<commit_before>/*
 * pathx.c: handling path expressions
 *
 * Copyright (C) 2007-2011 <NAME>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 *
 * Author: <NAME> <<EMAIL>>
 */

#include <config.h>
#include <internal.h>
#include <stdint.h>
#include <stdbool.h>
#include <memory.h>
#include <ctype.h>

#include "ref.h"
#include "regexp.h"
#include "errcode.h"

static const char *const errcodes[] = {
    "no error",
    "empty name",
    "illegal string literal",
    "illegal number",
    "string missing ending ' or \"",
    "expected '='",
    "allocation failed",
    "unmatched '['",
    "unmatched '('",
    "expected a '/'",
    "internal error",                             /* PATHX_EINTERNAL */
    "type error",                                 /* PATHX_ETYPE */
    "undefined variable",                         /* PATHX_ENOVAR */
    "garbage at end of path expression",          /* PATHX_EEND */
    "no match for path expression",               /* PATHX_ENOMATCH */
    "wrong number of arguments in function call", /* PATHX_EARITY */
    "invalid regular expression",                 /* PATHX_EREGEXP */
    "too many matches"                            /* PATHX_EMMATCH */
};

/*
 * Path expressions are strings that use a notation modelled on XPath.
 */

enum type {
    T_NONE = 0,     /* Not a type */
    T_NODESET,
    T_BOOLEAN,
    T_NUMBER,
    T_STRING,
    T_REGEXP
};

enum expr_tag {
    E_FILTER,
    E_BINARY,
    E_VALUE,
    E_VAR,
    E_APP
};

enum binary_op {
    OP_EQ,         /* '='  */
    OP_NEQ,        /* '!=' */
    OP_LT,         /* '<'  */
    OP_LE,         /* '<=' */
    OP_GT,         /* '>'  */
    OP_GE,         /* '>=' */
    OP_PLUS,       /* '+'  */
    OP_MINUS,      /* '-'  */
    OP_STAR,       /* '*'  */
    OP_AND,        /* 'and' */
    OP_OR,         /* 'or' */
    OP_RE_MATCH,   /* '=~' */
    OP_RE_NOMATCH, /* '!~' */
    OP_UNION       /* '|' */
};

struct pred {
    int               nexpr;
    struct expr     **exprs;
};

enum axis {
    SELF,
    CHILD,
    DESCENDANT,
    DESCENDANT_OR_SELF,
    PARENT,
    ANCESTOR,
    ROOT,
    PRECEDING_SIBLING,
    FOLLOWING_SIBLING
};

/* This array is indexed by enum axis */
static const char *const axis_names[] = {
    "self",
    "child",
    "descendant",
    "descendant-or-self",
    "parent",
    "ancestor",
    "root",
    "preceding-sibling",
    "following-sibling"
};

static const char *const axis_sep = "::";

/* Doubly linked list of location steps. Besides the information from the
 * path expression, also contains information to iterate over a node set,
 * in particular, the context node CTX for the step, and the current node
 * CUR within that context.
 */
struct step {
    struct step *next;
    enum axis    axis;
    char        *name;              /* NULL to match any name */
    struct pred *predicates;
};

/* Initialise the root nodeset with the first step */
static struct tree *step_root(struct step *step, struct tree *ctx,
                              struct tree *root_ctx);
/* Iteration over the nodes on a step, ignoring the predicates */
static struct tree *step_first(struct step *step, struct tree *ctx);
static struct tree *step_next(struct step *step, struct tree *ctx,
                              struct tree *node);

struct pathx_symtab {
    struct pathx_symtab *next;
    char                *name;
    struct value        *value;
};

struct pathx {
    struct state   *state;
    struct nodeset *nodeset;
    int             node;
    struct tree    *origin;
};

#define L_BRACK '['
#define R_BRACK ']'

struct locpath {
    struct step *steps;
};

struct nodeset {
    struct tree **nodes;
    size_t        used;
    size_t        size;
};

typedef uint32_t value_ind_t;

struct value {
    enum type tag;
    union {
        struct nodeset  *nodeset;     /* T_NODESET */
        int              number;      /* T_NUMBER  */
        char            *string;      /* T_STRING  */
        bool             boolval;     /* T_BOOLEAN */
        struct regexp   *regexp;      /* T_REGEXP  */
    };
};

struct expr {
    enum expr_tag tag;
    enum type     type;
    union {
        struct {                       /* E_FILTER */
            struct expr     *primary;
            struct pred     *predicates;
            struct locpath  *locpath;
        };
        struct {                       /* E_BINARY */
            enum binary_op op;
            struct expr *left;
            struct expr *right;
        };
        value_ind_t      value_ind;    /* E_VALUE */
        char            *ident;        /* E_VAR */
        struct {                       /* E_APP */
            const struct func *func;
            struct expr       **args;
        };
    };
};

struct locpath_trace {
    unsigned int      maxns;
    struct nodeset  **ns;
    struct locpath   *lp;
};

/* Internal state of the evaluator/parser */
struct state {
    pathx_errcode_t errcode;
    const char     *file;
    int             line;
    char           *errmsg;

    const char     *txt;  /* Entire expression */
    const char     *pos;  /* Current position within TXT during parsing */

    struct tree *ctx; /* The current node */
    uint            ctx_pos;
    uint            ctx_len;

    struct tree *root_ctx; /* Root context for relative paths */

    /* A table of all values. The table is dynamically reallocated, i.e.
     * pointers to struct value should not be used across calls that
     * might allocate new values
     *
     * value_pool[0] is always the boolean false, and value_pool[1]
     * always the boolean true
     */
    struct value  *value_pool;
    value_ind_t    value_pool_used;
    value_ind_t    value_pool_size;
    /* Stack of values (as indices into value_pool), with bottom of
       stack in values[0] */
    value_ind_t   *values;
    size_t         values_used;
    size_t         values_size;
    /* Stack of expressions, with bottom of stack in exprs[0] */
    struct expr  **exprs;
    size_t         exprs_used;
    size_t         exprs_size;
    /* Trace of a locpath evaluation, needed by pathx_expand_tree.
       Generally NULL, unless a trace is needed.
     */
    struct locpath_trace *locpath_trace;
    /* Symbol table for variable lookups */
    struct pathx_symtab *symtab;
    /* Error structure, used to communicate errors to struct augeas;
     * we never own this structure, and therefore never free it */
    struct error        *error;
};

/* We consider NULL and the empty string to be equal */
ATTRIBUTE_PURE
static inline int streqx(const char *s1, const char *s2) {
    if (s1 == NULL)
        return (s2 == NULL || strlen(s2) == 0);
    if (s2 == NULL)
        return strlen(s1) == 0;
    return STREQ(s1, s2);
}

/* Functions */

typedef void (*func_impl_t)(struct state *state);

struct func {
    const char      *name;
    unsigned int     arity;
    enum type        type;
    const enum type *arg_types;
    func_impl_t      impl;
};

static void func_last(struct state *state);
static void func_position(struct state *state);
static void func_count(struct state *state);
static void func_label(struct state *state);
static void func_regexp(struct state *state);
static void func_glob(struct state *state);
static void func_int(struct state *state);

