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 4a3a8b115572670b7356870c18991ff08c6e60a4 Author: Benoit TELLIER <[email protected]> AuthorDate: Tue Nov 17 07:21:34 2026 +0100 [FIX] AsciiNumeric: compare the digits instead of parsing them :is was charged the length of its values, but i;ascii-numeric parsed both of them with BigInteger(String), quadratic in the number of digits: a header of a megabyte of digits against a hundred keys kept the evaluating thread busy for minutes, well within the budget. AsciiNumeric#equals now compares the digits that follow the leading zeros, linear and without allocating. Equals gets, like Contains and Matches, a method taking a SieveContext: the comparators of jSieve charge the lengths, a comparator outside jSieve is charged the product of the lengths unless it overrides it. --- .../apache/jsieve/comparators/AsciiCasemap.java | 11 ++++ .../apache/jsieve/comparators/AsciiNumeric.java | 68 +++++++++++++++------- .../apache/jsieve/comparators/ComparatorUtils.java | 9 +-- .../java/org/apache/jsieve/comparators/Equals.java | 21 +++++++ .../java/org/apache/jsieve/comparators/Octet.java | 11 ++++ .../org/apache/jsieve/EvaluationBudgetTest.java | 20 +++++++ .../jsieve/comparators/AsciiNumericTest.java | 20 +++++++ 7 files changed, 132 insertions(+), 28 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 18dc36b..c04edb1 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java +++ b/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java @@ -46,6 +46,17 @@ public class AsciiCasemap implements Comparator { toAsciiUpperCase(string2)); } + /** + * The comparison being linear, charges the lengths. + * @see org.apache.jsieve.comparators.Equals#equals(String, String, SieveContext) + */ + @Override + public boolean equals(String string1, String string2, SieveContext context) + throws SieveException { + context.chargeComparison(ComparatorUtils.linearCost(string1, string2)); + return equals(string1, string2); + } + /** * @see org.apache.jsieve.comparators.Contains#contains(String, String) */ diff --git a/core/src/main/java/org/apache/jsieve/comparators/AsciiNumeric.java b/core/src/main/java/org/apache/jsieve/comparators/AsciiNumeric.java index 8db7e0c..f62633c 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/AsciiNumeric.java +++ b/core/src/main/java/org/apache/jsieve/comparators/AsciiNumeric.java @@ -19,9 +19,9 @@ package org.apache.jsieve.comparators; +import org.apache.jsieve.SieveContext; import org.apache.jsieve.exception.FeatureException; - -import java.math.BigInteger; +import org.apache.jsieve.exception.SieveException; /** * Class AsciiNumeric implements the EQUALITY operation of the i;ascii-numeric @@ -37,33 +37,57 @@ public class AsciiNumeric implements Comparator { } /** + * Compares the leading digits of the values as numbers, without parsing + * them: linear in their length, whatever the number of digits. + * * @see org.apache.jsieve.comparators.Equals#equals(String, String) */ public boolean equals(String string1, String string2) { - final boolean result; - if (isPositiveInfinity(string1)) { - result = isPositiveInfinity(string2); - } else { - if (isPositiveInfinity(string2)) { - result = false; - } else { - final BigInteger integer1 = toInteger(string1); - final BigInteger integer2 = toInteger(string2); - result = integer1.equals(integer2); - } + if (isPositiveInfinity(string1) || isPositiveInfinity(string2)) { + return isPositiveInfinity(string1) && isPositiveInfinity(string2); + } + final int end1 = digitEnd(string1); + final int end2 = digitEnd(string2); + final int start1 = firstSignificantDigit(string1, end1); + final int start2 = firstSignificantDigit(string2, end2); + final int length = end1 - start1; + return length == end2 - start2 + && string1.regionMatches(start1, string2, start2, length); + } + + /** + * The comparison being linear, charges the lengths. + * @see org.apache.jsieve.comparators.Equals#equals(String, String, SieveContext) + */ + @Override + public boolean equals(String string1, String string2, SieveContext context) + throws SieveException { + context.chargeComparison(ComparatorUtils.linearCost(string1, string2)); + return equals(string1, string2); + } + + /** + * Index of the first character that is not a digit, the length of the + * value when all are. + */ + private int digitEnd(final String value) { + int i = 0; + while (i < value.length() && isDigit(value.charAt(i))) { + i++; } - return result; + return i; } - private BigInteger toInteger(final String value) { - int i; - for (i = 0; i < value.length(); i++) { - final char next = value.charAt(i); - if (!isDigit(next)) { - break; - } + /** + * Index of the first digit that is not a leading zero, the last digit + * standing for zero when all are. + */ + private int firstSignificantDigit(final String value, final int digitEnd) { + int i = 0; + while (i < digitEnd - 1 && value.charAt(i) == '0') { + i++; } - return new BigInteger(value.substring(0, i)); + return i; } /** 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 77759f4..b14f8dd 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java +++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java @@ -22,7 +22,6 @@ package org.apache.jsieve.comparators; import java.util.Arrays; import org.apache.jsieve.SieveContext; -import org.apache.jsieve.exception.LookupException; import org.apache.jsieve.exception.SieveException; import org.apache.jsieve.exception.SievePatternException; @@ -75,10 +74,8 @@ public class ComparatorUtils { String matchTarget, String matchArgument, SieveContext context) throws SieveException { boolean isMatched = false; - if (matchType.equals(IS_TAG)) { - context.chargeComparison(linearCost(matchTarget, matchArgument)); + if (matchType.equals(IS_TAG)) isMatched = is(comparatorName, matchTarget, matchArgument, context); - } else if (matchType.equals(CONTAINS_TAG)) isMatched = contains(comparatorName, matchTarget, matchArgument, context); @@ -352,9 +349,9 @@ public class ComparatorUtils { * @return boolean */ public static boolean is(String comparatorName, String string1, - String string2, SieveContext context) throws LookupException { + String string2, SieveContext context) throws SieveException { Equals comparatorObj = context.getComparatorManager().getComparator(comparatorName); - return comparatorObj.equals(string1, string2); + return comparatorObj.equals(string1, string2, context); } /** diff --git a/core/src/main/java/org/apache/jsieve/comparators/Equals.java b/core/src/main/java/org/apache/jsieve/comparators/Equals.java index a619967..852dcaf 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/Equals.java +++ b/core/src/main/java/org/apache/jsieve/comparators/Equals.java @@ -19,6 +19,9 @@ package org.apache.jsieve.comparators; +import org.apache.jsieve.SieveContext; +import org.apache.jsieve.exception.SieveException; + /** * Interface Equals defines the method signatures for equals comparators. */ @@ -33,4 +36,22 @@ public interface Equals { * @return boolean */ public boolean equals(String string1, String string2); + + /** + * Same as {@link #equals(String, String)}, charging the evaluation + * budget of the context with the characters compared. Its cost being + * unknown, an implementation that does not override this method is + * charged the product of the lengths before running. + * + * @param string1 not null + * @param string2 not null + * @param context not null + * @return boolean + * @throws SieveException when the budget is exhausted + */ + default boolean equals(String string1, String string2, SieveContext context) + throws SieveException { + context.chargeComparison(ComparatorUtils.quadraticCost(string1, string2)); + return equals(string1, string2); + } } diff --git a/core/src/main/java/org/apache/jsieve/comparators/Octet.java b/core/src/main/java/org/apache/jsieve/comparators/Octet.java index be795a6..b02ac41 100644 --- a/core/src/main/java/org/apache/jsieve/comparators/Octet.java +++ b/core/src/main/java/org/apache/jsieve/comparators/Octet.java @@ -45,6 +45,17 @@ public class Octet implements Comparator { return ComparatorUtils.equals(string1, string2); } + /** + * The comparison being linear, charges the lengths. + * @see org.apache.jsieve.comparators.Equals#equals(String, String, SieveContext) + */ + @Override + public boolean equals(String string1, String string2, SieveContext context) + throws SieveException { + context.chargeComparison(ComparatorUtils.linearCost(string1, string2)); + return equals(string1, string2); + } + /** * @see org.apache.jsieve.comparators.Contains#contains(String, String) */ diff --git a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java index 7460333..407e0cc 100644 --- a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java +++ b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java @@ -29,6 +29,7 @@ import java.util.stream.Collectors; import java.util.stream.IntStream; import org.apache.jsieve.comparators.Contains; +import org.apache.jsieve.comparators.Equals; import org.apache.jsieve.comparators.Matches; import org.apache.jsieve.exception.SieveException; import org.apache.jsieve.mail.ActionDiscard; @@ -86,6 +87,21 @@ public class EvaluationBudgetTest { assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class); } + @Test(timeout = 30_000) + public void manyAsciiNumericKeysOnAMegabyteOfDigitsShouldBeEvaluatedInLinearTime() throws Exception { + String digits = "7".repeat(1_000_000); + SieveMailAdapter mail = mailWithSubject(digits); + String keys = IntStream.range(0, 100) + .mapToObj(i -> "\"" + "7".repeat(1_000) + i + "\"") + .collect(Collectors.joining(", ")); + String script = "require \"comparator-i;ascii-numeric\";" + + " if header :comparator \"i;ascii-numeric\" :is \"Subject\" [" + keys + ", \"000" + digits + "\"] { discard; }"; + + JUnitUtils.interpret(mail, script); + + assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class); + } + @Test public void aComparatorWithoutCostShouldBeChargedTheWorstCase() throws Exception { ConfigurationManager configurationManager = new ConfigurationManager(); @@ -93,6 +109,7 @@ public class EvaluationBudgetTest { configurationManager.getComparatorManager(), configurationManager.getTestManager(), 1_000); Contains naiveContains = String::contains; Matches naiveMatches = (string, glob) -> string.equals(glob); + Equals naiveEquals = String::equals; assertThatThrownBy(() -> naiveContains.contains("a".repeat(100), "b".repeat(10), context)) .isInstanceOf(SieveException.class) @@ -100,6 +117,9 @@ public class EvaluationBudgetTest { assertThatThrownBy(() -> naiveMatches.matches("a".repeat(100), "b".repeat(10), context)) .isInstanceOf(SieveException.class) .hasMessageContaining("budget"); + assertThatThrownBy(() -> naiveEquals.equals("a".repeat(100), "b".repeat(10), context)) + .isInstanceOf(SieveException.class) + .hasMessageContaining("budget"); } @Test diff --git a/core/src/test/java/org/apache/jsieve/comparators/AsciiNumericTest.java b/core/src/test/java/org/apache/jsieve/comparators/AsciiNumericTest.java index 85b3e27..779a8ca 100644 --- a/core/src/test/java/org/apache/jsieve/comparators/AsciiNumericTest.java +++ b/core/src/test/java/org/apache/jsieve/comparators/AsciiNumericTest.java @@ -91,6 +91,26 @@ public class AsciiNumericTest { Assert.assertFalse(subject.equals("000001", "10")); } + @Test + public void zerosShouldBeEqual() throws Exception { + Assert.assertTrue(subject.equals("0", "000")); + Assert.assertTrue(subject.equals("00A", "0")); + Assert.assertFalse(subject.equals("0", "001")); + } + + @Test + public void equalityShouldCompareEveryDigit() throws Exception { + Assert.assertTrue(subject.equals("00123456789123456789", "123456789123456789x")); + Assert.assertFalse(subject.equals("123456789123456789", "123456789123456788")); + Assert.assertFalse(subject.equals("12345678912345678", "123456789123456789")); + } + + @Test + public void nonAsciiDigitsShouldEndTheNumber() throws Exception { + Assert.assertTrue(subject.equals("12\u0663", "12")); + Assert.assertFalse(subject.equals("\u0663", "3")); + } + @Test public void testStingsThatDoNotStartWithADigitRepresentPositiveInfinityWhenUsedInEquality() throws Exception { Assert.assertFalse(subject.equals("1", "A4")); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
