use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::num::NonZeroUsize;
use std::sync::OnceLock;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::time::Instant;
use dbt_antlr_runtime::analysis::{
ATN, ATNConfigSet, ATNStateRef, ATNStateType, Arena, BOUNDARY_TAINT, BitSet, Bump, EOF,
FOREIGN_CONSUME_TAINT, FOREIGN_LINEAGE_TAINT, IATNSimulator, INTERIOR_TAINT, MIDWAY_TAINT,
PRECPRED_TAINT, PRED_TAINT, ParserATNSimulator, ParserATNSimulatorManager, ParserDFAState,
PrecedencePredicateTransition, PredictionContext, PredictionContextRef, PredictionMode,
ProposedDFAState, ROOTED_TAINT, RuleStartState, WIDENED_TAINT, all_subsets_conflict,
all_subsets_equal, conflicting_alt_subsets, get_alts, has_sll_conflict_terminating_prediction,
};
use dbt_antlr_runtime::dfa::ParserDFA;
use dbt_antlr_runtime::dfa::static_parser_dfa::{
ContinuationConfigEntry, ContinuationContextNode, ParserContinuation, VIRTUAL_ALT_BASE,
};
use super::closure::{
CallSites, ClosedSet, Closure, ClosureFacts, GuardRoots, PrecedenceClass, Taint, taint_of,
};
use super::cost::{AttemptCost, AttemptKind, AttemptOutcome, CostLog};
use super::descent::{DescentAnalyzer, DescentPlan, DescentRules};
use super::hazard::{self, StackHijackVerdict, StateHazard};
use super::loop_block::{
EXIT_ALT, EXIT_FOREIGN, ITERATE_ALT, ITERATE_REAL, LoopBlock, is_iterate_exit_pair,
};
use super::outcome::{
BudgetCutoff, DecisionKind, DecisionOutcome, NoTableReason, PrecedenceTables,
};
use super::postfix::{GuardRegions, PostfixShape, epsilon_closure};
use super::table::{StaticDfaEdge, StaticDfaState, StaticDfaTable};
use super::{CONFLICT_ESCAPE, DecisionBudget, ESCAPE, GUARDED};
use crate::optimization::AtnFallback;
pub(crate) const PARTIAL_DEPTH_CAP: usize = 4;
pub(crate) const PARTIAL_STATE_CAP: usize = 64;
pub(crate) const STATIC_ONLY_DEPTH_CAP: usize = 16;
pub(crate) const PARTIAL_MIN_COVERAGE_PERCENT: u32 = 10;
pub(crate) const MAX_CONTINUATION_WORDS: usize = 64;
const MAX_BUILD_THREADS: usize = 16;
const HAZARD_STATES: usize = 48;
const HAZARD_STATES_PER_GROUP: usize = 4;
const GUARD_HAZARD_STATES: usize = 48;
const GUARD_HAZARD_STATES_PER_GROUP: usize = 8;
const TRUST_TAINT: i32 = WIDENED_TAINT
| PRECPRED_TAINT
| BOUNDARY_TAINT
| FOREIGN_CONSUME_TAINT
| FOREIGN_LINEAGE_TAINT
| MIDWAY_TAINT
| ROOTED_TAINT
| INTERIOR_TAINT;
const POSTFIX_TAKE_ALT: i32 = 1;
const POSTFIX_SKIP_ALT: i32 = 2;
fn is_take_skip_pair(alts: &BitSet) -> bool {
alts.len() == 2
&& alts.contains(POSTFIX_TAKE_ALT as usize)
&& alts.contains(POSTFIX_SKIP_ALT as usize)
}
const MAX_TRACKED_DEPTH: usize = 30;
const VARIABLE_DEPTH: usize = 31;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Verdict {
Accept(i32),
Escape(i32),
Decide,
}
#[derive(Clone, Debug)]
struct StateFacts {
depth: usize,
verdict: Verdict,
taint: Taint,
fallback: i32,
conflicts: Vec<i32>,
resolved_conflict: bool,
expanded: bool,
conflict_min_alt: i32,
guarded_alt: i32,
guard_defer_alt: i32,
guard_group: u32,
roots: GuardRoots,
continuation: Option<ParserContinuation>,
predicated: bool,
}
#[derive(Debug, Default)]
struct ClassifyEffects {
conflict: Option<Vec<i32>>,
guard_candidate: bool,
guard_iterate_candidate: bool,
fail_predicated: bool,
}
impl StateFacts {
fn accept_value(&self) -> i32 {
match self.verdict {
Verdict::Accept(alt) => alt,
Verdict::Escape(marker) => marker,
Verdict::Decide => 0,
}
}
}
#[derive(Clone, Copy, Debug)]
struct Frontier {
depth_cap: usize,
state_cap: usize,
}
impl Frontier {
fn of(budget: &DecisionBudget, atn_fallback: AtnFallback) -> Self {
match atn_fallback {
AtnFallback::Allowed => Self {
depth_cap: budget.max_k.unwrap_or(PARTIAL_DEPTH_CAP),
state_cap: if budget.explicit_max_states {
budget.max_states
} else {
PARTIAL_STATE_CAP
},
},
AtnFallback::Forbidden => Self {
depth_cap: budget.max_k.unwrap_or(STATIC_ONLY_DEPTH_CAP),
state_cap: budget.max_states,
},
}
}
}
#[derive(Debug, Default)]
struct Attempt {
decision: usize,
state_count: usize,
table: Option<StaticDfaTable>,
failed: Option<BudgetCutoff>,
start_exhausted: bool,
exhausted: bool,
budget_cutoff: Option<BudgetCutoff>,
non_budget_escape: bool,
exceeded_frontier: bool,
visits: u64,
rule_visits: Vec<u64>,
facts: ClosureFacts,
conflicts: Vec<Vec<i32>>,
first_conflict_state: Option<i32>,
predicated: bool,
descent: Option<DescentPlan>,
}
impl Attempt {
fn finalize(self, decision_state: ATNStateRef, atn_fallback: AtnFallback) -> DecisionOutcome {
let mut outcome = DecisionOutcome::new(self.decision, decision_state);
for conflict in &self.conflicts {
if !outcome.conflicts.contains(conflict) {
outcome.conflicts.push(conflict.clone());
}
}
if self.predicated {
outcome.no_table = Some(NoTableReason::PredicatedStart(self.facts.first_predicate));
return outcome;
}
let Some(table) = self.table else {
outcome.no_table = Some(NoTableReason::StartBudget(
self.failed.expect("failed attempt records its budget"),
));
return outcome;
};
outcome.coverage_percent = (table.start_coverage() * 100.0) as u32;
outcome.conflict_witness = table
.first_escape(CONFLICT_ESCAPE)
.or_else(|| {
self.first_conflict_state.and_then(|state| {
usize::try_from(state)
.ok()
.filter(|state| *state < table.states.len())
})
})
.and_then(|state| table.witness(state));
if let Some(state) = table.first_escape(ESCAPE) {
outcome.budget_witness = table.witness(state);
}
if table.states.first().is_none_or(StaticDfaState::is_escape) {
outcome.no_table = Some(NoTableReason::StartConflict);
return outcome;
}
let escapes = table.escapes();
if escapes > 0 {
if atn_fallback == AtnFallback::Allowed
&& outcome.coverage_percent < PARTIAL_MIN_COVERAGE_PERCENT
{
outcome.no_table = Some(NoTableReason::LowCoverage {
coverage_percent: outcome.coverage_percent,
});
return outcome;
}
outcome.kind = DecisionKind::Hybrid;
} else {
outcome.kind = DecisionKind::Static;
}
outcome.num_dfa_states = table.states.len();
outcome.k = table.max_k;
outcome.escapes = escapes;
outcome.budget_cutoff = self.budget_cutoff;
outcome.descent = used_groups(self.descent.as_ref(), &table);
outcome.table = Some(table);
outcome
}
}
pub(crate) struct DecisionTableBuilder {
atn: &'static ATN,
ll1_disjoint: Vec<bool>,
completion_depths: Box<[OnceLock<BitSet>]>,
default_budget: DecisionBudget,
budgets: Vec<DecisionBudget>,
loop_blocks: Box<[OnceLock<LoopBlock>]>,
postfix_shapes: Box<[OnceLock<Option<PostfixShape>>]>,
atn_fallback: AtnFallback,
descent: DescentAnalyzer,
call_sites: CallSites,
guard_regions: OnceLock<GuardRegions>,
profile: bool,
#[cfg(test)]
widened: bool,
}
impl DecisionTableBuilder {
pub(crate) fn new(atn: &'static ATN, ll1_disjoint: Vec<bool>) -> Self {
Self {
atn,
ll1_disjoint,
completion_depths: once_locks(atn.states_count()),
default_budget: DecisionBudget::default(),
budgets: Vec::new(),
loop_blocks: once_locks(atn.decision_to_state.len()),
postfix_shapes: once_locks(atn.decision_to_state.len()),
atn_fallback: AtnFallback::Allowed,
descent: DescentAnalyzer::new(atn),
call_sites: CallSites::of(atn),
guard_regions: OnceLock::new(),
profile: false,
#[cfg(test)]
widened: false,
}
}
fn loop_block(&self, decision: usize) -> LoopBlock {
self.loop_blocks[decision]
.get_or_init(|| LoopBlock::of(self.atn, self.atn.decision_to_state[decision]))
.clone()
}
fn postfix_shape(&self, decision: usize) -> Option<PostfixShape> {
self.postfix_shapes[decision]
.get_or_init(|| PostfixShape::analyze(self.atn, self.atn.decision_to_state[decision]))
.clone()
}
#[cfg(test)]
pub(crate) const fn with_visit_budget(mut self, budget: u64) -> Self {
self.default_budget.max_visits = budget;
self
}
#[cfg(test)]
pub(crate) const fn with_max_k(mut self, max_k: usize) -> Self {
self.default_budget.max_k = Some(max_k);
self
}
#[cfg(test)]
pub(crate) const fn with_widening(mut self) -> Self {
self.widened = true;
self
}
pub(crate) fn with_budgets(mut self, budgets: Vec<DecisionBudget>) -> Self {
self.budgets = budgets;
self
}
pub(crate) fn budget(&self, decision: usize) -> DecisionBudget {
self.budgets
.get(decision)
.copied()
.unwrap_or(self.default_budget)
}
pub(crate) fn with_descent_rules(mut self, rules: DescentRules) -> Self {
self.descent = self.descent.with_rules(rules);
self
}
pub(crate) const fn with_atn_fallback(mut self, atn_fallback: AtnFallback) -> Self {
self.atn_fallback = atn_fallback;
self
}
pub(crate) const fn with_profiling(mut self, profile: bool) -> Self {
self.profile = profile;
self
}
pub(crate) fn threads(&self) -> usize {
let available = std::thread::available_parallelism().map_or(1, NonZeroUsize::get);
self.workers(available.min(MAX_BUILD_THREADS))
}
fn workers(&self, threads: usize) -> usize {
threads.clamp(1, self.atn.decision_to_state.len().max(1))
}
pub(crate) fn build_all(&self) -> Vec<DecisionOutcome> {
self.build_on(self.threads())
}
pub(super) fn build_on(&self, threads: usize) -> Vec<DecisionOutcome> {
let decisions = self.atn.decision_to_state.len();
let threads = self.workers(threads);
if threads == 1 {
return (0..decisions)
.map(|decision| self.build(decision))
.collect();
}
let next = AtomicUsize::new(0);
let mut outcomes: Vec<Option<DecisionOutcome>> = vec![None; decisions];
std::thread::scope(|scope| {
let workers: Vec<_> = (0..threads)
.map(|_| {
scope.spawn(|| {
let mut built = Vec::new();
loop {
let decision = next.fetch_add(1, Ordering::Relaxed);
if decision >= decisions {
break built;
}
built.push((decision, self.build(decision)));
}
})
})
.collect();
for worker in workers {
let built = worker
.join()
.unwrap_or_else(|panic| std::panic::resume_unwind(panic));
for (decision, outcome) in built {
outcomes[decision] = Some(outcome);
}
}
});
outcomes
.into_iter()
.map(|outcome| outcome.expect("every decision is built"))
.collect()
}
fn build(&self, decision: usize) -> DecisionOutcome {
let started = self.profile.then(Instant::now);
let mut log = CostLog::default();
let mut outcome = self.build_decision(decision, &mut log);
outcome.cost = log.finish(started.map(|started| started.elapsed()));
outcome.budget = self.budget(decision);
outcome
}
fn build_decision(&self, decision: usize, log: &mut CostLog) -> DecisionOutcome {
let state = self.atn.decision_to_state[decision];
let mut outcome = DecisionOutcome::new(decision, state);
if state.is_nongreedy_decision() == Some(true) {
outcome.kind = DecisionKind::Adaptive;
outcome.no_table = Some(NoTableReason::NonGreedy);
return outcome;
}
if self.is_precedence_loop_decision(state) {
return self.build_precedence(outcome, log);
}
if self.ll1_disjoint.get(decision).copied() == Some(true) {
outcome.kind = DecisionKind::Ll1;
outcome.k = 1;
return outcome;
}
if state.get_transitions().len() >= VIRTUAL_ALT_BASE as usize {
outcome.no_table = Some(NoTableReason::TooManyAlternatives);
return outcome;
}
self.build_table(decision, None, true, log)
}
fn build_table(
&self,
decision: usize,
class: Option<PrecedenceClass>,
analyze_hazards: bool,
log: &mut CostLog,
) -> DecisionOutcome {
let decision_state = self.atn.decision_to_state[decision];
#[cfg(test)]
if self.widened {
let widened = self.attempt(decision, 0, class, false, analyze_hazards, log);
return self.finish_partial(widened, 0, class, analyze_hazards, log);
}
let attempt = self.attempt(decision, i32::MAX, class, false, analyze_hazards, log);
if attempt.start_exhausted {
let widened = self.attempt(decision, 0, class, false, analyze_hazards, log);
return self.finish_partial(widened, 0, class, analyze_hazards, log);
}
let should_widen = attempt.budget_cutoff.is_some() && !attempt.non_budget_escape;
let exceeded_frontier = attempt.exceeded_frontier;
let outcome = attempt.finalize(decision_state, self.atn_fallback);
if outcome.kind == DecisionKind::Static {
return outcome;
}
if should_widen {
let widened = self.attempt(decision, 0, class, false, analyze_hazards, log);
let widened_outcome = widened.finalize(decision_state, self.atn_fallback);
if widened_outcome.kind == DecisionKind::Static {
return widened_outcome;
}
}
if self.should_retry_bounded(decision, exceeded_frontier, class, &outcome) {
let bounded = self.attempt(decision, i32::MAX, class, true, analyze_hazards, log);
return bounded.finalize(decision_state, self.atn_fallback);
}
outcome
}
fn finish_partial(
&self,
attempt: Attempt,
depth_bound: i32,
class: Option<PrecedenceClass>,
analyze_hazards: bool,
log: &mut CostLog,
) -> DecisionOutcome {
let decision = attempt.decision;
let decision_state = self.atn.decision_to_state[decision];
let exceeded_frontier = attempt.exceeded_frontier;
let outcome = attempt.finalize(decision_state, self.atn_fallback);
if outcome.kind == DecisionKind::Static {
return outcome;
}
if self.should_retry_bounded(decision, exceeded_frontier, class, &outcome) {
let bounded = self.attempt(decision, depth_bound, class, true, analyze_hazards, log);
return bounded.finalize(decision_state, self.atn_fallback);
}
outcome
}
fn should_retry_bounded(
&self,
decision: usize,
exceeded_frontier: bool,
class: Option<PrecedenceClass>,
outcome: &DecisionOutcome,
) -> bool {
let may_gain_guards = class.is_some() || self.postfix_shape(decision).is_some();
exceeded_frontier
&& (outcome.table.is_some()
|| (may_gain_guards
&& matches!(outcome.no_table, Some(NoTableReason::LowCoverage { .. }))))
}
fn is_precedence_loop_decision(&self, state: ATNStateRef) -> bool {
if state.state_type() != ATNStateType::StarLoopEntry {
return false;
}
let rule_start = self.atn.rule_to_start_state[state.get_rule_index() as usize];
let is_left_recursive = rule_start
.try_as::<RuleStartState>()
.is_some_and(|start| start.is_left_recursive);
if !is_left_recursive {
return false;
}
let transitions = state.get_transitions();
let Some(last) = transitions.last() else {
return false;
};
let loop_end = last.get_target();
if loop_end.state_type() != ATNStateType::LoopEnd {
return false;
}
loop_end.has_epsilon_only_transitions()
&& loop_end
.get_transitions()
.first()
.is_some_and(|transition| {
transition.get_target().state_type() == ATNStateType::RuleStop
})
}
fn build_precedence(&self, mut outcome: DecisionOutcome, log: &mut CostLog) -> DecisionOutcome {
let state = self.atn.decision_to_state[outcome.decision];
let target_rule = state.get_rule_index();
let mut cutoffs = BTreeSet::new();
for atn_state in self.atn.iter_states() {
if atn_state.get_rule_index() != target_rule {
continue;
}
for transition in atn_state.get_transitions() {
if let Some(predicate) = transition.try_as::<PrecedencePredicateTransition>() {
cutoffs.insert(predicate.precedence());
}
}
}
if cutoffs.is_empty() {
outcome.no_table = Some(NoTableReason::EmptyPrecedenceLoop);
return outcome;
}
let cutoffs: Vec<i32> = cutoffs.into_iter().collect();
let mut representatives = Vec::with_capacity(cutoffs.len() + 1);
representatives.push(0);
for cutoff in &cutoffs {
representatives.push(cutoff.saturating_add(1));
}
let mut tables: Vec<Option<StaticDfaTable>> = vec![None; representatives.len()];
let mut max_k = 0_i32;
let mut total_states = 0_usize;
let mut escapes = 0_usize;
let mut first_failure: Option<NoTableReason> = None;
let mut failed = 0_usize;
for class_index in 0..representatives.len() {
let class = PrecedenceClass {
rule_index: target_rule,
eval_value: representatives[class_index],
lo: representatives[class_index],
hi: cutoffs.get(class_index).copied().unwrap_or(i32::MAX),
};
log.class = Some(class_index);
let class_outcome =
self.build_table(outcome.decision, Some(class), first_failure.is_none(), log);
BudgetCutoff::merge_opt(&mut outcome.budget_cutoff, class_outcome.budget_cutoff);
for conflict in &class_outcome.conflicts {
if !outcome.conflicts.contains(conflict) {
outcome.conflicts.push(conflict.clone());
}
}
if outcome.conflict_witness.is_none() {
outcome.conflict_witness = class_outcome.conflict_witness.clone();
}
if outcome.budget_witness.is_none() {
outcome.budget_witness = class_outcome.budget_witness.clone();
}
match class_outcome.table {
Some(table) => {
max_k = max_k.max(table.max_k);
total_states += table.states.len();
escapes += table.escapes();
tables[class_index] = Some(table);
}
None => {
failed += 1;
if first_failure.is_none() {
first_failure = class_outcome.no_table;
}
}
}
}
let total = tables.len();
outcome.kind = if failed == total {
DecisionKind::Adaptive
} else if failed > 0 || escapes > 0 {
DecisionKind::Hybrid
} else {
DecisionKind::Static
};
if failed > 0 {
outcome.no_table = Some(NoTableReason::PrecedenceClasses {
failed,
total,
first: Box::new(
first_failure.expect("a failed precedence class records a no_table reason"),
),
});
}
if failed < total {
outcome.k = max_k;
outcome.num_dfa_states = total_states;
}
outcome.escapes = escapes;
outcome.precedence = Some(PrecedenceTables {
cutoffs,
tables,
adaptive_classes: failed,
escapes,
});
outcome
}
fn attempt(
&self,
decision: usize,
depth_bound: i32,
precedence: Option<PrecedenceClass>,
enforce_frontier: bool,
analyze_hazards: bool,
log: &mut CostLog,
) -> Attempt {
let started = self.profile.then(Instant::now);
let mut attempt = self.run_attempt(
decision,
depth_bound,
precedence,
enforce_frontier,
analyze_hazards,
);
let outcome = if attempt.exhausted {
AttemptOutcome::VisitBudget
} else if attempt.failed.is_some() || attempt.budget_cutoff.is_some() {
AttemptOutcome::StateBudget
} else {
AttemptOutcome::Finished
};
let kind = if depth_bound == 0 {
AttemptKind::Widened
} else if self.atn_fallback == AtnFallback::Forbidden {
AttemptKind::StaticOnly
} else {
AttemptKind::Default
};
log.record(
AttemptCost {
kind,
class: log.class,
outcome,
visits: attempt.visits,
states: attempt.state_count,
elapsed: started.map(|started| started.elapsed()),
},
&std::mem::take(&mut attempt.rule_visits),
);
attempt
}
fn run_attempt(
&self,
decision: usize,
depth_bound: i32,
precedence: Option<PrecedenceClass>,
enforce_frontier: bool,
analyze_hazards: bool,
) -> Attempt {
let atn = self.atn;
let decision_state = atn.decision_to_state[decision];
let loop_block = precedence.map(|_| self.loop_block(decision));
let postfix = self.postfix_shape(decision);
let budget = self.budget(decision);
let descent = if precedence.is_none() {
self.descent.plan(decision)
} else {
None
};
let manager = ParserATNSimulatorManager::new(atn);
Arena::with(|arena| {
let simulator = ParserATNSimulator::new(manager.get_simulator(arena));
let scratch = Bump::new();
let mut build = DecisionBuild {
atn,
simulator: &simulator,
dfa: simulator
.decision_to_dfa(decision)
.expect("every decision has a DFA"),
scratch: &scratch,
closure: Closure::new(
atn,
&self.call_sites,
&scratch,
depth_bound,
precedence,
loop_block,
postfix.clone(),
budget.max_visits,
),
depth_bound,
frontier: Frontier::of(&budget, self.atn_fallback),
enforce_frontier,
max_states: budget.max_states,
max_k: budget.max_k,
has_escape: false,
budget_spent: false,
allow_continuations: self.atn_fallback == AtnFallback::Allowed
&& precedence.is_none(),
precedence_class: precedence.is_some(),
postfix,
descent,
guard_candidates: BTreeSet::new(),
guard_iterate_candidates: BTreeMap::new(),
guard: None,
guard_regions: &self.guard_regions,
static_only: self.atn_fallback == AtnFallback::Forbidden,
analyze_hazards,
decision_state,
decision,
info: HashMap::new(),
accept_sinks: HashMap::new(),
queue: BinaryHeap::new(),
next_queue_seq: 0,
depth1_budget: None,
completion_depths: &self.completion_depths,
attempt: Attempt {
decision,
..Attempt::default()
},
};
build.run()
})
}
}
fn once_locks<T>(len: usize) -> Box<[OnceLock<T>]> {
(0..len).map(|_| OnceLock::new()).collect()
}
fn used_groups(plan: Option<&DescentPlan>, table: &StaticDfaTable) -> Option<DescentPlan> {
let groups: Vec<_> = plan?
.groups
.iter()
.filter(|group| {
table
.states
.iter()
.any(|state| state.accept == group.virtual_alt)
})
.cloned()
.collect();
(!groups.is_empty()).then_some(DescentPlan { groups })
}
#[derive(Debug)]
struct GuardSets {
groups: Vec<Vec<i32>>,
pass: Vec<i32>,
}
impl GuardSets {
fn group_of(&mut self, danger: Vec<i32>) -> u32 {
let index = match self.groups.iter().position(|group| *group == danger) {
Some(index) => index,
None => {
self.groups.push(danger);
self.groups.len() - 1
}
};
index as u32
}
}
struct QueuedState<'sim> {
depth: usize,
expanded: bool,
configs: usize,
seq: usize,
state: &'sim ParserDFAState<'sim>,
}
impl Eq for QueuedState<'_> {}
impl PartialEq for QueuedState<'_> {
fn eq(&self, other: &Self) -> bool {
(self.depth, self.expanded, self.configs, self.seq)
== (other.depth, other.expanded, other.configs, other.seq)
}
}
impl Ord for QueuedState<'_> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
(other.depth, other.expanded, other.configs, other.seq).cmp(&(
self.depth,
self.expanded,
self.configs,
self.seq,
))
}
}
impl PartialOrd for QueuedState<'_> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
struct DecisionBuild<'b, 'sim, 'a> {
atn: &'static ATN,
simulator: &'b ParserATNSimulator<'sim>,
dfa: &'sim ParserDFA<'sim>,
scratch: &'a Bump,
closure: Closure<'static, 'a>,
depth_bound: i32,
frontier: Frontier,
enforce_frontier: bool,
max_states: usize,
max_k: Option<usize>,
has_escape: bool,
budget_spent: bool,
allow_continuations: bool,
precedence_class: bool,
postfix: Option<PostfixShape>,
descent: Option<DescentPlan>,
guard_candidates: BTreeSet<i32>,
guard_iterate_candidates: BTreeMap<i32, bool>,
guard: Option<GuardSets>,
guard_regions: &'a OnceLock<GuardRegions>,
static_only: bool,
analyze_hazards: bool,
decision: usize,
decision_state: ATNStateRef,
info: HashMap<i32, StateFacts>,
accept_sinks: HashMap<i32, &'sim ParserDFAState<'sim>>,
queue: BinaryHeap<QueuedState<'sim>>,
next_queue_seq: usize,
depth1_budget: Option<(usize, u64)>,
completion_depths: &'a [OnceLock<BitSet>],
attempt: Attempt,
}
impl<'b, 'sim, 'a> DecisionBuild<'b, 'sim, 'a>
where
'sim: 'a,
{
fn push_queue(&mut self, state: &'sim ParserDFAState<'sim>, depth: usize, expanded: bool) {
let seq = self.next_queue_seq;
self.next_queue_seq += 1;
self.queue.push(QueuedState {
depth,
expanded,
configs: state.configs().length(),
seq,
state,
});
}
fn remaining_depth1_states(&self, current_state: i32) -> usize {
let mut seen = HashSet::new();
seen.insert(current_state);
for item in &self.queue {
if item.depth != 1 {
continue;
}
let number = item.state.state_number();
if self
.info
.get(&number)
.is_some_and(|facts| !facts.expanded && facts.verdict == Verdict::Decide)
{
seen.insert(number);
}
}
seen.len()
}
fn run(&mut self) -> Attempt {
let start = self.closure.start(self.decision_state);
if self.closure.exhausted {
self.attempt.failed = Some(BudgetCutoff::Visits);
self.attempt.start_exhausted = true;
return self.take_attempt();
}
let Some(start_state) = self.intern(start, 0) else {
self.attempt.failed = Some(BudgetCutoff::States);
return self.take_attempt();
};
self.dfa.set_s0(start_state);
if self.attempt.predicated {
return self.take_attempt();
}
while let Some(QueuedState { state, .. }) = self.queue.pop() {
let state_number = state.state_number();
let Some(facts) = self.info.get(&state_number).cloned() else {
continue;
};
if facts.verdict != Verdict::Decide {
continue;
}
if facts.expanded && self.attempt.exhausted {
if facts.depth > 0 {
self.escape_frontier(state_number, &facts);
continue;
}
self.attempt.failed = Some(BudgetCutoff::Visits);
self.attempt.start_exhausted = true;
break;
}
if !facts.expanded {
let at_frontier = self.at_frontier(facts.depth);
let at_max_k = self.max_k.is_some_and(|max_k| facts.depth >= max_k);
if self.budget_spent
|| (at_frontier && (self.enforce_frontier || self.has_escape || at_max_k))
{
self.escape_frontier(state_number, &facts);
continue;
}
if at_frontier && self.resolve_frontier(state_number, &facts, false) {
continue;
}
if at_frontier && !self.enforce_frontier {
self.attempt.exceeded_frontier = true;
}
}
if let Some(facts) = self.info.get_mut(&state_number) {
facts.expanded = true;
}
let closed = ClosedSet {
configs: state.configs().get_items().cloned().collect(),
taint: facts.taint.clone(),
roots: facts.roots.clone(),
};
let (successors, visit_cutoff) = if facts.depth == 1 && !facts.expanded {
let remaining_depth1 = self.remaining_depth1_states(state_number);
let remaining_visits = self.closure.remaining_visits();
let (initial_depth1, initial_remaining) = *self
.depth1_budget
.get_or_insert((remaining_depth1, remaining_visits));
let avg = (initial_remaining / initial_depth1 as u64).max(1);
let fair_share = (remaining_visits / remaining_depth1 as u64).max(1);
let reserve_per_state = (avg / 2).min(fair_share);
let above_reserve = remaining_visits.saturating_sub(
(remaining_depth1 as u64 - 1).saturating_mul(reserve_per_state),
);
let per_state_cap = avg.saturating_mul(5).max(fair_share);
let slice = per_state_cap.min(above_reserve).max(fair_share);
self.closure.successors_capped(&closed, slice)
} else {
let successors = self.closure.successors(&closed);
(successors, self.closure.exhausted)
};
let global_visit_exhausted = self.closure.exhausted;
let new_states = if facts.expanded { 0 } else { successors.len() };
let state_cutoff = facts.depth > 0 && self.dfa.len() + new_states > self.max_states;
let cut_off = facts.depth > 0 && (visit_cutoff || state_cutoff);
if cut_off {
let cutoff = match (state_cutoff, visit_cutoff) {
(true, true) => BudgetCutoff::Both,
(true, false) => BudgetCutoff::States,
(false, true) => BudgetCutoff::Visits,
(false, false) => unreachable!(),
};
self.attempt.exhausted |= global_visit_exhausted;
self.closure.exhausted = false;
if state_cutoff || global_visit_exhausted {
self.budget_spent = true;
}
BudgetCutoff::merge_opt(&mut self.attempt.budget_cutoff, Some(cutoff));
self.escape_frontier(state_number, &facts);
continue;
}
if self.closure.exhausted {
self.attempt.failed = Some(BudgetCutoff::Visits);
self.attempt.start_exhausted = true;
break;
}
let mut targets = Vec::with_capacity(successors.len());
for (label, successor) in successors {
let Some(target) = self.intern(successor, facts.depth + 1) else {
self.attempt.failed = Some(BudgetCutoff::States);
break;
};
targets.push((label, target));
}
if self.attempt.failed.is_some() {
break;
}
for (label, target) in targets {
for interval in label.as_interval_set().as_slice() {
for token in interval.a..=interval.b {
if token < EOF || token > self.atn.max_token_type {
continue;
}
self.dfa.set_edge(state, (token + 1) as usize, target);
}
}
}
}
if self.attempt.failed.is_none() {
self.prune_unreachable();
self.finalize_guards();
let start_decides = self.info.get(&0).is_some_and(|facts| {
!matches!(facts.verdict, Verdict::Escape(ESCAPE | CONFLICT_ESCAPE))
});
let has_escape = self
.info
.values()
.any(|facts| matches!(facts.verdict, Verdict::Escape(ESCAPE | CONFLICT_ESCAPE)));
let will_retry_partial = self.attempt.exceeded_frontier && start_decides && has_escape;
if !will_retry_partial {
self.attach_continuations();
}
let analyze =
self.static_only && self.analyze_hazards && start_decides && !will_retry_partial;
let hazards = if analyze {
self.state_hazards()
} else {
HashMap::new()
};
let mut table = self.snapshot(&hazards);
if analyze {
self.compute_guard_hazards(&mut table);
}
self.attempt.table = Some(table);
}
self.take_attempt()
}
fn escape_frontier(&mut self, number: i32, facts: &StateFacts) {
if self.resolve_frontier(number, facts, true) {
return;
}
self.set_escape(number, ESCAPE);
if self.postfix.is_some() && self.state_has_take_skip_pair(number) {
self.guard_candidates.insert(number);
}
}
fn resolve_frontier(&mut self, number: i32, facts: &StateFacts, escaping: bool) -> bool {
if self.accept_descent_group(number, facts) {
return true;
}
self.precedence_class
&& facts.depth >= 2
&& self.resolve_frontier_iterate(number, facts, escaping)
}
fn at_frontier(&self, depth: usize) -> bool {
let state_cap = self.frontier.state_cap.min(self.max_states);
depth >= self.frontier.depth_cap || (self.dfa.len() >= state_cap && depth >= 2)
}
fn take_attempt(&mut self) -> Attempt {
self.attempt.decision = self.decision;
self.attempt.state_count = self.dfa.len();
self.attempt.facts = std::mem::take(&mut self.closure.facts);
self.attempt.exhausted |= self.closure.exhausted;
self.attempt.visits = self.closure.visits();
self.attempt.rule_visits = self.closure.take_rule_visits();
self.attempt.descent = self.descent.take();
std::mem::take(&mut self.attempt)
}
fn finalize_guards(&mut self) {
self.finalize_guarded_takes();
if self.guard.is_none() {
self.finalize_guarded_iterates();
}
}
fn state_roots(&self, state: i32, alt: i32) -> BTreeSet<i32> {
self.info.get(&state).map_or_else(BTreeSet::new, |facts| {
facts
.roots
.iter()
.filter(|((_, config_alt), _)| *config_alt == alt)
.flat_map(|(_, roots)| roots.iter().copied())
.collect()
})
}
fn new_guard_sets(&self) -> GuardSets {
let regions = self
.guard_regions
.get_or_init(|| GuardRegions::of(self.atn));
GuardSets {
groups: Vec::new(),
pass: regions.pass().to_vec(),
}
}
fn guard_danger(&self, roots: &BTreeSet<i32>) -> Vec<i32> {
self.guard_regions
.get_or_init(|| GuardRegions::of(self.atn))
.danger(roots)
}
fn finalize_guarded_takes(&mut self) {
let Some(postfix) = self.postfix.clone() else {
return;
};
if self.guard_candidates.is_empty() {
return;
}
let candidates = std::mem::take(&mut self.guard_candidates);
let reachable_from_block = epsilon_closure(postfix.block_end_state);
let mut accepted: Vec<(i32, BTreeSet<i32>, bool)> = Vec::new();
for state in candidates {
let Some(facts) = self.info.get(&state) else {
continue;
};
if facts.predicated
|| !matches!(
facts.verdict,
Verdict::Escape(ESCAPE) | Verdict::Escape(CONFLICT_ESCAPE)
)
{
continue;
}
let roots = self.state_roots(state, POSTFIX_SKIP_ALT);
if roots.is_empty()
|| roots
.iter()
.any(|root| reachable_from_block.contains(*root as usize))
{
continue;
}
let mut eligible = true;
let mut real_take = false;
let Some(dfa_state) = self.dfa.get_state(state) else {
continue;
};
for config in dfa_state.configs().get_items() {
let taint = taint_of(&facts.taint, config);
if config.get_alt() == POSTFIX_TAKE_ALT && taint & WIDENED_TAINT == 0 {
real_take = true;
}
if config.get_alt() != POSTFIX_SKIP_ALT {
continue;
}
if taint & (WIDENED_TAINT | ROOTED_TAINT) == WIDENED_TAINT {
eligible = false;
break;
}
if taint & ROOTED_TAINT != 0
|| postfix.skip_mirrors(config.get_state(), config.get_context(), taint)
{
continue;
}
eligible = false;
break;
}
if !eligible || !(real_take || self.static_only) {
continue;
}
accepted.push((state, roots, real_take));
}
if accepted.is_empty() {
return;
}
let chase_leaves_the_rule = {
let rule_stop =
self.atn.rule_to_stop_state[self.decision_state.get_rule_index() as usize];
rule_stop.get_state_number() >= 0
&& reachable_from_block.contains(rule_stop.get_state_number() as usize)
};
let mut guard = self.new_guard_sets();
for (state, roots, real_take) in accepted {
let danger = if chase_leaves_the_rule {
self.guard_danger(&roots)
} else {
Vec::new()
};
if danger.is_empty() && !real_take {
continue;
}
if danger.is_empty() {
if let Some(facts) = self.info.get_mut(&state) {
facts.verdict = Verdict::Accept(POSTFIX_TAKE_ALT);
facts.resolved_conflict = true;
}
continue;
}
let group = guard.group_of(danger);
if let Some(facts) = self.info.get_mut(&state) {
facts.verdict = Verdict::Escape(GUARDED);
facts.guarded_alt = POSTFIX_TAKE_ALT;
facts.guard_defer_alt = POSTFIX_SKIP_ALT;
facts.guard_group = group;
}
}
if !guard.groups.is_empty() {
self.guard = Some(guard);
}
}
fn finalize_guarded_iterates(&mut self) {
if self.guard_iterate_candidates.is_empty() {
return;
}
let candidates = std::mem::take(&mut self.guard_iterate_candidates);
let rule_stop = self.atn.rule_to_stop_state[self.decision_state.get_rule_index() as usize];
let reachable_from_stop =
(rule_stop.get_state_number() >= 0).then(|| epsilon_closure(rule_stop));
let mut accepted: Vec<(i32, bool, BTreeSet<i32>, bool)> = Vec::new();
for (state, conflict) in candidates {
let Some(facts) = self.info.get(&state) else {
continue;
};
if facts.predicated
|| !matches!(
facts.verdict,
Verdict::Escape(ESCAPE) | Verdict::Escape(CONFLICT_ESCAPE)
)
{
continue;
}
let roots = self.state_roots(state, EXIT_ALT);
if roots.is_empty()
|| reachable_from_stop.as_ref().is_some_and(|reachable| {
roots.iter().any(|root| reachable.contains(*root as usize))
})
{
continue;
}
let mut eligible = true;
let mut real_iterate = false;
let Some(dfa_state) = self.dfa.get_state(state) else {
continue;
};
for config in dfa_state.configs().get_items() {
let taint = taint_of(&facts.taint, config);
if config.get_alt() == ITERATE_ALT
&& taint & (WIDENED_TAINT | FOREIGN_CONSUME_TAINT) == 0
{
real_iterate = true;
}
if config.get_alt() != EXIT_ALT {
continue;
}
if taint & FOREIGN_CONSUME_TAINT != 0 && taint & ROOTED_TAINT == 0 {
eligible = false;
break;
}
if taint & (WIDENED_TAINT | ROOTED_TAINT) == WIDENED_TAINT {
eligible = false;
break;
}
}
if !eligible || !(real_iterate || self.static_only) {
continue;
}
accepted.push((state, conflict, roots, real_iterate));
}
if accepted.is_empty() {
return;
}
let mut guard = self.new_guard_sets();
for (state, conflict, roots, real_iterate) in accepted {
let danger = self.guard_danger(&roots);
if danger.is_empty() && !real_iterate {
continue;
}
if danger.is_empty() && !conflict && self.static_only {
continue;
}
let Some(facts) = self.info.get_mut(&state) else {
continue;
};
facts.resolved_conflict = true;
if danger.is_empty() {
facts.verdict = Verdict::Accept(ITERATE_ALT);
continue;
}
facts.verdict = Verdict::Escape(GUARDED);
facts.guarded_alt = ITERATE_ALT;
facts.guard_defer_alt = EXIT_ALT;
facts.guard_group = guard.group_of(danger);
}
if !guard.groups.is_empty() {
self.guard = Some(guard);
}
}
fn attach_continuations(&mut self) {
if !self.allow_continuations {
return;
}
for state in self.dfa.get_states() {
let number = state.state_number();
let Some(facts) = self.info.get(&number) else {
continue;
};
if facts.depth == 0 || facts.verdict != Verdict::Escape(ESCAPE) {
continue;
}
let configs = state.configs();
if !continuation_is_faithful(configs, &facts.taint) {
continue;
}
let continuation = serialize_continuation(number as u32, configs, &facts.taint);
if continuation_words(&continuation) > MAX_CONTINUATION_WORDS {
continue;
}
if let Some(facts) = self.info.get_mut(&number) {
facts.continuation = Some(continuation);
}
}
}
fn intern(
&mut self,
closed: ClosedSet<'a>,
depth: usize,
) -> Option<&'sim ParserDFAState<'sim>> {
let closed = self.closure.canonical_set(closed);
let (facts, effects) = self.classify(&closed, depth);
if let Verdict::Accept(alt) = facts.verdict
&& alt > 0
&& depth > 0
&& !facts.resolved_conflict
&& !facts.predicated
{
return self.accept_sink(alt, facts, effects);
}
let interned = self.closure.merged_config_set(&closed);
let mut proposed = ProposedDFAState::new(interned);
proposed.is_accept_state = matches!(facts.verdict, Verdict::Accept(_));
proposed.prediction = facts.accept_value();
let state = self.dfa.add_state(proposed, self.simulator);
let number = state.state_number();
let newly_interned = !self.info.contains_key(&number);
if !newly_interned {
let state_configs = state.configs();
let mut new_trust_taint = 0;
let mut verdict = Verdict::Decide;
let mut resolved_conflict = false;
let mut roots_grew = false;
let mut expanded = false;
if let Some(existing) = self.info.get_mut(&number) {
verdict = existing.verdict;
resolved_conflict = existing.resolved_conflict;
expanded = existing.expanded;
for (key, taint) in &facts.taint {
let entry = existing.taint.entry(*key).or_insert(0);
new_trust_taint |= *taint & !*entry & TRUST_TAINT;
*entry |= *taint;
}
for (key, roots) in &facts.roots {
let entry = existing.roots.entry(*key).or_default();
let before = entry.len();
entry.extend(roots.iter().copied());
roots_grew |= entry.len() != before;
}
existing.fallback = fallback_of(state_configs, &existing.taint);
existing.predicated |= facts.predicated;
}
if new_trust_taint != 0 {
self.on_taint_increase(state, verdict, resolved_conflict);
} else if roots_grew && expanded && verdict == Verdict::Decide {
let existing_depth = self.info.get(&number).map_or(0, |existing| existing.depth);
self.push_queue(state, existing_depth, true);
}
return Some(state);
}
if number as usize >= self.max_states {
return None;
}
if effects.conflict.is_some() {
self.attempt.first_conflict_state.get_or_insert(number);
}
self.commit(number, effects);
let decide = facts.verdict == Verdict::Decide;
let is_escape = matches!(facts.verdict, Verdict::Escape(_));
self.has_escape |= is_escape;
if is_escape && !self.budget_spent {
self.attempt.non_budget_escape = true;
}
self.info.insert(number, facts);
if decide && self.attempt.failed.is_none() {
self.push_queue(state, depth, false);
}
Some(state)
}
fn accept_sink(
&mut self,
alt: i32,
facts: StateFacts,
effects: ClassifyEffects,
) -> Option<&'sim ParserDFAState<'sim>> {
if let Some(state) = self.accept_sinks.get(&alt) {
return Some(*state);
}
let config = dbt_antlr_runtime::analysis::ATNConfig::new(
self.decision_state,
alt,
Some(PredictionContextRef::new_empty()),
);
let sink = ClosedSet {
configs: vec![config],
taint: Taint::default(),
roots: GuardRoots::default(),
};
let mut proposed = ProposedDFAState::new(self.closure.merged_config_set(&sink));
proposed.is_accept_state = true;
proposed.prediction = alt;
let state = self.dfa.add_state(proposed, self.simulator);
let number = state.state_number();
if number as usize >= self.max_states {
return None;
}
self.commit(number, effects);
self.accept_sinks.insert(alt, state);
self.info.insert(
number,
StateFacts {
fallback: 0,
taint: Taint::default(),
roots: GuardRoots::default(),
..facts
},
);
Some(state)
}
fn accept_descent_group(&mut self, number: i32, facts: &StateFacts) -> bool {
let Some(plan) = &self.descent else {
return false;
};
let Some(dfa_state) = self.dfa.get_state(number) else {
return false;
};
let configs: Vec<_> = dfa_state.configs().get_items().cloned().collect();
let mut live = BitSet::new();
for config in &configs {
live.insert(config.get_alt() as usize);
}
let Some(alt) = plan
.group_for(&live, facts.depth, &configs, &facts.taint)
.map(|group| group.virtual_alt)
else {
return false;
};
if let Some(facts) = self.info.get_mut(&number) {
facts.verdict = Verdict::Accept(alt);
facts.resolved_conflict = true;
}
true
}
fn state_has_take_skip_pair(&self, number: i32) -> bool {
let mut alts = BitSet::new();
let Some(dfa_state) = self.dfa.get_state(number) else {
return false;
};
for config in dfa_state.configs().get_items() {
alts.insert(config.get_alt() as usize);
}
is_take_skip_pair(&alts)
}
fn is_iterate_guard_candidate(&self, attestation: i32) -> bool {
attestation == (ITERATE_REAL | EXIT_FOREIGN)
|| (self.static_only && attestation == EXIT_FOREIGN)
}
fn resolve_frontier_iterate(
&mut self,
number: i32,
facts: &StateFacts,
escaping: bool,
) -> bool {
let Some(dfa_state) = self.dfa.get_state(number) else {
return false;
};
let configs: Vec<dbt_antlr_runtime::analysis::ATNConfig<'_>> =
dfa_state.configs().get_items().cloned().collect();
let mut alts = BitSet::new();
for config in &configs {
alts.insert(config.get_alt() as usize);
}
if !is_iterate_exit_pair(&alts) {
return false;
}
let Some(block) = self.closure.loop_block() else {
return false;
};
if !block.guards_are_simple() {
return false;
}
let covered = block.iterate_covers_exit(&configs, &facts.taint);
if !covered && !self.static_only {
return false;
}
let attestation = block.iterate_exit_attestation(&configs, &facts.taint);
if covered && attestation == ITERATE_REAL && self.keeps_caller_frames() {
if let Some(facts) = self.info.get_mut(&number) {
facts.verdict = Verdict::Accept(ITERATE_ALT);
facts.resolved_conflict = true;
}
return true;
}
if escaping && self.postfix.is_none() && self.is_iterate_guard_candidate(attestation) {
self.guard_iterate_candidates.insert(number, false);
}
false
}
fn on_taint_increase(
&mut self,
state: &'sim ParserDFAState<'sim>,
verdict: Verdict,
resolved_conflict: bool,
) {
let number = state.state_number();
match verdict {
Verdict::Accept(_) if resolved_conflict => {
let conflicted = self
.info
.get(&number)
.is_some_and(|facts| !facts.conflicts.is_empty());
if conflicted {
self.attempt.first_conflict_state.get_or_insert(number);
}
self.has_escape = true;
if !self.budget_spent {
self.attempt.non_budget_escape = true;
}
if let Some(facts) = self.info.get_mut(&number) {
let approximated = facts
.taint
.values()
.any(|taint| taint & (WIDENED_TAINT | PRECPRED_TAINT) != 0);
facts.verdict = if conflicted {
Verdict::Escape(CONFLICT_ESCAPE)
} else {
Verdict::Escape(ESCAPE)
};
if !approximated && !self.precedence_class {
facts.conflict_min_alt = facts.conflicts.iter().min().copied().unwrap_or(0);
}
}
}
Verdict::Accept(_) | Verdict::Escape(_) => {}
Verdict::Decide => {
if let Some(facts) = self.info.get(&number)
&& facts.expanded
{
self.push_queue(state, facts.depth, true);
}
}
}
}
fn commit(&mut self, number: i32, effects: ClassifyEffects) {
if effects.guard_candidate {
self.guard_candidates.insert(number);
}
if effects.guard_iterate_candidate {
self.guard_iterate_candidates.insert(number, true);
}
if let Some(alts) = effects.conflict {
self.attempt.conflicts.push(alts);
}
if effects.fail_predicated {
self.attempt.predicated = true;
}
}
fn classify(&mut self, closed: &ClosedSet<'a>, depth: usize) -> (StateFacts, ClassifyEffects) {
let mut effects = ClassifyEffects::default();
let mut fallback = 0;
let mut alts = BitSet::new();
let mut predicated = false;
for config in &closed.configs {
alts.insert(config.get_alt() as usize);
let taint = closed.taint_of(config);
if taint & BOUNDARY_TAINT != 0 && (fallback == 0 || config.get_alt() < fallback) {
fallback = config.get_alt();
}
if taint & PRED_TAINT != 0 {
predicated = true;
}
}
let mut facts = StateFacts {
depth,
verdict: Verdict::Decide,
taint: closed.taint.clone(),
fallback,
conflicts: Vec::new(),
resolved_conflict: false,
expanded: false,
conflict_min_alt: 0,
guarded_alt: 0,
guard_defer_alt: 0,
guard_group: 0,
roots: closed.roots.clone(),
continuation: None,
predicated: false,
};
if predicated {
if depth == 0 {
effects.fail_predicated = true;
} else {
facts.verdict = Verdict::Escape(ESCAPE);
facts.predicated = true;
}
return (facts, effects);
}
if alts.len() <= 1 {
facts.verdict = Verdict::Accept(alts.iter().next().map_or(0, |alt| alt as i32));
return (facts, effects);
}
let all_stops = !closed.configs.is_empty()
&& closed
.configs
.iter()
.all(|config| config.get_state().state_type() == ATNStateType::RuleStop);
let merged = self.closure.merged_config_set(closed);
if !all_stops
&& !has_sll_conflict_terminating_prediction(self.scratch, PredictionMode::SLL, &merged)
{
return (facts, effects);
}
let subsets = conflicting_alt_subsets(self.scratch, &merged);
let exact = all_subsets_conflict(subsets.iter()) && all_subsets_equal(subsets.iter());
let mut widened_tainted = false;
let mut precedence_tainted = false;
let mut any_boundary = false;
let mut all_boundary = true;
for config in &closed.configs {
let taint = closed.taint_of(config);
if taint & WIDENED_TAINT != 0 {
widened_tainted = true;
}
if taint & PRECPRED_TAINT != 0 {
precedence_tainted = true;
}
if taint & BOUNDARY_TAINT != 0 {
any_boundary = true;
}
if taint & BOUNDARY_TAINT == 0 || taint & INTERIOR_TAINT != 0 {
all_boundary = false;
}
}
let conflicting = get_alts(subsets.into_iter());
facts.conflicts = conflicting.iter().map(|alt| alt as i32).collect();
if let Some(block) = self.closure.loop_block()
&& block.guards_are_simple()
&& is_iterate_exit_pair(&conflicting)
{
let attestation = block.iterate_exit_attestation(&closed.configs, &closed.taint);
if attestation == ITERATE_REAL && self.keeps_caller_frames() {
facts.resolved_conflict = true;
facts.verdict = Verdict::Accept(ITERATE_ALT);
return (facts, effects);
}
if self.postfix.is_none() && self.is_iterate_guard_candidate(attestation) {
effects.guard_iterate_candidate = true;
}
}
if let Some(postfix) = self.postfix.clone()
&& is_take_skip_pair(&conflicting)
{
let mut mirror_ok = true;
let mut real_take = false;
for config in &closed.configs {
let taint = closed.taint_of(config);
if config.get_alt() == POSTFIX_SKIP_ALT
&& !postfix.skip_mirrors(config.get_state(), config.get_context(), taint)
{
mirror_ok = false;
}
if config.get_alt() == POSTFIX_TAKE_ALT && taint & WIDENED_TAINT == 0 {
real_take = true;
}
}
if mirror_ok && real_take && self.keeps_caller_frames() {
facts.resolved_conflict = true;
facts.verdict = Verdict::Accept(POSTFIX_TAKE_ALT);
return (facts, effects);
}
if real_take || self.static_only {
effects.guard_candidate = true;
}
}
let untrusted = precedence_tainted
|| widened_tainted
|| (any_boundary && !all_boundary)
|| !self.uniform_pop_depths(&conflicting, any_boundary, all_boundary)
|| self.precedence_class;
if !untrusted && exact {
facts.resolved_conflict = true;
facts.verdict = Verdict::Accept(conflicting.iter().next().map_or(0, |alt| alt as i32));
return (facts, effects);
}
if depth > 0 {
let min_alt = self.utrust_min_alt(closed, &conflicting, any_boundary, all_boundary);
if min_alt > 0 {
facts.resolved_conflict = true;
facts.verdict = Verdict::Accept(min_alt);
return (facts, effects);
}
}
if let Some(alt) = self
.descent
.as_ref()
.and_then(|plan| plan.group_for(&alts, depth, &closed.configs, &closed.taint))
.map(|group| group.virtual_alt)
{
effects.guard_candidate = false;
facts.resolved_conflict = true;
facts.verdict = Verdict::Accept(alt);
return (facts, effects);
}
effects.conflict = Some(facts.conflicts.clone());
facts.verdict = Verdict::Escape(CONFLICT_ESCAPE);
if depth > 0 && !widened_tainted && !precedence_tainted && !self.precedence_class {
facts.conflict_min_alt = conflicting.iter().next().map_or(0, |alt| alt as i32);
}
(facts, effects)
}
const fn keeps_caller_frames(&self) -> bool {
self.depth_bound > 0
}
fn set_escape(&mut self, number: i32, marker: i32) {
self.has_escape = true;
if let Some(facts) = self.info.get_mut(&number) {
if matches!(facts.verdict, Verdict::Escape(_)) {
return;
}
facts.verdict = Verdict::Escape(marker);
}
}
fn state_hazards(&mut self) -> HashMap<i32, StateHazard> {
let mut candidates: Vec<(usize, i32)> = self
.info
.iter()
.filter(|(_, facts)| {
matches!(facts.verdict, Verdict::Escape(ESCAPE | CONFLICT_ESCAPE))
&& !facts.predicated
})
.map(|(number, facts)| (facts.depth, *number))
.collect();
candidates.sort_unstable();
let mut hazards = HashMap::new();
let mut groups: HashMap<(i32, Vec<i32>), (usize, bool)> = HashMap::new();
let mut analyzed = 0;
for (_, number) in candidates {
if analyzed == HAZARD_STATES {
break;
}
let Some(facts) = self.info.get(&number).cloned() else {
continue;
};
let Some(dfa_state) = self.dfa.get_state(number) else {
continue;
};
let configs: Vec<_> = dfa_state.configs().get_items().cloned().collect();
let alts: BTreeSet<i32> = configs
.iter()
.map(|config| config.get_alt())
.filter(|alt| *alt > 0)
.collect();
let conflicts: BTreeSet<i32> = facts
.conflicts
.iter()
.copied()
.filter(|alt| *alt > 0)
.collect();
let candidates = if conflicts.is_empty() {
&alts
} else {
&conflicts
};
let Some(&chosen) = candidates.first() else {
continue;
};
let dropped: Vec<i32> = candidates.iter().copied().skip(1).collect();
if dropped.is_empty() {
continue;
}
let group = groups.entry((chosen, dropped.clone())).or_default();
if group.1 || group.0 == HAZARD_STATES_PER_GROUP {
continue;
}
group.0 += 1;
analyzed += 1;
let verdict =
hazard::analyze(&mut self.closure, &configs, &facts.taint, chosen, &dropped);
group.1 = matches!(verdict, hazard::HijackVerdict::Hijack { .. });
let greedy = self.is_greedy_choice(&dropped);
hazards.insert(number, StateHazard { verdict, greedy });
}
hazards
}
fn compute_guard_hazards(&mut self, table: &mut StaticDfaTable) {
let mut candidates: Vec<(bool, usize, usize)> = table
.states
.iter()
.enumerate()
.filter(|(_, state)| {
state.is_guarded()
&& state.guarded_alt > 0
&& state.guard_defer_alt > 0
&& !state.predicated
})
.map(|(index, state)| (!state.conflicts.is_empty(), state.depth, index))
.collect();
candidates.sort_unstable();
let decision_rule = self.decision_state.get_rule_index();
let mut groups: HashMap<u32, (hazard::GuardChains, usize, bool)> = HashMap::new();
let mut analyzed = 0;
for (_, _, index) in candidates {
if analyzed == GUARD_HAZARD_STATES {
break;
}
let state = &table.states[index];
let (group_index, guarded_alt, defer_alt) =
(state.guard_group, state.guarded_alt, state.guard_defer_alt);
let Some(witness) = table.witness(index) else {
continue;
};
let group = groups.entry(group_index).or_insert_with(|| {
let danger = table
.guard_groups
.get(group_index as usize)
.map_or(&[][..], Vec::as_slice);
let chains = hazard::guard_chains(
self.closure.call_sites(),
decision_rule,
self.closure.precedence(),
danger,
&table.guard_pass,
);
(chains, 0, false)
});
if group.2 || group.1 == GUARD_HAZARD_STATES_PER_GROUP {
continue;
}
group.1 += 1;
analyzed += 1;
let verdict = hazard::analyze_guard(
&mut self.closure,
self.decision_state,
&group.0,
&witness,
(guarded_alt, defer_alt),
);
group.2 = matches!(verdict, StackHijackVerdict::Hijack { .. });
table.states[index].stack_hazard = Some(verdict);
}
}
fn is_greedy_choice(&self, dropped: &[i32]) -> bool {
let transitions = self.decision_state.get_transitions();
match self.decision_state.state_type() {
ATNStateType::StarLoopEntry | ATNStateType::PlusLoopBack => dropped == [2],
_ => {
let last = transitions.len();
dropped == [last as i32]
&& transitions.last().is_some_and(|transition| {
transition.get_target().state_type() == ATNStateType::BlockEnd
})
}
}
}
fn prune_unreachable(&mut self) {
let state_count = self.dfa.len();
let mut edges: Vec<Vec<i32>> = vec![Vec::new(); state_count];
for (from, _, to) in self.dfa.enumerate_edges() {
let from = from.state_number();
if self
.info
.get(&from)
.is_some_and(|facts| facts.verdict == Verdict::Decide)
{
edges[from as usize].push(to.state_number());
}
}
let mut reachable = vec![false; state_count];
let mut queue = VecDeque::new();
if self.info.contains_key(&0) {
reachable[0] = true;
queue.push_back(0_i32);
}
let mut reached = 0;
while let Some(number) = queue.pop_front() {
reached += 1;
for &target in &edges[number as usize] {
if let Some(slot) = reachable.get_mut(target as usize)
&& !*slot
&& self.info.contains_key(&target)
{
*slot = true;
queue.push_back(target);
}
}
}
if reached == state_count {
return;
}
self.info
.retain(|number, _| reachable.get(*number as usize).copied().unwrap_or(false));
self.guard_candidates
.retain(|number| reachable.get(*number as usize).copied().unwrap_or(false));
self.guard_iterate_candidates
.retain(|number, _| reachable.get(*number as usize).copied().unwrap_or(false));
if let Some(first) = self.attempt.first_conflict_state
&& !reachable.get(first as usize).copied().unwrap_or(false)
{
self.attempt.first_conflict_state = None;
}
}
fn snapshot(&mut self, hazards: &HashMap<i32, StateHazard>) -> StaticDfaTable {
let mut remap = vec![usize::MAX; self.dfa.len()];
let mut states: Vec<StaticDfaState> = Vec::with_capacity(self.info.len());
for state in self.dfa.get_states() {
let number = state.state_number();
let Some(facts) = self.info.get(&number) else {
continue;
};
remap[number as usize] = states.len();
let escape = matches!(facts.verdict, Verdict::Escape(_));
let viable_alts = if escape {
let alts: BTreeSet<i32> = state
.configs()
.get_items()
.map(|config| config.get_alt())
.filter(|alt| *alt > 0)
.collect();
alts.into_iter().collect()
} else {
Vec::new()
};
states.push(StaticDfaState {
accept: facts.accept_value(),
fallback: facts.fallback,
depth: facts.depth,
conflicts: facts.conflicts.clone(),
conflict_min_alt: facts.conflict_min_alt,
guarded_alt: facts.guarded_alt,
guard_defer_alt: facts.guard_defer_alt,
guard_group: facts.guard_group,
continuation: facts.continuation.clone(),
viable_alts,
predicated: facts.predicated,
resolution: None,
hazard: hazards.get(&number).cloned(),
stack_hazard: None,
edges: Vec::new(),
});
}
if let Some(first) = self.attempt.first_conflict_state {
self.attempt.first_conflict_state = usize::try_from(first)
.ok()
.and_then(|old| remap.get(old).copied())
.filter(|&new| new != usize::MAX)
.and_then(|new| i32::try_from(new).ok());
}
let mut per_state: Vec<Vec<(i32, usize)>> = vec![Vec::new(); states.len()];
for (from, symbol, to) in self.dfa.enumerate_edges() {
let from = from.state_number();
let decides = self
.info
.get(&from)
.is_some_and(|facts| facts.verdict == Verdict::Decide);
let from = remap.get(from as usize).copied().unwrap_or(usize::MAX);
let to = remap
.get(to.state_number() as usize)
.copied()
.unwrap_or(usize::MAX);
if decides && from < per_state.len() && to < states.len() {
per_state[from].push((symbol as i32 - 1, to));
}
}
for (index, mut edges) in per_state.into_iter().enumerate() {
edges.sort_unstable();
let mut merged: Vec<StaticDfaEdge> = Vec::new();
for (token, target) in edges {
match merged.last_mut() {
Some(edge) if edge.target == target && edge.hi + 1 == token => edge.hi = token,
_ => merged.push(StaticDfaEdge {
lo: token,
hi: token,
target,
}),
}
}
states[index].edges = merged;
}
let mut table = StaticDfaTable::finish(self.decision, states);
if let Some(guard) = &self.guard {
table.guard_groups.clone_from(&guard.groups);
table.guard_pass.clone_from(&guard.pass);
}
table
}
fn uniform_pop_depths(
&self,
conflicting: &BitSet,
any_boundary: bool,
all_boundary: bool,
) -> bool {
if !any_boundary {
return true;
}
if !all_boundary {
return false;
}
if self.depth_bound == 0 {
return false;
}
let alt_starts: Vec<ATNStateRef> = self
.decision_state
.get_transitions()
.iter()
.map(|transition| transition.get_target())
.collect();
let mut reference: Option<usize> = None;
for alt in conflicting {
if alt == 0 || alt > alt_starts.len() {
return false;
}
let depths = self.completion_depths(alt_starts[alt - 1]);
if depths.len() != 1 || depths.contains(VARIABLE_DEPTH) {
return false;
}
let depth = depths.iter().next().unwrap();
match reference {
None => reference = Some(depth),
Some(known) if known != depth => return false,
Some(_) => {}
}
}
true
}
fn completion_depths(&self, alt_start: ATNStateRef) -> &'a BitSet {
let state_number = usize::try_from(alt_start.get_state_number())
.expect("an alternative start is a real ATN state");
self.completion_depths[state_number].get_or_init(|| {
let mut visiting = BTreeSet::new();
let mut budget = 100_000_i32;
token_counts_to_stop(alt_start, &mut visiting, &mut budget)
})
}
fn utrust_min_alt(
&mut self,
closed: &ClosedSet<'a>,
conflicting: &BitSet,
any_boundary: bool,
all_boundary: bool,
) -> i32 {
if any_boundary && !all_boundary {
return 0;
}
let Some(min_alt) = conflicting.iter().next() else {
return 0;
};
let min_alt = min_alt as i32;
let mut clean_by_state: HashMap<i32, Vec<dbt_antlr_runtime::analysis::ATNConfig<'a>>> =
HashMap::new();
for config in &closed.configs {
if config.get_alt() != min_alt {
continue;
}
if closed.taint_of(config) & (BOUNDARY_TAINT | WIDENED_TAINT | PRECPRED_TAINT) != 0 {
continue;
}
clean_by_state
.entry(config.get_state().get_state_number())
.or_default()
.push(config.clone());
}
if clean_by_state.is_empty() {
return 0;
}
let mut by_state_contexts: HashMap<i32, Vec<PredictionContextRef<'a>>> = HashMap::new();
for config in &closed.configs {
if config.get_alt() != min_alt && closed.taint_of(config) & WIDENED_TAINT != 0 {
return 0;
}
let state_number = config.get_state().get_state_number();
let context = config.get_context().expect("config has a context");
let entries = by_state_contexts.entry(state_number).or_default();
if !entries.contains(&context) {
entries.push(context);
}
}
for (state_number, contexts) in by_state_contexts {
let Some(attestations) = clean_by_state.get(&state_number) else {
return 0;
};
for context in contexts {
let assured = attestations.iter().any(|config| {
top_prefix_wildcard_match(
config.get_context().expect("config has a context"),
context,
self.scratch,
)
});
if !assured {
return 0;
}
}
}
min_alt
}
}
fn continuation_is_faithful(configs: &ATNConfigSet<'_>, taint: &Taint) -> bool {
const APPROXIMATION: i32 = WIDENED_TAINT | PRECPRED_TAINT | PRED_TAINT;
configs.get_items().all(|config| {
let taint = taint
.get(&(config.get_state().get_state_number(), config.get_alt()))
.copied()
.unwrap_or(0);
taint & APPROXIMATION == 0
})
}
fn continuation_words(continuation: &ParserContinuation) -> usize {
let contexts = continuation
.contexts
.iter()
.map(|node| match node {
ContinuationContextNode::Singleton { .. } => 3,
ContinuationContextNode::Array { parents, .. } => 1 + parents.len() * 2,
})
.sum::<usize>();
3 + contexts + continuation.configs.len() * 4
}
fn serialize_continuation(
state: u32,
configs: &ATNConfigSet<'_>,
taint: &Taint,
) -> ParserContinuation {
fn return_state_number(return_state: ATNStateRef) -> i32 {
if return_state == ATNStateRef::empty_return() {
-1
} else {
return_state.get_state_number()
}
}
fn intern_context<'a>(
context: PredictionContextRef<'a>,
nodes: &mut Vec<ContinuationContextNode>,
seen: &mut HashMap<usize, u32>,
) -> u32 {
const EMPTY_CONTEXT: u32 = u32::MAX;
if context.is_empty() {
return EMPTY_CONTEXT;
}
let key = context.as_ref() as *const PredictionContext<'a> as usize;
if let Some(&index) = seen.get(&key) {
return index;
}
let node = if context.length() == 1 {
ContinuationContextNode::Singleton {
parent: context
.get_parent(0)
.map_or(EMPTY_CONTEXT, |parent| intern_context(parent, nodes, seen)),
return_state: return_state_number(context.get_return_state(0)),
}
} else {
let mut parents = Vec::with_capacity(context.length());
let mut return_states = Vec::with_capacity(context.length());
for index in 0..context.length() {
parents.push(
context
.get_parent(index)
.map_or(EMPTY_CONTEXT, |parent| intern_context(parent, nodes, seen)),
);
return_states.push(return_state_number(context.get_return_state(index)));
}
ContinuationContextNode::Array {
parents,
return_states,
}
};
let index = nodes.len() as u32;
nodes.push(node);
seen.insert(key, index);
index
}
let mut contexts = Vec::new();
let mut seen = HashMap::new();
let mut entries = Vec::with_capacity(configs.length());
for config in configs.get_items() {
let context = config.get_context().map_or(u32::MAX, |context| {
intern_context(context, &mut contexts, &mut seen)
});
let taint = taint
.get(&(config.get_state().get_state_number(), config.get_alt()))
.copied()
.unwrap_or(0);
entries.push(ContinuationConfigEntry {
state: config.get_state().get_state_number(),
alt: config.get_alt(),
context,
outer_depth: i32::from(taint & BOUNDARY_TAINT != 0),
});
}
ParserContinuation {
state,
contexts,
configs: entries,
}
}
fn fallback_of(configs: &ATNConfigSet<'_>, taint: &Taint) -> i32 {
let mut fallback = 0;
for config in configs.get_items() {
let key = (config.get_state().get_state_number(), config.get_alt());
if taint.get(&key).copied().unwrap_or(0) & BOUNDARY_TAINT != 0
&& (fallback == 0 || config.get_alt() < fallback)
{
fallback = config.get_alt();
}
}
fallback
}
fn token_counts_to_stop(
state: ATNStateRef,
visiting: &mut BTreeSet<i32>,
budget: &mut i32,
) -> BitSet {
let mut out = BitSet::with_capacity(VARIABLE_DEPTH + 1);
if state.state_type() == ATNStateType::RuleStop {
out.insert(0);
return out;
}
let previous_budget = *budget;
*budget -= 1;
if previous_budget <= 0 || !visiting.insert(state.get_state_number()) {
out.insert(VARIABLE_DEPTH);
return out;
}
for transition in state.get_transitions() {
let sub = if let Some(rule) =
transition.try_as::<dbt_antlr_runtime::analysis::RuleTransition>()
{
let inner = token_counts_to_stop(rule.get_target(), visiting, budget);
let rest = token_counts_to_stop(rule.follow_state, visiting, budget);
sum_depths(&inner, &rest)
} else if transition.is_epsilon() {
token_counts_to_stop(transition.get_target(), visiting, budget)
} else {
shift_depths(&token_counts_to_stop(
transition.get_target(),
visiting,
budget,
))
};
out.union_with(&sub);
}
visiting.remove(&state.get_state_number());
out
}
fn shift_depths(input: &BitSet) -> BitSet {
let mut out = BitSet::with_capacity(VARIABLE_DEPTH + 1);
if input.contains(VARIABLE_DEPTH) {
out.insert(VARIABLE_DEPTH);
return out;
}
for depth in input {
if depth + 1 > MAX_TRACKED_DEPTH {
out.insert(VARIABLE_DEPTH);
return out;
}
out.insert(depth + 1);
}
out
}
fn sum_depths(left: &BitSet, right: &BitSet) -> BitSet {
let mut out = BitSet::with_capacity(VARIABLE_DEPTH + 1);
if left.contains(VARIABLE_DEPTH) || right.contains(VARIABLE_DEPTH) {
out.insert(VARIABLE_DEPTH);
return out;
}
for a in left {
for b in right {
if a + b > MAX_TRACKED_DEPTH {
out.insert(VARIABLE_DEPTH);
return out;
}
out.insert(a + b);
}
}
out
}
fn top_prefix_wildcard_match<'a>(
shadow: PredictionContextRef<'a>,
exact: PredictionContextRef<'a>,
scratch: &'a Bump,
) -> bool {
if exact.length() > 1 {
for i in 0..exact.length() {
if !top_prefix_wildcard_match(shadow, branch(exact, i, scratch), scratch) {
return false;
}
}
return true;
}
if shadow.is_empty() {
return true;
}
if shadow.length() > 1 {
for i in 0..shadow.length() {
if top_prefix_wildcard_match(branch(shadow, i, scratch), exact, scratch) {
return true;
}
}
return false;
}
if exact.is_empty() {
return false;
}
let return_state = shadow.get_return_state(0);
if return_state == ATNStateRef::empty_return() {
return true;
}
if exact.get_return_state(0) == ATNStateRef::empty_return() {
return false;
}
return_state == exact.get_return_state(0)
&& top_prefix_wildcard_match(
shadow
.get_parent(0)
.unwrap_or_else(PredictionContextRef::new_empty),
exact
.get_parent(0)
.unwrap_or_else(PredictionContextRef::new_empty),
scratch,
)
}
fn branch<'a>(
context: PredictionContextRef<'a>,
index: usize,
scratch: &'a Bump,
) -> PredictionContextRef<'a> {
let parent = context
.get_parent(index)
.unwrap_or_else(PredictionContextRef::new_empty);
let return_state = context.get_return_state(index);
if return_state == ATNStateRef::empty_return() && parent.is_empty() {
return PredictionContextRef::new_empty();
}
PredictionContextRef::from(
scratch.alloc(PredictionContext::new_singleton(Some(parent), return_state)),
)
}