thread-ast-engine 0.1.1

// SPDX-FileCopyrightText: 2022 Herrington Darkholme <2883231+HerringtonDarkholme@users.noreply.github.com>
// SPDX-FileCopyrightText: 2025 Knitli Inc. <knitli@knit.li>
// SPDX-FileContributor: Adam Poulemanos <adam@knit.li>
//
// SPDX-License-Identifier: AGPL-3.0-or-later AND MIT

//! # AST Tree Traversal Algorithms
//!
//! Efficient tree traversal implementations for navigating and processing AST nodes.
//! Provides multiple traversal strategies optimized for different use cases, with
//! built-in support for pattern matching and reentrancy control.
//!
//! ## Traversal Algorithms
//!
//! - **Pre-order**: Visit parent before children (useful for top-down processing)
//! - **Post-order**: Visit children before parent (useful for bottom-up processing)
//! - **Level-order**: Visit nodes level by level (breadth-first search)
//!
//! ## Key Features
//!
//! ### Pattern-Based Traversal
//!
//! Combine traversal with pattern matching to find specific nodes efficiently:
//!
//! ```rust,no_run
//! # use thread_ast_engine::tree_sitter::traversal::Visitor;
//! # use thread_ast_engine::Language;
//! # use thread_ast_engine::tree_sitter::LanguageExt;
//! # struct Tsx;
//! # impl thread_ast_engine::Language for Tsx {
//! #     fn kind_to_id(&self, _: &str) -> u16 { 0 }
//! #     fn field_to_id(&self, _: &str) -> Option<u16> { None }
//! #     fn build_pattern(&self, _: &thread_ast_engine::PatternBuilder) -> Result<thread_ast_engine::Pattern, thread_ast_engine::PatternError> { todo!() }
//! # }
//! # impl LanguageExt for Tsx {
//! #     fn get_ts_language(&self) -> thread_ast_engine::tree_sitter::TSLanguage { todo!() }
//! # }
//! let ast = Tsx.ast_grep("function foo() { foo(); }");
//! let root = ast.root();
//!
//! // Find all function calls
//! for call in Visitor::new("$FUNC()").visit(root) {
//!     println!("Found call: {}", call.get_node().text());
//! }
//! ```
//!
//! ### Reentrancy Control
//!
//! Control whether nested matches should be reported. For example, when finding
//! function calls in `foo(bar(baz()))`, you can choose to find:
//! - Only outer calls: `foo(...)`
//! - Only inner calls: `bar(...)`, `baz()`
//! - All calls: `foo(...)`, `bar(...)`, `baz()`
//!
//! ```rust,no_run
//! # use thread_ast_engine::tree_sitter::traversal::Visitor;
//! # use thread_ast_engine::Language;
//! # use thread_ast_engine::tree_sitter::LanguageExt;
//! # struct Tsx;
//! # impl thread_ast_engine::Language for Tsx {
//! #     fn kind_to_id(&self, _: &str) -> u16 { 0 }
//! #     fn field_to_id(&self, _: &str) -> Option<u16> { None }
//! #     fn build_pattern(&self, _: &thread_ast_engine::PatternBuilder) -> Result<thread_ast_engine::Pattern, thread_ast_engine::PatternError> { todo!() }
//! # }
//! # impl LanguageExt for Tsx {
//! #     fn get_ts_language(&self) -> thread_ast_engine::tree_sitter::TSLanguage { todo!() }
//! # }
//! let ast = Tsx.ast_grep("foo(bar())");
//! let root = ast.root();
//!
//! // Non-reentrant: only finds outer matches
//! let outer_only: Vec<_> = Visitor::new("$FUNC($$$)")
//!     .reentrant(false)
//!     .visit(root)
//!     .collect();
//!
//! // Reentrant: finds all matches including nested ones
//! let all_matches: Vec<_> = Visitor::new("$FUNC($$$)")
//!     .reentrant(true)
//!     .visit(root)
//!     .collect();
//! ```
//!
//! ## Performance
//!
//! - **Pre/Post-order**: Use tree-sitter's cursor API with O(1) memory overhead
//! - **Level-order**: Uses a queue with O(width) memory, use sparingly for large trees
//! - **Stack-safe**: All traversals avoid recursion to prevent stack overflow
//!
//! Prefer traversal over manual recursion for performance and safety.

