Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 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 | |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 13 | static void strfilter_node__delete(struct strfilter_node *node) |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 14 | { |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 15 | if (node) { |
| 16 | if (node->p && !is_operator(*node->p)) |
Arnaldo Carvalho de Melo | 74cf249 | 2013-12-27 16:55:14 -0300 | [diff] [blame] | 17 | zfree((char **)&node->p); |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 18 | strfilter_node__delete(node->l); |
| 19 | strfilter_node__delete(node->r); |
| 20 | free(node); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 21 | } |
| 22 | } |
| 23 | |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 24 | void strfilter__delete(struct strfilter *filter) |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 25 | { |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 26 | if (filter) { |
| 27 | strfilter_node__delete(filter->root); |
| 28 | free(filter); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 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 | { |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 65 | struct strfilter_node *node = zalloc(sizeof(*node)); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 66 | |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 67 | if (node) { |
| 68 | node->p = op; |
| 69 | node->l = l; |
| 70 | node->r = r; |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 71 | } |
| 72 | |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 73 | return node; |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 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 | { |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 157 | struct strfilter *filter = zalloc(sizeof(*filter)); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 158 | const char *ep = NULL; |
| 159 | |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 160 | if (filter) |
| 161 | filter->root = strfilter_node__new(rules, &ep); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 162 | |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 163 | if (!filter || !filter->root || *ep != '\0') { |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 164 | if (err) |
| 165 | *err = ep; |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 166 | strfilter__delete(filter); |
| 167 | filter = NULL; |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 168 | } |
| 169 | |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 170 | return filter; |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 171 | } |
| 172 | |
Masami Hiramatsu | 4e60a2c | 2015-04-24 18:47:44 +0900 | [diff] [blame] | 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 | |
| 202 | int strfilter__or(struct strfilter *filter, const char *rules, const char **err) |
| 203 | { |
| 204 | return strfilter__append(filter, true, rules, err); |
| 205 | } |
| 206 | |
| 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 | |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 213 | static bool strfilter_node__compare(struct strfilter_node *node, |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 214 | const char *str) |
| 215 | { |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 216 | if (!node || !node->p) |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 217 | return false; |
| 218 | |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 219 | switch (*node->p) { |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 220 | case '|': /* OR */ |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 221 | return strfilter_node__compare(node->l, str) || |
| 222 | strfilter_node__compare(node->r, str); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 223 | case '&': /* AND */ |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 224 | return strfilter_node__compare(node->l, str) && |
| 225 | strfilter_node__compare(node->r, str); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 226 | case '!': /* NOT */ |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 227 | return !strfilter_node__compare(node->r, str); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 228 | default: |
Arnaldo Carvalho de Melo | c824c43 | 2013-10-22 19:01:31 -0300 | [diff] [blame] | 229 | return strglobmatch(str, node->p); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 230 | } |
| 231 | } |
| 232 | |
| 233 | /* Return true if STR matches the filter rules */ |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 234 | bool strfilter__compare(struct strfilter *filter, const char *str) |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 235 | { |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 236 | if (!filter) |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 237 | return false; |
Arnaldo Carvalho de Melo | 316c713 | 2013-11-05 15:32:36 -0300 | [diff] [blame] | 238 | return strfilter_node__compare(filter->root, str); |
Masami Hiramatsu | 68baa43 | 2011-01-20 23:15:30 +0900 | [diff] [blame] | 239 | } |
Masami Hiramatsu | 3f51972 | 2015-04-24 18:47:46 +0900 | [diff] [blame] | 240 | |
| 241 | static int strfilter_node__sprint(struct strfilter_node *node, char *buf); |
| 242 | |
| 243 | /* sprint node in parenthesis if needed */ |
| 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 | |
| 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 | 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 | |
| 292 | char *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 | } |