Problem

find_all_callers, find_all_callees and find_function_call_chain in tools/code_finder.py still enumerate every path of a variable-length pattern (-[:CALLS|HEURISTIC_CALLS*1..N]->). On a call graph with fan-out, the number of paths grows exponentially with depth, while the number of distinct edges grows only linearly. #1777 added LIMIT 500 and a 500-edge cap on result conversion to the two transitive queries. That bounds their time, but it also creates a second problem:

1. find_all_callers / find_all_callees are silently incomplete. The 500 paths are an arbitrary sample, not level-ordered. Direct callers can be missing while deep ones are present, and nothing reports truncated.
2. find_function_call_chain is still unbounded. It expands (start)-[*1..N]->() to any end node and only then filters on the target. ORDER BY chain_length + LIMIT cannot short-circuit, so a chain query between two functions that are not connected enumerates every path out of start.

Minimal repro (upstream/main 1b595a6, no code changes)

A layered graph: top calls W functions in layer 1, every function in layer i calls every function in layer i+1 (L layers), and every function in layer L calls target. island is a Function with no edges. W=10.

# nodes: Function {uid, name, path: "/repo/m.py", line_number, occurrence_index: 0, is_dependency: false}
# edges: (a)-[:CALLS {line_number: 1}]->(b), layer by layer as described above
cf = CodeFinder(db_manager)
cf.find_all_callers("target", depth=L + 1)
cf.find_function_call_chain("top", "island", max_depth=L + 1, limit=21)   # 21 = MCP call_chain limit + 1

Measured on one machine, each in a fresh process. The Neo4j runs used a local Neo4j 5.26 container. Kùzu 0.11.3 and LadybugDB 0.19.1 ran embedded, in separate processes.

find_all_callers("target", depth=L+1) (the true answer is 520 distinct edges, 10 of them direct callers of target):

With L=3 and depth 4 (220 true edges), Neo4j already returns 137 edges and 3 of the 10 direct callers.

find_function_call_chain("top", "island", limit=21): the answer is empty in every case, so all of the time goes on enumeration:

Time grows by about 10× per extra level: the fan-out to the power of the depth. Without a limit (the CodeFinder default), a reachable target is worse. find_function_call_chain("top", "target", max_depth=6) on Neo4j takes 0.47 s / 3.08 s / 48.3 s at depth 4 / 5 / 6, because it materialises all 10^3 / 10^4 / 10^5 chains.

On a real ERP-sized Python codebase (Neo4j, before #1777), find_all_callers on a widely used helper at depth 8 did not finish in 30 minutes. call_chain between two common entry points at depth 5 took 104.9 s.

(The Kùzu/LadybugDB chain endpoint bug, where func_nodes[size(func_nodes)-1] is 1-based, makes call_chain return 0 chains there even for reachable targets: 0 of 27 in a W=3, L=3 graph. That is #1781 and is separate from this issue.)

Impact

• Deep find_all_callers / find_all_callees results on any non-trivial graph are a sample, not an answer. Agents act on missing direct callers without being told.
• call_chain cost is fan-out^depth. At the default max_depth=5, a hub-heavy repository easily reaches minutes. Every MCP call holds a DB session (and an embedded backend's lock) for that long.

Proposed fix

Walk edges instead of paths:

• Transitive callers/callees: a level-ordered BFS. One anchored query per level expands the current frontier (UNWIND $frontier … MATCH (k)<-[r:CALLS|HEURISTIC_CALLS]-(c)), with a visited set and the repo filter on every hop. A total ORDER BY plus LIMIT budget+1 makes the cut deterministic. Each row carries its depth, and the result reports truncated and depth_completed, so a budget cut is always explicit and always falls at a level boundary.
• call_chain: a bidirectional search from both endpoints over the same per-level edge expansion. It needs path-aware pruning (a node is kept only if dist_from_start + dist_to_end <= max_depth) and a per-edge step budget that reports search_truncated instead of running unbounded. Chains are then enumerated only inside the pruned subgraph.

A downstream fork has implemented this. On the real-codebase cases above it measured find_all_callers depth 8 at >30 min → ~0.2 s and call_chain depth 5 at 104.9 s → ~0.3 s, with identical results on Neo4j, Kùzu and LadybugDB. It cannot be submitted as a drop-in PR, because it is entangled with fork-only pieces: an extended row contract (depth, labels, rel_type, plus the #1724-style OVERLOAD_WARNING row), extra relationship types, and a configurable step budget. I'm opening this issue so the approach can be agreed first, including the output contract for truncated / depth_completed.

Related

• fix(queries): return constructor calls and portable recursive call edges #1777 (merged): added the 500-path LIMIT and the conversion cap. It bounds time for callers/callees but makes their results a silent sample.
• Fix: CALLS caller/callee lookups never match Class targets (class instantiations invisible) #1723 (merged): Class targets for callers/callees.
• Add OVERLOAD_WARNING to by-name caller/callee results when a name has multiple definitions #1724 (open): OVERLOAD_WARNING for ambiguous names on the same tools.
• fix: use backend-correct indexing for embedded call chains #1781 (open): 1-based endpoint indexing in find_function_call_chain on Kùzu/LadybugDB, in the same function.
• [Bug] find_all_callers, find_all_callees, call_chain fail with "Unknown function list_extract" #756 (closed): earlier embedded-backend traversal fix in this code.