use alloc::{borrow::Cow, boxed::Box, vec::Vec};
use core::{mem, slice};
pub(crate) type Text = Cow<'static, str>;
#[derive(Clone, Debug)]
pub struct Rule(pub(crate) Expr);
#[derive(Clone, Debug)]
pub(crate) enum Expr {
Blank,
String(Text),
Pattern(Text),
Symbol(Text),
Seq(Vec<Rule>),
Choice(Vec<Rule>),
Repeat(Box<Rule>),
Repeat1(Box<Rule>),
Field(Text, Box<Rule>),
Alias(Text, Box<Rule>),
Token(Box<Rule>),
Immediate(Box<Rule>),
Prec(Prec, i32, Box<Rule>),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Prec {
Plain,
Left,
Right,
Dynamic,
}
impl Rule {
#[inline]
#[must_use]
pub fn symbol(name: impl Into<Cow<'static, str>>) -> Rule {
Rule(Expr::Symbol(name.into()))
}
#[inline]
#[must_use]
pub fn string(text: impl Into<Cow<'static, str>>) -> Rule {
Rule(Expr::String(text.into()))
}
#[inline]
#[must_use]
pub fn pattern(regex: impl Into<Cow<'static, str>>) -> Rule {
Rule(Expr::Pattern(regex.into()))
}
#[inline]
#[must_use]
pub const fn blank() -> Rule {
Rule(Expr::Blank)
}
#[must_use]
pub fn seq(rules: impl IntoIterator<Item = Rule>) -> Rule {
let rules: Vec<Rule> = rules.into_iter().collect();
if rules.is_empty() {
return Rule::blank();
}
Rule(Expr::Seq(rules))
}
#[must_use]
pub fn choice(rules: impl IntoIterator<Item = Rule>) -> Rule {
Rule(Expr::Choice(rules.into_iter().collect()))
}
#[must_use]
pub fn optional(rule: Rule) -> Rule {
Rule(Expr::Choice(alloc::vec![rule, Rule::blank()]))
}
#[must_use]
pub fn repeat(rule: Rule) -> Rule {
Rule(Expr::Repeat(Box::new(rule)))
}
#[must_use]
pub fn repeat1(rule: Rule) -> Rule {
Rule(Expr::Repeat1(Box::new(rule)))
}
#[must_use]
pub fn field(name: impl Into<Cow<'static, str>>, rule: Rule) -> Rule {
Rule(Expr::Field(name.into(), Box::new(rule)))
}
#[must_use]
pub fn alias(rule: Rule, name: impl Into<Cow<'static, str>>) -> Rule {
Rule(Expr::Alias(name.into(), Box::new(rule)))
}
#[must_use]
pub fn token(rule: Rule) -> Rule {
Rule(Expr::Token(Box::new(rule)))
}
#[must_use]
pub fn immediate(rule: Rule) -> Rule {
Rule(Expr::Immediate(Box::new(rule)))
}
#[must_use]
pub fn prec(level: i32, rule: Rule) -> Rule {
Rule(Expr::Prec(Prec::Plain, level, Box::new(rule)))
}
#[must_use]
pub fn prec_left(level: i32, rule: Rule) -> Rule {
Rule(Expr::Prec(Prec::Left, level, Box::new(rule)))
}
#[must_use]
pub fn prec_right(level: i32, rule: Rule) -> Rule {
Rule(Expr::Prec(Prec::Right, level, Box::new(rule)))
}
#[must_use]
pub fn prec_dynamic(level: i32, rule: Rule) -> Rule {
Rule(Expr::Prec(Prec::Dynamic, level, Box::new(rule)))
}
#[inline]
pub(crate) fn children(&self) -> &[Rule] {
match &self.0 {
Expr::Seq(rules) | Expr::Choice(rules) => rules,
Expr::Repeat(rule)
| Expr::Repeat1(rule)
| Expr::Field(_, rule)
| Expr::Alias(_, rule)
| Expr::Token(rule)
| Expr::Immediate(rule)
| Expr::Prec(_, _, rule) => slice::from_ref(&**rule),
Expr::Blank | Expr::String(_) | Expr::Pattern(_) | Expr::Symbol(_) => &[],
}
}
#[inline]
pub(crate) fn as_optional(&self) -> Option<&Rule> {
match &self.0 {
Expr::Choice(rules) => match rules.as_slice() {
[rule, Rule(Expr::Blank)] => Some(rule),
_ => None,
},
_ => None,
}
}
#[inline]
pub(crate) fn is_terminal(&self) -> bool {
matches!(
self.0,
Expr::String(_) | Expr::Pattern(_) | Expr::Token(_) | Expr::Immediate(_)
)
}
pub(crate) fn is_single_token(&self) -> bool {
let mut rule = self;
loop {
match &rule.0 {
Expr::Prec(_, _, inner) | Expr::Field(_, inner) => rule = inner,
_ => return rule.is_terminal(),
}
}
}
pub(crate) fn names_nodes(&self) -> bool {
let mut stack = alloc::vec![self];
while let Some(rule) = stack.pop() {
if matches!(rule.0, Expr::Symbol(_) | Expr::Alias(..)) {
return true;
}
stack.extend(rule.children());
}
false
}
pub(crate) fn same(&self, other: &Rule) -> bool {
let mut stack = alloc::vec![(self, other)];
while let Some((a, b)) = stack.pop() {
let leaves_equal = match (&a.0, &b.0) {
(Expr::Blank, Expr::Blank) => true,
(Expr::String(x), Expr::String(y))
| (Expr::Pattern(x), Expr::Pattern(y))
| (Expr::Symbol(x), Expr::Symbol(y)) => x == y,
(Expr::Seq(_), Expr::Seq(_))
| (Expr::Choice(_), Expr::Choice(_))
| (Expr::Repeat(_), Expr::Repeat(_))
| (Expr::Repeat1(_), Expr::Repeat1(_))
| (Expr::Token(_), Expr::Token(_))
| (Expr::Immediate(_), Expr::Immediate(_)) => true,
(Expr::Field(x, _), Expr::Field(y, _)) | (Expr::Alias(x, _), Expr::Alias(y, _)) => {
x == y
}
(Expr::Prec(k, n, _), Expr::Prec(l, m, _)) => k == l && n == m,
_ => false,
};
let (left, right) = (a.children(), b.children());
if !leaves_equal || left.len() != right.len() {
return false;
}
stack.extend(left.iter().zip(right));
}
true
}
fn detach_into(&mut self, stack: &mut Vec<Rule>) {
let mut detach = |rule: &mut Rule| {
if !rule.children().is_empty() {
stack.push(mem::replace(rule, Rule::blank()));
}
};
match &mut self.0 {
Expr::Seq(rules) | Expr::Choice(rules) => rules.iter_mut().for_each(detach),
Expr::Repeat(rule)
| Expr::Repeat1(rule)
| Expr::Field(_, rule)
| Expr::Alias(_, rule)
| Expr::Token(rule)
| Expr::Immediate(rule)
| Expr::Prec(_, _, rule) => detach(rule),
Expr::Blank | Expr::String(_) | Expr::Pattern(_) | Expr::Symbol(_) => {}
}
}
}
impl Drop for Rule {
fn drop(&mut self) {
if self
.children()
.iter()
.all(|child| child.children().is_empty())
{
return;
}
let mut stack = Vec::new();
self.detach_into(&mut stack);
while let Some(mut rule) = stack.pop() {
rule.detach_into(&mut stack);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_optional_is_choice_with_trailing_blank() {
let rule = Rule::optional(Rule::string("x"));
let inner = rule
.as_optional()
.map(|r| matches!(&r.0, Expr::String(s) if s == "x"));
assert_eq!(inner, Some(true));
assert!(
Rule::choice([Rule::blank(), Rule::string("x")])
.as_optional()
.is_none()
);
assert!(Rule::choice([Rule::string("x")]).as_optional().is_none());
}
#[test]
fn test_children_cover_every_shape() {
assert!(Rule::blank().children().is_empty());
assert!(Rule::symbol("a").children().is_empty());
assert_eq!(
Rule::seq([Rule::blank(), Rule::blank()]).children().len(),
2
);
assert_eq!(Rule::prec_left(1, Rule::blank()).children().len(), 1);
assert_eq!(Rule::field("f", Rule::blank()).children().len(), 1);
}
#[test]
fn test_is_terminal_only_for_unwrapped_tokens() {
assert!(Rule::string("a").is_terminal());
assert!(Rule::pattern("a").is_terminal());
assert!(Rule::token(Rule::seq([Rule::string("a")])).is_terminal());
assert!(Rule::immediate(Rule::string("a")).is_terminal());
assert!(!Rule::prec(1, Rule::string("a")).is_terminal());
assert!(!Rule::symbol("a").is_terminal());
assert!(!Rule::seq([Rule::string("a")]).is_terminal());
}
#[test]
fn test_drop_deeply_nested_rule_does_not_overflow() {
let mut rule = Rule::string("x");
for i in 0..200_000 {
rule = if i % 2 == 0 {
Rule::seq([rule, Rule::string("y")])
} else {
Rule::repeat(rule)
};
}
drop(rule);
}
#[test]
fn test_clone_is_independent() {
let a = Rule::seq([Rule::symbol("a"), Rule::string("b")]);
let b = a.clone();
drop(a);
assert_eq!(b.children().len(), 2);
}
}