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}
307