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]
