[lucene] branch branch_9x updated: LUCENE-10428: Avoid infinite loop under error conditions. (#711)

[jp...@apache.org]

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

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


The following commit(s) were added to refs/heads/branch_9x by this push:
     new 0d35e38  LUCENE-10428: Avoid infinite loop under error conditions. (#711)
0d35e38 is described below

commit 0d35e38b93d4c394aee691f308092cb9cfa792a2
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Thu Mar 3 09:42:12 2022 +0100

    LUCENE-10428: Avoid infinite loop under error conditions. (#711)
    
    Co-authored-by: dblock <db...@dblock.org>
---
 lucene/CHANGES.txt                                 |  4 +++
 .../lucene/search/MaxScoreSumPropagator.java       | 29 ++++++++++++++++------
 .../lucene/search/TestMaxScoreSumPropagator.java   | 23 +++++++++++++++++
 3 files changed, 49 insertions(+), 7 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 5c3f749..eed62dc 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -253,6 +253,10 @@ Bug Fixes
 * LUCENE-10405: When using the MemoryIndex, binary and Sorted doc values are stored 
    as BytesRef instead of BytesRefHash so they don't have a limit on size. (Ignacio Vera)
 
+* LUCENE-10428: Queries with a misbehaving score function may no longer cause
+  infinite loops in their parent BooleanQuery.
+  (Ankit Jain, Daniel Doubrovkine, Adrien Grand)
+
 Other
 ---------------------
 
diff --git a/lucene/core/src/java/org/apache/lucene/search/MaxScoreSumPropagator.java b/lucene/core/src/java/org/apache/lucene/search/MaxScoreSumPropagator.java
index 417b751..1557cd9 100644
--- a/lucene/core/src/java/org/apache/lucene/search/MaxScoreSumPropagator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/MaxScoreSumPropagator.java
@@ -128,25 +128,40 @@ final class MaxScoreSumPropagator {
     }
   }
 
-  /** Return the minimum score that a Scorer must produce in order for a hit to be competitive. */
+  /**
+   * Return the minimum score that a Scorer must produce in order for a hit to be competitive.
+   *
+   * <p>The way that boolean queries combine scores of their sub clauses together is by summing up
+   * the float scores into a double and finally casting back that double back to a float. This
+   * method undoes this operation by taking the float score sum and subtracting the sum of other
+   * scores as a double as a first approximation of the minimum score that this clause must have.
+   */
   private float getMinCompetitiveScore(float minScoreSum, double sumOfOtherMaxScores) {
     assert numClauses > 0;
-    if (minScoreSum <= sumOfOtherMaxScores) {
-      return 0f;
-    }
 
     // We need to find a value 'minScore' so that 'minScore + sumOfOtherMaxScores <= minScoreSum'
     // TODO: is there an efficient way to find the greatest value that meets this requirement?
     float minScore = (float) (minScoreSum - sumOfOtherMaxScores);
-    int iters = 0;
-    while (scoreSumUpperBound(minScore + sumOfOtherMaxScores) > minScoreSum) {
+    for (int iter = 0;
+        minScore > 0 && scoreSumUpperBound(minScore + sumOfOtherMaxScores) > minScoreSum;
+        ++iter) {
       // Important: use ulp of minScoreSum and not minScore to make sure that we
       // converge quickly.
       minScore -= Math.ulp(minScoreSum);
       // this should converge in at most two iterations:
       //  - one because of the subtraction rounding error
       //  - one because of the error introduced by sumUpperBound
-      assert ++iters <= 2 : iters;
+      if (iter > 2) {
+        throw new IllegalStateException(
+            "Could not compute a minimum score for minScore="
+                + +minScore
+                + ", minScoreSum="
+                + minScoreSum
+                + ", sumOfOtherMaxScores="
+                + sumOfOtherMaxScores
+                + ", numClauses="
+                + numClauses);
+      }
     }
     return Math.max(minScore, 0f);
   }
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestMaxScoreSumPropagator.java b/lucene/core/src/test/org/apache/lucene/search/TestMaxScoreSumPropagator.java
index 8fc3784..0cbe28f 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestMaxScoreSumPropagator.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestMaxScoreSumPropagator.java
@@ -229,4 +229,27 @@ public class TestMaxScoreSumPropagator extends LuceneTestCase {
           (float) scoreSum <= minCompetitiveScore);
     }
   }
+
+  /*
+    In https://issues.apache.org/jira/browse/LUCENE-10428 we have observed an issue in production
+    causing an infinite loop in MaxScoreSumPropagator.getMinCompetitiveScore. This is likely
+    caused by calling code that is breaking the assumptions made by MaxScoreSumPropagator,
+    e.g. a query that produces negative or NaN scores. This test reproduces that scenario,
+    and asserts that getMinCompetitiveScore aborts after more than 2 iterations.
+
+    See https://github.com/apache/lucene/pull/711.
+  */
+  public void testMinCompetitiveScoreIllegalState() throws Exception {
+    List<FakeScorer> scorers = new ArrayList<>();
+    scorers.add(new FakeScorer(-0.16903716f));
+    scorers.add(new FakeScorer(0.62573546f));
+    scorers.add(new FakeScorer(-0.64014715f));
+    float minScoreSum = 0.31314075f;
+    MaxScoreSumPropagator p = new MaxScoreSumPropagator(scorers);
+    Throwable exception =
+        assertThrows(IllegalStateException.class, () -> p.setMinCompetitiveScore(minScoreSum));
+    assertEquals(
+        "Could not compute a minimum score for minScore=1.1223251, minScoreSum=0.31314072, sumOfOtherMaxScores=-0.8091843128204346, numClauses=3",
+        exception.getMessage());
+  }
 }