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