Module ast_grep_core::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.