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 0def8f748c9a470d0ca325081dab014939bcd268
Author: Benoit TELLIER <[email protected]>
AuthorDate: Wed Nov 18 22:27:26 2026 +0100

    [FIX] AsciiCasemap: fold the case in the comparisons instead of copying
    
    i;ascii-casemap upper-cased a copy of both values on every comparison,
    two copies of each (char[] then String), even when nothing changed:
    the whole body again for each key of body :matches, and the key, a
    constant of the script, again for each value. This was 37-40% of the
    bytes allocated by evaluateBodyMatches and 95% of those of
    evaluateHeaderContainsHostile.
    
    equals, contains and matches now apply the RFC 4790 a-z folding to the
    characters as they compare them: the glob literals are folded once
    when compiled, the contents of :contains is upper-cased once, and the
    value is never copied. A contents without letter keeps the indexOf
    search. A contents with letters is searched with Knuth-Morris-Pratt
    whatever its length: no intrinsic applies, and a naive search would
    compare up to 64 characters per character of the value while the
    budget is charged linearly. The folding stays ASCII only, so
    equalsIgnoreCase and regionMatches are not used. toAsciiUpperCase
    returns its argument when nothing changes.
---
 .../apache/jsieve/comparators/AsciiCasemap.java    |  27 +++--
 .../apache/jsieve/comparators/ComparatorUtils.java | 113 +++++++++++++++++++--
 .../jsieve/comparators/AsciiCasemapTest.java       | 100 ++++++++++++++++++
 3 files changed, 215 insertions(+), 25 deletions(-)

