reaches() with no depth bound does not terminate on a large call graph: the quantified path pattern enumerates trails, it does not prune

[rahlk]

Problem

reaches() with its default depth=None does not terminate on a large call graph. Measured on a codeanalyzer-typescript 1.3.0 projection of microsoft/vscode's src/ tree — 9,005 files, 2.45M nodes:

MATCH (a:TSCallable {signature:$a}) WHERE …
MATCH (a) ((x:TSCallable)-[:TS_CALLS]->(y:TSCallable) WHERE …){1,} (m:TSCallable)
WITH DISTINCT m WHERE … AND m.signature = $b RETURN count(m) > 0 AS ok

44 minutes, then I terminated it unfinished. The same question, same pair, same database:

form	depth	time
count(shortestPath((a)-[:TS_CALLS*1..]->(b))) > 0	unbounded	1.5 s
shipped quantified form	{1,8}	~2 s
shipped quantified form	{1,} (the default)	44 min, unfinished

Bounded depths are fine at every value I tried up to 8. It is specifically the unbounded quantifier.

Why

A quantified path pattern has trail semantics — Neo4j enumerates distinct-relationship paths. WITH DISTINCT m deduplicates the result, after enumeration; it does not prune during traversal. On a cyclic call graph the number of trails grows combinatorially with the bound, so a finite bound stays cheap and no bound at all does not finish.

The comment above the Python copy states the opposite, and cites a measurement that no longer generalises:

the quantified path pattern below … still plans as a pruning expansion (WITH DISTINCT m keeps it one) … at 0.25s against 0.03s for the unsafe form

That 0.25 s was measured on the odoo graph. It is true there and false at vscode scale, which is exactly why this went unnoticed: every corpus the suites have run against so far has a call graph small enough for trail enumeration to finish.

Where

Two shapes, both affected, in the languages that answer them over Cypher:

accessor	Python	TypeScript	Java
reaches (call graph)	_REACHES, quantified {1,{depth}}	_REACHES, same	not affected — answered in memory over networkx
flows_to_call / flows_to_argument (SDG)	_VALUE_REACHES, var-length *1..{depth}	_VALUE_REACHES, same	_VALUE_REACHES, same

Variable-length patterns carry the same trail semantics as quantified ones, so _VALUE_REACHES is the same defect in a different spelling. It has been unreachable on Java until now (the port lattice was disconnected), which means codeanalyzer-java 3.0.3 turns on a code path with this shape in it.

Scope boundary

In scope: make the unbounded reachability predicate use a pruning primitive on every backend that answers it over Cypher, and correct the comments that claim the current form prunes.

Out of scope: paths_between and call_paths_between, which already use allShortestPaths and are not affected. The bounded case, which is correct and cheap today.

Goals

• reaches and _VALUE_REACHES answer in bounded time with depth=None on a graph of at least a million nodes, on Python, TypeScript and Java
• The replacement returns the same answers as the current form wherever the current form finishes — asserted against a bounded run, not assumed
• The comments claiming WITH DISTINCT m makes this a pruning BFS are corrected or removed
• A test that would have failed before: an unbounded reaches against a corpus large enough to enumerate, with a wall-clock bound

Caveats and known risks

• shortestPath answers "is there a path", which is what these predicates ask, but it is not a drop-in for anything that needs the path itself — check each call site is only consuming the boolean.
• The bounded form must keep working: a caller passing depth is asking a different, narrower question and its cost is already acceptable.
• Any wall-clock assertion must be paused around the coverage tracer, as the existing timed marker does — a run under instrumentation measures the tracer.

Definition of done

• An unbounded reaches on a million-node graph returns in seconds rather than not at all, on all three backends, and a test pins it.

[rahlk]

Correcting the diagnosis in the issue body. The mechanism I named is wrong, and the scope is narrower than stated.

I claimed the unbounded quantified path pattern enumerates trails and that WITH DISTINCT m deduplicates only the result. That is not what happens — it prunes, as the Python backend's comment always said. Measured three ways, all with an unreachable target so the search must exhaust:

graph	shipped quantified form	shortestPath
odoo, 15,549 callables / 328,401 call edges	3.0 s	2.0 s
synthetic complete digraph, 12 nodes / 132 edges	5.5 s	5.6 s
synthetic dense cyclic, 5,000 nodes / 100,000 edges, whole graph reachable at depth 6	4.97 s	4.84 s

The third is the decisive case: factorially many trails, unbounded quantifier, full exploration forced. No difference. So swapping to shortestPath would not have fixed anything, and the generalisation to "all three languages, two places each" was unfounded.

The actual cause is the per-hop predicate. Same graph, same pattern, same answer — only the WHERE inside the quantifier changes:

per-hop predicate	time
one STARTS WITH on one endpoint (what Python's _REACHES carries)	4.97 s
two OR-ed STARTS WITH plus two further tests, on both endpoints (what TypeScript's _REACHES carries)	623.9 s

125× on identical data. That explains the 44-minute vscode run and it explains why odoo never reproduced it: Python's predicate is the cheap one.

And most of that cost is redundant. In ((x)-[:CALLS]->(y)){1,}, consecutive repetitions bind x to the previous y, so predicating both endpoints checks every interior node twice. Checking one endpoint plus the anchor covers the whole walk — which is exactly why Python's form is both cheaper and equally scoped. The written-predicate doctrine is preserved either way: every node on the walk is still predicated, once instead of twice.

So the fix is to make the per-hop predicate cheap, not to change the traversal primitive. Re-measuring the variants now; will post the numbers and revise the goals before touching code.

What stands from the original report: that query really did run 44 minutes unfinished on the vscode graph while shortestPath answered the same pair in 1.5 s. Those measurements were real. The explanation attached to them was not.