Repository navigation
graphify update never finishes on TypeScript projects: _apply_symbol_resolution_facts is O(imports × edges) #4905
Description
What happened?
graphify update . never finishes on a mid-size TypeScript project. It stays at 100% of one core after AST extraction: 100%, with no error and no output. This happens on every run, even after a one-line change, so the graph can't be kept up to date.
The cause is a nested loop in _apply_symbol_resolution_facts (graphify/extractors/resolution.py, around line 1406, unchanged on v8). For each JS/TS import fact it walks all edges and builds a Path for each one, so the cost is imports × edges:
for fact in facts.imports:
...
for edge in edges:
if _js_source_path(str(edge.get("source_file") or ""), root) != source_path:
continueSampling the main thread showed it on line 1407 at 120, 135 and 150 seconds.
Steps to reproduce
Self-contained script. It generates n TypeScript files, each with 10 imports, and times extract():
# python repro.py <n_files>
import shutil, sys, tempfile, time
from pathlib import Path
def main():
n = int(sys.argv[1])
root = Path(tempfile.mkdtemp(prefix="gfy-repro-"))
(root / "src").mkdir()
for i in range(n):
lines = [f'import {{ f{(i + k) % n}_{k} }} from "./m{(i + k) % n}";' for k in range(1, 11)]
lines += [f"export function f{i}_{k}() {{ return 1; }}" for k in range(1, 11)]
lines.append("export const all = () => [" + ", ".join(f"f{(i + k) % n}_{k}()" for k in range(1, 11)) + "];")
(root / "src" / f"m{i}.ts").write_text("\n".join(lines) + "\n")
from graphify.extract import extract
t = time.time()
r = extract(sorted((root / "src").glob("*.ts")), cache_root=root, root=root)
print(f"n={n}: {time.time() - t:.1f}s, {len(r['nodes'])} nodes, {len(r['edges'])} edges")
shutil.rmtree(root, ignore_errors=True)
if __name__ == "__main__":
main()Error output or graph output
There is no error. Timings from the script above:
| Files | Edges | 0.9.99 | With the change below |
|---|---|---|---|
| 200 | 8,200 | 35.2 s | 1.6 s |
| 400 | 16,400 | 141.6 s | 1.9 s |
| 800 | 32,800 | not finished at 60 s (cut off) | 3.1 s |
Doubling the files multiplies the time by 4.
On a real private repository (1,922 files, about 96,700 edges, roughly 970 TS/TSX), the run was still going when stopped after 14 minutes. With the change below the same run takes 39 seconds.
Suggested fix
Index the references edges by source file once, before the loop. The filters are the same and only the lookup changes:
node_by_id = {node.get("id"): node for node in nodes}
+ references_by_file: dict[Path | None, list[dict]] = {}
+ for edge in edges:
+ if edge.get("relation") == "references":
+ references_by_file.setdefault(
+ _js_source_path(str(edge.get("source_file") or ""), root), []
+ ).append(edge)
for fact in facts.imports:
...
- for edge in edges:
- if _js_source_path(str(edge.get("source_file") or ""), root) != source_path:
- continue
- if edge.get("relation") != "references":
- continue
+ for edge in references_by_file.get(source_path, ()):
if edge.get("target") == target_nid:
continueThe loop only changes edge["target"], not source_file or relation, so the index stays valid while it runs.
On a generated 120-file project, the sorted node ids and (source, target, relation) edges were identical with and without the change (same SHA-256). That is the only equivalence check I ran. I did not run the project's test suite.
Graphify version
0.9.99
Operating System
macOS 27.2 (arm64)
Python Version
3.14
Installation Method
pip (Homebrew Python)
Additional context
Reproduced with the script above and on the private repository, both from a clean run with no cache. Found and measured with the help of Claude Code.
Activity
github-actions commentedon Oct 31, 2026
Thanks for opening this issue, @KlevisGolemi. A maintainer will take a look soon.
If you would like to discuss it in real time, come say hi on our Discord server. For longer-form questions and ideas there is also GitHub Discussions.
To help us triage, please make sure the report includes what you expected, what actually happened, and the steps (and a small sample) to reproduce it.
Mohamed-Abderrahmane commentedon Oct 31, 2026
Second data point, on another private TypeScript repository (macOS Intel, Python 3.14, graphifyy 0.9.99 + tree_sitter_sql 0.3.11), measured on a copy of the repo so the live graph was never touched:
import/export … from './…'statements (150 of them multi-line) importing 6,511 names, plus 520.sqlfiles.graphify update .with no change: 2 s (No relevant changes), so the skip gate itself is fine.graphify update .after adding one comment line tosrc/index.ts: 2,518 s (42 min), verdictNo code-graph topology changes._apply_symbol_resolution_facts→_js_source_path→_resolve_cached, i.e. thefor edge in edgesloop underfor fact in facts.imports(resolution.py:1406-1407in 0.9.99). On this machine_js_source_pathcosts about 9.7 µs per call with a warmlru_cache; 6,511 × 55,454 × 9.7 µs ≈ 3,500 s is an upper bound (facts whose target is not found skip the inner loop, and the number that do reach it was not counted), of the same order as the measured run.tree_sitter_sql(SQL files skipped, 10,626 nodes): 16 min 14 s, and 15 min 46 s on a second run with nothing changed. Same loop, fewer edges. (The no-change run was not short there because the 520.sqlfiles never get a manifest entry without the optional grammar, so_inputs_unchangednever matches; a separate, smaller matter.)#4854block, rebuilds the same repo in 54 s cold / 42 s warm.So the cost is paid on every real update whatever the size of the change, which rules out running
updatefrom a session hook with a timeout. The by-source-file index in #4907 is exactly where the profile points; happy to re-time on this repo once it lands.Edited: import counts corrected (the first count was a single-line grep and missed multi-line import statements; 3,194 / 5,100 → 3,361 / 6,511), and the arithmetic reworded as an upper bound.