You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2025/05/20 21:12:14 UTC

(lucene) branch main updated: Make competitive iterators more robust. (#14532)

This is an automated email from the ASF dual-hosted git repository.

jpountz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/main by this push:
     new 81f2517f985 Make competitive iterators more robust. (#14532)
81f2517f985 is described below

commit 81f2517f985f27e6fa4b4b6b25774c238c356adb
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Tue May 20 23:12:09 2025 +0200

    Make competitive iterators more robust. (#14532)
    
    As per a recent bug (#14517), competitive iterators are hard to get
    right given how their state gets updated in place. This commit tries to
    make them more robust by extracting the logic of updating the state of a
    `DocIdSetIterator` to a shared class, which can then be tested on its
    own.
    
    A side-effect is that it implements `#intoBitSet` on the doc competitive
    iterator and `#docIDRunEnd` on all competitive iterators.
---
 .../lucene/search/comparators/DocComparator.java   |  41 ++------
 .../search/comparators/NumericComparator.java      |  46 ++-------
 .../search/comparators/TermOrdValComparator.java   | 113 ++++++++-------------
 ...erator.java => UpdateableDocIdSetIterator.java} |  59 +++++++----
 .../comparators/TestTermOrdValComparator.java      |  84 ---------------
 .../TestUpdateableDocIdSetIterator.java            | 100 ++++++++++++++++++
 6 files changed, 200 insertions(+), 243 deletions(-)

diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
index 9b242c6ac6a..8120703a82e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
@@ -19,7 +19,6 @@ package org.apache.lucene.search.comparators;
 
 import java.io.IOException;
 import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.search.AbstractDocIdSetIterator;
 import org.apache.lucene.search.DocIdSetIterator;
 import org.apache.lucene.search.FieldComparator;
 import org.apache.lucene.search.LeafFieldComparator;
@@ -78,7 +77,8 @@ public class DocComparator extends FieldComparator<Integer> {
     private final int docBase;
     private final int minDoc;
     private final int maxDoc;
-    private DocIdSetIterator competitiveIterator; // iterator that starts from topValue
+    private final UpdateableDocIdSetIterator
+        competitiveIterator; // iterator that starts from topValue
 
     public DocLeafComparator(LeafReaderContext context) {
       this.docBase = context.docBase;
@@ -89,7 +89,8 @@ public class DocComparator extends FieldComparator<Integer> {
         // with the same docID.
         this.minDoc = topValue;
         this.maxDoc = context.reader().maxDoc();
-        this.competitiveIterator = DocIdSetIterator.all(maxDoc);
+        this.competitiveIterator = new UpdateableDocIdSetIterator();
+        this.competitiveIterator.update(DocIdSetIterator.all(maxDoc));
       } else {
         this.minDoc = -1;
         this.maxDoc = -1;
@@ -129,31 +130,7 @@ public class DocComparator extends FieldComparator<Integer> {
 
     @Override
     public DocIdSetIterator competitiveIterator() {
-      if (enableSkipping == false) {
-        return null;
-      } else {
-        return new AbstractDocIdSetIterator() {
-
-          {
-            doc = competitiveIterator.docID();
-          }
-
-          @Override
-          public int nextDoc() throws IOException {
-            return advance(doc + 1);
-          }
-
-          @Override
-          public long cost() {
-            return competitiveIterator.cost();
-          }
-
-          @Override
-          public int advance(int target) throws IOException {
-            return doc = competitiveIterator.advance(target);
-          }
-        };
-      }
+      return competitiveIterator;
     }
 
     @Override
@@ -169,14 +146,16 @@ public class DocComparator extends FieldComparator<Integer> {
         // Currently early termination on _doc is also implemented in TopFieldCollector, but this
         // will be removed
         // once all bulk scores uses collectors' iterators
-        competitiveIterator = DocIdSetIterator.empty();
+        competitiveIterator.update(DocIdSetIterator.empty());
       } else if (topValueSet) {
         // skip to the desired top doc
         if (docBase + maxDoc <= minDoc) {
-          competitiveIterator = DocIdSetIterator.empty(); // skip this segment
+          competitiveIterator.update(DocIdSetIterator.empty()); // skip this segment
         } else {
           int segmentMinDoc = Math.max(competitiveIterator.docID(), minDoc - docBase);
-          competitiveIterator = new MinDocIterator(segmentMinDoc, maxDoc);
+          // The competitive iterator may not be positioned yet.
+          segmentMinDoc = Math.max(0, segmentMinDoc);
+          competitiveIterator.update(DocIdSetIterator.range(segmentMinDoc, maxDoc));
         }
       }
     }
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
index a5d49a4b167..353d7ab39bf 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
@@ -23,7 +23,6 @@ import org.apache.lucene.index.FieldInfo;
 import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.index.NumericDocValues;
 import org.apache.lucene.index.PointValues;
-import org.apache.lucene.search.AbstractDocIdSetIterator;
 import org.apache.lucene.search.DocIdSetIterator;
 import org.apache.lucene.search.FieldComparator;
 import org.apache.lucene.search.LeafFieldComparator;
@@ -31,7 +30,6 @@ import org.apache.lucene.search.Pruning;
 import org.apache.lucene.search.Scorable;
 import org.apache.lucene.search.Scorer;
 import org.apache.lucene.util.DocIdSetBuilder;
-import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.IntsRef;
 
 /**
@@ -110,7 +108,7 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
     private long minValueAsLong = Long.MIN_VALUE;
     private long maxValueAsLong = Long.MAX_VALUE;
 
-    private DocIdSetIterator competitiveIterator;
+    private final UpdateableDocIdSetIterator competitiveIterator;
     private long iteratorCost = -1;
     private int maxDocVisited = -1;
     private int updateCounter = 0;
@@ -145,12 +143,14 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
         }
         this.enableSkipping = true; // skipping is enabled when points are available
         this.maxDoc = context.reader().maxDoc();
-        this.competitiveIterator = DocIdSetIterator.all(maxDoc);
+        this.competitiveIterator = new UpdateableDocIdSetIterator();
+        this.competitiveIterator.update(DocIdSetIterator.all(maxDoc));
         if (leafTopSet) {
           encodeTop();
         }
       } else {
         this.enableSkipping = false;
+        this.competitiveIterator = null;
         this.maxDoc = 0;
       }
     }
@@ -295,13 +295,13 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
         updateSkipInterval(false);
         if (pointValues.getDocCount() < iteratorCost) {
           // Use the set of doc with values to help drive iteration
-          competitiveIterator = getNumericDocValues(context, field);
+          competitiveIterator.update(getNumericDocValues(context, field));
           iteratorCost = pointValues.getDocCount();
         }
         return;
       }
       pointValues.intersect(visitor);
-      competitiveIterator = result.build().iterator();
+      competitiveIterator.update(result.build().iterator());
       iteratorCost = competitiveIterator.cost();
       updateSkipInterval(true);
     }
@@ -405,39 +405,7 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
 
     @Override
     public DocIdSetIterator competitiveIterator() {
-      if (enableSkipping == false) return null;
-      return new AbstractDocIdSetIterator() {
-
-        {
-          doc = competitiveIterator.docID();
-        }
-
-        @Override
-        public int nextDoc() throws IOException {
-          return advance(doc + 1);
-        }
-
-        @Override
-        public long cost() {
-          return competitiveIterator.cost();
-        }
-
-        @Override
-        public int advance(int target) throws IOException {
-          return doc = competitiveIterator.advance(target);
-        }
-
-        @Override
-        public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
-          // The competitive iterator is usually a BitSetIterator, which has an optimized
-          // implementation of #intoBitSet.
-          if (competitiveIterator.docID() < doc) {
-            competitiveIterator.advance(doc);
-          }
-          competitiveIterator.intoBitSet(upTo, bitSet, offset);
-          doc = competitiveIterator.docID();
-        }
-      };
+      return competitiveIterator;
     }
 
     protected abstract long bottomAsComparableLong();
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
index 4f8cc8099bc..ae21efe76c8 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/TermOrdValComparator.java
@@ -35,7 +35,6 @@ import org.apache.lucene.search.Pruning;
 import org.apache.lucene.search.Scorable;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.BytesRefBuilder;
-import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.PriorityQueue;
 
 /**
@@ -201,7 +200,7 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
     /** Which ordinal to use for a missing value. */
     final int missingOrd;
 
-    private final CompetitiveIterator competitiveIterator;
+    private final CompetitiveState competitiveState;
 
     private final boolean dense;
 
@@ -266,9 +265,9 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
         }
       }
       if (enableSkipping) {
-        competitiveIterator = new CompetitiveIterator(context, field, dense, values.termsEnum());
+        competitiveState = new CompetitiveState(context, field, dense, values.termsEnum());
       } else {
-        competitiveIterator = null;
+        competitiveState = null;
       }
       updateCompetitiveIterator();
     }
@@ -383,7 +382,7 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
     public void setScorer(Scorable scorer) {}
 
     private void updateCompetitiveIterator() throws IOException {
-      if (competitiveIterator == null || hitsThresholdReached == false || bottomSlot == -1) {
+      if (competitiveState == null || hitsThresholdReached == false || bottomSlot == -1) {
         return;
       }
       // This logic to figure out min and max ords is quite complex and verbose, can it be made
@@ -457,99 +456,71 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
       }
       assert minOrd >= 0;
       assert maxOrd < termsIndex.getValueCount();
-      competitiveIterator.update(minOrd, maxOrd);
+      competitiveState.update(minOrd, maxOrd);
     }
 
     @Override
     public DocIdSetIterator competitiveIterator() {
-      return competitiveIterator;
+      return competitiveState != null ? competitiveState.iterator : null;
     }
   }
 
   private record PostingsEnumAndOrd(PostingsEnum postings, int ord) {}
 
-  private class CompetitiveIterator extends AbstractDocIdSetIterator {
+  private class CompetitiveState {
 
     private static final int MAX_TERMS = 1024;
 
     private final LeafReaderContext context;
-    private final int maxDoc;
     private final String field;
     private final boolean dense;
     private final TermsEnum docValuesTerms;
     private ArrayDeque<PostingsEnumAndOrd> postings;
     private DocIdSetIterator docsWithField;
     private PriorityQueue<PostingsEnumAndOrd> disjunction;
+    private final DocIdSetIterator disjunctionIterator;
 
-    CompetitiveIterator(
+    private final UpdateableDocIdSetIterator iterator;
+
+    CompetitiveState(
         LeafReaderContext context, String field, boolean dense, TermsEnum docValuesTerms) {
       this.context = context;
-      this.maxDoc = context.reader().maxDoc();
       this.field = field;
       this.dense = dense;
       this.docValuesTerms = docValuesTerms;
-    }
-
-    @Override
-    public int nextDoc() throws IOException {
-      return advance(docID() + 1);
-    }
+      this.disjunctionIterator =
+          new AbstractDocIdSetIterator() {
 
-    @Override
-    public int advance(int target) throws IOException {
-      if (target >= maxDoc) {
-        return doc = NO_MORE_DOCS;
-      } else if (disjunction == null) {
-        if (docsWithField != null) {
-          // The field is sparse and we're only interested in documents that have a value.
-          assert dense == false;
-          return doc = docsWithField.advance(target);
-        } else {
-          // We haven't started skipping yet
-          return doc = target;
-        }
-      } else {
-        PostingsEnumAndOrd top = disjunction.top();
-        if (top == null) {
-          // priority queue is empty, none of the remaining documents are competitive
-          return doc = NO_MORE_DOCS;
-        }
-        while (top.postings.docID() < target) {
-          top.postings.advance(target);
-          top = disjunction.updateTop();
-        }
-        return doc = top.postings.docID();
-      }
-    }
+            @Override
+            public int nextDoc() throws IOException {
+              return advance(doc + 1);
+            }
 
-    @Override
-    public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
-      upTo = Math.min(upTo, maxDoc);
-      if (upTo <= doc) {
-        return;
-      }
-      // Optimize the case when intersecting the competitive iterator is expensive, which is when it
-      // hasn't nailed down a disjunction of competitive terms yet.
-      if (disjunction == null) {
-        if (docsWithField != null) {
-          // we need to be absolutely sure that the iterator is at least at offset
-          if (docsWithField.docID() < doc) {
-            docsWithField.advance(doc);
-          }
-          docsWithField.intoBitSet(upTo, bitSet, offset);
-          doc = docsWithField.docID();
-        } else {
-          bitSet.set(doc - offset, upTo - offset);
-          doc = upTo;
-        }
-      } else {
-        super.intoBitSet(upTo, bitSet, offset);
-      }
-    }
+            @Override
+            public int advance(int target) throws IOException {
+              PostingsEnumAndOrd top = disjunction.top();
+              if (top == null) {
+                // priority queue is empty, none of the remaining documents are competitive
+                return doc = NO_MORE_DOCS;
+              }
+              while (top.postings.docID() < target) {
+                top.postings.advance(target);
+                top = disjunction.updateTop();
+              }
+              return this.doc = top.postings.docID();
+            }
 
-    @Override
-    public long cost() {
-      return context.reader().maxDoc();
+            @Override
+            public long cost() {
+              long cost = 0;
+              for (PostingsEnumAndOrd posting : disjunction) {
+                cost += posting.postings.cost();
+              }
+              return cost;
+            }
+          };
+      this.iterator = new UpdateableDocIdSetIterator();
+      this.iterator.update(DocIdSetIterator.all(context.reader().maxDoc()));
     }
 
     /**
@@ -562,9 +533,11 @@ public class TermOrdValComparator extends FieldComparator<BytesRef> {
       if (size > maxTerms) {
         if (dense == false && docsWithField == null) {
           docsWithField = getSortedDocValues(context, field);
+          iterator.update(docsWithField);
         }
       } else if (postings == null) {
         init(minOrd, maxOrd);
+        iterator.update(disjunctionIterator);
       } else if (size < postings.size()) {
         // One or more ords got removed
         assert postings.isEmpty() || postings.getFirst().ord <= minOrd;
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/MinDocIterator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/UpdateableDocIdSetIterator.java
similarity index 50%
rename from lucene/core/src/java/org/apache/lucene/search/comparators/MinDocIterator.java
rename to lucene/core/src/java/org/apache/lucene/search/comparators/UpdateableDocIdSetIterator.java
index 5d2876ad2ba..2843bd138fb 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/MinDocIterator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/UpdateableDocIdSetIterator.java
@@ -14,20 +14,24 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 package org.apache.lucene.search.comparators;
 
 import java.io.IOException;
+import java.util.Objects;
 import org.apache.lucene.search.AbstractDocIdSetIterator;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.FixedBitSet;
+
+final class UpdateableDocIdSetIterator extends AbstractDocIdSetIterator {
 
-/** Docs iterator that starts iterating from a configurable minimum document */
-public class MinDocIterator extends AbstractDocIdSetIterator {
-  final int segmentMinDoc;
-  final int maxDoc;
+  private DocIdSetIterator in = DocIdSetIterator.empty();
 
-  MinDocIterator(int segmentMinDoc, int maxDoc) {
-    this.segmentMinDoc = segmentMinDoc;
-    this.maxDoc = maxDoc;
+  /**
+   * Update the wrapped {@link DocIdSetIterator}. It doesn't need to be positioned on the same doc
+   * ID as this iterator.
+   */
+  void update(DocIdSetIterator iterator) {
+    this.in = Objects.requireNonNull(iterator);
   }
 
   @Override
@@ -37,21 +41,38 @@ public class MinDocIterator extends AbstractDocIdSetIterator {
 
   @Override
   public int advance(int target) throws IOException {
-    assert target > doc;
-    if (doc == -1) {
-      // skip directly to minDoc
-      doc = Math.max(target, segmentMinDoc);
-    } else {
-      doc = target;
-    }
-    if (doc >= maxDoc) {
-      doc = NO_MORE_DOCS;
+    int curDoc = in.docID();
+    if (curDoc < target) {
+      curDoc = in.advance(target);
     }
-    return doc;
+    return this.doc = curDoc;
   }
 
   @Override
   public long cost() {
-    return maxDoc - segmentMinDoc;
+    return in.cost();
+  }
+
+  @Override
+  public void intoBitSet(int upTo, FixedBitSet bitSet, int offset) throws IOException {
+    // #update may have been just called
+    if (in.docID() < doc) {
+      in.advance(doc);
+    }
+    in.intoBitSet(upTo, bitSet, offset);
+    doc = in.docID();
+  }
+
+  @Override
+  public int docIDRunEnd() throws IOException {
+    // #update may have been just called
+    if (in.docID() < doc) {
+      in.advance(doc);
+    }
+    if (in.docID() == doc) {
+      return in.docIDRunEnd();
+    } else {
+      return super.docIDRunEnd();
+    }
   }
 }
diff --git a/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparator.java b/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparator.java
deleted file mode 100644
index 52738fc77c0..00000000000
--- a/lucene/core/src/test/org/apache/lucene/search/comparators/TestTermOrdValComparator.java
+++ /dev/null
@@ -1,84 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.search.comparators;
-
-import java.io.IOException;
-import org.apache.lucene.document.Document;
-import org.apache.lucene.document.Field;
-import org.apache.lucene.document.KeywordField;
-import org.apache.lucene.document.StringField;
-import org.apache.lucene.index.DirectoryReader;
-import org.apache.lucene.index.IndexWriter;
-import org.apache.lucene.index.IndexWriterConfig;
-import org.apache.lucene.index.LeafReaderContext;
-import org.apache.lucene.index.Term;
-import org.apache.lucene.search.BulkScorer;
-import org.apache.lucene.search.Collector;
-import org.apache.lucene.search.IndexSearcher;
-import org.apache.lucene.search.LeafCollector;
-import org.apache.lucene.search.Query;
-import org.apache.lucene.search.ScoreMode;
-import org.apache.lucene.search.Sort;
-import org.apache.lucene.search.SortField;
-import org.apache.lucene.search.SortedSetSelector;
-import org.apache.lucene.search.TermQuery;
-import org.apache.lucene.search.TopFieldCollectorManager;
-import org.apache.lucene.search.Weight;
-import org.apache.lucene.store.ByteBuffersDirectory;
-import org.apache.lucene.store.Directory;
-import org.apache.lucene.tests.util.LuceneTestCase;
-
-public class TestTermOrdValComparator extends LuceneTestCase {
-
-  public void testIntoBitSetBugIssue14517() throws IOException {
-    final int maxDoc = 5_000;
-    try (Directory dir = new ByteBuffersDirectory()) {
-      try (IndexWriter w = new IndexWriter(dir, new IndexWriterConfig())) {
-        // high max doc to have a high number of unique values so that the competitive iterator is
-        // initialized with `docsWithField` rather than specific (< 1024) terms
-        for (int i = 0; i < maxDoc; ++i) {
-          Document doc = new Document();
-          // make the field to be sparse, so that the iterator is initialized with `docsWithField`
-          if (i % 2 == 0) {
-            doc.add(new StringField("field", "value", Field.Store.NO));
-            doc.add(new KeywordField("sort", Integer.toString(i), Field.Store.NO));
-          }
-          w.addDocument(doc);
-        }
-        w.forceMerge(1);
-      }
-      try (DirectoryReader reader = DirectoryReader.open(dir)) {
-        LeafReaderContext context = reader.leaves().get(0);
-        IndexSearcher searcher = new IndexSearcher(reader);
-        Query query = new TermQuery(new Term("field", "value"));
-        Weight weight =
-            searcher.createWeight(query, ScoreMode.COMPLETE_NO_SCORES, RANDOM_MULTIPLIER);
-        SortField sortField = KeywordField.newSortField("sort", false, SortedSetSelector.Type.MIN);
-        sortField.setMissingValue(SortField.STRING_LAST);
-        Sort sort = new Sort(sortField);
-        Collector collector = new TopFieldCollectorManager(sort, 10, 10).newCollector();
-        LeafCollector leafCollector = collector.getLeafCollector(context);
-        BulkScorer bulkScorer = weight.bulkScorer(context);
-        // split on this specific doc ID so that the current doc of the competitive iterator
-        // and the current doc of `docsWithField` are out of sync,
-        // because the competitive iterator was just updated.
-        bulkScorer.score(leafCollector, null, 0, 22);
-        bulkScorer.score(leafCollector, null, 22, maxDoc);
-      }
-    }
-  }
-}
diff --git a/lucene/core/src/test/org/apache/lucene/search/comparators/TestUpdateableDocIdSetIterator.java b/lucene/core/src/test/org/apache/lucene/search/comparators/TestUpdateableDocIdSetIterator.java
new file mode 100644
index 00000000000..488d43adfa0
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/search/comparators/TestUpdateableDocIdSetIterator.java
@@ -0,0 +1,100 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.search.comparators;
+
+import java.io.IOException;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.FixedBitSet;
+
+public class TestUpdateableDocIdSetIterator extends LuceneTestCase {
+
+  public void testNextDoc() throws IOException {
+    UpdateableDocIdSetIterator iterator = new UpdateableDocIdSetIterator();
+    iterator.update(DocIdSetIterator.range(10, 20));
+    assertEquals(10, iterator.nextDoc());
+    iterator.update(DocIdSetIterator.range(10, 12));
+    assertEquals(11, iterator.nextDoc());
+    DocIdSetIterator in = DocIdSetIterator.range(10, 15);
+    in.advance(14);
+    iterator.update(in);
+    assertEquals(14, iterator.nextDoc());
+    assertEquals(DocIdSetIterator.NO_MORE_DOCS, iterator.nextDoc());
+  }
+
+  public void testAdvance() throws IOException {
+    UpdateableDocIdSetIterator iterator = new UpdateableDocIdSetIterator();
+    iterator.update(DocIdSetIterator.range(10, 20));
+    assertEquals(12, iterator.advance(12));
+    iterator.update(DocIdSetIterator.range(10, 15));
+    assertEquals(13, iterator.advance(13));
+    DocIdSetIterator in = DocIdSetIterator.range(10, 20);
+    in.advance(15);
+    iterator.update(in);
+    assertEquals(15, iterator.advance(15));
+    assertEquals(DocIdSetIterator.NO_MORE_DOCS, iterator.advance(20));
+  }
+
+  public void testIntoBitSet() throws IOException {
+    UpdateableDocIdSetIterator iterator = new UpdateableDocIdSetIterator();
+    iterator.update(DocIdSetIterator.range(10, 18));
+    assertEquals(10, iterator.nextDoc());
+    FixedBitSet bitSet = new FixedBitSet(100);
+    iterator.intoBitSet(15, bitSet, 5);
+    assertEquals(15, iterator.docID());
+    FixedBitSet expected = new FixedBitSet(100);
+    expected.set(5, 10);
+    assertEquals(expected, bitSet);
+
+    iterator.update(DocIdSetIterator.range(12, 25));
+    bitSet.clear();
+    iterator.intoBitSet(20, bitSet, 8);
+    assertEquals(20, iterator.docID());
+    expected.clear();
+    expected.set(7, 12);
+    assertEquals(expected, bitSet);
+
+    DocIdSetIterator in = DocIdSetIterator.range(15, 25);
+    in.advance(23);
+    iterator.update(in);
+    bitSet.clear();
+    iterator.intoBitSet(30, bitSet, 10);
+    assertEquals(DocIdSetIterator.NO_MORE_DOCS, iterator.docID());
+    expected.clear();
+    expected.set(13, 15);
+    assertEquals(expected, bitSet);
+  }
+
+  public void testDocIDRunEnd() throws IOException {
+    UpdateableDocIdSetIterator iterator = new UpdateableDocIdSetIterator();
+    iterator.update(DocIdSetIterator.range(10, 18));
+    assertEquals(10, iterator.nextDoc());
+    assertEquals(18, iterator.docIDRunEnd());
+    assertEquals(10, iterator.docID()); // no side effect
+
+    iterator.update(DocIdSetIterator.range(8, 25));
+    assertEquals(25, iterator.docIDRunEnd());
+    assertEquals(10, iterator.docID()); // no side effect
+
+    DocIdSetIterator in = DocIdSetIterator.range(5, 25);
+    in.advance(12);
+    iterator.update(in);
+    assertEquals(11, iterator.docIDRunEnd());
+    assertEquals(10, iterator.docID()); // no side effect
+    assertEquals(12, iterator.nextDoc());
+  }
+}