SimpleBindings.validate() takes cubic time on a chain of expression bindings: 2,000 bindings take 31-48 s, against 99 ms on 8.5.2

SimpleBindings binds expression variable names to value sources, including other expressions, and its optional validate() "Traverses the graph of bindings, checking there are no cycles or missing references". Since 8.6.0 (LUCENE-9338) validate() starts a new walk from every binding, and at every step CycleDetectionBindings copies the whole path so far into a new LinkedHashSet; nothing records which bindings were already checked. On a plain chain x0 = 1, x_i = x(i-1) + 1 that costs O(n^3): 1,000 bindings take 5.4 s on 8.6.0 and 10.6.0 and 5.7 s on main, against 45 ms on 8.5.2, and 2,000 take 31-48 s against 99 ms; the bytes allocated grow x7.6-7.9 per doubling (x4.0 on 8.5.2). The answers stay correct. Swapping only SimpleBindings.java across the introducing commit moves the slowdown both ways: 8.5.2 with the new file is slow, 8.6.0 with the old file is fast. A depth-first search with one shared path set and a record of checked bindings validates the 2,000-binding chain in 1.3 ms and passes all 171 tests of the expressions module. Low priority: validate() is optional, Lucene never calls it, and the chain must be hundreds of bindings long before it shows.

• validate() (SimpleBindings.java:81-85) applies every binding with a fresh CycleDetectionBindings(origin).
• An expression binding is stored as expression::getDoubleValuesSource (:64-66), which builds an ExpressionValueSource whose constructor resolves every variable through the given bindings at once (ExpressionValueSource.java:39-54, the call at :45).
• CycleDetectionBindings.getDoubleValuesSource(name) checks the path for a cycle and the map for a missing name, then applies the referenced binding with new CycleDetectionBindings(seenFields, name) (:100-110, the call at :109). That constructor copies the whole path: seenFields.addAll(parents) (:95-98).
• Nothing records which bindings were already checked.

1. validate() applies x_k with the set {x_k}.
2. Building x_k resolves x(k-1): a new set copies 1 name and adds x(k-1).
3. Building x(k-1) resolves x(k-2): another new set copies 2 names, and so on down to x0, where the last copy holds k names.
4. So one walk builds k expression sources and inserts about k^2/2 names into fresh sets. Over all n start points that is about n^2/2 builds and n^3/6 insertions: about 1.3 billion insertions for n = 2,000 (derived from the code).

8.5.2's validate() built every expression binding through the bindings themselves and turned a StackOverflowError into a cycle error: the same walk from every start point, but no path set, so about n^2/2 builds, the same work as resolving each binding once. LUCENE-9338 kept the walks and added the per-step copy. In the same walk, bindings that share sub-expressions are visited once per path, which is exponential in depth; that part is the same on every release tested since 5.5.5, so it is a secondary symptom, not part of the regression.

• Who. Code that chains named expressions to each other with SimpleBindings.add(String, Expression) and calls validate(). It shows from a few hundred bindings: about 0.1 s at 250, 0.6-1.3 s at 500, 4-6 s at 1,000 and 31-48 s at 2,000 on main (the spread is JIT flags and machine load).
• Default or opt-in. validate() is optional. Nothing in Lucene calls it outside tests. No call was found in the Elasticsearch, OpenSearch and Solr code that uses SimpleBindings (GitHub code search).
• Effect. CPU time and allocation at setup, before any search runs. The answer is correct and the call returns. Using the same bindings is not slowed by this bug: a sorted search by the top of a 4,001-binding chain (x0 to x4000) ran in 38 ms on main.
• Likelihood: rare. It needs hundreds of chained expression bindings plus the optional call; the searches found no report of it since 8.6.0 (2020).
• Workaround (by reading, not run): skip validate() for long chains, or check the name graph yourself; every Expression lists the names it uses in its public field variables.

One test class, one method, single thread, nothing random. The bound compares validate() with resolving each binding once through getDoubleValuesSource(name), the work 8.5.2's validate() did (itself quadratic on a chain, because each resolution builds every binding below it, so the bound is lenient), measured in the same JVM, so it does not depend on machine speed.

