preparing release 1.1.15 a bit more cleanup Daniel
[platform/upstream/libxslt.git] / libxslt / pattern.c
index dd82eb3..ed8e858 100644 (file)
@@ -60,6 +60,20 @@ typedef enum {
     XSLT_OP_PREDICATE
 } xsltOp;
 
+typedef struct _xsltStepState xsltStepState;
+typedef xsltStepState *xsltStepStatePtr;
+struct _xsltStepState {
+    int step;
+    xmlNodePtr node;
+};
+
+typedef struct _xsltStepStates xsltStepStates;
+typedef xsltStepStates *xsltStepStatesPtr;
+struct _xsltStepStates {
+    int nbstates;
+    int maxstates;
+    xsltStepStatePtr states;
+};
 
 typedef struct _xsltStepOp xsltStepOp;
 typedef xsltStepOp *xsltStepOpPtr;
@@ -85,6 +99,7 @@ struct _xsltCompMatch {
     const xmlChar *modeURI;      /* the mode URI */
     xsltTemplatePtr template;    /* the associated template */
 
+    int direct;
     /* TODO fix the statically allocated size steps[] */
     int nbStep;
     int maxStep;
@@ -133,6 +148,7 @@ xsltNewCompMatch(void) {
     cur->maxStep = 40;
     cur->nsNr = 0;
     cur->nsList = NULL;
+    cur->direct = 0;
     return(cur);
 }
 
@@ -151,10 +167,6 @@ xsltFreeCompMatch(xsltCompMatchPtr comp) {
        return;
     if (comp->pattern != NULL)
        xmlFree((xmlChar *)comp->pattern);
-    if (comp->mode != NULL)
-       xmlFree((xmlChar *)comp->mode);
-    if (comp->modeURI != NULL)
-       xmlFree((xmlChar *)comp->modeURI);
     if (comp->nsList != NULL)
        xmlFree(comp->nsList);
     for (i = 0;i < comp->nbStep;i++) {
@@ -289,7 +301,24 @@ xsltCompMatchAdd(xsltParserContextPtr ctxt, xsltCompMatchPtr comp,
            xsltAllocateExtra(ctxt->style);
     }
     if (op == XSLT_OP_PREDICATE) {
-       comp->steps[comp->nbStep].comp = xsltXPathCompile(ctxt->style, value);
+       xmlXPathContextPtr xctxt;
+
+       if (ctxt->style != NULL)
+           xctxt = xmlXPathNewContext(ctxt->style->doc);
+       else
+           xctxt = xmlXPathNewContext(NULL);
+#ifdef XML_XPATH_NOVAR
+       xctxt->flags = XML_XPATH_NOVAR;
+#endif
+       if (ctxt->style != NULL)
+           xctxt->dict = ctxt->style->dict;
+       comp->steps[comp->nbStep].comp = xmlXPathCtxtCompile(xctxt, value);
+       xmlXPathFreeContext(xctxt);
+       if (comp->steps[comp->nbStep].comp == NULL) {
+           xsltTransformError(NULL, ctxt->style, ctxt->elem,
+                   "Failed to compile predicate\n");
+           ctxt->style->errors++;
+       }
     }
     comp->nbStep++;
     return (0);
@@ -357,6 +386,27 @@ xsltReverseCompMatch(xsltCompMatchPtr comp) {
        i++;
     }
     comp->steps[comp->nbStep++].op = XSLT_OP_END;
+    /*
+     * detect consecutive XSLT_OP_PREDICATE indicating a direct
+     * matching should be done.
+     */
+    for (i = 0;i < comp->nbStep - 1;i++) {
+        if ((comp->steps[i].op == XSLT_OP_PREDICATE) &&
+           (comp->steps[i + 1].op == XSLT_OP_PREDICATE)) {
+
+           comp->direct = 1;
+           if (comp->pattern[0] != '/') {
+               xmlChar *query;
+
+               query = xmlStrdup((const xmlChar *)"//");
+               query = xmlStrcat(query, comp->pattern);
+
+               xmlFree((xmlChar *) comp->pattern);
+               comp->pattern = query;
+           }
+           break;
+       }
+    }
 }
 
 /************************************************************************
@@ -365,6 +415,132 @@ xsltReverseCompMatch(xsltCompMatchPtr comp) {
  *                                                                     *
  ************************************************************************/
 
+static int
+xsltPatPushState(xsltStepStates *states, int step, xmlNodePtr node) {
+    if ((states->states == NULL) || (states->maxstates <= 0)) {
+        states->maxstates = 4;
+       states->nbstates = 0;
+       states->states = xmlMalloc(4 * sizeof(xsltStepState));
+    }
+    else if (states->maxstates <= states->nbstates) {
+        xsltStepState *tmp;
+
+       tmp = (xsltStepStatePtr) xmlRealloc(states->states,
+                              2 * states->maxstates * sizeof(xsltStepState));
+       if (tmp == NULL)
+           return(-1);
+       states->states = tmp;
+       states->maxstates *= 2;
+    }
+    states->states[states->nbstates].step = step;
+    states->states[states->nbstates++].node = node;
+#if 0
+    fprintf(stderr, "Push: %d, %s\n", step, node->name);
+#endif
+    return(0);
+}
+
+/**
+ * xsltTestCompMatchDirect:
+ * @ctxt:  a XSLT process context
+ * @comp: the precompiled pattern
+ * @node: a node
+ *
+ * Test whether the node matches the pattern, do a direct evalutation
+ * and not a step by step evaluation.
+ *
+ * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
+ */
+static int
+xsltTestCompMatchDirect(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
+                       xmlNodePtr node) {
+    xsltStepOpPtr sel = NULL;
+    xmlDocPtr prevdoc;
+    xmlDocPtr doc;
+    xmlXPathObjectPtr list;
+    int ix, j;
+    int nocache = 0;
+    int isRVT;
+
+    doc = node->doc;
+    if ((doc != NULL) &&
+       (doc->name != NULL) &&
+       (doc->name[0] == ' ') &&
+       (xmlStrEqual(BAD_CAST doc->name,
+                    BAD_CAST " fake node libxslt")))
+       isRVT = 1;
+    else
+       isRVT = 0;
+    sel = &comp->steps[0]; /* store extra in first step arbitrarily */
+
+    prevdoc = (xmlDocPtr)
+       XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
+    ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
+    list = (xmlXPathObjectPtr)
+       XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra);
+    
+    if ((list == NULL) || (prevdoc != doc)) {
+       xmlXPathObjectPtr newlist;
+       xmlNodePtr parent = node->parent;
+       xmlDocPtr olddoc;
+       xmlNodePtr oldnode;
+
+       oldnode = ctxt->xpathCtxt->node;
+       olddoc = ctxt->xpathCtxt->doc;
+       ctxt->xpathCtxt->node = node;
+       ctxt->xpathCtxt->doc = doc;
+       newlist = xmlXPathEval(comp->pattern, ctxt->xpathCtxt);
+       ctxt->xpathCtxt->node = oldnode;
+       ctxt->xpathCtxt->doc = olddoc;
+       if (newlist == NULL)
+           return(-1);
+       if (newlist->type != XPATH_NODESET) {
+           xmlXPathFreeObject(newlist);
+           return(-1);
+       }
+       ix = 0;
+
+       if ((parent == NULL) || (node->doc == NULL) || isRVT)
+           nocache = 1;
+       
+       if (nocache == 0) {
+           if (list != NULL)
+               xmlXPathFreeObject(list);
+           list = newlist;
+
+           XSLT_RUNTIME_EXTRA_LST(ctxt, sel->lenExtra) =
+               (void *) list;
+           XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
+               (void *) doc;
+           XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
+               0;
+           XSLT_RUNTIME_EXTRA_FREE(ctxt, sel->lenExtra) =
+               (xmlFreeFunc) xmlXPathFreeObject;
+       } else
+           list = newlist;
+    }
+    if ((list->nodesetval == NULL) ||
+       (list->nodesetval->nodeNr <= 0)) {
+       if (nocache == 1)
+           xmlXPathFreeObject(list);
+       return(0);
+    }
+    /* TODO: store the index and use it for the scan */
+    if (ix == 0) {
+       for (j = 0;j < list->nodesetval->nodeNr;j++) {
+           if (list->nodesetval->nodeTab[j] == node) {
+               if (nocache == 1)
+                   xmlXPathFreeObject(list);
+               return(1);
+           }
+       }
+    } else {
+    }
+    if (nocache == 1)
+       xmlXPathFreeObject(list);
+    return(0);
+}
+
 /**
  * xsltTestCompMatch:
  * @ctxt:  a XSLT process context
@@ -373,7 +549,7 @@ xsltReverseCompMatch(xsltCompMatchPtr comp) {
  * @mode:  the mode name or NULL
  * @modeURI:  the mode URI or NULL
  *
- * Test wether the node matches the pattern
+ * Test whether the node matches the pattern
  *
  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
  */
@@ -382,7 +558,8 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                  xmlNodePtr node, const xmlChar *mode,
                  const xmlChar *modeURI) {
     int i;
-    xsltStepOpPtr step, select = NULL;
+    xsltStepOpPtr step, sel = NULL;
+    xsltStepStates states = {0, 0, NULL}; /* // may require backtrack */
 
     if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
        xsltTransformError(ctxt, NULL, node,
@@ -392,7 +569,10 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
     if (mode != NULL) {
        if (comp->mode == NULL)
            return(0);
-       if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
+       /*
+        * both mode strings must be interned on the stylesheet dictionary
+        */
+       if (comp->mode != mode)
            return(0);
     } else {
        if (comp->mode != NULL)
@@ -401,20 +581,25 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
     if (modeURI != NULL) {
        if (comp->modeURI == NULL)
            return(0);
-       if ((comp->modeURI != modeURI) &&
-           (!xmlStrEqual(comp->modeURI, modeURI)))
+       /*
+        * both modeURI strings must be interned on the stylesheet dictionary
+        */
+       if (comp->modeURI != modeURI)
            return(0);
     } else {
        if (comp->modeURI != NULL)
            return(0);
     }
-    for (i = 0;i < comp->nbStep;i++) {
+
+    i = 0;
+restart:
+    for (;i < comp->nbStep;i++) {
        step = &comp->steps[i];
        if (step->op != XSLT_OP_PREDICATE)
-           select = step;
+           sel = step;
        switch (step->op) {
             case XSLT_OP_END:
-               return(1);
+               goto found;
             case XSLT_OP_ROOT:
                if ((node->type == XML_DOCUMENT_NODE) ||
 #ifdef LIBXML_DOCB_ENABLED
@@ -424,26 +609,26 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                    continue;
                if ((node->type == XML_ELEMENT_NODE) && (node->name[0] == ' '))
                    continue;
-               return(0);
+               goto rollback;
             case XSLT_OP_ELEM:
                if (node->type != XML_ELEMENT_NODE)
-                   return(0);
+                   goto rollback;
                if (step->value == NULL)
                    continue;
                if (step->value[0] != node->name[0])
-                   return(0);
+                   goto rollback;
                if (!xmlStrEqual(step->value, node->name))
-                   return(0);
+                   goto rollback;
 
                /* Namespace test */
                if (node->ns == NULL) {
                    if (step->value2 != NULL)
-                       return(0);
+                       goto rollback;
                } else if (node->ns->href != NULL) {
                    if (step->value2 == NULL)
-                       return(0);
+                       goto rollback;
                    if (!xmlStrEqual(step->value2, node->ns->href))
-                       return(0);
+                       goto rollback;
                }
                continue;
             case XSLT_OP_CHILD: {
@@ -455,7 +640,7 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                    (node->type != XML_DOCB_DOCUMENT_NODE) &&
 #endif
                    (node->type != XML_HTML_DOCUMENT_NODE))
-                   return(0);
+                   goto rollback;
 
                lst = node->children;
 
@@ -470,24 +655,24 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                    if (lst != NULL)
                        continue;
                }
-               return(0);
+               goto rollback;
            }
             case XSLT_OP_ATTR:
                if (node->type != XML_ATTRIBUTE_NODE)
-                   return(0);
+                   goto rollback;
                if (step->value != NULL) {
                    if (step->value[0] != node->name[0])
-                       return(0);
+                       goto rollback;
                    if (!xmlStrEqual(step->value, node->name))
-                       return(0);
+                       goto rollback;
                }
                /* Namespace test */
                if (node->ns == NULL) {
                    if (step->value2 != NULL)
-                       return(0);
+                       goto rollback;
                } else if (step->value2 != NULL) {
                    if (!xmlStrEqual(step->value2, node->ns->href))
-                       return(0);
+                       goto rollback;
                }
                continue;
             case XSLT_OP_PARENT:
@@ -497,52 +682,63 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                    (node->type == XML_DOCB_DOCUMENT_NODE) ||
 #endif
                    (node->type == XML_NAMESPACE_DECL))
-                   return(0);
+                   goto rollback;
                node = node->parent;
                if (node == NULL)
-                   return(0);
+                   goto rollback;
                if (step->value == NULL)
                    continue;
                if (step->value[0] != node->name[0])
-                   return(0);
+                   goto rollback;
                if (!xmlStrEqual(step->value, node->name))
-                   return(0);
+                   goto rollback;
                /* Namespace test */
                if (node->ns == NULL) {
                    if (step->value2 != NULL)
-                       return(0);
+                       goto rollback;
                } else if (node->ns->href != NULL) {
                    if (step->value2 == NULL)
-                       return(0);
+                       goto rollback;
                    if (!xmlStrEqual(step->value2, node->ns->href))
-                       return(0);
+                       goto rollback;
                }
                continue;
             case XSLT_OP_ANCESTOR:
                /* TODO: implement coalescing of ANCESTOR/NODE ops */
                if (step->value == NULL) {
-                   i++;
-                   step = &comp->steps[i];
+                   step = &comp->steps[i+1];
                    if (step->op == XSLT_OP_ROOT)
-                       return(1);
-                   if (step->op != XSLT_OP_ELEM)
-                       return(0);
-                   if (step->value == NULL)
-                       return(-1);
+                       goto found;
+                   /* added NS, ID and KEY as a result of bug 168208 */
+                   if ((step->op != XSLT_OP_ELEM) && 
+                       (step->op != XSLT_OP_ALL) && 
+                       (step->op != XSLT_OP_NS) &&
+                       (step->op != XSLT_OP_ID) &&
+                       (step->op != XSLT_OP_KEY))
+                       goto rollback;
                }
                if (node == NULL)
-                   return(0);
+                   goto rollback;
                if ((node->type == XML_DOCUMENT_NODE) ||
                    (node->type == XML_HTML_DOCUMENT_NODE) ||
 #ifdef LIBXML_DOCB_ENABLED
                    (node->type == XML_DOCB_DOCUMENT_NODE) ||
 #endif
                    (node->type == XML_NAMESPACE_DECL))
-                   return(0);
+                   goto rollback;
                node = node->parent;
+               if ((step->op != XSLT_OP_ELEM) && step->op != XSLT_OP_ALL) {
+                   xsltPatPushState(&states, i, node);
+                   continue;
+               }
+               i++;
+               if (step->value == NULL) {
+                   xsltPatPushState(&states, i - 1, node);
+                   continue;
+               }
                while (node != NULL) {
                    if (node == NULL)
-                       return(0);
+                       goto rollback;
                    if ((node->type == XML_ELEMENT_NODE) &&
                        (step->value[0] == node->name[0]) &&
                        (xmlStrEqual(step->value, node->name))) {
@@ -559,18 +755,19 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                    node = node->parent;
                }
                if (node == NULL)
-                   return(0);
+                   goto rollback;
+               xsltPatPushState(&states, i - 1, node);
                continue;
             case XSLT_OP_ID: {
                /* TODO Handle IDs decently, must be done differently */
                xmlAttrPtr id;
 
                if (node->type != XML_ELEMENT_NODE)
-                   return(0);
+                   goto rollback;
 
                id = xmlGetID(node->doc, step->value);
                if ((id == NULL) || (id->parent != node))
-                   return(0);
+                   goto rollback;
                break;
            }
             case XSLT_OP_KEY: {
@@ -580,151 +777,79 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                list = xsltGetKey(ctxt, step->value,
                                  step->value3, step->value2);
                if (list == NULL)
-                   return(0);
+                   goto rollback;
                for (indx = 0;indx < list->nodeNr;indx++)
                    if (list->nodeTab[indx] == node)
                        break;
                if (indx >= list->nodeNr)
-                   return(0);
+                   goto rollback;
                break;
            }
             case XSLT_OP_NS:
                if (node->type != XML_ELEMENT_NODE)
-                   return(0);
+                   goto rollback;
                if (node->ns == NULL) {
                    if (step->value != NULL)
-                       return(0);
+                       goto rollback;
                } else if (node->ns->href != NULL) {
                    if (step->value == NULL)
-                       return(0);
+                       goto rollback;
                    if (!xmlStrEqual(step->value, node->ns->href))
-                       return(0);
+                       goto rollback;
                }
                break;
             case XSLT_OP_ALL:
                if (node->type != XML_ELEMENT_NODE)
-                   return(0);
+                   goto rollback;
                break;
            case XSLT_OP_PREDICATE: {
                xmlNodePtr oldNode;
+               xmlDocPtr doc;
                int oldCS, oldCP;
                int pos = 0, len = 0;
+               int isRVT;
+
                /*
-                * The simple existing predicate code cannot handle
-                * properly cascaded predicates. If in this situation
-                * compute directly the full node list once and check
-                * if the node is in the result list.
+                * when there is cascading XSLT_OP_PREDICATE, then use a
+                * direct computation approach. It's not done directly
+                * at the beginning of the routine to filter out as much
+                * as possible this costly computation.
                 */
-               if (comp->steps[i + 1].op == XSLT_OP_PREDICATE) {
-                   xmlDocPtr prevdoc, doc;
-                   xmlXPathObjectPtr list;
-                   int index, j;
-                   int nocache = 0;
-
-                   prevdoc = (xmlDocPtr)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra);
-                   index = (int)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra);
-                   list = (xmlXPathObjectPtr)
-                       XSLT_RUNTIME_EXTRA_LST(ctxt, select->lenExtra);
-                   
-                   doc = node->doc;
-                   if ((list == NULL) || (prevdoc != doc)) {
-                       xmlChar *query;
-                       xmlXPathObjectPtr newlist;
-                       xmlNodePtr parent = node->parent;
-                       xmlDocPtr olddoc;
-                       xmlNodePtr oldnode;
-
-                       if (comp->pattern[0] == '/')
-                           query = xmlStrdup(comp->pattern);
-                       else {
-                           query = xmlStrdup((const xmlChar *)"//");
-                           query = xmlStrcat(query, comp->pattern);
-                       }
-                       oldnode = ctxt->xpathCtxt->node;
-                       olddoc = ctxt->xpathCtxt->doc;
-                       ctxt->xpathCtxt->node = node;
-                       ctxt->xpathCtxt->doc = doc;
-                       newlist = xmlXPathEval(query, ctxt->xpathCtxt);
-                       ctxt->xpathCtxt->node = oldnode;
-                       ctxt->xpathCtxt->doc = olddoc;
-                       xmlFree(query);
-                       if (newlist == NULL)
-                           return(-1);
-                       if (newlist->type != XPATH_NODESET) {
-                           xmlXPathFreeObject(newlist);
-                           return(-1);
-                       }
-                       index = 0;
-
-                       if ((parent == NULL) || (node->doc == NULL))
-                           nocache = 1;
-                       else {
-                           if ((doc->name != NULL) &&
-                               (doc->name[0] == ' ') &&
-                               (xmlStrEqual(BAD_CAST doc->name, 
-                                            BAD_CAST " fake node libxslt")))
-                               nocache = 1;
-                       }
-                       
-                       if (nocache == 0) {
-                           if (list != NULL)
-                               xmlXPathFreeObject(list);
-                           list = newlist;
-
-                           XSLT_RUNTIME_EXTRA_LST(ctxt, select->lenExtra) =
-                               (void *) list;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra) =
-                               (void *) doc;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra) =
-                               0;
-                           XSLT_RUNTIME_EXTRA_FREE(ctxt, select->lenExtra) =
-                               (xmlFreeFunc) xmlXPathFreeObject;
-                       } else
-                           list = newlist;
-                   }
-                   if ((list->nodesetval == NULL) ||
-                       (list->nodesetval->nodeNr <= 0)) {
-                       if (nocache == 1)
-                           xmlXPathFreeObject(list);
-                       return(0);
-                   }
-                   /* TODO: store the index and use it for the scan */
-                   if (index == 0) {
-                       for (j = 0;j < list->nodesetval->nodeNr;j++) {
-                           if (list->nodesetval->nodeTab[j] == node) {
-                               if (nocache == 1)
-                                   xmlXPathFreeObject(list);
-                               return(1);
-                           }
-                       }
-                   } else {
+               if (comp->direct) {
+                   if (states.states != NULL) {
+                       /* Free the rollback states */
+                       xmlFree(states.states);
                    }
-                   if (nocache == 1)
-                       xmlXPathFreeObject(list);
-                   return(0);
+                   return(xsltTestCompMatchDirect(ctxt, comp, node));
                }
+
+               doc = node->doc;
+               if ((doc != NULL) &&
+                   (doc->name != NULL) &&
+                   (doc->name[0] == ' ') &&
+                   (xmlStrEqual(BAD_CAST doc->name,
+                                BAD_CAST " fake node libxslt")))
+                   isRVT = 1;
+               else
+                   isRVT = 0;
+
                /*
                 * Depending on the last selection, one may need to
                 * recompute contextSize and proximityPosition.
-                *
-                * TODO: make this thread safe !
                 */
                oldCS = ctxt->xpathCtxt->contextSize;
                oldCP = ctxt->xpathCtxt->proximityPosition;
-               if ((select != NULL) &&
-                   (select->op == XSLT_OP_ELEM) &&
-                   (select->value != NULL) &&
+               if ((sel != NULL) &&
+                   (sel->op == XSLT_OP_ELEM) &&
+                   (sel->value != NULL) &&
                    (node->type == XML_ELEMENT_NODE) &&
                    (node->parent != NULL)) {
                    xmlNodePtr previous;
-                   int index, nocache = 0;
+                   int ix, nocache = 0;
 
                    previous = (xmlNodePtr)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra);
-                   index = (int)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra);
+                       XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
+                   ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
                    if ((previous != NULL) &&
                        (previous->parent == node->parent)) {
                        /*
@@ -741,9 +866,9 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                                (sibling->name != NULL) &&
                                (previous->name[0] == sibling->name[0]) &&
                                (xmlStrEqual(previous->name, sibling->name))) {
-                               if ((select->value2 == NULL) ||
+                               if ((sel->value2 == NULL) ||
                                    ((sibling->ns != NULL) &&
-                                    (xmlStrEqual(select->value2,
+                                    (xmlStrEqual(sel->value2,
                                                  sibling->ns->href))))
                                    indx++;
                            }
@@ -756,29 +881,32 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                            while (sibling != NULL) {
                                if (sibling == previous)
                                    break;
-                               if ((select->value2 == NULL) ||
+                               if ((sel->value2 == NULL) ||
                                    ((sibling->ns != NULL) &&
-                                    (xmlStrEqual(select->value2,
+                                    (xmlStrEqual(sel->value2,
                                                  sibling->ns->href))))
                                    indx--;
                                sibling = sibling->next;
                            }
                        }
                        if (sibling != NULL) {
-                           pos = index + indx;
+                           pos = ix + indx;
                            /*
-                            * If the node is in a Value Tree we cannot
-                            * cache it !
+                            * If the node is in a Value Tree we need to
+                            * save len, but cannot cache the node!
+                            * (bugs 153137 and 158840)
                             */
                            if (node->doc != NULL) {
-                               len = (int)
-                                   XSLT_RUNTIME_EXTRA(ctxt, select->lenExtra);
-                               XSLT_RUNTIME_EXTRA(ctxt,
-                                       select->previousExtra) = node;
-                               XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra) =
-                                   (void *) pos;
+                               len = XSLT_RUNTIME_EXTRA(ctxt,
+                                       sel->lenExtra, ival);
+                               if (!isRVT) {
+                                   XSLT_RUNTIME_EXTRA(ctxt,
+                                       sel->previousExtra, ptr) = node;
+                                   XSLT_RUNTIME_EXTRA(ctxt,
+                                       sel->indexExtra, ival) = pos;
+                               }
                            }
-                           index = pos;
+                           ix = pos;
                        } else
                            pos = 0;
                    } else {
@@ -797,9 +925,9 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                                           (siblings->name != NULL) &&
                                    (node->name[0] == siblings->name[0]) &&
                                    (xmlStrEqual(node->name, siblings->name))) {
-                                   if ((select->value2 == NULL) ||
+                                   if ((sel->value2 == NULL) ||
                                        ((siblings->ns != NULL) &&
-                                        (xmlStrEqual(select->value2,
+                                        (xmlStrEqual(sel->value2,
                                                      siblings->ns->href))))
                                        len++;
                                }
@@ -824,24 +952,24 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                         * If the node is in a Value Tree we cannot
                         * cache it !
                         */
-                       if ((node->doc != NULL) && (nocache == 0)) {
-                           XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra) =
+                       if ((!isRVT) && (node->doc != NULL) &&
+                           (nocache == 0)) {
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
                                node;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra) =
-                               (void *) pos;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->lenExtra) =
-                               (void *) len;
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
+                               pos;
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
+                               len;
                        }
                    }
-               } else if ((select != NULL) && (select->op == XSLT_OP_ALL) &&
+               } else if ((sel != NULL) && (sel->op == XSLT_OP_ALL) &&
                           (node->type == XML_ELEMENT_NODE)) {
                    xmlNodePtr previous;
-                   int index, nocache = 0;
+                   int ix, nocache = 0;
 
                    previous = (xmlNodePtr)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra);
-                   index = (int)
-                       XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra);
+                       XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr);
+                   ix = XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival);
                    if ((previous != NULL) &&
                        (previous->parent == node->parent)) {
                        /*
@@ -870,18 +998,18 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                            }
                        }
                        if (sibling != NULL) {
-                           pos = index + indx;
+                           pos = ix + indx;
                            /*
                             * If the node is in a Value Tree we cannot
                             * cache it !
                             */
-                           if (node->doc != NULL) {
-                               len = (int)
-                                   XSLT_RUNTIME_EXTRA(ctxt, select->lenExtra);
+                           if ((node->doc != NULL) && !isRVT) {
+                               len = XSLT_RUNTIME_EXTRA(ctxt,
+                                       sel->lenExtra, ival);
                                XSLT_RUNTIME_EXTRA(ctxt,
-                                       select->previousExtra) = node;
-                               XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra) =
-                                   (void *) pos;
+                                       sel->previousExtra, ptr) = node;
+                               XSLT_RUNTIME_EXTRA(ctxt,
+                                       sel->indexExtra, ival) = pos;
                            }
                        } else
                            pos = 0;
