1 | use crate::hir::{self, Hir, HirKind}; |
2 | |
3 | /// A trait for visiting the high-level IR (HIR) in depth first order. |
4 | /// |
5 | /// The principle aim of this trait is to enable callers to perform case |
6 | /// analysis on a high-level intermediate representation of a regular |
7 | /// expression without necessarily using recursion. In particular, this permits |
8 | /// callers to do case analysis with constant stack usage, which can be |
9 | /// important since the size of an HIR may be proportional to end user input. |
10 | /// |
11 | /// Typical usage of this trait involves providing an implementation and then |
12 | /// running it using the [`visit`](fn.visit.html) function. |
13 | pub trait Visitor { |
14 | /// The result of visiting an HIR. |
15 | type Output; |
16 | /// An error that visiting an HIR might return. |
17 | type Err; |
18 | |
19 | /// All implementors of `Visitor` must provide a `finish` method, which |
20 | /// yields the result of visiting the HIR or an error. |
21 | fn finish(self) -> Result<Self::Output, Self::Err>; |
22 | |
23 | /// This method is called before beginning traversal of the HIR. |
24 | fn start(&mut self) {} |
25 | |
26 | /// This method is called on an `Hir` before descending into child `Hir` |
27 | /// nodes. |
28 | fn visit_pre(&mut self, _hir: &Hir) -> Result<(), Self::Err> { |
29 | Ok(()) |
30 | } |
31 | |
32 | /// This method is called on an `Hir` after descending all of its child |
33 | /// `Hir` nodes. |
34 | fn visit_post(&mut self, _hir: &Hir) -> Result<(), Self::Err> { |
35 | Ok(()) |
36 | } |
37 | |
38 | /// This method is called between child nodes of an alternation. |
39 | fn visit_alternation_in(&mut self) -> Result<(), Self::Err> { |
40 | Ok(()) |
41 | } |
42 | } |
43 | |
44 | /// Executes an implementation of `Visitor` in constant stack space. |
45 | /// |
46 | /// This function will visit every node in the given `Hir` while calling |
47 | /// appropriate methods provided by the |
48 | /// [`Visitor`](trait.Visitor.html) trait. |
49 | /// |
50 | /// The primary use case for this method is when one wants to perform case |
51 | /// analysis over an `Hir` without using a stack size proportional to the depth |
52 | /// of the `Hir`. Namely, this method will instead use constant stack space, |
53 | /// but will use heap space proportional to the size of the `Hir`. This may be |
54 | /// desirable in cases where the size of `Hir` is proportional to end user |
55 | /// input. |
56 | /// |
57 | /// If the visitor returns an error at any point, then visiting is stopped and |
58 | /// the error is returned. |
59 | pub fn visit<V: Visitor>(hir: &Hir, visitor: V) -> Result<V::Output, V::Err> { |
60 | HeapVisitor::new().visit(hir, visitor) |
61 | } |
62 | |
63 | /// HeapVisitor visits every item in an `Hir` recursively using constant stack |
64 | /// size and a heap size proportional to the size of the `Hir`. |
65 | struct HeapVisitor<'a> { |
66 | /// A stack of `Hir` nodes. This is roughly analogous to the call stack |
67 | /// used in a typical recursive visitor. |
68 | stack: Vec<(&'a Hir, Frame<'a>)>, |
69 | } |
70 | |
71 | /// Represents a single stack frame while performing structural induction over |
72 | /// an `Hir`. |
73 | enum Frame<'a> { |
74 | /// A stack frame allocated just before descending into a repetition |
75 | /// operator's child node. |
76 | Repetition(&'a hir::Repetition), |
77 | /// A stack frame allocated just before descending into a group's child |
78 | /// node. |
79 | Group(&'a hir::Group), |
80 | /// The stack frame used while visiting every child node of a concatenation |
81 | /// of expressions. |
82 | Concat { |
83 | /// The child node we are currently visiting. |
84 | head: &'a Hir, |
85 | /// The remaining child nodes to visit (which may be empty). |
86 | tail: &'a [Hir], |
87 | }, |
88 | /// The stack frame used while visiting every child node of an alternation |
89 | /// of expressions. |
90 | Alternation { |
91 | /// The child node we are currently visiting. |
92 | head: &'a Hir, |
93 | /// The remaining child nodes to visit (which may be empty). |
94 | tail: &'a [Hir], |
95 | }, |
96 | } |
97 | |
98 | impl<'a> HeapVisitor<'a> { |
99 | fn new() -> HeapVisitor<'a> { |
100 | HeapVisitor { stack: vec![] } |
101 | } |
102 | |
103 | fn visit<V: Visitor>( |
104 | &mut self, |
105 | mut hir: &'a Hir, |
106 | mut visitor: V, |
107 | ) -> Result<V::Output, V::Err> { |
108 | self.stack.clear(); |
109 | |
110 | visitor.start(); |
111 | loop { |
112 | visitor.visit_pre(hir)?; |
113 | if let Some(x) = self.induct(hir) { |
114 | let child = x.child(); |
115 | self.stack.push((hir, x)); |
116 | hir = child; |
117 | continue; |
118 | } |
119 | // No induction means we have a base case, so we can post visit |
120 | // it now. |
121 | visitor.visit_post(hir)?; |
122 | |
123 | // At this point, we now try to pop our call stack until it is |
124 | // either empty or we hit another inductive case. |
125 | loop { |
126 | let (post_hir, frame) = match self.stack.pop() { |
127 | None => return visitor.finish(), |
128 | Some((post_hir, frame)) => (post_hir, frame), |
129 | }; |
130 | // If this is a concat/alternate, then we might have additional |
131 | // inductive steps to process. |
132 | if let Some(x) = self.pop(frame) { |
133 | if let Frame::Alternation { .. } = x { |
134 | visitor.visit_alternation_in()?; |
135 | } |
136 | hir = x.child(); |
137 | self.stack.push((post_hir, x)); |
138 | break; |
139 | } |
140 | // Otherwise, we've finished visiting all the child nodes for |
141 | // this HIR, so we can post visit it now. |
142 | visitor.visit_post(post_hir)?; |
143 | } |
144 | } |
145 | } |
146 | |
147 | /// Build a stack frame for the given HIR if one is needed (which occurs if |
148 | /// and only if there are child nodes in the HIR). Otherwise, return None. |
149 | fn induct(&mut self, hir: &'a Hir) -> Option<Frame<'a>> { |
150 | match *hir.kind() { |
151 | HirKind::Repetition(ref x) => Some(Frame::Repetition(x)), |
152 | HirKind::Group(ref x) => Some(Frame::Group(x)), |
153 | HirKind::Concat(ref x) if x.is_empty() => None, |
154 | HirKind::Concat(ref x) => { |
155 | Some(Frame::Concat { head: &x[0], tail: &x[1..] }) |
156 | } |
157 | HirKind::Alternation(ref x) if x.is_empty() => None, |
158 | HirKind::Alternation(ref x) => { |
159 | Some(Frame::Alternation { head: &x[0], tail: &x[1..] }) |
160 | } |
161 | _ => None, |
162 | } |
163 | } |
164 | |
165 | /// Pops the given frame. If the frame has an additional inductive step, |
166 | /// then return it, otherwise return `None`. |
167 | fn pop(&self, induct: Frame<'a>) -> Option<Frame<'a>> { |
168 | match induct { |
169 | Frame::Repetition(_) => None, |
170 | Frame::Group(_) => None, |
171 | Frame::Concat { tail, .. } => { |
172 | if tail.is_empty() { |
173 | None |
174 | } else { |
175 | Some(Frame::Concat { head: &tail[0], tail: &tail[1..] }) |
176 | } |
177 | } |
178 | Frame::Alternation { tail, .. } => { |
179 | if tail.is_empty() { |
180 | None |
181 | } else { |
182 | Some(Frame::Alternation { |
183 | head: &tail[0], |
184 | tail: &tail[1..], |
185 | }) |
186 | } |
187 | } |
188 | } |
189 | } |
190 | } |
191 | |
192 | impl<'a> Frame<'a> { |
193 | /// Perform the next inductive step on this frame and return the next |
194 | /// child HIR node to visit. |
195 | fn child(&self) -> &'a Hir { |
196 | match *self { |
197 | Frame::Repetition(rep: &Repetition) => &rep.hir, |
198 | Frame::Group(group: &Group) => &group.hir, |
199 | Frame::Concat { head: &Hir, .. } => head, |
200 | Frame::Alternation { head: &Hir, .. } => head, |
201 | } |
202 | } |
203 | } |
204 | |