Timing caveat. A cost-only bug needs a timing oracle. Through gradle (Lucene's test JVM uses -XX:TieredStopAtLevel=1) stock main measured about 92x and 102x; across earlier stock runs the ratio was 12x-162x (the 12x run was on 10.6.0 at a load average of about 31 on 32 cores, and its re-run gave 50x). With the fix it is about 0.05x. A pass on a heavily loaded machine is not a refutation. The worst stock run (12x) was just above the bound, so the bound has little margin under heavy load; larger chains or another oracle were not tested. A deterministic allocation check exists but needs com.sun.management, which Lucene's forbidden-apis rejects, so it is evidence, not part of the test.

Lint: the test passes the expressions module's checkGoogleJavaFormat, ecjLintTest and forbiddenApisTest as is. Pass -Ptests.asserts explicitly, because Lucene's build picks it at random from the seed; the result is the same both ways.

Regression test: this same test. It fails on stock main and passes with the fix.

cp $REPRO/TestSimpleBindingsValidateChainCost.java $LUCENE/lucene/expressions/src/test/org/apache/lucene/expressions/
cd $LUCENE && ./gradlew :lucene:expressions:test --tests org.apache.lucene.expressions.TestSimpleBindingsValidateChainCost -Ptests.seed=DEADBEEF -Ptests.asserts=true
# same failure with -Ptests.asserts=false

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true
TestSimpleBindingsValidateChainCost > testValidateOfChainCostsAboutAsMuchAsResolvingEachBinding FAILED
    java.lang.AssertionError: validate() took 1288 ms, resolving each binding once took 14 ms
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E9B1B9D029CD38AD]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.expressions.TestSimpleBindingsValidateChainCost.testValidateOfChainCostsAboutAsMuchAsResolvingEachBinding(TestSimpleBindingsValidateChainCost.java:41)
1 test completed, 1 failed

# -Ptests.asserts=false
    java.lang.AssertionError: validate() took 1121 ms, resolving each binding once took 11 ms

# with the recommended fix: 1 test completed, 0 failures, both ways

# chain timing probe, main 645d4fe14a20, -da, default JIT: validate() / resolve each once
n=250   stock 96.4 ms / 7.9 ms       fix 2.0 ms / 6.5 ms
n=500   stock 606.5 ms / 5.2 ms      fix 0.8 ms / 7.7 ms
n=1000  stock 3915.9 ms / 22.7 ms    fix 0.5 ms / 32.6 ms
n=2000  stock 30831.5 ms / 127.5 ms  fix 1.3 ms / 146.8 ms

