strfilter.c

Go to the documentation of this file.

#include "util.h"
#include "string.h"
#include "strfilter.h"

/* Operators */
static const char *OP_and   = "&";  /* Logical AND */
static const char *OP_or    = "|";  /* Logical OR */
static const char *OP_not   = "!";  /* Logical NOT */

#define is_operator(c)  ((c) == '|' || (c) == '&' || (c) == '!')
#define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')

static void strfilter_node__delete(struct strfilter_node *self)
{
    if (self) {
        if (self->p && !is_operator(*self->p))
            free((char *)self->p);
        strfilter_node__delete(self->l);
        strfilter_node__delete(self->r);
        free(self);
    }
}

void strfilter__delete(struct strfilter *self)
{
    if (self) {
        strfilter_node__delete(self->root);
        free(self);
    }
}

static const char *get_token(const char *s, const char **e)
{
    const char *p;

    while (isspace(*s)) /* Skip spaces */
        s++;

    if (*s == '\0') {
        p = s;
        goto end;
    }

    p = s + 1;
    if (!is_separator(*s)) {
        /* End search */
retry:
        while (*p && !is_separator(*p) && !isspace(*p))
            p++;
        /* Escape and special case: '!' is also used in glob pattern */
        if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
            p++;
            goto retry;
        }
    }
end:
    *e = p;
    return s;
}

static struct strfilter_node *strfilter_node__alloc(const char *op,
                            struct strfilter_node *l,
                            struct strfilter_node *r)
{
    struct strfilter_node *ret = zalloc(sizeof(struct strfilter_node));

    if (ret) {
        ret->p = op;
        ret->l = l;
        ret->r = r;
    }

    return ret;
}

static struct strfilter_node *strfilter_node__new(const char *s,
                          const char **ep)
{
    struct strfilter_node root, *cur, *last_op;
    const char *e;

    if (!s)
        return NULL;

    memset(&root, 0, sizeof(root));
    last_op = cur = &root;

    s = get_token(s, &e);
    while (*s != '\0' && *s != ')') {
        switch (*s) {
        case '&':   /* Exchg last OP->r with AND */
            if (!cur->r || !last_op->r)
                goto error;
            cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
            if (!cur)
                goto nomem;
            last_op->r = cur;
            last_op = cur;
            break;
        case '|':   /* Exchg the root with OR */
            if (!cur->r || !root.r)
                goto error;
            cur = strfilter_node__alloc(OP_or, root.r, NULL);
            if (!cur)
                goto nomem;
            root.r = cur;
            last_op = cur;
            break;
        case '!':   /* Add NOT as a leaf node */
            if (cur->r)
                goto error;
            cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
            if (!cur->r)
                goto nomem;
            cur = cur->r;
            break;
        case '(':   /* Recursively parses inside the parenthesis */
            if (cur->r)
                goto error;
            cur->r = strfilter_node__new(s + 1, &s);
            if (!s)
                goto nomem;
            if (!cur->r || *s != ')')
                goto error;
            e = s + 1;
            break;
        default:
            if (cur->r)
                goto error;
            cur->r = strfilter_node__alloc(NULL, NULL, NULL);
            if (!cur->r)
                goto nomem;
            cur->r->p = strndup(s, e - s);
            if (!cur->r->p)
                goto nomem;
        }
        s = get_token(e, &e);
    }
    if (!cur->r)
        goto error;
    *ep = s;
    return root.r;
nomem:
    s = NULL;
error:
    *ep = s;
    strfilter_node__delete(root.r);
    return NULL;
}

/*
 * Parse filter rule and return new strfilter.
 * Return NULL if fail, and *ep == NULL if memory allocation failed.
 */
struct strfilter *strfilter__new(const char *rules, const char **err)
{
    struct strfilter *ret = zalloc(sizeof(struct strfilter));
    const char *ep = NULL;

    if (ret)
        ret->root = strfilter_node__new(rules, &ep);

    if (!ret || !ret->root || *ep != '\0') {
        if (err)
            *err = ep;
        strfilter__delete(ret);
        ret = NULL;
    }

    return ret;
}

static bool strfilter_node__compare(struct strfilter_node *self,
                    const char *str)
{
    if (!self || !self->p)
        return false;

    switch (*self->p) {
    case '|':   /* OR */
        return strfilter_node__compare(self->l, str) ||
            strfilter_node__compare(self->r, str);
    case '&':   /* AND */
        return strfilter_node__compare(self->l, str) &&
            strfilter_node__compare(self->r, str);
    case '!':   /* NOT */
        return !strfilter_node__compare(self->r, str);
    default:
        return strglobmatch(str, self->p);
    }
}

/* Return true if STR matches the filter rules */
bool strfilter__compare(struct strfilter *self, const char *str)
{
    if (!self)
        return false;
    return strfilter_node__compare(self->root, str);
}