// Interpreter for `@language.LexProgram`, the portable form of the lex
// functions that upstream's `render.rs` emits into `parser.c`. Every
// expression below mirrors the C text the generator would have produced (see
// `add_lex_state` and `add_character_range_conditions` in render.rs and the
// lexer macros in lib/src/parser.h), including how a decode error (-1)
// lookahead compares.
///|
/// `set_contains` from lib/src/parser.h.
fn set_contains(
ranges : Array[@language.CharacterRange],
lookahead : Int32,
) -> Bool {
let len = ranges.length()
let mut index = 0
let mut size = len - index
while size > 1 {
let half_size = size / 2
let mid_index = index + half_size
let range = ranges[mid_index]
if lookahead >= range.start && lookahead <= range.end {
return true
} else if lookahead > range.end {
index = mid_index
}
size -= half_size
}
let range = ranges[index]
lookahead >= range.start && lookahead <= range.end
}
///|
fn range_condition(
condition : @language.RangeCondition,
lookahead : Int32,
eof : Bool,
) -> Bool {
if condition.is_included {
for range in condition.ranges {
let start = range.start
let end = range.end
let matched = if start == 0 {
// `(!eof && lookahead == 0)` or `(!eof && lookahead <= end)`
!eof && (if end == 0 { lookahead == 0 } else { lookahead <= end })
} else if end == start {
lookahead == start
} else if end == start + 1 {
lookahead == start || lookahead == end
} else {
start <= lookahead && lookahead <= end
}
if matched {
return true
}
}
false
} else {
for range in condition.ranges {
let start = range.start
let end = range.end
let holds = if end == start {
lookahead != start
} else if end == start + 1 {
lookahead != start && lookahead != end
} else if start != 0 {
lookahead < start || end < lookahead
} else {
lookahead > end
}
if !holds {
return false
}
}
true
}
}
///|
fn lex_condition(
program : @language.LexProgram,
condition : @language.LexCondition,
lookahead : Int32,
eof : Bool,
) -> Bool {
let has_positive = condition.large_set is Some(_) ||
condition.asserted is Some(_)
let positive = if has_positive {
let large = match condition.large_set {
Some((index, check_eof)) =>
(!check_eof || !eof) &&
set_contains(program.large_character_sets[index], lookahead)
None => false
}
large ||
(match condition.asserted {
Some(asserted) => range_condition(asserted, lookahead, eof)
None => false
})
} else {
true
}
let negative = match condition.negated {
Some(negated) => range_condition(negated, lookahead, eof)
None => true
}
positive && negative
}
///|
/// Run a generated lex function (`ts_lex`/`ts_lex_keywords`) starting at
/// `state`, exactly as the emitted C would.
pub fn run_lex_program(
program : @language.LexProgram,
lexer : Lexer,
start_state : Int32,
) -> Bool {
// START_LEXER()
let mut result = false
let mut skip = false
let mut state = start_state
let mut first = true
for ;; {
if !first {
// next_state:
lexer.advance(skip)
}
first = false
// start:
skip = false
let lookahead = lexer.lookahead
let eof = lexer.eof()
guard program.states.get(state) is Some(code) else {
// default: return false;
return false
}
if code.accept_token is Some(symbol) {
// ACCEPT_TOKEN(symbol)
result = true
lexer.result_symbol = symbol
lexer.mark_end()
}
if code.eof_advance is Some(next) && eof {
state = next
continue
}
let mut advanced = false
for entry in code.advance_map {
if entry.0 == lookahead {
state = entry.1
advanced = true
break
}
}
if advanced {
continue
}
for transition in code.transitions {
if lex_condition(program, transition.condition, lookahead, eof) {
if transition.skip {
skip = true
}
state = transition.state
advanced = true
break
}
}
if advanced {
continue
}
// END_STATE()
return result
}
}
///|
/// `run_lex_program` over a `LexProgram` flattened into integer arrays, so
/// that lexing a character touches no boxed values. `compile` and `run`
/// together are equivalent to `run_lex_program`; the parser compiles each lex
/// function once per language.
priv struct CompiledLexProgram {
/// Indexed by state: whether `ACCEPT_TOKEN` is emitted, and its symbol.
has_accept : FixedArray[Bool]
accept : FixedArray[Int]
/// Indexed by state: whether `if (eof) ADVANCE(s)` is emitted, and `s`.
has_eof_advance : FixedArray[Bool]
eof_advance : FixedArray[Int]
/// `advance_map` pairs of state `s` are
/// `map[2 * map_start[s]:2 * map_start[s + 1]]`, as `(char, state)`.
map_start : FixedArray[Int]
map : FixedArray[Int]
/// Transitions of state `s` are `trans_start[s].. Bool {
let valid_state = (state : Int) => state >= 0 && state < 0x20000000
for code in program.states {
if code.eof_advance is Some(next) && !valid_state(next) {
return false
}
for entry in code.advance_map {
if !valid_state(entry.1) {
return false
}
}
for transition in code.transitions {
if !valid_state(transition.state) {
return false
}
if transition.condition.large_set is Some((index, _)) &&
(index < 0 || index >= program.large_character_sets.length()) {
return false
}
}
}
true
}
///|
fn CompiledLexProgram::compile(
program : @language.LexProgram,
) -> CompiledLexProgram? {
if !compilable(program) {
return None
}
let states = program.states
let n = states.length()
let has_accept = FixedArray::make(n, false)
let accept = FixedArray::make(n, 0)
let has_eof_advance = FixedArray::make(n, false)
let eof_advance = FixedArray::make(n, 0)
let map_start = FixedArray::make(n + 1, 0)
let map : Array[Int] = []
let trans_start = FixedArray::make(n + 1, 0)
let trans : Array[Int] = []
let rc_start : Array[Int] = [0]
let rc_included : Array[Bool] = []
let rc_ranges : Array[Int] = []
let add_range_condition = (condition : @language.RangeCondition?) => {
match condition {
Some(condition) => {
for range in condition.ranges {
rc_ranges.push(range.start)
rc_ranges.push(range.end)
}
rc_included.push(condition.is_included)
rc_start.push(rc_ranges.length() / 2)
rc_included.length() - 1
}
None => -1
}
}
for s, code in states {
if code.accept_token is Some(symbol) {
has_accept[s] = true
accept[s] = symbol
}
if code.eof_advance is Some(next) {
has_eof_advance[s] = true
eof_advance[s] = next
}
map_start[s] = map.length() / 2
for entry in code.advance_map {
map.push(entry.0)
map.push(entry.1)
}
trans_start[s] = trans.length() / transition_width
for transition in code.transitions {
let condition = transition.condition
trans.push(transition.state)
trans.push(if transition.skip { 1 } else { 0 })
match condition.large_set {
Some((index, check_eof)) => {
trans.push(index)
trans.push(if check_eof { 1 } else { 0 })
}
None => {
trans.push(-1)
trans.push(0)
}
}
trans.push(add_range_condition(condition.asserted))
trans.push(add_range_condition(condition.negated))
}
}
map_start[n] = map.length() / 2
trans_start[n] = trans.length() / transition_width
let set_start : Array[Int] = [0]
let set_ranges : Array[Int] = []
for set in program.large_character_sets {
for range in set {
set_ranges.push(range.start)
set_ranges.push(range.end)
}
set_start.push(set_ranges.length() / 2)
}
Some({
has_accept,
accept,
has_eof_advance,
eof_advance,
map_start,
map: FixedArray::from_array(map),
trans_start,
trans: FixedArray::from_array(trans),
rc_start: FixedArray::from_array(rc_start),
rc_included: FixedArray::from_array(rc_included),
rc_ranges: FixedArray::from_array(rc_ranges),
set_start: FixedArray::from_array(set_start),
set_ranges: FixedArray::from_array(set_ranges),
ascii: FixedArray::make(n * 128, ascii_unknown),
})
}
///|
/// The `ADVANCE_MAP` and transition outcome of `state` for `lookahead`, as
/// encoded in `ascii`.
fn CompiledLexProgram::advance_outcome(
self : CompiledLexProgram,
state : Int,
lookahead : Int32,
eof : Bool,
) -> Int {
let map = self.map
for k in self.map_start[state].. Unit {
for c in 0..<128 {
self.ascii[state * 128 + c] = self.advance_outcome(state, c, false)
}
}
///|
/// `set_contains` over large character set `set`.
fn CompiledLexProgram::set_contains(
self : CompiledLexProgram,
set : Int,
lookahead : Int32,
) -> Bool {
let ranges = self.set_ranges
let base = self.set_start[set]
let len = self.set_start[set + 1] - base
let mut index = 0
let mut size = len - index
while size > 1 {
let half_size = size / 2
let mid_index = index + half_size
let start = ranges[2 * (base + mid_index)]
let end = ranges[2 * (base + mid_index) + 1]
if lookahead >= start && lookahead <= end {
return true
} else if lookahead > end {
index = mid_index
}
size -= half_size
}
let start = ranges[2 * (base + index)]
let end = ranges[2 * (base + index) + 1]
lookahead >= start && lookahead <= end
}
///|
/// `range_condition` for range condition `c`.
fn CompiledLexProgram::range_condition(
self : CompiledLexProgram,
c : Int,
lookahead : Int32,
eof : Bool,
) -> Bool {
let ranges = self.rc_ranges
let first = self.rc_start[c]
let last = self.rc_start[c + 1]
if self.rc_included[c] {
for k in first.. end
}
if !holds {
return false
}
}
true
}
}
///|
/// `lex_condition` for the transition starting at `trans[t]`.
fn CompiledLexProgram::lex_condition(
self : CompiledLexProgram,
t : Int,
lookahead : Int32,
eof : Bool,
) -> Bool {
let trans = self.trans
let large_set = trans[t + 2]
let asserted = trans[t + 4]
let negated = trans[t + 5]
let positive = if large_set >= 0 || asserted >= 0 {
let large = large_set >= 0 &&
(trans[t + 3] == 0 || !eof) &&
self.set_contains(large_set, lookahead)
large || (asserted >= 0 && self.range_condition(asserted, lookahead, eof))
} else {
true
}
positive && (negated < 0 || self.range_condition(negated, lookahead, eof))
}
///|
/// `run_lex_program` for a compiled program.
fn CompiledLexProgram::run(
self : CompiledLexProgram,
lexer : Lexer,
start_state : Int32,
) -> Bool {
// START_LEXER()
let mut result = false
let mut skip = false
let mut state = start_state
let mut first = true
let state_count = self.has_accept.length()
let ascii = self.ascii
for ;; {
if !first {
// next_state:
lexer.advance(skip)
}
first = false
// start:
skip = false
let lookahead = lexer.lookahead
let eof = lexer.eof()
if state < 0 || state >= state_count {
// default: return false;
return false
}
if self.has_accept[state] {
// ACCEPT_TOKEN(symbol)
result = true
lexer.result_symbol = self.accept[state]
lexer.mark_end()
}
if eof && self.has_eof_advance[state] {
state = self.eof_advance[state]
continue
}
// ADVANCE_MAP and the transitions, in order.
let outcome = if !eof && lookahead >= 0 && lookahead < 128 {
let index = state * 128 + lookahead
if ascii[index] == ascii_unknown {
self.fill_ascii(state)
}
ascii[index]
} else {
self.advance_outcome(state, lookahead, eof)
}
if outcome == ascii_end {
// END_STATE()
return result
}
if (outcome & 1) != 0 {
skip = true
}
state = outcome >> 1
}
}