Audacious  $Id:Doxyfile42802007-03-2104:39:00Znenolod$
tuple_compiler.c
Go to the documentation of this file.
1 /*
2  * Audacious - Tuplez compiler
3  * Copyright (c) 2007 Matti 'ccr' Hämäläinen
4  * Copyright (c) 2011 John Lindgren
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; under version 3 of the License.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program. If not, see <http://www.gnu.org/licenses>.
17  *
18  * The Audacious team does not consider modular code linking to
19  * Audacious or using our public API to be a derived work.
20  */
21 
22 /*
23  * TODO:
24  * - Unicode/UTF-8 support in format strings. using any non-ASCII
25  * characters in Tuplez format strings WILL cause things go boom
26  * at the moment!
27  *
28  * - implement definitions (${=foo,"baz"} ${=foo,1234})
29  * - implement functions
30  * - implement handling of external expressions
31  * - evaluation context: how local variables should REALLY work?
32  * currently there is just a single context, is a "global" context needed?
33  */
34 
35 #include <ctype.h>
36 #include <stdarg.h>
37 #include <stdlib.h>
38 #include <stdio.h>
39 #include <string.h>
40 
41 #include <glib.h>
42 
43 #include "tuple_compiler.h"
44 
45 #define MAX_STR (256)
46 #define MIN_ALLOC_NODES (8)
47 #define MIN_ALLOC_BUF (64)
48 #define TUPLEZ_MAX_VARS (4)
49 
50 #define tuple_error(ctx, ...) fprintf (stderr, "Tuple compiler: " __VA_ARGS__)
51 
52 enum {
53  OP_RAW = 0, /* plain text */
54  OP_FIELD, /* a field/variable */
63 };
64 
65 enum {
68 };
69 
71  int opcode; /* operator, see OP_ enums */
72  int var[TUPLEZ_MAX_VARS]; /* tuple variable references */
73  char *text; /* raw text, if any (OP_RAW) */
74  struct _TupleEvalNode *children, *next, *prev; /* children of this struct, and pointer to next node. */
75 };
76 
77 typedef struct {
78  char *name;
79  int type; /* Type of variable, see VAR_* */
80  int defvali;
81  TupleValueType ctype; /* Type of constant/def value */
82 
83  int fieldidx; /* if >= 0: Index # of "pre-defined" Tuple fields */
84  bool_t fieldread, fieldvalid;
85  char * fieldstr;
86 } TupleEvalVar;
87 
91 };
92 
93 
95 {
96  g_free(var->name);
97  str_unref (var->fieldstr);
98  g_free(var);
99 }
100 
101 
102 /* Initialize an evaluation context
103  */
104 TupleEvalContext * tuple_evalctx_new(void)
105 {
106  return g_new0(TupleEvalContext, 1);
107 }
108 
109 
110 /* "Reset" the evaluation context
111  */
112 void tuple_evalctx_reset(TupleEvalContext *ctx)
113 {
114  int i;
115 
116  for (i = 0; i < ctx->nvariables; i++)
117  if (ctx->variables[i]) {
118  ctx->variables[i]->fieldread = FALSE;
119  ctx->variables[i]->fieldvalid = FALSE;
120  str_unref (ctx->variables[i]->fieldstr);
121  ctx->variables[i]->fieldstr = NULL;
122  }
123 }
124 
125 
126 /* Free an evaluation context and associated data
127  */
128 void tuple_evalctx_free(TupleEvalContext *ctx)
129 {
130  int i;
131 
132  if (!ctx) return;
133 
134  /* Deallocate variables */
135  for (i = 0; i < ctx->nvariables; i++)
136  if (ctx->variables[i])
137  tuple_evalctx_free_var(ctx->variables[i]);
138 
139  g_free(ctx->variables);
140  g_free(ctx);
141 }
142 
143 
144 static int tuple_evalctx_add_var (TupleEvalContext * ctx, const char * name,
145  const int type, const TupleValueType ctype)
146 {
147  int i;
148  TupleEvalVar *tmp = g_new0(TupleEvalVar, 1);
149 
150  tmp->name = g_strdup(name);
151  tmp->type = type;
152  tmp->fieldidx = -1;
153  tmp->ctype = ctype;
154 
155  /* Find fieldidx, if any */
156  switch (type) {
157  case TUPLE_VAR_FIELD:
158  tmp->fieldidx = tuple_field_by_name (name);
159  tmp->ctype = tuple_field_get_type (tmp->fieldidx);
160  break;
161 
162  case TUPLE_VAR_CONST:
163  if (ctype == TUPLE_INT)
164  tmp->defvali = atoi(name);
165  break;
166  }
167 
168  /* Find a free slot */
169  for (i = 0; i < ctx->nvariables; i++)
170  if (!ctx->variables[i]) {
171  ctx->variables[i] = tmp;
172  return i;
173  }
174 
175  i = ctx->nvariables;
176  ctx->variables = g_renew(TupleEvalVar *, ctx->variables, ctx->nvariables + MIN_ALLOC_NODES);
177  memset(&(ctx->variables[ctx->nvariables]), 0, MIN_ALLOC_NODES * sizeof(TupleEvalVar *));
178  ctx->nvariables += MIN_ALLOC_NODES;
179  ctx->variables[i] = tmp;
180 
181  return i;
182 }
183 
184 
185 static void tuple_evalnode_insert(TupleEvalNode **nodes, TupleEvalNode *node)
186 {
187  if (*nodes) {
188  node->prev = (*nodes)->prev;
189  (*nodes)->prev->next = node;
190  (*nodes)->prev = node;
191  node->next = NULL;
192  } else {
193  *nodes = node;
194  node->prev = node;
195  node->next = NULL;
196  }
197 }
198 
199 
200 static TupleEvalNode *tuple_evalnode_new(void)
201 {
202  return g_new0(TupleEvalNode, 1);
203 }
204 
205 
206 void tuple_evalnode_free(TupleEvalNode *expr)
207 {
208  TupleEvalNode *curr = expr, *next;
209 
210  while (curr) {
211  next = curr->next;
212 
213  g_free(curr->text);
214 
215  if (curr->children)
216  tuple_evalnode_free(curr->children);
217 
218  g_free(curr);
219 
220  curr = next;
221  }
222 }
223 
224 
225 static TupleEvalNode *tuple_compiler_pass1(int *level, TupleEvalContext *ctx, char **expression);
226 
227 
228 static bool_t tc_get_item(TupleEvalContext *ctx,
229  char **str, char *buf, gssize max,
230  char endch, bool_t *literal, char *errstr, char *item)
231 {
232  gssize i = 0;
233  char *s = *str, tmpendch;
234 
235  if (*s == '"') {
236  if (*literal == FALSE) {
237  tuple_error(ctx, "Literal string value not allowed in '%s'.\n", item);
238  return FALSE;
239  }
240  s++;
241  *literal = TRUE;
242  tmpendch = '"';
243  } else {
244  *literal = FALSE;
245  tmpendch = endch;
246  }
247 
248  if (*literal == FALSE) {
249  while (*s != '\0' && *s != tmpendch && (isalnum(*s) || *s == '-') && i < (max - 1)) {
250  buf[i++] = *(s++);
251  }
252 
253  if (*s != tmpendch && *s != '}' && !isalnum(*s) && *s != '-') {
254  tuple_error(ctx, "Invalid field '%s' in '%s'.\n", *str, item);
255  return FALSE;
256  } else if (*s != tmpendch) {
257  tuple_error(ctx, "Expected '%c' in '%s'.\n", tmpendch, item);
258  return FALSE;
259  }
260  } else {
261  while (*s != '\0' && *s != tmpendch && i < (max - 1)) {
262  if (*s == '\\') s++;
263  buf[i++] = *(s++);
264  }
265  }
266  buf[i] = '\0';
267 
268  if (*literal) {
269  if (*s == tmpendch)
270  s++;
271  else {
272  tuple_error(ctx, "Expected literal string end ('%c') in '%s'.\n", tmpendch, item);
273  return FALSE;
274  }
275  }
276 
277  if (*s != endch) {
278  tuple_error(ctx, "Expected '%c' after %s in '%s'\n", endch, errstr, item);
279  return FALSE;
280  } else {
281  *str = s;
282  return TRUE;
283  }
284 }
285 
286 
287 static int tc_get_variable(TupleEvalContext *ctx, char *name, int type)
288 {
289  int i;
291 
292  if (name == '\0') return -1;
293 
294  if (isdigit(name[0])) {
295  ctype = TUPLE_INT;
296  type = TUPLE_VAR_CONST;
297  } else
298  ctype = TUPLE_STRING;
299 
300  if (type != TUPLE_VAR_CONST) {
301  for (i = 0; i < ctx->nvariables; i++)
302  if (ctx->variables[i] && !strcmp(ctx->variables[i]->name, name))
303  return i;
304  }
305 
306  return tuple_evalctx_add_var(ctx, name, type, ctype);
307 }
308 
309 
310 static bool_t tc_parse_construct(TupleEvalContext *ctx, TupleEvalNode **res, char *item, char **c, int *level, int opcode)
311 {
312  char tmps1[MAX_STR], tmps2[MAX_STR];
313  bool_t literal1 = TRUE, literal2 = TRUE;
314 
315  (*c)++;
316  if (tc_get_item(ctx, c, tmps1, MAX_STR, ',', &literal1, "tag1", item)) {
317  (*c)++;
318  if (tc_get_item(ctx, c, tmps2, MAX_STR, ':', &literal2, "tag2", item)) {
319  TupleEvalNode *tmp = tuple_evalnode_new();
320  (*c)++;
321 
322  tmp->opcode = opcode;
323  if ((tmp->var[0] = tc_get_variable(ctx, tmps1, literal1 ? TUPLE_VAR_CONST : TUPLE_VAR_FIELD)) < 0) {
324  tuple_evalnode_free(tmp);
325  tuple_error(ctx, "Invalid variable '%s' in '%s'.\n", tmps1, item);
326  return FALSE;
327  }
328  if ((tmp->var[1] = tc_get_variable(ctx, tmps2, literal2 ? TUPLE_VAR_CONST : TUPLE_VAR_FIELD)) < 0) {
329  tuple_evalnode_free(tmp);
330  tuple_error(ctx, "Invalid variable '%s' in '%s'.\n", tmps2, item);
331  return FALSE;
332  }
333  tmp->children = tuple_compiler_pass1(level, ctx, c);
334  tuple_evalnode_insert(res, tmp);
335  } else
336  return FALSE;
337  } else
338  return FALSE;
339 
340  return TRUE;
341 }
342 
343 
344 /* Compile format expression into TupleEvalNode tree.
345  * A "simple" straight compilation is sufficient in first pass, later
346  * passes can perform subexpression removal and other optimizations.
347  */
348 static TupleEvalNode *tuple_compiler_pass1(int *level, TupleEvalContext *ctx, char **expression)
349 {
350  TupleEvalNode *res = NULL, *tmp = NULL;
351  char *c = *expression, *item, tmps1[MAX_STR];
352  bool_t literal, end = FALSE;
353 
354  (*level)++;
355 
356  while (*c != '\0' && !end) {
357  tmp = NULL;
358  if (*c == '}') {
359  c++;
360  (*level)--;
361  end = TRUE;
362  } else if (*c == '$') {
363  /* Expression? */
364  item = c++;
365  if (*c == '{') {
366  int opcode;
367  char *expr = ++c;
368 
369  switch (*c) {
370  case '?': c++;
371  /* Exists? */
372  literal = FALSE;
373  if (tc_get_item(ctx, &c, tmps1, MAX_STR, ':', &literal, "tag", item)) {
374  c++;
375  tmp = tuple_evalnode_new();
376  tmp->opcode = OP_EXISTS;
377  if ((tmp->var[0] = tc_get_variable(ctx, tmps1, TUPLE_VAR_FIELD)) < 0) {
378  tuple_error(ctx, "Invalid variable '%s' in '%s'.\n", tmps1, expr);
379  goto ret_error;
380  }
381  tmp->children = tuple_compiler_pass1(level, ctx, &c);
382  tuple_evalnode_insert(&res, tmp);
383  } else
384  goto ret_error;
385  break;
386 
387  case '=': c++;
388  if (*c != '=') {
389  /* Definition */
390  literal = FALSE;
391  if (tc_get_item(ctx, &c, tmps1, MAX_STR, ',', &literal, "variable", item)) {
392  c++;
393  if (*c == '"') {
394  /* String */
395  c++;
396  } else if (isdigit(*c)) {
397  /* Integer */
398  }
399 
400  tuple_error(ctx, "Definitions are not yet supported!\n");
401  goto ret_error;
402  } else
403  goto ret_error;
404  } else {
405  /* Equals? */
406  if (!tc_parse_construct(ctx, &res, item, &c, level, OP_EQUALS))
407  goto ret_error;
408  }
409  break;
410 
411  case '!': c++;
412  if (*c != '=') goto ext_expression;
413  if (!tc_parse_construct(ctx, &res, item, &c, level, OP_NOT_EQUALS))
414  goto ret_error;
415  break;
416 
417  case '<': c++;
418  if (*c == '=') {
419  opcode = OP_LTEQ;
420  c++;
421  } else
422  opcode = OP_LT;
423 
424  if (!tc_parse_construct(ctx, &res, item, &c, level, opcode))
425  goto ret_error;
426  break;
427 
428  case '>': c++;
429  if (*c == '=') {
430  opcode = OP_GTEQ;
431  c++;
432  } else
433  opcode = OP_GT;
434 
435  if (!tc_parse_construct(ctx, &res, item, &c, level, opcode))
436  goto ret_error;
437  break;
438 
439  case '(': c++;
440  if (!strncmp(c, "empty)?", 7)) {
441  c += 7;
442  literal = FALSE;
443  if (tc_get_item(ctx, &c, tmps1, MAX_STR, ':', &literal, "tag", item)) {
444  c++;
445  tmp = tuple_evalnode_new();
446  tmp->opcode = OP_IS_EMPTY;
447  if ((tmp->var[0] = tc_get_variable(ctx, tmps1, TUPLE_VAR_FIELD)) < 0) {
448  tuple_error(ctx, "Invalid variable '%s' in '%s'.\n", tmps1, expr);
449  goto ret_error;
450  }
451  tmp->children = tuple_compiler_pass1(level, ctx, &c);
452  tuple_evalnode_insert(&res, tmp);
453  } else
454  goto ret_error;
455  } else
456  goto ext_expression;
457  break;
458 
459  default:
460  ext_expression:
461  /* Get expression content */
462  c = expr;
463  literal = FALSE;
464  if (tc_get_item(ctx, &c, tmps1, MAX_STR, '}', &literal, "field", item)) {
465  /* FIXME!! FIX ME! Check for external expressions */
466 
467  /* I HAS A FIELD - A field. You has it. */
468  tmp = tuple_evalnode_new();
469  tmp->opcode = OP_FIELD;
470  if ((tmp->var[0] = tc_get_variable(ctx, tmps1, TUPLE_VAR_FIELD)) < 0) {
471  tuple_error(ctx, "Invalid variable '%s' in '%s'.\n", tmps1, expr);
472  goto ret_error;
473  }
474  tuple_evalnode_insert(&res, tmp);
475  c++;
476 
477  } else
478  goto ret_error;
479  }
480  } else {
481  tuple_error(ctx, "Expected '{', got '%c' in '%s'.\n", *c, c);
482  goto ret_error;
483  }
484 
485  } else if (*c == '%') {
486  /* Function? */
487  item = c++;
488  if (*c == '{') {
489  gssize i = 0;
490  c++;
491 
492  while (*c != '\0' && (isalnum(*c) || *c == '-') && *c != '}' && *c != ':' && i < (MAX_STR - 1))
493  tmps1[i++] = *(c++);
494  tmps1[i] = '\0';
495 
496  if (*c == ':') {
497  c++;
498  } else if (*c == '}') {
499  c++;
500  } else if (*c == '\0') {
501  tuple_error(ctx, "Expected '}' or function arguments in '%s'\n", item);
502  goto ret_error;
503  }
504  } else {
505  tuple_error(ctx, "Expected '{', got '%c' in '%s'.\n", *c, c);
506  goto ret_error;
507  }
508  } else {
509  /* Parse raw/literal text */
510  gssize i = 0;
511  while (*c != '\0' && *c != '$' && *c != '%' && *c != '}' && i < (MAX_STR - 1)) {
512  if (*c == '\\') c++;
513  tmps1[i++] = *(c++);
514  }
515  tmps1[i] = '\0';
516 
517  tmp = tuple_evalnode_new();
518  tmp->opcode = OP_RAW;
519  tmp->text = g_strdup(tmps1);
520  tuple_evalnode_insert(&res, tmp);
521  }
522  }
523 
524  if (*level <= 0) {
525  tuple_error(ctx, "Syntax error! Uneven/unmatched nesting of elements in '%s'!\n", c);
526  goto ret_error;
527  }
528 
529  *expression = c;
530  return res;
531 
532 ret_error:
533  tuple_evalnode_free(tmp);
534  tuple_evalnode_free(res);
535  return NULL;
536 }
537 
538 
539 TupleEvalNode *tuple_formatter_compile(TupleEvalContext *ctx, char *expr)
540 {
541  int level = 0;
542  char *tmpexpr = expr;
543  TupleEvalNode *res1;
544 
545  res1 = tuple_compiler_pass1(&level, ctx, &tmpexpr);
546 
547  if (level != 1) {
548  tuple_error(ctx, "Syntax error! Uneven/unmatched nesting of elements! (%d)\n", level);
549  tuple_evalnode_free(res1);
550  return NULL;
551  }
552 
553  return res1;
554 }
555 
556 
557 /* Fetch a tuple field value. Return TRUE if found. */
558 static bool_t tf_get_fieldval (TupleEvalVar * var, const Tuple * tuple)
559 {
560  if (var->type != TUPLE_VAR_FIELD || var->fieldidx < 0)
561  return FALSE;
562 
563  if (var->fieldread)
564  return var->fieldvalid;
565 
566  if (tuple_get_value_type (tuple, var->fieldidx, NULL) != var->ctype) {
567  var->fieldread = TRUE;
568  var->fieldvalid = FALSE;
569  return FALSE;
570  }
571 
572  if (var->ctype == TUPLE_INT)
573  var->defvali = tuple_get_int (tuple, var->fieldidx, NULL);
574  else if (var->ctype == TUPLE_STRING)
575  var->fieldstr = tuple_get_str (tuple, var->fieldidx, NULL);
576 
577  var->fieldread = TRUE;
578  var->fieldvalid = TRUE;
579  return TRUE;
580 }
581 
582 
583 /* Fetch string or int value of given variable, whatever type it might be.
584  * Return VAR_* type for the variable.
585  */
586 static TupleValueType tf_get_var (char * * tmps, int * tmpi, TupleEvalVar *
587  var, const Tuple * tuple)
588 {
590  *tmps = NULL;
591  *tmpi = 0;
592 
593  switch (var->type) {
594  case TUPLE_VAR_CONST:
595  switch (var->ctype) {
596  case TUPLE_STRING: *tmps = var->name; break;
597  case TUPLE_INT: *tmpi = var->defvali; break;
598  default: /* Cannot happen */ break;
599  }
600  type = var->ctype;
601  break;
602 
603  case TUPLE_VAR_FIELD:
604  if (tf_get_fieldval (var, tuple)) {
605  type = var->ctype;
606  if (type == TUPLE_INT)
607  * tmpi = var->defvali;
608  else if (type == TUPLE_STRING)
609  * tmps = var->fieldstr;
610  }
611  break;
612  }
613 
614  return type;
615 }
616 
617 
618 /* Evaluate tuple in given TupleEval expression in given
619  * context and return resulting string.
620  */
621 static bool_t tuple_formatter_eval_do (TupleEvalContext * ctx, TupleEvalNode *
622  expr, const Tuple * tuple, GString * out)
623 {
624  TupleEvalNode *curr = expr;
625  TupleEvalVar *var0, *var1;
626  TupleValueType type0, type1;
627  int tmpi0, tmpi1;
628  char tmps[MAX_STR], *tmps0, *tmps1, *tmps2;
629  bool_t result;
630  int resulti;
631 
632  if (!expr) return FALSE;
633 
634  while (curr) {
635  const char *str = NULL;
636 
637  switch (curr->opcode) {
638  case OP_RAW:
639  str = curr->text;
640  break;
641 
642  case OP_FIELD:
643  var0 = ctx->variables[curr->var[0]];
644 
645  switch (var0->type) {
646  case TUPLE_VAR_FIELD:
647  if (tf_get_fieldval (var0, tuple)) {
648  switch (var0->ctype) {
649  case TUPLE_STRING:
650  str = var0->fieldstr;
651  break;
652 
653  case TUPLE_INT:
654  g_snprintf (tmps, sizeof (tmps), "%d", var0->defvali);
655  str = tmps;
656  break;
657 
658  default:
659  str = NULL;
660  }
661  }
662  break;
663  }
664  break;
665 
666  case OP_EQUALS:
667  case OP_NOT_EQUALS:
668  case OP_LT: case OP_LTEQ:
669  case OP_GT: case OP_GTEQ:
670  var0 = ctx->variables[curr->var[0]];
671  var1 = ctx->variables[curr->var[1]];
672 
673  type0 = tf_get_var(&tmps0, &tmpi0, var0, tuple);
674  type1 = tf_get_var(&tmps1, &tmpi1, var1, tuple);
675  result = FALSE;
676 
677  if (type0 != TUPLE_UNKNOWN && type1 != TUPLE_UNKNOWN) {
678  if (type0 == type1) {
679  if (type0 == TUPLE_STRING)
680  resulti = strcmp(tmps0, tmps1);
681  else
682  resulti = tmpi0 - tmpi1;
683  } else {
684  if (type0 == TUPLE_INT)
685  resulti = tmpi0 - atoi(tmps1);
686  else
687  resulti = atoi(tmps0) - tmpi1;
688  }
689 
690  switch (curr->opcode) {
691  case OP_EQUALS: result = (resulti == 0); break;
692  case OP_NOT_EQUALS: result = (resulti != 0); break;
693  case OP_LT: result = (resulti < 0); break;
694  case OP_LTEQ: result = (resulti <= 0); break;
695  case OP_GT: result = (resulti > 0); break;
696  case OP_GTEQ: result = (resulti >= 0); break;
697  default: result = FALSE;
698  }
699  }
700 
701  if (result && ! tuple_formatter_eval_do (ctx, curr->children, tuple, out))
702  return FALSE;
703  break;
704 
705  case OP_EXISTS:
706  if (tf_get_fieldval (ctx->variables[curr->var[0]], tuple)) {
707  if (! tuple_formatter_eval_do (ctx, curr->children, tuple, out))
708  return FALSE;
709  }
710  break;
711 
712  case OP_IS_EMPTY:
713  var0 = ctx->variables[curr->var[0]];
714 
715  if (tf_get_fieldval (var0, tuple)) {
716  switch (var0->ctype) {
717  case TUPLE_INT:
718  result = (var0->defvali == 0);
719  break;
720 
721  case TUPLE_STRING:
722  result = TRUE;
723  tmps2 = var0->fieldstr;
724 
725  while (result && tmps2 && *tmps2 != '\0') {
726  gunichar uc = g_utf8_get_char(tmps2);
727  if (g_unichar_isspace(uc))
728  tmps2 = g_utf8_next_char(tmps2);
729  else
730  result = FALSE;
731  }
732  break;
733 
734  default:
735  result = TRUE;
736  }
737  } else
738  result = TRUE;
739 
740  if (result && ! tuple_formatter_eval_do (ctx, curr->children, tuple, out))
741  return FALSE;
742  break;
743 
744  default:
745  tuple_error(ctx, "Unimplemented opcode %d!\n", curr->opcode);
746  return FALSE;
747  break;
748  }
749 
750  if (str)
751  g_string_append (out, str);
752 
753  curr = curr->next;
754  }
755 
756  return TRUE;
757 }
758 
759 void tuple_formatter_eval (TupleEvalContext * ctx, TupleEvalNode * expr,
760  const Tuple * tuple, GString * out)
761 {
762  g_string_truncate (out, 0);
763  tuple_formatter_eval_do (ctx, expr, tuple, out);
764 }