1 #include "util.h" 2 #include "string2.h" 3 #include "strfilter.h" 4 5 #include <errno.h> 6 #include "sane_ctype.h" 7 8 /* Operators */ 9 static const char *OP_and = "&"; /* Logical AND */ 10 static const char *OP_or = "|"; /* Logical OR */ 11 static const char *OP_not = "!"; /* Logical NOT */ 12 13 #define is_operator(c) ((c) == '|' || (c) == '&' || (c) == '!') 14 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')') 15 16 static void strfilter_node__delete(struct strfilter_node *node) 17 { 18 if (node) { 19 if (node->p && !is_operator(*node->p)) 20 zfree((char **)&node->p); 21 strfilter_node__delete(node->l); 22 strfilter_node__delete(node->r); 23 free(node); 24 } 25 } 26 27 void strfilter__delete(struct strfilter *filter) 28 { 29 if (filter) { 30 strfilter_node__delete(filter->root); 31 free(filter); 32 } 33 } 34 35 static const char *get_token(const char *s, const char **e) 36 { 37 const char *p; 38 39 while (isspace(*s)) /* Skip spaces */ 40 s++; 41 42 if (*s == '\0') { 43 p = s; 44 goto end; 45 } 46 47 p = s + 1; 48 if (!is_separator(*s)) { 49 /* End search */ 50 retry: 51 while (*p && !is_separator(*p) && !isspace(*p)) 52 p++; 53 /* Escape and special case: '!' is also used in glob pattern */ 54 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) { 55 p++; 56 goto retry; 57 } 58 } 59 end: 60 *e = p; 61 return s; 62 } 63 64 static struct strfilter_node *strfilter_node__alloc(const char *op, 65 struct strfilter_node *l, 66 struct strfilter_node *r) 67 { 68 struct strfilter_node *node = zalloc(sizeof(*node)); 69 70 if (node) { 71 node->p = op; 72 node->l = l; 73 node->r = r; 74 } 75 76 return node; 77 } 78 79 static struct strfilter_node *strfilter_node__new(const char *s, 80 const char **ep) 81 { 82 struct strfilter_node root, *cur, *last_op; 83 const char *e; 84 85 if (!s) 86 return NULL; 87 88 memset(&root, 0, sizeof(root)); 89 last_op = cur = &root; 90 91 s = get_token(s, &e); 92 while (*s != '\0' && *s != ')') { 93 switch (*s) { 94 case '&': /* Exchg last OP->r with AND */ 95 if (!cur->r || !last_op->r) 96 goto error; 97 cur = strfilter_node__alloc(OP_and, last_op->r, NULL); 98 if (!cur) 99 goto nomem; 100 last_op->r = cur; 101 last_op = cur; 102 break; 103 case '|': /* Exchg the root with OR */ 104 if (!cur->r || !root.r) 105 goto error; 106 cur = strfilter_node__alloc(OP_or, root.r, NULL); 107 if (!cur) 108 goto nomem; 109 root.r = cur; 110 last_op = cur; 111 break; 112 case '!': /* Add NOT as a leaf node */ 113 if (cur->r) 114 goto error; 115 cur->r = strfilter_node__alloc(OP_not, NULL, NULL); 116 if (!cur->r) 117 goto nomem; 118 cur = cur->r; 119 break; 120 case '(': /* Recursively parses inside the parenthesis */ 121 if (cur->r) 122 goto error; 123 cur->r = strfilter_node__new(s + 1, &s); 124 if (!s) 125 goto nomem; 126 if (!cur->r || *s != ')') 127 goto error; 128 e = s + 1; 129 break; 130 default: 131 if (cur->r) 132 goto error; 133 cur->r = strfilter_node__alloc(NULL, NULL, NULL); 134 if (!cur->r) 135 goto nomem; 136 cur->r->p = strndup(s, e - s); 137 if (!cur->r->p) 138 goto nomem; 139 } 140 s = get_token(e, &e); 141 } 142 if (!cur->r) 143 goto error; 144 *ep = s; 145 return root.r; 146 nomem: 147 s = NULL; 148 error: 149 *ep = s; 150 strfilter_node__delete(root.r); 151 return NULL; 152 } 153 154 /* 155 * Parse filter rule and return new strfilter. 156 * Return NULL if fail, and *ep == NULL if memory allocation failed. 157 */ 158 struct strfilter *strfilter__new(const char *rules, const char **err) 159 { 160 struct strfilter *filter = zalloc(sizeof(*filter)); 161 const char *ep = NULL; 162 163 if (filter) 164 filter->root = strfilter_node__new(rules, &ep); 165 166 if (!filter || !filter->root || *ep != '\0') { 167 if (err) 168 *err = ep; 169 strfilter__delete(filter); 170 filter = NULL; 171 } 172 173 return filter; 174 } 175 176 static int strfilter__append(struct strfilter *filter, bool _or, 177 const char *rules, const char **err) 178 { 179 struct strfilter_node *right, *root; 180 const char *ep = NULL; 181 182 if (!filter || !rules) 183 return -EINVAL; 184 185 right = strfilter_node__new(rules, &ep); 186 if (!right || *ep != '\0') { 187 if (err) 188 *err = ep; 189 goto error; 190 } 191 root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right); 192 if (!root) { 193 ep = NULL; 194 goto error; 195 } 196 197 filter->root = root; 198 return 0; 199 200 error: 201 strfilter_node__delete(right); 202 return ep ? -EINVAL : -ENOMEM; 203 } 204 205 int strfilter__or(struct strfilter *filter, const char *rules, const char **err) 206 { 207 return strfilter__append(filter, true, rules, err); 208 } 209 210 int strfilter__and(struct strfilter *filter, const char *rules, 211 const char **err) 212 { 213 return strfilter__append(filter, false, rules, err); 214 } 215 216 static bool strfilter_node__compare(struct strfilter_node *node, 217 const char *str) 218 { 219 if (!node || !node->p) 220 return false; 221 222 switch (*node->p) { 223 case '|': /* OR */ 224 return strfilter_node__compare(node->l, str) || 225 strfilter_node__compare(node->r, str); 226 case '&': /* AND */ 227 return strfilter_node__compare(node->l, str) && 228 strfilter_node__compare(node->r, str); 229 case '!': /* NOT */ 230 return !strfilter_node__compare(node->r, str); 231 default: 232 return strglobmatch(str, node->p); 233 } 234 } 235 236 /* Return true if STR matches the filter rules */ 237 bool strfilter__compare(struct strfilter *filter, const char *str) 238 { 239 if (!filter) 240 return false; 241 return strfilter_node__compare(filter->root, str); 242 } 243 244 static int strfilter_node__sprint(struct strfilter_node *node, char *buf); 245 246 /* sprint node in parenthesis if needed */ 247 static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf) 248 { 249 int len; 250 int pt = node->r ? 2 : 0; /* don't need to check node->l */ 251 252 if (buf && pt) 253 *buf++ = '('; 254 len = strfilter_node__sprint(node, buf); 255 if (len < 0) 256 return len; 257 if (buf && pt) 258 *(buf + len) = ')'; 259 return len + pt; 260 } 261 262 static int strfilter_node__sprint(struct strfilter_node *node, char *buf) 263 { 264 int len = 0, rlen; 265 266 if (!node || !node->p) 267 return -EINVAL; 268 269 switch (*node->p) { 270 case '|': 271 case '&': 272 len = strfilter_node__sprint_pt(node->l, buf); 273 if (len < 0) 274 return len; 275 __fallthrough; 276 case '!': 277 if (buf) { 278 *(buf + len++) = *node->p; 279 buf += len; 280 } else 281 len++; 282 rlen = strfilter_node__sprint_pt(node->r, buf); 283 if (rlen < 0) 284 return rlen; 285 len += rlen; 286 break; 287 default: 288 len = strlen(node->p); 289 if (buf) 290 strcpy(buf, node->p); 291 } 292 293 return len; 294 } 295 296 char *strfilter__string(struct strfilter *filter) 297 { 298 int len; 299 char *ret = NULL; 300 301 len = strfilter_node__sprint(filter->root, NULL); 302 if (len < 0) 303 return NULL; 304 305 ret = malloc(len + 1); 306 if (ret) 307 strfilter_node__sprint(filter->root, ret); 308 309 return ret; 310 } 311