1 /* Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
2 * Use of this source code is governed by a BSD-style license that can be
3 * found in the LICENSE file.
4 */
5
6 #include <ctype.h>
7 #include <stdlib.h>
8 #include <syslog.h>
9
10 #include "array.h"
11 #include "cras_expr.h"
12
copy_str(const char * begin,const char * end)13 static const char *copy_str(const char *begin, const char *end)
14 {
15 char *s = malloc(end - begin + 1);
16 memcpy(s, begin, end - begin);
17 s[end - begin] = '\0';
18 return s;
19 }
20
value_set_boolean(struct cras_expr_value * value,char boolean)21 static void value_set_boolean(struct cras_expr_value *value, char boolean)
22 {
23 cras_expr_value_free(value);
24 value->type = CRAS_EXPR_VALUE_TYPE_BOOLEAN;
25 value->u.boolean = !!boolean;
26 }
27
value_set_integer(struct cras_expr_value * value,int integer)28 static void value_set_integer(struct cras_expr_value *value, int integer)
29 {
30 cras_expr_value_free(value);
31 value->type = CRAS_EXPR_VALUE_TYPE_INT;
32 value->u.integer = integer;
33 }
34
value_set_string2(struct cras_expr_value * value,const char * begin,const char * end)35 static void value_set_string2(struct cras_expr_value *value, const char *begin,
36 const char *end)
37 {
38 cras_expr_value_free(value);
39 value->type = CRAS_EXPR_VALUE_TYPE_STRING;
40 value->u.string = copy_str(begin, end);
41 }
42
value_set_string(struct cras_expr_value * value,const char * str)43 static void value_set_string(struct cras_expr_value *value, const char *str)
44 {
45 value_set_string2(value, str, str + strlen(str));
46 }
47
cras_expr_value_set_function(struct cras_expr_value * value,cras_expr_function_type function)48 static void cras_expr_value_set_function(struct cras_expr_value *value,
49 cras_expr_function_type function)
50 {
51 cras_expr_value_free(value);
52 value->type = CRAS_EXPR_VALUE_TYPE_FUNCTION;
53 value->u.function = function;
54 }
55
copy_value(struct cras_expr_value * value,struct cras_expr_value * original)56 static void copy_value(struct cras_expr_value *value,
57 struct cras_expr_value *original)
58 {
59 cras_expr_value_free(value); /* free the original value first */
60 value->type = original->type;
61 switch (value->type) {
62 case CRAS_EXPR_VALUE_TYPE_NONE:
63 break;
64 case CRAS_EXPR_VALUE_TYPE_BOOLEAN:
65 value->u.boolean = original->u.boolean;
66 break;
67 case CRAS_EXPR_VALUE_TYPE_INT:
68 value->u.integer = original->u.integer;
69 break;
70 case CRAS_EXPR_VALUE_TYPE_STRING:
71 value->u.string = strdup(original->u.string);
72 break;
73 case CRAS_EXPR_VALUE_TYPE_FUNCTION:
74 value->u.function = original->u.function;
75 break;
76 }
77 }
78
cras_expr_value_free(struct cras_expr_value * value)79 void cras_expr_value_free(struct cras_expr_value *value)
80 {
81 switch (value->type) {
82 case CRAS_EXPR_VALUE_TYPE_STRING:
83 free((char *)value->u.string);
84 value->u.string = NULL;
85 break;
86 case CRAS_EXPR_VALUE_TYPE_NONE:
87 case CRAS_EXPR_VALUE_TYPE_BOOLEAN:
88 case CRAS_EXPR_VALUE_TYPE_INT:
89 case CRAS_EXPR_VALUE_TYPE_FUNCTION:
90 break;
91 }
92 value->type = CRAS_EXPR_VALUE_TYPE_NONE;
93 }
94
cras_expr_value_dump(struct dumper * d,const struct cras_expr_value * value)95 void cras_expr_value_dump(struct dumper *d, const struct cras_expr_value *value)
96 {
97 switch (value->type) {
98 case CRAS_EXPR_VALUE_TYPE_NONE:
99 dumpf(d, "none");
100 break;
101 case CRAS_EXPR_VALUE_TYPE_BOOLEAN:
102 dumpf(d, "boolean(%s)",
103 value->u.boolean ? "true" : "false");
104 break;
105 case CRAS_EXPR_VALUE_TYPE_INT:
106 dumpf(d, "integer(%d)", value->u.integer);
107 break;
108 case CRAS_EXPR_VALUE_TYPE_STRING:
109 dumpf(d, "string(%s)", value->u.string);
110 break;
111 case CRAS_EXPR_VALUE_TYPE_FUNCTION:
112 dumpf(d, "function(%p)", value->u.function);
113 break;
114 }
115 }
116
find_value(struct cras_expr_env * env,const char * name)117 static struct cras_expr_value *find_value(struct cras_expr_env *env,
118 const char *name)
119 {
120 int i;
121 const char **key;
122
123 FOR_ARRAY_ELEMENT(&env->keys, i, key) {
124 if (strcmp(*key, name) == 0)
125 return ARRAY_ELEMENT(&env->values, i);
126 }
127 return NULL;
128 }
129
130 /* Insert a (key, value) pair to the environment. The value is
131 * initialized to zero. Return the pointer to value so it can be set
132 * to the proper value. */
insert_value(struct cras_expr_env * env,const char * key)133 static struct cras_expr_value *insert_value(struct cras_expr_env *env,
134 const char *key)
135 {
136 *ARRAY_APPEND_ZERO(&env->keys) = strdup(key);
137 return ARRAY_APPEND_ZERO(&env->values);
138 }
139
find_or_insert_value(struct cras_expr_env * env,const char * key)140 static struct cras_expr_value *find_or_insert_value(struct cras_expr_env *env,
141 const char *key)
142 {
143 struct cras_expr_value *value = find_value(env, key);
144 if (!value)
145 value = insert_value(env, key);
146 return value;
147 }
148
function_not(cras_expr_value_array * operands,struct cras_expr_value * result)149 static void function_not(cras_expr_value_array *operands,
150 struct cras_expr_value *result)
151 {
152 struct cras_expr_value *value;
153 int is_false;
154
155 if (ARRAY_COUNT(operands) != 2) {
156 cras_expr_value_free(result);
157 syslog(LOG_ERR, "not takes one argument");
158 return;
159 }
160
161 value = ARRAY_ELEMENT(operands, 1);
162 is_false = (value->type == CRAS_EXPR_VALUE_TYPE_BOOLEAN &&
163 !value->u.boolean);
164 value_set_boolean(result, is_false);
165 }
166
function_and(cras_expr_value_array * operands,struct cras_expr_value * result)167 static void function_and(cras_expr_value_array *operands,
168 struct cras_expr_value *result)
169 {
170 int i;
171 struct cras_expr_value *value;
172 int n = ARRAY_COUNT(operands);
173
174 /* no operands -- return #t */
175 if (n <= 1) {
176 value_set_boolean(result, 1);
177 return;
178 }
179
180 /* if there is any #f, return it */
181 FOR_ARRAY_ELEMENT(operands, i, value) {
182 if (i == 0)
183 continue; /* ignore "and" itself */
184 if (value->type == CRAS_EXPR_VALUE_TYPE_BOOLEAN &&
185 !value->u.boolean) {
186 value_set_boolean(result, 0);
187 return;
188 }
189 }
190
191 /* otherwise return the last element */
192 copy_value(result, ARRAY_ELEMENT(operands, n - 1));
193 }
194
function_or(cras_expr_value_array * operands,struct cras_expr_value * result)195 static void function_or(cras_expr_value_array *operands,
196 struct cras_expr_value *result)
197 {
198 int i;
199 struct cras_expr_value *value;
200
201 FOR_ARRAY_ELEMENT(operands, i, value) {
202 if (i == 0)
203 continue; /* ignore "or" itself */
204 if (value->type != CRAS_EXPR_VALUE_TYPE_BOOLEAN ||
205 value->u.boolean) {
206 copy_value(result, value);
207 return;
208 }
209 }
210
211 value_set_boolean(result, 0);
212 }
213
function_equal_real(cras_expr_value_array * operands)214 static char function_equal_real(cras_expr_value_array *operands)
215 {
216 int i;
217 struct cras_expr_value *value, *prev;
218
219 FOR_ARRAY_ELEMENT(operands, i, value) {
220 if (i <= 1)
221 continue; /* ignore equal? and first operand */
222 /* compare with the previous operand */
223
224 prev = ARRAY_ELEMENT(operands, i - 1);
225
226 if (prev->type != value->type)
227 return 0;
228
229 switch (prev->type) {
230 case CRAS_EXPR_VALUE_TYPE_NONE:
231 break;
232 case CRAS_EXPR_VALUE_TYPE_BOOLEAN:
233 if (prev->u.boolean != value->u.boolean)
234 return 0;
235 break;
236 case CRAS_EXPR_VALUE_TYPE_INT:
237 if (prev->u.integer != value->u.integer)
238 return 0;
239 break;
240 case CRAS_EXPR_VALUE_TYPE_STRING:
241 if (strcmp(prev->u.string, value->u.string) != 0)
242 return 0;
243 break;
244 case CRAS_EXPR_VALUE_TYPE_FUNCTION:
245 if (prev->u.function != value->u.function)
246 return 0;
247 break;
248 }
249 }
250
251 return 1;
252 }
253
function_equal(cras_expr_value_array * operands,struct cras_expr_value * result)254 static void function_equal(cras_expr_value_array *operands,
255 struct cras_expr_value *result)
256 {
257 value_set_boolean(result, function_equal_real(operands));
258 }
259
env_set_variable(struct cras_expr_env * env,const char * name,struct cras_expr_value * new_value)260 static void env_set_variable(struct cras_expr_env *env, const char *name,
261 struct cras_expr_value *new_value)
262 {
263 struct cras_expr_value *value = find_or_insert_value(env, name);
264 copy_value(value, new_value);
265 }
266
cras_expr_env_install_builtins(struct cras_expr_env * env)267 void cras_expr_env_install_builtins(struct cras_expr_env *env)
268 {
269 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT;
270
271 /* initialize env with builtin functions */
272 cras_expr_value_set_function(&value, &function_not);
273 env_set_variable(env, "not", &value);
274
275 cras_expr_value_set_function(&value, &function_and);
276 env_set_variable(env, "and", &value);
277
278 cras_expr_value_set_function(&value, &function_or);
279 env_set_variable(env, "or", &value);
280
281 cras_expr_value_set_function(&value, &function_equal);
282 env_set_variable(env, "equal?", &value);
283
284 cras_expr_value_free(&value);
285 }
286
cras_expr_env_set_variable_boolean(struct cras_expr_env * env,const char * name,char boolean)287 void cras_expr_env_set_variable_boolean(struct cras_expr_env *env,
288 const char *name, char boolean)
289 {
290 struct cras_expr_value *value = find_or_insert_value(env, name);
291 value_set_boolean(value, boolean);
292 }
293
cras_expr_env_set_variable_integer(struct cras_expr_env * env,const char * name,int integer)294 void cras_expr_env_set_variable_integer(struct cras_expr_env *env,
295 const char *name, int integer)
296 {
297 struct cras_expr_value *value = find_or_insert_value(env, name);
298 value_set_integer(value, integer);
299 }
300
cras_expr_env_set_variable_string(struct cras_expr_env * env,const char * name,const char * str)301 void cras_expr_env_set_variable_string(struct cras_expr_env *env,
302 const char *name, const char *str)
303 {
304 struct cras_expr_value *value = find_or_insert_value(env, name);
305 value_set_string(value, str);
306 }
307
cras_expr_env_free(struct cras_expr_env * env)308 void cras_expr_env_free(struct cras_expr_env *env)
309 {
310 int i;
311 const char **key;
312 struct cras_expr_value *value;
313
314 FOR_ARRAY_ELEMENT(&env->keys, i, key) {
315 free((char *)*key);
316 }
317
318 FOR_ARRAY_ELEMENT(&env->values, i, value) {
319 cras_expr_value_free(value);
320 }
321
322 ARRAY_FREE(&env->keys);
323 ARRAY_FREE(&env->values);
324 }
325
cras_expr_env_dump(struct dumper * d,const struct cras_expr_env * env)326 void cras_expr_env_dump(struct dumper *d, const struct cras_expr_env *env)
327 {
328 int i;
329 const char **key;
330 struct cras_expr_value *value;
331
332 dumpf(d, "--- environment ---\n");
333 FOR_ARRAY_ELEMENT(&env->keys, i, key) {
334 dumpf(d, " key=%s,", *key);
335 dumpf(d, " value=");
336 value = ARRAY_ELEMENT(&env->values, i);
337 cras_expr_value_dump(d, value);
338 dumpf(d, "\n");
339 }
340 }
341
new_boolean_literal(char boolean)342 static struct cras_expr_expression *new_boolean_literal(char boolean)
343 {
344 struct cras_expr_expression *expr;
345 expr = calloc(1, sizeof(struct cras_expr_expression));
346 expr->type = EXPR_TYPE_LITERAL;
347 value_set_boolean(&expr->u.literal, boolean);
348 return expr;
349 }
350
new_integer_literal(int integer)351 static struct cras_expr_expression *new_integer_literal(int integer)
352 {
353 struct cras_expr_expression *expr;
354 expr = calloc(1, sizeof(struct cras_expr_expression));
355 expr->type = EXPR_TYPE_LITERAL;
356 value_set_integer(&expr->u.literal, integer);
357 return expr;
358 }
359
new_string_literal(const char * begin,const char * end)360 static struct cras_expr_expression *new_string_literal(const char *begin,
361 const char *end)
362 {
363 struct cras_expr_expression *expr;
364 expr = calloc(1, sizeof(struct cras_expr_expression));
365 expr->type = EXPR_TYPE_LITERAL;
366 value_set_string2(&expr->u.literal, begin, end);
367 return expr;
368 }
369
new_variable(const char * begin,const char * end)370 static struct cras_expr_expression *new_variable(const char *begin,
371 const char *end)
372 {
373 struct cras_expr_expression *expr;
374 expr = calloc(1, sizeof(struct cras_expr_expression));
375 expr->type = EXPR_TYPE_VARIABLE;
376 expr->u.variable = copy_str(begin, end);
377 return expr;
378 }
379
new_compound_expression()380 static struct cras_expr_expression *new_compound_expression()
381 {
382 struct cras_expr_expression *expr;
383 expr = calloc(1, sizeof(struct cras_expr_expression));
384 expr->type = EXPR_TYPE_COMPOUND;
385 return expr;
386 }
387
add_sub_expression(struct cras_expr_expression * expr,struct cras_expr_expression * sub)388 static void add_sub_expression(struct cras_expr_expression *expr,
389 struct cras_expr_expression *sub)
390 {
391 ARRAY_APPEND(&expr->u.children, sub);
392 }
393
is_identifier_char(char c)394 static int is_identifier_char(char c)
395 {
396 if (isspace(c))
397 return 0;
398 if (c == '\0')
399 return 0;
400 if (isalpha(c))
401 return 1;
402 if (c == '_' || c == '-' || c == '?')
403 return 1;
404 return 0;
405 }
406
parse_one_expr(const char ** str)407 static struct cras_expr_expression *parse_one_expr(const char **str)
408 {
409 /* skip whitespace */
410 while (isspace(**str))
411 (*str)++;
412
413 if (**str == '\0')
414 return NULL;
415
416 /* boolean literal: #t, #f */
417 if (**str == '#') {
418 (*str)++;
419 char c = **str;
420 if (c == 't' || c == 'f') {
421 (*str)++;
422 return new_boolean_literal(c == 't');
423 } else {
424 syslog(LOG_ERR, "unexpected char after #: '%c'",
425 c);
426 }
427 return NULL;
428 }
429
430 /* integer literal: (-)[0-9]+ */
431 if (isdigit(**str) || (**str == '-' && isdigit((*str)[1])))
432 return new_integer_literal(strtol(*str, (char **)str, 10));
433
434 /* string literal: "..." */
435 if (**str == '"') {
436 const char *begin = *str + 1;
437 const char *end = strchr(begin, '"');
438 if (end == NULL) {
439 syslog(LOG_ERR, "no matching \"");
440 end = begin;
441 *str = begin;
442 } else {
443 *str = end + 1;
444 }
445 return new_string_literal(begin, end);
446 }
447
448 /* compound expression: (expr1 expr2 ...) */
449 if (**str == '(') {
450 (*str)++;
451 struct cras_expr_expression *expr = new_compound_expression();
452 while (1) {
453 struct cras_expr_expression *next = parse_one_expr(str);
454 if (next == NULL)
455 break;
456 add_sub_expression(expr, next);
457 }
458 if (**str != ')') {
459 syslog(LOG_ERR, "no matching ): found '%c'", **str);
460 cras_expr_expression_free(expr);
461 return NULL;
462 } else {
463 (*str)++;
464 }
465 return expr;
466 }
467
468 /* variable name */
469 if (is_identifier_char(**str)) {
470 const char *begin = *str;
471 while (is_identifier_char(**str))
472 (*str)++;
473 return new_variable(begin, *str);
474 }
475
476 return NULL;
477 }
478
cras_expr_expression_parse(const char * str)479 struct cras_expr_expression *cras_expr_expression_parse(const char *str)
480 {
481 if (!str)
482 return NULL;
483 return parse_one_expr(&str);
484 }
485
dump_value(struct dumper * d,const struct cras_expr_value * value,int indent)486 static void dump_value(struct dumper *d, const struct cras_expr_value *value,
487 int indent)
488 {
489 switch (value->type) {
490 case CRAS_EXPR_VALUE_TYPE_NONE:
491 dumpf(d, "%*s(none)", indent, "");
492 break;
493 case CRAS_EXPR_VALUE_TYPE_BOOLEAN:
494 dumpf(d, "%*s%s", indent, "",
495 value->u.boolean ? "#t" : "#f");
496 break;
497 case CRAS_EXPR_VALUE_TYPE_INT:
498 dumpf(d, "%*s%d", indent, "", value->u.integer);
499 break;
500 case CRAS_EXPR_VALUE_TYPE_STRING:
501 dumpf(d, "%*s%s", indent, "", value->u.string);
502 break;
503 case CRAS_EXPR_VALUE_TYPE_FUNCTION:
504 dumpf(d, "%*s%p", indent, "", value->u.function);
505 break;
506 }
507 }
508
dump_one_expression(struct dumper * d,const struct cras_expr_expression * expr,int indent)509 static void dump_one_expression(struct dumper *d,
510 const struct cras_expr_expression *expr,
511 int indent)
512 {
513 int i;
514 struct cras_expr_expression **sub;
515
516 switch (expr->type) {
517 case EXPR_TYPE_NONE:
518 dumpf(d, "%*snone", indent, "");
519 break;
520 case EXPR_TYPE_LITERAL:
521 dumpf(d, "%*sliteral", indent, "");
522 dump_value(d, &expr->u.literal, indent + 2);
523 break;
524 case EXPR_TYPE_VARIABLE:
525 dumpf(d, "%*svariable (%s)", indent, "",
526 expr->u.variable);
527 break;
528 case EXPR_TYPE_COMPOUND:
529 dumpf(d, "%*scompound", indent, "");
530 FOR_ARRAY_ELEMENT(&expr->u.children, i, sub) {
531 dump_one_expression(d, *sub, indent + 2);
532 }
533 break;
534 }
535 }
536
cras_expr_expression_dump(struct dumper * d,const struct cras_expr_expression * expr)537 void cras_expr_expression_dump(struct dumper *d,
538 const struct cras_expr_expression *expr)
539 {
540 dump_one_expression(d, expr, 0);
541 }
542
cras_expr_expression_free(struct cras_expr_expression * expr)543 void cras_expr_expression_free(struct cras_expr_expression *expr)
544 {
545 if (!expr)
546 return;
547
548 switch (expr->type) {
549 case EXPR_TYPE_NONE:
550 break;
551 case EXPR_TYPE_LITERAL:
552 cras_expr_value_free(&expr->u.literal);
553 break;
554 case EXPR_TYPE_VARIABLE:
555 free((char *)expr->u.variable);
556 break;
557 case EXPR_TYPE_COMPOUND:
558 {
559 int i;
560 struct cras_expr_expression **psub;
561 FOR_ARRAY_ELEMENT(&expr->u.children, i, psub) {
562 cras_expr_expression_free(*psub);
563 }
564 ARRAY_FREE(&expr->u.children);
565 break;
566 }
567 }
568 free(expr);
569 }
570
cras_expr_expression_eval(struct cras_expr_expression * expr,struct cras_expr_env * env,struct cras_expr_value * result)571 void cras_expr_expression_eval(struct cras_expr_expression *expr,
572 struct cras_expr_env *env,
573 struct cras_expr_value *result)
574 {
575 cras_expr_value_free(result);
576
577 switch (expr->type) {
578 case EXPR_TYPE_NONE:
579 break;
580 case EXPR_TYPE_LITERAL:
581 copy_value(result, &expr->u.literal);
582 break;
583 case EXPR_TYPE_VARIABLE:
584 {
585 struct cras_expr_value *value = find_value(env,
586 expr->u.variable);
587 if (value == NULL) {
588 syslog(LOG_ERR, "cannot find value for %s",
589 expr->u.variable);
590 } else {
591 copy_value(result, value);
592 }
593 break;
594 }
595 case EXPR_TYPE_COMPOUND:
596 {
597 int i;
598 struct cras_expr_expression **psub;
599 cras_expr_value_array values = ARRAY_INIT;
600 struct cras_expr_value *value;
601
602 FOR_ARRAY_ELEMENT(&expr->u.children, i, psub) {
603 value = ARRAY_APPEND_ZERO(&values);
604 cras_expr_expression_eval(*psub, env, value);
605 }
606
607 if (ARRAY_COUNT(&values) > 0) {
608 struct cras_expr_value *f = ARRAY_ELEMENT(&values, 0);
609 if (f->type == CRAS_EXPR_VALUE_TYPE_FUNCTION)
610 f->u.function(&values, result);
611 else
612 syslog(LOG_ERR,
613 "first element is not a function");
614 } else {
615 syslog(LOG_ERR, "empty compound expression?");
616 }
617
618 FOR_ARRAY_ELEMENT(&values, i, value) {
619 cras_expr_value_free(value);
620 }
621
622 ARRAY_FREE(&values);
623 break;
624 }
625 }
626 }
627
cras_expr_expression_eval_int(struct cras_expr_expression * expr,struct cras_expr_env * env,int * integer)628 int cras_expr_expression_eval_int(struct cras_expr_expression *expr,
629 struct cras_expr_env *env,
630 int *integer)
631 {
632 int rc = 0;
633 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT;
634
635 cras_expr_expression_eval(expr, env, &value);
636 if (value.type == CRAS_EXPR_VALUE_TYPE_INT) {
637 *integer = value.u.integer;
638 } else {
639 syslog(LOG_ERR, "value type is not integer (%d)", value.type);
640 rc = -1;
641 }
642 cras_expr_value_free(&value);
643 return rc;
644 }
645
cras_expr_expression_eval_boolean(struct cras_expr_expression * expr,struct cras_expr_env * env,char * boolean)646 int cras_expr_expression_eval_boolean(struct cras_expr_expression *expr,
647 struct cras_expr_env *env,
648 char *boolean)
649 {
650 int rc = 0;
651 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT;
652
653 cras_expr_expression_eval(expr, env, &value);
654 if (value.type == CRAS_EXPR_VALUE_TYPE_BOOLEAN) {
655 *boolean = value.u.boolean;
656 } else {
657 syslog(LOG_ERR, "value type is not boolean (%d)", value.type);
658 rc = -1;
659 }
660 cras_expr_value_free(&value);
661 return rc;
662 }
663