You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@poi.apache.org by fa...@apache.org on 2026/10/18 10:08:04 UTC
(poi) branch trunk updated: Avoid quadratic regex scans of number format strings and embedded file names (#1440)
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 e1850d7c34 Avoid quadratic regex scans of number format strings and embedded file names (#1440)
e1850d7c34 is described below
commit e1850d7c34bcafe4e46feb60207d006ca990aa4f
Author: PJ Fanning <pj...@users.noreply.github.com>
AuthorDate: Sun Oct 18 11:07:59 2026 +0100
Avoid quadratic regex scans of number format strings and embedded file names (#1440)
DataFormatter: remove colours in one pass, replace the [$...] locale/currency
regex with a scanner that finds the same matches, stop endsWithCommas from
retrying every comma in a run that is not at the end, and count the scaling
commas without repeated substrings. DateUtil: make the first part of
date_ptrn3b possessive. EmbeddedData: take the name after the last separator
with lastIndexOf instead of a replaceAll. Results are unchanged.
Co-authored-by: Claude Opus 5.5 <no...@anthropic.com>
---
.../ss/tests/extractor/TestEmbeddedExtractor.java | 15 +++
.../org/apache/poi/ss/extractor/EmbeddedData.java | 4 +-
.../org/apache/poi/ss/usermodel/DataFormatter.java | 141 ++++++++++++++-------
.../java/org/apache/poi/ss/usermodel/DateUtil.java | 4 +-
.../apache/poi/ss/usermodel/TestDataFormatter.java | 54 ++++++++
.../org/apache/poi/ss/usermodel/TestDateUtil.java | 13 ++
6 files changed, 186 insertions(+), 45 deletions(-)
diff --git a/poi-ooxml/src/test/java/org/apache/poi/ss/tests/extractor/TestEmbeddedExtractor.java b/poi-ooxml/src/test/java/org/apache/poi/ss/tests/extractor/TestEmbeddedExtractor.java
index ca3ec7d1fe..83546b31c0 100644
--- a/poi-ooxml/src/test/java/org/apache/poi/ss/tests/extractor/TestEmbeddedExtractor.java
+++ b/poi-ooxml/src/test/java/org/apache/poi/ss/tests/extractor/TestEmbeddedExtractor.java
@@ -19,11 +19,13 @@ package org.apache.poi.ss.tests.extractor;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import java.io.IOException;
import java.io.InputStream;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
+import java.time.Duration;
import java.util.ArrayList;
import java.util.Base64;
import java.util.List;
@@ -43,6 +45,19 @@ import org.junit.jupiter.api.Test;
class TestEmbeddedExtractor {
private static final POIDataSamples samples = POIDataSamples.getSpreadSheetInstance();
+ @Test
+ void filenameWithoutPath() {
+ assertEquals("a.pdf", new EmbeddedData("C:\\docs/x\\ a.pdf ", null, null).getFilename());
+ assertEquals("", new EmbeddedData("dir/", null, null).getFilename());
+ assertEquals("unknown.bin", new EmbeddedData(null, null, null).getFilename());
+
+ // a long name without a separator used to be retried from every character, which was quadratic
+ String name = "a".repeat(50_000) + ".pdf";
+ EmbeddedData ed = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> new EmbeddedData(name, null, null));
+ assertEquals(name, ed.getFilename());
+ }
+
@Test
void extractPDFfromEMF() throws Exception {
InputStream fis = samples.openResourceAsStream("Basic_Expense_Template_2011.xls");
diff --git a/poi/src/main/java/org/apache/poi/ss/extractor/EmbeddedData.java b/poi/src/main/java/org/apache/poi/ss/extractor/EmbeddedData.java
index 0e598b3175..4b82b34604 100644
--- a/poi/src/main/java/org/apache/poi/ss/extractor/EmbeddedData.java
+++ b/poi/src/main/java/org/apache/poi/ss/extractor/EmbeddedData.java
@@ -50,7 +50,9 @@ public class EmbeddedData {
if (filename == null) {
this.filename = "unknown.bin";
} else {
- this.filename = filename.replaceAll("[^/\\\\]*[/\\\\]", "").trim();
+ // only the name after the last '/' or '\', without a regex that was quadratic on a long name
+ int lastSeparator = Math.max(filename.lastIndexOf('/'), filename.lastIndexOf('\\'));
+ this.filename = filename.substring(lastSeparator + 1).trim();
}
}
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 dd558017da..e1fb9332e6 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
@@ -27,8 +27,10 @@ import java.text.FieldPosition;
import java.text.Format;
import java.text.ParsePosition;
import java.text.SimpleDateFormat;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Date;
+import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
@@ -139,12 +141,6 @@ public class DataFormatter {
/** Pattern to find formats with condition ranges e.g. [>=100] */
private static final Pattern rangeConditionalPattern = Pattern.compile("\\[\\s*(<>|<=|>=|<|>|=)\\s*-?(?:[0-9]*\\.)?[0-9]+\\s*]");
- /**
- * A regex to find locale patterns like [$$-1009] and [$?-452], or a currency string without a locale like [$USD].
- * Note that we don't currently process these into locales
- */
- private static final Pattern localePatternGroup = Pattern.compile("(\\[\\$[^-\\]]*(?:-[0-9A-Za-z]+)?])");
-
/**
* A regex to match the colour formatting's rules.
* Allowed colours are: Black, Blue, Cyan, Green,
@@ -519,21 +515,7 @@ public class DataFormatter {
// Remove colour formatting if present
if (formatStr != null) {
- Matcher colourM = colorPattern.matcher(formatStr);
- while (colourM.find()) {
- String colour = colourM.group();
-
- // Paranoid replacement...
- int at = formatStr.indexOf(colour);
- if (at == -1) break;
- String nFormatStr = formatStr.substring(0, at) +
- formatStr.substring(at + colour.length());
- if (nFormatStr.equals(formatStr)) break;
-
- // Try again in case there's multiple
- formatStr = nFormatStr;
- colourM = colorPattern.matcher(formatStr);
- }
+ formatStr = removeColours(formatStr);
}
// Strip off the numeral style: Arabic digits are shown instead of Chinese/Japanese numerals
@@ -544,22 +526,7 @@ public class DataFormatter {
// Strip off the locale information, we use an instance-wide locale for everything.
// The locale is optional, e.g. "[$USD]" is just the currency string
if (formatStr != null) {
- Matcher m = localePatternGroup.matcher(formatStr);
- StringBuilder sb = new StringBuilder(formatStr.length());
- while (m.find()) {
- String match = m.group();
- int dash = match.indexOf('-');
- String symbol = match.substring(2, dash < 0 ? match.length() - 1 : dash);
- // escaped, so that letters and dots in it, e.g. "EUR" or "Bs.", are not taken as part of the pattern
- // (quoted text is not used, as date letters in it still make it count as a date format)
- StringBuilder escaped = new StringBuilder(symbol.length() * 2);
- for (int i = 0; i < symbol.length(); i++) {
- escaped.append('\\').append(symbol.charAt(i));
- }
- m.appendReplacement(sb, Matcher.quoteReplacement(escaped.toString()));
- }
- m.appendTail(sb);
- formatStr = sb.toString();
+ formatStr = replaceLocalePatterns(formatStr);
}
// Check for special cases
@@ -638,6 +605,92 @@ public class DataFormatter {
return null;
}
+ /**
+ * Removes the colours, e.g. [Red] or [Color 10]. Removing one can make another, e.g. "[Re[Red]d]",
+ * and that is removed too.
+ * A colour has no brackets inside it, so one can only end at a ']' and start at the last '[' before it.
+ * This is a single pass: finding the first colour and searching again from the start after removing it
+ * was quadratic.
+ */
+ private static String removeColours(String formatStr) {
+ StringBuilder sb = new StringBuilder(formatStr.length());
+ // the positions in sb of the '[' after the last ']' that was kept
+ Deque<Integer> opens = new ArrayDeque<>();
+ Matcher m = colorPattern.matcher(sb);
+ for (int i = 0; i < formatStr.length(); i++) {
+ char c = formatStr.charAt(i);
+ sb.append(c);
+ if (c == '[') {
+ opens.push(sb.length() - 1);
+ } else if (c == ']') {
+ if (!opens.isEmpty()) {
+ int start = opens.peek();
+ m.reset(sb).region(start, sb.length());
+ if (m.matches()) {
+ sb.setLength(start);
+ opens.pop();
+ continue;
+ }
+ }
+ // no colour can include this ']' or anything before it
+ opens.clear();
+ }
+ }
+ return sb.toString();
+ }
+
+ /**
+ * Replaces the locale patterns like [$$-1009] and [$?-452], or a currency string without a locale like [$USD],
+ * with the escaped currency string. Note that we don't currently process these into locales.
+ * <p>
+ * This finds the same matches as the regex {@code \[\$[^-\]]*(?:-[0-9A-Za-z]+)?]}, but does not try again
+ * from every "[$" before a failed match, which was quadratic.
+ */
+ private static String replaceLocalePatterns(String formatStr) {
+ final int length = formatStr.length();
+ StringBuilder sb = new StringBuilder(length);
+ int copied = 0;
+ int start = formatStr.indexOf("[$");
+ while (start >= 0) {
+ // the currency string runs to the first '-' or ']'
+ int end = start + 2;
+ while (end < length && formatStr.charAt(end) != '-' && formatStr.charAt(end) != ']') {
+ end++;
+ }
+ if (end == length) {
+ // no later "[$" can match either
+ break;
+ }
+ int dash = -1;
+ if (formatStr.charAt(end) == '-') {
+ // the locale must be letters and digits, then the ']'
+ dash = end++;
+ while (end < length && isAsciiLetterOrDigit(formatStr.charAt(end))) {
+ end++;
+ }
+ if (end == dash + 1 || end == length || formatStr.charAt(end) != ']') {
+ // a "[$" before the '-' would stop at the same '-' and fail the same way
+ start = formatStr.indexOf("[$", dash + 1);
+ continue;
+ }
+ }
+ sb.append(formatStr, copied, start);
+ // escaped, so that letters and dots in it, e.g. "EUR" or "Bs.", are not taken as part of the pattern
+ // (quoted text is not used, as date letters in it still make it count as a date format)
+ for (int i = start + 2; i < (dash < 0 ? end : dash); i++) {
+ sb.append('\\').append(formatStr.charAt(i));
+ }
+ copied = end + 1;
+ start = formatStr.indexOf("[$", copied);
+ }
+ sb.append(formatStr, copied, length);
+ return sb.toString();
+ }
+
+ private static boolean isAsciiLetterOrDigit(char c) {
+ return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
+ }
+
String adjustTo4DigitYearsIfConfigured(String format) {
if (use4DigitYearsInAllDateFormats) {
int ypos2 = format.indexOf("yy");
@@ -1195,7 +1248,9 @@ public class DataFormatter {
private static class InternalDecimalFormatWithScale extends Format {
- private static final Pattern endsWithCommas = Pattern.compile("(,+)$");
+ // the lookbehind and the possessive quantifier stop find() from trying every comma in a run
+ // that is not at the end, which was quadratic
+ private static final Pattern endsWithCommas = Pattern.compile("(?<!,)(,++)$");
private final BigDecimal divider;
private static final BigDecimal ONE_THOUSAND = BigDecimal.valueOf(1000);
private final DecimalFormat df;
@@ -1480,12 +1535,12 @@ public class DataFormatter {
while (end < section.length() && "0#?,".indexOf(section.charAt(end)) >= 0) {
end++;
}
- String integerPart = section.substring(start, end);
- int scalingCommas = 0;
- while (integerPart.endsWith(",")) {
- integerPart = integerPart.substring(0, integerPart.length() - 1);
- scalingCommas++;
+ int digitsEnd = end;
+ while (section.charAt(digitsEnd - 1) == ',') {
+ digitsEnd--;
}
+ String integerPart = section.substring(start, digitsEnd);
+ int scalingCommas = end - digitsEnd;
String suffix = section.substring(end);
boolean beforeDecimalPoint = suffix.startsWith(".");
if (!beforeDecimalPoint && suffix.indexOf(',') >= 0) {
diff --git a/poi/src/main/java/org/apache/poi/ss/usermodel/DateUtil.java b/poi/src/main/java/org/apache/poi/ss/usermodel/DateUtil.java
index d82dfe4044..d7bf29b504 100644
--- a/poi/src/main/java/org/apache/poi/ss/usermodel/DateUtil.java
+++ b/poi/src/main/java/org/apache/poi/ss/usermodel/DateUtil.java
@@ -73,8 +73,10 @@ public class DateUtil {
private static final Pattern date_ptrn3a = Pattern.compile("[yYmMdDhHsS]");
// add "年 月 日" for Chinese/Japanese date format:2017 年 2 月 7 日
// and "时 分 秒" (Chinese) or "時 分 秒" (Japanese) for hours, minutes and seconds
+ // The first part is possessive: it shares ' ', 'm', 'M' and '/' with the rest, and giving them back
+ // one at a time was quadratic. It never needs to, as the rest can then match without them too.
private static final Pattern date_ptrn3b = Pattern.compile(
- "^[\\[\\]yYmMdDhHsS\\-T/年月日时時分秒,. :\"\\\\]+0* ?[ampAMP/]*$");
+ "^[\\[\\]yYmMdDhHsS\\-T/年月日时時分秒,. :\"\\\\]++0* ?[ampAMP/]*$");
// elapsed time patterns: [h],[m] and [s]
private static final Pattern date_ptrn4 = Pattern.compile("^\\[([hH]+|[mM]+|[sS]+)]");
private static final Pattern date_ptrn4b = Pattern.compile("\\[([hH]+|[mM]+|[sS]+)]");
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 a4f2e91178..950c1f3b21 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
@@ -279,6 +279,60 @@ class TestDataFormatter {
assertEquals("1.5", result);
}
+ @Test
+ void testManyColours() {
+ DataFormatter dfUS = new DataFormatter(Locale.US);
+
+ // each colour used to be removed by searching again from the start of the format, which was quadratic
+ String format = "#".repeat(25_000) + "[Red]".repeat(5_000);
+ String result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> dfUS.formatRawCellContents(1.5, -1, format));
+ assertEquals("2", result);
+
+ // removing a colour can make another one
+ assertEquals("2", dfUS.formatRawCellContents(1.5, -1, "[Re[Blue]d]0"));
+ }
+
+ @Test
+ void testLocaleWithoutEnd() {
+ DataFormatter dfUS = new DataFormatter(Locale.US);
+
+ // a "[$" with no '-' or ']' after it used to be retried from every "[$", which was quadratic
+ String format = "0" + "[$".repeat(25_000);
+ String result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> dfUS.formatRawCellContents(1.5, -1, format));
+ assertEquals("2" + "[$".repeat(25_000), result);
+ }
+
+ @Test
+ void testManyCommasNotAtEnd() {
+ DataFormatter dfUS = new DataFormatter(Locale.US);
+
+ // a long run of commas that is not at the end used to be tried from every comma, which was quadratic
+ String commas = ",".repeat(50_000);
+ String format = "0\"x" + commas + "y\"";
+ String result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> dfUS.formatRawCellContents(1.5, -1, format));
+ assertEquals("2x" + commas + "y", result);
+
+ // scaling commas straight after the digits
+ String scaling = "0" + ",".repeat(50_000) + "x";
+ result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> dfUS.formatRawCellContents(1.5, -1, scaling));
+ assertEquals("1.5", result);
+ }
+
+ @Test
+ void testLongDateLikeFormat() {
+ DataFormatter dfUS = new DataFormatter(Locale.US);
+
+ // '/' is allowed both in the date part and in the AM/PM part, which used to backtrack quadratically
+ String format = "y" + "/".repeat(50_000) + "x";
+ String result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> dfUS.formatRawCellContents(1.5, -1, format));
+ assertEquals("1.5", result);
+ }
+
/**
* Test how we handle negative and zeros.
* Note - some tests are disabled as DecimalFormat
diff --git a/poi/src/test/java/org/apache/poi/ss/usermodel/TestDateUtil.java b/poi/src/test/java/org/apache/poi/ss/usermodel/TestDateUtil.java
index 918aa9b326..0ad39886ab 100644
--- a/poi/src/test/java/org/apache/poi/ss/usermodel/TestDateUtil.java
+++ b/poi/src/test/java/org/apache/poi/ss/usermodel/TestDateUtil.java
@@ -29,11 +29,13 @@ import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.io.IOException;
import java.text.ParseException;
import java.text.SimpleDateFormat;
+import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Calendar;
import java.util.Date;
@@ -154,6 +156,17 @@ class TestDateUtil {
assertEquals(date, DateUtil.getLocalDateTime(dateValue, use1904windowing, roundSeconds));
}
+ @Test
+ void isADateFormatWithLongRun() {
+ // '/' is allowed both in the date part and in the AM/PM part, which used to backtrack quadratically
+ String format = "y" + "/".repeat(50_000) + "x";
+ boolean result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> DateUtil.isADateFormat(-1, format));
+ assertFalse(result);
+ assertTrue(DateUtil.isADateFormat(-1, "y" + "/".repeat(50_000) + "AM/PM"));
+ assertTrue(DateUtil.isADateFormat(-1, "mm/dd/yy m/"));
+ }
+
@Test
void isADateFormat() {
// Cell content 2016-12-8 as an example
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@poi.apache.org
For additional commands, e-mail: commits-help@poi.apache.org