use std::collections::HashMap;
use std::fmt;
use std::fmt::Formatter;
use crate::atn::ATN;
use crate::int_stream::EOF;
use crate::lexer_action::{LexerAction, LEXER_ACTION_TYPE_CUSTOM};
pub const STATIC_DFA_MAGIC: u32 = 0x5344_4641;
pub const STATIC_DFA_FORMAT_VERSION: u32 = 1;
pub const NO_EDGE: u16 = 0xFFFF;
pub const ESCAPE: u16 = 0xFFFE;
pub const ACCEPT_BIT: u16 = 0x8000;
pub const STATE_MASK: u16 = 0x7FFF;
pub const NO_CONTINUATION: u32 = u32::MAX;
pub const CONTINUATION_MOVED_CONFIGS: u32 = 0;
pub const CONTINUATION_SOURCE_SET: u32 = 1;
pub const ACCEL_POSITIVE: u32 = 1;
pub const ACCEL_EXCLUSION: u32 = 2;
pub const ACCEL_COUNTED_EXCLUSION: u32 = 3;
pub const BEHIND_POSITION_INDEPENDENT: u32 = 0xFFFF;
pub(crate) const ASCII_ROW: usize = 128;
pub(crate) const LOW_ROW: usize = ASCII_ROW + 1;
const MAX_SYMBOL: u32 = 0x10FFFF;
const MAX_STATE_COUNT: usize = 0x7FFE;
#[derive(Debug)]
#[cfg_attr(feature = "static-dfa-build", derive(PartialEq))]
pub struct StaticLexerTables {
pub(crate) modes: Vec<Option<StaticLexerDFA>>,
}
#[derive(Debug)]
#[cfg_attr(feature = "static-dfa-build", derive(PartialEq))]
pub struct StaticLexerDFA {
pub(crate) start_state: u16,
pub(crate) low: Vec<u16>,
pub(crate) class_of: Vec<u16>,
pub(crate) hi_rows: Vec<u16>,
pub(crate) row_of: Vec<u32>,
pub(crate) num_classes: usize,
pub(crate) class_starts: Vec<u32>,
pub(crate) accept_type: Vec<i32>,
pub(crate) accept_actions: Vec<(u32, u32)>,
pub(crate) actions: Vec<LexerAction<'static>>,
pub(crate) accel_tag: Vec<u8>,
pub(crate) accel_data: Vec<Accel>,
pub(crate) eof_escape: Vec<u32>,
pub(crate) escape_off: Vec<u32>,
pub(crate) escape_ranges: Vec<EscapeRange>,
pub(crate) continuations: Vec<LexerContinuation>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct EscapeRange {
pub(crate) lo: i32,
pub(crate) hi: i32,
pub(crate) continuation: u32,
}
#[derive(Debug, PartialEq, Eq)]
pub(crate) struct LexerContinuation {
pub(crate) kind: u32,
pub(crate) ctxs: Vec<(u32, i32)>,
pub(crate) configs: Vec<ContinuationConfig>,
}
#[derive(Debug, PartialEq, Eq)]
pub(crate) struct ContinuationConfig {
pub(crate) state: i32,
pub(crate) alt: i32,
pub(crate) ctx: u32,
pub(crate) non_greedy: bool,
pub(crate) alt_reached_accept: bool,
pub(crate) actions: Vec<u32>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Accel {
Positive(u128),
Exclude(u8),
Exclude2(u8, u8),
Exclude3(u8, u8, u8),
CountedExclusion {
opener: [u8; 3],
closer: [u8; 3],
n: u8,
},
}
impl Accel {
#[cfg(feature = "static-dfa-build")]
pub(crate) fn to_serialized(self, s: u16) -> Vec<u32> {
match self {
Accel::Positive(bitmap) => {
vec![
u32::from(s),
ACCEL_POSITIVE,
bitmap as u32,
(bitmap >> 32) as u32,
(bitmap >> 64) as u32,
(bitmap >> 96) as u32,
]
}
Accel::Exclude(n0) => {
vec![u32::from(s), ACCEL_EXCLUSION, 1, u32::from(n0), 0, 0]
}
Accel::Exclude2(n0, n1) => {
vec![
u32::from(s),
ACCEL_EXCLUSION,
2,
u32::from(n0),
u32::from(n1),
0,
]
}
Accel::Exclude3(n0, n1, n2) => {
vec![
u32::from(s),
ACCEL_EXCLUSION,
3,
u32::from(n0),
u32::from(n1),
u32::from(n2),
]
}
Accel::CountedExclusion { opener, closer, n } => {
vec![
u32::from(s),
ACCEL_COUNTED_EXCLUSION,
u32::from(n),
u32::from_le_bytes([opener[0], opener[1], opener[2], 0]),
u32::from_le_bytes([closer[0], closer[1], closer[2], 0]),
0,
]
}
}
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum StaticLexerError {
BadMagic {
found: u32,
},
TotalLengthMismatch {
declared: usize,
actual: usize,
},
TruncatedStream {
expected_at_least: usize,
actual: usize,
},
TrailingWords {
consumed: usize,
actual: usize,
},
InvalidModeFlag {
mode: usize,
value: u32,
},
InvalidStateCount {
mode: usize,
count: usize,
},
IndexOutOfBounds {
mode: usize,
what: &'static str,
index: u32,
count: usize,
},
InvalidEdgeTarget {
mode: usize,
entry: u32,
},
InconsistentAcceptBit {
mode: usize,
entry: u16,
},
InvalidAcceptType {
mode: usize,
state: usize,
value: i32,
},
InvalidClassStarts {
mode: usize,
},
InvalidRowOffsets {
mode: usize,
},
InvalidClassRange {
mode: usize,
row: usize,
},
InvalidActionList {
mode: usize,
state: usize,
},
InvalidActionType {
mode: usize,
state: usize,
value: i32,
},
SectionLengthMismatch {
mode: usize,
section: &'static str,
expected: usize,
found: usize,
},
InvalidAccelTag {
mode: usize,
value: u32,
},
InvalidAccelNeedles {
mode: usize,
},
InvalidEscapeRow {
mode: usize,
state: usize,
},
InconsistentEscapeRow {
mode: usize,
state: usize,
symbol: i32,
},
UnknownContinuationKind {
mode: usize,
index: usize,
kind: u32,
},
InvalidContextKind {
mode: usize,
index: usize,
value: u32,
},
NonTopologicalContext {
mode: usize,
index: usize,
},
InvalidContinuationConfig {
mode: usize,
index: usize,
},
InvalidBehind {
mode: usize,
index: usize,
value: u32,
},
}
impl fmt::Display for StaticLexerError {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
match self {
StaticLexerError::BadMagic { found } => {
write!(
f,
"bad magic 0x{found:08x}; expected 0x{STATIC_DFA_MAGIC:08x}"
)
}
StaticLexerError::TotalLengthMismatch { declared, actual } => {
write!(
f,
"declared total length {declared} does not match stream length {actual}"
)
}
StaticLexerError::TruncatedStream {
expected_at_least,
actual,
} => {
write!(
f,
"stream has {actual} words; expected at least {expected_at_least}"
)
}
StaticLexerError::TrailingWords { consumed, actual } => {
write!(
f,
"mode sections consumed {consumed} words of the declared {actual}"
)
}
StaticLexerError::InvalidModeFlag { mode, value } => {
write!(f, "mode {mode} present flag is {value}; expected 0 or 1")
}
StaticLexerError::InvalidStateCount { mode, count } => {
write!(
f,
"mode {mode} has {count} states; expected 1..={MAX_STATE_COUNT}"
)
}
StaticLexerError::IndexOutOfBounds {
mode,
what,
index,
count,
} => {
write!(f, "mode {mode}: {what} index {index} outside 0..{count}")
}
StaticLexerError::InvalidEdgeTarget { mode, entry } => {
write!(f, "mode {mode}: invalid edge entry 0x{entry:04x}")
}
StaticLexerError::InconsistentAcceptBit { mode, entry } => {
write!(
f,
"mode {mode}: edge entry 0x{entry:04x} accept bit does not match \
the target state's accept type"
)
}
StaticLexerError::InvalidAcceptType { mode, state, value } => {
write!(
f,
"mode {mode} state {state}: accept type {value}; expected -1 or a token type"
)
}
StaticLexerError::InvalidClassStarts { mode } => {
write!(f, "mode {mode}: invalid class starts")
}
StaticLexerError::InvalidRowOffsets { mode } => {
write!(f, "mode {mode}: invalid class row offsets")
}
StaticLexerError::InvalidClassRange { mode, row } => {
write!(f, "mode {mode} hi row {row}: invalid class range")
}
StaticLexerError::InvalidActionList { mode, state } => {
write!(
f,
"mode {mode} state {state}: accept action list is not decodable"
)
}
StaticLexerError::InvalidActionType { mode, state, value } => {
write!(
f,
"mode {mode} state {state}: invalid or position-dependent action type {value}"
)
}
StaticLexerError::SectionLengthMismatch {
mode,
section,
expected,
found,
} => {
write!(
f,
"mode {mode}: {section} section declared {expected} words; read {found}"
)
}
StaticLexerError::InvalidAccelTag { mode, value } => {
write!(f, "mode {mode}: unknown accel tag {value}")
}
StaticLexerError::InvalidAccelNeedles { mode } => {
write!(f, "mode {mode}: invalid exclusion accel needles")
}
StaticLexerError::InvalidEscapeRow { mode, state } => {
write!(f, "mode {mode} state {state}: invalid escape row")
}
StaticLexerError::InconsistentEscapeRow {
mode,
state,
symbol,
} => {
write!(
f,
"mode {mode} state {state}: escape row does not match the edge entry at symbol {symbol}"
)
}
StaticLexerError::UnknownContinuationKind { mode, index, kind } => {
write!(f, "mode {mode} continuation {index}: unknown kind {kind}")
}
StaticLexerError::InvalidContextKind { mode, index, value } => {
write!(
f,
"mode {mode} continuation {index}: context kind {value}; expected 0 (singleton)"
)
}
StaticLexerError::NonTopologicalContext { mode, index } => {
write!(
f,
"mode {mode} continuation {index}: context table is not topological"
)
}
StaticLexerError::InvalidContinuationConfig { mode, index } => {
write!(f, "mode {mode} continuation {index}: invalid config")
}
StaticLexerError::InvalidBehind { mode, index, value } => {
write!(
f,
"mode {mode} continuation {index}: behind value {value}; expected {BEHIND_POSITION_INDEPENDENT}"
)
}
}
}
}
impl std::error::Error for StaticLexerError {}
impl StaticLexerTables {
pub fn from_words(words: &[u32]) -> Result<Self, StaticLexerError> {
let mut r = Reader { words, pos: 0 };
if words.len() < 4 {
return Err(StaticLexerError::TruncatedStream {
expected_at_least: 4,
actual: words.len(),
});
}
let magic = r.next()?;
if magic != STATIC_DFA_MAGIC {
return Err(StaticLexerError::BadMagic { found: magic });
}
let version = r.next()?;
assert_eq!(
version, STATIC_DFA_FORMAT_VERSION,
"static lexer DFA table format version mismatch (found {version}, expected \
{STATIC_DFA_FORMAT_VERSION}): the table was generated with a different tool \
version; regenerate the lexer tables"
);
let total = r.next()? as usize;
if total != words.len() {
return Err(StaticLexerError::TotalLengthMismatch {
declared: total,
actual: words.len(),
});
}
let num_modes = r.next()? as usize;
let mut modes = Vec::with_capacity(num_modes);
for mode in 0..num_modes {
modes.push(read_mode(&mut r, mode)?);
}
if r.pos != words.len() {
return Err(StaticLexerError::TrailingWords {
consumed: r.pos,
actual: words.len(),
});
}
Ok(StaticLexerTables { modes })
}
#[inline]
pub fn mode(&self, m: usize) -> Option<&StaticLexerDFA> {
self.modes.get(m).and_then(Option::as_ref)
}
pub fn num_modes(&self) -> usize {
self.modes.len()
}
#[cfg(feature = "static-dfa-build")]
pub(crate) fn from_modes(modes: Vec<Option<StaticLexerDFA>>) -> Self {
StaticLexerTables { modes }
}
#[cfg(feature = "static-dfa-build")]
pub(crate) fn into_modes(self) -> Vec<Option<StaticLexerDFA>> {
self.modes
}
#[cfg(feature = "static-dfa-build")]
pub fn to_words(&self) -> Vec<u32> {
let mut out = vec![
STATIC_DFA_MAGIC,
STATIC_DFA_FORMAT_VERSION,
0,
self.modes.len() as u32,
];
for mode in &self.modes {
match mode {
None => out.push(0),
Some(dfa) => {
out.push(1);
dfa.write_mode(&mut out);
}
}
}
out[2] = out.len() as u32;
out
}
pub(crate) fn validate_for_atn(&self, atn: &ATN) {
let states = atn.states_count();
let actions = atn.lexer_actions.len();
for (m, mode) in self.modes.iter().enumerate() {
let Some(mode) = mode else { continue };
for cont in &mode.continuations {
for &(_, return_state) in &cont.ctxs {
assert!(
(return_state as usize) < states,
"static lexer DFA table of mode {m} references ATN state {return_state}, \
but the ATN has {states} states; regenerate the lexer tables"
);
}
for config in &cont.configs {
assert!(
(config.state as usize) < states,
"static lexer DFA table of mode {m} references ATN state {}, \
but the ATN has {states} states; regenerate the lexer tables",
config.state
);
for &action in &config.actions {
assert!(
(action as usize) < actions,
"static lexer DFA table of mode {m} references lexer action {action}, \
but the ATN has {actions} lexer actions; regenerate the lexer tables"
);
}
}
}
}
}
}
impl StaticLexerDFA {
#[cfg(feature = "static-dfa-build")]
#[inline]
pub fn start_state(&self) -> u16 {
self.start_state
}
#[cfg(not(feature = "static-dfa-build"))]
#[inline]
pub(crate) fn start_state(&self) -> u16 {
self.start_state
}
#[cfg(feature = "static-dfa-build")]
#[inline]
pub fn edge_entry(&self, s: u16, t: i32) -> u16 {
let col = (t as u32).wrapping_add(1) as usize;
if col < LOW_ROW {
return unsafe { *self.low.get_unchecked(s as usize * LOW_ROW + col) };
}
let i = t as usize - ASCII_ROW;
if i >= self.class_of.len() {
return NO_EDGE;
}
unsafe {
let class = *self.class_of.get_unchecked(i) as usize;
let row = *self.row_of.get_unchecked(s as usize) as usize;
*self.hi_rows.get_unchecked(row * self.num_classes + class)
}
}
#[cfg(not(feature = "static-dfa-build"))]
#[inline]
pub(crate) fn edge_entry(&self, s: u16, t: i32) -> u16 {
let col = (t as u32).wrapping_add(1) as usize;
if col < LOW_ROW {
return unsafe { *self.low.get_unchecked(s as usize * LOW_ROW + col) };
}
let i = t as usize - ASCII_ROW;
if i >= self.class_of.len() {
return NO_EDGE;
}
unsafe {
let class = *self.class_of.get_unchecked(i) as usize;
let row = *self.row_of.get_unchecked(s as usize) as usize;
*self.hi_rows.get_unchecked(row * self.num_classes + class)
}
}
#[cfg(feature = "static-dfa-build")]
#[inline]
pub fn accept_type(&self, s: u16) -> i32 {
unsafe { *self.accept_type.get_unchecked(s as usize) }
}
#[cfg(not(feature = "static-dfa-build"))]
#[inline]
pub(crate) fn accept_type(&self, s: u16) -> i32 {
unsafe { *self.accept_type.get_unchecked(s as usize) }
}
#[inline]
pub(crate) fn accept_actions(&self, s: u16) -> &[LexerAction<'static>] {
let (off, len) = unsafe { *self.accept_actions.get_unchecked(s as usize) };
&self.actions[off as usize..(off + len) as usize]
}
#[inline]
pub(crate) fn accel_tag(&self, s: u16) -> u8 {
unsafe { *self.accel_tag.get_unchecked(s as usize) }
}
#[inline]
pub(crate) fn accel_payload(&self, tag: u8) -> Accel {
unsafe { *self.accel_data.get_unchecked(tag as usize - 1) }
}
#[cfg(feature = "static-dfa-build")]
pub fn escape_continuation(&self, s: u16, symbol: i32) -> u32 {
if symbol == EOF {
return unsafe { *self.eof_escape.get_unchecked(s as usize) };
}
self.escape_range(s, symbol)
.map_or(NO_CONTINUATION, |r| r.continuation)
}
#[cfg(not(feature = "static-dfa-build"))]
pub(crate) fn escape_continuation(&self, s: u16, symbol: i32) -> u32 {
if symbol == EOF {
return unsafe { *self.eof_escape.get_unchecked(s as usize) };
}
self.escape_range(s, symbol)
.map_or(NO_CONTINUATION, |r| r.continuation)
}
fn escape_range(&self, s: u16, symbol: i32) -> Option<&EscapeRange> {
let row = unsafe {
let lo = *self.escape_off.get_unchecked(s as usize) as usize;
let hi = *self.escape_off.get_unchecked(s as usize + 1) as usize;
self.escape_ranges.get_unchecked(lo..hi)
};
let found = row.binary_search_by(|r| {
if symbol < r.lo {
std::cmp::Ordering::Greater
} else if symbol > r.hi {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Equal
}
});
found.ok().map(|i| &row[i])
}
pub(crate) fn continuation(&self, index: u32) -> &LexerContinuation {
unsafe { self.continuations.get_unchecked(index as usize) }
}
}
#[cfg(feature = "static-dfa-build")]
impl StaticLexerDFA {
pub fn num_states(&self) -> usize {
self.accept_type.len()
}
pub fn num_classes(&self) -> usize {
self.num_classes
}
pub fn num_continuations(&self) -> usize {
self.continuations.len()
}
pub fn continuation_kind(&self, index: u32) -> u32 {
self.continuations[index as usize].kind
}
pub fn continuation_num_configs(&self, index: u32) -> usize {
self.continuations[index as usize].configs.len()
}
pub fn accept_action_triples(&self, s: u16) -> Vec<(i32, i32, i32)> {
self.accept_actions(s)
.iter()
.map(LexerAction::to_serialized)
.collect()
}
pub fn escape_ranges(&self, s: u16) -> Vec<(i32, i32, u32)> {
let row = &self.escape_ranges
[self.escape_off[s as usize] as usize..self.escape_off[s as usize + 1] as usize];
row.iter().map(|r| (r.lo, r.hi, r.continuation)).collect()
}
}
#[cfg(feature = "static-dfa-build")]
impl StaticLexerDFA {
fn write_mode(&self, out: &mut Vec<u32>) {
let num_states = self.accept_type.len();
out.push(num_states as u32);
out.push(u32::from(self.start_state));
out.extend(self.accept_type.iter().map(|&t| t as u32));
let mut action_lists: Vec<u32> = Vec::new();
let mut list_ids: HashMap<&[LexerAction], u32> = HashMap::new();
let mut offsets = Vec::with_capacity(num_states);
for &(off, len) in &self.accept_actions {
if len == 0 {
offsets.push(-1i32);
continue;
}
let list = &self.actions[off as usize..(off + len) as usize];
let offset = match list_ids.get(list) {
Some(&offset) => offset,
None => {
let offset = action_lists.len() as u32;
action_lists.push(len);
for action in list {
let (ty, d1, d2) = action.to_serialized();
action_lists.extend([ty as u32, d1 as u32, d2 as u32]);
}
list_ids.insert(list, offset);
offset
}
};
offsets.push(offset as i32);
}
out.extend(offsets.iter().map(|&o| o as u32));
for s in 0..num_states {
out.push(u32::from(self.low[s * LOW_ROW]));
}
for s in 0..num_states {
out.extend(
self.low[s * LOW_ROW + 1..(s + 1) * LOW_ROW]
.iter()
.map(|&entry| u32::from(entry)),
);
}
self.write_hi_classes(out);
out.push(action_lists.len() as u32);
out.extend(action_lists);
let mut accel = Vec::new();
for (s, &tag) in self.accel_tag.iter().enumerate() {
if tag != 0 {
accel.extend(self.accel_data[tag as usize - 1].to_serialized(s as u16));
}
}
out.push(accel.len() as u32);
out.extend(accel);
for s in 0..num_states {
out.push(self.eof_escape[s]);
let ranges =
&self.escape_ranges[self.escape_off[s] as usize..self.escape_off[s + 1] as usize];
out.push(ranges.len() as u32);
for range in ranges {
out.extend([range.lo as u32, range.hi as u32, range.continuation]);
}
}
out.push(self.continuations.len() as u32);
for cont in &self.continuations {
out.push(cont.kind);
out.push(cont.ctxs.len() as u32);
for &(parent, return_state) in &cont.ctxs {
out.extend([0, parent, return_state as u32]);
}
out.push(cont.configs.len() as u32);
for config in &cont.configs {
let flags =
u32::from(config.non_greedy) | (u32::from(config.alt_reached_accept) << 1);
out.extend([
config.state as u32,
flags,
config.alt as u32,
config.ctx,
config.actions.len() as u32,
]);
for &action in &config.actions {
out.extend([action, BEHIND_POSITION_INDEPENDENT]);
}
}
}
}
fn write_hi_classes(&self, out: &mut Vec<u32>) {
out.push(self.num_classes as u32);
if self.num_classes == 0 {
return;
}
out.extend(self.class_starts.iter().copied());
let num_rows = self.hi_rows.len() / self.num_classes;
let row_runs: Vec<Vec<(u32, u32, u16)>> = (0..num_rows)
.map(|row| {
dense_row_runs(&self.hi_rows[row * self.num_classes..(row + 1) * self.num_classes])
})
.collect();
out.push(num_rows as u32);
out.push(row_runs.iter().map(Vec::len).sum::<usize>() as u32);
let mut offset = 0;
for runs in &row_runs {
out.push(offset);
offset += runs.len() as u32;
}
out.push(offset);
for runs in &row_runs {
for &(lo, hi, entry) in runs {
out.extend([lo, hi, u32::from(entry)]);
}
}
out.extend(self.row_of.iter().copied());
}
}
#[cfg(feature = "static-dfa-build")]
fn dense_row_runs(dense: &[u16]) -> Vec<(u32, u32, u16)> {
let mut runs = Vec::new();
let mut c = 0;
while c < dense.len() {
let entry = dense[c];
if entry == NO_EDGE {
c += 1;
continue;
}
let start = c;
c += 1;
while c < dense.len() && dense[c] == entry {
c += 1;
}
runs.push((start as u32, (c - 1) as u32, entry));
}
runs
}
pub(crate) fn class_map(class_starts: &[u32]) -> Vec<u16> {
let mut class_of = vec![0u16; (MAX_SYMBOL - ASCII_ROW as u32 + 1) as usize];
for (c, &start) in class_starts.iter().enumerate() {
let from = (start - ASCII_ROW as u32) as usize;
let to = if c + 1 < class_starts.len() {
(class_starts[c + 1] - ASCII_ROW as u32) as usize
} else {
class_of.len()
};
class_of[from..to].fill(c as u16);
}
class_of
}
pub(crate) fn dense_hi_rows(row_runs: &[Vec<(u32, u32, u16)>], num_classes: usize) -> Vec<u16> {
let mut hi_rows = vec![NO_EDGE; row_runs.len() * num_classes];
for (row, runs) in row_runs.iter().enumerate() {
for &(lo, hi, target) in runs {
hi_rows[row * num_classes + lo as usize..=row * num_classes + hi as usize].fill(target);
}
}
hi_rows
}
struct Reader<'a> {
words: &'a [u32],
pos: usize,
}
impl Reader<'_> {
fn next(&mut self) -> Result<u32, StaticLexerError> {
let w = self
.words
.get(self.pos)
.ok_or(StaticLexerError::TruncatedStream {
expected_at_least: self.pos + 1,
actual: self.words.len(),
})?;
self.pos += 1;
Ok(*w)
}
}
fn check_index(
mode: usize,
what: &'static str,
index: u32,
count: usize,
) -> Result<(), StaticLexerError> {
if index as usize >= count {
return Err(StaticLexerError::IndexOutOfBounds {
mode,
what,
index,
count,
});
}
Ok(())
}
fn check_edge(
mode: usize,
word: u32,
num_states: usize,
accept_type: &[i32],
) -> Result<u16, StaticLexerError> {
if word > u16::MAX as u32 {
return Err(StaticLexerError::InvalidEdgeTarget { mode, entry: word });
}
let entry = word as u16;
if entry == NO_EDGE || entry == ESCAPE {
return Ok(entry);
}
let target = (entry & STATE_MASK) as usize;
if target >= num_states {
return Err(StaticLexerError::InvalidEdgeTarget { mode, entry: word });
}
if (entry & ACCEPT_BIT != 0) != (accept_type[target] >= 0) {
return Err(StaticLexerError::InconsistentAcceptBit { mode, entry });
}
Ok(entry)
}
fn read_mode(r: &mut Reader, mode: usize) -> Result<Option<StaticLexerDFA>, StaticLexerError> {
let present = r.next()?;
if present == 0 {
return Ok(None);
}
if present != 1 {
return Err(StaticLexerError::InvalidModeFlag {
mode,
value: present,
});
}
let num_states = r.next()? as usize;
if num_states == 0 || num_states > MAX_STATE_COUNT {
return Err(StaticLexerError::InvalidStateCount {
mode,
count: num_states,
});
}
let start_state = r.next()?;
check_index(mode, "start state", start_state, num_states)?;
let mut accept_type = Vec::with_capacity(num_states);
for s in 0..num_states {
let value = r.next()? as i32;
if value < -1 {
return Err(StaticLexerError::InvalidAcceptType {
mode,
state: s,
value,
});
}
accept_type.push(value);
}
let mut accept_action_offsets = Vec::with_capacity(num_states);
for _ in 0..num_states {
accept_action_offsets.push(r.next()? as i32);
}
let mut low = vec![NO_EDGE; num_states * LOW_ROW];
for s in 0..num_states {
low[s * LOW_ROW] = check_edge(mode, r.next()?, num_states, &accept_type)?;
}
for s in 0..num_states {
for c in 1..LOW_ROW {
low[s * LOW_ROW + c] = check_edge(mode, r.next()?, num_states, &accept_type)?;
}
}
let hi = read_hi_classes(r, mode, num_states, &accept_type)?;
let action_lists = read_action_lists(r, mode, &accept_action_offsets)?;
let (accel_tag, accel_data) = read_accel(r, mode, num_states)?;
let (eof_escape, escape_off, escape_ranges) = read_escape_rows(r, mode, num_states)?;
let continuations = read_continuations(r, mode)?;
let table = StaticLexerDFA {
start_state: start_state as u16,
low,
class_of: hi.class_of,
hi_rows: hi.hi_rows,
row_of: hi.row_of,
num_classes: hi.num_classes,
class_starts: hi.class_starts,
accept_type,
accept_actions: action_lists.accept_actions,
actions: action_lists.actions,
accel_tag,
accel_data,
eof_escape,
escape_off,
escape_ranges,
continuations,
};
table.validate_escapes(mode)?;
Ok(Some(table))
}
struct HiClasses {
class_of: Vec<u16>,
class_starts: Vec<u32>,
hi_rows: Vec<u16>,
row_of: Vec<u32>,
num_classes: usize,
}
struct ActionLists {
actions: Vec<LexerAction<'static>>,
accept_actions: Vec<(u32, u32)>,
}
fn read_hi_classes(
r: &mut Reader,
mode: usize,
num_states: usize,
accept_type: &[i32],
) -> Result<HiClasses, StaticLexerError> {
let num_classes = r.next()? as usize;
if num_classes == 0 {
return Ok(HiClasses {
class_of: Vec::new(),
class_starts: Vec::new(),
hi_rows: Vec::new(),
row_of: Vec::new(),
num_classes: 0,
});
}
if num_classes > u16::MAX as usize + 1 {
return Err(StaticLexerError::InvalidClassStarts { mode });
}
let mut class_starts = Vec::with_capacity(num_classes);
for _ in 0..num_classes {
class_starts.push(r.next()?);
}
if class_starts[0] != ASCII_ROW as u32
|| !class_starts.windows(2).all(|w| w[0] < w[1])
|| *class_starts.last().unwrap() > MAX_SYMBOL
{
return Err(StaticLexerError::InvalidClassStarts { mode });
}
let class_of = class_map(&class_starts);
let num_rows = r.next()? as usize;
let num_row_triples = r.next()? as usize;
let mut row_offsets = Vec::with_capacity(num_rows + 1);
for _ in 0..=num_rows {
row_offsets.push(r.next()? as usize);
}
if row_offsets[0] != 0
|| row_offsets[num_rows] != num_row_triples
|| !row_offsets.windows(2).all(|w| w[0] <= w[1])
{
return Err(StaticLexerError::InvalidRowOffsets { mode });
}
let mut row_runs = Vec::with_capacity(num_rows);
for row in 0..num_rows {
let mut runs = Vec::with_capacity(row_offsets[row + 1] - row_offsets[row]);
let mut prev_hi = None;
for _ in row_offsets[row]..row_offsets[row + 1] {
let lo = r.next()?;
let hi = r.next()?;
let target = r.next()?;
if lo > hi || hi as usize >= num_classes || prev_hi.is_some_and(|p: u32| lo <= p) {
return Err(StaticLexerError::InvalidClassRange { mode, row });
}
prev_hi = Some(hi);
runs.push((lo, hi, check_edge(mode, target, num_states, accept_type)?));
}
row_runs.push(runs);
}
let hi_rows = dense_hi_rows(&row_runs, num_classes);
let mut row_of = Vec::with_capacity(num_states);
for _ in 0..num_states {
let row = r.next()?;
check_index(mode, "hi row", row, num_rows)?;
row_of.push(row);
}
Ok(HiClasses {
class_of,
class_starts,
hi_rows,
row_of,
num_classes,
})
}
fn read_action_lists(
r: &mut Reader,
mode: usize,
accept_action_offsets: &[i32],
) -> Result<ActionLists, StaticLexerError> {
let num_ints = r.next()? as usize;
let mut words = Vec::with_capacity(num_ints);
for _ in 0..num_ints {
words.push(r.next()?);
}
let mut actions = Vec::new();
let mut list_ids: HashMap<&[u32], (u32, u32)> = HashMap::new();
let mut lists = Vec::with_capacity(accept_action_offsets.len());
for (s, &offset) in accept_action_offsets.iter().enumerate() {
if offset < 0 {
lists.push((0, 0));
continue;
}
let offset = offset as usize;
let Some(&len) = words.get(offset) else {
return Err(StaticLexerError::InvalidActionList { mode, state: s });
};
let len = len as usize;
let triples = len
.checked_mul(3)
.and_then(|n| words.get(offset + 1..offset + 1 + n))
.ok_or(StaticLexerError::InvalidActionList { mode, state: s })?;
if let Some(&list) = list_ids.get(triples) {
lists.push(list);
continue;
}
let start = actions.len() as u32;
for &[ty, d1, d2] in triples.as_chunks::<3>().0 {
let (ty, d1, d2) = (ty as i32, d1 as i32, d2 as i32);
if !(0..=7).contains(&ty) || ty == LEXER_ACTION_TYPE_CUSTOM {
return Err(StaticLexerError::InvalidActionType {
mode,
state: s,
value: ty,
});
}
actions.push(LexerAction::from_serialized(ty, d1, d2));
}
let list = (start, len as u32);
list_ids.insert(triples, list);
lists.push(list);
}
Ok(ActionLists {
actions,
accept_actions: lists,
})
}
fn read_accel(
r: &mut Reader,
mode: usize,
num_states: usize,
) -> Result<(Vec<u8>, Vec<Accel>), StaticLexerError> {
let num_ints = r.next()? as usize;
let mut accel_tag = vec![0u8; num_states];
let mut accel_data = Vec::new();
let mut read = 0;
while read < num_ints {
let s = r.next()?;
check_index(mode, "accel state", s, num_states)?;
let payload = match r.next()? {
ACCEL_POSITIVE => {
let mut bitmap = 0u128;
for limb in 0..4 {
bitmap |= (r.next()? as u128) << (limb * 32);
}
read += 6;
Accel::Positive(bitmap)
}
ACCEL_EXCLUSION => {
let n = r.next()?;
let mut needle_words = [0; 3];
for slot in needle_words.iter_mut() {
*slot = r.next()?;
}
if !(1..=3).contains(&n) || needle_words[..n as usize].iter().any(|&w| w >= 0x80) {
return Err(StaticLexerError::InvalidAccelNeedles { mode });
}
read += 6;
match n {
1 => Accel::Exclude(needle_words[0] as u8),
2 => Accel::Exclude2(needle_words[0] as u8, needle_words[1] as u8),
3 => Accel::Exclude3(
needle_words[0] as u8,
needle_words[1] as u8,
needle_words[2] as u8,
),
_ => unreachable!(),
}
}
ACCEL_COUNTED_EXCLUSION => {
let n = r.next()?;
let opener_word = r.next()?;
let closer_word = r.next()?;
let reserved = r.next()?;
let opener_bytes = opener_word.to_le_bytes();
let closer_bytes = closer_word.to_le_bytes();
if !(1..=3).contains(&n)
|| reserved != 0
|| opener_word == closer_word
|| opener_bytes[..n as usize].iter().any(|&b| b >= 0x80)
|| closer_bytes[..n as usize].iter().any(|&b| b >= 0x80)
|| opener_bytes[n as usize..].iter().any(|&b| b != 0)
|| closer_bytes[n as usize..].iter().any(|&b| b != 0)
{
return Err(StaticLexerError::InvalidAccelNeedles { mode });
}
read += 6;
Accel::CountedExclusion {
opener: [opener_bytes[0], opener_bytes[1], opener_bytes[2]],
closer: [closer_bytes[0], closer_bytes[1], closer_bytes[2]],
n: n as u8,
}
}
value => {
return Err(StaticLexerError::InvalidAccelTag { mode, value });
}
};
accel_data.push(payload);
check_index(
mode,
"accel payload",
accel_data.len() as u32,
u8::MAX as usize + 1,
)?;
accel_tag[s as usize] = accel_data.len() as u8;
}
if read != num_ints {
return Err(StaticLexerError::SectionLengthMismatch {
mode,
section: "accel",
expected: num_ints,
found: read,
});
}
Ok((accel_tag, accel_data))
}
#[allow(clippy::type_complexity)]
fn read_escape_rows(
r: &mut Reader,
mode: usize,
num_states: usize,
) -> Result<(Vec<u32>, Vec<u32>, Vec<EscapeRange>), StaticLexerError> {
let mut eof_escape = Vec::with_capacity(num_states);
let mut escape_off = Vec::with_capacity(num_states + 1);
let mut escape_ranges = Vec::new();
escape_off.push(0u32);
for s in 0..num_states {
eof_escape.push(r.next()?);
let num_ranges = r.next()? as usize;
let mut prev_hi: i32 = -1;
for _ in 0..num_ranges {
let lo = r.next()? as i32;
let hi = r.next()? as i32;
let continuation = r.next()?;
if lo < 0 || lo > hi || hi > MAX_SYMBOL as i32 || lo <= prev_hi {
return Err(StaticLexerError::InvalidEscapeRow { mode, state: s });
}
prev_hi = hi;
escape_ranges.push(EscapeRange {
lo,
hi,
continuation,
});
}
escape_off.push(escape_ranges.len() as u32);
}
Ok((eof_escape, escape_off, escape_ranges))
}
fn read_continuations(
r: &mut Reader,
mode: usize,
) -> Result<Vec<LexerContinuation>, StaticLexerError> {
let num_continuations = r.next()? as usize;
let mut continuations = Vec::with_capacity(num_continuations);
for index in 0..num_continuations {
let kind = r.next()?;
if kind != CONTINUATION_MOVED_CONFIGS && kind != CONTINUATION_SOURCE_SET {
return Err(StaticLexerError::UnknownContinuationKind { mode, index, kind });
}
let nctx = r.next()? as usize;
let mut ctxs = Vec::with_capacity(nctx);
for i in 0..nctx {
let ctx_kind = r.next()?;
if ctx_kind != 0 {
return Err(StaticLexerError::InvalidContextKind {
mode,
index,
value: ctx_kind,
});
}
let parent = r.next()?;
if parent as usize > i {
return Err(StaticLexerError::NonTopologicalContext { mode, index });
}
let return_state = r.next()?;
if return_state > i32::MAX as u32 {
return Err(StaticLexerError::NonTopologicalContext { mode, index });
}
ctxs.push((parent, return_state as i32));
}
let nconfigs = r.next()? as usize;
let mut configs = Vec::with_capacity(nconfigs);
for _ in 0..nconfigs {
let state = r.next()?;
let flags = r.next()?;
let alt = r.next()?;
let ctx_local = r.next()?;
if state > i32::MAX as u32
|| flags & !0b11 != 0
|| alt == 0
|| alt > i32::MAX as u32
|| ctx_local as usize > nctx
{
return Err(StaticLexerError::InvalidContinuationConfig { mode, index });
}
let nactions = r.next()? as usize;
let mut actions = Vec::with_capacity(nactions);
for _ in 0..nactions {
let action = r.next()?;
if action > i32::MAX as u32 {
return Err(StaticLexerError::InvalidContinuationConfig { mode, index });
}
let behind = r.next()?;
if behind != BEHIND_POSITION_INDEPENDENT {
return Err(StaticLexerError::InvalidBehind {
mode,
index,
value: behind,
});
}
actions.push(action);
}
configs.push(ContinuationConfig {
state: state as i32,
alt: alt as i32,
ctx: ctx_local,
non_greedy: flags & 1 != 0,
alt_reached_accept: flags & 2 != 0,
actions,
});
}
continuations.push(LexerContinuation {
kind,
ctxs,
configs,
});
}
Ok(continuations)
}
impl StaticLexerDFA {
fn validate_escapes(&self, mode: usize) -> Result<(), StaticLexerError> {
let num_states = self.accept_type.len();
let num_continuations = self.continuations.len();
let check_continuation = |index: u32| {
if index != NO_CONTINUATION {
check_index(mode, "continuation", index, num_continuations)?;
}
Ok(())
};
for (s, &eof_escape) in self.eof_escape.iter().enumerate() {
check_continuation(eof_escape)?;
if eof_escape != NO_CONTINUATION && self.edge_entry(s as u16, EOF) != ESCAPE {
return Err(StaticLexerError::InconsistentEscapeRow {
mode,
state: s,
symbol: EOF,
});
}
}
for range in &self.escape_ranges {
check_continuation(range.continuation)?;
}
for s in 0..num_states {
let lo = self.escape_off[s] as usize;
let hi = self.escape_off[s + 1] as usize;
for range in &self.escape_ranges[lo..hi] {
for bound in [range.lo, range.hi] {
if self.edge_entry(s as u16, bound) != ESCAPE {
return Err(StaticLexerError::InconsistentEscapeRow {
mode,
state: s,
symbol: bound,
});
}
}
}
for col in 1..LOW_ROW {
let symbol = col as i32 - 1;
if self.low[s * LOW_ROW + col] == ESCAPE
&& self.escape_range(s as u16, symbol).is_none()
{
return Err(StaticLexerError::InconsistentEscapeRow {
mode,
state: s,
symbol,
});
}
}
if self.num_classes > 0 {
let row = self.row_of[s] as usize;
for (class, &start) in self.class_starts.iter().enumerate() {
if self.hi_rows[row * self.num_classes + class] == ESCAPE
&& self.escape_range(s as u16, start as i32).is_none()
{
return Err(StaticLexerError::InconsistentEscapeRow {
mode,
state: s,
symbol: start as i32,
});
}
}
}
}
Ok(())
}
}
#[cfg(all(test, feature = "static-dfa-build"))]
mod tests {
use std::path::{Path, PathBuf};
use super::*;
use crate::atn_deserializer::ATNDeserializer;
use crate::dfa::static_dfa_build::StaticLexerDfaBuilder;
fn fixture(name: &str) -> PathBuf {
Path::new(env!("CARGO_MANIFEST_DIR"))
.join("tests/static_lexer")
.join(name)
}
fn gen_grammar(name: &str) -> PathBuf {
Path::new(env!("CARGO_MANIFEST_DIR"))
.join("grammars")
.join(name)
}
fn compile_tables(path: &Path) -> ATN {
let units = dbt_antlr_codegen::atn_export::compile_atn_data(path, &[]).expect("compile");
let words = units
.iter()
.find_map(|u| u.lexer_atn_words.clone())
.expect("lexer unit");
ATNDeserializer::new(None).deserialize(&mut words.iter())
}
#[test]
fn word_stream_round_trip() {
let mut grammars: Vec<PathBuf> = [
"CSV.g4",
"CustomAction.g4",
"EofChain.g4",
"EofEscape.g4",
"EofLexer.g4",
"MiniModes.g4",
"Spike.g4",
"StartAction.g4",
"StartPred.g4",
"StartRecurse.g4",
"XMLLexer.g4",
]
.into_iter()
.map(fixture)
.collect();
grammars.extend(
["CSV.g4", "XMLLexer.g4", "SpikeLexer.g4"]
.into_iter()
.map(gen_grammar),
);
for path in grammars {
let atn = compile_tables(&path);
for builder in [
StaticLexerDfaBuilder::new(),
StaticLexerDfaBuilder::new().with_max_states_per_mode(3),
] {
let build = builder.build(&atn);
let name = path.display();
let decoded = StaticLexerTables::from_words(&build.words)
.unwrap_or_else(|e| panic!("{name}: the builder's words decode: {e}"));
assert_eq!(decoded.num_modes(), build.modes.len(), "{name}: mode count");
for m in 0..build.modes.len() {
assert_eq!(
decoded.mode(m),
build.table(m),
"{name}: from_words(to_words(tables)) == tables (mode {m})"
);
}
assert_eq!(
decoded.to_words(),
build.words,
"{name}: to_words(from_words(words)) == words"
);
}
}
}
#[test]
fn commit_and_decode_agree() {
for name in ["Spike.g4", "XMLLexer.g4", "EofEscape.g4"] {
let atn = compile_tables(&fixture(name));
let build = StaticLexerDfaBuilder::new().build(&atn);
let decoded = StaticLexerTables::from_words(&build.words).expect("decode");
for m in 0..build.modes.len() {
let (Some(committed), Some(decoded)) = (build.table(m), decoded.mode(m)) else {
continue;
};
for s in 0..committed.num_states() as u16 {
for symbol in [EOF, 0, b'a' as i32, 127, 128, 0x1000, 0x10FFFF] {
assert_eq!(
committed.edge_entry(s, symbol),
decoded.edge_entry(s, symbol),
"{name} mode {m} state {s} symbol {symbol}"
);
assert_eq!(
committed.escape_continuation(s, symbol),
decoded.escape_continuation(s, symbol),
"{name} mode {m} state {s} symbol {symbol}"
);
}
assert_eq!(committed.accept_type(s), decoded.accept_type(s));
assert_eq!(
committed.accept_action_triples(s),
decoded.accept_action_triples(s)
);
}
}
}
}
}