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 5bbbf8d2991c763cd4392e3f7d0e5039a4f75db2
Author: Benoit TELLIER <[email protected]>
AuthorDate: Wed Nov 18 22:24:59 2026 +0100

    [FIX] ComparatorUtils: charge the glob matcher when it restarts
    
    4bf3a6b counted every step of the :matches glob matcher to charge the
    budget, an increment and a test on each character matched: about 40%
    more time per step, evaluateHeaderMatchesHostile running x1.5 slower
    for the same budget.
    
    The matcher now charges only when a star swallows one more character:
    the characters matched since that star, compared again, and the
    restart itself. The steps that are never undone are at most the
    lengths charged up front, so the total charged still bounds the work,
    and the match path no longer checks anything.
---
 .../apache/jsieve/comparators/ComparatorUtils.java | 18 ++++++++++-----
 .../org/apache/jsieve/EvaluationBudgetTest.java    | 27 ++++++++++++++++++++++
 2 files changed, 39 insertions(+), 6 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 398cda3..ab7c91e 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
@@ -165,14 +165,12 @@ public class ComparatorUtils {
         int afterStar = -1;
         // Position in the target the last star is currently matched up to
         int starMatchEnd = 0;
-        // Steps taken and not charged yet
-        int uncharged = 0;
+        // Steps of failed attempts not charged yet. The steps that are never
+        // undone (stars, and characters matched before the last star or in
+        // the last attempt) are at most the lengths charged up front.
+        long uncharged = 0;
         boolean mismatch = false;
         while (t < target.length) {
-            if (context != null && ++uncharged == STEPS_CHARGED_AT_ONCE) {
-                context.chargeComparison(uncharged);
-                uncharged = 0;
-            }
             if (p < pattern.length && pattern[p] == GLOB_STAR) {
                 afterStar = ++p;
                 starMatchEnd = t;
@@ -183,6 +181,14 @@ public class ComparatorUtils {
             } else if (afterStar >= 0) {
                 // Mismatch: let the last star swallow one more character.
                 // Earlier stars never need revisiting.
+                if (context != null) {
+                    // The characters matched since the star are compared again
+                    uncharged += t - starMatchEnd + 1;
+                    if (uncharged >= STEPS_CHARGED_AT_ONCE) {
+                        context.chargeComparison(uncharged);
+                        uncharged = 0;
+                    }
+                }
                 p = afterStar;
                 t = ++starMatchEnd;
             } else {
diff --git a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java 
b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java
index fc2a4f7..6458a6e 100644
--- a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java
+++ b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java
@@ -28,6 +28,7 @@ import java.nio.charset.StandardCharsets;
 import java.util.stream.Collectors;
 import java.util.stream.IntStream;
 
+import org.apache.jsieve.comparators.AsciiCasemap;
 import org.apache.jsieve.comparators.Contains;
 import org.apache.jsieve.comparators.Equals;
 import org.apache.jsieve.comparators.Matches;
@@ -124,6 +125,32 @@ public class EvaluationBudgetTest {
         
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class);
     }
 
+    @Test
+    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";
+
+        assertThatThrownBy(() -> new AsciiCasemap().matches(string, glob, 
contextWithBudget(50_000)))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+        assertThat(new AsciiCasemap().matches(string, glob, 
contextWithBudget(150_000))).isFalse();
+    }
+
+    @Test
+    public void aStarScanningAValueShouldBeChargedLinearly() throws Exception {
+        String string = "a".repeat(100_000) + "b";
+
+        // The value up front, then one step per character the star swallows
+        assertThat(new AsciiCasemap().matches(string, "*b", 
contextWithBudget(200_010))).isTrue();
+    }
+
+    private static SieveContext contextWithBudget(long budget) throws 
Exception {
+        ConfigurationManager configurationManager = new ConfigurationManager();
+        return new BaseSieveContext(configurationManager.getCommandManager(),
+            configurationManager.getComparatorManager(), 
configurationManager.getTestManager(), budget);
+    }
+
     @Test
     public void aComparatorWithoutCostShouldBeChargedTheWorstCase() throws 
Exception {
         ConfigurationManager configurationManager = new ConfigurationManager();


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

Reply via email to