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

chibenwa pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/james-jsieve.git

commit 76b903e380bbca5954324e2610ee632d51a7023d
Author: Benoit TELLIER <[email protected]>
AuthorDate: Wed Nov 18 22:23:10 2026 +0100

    [FIX] ComparatorUtils: search a short :contains key with indexOf
    
    4bf3a6b made :contains linear by replacing String#indexOf with a
    Knuth-Morris-Pratt search. Every comparison then allocated the failure
    table of its key and compared one charAt at a time, losing the indexOf
    intrinsic: evaluateHeaderContains ran x2.7 slower and a typical filter
    script x1.3, for keys of a few characters.
    
    A key of at most 64 characters is searched with indexOf again. Its
    worst case, at most 64 characters compared per character of the value,
    stays within a constant factor of the linear cost charged to the
    budget. A longer key keeps the Knuth-Morris-Pratt search, so a hostile
    key on a large header stays linear.
---
 .../apache/jsieve/comparators/ComparatorUtils.java | 26 +++++++++++++++---
 .../jsieve/comparator/ComparatorUtilsTest.java     | 31 ++++++++++++++++++++++
 2 files changed, 54 insertions(+), 3 deletions(-)

diff --git 
a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java 
b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
index b14f8dd..398cda3 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
@@ -245,9 +245,13 @@ public class ComparatorUtils {
      * 2.7.1): a match never starts or ends inside a surrogate pair.
      * </p>
      * <p>
-     * The search is linear (Knuth-Morris-Pratt): it compares at most
-     * <code>2 * container length + contents length</code> characters,
-     * whatever the values.
+     * The search is linear whatever the values. A contents of at most
+     * {@link #SHORT_CONTENTS} characters, the usual case of a script key, is
+     * searched with {@link String#indexOf(String, int)}: at most
+     * {@link #SHORT_CONTENTS} characters are compared per character of the
+     * container, and the JIT runs it much faster than a scalar loop. A
+     * longer contents is searched with Knuth-Morris-Pratt, which compares at
+     * most <code>2 * container length + contents length</code> characters.
      * </p>
      *
      * @param container
@@ -259,6 +263,15 @@ public class ComparatorUtils {
         if (length == 0) {
             return true;
         }
+        if (length <= SHORT_CONTENTS) {
+            for (int i = container.indexOf(contents); i >= 0; i = 
container.indexOf(contents, i + 1)) {
+                if (!splitsSurrogatePair(container, i)
+                        && !splitsSurrogatePair(container, i + length)) {
+                    return true;
+                }
+            }
+            return false;
+        }
         final int[] border = borders(contents);
         // Number of characters of contents matched so far
         int matched = 0;
@@ -282,6 +295,13 @@ public class ComparatorUtils {
         return false;
     }
 
+    /**
+     * Longest contents searched by {@link String#indexOf(String, int)}: its
+     * worst case, quadratic, stays within a constant factor of a linear
+     * search.
+     */
+    static final int SHORT_CONTENTS = 64;
+
     /**
      * Knuth-Morris-Pratt failure function: for each prefix of the string,
      * the length of its longest proper prefix that is also a suffix.
diff --git 
a/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java 
b/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
index 8f4676a..ec13305 100644
--- a/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
+++ b/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
@@ -143,6 +143,37 @@ public class ComparatorUtilsTest {
         }
     }
 
+    @Test
+    public void containsShouldAgreeWithIndexOfOnRandomLongContents() throws 
Exception {
+        Random random = new Random(42);
+        for (int i = 0; i < 5_000; i++) {
+            // Over 64 characters, the search is no longer delegated to indexOf
+            String contents = repeat("ab", 32) + randomAbc(random, 1 + 
random.nextInt(4));
+            String container = randomAbc(random, random.nextInt(8)) + 
repeat("ab", random.nextInt(40))
+                + randomAbc(random, random.nextInt(8)) + contents.substring(0, 
random.nextInt(contents.length() + 1))
+                + randomAbc(random, random.nextInt(8));
+            Assert.assertEquals("container=" + container + " contents=" + 
contents,
+                container.contains(contents), 
ComparatorUtils.contains(container, contents));
+        }
+    }
+
+    @Test
+    public void containsShouldNotMatchHalfOfASurrogatePairWithALongContents() 
throws Exception {
+        String longContents = repeat("x", 70);
+        String angryFace = "a😠" + longContents + "😠b";
+
+        Assert.assertFalse(ComparatorUtils.contains(angryFace, "\uDE20" + 
longContents));
+        Assert.assertFalse(ComparatorUtils.contains(angryFace, longContents + 
"\uD83D"));
+        Assert.assertTrue(ComparatorUtils.contains(angryFace, "😠" + 
longContents + "😠"));
+    }
+
+    @Test
+    public void 
containsShouldSkipAMatchSplittingASurrogatePairAndFindTheNextOne() throws 
Exception {
+        Assert.assertTrue(ComparatorUtils.contains("😠b\uDE20b", "\uDE20b"));
+        Assert.assertTrue(ComparatorUtils.contains("😠" + repeat("b", 70) + 
"\uDE20" + repeat("b", 70),
+            "\uDE20" + repeat("b", 70)));
+    }
+
     private static String randomAbc(Random random, int length) {
         StringBuilder builder = new StringBuilder();
         for (int i = 0; i < length; i++) {


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to