// SPDX-License-Identifier: GPL-2.0
#include "string2.h"
#include "strfilter.h"

#include <errno.h>
#include <stdlib.h>
#include <linux/ctype.h>
#include <linux/string.h>
#include <linux/zalloc.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 *node)
{
        if (node) {
                if (node->p && !is_operator(*node->p))
                        zfree((char **)&node->p);
                strfilter_node__delete(node->l);
                strfilter_node__delete(node->r);
                free(node);
        }
}

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

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

        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 *node = zalloc(sizeof(*node));

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

        return node;
}

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 *filter = zalloc(sizeof(*filter));
        const char *ep = NULL;

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

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

        return filter;
}

static int strfilter__append(struct strfilter *filter, bool _or,
                             const char *rules, const char **err)
{
        struct strfilter_node *right, *root;
        const char *ep = NULL;

        if (!filter || !rules)
                return -EINVAL;

        right = strfilter_node__new(rules, &ep);
        if (!right || *ep != '\0') {
                if (err)
                        *err = ep;
                goto error;
        }
        root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
        if (!root) {
                ep = NULL;
                goto error;
        }

        filter->root = root;
        return 0;

error:
        strfilter_node__delete(right);
        return ep ? -EINVAL : -ENOMEM;
}

int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
{
        return strfilter__append(filter, true, rules, err);
}

int strfilter__and(struct strfilter *filter, const char *rules,
                   const char **err)
{
        return strfilter__append(filter, false, rules, err);
}

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

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

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

static int strfilter_node__sprint(struct strfilter_node *node, char *buf);

/* sprint node in parenthesis if needed */
static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
{
        int len;
        int pt = node->r ? 2 : 0;       /* don't need to check node->l */

        if (buf && pt)
                *buf++ = '(';
        len = strfilter_node__sprint(node, buf);
        if (len < 0)
                return len;
        if (buf && pt)
                *(buf + len) = ')';
        return len + pt;
}

static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
{
        int len = 0, rlen;

        if (!node || !node->p)
                return -EINVAL;

        switch (*node->p) {
        case '|':
        case '&':
                len = strfilter_node__sprint_pt(node->l, buf);
                if (len < 0)
                        return len;
                fallthrough;
        case '!':
                if (buf) {
                        *(buf + len++) = *node->p;
                        buf += len;
                } else
                        len++;
                rlen = strfilter_node__sprint_pt(node->r, buf);
                if (rlen < 0)
                        return rlen;
                len += rlen;
                break;
        default:
                len = strlen(node->p);
                if (buf)
                        strcpy(buf, node->p);
        }

        return len;
}

char *strfilter__string(struct strfilter *filter)
{
        int len;
        char *ret = NULL;

        len = strfilter_node__sprint(filter->root, NULL);
        if (len < 0)
                return NULL;

        ret = malloc(len + 1);
        if (ret)
                strfilter_node__sprint(filter->root, ret);

        return ret;
}