use alloc::{format, string::String, vec, vec::Vec};
use core::ptr;
use crate::{
Error, Grammar, Rule,
pattern::{Checker, Invalid},
rule::{Expr, Prec, Text},
};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Def {
Rule(usize),
External,
}
pub(crate) struct Index<'g> {
entries: Vec<(&'g str, Def)>,
}
impl<'g> Index<'g> {
pub(crate) fn new(grammar: &'g Grammar) -> Index<'g> {
let mut entries = Vec::with_capacity(grammar.rules.len() + grammar.externals.len());
entries.extend(
grammar
.rules
.iter()
.enumerate()
.map(|(i, (name, _))| (&**name, Def::Rule(i))),
);
entries.extend(
grammar
.externals
.iter()
.map(|name| (&**name, Def::External)),
);
entries.sort_unstable_by(|a, b| a.0.cmp(b.0).then(rank(a.1).cmp(&rank(b.1))));
Index { entries }
}
pub(crate) fn get(&self, name: &str) -> Option<Def> {
let at = self.entries.partition_point(|(n, _)| *n < name);
match self.entries.get(at) {
Some(&(n, def)) if n == name => Some(def),
_ => None,
}
}
fn duplicate(&self) -> Option<&'g str> {
self.entries
.windows(2)
.filter_map(|pair| match (pair[0], pair[1]) {
((a, Def::Rule(_)), (b, Def::Rule(second))) if a == b => Some((second, a)),
_ => None,
})
.min_by_key(|&(second, _)| second)
.map(|(_, name)| name)
}
}
fn rank(def: Def) -> usize {
match def {
Def::Rule(i) => i,
Def::External => usize::MAX,
}
}
struct Graph {
starts: Vec<usize>,
edges: Vec<usize>,
unit_starts: Vec<usize>,
units: Vec<usize>,
extra_roots: Vec<usize>,
}
impl Graph {
fn edges(&self, rule: usize) -> &[usize] {
&self.edges[self.starts[rule]..self.starts[rule + 1]]
}
fn units(&self, rule: usize) -> &[usize] {
&self.units[self.unit_starts[rule]..self.unit_starts[rule + 1]]
}
}
struct Reach {
reachable: Vec<bool>,
used: Vec<bool>,
}
pub(crate) fn validate(grammar: &Grammar) -> Result<(), Error> {
names(grammar)?;
let index = Index::new(grammar);
if let Some(name) = index.duplicate() {
return Err(Error::DuplicateRule {
name: String::from(name),
});
}
let mut patterns = Checker::default();
let graph = load(grammar, &index, &mut patterns)?;
references(grammar, &index)?;
let reach = reach(grammar, &graph);
unit_cycles(grammar, &graph, &reach)?;
reachable_rules(grammar, &reach, &mut patterns)?;
word(grammar, &index, &reach)?;
externals(grammar, &index, &reach)?;
inline(grammar, &index, &reach)?;
supertypes(grammar, &index, &reach)
}
fn names(grammar: &Grammar) -> Result<(), Error> {
identifier(&grammar.name)?;
let Some((start, _)) = grammar.rules.first() else {
return Err(Error::NoRules);
};
for name in grammar
.rules
.iter()
.map(|(name, _)| name)
.chain(&grammar.externals)
{
identifier(name)?;
if name == "__proto__" {
return Err(invalid_name(name));
}
}
if is_hidden(start) {
return Err(Error::HiddenStart {
name: String::from(&**start),
});
}
Ok(())
}
fn identifier(name: &str) -> Result<(), Error> {
let bytes = name.as_bytes();
let valid = matches!(bytes.first(), Some(b) if b.is_ascii_alphabetic() || *b == b'_')
&& bytes[1..]
.iter()
.all(|b| b.is_ascii_alphanumeric() || *b == b'_');
if valid {
Ok(())
} else {
Err(invalid_name(name))
}
}
fn invalid_name(name: &str) -> Error {
Error::InvalidName {
name: String::from(name),
}
}
#[inline]
pub(crate) fn is_hidden(name: &str) -> bool {
name.starts_with('_')
}
fn undefined(symbol: &str, rule: &str) -> Error {
Error::UndefinedSymbol {
symbol: String::from(symbol),
rule: String::from(rule),
}
}
fn load(grammar: &Grammar, index: &Index<'_>, patterns: &mut Checker) -> Result<Graph, Error> {
let count = grammar.rules.len();
let mut graph = Graph {
starts: Vec::with_capacity(count + 1),
edges: Vec::new(),
unit_starts: Vec::with_capacity(count + 1),
units: Vec::new(),
extra_roots: Vec::new(),
};
let mut stack = Vec::new();
for (i, (name, body)) in grammar.rules.iter().enumerate() {
graph.starts.push(graph.edges.len());
graph.unit_starts.push(graph.units.len());
let refs = Refs {
edges: &mut graph.edges,
units: &mut graph.units,
rule: i,
};
load_rule(body, name, false, index, &mut stack, refs, patterns)?;
}
graph.starts.push(graph.edges.len());
graph.unit_starts.push(graph.units.len());
let (mut edges, mut units) = (Vec::new(), Vec::new());
for extra in grammar.extras.iter().flatten() {
match &extra.0 {
Expr::Symbol(name) => match index.get(name) {
None => return Err(undefined(name, "extras")),
Some(Def::Rule(i)) => graph.extra_roots.push(i),
Some(Def::External) => {}
},
_ => {
let refs = Refs {
edges: &mut edges,
units: &mut units,
rule: usize::MAX,
};
load_rule(extra, "extras", true, index, &mut stack, refs, patterns)?;
}
}
}
Ok(graph)
}
struct Refs<'a> {
edges: &'a mut Vec<usize>,
units: &'a mut Vec<usize>,
rule: usize,
}
fn load_rule<'g>(
root: &'g Rule,
rule: &str,
lexical: bool,
index: &Index<'_>,
stack: &mut Vec<(&'g Rule, bool, bool)>,
refs: Refs<'_>,
patterns: &mut Checker,
) -> Result<(), Error> {
stack.clear();
stack.push((root, lexical, true));
while let Some((node, in_token, unit)) = stack.pop() {
match &node.0 {
Expr::Symbol(name) => {
let def = index.get(name).ok_or_else(|| undefined(name, rule))?;
if in_token {
return Err(Error::SymbolInToken {
symbol: String::from(&**name),
rule: String::from(rule),
});
}
if let Def::Rule(i) = def {
refs.edges.push(i);
if unit && i != refs.rule {
refs.units.push(i);
}
}
}
Expr::Pattern(text) if text.is_empty() => {
return Err(Error::EmptyString {
rule: String::from(rule),
});
}
Expr::Pattern(text) => patterns
.javascript(text)
.map_err(|problem| invalid_pattern(rule, text, problem))?,
Expr::Choice(rules) if rules.is_empty() => {
return Err(Error::EmptyChoice {
rule: String::from(rule),
});
}
Expr::Field(name, _) | Expr::Alias(name, _) => identifier(name)?,
_ => {}
}
let in_token = in_token || matches!(node.0, Expr::Token(_) | Expr::Immediate(_));
let unit = unit
&& matches!(
node.0,
Expr::Choice(_) | Expr::Prec(..) | Expr::Field(..) | Expr::Alias(..)
);
stack.extend(
node.children()
.iter()
.rev()
.map(|child| (child, in_token, unit)),
);
}
Ok(())
}
fn references(grammar: &Grammar, index: &Index<'_>) -> Result<(), Error> {
let defined = |name: &Text, place: &str| match index.get(name) {
Some(_) => Ok(()),
None => Err(undefined(name, place)),
};
if let Some(word) = &grammar.word {
defined(word, "word")?;
}
for name in grammar.conflicts.iter().flatten() {
defined(name, "conflicts")?;
}
for name in &grammar.inline {
defined(name, "inline")?;
}
for name in &grammar.supertypes {
defined(name, "supertypes")?;
}
Ok(())
}
fn reach(grammar: &Grammar, graph: &Graph) -> Reach {
let count = grammar.rules.len();
let mut reachable = vec![false; count];
let mut used = vec![false; count];
let mut queue = Vec::with_capacity(count);
for &root in [0].iter().chain(&graph.extra_roots) {
if !reachable[root] {
reachable[root] = true;
queue.push(root);
}
}
for &root in &graph.extra_roots {
used[root] = true;
}
while let Some(rule) = queue.pop() {
for &next in graph.edges(rule) {
used[next] = true;
if !reachable[next] {
reachable[next] = true;
queue.push(next);
}
}
}
Reach { reachable, used }
}
fn reachable_rules(grammar: &Grammar, reach: &Reach, patterns: &mut Checker) -> Result<(), Error> {
let mut walk = Vec::new();
let mut frames = Vec::new();
for (i, (name, body)) in grammar.rules.iter().enumerate() {
if !reach.reachable[i] {
continue;
}
walk.clear();
walk.push(body);
while let Some(node) = walk.pop() {
match &node.0 {
Expr::String(text) if text.is_empty() => {
return Err(Error::EmptyString {
rule: String::from(&**name),
});
}
Expr::Pattern(text) => patterns
.tree_sitter(text)
.map_err(|problem| invalid_pattern(name, text, problem))?,
_ => walk.extend(node.children()),
}
}
let (empty, empty_repeat) = nullability(body, &mut frames);
if empty_repeat || (empty && reach.used[i]) {
return Err(Error::MatchesEmpty {
rule: String::from(&**name),
});
}
}
for extra in grammar.extras.iter().flatten() {
walk.clear();
walk.push(extra);
while let Some(node) = walk.pop() {
match &node.0 {
Expr::Pattern(text) => patterns
.tree_sitter(text)
.map_err(|problem| invalid_pattern("extras", text, problem))?,
_ => walk.extend(node.children()),
}
}
}
Ok(())
}
fn invalid_pattern(rule: &str, pattern: &str, problem: Invalid) -> Error {
const PREVIEW: usize = 40;
let mut preview = String::new();
for (n, c) in pattern.chars().enumerate() {
if n == PREVIEW {
preview.push('…');
break;
}
if c.is_control() || c == '\u{2028}' || c == '\u{2029}' {
preview.extend(c.escape_default());
} else {
preview.push(c);
}
}
Error::EmptyString {
rule: format!(
"{rule}: {} at byte {} of `{preview}`",
problem.reason, problem.at
),
}
}
struct Frame<'g> {
rule: &'g Rule,
next: usize,
value: bool,
}
fn nullability<'g>(root: &'g Rule, frames: &mut Vec<Frame<'g>>) -> (bool, bool) {
frames.clear();
let mut empty_repeat = false;
let mut current = root;
loop {
let mut value = match ¤t.0 {
Expr::Blank => true,
Expr::String(_)
| Expr::Pattern(_)
| Expr::Symbol(_)
| Expr::Token(_)
| Expr::Immediate(_) => false,
Expr::Seq(rules) | Expr::Choice(rules) => match rules.first() {
None => matches!(current.0, Expr::Seq(_)),
Some(first) => {
let value = matches!(current.0, Expr::Seq(_));
frames.push(Frame {
rule: current,
next: 1,
value,
});
current = first;
continue;
}
},
Expr::Repeat(inner)
| Expr::Repeat1(inner)
| Expr::Field(_, inner)
| Expr::Alias(_, inner)
| Expr::Prec(_, _, inner) => {
frames.push(Frame {
rule: current,
next: 1,
value: false,
});
current = inner;
continue;
}
};
loop {
let Some(frame) = frames.last_mut() else {
return (value, empty_repeat);
};
let parent: &'g Rule = frame.rule;
match &parent.0 {
Expr::Seq(rules) | Expr::Choice(rules) => {
frame.value = if matches!(parent.0, Expr::Seq(_)) {
frame.value && value
} else {
frame.value || value
};
if let Some(next) = rules.get(frame.next) {
frame.next += 1;
current = next;
break;
}
value = frame.value;
}
Expr::Repeat(_) => {
empty_repeat |= value;
value = true;
}
Expr::Repeat1(_) => empty_repeat |= value,
_ => {}
}
let _finished = frames.pop();
}
}
}
fn unit_cycles(grammar: &Grammar, graph: &Graph, reach: &Reach) -> Result<(), Error> {
const WHITE: u8 = 0;
const GRAY: u8 = 1;
const BLACK: u8 = 2;
let count = grammar.rules.len();
let mut walk = Vec::new();
for (i, (name, body)) in grammar.rules.iter().enumerate() {
if reach.reachable[i] && is_hidden(name) && itself_under_precedence(body, name, &mut walk) {
return Err(Error::IndirectRecursion {
rule: String::from(&**name),
});
}
}
let mut color = vec![WHITE; count];
let mut stack: Vec<(usize, usize)> = Vec::new();
for start in 0..count {
if color[start] != WHITE || !reach.reachable[start] {
continue;
}
color[start] = GRAY;
stack.push((start, 0));
while let Some(top) = stack.last_mut() {
let (rule, at) = *top;
let Some(&next) = graph.units(rule).get(at) else {
color[rule] = BLACK;
let _finished = stack.pop();
continue;
};
top.1 += 1;
if color[next] == GRAY {
return Err(Error::IndirectRecursion {
rule: String::from(&*grammar.rules[next].0),
});
}
if color[next] == WHITE {
color[next] = GRAY;
stack.push((next, 0));
}
}
}
Ok(())
}
fn itself_under_precedence<'g>(
body: &'g Rule,
name: &str,
walk: &mut Vec<(&'g Rule, bool)>,
) -> bool {
walk.clear();
walk.push((body, false));
while let Some((node, ranked)) = walk.pop() {
match &node.0 {
Expr::Symbol(symbol) if ranked && symbol == name => return true,
Expr::Choice(alternatives) => {
walk.extend(alternatives.iter().map(|a| (a, ranked)));
}
Expr::Prec(kind, level, inner) => {
let ranked = ranked || (*kind != Prec::Dynamic && *level != 0);
walk.push((inner, ranked));
}
Expr::Seq(parts) => {
let mut solid = parts.iter().filter(|p| !matches!(p.0, Expr::Blank));
if let (Some(part), None) = (solid.next(), solid.next()) {
walk.push((part, ranked));
}
}
_ => {}
}
}
false
}
fn is_token_rule(grammar: &Grammar, reach: &Reach, i: usize, supertypes_hidden: bool) -> bool {
let (name, target) = &grammar.rules[i];
let hidden = is_hidden(name) || (supertypes_hidden && grammar.supertypes.contains(name));
if i == 0 || !target.is_terminal() || (hidden && is_literal(target)) {
return false;
}
let key = token_key(target);
let mut walk = Vec::new();
for (j, (_, body)) in grammar.rules.iter().enumerate() {
if !reach.reachable[j] {
continue;
}
walk.clear();
walk.push(body);
while let Some(node) = walk.pop() {
if node.is_terminal() {
if !ptr::eq(node, target) && token_key(node).same(key) {
return false;
}
} else {
walk.extend(node.children());
}
}
}
true
}
fn token_key(rule: &Rule) -> &Rule {
match &rule.0 {
Expr::Token(inner) if matches!(inner.0, Expr::String(_) | Expr::Pattern(_)) => inner,
_ => rule,
}
}
fn is_literal(rule: &Rule) -> bool {
let mut rule = match &rule.0 {
Expr::Token(inner) | Expr::Immediate(inner) => inner,
_ => rule,
};
loop {
match &rule.0 {
Expr::Prec(_, _, inner) | Expr::Field(_, inner) | Expr::Alias(_, inner) => rule = inner,
Expr::String(_) => return true,
_ => return false,
}
}
}
fn word(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
let Some(word) = &grammar.word else {
return Ok(());
};
match index.get(word) {
Some(Def::Rule(i)) if !is_token_rule(grammar, reach, i, true) => Err(Error::WordNotToken {
name: String::from(&**word),
}),
_ => Ok(()),
}
}
fn externals(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
for name in &grammar.externals {
if let Some(Def::Rule(i)) = index.get(name) {
if !is_token_rule(grammar, reach, i, true) {
return Err(Error::InvalidExternal {
name: String::from(&**name),
});
}
}
}
Ok(())
}
fn inline(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
const WHITE: u8 = 0;
const GRAY: u8 = 1;
const BLACK: u8 = 2;
if grammar.inline.is_empty() {
return Ok(());
}
let count = grammar.rules.len();
let mut inlined = vec![false; count];
for name in &grammar.inline {
let invalid = || Error::InvalidInline {
name: String::from(&**name),
};
let Some(Def::Rule(i)) = index.get(name) else {
return Err(invalid());
};
if i == 0 || is_token_rule(grammar, reach, i, false) {
return Err(invalid());
}
inlined[i] = true;
}
let mut edges: Vec<Vec<usize>> = vec![Vec::new(); count];
let mut walk = Vec::new();
for (i, (_, body)) in grammar.rules.iter().enumerate() {
if !inlined[i] {
continue;
}
walk.clear();
walk.push(body);
while let Some(node) = walk.pop() {
match &node.0 {
Expr::Symbol(name) => {
if let Some(Def::Rule(j)) = index.get(name) {
if inlined[j] {
edges[i].push(j);
}
}
}
Expr::Repeat(_) | Expr::Repeat1(_) | Expr::Token(_) | Expr::Immediate(_) => {}
_ => walk.extend(node.children()),
}
}
}
let mut color = vec![WHITE; count];
let mut stack: Vec<(usize, usize)> = Vec::new();
for name in &grammar.inline {
let Some(Def::Rule(start)) = index.get(name) else {
continue;
};
if color[start] != WHITE {
continue;
}
color[start] = GRAY;
stack.push((start, 0));
while let Some(top) = stack.last_mut() {
let (rule, at) = *top;
let Some(&next) = edges[rule].get(at) else {
color[rule] = BLACK;
let _finished = stack.pop();
continue;
};
top.1 += 1;
if color[next] == GRAY {
return Err(Error::InvalidInline {
name: String::from(&*grammar.rules[next].0),
});
}
if color[next] == WHITE {
color[next] = GRAY;
stack.push((next, 0));
}
}
}
Ok(())
}
fn supertypes(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
if grammar.supertypes.is_empty() {
return Ok(());
}
let nodes = NodeCounts::new(grammar, index);
let mut walk = Vec::new();
let mut expanded = Vec::new();
for name in &grammar.supertypes {
let invalid = || Error::InvalidSupertype {
name: String::from(&**name),
};
let Some(Def::Rule(i)) = index.get(name) else {
return Err(invalid());
};
if !reach.reachable[i] || grammar.inline.contains(name) {
continue;
}
let body = &grammar.rules[i].1;
if is_token_rule(grammar, reach, i, true) || nodes.most(body) > 1 {
return Err(invalid());
}
walk.clear();
walk.push(body);
expanded.clear();
expanded.resize(grammar.rules.len(), false);
while let Some(node) = walk.pop() {
match &node.0 {
Expr::Symbol(symbol) if symbol == name => return Err(invalid()),
Expr::Symbol(symbol) => {
if let Some(Def::Rule(j)) = index.get(symbol) {
if nodes.expands[j] && !expanded[j] {
expanded[j] = true;
walk.push(&grammar.rules[j].1);
}
}
}
Expr::Alias(..) | Expr::Token(_) | Expr::Immediate(_) => {}
_ => walk.extend(node.children()),
}
}
}
Ok(())
}
struct NodeCounts<'g, 'i> {
index: &'i Index<'g>,
expands: Vec<bool>,
counts: Vec<u8>,
}
impl<'g, 'i> NodeCounts<'g, 'i> {
fn new(grammar: &'g Grammar, index: &'i Index<'g>) -> Self {
let expands: Vec<bool> = grammar
.rules
.iter()
.map(|(name, body)| {
(is_hidden(name) || grammar.inline.contains(name)) && !body.is_terminal()
})
.collect();
let mut counts = NodeCounts {
index,
counts: vec![0; expands.len()],
expands,
};
let mut changed = true;
while changed {
changed = false;
for (i, (_, body)) in grammar.rules.iter().enumerate() {
if counts.expands[i] {
let count = counts.most(body);
if count > counts.counts[i] {
counts.counts[i] = count;
changed = true;
}
}
}
}
counts
}
fn most(&self, root: &Rule) -> u8 {
let mut frames: Vec<(&Rule, usize, u8, bool)> = Vec::new();
let mut current = root;
let mut aliased = false;
loop {
let mut value = match ¤t.0 {
Expr::Blank => 0,
Expr::String(_) | Expr::Pattern(_) | Expr::Token(_) | Expr::Immediate(_) => 1,
Expr::Symbol(name) => match self.index.get(name) {
Some(Def::Rule(j)) if self.expands[j] && !aliased => self.counts[j],
_ => 1,
},
Expr::Choice(rules) if rules.is_empty() => 0,
Expr::Repeat(_) | Expr::Repeat1(_) => 2,
_ => {
frames.push((current, 1, 0, aliased));
aliased = aliased || matches!(current.0, Expr::Alias(..));
current = ¤t.children()[0];
continue;
}
};
loop {
let Some(frame) = frames.last_mut() else {
return value;
};
let parent = frame.0;
frame.2 = match parent.0 {
Expr::Seq(_) => frame.2.saturating_add(value).min(2),
Expr::Choice(_) => frame.2.max(value),
_ => value,
};
if let Some(next) = parent.children().get(frame.1) {
frame.1 += 1;
aliased = frame.3 || matches!(parent.0, Expr::Alias(..));
current = next;
break;
}
value = frame.2;
let _finished = frames.pop();
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn empty(rule: &Rule) -> bool {
nullability(rule, &mut Vec::new()).0
}
fn empty_repeat(rule: &Rule) -> bool {
nullability(rule, &mut Vec::new()).1
}
#[test]
fn test_nullability_leaves() {
assert!(empty(&Rule::blank()));
assert!(!empty(&Rule::string("a")));
assert!(!empty(&Rule::pattern("a*")));
assert!(!empty(&Rule::symbol("a")));
assert!(!empty(&Rule::token(Rule::blank())));
}
#[test]
fn test_nullability_combinators() {
assert!(empty(&Rule::seq([])));
assert!(!empty(&Rule::choice([])));
assert!(empty(&Rule::repeat(Rule::string("a"))));
assert!(!empty(&Rule::repeat1(Rule::string("a"))));
assert!(empty(&Rule::repeat1(Rule::blank())));
assert!(empty(&Rule::optional(Rule::string("a"))));
assert!(empty(&Rule::seq([
Rule::blank(),
Rule::optional(Rule::string("a"))
])));
assert!(!empty(&Rule::seq([Rule::blank(), Rule::string("a")])));
assert!(!empty(&Rule::seq([Rule::string("a"), Rule::blank()])));
assert!(empty(&Rule::choice([Rule::string("a"), Rule::blank()])));
assert!(!empty(&Rule::choice([
Rule::string("a"),
Rule::symbol("b")
])));
assert!(empty(&Rule::field(
"f",
Rule::prec(1, Rule::repeat(Rule::string("a")))
)));
assert!(!empty(&Rule::alias(Rule::string("a"), "b")));
}
#[test]
fn test_nullability_finds_empty_repeats_anywhere_outside_tokens() {
assert!(!empty_repeat(&Rule::repeat(Rule::string("a"))));
assert!(empty_repeat(&Rule::repeat(Rule::optional(Rule::string(
"a"
)))));
assert!(empty_repeat(&Rule::repeat1(Rule::blank())));
assert!(empty_repeat(&Rule::repeat1(Rule::repeat(Rule::string(
"a"
)))));
let nested = Rule::seq([
Rule::string("x"),
Rule::choice([
Rule::symbol("y"),
Rule::repeat(Rule::optional(Rule::symbol("z"))),
]),
]);
assert!(!empty(&nested));
assert!(empty_repeat(&nested));
assert!(!empty_repeat(&Rule::token(Rule::repeat(Rule::optional(
Rule::string("a")
)))));
}
#[test]
fn test_nullability_deep_chain_is_iterative() {
let mut rule = Rule::blank();
for _ in 0..100_000 {
rule = Rule::seq([Rule::field("f", rule)]);
}
assert!(empty(&rule));
}
#[test]
fn test_identifier_rules() {
for ok in ["a", "_", "_a1", "Snake_Case9", "class"] {
assert_eq!(identifier(ok), Ok(()), "{ok}");
}
for bad in ["", "1a", "a-b", "a b", "é", "a.b", "$a"] {
assert!(identifier(bad).is_err(), "{bad}");
}
}
#[test]
fn test_index_resolves_rules_before_externals() {
let g = Grammar::new("g")
.rule("b", Rule::string("b"))
.rule("a", Rule::string("a"))
.external("a")
.external("z");
let index = Index::new(&g);
assert_eq!(index.get("a"), Some(Def::Rule(1)));
assert_eq!(index.get("b"), Some(Def::Rule(0)));
assert_eq!(index.get("z"), Some(Def::External));
assert_eq!(index.get("c"), None);
assert_eq!(index.duplicate(), None);
}
#[test]
fn test_duplicate_reports_earliest_second_definition() {
let g = Grammar::new("g")
.rule("s", Rule::string("s"))
.rule("z", Rule::string("1"))
.rule("a", Rule::string("1"))
.rule("z", Rule::string("2"))
.rule("a", Rule::string("2"));
assert_eq!(Index::new(&g).duplicate(), Some("z"));
}
#[test]
fn test_reach_follows_references_and_extras() {
let g = Grammar::new("g")
.extra(Rule::symbol("note"))
.rule("s", Rule::repeat(Rule::symbol("a")))
.rule("a", Rule::string("a"))
.rule("orphan", Rule::symbol("a"))
.rule("note", Rule::seq([Rule::string("#"), Rule::symbol("text")]))
.rule("text", Rule::pattern("[a-z]+"));
let index = Index::new(&g);
let graph = load(&g, &index, &mut Checker::default());
assert!(graph.is_ok());
let Ok(graph) = graph else { return };
let reach = reach(&g, &graph);
assert_eq!(reach.reachable, [true, true, false, true, true]);
assert_eq!(reach.used, [false, true, false, true, true]);
}
#[test]
fn test_node_counts_expand_hidden_rules() {
let g = Grammar::new("g")
.rule("s", Rule::blank())
.rule(
"_one",
Rule::choice([Rule::symbol("a"), Rule::symbol("_nested")]),
)
.rule("_nested", Rule::symbol("a"))
.rule("_two", Rule::seq([Rule::symbol("a"), Rule::string(";")]))
.rule(
"_list",
Rule::seq([Rule::symbol("a"), Rule::optional(Rule::symbol("_list"))]),
)
.rule("a", Rule::string("a"));
let index = Index::new(&g);
let counts = NodeCounts::new(&g, &index);
let most = |name: &str| match index.get(name) {
Some(Def::Rule(i)) => counts.most(&g.rules[i].1),
_ => u8::MAX,
};
assert_eq!(most("s"), 0);
assert_eq!(most("_one"), 1);
assert_eq!(most("_two"), 2);
assert_eq!(most("_list"), 2);
assert_eq!(counts.most(&Rule::repeat(Rule::symbol("a"))), 2);
assert_eq!(counts.most(&Rule::repeat(Rule::blank())), 2);
assert_eq!(counts.most(&Rule::alias(Rule::symbol("_two"), "x")), 1);
}
}