use alloc::vec::Vec;
use crate::compile::{CompiledRule, Op};
use crate::context::Hygiene;
use crate::matcher::{Matcher, OpenGroup};
use crate::{Context, ExpandError, Limit, Tree};
#[derive(Clone, Copy, Debug)]
pub(crate) struct Frame {
index: usize,
count: usize,
separator: Option<Context>,
}
#[derive(Clone, Debug)]
pub(crate) struct Scratch<K> {
frames: Vec<Frame>,
groups: Vec<OpenGroup<K>>,
marks: Vec<(Context, Context)>,
}
impl<K> Default for Scratch<K> {
fn default() -> Self {
Self {
frames: Vec::new(),
groups: Vec::new(),
marks: Vec::new(),
}
}
}
pub(crate) struct Expansion<'a, K> {
pub(crate) rule: &'a CompiledRule<K>,
pub(crate) index: usize,
pub(crate) matcher: &'a Matcher<K>,
pub(crate) hygiene: &'a mut Hygiene,
pub(crate) expansion: usize,
pub(crate) tokens_left: usize,
pub(crate) tokens_max: usize,
}
struct Meter {
left: usize,
max: usize,
}
impl Meter {
#[cold]
#[inline(never)]
fn exceeded(&self) -> ExpandError {
ExpandError::Budget(Limit::Tokens { max: self.max })
}
#[inline]
fn charge(&mut self, n: usize) -> Result<(), ExpandError> {
match self.left.checked_sub(n) {
Some(left) => {
self.left = left;
Ok(())
}
None => Err(self.exceeded()),
}
}
}
pub(crate) fn transcribe<K: Clone>(
ex: Expansion<'_, K>,
scratch: &mut Scratch<K>,
) -> Result<(Vec<Tree<K>>, usize), ExpandError> {
let mut out = Vec::new();
match write(ex, scratch, &mut out) {
Ok(written) => Ok((out, written)),
Err(err) => {
Tree::dismantle(out);
Tree::dismantle(scratch.groups.drain(..).flat_map(|(_, _, trees)| trees));
Err(err)
}
}
}
fn write<K: Clone>(
ex: Expansion<'_, K>,
scratch: &mut Scratch<K>,
out: &mut Vec<Tree<K>>,
) -> Result<usize, ExpandError> {
let Expansion {
rule,
index,
matcher,
hygiene,
expansion,
tokens_left,
tokens_max,
} = ex;
let mut meter = Meter {
left: tokens_left,
max: tokens_max,
};
let mismatch = ExpandError::RepetitionMismatch { rule: index };
scratch.frames.clear();
scratch.groups.clear();
scratch.marks.clear();
let mut pc = 0;
while let Some(op) = rule.ops.get(pc) {
match op {
Op::Token(token, ctx) => {
meter.charge(1)?;
let ctx = hygiene
.mark(*ctx, expansion, &mut scratch.marks)
.ok_or(ExpandError::ContextOverflow)?;
current(out, &mut scratch.groups).push(Tree::Token {
token: token.clone(),
ctx,
});
}
Op::Open(open, close) => {
meter.charge(2)?;
scratch
.groups
.push((open.clone(), close.clone(), Vec::new()));
}
Op::Close => {
if let Some((open, close, trees)) = scratch.groups.pop() {
current(out, &mut scratch.groups).push(Tree::Group { open, close, trees });
}
}
Op::Var(slot) => {
let chain = rule.chain(*slot);
let instance =
locate(matcher, chain, &scratch.frames, chain.len()).ok_or(mismatch)?;
let at = matcher
.leaves
.get(*slot)
.and_then(|leaves| leaves.get(instance))
.ok_or(mismatch)?;
if !matcher.emit(*at, current(out, &mut scratch.groups), &mut meter.left) {
return Err(meter.exceeded());
}
}
Op::Repeat { end, locks, .. } => {
let count = lockstep(rule, matcher, *locks, &scratch.frames).ok_or(mismatch)?;
if count == 0 {
pc = *end;
} else {
scratch.frames.push(Frame {
index: 0,
count,
separator: None,
});
}
}
Op::End { start } => {
if let Some(frame) = scratch.frames.last_mut() {
frame.index += 1;
if frame.index < frame.count {
if let Some(Op::Repeat {
separator: Some((separator, def)),
..
}) = rule.ops.get(*start)
{
meter.charge(1)?;
let ctx = match frame.separator {
Some(ctx) => ctx,
None => {
let ctx = hygiene
.mark(*def, expansion, &mut scratch.marks)
.ok_or(ExpandError::ContextOverflow)?;
frame.separator = Some(ctx);
ctx
}
};
current(out, &mut scratch.groups).push(Tree::Token {
token: separator.clone(),
ctx,
});
}
pc = *start;
} else {
scratch.frames.truncate(scratch.frames.len() - 1);
}
}
}
}
pc += 1;
}
Ok(tokens_left.saturating_sub(meter.left))
}
#[inline]
fn current<'a, K>(
out: &'a mut Vec<Tree<K>>,
groups: &'a mut [OpenGroup<K>],
) -> &'a mut Vec<Tree<K>> {
match groups.last_mut() {
Some((_, _, trees)) => trees,
None => out,
}
}
#[inline]
fn locate<K>(
matcher: &Matcher<K>,
chain: &[usize],
frames: &[Frame],
levels: usize,
) -> Option<usize> {
let mut linear = 0;
for (rep, frame) in chain.iter().zip(frames).take(levels) {
linear = matcher.starts.get(*rep)?.get(linear)? + frame.index;
}
Some(linear)
}
fn lockstep<K>(
rule: &CompiledRule<K>,
matcher: &Matcher<K>,
(start, len): (usize, usize),
frames: &[Frame],
) -> Option<usize> {
let depth = frames.len();
let mut agreed: Option<usize> = None;
for &slot in rule.locks.get(start..start + len)? {
let chain = rule.chain(slot);
let instance = locate(matcher, chain, frames, depth)?;
let count = *matcher.counts.get(*chain.get(depth)?)?.get(instance)?;
match agreed {
Some(previous) if previous != count => return None,
_ => agreed = Some(count),
}
}
agreed
}