diff --git a/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java 
b/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
index c04edb1..b4a089e 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
@@ -42,8 +42,7 @@ public class AsciiCasemap implements Comparator {
      * @see org.apache.jsieve.comparators.Equals#equals(String, String)
      */
     public boolean equals(String string1, String string2) {
-        return ComparatorUtils.equals(toAsciiUpperCase(string1),
-                toAsciiUpperCase(string2));
+        return ComparatorUtils.equalsIgnoringAsciiCase(string1, string2);
     }
 
     /**
@@ -61,8 +60,7 @@ public class AsciiCasemap implements Comparator {
      * @see org.apache.jsieve.comparators.Contains#contains(String, String)
      */
     public boolean contains(String container, String content) {
-        return ComparatorUtils.contains(toAsciiUpperCase(container),
-                toAsciiUpperCase(content));
+        return ComparatorUtils.contains(container, content, true);
     }
 
     /**
@@ -70,8 +68,14 @@ public class AsciiCasemap implements Comparator {
      */
     public boolean matches(String string, String glob)
             throws SievePatternException {
-        return ComparatorUtils.matches(toAsciiUpperCase(string),
-                toAsciiUpperCase(glob));
+        try {
+            return ComparatorUtils.matches(string, glob, null, true);
+        } catch (SievePatternException e) {
+            throw e;
+        } catch (SieveException e) {
+            // Not reached: nothing is charged without context
+            throw new IllegalStateException(e);
+        }
     }
 
     /**
@@ -92,8 +96,7 @@ public class AsciiCasemap implements Comparator {
     @Override
     public boolean matches(String string, String glob, SieveContext context)
             throws SieveException {
-        return ComparatorUtils.matches(toAsciiUpperCase(string),
-                toAsciiUpperCase(glob), context);
+        return ComparatorUtils.matches(string, glob, context, true);
     }
 
     /**
@@ -103,13 +106,7 @@ public class AsciiCasemap implements Comparator {
      * the string.
      */
     public static String toAsciiUpperCase(String string) {
-        final char[] chars = string.toCharArray();
-        for (int i = 0; i < chars.length; i++) {
-            if (chars[i] >= 'a' && chars[i] <= 'z') {
-                chars[i] = (char) (chars[i] - ('a' - 'A'));
-            }
-        }
-        return new String(chars);
+        return ComparatorUtils.toAsciiUpperCase(string);
     }
 
 }
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 f7d6ae4..40548aa 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
@@ -153,10 +153,20 @@ public class ComparatorUtils {
      */
     static public boolean matches(String string, String glob, SieveContext 
context)
             throws SieveException {
+        return matches(string, glob, context, false);
+    }
+
+    /**
+     * Same as {@link #matches(String, String, SieveContext)}, comparing the
+     * characters after {@link #toAsciiUpperCase(int)} when
+     * <code>ignoreAsciiCase</code>, without copying the string.
+     */
+    static boolean matches(String string, String glob, SieveContext context,
+            boolean ignoreAsciiCase) throws SieveException {
         if (context != null) {
             context.chargeComparison(linearCost(string, glob));
         }
-        final int[] pattern = compileGlob(glob);
+        final int[] pattern = compileGlob(glob, ignoreAsciiCase);
         // The string is walked by code point, without copying it: ? matches
         // a character and a match never splits a surrogate pair
         final int length = string.length();
@@ -180,11 +190,12 @@ public class ComparatorUtils {
                 starMatchEnd = t;
                 continue;
             }
-            final int c = string.codePointAt(t);
+            final int codePoint = string.codePointAt(t);
+            final int c = ignoreAsciiCase ? toAsciiUpperCase(codePoint) : 
codePoint;
             if (p < pattern.length
                     && (pattern[p] == GLOB_ANY || pattern[p] == c)) {
                 p++;
-                t += Character.charCount(c);
+                t += Character.charCount(codePoint);
             } else if (afterStar >= 0) {
                 // Mismatch: let the last star swallow one more character.
                 // Earlier stars never need revisiting.
@@ -226,8 +237,10 @@ public class ComparatorUtils {
      * 2.7.1 and 2.4.2, a backslash makes the following character literal,
      * an undefined escape such as <code>\a</code> standing for <code>a</code>.
      * A trailing backslash stands for itself. Consecutive stars are merged.
+     * Literals are upper-cased by {@link #toAsciiUpperCase(int)} when
+     * <code>ignoreAsciiCase</code>.
      */
-    private static int[] compileGlob(String glob) {
+    private static int[] compileGlob(String glob, boolean ignoreAsciiCase) {
         final int[] codePoints = glob.codePoints().toArray();
         final int[] result = new int[codePoints.length];
         int length = 0;
@@ -240,9 +253,9 @@ public class ComparatorUtils {
             } else if (c == '?') {
                 result[length++] = GLOB_ANY;
             } else if (c == '\\' && i + 1 < codePoints.length) {
-                result[length++] = codePoints[++i];
+                result[length++] = ignoreAsciiCase ? 
toAsciiUpperCase(codePoints[++i]) : codePoints[++i];
             } else {
-                result[length++] = c;
+                result[length++] = ignoreAsciiCase ? toAsciiUpperCase(c) : c;
             }
         }
         return Arrays.copyOf(result, length);
@@ -264,8 +277,9 @@ public class ComparatorUtils {
      * 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.
+     * longer contents, or one compared ignoring the ASCII case, is searched
+     * with Knuth-Morris-Pratt, which compares at most
+     * <code>2 * container length + contents length</code> characters.
      * </p>
      *
      * @param container
@@ -273,11 +287,29 @@ public class ComparatorUtils {
      * @return boolean
      */
     static public boolean contains(String container, String contents) {
+        return contains(container, contents, false);
+    }
+
+    /**
+     * Same as {@link #contains(String, String)}, comparing the characters
+     * after {@link #toAsciiUpperCase(int)} when <code>ignoreAsciiCase</code>,
+     * without copying the container.
+     */
+    static boolean contains(String container, String contents, boolean 
ignoreAsciiCase) {
         final int length = contents.length();
         if (length == 0) {
             return true;
         }
-        if (length <= SHORT_CONTENTS) {
+        if (ignoreAsciiCase) {
+            // The contents is short, usually a constant of the script
+            contents = toAsciiUpperCase(contents);
+            if (!hasAsciiLetter(contents)) {
+                // A character of the container matches a non-letter only
+                // when equal to it: the case is irrelevant
+                ignoreAsciiCase = false;
+            }
+        }
+        if (!ignoreAsciiCase && 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)) {
@@ -286,11 +318,14 @@ public class ComparatorUtils {
             }
             return false;
         }
+        // Ignoring the case, no intrinsic applies: a naive search would 
compare
+        // up to SHORT_CONTENTS characters per character of the container while
+        // the budget is charged linearly
         final int[] border = borders(contents);
         // Number of characters of contents matched so far
         int matched = 0;
         for (int i = 0; i < container.length(); i++) {
-            final char c = container.charAt(i);
+            final char c = ignoreAsciiCase ? 
toAsciiUpperCase(container.charAt(i)) : container.charAt(i);
             while (matched > 0 && contents.charAt(matched) != c) {
                 matched = border[matched - 1];
             }
@@ -309,6 +344,64 @@ public class ComparatorUtils {
         return false;
     }
 
+    /**
+     * Maps a-z onto A-Z and leaves every other character untouched, as
+     * defined by RFC 4790 section 9.2.
+     */
+    static int toAsciiUpperCase(int c) {
+        return c >= 'a' && c <= 'z' ? c - ('a' - 'A') : c;
+    }
+
+    private static char toAsciiUpperCase(char c) {
+        return c >= 'a' && c <= 'z' ? (char) (c - ('a' - 'A')) : c;
+    }
+
+    /**
+     * Same as {@link #toAsciiUpperCase(int)} for each character of the
+     * string, the string itself being returned when nothing changes.
+     */
+    static String toAsciiUpperCase(String string) {
+        int i = 0;
+        while (i < string.length() && toAsciiUpperCase(string.charAt(i)) == 
string.charAt(i)) {
+            i++;
+        }
+        if (i == string.length()) {
+            return string;
+        }
+        final char[] chars = string.toCharArray();
+        for (; i < chars.length; i++) {
+            chars[i] = toAsciiUpperCase(chars[i]);
+        }
+        return new String(chars);
+    }
+
+    private static boolean hasAsciiLetter(String upperCase) {
+        for (int i = 0; i < upperCase.length(); i++) {
+            final char c = upperCase.charAt(i);
+            if (c >= 'A' && c <= 'Z') {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Equality of the strings after {@link #toAsciiUpperCase(int)}, without
+     * copying them.
+     */
+    static boolean equalsIgnoringAsciiCase(String string1, String string2) {
+        final int length = string1.length();
+        if (length != string2.length()) {
+            return false;
+        }
+        for (int i = 0; i < length; i++) {
+            if (toAsciiUpperCase(string1.charAt(i)) != 
toAsciiUpperCase(string2.charAt(i))) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     /**
      * Longest contents searched by {@link String#indexOf(String, int)}: its
      * worst case, quadratic, stays within a constant factor of a linear
diff --git 
a/core/src/test/java/org/apache/jsieve/comparators/AsciiCasemapTest.java 
b/core/src/test/java/org/apache/jsieve/comparators/AsciiCasemapTest.java
index e11470b..35cb53d 100644
--- a/core/src/test/java/org/apache/jsieve/comparators/AsciiCasemapTest.java
+++ b/core/src/test/java/org/apache/jsieve/comparators/AsciiCasemapTest.java
@@ -20,6 +20,7 @@
 package org.apache.jsieve.comparators;
 
 import java.util.Locale;
+import java.util.Random;
 
 import org.junit.Assert;
 import org.junit.Test;
@@ -82,4 +83,103 @@ public class AsciiCasemapTest {
             Locale.setDefault(defaultLocale);
         }
     }
+
+    @Test
+    public void unicodeCaseFoldingsShouldNotApply() throws Exception {
+        // equalsIgnoreCase or regionMatches would fold these
+        Assert.assertFalse(subject.equals("\u017F", "S"));
+        Assert.assertFalse(subject.equals("\u212A", "k"));
+        Assert.assertFalse(subject.contains("x\u212Ax", "K"));
+        Assert.assertFalse(subject.contains("x\u017Fx" + "y".repeat(70), "S" + 
"y".repeat(70)));
+        Assert.assertFalse(subject.matches("\u212A", "k"));
+    }
+
+    @Test
+    public void longContentsShouldIgnoreAsciiCase() throws Exception {
+        String key = "Lorem Ipsum ".repeat(10);
+
+        Assert.assertTrue(subject.contains("xx" + key.toUpperCase(Locale.ROOT) 
+ "yy", key));
+        Assert.assertTrue(subject.contains("xx" + key.toLowerCase(Locale.ROOT) 
+ "yy", key.toUpperCase(Locale.ROOT)));
+        Assert.assertFalse(subject.contains("xx" + key.substring(1) + "yy", 
key));
+    }
+
+    @Test(timeout = 3000)
+    public void shortContentsShouldBeSearchedInLinearTime() throws Exception {
+        // A naive search compares 64 characters at each position: ~7 seconds
+        String container = "a".repeat(10_000_000);
+        String key = "A".repeat(63) + "B";
+
+        for (int i = 0; i < 10; i++) {
+            Assert.assertFalse(subject.contains(container, key));
+        }
+    }
+
+    @Test
+    public void contentsWithoutLetterShouldBeFound() throws Exception {
+        Assert.assertTrue(subject.contains("Price: 12.50 EUR", "12.50"));
+        Assert.assertFalse(subject.contains("Price: 12.50 EUR", "12,50"));
+    }
+
+    @Test
+    public void comparisonsShouldAgreeWithUpperCasedCopiesOnRandomStrings() 
throws Exception {
+        Random random = new Random(42);
+        for (int i = 0; i < 50_000; i++) {
+            String first = randomString(random, random.nextInt(12));
+            String second = randomString(random, random.nextInt(5));
+            assertAgreesWithUpperCasedCopies(first, second);
+        }
+        for (int i = 0; i < 2_000; i++) {
+            // Beyond 64 characters, contents is no longer searched by the 
short path
+            String second = randomString(random, 65 + random.nextInt(5));
+            String first = randomString(random, random.nextInt(8)) + 
flipCase(random, second)
+                + randomString(random, random.nextInt(8));
+            assertAgreesWithUpperCasedCopies(first, second);
+            assertAgreesWithUpperCasedCopies(first.substring(1), second);
+        }
+    }
+
+    private void assertAgreesWithUpperCasedCopies(String first, String second) 
throws Exception {
+        String upperFirst = upperCaseCopy(first);
+        String upperSecond = upperCaseCopy(second);
+        String message = "first=" + first + " second=" + second;
+        Assert.assertEquals(message, ComparatorUtils.contains(upperFirst, 
upperSecond), subject.contains(first, second));
+        Assert.assertEquals(message, ComparatorUtils.matches(upperFirst, 
upperSecond), subject.matches(first, second));
+        Assert.assertEquals(message, upperFirst.equals(upperSecond), 
subject.equals(first, second));
+        Assert.assertEquals(message, upperFirst.equals(upperSecond), 
subject.equals(first, flipCase(new Random(0), second)));
+    }
+
+    /**
+     * The definition of i;ascii-casemap, as implemented before the
+     * comparisons folded the case in their loops.
+     */
+    private static String upperCaseCopy(String string) {
+        char[] chars = string.toCharArray();
+        for (int i = 0; i < chars.length; i++) {
+            if (chars[i] >= 'a' && chars[i] <= 'z') {
+                chars[i] = (char) (chars[i] - ('a' - 'A'));
+            }
+        }
+        return new String(chars);
+    }
+
+    private static final String[] ALPHABET = {"a", "A", "b", "B", "z", "Z", 
"*", "?", "\\", "@", "[", "`", "{",
+        "\u00E9", "\u00C9", "\u00DF", "\u017F", "\u212A", "\uD83D\uDE00", 
"\uD83D", "\uDE00"};
+
+    private static String randomString(Random random, int length) {
+        StringBuilder builder = new StringBuilder();
+        for (int i = 0; i < length; i++) {
+            builder.append(ALPHABET[random.nextInt(ALPHABET.length)]);
+        }
+        return builder.toString();
+    }
+
+    private static String flipCase(Random random, String string) {
+        char[] chars = string.toCharArray();
+        for (int i = 0; i < chars.length; i++) {
+            if (random.nextBoolean() && chars[i] < 128 && 
Character.isLetter(chars[i])) {
+                chars[i] = Character.isUpperCase(chars[i]) ? 
Character.toLowerCase(chars[i]) : Character.toUpperCase(chars[i]);
+            }
+        }
+        return new String(chars);
+    }
 }


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

Reply via email to