• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #include "util.h"
2 #include "string.h"
3 #include "strfilter.h"
4 
5 /* Operators */
6 static const char *OP_and	= "&";	/* Logical AND */
7 static const char *OP_or	= "|";	/* Logical OR */
8 static 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 
strfilter_node__delete(struct strfilter_node * node)13 static 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 
strfilter__delete(struct strfilter * filter)24 void strfilter__delete(struct strfilter *filter)
25 {
26 	if (filter) {
27 		strfilter_node__delete(filter->root);
28 		free(filter);
29 	}
30 }
31 
get_token(const char * s,const char ** e)32 static 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 */
47 retry:
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 	}
56 end:
57 	*e = p;
58 	return s;
59 }
60 
strfilter_node__alloc(const char * op,struct strfilter_node * l,struct strfilter_node * r)61 static 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 
strfilter_node__new(const char * s,const char ** ep)76 static 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;
143 nomem:
144 	s = NULL;
145 error:
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  */
strfilter__new(const char * rules,const char ** err)155 struct 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 
strfilter__append(struct strfilter * filter,bool _or,const char * rules,const char ** err)173 static 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 
197 error:
198 	strfilter_node__delete(right);
199 	return ep ? -EINVAL : -ENOMEM;
200 }
201 
strfilter__or(struct strfilter * filter,const char * rules,const char ** err)202 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
203 {
204 	return strfilter__append(filter, true, rules, err);
205 }
206 
strfilter__and(struct strfilter * filter,const char * rules,const char ** err)207 int strfilter__and(struct strfilter *filter, const char *rules,
208 		   const char **err)
209 {
210 	return strfilter__append(filter, false, rules, err);
211 }
212 
strfilter_node__compare(struct strfilter_node * node,const char * str)213 static 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 */
strfilter__compare(struct strfilter * filter,const char * str)234 bool 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 
241 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
242 
243 /* sprint node in parenthesis if needed */
strfilter_node__sprint_pt(struct strfilter_node * node,char * buf)244 static 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 
strfilter_node__sprint(struct strfilter_node * node,char * buf)259 static 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 		__fallthrough;
273 	case '!':
274 		if (buf) {
275 			*(buf + len++) = *node->p;
276 			buf += len;
277 		} else
278 			len++;
279 		rlen = strfilter_node__sprint_pt(node->r, buf);
280 		if (rlen < 0)
281 			return rlen;
282 		len += rlen;
283 		break;
284 	default:
285 		len = strlen(node->p);
286 		if (buf)
287 			strcpy(buf, node->p);
288 	}
289 
290 	return len;
291 }
292 
strfilter__string(struct strfilter * filter)293 char *strfilter__string(struct strfilter *filter)
294 {
295 	int len;
296 	char *ret = NULL;
297 
298 	len = strfilter_node__sprint(filter->root, NULL);
299 	if (len < 0)
300 		return NULL;
301 
302 	ret = malloc(len + 1);
303 	if (ret)
304 		strfilter_node__sprint(filter->root, ret);
305 
306 	return ret;
307 }
308