static const enum type const arg_types_nodeset[] = { T_NODESET };
static const enum type const arg_types_string[] = { T_STRING };
static const enum type const arg_types_bool[] = { T_BOOLEAN };

static const struct func builtin_funcs[] = {
    { .name = "last", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
      .impl = func_last },
    { .name = "position", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
      .impl = func_position },
    { .name = "label", .arity = 0, .type = T_STRING, .arg_types = NULL,
      .impl = func_label },
    { .name = "count", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_nodeset,
      .impl = func_count },
    { .name = "regexp", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_string,
      .impl = func_regexp },
    { .name = "regexp", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_nodeset,
      .impl = func_regexp },
    { .name = "glob", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_string,
      .impl = func_glob },
    { .name = "glob", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_nodeset,
      .impl = func_glob },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_string, .impl = func_int },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_nodeset, .impl = func_int },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_bool, .impl = func_int }
};

#define RET_ON_ERROR                                                    \
    if (state->errcode != PATHX_NOERROR) return

#define RET0_ON_ERROR                                                   \
    if (state->errcode != PATHX_NOERROR) return 0

#define STATE_ERROR(state, err)                                         \
    do {                                                                \
        state->errcode = err;                                           \
        state->file = __FILE__;                                         \
        state->line = __LINE__;                                         \
    } while (0)

#define HAS_ERROR(state) (state->errcode != PATHX_NOERROR)

#define STATE_ENOMEM STATE_ERROR(state, PATHX_ENOMEM)

#define ENOMEM_ON_NULL(state, v)                                        \
    do {                                                                \
        if (v == NULL) {                                                \
            STATE_ERROR(state, PATHX_ENOMEM);                           \
            return NULL;                                                \
        }                                                               \
    } while (0);

/*
 * Free the various data structures
 */

static void free_expr(struct expr *expr);

static void free_pred(struct pred *pred) {
    if (pred == NULL)
        return;

    for (int i=0; i < pred->nexpr; i++) {
        free_expr(pred->exprs[i]);
    }
    free(pred->exprs);
    free(pred);
}

static void free_step(struct step *step) {
    while (step != NULL) {
        struct step *del = step;
        step = del->next;
        free(del->name);
        free_pred(del->predicates);
        free(del);
    }
}

static void free_locpath(struct locpath *locpath) {
    if (locpath == NULL)
        return;
    while (locpath->steps != NULL) {
        struct step *step = locpath->steps;
        locpath->steps = step->next;
        free(step->name);
        free_pred(step->predicates);
        free(step);
    }
    free(locpath);
}

static void free_expr(struct expr *expr) {
    if (expr == NULL)
        return;
    switch (expr->tag) {
    case E_FILTER:
        free_expr(expr->primary);
        free_pred(expr->predicates);
        free_locpath(expr->locpath);
        break;
    case E_BINARY:
        free_expr(expr->left);
        free_expr(expr->right);
        break;
    case E_VALUE:
        break;
    case E_VAR:
        free(expr->ident);
        break;
    case E_APP:
        for (int i=0; i < expr->func->arity; i++)
            free_expr(expr->args[i]);
        free(expr->args);
        break;
    default:
        assert(0);
    }
    free(expr);
}

static void free_nodeset(struct nodeset *ns) {
    if (ns != NULL) {
        free(ns->nodes);
        free(ns);
    }
}

/* Free all objects used by VALUE, but not VALUE itself */
static void release_value(struct value *v) {
    if (v == NULL)
        return;

    switch (v->tag) {
    case T_NODESET:
        free_nodeset(v->nodeset);
        break;
    case T_STRING:
        free(v->string);
        break;
    case T_BOOLEAN:
    case T_NUMBER:
        break;
    case T_REGEXP:
        unref(v->regexp, regexp);
        break;
    default:
        assert(0);
    }
}

static void free_state(struct state *state) {
    if (state == NULL)
        return;

    for(int i=0; i < state->exprs_used; i++)
        free_expr(state->exprs[i]);
    free(state->exprs);

    for(int i=0; i < state->value_pool_used; i++)
        release_value(state->value_pool + i);
    free(state->value_pool);
    free(state->values);
    free(state);
}

void free_pathx(struct pathx *pathx) {
    if (pathx == NULL)
        return;
    free_state(pathx->state);
    free(pathx);
}

/*
 * Nodeset helpers
 */
static struct nodeset *make_nodeset(struct state *state) {
    struct nodeset *result;
    if (ALLOC(result) < 0)
        STATE_ENOMEM;
    return result;
}

static void ns_add(struct nodeset *ns, struct tree *node,
                   struct state *state) {
    for (int i=0; i < ns->used; i++)
        if (ns->nodes[i] == node)
            return;
    if (ns->used >= ns->size) {
        size_t size = 2 * ns->size;
        if (size < 10) size = 10;
        if (REALLOC_N(ns->nodes, size) < 0)
            STATE_ENOMEM;
        ns->size = size;
    }
    ns->nodes[ns->used] = node;
    ns->used += 1;
}

static struct nodeset *
clone_nodeset(struct nodeset *ns, struct state *state)
{
    struct nodeset *clone;
    if (ALLOC(clone) < 0) {
        STATE_ENOMEM;
        return NULL;
    }
    if (ALLOC_N(clone->nodes, ns->used) < 0) {
        free(clone);
        STATE_ENOMEM;
        return NULL;
    }
    clone->used = ns->used;
    clone->size = ns->used;
    for (int i=0; i < ns->used; i++)
        clone->nodes[i] = ns->nodes[i];
    return clone;
}

/*
 * Handling values
 */
static value_ind_t make_value(enum type tag, struct state *state) {
    assert(tag != T_BOOLEAN);

    if (state->value_pool_used >= state->value_pool_size) {
        value_ind_t new_size = 2*state->value_pool_size;
        if (new_size <= state->value_pool_size) {
            STATE_ENOMEM;
            return 0;
        }
        if (REALLOC_N(state->value_pool, new_size) < 0) {
            STATE_ENOMEM;
            return 0;
        }
        state->value_pool_size = new_size;
    }
    state->value_pool[state->value_pool_used].tag = tag;
    state->value_pool[state->value_pool_used].nodeset = NULL;
    return state->value_pool_used++;
}

ATTRIBUTE_UNUSED
static value_ind_t clone_value(struct value *v, struct state *state) {
    value_ind_t vind = make_value(v->tag, state);
    RET0_ON_ERROR;
    struct value *clone = state->value_pool + vind;

    switch (v->tag) {
    case T_NODESET:
        clone->nodeset = clone_nodeset(v->nodeset, state);
        break;
    case T_NUMBER:
        clone->number = v->number;
        break;
    case T_STRING:
        clone->string = strdup(v->string);
        if (clone->string == NULL) {
            FREE(clone);
            STATE_ENOMEM;
        }
        break;
    case T_BOOLEAN:
        clone->boolval = v->boolval;
        break;
    case T_REGEXP:
        clone->regexp = ref(v->regexp);
        break;
    default:
        assert(0);
    }
    return vind;
}

static value_ind_t pop_value_ind(struct state *state) {
    if (state->values_used > 0) {
        state->values_used -= 1;
        return state->values[state->values_used];
    } else {
        STATE_ERROR(state, PATHX_EINTERNAL);
        assert(0);
        return 0;
    }
}

