libxml2: linearly optimize XPath expressions.

third_party/libxml/src/xpath.c

 /*
  * xpath.c: XML Path Language implementation
  *          XPath is a language for addressing parts of an XML document,
  *          designed to be used by both XSLT and XPointer
  *f
  * Reference: W3C Recommendation 16 November 1999
  *     http://www.w3.org/TR/1999/REC-xpath-19991116
  * Public reference:
  *     http://www.w3.org/TR/xpath
  *
@@ skipping 1114 matching lines @@
             comp->steps[comp->nbStep].value5 = (xmlChar *)
                 (void *)xmlDictLookup(comp->dict, value5, -1);
             xmlFree(value5);
         } else
             comp->steps[comp->nbStep].value5 = NULL;
     } else {
         comp->steps[comp->nbStep].value4 = value4;
         comp->steps[comp->nbStep].value5 = value5;
     }
     comp->steps[comp->nbStep].cache = NULL;
+    comp->steps[comp->nbStep].cacheURI = NULL;
     return(comp->nbStep++);
 }
 
 /**
  * xmlXPathCompSwap:
  * @comp:  the compiled expression
  * @op: operation index
  *
  * Swaps 2 operations in the compiled expression
  */
@@ skipping 13580 matching lines @@
                 xmlDictReference(comp->dict);
             return(comp);
         }
         xmlFreePattern(stream);
     }
     return(NULL);
 }
 #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.
     */
 
     if ((op->op == XPATH_OP_COLLECT /* 11 */) &&
         (op->ch1 != -1) &&
         (op->ch2 == -1 /* no predicate */))
     {
         xmlXPathStepOpPtr prevop = &comp->steps[op->ch1];
@@ skipping 30 matching lines @@
                     */
                     op->ch1   = prevop->ch1;
                     op->value = AXIS_DESCENDANT_OR_SELF;
                     break;
                 default:
                     break;
             }
         }
     }
 
+    /* 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;
 }
 
 /**
  * xmlXPathCtxtCompile:
  * @ctxt: an XPath context
  * @str:  the XPath expression
  *
  * Compile an XPath expression
  *
  * Returns the xmlXPathCompExprPtr resulting from the compilation or NULL.
@@ skipping 38 matching lines @@
     }
     xmlXPathFreeParserContext(pctxt);
 
     if (comp != NULL) {
         comp->expr = xmlStrdup(str);
 #ifdef DEBUG_EVAL_COUNTS
         comp->string = xmlStrdup(str);
         comp->nb = 0;
 #endif
         if ((comp->nbStep > 1) && (comp->last >= 0)) {
-            xmlXPathOptimizeExpression(comp, &comp->steps[comp->last]);
+            xmlXPathOptimizeExpression(comp, comp->last);
         }
     }
     return(comp);
 }
 
 /**
  * xmlXPathCompile:
  * @str:  the XPath expression
  *
  * Compile an XPath expression
@@ skipping 161 matching lines @@
             while (*ctxt->cur != 0) ctxt->cur++;
     } else
 #endif
     {
         xmlXPathCompileExpr(ctxt, 1);
         if ((ctxt->error == XPATH_EXPRESSION_OK) &&
             (ctxt->comp != NULL) &&
             (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;
     xmlXPathRunEval(ctxt, 0);
 }
 
 /**
  * xmlXPathEval:
  * @str:  the XPath expression
  * @ctx:  the XPath context
@@ skipping 324 matching lines @@
                          xmlXPathTranslateFunction);
 
     xmlXPathRegisterFuncNS(ctxt, (const xmlChar *)"escape-uri",
          (const xmlChar *)"http://www.w3.org/2002/08/xquery-functions",
                          xmlXPathEscapeUriFunction);
 }
 
 #endif /* LIBXML_XPATH_ENABLED */
 #define bottom_xpath
 #include "elfgcchack.h"