ConcatenateGraphFilter's maxGraphExpansions javadoc promises an exception, but extra paths are silently dropped (and CompletionAnalyzer's "no limit" is 10000)

ConcatenateGraphFilter turns a token graph (for example the output of a synonym filter) into one concatenated token per path; the document suggester's CompletionAnalyzer uses it to index completions. Its 4-argument constructors and ConcatenateGraphFilterFactory document maxGraphExpansions as "If the tokenStream graph has more than this many possible paths through, then we'll throw TooComplexToDeterminizeException". The code never counts the total number of paths in the graph. It reads the paths through LimitedFiniteStringsIterator, which by its own javadoc returns "the first limit strings found", so extra paths are dropped without any signal: a 4-path graph at limit 3 gives 3 tokens. It also passes the same value to Operations.determinize as its work limit (an effort budget of 10 x the value), so a 2-path graph whose alternatives share a prefix throws once the input is long enough (in the probe's wifi|wireless shape, from 94 characters at limit 10 and 994 at limit 100). CompletionAnalyzer(Analyzer) and CompletionAnalyzer(Analyzer, boolean, boolean) say "no limit on graph expansions" but pass DEFAULT_MAX_GRAPH_EXPANSIONS = 10000: a value with 16384 paths gets 10000. Keeping the first N is a deliberate design (LUCENE-4971), so this is a documentation defect: the fix is a javadoc-only change in three files, validated on main. The filter and factory text dates from 7.4.0, the CompletionAnalyzer text has been stale since 5.3.0, and nobody has reported either.

• ConcatenateGraphFilter.java:106-110: @param maxGraphExpansions If the tokenStream graph has more than this many possible paths through, then we'll throw {@link TooComplexToDeterminizeException} to preserve the stability and memory of the machine. and @throws TooComplexToDeterminizeException if the tokenStream graph has more than {@code maxGraphExpansions} expansions. The boolean constructor (:126-143) "Calls" this one.
• ConcatenateGraphFilterFactory.java:35-37: the same sentence; the factory passes any integer through (:62-63, :77-78).
• CompletionAnalyzer.java:90-93 and :102-105: "... no limit on graph expansions"; both constructors pass ConcatenateGraphFilter.DEFAULT_MAX_GRAPH_EXPANSIONS (:99, :112), which is Operations.DEFAULT_DETERMINIZE_WORK_LIMIT (ConcatenateGraphFilter.java:61) = 10000 (Operations.java:63). The private field doc says "Defaults to -1 (no limit)" (:62-67).

incrementToken() builds the automaton and wraps it: finiteStrings = new LimitedFiniteStringsIterator(automaton, maxGraphExpansions); (ConcatenateGraphFilter.java:163-166). LimitedFiniteStringsIterator.next() returns null once count >= limit ("Abort on limit.", LimitedFiniteStringsIterator.java:57-61), as its class javadoc documents: "If more than limit strings are accepted, the first limit strings found are returned" (:21-23). incrementToken() then returns false (ConcatenateGraphFilter.java:172-175). No exception, no flag. The only count is the iterator's count of the strings it has returned (LimitedFiniteStringsIterator.java:36-37, :65); since the automaton is determinized first, these are distinct accepted strings (FiniteStringsIterator.java:33), so strictly the cap is on distinct concatenated strings, which can be fewer than the graph's paths when two paths concatenate to the same bytes. For (a|b) (c|d) at limit 3 the tokens are a␟c, a␟d, b␟c (␟ = the separator byte) on this build; which paths come first is not an API guarantee ("the iteration order is implementation dependent and may change across releases", LimitedFiniteStringsIterator.java:28).

toAutomaton() ends with return Operations.determinize(automaton, maxGraphExpansions); (ConcatenateGraphFilter.java:249-250). determinize returns a deterministic automaton unchanged (Operations.java:654-657); otherwise it adds up "effort" (the size of each state set it visits) against effortLimit = workLimit * 10 (:695) and throws TooComplexToDeterminizeException when it reaches it (:707-709). Its own javadoc calls the argument a "Maximum amount of \"work\"" (:645-651), not a path count.

