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]