tools/perf/util/strfilter.c

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