regast_core/
lower.rs

1use regast_syntax::{AstKind, ClassSet, NodeId, NodeMap, Pattern, RepKind};
2
3use crate::{Disambiguation, IrId, IrPool, Prov};
4
5const MAX_REPEAT: u32 = 1_000;
6
7#[derive(Clone, Debug)]
8pub struct Lowering {
9    pub root: IrId,
10    pub origins: NodeMap<Vec<IrId>>,
11}
12
13impl Lowering {
14    #[must_use]
15    pub fn ir_for(&self, node: NodeId) -> Option<IrId> {
16        self.origins.get(node)?.last().copied()
17    }
18}
19
20pub fn lower(pattern: &Pattern, pool: &mut IrPool, disambiguation: Disambiguation) -> Lowering {
21    let mut origins: NodeMap<Vec<IrId>> = NodeMap::new(pattern);
22    for cursor in pattern.root().walk().collect::<Vec<_>>().into_iter().rev() {
23        let node = cursor.id();
24        let prov = Prov::Ast(node);
25        let root = match cursor.kind() {
26            AstKind::Empty => pool.one(),
27            AstKind::Anchor { kind } => pool.anchor(*kind, prov),
28            AstKind::Literal { c, .. } => {
29                let set = pool.class_set(ClassSet::singleton(*c));
30                pool.class(set, prov)
31            }
32            AstKind::Dot => {
33                let set = pool.class_set(ClassSet::singleton('\n').negate());
34                pool.class(set, prov)
35            }
36            AstKind::Class { set, .. } => {
37                let set = pool.class_set(set.clone());
38                pool.class(set, prov)
39            }
40            AstKind::Group { inner, .. } => origins.get(*inner).expect("inner lowered")[0],
41            AstKind::Alt { arms } => fold_alt(
42                &origins,
43                pool,
44                arms,
45                node,
46                disambiguation == Disambiguation::Greedy,
47            ),
48            AstKind::Concat { parts } => fold_seq(&origins, pool, parts, node),
49            AstKind::Repeat {
50                inner,
51                kind,
52                greedy,
53            } => {
54                let inner = origins.get(*inner).expect("inner lowered")[0];
55                let greedy = disambiguation == Disambiguation::Posix || *greedy;
56                lower_repeat(pool, inner, *kind, greedy, node)
57            }
58        };
59        origins.insert(node, vec![root]);
60    }
61    Lowering {
62        root: origins.get(pattern.root_id()).expect("root lowered")[0],
63        origins,
64    }
65}
66
67fn fold_alt(
68    origins: &NodeMap<Vec<IrId>>,
69    pool: &mut IrPool,
70    arms: &[NodeId],
71    node: NodeId,
72    ordered: bool,
73) -> IrId {
74    let mut iter = arms.iter().rev();
75    let mut result = origins
76        .get(*iter.next().expect("at least two arms"))
77        .unwrap()[0];
78    for arm in iter {
79        let left = origins.get(*arm).unwrap()[0];
80        result = pool.alt(left, result, Prov::Ast(node), ordered);
81    }
82    result
83}
84
85fn fold_seq(
86    origins: &NodeMap<Vec<IrId>>,
87    pool: &mut IrPool,
88    parts: &[NodeId],
89    node: NodeId,
90) -> IrId {
91    let mut iter = parts.iter().rev();
92    let mut result = origins
93        .get(*iter.next().expect("at least two parts"))
94        .unwrap()[0];
95    for part in iter {
96        let left = origins.get(*part).unwrap()[0];
97        result = pool.seq(left, result, Prov::Ast(node));
98    }
99    result
100}
101
102fn lower_repeat(pool: &mut IrPool, inner: IrId, kind: RepKind, greedy: bool, node: NodeId) -> IrId {
103    let prov = Prov::Ast(node);
104    match kind {
105        RepKind::ZeroOrOne => optional(pool, inner, greedy, node),
106        RepKind::ZeroOrMore => pool.star(inner, prov, greedy),
107        RepKind::OneOrMore => {
108            let star = pool.star(inner, Prov::Synth(node), greedy);
109            pool.seq(inner, star, prov)
110        }
111        RepKind::Range { min, max } => {
112            assert!(min <= MAX_REPEAT, "repeat lower bound exceeds limit");
113            assert!(
114                max.is_none_or(|max| max <= MAX_REPEAT),
115                "repeat upper bound exceeds limit"
116            );
117            lower_range(pool, inner, min, max, greedy, node)
118        }
119    }
120}
121
122fn lower_range(
123    pool: &mut IrPool,
124    inner: IrId,
125    min: u32,
126    max: Option<u32>,
127    greedy: bool,
128    node: NodeId,
129) -> IrId {
130    let (mut suffix, has_suffix) = match max {
131        None => (pool.star(inner, Prov::Synth(node), greedy), true),
132        Some(max) => {
133            let mut optional_suffix = pool.one();
134            for _ in 0..max - min {
135                let seq = if optional_suffix == pool.one() {
136                    inner
137                } else {
138                    pool.seq(inner, optional_suffix, Prov::Synth(node))
139                };
140                optional_suffix = optional(pool, seq, greedy, node);
141            }
142            (optional_suffix, max > min)
143        }
144    };
145    if min == 0 {
146        return suffix;
147    }
148    if !has_suffix {
149        suffix = inner;
150        for _ in 1..min {
151            suffix = pool.seq(inner, suffix, Prov::Synth(node));
152        }
153        return suffix;
154    }
155    for _ in 0..min {
156        suffix = pool.seq(inner, suffix, Prov::Synth(node));
157    }
158    suffix
159}
160
161fn optional(pool: &mut IrPool, inner: IrId, greedy: bool, node: NodeId) -> IrId {
162    if greedy {
163        pool.alt(inner, pool.one(), Prov::Ast(node), false)
164    } else {
165        pool.alt(pool.one(), inner, Prov::Ast(node), true)
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use regast_syntax::Pattern;
172
173    use super::*;
174
175    #[test]
176    fn lowers_every_repeat_form() {
177        for pattern in ["a?", "a*", "a+", "a{2}", "a{1,3}", "a{2,}", "a??"] {
178            let pattern = Pattern::parse(pattern).unwrap();
179            let mut pool = IrPool::new();
180            let lowered = lower(&pattern, &mut pool, Disambiguation::Posix);
181            assert!(lowered.root.index() < u32::try_from(pool.len()).unwrap());
182        }
183    }
184}
regast_core/lower.rs

regast_core/
lower.rs