A 2-path graph whose alternatives start with the same bytes (wifi / wireless) is not deterministic, and its effort grows with the input length. In the intended-behaviour check probe (wifi with the synonym wireless, lengthened with short filler words) the first throw came at 43, 94, 193, 493, 994 and 9994 characters for limits 5, 10, 20, 50, 100 and 1000, roughly 10 x the limit for that shape (a measurement, not a general rule); at 10000 the filter did not throw up to 60,004 bytes (one term that long is over IndexWriter.MAX_TERM_LENGTH, 32766 bytes, anyway). The (a|b) (c|d) graph is already deterministic, so use 2 never fires for it (4 tokens at limits 4 and 100, 3 at limit 3).

No code path counts the total number of paths and throws when it is above maxGraphExpansions.

• Who. Users of ConcatenateGraphFilter (directly, or as the concatenateGraph SPI factory) and of the document suggester (CompletionAnalyzer behind SuggestField / ContextSuggestField). Both classes are @lucene.experimental.
• At the default (10000). Truncation needs more than 10000 paths in one value, for example 14 positions that each carry a synonym (10000 of 16384 kept). The determinize throw needs a very large automaton. A single value did not throw in the filter up to 60,004 bytes, but one term that long could not be indexed anyway (IndexWriter.MAX_TERM_LENGTH is 32766 bytes). The realistic case is many contexts: about 1000 shared-prefix contexts on one ContextSuggestField (about 104 KB of contexts) throw; about 54 KB pass.
• With a small explicit limit. Paths beyond the limit vanish silently (fewer suggestions than the analyzer produced), and a long enough value with a shared-prefix alternative is rejected although it has fewer paths than the limit (in the intended-behaviour check probe's wifi|wireless shape: from 94 characters at limit 10, from 994 at limit 100).
• Effect. Silently missing completions, or one document rejected with a non-aborting exception. In the recorded indexing probe only that document fails, the IndexWriter stays open and records no tragic exception, the next document indexes, and the index passes the test framework's CheckIndex on close: no corruption and no hang for that input (not a proof for every input).
• Scale. Every release since 7.4.0 (filter and factory text) and since 5.3.0 (CompletionAnalyzer text); unreported in that time.

The graph is built with CannedTokenStream (the same graph a synonym map a -> b, c -> d gives for a c). It is deterministic, so the determinize work limit plays no part: a side check gives 4 tokens at limits 4 and 100 and 3 at limit 3.

The other two facets are covered by the finder's JUnit (re-run on fresh seeds in the registration check and the audit): 2 paths (wifi|wireless) network adapter for laptops at limit 3 throw Determinizing automaton with 40 states and 40 transitions would require more than 3 effort; CompletionAnalyzer(Analyzer) on a 16384-path value gives expected:<16384> but was:<10000>.

Gradle form (file in $LUCENE/lucene/analysis/common/src/test/org/apache/lucene/analysis/miscellaneous/): ./gradlew :lucene:analysis:common:test --tests "org.apache.lucene.analysis.miscellaneous.TestConcatenateGraphMaxGraphExpansionsJavadoc" -Ptests.seed=DEADBEEF fails with the same message, with -Ptests.asserts=true and false.

# main 645d4fe14a20, Gradle, seed DEADBEEF, -Ptests.asserts=true (false identical; the 'app/...' frame prefixes are left out). The 10.6.0 jars, run standalone, give the same message, with the expectThrows frames at LuceneTestCase.java:2940/2926
TestConcatenateGraphMaxGraphExpansionsJavadoc > testMorePathsThanMaxGraphExpansions FAILED
    junit.framework.AssertionFailedError: Expected exception TooComplexToDeterminizeException but no exception was thrown
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:BB5D7E37299F529F]:0)
        at org.apache.lucene.tests.util.LuceneTestCaseParent.expectThrows(LuceneTestCaseParent.java:1432)
        at org.apache.lucene.tests.util.LuceneTestCaseParent.expectThrows(LuceneTestCaseParent.java:1418)
        at org.apache.lucene.analysis.miscellaneous.TestConcatenateGraphMaxGraphExpansionsJavadoc.testMorePathsThanMaxGraphExpansions(TestConcatenateGraphMaxGraphExpansionsJavadoc.java:35)
