Fix cross-doc leakage in nested WithinSpans
Change-Id: I686e8ed339aa833c94df39d09cf87f052fd86541
diff --git a/Changes b/Changes
index 80a5ed3..a5366f3 100644
--- a/Changes
+++ b/Changes
@@ -1,11 +1,13 @@
-0.65.1 2026-06-10
+0.65.1 2026-06-16
- [feature] Prevent indexation of documents without
a token stream (diewald; AI-assisted Claude Opus 4.6)
- [bugfix] Fix "force" in commit method
(diewald; AI-assisted Claude Opus 4.6)
- [tool] Add standalone MetaExporter tool
(kupietz; AI-assistend Claude Opus 4.8)
-
+ - [bugfix] Fix cross-doc leakage in nested WithinSpans
+ (diewald; AI-assisted Claude Opus 4.6)
+
0.65 2026-05-12
- [bugfix] Keep highlights that extend beyond a cut match
(diewald; fixes #177; AI-assisted Claude Opus 4.6)
diff --git a/src/main/java/de/ids_mannheim/korap/query/spans/WithinSpans.java b/src/main/java/de/ids_mannheim/korap/query/spans/WithinSpans.java
index fe507d9..bfdfefa 100644
--- a/src/main/java/de/ids_mannheim/korap/query/spans/WithinSpans.java
+++ b/src/main/java/de/ids_mannheim/korap/query/spans/WithinSpans.java
@@ -204,17 +204,31 @@
log.trace("In the next embedded branch");
WithinSpan current = null;
+ WithinSpan candidate;
- // New - fetch until theres a span in the correct doc or bigger
+ // Skip stale entries, stop at future documents
while (!this.spanStore2.isEmpty()) {
- current = spanStore2.removeFirst();
- if (current.doc >= this.wrapDoc)
+ candidate = spanStore2.peekFirst();
+ if (candidate.doc < this.wrapDoc) {
+ spanStore2.removeFirst();
+ }
+ else if (candidate.doc == this.wrapDoc) {
+ current = spanStore2.removeFirst();
break;
- };
+ }
+ else {
+ break;
+ }
+ }
-
- // There is nothing in the second store
if (current == null) {
+
+ // Future-doc entries remain: advance wrap instead
+ if (!this.spanStore2.isEmpty()) {
+ this.nextSpanA();
+ continue;
+ }
+
if (DEBUG)
log.trace("SpanStore 2 is empty");
@@ -626,32 +640,49 @@
log.trace("skipTo document {}/{} -> {}", this.embeddedDoc,
this.wrapDoc, target);
- // Initialize spans
if (!this.init())
return false;
- assert target > this.embeddedDoc;
+ // Already at or past target: just find next match
+ if (this.matchDoc >= target)
+ return this.next() && this.matchDoc >= target;
- // Only forward embedded spans
- if (this.more && (this.embeddedDoc < target)) {
- if (this.embeddedSpans.skipTo(target)) {
- this.inSameDoc = false;
- this.embeddedStart = -1;
- this.embeddedEnd = -1;
- this.embeddedPayload = null;
- this.embeddedDoc = this.embeddedSpans.doc();
- }
+ // Fast-forward operands when both are behind target
+ if (this.embeddedDoc >= 0 && this.wrapDoc < target
+ && this.embeddedDoc < target) {
- // Can't be skipped to target
- else {
- this.inSameDoc = false;
- this.more = false;
+ if (!this.wrapSpans.skipTo(target))
return false;
- };
- };
+ this.wrapDoc = this.wrapSpans.doc();
+ if (this.wrapDoc == DocIdSetIterator.NO_MORE_DOCS)
+ return false;
- // Move to same doc
- return this.toSameDoc();
+ if (!this.embeddedSpans.skipTo(this.wrapDoc))
+ return false;
+ this.embeddedDoc = this.embeddedSpans.doc();
+ if (this.embeddedDoc == DocIdSetIterator.NO_MORE_DOCS)
+ return false;
+
+ // Reset internal state after skip
+ this.spanStore1.clear();
+ this.spanStore2.clear();
+ this.wrapStart = this.wrapSpans.start();
+ this.embeddedStart = this.embeddedSpans.start();
+ this.wrapEnd = -1;
+ this.embeddedEnd = -1;
+ this.embeddedPayload = null;
+ this.inSameDoc = (this.wrapDoc == this.embeddedDoc);
+ this.more = true;
+ this.tryMatch = true;
+ this.nextSpanB = true;
+ }
+
+ while (true) {
+ if (!this.next())
+ return false;
+ if (this.matchDoc >= target)
+ return true;
+ }
};
diff --git a/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java b/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
index b7c2416..0f18b1b 100644
--- a/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
+++ b/src/test/java/de/ids_mannheim/korap/index/TestWithinIndex.java
@@ -3,27 +3,46 @@
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
+import static org.junit.Assume.assumeTrue;
import java.io.*;
import java.net.URLDecoder;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+import java.util.TreeSet;
+
import static de.ids_mannheim.korap.TestSimple.*;
import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermContext;
+import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.search.spans.SpanQuery;
+import org.apache.lucene.search.spans.Spans;
import org.apache.lucene.search.spans.SpanTermQuery;
+import org.apache.lucene.util.Bits;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
+import de.ids_mannheim.korap.Krill;
+import de.ids_mannheim.korap.KrillCollection;
import de.ids_mannheim.korap.KrillIndex;
import de.ids_mannheim.korap.KrillQuery;
+import de.ids_mannheim.korap.collection.CollectionBuilder;
import de.ids_mannheim.korap.query.QueryBuilder;
import de.ids_mannheim.korap.query.SpanClassQuery;
import de.ids_mannheim.korap.query.SpanElementQuery;
+import de.ids_mannheim.korap.query.SpanFocusQuery;
import de.ids_mannheim.korap.query.wrap.SpanQueryWrapper;
import de.ids_mannheim.korap.query.SpanNextQuery;
import de.ids_mannheim.korap.query.SpanWithinQuery;
import de.ids_mannheim.korap.query.wrap.SpanQueryWrapper;
+import de.ids_mannheim.korap.response.Match;
import de.ids_mannheim.korap.response.Result;
import de.ids_mannheim.korap.util.QueryException;
@@ -1169,4 +1188,890 @@
Result kr = ki.search(sq, (short) 1);
assertEquals(1, kr.getTotalResults());
}
+
+
+ // Build one "tokens" FieldDocument from sentence token arrays.
+ // Each input array is one sentence, e.g. ["b","a","w2"].
+ // Example doc: [["b","a","w2"],["a","w4","w5"]].
+ private FieldDocument multiSentenceDoc (String[]... sentences) {
+ FieldDocument fd = new FieldDocument();
+
+ int total = 0;
+ for (String[] s : sentences) total += s.length;
+
+ StringBuilder surface = new StringBuilder();
+ StringBuilder tv = new StringBuilder();
+
+ int tokIdx = 0;
+ int charOff = 0;
+ int sentStart = 0;
+
+ for (int si = 0; si < sentences.length; si++) {
+ String[] sent = sentences[si];
+ int sentEnd = sentStart + sent.length;
+
+ for (int ti = 0; ti < sent.length; ti++) {
+ String tok = sent[ti];
+ int cStart = charOff;
+ int cEnd = charOff + tok.length();
+
+ surface.append(tok);
+
+ tv.append("[(").append(cStart).append("-").append(cEnd)
+ .append(")");
+ tv.append("s:").append(tok);
+
+ if (tokIdx == 0) {
+ int totalChars = 0;
+ for (String[] s : sentences)
+ for (String t : s)
+ totalChars += t.length();
+ tv.append("|-:t$<i>").append(total);
+ tv.append("|<>:base/s:t$<b>64<i>0<i>")
+ .append(totalChars).append("<i>")
+ .append(total).append("<b>0");
+ }
+ if (ti == 0) {
+ int sentCharEnd = cStart;
+ for (String t : sent) sentCharEnd += t.length();
+ tv.append("|<>:base/s:s$<b>64<i>")
+ .append(cStart).append("<i>")
+ .append(sentCharEnd).append("<i>")
+ .append(sentEnd).append("<b>1");
+ }
+
+ tv.append("|_").append(tokIdx).append("$<i>")
+ .append(cStart).append("<i>").append(cEnd);
+ tv.append("]");
+
+ charOff = cEnd;
+ tokIdx++;
+ }
+ sentStart = sentEnd;
+ }
+
+ fd.addTV("tokens", surface.toString(), tv.toString());
+ return fd;
+ }
+
+ // focus(1: contains(contains(<s>, {1: s:a}), {2: s:b}))
+ private SpanQuery nestedContainsDiffClassQuery () {
+ SpanQuery sentence = new SpanElementQuery("tokens", "base/s:s");
+ SpanQuery tokenA = new SpanClassQuery(
+ new SpanTermQuery(new Term("tokens", "s:a")), (byte) 1);
+ SpanQuery tokenB = new SpanClassQuery(
+ new SpanTermQuery(new Term("tokens", "s:b")), (byte) 2);
+ SpanQuery innerContains = new SpanWithinQuery(sentence, tokenA);
+ SpanQuery outerContains = new SpanWithinQuery(innerContains, tokenB);
+ SpanFocusQuery focus = new SpanFocusQuery(outerContains, (byte) 1);
+ focus.setSorted(false);
+ return focus;
+ }
+
+ /**
+ * Two docs in one segment where doc 1 has b in a separate sentence.
+ * The fix prevents b from leaking into doc 0's a-only sentence.
+ */
+ @Test
+ public void testNestedContainsSameSegmentCrossDocLeakage ()
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+
+ // Doc 0: S0 has b+a, S1 has a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "b", "a", "w2" },
+ new String[] { "a", "w4", "w5" }));
+
+ // Doc 1: S0 has a only, S1 has b only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2" },
+ new String[] { "b", "w4", "w5" }));
+
+ ki.commit();
+
+ Result kr = ki.search(nestedContainsDiffClassQuery(), (short) 50);
+ assertEquals("Only Doc 0 S0 has both a+b, expect 1 match",
+ 1, kr.getTotalResults());
+ assertEquals(1, kr.getMatch(0).getStartPos());
+ assertEquals(2, kr.getMatch(0).getEndPos());
+ ki.close();
+ }
+
+ /**
+ * Same data as above but each doc in its own segment.
+ * Verifies no cross-doc leak with separate segments.
+ */
+ @Test
+ public void testNestedContainsSeparateSegmentsNoLeakage ()
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+
+ // Doc 0: S0 has b+a, S1 has a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "b", "a", "w2" },
+ new String[] { "a", "w4", "w5" }));
+ ki.commit();
+
+ // Doc 1: S0 has a only, S1 has b only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2" },
+ new String[] { "b", "w4", "w5" }));
+ ki.commit();
+
+ Result kr = ki.search(nestedContainsDiffClassQuery(), (short) 50);
+ assertEquals("Separate segments: expect 1 match",
+ 1, kr.getTotalResults());
+ assertEquals(1, kr.getMatch(0).getStartPos());
+ assertEquals(2, kr.getMatch(0).getEndPos());
+ ki.close();
+ }
+
+ /**
+ * Multiple a-only docs then one doc with both a+b in same segment.
+ * B from last doc must not leak into earlier docs.
+ */
+ @Test
+ public void testNestedContainsManyAOnlyDocsThenBoth ()
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+
+ // Doc 0: single sentence with a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2" }));
+ // Doc 1: single sentence with a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "w0", "a", "w2" }));
+ // Doc 2: single sentence with a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2" }));
+ // Doc 3: single sentence with both a and b.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "b", "w2" }));
+
+ ki.commit();
+
+ Result kr = ki.search(nestedContainsDiffClassQuery(), (short) 50);
+ assertEquals("Only Doc 3 has both, expect 1 match",
+ 1, kr.getTotalResults());
+ assertEquals(0, kr.getMatch(0).getStartPos());
+ assertEquals(1, kr.getMatch(0).getEndPos());
+ ki.close();
+ }
+
+ /**
+ * Multi-sentence a-only doc then doc with a+b in one sentence.
+ * Tests scenario from fuzz seed 125901200207375.
+ */
+ @Test
+ public void testNestedContainsMultiSentenceAOnlyThenBoth ()
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+
+ // Doc 0: two sentences, both are a only.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "w0", "w1", "a", "w3", "w4" },
+ new String[] { "w5", "a", "w7", "w8", "w9" }));
+
+ // Doc 1: one sentence with both a and b.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2", "b", "w4" }));
+
+ ki.commit();
+
+ Result kr = ki.search(nestedContainsDiffClassQuery(), (short) 50);
+ assertEquals("Only Doc 1 has both a+b, expect 1 match",
+ 1, kr.getTotalResults());
+ assertEquals(0, kr.getMatch(0).getStartPos());
+ assertEquals(1, kr.getMatch(0).getEndPos());
+ ki.close();
+ }
+
+ // Regression: skipTo() must also work before first next().
+ @Test
+ public void testWithinSkipToBeforeNextInitializesSpans ()
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+
+ // One local doc with a single sentence that contains token a.
+ ki.addDoc(multiSentenceDoc(
+ new String[] { "a", "w1", "w2" }));
+ ki.commit();
+
+ SpanQuery sq = new SpanWithinQuery(
+ new SpanElementQuery("tokens", "base/s:s"),
+ new SpanTermQuery(new Term("tokens", "s:a")));
+
+ Map<Term, TermContext> termContexts = new HashMap<>();
+ for (LeafReaderContext atomic : ki.reader().leaves()) {
+ Bits bitset = atomic.reader().getLiveDocs();
+ Spans spans = sq.getSpans(atomic, bitset, termContexts);
+ assertTrue("skipTo() before next() must initialize spans",
+ spans.skipTo(0));
+ assertEquals(0, spans.doc());
+ assertEquals(0, spans.start());
+ assertEquals(3, spans.end());
+ }
+
+ ki.close();
+ }
+
+ // ----------------------------------------------------------------------
+ // Fuzzing tests for nested contains + focus
+ //
+ // Call with:
+ // $ mvn test -Dtest="TestWithinIndex" -Dfuzz.iterations=200 -pl .
+ // ----------------------------------------------------------------------
+
+ // Read iteration count; default 0 keeps fuzz tests disabled.
+ private static int getFuzzIterations () {
+ String prop = System.getProperty("fuzz.iterations");
+ if (prop != null) return Integer.parseInt(prop);
+ return 0;
+ }
+
+ // Read optional seed; default uses current nano time.
+ private static long getFuzzBaseSeed () {
+ String prop = System.getProperty("fuzz.seed");
+ if (prop != null) return Long.parseLong(prop);
+ return System.nanoTime();
+ }
+
+ enum BiasStrategy {
+ UNIFORM,
+ HEAVY_A_RARE_B,
+ ALTERNATING,
+ CLUSTER,
+ DENSE
+ }
+
+ static class SentenceInfo {
+ final int startPos;
+ final int endPos;
+ final List<Integer> aPositions;
+ final List<Integer> bPositions;
+
+ SentenceInfo (int startPos, int endPos,
+ List<Integer> aPositions, List<Integer> bPositions) {
+ this.startPos = startPos;
+ this.endPos = endPos;
+ this.aPositions = aPositions;
+ this.bPositions = bPositions;
+ }
+
+ boolean hasA () { return !aPositions.isEmpty(); }
+ boolean hasB () { return !bPositions.isEmpty(); }
+ boolean hasBoth () { return hasA() && hasB(); }
+ }
+
+ static class DocInfo {
+ final String textSigle;
+ final String genre;
+ final List<SentenceInfo> sentences;
+
+ DocInfo (String textSigle, String genre,
+ List<SentenceInfo> sentences) {
+ this.textSigle = textSigle;
+ this.genre = genre;
+ this.sentences = sentences;
+ }
+ }
+
+ static class IndexConfig {
+ final List<DocInfo> docs;
+ final int[] commitAfterDoc;
+ final long seed;
+ final BiasStrategy strategy;
+
+ IndexConfig (List<DocInfo> docs, int[] commitAfterDoc,
+ long seed, BiasStrategy strategy) {
+ this.docs = docs;
+ this.commitAfterDoc = commitAfterDoc;
+ this.seed = seed;
+ this.strategy = strategy;
+ }
+ }
+
+ // Generate one random fuzz corpus with a random bias strategy.
+ private IndexConfig generateFuzzConfig (long seed) {
+ Random rng = new Random(seed);
+ BiasStrategy[] strategies = BiasStrategy.values();
+ BiasStrategy strategy = strategies[rng.nextInt(strategies.length)];
+ return generateFuzzConfig(seed, rng, strategy);
+ }
+
+ // Generate one random fuzz corpus using a fixed strategy.
+ private IndexConfig generateFuzzConfig (long seed, Random rng,
+ BiasStrategy strategy) {
+ int numDocs = 1 + rng.nextInt(5);
+ List<DocInfo> docs = new ArrayList<>();
+
+ for (int d = 0; d < numDocs; d++) {
+ int numSentences = 2 + rng.nextInt(14);
+ List<SentenceInfo> sentences = new ArrayList<>();
+ int docTokenPos = 0;
+
+ for (int s = 0; s < numSentences; s++) {
+ int sentLen = decideSentenceLength(rng, strategy);
+ int sentStart = docTokenPos;
+ int sentEnd = docTokenPos + sentLen;
+
+ boolean placeA = decidePlaceA(rng, strategy, s, numSentences);
+ boolean placeB = decidePlaceB(rng, strategy, s, numSentences);
+
+ int numA = placeA ? (1 + rng.nextInt(
+ strategy == BiasStrategy.DENSE ? 3 : 2)) : 0;
+ int numB = placeB ? (1 + rng.nextInt(
+ strategy == BiasStrategy.DENSE ? 3 : 2)) : 0;
+ numA = Math.min(numA, sentLen / 2);
+ numB = Math.min(numB, Math.max(0, sentLen - numA));
+
+ Set<Integer> usedOffsets = new HashSet<>();
+ List<Integer> aPositions = new ArrayList<>();
+ List<Integer> bPositions = new ArrayList<>();
+
+ for (int i = 0; i < numA; i++) {
+ int off = pickUnusedOffset(rng, sentLen, usedOffsets);
+ if (off >= 0) {
+ usedOffsets.add(off);
+ aPositions.add(sentStart + off);
+ }
+ }
+ for (int i = 0; i < numB; i++) {
+ int off = pickUnusedOffset(rng, sentLen, usedOffsets);
+ if (off >= 0) {
+ usedOffsets.add(off);
+ bPositions.add(sentStart + off);
+ }
+ }
+
+ sentences.add(new SentenceInfo(sentStart, sentEnd,
+ aPositions, bPositions));
+ docTokenPos = sentEnd;
+ }
+
+ String genre = (d % 3 == 0) ? "science"
+ : (d % 3 == 1) ? "fiction" : "news";
+ docs.add(new DocInfo("TST/D" + d + "/T0", genre, sentences));
+ }
+
+ int[] commitAfterDoc = decideCommitPoints(rng, numDocs);
+ return new IndexConfig(docs, commitAfterDoc, seed, strategy);
+ }
+
+ // Choose sentence length for one random sentence.
+ private int decideSentenceLength (Random rng, BiasStrategy strategy) {
+ if (strategy == BiasStrategy.DENSE) {
+ return 6 + rng.nextInt(10);
+ }
+ int r = rng.nextInt(100);
+ if (r < 5) return 2 + rng.nextInt(2);
+ if (r < 15) return 20 + rng.nextInt(11);
+ return 3 + rng.nextInt(15);
+ }
+
+ // Decide if sentence gets at least one a token.
+ private boolean decidePlaceA (Random rng, BiasStrategy strategy,
+ int sentIdx, int numSentences) {
+ switch (strategy) {
+ case HEAVY_A_RARE_B:
+ return rng.nextDouble() < 0.9;
+ case ALTERNATING:
+ return sentIdx % 2 == 0 || rng.nextDouble() < 0.15;
+ case CLUSTER:
+ return sentIdx < numSentences / 2 || rng.nextDouble() < 0.2;
+ case DENSE:
+ return true;
+ default:
+ return rng.nextDouble() < 0.6;
+ }
+ }
+
+ // Decide if sentence gets at least one b token.
+ private boolean decidePlaceB (Random rng, BiasStrategy strategy,
+ int sentIdx, int numSentences) {
+ switch (strategy) {
+ case HEAVY_A_RARE_B:
+ return rng.nextDouble() < 0.1;
+ case ALTERNATING:
+ return sentIdx % 2 == 1 || rng.nextDouble() < 0.15;
+ case CLUSTER:
+ return sentIdx >= numSentences / 2 || rng.nextDouble() < 0.2;
+ case DENSE:
+ return true;
+ default:
+ return rng.nextDouble() < 0.4;
+ }
+ }
+
+ // Pick a random token offset not used yet in sentence.
+ private int pickUnusedOffset (Random rng, int sentLen,
+ Set<Integer> used) {
+ if (used.size() >= sentLen) return -1;
+ for (int attempt = 0; attempt < 20; attempt++) {
+ int pos = rng.nextInt(sentLen);
+ if (!used.contains(pos)) return pos;
+ }
+ for (int pos = 0; pos < sentLen; pos++) {
+ if (!used.contains(pos)) return pos;
+ }
+ return -1;
+ }
+
+ // Choose where to commit so we get multiple segment layouts.
+ private int[] decideCommitPoints (Random rng, int numDocs) {
+ if (numDocs <= 1) return new int[] { 0 };
+ List<Integer> points = new ArrayList<>();
+ for (int d = 0; d < numDocs; d++) {
+ if (d == numDocs - 1 || rng.nextDouble() < 0.4) {
+ points.add(d);
+ }
+ }
+ if (!points.contains(numDocs - 1)) points.add(numDocs - 1);
+ int[] result = new int[points.size()];
+ for (int i = 0; i < result.length; i++) result[i] = points.get(i);
+ return result;
+ }
+
+ // Build a KrillIndex from generated docs and commit plan.
+ private KrillIndex buildFuzzIndex (IndexConfig config)
+ throws IOException {
+ KrillIndex ki = new KrillIndex();
+ int commitIdx = 0;
+
+ for (int d = 0; d < config.docs.size(); d++) {
+ DocInfo doc = config.docs.get(d);
+ FieldDocument fd = buildFuzzFieldDocument(doc);
+ ki.addDoc(fd);
+
+ if (commitIdx < config.commitAfterDoc.length
+ && config.commitAfterDoc[commitIdx] == d) {
+ ki.commit();
+ commitIdx++;
+ }
+ }
+
+ if (commitIdx == 0 || config.commitAfterDoc[commitIdx - 1]
+ != config.docs.size() - 1) {
+ ki.commit();
+ }
+
+ return ki;
+ }
+
+ // Convert one generated doc into a tokens field with TV data.
+ private FieldDocument buildFuzzFieldDocument (DocInfo doc) {
+ FieldDocument fd = new FieldDocument();
+ fd.addString("textSigle", doc.textSigle);
+ fd.addString("genre", doc.genre);
+
+ Set<Integer> aPositions = new HashSet<>();
+ Set<Integer> bPositions = new HashSet<>();
+ for (SentenceInfo sent : doc.sentences) {
+ aPositions.addAll(sent.aPositions);
+ bPositions.addAll(sent.bPositions);
+ }
+
+ int totalTokens = 0;
+ for (SentenceInfo sent : doc.sentences) {
+ totalTokens += (sent.endPos - sent.startPos);
+ }
+
+ String[] allTokens = new String[totalTokens];
+ int idx = 0;
+ for (SentenceInfo sent : doc.sentences) {
+ for (int pos = sent.startPos; pos < sent.endPos; pos++) {
+ if (aPositions.contains(pos)) {
+ allTokens[idx] = "a";
+ }
+ else if (bPositions.contains(pos)) {
+ allTokens[idx] = "b";
+ }
+ else {
+ allTokens[idx] = "w" + pos;
+ }
+ idx++;
+ }
+ }
+
+ int totalChars = 0;
+ for (String t : allTokens) totalChars += t.length();
+
+ StringBuilder surface = new StringBuilder();
+ StringBuilder tv = new StringBuilder();
+
+ int tokIdx = 0;
+ int charOff = 0;
+
+ for (int si = 0; si < doc.sentences.size(); si++) {
+ SentenceInfo sent = doc.sentences.get(si);
+ int sentLen = sent.endPos - sent.startPos;
+
+ int sentCharStart = charOff;
+ int sentCharEnd = sentCharStart;
+ for (int ti = 0; ti < sentLen; ti++) {
+ sentCharEnd += allTokens[tokIdx + ti].length();
+ }
+
+ for (int ti = 0; ti < sentLen; ti++) {
+ String tok = allTokens[tokIdx + ti];
+ int cStart = charOff;
+ int cEnd = charOff + tok.length();
+ surface.append(tok);
+
+ tv.append("[(").append(cStart).append("-").append(cEnd)
+ .append(")");
+ tv.append("s:").append(tok);
+
+ if (tokIdx + ti == 0) {
+ tv.append("|-:t$<i>").append(totalTokens);
+ tv.append("|<>:base/s:t$<b>64<i>0<i>")
+ .append(totalChars).append("<i>")
+ .append(totalTokens).append("<b>0");
+ }
+
+ if (ti == 0) {
+ tv.append("|<>:base/s:s$<b>64<i>")
+ .append(sentCharStart).append("<i>")
+ .append(sentCharEnd).append("<i>")
+ .append(sent.endPos).append("<b>1");
+ }
+
+ tv.append("|_").append(tokIdx + ti).append("$<i>")
+ .append(cStart).append("<i>").append(cEnd);
+ tv.append("]");
+
+ charOff = cEnd;
+ }
+ tokIdx += sentLen;
+ }
+
+ fd.addTV("tokens", surface.toString(), tv.toString());
+ return fd;
+ }
+
+ // focus(1: contains(contains(<s>, {1: a}), {1: b}))
+ private SpanQuery nestedContainsSameClassQuery () {
+ SpanQuery sentence = new SpanElementQuery("tokens", "base/s:s");
+ SpanQuery tokenA = new SpanClassQuery(
+ new SpanTermQuery(new Term("tokens", "s:a")), (byte) 1);
+ SpanQuery tokenB = new SpanClassQuery(
+ new SpanTermQuery(new Term("tokens", "s:b")), (byte) 1);
+ SpanQuery innerContains = new SpanWithinQuery(sentence, tokenA);
+ SpanQuery outerContains = new SpanWithinQuery(innerContains, tokenB);
+ SpanFocusQuery focus = new SpanFocusQuery(outerContains, (byte) 1);
+ focus.setSorted(false);
+ return focus;
+ }
+
+ // Collect all a positions from sentences that also contain b.
+ private Set<Integer> expectedAPositions (DocInfo doc) {
+ Set<Integer> result = new TreeSet<>();
+ for (SentenceInfo sent : doc.sentences) {
+ if (sent.hasBoth()) {
+ result.addAll(sent.aPositions);
+ }
+ }
+ return result;
+ }
+
+ // Collect all a positions in one generated document.
+ private Set<Integer> allAPositions (DocInfo doc) {
+ Set<Integer> result = new TreeSet<>();
+ for (SentenceInfo sent : doc.sentences) {
+ result.addAll(sent.aPositions);
+ }
+ return result;
+ }
+
+ // Collect all a and b positions in one generated document.
+ private Set<Integer> allABPositions (DocInfo doc) {
+ Set<Integer> result = new TreeSet<>();
+ for (SentenceInfo sent : doc.sentences) {
+ result.addAll(sent.aPositions);
+ result.addAll(sent.bPositions);
+ }
+ return result;
+ }
+
+ // Check invariants for focus(class1) over different class ids.
+ private void verifyDiffClassInvariants (Result kr,
+ IndexConfig config, String context) {
+
+ Set<Integer> anyDocExpectedA = new TreeSet<>();
+ for (DocInfo doc : config.docs) {
+ anyDocExpectedA.addAll(expectedAPositions(doc));
+ }
+
+ Set<Integer> matchedPositions = new TreeSet<>();
+ int storedMatches = kr.getMatches().size();
+
+ for (int i = 0; i < storedMatches; i++) {
+ Match m = kr.getMatch(i);
+ int mStart = m.getStartPos();
+ int mEnd = m.getEndPos();
+
+ assertTrue(context + ": Match " + i + " [" + mStart + ","
+ + mEnd + ") must be single token (end==start+1)",
+ mEnd == mStart + 1);
+
+ boolean validInSomeDoc = false;
+ for (DocInfo doc : config.docs) {
+ if (allAPositions(doc).contains(mStart)
+ && expectedAPositions(doc).contains(mStart)) {
+ validInSomeDoc = true;
+ break;
+ }
+ }
+ assertTrue(context + ": Match " + i + " start=" + mStart
+ + " must be a valid 'a' in a sentence with 'b'",
+ validInSomeDoc);
+
+ matchedPositions.add(mStart);
+ }
+
+ if (config.docs.size() == 1
+ && kr.getTotalResults() == storedMatches) {
+ Set<Integer> expected = expectedAPositions(config.docs.get(0));
+ for (int pos : expected) {
+ assertTrue(context + ": Expected 'a' at position "
+ + pos + " not found in results",
+ matchedPositions.contains(pos));
+ }
+ }
+ }
+
+ // Check invariants for focus(class1) with shared class ids.
+ private void verifySameClassInvariants (Result kr,
+ IndexConfig config, String context) {
+
+ int storedMatches = kr.getMatches().size();
+ for (int i = 0; i < storedMatches; i++) {
+ Match m = kr.getMatch(i);
+ int mStart = m.getStartPos();
+ int mEnd = m.getEndPos();
+
+ boolean validInSomeDoc = false;
+ for (DocInfo doc : config.docs) {
+ Set<Integer> abPos = allABPositions(doc);
+
+ if (!abPos.contains(mStart)) continue;
+ if (!abPos.contains(mEnd - 1)) continue;
+
+ boolean withinSentence = false;
+ boolean sentHasBoth = false;
+ for (SentenceInfo sent : doc.sentences) {
+ if (mStart >= sent.startPos && mEnd <= sent.endPos) {
+ withinSentence = true;
+ sentHasBoth = sent.hasBoth();
+ break;
+ }
+ }
+ if (withinSentence && sentHasBoth) {
+ validInSomeDoc = true;
+ break;
+ }
+ }
+
+ assertTrue(context + ": Match " + i + " [" + mStart + ","
+ + mEnd + ") failed same-class invariants",
+ validInSomeDoc);
+ }
+ }
+
+ // Check diff-class invariants after virtual corpus filtering.
+ private void verifyDiffClassInvariantsFiltered (Result kr,
+ IndexConfig config, Set<String> includedSigles,
+ String context) {
+
+ int storedMatches = kr.getMatches().size();
+ for (int i = 0; i < storedMatches; i++) {
+ Match m = kr.getMatch(i);
+ int mStart = m.getStartPos();
+ int mEnd = m.getEndPos();
+
+ assertTrue(context + ": Match " + i + " [" + mStart + ","
+ + mEnd + ") must be single token",
+ mEnd == mStart + 1);
+
+ boolean validInFilteredDoc = false;
+ for (DocInfo doc : config.docs) {
+ if (!includedSigles.contains(doc.textSigle)) continue;
+ if (expectedAPositions(doc).contains(mStart)) {
+ validInFilteredDoc = true;
+ break;
+ }
+ }
+ assertTrue(context + ": Match " + i + " start=" + mStart
+ + " must be valid 'a' in filtered docs",
+ validInFilteredDoc);
+ }
+ }
+
+ // Function type used by fuzzLoop for one seeded iteration.
+ @FunctionalInterface
+ interface FuzzAction {
+ void run (long seed) throws Exception;
+ }
+
+ // Run a fuzz action over N seeds and print reproducible failures.
+ private void fuzzLoop (String testName, FuzzAction action) {
+ int iterations = getFuzzIterations();
+ assumeTrue("Fuzz tests skipped (set -Dfuzz.iterations=N to run)",
+ iterations > 0);
+ long baseSeed = getFuzzBaseSeed();
+
+ for (int i = 0; i < iterations; i++) {
+ long seed = baseSeed + i;
+ try {
+ action.run(seed);
+ }
+ catch (AssertionError e) {
+ throw new AssertionError(
+ "FUZZ FAILURE [" + testName + "] iteration="
+ + i + " seed=" + seed + "\n"
+ + "Reproduce: -Dfuzz.seed=" + seed
+ + " -Dfuzz.iterations=1", e);
+ }
+ catch (Exception e) {
+ throw new AssertionError(
+ "FUZZ ERROR [" + testName + "] iteration="
+ + i + " seed=" + seed, e);
+ }
+ }
+ }
+
+ // Fuzz test: class1 focus with inner class1 and outer class2.
+ @Test
+ public void fuzzNestedContainsDiffClass () {
+ fuzzLoop("fuzzNestedContainsDiffClass", seed -> {
+ IndexConfig config = generateFuzzConfig(seed);
+ KrillIndex ki = buildFuzzIndex(config);
+ try {
+ Result kr = ki.search(
+ nestedContainsDiffClassQuery(), (short) 500);
+ verifyDiffClassInvariants(kr, config,
+ "seed=" + seed + " strategy=" + config.strategy);
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
+
+ // Fuzz test: class1 focus with both terms in class1.
+ @Test
+ public void fuzzNestedContainsSameClass () {
+ fuzzLoop("fuzzNestedContainsSameClass", seed -> {
+ IndexConfig config = generateFuzzConfig(seed);
+ KrillIndex ki = buildFuzzIndex(config);
+ try {
+ Result kr = ki.search(
+ nestedContainsSameClassQuery(), (short) 500);
+ verifySameClassInvariants(kr, config,
+ "seed=" + seed + " strategy=" + config.strategy);
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
+
+ // Fuzz test: force one commit per doc to maximize segment count.
+ @Test
+ public void fuzzNestedContainsMultiSegment () {
+ fuzzLoop("fuzzNestedContainsMultiSegment", seed -> {
+ Random rng = new Random(seed);
+ BiasStrategy strategy = BiasStrategy.values()[
+ rng.nextInt(BiasStrategy.values().length)];
+ IndexConfig config = generateFuzzConfig(seed, rng, strategy);
+
+ int numDocs = config.docs.size();
+ int[] manyCommits = new int[numDocs];
+ for (int d = 0; d < numDocs; d++) manyCommits[d] = d;
+ IndexConfig multiSegConfig = new IndexConfig(
+ config.docs, manyCommits, seed, strategy);
+
+ KrillIndex ki = buildFuzzIndex(multiSegConfig);
+ try {
+ Result kr = ki.search(
+ nestedContainsDiffClassQuery(), (short) 500);
+ verifyDiffClassInvariants(kr, multiSegConfig,
+ "seed=" + seed + " strategy=" + strategy);
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
+
+ // Fuzz test: run diff-class query on a filtered virtual corpus.
+ @Test
+ public void fuzzNestedContainsVirtualCorpus () {
+ fuzzLoop("fuzzNestedContainsVirtualCorpus", seed -> {
+ IndexConfig config = generateFuzzConfig(seed);
+ if (config.docs.size() < 2) return;
+
+ KrillIndex ki = buildFuzzIndex(config);
+ try {
+ String targetSigle = config.docs.get(0).textSigle;
+ Set<String> included = new HashSet<>();
+ included.add(targetSigle);
+
+ Krill ks = new Krill(nestedContainsDiffClassQuery());
+ ks.getMeta().setCount((short) 500);
+
+ CollectionBuilder cb = new CollectionBuilder();
+ KrillCollection kc = new KrillCollection(ki);
+ kc.fromBuilder(cb.term("textSigle", targetSigle));
+ ks.setCollection(kc);
+
+ Result kr = ks.apply(ki);
+ verifyDiffClassInvariantsFiltered(kr, config, included,
+ "seed=" + seed + " vc_sigle=" + targetSigle);
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
+
+ // Fuzz test: heavy backtracking setup with many a and rare b.
+ @Test
+ public void fuzzNestedContainsHeavyBacktracking () {
+ fuzzLoop("fuzzNestedContainsHeavyBacktracking", seed -> {
+ Random rng = new Random(seed);
+ IndexConfig config = generateFuzzConfig(seed, rng,
+ BiasStrategy.HEAVY_A_RARE_B);
+ KrillIndex ki = buildFuzzIndex(config);
+ try {
+ Result kr = ki.search(
+ nestedContainsDiffClassQuery(), (short) 500);
+ verifyDiffClassInvariants(kr, config,
+ "seed=" + seed + " strategy=HEAVY_A_RARE_B");
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
+
+ // Fuzz test: dense setup where almost every sentence has a and b.
+ @Test
+ public void fuzzNestedContainsDense () {
+ fuzzLoop("fuzzNestedContainsDense", seed -> {
+ Random rng = new Random(seed);
+ IndexConfig config = generateFuzzConfig(seed, rng,
+ BiasStrategy.DENSE);
+ KrillIndex ki = buildFuzzIndex(config);
+ try {
+ Result kr = ki.search(
+ nestedContainsDiffClassQuery(), (short) 500);
+ verifyDiffClassInvariants(kr, config,
+ "seed=" + seed + " strategy=DENSE");
+ }
+ finally {
+ ki.close();
+ }
+ });
+ }
};