]>
Commit | Line | Data |
---|---|---|
68baa431 MH |
1 | #include <ctype.h> |
2 | #include "util.h" | |
3 | #include "string.h" | |
4 | #include "strfilter.h" | |
5 | ||
6 | /* Operators */ | |
7 | static const char *OP_and = "&"; /* Logical AND */ | |
8 | static const char *OP_or = "|"; /* Logical OR */ | |
9 | static const char *OP_not = "!"; /* Logical NOT */ | |
10 | ||
11 | #define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!') | |
12 | #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')') | |
13 | ||
14 | static void strfilter_node__delete(struct strfilter_node *self) | |
15 | { | |
16 | if (self) { | |
17 | if (self->p && !is_operator(*self->p)) | |
18 | free((char *)self->p); | |
19 | strfilter_node__delete(self->l); | |
20 | strfilter_node__delete(self->r); | |
21 | free(self); | |
22 | } | |
23 | } | |
24 | ||
25 | void strfilter__delete(struct strfilter *self) | |
26 | { | |
27 | if (self) { | |
28 | strfilter_node__delete(self->root); | |
29 | free(self); | |
30 | } | |
31 | } | |
32 | ||
33 | static const char *get_token(const char *s, const char **e) | |
34 | { | |
35 | const char *p; | |
36 | ||
37 | while (isspace(*s)) /* Skip spaces */ | |
38 | s++; | |
39 | ||
40 | if (*s == '\0') { | |
41 | p = s; | |
42 | goto end; | |
43 | } | |
44 | ||
45 | p = s + 1; | |
46 | if (!is_separator(*s)) { | |
47 | /* End search */ | |
48 | retry: | |
49 | while (*p && !is_separator(*p) && !isspace(*p)) | |
50 | p++; | |
51 | /* Escape and special case: '!' is also used in glob pattern */ | |
52 | if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) { | |
53 | p++; | |
54 | goto retry; | |
55 | } | |
56 | } | |
57 | end: | |
58 | *e = p; | |
59 | return s; | |
60 | } | |
61 | ||
62 | static struct strfilter_node *strfilter_node__alloc(const char *op, | |
63 | struct strfilter_node *l, | |
64 | struct strfilter_node *r) | |
65 | { | |
66 | struct strfilter_node *ret = zalloc(sizeof(struct strfilter_node)); | |
67 | ||
68 | if (ret) { | |
69 | ret->p = op; | |
70 | ret->l = l; | |
71 | ret->r = r; | |
72 | } | |
73 | ||
74 | return ret; | |
75 | } | |
76 | ||
77 | static struct strfilter_node *strfilter_node__new(const char *s, | |
78 | const char **ep) | |
79 | { | |
80 | struct strfilter_node root, *cur, *last_op; | |
81 | const char *e; | |
82 | ||
83 | if (!s) | |
84 | return NULL; | |
85 | ||
86 | memset(&root, 0, sizeof(root)); | |
87 | last_op = cur = &root; | |
88 | ||
89 | s = get_token(s, &e); | |
90 | while (*s != '\0' && *s != ')') { | |
91 | switch (*s) { | |
92 | case '&': /* Exchg last OP->r with AND */ | |
93 | if (!cur->r || !last_op->r) | |
94 | goto error; | |
95 | cur = strfilter_node__alloc(OP_and, last_op->r, NULL); | |
96 | if (!cur) | |
97 | goto nomem; | |
98 | last_op->r = cur; | |
99 | last_op = cur; | |
100 | break; | |
101 | case '|': /* Exchg the root with OR */ | |
102 | if (!cur->r || !root.r) | |
103 | goto error; | |
104 | cur = strfilter_node__alloc(OP_or, root.r, NULL); | |
105 | if (!cur) | |
106 | goto nomem; | |
107 | root.r = cur; | |
108 | last_op = cur; | |
109 | break; | |
110 | case '!': /* Add NOT as a leaf node */ | |
111 | if (cur->r) | |
112 | goto error; | |
113 | cur->r = strfilter_node__alloc(OP_not, NULL, NULL); | |
114 | if (!cur->r) | |
115 | goto nomem; | |
116 | cur = cur->r; | |
117 | break; | |
118 | case '(': /* Recursively parses inside the parenthesis */ | |
119 | if (cur->r) | |
120 | goto error; | |
121 | cur->r = strfilter_node__new(s + 1, &s); | |
122 | if (!s) | |
123 | goto nomem; | |
124 | if (!cur->r || *s != ')') | |
125 | goto error; | |
126 | e = s + 1; | |
127 | break; | |
128 | default: | |
129 | if (cur->r) | |
130 | goto error; | |
131 | cur->r = strfilter_node__alloc(NULL, NULL, NULL); | |
132 | if (!cur->r) | |
133 | goto nomem; | |
134 | cur->r->p = strndup(s, e - s); | |
135 | if (!cur->r->p) | |
136 | goto nomem; | |
137 | } | |
138 | s = get_token(e, &e); | |
139 | } | |
140 | if (!cur->r) | |
141 | goto error; | |
142 | *ep = s; | |
143 | return root.r; | |
144 | nomem: | |
145 | s = NULL; | |
146 | error: | |
147 | *ep = s; | |
148 | strfilter_node__delete(root.r); | |
149 | return NULL; | |
150 | } | |
151 | ||
152 | /* | |
153 | * Parse filter rule and return new strfilter. | |
154 | * Return NULL if fail, and *ep == NULL if memory allocation failed. | |
155 | */ | |
156 | struct strfilter *strfilter__new(const char *rules, const char **err) | |
157 | { | |
158 | struct strfilter *ret = zalloc(sizeof(struct strfilter)); | |
159 | const char *ep = NULL; | |
160 | ||
161 | if (ret) | |
162 | ret->root = strfilter_node__new(rules, &ep); | |
163 | ||
164 | if (!ret || !ret->root || *ep != '\0') { | |
165 | if (err) | |
166 | *err = ep; | |
167 | strfilter__delete(ret); | |
168 | ret = NULL; | |
169 | } | |
170 | ||
171 | return ret; | |
172 | } | |
173 | ||
174 | static bool strfilter_node__compare(struct strfilter_node *self, | |
175 | const char *str) | |
176 | { | |
177 | if (!self || !self->p) | |
178 | return false; | |
179 | ||
180 | switch (*self->p) { | |
181 | case '|': /* OR */ | |
182 | return strfilter_node__compare(self->l, str) || | |
183 | strfilter_node__compare(self->r, str); | |
184 | case '&': /* AND */ | |
185 | return strfilter_node__compare(self->l, str) && | |
186 | strfilter_node__compare(self->r, str); | |
187 | case '!': /* NOT */ | |
188 | return !strfilter_node__compare(self->r, str); | |
189 | default: | |
190 | return strglobmatch(str, self->p); | |
191 | } | |
192 | } | |
193 | ||
194 | /* Return true if STR matches the filter rules */ | |
195 | bool strfilter__compare(struct strfilter *self, const char *str) | |
196 | { | |
197 | if (!self) | |
198 | return false; | |
199 | return strfilter_node__compare(self->root, str); | |
200 | } |