You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ta...@apache.org on 2026/08/13 19:55:43 UTC
(lucene) 01/01: Add docIDRunEnd contract tests for DV formats
This is an automated email from the ASF dual-hosted git repository.
tballison pushed a commit to branch docidrunend-format-contract
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 10c7aa40dc244957dca4c3add6e689b81a2be2c9
Author: tballison <ti...@elastic.co>
AuthorDate: Thu Aug 13 15:55:25 2026 -0400
Add docIDRunEnd contract tests for DV formats
---
.../tests/index/BaseDocValuesFormatTestCase.java | 266 +++++++++++++++++++++
1 file changed, 266 insertions(+)
diff --git a/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseDocValuesFormatTestCase.java b/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseDocValuesFormatTestCase.java
index 70bff46d76c..1531a06b9e8 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseDocValuesFormatTestCase.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/tests/index/BaseDocValuesFormatTestCase.java
@@ -53,6 +53,8 @@ import org.apache.lucene.index.Term;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.index.TermsEnum.SeekStatus;
import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.TwoPhaseIterator;
import org.apache.lucene.store.Directory;
import org.apache.lucene.tests.analysis.MockAnalyzer;
import org.apache.lucene.tests.util.TestUtil;
@@ -60,6 +62,7 @@ import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOFunction;
import org.apache.lucene.util.IOUtils;
+import org.apache.lucene.util.LongBitSet;
/**
* Extends {@link LegacyBaseDocValuesFormatTestCase} and adds checks for {@link DocValuesSkipper}.
@@ -1089,4 +1092,267 @@ public abstract class BaseDocValuesFormatTestCase extends LegacyBaseDocValuesFor
}
}
}
+
+ public void testDocIDRunEndNumericRange() throws Exception {
+ int totalDocs = TestUtil.nextInt(random(), 1, 1500);
+ long domain = TestUtil.nextInt(random(), 5, 100);
+ boolean clustered = random().nextBoolean();
+ int missingOneIn = TestUtil.nextInt(random(), 0, 4);
+ try (Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir)) {
+ for (int i = 0; i < totalDocs; i++) {
+ Document doc = new Document();
+ if (missingOneIn == 0 || random().nextInt(missingOneIn + 1) != 0) {
+ long v = clustered ? i * domain / totalDocs : TestUtil.nextLong(random(), 0, domain);
+ doc.add(NumericDocValuesField.indexedField("f", v));
+ }
+ w.addDocument(doc);
+ }
+ if (random().nextBoolean()) {
+ w.forceMerge(1);
+ }
+ try (IndexReader r = w.getReader()) {
+ for (LeafReaderContext ctx : r.leaves()) {
+ LeafReader leaf = ctx.reader();
+ for (int iter = 0; iter < 10; iter++) {
+ NumericDocValues values = leaf.getNumericDocValues("f");
+ if (values == null) {
+ break;
+ }
+ long a = TestUtil.nextLong(random(), 0, domain);
+ long b = TestUtil.nextLong(random(), 0, domain);
+ long min = Math.min(a, b);
+ long max = Math.max(a, b);
+ TwoPhaseIterator tpi =
+ DocValuesRangeIterator.forRange(values, leaf.getDocValuesSkipper("f"), min, max);
+ FixedBitSet expected = new FixedBitSet(leaf.maxDoc());
+ NumericDocValues truth = leaf.getNumericDocValues("f");
+ for (int d = truth.nextDoc(); d != NO_MORE_DOCS; d = truth.nextDoc()) {
+ long v = truth.longValue();
+ if (v >= min && v <= max) {
+ expected.set(d);
+ }
+ }
+ assertDocIDRunEnds(tpi, expected, leaf.maxDoc());
+ }
+ }
+ }
+ }
+ }
+
+ public void testDocIDRunEndSortedNumericRange() throws Exception {
+ int totalDocs = TestUtil.nextInt(random(), 1, 1500);
+ long domain = TestUtil.nextInt(random(), 5, 100);
+ int missingOneIn = TestUtil.nextInt(random(), 0, 4);
+ try (Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir)) {
+ for (int i = 0; i < totalDocs; i++) {
+ Document doc = new Document();
+ if (missingOneIn == 0 || random().nextInt(missingOneIn + 1) != 0) {
+ int count = TestUtil.nextInt(random(), 1, 2);
+ for (int j = 0; j < count; j++) {
+ doc.add(
+ SortedNumericDocValuesField.indexedField(
+ "f", TestUtil.nextLong(random(), 0, domain)));
+ }
+ }
+ w.addDocument(doc);
+ }
+ if (random().nextBoolean()) {
+ w.forceMerge(1);
+ }
+ try (IndexReader r = w.getReader()) {
+ for (LeafReaderContext ctx : r.leaves()) {
+ LeafReader leaf = ctx.reader();
+ for (int iter = 0; iter < 10; iter++) {
+ SortedNumericDocValues values = leaf.getSortedNumericDocValues("f");
+ if (values == null) {
+ break;
+ }
+ long a = TestUtil.nextLong(random(), 0, domain);
+ long b = TestUtil.nextLong(random(), 0, domain);
+ long min = Math.min(a, b);
+ long max = Math.max(a, b);
+ TwoPhaseIterator tpi =
+ DocValuesRangeIterator.forRange(values, leaf.getDocValuesSkipper("f"), min, max);
+ FixedBitSet expected = new FixedBitSet(leaf.maxDoc());
+ SortedNumericDocValues truth = leaf.getSortedNumericDocValues("f");
+ for (int d = truth.nextDoc(); d != NO_MORE_DOCS; d = truth.nextDoc()) {
+ for (int j = 0; j < truth.docValueCount(); j++) {
+ long v = truth.nextValue();
+ if (v >= min && v <= max) {
+ expected.set(d);
+ break;
+ }
+ }
+ }
+ assertDocIDRunEnds(tpi, expected, leaf.maxDoc());
+ }
+ }
+ }
+ }
+ }
+
+ public void testDocIDRunEndSortedOrdinalRange() throws Exception {
+ int totalDocs = TestUtil.nextInt(random(), 1, 1500);
+ int domain = TestUtil.nextInt(random(), 5, 100);
+ int missingOneIn = TestUtil.nextInt(random(), 0, 4);
+ try (Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir)) {
+ for (int i = 0; i < totalDocs; i++) {
+ Document doc = new Document();
+ if (missingOneIn == 0 || random().nextInt(missingOneIn + 1) != 0) {
+ doc.add(SortedDocValuesField.indexedField("f", randomFixedWidthTerm(domain)));
+ }
+ w.addDocument(doc);
+ }
+ if (random().nextBoolean()) {
+ w.forceMerge(1);
+ }
+ try (IndexReader r = w.getReader()) {
+ for (LeafReaderContext ctx : r.leaves()) {
+ LeafReader leaf = ctx.reader();
+ for (int iter = 0; iter < 10; iter++) {
+ SortedDocValues values = leaf.getSortedDocValues("f");
+ if (values == null || values.getValueCount() == 0) {
+ break;
+ }
+ int a = random().nextInt(values.getValueCount());
+ int b = random().nextInt(values.getValueCount());
+ int minOrd = Math.min(a, b);
+ int maxOrd = Math.max(a, b);
+ TwoPhaseIterator tpi =
+ DocValuesRangeIterator.forOrdinalRange(
+ values, leaf.getDocValuesSkipper("f"), minOrd, maxOrd);
+ FixedBitSet expected = new FixedBitSet(leaf.maxDoc());
+ SortedDocValues truth = leaf.getSortedDocValues("f");
+ for (int d = truth.nextDoc(); d != NO_MORE_DOCS; d = truth.nextDoc()) {
+ int ord = truth.ordValue();
+ if (ord >= minOrd && ord <= maxOrd) {
+ expected.set(d);
+ }
+ }
+ assertDocIDRunEnds(tpi, expected, leaf.maxDoc());
+ }
+ }
+ }
+ }
+ }
+
+ public void testDocIDRunEndSortedSetOrdinalRange() throws Exception {
+ doTestDocIDRunEndSortedSet(false);
+ }
+
+ public void testDocIDRunEndSortedSetOrdinalSet() throws Exception {
+ doTestDocIDRunEndSortedSet(true);
+ }
+
+ private void doTestDocIDRunEndSortedSet(boolean ordinalSet) throws Exception {
+ int totalDocs = TestUtil.nextInt(random(), 1, 1500);
+ int domain = TestUtil.nextInt(random(), 5, 100);
+ int missingOneIn = TestUtil.nextInt(random(), 0, 4);
+ try (Directory dir = newDirectory();
+ RandomIndexWriter w = new RandomIndexWriter(random(), dir)) {
+ for (int i = 0; i < totalDocs; i++) {
+ Document doc = new Document();
+ if (missingOneIn == 0 || random().nextInt(missingOneIn + 1) != 0) {
+ int count = TestUtil.nextInt(random(), 1, 2);
+ for (int j = 0; j < count; j++) {
+ doc.add(SortedSetDocValuesField.indexedField("f", randomFixedWidthTerm(domain)));
+ }
+ }
+ w.addDocument(doc);
+ }
+ if (random().nextBoolean()) {
+ w.forceMerge(1);
+ }
+ try (IndexReader r = w.getReader()) {
+ for (LeafReaderContext ctx : r.leaves()) {
+ LeafReader leaf = ctx.reader();
+ for (int iter = 0; iter < 10; iter++) {
+ SortedSetDocValues values = leaf.getSortedSetDocValues("f");
+ if (values == null || values.getValueCount() == 0) {
+ break;
+ }
+ long valueCount = values.getValueCount();
+ LongBitSet ords = new LongBitSet(valueCount);
+ long minOrd;
+ long maxOrd;
+ if (ordinalSet) {
+ // every other ordinal: guarantees a gap, the non-contiguous shape from GH#16450
+ minOrd = -1;
+ maxOrd = -1;
+ for (long o = random().nextInt(2); o < valueCount; o += 2) {
+ ords.set(o);
+ if (minOrd == -1) {
+ minOrd = o;
+ }
+ maxOrd = o;
+ }
+ if (minOrd == -1) {
+ continue;
+ }
+ } else {
+ long a = TestUtil.nextLong(random(), 0, valueCount - 1);
+ long b = TestUtil.nextLong(random(), 0, valueCount - 1);
+ minOrd = Math.min(a, b);
+ maxOrd = Math.max(a, b);
+ ords.set(minOrd, maxOrd + 1);
+ }
+ TwoPhaseIterator tpi =
+ ordinalSet
+ ? DocValuesRangeIterator.forOrdinalSet(
+ values, leaf.getDocValuesSkipper("f"), minOrd, maxOrd, ords)
+ : DocValuesRangeIterator.forOrdinalRange(
+ values, leaf.getDocValuesSkipper("f"), minOrd, maxOrd);
+ FixedBitSet expected = new FixedBitSet(leaf.maxDoc());
+ SortedSetDocValues truth = leaf.getSortedSetDocValues("f");
+ for (int d = truth.nextDoc(); d != NO_MORE_DOCS; d = truth.nextDoc()) {
+ for (int j = 0; j < truth.docValueCount(); j++) {
+ if (ords.get(truth.nextOrd())) {
+ expected.set(d);
+ break;
+ }
+ }
+ }
+ assertDocIDRunEnds(tpi, expected, leaf.maxDoc());
+ }
+ }
+ }
+ }
+ }
+
+ private static BytesRef randomFixedWidthTerm(int domain) {
+ // offset keeps the string width fixed so ordinal order matches numeric order
+ return new BytesRef(Long.toString(1000000L + random().nextInt(domain)));
+ }
+
+ /**
+ * Walks the approximation and verifies the {@link TwoPhaseIterator#docIDRunEnd()} contract: every
+ * doc in a reported run {@code [docID, runEnd)} must be a true match, the call must not move the
+ * approximation, and outside runs {@link TwoPhaseIterator#matches()} must agree with a
+ * brute-force per-doc check.
+ */
+ private static void assertDocIDRunEnds(TwoPhaseIterator tpi, FixedBitSet expected, int maxDoc)
+ throws IOException {
+ DocIdSetIterator approx = tpi.approximation();
+ for (int doc = approx.nextDoc(); doc != NO_MORE_DOCS; ) {
+ int runEnd = tpi.docIDRunEnd();
+ assertEquals("docIDRunEnd() must not move the approximation", doc, approx.docID());
+ assertTrue("docIDRunEnd() " + runEnd + " is below the current doc " + doc, runEnd >= doc);
+ assertTrue("docIDRunEnd() " + runEnd + " is beyond maxDoc " + maxDoc, runEnd <= maxDoc);
+ for (int d = doc; d < runEnd; d++) {
+ assertTrue(
+ "doc " + d + " in reported run [" + doc + ", " + runEnd + ") is not a true match",
+ expected.get(d));
+ }
+ if (runEnd > doc) {
+ doc = approx.advance(runEnd);
+ } else {
+ assertEquals(
+ "matches() disagrees with brute force on doc " + doc, expected.get(doc), tpi.matches());
+ doc = approx.nextDoc();
+ }
+ }
+ }
}