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 #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 */