pattern.c

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