FixedShingleFilter drops the gap filler before stacked tokens: "coffee at the café" gives "at café"

FixedShingleFilter (lucene/analysis/common) writes a filler "_" for each empty position, such as a removed stop word, and promises stacked shingles for stacked tokens. Since 8.0 it builds one shingle per route through the token graph, but it takes the gap before each route token from that token's own position increment, which counts from the previous token in the stream, not from the previous token on the route. So a token stacked right after a gap (increment 0) gets no filler: "coffee at the café" through StopFilter and ASCIIFoldingFilter(preserveOriginal) gives "at café" and "coffee at café", and "at _ café" is missing; which stacked token keeps the filler depends only on the stream order of the stack, which Lucene documents as undefined. After a token that spans two positions, the next token can get a filler it should not have ("login _" instead of "login page"). Nothing throws. 7.4.0-7.7.3 produced the right stacked shingles; every release from 8.0.0 (LUCENE-8564, which rebuilt the filter on GraphTokenFilter) to 10.5.2 and main does not. A fix that measures the gap along the route, in GraphTokenFilter, was validated with the repro, the whole analysis-common module and a bounded-exhaustive model check.

• Shingle and filler: FixedShingleFilter(input, shingleSize) emits every run of shingleSize consecutive tokens as one token. It "handles position increments > 1 by inserting filler tokens (tokens with termtext "_")" (FixedShingleFilter.java:40-41); the filler represents "gaps in the input stream (due to eg stopwords)" (:81). StopFilter removes a word and adds 1 to the next token's position increment.
• Stacked tokens: tokens with position increment 0 sit at the same position as the token before them: a synonym, the original kept by ASCIIFoldingFilter(preserveOriginal = true), or the stem added by KeywordRepeatFilter plus a stemmer. The filter promises that "if the filter encounters stacked tokens (eg synonyms), then it will output stacked shingles" (:34-35).
• Routes: since 8.0 the filter extends GraphTokenFilter, which walks one route through the token graph at a time (incrementGraphToken, GraphTokenFilter.java:97-112) and then switches a route token to the next token stacked behind it (incrementGraph, :119-139).

1. Both route methods copy the cached token's attributes unchanged from the stream (GraphTokenFilter.java:100, :110).
2. FixedShingleFilter reads the gap from them: int posInc = incAtt.getPositionIncrement(); (FixedShingleFilter.java:143) and writes posInc - 1 fillers (:144-161).
3. That increment counts from the previous token in the stream. A token stacked behind another one has increment 0, so on its route the gap before its stack disappears.
4. After a token that spans two positions, nextTokenInGraph (GraphTokenFilter.java:200-210) finds the right successor, but the successor's increment counts from a shorter token in the stream, so a filler can appear where there is no gap.

Canned a(+1), b(+2), c(+0), shingle size 2: the route a -> b reads increment 2 and gives a _; the route a -> c reads increment 0 and gives a c, although c is two positions after a. At size 3 the route a -> c runs out of tokens and emits nothing, so a _ c is missing. With c first in the stream, a -> c gets the filler and a -> b does not: [a _, a b].

For login(+1, length 2), log(+0), page(+2) (a removed "in" under "login"), page directly follows login, but its increment 2 counts from log, so size 2 gives [login _, log _] instead of [login page, log _].

Not affected (in the bounded model): single-position chains with no stack right after a gap, and multi-position tokens whose last covered position starts a token, even with empty inner positions, when no stack follows a gap (0 differences in those domains of the exhaustive check). A gap under the last position of a multi-position token is the second shape.

• Who is exposed. Users of FixedShingleFilter (lucene/analysis/common, opt-in, @lucene.experimental), directly or through FixedShingleFilterFactory ("fixedShingle"), at default settings, after a chain that removes tokens and then stacks tokens:
  • StopFilter -> ASCIIFoldingFilter(preserveOriginal = true): "coffee at the café" gives "at café";
  • StopFilter -> KeywordRepeatFilter -> PorterStemFilter: "walk the dogs" gives "walk dog" (and at size 3 "walk _ dog" is missing);
  • single-word synonyms, then StopFilter: "coffee at the cafe" with cafe -> bistro gives "at cafe". With StopFilter before SynonymGraphFilter it does not show, because the synonym filter re-emits the match with increment 1.
