This is an automated email from the ASF dual-hosted git repository.

pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git


The following commit(s) were added to refs/heads/trunk by this push:
     new 62322b97f3 DataFormatter: avoid quadratic backtracking in 
fractionPattern (#1437)
62322b97f3 is described below

commit 62322b97f3f1bca39cdcd0b7705973833c74ad25
Author: PJ Fanning <[email protected]>
AuthorDate: Sun Oct 18 09:39:08 2026 +0100

    DataFormatter: avoid quadratic backtracking in fractionPattern (#1437)
    
    In fractionPattern, find() rescanned a run of # or digits from every
    position in it, so a format such as "#".repeat(20_000) + "/" took about
    28 s per format. Lookbehinds stop a match from starting inside a run,
    and possessive quantifiers drop backtracking that could never succeed.
    The leftmost match and its groups are unchanged.
    
    Co-authored-by: Claude Opus 5.5 <[email protected]>
---
 .../main/java/org/apache/poi/ss/usermodel/DataFormatter.java |  6 ++++--
 .../java/org/apache/poi/ss/usermodel/TestDataFormatter.java  | 12 ++++++++++++
 2 files changed, 16 insertions(+), 2 deletions(-)

diff --git a/poi/src/main/java/org/apache/poi/ss/usermodel/DataFormatter.java 
b/poi/src/main/java/org/apache/poi/ss/usermodel/DataFormatter.java
index ff62944d84..dd558017da 100644
--- a/poi/src/main/java/org/apache/poi/ss/usermodel/DataFormatter.java
+++ b/poi/src/main/java/org/apache/poi/ss/usermodel/DataFormatter.java
@@ -157,9 +157,11 @@ public class DataFormatter {
 
     /**
      * A regex to identify a fraction pattern.
-     * This requires that replaceAll("\\?", "#") has already been called
+     * This requires that replaceAll("\\?", "#") has already been called.
+     * The lookbehinds and possessive quantifiers stop find() from rescanning 
a run of # or digits
+     * from every position in it, which was quadratic; the leftmost match and 
its groups are unchanged.
      */
-    private static final Pattern fractionPattern = 
Pattern.compile("(?:([#\\d]+)\\s+)?(#+)\\s*/\\s*([#\\d]+)");
+    private static final Pattern fractionPattern = 
Pattern.compile("(?:(?<![#\\d])([#\\d]++)\\s+)?(?<!#)(#++)\\s*/\\s*([#\\d]+)");
 
     /**
      * A regex to strip junk out of fraction formats
diff --git 
a/poi/src/test/java/org/apache/poi/ss/usermodel/TestDataFormatter.java 
b/poi/src/test/java/org/apache/poi/ss/usermodel/TestDataFormatter.java
index b96541e5c6..a4f2e91178 100644
--- a/poi/src/test/java/org/apache/poi/ss/usermodel/TestDataFormatter.java
+++ b/poi/src/test/java/org/apache/poi/ss/usermodel/TestDataFormatter.java
@@ -398,6 +398,18 @@ class TestDataFormatter {
         assertEquals("11",   dfUS.formatRawCellContents(11.0, -1, "# #/#"));
     }
 
+    @Test
+    void testFractionWithLongRun() {
+        DataFormatter dfUS = new DataFormatter(Locale.US);
+
+        // a long run of # or digits before a '/' used to backtrack 
quadratically in fractionPattern
+        for (String format : new String[] {"#".repeat(50_000) + "/", "0" + 
"#".repeat(50_000) + "/", "1".repeat(50_000) + " #/"}) {
+            String result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+                    () -> dfUS.formatRawCellContents(1.5, -1, format));
+            assertEquals("1 1/2", result);
+        }
+    }
+
     /**
      * Test that _x (blank with the space taken by "x")
      *  and *x (fill to the column width with "x"s) are


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

Reply via email to