perf/util/strfilter.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include "string2.h"
0003 #include "strfilter.h"
0004
0005 #include <errno.h>
0006 #include <stdlib.h>
0007 #include <linux/ctype.h>
0008 #include <linux/string.h>
0009 #include <linux/zalloc.h>
0010
0011 /* Operators */
0012 static const char *OP_and   = "&";  /* Logical AND */
0013 static const char *OP_or    = "|";  /* Logical OR */
0014 static const char *OP_not   = "!";  /* Logical NOT */
0015
0016 #define is_operator(c)  ((c) == '|' || (c) == '&' || (c) == '!')
0017 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
0018
0019 static void strfilter_node__delete(struct strfilter_node *node)
0020 {
0021     if (node) {
0022         if (node->p && !is_operator(*node->p))
0023             zfree((char **)&node->p);
0024         strfilter_node__delete(node->l);
0025         strfilter_node__delete(node->r);
0026         free(node);
0027     }
0028 }
0029
0030 void strfilter__delete(struct strfilter *filter)
0031 {
0032     if (filter) {
0033         strfilter_node__delete(filter->root);
0034         free(filter);
0035     }
0036 }
0037
0038 static const char *get_token(const char *s, const char **e)
0039 {
0040     const char *p;
0041
0042     s = skip_spaces(s);
0043
0044     if (*s == '\0') {
0045         p = s;
0046         goto end;
0047     }
0048
0049     p = s + 1;
0050     if (!is_separator(*s)) {
0051         /* End search */
0052 retry:
0053         while (*p && !is_separator(*p) && !isspace(*p))
0054             p++;
0055         /* Escape and special case: '!' is also used in glob pattern */
0056         if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
0057             p++;
0058             goto retry;
0059         }
0060     }
0061 end:
0062     *e = p;
0063     return s;
0064 }
0065
0066 static struct strfilter_node *strfilter_node__alloc(const char *op,
0067                             struct strfilter_node *l,
0068                             struct strfilter_node *r)
0069 {
0070     struct strfilter_node *node = zalloc(sizeof(*node));
0071
0072     if (node) {
0073         node->p = op;
0074         node->l = l;
0075         node->r = r;
0076     }
0077
0078     return node;
0079 }
0080
0081 static struct strfilter_node *strfilter_node__new(const char *s,
0082                           const char **ep)
0083 {
0084     struct strfilter_node root, *cur, *last_op;
0085     const char *e;
0086
0087     if (!s)
0088         return NULL;
0089
0090     memset(&root, 0, sizeof(root));
0091     last_op = cur = &root;
0092
0093     s = get_token(s, &e);
0094     while (*s != '\0' && *s != ')') {
0095         switch (*s) {
0096         case '&':   /* Exchg last OP->r with AND */
0097             if (!cur->r || !last_op->r)
0098                 goto error;
0099             cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
0100             if (!cur)
0101                 goto nomem;
0102             last_op->r = cur;
0103             last_op = cur;
0104             break;
0105         case '|':   /* Exchg the root with OR */
0106             if (!cur->r || !root.r)
0107                 goto error;
0108             cur = strfilter_node__alloc(OP_or, root.r, NULL);
0109             if (!cur)
0110                 goto nomem;
0111             root.r = cur;
0112             last_op = cur;
0113             break;
0114         case '!':   /* Add NOT as a leaf node */
0115             if (cur->r)
0116                 goto error;
0117             cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
0118             if (!cur->r)
0119                 goto nomem;
0120             cur = cur->r;
0121             break;
0122         case '(':   /* Recursively parses inside the parenthesis */
0123             if (cur->r)
0124                 goto error;
0125             cur->r = strfilter_node__new(s + 1, &s);
0126             if (!s)
0127                 goto nomem;
0128             if (!cur->r || *s != ')')
0129                 goto error;
0130             e = s + 1;
0131             break;
0132         default:
0133             if (cur->r)
0134                 goto error;
0135             cur->r = strfilter_node__alloc(NULL, NULL, NULL);
0136             if (!cur->r)
0137                 goto nomem;
0138             cur->r->p = strndup(s, e - s);
0139             if (!cur->r->p)
0140                 goto nomem;
0141         }
0142         s = get_token(e, &e);
0143     }
0144     if (!cur->r)
0145         goto error;
0146     *ep = s;
0147     return root.r;
0148 nomem:
0149     s = NULL;
0150 error:
0151     *ep = s;
0152     strfilter_node__delete(root.r);
0153     return NULL;
0154 }
0155
0156 /*
0157  * Parse filter rule and return new strfilter.
0158  * Return NULL if fail, and *ep == NULL if memory allocation failed.
0159  */
0160 struct strfilter *strfilter__new(const char *rules, const char **err)
0161 {
0162     struct strfilter *filter = zalloc(sizeof(*filter));
0163     const char *ep = NULL;
0164
0165     if (filter)
0166         filter->root = strfilter_node__new(rules, &ep);
0167
0168     if (!filter || !filter->root || *ep != '\0') {
0169         if (err)
0170             *err = ep;
0171         strfilter__delete(filter);
0172         filter = NULL;
0173     }
0174
0175     return filter;
0176 }
0177
0178 static int strfilter__append(struct strfilter *filter, bool _or,
0179                  const char *rules, const char **err)
0180 {
0181     struct strfilter_node *right, *root;
0182     const char *ep = NULL;
0183
0184     if (!filter || !rules)
0185         return -EINVAL;
0186
0187     right = strfilter_node__new(rules, &ep);
0188     if (!right || *ep != '\0') {
0189         if (err)
0190             *err = ep;
0191         goto error;
0192     }
0193     root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
0194     if (!root) {
0195         ep = NULL;
0196         goto error;
0197     }
0198
0199     filter->root = root;
0200     return 0;
0201
0202 error:
0203     strfilter_node__delete(right);
0204     return ep ? -EINVAL : -ENOMEM;
0205 }
0206
0207 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
0208 {
0209     return strfilter__append(filter, true, rules, err);
0210 }
0211
0212 int strfilter__and(struct strfilter *filter, const char *rules,
0213            const char **err)
0214 {
0215     return strfilter__append(filter, false, rules, err);
0216 }
0217
0218 static bool strfilter_node__compare(struct strfilter_node *node,
0219                     const char *str)
0220 {
0221     if (!node || !node->p)
0222         return false;
0223
0224     switch (*node->p) {
0225     case '|':   /* OR */
0226         return strfilter_node__compare(node->l, str) ||
0227             strfilter_node__compare(node->r, str);
0228     case '&':   /* AND */
0229         return strfilter_node__compare(node->l, str) &&
0230             strfilter_node__compare(node->r, str);
0231     case '!':   /* NOT */
0232         return !strfilter_node__compare(node->r, str);
0233     default:
0234         return strglobmatch(str, node->p);
0235     }
0236 }
0237
0238 /* Return true if STR matches the filter rules */
0239 bool strfilter__compare(struct strfilter *filter, const char *str)
0240 {
0241     if (!filter)
0242         return false;
0243     return strfilter_node__compare(filter->root, str);
0244 }
0245
0246 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
0247
0248 /* sprint node in parenthesis if needed */
0249 static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
0250 {
0251     int len;
0252     int pt = node->r ? 2 : 0;   /* don't need to check node->l */
0253
0254     if (buf && pt)
0255         *buf++ = '(';
0256     len = strfilter_node__sprint(node, buf);
0257     if (len < 0)
0258         return len;
0259     if (buf && pt)
0260         *(buf + len) = ')';
0261     return len + pt;
0262 }
0263
0264 static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
0265 {
0266     int len = 0, rlen;
0267
0268     if (!node || !node->p)
0269         return -EINVAL;
0270
0271     switch (*node->p) {
0272     case '|':
0273     case '&':
0274         len = strfilter_node__sprint_pt(node->l, buf);
0275         if (len < 0)
0276             return len;
0277         __fallthrough;
0278     case '!':
0279         if (buf) {
0280             *(buf + len++) = *node->p;
0281             buf += len;
0282         } else
0283             len++;
0284         rlen = strfilter_node__sprint_pt(node->r, buf);
0285         if (rlen < 0)
0286             return rlen;
0287         len += rlen;
0288         break;
0289     default:
0290         len = strlen(node->p);
0291         if (buf)
0292             strcpy(buf, node->p);
0293     }
0294
0295     return len;
0296 }
0297
0298 char *strfilter__string(struct strfilter *filter)
0299 {
0300     int len;
0301     char *ret = NULL;
0302
0303     len = strfilter_node__sprint(filter->root, NULL);
0304     if (len < 0)
0305         return NULL;
0306
0307     ret = malloc(len + 1);
0308     if (ret)
0309         strfilter_node__sprint(filter->root, ret);
0310
0311     return ret;
0312 }