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]

Reply via email to