Loading...
1// SPDX-License-Identifier: GPL-2.0
2#include "string2.h"
3#include "strfilter.h"
4
5#include <errno.h>
6#include <stdlib.h>
7#include <linux/ctype.h>
8#include <linux/string.h>
9#include <linux/zalloc.h>
10
11/* Operators */
12static const char *OP_and = "&"; /* Logical AND */
13static const char *OP_or = "|"; /* Logical OR */
14static const char *OP_not = "!"; /* Logical NOT */
15
16#define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
17#define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
18
19static void strfilter_node__delete(struct strfilter_node *node)
20{
21 if (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);
26 free(node);
27 }
28}
29
30void strfilter__delete(struct strfilter *filter)
31{
32 if (filter) {
33 strfilter_node__delete(filter->root);
34 free(filter);
35 }
36}
37
38static const char *get_token(const char *s, const char **e)
39{
40 const char *p;
41
42 s = skip_spaces(s);
43
44 if (*s == '\0') {
45 p = s;
46 goto end;
47 }
48
49 p = s + 1;
50 if (!is_separator(*s)) {
51 /* End search */
52retry:
53 while (*p && !is_separator(*p) && !isspace(*p))
54 p++;
55 /* Escape and special case: '!' is also used in glob pattern */
56 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
57 p++;
58 goto retry;
59 }
60 }
61end:
62 *e = p;
63 return s;
64}
65
66static struct strfilter_node *strfilter_node__alloc(const char *op,
67 struct strfilter_node *l,
68 struct strfilter_node *r)
69{
70 struct strfilter_node *node = zalloc(sizeof(*node));
71
72 if (node) {
73 node->p = op;
74 node->l = l;
75 node->r = r;
76 }
77
78 return node;
79}
80
81static struct strfilter_node *strfilter_node__new(const char *s,
82 const char **ep)
83{
84 struct strfilter_node root, *cur, *last_op;
85 const char *e;
86
87 if (!s)
88 return NULL;
89
90 memset(&root, 0, sizeof(root));
91 last_op = cur = &root;
92
93 s = get_token(s, &e);
94 while (*s != '\0' && *s != ')') {
95 switch (*s) {
96 case '&': /* Exchg last OP->r with AND */
97 if (!cur->r || !last_op->r)
98 goto error;
99 cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
100 if (!cur)
101 goto nomem;
102 last_op->r = cur;
103 last_op = cur;
104 break;
105 case '|': /* Exchg the root with OR */
106 if (!cur->r || !root.r)
107 goto error;
108 cur = strfilter_node__alloc(OP_or, root.r, NULL);
109 if (!cur)
110 goto nomem;
111 root.r = cur;
112 last_op = cur;
113 break;
114 case '!': /* Add NOT as a leaf node */
115 if (cur->r)
116 goto error;
117 cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
118 if (!cur->r)
119 goto nomem;
120 cur = cur->r;
121 break;
122 case '(': /* Recursively parses inside the parenthesis */
123 if (cur->r)
124 goto error;
125 cur->r = strfilter_node__new(s + 1, &s);
126 if (!s)
127 goto nomem;
128 if (!cur->r || *s != ')')
129 goto error;
130 e = s + 1;
131 break;
132 default:
133 if (cur->r)
134 goto error;
135 cur->r = strfilter_node__alloc(NULL, NULL, NULL);
136 if (!cur->r)
137 goto nomem;
138 cur->r->p = strndup(s, e - s);
139 if (!cur->r->p)
140 goto nomem;
141 }
142 s = get_token(e, &e);
143 }
144 if (!cur->r)
145 goto error;
146 *ep = s;
147 return root.r;
148nomem:
149 s = NULL;
150error:
151 *ep = s;
152 strfilter_node__delete(root.r);
153 return NULL;
154}
155
156/*
157 * Parse filter rule and return new strfilter.
158 * Return NULL if fail, and *ep == NULL if memory allocation failed.
159 */
160struct strfilter *strfilter__new(const char *rules, const char **err)
161{
162 struct strfilter *filter = zalloc(sizeof(*filter));
163 const char *ep = NULL;
164
165 if (filter)
166 filter->root = strfilter_node__new(rules, &ep);
167
168 if (!filter || !filter->root || *ep != '\0') {
169 if (err)
170 *err = ep;
171 strfilter__delete(filter);
172 filter = NULL;
173 }
174
175 return filter;
176}
177
178static int strfilter__append(struct strfilter *filter, bool _or,
179 const char *rules, const char **err)
180{
181 struct strfilter_node *right, *root;
182 const char *ep = NULL;
183
184 if (!filter || !rules)
185 return -EINVAL;
186
187 right = strfilter_node__new(rules, &ep);
188 if (!right || *ep != '\0') {
189 if (err)
190 *err = ep;
191 goto error;
192 }
193 root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
194 if (!root) {
195 ep = NULL;
196 goto error;
197 }
198
199 filter->root = root;
200 return 0;
201
202error:
203 strfilter_node__delete(right);
204 return ep ? -EINVAL : -ENOMEM;
205}
206
207int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
208{
209 return strfilter__append(filter, true, rules, err);
210}
211
212int strfilter__and(struct strfilter *filter, const char *rules,
213 const char **err)
214{
215 return strfilter__append(filter, false, rules, err);
216}
217
218static bool strfilter_node__compare(struct strfilter_node *node,
219 const char *str)
220{
221 if (!node || !node->p)
222 return false;
223
224 switch (*node->p) {
225 case '|': /* OR */
226 return strfilter_node__compare(node->l, str) ||
227 strfilter_node__compare(node->r, str);
228 case '&': /* AND */
229 return strfilter_node__compare(node->l, str) &&
230 strfilter_node__compare(node->r, str);
231 case '!': /* NOT */
232 return !strfilter_node__compare(node->r, str);
233 default:
234 return strglobmatch(str, node->p);
235 }
236}
237
238/* Return true if STR matches the filter rules */
239bool strfilter__compare(struct strfilter *filter, const char *str)
240{
241 if (!filter)
242 return false;
243 return strfilter_node__compare(filter->root, str);
244}
245
246static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
247
248/* sprint node in parenthesis if needed */
249static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
250{
251 int len;
252 int pt = node->r ? 2 : 0; /* don't need to check node->l */
253
254 if (buf && pt)
255 *buf++ = '(';
256 len = strfilter_node__sprint(node, buf);
257 if (len < 0)
258 return len;
259 if (buf && pt)
260 *(buf + len) = ')';
261 return len + pt;
262}
263
264static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
265{
266 int len = 0, rlen;
267
268 if (!node || !node->p)
269 return -EINVAL;
270
271 switch (*node->p) {
272 case '|':
273 case '&':
274 len = strfilter_node__sprint_pt(node->l, buf);
275 if (len < 0)
276 return len;
277 __fallthrough;
278 case '!':
279 if (buf) {
280 *(buf + len++) = *node->p;
281 buf += len;
282 } else
283 len++;
284 rlen = strfilter_node__sprint_pt(node->r, buf);
285 if (rlen < 0)
286 return rlen;
287 len += rlen;
288 break;
289 default:
290 len = strlen(node->p);
291 if (buf)
292 strcpy(buf, node->p);
293 }
294
295 return len;
296}
297
298char *strfilter__string(struct strfilter *filter)
299{
300 int len;
301 char *ret = NULL;
302
303 len = strfilter_node__sprint(filter->root, NULL);
304 if (len < 0)
305 return NULL;
306
307 ret = malloc(len + 1);
308 if (ret)
309 strfilter_node__sprint(filter->root, ret);
310
311 return ret;
312}
1// SPDX-License-Identifier: GPL-2.0
2#include "string2.h"
3#include "strfilter.h"
4
5#include <errno.h>
6#include <stdlib.h>
7#include <linux/ctype.h>
8#include <linux/string.h>
9#include <linux/zalloc.h>
10
11/* Operators */
12static const char *OP_and = "&"; /* Logical AND */
13static const char *OP_or = "|"; /* Logical OR */
14static const char *OP_not = "!"; /* Logical NOT */
15
16#define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!')
17#define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
18
19static void strfilter_node__delete(struct strfilter_node *node)
20{
21 if (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);
26 free(node);
27 }
28}
29
30void strfilter__delete(struct strfilter *filter)
31{
32 if (filter) {
33 strfilter_node__delete(filter->root);
34 free(filter);
35 }
36}
37
38static const char *get_token(const char *s, const char **e)
39{
40 const char *p;
41
42 s = skip_spaces(s);
43
44 if (*s == '\0') {
45 p = s;
46 goto end;
47 }
48
49 p = s + 1;
50 if (!is_separator(*s)) {
51 /* End search */
52retry:
53 while (*p && !is_separator(*p) && !isspace(*p))
54 p++;
55 /* Escape and special case: '!' is also used in glob pattern */
56 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
57 p++;
58 goto retry;
59 }
60 }
61end:
62 *e = p;
63 return s;
64}
65
66static struct strfilter_node *strfilter_node__alloc(const char *op,
67 struct strfilter_node *l,
68 struct strfilter_node *r)
69{
70 struct strfilter_node *node = zalloc(sizeof(*node));
71
72 if (node) {
73 node->p = op;
74 node->l = l;
75 node->r = r;
76 }
77
78 return node;
79}
80
81static struct strfilter_node *strfilter_node__new(const char *s,
82 const char **ep)
83{
84 struct strfilter_node root, *cur, *last_op;
85 const char *e;
86
87 if (!s)
88 return NULL;
89
90 memset(&root, 0, sizeof(root));
91 last_op = cur = &root;
92
93 s = get_token(s, &e);
94 while (*s != '\0' && *s != ')') {
95 switch (*s) {
96 case '&': /* Exchg last OP->r with AND */
97 if (!cur->r || !last_op->r)
98 goto error;
99 cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
100 if (!cur)
101 goto nomem;
102 last_op->r = cur;
103 last_op = cur;
104 break;
105 case '|': /* Exchg the root with OR */
106 if (!cur->r || !root.r)
107 goto error;
108 cur = strfilter_node__alloc(OP_or, root.r, NULL);
109 if (!cur)
110 goto nomem;
111 root.r = cur;
112 last_op = cur;
113 break;
114 case '!': /* Add NOT as a leaf node */
115 if (cur->r)
116 goto error;
117 cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
118 if (!cur->r)
119 goto nomem;
120 cur = cur->r;
121 break;
122 case '(': /* Recursively parses inside the parenthesis */
123 if (cur->r)
124 goto error;
125 cur->r = strfilter_node__new(s + 1, &s);
126 if (!s)
127 goto nomem;
128 if (!cur->r || *s != ')')
129 goto error;
130 e = s + 1;
131 break;
132 default:
133 if (cur->r)
134 goto error;
135 cur->r = strfilter_node__alloc(NULL, NULL, NULL);
136 if (!cur->r)
137 goto nomem;
138 cur->r->p = strndup(s, e - s);
139 if (!cur->r->p)
140 goto nomem;
141 }
142 s = get_token(e, &e);
143 }
144 if (!cur->r)
145 goto error;
146 *ep = s;
147 return root.r;
148nomem:
149 s = NULL;
150error:
151 *ep = s;
152 strfilter_node__delete(root.r);
153 return NULL;
154}
155
156/*
157 * Parse filter rule and return new strfilter.
158 * Return NULL if fail, and *ep == NULL if memory allocation failed.
159 */
160struct strfilter *strfilter__new(const char *rules, const char **err)
161{
162 struct strfilter *filter = zalloc(sizeof(*filter));
163 const char *ep = NULL;
164
165 if (filter)
166 filter->root = strfilter_node__new(rules, &ep);
167
168 if (!filter || !filter->root || *ep != '\0') {
169 if (err)
170 *err = ep;
171 strfilter__delete(filter);
172 filter = NULL;
173 }
174
175 return filter;
176}
177
178static int strfilter__append(struct strfilter *filter, bool _or,
179 const char *rules, const char **err)
180{
181 struct strfilter_node *right, *root;
182 const char *ep = NULL;
183
184 if (!filter || !rules)
185 return -EINVAL;
186
187 right = strfilter_node__new(rules, &ep);
188 if (!right || *ep != '\0') {
189 if (err)
190 *err = ep;
191 goto error;
192 }
193 root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
194 if (!root) {
195 ep = NULL;
196 goto error;
197 }
198
199 filter->root = root;
200 return 0;
201
202error:
203 strfilter_node__delete(right);
204 return ep ? -EINVAL : -ENOMEM;
205}
206
207int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
208{
209 return strfilter__append(filter, true, rules, err);
210}
211
212int strfilter__and(struct strfilter *filter, const char *rules,
213 const char **err)
214{
215 return strfilter__append(filter, false, rules, err);
216}
217
218static bool strfilter_node__compare(struct strfilter_node *node,
219 const char *str)
220{
221 if (!node || !node->p)
222 return false;
223
224 switch (*node->p) {
225 case '|': /* OR */
226 return strfilter_node__compare(node->l, str) ||
227 strfilter_node__compare(node->r, str);
228 case '&': /* AND */
229 return strfilter_node__compare(node->l, str) &&
230 strfilter_node__compare(node->r, str);
231 case '!': /* NOT */
232 return !strfilter_node__compare(node->r, str);
233 default:
234 return strglobmatch(str, node->p);
235 }
236}
237
238/* Return true if STR matches the filter rules */
239bool strfilter__compare(struct strfilter *filter, const char *str)
240{
241 if (!filter)
242 return false;
243 return strfilter_node__compare(filter->root, str);
244}
245
246static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
247
248/* sprint node in parenthesis if needed */
249static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
250{
251 int len;
252 int pt = node->r ? 2 : 0; /* don't need to check node->l */
253
254 if (buf && pt)
255 *buf++ = '(';
256 len = strfilter_node__sprint(node, buf);
257 if (len < 0)
258 return len;
259 if (buf && pt)
260 *(buf + len) = ')';
261 return len + pt;
262}
263
264static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
265{
266 int len = 0, rlen;
267
268 if (!node || !node->p)
269 return -EINVAL;
270
271 switch (*node->p) {
272 case '|':
273 case '&':
274 len = strfilter_node__sprint_pt(node->l, buf);
275 if (len < 0)
276 return len;
277 fallthrough;
278 case '!':
279 if (buf) {
280 *(buf + len++) = *node->p;
281 buf += len;
282 } else
283 len++;
284 rlen = strfilter_node__sprint_pt(node->r, buf);
285 if (rlen < 0)
286 return rlen;
287 len += rlen;
288 break;
289 default:
290 len = strlen(node->p);
291 if (buf)
292 strcpy(buf, node->p);
293 }
294
295 return len;
296}
297
298char *strfilter__string(struct strfilter *filter)
299{
300 int len;
301 char *ret = NULL;
302
303 len = strfilter_node__sprint(filter->root, NULL);
304 if (len < 0)
305 return NULL;
306
307 ret = malloc(len + 1);
308 if (ret)
309 strfilter_node__sprint(filter->root, ret);
310
311 return ret;
312}