1 use hir
::{self, Hir, HirKind}
;
3 /// A trait for visiting the high-level IR (HIR) in depth first order.
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.
11 /// Typical usage of this trait involves providing an implementation and then
12 /// running it using the [`visit`](fn.visit.html) function.
14 /// The result of visiting an HIR.
16 /// An error that visiting an HIR might return.
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
>;
23 /// This method is called before beginning traversal of the HIR.
24 fn start(&mut self) {}
26 /// This method is called on an `Hir` before descending into child `Hir`
28 fn visit_pre(&mut self, _hir
: &Hir
) -> Result
<(), Self::Err
> {
32 /// This method is called on an `Hir` after descending all of its child
34 fn visit_post(&mut self, _hir
: &Hir
) -> Result
<(), Self::Err
> {
38 /// This method is called between child nodes of an alternation.
39 fn visit_alternation_in(&mut self) -> Result
<(), Self::Err
> {
44 /// Executes an implementation of `Visitor` in constant stack space.
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.
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
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
)
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
>)>,
71 /// Represents a single stack frame while performing structural induction over
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
79 Group(&'a hir
::Group
),
80 /// The stack frame used while visiting every child node of a concatenation
83 /// The child node we are currently visiting.
85 /// The remaining child nodes to visit (which may be empty).
88 /// The stack frame used while visiting every child node of an alternation
91 /// The child node we are currently visiting.
93 /// The remaining child nodes to visit (which may be empty).
98 impl<'a
> HeapVisitor
<'a
> {
99 fn new() -> HeapVisitor
<'a
> {
100 HeapVisitor { stack: vec![] }
103 fn visit
<V
: Visitor
>(
107 ) -> Result
<V
::Output
, V
::Err
> {
112 visitor
.visit_pre(hir
)?
;
113 if let Some(x
) = self.induct(hir
) {
114 let child
= x
.child();
115 self.stack
.push((hir
, x
));
119 // No induction means we have a base case, so we can post visit
121 visitor
.visit_post(hir
)?
;
123 // At this point, we now try to pop our call stack until it is
124 // either empty or we hit another inductive case.
126 let (post_hir
, frame
) = match self.stack
.pop() {
127 None
=> return visitor
.finish(),
128 Some((post_hir
, frame
)) => (post_hir
, frame
),
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()?
;
137 self.stack
.push((post_hir
, x
));
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
)?
;
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
>> {
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..] }
)
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..] }
)
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
>> {
169 Frame
::Repetition(_
) => None
,
170 Frame
::Group(_
) => None
,
171 Frame
::Concat { tail, .. }
=> {
175 Some(Frame
::Concat { head: &tail[0], tail: &tail[1..] }
)
178 Frame
::Alternation { tail, .. }
=> {
182 Some(Frame
::Alternation
{
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
{
197 Frame
::Repetition(rep
) => &rep
.hir
,
198 Frame
::Group(group
) => &group
.hir
,
199 Frame
::Concat { head, .. }
=> head
,
200 Frame
::Alternation { head, .. }
=> head
,