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 db0182520c3770b88119b181e46d96ea28d64d44 Author: Benoit TELLIER <[email protected]> AuthorDate: Wed Nov 18 23:26:48 2026 +0100 [FIX] ComparatorUtils: compare the end of a glob after its last star once Walking the value by code point made evaluateHeaderMatchesHostile x5.4 slower than reading an int[]: "*aaa...ab" against "aaa...a" retried the part after the star at each position, String#codePointAt taking several times charAt at each step. After the last star, the pattern can only match the end of the value, each of its elements matching one character: it is now compared there once, from the end. Such a glob is linear, only charged its lengths up front. The matcher also reads the value with charAt, pairing a high surrogate with the low one that follows instead of calling codePointAt. ? still matches a character and a match never splits a surrogate pair. --- .../apache/jsieve/comparators/ComparatorUtils.java | 55 ++++++++++++++++++++-- .../org/apache/jsieve/EvaluationBudgetTest.java | 14 +++++- .../jsieve/comparator/ComparatorUtilsTest.java | 14 ++++++ 3 files changed, 78 insertions(+), 5 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 40548aa..e944a02 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java +++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java @@ -184,18 +184,39 @@ public class ComparatorUtils { // the last attempt) are at most the lengths charged up front. long uncharged = 0; boolean mismatch = false; + // After the last star, the pattern can only match the end of the + // string: it is compared there once instead of at each position + int lastStar = pattern.length - 1; + while (lastStar >= 0 && pattern[lastStar] != GLOB_STAR) { + lastStar--; + } while (t < length) { if (p < pattern.length && pattern[p] == GLOB_STAR) { + if (p == lastStar) { + if (context != null) { + context.chargeComparison(uncharged); + } + return matchesEnd(string, t, pattern, p + 1, ignoreAsciiCase); + } afterStar = ++p; starMatchEnd = t; continue; } - final int codePoint = string.codePointAt(t); - final int c = ignoreAsciiCase ? toAsciiUpperCase(codePoint) : codePoint; + // String#codePointAt costs several times charAt on this path, + // taken for each step: a pair is only looked for at a high + // surrogate + final char ch = string.charAt(t); + int c = ignoreAsciiCase ? toAsciiUpperCase(ch) : ch; + int width = 1; + if (Character.isHighSurrogate(ch) && t + 1 < length + && Character.isLowSurrogate(string.charAt(t + 1))) { + c = Character.toCodePoint(ch, string.charAt(t + 1)); + width = 2; + } if (p < pattern.length && (pattern[p] == GLOB_ANY || pattern[p] == c)) { p++; - t += Character.charCount(codePoint); + t += width; } else if (afterStar >= 0) { // Mismatch: let the last star swallow one more character. // Earlier stars never need revisiting. @@ -227,6 +248,34 @@ public class ComparatorUtils { return p == pattern.length; } + /** + * Whether the end of <code>string</code>, from <code>start</code> on, + * ends with <code>pattern</code> from <code>from</code> on, a part + * without star: each of its elements matches one character, so the + * characters it matches are the last ones. + */ + private static boolean matchesEnd(String string, int start, int[] pattern, int from, + boolean ignoreAsciiCase) { + int i = string.length(); + for (int k = pattern.length - 1; k >= from; k--) { + if (i <= start) { + return false; + } + final char ch = string.charAt(i - 1); + int c = ignoreAsciiCase ? toAsciiUpperCase(ch) : ch; + i--; + if (Character.isLowSurrogate(ch) && i > start + && Character.isHighSurrogate(string.charAt(i - 1))) { + c = Character.toCodePoint(string.charAt(i - 1), ch); + i--; + } + if (pattern[k] != GLOB_ANY && pattern[k] != c) { + return false; + } + } + return true; + } + private static final int GLOB_STAR = -1; private static final int GLOB_ANY = -2; diff --git a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java index 6458a6e..ffa14b5 100644 --- a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java +++ b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java @@ -50,7 +50,7 @@ public class EvaluationBudgetTest { @Test(timeout = 10_000) public void aPathologicalMatchOnALargeHeaderShouldFailOnceTheBudgetIsSpent() throws Exception { SieveMailAdapter mail = mailWithSubject("a".repeat(2_000_000)); - String script = "if header :matches \"Subject\" \"*" + "a".repeat(10_000) + "b\" { discard; }"; + String script = "if header :matches \"Subject\" \"*" + "a".repeat(10_000) + "b*\" { discard; }"; assertThatThrownBy(() -> factoryWithBudget(100_000_000).interpret(mail, script(script))) .isInstanceOf(SieveException.class) @@ -129,7 +129,7 @@ public class EvaluationBudgetTest { public void theGlobMatcherShouldBeChargedTheCharactersItComparesAgain() throws Exception { // Each of the ~1000 attempts compares up to 100 characters before failing String string = "a".repeat(1_000); - String glob = "*" + "a".repeat(99) + "b"; + String glob = "*" + "a".repeat(99) + "b*"; assertThatThrownBy(() -> new AsciiCasemap().matches(string, glob, contextWithBudget(50_000))) .isInstanceOf(SieveException.class) @@ -145,6 +145,16 @@ public class EvaluationBudgetTest { assertThat(new AsciiCasemap().matches(string, "*b", contextWithBudget(200_010))).isTrue(); } + @Test + public void theEndAfterTheLastStarShouldBeComparedOnce() throws Exception { + String string = "a".repeat(100_000); + String glob = "*" + "a".repeat(999) + "b"; + + // The lengths up front only: the end is not searched for + assertThat(new AsciiCasemap().matches(string, glob, contextWithBudget(101_003))).isFalse(); + assertThat(new AsciiCasemap().matches(string + "B", glob, contextWithBudget(101_004))).isTrue(); + } + private static SieveContext contextWithBudget(long budget) throws Exception { ConfigurationManager configurationManager = new ConfigurationManager(); return new BaseSieveContext(configurationManager.getCommandManager(), 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 dc5c553..fa1a7c9 100644 --- a/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java +++ b/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java @@ -191,6 +191,20 @@ public class ComparatorUtilsTest { assertMatch("\uDE00\uD83D\uDE00", "??"); } + @Test + public void theEndAfterTheLastStarShouldBeMatchedByCharacter() throws Exception { + assertMatch("x\uD83D\uDE00", "*?"); + assertMatch("\uD83D\uDE00", "*?"); + assertNoMatch("\uD83D\uDE00", "*??"); + assertMatch("a\uD83D\uDE00\uD83Db", "a*\uD83D\uDE00?b"); + assertNoMatch("ab", "a*ab"); + assertMatch("aab", "a*ab"); + assertMatch("xay", "*a*y"); + assertNoMatch("xa", "*a*y"); + assertMatch("anything", "*"); + assertMatch("anything", "any*"); + } + @Test public void supplementaryCharacterShouldNotBeAWildcard() throws Exception { // U+1002A must not be truncated into '*' --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
