[PR #909] [MERGED] perf(call-path): prune dead ends and enumerate without recursion #2338

New issue

Closed

opened 2026-10-16 21:17:29 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-16 21:17:29 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/909
Author: @morluto
Created: 10/7/2026
Status: ✅ Merged
Merged: 10/7/2026
Merged by: @morluto

Base: main ← Head: codex/call-path-search-audit

📝 Commits (1)

5bd1572 perf(call-path): prune dead ends and enumerate without recursion

📊 Changes

2 files changed (+163 additions, -52 deletions)

View changed files

📝 src/domain/callPath.test.ts (+99 -0)
📝 src/domain/callPath.ts (+64 -52)

📄 Description

Summary

build_call_path now enumerates only edges that can participate in a shortest path and uses an explicit stack. This prevents repeated dead-end exploration and stack overflow while returning every shortest path in the existing order.

Discovered and reproduced during the requested whole-codebase performance audit; there is no separate tracking issue for this finding.

Problem and expected behavior

A graph with 69 supplied functions and one actual shortest path repeatedly explores merging branches that cannot reach the goal. A 20,000-hop chain throws RangeError: Maximum call stack size exceeded. The tool should handle both without dropping paths, citations, or coverage limitations.

Change and scope

Index predecessor edges, compute shortest remaining distances with reverse BFS, and enumerate only edges whose remaining distance decreases by one. Cache sorted eligible neighbors and use explicit traversal frames. Replace the spread-based maximum-depth reduction so graph size does not become an argument-count limit.

Forward evidence inspection remains responsible for explored counts and uncovered reachable functions, including dead ends. Genuine exponentially many shortest paths still require proportional output; this change does not truncate them.

Contract and boundary impact

Semantic owner and earliest changed stage: pure domain call-graph construction/search.
CLI and MCP/tool-catalog contract: no schema or inventory change; existing complete shortest-path results and deterministic order are preserved.
Provider/bridge/platform compatibility: no provider or wire changes.
Evidence/provenance contract: existing citations and exhaustive/unknown classifications preserved.
Process/authorization/cleanup impact: none; operates on supplied Evidence.
Generated metadata/package/installation impact: none.

Evidence and regression coverage

Behavioral regressions cover merged branches and cycles, uncovered dead ends despite a found path, zero-hop paths, a 20,000-hop chain, and a 28-stage merging dead-end graph.
Node 24.18.0/macOS arm64 CPU profiles attribute the baseline dead-end workload primarily to recursive enumeration. With the same input digest and profiling configuration, three-call median for 69 functions fell from 582.02 ms to 3.33 ms. Measurements include Evidence parsing and result validation, excluding fixture construction; they are synthetic function measurements, not end-to-end provider speedups.
The 20,000-hop baseline fails with stack overflow; the candidate returns the sole fully cited path.
300 seeded randomized directed graphs matched baseline results exactly, including cycles, missing dossiers, unreachable goals, and zero-hop paths.
Remaining proof gaps: arbitrary input/output sizes and exponentially large genuine path sets are not benchmarked.
Observed, derived, and inferred claims remain distinguishable.
Artifact identity, source provenance, and failed attempts remain preserved.
Unsupported, incomplete, unavailable, or uncertain outcomes remain visible.

Validation performed

npm run test:focused -- src/domain/callPath.test.ts tests/boundary/mcp/investigationAnalysisMcp.test.ts tests/boundary/mcp/enhancedTools.callPathsAndBatches.test.ts — 23 tests passed in the isolated worktree.
npm run check:fast — typecheck, lint, and module-boundary checks passed.
git diff --check — passed.
Independent standards and behavior reviews — no actionable findings; reviewer reran all 13 domain tests.

Compatibility, safety, and release

Breaking changes/migration: none.
Real Hopper/Ghidra/browser/OS coverage: no real-provider verification; this pure supplied-Evidence workflow does not invoke those providers. Profiling used macOS arm64.
Package/release metadata impact: none.
Safety review: preserves complete output and existing error/evidence semantics; no added execution authority or arbitrary caps.

Review checklist

One focused outcome and Conventional Commit title.
Origin of finding and lack of separate issue explained.
Tests cover changed observable behavior and meaningful failure paths.
No owning docs, contract, or generated metadata changes are needed.
Existing MCP output regressions pass.
Final diff checked for secrets, unrelated edits, and unsupported claims.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/morluto/rea/pull/909 **Author:** [@morluto](https://github.com/morluto) **Created:** 10/7/2026 **Status:** ✅ Merged **Merged:** 10/7/2026 **Merged by:** [@morluto](https://github.com/morluto) **Base:** `main` ← **Head:** `codex/call-path-search-audit` --- ### 📝 Commits (1) - [`5bd1572`](https://github.com/morluto/rea/commit/5bd1572267dbb99b47c520acb21dcb6bb17fe923) perf(call-path): prune dead ends and enumerate without recursion ### 📊 Changes **2 files changed** (+163 additions, -52 deletions) <details> <summary>View changed files</summary> 📝 `src/domain/callPath.test.ts` (+99 -0) 📝 `src/domain/callPath.ts` (+64 -52) </details> ### 📄 Description ## Summary `build_call_path` now enumerates only edges that can participate in a shortest path and uses an explicit stack. This prevents repeated dead-end exploration and stack overflow while returning every shortest path in the existing order. Discovered and reproduced during the requested whole-codebase performance audit; there is no separate tracking issue for this finding. ## Problem and expected behavior A graph with 69 supplied functions and one actual shortest path repeatedly explores merging branches that cannot reach the goal. A 20,000-hop chain throws `RangeError: Maximum call stack size exceeded`. The tool should handle both without dropping paths, citations, or coverage limitations. ## Change and scope Index predecessor edges, compute shortest remaining distances with reverse BFS, and enumerate only edges whose remaining distance decreases by one. Cache sorted eligible neighbors and use explicit traversal frames. Replace the spread-based maximum-depth reduction so graph size does not become an argument-count limit. Forward evidence inspection remains responsible for explored counts and uncovered reachable functions, including dead ends. Genuine exponentially many shortest paths still require proportional output; this change does not truncate them. ## Contract and boundary impact - Semantic owner and earliest changed stage: pure domain call-graph construction/search. - CLI and MCP/tool-catalog contract: no schema or inventory change; existing complete shortest-path results and deterministic order are preserved. - Provider/bridge/platform compatibility: no provider or wire changes. - Evidence/provenance contract: existing citations and exhaustive/unknown classifications preserved. - Process/authorization/cleanup impact: none; operates on supplied Evidence. - Generated metadata/package/installation impact: none. ## Evidence and regression coverage - Behavioral regressions cover merged branches and cycles, uncovered dead ends despite a found path, zero-hop paths, a 20,000-hop chain, and a 28-stage merging dead-end graph. - Node 24.18.0/macOS arm64 CPU profiles attribute the baseline dead-end workload primarily to recursive enumeration. With the same input digest and profiling configuration, three-call median for 69 functions fell from 582.02 ms to 3.33 ms. Measurements include Evidence parsing and result validation, excluding fixture construction; they are synthetic function measurements, not end-to-end provider speedups. - The 20,000-hop baseline fails with stack overflow; the candidate returns the sole fully cited path. - 300 seeded randomized directed graphs matched baseline results exactly, including cycles, missing dossiers, unreachable goals, and zero-hop paths. - Remaining proof gaps: arbitrary input/output sizes and exponentially large genuine path sets are not benchmarked. - [x] Observed, derived, and inferred claims remain distinguishable. - [x] Artifact identity, source provenance, and failed attempts remain preserved. - [x] Unsupported, incomplete, unavailable, or uncertain outcomes remain visible. ## Validation performed - `npm run test:focused -- src/domain/callPath.test.ts tests/boundary/mcp/investigationAnalysisMcp.test.ts tests/boundary/mcp/enhancedTools.callPathsAndBatches.test.ts` — 23 tests passed in the isolated worktree. - `npm run check:fast` — typecheck, lint, and module-boundary checks passed. - `git diff --check` — passed. - Independent standards and behavior reviews — no actionable findings; reviewer reran all 13 domain tests. ## Compatibility, safety, and release - Breaking changes/migration: none. - Real Hopper/Ghidra/browser/OS coverage: no real-provider verification; this pure supplied-Evidence workflow does not invoke those providers. Profiling used macOS arm64. - Package/release metadata impact: none. - Safety review: preserves complete output and existing error/evidence semantics; no added execution authority or arbitrary caps. ## Review checklist - [x] One focused outcome and Conventional Commit title. - [x] Origin of finding and lack of separate issue explained. - [x] Tests cover changed observable behavior and meaningful failure paths. - [x] No owning docs, contract, or generated metadata changes are needed. - [x] Existing MCP output regressions pass. - [x] Final diff checked for secrets, unrelated edits, and unsupported claims. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi

2026-10-16 21:17:29 +00:00