use std::collections::HashSet;
use dbt_antlr_runtime::analysis::{
ATN, ATNConfig, ATNStateRef, ATNStateType, BitSet, FOREIGN_CONSUME_TAINT,
FOREIGN_LINEAGE_TAINT, MIDWAY_TAINT, PrecedencePredicateTransition, PredictionContextRef,
RuleTransition, WIDENED_TAINT,
};
use super::closure::{Taint, in_popped_frame, positions_owing_input, rule_positions, taint_of};
pub(super) const ITERATE_ALT: i32 = 1;
pub(super) const EXIT_ALT: i32 = 2;
pub(super) const EXIT_FOREIGN: i32 = 1;
pub(super) const EXIT_OBLIGATED: i32 = 2;
pub(super) const ITERATE_REAL: i32 = 4;
#[derive(Clone, Debug)]
pub(super) struct LoopBlock {
rule_index: i32,
operator_states: BitSet,
pending_states: BitSet,
midway_states: BitSet,
simple: bool,
}
impl LoopBlock {
pub(super) fn of(atn: &ATN, decision_state: ATNStateRef) -> Self {
let rule_index = decision_state.get_rule_index();
let operator_states = operator_states(decision_state);
let pending_states = pending_states(atn, decision_state, rule_index);
let midway_states = positions_owing_input(atn, rule_index, decision_state);
let simple = guards_are_simple(atn, decision_state, rule_index);
Self {
rule_index,
operator_states,
pending_states,
midway_states,
simple,
}
}
pub(super) fn iterate_exit_attestation(&self, configs: &[ATNConfig<'_>], taint: &Taint) -> i32 {
let mut iterate_pending = BitSet::new();
for config in configs {
if config.get_alt() == ITERATE_ALT
&& let Some(context) = config.get_context()
{
let mut visited = HashSet::new();
self.collect_pending(&context, &mut visited, &mut iterate_pending);
}
}
let mut attestation = 0;
for config in configs {
let taint = taint_of(taint, config);
if config.get_alt() == EXIT_ALT {
let foreign = taint & FOREIGN_CONSUME_TAINT != 0;
if foreign {
attestation |= EXIT_FOREIGN;
}
if self.has_unshared_obligation(config.get_context(), &iterate_pending, foreign) {
attestation |= EXIT_OBLIGATED;
}
}
if config.get_alt() == ITERATE_ALT
&& taint & (WIDENED_TAINT | FOREIGN_CONSUME_TAINT) == 0
{
attestation |= ITERATE_REAL;
}
}
attestation
}
pub(super) fn iterate_covers_exit(&self, configs: &[ATNConfig<'_>], taint: &Taint) -> bool {
let mut budget = PATH_BUDGET;
configs
.iter()
.filter(|config| config.get_alt() == EXIT_ALT)
.all(|exit| {
let exit_taint = taint_of(taint, exit);
if exit_taint & WIDENED_TAINT != 0 {
return false;
}
let iterate: Vec<_> = configs
.iter()
.filter(|config| {
config.get_alt() == ITERATE_ALT
&& config.get_state() == exit.get_state()
&& taint_of(taint, config) & (WIDENED_TAINT | FOREIGN_CONSUME_TAINT)
== 0
})
.map(ATNConfig::get_context)
.collect();
let walk = PathWalk {
block: self,
state: exit.get_state(),
loop_only: exit_taint & FOREIGN_CONSUME_TAINT != 0,
};
walk.covered(exit.get_context(), iterate, None, &mut budget)
})
}
pub(super) fn guards_are_simple(&self) -> bool {
self.simple
}
pub(super) fn is_loop_consumption(
&self,
state: ATNStateRef,
context: Option<PredictionContextRef<'_>>,
taint: i32,
) -> bool {
if taint & (FOREIGN_LINEAGE_TAINT | MIDWAY_TAINT) != 0 {
return false;
}
!in_popped_frame(context)
|| self
.operator_states
.contains(state.get_state_number() as usize)
}
pub(super) fn is_foreign_call(
&self,
state: ATNStateRef,
context: Option<PredictionContextRef<'_>>,
) -> bool {
in_popped_frame(context)
&& !self
.operator_states
.contains(state.get_state_number() as usize)
}
fn has_unshared_obligation(
&self,
context: Option<PredictionContextRef<'_>>,
iterate_pending: &BitSet,
foreign: bool,
) -> bool {
let Some(context) = context else {
return false;
};
let mut visited = HashSet::new();
self.obligation_in(&context, iterate_pending, foreign, &mut visited)
}
pub(super) fn is_midway(&self, state: ATNStateRef) -> bool {
self.midway_states
.contains(state.get_state_number() as usize)
}
pub(super) fn is_loop_state(&self, state: ATNStateRef) -> bool {
self.operator_states
.contains(state.get_state_number() as usize)
}
pub(super) fn is_pending(&self, state: ATNStateRef) -> bool {
self.pending_states
.contains(state.get_state_number() as usize)
}
fn collect_pending(
&self,
context: &PredictionContextRef<'_>,
visited: &mut HashSet<*const ()>,
out: &mut BitSet,
) {
if context.is_empty() || !visited.insert(pointer_key(context)) {
return;
}
for index in 0..context.length() {
let return_state = context.get_return_state(index);
if return_state == ATNStateRef::empty_return() {
continue;
}
if return_state.get_rule_index() == self.rule_index && self.is_pending(return_state) {
out.insert(return_state.get_state_number() as usize);
}
if let Some(parent) = context.get_parent(index) {
self.collect_pending(&parent, visited, out);
}
}
}
fn obligation_in(
&self,
context: &PredictionContextRef<'_>,
iterate_pending: &BitSet,
foreign: bool,
visited: &mut HashSet<*const ()>,
) -> bool {
if context.is_empty() || !visited.insert(pointer_key(context)) {
return false;
}
for index in 0..context.length() {
let return_state = context.get_return_state(index);
if return_state == ATNStateRef::empty_return() {
continue;
}
if return_state.get_rule_index() == self.rule_index
&& self.is_pending(return_state)
&& (!foreign || self.is_loop_state(return_state))
&& !iterate_pending.contains(return_state.get_state_number() as usize)
{
return true;
}
let Some(parent) = context.get_parent(index) else {
continue;
};
if self.obligation_in(&parent, iterate_pending, foreign, visited) {
return true;
}
}
false
}
}
pub(super) fn is_iterate_exit_pair(alts: &BitSet) -> bool {
alts.len() == 2 && alts.contains(ITERATE_ALT as usize) && alts.contains(EXIT_ALT as usize)
}
const PATH_BUDGET: usize = 4096;
struct PathWalk<'b> {
block: &'b LoopBlock,
state: ATNStateRef,
loop_only: bool,
}
impl PathWalk<'_> {
fn covered<'a>(
&self,
exit: Option<PredictionContextRef<'a>>,
iterate: Vec<Option<PredictionContextRef<'a>>>,
last: Option<ATNStateRef>,
budget: &mut usize,
) -> bool {
let Some(left) = budget.checked_sub(1) else {
return false;
};
*budget = left;
let Some(exit) = exit.filter(|context| !context.is_empty()) else {
return self.path_end_covered(&iterate, last);
};
for index in 0..exit.length() {
let return_state = exit.get_return_state(index);
if return_state == ATNStateRef::empty_return() {
if !self.path_end_covered(&iterate, last) {
return false;
}
continue;
}
let next = iterate
.iter()
.flatten()
.filter(|context| !context.is_empty())
.flat_map(|context| {
(0..context.length())
.filter(move |&other| context.get_return_state(other) == return_state)
.map(move |other| context.get_parent(other))
})
.collect();
if !self.covered(exit.get_parent(index), next, Some(return_state), budget) {
return false;
}
}
true
}
fn path_end_covered(
&self,
iterate: &[Option<PredictionContextRef<'_>>],
last: Option<ATNStateRef>,
) -> bool {
let counts = !self.loop_only || self.block.is_loop_state(last.unwrap_or(self.state));
!counts
|| iterate.iter().any(|context| {
context
.as_ref()
.is_none_or(|context| context.has_empty_path())
})
}
}
fn pointer_key(context: &PredictionContextRef<'_>) -> *const () {
context.as_ref() as *const _ as *const ()
}
fn operator_states(decision_state: ATNStateRef) -> BitSet {
rule_positions(decision_state, None)
}
fn pending_states(atn: &ATN, decision_state: ATNStateRef, rule_index: i32) -> BitSet {
let states_count = atn.states_count();
let mut reverse_epsilon: Vec<Vec<ATNStateRef>> = vec![Vec::new(); states_count];
for state in atn.iter_states() {
if state.get_rule_index() != rule_index {
continue;
}
for transition in state.get_transitions() {
if !transition.is_epsilon()
|| transition.try_as::<RuleTransition>().is_some()
|| transition.get_target().get_rule_index() != rule_index
{
continue;
}
let target = transition.get_target().get_state_number() as usize;
reverse_epsilon[target].push(atn.make_state_ref(state.get_state_number()));
}
}
let mut skips: BitSet = BitSet::new();
let mut work: Vec<ATNStateRef> = vec![decision_state];
skips.insert(decision_state.get_state_number() as usize);
while let Some(state) = work.pop() {
for predecessor in &reverse_epsilon[state.get_state_number() as usize] {
if skips.insert(predecessor.get_state_number() as usize) {
work.push(*predecessor);
}
}
}
let mut pending = BitSet::new();
for state in atn.iter_states() {
if state.get_rule_index() != rule_index || state.state_type() == ATNStateType::RuleStop {
continue;
}
if !skips.contains(state.get_state_number() as usize) {
pending.insert(state.get_state_number() as usize);
}
}
pending
}
fn guards_are_simple(atn: &ATN, decision_state: ATNStateRef, rule_index: i32) -> bool {
let mut pending: Vec<ATNStateRef> = Vec::new();
for state in atn.iter_states() {
if state.get_rule_index() != rule_index {
continue;
}
for transition in state.get_transitions() {
if transition
.try_as::<PrecedencePredicateTransition>()
.is_some()
{
pending.push(transition.get_target());
}
}
}
while let Some(start) = pending.pop() {
let mut visited: HashSet<i32> = HashSet::new();
let mut invocations = 0;
let mut work: Vec<ATNStateRef> = vec![start];
while let Some(current) = work.pop() {
if current == decision_state
|| current.get_rule_index() != rule_index
|| !visited.insert(current.get_state_number())
{
continue;
}
if matches!(
current.state_type(),
ATNStateType::StarBlockStart | ATNStateType::PlusBlockStart
) {
return false;
}
for transition in current.get_transitions() {
match transition.try_as::<RuleTransition>() {
Some(rule) => {
invocations += 1;
if invocations > 1 {
return false;
}
work.push(rule.follow_state);
}
None => work.push(transition.get_target()),
}
}
}
}
true
}