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 *node) 14 { 15 if (node) { 16 if (node->p && !is_operator(*node->p)) 17 zfree((char **)&node->p); 18 strfilter_node__delete(node->l); 19 strfilter_node__delete(node->r); 20 free(node); 21 } 22 } 23 24 void strfilter__delete(struct strfilter *filter) 25 { 26 if (filter) { 27 strfilter_node__delete(filter->root); 28 free(filter); 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 *node = zalloc(sizeof(*node)); 66 67 if (node) { 68 node->p = op; 69 node->l = l; 70 node->r = r; 71 } 72 73 return node; 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 *filter = zalloc(sizeof(*filter)); 158 const char *ep = NULL; 159 160 if (filter) 161 filter->root = strfilter_node__new(rules, &ep); 162 163 if (!filter || !filter->root || *ep != '\0') { 164 if (err) 165 *err = ep; 166 strfilter__delete(filter); 167 filter = NULL; 168 } 169 170 return filter; 171 } 172 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 213 static bool strfilter_node__compare(struct strfilter_node *node, 214 const char *str) 215 { 216 if (!node || !node->p) 217 return false; 218 219 switch (*node->p) { 220 case '|': /* OR */ 221 return strfilter_node__compare(node->l, str) || 222 strfilter_node__compare(node->r, str); 223 case '&': /* AND */ 224 return strfilter_node__compare(node->l, str) && 225 strfilter_node__compare(node->r, str); 226 case '!': /* NOT */ 227 return !strfilter_node__compare(node->r, str); 228 default: 229 return strglobmatch(str, node->p); 230 } 231 } 232 233 /* Return true if STR matches the filter rules */ 234 bool strfilter__compare(struct strfilter *filter, const char *str) 235 { 236 if (!filter) 237 return false; 238 return strfilter_node__compare(filter->root, str); 239 } 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 } 307