use super::StrDoc;
use crate::tree_sitter::LanguageExt;
use crate::{Doc, Matcher, Node, Root};
#[cfg(feature = "matching")]
use crate::{MatcherExt, NodeMatch};

use tree_sitter as ts;

use std::collections::VecDeque;
use std::marker::PhantomData;

/// Configurable tree visitor that combines traversal algorithms with pattern matching.
///
/// `Visitor` allows you to traverse an AST while filtering nodes based on patterns.
/// It supports different traversal algorithms and provides fine-grained control
/// over matching behavior through reentrancy and node type filtering.
///
/// # Type Parameters
///
/// - `M: Matcher` - The pattern matcher to filter nodes
/// - `A` - The traversal algorithm (defaults to [`PreOrder`])
///
/// # Example
///
/// ```rust,no_run
/// # use thread_ast_engine::tree_sitter::traversal::Visitor;
/// # use thread_ast_engine::Language;
/// # use thread_ast_engine::tree_sitter::LanguageExt;
/// # struct Tsx;
/// # impl thread_ast_engine::Language for Tsx {
/// #     fn kind_to_id(&self, _: &str) -> u16 { 0 }
/// #     fn field_to_id(&self, _: &str) -> Option<u16> { None }
/// #     fn build_pattern(&self, _: &thread_ast_engine::PatternBuilder) -> Result<thread_ast_engine::Pattern, thread_ast_engine::PatternError> { todo!() }
/// # }
/// # impl LanguageExt for Tsx {
/// #     fn get_ts_language(&self) -> thread_ast_engine::tree_sitter::TSLanguage { todo!() }
/// # }
/// let ast = Tsx.ast_grep("let x = foo(); let y = bar();");
/// let root = ast.root();
///
/// // Find all identifiers, visiting only named nodes
/// let identifiers: Vec<_> = Visitor::new("$ID")
///     .named_only(true)
///     .reentrant(false)
///     .visit(root)
///     .collect();
/// ```
pub struct Visitor<M, A = PreOrder> {
    /// Whether nested matches should be reported (true) or skipped (false)
    reentrant: bool,
    /// Whether to visit only named AST nodes, skipping anonymous syntax tokens
    named_only: bool,
    /// Pattern matcher used to filter nodes during traversal
    matcher: M,
    /// Traversal algorithm type marker (pre-order, post-order, level-order)
    algorithm: PhantomData<A>,
}

impl<M> Visitor<M> {
    pub const fn new(matcher: M) -> Self {
        Self {
            reentrant: true,
            named_only: false,
            matcher,
            algorithm: PhantomData,
        }
    }
}

impl<M, A> Visitor<M, A> {
    pub fn algorithm<Algo>(self) -> Visitor<M, Algo> {
        Visitor {
            reentrant: self.reentrant,
            named_only: self.named_only,
            matcher: self.matcher,
            algorithm: PhantomData,
        }
    }

    #[must_use]
    pub fn reentrant(self, reentrant: bool) -> Self {
        Self { reentrant, ..self }
    }

    #[must_use]
    pub fn named_only(self, named_only: bool) -> Self {
        Self { named_only, ..self }
    }
}

impl<M, A> Visitor<M, A>
where
    A: Algorithm,
{
    pub fn visit<L: LanguageExt>(
        self,
        node: Node<'_, StrDoc<L>>,
    ) -> Visit<'_, StrDoc<L>, A::Traversal<'_, L>, M>
    where
        M: Matcher,
    {
        let traversal = A::traverse(node);
        Visit {
            reentrant: self.reentrant,
            named: self.named_only,
            matcher: self.matcher,
            traversal,
            lang: PhantomData,
        }
    }
}

#[cfg_attr(not(feature = "matching"), allow(dead_code))]
pub struct Visit<'t, D, T, M> {
    reentrant: bool,
    named: bool,
    matcher: M,
    traversal: T,
    lang: PhantomData<&'t D>,
}
impl<'t, D, T, M> Visit<'t, D, T, M>
where
    D: Doc + 't,
    T: Traversal<'t, D>,
    M: Matcher,
{
    #[cfg_attr(feature = "matching", inline)]
    #[cfg_attr(not(feature = "matching"), allow(dead_code))]
    fn mark_match(&mut self, depth: Option<usize>) {
        if !self.reentrant {
            self.traversal.calibrate_for_match(depth);
        }
    }
}

