You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Computing metrics takes hours on files with very deep syntax trees #1258
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>>.
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).
Activity
Exclude two slow files from the grammar check tasks
Exclude two slow files from the grammar check tasks
Look up parents in a map when computing metrics