gettext-tools/gnulib-lib/libxml/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             if (token == NULL) {
1095                 if (CUR == '*') {
1096                     NEXT;
1097                     PUSH(XML_OP_NS, URL, NULL);
1098                 } else {
1099                     ERROR(NULL, NULL, NULL,
1100                             "xmlCompileStepPattern : Name expected\n");
1101                     ctxt->error = 1;
1102                     goto error;
1103                 }
1104             } else {
1105                 PUSH(XML_OP_ELEM, token, URL);
1106             }
1107         } else {
1108             NEXT;
1109             if (xmlStrEqual(name, (const xmlChar *) "child")) {
1110                 XML_PAT_FREE_STRING(ctxt, name);
1111                 name = xmlPatScanName(ctxt);
1112                 if (name == NULL) {
1113                     if (CUR == '*') {
1114                         NEXT;
1115                         PUSH(XML_OP_ALL, NULL, NULL);
1116                         return;
1117                     } else {
1118                         ERROR(NULL, NULL, NULL,
1119                             "xmlCompileStepPattern : QName expected\n");
1120                         ctxt->error = 1;
1121                         goto error;
1122                     }
1123                 }
1124                 if (CUR == ':') {
1125                     xmlChar *prefix = name;
1126                     int i;
1127
1128                     NEXT;
1129                     if (IS_BLANK_CH(CUR)) {
1130                         ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
1131                         ctxt->error = 1;
1132                         goto error;
1133                     }
1134                     /*
1135                     * This is a namespace match
1136                     */
1137                     token = xmlPatScanName(ctxt);
1138                     if ((prefix[0] == 'x') &&
1139                         (prefix[1] == 'm') &&
1140                         (prefix[2] == 'l') &&
1141                         (prefix[3] == 0))
1142                     {
1143                         XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
1144                     } else {
1145                         for (i = 0;i < ctxt->nb_namespaces;i++) {
1146                             if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
1147                                 XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
1148                                 break;
1149                             }
1150                         }
1151                         if (i >= ctxt->nb_namespaces) {
1152                             ERROR5(NULL, NULL, NULL,
1153                                 "xmlCompileStepPattern : no namespace bound "
1154                                 "to prefix %s\n", prefix);
1155                             ctxt->error = 1;
1156                             goto error;
1157                         }
1158                     }
1159                     XML_PAT_FREE_STRING(ctxt, prefix);
1160                     if (token == NULL) {
1161                         if (CUR == '*') {
1162                             NEXT;
1163                             PUSH(XML_OP_NS, URL, NULL);
1164                         } else {
1165                             ERROR(NULL, NULL, NULL,
1166                                 "xmlCompileStepPattern : Name expected\n");
1167                             ctxt->error = 1;
1168                             goto error;
1169                         }
1170                     } else {
1171                         PUSH(XML_OP_CHILD, token, URL);
1172                     }
1173                 } else
1174                     PUSH(XML_OP_CHILD, name, NULL);
1175                 return;
1176             } else if (xmlStrEqual(name, (const xmlChar *) "attribute")) {
1177                 XML_PAT_FREE_STRING(ctxt, name)
1178                 name = NULL;
1179                 if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
1180                     ERROR5(NULL, NULL, NULL,
1181                         "Unexpected attribute axis in '%s'.\n", ctxt->base);
1182                     ctxt->error = 1;
1183                     goto error;
1184                 }
1185                 xmlCompileAttributeTest(ctxt);
1186                 if (ctxt->error != 0)
1187                     goto error;
1188                 return;
1189             } else {
1190                 ERROR5(NULL, NULL, NULL,
1191                     "The 'element' or 'attribute' axis is expected.\n", NULL);
1192                 ctxt->error = 1;
1193                 goto error;
1194             }
1195         }
1196     } else if (CUR == '*') {
1197         if (name != NULL) {
1198             ctxt->error = 1;
1199             goto error;
1200         }
1201         NEXT;
1202         PUSH(XML_OP_ALL, token, NULL);
1203     } else {
1204         PUSH(XML_OP_ELEM, name, NULL);
1205     }
1206     return;
1207 error:
1208     if (URL != NULL)
1209         XML_PAT_FREE_STRING(ctxt, URL)
1210     if (token != NULL)
1211         XML_PAT_FREE_STRING(ctxt, token)
1212     if (name != NULL)
1213         XML_PAT_FREE_STRING(ctxt, name)
1214 }
1215
1216 /**
1217  * xmlCompilePathPattern:
1218  * @ctxt:  the compilation context
1219  *
1220  * Compile the Path Pattern and generates a precompiled
1221  * form suitable for fast matching.
1222  *
1223  * [5]    Path    ::=    ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1224  */
1225 static void
1226 xmlCompilePathPattern(xmlPatParserContextPtr ctxt) {
1227     SKIP_BLANKS;
1228     if (CUR == '/') {
1229         ctxt->comp->flags |= PAT_FROM_ROOT;
1230     } else if ((CUR == '.') || (ctxt->comp->flags & XML_PATTERN_NOTPATTERN)) {
1231         ctxt->comp->flags |= PAT_FROM_CUR;
1232     }
1233
1234     if ((CUR == '/') && (NXT(1) == '/')) {
1235         PUSH(XML_OP_ANCESTOR, NULL, NULL);
1236         NEXT;
1237         NEXT;
1238     } else if ((CUR == '.') && (NXT(1) == '/') && (NXT(2) == '/')) {
1239         PUSH(XML_OP_ANCESTOR, NULL, NULL);
1240         NEXT;
1241         NEXT;
1242         NEXT;
1243         /* Check for incompleteness. */
1244         SKIP_BLANKS;
1245         if (CUR == 0) {
1246             ERROR5(NULL, NULL, NULL,
1247                "Incomplete expression '%s'.\n", ctxt->base);
1248             ctxt->error = 1;
1249             goto error;
1250         }
1251     }
1252     if (CUR == '@') {
1253         NEXT;
1254         xmlCompileAttributeTest(ctxt);
1255         SKIP_BLANKS;
1256         /* TODO: check for incompleteness */
1257         if (CUR != 0) {
1258             xmlCompileStepPattern(ctxt);
1259             if (ctxt->error != 0)
1260                 goto error;
1261         }
1262     } else {
1263         if (CUR == '/') {
1264             PUSH(XML_OP_ROOT, NULL, NULL);
1265             NEXT;
1266             /* Check for incompleteness. */
1267             SKIP_BLANKS;
1268             if (CUR == 0) {
1269                 ERROR5(NULL, NULL, NULL,
1270                     "Incomplete expression '%s'.\n", ctxt->base);
1271                 ctxt->error = 1;
1272                 goto error;
1273             }
1274         }
1275         xmlCompileStepPattern(ctxt);
1276         if (ctxt->error != 0)
1277             goto error;
1278         SKIP_BLANKS;
1279         while (CUR == '/') {
1280             if (NXT(1) == '/') {
1281                 PUSH(XML_OP_ANCESTOR, NULL, NULL);
1282                 NEXT;
1283                 NEXT;
1284                 SKIP_BLANKS;
1285                 xmlCompileStepPattern(ctxt);
1286                 if (ctxt->error != 0)
1287                     goto error;
1288             } else {
1289                 PUSH(XML_OP_PARENT, NULL, NULL);
1290                 NEXT;
1291                 SKIP_BLANKS;
1292                 if (CUR == 0) {
1293                     ERROR5(NULL, NULL, NULL,
1294                     "Incomplete expression '%s'.\n", ctxt->base);
1295                     ctxt->error = 1;
1296                     goto error;
1297                 }
1298                 xmlCompileStepPattern(ctxt);
1299                 if (ctxt->error != 0)
1300                     goto error;
1301             }
1302         }
1303     }
1304     if (CUR != 0) {
1305         ERROR5(NULL, NULL, NULL,
1306                "Failed to compile pattern %s\n", ctxt->base);
1307         ctxt->error = 1;
1308     }
1309 error:
1310     return;
1311 }
1312
1313 /**
1314  * xmlCompileIDCXPathPath:
1315  * @ctxt:  the compilation context
1316  *
1317  * Compile the Path Pattern and generates a precompiled
1318  * form suitable for fast matching.
1319  *
1320  * [5]    Path    ::=    ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1321  */
1322 static void
1323 xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt) {
1324     SKIP_BLANKS;
1325     if (CUR == '/') {
1326         ERROR5(NULL, NULL, NULL,
1327             "Unexpected selection of the document root in '%s'.\n",
1328             ctxt->base);
1329         goto error;
1330     }
1331     ctxt->comp->flags |= PAT_FROM_CUR;
1332
1333     if (CUR == '.') {
1334         /* "." - "self::node()" */
1335         NEXT;
1336         SKIP_BLANKS;
1337         if (CUR == 0) {
1338             /*
1339             * Selection of the context node.
1340             */
1341             PUSH(XML_OP_ELEM, NULL, NULL);
1342             return;
1343         }
1344         if (CUR != '/') {
1345             /* TODO: A more meaningful error message. */
1346             ERROR5(NULL, NULL, NULL,
1347             "Unexpected token after '.' in '%s'.\n", ctxt->base);
1348             goto error;
1349         }
1350         /* "./" - "self::node()/" */
1351         NEXT;
1352         SKIP_BLANKS;
1353         if (CUR == '/') {
1354             if (IS_BLANK_CH(PEEKPREV(1))) {
1355                 /*
1356                 * Disallow "./ /"
1357                 */
1358                 ERROR5(NULL, NULL, NULL,
1359                     "Unexpected '/' token in '%s'.\n", ctxt->base);
1360                 goto error;
1361             }
1362             /* ".//" - "self:node()/descendant-or-self::node()/" */
1363             PUSH(XML_OP_ANCESTOR, NULL, NULL);
1364             NEXT;
1365             SKIP_BLANKS;
1366         }
1367         if (CUR == 0)
1368             goto error_unfinished;
1369     }
1370     /*
1371     * Process steps.
1372     */
1373     do {
1374         xmlCompileStepPattern(ctxt);
1375         if (ctxt->error != 0)
1376             goto error;
1377         SKIP_BLANKS;
1378         if (CUR != '/')
1379             break;
1380         PUSH(XML_OP_PARENT, NULL, NULL);
1381         NEXT;
1382         SKIP_BLANKS;
1383         if (CUR == '/') {
1384             /*
1385             * Disallow subsequent '//'.
1386             */
1387             ERROR5(NULL, NULL, NULL,
1388                 "Unexpected subsequent '//' in '%s'.\n",
1389                 ctxt->base);
1390             goto error;
1391         }
1392         if (CUR == 0)
1393             goto error_unfinished;
1394
1395     } while (CUR != 0);
1396
1397     if (CUR != 0) {
1398         ERROR5(NULL, NULL, NULL,
1399             "Failed to compile expression '%s'.\n", ctxt->base);
1400         ctxt->error = 1;
1401     }
1402     return;
1403 error:
1404     ctxt->error = 1;
1405     return;
1406
1407 error_unfinished:
1408     ctxt->error = 1;
1409     ERROR5(NULL, NULL, NULL,
1410         "Unfinished expression '%s'.\n", ctxt->base);
1411     return;
1412 }
1413
1414 /************************************************************************
1415  *                                                                      *
1416  *                      The streaming code                              *
1417  *                                                                      *
1418  ************************************************************************/
1419
1420 #ifdef DEBUG_STREAMING
1421 static void
1422 xmlDebugStreamComp(xmlStreamCompPtr stream) {
1423     int i;
1424
1425     if (stream == NULL) {
1426         printf("Stream: NULL\n");
1427         return;
1428     }
1429     printf("Stream: %d steps\n", stream->nbStep);
1430     for (i = 0;i < stream->nbStep;i++) {
1431         if (stream->steps[i].ns != NULL) {
1432             printf("{%s}", stream->steps[i].ns);
1433         }
1434         if (stream->steps[i].name == NULL) {
1435             printf("* ");
1436         } else {
1437             printf("%s ", stream->steps[i].name);
1438         }
1439         if (stream->steps[i].flags & XML_STREAM_STEP_ROOT)
1440             printf("root ");
1441         if (stream->steps[i].flags & XML_STREAM_STEP_DESC)
1442             printf("// ");
1443         if (stream->steps[i].flags & XML_STREAM_STEP_FINAL)
1444             printf("final ");
1445         printf("\n");
1446     }
1447 }
1448 static void
1449 xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt, int match) {
1450     int i;
1451
1452     if (ctxt == NULL) {
1453         printf("Stream: NULL\n");
1454         return;
1455     }
1456     printf("Stream: level %d, %d states: ", ctxt->level, ctxt->nbState);
1457     if (match)
1458         printf("matches\n");
1459     else
1460         printf("\n");
1461     for (i = 0;i < ctxt->nbState;i++) {
1462         if (ctxt->states[2 * i] < 0)
1463             printf(" %d: free\n", i);
1464         else {
1465             printf(" %d: step %d, level %d", i, ctxt->states[2 * i],
1466                    ctxt->states[(2 * i) + 1]);
1467             if (ctxt->comp->steps[ctxt->states[2 * i]].flags &
1468                 XML_STREAM_STEP_DESC)
1469                 printf(" //\n");
1470             else
1471                 printf("\n");
1472         }
1473     }
1474 }
1475 #endif
1476 /**
1477  * xmlNewStreamComp:
1478  * @size: the number of expected steps
1479  *
1480  * build a new compiled pattern for streaming
1481  *
1482  * Returns the new structure or NULL in case of error.
1483  */
1484 static xmlStreamCompPtr
1485 xmlNewStreamComp(int size) {
1486     xmlStreamCompPtr cur;
1487
1488     if (size < 4)
1489         size  = 4;
1490
1491     cur = (xmlStreamCompPtr) xmlMalloc(sizeof(xmlStreamComp));
1492     if (cur == NULL) {
1493         ERROR(NULL, NULL, NULL,
1494                 "xmlNewStreamComp: malloc failed\n");
1495         return(NULL);
1496     }
1497     memset(cur, 0, sizeof(xmlStreamComp));
1498     cur->steps = (xmlStreamStepPtr) xmlMalloc(size * sizeof(xmlStreamStep));
1499     if (cur->steps == NULL) {
1500         xmlFree(cur);
1501         ERROR(NULL, NULL, NULL,
1502               "xmlNewStreamComp: malloc failed\n");
1503         return(NULL);
1504     }
1505     cur->nbStep = 0;
1506     cur->maxStep = size;
1507     return(cur);
1508 }
1509
1510 /**
1511  * xmlFreeStreamComp:
1512  * @comp: the compiled pattern for streaming
1513  *
1514  * Free the compiled pattern for streaming
1515  */
1516 static void
1517 xmlFreeStreamComp(xmlStreamCompPtr comp) {
1518     if (comp != NULL) {
1519         if (comp->steps != NULL)
1520             xmlFree(comp->steps);
1521         if (comp->dict != NULL)
1522             xmlDictFree(comp->dict);
1523         xmlFree(comp);
1524     }
1525 }
1526
1527 /**
1528  * xmlStreamCompAddStep:
1529  * @comp: the compiled pattern for streaming
1530  * @name: the first string, the name, or NULL for *
1531  * @ns: the second step, the namespace name
1532  * @flags: the flags for that step
1533  *
1534  * Add a new step to the compiled pattern
1535  *
1536  * Returns -1 in case of error or the step index if successful
1537  */
1538 static int
1539 xmlStreamCompAddStep(xmlStreamCompPtr comp, const xmlChar *name,
1540                      const xmlChar *ns, int nodeType, int flags) {
1541     xmlStreamStepPtr cur;
1542
1543     if (comp->nbStep >= comp->maxStep) {
1544         cur = (xmlStreamStepPtr) xmlRealloc(comp->steps,
1545                                  comp->maxStep * 2 * sizeof(xmlStreamStep));
1546         if (cur == NULL) {
1547             ERROR(NULL, NULL, NULL,
1548                   "xmlNewStreamComp: malloc failed\n");
1549             return(-1);
1550         }
1551         comp->steps = cur;
1552         comp->maxStep *= 2;
1553     }
1554     cur = &comp->steps[comp->nbStep++];
1555     cur->flags = flags;
1556     cur->name = name;
1557     cur->ns = ns;
1558     cur->nodeType = nodeType;
1559     return(comp->nbStep - 1);
1560 }
1561
1562 /**
1563  * xmlStreamCompile:
1564  * @comp: the precompiled pattern
1565  *
1566  * Tries to stream compile a pattern
1567  *
1568  * Returns -1 in case of failure and 0 in case of success.
1569  */
1570 static int
1571 xmlStreamCompile(xmlPatternPtr comp) {
1572     xmlStreamCompPtr stream;
1573     int i, s = 0, root = 0, flags = 0, prevs = -1;
1574     xmlStepOp step;
1575
1576     if ((comp == NULL) || (comp->steps == NULL))
1577         return(-1);
1578     /*
1579      * special case for .
1580      */
1581     if ((comp->nbStep == 1) &&
1582         (comp->steps[0].op == XML_OP_ELEM) &&
1583         (comp->steps[0].value == NULL) &&
1584         (comp->steps[0].value2 == NULL)) {
1585         stream = xmlNewStreamComp(0);
1586         if (stream == NULL)
1587             return(-1);
1588         /* Note that the stream will have no steps in this case. */
1589         stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1590         comp->stream = stream;
1591         return(0);
1592     }
1593
1594     stream = xmlNewStreamComp((comp->nbStep / 2) + 1);
1595     if (stream == NULL)
1596         return(-1);
1597     if (comp->dict != NULL) {
1598         stream->dict = comp->dict;
1599         xmlDictReference(stream->dict);
1600     }
1601
1602     i = 0;
1603     if (comp->flags & PAT_FROM_ROOT)
1604         stream->flags |= XML_STREAM_FROM_ROOT;
1605
1606     for (;i < comp->nbStep;i++) {
1607         step = comp->steps[i];
1608         switch (step.op) {
1609             case XML_OP_END:
1610                 break;
1611             case XML_OP_ROOT:
1612                 if (i != 0)
1613                     goto error;
1614                 root = 1;
1615                 break;
1616             case XML_OP_NS:
1617                 s = xmlStreamCompAddStep(stream, NULL, step.value,
1618                     XML_ELEMENT_NODE, flags);
1619                 if (s < 0)
1620                     goto error;
1621                 prevs = s;
1622                 flags = 0;
1623                 break;
1624             case XML_OP_ATTR:
1625                 flags |= XML_STREAM_STEP_ATTR;
1626                 prevs = -1;
1627                 s = xmlStreamCompAddStep(stream,
1628                     step.value, step.value2, XML_ATTRIBUTE_NODE, flags);
1629                 flags = 0;
1630                 if (s < 0)
1631                     goto error;
1632                 break;
1633             case XML_OP_ELEM:
1634                 if ((step.value == NULL) && (step.value2 == NULL)) {
1635                     /*
1636                     * We have a "." or "self::node()" here.
1637                     * Eliminate redundant self::node() tests like in "/./."
1638                     * or "//./"
1639                     * The only case we won't eliminate is "//.", i.e. if
1640                     * self::node() is the last node test and we had
1641                     * continuation somewhere beforehand.
1642                     */
1643                     if ((comp->nbStep == i + 1) &&
1644                         (flags & XML_STREAM_STEP_DESC)) {
1645                         /*
1646                         * Mark the special case where the expression resolves
1647                         * to any type of node.
1648                         */
1649                         if (comp->nbStep == i + 1) {
1650                             stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1651                         }
1652                         flags |= XML_STREAM_STEP_NODE;
1653                         s = xmlStreamCompAddStep(stream, NULL, NULL,
1654                             XML_STREAM_ANY_NODE, flags);
1655                         if (s < 0)
1656                             goto error;
1657                         flags = 0;
1658                         /*
1659                         * If there was a previous step, mark it to be added to
1660                         * the result node-set; this is needed since only
1661                         * the last step will be marked as "final" and only
1662                         * "final" nodes are added to the resulting set.
1663                         */
1664                         if (prevs != -1) {
1665                             stream->steps[prevs].flags |= XML_STREAM_STEP_IN_SET;
1666                             prevs = -1;
1667                         }
1668                         break;
1669
1670                     } else {
1671                         /* Just skip this one. */
1672                         continue;
1673                     }
1674                 }
1675                 /* An element node. */
1676                 s = xmlStreamCompAddStep(stream, step.value, step.value2,
1677                     XML_ELEMENT_NODE, flags);
1678                 if (s < 0)
1679                     goto error;
1680                 prevs = s;
1681                 flags = 0;
1682                 break;
1683             case XML_OP_CHILD:
1684                 /* An element node child. */
1685                 s = xmlStreamCompAddStep(stream, step.value, step.value2,
1686                     XML_ELEMENT_NODE, flags);
1687                 if (s < 0)
1688                     goto error;
1689                 prevs = s;
1690                 flags = 0;
1691                 break;
1692             case XML_OP_ALL:
1693                 s = xmlStreamCompAddStep(stream, NULL, NULL,
1694                     XML_ELEMENT_NODE, flags);
1695                 if (s < 0)
1696                     goto error;
1697                 prevs = s;
1698                 flags = 0;
1699                 break;
1700             case XML_OP_PARENT:
1701                 break;
1702             case XML_OP_ANCESTOR:
1703                 /* Skip redundant continuations. */
1704                 if (flags & XML_STREAM_STEP_DESC)
1705                     break;
1706                 flags |= XML_STREAM_STEP_DESC;
1707                 /*
1708                 * Mark the expression as having "//".
1709                 */
1710                 if ((stream->flags & XML_STREAM_DESC) == 0)
1711                     stream->flags |= XML_STREAM_DESC;
1712                 break;
1713         }
1714     }
1715     if ((! root) && (comp->flags & XML_PATTERN_NOTPATTERN) == 0) {
1716         /*
1717         * If this should behave like a real pattern, we will mark
1718         * the first step as having "//", to be reentrant on every
1719         * tree level.
1720         */
1721         if ((stream->flags & XML_STREAM_DESC) == 0)
1722             stream->flags |= XML_STREAM_DESC;
1723
1724         if (stream->nbStep > 0) {
1725             if ((stream->steps[0].flags & XML_STREAM_STEP_DESC) == 0)
1726                 stream->steps[0].flags |= XML_STREAM_STEP_DESC;
1727         }
1728     }
1729     if (stream->nbStep <= s)
1730         goto error;
1731     stream->steps[s].flags |= XML_STREAM_STEP_FINAL;
1732     if (root)
1733         stream->steps[0].flags |= XML_STREAM_STEP_ROOT;
1734 #ifdef DEBUG_STREAMING
1735     xmlDebugStreamComp(stream);
1736 #endif
1737     comp->stream = stream;
1738     return(0);
1739 error:
1740     xmlFreeStreamComp(stream);
1741     return(0);
1742 }
1743
1744 /**
1745  * xmlNewStreamCtxt:
1746  * @size: the number of expected states
1747  *
1748  * build a new stream context
1749  *
1750  * Returns the new structure or NULL in case of error.
1751  */
1752 static xmlStreamCtxtPtr
1753 xmlNewStreamCtxt(xmlStreamCompPtr stream) {
1754     xmlStreamCtxtPtr cur;
1755
1756     cur = (xmlStreamCtxtPtr) xmlMalloc(sizeof(xmlStreamCtxt));
1757     if (cur == NULL) {
1758         ERROR(NULL, NULL, NULL,
1759                 "xmlNewStreamCtxt: malloc failed\n");
1760         return(NULL);
1761     }
1762     memset(cur, 0, sizeof(xmlStreamCtxt));
1763     cur->states = (int *) xmlMalloc(4 * 2 * sizeof(int));
1764     if (cur->states == NULL) {
1765         xmlFree(cur);
1766         ERROR(NULL, NULL, NULL,
1767               "xmlNewStreamCtxt: malloc failed\n");
1768         return(NULL);
1769     }
1770     cur->nbState = 0;
1771     cur->maxState = 4;
1772     cur->level = 0;
1773     cur->comp = stream;
1774     cur->blockLevel = -1;
1775     return(cur);
1776 }
1777
1778 /**
1779  * xmlFreeStreamCtxt:
1780  * @stream: the stream context
1781  *
1782  * Free the stream context
1783  */
1784 void
1785 xmlFreeStreamCtxt(xmlStreamCtxtPtr stream) {
1786     xmlStreamCtxtPtr next;
1787
1788     while (stream != NULL) {
1789         next = stream->next;
1790         if (stream->states != NULL)
1791             xmlFree(stream->states);
1792         xmlFree(stream);
1793         stream = next;
1794     }
1795 }
1796
1797 /**
1798  * xmlStreamCtxtAddState:
1799  * @comp: the stream context
1800  * @idx: the step index for that streaming state
1801  *
1802  * Add a new state to the stream context
1803  *
1804  * Returns -1 in case of error or the state index if successful
1805  */
1806 static int
1807 xmlStreamCtxtAddState(xmlStreamCtxtPtr comp, int idx, int level) {
1808     int i;
1809     for (i = 0;i < comp->nbState;i++) {
1810         if (comp->states[2 * i] < 0) {
1811             comp->states[2 * i] = idx;
1812             comp->states[2 * i + 1] = level;
1813             return(i);
1814         }
1815     }
1816     if (comp->nbState >= comp->maxState) {
1817         int *cur;
1818
1819         cur = (int *) xmlRealloc(comp->states,
1820                                  comp->maxState * 4 * sizeof(int));
1821         if (cur == NULL) {
1822             ERROR(NULL, NULL, NULL,
1823                   "xmlNewStreamCtxt: malloc failed\n");
1824             return(-1);
1825         }
1826         comp->states = cur;
1827         comp->maxState *= 2;
1828     }
1829     comp->states[2 * comp->nbState] = idx;
1830     comp->states[2 * comp->nbState++ + 1] = level;
1831     return(comp->nbState - 1);
1832 }
1833
1834 /**
1835  * xmlStreamPushInternal:
1836  * @stream: the stream context
1837  * @name: the current name
1838  * @ns: the namespace name
1839  * @nodeType: the type of the node
1840  *
1841  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
1842  * indicated a dictionary, then strings for name and ns will be expected
1843  * to come from the dictionary.
1844  * Both @name and @ns being NULL means the / i.e. the root of the document.
1845  * This can also act as a reset.
1846  *
1847  * Returns: -1 in case of error, 1 if the current state in the stream is a
1848  *    match and 0 otherwise.
1849  */
1850 static int
1851 xmlStreamPushInternal(xmlStreamCtxtPtr stream,
1852                       const xmlChar *name, const xmlChar *ns,
1853                       int nodeType) {
1854     int ret = 0, err = 0, final = 0, tmp, i, m, match, stepNr, desc;
1855     xmlStreamCompPtr comp;
1856     xmlStreamStep step;
1857 #ifdef DEBUG_STREAMING
1858     xmlStreamCtxtPtr orig = stream;
1859 #endif
1860
1861     if ((stream == NULL) || (stream->nbState < 0))
1862         return(-1);
1863
1864     while (stream != NULL) {
1865         comp = stream->comp;
1866
1867         if ((nodeType == XML_ELEMENT_NODE) &&
1868             (name == NULL) && (ns == NULL)) {
1869             /* We have a document node here (or a reset). */
1870             stream->nbState = 0;
1871             stream->level = 0;
1872             stream->blockLevel = -1;
1873             if (comp->flags & XML_STREAM_FROM_ROOT) {
1874                 if (comp->nbStep == 0) {
1875                     /* TODO: We have a "/." here? */
1876                     ret = 1;
1877                 } else {
1878                     if ((comp->nbStep == 1) &&
1879                         (comp->steps[0].nodeType == XML_STREAM_ANY_NODE) &&
1880                         (comp->steps[0].flags & XML_STREAM_STEP_DESC))
1881                     {
1882                         /*
1883                         * In the case of "//." the document node will match
1884                         * as well.
1885                         */
1886                         ret = 1;
1887                     } else if (comp->steps[0].flags & XML_STREAM_STEP_ROOT) {
1888                         /* TODO: Do we need this ? */
1889                         tmp = xmlStreamCtxtAddState(stream, 0, 0);
1890                         if (tmp < 0)
1891                             err++;
1892                     }
1893                 }
1894             }
1895             stream = stream->next;
1896             continue; /* while */
1897         }
1898
1899         /*
1900         * Fast check for ".".
1901         */
1902         if (comp->nbStep == 0) {
1903             /*
1904              * / and . are handled at the XPath node set creation
1905              * level by checking min depth
1906              */
1907             if (stream->flags & XML_PATTERN_XPATH) {
1908                 stream = stream->next;
1909                 continue; /* while */
1910             }
1911             /*
1912             * For non-pattern like evaluation like XML Schema IDCs
1913             * or traditional XPath expressions, this will match if
1914             * we are at the first level only, otherwise on every level.
1915             */
1916             if ((nodeType != XML_ATTRIBUTE_NODE) &&
1917                 (((stream->flags & XML_PATTERN_NOTPATTERN) == 0) ||
1918                 (stream->level == 0))) {
1919                     ret = 1;
1920             }
1921             stream->level++;
1922             goto stream_next;
1923         }
1924         if (stream->blockLevel != -1) {
1925             /*
1926             * Skip blocked expressions.
1927             */
1928             stream->level++;
1929             goto stream_next;
1930         }
1931
1932         if ((nodeType != XML_ELEMENT_NODE) &&
1933             (nodeType != XML_ATTRIBUTE_NODE) &&
1934             ((comp->flags & XML_STREAM_FINAL_IS_ANY_NODE) == 0)) {
1935             /*
1936             * No need to process nodes of other types if we don't
1937             * resolve to those types.
1938             * TODO: Do we need to block the context here?
1939             */
1940             stream->level++;
1941             goto stream_next;
1942         }
1943
1944         /*
1945          * Check evolution of existing states
1946          */
1947         i = 0;
1948         m = stream->nbState;
1949         while (i < m) {
1950             if ((comp->flags & XML_STREAM_DESC) == 0) {
1951                 /*
1952                 * If there is no "//", then only the last
1953                 * added state is of interest.
1954                 */
1955                 stepNr = stream->states[2 * (stream->nbState -1)];
1956                 /*
1957                 * TODO: Security check, should not happen, remove it.
1958                 */
1959                 if (stream->states[(2 * (stream->nbState -1)) + 1] <
1960                     stream->level) {
1961                     return (-1);
1962                 }
1963                 desc = 0;
1964                 /* loop-stopper */
1965                 i = m;
1966             } else {
1967                 /*
1968                 * If there are "//", then we need to process every "//"
1969                 * occuring in the states, plus any other state for this
1970                 * level.
1971                 */
1972                 stepNr = stream->states[2 * i];
1973
1974                 /* TODO: should not happen anymore: dead states */
1975                 if (stepNr < 0)
1976                     goto next_state;
1977
1978                 tmp = stream->states[(2 * i) + 1];
1979
1980                 /* skip new states just added */
1981                 if (tmp > stream->level)
1982                     goto next_state;
1983
1984                 /* skip states at ancestor levels, except if "//" */
1985                 desc = comp->steps[stepNr].flags & XML_STREAM_STEP_DESC;
1986                 if ((tmp < stream->level) && (!desc))
1987                     goto next_state;
1988             }
1989             /*
1990             * Check for correct node-type.
1991             */
1992             step = comp->steps[stepNr];
1993             if (step.nodeType != nodeType) {
1994                 if (step.nodeType == XML_ATTRIBUTE_NODE) {
1995                     /*
1996                     * Block this expression for deeper evaluation.
1997                     */
1998                     if ((comp->flags & XML_STREAM_DESC) == 0)
1999                         stream->blockLevel = stream->level +1;
2000                     goto next_state;
2001                 } else if (step.nodeType != XML_STREAM_ANY_NODE)
2002                     goto next_state;
2003             }
2004             /*
2005             * Compare local/namespace-name.
2006             */
2007             match = 0;
2008             if (step.nodeType == XML_STREAM_ANY_NODE) {
2009                 match = 1;
2010             } else if (step.name == NULL) {
2011                 if (step.ns == NULL) {
2012                     /*
2013                     * This lets through all elements/attributes.
2014                     */
2015                     match = 1;
2016                 } else if (ns != NULL)
2017                     match = xmlStrEqual(step.ns, ns);
2018             } else if (((step.ns != NULL) == (ns != NULL)) &&
2019                 (name != NULL) &&
2020                 (step.name[0] == name[0]) &&
2021                 xmlStrEqual(step.name, name) &&
2022                 ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2023             {
2024                 match = 1;
2025             }
2026 #if 0
2027 /*
2028 * TODO: Pointer comparison won't work, since not guaranteed that the given
2029 *  values are in the same dict; especially if it's the namespace name,
2030 *  normally coming from ns->href. We need a namespace dict mechanism !
2031 */
2032             } else if (comp->dict) {
2033                 if (step.name == NULL) {
2034                     if (step.ns == NULL)
2035                         match = 1;
2036                     else
2037                         match = (step.ns == ns);
2038                 } else {
2039                     match = ((step.name == name) && (step.ns == ns));
2040                 }
2041 #endif /* if 0 ------------------------------------------------------- */
2042             if (match) {
2043                 final = step.flags & XML_STREAM_STEP_FINAL;
2044                 if (desc) {
2045                     if (final) {
2046                         ret = 1;
2047                     } else {
2048                         /* descending match create a new state */
2049                         xmlStreamCtxtAddState(stream, stepNr + 1,
2050                                               stream->level + 1);
2051                     }
2052                 } else {
2053                     if (final) {
2054                         ret = 1;
2055                     } else {
2056                         xmlStreamCtxtAddState(stream, stepNr + 1,
2057                                               stream->level + 1);
2058                     }
2059                 }
2060                 if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2061                     /*
2062                     * Check if we have a special case like "foo/bar//.", where
2063                     * "foo" is selected as well.
2064                     */
2065                     ret = 1;
2066                 }
2067             }
2068             if (((comp->flags & XML_STREAM_DESC) == 0) &&
2069                 ((! match) || final))  {
2070                 /*
2071                 * Mark this expression as blocked for any evaluation at
2072                 * deeper levels. Note that this includes "/foo"
2073                 * expressions if the *pattern* behaviour is used.
2074                 */
2075                 stream->blockLevel = stream->level +1;
2076             }
2077 next_state:
2078             i++;
2079         }
2080
2081         stream->level++;
2082
2083         /*
2084         * Re/enter the expression.
2085         * Don't reenter if it's an absolute expression like "/foo",
2086         *   except "//foo".
2087         */
2088         step = comp->steps[0];
2089         if (step.flags & XML_STREAM_STEP_ROOT)
2090             goto stream_next;
2091
2092         desc = step.flags & XML_STREAM_STEP_DESC;
2093         if (stream->flags & XML_PATTERN_NOTPATTERN) {
2094             /*
2095             * Re/enter the expression if it is a "descendant" one,
2096             * or if we are at the 1st level of evaluation.
2097             */
2098
2099             if (stream->level == 1) {
2100                 if (XML_STREAM_XS_IDC(stream)) {
2101                     /*
2102                     * XS-IDC: The missing "self::node()" will always
2103                     * match the first given node.
2104                     */
2105                     goto stream_next;
2106                 } else
2107                     goto compare;
2108             }
2109             /*
2110             * A "//" is always reentrant.
2111             */
2112             if (desc)
2113                 goto compare;
2114
2115             /*
2116             * XS-IDC: Process the 2nd level, since the missing
2117             * "self::node()" is responsible for the 2nd level being
2118             * the real start level.
2119             */
2120             if ((stream->level == 2) && XML_STREAM_XS_IDC(stream))
2121                 goto compare;
2122
2123             goto stream_next;
2124         }
2125
2126 compare:
2127         /*
2128         * Check expected node-type.
2129         */
2130         if (step.nodeType != nodeType) {
2131             if (nodeType == XML_ATTRIBUTE_NODE)
2132                 goto stream_next;
2133             else if (step.nodeType != XML_STREAM_ANY_NODE)
2134                 goto stream_next;
2135         }
2136         /*
2137         * Compare local/namespace-name.
2138         */
2139         match = 0;
2140         if (step.nodeType == XML_STREAM_ANY_NODE) {
2141             match = 1;
2142         } else if (step.name == NULL) {
2143             if (step.ns == NULL) {
2144                 /*
2145                 * This lets through all elements/attributes.
2146                 */
2147                 match = 1;
2148             } else if (ns != NULL)
2149                 match = xmlStrEqual(step.ns, ns);
2150         } else if (((step.ns != NULL) == (ns != NULL)) &&
2151             (name != NULL) &&
2152             (step.name[0] == name[0]) &&
2153             xmlStrEqual(step.name, name) &&
2154             ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2155         {
2156             match = 1;
2157         }
2158         final = step.flags & XML_STREAM_STEP_FINAL;
2159         if (match) {
2160             if (final)
2161                 ret = 1;
2162             else
2163                 xmlStreamCtxtAddState(stream, 1, stream->level);
2164             if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2165                 /*
2166                 * Check if we have a special case like "foo//.", where
2167                 * "foo" is selected as well.
2168                 */
2169                 ret = 1;
2170             }
2171         }
2172         if (((comp->flags & XML_STREAM_DESC) == 0) &&
2173             ((! match) || final))  {
2174             /*
2175             * Mark this expression as blocked for any evaluation at
2176             * deeper levels.
2177             */
2178             stream->blockLevel = stream->level;
2179         }
2180
2181 stream_next:
2182         stream = stream->next;
2183     } /* while stream != NULL */
2184
2185     if (err > 0)
2186         ret = -1;
2187 #ifdef DEBUG_STREAMING
2188     xmlDebugStreamCtxt(orig, ret);
2189 #endif
2190     return(ret);
2191 }
2192
2193 /**
2194  * xmlStreamPush:
2195  * @stream: the stream context
2196  * @name: the current name
2197  * @ns: the namespace name
2198  *
2199  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2200  * indicated a dictionary, then strings for name and ns will be expected
2201  * to come from the dictionary.
2202  * Both @name and @ns being NULL means the / i.e. the root of the document.
2203  * This can also act as a reset.
2204  * Otherwise the function will act as if it has been given an element-node.
2205  *
2206  * Returns: -1 in case of error, 1 if the current state in the stream is a
2207  *    match and 0 otherwise.
2208  */
2209 int
2210 xmlStreamPush(xmlStreamCtxtPtr stream,
2211               const xmlChar *name, const xmlChar *ns) {
2212     return (xmlStreamPushInternal(stream, name, ns, (int) XML_ELEMENT_NODE));
2213 }
2214
2215 /**
2216  * xmlStreamPushNode:
2217  * @stream: the stream context
2218  * @name: the current name
2219  * @ns: the namespace name
2220  * @nodeType: the type of the node being pushed
2221  *
2222  * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2223  * indicated a dictionary, then strings for name and ns will be expected
2224  * to come from the dictionary.
2225  * Both @name and @ns being NULL means the / i.e. the root of the document.
2226  * This can also act as a reset.
2227  * Different from xmlStreamPush() this function can be fed with nodes of type:
2228  * element-, attribute-, text-, cdata-section-, comment- and
2229  * processing-instruction-node.
2230  *
2231  * Returns: -1 in case of error, 1 if the current state in the stream is a
2232  *    match and 0 otherwise.
2233  */
2234 int
2235 xmlStreamPushNode(xmlStreamCtxtPtr stream,
2236                   const xmlChar *name, const xmlChar *ns,
2237                   int nodeType)
2238 {
2239     return (xmlStreamPushInternal(stream, name, ns,
2240         nodeType));
2241 }
2242
2243 /**
2244 * xmlStreamPushAttr:
2245 * @stream: the stream context
2246 * @name: the current name
2247 * @ns: the namespace name
2248 *
2249 * Push new attribute data onto the stream. NOTE: if the call xmlPatterncompile()
2250 * indicated a dictionary, then strings for name and ns will be expected
2251 * to come from the dictionary.
2252 * Both @name and @ns being NULL means the / i.e. the root of the document.
2253 * This can also act as a reset.
2254 * Otherwise the function will act as if it has been given an attribute-node.
2255 *
2256 * Returns: -1 in case of error, 1 if the current state in the stream is a
2257 *    match and 0 otherwise.
2258 */
2259 int
2260 xmlStreamPushAttr(xmlStreamCtxtPtr stream,
2261                   const xmlChar *name, const xmlChar *ns) {
2262     return (xmlStreamPushInternal(stream, name, ns, (int) XML_ATTRIBUTE_NODE));
2263 }
2264
2265 /**
2266  * xmlStreamPop:
2267  * @stream: the stream context
2268  *
2269  * push one level from the stream.
2270  *
2271  * Returns: -1 in case of error, 0 otherwise.
2272  */
2273 int
2274 xmlStreamPop(xmlStreamCtxtPtr stream) {
2275     int i, lev;
2276
2277     if (stream == NULL)
2278         return(-1);
2279     while (stream != NULL) {
2280         /*
2281         * Reset block-level.
2282         */
2283         if (stream->blockLevel == stream->level)
2284             stream->blockLevel = -1;
2285
2286         stream->level--;
2287         if (stream->level < 0)
2288             return(-1);
2289         /*
2290          * Check evolution of existing states
2291          */
2292         for (i = stream->nbState -1; i >= 0; i--) {
2293             /* discard obsoleted states */
2294             lev = stream->states[(2 * i) + 1];
2295             if (lev > stream->level)
2296                 stream->nbState--;
2297             if (lev <= stream->level)
2298                 break;
2299         }
2300         stream = stream->next;
2301     }
2302     return(0);
2303 }
2304
2305 /**
2306  * xmlStreamWantsAnyNode:
2307  * @streamCtxt: the stream context
2308  *
2309  * Query if the streaming pattern additionally needs to be fed with
2310  * text-, cdata-section-, comment- and processing-instruction-nodes.
2311  * If the result is 0 then only element-nodes and attribute-nodes
2312  * need to be pushed.
2313  *
2314  * Returns: 1 in case of need of nodes of the above described types,
2315  *          0 otherwise. -1 on API errors.
2316  */
2317 int
2318 xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt)
2319 {
2320     if (streamCtxt == NULL)
2321         return(-1);
2322     while (streamCtxt != NULL) {
2323         if (streamCtxt->comp->flags & XML_STREAM_FINAL_IS_ANY_NODE)
2324             return(1);
2325         streamCtxt = streamCtxt->next;
2326     }
2327     return(0);
2328 }
2329
2330 /************************************************************************
2331  *                                                                      *
2332  *                      The public interfaces                           *
2333  *                                                                      *
2334  ************************************************************************/
2335
2336 /**
2337  * xmlPatterncompile:
2338  * @pattern: the pattern to compile
2339  * @dict: an optional dictionary for interned strings
2340  * @flags: compilation flags, see xmlPatternFlags
2341  * @namespaces: the prefix definitions, array of [URI, prefix] or NULL
2342  *
2343  * Compile a pattern.
2344  *
2345  * Returns the compiled form of the pattern or NULL in case of error
2346  */
2347 xmlPatternPtr
2348 xmlPatterncompile(const xmlChar *pattern, xmlDict *dict, int flags,
2349                   const xmlChar **namespaces) {
2350     xmlPatternPtr ret = NULL, cur;
2351     xmlPatParserContextPtr ctxt = NULL;
2352     const xmlChar *or, *start;
2353     xmlChar *tmp = NULL;
2354     int type = 0;
2355     int streamable = 1;
2356
2357     if (pattern == NULL)
2358         return(NULL);
2359
2360     start = pattern;
2361     or = start;
2362     while (*or != 0) {
2363         tmp = NULL;
2364         while ((*or != 0) && (*or != '|')) or++;
2365         if (*or == 0)
2366             ctxt = xmlNewPatParserContext(start, dict, namespaces);
2367         else {
2368             tmp = xmlStrndup(start, or - start);
2369             if (tmp != NULL) {
2370                 ctxt = xmlNewPatParserContext(tmp, dict, namespaces);
2371             }
2372             or++;
2373         }
2374         if (ctxt == NULL) goto error;
2375         cur = xmlNewPattern();
2376         if (cur == NULL) goto error;
2377         /*
2378         * Assign string dict.
2379         */
2380         if (dict) {
2381             cur->dict = dict;
2382             xmlDictReference(dict);
2383         }
2384         if (ret == NULL)
2385             ret = cur;
2386         else {
2387             cur->next = ret->next;
2388             ret->next = cur;
2389         }
2390         cur->flags = flags;
2391         ctxt->comp = cur;
2392
2393         if (XML_STREAM_XS_IDC(cur))
2394             xmlCompileIDCXPathPath(ctxt);
2395         else
2396             xmlCompilePathPattern(ctxt);
2397         if (ctxt->error != 0)
2398             goto error;
2399         xmlFreePatParserContext(ctxt);
2400         ctxt = NULL;
2401
2402
2403         if (streamable) {
2404             if (type == 0) {
2405                 type = cur->flags & (PAT_FROM_ROOT | PAT_FROM_CUR);
2406             } else if (type == PAT_FROM_ROOT) {
2407                 if (cur->flags & PAT_FROM_CUR)
2408                     streamable = 0;
2409             } else if (type == PAT_FROM_CUR) {
2410                 if (cur->flags & PAT_FROM_ROOT)
2411                     streamable = 0;
2412             }
2413         }
2414         if (streamable)
2415             xmlStreamCompile(cur);
2416         if (xmlReversePattern(cur) < 0)
2417             goto error;
2418         if (tmp != NULL) {
2419             xmlFree(tmp);
2420             tmp = NULL;
2421         }
2422         start = or;
2423     }
2424     if (streamable == 0) {
2425         cur = ret;
2426         while (cur != NULL) {
2427             if (cur->stream != NULL) {
2428                 xmlFreeStreamComp(cur->stream);
2429                 cur->stream = NULL;
2430             }
2431             cur = cur->next;
2432         }
2433     }
2434
2435     return(ret);
2436 error:
2437     if (ctxt != NULL) xmlFreePatParserContext(ctxt);
2438     if (ret != NULL) xmlFreePattern(ret);
2439     if (tmp != NULL) xmlFree(tmp);
2440     return(NULL);
2441 }
2442
2443 /**
2444  * xmlPatternMatch:
2445  * @comp: the precompiled pattern
2446  * @node: a node
2447  *
2448  * Test whether the node matches the pattern
2449  *
2450  * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
2451  */
2452 int
2453 xmlPatternMatch(xmlPatternPtr comp, xmlNodePtr node)
2454 {
2455     int ret = 0;
2456
2457     if ((comp == NULL) || (node == NULL))
2458         return(-1);
2459
2460     while (comp != NULL) {
2461         ret = xmlPatMatch(comp, node);
2462         if (ret != 0)
2463             return(ret);
2464         comp = comp->next;
2465     }
2466     return(ret);
2467 }
2468
2469 /**
2470  * xmlPatternGetStreamCtxt:
2471  * @comp: the precompiled pattern
2472  *
2473  * Get a streaming context for that pattern
2474  * Use xmlFreeStreamCtxt to free the context.
2475  *
2476  * Returns a pointer to the context or NULL in case of failure
2477  */
2478 xmlStreamCtxtPtr
2479 xmlPatternGetStreamCtxt(xmlPatternPtr comp)
2480 {
2481     xmlStreamCtxtPtr ret = NULL, cur;
2482
2483     if ((comp == NULL) || (comp->stream == NULL))
2484         return(NULL);
2485
2486     while (comp != NULL) {
2487         if (comp->stream == NULL)
2488             goto failed;
2489         cur = xmlNewStreamCtxt(comp->stream);
2490         if (cur == NULL)
2491             goto failed;
2492         if (ret == NULL)
2493             ret = cur;
2494         else {
2495             cur->next = ret->next;
2496             ret->next = cur;
2497         }
2498         cur->flags = comp->flags;
2499         comp = comp->next;
2500     }
2501     return(ret);
2502 failed:
2503     xmlFreeStreamCtxt(ret);
2504     return(NULL);
2505 }
2506
2507 /**
2508  * xmlPatternStreamable:
2509  * @comp: the precompiled pattern
2510  *
2511  * Check if the pattern is streamable i.e. xmlPatternGetStreamCtxt()
2512  * should work.
2513  *
2514  * Returns 1 if streamable, 0 if not and -1 in case of error.
2515  */
2516 int
2517 xmlPatternStreamable(xmlPatternPtr comp) {
2518     if (comp == NULL)
2519         return(-1);
2520     while (comp != NULL) {
2521         if (comp->stream == NULL)
2522             return(0);
2523         comp = comp->next;
2524     }
2525     return(1);
2526 }
2527
2528 /**
2529  * xmlPatternMaxDepth:
2530  * @comp: the precompiled pattern
2531  *
2532  * Check the maximum depth reachable by a pattern
2533  *
2534  * Returns -2 if no limit (using //), otherwise the depth,
2535  *         and -1 in case of error
2536  */
2537 int
2538 xmlPatternMaxDepth(xmlPatternPtr comp) {
2539     int ret = 0, i;
2540     if (comp == NULL)
2541         return(-1);
2542     while (comp != NULL) {
2543         if (comp->stream == NULL)
2544             return(-1);
2545         for (i = 0;i < comp->stream->nbStep;i++)
2546             if (comp->stream->steps[i].flags & XML_STREAM_STEP_DESC)
2547                 return(-2);
2548         if (comp->stream->nbStep > ret)
2549             ret = comp->stream->nbStep;
2550         comp = comp->next;
2551     }
2552     return(ret);
2553 }
2554
2555 /**
2556  * xmlPatternMinDepth:
2557  * @comp: the precompiled pattern
2558  *
2559  * Check the minimum depth reachable by a pattern, 0 mean the / or . are
2560  * part of the set.
2561  *
2562  * Returns -1 in case of error otherwise the depth,
2563  *
2564  */
2565 int
2566 xmlPatternMinDepth(xmlPatternPtr comp) {
2567     int ret = 12345678;
2568     if (comp == NULL)
2569         return(-1);
2570     while (comp != NULL) {
2571         if (comp->stream == NULL)
2572             return(-1);
2573         if (comp->stream->nbStep < ret)
2574             ret = comp->stream->nbStep;
2575         if (ret == 0)
2576             return(0);
2577         comp = comp->next;
2578     }
2579     return(ret);
2580 }
2581
2582 /**
2583  * xmlPatternFromRoot:
2584  * @comp: the precompiled pattern
2585  *
2586  * Check if the pattern must be looked at from the root.
2587  *
2588  * Returns 1 if true, 0 if false and -1 in case of error
2589  */
2590 int
2591 xmlPatternFromRoot(xmlPatternPtr comp) {
2592     if (comp == NULL)
2593         return(-1);
2594     while (comp != NULL) {
2595         if (comp->stream == NULL)
2596             return(-1);
2597         if (comp->flags & PAT_FROM_ROOT)
2598             return(1);
2599         comp = comp->next;
2600     }
2601     return(0);
2602
2603 }
2604
2605 #define bottom_pattern
2606 #include "elfgcchack.h"
2607 #endif /* LIBXML_PATTERN_ENABLED */