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 815f53b912 PackagePartCollection: avoid quadratic M1.11 check on deep
names (#1525)
815f53b912 is described below
commit 815f53b9124b92874fa2f71b73ca469fb96d83b0
Author: Nayyar <[email protected]>
AuthorDate: Wed Nov 4 16:36:01 2026 +0530
PackagePartCollection: avoid quadratic M1.11 check on deep names (#1525)
* PackagePartCollection: avoid quadratic M1.11 check on deep names
put() rebuilt every slash-delimited prefix of a part name as a new
string and looked it up in the registered-name set, so a name with k
segments cost O(k * length). OPCPackage.open runs this for every zip
entry, and an entry name of up to 65,535 bytes such as a/a/.../a/1.xml
makes a 1.2 MB package take about 17 s to load.
A prefix can only be in the set if a registered name has the same
length, so keep a count of the registered name lengths and only build
the prefixes of those lengths.
* PackagePartCollection: check M1.11 with a tree of the name segments
Filtering the prefixes by the lengths of the registered names still lets a
package with names of just those lengths make the check quadratic. Keep the
registered names as a tree of their segments instead (runs of segments
without a branch in one node), so the check costs time linear in the name
and memory linear in the registered names. The tree is transient and rebuilt
from the parts after deserialization, and it compares names ignoring case
like PackagePartName does, which also makes remove() find a part registered
with a different case. The test checks the work done on put() directly
instead of timing the opening of a package.
* PackagePartCollection: fix compare cost and lookup/tree drift
PackagePartName.compare parsed digit runs as BigInteger, which is
quadratic in their length, so a package of names with long digit runs was
still slow to open. Compare the digits directly, with the same result.
PackagePartName.compare sees some differently spelled names as equal
(/a01b1.xml and /a1b01.xml), which the name tree didn't: remove and put now
drop the name of the stored part. Normalize each name once in put.
PackagePartCollection can't be serialized (its comparator and PackagePart
aren't serializable), so build the tree eagerly rather than rebuild it for
instances that can't exist. Replace the test-only character counter with a
test which opens a real package.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
---------
Co-authored-by: PJ Fanning <[email protected]>
Co-authored-by: Claude Opus 5.5 <[email protected]>
---
.../poi/openxml4j/opc/PackagePartCollection.java | 204 ++++++++++++++++++---
.../apache/poi/openxml4j/opc/PackagePartName.java | 31 +++-
.../openxml4j/opc/TestPackagePartCollection.java | 126 +++++++++++++
.../poi/openxml4j/opc/TestPackagePartName.java | 29 +++
4 files changed, 363 insertions(+), 27 deletions(-)
diff --git
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java
index 96a8ad13e6..8425290a8b 100644
---
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java
+++
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java
@@ -18,10 +18,13 @@
package org.apache.poi.openxml4j.opc;
import java.io.Serializable;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
-import java.util.Set;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
import java.util.TreeMap;
import java.util.function.ToIntFunction;
import java.util.regex.Matcher;
@@ -38,15 +41,15 @@ public final class PackagePartCollection implements
Serializable {
private static final long serialVersionUID = 2515031135957635517L;
- /**
- * HashSet use to store this collection part names as string for rule
- * M1.11 optimized checking.
- */
- private final Set<String> registerPartNameStr = new HashSet<>();
-
private final TreeMap<String, PackagePart> packagePartLookup =
new TreeMap<>(PackagePartName::compare);
+ /**
+ * The registered part names as a tree of their segments, for checking rule
+ * M1.11.
+ */
+ private final transient PartNameTree registeredNames = new PartNameTree();
+
/**
* Check rule [M1.11]: a package implementer shall neither create nor
@@ -63,32 +66,189 @@ public final class PackagePartCollection implements
Serializable {
*/
public PackagePart put(final PackagePartName partName, final PackagePart
part) {
final String ppName = partName.getName();
- final StringBuilder concatSeg = new StringBuilder();
- // split at slash, but keep leading slash
- final String delim =
"(?=["+PackagingURIHelper.FORWARD_SLASH_STRING+"])";
- for (String seg : ppName.split(delim)) {
- concatSeg.append(seg);
- if (registerPartNameStr.contains(concatSeg.toString())) {
- throw new InvalidOperationException(
- "You can't add a part with a part name derived from
another part ! [M1.11]");
- }
+ final String normalized = PartNameTree.normalize(ppName);
+ if (registeredNames.containsPrefixOf(normalized)) {
+ throw new InvalidOperationException(
+ "You can't add a part with a part name derived from another
part ! [M1.11]");
}
- registerPartNameStr.add(ppName);
- return packagePartLookup.put(ppName, part);
+ // the lookup can see this name as equal to one spelled differently,
e.g. /a01.xml and /a1.xml
+ final PackagePart previous = packagePartLookup.put(ppName, part);
+ if (previous != null) {
+
registeredNames.remove(PartNameTree.normalize(previous.getPartName().getName()));
+ }
+ registeredNames.add(normalized);
+ return previous;
}
public PackagePart remove(PackagePartName key) {
if (key == null) {
return null;
}
- final String ppName = key.getName();
- PackagePart pp = packagePartLookup.remove(ppName);
+ PackagePart pp = packagePartLookup.remove(key.getName());
if (pp != null) {
- this.registerPartNameStr.remove(ppName);
+ // not the key's name: the lookup can see differently spelled
names as equal
+
registeredNames.remove(PartNameTree.normalize(pp.getPartName().getName()));
}
return pp;
}
+ /**
+ * The registered part names, split at their slashes into a tree of
segments,
+ * so that checking whether a registered name is a prefix of a part name
(at a
+ * segment boundary) takes time linear in the length of that name, whatever
+ * the registered names are. Segments without a branch or a name end in
+ * between are kept in one node, so the tree takes memory linear in the
total
+ * length of the registered names. Names are compared ignoring case, like
+ * {@link PackagePartName}, so all the names passed in have to be {@link
#normalize normalized}.
+ */
+ private static final class PartNameTree {
+ private static final class Node {
+ /** the segments of this node (after those of its parents),
separated by slashes */
+ private String label;
+ /** whether a registered name ends with this node */
+ private boolean isName;
+ /** the children by their first segment */
+ private final Map<String, Node> children = new HashMap<>();
+
+ Node(String label, boolean isName) {
+ this.label = label;
+ this.isName = isName;
+ }
+ }
+
+ private final Node root = new Node("", false);
+
+ /**
+ * @return whether a registered name equals the given name or is a
prefix
+ * of it ending at a slash
+ */
+ boolean containsPrefixOf(String n) {
+ Node node = root;
+ int pos = 0;
+ while (true) {
+ final String segment = segmentAt(n, pos);
+ final Node child = node.children.get(segment);
+ if (child == null) {
+ return false;
+ }
+ final String label = child.label;
+ final int end = pos + label.length();
+ if (end > n.length()) {
+ return false;
+ }
+ if (!n.startsWith(label, pos) || !isSegmentEnd(n, end)) {
+ return false;
+ }
+ if (child.isName) {
+ return true;
+ }
+ if (end == n.length()) {
+ return false;
+ }
+ node = child;
+ pos = end + 1;
+ }
+ }
+
+ void add(String n) {
+ Node node = root;
+ int pos = 0;
+ while (true) {
+ final String segment = segmentAt(n, pos);
+ Node child = node.children.get(segment);
+ if (child == null) {
+ node.children.put(segment, new Node(n.substring(pos),
true));
+ return;
+ }
+ final int common = commonSegments(n, pos, child.label);
+ if (common < child.label.length()) {
+ // the name leaves the segments of the child half-way:
split it there
+ final Node split = new Node(child.label.substring(0,
common), false);
+ child.label = child.label.substring(common + 1);
+ split.children.put(segmentAt(child.label, 0), child);
+ node.children.put(segment, split);
+ child = split;
+ }
+ pos += common;
+ if (pos == n.length()) {
+ child.isName = true;
+ return;
+ }
+ node = child;
+ pos++;
+ }
+ }
+
+ void remove(String n) {
+ final List<Node> path = new ArrayList<>();
+ final List<String> keys = new ArrayList<>();
+ Node node = root;
+ int pos = 0;
+ while (true) {
+ final String segment = segmentAt(n, pos);
+ final Node child = node.children.get(segment);
+ if (child == null) {
+ return;
+ }
+ final int end = pos + child.label.length();
+ if (!n.startsWith(child.label, pos) || !isSegmentEnd(n, end)) {
+ return;
+ }
+ path.add(node);
+ keys.add(segment);
+ node = child;
+ if (end == n.length()) {
+ break;
+ }
+ pos = end + 1;
+ }
+ node.isName = false;
+ // drop the nodes which neither end a name nor lead to one anymore
+ for (int i = path.size() - 1; i >= 0 && !node.isName &&
node.children.isEmpty(); i--) {
+ path.get(i).children.remove(keys.get(i));
+ node = path.get(i);
+ }
+ }
+
+ /** @return the name in lower case and without its leading slash */
+ static String normalize(String name) {
+ final String n = name.toLowerCase(Locale.ROOT);
+ return n.startsWith(PackagingURIHelper.FORWARD_SLASH_STRING) ?
n.substring(1) : n;
+ }
+
+ private static String segmentAt(String n, int pos) {
+ final int end = n.indexOf(PackagingURIHelper.FORWARD_SLASH_CHAR,
pos);
+ return n.substring(pos, end < 0 ? n.length() : end);
+ }
+
+ private static boolean isSegmentEnd(String n, int pos) {
+ return pos == n.length() || (pos < n.length() && n.charAt(pos) ==
PackagingURIHelper.FORWARD_SLASH_CHAR);
+ }
+
+ /**
+ * @return the length of the longest run of whole segments at the
start of
+ * the label which equals the name from the given position on
+ */
+ private static int commonSegments(String n, int pos, String label) {
+ int common = 0;
+ int start = 0;
+ while (true) {
+ int end = label.indexOf(PackagingURIHelper.FORWARD_SLASH_CHAR,
start);
+ if (end < 0) {
+ end = label.length();
+ }
+ if (!n.regionMatches(pos + start, label, start, end - start)
|| !isSegmentEnd(n, pos + end)) {
+ return common;
+ }
+ common = end;
+ if (end == label.length()) {
+ return common;
+ }
+ start = end + 1;
+ }
+ }
+ }
+
/**
* The values themselves should be returned in sorted order. Doing it here
diff --git
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
index d48d5965a2..22f9507f67 100644
--- a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
+++ b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
@@ -17,7 +17,6 @@
package org.apache.poi.openxml4j.opc;
-import java.math.BigInteger;
import java.net.URI;
import java.net.URISyntaxException;
import java.util.Locale;
@@ -575,10 +574,7 @@ public final class PackagePartName implements
Comparable<PackagePartName> {
idx2++;
}
- // note: BigInteger for extra safety
- final BigInteger b1 = new BigInteger(name1.substring(beg1,
idx1));
- final BigInteger b2 = new BigInteger(name2.substring(beg2,
idx2));
- final int cmp = b1.compareTo(b2);
+ final int cmp = compareNumbers(name1, beg1, idx1, name2, beg2,
idx2);
if (cmp != 0) {
return cmp;
}
@@ -591,6 +587,31 @@ public final class PackagePartName implements
Comparable<PackagePartName> {
return (len1 - len2);
}
+ /**
+ * Compares two runs of digits by their numerical value, in time linear in
their
+ * length: parsing them as a BigInteger is quadratic, and a part name can
hold
+ * tens of thousands of digits.
+ */
+ private static int compareNumbers(String str1, int beg1, int end1, String
str2, int beg2, int end2) {
+ while (beg1 < end1 && Character.digit(str1.charAt(beg1), 10) == 0) {
+ beg1++;
+ }
+ while (beg2 < end2 && Character.digit(str2.charAt(beg2), 10) == 0) {
+ beg2++;
+ }
+ final int cmp = (end1 - beg1) - (end2 - beg2);
+ if (cmp != 0) {
+ return cmp;
+ }
+ while (beg1 < end1) {
+ final int diff = Character.digit(str1.charAt(beg1++), 10) -
Character.digit(str2.charAt(beg2++), 10);
+ if (diff != 0) {
+ return diff;
+ }
+ }
+ return 0;
+ }
+
private static boolean isDigitOrLetter(char c) {
return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a'
&& c <= 'z');
}
diff --git
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartCollection.java
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartCollection.java
index f64d582c12..d44a0dc442 100644
---
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartCollection.java
+++
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartCollection.java
@@ -19,11 +19,23 @@ package org.apache.poi.openxml4j.opc;
import static
org.apache.poi.openxml4j.OpenXML4JTestDataSamples.openSampleStream;
import static org.junit.jupiter.api.Assertions.assertEquals;
+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.assertTimeout;
+import java.io.IOException;
import java.io.InputStream;
+import java.nio.charset.StandardCharsets;
+import java.time.Duration;
import java.util.List;
import java.util.regex.Pattern;
+import java.util.zip.ZipEntry;
+import java.util.zip.ZipOutputStream;
+import org.apache.commons.io.output.UnsynchronizedByteArrayOutputStream;
+import org.apache.poi.openxml4j.exceptions.InvalidOperationException;
+import org.apache.poi.openxml4j.opc.internal.MemoryPackagePart;
import org.junit.jupiter.api.Test;
public class TestPackagePartCollection {
@@ -42,4 +54,118 @@ public class TestPackagePartCollection {
}
}
+ /**
+ * Checking rule M1.11 used to build and look up every prefix of a part
name,
+ * which is quadratic in the length of deeply nested names. Filtering the
+ * prefixes by the lengths of the registered names isn't enough either, as
a
+ * package can also contain names with just those lengths, which is what
the
+ * first loop adds.
+ */
+ @Test
+ void testDeeplyNestedPartNames() throws Exception {
+ String folder = "a/".repeat(15_000);
+ UnsynchronizedByteArrayOutputStream bos =
UnsynchronizedByteArrayOutputStream.builder().get();
+ try (ZipOutputStream zos = new ZipOutputStream(bos)) {
+ addEntry(zos, "[Content_Types].xml",
+ "<Types
xmlns=\"http://schemas.openxmlformats.org/package/2006/content-types\">"
+ + "<Default Extension=\"xml\"
ContentType=\"application/xml\"/></Types>");
+ for (int i = 0; i < 50; i++) {
+ addEntry(zos, folder + "d" + "x".repeat(i) + ".xml", "<a/>");
+ }
+ for (int i = 0; i < 50; i++) {
+ addEntry(zos, folder + folder + "p" + i + ".xml", "<a/>");
+ }
+ }
+
+ assertTimeout(Duration.ofSeconds(60), () -> {
+ try (OPCPackage pkg = OPCPackage.open(bos.toInputStream())) {
+ assertEquals(100, pkg.getParts().size());
+ }
+ });
+
+ // the names are still checked
+ PackagePartCollection parts = new PackagePartCollection();
+ String deep = "/" + folder + "p.xml";
+ put(parts, deep);
+ assertThrows(InvalidOperationException.class, () -> put(parts, deep +
"/derived.xml"));
+ }
+
+ /**
+ * {@link PackagePartName#compare} treats runs of digits by their value, so
+ * differently spelled names can be the same part for the lookup
+ */
+ @Test
+ void testEqualNamesSpelledDifferently() throws Exception {
+ PackagePartCollection parts = new PackagePartCollection();
+ put(parts, "/a01b1.xml");
+
assertNotNull(parts.remove(PackagingURIHelper.createPartName("/a1b01.xml")));
+ put(parts, "/a01b1.xml");
+ put(parts, "/a1b01.xml");
+ assertEquals(1, parts.size());
+
assertNotNull(parts.remove(PackagingURIHelper.createPartName("/a01b1.xml")));
+ put(parts, "/a01b1.xml/x.xml");
+ assertEquals(1, parts.size());
+ }
+
+ @Test
+ void testDerivedPartNames() throws Exception {
+ PackagePartCollection parts = new PackagePartCollection();
+ put(parts, "/a/b/c.xml");
+ put(parts, "/a/b/d.xml");
+ put(parts, "/a/x.xml");
+
+ assertThrows(InvalidOperationException.class, () -> put(parts,
"/a/b/c.xml/y.xml"));
+ assertThrows(InvalidOperationException.class, () -> put(parts,
"/a/x.xml/y.xml"));
+ // a prefix which doesn't end at a slash is fine
+ put(parts, "/a/b/c.xm");
+ put(parts, "/a/b.xml");
+ assertEquals(5, parts.size());
+
+
assertNotNull(parts.remove(PackagingURIHelper.createPartName("/a/b/c.xml")));
+
assertNull(parts.remove(PackagingURIHelper.createPartName("/a/b/c.xml")));
+ put(parts, "/a/b/c.xml/y.xml");
+ assertThrows(InvalidOperationException.class, () -> put(parts,
"/a/b/d.xml/y.xml"));
+ assertEquals(5, parts.size());
+ }
+
+ /**
+ * Part names are equal regardless of case, so the derived name check and
+ * {@link PackagePartCollection#remove} have to ignore case as well
+ */
+ @Test
+ void testDerivedPartNamesIgnoreCase() throws Exception {
+ PackagePartCollection parts = new PackagePartCollection();
+ put(parts, "/word/document.xml");
+ assertThrows(InvalidOperationException.class, () -> put(parts,
"/Word/Document.xml/image1.gif"));
+
+ put(parts, "/A.xml");
+
assertNotNull(parts.remove(PackagingURIHelper.createPartName("/a.xml")));
+ put(parts, "/A.xml/x.xml");
+ assertEquals(2, parts.size());
+ }
+
+ @Test
+ void testDerivedPartNameAfterRemove() throws Exception {
+ try (OPCPackage pkg =
OPCPackage.create(UnsynchronizedByteArrayOutputStream.builder().get())) {
+ PackagePartName name =
PackagingURIHelper.createPartName("/word/document.xml");
+ PackagePartName derived =
PackagingURIHelper.createPartName("/word/document.xml/image1.gif");
+ pkg.createPart(name, ContentTypes.XML);
+ assertThrows(InvalidOperationException.class, () ->
pkg.createPart(derived, ContentTypes.IMAGE_GIF));
+
+ pkg.removePart(name);
+ assertNotNull(pkg.createPart(derived, ContentTypes.IMAGE_GIF));
+ pkg.revert();
+ }
+ }
+
+ private static void addEntry(ZipOutputStream zos, String name, String
content) throws IOException {
+ zos.putNextEntry(new ZipEntry(name));
+ zos.write(content.getBytes(StandardCharsets.UTF_8));
+ zos.closeEntry();
+ }
+
+ private static void put(PackagePartCollection parts, String name) throws
Exception {
+ PackagePartName partName = PackagingURIHelper.createPartName(name);
+ parts.put(partName, new MemoryPackagePart(null, partName,
ContentTypes.XML, false));
+ }
}
diff --git
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
index 4de7584b9d..f93abbba35 100644
---
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
+++
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
@@ -17,6 +17,9 @@
package org.apache.poi.openxml4j.opc;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.greaterThan;
+import static org.hamcrest.Matchers.lessThan;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
@@ -81,4 +84,30 @@ public final class TestPackagePartName {
() ->
PackagingURIHelper.createPartName(name).isRelationshipPartURI());
assertFalse(result);
}
+
+ @Test
+ void testCompareNumbers() {
+ assertThat(PackagePartName.compare("/f2.png", "/f10.png"),
lessThan(0));
+ assertThat(PackagePartName.compare("/f10.png", "/f2.png"),
greaterThan(0));
+ assertThat(PackagePartName.compare("/f007.xml", "/f7.xml"),
greaterThan(0));
+ assertThat(PackagePartName.compare("/f00.xml", "/f0.xml"),
greaterThan(0));
+ assertEquals(0, PackagePartName.compare("/a01b1.xml", "/a1b01.xml"));
+ // more digits than fit in a long
+ assertThat(PackagePartName.compare("/f" + "9".repeat(30), "/f1" +
"0".repeat(30)), lessThan(0));
+ assertThat(PackagePartName.compare("/f" + "2".repeat(30), "/f" +
"1".repeat(30)), greaterThan(0));
+ }
+
+ /**
+ * Parsing the digits as a BigInteger is quadratic in their number
+ */
+ @Test
+ void testCompareSlowness() {
+ String name1 = "/" + "1".repeat(65_000) + "2.xml";
+ String name2 = "/" + "1".repeat(65_000) + "3.xml";
+ assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
+ for (int i = 0; i < 1_000; i++) {
+ assertThat(PackagePartName.compare(name1, name2), lessThan(0));
+ }
+ });
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]