Logo Search packages:      
Sourcecode: cmus version File versions  Download package

expr.c

/*
 * Copyright 2005 Timo Hirvonen
 */

#include <expr.h>
#include <glob.h>
#include <uchar.h>
#include <track_info.h>
#include <comment.h>
#include <xmalloc.h>
#include <utils.h>
#include <debug.h>
#include <list.h>

#include <stdlib.h>
#include <ctype.h>
#include <stdarg.h>
#include <limits.h>

enum token_type {
      /* speacial chars */
      TOK_NOT,
      TOK_LT,
      TOK_GT,

#define NR_COMBINATIONS TOK_EQ

      /* speacial chars */
      TOK_EQ,
      TOK_AND,
      TOK_OR,
      TOK_LPAREN,
      TOK_RPAREN,

#define NR_SPECIALS TOK_NE
#define COMB_BASE TOK_NE

      /* same as the first 3 + '=' */
      TOK_NE,
      TOK_LE,
      TOK_GE,

      TOK_KEY,
      TOK_INT_OR_KEY,
      TOK_STR
};
#define NR_TOKS (TOK_STR + 1)

struct token {
      struct list_head node;
      enum token_type type;
      /* for TOK_KEY, TOK_INT_OR_KEY and TOK_STR */
      char str[0];
};

/* same order as TOK_* */
static const char specials[NR_SPECIALS] = "!<>=&|()";

static const int tok_to_op[NR_TOKS] = {
      -1, OP_LT, OP_GT, OP_EQ, -1, -1, -1, -1, OP_NE, OP_LE, OP_GE, -1, -1, -1
};

static const char * const op_names[NR_OPS] = { "<", "<=", "=", ">=", ">", "!=" };
static const char * const expr_names[NR_EXPRS] = {
      "&", "|", "!", "a string", "an integer", "a boolean"
};

static char error_buf[64] = { 0, };


static void set_error(const char *format, ...)
{
      va_list ap;

      va_start(ap, format);
      vsnprintf(error_buf, sizeof(error_buf), format, ap);
      va_end(ap);
}

static struct token *get_str(const char *str, int *idxp)
{
      struct token *tok;
      int s = *idxp + 1;
      int e = s;

      /* can't remove all backslashes here => don't remove any */
      while (str[e] != '"') {
            int c = str[e];

            if (c == 0)
                  goto err;
            if (c == '\\') {
                  if (str[e + 1] == 0)
                        goto err;
                  e += 2;
                  continue;
            }
            e++;
      }

      tok = xmalloc(sizeof(struct token) + e - s + 1);
      memcpy(tok->str, str + s, e - s);
      tok->str[e - s] = 0;
      tok->type = TOK_STR;
      *idxp = e + 1;
      return tok;
err:
      set_error("end of expression at middle of string");
      return NULL;
}

static struct token *get_int_or_key(const char *str, int *idxp)
{
      int s = *idxp;
      int e = s;
      int digits_only = 1;
      struct token *tok;

      if (str[e] == '-')
            e++;
      while (str[e]) {
            int i, c = str[e];

            for (i = 0; i < NR_SPECIALS; i++) {
                  if (c == specials[i])
                        goto out;
            }
            if (c < '0' || c > '9') {
                  digits_only = 0;
                  if (!isalpha(c) && c != '_' && c != '-') {
                        set_error("unexpected '%c'", c);
                        return NULL;
                  }
            }
            e++;
      }
out:
      tok = xmalloc(sizeof(struct token) + e - s + 1);
      memcpy(tok->str, str + s, e - s);
      tok->str[e - s] = 0;
      tok->type = TOK_KEY;
      if (digits_only)
            tok->type = TOK_INT_OR_KEY;
      *idxp = e;
      return tok;
}

static struct token *get_token(const char *str, int *idxp)
{
      int idx = *idxp;
      int c, i;

      c = str[idx];
      for (i = 0; i < NR_SPECIALS; i++) {
            struct token *tok;

            if (c != specials[i])
                  continue;

            idx++;
            tok = xnew(struct token, 1);
            tok->type = i;
            if (i < NR_COMBINATIONS && str[idx] == '=') {
                  tok->type = COMB_BASE + i;
                  idx++;
            }
            *idxp = idx;
            return tok;
      }
      if (c == '"')
            return get_str(str, idxp);
      return get_int_or_key(str, idxp);
}

static void free_tokens(struct list_head *head)
{
      struct list_head *item = head->next;

      while (item != head) {
            struct list_head *next = item->next;
            struct token *tok = container_of(item, struct token, node);

            free(tok);
            item = next;
      }
}

static int tokenize(struct list_head *head, const char *str)
{
      struct token *tok;
      int idx = 0;

      while (1) {
            if (str[idx] == 0)
                  break;
            tok = get_token(str, &idx);
            if (tok == NULL) {
                  free_tokens(head);
                  return -1;
            }
            list_add_tail(&tok->node, head);
      }
      return 0;
}

