tools/perf/util/strfilter.c

   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 }