1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
2a067558eSArnaldo Carvalho de Melo #include "string2.h"
368baa431SMasami Hiramatsu #include "strfilter.h"
468baa431SMasami Hiramatsu
5a43783aeSArnaldo Carvalho de Melo #include <errno.h>
67f7c536fSArnaldo Carvalho de Melo #include <stdlib.h>
73052ba56SArnaldo Carvalho de Melo #include <linux/ctype.h>
8c1fc14cbSArnaldo Carvalho de Melo #include <linux/string.h>
97f7c536fSArnaldo Carvalho de Melo #include <linux/zalloc.h>
103d689ed6SArnaldo Carvalho de Melo
1168baa431SMasami Hiramatsu /* Operators */
1268baa431SMasami Hiramatsu static const char *OP_and = "&"; /* Logical AND */
1368baa431SMasami Hiramatsu static const char *OP_or = "|"; /* Logical OR */
1468baa431SMasami Hiramatsu static const char *OP_not = "!"; /* Logical NOT */
1568baa431SMasami Hiramatsu
1668baa431SMasami Hiramatsu #define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
1768baa431SMasami Hiramatsu #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
1868baa431SMasami Hiramatsu
strfilter_node__delete(struct strfilter_node * node)19c824c433SArnaldo Carvalho de Melo static void strfilter_node__delete(struct strfilter_node *node)
2068baa431SMasami Hiramatsu {
21c824c433SArnaldo Carvalho de Melo if (node) {
22c824c433SArnaldo Carvalho de Melo if (node->p && !is_operator(*node->p))
2374cf249dSArnaldo Carvalho de Melo zfree((char **)&node->p);
24c824c433SArnaldo Carvalho de Melo strfilter_node__delete(node->l);
25c824c433SArnaldo Carvalho de Melo strfilter_node__delete(node->r);
26c824c433SArnaldo Carvalho de Melo free(node);
2768baa431SMasami Hiramatsu }
2868baa431SMasami Hiramatsu }
2968baa431SMasami Hiramatsu
strfilter__delete(struct strfilter * filter)30c824c433SArnaldo Carvalho de Melo void strfilter__delete(struct strfilter *filter)
3168baa431SMasami Hiramatsu {
32c824c433SArnaldo Carvalho de Melo if (filter) {
33c824c433SArnaldo Carvalho de Melo strfilter_node__delete(filter->root);
34c824c433SArnaldo Carvalho de Melo free(filter);
3568baa431SMasami Hiramatsu }
3668baa431SMasami Hiramatsu }
3768baa431SMasami Hiramatsu
get_token(const char * s,const char ** e)3868baa431SMasami Hiramatsu static const char *get_token(const char *s, const char **e)
3968baa431SMasami Hiramatsu {
4068baa431SMasami Hiramatsu const char *p;
4168baa431SMasami Hiramatsu
42c1fc14cbSArnaldo Carvalho de Melo s = skip_spaces(s);
4368baa431SMasami Hiramatsu
4468baa431SMasami Hiramatsu if (*s == '\0') {
4568baa431SMasami Hiramatsu p = s;
4668baa431SMasami Hiramatsu goto end;
4768baa431SMasami Hiramatsu }
4868baa431SMasami Hiramatsu
4968baa431SMasami Hiramatsu p = s + 1;
5068baa431SMasami Hiramatsu if (!is_separator(*s)) {
5168baa431SMasami Hiramatsu /* End search */
5268baa431SMasami Hiramatsu retry:
5368baa431SMasami Hiramatsu while (*p && !is_separator(*p) && !isspace(*p))
5468baa431SMasami Hiramatsu p++;
5568baa431SMasami Hiramatsu /* Escape and special case: '!' is also used in glob pattern */
5668baa431SMasami Hiramatsu if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
5768baa431SMasami Hiramatsu p++;
5868baa431SMasami Hiramatsu goto retry;
5968baa431SMasami Hiramatsu }
6068baa431SMasami Hiramatsu }
6168baa431SMasami Hiramatsu end:
6268baa431SMasami Hiramatsu *e = p;
6368baa431SMasami Hiramatsu return s;
6468baa431SMasami Hiramatsu }
6568baa431SMasami Hiramatsu
strfilter_node__alloc(const char * op,struct strfilter_node * l,struct strfilter_node * r)6668baa431SMasami Hiramatsu static struct strfilter_node *strfilter_node__alloc(const char *op,
6768baa431SMasami Hiramatsu struct strfilter_node *l,
6868baa431SMasami Hiramatsu struct strfilter_node *r)
6968baa431SMasami Hiramatsu {
70316c7136SArnaldo Carvalho de Melo struct strfilter_node *node = zalloc(sizeof(*node));
7168baa431SMasami Hiramatsu
72316c7136SArnaldo Carvalho de Melo if (node) {
73316c7136SArnaldo Carvalho de Melo node->p = op;
74316c7136SArnaldo Carvalho de Melo node->l = l;
75316c7136SArnaldo Carvalho de Melo node->r = r;
7668baa431SMasami Hiramatsu }
7768baa431SMasami Hiramatsu
78316c7136SArnaldo Carvalho de Melo return node;
7968baa431SMasami Hiramatsu }
8068baa431SMasami Hiramatsu
strfilter_node__new(const char * s,const char ** ep)8168baa431SMasami Hiramatsu static struct strfilter_node *strfilter_node__new(const char *s,
8268baa431SMasami Hiramatsu const char **ep)
8368baa431SMasami Hiramatsu {
8468baa431SMasami Hiramatsu struct strfilter_node root, *cur, *last_op;
8568baa431SMasami Hiramatsu const char *e;
8668baa431SMasami Hiramatsu
8768baa431SMasami Hiramatsu if (!s)
8868baa431SMasami Hiramatsu return NULL;
8968baa431SMasami Hiramatsu
9068baa431SMasami Hiramatsu memset(&root, 0, sizeof(root));
9168baa431SMasami Hiramatsu last_op = cur = &root;
9268baa431SMasami Hiramatsu
9368baa431SMasami Hiramatsu s = get_token(s, &e);
9468baa431SMasami Hiramatsu while (*s != '\0' && *s != ')') {
9568baa431SMasami Hiramatsu switch (*s) {
9668baa431SMasami Hiramatsu case '&': /* Exchg last OP->r with AND */
9768baa431SMasami Hiramatsu if (!cur->r || !last_op->r)
9868baa431SMasami Hiramatsu goto error;
9968baa431SMasami Hiramatsu cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
10068baa431SMasami Hiramatsu if (!cur)
10168baa431SMasami Hiramatsu goto nomem;
10268baa431SMasami Hiramatsu last_op->r = cur;
10368baa431SMasami Hiramatsu last_op = cur;
10468baa431SMasami Hiramatsu break;
10568baa431SMasami Hiramatsu case '|': /* Exchg the root with OR */
10668baa431SMasami Hiramatsu if (!cur->r || !root.r)
10768baa431SMasami Hiramatsu goto error;
10868baa431SMasami Hiramatsu cur = strfilter_node__alloc(OP_or, root.r, NULL);
10968baa431SMasami Hiramatsu if (!cur)
11068baa431SMasami Hiramatsu goto nomem;
11168baa431SMasami Hiramatsu root.r = cur;
11268baa431SMasami Hiramatsu last_op = cur;
11368baa431SMasami Hiramatsu break;
11468baa431SMasami Hiramatsu case '!': /* Add NOT as a leaf node */
11568baa431SMasami Hiramatsu if (cur->r)
11668baa431SMasami Hiramatsu goto error;
11768baa431SMasami Hiramatsu cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
11868baa431SMasami Hiramatsu if (!cur->r)
11968baa431SMasami Hiramatsu goto nomem;
12068baa431SMasami Hiramatsu cur = cur->r;
12168baa431SMasami Hiramatsu break;
12268baa431SMasami Hiramatsu case '(': /* Recursively parses inside the parenthesis */
12368baa431SMasami Hiramatsu if (cur->r)
12468baa431SMasami Hiramatsu goto error;
12568baa431SMasami Hiramatsu cur->r = strfilter_node__new(s + 1, &s);
12668baa431SMasami Hiramatsu if (!s)
12768baa431SMasami Hiramatsu goto nomem;
12868baa431SMasami Hiramatsu if (!cur->r || *s != ')')
12968baa431SMasami Hiramatsu goto error;
13068baa431SMasami Hiramatsu e = s + 1;
13168baa431SMasami Hiramatsu break;
13268baa431SMasami Hiramatsu default:
13368baa431SMasami Hiramatsu if (cur->r)
13468baa431SMasami Hiramatsu goto error;
13568baa431SMasami Hiramatsu cur->r = strfilter_node__alloc(NULL, NULL, NULL);
13668baa431SMasami Hiramatsu if (!cur->r)
13768baa431SMasami Hiramatsu goto nomem;
13868baa431SMasami Hiramatsu cur->r->p = strndup(s, e - s);
13968baa431SMasami Hiramatsu if (!cur->r->p)
14068baa431SMasami Hiramatsu goto nomem;
14168baa431SMasami Hiramatsu }
14268baa431SMasami Hiramatsu s = get_token(e, &e);
14368baa431SMasami Hiramatsu }
14468baa431SMasami Hiramatsu if (!cur->r)
14568baa431SMasami Hiramatsu goto error;
14668baa431SMasami Hiramatsu *ep = s;
14768baa431SMasami Hiramatsu return root.r;
14868baa431SMasami Hiramatsu nomem:
14968baa431SMasami Hiramatsu s = NULL;
15068baa431SMasami Hiramatsu error:
15168baa431SMasami Hiramatsu *ep = s;
15268baa431SMasami Hiramatsu strfilter_node__delete(root.r);
15368baa431SMasami Hiramatsu return NULL;
15468baa431SMasami Hiramatsu }
15568baa431SMasami Hiramatsu
15668baa431SMasami Hiramatsu /*
15768baa431SMasami Hiramatsu * Parse filter rule and return new strfilter.
15868baa431SMasami Hiramatsu * Return NULL if fail, and *ep == NULL if memory allocation failed.
15968baa431SMasami Hiramatsu */
strfilter__new(const char * rules,const char ** err)16068baa431SMasami Hiramatsu struct strfilter *strfilter__new(const char *rules, const char **err)
16168baa431SMasami Hiramatsu {
162316c7136SArnaldo Carvalho de Melo struct strfilter *filter = zalloc(sizeof(*filter));
16368baa431SMasami Hiramatsu const char *ep = NULL;
16468baa431SMasami Hiramatsu
165316c7136SArnaldo Carvalho de Melo if (filter)
166316c7136SArnaldo Carvalho de Melo filter->root = strfilter_node__new(rules, &ep);
16768baa431SMasami Hiramatsu
168316c7136SArnaldo Carvalho de Melo if (!filter || !filter->root || *ep != '\0') {
16968baa431SMasami Hiramatsu if (err)
17068baa431SMasami Hiramatsu *err = ep;
171316c7136SArnaldo Carvalho de Melo strfilter__delete(filter);
172316c7136SArnaldo Carvalho de Melo filter = NULL;
17368baa431SMasami Hiramatsu }
17468baa431SMasami Hiramatsu
175316c7136SArnaldo Carvalho de Melo return filter;
17668baa431SMasami Hiramatsu }
17768baa431SMasami Hiramatsu
strfilter__append(struct strfilter * filter,bool _or,const char * rules,const char ** err)1784e60a2caSMasami Hiramatsu static int strfilter__append(struct strfilter *filter, bool _or,
1794e60a2caSMasami Hiramatsu const char *rules, const char **err)
1804e60a2caSMasami Hiramatsu {
1814e60a2caSMasami Hiramatsu struct strfilter_node *right, *root;
1824e60a2caSMasami Hiramatsu const char *ep = NULL;
1834e60a2caSMasami Hiramatsu
1844e60a2caSMasami Hiramatsu if (!filter || !rules)
1854e60a2caSMasami Hiramatsu return -EINVAL;
1864e60a2caSMasami Hiramatsu
1874e60a2caSMasami Hiramatsu right = strfilter_node__new(rules, &ep);
1884e60a2caSMasami Hiramatsu if (!right || *ep != '\0') {
1894e60a2caSMasami Hiramatsu if (err)
1904e60a2caSMasami Hiramatsu *err = ep;
1914e60a2caSMasami Hiramatsu goto error;
1924e60a2caSMasami Hiramatsu }
1934e60a2caSMasami Hiramatsu root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
1944e60a2caSMasami Hiramatsu if (!root) {
1954e60a2caSMasami Hiramatsu ep = NULL;
1964e60a2caSMasami Hiramatsu goto error;
1974e60a2caSMasami Hiramatsu }
1984e60a2caSMasami Hiramatsu
1994e60a2caSMasami Hiramatsu filter->root = root;
2004e60a2caSMasami Hiramatsu return 0;
2014e60a2caSMasami Hiramatsu
2024e60a2caSMasami Hiramatsu error:
2034e60a2caSMasami Hiramatsu strfilter_node__delete(right);
2044e60a2caSMasami Hiramatsu return ep ? -EINVAL : -ENOMEM;
2054e60a2caSMasami Hiramatsu }
2064e60a2caSMasami Hiramatsu
strfilter__or(struct strfilter * filter,const char * rules,const char ** err)2074e60a2caSMasami Hiramatsu int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
2084e60a2caSMasami Hiramatsu {
2094e60a2caSMasami Hiramatsu return strfilter__append(filter, true, rules, err);
2104e60a2caSMasami Hiramatsu }
2114e60a2caSMasami Hiramatsu
strfilter__and(struct strfilter * filter,const char * rules,const char ** err)2124e60a2caSMasami Hiramatsu int strfilter__and(struct strfilter *filter, const char *rules,
2134e60a2caSMasami Hiramatsu const char **err)
2144e60a2caSMasami Hiramatsu {
2154e60a2caSMasami Hiramatsu return strfilter__append(filter, false, rules, err);
2164e60a2caSMasami Hiramatsu }
2174e60a2caSMasami Hiramatsu
strfilter_node__compare(struct strfilter_node * node,const char * str)218c824c433SArnaldo Carvalho de Melo static bool strfilter_node__compare(struct strfilter_node *node,
21968baa431SMasami Hiramatsu const char *str)
22068baa431SMasami Hiramatsu {
221c824c433SArnaldo Carvalho de Melo if (!node || !node->p)
22268baa431SMasami Hiramatsu return false;
22368baa431SMasami Hiramatsu
224c824c433SArnaldo Carvalho de Melo switch (*node->p) {
22568baa431SMasami Hiramatsu case '|': /* OR */
226c824c433SArnaldo Carvalho de Melo return strfilter_node__compare(node->l, str) ||
227c824c433SArnaldo Carvalho de Melo strfilter_node__compare(node->r, str);
22868baa431SMasami Hiramatsu case '&': /* AND */
229c824c433SArnaldo Carvalho de Melo return strfilter_node__compare(node->l, str) &&
230c824c433SArnaldo Carvalho de Melo strfilter_node__compare(node->r, str);
23168baa431SMasami Hiramatsu case '!': /* NOT */
232c824c433SArnaldo Carvalho de Melo return !strfilter_node__compare(node->r, str);
23368baa431SMasami Hiramatsu default:
234c824c433SArnaldo Carvalho de Melo return strglobmatch(str, node->p);
23568baa431SMasami Hiramatsu }
23668baa431SMasami Hiramatsu }
23768baa431SMasami Hiramatsu
23868baa431SMasami Hiramatsu /* Return true if STR matches the filter rules */
strfilter__compare(struct strfilter * filter,const char * str)239316c7136SArnaldo Carvalho de Melo bool strfilter__compare(struct strfilter *filter, const char *str)
24068baa431SMasami Hiramatsu {
241316c7136SArnaldo Carvalho de Melo if (!filter)
24268baa431SMasami Hiramatsu return false;
243316c7136SArnaldo Carvalho de Melo return strfilter_node__compare(filter->root, str);
24468baa431SMasami Hiramatsu }
2453f51972cSMasami Hiramatsu
2463f51972cSMasami Hiramatsu static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
2473f51972cSMasami Hiramatsu
2483f51972cSMasami Hiramatsu /* sprint node in parenthesis if needed */
strfilter_node__sprint_pt(struct strfilter_node * node,char * buf)2493f51972cSMasami Hiramatsu static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
2503f51972cSMasami Hiramatsu {
2513f51972cSMasami Hiramatsu int len;
2523f51972cSMasami Hiramatsu int pt = node->r ? 2 : 0; /* don't need to check node->l */
2533f51972cSMasami Hiramatsu
2543f51972cSMasami Hiramatsu if (buf && pt)
2553f51972cSMasami Hiramatsu *buf++ = '(';
2563f51972cSMasami Hiramatsu len = strfilter_node__sprint(node, buf);
2573f51972cSMasami Hiramatsu if (len < 0)
2583f51972cSMasami Hiramatsu return len;
2593f51972cSMasami Hiramatsu if (buf && pt)
2603f51972cSMasami Hiramatsu *(buf + len) = ')';
2613f51972cSMasami Hiramatsu return len + pt;
2623f51972cSMasami Hiramatsu }
2633f51972cSMasami Hiramatsu
strfilter_node__sprint(struct strfilter_node * node,char * buf)2643f51972cSMasami Hiramatsu static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
2653f51972cSMasami Hiramatsu {
2663f51972cSMasami Hiramatsu int len = 0, rlen;
2673f51972cSMasami Hiramatsu
2683f51972cSMasami Hiramatsu if (!node || !node->p)
2693f51972cSMasami Hiramatsu return -EINVAL;
2703f51972cSMasami Hiramatsu
2713f51972cSMasami Hiramatsu switch (*node->p) {
2723f51972cSMasami Hiramatsu case '|':
2733f51972cSMasami Hiramatsu case '&':
2743f51972cSMasami Hiramatsu len = strfilter_node__sprint_pt(node->l, buf);
2753f51972cSMasami Hiramatsu if (len < 0)
2763f51972cSMasami Hiramatsu return len;
277*f7a858bfSLiam Howlett fallthrough;
2783f51972cSMasami Hiramatsu case '!':
2793f51972cSMasami Hiramatsu if (buf) {
2803f51972cSMasami Hiramatsu *(buf + len++) = *node->p;
2813f51972cSMasami Hiramatsu buf += len;
2823f51972cSMasami Hiramatsu } else
2833f51972cSMasami Hiramatsu len++;
2843f51972cSMasami Hiramatsu rlen = strfilter_node__sprint_pt(node->r, buf);
2853f51972cSMasami Hiramatsu if (rlen < 0)
2863f51972cSMasami Hiramatsu return rlen;
2873f51972cSMasami Hiramatsu len += rlen;
2883f51972cSMasami Hiramatsu break;
2893f51972cSMasami Hiramatsu default:
2903f51972cSMasami Hiramatsu len = strlen(node->p);
2913f51972cSMasami Hiramatsu if (buf)
2923f51972cSMasami Hiramatsu strcpy(buf, node->p);
2933f51972cSMasami Hiramatsu }
2943f51972cSMasami Hiramatsu
2953f51972cSMasami Hiramatsu return len;
2963f51972cSMasami Hiramatsu }
2973f51972cSMasami Hiramatsu
strfilter__string(struct strfilter * filter)2983f51972cSMasami Hiramatsu char *strfilter__string(struct strfilter *filter)
2993f51972cSMasami Hiramatsu {
3003f51972cSMasami Hiramatsu int len;
3013f51972cSMasami Hiramatsu char *ret = NULL;
3023f51972cSMasami Hiramatsu
3033f51972cSMasami Hiramatsu len = strfilter_node__sprint(filter->root, NULL);
3043f51972cSMasami Hiramatsu if (len < 0)
3053f51972cSMasami Hiramatsu return NULL;
3063f51972cSMasami Hiramatsu
3073f51972cSMasami Hiramatsu ret = malloc(len + 1);
3083f51972cSMasami Hiramatsu if (ret)
3093f51972cSMasami Hiramatsu strfilter_node__sprint(filter->root, ret);
3103f51972cSMasami Hiramatsu
3113f51972cSMasami Hiramatsu return ret;
3123f51972cSMasami Hiramatsu }
313