#[derive(Debug, Default)]
struct DecisionAltLook {
symbols: BTreeSet<i32>,
hit_pred: bool,
nullable: bool,
}
pub(crate) const MAX_FIXED_LOOKAHEAD_FLAG: usize = 8;
const FIXED_LOOKAHEAD_RECTANGLE_BUDGET: usize = 8192;
const FIXED_LOOKAHEAD_STEP_BUDGET: usize = 200_000;
const FIXED_LOOKAHEAD_TABLE_ARM_BUDGET: usize = 256;
pub(crate) fn classify_decisions(
data: &ParserCodegenData<'_>,
fixed_lookahead: Option<usize>,
) -> ParserDecisionAnalysis {
let atn = data.parser_atn();
let max_lookahead = fixed_lookahead.unwrap_or(1);
let mut classification = ParserDecisionAnalysis::default();
for (decision, state_number) in atn.decision_to_state().iter().enumerate() {
let Some(state) = atn.state(state_number) else {
continue;
};
let report = |tier: DecisionTierReport| DecisionReportRow {
decision,
state: state_number,
rule_index: state.rule_index(),
fallback: tier.fallback_capability(),
tier,
};
if state.non_greedy() {
classification.adaptive_decisions.insert(decision);
classification
.report_rows
.push(report(DecisionTierReport::adaptive(
AdaptiveReason::NonGreedy,
0,
)));
continue;
}
if state.precedence_rule_decision() {
classification.adaptive_decisions.insert(decision);
classification
.report_rows
.push(report(DecisionTierReport::adaptive(
AdaptiveReason::Precedence,
0,
)));
continue;
}
let looks: Vec<DecisionAltLook> = state
.transitions()
.iter()
.map(|transition| {
let mut look = DecisionAltLook::default();
let mut walk = DecisionLookWalk {
atn,
owning_rule_stop: state
.rule_index()
.and_then(|rule_index| atn.rule_to_stop_state().get(rule_index)),
busy: BTreeSet::new(),
called_rules: vec![false; atn.rule_to_start_state().len()],
};
walk.walk(transition.target(), &mut Vec::new(), &mut look);
look
})
.collect();
if looks.iter().any(|look| look.hit_pred) {
classification.adaptive_decisions.insert(decision);
classification
.report_rows
.push(report(DecisionTierReport::adaptive(
AdaptiveReason::Predicate,
1,
)));
continue;
}
if looks.iter().any(|look| look.symbols.is_empty()) {
classification.adaptive_decisions.insert(decision);
classification
.report_rows
.push(report(DecisionTierReport::adaptive(
AdaptiveReason::EmptyLook,
1,
)));
continue;
}
if decision_alt_looks_disjoint(&looks) {
let arms: Vec<Vec<(i32, i32)>> = looks
.iter()
.map(|look| symbol_intervals(&look.symbols))
.collect();
let default_alt = looks
.iter()
.enumerate()
.find_map(|(index, look)| look.nullable.then_some(index + 1));
if fixed_lookahead.is_some() {
let root = FixedLookaheadNode::Probe(
arms.iter()
.enumerate()
.filter(|(_, intervals)| !intervals.is_empty())
.map(|(index, intervals)| {
(intervals.clone(), FixedLookaheadNode::Alt(index + 1))
})
.collect(),
);
if let Some(root) = restrict_dispatch_to_sync_noop(atn, state, root) {
classification
.ll1_dispatch_tables
.insert(decision, FixedLookaheadTable { lookahead: 1, root });
}
}
classification.complete_ll1_dispatches.insert(
decision,
CompleteLl1Dispatch {
fast_path: GeneratedDecisionFastPath {
arms: arms
.into_iter()
.enumerate()
.map(|(index, intervals)| GeneratedDecisionFastArm {
alt: index + 1,
intervals,
})
.collect(),
},
default_alt,
},
);
classification
.report_rows
.push(report(DecisionTierReport::Ll1));
continue;
}
classification.adaptive_decisions.insert(decision);
let mut tier = DecisionTierReport::adaptive(AdaptiveReason::NotDisjoint, max_lookahead);
for depth in 2..=max_lookahead {
match fixed_lookahead_table(atn, state, depth) {
FixedLookaheadOutcome::Table(table) => {
match restrict_dispatch_to_sync_noop(atn, state, table.root) {
Some(root) => {
classification.fixed_lookahead_tables.insert(
decision,
FixedLookaheadTable {
lookahead: table.lookahead,
root,
},
);
tier = DecisionTierReport::Fixed { lookahead: depth };
}
None => {
tier = DecisionTierReport::adaptive(AdaptiveReason::SyncBound, depth);
}
}
break;
}
FixedLookaheadOutcome::NotDisjoint => {}
FixedLookaheadOutcome::Predicate => {
tier = DecisionTierReport::adaptive(AdaptiveReason::Predicate, depth);
break;
}
FixedLookaheadOutcome::Budget => {
tier = DecisionTierReport::adaptive(AdaptiveReason::Budget, depth);
break;
}
}
}
classification.report_rows.push(report(tier));
}
classification
}
fn restrict_dispatch_to_sync_noop(
atn: &ParserAtn,
state: ParserAtnState<'_>,
root: FixedLookaheadNode,
) -> Option<FixedLookaheadNode> {
let allowed = sync_noop_symbol_intervals(atn, state);
let FixedLookaheadNode::Probe(arms) = root else {
return None;
};
let arms: Vec<(Vec<(i32, i32)>, FixedLookaheadNode)> = arms
.into_iter()
.filter_map(|(intervals, child)| {
let restricted = intersect_interval_sets(&intervals, &allowed);
(!restricted.is_empty()).then_some((restricted, child))
})
.collect();
(!arms.is_empty()).then_some(FixedLookaheadNode::Probe(arms))
}
pub(crate) fn sync_noop_symbol_intervals(
atn: &ParserAtn,
state: ParserAtnState<'_>,
) -> Vec<(i32, i32)> {
let Some(rule_index) = state.rule_index() else {
return Vec::new();
};
let Some(rule_stop) = atn.rule_to_stop_state().get(rule_index) else {
return Vec::new();
};
let mut ctx = GeneratedFirstSetCtx::default();
let mut symbols = BTreeSet::new();
for transition in state.transitions() {
let direct = generated_transition_symbols(transition, atn.max_token_type());
if !direct.is_empty() {
symbols.extend(direct);
continue;
}
match transition.data() {
ParserTransitionData::Rule {
target,
rule_index: child_rule,
follow_state,
..
} => {
let Some(child_stop) = atn.rule_to_stop_state().get(child_rule) else {
continue;
};
let child = generated_rule_first_set(atn, target, child_stop, &mut ctx);
symbols.extend(child.symbols.iter().copied());
if child.nullable {
let follow = generated_rule_first_set(atn, follow_state, rule_stop, &mut ctx);
symbols.extend(follow.symbols.iter().copied());
}
}
ParserTransitionData::Epsilon { target }
| ParserTransitionData::Action { target, .. }
| ParserTransitionData::Predicate { target, .. }
| ParserTransitionData::Precedence { target, .. } => {
let first = generated_rule_first_set(atn, target, rule_stop, &mut ctx);
symbols.extend(first.symbols.iter().copied());
}
_ => {}
}
}
symbol_intervals(&symbols)
}
pub(crate) fn intersect_interval_sets(
left: &[(i32, i32)],
right: &[(i32, i32)],
) -> Vec<(i32, i32)> {
let mut result = Vec::new();
let (mut left_index, mut right_index) = (0, 0);
while left_index < left.len() && right_index < right.len() {
let (left_start, left_stop) = left[left_index];
let (right_start, right_stop) = right[right_index];
let start = left_start.max(right_start);
let stop = left_stop.min(right_stop);
if start <= stop {
result.push((start, stop));
}
if left_stop < right_stop {
left_index += 1;
} else {
right_index += 1;
}
}
result
}
#[derive(Debug, Default)]
pub(crate) struct ParserDecisionAnalysis {
pub(crate) adaptive_decisions: BTreeSet<usize>,
pub(crate) complete_ll1_dispatches: BTreeMap<usize, CompleteLl1Dispatch>,
pub(crate) ll1_dispatch_tables: BTreeMap<usize, FixedLookaheadTable>,
pub(crate) fixed_lookahead_tables: BTreeMap<usize, FixedLookaheadTable>,
pub(crate) report_rows: Vec<DecisionReportRow>,
}
#[derive(Clone, Debug)]
pub(crate) struct DecisionReportRow {
pub(crate) decision: usize,
pub(crate) state: usize,
pub(crate) rule_index: Option<usize>,
pub(crate) fallback: DecisionFallbackCapability,
pub(crate) tier: DecisionTierReport,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum DecisionTierReport {
Ll1,
Fixed { lookahead: usize },
Adaptive {
reason: AdaptiveReason,
probed_lookahead: usize,
},
}
impl DecisionTierReport {
const fn adaptive(reason: AdaptiveReason, probed_lookahead: usize) -> Self {
Self::Adaptive {
reason,
probed_lookahead,
}
}
const fn fallback_capability(self) -> DecisionFallbackCapability {
match self {
Self::Ll1 => DecisionFallbackCapability::None,
Self::Fixed { .. } | Self::Adaptive { .. } => DecisionFallbackCapability::CanDefer,
}
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum DecisionFallbackCapability {
None,
CanDefer,
}
impl DecisionFallbackCapability {
pub(crate) const fn can_defer(self) -> bool {
matches!(self, Self::CanDefer)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum AdaptiveReason {
NonGreedy,
Precedence,
Predicate,
EmptyLook,
NotDisjoint,
Budget,
SyncBound,
}
impl AdaptiveReason {
pub(crate) const fn manifest_name(self) -> &'static str {
match self {
Self::NonGreedy => "non-greedy",
Self::Precedence => "precedence",
Self::Predicate => "predicate",
Self::EmptyLook => "empty-look",
Self::NotDisjoint => "not-disjoint",
Self::Budget => "budget-exceeded",
Self::SyncBound => "sync-bound",
}
}
}
type LookaheadRectangle = Vec<Vec<(i32, i32)>>;
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct FixedLookaheadTable {
pub(crate) lookahead: usize,
pub(crate) root: FixedLookaheadNode,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) enum FixedLookaheadNode {
Alt(usize),
Probe(Vec<(Vec<(i32, i32)>, Self)>),
}
enum FixedLookaheadOutcome {
Table(FixedLookaheadTable),
NotDisjoint,
Predicate,
Budget,
}
fn fixed_lookahead_table(
atn: &ParserAtn,
state: ParserAtnState<'_>,
depth: usize,
) -> FixedLookaheadOutcome {
let mut alt_rectangles: Vec<Vec<LookaheadRectangle>> = Vec::new();
for transition in state.transitions() {
let mut walk = FixedLookaheadWalk {
atn,
depth_limit: depth,
steps: 0,
};
match walk.alt_rectangles(transition.target()) {
Ok(rectangles) if rectangles.is_empty() => {
return FixedLookaheadOutcome::NotDisjoint;
}
Ok(rectangles) => alt_rectangles.push(rectangles),
Err(FixedWalkBail::Predicate) => return FixedLookaheadOutcome::Predicate,
Err(FixedWalkBail::Budget) => return FixedLookaheadOutcome::Budget,
}
}
for (left, left_rectangles) in alt_rectangles.iter().enumerate() {
for right_rectangles in alt_rectangles.iter().skip(left + 1) {
let overlap = left_rectangles.iter().any(|left_rectangle| {
right_rectangles
.iter()
.any(|right_rectangle| rectangles_overlap(left_rectangle, right_rectangle))
});
if overlap {
return FixedLookaheadOutcome::NotDisjoint;
}
}
}
let items: Vec<(usize, &LookaheadRectangle)> = alt_rectangles
.iter()
.enumerate()
.flat_map(|(index, rectangles)| {
rectangles
.iter()
.map(move |rectangle| (index + 1, rectangle))
})
.collect();
match build_fixed_lookahead_node(&items, 0, depth) {
Some(root) => {
if fixed_lookahead_node_arm_count(&root) > FIXED_LOOKAHEAD_TABLE_ARM_BUDGET {
return FixedLookaheadOutcome::Budget;
}
FixedLookaheadOutcome::Table(FixedLookaheadTable {
lookahead: depth,
root,
})
}
None => FixedLookaheadOutcome::NotDisjoint,
}
}
fn fixed_lookahead_node_arm_count(node: &FixedLookaheadNode) -> usize {
match node {
FixedLookaheadNode::Alt(_) => 1,
FixedLookaheadNode::Probe(arms) => arms
.iter()
.map(|(_, child)| 1 + fixed_lookahead_node_arm_count(child))
.sum(),
}
}
fn rectangles_overlap(left: &LookaheadRectangle, right: &LookaheadRectangle) -> bool {
left.iter()
.zip(right.iter())
.all(|(left_set, right_set)| interval_sets_intersect(left_set, right_set))
}
fn interval_sets_intersect(left: &[(i32, i32)], right: &[(i32, i32)]) -> bool {
let (mut left_index, mut right_index) = (0, 0);
while left_index < left.len() && right_index < right.len() {
let (left_start, left_stop) = left[left_index];
let (right_start, right_stop) = right[right_index];
if left_stop < right_start {
left_index += 1;
} else if right_stop < left_start {
right_index += 1;
} else {
return true;
}
}
false
}
fn build_fixed_lookahead_node(
items: &[(usize, &LookaheadRectangle)],
dim: usize,
depth: usize,
) -> Option<FixedLookaheadNode> {
let first_alt = items.first().map(|(alt, _)| *alt)?;
if items.iter().all(|(alt, _)| *alt == first_alt) {
return Some(FixedLookaheadNode::Alt(first_alt));
}
if dim >= depth {
return None;
}
let mut bounds = BTreeSet::new();
for (_, rectangle) in items {
for (start, stop) in &rectangle[dim] {
bounds.insert(*start);
bounds.insert(stop.checked_add(1)?);
}
}
let bounds: Vec<i32> = bounds.into_iter().collect();
let mut arms: Vec<(Vec<(i32, i32)>, FixedLookaheadNode)> = Vec::new();
for window in bounds.windows(2) {
let (atom_start, atom_stop) = (window[0], window[1] - 1);
let covering: Vec<(usize, &LookaheadRectangle)> = items
.iter()
.filter(|(_, rectangle)| {
interval_sets_intersect(&rectangle[dim], &[(atom_start, atom_start)])
})
.copied()
.collect();
if covering.is_empty() {
continue;
}
let child = build_fixed_lookahead_node(&covering, dim + 1, depth)?;
match arms.iter_mut().find(|(_, existing)| *existing == child) {
Some((intervals, _)) => push_coalesced_interval(intervals, atom_start, atom_stop),
None => arms.push((vec![(atom_start, atom_stop)], child)),
}
}
Some(FixedLookaheadNode::Probe(arms))
}
fn push_coalesced_interval(intervals: &mut Vec<(i32, i32)>, start: i32, stop: i32) {
match intervals.last_mut() {
Some((_, last_stop)) if *last_stop + 1 == start => *last_stop = stop,
_ => intervals.push((start, stop)),
}
}
enum FixedWalkBail {
Predicate,
Budget,
}
struct FixedLookaheadWalk<'a> {
atn: &'a ParserAtn,
depth_limit: usize,
steps: usize,
}
impl FixedLookaheadWalk<'_> {
fn alt_rectangles(&mut self, start: usize) -> Result<Vec<LookaheadRectangle>, FixedWalkBail> {
let mut rectangles = Vec::new();
let rule_count = self.atn.rule_to_start_state().len();
self.segment(
start,
&mut Vec::new(),
&mut BTreeSet::new(),
&mut vec![false; rule_count],
&[],
&mut rectangles,
)?;
Ok(rectangles)
}
#[allow(clippy::too_many_lines, clippy::too_many_arguments)]
fn segment(
&mut self,
state_number: usize,
ctx: &mut Vec<usize>,
busy: &mut BTreeSet<(usize, Vec<usize>)>,
called_rules: &mut Vec<bool>,
prefix: &[Vec<(i32, i32)>],
out: &mut Vec<LookaheadRectangle>,
) -> Result<(), FixedWalkBail> {
self.steps += 1;
if self.steps > FIXED_LOOKAHEAD_STEP_BUDGET {
return Err(FixedWalkBail::Budget);
}
if !busy.insert((state_number, ctx.clone())) {
return Ok(());
}
let Some(state) = self.atn.state(state_number) else {
return Ok(());
};
if state.kind() == AtnStateKind::RuleStop {
if let Some(return_state) = ctx.pop() {
let cleared = state
.rule_index()
.map(|rule| std::mem::replace(&mut called_rules[rule], false));
let result = self.segment(return_state, ctx, busy, called_rules, prefix, out);
if let (Some(rule), Some(flag)) = (state.rule_index(), cleared) {
called_rules[rule] = flag;
}
ctx.push(return_state);
return result;
}
if state.transitions().is_empty() {
self.emit_eof_padded(prefix.to_vec(), out)?;
return Ok(());
}
}
for transition in state.transitions() {
match transition.data() {
ParserTransitionData::Rule {
target,
rule_index,
follow_state,
..
} => {
if called_rules.get(rule_index).copied().unwrap_or(true) {
continue;
}
called_rules[rule_index] = true;
ctx.push(follow_state);
let result = self.segment(target, ctx, busy, called_rules, prefix, out);
ctx.pop();
called_rules[rule_index] = false;
result?;
}
ParserTransitionData::Predicate { .. }
| ParserTransitionData::Precedence { .. } => {
return Err(FixedWalkBail::Predicate);
}
ParserTransitionData::Epsilon { target }
| ParserTransitionData::Action { target, .. } => {
self.segment(target, ctx, busy, called_rules, prefix, out)?;
}
_ => {
let mut symbols =
generated_transition_symbols(transition, self.atn.max_token_type());
if symbols.remove(&TOKEN_EOF) {
let mut rectangle = prefix.to_vec();
rectangle.push(vec![(TOKEN_EOF, TOKEN_EOF)]);
self.emit_eof_padded(rectangle, out)?;
}
if symbols.is_empty() {
continue;
}
let mut extended = prefix.to_vec();
extended.push(symbol_intervals(&symbols));
if extended.len() == self.depth_limit {
push_rectangle(out, extended)?;
} else {
let rule_count = called_rules.len();
self.segment(
transition.target(),
ctx,
&mut BTreeSet::new(),
&mut vec![false; rule_count],
&extended,
out,
)?;
}
}
}
}
Ok(())
}
fn emit_eof_padded(
&self,
mut rectangle: LookaheadRectangle,
out: &mut Vec<LookaheadRectangle>,
) -> Result<(), FixedWalkBail> {
while rectangle.len() < self.depth_limit {
rectangle.push(vec![(TOKEN_EOF, TOKEN_EOF)]);
}
push_rectangle(out, rectangle)
}
}
fn push_rectangle(
out: &mut Vec<LookaheadRectangle>,
rectangle: LookaheadRectangle,
) -> Result<(), FixedWalkBail> {
if out.len() >= FIXED_LOOKAHEAD_RECTANGLE_BUDGET {
return Err(FixedWalkBail::Budget);
}
out.push(rectangle);
Ok(())
}
fn symbol_intervals(symbols: &BTreeSet<i32>) -> Vec<(i32, i32)> {
let mut intervals: Vec<(i32, i32)> = Vec::new();
for &symbol in symbols {
match intervals.last_mut() {
Some((_, stop)) if *stop + 1 == symbol => *stop = symbol,
_ => intervals.push((symbol, symbol)),
}
}
intervals
}
fn decision_alt_looks_disjoint(looks: &[DecisionAltLook]) -> bool {
let mut combined = BTreeSet::new();
for look in looks {
if look.hit_pred || look.symbols.is_empty() {
return false;
}
if look.symbols.intersection(&combined).next().is_some() {
return false;
}
combined.extend(look.symbols.iter().copied());
}
true
}
struct DecisionLookWalk<'a> {
atn: &'a ParserAtn,
owning_rule_stop: Option<usize>,
busy: BTreeSet<(usize, Vec<usize>)>,
called_rules: Vec<bool>,
}
impl DecisionLookWalk<'_> {
fn walk(&mut self, state_number: usize, ctx: &mut Vec<usize>, look: &mut DecisionAltLook) {
if !self.busy.insert((state_number, ctx.clone())) {
return;
}
if self.owning_rule_stop == Some(state_number) && ctx.is_empty() {
look.nullable = true;
}
let Some(state) = self.atn.state(state_number) else {
return;
};
if state.kind() == AtnStateKind::RuleStop {
if let Some(return_state) = ctx.pop() {
let cleared = state
.rule_index()
.map(|rule| std::mem::replace(&mut self.called_rules[rule], false));
self.walk(return_state, ctx, look);
if let (Some(rule), Some(flag)) = (state.rule_index(), cleared) {
self.called_rules[rule] = flag;
}
ctx.push(return_state);
return;
}
if state.transitions().is_empty() {
look.symbols.insert(TOKEN_EOF);
return;
}
}
for transition in state.transitions() {
match transition.data() {
ParserTransitionData::Rule {
target,
rule_index,
follow_state,
..
} => {
if self.called_rules.get(rule_index).copied().unwrap_or(true) {
continue;
}
self.called_rules[rule_index] = true;
ctx.push(follow_state);
self.walk(target, ctx, look);
ctx.pop();
self.called_rules[rule_index] = false;
}
ParserTransitionData::Predicate { .. }
| ParserTransitionData::Precedence { .. } => {
look.hit_pred = true;
}
ParserTransitionData::Epsilon { target }
| ParserTransitionData::Action { target, .. } => {
self.walk(target, ctx, look);
}
_ => {
for symbol in TOKEN_EOF..=self.atn.max_token_type() {
if transition.matches(symbol, 1, self.atn.max_token_type()) {
look.symbols.insert(symbol);
}
}
}
}
}
}
}