Module traversal

Traverse Node AST

ast-grep supports common tree traversal algorithms, including

• Pre order traversal
• Post order traversal
• Level order traversal

Note tree traversal can also be used with Matcher. A traversal with Matcher will produce a NodeMatch sequence where all items satisfies the Matcher.

It is also possible to specify the reentrancy of a traversal. That is, we can control whether a matching node should be visited when it is nested within another match. For example, suppose we want to find all usages of calling foo in the source foo(foo()). The code has two matching calls and we can configure a traversal to report only the inner one, only the outer one or both.

Pre and Post order traversals in this module are implemented using tree-sitter’s cursor API without extra heap allocation. It is recommended to use traversal instead of tree recursion to avoid stack overflow and memory overhead. Level order is also included for completeness and should be used sparingly.

Structs

Level

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.

Post

Represents a post-order traversal

PostOrder

Pre

Represents a pre-order traversal

PreOrder

Visit

Visitor

Traits

Algorithm

Traversal

Traversal can iterate over node by using traversal algorithm. The next method should only handle normal, reentrant iteration. If reentrancy is not desired, traversal should mutate cursor in calibrate_for_match. Visit will maintain the matched node depth so traversal does not need to use extra field.