LXR linux/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 */
   9static const char *OP_and       = "&";  /* Logical AND */
  10static const char *OP_or        = "|";  /* Logical OR */
  11static 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
  16static 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
  27void strfilter__delete(struct strfilter *filter)
  28{
  29        if (filter) {
  30                strfilter_node__delete(filter->root);
  31                free(filter);
  32        }
  33}
  34
  35static 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 */
  50retry:
  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        }
  59end:
  60        *e = p;
  61        return s;
  62}
  63
  64static 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
  79static 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;
 146nomem:
 147        s = NULL;
 148error:
 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 */
 158struct 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
 176static 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
 200error:
 201        strfilter_node__delete(right);
 202        return ep ? -EINVAL : -ENOMEM;
 203}
 204
 205int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
 206{
 207        return strfilter__append(filter, true, rules, err);
 208}
 209
 210int strfilter__and(struct strfilter *filter, const char *rules,
 211                   const char **err)
 212{
 213        return strfilter__append(filter, false, rules, err);
 214}
 215
 216static 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 */
 237bool 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
 244static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
 245
 246/* sprint node in parenthesis if needed */
 247static 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
 262static 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
 296char *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}
 311