Skip to content

Computing metrics takes hours on files with very deep syntax trees #1258

Closed

Description

@marco-c

Computing metrics never finishes in practice on some files that tree-sitter parses into very deep trees. This is why the "check tree-sitter-mozcpp" CI task never completes: it processes ~40k mozilla-central C/C++ files in ~20 minutes, then stays stuck on the last two for hours until it hits its deadline (e.g. this run).

Affected files

Both are in mozilla-central and are generated by gperf:

File Why the tree is deep
security/manager/ssl/nsSTSPreloadList.inc Its body is a gperf input: ~125k domain.example, 0/1 lines between %% markers. Parsed as C++, they become a single nested expression chain, ~6,900 levels deep (a typical file like dom/base/Document.cpp is ~35).
third_party/wasm2c/src/prebuilt/lexer-keywords.cc gperf output with 613 #line directives inside the wordlist[] array initializer. The grammar can't place them there, so error recovery nests nodes.

Parsing is fast (~0.6s for lexer-keywords.cc with --find/--function). Only --metrics hangs; neither file finished within 2 minutes, while every other C/C++ file in mozilla-central takes at most a few seconds.

Cause

Node::parent() is not O(1): tree-sitter's ts_node_parent walks down from the root (ts_node_child_with_descendant), so each call costs O(depth). Several metrics walk up through all the ancestors of a node with repeated parent() calls, which costs O(depth²) per node:

  • Node::count_specific_ancestors, used by the C++ Declaration case of the LOC metric (src/metrics/loc.rs), which walks up to the root for every top-level declaration, as well as by the Java LOC metric, the Python cognitive metric and the JS-like function checks in src/checker.rs;
  • increment_function_depth in src/metrics/cognitive.rs.

Backtraces of the stuck process show it in ts_node_parent → ts_node_child_with_descendant, called from rust_code_analysis::spaces::metrics::<Parser<CppCode>>.

Reproduce

rust-code-analysis-cli -m -O json -p /path/to/mozilla-central/third_party/wasm2c/src/prebuilt/lexer-keywords.cc

Possible fix

spaces::metrics already visits every node from an explicit stack, so it could record each node's parent during the traversal and make Node::parent() (and therefore the ancestor walks) O(1) per step instead of O(depth).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    Priority

    None yet

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions