use alloc::collections::BTreeMap;
use alloc::vec::Vec;
use intern_lang::Symbol;
use token_lang::Token;
use crate::{Context, Fragment, Kleene, MacroError, Pattern, Rule, Template};
#[derive(Clone, Debug)]
pub(crate) enum Inst<K> {
Token(K),
Open { open: K, close: K },
Close,
Bind { slot: usize, fragment: Fragment<K> },
Enter(usize),
Iter(usize),
Split(usize, usize),
Jump(usize),
Accept,
}
#[derive(Clone, Debug)]
pub(crate) enum Op<K> {
Token(Token<K>, Context),
Open(Token<K>, Token<K>),
Close,
Var(usize),
Repeat {
end: usize,
locks: (usize, usize),
separator: Option<(Token<K>, Context)>,
},
End { start: usize },
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Slot {
chain: usize,
pub(crate) depth: usize,
}
#[derive(Clone, Debug)]
pub(crate) struct CompiledRule<K> {
pub(crate) program: Vec<Inst<K>>,
pub(crate) ops: Vec<Op<K>>,
pub(crate) slots: Vec<Slot>,
chains: Vec<usize>,
pub(crate) locks: Vec<usize>,
pub(crate) reps: usize,
pub(crate) lead: Option<usize>,
}
impl<K> CompiledRule<K> {
#[inline]
pub(crate) fn chain(&self, slot: usize) -> &[usize] {
self.slots
.get(slot)
.and_then(|info| self.chains.get(info.chain..info.chain + info.depth))
.unwrap_or(&[])
}
}
pub(crate) fn compile_rule<K>(rule: Rule<K>, index: usize) -> Result<CompiledRule<K>, MacroError> {
let mut compiled = CompiledRule {
program: Vec::new(),
ops: Vec::new(),
slots: Vec::new(),
chains: Vec::new(),
locks: Vec::new(),
reps: 0,
lead: None,
};
let names = compile_pattern(rule.pattern, index, &mut compiled)?;
compile_template(rule.template, index, &names, &mut compiled)?;
compiled.lead = lead(&compiled.program);
Ok(compiled)
}
fn lead<K>(program: &[Inst<K>]) -> Option<usize> {
let mut pc = 0;
loop {
match program.get(pc)? {
Inst::Enter(_) | Inst::Iter(_) => pc += 1,
Inst::Token(_) | Inst::Open { .. } => return Some(pc),
_ => return None,
}
}
}
enum PatternWork<K> {
Element(Pattern<K>),
CloseGroup,
EndRepeat(RepeatFrame<K>),
}
struct RepeatFrame<K> {
iterate: usize,
entry: Option<usize>,
separator: Option<K>,
kleene: Kleene,
}
fn compile_pattern<K>(
pattern: Vec<Pattern<K>>,
rule: usize,
out: &mut CompiledRule<K>,
) -> Result<BTreeMap<Symbol, usize>, MacroError> {
let mut names = BTreeMap::new();
let mut chain: Vec<usize> = Vec::new();
let mut consumes: Vec<bool> = alloc::vec![false];
let mut work: Vec<PatternWork<K>> = pattern
.into_iter()
.rev()
.map(PatternWork::Element)
.collect();
while let Some(item) = work.pop() {
match item {
PatternWork::Element(Pattern::Token(kind)) => {
set_consumes(&mut consumes);
out.program.push(Inst::Token(kind));
}
PatternWork::Element(Pattern::Group { open, close, body }) => {
set_consumes(&mut consumes);
out.program.push(Inst::Open { open, close });
consumes.push(false);
work.push(PatternWork::CloseGroup);
work.extend(body.into_iter().rev().map(PatternWork::Element));
}
PatternWork::CloseGroup => {
consumes.truncate(consumes.len().saturating_sub(1));
out.program.push(Inst::Close);
}
PatternWork::Element(Pattern::Bind { name, fragment }) => {
let slot = out.slots.len();
if names.insert(name, slot).is_some() {
return Err(MacroError::DuplicateBinding { rule, name });
}
out.slots.push(Slot {
chain: out.chains.len(),
depth: chain.len(),
});
out.chains.extend_from_slice(&chain);
set_consumes(&mut consumes);
out.program.push(Inst::Bind { slot, fragment });
}
PatternWork::Element(Pattern::Repeat {
body,
separator,
kleene,
}) => {
if kleene == Kleene::ZeroOrOne && separator.is_some() {
return Err(MacroError::OptionalSeparator { rule });
}
let rep = out.reps;
out.reps += 1;
out.program.push(Inst::Enter(rep));
let entry = if kleene == Kleene::OneOrMore {
None
} else {
out.program.push(Inst::Split(0, 0));
Some(out.program.len() - 1)
};
let iterate = out.program.len();
out.program.push(Inst::Iter(rep));
chain.push(rep);
consumes.push(false);
work.push(PatternWork::EndRepeat(RepeatFrame {
iterate,
entry,
separator,
kleene,
}));
work.extend(body.into_iter().rev().map(PatternWork::Element));
}
PatternWork::EndRepeat(frame) => {
if consumes.pop() != Some(true) {
return Err(MacroError::EmptyRepetition { rule });
}
chain.truncate(chain.len().saturating_sub(1));
if frame.kleene == Kleene::OneOrMore {
set_consumes(&mut consumes);
}
close_repeat(&mut out.program, frame);
}
}
}
out.program.push(Inst::Accept);
Ok(names)
}
#[inline]
fn set_consumes(consumes: &mut [bool]) {
if let Some(flag) = consumes.last_mut() {
*flag = true;
}
}
fn close_repeat<K>(program: &mut Vec<Inst<K>>, frame: RepeatFrame<K>) {
if frame.kleene != Kleene::ZeroOrOne {
let split = program.len();
match frame.separator {
Some(separator) => {
program.push(Inst::Split(split + 1, split + 3));
program.push(Inst::Token(separator));
program.push(Inst::Jump(frame.iterate));
}
None => program.push(Inst::Split(frame.iterate, split + 1)),
}
}
let exit = program.len();
if let Some(entry) = frame.entry {
if let Some(inst) = program.get_mut(entry) {
*inst = Inst::Split(frame.iterate, exit);
}
}
}
enum TemplateWork<K> {
Element(Template<K>),
CloseGroup,
End { start: usize },
}
fn compile_template<K>(
template: Vec<Template<K>>,
rule: usize,
names: &BTreeMap<Symbol, usize>,
out: &mut CompiledRule<K>,
) -> Result<(), MacroError> {
let mut open: Vec<Vec<usize>> = Vec::new();
let mut work: Vec<TemplateWork<K>> = template
.into_iter()
.rev()
.map(TemplateWork::Element)
.collect();
while let Some(item) = work.pop() {
match item {
TemplateWork::Element(Template::Token { token, ctx }) => {
out.ops.push(Op::Token(token, ctx));
}
TemplateWork::Element(Template::Group {
open: open_token,
close,
body,
}) => {
out.ops.push(Op::Open(open_token, close));
work.push(TemplateWork::CloseGroup);
work.extend(body.into_iter().rev().map(TemplateWork::Element));
}
TemplateWork::CloseGroup => out.ops.push(Op::Close),
TemplateWork::Element(Template::Var(name)) => {
let slot = *names
.get(&name)
.ok_or(MacroError::UnboundVariable { rule, name })?;
let depth = out.slots.get(slot).map_or(0, |info| info.depth);
if depth > open.len() {
return Err(MacroError::StillRepeating { rule, name });
}
for locks in open.iter_mut().take(depth) {
if !locks.contains(&slot) {
locks.push(slot);
}
}
out.ops.push(Op::Var(slot));
}
TemplateWork::Element(Template::Repeat { body, separator }) => {
let separator = separator.map(|token| (token, Context::ROOT));
open_repeat(body, separator, &mut open, &mut work, out);
}
TemplateWork::Element(Template::RepeatSeparated {
body,
separator,
ctx,
}) => open_repeat(body, Some((separator, ctx)), &mut open, &mut work, out),
TemplateWork::End { start } => {
let locks = open.pop().unwrap_or_default();
if locks.is_empty() {
return Err(MacroError::NoRepeatingVariable { rule });
}
let range = (out.locks.len(), locks.len());
out.locks.extend_from_slice(&locks);
let end = out.ops.len();
out.ops.push(Op::End { start });
if let Some(Op::Repeat {
end: patch_end,
locks: patch_locks,
..
}) = out.ops.get_mut(start)
{
*patch_end = end;
*patch_locks = range;
}
}
}
}
Ok(())
}
fn open_repeat<K>(
body: Vec<Template<K>>,
separator: Option<(Token<K>, Context)>,
open: &mut Vec<Vec<usize>>,
work: &mut Vec<TemplateWork<K>>,
out: &mut CompiledRule<K>,
) {
let start = out.ops.len();
out.ops.push(Op::Repeat {
end: 0,
locks: (0, 0),
separator,
});
open.push(Vec::new());
work.push(TemplateWork::End { start });
work.extend(body.into_iter().rev().map(TemplateWork::Element));
}