• How often. No crafted input: in such a chain, every stop word directly followed by a word with a stacked variant hits it, deterministically. The reach is narrower than that sounds: the filter is opt-in and experimental, preserveOriginal is not the default and stacks the original only when folding changes the word, and RemoveDuplicatesTokenFilter would drop only text-identical copies, not "cafe"/"café" or "dogs"/"dog" (reasoning). How common such chains are was not measured.
• What goes wrong. Shingle fields usually speed up phrase or as-you-type matching. A lookup of "at café" can match text that says "at the café", and a lookup that expects "at _ café" finds nothing (reasoning; no search was run). Terms already indexed stay wrong until the field is reindexed.
• Silent. No exception or warning, with assertions on and off; one 4-word string is enough.
• The multi-position shape ("login _") needs a token-removing filter after a graph filter (demonstrated with SynonymGraphFilter with a multi-word rule, FlattenGraphFilter, StopFilter), which is rarer.
• How likely. Plausible: the chain is opt-in, and extra or missing shingle terms are easy to miss, which fits that nobody has reported it since 8.0.0 (2019).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected no shingle "a c", got [a _, a c]
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.assertTrue(Assert.java:42)
       org.junit.Assert.assertFalse(Assert.java:65)
       org.apache.lucene.analysis.shingle.TestFixedShingleFilterStackedAfterHole.testStackedTokenAfterHole(TestFixedShingleFilterStackedAfterHole.java:44)

