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 * self)13 static void strfilter_node__delete(struct strfilter_node *self)
14 {
15 if (self) {
16 if (self->p && !is_operator(*self->p))
17 free((char *)self->p);
18 strfilter_node__delete(self->l);
19 strfilter_node__delete(self->r);
20 free(self);
21 }
22 }
23
strfilter__delete(struct strfilter * self)24 void strfilter__delete(struct strfilter *self)
25 {
26 if (self) {
27 strfilter_node__delete(self->root);
28 free(self);
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 *ret = zalloc(sizeof(struct strfilter_node));
66
67 if (ret) {
68 ret->p = op;
69 ret->l = l;
70 ret->r = r;
71 }
72
73 return ret;
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 *ret = zalloc(sizeof(struct strfilter));
158 const char *ep = NULL;
159
160 if (ret)
161 ret->root = strfilter_node__new(rules, &ep);
162
163 if (!ret || !ret->root || *ep != '\0') {
164 if (err)
165 *err = ep;
166 strfilter__delete(ret);
167 ret = NULL;
168 }
169
170 return ret;
171 }
172
strfilter_node__compare(struct strfilter_node * self,const char * str)173 static bool strfilter_node__compare(struct strfilter_node *self,
174 const char *str)
175 {
176 if (!self || !self->p)
177 return false;
178
179 switch (*self->p) {
180 case '|': /* OR */
181 return strfilter_node__compare(self->l, str) ||
182 strfilter_node__compare(self->r, str);
183 case '&': /* AND */
184 return strfilter_node__compare(self->l, str) &&
185 strfilter_node__compare(self->r, str);
186 case '!': /* NOT */
187 return !strfilter_node__compare(self->r, str);
188 default:
189 return strglobmatch(str, self->p);
190 }
191 }
192
193 /* Return true if STR matches the filter rules */
strfilter__compare(struct strfilter * self,const char * str)194 bool strfilter__compare(struct strfilter *self, const char *str)
195 {
196 if (!self)
197 return false;
198 return strfilter_node__compare(self->root, str);
199 }
200