Commit | Line | Data |
---|---|---|
68baa431 MH |
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 | ||
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 | ||
24 | void strfilter__delete(struct strfilter *self) | |
25 | { | |
26 | if (self) { | |
27 | strfilter_node__delete(self->root); | |
28 | free(self); | |
29 | } | |
30 | } | |
31 | ||
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 | ||
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 | ||
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 | */ | |
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 | ||
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 */ | |
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 | } |