static struct expr *expr_new(int type)
{
      struct expr *new = xnew(struct expr, 1);

      new->type = type;
      new->key = NULL;
      new->parent = NULL;
      new->left = NULL;
      new->right = NULL;
      return new;
}

static int parse(struct expr **rootp, struct list_head *head, struct list_head **itemp, int level);

static int parse_one(struct expr **exprp, struct list_head *head, struct list_head **itemp)
{
      struct list_head *item = *itemp;
      struct token *tok;
      enum token_type type;
      int rc;

      *exprp = NULL;
      if (item == head) {
            set_error("expression expected");
            return -1;
      }

      tok = container_of(item, struct token, node);
      type = tok->type;
      if (type == TOK_NOT) {
            struct expr *new, *tmp;

            *itemp = item->next;
            rc = parse_one(&tmp, head, itemp);
            if (rc)
                  return rc;
            new = expr_new(EXPR_NOT);
            new->left = tmp;
            *exprp = new;
            return 0;
      } else if (type == TOK_LPAREN) {
            *itemp = item->next;
            *exprp = NULL;
            return parse(exprp, head, itemp, 1);
            /* ')' already eaten */
      } else if (type == TOK_KEY || type == TOK_INT_OR_KEY) {
            const char *key = tok->str;
            struct expr *new;
            int op = -1;

            item = item->next;
            if (item != head) {
                  tok = container_of(item, struct token, node);
                  op = tok_to_op[tok->type];
            }
            if (item == head || op == -1) {
                  /* must be a bool */
                  new = expr_new(EXPR_BOOL);
                  new->key = xstrdup(key);
                  *itemp = item;
                  *exprp = new;
                  return 0;
            }
            item = item->next;
            if (item == head) {
                  set_error("right side of expression expected");
                  return -1;
            }
            tok = container_of(item, struct token, node);
            type = tok->type;
            *itemp = item->next;
            if (type == TOK_STR) {
                  if (op != OP_EQ && op != OP_NE) {
                        set_error("invalid string operator '%s'", op_names[op]);
                        return -1;
                  }
                  new = expr_new(EXPR_STR);
                  new->key = xstrdup(key);
                  glob_compile(&new->estr.glob_head, tok->str);
                  new->estr.op = op;
                  *exprp = new;
                  return 0;
            } else if (type == TOK_INT_OR_KEY) {
                  long int val = 0;

                  if (str_to_int(tok->str, &val)) {
                  }
                  new = expr_new(EXPR_INT);
                  new->key = xstrdup(key);
                  new->eint.val = val;
                  new->eint.op = op;
                  *exprp = new;
                  return 0;
            }
            if (op == OP_EQ || op == OP_NE) {
                  set_error("integer or string expected");
            } else {
                  set_error("integer expected");
            }
            return -1;
      }
      set_error("key expected");
      return -1;
}

static void add(struct expr **rootp, struct expr *expr)
{
      struct expr *tmp, *root = *rootp;

      if (root == NULL) {
            *rootp = expr;
            return;
      }

      tmp = root;
      while (tmp->right)
            tmp = tmp->right;
      if (tmp->type <= EXPR_OR) {
            /* tmp is binary, tree is incomplete */
            tmp->right = expr;
            expr->parent = tmp;
            return;
      }

      /* tmp is unary, tree is complete
       * expr must be a binary operator */
      BUG_ON(expr->type > EXPR_OR);

      expr->left = root;
      root->parent = expr;
      *rootp = expr;
}

static int parse(struct expr **rootp, struct list_head *head, struct list_head **itemp, int level)
{
      struct list_head *item = *itemp;

      while (1) {
            struct token *tok;
            struct expr *expr;
            int rc, type;

            rc = parse_one(&expr, head, &item);
            if (rc)
                  return rc;
            add(rootp, expr);
            if (item == head) {
                  if (level > 0) {
                        set_error("')' expected");
                        return -1;
                  }
                  *itemp = item;
                  return 0;
            }
            tok = container_of(item, struct token, node);
            if (tok->type == TOK_RPAREN) {
                  if (level == 0) {
                        set_error("unexpected ')'");
                        return -1;
                  }
                  *itemp = item->next;
                  return 0;
            }

            if (tok->type == TOK_AND) {
                  type = EXPR_AND;
            } else if (tok->type == TOK_OR) {
                  type = EXPR_OR;
            } else {
                  set_error("'&' or '|' expected");
                  return -1;
            }
            expr = expr_new(type);
            add(rootp, expr);
            item = item->next;
      }
}

struct expr *expr_parse(const char *str)
{
      LIST_HEAD(head);
      struct expr *root = NULL;
      struct list_head *item;
      int i;

      for (i = 0; str[i]; i++) {
            unsigned char c = str[i];
            if (c < 0x20) {
                  set_error("filter contains control characters");
                  return NULL;
            }
      }
      if (!u_is_valid(str)) {
            set_error("invalid UTF-8");
            return NULL;
      }

