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