///|
/// Observable counters for one parse; DFA storage is isolated per parse.
pub(all) struct PredictionStatistics {
decisions : Int32
full_context_fallbacks : Int32
dfa_states : Int32
dfa_hits : Int32
}
///|
pub(all) struct ParseResult {
context : RuleContext
prediction : PredictionStatistics
}
///|
/// Interned return contexts share tails; precedence is restored on rule exit.
priv struct ReturnContext {
state : Int32
precedence : Int32
parent : Int32
}
///|
priv struct PredictionConfig {
state : Int32
edge : Int32
alt : Int32
context : Int32
precedence : Int32
}
///|
priv struct DfaState {
configs : Array[PredictionConfig]
accepted : Array[Int32]
edges : Map[Int32, Int32]
}
///|
priv struct Predictor {
atn : Atn
budget : Budget
returns : Array[ReturnContext]
contexts : Map[(Int32, Int32, Int32), Int32]
states : Array[DfaState]
interned : Map[String, Int32]
starts : Map[(Int32, Int32, Int32), Int32]
mut decisions : Int32
mut fallbacks : Int32
mut hits : Int32
}
///|
fn Predictor::new(atn : Atn, budget : Budget) -> Predictor {
{
atn,
budget,
returns: [{ state: -1, precedence: 0, parent: 0, }],
contexts: Map([]),
states: [],
interned: Map([]),
starts: Map([]),
decisions: 0,
fallbacks: 0,
hits: 0,
}
}
///|
fn Predictor::push(
self : Predictor,
state : Int32,
precedence : Int32,
parent : Int32,
) -> Int32 {
let key = (state, precedence, parent)
if self.contexts.get(key) is Some(id) {
return id
}
let id = self.returns.length()
self.returns.push({ state, precedence, parent, })
self.contexts[key] = id
id
}
///|
fn PredictionConfig::key(self : PredictionConfig) -> String {
"\{self.state}:\{self.edge}:\{self.alt}:\{self.context}:\{self.precedence}"
}
///|
/// Epsilon closure includes internal rule calls and precedence predicates.
/// A stopped outer context is an accepting wildcard in SLL mode. Including
/// the caller's interned return context produces the full-context simulation.
fn Predictor::closure(
self : Predictor,
seeds : Array[PredictionConfig],
) -> Int32 raise RuntimeError {
let work = seeds.copy()
let seen : Map[String, Bool] = Map([])
let configs : Array[PredictionConfig] = []
let accepted : Array[Int32] = []
while work.pop() is Some(cfg) {
self.budget.tick()
let key = cfg.key()
if seen.contains(key) {
continue
}
seen[key] = true
let state = self.atn.states[cfg.state]
if state.kind == 7 {
if cfg.context == 0 {
if !accepted.contains(cfg.alt) {
accepted.push(cfg.alt)
}
} else {
let ret = self.returns[cfg.context]
work.push({
..cfg,
state: ret.state,
edge: -1,
context: ret.parent,
precedence: ret.precedence,
})
}
continue
}
for i, edge in state.edges {
if cfg.edge >= 0 && cfg.edge != i {
continue
}
match edge.kind {
1 | 6 => work.push({ ..cfg, state: edge.target, edge: -1, })
10 =>
if edge.a >= cfg.precedence {
work.push({ ..cfg, state: edge.target, edge: -1, })
}
3 => {
// Recursive nullable calls must terminate under the shared work budget.
let context = self.push(edge.target, cfg.precedence, cfg.context)
work.push({
..cfg,
state: edge.a,
edge: -1,
context,
precedence: edge.c,
})
}
2 | 5 | 7 | 8 | 9 => configs.push({ ..cfg, edge: i, })
_ => raise Unsupported("prediction requires action-free grammar")
}
}
}
let keys = configs.map(c => c.key())
keys.sort()
accepted.sort()
let key = keys.join(";") + "/" + accepted.map(a => a.to_string()).join(",")
if self.interned.get(key) is Some(id) {
self.hits += 1
return id
}
let id = self.states.length()
self.states.push({ configs, accepted, edges: Map([]), })
self.interned[key] = id
id
}
///|
fn Predictor::start(
self : Predictor,
state : Int32,
precedence : Int32,
context : Int32,
) -> Int32 raise RuntimeError {
let key = (state, precedence, context)
if self.starts.get(key) is Some(id) {
self.hits += 1
return id
}
let seeds : Array[PredictionConfig] = []
for i in 0.. Int32 raise RuntimeError {
let state = self.states[id]
if state.edges.get(token) is Some(next) {
self.hits += 1
return next
}
let seeds : Array[PredictionConfig] = []
for cfg in state.configs {
let edge = self.atn.states[cfg.state].edges[cfg.edge]
if self.atn.matches(edge, token) {
seeds.push({ ..cfg, state: edge.target, edge: -1, })
}
}
let next = self.closure(seeds)
state.edges[token] = next
next
}
///|
fn DfaState::alternatives(self : DfaState) -> Array[Int32] {
let alts = self.accepted.copy()
for cfg in self.configs {
if !alts.contains(cfg.alt) {
alts.push(cfg.alt)
}
}
alts.sort()
alts
}
///|
/// Adaptive lookahead with conservative bounded fallback. When 64 tokens do
/// not settle a decision, every surviving alternative remains available to
/// the memoized parser; no unresolved alternative is silently discarded.
fn Predictor::simulate(
self : Predictor,
initial : Int32,
tokens : Array[Token],
pos : Int32,
) -> Array[Int32] raise RuntimeError {
let mut id = initial
let stopped : Array[Int32] = []
for offset in 0..<64 {
let state = self.states[id]
for alt in state.accepted {
if !stopped.contains(alt) {
stopped.push(alt)
}
}
let alts = state.alternatives()
for alt in stopped {
if !alts.contains(alt) {
alts.push(alt)
}
}
if alts.length() <= 1 ||
pos + offset >= tokens.length() ||
state.configs.is_empty() {
return alts
}
id = self.advance(id, tokens[pos + offset].kind)
}
let alts = self.states[id].alternatives()
for alt in stopped {
if !alts.contains(alt) {
alts.push(alt)
}
}
alts
}
///|
fn Predictor::predict(
self : Predictor,
state : Int32,
precedence : Int32,
context : Int32,
tokens : Array[Token],
pos : Int32,
) -> Array[Int32] raise RuntimeError {
self.decisions += 1
let sll = self.simulate(self.start(state, precedence, 0), tokens, pos)
if sll.length() <= 1 || context == 0 {
return sll
}
self.fallbacks += 1
self.simulate(self.start(state, precedence, context), tokens, pos)
}