1 /*
   2  * pattern.c: Implemetation of selectors for nodes
   3  *
   4  * Reference:
   5  *   http://www.w3.org/TR/2001/REC-xmlschema-1-20010502/
   6  *   to some extent
   7  *   http://www.w3.org/TR/1999/REC-xml-19991116
   8  *
   9  * See Copyright for the status of this software.
  10  *
  11  * daniel@veillard.com
  12  */
  13 
  14 /*
  15  * TODO:
  16  * - compilation flags to check for specific syntaxes
  17  *   using flags of xmlPatterncompile()
  18  * - making clear how pattern starting with / or . need to be handled,
  19  *   currently push(NULL, NULL) means a reset of the streaming context
  20  *   and indicating we are on / (the document node), probably need
  21  *   something similar for .
  22  * - get rid of the "compile" starting with lowercase
  23  * - DONE (2006-05-16): get rid of the Strdup/Strndup in case of dictionary
  24  */
  25 
  26 #define IN_LIBXML
  27 #include "libxml.h"
  28 
  29 #include <string.h>
  30 #include <libxml/xmlmemory.h>
  31 #include <libxml/tree.h>
  32 #include <libxml/hash.h>
  33 #include <libxml/dict.h>
  34 #include <libxml/xmlerror.h>
  35 #include <libxml/parserInternals.h>
  36 #include <libxml/pattern.h>
  37 
  38 #ifdef LIBXML_PATTERN_ENABLED
  39 
  40 /* #define DEBUG_STREAMING */
  41 
  42 #define ERROR(a, b, c, d)
  43 #define ERROR5(a, b, c, d, e)
  44 
  45 #define XML_STREAM_STEP_DESC    1
  46 #define XML_STREAM_STEP_FINAL   2
  47 #define XML_STREAM_STEP_ROOT    4
  48 #define XML_STREAM_STEP_ATTR    8
  49 #define XML_STREAM_STEP_NODE    16
  50 #define XML_STREAM_STEP_IN_SET  32
  51 
  52 /*
  53 * NOTE: Those private flags (XML_STREAM_xxx) are used
  54 *   in _xmlStreamCtxt->flag. They extend the public
  55 *   xmlPatternFlags, so be carefull not to interfere with the
  56 *   reserved values for xmlPatternFlags.
  57 */
  58 #define XML_STREAM_FINAL_IS_ANY_NODE 1<<14
  59 #define XML_STREAM_FROM_ROOT 1<<15
  60 #define XML_STREAM_DESC 1<<16
  61 
  62 /*
  63 * XML_STREAM_ANY_NODE is used for comparison against
  64 * xmlElementType enums, to indicate a node of any type.
  65 */
  66 #define XML_STREAM_ANY_NODE 100
  67 
  68 #define XML_PATTERN_NOTPATTERN  (XML_PATTERN_XPATH | \
  69                  XML_PATTERN_XSSEL | \
  70                  XML_PATTERN_XSFIELD)
  71 
  72 #define XML_STREAM_XS_IDC(c) ((c)->flags & \
  73     (XML_PATTERN_XSSEL | XML_PATTERN_XSFIELD))
  74 
  75 #define XML_STREAM_XS_IDC_SEL(c) ((c)->flags & XML_PATTERN_XSSEL)
  76 
  77 #define XML_STREAM_XS_IDC_FIELD(c) ((c)->flags & XML_PATTERN_XSFIELD)
  78 
  79 #define XML_PAT_COPY_NSNAME(c, r, nsname) \
  80     if ((c)->comp->dict) \
  81     r = (xmlChar *) xmlDictLookup((c)->comp->dict, BAD_CAST nsname, -1); \
  82     else r = xmlStrdup(BAD_CAST nsname);
  83 
  84 #define XML_PAT_FREE_STRING(c, r) if ((c)->comp->dict == NULL) xmlFree(r);
  85 
  86 typedef struct _xmlStreamStep xmlStreamStep;
  87 typedef xmlStreamStep *xmlStreamStepPtr;
  88 struct _xmlStreamStep {
  89     int flags;          /* properties of that step */
  90     const xmlChar *name;    /* first string value if NULL accept all */
  91     const xmlChar *ns;      /* second string value */
  92     int nodeType;       /* type of node */
  93 };
  94 
  95 typedef struct _xmlStreamComp xmlStreamComp;
  96 typedef xmlStreamComp *xmlStreamCompPtr;
  97 struct _xmlStreamComp {
  98     xmlDict *dict;      /* the dictionary if any */
  99     int nbStep;         /* number of steps in the automata */
 100     int maxStep;        /* allocated number of steps */
 101     xmlStreamStepPtr steps; /* the array of steps */
 102     int flags;
 103 };
 104 
 105 struct _xmlStreamCtxt {
 106     struct _xmlStreamCtxt *next;/* link to next sub pattern if | */
 107     xmlStreamCompPtr comp;  /* the compiled stream */
 108     int nbState;        /* number of states in the automata */
 109     int maxState;       /* allocated number of states */
 110     int level;          /* how deep are we ? */
 111     int *states;        /* the array of step indexes */
 112     int flags;          /* validation options */
 113     int blockLevel;
 114 };
 115 
 116 static void xmlFreeStreamComp(xmlStreamCompPtr comp);
 117 
 118 /*
 119  * Types are private:
 120  */
 121 
 122 typedef enum {
 123     XML_OP_END=0,
 124     XML_OP_ROOT,
 125     XML_OP_ELEM,
 126     XML_OP_CHILD,
 127     XML_OP_ATTR,
 128     XML_OP_PARENT,
 129     XML_OP_ANCESTOR,
 130     XML_OP_NS,
 131     XML_OP_ALL
 132 } xmlPatOp;
 133 
 134 
 135 typedef struct _xmlStepState xmlStepState;
 136 typedef xmlStepState *xmlStepStatePtr;
 137 struct _xmlStepState {
 138     int step;
 139     xmlNodePtr node;
 140 };
 141 
 142 typedef struct _xmlStepStates xmlStepStates;
 143 typedef xmlStepStates *xmlStepStatesPtr;
 144 struct _xmlStepStates {
 145     int nbstates;
 146     int maxstates;
 147     xmlStepStatePtr states;
 148 };
 149 
 150 typedef struct _xmlStepOp xmlStepOp;
 151 typedef xmlStepOp *xmlStepOpPtr;
 152 struct _xmlStepOp {
 153     xmlPatOp op;
 154     const xmlChar *value;
 155     const xmlChar *value2; /* The namespace name */
 156 };
 157 
 158 #define PAT_FROM_ROOT   (1<<8)
 159 #define PAT_FROM_CUR    (1<<9)
 160 
 161 struct _xmlPattern {
 162     void *data;         /* the associated template */
 163     xmlDictPtr dict;        /* the optional dictionary */
 164     struct _xmlPattern *next;   /* next pattern if | is used */
 165     const xmlChar *pattern; /* the pattern */
 166     int flags;          /* flags */
 167     int nbStep;
 168     int maxStep;
 169     xmlStepOpPtr steps;        /* ops for computation */
 170     xmlStreamCompPtr stream;    /* the streaming data if any */
 171 };
 172 
 173 typedef struct _xmlPatParserContext xmlPatParserContext;
 174 typedef xmlPatParserContext *xmlPatParserContextPtr;
 175 struct _xmlPatParserContext {
 176     const xmlChar *cur;         /* the current char being parsed */
 177     const xmlChar *base;        /* the full expression */
 178     int            error;       /* error code */
 179     xmlDictPtr     dict;        /* the dictionary if any */
 180     xmlPatternPtr  comp;        /* the result */
 181     xmlNodePtr     elem;        /* the current node if any */
 182     const xmlChar **namespaces;     /* the namespaces definitions */
 183     int   nb_namespaces;        /* the number of namespaces */
 184 };
 185 
 186 /************************************************************************
 187  *                                  *
 188  *          Type functions                  *
 189  *                                  *
 190  ************************************************************************/
 191 
 192 /**
 193  * xmlNewPattern:
 194  *
 195  * Create a new XSLT Pattern
 196  *
 197  * Returns the newly allocated xmlPatternPtr or NULL in case of error
 198  */
 199 static xmlPatternPtr
 200 xmlNewPattern(void) {
 201     xmlPatternPtr cur;
 202 
 203     cur = (xmlPatternPtr) xmlMalloc(sizeof(xmlPattern));
 204     if (cur == NULL) {
 205     ERROR(NULL, NULL, NULL,
 206         "xmlNewPattern : malloc failed\n");
 207     return(NULL);
 208     }
 209     memset(cur, 0, sizeof(xmlPattern));
 210     cur->maxStep = 10;
 211     cur->steps = (xmlStepOpPtr) xmlMalloc(cur->maxStep * sizeof(xmlStepOp));
 212     if (cur->steps == NULL) {
 213         xmlFree(cur);
 214     ERROR(NULL, NULL, NULL,
 215         "xmlNewPattern : malloc failed\n");
 216     return(NULL);
 217     }
 218     return(cur);
 219 }
 220 
 221 /**
 222  * xmlFreePattern:
 223  * @comp:  an XSLT comp
 224  *
 225  * Free up the memory allocated by @comp
 226  */
 227 void
 228 xmlFreePattern(xmlPatternPtr comp) {
 229     xmlStepOpPtr op;
 230     int i;
 231 
 232     if (comp == NULL)
 233     return;
 234     if (comp->next != NULL)
 235         xmlFreePattern(comp->next);
 236     if (comp->stream != NULL)
 237         xmlFreeStreamComp(comp->stream);
 238     if (comp->pattern != NULL)
 239     xmlFree((xmlChar *)comp->pattern);
 240     if (comp->steps != NULL) {
 241         if (comp->dict == NULL) {
 242         for (i = 0;i < comp->nbStep;i++) {
 243         op = &comp->steps[i];
 244         if (op->value != NULL)
 245             xmlFree((xmlChar *) op->value);
 246         if (op->value2 != NULL)
 247             xmlFree((xmlChar *) op->value2);
 248         }
 249     }
 250     xmlFree(comp->steps);
 251     }
 252     if (comp->dict != NULL)
 253         xmlDictFree(comp->dict);
 254 
 255     memset(comp, -1, sizeof(xmlPattern));
 256     xmlFree(comp);
 257 }
 258 
 259 /**
 260  * xmlFreePatternList:
 261  * @comp:  an XSLT comp list
 262  *
 263  * Free up the memory allocated by all the elements of @comp
 264  */
 265 void
 266 xmlFreePatternList(xmlPatternPtr comp) {
 267     xmlPatternPtr cur;
 268 
 269     while (comp != NULL) {
 270     cur = comp;
 271     comp = comp->next;
 272     cur->next = NULL;
 273     xmlFreePattern(cur);
 274     }
 275 }
 276 
 277 /**
 278  * xmlNewPatParserContext:
 279  * @pattern:  the pattern context
 280  * @dict:  the inherited dictionary or NULL
 281  * @namespaces: the prefix definitions, array of [URI, prefix] terminated
 282  *              with [NULL, NULL] or NULL if no namespace is used
 283  *
 284  * Create a new XML pattern parser context
 285  *
 286  * Returns the newly allocated xmlPatParserContextPtr or NULL in case of error
 287  */
 288 static xmlPatParserContextPtr
 289 xmlNewPatParserContext(const xmlChar *pattern, xmlDictPtr dict,
 290                        const xmlChar **namespaces) {
 291     xmlPatParserContextPtr cur;
 292 
 293     if (pattern == NULL)
 294         return(NULL);
 295 
 296     cur = (xmlPatParserContextPtr) xmlMalloc(sizeof(xmlPatParserContext));
 297     if (cur == NULL) {
 298     ERROR(NULL, NULL, NULL,
 299         "xmlNewPatParserContext : malloc failed\n");
 300     return(NULL);
 301     }
 302     memset(cur, 0, sizeof(xmlPatParserContext));
 303     cur->dict = dict;
 304     cur->cur = pattern;
 305     cur->base = pattern;
 306     if (namespaces != NULL) {
 307         int i;
 308     for (i = 0;namespaces[2 * i] != NULL;i++);
 309         cur->nb_namespaces = i;
 310     } else {
 311         cur->nb_namespaces = 0;
 312     }
 313     cur->namespaces = namespaces;
 314     return(cur);
 315 }
 316 
 317 /**
 318  * xmlFreePatParserContext:
 319  * @ctxt:  an XSLT parser context
 320  *
 321  * Free up the memory allocated by @ctxt
 322  */
 323 static void
 324 xmlFreePatParserContext(xmlPatParserContextPtr ctxt) {
 325     if (ctxt == NULL)
 326     return;
 327     memset(ctxt, -1, sizeof(xmlPatParserContext));
 328     xmlFree(ctxt);
 329 }
 330 
 331 /**
 332  * xmlPatternAdd:
 333  * @comp:  the compiled match expression
 334  * @op:  an op
 335  * @value:  the first value
 336  * @value2:  the second value
 337  *
 338  * Add a step to an XSLT Compiled Match
 339  *
 340  * Returns -1 in case of failure, 0 otherwise.
 341  */
 342 static int
 343 xmlPatternAdd(xmlPatParserContextPtr ctxt ATTRIBUTE_UNUSED,
 344                 xmlPatternPtr comp,
 345                 xmlPatOp op, xmlChar * value, xmlChar * value2)
 346 {
 347     if (comp->nbStep >= comp->maxStep) {
 348         xmlStepOpPtr temp;
 349     temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
 350                                      sizeof(xmlStepOp));
 351         if (temp == NULL) {
 352         ERROR(ctxt, NULL, NULL,
 353                  "xmlPatternAdd: realloc failed\n");
 354         return (-1);
 355     }
 356     comp->steps = temp;
 357     comp->maxStep *= 2;
 358     }
 359     comp->steps[comp->nbStep].op = op;
 360     comp->steps[comp->nbStep].value = value;
 361     comp->steps[comp->nbStep].value2 = value2;
 362     comp->nbStep++;
 363     return (0);
 364 }
 365 
 366 #if 0
 367 /**
 368  * xsltSwapTopPattern:
 369  * @comp:  the compiled match expression
 370  *
 371  * reverse the two top steps.
 372  */
 373 static void
 374 xsltSwapTopPattern(xmlPatternPtr comp) {
 375     int i;
 376     int j = comp->nbStep - 1;
 377 
 378     if (j > 0) {
 379     register const xmlChar *tmp;
 380     register xmlPatOp op;
 381     i = j - 1;
 382     tmp = comp->steps[i].value;
 383     comp->steps[i].value = comp->steps[j].value;
 384     comp->steps[j].value = tmp;
 385     tmp = comp->steps[i].value2;
 386     comp->steps[i].value2 = comp->steps[j].value2;
 387     comp->steps[j].value2 = tmp;
 388     op = comp->steps[i].op;
 389     comp->steps[i].op = comp->steps[j].op;
 390     comp->steps[j].op = op;
 391     }
 392 }
 393 #endif
 394 
 395 /**
 396  * xmlReversePattern:
 397  * @comp:  the compiled match expression
 398  *
 399  * reverse all the stack of expressions
 400  *
 401  * returns 0 in case of success and -1 in case of error.
 402  */
 403 static int
 404 xmlReversePattern(xmlPatternPtr comp) {
 405     int i, j;
 406 
 407     /*
 408      * remove the leading // for //a or .//a
 409      */
 410     if ((comp->nbStep > 0) && (comp->steps[0].op == XML_OP_ANCESTOR)) {
 411         for (i = 0, j = 1;j < comp->nbStep;i++,j++) {
 412         comp->steps[i].value = comp->steps[j].value;
 413         comp->steps[i].value2 = comp->steps[j].value2;
 414         comp->steps[i].op = comp->steps[j].op;
 415     }
 416     comp->nbStep--;
 417     }
 418     if (comp->nbStep >= comp->maxStep) {
 419         xmlStepOpPtr temp;
 420     temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
 421                                      sizeof(xmlStepOp));
 422         if (temp == NULL) {
 423         ERROR(ctxt, NULL, NULL,
 424                  "xmlReversePattern: realloc failed\n");
 425         return (-1);
 426     }
 427     comp->steps = temp;
 428     comp->maxStep *= 2;
 429     }
 430     i = 0;
 431     j = comp->nbStep - 1;
 432     while (j > i) {
 433     register const xmlChar *tmp;
 434     register xmlPatOp op;
 435     tmp = comp->steps[i].value;
 436     comp->steps[i].value = comp->steps[j].value;
 437     comp->steps[j].value = tmp;
 438     tmp = comp->steps[i].value2;
 439     comp->steps[i].value2 = comp->steps[j].value2;
 440     comp->steps[j].value2 = tmp;
 441     op = comp->steps[i].op;
 442     comp->steps[i].op = comp->steps[j].op;
 443     comp->steps[j].op = op;
 444     j--;
 445     i++;
 446     }
 447     comp->steps[comp->nbStep].value = NULL;
 448     comp->steps[comp->nbStep].value2 = NULL;
 449     comp->steps[comp->nbStep++].op = XML_OP_END;
 450     return(0);
 451 }
 452 
 453 /************************************************************************
 454  *                                  *
 455  *      The interpreter for the precompiled patterns        *
 456  *                                  *
 457  ************************************************************************/
 458 
 459 static int
 460 xmlPatPushState(xmlStepStates *states, int step, xmlNodePtr node) {
 461     if ((states->states == NULL) || (states->maxstates <= 0)) {
 462         states->maxstates = 4;
 463     states->nbstates = 0;
 464     states->states = xmlMalloc(4 * sizeof(xmlStepState));
 465     }
 466     else if (states->maxstates <= states->nbstates) {
 467         xmlStepState *tmp;
 468 
 469     tmp = (xmlStepStatePtr) xmlRealloc(states->states,
 470                    2 * states->maxstates * sizeof(xmlStepState));
 471     if (tmp == NULL)
 472         return(-1);
 473     states->states = tmp;
 474     states->maxstates *= 2;
 475     }
 476     states->states[states->nbstates].step = step;
 477     states->states[states->nbstates++].node = node;
 478 #if 0
 479     fprintf(stderr, "Push: %d, %s\n", step, node->name);
 480 #endif
 481     return(0);
 482 }
 483 
 484 /**
 485  * xmlPatMatch:
 486  * @comp: the precompiled pattern
 487  * @node: a node
 488  *
 489  * Test whether the node matches the pattern
 490  *
 491  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
 492  */
 493 static int
 494 xmlPatMatch(xmlPatternPtr comp, xmlNodePtr node) {
 495     int i;
 496     xmlStepOpPtr step;
 497     xmlStepStates states = {0, 0, NULL}; /* // may require backtrack */
 498 
 499     if ((comp == NULL) || (node == NULL)) return(-1);
 500     i = 0;
 501 restart:
 502     for (;i < comp->nbStep;i++) {
 503     step = &comp->steps[i];
 504     switch (step->op) {
 505             case XML_OP_END:
 506         goto found;
 507             case XML_OP_ROOT:
 508         if (node->type == XML_NAMESPACE_DECL)
 509             goto rollback;
 510         node = node->parent;
 511         if ((node->type == XML_DOCUMENT_NODE) ||
 512 #ifdef LIBXML_DOCB_ENABLED
 513             (node->type == XML_DOCB_DOCUMENT_NODE) ||
 514 #endif
 515             (node->type == XML_HTML_DOCUMENT_NODE))
 516             continue;
 517         goto rollback;
 518             case XML_OP_ELEM:
 519         if (node->type != XML_ELEMENT_NODE)
 520             goto rollback;
 521         if (step->value == NULL)
 522             continue;
 523         if (step->value[0] != node->name[0])
 524             goto rollback;
 525         if (!xmlStrEqual(step->value, node->name))
 526             goto rollback;
 527 
 528         /* Namespace test */
 529         if (node->ns == NULL) {
 530             if (step->value2 != NULL)
 531             goto rollback;
 532         } else if (node->ns->href != NULL) {
 533             if (step->value2 == NULL)
 534             goto rollback;
 535             if (!xmlStrEqual(step->value2, node->ns->href))
 536             goto rollback;
 537         }
 538         continue;
 539             case XML_OP_CHILD: {
 540         xmlNodePtr lst;
 541 
 542         if ((node->type != XML_ELEMENT_NODE) &&
 543             (node->type != XML_DOCUMENT_NODE) &&
 544 #ifdef LIBXML_DOCB_ENABLED
 545             (node->type != XML_DOCB_DOCUMENT_NODE) &&
 546 #endif
 547             (node->type != XML_HTML_DOCUMENT_NODE))
 548             goto rollback;
 549 
 550         lst = node->children;
 551 
 552         if (step->value != NULL) {
 553             while (lst != NULL) {
 554             if ((lst->type == XML_ELEMENT_NODE) &&
 555                 (step->value[0] == lst->name[0]) &&
 556                 (xmlStrEqual(step->value, lst->name)))
 557                 break;
 558             lst = lst->next;
 559             }
 560             if (lst != NULL)
 561             continue;
 562         }
 563         goto rollback;
 564         }
 565             case XML_OP_ATTR:
 566         if (node->type != XML_ATTRIBUTE_NODE)
 567             goto rollback;
 568         if (step->value != NULL) {
 569             if (step->value[0] != node->name[0])
 570             goto rollback;
 571             if (!xmlStrEqual(step->value, node->name))
 572             goto rollback;
 573         }
 574         /* Namespace test */
 575         if (node->ns == NULL) {
 576             if (step->value2 != NULL)
 577             goto rollback;
 578         } else if (step->value2 != NULL) {
 579             if (!xmlStrEqual(step->value2, node->ns->href))
 580             goto rollback;
 581         }
 582         continue;
 583             case XML_OP_PARENT:
 584         if ((node->type == XML_DOCUMENT_NODE) ||
 585             (node->type == XML_HTML_DOCUMENT_NODE) ||
 586 #ifdef LIBXML_DOCB_ENABLED
 587             (node->type == XML_DOCB_DOCUMENT_NODE) ||
 588 #endif
 589             (node->type == XML_NAMESPACE_DECL))
 590             goto rollback;
 591         node = node->parent;
 592         if (node == NULL)
 593             goto rollback;
 594         if (step->value == NULL)
 595             continue;
 596         if (step->value[0] != node->name[0])
 597             goto rollback;
 598         if (!xmlStrEqual(step->value, node->name))
 599             goto rollback;
 600         /* Namespace test */
 601         if (node->ns == NULL) {
 602             if (step->value2 != NULL)
 603             goto rollback;
 604         } else if (node->ns->href != NULL) {
 605             if (step->value2 == NULL)
 606             goto rollback;
 607             if (!xmlStrEqual(step->value2, node->ns->href))
 608             goto rollback;
 609         }
 610         continue;
 611             case XML_OP_ANCESTOR:
 612         /* TODO: implement coalescing of ANCESTOR/NODE ops */
 613         if (step->value == NULL) {
 614             i++;
 615             step = &comp->steps[i];
 616             if (step->op == XML_OP_ROOT)
 617             goto found;
 618             if (step->op != XML_OP_ELEM)
 619             goto rollback;
 620             if (step->value == NULL)
 621             return(-1);
 622         }
 623         if (node == NULL)
 624             goto rollback;
 625         if ((node->type == XML_DOCUMENT_NODE) ||
 626             (node->type == XML_HTML_DOCUMENT_NODE) ||
 627 #ifdef LIBXML_DOCB_ENABLED
 628             (node->type == XML_DOCB_DOCUMENT_NODE) ||
 629 #endif
 630             (node->type == XML_NAMESPACE_DECL))
 631             goto rollback;
 632         node = node->parent;
 633         while (node != NULL) {
 634             if ((node->type == XML_ELEMENT_NODE) &&
 635             (step->value[0] == node->name[0]) &&
 636             (xmlStrEqual(step->value, node->name))) {
 637             /* Namespace test */
 638             if (node->ns == NULL) {
 639                 if (step->value2 == NULL)
 640                 break;
 641             } else if (node->ns->href != NULL) {
 642                 if ((step->value2 != NULL) &&
 643                     (xmlStrEqual(step->value2, node->ns->href)))
 644                 break;
 645             }
 646             }
 647             node = node->parent;
 648         }
 649         if (node == NULL)
 650             goto rollback;
 651         /*
 652          * prepare a potential rollback from here
 653          * for ancestors of that node.
 654          */
 655         if (step->op == XML_OP_ANCESTOR)
 656             xmlPatPushState(&states, i, node);
 657         else
 658             xmlPatPushState(&states, i - 1, node);
 659         continue;
 660             case XML_OP_NS:
 661         if (node->type != XML_ELEMENT_NODE)
 662             goto rollback;
 663         if (node->ns == NULL) {
 664             if (step->value != NULL)
 665             goto rollback;
 666         } else if (node->ns->href != NULL) {
 667             if (step->value == NULL)
 668             goto rollback;
 669             if (!xmlStrEqual(step->value, node->ns->href))
 670             goto rollback;
 671         }
 672         break;
 673             case XML_OP_ALL:
 674         if (node->type != XML_ELEMENT_NODE)
 675             goto rollback;
 676         break;
 677     }
 678     }
 679 found:
 680     if (states.states != NULL) {
 681         /* Free the rollback states */
 682     xmlFree(states.states);
 683     }
 684     return(1);
 685 rollback:
 686     /* got an error try to rollback */
 687     if (states.states == NULL)
 688     return(0);
 689     if (states.nbstates <= 0) {
 690     xmlFree(states.states);
 691     return(0);
 692     }
 693     states.nbstates--;
 694     i = states.states[states.nbstates].step;
 695     node = states.states[states.nbstates].node;
 696 #if 0
 697     fprintf(stderr, "Pop: %d, %s\n", i, node->name);
 698 #endif
 699     goto restart;
 700 }
 701 
 702 /************************************************************************
 703  *                                  *
 704  *          Dedicated parser for templates          *
 705  *                                  *
 706  ************************************************************************/
 707 
 708 #define TODO                                \
 709     xmlGenericError(xmlGenericErrorContext,             \
 710         "Unimplemented block at %s:%d\n",               \
 711             __FILE__, __LINE__);
 712 #define CUR (*ctxt->cur)
 713 #define SKIP(val) ctxt->cur += (val)
 714 #define NXT(val) ctxt->cur[(val)]
 715 #define PEEKPREV(val) ctxt->cur[-(val)]
 716 #define CUR_PTR ctxt->cur
 717 
 718 #define SKIP_BLANKS                             \
 719     while (IS_BLANK_CH(CUR)) NEXT
 720 
 721 #define CURRENT (*ctxt->cur)
 722 #define NEXT ((*ctxt->cur) ?  ctxt->cur++: ctxt->cur)
 723 
 724 
 725 #define PUSH(op, val, val2)                         \
 726     if (xmlPatternAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
 727 
 728 #define XSLT_ERROR(X)                           \
 729     { xsltError(ctxt, __FILE__, __LINE__, X);               \
 730       ctxt->error = (X); return; }
 731 
 732 #define XSLT_ERROR0(X)                          \
 733     { xsltError(ctxt, __FILE__, __LINE__, X);               \
 734       ctxt->error = (X); return(0); }
 735 
 736 #if 0
 737 /**
 738  * xmlPatScanLiteral:
 739  * @ctxt:  the XPath Parser context
 740  *
 741  * Parse an XPath Litteral:
 742  *
 743  * [29] Literal ::= '"' [^"]* '"'
 744  *                | "'" [^']* "'"
 745  *
 746  * Returns the Literal parsed or NULL
 747  */
 748 
 749 static xmlChar *
 750 xmlPatScanLiteral(xmlPatParserContextPtr ctxt) {
 751     const xmlChar *q, *cur;
 752     xmlChar *ret = NULL;
 753     int val, len;
 754 
 755     SKIP_BLANKS;
 756     if (CUR == '"') {
 757         NEXT;
 758     cur = q = CUR_PTR;
 759     val = xmlStringCurrentChar(NULL, cur, &len);
 760     while ((IS_CHAR(val)) && (val != '"')) {
 761         cur += len;
 762         val = xmlStringCurrentChar(NULL, cur, &len);
 763     }
 764     if (!IS_CHAR(val)) {
 765         ctxt->error = 1;
 766         return(NULL);
 767     } else {
 768         if (ctxt->dict)
 769         ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
 770         else
 771         ret = xmlStrndup(q, cur - q);
 772         }
 773     cur += len;
 774     CUR_PTR = cur;
 775     } else if (CUR == '\'') {
 776         NEXT;
 777     cur = q = CUR_PTR;
 778     val = xmlStringCurrentChar(NULL, cur, &len);
 779     while ((IS_CHAR(val)) && (val != '\'')) {
 780         cur += len;
 781         val = xmlStringCurrentChar(NULL, cur, &len);
 782     }
 783     if (!IS_CHAR(val)) {
 784         ctxt->error = 1;
 785         return(NULL);
 786     } else {
 787         if (ctxt->dict)
 788         ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
 789         else
 790         ret = xmlStrndup(q, cur - q);
 791         }
 792     cur += len;
 793     CUR_PTR = cur;
 794     } else {
 795     /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
 796     ctxt->error = 1;
 797     return(NULL);
 798     }
 799     return(ret);
 800 }
 801 #endif
 802 
 803 /**
 804  * xmlPatScanName:
 805  * @ctxt:  the XPath Parser context
 806  *
 807  * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' |
 808  *                  CombiningChar | Extender
 809  *
 810  * [5] Name ::= (Letter | '_' | ':') (NameChar)*
 811  *
 812  * [6] Names ::= Name (S Name)*
 813  *
 814  * Returns the Name parsed or NULL
 815  */
 816 
 817 static xmlChar *
 818 xmlPatScanName(xmlPatParserContextPtr ctxt) {
 819     const xmlChar *q, *cur;
 820     xmlChar *ret = NULL;
 821     int val, len;
 822 
 823     SKIP_BLANKS;
 824 
 825     cur = q = CUR_PTR;
 826     val = xmlStringCurrentChar(NULL, cur, &len);
 827     if (!IS_LETTER(val) && (val != '_') && (val != ':'))
 828     return(NULL);
 829 
 830     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
 831            (val == '.') || (val == '-') ||
 832        (val == '_') ||
 833        (IS_COMBINING(val)) ||
 834        (IS_EXTENDER(val))) {
 835     cur += len;
 836     val = xmlStringCurrentChar(NULL, cur, &len);
 837     }
 838     if (ctxt->dict)
 839     ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
 840     else
 841     ret = xmlStrndup(q, cur - q);
 842     CUR_PTR = cur;
 843     return(ret);
 844 }
 845 
 846 /**
 847  * xmlPatScanNCName:
 848  * @ctxt:  the XPath Parser context
 849  *
 850  * Parses a non qualified name
 851  *
 852  * Returns the Name parsed or NULL
 853  */
 854 
 855 static xmlChar *
 856 xmlPatScanNCName(xmlPatParserContextPtr ctxt) {
 857     const xmlChar *q, *cur;
 858     xmlChar *ret = NULL;
 859     int val, len;
 860 
 861     SKIP_BLANKS;
 862 
 863     cur = q = CUR_PTR;
 864     val = xmlStringCurrentChar(NULL, cur, &len);
 865     if (!IS_LETTER(val) && (val != '_'))
 866     return(NULL);
 867 
 868     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
 869            (val == '.') || (val == '-') ||
 870        (val == '_') ||
 871        (IS_COMBINING(val)) ||
 872        (IS_EXTENDER(val))) {
 873     cur += len;
 874     val = xmlStringCurrentChar(NULL, cur, &len);
 875     }
 876     if (ctxt->dict)
 877     ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
 878     else
 879     ret = xmlStrndup(q, cur - q);
 880     CUR_PTR = cur;
 881     return(ret);
 882 }
 883 
 884 #if 0
 885 /**
 886  * xmlPatScanQName:
 887  * @ctxt:  the XPath Parser context
 888  * @prefix:  the place to store the prefix
 889  *
 890  * Parse a qualified name
 891  *
 892  * Returns the Name parsed or NULL
 893  */
 894 
 895 static xmlChar *
 896 xmlPatScanQName(xmlPatParserContextPtr ctxt, xmlChar **prefix) {
 897     xmlChar *ret = NULL;
 898 
 899     *prefix = NULL;
 900     ret = xmlPatScanNCName(ctxt);
 901     if (CUR == ':') {
 902         *prefix = ret;
 903     NEXT;
 904     ret = xmlPatScanNCName(ctxt);
 905     }
 906     return(ret);
 907 }
 908 #endif
 909 
 910 /**
 911  * xmlCompileAttributeTest:
 912  * @ctxt:  the compilation context
 913  *
 914  * Compile an attribute test.
 915  */
 916 static void
 917 xmlCompileAttributeTest(xmlPatParserContextPtr ctxt) {
 918     xmlChar *token = NULL;
 919     xmlChar *name = NULL;
 920     xmlChar *URL = NULL;
 921 
 922     SKIP_BLANKS;
 923     name = xmlPatScanNCName(ctxt);
 924     if (name == NULL) {
 925     if (CUR == '*') {
 926         PUSH(XML_OP_ATTR, NULL, NULL);
 927         NEXT;
 928     } else {
 929         ERROR(NULL, NULL, NULL,
 930         "xmlCompileAttributeTest : Name expected\n");
 931         ctxt->error = 1;
 932     }
 933     return;
 934     }
 935     if (CUR == ':') {
 936     int i;
 937     xmlChar *prefix = name;
 938 
 939     NEXT;
 940 
 941     if (IS_BLANK_CH(CUR)) {
 942         ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
 943         XML_PAT_FREE_STRING(ctxt, prefix);
 944         ctxt->error = 1;
 945         goto error;
 946     }
 947     /*
 948     * This is a namespace match
 949     */
 950     token = xmlPatScanName(ctxt);
 951     if ((prefix[0] == 'x') &&
 952         (prefix[1] == 'm') &&
 953         (prefix[2] == 'l') &&
 954         (prefix[3] == 0))
 955     {
 956         XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE);
 957     } else {
 958         for (i = 0;i < ctxt->nb_namespaces;i++) {
 959         if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
 960             XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
 961             break;
 962         }
 963         }
 964         if (i >= ctxt->nb_namespaces) {
 965         ERROR5(NULL, NULL, NULL,
 966             "xmlCompileAttributeTest : no namespace bound to prefix %s\n",
 967             prefix);
 968         ctxt->error = 1;
 969         goto error;
 970         }
 971     }
 972     XML_PAT_FREE_STRING(ctxt, prefix);
 973     if (token == NULL) {
 974         if (CUR == '*') {
 975         NEXT;
 976         PUSH(XML_OP_ATTR, NULL, URL);
 977         } else {
 978         ERROR(NULL, NULL, NULL,
 979             "xmlCompileAttributeTest : Name expected\n");
 980         ctxt->error = 1;
 981         goto error;
 982         }
 983     } else {
 984         PUSH(XML_OP_ATTR, token, URL);
 985     }
 986     } else {
 987     PUSH(XML_OP_ATTR, name, NULL);
 988     }
 989     return;
 990 error:
 991     if (URL != NULL)
 992     XML_PAT_FREE_STRING(ctxt, URL)
 993     if (token != NULL)
 994     XML_PAT_FREE_STRING(ctxt, token);
 995 }
 996 
 997 /**
 998  * xmlCompileStepPattern:
 999  * @ctxt:  the compilation context
1000  *
1001  * Compile the Step Pattern and generates a precompiled
1002  * form suitable for fast matching.
1003  *
1004  * [3]    Step    ::=    '.' | NameTest
1005  * [4]    NameTest    ::=    QName | '*' | NCName ':' '*'
1006  */
1007 
1008 static void
1009 xmlCompileStepPattern(xmlPatParserContextPtr ctxt) {
1010     xmlChar *token = NULL;
1011     xmlChar *name = NULL;
1012     xmlChar *URL = NULL;
1013     int hasBlanks = 0;
1014 
1015     SKIP_BLANKS;
1016     if (CUR == '.') {
1017     /*
1018     * Context node.
1019     */
1020     NEXT;
1021     PUSH(XML_OP_ELEM, NULL, NULL);
1022     return;
1023     }
1024     if (CUR == '@') {
1025     /*
1026     * Attribute test.
1027     */
1028     if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
1029         ERROR5(NULL, NULL, NULL,
1030         "Unexpected attribute axis in '%s'.\n", ctxt->base);
1031         ctxt->error = 1;
1032         return;
1033     }
1034     NEXT;
1035     xmlCompileAttributeTest(ctxt);
1036     if (ctxt->error != 0)
1037         goto error;
1038     return;
1039     }
1040     name = xmlPatScanNCName(ctxt);
1041     if (name == NULL) {
1042     if (CUR == '*') {
1043         NEXT;
1044         PUSH(XML_OP_ALL, NULL, NULL);
1045         return;
1046     } else {
1047         ERROR(NULL, NULL, NULL,
1048             "xmlCompileStepPattern : Name expected\n");
1049         ctxt->error = 1;
1050         return;
1051     }
1052     }
1053     if (IS_BLANK_CH(CUR)) {
1054     hasBlanks = 1;
1055     SKIP_BLANKS;
1056     }
1057     if (CUR == ':') {
1058     NEXT;
1059     if (CUR != ':') {
1060         xmlChar *prefix = name;
1061         int i;
1062 
1063         if (hasBlanks || IS_BLANK_CH(CUR)) {
1064         ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
1065         ctxt->error = 1;
1066         goto error;
1067         }
1068         /*
1069          * This is a namespace match
1070          */
1071         token = xmlPatScanName(ctxt);
1072         if ((prefix[0] == 'x') &&
1073         (prefix[1] == 'm') &&
1074         (prefix[2] == 'l') &&
1075         (prefix[3] == 0))
1076         {
1077         XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
1078         } else {
1079         for (i = 0;i < ctxt->nb_namespaces;i++) {
1080             if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
1081             XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
1082             break;
1083             }
1084         }
1085         if (i >= ctxt->nb_namespaces) {
1086             ERROR5(NULL, NULL, NULL,
1087             "xmlCompileStepPattern : no namespace bound to prefix %s\n",
1088             prefix);
1089             ctxt->error = 1;
1090             goto error;
1091         }
1092         }
1093         XML_PAT_FREE_STRING(ctxt, prefix);
1094         name = NULL;
1095         if (token == NULL) {
1096         if (CUR == '*') {
1097             NEXT;
1098             PUSH(XML_OP_NS, URL, NULL);
1099         } else {
1100             ERROR(NULL, NULL, NULL,
1101                 "xmlCompileStepPattern : Name expected\n");
1102             ctxt->error = 1;
1103             goto error;
1104         }
1105         } else {
1106         PUSH(XML_OP_ELEM, token, URL);
1107         }
1108     } else {
1109         NEXT;
1110         if (xmlStrEqual(name, (const xmlChar *) "child")) {
1111         XML_PAT_FREE_STRING(ctxt, name);
1112         name = xmlPatScanName(ctxt);
1113         if (name == NULL) {
1114             if (CUR == '*') {
1115             NEXT;
1116             PUSH(XML_OP_ALL, NULL, NULL);
1117             return;
1118             } else {
1119             ERROR(NULL, NULL, NULL,
1120                 "xmlCompileStepPattern : QName expected\n");
1121             ctxt->error = 1;
1122             goto error;
1123             }
1124         }
1125         if (CUR == ':') {
1126             xmlChar *prefix = name;
1127             int i;
1128 
1129             NEXT;
1130             if (IS_BLANK_CH(CUR)) {
1131             ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
1132             ctxt->error = 1;
1133             goto error;
1134             }
1135             /*
1136             * This is a namespace match
1137             */
1138             token = xmlPatScanName(ctxt);
1139             if ((prefix[0] == 'x') &&
1140             (prefix[1] == 'm') &&
1141             (prefix[2] == 'l') &&
1142             (prefix[3] == 0))
1143             {
1144             XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
1145             } else {
1146             for (i = 0;i < ctxt->nb_namespaces;i++) {
1147                 if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
1148                 XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
1149                 break;
1150                 }
1151             }
1152             if (i >= ctxt->nb_namespaces) {
1153                 ERROR5(NULL, NULL, NULL,
1154                 "xmlCompileStepPattern : no namespace bound "
1155                 "to prefix %s\n", prefix);
1156                 ctxt->error = 1;
1157                 goto error;
1158             }
1159             }
1160             XML_PAT_FREE_STRING(ctxt, prefix);
1161             name = NULL;
1162             if (token == NULL) {
1163             if (CUR == '*') {
1164                 NEXT;
1165                 PUSH(XML_OP_NS, URL, NULL);
1166             } else {
1167                 ERROR(NULL, NULL, NULL,
1168                 "xmlCompileStepPattern : Name expected\n");
1169                 ctxt->error = 1;
1170                 goto error;
1171             }
1172             } else {
1173             PUSH(XML_OP_CHILD, token, URL);
1174             }
1175         } else
1176             PUSH(XML_OP_CHILD, name, NULL);
1177         return;
1178         } else if (xmlStrEqual(name, (const xmlChar *) "attribute")) {
1179         XML_PAT_FREE_STRING(ctxt, name)
1180         name = NULL;
1181         if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
1182             ERROR5(NULL, NULL, NULL,
1183             "Unexpected attribute axis in '%s'.\n", ctxt->base);
1184             ctxt->error = 1;
1185             goto error;
1186         }
1187         xmlCompileAttributeTest(ctxt);
1188         if (ctxt->error != 0)
1189             goto error;
1190         return;
1191         } else {
1192         ERROR5(NULL, NULL, NULL,
1193             "The 'element' or 'attribute' axis is expected.\n", NULL);
1194         ctxt->error = 1;
1195         goto error;
1196         }
1197     }
1198     } else if (CUR == '*') {
1199         if (name != NULL) {
1200         ctxt->error = 1;
1201         goto error;
1202     }
1203     NEXT;
1204     PUSH(XML_OP_ALL, token, NULL);
1205     } else {
1206     PUSH(XML_OP_ELEM, name, NULL);
1207     }
1208     return;
1209 error:
1210     if (URL != NULL)
1211     XML_PAT_FREE_STRING(ctxt, URL)
1212     if (token != NULL)
1213     XML_PAT_FREE_STRING(ctxt, token)
1214     if (name != NULL)
1215     XML_PAT_FREE_STRING(ctxt, name)
1216 }
1217 
1218 /**
1219  * xmlCompilePathPattern:
1220  * @ctxt:  the compilation context
1221  *
1222  * Compile the Path Pattern and generates a precompiled
1223  * form suitable for fast matching.
1224  *
1225  * [5]    Path    ::=    ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1226  */
1227 static void
1228 xmlCompilePathPattern(xmlPatParserContextPtr ctxt) {
1229     SKIP_BLANKS;
1230     if (CUR == '/') {
1231         ctxt->comp->flags |= PAT_FROM_ROOT;
1232     } else if ((CUR == '.') || (ctxt->comp->flags & XML_PATTERN_NOTPATTERN)) {
1233         ctxt->comp->flags |= PAT_FROM_CUR;
1234     }
1235 
1236     if ((CUR == '/') && (NXT(1) == '/')) {
1237     PUSH(XML_OP_ANCESTOR, NULL, NULL);
1238     NEXT;
1239     NEXT;
1240     } else if ((CUR == '.') && (NXT(1) == '/') && (NXT(2) == '/')) {
1241     PUSH(XML_OP_ANCESTOR, NULL, NULL);
1242     NEXT;
1243     NEXT;
1244     NEXT;
1245     /* Check for incompleteness. */
1246     SKIP_BLANKS;
1247     if (CUR == 0) {
1248         ERROR5(NULL, NULL, NULL,
1249            "Incomplete expression '%s'.\n", ctxt->base);
1250         ctxt->error = 1;
1251         goto error;
1252     }
1253     }
1254     if (CUR == '@') {
1255     NEXT;
1256     xmlCompileAttributeTest(ctxt);
1257     SKIP_BLANKS;
1258     /* TODO: check for incompleteness */
1259     if (CUR != 0) {
1260         xmlCompileStepPattern(ctxt);
1261         if (ctxt->error != 0)
1262         goto error;
1263     }
1264     } else {
1265         if (CUR == '/') {
1266         PUSH(XML_OP_ROOT, NULL, NULL);
1267         NEXT;
1268         /* Check for incompleteness. */
1269         SKIP_BLANKS;
1270         if (CUR == 0) {
1271         ERROR5(NULL, NULL, NULL,
1272             "Incomplete expression '%s'.\n", ctxt->base);
1273         ctxt->error = 1;
1274         goto error;
1275         }
1276     }
1277     xmlCompileStepPattern(ctxt);
1278     if (ctxt->error != 0)
1279         goto error;
1280     SKIP_BLANKS;
1281     while (CUR == '/') {
1282         if (NXT(1) == '/') {
1283             PUSH(XML_OP_ANCESTOR, NULL, NULL);
1284         NEXT;
1285         NEXT;
1286         SKIP_BLANKS;
1287         xmlCompileStepPattern(ctxt);
1288         if (ctxt->error != 0)
1289             goto error;
1290         } else {
1291             PUSH(XML_OP_PARENT, NULL, NULL);
1292         NEXT;
1293         SKIP_BLANKS;
1294         if (CUR == 0) {
1295             ERROR5(NULL, NULL, NULL,
1296             "Incomplete expression '%s'.\n", ctxt->base);
1297             ctxt->error = 1;
1298             goto error;
1299         }
1300         xmlCompileStepPattern(ctxt);
1301         if (ctxt->error != 0)
1302             goto error;
1303         }
1304     }
1305     }
1306     if (CUR != 0) {
1307     ERROR5(NULL, NULL, NULL,
1308            "Failed to compile pattern %s\n", ctxt->base);
1309     ctxt->error = 1;
1310     }
1311 error:
1312     return;
1313 }
1314 
1315 /**
1316  * xmlCompileIDCXPathPath:
1317  * @ctxt:  the compilation context
1318  *
1319  * Compile the Path Pattern and generates a precompiled
1320  * form suitable for fast matching.
1321  *
1322  * [5]    Path    ::=    ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1323  */
1324 static void
1325 xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt) {
1326     SKIP_BLANKS;
1327     if (CUR == '/') {
1328     ERROR5(NULL, NULL, NULL,
1329         "Unexpected selection of the document root in '%s'.\n",
1330         ctxt->base);
1331     goto error;
1332     }
1333     ctxt->comp->flags |= PAT_FROM_CUR;
1334 
1335     if (CUR == '.') {
1336     /* "." - "self::node()" */
1337     NEXT;
1338     SKIP_BLANKS;
1339     if (CUR == 0) {
1340         /*
1341         * Selection of the context node.
1342         */
1343         PUSH(XML_OP_ELEM, NULL, NULL);
1344         return;
1345     }
1346     if (CUR != '/') {
1347         /* TODO: A more meaningful error message. */
1348         ERROR5(NULL, NULL, NULL,
1349         "Unexpected token after '.' in '%s'.\n", ctxt->base);
1350         goto error;
1351     }
1352     /* "./" - "self::node()/" */
1353     NEXT;
1354     SKIP_BLANKS;
1355     if (CUR == '/') {
1356         if (IS_BLANK_CH(PEEKPREV(1))) {
1357         /*
1358         * Disallow "./ /"
1359         */
1360         ERROR5(NULL, NULL, NULL,
1361             "Unexpected '/' token in '%s'.\n", ctxt->base);
1362         goto error;
1363         }
1364         /* ".//" - "self:node()/descendant-or-self::node()/" */
1365         PUSH(XML_OP_ANCESTOR, NULL, NULL);
1366         NEXT;
1367         SKIP_BLANKS;
1368     }
1369     if (CUR == 0)
1370         goto error_unfinished;
1371     }
1372     /*
1373     * Process steps.
1374     */
1375     do {
1376     xmlCompileStepPattern(ctxt);
1377     if (ctxt->error != 0)
1378         goto error;
1379     SKIP_BLANKS;
1380     if (CUR != '/')
1381         break;
1382     PUSH(XML_OP_PARENT, NULL, NULL);
1383     NEXT;
1384     SKIP_BLANKS;
1385     if (CUR == '/') {
1386         /*
1387         * Disallow subsequent '//'.
1388         */
1389         ERROR5(NULL, NULL, NULL,
1390         "Unexpected subsequent '//' in '%s'.\n",
1391         ctxt->base);
1392         goto error;
1393     }
1394     if (CUR == 0)
1395         goto error_unfinished;
1396 
1397     } while (CUR != 0);
1398 
1399     if (CUR != 0) {
1400     ERROR5(NULL, NULL, NULL,
1401         "Failed to compile expression '%s'.\n", ctxt->base);
1402     ctxt->error = 1;
1403     }
1404     return;
1405 error:
1406     ctxt->error = 1;
1407     return;
1408 
1409 error_unfinished:
1410     ctxt->error = 1;
1411     ERROR5(NULL, NULL, NULL,
1412     "Unfinished expression '%s'.\n", ctxt->base);
1413     return;
1414 }
1415 
1416 /************************************************************************
1417  *                                  *
1418  *          The streaming code              *
1419  *                                  *
1420  ************************************************************************/
1421 
1422 #ifdef DEBUG_STREAMING
1423 static void
1424 xmlDebugStreamComp(xmlStreamCompPtr stream) {
1425     int i;
1426 
1427     if (stream == NULL) {
1428         printf("Stream: NULL\n");
1429     return;
1430     }
1431     printf("Stream: %d steps\n", stream->nbStep);
1432     for (i = 0;i < stream->nbStep;i++) {
1433     if (stream->steps[i].ns != NULL) {
1434         printf("{%s}", stream->steps[i].ns);
1435     }
1436         if (stream->steps[i].name == NULL) {
1437         printf("* ");
1438     } else {
1439         printf("%s ", stream->steps[i].name);
1440     }
1441     if (stream->steps[i].flags & XML_STREAM_STEP_ROOT)
1442         printf("root ");
1443     if (stream->steps[i].flags & XML_STREAM_STEP_DESC)
1444         printf("// ");
1445     if (stream->steps[i].flags & XML_STREAM_STEP_FINAL)
1446         printf("final ");
1447     printf("\n");
1448     }
1449 }
1450 static void
1451 xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt, int match) {
1452     int i;
1453 
1454     if (ctxt == NULL) {
1455         printf("Stream: NULL\n");
1456     return;
1457     }
1458     printf("Stream: level %d, %d states: ", ctxt->level, ctxt->nbState);
1459     if (match)
1460         printf("matches\n");
1461     else
1462         printf("\n");
1463     for (i = 0;i < ctxt->nbState;i++) {
1464         if (ctxt->states[2 * i] < 0)
1465         printf(" %d: free\n", i);
1466     else {
1467         printf(" %d: step %d, level %d", i, ctxt->states[2 * i],
1468                ctxt->states[(2 * i) + 1]);
1469             if (ctxt->comp->steps[ctxt->states[2 * i]].flags &
1470             XML_STREAM_STEP_DESC)
1471             printf(" //\n");
1472         else
1473             printf("\n");
1474     }
1475     }
1476 }
1477 #endif
1478 /**
1479  * xmlNewStreamComp:
1480  * @size: the number of expected steps
1481  *
1482  * build a new compiled pattern for streaming
1483  *
1484  * Returns the new structure or NULL in case of error.
1485  */
1486 static xmlStreamCompPtr
1487 xmlNewStreamComp(int size) {
1488     xmlStreamCompPtr cur;
1489 
1490     if (size < 4)
1491         size  = 4;
1492 
1493     cur = (xmlStreamCompPtr) xmlMalloc(sizeof(xmlStreamComp));
1494     if (cur == NULL) {
1495     ERROR(NULL, NULL, NULL,
1496         "xmlNewStreamComp: malloc failed\n");
1497     return(NULL);
1498     }
1499     memset(cur, 0, sizeof(xmlStreamComp));
1500     cur->steps = (xmlStreamStepPtr) xmlMalloc(size * sizeof(xmlStreamStep));
1501     if (cur->steps == NULL) {
1502     xmlFree(cur);
1503     ERROR(NULL, NULL, NULL,
1504           "xmlNewStreamComp: malloc failed\n");
1505     return(NULL);
1506     }
1507     cur->nbStep = 0;
1508     cur->maxStep = size;
1509     return(cur);
1510 }
1511 
1512 /**
1513  * xmlFreeStreamComp:
1514  * @comp: the compiled pattern for streaming
1515  *
1516  * Free the compiled pattern for streaming
1517  */
1518 static void
1519 xmlFreeStreamComp(xmlStreamCompPtr comp) {
1520     if (comp != NULL) {
1521         if (comp->steps != NULL)
1522         xmlFree(comp->steps);
1523     if (comp->dict != NULL)
1524         xmlDictFree(comp->dict);
1525         xmlFree(comp);
1526     }
1527 }
1528 
1529 /**
1530  * xmlStreamCompAddStep:
1531  * @comp: the compiled pattern for streaming
1532  * @name: the first string, the name, or NULL for *
1533  * @ns: the second step, the namespace name
1534  * @flags: the flags for that step
1535  *
1536  * Add a new step to the compiled pattern
1537  *
1538  * Returns -1 in case of error or the step index if successful
1539  */
1540 static int
1541 xmlStreamCompAddStep(xmlStreamCompPtr comp, const xmlChar *name,
1542                      const xmlChar *ns, int nodeType, int flags) {
1543     xmlStreamStepPtr cur;
1544 
1545     if (comp->nbStep >= comp->maxStep) {
1546     cur = (xmlStreamStepPtr) xmlRealloc(comp->steps,
1547                  comp->maxStep * 2 * sizeof(xmlStreamStep));
1548     if (cur == NULL) {
1549         ERROR(NULL, NULL, NULL,
1550           "xmlNewStreamComp: malloc failed\n");
1551         return(-1);
1552     }
1553     comp->steps = cur;
1554         comp->maxStep *= 2;
1555     }
1556     cur = &comp->steps[comp->nbStep++];
1557     cur->flags = flags;
1558     cur->name = name;
1559     cur->ns = ns;
1560     cur->nodeType = nodeType;
1561     return(comp->nbStep - 1);
1562 }
1563 
1564 /**
1565  * xmlStreamCompile:
1566  * @comp: the precompiled pattern
1567  *
1568  * Tries to stream compile a pattern
1569  *
1570  * Returns -1 in case of failure and 0 in case of success.
1571  */
1572 static int
1573 xmlStreamCompile(xmlPatternPtr comp) {
1574     xmlStreamCompPtr stream;
1575     int i, s = 0, root = 0, flags = 0, prevs = -1;
1576     xmlStepOp step;
1577 
1578     if ((comp == NULL) || (comp->steps == NULL))
1579         return(-1);
1580     /*
1581      * special case for .
1582      */
1583     if ((comp->nbStep == 1) &&
1584         (comp->steps[0].op == XML_OP_ELEM) &&
1585     (comp->steps[0].value == NULL) &&
1586     (comp->steps[0].value2 == NULL)) {
1587     stream = xmlNewStreamComp(0);
1588     if (stream == NULL)
1589         return(-1);
1590     /* Note that the stream will have no steps in this case. */
1591     stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1592     comp->stream = stream;
1593     return(0);
1594     }
1595 
1596     stream = xmlNewStreamComp((comp->nbStep / 2) + 1);
1597     if (stream == NULL)
1598         return(-1);
1599     if (comp->dict != NULL) {
1600         stream->dict = comp->dict;
1601     xmlDictReference(stream->dict);
1602     }
1603 
1604     i = 0;
1605     if (comp->flags & PAT_FROM_ROOT)
1606     stream->flags |= XML_STREAM_FROM_ROOT;
1607 
1608     for (;i < comp->nbStep;i++) {
1609     step = comp->steps[i];
1610         switch (step.op) {
1611         case XML_OP_END:
1612             break;
1613         case XML_OP_ROOT:
1614             if (i != 0)
1615             goto error;
1616         root = 1;
1617         break;
1618         case XML_OP_NS:
1619         s = xmlStreamCompAddStep(stream, NULL, step.value,
1620             XML_ELEMENT_NODE, flags);
1621         if (s < 0)
1622             goto error;
1623         prevs = s;
1624         flags = 0;
1625         break;
1626         case XML_OP_ATTR:
1627         flags |= XML_STREAM_STEP_ATTR;
1628         prevs = -1;
1629         s = xmlStreamCompAddStep(stream,
1630             step.value, step.value2, XML_ATTRIBUTE_NODE, flags);
1631         flags = 0;
1632         if (s < 0)
1633             goto error;
1634         break;
1635         case XML_OP_ELEM:
1636             if ((step.value == NULL) && (step.value2 == NULL)) {
1637             /*
1638             * We have a "." or "self::node()" here.
1639             * Eliminate redundant self::node() tests like in "/./."
1640             * or "//./"
1641             * The only case we won't eliminate is "//.", i.e. if
1642             * self::node() is the last node test and we had
1643             * continuation somewhere beforehand.
1644             */
1645             if ((comp->nbStep == i + 1) &&
1646             (flags & XML_STREAM_STEP_DESC)) {
1647             /*
1648             * Mark the special case where the expression resolves
1649             * to any type of node.
1650             */
1651             if (comp->nbStep == i + 1) {
1652                 stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1653             }
1654             flags |= XML_STREAM_STEP_NODE;
1655             s = xmlStreamCompAddStep(stream, NULL, NULL,
1656                 XML_STREAM_ANY_NODE, flags);
1657             if (s < 0)
1658                 goto error;
1659             flags = 0;
1660             /*
1661             * If there was a previous step, mark it to be added to
1662             * the result node-set; this is needed since only
1663             * the last step will be marked as "final" and only
1664             * "final" nodes are added to the resulting set.
1665             */
1666             if (prevs != -1) {
1667                 stream->steps[prevs].flags |= XML_STREAM_STEP_IN_SET;
1668                 prevs = -1;
1669             }
1670             break;
1671 
1672             } else {
1673             /* Just skip this one. */
1674             continue;
1675             }
1676         }
1677         /* An element node. */
1678             s = xmlStreamCompAddStep(stream, step.value, step.value2,
1679             XML_ELEMENT_NODE, flags);
1680         if (s < 0)
1681             goto error;
1682         prevs = s;
1683         flags = 0;
1684         break;
1685         case XML_OP_CHILD:
1686         /* An element node child. */
1687             s = xmlStreamCompAddStep(stream, step.value, step.value2,
1688             XML_ELEMENT_NODE, flags);
1689         if (s < 0)
1690             goto error;
1691         prevs = s;
1692         flags = 0;
1693         break;
1694         case XML_OP_ALL:
1695             s = xmlStreamCompAddStep(stream, NULL, NULL,
1696             XML_ELEMENT_NODE, flags);
1697         if (s < 0)
1698             goto error;
1699         prevs = s;
1700         flags = 0;
1701         break;
1702         case XML_OP_PARENT:
1703             break;
1704         case XML_OP_ANCESTOR:
1705         /* Skip redundant continuations. */
1706         if (flags & XML_STREAM_STEP_DESC)
1707             break;
1708             flags |= XML_STREAM_STEP_DESC;
1709         /*
1710         * Mark the expression as having "//".
1711         */
1712         if ((stream->flags & XML_STREAM_DESC) == 0)
1713             stream->flags |= XML_STREAM_DESC;
1714         break;
1715     }
1716     }
1717     if ((! root) && (comp->flags & XML_PATTERN_NOTPATTERN) == 0) {
1718     /*
1719     * If this should behave like a real pattern, we will mark
1720     * the first step as having "//", to be reentrant on every
1721     * tree level.
1722     */
1723     if ((stream->flags & XML_STREAM_DESC) == 0)
1724         stream->flags |= XML_STREAM_DESC;
1725 
1726     if (stream->nbStep > 0) {
1727         if ((stream->steps[0].flags & XML_STREAM_STEP_DESC) == 0)
1728         stream->steps[0].flags |= XML_STREAM_STEP_DESC;
1729     }
1730     }
1731     if (stream->nbStep <= s)
1732     goto error;
1733     stream->steps[s].flags |= XML_STREAM_STEP_FINAL;
1734     if (root)
1735     stream->steps[0].flags |= XML_STREAM_STEP_ROOT;
1736 #ifdef DEBUG_STREAMING
1737     xmlDebugStreamComp(stream);
1738 #endif
1739     comp->stream = stream;
1740     return(0);
1741 error:
1742     xmlFreeStreamComp(stream);
1743     return(0);
1744 }
1745 
1746 /**
1747  * xmlNewStreamCtxt:
1748  * @size: the number of expected states
1749  *
1750  * build a new stream context
1751  *
1752  * Returns the new structure or NULL in case of error.
1753  */
1754 static xmlStreamCtxtPtr
1755 xmlNewStreamCtxt(xmlStreamCompPtr stream) {
1756     xmlStreamCtxtPtr cur;
1757 
1758     cur = (xmlStreamCtxtPtr) xmlMalloc(sizeof(xmlStreamCtxt));
1759     if (cur == NULL) {
1760     ERROR(NULL, NULL, NULL,
1761         "xmlNewStreamCtxt: malloc failed\n");
1762     return(NULL);
1763     }
1764     memset(cur, 0, sizeof(xmlStreamCtxt));
1765     cur->states = (int *) xmlMalloc(4 * 2 * sizeof(int));
1766     if (cur->states == NULL) {
1767     xmlFree(cur);
1768     ERROR(NULL, NULL, NULL,
1769           "xmlNewStreamCtxt: malloc failed\n");
1770     return(NULL);
1771     }
1772     cur->nbState = 0;
1773     cur->maxState = 4;
1774     cur->level = 0;
1775     cur->comp = stream;
1776     cur->blockLevel = -1;
1777     return(cur);
1778 }
1779 
1780 /**
1781  * xmlFreeStreamCtxt:
1782  * @stream: the stream context
1783  *
1784  * Free the stream context
1785  */
1786 void
1787 xmlFreeStreamCtxt(xmlStreamCtxtPtr stream) {
1788     xmlStreamCtxtPtr next;
1789 
1790     while (stream != NULL) {
1791         next = stream->next;
1792         if (stream->states != NULL)
1793         xmlFree(stream->states);
1794         xmlFree(stream);
1795     stream = next;
1796     }
1797 }
1798 
1799 /**
1800  * xmlStreamCtxtAddState:
1801  * @comp: the stream context
1802  * @idx: the step index for that streaming state
1803  *
1804  * Add a new state to the stream context
1805  *
1806  * Returns -1 in case of error or the state index if successful
1807  */
1808 static int
1809 xmlStreamCtxtAddState(xmlStreamCtxtPtr comp, int idx, int level) {
1810     int i;
1811     for (i = 0;i < comp->nbState;i++) {
1812         if (comp->states[2 * i] < 0) {
1813         comp->states[2 * i] = idx;
1814         comp->states[2 * i + 1] = level;
1815         return(i);
1816     }
1817     }
1818     if (comp->nbState >= comp->maxState) {
1819         int *cur;
1820 
1821     cur = (int *) xmlRealloc(comp->states,
1822                  comp->maxState * 4 * sizeof(int));
1823     if (cur == NULL) {
1824         ERROR(NULL, NULL, NULL,
1825           "xmlNewStreamCtxt: malloc failed\n");
1826         return(-1);
1827     }
1828     comp->states = cur;
1829         comp->maxState *= 2;
1830     }
1831     comp->states[2 * comp->nbState] = idx;
1832     comp->states[2 * comp->nbState++ + 1] = level;
1833     return(comp->nbState - 1);
1834 }
1835 
1836 /**
1837  * xmlStreamPushInternal:
1838  * @stream: the stream context
1839  * @name: the current name
1840  * @ns: the namespace name
1841  * @nodeType: the type of the node
1842  *
1843  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
1844  * indicated a dictionary, then strings for name and ns will be expected
1845  * to come from the dictionary.
1846  * Both @name and @ns being NULL means the / i.e. the root of the document.
1847  * This can also act as a reset.
1848  *
1849  * Returns: -1 in case of error, 1 if the current state in the stream is a
1850  *    match and 0 otherwise.
1851  */
1852 static int
1853 xmlStreamPushInternal(xmlStreamCtxtPtr stream,
1854               const xmlChar *name, const xmlChar *ns,
1855               int nodeType) {
1856     int ret = 0, err = 0, final = 0, tmp, i, m, match, stepNr, desc;
1857     xmlStreamCompPtr comp;
1858     xmlStreamStep step;
1859 #ifdef DEBUG_STREAMING
1860     xmlStreamCtxtPtr orig = stream;
1861 #endif
1862 
1863     if ((stream == NULL) || (stream->nbState < 0))
1864         return(-1);
1865 
1866     while (stream != NULL) {
1867     comp = stream->comp;
1868 
1869     if ((nodeType == XML_ELEMENT_NODE) &&
1870         (name == NULL) && (ns == NULL)) {
1871         /* We have a document node here (or a reset). */
1872         stream->nbState = 0;
1873         stream->level = 0;
1874         stream->blockLevel = -1;
1875         if (comp->flags & XML_STREAM_FROM_ROOT) {
1876         if (comp->nbStep == 0) {
1877             /* TODO: We have a "/." here? */
1878             ret = 1;
1879         } else {
1880             if ((comp->nbStep == 1) &&
1881             (comp->steps[0].nodeType == XML_STREAM_ANY_NODE) &&
1882             (comp->steps[0].flags & XML_STREAM_STEP_DESC))
1883             {
1884             /*
1885             * In the case of "//." the document node will match
1886             * as well.
1887             */
1888             ret = 1;
1889             } else if (comp->steps[0].flags & XML_STREAM_STEP_ROOT) {
1890             /* TODO: Do we need this ? */
1891             tmp = xmlStreamCtxtAddState(stream, 0, 0);
1892             if (tmp < 0)
1893                 err++;
1894             }
1895         }
1896         }
1897         stream = stream->next;
1898         continue; /* while */
1899     }
1900 
1901     /*
1902     * Fast check for ".".
1903     */
1904     if (comp->nbStep == 0) {
1905         /*
1906          * / and . are handled at the XPath node set creation
1907          * level by checking min depth
1908          */
1909         if (stream->flags & XML_PATTERN_XPATH) {
1910         stream = stream->next;
1911         continue; /* while */
1912         }
1913         /*
1914         * For non-pattern like evaluation like XML Schema IDCs
1915         * or traditional XPath expressions, this will match if
1916         * we are at the first level only, otherwise on every level.
1917         */
1918         if ((nodeType != XML_ATTRIBUTE_NODE) &&
1919         (((stream->flags & XML_PATTERN_NOTPATTERN) == 0) ||
1920         (stream->level == 0))) {
1921             ret = 1;
1922         }
1923         stream->level++;
1924         goto stream_next;
1925     }
1926     if (stream->blockLevel != -1) {
1927         /*
1928         * Skip blocked expressions.
1929         */
1930             stream->level++;
1931         goto stream_next;
1932     }
1933 
1934     if ((nodeType != XML_ELEMENT_NODE) &&
1935         (nodeType != XML_ATTRIBUTE_NODE) &&
1936         ((comp->flags & XML_STREAM_FINAL_IS_ANY_NODE) == 0)) {
1937         /*
1938         * No need to process nodes of other types if we don't
1939         * resolve to those types.
1940         * TODO: Do we need to block the context here?
1941         */
1942         stream->level++;
1943         goto stream_next;
1944     }
1945 
1946     /*
1947      * Check evolution of existing states
1948      */
1949     i = 0;
1950     m = stream->nbState;
1951     while (i < m) {
1952         if ((comp->flags & XML_STREAM_DESC) == 0) {
1953         /*
1954         * If there is no "//", then only the last
1955         * added state is of interest.
1956         */
1957         stepNr = stream->states[2 * (stream->nbState -1)];
1958         /*
1959         * TODO: Security check, should not happen, remove it.
1960         */
1961         if (stream->states[(2 * (stream->nbState -1)) + 1] <
1962             stream->level) {
1963             return (-1);
1964         }
1965         desc = 0;
1966         /* loop-stopper */
1967         i = m;
1968         } else {
1969         /*
1970         * If there are "//", then we need to process every "//"
1971         * occuring in the states, plus any other state for this
1972         * level.
1973         */
1974         stepNr = stream->states[2 * i];
1975 
1976         /* TODO: should not happen anymore: dead states */
1977         if (stepNr < 0)
1978             goto next_state;
1979 
1980         tmp = stream->states[(2 * i) + 1];
1981 
1982         /* skip new states just added */
1983         if (tmp > stream->level)
1984             goto next_state;
1985 
1986         /* skip states at ancestor levels, except if "//" */
1987         desc = comp->steps[stepNr].flags & XML_STREAM_STEP_DESC;
1988         if ((tmp < stream->level) && (!desc))
1989             goto next_state;
1990         }
1991         /*
1992         * Check for correct node-type.
1993         */
1994         step = comp->steps[stepNr];
1995         if (step.nodeType != nodeType) {
1996         if (step.nodeType == XML_ATTRIBUTE_NODE) {
1997             /*
1998             * Block this expression for deeper evaluation.
1999             */
2000             if ((comp->flags & XML_STREAM_DESC) == 0)
2001             stream->blockLevel = stream->level +1;
2002             goto next_state;
2003         } else if (step.nodeType != XML_STREAM_ANY_NODE)
2004             goto next_state;
2005         }
2006         /*
2007         * Compare local/namespace-name.
2008         */
2009         match = 0;
2010         if (step.nodeType == XML_STREAM_ANY_NODE) {
2011         match = 1;
2012         } else if (step.name == NULL) {
2013         if (step.ns == NULL) {
2014             /*
2015             * This lets through all elements/attributes.
2016             */
2017             match = 1;
2018         } else if (ns != NULL)
2019             match = xmlStrEqual(step.ns, ns);
2020         } else if (((step.ns != NULL) == (ns != NULL)) &&
2021         (name != NULL) &&
2022         (step.name[0] == name[0]) &&
2023         xmlStrEqual(step.name, name) &&
2024         ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2025         {
2026         match = 1;
2027         }
2028 #if 0
2029 /*
2030 * TODO: Pointer comparison won't work, since not guaranteed that the given
2031 *  values are in the same dict; especially if it's the namespace name,
2032 *  normally coming from ns->href. We need a namespace dict mechanism !
2033 */
2034         } else if (comp->dict) {
2035         if (step.name == NULL) {
2036             if (step.ns == NULL)
2037             match = 1;
2038             else
2039             match = (step.ns == ns);
2040         } else {
2041             match = ((step.name == name) && (step.ns == ns));
2042         }
2043 #endif /* if 0 ------------------------------------------------------- */
2044         if (match) {
2045         final = step.flags & XML_STREAM_STEP_FINAL;
2046         if (desc) {
2047             if (final) {
2048             ret = 1;
2049             } else {
2050             /* descending match create a new state */
2051             xmlStreamCtxtAddState(stream, stepNr + 1,
2052                                   stream->level + 1);
2053             }
2054         } else {
2055             if (final) {
2056             ret = 1;
2057             } else {
2058             xmlStreamCtxtAddState(stream, stepNr + 1,
2059                                   stream->level + 1);
2060             }
2061         }
2062         if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2063             /*
2064             * Check if we have a special case like "foo/bar//.", where
2065             * "foo" is selected as well.
2066             */
2067             ret = 1;
2068         }
2069         }
2070         if (((comp->flags & XML_STREAM_DESC) == 0) &&
2071         ((! match) || final))  {
2072         /*
2073         * Mark this expression as blocked for any evaluation at
2074         * deeper levels. Note that this includes "/foo"
2075         * expressions if the *pattern* behaviour is used.
2076         */
2077         stream->blockLevel = stream->level +1;
2078         }
2079 next_state:
2080         i++;
2081     }
2082 
2083     stream->level++;
2084 
2085     /*
2086     * Re/enter the expression.
2087     * Don't reenter if it's an absolute expression like "/foo",
2088     *   except "//foo".
2089     */
2090     step = comp->steps[0];
2091     if (step.flags & XML_STREAM_STEP_ROOT)
2092         goto stream_next;
2093 
2094     desc = step.flags & XML_STREAM_STEP_DESC;
2095     if (stream->flags & XML_PATTERN_NOTPATTERN) {
2096         /*
2097         * Re/enter the expression if it is a "descendant" one,
2098         * or if we are at the 1st level of evaluation.
2099         */
2100 
2101         if (stream->level == 1) {
2102         if (XML_STREAM_XS_IDC(stream)) {
2103             /*
2104             * XS-IDC: The missing "self::node()" will always
2105             * match the first given node.
2106             */
2107             goto stream_next;
2108         } else
2109             goto compare;
2110         }
2111         /*
2112         * A "//" is always reentrant.
2113         */
2114         if (desc)
2115         goto compare;
2116 
2117         /*
2118         * XS-IDC: Process the 2nd level, since the missing
2119         * "self::node()" is responsible for the 2nd level being
2120         * the real start level.
2121         */
2122         if ((stream->level == 2) && XML_STREAM_XS_IDC(stream))
2123         goto compare;
2124 
2125         goto stream_next;
2126     }
2127 
2128 compare:
2129     /*
2130     * Check expected node-type.
2131     */
2132     if (step.nodeType != nodeType) {
2133         if (nodeType == XML_ATTRIBUTE_NODE)
2134         goto stream_next;
2135         else if (step.nodeType != XML_STREAM_ANY_NODE)
2136         goto stream_next;
2137     }
2138     /*
2139     * Compare local/namespace-name.
2140     */
2141     match = 0;
2142     if (step.nodeType == XML_STREAM_ANY_NODE) {
2143         match = 1;
2144     } else if (step.name == NULL) {
2145         if (step.ns == NULL) {
2146         /*
2147         * This lets through all elements/attributes.
2148         */
2149         match = 1;
2150         } else if (ns != NULL)
2151         match = xmlStrEqual(step.ns, ns);
2152     } else if (((step.ns != NULL) == (ns != NULL)) &&
2153         (name != NULL) &&
2154         (step.name[0] == name[0]) &&
2155         xmlStrEqual(step.name, name) &&
2156         ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2157     {
2158         match = 1;
2159     }
2160     final = step.flags & XML_STREAM_STEP_FINAL;
2161     if (match) {
2162         if (final)
2163         ret = 1;
2164         else
2165         xmlStreamCtxtAddState(stream, 1, stream->level);
2166         if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2167         /*
2168         * Check if we have a special case like "foo//.", where
2169         * "foo" is selected as well.
2170         */
2171         ret = 1;
2172         }
2173     }
2174     if (((comp->flags & XML_STREAM_DESC) == 0) &&
2175         ((! match) || final))  {
2176         /*
2177         * Mark this expression as blocked for any evaluation at
2178         * deeper levels.
2179         */
2180         stream->blockLevel = stream->level;
2181     }
2182 
2183 stream_next:
2184         stream = stream->next;
2185     } /* while stream != NULL */
2186 
2187     if (err > 0)
2188         ret = -1;
2189 #ifdef DEBUG_STREAMING
2190     xmlDebugStreamCtxt(orig, ret);
2191 #endif
2192     return(ret);
2193 }
2194 
2195 /**
2196  * xmlStreamPush:
2197  * @stream: the stream context
2198  * @name: the current name
2199  * @ns: the namespace name
2200  *
2201  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2202  * indicated a dictionary, then strings for name and ns will be expected
2203  * to come from the dictionary.
2204  * Both @name and @ns being NULL means the / i.e. the root of the document.
2205  * This can also act as a reset.
2206  * Otherwise the function will act as if it has been given an element-node.
2207  *
2208  * Returns: -1 in case of error, 1 if the current state in the stream is a
2209  *    match and 0 otherwise.
2210  */
2211 int
2212 xmlStreamPush(xmlStreamCtxtPtr stream,
2213               const xmlChar *name, const xmlChar *ns) {
2214     return (xmlStreamPushInternal(stream, name, ns, (int) XML_ELEMENT_NODE));
2215 }
2216 
2217 /**
2218  * xmlStreamPushNode:
2219  * @stream: the stream context
2220  * @name: the current name
2221  * @ns: the namespace name
2222  * @nodeType: the type of the node being pushed
2223  *
2224  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2225  * indicated a dictionary, then strings for name and ns will be expected
2226  * to come from the dictionary.
2227  * Both @name and @ns being NULL means the / i.e. the root of the document.
2228  * This can also act as a reset.
2229  * Different from xmlStreamPush() this function can be fed with nodes of type:
2230  * element-, attribute-, text-, cdata-section-, comment- and
2231  * processing-instruction-node.
2232  *
2233  * Returns: -1 in case of error, 1 if the current state in the stream is a
2234  *    match and 0 otherwise.
2235  */
2236 int
2237 xmlStreamPushNode(xmlStreamCtxtPtr stream,
2238           const xmlChar *name, const xmlChar *ns,
2239           int nodeType)
2240 {
2241     return (xmlStreamPushInternal(stream, name, ns,
2242     nodeType));
2243 }
2244 
2245 /**
2246 * xmlStreamPushAttr:
2247 * @stream: the stream context
2248 * @name: the current name
2249 * @ns: the namespace name
2250 *
2251 * Push new attribute data onto the stream. NOTE: if the call xmlPatterncompile()
2252 * indicated a dictionary, then strings for name and ns will be expected
2253 * to come from the dictionary.
2254 * Both @name and @ns being NULL means the / i.e. the root of the document.
2255 * This can also act as a reset.
2256 * Otherwise the function will act as if it has been given an attribute-node.
2257 *
2258 * Returns: -1 in case of error, 1 if the current state in the stream is a
2259 *    match and 0 otherwise.
2260 */
2261 int
2262 xmlStreamPushAttr(xmlStreamCtxtPtr stream,
2263           const xmlChar *name, const xmlChar *ns) {
2264     return (xmlStreamPushInternal(stream, name, ns, (int) XML_ATTRIBUTE_NODE));
2265 }
2266 
2267 /**
2268  * xmlStreamPop:
2269  * @stream: the stream context
2270  *
2271  * push one level from the stream.
2272  *
2273  * Returns: -1 in case of error, 0 otherwise.
2274  */
2275 int
2276 xmlStreamPop(xmlStreamCtxtPtr stream) {
2277     int i, lev;
2278 
2279     if (stream == NULL)
2280         return(-1);
2281     while (stream != NULL) {
2282     /*
2283     * Reset block-level.
2284     */
2285     if (stream->blockLevel == stream->level)
2286         stream->blockLevel = -1;
2287 
2288     /*
2289      *  stream->level can be zero when XML_FINAL_IS_ANY_NODE is set
2290      *  (see the thread at
2291      *  http://mail.gnome.org/archives/xslt/2008-July/msg00027.html)
2292      */
2293     if (stream->level)
2294         stream->level--;
2295     /*
2296      * Check evolution of existing states
2297      */
2298     for (i = stream->nbState -1; i >= 0; i--) {
2299         /* discard obsoleted states */
2300         lev = stream->states[(2 * i) + 1];
2301         if (lev > stream->level)
2302         stream->nbState--;
2303         if (lev <= stream->level)
2304         break;
2305     }
2306     stream = stream->next;
2307     }
2308     return(0);
2309 }
2310 
2311 /**
2312  * xmlStreamWantsAnyNode:
2313  * @streamCtxt: the stream context
2314  *
2315  * Query if the streaming pattern additionally needs to be fed with
2316  * text-, cdata-section-, comment- and processing-instruction-nodes.
2317  * If the result is 0 then only element-nodes and attribute-nodes
2318  * need to be pushed.
2319  *
2320  * Returns: 1 in case of need of nodes of the above described types,
2321  *          0 otherwise. -1 on API errors.
2322  */
2323 int
2324 xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt)
2325 {
2326     if (streamCtxt == NULL)
2327     return(-1);
2328     while (streamCtxt != NULL) {
2329     if (streamCtxt->comp->flags & XML_STREAM_FINAL_IS_ANY_NODE)
2330         return(1);
2331     streamCtxt = streamCtxt->next;
2332     }
2333     return(0);
2334 }
2335 
2336 /************************************************************************
2337  *                                  *
2338  *          The public interfaces               *
2339  *                                  *
2340  ************************************************************************/
2341 
2342 /**
2343  * xmlPatterncompile:
2344  * @pattern: the pattern to compile
2345  * @dict: an optional dictionary for interned strings
2346  * @flags: compilation flags, see xmlPatternFlags
2347  * @namespaces: the prefix definitions, array of [URI, prefix] or NULL
2348  *
2349  * Compile a pattern.
2350  *
2351  * Returns the compiled form of the pattern or NULL in case of error
2352  */
2353 xmlPatternPtr
2354 xmlPatterncompile(const xmlChar *pattern, xmlDict *dict, int flags,
2355                   const xmlChar **namespaces) {
2356     xmlPatternPtr ret = NULL, cur;
2357     xmlPatParserContextPtr ctxt = NULL;
2358     const xmlChar *or, *start;
2359     xmlChar *tmp = NULL;
2360     int type = 0;
2361     int streamable = 1;
2362 
2363     if (pattern == NULL)
2364         return(NULL);
2365 
2366     start = pattern;
2367     or = start;
2368     while (*or != 0) {
2369     tmp = NULL;
2370     while ((*or != 0) && (*or != '|')) or++;
2371         if (*or == 0)
2372         ctxt = xmlNewPatParserContext(start, dict, namespaces);
2373     else {
2374         tmp = xmlStrndup(start, or - start);
2375         if (tmp != NULL) {
2376         ctxt = xmlNewPatParserContext(tmp, dict, namespaces);
2377         }
2378         or++;
2379     }
2380     if (ctxt == NULL) goto error;
2381     cur = xmlNewPattern();
2382     if (cur == NULL) goto error;
2383     /*
2384     * Assign string dict.
2385     */
2386     if (dict) {
2387         cur->dict = dict;
2388         xmlDictReference(dict);
2389     }
2390     if (ret == NULL)
2391         ret = cur;
2392     else {
2393         cur->next = ret->next;
2394         ret->next = cur;
2395     }
2396     cur->flags = flags;
2397     ctxt->comp = cur;
2398 
2399     if (XML_STREAM_XS_IDC(cur))
2400         xmlCompileIDCXPathPath(ctxt);
2401     else
2402         xmlCompilePathPattern(ctxt);
2403     if (ctxt->error != 0)
2404         goto error;
2405     xmlFreePatParserContext(ctxt);
2406     ctxt = NULL;
2407 
2408 
2409         if (streamable) {
2410         if (type == 0) {
2411             type = cur->flags & (PAT_FROM_ROOT | PAT_FROM_CUR);
2412         } else if (type == PAT_FROM_ROOT) {
2413             if (cur->flags & PAT_FROM_CUR)
2414             streamable = 0;
2415         } else if (type == PAT_FROM_CUR) {
2416             if (cur->flags & PAT_FROM_ROOT)
2417             streamable = 0;
2418         }
2419     }
2420     if (streamable)
2421         xmlStreamCompile(cur);
2422     if (xmlReversePattern(cur) < 0)
2423         goto error;
2424     if (tmp != NULL) {
2425         xmlFree(tmp);
2426         tmp = NULL;
2427     }
2428     start = or;
2429     }
2430     if (streamable == 0) {
2431         cur = ret;
2432     while (cur != NULL) {
2433         if (cur->stream != NULL) {
2434         xmlFreeStreamComp(cur->stream);
2435         cur->stream = NULL;
2436         }
2437         cur = cur->next;
2438     }
2439     }
2440 
2441     return(ret);
2442 error:
2443     if (ctxt != NULL) xmlFreePatParserContext(ctxt);
2444     if (ret != NULL) xmlFreePattern(ret);
2445     if (tmp != NULL) xmlFree(tmp);
2446     return(NULL);
2447 }
2448 
2449 /**
2450  * xmlPatternMatch:
2451  * @comp: the precompiled pattern
2452  * @node: a node
2453  *
2454  * Test whether the node matches the pattern
2455  *
2456  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
2457  */
2458 int
2459 xmlPatternMatch(xmlPatternPtr comp, xmlNodePtr node)
2460 {
2461     int ret = 0;
2462 
2463     if ((comp == NULL) || (node == NULL))
2464         return(-1);
2465 
2466     while (comp != NULL) {
2467         ret = xmlPatMatch(comp, node);
2468     if (ret != 0)
2469         return(ret);
2470     comp = comp->next;
2471     }
2472     return(ret);
2473 }
2474 
2475 /**
2476  * xmlPatternGetStreamCtxt:
2477  * @comp: the precompiled pattern
2478  *
2479  * Get a streaming context for that pattern
2480  * Use xmlFreeStreamCtxt to free the context.
2481  *
2482  * Returns a pointer to the context or NULL in case of failure
2483  */
2484 xmlStreamCtxtPtr
2485 xmlPatternGetStreamCtxt(xmlPatternPtr comp)
2486 {
2487     xmlStreamCtxtPtr ret = NULL, cur;
2488 
2489     if ((comp == NULL) || (comp->stream == NULL))
2490         return(NULL);
2491 
2492     while (comp != NULL) {
2493         if (comp->stream == NULL)
2494         goto failed;
2495     cur = xmlNewStreamCtxt(comp->stream);
2496     if (cur == NULL)
2497         goto failed;
2498     if (ret == NULL)
2499         ret = cur;
2500     else {
2501         cur->next = ret->next;
2502         ret->next = cur;
2503     }
2504     cur->flags = comp->flags;
2505     comp = comp->next;
2506     }
2507     return(ret);
2508 failed:
2509     xmlFreeStreamCtxt(ret);
2510     return(NULL);
2511 }
2512 
2513 /**
2514  * xmlPatternStreamable:
2515  * @comp: the precompiled pattern
2516  *
2517  * Check if the pattern is streamable i.e. xmlPatternGetStreamCtxt()
2518  * should work.
2519  *
2520  * Returns 1 if streamable, 0 if not and -1 in case of error.
2521  */
2522 int
2523 xmlPatternStreamable(xmlPatternPtr comp) {
2524     if (comp == NULL)
2525         return(-1);
2526     while (comp != NULL) {
2527         if (comp->stream == NULL)
2528         return(0);
2529     comp = comp->next;
2530     }
2531     return(1);
2532 }
2533 
2534 /**
2535  * xmlPatternMaxDepth:
2536  * @comp: the precompiled pattern
2537  *
2538  * Check the maximum depth reachable by a pattern
2539  *
2540  * Returns -2 if no limit (using //), otherwise the depth,
2541  *         and -1 in case of error
2542  */
2543 int
2544 xmlPatternMaxDepth(xmlPatternPtr comp) {
2545     int ret = 0, i;
2546     if (comp == NULL)
2547         return(-1);
2548     while (comp != NULL) {
2549         if (comp->stream == NULL)
2550         return(-1);
2551     for (i = 0;i < comp->stream->nbStep;i++)
2552         if (comp->stream->steps[i].flags & XML_STREAM_STEP_DESC)
2553             return(-2);
2554     if (comp->stream->nbStep > ret)
2555         ret = comp->stream->nbStep;
2556     comp = comp->next;
2557     }
2558     return(ret);
2559 }
2560 
2561 /**
2562  * xmlPatternMinDepth:
2563  * @comp: the precompiled pattern
2564  *
2565  * Check the minimum depth reachable by a pattern, 0 mean the / or . are
2566  * part of the set.
2567  *
2568  * Returns -1 in case of error otherwise the depth,
2569  *
2570  */
2571 int
2572 xmlPatternMinDepth(xmlPatternPtr comp) {
2573     int ret = 12345678;
2574     if (comp == NULL)
2575         return(-1);
2576     while (comp != NULL) {
2577         if (comp->stream == NULL)
2578         return(-1);
2579     if (comp->stream->nbStep < ret)
2580         ret = comp->stream->nbStep;
2581     if (ret == 0)
2582         return(0);
2583     comp = comp->next;
2584     }
2585     return(ret);
2586 }
2587 
2588 /**
2589  * xmlPatternFromRoot:
2590  * @comp: the precompiled pattern
2591  *
2592  * Check if the pattern must be looked at from the root.
2593  *
2594  * Returns 1 if true, 0 if false and -1 in case of error
2595  */
2596 int
2597 xmlPatternFromRoot(xmlPatternPtr comp) {
2598     if (comp == NULL)
2599         return(-1);
2600     while (comp != NULL) {
2601         if (comp->stream == NULL)
2602         return(-1);
2603     if (comp->flags & PAT_FROM_ROOT)
2604         return(1);
2605     comp = comp->next;
2606     }
2607     return(0);
2608 
2609 }
2610 
2611 #define bottom_pattern
2612 #include "elfgcchack.h"
2613 #endif /* LIBXML_PATTERN_ENABLED */