1 test completed, 1 failed

• The @param sentence is a definition, not a side remark. It describes the value only as a path count past which the filter throws. Both it and the @throws say "more than N paths, then an exception"; the truncation (4 paths, limit 3, no exception) breaks that under any reading, including reading @throws X if C as a sufficient condition only. The below-the-limit determinize throw is weaker evidence: read as a sufficient condition, the text does not forbid a throw with fewer paths; it counts only because the text never says the value is also a work limit.
• CompletionAnalyzer. "no limit on graph expansions" was true in 5.1.0 and 5.2.1 (default -1: 16384 of 16384 paths kept). LUCENE-6459 (#7518) changed the default to 10000 in 5.3.0 without touching the javadoc (10000 of 16384 from 5.3.0 on).
• History. LUCENE-8332 (#9379, 7.4.0) moved the logic of CompletionTokenStream, which already used LimitedFiniteStringsIterator(automaton, maxGraphExpansions) and determinize(automaton, maxGraphExpansions), into the new public ConcatenateGraphFilter and wrote the throw-above-N text for it. The issue's 13 comments and the 18 review comments on lucene-solr#384 never discuss what the parameter means.
• Tests. TestConcatenateGraphFilter.testValidNumberOfExpansions checks a graph under the limit (256 paths at the default). No test in analysis-common or suggest/document builds a graph over the limit.

Strongest case that this is intended (the cross-model review, the intended-behaviour check and the adjudication): keeping the first N is a committer decision. On LUCENE-4971 (#6035) Mike McCandless wrote "I'd lean towards returning the first N after the limit is hit; this way at least some expansions are indexed", and Robert Muir answered "+1, the new semantics for the getFiniteStrings seem more useful to me anyway". LimitedFiniteStringsIterator documents the cap; reusing the value for determinize dates from LUCENE-6339; @throws X if C can be read as a sufficient condition only; both classes are @lucene.experimental; the "-1 (no limit)" text sits on a private field.

Why it fails: every point argues that the code is right, which is exactly why the javadoc should change. None makes the public @param text or the public "no limit" constructor docs true. The verifier who built this case concluded that it strengthens the documentation defect instead of refuting it. So this page claims only the javadoc, not a "should throw" behaviour bug.

Option A was validated in a scratch worktree of 645d4fe14a20 (removed afterwards); the other options were not run. Changing the code instead would reverse the LUCENE-4971 decision.

The hunk below is ConcatenateGraphFilter; the constructor's @throws line goes because the constructor never throws (in normal token-stream use the exception is thrown during incrementToken(), which calls toAutomaton(); the public toAutomaton() throws it too when called directly, so "incrementToken() (and toAutomaton())" would be more complete). "Only the first" follows the iterator's own wording; which paths come first is not specified. The snippets are abridged. The other two files:

--- ConcatenateGraphFilterFactory.java
- *   <li><code>maxGraphExpansions</code>: If the tokenStream graph has more than this many possible
- *       paths through, then we'll throw {@link TooComplexToDeterminizeException} to preserve the
- *       stability and memory of the machine.
+ *   <li><code>maxGraphExpansions</code>: The maximum number of paths through the tokenStream graph
+ *       that are emitted; further paths are silently dropped. The same value is also the
+ *       determinization work limit, so a graph that is too costly to determinize throws {@link
+ *       TooComplexToDeterminizeException} even if it has fewer paths. Defaults to {@link
+ *       ConcatenateGraphFilter#DEFAULT_MAX_GRAPH_EXPANSIONS}.
--- CompletionAnalyzer.java
-   * <p>Defaults to <code>-1</code> (no limit)
+   * <p>Defaults to {@link ConcatenateGraphFilter#DEFAULT_MAX_GRAPH_EXPANSIONS}
-   * preserving token separation, position increments and no limit on graph expansions
+   * preserving token separation and position increments, with at most {@link
+   * ConcatenateGraphFilter#DEFAULT_MAX_GRAPH_EXPANSIONS} graph expansions
-   * with no limit on graph expansions
+   * with at most {@link ConcatenateGraphFilter#DEFAULT_MAX_GRAPH_EXPANSIONS} graph expansions

Also recommended (not built or checked): the class javadoc's "one output token for every path" (ConcatenateGraphFilter.java:40-41) still contradicts the cap, so add "(at most maxGraphExpansions of them)".

-   * @param maxGraphExpansions If the tokenStream graph has more than this many possible paths
-   *     through, then we'll throw {@link TooComplexToDeterminizeException} to preserve the
-   *     stability and memory of the machine.
-   * @throws TooComplexToDeterminizeException if the tokenStream graph has more than {@code
-   *     maxGraphExpansions} expansions
+   * @param maxGraphExpansions The maximum number of paths through the tokenStream graph that are
+   *     emitted as tokens. If the graph has more paths, only the first {@code maxGraphExpansions}
+   *     are emitted and the others are silently dropped. The same value is also the work limit
+   *     passed to {@link Operations#determinize(Automaton, int)}, so {@link #incrementToken()} may
+   *     throw {@link TooComplexToDeterminizeException} for a graph that is too costly to
+   *     determinize (for example a long input with a synonym that shares a prefix with the original
+   *     token), even if it has fewer paths than this.

Trade-offs

None for users: documentation only. A CHANGES entry is optional.

What the checks validated

• Format: the diff is the output of applyGoogleJavaFormat on both modules; checkGoogleJavaFormat passes.
• Module tests: ./gradlew :lucene:analysis:common:test --tests "org.apache.lucene.analysis.miscellaneous.TestConcatenateGraphFilter*" -Ptests.seed=DEADBEEF: 18 tests, 0 failures. ./gradlew :lucene:suggest:test --tests "org.apache.lucene.search.suggest.document.*" -Ptests.seed=DEADBEEF: 58 tests in 6 suites, 0 failures.
• Javadoc: renderJavadoc and ecjLintMain succeed on both modules; the rendered pages carry the new text and neither "we'll throw" nor "no limit on graph expansions". In the per-module render the cross-module link in CompletionAnalyzer shows as plain code text.
• Behaviour unchanged: the minimal repro still fails the same way on the patched build, as it must.
• The new text matches the code: the same minimal test with its expectation flipped (3 tokens, no exception) passes on the patched build with -ea and -da.

Determinize with Operations.DEFAULT_DETERMINIZE_WORK_LIMIT (or a separate parameter) instead of maxGraphExpansions, so the value means only "number of paths".

Trade-offs

Inputs rejected today under a small limit would be indexed, and determinize could use more memory under a small limit. The adjudication and the audit kept it separate from the docs fix.

Iterate with limit + 1 and throw when the extra path appears, matching the current text.

Trade-offs

Reverses the LUCENE-4971 decision ("at least some expansions are indexed"), starts rejecting documents that index today, and needs a migration note.

None is needed for a javadoc change. If a reviewer wants the documented behaviour pinned, use the same minimal test with its expectation flipped (same graph, same limit: assert 3 tokens and no exception); it passes on the patched build, whose code is that of main. Lucene has no test today for a graph over the limit.

Trade-offs

Pins behaviour that LUCENE-4971 chose, so a later deliberate change would have to update it.

• Translation validation. Every token graph with at least 2 paths over a 6-letter alphabet and up to 3 slots, with maxGraphExpansions = paths - 1, paths and paths + 1; expected (from the javadoc): throw if and only if paths > limit, else all paths. 129,060 checks; 42,440 in the bucket "expected throw, got truncated to limit".
• Directed probe. Longer shared-prefix synonym values showed the throw below the limit (the determinize work limit).
• Review. The cross-model reviewer (OpenAI GPT-5.6) pointed to the CompletionAnalyzer "no limit" javadoc; all three facets were then shown by a public-API JUnit on the stock main jar.
• Tier. Semi-formal (bounded-exhaustive checking against the documented contract).