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 static struct cras_expr_value *find_value(struct cras_expr_env *env, 96 const char *name) 97 { 98 int i; 99 const char **key; 100 101 FOR_ARRAY_ELEMENT(&env->keys, i, key) { 102 if (strcmp(*key, name) == 0) 103 return ARRAY_ELEMENT(&env->values, i); 104 } 105 return NULL; 106 } 107 108 /* Insert a (key, value) pair to the environment. The value is 109 * initialized to zero. Return the pointer to value so it can be set 110 * to the proper value. */ 111 static struct cras_expr_value *insert_value(struct cras_expr_env *env, 112 const char *key) 113 { 114 *ARRAY_APPEND_ZERO(&env->keys) = strdup(key); 115 return ARRAY_APPEND_ZERO(&env->values); 116 } 117 118 static struct cras_expr_value *find_or_insert_value(struct cras_expr_env *env, 119 const char *key) 120 { 121 struct cras_expr_value *value = find_value(env, key); 122 if (!value) 123 value = insert_value(env, key); 124 return value; 125 } 126 127 static void function_not(cras_expr_value_array *operands, 128 struct cras_expr_value *result) 129 { 130 struct cras_expr_value *value; 131 int is_false; 132 133 if (ARRAY_COUNT(operands) != 2) { 134 cras_expr_value_free(result); 135 syslog(LOG_ERR, "not takes one argument"); 136 return; 137 } 138 139 value = ARRAY_ELEMENT(operands, 1); 140 is_false = (value->type == CRAS_EXPR_VALUE_TYPE_BOOLEAN && 141 !value->u.boolean); 142 value_set_boolean(result, is_false); 143 } 144 145 static void function_and(cras_expr_value_array *operands, 146 struct cras_expr_value *result) 147 { 148 int i; 149 struct cras_expr_value *value; 150 int n = ARRAY_COUNT(operands); 151 152 /* no operands -- return #t */ 153 if (n <= 1) { 154 value_set_boolean(result, 1); 155 return; 156 } 157 158 /* if there is any #f, return it */ 159 FOR_ARRAY_ELEMENT(operands, i, value) { 160 if (i == 0) 161 continue; /* ignore "and" itself */ 162 if (value->type == CRAS_EXPR_VALUE_TYPE_BOOLEAN && 163 !value->u.boolean) { 164 value_set_boolean(result, 0); 165 return; 166 } 167 } 168 169 /* otherwise return the last element */ 170 copy_value(result, ARRAY_ELEMENT(operands, n - 1)); 171 } 172 173 static void function_or(cras_expr_value_array *operands, 174 struct cras_expr_value *result) 175 { 176 int i; 177 struct cras_expr_value *value; 178 179 FOR_ARRAY_ELEMENT(operands, i, value) { 180 if (i == 0) 181 continue; /* ignore "or" itself */ 182 if (value->type != CRAS_EXPR_VALUE_TYPE_BOOLEAN || 183 value->u.boolean) { 184 copy_value(result, value); 185 return; 186 } 187 } 188 189 value_set_boolean(result, 0); 190 } 191 192 static char function_equal_real(cras_expr_value_array *operands) 193 { 194 int i; 195 struct cras_expr_value *value, *prev; 196 197 FOR_ARRAY_ELEMENT(operands, i, value) { 198 if (i <= 1) 199 continue; /* ignore equal? and first operand */ 200 /* compare with the previous operand */ 201 202 prev = ARRAY_ELEMENT(operands, i - 1); 203 204 if (prev->type != value->type) 205 return 0; 206 207 switch (prev->type) { 208 case CRAS_EXPR_VALUE_TYPE_NONE: 209 break; 210 case CRAS_EXPR_VALUE_TYPE_BOOLEAN: 211 if (prev->u.boolean != value->u.boolean) 212 return 0; 213 break; 214 case CRAS_EXPR_VALUE_TYPE_INT: 215 if (prev->u.integer != value->u.integer) 216 return 0; 217 break; 218 case CRAS_EXPR_VALUE_TYPE_STRING: 219 if (strcmp(prev->u.string, value->u.string) != 0) 220 return 0; 221 break; 222 case CRAS_EXPR_VALUE_TYPE_FUNCTION: 223 if (prev->u.function != value->u.function) 224 return 0; 225 break; 226 } 227 } 228 229 return 1; 230 } 231 232 static void function_equal(cras_expr_value_array *operands, 233 struct cras_expr_value *result) 234 { 235 value_set_boolean(result, function_equal_real(operands)); 236 } 237 238 static void env_set_variable(struct cras_expr_env *env, const char *name, 239 struct cras_expr_value *new_value) 240 { 241 struct cras_expr_value *value = find_or_insert_value(env, name); 242 copy_value(value, new_value); 243 } 244 245 void cras_expr_env_install_builtins(struct cras_expr_env *env) 246 { 247 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT; 248 249 /* initialize env with builtin functions */ 250 cras_expr_value_set_function(&value, &function_not); 251 env_set_variable(env, "not", &value); 252 253 cras_expr_value_set_function(&value, &function_and); 254 env_set_variable(env, "and", &value); 255 256 cras_expr_value_set_function(&value, &function_or); 257 env_set_variable(env, "or", &value); 258 259 cras_expr_value_set_function(&value, &function_equal); 260 env_set_variable(env, "equal?", &value); 261 262 cras_expr_value_free(&value); 263 } 264 265 void cras_expr_env_set_variable_boolean(struct cras_expr_env *env, 266 const char *name, char boolean) 267 { 268 struct cras_expr_value *value = find_or_insert_value(env, name); 269 value_set_boolean(value, boolean); 270 } 271 272 void cras_expr_env_set_variable_integer(struct cras_expr_env *env, 273 const char *name, int integer) 274 { 275 struct cras_expr_value *value = find_or_insert_value(env, name); 276 value_set_integer(value, integer); 277 } 278 279 void cras_expr_env_set_variable_string(struct cras_expr_env *env, 280 const char *name, const char *str) 281 { 282 struct cras_expr_value *value = find_or_insert_value(env, name); 283 value_set_string(value, str); 284 } 285 286 void cras_expr_env_free(struct cras_expr_env *env) 287 { 288 int i; 289 const char **key; 290 struct cras_expr_value *value; 291 292 FOR_ARRAY_ELEMENT(&env->keys, i, key) { 293 free((char *)*key); 294 } 295 296 FOR_ARRAY_ELEMENT(&env->values, i, value) { 297 cras_expr_value_free(value); 298 } 299 300 ARRAY_FREE(&env->keys); 301 ARRAY_FREE(&env->values); 302 } 303 304 static struct cras_expr_expression *new_boolean_literal(char boolean) 305 { 306 struct cras_expr_expression *expr; 307 expr = calloc(1, sizeof(struct cras_expr_expression)); 308 expr->type = EXPR_TYPE_LITERAL; 309 value_set_boolean(&expr->u.literal, boolean); 310 return expr; 311 } 312 313 static struct cras_expr_expression *new_integer_literal(int integer) 314 { 315 struct cras_expr_expression *expr; 316 expr = calloc(1, sizeof(struct cras_expr_expression)); 317 expr->type = EXPR_TYPE_LITERAL; 318 value_set_integer(&expr->u.literal, integer); 319 return expr; 320 } 321 322 static struct cras_expr_expression *new_string_literal(const char *begin, 323 const char *end) 324 { 325 struct cras_expr_expression *expr; 326 expr = calloc(1, sizeof(struct cras_expr_expression)); 327 expr->type = EXPR_TYPE_LITERAL; 328 value_set_string2(&expr->u.literal, begin, end); 329 return expr; 330 } 331 332 static struct cras_expr_expression *new_variable(const char *begin, 333 const char *end) 334 { 335 struct cras_expr_expression *expr; 336 expr = calloc(1, sizeof(struct cras_expr_expression)); 337 expr->type = EXPR_TYPE_VARIABLE; 338 expr->u.variable = copy_str(begin, end); 339 return expr; 340 } 341 342 static struct cras_expr_expression *new_compound_expression() 343 { 344 struct cras_expr_expression *expr; 345 expr = calloc(1, sizeof(struct cras_expr_expression)); 346 expr->type = EXPR_TYPE_COMPOUND; 347 return expr; 348 } 349 350 static void add_sub_expression(struct cras_expr_expression *expr, 351 struct cras_expr_expression *sub) 352 { 353 ARRAY_APPEND(&expr->u.children, sub); 354 } 355 356 static int is_identifier_char(char c) 357 { 358 if (isspace(c)) 359 return 0; 360 if (c == '\0') 361 return 0; 362 if (isalpha(c)) 363 return 1; 364 if (c == '_' || c == '-' || c == '?') 365 return 1; 366 return 0; 367 } 368 369 static struct cras_expr_expression *parse_one_expr(const char **str) 370 { 371 /* skip whitespace */ 372 while (isspace(**str)) 373 (*str)++; 374 375 if (**str == '\0') 376 return NULL; 377 378 /* boolean literal: #t, #f */ 379 if (**str == '#') { 380 (*str)++; 381 char c = **str; 382 if (c == 't' || c == 'f') { 383 (*str)++; 384 return new_boolean_literal(c == 't'); 385 } else { 386 syslog(LOG_ERR, "unexpected char after #: '%c'", 387 c); 388 } 389 return NULL; 390 } 391 392 /* integer literal: (-)[0-9]+ */ 393 if (isdigit(**str) || (**str == '-' && isdigit((*str)[1]))) 394 return new_integer_literal(strtol(*str, (char **)str, 10)); 395 396 /* string literal: "..." */ 397 if (**str == '"') { 398 const char *begin = *str + 1; 399 const char *end = strchr(begin, '"'); 400 if (end == NULL) { 401 syslog(LOG_ERR, "no matching \""); 402 end = begin; 403 *str = begin; 404 } else { 405 *str = end + 1; 406 } 407 return new_string_literal(begin, end); 408 } 409 410 /* compound expression: (expr1 expr2 ...) */ 411 if (**str == '(') { 412 (*str)++; 413 struct cras_expr_expression *expr = new_compound_expression(); 414 while (1) { 415 struct cras_expr_expression *next = parse_one_expr(str); 416 if (next == NULL) 417 break; 418 add_sub_expression(expr, next); 419 } 420 if (**str != ')') { 421 syslog(LOG_ERR, "no matching ): found '%c'", **str); 422 cras_expr_expression_free(expr); 423 return NULL; 424 } else { 425 (*str)++; 426 } 427 return expr; 428 } 429 430 /* variable name */ 431 if (is_identifier_char(**str)) { 432 const char *begin = *str; 433 while (is_identifier_char(**str)) 434 (*str)++; 435 return new_variable(begin, *str); 436 } 437 438 return NULL; 439 } 440 441 struct cras_expr_expression *cras_expr_expression_parse(const char *str) 442 { 443 if (!str) 444 return NULL; 445 return parse_one_expr(&str); 446 } 447 448 void cras_expr_expression_free(struct cras_expr_expression *expr) 449 { 450 if (!expr) 451 return; 452 453 switch (expr->type) { 454 case EXPR_TYPE_NONE: 455 break; 456 case EXPR_TYPE_LITERAL: 457 cras_expr_value_free(&expr->u.literal); 458 break; 459 case EXPR_TYPE_VARIABLE: 460 free((char *)expr->u.variable); 461 break; 462 case EXPR_TYPE_COMPOUND: 463 { 464 int i; 465 struct cras_expr_expression **psub; 466 FOR_ARRAY_ELEMENT(&expr->u.children, i, psub) { 467 cras_expr_expression_free(*psub); 468 } 469 ARRAY_FREE(&expr->u.children); 470 break; 471 } 472 } 473 free(expr); 474 } 475 476 void cras_expr_expression_eval(struct cras_expr_expression *expr, 477 struct cras_expr_env *env, 478 struct cras_expr_value *result) 479 { 480 cras_expr_value_free(result); 481 482 switch (expr->type) { 483 case EXPR_TYPE_NONE: 484 break; 485 case EXPR_TYPE_LITERAL: 486 copy_value(result, &expr->u.literal); 487 break; 488 case EXPR_TYPE_VARIABLE: 489 { 490 struct cras_expr_value *value = find_value(env, 491 expr->u.variable); 492 if (value == NULL) { 493 syslog(LOG_ERR, "cannot find value for %s", 494 expr->u.variable); 495 } else { 496 copy_value(result, value); 497 } 498 break; 499 } 500 case EXPR_TYPE_COMPOUND: 501 { 502 int i; 503 struct cras_expr_expression **psub; 504 cras_expr_value_array values = ARRAY_INIT; 505 struct cras_expr_value *value; 506 507 FOR_ARRAY_ELEMENT(&expr->u.children, i, psub) { 508 value = ARRAY_APPEND_ZERO(&values); 509 cras_expr_expression_eval(*psub, env, value); 510 } 511 512 if (ARRAY_COUNT(&values) > 0) { 513 struct cras_expr_value *f = ARRAY_ELEMENT(&values, 0); 514 if (f->type == CRAS_EXPR_VALUE_TYPE_FUNCTION) 515 f->u.function(&values, result); 516 else 517 syslog(LOG_ERR, 518 "first element is not a function"); 519 } else { 520 syslog(LOG_ERR, "empty compound expression?"); 521 } 522 523 FOR_ARRAY_ELEMENT(&values, i, value) { 524 cras_expr_value_free(value); 525 } 526 527 ARRAY_FREE(&values); 528 break; 529 } 530 } 531 } 532 533 int cras_expr_expression_eval_int(struct cras_expr_expression *expr, 534 struct cras_expr_env *env, 535 int *integer) 536 { 537 int rc = 0; 538 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT; 539 540 cras_expr_expression_eval(expr, env, &value); 541 if (value.type == CRAS_EXPR_VALUE_TYPE_INT) { 542 *integer = value.u.integer; 543 } else { 544 syslog(LOG_ERR, "value type is not integer (%d)", value.type); 545 rc = -1; 546 } 547 cras_expr_value_free(&value); 548 return rc; 549 } 550 551 int cras_expr_expression_eval_boolean(struct cras_expr_expression *expr, 552 struct cras_expr_env *env, 553 char *boolean) 554 { 555 int rc = 0; 556 struct cras_expr_value value = CRAS_EXPR_VALUE_INIT; 557 558 cras_expr_expression_eval(expr, env, &value); 559 if (value.type == CRAS_EXPR_VALUE_TYPE_BOOLEAN) { 560 *boolean = value.u.boolean; 561 } else { 562 syslog(LOG_ERR, "value type is not boolean (%d)", value.type); 563 rc = -1; 564 } 565 cras_expr_value_free(&value); 566 return rc; 567 } 568
