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 9d33c42e5e Avoid quadratic regex backtracking in Context,
AbstractWordConverter and MAPIMessage (#1442)
9d33c42e5e is described below
commit 9d33c42e5e24b2cfa7698d43e4bf21ab239487c8
Author: PJ Fanning <[email protected]>
AuthorDate: Sun Oct 18 11:20:12 2026 +0100
Avoid quadratic regex backtracking in Context, AbstractWordConverter and
MAPIMessage (#1442)
- Context.DOUBLE_PATTERN: make the digit runs possessive.
- AbstractWordConverter: use atomic groups in the HYPERLINK and PAGEREF
field patterns so a failing ".*$" tail is not retried for every
shorter match.
- MAPIMessage.guess7BitEncoding: replace the content-type charset regex
with an equivalent hand-written matcher.
All changes keep the exact accept/reject results and captured groups.
Co-authored-by: Claude Opus 5.5 <[email protected]>
---
.../main/java/org/apache/poi/hsmf/MAPIMessage.java | 75 +++++++++++++++++++---
.../poi/hwpf/converter/AbstractWordConverter.java | 23 ++++---
.../java/org/apache/poi/hsmf/Test7BitCodepage.java | 16 +++++
.../hwpf/converter/TestWordToHtmlConverter.java | 42 ++++++++++++
.../java/org/apache/poi/sl/draw/geom/Context.java | 10 +--
.../apache/poi/sl/draw/geom/TestFormulaParser.java | 18 ++++++
6 files changed, 164 insertions(+), 20 deletions(-)
diff --git a/poi-scratchpad/src/main/java/org/apache/poi/hsmf/MAPIMessage.java
b/poi-scratchpad/src/main/java/org/apache/poi/hsmf/MAPIMessage.java
index 9b3ea18208..6fec8c629c 100644
--- a/poi-scratchpad/src/main/java/org/apache/poi/hsmf/MAPIMessage.java
+++ b/poi-scratchpad/src/main/java/org/apache/poi/hsmf/MAPIMessage.java
@@ -25,8 +25,6 @@ import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.List;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
import org.apache.logging.log4j.Logger;
import org.apache.poi.logging.PoiLogManager;
@@ -87,9 +85,6 @@ public class MAPIMessage extends POIReadOnlyDocument {
*/
private static final Logger LOG =
PoiLogManager.getLogger(MAPIMessage.class);
- private static final Pattern GUESS_7_BIT_ENCODING_PATTERN =
Pattern.compile("content-type:.*?charset=[\"']?([^;'\"]+)[\"']?",
Pattern.CASE_INSENSITIVE);
-
-
private Chunks mainChunks;
private NameIdChunks nameIdChunks;
private RecipientChunks[] recipientChunks;
@@ -500,9 +495,9 @@ public class MAPIMessage extends POIReadOnlyDocument {
if (headers != null) {
for (String header : headers) {
if
(header.toLowerCase(LocaleUtil.getUserLocale()).startsWith("content-type")) {
- Matcher m =
GUESS_7_BIT_ENCODING_PATTERN.matcher(header);
- if (m.matches()) {
- generalcodepage = m.group(1);
+ String charset = getCharsetFromContentType(header);
+ if (charset != null) {
+ generalcodepage = charset;
}
}
}
@@ -748,6 +743,70 @@ public class MAPIMessage extends POIReadOnlyDocument {
this.returnNullOnMissingChunk = returnNullOnMissingChunk;
}
+ /**
+ * Extracts the charset from a content type header, matching it the same
way as
+ * the regular expression {@code
content-type:.*?charset=["']?([^;'"]+)["']?}
+ * (ASCII case-insensitive, whole header), which this replaces because it
+ * backtracks quadratically on headers with many {@code charset=} parts.
+ *
+ * @return the charset (group 1 of the expression), or {@code null} if it
doesn't match
+ */
+ static String getCharsetFromContentType(String header) {
+ if (!startsWithIgnoreAsciiCase(header, 0, "content-type:")) {
+ return null;
+ }
+ final int len = header.length();
+ // the charset value runs to the end, less an optional closing quote,
+ // and must not contain ';' or a quote
+ final int end = len > 0 && isQuote(header.charAt(len - 1)) ? len - 1 :
len;
+ int lastInvalid = -1;
+ for (int i = end - 1; i >= 0; i--) {
+ final char c = header.charAt(i);
+ if (c == ';' || isQuote(c)) {
+ lastInvalid = i;
+ break;
+ }
+ }
+ // ".*?" picks the first "charset=" on the first line whose value is
valid
+ for (int i = 13; i < len && !isLineTerminator(header.charAt(i)); i++) {
+ if (startsWithIgnoreAsciiCase(header, i, "charset=")) {
+ int start = i + 8;
+ if (start < len && isQuote(header.charAt(start))) {
+ start++;
+ }
+ if (start < end && start > lastInvalid) {
+ return header.substring(start, end);
+ }
+ }
+ }
+ return null;
+ }
+
+ private static boolean startsWithIgnoreAsciiCase(String str, int offset,
String lowerCasePrefix) {
+ if (offset + lowerCasePrefix.length() > str.length()) {
+ return false;
+ }
+ for (int i = 0; i < lowerCasePrefix.length(); i++) {
+ char c = str.charAt(offset + i);
+ if (c >= 'A' && c <= 'Z') {
+ c += 'a' - 'A';
+ }
+ if (c != lowerCasePrefix.charAt(i)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static boolean isQuote(char c) {
+ return c == '"' || c == '\'';
+ }
+
+ /** the characters {@code .} does not match in a regular expression */
+ private static boolean isLineTerminator(char c) {
+ return c == '\n' || c == '\r' || c == '\u0085' || c == '\u2028' || c
== '\u2029';
+ }
+
private String toSemicolonList(String[] l) {
StringBuilder list = new StringBuilder();
diff --git
a/poi-scratchpad/src/main/java/org/apache/poi/hwpf/converter/AbstractWordConverter.java
b/poi-scratchpad/src/main/java/org/apache/poi/hwpf/converter/AbstractWordConverter.java
index dbb81b8783..0ca4bddf34 100644
---
a/poi-scratchpad/src/main/java/org/apache/poi/hwpf/converter/AbstractWordConverter.java
+++
b/poi-scratchpad/src/main/java/org/apache/poi/hwpf/converter/AbstractWordConverter.java
@@ -121,14 +121,21 @@ public abstract class AbstractWordConverter {
private static final Logger LOG =
PoiLogManager.getLogger(AbstractWordConverter.class);
- private static final Pattern PATTERN_HYPERLINK_EXTERNAL = Pattern
- .compile("^[ \\t\\r\\n]*HYPERLINK \"(.*)\".*$");
-
- private static final Pattern PATTERN_HYPERLINK_LOCAL = Pattern
- .compile("^[ \\t\\r\\n]*HYPERLINK \\\\l \"(.*)\"[ ](.*)$");
-
- private static final Pattern PATTERN_PAGEREF = Pattern
- .compile("^[ \\t\\r\\n]*PAGEREF ([^ ]*)[ \\t\\r\\n]*\\\\h.*$");
+ // The atomic groups (?>...) keep only the longest match of the leading
part.
+ // If the trailing ".*$" fails after it, it is because of a line break that
+ // a shorter match would run into too, so retrying them (quadratic on long
+ // formulas) cannot find a match.
+ // The patterns are package-private for testing.
+ static final Pattern PATTERN_HYPERLINK_EXTERNAL = Pattern
+ .compile("^[ \\t\\r\\n]*HYPERLINK \"(?>(.*)\").*$");
+
+ static final Pattern PATTERN_HYPERLINK_LOCAL = Pattern
+ .compile("^[ \\t\\r\\n]*HYPERLINK \\\\l \"(?>(.*)\"[ ])(.*)$");
+
+ // within the atomic group, whitespace directly after ([^ ]*) must start
with
+ // a space: tabs and line breaks there are matched by ([^ ]*) itself first
+ static final Pattern PATTERN_PAGEREF = Pattern
+ .compile("^[ \\t\\r\\n]*PAGEREF (?>([^ ]*)(?: [
\\t\\r\\n]*+)?\\\\h).*$");
private static final byte SPECCHAR_AUTONUMBERED_FOOTNOTE_REFERENCE = 2;
private static final byte SPECCHAR_DRAWN_OBJECT = 8;
diff --git
a/poi-scratchpad/src/test/java/org/apache/poi/hsmf/Test7BitCodepage.java
b/poi-scratchpad/src/test/java/org/apache/poi/hsmf/Test7BitCodepage.java
index deecb942ab..b996f737d4 100644
--- a/poi-scratchpad/src/test/java/org/apache/poi/hsmf/Test7BitCodepage.java
+++ b/poi-scratchpad/src/test/java/org/apache/poi/hsmf/Test7BitCodepage.java
@@ -19,8 +19,10 @@ package org.apache.poi.hsmf;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import java.io.IOException;
+import java.time.Duration;
import org.apache.poi.POIDataSamples;
import org.junit.jupiter.api.BeforeEach;
@@ -86,4 +88,18 @@ public final class Test7BitCodepage {
assertNull(htmlbodybinary_utf_8.getTextBody());
assertEquals("<!DOCTYPE html><html><meta
charset=\\\"utf-8\\\"><body>HTML öäü</body></html>",
htmlbodybinary_utf_8.getHtmlBody());
}
+
+ @Test
+ void testCharsetFromContentType() {
+ assertEquals("utf-8",
MAPIMessage.getCharsetFromContentType("Content-Type: text/plain;
charset=\"utf-8\""));
+ assertEquals("windows-1251",
MAPIMessage.getCharsetFromContentType("content-type: text/plain;
CHARSET=windows-1251"));
+ assertEquals("koi8-r",
MAPIMessage.getCharsetFromContentType("Content-Type: text/plain; charset=x;
charset='koi8-r"));
+ assertNull(MAPIMessage.getCharsetFromContentType("Content-Type:
text/plain; charset=utf-8; format=flowed"));
+ assertNull(MAPIMessage.getCharsetFromContentType("Content-Type:
text/plain;\n charset=utf-8"));
+ assertNull(MAPIMessage.getCharsetFromContentType("Content-Type:
text/plain"));
+
+ // this used to take quadratic time, as every "charset=" was tried in
turn
+ String header = "content-type:" + "charset=a".repeat(200_000) + ";";
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () ->
assertNull(MAPIMessage.getCharsetFromContentType(header)));
+ }
}
diff --git
a/poi-scratchpad/src/test/java/org/apache/poi/hwpf/converter/TestWordToHtmlConverter.java
b/poi-scratchpad/src/test/java/org/apache/poi/hwpf/converter/TestWordToHtmlConverter.java
index 6128e842ae..2840ea17f6 100644
---
a/poi-scratchpad/src/test/java/org/apache/poi/hwpf/converter/TestWordToHtmlConverter.java
+++
b/poi-scratchpad/src/test/java/org/apache/poi/hwpf/converter/TestWordToHtmlConverter.java
@@ -18,9 +18,15 @@ package org.apache.poi.hwpf.converter;
import static org.apache.poi.POITestCase.assertContains;
import static org.apache.poi.POITestCase.assertNotContains;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+import static org.junit.jupiter.api.Assertions.assertTrue;
import java.io.StringWriter;
+import java.time.Duration;
+import java.util.regex.Matcher;
import javax.xml.transform.OutputKeys;
import javax.xml.transform.Transformer;
@@ -31,6 +37,7 @@ import org.apache.poi.POIDataSamples;
import org.apache.poi.POITestCase;
import org.apache.poi.hwpf.HWPFDocument;
import org.apache.poi.util.XMLHelper;
+import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;
import org.w3c.dom.Document;
@@ -117,6 +124,41 @@ public class TestWordToHtmlConverter {
}
}
+ @Test
+ void testFieldPatterns() {
+ Matcher m = AbstractWordConverter.PATTERN_HYPERLINK_EXTERNAL.matcher("
HYPERLINK \"http://testuri.org/\" ");
+ assertTrue(m.matches());
+ assertEquals("http://testuri.org/", m.group(1));
+
+ m = AbstractWordConverter.PATTERN_HYPERLINK_LOCAL.matcher("HYPERLINK
\\l \"_Toc1\" text\"");
+ assertTrue(m.matches());
+ assertEquals("_Toc1", m.group(1));
+ assertEquals("text\"", m.group(2));
+
+ m = AbstractWordConverter.PATTERN_PAGEREF.matcher("\r\n PAGEREF _Toc2
\t\\h \\* MERGEFORMAT \r");
+ assertTrue(m.find());
+ assertEquals("_Toc2", m.group(1));
+
+ m = AbstractWordConverter.PATTERN_PAGEREF.matcher("PAGEREF
_Toc2\t\\h");
+ assertTrue(m.find());
+ assertEquals("_Toc2\t", m.group(1));
+ }
+
+ @Test
+ void testFieldPatternsBacktracking() {
+ // these used to take minutes, as every shorter match was retried
before failing
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+
assertFalse(AbstractWordConverter.PATTERN_HYPERLINK_EXTERNAL.matcher(
+ "HYPERLINK \"" + "\"".repeat(100_000) + "\"\nx").matches());
+ assertFalse(AbstractWordConverter.PATTERN_HYPERLINK_LOCAL.matcher(
+ "HYPERLINK \\l \"" + "\" ".repeat(50_000) + "\nx").matches());
+ assertFalse(AbstractWordConverter.PATTERN_PAGEREF.matcher(
+ "PAGEREF " + "\t".repeat(100_000) + "x").find());
+ assertFalse(AbstractWordConverter.PATTERN_PAGEREF.matcher(
+ "PAGEREF " + "\\h".repeat(50_000) + "\n\n").find());
+ });
+ }
+
private static String getHtmlText(final String sampleFileName, boolean
emulatePictureStorage) throws Exception {
Document newDocument = XMLHelper.newDocumentBuilder().newDocument();
WordToHtmlConverter wordToHtmlConverter = new
WordToHtmlConverter(newDocument);
diff --git a/poi/src/main/java/org/apache/poi/sl/draw/geom/Context.java
b/poi/src/main/java/org/apache/poi/sl/draw/geom/Context.java
index cb66206c94..ae167c6be1 100644
--- a/poi/src/main/java/org/apache/poi/sl/draw/geom/Context.java
+++ b/poi/src/main/java/org/apache/poi/sl/draw/geom/Context.java
@@ -25,11 +25,13 @@ import java.util.Map;
import java.util.regex.Pattern;
public class Context {
+ // the digit runs are possessive: giving digits back never turns a failed
match into a success,
+ // and backtracking into them is quadratic on long non-numeric strings
private static final Pattern DOUBLE_PATTERN = Pattern.compile(
-
"[\\x00-\\x20]*[+-]?(NaN|Infinity|((((\\p{Digit}+)(\\.)?((\\p{Digit}+)?)" +
-
"([eE][+-]?(\\p{Digit}+))?)|(\\.(\\p{Digit}+)([eE][+-]?(\\p{Digit}+))?)|" +
-
"(((0[xX](\\p{XDigit}+)(\\.)?)|(0[xX](\\p{XDigit}+)?(\\.)(\\p{XDigit}+)))" +
- "[pP][+-]?(\\p{Digit}+)))[fFdD]?))[\\x00-\\x20]*");
+
"[\\x00-\\x20]*[+-]?(NaN|Infinity|((((\\p{Digit}++)(\\.)?((\\p{Digit}++)?)" +
+
"([eE][+-]?(\\p{Digit}++))?)|(\\.(\\p{Digit}++)([eE][+-]?(\\p{Digit}++))?)|" +
+
"(((0[xX](\\p{XDigit}++)(\\.)?)|(0[xX](\\p{XDigit}++)?(\\.)(\\p{XDigit}++)))" +
+ "[pP][+-]?(\\p{Digit}++)))[fFdD]?))[\\x00-\\x20]*");
private final Map<String, Double> _ctx = new HashMap<>();
private final IAdjustableShape _props;
diff --git
a/poi/src/test/java/org/apache/poi/sl/draw/geom/TestFormulaParser.java
b/poi/src/test/java/org/apache/poi/sl/draw/geom/TestFormulaParser.java
index 9175a2b8f4..df1c6386f7 100644
--- a/poi/src/test/java/org/apache/poi/sl/draw/geom/TestFormulaParser.java
+++ b/poi/src/test/java/org/apache/poi/sl/draw/geom/TestFormulaParser.java
@@ -19,6 +19,10 @@
package org.apache.poi.sl.draw.geom;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+
+import java.time.Duration;
import org.junit.jupiter.api.Test;
@@ -52,6 +56,20 @@ class TestFormulaParser {
assertEquals(2.0, ctx.getValue("a5"), 0.0);
}
+ @Test
+ void testNumericValues() {
+ Context ctx = new Context(new CustomGeometry(), null, null);
+ assertEquals(150.0, ctx.getValue("1.5e2"), 0.0);
+ assertEquals(-0.25, ctx.getValue(" -.25 "), 0.0);
+ assertEquals(8.0, ctx.getValue("0x1p3"), 0.0);
+ assertEquals(12.0, ctx.getValue("12d"), 0.0);
+
+ // a long name made of digits used to take minutes to be rejected as a
number
+ String key = "1".repeat(50_000) + "x";
+ assertTimeoutPreemptively(Duration.ofSeconds(10),
+ () -> assertThrows(IllegalArgumentException.class, () ->
ctx.getValue(key)));
+ }
+
private static Guide newGuide(String name, String fmla) {
Guide gd = new Guide();
gd.setName(name);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]