@@ -919,13 +1047,13 @@ xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
                         * If the node is in a Value Tree we cannot
                         * cache it !
                         */
-                       if ((node->doc != NULL) && (nocache == 0)) {
-                           XSLT_RUNTIME_EXTRA(ctxt, select->previousExtra) =
+                       if ((node->doc != NULL) && (nocache == 0) && !isRVT) {
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->previousExtra, ptr) =
                                node;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->indexExtra) =
-                               (void *) pos;
-                           XSLT_RUNTIME_EXTRA(ctxt, select->lenExtra) =
-                               (void *) len;
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->indexExtra, ival) =
+                               pos;
+                           XSLT_RUNTIME_EXTRA(ctxt, sel->lenExtra, ival) =
+                               len;
                        }
                    }
                }
@@ -953,24 +1081,24 @@ wrong_index:
                    ctxt->xpathCtxt->proximityPosition = oldCP;
                }
                ctxt->node = oldNode;
-               return(0);
+               goto rollback;
            }
             case XSLT_OP_PI:
                if (node->type != XML_PI_NODE)
-                   return(0);
+                   goto rollback;
                if (step->value != NULL) {
                    if (!xmlStrEqual(step->value, node->name))
-                       return(0);
+                       goto rollback;
                }
                break;
             case XSLT_OP_COMMENT:
                if (node->type != XML_COMMENT_NODE)
