src/pathx.c

   1 /*
   2  * pathx.c: handling path expressions
   3  *
   4  * Copyright (C) 2007-2016 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 #include <config.h>
  24 #include <internal.h>
  25 #include <stdint.h>
  26 #include <stdbool.h>
  27 #include <memory.h>
  28 #include <ctype.h>
  29
  30 #include "ref.h"
  31 #include "regexp.h"
  32 #include "errcode.h"
  33
  34 static const char *const errcodes[] = {
  35     "no error",
  36     "empty name",
  37     "illegal string literal",
  38     "illegal number",
  39     "string missing ending ' or \"",
  40     "expected '='",
  41     "allocation failed",
  42     "unmatched '['",
  43     "unmatched '('",
  44     "expected a '/'",
  45     "internal error",                             /* PATHX_EINTERNAL */
  46     "type error",                                 /* PATHX_ETYPE */
  47     "undefined variable",                         /* PATHX_ENOVAR */
  48     "garbage at end of path expression",          /* PATHX_EEND */
  49     "no match for path expression",               /* PATHX_ENOMATCH */
  50     "wrong number of arguments in function call", /* PATHX_EARITY */
  51     "invalid regular expression",                 /* PATHX_EREGEXP */
  52     "too many matches",                           /* PATHX_EMMATCH */
  53     "wrong flag for regexp"                       /* PATHX_EREGEXPFLAG */
  54 };
  55
  56 /*
  57  * Path expressions are strings that use a notation modelled on XPath.
  58  */
  59
  60 enum type {
  61     T_NONE = 0,     /* Not a type */
  62     T_NODESET,
  63     T_BOOLEAN,
  64     T_NUMBER,
  65     T_STRING,
  66     T_REGEXP
  67 };
  68
  69 enum expr_tag {
  70     E_FILTER,
  71     E_BINARY,
  72     E_VALUE,
  73     E_VAR,
  74     E_APP
  75 };
  76
  77 enum binary_op {
  78     OP_EQ,         /* '='  */
  79     OP_NEQ,        /* '!=' */
  80     OP_LT,         /* '<'  */
  81     OP_LE,         /* '<=' */
  82     OP_GT,         /* '>'  */
  83     OP_GE,         /* '>=' */
  84     OP_PLUS,       /* '+'  */
  85     OP_MINUS,      /* '-'  */
  86     OP_STAR,       /* '*'  */
  87     OP_AND,        /* 'and' */
  88     OP_OR,         /* 'or' */
  89     OP_RE_MATCH,   /* '=~' */
  90     OP_RE_NOMATCH, /* '!~' */
  91     OP_UNION       /* '|' */
  92 };
  93
  94 struct pred {
  95     int               nexpr;
  96     struct expr     **exprs;
  97 };
  98
  99 enum axis {
 100     SELF,
 101     CHILD,
 102     DESCENDANT,
 103     DESCENDANT_OR_SELF,
 104     PARENT,
 105     ANCESTOR,
 106     ROOT,
 107     PRECEDING_SIBLING,
 108     FOLLOWING_SIBLING
 109 };
 110
 111 /* This array is indexed by enum axis */
 112 static const char *const axis_names[] = {
 113     "self",
 114     "child",
 115     "descendant",
 116     "descendant-or-self",
 117     "parent",
 118     "ancestor",
 119     "root",
 120     "preceding-sibling",
 121     "following-sibling"
 122 };
 123
 124 /* The characters that can follow a name in a location expression (aka path)
 125  * The parser will assume that name (path component) is finished when it
 126  * encounters any of these characters, unless they are escaped by preceding
 127  * them with a '\\'.
 128  *
 129  * See parse_name for the gory details
 130  */
 131 static const char name_follow[] = "][|/=()!,";
 132
 133 /* Doubly linked list of location steps. Besides the information from the
 134  * path expression, also contains information to iterate over a node set,
 135  * in particular, the context node CTX for the step, and the current node
 136  * CUR within that context.
 137  */
 138 struct step {
 139     struct step *next;
 140     enum axis    axis;
 141     char        *name;              /* NULL to match any name */
 142     struct pred *predicates;
 143 };
 144
 145 /* Initialise the root nodeset with the first step */
 146 static struct tree *step_root(struct step *step, struct tree *ctx,
 147                               struct tree *root_ctx);
 148 /* Iteration over the nodes on a step, ignoring the predicates */
 149 static struct tree *step_first(struct step *step, struct tree *ctx);
 150 static struct tree *step_next(struct step *step, struct tree *ctx,
 151                               struct tree *node);
 152
 153 struct pathx_symtab {
 154     struct pathx_symtab *next;
 155     char                *name;
 156     struct value        *value;
 157 };
 158
 159 struct pathx {
 160     struct state   *state;
 161     struct nodeset *nodeset;
 162     int             node;
 163     struct tree    *origin;
 164 };
 165
 166 #define L_BRACK '['
 167 #define R_BRACK ']'
 168
 169 struct locpath {
 170     struct step *steps;
 171 };
 172
 173 struct nodeset {
 174     struct tree **nodes;
 175     size_t        used;
 176     size_t        size;
 177 };
 178
 179 typedef uint32_t value_ind_t;
 180
 181 struct value {
 182     enum type tag;
 183     union {
 184         struct nodeset  *nodeset;     /* T_NODESET */
 185         int64_t          number;      /* T_NUMBER  */
 186         char            *string;      /* T_STRING  */
 187         bool             boolval;     /* T_BOOLEAN */
 188         struct regexp   *regexp;      /* T_REGEXP  */
 189     };
 190 };
 191
 192 struct expr {
 193     enum expr_tag tag;
 194     enum type     type;
 195     union {
 196         struct {                       /* E_FILTER */
 197             struct expr     *primary;
 198             struct pred     *predicates;
 199             struct locpath  *locpath;
 200         };
 201         struct {                       /* E_BINARY */
 202             enum binary_op op;
 203             struct expr *left;
 204             struct expr *right;
 205         };
 206         value_ind_t      value_ind;    /* E_VALUE */
 207         char            *ident;        /* E_VAR */
 208         struct {                       /* E_APP */
 209             const struct func *func;
 210             struct expr       **args;
 211         };
 212     };
 213 };
 214
 215 struct locpath_trace {
 216     unsigned int      maxns;
 217     struct nodeset  **ns;
 218     struct locpath   *lp;
 219 };
 220
 221 /* Internal state of the evaluator/parser */
 222 struct state {
 223     pathx_errcode_t errcode;
 224     const char     *file;
 225     int             line;
 226     char           *errmsg;
 227
 228     const char     *txt;  /* Entire expression */
 229     const char     *pos;  /* Current position within TXT during parsing */
 230
 231     struct tree *ctx; /* The current node */
 232     uint            ctx_pos;
 233     uint            ctx_len;
 234
 235     struct tree *root_ctx; /* Root context for relative paths */
 236
 237     /* A table of all values. The table is dynamically reallocated, i.e.
 238      * pointers to struct value should not be used across calls that
 239      * might allocate new values
 240      *
 241      * value_pool[0] is always the boolean false, and value_pool[1]
 242      * always the boolean true
 243      */
 244     struct value  *value_pool;
 245     value_ind_t    value_pool_used;
 246     value_ind_t    value_pool_size;
 247     /* Stack of values (as indices into value_pool), with bottom of
 248        stack in values[0] */
 249     value_ind_t   *values;
 250     size_t         values_used;
 251     size_t         values_size;
 252     /* Stack of expressions, with bottom of stack in exprs[0] */
 253     struct expr  **exprs;
 254     size_t         exprs_used;
 255     size_t         exprs_size;
 256     /* Trace of a locpath evaluation, needed by pathx_expand_tree.
 257        Generally NULL, unless a trace is needed.
 258      */
 259     struct locpath_trace *locpath_trace;
 260     /* Symbol table for variable lookups */
 261     struct pathx_symtab *symtab;
 262     /* Error structure, used to communicate errors to struct augeas;
 263      * we never own this structure, and therefore never free it */
 264     struct error        *error;
 265 };
 266
 267 /* We consider NULL and the empty string to be equal */
 268 ATTRIBUTE_PURE
 269 static inline int streqx(const char *s1, const char *s2) {
 270     if (s1 == NULL)
 271         return (s2 == NULL || strlen(s2) == 0);
 272     if (s2 == NULL)
 273         return strlen(s1) == 0;
 274     return STREQ(s1, s2);
 275 }
 276
 277 /* Functions */
 278
 279 typedef void (*func_impl_t)(struct state *state, int nargs);
 280
 281 struct func {
 282     const char      *name;
 283     unsigned int     arity;
 284     enum type        type;
 285     const enum type *arg_types;
 286     func_impl_t      impl;
 287 };
 288
 289 static void func_last(struct state *state, int nargs);
 290 static void func_position(struct state *state, int nargs);
 291 static void func_count(struct state *state, int nargs);
 292 static void func_label(struct state *state, int nargs);
 293 static void func_regexp(struct state *state, int nargs);
 294 static void func_regexp_flag(struct state *state, int nargs);
 295 static void func_glob(struct state *state, int nargs);
 296 static void func_int(struct state *state, int nargs);
 297 static void func_not(struct state *state, int nargs);
 298
 299 static const enum type arg_types_nodeset[] = { T_NODESET };
 300 static const enum type arg_types_string[] = { T_STRING };
 301 static const enum type arg_types_bool[] = { T_BOOLEAN };
 302 static const enum type arg_types_string_string[] = { T_STRING, T_STRING };
 303 static const enum type arg_types_nodeset_string[] = { T_NODESET, T_STRING };
 304
 305 static const struct func builtin_funcs[] = {
 306     { .name = "last", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
 307       .impl = func_last },
 308     { .name = "position", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
 309       .impl = func_position },
 310     { .name = "label", .arity = 0, .type = T_STRING, .arg_types = NULL,
 311       .impl = func_label },
 312     { .name = "count", .arity = 1, .type = T_NUMBER,
 313       .arg_types = arg_types_nodeset,
 314       .impl = func_count },
 315     { .name = "regexp", .arity = 1, .type = T_REGEXP,
 316       .arg_types = arg_types_string,
 317       .impl = func_regexp },
 318     { .name = "regexp", .arity = 1, .type = T_REGEXP,
 319       .arg_types = arg_types_nodeset,
 320       .impl = func_regexp },
 321     { .name = "regexp", .arity = 2, .type = T_REGEXP,
 322       .arg_types = arg_types_string_string,
 323       .impl = func_regexp_flag },
 324     { .name = "regexp", .arity = 2, .type = T_REGEXP,
 325       .arg_types = arg_types_nodeset_string,
 326       .impl = func_regexp_flag },
 327     { .name = "glob", .arity = 1, .type = T_REGEXP,
 328       .arg_types = arg_types_string,
 329       .impl = func_glob },
 330     { .name = "glob", .arity = 1, .type = T_REGEXP,
 331       .arg_types = arg_types_nodeset,
 332       .impl = func_glob },
 333     { .name = "int", .arity = 1, .type = T_NUMBER,
 334       .arg_types = arg_types_string, .impl = func_int },
 335     { .name = "int", .arity = 1, .type = T_NUMBER,
 336       .arg_types = arg_types_nodeset, .impl = func_int },
 337     { .name = "int", .arity = 1, .type = T_NUMBER,
 338       .arg_types = arg_types_bool, .impl = func_int },
 339     { .name = "not", .arity = 1, .type = T_BOOLEAN,
 340       .arg_types = arg_types_bool, .impl = func_not }
 341 };
 342
 343 #define RET_ON_ERROR                                                    \
 344     if (state->errcode != PATHX_NOERROR) return
 345
 346 #define RET0_ON_ERROR                                                   \
 347     if (state->errcode != PATHX_NOERROR) return 0
 348
 349 #define STATE_ERROR(state, err)                                         \
 350     do {                                                                \
 351         state->errcode = err;                                           \
 352         state->file = __FILE__;                                         \
 353         state->line = __LINE__;                                         \
 354     } while (0)
 355
 356 #define HAS_ERROR(state) (state->errcode != PATHX_NOERROR)
 357
 358 #define STATE_ENOMEM STATE_ERROR(state, PATHX_ENOMEM)
 359
 360 /*
 361  * Free the various data structures
 362  */
 363
 364 static void free_expr(struct expr *expr);
 365
 366 static void free_pred(struct pred *pred) {
 367     if (pred == NULL)
 368         return;
 369
 370     for (int i=0; i < pred->nexpr; i++) {
 371         free_expr(pred->exprs[i]);
 372     }
 373     free(pred->exprs);
 374     free(pred);
 375 }
 376
 377 static void free_step(struct step *step) {
 378     while (step != NULL) {
 379         struct step *del = step;
 380         step = del->next;
 381         free(del->name);
 382         free_pred(del->predicates);
 383         free(del);
 384     }
 385 }
 386
 387 static void free_locpath(struct locpath *locpath) {
 388     if (locpath == NULL)
 389         return;
 390     while (locpath->steps != NULL) {
 391         struct step *step = locpath->steps;
 392         locpath->steps = step->next;
 393         free(step->name);
 394         free_pred(step->predicates);
 395         free(step);
 396     }
 397     free(locpath);
 398 }
 399
 400 static void free_expr(struct expr *expr) {
 401     if (expr == NULL)
 402         return;
 403     switch (expr->tag) {
 404     case E_FILTER:
 405         free_expr(expr->primary);
 406         free_pred(expr->predicates);
 407         free_locpath(expr->locpath);
 408         break;
 409     case E_BINARY:
 410         free_expr(expr->left);
 411         free_expr(expr->right);
 412         break;
 413     case E_VALUE:
 414         break;
 415     case E_VAR:
 416         free(expr->ident);
 417         break;
 418     case E_APP:
 419         for (int i=0; i < expr->func->arity; i++)
 420             free_expr(expr->args[i]);
 421         free(expr->args);
 422         break;
 423     default:
 424         assert(0);
 425     }
 426     free(expr);
 427 }
 428
 429 static void free_nodeset(struct nodeset *ns) {
 430     if (ns != NULL) {
 431         free(ns->nodes);
 432         free(ns);
 433     }
 434 }
 435
 436 /* Free all objects used by VALUE, but not VALUE itself */
 437 static void release_value(struct value *v) {
 438     if (v == NULL)
 439         return;
 440
 441     switch (v->tag) {
 442     case T_NODESET:
 443         free_nodeset(v->nodeset);
 444         break;
 445     case T_STRING:
 446         free(v->string);
 447         break;
 448     case T_BOOLEAN:
 449     case T_NUMBER:
 450         break;
 451     case T_REGEXP:
 452         unref(v->regexp, regexp);
 453         break;
 454     default:
 455         assert(0);
 456     }
 457 }
 458
 459 static void free_state(struct state *state) {
 460     if (state == NULL)
 461         return;
 462
 463     for(int i=0; i < state->exprs_used; i++)
 464         free_expr(state->exprs[i]);
 465     free(state->exprs);
 466
 467     for(int i=0; i < state->value_pool_used; i++)
 468         release_value(state->value_pool + i);
 469     free(state->value_pool);
 470     free(state->values);
 471     free(state);
 472 }
 473
 474 void free_pathx(struct pathx *pathx) {
 475     if (pathx == NULL)
 476         return;
 477     free_state(pathx->state);
 478     free(pathx);
 479 }
 480
 481 /*
 482  * Nodeset helpers
 483  */
 484 static struct nodeset *make_nodeset(struct state *state) {
 485     struct nodeset *result;
 486     if (ALLOC(result) < 0)
 487         STATE_ENOMEM;
 488     return result;
 489 }
 490
 491 /* Add NODE to NS if it is not in NS yet. This relies on the flag
 492  * NODE->ADDED and care must be taken that NS_CLEAR_ADDED is called on NS
 493  * as soon as we are done adding nodes to it.
 494  */
 495 static void ns_add(struct nodeset *ns, struct tree *node,
 496                    struct state *state) {
 497     if (node->added)
 498         return;
 499     if (ns->used >= ns->size) {
 500         size_t size = 2 * ns->size;
 501         if (size < 10) size = 10;
 502         if (REALLOC_N(ns->nodes, size) < 0)
 503             STATE_ENOMEM;
 504         ns->size = size;
 505     }
 506     ns->nodes[ns->used] = node;
 507     node->added = 1;
 508     ns->used += 1;
 509 }
 510
 511 static void ns_clear_added(struct nodeset *ns) {
 512     for (int i=0; i < ns->used; i++)
 513         ns->nodes[i]->added = 0;
 514 }
 515
 516 static struct nodeset *
 517 clone_nodeset(struct nodeset *ns, struct state *state)
 518 {
 519     struct nodeset *clone;
 520     if (ALLOC(clone) < 0) {
 521         STATE_ENOMEM;
 522         return NULL;
 523     }
 524     if (ALLOC_N(clone->nodes, ns->used) < 0) {
 525         free(clone);
 526         STATE_ENOMEM;
 527         return NULL;
 528     }
 529     clone->used = ns->used;
 530     clone->size = ns->used;
 531     for (int i=0; i < ns->used; i++)
 532         clone->nodes[i] = ns->nodes[i];
 533     return clone;
 534 }
 535
 536 /*
 537  * Handling values
 538  */
 539 static value_ind_t make_value(enum type tag, struct state *state) {
 540     assert(tag != T_BOOLEAN);
 541
 542     if (state->value_pool_used >= state->value_pool_size) {
 543         value_ind_t new_size = 2*state->value_pool_size;
 544         if (new_size <= state->value_pool_size) {
 545             STATE_ENOMEM;
 546             return 0;
 547         }
 548         if (REALLOC_N(state->value_pool, new_size) < 0) {
 549             STATE_ENOMEM;
 550             return 0;
 551         }
 552         state->value_pool_size = new_size;
 553     }
 554     state->value_pool[state->value_pool_used].tag = tag;
 555     state->value_pool[state->value_pool_used].nodeset = NULL;
 556     return state->value_pool_used++;
 557 }
 558
 559 static value_ind_t clone_value(struct value *v, struct state *state) {
 560     value_ind_t vind = make_value(v->tag, state);
 561     RET0_ON_ERROR;
 562     struct value *clone = state->value_pool + vind;
 563
 564     switch (v->tag) {
 565     case T_NODESET:
 566         clone->nodeset = clone_nodeset(v->nodeset, state);
 567         break;
 568     case T_NUMBER:
 569         clone->number = v->number;
 570         break;
 571     case T_STRING:
 572         clone->string = strdup(v->string);
 573         if (clone->string == NULL) {
 574             STATE_ENOMEM;
 575         }
 576         break;
 577     case T_BOOLEAN:
 578         clone->boolval = v->boolval;
 579         break;
 580     case T_REGEXP:
 581         clone->regexp = ref(v->regexp);
 582         break;
 583     default:
 584         assert(0);
 585     }
 586     return vind;
 587 }
 588
 589 static value_ind_t pop_value_ind(struct state *state) {
 590     if (state->values_used > 0) {
 591         state->values_used -= 1;
 592         return state->values[state->values_used];
 593     } else {
 594         STATE_ERROR(state, PATHX_EINTERNAL);
 595         assert(0);
 596         return 0;
 597     }
 598 }
 599
 600 static struct value *pop_value(struct state *state) {
 601     value_ind_t vind = pop_value_ind(state);
 602     if (HAS_ERROR(state))
 603         return NULL;
 604     return state->value_pool + vind;
 605 }
 606
 607 static void push_value(value_ind_t vind, struct state *state) {
 608     if (state->values_used >= state->values_size) {
 609         size_t new_size = 2*state->values_size;
 610         if (new_size == 0) new_size = 8;
 611         if (REALLOC_N(state->values, new_size) < 0) {
 612             STATE_ENOMEM;
 613             return;
 614         }
 615         state->values_size = new_size;
 616     }
 617     state->values[state->values_used++] = vind;
 618 }
 619
 620 static void push_boolean_value(int b, struct state *state) {
 621     push_value(b != 0, state);
 622 }
 623
 624 ATTRIBUTE_PURE
 625 static struct value *expr_value(struct expr *expr, struct state *state) {
 626     return state->value_pool + expr->value_ind;
 627 }
 628
 629 /*************************************************************************
 630  * Evaluation
 631  ************************************************************************/
 632 static void eval_expr(struct expr *expr, struct state *state);
 633
 634
 635 #define ensure_arity(min, max)                                          \
 636     if (nargs < min || nargs > max) {                                   \
 637         STATE_ERROR(state, PATHX_EINTERNAL);                            \
 638         return;                                                         \
 639     }
 640
 641 static void func_last(struct state *state, int nargs) {
 642     ensure_arity(0, 0);
 643     value_ind_t vind = make_value(T_NUMBER, state);
 644     RET_ON_ERROR;
 645
 646     state->value_pool[vind].number = state->ctx_len;
 647     push_value(vind, state);
 648 }
 649
 650 static void func_position(struct state *state, int nargs) {
 651     ensure_arity(0, 0);
 652     value_ind_t vind = make_value(T_NUMBER, state);
 653     RET_ON_ERROR;
 654
 655     state->value_pool[vind].number = state->ctx_pos;
 656     push_value(vind, state);
 657 }
 658
 659 static void func_count(struct state *state, int nargs) {
 660     ensure_arity(1, 1);
 661     value_ind_t vind = make_value(T_NUMBER, state);
 662     RET_ON_ERROR;
 663
 664     struct value *ns = pop_value(state);
 665     state->value_pool[vind].number = ns->nodeset->used;
 666     push_value(vind, state);
 667 }
 668
 669 static void func_label(struct state *state, int nargs) {
 670     ensure_arity(0, 0);
 671     value_ind_t vind = make_value(T_STRING, state);
 672     char *s;
 673
 674     RET_ON_ERROR;
 675
 676     if (state->ctx->label)
 677         s = strdup(state->ctx->label);
 678     else
 679         s = strdup("");
 680     if (s == NULL) {
 681         STATE_ENOMEM;
 682         return;
 683     }
 684     state->value_pool[vind].string = s;
 685     push_value(vind, state);
 686 }
 687
 688 static void func_int(struct state *state, int nargs) {
 689     ensure_arity(1, 1);
 690     value_ind_t vind = make_value(T_NUMBER, state);
 691     int64_t i = -1;
 692     RET_ON_ERROR;
 693
 694     struct value *v = pop_value(state);
 695     if (v->tag == T_BOOLEAN) {
 696         i = v->boolval;
 697     } else {
 698         const char *s = NULL;
 699         if (v->tag == T_STRING) {
 700             s = v->string;
 701         } else {
 702             /* T_NODESET */
 703             if (v->nodeset->used != 1) {
 704                 STATE_ERROR(state, PATHX_EMMATCH);
 705                 return;
 706             }
 707             s = v->nodeset->nodes[0]->value;
 708         }
 709         if (s != NULL) {
 710             int r;
 711             r = xstrtoint64(s, 10, &i);
 712             if (r < 0) {
 713                 STATE_ERROR(state, PATHX_ENUMBER);
 714                 return;
 715             }
 716         }
 717     }
 718     state->value_pool[vind].number = i;
 719     push_value(vind, state);
 720 }
 721
 722 static void func_not(struct state *state, int nargs) {
 723     ensure_arity(1, 1);
 724     RET_ON_ERROR;
 725
 726     struct value *v = pop_value(state);
 727     if (v->tag == T_BOOLEAN) {
 728         push_boolean_value(! v->boolval, state);
 729     }
 730 }
 731
 732 static struct regexp *
 733 nodeset_as_regexp(struct info *info, struct nodeset *ns, int glob, int nocase) {
 734     struct regexp *result = NULL;
 735     struct regexp **rx = NULL;
 736     int used = 0;
 737
 738     for (int i = 0; i < ns->used; i++) {
 739         if (ns->nodes[i]->value != NULL)
 740             used += 1;
 741     }
 742
 743     if (used == 0) {
 744         /* If the nodeset is empty, make sure we produce a regexp
 745          * that never matches anything */
 746         result = make_regexp_unescape(info, "[^\001-\7ff]", nocase);
 747     } else {
 748         if (ALLOC_N(rx, ns->used) < 0)
 749             goto error;
 750         for (int i=0; i < ns->used; i++) {
 751             if (ns->nodes[i]->value == NULL)
 752                 continue;
 753
 754             if (glob)
 755                 rx[i] = make_regexp_from_glob(info, ns->nodes[i]->value);
 756             else
 757                 rx[i] = make_regexp_unescape(info, ns->nodes[i]->value, 0);
 758             if (rx[i] == NULL)
 759                 goto error;
 760         }
 761         result = regexp_union_n(info, ns->used, rx);
 762     }
 763
 764  error:
 765     if (rx != NULL) {
 766         for (int i=0; i < ns->used; i++)
 767             unref(rx[i], regexp);
 768         free(rx);
 769     }
 770     return result;
 771 }
 772
 773 static void func_regexp_or_glob(struct state *state, int glob, int nocase) {
 774     value_ind_t vind = make_value(T_REGEXP, state);
 775     int r;
 776
 777     RET_ON_ERROR;
 778
 779     struct value *v = pop_value(state);
 780     struct regexp *rx = NULL;
 781
 782     if (v->tag == T_STRING) {
 783         if (glob)
 784             rx = make_regexp_from_glob(state->error->info, v->string);
 785         else
 786             rx = make_regexp_unescape(state->error->info, v->string, nocase);
 787     } else if (v->tag == T_NODESET) {
 788         rx = nodeset_as_regexp(state->error->info, v->nodeset, glob, nocase);
 789     } else {
 790         assert(0);
 791     }
 792
 793     if (rx == NULL) {
 794         STATE_ENOMEM;
 795         return;
 796     }
 797
 798     state->value_pool[vind].regexp = rx;
 799     r = regexp_compile(rx);
 800     if (r < 0) {
 801         const char *msg;
 802         regexp_check(rx, &msg);
 803         state->errmsg = strdup(msg);
 804         STATE_ERROR(state, PATHX_EREGEXP);
 805         return;
 806     }
 807     push_value(vind, state);
 808 }
 809
 810 static void func_regexp(struct state *state, int nargs) {
 811     ensure_arity(1, 1);
 812     func_regexp_or_glob(state, 0, 0);
 813 }
 814
 815 static void func_regexp_flag(struct state *state, int nargs) {
 816     ensure_arity(2, 2);
 817     int nocase = 0;
 818     struct value *f = pop_value(state);
 819
 820     if (STREQ("i", f->string))
 821         nocase = 1;
 822     else
 823         STATE_ERROR(state, PATHX_EREGEXPFLAG);
 824
 825     func_regexp_or_glob(state, 0, nocase);
 826 }
 827
 828 static void func_glob(struct state *state, int nargs) {
 829     ensure_arity(1, 1);
 830     func_regexp_or_glob(state, 1, 0);
 831 }
 832
 833 static bool coerce_to_bool(struct value *v) {
 834     switch (v->tag) {
 835     case T_NODESET:
 836         return v->nodeset->used > 0;
 837         break;
 838     case T_BOOLEAN:
 839         return v->boolval;
 840         break;
 841     case T_NUMBER:
 842         return v->number > 0;
 843         break;
 844     case T_STRING:
 845         return strlen(v->string) > 0;
 846         break;
 847     case T_REGEXP:
 848         return true;
 849     default:
 850         assert(0);
 851         return false;
 852     }
 853 }
 854
 855 static int calc_eq_nodeset_nodeset(struct nodeset *ns1, struct nodeset *ns2,
 856                                    int neq) {
 857     for (int i1=0; i1 < ns1->used; i1++) {
 858         struct tree *t1 = ns1->nodes[i1];
 859         for (int i2=0; i2 < ns2->used; i2++) {
 860             struct tree *t2 = ns2->nodes[i2];
 861             if (neq) {
 862                 if (!streqx(t1->value, t2->value))
 863                     return 1;
 864             } else {
 865                 if (streqx(t1->value, t2->value))
 866                     return 1;
 867             }
 868         }
 869     }
 870     return 0;
 871 }
 872
 873 static int calc_eq_nodeset_string(struct nodeset *ns, const char *s,
 874                                   int neq) {
 875     for (int i=0; i < ns->used; i++) {
 876         struct tree *t = ns->nodes[i];
 877         if (neq) {
 878             if (!streqx(t->value, s))
 879                 return 1;
 880         } else {
 881             if (streqx(t->value, s))
 882                 return 1;
 883         }
 884     }
 885     return 0;
 886 }
 887
 888 static void eval_eq(struct state *state, int neq) {
 889     struct value *r = pop_value(state);
 890     struct value *l = pop_value(state);
 891     int res;
 892
 893     if (l->tag == T_NODESET && r->tag == T_NODESET) {
 894         res = calc_eq_nodeset_nodeset(l->nodeset, r->nodeset, neq);
 895     } else if (l->tag == T_NODESET) {
 896         res = calc_eq_nodeset_string(l->nodeset, r->string, neq);
 897     } else if (r->tag == T_NODESET) {
 898         res = calc_eq_nodeset_string(r->nodeset, l->string, neq);
 899     } else if (l->tag == T_NUMBER && r->tag == T_NUMBER) {
 900         if (neq)
 901             res = (l->number != r->number);
 902         else
 903             res = (l->number == r->number);
 904     } else {
 905         assert(l->tag == T_STRING);
 906         assert(r->tag == T_STRING);
 907         res = streqx(l->string, r->string);
 908         if (neq)
 909             res = !res;
 910     }
 911     RET_ON_ERROR;
 912
 913     push_boolean_value(res, state);
 914 }
 915
 916 static void eval_arith(struct state *state, enum binary_op op) {
 917     value_ind_t vind = make_value(T_NUMBER, state);
 918     struct value *r = pop_value(state);
 919     struct value *l = pop_value(state);
 920     int res;
 921
 922     assert(l->tag == T_NUMBER);
 923     assert(r->tag == T_NUMBER);
 924
 925     RET_ON_ERROR;
 926
 927     if (op == OP_PLUS)
 928         res = l->number + r->number;
 929     else if (op == OP_MINUS)
 930         res = l->number - r->number;
 931     else if (op == OP_STAR)
 932         res = l->number * r->number;
 933     else
 934         assert(0);
 935
 936     state->value_pool[vind].number = res;
 937     push_value(vind, state);
 938 }
 939
 940 static void eval_rel(struct state *state, bool greater, bool equal) {
 941     struct value *r, *l;
 942     int res;
 943
 944     /* We always check l < r or l <= r */
 945     if (greater) {
 946         l = pop_value(state);
 947         r = pop_value(state);
 948     } else {
 949         r = pop_value(state);
 950         l = pop_value(state);
 951     }
 952     if (l->tag == T_NUMBER) {
 953         if (equal)
 954             res = (l->number <= r->number);
 955         else
 956             res = (l->number < r->number);
 957     } else if (l->tag == T_STRING) {
 958         int cmp = strcmp(l->string, r->string);
 959         if (equal)
 960             res = cmp <= 0;
 961         else
 962             res = cmp < 0;
 963     } else {
 964         assert(0);
 965     }
 966
 967     push_boolean_value(res, state);
 968 }
 969
 970 static void eval_and_or(struct state *state, enum binary_op op) {
 971     struct value *r = pop_value(state);
 972     struct value *l = pop_value(state);
 973     bool left = coerce_to_bool(l);
 974     bool right = coerce_to_bool(r);
 975
 976
 977     if (op == OP_AND)
 978         push_boolean_value(left && right, state);
 979     else
 980         push_boolean_value(left || right, state);
 981 }
 982
 983 static bool eval_re_match_str(struct state *state, struct regexp *rx,
 984                               const char *str) {
 985     int r;
 986
 987     if (str == NULL)
 988         str = "";
 989
 990     r = regexp_match(rx, str, strlen(str), 0, NULL);
 991     if (r == -2) {
 992         STATE_ERROR(state, PATHX_EINTERNAL);
 993     } else if (r == -3) {
 994         /* We should never get this far; func_regexp should catch
 995          * invalid regexps */
 996         assert(false);
 997     }
 998     return r == strlen(str);
 999 }
