expr.c

   1 /*
   2  * Copyright 2005 Timo Hirvonen
   3  */
   4
   5 #include <expr.h>
   6 #include <glob.h>
   7 #include <uchar.h>
   8 #include <track_info.h>
   9 #include <comment.h>
  10 #include <xmalloc.h>
  11 #include <utils.h>
  12 #include <debug.h>
  13 #include <list.h>
  14
  15 #include <stdlib.h>
  16 #include <ctype.h>
  17 #include <stdarg.h>
  18 #include <limits.h>
  19
  20 /* #define DEBUG_EXPR */
  21
  22 enum token_type {
  23         /* speacial chars */
  24         TOK_NOT,
  25         TOK_LT,
  26         TOK_GT,
  27
  28 #define NR_COMBINATIONS TOK_EQ
  29
  30         /* speacial chars */
  31         TOK_EQ,
  32         TOK_AND,
  33         TOK_OR,
  34         TOK_LPAREN,
  35         TOK_RPAREN,
  36
  37 #define NR_SPECIALS TOK_NE
  38 #define COMB_BASE TOK_NE
  39
  40         /* same as the first 3 + '=' */
  41         TOK_NE,
  42         TOK_LE,
  43         TOK_GE,
  44
  45         TOK_KEY,
  46         TOK_INT_OR_KEY,
  47         TOK_STR
  48 };
  49 #define NR_TOKS (TOK_STR + 1)
  50
  51 struct token {
  52         struct list_head node;
  53         enum token_type type;
  54         /* for TOK_KEY, TOK_INT_OR_KEY and TOK_STR */
  55         char str[0];
  56 };
  57
  58 /* same order as TOK_* */
  59 static const char specials[NR_SPECIALS] = "!<>=&|()";
  60
  61 static const int tok_to_op[NR_TOKS] = {
  62         -1, OP_LT, OP_GT, OP_EQ, -1, -1, -1, -1, OP_NE, OP_LE, OP_GE, -1, -1, -1
  63 };
  64
  65 static const char * const op_names[NR_OPS] = { "<", "<=", "=", ">=", ">", "!=" };
  66 static const char * const expr_names[NR_EXPRS] = {
  67         "&", "|", "!", "a string", "an integer", "a boolean"
  68 };
  69
  70 static char error_buf[64] = { 0, };
  71
  72 #ifdef DEBUG_EXPR
  73 #define CHECK_EXPR(e)                                                   \
  74 do {                                                                    \
  75         BUG_ON(e->type < 0);                                            \
  76         BUG_ON(e->type >= NR_EXPRS);                                    \
  77         switch (e->type) {                                              \
  78         case EXPR_AND:                                                  \
  79         case EXPR_OR:                                                   \
  80                 BUG_ON(e->left == NULL);                                \
  81                 BUG_ON(e->right == NULL);                               \
  82                 BUG_ON(e->key);                                         \
  83                 break;                                                  \
  84         case EXPR_NOT:                                                  \
  85                 BUG_ON(e->left == NULL);                                \
  86                 BUG_ON(e->right);                                       \
  87                 BUG_ON(e->key);                                         \
  88                 break;                                                  \
  89         case EXPR_STR:                                                  \
  90                 BUG_ON(e->left);                                        \
  91                 BUG_ON(e->right);                                       \
  92                 BUG_ON(e->key == NULL);                                 \
  93                 BUG_ON(e->estr.op != SOP_EQ && e->estr.op != SOP_NE);   \
  94                 break;                                                  \
  95         case EXPR_INT:                                                  \
  96                 BUG_ON(e->left);                                        \
  97                 BUG_ON(e->right);                                       \
  98                 BUG_ON(e->key == NULL);                                 \
  99                 BUG_ON(e->eint.op < 0);                                 \
 100                 BUG_ON(e->eint.op >= NR_OPS);                           \
 101                 break;                                                  \
 102         case EXPR_BOOL:                                                 \
 103                 BUG_ON(e->left);                                        \
 104                 BUG_ON(e->right);                                       \
 105                 BUG_ON(e->key == NULL);                                 \
 106                 break;                                                  \
 107         }                                                               \
 108 } while (0)
 109 #else
 110 #define CHECK_EXPR(e) do { } while (0)
 111 #endif
 112
 113 static void set_error(const char *format, ...)
 114 {
 115         va_list ap;
 116
 117         va_start(ap, format);
 118         vsnprintf(error_buf, sizeof(error_buf), format, ap);
 119         va_end(ap);
 120 }
 121
 122 static struct token *get_str(const char *str, int *idxp)
 123 {
 124         struct token *tok;
 125         int s = *idxp + 1;
 126         int e = s;
 127
 128         /* can't remove all backslashes here => don't remove any */
 129         while (str[e] != '"') {
 130                 int c = str[e];
 131
 132                 if (c == 0)
 133                         goto err;
 134                 if (c == '\\') {
 135                         if (str[e + 1] == 0)
 136                                 goto err;
 137                         e += 2;
 138                         continue;
 139                 }
 140                 e++;
 141         }
 142
 143         tok = xmalloc(sizeof(struct token) + e - s + 1);
 144         memcpy(tok->str, str + s, e - s);
 145         tok->str[e - s] = 0;
 146         tok->type = TOK_STR;
 147         *idxp = e + 1;
 148         return tok;
 149 err:
 150         set_error("end of expression at middle of string");
 151         return NULL;
 152 }
 153
 154 static struct token *get_int_or_key(const char *str, int *idxp)
 155 {
 156         int s = *idxp;
 157         int e = s;
 158         int digits_only = 1;
 159         struct token *tok;
 160
 161         if (str[e] == '-')
 162                 e++;
 163         while (str[e]) {
 164                 int i, c = str[e];
 165
 166                 for (i = 0; i < NR_SPECIALS; i++) {
 167                         if (c == specials[i])
 168                                 goto out;
 169                 }
 170                 if (c < '0' || c > '9') {
 171                         digits_only = 0;
 172                         if (!isalpha(c) && c != '_' && c != '-') {
 173                                 set_error("unexpected '%c'", c);
 174                                 return NULL;
 175                         }
 176                 }
 177                 e++;
 178         }
 179 out:
 180         tok = xmalloc(sizeof(struct token) + e - s + 1);
 181         memcpy(tok->str, str + s, e - s);
 182         tok->str[e - s] = 0;
 183         tok->type = TOK_KEY;
 184         if (digits_only)
 185                 tok->type = TOK_INT_OR_KEY;
 186         *idxp = e;
 187         return tok;
 188 }
 189
 190 static struct token *get_token(const char *str, int *idxp)
 191 {
 192         int idx = *idxp;
 193         int c, i;
 194
 195         c = str[idx];
 196         for (i = 0; i < NR_SPECIALS; i++) {
 197                 struct token *tok;
 198
 199                 if (c != specials[i])
 200                         continue;
 201
 202                 idx++;
 203                 tok = xnew(struct token, 1);
 204                 tok->type = i;
 205                 if (i < NR_COMBINATIONS && str[idx] == '=') {
 206                         tok->type = COMB_BASE + i;
 207                         idx++;
 208                 }
 209                 *idxp = idx;
 210                 return tok;
 211         }
 212         if (c == '"')
 213                 return get_str(str, idxp);
 214         return get_int_or_key(str, idxp);
 215 }
 216
 217 static void free_tokens(struct list_head *head)
 218 {
 219         struct list_head *item = head->next;
 220
 221         while (item != head) {
 222                 struct list_head *next = item->next;
 223                 struct token *tok = container_of(item, struct token, node);
 224
 225                 free(tok);
 226                 item = next;
 227         }
 228 }
 229
 230 static int tokenize(struct list_head *head, const char *str)
 231 {
 232         struct token *tok;
 233         int idx = 0;
 234
 235         while (1) {
 236                 if (str[idx] == 0)
 237                         break;
 238                 tok = get_token(str, &idx);
 239                 if (tok == NULL) {
 240                         free_tokens(head);
 241                         return -1;
 242                 }
 243                 list_add_tail(&tok->node, head);
 244         }
 245         return 0;
 246 }
 247
 248 static struct expr *expr_new(int type)
 249 {
 250         struct expr *new = xnew(struct expr, 1);
 251
 252         new->type = type;
 253         new->key = NULL;
 254         new->parent = NULL;
 255         new->left = NULL;
 256         new->right = NULL;
 257         return new;
 258 }
 259
 260 static int parse(struct expr **rootp, struct list_head *head, struct list_head **itemp, int level);
 261
 262 static int parse_one(struct expr **exprp, struct list_head *head, struct list_head **itemp)
 263 {
 264         struct list_head *item = *itemp;
 265         struct token *tok;
 266         enum token_type type;
 267         int rc;
 268
 269         *exprp = NULL;
 270         if (item == head) {
 271                 set_error("expression expected");
 272                 return -1;
 273         }
 274
 275         tok = container_of(item, struct token, node);
 276         type = tok->type;
 277         if (type == TOK_NOT) {
 278                 struct expr *new, *tmp;
 279
 280                 *itemp = item->next;
 281                 rc = parse_one(&tmp, head, itemp);
 282                 if (rc)
 283                         return rc;
 284                 new = expr_new(EXPR_NOT);
 285                 new->left = tmp;
 286                 *exprp = new;
 287                 return 0;
 288         } else if (type == TOK_LPAREN) {
 289                 *itemp = item->next;
 290                 *exprp = NULL;
 291                 return parse(exprp, head, itemp, 1);
 292                 /* ')' already eaten */
 293         } else if (type == TOK_KEY || type == TOK_INT_OR_KEY) {
 294                 const char *key = tok->str;
 295                 struct expr *new;
 296                 int op = -1;
 297
 298                 item = item->next;
 299                 if (item != head) {
 300                         tok = container_of(item, struct token, node);
 301                         op = tok_to_op[tok->type];
 302                 }
 303                 if (item == head || op == -1) {
 304                         /* must be a bool */
 305                         new = expr_new(EXPR_BOOL);
 306                         new->key = xstrdup(key);
 307                         *itemp = item;
 308                         *exprp = new;
 309                         return 0;
 310                 }
 311                 item = item->next;
 312                 if (item == head) {
 313                         set_error("right side of expression expected");
 314                         return -1;
 315                 }
 316                 tok = container_of(item, struct token, node);
 317                 type = tok->type;
 318                 *itemp = item->next;
 319                 if (type == TOK_STR) {
 320                         if (op != OP_EQ && op != OP_NE) {
 321                                 set_error("invalid string operator '%s'", op_names[op]);
 322                                 return -1;
 323                         }
 324                         new = expr_new(EXPR_STR);
 325                         new->key = xstrdup(key);
 326                         glob_compile(&new->estr.glob_head, tok->str);
 327                         new->estr.op = op;
 328                         *exprp = new;
 329                         return 0;
 330                 } else if (type == TOK_INT_OR_KEY) {
 331                         long int val = 0;
 332
 333                         if (str_to_int(tok->str, &val)) {
 334                         }
 335                         new = expr_new(EXPR_INT);
 336                         new->key = xstrdup(key);
 337                         new->eint.val = val;
 338                         new->eint.op = op;
 339                         *exprp = new;
 340                         return 0;
 341                 }
 342                 if (op == OP_EQ || op == OP_NE) {
 343                         set_error("integer or string expected");
 344                 } else {
 345                         set_error("integer expected");
 346                 }
 347                 return -1;
 348         }
 349         set_error("key expected");
 350         return -1;
 351 }
 352
 353 static void add(struct expr **rootp, struct expr *expr)
 354 {
 355         struct expr *tmp, *root = *rootp;
 356
 357         BUG_ON(expr == NULL);
 358         if (root == NULL) {
 359                 *rootp = expr;
 360                 return;
 361         }
 362
 363         tmp = root;
 364         while (tmp->right)
 365                 tmp = tmp->right;
 366         if (tmp->type <= EXPR_OR) {
 367                 /* tmp is binary, tree is incomplete */
 368                 tmp->right = expr;
 369                 expr->parent = tmp;
 370                 return;
 371         }
 372
 373         /* tmp is unary, tree is complete
 374          * expr must be a binary operator */
 375         BUG_ON(expr->type > EXPR_OR);
 376
 377         expr->left = root;
 378         root->parent = expr;
 379         *rootp = expr;
 380 }
 381
 382 static int parse(struct expr **rootp, struct list_head *head, struct list_head **itemp, int level)
 383 {
 384         struct list_head *item = *itemp;
 385
 386         while (1) {
 387                 struct token *tok;
 388                 struct expr *expr;
 389                 int rc, type;
 390
 391                 rc = parse_one(&expr, head, &item);
 392                 if (rc)
 393                         return rc;
 394                 add(rootp, expr);
 395                 if (item == head) {
 396                         if (level > 0) {
 397                                 set_error("')' expected");
 398                                 return -1;
 399                         }
 400                         *itemp = item;
 401                         return 0;
 402                 }
 403                 tok = container_of(item, struct token, node);
 404                 if (tok->type == TOK_RPAREN) {
 405                         if (level == 0) {
 406                                 set_error("unexpected ')'");
 407                                 return -1;
 408                         }
 409                         *itemp = item->next;
 410                         return 0;
 411                 }
 412
 413                 if (tok->type == TOK_AND) {
 414                         type = EXPR_AND;
 415                 } else if (tok->type == TOK_OR) {
 416                         type = EXPR_OR;
 417                 } else {
 418                         set_error("'&' or '|' expected");
 419                         return -1;
 420                 }
 421                 expr = expr_new(type);
 422                 add(rootp, expr);
 423                 item = item->next;
 424         }
 425 }
 426
 427 struct expr *expr_parse(const char *str)
 428 {
 429         LIST_HEAD(head);
 430         struct expr *root = NULL;
 431         struct list_head *item;
 432         int i;
 433
 434         for (i = 0; str[i]; i++) {
 435                 unsigned char c = str[i];
 436                 if (c < 0x20) {
 437                         set_error("filter contains control characters");
 438                         return NULL;
 439                 }
 440         }
 441         if (!u_is_valid(str)) {
 442                 set_error("invalid UTF-8");
 443                 return NULL;
 444         }
 445
 446         if (tokenize(&head, str))
 447                 return NULL;
 448
 449         item = head.next;
 450         if (parse(&root, &head, &item, 0))
 451                 root = NULL;
 452         free_tokens(&head);
 453         return root;
 454 }
 455
 456 static const struct {
 457         const char *key;
 458         enum expr_type type;
 459 } builtin[] = {
 460         { "album",      EXPR_STR },
 461         { "artist",     EXPR_STR },
 462         { "date",       EXPR_INT },
 463         { "discnumber", EXPR_INT },
 464         { "duration",   EXPR_INT },
 465         { "filename",   EXPR_STR },
 466         { "genre",      EXPR_STR },
 467         { "stream",     EXPR_BOOL },
 468         { "tag",        EXPR_BOOL },
 469         { "title",      EXPR_STR },
 470         { "tracknumber",EXPR_INT },
 471         { NULL,         -1 },
 472 };
 473
 474 int expr_check_leaves(struct expr **exprp, const char *(*get_filter)(const char *name))
 475 {
 476         struct expr *expr = *exprp;
 477         struct expr *e;
 478         const char *filter;
 479         int i, rc;
 480
 481         if (expr->left) {
 482                 if (expr_check_leaves(&expr->left, get_filter))
 483                         return -1;
 484                 if (expr->right)
 485                         return expr_check_leaves(&expr->right, get_filter);
 486                 return 0;
 487         }
 488
 489         for (i = 0; builtin[i].key; i++) {
 490                 int cmp = strcmp(expr->key, builtin[i].key);
 491
 492                 if (cmp > 0)
 493                         continue;
 494                 if (cmp < 0)
 495                         break;
 496
 497                 if (builtin[i].type != expr->type) {
 498                         /* type mismatch */
 499                         set_error("%s is %s", builtin[i].key, expr_names[builtin[i].type]);
 500                         return -1;
 501                 }
 502                 return 0;
 503         }
 504         if (expr->type != EXPR_BOOL) {
 505                 /* unknown key */
 506                 set_error("unkown key %s", expr->key);
 507                 return -1;
 508         }
 509
 510         /* user defined filter */
 511         filter = get_filter(expr->key);
 512         if (filter == NULL) {
 513                 set_error("unkown filter or boolean %s", expr->key);
 514                 return -1;
 515         }
 516         e = expr_parse(filter);
 517         if (e == NULL) {
 518                 return -1;
 519         }
 520         rc = expr_check_leaves(&e, get_filter);
 521         if (rc) {
 522                 expr_free(e);
 523                 return rc;
 524         }
 525
 526         /* replace */
 527         e->parent = expr->parent;
 528         expr_free(expr);
 529
 530         /* this sets parents left pointer */
 531         *exprp = e;
 532         return 0;
 533 }
 534
 535 int expr_eval(struct expr *expr, struct track_info *ti)
 536 {
 537         enum expr_type type = expr->type;
 538         const char *key;
 539
 540         CHECK_EXPR(expr);
 541         if (expr->left) {
 542                 int left = expr_eval(expr->left, ti);
 543
 544                 if (type == EXPR_AND)
 545                         return left && expr_eval(expr->right, ti);
 546                 if (type == EXPR_OR)
 547                         return left || expr_eval(expr->right, ti);
 548                 /* EXPR_NOT */
 549                 return !left;
 550         }
 551
 552         key = expr->key;
 553         if (type == EXPR_STR) {
 554                 const char *val;
 555                 int res;
 556
 557                 if (strcmp(key, "filename") == 0) {
 558                         val = ti->filename;
 559                 } else {
 560                         val = comments_get_val(ti->comments, key);
 561                         if (val == NULL) {
 562                                 /* NULL="something" is false */
 563                                 if (expr->estr.op == SOP_EQ)
 564                                         return 0;
 565                                 /* NULL!="something" is true */
 566                                 return 1;
 567                         }
 568                 }
 569                 res = glob_match(&expr->estr.glob_head, val);
 570                 if (expr->estr.op == SOP_EQ)
 571                         return res;
 572                 return !res;
 573         } else if (type == EXPR_INT) {
 574                 int val, res;
 575
 576                 if (strcmp(key, "duration") == 0) {
 577                         val = ti->duration;
 578                         /* duration of a stream is infinite (well, almost) */
 579                         if (is_url(ti->filename))
 580                                 val = INT_MAX;
 581                 } else {
 582                         val = comments_get_int(ti->comments, key);
 583                 }
 584                 if (expr->eint.val == -1) {
 585                         /* -1 is "not set"
 586                          * doesn't make sense to do 123 < "not set"
 587                          * but it makes sense to do date=-1 (date is not set)
 588                          */
 589                         if (expr->eint.op == IOP_EQ)
 590                                 return val == -1;
 591                         if (expr->eint.op == IOP_NE)
 592                                 return val != -1;
 593                 }
 594                 if (val == -1) {
 595                         /* tag not set, can't compare */
 596                         return 0;
 597                 }
 598                 res = val - expr->eint.val;
 599                 switch (expr->eint.op) {
 600                 case IOP_LT:
 601                         return res < 0;
 602                 case IOP_LE:
 603                         return res <= 0;
 604                 case IOP_EQ:
 605                         return res == 0;
 606                 case IOP_GE:
 607                         return res >= 0;
 608                 case IOP_GT:
 609                         return res > 0;
 610                 case IOP_NE:
 611                         return res != 0;
 612                 }
 613         }
 614         if (strcmp(key, "stream") == 0)
 615                 return is_url(ti->filename);
 616         return track_info_has_tag(ti);
 617 }
 618
 619 void expr_free(struct expr *expr)
 620 {
 621         if (expr->left) {
 622                 expr_free(expr->left);
 623                 if (expr->right)
 624                         expr_free(expr->right);
 625         }
 626         free(expr->key);
 627         if (expr->type == EXPR_STR)
 628                 glob_free(&expr->estr.glob_head);
 629         free(expr);
 630 }
 631
 632 const char *expr_error(void)
 633 {
 634         return error_buf;
 635 }