use std::collections::{BTreeSet, HashMap, HashSet};
use std::sync::Arc;
use dbt_antlr_runtime::analysis::{
ATN, ATNStateRef, ATNStateType, BOUNDARY_TAINT, BasicBlockStartState, BitSet,
FOREIGN_LINEAGE_TAINT, IntervalSetBuf, MIDWAY_TAINT, NotSetTransition, PlusBlockStartState,
PredictionContextRef, ROOTED_TAINT, RuleTransition, StarBlockStartState,
TOKEN_MIN_USER_TOKEN_TYPE, TransitionType,
};
use super::closure::{in_popped_frame, positions_owing_input, rule_positions};
#[derive(Clone, Debug)]
pub(super) struct PostfixShape {
pub(super) block_end_state: ATNStateRef,
take_states: Arc<BitSet>,
midway_states: Arc<BitSet>,
}
impl PostfixShape {
pub(super) fn analyze(atn: &ATN, decision_state: ATNStateRef) -> Option<Self> {
let block = block_end_state(decision_state)?;
let transitions = decision_state.get_transitions();
if transitions.len() != 2 {
return None;
}
if !epsilon_path_to(transitions[1].get_target(), block) {
return None;
}
let first = first_element(transitions[0].get_target())?;
if !first
.get_transitions()
.iter()
.any(|transition| transition.try_as::<RuleTransition>().is_some())
{
return None;
}
let rule_stop = atn.rule_to_stop_state[decision_state.get_rule_index() as usize];
let continuation = look(atn, block, rule_stop);
let take = look(atn, transitions[0].get_target(), block);
if continuation.intersection(&take).next().is_some() {
return None;
}
Some(Self {
block_end_state: block,
take_states: Arc::new(rule_positions(transitions[0].get_target(), Some(block))),
midway_states: Arc::new(positions_owing_input(
atn,
decision_state.get_rule_index(),
block,
)),
})
}
pub(super) fn skip_mirrors(
&self,
state: ATNStateRef,
context: Option<PredictionContextRef<'_>>,
taint: i32,
) -> bool {
if taint & (FOREIGN_LINEAGE_TAINT | MIDWAY_TAINT | ROOTED_TAINT) != 0 {
return false;
}
if state.get_rule_index() == self.block_end_state.get_rule_index() {
if taint & BOUNDARY_TAINT == 0 {
return true;
}
if in_popped_frame(context) {
return self.is_take_state(state);
}
}
context.is_some_and(|context| {
bottom_frame_is(context, self.block_end_state, &mut HashSet::new())
})
}
pub(super) fn is_foreign_call(
&self,
state: ATNStateRef,
context: Option<PredictionContextRef<'_>>,
) -> bool {
in_popped_frame(context) && !self.is_take_state(state)
}
pub(super) fn is_midway(&self, state: ATNStateRef) -> bool {
self.is_take_state(state)
&& self
.midway_states
.contains(state.get_state_number() as usize)
}
fn is_take_state(&self, state: ATNStateRef) -> bool {
self.take_states.contains(state.get_state_number() as usize)
}
}
fn bottom_frame_is(
context: PredictionContextRef<'_>,
end_state: ATNStateRef,
visited: &mut HashSet<*const ()>,
) -> bool {
if context.is_empty() {
return false;
}
if !visited.insert(context.as_ref() as *const _ as *const ()) {
return true;
}
for index in 0..context.length() {
let return_state = context.get_return_state(index);
match context.get_parent(index) {
Some(parent) if !parent.is_empty() => {
if !bottom_frame_is(parent, end_state, visited) {
return false;
}
}
_ => {
if return_state != end_state {
return false;
}
}
}
}
true
}
fn block_end_state(state: ATNStateRef) -> Option<ATNStateRef> {
let number = state.get_state_number();
if number < 0 {
return None;
}
match state.state_type() {
ATNStateType::BasicBlockStart => state
.try_as::<BasicBlockStartState>()
.map(|start| start.end_state),
ATNStateType::StarBlockStart => state
.try_as::<StarBlockStartState>()
.map(|start| start.end_state),
ATNStateType::PlusBlockStart => state
.try_as::<PlusBlockStartState>()
.map(|start| start.end_state),
_ => None,
}
}
fn epsilon_path_to(from: ATNStateRef, to: ATNStateRef) -> bool {
let mut visited: BitSet = BitSet::new();
let mut work = vec![from];
while let Some(state) = work.pop() {
if state == to {
return true;
}
if state.get_state_number() < 0 || !visited.insert(state.get_state_number() as usize) {
continue;
}
for transition in state.get_transitions() {
if transition.is_epsilon() {
work.push(transition.get_target());
}
}
}
false
}
fn first_element(start: ATNStateRef) -> Option<ATNStateRef> {
let mut visited: BitSet = BitSet::new();
let mut work = vec![start];
while let Some(state) = work.pop() {
if state.get_state_number() < 0 || !visited.insert(state.get_state_number() as usize) {
continue;
}
for transition in state.get_transitions() {
if transition.try_as::<RuleTransition>().is_some() || !transition.is_epsilon() {
return Some(state);
}
work.push(transition.get_target());
}
}
None
}
fn look(atn: &ATN, start: ATNStateRef, stop: ATNStateRef) -> BitSet {
let mut tokens = BitSet::new();
let mut visited: HashSet<(i32, usize)> = HashSet::new();
let mut work: Vec<(ATNStateRef, Vec<ATNStateRef>)> = vec![(start, Vec::new())];
while let Some((state, returns)) = work.pop() {
let number = state.get_state_number();
if number < 0 || state == stop || !visited.insert((number, returns.len())) {
continue;
}
if state.state_type() == ATNStateType::RuleStop {
if let Some(follow) = returns.last() {
let mut next = returns.clone();
next.pop();
work.push((*follow, next));
}
continue;
}
for transition in state.get_transitions() {
if let Some(rule) = transition.try_as::<RuleTransition>() {
let mut next = returns.clone();
next.push(rule.follow_state);
work.push((transition.get_target(), next));
continue;
}
if transition.is_epsilon() {
work.push((transition.get_target(), returns.clone()));
continue;
}
let label: IntervalSetBuf = match transition.transition_type() {
TransitionType::NotSet => transition
.try_as::<NotSetTransition>()
.expect("not-set transition")
.get_label()
.expect("not-set label")
.complement(TOKEN_MIN_USER_TOKEN_TYPE, atn.max_token_type),
TransitionType::Wildcard => {
let mut all = IntervalSetBuf::new();
if atn.max_token_type >= TOKEN_MIN_USER_TOKEN_TYPE {
all.add_range(TOKEN_MIN_USER_TOKEN_TYPE, atn.max_token_type);
}
all
}
_ => match transition.get_label() {
Some(label) => label.to_interval_set_buf(),
None => continue,
},
};
add_intervals(&mut tokens, &label);
}
}
tokens
}
fn add_intervals(tokens: &mut BitSet, label: &IntervalSetBuf) {
for interval in label.as_interval_set().as_slice() {
for token in interval.a..=interval.b {
if token >= 0 {
tokens.insert(token as usize);
}
}
}
}
pub(super) fn epsilon_closure(start: ATNStateRef) -> BitSet {
let mut out = BitSet::new();
let mut work = vec![start];
while let Some(state) = work.pop() {
let number = state.get_state_number();
if number < 0 || !out.insert(number as usize) {
continue;
}
if state.state_type() == ATNStateType::RuleStop {
continue;
}
for transition in state.get_transitions() {
if transition.is_epsilon() {
work.push(transition.get_target());
}
}
}
out
}
pub(super) fn collect_guard_roots(
state: ATNStateRef,
context: Option<PredictionContextRef<'_>>,
mirror: &dyn Fn(ATNStateRef) -> bool,
sites: &HashMap<i32, i32>,
out: &mut BTreeSet<i32>,
) {
let Some(context) = context.filter(|context| !context.is_empty()) else {
out.insert(state.get_state_number());
return;
};
let mut visited: HashSet<*const ()> = HashSet::new();
collect_roots_in(state, &context, mirror, sites, out, &mut visited)
}
fn collect_roots_in(
state: ATNStateRef,
context: &PredictionContextRef<'_>,
mirror: &dyn Fn(ATNStateRef) -> bool,
sites: &HashMap<i32, i32>,
out: &mut BTreeSet<i32>,
visited: &mut HashSet<*const ()>,
) {
if context.is_empty() {
out.insert(state.get_state_number());
return;
}
if !visited.insert(context.as_ref() as *const _ as *const ()) {
return;
}
for index in 0..context.length() {
let return_state = context.get_return_state(index);
match context.get_parent(index) {
Some(parent) if !parent.is_empty() => {
collect_roots_in(state, &parent, mirror, sites, out, visited);
}
_ => {
if return_state == ATNStateRef::empty_return() {
out.insert(state.get_state_number());
} else if !mirror(return_state) {
let number = return_state.get_state_number();
out.insert(sites.get(&number).copied().unwrap_or(number));
}
}
}
}
}
pub(super) struct GuardRegions {
calls: Vec<(i32, Vec<usize>)>,
regions: Vec<BitSet>,
pass: Vec<i32>,
}
impl GuardRegions {
pub(super) fn of(atn: &ATN) -> Self {
let mut calls = Vec::new();
let mut regions = Vec::new();
let mut region_of: HashMap<i32, usize> = HashMap::new();
let mut pass = Vec::new();
for state in atn.iter_states() {
let rule_index = state.get_rule_index();
let rule_stop = if rule_index >= 0 {
atn.rule_to_stop_state[rule_index as usize]
} else {
ATNStateRef::invalid()
};
let mut all_pass = true;
let mut follows = Vec::new();
for transition in state.get_transitions() {
let Some(rule) = transition.try_as::<RuleTransition>() else {
continue;
};
let follow = rule.follow_state.get_state_number();
let index = *region_of.entry(follow).or_insert_with(|| {
regions.push(epsilon_closure(rule.follow_state));
regions.len() - 1
});
if rule_stop.get_state_number() < 0
|| !regions[index].contains(rule_stop.get_state_number() as usize)
{
all_pass = false;
}
follows.push(index);
}
if follows.is_empty() {
continue;
}
if all_pass {
pass.push(state.get_state_number());
}
calls.push((state.get_state_number(), follows));
}
Self {
calls,
regions,
pass,
}
}
pub(super) fn danger(&self, roots: &BTreeSet<i32>) -> Vec<i32> {
self.calls
.iter()
.filter(|(_, follows)| {
follows.iter().any(|&index| {
roots
.iter()
.any(|&root| self.regions[index].contains(root as usize))
})
})
.map(|&(state, _)| state)
.collect()
}
pub(super) fn pass(&self) -> &[i32] {
&self.pass
}
}