      if (tokenize(&head, str))
            return NULL;

      item = head.next;
      if (parse(&root, &head, &item, 0))
            root = NULL;
      free_tokens(&head);
      return root;
}

static const struct {
      const char *key;
      enum expr_type type;
} builtin[] = {
      { "album",  EXPR_STR },
      { "artist", EXPR_STR },
      { "date",   EXPR_INT },
      { "discnumber",   EXPR_INT },
      { "duration",     EXPR_INT },
      { "filename",     EXPR_STR },
      { "genre",  EXPR_STR },
      { "stream", EXPR_BOOL },
      { "tag",    EXPR_BOOL },
      { "title",  EXPR_STR },
      { "tracknumber",EXPR_INT },
      { NULL,           -1 },
};

int expr_check_leaves(struct expr **exprp, const char *(*get_filter)(const char *name))
{
      struct expr *expr = *exprp;
      struct expr *e;
      const char *filter;
      int i, rc;

      if (expr->left) {
            if (expr_check_leaves(&expr->left, get_filter))
                  return -1;
            if (expr->right)
                  return expr_check_leaves(&expr->right, get_filter);
            return 0;
      }

      for (i = 0; builtin[i].key; i++) {
            int cmp = strcmp(expr->key, builtin[i].key);

            if (cmp > 0)
                  continue;
            if (cmp < 0)
                  break;

            if (builtin[i].type != expr->type) {
                  /* type mismatch */
                  set_error("%s is %s", builtin[i].key, expr_names[builtin[i].type]);
                  return -1;
            }
            return 0;
      }
      if (expr->type != EXPR_BOOL) {
            /* unknown key */
            set_error("unkown key %s", expr->key);
            return -1;
      }

      /* user defined filter */
      filter = get_filter(expr->key);
      if (filter == NULL) {
            set_error("unkown filter or boolean %s", expr->key);
            return -1;
      }
      e = expr_parse(filter);
      if (e == NULL) {
            return -1;
      }
      rc = expr_check_leaves(&e, get_filter);
      if (rc) {
            expr_free(e);
            return rc;
      }

      /* replace */
      e->parent = expr->parent;
      expr_free(expr);

      /* this sets parents left pointer */
      *exprp = e;
      return 0;
}

int expr_eval(struct expr *expr, struct track_info *ti)
{
      enum expr_type type = expr->type;
      const char *key;

      if (expr->left) {
            int left = expr_eval(expr->left, ti);

            if (type == EXPR_AND)
                  return left && expr_eval(expr->right, ti);
            if (type == EXPR_OR)
                  return left || expr_eval(expr->right, ti);
            /* EXPR_NOT */
            return !left;
      }

      key = expr->key;
      if (type == EXPR_STR) {
            const char *val;
            int res;

            if (strcmp(key, "filename") == 0) {
                  val = ti->filename;
            } else {
                  val = comments_get_val(ti->comments, key);
                  if (val == NULL) {
                        /* NULL="something" is false */
                        if (expr->estr.op == SOP_EQ)
                              return 0;
                        /* NULL!="something" is true */
                        return 1;
                  }
            }
            res = glob_match(&expr->estr.glob_head, val);
            if (expr->estr.op == SOP_EQ)
                  return res;
            return !res;
      } else if (type == EXPR_INT) {
            int val, res;

            if (strcmp(key, "duration") == 0) {
                  val = ti->duration;
                  /* duration of a stream is infinite (well, almost) */
                  if (is_url(ti->filename))
                        val = INT_MAX;
            } else {
                  val = comments_get_int(ti->comments, key);
            }
            if (expr->eint.val == -1) {
                  /* -1 is "not set"
                   * doesn't make sense to do 123 < "not set"
                   * but it makes sense to do date=-1 (date is not set)
                   */
                  if (expr->eint.op == IOP_EQ)
                        return val == -1;
                  if (expr->eint.op == IOP_NE)
                        return val != -1;
            }
            if (val == -1) {
                  /* tag not set, can't compare */
                  return 0;
            }
            res = val - expr->eint.val;
            switch (expr->eint.op) {
            case IOP_LT:
                  return res < 0;
            case IOP_LE:
                  return res <= 0;
            case IOP_EQ:
                  return res == 0;
            case IOP_GE:
                  return res >= 0;
            case IOP_GT:
                  return res > 0;
            case IOP_NE:
                  return res != 0;
            }
      }
      if (strcmp(key, "stream") == 0)
            return is_url(ti->filename);
      return track_info_has_tag(ti);
}

void expr_free(struct expr *expr)
{
      if (expr->left) {
            expr_free(expr->left);
            if (expr->right)
                  expr_free(expr->right);
      }
      free(expr->key);
      if (expr->type == EXPR_STR)
            glob_free(&expr->estr.glob_head);
      free(expr);
}

const char *expr_error(void)
{
      return error_buf;
}

Generated by  Doxygen 1.6.0   Back to index