/build/cargo-vendor-dir/regex-syntax-0.8.2/src/hir/visitor.rs

Source (jump to first uncovered line)
use alloc::{vec, vec::Vec};

use crate::hir::{self, Hir, HirKind};

/// A trait for visiting the high-level IR (HIR) in depth first order.
///
/// The principle aim of this trait is to enable callers to perform case
/// analysis on a high-level intermediate representation of a regular
/// expression without necessarily using recursion. In particular, this permits
/// callers to do case analysis with constant stack usage, which can be
/// important since the size of an HIR may be proportional to end user input.
///
/// Typical usage of this trait involves providing an implementation and then
/// running it using the [`visit`] function.
pub trait Visitor {
    /// The result of visiting an HIR.
    type Output;
    /// An error that visiting an HIR might return.
    type Err;

    /// All implementors of `Visitor` must provide a `finish` method, which
    /// yields the result of visiting the HIR or an error.
    fn finish(self) -> Result<Self::Output, Self::Err>;

    /// This method is called before beginning traversal of the HIR.
    fn start(&mut self) {}

    /// This method is called on an `Hir` before descending into child `Hir`
    /// nodes.
    fn visit_pre(&mut self, _hir: &Hir) -> Result<(), Self::Err> {
        Ok(())
    }

    /// This method is called on an `Hir` after descending all of its child
    /// `Hir` nodes.
    fn visit_post(&mut self, _hir: &Hir) -> Result<(), Self::Err> {
        Ok(())
    }

    /// This method is called between child nodes of an alternation.
    fn visit_alternation_in(&mut self) -> Result<(), Self::Err> {
        Ok(())
    }

    /// This method is called between child nodes of a concatenation.
    fn visit_concat_in(&mut self) -> Result<(), Self::Err> {
        Ok(())
    }
}

/// Executes an implementation of `Visitor` in constant stack space.
///
/// This function will visit every node in the given `Hir` while calling
/// appropriate methods provided by the [`Visitor`] trait.
///
/// The primary use case for this method is when one wants to perform case
/// analysis over an `Hir` without using a stack size proportional to the depth
/// of the `Hir`. Namely, this method will instead use constant stack space,
/// but will use heap space proportional to the size of the `Hir`. This may be
/// desirable in cases where the size of `Hir` is proportional to end user
/// input.
///
/// If the visitor returns an error at any point, then visiting is stopped and
/// the error is returned.
pub fn visit<V: Visitor>(hir: &Hir, visitor: V) -> Result<V::Output, V::Err> {
    HeapVisitor::new().visit(hir, visitor)
}

/// HeapVisitor visits every item in an `Hir` recursively using constant stack
/// size and a heap size proportional to the size of the `Hir`.
struct HeapVisitor<'a> {
    /// A stack of `Hir` nodes. This is roughly analogous to the call stack
    /// used in a typical recursive visitor.
    stack: Vec<(&'a Hir, Frame<'a>)>,
}

/// Represents a single stack frame while performing structural induction over
/// an `Hir`.
enum Frame<'a> {
    /// A stack frame allocated just before descending into a repetition
    /// operator's child node.
    Repetition(&'a hir::Repetition),
    /// A stack frame allocated just before descending into a capture's child
    /// node.
    Capture(&'a hir::Capture),
    /// The stack frame used while visiting every child node of a concatenation
    /// of expressions.
    Concat {
        /// The child node we are currently visiting.
        head: &'a Hir,
        /// The remaining child nodes to visit (which may be empty).
        tail: &'a [Hir],
    },
    /// The stack frame used while visiting every child node of an alternation
    /// of expressions.
    Alternation {
        /// The child node we are currently visiting.
        head: &'a Hir,
        /// The remaining child nodes to visit (which may be empty).
        tail: &'a [Hir],
    },
}

impl<'a> HeapVisitor<'a> {
    fn new() -> HeapVisitor<'a> {
        HeapVisitor { stack: vec![] }
    }

    fn visit<V: Visitor>(
        &mut self,
        mut hir: &'a Hir,
        mut visitor: V,
    ) -> Result<V::Output, V::Err> {
        self.stack.clear();

        visitor.start();
        loop {
            visitor.visit_pre(hir)?;
            if let Some(x) = self.induct(hir) {
                let child = x.child();
                self.stack.push((hir, x));
                hir = child;
                continue;
            }
            // No induction means we have a base case, so we can post visit
            // it now.
            visitor.visit_post(hir)?;

            // At this point, we now try to pop our call stack until it is
            // either empty or we hit another inductive case.
            loop {
                let (post_hir, frame) = match self.stack.pop() {
                    None => return visitor.finish(),
                    Some((post_hir, frame)) => (post_hir, frame),
                };
                // If this is a concat/alternate, then we might have additional
                // inductive steps to process.
                if let Some(x) = self.pop(frame) {
                    match x {
                        Frame::Alternation { .. } => {
                            visitor.visit_alternation_in()?;
                        }
                        Frame::Concat { .. } => {
                            visitor.visit_concat_in()?;
                        }
                        _ => {}
                    }
                    hir = x.child();
                    self.stack.push((post_hir, x));
                    break;
                }
                // Otherwise, we've finished visiting all the child nodes for
                // this HIR, so we can post visit it now.
                visitor.visit_post(post_hir)?;
            }
        }
    }

    /// Build a stack frame for the given HIR if one is needed (which occurs if
    /// and only if there are child nodes in the HIR). Otherwise, return None.
    fn induct(&mut self, hir: &'a Hir) -> Option<Frame<'a>> {
        match *hir.kind() {
            HirKind::Repetition(ref x) => Some(Frame::Repetition(x)),
            HirKind::Capture(ref x) => Some(Frame::Capture(x)),
            HirKind::Concat(ref x) if x.is_empty() => None,
            HirKind::Concat(ref x) => {
                Some(Frame::Concat { head: &x[0], tail: &x[1..] })
            }
            HirKind::Alternation(ref x) if x.is_empty() => None,
            HirKind::Alternation(ref x) => {
                Some(Frame::Alternation { head: &x[0], tail: &x[1..] })
            }
            _ => None,
        }
    }

    /// Pops the given frame. If the frame has an additional inductive step,
    /// then return it, otherwise return `None`.
    fn pop(&self, induct: Frame<'a>) -> Option<Frame<'a>> {
        match induct {
            Frame::Repetition(_) => None,
            Frame::Capture(_) => None,
            Frame::Concat { tail, .. } => {
                if tail.is_empty() {
                    None
                } else {
                    Some(Frame::Concat { head: &tail[0], tail: &tail[1..] })
                }
            }
            Frame::Alternation { tail, .. } => {
                if tail.is_empty() {
                    None
                } else {
                    Some(Frame::Alternation {
                        head: &tail[0],
                        tail: &tail[1..],
                    })
                }
            }
        }
    }
}

impl<'a> Frame<'a> {
    /// Perform the next inductive step on this frame and return the next
    /// child HIR node to visit.
    fn child(&self) -> &'a Hir {
        match *self {
            Frame::Repetition(rep) => &rep.sub,
            Frame::Capture(capture) => &capture.sub,
            Frame::Concat { head, .. } => head,
            Frame::Alternation { head, .. } => head,
        }
    }
}

Coverage Report

Created: 2024-11-19 11:03

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