static struct value *pop_value(struct state *state) {
    value_ind_t vind = pop_value_ind(state);
    if (HAS_ERROR(state))
        return NULL;
    return state->value_pool + vind;
}

static void push_value(value_ind_t vind, struct state *state) {
    if (state->values_used >= state->values_size) {
        size_t new_size = 2*state->values_size;
        if (new_size == 0) new_size = 8;
        if (REALLOC_N(state->values, new_size) < 0) {
            STATE_ENOMEM;
            return;
        }
        state->values_size = new_size;
    }
    state->values[state->values_used++] = vind;
}

static void push_boolean_value(int b, struct state *state) {
    push_value(b != 0, state);
}

ATTRIBUTE_PURE
static struct value *expr_value(struct expr *expr, struct state *state) {
    return state->value_pool + expr->value_ind;
}

/*************************************************************************
 * Evaluation
 ************************************************************************/
static void eval_expr(struct expr *expr, struct state *state);

static void func_last(struct state *state) {
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    state->value_pool[vind].number = state->ctx_len;
    push_value(vind, state);
}

static void func_position(struct state *state) {
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    state->value_pool[vind].number = state->ctx_pos;
    push_value(vind, state);
}

static void func_count(struct state *state) {
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    struct value *ns = pop_value(state);
    state->value_pool[vind].number = ns->nodeset->used;
    push_value(vind, state);
}

static void func_label(struct state *state) {
    value_ind_t vind = make_value(T_STRING, state);
    char *s;

    RET_ON_ERROR;

    if (state->ctx->label)
        s = strdup(state->ctx->label);
    else
        s = strdup("");
    if (s == NULL) {
        STATE_ENOMEM;
        return;
    }
    state->value_pool[vind].string = s;
    push_value(vind, state);
}

static void func_int(struct state *state) {
    value_ind_t vind = make_value(T_NUMBER, state);
    int64_t i = -1;
    RET_ON_ERROR;

    struct value *v = pop_value(state);
    if (v->tag == T_BOOLEAN) {
        i = v->boolval;
    } else {
        const char *s = NULL;
        if (v->tag == T_STRING) {
            s = v->string;
        } else {
            /* T_NODESET */
            if (v->nodeset->used != 1) {
                STATE_ERROR(state, PATHX_EMMATCH);
                return;
            }
            s = v->nodeset->nodes[0]->value;
        }
        if (s != NULL) {
            int r;
            r = xstrtoint64(s, 10, &i);
            if (r < 0) {
                STATE_ERROR(state, PATHX_ENUMBER);
                return;
            }
        }
    }
    state->value_pool[vind].number = i;
    push_value(vind, state);
}

static struct regexp *
nodeset_as_regexp(struct info *info, struct nodeset *ns, int glob) {
    struct regexp *result = NULL;
    struct regexp **rx = NULL;
    int used = 0;

    for (int i = 0; i < ns->used; i++) {
        if (ns->nodes[i]->value != NULL)
            used += 1;
    }

    if (used == 0) {
        /* If the nodeset is empty, make sure we produce a regexp
         * that never matches anything */
        result = make_regexp_unescape(info, "[^\001-\7ff]", 0);
    } else {
        if (ALLOC_N(rx, ns->used) < 0)
            goto error;
        for (int i=0; i < ns->used; i++) {
            if (ns->nodes[i]->value == NULL)
                continue;

            if (glob)
                rx[i] = make_regexp_from_glob(info, ns->nodes[i]->value);
            else
                rx[i] = make_regexp_unescape(info, ns->nodes[i]->value, 0);
            if (rx[i] == NULL)
                goto error;
        }
        result = regexp_union_n(info, ns->used, rx);
    }

 error:
    if (rx != NULL) {
        for (int i=0; i < ns->used; i++)
            unref(rx[i], regexp);
        free(rx);
    }
    return result;
}

static void func_regexp_or_glob(struct state *state, int glob) {
    value_ind_t vind = make_value(T_REGEXP, state);
    int r;

    RET_ON_ERROR;

    struct value *v = pop_value(state);
    struct regexp *rx = NULL;

    if (v->tag == T_STRING) {
        if (glob)
            rx = make_regexp_from_glob(state->error->info, v->string);
        else
            rx = make_regexp_unescape(state->error->info, v->string, 0);
    } else if (v->tag == T_NODESET) {
        rx = nodeset_as_regexp(state->error->info, v->nodeset, glob);
    } else {
        assert(0);
    }

    if (rx == NULL) {
        STATE_ENOMEM;
        return;
    }

    state->value_pool[vind].regexp = rx;
    r = regexp_compile(rx);
    if (r < 0) {
        const char *msg;
        regexp_check(rx, &msg);
        state->errmsg = strdup(msg);
        STATE_ERROR(state, PATHX_EREGEXP);
        return;
    }
    push_value(vind, state);
}

static void func_regexp(struct state *state) {
    func_regexp_or_glob(state, 0);
}

static void func_glob(struct state *state) {
    func_regexp_or_glob(state, 1);
}

static bool coerce_to_bool(struct value *v) {
    switch (v->tag) {
    case T_NODESET:
        return v->nodeset->used > 0;
        break;
    case T_BOOLEAN:
        return v->boolval;
        break;
    case T_NUMBER:
        return v->number > 0;
        break;
    case T_STRING:
        return strlen(v->string) > 0;
        break;
    case T_REGEXP:
        return true;
    default:
        assert(0);
        return false;
    }
}

static int calc_eq_nodeset_nodeset(struct nodeset *ns1, struct nodeset *ns2,
                                   int neq) {
    for (int i1=0; i1 < ns1->used; i1++) {
        struct tree *t1 = ns1->nodes[i1];
        for (int i2=0; i2 < ns2->used; i2++) {
            struct tree *t2 = ns2->nodes[i2];
            if (neq) {
                if (!streqx(t1->value, t2->value))
                    return 1;
            } else {
                if (streqx(t1->value, t2->value))
                    return 1;
            }
        }
    }
    return 0;
}

static int calc_eq_nodeset_string(struct nodeset *ns, const char *s,
                                  int neq) {
    for (int i=0; i < ns->used; i++) {
        struct tree *t = ns->nodes[i];
        if (neq) {
            if (!streqx(t->value, s))
                return 1;
        } else {
            if (streqx(t->value, s))
                return 1;
        }
    }
    return 0;
}

static void eval_eq(struct state *state, int neq) {
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    int res;

    if (l->tag == T_NODESET && r->tag == T_NODESET) {
        res = calc_eq_nodeset_nodeset(l->nodeset, r->nodeset, neq);
    } else if (l->tag == T_NODESET) {
        res = calc_eq_nodeset_string(l->nodeset, r->string, neq);
    } else if (r->tag == T_NODESET) {
        res = calc_eq_nodeset_string(r->nodeset, l->string, neq);
    } else if (l->tag == T_NUMBER && r->tag == T_NUMBER) {
        if (neq)
            res = (l->number != r->number);
        else
            res = (l->number == r->number);
    } else {
        assert(l->tag == T_STRING);
        assert(r->tag == T_STRING);
        res = streqx(l->string, r->string);
        if (neq)
            res = !res;
    }
    RET_ON_ERROR;

    push_boolean_value(res, state);
}

