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

Is your feature request related to a problem? Please describe.

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:

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

Describe the solution you'd like

• 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

Describe alternatives you've considered

Not stated in the original issue.

Additional context

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:

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.

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.