Module traversal 

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:

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()

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.

Structs

Level

Represents a level-order traversal.

Post

Represents a post-order traversal

PostOrder

Post-order traversal algorithm.

Pre

PreOrder

Pre-order traversal algorithm.

TsPre

Represents a pre-order traversal

Visit

Visitor

Configurable tree visitor that combines traversal algorithms with pattern matching.

Traits

Algorithm

Trait for tree traversal algorithms.

Traversal

Core trait for tree traversal implementations.