sim_lib_pattern/
extension.rs

1//! Explicitly opt-in, separately metered execution for non-regular constructs.
2
3use crate::{AssertionId, CaptureId};
4use std::collections::VecDeque;
5
6/// Stable kinds understood by the non-regular extension lane.
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub enum ExtensionKind {
9    /// Compare input with an earlier capture.
10    Backreference(CaptureId),
11    /// Evaluate an assertion whose width cannot be established statically.
12    VariableWidthAssertion(AssertionId),
13}
14
15/// Independent limits for work that can invalidate regular worst-case bounds.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub struct ExtensionLimits {
18    /// Maximum capture bytes or code units inspected.
19    pub max_capture_units: usize,
20    /// Maximum queue entries evaluated.
21    pub max_work_items: usize,
22}
23
24/// Exact non-regular work charged by an attempt.
25#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
26pub struct ExtensionReceipt {
27    /// Capture bytes or code units inspected.
28    pub capture_units: usize,
29    /// Queue entries evaluated.
30    pub work_items: usize,
31}
32
33/// Typed reason that extension execution did not produce a match decision.
34#[derive(Clone, Copy, Debug, PartialEq, Eq)]
35pub enum ExtensionRefusal {
36    /// No installed extension admitted this operation.
37    Unsupported(ExtensionKind),
38    /// The capture-byte or code-unit allowance was exhausted.
39    CaptureUnits,
40    /// The recursion-free work queue allowance was exhausted.
41    WorkItems,
42}
43
44/// One unit placed onto the bounded extension queue.
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub struct ExtensionWork<T> {
47    /// Extension-private, caller-defined work payload.
48    pub payload: T,
49    /// Capture bytes or code units this item will inspect.
50    pub capture_units: usize,
51}
52
53/// Result of a bounded non-regular attempt.
54#[derive(Clone, Debug, PartialEq, Eq)]
55pub enum ExtensionOutcome {
56    /// The extension accepted.
57    Match(ExtensionReceipt),
58    /// The extension rejected conclusively.
59    NoMatch(ExtensionReceipt),
60    /// The feature was unsupported or its independent budget was exhausted.
61    Refused {
62        /// Exact refusal.
63        reason: ExtensionRefusal,
64        /// Work consumed before refusal.
65        receipt: ExtensionReceipt,
66    },
67}
68
69/// Result of evaluating one queue item without recursive calls.
70#[derive(Clone, Debug, PartialEq, Eq)]
71pub enum ExtensionStep<T> {
72    /// This branch matched.
73    Match,
74    /// This branch ended without matching.
75    NoMatch,
76    /// Add bounded continuation work to the queue.
77    Continue(Vec<ExtensionWork<T>>),
78}
79
80/// Opt-in implementation of one non-regular feature family.
81pub trait BoundedExtension {
82    /// Extension-private queue payload.
83    type Work;
84
85    /// Reports whether this implementation admits `kind` and creates initial work.
86    fn start(&self, kind: ExtensionKind) -> Option<Vec<ExtensionWork<Self::Work>>>;
87
88    /// Evaluates exactly one item. Implementations continue through returned work,
89    /// never by recursively invoking the executor.
90    fn step(&self, work: Self::Work) -> ExtensionStep<Self::Work>;
91}
92
93/// Executes an admitted non-regular operation using an independent FIFO budget.
94pub fn execute_extension<X: BoundedExtension>(
95    extension: &X,
96    kind: ExtensionKind,
97    limits: ExtensionLimits,
98) -> ExtensionOutcome {
99    let Some(initial) = extension.start(kind) else {
100        return ExtensionOutcome::Refused {
101            reason: ExtensionRefusal::Unsupported(kind),
102            receipt: ExtensionReceipt::default(),
103        };
104    };
105    let mut queue = VecDeque::from(initial);
106    let mut receipt = ExtensionReceipt::default();
107    while let Some(work) = queue.pop_front() {
108        if receipt.work_items == limits.max_work_items {
109            return refused(ExtensionRefusal::WorkItems, receipt);
110        }
111        if work.capture_units
112            > limits
113                .max_capture_units
114                .saturating_sub(receipt.capture_units)
115        {
116            return refused(ExtensionRefusal::CaptureUnits, receipt);
117        }
118        receipt.work_items += 1;
119        receipt.capture_units += work.capture_units;
120        match extension.step(work.payload) {
121            ExtensionStep::Match => return ExtensionOutcome::Match(receipt),
122            ExtensionStep::NoMatch => {}
123            ExtensionStep::Continue(next) => queue.extend(next),
124        }
125    }
126    ExtensionOutcome::NoMatch(receipt)
127}
128
129fn refused(reason: ExtensionRefusal, receipt: ExtensionReceipt) -> ExtensionOutcome {
130    ExtensionOutcome::Refused { reason, receipt }
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    struct Backreference;
138
139    impl BoundedExtension for Backreference {
140        type Work = usize;
141
142        fn start(&self, kind: ExtensionKind) -> Option<Vec<ExtensionWork<Self::Work>>> {
143            matches!(kind, ExtensionKind::Backreference(_)).then(|| {
144                vec![ExtensionWork {
145                    payload: 0,
146                    capture_units: 3,
147                }]
148            })
149        }
150
151        fn step(&self, offset: usize) -> ExtensionStep<Self::Work> {
152            if offset == 3 {
153                ExtensionStep::Match
154            } else {
155                ExtensionStep::Continue(vec![ExtensionWork {
156                    payload: offset + 1,
157                    capture_units: 3,
158                }])
159            }
160        }
161    }
162
163    #[test]
164    fn backreference_exhausts_capture_budget_deterministically() {
165        let limits = ExtensionLimits {
166            max_capture_units: 6,
167            max_work_items: 8,
168        };
169        let expected = ExtensionOutcome::Refused {
170            reason: ExtensionRefusal::CaptureUnits,
171            receipt: ExtensionReceipt {
172                capture_units: 6,
173                work_items: 2,
174            },
175        };
176        for _ in 0..3 {
177            assert_eq!(
178                execute_extension(
179                    &Backreference,
180                    ExtensionKind::Backreference(CaptureId(1)),
181                    limits
182                ),
183                expected
184            );
185        }
186    }
187
188    #[test]
189    fn unsupported_extensions_are_typed() {
190        assert!(matches!(
191            execute_extension(
192                &Backreference,
193                ExtensionKind::VariableWidthAssertion(AssertionId(4)),
194                ExtensionLimits {
195                    max_capture_units: 10,
196                    max_work_items: 10
197                }
198            ),
199            ExtensionOutcome::Refused {
200                reason: ExtensionRefusal::Unsupported(ExtensionKind::VariableWidthAssertion(
201                    AssertionId(4)
202                )),
203                ..
204            }
205        ));
206    }
207}
sim_lib_pattern/extension.rs

sim_lib_pattern/
extension.rs
