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 | |
| 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 | } |