use std::collections::HashMap;
use std::fmt::{self, Debug, Display, Formatter};
pub const STATIC_PARSER_DFA_MAGIC: u32 = 0x5344_4641;
pub const FORMAT_VERSION: u32 = 2;
pub const ESCAPE: i32 = -1;
pub const CONFLICT_ESCAPE: i32 = -2;
pub const GUARDED: i32 = -3;
pub const VIRTUAL_ALT_BASE: i32 = 65_536;
pub(crate) const EMPTY_CONTEXT: u32 = u32::MAX;
const MAX_DENSE_PRECEDENCE: i32 = 1024;
fn checked_count(
count: usize,
words_per_record: usize,
remaining: usize,
) -> Result<usize, StaticParserDfaError> {
if count.saturating_mul(words_per_record) > remaining {
return Err(StaticParserDfaError::TruncatedStream);
}
Ok(count)
}
const PACKED_ATN_TOTAL_LEN: usize = 25;
const MAX_TABLE_STATES: usize = 1 << 16;
const MAX_TABLE_ROWS: usize = 1 << 16;
const MAX_TABLE_COLUMNS: usize = 1 << 16;
const MAX_TABLE_CELLS: usize = 1 << 24;
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum StaticParserDfaError {
TruncatedStream,
BadMagic {
found: u32,
},
UnsupportedVersion {
found: u32,
},
LengthMismatch {
declared: usize,
actual: usize,
},
DuplicateGuard {
state: usize,
},
InvalidGuardState {
state: i32,
},
InvalidRowIndex {
row: i32,
num_rows: usize,
},
InvalidEdgeOffsets,
InvalidEdgeBounds {
lo: i32,
hi: i32,
edge_width: usize,
},
InvalidEdgeTarget {
target: i32,
num_states: usize,
},
InvalidStateIndex {
state: usize,
num_states: usize,
},
InvalidDecision {
decision: usize,
num_slots: usize,
},
InvalidDispatchTable {
table_index: i32,
num_tables: usize,
},
UnsortedCutoffs,
DuplicateDispatch {
decision: usize,
},
InvalidContinuationContext {
index: u32,
decoded: usize,
},
EmptyContinuationContext {
index: usize,
},
DuplicateContinuation {
state: u32,
},
InvalidConflictAlt {
alt: i32,
},
InvalidContinuationConfig {
state: i32,
alt: i32,
outer_depth: i32,
},
InvalidReturnState {
return_state: i32,
},
OutsideAtn {
what: &'static str,
index: i64,
count: usize,
},
InvalidTableSize {
num_states: usize,
num_rows: usize,
edge_width: usize,
},
}
impl Display for StaticParserDfaError {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
match self {
Self::TruncatedStream => f.write_str("truncated static parser DFA stream"),
Self::BadMagic { found } => write!(f, "bad static parser DFA magic 0x{found:08x}"),
Self::UnsupportedVersion { found } => {
write!(f, "unsupported static parser DFA format version {found}")
}
Self::LengthMismatch { declared, actual } => write!(
f,
"static parser DFA section declares {declared} words but holds {actual}"
),
Self::InvalidRowIndex { row, num_rows } => {
write!(f, "row index {row} out of bounds for {num_rows} rows")
}
Self::InvalidEdgeOffsets => f.write_str("invalid state row edge offsets"),
Self::DuplicateGuard { state } => {
write!(f, "state {state} carries two guarded alternatives")
}
Self::InvalidGuardState { state } => {
write!(f, "guard set names a negative invoking state {state}")
}
Self::InvalidEdgeBounds {
lo,
hi,
edge_width,
} => write!(
f,
"edge token range {lo}..={hi} out of bounds for width {edge_width}"
),
Self::InvalidEdgeTarget {
target,
num_states,
} => write!(
f,
"edge target {target} out of bounds for {num_states} states"
),
Self::InvalidStateIndex { state, num_states } => {
write!(f, "state index {state} out of bounds for {num_states} states")
}
Self::InvalidDecision {
decision,
num_slots,
} => write!(
f,
"decision {decision} out of bounds for {num_slots} decision slots"
),
Self::InvalidDispatchTable {
table_index,
num_tables,
} => write!(
f,
"precedence class table {table_index} out of bounds for {num_tables} tables"
),
Self::UnsortedCutoffs => {
f.write_str("precedence dispatch cutoffs are not strictly ascending")
}
Self::DuplicateDispatch { decision } => {
write!(f, "decision {decision} carries two precedence dispatches")
}
Self::InvalidContinuationContext { index, decoded } => write!(
f,
"continuation context parent {index} is not one of the {decoded} preceding nodes"
),
Self::EmptyContinuationContext { index } => {
write!(f, "continuation context node {index} has no parents")
}
Self::DuplicateContinuation { state } => {
write!(f, "two continuations are registered for state {state}")
}
Self::InvalidConflictAlt { alt } => {
write!(f, "conflict escape alternative {alt}; expected a positive alt")
}
Self::InvalidContinuationConfig {
state,
alt,
outer_depth,
} => write!(
f,
"continuation config (state {state}, alt {alt}, outer depth {outer_depth}) is out of range"
),
Self::InvalidReturnState { return_state } => {
write!(f, "continuation return state {return_state}; expected -1 or a state number")
}
Self::OutsideAtn { what, index, count } => {
write!(f, "{what} {index} out of bounds for {count} ATN entries")
}
Self::InvalidTableSize {
num_states,
num_rows,
edge_width,
} => write!(
f,
"invalid static parser DFA table shape: {num_states} states, {num_rows} rows, {edge_width} columns"
),
}
}
}
impl std::error::Error for StaticParserDfaError {}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum ContinuationContextNode {
Singleton {
parent: u32,
return_state: i32,
},
Array {
parents: Vec<u32>,
return_states: Vec<i32>,
},
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ContinuationConfigEntry {
pub state: i32,
pub alt: i32,
pub context: u32,
pub outer_depth: i32,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ParserContinuation {
pub state: u32,
pub contexts: Vec<ContinuationContextNode>,
pub configs: Vec<ContinuationConfigEntry>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct StaticParserTable {
decision: i32,
accepts: Vec<i32>,
fallbacks: Vec<i32>,
conflict_min_alts: Vec<i32>,
continuations: Vec<ParserContinuation>,
continuation_of: Vec<u32>,
guarded_alts: Vec<i32>,
guard_danger: Vec<i32>,
guard_pass: Vec<i32>,
edge_width: usize,
row_of: Vec<u32>,
rows: Vec<i32>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum DecisionTables {
None,
Single(usize),
Dispatch(PrecedenceDispatch),
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct PrecedenceDispatch {
pub cutoffs: Vec<i32>,
pub class_tables: Vec<i32>,
by_precedence: Box<[i32]>,
}
impl PrecedenceDispatch {
pub fn new(cutoffs: Vec<i32>, class_tables: Vec<i32>) -> Self {
let last = cutoffs.last().copied().unwrap_or(-1);
let dense_end = last.saturating_add(1).clamp(0, MAX_DENSE_PRECEDENCE);
let mut by_precedence = Vec::with_capacity(dense_end as usize + 1);
for precedence in 0..=dense_end {
by_precedence.push(class_tables[class_of(&cutoffs, precedence)]);
}
Self {
cutoffs,
class_tables,
by_precedence: by_precedence.into_boxed_slice(),
}
}
#[inline]
pub fn table_of(&self, precedence: i32) -> i32 {
let precedence = precedence.max(0);
match usize::try_from(precedence)
.ok()
.and_then(|index| self.by_precedence.get(index))
{
Some(&table) => table,
None => self.class_tables[class_of(&self.cutoffs, precedence)],
}
}
}
fn class_of(cutoffs: &[i32], precedence: i32) -> usize {
cutoffs
.iter()
.take_while(|&&cutoff| cutoff < precedence)
.count()
}
#[derive(Clone, Debug, Default, Eq, PartialEq)]
pub struct StaticParserTables {
decisions: Vec<DecisionTables>,
tables: Vec<StaticParserTable>,
}
impl StaticParserTables {
pub fn empty() -> Self {
Self::default()
}
pub fn new(decisions: Vec<DecisionTables>, tables: Vec<StaticParserTable>) -> Self {
Self { decisions, tables }
}
pub fn is_empty(&self) -> bool {
self.tables.is_empty()
}
pub fn tables(&self) -> &[StaticParserTable] {
&self.tables
}
pub fn decisions(&self) -> &[DecisionTables] {
&self.decisions
}
#[inline]
pub fn is_precedence_dispatched(&self, decision: i32) -> bool {
matches!(
usize::try_from(decision)
.ok()
.and_then(|d| self.decisions.get(d)),
Some(DecisionTables::Dispatch(_))
)
}
#[inline]
pub fn table(&self, decision: i32, precedence: i32) -> Option<&StaticParserTable> {
let index = match usize::try_from(decision)
.ok()
.and_then(|decision| self.decisions.get(decision))?
{
DecisionTables::None => return None,
DecisionTables::Single(index) => *index,
DecisionTables::Dispatch(dispatch) => {
let index = dispatch.table_of(precedence);
if index < 0 {
return None;
}
index as usize
}
};
self.tables.get(index)
}
pub fn to_words(&self) -> Vec<u32> {
if self.tables.is_empty() {
return Vec::new();
}
let mut words = vec![
STATIC_PARSER_DFA_MAGIC,
FORMAT_VERSION,
0,
self.tables.len() as u32,
self.decisions.len() as u32,
];
for table in &self.tables {
table.encode_into(&mut words);
}
let dispatches = self
.decisions
.iter()
.enumerate()
.filter_map(|(decision, slot)| match slot {
DecisionTables::Dispatch(dispatch) => Some((decision, dispatch)),
_ => None,
})
.collect::<Vec<_>>();
words.push(dispatches.len() as u32);
for (decision, dispatch) in dispatches {
words.push(decision as u32);
words.push(dispatch.cutoffs.len() as u32);
words.extend(dispatch.cutoffs.iter().map(|&cutoff| cutoff as u32));
words.extend(dispatch.class_tables.iter().map(|&table| table as u32));
}
words[2] = words.len() as u32;
words
}
pub fn from_words(words: &[u32]) -> Result<Self, StaticParserDfaError> {
if words.is_empty() {
return Ok(Self::empty());
}
let mut reader = Reader::new(words);
let magic = reader.next()?;
if magic != STATIC_PARSER_DFA_MAGIC {
return Err(StaticParserDfaError::BadMagic { found: magic });
}
let version = reader.next()?;
if version != FORMAT_VERSION {
return Err(StaticParserDfaError::UnsupportedVersion { found: version });
}
let declared = reader.next()? as usize;
if declared != words.len() {
return Err(StaticParserDfaError::LengthMismatch {
declared,
actual: words.len(),
});
}
let num_tables = checked_count(reader.next()? as usize, 5, reader.remaining())?;
let num_slots = checked_count(reader.next()? as usize, 1, reader.remaining())?;
let mut decisions = vec![DecisionTables::None; num_slots];
let mut tables = Vec::with_capacity(num_tables);
for _ in 0..num_tables {
let (decision, table) = StaticParserTable::decode(&mut reader)?;
if decision >= 0 {
let slot = decisions.get_mut(decision as usize).ok_or(
StaticParserDfaError::InvalidDecision {
decision: decision as usize,
num_slots,
},
)?;
*slot = DecisionTables::Single(tables.len());
}
tables.push(table);
}
let num_dispatches = reader.next()? as usize;
for _ in 0..num_dispatches {
let decision = reader.next()? as usize;
let num_cutoffs = checked_count(reader.next()? as usize, 2, reader.remaining())?;
if decisions
.get(decision)
.is_some_and(|slot| matches!(slot, DecisionTables::Dispatch(_)))
{
return Err(StaticParserDfaError::DuplicateDispatch { decision });
}
let mut cutoffs = Vec::with_capacity(num_cutoffs);
for _ in 0..num_cutoffs {
cutoffs.push(reader.next()? as i32);
}
if cutoffs.windows(2).any(|window| window[0] >= window[1]) {
return Err(StaticParserDfaError::UnsortedCutoffs);
}
let mut class_tables = Vec::with_capacity(num_cutoffs + 1);
for _ in 0..=num_cutoffs {
let table = reader.next()? as i32;
if table < -1 || (table >= 0 && table as usize >= num_tables) {
return Err(StaticParserDfaError::InvalidDispatchTable {
table_index: table,
num_tables,
});
}
class_tables.push(table);
}
let slot =
decisions
.get_mut(decision)
.ok_or(StaticParserDfaError::InvalidDecision {
decision,
num_slots,
})?;
*slot = DecisionTables::Dispatch(PrecedenceDispatch::new(cutoffs, class_tables));
}
if reader.position != words.len() {
return Err(StaticParserDfaError::LengthMismatch {
declared: words.len(),
actual: reader.position,
});
}
Ok(Self { decisions, tables })
}
}
impl StaticParserTable {
pub fn from_state_edges(
decision: i32,
accepts: Vec<i32>,
fallbacks: Vec<i32>,
conflict_min_alts: Vec<i32>,
continuations: Vec<ParserContinuation>,
edges: &[Vec<(i32, i32, u32)>],
) -> Self {
let num_states = accepts.len();
let edge_width = edges
.iter()
.flatten()
.map(|&(_, hi, _)| hi.saturating_add(2).max(1) as usize)
.max()
.unwrap_or(1)
.max(1);
assert!(
edge_width <= MAX_TABLE_COLUMNS,
"a table row must not be wider than {MAX_TABLE_COLUMNS} columns"
);
let mut state_rows = vec![-1_i32; num_states * edge_width];
for (state, ranges) in edges.iter().enumerate() {
let row = &mut state_rows[state * edge_width..(state + 1) * edge_width];
for &(lo, hi, target) in ranges {
for token in lo.max(-1)..=hi {
row[(token + 1) as usize] = target as i32;
}
}
}
let mut rows: Vec<i32> = Vec::new();
let mut row_of = Vec::with_capacity(num_states);
let mut distinct: HashMap<&[i32], u32> = HashMap::new();
for state in 0..num_states {
let key = &state_rows[state * edge_width..(state + 1) * edge_width];
let index = match distinct.get(key) {
Some(&index) => index,
None => {
let index = rows.len() as u32 / edge_width as u32;
rows.extend_from_slice(key);
distinct.insert(key, index);
index
}
};
row_of.push(index);
}
let continuation_of = Self::continuation_slots(&continuations, num_states);
Self {
decision,
accepts,
fallbacks,
conflict_min_alts,
continuations,
continuation_of,
guarded_alts: vec![0; num_states],
guard_danger: Vec::new(),
guard_pass: Vec::new(),
edge_width,
row_of,
rows,
}
}
#[must_use]
pub fn with_guards(
mut self,
guarded_alts: Vec<i32>,
guard_danger: Vec<i32>,
guard_pass: Vec<i32>,
) -> Self {
assert_eq!(
guarded_alts.len(),
self.accepts.len(),
"one guarded alternative per state"
);
self.guarded_alts = guarded_alts;
self.guard_danger = guard_danger;
self.guard_danger.sort_unstable();
self.guard_pass = guard_pass;
self.guard_pass.sort_unstable();
self
}
fn continuation_slots(continuations: &[ParserContinuation], num_states: usize) -> Vec<u32> {
let mut slots = vec![EMPTY_CONTEXT; num_states];
for (index, continuation) in continuations.iter().enumerate() {
if let Some(slot) = slots.get_mut(continuation.state as usize) {
*slot = index as u32;
}
}
slots
}
pub fn decision(&self) -> i32 {
self.decision
}
pub fn num_states(&self) -> usize {
self.accepts.len()
}
#[inline]
pub fn accept(&self, state: i32) -> i32 {
self.accepts[state as usize]
}
#[inline]
pub fn guarded_alt(&self, state: i32) -> Option<i32> {
let alt = *self.guarded_alts.get(state as usize)?;
if alt > 0 {
Some(alt)
} else {
None
}
}
pub fn has_guards(&self) -> bool {
self.guarded_alts.iter().any(|&alt| alt > 0)
}
#[inline]
pub fn guard_step(&self, invoking_state: i32) -> Option<bool> {
if self.guard_danger.binary_search(&invoking_state).is_ok() {
return Some(true);
}
if self.guard_pass.binary_search(&invoking_state).is_err() {
return Some(false);
}
None
}
#[inline]
pub fn fallback(&self, state: i32) -> Option<i32> {
let fallback = self.fallbacks[state as usize];
if fallback > 0 {
Some(fallback)
} else {
None
}
}
#[inline]
pub fn conflict_min_alt(&self, state: i32) -> Option<i32> {
let alt = self.conflict_min_alts[state as usize];
if alt > 0 {
Some(alt)
} else {
None
}
}
#[inline]
pub fn continuation(&self, state: i32) -> Option<(usize, &ParserContinuation)> {
let slot = *self.continuation_of.get(state as usize)?;
if slot == EMPTY_CONTEXT {
None
} else {
Some((slot as usize, &self.continuations[slot as usize]))
}
}
pub fn num_continuations(&self) -> usize {
self.continuations.len()
}
#[inline]
pub fn edge(&self, state: i32, token: i32) -> Option<i32> {
let column = token.wrapping_add(1) as usize;
if column >= self.edge_width {
return None;
}
let row = unsafe { *self.row_of.get_unchecked(state as usize) } as usize;
let target = unsafe { *self.rows.get_unchecked(row * self.edge_width + column) };
if target < 0 {
None
} else {
Some(target)
}
}
fn encode_into(&self, words: &mut Vec<u32>) {
let num_states = self.accepts.len();
words.push(self.decision as u32);
words.push(num_states as u32);
words.push(self.edge_width as u32);
words.push((self.rows.len() / self.edge_width) as u32);
let (offsets, triples) = self.encode_rows();
words.push(triples.len() as u32);
for &accept in &self.accepts {
let accept = if accept == CONFLICT_ESCAPE {
ESCAPE
} else {
accept
};
words.push(accept as u32);
}
words.extend(self.fallbacks.iter().map(|&fallback| fallback as u32));
words.extend(self.row_of.iter().copied());
words.extend(offsets.iter().map(|&offset| offset as u32));
words.extend(triples.iter().map(|&triple| triple as u32));
let conflicts = self
.conflict_min_alts
.iter()
.enumerate()
.filter(|(_, &alt)| alt > 0)
.collect::<Vec<_>>();
words.push(conflicts.len() as u32);
for (state, &alt) in conflicts {
words.push(state as u32);
words.push(alt as u32);
}
words.push(self.continuations.len() as u32);
for continuation in &self.continuations {
words.push(continuation.state);
words.push(continuation.contexts.len() as u32);
for node in &continuation.contexts {
match node {
ContinuationContextNode::Singleton {
parent,
return_state,
} => {
words.push(1);
words.push(*parent);
words.push(*return_state as u32);
}
ContinuationContextNode::Array {
parents,
return_states,
} => {
words.push(parents.len() as u32);
for (&parent, &return_state) in parents.iter().zip(return_states) {
words.push(parent);
words.push(return_state as u32);
}
}
}
}
words.push(continuation.configs.len() as u32);
for config in &continuation.configs {
words.push(config.state as u32);
words.push(config.alt as u32);
words.push(config.context);
words.push(config.outer_depth as u32);
}
}
let guarded = self
.guarded_alts
.iter()
.enumerate()
.filter(|(_, &alt)| alt > 0)
.collect::<Vec<_>>();
words.push(guarded.len() as u32);
for (state, &alt) in guarded {
words.push(state as u32);
words.push(alt as u32);
}
words.push(self.guard_danger.len() as u32);
words.extend(self.guard_danger.iter().map(|&state| state as u32));
words.push(self.guard_pass.len() as u32);
words.extend(self.guard_pass.iter().map(|&state| state as u32));
}
fn encode_rows(&self) -> (Vec<usize>, Vec<i32>) {
let num_rows = self.rows.len() / self.edge_width;
let mut offsets = Vec::with_capacity(num_rows + 1);
let mut triples = Vec::with_capacity(num_rows);
for row_index in 0..num_rows {
offsets.push(triples.len());
let row = &self.rows[row_index * self.edge_width..(row_index + 1) * self.edge_width];
let mut column = 0;
while column < self.edge_width {
let target = row[column];
if target < 0 {
column += 1;
continue;
}
let start = column;
while column + 1 < self.edge_width && row[column + 1] == target {
column += 1;
}
triples.push(start as i32 - 1);
triples.push(column as i32 - 1);
triples.push(target);
column += 1;
}
}
offsets.push(triples.len());
(offsets, triples)
}
#[allow(clippy::too_many_lines)]
fn decode(reader: &mut Reader<'_>) -> Result<(i32, Self), StaticParserDfaError> {
let decision = reader.next()? as i32;
let num_states = reader.next()? as usize;
let edge_width = reader.next()? as usize;
let num_rows = reader.next()? as usize;
let num_row_edge_ints = reader.next()? as usize;
if !num_row_edge_ints.is_multiple_of(3) {
return Err(StaticParserDfaError::InvalidEdgeOffsets);
}
let too_large = num_states == 0
|| edge_width == 0
|| num_states > MAX_TABLE_STATES
|| num_rows > MAX_TABLE_ROWS
|| edge_width > MAX_TABLE_COLUMNS
|| num_rows.saturating_mul(edge_width) > MAX_TABLE_CELLS;
if too_large {
return Err(StaticParserDfaError::InvalidTableSize {
num_states,
num_rows,
edge_width,
});
}
checked_count(num_states, 3, reader.remaining())?;
let mut accepts = Vec::with_capacity(num_states);
for _ in 0..num_states {
accepts.push(reader.next()? as i32);
}
let mut fallbacks = Vec::with_capacity(num_states);
for _ in 0..num_states {
fallbacks.push(reader.next()? as i32);
}
let mut row_of = Vec::with_capacity(num_states);
for _ in 0..num_states {
let row = reader.next()? as i32;
if row < 0 || row as usize >= num_rows {
return Err(StaticParserDfaError::InvalidRowIndex { row, num_rows });
}
row_of.push(row as u32);
}
let mut offsets = Vec::with_capacity(num_rows + 1);
for _ in 0..=num_rows {
offsets.push(reader.next()? as usize);
}
if offsets.first().copied() != Some(0)
|| offsets.last().copied() != Some(num_row_edge_ints)
|| offsets
.windows(2)
.any(|window| window[0] > window[1] || !window[0].is_multiple_of(3))
{
return Err(StaticParserDfaError::InvalidEdgeOffsets);
}
let mut triples = Vec::with_capacity(num_row_edge_ints);
for _ in 0..num_row_edge_ints {
triples.push(reader.next()? as i32);
}
let mut rows = vec![-1_i32; num_rows.saturating_mul(edge_width)];
for row_index in 0..num_rows {
let row = &mut rows[row_index * edge_width..(row_index + 1) * edge_width];
for range in offsets[row_index] / 3..offsets[row_index + 1] / 3 {
let lo = triples[range * 3];
let hi = triples[range * 3 + 1];
let target = triples[range * 3 + 2];
if lo < -1 || hi < lo || hi >= edge_width as i32 - 1 {
return Err(StaticParserDfaError::InvalidEdgeBounds { lo, hi, edge_width });
}
if target < 0 || target as usize >= num_states {
return Err(StaticParserDfaError::InvalidEdgeTarget { target, num_states });
}
for token in lo..=hi {
row[(token + 1) as usize] = target;
}
}
}
let mut conflict_min_alts = vec![0_i32; num_states];
let num_conflicts = checked_count(reader.next()? as usize, 2, reader.remaining())?;
for _ in 0..num_conflicts {
let state = reader.next()? as usize;
let alt = reader.next()? as i32;
if state >= num_states {
return Err(StaticParserDfaError::InvalidStateIndex { state, num_states });
}
if alt <= 0 {
return Err(StaticParserDfaError::InvalidConflictAlt { alt });
}
accepts[state] = CONFLICT_ESCAPE;
conflict_min_alts[state] = alt;
}
let mut continuations = Vec::new();
let num_continuations = checked_count(reader.next()? as usize, 3, reader.remaining())?;
for _ in 0..num_continuations {
let state = reader.next()?;
if state as usize >= num_states {
return Err(StaticParserDfaError::InvalidStateIndex {
state: state as usize,
num_states,
});
}
let num_nodes = checked_count(reader.next()? as usize, 1, reader.remaining())?;
let mut contexts = Vec::with_capacity(num_nodes);
for node in 0..num_nodes {
let arity = checked_count(reader.next()? as usize, 2, reader.remaining())?;
if arity == 0 {
return Err(StaticParserDfaError::EmptyContinuationContext { index: node });
}
let mut parents = Vec::with_capacity(arity);
let mut return_states = Vec::with_capacity(arity);
for _ in 0..arity {
let parent = reader.next()?;
if parent != EMPTY_CONTEXT && parent as usize >= node {
return Err(StaticParserDfaError::InvalidContinuationContext {
index: parent,
decoded: node,
});
}
parents.push(parent);
let return_state = reader.next()? as i32;
if return_state < -1 {
return Err(StaticParserDfaError::InvalidReturnState { return_state });
}
return_states.push(return_state);
}
if arity == 1 {
contexts.push(ContinuationContextNode::Singleton {
parent: parents[0],
return_state: return_states[0],
});
} else {
contexts.push(ContinuationContextNode::Array {
parents,
return_states,
});
}
}
let num_configs = checked_count(reader.next()? as usize, 4, reader.remaining())?;
let mut configs = Vec::with_capacity(num_configs);
for _ in 0..num_configs {
let config_state = reader.next()? as i32;
let alt = reader.next()? as i32;
let context = reader.next()?;
if context != EMPTY_CONTEXT && context as usize >= num_nodes {
return Err(StaticParserDfaError::InvalidContinuationContext {
index: context,
decoded: num_nodes,
});
}
let outer_depth = reader.next()? as i32;
if config_state < 0 || alt <= 0 || outer_depth < 0 {
return Err(StaticParserDfaError::InvalidContinuationConfig {
state: config_state,
alt,
outer_depth,
});
}
configs.push(ContinuationConfigEntry {
state: config_state,
alt,
context,
outer_depth,
});
}
if continuations
.iter()
.any(|existing: &ParserContinuation| existing.state == state)
{
return Err(StaticParserDfaError::DuplicateContinuation { state });
}
continuations.push(ParserContinuation {
state,
contexts,
configs,
});
}
let mut guarded_alts = vec![0_i32; num_states];
let num_guarded = checked_count(reader.next()? as usize, 2, reader.remaining())?;
for _ in 0..num_guarded {
let state = reader.next()? as usize;
let alt = reader.next()? as i32;
if state >= num_states {
return Err(StaticParserDfaError::InvalidStateIndex { state, num_states });
}
if alt <= 0 {
return Err(StaticParserDfaError::InvalidConflictAlt { alt });
}
if guarded_alts[state] != 0 {
return Err(StaticParserDfaError::DuplicateGuard { state });
}
accepts[state] = GUARDED;
guarded_alts[state] = alt;
}
let num_danger = checked_count(reader.next()? as usize, 1, reader.remaining())?;
let mut guard_danger = Vec::with_capacity(num_danger);
for _ in 0..num_danger {
let state = reader.next()? as i32;
if state < 0 {
return Err(StaticParserDfaError::InvalidGuardState { state });
}
guard_danger.push(state);
}
guard_danger.sort_unstable();
let num_pass = checked_count(reader.next()? as usize, 1, reader.remaining())?;
let mut guard_pass = Vec::with_capacity(num_pass);
for _ in 0..num_pass {
let state = reader.next()? as i32;
if state < 0 {
return Err(StaticParserDfaError::InvalidGuardState { state });
}
guard_pass.push(state);
}
guard_pass.sort_unstable();
let continuation_of = Self::continuation_slots(&continuations, num_states);
Ok((
decision,
Self {
decision,
accepts,
fallbacks,
conflict_min_alts,
continuations,
continuation_of,
guarded_alts,
guard_danger,
guard_pass,
edge_width,
row_of,
rows,
},
))
}
}
impl StaticParserTables {
pub fn validate_for_atn(&self, atn: &crate::atn::ATN) -> Result<(), StaticParserDfaError> {
let num_states = atn.states_count();
let num_decisions = atn.decision_to_state.len();
let check_state = |state: i64, what: &'static str| {
if state < 0 || state as usize >= num_states {
return Err(StaticParserDfaError::OutsideAtn {
what,
index: state,
count: num_states,
});
}
Ok(())
};
if self.decisions.len() > num_decisions {
return Err(StaticParserDfaError::OutsideAtn {
what: "decision slot",
index: num_decisions as i64,
count: num_decisions,
});
}
for table in &self.tables {
if table.decision as usize >= num_decisions && table.decision >= 0 {
return Err(StaticParserDfaError::OutsideAtn {
what: "table decision",
index: i64::from(table.decision),
count: num_decisions,
});
}
for &state in table.guard_danger.iter().chain(&table.guard_pass) {
check_state(i64::from(state), "guard invoking state")?;
}
for continuation in &table.continuations {
for node in &continuation.contexts {
let return_states: &[i32] = match node {
ContinuationContextNode::Singleton { return_state, .. } => {
std::slice::from_ref(return_state)
}
ContinuationContextNode::Array { return_states, .. } => return_states,
};
for &return_state in return_states {
if return_state >= 0 {
check_state(i64::from(return_state), "return state")?;
}
}
}
for config in &continuation.configs {
check_state(i64::from(config.state), "continuation config state")?;
}
}
}
Ok(())
}
}
pub fn append_sdfa_section(packed_words: &[u32], sdfa_words: &[u32]) -> Vec<u32> {
if sdfa_words.is_empty() {
return packed_words.to_vec();
}
let mut words = Vec::with_capacity(packed_words.len() + sdfa_words.len());
words.extend_from_slice(packed_words);
words.extend_from_slice(sdfa_words);
words[PACKED_ATN_TOTAL_LEN] = words.len() as u32;
words
}
struct Reader<'a> {
words: &'a [u32],
position: usize,
}
impl<'a> Reader<'a> {
const fn new(words: &'a [u32]) -> Self {
Self { words, position: 0 }
}
fn remaining(&self) -> usize {
self.words.len().saturating_sub(self.position)
}
#[inline]
fn next(&mut self) -> Result<u32, StaticParserDfaError> {
let word = *self
.words
.get(self.position)
.ok_or(StaticParserDfaError::TruncatedStream)?;
self.position += 1;
Ok(word)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn dispatch(cutoffs: &[i32], classes: &[i32]) -> PrecedenceDispatch {
PrecedenceDispatch::new(cutoffs.to_vec(), classes.to_vec())
}
#[test]
fn precedence_dispatch_covers_every_class() {
let dispatch = dispatch(&[2, 5], &[10, 11, 12]);
assert_eq!(dispatch.table_of(-1), 10);
assert_eq!(dispatch.table_of(0), 10);
assert_eq!(dispatch.table_of(2), 10);
assert_eq!(dispatch.table_of(3), 11);
assert_eq!(dispatch.table_of(5), 11);
assert_eq!(dispatch.table_of(6), 12);
assert_eq!(dispatch.table_of(1_000_000), 12);
assert_eq!(dispatch.table_of(i32::MAX), 12);
}
#[test]
fn precedence_dispatch_without_cutoffs_is_one_class() {
let dispatch = dispatch(&[], &[7]);
assert_eq!(dispatch.table_of(0), 7);
assert_eq!(dispatch.table_of(i32::MAX), 7);
}
fn table(
decision: i32,
accepts: Vec<i32>,
edges: &[Vec<(i32, i32, u32)>],
) -> StaticParserTable {
let states = accepts.len();
StaticParserTable::from_state_edges(
decision,
accepts,
vec![0; states],
vec![0; states],
Vec::new(),
edges,
)
}
#[test]
fn rows_are_deduplicated_and_decoded() {
let built = table(
0,
vec![0, 1, 1],
&[
vec![(1, 2, 1), (4, 4, 2)],
vec![(1, 2, 1), (4, 4, 2)],
vec![(-1, -1, 0)],
],
);
assert_eq!(built.edge(0, 1), Some(1));
assert_eq!(built.edge(0, 3), None);
assert_eq!(built.edge(0, -1), None);
assert_eq!(built.edge(2, -1), Some(0));
let words = StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built.clone()])
.to_words();
let decoded = StaticParserTables::from_words(&words).expect("the words decode");
assert_eq!(decoded.table(0, 0), Some(&built));
assert_eq!(decoded.to_words(), words);
}
#[test]
fn guarded_takes_round_trip_through_the_guard_section() {
let built = StaticParserTable::from_state_edges(
0,
vec![0, GUARDED],
vec![0, 0],
vec![0, 0],
Vec::new(),
&[vec![(1, 1, 1)], Vec::new()],
)
.with_guards(vec![0, 1], vec![4, 9], vec![2, 7]);
assert!(built.has_guards());
assert_eq!(built.guard_step(4), Some(true));
assert_eq!(built.guard_step(2), None);
assert_eq!(built.guard_step(5), Some(false));
assert_eq!(built.guarded_alt(1), Some(1));
assert_eq!(built.guarded_alt(0), None);
let words = StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built.clone()])
.to_words();
let decoded = StaticParserTables::from_words(&words).expect("the words decode");
let table = decoded.table(0, 0).expect("the table");
assert_eq!(table, &built);
assert_eq!(table.accept(1), GUARDED);
assert_eq!(table.guard_step(9), Some(true));
assert_eq!(table.guard_step(7), None);
assert_eq!(table.guard_step(9), Some(true));
assert_eq!(decoded.to_words(), words);
}
#[test]
fn virtual_alternatives_round_trip_as_accepts() {
let built = table(
0,
vec![0, VIRTUAL_ALT_BASE + 1, 2],
&[vec![(1, 1, 1), (2, 2, 2)], Vec::new(), Vec::new()],
);
let words = StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built.clone()])
.to_words();
let decoded = StaticParserTables::from_words(&words).expect("the words decode");
let table = decoded.table(0, 0).expect("decision 0 has a table");
assert_eq!(table, &built);
assert_eq!(table.accept(1), VIRTUAL_ALT_BASE + 1);
assert_eq!(table.accept(2), 2);
}
#[test]
fn conflict_escapes_round_trip_through_the_min_alt_pairs() {
let built = StaticParserTable::from_state_edges(
0,
vec![CONFLICT_ESCAPE, 2],
vec![1, 0],
vec![1, 0],
Vec::new(),
&[vec![(1, 1, 1)], Vec::new()],
);
let words =
StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built]).to_words();
let decoded = StaticParserTables::from_words(&words).expect("the words decode");
let table = decoded.table(0, 0).expect("decision 0 has a table");
assert_eq!(table.accept(0), CONFLICT_ESCAPE);
assert_eq!(table.conflict_min_alt(0), Some(1));
assert_eq!(table.accept(1), 2);
assert_eq!(table.conflict_min_alt(1), None);
}
#[test]
fn continuations_round_trip_and_validate_their_context_dag() {
let continuation = ParserContinuation {
state: 1,
contexts: vec![
ContinuationContextNode::Singleton {
parent: EMPTY_CONTEXT,
return_state: 7,
},
ContinuationContextNode::Array {
parents: vec![0, EMPTY_CONTEXT],
return_states: vec![8, -1],
},
],
configs: vec![
ContinuationConfigEntry {
state: 3,
alt: 1,
context: 0,
outer_depth: 0,
},
ContinuationConfigEntry {
state: 4,
alt: 2,
context: 1,
outer_depth: 1,
},
],
};
let built = StaticParserTable::from_state_edges(
0,
vec![0, ESCAPE],
vec![0, 0],
vec![0, 0],
vec![continuation],
&[vec![(1, 1, 1)], Vec::new()],
);
let words = StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built.clone()])
.to_words();
let decoded = StaticParserTables::from_words(&words).expect("the words decode");
let table = decoded.table(0, 0).expect("decision 0 has a table");
let (slot, decoded_continuation) = table.continuation(1).expect("the escape has one");
assert_eq!(slot, 0);
assert_eq!(decoded_continuation.state, 1);
assert_eq!(decoded_continuation.contexts.len(), 2);
assert_eq!(decoded_continuation.configs.len(), 2);
assert_eq!(decoded.to_words(), words);
}
#[test]
fn malformed_streams_are_rejected() {
let empty = StaticParserTables::from_words(&[]).expect("an empty stream is empty tables");
assert!(empty.is_empty());
assert_eq!(
StaticParserTables::from_words(&[0, FORMAT_VERSION, 0, 0, 0]),
Err(StaticParserDfaError::BadMagic { found: 0 })
);
assert_eq!(
StaticParserTables::from_words(&[STATIC_PARSER_DFA_MAGIC, 99, 5, 0, 0]),
Err(StaticParserDfaError::UnsupportedVersion { found: 99 })
);
assert_eq!(
StaticParserTables::from_words(&[STATIC_PARSER_DFA_MAGIC, FORMAT_VERSION, 9, 0, 0]),
Err(StaticParserDfaError::LengthMismatch {
declared: 9,
actual: 5
})
);
let built = StaticParserTable::from_state_edges(
0,
vec![ESCAPE],
vec![0],
vec![0],
vec![ParserContinuation {
state: 0,
contexts: vec![ContinuationContextNode::Singleton {
parent: 0,
return_state: 3,
}],
configs: Vec::new(),
}],
&[Vec::new()],
);
let words =
StaticParserTables::new(vec![DecisionTables::Single(0)], vec![built]).to_words();
assert!(
matches!(
StaticParserTables::from_words(&words),
Err(StaticParserDfaError::InvalidContinuationContext { .. })
),
"a self-referencing context node is a cycle"
);
}
}