meta_language/grammar/feature_runtime/
operations.rs

1//! The operation language of external scanners, semantic actions and
2//! predicates, as `js/src/grammar-runtime/operations.js`: a small,
3//! deterministic statement language over the parser state.
4//!
5//! The operations are data in the grammar, compiled at load into the
6//! [`Statement`], [`Condition`] and [`ValueOp`] trees interpreted here.
7
8use std::collections::BTreeMap;
9use std::rc::Rc;
10use std::sync::Arc;
11
12use super::executor::Executor;
13use super::program::Expr;
14use super::results::{Res, content_start};
15use super::text::column_of;
16
17/// The largest integer the operation language computes, as `Number.MAX_SAFE_INTEGER`.
18const SAFE_INTEGER: i64 = (1 << 53) - 1;
19
20/// A value of the operation language: an integer or a text.
21#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
22pub enum OperationValue {
23    /// An integer within the safe range of a JavaScript number.
24    Integer(i64),
25    /// A text.
26    Text(String),
27}
28
29/// Why a parse stops before it ends: a resource limit.
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub(super) enum Abort {
32    StepLimit,
33    NestingTooDeep,
34    MemoryBudget,
35}
36
37/// Why an operation does not complete.
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub(super) enum OpError {
40    /// The operation failed: the match it guards fails.
41    Failed,
42    /// A resource limit ends the parse.
43    Abort(Abort),
44}
45
46impl From<Abort> for OpError {
47    fn from(abort: Abort) -> Self {
48        Self::Abort(abort)
49    }
50}
51
52pub(super) type OpResult<T> = Result<T, OpError>;
53
54/// The immutable parser state threaded through every match: the mode stack,
55/// the named stacks (empty ones dropped) and the named variables.
56#[derive(Debug, PartialEq, Eq, Hash)]
57pub(super) struct StateData {
58    pub(super) modes: Vec<Arc<str>>,
59    pub(super) stacks: BTreeMap<Arc<str>, Vec<OperationValue>>,
60    pub(super) variables: BTreeMap<Arc<str>, OperationValue>,
61}
62
63/// A shared, immutable parser state; equal states are interchangeable.
64#[derive(Clone, Debug, PartialEq, Eq, Hash)]
65pub(super) struct State(pub(super) Rc<StateData>);
66
67impl State {
68    /// The state every parse starts in: the `default` mode, no stacks and no variables.
69    pub(super) fn initial() -> Self {
70        Self(Rc::new(StateData {
71            modes: vec![Arc::from("default")],
72            stacks: BTreeMap::new(),
73            variables: BTreeMap::new(),
74        }))
75    }
76
77    /// The current mode.
78    pub(super) fn mode(&self) -> &str {
79        self.0.modes.last().map_or("default", |mode| mode)
80    }
81
82    /// A mutable working copy for one run of operations.
83    pub(super) fn working(&self) -> Working {
84        Working {
85            modes: self.0.modes.clone(),
86            stacks: self.0.stacks.clone(),
87            variables: self.0.variables.clone(),
88        }
89    }
90}
91
92/// A mutable working copy of a [`State`].
93#[derive(Clone, Debug)]
94pub(super) struct Working {
95    pub(super) modes: Vec<Arc<str>>,
96    pub(super) stacks: BTreeMap<Arc<str>, Vec<OperationValue>>,
97    pub(super) variables: BTreeMap<Arc<str>, OperationValue>,
98}
99
100impl Working {
101    /// Freezes the working copy back into a state.
102    pub(super) fn settle(self) -> State {
103        let mut stacks = self.stacks;
104        stacks.retain(|_, values| !values.is_empty());
105        State(Rc::new(StateData {
106            modes: self.modes,
107            stacks,
108            variables: self.variables,
109        }))
110    }
111}
112
113/// A value operation.
114#[derive(Debug)]
115pub(super) enum ValueOp {
116    Integer(i64),
117    Text(String),
118    Variable(Arc<str>),
119    Top(Arc<str>),
120    Depth(Arc<str>),
121    Column,
122    Matched,
123    Mode,
124    Attribute(String, String),
125    SumOf(String, String),
126    FieldText(String),
127    Length(Box<Self>),
128    Number(Box<Self>),
129    Add(Box<Self>, Box<Self>),
130    Subtract(Box<Self>, Box<Self>),
131    Multiply(Box<Self>, Box<Self>),
132}
133
134/// A condition operation.
135#[derive(Debug)]
136pub(super) enum Condition {
137    Valid(Arc<str>),
138    /// Whether the parse, where the scan started, tries the item of this id
139    /// (see `Expectations` in executor.rs).
140    Expected(usize),
141    Next(Expr),
142    AtEnd,
143    Equal(ValueOp, ValueOp),
144    Less(ValueOp, ValueOp),
145    Greater(ValueOp, ValueOp),
146    All(Vec<Self>),
147    Some(Vec<Self>),
148    Not(Box<Self>),
149}
150
151/// A statement operation.
152#[derive(Debug)]
153pub(super) enum Statement {
154    Advance,
155    Consume(Expr),
156    Skip(Expr),
157    Mark,
158    Emit(Arc<str>),
159    Fail,
160    If(Condition, Vec<Self>, Option<Vec<Self>>),
161    While(Condition, Vec<Self>),
162    Push(Arc<str>, ValueOp),
163    Pop(Arc<str>),
164    Set(Arc<str>, ValueOp),
165    PushMode(Arc<str>),
166    PopMode,
167    SetMode(Arc<str>),
168    SetAttribute(String, ValueOp),
169    BuildNode(Arc<str>),
170}
171
172/// What the operations of one context may read and do. Every operation an
173/// executor does not offer in a context is rejected at load, so the default
174/// methods are never reached.
175pub(super) trait Machine {
176    fn state(&mut self) -> &mut Working;
177    fn step(&mut self) -> Result<(), Abort>;
178    fn requested(&self) -> Option<&str> {
179        None
180    }
181    fn expected(&mut self, _id: usize) -> bool {
182        false
183    }
184    fn column(&mut self) -> usize;
185    fn at_end(&mut self) -> bool;
186    fn matched(&mut self) -> OpResult<String> {
187        Err(OpError::Failed)
188    }
189    fn lookahead(&mut self, _item: &Expr) -> OpResult<bool> {
190        Ok(false)
191    }
192    fn attribute(&mut self, _field: &str, _name: &str) -> OpResult<OperationValue> {
193        Err(OpError::Failed)
194    }
195    fn attributes(&mut self, _field: &str, _name: &str) -> OpResult<Vec<OperationValue>> {
196        Err(OpError::Failed)
197    }
198    fn field_text(&mut self, _field: &str) -> OpResult<String> {
199        Err(OpError::Failed)
200    }
201    fn advance(&mut self) -> OpResult<()> {
202        Err(OpError::Failed)
203    }
204    fn consume(&mut self, _item: &Expr) -> OpResult<()> {
205        Err(OpError::Failed)
206    }
207    fn skip(&mut self, _item: &Expr) -> OpResult<()> {
208        Err(OpError::Failed)
209    }
210    fn mark(&mut self) {}
211    fn set_attribute(&mut self, _name: &str, _value: OperationValue) {}
212    fn build_node(&mut self, _kind: &Arc<str>) {}
213}
214
215const fn integer(value: &OperationValue) -> OpResult<i64> {
216    match value {
217        OperationValue::Integer(value) => Ok(*value),
218        OperationValue::Text(_) => Err(OpError::Failed),
219    }
220}
221
222fn checked(value: Option<i64>) -> OpResult<OperationValue> {
223    match value {
224        Some(value) if (-SAFE_INTEGER..=SAFE_INTEGER).contains(&value) => {
225            Ok(OperationValue::Integer(value))
226        }
227        _ => Err(OpError::Failed),
228    }
229}
230
231fn to_integer(value: usize) -> OperationValue {
232    OperationValue::Integer(i64::try_from(value).unwrap_or(i64::MAX))
233}
234
235fn arithmetic(
236    left: &ValueOp,
237    right: &ValueOp,
238    machine: &mut dyn Machine,
239    combine: fn(i64, i64) -> Option<i64>,
240) -> OpResult<OperationValue> {
241    let left = integer(&evaluate_value(left, machine)?)?;
242    let right = integer(&evaluate_value(right, machine)?)?;
243    checked(combine(left, right))
244}
245
246fn is_number_text(text: &str) -> bool {
247    let digits = text.strip_prefix('-').unwrap_or(text);
248    (1..=15).contains(&digits.len()) && digits.bytes().all(|byte| byte.is_ascii_digit())
249}
250
251/// Evaluates a value operation.
252pub(super) fn evaluate_value(
253    value: &ValueOp,
254    machine: &mut dyn Machine,
255) -> OpResult<OperationValue> {
256    machine.step()?;
257    Ok(match value {
258        ValueOp::Integer(value) => OperationValue::Integer(*value),
259        ValueOp::Text(value) => OperationValue::Text(value.clone()),
260        ValueOp::Variable(name) => machine
261            .state()
262            .variables
263            .get(name)
264            .cloned()
265            .unwrap_or(OperationValue::Integer(0)),
266        ValueOp::Top(stack) => machine
267            .state()
268            .stacks
269            .get(stack)
270            .and_then(|values| values.last().cloned())
271            .unwrap_or(OperationValue::Integer(0)),
272        ValueOp::Depth(stack) => to_integer(machine.state().stacks.get(stack).map_or(0, Vec::len)),
273        ValueOp::Column => to_integer(machine.column()),
274        ValueOp::Matched => OperationValue::Text(machine.matched()?),
275        ValueOp::Mode => OperationValue::Text(
276            machine
277                .state()
278                .modes
279                .last()
280                .map_or_else(String::new, std::string::ToString::to_string),
281        ),
282        ValueOp::Attribute(field, name) => machine.attribute(field, name)?,
283        ValueOp::SumOf(field, name) => {
284            let mut sum = OperationValue::Integer(0);
285            for item in machine.attributes(field, name)? {
286                sum = checked(integer(&sum)?.checked_add(integer(&item)?))?;
287            }
288            sum
289        }
290        ValueOp::FieldText(field) => OperationValue::Text(machine.field_text(field)?),
291        ValueOp::Length(inner) => match evaluate_value(inner, machine)? {
292            OperationValue::Text(text) => to_integer(text.chars().count()),
293            OperationValue::Integer(_) => return Err(OpError::Failed),
294        },
295        ValueOp::Number(inner) => match evaluate_value(inner, machine)? {
296            number @ OperationValue::Integer(_) => number,
297            OperationValue::Text(text) => {
298                if !is_number_text(&text) {
299                    return Err(OpError::Failed);
300                }
301                OperationValue::Integer(text.parse().map_err(|_| OpError::Failed)?)
302            }
303        },
304        ValueOp::Add(left, right) => arithmetic(left, right, machine, i64::checked_add)?,
305        ValueOp::Subtract(left, right) => arithmetic(left, right, machine, i64::checked_sub)?,
306        ValueOp::Multiply(left, right) => arithmetic(left, right, machine, i64::checked_mul)?,
307    })
308}
309
310/// Evaluates a condition operation.
311pub(super) fn evaluate_condition(
312    condition: &Condition,
313    machine: &mut dyn Machine,
314) -> OpResult<bool> {
315    machine.step()?;
316    Ok(match condition {
317        Condition::Valid(token) => machine.requested() == Some(&**token),
318        Condition::Expected(id) => machine.expected(*id),
319        Condition::Next(item) => machine.lookahead(item)?,
320        Condition::AtEnd => machine.at_end(),
321        Condition::Equal(left, right) => {
322            let left = evaluate_value(left, machine)?;
323            let right = evaluate_value(right, machine)?;
324            left == right
325        }
326        Condition::Less(left, right) => {
327            let left = integer(&evaluate_value(left, machine)?)?;
328            left < integer(&evaluate_value(right, machine)?)?
329        }
330        Condition::Greater(left, right) => {
331            let left = integer(&evaluate_value(left, machine)?)?;
332            left > integer(&evaluate_value(right, machine)?)?
333        }
334        Condition::All(items) => {
335            for item in items {
336                if !evaluate_condition(item, machine)? {
337                    return Ok(false);
338                }
339            }
340            true
341        }
342        Condition::Some(items) => {
343            for item in items {
344                if evaluate_condition(item, machine)? {
345                    return Ok(true);
346                }
347            }
348            false
349        }
350        Condition::Not(inner) => !evaluate_condition(inner, machine)?,
351    })
352}
353
354/// Runs a statement list: `Some(token)` when an `emit` ends the run, `None`
355/// when the list runs out.
356pub(super) fn run_statements(
357    statements: &[Statement],
358    machine: &mut dyn Machine,
359) -> OpResult<Option<Arc<str>>> {
360    for statement in statements {
361        machine.step()?;
362        match statement {
363            Statement::Advance => machine.advance()?,
364            Statement::Consume(item) => machine.consume(item)?,
365            Statement::Skip(item) => machine.skip(item)?,
366            Statement::Mark => machine.mark(),
367            Statement::Emit(token) => return Ok(Some(token.clone())),
368            Statement::Fail => return Err(OpError::Failed),
369            Statement::If(condition, consequent, alternative) => {
370                let branch = if evaluate_condition(condition, machine)? {
371                    Some(consequent)
372                } else {
373                    alternative.as_ref()
374                };
375                if let Some(branch) = branch
376                    && let Some(signal) = run_statements(branch, machine)?
377                {
378                    return Ok(Some(signal));
379                }
380            }
381            Statement::While(condition, body) => {
382                while evaluate_condition(condition, machine)? {
383                    if let Some(signal) = run_statements(body, machine)? {
384                        return Ok(Some(signal));
385                    }
386                }
387            }
388            Statement::Push(stack, value) => {
389                let value = evaluate_value(value, machine)?;
390                machine
391                    .state()
392                    .stacks
393                    .entry(stack.clone())
394                    .or_default()
395                    .push(value);
396            }
397            Statement::Pop(stack) => {
398                let popped = machine.state().stacks.get_mut(stack).and_then(Vec::pop);
399                if popped.is_none() {
400                    return Err(OpError::Failed);
401                }
402            }
403            Statement::Set(variable, value) => {
404                let value = evaluate_value(value, machine)?;
405                machine.state().variables.insert(variable.clone(), value);
406            }
407            Statement::PushMode(mode) => machine.state().modes.push(mode.clone()),
408            Statement::PopMode => {
409                let modes = &mut machine.state().modes;
410                if modes.len() <= 1 {
411                    return Err(OpError::Failed);
412                }
413                modes.pop();
414            }
415            Statement::SetMode(mode) => {
416                if let Some(last) = machine.state().modes.last_mut() {
417                    *last = mode.clone();
418                }
419            }
420            Statement::SetAttribute(name, value) => {
421                let value = evaluate_value(value, machine)?;
422                machine.set_attribute(name, value);
423            }
424            Statement::BuildNode(kind) => machine.build_node(kind),
425        }
426    }
427    Ok(None)
428}
429
430/// The operations each context may use; loading rejects any other.
431pub(super) fn allowed_in(context: &str, operation: &str) -> bool {
432    const COMMON: &[&str] = &[
433        "if", "while", "push", "pop", "set", "pushMode", "popMode", "setMode", "atEnd", "equal",
434        "less", "greater", "all", "some", "not", "integer", "text", "variable", "top", "depth",
435        "column", "mode", "length", "number", "add", "subtract", "multiply",
436    ];
437    const SCANNER: &[&str] = &[
438        "advance", "consume", "skip", "mark", "emit", "fail", "valid", "expected", "next",
439    ];
440    const ACTION: &[&str] = &[
441        "fail",
442        "setAttribute",
443        "buildNode",
444        "matched",
445        "attribute",
446        "sumOf",
447        "fieldText",
448    ];
449    const PREDICATE: &[&str] = &[
450        "atEnd", "equal", "less", "greater", "all", "some", "not", "integer", "text", "variable",
451        "top", "depth", "column", "matched", "mode", "length", "number", "add", "subtract",
452        "multiply",
453    ];
454    match context {
455        "scanner" => COMMON.contains(&operation) || SCANNER.contains(&operation),
456        "action" => COMMON.contains(&operation) || ACTION.contains(&operation),
457        _ => PREDICATE.contains(&operation),
458    }
459}
460
461/// The read-only machine conditions see over one result.
462pub(super) struct ValueMachine<'e, 'c> {
463    executor: &'e mut Executor<'c>,
464    working: Working,
465    start: usize,
466    end: usize,
467}
468
469impl<'e, 'c> ValueMachine<'e, 'c> {
470    pub(super) fn new(executor: &'e mut Executor<'c>, result: &Res, from: usize) -> Self {
471        Self {
472            start: content_start(&result.children, from),
473            end: result.end,
474            working: result.state.working(),
475            executor,
476        }
477    }
478}
479
480impl Machine for ValueMachine<'_, '_> {
481    fn state(&mut self) -> &mut Working {
482        &mut self.working
483    }
484
485    fn step(&mut self) -> Result<(), Abort> {
486        self.executor.step()
487    }
488
489    fn column(&mut self) -> usize {
490        column_of(self.executor.bytes, self.start, self.executor.begin)
491    }
492
493    fn at_end(&mut self) -> bool {
494        self.end == self.executor.end
495    }
496
497    fn matched(&mut self) -> OpResult<String> {
498        Ok(self.executor.text(self.start, self.end))
499    }
500}
meta_language/grammar/feature_runtime/operations.rs

meta_language/grammar/feature_runtime/
operations.rs