• The class contract. "This filter handles position increments > 1 by inserting filler tokens" (FixedShingleFilter.java:40-41); stacked tokens give "stacked shingles" (:34-35); the filler represents "gaps in the input stream (due to eg stopwords)" (:81); the factory's fillerToken is "what should be added in place of stop words" (FixedShingleFilterFactory.java:32).
• An undefined order decides. The analysis package docs: "the output order of the original token and the injected synonym is undefined as long as they both leave from the same position", and such tokens "would be considered to appear in exactly the same position" (analysis/package-info.java:341-345). Swapping two stacked tokens changes [a _, a c] into [a _, a b].
• Lucene's own graph code gives stacked tokens the same gap. GraphTokenStreamFiniteStrings: "stacked token should have the same increment as original token at this position" (GraphTokenStreamFiniteStrings.java:237-240); fed path by path that way, FixedShingleFilter gives {a _} and {a _ b, a _ c}. TokenStreamToAutomaton accepts "a HOLE c" and rejects "a c".
• Increments exist to stop phrases across removed words. PositionIncrementAttribute: values greater than one "inhibit exact phrase matches", so that "exact phrase queries will only match when the terms occur with no intervening stop words" (PositionIncrementAttribute.java:35-39). In review of LUCENE-8202 (#9249), @jpountz proposed the goal that the filter "should emit exactly all the exact phrases of length shingleSize that you could search if you indexed with the wrapped analyzer directly"; the author's next patch said it "should address all of Adrien's concerns".
• It used to work. 7.4.0-7.7.3 emit [a _], [a _ b, a _ c] and "at _ café"; 8.0.0 onwards do not. LUCENE-8564's CHANGES entry only says it "also changes FixedShingleFilter to extend GraphTokenFilter", and the commit changed no shingle expectation in the tests (its test edit added a comment and removed testShingleCountLimits, an exception-message test for the old shingle-count limit).
• No test pins the current output. Upstream TestFixedShingleFilter (15 tests) and TestGraphTokenFilter (4) never combine a gap with a stacked group, and they pass with the fix.

The strongest case for "works as designed" (rated moderate by the devil's advocate and by a reviewer from another model family): PositionIncrementAttribute is defined "relative to the previous Token in a TokenStream" (PositionIncrementAttribute.java:22), GraphTokenFilter promises routes, not route-relative increments, and the javadoc's fillers are for "position increments > 1", which a stacked token (increment 0) literally does not have. The class is @lucene.experimental, and its author called it the index-time filter "that assumes a linear stream (or sausage)" (LUCENE-8202).

Why it fails for the stacked shape: the literal reading makes the output depend on an order Lucene documents as undefined; GraphTokenStreamFiniteStrings gives stacked tokens their stack head's increment (a rule the FixedShingleFilter author added in LUCENE-8916); the 7.x filter produced the expected shingles; and a stack of single-position tokens after a gap is a sausage. Experimental status allows API changes; it does not make wrong output intended. Verdict: a defect (adjudication: confirmed, high).

The multi-position shape is weaker (devil's advocate: medium): upstream tests assert route semantics (testTrailingGraphsOfDifferingLengths expects "a b f" over a three-position "b") and TokenStreamToAutomaton handles "a token spanned over a hole" on purpose (TokenStreamToAutomaton.java:157-161, it accepts "login page"). Against it: position length is not indexed, so in the flat index "login page" is not an exact phrase while "login _ page" is, and the exact-phrase goal above can be read in favour of today's output (@jpountz made that point about a multi-length path in the same comment; upstream's "a b f" over a three-position "b" is not a flat-index phrase either). GraphTokenStreamFiniteStrings drops the "login" route for this input, and the only demonstrated stock trigger is a token-removing filter (StopFilter in the run) after a graph filter, the territory of the open LUCENE-8717 (#9763). Present it second.

The gap must be measured along the route. FixedShingleFilter alone cannot do that for multi-position tokens, because the token that carries the right increment is not on the route; GraphTokenFilter has the positions. A3 is recommended; A and B fix every wrong shingle but leave duplicates; C fixes only the stacked shape.

1. GraphTokenFilter records each cached token's absolute position when it reads it (one int per cached token, at most 100) and, on every incrementGraphToken, the number of empty positions between the end of the previous route token and the start of the current one. A new protected final int getRouteGap() returns it; attribute values are not changed.
2. FixedShingleFilter uses posInc = getRouteGap() + 1 instead of the stream increment (FixedShingleFilter.java:143).
3. With 1-2 alone, a shingle that fillers complete comes out once per stacked token after the gap (a _ twice). When fillers complete the shingle before a route token whose stream increment is 0, that token is stacked behind the one the previous route had at the same depth (incrementGraph advances exactly one depth to the next stacked token, and a token found by nextTokenInGraph always has increment >= 1), so the previous route already emitted the same shingle: skip it.

-        int posInc = incAtt.getPositionIncrement();
+        // count the gap from the previous token on this route, not from the previous token in the
+        // stream: a stacked token has increment 0 even when its stack follows a gap
+        int posInc = getRouteGap() + 1;
         if (posInc > 1) {
           // if we have a posInc > 1, we need to fill in the gaps
           if (i + posInc > shingleSize) {
+            if (incAtt.getPositionIncrement() == 0) {
+              // this token is stacked behind the one the previous route had here, so the
+              // previous route ended with the same fillers: skip the duplicate shingle
+              continue outer;
+            }

Trade-offs

• Adds a protected method to a public core base class (an API addition; the name is a suggestion). GraphTokenFilter is public and, unlike FixedShingleFilter, not marked @lucene.experimental, so a new protected final method could clash with a same-named method in an external subclass. The GraphTokenFilter part (+35/-4) is in the full diff.
• The duplicate skip relies on the order in which incrementGraph walks routes; the set-based JUnit does not pin how many copies come out, only the model's multiset comparison does.
• In the bounded model, output changes only in the two input shapes, which were wrong; existing shingle fields need reindexing to get the corrected terms.
• Two text-identical stacked tokens (KeywordRepeatFilter where the stem equals the word) still give one shingle each, as today ("coffee walk the dogs", size 3: "coffee walk _" twice, before and after).
• Not benchmarked; the extra work is one addition per token read and one subtraction per route step.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: the new test fails 5 of 6 on stock (assertions on and off) and passes 6 of 6 with the fix; with assertions on, the whole analysis-common module (340 suites, 1,915 tests, 18 skipped), TestGraphTokenFilter and TestGraphTokenizers (27 tests) and TestRandomChains pass; checkGoogleJavaFormat, ecjLint, forbiddenApis and core renderJavadoc pass.
• With assertions off: the 5 shingle suites, TestSynonymGraphFilter, TestFlattenGraphFilter and the 2 core graph suites (198 tests) pass.
• Standalone runner: the new test 6 of 6 with assertions on and off, the finder's 4 of 4, the independent reproducer's 9 of 9.
• Bounded-exhaustive model (every stream of 1-5 tokens with increments 0-2, position lengths 1-3 and final increment 0-1, fixed terms and offsets, shingle sizes 2-4, compared as multisets of position, term and offsets), assertions on and off: 0 of 265,716 checks differ from the all-paths reference, against 146,634 on stock.

The same getRouteGap() without the duplicate skip (+38/-5).

Trade-offs

Removes every wrong, extra and missing shingle but leaves identical duplicates: 18,180 of 265,716 model checks differ only by them (for example [a _, a _], [coffee at, at _, at _]). If the field indexes frequencies, the duplicates raise the filler shingle's term frequency.

What the checks validated

The new test 6 of 6 (it compares sets); the exhaustive model: 18,180 checks, all duplicate-only.

GraphTokenFilter sets the route token's PositionIncrementAttribute to 1 + the empty positions after the previous route token's end; FixedShingleFilter is unchanged.

Trade-offs

Same output as A, duplicates included. It changes what every GraphTokenFilter subclass sees in PositionIncrementAttribute on route tokens (no longer the stream's value), the concern raised by a cross-model review and the adjudication.

What the checks validated

The new test 6 of 6, the finder's 4 of 4, the independent reproducer's 9 of 9 (also re-run by the adjudication), the 19 upstream TestGraphTokenFilter and TestFixedShingleFilter tests; the exhaustive model: 18,180 duplicate-only checks.

Remember the increment of the first token of the stack at each route depth, and use it for a route token whose increment is 0 (+12 lines in FixedShingleFilter.java).

Trade-offs

No base-class change, and it fixes the headline stacked shape, but not the multi-position one: the successor's correct increment is not visible to the subclass. The duplicate skip of A3 can be added to it.

What the checks validated

The new test 5 of 6 (the multi-position test still gives login _); the exhaustive model: 136,458 checks still differ, all with position length > 1 or duplicate-only.

Say in the javadoc that fillers count from the previous token in the stream.

Trade-offs

Not recommended: it documents output that depends on an undefined token order.

Method: bounded-exhaustive translation validation on the stock main jars (semi-formal), then a JUnit.

• The hunt unit on regressions around recent fixes started from the #16577 fix to FixedShingleFilter and checked the filter against an independent reference that enumerates every path through the token graph, with hole semantics taken from core TokenStreamToAutomaton (one filler per empty position).
• Scope (a bounded model): every token stream of 1-5 tokens with position increments 0-2, position lengths 1-3 and final increment 0-1, fixed distinct terms and fixed offsets (88,572 streams) at shingle sizes 2-4: 265,716 checks, 146,634 mismatching, all with a stacked group right after a gap or a multi-position token whose last covered position starts no token.
• A side check drove GraphTokenFilter through a minimal subclass: its route enumeration matched the reference exactly (0 route mismatches; 50,712 on a deliberate mutant).
• An AI finder reduced it to a 4-test public-API JUnit with stock filters; independent AI tools then reproduced, reviewed and judged it (see the checks).