use std::collections::BTreeMap;
use std::fmt;
use std::time::{Duration, Instant};
use minijinja::Value;
use super::config::AtnFallback;
use super::descriptor::PassDescriptor;
use super::manifest::{object, option, source_location_value, source_value};
use dbt_antlr_runtime::dfa::static_parser_dfa::{
StaticParserTables as RuntimeTables, VIRTUAL_ALT_BASE,
};
use super::parser_dfa::{
AttemptOutcome, BudgetCutoff, BudgetLimits, CONFLICT_ESCAPE, DecisionBudget, DecisionKind,
DecisionOutcome, DecisionTableBuilder, DescentPlan, DescentRules, ESCAPE, EscapeResolution,
EscapeResolutions, GuardGroup, HazardLevel, HijackVerdict, NoTableReason,
PARTIAL_MIN_COVERAGE_PERCENT, ParserDfaBudgets, StackHijackVerdict, StaticDfaTable, TieBreak,
has_non_budget_option, minimized_states,
};
use crate::grammar::atn::{CompiledParser, FinalizedTransitionKind, left_corner_rules};
use crate::grammar::diagnostic::Diagnostic;
use crate::grammar::frontend::SourceSpan;
use crate::grammar::model::{
Alternative, Block, Element, ElementKind, ModelNodeId, Quantifier, RecognizerModel, Rule,
RuleKind, Terminal,
};
use crate::grammar::provenance::Origin;
use crate::grammar::source::SourceSet;
use crate::grammar::transform::SafetyClass;
use crate::optimization::{AlternativeNames, alternative_names};
const NOT_FULLY_STATIC: &str = "G4S190";
const DUMP_SELECTOR_NO_MATCH: &str = "G4S191";
const STATIC_ONLY_RESOLVED: &str = "G4S192";
const VISIT_BUDGET_SPENT: &str = "G4S193";
const TOKEN_BRANCHES: &str = "G4S194";
const TIE_BREAK_GROUPS: usize = 3;
const DANGER_CALLERS: usize = 3;
const STACK_HIJACKS: usize = 3;
const TOKEN_BRANCH_ENTRIES: usize = 20;
const TOKEN_BRANCH_ALTERNATIVES: usize = 64;
const HOT_RULES: usize = 3;
const PROFILE_ROWS: usize = 20;
const SLOW_DECISION: Duration = Duration::from_millis(500);
#[derive(Clone, Debug, Default)]
pub(crate) struct StaticParserTables {
tables: RuntimeTables,
has_table: Vec<bool>,
defers: Vec<bool>,
descent: Vec<Option<DescentPlan>>,
atn_fallback: AtnFallback,
}
impl StaticParserTables {
fn new(results: &[DecisionOutcome], atn_fallback: AtnFallback) -> Self {
let mut has_table = Vec::with_capacity(results.len());
let mut defers = Vec::with_capacity(results.len());
for result in results {
has_table.push(result.has_table());
defers.push(!result.is_fully_static());
}
Self {
tables: super::parser_dfa::build_tables(results),
has_table,
defers,
descent: results
.iter()
.map(|result| result.descent.clone())
.collect(),
atn_fallback,
}
}
pub(crate) fn has_table(&self, decision: usize) -> bool {
self.has_table.get(decision).copied().unwrap_or(false)
}
pub(crate) fn defers(&self, decision: usize) -> bool {
self.defers.get(decision).copied().unwrap_or(false)
}
pub(crate) fn descent(&self, decision: usize) -> Option<&DescentPlan> {
self.descent.get(decision).and_then(Option::as_ref)
}
pub(crate) fn shared_rules(&self) -> impl Iterator<Item = usize> + '_ {
self.descent
.iter()
.flatten()
.flat_map(|plan| plan.groups.iter().map(|group| group.rule))
}
pub(crate) const fn atn_fallback(&self) -> AtnFallback {
self.atn_fallback
}
pub(crate) fn words(&self) -> Vec<u32> {
self.tables.words().to_vec()
}
}
pub(crate) struct StaticParserDfa;
impl StaticParserDfa {
pub(crate) const NAME: &'static str = "static-parser-dfa";
pub(crate) const SAFETY: SafetyClass = SafetyClass::TreeAndApiPreserving;
pub(crate) fn build(
compiled: &CompiledParser,
sources: &SourceSet,
atn_fallback: AtnFallback,
profile: bool,
budgets: &ParserDfaBudgets,
) -> StaticParserDfaArtifact {
let atn = compiled.atn;
let recognizer = &compiled.semantic.recognizer;
let ll1_disjoint = ll1_disjointness(compiled);
let (budget, decision_budgets) = decision_budgets(compiled, budgets);
let builder = DecisionTableBuilder::new(atn, ll1_disjoint)
.with_atn_fallback(atn_fallback)
.with_descent_rules(descent_rules(compiled))
.with_budgets(decision_budgets)
.with_profiling(profile);
let started = profile.then(Instant::now);
let mut results = builder.build_all();
let profile = started.map(|started| BuildProfile {
elapsed: started.elapsed(),
threads: builder.threads(),
});
if atn_fallback == AtnFallback::Forbidden {
for result in &mut results {
result.resolve_static_only();
}
}
let tables = StaticParserTables::new(&results, atn_fallback);
let decisions = results
.iter()
.map(|result| StaticParserDecisionReport {
decision: result.decision,
state: usize::try_from(result.state_number).unwrap_or(0),
rule: recognizer
.rule_names
.get(result.rule_index)
.cloned()
.unwrap_or_default(),
source_span: decision_span(compiled, result)
.unwrap_or_else(|| compiled.semantic.unit.span.clone()),
alternatives: alternative_names(compiled, sources, result.decision),
result: result.clone(),
})
.collect::<Vec<_>>();
let vocabulary = (1..=atn.max_token_type)
.map(|token_type| token_display_name(recognizer, token_type))
.collect();
let report = StaticParserDfaReport {
grammar: compiled.semantic.unit.name.clone(),
source_span: compiled.semantic.unit.span.clone(),
vocabulary,
rule_names: recognizer.rule_names.clone(),
invoking_states: danger_invoking_states(compiled, sources, &results),
decisions,
atn_fallback,
budget,
profile,
};
let mut diagnostics = match atn_fallback {
AtnFallback::Allowed => Vec::new(),
AtnFallback::Forbidden => static_only_diagnostics(&report),
};
diagnostics.extend(visit_budget_diagnostics(&report));
diagnostics.extend(token_branch_diagnostics(compiled));
StaticParserDfaArtifact {
diagnostics,
report,
tables,
}
}
pub(super) fn manifest_pass_value(
id: usize,
descriptor: &PassDescriptor,
parsers: &[StaticParserDfaReport],
sources: &SourceSet,
) -> Value {
let mut totals = ReportMetrics::default();
for parser in parsers {
totals.add(parser);
}
let metrics = object(vec![
("parsers", Value::from(parsers.len())),
("decisions", Value::from(totals.decisions)),
("staticDecisions", Value::from(totals.static_decisions)),
("hybridDecisions", Value::from(totals.hybrid_decisions)),
("adaptiveDecisions", Value::from(totals.adaptive_decisions)),
("escapeStates", Value::from(totals.escape_states)),
("guardedStates", Value::from(totals.guarded_states)),
("minAltStates", Value::from(totals.min_alt_states)),
(
"minViableAltStates",
Value::from(totals.min_viable_alt_states),
),
("syntaxErrorStates", Value::from(totals.syntax_error_states)),
("hijackHazards", Value::from(totals.hijack_hazards)),
(
"descentGroupStates",
Value::from(totals.descent_group_states),
),
]);
let rendered = Value::from_iter(
parsers
.iter()
.map(|parser| parser_report_value(parser, sources)),
);
super::manifest::pass_value(
id,
descriptor,
totals.static_decisions > 0,
metrics,
vec![
(
"staticDfaOnly",
Value::from(
parsers
.iter()
.any(|parser| parser.atn_fallback == AtnFallback::Forbidden),
),
),
("parsers", rendered),
],
)
}
pub(crate) fn render_decision_profile(reports: &[StaticParserDfaReport]) -> String {
render_blocks(
&reports
.iter()
.map(decision_profile_text)
.collect::<Vec<_>>(),
)
}
pub(crate) fn render_dfa_dump(
reports: &[StaticParserDfaReport],
spec: &str,
) -> (String, Vec<Diagnostic>) {
let mut blocks = Vec::new();
let mut diagnostics = Vec::new();
for report in reports {
let (block, block_diagnostics) = dfa_dump_text(report, spec);
blocks.push(block);
diagnostics.extend(block_diagnostics);
}
(render_blocks(&blocks), diagnostics)
}
}
pub(crate) struct StaticParserDfaArtifact {
pub(crate) diagnostics: Vec<Diagnostic>,
pub(crate) report: StaticParserDfaReport,
pub(crate) tables: StaticParserTables,
}
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub(crate) struct StaticParserDfaSelection {
pub(crate) dump_dfas: Option<String>,
pub(crate) profile_decisions: bool,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct BuildProfile {
pub(crate) elapsed: Duration,
pub(crate) threads: usize,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct StaticParserDfaReport {
pub(crate) grammar: String,
pub(crate) source_span: SourceSpan,
pub(crate) vocabulary: Vec<String>,
pub(crate) rule_names: Vec<String>,
pub(crate) invoking_states: BTreeMap<i32, InvokingState>,
pub(crate) decisions: Vec<StaticParserDecisionReport>,
pub(crate) atn_fallback: AtnFallback,
pub(crate) budget: DecisionBudget,
pub(crate) profile: Option<BuildProfile>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct InvokingState {
pub(crate) rule: String,
pub(crate) label: Option<String>,
pub(crate) line: Option<usize>,
}
impl fmt::Display for InvokingState {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.rule)?;
if let Some(label) = &self.label {
write!(f, "#{label}")?;
}
if let Some(line) = self.line {
write!(f, ":{line}")?;
}
Ok(())
}
}
impl InvokingState {
fn called_from_text(&self) -> String {
let mut text = format!("'{}", self.rule);
if let Some(label) = &self.label {
text.push_str(&format!("#{label}"));
}
text.push('\'');
if let Some(line) = self.line {
text.push_str(&format!(" (line {line})"));
}
text
}
}
impl StaticParserDfaReport {
fn danger_text(&self, danger: &[i32]) -> String {
let states: Vec<String> = danger
.iter()
.map(|state| match self.invoking_states.get(state) {
Some(caller) => format!("{state} ({caller})"),
None => state.to_string(),
})
.collect();
format!("[{}]", states.join(", "))
}
fn static_decisions(&self) -> usize {
self.decisions
.iter()
.filter(|decision| decision.result.is_fully_static())
.count()
}
fn hybrid_decisions(&self) -> usize {
self.decisions
.iter()
.filter(|decision| decision.result.kind == DecisionKind::Hybrid)
.count()
}
fn adaptive_decisions(&self) -> usize {
self.decisions
.iter()
.filter(|decision| !decision.result.is_fully_static())
.count()
}
fn descent_group_states(&self) -> usize {
self.decisions
.iter()
.map(StaticParserDecisionReport::descent_group_states)
.sum()
}
fn escape_states(&self) -> usize {
self.decisions
.iter()
.map(|decision| decision.result.escapes)
.sum()
}
fn guarded_states(&self) -> usize {
self.decisions
.iter()
.map(|decision| decision.result.guarded_states())
.sum()
}
fn hijack_hazards(&self) -> usize {
self.decisions
.iter()
.map(StaticParserDecisionReport::hijack_hazards)
.sum()
}
fn resolved_states(&self) -> EscapeResolutions {
let mut total = EscapeResolutions::default();
for resolved in self
.decisions
.iter()
.filter_map(|decision| decision.result.static_only.as_ref())
{
total.guarded += resolved.guarded;
total.min_alt += resolved.min_alt;
total.min_viable_alt += resolved.min_viable_alt;
total.syntax_error += resolved.syntax_error;
}
total
}
}
#[derive(Clone, Copy, Debug, Default)]
struct ReportMetrics {
decisions: usize,
static_decisions: usize,
hybrid_decisions: usize,
adaptive_decisions: usize,
escape_states: usize,
guarded_states: usize,
min_alt_states: usize,
min_viable_alt_states: usize,
syntax_error_states: usize,
hijack_hazards: usize,
descent_group_states: usize,
}
impl ReportMetrics {
fn add(&mut self, parser: &StaticParserDfaReport) {
self.decisions += parser.decisions.len();
self.static_decisions += parser.static_decisions();
self.hybrid_decisions += parser.hybrid_decisions();
self.adaptive_decisions += parser.adaptive_decisions();
self.escape_states += parser.escape_states();
let resolved = parser.resolved_states();
self.guarded_states += parser.guarded_states();
self.min_alt_states += resolved.min_alt;
self.min_viable_alt_states += resolved.min_viable_alt;
self.syntax_error_states += resolved.syntax_error;
self.hijack_hazards += parser.hijack_hazards();
self.descent_group_states += parser.descent_group_states();
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct StaticParserDecisionReport {
pub(crate) decision: usize,
pub(crate) state: usize,
pub(crate) rule: String,
pub(crate) source_span: SourceSpan,
pub(crate) alternatives: AlternativeNames,
pub(crate) result: DecisionOutcome,
}
impl StaticParserDecisionReport {
fn hijack_hazards(&self) -> usize {
self.result.static_only.as_ref().map_or(0, |resolved| {
let prefix = resolved
.tie_breaks
.iter()
.filter(|group| group.level() == HazardLevel::High)
.count();
prefix + resolved.stack_hijacks().count()
})
}
fn descent_group_states(&self) -> usize {
self.result.descent_group_states()
}
}
fn parser_report_value(parser: &StaticParserDfaReport, sources: &SourceSet) -> Value {
let resolved = parser.resolved_states();
object(vec![
("grammar", Value::from(parser.grammar.as_str())),
("source", source_value(&parser.source_span, sources)),
("decisions", Value::from(parser.decisions.len())),
("staticDecisions", Value::from(parser.static_decisions())),
("hybridDecisions", Value::from(parser.hybrid_decisions())),
(
"adaptiveDecisions",
Value::from(parser.adaptive_decisions()),
),
("escapeStates", Value::from(parser.escape_states())),
("guardedStates", Value::from(parser.guarded_states())),
("minAltStates", Value::from(resolved.min_alt)),
("minViableAltStates", Value::from(resolved.min_viable_alt)),
("syntaxErrorStates", Value::from(resolved.syntax_error)),
("hijackHazards", Value::from(parser.hijack_hazards())),
(
"descentGroupStates",
Value::from(parser.descent_group_states()),
),
(
"decisionInventory",
Value::from_iter(
parser
.decisions
.iter()
.map(|decision| decision_report_value(decision, sources)),
),
),
])
}
fn decision_report_value(decision: &StaticParserDecisionReport, sources: &SourceSet) -> Value {
let result = &decision.result;
let resolved = result.static_only.clone().unwrap_or_default();
object(vec![
("decision", Value::from(decision.decision)),
("rule", Value::from(decision.rule.as_str())),
("state", Value::from(decision.state)),
(
"source",
source_location_value(&decision.source_span, sources),
),
("kind", Value::from(result.kind.as_str())),
("k", option(usize::try_from(result.k).ok(), Value::from)),
("fullyStatic", Value::from(result.is_fully_static())),
("dfaStates", Value::from(result.num_dfa_states)),
("escapeStates", Value::from(result.escapes)),
("fallback", Value::from(result.fallback_text())),
("guardedStates", Value::from(result.guarded_states())),
("minAltStates", Value::from(resolved.min_alt)),
("minViableAltStates", Value::from(resolved.min_viable_alt)),
("syntaxErrorStates", Value::from(resolved.syntax_error)),
("hijackHazards", Value::from(decision.hijack_hazards())),
(
"descentGroupStates",
Value::from(decision.descent_group_states()),
),
])
}
pub(super) fn ll1_disjointness(compiled: &CompiledParser) -> Vec<bool> {
let by_state = compiled
.analysis
.decision_lookahead
.iter()
.map(|lookahead| (lookahead.state, lookahead.disjoint))
.collect::<BTreeMap<_, _>>();
compiled
.atn
.decision_to_state
.iter()
.map(|state| {
by_state
.get(&usize::try_from(state.get_state_number()).unwrap_or(usize::MAX))
.copied()
.unwrap_or(false)
})
.collect()
}
pub(super) fn descent_rules(compiled: &CompiledParser) -> DescentRules {
let rules = &compiled.semantic.unit.rules;
DescentRules {
has_arguments: rules
.iter()
.map(|rule| {
compiled
.semantic
.bindings
.attributes
.get(&rule.id)
.is_some_and(|attributes| !attributes.arguments.is_empty())
})
.collect(),
has_actions: rules
.iter()
.map(|rule| {
rule.actions
.iter()
.any(|action| matches!(action.name.as_str(), "init" | "after"))
|| !rule.catches.is_empty()
|| rule.finally_action.is_some()
|| block_has_action(&rule.block)
})
.collect(),
}
}
fn block_has_action(block: &Block) -> bool {
block.alternatives.iter().any(|alternative| {
alternative
.elements
.iter()
.any(|element| match &element.kind {
ElementKind::Action { body, .. } => !body.trim().is_empty(),
ElementKind::Block(block) => block_has_action(block),
_ => false,
})
})
}
fn token_display_name(recognizer: &RecognizerModel, token_type: i32) -> String {
let Ok(index) = usize::try_from(token_type) else {
return "EOF".to_owned();
};
recognizer
.literal_names
.get(index)
.and_then(Clone::clone)
.or_else(|| recognizer.symbolic_names.get(index).and_then(Clone::clone))
.unwrap_or_else(|| token_type.to_string())
}
fn decision_profile_text(report: &StaticParserDfaReport) -> String {
let decisions = &report.decisions;
let mut lines = vec![format!(
"=== parser decision profile: {} ({} decisions) ===",
report.grammar,
decisions.len()
)];
let elapsed =
|decision: &StaticParserDecisionReport| decision.result.cost.elapsed.unwrap_or_default();
let summed: Duration = decisions.iter().map(elapsed).sum();
if let Some(profile) = &report.profile {
lines.push(format!(
"table builds: {} on {} {}; {} summed over the decisions",
duration_text(profile.elapsed),
profile.threads,
if profile.threads == 1 {
"thread"
} else {
"threads"
},
duration_text(summed),
));
}
let attempts: usize = decisions
.iter()
.map(|decision| decision.result.cost.attempts.len())
.sum();
let visits: u64 = decisions
.iter()
.map(|decision| decision.result.cost.visits())
.sum();
let states: usize = decisions
.iter()
.map(|decision| decision.result.cost.states())
.sum();
lines.push(format!(
"work: {attempts} build attempts; {visits} configs visited; {states} DFA states built"
));
let spent = |outcome| {
decisions
.iter()
.filter(|decision| decision.result.cost.count(outcome) > 0)
.count()
};
lines.push(format!(
"budgets: {} decisions spent the visit budget ({} configs); {} decisions spent the \
state budget ({} states)",
spent(AttemptOutcome::VisitBudget),
report.budget.max_visits,
spent(AttemptOutcome::StateBudget),
report.budget.max_states,
));
lines.push(format!(
"slow: {} decisions took {} ms or more",
decisions
.iter()
.filter(|decision| elapsed(decision) >= SLOW_DECISION)
.count(),
SLOW_DECISION.as_millis(),
));
lines.push(
"attempts: D default, S static-only, W widened, (N) milliseconds, cN: precedence class N"
.to_owned(),
);
lines.push("outcomes: $ spent the visit budget, ^ spent the state budget".to_owned());
let mut slowest: Vec<&StaticParserDecisionReport> = decisions.iter().collect();
slowest.sort_by(|left, right| {
elapsed(right)
.cmp(&elapsed(left))
.then(right.result.cost.visits().cmp(&left.result.cost.visits()))
.then(left.decision.cmp(&right.decision))
});
slowest.truncate(PROFILE_ROWS);
lines.push(format!("slowest {} decisions:", slowest.len()));
lines.extend(profile_rows(report, &slowest, elapsed));
finish_block(lines)
}
fn profile_rows(
report: &StaticParserDfaReport,
decisions: &[&StaticParserDecisionReport],
elapsed: impl Fn(&StaticParserDecisionReport) -> Duration,
) -> Vec<String> {
let rows: Vec<[String; 9]> = decisions
.iter()
.map(|decision| {
let cost = &decision.result.cost;
[
decision.decision.to_string(),
decision.rule.clone(),
decision.state.to_string(),
decision.result.kind.as_str().to_owned(),
format!("{:.1}", elapsed(decision).as_secs_f64() * 1000.0),
cost.visits().to_string(),
cost.states().to_string(),
cost.attempts_text(),
cost.hot_rules_text(&report.rule_names, HOT_RULES),
]
})
.collect();
let headers = [
"#",
"rule",
"state",
"kind",
"ms",
"visits",
"statesBuilt",
"attempts",
"most visited rules",
];
let right_aligned = [true, false, true, false, true, true, true, false, false];
let widths: Vec<usize> = headers
.iter()
.enumerate()
.map(|(column, header)| {
rows.iter()
.map(|row| row[column].len())
.max()
.unwrap_or(0)
.max(header.len())
})
.collect();
let line = |cells: Vec<&str>| {
let mut text = String::from(" ");
for (column, cell) in cells.iter().enumerate() {
let width = widths[column];
text.push(' ');
if right_aligned[column] {
text.push_str(&format!("{cell:>width$}"));
} else if column + 1 < cells.len() {
text.push_str(&format!("{cell:<width$}"));
} else {
text.push_str(cell);
}
if column + 1 < cells.len() {
text.push(' ');
}
}
text.trim_end().to_owned()
};
let mut lines = vec![line(headers.to_vec())];
lines.extend(
rows.iter()
.map(|row| line(row.iter().map(String::as_str).collect())),
);
lines
}
fn duration_text(duration: Duration) -> String {
if duration < Duration::from_secs(1) {
format!("{:.1} ms", duration.as_secs_f64() * 1000.0)
} else {
format!("{:.2} s", duration.as_secs_f64())
}
}
fn k_text(result: &DecisionOutcome) -> String {
if result.k < 0 {
"-".to_owned()
} else {
result.k.to_string()
}
}
fn dfa_dump_text(report: &StaticParserDfaReport, spec: &str) -> (String, Vec<Diagnostic>) {
let selection = DfaDumpSelection::parse(spec);
let mut diagnostics = Vec::new();
let mut lines = vec![
format!("=== static DFA dump: grammar {} ===", report.grammar),
vocabulary_line(&report.vocabulary),
];
let mut selected = vec![false; selection.selectors.len()];
let mut shown = 0_usize;
for decision in &report.decisions {
let mut hit = selection.all;
for (index, selector) in selection.selectors.iter().enumerate() {
if selector.matches(decision) {
selected[index] = true;
hit = true;
}
}
if !hit {
continue;
}
shown += 1;
lines.extend(decision_dump_lines(report, decision, selection.paths));
}
lines.push(String::new());
lines.push(format!(
"({shown} of {} decisions dumped)",
report.decisions.len()
));
if selection.selects_nothing() {
diagnostics.push(no_matching_decision_error(report, spec));
}
diagnostics.extend(
selection
.malformed
.iter()
.map(|item| no_matching_decision_error(report, item)),
);
diagnostics.extend(
selection
.selectors
.iter()
.zip(&selected)
.filter(|(_, matched)| !**matched)
.map(|(selector, _)| no_matching_decision_error(report, &selector.text())),
);
(finish_block(lines), diagnostics)
}
fn decision_dump_lines(
report: &StaticParserDfaReport,
decision: &StaticParserDecisionReport,
with_paths: bool,
) -> Vec<String> {
let result = &decision.result;
let headline = if !result.has_table() {
format!(
"--- decision {}: rule '{}' ({}) ---",
decision.decision, decision.rule, result.kind
)
} else {
format!(
"--- decision {}: rule '{}' ({}, k={}, {} states) ---",
decision.decision,
decision.rule,
result.kind,
k_text(result),
result.num_dfa_states
)
};
let mut lines = vec![String::new(), headline];
if !decision.alternatives.all().is_empty() {
lines.push(format!(
"alternatives: {}",
decision.alternatives.all().join("; ")
));
}
match (&result.table, &result.precedence) {
(_, Some(precedence)) => {
lines.push(format!("precedence classes: {:?}", precedence.cutoffs));
for (index, table) in precedence.tables.iter().enumerate() {
match table {
Some(table) => {
lines.push(format!("class {index}:"));
lines.extend(table_dump_lines(report, decision, table, with_paths));
}
None => lines.push(format!(
"class {index}: no static table: this precedence class runs on adaptive_predict"
)),
}
}
}
(Some(table), None) => {
lines.extend(descent_dump_lines(report, result.descent.as_ref()));
lines.extend(table_dump_lines(report, decision, table, with_paths));
}
(None, None) if result.kind == DecisionKind::Ll1 => lines.push(
" no table needed: the alternatives have disjoint first tokens, so plain LL(1) \
prediction decides"
.to_owned(),
),
(None, None) => lines.push(format!(" no static table: {}", no_table_text(result))),
}
lines
}
fn table_dump_lines(
report: &StaticParserDfaReport,
decision: &StaticParserDecisionReport,
table: &StaticDfaTable,
with_paths: bool,
) -> Vec<String> {
let runtime_states = minimized_states(table);
let mut lines = vec![format!(
" table: states={}{} cyclic={}{}",
table.states.len(),
if runtime_states < table.states.len() {
format!(" (runtime {runtime_states})")
} else {
String::new()
},
table.cyclic,
if table.cyclic {
String::new()
} else {
format!(" maxK={}", table.max_k)
}
)];
if table.guarded() > 0 {
lines.push(format!(
" guards: {} guarded states in {} guard groups (pass={} states). A guard walks up the parse stack through the pass frames. It defers at an invoking state of its danger set.",
table.guarded(),
table.guard_groups.len(),
table.guard_pass.len()
));
for (group, danger) in table.guard_groups.iter().enumerate() {
let hazard = decision
.result
.static_only
.iter()
.flat_map(|resolved| &resolved.guard_groups)
.find(|known| known.danger == *danger)
.and_then(|known| known.hazard.as_ref())
.filter(|hazard| matches!(hazard, StackHijackVerdict::Hijack { .. }))
.map(|hazard| stack_hazard_text(report, Some(hazard)))
.unwrap_or_default();
lines.push(format!(
" group {group}: danger={}{hazard}",
report.danger_text(danger)
));
}
}
for (index, state) in table.states.iter().enumerate() {
let mut line = format!(" s{index}: ");
let mut note = None;
if state.accept >= VIRTUAL_ALT_BASE {
line.push_str(&format!("GROUP {}", state.accept));
} else if state.accept > 0 {
line.push_str(&format!("accept alt={}", state.accept));
match state.resolution {
Some(EscapeResolution::MinAlt) => {
line.push_str(" (static-dfa-only: minimum conflicting alternative)");
}
Some(EscapeResolution::MinViableAlt) => {
line.push_str(" (static-dfa-only: minimum viable alternative)");
}
_ => {}
}
let dropped: &[i32] = match state.resolution {
Some(EscapeResolution::MinAlt) => &state.conflicts,
Some(EscapeResolution::MinViableAlt) => &state.viable_alts,
_ => &[],
};
let dropped: Vec<String> = dropped
.iter()
.filter(|alt| **alt > 0 && **alt != state.accept)
.map(ToString::to_string)
.collect();
match dropped.as_slice() {
[] => {}
[alt] => note = Some(format!("; over alt {alt}")),
alts => note = Some(format!("; over alts {}", alts.join(", "))),
}
} else if state.is_guarded() {
let deferred = if state.resolution == Some(EscapeResolution::Guarded) {
format!("alt={}", state.guard_defer_alt)
} else {
"adaptive_predict".to_owned()
};
line.push_str(&format!(
"GUARDED alt={}, or {deferred} when the parse stack reaches a guard root of group {} (danger={})",
state.guarded_alt,
state.guard_group,
report.danger_text(
table
.guard_groups
.get(state.guard_group as usize)
.map_or(&[][..], Vec::as_slice)
)
));
} else if state.is_escape() {
line.push_str("ESCAPE");
if state.viable_alts.len() > 1 {
let viable: Vec<String> =
state.viable_alts.iter().map(ToString::to_string).collect();
note = Some(format!("; viable alts {}", viable.join(", ")));
}
} else if state.resolution == Some(EscapeResolution::SyntaxError) {
line.push_str("SYNTAX ERROR (static-dfa-only: predicated lookahead)");
} else {
line.push_str("(non-accept)");
}
if state.fallback > 0 {
line.push_str(&format!("; error-recovery fallback alt={}", state.fallback));
}
if let Some(note) = note {
line.push_str(¬e);
}
if with_paths && let Some(path) = table.witness(index).filter(|path| !path.is_empty()) {
line.push_str(&format!("; path: {}", path_text(&report.vocabulary, &path)));
}
lines.push(line);
for edge in &state.edges {
lines.push(format!(
" s{index} {}({}) -> s{}",
interval_text(&report.vocabulary, edge.lo, edge.hi),
token_range_text(edge.lo, edge.hi),
edge.target
));
}
}
lines
}
fn descent_dump_lines(report: &StaticParserDfaReport, plan: Option<&DescentPlan>) -> Vec<String> {
let Some(plan) = plan else {
return Vec::new();
};
plan.groups
.iter()
.map(|group| {
let mut text = format!(
" group {}: shared rule '{}' after {} prefix tokens, members {:?}; tails:",
group.virtual_alt,
report
.rule_names
.get(group.rule)
.map_or("?", String::as_str),
group.prefix.len(),
group.alts
);
for arm in &group.arms {
let tokens: Vec<String> = arm
.tokens
.iter()
.map(|token| token_name(&report.vocabulary, *token))
.collect();
text.push_str(&format!(" alt {} on {}", arm.alt, tokens.join(" ")));
text.push(';');
}
if group.default_alt > 0 {
text.push_str(&format!(" otherwise alt {}", group.default_alt));
} else {
text.push_str(&format!(" default alt {}", group.min_alt()));
}
text
})
.collect()
}
fn token_name(vocabulary: &[String], token: i32) -> String {
if token < 0 {
return "EOF".to_owned();
}
usize::try_from(token)
.ok()
.and_then(|token| token.checked_sub(1))
.and_then(|index| vocabulary.get(index))
.cloned()
.unwrap_or_else(|| token.to_string())
}
fn interval_text(vocabulary: &[String], lo: i32, hi: i32) -> String {
if lo == hi {
token_name(vocabulary, lo)
} else {
format!(
"{}..{}",
token_name(vocabulary, lo),
token_name(vocabulary, hi)
)
}
}
fn token_range_text(lo: i32, hi: i32) -> String {
if lo == hi {
lo.to_string()
} else {
format!("{lo}..{hi}")
}
}
fn path_text(vocabulary: &[String], path: &[i32]) -> String {
path.iter()
.map(|token| token_name(vocabulary, *token))
.collect::<Vec<_>>()
.join(" ")
}
fn no_table_text(result: &DecisionOutcome) -> String {
result.no_table.as_ref().map_or_else(
|| "no static table".to_owned(),
|reason| reason_text(reason, &result.budget),
)
}
fn reason_text(reason: &NoTableReason, budget: &DecisionBudget) -> String {
match reason {
NoTableReason::NonGreedy => "the decision is a non-greedy subrule, and the generated \
parser predicts non-greedy subrules only with adaptive_predict"
.to_owned(),
NoTableReason::TooManyAlternatives => {
"the decision has too many alternatives for a static table".to_owned()
}
NoTableReason::EmptyPrecedenceLoop => {
"the precedence loop has no precedence predicates to build class tables from".to_owned()
}
NoTableReason::PredicatedStart(Some((rule, index))) => format!(
"the decision depends on predicate {rule}:{index}, so the prediction is not input-only"
),
NoTableReason::PredicatedStart(None) => {
"the decision depends on a predicate, so the prediction is not input-only".to_owned()
}
NoTableReason::StartConflict => {
"SLL cannot separate the alternatives; only full-context prediction can".to_owned()
}
NoTableReason::StartBudget(cutoff) => format!(
"the SLL DFA exceeded the analysis budget ({})",
budget_limit_text(*cutoff, budget)
),
NoTableReason::LowCoverage { coverage_percent } => format!(
"the partial table decides {coverage_percent}% of the start lookahead, less than the \
{PARTIAL_MIN_COVERAGE_PERCENT}% that a partial table needs"
),
NoTableReason::PrecedenceClasses {
failed,
total,
first,
} => format!(
"{failed} of {total} precedence classes have no static table: {}",
reason_text(first, budget)
),
}
}
fn budget_limit_text(cutoff: BudgetCutoff, budget: &DecisionBudget) -> String {
match cutoff {
BudgetCutoff::States => format!("{} states", budget.max_states),
BudgetCutoff::Visits => format!("{} visited configs", budget.max_visits),
BudgetCutoff::Both => format!(
"{} states and {} visited configs",
budget.max_states, budget.max_visits
),
}
}
fn budget_cutoff_text(cutoff: BudgetCutoff, budget: &DecisionBudget) -> String {
let option = match cutoff {
BudgetCutoff::States => "the max_dfa_states option",
BudgetCutoff::Visits => "the max_dfa_visits option",
BudgetCutoff::Both => "the max_dfa_states and max_dfa_visits options",
};
format!(
"the analysis budget ({}) stopped the lookahead; \
raise it with {option} of the grammar, the rule, or the block",
budget_limit_text(cutoff, budget)
)
}
fn witness_text(vocabulary: &[String], witness: Option<&[i32]>) -> Option<String> {
witness
.filter(|witness| !witness.is_empty())
.map(|witness| path_text(vocabulary, witness))
}
fn vocabulary_line(vocabulary: &[String]) -> String {
let tokens = vocabulary
.iter()
.enumerate()
.map(|(index, name)| format!(" {name}={}", index + 1))
.collect::<String>();
format!("vocabulary: EOF=-1{tokens}")
}
fn render_blocks(blocks: &[String]) -> String {
let mut text = blocks.join("\n");
if !blocks.is_empty() {
text.push('\n');
}
text
}
fn finish_block(lines: Vec<String>) -> String {
let mut text = lines.join("\n");
text.push('\n');
text
}
fn no_matching_decision_error(report: &StaticParserDfaReport, selector: &str) -> Diagnostic {
Diagnostic::error(
DUMP_SELECTOR_NO_MATCH,
report.source_span.clone(),
format!(
"--dump-dfas: no parser decision of grammar {} matches '{selector}'",
report.grammar
),
)
}
#[derive(Debug, Default)]
struct DfaDumpSelection {
all: bool,
paths: bool,
selectors: Vec<DfaDumpSelector>,
malformed: Vec<String>,
}
impl DfaDumpSelection {
fn parse(spec: &str) -> Self {
let mut selection = Self::default();
for raw in spec.split(',') {
let item = raw.trim();
if item.is_empty() {
continue;
}
if item.eq_ignore_ascii_case("all") {
selection.all = true;
} else if item.eq_ignore_ascii_case("paths") {
selection.paths = true;
} else if let Some(selector) = DfaDumpSelector::parse(item) {
if !selection.selectors.contains(&selector) {
selection.selectors.push(selector);
}
} else if !selection.malformed.iter().any(|known| known == item) {
selection.malformed.push(item.to_owned());
}
}
selection
}
fn selects_nothing(&self) -> bool {
!self.all && self.selectors.is_empty() && self.malformed.is_empty()
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
enum DfaDumpSelector {
Decision(usize),
Rule(String),
RuleDecision { rule: String, decision: usize },
}
impl DfaDumpSelector {
fn parse(item: &str) -> Option<Self> {
if let Some((rule, decision)) = item.split_once(':') {
let rule = rule.trim();
let decision = decision_number(decision.trim())?;
return (!rule.is_empty()).then(|| Self::RuleDecision {
rule: rule.to_owned(),
decision,
});
}
Some(match decision_number(item) {
Some(decision) => Self::Decision(decision),
None => Self::Rule(item.to_owned()),
})
}
fn matches(&self, decision: &StaticParserDecisionReport) -> bool {
match self {
Self::Decision(wanted) => *wanted == decision.decision,
Self::Rule(wanted) => *wanted == decision.rule,
Self::RuleDecision {
rule,
decision: wanted,
} => *rule == decision.rule && *wanted == decision.decision,
}
}
fn text(&self) -> String {
match self {
Self::Decision(decision) => decision.to_string(),
Self::Rule(rule) => rule.clone(),
Self::RuleDecision { rule, decision } => format!("{rule}:{decision}"),
}
}
}
fn decision_number(text: &str) -> Option<usize> {
if text.is_empty() || !text.bytes().all(|byte| byte.is_ascii_digit()) {
return None;
}
text.parse().ok()
}
fn static_only_diagnostics(report: &StaticParserDfaReport) -> Vec<Diagnostic> {
report
.decisions
.iter()
.filter_map(|decision| {
let result = &decision.result;
let span = decision.source_span.clone();
let Some(resolved) = &result.static_only else {
let mut message = format!(
"parser decision {} of rule '{}' is not fully static: {}; \
--static-dfa-only requires a static table for every decision",
decision.decision,
decision.rule,
no_table_text(result)
);
if let Some(witness) = witness_text(
&report.vocabulary,
result
.conflict_witness
.as_deref()
.or(result.budget_witness.as_deref()),
) {
message.push_str(&format!("; witness: {witness}"));
}
message.push_str(&conflict_text(decision));
return Some(Diagnostic::error(NOT_FULLY_STATIC, span, message));
};
let mut parts = Vec::new();
if resolved.guarded > 0 {
parts.push(resolution_text(
&report.vocabulary,
resolved.guarded,
("guarded state returns", "guarded states return"),
"the skip or the exit where the stack guard defers",
resolved.guarded_witness.as_deref(),
danger_callers_text(report, &resolved.guarded_danger),
));
parts
.last_mut()
.expect("the guarded clause")
.push_str(&stack_hijacks_text(report, resolved));
}
if resolved.min_alt > 0 {
parts.push(resolution_text(
&report.vocabulary,
resolved.min_alt,
("conflict state predicts", "conflict states predict"),
"the minimum alternative",
resolved.min_alt_witness.as_deref(),
None,
));
}
if resolved.min_viable_alt > 0 {
parts.push(resolution_text(
&report.vocabulary,
resolved.min_viable_alt,
("undecided state predicts", "undecided states predict"),
"the minimum viable alternative",
resolved.min_viable_alt_witness.as_deref(),
None,
));
}
if resolved.syntax_error > 0 {
parts.push(resolution_text(
&report.vocabulary,
resolved.syntax_error,
("predicated state reports", "predicated states report"),
"a syntax error",
resolved.syntax_error_witness.as_deref(),
None,
));
}
(!parts.is_empty()).then(|| {
let mut message = format!(
"decision {} of rule '{}' applied heuristic resolution of escape states: {}",
decision.decision,
decision.rule,
parts.join(", ")
);
message.push_str(&tie_break_text(report, decision));
if let Some(cutoff) = result.budget_cutoff {
message.push_str(&format!("; {}", budget_cutoff_text(cutoff, &result.budget)));
}
Diagnostic::warning(STATIC_ONLY_RESOLVED, span, message)
})
})
.collect()
}
fn visit_budget_diagnostics(report: &StaticParserDfaReport) -> Vec<Diagnostic> {
report
.decisions
.iter()
.filter_map(|decision| {
let result = &decision.result;
let cost = &result.cost;
let spent = cost.count(AttemptOutcome::VisitBudget);
if spent == 0 {
return None;
}
let mut message = format!(
"the analysis of parser decision {} of rule '{}' is slow: {spent} of {} build \
attempts spent the visit budget ({} configs); {} configs visited, {} DFA states \
built",
decision.decision,
decision.rule,
cost.attempts.len(),
result.budget.max_visits,
cost.visits(),
cost.states(),
);
let hot_rules = cost.hot_rules_text(&report.rule_names, HOT_RULES);
if !hot_rules.is_empty() {
message.push_str(&format!("; most visited rules: {hot_rules}"));
}
let span = decision.source_span.clone();
Some(Diagnostic::warning(VISIT_BUDGET_SPENT, span, message))
})
.collect()
}
fn token_branch_diagnostics(compiled: &CompiledParser) -> Vec<Diagnostic> {
let mut candidates = Vec::new();
for rule in &compiled.semantic.unit.rules {
if rule.kind != RuleKind::Parser {
continue;
}
let mut blocks = Vec::new();
leading_blocks(compiled, &rule.block, &mut blocks);
candidates.extend(
blocks
.into_iter()
.filter_map(|block| TokenBranches::of(rule, block))
.map(|branches| (rule, branches)),
);
}
if candidates.is_empty() {
return Vec::new();
}
let entries = rule_entries(compiled);
candidates
.into_iter()
.filter_map(|(rule, branches)| {
let entries = compiled
.semantic
.recognizer
.rule_numbers
.get(&rule.id)
.and_then(|index| entries.get(*index))
.copied()?;
(entries >= TOKEN_BRANCH_ENTRIES).then(|| branches.diagnostic(rule, entries))
})
.collect()
}
fn leading_blocks<'b>(
compiled: &CompiledParser,
block: &'b Block,
out: &mut Vec<&'b Block>,
) -> bool {
out.push(block);
let mut nullable = false;
for alternative in &block.alternatives {
let mut empty = true;
for element in &alternative.elements {
let element_nullable = match &element.kind {
ElementKind::Block(nested) => leading_blocks(compiled, nested, out),
ElementKind::Action { .. }
| ElementKind::Predicate { .. }
| ElementKind::Epsilon => true,
ElementKind::RuleCall(_) => compiled
.semantic
.bindings
.rule_calls
.get(&element.id)
.is_some_and(|call| compiled.analysis.nullable_rules.contains(&call.target)),
_ => false,
};
if !element_nullable
&& !matches!(
element.quantifier,
Quantifier::Optional { .. } | Quantifier::ZeroOrMore { .. }
)
{
empty = false;
break;
}
}
nullable |= empty;
}
nullable
}
struct TokenBranches<'b> {
block: &'b Block,
count: usize,
causes: Vec<String>,
}
impl<'b> TokenBranches<'b> {
fn of(rule: &Rule, block: &'b Block) -> Option<Self> {
let operators = rule
.left_recursion
.as_ref()
.and_then(|_| left_recursion_operators(rule, block))
.unwrap_or(0);
let single_tokens = block
.alternatives
.iter()
.enumerate()
.filter_map(|(index, alternative)| {
let mut elements = alternative.elements.iter();
if index == 0
&& operators > 0
&& let [first, _, ..] = alternative.elements.as_slice()
&& matches!(&first.kind, ElementKind::Action { body, .. } if body.is_empty())
{
elements.next();
}
match (elements.next(), elements.next()) {
(Some(element), None)
if element.quantifier == Quantifier::One
&& matches!(
element.kind,
ElementKind::Terminal(Terminal::Token(_) | Terminal::Literal(_))
) =>
{
Some((alternative, element))
}
_ => None,
}
})
.collect::<Vec<_>>();
if single_tokens.len() < TOKEN_BRANCH_ALTERNATIVES {
return None;
}
let mut causes = Vec::new();
let others = block.alternatives.len() - single_tokens.len() + operators;
if others > 0 {
causes.push(count_text(
others,
"alternative is not a single token",
"alternatives are not a single token",
));
}
let labeled = single_tokens
.iter()
.filter(|(alternative, _)| alternative.label.is_some())
.count();
if labeled > 0 {
causes.push(count_text(
labeled,
"alternative has a label",
"alternatives have a label",
));
}
let element_labeled = single_tokens
.iter()
.filter(|(_, element)| element.label.is_some())
.count();
if element_labeled > 0 {
causes.push(count_text(
element_labeled,
"token has an element label",
"tokens have an element label",
));
}
if has_non_budget_option(&block.options)
|| single_tokens
.iter()
.any(|(alternative, _)| !alternative.options.is_empty())
{
causes.push("the block or its alternatives have options".to_owned());
}
(!causes.is_empty()).then_some(Self {
block,
count: single_tokens.len(),
causes,
})
}
fn diagnostic(&self, rule: &Rule, entries: usize) -> Diagnostic {
Diagnostic::warning(
TOKEN_BRANCHES,
self.block.span.clone(),
format!(
"rule '{}' has a block with {} single-token alternatives that do not fold into \
one token set. The block does not fold because {}. {entries} 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",
rule.name,
self.count,
self.causes.join(", and "),
),
)
}
}
fn left_recursion_operators(rule: &Rule, block: &Block) -> Option<usize> {
let [alternative] = rule.block.alternatives.as_slice() else {
return None;
};
let [primary, operators] = alternative.elements.as_slice() else {
return None;
};
match (&primary.kind, &operators.kind) {
(ElementKind::Block(primary), ElementKind::Block(operators))
if std::ptr::eq(primary, block) =>
{
Some(operators.alternatives.len())
}
_ => None,
}
}
fn rule_entries(compiled: &CompiledParser) -> Vec<usize> {
let graph = &compiled.graph;
let rules = graph.rule_starts.len();
let mut direct = vec![0_usize; rules];
for transition in &graph.transitions {
if let FinalizedTransitionKind::Rule { rule_index, .. } = transition.kind
&& let Some(count) = direct.get_mut(rule_index)
{
*count += 1;
}
}
let recognizer = &compiled.semantic.recognizer;
let nullable = compiled
.analysis
.nullable_rules
.iter()
.filter_map(|rule| recognizer.rule_numbers.get(rule).copied())
.collect();
let mut callers = vec![Vec::new(); rules];
for (caller, callees) in left_corner_rules(graph, &nullable).iter().enumerate() {
for &callee in callees {
if let Some(callers) = callers.get_mut(callee) {
callers.push(caller);
}
}
}
(0..rules)
.map(|rule| {
let mut seen = vec![false; rules];
seen[rule] = true;
let mut pending = vec![rule];
let mut entries = 0;
while let Some(current) = pending.pop() {
entries += direct[current];
for &caller in &callers[current] {
if !seen[caller] {
seen[caller] = true;
pending.push(caller);
}
}
}
entries
})
.collect()
}
fn count_text(count: usize, singular: &str, plural: &str) -> String {
format!("{count} {}", if count == 1 { singular } else { plural })
}
fn conflict_text(decision: &StaticParserDecisionReport) -> String {
let result = &decision.result;
let conflicting = |alts: &[i32]| {
format!(
"; conflicting alternatives: {}",
decision.alternatives.list(alts)
)
};
if let Some(alts) = result.conflicts.first().filter(|alts| alts.len() > 1) {
return conflicting(alts);
}
let first_state = |marker| {
result.tables().find_map(|table| {
table
.first_escape(marker)
.and_then(|index| table.states.get(index))
})
};
if let Some(state) = first_state(CONFLICT_ESCAPE) {
return if state.conflicts.len() > 1 {
conflicting(&state.conflicts)
} else {
String::new()
};
}
match first_state(ESCAPE) {
Some(state) if state.viable_alts.len() > 1 => format!(
"; viable alternatives: {}",
decision.alternatives.list(&state.viable_alts)
),
_ => String::new(),
}
}
fn tie_break_text(report: &StaticParserDfaReport, decision: &StaticParserDecisionReport) -> String {
let Some(resolved) = &decision.result.static_only else {
return String::new();
};
let groups = &resolved.tie_breaks;
let mut parts: Vec<String> = groups
.iter()
.take(TIE_BREAK_GROUPS)
.map(|group| {
let states = if group.states == 1 {
"1 state chooses".to_owned()
} else {
format!("{} states choose", group.states)
};
let mut text = format!(
"{states} {} over {}",
decision.alternatives.name(group.chosen),
decision.alternatives.list(&group.dropped)
);
let shown = [&resolved.min_alt_witness, &resolved.min_viable_alt_witness];
let hijack = group
.hazard
.as_ref()
.is_some_and(|hazard| matches!(hazard.verdict, HijackVerdict::Hijack { .. }));
if !hijack
&& !shown.contains(&&group.witness)
&& let Some(witness) = witness_text(&report.vocabulary, group.witness.as_deref())
{
text.push_str(&format!(" (witness: {witness})"));
}
text.push_str(&hazard_text(report, decision, group));
text
})
.collect();
if parts.is_empty() {
return String::new();
}
match groups.len().saturating_sub(TIE_BREAK_GROUPS) {
0 => {}
1 => parts.push("and 1 more tie-break group".to_owned()),
more => parts.push(format!("and {more} more tie-break groups")),
}
format!("; tie-breaks: {}", parts.join("; "))
}
fn hazard_text(
report: &StaticParserDfaReport,
decision: &StaticParserDecisionReport,
group: &TieBreak,
) -> String {
let Some(hazard) = &group.hazard else {
return " [unverified: no analysis of the hijack hazard]".to_owned();
};
let chosen = format!("alt {}", group.chosen);
match &hazard.verdict {
HijackVerdict::Hijack { alt, extension } => {
let (prefix, token) = extension.split_at(extension.len().saturating_sub(1));
let kind = if hazard.greedy {
"greedy choice"
} else {
"prefix-hijack hazard"
};
let after = if prefix.is_empty() {
String::new()
} else {
format!(" after {}", path_text(&report.vocabulary, prefix))
};
format!(
" [{kind}: {} reads {}{after}, and {chosen} cannot]",
decision.alternatives.name(*alt),
path_text(&report.vocabulary, token)
)
}
HijackVerdict::Covered if hazard.greedy => " [benign greedy choice]".to_owned(),
HijackVerdict::Covered => {
format!(" [benign: {chosen} reads each continuation of the dropped alternatives]")
}
HijackVerdict::Unknown if hazard.greedy => " [greedy choice, not verified]".to_owned(),
HijackVerdict::Unknown => {
" [unverified: the analysis did not separate the alternatives]".to_owned()
}
}
}
fn stack_hazard_text(
report: &StaticParserDfaReport,
hazard: Option<&StackHijackVerdict>,
) -> String {
match hazard {
None => " [unverified: no analysis of the stack guard]".to_owned(),
Some(StackHijackVerdict::Covered) => " [benign stack guard]".to_owned(),
Some(StackHijackVerdict::Unknown) => " [stack guard, not verified]".to_owned(),
Some(StackHijackVerdict::Hijack { caller, extension }) => {
let (deferred, token) = extension.split_at(extension.len().saturating_sub(1));
let caller = report.invoking_states.get(caller).map_or_else(
|| format!("invoking state {caller}"),
InvokingState::called_from_text,
);
let deferred = if deferred.is_empty() {
String::new()
} else {
format!(" {}", path_text(&report.vocabulary, deferred))
};
format!(
" [stack-hijack hazard: when called from {caller}, defers{deferred} even when \
followed by {}]",
path_text(&report.vocabulary, token)
)
}
}
}
fn stack_hijacks_text(report: &StaticParserDfaReport, resolved: &EscapeResolutions) -> String {
let hijacks: Vec<&GuardGroup> = resolved.stack_hijacks().collect();
if hijacks.is_empty() {
return resolved
.guard_groups
.first()
.map(|group| stack_hazard_text(report, group.hazard.as_ref()))
.unwrap_or_default();
}
let shown = hijacks.len().min(STACK_HIJACKS);
let mut text: String = hijacks[..shown]
.iter()
.map(|group| stack_hazard_text(report, group.hazard.as_ref()))
.collect();
match hijacks.len() - shown {
0 => {}
1 => text.push_str(" [and 1 more stack-hijack hazard]"),
more => text.push_str(&format!(" [and {more} more stack-hijack hazards]")),
}
text
}
fn resolution_text(
vocabulary: &[String],
count: usize,
(singular, plural): (&str, &str),
verdict: &str,
witness: Option<&[i32]>,
note: Option<String>,
) -> String {
let subject = if count == 1 { singular } else { plural };
let mut text = format!("{count} {subject} {verdict}");
let details: Vec<String> = witness_text(vocabulary, witness)
.map(|witness| format!("witness: {witness}"))
.into_iter()
.chain(note)
.collect();
if !details.is_empty() {
text.push_str(&format!(" ({})", details.join("; ")));
}
text
}
fn danger_callers_text(report: &StaticParserDfaReport, danger: &[i32]) -> Option<String> {
let mut callers: Vec<String> = Vec::new();
for caller in danger
.iter()
.filter_map(|state| report.invoking_states.get(state))
{
let caller = caller.to_string();
if !callers.contains(&caller) {
callers.push(caller);
}
}
let shown = callers.len().min(DANGER_CALLERS);
let mut text = match callers.len() {
0 => return None,
1 => "danger caller: ".to_owned(),
_ => "danger callers: ".to_owned(),
};
text.push_str(&callers[..shown].join(", "));
match callers.len() - shown {
0 => {}
1 => text.push_str(" and 1 more danger caller"),
more => text.push_str(&format!(" and {more} more danger callers")),
}
Some(text)
}
fn danger_invoking_states(
compiled: &CompiledParser,
sources: &SourceSet,
results: &[DecisionOutcome],
) -> BTreeMap<i32, InvokingState> {
let mut states = BTreeMap::new();
for result in results {
for table in result.tables() {
for state in table.guard_groups.iter().flatten() {
states
.entry(*state)
.or_insert_with(|| invoking_state(compiled, sources, *state));
}
}
}
states
}
fn invoking_state(compiled: &CompiledParser, sources: &SourceSet, state: i32) -> InvokingState {
let graph_state = usize::try_from(state)
.ok()
.and_then(|state| compiled.graph.states.get(state));
let rule_index = graph_state.and_then(|state| state.rule_index);
let rule = rule_index
.and_then(|rule| compiled.semantic.recognizer.rule_names.get(rule))
.cloned()
.unwrap_or_else(|| "?".to_owned());
let span = graph_state.and_then(|state| {
let call_origins = state
.transitions
.iter()
.flat_map(|transition| compiled.provenance.transition_origins(*transition));
let state_origins = compiled.provenance.state_origins(state.original);
call_origins
.chain(state_origins)
.find_map(|origin| origin_span(compiled, origin))
});
let label = span.as_ref().and_then(|span| {
let rule = compiled.semantic.unit.rules.get(rule_index?)?;
labeled_alternative(&rule.block, span)
});
let line = span
.and_then(|span| sources.line_column(span.source, span.bytes.start))
.map(|(line, _)| line);
InvokingState { rule, label, line }
}
fn labeled_alternative(block: &Block, span: &SourceSpan) -> Option<String> {
block.alternatives.iter().find_map(|alternative| {
if let Some(label) = &alternative.label
&& alternative.span.source == span.source
&& alternative.span.bytes.start <= span.bytes.start
&& span.bytes.end <= alternative.span.bytes.end
{
return Some(label.value.clone());
}
alternative
.elements
.iter()
.find_map(|element| match &element.kind {
ElementKind::Block(inner) => labeled_alternative(inner, span),
_ => None,
})
})
}
fn origin_span(compiled: &CompiledParser, origin: &Origin) -> Option<SourceSpan> {
match origin {
Origin::Authored { span, .. } => Some(span.clone()),
Origin::Synthetic { owner, .. } => model_node_span(compiled, *owner),
_ => None,
}
}
fn decision_span(compiled: &CompiledParser, result: &DecisionOutcome) -> Option<SourceSpan> {
if !result.is_precedence_loop()
&& let Ok(state_number) = usize::try_from(result.state_number)
&& let Some(state) = compiled.graph.states.get(state_number)
{
let origins = compiled.provenance.state_origins(state.original);
for owner in origins.iter().filter_map(|origin| match origin {
Origin::Synthetic { owner, .. } => Some(*owner),
_ => None,
}) {
if let Some(span) = model_node_span(compiled, owner) {
return Some(span);
}
}
if let Some(span) = origins.iter().find_map(|origin| match origin {
Origin::Authored { span, .. } => Some(span),
_ => None,
}) {
return Some(span.clone());
}
}
let rule = compiled.semantic.unit.rules.get(result.rule_index)?;
Some(rule.span.clone())
}
fn decision_budgets(
compiled: &CompiledParser,
budgets: &ParserDfaBudgets,
) -> (DecisionBudget, Vec<DecisionBudget>) {
let atn = compiled.atn;
let unit = &compiled.semantic.unit;
let grammar = BudgetLimits::from_options(&unit.options).or(budgets.global);
let decisions = atn
.decision_to_state
.iter()
.map(|state| {
let rule_index = usize::try_from(state.get_rule_index()).unwrap_or(usize::MAX);
let rule = unit.rules.get(rule_index);
let block = rule
.zip(usize::try_from(state.get_state_number()).ok())
.map(|(rule, state)| block_limits(compiled, state, rule))
.unwrap_or_default();
let rule = rule
.map(|rule| BudgetLimits::from_options(&rule.options))
.unwrap_or_default();
let limits = block.or(rule).or(grammar);
DecisionBudget::resolve(limits, atn.max_token_type)
})
.collect();
(
DecisionBudget::resolve(grammar, atn.max_token_type),
decisions,
)
}
fn block_limits(compiled: &CompiledParser, state: usize, rule: &Rule) -> BudgetLimits {
let Some(state) = compiled.graph.states.get(state) else {
return BudgetLimits::default();
};
let owner = compiled
.provenance
.state_origins(state.original)
.iter()
.rev()
.find_map(|origin| match origin {
Origin::Synthetic {
owner: ModelNodeId::Element(element),
..
} => Some(*element),
_ => None,
});
let mut blocks = Vec::new();
if owner.is_none_or(|owner| !enclosing_blocks(&rule.block, owner, &mut blocks)) {
return BudgetLimits::default();
}
blocks
.iter()
.rev()
.fold(BudgetLimits::default(), |limits, block| {
limits.or(BudgetLimits::from_options(&block.options))
})
}
fn enclosing_blocks<'a>(
block: &'a Block,
target: crate::grammar::model::ElementId,
path: &mut Vec<&'a Block>,
) -> bool {
for element in block
.alternatives
.iter()
.flat_map(|alternative| &alternative.elements)
{
let ElementKind::Block(inner) = &element.kind else {
if element.id == target {
return true;
}
continue;
};
path.push(inner);
if element.id == target || enclosing_blocks(inner, target, path) {
return true;
}
path.pop();
}
false
}
fn model_node_span(compiled: &CompiledParser, node: ModelNodeId) -> Option<SourceSpan> {
match node {
ModelNodeId::Rule(rule_id) => compiled
.semantic
.unit
.rules
.iter()
.find(|rule| rule.id == rule_id)
.map(rule_location),
ModelNodeId::Element(element_id) => {
find_element(&compiled.semantic.unit.rules, element_id).map(element_location)
}
_ => None,
}
}
fn rule_location(rule: &Rule) -> SourceSpan {
rule.block.span.clone()
}
fn element_location(element: &Element) -> SourceSpan {
let is_quantifier_decision = matches!(
element.quantifier,
Quantifier::Optional { .. } | Quantifier::ZeroOrMore { .. } | Quantifier::OneOrMore { .. }
);
if is_quantifier_decision {
return element.enclosing_span.clone();
}
element.span.clone()
}
fn find_element(rules: &[Rule], target: crate::grammar::model::ElementId) -> Option<&Element> {
rules
.iter()
.find_map(|rule| find_element_in_block(&rule.block, target))
}
fn find_element_in_block(
block: &Block,
target: crate::grammar::model::ElementId,
) -> Option<&Element> {
block
.alternatives
.iter()
.find_map(|alternative| find_element_in_alt(alternative, target))
}
fn find_element_in_alt(
alternative: &Alternative,
target: crate::grammar::model::ElementId,
) -> Option<&Element> {
for element in &alternative.elements {
if element.id == target {
return Some(element);
}
if let ElementKind::Block(inner) = &element.kind
&& let Some(found) = find_element_in_block(inner, target)
{
return Some(found);
}
}
None
}
#[cfg(test)]
mod tests {
use super::{BudgetCutoff, DecisionBudget, NoTableReason, budget_cutoff_text, reason_text};
#[test]
fn no_table_reasons_tell_why() {
let budget = DecisionBudget::default();
let cases = [
(
NoTableReason::NonGreedy,
"the decision is a non-greedy subrule, and the generated parser predicts \
non-greedy subrules only with adaptive_predict",
),
(
NoTableReason::TooManyAlternatives,
"the decision has too many alternatives for a static table",
),
(
NoTableReason::EmptyPrecedenceLoop,
"the precedence loop has no precedence predicates to build class tables from",
),
(
NoTableReason::PredicatedStart(Some((3, 1))),
"the decision depends on predicate 3:1, so the prediction is not input-only",
),
(
NoTableReason::PredicatedStart(None),
"the decision depends on a predicate, so the prediction is not input-only",
),
(
NoTableReason::StartConflict,
"SLL cannot separate the alternatives; only full-context prediction can",
),
(
NoTableReason::StartBudget(BudgetCutoff::States),
"the SLL DFA exceeded the analysis budget (1000 states)",
),
(
NoTableReason::StartBudget(BudgetCutoff::Visits),
"the SLL DFA exceeded the analysis budget (2000000 visited configs)",
),
(
NoTableReason::StartBudget(BudgetCutoff::Both),
"the SLL DFA exceeded the analysis budget (1000 states and 2000000 visited configs)",
),
(
NoTableReason::LowCoverage {
coverage_percent: 4,
},
"the partial table decides 4% of the start lookahead, less than the 10% that a \
partial table needs",
),
(
NoTableReason::PrecedenceClasses {
failed: 1,
total: 3,
first: Box::new(NoTableReason::StartConflict),
},
"1 of 3 precedence classes have no static table: SLL cannot separate the \
alternatives; only full-context prediction can",
),
];
for (reason, text) in cases {
assert_eq!(reason_text(&reason, &budget), text, "{reason:?}");
}
}
#[test]
fn budget_cutoff_texts_name_the_exhausted_budget() {
let budget = DecisionBudget::default();
assert_eq!(
budget_cutoff_text(BudgetCutoff::States, &budget),
"the analysis budget (1000 states) stopped the lookahead; raise it with the \
max_dfa_states option of the grammar, the rule, or the block"
);
assert_eq!(
budget_cutoff_text(BudgetCutoff::Visits, &budget),
"the analysis budget (2000000 visited configs) stopped the lookahead; raise it with \
the max_dfa_visits option of the grammar, the rule, or the block"
);
assert_eq!(
budget_cutoff_text(BudgetCutoff::Both, &budget),
"the analysis budget (1000 states and 2000000 visited configs) stopped the lookahead; \
raise it with the max_dfa_states and max_dfa_visits options of the grammar, the rule, \
or the block"
);
}
}