LXR linux/tools/perf/util/strfilter.c

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