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:06:40 UTC
(poi-xmlbeans) branch trunk updated: fix quadratic regex matching and other regex hot spots (#137)
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-xmlbeans.git
The following commit(s) were added to refs/heads/trunk by this push:
new 745ba906 fix quadratic regex matching and other regex hot spots (#137)
745ba906 is described below
commit 745ba9068d53b7198e950ab0b921be0c9afaf203
Author: PJ Fanning <pj...@users.noreply.github.com>
AuthorDate: Sun Oct 18 11:06:34 2026 +0100
fix quadratic regex matching and other regex hot spots (#137)
- RegularExpression: ClosureContext kept the offsets each closure had
visited in a list and scanned it on every iteration, so matching any
* or + closure (e.g. an xs:pattern of \c+) was O(n^2) in the value
length. Use an open-addressing int hash set instead; memory stays
proportional to the offsets seen, so sparse offsets stay cheap.
- RegularExpression: use ArrayDeque rather than synchronized Stack for
the match op stack.
- RangeToken: binary search ranges above U+00FF instead of a linear scan.
- replace simple String.matches/replaceAll calls with plain string code
in StscState, StscImporter, CodeGenUtil and MavenPlugin.
Co-authored-by: Claude Opus 5.5 <no...@anthropic.com>
---
.../org/apache/xmlbeans/impl/regex/RangeToken.java | 70 +++++++++++++------
.../xmlbeans/impl/regex/RegularExpression.java | 81 +++++++++++++++++-----
.../apache/xmlbeans/impl/schema/StscImporter.java | 2 +-
.../org/apache/xmlbeans/impl/schema/StscState.java | 19 ++++-
.../org/apache/xmlbeans/impl/tool/CodeGenUtil.java | 3 +-
.../org/apache/xmlbeans/impl/tool/MavenPlugin.java | 2 +-
.../java/misc/checkin/RegularExpressionTest.java | 36 +++++++++-
7 files changed, 168 insertions(+), 45 deletions(-)
diff --git a/src/main/java/org/apache/xmlbeans/impl/regex/RangeToken.java b/src/main/java/org/apache/xmlbeans/impl/regex/RangeToken.java
index 405d22d6..c72e97a1 100644
--- a/src/main/java/org/apache/xmlbeans/impl/regex/RangeToken.java
+++ b/src/main/java/org/apache/xmlbeans/impl/regex/RangeToken.java
@@ -15,6 +15,8 @@
package org.apache.xmlbeans.impl.regex;
+import java.util.Arrays;
+
/**
* This class represents a character class such as [a-z] or a period.
*/
@@ -26,6 +28,8 @@ final class RangeToken extends Token implements java.io.Serializable {
RangeToken icaseCache = null;
int[] map = null;
int nonMapIndex;
+ // ranges from nonMapIndex on, merged so that they can be binary searched
+ private transient int[] highRanges = null;
RangeToken(int type) {
super(type);
@@ -491,32 +495,37 @@ final class RangeToken extends Token implements java.io.Serializable {
}
boolean match(int ch) {
- if (this.map == null) {
+ int[] high = this.highRanges;
+ if (this.map == null || high == null) {
this.createMap();
+ high = this.highRanges;
}
- boolean ret;
- if (this.type == RANGE) {
- if (ch < MAPSIZE) {
- return (this.map[ch / 32] & (1 << (ch & 0x1f))) != 0;
- }
- ret = false;
- for (int i = this.nonMapIndex; i < this.ranges.length; i += 2) {
- if (this.ranges[i] <= ch && ch <= this.ranges[i + 1]) {
- return true;
- }
- }
+ boolean in;
+ if (ch < MAPSIZE) {
+ in = (this.map[ch / 32] & (1 << (ch & 0x1f))) != 0;
} else {
- if (ch < MAPSIZE) {
- return (this.map[ch / 32] & (1 << (ch & 0x1f))) == 0;
- }
- ret = true;
- for (int i = this.nonMapIndex; i < this.ranges.length; i += 2) {
- if (this.ranges[i] <= ch && ch <= this.ranges[i + 1]) {
- return false;
- }
+ in = inHighRanges(high, ch);
+ }
+ return (this.type == RANGE) == in;
+ }
+
+ /**
+ * Binary search of the sorted, non-overlapping ranges built by createMap().
+ */
+ private static boolean inHighRanges(int[] high, int ch) {
+ int lo = 0;
+ int hi = high.length / 2 - 1;
+ while (lo <= hi) {
+ int mid = (lo + hi) >>> 1;
+ if (high[mid * 2] > ch) {
+ hi = mid - 1;
+ } else if (high[mid * 2 + 1] < ch) {
+ lo = mid + 1;
+ } else {
+ return true;
}
}
- return ret;
+ return false;
}
private static final int MAPSIZE = 256;
@@ -550,10 +559,29 @@ final class RangeToken extends Token implements java.io.Serializable {
}
}
this.nonMapIndex = localnonMapIndex; // +
+ this.highRanges = mergeRanges(this.ranges, localnonMapIndex);
this.map = localmap; // +
//for (int i = 0; i < asize; i ++) System.err.println("Map: "+Integer.toString(this.map[i], 16));
}
+ /**
+ * Copies the sorted ranges from <var>from</var> on, merging any that overlap
+ * or touch, as uncompacted ranges are sorted but may still overlap.
+ */
+ private static int[] mergeRanges(int[] ranges, int from) {
+ int[] merged = new int[ranges.length - from];
+ int n = 0;
+ for (int i = from; i < ranges.length; i += 2) {
+ if (n > 0 && ranges[i] <= merged[n - 1] + 1) {
+ merged[n - 1] = Math.max(merged[n - 1], ranges[i + 1]);
+ } else {
+ merged[n++] = ranges[i];
+ merged[n++] = ranges[i + 1];
+ }
+ }
+ return n == merged.length ? merged : Arrays.copyOf(merged, n);
+ }
+
public String toString(int options) {
String ret;
if (this.type == RANGE) {
diff --git a/src/main/java/org/apache/xmlbeans/impl/regex/RegularExpression.java b/src/main/java/org/apache/xmlbeans/impl/regex/RegularExpression.java
index 407e571c..317d9043 100644
--- a/src/main/java/org/apache/xmlbeans/impl/regex/RegularExpression.java
+++ b/src/main/java/org/apache/xmlbeans/impl/regex/RegularExpression.java
@@ -18,8 +18,10 @@
package org.apache.xmlbeans.impl.regex;
import java.text.CharacterIterator;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Deque;
import java.util.Locale;
-import java.util.Stack;
/**
* A regular expression matching engine using Non-deterministic Finite Automaton (NFA).
@@ -1023,7 +1025,7 @@ public class RegularExpression implements java.io.Serializable {
*/
private int match(Context con, Op op, int offset, int dx, int opts) {
final ExpressionTarget target = con.target;
- final Stack<Op> opStack = new Stack<>();
+ final Deque<Op> opStack = new ArrayDeque<>();
final IntStack dataStack = new IntStack();
final boolean isSetIgnoreCase = isSet(opts, IGNORE_CASE);
int retValue = -1;
@@ -1957,37 +1959,82 @@ public class RegularExpression implements java.io.Serializable {
static final class ClosureContext {
- int[] offsets = new int[4];
- int currentIndex = 0;
+ // An open-addressing hash set of the offsets seen. A plain list made
+ // contains() a linear scan, so matching a closure such as \c+ was
+ // quadratic. A bit set would be sized by the largest offset rather than
+ // by the number of offsets seen, which is bad for sparse offsets.
+ private static final int EMPTY = Integer.MIN_VALUE;
+ private static final int INITIAL_CAPACITY = 16;
+
+ private int[] offsets = newTable(INITIAL_CAPACITY);
+ private int shift = 32 - Integer.numberOfTrailingZeros(INITIAL_CAPACITY);
+ private int size = 0;
boolean contains(int offset) {
- for (int i=0; i<currentIndex;++i) {
- if (offsets[i] == offset) {
+ final int mask = offsets.length - 1;
+ for (int i = slot(offset); ; i = (i + 1) & mask) {
+ final int o = offsets[i];
+ if (o == offset) {
return true;
}
+ if (o == EMPTY) {
+ return false;
+ }
}
- return false;
}
void reset() {
- currentIndex = 0;
+ if (size == 0) {
+ return;
+ }
+ if (offsets.length > INITIAL_CAPACITY) {
+ // don't hold on to the table grown by a long match
+ offsets = newTable(INITIAL_CAPACITY);
+ shift = 32 - Integer.numberOfTrailingZeros(INITIAL_CAPACITY);
+ } else {
+ Arrays.fill(offsets, EMPTY);
+ }
+ size = 0;
}
void addOffset(int offset) {
// We do not check for duplicates, caller is responsible for that
- if (currentIndex == offsets.length) {
- offsets = expandOffsets();
+ if ((size + 1) * 2 > offsets.length) {
+ grow();
}
- offsets[currentIndex++] = offset;
+ insert(offsets, offset);
+ size++;
}
- private int[] expandOffsets() {
- final int len = offsets.length;
- final int newLen = len << 1;
- int[] newOffsets = new int[newLen];
+ private int slot(int offset) {
+ // Fibonacci hashing, as offsets are often consecutive or strided
+ return (offset * 0x9E3779B9) >>> shift;
+ }
+
+ private void insert(int[] table, int offset) {
+ final int mask = table.length - 1;
+ int i = slot(offset);
+ while (table[i] != EMPTY) {
+ i = (i + 1) & mask;
+ }
+ table[i] = offset;
+ }
+
+ private void grow() {
+ final int[] old = offsets;
+ offsets = newTable(old.length << 1);
+ shift--;
+ for (int o : old) {
+ if (o != EMPTY) {
+ insert(offsets, o);
+ }
+ }
+ }
- System.arraycopy(offsets, 0, newOffsets, 0, currentIndex);
- return newOffsets;
+ private static int[] newTable(int capacity) {
+ final int[] table = new int[capacity];
+ Arrays.fill(table, EMPTY);
+ return table;
}
}
diff --git a/src/main/java/org/apache/xmlbeans/impl/schema/StscImporter.java b/src/main/java/org/apache/xmlbeans/impl/schema/StscImporter.java
index f0f6de7c..95532835 100644
--- a/src/main/java/org/apache/xmlbeans/impl/schema/StscImporter.java
+++ b/src/main/java/org/apache/xmlbeans/impl/schema/StscImporter.java
@@ -203,7 +203,7 @@ public class StscImporter {
// looks like a URL?
int colon = path.indexOf(':');
- if (colon > 1 && path.substring(0, colon).matches("^\\w+$")) {
+ if (colon > 1 && StscState.isWordPrefix(path, colon)) {
return path;
}
diff --git a/src/main/java/org/apache/xmlbeans/impl/schema/StscState.java b/src/main/java/org/apache/xmlbeans/impl/schema/StscState.java
index c4f22f09..1d334641 100644
--- a/src/main/java/org/apache/xmlbeans/impl/schema/StscState.java
+++ b/src/main/java/org/apache/xmlbeans/impl/schema/StscState.java
@@ -1350,6 +1350,23 @@ public class StscState {
return relativize(uri, true);
}
+ /**
+ * @return true if the first <var>end</var> chars of <var>s</var> are all
+ * regex word chars ({@code [a-zA-Z_0-9]}), i.e. {@code s.substring(0, end).matches("\\w+")}
+ */
+ static boolean isWordPrefix(String s, int end) {
+ if (end <= 0) {
+ return false;
+ }
+ for (int i = 0; i < end; i++) {
+ char c = s.charAt(i);
+ if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_')) {
+ return false;
+ }
+ }
+ return true;
+ }
+
private String relativize(String uri, boolean forSavedFilename) {
if (uri == null) {
return null;
@@ -1361,7 +1378,7 @@ public class StscState {
} else {
// looks like a URL?
int colon = uri.indexOf(':');
- if (colon <= 1 || !uri.substring(0, colon).matches("^\\w+$")) {
+ if (colon <= 1 || !isWordPrefix(uri, colon)) {
uri = PROJECT_URL_PREFIX + "/" + uri.replace('\\', '/');
}
}
diff --git a/src/main/java/org/apache/xmlbeans/impl/tool/CodeGenUtil.java b/src/main/java/org/apache/xmlbeans/impl/tool/CodeGenUtil.java
index 80c2264b..da653b4d 100644
--- a/src/main/java/org/apache/xmlbeans/impl/tool/CodeGenUtil.java
+++ b/src/main/java/org/apache/xmlbeans/impl/tool/CodeGenUtil.java
@@ -75,8 +75,7 @@ public class CodeGenUtil {
}
// bizarre. javac expects backslash escaping if we quote the classpath
- // bizarre also. replaceAll expects replacement backslashes to be double escaped.
- return "\"" + filename.replaceAll("\\\\", "\\\\\\\\") + "\"";
+ return "\"" + filename.replace("\\", "\\\\") + "\"";
}
diff --git a/src/main/java/org/apache/xmlbeans/impl/tool/MavenPlugin.java b/src/main/java/org/apache/xmlbeans/impl/tool/MavenPlugin.java
index 8a7e2f9a..7ddf8b43 100644
--- a/src/main/java/org/apache/xmlbeans/impl/tool/MavenPlugin.java
+++ b/src/main/java/org/apache/xmlbeans/impl/tool/MavenPlugin.java
@@ -231,7 +231,7 @@ public class MavenPlugin extends AbstractMojo {
final Collection<File> schemaFiles = FileUtil.find(base, pat, recurseSourceSubdirs);
for (File sf : schemaFiles) {
String name = sf.getName();
- switch (name.replaceAll(".*\\.", "")) {
+ switch (name.substring(name.lastIndexOf('.') + 1)) {
case "wsdl":
wsdls.add(sf);
break;
diff --git a/src/test/java/misc/checkin/RegularExpressionTest.java b/src/test/java/misc/checkin/RegularExpressionTest.java
index 15424d70..4aad8cd2 100644
--- a/src/test/java/misc/checkin/RegularExpressionTest.java
+++ b/src/test/java/misc/checkin/RegularExpressionTest.java
@@ -19,10 +19,13 @@ import org.apache.xmlbeans.impl.regex.ParseException;
import org.apache.xmlbeans.impl.regex.RegularExpression;
import org.junit.jupiter.api.Test;
+import java.time.Duration;
import java.util.Random;
+import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
-import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class RegularExpressionTest {
@@ -78,7 +81,36 @@ public class RegularExpressionTest {
}
- private static final String AB = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+ @Test
+ void testLongClosureIsLinear() {
+ // each closure iteration records its offset to stop zero-width repeats; those
+ // offsets used to be kept in a list that was scanned on every iteration, which
+ // made this match quadratic (a 50,000 char name took seconds, 1M chars minutes)
+ String s = "a".repeat(1_000_000);
+ RegularExpression regex = new RegularExpression("\\c+", "X");
+ assertTimeoutPreemptively(Duration.ofSeconds(30), () -> assertTrue(regex.matches(s)));
+ }
+
+ @Test
+ void testCharClassAboveLatin1() {
+ // chars >= 256 are looked up by binary search of the class ranges rather
+ // than the latin-1 bitmap, so check every code point against java.util.regex
+ String ranges = "a-zà-ŐЀ-ӿぁ-ゖ一-鿿😀-🙏";
+ RegularExpression pos = new RegularExpression("[" + ranges + "]", "X");
+ RegularExpression neg = new RegularExpression("[^" + ranges + "]", "X");
+ java.util.regex.Pattern expected = java.util.regex.Pattern.compile("[" + ranges + "]");
+ for (int cp = 0; cp <= Character.MAX_CODE_POINT; cp++) {
+ if (Character.getType(cp) == Character.SURROGATE) {
+ continue;
+ }
+ String s = new String(Character.toChars(cp));
+ boolean in = expected.matcher(s).matches();
+ assertEquals(in, pos.matches(s), () -> "positive class, code point " + Integer.toHexString(s.codePointAt(0)));
+ assertEquals(!in, neg.matches(s), () -> "negated class, code point " + Integer.toHexString(s.codePointAt(0)));
+ }
+ }
+
+ private static final String AB ="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
private static final Random rnd = new Random();
private String randomString(int len) {
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@poi.apache.org
For additional commands, e-mail: commits-help@poi.apache.org