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]