#[cfg(feature = "matching")]
impl<'t, D, T, M> Iterator for Visit<'t, D, T, M>
where
    D: Doc + 't,
    T: Traversal<'t, D>,
    M: Matcher + MatcherExt,
{
    type Item = NodeMatch<'t, D>;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let match_depth = self.traversal.get_current_depth();
            let node = self.traversal.next()?;
            let pass_named = !self.named || node.is_named();
            if let Some(node_match) = pass_named.then(|| self.matcher.match_node(node)).flatten() {
                self.mark_match(Some(match_depth));
                return Some(node_match);
            }
            self.mark_match(None);
        }
    }
}

/// Trait for tree traversal algorithms.
///
/// Defines how to create traversal iterators for different algorithms
/// (pre-order, post-order, level-order). Each algorithm has its own
/// traversal implementation with specific visiting order and performance
/// characteristics.
pub trait Algorithm {
    /// The specific traversal iterator type for this algorithm
    type Traversal<'t, L: LanguageExt>: Traversal<'t, StrDoc<L>>;

    /// Create a traversal iterator starting from the given node
    fn traverse<L: LanguageExt>(node: Node<'_, StrDoc<L>>) -> Self::Traversal<'_, L>;
}

/// Pre-order traversal algorithm.
///
/// Visits parent nodes before their children. Useful for top-down processing
/// where you need to process a node before its descendants.
///
/// **Visit order**: Root → Left subtree → Right subtree
pub struct PreOrder;

impl Algorithm for PreOrder {
    type Traversal<'t, L: LanguageExt> = Pre<'t, L>;
    fn traverse<L: LanguageExt>(node: Node<'_, StrDoc<L>>) -> Self::Traversal<'_, L> {
        Pre::new(&node)
    }
}

/// Post-order traversal algorithm.
///
/// Visits children before their parent. Useful for bottom-up processing
/// where you need to process all descendants before the node itself.
///
/// **Visit order**: Left subtree → Right subtree → Root
pub struct PostOrder;

impl Algorithm for PostOrder {
    type Traversal<'t, L: LanguageExt> = Post<'t, L>;
    fn traverse<L: LanguageExt>(node: Node<'_, StrDoc<L>>) -> Self::Traversal<'_, L> {
        Post::new(&node)
    }
}

/// Core trait for tree traversal implementations.
///
/// Provides the interface for iterating over AST nodes using different algorithms.
/// Supports both reentrant and non-reentrant traversal through calibration methods.
///
/// # Reentrancy Control
///
/// The traversal can be configured to skip nested matches when a pattern is found.
/// The `calibrate_for_match` method is called to adjust the cursor position when
/// matches are found, allowing non-reentrant behavior.
///
/// # Implementation Notes
///
/// - The `next` method handles normal iteration over all nodes
/// - Depth tracking enables proper calibration for non-reentrant traversal
/// - Root node is at depth 0, children are at depth 1, etc.
pub trait Traversal<'t, D: Doc + 't>: Iterator<Item = Node<'t, D>> {
    /// Adjust cursor position to implement non-reentrant matching behavior.
    ///
    /// Called by [`Visit`] to skip overlapping matches when reentrancy is disabled.
    /// If a node matches a pattern, this method can skip its descendants to avoid
    /// finding nested matches.
    ///
    /// # Parameters
    ///
    /// - `depth` - Depth of the matched node if a match was found, `None` otherwise
    fn calibrate_for_match(&mut self, depth: Option<usize>);

    /// Get the current depth in the tree traversal.
    ///
    /// Depth increases by 1 when moving from parent to child nodes.
    /// The root node has depth 0.
    ///
    /// # Returns
    ///
    /// Current traversal depth (0 = root, 1 = root's children, etc.)
    fn get_current_depth(&self) -> usize;
}

/// Represents a pre-order traversal
pub struct TsPre<'tree> {
    cursor: ts::TreeCursor<'tree>,
    // record the starting node, if we return back to starting point
    // we should terminate the dfs.
    start_id: Option<usize>,
    current_depth: usize,
}

impl<'tree> TsPre<'tree> {
    #[must_use]
    pub fn new(node: &ts::Node<'tree>) -> Self {
        Self {
            cursor: node.walk(),
            start_id: Some(node.id()),
            current_depth: 0,
        }
    }
    fn step_down(&mut self) -> bool {
        if self.cursor.goto_first_child() {
            self.current_depth += 1;
            true
        } else {
            false
        }
    }