-                   return(0);
+                   goto rollback;
                break;
             case XSLT_OP_TEXT:
                if ((node->type != XML_TEXT_NODE) &&
                    (node->type != XML_CDATA_SECTION_NODE))
-                   return(0);
+                   goto rollback;
                break;
             case XSLT_OP_NODE:
                switch (node->type) {
@@ -981,12 +1109,32 @@ wrong_index:
                    case XML_TEXT_NODE:
                        break;
                    default:
-                       return(0);
+                       goto rollback;
                }
                break;
        }
     }
+found:
+    if (states.states != NULL) {
+        /* Free the rollback states */
+       xmlFree(states.states);
+    }
     return(1);
+rollback:
+    /* got an error try to rollback */
+    if (states.states == NULL)
+       return(0);
+    if (states.nbstates <= 0) {
+       xmlFree(states.states);
+       return(0);
+    }
+    states.nbstates--;
+    i = states.states[states.nbstates].step;
+    node = states.states[states.nbstates].node;
+#if 0
+    fprintf(stderr, "Pop: %d, %s\n", i, node->name);
+#endif
+    goto restart;
 }
 
 /**
@@ -995,7 +1143,7 @@ wrong_index:
  * @node: a node
  * @comp: the precompiled pattern list
  *
- * Test wether the node matches one of the patterns in the list
+ * Test whether the node matches one of the patterns in the list
  *
  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
  */
