#![allow(clippy::result_unit_err)]
use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
use dsl_kit_core::{NodeId, Suggester};
use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
use std::collections::{BTreeSet, HashMap};
#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
pub enum Peg {
Rule {
id: NodeId,
name: String,
body: Box<Peg>,
},
Seq {
id: NodeId,
items: Vec<Peg>,
},
Choice {
id: NodeId,
alts: Vec<Peg>,
},
Repeat {
id: NodeId,
body: Box<Peg>,
min: u32,
max: Option<u32>,
},
RuleRef {
id: NodeId,
name: String,
},
Token {
id: NodeId,
pat: String,
},
Node {
id: NodeId,
variant: String,
body: Box<Peg>,
},
Field {
id: NodeId,
name: String,
body: Box<Peg>,
},
KeyedEntry {
id: NodeId,
slot: String,
key: Box<Peg>,
value: Box<Peg>,
},
}
#[derive(Debug, Clone)]
pub struct Grammar {
pub rules: Vec<Peg>,
pub start: String,
}
impl Grammar {
pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
Self {
rules,
start: start.into(),
}
}
pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
for r in &self.rules {
if let Peg::Rule { name, .. } = r {
rules_by_name.insert(name.as_str(), r);
}
}
let start_rule = rules_by_name
.get(self.start.as_str())
.copied()
.ok_or_else(|| {
let names: Vec<&str> = rules_by_name.keys().copied().collect();
let base = format!("start rule `{}` is not defined in the grammar", self.start);
let msg = match crate::BuiltinLevenshteinSuggester
.enrich_unknown(self.start.as_str(), &names)
{
Some(hint) => format!("{base} ({hint})"),
None => base,
};
BuildError::single(Diagnostic::error(codes::UNKNOWN_RULE, msg))
})?;
let mut interp = Interpreter::new(input, rules_by_name);
interp.skip_ws();
interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
match interp.run_peg(start_rule) {
Ok(()) => {}
Err(()) => {
if let Some(fatal) = interp.fatal_error.take() {
return Err(BuildError::single(fatal));
}
return Err(BuildError::single(interp.expected_diagnostic()));
}
}
interp.skip_ws();
if interp.pos != input.len() {
let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
{
interp.expected_diagnostic()
} else {
Diagnostic::error(
codes::UNEXPECTED,
format!("unexpected trailing input at byte {}", interp.pos),
)
.with_span(Some(Span::new(interp.pos, input.len())))
};
return Err(BuildError::single(diag));
}
let top = match interp.sink_stack.pop() {
Some(ActiveSink::Top(t)) => t,
_ => unreachable!("top sink must be present"),
};
let tree = top.tree.ok_or_else(|| {
BuildError::single(Diagnostic::error(
codes::NO_TOP_TREE,
format!(
"parse succeeded but produced no top-level `Node`; \
start rule `{}` must reach exactly one `Peg::Node`",
self.start
),
))
})?;
crate::allow::collapse(tree)
}
}
pub mod codes {
pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
}
#[derive(Debug, Clone)]
enum Production {
#[allow(dead_code)] Text(String, Span),
Tree(ParseTree),
}
#[derive(Debug, Default, Clone)]
struct FieldSink {
productions: Vec<Production>,
}
#[derive(Debug, Default, Clone)]
struct NodeSink {
fields: Vec<(String, RawValue)>,
children: Vec<(String, Vec<ParseTree>)>,
keyed_children: Vec<(String, Vec<(String, ParseTree)>)>,
}
#[derive(Debug, Default, Clone)]
struct TopSink {
tree: Option<ParseTree>,
}
#[derive(Debug, Clone)]
enum ActiveSink {
Top(TopSink),
Node(NodeSink),
Field(FieldSink),
}
struct Interpreter<'g, 'i> {
input: &'i str,
pos: usize,
rules_by_name: HashMap<&'g str, &'g Peg>,
sink_stack: Vec<ActiveSink>,
farthest_pos: usize,
farthest_expected: BTreeSet<String>,
call_stack: Vec<(&'g str, usize)>,
fatal_error: Option<Diagnostic>,
}
impl<'g, 'i> Interpreter<'g, 'i> {
fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
Self {
input,
pos: 0,
rules_by_name,
sink_stack: Vec::new(),
farthest_pos: 0,
farthest_expected: BTreeSet::new(),
call_stack: Vec::new(),
fatal_error: None,
}
}
fn top_sink_snapshot(&self) -> ActiveSink {
self.sink_stack
.last()
.cloned()
.expect("sink stack has at least the top-level entry during parse")
}
fn restore_top_sink(&mut self, snap: ActiveSink) {
let last = self
.sink_stack
.last_mut()
.expect("sink stack has at least the top-level entry during parse");
*last = snap;
}
fn contribute_text(&mut self, text: String, span: Span) {
match self.sink_stack.last_mut() {
Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
_ => {
}
}
}
fn contribute_tree(&mut self, tree: ParseTree) {
match self.sink_stack.last_mut() {
Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
Some(ActiveSink::Node(_)) => {
}
Some(ActiveSink::Top(t)) => {
t.tree = Some(tree);
}
None => unreachable!("sink stack must not be empty during parse"),
}
}
fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
if productions.is_empty() {
return;
}
let all_text = productions
.iter()
.all(|p| matches!(p, Production::Text(..)));
let all_tree = productions
.iter()
.all(|p| matches!(p, Production::Tree(..)));
let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
return;
};
if all_text {
let joined: String = productions
.iter()
.filter_map(|p| match p {
Production::Text(t, _) => Some(t.as_str()),
_ => None,
})
.collect();
node_sink
.fields
.push((name.to_string(), RawValue::Text(joined)));
return;
}
if all_tree {
let trees: Vec<ParseTree> = productions
.into_iter()
.filter_map(|p| match p {
Production::Tree(t) => Some(t),
_ => None,
})
.collect();
if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
slot.1.extend(trees);
} else {
node_sink.children.push((name.to_string(), trees));
}
return;
}
let trees: Vec<ParseTree> = productions
.into_iter()
.filter_map(|p| match p {
Production::Tree(t) => Some(t),
_ => None,
})
.collect();
if trees.is_empty() {
return;
}
if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
slot.1.extend(trees);
} else {
node_sink.children.push((name.to_string(), trees));
}
}
fn expected(&mut self, what: impl Into<String>) {
if self.pos > self.farthest_pos {
self.farthest_pos = self.pos;
self.farthest_expected.clear();
self.farthest_expected.insert(what.into());
} else if self.pos == self.farthest_pos {
self.farthest_expected.insert(what.into());
}
}
fn expected_diagnostic(&self) -> Diagnostic {
let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
let expected_msg = if expected.is_empty() {
"<unknown>".to_string()
} else {
expected
.iter()
.map(|e| format!("`{e}`"))
.collect::<Vec<_>>()
.join(" | ")
};
let end = self.input.len().min(self.farthest_pos + 1);
let got_msg = if self.farthest_pos >= self.input.len() {
"end of input".to_string()
} else {
let bytes = self.input.as_bytes();
let snip_end = self.input.len().min(self.farthest_pos + 8);
let snip =
std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
format!("`{}`", snip)
};
Diagnostic::error(
codes::UNEXPECTED,
format!(
"expected {expected_msg} at byte {}, got {got_msg}",
self.farthest_pos
),
)
.with_span(Some(Span::new(self.farthest_pos, end)))
}
fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
match peg {
Peg::Rule { body, .. } => self.run_peg(body),
Peg::Seq { items, .. } => {
for item in items {
self.run_peg(item)?;
}
Ok(())
}
Peg::Choice { alts, .. } => self.run_choice(alts),
Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
Peg::RuleRef { name, .. } => self.run_rule_ref(name),
Peg::Token { pat, .. } => self.match_token(pat),
Peg::Node { variant, body, .. } => self.run_node(variant, body),
Peg::Field { name, body, .. } => self.run_field(name, body),
Peg::KeyedEntry {
slot, key, value, ..
} => self.run_keyed_entry(slot, key, value),
}
}
fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
let start_pos = self.pos;
let saved = self.top_sink_snapshot();
for alt in alts {
self.pos = start_pos;
self.restore_top_sink(saved.clone());
if self.fatal_error.is_some() {
return Err(());
}
if self.run_peg(alt).is_ok() {
return Ok(());
}
if self.fatal_error.is_some() {
return Err(());
}
}
self.pos = start_pos;
self.restore_top_sink(saved);
Err(())
}
fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
let mut count: u32 = 0;
loop {
if let Some(mx) = max
&& count >= mx
{
break;
}
let saved_pos = self.pos;
let saved_sink = self.top_sink_snapshot();
match self.run_peg(body) {
Ok(()) => {
if self.pos == saved_pos {
if count < min {
self.fatal_error = Some(
Diagnostic::error(
codes::NULLABLE_REPEAT,
"repeat body succeeded without consuming input".to_string(),
)
.with_span(Some(Span::new(saved_pos, saved_pos))),
);
return Err(());
}
break;
}
count += 1;
}
Err(()) => {
if self.fatal_error.is_some() {
return Err(());
}
self.pos = saved_pos;
self.restore_top_sink(saved_sink);
break;
}
}
}
if count < min { Err(()) } else { Ok(()) }
}
fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
let Some(&rule) = self.rules_by_name.get(name) else {
let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
let base = format!("reference to undefined rule `{name}`");
let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
Some(hint) => format!("{base} ({hint})"),
None => base,
};
self.fatal_error = Some(
Diagnostic::error(codes::UNKNOWN_RULE, msg)
.with_span(Some(Span::new(self.pos, self.pos))),
);
return Err(());
};
let rule_name: &'g str = self
.rules_by_name
.keys()
.copied()
.find(|k| *k == name)
.expect("just found");
if self
.call_stack
.iter()
.any(|(n, p)| *n == rule_name && *p == self.pos)
{
self.fatal_error = Some(
Diagnostic::error(
codes::LEFT_RECURSION,
format!(
"left recursion detected: rule `{name}` re-entered at byte {}",
self.pos
),
)
.with_span(Some(Span::new(self.pos, self.pos))),
);
return Err(());
}
self.call_stack.push((rule_name, self.pos));
let r = self.run_peg(rule);
self.call_stack.pop();
r
}
fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
let start_pos = self.pos;
self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
let body_result = self.run_peg(body);
let node_sink = match self.sink_stack.pop() {
Some(ActiveSink::Node(s)) => s,
_ => unreachable!("balanced push/pop of NodeSink"),
};
body_result?;
let end_pos = self.pos;
let mut keyed_children = node_sink.keyed_children;
for (_, entries) in &mut keyed_children {
entries.sort_by(|(a, _), (b, _)| a.cmp(b));
}
let tree = ParseTree {
variant: variant.to_string(),
fields: node_sink.fields,
children: node_sink.children,
keyed_children,
allows: Vec::new(),
span: Some(Span::new(start_pos, end_pos)),
};
self.contribute_tree(tree);
Ok(())
}
fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
self.sink_stack
.push(ActiveSink::Field(FieldSink::default()));
let body_result = self.run_peg(body);
let field_sink = match self.sink_stack.pop() {
Some(ActiveSink::Field(s)) => s,
_ => unreachable!("balanced push/pop of FieldSink"),
};
body_result?;
self.contribute_field(name, field_sink.productions);
Ok(())
}
fn run_keyed_entry(&mut self, slot: &str, key: &'g Peg, value: &'g Peg) -> Result<(), ()> {
let key_text = {
self.sink_stack
.push(ActiveSink::Field(FieldSink::default()));
let result = self.run_peg(key);
let sink = match self.sink_stack.pop() {
Some(ActiveSink::Field(s)) => s,
_ => unreachable!("balanced push/pop of FieldSink"),
};
result?;
if sink.productions.is_empty() {
self.expected("a text production for the keyed-entry key");
return Err(());
}
let mut text = String::new();
for production in &sink.productions {
match production {
Production::Text(t, _) => text.push_str(t),
Production::Tree(_) => {
self.expected("a text production for the keyed-entry key");
return Err(());
}
}
}
text
};
self.sink_stack
.push(ActiveSink::Field(FieldSink::default()));
let value_result = self.run_peg(value);
let value_sink = match self.sink_stack.pop() {
Some(ActiveSink::Field(s)) => s,
_ => unreachable!("balanced push/pop of FieldSink"),
};
value_result?;
let mut trees = value_sink.productions.into_iter().filter_map(|p| match p {
Production::Tree(t) => Some(t),
Production::Text(..) => None,
});
let Some(tree) = trees.next() else {
self.expected("a subtree production for the keyed-entry value");
return Err(());
};
if trees.next().is_some() {
self.expected("exactly one subtree for the keyed-entry value");
return Err(());
}
let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
return Ok(());
};
if let Some(existing) = node_sink.keyed_children.iter_mut().find(|(n, _)| n == slot) {
existing.1.push((key_text, tree));
} else {
node_sink
.keyed_children
.push((slot.to_string(), vec![(key_text, tree)]));
}
Ok(())
}
fn match_token(&mut self, pat: &str) -> Result<(), ()> {
if pat != "%ws" {
self.skip_ws();
}
let start = self.pos;
if pat == "%str" {
return match self.match_str() {
Some(decoded) => {
let end = self.pos;
self.contribute_text(decoded, Span::new(start, end));
Ok(())
}
None => {
self.expected(pat);
self.pos = start;
Err(())
}
};
}
if pat == "%str_raw" {
return match self.match_str() {
Some(_) => {
let end = self.pos;
let text = self.input[start..end].to_string();
self.contribute_text(text, Span::new(start, end));
Ok(())
}
None => {
self.expected(pat);
self.pos = start;
Err(())
}
};
}
let ok = if pat == "%ident" {
self.match_ident()
} else if pat == "%int" {
self.match_int()
} else if pat == "%ws" {
self.match_ws_required()
} else if let Some(word) = pat.strip_prefix("%kw:") {
self.match_keyword(word)
} else {
self.match_literal(pat)
};
if ok {
let end = self.pos;
let text = self.input[start..end].to_string();
self.contribute_text(text, Span::new(start, end));
Ok(())
} else {
self.expected(pat);
self.pos = start;
Err(())
}
}
fn skip_ws(&mut self) {
let bytes = self.input.as_bytes();
while let Some(&c) = bytes.get(self.pos) {
if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
self.pos += 1;
} else {
break;
}
}
}
fn match_ident(&mut self) -> bool {
let bytes = self.input.as_bytes();
match bytes.get(self.pos) {
Some(&c) if is_ident_start(c) => self.pos += 1,
_ => return false,
}
while let Some(&c) = bytes.get(self.pos) {
if is_ident_cont(c) {
self.pos += 1;
} else {
break;
}
}
true
}
fn match_int(&mut self) -> bool {
let bytes = self.input.as_bytes();
let mut p = self.pos;
if bytes.get(p) == Some(&b'-') {
p += 1;
}
let digit_start = p;
while let Some(&c) = bytes.get(p) {
if c.is_ascii_digit() {
p += 1;
} else {
break;
}
}
if p > digit_start {
self.pos = p;
true
} else {
false
}
}
fn match_str(&mut self) -> Option<String> {
let rest = &self.input[self.pos..];
let mut chars = rest.char_indices();
match chars.next() {
Some((_, '"')) => {}
_ => return None,
}
let mut out = String::new();
while let Some((i, c)) = chars.next() {
match c {
'"' => {
self.pos += i + 1;
return Some(out);
}
'\\' => match chars.next() {
Some((_, '"')) => out.push('"'),
Some((_, '\\')) => out.push('\\'),
Some((_, 'n')) => out.push('\n'),
Some((_, 't')) => out.push('\t'),
Some((_, 'r')) => out.push('\r'),
_ => return None,
},
other => out.push(other),
}
}
None
}
fn match_ws_required(&mut self) -> bool {
let start = self.pos;
let bytes = self.input.as_bytes();
while let Some(&c) = bytes.get(self.pos) {
if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
self.pos += 1;
} else {
break;
}
}
self.pos > start
}
fn match_literal(&mut self, s: &str) -> bool {
let bytes = self.input.as_bytes();
let end = self.pos + s.len();
if end > bytes.len() {
return false;
}
if &bytes[self.pos..end] != s.as_bytes() {
return false;
}
self.pos = end;
true
}
fn match_keyword(&mut self, word: &str) -> bool {
let saved = self.pos;
if !self.match_literal(word) {
return false;
}
if let Some(&next) = self.input.as_bytes().get(self.pos)
&& is_ident_cont(next)
{
self.pos = saved;
return false;
}
true
}
}
fn is_ident_start(c: u8) -> bool {
c.is_ascii_alphabetic() || c == b'_'
}
fn is_ident_cont(c: u8) -> bool {
c.is_ascii_alphanumeric() || c == b'_'
}
use dsl_kit_core::IdGen;
pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
Peg::Rule {
id: ids.node(),
name: name.into(),
body: Box::new(body),
}
}
pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
Peg::Seq {
id: ids.node(),
items,
}
}
pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
Peg::Choice {
id: ids.node(),
alts,
}
}
pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
Peg::Repeat {
id: ids.node(),
body: Box::new(body),
min,
max,
}
}
pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
Peg::RuleRef {
id: ids.node(),
name: name.into(),
}
}
pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
Peg::Token {
id: ids.node(),
pat: pat.into(),
}
}
pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
Peg::Node {
id: ids.node(),
variant: variant.into(),
body: Box::new(body),
}
}
pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
Peg::Field {
id: ids.node(),
name: name.into(),
body: Box::new(body),
}
}
pub fn keyed_entry(ids: &IdGen, slot: impl Into<String>, key: Peg, value: Peg) -> Peg {
Peg::KeyedEntry {
id: ids.node(),
slot: slot.into(),
key: Box::new(key),
value: Box::new(value),
}
}
#[cfg(test)]
mod tests {
use super::*;
use dsl_kit_core::IdGen;
use dsl_kit_schema::DslSchema;
#[test]
fn peg_schema_lists_all_variants() {
let s = Peg::schema();
assert_eq!(s.name, "Peg");
let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
assert_eq!(
names,
vec![
"Rule",
"Seq",
"Choice",
"Repeat",
"RuleRef",
"Token",
"Node",
"Field",
"KeyedEntry"
]
);
let keyed = s.variant("KeyedEntry").unwrap();
let keyed_children: Vec<&str> = keyed.children.iter().map(|c| c.name.as_str()).collect();
assert_eq!(keyed_children, vec!["key", "value"]);
let keyed_fields: Vec<&str> = keyed.fields.iter().map(|f| f.name.as_str()).collect();
assert_eq!(keyed_fields, vec!["slot"]);
let repeat = s.variant("Repeat").unwrap();
assert_eq!(repeat.children.len(), 1);
assert_eq!(repeat.children[0].name, "body");
let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
assert!(field_names.contains(&"min"));
assert!(field_names.contains(&"max"));
}
fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
g.parse(input)
}
fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
Grammar::new(vec![rule(ids, start, body)], start)
}
fn keyed_grammar(ids: &IdGen, key: Peg, value: Peg) -> Grammar {
let entry = keyed_entry(ids, "entries", key, value);
one_rule_grammar(
ids,
"start",
node(
ids,
"Env",
seq(
ids,
vec![
token(ids, "{"),
repeat(
ids,
seq(ids, vec![entry, repeat(ids, token(ids, ","), 0, Some(1))]),
0,
None,
),
token(ids, "}"),
],
),
),
)
}
fn keyed_leaf_value(ids: &IdGen) -> Peg {
seq(
ids,
vec![
token(ids, ":"),
node(ids, "Lit", field(ids, "value", token(ids, "%int"))),
],
)
}
#[test]
fn keyed_entry_pairs_key_with_subtree_and_sorts() {
let ids = IdGen::new();
let g = keyed_grammar(&ids, token(&ids, "%ident"), keyed_leaf_value(&ids));
let tree = parse_one(&g, "{ b: 2, a: 1 }").unwrap();
let entries = tree.keyed_child_slot("entries").expect("slot bound");
let keys: Vec<&str> = entries.iter().map(|(k, _)| k.as_str()).collect();
assert_eq!(keys, ["a", "b"], "Node emission sorts by key");
let values: Vec<&RawValue> = entries
.iter()
.map(|(_, t)| t.field("value").expect("leaf payload"))
.collect();
assert_eq!(values[0], &RawValue::Text("1".into()));
assert_eq!(values[1], &RawValue::Text("2".into()));
}
#[test]
fn keyed_entry_accepts_an_empty_string_key() {
let ids = IdGen::new();
let g = keyed_grammar(&ids, token(&ids, "%str"), keyed_leaf_value(&ids));
let tree = parse_one(&g, r#"{ "": 1 }"#).unwrap();
let entries = tree.keyed_child_slot("entries").expect("slot bound");
assert_eq!(entries.len(), 1);
assert_eq!(entries[0].0, "");
}
#[test]
fn keyed_entry_rejects_a_key_half_that_produces_nothing() {
let ids = IdGen::new();
let g = keyed_grammar(
&ids,
repeat(&ids, token(&ids, "%ident"), 0, Some(1)),
keyed_leaf_value(&ids),
);
let err = parse_one(&g, "{ : 1 }").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
}
#[test]
fn keyed_entry_rejects_a_tree_where_the_key_belongs() {
let ids = IdGen::new();
let g = keyed_grammar(
&ids,
node(&ids, "Lit", field(&ids, "value", token(&ids, "%int"))),
keyed_leaf_value(&ids),
);
let err = parse_one(&g, "{ 1: 2 }").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
}
#[test]
fn keyed_entry_rejects_a_value_half_without_exactly_one_tree() {
let ids = IdGen::new();
let none = keyed_grammar(
&ids,
token(&ids, "%ident"),
seq(&ids, vec![token(&ids, ":"), token(&ids, "%int")]),
);
assert!(parse_one(&none, "{ a: 1 }").is_err());
let leaf = |ids: &IdGen| node(ids, "Lit", field(ids, "value", token(ids, "%int")));
let two = keyed_grammar(
&ids,
token(&ids, "%ident"),
seq(&ids, vec![token(&ids, ":"), leaf(&ids), leaf(&ids)]),
);
assert!(parse_one(&two, "{ a: 1 2 }").is_err());
}
#[test]
fn keyed_entry_survives_backtracking_without_leaking_entries() {
let ids = IdGen::new();
let entry_then_semi = seq(
&ids,
vec![
keyed_entry(
&ids,
"entries",
token(&ids, "%ident"),
keyed_leaf_value(&ids),
),
token(&ids, ";"),
],
);
let entry_then_end = seq(
&ids,
vec![
keyed_entry(
&ids,
"entries",
token(&ids, "%ident"),
keyed_leaf_value(&ids),
),
token(&ids, "}"),
],
);
let g = one_rule_grammar(
&ids,
"start",
node(
&ids,
"Env",
seq(
&ids,
vec![
token(&ids, "{"),
choice(&ids, vec![entry_then_semi, entry_then_end]),
],
),
),
);
let tree = parse_one(&g, "{ a: 1 }").unwrap();
let entries = tree.keyed_child_slot("entries").expect("slot bound");
assert_eq!(
entries.len(),
1,
"the failed alternative's entry must be rolled back, not kept: {entries:?}"
);
assert_eq!(entries[0].0, "a");
}
#[test]
fn keyed_entry_outside_a_node_drops_the_entry() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"start",
seq(
&ids,
vec![
keyed_entry(
&ids,
"entries",
token(&ids, "%ident"),
keyed_leaf_value(&ids),
),
node(&ids, "Env", token(&ids, "!")),
],
),
);
let tree = parse_one(&g, "a: 1 !").unwrap();
assert_eq!(tree.variant, "Env");
assert!(
tree.keyed_children.is_empty(),
"a keyed entry with no enclosing Node has nowhere to land: {:?}",
tree.keyed_children
);
}
#[test]
fn literal_token_and_wrap_node() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"start",
node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
);
let tree = parse_one(&g, "let").unwrap();
assert_eq!(tree.variant, "K");
assert_eq!(tree.fields.len(), 1);
assert_eq!(tree.fields[0].0, "kw");
match &tree.fields[0].1 {
RawValue::Text(t) => assert_eq!(t, "let"),
_ => panic!("expected text"),
}
}
#[test]
fn keyword_guard_blocks_prefix_match() {
let ids = IdGen::new();
let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
let err = parse_one(&g, "letme").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
assert!(parse_one(&g2, "let ").is_ok());
}
#[test]
fn plain_literal_has_no_word_boundary_guard() {
let ids = IdGen::new();
let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
let err = parse_one(&g, "ab").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
assert!(
err.diagnostics[0].message.contains("trailing"),
"{}",
err.diagnostics[0].message
);
}
#[test]
fn ident_and_int_classes() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"s",
node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
);
let t = parse_one(&g, "foo_bar1").unwrap();
assert_eq!(t.variant, "Var");
match &t.fields[0].1 {
RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
_ => panic!(),
}
let g2 = one_rule_grammar(
&ids,
"s",
node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
);
let t2 = parse_one(&g2, "-42").unwrap();
match &t2.fields[0].1 {
RawValue::Text(v) => assert_eq!(v, "-42"),
_ => panic!(),
}
}
#[test]
fn implicit_ws_skip_before_tokens_and_at_boundaries() {
let ids = IdGen::new();
let body = seq(
&ids,
vec![
field(&ids, "a", token(&ids, "%int")),
field(&ids, "b", token(&ids, "%int")),
],
);
let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
let t = parse_one(&g, " 3 7 ").unwrap();
assert_eq!(t.fields.len(), 2);
assert_eq!(t.fields[0].0, "a");
assert_eq!(t.fields[1].0, "b");
}
#[test]
fn choice_commits_on_first_match() {
let ids = IdGen::new();
let alt_a = node(&ids, "A", token(&ids, "a"));
let alt_ab = node(&ids, "B", token(&ids, "ab"));
let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
let err = parse_one(&g, "ab").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
assert!(
err.diagnostics[0].message.contains("byte 1"),
"{}",
err.diagnostics[0].message
);
}
#[test]
fn failed_alt_restores_position() {
let ids = IdGen::new();
let alt_abc = node(&ids, "L", token(&ids, "abc"));
let alt_a = node(&ids, "S", token(&ids, "a"));
let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
let err = parse_one(&g, "ab").unwrap_err();
assert!(
err.diagnostics[0].message.contains("byte 1"),
"{}",
err.diagnostics[0].message
);
}
#[test]
fn repeat_is_greedy_and_no_backtrack_into_completed() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"s",
node(
&ids,
"N",
seq(
&ids,
vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
),
),
);
let err = parse_one(&g, "aaa").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
}
#[test]
fn repeat_min_enforced() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"s",
node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
);
assert!(parse_one(&g, "a").is_err());
assert!(parse_one(&g, "aa").is_ok());
}
#[test]
fn farthest_failure_carries_position_and_expected_set() {
let ids = IdGen::new();
let g = one_rule_grammar(
&ids,
"s",
node(
&ids,
"N",
seq(
&ids,
vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
),
),
);
let err = parse_one(&g, "let x !").unwrap_err();
let msg = &err.diagnostics[0].message;
assert!(msg.contains("byte 6"), "{msg}");
assert!(msg.contains("`=`"), "{msg}");
}
#[test]
fn left_recursion_is_detected_at_runtime() {
let ids = IdGen::new();
let r = rule(
&ids,
"r",
seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
);
let g = Grammar::new(vec![r], "r");
let err = g.parse("aaa").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
}
#[test]
fn unknown_rule_ref_is_diagnosed() {
let ids = IdGen::new();
let r = rule(&ids, "start", rule_ref(&ids, "missing"));
let g = Grammar::new(vec![r], "start");
let err = g.parse("").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
}
#[test]
fn unknown_rule_ref_suggests_declared_rule() {
let ids = IdGen::new();
let start = rule(&ids, "start", rule_ref(&ids, "helo"));
let target = rule(&ids, "hello", token(&ids, "hi"));
let g = Grammar::new(vec![start, target], "start");
let err = g.parse("hi").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
assert!(
err.diagnostics[0].message.contains("did you mean")
&& err.diagnostics[0].message.contains("hello"),
"expected hint, got: {}",
err.diagnostics[0].message
);
}
#[test]
fn unknown_start_rule_is_diagnosed() {
let ids = IdGen::new();
let r = rule(&ids, "other", token(&ids, "x"));
let g = Grammar::new(vec![r], "start");
let err = g.parse("x").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
}
#[test]
fn unknown_start_rule_suggests_declared_rule() {
let ids = IdGen::new();
let r = rule(&ids, "start", token(&ids, "x"));
let g = Grammar::new(vec![r], "strat");
let err = g.parse("x").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
assert!(
err.diagnostics[0].message.contains("did you mean")
&& err.diagnostics[0].message.contains("start"),
"expected hint, got: {}",
err.diagnostics[0].message
);
}
#[test]
fn nullable_repeat_body_below_min_is_rejected() {
let ids = IdGen::new();
let empty_body = seq(&ids, vec![]);
let g = one_rule_grammar(
&ids,
"s",
node(&ids, "N", repeat(&ids, empty_body, 1, None)),
);
let err = g.parse("").unwrap_err();
assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
}
}