Fix quadratic runtime in xi:fallback processing
Copying the tree would lead to runtime quadratic in nested fallback
depth, similar to naive string concatenation.
diff --git a/xinclude.c b/xinclude.c
index e9d3af5..9a65ee5 100644
--- a/xinclude.c
+++ b/xinclude.c
@@ -2003,8 +2003,7 @@
ret = -1;
xmlXIncludeFreeContext(newctxt);
- ctxt->incTab[nr]->inc = xmlDocCopyNodeList(ctxt->doc,
- fallback->children);
+ ctxt->incTab[nr]->inc = fallback->children;
} else {
ctxt->incTab[nr]->inc = NULL;
}
@@ -2268,12 +2267,6 @@
* XInclude end one
*/
cur->type = XML_XINCLUDE_START;
- /* Remove fallback children */
- for (child = cur->children; child != NULL; child = next) {
- next = child->next;
- xmlUnlinkNode(child);
- xmlFreeNode(child);
- }
end = xmlNewDocNode(cur->doc, cur->ns, cur->name, NULL);
if (end == NULL) {
xmlXIncludeErr(ctxt, ctxt->incTab[nr]->ref,
@@ -2289,11 +2282,17 @@
* Add the list of nodes
*/
while (list != NULL) {
- cur = list;
- list = list->next;
-
- xmlAddPrevSibling(end, cur);
+ next = list->next;
+ xmlAddPrevSibling(end, list);
+ list = next;
}
+
+ /* Remove fallback node */
+ for (child = cur->children; child != NULL; child = next) {
+ next = child->next;
+ xmlUnlinkNode(child);
+ xmlFreeNode(child);
+ }
}
