Mercurial > hg-old > index.cgi

comparison lwlib/lw_expr.c @ 431:d7d7e4dca3e7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Eliminated infinite loop on recursive symbol resolution with a Q&D hack: limit the depth that lw_expr_simplify can be called to globally. Not thread friendly.
author lost@l-w.ca
date Sun, 24 Oct 2010 20:05:15 -0600
parents 652eee8f0c82
children 22bbb716dea6
comparison
equal deleted inserted replaced
430:4bcb763bddde 431:d7d7e4dca3e7
32 #include "lw_string.h" 32 #include "lw_string.h"
33 33
34 static lw_expr_fn_t *evaluate_special = NULL; 34 static lw_expr_fn_t *evaluate_special = NULL;
35 static lw_expr_fn2_t *evaluate_var = NULL; 35 static lw_expr_fn2_t *evaluate_var = NULL;
36 static lw_expr_fn3_t *parse_term = NULL; 36 static lw_expr_fn3_t *parse_term = NULL;
37
38 /* Q&D to break out of infinite recursion */
39 static int level = 0;
40 static int bailing = 0;
37 41
38 int lw_expr_istype(lw_expr_t e, int t) 42 int lw_expr_istype(lw_expr_t e, int t)
39 { 43 {
40 if (e -> type == t) 44 if (e -> type == t)
41 return 1; 45 return 1;
335 struct lw_expr_opers *o1, *o2; 339 struct lw_expr_opers *o1, *o2;
336 340
337 if (E1 == E2) 341 if (E1 == E2)
338 return 1; 342 return 1;
339 343
344 if (!E1 || !E2)
345 return 0;
346
340 if (!(E1 -> type == E2 -> type && E1 -> value == E2 -> value)) 347 if (!(E1 -> type == E2 -> type && E1 -> value == E2 -> value))
341 return 0; 348 return 0;
342 349
343 if (E1 -> type == lw_expr_type_var) 350 if (E1 -> type == lw_expr_type_var)
344 { 351 {
451 return 0; 458 return 0;
452 } 459 }
453 460
454 // not a times - have to assume it's the operand list 461 // not a times - have to assume it's the operand list
455 // with a "1 *" in front if it 462 // with a "1 *" in front if it
463 if (!e1 -> operands -> next)
464 return 0;
456 if (e1 -> operands -> next -> next) 465 if (e1 -> operands -> next -> next)
457 return 0; 466 return 0;
458 if (!lw_expr_compare(e1 -> operands -> next -> p, e2)) 467 if (!lw_expr_compare(e1 -> operands -> next -> p, e2))
459 return 0; 468 return 0;
460 return 1; 469 return 1;
475 if (!lw_expr_compare(e1, e2)) 484 if (!lw_expr_compare(e1, e2))
476 return 0; 485 return 0;
477 return 1; 486 return 1;
478 } 487 }
479 488
480 void lw_expr_simplify(lw_expr_t E, void *priv); 489 int lw_expr_contains(lw_expr_t E, lw_expr_t E1)
490 {
491 struct lw_expr_opers *o;
492
493 // NULL expr contains nothing :)
494 if (!E)
495 return 0;
496
497 if (E1 -> type != lw_expr_type_var && E1 -> type != lw_expr_type_special)
498 return 0;
499
500 if (lw_expr_compare(E, E1))
501 return 1;
502
503 for (o = E -> operands; o; o = o -> next)
504 {
505 if (lw_expr_contains(o -> p, E1))
506 return 1;
507 }
508 return 0;
509 }
510
511 void lw_expr_simplify_l(lw_expr_t E, void *priv);
481 512
482 void lw_expr_simplify_go(lw_expr_t E, void *priv) 513 void lw_expr_simplify_go(lw_expr_t E, void *priv)
483 { 514 {
484 struct lw_expr_opers *o; 515 struct lw_expr_opers *o;
485 516
516 if (E -> type == lw_expr_type_special && evaluate_special) 547 if (E -> type == lw_expr_type_special && evaluate_special)
517 { 548 {
518 lw_expr_t te; 549 lw_expr_t te;
519 550
520 te = evaluate_special(E -> value, E -> value2, priv); 551 te = evaluate_special(E -> value, E -> value2, priv);
552 if (lw_expr_contains(te, E))
553 lw_expr_destroy(te);
521 if (te) 554 if (te)
522 { 555 {
523 for (o = E -> operands; o; o = o -> next) 556 for (o = E -> operands; o; o = o -> next)
524 lw_expr_destroy(o -> p); 557 lw_expr_destroy(o -> p);
525 if (E -> type == lw_expr_type_var) 558 if (E -> type == lw_expr_type_var)
542 if (E -> type == lw_expr_type_var && evaluate_var) 575 if (E -> type == lw_expr_type_var && evaluate_var)
543 { 576 {
544 lw_expr_t te; 577 lw_expr_t te;
545 578
546 te = evaluate_var(E -> value2, priv); 579 te = evaluate_var(E -> value2, priv);
547 if (te) 580 if (lw_expr_contains(te, E))
581 lw_expr_destroy(te);
582 else if (te)
548 { 583 {
549 for (o = E -> operands; o; o = o -> next) 584 for (o = E -> operands; o; o = o -> next)
550 lw_expr_destroy(o -> p); 585 lw_expr_destroy(o -> p);
551 if (E -> type == lw_expr_type_var) 586 if (E -> type == lw_expr_type_var)
552 lw_free(E -> value2); 587 lw_free(E -> value2);
629 } 664 }
630 } 665 }
631 666
632 // simplify operands 667 // simplify operands
633 for (o = E -> operands; o; o = o -> next) 668 for (o = E -> operands; o; o = o -> next)
634 lw_expr_simplify(o -> p, priv); 669 lw_expr_simplify_l(o -> p, priv);
635 670
636 for (o = E -> operands; o; o = o -> next) 671 for (o = E -> operands; o; o = o -> next)
637 { 672 {
638 if (o -> p -> type != lw_expr_type_int) 673 if (o -> p -> type != lw_expr_type_int)
639 break; 674 break;
991 } 1026 }
992 } 1027 }
993 } 1028 }
994 } 1029 }
995 1030
996 void lw_expr_simplify(lw_expr_t E, void *priv) 1031 void lw_expr_simplify_l(lw_expr_t E, void *priv)
997 { 1032 {
998 lw_expr_t te; 1033 lw_expr_t te;
999 int c; 1034 int c;
1035
1036 (level)++;
1037 // bail out if the level gets too deep
1038 if (level >= 500 || bailing)
1039 {
1040 bailing = 1;
1041 level--;
1042 if (level == 0)
1043 bailing = 0;
1044 return;
1045 }
1000 do 1046 do
1001 { 1047 {
1002 te = lw_expr_copy(E); 1048 te = lw_expr_copy(E);
1003 lw_expr_simplify_go(E, priv); 1049 lw_expr_simplify_go(E, priv);
1004 c = 0; 1050 c = 0;
1005 if (lw_expr_compare(te, E) == 0) 1051 if (lw_expr_compare(te, E) == 0)
1006 c = 1; 1052 c = 1;
1007 lw_expr_destroy(te); 1053 lw_expr_destroy(te);
1008 } 1054 }
1009 while (c); 1055 while (c);
1010 } 1056 (level)--;
1011 1057 }
1058
1059 void lw_expr_simplify(lw_expr_t E, void *priv)
1060 {
1061 lw_expr_simplify_l(E, priv);
1062 }
1012 1063
1013 /* 1064 /*
1014 1065
1015 The following two functions are co-routines which evaluate an infix 1066 The following two functions are co-routines which evaluate an infix
1016 expression. lw_expr_parse_term checks for unary prefix operators then, if 1067 expression. lw_expr_parse_term checks for unary prefix operators then, if