@@ -1608,7 +1756,7 @@ xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
            PUSH(XSLT_OP_PARENT, NULL, NULL);
            NEXT;
            SKIP_BLANKS;
-           if ((CUR != 0) || (CUR == '|')) {
+           if ((CUR != 0) && (CUR != '|')) {
                xsltCompileRelativePathPattern(ctxt, NULL);
            }
        } else {
@@ -1652,7 +1800,7 @@ xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
        NEXT;
        SKIP_BLANKS;
        PUSH(XSLT_OP_ROOT, NULL, NULL);
-       if ((CUR != 0) || (CUR == '|')) {
+       if ((CUR != 0) && (CUR != '|')) {
            PUSH(XSLT_OP_PARENT, NULL, NULL);
            xsltCompileRelativePathPattern(ctxt, NULL);
        }
@@ -1901,9 +2049,9 @@ xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
        
        pat->template = cur;
        if (mode != NULL)
-           pat->mode = xmlStrdup(mode);
+           pat->mode = xmlDictLookup(style->dict, mode, -1);
        if (modeURI != NULL)
-           pat->modeURI = xmlStrdup(modeURI);
+           pat->modeURI = xmlDictLookup(style->dict, modeURI, -1);
        if (priority != XSLT_PAT_NO_PRIORITY)
            pat->priority = priority;
 
@@ -2057,6 +2205,7 @@ xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
     const xmlChar *name = NULL;
     xsltCompMatchPtr list = NULL;
     float priority;
+    int keyed = 0;
 
     if ((ctxt == NULL) || (node == NULL))
        return(NULL);
@@ -2107,7 +2256,7 @@ xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
        }
        if (name != NULL) {
            /*
-            * find the list of appliable expressions based on the name
+            * find the list of applicable expressions based on the name
             */
            list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
                                             name, ctxt->mode, ctxt->modeURI);
@@ -2133,23 +2282,37 @@ xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
                    list = curstyle->rootMatch;
                else
                    list = curstyle->elemMatch;
+               if (node->psvi != NULL) keyed = 1;
                break;
-           case XML_ATTRIBUTE_NODE:
+           case XML_ATTRIBUTE_NODE: {
+               xmlAttrPtr attr;
+
                list = curstyle->attrMatch;
+               attr = (xmlAttrPtr) node;
+               if (attr->psvi != NULL) keyed = 1;
                break;
+           }
            case XML_PI_NODE:
                list = curstyle->piMatch;
+               if (node->psvi != NULL) keyed = 1;
                break;
            case XML_DOCUMENT_NODE:
-           case XML_HTML_DOCUMENT_NODE:
+           case XML_HTML_DOCUMENT_NODE: {
+               xmlDocPtr doc;
+
                list = curstyle->rootMatch;
+               doc = (xmlDocPtr) node;
+               if (doc->psvi != NULL) keyed = 1;
                break;
+           }
            case XML_TEXT_NODE:
            case XML_CDATA_SECTION_NODE:
                list = curstyle->textMatch;
+               if (node->psvi != NULL) keyed = 1;
                break;
            case XML_COMMENT_NODE:
                list = curstyle->commentMatch;
+               if (node->psvi != NULL) keyed = 1;
                break;
            case XML_ENTITY_REF_NODE:
            case XML_ENTITY_NODE:
@@ -2166,7 +2329,6 @@ xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
                break;
            default:
                break;
-
        }
        while ((list != NULL) &&
               ((ret == NULL)  || (list->priority > priority))) {
@@ -2210,7 +2372,7 @@ xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
            }
        }
 
-       if (node->_private != NULL) {
+       if (keyed) {
            list = curstyle->keyMatch;
            while ((list != NULL) &&
                   ((ret == NULL)  || (list->priority > priority))) {