use std::collections::{BTreeSet, HashMap, HashSet};
use dbt_antlr_runtime::analysis::{
ATN, ATNConfig, ATNStateRef, ATNStateType, BOUNDARY_TAINT, BitSet, Bump, EOF,
FOREIGN_CONSUME_TAINT, FOREIGN_LINEAGE_TAINT, INTERIOR_TAINT, IntervalSetBuf, MIDWAY_TAINT,
MergeCache, MutableATNConfigSet, NotSetTransition, PRECPRED_TAINT, PRED_TAINT,
PrecedencePredicateTransition, PredicateTransition, PredictionContext, PredictionContextRef,
ROOTED_TAINT, RuleTransition, TOKEN_MIN_USER_TOKEN_TYPE, TransitionType, WIDENED_TAINT,
};
use super::loop_block::LoopBlock;
use super::postfix::{PostfixShape, collect_guard_roots};
const POSTFIX_SKIP_ALT: i32 = 2;
const ITERATE_EXIT_ALT: i32 = 2;
pub(super) type Taint = HashMap<(i32, i32), i32>;
pub(super) type GuardRoots = HashMap<(i32, i32), BTreeSet<i32>>;
pub(super) struct ClosedSet<'a> {
pub(super) configs: Vec<ATNConfig<'a>>,
pub(super) taint: Taint,
pub(super) roots: GuardRoots,
}
impl ClosedSet<'_> {
pub(super) fn taint_of(&self, config: &ATNConfig<'_>) -> i32 {
taint_of(&self.taint, config)
}
}
pub(super) fn in_popped_frame(context: Option<PredictionContextRef<'_>>) -> bool {
context.is_none_or(|context| context.has_empty_path())
}
pub(super) fn positions_owing_input(atn: &ATN, rule_index: i32, stop: ATNStateRef) -> BitSet {
let mut owing = BitSet::new();
for state in atn.iter_states() {
if state.get_rule_index() != rule_index {
continue;
}
let start = atn.make_state_ref(state.get_state_number());
let mut visited = BitSet::new();
let mut work = vec![start];
'walk: while let Some(current) = work.pop() {
if current == stop
|| current.get_rule_index() != rule_index
|| current.state_type() == ATNStateType::RuleStop
|| !visited.insert(current.get_state_number() as usize)
{
continue;
}
for transition in current.get_transitions() {
if !transition.is_epsilon() || transition.try_as::<RuleTransition>().is_some() {
owing.insert(state.get_state_number() as usize);
break 'walk;
}
work.push(transition.get_target());
}
}
}
owing
}
pub(super) fn rule_positions(start: ATNStateRef, end: Option<ATNStateRef>) -> BitSet {
let rule_index = start.get_rule_index();
let mut states = BitSet::new();
let mut work = vec![start];
while let Some(state) = work.pop() {
if Some(state) == end
|| state.get_rule_index() != rule_index
|| state.state_type() == ATNStateType::RuleStop
|| !states.insert(state.get_state_number() as usize)
{
continue;
}
for transition in state.get_transitions() {
work.push(match transition.try_as::<RuleTransition>() {
Some(rule) => rule.follow_state,
None => transition.get_target(),
});
}
}
states
}
pub(super) fn taint_of(taint: &Taint, config: &ATNConfig<'_>) -> i32 {
taint
.get(&(config.get_state().get_state_number(), config.get_alt()))
.copied()
.unwrap_or(0)
}
#[derive(Clone, Copy, Debug)]
pub(super) struct PrecedenceClass {
pub(super) rule_index: i32,
pub(super) eval_value: i32,
pub(super) lo: i32,
pub(super) hi: i32,
}
#[derive(Debug, Default)]
pub(super) struct ClosureFacts {
pub(super) first_predicate: Option<(i32, i32)>,
}
#[derive(Clone, Copy, Debug)]
struct CallInfo {
target_rule_index: i32,
precedence: i32,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) struct RuleCall {
pub(super) site: i32,
pub(super) caller_rule: i32,
pub(super) follow: i32,
pub(super) precedence: i32,
}
#[derive(Debug, Default)]
pub(super) struct CallSites {
site_by_follow_state: HashMap<i32, i32>,
call_by_follow_state: HashMap<i32, CallInfo>,
calls_to_rule: Vec<Vec<RuleCall>>,
}
impl CallSites {
pub(super) fn of(atn: &ATN) -> Self {
let mut sites = Self {
calls_to_rule: vec![Vec::new(); atn.rule_to_start_state.len()],
..Self::default()
};
for state in atn.iter_states() {
for transition in state.get_transitions() {
if let Some(rule_transition) = transition.try_as::<RuleTransition>() {
let follow_state = rule_transition.follow_state.get_state_number();
let target_rule_index = rule_transition.get_target().get_rule_index();
sites
.site_by_follow_state
.insert(follow_state, state.get_state_number());
sites.call_by_follow_state.insert(
follow_state,
CallInfo {
target_rule_index,
precedence: rule_transition.precedence(),
},
);
if let Some(calls) = usize::try_from(target_rule_index)
.ok()
.and_then(|rule| sites.calls_to_rule.get_mut(rule))
{
calls.push(RuleCall {
site: state.get_state_number(),
caller_rule: state.get_rule_index(),
follow: follow_state,
precedence: rule_transition.precedence(),
});
}
}
}
}
sites
}
pub(super) fn calls_to(&self, rule: i32) -> &[RuleCall] {
usize::try_from(rule)
.ok()
.and_then(|rule| self.calls_to_rule.get(rule))
.map_or(&[], Vec::as_slice)
}
}
struct RootPool {
sets: Vec<BTreeSet<i32>>,
ids: HashMap<BTreeSet<i32>, u32>,
}
impl RootPool {
fn new() -> Self {
Self {
sets: vec![BTreeSet::new()],
ids: HashMap::from([(BTreeSet::new(), 0)]),
}
}
fn intern(&mut self, set: BTreeSet<i32>) -> u32 {
if let Some(&id) = self.ids.get(&set) {
return id;
}
let id = self.sets.len() as u32;
self.sets.push(set.clone());
self.ids.insert(set, id);
id
}
fn get(&self, id: u32) -> &BTreeSet<i32> {
&self.sets[id as usize]
}
}
#[derive(Clone, PartialEq, Eq, Hash)]
struct Step<'a> {
stop: bool,
config: ATNConfig<'a>,
outer: i32,
taint: i32,
roots: u32,
}
struct SetBuilder<'a> {
configs: Vec<ATNConfig<'a>>,
seen: HashSet<ATNConfig<'a>>,
taint: Taint,
roots: GuardRoots,
busy: HashMap<(ATNConfig<'a>, i32, bool), (i32, BTreeSet<i32>)>,
}
impl<'a> SetBuilder<'a> {
fn new() -> Self {
Self {
configs: Vec::new(),
seen: HashSet::new(),
taint: Taint::new(),
roots: GuardRoots::new(),
busy: HashMap::new(),
}
}
fn record(&mut self, config: &ATNConfig<'a>, taint: i32, roots: &BTreeSet<i32>) {
let key = (config.get_state().get_state_number(), config.get_alt());
let slot = self.taint.entry(key).or_insert(0);
*slot |= taint;
if taint & BOUNDARY_TAINT == 0 {
*slot |= INTERIOR_TAINT;
}
if !roots.is_empty() {
self.roots
.entry(key)
.or_default()
.extend(roots.iter().copied());
}
}
fn insert(&mut self, config: ATNConfig<'a>, taint: i32, roots: &BTreeSet<i32>) {
self.record(&config, taint, roots);
if self.seen.insert(config.clone()) {
self.configs.push(config);
}
}
fn into_closed_set(self) -> ClosedSet<'a> {
ClosedSet {
configs: self.configs,
taint: self.taint,
roots: self.roots,
}
}
}
pub(super) struct Closure<'atn, 'a> {
atn: &'atn ATN,
scratch: &'a Bump,
merge: MergeCache<'a>,
pub(super) facts: ClosureFacts,
precedence: Option<PrecedenceClass>,
depth_cache: HashMap<usize, i32>,
call_sites: &'a CallSites,
depth_bound: i32,
precedence_start: bool,
loop_block: Option<LoopBlock>,
postfix: Option<PostfixShape>,
decision_state: ATNStateRef,
visits: u64,
rule_visits: Vec<u64>,
visit_budget: u64,
pub(super) exhausted: bool,
roots: RootPool,
current_roots: u32,
propagating_roots: bool,
}
impl<'atn, 'a> Closure<'atn, 'a> {
#[expect(clippy::too_many_arguments)]
pub(super) fn new(
atn: &'atn ATN,
call_sites: &'a CallSites,
scratch: &'a Bump,
depth_bound: i32,
precedence: Option<PrecedenceClass>,
loop_block: Option<LoopBlock>,
postfix: Option<PostfixShape>,
visit_budget: u64,
) -> Self {
Self {
atn,
scratch,
merge: MergeCache::new(scratch),
facts: ClosureFacts::default(),
precedence,
depth_cache: HashMap::new(),
call_sites,
depth_bound,
precedence_start: false,
loop_block,
postfix,
decision_state: ATNStateRef::invalid(),
visits: 0,
rule_visits: vec![0; atn.rule_to_start_state.len()],
visit_budget,
exhausted: false,
roots: RootPool::new(),
current_roots: 0,
propagating_roots: false,
}
}
pub(super) fn loop_block(&self) -> Option<&LoopBlock> {
self.loop_block.as_ref()
}
pub(super) fn visits(&self) -> u64 {
self.visits.min(self.visit_budget)
}
pub(super) fn remaining_visits(&self) -> u64 {
self.visit_budget.saturating_sub(self.visits)
}
pub(super) fn successors_capped(
&mut self,
closed: &ClosedSet<'a>,
max_call_visits: u64,
) -> (Vec<(IntervalSetBuf, ClosedSet<'a>)>, bool) {
let global_budget = self.visit_budget;
let remaining_global = global_budget.saturating_sub(self.visits);
if max_call_visits >= remaining_global {
let successors = self.successors(closed);
return (successors, self.exhausted);
}
let capped_budget = self.visits.saturating_add(max_call_visits);
self.visit_budget = capped_budget;
let successors = self.successors(closed);
let hit_cap = self.exhausted;
self.visit_budget = global_budget;
if hit_cap {
self.visits = self.visits.min(capped_budget);
self.exhausted = false;
}
(successors, hit_cap)
}
pub(super) fn sandbox<R>(
&mut self,
visits: u64,
analysis: impl FnOnce(&mut Self) -> Option<R>,
) -> Option<R> {
let facts = std::mem::take(&mut self.facts);
let rule_visits = self.rule_visits.clone();
let (saved_visits, budget, exhausted) = (self.visits, self.visit_budget, self.exhausted);
self.visit_budget = saved_visits.saturating_add(visits);
self.exhausted = false;
let result = analysis(self);
let spent = self.exhausted;
self.facts = facts;
self.rule_visits = rule_visits;
self.visits = saved_visits;
self.visit_budget = budget;
self.exhausted = exhausted;
if spent { None } else { result }
}
pub(super) fn take_rule_visits(&mut self) -> Vec<u64> {
std::mem::take(&mut self.rule_visits)
}
pub(super) fn start(&mut self, decision_state: ATNStateRef) -> ClosedSet<'a> {
self.start_in(decision_state, PredictionContextRef::new_empty())
}
pub(super) fn start_in(
&mut self,
decision_state: ATNStateRef,
context: PredictionContextRef<'a>,
) -> ClosedSet<'a> {
let mut out = SetBuilder::new();
self.decision_state = decision_state;
self.precedence_start = self.precedence.is_some();
for (index, transition) in decision_state.get_transitions().iter().enumerate() {
let config = ATNConfig::new(transition.get_target(), (index + 1) as i32, Some(context));
self.current_roots = 0;
self.closure(config, 0, 0, &mut out);
}
self.precedence_start = false;
let closed = out.into_closed_set();
match self.precedence {
Some(_) => self.apply_precedence_filter(closed),
None => closed,
}
}
pub(super) fn step(&mut self, closed: &ClosedSet<'a>, token: i32) -> ClosedSet<'a> {
let mut out = SetBuilder::new();
for config in &closed.configs {
let mut taint = closed.taint_of(config);
if taint & BOUNDARY_TAINT != 0 {
taint &= !INTERIOR_TAINT;
}
let state = config.get_state();
if state.state_type() == ATNStateType::RuleStop {
if token == EOF {
out.insert(config.clone(), taint, &BTreeSet::new());
}
continue;
}
for transition in state.get_transitions() {
let reads = !transition.is_epsilon()
&& transition.matches(
token,
TOKEN_MIN_USER_TOKEN_TYPE,
self.atn.max_token_type,
);
if !reads {
continue;
}
let step = self.consume(config, transition.get_target(), taint, 0);
self.current_roots = 0;
self.closure(step.config, step.taint, 0, &mut out);
if self.exhausted {
return out.into_closed_set();
}
}
}
self.current_roots = 0;
out.into_closed_set()
}
pub(super) fn call_sites(&self) -> &'a CallSites {
self.call_sites
}
pub(super) fn precedence(&self) -> Option<PrecedenceClass> {
self.precedence
}
pub(super) fn with_depth_bound<R>(
&mut self,
depth_bound: i32,
analysis: impl FnOnce(&mut Self) -> R,
) -> R {
let saved = std::mem::replace(&mut self.depth_bound, depth_bound);
let result = analysis(self);
self.depth_bound = saved;
result
}
pub(super) fn call_stack(&mut self, follows: &[i32]) -> PredictionContextRef<'a> {
let mut context = PredictionContextRef::new_empty();
for &follow in follows.iter().rev() {
let follow_state = self.atn.make_state_ref(follow);
context = PredictionContextRef::from(self.scratch.alloc(
PredictionContext::new_singleton(Some(context), follow_state),
));
}
context
}
pub(super) fn successors(
&mut self,
closed: &ClosedSet<'a>,
) -> Vec<(IntervalSetBuf, ClosedSet<'a>)> {
let all_tokens = self.all_tokens();
let mut labels: Vec<IntervalSetBuf> = Vec::new();
let mut step_of: Vec<usize> = Vec::new();
let mut steps: Vec<Step<'a>> = Vec::new();
let mut step_numbers: HashMap<Step<'a>, usize> = HashMap::new();
let mut add_step = |label: IntervalSetBuf, step: Step<'a>| {
let number = match step_numbers.get(&step) {
Some(&number) => number,
None => {
let number = steps.len();
steps.push(step.clone());
step_numbers.insert(step, number);
number
}
};
labels.push(label);
step_of.push(number);
};
for config in &closed.configs {
let mut taint = closed.taint_of(config);
if taint & BOUNDARY_TAINT != 0 {
taint &= !INTERIOR_TAINT;
}
let roots = match closed
.roots
.get(&(config.get_state().get_state_number(), config.get_alt()))
{
Some(roots) => self.roots.intern(roots.clone()),
None => 0,
};
let state = config.get_state();
if state.state_type() == ATNStateType::RuleStop {
let mut eof = IntervalSetBuf::new();
eof.add_one(EOF);
add_step(
eof,
Step {
stop: true,
config: config.clone(),
outer: config.reaches_into_outer_context,
taint,
roots,
},
);
continue;
}
for transition in state.get_transitions() {
if transition.is_epsilon() {
continue;
}
let label = match transition.transition_type() {
TransitionType::NotSet => {
let not_set = transition.try_as::<NotSetTransition>().unwrap();
not_set
.get_label()
.unwrap()
.complement(TOKEN_MIN_USER_TOKEN_TYPE, self.atn.max_token_type)
}
TransitionType::Wildcard => all_tokens.clone(),
_ => match transition.get_label() {
Some(set) => set.to_interval_set_buf(),
None => continue,
},
};
if label.as_interval_set().as_slice().is_empty() {
continue;
}
add_step(
label,
self.consume(config, transition.get_target(), taint, roots),
);
}
}
let mut boundaries: Vec<i32> = Vec::new();
for label in &labels {
for interval in label.as_interval_set().as_slice() {
boundaries.push(interval.a);
boundaries.push(interval.b.saturating_add(1));
}
}
boundaries.sort_unstable();
boundaries.dedup();
let mut classes: Vec<(BitSet, IntervalSetBuf)> = Vec::new();
for window in boundaries.windows(2) {
let (lo, hi) = (window[0], window[1] - 1);
let mut key = BitSet::new();
for (index, label) in labels.iter().enumerate() {
if label.as_interval_set().contains(lo) {
key.insert(index);
}
}
if key.is_empty() {
continue;
}
match classes.last_mut() {
Some((known, label)) if *known == key => label.add_range(lo, hi),
_ => {
let mut label = IntervalSetBuf::new();
label.add_range(lo, hi);
classes.push((key, label));
}
}
}
let mut successors: Vec<(IntervalSetBuf, ClosedSet<'a>)> =
Vec::with_capacity(classes.len());
let mut successor_of: HashMap<Vec<usize>, usize> = HashMap::new();
let mut seen = BitSet::with_capacity(steps.len());
for (class, label) in classes {
if self.exhausted {
break;
}
seen.clear();
let sequence: Vec<usize> = class
.iter()
.map(|index| step_of[index])
.filter(|&number| seen.insert(number))
.collect();
if let Some(&known) = successor_of.get(&sequence) {
successors[known].0.add_set(&label);
continue;
}
let mut out = SetBuilder::new();
for &number in &sequence {
let step = &steps[number];
self.current_roots = step.roots;
if step.stop {
out.insert(step.config.clone(), step.taint, self.roots.get(step.roots));
} else {
self.closure(step.config.clone(), step.taint, 0, &mut out);
}
}
self.current_roots = 0;
successor_of.insert(sequence, successors.len());
successors.push((label, out.into_closed_set()));
}
successors
}
fn consume(
&mut self,
source: &ATNConfig<'a>,
target: ATNStateRef,
mut taint: i32,
roots: u32,
) -> Step<'a> {
let sites = &self.call_sites.site_by_follow_state;
let mut new_roots: BTreeSet<i32> = BTreeSet::new();
if let Some(block) = self.loop_block.as_ref()
&& taint & BOUNDARY_TAINT != 0
&& !block.is_loop_consumption(source.get_state(), source.get_context(), taint)
{
let in_loop = taint & (FOREIGN_LINEAGE_TAINT | MIDWAY_TAINT) == 0;
taint |= FOREIGN_CONSUME_TAINT;
if source.get_alt() == ITERATE_EXIT_ALT && taint & ROOTED_TAINT == 0 {
taint |= ROOTED_TAINT;
collect_guard_roots(
source.get_state(),
source.get_context(),
&|state| in_loop && block.is_loop_state(state),
sites,
&mut new_roots,
);
}
}
if let Some(postfix) = self.postfix.as_ref()
&& source.get_alt() == POSTFIX_SKIP_ALT
&& taint & ROOTED_TAINT == 0
&& !postfix.skip_mirrors(source.get_state(), source.get_context(), taint)
{
let in_take = taint & (FOREIGN_LINEAGE_TAINT | MIDWAY_TAINT) == 0;
taint |= ROOTED_TAINT;
collect_guard_roots(
source.get_state(),
source.get_context(),
&|state| in_take && state == postfix.block_end_state,
sites,
&mut new_roots,
);
}
let roots = if new_roots.is_empty() {
roots
} else {
new_roots.extend(self.roots.get(roots).iter().copied());
self.roots.intern(new_roots)
};
Step {
stop: false,
config: source.clone().with_state(target),
outer: source.reaches_into_outer_context,
taint,
roots,
}
}
pub(super) fn canonical_set(&mut self, closed: ClosedSet<'a>) -> ClosedSet<'a> {
let set = self.config_set(&closed.configs);
let mut configs: Vec<ATNConfig<'a>> = set.into_iter().collect();
configs.sort_by_key(|config| (config.get_state().get_state_number(), config.get_alt()));
ClosedSet {
configs,
taint: closed.taint,
roots: closed.roots,
}
}
pub(super) fn merged_config_set(&mut self, closed: &ClosedSet<'a>) -> MutableATNConfigSet<'a> {
self.config_set(&closed.configs)
}
fn all_tokens(&self) -> IntervalSetBuf {
let mut set = IntervalSetBuf::new();
if self.atn.max_token_type >= TOKEN_MIN_USER_TOKEN_TYPE {
set.add_range(TOKEN_MIN_USER_TOKEN_TYPE, self.atn.max_token_type);
}
set
}
pub(super) fn config_set(&mut self, configs: &[ATNConfig<'a>]) -> MutableATNConfigSet<'a> {
let mut set = MutableATNConfigSet::new(self.scratch, false);
for config in configs {
set.add_cached(config.clone(), &mut self.merge);
}
set
}
fn closure(&mut self, config: ATNConfig<'a>, taint: i32, depth: i32, out: &mut SetBuilder<'a>) {
if self.exhausted {
return;
}
let chasing = depth < 0;
let current = self.roots.get(self.current_roots);
let missing = match out.busy.get_mut(&(config.clone(), taint, chasing)) {
None => {
out.busy
.insert((config.clone(), taint, chasing), (depth, current.clone()));
None
}
Some((first_depth, explored)) => {
let missing: BTreeSet<i32> = current.difference(explored).copied().collect();
explored.extend(missing.iter().copied());
Some((*first_depth, missing))
}
};
if missing.is_none() || !self.propagating_roots {
self.visits = self.visits.saturating_add(1);
if self.visits > self.visit_budget {
self.exhausted = true;
return;
}
if let Some(visits) = usize::try_from(config.get_state().get_rule_index())
.ok()
.and_then(|rule| self.rule_visits.get_mut(rule))
{
*visits += 1;
}
}
match missing {
None => self.closure_body(config, taint, depth, out),
Some((_, missing)) if missing.is_empty() => {}
Some((first_depth, missing)) => {
let saved = (self.current_roots, self.propagating_roots);
self.current_roots = self.roots.intern(missing);
self.propagating_roots = true;
self.closure_body(config, taint, first_depth, out);
(self.current_roots, self.propagating_roots) = saved;
}
}
}
fn closure_body(
&mut self,
config: ATNConfig<'a>,
mut taint: i32,
depth: i32,
out: &mut SetBuilder<'a>,
) {
let state = config.get_state();
if taint & MIDWAY_TAINT != 0
&& state == self.decision_state
&& in_popped_frame(config.get_context())
{
taint &= !MIDWAY_TAINT;
}
if state.state_type() == ATNStateType::RuleStop {
let context = config.get_context().expect("config has a context");
if !context.is_empty() {
for i in 0..context.length() {
if context.get_return_state(i) == ATNStateRef::empty_return() {
let popped = config
.clone()
.with_prediction_context(Some(PredictionContextRef::new_empty()));
self.closure(popped, taint, depth, out);
} else {
let return_state = context.get_return_state(i);
let parent = context
.get_parent(i)
.unwrap_or_else(PredictionContextRef::new_empty);
let popped = config
.clone()
.with_state(return_state)
.with_prediction_context(Some(parent));
self.closure(popped, taint, depth - 1, out);
}
}
return;
}
taint = (taint & !INTERIOR_TAINT) | BOUNDARY_TAINT;
out.insert(config.clone(), taint, self.roots.get(self.current_roots));
} else if !state.has_epsilon_only_transitions() {
out.insert(config.clone(), taint, self.roots.get(self.current_roots));
}
let boundary_chase = state.state_type() == ATNStateType::RuleStop;
for transition in state.get_transitions() {
match transition.transition_type() {
TransitionType::Rule => {
let rule_transition = transition.try_as::<RuleTransition>().unwrap();
self.enter_rule(&config, rule_transition, taint, depth, out);
}
TransitionType::PrecedencePredicate => {
let predicate = transition
.try_as::<PrecedencePredicateTransition>()
.unwrap();
self.cross_precedence_predicate(&config, predicate, taint, depth, out);
}
TransitionType::Predicate => {
let predicate = transition.try_as::<PredicateTransition>().unwrap();
if self.facts.first_predicate.is_none() {
self.facts.first_predicate =
Some((predicate.rule_index(), predicate.pred_index()));
}
let next = config.clone().with_state(predicate.get_target());
self.closure(next, taint | PRED_TAINT, depth, out);
}
_ if transition.is_epsilon() => {
if boundary_chase
&& transition.get_target().get_rule_index() == state.get_rule_index()
&& self.precedence_suppresses(transition.get_target(), depth)
{
continue;
}
let mut next = config.clone().with_state(transition.get_target());
let mut next_depth = depth;
let mut next_taint = taint;
if boundary_chase {
next_depth = (depth - 1).min(-1);
let target = transition.get_target();
let midway = match (&self.loop_block, &self.postfix) {
(Some(block), _) => block.is_midway(target),
(None, Some(postfix)) => postfix.is_midway(target),
(None, None) => false,
};
if midway {
next_taint |= MIDWAY_TAINT;
}
if self.precedence_start
&& self
.precedence
.is_some_and(|class| state.get_rule_index() == class.rule_index)
&& self.precedence_starts_self_call(transition.get_target())
{
next.set_precedence_filter_suppressed(true);
}
}
self.closure(next, next_taint, next_depth, out);
}
_ => {}
}
}
}
fn enter_rule(
&mut self,
config: &ATNConfig<'a>,
transition: &RuleTransition,
taint: i32,
depth: i32,
out: &mut SetBuilder<'a>,
) {
let follow_state = transition.follow_state;
let follow_state_number = follow_state.get_state_number();
let context = config.get_context().expect("config has a context");
let (new_context, widened) = if self.depth_bound == 0 {
(PredictionContextRef::new_empty(), true)
} else if self.context_depth(context) >= self.depth_bound
|| has_return_state(context, follow_state_number)
{
let joint =
PredictionContextRef::from(self.scratch.alloc(PredictionContext::new_singleton(
Some(PredictionContextRef::new_empty()),
follow_state,
)));
(joint, true)
} else {
let pushed = PredictionContextRef::from(self.scratch.alloc(
PredictionContext::new_singleton(Some(context), follow_state),
));
(pushed, false)
};
let callee = config
.clone()
.with_state(transition.get_target())
.with_prediction_context(Some(new_context));
let mut callee_taint = taint;
if widened {
callee_taint |= WIDENED_TAINT;
}
let foreign_call = taint & BOUNDARY_TAINT != 0
&& (taint & MIDWAY_TAINT != 0
|| match (&self.loop_block, &self.postfix) {
(Some(block), _) => {
block.is_foreign_call(config.get_state(), config.get_context())
}
(None, Some(postfix)) => {
postfix.is_foreign_call(config.get_state(), config.get_context())
}
(None, None) => false,
});
if foreign_call {
callee_taint |= FOREIGN_LINEAGE_TAINT;
}
let next_depth = if depth >= 0 { depth + 1 } else { depth };
self.closure(callee, callee_taint, next_depth, out);
}
fn cross_precedence_predicate(
&mut self,
config: &ATNConfig<'a>,
predicate: &PrecedencePredicateTransition,
taint: i32,
depth: i32,
out: &mut SetBuilder<'a>,
) {
let value = predicate.precedence();
if let Some(class) = self.precedence
&& self.precedence_start
&& depth == 0
{
if value >= class.eval_value {
let next = config.clone().with_state(predicate.get_target());
self.closure(next, taint, depth, out);
}
return;
}
let context = config.get_context().expect("config has a context");
let rule_index = config.get_state().get_rule_index();
if let Some(passes) = self.evaluate_precedence_from_context(context, rule_index, value) {
if passes {
let next = config.clone().with_state(predicate.get_target());
self.closure(next, taint, depth, out);
}
return;
}
let next = config.clone().with_state(predicate.get_target());
self.closure(next, taint | PRECPRED_TAINT, depth, out);
}
fn precedence_suppresses(&self, target: ATNStateRef, depth: i32) -> bool {
let Some(class) = self.precedence else {
return false;
};
if depth < 0 {
return false;
}
self.call_info(target.get_state_number())
.is_some_and(|call| {
call.target_rule_index == class.rule_index
&& (call.precedence < class.lo || call.precedence > class.hi)
})
}
fn precedence_starts_self_call(&self, target: ATNStateRef) -> bool {
let Some(class) = self.precedence else {
return false;
};
self.call_info(target.get_state_number())
.is_some_and(|call| call.precedence == 0 && call.target_rule_index == class.rule_index)
}
fn call_info(&self, follow_state_number: i32) -> Option<CallInfo> {
self.call_sites
.call_by_follow_state
.get(&follow_state_number)
.copied()
}
fn evaluate_precedence_from_context(
&self,
context: PredictionContextRef<'_>,
rule: i32,
value: i32,
) -> Option<bool> {
if context.is_empty() {
return None;
}
let mut agreed = None;
for i in 0..context.length() {
let return_state = context.get_return_state(i);
if return_state == ATNStateRef::empty_return() {
return None;
}
let call = self.call_info(return_state.get_state_number())?;
if call.target_rule_index != rule {
return None;
}
let outcome = value >= call.precedence;
match agreed {
None => agreed = Some(outcome),
Some(previous) if previous != outcome => return None,
Some(_) => {}
}
}
agreed
}
fn context_depth(&mut self, context: PredictionContextRef<'a>) -> i32 {
if context.is_empty() {
return 0;
}
let pointer = context.as_ref() as *const PredictionContext<'_> as usize;
if let Some(&cached) = self.depth_cache.get(&pointer) {
return cached;
}
let mut max_depth = 0;
for i in 0..context.length() {
if context.get_return_state(i) == ATNStateRef::empty_return() {
continue;
}
let depth = match context.get_parent(i) {
Some(parent) => 1 + self.context_depth(parent),
None => 1,
};
max_depth = max_depth.max(depth);
}
self.depth_cache.insert(pointer, max_depth);
max_depth
}
fn apply_precedence_filter(&mut self, closed: ClosedSet<'a>) -> ClosedSet<'a> {
let closed = self.canonical_set(closed);
let mut states_from_alt1: HashMap<i32, PredictionContextRef<'a>> = HashMap::new();
for config in &closed.configs {
if config.get_alt() == 1 {
states_from_alt1.insert(
config.get_state().get_state_number(),
config.get_context().expect("config has a context"),
);
}
}
let mut out = SetBuilder::new();
for config in closed.configs {
let state_number = config.get_state().get_state_number();
let widened = (taint_of(&closed.taint, &config)
| closed.taint.get(&(state_number, 1)).copied().unwrap_or(0))
& WIDENED_TAINT
!= 0;
if config.get_alt() != 1
&& !config.is_precedence_filter_suppressed()
&& !widened
&& states_from_alt1.get(&state_number) == config.get_context().as_ref()
{
continue;
}
let mut kept = config;
kept.set_precedence_filter_suppressed(false);
let key = (kept.get_state().get_state_number(), kept.get_alt());
let taint = closed.taint.get(&key).copied().unwrap_or(0);
let roots = closed.roots.get(&key).cloned().unwrap_or_default();
out.insert(kept, taint, &roots);
}
out.into_closed_set()
}
}
fn has_return_state(mut context: PredictionContextRef<'_>, return_state_number: i32) -> bool {
while !context.is_empty() {
if context.length() != 1 {
let mut visited = HashSet::new();
return has_return_state_in_dag(context, return_state_number, &mut visited);
}
let return_state = context.get_return_state(0);
if return_state.get_state_number() == return_state_number {
return true;
}
if return_state == ATNStateRef::empty_return() {
return false;
}
match context.get_parent(0) {
Some(parent) => context = parent,
None => return false,
}
}
false
}
fn has_return_state_in_dag(
context: PredictionContextRef<'_>,
return_state_number: i32,
visited: &mut HashSet<usize>,
) -> bool {
if context.is_empty() {
return false;
}
let pointer = context.as_ref() as *const PredictionContext<'_> as usize;
if !visited.insert(pointer) {
return false;
}
for i in 0..context.length() {
let return_state = context.get_return_state(i);
if return_state.get_state_number() == return_state_number {
return true;
}
if return_state != ATNStateRef::empty_return()
&& context
.get_parent(i)
.is_some_and(|parent| has_return_state_in_dag(parent, return_state_number, visited))
{
return true;
}
}
false
}