1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
// SPDX-License-Identifier: BSD-3-Clause
// Copyright (c) 2026 Bo Lin
//! Owned snapshot of a decision DFA, plus the graph queries the report needs.
use std::collections::VecDeque;
use dbt_antlr_runtime::dfa::static_parser_dfa::{ParserContinuation, VIRTUAL_ALT_BASE};
use super::hazard::{StackHijackVerdict, StateHazard};
use super::{CONFLICT_ESCAPE, ESCAPE, EscapeResolution, GUARDED};
/// One DFA state of a decision table.
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct StaticDfaState {
/// `> 0` is the predicted alternative of an accept state, [`ESCAPE`] and
/// [`CONFLICT_ESCAPE`] mark escapes, and `0` marks a decision state that
/// has outgoing edges.
pub(crate) accept: i32,
/// Lowest alternative that already left the decision (a rule stop reached
/// with an empty context). The runtime falls back to it when no edge
/// matches the lookahead.
pub(crate) fallback: i32,
/// Number of tokens read to reach this state.
pub(crate) depth: usize,
/// Alternatives SLL could not separate here, when this state is a
/// conflict.
pub(crate) conflicts: Vec<i32>,
/// The lowest conflicting alternative of a conflict escape state, when the
/// table can hand the conflict over to full-context prediction directly.
pub(crate) conflict_min_alt: i32,
/// The alternative a guarded state resolves to, `0` when the state is not
/// guarded. A guarded state takes its alternative unless the runtime stack
/// guard defers.
pub(crate) guarded_alt: i32,
/// The other alternative of a guarded state: the skip of an optional
/// postfix or the exit of a precedence loop. A table that keeps the
/// adaptive fallback defers to the adaptive simulation instead.
pub(crate) guard_defer_alt: i32,
/// The guard group of a guarded state: an index into
/// [`StaticDfaTable::guard_groups`].
pub(crate) guard_group: u32,
/// The closed config set of a frontier escape state, when SLL can resume
/// from it instead of restarting at the decision start.
pub(crate) continuation: Option<ParserContinuation>,
/// The sorted alternatives that are still viable in an escape state. The
/// list is empty for the other states.
pub(crate) viable_alts: Vec<i32>,
/// `true` for an escape state that a predicate in its config set made
/// undecidable.
pub(crate) predicated: bool,
/// How `--static-dfa-only` replaced the escape verdict of this state, when
/// it did.
pub(crate) resolution: Option<EscapeResolution>,
/// The prefix-hijack hazard of the guess of an escape state, under
/// `--static-dfa-only`, when the analysis ran for the state.
pub(crate) hazard: Option<StateHazard>,
/// The stack-hijack hazard of the guard of a guarded state, under
/// `--static-dfa-only`, when the analysis ran for the state.
pub(crate) stack_hazard: Option<StackHijackVerdict>,
pub(crate) edges: Vec<StaticDfaEdge>,
}
impl StaticDfaState {
pub(crate) fn is_escape(&self) -> bool {
self.accept == ESCAPE || self.accept == CONFLICT_ESCAPE
}
pub(crate) fn is_accept(&self) -> bool {
self.accept > 0
}
pub(crate) fn is_guarded(&self) -> bool {
self.accept == GUARDED
}
}
/// One token-interval edge of a state. `lo == hi` is a single-token edge.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct StaticDfaEdge {
/// Inclusive token type; `-1` is the EOF edge.
pub(crate) lo: i32,
/// Inclusive token type.
pub(crate) hi: i32,
/// Index into [`StaticDfaTable::states`].
pub(crate) target: usize,
}
/// The built DFA of one decision (or of one precedence class).
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct StaticDfaTable {
pub(crate) decision: usize,
/// `true` when the edge graph has a cycle: the lookahead is unbounded.
pub(crate) cyclic: bool,
/// Longest path from the start state, `-1` for a cyclic table.
pub(crate) max_k: i32,
/// State `0` is the start state.
pub(crate) states: Vec<StaticDfaState>,
/// The danger set of every guard group: sorted invoking states whose
/// follow region reaches a guard root of the group. The runtime guard of a
/// state walks up the parse stack through the frames of
/// [`Self::guard_pass`]. It defers when it reaches an invoking state of the
/// danger set of its group.
pub(crate) guard_groups: Vec<Vec<i32>>,
/// Sorted invoking states whose follow region can pop out of its rule:
/// the runtime guard continues up the stack.
pub(crate) guard_pass: Vec<i32>,
}
impl StaticDfaTable {
/// Finalizes the graph-level facts of a table built state by state.
pub(super) fn finish(decision: usize, states: Vec<StaticDfaState>) -> Self {
let cyclic = is_cyclic(&states);
let max_k = if cyclic { -1 } else { longest_path(&states) };
Self {
decision,
cyclic,
max_k,
states,
guard_groups: Vec::new(),
guard_pass: Vec::new(),
}
}
pub(crate) fn escapes(&self) -> usize {
self.states.iter().filter(|state| state.is_escape()).count()
}
/// The number of states that requires a runtime stack walk.
pub(crate) fn guarded(&self) -> usize {
self.states
.iter()
.filter(|state| state.is_guarded())
.count()
}
/// The number of states that accept with the virtual alternative of a
/// shared-descent group.
pub(crate) fn descent_group_states(&self) -> usize {
self.states
.iter()
.filter(|state| state.accept >= VIRTUAL_ALT_BASE)
.count()
}
/// The sorted union of the danger sets of all guard groups.
#[cfg(test)]
pub(crate) fn guard_danger(&self) -> Vec<i32> {
let mut danger: Vec<i32> = self.guard_groups.iter().flatten().copied().collect();
danger.sort_unstable();
danger.dedup();
danger
}
/// How much of the start state's alphabet leads to an accepting state.
pub(crate) fn start_coverage(&self) -> f64 {
let Some(start) = self.states.first() else {
return 0.0;
};
let mut reaches_accept = vec![false; self.states.len()];
let mut reverse = vec![Vec::new(); self.states.len()];
for (index, state) in self.states.iter().enumerate() {
for edge in &state.edges {
reverse[edge.target].push(index);
}
}
let mut work = VecDeque::new();
for (index, state) in self.states.iter().enumerate() {
if state.is_accept() || state.is_guarded() {
reaches_accept[index] = true;
work.push_back(index);
}
}
while let Some(current) = work.pop_front() {
for &previous in &reverse[current] {
if !reaches_accept[previous] {
reaches_accept[previous] = true;
work.push_back(previous);
}
}
}
let mut total = 0_i64;
let mut useful = 0_i64;
for edge in &start.edges {
let width = i64::from(edge.hi - edge.lo + 1);
total += width;
if reaches_accept[edge.target] {
useful += width;
}
}
if total == 0 {
0.0
} else {
useful as f64 / total as f64
}
}
/// The number of tokens on a shortest path from the start state to each
/// state, `usize::MAX` for a state that the start state does not reach.
pub(crate) fn depths(&self) -> Vec<usize> {
let mut depths = vec![usize::MAX; self.states.len()];
let Some(first) = depths.first_mut() else {
return depths;
};
*first = 0;
let mut queue = VecDeque::from([0_usize]);
while let Some(current) = queue.pop_front() {
for edge in &self.states[current].edges {
if depths[edge.target] == usize::MAX {
depths[edge.target] = depths[current] + 1;
queue.push_back(edge.target);
}
}
}
depths
}
/// A shortest lookahead path from the start state to `target`, one token
/// per edge (the lowest token of the edge interval).
pub(crate) fn witness(&self, target: usize) -> Option<Vec<i32>> {
if target >= self.states.len() {
return None;
}
let mut parent: Vec<Option<usize>> = vec![None; self.states.len()];
let mut parent_token = vec![0_i32; self.states.len()];
let mut queue = VecDeque::new();
parent[0] = Some(0);
queue.push_back(0_usize);
while let Some(current) = queue.pop_front() {
if current == target {
break;
}
for edge in &self.states[current].edges {
if parent[edge.target].is_none() {
parent[edge.target] = Some(current);
parent_token[edge.target] = edge.lo;
queue.push_back(edge.target);
}
}
}
parent[target]?;
let mut path = Vec::new();
let mut cursor = target;
while cursor != 0 {
path.push(parent_token[cursor]);
cursor = parent[cursor]?;
}
path.reverse();
Some(path)
}
/// The first escape state with the given marker.
pub(crate) fn first_escape(&self, marker: i32) -> Option<usize> {
self.states.iter().position(|state| state.accept == marker)
}
}
fn is_cyclic(states: &[StaticDfaState]) -> bool {
let mut color = vec![0_u8; states.len()];
let mut stack: Vec<(usize, usize)> = Vec::new();
for root in 0..states.len() {
if color[root] != 0 {
continue;
}
stack.push((root, 0));
color[root] = 1;
while let Some((state, edge_index)) = stack.last_mut() {
let current = *state;
if *edge_index < states[current].edges.len() {
let target = states[current].edges[*edge_index].target;
*edge_index += 1;
match color[target] {
1 => return true,
0 => {
color[target] = 1;
stack.push((target, 0));
}
_ => {}
}
} else {
color[current] = 2;
stack.pop();
}
}
}
false
}
fn longest_path(states: &[StaticDfaState]) -> i32 {
if states.is_empty() {
return 0;
}
let mut memo = vec![-1_i32; states.len()];
longest_path_from(0, states, &mut memo)
}
fn longest_path_from(state: usize, states: &[StaticDfaState], memo: &mut [i32]) -> i32 {
if memo[state] >= 0 {
return memo[state];
}
memo[state] = 0;
let mut max_length = 0;
for edge in &states[state].edges {
max_length = max_length.max(1 + longest_path_from(edge.target, states, memo));
}
memo[state] = max_length;
max_length
}