#2825·ast-grep

perf(outline): add per-rule stopBy traversal bounds

Author: HerringtonDarkholmeCreated Jul 20, 2026Updated Jul 24, 2026

Background

After improving parser performance (including testing with the custom optimized tree-sitter build), outline tree traversal became a more visible part of ast-grep outline runtime. Profiling identified outline traversal as a meaningful hotspot: the traversal currently considers retained item rules throughout the file tree, and member rules throughout the matched item's subtree, even when a rule can only validly match nodes directly owned by its source node.

The source node should be defined by extractor role:

  • item rule: the file's root AST node
  • member rule: the enclosing item matched by the parent item extractor

An experiment that marked root-owned TypeScript/TSX export and namespace/container item rules as immediate showed a material improvement on the opencode repository in exports mode. Using the optimized parser build, canonical output remained identical (1,455 files and 7,575 items), while median wall time fell from 174.6 ms to 151.8 ms (13.1%) and user CPU fell from 1.551 s to 1.333 s (14.1%).

A blanket immediate conversion is not correct, however. The TypeScript compiler corpus contains legacy syntax and intentionally malformed/error-recovery fixtures where candidates occur below wrapper nodes. Those cases demonstrated that traversal bounds must be declared per extractor and must coexist correctly with rules that still require deep traversal.

Requirements

  1. Allow both item and member outline rules to be annotated with stopBy.

    • Support at least stopBy: end and stopBy: immediate.
    • Preserve current behavior by defaulting omitted stopBy to end.
    • For an item rule, evaluate the boundary relative to the file root AST node.
    • For a member rule, evaluate the boundary relative to the enclosing matched item.
  2. A rule with stopBy: immediate must not participate when visiting non-immediate descendants of its source node.

    • In a mixed rule set, end rules must continue to participate below direct children.
    • Rule ordering/precedence at eligible nodes should remain unchanged.
  3. If all active rules for a traversal scope are immediate, do not descend beyond the source node's direct children.

    • For item traversal, determine this from the retained item rules after outline options have filtered the rule set.
    • For member traversal, determine this from the member rules applicable to the enclosing item's rule ID and the active member options.

Acceptance criteria

  • Add schema/deserialization coverage for item and member stopBy, including the default.
  • Add traversal tests for immediate-only and mixed immediate/end item rules.
  • Add equivalent tests for member rules scoped to an enclosing item.
  • Verify that an immediate-only scope prunes descendant traversal rather than merely skipping matcher evaluation.
  • Annotate only bundled rules whose matched candidate is directly owned by the role's source node.
  • Benchmark ast-grep outline --items exports on opencode and confirm output equivalence against stopBy: end rules.
  • Check the TypeScript corpus separately and document any remaining legacy/error-recovery cases before changing additional bundled rules to immediate.