tools/cfzy/libconfizery/cfzy_expr.c

   1 /*
   2  * Copyright (c) 2013, Olivier MATZ <zer0@droids-corp.org>
   3  * All rights reserved.
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <ctype.h>
  32 #include <sys/queue.h>
  33
  34 #include "cfzy_list.h"
  35 #include "cfzy_expr.h"
  36
  37 /* #define DEBUG */
  38
  39 #ifdef DEBUG
  40 #define debug_printf(args...) fprintf(stderr, args)
  41 #else
  42 #define debug_printf(args...) do { } while(0)
  43 #endif
  44
  45 /*
  46  * Return the operator (or the variable name) of the root node of the
  47  * given expression.
  48  */
  49 static const char *op_print(const struct cfzy_expr *exp)
  50 {
  51         switch (exp->optype) {
  52         case OP_OR:
  53                 return "||";
  54         case OP_AND:
  55                 return "&&";
  56         case OP_EQUAL:
  57                 return "==";
  58         case OP_OBRACKET:
  59                 return "(";
  60         case OP_NOT:
  61                 return "!";
  62         case OP_CBRACKET:
  63                 return ")";
  64         case OP_VAR:
  65                 return exp->varname;
  66         default:
  67                 return NULL;
  68         }
  69 }
  70
  71 /* recursive function called by cfzy_expr_graph_dump() */
  72 static void expr_dump_node(FILE *f, const struct cfzy_expr *exp, int level)
  73 {
  74         if (exp == NULL)
  75                 return;
  76
  77         fprintf(f, "vertice %d %s:%p\n", level, op_print(exp), exp);
  78
  79         if (exp->left) {
  80                 fprintf(f, "edge %p %p\n", exp, exp->left);
  81                 expr_dump_node(f, exp->left, level + 1);
  82         }
  83
  84         if (exp->right) {
  85                 fprintf(f, "edge %p %p\n", exp, exp->right);
  86                 expr_dump_node(f, exp->right, level + 1);
  87         }
  88 }
  89
  90 /* dump an expression graph in a file */
  91 int cfzy_expr_graph_dump(const char *filename, const struct cfzy_expr *exp)
  92 {
  93         FILE *f;
  94
  95         f = fopen(filename, "w");
  96         if (f == NULL)
  97                 return -1;
  98         expr_dump_node(f, exp, 0);
  99         fclose(f);
 100         return 0;
 101 }
 102
 103 /* return true if it's a binary operator */
 104 static int expr_is_bin_op(const struct cfzy_expr *exp)
 105 {
 106         if (exp->optype == OP_AND ||
 107             exp->optype == OP_OR ||
 108             exp->optype == OP_EQUAL)
 109                 return 1;
 110         return 0;
 111 }
 112
 113 /*
 114  * Dump the expression 'exp' as a string into the buffer 'buf' of
 115  * length 'len'. The string is nul-terminated. Return the number of
 116  * written bytes on success (not including \0), else return -1.
 117  */
 118 int cfzy_expr_to_str(const struct cfzy_expr *exp, char *buf, int len)
 119 {
 120         int n, orig_len;
 121
 122         orig_len = len;
 123
 124         /* dump left expression if it's a binary operator (in case of
 125          * unary operator, we only use the right child) */
 126         if (expr_is_bin_op(exp)) {
 127                 n = cfzy_expr_to_str(exp->left, buf, len);
 128                 if (n == -1 || n >= len || len <= 0)
 129                         return -1;
 130                 buf += n;
 131                 len -= n;
 132         }
 133
 134         /* dump the operator */
 135         if (expr_is_bin_op(exp))
 136                 n = snprintf(buf, len, " %s ", op_print(exp));
 137         else
 138                 n = snprintf(buf, len, "%s", op_print(exp));
 139         if (n == -1 || n >= len || len <= 0)
 140                 return -1;
 141         buf += n;
 142         len -= n;
 143
 144         /* dump the right expression except if it's a variable */
 145         if (exp->optype != OP_VAR) {
 146                 n = cfzy_expr_to_str(exp->right, buf, len);
 147                 if (n == -1 || n >= len || len <= 0)
 148                         return -1;
 149                 buf += n;
 150                 len -= n;
 151         }
 152
 153         /* close the bracket if needed */
 154         if (exp->optype == OP_OBRACKET) {
 155                 n = snprintf(buf, len, ")");
 156                 if (n == -1 || n >= len || len <= 0)
 157                         return -1;
 158                 buf += n;
 159                 len -= n;
 160         }
 161
 162         return orig_len - len;
 163 }
 164
 165 /*
 166  * Evaluate an expression. Return -1 on error, else the value of the
 167  * expression (greater or equal to 0).
 168  */
 169 int cfzy_expr_eval(const struct cfzy_expr *exp,
 170                    int (*getvalue)(const char *, void *), void *opaque_arg)
 171 {
 172         switch (exp->optype) {
 173         case OP_OR:
 174                 return cfzy_expr_eval(exp->left, getvalue, opaque_arg) ||
 175                         cfzy_expr_eval(exp->right, getvalue, opaque_arg);
 176         case OP_AND:
 177                 return cfzy_expr_eval(exp->left, getvalue, opaque_arg) &&
 178                         cfzy_expr_eval(exp->right, getvalue, opaque_arg);
 179         case OP_EQUAL:
 180                 return cfzy_expr_eval(exp->left, getvalue, opaque_arg) ==
 181                         cfzy_expr_eval(exp->right, getvalue, opaque_arg);
 182         case OP_OBRACKET:
 183                 return cfzy_expr_eval(exp->right, getvalue, opaque_arg);
 184         case OP_NOT:
 185                 return !cfzy_expr_eval(exp->right, getvalue, opaque_arg);
 186         case OP_VAR:
 187                 /* constants names (used for testing purposes) */
 188                 if (!strcmp("true", exp->varname))
 189                         return 1;
 190                 if (!strcmp("false", exp->varname))
 191                         return 0;
 192                 if (getvalue == NULL)
 193                         return -1;
 194                 return getvalue(exp->varname, opaque_arg);
 195         default:
 196                 debug_printf("%s(): bad operator\n", __FUNCTION__);
 197                 return -1;
 198         }
 199 }
 200
 201 /* The argument 'buf' is expression string that must start with an
 202  * opening bracket '('. This function returns the len of the
 203  * expression contained until we get the closing bracket corresponding
 204  * to buf[0]. Return -1 on error. */
 205 static int get_brac_len(const char *buf)
 206 {
 207         const char *s = buf;
 208         int i = 1;
 209
 210         if (*s != '(')
 211                 return -1;
 212         s++;
 213
 214         while(*s != '\0' && i != 0) {
 215                 if (*s == ')')
 216                         i--;
 217                 if (*s == '(')
 218                         i++;
 219                 s++;
 220         }
 221         if (i != 0)
 222                 return -1;
 223
 224         return s-buf;
 225 }
 226
 227 /*
 228  * Allocate a new expression exp corresponding to the next characters
 229  * in "buf". On success, a new expression exp is returned and the
 230  * number of eaten characters is set in "eatlen". If the end of the
 231  * string is reached, the expression exp contains the OP_EOF
 232  * operator. On error, NULL is returned.
 233  */
 234  static struct cfzy_expr *get_next_op(const char *buf, unsigned *eatlen)
 235 {
 236         struct cfzy_expr *exp;
 237         const char *s;
 238         unsigned len;
 239
 240         s = buf;
 241         exp = malloc(sizeof(struct cfzy_expr));
 242         if (exp == NULL)
 243                 return NULL;
 244         memset(exp, 0, sizeof(*exp));
 245
 246         switch (s[0]) {
 247         case '#':
 248                 exp->optype = OP_EOF;
 249                 *eatlen = s - buf + 1;
 250                 return exp;
 251         case '\0':
 252                 exp->optype = OP_EOF;
 253                 *eatlen = s - buf + 1;
 254                 return exp;
 255         case '(':
 256                 exp->optype = OP_OBRACKET;
 257                 *eatlen = s - buf + 1;
 258                 return exp;
 259         case ')':
 260                 exp->optype = OP_CBRACKET;
 261                 *eatlen = s - buf + 1;
 262                 return exp;
 263         case '!':
 264                 exp->optype = OP_NOT;
 265                 *eatlen = s - buf + 1;
 266                 return exp;
 267         case '&':
 268                 exp->optype = OP_AND;
 269                 if (s[1] != '&')
 270                         goto fail;
 271                 *eatlen = s - buf + 2;
 272                 return exp;
 273         case '|':
 274                 exp->optype = OP_OR;
 275                 if (s[1] != '|')
 276                         goto fail;
 277                 *eatlen = s - buf + 2;
 278                 return exp;
 279         case '=':
 280                 if (s[1] != '=')
 281                         goto fail;
 282                 exp->optype = OP_EQUAL;
 283                 *eatlen = s - buf + 2;
 284                 return exp;
 285         default:
 286                 /* a variable name must start with a letter */
 287                 if (isalpha(s[0]))
 288                         break;
 289                 goto fail;
 290         }
 291
 292         /* It's a variable, get name */
 293         while (isalnum(s[0]) || s[0] == '_')
 294                 s++;
 295
 296         exp->optype = OP_VAR;
 297         *eatlen = s - buf;
 298
 299         /* alloc string for variable name */
 300         len = s - buf;
 301         exp->varname = malloc(len+1);
 302         memcpy(exp->varname, buf, len);
 303         exp->varname[len] = '\0';
 304         return exp;
 305
 306  fail:
 307         free(exp);
 308         return NULL;
 309 }
 310
 311 /*
 312  * Parse the expression contained in s (which is a modifiable
 313  * string). Return 0 on success, in this case the expression tree is
 314  * returned in exp_ptr. On error, return -1.
 315  */
 316 static int expr_parse(char *s, struct cfzy_expr **exp_ptr)
 317 {
 318         struct cfzy_expr *top = NULL, *exp, *tmp;
 319         int len;
 320         unsigned eatlen;
 321
 322         debug_printf("parse <%s>\n", s);
 323
 324         if (*s == '\0')
 325                 return -1;
 326
 327         while (1) {
 328
 329                 /* skip spaces */
 330                 while (isspace(*s))
 331                         s++;
 332
 333                 /* get next operator/operand */
 334                 exp = get_next_op(s, &eatlen);
 335                 if (exp == NULL) {
 336                         debug_printf("Parse error\n");
 337                         goto fail;
 338                 }
 339
 340                 if (exp->optype == OP_EOF) {
 341                         free(exp);
 342                         exp = NULL;
 343                         break;
 344                 }
 345
 346                 debug_printf("New node: %s\n", op_print(exp));
 347                 switch (exp->optype) {
 348
 349                 case OP_OR:
 350                 case OP_AND:
 351                 case OP_EQUAL:
 352                         /* if it is the first node, error */
 353                         if (top == NULL)
 354                                 goto fail;
 355
 356                         /* the rightest leaf must be a variable */
 357                         tmp = top;
 358                         while (tmp->right)
 359                                 tmp = tmp->right;
 360                         if (tmp->optype != OP_VAR)
 361                                 goto fail;
 362
 363                         /* if new node priority is lower than root
 364                          * node, it becomes the new root */
 365                         if (exp->optype < top->optype) {
 366                                 exp->left = top;
 367                                 top = exp;
 368                                 break;
 369                         }
 370
 371                         /* exp is placed at the "rightest" leaf. Check
 372                          * that our parent is not a variable */
 373                         tmp = top;
 374                         while (tmp->right && exp->optype > tmp->right->optype)
 375                                 tmp = tmp->right;
 376
 377                         if (tmp->right == NULL)
 378                                 goto fail;
 379
 380                         exp->left = tmp->right;
 381                         tmp->right = exp;
 382                         break;
 383
 384                 case OP_OBRACKET:
 385                         /* if operator is an opening bracket,
 386                          * recursively call ourself with the
 387                          * sub-expression */
 388                         len = get_brac_len(s);
 389                         if (len < 0) {
 390                                 debug_printf("Cannot find closing bracket\n");
 391                                 goto fail;
 392                         }
 393                         s[len-1] = '\0';
 394                         if (expr_parse(s+1, &exp->right) < 0)
 395                                 goto fail;
 396                         if (exp->right == NULL)
 397                                 goto fail;
 398                         s[len-1] = ')';
 399                         s += len - 1;
 400
 401                         /* if it is the first node */
 402                         if (top == NULL) {
 403                                 top = exp;
 404                                 break;
 405                         }
 406
 407                         /* exp is placed at the "rightest" leaf. Check
 408                          * that our parent is not a variable */
 409                         tmp = top;
 410                         while (tmp->right)
 411                                 tmp = tmp->right;
 412                         if (tmp->optype == OP_VAR)
 413                                 goto fail;
 414                         tmp->right = exp;
 415                         break;
 416
 417                 case OP_NOT:
 418                 case OP_VAR:
 419                         /* if it is the first node */
 420                         if (top == NULL) {
 421                                 top = exp;
 422                                 break;
 423                         }
 424
 425                         /* exp is placed at the "rightest" leaf. Check
 426                          * that our parent is not a variable */
 427                         tmp = top;
 428                         while (tmp->right)
 429                                 tmp = tmp->right;
 430                         if (tmp->optype == OP_VAR)
 431                                 goto fail;
 432                         tmp->right = exp;
 433                         break;
 434
 435                 default:
 436                         /* should not happen */
 437                         debug_printf("Parse error\n");
 438                         goto fail;
 439                 }
 440
 441                 s += eatlen;
 442         }
 443
 444         if (top == NULL)
 445                 goto fail;
 446
 447         /* the rightest leaf must be a variable */
 448         tmp = top;
 449         while (tmp->right)
 450                 tmp = tmp->right;
 451         if (tmp->optype != OP_VAR) {
 452                 debug_printf("Missing operand\n");
 453                 goto fail;
 454         }
 455
 456         *exp_ptr = top;
 457         return 0;
 458
 459  fail:
 460         if (top != NULL)
 461                 cfzy_expr_free(top);
 462         if (exp != NULL)
 463                 cfzy_expr_free(exp);
 464
 465         return -1;
 466 }
 467
 468 /*
 469  * Parse the expression contained in buf. Return an expression tree or
 470  * NULL on error.
 471  */
 472 struct cfzy_expr *cfzy_expr_parse(const char *buf)
 473 {
 474         struct cfzy_expr *top;
 475         char *s;
 476         int ret;
 477
 478         s = strdup(buf);
 479         if (s == NULL)
 480                 return NULL;
 481
 482         ret = expr_parse(s, &top);
 483         free(s);
 484         if (ret < 0)
 485                 return NULL;
 486         return top;
 487 }
 488
 489 /* Free an expression tree */
 490 void cfzy_expr_free(struct cfzy_expr *exp)
 491 {
 492         if (exp == NULL)
 493                 return;
 494
 495         if (exp->left) {
 496                 cfzy_expr_free(exp->left);
 497                 exp->left = NULL;
 498         }
 499
 500         if (exp->right) {
 501                 cfzy_expr_free(exp->right);
 502                 exp->right = NULL;
 503         }
 504
 505         if (exp->varname != NULL)
 506                 free(exp->varname);
 507
 508         free(exp);
 509 }
 510
 511 /* recursive function called by cfzy_expr_get_vars() that browse the
 512  * expr tree to fill the list */
 513 static int
 514 expr_get_vars(const struct cfzy_expr *exp, struct cfzy_list_head *list)
 515 {
 516         struct cfzy_list_elt *e;
 517         char *name;
 518
 519         if (exp->left) {
 520                 if (expr_get_vars(exp->left, list) < 0)
 521                         return -1;
 522         }
 523
 524         if (exp->right) {
 525                 if (expr_get_vars(exp->right, list) < 0)
 526                         return -1;
 527         }
 528
 529         if (exp->optype != OP_VAR)
 530                 return 0;
 531
 532         /* ignore true and false constants */
 533         if (!strcmp(exp->varname, "true"))
 534                 return 0;
 535         if (!strcmp(exp->varname, "false"))
 536                 return 0;
 537
 538         /* nothing to do if var is already in list */
 539         TAILQ_FOREACH(e, list, next) {
 540                 if (!strcmp(e->ptr, exp->varname))
 541                         return 0;
 542         }
 543
 544         name = strdup(exp->varname);
 545         if (name == NULL)
 546                 return -1;
 547
 548         if (cfzy_list_add_tail(list, name) < 0) {
 549                 free(name);
 550                 return -1;
 551         }
 552
 553         return 0;
 554 }
 555
 556 /* Return a list containing all variables on which expression depend */
 557 struct cfzy_list_head *cfzy_expr_get_vars(const struct cfzy_expr *exp)
 558 {
 559         struct cfzy_list_head *list;
 560
 561         list = cfzy_list_alloc();
 562         if (list == NULL)
 563                 return NULL;
 564
 565         if (expr_get_vars(exp, list) < 0) {
 566                 cfzy_list_free(list, free);
 567                 return NULL;
 568         }
 569
 570         return list;
 571 }