    // retrace back to ancestors and find next node to explore
    fn trace_up(&mut self, start: usize) {
        let cursor = &mut self.cursor;
        while cursor.node().id() != start {
            // try visit sibling nodes
            if cursor.goto_next_sibling() {
                return;
            }
            self.current_depth -= 1;
            // go back to parent node
            if !cursor.goto_parent() {
                // it should never fail here. However, tree-sitter has bad parsing bugs
                // stop to avoid panic. https://github.com/ast-grep/ast-grep/issues/713
                break;
            }
        }
        // terminate traversal here
        self.start_id = None;
    }
}

/// Amortized time complexity is O(NlgN), depending on branching factor.
impl<'tree> Iterator for TsPre<'tree> {
    type Item = ts::Node<'tree>;
    // 1. Yield the node itself
    // 2. Try visit the child node until no child available
    // 3. Try visit next sibling after going back to parent
    // 4. Repeat step 3 until returning to the starting node
    fn next(&mut self) -> Option<Self::Item> {
        // start_id will always be Some until the dfs terminates
        let start = self.start_id?;
        let cursor = &mut self.cursor;
        let inner = cursor.node(); // get current node
        let ret = Some(inner);
        // try going to children first
        if self.step_down() {
            return ret;
        }
        // if no child available, go to ancestor nodes
        // until we get to the starting point
        self.trace_up(start);
        ret
    }
}

pub struct Pre<'tree, L: LanguageExt> {
    root: &'tree Root<StrDoc<L>>,
    inner: TsPre<'tree>,
}
impl<'tree, L: LanguageExt> Iterator for Pre<'tree, L> {
    type Item = Node<'tree, StrDoc<L>>;
    fn next(&mut self) -> Option<Self::Item> {
        let inner = self.inner.next()?;
        Some(self.root.adopt(inner))
    }
}

impl<'t, L: LanguageExt> Pre<'t, L> {
    #[must_use]
    pub fn new(node: &Node<'t, StrDoc<L>>) -> Self {
        let inner = TsPre::new(&node.inner);
        Self {
            root: node.root,
            inner,
        }
    }
}

impl<'t, L: LanguageExt> Traversal<'t, StrDoc<L>> for Pre<'t, L> {
    fn calibrate_for_match(&mut self, depth: Option<usize>) {
        // not entering the node, ignore
        let Some(depth) = depth else {
            return;
        };
        // if already entering sibling or traced up, ignore
        if self.inner.current_depth <= depth {
            return;
        }
        debug_assert!(self.inner.current_depth > depth);
        if let Some(start) = self.inner.start_id {
            // revert the step down
            self.inner.cursor.goto_parent();
            self.inner.trace_up(start);
        }
    }

    #[inline]
    fn get_current_depth(&self) -> usize {
        self.inner.current_depth
    }
}

/// Represents a post-order traversal
pub struct Post<'tree, L: LanguageExt> {
    cursor: ts::TreeCursor<'tree>,
    root: &'tree Root<StrDoc<L>>,
    start_id: Option<usize>,
    current_depth: usize,
    match_depth: usize,
}

/// Amortized time complexity is O(NlgN), depending on branching factor.
impl<'tree, L: LanguageExt> Post<'tree, L> {
    #[must_use]
    pub fn new(node: &Node<'tree, StrDoc<L>>) -> Self {
        let mut ret = Self {
            cursor: node.inner.walk(),
            root: node.root,
            start_id: Some(node.inner.id()),
            current_depth: 0,
            match_depth: 0,
        };
        ret.trace_down();
        ret
    }
    fn trace_down(&mut self) {
        while self.cursor.goto_first_child() {
            self.current_depth += 1;
        }
    }
    fn step_up(&mut self) {
        self.current_depth -= 1;
        self.cursor.goto_parent();
    }
}

/// Amortized time complexity is O(NlgN), depending on branching factor.
impl<'tree, L: LanguageExt> Iterator for Post<'tree, L> {
    type Item = Node<'tree, StrDoc<L>>;
    fn next(&mut self) -> Option<Self::Item> {
        // start_id will always be Some until the dfs terminates
        let start = self.start_id?;
        let cursor = &mut self.cursor;
        let node = self.root.adopt(cursor.node());
        // return to start
        if node.inner.id() == start {
            self.start_id = None;
        } else if cursor.goto_next_sibling() {
            // try visit sibling
            self.trace_down();
        } else {
            self.step_up();
        }
        Some(node)
    }
}

