1#include "util.h" 2#include "string.h" 3#include "strfilter.h" 4 5/* Operators */ 6static const char *OP_and = "&"; /* Logical AND */ 7static const char *OP_or = "|"; /* Logical OR */ 8static 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 13static 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 24void strfilter__delete(struct strfilter *self) 25{ 26 if (self) { 27 strfilter_node__delete(self->root); 28 free(self); 29 } 30} 31 32static 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 */ 47retry: 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 } 56end: 57 *e = p; 58 return s; 59} 60 61static 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 76static 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; 143nomem: 144 s = NULL; 145error: 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 */ 155struct 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 173static 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 */ 194bool 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