///|
/// A side-effect-free parser semantic predicate. The first two arguments
/// identify the rule and predicate. The third is the current visible token.
pub type ParserPredicate = (Int32, Int32, Token) -> Bool
///|
priv struct Outcome {
pos : Int32
context : RuleContext
}
///|
priv struct ParseConfig {
state : Int32
pos : Int32
context : RuleContext
visited : Array[(Int32, Int32)]
}
///|
priv struct ParseContext {
mut predicting : Bool
predicate : ParserPredicate?
partial : Ref[RuleContext?]?
mut partial_pos : Int32
atn : Atn
rules : Array[String]
tokens : Array[Token]
predictor : Predictor
budget : Budget
cache : Map[(Int32, Int32, Int32, Int32), Array[Outcome]]
active : Map[(Int32, Int32, Int32, Int32), Bool]
mut furthest : Int32
expected : Map[Int32, Bool]
}
///|
fn ParseContext::expect(self : ParseContext, pos : Int32, edge : Edge) -> Unit {
if pos > self.furthest {
self.furthest = pos
self.expected.clear()
}
if pos != self.furthest {
return
}
if edge.kind == 5 {
self.expected[if edge.c != 0 { -1 } else { edge.a }] = true
} else {
for symbol in 1..<=self.atn.max_token {
if self.atn.matches(edge, symbol) {
self.expected[symbol] = true
}
}
if self.atn.matches(edge, -1) {
self.expected[-1] = true
}
}
}
///| Ordered bounded traversal with rule/position memoization. This is an
///|
/// Precedence is part of the memoization key, including right-associative calls.
fn parse_rule(
ctx : ParseContext,
rule : Int32,
pos : Int32,
depth : Int32,
precedence : Int32,
outer : Int32,
) -> Array[Outcome] raise RuntimeError {
if depth > 128 {
raise LimitExceeded("parser rule nesting exceeds 128")
}
let key = (rule, pos, precedence, outer)
match ctx.cache.get(key) {
Some(cached) => return cached
None => ()
}
if ctx.active.get(key).unwrap_or(false) {
raise Unsupported("left-recursive rule invocation")
}
ctx.active[key] = true
let work : Array[ParseConfig] = [
{
state: ctx.atn.starts[rule],
pos,
context: { name: ctx.rules[rule], children: [], sources: [], path: [], },
visited: [],
},
]
let results : Array[Outcome] = []
while work.length() > 0 {
ctx.budget.tick()
let cfg = work.pop().unwrap()
let state = ctx.atn.states[cfg.state]
let cfg = { ..cfg, context: cfg.context.enter(cfg.state), }
if depth == 0 && cfg.pos > ctx.partial_pos && ctx.partial is Some(partial) {
ctx.partial_pos = cfg.pos
partial.val = Some(cfg.context)
}
if state.kind == 7 {
results.push({ pos: cfg.pos, context: cfg.context, })
continue
}
let stamp = (cfg.state, cfg.pos)
if cfg.visited.contains(stamp) {
continue
}
let visited = cfg.visited.copy()
visited.push(stamp)
let predicted = if ctx.predicting && state.edges.length() > 1 {
ctx.predictor.predict(cfg.state, precedence, outer, ctx.tokens, cfg.pos)
} else {
[]
}
// The worklist is LIFO: reverse pushes preserve grammar alternative order.
for i = state.edges.length() - 1; i >= 0; i = i - 1 {
if !predicted.is_empty() && !predicted.contains(i) {
continue
}
let edge = state.edges[i]
match edge.kind {
4 =>
if ctx.predicate is Some(check) {
let token = ctx.tokens[cfg.pos.min(ctx.tokens.length() - 1)]
if check(edge.a, edge.b, token) {
work.push({ ..cfg, state: edge.target, visited, })
}
}
1 => {
let context = if ctx.atn.is_precedence_decision(cfg.state) &&
ctx.atn.states[edge.target].kind != 12 {
{
name: ctx.rules[rule],
children: [RuleChild(cfg.context)],
sources: [-1],
path: [],
}
} else {
cfg.context
}
work.push({ ..cfg, state: edge.target, context, visited, })
}
6 => work.push({ ..cfg, state: edge.target, visited, })
10 =>
if edge.a >= precedence {
work.push({ ..cfg, state: edge.target, visited, })
}
3 => {
let outer = ctx.predictor.push(edge.target, precedence, outer)
let outcomes = parse_rule(
ctx,
edge.b,
cfg.pos,
depth + 1,
edge.c,
outer,
)
for j = outcomes.length() - 1; j >= 0; j = j - 1 {
let outcome = outcomes[j]
let context = cfg.context.append(
RuleChild(outcome.context),
cfg.state,
)
work.push({
state: edge.target,
pos: outcome.pos,
context,
visited,
})
}
}
2 | 5 | 7 | 8 | 9 =>
if cfg.pos < ctx.tokens.length() &&
ctx.atn.matches(edge, ctx.tokens[cfg.pos].kind) {
let context = cfg.context.append(
TokenChild(ctx.tokens[cfg.pos]),
cfg.state,
)
work.push({
state: edge.target,
pos: cfg.pos + 1,
context,
visited: [],
})
} else {
ctx.expect(cfg.pos, edge)
}
_ => raise Unsupported("unsupported parser transition")
}
}
}
ctx.active[key] = false
ctx.cache[key] = results
results
}
///| Parse a complete document using a rule index (default: first grammar rule).
///|
/// Non-default channels are filtered, and trailing input is always rejected.
pub fn Grammar::parse_detailed(
self : Grammar,
source : String,
start_rule~ : Int32 = 0,
work_limit~ : Int32 = 1_000_000,
predicate? : ParserPredicate,
) -> ParseResult raise RuntimeError {
let tokens = TokenStream::new(self.tokenize(source, work_limit~)).visible_tokens()
self.parse_tokens(tokens, start_rule, { remaining: work_limit, }, predicate)
}
///|
fn Grammar::parse_tokens(
self : Grammar,
tokens : Array[Token],
start_rule : Int32,
budget : Budget,
predicate : ParserPredicate?,
prefix? : Ref[RuleContext?],
) -> ParseResult raise RuntimeError {
if self.parser.kind != 1 {
raise InvalidAtn("parser ATN expected")
}
self.parser.validate_supported(predicates=predicate is Some(_))
if self.rules.length() != self.parser.starts.length() {
raise InvalidAtn("rule-name table length mismatch")
}
if start_rule < 0 || start_rule >= self.rules.length() {
raise InvalidAtn("unknown start rule")
}
let predictor = Predictor::new(self.parser, budget)
let ctx : ParseContext = {
predicting: predicate is None,
predicate,
partial: prefix,
partial_pos: 0,
predictor,
atn: self.parser,
rules: self.rules,
tokens,
budget,
cache: Map([]),
active: Map([]),
furthest: 0,
expected: Map([]),
}
let outcomes = parse_rule(ctx, start_rule, 0, 0, 0, 0)
// Revisit rejected input without pruning so expected-token diagnostics still
// refer to the furthest syntactic failure, not an earlier prediction exit.
let outcomes = if outcomes.any(outcome => outcome.pos >= tokens.length() - 1) {
outcomes
} else if ctx.predicting {
ctx.predicting = false
ctx.cache.clear()
ctx.active.clear()
parse_rule(ctx, start_rule, 0, 0, 0, 0)
} else {
outcomes
}
for outcome in outcomes {
if outcome.pos == tokens.length() || outcome.pos == tokens.length() - 1 {
return {
context: outcome.context,
prediction: {
decisions: predictor.decisions,
full_context_fallbacks: predictor.fallbacks,
dfa_states: predictor.states.length(),
dfa_hits: predictor.hits,
},
}
}
ctx.expect(outcome.pos, { target: 0, kind: 5, a: 0, b: 0, c: 1, })
}
let expected : Array[Int32] = ctx.expected.keys().collect()
expected.sort()
let index = ctx.furthest.min(tokens.length() - 1)
raise SyntaxError(tokens[index].line, tokens[index].column, expected)
}
///|
/// Parse and return the lightweight, backwards-compatible tree representation.
pub fn Grammar::parse(
self : Grammar,
source : String,
start_rule~ : Int32 = 0,
work_limit~ : Int32 = 1_000_000,
) -> ParseTree raise RuntimeError {
self.parse_context(source, start_rule~, work_limit~).to_tree()
}
///|
/// Parse with concrete rule and element source identities.
pub fn Grammar::parse_context(
self : Grammar,
source : String,
start_rule~ : Int32 = 0,
work_limit~ : Int32 = 1_000_000,
predicate? : ParserPredicate,
) -> RuleContext raise RuntimeError {
self.parse_detailed(source, start_rule~, work_limit~, predicate?).context
}