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