impl<'t, L: LanguageExt> Traversal<'t, StrDoc<L>> for Post<'t, L> {
    fn calibrate_for_match(&mut self, depth: Option<usize>) {
        if let Some(depth) = depth {
            // Later matches' depth should always be greater than former matches.
            // because we bump match_depth in `step_up` during traversal.
            debug_assert!(depth >= self.match_depth);
            self.match_depth = depth;
            return;
        }
        // found new nodes to explore in trace_down, skip calibration.
        if self.current_depth >= self.match_depth {
            return;
        }
        let Some(start) = self.start_id else {
            return;
        };
        while self.cursor.node().id() != start {
            self.match_depth = self.current_depth;
            if self.cursor.goto_next_sibling() {
                // try visit sibling
                self.trace_down();
                return;
            }
            self.step_up();
        }
        // terminate because all ancestors are skipped
        self.start_id = None;
    }

    #[inline]
    fn get_current_depth(&self) -> usize {
        self.current_depth
    }
}

/// Represents a level-order traversal.
///
/// It is implemented with [`VecDeque`] since quadratic backtracking is too time consuming.
/// Though level-order is not used as frequently as other DFS traversals,
/// traversing a big AST with level-order should be done with caution since it might increase the memory usage.
pub struct Level<'tree, L: LanguageExt> {
    deque: VecDeque<ts::Node<'tree>>,
    cursor: ts::TreeCursor<'tree>,
    root: &'tree Root<StrDoc<L>>,
}

impl<'tree, L: LanguageExt> Level<'tree, L> {
    #[must_use]
    pub fn new(node: &Node<'tree, StrDoc<L>>) -> Self {
        let mut deque = VecDeque::new();
        deque.push_back(node.inner);
        let cursor = node.inner.walk();
        Self {
            deque,
            cursor,
            root: node.root,
        }
    }
}

