libxml2: linearly optimize XPath expressions.

third_party/libxml/src/xpath.c

Index: third_party/libxml/src/xpath.c
diff --git a/third_party/libxml/src/xpath.c b/third_party/libxml/src/xpath.c
index dc41ce6b327774adad749c3c58401f485b5a5f0c..533c7b7cd3e796ea7a226c9899357fd77075c6ae 100644
--- a/third_party/libxml/src/xpath.c
+++ b/third_party/libxml/src/xpath.c
@@ -1132,6 +1132,7 @@ xmlXPathCompExprAdd(xmlXPathCompExprPtr comp, int ch1, int ch2,
 	comp->steps[comp->nbStep].value5 = value5;
     }
     comp->steps[comp->nbStep].cache = NULL;
+    comp->steps[comp->nbStep].cacheURI = NULL;
     return(comp->nbStep++);
 }
 
@@ -14732,8 +14733,12 @@ xmlXPathTryStreamCompile(xmlXPathContextPtr ctxt, const xmlChar *str) {
 #endif /* XPATH_STREAMING */
 
 static void
-xmlXPathOptimizeExpression(xmlXPathCompExprPtr comp, xmlXPathStepOpPtr op)
+xmlXPathOptimizeExpressionInternal(xmlXPathCompExprPtr comp, xmlXPathStepOpPtr op)
 {
+    /* Already optimized? */
+    if (op->cacheURI != NULL)
+        return;
+
     /*
     * Try to rewrite "descendant-or-self::node()/foo" to an optimized
     * internal representation.
@@ -14784,11 +14789,28 @@ xmlXPathOptimizeExpression(xmlXPathCompExprPtr comp, xmlXPathStepOpPtr op)
 	}
     }
 
+    /* Mark the node. */
+    op->cacheURI = (void*)(~0);
+
     /* Recurse */
     if (op->ch1 != -1)
-        xmlXPathOptimizeExpression(comp, &comp->steps[op->ch1]);
+        xmlXPathOptimizeExpressionInternal(comp, &comp->steps[op->ch1]);
     if (op->ch2 != -1)
-	xmlXPathOptimizeExpression(comp, &comp->steps[op->ch2]);
+	xmlXPathOptimizeExpressionInternal(comp, &comp->steps[op->ch2]);
+}
+
+static void
+xmlXPathOptimizeExpression(xmlXPathCompExprPtr comp, int root)
+{
+    int i;
+    /* The expression tree/graph traversal is linear, visiting
+     * each node at most once. Mark each xmlXPathStepOp node
+     * upon visiting, taking care of clearing out the marks
+     * afterwards.
+     */
+    xmlXPathOptimizeExpressionInternal(comp, &comp->steps[root]);
+    for (i = 0; i <= root; ++i)
+        comp->steps[i].cacheURI = NULL;
 }
 
 /**
@@ -14847,7 +14869,7 @@ xmlXPathCtxtCompile(xmlXPathContextPtr ctxt, const xmlChar *str) {
 	comp->nb = 0;
 #endif
 	if ((comp->nbStep > 1) && (comp->last >= 0)) {
-	    xmlXPathOptimizeExpression(comp, &comp->steps[comp->last]);
+	    xmlXPathOptimizeExpression(comp, comp->last);
 	}
     }
     return(comp);
@@ -15029,8 +15051,7 @@ xmlXPathEvalExpr(xmlXPathParserContextPtr ctxt) {
 	    (ctxt->comp->nbStep > 1) &&
 	    (ctxt->comp->last >= 0))
 	{
-	    xmlXPathOptimizeExpression(ctxt->comp,
-		&ctxt->comp->steps[ctxt->comp->last]);
+	    xmlXPathOptimizeExpression(ctxt->comp, ctxt->comp->last);
 	}
     }
     CHECK_ERROR;