tools/perf/util/strfilter.c

   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 }