pjfanning commented on code in PR #1577:
URL: https://github.com/apache/poi/pull/1577#discussion_r4648055222
##########
poi-ooxml/src/main/java/org/apache/poi/xwpf/usermodel/XWPFDocument.java:
##########
@@ -443,22 +445,29 @@ public String getTblStyle(XWPFTable table) {
}
public XWPFHyperlink getHyperlinkByID(String id) {
- for (XWPFHyperlink link : hyperlinks) {
- if (link.getId().equals(id)) {
- return link;
- }
+ if (id == null) {
+ return null;
+ }
+ XWPFHyperlink link = hyperlinksById.get(id);
Review Comment:
Nothing ever invalidates this cache. After
`doc.getPackagePart().removeRelationship("rId5")` and re-adding `rId5` with a
new URL (or a different type), `getHyperlinkByID("rId5")` keeps returning the
old URL, and the stale entry stays in `getHyperlinks()`. Previously a miss on
any other id rebuilt the list and dropped it. Could a hit be checked against
`getPackagePart().getRelationship(id)` (cheap, it's a map lookup), or the cache
cleared where hyperlink relationships are removed?
##########
poi-ooxml/src/main/java/org/apache/poi/xwpf/usermodel/XWPFDocument.java:
##########
@@ -443,22 +445,29 @@ public String getTblStyle(XWPFTable table) {
}
public XWPFHyperlink getHyperlinkByID(String id) {
- for (XWPFHyperlink link : hyperlinks) {
- if (link.getId().equals(id)) {
- return link;
- }
+ if (id == null) {
+ return null;
+ }
+ XWPFHyperlink link = hyperlinksById.get(id);
+ if (link != null) {
+ return link;
}
- // If the link was not found, rebuild the list (maybe a new link was
added into the document) and check again.
- initHyperlinks();
- for (XWPFHyperlink link : hyperlinks) {
- if (link.getId().equals(id)) {
- return link;
- }
+ // The link may have been added after the document was read, e.g. by
createHyperlinkRun.
+ // Only look up this relationship: rebuilding the list for every
unknown id is quadratic
+ // in the number of hyperlinks, and the ids are taken from the
document content.
+ PackageRelationship rel = getPackagePart().getRelationship(id);
Review Comment:
A miss now adds only the one relationship looked up, so other hyperlink
relationships added after loading never show up in `getHyperlinks()`. E.g.
`createHyperlinkRun(urlA)`, `createHyperlinkRun(urlB)`, then resolve only A:
before, the rebuild meant `getHyperlinks()` held both; now only A, until B is
looked up by id. If `getHyperlinks()` should stay complete, it could resync
from the package itself (it's not on the hot path).
Unrelated to this change but in the same function: ids are always resolved
against the main document part, so hyperlink runs in
headers/footers/footnotes/comments use the wrong relationship table (wrong URL
if ids collide, null otherwise). Might be worth a follow-up issue.
##########
poi-ooxml/src/main/java/org/apache/poi/xwpf/usermodel/XWPFDocument.java:
##########
@@ -100,6 +100,7 @@ public class XWPFDocument extends POIXMLDocument implements
Document, IBody {
protected List<XWPFFooter> footers = new ArrayList<>();
protected List<XWPFHeader> headers = new ArrayList<>();
protected List<XWPFHyperlink> hyperlinks = new ArrayList<>();
Review Comment:
`hyperlinks` is still a protected, non-final list, but `getHyperlinkByID`
now only consults the private `hyperlinksById`. A subclass that adds to
`hyperlinks` (e.g. `hyperlinks.add(new XWPFHyperlink("myId", url))`) or
replaces the list used to have those links resolved by the scan; now the map
misses, the package part has no such relationship, and it returns null, so
`XWPFHyperlinkRun.getHyperlink` and `setFetchHyperlinks(true)` extraction
silently drop the URL. Either keep the two in sync (fall back to scanning
`hyperlinks` on a map miss before going to the package) or document that the
list is no longer the source of truth.
##########
poi-ooxml/src/main/java/org/apache/poi/xwpf/usermodel/XWPFDocument.java:
##########
@@ -443,22 +445,29 @@ public String getTblStyle(XWPFTable table) {
}
public XWPFHyperlink getHyperlinkByID(String id) {
- for (XWPFHyperlink link : hyperlinks) {
- if (link.getId().equals(id)) {
- return link;
- }
+ if (id == null) {
+ return null;
+ }
+ XWPFHyperlink link = hyperlinksById.get(id);
+ if (link != null) {
+ return link;
}
- // If the link was not found, rebuild the list (maybe a new link was
added into the document) and check again.
- initHyperlinks();
- for (XWPFHyperlink link : hyperlinks) {
- if (link.getId().equals(id)) {
- return link;
- }
+ // The link may have been added after the document was read, e.g. by
createHyperlinkRun.
+ // Only look up this relationship: rebuilding the list for every
unknown id is quadratic
+ // in the number of hyperlinks, and the ids are taken from the
document content.
+ PackageRelationship rel = getPackagePart().getRelationship(id);
+ if (rel == null ||
!XWPFRelation.HYPERLINK.getRelation().equals(rel.getRelationshipType())) {
+ return null;
}
+ return addHyperlink(rel);
+ }
- // Link still not there? Giving up.
- return null;
+ private XWPFHyperlink addHyperlink(PackageRelationship rel) {
+ XWPFHyperlink link = new XWPFHyperlink(rel.getId(),
rel.getTargetURI().toString());
+ hyperlinks.add(link);
Review Comment:
This makes a getter mutate both the shared `ArrayList` and the `HashMap` in
place; the old code assigned a freshly built list. Two threads reading the same
document (e.g. extracting different paragraphs in parallel) can now get a
`ConcurrentModificationException` while one iterates `getHyperlinks()`, or
corrupt the HashMap. POI isn't thread-safe in general, but read-only use used
to be safe here.
Minor: it also means `getHyperlinks()` order follows lookup order after a
miss, rather than relationship order as the rebuild produced.
##########
poi-ooxml/src/test/java/org/apache/poi/xwpf/usermodel/TestXWPFDocument.java:
##########
@@ -223,6 +228,44 @@ void testAddHyperlink() throws IOException {
}
}
+ /**
+ * Looking up an id that isn't a hyperlink relationship must not rebuild
the hyperlink list,
+ * otherwise a document with n such links and n hyperlink relationships
takes O(n^2) to extract
+ */
+ @Test
+ void testUnknownHyperlinkIds() throws Exception {
+ final int count = 10_000;
+ try (XWPFDocument doc = new XWPFDocument()) {
+ for (int i = 0; i < count; i++) {
+ doc.getPackagePart().addRelationship(new
URI("https://poi.apache.org/" + i),
+ TargetMode.EXTERNAL, XWPFRelation.HYPERLINK.getRelation(),
"rIdH" + i);
+ }
+ doc.getPackagePart().addRelationship(new
URI("https://poi.apache.org/"),
+ TargetMode.EXTERNAL, "http://example.com/other", "rIdOther");
+ XWPFParagraph p = doc.createParagraph();
+ for (int i = 0; i < count; i++) {
+ CTHyperlink link = p.getCTP().addNewHyperlink();
+ link.setId("x" + i);
+ link.addNewR().addNewT().setStringValue("a");
+ }
+ CTHyperlink known = p.getCTP().addNewHyperlink();
+ known.setId("rIdH42");
+ known.addNewR().addNewT().setStringValue("b");
+
+ try (XWPFDocument doc2 =
XWPFTestDataSamples.writeOutAndReadBack(doc)) {
+ assertTimeout(Duration.ofSeconds(20), () -> {
+ try (XWPFWordExtractor ex = new XWPFWordExtractor(doc2)) {
+ ex.setFetchHyperlinks(true);
+ assertTrue(ex.getText().contains("
<https://poi.apache.org/42>"));
Review Comment:
Could this use `assertThat(ex.getText(), containsString("
<https://poi.apache.org/42>"))`? On failure `assertTrue` only reports 'expected
true', while the matcher prints the extracted text.
##########
poi-ooxml/src/test/java/org/apache/poi/xwpf/usermodel/TestXWPFDocument.java:
##########
@@ -223,6 +228,44 @@ void testAddHyperlink() throws IOException {
}
}
+ /**
+ * Looking up an id that isn't a hyperlink relationship must not rebuild
the hyperlink list,
+ * otherwise a document with n such links and n hyperlink relationships
takes O(n^2) to extract
+ */
+ @Test
+ void testUnknownHyperlinkIds() throws Exception {
+ final int count = 10_000;
Review Comment:
10,000 relationships plus 10,000 `CTHyperlink` elements and a full
write/read-back is quite heavy for a unit test that runs with every xwpf build.
A smaller count (e.g. 2,000) would still show the difference between linear and
quadratic behaviour.
##########
poi-ooxml/src/test/java/org/apache/poi/xwpf/usermodel/TestXWPFDocument.java:
##########
@@ -223,6 +228,44 @@ void testAddHyperlink() throws IOException {
}
}
+ /**
+ * Looking up an id that isn't a hyperlink relationship must not rebuild
the hyperlink list,
+ * otherwise a document with n such links and n hyperlink relationships
takes O(n^2) to extract
+ */
+ @Test
+ void testUnknownHyperlinkIds() throws Exception {
+ final int count = 10_000;
+ try (XWPFDocument doc = new XWPFDocument()) {
+ for (int i = 0; i < count; i++) {
+ doc.getPackagePart().addRelationship(new
URI("https://poi.apache.org/" + i),
+ TargetMode.EXTERNAL, XWPFRelation.HYPERLINK.getRelation(),
"rIdH" + i);
+ }
+ doc.getPackagePart().addRelationship(new
URI("https://poi.apache.org/"),
+ TargetMode.EXTERNAL, "http://example.com/other", "rIdOther");
+ XWPFParagraph p = doc.createParagraph();
+ for (int i = 0; i < count; i++) {
+ CTHyperlink link = p.getCTP().addNewHyperlink();
+ link.setId("x" + i);
+ link.addNewR().addNewT().setStringValue("a");
+ }
+ CTHyperlink known = p.getCTP().addNewHyperlink();
+ known.setId("rIdH42");
+ known.addNewR().addNewT().setStringValue("b");
+
+ try (XWPFDocument doc2 =
XWPFTestDataSamples.writeOutAndReadBack(doc)) {
+ assertTimeout(Duration.ofSeconds(20), () -> {
Review Comment:
`assertTimeout` runs in the same thread and only fails after the work
completes, so on a regression back to quadratic behaviour the test runs for the
full duration (32 s+ at this size per the description) before failing. A
wall-clock bound is also prone to flakiness on slow CI runners. I'd consider
dropping the timeout and asserting the behaviour directly instead (e.g. that a
miss doesn't rescan the relationships), or at least shrinking the input, see
below.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]