///|
priv struct Budget {
mut remaining : Int32
}
///|
fn Budget::tick(self : Budget) -> Unit raise RuntimeError {
if self.remaining <= 0 {
raise LimitExceeded("ATN work budget exhausted")
}
self.remaining -= 1
}
///|
priv struct LexConfig {
state : Int32
pos : Int32
root : Int32
returns : Array[Int32]
actions : Array[Int32]
passed_non_greedy : Bool
}
///|
fn LexConfig::key(self : LexConfig) -> String {
let out = StringBuilder()
out.write_string(
self.state.to_string() +
":" +
self.pos.to_string() +
":" +
self.root.to_string(),
)
if self.passed_non_greedy {
out.write_string("!")
}
for n in self.returns {
out.write_string("/" + n.to_string())
}
out.write_string(":")
for n in self.actions {
out.write_string("/" + n.to_string())
}
out.to_string()
}
///|
/// Ordered NFA execution. A rule acceptance suppresses lower-priority paths
/// that passed a non-greedy decision. Competing rules still prefer longest match.
fn lex_match(
atn : Atn,
chars : Array[Char],
start : Int32,
mode : Int32,
budget : Budget,
) -> LexConfig? raise RuntimeError {
if mode < 0 || mode >= atn.modes.length() {
raise InvalidAtn("unknown lexer mode")
}
let work : Array[LexConfig] = []
let entries = atn.states[atn.modes[mode]].edges
for i = entries.length() - 1; i >= 0; i = i - 1 {
let edge = entries[i]
if edge.kind != 1 {
raise InvalidAtn("mode must enter rules through epsilon edges")
}
if atn.states[edge.target].kind != 2 {
raise InvalidAtn("mode must enter a rule start")
}
work.push({
state: edge.target,
pos: start,
root: atn.states[edge.target].rule,
returns: [],
actions: [],
passed_non_greedy: false,
})
}
let seen : Map[String, Bool] = Map([])
let mut best : LexConfig? = None
let mut next : Array[LexConfig] = []
let accepted : Map[Int32, Bool] = Map([])
while !work.is_empty() || !next.is_empty() {
if work.is_empty() {
for i = next.length() - 1; i >= 0; i = i - 1 {
work.push(next[i])
}
next = []
accepted.clear()
seen.clear()
}
budget.tick()
let cfg = work.pop().unwrap()
let state = atn.states[cfg.state]
let cfg = {
..cfg,
passed_non_greedy: cfg.passed_non_greedy || state.non_greedy,
}
if cfg.passed_non_greedy && accepted.contains(cfg.root) {
continue
}
let key = cfg.key()
if seen.contains(key) {
continue
}
seen[key] = true
if state.kind == 7 {
if cfg.returns.is_empty() {
accepted[cfg.root] = true
match best {
None => best = Some(cfg)
Some(old) =>
if cfg.pos > old.pos || (cfg.pos == old.pos && cfg.root < old.root) {
best = Some(cfg)
}
}
} else {
let returns = cfg.returns.copy()
let target = returns.pop().unwrap()
work.push({ ..cfg, state: target, returns, })
}
continue
}
for i = state.edges.length() - 1; i >= 0; i = i - 1 {
let edge = state.edges[i]
match edge.kind {
1 => work.push({ ..cfg, state: edge.target, })
3 => {
if cfg.returns.length() >= 64 {
raise LimitExceeded("lexer rule nesting exceeds 64")
}
let returns = cfg.returns.copy()
returns.push(edge.target)
work.push({ ..cfg, state: edge.a, returns, })
}
6 => {
let actions = cfg.actions.copy()
actions.push(edge.b)
work.push({ ..cfg, state: edge.target, actions, })
}
2 | 5 | 7 | 8 | 9 => {
let symbol = if cfg.pos < chars.length() {
chars[cfg.pos].to_int()
} else {
-1
}
if atn.matches(edge, symbol) {
if symbol == -1 {
work.push({ ..cfg, state: edge.target, })
} else {
next.push({ ..cfg, state: edge.target, pos: cfg.pos + 1, })
}
}
}
_ => raise Unsupported("unsupported lexer transition")
}
}
}
best
}
///|
/// Tokenize using the generated lexer ATN. Hidden channels are retained.
pub fn Atn::tokenize(
self : Atn,
source : String,
work_limit~ : Int32 = 1_000_000,
) -> Array[Token] raise RuntimeError {
if self.kind != 0 {
raise InvalidAtn("lexer ATN expected")
}
self.validate_supported()
let budget = Budget::{ remaining: work_limit, }
let chars = source.to_array()
let tokens : Array[Token] = []
let modes : Array[Int32] = []
let mut mode = 0
let mut pos = 0
let mut line = 1
let mut column = 0
let mut token_start = 0
let mut token_line = 1
let mut token_column = 0
let mut continuing = false
let mut channel = 0
while pos < chars.length() {
if !continuing {
token_start = pos
token_line = line
token_column = column
channel = 0
}
let accepted = match lex_match(self, chars, pos, mode, budget) {
Some(cfg) => cfg
None => raise LexicalError(line, column, "no lexer rule matches input")
}
if accepted.pos == pos {
raise Unsupported("zero-width lexer token")
}
let mut kind = self.token_types[accepted.root]
let mut skip = false
let mut more = false
for index in accepted.actions {
let (action, argument, _) = self.actions[index]
match action {
0 => channel = argument
2 => mode = argument
3 => more = true
4 =>
mode = match modes.pop() {
Some(previous) => previous
None =>
raise LexicalError(
token_line, token_column, "lexer mode stack underflow",
)
}
5 => {
modes.push(mode)
mode = argument
}
6 => skip = true
7 => kind = argument
_ => raise Unsupported("custom lexer action")
}
}
for i in pos..= self.modes.length() {
raise InvalidAtn("lexer action selected unknown mode")
}
continuing = more && !skip
if !skip && !more {
if kind <= 0 || kind > self.max_token || channel < 0 {
raise InvalidAtn("invalid emitted token type or channel")
}
tokens.push({
kind,
text: String::from_array(chars[token_start:pos]),
start: token_start,
end: pos,
line: token_line,
column: token_column,
channel,
})
}
}
tokens.push({
kind: -1,
text: if continuing {
String::from_array(chars[token_start:pos])
} else {
""
},
start: if continuing {
token_start
} else {
pos
},
end: pos,
line: if continuing {
token_line
} else {
line
},
column: if continuing {
token_column
} else {
column
},
channel: if continuing {
channel
} else {
0
},
})
tokens
}
///|
/// Tokenize a source with this grammar's lexer.
pub fn Grammar::tokenize(
self : Grammar,
source : String,
work_limit~ : Int32 = 1_000_000,
) -> Array[Token] raise RuntimeError {
self.lexer.tokenize(source, work_limit~)
}