Home | History | Annotate | Download | only in server 
      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 
     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 
     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 
     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 
     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 
     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 
     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 
     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 
     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 
     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 
    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. */
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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