1000
1001 static void eval_union(struct state *state) {
1002     value_ind_t vind = make_value(T_NODESET, state);
1003     struct value *r = pop_value(state);
1004     struct value *l = pop_value(state);
1005     struct nodeset *res = NULL;
1006
1007     assert(l->tag == T_NODESET);
1008     assert(r->tag == T_NODESET);
1009
1010     RET_ON_ERROR;
1011
1012     res = clone_nodeset(l->nodeset, state);
1013     RET_ON_ERROR;
1014     for (int i=0; i < r->nodeset->used; i++) {
1015         ns_add(res, r->nodeset->nodes[i], state);
1016         if (HAS_ERROR(state))
1017             goto error;
1018     }
1019     state->value_pool[vind].nodeset = res;
1020     push_value(vind, state);
1021  error:
1022     ns_clear_added(res);
1023 }
1024
1025 static void eval_concat_string(struct state *state) {
1026     value_ind_t vind = make_value(T_STRING, state);
1027     struct value *r = pop_value(state);
1028     struct value *l = pop_value(state);
1029     char *res = NULL;
1030
1031     RET_ON_ERROR;
1032
1033     if (ALLOC_N(res, strlen(l->string) + strlen(r->string) + 1) < 0) {
1034         STATE_ENOMEM;
1035         return;
1036     }
1037     strcpy(res, l->string);
1038     strcat(res, r->string);
1039     state->value_pool[vind].string = res;
1040     push_value(vind, state);
1041 }
1042
1043 static void eval_concat_regexp(struct state *state) {
1044     value_ind_t vind = make_value(T_REGEXP, state);
1045     struct value *r = pop_value(state);
1046     struct value *l = pop_value(state);
1047     struct regexp *rx = NULL;
1048
1049     RET_ON_ERROR;
1050
1051     rx = regexp_concat(state->error->info, l->regexp, r->regexp);
1052     if (rx == NULL) {
1053         STATE_ENOMEM;
1054         return;
1055     }
1056
1057     state->value_pool[vind].regexp = rx;
1058     push_value(vind, state);
1059 }
1060
1061 static void eval_re_match(struct state *state, enum binary_op op) {
1062     struct value *rx  = pop_value(state);
1063     struct value *v = pop_value(state);
1064
1065     bool result = false;
1066
1067     if (v->tag == T_STRING) {
1068         result = eval_re_match_str(state, rx->regexp, v->string);
1069         RET_ON_ERROR;
1070     } else if (v->tag == T_NODESET) {
1071         for (int i=0; i < v->nodeset->used && result == false; i++) {
1072             struct tree *t = v->nodeset->nodes[i];
1073             result = eval_re_match_str(state, rx->regexp, t->value);
1074             RET_ON_ERROR;
1075         }
1076     }
1077     if (op == OP_RE_NOMATCH)
1078         result = !result;
1079     push_boolean_value(result, state);
1080 }
1081
1082 static void eval_binary(struct expr *expr, struct state *state) {
1083     eval_expr(expr->left, state);
1084     eval_expr(expr->right, state);
1085     RET_ON_ERROR;
1086
1087     switch (expr->op) {
1088     case OP_EQ:
1089         eval_eq(state, 0);
1090         break;
1091     case OP_NEQ:
1092         eval_eq(state, 1);
1093         break;
1094     case OP_LT:
1095         eval_rel(state, false, false);
1096         break;
1097     case OP_LE:
1098         eval_rel(state, false, true);
1099         break;
1100     case OP_GT:
1101         eval_rel(state, true, false);
1102         break;
1103     case OP_GE:
1104         eval_rel(state, true, true);
1105         break;
1106     case OP_PLUS:
1107         if (expr->type == T_NUMBER)
1108             eval_arith(state, expr->op);
1109         else if (expr->type == T_STRING)
1110             eval_concat_string(state);
1111         else if (expr->type == T_REGEXP)
1112             eval_concat_regexp(state);
1113         break;
1114     case OP_MINUS:
1115     case OP_STAR:
1116         eval_arith(state, expr->op);
1117         break;
1118     case OP_AND:
1119     case OP_OR:
1120         eval_and_or(state, expr->op);
1121         break;
1122     case OP_UNION:
1123         eval_union(state);
1124         break;
1125     case OP_RE_MATCH:
1126     case OP_RE_NOMATCH:
1127         eval_re_match(state, expr->op);
1128         break;
1129     default:
1130         assert(0);
1131     }
1132 }
1133
1134 static void eval_app(struct expr *expr, struct state *state) {
1135     assert(expr->tag == E_APP);
1136
1137     for (int i=0; i < expr->func->arity; i++) {
1138         eval_expr(expr->args[i], state);
1139         RET_ON_ERROR;
1140     }
1141     expr->func->impl(state, expr->func->arity);
1142 }
1143
1144 static bool eval_pred(struct expr *expr, struct state *state) {
1145     eval_expr(expr, state);
1146     RET0_ON_ERROR;
1147
1148     struct value *v = pop_value(state);
1149     switch(v->tag) {
1150     case T_BOOLEAN:
1151         return v->boolval;
1152     case T_NUMBER:
1153         return (state->ctx_pos == v->number);
1154     case T_NODESET:
1155         return v->nodeset->used > 0;
1156     case T_STRING:
1157         return streqv(state->ctx->value, v->string);
1158     default:
1159         assert(0);
1160         return false;
1161     }
1162 }
1163
1164 /* Remove COUNT successive entries from NS. The first entry to remove is at
1165    IND */
1166 static void ns_remove(struct nodeset *ns, int ind, int count) {
1167     if (count < 1)
1168         return;
1169     memmove(ns->nodes + ind, ns->nodes + ind+count,
1170             sizeof(ns->nodes[0]) * (ns->used - (ind+count)));
1171     ns->used -= count;
1172 }
1173
1174 /*
1175  * Remove all nodes from NS for which one of PRED is false
1176  */
1177 static void ns_filter(struct nodeset *ns, struct pred *predicates,
1178                       struct state *state) {
1179     if (predicates == NULL)
1180         return;
1181
1182     struct tree *old_ctx = state->ctx;
1183     uint old_ctx_len = state->ctx_len;
1184     uint old_ctx_pos = state->ctx_pos;
1185
1186     for (int p=0; p < predicates->nexpr; p++) {
1187         int first_bad = -1;  /* The index of the first non-matching node */
1188         state->ctx_len = ns->used;
1189         state->ctx_pos = 1;
1190         for (int i=0; i < ns->used; state->ctx_pos++) {
1191             state->ctx = ns->nodes[i];
1192             bool match = eval_pred(predicates->exprs[p], state);
1193             RET_ON_ERROR;
1194             /* We remove non-matching nodes from NS in batches; this logic
1195              * makes sure that we only call ns_remove at the end of a run
1196              * of non-matching nodes
1197              */
1198             if (match) {
1199                 if (first_bad >= 0) {
1200                     ns_remove(ns, first_bad, i - first_bad);
1201                     i = first_bad + 1;
1202                 } else {
1203                     i += 1;
1204                 }
1205                 first_bad = -1;
1206             } else {
1207                 if (first_bad == -1)
1208                     first_bad = i;
1209                 i += 1;
1210             }
1211         }
1212         if (first_bad >= 0) {
1213             ns_remove(ns, first_bad, ns->used - first_bad);
1214         }
1215     }
1216
1217     state->ctx = old_ctx;
1218     state->ctx_pos = old_ctx_pos;
1219     state->ctx_len = old_ctx_len;
1220 }
1221
1222 /* Return true if PRED is solely the predicate '[n]' as in 'foo[17]' */
1223 static bool position_pred(struct pred *pred) {
1224     return pred != NULL &&
1225         pred->nexpr == 1 &&
1226         pred->exprs[0]->tag == E_VALUE &&
1227         pred->exprs[0]->type == T_NUMBER;
1228 }
1229
1230 /* Return the tree node at the position implied by STEP->PREDICATES. It is
1231    assumed and required that STEP->PREDICATES is actually a
1232    POSITION_PRED.
1233
1234    This method hand-optimizes the important case of a path expression like
1235    'service[42]'
1236 */
1237 static struct tree *position_filter(struct nodeset *ns,
1238                                     struct step *step,
1239                                     struct state *state) {
1240     int value_ind = step->predicates->exprs[0]->value_ind;
1241     int number = state->value_pool[value_ind].number;
1242
1243     int pos = 1;
1244     for (int i=0; i < ns->used; i++) {
1245         for (struct tree *node = step_first(step, ns->nodes[i]);
1246              node != NULL;
1247              node = step_next(step, ns->nodes[i], node), pos++) {
1248             if (pos == number)
1249                 return node;
1250         }
1251     }
1252
1253     return NULL;
1254 }
1255
1256 /* Return an array of nodesets, one for each step in the locpath.
1257  *
1258  * On return, (*NS)[0] will contain state->ctx, and (*NS)[*MAXNS] will
1259  * contain the nodes that matched the entire locpath
1260  */
1261 static void ns_from_locpath(struct locpath *lp, uint *maxns,
1262                             struct nodeset ***ns,
1263                             const struct nodeset *root,
1264                             struct state *state) {
1265     struct tree *old_ctx = state->ctx;
1266     *maxns = 0;
1267
1268     ensure(lp != NULL, state);
1269
1270     *ns = NULL;
1271     list_for_each(step, lp->steps)
1272         *maxns += 1;
1273     if (ALLOC_N(*ns, *maxns+1) < 0) {
1274         STATE_ERROR(state, PATHX_ENOMEM);
1275         goto error;
1276     }
1277     for (int i=0; i <= *maxns; i++) {
1278         (*ns)[i] = make_nodeset(state);
1279         if (HAS_ERROR(state))
1280             goto error;
1281     }
1282
1283     if (root == NULL) {
1284         struct step *first_step = NULL;
1285         first_step = lp->steps;
1286
1287         struct tree *root_tree;
1288         root_tree = step_root(first_step, state->ctx, state->root_ctx);
1289         ns_add((*ns)[0], root_tree, state);
1290         ns_clear_added((*ns)[0]);
1291     } else {
1292         for (int i=0; i < root->used; i++)
1293             ns_add((*ns)[0], root->nodes[i], state);
1294         ns_clear_added((*ns)[0]);
1295     }
1296
1297     if (HAS_ERROR(state))
1298         goto error;
1299
1300     uint cur_ns = 0;
1301     list_for_each(step, lp->steps) {
1302         struct nodeset *work = (*ns)[cur_ns];
1303         struct nodeset *next = (*ns)[cur_ns + 1];
1304         if (position_pred(step->predicates)) {
1305             struct tree *node = position_filter(work, step, state);
1306             if (node) {
1307                 ns_add(next, node, state);
1308                 ns_clear_added(next);
1309             }
1310         } else {
1311             for (int i=0; i < work->used; i++) {
1312                 for (struct tree *node = step_first(step, work->nodes[i]);
1313                      node != NULL;
1314                      node = step_next(step, work->nodes[i], node)) {
1315                     ns_add(next, node, state);
1316                 }
1317             }
1318             ns_clear_added(next);
1319             ns_filter(next, step->predicates, state);
1320             if (HAS_ERROR(state))
1321                 goto error;
1322         }
1323         cur_ns += 1;
1324     }
1325
1326     state->ctx = old_ctx;
1327     return;
1328  error:
1329     if (*ns != NULL) {
1330         for (int i=0; i <= *maxns; i++)
1331             free_nodeset((*ns)[i]);
1332         FREE(*ns);
1333     }
1334     state->ctx = old_ctx;
1335     return;
1336 }
1337
1338 static void eval_filter(struct expr *expr, struct state *state) {
1339     struct locpath *lp = expr->locpath;
1340     struct nodeset **ns = NULL;
1341     struct locpath_trace *lpt = state->locpath_trace;
1342     uint maxns;
1343
1344     state->locpath_trace = NULL;
1345     if (expr->primary == NULL) {
1346         ns_from_locpath(lp, &maxns, &ns, NULL, state);
1347     } else {
1348         eval_expr(expr->primary, state);
1349         RET_ON_ERROR;
1350         value_ind_t primary_ind = pop_value_ind(state);
1351         struct value *primary = state->value_pool + primary_ind;
1352         assert(primary->tag == T_NODESET);
1353         ns_filter(primary->nodeset, expr->predicates, state);
1354         /* Evaluating predicates might have reallocated the value_pool */
1355         primary = state->value_pool + primary_ind;
1356         ns_from_locpath(lp, &maxns, &ns, primary->nodeset, state);
1357     }
1358     RET_ON_ERROR;
1359
1360     value_ind_t vind = make_value(T_NODESET, state);
1361     RET_ON_ERROR;
1362     state->value_pool[vind].nodeset = ns[maxns];
1363     push_value(vind, state);
1364
1365     if (lpt != NULL) {
1366         assert(lpt->ns == NULL);
1367         assert(lpt->lp == NULL);
1368         lpt->maxns = maxns;
1369         lpt->ns = ns;
1370         lpt->lp = lp;
1371         state->locpath_trace = lpt;
1372     } else {
1373         for (int i=0; i < maxns; i++)
1374             free_nodeset(ns[i]);
1375         FREE(ns);
1376     }
1377 }
1378
1379 static struct value *lookup_var(const char *ident,
1380                                 const struct pathx_symtab *symtab) {
1381     list_for_each(tab, symtab) {
1382         if (STREQ(ident, tab->name))
1383             return tab->value;
1384     }
1385     return NULL;
1386 }
1387
1388 static void eval_var(struct expr *expr, struct state *state) {
1389     struct value *v = lookup_var(expr->ident, state->symtab);
1390     value_ind_t vind = clone_value(v, state);
1391     RET_ON_ERROR;
1392     push_value(vind, state);
1393 }
1394
1395 static void eval_expr(struct expr *expr, struct state *state) {
1396     RET_ON_ERROR;
1397     switch (expr->tag) {
1398     case E_FILTER:
1399         eval_filter(expr, state);
1400         break;
1401     case E_BINARY:
1402         eval_binary(expr, state);
1403         break;
1404     case E_VALUE:
1405         push_value(expr->value_ind, state);
1406         break;
1407     case E_VAR:
1408         eval_var(expr, state);
1409         break;
1410     case E_APP:
1411         eval_app(expr, state);
1412         break;
1413     default:
1414         assert(0);
1415     }
1416 }
1417
1418 /*************************************************************************
1419  * Typechecker
1420  *************************************************************************/
1421
1422 static void check_expr(struct expr *expr, struct state *state);
1423
1424 /* Typecheck a list of predicates. A predicate is a function of
1425  * one of the following types:
1426  *
1427  * T_NODESET -> T_BOOLEAN
1428  * T_NUMBER  -> T_BOOLEAN  (position test)
1429  * T_BOOLEAN -> T_BOOLEAN
1430  */
1431 static void check_preds(struct pred *pred, struct state *state) {
1432     if (pred == NULL)
1433         return;
1434     for (int i=0; i < pred->nexpr; i++) {
1435         struct expr *e = pred->exprs[i];
1436         check_expr(e, state);
1437         RET_ON_ERROR;
1438         if (e->type != T_NODESET && e->type != T_NUMBER &&
1439             e->type != T_BOOLEAN && e->type != T_STRING) {
1440             STATE_ERROR(state, PATHX_ETYPE);
1441             return;
1442         }
1443     }
1444 }
1445
1446 static void check_filter(struct expr *expr, struct state *state) {
1447     assert(expr->tag == E_FILTER);
1448     struct locpath *locpath = expr->locpath;
1449
1450     if (expr->primary != NULL) {
1451         check_expr(expr->primary, state);
1452         if (expr->primary->type != T_NODESET) {
1453             STATE_ERROR(state, PATHX_ETYPE);
1454             return;
1455         }
1456         check_preds(expr->predicates, state);
1457         RET_ON_ERROR;
1458     }
1459     list_for_each(s, locpath->steps) {
1460         check_preds(s->predicates, state);
1461         RET_ON_ERROR;
1462     }
1463     expr->type = T_NODESET;
1464 }
1465
1466 static void check_app(struct expr *expr, struct state *state) {
1467     assert(expr->tag == E_APP);
1468
1469     for (int i=0; i < expr->func->arity; i++) {
1470         check_expr(expr->args[i], state);
1471         RET_ON_ERROR;
1472     }
1473
1474     int f;
1475     for (f=0; f < ARRAY_CARDINALITY(builtin_funcs); f++) {
1476         const struct func *fn = builtin_funcs + f;
1477         if (STRNEQ(expr->func->name, fn->name))
1478             continue;
1479         if (expr->func->arity != fn->arity)
1480             continue;
1481
1482         int match = 1;
1483         for (int i=0; i < expr->func->arity; i++) {
1484             if (expr->args[i]->type != fn->arg_types[i]) {
1485                 match = 0;
1486                 break;
1487             }
1488         }
1489         if (match)
1490             break;
1491     }
1492
1493     if (f < ARRAY_CARDINALITY(builtin_funcs)) {
1494         expr->func = builtin_funcs + f;
1495         expr->type = expr->func->type;
1496     } else {
1497         STATE_ERROR(state, PATHX_ETYPE);
1498     }
1499 }
1500
1501 /* Check the binary operators. Type rules:
1502  *
1503  * '=', '!='  : T_NODESET -> T_NODESET -> T_BOOLEAN
1504  *              T_STRING  -> T_NODESET -> T_BOOLEAN
1505  *              T_NODESET -> T_STRING  -> T_BOOLEAN
1506  *              T_NUMBER  -> T_NUMBER  -> T_BOOLEAN
1507  *
1508  * '>', '>=',
1509  * '<', '<='  : T_NUMBER -> T_NUMBER -> T_BOOLEAN
1510  *              T_STRING -> T_STRING -> T_BOOLEAN
1511  * '+'        : T_NUMBER -> T_NUMBER -> T_NUMBER
1512  *              T_STRING -> T_STRING -> T_STRING
1513  *              T_REGEXP -> T_REGEXP -> T_REGEXP
1514  * '+', '-', '*': T_NUMBER -> T_NUMBER -> T_NUMBER
1515  *
1516  * 'and', 'or': T_BOOLEAN -> T_BOOLEAN -> T_BOOLEAN
1517  * '=~', '!~' : T_STRING  -> T_REGEXP  -> T_BOOLEAN
1518  *              T_NODESET -> T_REGEXP  -> T_BOOLEAN
1519  *
1520  * '|'        : T_NODESET -> T_NODESET -> T_NODESET
1521  *
1522  * Any type can be coerced to T_BOOLEAN (see coerce_to_bool)
1523  */
1524 static void check_binary(struct expr *expr, struct state *state) {
1525     check_expr(expr->left, state);
1526     check_expr(expr->right, state);
1527     RET_ON_ERROR;
1528
1529     enum type l = expr->left->type;
1530     enum type r = expr->right->type;
1531     int  ok = 1;
1532     enum type res;
1533
1534     switch(expr->op) {
1535     case OP_EQ:
1536     case OP_NEQ:
1537         ok = ((l == T_NODESET || l == T_STRING)
1538               && (r == T_NODESET || r == T_STRING))
1539             || (l == T_NUMBER && r == T_NUMBER);;
1540         res = T_BOOLEAN;
1541         break;
1542     case OP_LT:
1543     case OP_LE:
1544     case OP_GT:
1545     case OP_GE:
1546         ok = (l == T_NUMBER && r == T_NUMBER)
1547             || (l == T_STRING && r == T_STRING);
1548         res = T_BOOLEAN;
1549         break;
1550     case OP_PLUS:
1551         ok = (l == r && (l == T_NUMBER || l == T_STRING || l == T_REGEXP));
1552         res = l;
1553         break;
1554     case OP_MINUS:
1555     case OP_STAR:
1556         ok =  (l == T_NUMBER && r == T_NUMBER);
1557         res = T_NUMBER;
1558         break;
1559     case OP_UNION:
1560         ok = (l == T_NODESET && r == T_NODESET);
1561         res = T_NODESET;
1562         break;
1563     case OP_AND:
1564     case OP_OR:
1565         ok = 1;
1566         res = T_BOOLEAN;
1567         break;
1568     case OP_RE_MATCH:
1569     case OP_RE_NOMATCH:
1570         ok = ((l == T_STRING || l == T_NODESET) && r == T_REGEXP);
1571         res = T_BOOLEAN;
1572         break;
1573     default:
1574         assert(0);
1575     }
1576     if (! ok) {
1577         STATE_ERROR(state, PATHX_ETYPE);
1578     } else {
1579         expr->type = res;
1580     }
1581 }
1582
1583 static void check_var(struct expr *expr, struct state *state) {
1584     struct value *v = lookup_var(expr->ident, state->symtab);
1585     if (v == NULL) {
1586         STATE_ERROR(state, PATHX_ENOVAR);
1587         return;
1588     }
1589     expr->type = v->tag;
1590 }
1591
1592 /* Typecheck an expression */
1593 static void check_expr(struct expr *expr, struct state *state) {
1594     RET_ON_ERROR;
1595     switch(expr->tag) {
1596     case E_FILTER:
1597         check_filter(expr, state);
1598         break;
1599     case E_BINARY:
1600         check_binary(expr, state);
1601         break;
1602     case E_VALUE:
1603         expr->type = expr_value(expr, state)->tag;
1604         break;
1605     case E_VAR:
1606         check_var(expr, state);
1607         break;
1608     case E_APP:
1609         check_app(expr, state);
1610         break;
1611     default:
1612         assert(0);
1613     }
1614 }
1615
1616 /*
1617  * Utility functions for the parser
1618  */
1619
1620 static void skipws(struct state *state) {
1621     while (isspace(*state->pos)) state->pos += 1;
1622 }
1623
1624 static int match(struct state *state, char m) {
1625     skipws(state);
1626
1627     if (*state->pos == '\0')
1628         return 0;
1629     if (*state->pos == m) {
1630         state->pos += 1;
1631         return 1;
1632     }
1633     return 0;
1634 }
1635
1636 static int peek(struct state *state, const char *chars) {
1637     return strchr(chars, *state->pos) != NULL;
1638 }
1639
1640 /* Return 1 if STATE->POS starts with TOKEN, followed by optional
1641  * whitespace, followed by FOLLOW. In that case, STATE->POS is set to the
1642  * first character after FOLLOW. Return 0 otherwise and leave STATE->POS
1643  * unchanged.
1644  */
1645 static int looking_at(struct state *state, const char *token,
1646                       const char *follow) {
1647     if (STREQLEN(state->pos, token, strlen(token))) {
1648         const char *p = state->pos + strlen(token);
1649         while (isspace(*p)) p++;
1650         if (STREQLEN(p, follow, strlen(follow))) {
1651             state->pos = p + strlen(follow);
1652             return 1;
1653         }
1654     }
1655     return 0;
1656 }
1657
1658 /*************************************************************************
1659  * The parser
1660  *************************************************************************/
1661
1662 static void parse_expr(struct state *state);
1663
1664 static struct expr* pop_expr(struct state *state) {
1665     if (state->exprs_used > 0) {
1666         state->exprs_used -= 1;
1667         return state->exprs[state->exprs_used];
1668     } else {
1669         STATE_ERROR(state, PATHX_EINTERNAL);
1670         assert(0);
1671         return NULL;
1672     }
1673 }
1674
1675 static void push_expr(struct expr *expr, struct state *state) {
1676     if (state->exprs_used >= state->exprs_size) {
1677         size_t new_size = 2*state->exprs_size;
1678         if (new_size == 0) new_size = 8;
1679         if (REALLOC_N(state->exprs, new_size) < 0) {
1680             STATE_ENOMEM;
1681             return;
1682         }
1683         state->exprs_size = new_size;
1684     }
1685     state->exprs[state->exprs_used++] = expr;
1686 }
1687
1688 static void push_new_binary_op(enum binary_op op, struct state *state) {
1689     struct expr *expr = NULL;
1690     if (ALLOC(expr) < 0) {
1691         STATE_ENOMEM;
1692         return;
1693     }
1694
1695     expr->tag = E_BINARY;
1696     expr->op  = op;
1697     expr->right = pop_expr(state);
1698     expr->left = pop_expr(state);
1699     push_expr(expr, state);
1700 }
1701
1702 int pathx_escape_name(const char *in, char **out) {
1703     const char *p;
1704     int num_to_escape = 0;
1705     char *s;
1706
1707     *out = NULL;
1708
1709     for (p = in; *p; p++) {
1710         if (strchr(name_follow, *p) || isspace(*p) || *p == '\\')
1711             num_to_escape += 1;
1712     }
1713
1714     if (num_to_escape == 0)
1715         return 0;
1716
1717     if (ALLOC_N(*out, strlen(in) + num_to_escape + 1) < 0)
1718         return -1;
1719
1720     for (p = in, s = *out; *p; p++) {
1721         if (strchr(name_follow, *p) || isspace(*p) || *p == '\\')
1722             *s++ = '\\';
1723         *s++ = *p;
1724     }
1725     *s = '\0';
1726     return 0;
1727 }
1728
1729 /* Return true if POS is preceded by an odd number of backslashes, i.e., if
1730  * POS is escaped. Stop the search when we get to START */
1731 static bool backslash_escaped(const char *pos, const char *start) {
1732     bool result=false;
1733     while (pos-- > start && *pos == '\\') {
1734         result = !result;
1735     }
1736     return result;
1737 }
1738
1739 /*
1740  * NameNoWS ::= [^][|/\= \t\n] | \\.
1741  * NameWS   ::= [^][|/\=] | \\.
1742  * Name ::= NameNoWS NameWS* NameNoWS | NameNoWS
1743  */
1744 static char *parse_name(struct state *state) {
1745     const char *s = state->pos;
1746     char *result;
1747
1748     /* Advance state->pos until it points to the first character that is
1749      * not part of a name. */
1750     while (*state->pos != '\0' && strchr(name_follow, *state->pos) == NULL) {
1751         /* Since we allow spaces in names, we need to avoid gobbling up
1752          * stuff that is in follow(Name), e.g. 'or' so that things like
1753          * [name1 or name2] still work. In other words, we'll parse 'x frob
1754          * y' as one name, but for 'x or y', we consider 'x' a name in its
1755          * own right. */
1756         if (STREQLEN(state->pos, " or ", strlen(" or ")) ||
1757             STREQLEN(state->pos, " and ", strlen(" and ")))
1758             break;
1759
1760         if (*state->pos == '\\') {
1761             state->pos += 1;
1762             if (*state->pos == '\0') {
1763                 STATE_ERROR(state, PATHX_ENAME);
1764                 return NULL;
1765             }
1766         }
1767         state->pos += 1;
1768     }
1769
1770     /* Strip trailing white space. Make sure we respect escaped whitespace
1771      * and don't strip it as in "x\\ " */
1772     if (state->pos > s) {
1773         state->pos -= 1;
1774         while (isspace(*state->pos) && state->pos > s
1775                && !backslash_escaped(state->pos, s))
1776             state->pos -= 1;
1777         state->pos += 1;
1778     }
1779
1780     if (state->pos == s) {
1781         STATE_ERROR(state, PATHX_ENAME);
1782         return NULL;
1783     }
1784
1785     result = strndup(s, state->pos - s);
1786     if (result == NULL) {
1787         STATE_ENOMEM;
1788         return NULL;
1789     }
1790
1791     char *p = result;
1792     for (char *t = result; *t != '\0'; t++, p++) {
1793         if (*t == '\\')
1794             t += 1;
1795         *p = *t;
1796     }
1797     *p = '\0';
1798
1799     return result;
1800 }
1801
1802 /*
1803  * Predicate    ::= "[" Expr "]" *
1804  */
1805 static struct pred *parse_predicates(struct state *state) {
1806     struct pred *pred = NULL;
1807     int nexpr = 0;
1808
1809     while (match(state, L_BRACK)) {
1810         parse_expr(state);
1811         nexpr += 1;
1812         RET0_ON_ERROR;
1813
1814         if (! match(state, R_BRACK)) {
1815             STATE_ERROR(state, PATHX_EPRED);
1816             return NULL;
1817         }
1818         skipws(state);
1819     }
1820
1821     if (nexpr == 0)
1822         return NULL;
1823
1824     if (ALLOC(pred) < 0) {
1825         STATE_ENOMEM;
1826         return NULL;
1827     }
1828     pred->nexpr = nexpr;
1829
1830     if (ALLOC_N(pred->exprs, nexpr) < 0) {
1831         free_pred(pred);
1832         STATE_ENOMEM;
1833         return NULL;
1834     }
1835
1836     for (int i = nexpr - 1; i >= 0; i--)
1837         pred->exprs[i] = pop_expr(state);
1838
1839     return pred;
1840 }
1841
1842 /*
1843  * Step ::= AxisSpecifier NameTest Predicate* | '.' | '..'
1844  * AxisSpecifier ::= AxisName '::' | <epsilon>
1845  * AxisName ::= 'ancestor'
1846  *            | 'ancestor-or-self'
1847  *            | 'child'
1848  *            | 'descendant'
1849  *            | 'descendant-or-self'
1850  *            | 'parent'
1851  *            | 'self'
1852  *            | 'root'
1853  */
1854 static struct step *parse_step(struct state *state) {
1855     struct step *step;
1856     int explicit_axis = 0, allow_predicates = 1;
1857
1858     if (ALLOC(step) < 0) {
1859         STATE_ENOMEM;
1860         return NULL;
1861     }
1862
1863     step->axis = CHILD;
1864     for (int i = 0; i < ARRAY_CARDINALITY(axis_names); i++) {
1865         if (looking_at(state, axis_names[i], "::")) {
1866             step->axis = i;
1867             explicit_axis = 1;
1868             break;
1869         }
1870     }
1871
1872     if (! match(state, '*')) {
1873         step->name = parse_name(state);
1874         if (HAS_ERROR(state))
1875             goto error;
1876         if (! explicit_axis) {
1877             if (STREQ(step->name, ".") || STREQ(step->name, "..")) {
1878                 step->axis = STREQ(step->name, ".") ? SELF : PARENT;
1879                 FREE(step->name);
1880                 allow_predicates = 0;
1881             }
1882         }
1883     }
1884
1885     if (allow_predicates) {
1886         step->predicates = parse_predicates(state);
1887         if (HAS_ERROR(state))
1888             goto error;
1889     }
1890
1891     return step;
1892
1893  error:
1894     free_step(step);
1895     return NULL;
1896 }
1897
1898 static struct step *make_step(enum axis axis, struct state *state) {
1899     struct step *result = NULL;
1900
1901     if (ALLOC(result) < 0) {
1902         STATE_ENOMEM;
1903         return NULL;
1904     }
1905     result->axis = axis;
1906     return result;
1907 }
1908
1909 /*
1910  * RelativeLocationPath ::= Step
1911  *                        | RelativeLocationPath '/' Step
1912  *                        | AbbreviatedRelativeLocationPath
1913  * AbbreviatedRelativeLocationPath ::= RelativeLocationPath '//' Step
1914  *
1915  * The above is the same as
1916  * RelativeLocationPath ::= Step ('/' Step | '//' Step)*
1917  */
1918 static struct locpath *
1919 parse_relative_location_path(struct state *state) {
1920     struct step *step = NULL;
1921     struct locpath *locpath = NULL;
1922
1923     step = parse_step(state);
1924     if (HAS_ERROR(state))
1925         goto error;
1926
1927     if (ALLOC(locpath) < 0) {
1928         STATE_ENOMEM;
1929         goto error;
1930     }
1931     list_append(locpath->steps, step);
1932     step = NULL;
1933
1934     while (match(state, '/')) {
1935         if (*state->pos == '/') {
1936             state->pos += 1;
1937             step = make_step(DESCENDANT_OR_SELF, state);
1938             if (step == NULL) {
1939                 STATE_ENOMEM;
1940                 goto error;
1941             }
1942             list_append(locpath->steps, step);
1943         }
1944         step = parse_step(state);
1945         if (HAS_ERROR(state))
1946             goto error;
1947         list_append(locpath->steps, step);
1948         step = NULL;
1949     }
1950     return locpath;
1951
1952  error:
1953     free_step(step);
1954     free_locpath(locpath);
1955     return NULL;
1956 }
1957
1958 /*
1959  * LocationPath ::= RelativeLocationPath | AbsoluteLocationPath
1960  * AbsoluteLocationPath ::= '/' RelativeLocationPath?
1961  *                        | AbbreviatedAbsoluteLocationPath
1962  * AbbreviatedAbsoluteLocationPath ::= '//' RelativeLocationPath
1963  *
1964  */
1965 static void parse_location_path(struct state *state) {
1966     struct expr *expr = NULL;
1967     struct locpath *locpath = NULL;
1968
1969     if (match(state, '/')) {
1970         if (*state->pos == '/') {
1971             state->pos += 1;
1972             locpath = parse_relative_location_path(state);
1973             if (HAS_ERROR(state))
1974                 return;
1975             struct step *step = make_step(DESCENDANT_OR_SELF, state);
1976             if (HAS_ERROR(state))
1977                 goto error;
1978             list_cons(locpath->steps, step);
1979         } else {
1980             if (*state->pos != '\0') {
1981                 locpath = parse_relative_location_path(state);
1982             } else {
1983                 if (ALLOC(locpath) < 0)
1984                     goto err_nomem;
1985             }
1986             struct step *step = make_step(ROOT, state);
1987             if (HAS_ERROR(state)) {
1988                 free_step(step);
1989                 goto error;
1990             }
1991             list_cons(locpath->steps, step);
1992         }
1993     } else {
1994         locpath = parse_relative_location_path(state);
1995     }
1996
1997     if (ALLOC(expr) < 0)
1998         goto err_nomem;
1999     expr->tag = E_FILTER;
2000     expr->locpath = locpath;
2001     push_expr(expr, state);
2002     return;
2003
2004  err_nomem:
2005     STATE_ENOMEM;
2006  error:
2007     free_expr(expr);
2008     free_locpath(locpath);
2009     return;
2010 }
2011
2012 /*
2013  * Number       ::= /[0-9]+/
2014  */
2015 static void parse_number(struct state *state) {
2016     struct expr *expr = NULL;
2017     unsigned long val;
2018     char *end;
2019
2020     errno = 0;
2021     val = strtoul(state->pos, &end, 10);
2022     if (errno || end == state->pos || (int) val != val) {
2023         STATE_ERROR(state, PATHX_ENUMBER);
2024         return;
2025     }
2026
2027     state->pos = end;
2028
2029     if (ALLOC(expr) < 0)
2030         goto err_nomem;
2031     expr->tag = E_VALUE;
2032     expr->value_ind = make_value(T_NUMBER, state);
2033     if (HAS_ERROR(state))
2034         goto error;
2035     expr_value(expr, state)->number = val;
2036
2037     push_expr(expr, state);
2038     return;
2039
2040  err_nomem:
2041     STATE_ENOMEM;
2042  error:
2043     free_expr(expr);
2044     return;
2045 }
2046
2047 /*
2048  * Literal ::= '"' /[^"]* / '"' | "'" /[^']* / "'"
2049  */
2050 static void parse_literal(struct state *state) {
2051     char delim;
2052     const char *s;
2053     struct expr *expr = NULL;
2054
2055     if (*state->pos == '"')
2056         delim = '"';
2057     else if (*state->pos == '\'')
2058         delim = '\'';
2059     else {
2060         STATE_ERROR(state, PATHX_ESTRING);
2061         return;
2062     }
2063     state->pos += 1;
2064
2065     s = state->pos;
2066     while (*state->pos != '\0' && *state->pos != delim) state->pos += 1;
2067
2068     if (*state->pos != delim) {
2069         STATE_ERROR(state, PATHX_EDELIM);
2070         return;
2071     }
2072     state->pos += 1;
2073
2074     if (ALLOC(expr) < 0)
2075         goto err_nomem;
2076     expr->tag = E_VALUE;
2077     expr->value_ind = make_value(T_STRING, state);
2078     if (HAS_ERROR(state))
2079         goto error;
2080     expr_value(expr, state)->string = strndup(s, state->pos - s - 1);
2081     if (expr_value(expr, state)->string == NULL)
2082         goto err_nomem;
2083
2084     push_expr(expr, state);
2085     return;
2086
2087  err_nomem:
2088     STATE_ENOMEM;
2089  error:
2090     free_expr(expr);
2091     return;
2092 }
2093
2094 /*
2095  * FunctionCall ::= Name '(' ( Expr ( ',' Expr )* )? ')'
2096  */
2097 static void parse_function_call(struct state *state) {
2098     const struct func *func = NULL;
2099     struct expr *expr = NULL;
2100     int nargs = 0, find = 0;
2101
2102     for (; find < ARRAY_CARDINALITY(builtin_funcs); find++) {
2103         if (looking_at(state, builtin_funcs[find].name, "(")) {
2104             func = builtin_funcs + find;
2105             break;
2106         }
2107     }
2108     if (func == NULL) {
2109         STATE_ERROR(state, PATHX_ENAME);
2110         return;
2111     }
2112
2113     if (! match(state, ')')) {
2114         do {
2115             nargs += 1;
2116             parse_expr(state);
2117             RET_ON_ERROR;
2118         } while (match(state, ','));
2119
2120         if (! match(state, ')')) {
2121             STATE_ERROR(state, PATHX_EPAREN);
2122             return;
2123         }
2124     }
2125
2126     int found = 0; /* Whether there is a builtin matching in name and arity */
2127     for (int i=find; i < ARRAY_CARDINALITY(builtin_funcs); i++) {
2128         if (STRNEQ(func->name, builtin_funcs[i].name))
2129             break;
2130         if (builtin_funcs[i].arity == nargs) {
2131             func = builtin_funcs + i;
2132             found = 1;
2133             break;
2134         }
2135     }
2136
2137     if (! found) {
2138         STATE_ERROR(state, PATHX_EARITY);
2139         return;
2140     }
2141
2142     if (ALLOC(expr) < 0) {
2143         STATE_ENOMEM;
2144         return;
2145     }
2146     expr->tag = E_APP;
2147     if (ALLOC_N(expr->args, nargs) < 0) {
2148         free_expr(expr);
2149         STATE_ENOMEM;
2150         return;
2151     }
2152     expr->func = func;
2153     for (int i = nargs - 1; i >= 0; i--)
2154         expr->args[i] = pop_expr(state);
2155
2156     push_expr(expr, state);
2157 }
2158
2159 /*
2160  * VariableReference ::= '$' /[a-zA-Z_][a-zA-Z0-9_]* /
2161  *
2162  * The '$' is consumed by parse_primary_expr
2163  */
2164 static void parse_var(struct state *state) {
2165     const char *id = state->pos;
2166     struct expr *expr = NULL;
2167
2168     if (!isalpha(*id) && *id != '_') {
2169         STATE_ERROR(state, PATHX_ENAME);
2170         return;
2171     }
2172     id++;
2173     while (isalpha(*id) || isdigit(*id) || *id == '_')
2174         id += 1;
2175
2176     if (ALLOC(expr) < 0)
2177         goto err_nomem;
2178     expr->tag = E_VAR;
2179     expr->ident = strndup(state->pos, id - state->pos);
2180     if (expr->ident == NULL)
2181         goto err_nomem;
2182
2183     push_expr(expr, state);
2184     state->pos = id;
2185     return;
2186  err_nomem:
2187     STATE_ENOMEM;
2188     free_expr(expr);
2189     return;
2190 }
2191
2192 /*
2193  * PrimaryExpr ::= Literal
2194  *               | Number
2195  *               | FunctionCall
2196  *               | VariableReference
2197  *               | '(' Expr ')'
2198  *
2199  */
2200 static void parse_primary_expr(struct state *state) {
2201     if (peek(state, "'\"")) {
2202         parse_literal(state);
2203     } else if (peek(state, "0123456789")) {
2204         parse_number(state);
2205     } else if (match(state, '(')) {
2206         parse_expr(state);
2207         RET_ON_ERROR;
2208         if (! match(state, ')')) {
2209             STATE_ERROR(state, PATHX_EPAREN);
2210             return;
2211         }
2212     } else if (match(state, '$')) {
2213         parse_var(state);
2214     } else {
2215         parse_function_call(state);
2216     }
2217 }
2218
2219 static int looking_at_primary_expr(struct state *state) {
2220     const char *s = state->pos;
2221     /* Is it a Number, Literal or VariableReference ? */
2222     if (peek(state, "$'\"0123456789"))
2223         return 1;
2224
2225     /* Or maybe a function call, i.e. a word followed by a '(' ?
2226      * Note that our function names are only [a-zA-Z]+
2227      */
2228     while (*s != '\0' && isalpha(*s)) s++;
2229     while (*s != '\0' && isspace(*s)) s++;
2230     return *s == '(';
2231 }
2232
2233 /*
2234  * PathExpr ::= LocationPath
2235  *            | FilterExpr
2236  *            | FilterExpr '/' RelativeLocationPath
2237  *            | FilterExpr '//' RelativeLocationPath
2238  *
2239  * FilterExpr ::= PrimaryExpr Predicate
2240  *
2241  * The grammar is ambiguous here: the expression '42' can either be the
2242  * number 42 (a PrimaryExpr) or the RelativeLocationPath 'child::42'. The
2243  * reason for this ambiguity is that we allow node names like '42' in the
2244  * tree; rather than forbid them, we resolve the ambiguity by always
2245  * parsing '42' as a number, and requiring that the user write the
2246  * RelativeLocationPath in a different form, e.g. 'child::42' or './42'.
2247  */
2248 static void parse_path_expr(struct state *state) {
2249     struct expr *expr = NULL;
2250     struct pred *predicates = NULL;
2251     struct locpath *locpath = NULL;
2252
2253     if (looking_at_primary_expr(state)) {
2254         parse_primary_expr(state);
2255         RET_ON_ERROR;
2256         predicates = parse_predicates(state);
2257         RET_ON_ERROR;
2258         if (match(state, '/')) {
2259             if (match(state, '/')) {
2260                 locpath = parse_relative_location_path(state);
2261                 if (HAS_ERROR(state))
2262                     goto error;
2263
2264                 struct step *step = make_step(DESCENDANT_OR_SELF, state);
2265                 if (HAS_ERROR(state))
2266                     return;
2267                 list_cons(locpath->steps, step);
2268             } else {
2269                 if (*state->pos == '\0') {
2270                     STATE_ERROR(state, PATHX_EEND);
2271                     goto error;
2272                 }
2273                 locpath = parse_relative_location_path(state);
2274             }
2275         }
2276         /* A PathExpr without predicates and locpath is
2277          * just a PrimaryExpr
2278          */
2279         if (predicates == NULL && locpath == NULL)
2280             return;
2281         /* To make evaluation easier, we parse something like
2282          *   $var[pred] as $var[pred]/.
2283          */
2284         if (locpath == NULL) {
2285             if (ALLOC(locpath) < 0)
2286                 goto error;
2287             if (ALLOC(locpath->steps) < 0)
2288                 goto error;
2289             locpath->steps->axis = SELF;
2290         }
2291         if (ALLOC(expr) < 0)
2292             goto error;
2293         expr->tag = E_FILTER;
2294         expr->predicates = predicates;
2295         expr->primary    = pop_expr(state);
2296         expr->locpath    = locpath;
2297         push_expr(expr, state);
2298     } else {
2299         parse_location_path(state);
2300     }
2301     return;
2302  error:
2303     free_expr(expr);
2304     free_pred(predicates);
2305     free_locpath(locpath);
2306     return;
2307 }
2308
2309 /*
2310  * UnionExpr ::= PathExpr ('|' PathExpr)*
2311  */
2312 static void parse_union_expr(struct state *state) {
2313     parse_path_expr(state);
2314     RET_ON_ERROR;
2315     while (match(state, '|')) {
2316         parse_path_expr(state);
2317         RET_ON_ERROR;
2318         push_new_binary_op(OP_UNION, state);
2319     }
2320 }
2321
2322 /*
2323  * MultiplicativeExpr ::= UnionExpr ('*' UnionExpr)*
2324  */
2325 static void parse_multiplicative_expr(struct state *state) {
2326     parse_union_expr(state);
2327     RET_ON_ERROR;
2328     while (match(state, '*')) {
2329         parse_union_expr(state);
2330         RET_ON_ERROR;
2331         push_new_binary_op(OP_STAR, state);
2332     }
2333 }
2334
2335 /*
2336  * AdditiveExpr ::= MultiplicativeExpr (AdditiveOp MultiplicativeExpr)*
2337  * AdditiveOp   ::= '+' | '-'
2338  */
2339 static void parse_additive_expr(struct state *state) {
2340     parse_multiplicative_expr(state);
2341     RET_ON_ERROR;
2342     while (*state->pos == '+' || *state->pos == '-') {
2343         enum binary_op op = (*state->pos == '+') ? OP_PLUS : OP_MINUS;
2344         state->pos += 1;
2345         skipws(state);
2346         parse_multiplicative_expr(state);
2347         RET_ON_ERROR;
2348         push_new_binary_op(op, state);
2349     }
2350 }
2351
2352 /*
2353  * RelationalExpr ::= AdditiveExpr (RelationalOp AdditiveExpr)?
2354  * RelationalOp ::= ">" | "<" | ">=" | "<="
2355  */
2356 static void parse_relational_expr(struct state *state) {
2357     parse_additive_expr(state);
2358     RET_ON_ERROR;
2359     if (*state->pos == '<' || *state->pos == '>') {
2360         enum binary_op op = (*state->pos == '<') ? OP_LT : OP_GT;
2361         state->pos += 1;
2362         if (*state->pos == '=') {
2363             op = (op == OP_LT) ? OP_LE : OP_GE;
2364             state->pos += 1;
2365         }
2366         skipws(state);
2367         parse_additive_expr(state);
2368         RET_ON_ERROR;
2369         push_new_binary_op(op, state);
2370     }
2371 }
2372
2373 /*
2374  * EqualityExpr ::= RelationalExpr (EqualityOp RelationalExpr)? | ReMatchExpr
2375  * EqualityOp ::= "=" | "!="
2376  * ReMatchExpr ::= RelationalExpr MatchOp RelationalExpr
2377  * MatchOp ::= "=~" | "!~"
2378  */
2379 static void parse_equality_expr(struct state *state) {
2380     parse_relational_expr(state);
2381     RET_ON_ERROR;
2382     if ((*state->pos == '=' || *state->pos == '!') && state->pos[1] == '~') {
2383         enum binary_op op = (*state->pos == '=') ? OP_RE_MATCH : OP_RE_NOMATCH;
2384         state->pos += 2;
2385         skipws(state);
2386         parse_relational_expr(state);
2387         RET_ON_ERROR;
2388         push_new_binary_op(op, state);
2389     } else if (*state->pos == '=' ||
2390         (*state->pos == '!' && state->pos[1] == '=')) {
2391         enum binary_op op = (*state->pos == '=') ? OP_EQ : OP_NEQ;
2392         state->pos += (op == OP_EQ) ? 1 : 2;
2393         skipws(state);
2394         parse_relational_expr(state);
2395         RET_ON_ERROR;
2396         push_new_binary_op(op, state);
2397     }
2398 }
2399
2400 /*
2401  * AndExpr ::= EqualityExpr ('and' EqualityExpr)*
2402  */
2403 static void parse_and_expr(struct state *state) {
2404     parse_equality_expr(state);
2405     RET_ON_ERROR;
2406     while (*state->pos == 'a' && state->pos[1] == 'n'
2407         && state->pos[2] == 'd') {
2408         state->pos += 3;
2409         skipws(state);
2410         parse_equality_expr(state);
2411         RET_ON_ERROR;
2412         push_new_binary_op(OP_AND, state);
2413     }
2414 }
2415
2416 /*
2417  * OrExpr ::= AndExpr ('or' AndExpr)*
2418  */
2419 static void parse_or_expr(struct state *state) {
2420     parse_and_expr(state);
2421     RET_ON_ERROR;
2422     while (*state->pos == 'o' && state->pos[1] == 'r') {
2423         state->pos += 2;
2424         skipws(state);
2425         parse_and_expr(state);
2426         RET_ON_ERROR;
2427         push_new_binary_op(OP_OR, state);
2428     }
2429 }
2430
2431 /*
2432  * Expr ::= OrExpr
2433  */
2434 static void parse_expr(struct state *state) {
2435     skipws(state);
2436     parse_or_expr(state);
2437 }
2438
2439 static void store_error(struct pathx *pathx) {
2440     const char *pathx_msg = NULL;
2441     const char *path = pathx->state->txt;
2442     const pathx_errcode_t errcode = pathx->state->errcode;
2443     struct error *err = pathx->state->error;
2444
2445     char *pos_str = pathx->state->errmsg;
2446     pathx->state->errmsg = NULL;
2447
2448     if (err == NULL || errcode == PATHX_NOERROR || err->code != AUG_NOERROR)
2449         return;
2450
2451     switch (errcode) {
2452     case PATHX_ENOMEM:
2453         err->code = AUG_ENOMEM;
2454         break;
2455     case PATHX_EMMATCH:
2456         err->code = AUG_EMMATCH;
2457         break;
2458     case PATHX_ENOMATCH:
2459         err->code = AUG_ENOMATCH;
2460         break;
2461     default:
2462         err->code = AUG_EPATHX;
2463         break;
2464     }
2465
2466     /* We only need details for pathx syntax errors */
2467     if (err->code != AUG_EPATHX)
2468         return;
2469
2470     int pos;
2471     pathx_msg = pathx_error(pathx, NULL, &pos);
2472
2473     bool has_msg = pos_str != NULL;
2474     int pos_str_len = pos_str == NULL ? 0 : strlen(pos_str);
2475     if (REALLOC_N(pos_str, pos_str_len + strlen(path) + 8) >= 0) {
2476         if (has_msg) {
2477             strcat(pos_str, " in ");
2478             strncat(pos_str, path, pos);
2479         } else {
2480             /* initialize pos_str explicitly, path might be "" */
2481             pos_str[0] = '\0';
2482             strncat(pos_str, path, pos);
2483         }
2484         strcat(pos_str, "|=|");
2485         strcat(pos_str, path + pos);
2486     }
2487
2488     err->minor = errcode;
2489     err->details = pos_str;
2490     pos_str = NULL;
2491     err->minor_details = pathx_msg;
2492 }
2493
2494 int pathx_parse(const struct tree *tree,
2495                 struct error *err,
2496                 const char *txt,
2497                 bool need_nodeset,
2498                 struct pathx_symtab *symtab,
2499                 struct tree *root_ctx,
2500                 struct pathx **pathx) {
2501     struct state *state = NULL;
2502
2503     *pathx = NULL;
2504
2505     if (ALLOC(*pathx) < 0)
2506         goto oom;
2507
2508     (*pathx)->origin = (struct tree *) tree;
2509
2510     /* Set up state */
2511     if (ALLOC((*pathx)->state) < 0)
2512         goto oom;
2513     state = (*pathx)->state;
2514
2515     state->errcode = PATHX_NOERROR;
2516     state->errmsg = NULL;
2517     state->txt = txt;
2518     state->pos = txt;
2519     state->symtab = symtab;
2520     state->root_ctx = root_ctx;
2521     state->error = err;
2522
2523     if (ALLOC_N(state->value_pool, 8) < 0) {
2524         STATE_ENOMEM;
2525         goto done;
2526     }
2527     state->value_pool_size = 8;
2528     state->value_pool[0].tag = T_BOOLEAN;
2529     state->value_pool[0].boolval = 0;
2530     state->value_pool[1].tag = T_BOOLEAN;
2531     state->value_pool[1].boolval = 1;
2532     state->value_pool_used = 2;
2533
2534     /* Parse */
2535     parse_expr(state);
2536     if (HAS_ERROR(state))
2537         goto done;
2538     if (state->pos != state->txt + strlen(state->txt)) {
2539         STATE_ERROR(state, PATHX_EEND);
2540         goto done;
2541     }
2542
2543     if (state->exprs_used != 1) {
2544         STATE_ERROR(state, PATHX_EINTERNAL);
2545         goto done;
2546     }
2547
2548     /* Typecheck */
2549     check_expr(state->exprs[0], state);
2550     if (HAS_ERROR(state))
2551         goto done;
2552
2553     if (need_nodeset && state->exprs[0]->type != T_NODESET) {
2554         STATE_ERROR(state, PATHX_ETYPE);
2555         goto done;
2556     }
2557
2558  done:
2559     store_error(*pathx);
2560     return state->errcode;
2561  oom:
2562     free_pathx(*pathx);
2563     *pathx = NULL;
2564     if (err != NULL)
2565         err->code = AUG_ENOMEM;
2566     return PATHX_ENOMEM;
2567 }
2568
2569 /*************************************************************************
2570  * Searching in the tree
2571  *************************************************************************/
2572
2573 static bool step_matches(struct step *step, struct tree *tree) {
2574     if (step->name == NULL) {
2575         return step->axis == ROOT || tree->label != NULL;
2576     } else {
2577         return streqx(step->name, tree->label);
2578     }
2579 }
2580
2581 static struct tree *tree_prev(struct tree *pos) {
2582     struct tree *node = NULL;
2583     if (pos != pos->parent->children) {
2584         for (node = pos->parent->children;
2585              node->next != pos;
2586              node = node->next);
2587     }
2588     return node;
2589 }
2590
2591 /* When the first step doesn't begin with ROOT then use relative root context
2592  * instead. */
2593 static struct tree *step_root(struct step *step, struct tree *ctx,
2594                               struct tree *root_ctx) {
2595     struct tree *node = NULL;
2596     switch (step->axis) {
2597     case SELF:
2598     case CHILD:
2599     case DESCENDANT:
2600     case PARENT:
2601     case ANCESTOR:
2602     case PRECEDING_SIBLING:
2603     case FOLLOWING_SIBLING:
2604         /* only use root_ctx when ctx is the absolute tree root */
2605         if (ctx == ctx->parent && root_ctx != NULL)
2606             node = root_ctx;
2607         else
2608             node = ctx;
2609         break;
2610     case ROOT:
2611     case DESCENDANT_OR_SELF:
2612         node = ctx;
2613         break;
2614     default:
2615         assert(0);
2616     }
2617     if (node == NULL)
2618         return NULL;
2619     return node;
2620 }
2621
2622 static struct tree *step_first(struct step *step, struct tree *ctx) {
2623     struct tree *node = NULL;
2624     switch (step->axis) {
2625     case SELF:
2626     case DESCENDANT_OR_SELF:
2627         node = ctx;
2628         break;
2629     case CHILD:
2630     case DESCENDANT:
2631         node = ctx->children;
2632         break;
2633     case PARENT:
2634     case ANCESTOR:
2635         node = ctx->parent;
2636         break;
2637     case ROOT:
2638         while (ctx->parent != ctx)
2639             ctx = ctx->parent;
2640         node = ctx;
2641         break;
2642     case PRECEDING_SIBLING:
2643         node = tree_prev(ctx);
2644         break;
2645     case FOLLOWING_SIBLING:
2646         node = ctx->next;
2647         break;
2648     default:
2649         assert(0);
2650     }
2651     if (node == NULL)
2652         return NULL;
2653     if (step_matches(step, node))
2654         return node;
2655     return step_next(step, ctx, node);
2656 }
2657
2658 static struct tree *step_next(struct step *step, struct tree *ctx,
2659                               struct tree *node) {
2660     while (node != NULL) {
2661         switch (step->axis) {
2662         case SELF:
2663             node = NULL;
2664             break;
2665         case CHILD:
2666             node = node->next;
2667             break;
2668         case DESCENDANT:
2669         case DESCENDANT_OR_SELF:
2670             if (node->children != NULL) {
2671                 node = node->children;
2672             } else {
2673                 while (node->next == NULL && node != ctx)
2674                     node = node->parent;
2675                 if (node == ctx)
2676                     node = NULL;
2677                 else
2678                     node = node->next;
2679             }
2680             break;
2681         case PARENT:
2682         case ROOT:
2683             node = NULL;
2684             break;
2685         case ANCESTOR:
2686             if (node->parent == node)
2687                 node = NULL;
2688             else
2689                 node = node->parent;
2690             break;
2691         case PRECEDING_SIBLING:
2692             node = tree_prev(node);
2693             break;
2694         case FOLLOWING_SIBLING:
2695             node = node->next;
2696             break;
2697         default:
2698             assert(0);
2699         }
2700         if (node != NULL && step_matches(step, node))
2701             break;
2702     }
2703     return node;
2704 }
2705
2706 static struct value *pathx_eval(struct pathx *pathx) {
2707     struct state *state = pathx->state;
2708     state->ctx = pathx->origin;
2709     state->ctx_pos = 1;
2710     state->ctx_len = 1;
2711     eval_expr(state->exprs[0], state);
2712     if (HAS_ERROR(state))
2713         return NULL;
2714
2715     if (state->values_used != 1) {
2716         STATE_ERROR(state, PATHX_EINTERNAL);
2717         return NULL;
2718     }
2719     return pop_value(state);
2720 }
2721
2722 struct tree *pathx_next(struct pathx *pathx) {
2723     if (pathx->node + 1 < pathx->nodeset->used)
2724         return pathx->nodeset->nodes[++pathx->node];
2725     return NULL;
2726 }
2727
2728 /* Find the first node in TREE matching PATH. */
2729 struct tree *pathx_first(struct pathx *pathx) {
2730     if (pathx->nodeset == NULL) {
2731         struct value *v = pathx_eval(pathx);
2732
2733         if (HAS_ERROR(pathx->state))
2734             goto error;
2735         assert(v->tag == T_NODESET);
2736         pathx->nodeset = v->nodeset;
2737     }
2738     pathx->node = 0;
2739     if (pathx->nodeset->used == 0)
2740         return NULL;
2741     else
2742         return pathx->nodeset->nodes[0];
2743  error:
2744     store_error(pathx);
2745     return NULL;
2746 }
2747
2748 /* Find a node in the tree that matches the longest prefix of PATH.
2749  *
2750  * Return 1 if a node was found that exactly matches PATH, 0 if an incomplete
2751  * prefix matches, and -1 if more than one node in the tree match.
2752  *
2753  * TMATCH is set to the tree node that matches, and SMATCH to the next step
2754  * after the one where TMATCH matched. If no node matches or multiple nodes
2755  * at the same depth match, TMATCH and SMATCH will be NULL. When exactly
2756  * one node matches, TMATCH will be that node, and SMATCH will be NULL.
2757  */
2758 static int locpath_search(struct locpath_trace *lpt,
2759                           struct tree **tmatch, struct step **smatch) {
2760     int last;
2761     int result = -1;
2762
2763     for (last=lpt->maxns; last >= 0 && lpt->ns[last]->used == 0; last--);
2764     if (last < 0) {
2765         *smatch = lpt->lp->steps;
2766         result = 1;
2767         goto done;
2768     }
2769     if (lpt->ns[last]->used > 1) {
2770         result = -1;
2771         goto done;
2772     }
2773     result = 0;
2774     *tmatch = lpt->ns[last]->nodes[0];
2775     *smatch = lpt->lp->steps;
2776     for (int i=0; i < last; i++)
2777         *smatch = (*smatch)->next;
2778  done:
2779     for (int i=0; i < lpt->maxns; i++)
2780         free_nodeset(lpt->ns[i]);
2781     FREE(lpt->ns);
2782     return result;
2783 }
2784
2785 /* Expand the tree ROOT so that it contains all components of PATH. PATH
2786  * must have been initialized against ROOT by a call to PATH_FIND_ONE.
2787  *
2788  * Return the first segment that was created by this operation, or NULL on
2789  * error.
2790  */
2791 int pathx_expand_tree(struct pathx *path, struct tree **tree) {
2792     int r;
2793     struct step *step = NULL;
2794     struct locpath_trace lpt;
2795     struct tree *first_child = NULL;
2796     struct value *v = NULL;
2797
2798     MEMZERO(&lpt, 1);
2799     path->state->locpath_trace = &lpt;
2800     v = pathx_eval(path);
2801     path->state->locpath_trace = NULL;
2802     if (HAS_ERROR(path->state))
2803         goto error;
2804
2805     if (lpt.maxns == 0) {
2806         if (v->tag != T_NODESET || v->nodeset->used == 0) {
2807             STATE_ERROR(path->state, PATHX_ENOMATCH);
2808             goto error;
2809         }
2810         if (v->nodeset->used > 1)
2811             goto error;
2812         *tree = v->nodeset->nodes[0];
2813         return 0;
2814     }
2815
2816     *tree = path->origin;
2817     r = locpath_search(&lpt, tree, &step);
2818     if (r == -1) {
2819         STATE_ERROR(path->state, PATHX_EMMATCH);
2820         goto error;
2821     }
2822
2823     if (step == NULL)
2824         return 0;
2825
2826     struct tree *parent = *tree;
2827     if (parent == NULL)
2828         parent = path->origin;
2829
2830     list_for_each(s, step) {
2831         if (s->name == NULL || s->axis != CHILD)
2832             goto error;
2833         struct tree *t = make_tree(strdup(s->name), NULL, parent, NULL);
2834         if (first_child == NULL)
2835             first_child = t;
2836         if (t == NULL || t->label == NULL)
2837             goto error;
2838         list_append(parent->children, t);
2839         parent = t;
2840     }
2841
2842     while (first_child->children != NULL)
2843         first_child = first_child->children;
2844
2845     *tree = first_child;
2846     return 1;
2847
2848  error:
2849     if (first_child != NULL) {
2850         list_remove(first_child, first_child->parent->children);
2851         free_tree(first_child);
2852     }
2853     *tree = NULL;
2854     store_error(path);
2855     return -1;
2856 }
2857
2858 int pathx_find_one(struct pathx *path, struct tree **tree) {
2859     *tree = pathx_first(path);
2860     if (HAS_ERROR(path->state))
2861         return -1;
2862     return path->nodeset->used;
2863 }
2864
2865 struct error *err_of_pathx(struct pathx *px) {
2866     return px->state->error;
2867 }
2868
2869 const char *pathx_error(struct pathx *path, const char **txt, int *pos) {
2870     int errcode = PATHX_ENOMEM;
2871
2872     if (path != NULL) {
2873         if (path->state->errcode < ARRAY_CARDINALITY(errcodes))
2874             errcode = path->state->errcode;
2875         else
2876             errcode = PATHX_EINTERNAL;
2877
2878         if (txt)
2879             *txt = path->state->txt;
2880
2881         if (pos)
2882             *pos = path->state->pos - path->state->txt;
2883     }
2884     return errcodes[errcode];
2885 }
2886
2887 /*
2888  * Symbol tables
2889  */
2890 static struct pathx_symtab
2891 *make_symtab(struct pathx_symtab *symtab, const char *name,
2892              struct value *value)
2893 {
2894     struct pathx_symtab *new;
2895     char *n = NULL;
2896
2897     n = strdup(name);
2898     if (n == NULL)
2899         return NULL;
2900
2901     if (ALLOC(new) < 0) {
2902         free(n);
2903         return NULL;
2904     }
2905     new->name = n;
2906     new->value = value;
2907     if (symtab == NULL) {
2908         return new;
2909     } else {
2910         new->next = symtab->next;
2911         symtab->next = new;
2912     }
2913     return symtab;
2914 }
2915
2916 void free_symtab(struct pathx_symtab *symtab) {
2917
2918     while (symtab != NULL) {
2919         struct pathx_symtab *del = symtab;
2920         symtab = del->next;
2921         free(del->name);
2922         release_value(del->value);
2923         free(del->value);
2924         free(del);
2925     }
2926 }
2927
2928 struct pathx_symtab *pathx_get_symtab(struct pathx *pathx) {
2929     return pathx->state->symtab;
2930 }
2931
2932 static int pathx_symtab_set(struct pathx_symtab **symtab,
2933                             const char *name, struct value *v) {
2934     int found = 0;
2935
2936     list_for_each(tab, *symtab) {
2937         if (STREQ(tab->name, name)) {
2938             release_value(tab->value);
2939             free(tab->value);
2940             tab->value = v;
2941             found = 1;
2942             break;
2943         }
2944     }
2945
2946     if (!found) {
2947         struct pathx_symtab *new = NULL;
2948
2949         new = make_symtab(*symtab, name, v);
2950         if (new == NULL)
2951             goto error;
2952         *symtab = new;
2953     }
2954     return 0;
2955  error:
2956     return -1;
2957 }
2958
2959 int pathx_symtab_define(struct pathx_symtab **symtab,
2960                         const char *name, struct pathx *px) {
2961     int r;
2962     struct value *value = NULL, *v = NULL;
2963     struct state *state = px->state;
2964
2965     value = pathx_eval(px);
2966     if (HAS_ERROR(px->state))
2967         goto error;
2968
2969     if (ALLOC(v) < 0) {
2970         STATE_ENOMEM;
2971         goto error;
2972     }
2973
2974     *v = *value;
2975     value->tag = T_BOOLEAN;
2976
2977     r = pathx_symtab_set(symtab, name, v);
2978     if (r < 0) {
2979         STATE_ENOMEM;
2980         goto error;
2981     }
2982
2983     if (v->tag == T_NODESET)
2984         return v->nodeset->used;
2985     else
2986         return 0;
2987  error:
2988     release_value(value);
2989     free(value);
2990     release_value(v);
2991     free(v);
2992     store_error(px);
2993     return -1;
2994 }
2995
2996 int pathx_symtab_undefine(struct pathx_symtab **symtab, const char *name) {
2997     struct pathx_symtab *del = NULL;
2998
2999     for(del = *symtab;
3000         del != NULL && !STREQ(del->name, name);
3001         del = del->next);
3002     if (del == NULL)
3003         return 0;
3004     list_remove(del, *symtab);
3005     free_symtab(del);
3006     return 0;
3007 }
3008
3009 int pathx_symtab_assign_tree(struct pathx_symtab **symtab,
3010                              const char *name, struct tree *tree) {
3011     struct value *v = NULL;
3012     int r;
3013
3014     if (ALLOC(v) < 0)
3015         goto error;
3016
3017     v->tag = T_NODESET;
3018     if (ALLOC(v->nodeset) < 0)
3019         goto error;
3020     if (ALLOC_N(v->nodeset->nodes, 1) < 0)
3021         goto error;
3022     v->nodeset->used = 1;
3023     v->nodeset->size = 1;
3024     v->nodeset->nodes[0] = tree;
3025
3026     r = pathx_symtab_set(symtab, name, v);
3027     if (r < 0)
3028         goto error;
3029     return 1;
3030  error:
3031     release_value(v);
3032     free(v);
3033     return -1;
3034 }
3035
3036 int
3037 pathx_symtab_count(const struct pathx_symtab *symtab, const char *name) {
3038     struct value *v = lookup_var(name, symtab);
3039
3040     if (v == NULL || v->tag != T_NODESET)
3041         return -1;
3042
3043     return v->nodeset->used;
3044 }
3045
3046 struct tree *
3047 pathx_symtab_get_tree(struct pathx_symtab *symtab,
3048                       const char *name, int i) {
3049     struct value *v = lookup_var(name, symtab);
3050     if (v == NULL)
3051         return NULL;
3052     if (v->tag != T_NODESET)
3053         return NULL;
3054     if (i >= v->nodeset->used)
3055         return NULL;
3056     return v->nodeset->nodes[i];
3057 }
3058
3059 void pathx_symtab_remove_descendants(struct pathx_symtab *symtab,
3060                                      const struct tree *tree) {
3061     list_for_each(tab, symtab) {
3062         if (tab->value->tag != T_NODESET)
3063             continue;
3064         struct nodeset *ns = tab->value->nodeset;
3065         for (int i=0; i < ns->used;) {
3066             struct tree *t = ns->nodes[i];
3067             while (t != t->parent && t != tree)
3068                 t = t->parent;
3069             if (t == tree)
3070                 ns_remove(ns, i, 1);
3071             else
3072                 i += 1;
3073         }
3074     }
3075 }
3076
3077 /*
3078  * Local variables:
3079  *  indent-tabs-mode: nil
3080  *  c-indent-level: 4
3081  *  c-basic-offset: 4
3082  *  tab-width: 4
3083  * End:
3084  */