• The contract. validate() "Traverses the graph of bindings, checking there are no cycles or missing references" (SimpleBindings.java:76-80). Expression-to-expression bindings are the documented use: the class javadoc example binds "another expression" (:38-39), and add(String, Expression) "can be used to reference expressions from other expressions" (:62). No cost, size or depth limit is documented in the javadoc, package docs, CHANGES or MIGRATE.
• Tests call it routinely. All 8 tests of TestExpressionValidation call validate(); testValidExternals calls it after each expression it adds, three times. The only documented limit, JavascriptCompiler.DEFAULT_MAX_NESTING_DEPTH = 1024, bounds the nesting inside one expression; each binding here is a one-variable expression.
• History. LUCENE-9338 is recorded as "Refactors SimpleBindings to improve type safety and cycle detection" (8.6.0 CHANGES). In its review (apache/lucene-solr#1444), jpountz noted that catching stack overflows "is usually a bad idea", then posted a test with a cycle that does not pass through the start, which defeated the PR's first version (8.5.2 rejected such a cycle only by catching the StackOverflowError). The author (romseygeek) "updated the cycle detection logic to handle multiple levels of recursion" in PR commit f31cb0601615, which added the copying constructor. Nobody discussed what validate() costs.
• The copy buys nothing for the cycle check. One shared path set catches the same cycles: with the recommended fix, a bounded-exhaustive check gave the same accept or reject answer as the stock jar on all 730,272 enumerated graphs, and all 171 expressions tests pass.

The strongest case for "not a bug": no complexity bound is documented; validate() is optional, @lucene.experimental and has no in-tree caller; the results are correct; 8.5.2 was already quadratic and found cycles only by catching StackOverflowError, which LUCENE-9338 replaced after review; in that review the author said "it's part of query setup, not query execution"; and the cross-model refute review (OpenAI GPT-5.6) said "not real", arguing that maintainers "could regard this as an accepted simplicity-versus-setup-cost trade-off".

Why it fails: the "query setup" reply answered madrob's nit about containsKey versus get, a constant factor, not a change from n^2 to n^3. No source shows a trade-off was weighed, and the copy buys nothing for the cycle check, since the fix keeps LUCENE-9338's path-set check and its answers without the copy. The cross-model reviewer could not run anything; its "not real" is procedural, and on reading it agreed with every point of the mechanism. The remaining points (optional, experimental, correct results) argue for Low priority, which is how it is classed, not for intent.

One fix was validated through gradle in a scratch worktree of 645d4fe14a20; a smaller variant that only stops the copying passes the same tests but stays quadratic; going back to 8.5.2's check is not recommended.

SimpleBindings.java +28/-12. validate() creates one CycleDetectionBindings holding a shared LinkedHashSet path and a HashMap of checked bindings, and calls check(name) for every name. getDoubleValuesSource(name) keeps its cycle and missing-name checks and then calls check(name) instead of building a new CycleDetectionBindings. The heart of it:

DoubleValuesSource check(String name) {
  DoubleValuesSource done = verified.get(name);
  if (done != null) {
    return done;
  }
  path.add(name);
  try {
    DoubleValuesSource source = map.get(name).apply(this);
    verified.put(name, source);
    return source;
  } finally {
    path.remove(name);
  }
}

Trade-offs

• Each binding is applied once: the chain becomes linear (1.3 ms at 2,000 bindings), and the exponential cost on shared sub-expressions goes too (48 builds instead of 786,308 for 49 bindings).
• Same exception types and message format; a bounded-exhaustive check gave the same accept or reject answers as the stock jar on 730,272 graphs.
• Cost: one DoubleValuesSource per binding, with its array of variable sources (O(bindings + references) in all), is held until validate() returns; the walk still recurses as deep as the chain, like the current code.
• Scope (by reading, not run): Expression.getDoubleValuesSource(Bindings) is public and not final, so a custom Expression subclass that overrides it would be called fewer times and would get one shared, mutable Bindings object instead of a fresh one per step; the exhaustive check covers accept or reject answers, not such side effects. A binding that resolves to null is not recorded and is applied again when referenced.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle --offline, OpenJDK 25.0.3, seed DEADBEEF. Stock: the repro fails with assertions on and off.
• With the fix: the repro passes both ways; the whole :lucene:expressions:test (14 suites, 171 tests, including TestExpressionValidation with its cycle and missing-reference tests) passes with 0 failures with assertions on and off; the module's checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest pass.
• The tie-breaker and the current-main reproducer also passed the repro with it through the standalone runner, with assertions on and off.

SimpleBindings.java +12/-10: one LinkedHashSet per start point; getDoubleValuesSource adds the name, applies the binding with this, and removes the name in a finally.

Trade-offs

Smaller diff; back to 8.5.2's O(n^2) on a chain: 434 ms at 2,000 bindings, against 31 s stock and 1.3 ms with the recommended fix. Keeps the exponential cost on shared sub-expressions (by reading).

What the checks validated

The whole :lucene:expressions:test, the repro included, with assertions off: 171 tests, 0 failures. Not run with assertions on.

8.5.2 built every binding and turned a StackOverflowError into a cycle error.

Trade-offs

Quadratic on a chain, but jpountz's review point that catching stack overflows "is usually a bad idea" is why LUCENE-9338 replaced it.

What the checks validated

Not run.

Method: testing (the hunt's non-formal tier: the chain result came from a timing probe, not from the model).

• Lead. An idea from an independent model from another family (OpenAI GPT-5.6) in a cross-model ideation round: expression bindings that share sub-expressions may be expanded once per path. Its probe timed validate() at 20.0-20.4 s for 61 such bindings on main.
• Cost model. The finder wrote an exact cost model of validate() (expression builds = the sum over expression start points of the number of paths) and checked it against the stock jar by bounded-exhaustive enumeration: 730,272 graphs, 79,987,206 checks, 0 mismatches; a linear-traversal mutant of the model is rejected.
• Chain. While bounding that model, a wall-clock side probe on plain chains showed the cubic cost, and the same probe on 8.5.2 and 8.6.0 dated it.
• Then an independent reproducer, cross-model reviews (which could not run code), a devil's-advocate check, an adjudication, the registration check, an audit, a repro-minimization step, a current-main reproducer, a tie-breaker, the version-history runs and a prior-report search followed.