1 // SPDX-License-Identifier: GPL-2.0
7 #include <linux/ctype.h>
8 #include <linux/string.h>
9 #include <linux/zalloc.h>
12 static const char *OP_and = "&"; /* Logical AND */
13 static const char *OP_or = "|"; /* Logical OR */
14 static const char *OP_not = "!"; /* Logical NOT */
16 #define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
17 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
19 static void strfilter_node__delete(struct strfilter_node *node)
22 if (node->p && !is_operator(*node->p))
23 zfree((char **)&node->p);
24 strfilter_node__delete(node->l);
25 strfilter_node__delete(node->r);
30 void strfilter__delete(struct strfilter *filter)
33 strfilter_node__delete(filter->root);
38 static const char *get_token(const char *s, const char **e)
50 if (!is_separator(*s)) {
53 while (*p && !is_separator(*p) && !isspace(*p))
55 /* Escape and special case: '!' is also used in glob pattern */
56 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
66 static struct strfilter_node *strfilter_node__alloc(const char *op,
67 struct strfilter_node *l,
68 struct strfilter_node *r)
70 struct strfilter_node *node = zalloc(sizeof(*node));
81 static struct strfilter_node *strfilter_node__new(const char *s,
84 struct strfilter_node root, *cur, *last_op;
90 memset(&root, 0, sizeof(root));
91 last_op = cur = &root;
94 while (*s != '\0' && *s != ')') {
96 case '&': /* Exchg last OP->r with AND */
97 if (!cur->r || !last_op->r)
99 cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
105 case '|': /* Exchg the root with OR */
106 if (!cur->r || !root.r)
108 cur = strfilter_node__alloc(OP_or, root.r, NULL);
114 case '!': /* Add NOT as a leaf node */
117 cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
122 case '(': /* Recursively parses inside the parenthesis */
125 cur->r = strfilter_node__new(s + 1, &s);
128 if (!cur->r || *s != ')')
135 cur->r = strfilter_node__alloc(NULL, NULL, NULL);
138 cur->r->p = strndup(s, e - s);
142 s = get_token(e, &e);
152 strfilter_node__delete(root.r);
157 * Parse filter rule and return new strfilter.
158 * Return NULL if fail, and *ep == NULL if memory allocation failed.
160 struct strfilter *strfilter__new(const char *rules, const char **err)
162 struct strfilter *filter = zalloc(sizeof(*filter));
163 const char *ep = NULL;
166 filter->root = strfilter_node__new(rules, &ep);
168 if (!filter || !filter->root || *ep != '\0') {
171 strfilter__delete(filter);
178 static int strfilter__append(struct strfilter *filter, bool _or,
179 const char *rules, const char **err)
181 struct strfilter_node *right, *root;
182 const char *ep = NULL;
184 if (!filter || !rules)
187 right = strfilter_node__new(rules, &ep);
188 if (!right || *ep != '\0') {
193 root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
203 strfilter_node__delete(right);
204 return ep ? -EINVAL : -ENOMEM;
207 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
209 return strfilter__append(filter, true, rules, err);
212 int strfilter__and(struct strfilter *filter, const char *rules,
215 return strfilter__append(filter, false, rules, err);
218 static bool strfilter_node__compare(struct strfilter_node *node,
221 if (!node || !node->p)
226 return strfilter_node__compare(node->l, str) ||
227 strfilter_node__compare(node->r, str);
229 return strfilter_node__compare(node->l, str) &&
230 strfilter_node__compare(node->r, str);
232 return !strfilter_node__compare(node->r, str);
234 return strglobmatch(str, node->p);
238 /* Return true if STR matches the filter rules */
239 bool strfilter__compare(struct strfilter *filter, const char *str)
243 return strfilter_node__compare(filter->root, str);
246 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
248 /* sprint node in parenthesis if needed */
249 static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
252 int pt = node->r ? 2 : 0; /* don't need to check node->l */
256 len = strfilter_node__sprint(node, buf);
264 static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
268 if (!node || !node->p)
274 len = strfilter_node__sprint_pt(node->l, buf);
280 *(buf + len++) = *node->p;
284 rlen = strfilter_node__sprint_pt(node->r, buf);
290 len = strlen(node->p);
292 strcpy(buf, node->p);
298 char *strfilter__string(struct strfilter *filter)
303 len = strfilter_node__sprint(filter->root, NULL);
307 ret = malloc(len + 1);
309 strfilter_node__sprint(filter->root, ret);