use std::path::{Path, PathBuf};
use dbt_antlr_runtime::analysis::{BOUNDARY_TAINT, EOF, FOREIGN_LINEAGE_TAINT};
use crate::grammar::compiler::compile;
use crate::grammar::diagnostic::Severity;
use crate::grammar::loader::LoadOptions;
use crate::optimization::AtnFallback;
use super::builder::{PARTIAL_DEPTH_CAP, STATIC_ONLY_DEPTH_CAP};
use super::cost::{AttemptKind, AttemptOutcome};
use super::loop_block::LoopBlock;
use super::table::{StaticDfaState, StaticDfaTable};
use super::{
BudgetCutoff, BudgetLimits, CONFLICT_ESCAPE, DecisionKind, DecisionOutcome,
DecisionTableBuilder, NoTableReason, ParserDfaBudgets,
};
fn grammars_dir() -> PathBuf {
Path::new(env!("CARGO_MANIFEST_DIR"))
.parent()
.expect("crate directory")
.join("dbt-antlr-runtime")
.join("grammars")
}
fn fixture(name: &str) -> PathBuf {
Path::new(env!("CARGO_MANIFEST_DIR"))
.join("tests")
.join("codegen-direct")
.join("fixtures")
.join(name)
}
fn builder(parser: &crate::grammar::atn::CompiledParser) -> DecisionTableBuilder {
let ll1 = crate::optimization::static_parser_dfa::ll1_disjointness(parser);
DecisionTableBuilder::new(parser.atn, ll1).with_descent_rules(
crate::optimization::static_parser_dfa::descent_rules(parser),
)
}
fn outcomes(path: &Path) -> Vec<DecisionOutcome> {
outcomes_with(path, AtnFallback::Allowed)
}
fn outcomes_with(path: &Path, atn_fallback: AtnFallback) -> Vec<DecisionOutcome> {
outcomes_of(path, |builder| builder.with_atn_fallback(atn_fallback))
}
fn widened_outcomes_with(path: &Path, atn_fallback: AtnFallback) -> Vec<DecisionOutcome> {
outcomes_of(path, |builder| {
builder
.with_atn_fallback(atn_fallback)
.with_widening()
.with_max_k(64)
})
}
fn outcomes_of(
path: &Path,
setup: impl Fn(DecisionTableBuilder) -> DecisionTableBuilder,
) -> Vec<DecisionOutcome> {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let mut results = Vec::new();
for root in &compilation.roots {
let Some(parser_id) = root.parser else {
continue;
};
let parser = compilation.parser(parser_id).expect("parser artifact");
results.extend(setup(builder(parser)).build_all());
}
results
}
fn rule_names(path: &Path, results: &[DecisionOutcome]) -> Vec<String> {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let Some(root) = compilation.roots.first() else {
return Vec::new();
};
let Some(parser) = compilation.parser(root.parser.expect("parser root")) else {
return Vec::new();
};
results
.iter()
.map(|result| parser.semantic.recognizer.rule_names[result.rule_index].clone())
.collect()
}
fn kinds(path: &Path) -> Vec<DecisionKind> {
outcomes(path)
.into_iter()
.map(|result| result.kind)
.collect()
}
#[test]
fn golden_corpus_decisions_get_their_kinds() {
let cases: [(&str, &[DecisionKind]); 7] = [
("CSV.g4", &[DecisionKind::Ll1; 4]),
(
"Labels.g4",
&[
DecisionKind::Ll1,
DecisionKind::Ll1,
DecisionKind::Static,
DecisionKind::Static,
],
),
("SimpleLR.g4", &[DecisionKind::Static]),
("VisitorBasic.g4", &[]),
(
"VisitorCalc.g4",
&[DecisionKind::Static, DecisionKind::Static],
),
(
"ReferenceToATN.g4",
&[DecisionKind::Hybrid, DecisionKind::Ll1],
),
(
"Perf.g4",
&[
DecisionKind::Static,
DecisionKind::Ll1,
DecisionKind::Static,
DecisionKind::Hybrid,
],
),
];
for (file, expected) in cases {
let path = grammars_dir().join(file);
assert_eq!(kinds(&path), expected, "{file}");
}
let shapes = fixture("parser-shapes").join("ParserShapes.g4");
assert_eq!(
kinds(&shapes),
[
DecisionKind::Ll1,
DecisionKind::Hybrid,
DecisionKind::Ll1,
DecisionKind::Adaptive,
]
);
let results = outcomes(&shapes);
let rules = rule_names(&shapes, &results);
assert_eq!(rules, ["optional", "plus", "star", "nongreedy"]);
}
#[test]
fn ll1_decisions_need_no_table() {
let results = outcomes(&grammars_dir().join("CSV.g4"));
for result in &results {
assert_eq!(result.kind, DecisionKind::Ll1);
assert_eq!(result.k, 1);
assert!(result.table.is_none());
assert!(result.is_fully_static());
assert_eq!(result.fallback_text(), "0");
}
}
#[test]
fn hybrid_tables_escape_at_the_conflict_state() {
let results = outcomes(&grammars_dir().join("ReferenceToATN.g4"));
let decision = &results[0];
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert_eq!(decision.k, 2);
assert_eq!(decision.escapes, 1);
assert!(!decision.is_fully_static());
assert_eq!(decision.fallback_text(), "1");
let table = decision.table.as_ref().expect("hybrid table is kept");
assert_eq!(table.states.len(), 5);
assert_eq!(table.states[0].edges.len(), 3);
assert_eq!(decision.conflict_witness.as_deref(), Some(&[2, -1][..]));
}
#[test]
fn precedence_decisions_get_one_table_per_class() {
let results = outcomes(&grammars_dir().join("SimpleLR.g4"));
let decision = &results[0];
assert_eq!(decision.kind, DecisionKind::Static);
let precedence = decision.precedence.as_ref().expect("precedence tables");
assert_eq!(precedence.cutoffs, [2]);
assert_eq!(precedence.tables.len(), 2);
assert_eq!(precedence.adaptive_classes, 0);
assert!(precedence.tables.iter().all(Option::is_some));
assert!(decision.is_fully_static());
assert_eq!(decision.fallback_text(), "0");
}
#[test]
fn predicated_branches_escape_while_the_loop_stays_static() {
let shapes = fixture("parser-shapes").join("ParserShapes.g4");
let results = outcomes(&shapes);
let plus = &results[1];
assert_eq!(plus.kind, DecisionKind::Hybrid);
let table = plus.table.as_ref().expect("the loop keeps a hybrid table");
assert!(
table.states.iter().any(|state| state.predicated),
"the predicated branch escapes"
);
assert!(table.escapes() > 0, "the predicated branch escapes");
assert!(!plus.is_fully_static());
}
#[test]
fn non_greedy_decisions_are_flagged_without_a_table() {
let shapes = fixture("parser-shapes").join("ParserShapes.g4");
let results = outcomes(&shapes);
let nongreedy = &results[3];
assert_eq!(nongreedy.kind, DecisionKind::Adaptive);
assert_eq!(nongreedy.no_table, Some(NoTableReason::NonGreedy));
assert!(nongreedy.table.is_none());
assert!(!nongreedy.is_fully_static());
}
#[test]
fn table_builds_are_deterministic() {
for file in ["Labels.g4", "Perf.g4", "ReferenceToATN.g4", "SimpleLR.g4"] {
let path = grammars_dir().join(file);
let first = outcomes(&path);
let second = outcomes(&path);
assert_eq!(first.len(), second.len(), "{file}");
for (first, second) in first.iter().zip(&second) {
assert_eq!(first.kind, second.kind, "{file}");
assert_eq!(first.k, second.k, "{file}");
assert_eq!(first.num_dfa_states, second.num_dfa_states, "{file}");
assert_eq!(first.table, second.table, "{file}");
assert_eq!(first.precedence, second.precedence, "{file}");
}
}
}
#[test]
fn no_table_has_an_eof_self_loop() {
let grammars = [
"CSV.g4",
"Labels.g4",
"Perf.g4",
"ReferenceToATN.g4",
"SimpleLR.g4",
"VisitorBasic.g4",
"VisitorCalc.g4",
];
let mut tables = Vec::new();
for file in grammars {
for result in outcomes(&grammars_dir().join(file)) {
if let Some(table) = &result.table {
tables.push((file, result.decision, table.clone()));
}
if let Some(precedence) = &result.precedence {
for table in precedence.tables.iter().flatten() {
tables.push((file, result.decision, table.clone()));
}
}
}
}
assert!(!tables.is_empty(), "the corpus produces tables");
for (file, decision, table) in tables {
for (index, state) in table.states.iter().enumerate() {
for edge in &state.edges {
assert!(
!(edge.lo == -1 && edge.target == index),
"{file} decision {decision}: state {index} loops on EOF"
);
}
}
}
}
#[test]
fn fixture_corpus_builds_without_panicking() {
let fixtures = Path::new(env!("CARGO_MANIFEST_DIR"))
.join("tests")
.join("codegen-direct")
.join("fixtures");
let mut all = Vec::new();
collect_grammars(&fixtures, &mut all);
assert!(all.len() > 100, "fixture corpus found: {}", all.len());
all.sort();
let grammars = all
.into_iter()
.enumerate()
.filter(|(index, _)| index % 4 == 0)
.map(|(_, path)| path)
.collect::<Vec<_>>();
let mut built = 0_usize;
for path in grammars {
let Ok(compilation) = compile(LoadOptions {
roots: vec![path.clone()],
library_directories: Vec::new(),
}) else {
continue;
};
for root in &compilation.roots {
let Some(parser_id) = root.parser else {
continue;
};
let parser = compilation.parser(parser_id).expect("parser artifact");
let results = builder(parser).build_all();
for result in results {
built += 1;
for table in result.table.iter().chain(
result
.precedence
.iter()
.flat_map(|p| p.tables.iter().flatten()),
) {
assert!(
!table.states.is_empty(),
"{}: decision {} has an empty table",
path.display(),
result.decision
);
for state in &table.states {
for edge in &state.edges {
assert!(
edge.target < table.states.len(),
"{}: decision {} edge leaves the table",
path.display(),
result.decision
);
assert!(
edge.lo <= edge.hi,
"{}: empty edge interval",
path.display()
);
}
}
}
}
}
}
assert!(built > 10, "built {built} decisions");
}
fn collect_grammars(directory: &Path, out: &mut Vec<PathBuf>) {
let Ok(entries) = std::fs::read_dir(directory) else {
return;
};
for entry in entries.flatten() {
let path = entry.path();
if path.is_dir() {
collect_grammars(&path, out);
} else if path.extension().is_some_and(|extension| extension == "g4") {
out.push(path);
}
}
}
#[test]
fn whole_fixture_corpus_builds_under_a_small_budget() {
let fixtures = Path::new(env!("CARGO_MANIFEST_DIR"))
.join("tests")
.join("codegen-direct")
.join("fixtures");
let mut all = Vec::new();
collect_grammars(&fixtures, &mut all);
all.sort();
let grammars = all
.into_iter()
.enumerate()
.filter(|(index, _)| index % 4 == 0)
.map(|(_, path)| path)
.collect::<Vec<_>>();
let mut tables = 0_usize;
for path in grammars {
let Ok(compilation) = compile(LoadOptions {
roots: vec![path.clone()],
library_directories: Vec::new(),
}) else {
continue;
};
for root in &compilation.roots {
let Some(parser_id) = root.parser else {
continue;
};
let parser = compilation.parser(parser_id).expect("parser artifact");
let results = builder(parser).with_visit_budget(20_000).build_all();
for result in results {
for table in result.table.iter().chain(
result
.precedence
.iter()
.flat_map(|p| p.tables.iter().flatten()),
) {
tables += 1;
assert!(!table.states.is_empty(), "{}", path.display());
for state in &table.states {
for edge in &state.edges {
assert!(edge.target < table.states.len(), "{}", path.display());
}
}
}
}
}
}
assert!(tables > 0, "the corpus produces tables");
}
#[test]
fn exhausted_start_state_yields_no_table() {
let reference = outcomes_with_budget(&grammars_dir().join("ReferenceToATN.g4"), 1);
let decision = &reference[0];
assert_eq!(decision.kind, DecisionKind::Adaptive);
assert_eq!(
decision.no_table,
Some(NoTableReason::StartBudget(BudgetCutoff::Visits))
);
assert!(decision.table.is_none());
assert!(!decision.is_fully_static());
let precedence = outcomes_with_budget(&grammars_dir().join("SimpleLR.g4"), 1);
let decision = &precedence[0];
assert_eq!(decision.kind, DecisionKind::Adaptive);
let classes = decision.precedence.as_ref().expect("precedence classes");
assert_eq!(
decision.no_table,
Some(NoTableReason::PrecedenceClasses {
failed: classes.tables.len(),
total: classes.tables.len(),
first: Box::new(NoTableReason::StartBudget(BudgetCutoff::Visits)),
})
);
assert!(classes.tables.iter().all(Option::is_none));
assert!(!decision.is_fully_static());
}
fn parser_atn(path: &Path) -> &'static dbt_antlr_runtime::analysis::ATN {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let root = compilation.roots.first().expect("one root");
compilation
.parser(root.parser.expect("parser root"))
.expect("parser artifact")
.atn
}
fn precedence_decision(
atn: &dbt_antlr_runtime::analysis::ATN,
) -> dbt_antlr_runtime::analysis::ATNStateRef {
use dbt_antlr_runtime::analysis::{ATNStateType, RuleStartState};
atn.decision_to_state
.iter()
.copied()
.find(|state| {
state.state_type() == ATNStateType::StarLoopEntry
&& atn.rule_to_start_state[state.get_rule_index() as usize]
.try_as::<RuleStartState>()
.is_some_and(|start| start.is_left_recursive)
&& state.get_transitions().last().is_some_and(|transition| {
let loop_end = transition.get_target();
loop_end.state_type() == ATNStateType::LoopEnd
&& loop_end.has_epsilon_only_transitions()
&& loop_end.get_transitions().first().is_some_and(|epsilon| {
epsilon.get_target().state_type() == ATNStateType::RuleStop
})
})
})
.expect("a left-recursive rule has a precedence loop")
}
fn outcomes_with_budget(path: &Path, budget: u64) -> Vec<DecisionOutcome> {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let root = compilation.roots.first().expect("one root");
let parser = compilation
.parser(root.parser.expect("parser root"))
.expect("parser artifact");
builder(parser).with_visit_budget(budget).build_all()
}
fn build_tables(path: &Path) -> (Vec<DecisionOutcome>, super::super::StaticParserTables) {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let build = crate::optimization::StaticParserDfa::build(
compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact"),
&compilation.sources,
AtnFallback::Allowed,
false,
&ParserDfaBudgets::default(),
);
let results = outcomes(path);
(results, build.tables)
}
#[test]
fn table_image_loads_in_the_runtime() {
let (results, tables) = build_tables(&grammars_dir().join("ReferenceToATN.g4"));
assert!(tables.has_table(0), "decision 0 has a hybrid table");
assert!(tables.defers(0), "the hybrid table keeps an adaptive path");
let words = tables.words();
let decoded = load_image(&words);
assert_eq!(decoded.words(), words, "the image loads in place");
assert_eq!(
decoded.table(0, 0).expect("decoded table").num_states(),
results[0].num_dfa_states
);
}
#[test]
fn fully_static_decisions_never_defer() {
let (results, tables) = build_tables(&grammars_dir().join("parser/StaticDFA.g4"));
assert!(!results.is_empty());
for result in &results {
assert!(
result.is_fully_static(),
"decision {} of rule index {} should be fully static, got {:?}",
result.decision,
result.rule_index,
result.kind
);
if result.kind == DecisionKind::Ll1 {
continue;
}
assert!(tables.has_table(result.decision));
assert!(!tables.defers(result.decision));
}
}
#[test]
fn hybrid_frontier_escapes_carry_continuations() {
let (results, tables) = build_tables(&grammars_dir().join("parser/FuzzExpr.g4"));
let hybrid = results
.iter()
.filter(|result| result.kind == DecisionKind::Hybrid)
.max_by_key(|result| result.escapes)
.expect("FuzzExpr has a hybrid decision");
let words = tables.words();
let decoded = load_image(&words);
assert_eq!(decoded.words(), words, "the image loads in place");
let table = decoded
.table(hybrid.decision as i32, 0)
.expect("the hybrid decision has a table");
let continuations = (0..table.num_states() as i32)
.filter_map(|state| table.continuation(state))
.count();
assert!(
continuations > 0,
"decision {} has {} escapes, so its frontier must carry continuations",
hybrid.decision,
hybrid.escapes
);
}
#[test]
fn precedence_class_tables_are_deduplicated() {
let (results, tables) = build_tables(&grammars_dir().join("parser/LrDfa.g4"));
let precedence = results
.iter()
.find(|result| result.precedence.is_some())
.expect("LrDfa has a precedence decision");
let classes = precedence.precedence.as_ref().unwrap();
assert!(classes.tables.iter().flatten().count() > 0);
let words = tables.words();
let decoded = load_image(&words);
assert!(
decoded.is_precedence_dispatched(precedence.decision as i32),
"the precedence decision dispatches on its precedence"
);
let first = decoded.table(
precedence.decision as i32,
classes.cutoffs.last().copied().unwrap_or(0) + 1,
);
assert!(first.is_some(), "the highest class resolves to a table");
}
#[test]
fn table_build_is_deterministic() {
let path = grammars_dir().join("parser/FuzzExpr.g4");
let (_, first) = build_tables(&path);
let (_, second) = build_tables(&path);
assert_eq!(first.words(), second.words());
}
#[test]
fn emitted_tables_validate_against_the_packed_atn() {
use dbt_antlr_runtime::atn_packed_deserializer::PackedATNDeserializer;
use dbt_antlr_runtime::dfa::static_parser_dfa::StaticParserTables;
for grammar in [
"ReferenceToATN.g4",
"parser/StaticDFA.g4",
"parser/LrDfa.g4",
] {
let path = grammars_dir().join(grammar);
let compilation = compile(LoadOptions {
roots: vec![path.clone()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let parser = compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact");
let build = crate::optimization::StaticParserDfa::build(
parser,
&compilation.sources,
AtnFallback::Allowed,
false,
&ParserDfaBudgets::default(),
);
let packed = crate::grammar::atn::encode_packed_atn(parser.atn);
let atn = PackedATNDeserializer::new()
.deserialize(&packed)
.expect("the packed ATN deserializes");
let tables =
StaticParserTables::from_image(Box::leak(build.tables.words().into_boxed_slice()))
.expect("the emitted image loads");
assert!(!tables.is_empty(), "{grammar}: the unit has tables");
tables
.validate_for_atn(&atn)
.unwrap_or_else(|error| panic!("{grammar}: {error}"));
let mut extended = packed.clone();
extended.push(0);
extended[25] += 1;
assert!(
PackedATNDeserializer::new().deserialize(&extended).is_err(),
"{grammar}: words after the last packed section are rejected"
);
}
}
#[test]
fn operator_loop_covers_the_loop_positions_only() {
let atn = parser_atn(&grammars_dir().join("parser").join("LoopSubst.g4"));
let decision = precedence_decision(atn);
let block = LoopBlock::of(atn, decision);
let rule_index = decision.get_rule_index();
assert!(block.guards_are_simple(), "the arithmetic loop is simple");
assert!(
block.is_loop_consumption(decision, None, BOUNDARY_TAINT),
"the loop decision is part of the loop"
);
let rule_start = atn.rule_to_start_state[rule_index as usize];
assert!(!block.is_loop_consumption(rule_start, None, BOUNDARY_TAINT));
assert!(block.is_foreign_call(rule_start, None));
let operand_state = atn.make_state_ref(
atn.iter_states()
.find(|state| state.get_rule_index() != rule_index)
.expect("the grammar has another rule")
.get_state_number(),
);
assert!(!block.is_loop_consumption(operand_state, None, BOUNDARY_TAINT));
assert!(block.is_foreign_call(operand_state, None));
assert!(!block.is_foreign_call(decision, None));
assert!(!block.is_loop_consumption(decision, None, BOUNDARY_TAINT | FOREIGN_LINEAGE_TAINT));
assert!(!block.is_pending(decision));
}
#[test]
fn compound_guarded_alternatives_are_not_substitutable() {
let atn = parser_atn(&grammars_dir().join("parser").join("LoopVeto.g4"));
let decision = precedence_decision(atn);
let block = LoopBlock::of(atn, decision);
assert!(
!block.guards_are_simple(),
"`(',' send)* '>>' send` is not a simple guarded alternative"
);
let results = outcomes(&grammars_dir().join("parser").join("LoopVeto.g4"));
let result = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the loop decision");
assert_eq!(result.escapes, 2, "the vetoed conflict escapes");
assert!(!result.is_fully_static());
let table = &result
.precedence
.as_ref()
.expect("precedence tables")
.tables[0]
.as_ref()
.expect("the first class has a table");
assert!(
table
.states
.iter()
.any(|state| state.is_escape() && state.conflicts == [1, 2]),
"the escape is the iterate/exit conflict"
);
}
#[test]
fn simple_guarded_alternatives_need_no_escape() {
let results = outcomes(&grammars_dir().join("parser").join("LoopSubst.g4"));
let result = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the arithmetic loop decision");
assert_eq!(result.escapes, 0);
assert!(result.is_fully_static());
assert_eq!(result.fallback_text(), "0");
let classes = result.precedence.as_ref().expect("precedence tables");
assert_eq!(classes.adaptive_classes, 0);
assert!(classes.tables.iter().all(Option::is_some));
let tables: Vec<_> = classes.tables.iter().flatten().collect();
for table in &tables {
assert!(
table
.states
.iter()
.all(|state| !(state.is_escape() && state.conflicts == [1, 2])),
"no iterate/exit state escapes"
);
}
assert!(
tables
.iter()
.flat_map(|table| table.states.iter())
.any(|state| state.accept == 1 && state.conflicts == [1, 2]),
"the substitution resolves an iterate/exit conflict to iterate"
);
}
#[test]
fn foreign_consumption_guards_the_iterate_reading() {
let results = outcomes(&grammars_dir().join("parser").join("LoopFrontier.g4"));
let result = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the arithmetic loop decision");
assert_eq!(result.k, 4);
assert_eq!(result.num_dfa_states, 88);
assert_eq!(result.escapes, 3, "the frontier states escape");
assert_eq!(result.guarded_states(), 32);
assert!(!result.is_fully_static(), "a guard may defer");
let classes = result.precedence.as_ref().expect("precedence tables");
assert_eq!(classes.adaptive_classes, 0);
let states: Vec<_> = classes
.tables
.iter()
.flatten()
.flat_map(|table| table.states.iter())
.collect();
assert!(
states
.iter()
.all(|state| !(state.accept == 1 && state.conflicts == [1, 2])),
"no iterate/exit conflict resolves to iterate outright"
);
let guarded: Vec<_> = states
.iter()
.copied()
.filter(|state| state.is_guarded())
.collect();
assert_eq!(guarded.len(), 32);
let conflict_guards = guarded
.iter()
.filter(|state| state.conflicts == [1, 2])
.count();
let frontier_guards = guarded
.iter()
.filter(|state| state.conflicts.is_empty())
.count();
assert_eq!((conflict_guards, frontier_guards), (32, 0));
for state in guarded {
assert_eq!(state.guarded_alt, 1, "a guarded iterate takes alt 1");
}
let table = classes.tables[0].as_ref().expect("class 0 table");
assert!(!table.guard_danger().is_empty(), "the guard can trip");
let between = outcomes(&grammars_dir().join("parser").join("BetweenExpr.g4"));
let boolean_loop = &between[3];
assert_eq!(boolean_loop.kind, DecisionKind::Static);
assert_eq!(boolean_loop.escapes, 0);
assert_eq!(boolean_loop.guarded_states(), 2);
assert_eq!(boolean_loop.fallback_text(), "2g");
assert!(!boolean_loop.is_fully_static());
}
fn token_types(path: &Path, names: &[&str]) -> Vec<i32> {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let root = compilation.roots.first().expect("one root");
let parser = compilation
.parser(root.parser.expect("parser root"))
.expect("parser artifact");
let recognizer = &parser.semantic.recognizer;
names
.iter()
.map(|name| {
let position = |names: &[Option<String>]| {
names
.iter()
.position(|candidate| candidate.as_deref() == Some(*name))
};
position(&recognizer.literal_names)
.or_else(|| position(&recognizer.symbolic_names))
.unwrap_or_else(|| panic!("unknown token {name}")) as i32
})
.collect()
}
fn walk<'t>(table: &'t StaticDfaTable, tokens: &[i32]) -> Option<&'t StaticDfaState> {
let mut state = &table.states[0];
for token in tokens {
let edge = state
.edges
.iter()
.find(|edge| edge.lo <= *token && *token <= edge.hi)?;
state = &table.states[edge.target];
}
Some(state)
}
#[test]
fn tokens_that_the_loop_does_not_own_veto_the_substitution() {
let path = grammars_dir().join("parser").join("LoopSibling.g4");
let results = outcomes(&path);
let names = rule_names(&path, &results);
let types = token_types(&path, &["'-'", "'+'", "'pair'", "ID"]);
let (minus, plus, pair, id) = (types[0], types[1], types[2], types[3]);
for (rule, tokens) in [
("expr", vec![minus, minus, id]),
("term", vec![minus, pair, minus, id]),
("cond", vec![minus, id]),
("tail", vec![minus, id, minus, id]),
("prec", vec![plus, id, plus, id]),
] {
let (result, _) = results
.iter()
.zip(&names)
.find(|(result, name)| result.is_precedence_loop() && *name == rule)
.unwrap_or_else(|| panic!("the loop decision of {rule}"));
let ends: Vec<&StaticDfaState> = result
.precedence
.as_ref()
.expect("precedence tables")
.tables
.iter()
.flatten()
.filter_map(|table| walk(table, &tokens))
.collect();
assert!(
ends.iter()
.any(|state| state.is_escape() || state.is_guarded()),
"{rule}: the iterate/exit conflict defers"
);
assert!(
ends.iter().all(|state| state.accept != 1),
"{rule}: no class table iterates on the path"
);
}
}
#[test]
fn foreign_rooted_obligations_guard_the_iterate_reading() {
let path = grammars_dir().join("parser").join("LoopObligation.g4");
let results = outcomes(&path);
let result = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the loop decision of `p`");
assert_eq!(result.k, 4);
assert_eq!(result.num_dfa_states, 27);
assert_eq!(result.escapes, 0);
assert_eq!(result.guarded_states(), 10);
assert!(!result.is_fully_static());
assert_eq!(result.fallback_text(), "10g");
let classes = result.precedence.as_ref().expect("precedence tables");
assert_eq!(classes.adaptive_classes, 0);
let types = token_types(&path, &["'['", "':'", "'.'", "'prior'", "'trim'", "ID"]);
let (open, colon, dot, prior, trim, id) =
(types[0], types[1], types[2], types[3], types[4], types[5]);
for table in &classes.tables[..2] {
let table = table.as_ref().expect("hybrid class table");
assert_eq!(table.guard_danger(), [9, 15]);
assert_eq!(table.guard_pass, [40]);
let conflict = walk(table, &[dot, id]).expect("`.` ID edge");
assert!(conflict.is_guarded());
assert_eq!(conflict.guarded_alt, 1);
assert_eq!(conflict.conflicts, [1, 2]);
for tail in [open, prior, trim, id] {
let frontier = walk(table, &[open, id, colon, tail]).expect("frontier edge");
assert!(frontier.is_guarded());
assert_eq!(frontier.guarded_alt, 1);
assert!(frontier.conflicts.is_empty());
}
}
}
fn first_of_two_calls(atn: &dbt_antlr_runtime::analysis::ATN, rule_index: usize) -> i32 {
use dbt_antlr_runtime::analysis::RuleTransition;
let calls = |state: dbt_antlr_runtime::analysis::ATNStateRef| {
state.get_transitions().iter().any(|transition| {
transition
.try_as::<RuleTransition>()
.is_some_and(|call| call.get_target().get_rule_index() as usize == rule_index)
})
};
atn.iter_states()
.map(|state| atn.make_state_ref(state.get_state_number()))
.find(|state| {
state.get_transitions().iter().any(|transition| {
transition.try_as::<RuleTransition>().is_some_and(|call| {
call.get_target().get_rule_index() as usize == rule_index
&& calls(call.follow_state)
})
})
})
.expect("two side-by-side calls")
.get_state_number()
}
#[test]
fn new_invocations_after_the_skip_are_out_of_discipline() {
let path = grammars_dir().join("parser").join("PostfixSibling.g4");
let atn = parser_atn(&path);
let results = outcomes(&path);
let names = rule_names(&path, &results);
let types = token_types(&path, &["'-'", "'B'", "';'", "']'", "'A'"]);
let (minus, b, semi, close, a) = (types[0], types[1], types[2], types[3], types[4]);
for (rule, tokens) in [
("r", vec![minus, b, semi]),
("q", vec![minus, b, close]),
("m", vec![minus, b, a, minus]),
] {
let (result, _) = results
.iter()
.zip(&names)
.find(|(result, name)| {
result.kind != DecisionKind::Ll1
&& super::postfix::PostfixShape::analyze(
atn,
atn.decision_to_state[result.decision],
)
.is_some()
&& *name == rule
})
.unwrap_or_else(|| panic!("the postfix decision of {rule}"));
let table = result.table.as_ref().expect("a hybrid table");
let state = walk(table, &tokens).expect("the path has edges");
assert_ne!(state.accept, 1, "{rule}: the table does not take outright");
assert!(
state.is_escape() || state.is_guarded(),
"{rule}: the conflict defers"
);
if state.is_guarded() && rule != "m" {
let first_call = first_of_two_calls(atn, result.rule_index);
assert!(
table.guard_danger().contains(&first_call),
"{rule}: the guard defers at the first of the two calls"
);
}
}
}
#[test]
fn optional_elements_after_the_postfix_starve_it() {
let path = grammars_dir().join("parser").join("PostfixSibling.g4");
let atn = parser_atn(&path);
let results = outcomes(&path);
let names = rule_names(&path, &results);
let shaped: Vec<&str> = results
.iter()
.zip(&names)
.filter(|(result, _)| {
result.kind != DecisionKind::Ll1
&& super::postfix::PostfixShape::analyze(
atn,
atn.decision_to_state[result.decision],
)
.is_some()
})
.map(|(_, name)| name.as_str())
.collect();
assert_eq!(shaped, ["r", "q", "m"]);
}
#[test]
fn skip_mirrors_need_the_take_path_of_the_popped_frame() {
use dbt_antlr_runtime::analysis::{MIDWAY_TAINT, ROOTED_TAINT};
let atn = parser_atn(&grammars_dir().join("parser").join("DanglingElse.g4"));
let (decision, shape) = atn
.decision_to_state
.iter()
.find_map(|state| {
super::postfix::PostfixShape::analyze(atn, *state).map(|shape| (*state, shape))
})
.expect("the `e?` shape");
let take = decision.get_transitions()[0].get_target();
let rule_start = atn.rule_to_start_state[decision.get_rule_index() as usize];
assert!(
shape.skip_mirrors(rule_start, None, 0),
"inside the decision invocation"
);
assert!(
shape.skip_mirrors(take, None, BOUNDARY_TAINT),
"on the take path"
);
assert!(
!shape.skip_mirrors(rule_start, None, BOUNDARY_TAINT),
"off the take path"
);
for taint in [MIDWAY_TAINT, FOREIGN_LINEAGE_TAINT, ROOTED_TAINT] {
assert!(!shape.skip_mirrors(take, None, BOUNDARY_TAINT | taint));
}
assert!(
!shape.is_foreign_call(take, None),
"the take path calls `e`"
);
assert!(shape.is_foreign_call(rule_start, None));
}
#[test]
fn the_take_path_of_an_enclosing_invocation_mirrors_the_take() {
let results = outcomes(&grammars_dir().join("parser").join("DanglingElse.g4"));
let fires: usize = results
.iter()
.flat_map(DecisionOutcome::tables)
.flat_map(|table| &table.states)
.filter(|state| state.accept == 1 && state.conflicts == [1, 2])
.count();
assert_eq!(fires, 1);
assert!(results.iter().all(DecisionOutcome::is_fully_static));
}
#[test]
fn optional_postfix_shapes_are_guarded() {
let path = grammars_dir().join("parser").join("GuardExpr.g4");
let atn = parser_atn(&path);
let results = outcomes(&path);
let shaped: Vec<&DecisionOutcome> = results
.iter()
.filter(|result| {
super::postfix::PostfixShape::analyze(atn, atn.decision_to_state[result.decision])
.is_some()
})
.collect();
assert_eq!(shaped.len(), 1, "one `pred=predicate?` decision");
assert_eq!(shaped[0].rule_index, 2, "the `expr` rule owns the shape");
let fires: usize = results
.iter()
.flat_map(DecisionOutcome::tables)
.flat_map(|table| &table.states)
.filter(|state| state.accept == 1 && state.conflicts == [1, 2])
.count();
assert_eq!(fires, 0);
let guarded: usize = results.iter().map(DecisionOutcome::guarded_states).sum();
assert_eq!(guarded, 8, "matching the reference Java tool");
assert!(!shaped[0].is_fully_static(), "a guard may defer");
let table = shaped[0].table.as_ref().expect("the hybrid table is kept");
assert!(!table.guard_danger().is_empty(), "the guard can trip");
assert!(!table.guard_pass.is_empty(), "the walk can continue");
assert!(
table.states.iter().any(|state| state.is_guarded()),
"the table carries guarded states"
);
let csv = grammars_dir().join("CSV.g4");
let csv_atn = parser_atn(&csv);
let plain = outcomes(&csv);
assert!(plain.iter().all(|result| {
super::postfix::PostfixShape::analyze(csv_atn, csv_atn.decision_to_state[result.decision])
.is_none()
}));
}
fn resolve_static_only(path: &Path) -> Vec<DecisionOutcome> {
let mut results = outcomes_with(path, AtnFallback::Forbidden);
for result in &mut results {
result.resolve_static_only();
}
results
}
fn decoded_tables(
results: &[DecisionOutcome],
) -> dbt_antlr_runtime::dfa::static_parser_dfa::StaticParserTables {
load_image(super::build_tables(results).words())
}
fn load_image(words: &[u32]) -> dbt_antlr_runtime::dfa::static_parser_dfa::StaticParserTables {
dbt_antlr_runtime::dfa::static_parser_dfa::StaticParserTables::from_image(Box::leak(
words.to_vec().into_boxed_slice(),
))
.expect("the emitted image loads")
}
fn assert_no_runtime_escapes(results: &[DecisionOutcome]) {
use dbt_antlr_runtime::dfa::static_parser_dfa::{CONFLICT_ESCAPE, ESCAPE};
let decoded = decoded_tables(results);
for result in results {
let precedences = result.precedence.as_ref().map_or_else(
|| vec![0],
|precedence| {
std::iter::once(0)
.chain(precedence.cutoffs.iter().map(|cutoff| cutoff + 1))
.collect()
},
);
for precedence in precedences {
let Some(table) = decoded.table(result.decision as i32, precedence) else {
continue;
};
for state in 0..table.num_states() as i32 {
let accept = table.accept(state);
assert!(
![ESCAPE, CONFLICT_ESCAPE].contains(&accept),
"decision {} state {state} still escapes ({accept})",
result.decision
);
if let Some(guard) = table.guard(state) {
assert!(
guard.defer_alt > 0,
"decision {} state {state} defers to adaptive_predict ({guard:?})",
result.decision
);
}
}
}
}
}
#[test]
fn static_only_resolves_conflict_escapes_to_the_minimum_alternative() {
let results = resolve_static_only(&grammars_dir().join("ReferenceToATN.g4"));
let decision = &results[0];
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert_eq!(decision.escapes, 0);
assert!(decision.is_fully_static());
assert_eq!(decision.fallback_text(), "1m");
let resolved = decision.static_only.as_ref().expect("resolved");
assert_eq!((resolved.min_alt, resolved.syntax_error), (1, 0));
assert_eq!(resolved.min_alt_witness.as_deref(), Some(&[2, -1][..]));
let table = decision.table.as_ref().expect("the table is kept");
let state = &table.states[4];
assert_eq!(
state.accept, 1,
"the ATN/ID conflict predicts alternative 1"
);
assert_eq!(state.resolution, Some(super::EscapeResolution::MinAlt));
assert_eq!(table.escapes(), 0);
assert_no_runtime_escapes(&results);
}
#[test]
fn static_only_turns_predicated_states_into_syntax_errors() {
let results = resolve_static_only(&fixture("parser-shapes").join("ParserShapes.g4"));
let plus = &results[1];
let resolved = plus.static_only.as_ref().expect("the loop is resolved");
assert_eq!(resolved.min_alt, 0);
assert!(resolved.syntax_error > 0, "the predicated branches stop");
assert!(resolved.syntax_error_witness.is_some());
assert_eq!(plus.fallback_text(), format!("{}x", resolved.syntax_error));
let table = plus.table.as_ref().expect("the hybrid table is kept");
let dead_ends: Vec<_> = table
.states
.iter()
.filter(|state| state.resolution == Some(super::EscapeResolution::SyntaxError))
.collect();
assert_eq!(dead_ends.len(), resolved.syntax_error);
for state in dead_ends {
assert!(state.predicated, "only a predicate stops the guess");
assert_eq!(state.accept, 0);
assert_eq!(
state.fallback, 0,
"no error-recovery alternative hides the error"
);
assert!(state.edges.is_empty());
assert!(state.continuation.is_none());
}
let decoded = decoded_tables(&results);
let runtime = decoded.table(1, 0).expect("decision 1 has a table");
let dead_end = super::tables::minimized(table)
.states
.iter()
.position(|state| state.resolution.is_some())
.expect("a resolved state") as i32;
assert_eq!(runtime.accept(dead_end), 0);
assert_eq!(runtime.fallback(dead_end), None);
for token in -1..=5 {
assert_eq!(runtime.edge(dead_end, token), None, "token {token}");
}
}
#[test]
fn static_only_keeps_the_guard_of_guarded_takes() {
let path = grammars_dir().join("parser").join("GuardExpr.g4");
let atn = parser_atn(&path);
let results = resolve_static_only(&path);
let shaped = results
.iter()
.find(|result| {
super::postfix::PostfixShape::analyze(atn, atn.decision_to_state[result.decision])
.is_some()
})
.expect("the `pred?` decision");
assert!(
shaped.guarded_states() > 0,
"the guarded takes stay guarded"
);
assert!(shaped.is_fully_static());
let table = shaped.table.as_ref().expect("the hybrid table is kept");
assert_eq!(table.guarded(), shaped.guarded_states());
assert!(!table.guard_groups.is_empty(), "the guard can trip");
assert!(!table.guard_pass.is_empty(), "the walk can continue");
for state in table.states.iter().filter(|state| state.is_guarded()) {
assert_eq!(state.resolution, Some(super::EscapeResolution::Guarded));
assert_eq!(state.guarded_alt, 1, "the take");
assert_eq!(state.guard_defer_alt, 2, "the skip");
assert!((state.guard_group as usize) < table.guard_groups.len());
}
let resolved = shaped.static_only.as_ref().expect("resolved");
assert_eq!(resolved.guarded, shaped.guarded_states());
assert!(
shaped
.fallback_text()
.starts_with(&format!("{}g", resolved.guarded)),
"{}",
shaped.fallback_text()
);
assert_no_runtime_escapes(&results);
let decoded = decoded_tables(&results);
let runtime = decoded
.table(shaped.decision as i32, 0)
.expect("the decision has a table");
let guarded = table
.states
.iter()
.position(|state| state.is_guarded())
.expect("a guarded state") as i32;
let guard = runtime
.guard(guarded)
.expect("the runtime state is guarded");
assert_eq!((guard.alt, guard.defer_alt), (1, 2));
}
#[test]
fn static_only_guards_iterates_that_consume_foreign_tokens() {
let path = grammars_dir().join("parser").join("InlineAlias.g4");
let hybrid = outcomes(&path);
let hybrid_loop = hybrid
.iter()
.find(|result| result.is_precedence_loop())
.expect("the operator loop");
assert!(hybrid_loop.escapes > 0, "the cast state escapes");
let results = resolve_static_only(&path);
let alias_loop = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the operator loop");
let resolved = alias_loop.static_only.as_ref().expect("resolved");
assert!(resolved.guarded > 0);
assert_eq!(
(
resolved.min_alt,
resolved.min_viable_alt,
resolved.syntax_error
),
(0, 0, 0),
"every state of the loop is guarded: {resolved:?}"
);
assert_no_runtime_escapes(&results);
let precedence = alias_loop.precedence.as_ref().expect("precedence tables");
let table = precedence
.tables
.iter()
.flatten()
.max_by_key(|table| table.guarded())
.expect("a class table");
assert!(table.guard_groups.len() >= 2, "{:?}", table.guard_groups);
let smallest = table
.guard_groups
.iter()
.min_by_key(|group| group.len())
.expect("a group");
assert!(
table
.guard_groups
.iter()
.any(|group| group.len() > smallest.len()),
"the `AND` states do not guard the `CAST` operand: {:?}",
table.guard_groups
);
}
#[test]
fn guarded_states_have_their_own_guard_groups() {
let results = outcomes(&grammars_dir().join("parser").join("LoopObligation.g4"));
let p = results
.iter()
.find(|result| result.is_precedence_loop())
.expect("the `p` loop");
let precedence = p.precedence.as_ref().expect("precedence tables");
for table in precedence.tables.iter().flatten() {
if table.guarded() == 0 {
continue;
}
assert_eq!(table.guard_danger(), [9, 15]);
assert_eq!(table.guard_groups.len(), 2, "{:?}", table.guard_groups);
for state in table.states.iter().filter(|state| state.is_guarded()) {
assert_eq!(state.guard_defer_alt, 2, "the exit");
assert_eq!(
table.guard_groups[state.guard_group as usize].len(),
1,
"a state guards one invoking state"
);
}
}
}
#[test]
fn static_only_looks_further_and_guesses_the_minimum_viable_alternative() {
let path = grammars_dir().join("parser").join("ParenExpr.g4");
let adaptive = &outcomes(&path)[1];
assert_eq!(adaptive.kind, DecisionKind::Hybrid);
let default_table = adaptive.table.as_ref().expect("the hybrid table");
assert!(default_table.escapes() > 0);
let results = resolve_static_only(&path);
let decision = &results[1];
let table = decision.table.as_ref().expect("the hybrid table is kept");
assert!(
table.states.len() > 4 * default_table.states.len(),
"{} states with the larger budget, {} without",
table.states.len(),
default_table.states.len()
);
let resolved = decision.static_only.as_ref().expect("resolved");
assert!(resolved.min_viable_alt > 0, "{resolved:?}");
assert_eq!(resolved.syntax_error, 0);
assert!(resolved.min_viable_alt_witness.is_some());
assert!(
decision
.fallback_text()
.ends_with(&format!("+{}v", resolved.min_viable_alt)),
"{}",
decision.fallback_text()
);
let guesses: Vec<_> = table
.states
.iter()
.filter(|state| state.resolution == Some(super::EscapeResolution::MinViableAlt))
.collect();
assert_eq!(guesses.len(), resolved.min_viable_alt);
for state in guesses {
assert!(!state.predicated);
assert!(state.conflicts.is_empty(), "a guess is not a conflict");
assert!(state.viable_alts.len() >= 2, "{:?}", state.viable_alts);
assert_eq!(state.accept, state.viable_alts[0]);
assert!(state.continuation.is_none());
}
assert_no_runtime_escapes(&results);
}
#[test]
fn static_only_keeps_precedence_classes_static() {
let results = resolve_static_only(&grammars_dir().join("parser").join("LrDfa.g4"));
assert!(results.iter().any(|result| result.precedence.is_some()));
for result in &results {
assert!(
result.static_only.is_some(),
"decision {} ({}) resolves",
result.decision,
result.kind
);
if let Some(precedence) = &result.precedence {
assert_eq!(precedence.escapes, 0);
assert!(
precedence
.tables
.iter()
.flatten()
.all(|table| table.escapes() == 0)
);
}
}
assert_no_runtime_escapes(&results);
}
#[test]
fn static_only_rejects_decisions_without_a_static_prediction() {
let mut results = outcomes_with(
&fixture("parser-shapes").join("ParserShapes.g4"),
AtnFallback::Forbidden,
);
let nongreedy = &mut results[3];
assert_eq!(nongreedy.kind, DecisionKind::Adaptive);
assert!(!nongreedy.resolve_static_only());
assert!(nongreedy.static_only.is_none());
let optional = &mut results[0];
assert_eq!(optional.kind, DecisionKind::Ll1);
assert!(optional.resolve_static_only(), "LL(1) needs no table");
assert_eq!(optional.fallback_text(), "0");
}
#[test]
fn static_only_keeps_partial_tables_below_the_coverage_threshold() {
let path = grammars_dir().join("parser").join("LowCoverage.g4");
let adaptive = &outcomes(&path)[0];
assert_eq!(adaptive.kind, DecisionKind::Adaptive);
assert!(adaptive.table.is_none());
let results = resolve_static_only(&path);
let decision = &results[0];
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert!(
decision.coverage_percent < super::PARTIAL_MIN_COVERAGE_PERCENT,
"coverage {}%",
decision.coverage_percent
);
assert!(decision.table.is_some());
let resolved = decision.static_only.as_ref().expect("resolved");
assert_eq!((resolved.min_alt, resolved.syntax_error), (0, 10));
assert_eq!(decision.fallback_text(), "10x");
assert_no_runtime_escapes(&results);
}
fn outcomes_of_source(name: &str, source: &str) -> Vec<DecisionOutcome> {
let directory =
std::env::temp_dir().join(format!("dbt-antlr-descent-{}-{name}", std::process::id()));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join(format!("{name}.g4"));
std::fs::write(&path, source).expect("scratch grammar");
let results = outcomes(&path);
let _ = std::fs::remove_dir_all(&directory);
results
}
fn rule_has_groups(results: &[DecisionOutcome], rule_index: usize) -> bool {
results
.iter()
.filter(|result| result.rule_index == rule_index)
.any(|result| result.descent.is_some())
}
#[test]
fn shared_descent_groups_cure_the_escapes_of_the_fuzz_items() {
let results = outcomes(&grammars_dir().join("parser/FuzzExpr.g4"));
let path = grammars_dir().join("parser/FuzzExpr.g4");
let rules = rule_names(&path, &results);
let by_rule = |name: &str| {
results
.iter()
.zip(&rules)
.find(|(_, rule)| *rule == name)
.map(|(result, _)| result)
.expect("the rule has a decision")
};
let item = by_rule("item");
assert_eq!(item.kind, DecisionKind::Static);
assert_eq!(item.escapes, 0);
assert_eq!(item.descent_group_states(), 15);
let plan = item.descent.as_ref().expect("item accepts with a group");
let [group] = &plan.groups[..] else {
panic!("one group: {plan:?}");
};
assert_eq!(group.alts, [1, 2]);
assert!(group.prefix.is_empty());
assert_eq!(group.default_alt, 2);
assert_eq!(group.arms.len(), 1);
assert_eq!(group.arms[0].alt, 1);
assert!(
item.table
.as_ref()
.expect("item has a table")
.states
.iter()
.any(|state| state.accept == group.virtual_alt)
);
let alias = by_rule("alias");
assert!(alias.descent.is_none());
assert!(alias.escapes > 0);
let binding = by_rule("binding");
assert!(binding.descent.is_none());
assert!(binding.escapes > 0);
}
#[test]
fn shared_descent_groups_share_a_one_token_prefix() {
let results = outcomes(&grammars_dir().join("parser/ParenExpr.g4"));
let primary = results
.iter()
.find(|result| result.descent.is_some())
.expect("the primary block accepts with a group");
assert_eq!(primary.descent_group_states(), 8);
assert_eq!(primary.escapes, 8);
let group = &primary.descent.as_ref().unwrap().groups[0];
assert_eq!(group.alts, [3, 4]);
assert_eq!(group.prefix.len(), 1);
assert_eq!(group.default_alt, 0);
let arms: Vec<(i32, usize)> = group
.arms
.iter()
.map(|arm| (arm.alt, arm.tokens.len()))
.collect();
assert_eq!(arms, [(3, 1), (4, 1)], "',' and ')'");
}
fn descent_witness(name: &str, x: &str, y: &str) -> String {
format!(
"grammar {name};\ns : x EOF ;\nx : {x} ;\ny : {y} ;\nID : [a-z]+ ;\nWS : [ \\t]+ -> skip ;\n"
)
}
#[test]
fn shared_descent_accepts_a_plain_group() {
let results = outcomes_of_source(
"DescentPlain",
&descent_witness("DescentPlain", "y '+' ID | y", "'(' y ')' | ID"),
);
assert!(rule_has_groups(&results, 1), "{results:?}");
assert!(results.iter().all(|result| result.escapes == 0));
}
#[test]
fn shared_descent_rejects_a_rule_with_arguments() {
let results = outcomes_of_source(
"DescentArgs",
&descent_witness("DescentArgs", "y[1] '+' ID | y[1]", "'(' y[1] ')' | ID")
.replace("y : ", "y[i32 depth] : "),
);
assert!(!rule_has_groups(&results, 1));
}
#[test]
fn shared_descent_rejects_a_rule_that_runs_an_action() {
let results = outcomes_of_source(
"DescentAction",
&descent_witness(
"DescentAction",
"y '+' ID | y",
"'(' y ')' | ID {} {let _ = 1;}",
),
);
assert!(!rule_has_groups(&results, 1));
}
#[test]
fn shared_descent_rejects_members_with_another_prefix_length() {
let results = outcomes_of_source(
"DescentPrefix",
&descent_witness(
"DescentPrefix",
"('[' | '[' '[') y '+' ID | '[' y",
"'(' y ')' | ID",
),
);
assert!(!rule_has_groups(&results, 1));
let results = outcomes_of_source(
"DescentSetPrefix",
&descent_witness(
"DescentSetPrefix",
"('[' | ']') y '+' ID | '[' y",
"'(' y ')' | ID",
),
);
assert!(!rule_has_groups(&results, 1));
}
#[test]
fn shared_descent_skips_optional_blocks() {
let results = outcomes_of_source(
"DescentOptional",
&descent_witness("DescentOptional", "(y '+' ID)? y", "'(' y ')' | ID"),
);
assert!(results.iter().all(|result| result.descent.is_none()));
}
#[test]
fn shared_descent_rejects_decisions_and_loops_before_the_shared_rule() {
let results = outcomes_of_source(
"DescentLoop",
&descent_witness(
"DescentLoop",
"(y '+')+ ':' ID | y ';' ID",
"'(' y ')' | ID",
),
);
assert!(!rule_has_groups(&results, 1));
let results = outcomes_of_source(
"DescentOptionalPrefix",
&descent_witness(
"DescentOptionalPrefix",
"'['? y '+' ID | y ';' ID",
"'(' y ')' | ID",
),
);
assert!(!rule_has_groups(&results, 1));
}
#[test]
fn shared_descent_excludes_rules_whose_shared_rule_conflicts_with_member_tails() {
let results = outcomes(&grammars_dir().join("parser/DescentContext.g4"));
assert!(
results
.iter()
.all(|result| result.descent.is_none() && result.descent_group_states() == 0),
"{results:?}"
);
let results = outcomes_of_source(
"DescentDistinctSubrules",
concat!(
"grammar DescentDistinctSubrules;\n",
"s : d EOF ;\n",
"d : r '+' ID ';' ID | r ';' ID INT ;\n",
"r : '(' r ')' | b '+' ID | a ;\n",
"a : '[' a ']' | ID ;\n",
"b : '[' b ']' | ID ;\n",
"ID : [a-z]+ ;\n",
"INT : [0-9]+ ;\n",
"WS : [ \\t\\n]+ -> skip ;\n",
),
);
assert!(
results
.iter()
.all(|result| result.descent.is_none() && result.descent_group_states() == 0),
"{results:?}"
);
}
fn attempts_of(results: &[DecisionOutcome], decision: usize) -> Vec<AttemptKind> {
results[decision]
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect()
}
#[test]
fn one_build_per_decision() {
let path = fixture("vscode-split").join("TParser.g4");
let results = outcomes_with_budget(&path, super::DEFAULT_VISIT_BUDGET);
for (decision, result) in results.iter().enumerate() {
if result.kind == DecisionKind::Ll1 || result.no_table == Some(NoTableReason::NonGreedy) {
continue;
}
let builds = result
.precedence
.as_ref()
.map_or(1, |precedence| precedence.tables.len());
assert_eq!(
attempts_of(&results, decision).len(),
builds,
"decision {decision}: {result:?}"
);
}
let path = grammars_dir().join("parser").join("LowCoverage.g4");
let results = outcomes_with_budget(&path, super::DEFAULT_VISIT_BUDGET);
assert_eq!(results[0].kind, DecisionKind::Adaptive);
assert!(matches!(
results[0].no_table,
Some(NoTableReason::LowCoverage { .. })
));
assert_eq!(attempts_of(&results, 0), [AttemptKind::Default]);
}
#[test]
fn exhausted_start_state_falls_back_to_widening() {
let path = grammars_dir().join("ReferenceToATN.g4");
let results = outcomes_with_budget(&path, 1);
assert_eq!(results[0].kind, DecisionKind::Adaptive);
assert_eq!(
attempts_of(&results, 0),
[AttemptKind::Default, AttemptKind::Widened]
);
}
#[test]
fn builds_escape_where_the_visit_budget_runs_out() {
let path =
fixture("testcompositegrammars-testimportlargegrammar-110006096d").join("NewJava.g4");
let results = outcomes_with_budget(&path, 2_000);
assert_eq!(results[7].kind, DecisionKind::Hybrid);
assert_eq!(results[7].budget_cutoff, Some(BudgetCutoff::Visits));
assert!(results[7].escapes > 0);
assert_eq!(
attempts_of(&results, 7),
[AttemptKind::Default, AttemptKind::Widened]
);
assert_eq!(
results[7].cost.attempts[0].outcome,
AttemptOutcome::VisitBudget
);
let results = outcomes_with_budget(&path, 100);
assert_eq!(results[7].kind, DecisionKind::Adaptive);
assert!(results[7].table.is_none());
}
#[test]
fn precedence_classes_keep_tables_where_the_visit_budget_runs_out() {
let path = grammars_dir().join("parser").join("LoopFrontier.g4");
let results = outcomes_with_budget(&path, 2_000);
let precedence = results[4].precedence.as_ref().expect("precedence tables");
assert_eq!(precedence.adaptive_classes, 0);
assert_eq!(precedence.tables.len(), 5);
assert!(precedence.tables.iter().all(Option::is_some));
assert_eq!(results[4].budget_cutoff, Some(BudgetCutoff::Visits));
}
#[test]
fn conflict_escapes_do_not_fall_back_to_widening() {
let results = outcomes_of_source(
"WidenedAfterStop",
"grammar WidenedAfterStop;\n\
top : a X | a Y ;\n\
a : ( A | C ( B A | B a E ) ) D ;\n\
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; X : 'x' ; Y : 'y' ;\n",
);
let decision = &results[1];
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert_eq!(decision.conflicts, [vec![1, 2]]);
assert!(decision.table.is_some());
assert_eq!(attempts_of(&results, 1), [AttemptKind::Default]);
}
#[test]
fn widened_competitors_get_no_uniform_trust() {
let path = grammars_dir().join("parser").join("WidenedTrust.g4");
let types = token_types(&path, &["'a'", "'b'"]);
let (a, b) = (types[0], types[1]);
for atn_fallback in [AtnFallback::Allowed, AtnFallback::Forbidden] {
let results = widened_outcomes_with(&path, atn_fallback);
let decision = &results[1];
assert_eq!(attempts_of(&results, 1), [AttemptKind::Widened]);
assert!(!decision.is_fully_static(), "{atn_fallback:?}");
let table = decision.table.as_ref().expect("a partial table");
assert!(
!table
.states
.iter()
.any(|state| state.accept > 0 && state.conflicts.len() > 1),
"{atn_fallback:?}: no conflict state resolves to an alternative"
);
let conflict = walk(table, &[b, b, b, b, a]).expect("conflict state");
assert_eq!(
conflict.accept, CONFLICT_ESCAPE,
"{atn_fallback:?}: the table does not decide after `'b' 'b' 'b' 'b' 'a'`"
);
assert_eq!(conflict.conflicts, [1, 2], "{atn_fallback:?}");
}
}
#[test]
fn widened_precedence_filter_keeps_the_exit() {
let path = grammars_dir().join("parser").join("WidenedPrecedence.g4");
let types = token_types(&path, &["'+'", "'q'", "'r'"]);
let tokens = [types[0], types[1], types[2], EOF];
for widened in [false, true] {
for atn_fallback in [AtnFallback::Allowed, AtnFallback::Forbidden] {
let results = if widened {
widened_outcomes_with(&path, atn_fallback)
} else {
outcomes_with(&path, atn_fallback)
};
let decision = &results[1];
assert!(decision.is_precedence_loop());
assert_eq!(
decision
.cost
.attempts
.iter()
.all(|attempt| attempt.kind == AttemptKind::Widened),
widened,
"{atn_fallback:?}"
);
let precedence = decision.precedence.as_ref().expect("precedence tables");
assert_eq!(precedence.cutoffs[0], 2);
assert_eq!(precedence.adaptive_classes, 0, "{atn_fallback:?}");
for (class, table) in precedence.tables.iter().enumerate().skip(1) {
let table = table.as_ref().expect("class table");
let prediction = (0..=tokens.len())
.filter_map(|length| walk(table, &tokens[..length]))
.find(|state| state.accept != 0);
assert!(
prediction.is_some_and(|state| {
state.accept == 2
|| (state.accept < 0
&& (state.conflicts.contains(&2) || state.viable_alts.contains(&2)))
}),
"{atn_fallback:?}, widened {widened}: class {class} iterates on \
`'+' 'q' 'r' EOF`"
);
}
}
}
}
#[test]
fn parallel_builds_match_serial_builds() {
let mut grammars = Vec::new();
collect_grammars(&grammars_dir(), &mut grammars);
grammars.push(fixture("vscode-cpp14/CPP14.g4"));
grammars.sort();
let mut decisions = 0_usize;
for path in grammars {
let Ok(compilation) = compile(LoadOptions {
roots: vec![path.clone()],
library_directories: Vec::new(),
}) else {
continue;
};
for root in &compilation.roots {
let Some(parser_id) = root.parser else {
continue;
};
let parser = compilation.parser(parser_id).expect("parser artifact");
for atn_fallback in [AtnFallback::Allowed, AtnFallback::Forbidden] {
let build_on = |threads| {
builder(parser)
.with_atn_fallback(atn_fallback)
.with_visit_budget(5_000)
.build_on(threads)
};
let parallel = build_on(8);
let serial = build_on(1);
decisions += serial.len();
assert_eq!(serial, parallel, "{}", path.display());
}
}
}
assert!(decisions > 800, "decisions built: {decisions}");
}
fn visit_budget(budget: u64) -> ParserDfaBudgets {
ParserDfaBudgets {
global: BudgetLimits {
max_visits: Some(budget),
..BudgetLimits::default()
},
}
}
fn build_with_budget(
path: &Path,
budget: u64,
) -> crate::optimization::static_parser_dfa::StaticParserDfaArtifact {
let compilation = compile(LoadOptions {
roots: vec![path.to_path_buf()],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let parser = compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact");
crate::optimization::StaticParserDfa::build(
parser,
&compilation.sources,
AtnFallback::Allowed,
false,
&visit_budget(budget),
)
}
#[test]
fn spent_visit_budgets_emit_g4s193_warnings() {
let build = build_with_budget(&grammars_dir().join("Perf.g4"), 100);
let warnings: Vec<_> = build
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.code == "G4S193")
.map(|diagnostic| {
assert_eq!(diagnostic.severity, Severity::Warning);
diagnostic.message.as_str()
})
.collect();
assert_eq!(
warnings,
[
"the analysis of parser decision 0 of rule 'stat' is slow: 1 of 1 build attempts \
spent the visit budget (100 configs); 100 configs visited, 6 DFA states built; \
most visited rules: expr 93%, stat 7%",
"the analysis of parser decision 3 of rule 'expr' is slow: 3 of 7 build attempts \
spent the visit budget (100 configs); 548 configs visited, 23 DFA states built; \
most visited rules: expr 88%, stat 11%",
]
);
let build = build_with_budget(&grammars_dir().join("Perf.g4"), super::DEFAULT_VISIT_BUDGET);
assert!(
build
.diagnostics
.iter()
.all(|diagnostic| diagnostic.code != "G4S193"),
"{:?}",
build.diagnostics
);
}
#[test]
fn decision_costs_account_for_every_visit() {
for budget in [100, super::DEFAULT_VISIT_BUDGET] {
let results = outcomes_with_budget(&grammars_dir().join("Perf.g4"), budget);
for result in &results {
let cost = &result.cost;
assert!(cost.elapsed.is_none(), "no times without profiling");
for attempt in &cost.attempts {
assert!(attempt.visits <= budget, "{attempt:?}");
assert!(attempt.elapsed.is_none());
if attempt.outcome == AttemptOutcome::VisitBudget {
assert_eq!(attempt.visits, budget, "{attempt:?}");
}
}
let by_rule: u64 = cost.rule_visits.iter().map(|(_, visits)| visits).sum();
assert_eq!(by_rule, cost.visits(), "decision {}", result.decision);
}
assert_eq!(attempts_of(&results, 1), []);
assert_eq!(attempts_of(&results, 2), [AttemptKind::Default]);
}
}
#[test]
fn attempt_codes_follow_the_classes_and_the_fallback_policy() {
let results = outcomes_with_budget(
&grammars_dir().join("parser").join("LoopFrontier.g4"),
2_000,
);
assert_eq!(
results[4].cost.attempts_text(),
"c0: D$; c1: D$; c2: D$; c3: D; c4: D"
);
let path = grammars_dir().join("ReferenceToATN.g4");
assert_eq!(outcomes(&path)[0].cost.attempts_text(), "D");
assert_eq!(
outcomes_with(&path, AtnFallback::Forbidden)[0]
.cost
.attempts_text(),
"S"
);
}
#[test]
fn profiled_builds_time_every_decision_and_list_the_slowest() {
let directory = std::env::temp_dir().join(format!("dbt-antlr-profile-{}", std::process::id()));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join("Many.g4");
let mut source = String::from("grammar Many;\n");
for rule in 0..25 {
source.push_str(&format!("r{rule} : A B | A C ;\n"));
}
source.push_str("A : 'a' ; B : 'b' ; C : 'c' ;\n");
std::fs::write(&path, source).expect("scratch grammar");
let compilation = compile(LoadOptions {
roots: vec![path],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let _ = std::fs::remove_dir_all(&directory);
let parser = compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact");
let build = crate::optimization::StaticParserDfa::build(
parser,
&compilation.sources,
AtnFallback::Allowed,
true,
&ParserDfaBudgets::default(),
);
assert_eq!(build.report.decisions.len(), 25);
for decision in &build.report.decisions {
let cost = &decision.result.cost;
assert!(cost.elapsed.is_some(), "{cost:?}");
assert_eq!(cost.attempts.len(), 1, "{cost:?}");
assert!(
cost.attempts
.iter()
.all(|attempt| attempt.elapsed.is_some())
);
}
let profile = crate::optimization::StaticParserDfa::render_decision_profile(&[build.report]);
let lines: Vec<&str> = profile.lines().collect();
let slowest = lines
.iter()
.position(|line| *line == "slowest 20 decisions:")
.unwrap_or_else(|| panic!("{profile}"));
assert!(
lines[slowest + 1].trim_start().starts_with("# rule"),
"{profile}"
);
let rows = lines[slowest + 2..]
.iter()
.filter(|line| !line.is_empty())
.count();
assert_eq!(rows, 20, "{profile}");
}
#[test]
fn single_token_alternatives_share_one_successor() {
fn keywords(count: usize) -> DecisionOutcome {
let mut source = format!("grammar Keywords{count};\ns : word X | word Y ;\nword :");
for keyword in 0..count {
source.push_str(&format!(" K{keyword} #k{keyword} |"));
}
source.push_str(" L K0 R #nested ;\nX : 'x' ; Y : 'y' ; L : '(' ; R : ')' ;\n");
for keyword in 0..count {
source.push_str(&format!("K{keyword} : 'k{keyword}' ;\n"));
}
outcomes_of_source(&format!("Keywords{count}"), &source).remove(0)
}
let few = keywords(2);
let many = keywords(200);
assert_eq!(few.kind, DecisionKind::Static);
assert_eq!(many.kind, few.kind);
assert_eq!(many.k, few.k);
assert_eq!(many.num_dfa_states, few.num_dfa_states);
let start = &many.table.as_ref().expect("LL(k) table").states[0];
let covered: i32 = start.edges.iter().map(|edge| edge.hi - edge.lo + 1).sum();
assert_eq!(
covered, 201,
"each keyword and L lead out of the start state"
);
let extra = many.cost.visits() - few.cost.visits();
assert!(extra <= 3 * 198, "{extra} extra visits");
}
fn build_source(
name: &str,
source: &str,
) -> crate::optimization::static_parser_dfa::StaticParserDfaArtifact {
let directory =
std::env::temp_dir().join(format!("dbt-antlr-build-{}-{name}", std::process::id()));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join(format!("{name}.g4"));
std::fs::write(&path, source).expect("scratch grammar");
let build = build_with_budget(&path, super::DEFAULT_VISIT_BUDGET);
let _ = std::fs::remove_dir_all(&directory);
build
}
fn keyword_grammar(name: &str, alternatives: &str, rules: &str, callers: usize) -> String {
let mut source = format!("grammar {name};\nword : {alternatives} ;\n{rules}");
for caller in 0..callers {
source.push_str(&format!("r{caller} : word X ;\n"));
}
source.push_str("X : 'x' ; L : '(' ; R : ')' ;\n");
for keyword in 0..70 {
source.push_str(&format!("K{keyword} : 'k{keyword}' ;\n"));
}
source
}
fn token_branch_warnings(
name: &str,
alternatives: &str,
rules: &str,
callers: usize,
) -> Vec<(String, String)> {
let source = keyword_grammar(name, alternatives, rules, callers);
build_source(name, &source)
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.code == "G4S194")
.map(|diagnostic| {
assert_eq!(diagnostic.severity, Severity::Warning);
let offset = diagnostic.primary.bytes.start as usize;
let line = source[..offset].matches('\n').count() + 1;
let column = offset
- source[..offset]
.rfind('\n')
.map_or(0, |newline| newline + 1);
(format!("{line}:{column}"), diagnostic.message.clone())
})
.collect()
}
fn token_branch_causes(message: &str) -> &str {
let start = message.find("because ").expect("causes") + "because ".len();
let end = message.find(" before they read").expect("entries");
&message[start..end]
}
#[test]
fn unfolded_token_branches_emit_g4s194_warnings() {
let keywords = (0..70)
.map(|keyword| format!("K{keyword}"))
.collect::<Vec<_>>();
let mixed = format!("{} | L word R", keywords.join(" | "));
assert_eq!(
token_branch_warnings("Mixed", &mixed, "", 20),
[(
"2:7".to_owned(),
"rule 'word' has a block with 70 single-token alternatives that do not fold into one \
token set. The block does not fold because 1 alternative is not a single token. 21 \
call sites enter the rule before they read a token. The analysis of the static \
parser DFA follows each alternative at each site. Move the single tokens into one \
unlabeled subrule, for example `( A | B | C )`, or into a token-only rule"
.to_owned()
)]
);
let causes = |name: &str, alternatives: &str, rules: &str, callers: usize| {
token_branch_warnings(name, alternatives, rules, callers)
.iter()
.map(|(span, message)| format!("{span} {}", token_branch_causes(message)))
.collect::<Vec<_>>()
};
let labeled = keywords
.iter()
.map(|keyword| format!("{keyword} #{}", keyword.to_lowercase()))
.collect::<Vec<_>>()
.join(" | ");
assert_eq!(
causes("Labeled", &labeled, "", 20),
["2:7 70 alternatives have a label. 20 call sites enter the rule"]
);
assert_eq!(causes("Callers", &labeled, "", 19), [] as [String; 0]);
let element_labels = keywords
.iter()
.map(|keyword| format!("k={keyword}"))
.collect::<Vec<_>>()
.join(" | ");
assert_eq!(
causes("ElementLabels", &format!("{element_labels} | L"), "", 20),
["2:7 70 tokens have an element label. 20 call sites enter the rule"]
);
let threshold = format!("{} | L word R", keywords[..64].join(" | "));
assert_eq!(causes("Threshold", &threshold, "", 20).len(), 1);
let few = format!("{} | L word R", keywords[..63].join(" | "));
assert_eq!(causes("Few", &few, "", 20), [] as [String; 0]);
assert_eq!(
causes("Folded", &keywords.join(" | "), "", 20),
[] as [String; 0]
);
let grouped = format!("( {} ) | L word R", keywords.join(" | "));
assert_eq!(causes("Grouped", &grouped, "", 20), [] as [String; 0]);
let late = format!("L ( {mixed} ) | X");
assert_eq!(causes("Late", &late, "", 20), [] as [String; 0]);
let rules = format!("opt : L | ;\ninner : {mixed} ;\n");
assert_eq!(
causes("Inner", "opt inner X | L", &rules, 20),
["4:8 1 alternative is not a single token. 22 call sites enter the rule"]
);
let nested = format!("X ( {mixed} )? | ( {mixed} ) X");
let column = "word : ".len() + nested.rfind("( ").expect("second block");
assert_eq!(
causes("Nested", &nested, "", 20),
[format!(
"2:{column} 1 alternative is not a single token. 22 call sites enter the rule"
)]
);
for (name, prefix) in [("NullableBlock", "( L | )"), ("NullableCall", "opt")] {
let behind = format!("{prefix} ( {mixed} ) X");
let column = "word : ".len() + behind.rfind("( K0").expect("block");
assert_eq!(
causes(name, &behind, "opt : L | ;\n", 20),
[format!(
"2:{column} 1 alternative is not a single token. 21 call sites enter the rule"
)]
);
}
let recursive = format!("{} | word L word", keywords.join(" | "));
assert_eq!(
causes("Recursive", &recursive, "", 20),
["2:7 1 alternative is not a single token. 21 call sites enter the rule"]
);
}
fn build_source_with(
name: &str,
source: &str,
atn_fallback: AtnFallback,
budgets: &ParserDfaBudgets,
) -> (
Vec<crate::grammar::diagnostic::Diagnostic>,
crate::optimization::static_parser_dfa::StaticParserDfaArtifact,
) {
static SCRATCH: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
let scratch = SCRATCH.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let directory = std::env::temp_dir().join(format!(
"dbt-antlr-budget-{}-{scratch}-{name}",
std::process::id()
));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join(format!("{name}.g4"));
std::fs::write(&path, source).expect("scratch grammar");
let compilation = compile(LoadOptions {
roots: vec![path],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let _ = std::fs::remove_dir_all(&directory);
let parser = compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact");
let build = crate::optimization::StaticParserDfa::build(
parser,
&compilation.sources,
atn_fallback,
false,
budgets,
);
(compilation.diagnostics.clone(), build)
}
fn rule_budgets(
build: &crate::optimization::static_parser_dfa::StaticParserDfaArtifact,
rule: &str,
) -> Vec<super::DecisionBudget> {
build
.report
.decisions
.iter()
.filter(|decision| decision.rule == rule)
.map(|decision| decision.result.budget)
.collect()
}
const BUDGET_GRAMMAR: &str = "grammar Budgets;
options { max_dfa_states = 7; }
s : a b EOF ;
a options { max_k = 3; } : A B | A C ;
b : ( options { max_dfa_visits = 5000; } : X Y | X Z ) | W ;
A : 'a' ; B : 'b' ; C : 'c' ; X : 'x' ; Y : 'y' ; Z : 'z' ; W : 'w' ;
";
#[test]
fn budget_options_set_the_budgets_of_their_decisions() {
let (diagnostics, build) = build_source_with(
"Budgets",
BUDGET_GRAMMAR,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
assert!(
diagnostics
.iter()
.all(|diagnostic| !matches!(diagnostic.code, "G4S014" | "G4S015")),
"{diagnostics:?}"
);
let budget = |max_states, max_k, max_visits| super::DecisionBudget {
max_states,
max_k,
max_visits,
explicit_max_states: true,
};
assert_eq!(rule_budgets(&build, "a"), [budget(7, Some(3), 2_000_000)]);
assert_eq!(
rule_budgets(&build, "b"),
[budget(7, None, 5_000), budget(7, None, 2_000_000)]
);
assert_eq!(build.report.budget, budget(7, None, 2_000_000));
}
#[test]
fn budget_options_win_over_the_base_limits() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(50),
max_k: Some(2),
max_visits: Some(9_000),
},
};
let (_, build) = build_source_with("Budgets", BUDGET_GRAMMAR, AtnFallback::Allowed, &budgets);
let budget = |max_states, max_k, max_visits| super::DecisionBudget {
max_states,
max_k,
max_visits,
explicit_max_states: true,
};
assert_eq!(rule_budgets(&build, "a"), [budget(7, Some(3), 9_000)]);
assert_eq!(
rule_budgets(&build, "b"),
[budget(7, Some(2), 5_000), budget(7, Some(2), 9_000)]
);
}
#[test]
fn incorrect_budget_option_values_emit_g4s015_warnings() {
let source = "grammar Wrong;
options { max_dfa_states = 0; }
s options { max_k = many; } : A B | A C ;
A : 'a' ; B : 'b' ; C : 'c' ;
";
let (diagnostics, build) = build_source_with(
"Wrong",
source,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
let warnings: Vec<_> = diagnostics
.iter()
.filter(|diagnostic| diagnostic.code == "G4S015")
.map(|diagnostic| diagnostic.message.as_str())
.collect();
assert_eq!(
warnings,
[
"unsupported option value max_dfa_states=0: the value must be at least 1",
"unsupported option value max_k=many: 'many' is not a positive integer",
]
);
assert_eq!(
rule_budgets(&build, "s"),
[super::DecisionBudget::default()]
);
}
const FANOUT_GRAMMAR: &str = "grammar Fanout;
s : a EOF ;
a : A B X | A C X | A D X | A B Y | E ;
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; X : 'x' ; Y : 'y' ;
";
#[test]
fn state_caps_cut_hybrid_tables_instead_of_failing_them() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(4),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Fanout", FANOUT_GRAMMAR, AtnFallback::Allowed, &budgets);
let decision = &build.report.decisions[0];
assert_eq!(decision.rule, "a");
assert_eq!(decision.result.kind, DecisionKind::Hybrid);
assert_eq!(decision.result.budget_cutoff, Some(BudgetCutoff::States));
assert_eq!(decision.result.num_dfa_states, 3);
let (_, build) = build_source_with("Fanout", FANOUT_GRAMMAR, AtnFallback::Forbidden, &budgets);
let messages: Vec<_> = build
.diagnostics
.iter()
.map(|diagnostic| (diagnostic.code, diagnostic.message.as_str()))
.collect();
assert_eq!(
messages,
[(
"G4S192",
"decision 0 of rule 'a' applied heuristic resolution of escape states: \
1 undecided state predicts the minimum viable alternative (witness: 'a'); \
tie-breaks: 1 state chooses alt 1 (A B X, line 3) over alt 2 (A C X, line 3), \
alt 3 (A D X, line 3), alt 4 (A B Y, line 3) [prefix-hijack hazard: alt 2 \
(A C X, line 3) reads 'c' after 'a', and alt 1 cannot]; the analysis budget (4 \
states) stopped the lookahead; raise it with the max_dfa_states option of the \
grammar, the rule, or the block"
)]
);
let (_, build) = build_source_with(
"Fanout",
FANOUT_GRAMMAR,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
assert!(build.diagnostics.is_empty(), "{:?}", build.diagnostics);
}
#[test]
fn visit_budget_cutoff_reports_max_dfa_visits_in_g4s192() {
let source = "grammar VisitCutoff;\n\
options { max_dfa_visits = 60; }\n\
top : 'k' 'p' a0 'x' | 'k' 'p' a0 'y' | 'z' ;\n\
a0 : c0 ;\n\
c0 : c1 | c2 ; c1 : c3 | c4 ; c2 : c3 | c4 ;\n\
c3 : c5 | c6 ; c4 : c5 | c6 ; c5 : c7 | c8 ; c6 : c7 | c8 ;\n\
c7 : 'f' | 'g' ; c8 : 'h' | 'i' ;\n";
let (_, build) = build_source_with(
"VisitCutoff",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let decision = build
.report
.decisions
.iter()
.find(|entry| entry.rule == "top")
.expect("top decision");
assert_eq!(decision.result.kind, DecisionKind::Hybrid);
assert_eq!(decision.result.budget_cutoff, Some(BudgetCutoff::Visits));
let warning = build
.diagnostics
.iter()
.find(|diagnostic| diagnostic.code == "G4S192")
.expect("a G4S192 warning");
assert!(
warning.message.contains(
"the analysis budget (60 visited configs) stopped the lookahead; \
raise it with the max_dfa_visits option of the grammar, the rule, or the block"
),
"{}",
warning.message
);
}
#[test]
fn start_state_state_cap_reports_states_in_g4s190() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(2),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Fanout", FANOUT_GRAMMAR, AtnFallback::Forbidden, &budgets);
let decision = &build.report.decisions[0];
assert_eq!(
decision.result.no_table,
Some(NoTableReason::StartBudget(BudgetCutoff::States))
);
let error = build
.diagnostics
.iter()
.find(|diagnostic| diagnostic.code == "G4S190")
.expect("a G4S190 error");
assert!(
error
.message
.contains("the SLL DFA exceeded the analysis budget (2 states)"),
"{}",
error.message
);
}
const SPLIT_OPERATOR_GRAMMAR: &str = "grammar Split;
s : e EOF ;
e : e '+' 'q' 'a' | e '*' e | e '+' 'q' 'b' | 'x' ;
";
fn accept_after(table: &StaticDfaTable, tokens: &[i32]) -> Option<i32> {
let mut state = 0;
for token in tokens {
state = table.states[state]
.edges
.iter()
.find(|edge| edge.lo <= *token && *token <= edge.hi)?
.target;
}
Some(table.states[state].accept)
}
#[test]
fn frontier_iterates_need_every_exit_position_in_the_iterate_lineage() {
let accepts = split_operator_accepts("Split", SPLIT_OPERATOR_GRAMMAR, 4);
assert_eq!(accepts.len(), 4, "the cutoffs are 2, 3, and 4");
assert_eq!(accepts[2], Some(super::ESCAPE), "{accepts:?}");
}
fn split_operator_accepts(name: &str, source: &str, max_states: usize) -> Vec<Option<i32>> {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(max_states),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with(name, source, AtnFallback::Allowed, &budgets);
let token = |name: &str| {
build
.report
.vocabulary
.iter()
.position(|display| display == name)
.map(|index| index as i32 + 1)
.expect("token in vocabulary")
};
let path = [token("'+'"), token("'q'")];
let decision = build
.report
.decisions
.iter()
.find(|decision| decision.result.is_precedence_loop())
.expect("a precedence loop decision");
let precedence = decision.result.precedence.as_ref().expect("classes");
precedence
.tables
.iter()
.map(|table| table.as_ref().and_then(|table| accept_after(table, &path)))
.collect()
}
#[test]
fn frontier_iterate_guards_need_every_loop_exit_in_the_iterate_lineage() {
let source = "grammar SplitGuard;
s : e EOF | 'between' e '+' 'q' 'z' ;
e : e '+' 'q' 'a' | e '*' e | e '+' 'q' 'b' | 'x' ;
";
let accepts = split_operator_accepts("SplitGuard", source, 4);
assert_eq!(accepts[2], Some(super::ESCAPE), "{accepts:?}");
}
#[test]
fn nested_blocks_inherit_the_budget_options_of_outer_blocks() {
let source = "grammar Nested;
options { k = 2; }
s : ( options { max_k = 5; max_dfa_visits = 7000; } :
( options { max_k = 6; } : A B | A C ) D
| E
) EOF ;
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ;
";
let (diagnostics, build) = build_source_with(
"Nested",
source,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
assert!(
diagnostics
.iter()
.any(|diagnostic| diagnostic.code == "G4S014"
&& diagnostic.message == "unsupported option k"),
"{diagnostics:?}"
);
let limits: Vec<_> = rule_budgets(&build, "s")
.iter()
.map(|budget| (budget.max_k, budget.max_visits))
.collect();
assert_eq!(limits, [(Some(6), 7_000), (Some(5), 7_000)]);
}
#[test]
fn lexer_grammars_do_not_support_budget_options() {
let directory =
std::env::temp_dir().join(format!("dbt-antlr-budget-lexer-{}", std::process::id()));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join("Words.g4");
std::fs::write(
&path,
"lexer grammar Words;\noptions { max_k = 2; }\nA options { max_k = 3; } : 'a' | 'b' ;\n",
)
.expect("scratch grammar");
let compilation = compile(LoadOptions {
roots: vec![path],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let _ = std::fs::remove_dir_all(&directory);
let unsupported = compilation
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.message == "unsupported option max_k")
.count();
assert_eq!(unsupported, 2, "{:?}", compilation.diagnostics);
}
#[test]
fn single_alternative_accepts_share_one_state() {
let source = "grammar Sinks;
s : a EOF ;
a : ( A B | C D | E F ) X | A G Y ;
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; F : 'f' ; G : 'g' ; X : 'x' ; Y : 'y' ;
";
let results = outcomes_of_source("Sinks", source);
let decision = results
.iter()
.find(|result| result.table.is_some() && result.k == 2)
.expect("the LL(2) decision of `a`");
let table = decision.table.as_ref().expect("table");
let accepts: Vec<_> = table
.states
.iter()
.filter(|state| state.is_accept())
.map(|state| state.accept)
.collect();
assert_eq!(accepts, [1, 2], "{table:?}");
let first_alt = table
.states
.iter()
.position(|state| state.accept == 1)
.expect("an accept of alternative 1");
let into_first_alt = table
.states
.iter()
.flat_map(|state| &state.edges)
.filter(|edge| edge.target == first_alt)
.count();
assert_eq!(into_first_alt, 3, "`a b`, `c`, and `e` lead to one state");
}
#[test]
fn shared_accept_states_do_not_absorb_predicated_paths() {
for order in ["Y W X", "X Y W", "X W Y", "W Y X"] {
let mut source = String::from(
"grammar Order;\ns : a EOF ;\na : P ( Y | W Q | X {false}? ) B | P Z ;\nP : 'p' ;\n",
);
for token in order.split(' ') {
source.push_str(&format!("{token} : '{}' ;\n", token.to_lowercase()));
}
source.push_str("Q : 'q' ; B : 'b' ; Z : 'z' ;\n");
let results = resolve_static_only_source("Order", &source);
let decision = results
.iter()
.find(|result| result.table.is_some() && result.k >= 2)
.unwrap_or_else(|| panic!("{order}: the decision of `a`"));
let table = decision.table.as_ref().expect("table");
let token = |name: char| {
2 + order
.split(' ')
.position(|token| token.starts_with(name))
.expect("token") as i32
};
let after = |second: i32| accept_after(table, &[1, second]);
assert_eq!(after(token('Y')), Some(1), "{order}: `p y` predicts 1");
assert_eq!(after(token('W')), Some(1), "{order}: `p w` predicts 1");
let x = table.states[0]
.edges
.iter()
.find(|edge| edge.lo <= 1 && 1 <= edge.hi)
.map(|edge| &table.states[edge.target])
.and_then(|state| {
state
.edges
.iter()
.find(|edge| edge.lo <= token('X') && token('X') <= edge.hi)
})
.map(|edge| &table.states[edge.target])
.expect("an edge for `p x`");
assert_eq!(
x.resolution,
Some(super::EscapeResolution::SyntaxError),
"{order}: `p x` stops at the predicate"
);
}
}
fn resolve_static_only_source(name: &str, source: &str) -> Vec<DecisionOutcome> {
static SCRATCH: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
let scratch = SCRATCH.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let directory = std::env::temp_dir().join(format!(
"dbt-antlr-static-only-{}-{scratch}-{name}",
std::process::id()
));
std::fs::create_dir_all(&directory).expect("scratch directory");
let path = directory.join(format!("{name}.g4"));
std::fs::write(&path, source).expect("scratch grammar");
let results = resolve_static_only(&path);
let _ = std::fs::remove_dir_all(&directory);
results
}
fn assert_runtime_equivalent(table: &StaticDfaTable, minimized: &StaticDfaTable) {
let outcome = |state: &StaticDfaState| {
let accept = if state.accept == CONFLICT_ESCAPE && state.conflict_min_alt <= 0 {
super::ESCAPE
} else {
state.accept
};
(
accept,
if accept == 0 { state.fallback } else { 0 },
if accept == CONFLICT_ESCAPE {
state.conflict_min_alt
} else {
0
},
state.guarded_alt,
if state.resolution == Some(super::EscapeResolution::Guarded) {
state.guard_defer_alt
} else {
0
},
state.guard_group,
state
.continuation
.as_ref()
.filter(|_| accept == super::ESCAPE)
.map(|continuation| (continuation.contexts.clone(), continuation.configs.clone())),
)
};
let target = |state: &StaticDfaState, token: i32| {
state
.edges
.iter()
.find(|edge| edge.lo <= token && token <= edge.hi)
.map(|edge| edge.target)
};
let mut tokens: Vec<i32> = table
.states
.iter()
.chain(&minimized.states)
.flat_map(|state| &state.edges)
.flat_map(|edge| [edge.lo - 1, edge.lo, edge.hi, edge.hi + 1])
.collect();
tokens.sort_unstable();
tokens.dedup();
let mut seen = std::collections::HashSet::new();
let mut queue = std::collections::VecDeque::from([(0_usize, 0_usize)]);
while let Some((left, right)) = queue.pop_front() {
if !seen.insert((left, right)) {
continue;
}
let (left_state, right_state) = (&table.states[left], &minimized.states[right]);
assert_eq!(
outcome(left_state),
outcome(right_state),
"states {left} and {right}"
);
if left_state.accept != 0 {
continue;
}
for &token in &tokens {
match (target(left_state, token), target(right_state, token)) {
(Some(left), Some(right)) => queue.push_back((left, right)),
(None, None) => {}
pair => panic!("token {token} from {left}/{right}: {pair:?}"),
}
}
}
}
#[test]
fn runtime_tables_are_minimized_and_equivalent() {
let mut merged = 0;
for (grammar, fallback) in [
("parser/FuzzExpr.g4", AtnFallback::Allowed),
("parser/LoopFrontier.g4", AtnFallback::Allowed),
("parser/GuardExpr.g4", AtnFallback::Forbidden),
("parser/InlineAlias.g4", AtnFallback::Forbidden),
] {
let path = grammars_dir().join(grammar);
let results = match fallback {
AtnFallback::Allowed => outcomes(&path),
AtnFallback::Forbidden => resolve_static_only(&path),
};
for result in &results {
let tables = result.table.iter().chain(
result
.precedence
.iter()
.flat_map(|precedence| precedence.tables.iter().flatten()),
);
for table in tables {
let minimized = super::tables::minimized(table);
assert!(minimized.states.len() <= table.states.len());
merged += table.states.len() - minimized.states.len();
assert_runtime_equivalent(table, &minimized);
}
}
decoded_tables(&results);
}
assert!(merged > 0, "some states merge");
}
fn names_of(name: &str, source: &str) -> Vec<(String, Vec<String>)> {
let (_, build) = build_source_with(
name,
source,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
build
.report
.decisions
.iter()
.map(|decision| (decision.rule.clone(), decision.alternatives.all().to_vec()))
.collect()
}
#[test]
fn decisions_name_their_alternatives() {
let source = "grammar Names;
s : e (COMMA e)* COMMA? EOF ;
e : e STAR e #mul
| e PLUS e #add
| p #prim
;
p : ID LP e RP OVER LP RP
| ID LP e RP
| ( ID | INT ) ( DOT ID )?
;
COMMA : ',' ; STAR : '*' ; PLUS : '+' ; ID : [a-z]+ ; INT : [0-9]+ ; LP : '(' ; RP : ')' ;
OVER : 'over' ; DOT : '.' ;
";
let names = names_of("Names", source);
let find = |rule: &str, first: &str| {
names
.iter()
.find(|(owner, alternatives)| {
owner == rule
&& alternatives
.first()
.is_some_and(|name| name.starts_with(first))
})
.map_or_else(
|| panic!("no decision of {rule} starts with {first}: {names:?}"),
|(_, alternatives)| alternatives.clone(),
)
};
assert_eq!(
find("s", "alt 1 (repeat"),
["alt 1 (repeat COMMA e, line 2)", "alt 2 (exit the loop)"]
);
assert_eq!(
find("s", "alt 1 (COMMA,"),
["alt 1 (COMMA, line 2)", "alt 2 (skip)"]
);
assert_eq!(
find("e", "alt 1 (#mul"),
["alt 1 (#mul, line 3)", "alt 2 (#add, line 4)"]
);
assert_eq!(
find("p", "alt 1 (ID LP e ..."),
[
"alt 1 (ID LP e ..., line 7)",
"alt 2 (ID LP e ..., line 8)",
"alt 3 ((ID | INT) ( ... )?, line 9)",
]
);
assert_eq!(
find("p", "alt 1 (DOT ID"),
["alt 1 (DOT ID, line 9)", "alt 2 (skip the block)"]
);
assert_eq!(
find("e", "alt 1 (repeat ( #mul"),
[
"alt 1 (repeat ( #mul | #add ), line 3)",
"alt 2 (exit the loop)"
]
);
}
#[test]
fn static_only_groups_its_tie_breaks() {
let mut results = resolve_static_only(&grammars_dir().join("parser").join("GuardExpr.g4"));
results.extend(resolve_static_only(
&grammars_dir().join("ReferenceToATN.g4"),
));
results.extend(resolve_static_only(
&grammars_dir().join("parser").join("LoopFrontier.g4"),
));
for result in &results {
let Some(resolved) = &result.static_only else {
continue;
};
let grouped: usize = resolved.tie_breaks.iter().map(|group| group.states).sum();
assert_eq!(grouped, resolved.min_alt + resolved.min_viable_alt);
for pair in resolved.tie_breaks.windows(2) {
assert!(
(pair[0].level(), pair[0].states) >= (pair[1].level(), pair[1].states),
"{:?}",
resolved.tie_breaks
);
assert_ne!(
(pair[0].chosen, &pair[0].dropped),
(pair[1].chosen, &pair[1].dropped)
);
}
for group in &resolved.tie_breaks {
assert!(!group.dropped.is_empty());
assert!(!group.dropped.contains(&group.chosen));
assert!(group.dropped.iter().all(|alt| *alt > 0));
assert!(group.witness.is_some());
}
}
assert!(
results.iter().any(|result| result
.static_only
.as_ref()
.is_some_and(|resolved| !resolved.tie_breaks.is_empty())),
"the grammars have tie-breaks"
);
}
#[test]
fn non_greedy_decisions_name_the_exit_first() {
let source = "grammar Lazy;
s : ID*? INT ( ID ID | INT INT )?? EOF ;
ID : [a-z]+ ; INT : [0-9]+ ;
";
let names = names_of("Lazy", source);
let alternatives: Vec<_> = names.iter().map(|(_, names)| names.clone()).collect();
assert!(
alternatives.contains(&vec![
"alt 1 (exit the loop)".to_owned(),
"alt 2 (repeat ID, line 2)".to_owned(),
]),
"{alternatives:?}"
);
assert!(
alternatives.contains(&vec![
"alt 1 (skip the block)".to_owned(),
"alt 2 (ID ID, line 2)".to_owned(),
"alt 3 (INT INT, line 2)".to_owned(),
]),
"{alternatives:?}"
);
}
const TIE_GRAMMAR: &str = "grammar Ties;
s : a EOF ;
a : X Y P | X Y Q | X Z P | X Z Q | W Y P | W Y Q | W Z P | W Z Q ;
X : 'x' ; Y : 'y' ; Z : 'z' ; W : 'w' ; P : 'p' ; Q : 'q' ;
";
#[test]
fn static_only_warnings_show_the_largest_tie_break_groups() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(8),
max_k: Some(2),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Ties", TIE_GRAMMAR, AtnFallback::Forbidden, &budgets);
let decision = &build.report.decisions[0];
let resolved = decision.result.static_only.as_ref().expect("resolved");
let groups: Vec<_> = resolved
.tie_breaks
.iter()
.map(|group| (group.chosen, group.dropped.clone(), group.states))
.collect();
assert_eq!(
groups,
[
(1, vec![2], 1),
(3, vec![4], 1),
(5, vec![6], 1),
(7, vec![8], 1)
]
);
let message = &build
.diagnostics
.iter()
.find(|diagnostic| diagnostic.code == "G4S192")
.expect("a G4S192 warning")
.message;
assert!(
message.contains(
"tie-breaks: 1 state chooses alt 1 (X Y P, line 3) over alt 2 (X Y Q, line 3) \
[prefix-hijack hazard: alt 2 (X Y Q, line 3) reads 'q' after 'x' 'y', and alt 1 \
cannot]; 1 state chooses alt 3 (X Z P, line 3) over alt 4 (X Z Q, line 3) \
[prefix-hijack hazard: alt 4 (X Z Q, line 3) reads 'q' after 'x' 'z', and alt 3 \
cannot]; 1 state chooses alt 5 (W Y P, line 3) over alt 6 (W Y Q, line 3) \
[prefix-hijack hazard: alt 6 (W Y Q, line 3) reads 'q' after 'w' 'y', and alt 5 \
cannot]; and 1 more tie-break group"
),
"{message}"
);
}
#[test]
fn only_static_dfa_only_reports_decisions_without_a_static_prediction() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(12),
max_k: Some(2),
..BudgetLimits::default()
},
};
let source = TIE_GRAMMAR
.replace("W Z Q ;", "W Z Q | E ;")
.replace("Q : 'q' ;", "Q : 'q' ; E : 'e' ;");
let (_, build) = build_source_with("Ties", &source, AtnFallback::Allowed, &budgets);
assert!(
build
.report
.decisions
.iter()
.any(|decision| decision.result.kind == DecisionKind::Hybrid
&& decision.result.escapes > 0),
"{:?}",
build.report.decisions
);
assert!(
build
.diagnostics
.iter()
.all(|diagnostic| diagnostic.code != "G4S190"),
"{:?}",
build.diagnostics
);
let source = "grammar PredStart;\ns : r EOF ;\nr : {p()}? A | A B ;\nA : 'a' ; B : 'b' ;\n";
let (_, build) = build_source_with(
"PredStart",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let errors: Vec<_> = build
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.code == "G4S190")
.map(|diagnostic| (diagnostic.severity, diagnostic.message.as_str()))
.collect();
assert_eq!(
errors,
[(
Severity::Error,
"parser decision 0 of rule 'r' is not fully static: the decision depends on \
predicate 1:0, so the prediction is not input-only; --static-dfa-only requires a \
static table for every decision"
)]
);
}
#[test]
fn optional_elements_and_long_lists_have_short_names() {
let source = "grammar Short;
s : A?? (B | C | D | E | F | G) EOF ;
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; F : 'f' ; G : 'g' ;
";
let (_, build) = build_source_with(
"Short",
source,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
let lazy = build
.report
.decisions
.iter()
.find(|decision| decision.alternatives.all().len() == 2)
.expect("the decision of `A??`");
assert_eq!(
lazy.alternatives.all(),
["alt 1 (skip)", "alt 2 (A, line 2)"]
);
assert_eq!(
lazy.alternatives.list(&[1, 2, 1, 2, 1, 2]),
"alt 1 (skip), alt 2 (A, line 2), alt 1 (skip), alt 2 (A, line 2), \
and 2 more alternatives"
);
assert_eq!(
lazy.alternatives.list(&[1, 2, 1, 2, 1]),
"alt 1 (skip), alt 2 (A, line 2), alt 1 (skip), alt 2 (A, line 2), \
and 1 more alternative"
);
}
fn hazards_of(name: &str, source: &str, rule: &str, max_k: usize) -> Vec<(i32, Vec<i32>, String)> {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_k: Some(max_k),
max_states: Some(3),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with(name, source, AtnFallback::Forbidden, &budgets);
build
.report
.decisions
.iter()
.filter(|decision| decision.rule == rule)
.filter_map(|decision| decision.result.static_only.as_ref())
.flat_map(|resolved| resolved.tie_breaks.iter())
.map(|group| {
let verdict = match &group.hazard {
Some(hazard) => format!("{:?} {:?}", hazard.level, hazard.verdict),
None => "none".to_owned(),
};
(group.chosen, group.dropped.clone(), verdict)
})
.collect()
}
const SUBQUERY_GRAMMAR: &str = "grammar Sub;
s : e EOF ;
e : LP q RP #sub | LP e (COMMA e)* RP #tuple | INT #lit ;
q : SELECT INT | LP q RP ;
LP : '(' ; RP : ')' ; COMMA : ',' ; SELECT : 'select' ; INT : [0-9]+ ;
";
#[test]
fn narrow_alternatives_before_broad_ones_are_prefix_hijacks() {
assert_eq!(
hazards_of("Sub", SUBQUERY_GRAMMAR, "e", 2),
[(
1,
vec![2],
"High Hijack { alt: 2, extension: [1, 5] }".to_owned()
)]
);
let index = "grammar Index;
s : el EOF ;
el : identifier dtype #col | INDEX identifier TYPE identifier GRANULARITY INT #idx ;
identifier : ID | INDEX | TYPE ;
dtype : ID ;
INDEX : 'index' ; TYPE : 'type' ; GRANULARITY : 'granularity' ; INT : [0-9]+ ; ID : [a-z]+ ;
";
assert_eq!(
hazards_of("Index", index, "el", 2),
[(
1,
vec![2],
"High Hijack { alt: 2, extension: [1, 1] }".to_owned()
)]
);
}
#[test]
fn greedy_choices_and_exact_ambiguities_rank_lower() {
let comma = "grammar Comma;
s : list FROM id EOF ;
list : id (COMMA id)* COMMA? ;
id : ID | FROM ;
FROM : 'from' ; COMMA : ',' ; ID : [a-z]+ ;
";
assert_eq!(
hazards_of("Comma", comma, "list", 1),
[(
1,
vec![2],
"Medium Hijack { alt: 2, extension: [2, 1, 3] }".to_owned()
)]
);
let ambiguous = "grammar Ambig;
s : a EOF ;
a : X Y Z | X Y Z ;
X : 'x' ; Y : 'y' ; Z : 'z' ;
";
assert_eq!(
hazards_of("Ambig", ambiguous, "a", 1),
[(1, vec![2], "Low Covered".to_owned())]
);
}
#[test]
fn static_only_warnings_show_the_hijack_hazards() {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_k: Some(2),
max_states: Some(3),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Sub", SUBQUERY_GRAMMAR, AtnFallback::Forbidden, &budgets);
let message = &build
.diagnostics
.iter()
.find(|diagnostic| diagnostic.code == "G4S192")
.expect("a G4S192 warning")
.message;
assert!(
message.contains(
"chooses alt 1 (#sub, line 3) over alt 2 (#tuple, line 3) [prefix-hijack hazard: \
alt 2 (#tuple, line 3) reads INT after '(', and alt 1 cannot]"
),
"{message}"
);
}
const CALLERS_GRAMMAR: &str = "grammar Callers;
prog : stmt+ EOF ;
stmt : 'set' expr '=' expr ';'
| 'let' expr '=' expr ';'
| assign
| update
| expr ';'
;
assign : 'var' expr '=' expr ';' ;
update : 'put' expr '=' expr ';' ;
expr : value pred? ;
pred : '=' value ;
value : ID | '(' expr ')' ;
ID : [a-z]+ ;
WS : [ \\t\\n]+ -> skip ;
";
#[test]
fn guard_danger_sets_name_their_callers() {
let (_, build) = build_source_with(
"Callers",
CALLERS_GRAMMAR,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let message = &build
.diagnostics
.iter()
.find(|diagnostic| diagnostic.code == "G4S192")
.expect("a G4S192 warning")
.message;
assert!(
message.contains(
"the stack guard defers (witness: '=' ID ';'; danger callers: stmt:3, stmt:4, \
assign:9 and 1 more danger caller)"
),
"{message}"
);
let (dump, diagnostics) = crate::optimization::StaticParserDfa::render_dfa_dump(
std::slice::from_ref(&build.report),
"expr",
);
assert!(diagnostics.is_empty(), "{diagnostics:?}");
let danger = "danger=[22 (stmt:3), 28 (stmt:4), 41 (assign:9), 47 (update:10)]";
assert!(dump.contains(&format!("group 0: {danger}\n")), "{dump}");
assert!(
dump.contains(&format!("guard root of group 0 ({danger})")),
"{dump}"
);
}
#[test]
fn tie_breaks_rank_by_hazard() {
let source = "grammar Rank;
s : a EOF ;
a : X Y Z | X Y Z | W Y P | W Y Q ;
X : 'x' ; Y : 'y' ; Z : 'z' ; W : 'w' ; P : 'p' ; Q : 'q' ;
";
let groups: Vec<_> = hazards_of("Rank", source, "a", 2)
.into_iter()
.map(|(chosen, dropped, verdict)| {
(
chosen,
dropped,
verdict.split(' ').next().map(str::to_owned),
)
})
.collect();
assert_eq!(
groups,
[
(3, vec![4], Some("High".to_owned())),
(1, vec![2], Some("Low".to_owned())),
]
);
}
#[test]
fn widened_paths_are_no_hijack_evidence() {
let source = "grammar Widened;
s : target EOF ;
target : A LP expr RP X | A parens X ;
expr : LP expr RP | ID ;
parens : LP parens RP | ID ;
A : 'a' ; LP : '(' ; RP : ')' ; X : 'x' ; ID : [a-z]+ ;
";
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(4),
max_k: Some(2),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Widened", source, AtnFallback::Forbidden, &budgets);
let groups: Vec<_> = build
.report
.decisions
.iter()
.filter_map(|decision| decision.result.static_only.as_ref())
.flat_map(|resolved| &resolved.tie_breaks)
.collect();
assert!(!groups.is_empty());
assert!(
groups
.iter()
.all(|group| group.level() != super::HazardLevel::High),
"{groups:?}"
);
}
#[test]
fn partially_analyzed_groups_are_not_covered() {
let source = "grammar Partial;
s : r EOF ;
r : (A X Y W | B X Y W | C X Y W | D X Y W | P X Q) #one
| (A X Y W | B X Y W | C X Y W | D X Y W | P X Z) #two
;
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; P : 'p' ; Q : 'q' ; W : 'w' ; X : 'x' ; Y : 'y' ;
Z : 'z' ;
";
for states in [9, 12] {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(states),
..BudgetLimits::default()
},
};
let (_, build) = build_source_with("Partial", source, AtnFallback::Forbidden, &budgets);
let groups: Vec<_> = build
.report
.decisions
.iter()
.filter_map(|decision| decision.result.static_only.as_ref())
.flat_map(|resolved| &resolved.tie_breaks)
.collect();
assert!(!groups.is_empty());
for group in groups {
let hazard = group.hazard.as_ref().expect("analyzed");
assert_ne!(
hazard.verdict,
super::HijackVerdict::Covered,
"{states}: {group:?}"
);
}
}
}
#[test]
fn unsure_chosen_paths_do_not_cover() {
for (name, source) in [
(
"Boundary",
"grammar Boundary;
s : r EOF ;
r : A | (X r | A) B ;
A : 'a' ; B : 'b' ; X : 'x' ;
",
),
(
"PredChosen",
"grammar PredChosen;
s : r EOF ;
r : A X {false}? B | A X B ;
A : 'a' ; B : 'b' ; X : 'x' ;
",
),
] {
let groups = hazards_of(name, source, "r", 1);
assert!(!groups.is_empty(), "{name}");
for (_, _, verdict) in groups {
assert!(!verdict.contains("Covered"), "{name}: {verdict}");
}
}
}
fn guard_hazards_of(
name: &str,
source: &str,
rule: &str,
max_k: Option<usize>,
) -> (
Vec<(Vec<i32>, String)>,
crate::optimization::static_parser_dfa::StaticParserDfaArtifact,
) {
let budgets = ParserDfaBudgets {
global: BudgetLimits {
max_k,
..BudgetLimits::default()
},
};
let (_, build) = build_source_with(name, source, AtnFallback::Forbidden, &budgets);
let groups = build
.report
.decisions
.iter()
.filter(|decision| decision.rule == rule)
.filter_map(|decision| decision.result.static_only.as_ref())
.flat_map(|resolved| resolved.guard_groups.iter())
.map(|group| (group.danger.clone(), format!("{:?}", group.hazard)))
.collect();
(groups, build)
}
fn static_only_warning(
build: &crate::optimization::static_parser_dfa::StaticParserDfaArtifact,
rule: &str,
) -> String {
build
.diagnostics
.iter()
.find(|diagnostic| {
diagnostic.code == "G4S192" && diagnostic.message.contains(&format!("of rule '{rule}'"))
})
.map_or_else(
|| panic!("a G4S192 warning for '{rule}': {:?}", build.diagnostics),
|diagnostic| diagnostic.message.clone(),
)
}
const SETTINGS_GRAMMAR: &str = "grammar Settings;
command : query settings? ';' ;
query : select ('UNION' 'ALL' select)* ;
select : 'SELECT' expr settings? ;
settings : 'SETTINGS' ID '=' INT (',' ID '=' INT)* ;
expr : ID | INT ;
ID : [a-z]+ ; INT : [0-9]+ ; WS : [ ]+ -> skip ;
";
#[test]
fn outer_wrapper_guards_are_stack_hijacks() {
let (groups, build) = guard_hazards_of("Settings", SETTINGS_GRAMMAR, "select", Some(4));
let [(danger, verdict)] = groups.as_slice() else {
panic!("one guard group: {groups:?}");
};
assert_eq!(danger.len(), 1, "{groups:?}");
let caller = danger[0];
assert_eq!(
*verdict,
format!("Some(Hijack {{ caller: {caller}, extension: [5, 8, 6, 9, 2] }})")
);
let warning = static_only_warning(&build, "select");
assert!(
warning.ends_with(
"(witness: 'SETTINGS' ID '=' INT; danger caller: command:2) [stack-hijack hazard: \
when called from 'command' (line 2), defers 'SETTINGS' ID '=' INT even when \
followed by 'UNION']"
),
"{warning}"
);
let (dump, diagnostics) = crate::optimization::StaticParserDfa::render_dfa_dump(
std::slice::from_ref(&build.report),
"select",
);
assert!(diagnostics.is_empty(), "{diagnostics:?}");
assert!(
dump.contains(&format!(
"group 0: danger=[{caller} (command:2)] [stack-hijack hazard: when called from \
'command' (line 2), defers 'SETTINGS' ID '=' INT even when followed by 'UNION']\n"
)),
"{dump}"
);
let (groups, build) = guard_hazards_of("Settings", SETTINGS_GRAMMAR, "select", Some(8));
assert_eq!(groups, [(danger.clone(), "Some(Covered)".to_owned())]);
let warning = static_only_warning(&build, "select");
assert!(warning.ends_with(" [benign stack guard]"), "{warning}");
let (dump, _) = crate::optimization::StaticParserDfa::render_dfa_dump(
std::slice::from_ref(&build.report),
"select",
);
assert!(
dump.contains(&format!("group 0: danger=[{caller} (command:2)]\n")),
"a benign group has no note: {dump}"
);
}
#[test]
fn interval_units_are_stack_hijacks() {
let rules = [
(
"unary",
"column : add alias? ;
add : unary ('+' unary)* ;
unary : 'INTERVAL' STR unit? | 'CAST' '(' column 'AS' ID ')' | ID | INT ;",
),
(
"expr",
"column : expr alias? ;
expr : expr '+' expr | 'INTERVAL' STR unit? | 'CAST' '(' column 'AS' ID ')' | ID | INT ;",
),
];
for (rule, rules) in rules {
let source = format!(
"grammar Interval;
stmt : 'SELECT' column ('+' INT)? EOF ;
{rules}
unit : 'DAY' | 'HOUR' ;
alias : ID | 'DAY' ;
ID : [a-z]+ ; INT : [0-9]+ ; STR : '\\'' [0-9]+ '\\'' ; WS : [ ]+ -> skip ;
"
);
let (groups, build) = guard_hazards_of("Interval", &source, rule, Some(3));
assert!(
groups
.iter()
.any(|(_, verdict)| verdict.contains("extension: [8, 2, 11, 2]")),
"{rule}: {groups:?}"
);
let warning = static_only_warning(&build, rule);
assert!(
warning.contains(
"[stack-hijack hazard: when called from 'column' (line 3), defers 'DAY' '+' INT \
even when followed by '+']"
),
"{rule}: {warning}"
);
if rule == "expr" {
assert!(
groups.iter().any(|(_, verdict)| verdict == "Some(Covered)"),
"{groups:?}"
);
}
}
}
#[test]
fn direct_danger_callers_are_benign_guards() {
let (groups, build) = guard_hazards_of("Callers", CALLERS_GRAMMAR, "expr", None);
assert!(!groups.is_empty());
for (danger, verdict) in &groups {
assert_eq!(verdict, "Some(Covered)", "{danger:?}");
}
let warning = static_only_warning(&build, "expr");
assert!(warning.ends_with(" [benign stack guard]"), "{warning}");
}
#[test]
fn reexpansion_respects_state_cap_and_prunes_unreachable_states_on_visit_cutoff() {
let source = "grammar ReexpandBudget;\n\
top : ( r | r1 )? q X | r? q Y ;\n\
r : '(' r ')' | B ;\n\
r1 : '(' r1 ')' | B Z ;\n\
q : K ( M1 M2 | N1 N2 ) ;\n\
B : 'b' ; K : 'k' ; M1 : 'm1' ; M2 : 'm2' ; N1 : 'n1' ; N2 : 'n2' ; X : 'x' ; Y : 'y' ; Z : 'z' ;\n";
let build_with = |budgets: &ParserDfaBudgets| {
build_source_with("ReexpandBudget", source, AtnFallback::Allowed, budgets).1
};
let full = build_with(&ParserDfaBudgets::default());
let decision = full
.report
.decisions
.iter()
.rposition(|entry| entry.rule == "top" && entry.result.table.is_some())
.expect("top decision has a table");
let full_outcome = &full.report.decisions[decision].result;
let full_table = full_outcome.table.as_ref().expect("full table");
let exact_states = full_table.states.len();
assert_eq!(full_outcome.budget_cutoff, None);
assert!(full_table.depths().iter().all(|&depth| depth != usize::MAX));
let capped = build_with(&ParserDfaBudgets {
global: BudgetLimits {
max_states: Some(exact_states + 1),
max_k: None,
max_visits: None,
},
});
let capped_outcome = &capped.report.decisions[decision].result;
let capped_table = capped_outcome.table.as_ref().expect("capped table");
assert_eq!(capped_outcome.budget_cutoff, None);
assert_eq!(capped_table.states.len(), exact_states);
assert!(
capped_table
.depths()
.iter()
.all(|&depth| depth != usize::MAX)
);
let mut saw_pruned = false;
for visits in 1..full_outcome.cost.visits() {
let limited = build_with(&ParserDfaBudgets {
global: BudgetLimits {
max_states: None,
max_k: None,
max_visits: Some(visits),
},
});
let outcome = &limited.report.decisions[decision].result;
if let Some(table) = &outcome.table {
assert_eq!(outcome.num_dfa_states, table.states.len());
assert!(
table.depths().iter().all(|&depth| depth != usize::MAX),
"visits={visits} emitted unreachable state(s): {:#?}",
table.states
);
if outcome.budget_cutoff == Some(BudgetCutoff::Visits)
&& table.states.len() < exact_states
{
saw_pruned = true;
}
}
}
assert!(
saw_pruned,
"visit-budget sweep should exercise post-cutoff pruning"
);
}
#[test]
fn state_budget_cutoff_without_escape_widens_to_static() {
let source = "grammar WidenStatic;\n\
options { max_dfa_states = 8; }\n\
top : r1 | r2 ;\n\
r1 : '(' r1 ')' | A X ;\n\
r2 : '(' r2 ')' | A Y ;\n\
A : 'a' ; X : 'x' ; Y : 'y' ;\n";
for (atn_fallback, first_attempt) in [
(AtnFallback::Allowed, AttemptKind::Default),
(AtnFallback::Forbidden, AttemptKind::StaticOnly),
] {
let (_, build) = build_source_with(
"WidenStatic",
source,
atn_fallback,
&ParserDfaBudgets::default(),
);
let decision = build
.report
.decisions
.iter()
.find(|entry| entry.rule == "top")
.expect("top decision");
assert_eq!(
decision.result.kind,
DecisionKind::Static,
"{atn_fallback:?}"
);
assert_eq!(decision.result.escapes, 0, "{atn_fallback:?}");
assert_eq!(decision.result.guarded_states(), 0, "{atn_fallback:?}");
assert_eq!(
decision
.result
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[first_attempt, AttemptKind::Widened],
"{atn_fallback:?}"
);
}
}
#[test]
fn budget_cutoff_after_non_budget_escape_skips_widening() {
let source = "grammar EscapeBeforeCutoff;\n\
options { max_dfa_states = 8; }\n\
top : A {true}? B | A C | D E1 E2 E3 ( F1 | F2 ) X | D E1 E2 E3 ( F1 | F2 ) Y ;\n\
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ;\n\
E1 : 'e1' ; E2 : 'e2' ; E3 : 'e3' ; F1 : 'f1' ; F2 : 'f2' ;\n\
X : 'x' ; Y : 'y' ;\n";
let (_, build) = build_source_with(
"EscapeBeforeCutoff",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let decision = &build.report.decisions[0].result;
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert_eq!(decision.budget_cutoff, Some(BudgetCutoff::States));
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[AttemptKind::StaticOnly]
);
}
#[test]
fn widened_false_conflict_keeps_default_partial_table() {
let path = grammars_dir().join("parser").join("WidenedTrust.g4");
let compilation = compile(LoadOptions {
roots: vec![path],
library_directories: Vec::new(),
})
.expect("grammar compiles");
let parser = compilation
.parser(compilation.roots[0].parser.expect("parser root"))
.expect("parser artifact");
let budgets = vec![
super::DecisionBudget::default(),
super::DecisionBudget {
max_states: 50,
explicit_max_states: true,
..super::DecisionBudget::default()
},
];
let results = builder(parser)
.with_atn_fallback(AtnFallback::Forbidden)
.with_budgets(budgets)
.build_all();
let decision = &results[1];
assert_eq!(
attempts_of(&results, 1),
[AttemptKind::StaticOnly, AttemptKind::Widened]
);
assert_eq!(decision.kind, DecisionKind::Hybrid);
let table = decision.table.as_ref().expect("partial table kept");
assert!(
table.states.iter().all(|state| state.conflicts.is_empty()),
"widened false conflict must not replace default table"
);
}
#[test]
fn frontier_bounds_late_escapes_and_conflict_free_static_only_cutoffs() {
let late_default = "grammar LateDefault;\n\
top : A B C D E F {true}? G X | A B C D E F G Y | Z ;\n\
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; F : 'f' ;\n\
G : 'g' ; X : 'x' ; Y : 'y' ; Z : 'z' ;\n";
let (_, build) = build_source_with(
"LateDefault",
late_default,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
let decision = &build.report.decisions[0].result;
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert!(decision.k <= PARTIAL_DEPTH_CAP as i32);
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[AttemptKind::Default, AttemptKind::Default]
);
let late_static_only = "grammar LateStaticOnly;\n\
top : T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 T14 T15 T16 T17 T18 {true}? A X\n\
| T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 T14 T15 T16 T17 T18 A Y ;\n\
T1 : 't1' ; T2 : 't2' ; T3 : 't3' ; T4 : 't4' ; T5 : 't5' ; T6 : 't6' ;\n\
T7 : 't7' ; T8 : 't8' ; T9 : 't9' ; T10 : 't10' ; T11 : 't11' ; T12 : 't12' ;\n\
T13 : 't13' ; T14 : 't14' ; T15 : 't15' ; T16 : 't16' ; T17 : 't17' ; T18 : 't18' ;\n\
A : 'a' ; X : 'x' ; Y : 'y' ;\n";
let (_, build) = build_source_with(
"LateStaticOnly",
late_static_only,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let decision = &build.report.decisions[0].result;
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert!(decision.k <= STATIC_ONLY_DEPTH_CAP as i32);
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[AttemptKind::StaticOnly, AttemptKind::StaticOnly]
);
let deep_static_cutoff = "grammar DeepStaticOnlyCutoff;\n\
options { max_dfa_states = 18; }\n\
top : P P P P P P P P P P P P P P P P P P P P A X\n\
| P P P P P P P P P P P P P P P P P P P P A Y ;\n\
A : 'a' ; P : 'p' ; X : 'x' ; Y : 'y' ;\n";
let (_, build) = build_source_with(
"DeepStaticOnlyCutoff",
deep_static_cutoff,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let decision = &build.report.decisions[0].result;
assert_eq!(decision.kind, DecisionKind::Hybrid);
assert!(decision.k <= STATIC_ONLY_DEPTH_CAP as i32);
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[
AttemptKind::StaticOnly,
AttemptKind::Widened,
AttemptKind::StaticOnly,
]
);
}
#[test]
fn start_exhausted_widened_exceeding_frontier_retries_bounded_with_hazards() {
let source = "grammar StartExhaustedBounded;\n\
options { max_dfa_visits = 350; }\n\
entry : top 'u' | top 'v' ;\n\
top : H P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15 P16 P17 P18 tail\n\
| H P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15 P16 P17 P18 tail\n\
| a0 'z' ;\n\
a0 : c0 ; tail : 'a' ;\n\
c0 : c1 | c2 ; c1 : c3 | c4 ; c2 : c3 | c4 ;\n\
c3 : c5 | c6 ; c4 : c5 | c6 ; c5 : c7 | c8 ; c6 : c7 | c8 ;\n\
c7 : c9 | c10 ; c8 : c9 | c10 ; c9 : c11 | c12 ; c10 : c11 | c12 ;\n\
c11 : c13 | c14 ; c12 : c13 | c14 ; c13 : 'f' ; c14 : 'g' ;\n\
H : 'h' ;\n\
P1 : 'p1' ; P2 : 'p2' ; P3 : 'p3' ; P4 : 'p4' ; P5 : 'p5' ; P6 : 'p6' ;\n\
P7 : 'p7' ; P8 : 'p8' ; P9 : 'p9' ; P10 : 'p10' ; P11 : 'p11' ; P12 : 'p12' ;\n\
P13 : 'p13' ; P14 : 'p14' ; P15 : 'p15' ; P16 : 'p16' ; P17 : 'p17' ; P18 : 'p18' ;\n";
let (_, build) = build_source_with(
"StartExhaustedBounded",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let decision = &build
.report
.decisions
.iter()
.find(|entry| entry.rule == "top")
.expect("top decision")
.result;
assert_eq!(decision.kind, DecisionKind::Hybrid, "{decision:#?}");
assert!(decision.k <= STATIC_ONLY_DEPTH_CAP as i32);
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[
AttemptKind::StaticOnly,
AttemptKind::Widened,
AttemptKind::Widened,
],
"{decision:#?}"
);
let resolved = decision.static_only.as_ref().expect("resolved");
assert!(
resolved
.tie_breaks
.iter()
.any(|group| group.hazard.is_some()),
"bounded widened retry must run hazard analysis: {resolved:?}"
);
}
#[test]
fn guarded_zero_escape_table_past_frontier_stays_static_without_truncating() {
let source = "grammar GuardedPastFrontier;\n\
prog : stmt+ EOF ;\n\
stmt : 'set' expr K1 K2 K3 K4 '=' expr ';' | expr ';' ;\n\
expr : value postfix? ;\n\
postfix : K1 K2 K3 K4 '=' value ;\n\
value : ID ;\n\
K1 : 'k1' ; K2 : 'k2' ; K3 : 'k3' ; K4 : 'k4' ; ID : 'id' ;\n";
for (atn_fallback, expected_attempt) in [
(AtnFallback::Allowed, AttemptKind::Default),
(AtnFallback::Forbidden, AttemptKind::StaticOnly),
] {
let (_, build) = build_source_with(
"GuardedPastFrontier",
source,
atn_fallback,
&ParserDfaBudgets::default(),
);
let decision = build
.report
.decisions
.iter()
.find(|entry| entry.rule == "expr")
.expect("expr decision");
assert_eq!(
decision.result.kind,
DecisionKind::Static,
"{atn_fallback:?}"
);
assert_eq!(decision.result.escapes, 0, "{atn_fallback:?}");
assert!(decision.result.guarded_states() > 0, "{atn_fallback:?}");
assert!(
decision.result.k > PARTIAL_DEPTH_CAP as i32,
"{atn_fallback:?}"
);
assert_eq!(
decision
.result
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[expected_attempt],
"{atn_fallback:?}"
);
if atn_fallback == AtnFallback::Forbidden {
let resolved = decision.result.static_only.as_ref().expect("resolved");
assert!(resolved.guarded > 0);
assert!(
resolved
.guard_groups
.iter()
.any(|group| group.hazard.is_some()),
"guard hazard analysis must run"
);
}
}
}
#[test]
fn low_coverage_past_frontier_skips_redundant_bounded_retry() {
let source = "grammar LowCoverageLateEscape;\n\
top : head A B C D E {true}? F X\n\
| head A B C D E F Y\n\
| T12 ;\n\
head : T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | T10 | T11 ;\n\
T1 : 't1' ; T2 : 't2' ; T3 : 't3' ; T4 : 't4' ;\n\
T5 : 't5' ; T6 : 't6' ; T7 : 't7' ; T8 : 't8' ;\n\
T9 : 't9' ; T10 : 't10' ; T11 : 't11' ; T12 : 't12' ;\n\
A : 'a' ; B : 'b' ; C : 'c' ; D : 'd' ; E : 'e' ; F : 'f' ;\n\
X : 'x' ; Y : 'y' ;\n";
let (_, build) = build_source_with(
"LowCoverageLateEscape",
source,
AtnFallback::Allowed,
&ParserDfaBudgets::default(),
);
let decision = &build.report.decisions[0].result;
assert!(matches!(
decision.no_table,
Some(NoTableReason::LowCoverage { .. })
));
assert_eq!(
decision
.cost
.attempts
.iter()
.map(|attempt| attempt.kind)
.collect::<Vec<_>>(),
[AttemptKind::Default]
);
}
#[test]
fn smaller_config_sets_expand_first_at_equal_depth() {
let source = "grammar CheapFirst;\n\
options { max_dfa_visits = 90; }\n\
top : ( '-' 's' | '-' 'n' | 'a' big 'x' | 'a' big 'y' ) ;\n\
big : c0 ;\n\
c0 : c1 | c2 ; c1 : c3 | c4 ; c2 : c3 | c4 ;\n\
c3 : c5 | c6 ; c4 : c5 | c6 ; c5 : 'p' | 'q' ; c6 : 'r' | 't' ;\n";
let (_, build) = build_source_with(
"CheapFirst",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let token = |name: &str| {
build
.report
.vocabulary
.iter()
.position(|display| display == name)
.map(|index| index as i32 + 1)
.expect("token in vocabulary")
};
let decision = build
.report
.decisions
.iter()
.find(|entry| entry.rule == "top")
.expect("top decision");
let table = decision.result.table.as_ref().expect("table");
assert_eq!(accept_after(table, &[token("'-'"), token("'s'")]), Some(1));
assert_eq!(accept_after(table, &[token("'-'"), token("'n'")]), Some(2));
}
#[test]
fn depth1_visit_slice_prevents_expensive_prefix_from_starving_siblings() {
let source = "grammar Depth1Slice;\n\
options { max_dfa_visits = 90; }\n\
top : ( 'a' 'p' big 'x' | 'a' 'p' big 'y' | 'b' 'p' | 'b' 'q' | 'b' 'r' ) ;\n\
big : r0 ;\n\
r0 : r1 | r2 ; r1 : r3 | r4 ; r2 : r5 | r6 ;\n\
r3 : r7 | r8 ; r4 : r9 | r10 ; r5 : r11 | r12 ; r6 : r13 | r14 ;\n\
r7 : 'k' ; r8 : 'k' ; r9 : 'k' ; r10 : 'k' ;\n\
r11 : 'k' ; r12 : 'k' ; r13 : 'k' ; r14 : 'k' ;\n";
let (_, build) = build_source_with(
"Depth1Slice",
source,
AtnFallback::Forbidden,
&ParserDfaBudgets::default(),
);
let token = |name: &str| {
build
.report
.vocabulary
.iter()
.position(|display| display == name)
.map(|index| index as i32 + 1)
.expect("token in vocabulary")
};
let decision = build
.report
.decisions
.iter()
.find(|entry| entry.rule == "top")
.expect("top decision");
assert_eq!(decision.result.budget_cutoff, Some(BudgetCutoff::Visits));
let table = decision.result.table.as_ref().expect("table");
assert_eq!(accept_after(table, &[token("'b'"), token("'p'")]), Some(3));
assert_eq!(accept_after(table, &[token("'b'"), token("'q'")]), Some(4));
assert_eq!(accept_after(table, &[token("'b'"), token("'r'")]), Some(5));
}