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