static void eval_arith(struct state *state, enum binary_op op) {
    value_ind_t vind = make_value(T_NUMBER, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    int res;

    assert(l->tag == T_NUMBER);
    assert(r->tag == T_NUMBER);

    RET_ON_ERROR;

    if (op == OP_PLUS)
        res = l->number + r->number;
    else if (op == OP_MINUS)
        res = l->number - r->number;
    else if (op == OP_STAR)
        res = l->number * r->number;
    else
        assert(0);

    state->value_pool[vind].number = res;
    push_value(vind, state);
}

static void eval_rel(struct state *state, bool greater, bool equal) {
    struct value *r, *l;
    int res;

    /* We always check l < r or l <= r */
    if (greater) {
        l = pop_value(state);
        r = pop_value(state);
    } else {
        r = pop_value(state);
        l = pop_value(state);
    }
    if (l->tag == T_NUMBER) {
        if (equal)
            res = (l->number <= r->number);
        else
            res = (l->number < r->number);
    } else if (l->tag == T_STRING) {
        int cmp = strcmp(l->string, r->string);
        if (equal)
            res = cmp <= 0;
        else
            res = cmp < 0;
    } else {
        assert(0);
    }

    push_boolean_value(res, state);
}

static void eval_and_or(struct state *state, enum binary_op op) {
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    bool left = coerce_to_bool(l);
    bool right = coerce_to_bool(r);


    if (op == OP_AND)
        push_boolean_value(left && right, state);
    else
        push_boolean_value(left || right, state);
}

static bool eval_re_match_str(struct state *state, struct regexp *rx,
                              const char *str) {
    int r;

    if (str == NULL)
        str = "";

    r = regexp_match(rx, str, strlen(str), 0, NULL);
    if (r == -2) {
        STATE_ERROR(state, PATHX_EINTERNAL);
    } else if (r == -3) {
        /* We should never get this far; func_regexp should catch
         * invalid regexps */
        assert(false);
    }
    return r == strlen(str);
}

static void eval_union(struct state *state) {
    value_ind_t vind = make_value(T_NODESET, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    struct nodeset *res = NULL;

    assert(l->tag == T_NODESET);
    assert(r->tag == T_NODESET);

    RET_ON_ERROR;

    res = clone_nodeset(l->nodeset, state);
    RET_ON_ERROR;
    for (int i=0; i < r->nodeset->used; i++) {
        ns_add(res, r->nodeset->nodes[i], state);
        RET_ON_ERROR;
    }
    state->value_pool[vind].nodeset = res;
    push_value(vind, state);
}

static void eval_concat_string(struct state *state) {
    value_ind_t vind = make_value(T_STRING, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    char *res = NULL;

    RET_ON_ERROR;

    if (ALLOC_N(res, strlen(l->string) + strlen(r->string) + 1) < 0) {
        STATE_ENOMEM;
        return;
    }
    strcpy(res, l->string);
    strcat(res, r->string);
    state->value_pool[vind].string = res;
    push_value(vind, state);
}

static void eval_concat_regexp(struct state *state) {
    value_ind_t vind = make_value(T_REGEXP, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    struct regexp *rx = NULL;

    RET_ON_ERROR;

    rx = regexp_concat(state->error->info, l->regexp, r->regexp);
    if (rx == NULL) {
        STATE_ENOMEM;
        return;
    }

    state->value_pool[vind].regexp = rx;
    push_value(vind, state);
}

static void eval_re_match(struct state *state, enum binary_op op) {
    struct value *rx  = pop_value(state);
    struct value *v = pop_value(state);

    bool result = false;

    if (v->tag == T_STRING) {
        result = eval_re_match_str(state, rx->regexp, v->string);
        RET_ON_ERROR;
    } else if (v->tag == T_NODESET) {
        for (int i=0; i < v->nodeset->used && result == false; i++) {
            struct tree *t = v->nodeset->nodes[i];
            result = eval_re_match_str(state, rx->regexp, t->value);
            RET_ON_ERROR;
        }
    }
    if (op == OP_RE_NOMATCH)
        result = !result;
    push_boolean_value(result, state);
}

static void eval_binary(struct expr *expr, struct state *state) {
    eval_expr(expr->left, state);
    eval_expr(expr->right, state);
    RET_ON_ERROR;

    switch (expr->op) {
    case OP_EQ:
        eval_eq(state, 0);
        break;
    case OP_NEQ:
        eval_eq(state, 1);
        break;
    case OP_LT:
        eval_rel(state, false, false);
        break;
    case OP_LE:
        eval_rel(state, false, true);
        break;
    case OP_GT:
        eval_rel(state, true, false);
        break;
    case OP_GE:
        eval_rel(state, true, true);
        break;
    case OP_PLUS:
        if (expr->type == T_NUMBER)
            eval_arith(state, expr->op);
        else if (expr->type == T_STRING)
            eval_concat_string(state);
        else if (expr->type == T_REGEXP)
            eval_concat_regexp(state);
        break;
    case OP_MINUS:
    case OP_STAR:
        eval_arith(state, expr->op);
        break;
    case OP_AND:
    case OP_OR:
        eval_and_or(state, expr->op);
        break;
    case OP_UNION:
        eval_union(state);
        break;
    case OP_RE_MATCH:
    case OP_RE_NOMATCH:
        eval_re_match(state, expr->op);
        break;
    default:
        assert(0);
    }
}

static void eval_app(struct expr *expr, struct state *state) {
    assert(expr->tag == E_APP);

    for (int i=0; i < expr->func->arity; i++) {
        eval_expr(expr->args[i], state);
        RET_ON_ERROR;
    }
    expr->func->impl(state);
}

static bool eval_pred(struct expr *expr, struct state *state) {
    eval_expr(expr, state);
    RET0_ON_ERROR;

    struct value *v = pop_value(state);
    switch(v->tag) {
    case T_BOOLEAN:
        return v->boolval;
    case T_NUMBER:
        return (state->ctx_pos == v->number);
    case T_NODESET:
        return v->nodeset->used > 0;
    default:
        assert(0);
        return false;
    }
}

static void ns_remove(struct nodeset *ns, int ind) {
    memmove(ns->nodes + ind, ns->nodes + ind+1,
            sizeof(ns->nodes[0]) * (ns->used - (ind+1)));
    ns->used -= 1;
}

/*
 * Remove all nodes from NS for which one of PRED is false<commit_msg>* src/pathx.c: pass the number of actual arguments to the func implementation<commit_after>/*
 * pathx.c: handling path expressions
 *
 * Copyright (C) 2007-2011 <NAME>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 *
 * Author: <NAME> <<EMAIL>>
 */

#include <config.h>
#include <internal.h>
#include <stdint.h>
#include <stdbool.h>
#include <memory.h>
#include <ctype.h>

#include "ref.h"
#include "regexp.h"
#include "errcode.h"

static const char *const errcodes[] = {
    "no error",
    "empty name",
    "illegal string literal",
    "illegal number",
    "string missing ending ' or \"",
    "expected '='",
    "allocation failed",
    "unmatched '['",
    "unmatched '('",
    "expected a '/'",
    "internal error",                             /* PATHX_EINTERNAL */
    "type error",                                 /* PATHX_ETYPE */
    "undefined variable",                         /* PATHX_ENOVAR */
    "garbage at end of path expression",          /* PATHX_EEND */
    "no match for path expression",               /* PATHX_ENOMATCH */
    "wrong number of arguments in function call", /* PATHX_EARITY */
    "invalid regular expression",                 /* PATHX_EREGEXP */
    "too many matches"                            /* PATHX_EMMATCH */
};

/*
 * Path expressions are strings that use a notation modelled on XPath.
 */

enum type {
    T_NONE = 0,     /* Not a type */
    T_NODESET,
    T_BOOLEAN,
    T_NUMBER,
    T_STRING,
    T_REGEXP
};

enum expr_tag {
    E_FILTER,
    E_BINARY,
    E_VALUE,
    E_VAR,
    E_APP
};

enum binary_op {
    OP_EQ,         /* '='  */
    OP_NEQ,        /* '!=' */
    OP_LT,         /* '<'  */
    OP_LE,         /* '<=' */
    OP_GT,         /* '>'  */
    OP_GE,         /* '>=' */
    OP_PLUS,       /* '+'  */
    OP_MINUS,      /* '-'  */
    OP_STAR,       /* '*'  */
    OP_AND,        /* 'and' */
    OP_OR,         /* 'or' */
    OP_RE_MATCH,   /* '=~' */
    OP_RE_NOMATCH, /* '!~' */
    OP_UNION       /* '|' */
};

struct pred {
    int               nexpr;
    struct expr     **exprs;
};

enum axis {
    SELF,
    CHILD,
    DESCENDANT,
    DESCENDANT_OR_SELF,
    PARENT,
    ANCESTOR,
    ROOT,
    PRECEDING_SIBLING,
    FOLLOWING_SIBLING
};

/* This array is indexed by enum axis */
static const char *const axis_names[] = {
    "self",
    "child",
    "descendant",
    "descendant-or-self",
    "parent",
    "ancestor",
    "root",
    "preceding-sibling",
    "following-sibling"
};

static const char *const axis_sep = "::";

/* Doubly linked list of location steps. Besides the information from the
 * path expression, also contains information to iterate over a node set,
 * in particular, the context node CTX for the step, and the current node
 * CUR within that context.
 */
struct step {
    struct step *next;
    enum axis    axis;
    char        *name;              /* NULL to match any name */
    struct pred *predicates;
};

/* Initialise the root nodeset with the first step */
static struct tree *step_root(struct step *step, struct tree *ctx,
                              struct tree *root_ctx);
/* Iteration over the nodes on a step, ignoring the predicates */
static struct tree *step_first(struct step *step, struct tree *ctx);
static struct tree *step_next(struct step *step, struct tree *ctx,
                              struct tree *node);

struct pathx_symtab {
    struct pathx_symtab *next;
    char                *name;
    struct value        *value;
};

struct pathx {
    struct state   *state;
    struct nodeset *nodeset;
    int             node;
    struct tree    *origin;
};

#define L_BRACK '['
#define R_BRACK ']'

struct locpath {
    struct step *steps;
};

struct nodeset {
    struct tree **nodes;
    size_t        used;
    size_t        size;
};

typedef uint32_t value_ind_t;

struct value {
    enum type tag;
    union {
        struct nodeset  *nodeset;     /* T_NODESET */
        int              number;      /* T_NUMBER  */
        char            *string;      /* T_STRING  */
        bool             boolval;     /* T_BOOLEAN */
        struct regexp   *regexp;      /* T_REGEXP  */
    };
};

struct expr {
    enum expr_tag tag;
    enum type     type;
    union {
        struct {                       /* E_FILTER */
            struct expr     *primary;
            struct pred     *predicates;
            struct locpath  *locpath;
        };
        struct {                       /* E_BINARY */
            enum binary_op op;
            struct expr *left;
            struct expr *right;
        };
        value_ind_t      value_ind;    /* E_VALUE */
        char            *ident;        /* E_VAR */
        struct {                       /* E_APP */
            const struct func *func;
            struct expr       **args;
        };
    };
};

struct locpath_trace {
    unsigned int      maxns;
    struct nodeset  **ns;
    struct locpath   *lp;
};

/* Internal state of the evaluator/parser */
struct state {
    pathx_errcode_t errcode;
    const char     *file;
    int             line;
    char           *errmsg;

    const char     *txt;  /* Entire expression */
    const char     *pos;  /* Current position within TXT during parsing */

    struct tree *ctx; /* The current node */
    uint            ctx_pos;
    uint            ctx_len;

    struct tree *root_ctx; /* Root context for relative paths */

    /* A table of all values. The table is dynamically reallocated, i.e.
     * pointers to struct value should not be used across calls that
     * might allocate new values
     *
     * value_pool[0] is always the boolean false, and value_pool[1]
     * always the boolean true
     */
    struct value  *value_pool;
    value_ind_t    value_pool_used;
    value_ind_t    value_pool_size;
    /* Stack of values (as indices into value_pool), with bottom of
       stack in values[0] */
    value_ind_t   *values;
    size_t         values_used;
    size_t         values_size;
    /* Stack of expressions, with bottom of stack in exprs[0] */
    struct expr  **exprs;
    size_t         exprs_used;
    size_t         exprs_size;
    /* Trace of a locpath evaluation, needed by pathx_expand_tree.
       Generally NULL, unless a trace is needed.
     */
    struct locpath_trace *locpath_trace;
    /* Symbol table for variable lookups */
    struct pathx_symtab *symtab;
    /* Error structure, used to communicate errors to struct augeas;
     * we never own this structure, and therefore never free it */
    struct error        *error;
};

/* We consider NULL and the empty string to be equal */
ATTRIBUTE_PURE
static inline int streqx(const char *s1, const char *s2) {
    if (s1 == NULL)
        return (s2 == NULL || strlen(s2) == 0);
    if (s2 == NULL)
        return strlen(s1) == 0;
    return STREQ(s1, s2);
}

/* Functions */

typedef void (*func_impl_t)(struct state *state, int nargs);

struct func {
    const char      *name;
    unsigned int     arity;
    enum type        type;
    const enum type *arg_types;
    func_impl_t      impl;
};

static void func_last(struct state *state, int nargs);
static void func_position(struct state *state, int nargs);
static void func_count(struct state *state, int nargs);
static void func_label(struct state *state, int nargs);
static void func_regexp(struct state *state, int nargs);
static void func_glob(struct state *state, int nargs);
static void func_int(struct state *state, int nargs);

static const enum type const arg_types_nodeset[] = { T_NODESET };
static const enum type const arg_types_string[] = { T_STRING };
static const enum type const arg_types_bool[] = { T_BOOLEAN };

static const struct func builtin_funcs[] = {
    { .name = "last", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
      .impl = func_last },
    { .name = "position", .arity = 0, .type = T_NUMBER, .arg_types = NULL,
      .impl = func_position },
    { .name = "label", .arity = 0, .type = T_STRING, .arg_types = NULL,
      .impl = func_label },
    { .name = "count", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_nodeset,
      .impl = func_count },
    { .name = "regexp", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_string,
      .impl = func_regexp },
    { .name = "regexp", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_nodeset,
      .impl = func_regexp },
    { .name = "glob", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_string,
      .impl = func_glob },
    { .name = "glob", .arity = 1, .type = T_REGEXP,
      .arg_types = arg_types_nodeset,
      .impl = func_glob },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_string, .impl = func_int },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_nodeset, .impl = func_int },
    { .name = "int", .arity = 1, .type = T_NUMBER,
      .arg_types = arg_types_bool, .impl = func_int }
};

#define RET_ON_ERROR                                                    \
    if (state->errcode != PATHX_NOERROR) return

#define RET0_ON_ERROR                                                   \
    if (state->errcode != PATHX_NOERROR) return 0

#define STATE_ERROR(state, err)                                         \
    do {                                                                \
        state->errcode = err;                                           \
        state->file = __FILE__;                                         \
        state->line = __LINE__;                                         \
    } while (0)

#define HAS_ERROR(state) (state->errcode != PATHX_NOERROR)

#define STATE_ENOMEM STATE_ERROR(state, PATHX_ENOMEM)

#define ENOMEM_ON_NULL(state, v)                                        \
    do {                                                                \
        if (v == NULL) {                                                \
            STATE_ERROR(state, PATHX_ENOMEM);                           \
            return NULL;                                                \
        }                                                               \
    } while (0);

/*
 * Free the various data structures
 */

static void free_expr(struct expr *expr);

static void free_pred(struct pred *pred) {
    if (pred == NULL)
        return;

    for (int i=0; i < pred->nexpr; i++) {
        free_expr(pred->exprs[i]);
    }
    free(pred->exprs);
    free(pred);
}

static void free_step(struct step *step) {
    while (step != NULL) {
        struct step *del = step;
        step = del->next;
        free(del->name);
        free_pred(del->predicates);
        free(del);
    }
}

static void free_locpath(struct locpath *locpath) {
    if (locpath == NULL)
        return;
    while (locpath->steps != NULL) {
        struct step *step = locpath->steps;
        locpath->steps = step->next;
        free(step->name);
        free_pred(step->predicates);
        free(step);
    }
    free(locpath);
}

static void free_expr(struct expr *expr) {
    if (expr == NULL)
        return;
    switch (expr->tag) {
    case E_FILTER:
        free_expr(expr->primary);
        free_pred(expr->predicates);
        free_locpath(expr->locpath);
        break;
    case E_BINARY:
        free_expr(expr->left);
        free_expr(expr->right);
        break;
    case E_VALUE:
        break;
    case E_VAR:
        free(expr->ident);
        break;
    case E_APP:
        for (int i=0; i < expr->func->arity; i++)
            free_expr(expr->args[i]);
        free(expr->args);
        break;
    default:
        assert(0);
    }
    free(expr);
}

static void free_nodeset(struct nodeset *ns) {
    if (ns != NULL) {
        free(ns->nodes);
        free(ns);
    }
}

/* Free all objects used by VALUE, but not VALUE itself */
static void release_value(struct value *v) {
    if (v == NULL)
        return;

    switch (v->tag) {
    case T_NODESET:
        free_nodeset(v->nodeset);
        break;
    case T_STRING:
        free(v->string);
        break;
    case T_BOOLEAN:
    case T_NUMBER:
        break;
    case T_REGEXP:
        unref(v->regexp, regexp);
        break;
    default:
        assert(0);
    }
}

static void free_state(struct state *state) {
    if (state == NULL)
        return;

    for(int i=0; i < state->exprs_used; i++)
        free_expr(state->exprs[i]);
    free(state->exprs);

    for(int i=0; i < state->value_pool_used; i++)
        release_value(state->value_pool + i);
    free(state->value_pool);
    free(state->values);
    free(state);
}

void free_pathx(struct pathx *pathx) {
    if (pathx == NULL)
        return;
    free_state(pathx->state);
    free(pathx);
}

/*
 * Nodeset helpers
 */
static struct nodeset *make_nodeset(struct state *state) {
    struct nodeset *result;
    if (ALLOC(result) < 0)
        STATE_ENOMEM;
    return result;
}

static void ns_add(struct nodeset *ns, struct tree *node,
                   struct state *state) {
    for (int i=0; i < ns->used; i++)
        if (ns->nodes[i] == node)
            return;
    if (ns->used >= ns->size) {
        size_t size = 2 * ns->size;
        if (size < 10) size = 10;
        if (REALLOC_N(ns->nodes, size) < 0)
            STATE_ENOMEM;
        ns->size = size;
    }
    ns->nodes[ns->used] = node;
    ns->used += 1;
}

static struct nodeset *
clone_nodeset(struct nodeset *ns, struct state *state)
{
    struct nodeset *clone;
    if (ALLOC(clone) < 0) {
        STATE_ENOMEM;
        return NULL;
    }
    if (ALLOC_N(clone->nodes, ns->used) < 0) {
        free(clone);
        STATE_ENOMEM;
        return NULL;
    }
    clone->used = ns->used;
    clone->size = ns->used;
    for (int i=0; i < ns->used; i++)
        clone->nodes[i] = ns->nodes[i];
    return clone;
}

/*
 * Handling values
 */
static value_ind_t make_value(enum type tag, struct state *state) {
    assert(tag != T_BOOLEAN);

    if (state->value_pool_used >= state->value_pool_size) {
        value_ind_t new_size = 2*state->value_pool_size;
        if (new_size <= state->value_pool_size) {
            STATE_ENOMEM;
            return 0;
        }
        if (REALLOC_N(state->value_pool, new_size) < 0) {
            STATE_ENOMEM;
            return 0;
        }
        state->value_pool_size = new_size;
    }
    state->value_pool[state->value_pool_used].tag = tag;
    state->value_pool[state->value_pool_used].nodeset = NULL;
    return state->value_pool_used++;
}

ATTRIBUTE_UNUSED
static value_ind_t clone_value(struct value *v, struct state *state) {
    value_ind_t vind = make_value(v->tag, state);
    RET0_ON_ERROR;
    struct value *clone = state->value_pool + vind;

    switch (v->tag) {
    case T_NODESET:
        clone->nodeset = clone_nodeset(v->nodeset, state);
        break;
    case T_NUMBER:
        clone->number = v->number;
        break;
    case T_STRING:
        clone->string = strdup(v->string);
        if (clone->string == NULL) {
            FREE(clone);
            STATE_ENOMEM;
        }
        break;
    case T_BOOLEAN:
        clone->boolval = v->boolval;
        break;
    case T_REGEXP:
        clone->regexp = ref(v->regexp);
        break;
    default:
        assert(0);
    }
    return vind;
}

static value_ind_t pop_value_ind(struct state *state) {
    if (state->values_used > 0) {
        state->values_used -= 1;
        return state->values[state->values_used];
    } else {
        STATE_ERROR(state, PATHX_EINTERNAL);
        assert(0);
        return 0;
    }
}

static struct value *pop_value(struct state *state) {
    value_ind_t vind = pop_value_ind(state);
    if (HAS_ERROR(state))
        return NULL;
    return state->value_pool + vind;
}

static void push_value(value_ind_t vind, struct state *state) {
    if (state->values_used >= state->values_size) {
        size_t new_size = 2*state->values_size;
        if (new_size == 0) new_size = 8;
        if (REALLOC_N(state->values, new_size) < 0) {
            STATE_ENOMEM;
            return;
        }
        state->values_size = new_size;
    }
    state->values[state->values_used++] = vind;
}

static void push_boolean_value(int b, struct state *state) {
    push_value(b != 0, state);
}

ATTRIBUTE_PURE
static struct value *expr_value(struct expr *expr, struct state *state) {
    return state->value_pool + expr->value_ind;
}

/*************************************************************************
 * Evaluation
 ************************************************************************/
static void eval_expr(struct expr *expr, struct state *state);


#define ensure_arity(min, max)                                          \
    if (nargs < min || nargs > max) {                                   \
        STATE_ERROR(state, PATHX_EINTERNAL);                            \
        return;                                                         \
    }

static void func_last(struct state *state, int nargs) {
    ensure_arity(0, 0);
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    state->value_pool[vind].number = state->ctx_len;
    push_value(vind, state);
}

static void func_position(struct state *state, int nargs) {
    ensure_arity(0, 0);
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    state->value_pool[vind].number = state->ctx_pos;
    push_value(vind, state);
}

static void func_count(struct state *state, int nargs) {
    ensure_arity(1, 1);
    value_ind_t vind = make_value(T_NUMBER, state);
    RET_ON_ERROR;

    struct value *ns = pop_value(state);
    state->value_pool[vind].number = ns->nodeset->used;
    push_value(vind, state);
}

static void func_label(struct state *state, int nargs) {
    ensure_arity(0, 0);
    value_ind_t vind = make_value(T_STRING, state);
    char *s;

    RET_ON_ERROR;

    if (state->ctx->label)
        s = strdup(state->ctx->label);
    else
        s = strdup("");
    if (s == NULL) {
        STATE_ENOMEM;
        return;
    }
    state->value_pool[vind].string = s;
    push_value(vind, state);
}

static void func_int(struct state *state, int nargs) {
    ensure_arity(1, 1);
    value_ind_t vind = make_value(T_NUMBER, state);
    int64_t i = -1;
    RET_ON_ERROR;

    struct value *v = pop_value(state);
    if (v->tag == T_BOOLEAN) {
        i = v->boolval;
    } else {
        const char *s = NULL;
        if (v->tag == T_STRING) {
            s = v->string;
        } else {
            /* T_NODESET */
            if (v->nodeset->used != 1) {
                STATE_ERROR(state, PATHX_EMMATCH);
                return;
            }
            s = v->nodeset->nodes[0]->value;
        }
        if (s != NULL) {
            int r;
            r = xstrtoint64(s, 10, &i);
            if (r < 0) {
                STATE_ERROR(state, PATHX_ENUMBER);
                return;
            }
        }
    }
    state->value_pool[vind].number = i;
    push_value(vind, state);
}

static struct regexp *
nodeset_as_regexp(struct info *info, struct nodeset *ns, int glob) {
    struct regexp *result = NULL;
    struct regexp **rx = NULL;
    int used = 0;

    for (int i = 0; i < ns->used; i++) {
        if (ns->nodes[i]->value != NULL)
            used += 1;
    }

    if (used == 0) {
        /* If the nodeset is empty, make sure we produce a regexp
         * that never matches anything */
        result = make_regexp_unescape(info, "[^\001-\7ff]", 0);
    } else {
        if (ALLOC_N(rx, ns->used) < 0)
            goto error;
        for (int i=0; i < ns->used; i++) {
            if (ns->nodes[i]->value == NULL)
                continue;

            if (glob)
                rx[i] = make_regexp_from_glob(info, ns->nodes[i]->value);
            else
                rx[i] = make_regexp_unescape(info, ns->nodes[i]->value, 0);
            if (rx[i] == NULL)
                goto error;
        }
        result = regexp_union_n(info, ns->used, rx);
    }

 error:
    if (rx != NULL) {
        for (int i=0; i < ns->used; i++)
            unref(rx[i], regexp);
        free(rx);
    }
    return result;
}

static void func_regexp_or_glob(struct state *state, int glob) {
    value_ind_t vind = make_value(T_REGEXP, state);
    int r;

    RET_ON_ERROR;

    struct value *v = pop_value(state);
    struct regexp *rx = NULL;

    if (v->tag == T_STRING) {
        if (glob)
            rx = make_regexp_from_glob(state->error->info, v->string);
        else
            rx = make_regexp_unescape(state->error->info, v->string, 0);
    } else if (v->tag == T_NODESET) {
        rx = nodeset_as_regexp(state->error->info, v->nodeset, glob);
    } else {
        assert(0);
    }

    if (rx == NULL) {
        STATE_ENOMEM;
        return;
    }

    state->value_pool[vind].regexp = rx;
    r = regexp_compile(rx);
    if (r < 0) {
        const char *msg;
        regexp_check(rx, &msg);
        state->errmsg = strdup(msg);
        STATE_ERROR(state, PATHX_EREGEXP);
        return;
    }
    push_value(vind, state);
}

static void func_regexp(struct state *state, int nargs) {
    ensure_arity(1, 1);
    func_regexp_or_glob(state, 0);
}

static void func_glob(struct state *state, int nargs) {
    ensure_arity(1, 1);
    func_regexp_or_glob(state, 1);
}

static bool coerce_to_bool(struct value *v) {
    switch (v->tag) {
    case T_NODESET:
        return v->nodeset->used > 0;
        break;
    case T_BOOLEAN:
        return v->boolval;
        break;
    case T_NUMBER:
        return v->number > 0;
        break;
    case T_STRING:
        return strlen(v->string) > 0;
        break;
    case T_REGEXP:
        return true;
    default:
        assert(0);
        return false;
    }
}

static int calc_eq_nodeset_nodeset(struct nodeset *ns1, struct nodeset *ns2,
                                   int neq) {
    for (int i1=0; i1 < ns1->used; i1++) {
        struct tree *t1 = ns1->nodes[i1];
        for (int i2=0; i2 < ns2->used; i2++) {
            struct tree *t2 = ns2->nodes[i2];
            if (neq) {
                if (!streqx(t1->value, t2->value))
                    return 1;
            } else {
                if (streqx(t1->value, t2->value))
                    return 1;
            }
        }
    }
    return 0;
}

static int calc_eq_nodeset_string(struct nodeset *ns, const char *s,
                                  int neq) {
    for (int i=0; i < ns->used; i++) {
        struct tree *t = ns->nodes[i];
        if (neq) {
            if (!streqx(t->value, s))
                return 1;
        } else {
            if (streqx(t->value, s))
                return 1;
        }
    }
    return 0;
}

static void eval_eq(struct state *state, int neq) {
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    int res;

    if (l->tag == T_NODESET && r->tag == T_NODESET) {
        res = calc_eq_nodeset_nodeset(l->nodeset, r->nodeset, neq);
    } else if (l->tag == T_NODESET) {
        res = calc_eq_nodeset_string(l->nodeset, r->string, neq);
    } else if (r->tag == T_NODESET) {
        res = calc_eq_nodeset_string(r->nodeset, l->string, neq);
    } else if (l->tag == T_NUMBER && r->tag == T_NUMBER) {
        if (neq)
            res = (l->number != r->number);
        else
            res = (l->number == r->number);
    } else {
        assert(l->tag == T_STRING);
        assert(r->tag == T_STRING);
        res = streqx(l->string, r->string);
        if (neq)
            res = !res;
    }
    RET_ON_ERROR;

    push_boolean_value(res, state);
}

static void eval_arith(struct state *state, enum binary_op op) {
    value_ind_t vind = make_value(T_NUMBER, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    int res;

    assert(l->tag == T_NUMBER);
    assert(r->tag == T_NUMBER);

    RET_ON_ERROR;

    if (op == OP_PLUS)
        res = l->number + r->number;
    else if (op == OP_MINUS)
        res = l->number - r->number;
    else if (op == OP_STAR)
        res = l->number * r->number;
    else
        assert(0);

    state->value_pool[vind].number = res;
    push_value(vind, state);
}

static void eval_rel(struct state *state, bool greater, bool equal) {
    struct value *r, *l;
    int res;

    /* We always check l < r or l <= r */
    if (greater) {
        l = pop_value(state);
        r = pop_value(state);
    } else {
        r = pop_value(state);
        l = pop_value(state);
    }
    if (l->tag == T_NUMBER) {
        if (equal)
            res = (l->number <= r->number);
        else
            res = (l->number < r->number);
    } else if (l->tag == T_STRING) {
        int cmp = strcmp(l->string, r->string);
        if (equal)
            res = cmp <= 0;
        else
            res = cmp < 0;
    } else {
        assert(0);
    }

    push_boolean_value(res, state);
}

static void eval_and_or(struct state *state, enum binary_op op) {
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    bool left = coerce_to_bool(l);
    bool right = coerce_to_bool(r);


    if (op == OP_AND)
        push_boolean_value(left && right, state);
    else
        push_boolean_value(left || right, state);
}

static bool eval_re_match_str(struct state *state, struct regexp *rx,
                              const char *str) {
    int r;

    if (str == NULL)
        str = "";

    r = regexp_match(rx, str, strlen(str), 0, NULL);
    if (r == -2) {
        STATE_ERROR(state, PATHX_EINTERNAL);
    } else if (r == -3) {
        /* We should never get this far; func_regexp should catch
         * invalid regexps */
        assert(false);
    }
    return r == strlen(str);
}

static void eval_union(struct state *state) {
    value_ind_t vind = make_value(T_NODESET, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    struct nodeset *res = NULL;

    assert(l->tag == T_NODESET);
    assert(r->tag == T_NODESET);

    RET_ON_ERROR;

    res = clone_nodeset(l->nodeset, state);
    RET_ON_ERROR;
    for (int i=0; i < r->nodeset->used; i++) {
        ns_add(res, r->nodeset->nodes[i], state);
        RET_ON_ERROR;
    }
    state->value_pool[vind].nodeset = res;
    push_value(vind, state);
}

static void eval_concat_string(struct state *state) {
    value_ind_t vind = make_value(T_STRING, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    char *res = NULL;

    RET_ON_ERROR;

    if (ALLOC_N(res, strlen(l->string) + strlen(r->string) + 1) < 0) {
        STATE_ENOMEM;
        return;
    }
    strcpy(res, l->string);
    strcat(res, r->string);
    state->value_pool[vind].string = res;
    push_value(vind, state);
}

static void eval_concat_regexp(struct state *state) {
    value_ind_t vind = make_value(T_REGEXP, state);
    struct value *r = pop_value(state);
    struct value *l = pop_value(state);
    struct regexp *rx = NULL;

    RET_ON_ERROR;

    rx = regexp_concat(state->error->info, l->regexp, r->regexp);
    if (rx == NULL) {
        STATE_ENOMEM;
        return;
    }

    state->value_pool[vind].regexp = rx;
    push_value(vind, state);
}

static void eval_re_match(struct state *state, enum binary_op op) {
    struct value *rx  = pop_value(state);
    struct value *v = pop_value(state);

    bool result = false;

    if (v->tag == T_STRING) {
        result = eval_re_match_str(state, rx->regexp, v->string);
        RET_ON_ERROR;
    } else if (v->tag == T_NODESET) {
        for (int i=0; i < v->nodeset->used && result == false; i++) {
            struct tree *t = v->nodeset->nodes[i];
            result = eval_re_match_str(state, rx->regexp, t->value);
            RET_ON_ERROR;
        }
    }
    if (op == OP_RE_NOMATCH)
        result = !result;
    push_boolean_value(result, state);
}

static void eval_binary(struct expr *expr, struct state *state) {
    eval_expr(expr->left, state);
    eval_expr(expr->right, state);
    RET_ON_ERROR;

    switch (expr->op) {
    case OP_EQ:
        eval_eq(state, 0);
        break;
    case OP_NEQ:
        eval_eq(state, 1);
        break;
    case OP_LT:
        eval_rel(state, false, false);
        break;
    case OP_LE:
        eval_rel(state, false, true);
        break;
    case OP_GT:
        eval_rel(state, true, false);
        break;
    case OP_GE:
        eval_rel(state, true, true);
        break;
    case OP_PLUS:
        if (expr->type == T_NUMBER)
            eval_arith(state, expr->op);
        else if (expr->type == T_STRING)
            eval_concat_string(state);
        else if (expr->type == T_REGEXP)
            eval_concat_regexp(state);
        break;
    case OP_MINUS:
    case OP_STAR:
        eval_arith(state, expr->op);
        break;
    case OP_AND:
    case OP_OR:
        eval_and_or(state, expr->op);
        break;
    case OP_UNION:
        eval_union(state);
        break;
    case OP_RE_MATCH:
    case OP_RE_NOMATCH:
        eval_re_match(state, expr->op);
        break;
    default:
        assert(0);
    }
}

static void eval_app(struct expr *expr, struct state *state) {
    assert(expr->tag == E_APP);

    for (int i=0; i < expr->func->arity; i++) {
        eval_expr(expr->args[i], state);
        RET_ON_ERROR;
    }
    expr->func->impl(state, expr->func->arity);
}

static bool eval_pred(struct expr *expr, struct state *state) {
    eval_expr(expr, state);
    RET0_ON_ERROR;

    struct value *v = pop_value(state);
    switch(v->tag) {
    case T_BOOLEAN:
        return v->boolval;
    case T_NUMBER:
        return (state->ctx_pos == v->number);
    case T_NODESET:
        return v->nodeset->used > 0;
    default:
        assert(0);
        return false;
    }
}

static void ns_remove(struct nodeset *ns, int ind) {
    memmove(ns->nodes + ind, ns->nodes + ind+1,
            sizeof(ns->nodes[0]) * (ns->used - (ind+1)));
    ns->used -= 1;
}

/*
 * Remove all nodes from NS for which one of PRED is false
{'fraction_non_alphanumeric': 0.12866049812622293, 'fraction_numerical': 0.0059695552681325245, 'mean_word_length': 1.9422354490901108, 'pattern_counts': {'":': 2, '<': 94, '<?xml version=': 0, '>': 562, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 55, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5139334', 'n_tokens_mistral': 20066, 'n_tokens_neox': 19662, 'n_words': 5134}