]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
68baa431 | 2 | #include "util.h" |
a067558e | 3 | #include "string2.h" |
68baa431 MH |
4 | #include "strfilter.h" |
5 | ||
a43783ae | 6 | #include <errno.h> |
3d689ed6 ACM |
7 | #include "sane_ctype.h" |
8 | ||
68baa431 MH |
9 | /* Operators */ |
10 | static const char *OP_and = "&"; /* Logical AND */ | |
11 | static const char *OP_or = "|"; /* Logical OR */ | |
12 | static 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 | ||
c824c433 | 17 | static void strfilter_node__delete(struct strfilter_node *node) |
68baa431 | 18 | { |
c824c433 ACM |
19 | if (node) { |
20 | if (node->p && !is_operator(*node->p)) | |
74cf249d | 21 | zfree((char **)&node->p); |
c824c433 ACM |
22 | strfilter_node__delete(node->l); |
23 | strfilter_node__delete(node->r); | |
24 | free(node); | |
68baa431 MH |
25 | } |
26 | } | |
27 | ||
c824c433 | 28 | void strfilter__delete(struct strfilter *filter) |
68baa431 | 29 | { |
c824c433 ACM |
30 | if (filter) { |
31 | strfilter_node__delete(filter->root); | |
32 | free(filter); | |
68baa431 MH |
33 | } |
34 | } | |
35 | ||
36 | static 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 */ | |
51 | retry: | |
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 | } | |
60 | end: | |
61 | *e = p; | |
62 | return s; | |
63 | } | |
64 | ||
65 | static struct strfilter_node *strfilter_node__alloc(const char *op, | |
66 | struct strfilter_node *l, | |
67 | struct strfilter_node *r) | |
68 | { | |
316c7136 | 69 | struct strfilter_node *node = zalloc(sizeof(*node)); |
68baa431 | 70 | |
316c7136 ACM |
71 | if (node) { |
72 | node->p = op; | |
73 | node->l = l; | |
74 | node->r = r; | |
68baa431 MH |
75 | } |
76 | ||
316c7136 | 77 | return node; |
68baa431 MH |
78 | } |
79 | ||
80 | static 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; | |
147 | nomem: | |
148 | s = NULL; | |
149 | error: | |
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 | */ | |
159 | struct strfilter *strfilter__new(const char *rules, const char **err) | |
160 | { | |
316c7136 | 161 | struct strfilter *filter = zalloc(sizeof(*filter)); |
68baa431 MH |
162 | const char *ep = NULL; |
163 | ||
316c7136 ACM |
164 | if (filter) |
165 | filter->root = strfilter_node__new(rules, &ep); | |
68baa431 | 166 | |
316c7136 | 167 | if (!filter || !filter->root || *ep != '\0') { |
68baa431 MH |
168 | if (err) |
169 | *err = ep; | |
316c7136 ACM |
170 | strfilter__delete(filter); |
171 | filter = NULL; | |
68baa431 MH |
172 | } |
173 | ||
316c7136 | 174 | return filter; |
68baa431 MH |
175 | } |
176 | ||
4e60a2ca MH |
177 | static 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 | ||
201 | error: | |
202 | strfilter_node__delete(right); | |
203 | return ep ? -EINVAL : -ENOMEM; | |
204 | } | |
205 | ||
206 | int strfilter__or(struct strfilter *filter, const char *rules, const char **err) | |
207 | { | |
208 | return strfilter__append(filter, true, rules, err); | |
209 | } | |
210 | ||
211 | int strfilter__and(struct strfilter *filter, const char *rules, | |
212 | const char **err) | |
213 | { | |
214 | return strfilter__append(filter, false, rules, err); | |
215 | } | |
216 | ||
c824c433 | 217 | static bool strfilter_node__compare(struct strfilter_node *node, |
68baa431 MH |
218 | const char *str) |
219 | { | |
c824c433 | 220 | if (!node || !node->p) |
68baa431 MH |
221 | return false; |
222 | ||
c824c433 | 223 | switch (*node->p) { |
68baa431 | 224 | case '|': /* OR */ |
c824c433 ACM |
225 | return strfilter_node__compare(node->l, str) || |
226 | strfilter_node__compare(node->r, str); | |
68baa431 | 227 | case '&': /* AND */ |
c824c433 ACM |
228 | return strfilter_node__compare(node->l, str) && |
229 | strfilter_node__compare(node->r, str); | |
68baa431 | 230 | case '!': /* NOT */ |
c824c433 | 231 | return !strfilter_node__compare(node->r, str); |
68baa431 | 232 | default: |
c824c433 | 233 | return strglobmatch(str, node->p); |
68baa431 MH |
234 | } |
235 | } | |
236 | ||
237 | /* Return true if STR matches the filter rules */ | |
316c7136 | 238 | bool strfilter__compare(struct strfilter *filter, const char *str) |
68baa431 | 239 | { |
316c7136 | 240 | if (!filter) |
68baa431 | 241 | return false; |
316c7136 | 242 | return strfilter_node__compare(filter->root, str); |
68baa431 | 243 | } |
3f51972c MH |
244 | |
245 | static int strfilter_node__sprint(struct strfilter_node *node, char *buf); | |
246 | ||
247 | /* sprint node in parenthesis if needed */ | |
248 | static 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 | ||
263 | static 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; | |
d64b721d | 276 | __fallthrough; |
3f51972c MH |
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 | ||
297 | char *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 | } |