sim_lib_pattern/
ir.rs

1//! Validated, dialect-neutral pattern intermediate representation.
2
3use crate::SymbolDomain;
4use core::fmt;
5use core::marker::PhantomData;
6use std::collections::{BTreeMap, BTreeSet};
7
8/// Stable identifier for a tagged capture.
9#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
10pub struct CaptureId(pub u32);
11
12/// Stable identifier for a named assertion definition.
13#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
14pub struct AssertionId(pub u32);
15
16/// A zero-width subject anchor.
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum Anchor {
19    /// Start of the subject.
20    SubjectStart,
21    /// End of the subject.
22    SubjectEnd,
23}
24
25/// Valid bounds for a repetition node.
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub struct RepeatBounds {
28    min: usize,
29    max: Option<usize>,
30}
31
32impl RepeatBounds {
33    /// Creates repetition bounds, rejecting a finite maximum below `min`.
34    ///
35    /// ```
36    /// use sim_lib_pattern::RepeatBounds;
37    ///
38    /// let error = RepeatBounds::new(4, Some(3)).unwrap_err();
39    /// assert_eq!(
40    ///     error.to_string(),
41    ///     "invalid repeat bounds: minimum 4 exceeds maximum 3"
42    /// );
43    /// ```
44    pub fn new(min: usize, max: Option<usize>) -> Result<Self, IrError> {
45        if let Some(max) = max
46            && min > max
47        {
48            return Err(IrError::InvalidRepeatBounds { min, max });
49        }
50        Ok(Self { min, max })
51    }
52
53    /// Returns the minimum number of matches.
54    pub const fn min(self) -> usize {
55        self.min
56    }
57
58    /// Returns the maximum number of matches, or `None` when unbounded.
59    pub const fn max(self) -> Option<usize> {
60        self.max
61    }
62}
63
64/// One structured pattern expression.
65#[derive(Clone, Debug, PartialEq, Eq)]
66pub enum IrNode<S, E> {
67    /// Match one exact symbol.
68    Symbol(S),
69    /// Match any one symbol.
70    Any,
71    /// Match every child in order.
72    Concat(Vec<Self>),
73    /// Try each child as an alternative.
74    Alternation(Vec<Self>),
75    /// Repeat a child within validated bounds.
76    Repeat {
77        /// Expression being repeated.
78        node: Box<Self>,
79        /// Validated repetition bounds.
80        bounds: RepeatBounds,
81        /// Whether longer matches are preferred.
82        greedy: bool,
83    },
84    /// Preserve explicit grouping from the source dialect.
85    Group(Box<Self>),
86    /// Record the child's subject span under a stable tag.
87    Capture {
88        /// Unique capture tag within the IR.
89        id: CaptureId,
90        /// Captured expression.
91        node: Box<Self>,
92    },
93    /// Test a zero-width subject boundary.
94    Anchor(Anchor),
95    /// Evaluate a separately declared zero-width assertion.
96    Assertion(AssertionId),
97    /// A dialect-specific operation explicitly admitted by the target engine.
98    Extension(E),
99}
100
101/// Target-engine policy for dialect extension nodes.
102#[derive(Clone, Debug, PartialEq, Eq)]
103pub struct EnginePolicy<E> {
104    admitted_extensions: BTreeSet<E>,
105}
106
107impl<E: Ord> EnginePolicy<E> {
108    /// Creates a policy from exactly the extension operations an engine admits.
109    pub fn new(admitted_extensions: impl IntoIterator<Item = E>) -> Self {
110        Self {
111            admitted_extensions: admitted_extensions.into_iter().collect(),
112        }
113    }
114}
115
116/// A fully validated pattern IR tied to one symbol and offset domain.
117#[derive(Clone, Debug, PartialEq, Eq)]
118pub struct PatternIr<D: SymbolDomain, E> {
119    root: IrNode<D::Symbol, E>,
120    assertions: BTreeMap<AssertionId, IrNode<D::Symbol, E>>,
121    domain: PhantomData<fn() -> D>,
122}
123
124impl<D, E> PatternIr<D, E>
125where
126    D: SymbolDomain,
127    E: Clone + fmt::Debug + Ord,
128{
129    /// Validates and creates an IR for a target engine.
130    pub fn new(
131        root: IrNode<D::Symbol, E>,
132        assertions: BTreeMap<AssertionId, IrNode<D::Symbol, E>>,
133        policy: &EnginePolicy<E>,
134    ) -> Result<Self, IrError> {
135        let mut captures = BTreeSet::new();
136        validate_node(&root, &assertions, policy, &mut captures)?;
137        for definition in assertions.values() {
138            validate_node(definition, &assertions, policy, &mut captures)?;
139        }
140        validate_assertion_cycles(&root, &assertions, &mut Vec::new())?;
141        for (id, definition) in &assertions {
142            validate_assertion_cycles(definition, &assertions, &mut vec![*id])?;
143        }
144        Ok(Self {
145            root,
146            assertions,
147            domain: PhantomData,
148        })
149    }
150
151    /// Returns the root expression.
152    pub fn root(&self) -> &IrNode<D::Symbol, E> {
153        &self.root
154    }
155
156    /// Returns the validated assertion definitions.
157    pub fn assertions(&self) -> &BTreeMap<AssertionId, IrNode<D::Symbol, E>> {
158        &self.assertions
159    }
160}
161
162/// A construction failure for pattern IR.
163#[derive(Clone, Debug, PartialEq, Eq)]
164pub enum IrError {
165    /// A repeat's minimum exceeds its maximum.
166    InvalidRepeatBounds {
167        /// Requested minimum.
168        min: usize,
169        /// Requested finite maximum.
170        max: usize,
171    },
172    /// A capture identifier occurs more than once.
173    DuplicateCapture(CaptureId),
174    /// An assertion refers to a definition that was not supplied.
175    MissingAssertion(AssertionId),
176    /// Assertion references form a cycle.
177    AssertionCycle(Vec<AssertionId>),
178    /// An extension is unavailable on the selected target engine.
179    UnsupportedExtension(String),
180}
181
182impl fmt::Display for IrError {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        match self {
185            Self::InvalidRepeatBounds { min, max } => {
186                write!(
187                    f,
188                    "invalid repeat bounds: minimum {min} exceeds maximum {max}"
189                )
190            }
191            Self::DuplicateCapture(id) => write!(f, "duplicate capture id {}", id.0),
192            Self::MissingAssertion(id) => write!(f, "missing assertion id {}", id.0),
193            Self::AssertionCycle(path) => write!(f, "assertion cycle: {path:?}"),
194            Self::UnsupportedExtension(extension) => {
195                write!(f, "target engine does not admit extension {extension}")
196            }
197        }
198    }
199}
200
201impl std::error::Error for IrError {}
202
203fn validate_node<S, E>(
204    node: &IrNode<S, E>,
205    assertions: &BTreeMap<AssertionId, IrNode<S, E>>,
206    policy: &EnginePolicy<E>,
207    captures: &mut BTreeSet<CaptureId>,
208) -> Result<(), IrError>
209where
210    E: fmt::Debug + Ord,
211{
212    match node {
213        IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
214            for node in nodes {
215                validate_node(node, assertions, policy, captures)?;
216            }
217        }
218        IrNode::Repeat { node, .. } | IrNode::Group(node) => {
219            validate_node(node, assertions, policy, captures)?;
220        }
221        IrNode::Capture { id, node } => {
222            if !captures.insert(*id) {
223                return Err(IrError::DuplicateCapture(*id));
224            }
225            validate_node(node, assertions, policy, captures)?;
226        }
227        IrNode::Assertion(id) => {
228            assertions.get(id).ok_or(IrError::MissingAssertion(*id))?;
229        }
230        IrNode::Extension(extension) if !policy.admitted_extensions.contains(extension) => {
231            return Err(IrError::UnsupportedExtension(format!("{extension:?}")));
232        }
233        IrNode::Symbol(_) | IrNode::Any | IrNode::Anchor(_) | IrNode::Extension(_) => {}
234    }
235    Ok(())
236}
237
238fn validate_assertion_cycles<S, E>(
239    node: &IrNode<S, E>,
240    assertions: &BTreeMap<AssertionId, IrNode<S, E>>,
241    path: &mut Vec<AssertionId>,
242) -> Result<(), IrError> {
243    match node {
244        IrNode::Concat(nodes) | IrNode::Alternation(nodes) => {
245            for node in nodes {
246                validate_assertion_cycles(node, assertions, path)?;
247            }
248        }
249        IrNode::Repeat { node, .. } | IrNode::Group(node) | IrNode::Capture { node, .. } => {
250            validate_assertion_cycles(node, assertions, path)?;
251        }
252        IrNode::Assertion(id) => {
253            if let Some(cycle_start) = path.iter().position(|seen| seen == id) {
254                let mut cycle = path[cycle_start..].to_vec();
255                cycle.push(*id);
256                return Err(IrError::AssertionCycle(cycle));
257            }
258            let definition = assertions.get(id).ok_or(IrError::MissingAssertion(*id))?;
259            path.push(*id);
260            let result = validate_assertion_cycles(definition, assertions, path);
261            path.pop();
262            result?;
263        }
264        IrNode::Symbol(_) | IrNode::Any | IrNode::Anchor(_) | IrNode::Extension(_) => {}
265    }
266    Ok(())
267}
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272    use crate::ByteDomain;
273
274    #[test]
275    fn invalid_repeat_names_both_bounds() {
276        let error = RepeatBounds::new(4, Some(3)).unwrap_err();
277        assert_eq!(
278            error.to_string(),
279            "invalid repeat bounds: minimum 4 exceeds maximum 3"
280        );
281    }
282
283    #[test]
284    fn rejects_duplicate_capture_ids() {
285        let capture = |symbol| IrNode::Capture {
286            id: CaptureId(7),
287            node: Box::new(IrNode::Symbol(symbol)),
288        };
289        let root = IrNode::Concat(vec![capture(b'a'), capture(b'b')]);
290        let error =
291            PatternIr::<ByteDomain, &str>::new(root, BTreeMap::new(), &EnginePolicy::new([]))
292                .unwrap_err();
293        assert_eq!(error, IrError::DuplicateCapture(CaptureId(7)));
294    }
295
296    #[test]
297    fn rejects_assertion_cycles() {
298        let assertions = BTreeMap::from([
299            (AssertionId(1), IrNode::Assertion(AssertionId(2))),
300            (AssertionId(2), IrNode::Assertion(AssertionId(1))),
301        ]);
302        let error = PatternIr::<ByteDomain, &str>::new(
303            IrNode::Assertion(AssertionId(1)),
304            assertions,
305            &EnginePolicy::new([]),
306        )
307        .unwrap_err();
308        assert_eq!(
309            error,
310            IrError::AssertionCycle(vec![AssertionId(1), AssertionId(2), AssertionId(1)])
311        );
312    }
313
314    #[test]
315    fn target_controls_dialect_extensions() {
316        let denied = PatternIr::<ByteDomain, &str>::new(
317            IrNode::Extension("backreference"),
318            BTreeMap::new(),
319            &EnginePolicy::new([]),
320        );
321        assert!(matches!(denied, Err(IrError::UnsupportedExtension(_))));
322
323        let admitted = PatternIr::<ByteDomain, &str>::new(
324            IrNode::Extension("backreference"),
325            BTreeMap::new(),
326            &EnginePolicy::new(["backreference"]),
327        );
328        assert!(admitted.is_ok());
329    }
330}
sim_lib_pattern/ir.rs

sim_lib_pattern/
ir.rs
