LXR linux/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 */
  10static const char *OP_and       = "&";  /* Logical AND */
  11static const char *OP_or        = "|";  /* Logical OR */
  12static 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
  17static 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
  28void strfilter__delete(struct strfilter *filter)
  29{
  30        if (filter) {
  31                strfilter_node__delete(filter->root);
  32                free(filter);
  33        }
  34}
  35
  36static 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 */
  51retry:
  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        }
  60end:
  61        *e = p;
  62        return s;
  63}
  64
  65static 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
  80static 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;
 147nomem:
 148        s = NULL;
 149error:
 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 */
 159struct 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
 177static 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
 201error:
 202        strfilter_node__delete(right);
 203        return ep ? -EINVAL : -ENOMEM;
 204}
 205
 206int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
 207{
 208        return strfilter__append(filter, true, rules, err);
 209}
 210
 211int strfilter__and(struct strfilter *filter, const char *rules,
 212                   const char **err)
 213{
 214        return strfilter__append(filter, false, rules, err);
 215}
 216
 217static 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 */
 238bool 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
 245static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
 246
 247/* sprint node in parenthesis if needed */
 248static 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
 263static 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
 297char *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}
 312