/// Time complexity is O(N). Space complexity is O(N)
impl<'tree, L: LanguageExt> Iterator for Level<'tree, L> {
    type Item = Node<'tree, StrDoc<L>>;
    fn next(&mut self) -> Option<Self::Item> {
        let inner = self.deque.pop_front()?;
        let children = inner.children(&mut self.cursor);
        self.deque.extend(children);
        Some(self.root.adopt(inner))
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::language::Tsx;
    use std::ops::Range;

    // recursive pre order as baseline
    fn pre_order(node: &Node<StrDoc<Tsx>>) -> Vec<Range<usize>> {
        let mut ret = vec![node.range()];
        ret.extend(node.children().flat_map(|n| pre_order(&n)));
        ret
    }

    // recursion baseline
    fn post_order(node: &Node<StrDoc<Tsx>>) -> Vec<Range<usize>> {
        let mut ret: Vec<_> = node.children().flat_map(|n| post_order(&n)).collect();
        ret.push(node.range());
        ret
    }

    fn pre_order_equivalent(source: &str) {
        let grep = Tsx.ast_grep(source);
        let node = grep.root();
        let iterative: Vec<_> = Pre::new(&node).map(|n| n.range()).collect();
        let recursive = pre_order(&node);
        assert_eq!(iterative, recursive);
    }

    fn post_order_equivalent(source: &str) {
        let grep = Tsx.ast_grep(source);
        let node = grep.root();
        let iterative: Vec<_> = Post::new(&node).map(|n| n.range()).collect();
        let recursive = post_order(&node);
        assert_eq!(iterative, recursive);
    }

    const CASES: &[&str] = &[
        "console.log('hello world')",
        "let a = (a, b, c)",
        "function test() { let a = 1; let b = 2; a === b}",
        "[[[[[[]]]]], 1 , 2 ,3]",
        "class A { test() { class B {} } }",
    ];

    #[test]
    fn tes_pre_order() {
        for case in CASES {
            pre_order_equivalent(case);
        }
    }

    #[test]
    fn test_post_order() {
        for case in CASES {
            post_order_equivalent(case);
        }
    }

    #[test]
    fn test_different_order() {
        for case in CASES {
            let grep = Tsx.ast_grep(case);
            let node = grep.root();
            let pre: Vec<_> = Pre::new(&node).map(|n| n.range()).collect();
            let post: Vec<_> = Post::new(&node).map(|n| n.range()).collect();
            let level: Vec<_> = Level::new(&node).map(|n| n.range()).collect();
            assert_ne!(pre, post);
            assert_ne!(pre, level);
            assert_ne!(post, level);
        }
    }

    #[test]
    fn test_fused_traversal() {
        for case in CASES {
            let grep = Tsx.ast_grep(case);
            let node = grep.root();
            let mut pre = Pre::new(&node);
            let mut post = Post::new(&node);
            while pre.next().is_some() {}
            while post.next().is_some() {}
            assert!(pre.next().is_none());
            assert!(pre.next().is_none());
            assert!(post.next().is_none());
            assert!(post.next().is_none());
        }
    }

    #[test]
    fn test_non_root_traverse() {
        let grep = Tsx.ast_grep("let a = 123; let b = 123;");
        let node = grep.root();
        let pre: Vec<_> = Pre::new(&node).map(|n| n.range()).collect();
        let post: Vec<_> = Post::new(&node).map(|n| n.range()).collect();
        let node2 = node.child(0).unwrap();
        let pre2: Vec<_> = Pre::new(&node2).map(|n| n.range()).collect();
        let post2: Vec<_> = Post::new(&node2).map(|n| n.range()).collect();
        // traversal should stop at node
        assert_ne!(pre, pre2);
        assert_ne!(post, post2);
        // child traversal should be a part of parent traversal
        assert!(pre[1..].starts_with(&pre2));
        assert!(post.starts_with(&post2));
    }

    fn pre_order_with_matcher(node: &Node<StrDoc<Tsx>>, matcher: &str) -> Vec<Range<usize>> {
        if node.matches(matcher) {
            vec![node.range()]
        } else {
            node.children()
                .flat_map(|n| pre_order_with_matcher(&n, matcher))
                .collect()
        }
    }

    fn post_order_with_matcher(node: &Node<StrDoc<Tsx>>, matcher: &str) -> Vec<Range<usize>> {
        let mut ret: Vec<_> = node
            .children()
            .flat_map(|n| post_order_with_matcher(&n, matcher))
            .collect();
        if ret.is_empty() && node.matches(matcher) {
            ret.push(node.range());
        }
        ret
    }

    const MATCHER_CASES: &[&str] = &[
        "Some(123)",
        "Some(1, 2, Some(2))",
        "NoMatch",
        "NoMatch(Some(123))",
        "Some(1, Some(2), Some(3))",
        "Some(1, Some(2), Some(Some(3)))",
    ];

    #[test]
    fn test_pre_order_visitor() {
        let matcher = "Some($$$)";
        for case in MATCHER_CASES {
            let grep = Tsx.ast_grep(case);
            let node = grep.root();
            let recur = pre_order_with_matcher(&node, matcher);
            let visit: Vec<_> = Visitor::new(matcher)
                .reentrant(false)
                .visit(node)
                .map(|n| n.range())
                .collect();
            assert_eq!(recur, visit);
        }
    }
    #[test]
    fn test_post_order_visitor() {
        let matcher = "Some($$$)";
        for case in MATCHER_CASES {
            let grep = Tsx.ast_grep(case);
            let node = grep.root();
            let recur = post_order_with_matcher(&node, matcher);
            let visit: Vec<_> = Visitor::new(matcher)
                .algorithm::<PostOrder>()
                .reentrant(false)
                .visit(node)
                .map(|n| n.range())
                .collect();
            assert_eq!(recur, visit);
        }
    }

    // match a leaf node will trace_up the cursor
    #[test]
    fn test_traversal_leaf() {
        let matcher = "true";
        let case = "((((true))));true";
        let grep = Tsx.ast_grep(case);
        let recur = pre_order_with_matcher(&grep.root(), matcher);
        let visit: Vec<_> = Visitor::new(matcher)
            .reentrant(false)
            .visit(grep.root())
            .map(|n| n.range())
            .collect();
        assert_eq!(recur, visit);
        let recur = post_order_with_matcher(&grep.root(), matcher);
        let visit: Vec<_> = Visitor::new(matcher)
            .algorithm::<PostOrder>()
            .reentrant(false)
            .visit(grep.root())
            .map(|n| n.range())
            .collect();
        assert_eq!(recur, visit);
    }
}