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