src/esi/Expression.cc

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 86    ESI processing
   6  * AUTHOR: Robert Collins
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  ;  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37 #include "esi/Expression.h"
  38
  39 /* stack precedence rules:
  40  * before pushing an operator onto the stack, the
  41  * top 2 elements are checked. if either has a higher
  42  * or equal precedence than the current operator, they
  43  * are evaluated.
  44  * Start of expression has 5 precedence,
  45  * end of expression has 0 precedence
  46  * literal has 1 as does expression results
  47  * | has 2
  48  * & has 3
  49  * ! has 4
  50  * == != < > <= >= has 5
  51  * ( has 5
  52  * ) has 0
  53  */
  54
  55 typedef struct _stackmember stackmember;
  56
  57 typedef int evaluate (stackmember * stack, int *depth, int whereAmI,
  58                       stackmember * candidate);
  59
  60 typedef enum {
  61     ESI_EXPR_INVALID,
  62     ESI_EXPR_LITERAL,
  63     ESI_EXPR_OR,
  64     ESI_EXPR_AND,
  65     ESI_EXPR_NOT,
  66     ESI_EXPR_START,
  67     ESI_EXPR_END,
  68     ESI_EXPR_EQ,
  69     ESI_EXPR_NOTEQ,
  70     ESI_EXPR_LESS,
  71     ESI_EXPR_LESSEQ,
  72     ESI_EXPR_MORE,
  73     ESI_EXPR_MOREEQ,
  74     ESI_EXPR_EXPR                       /* the result of an expr PRI 1 */
  75 } evaltype;
  76
  77 typedef enum {
  78     ESI_LITERAL_STRING,
  79     ESI_LITERAL_FLOAT,
  80     ESI_LITERAL_INT,
  81     ESI_LITERAL_BOOL,
  82     ESI_LITERAL_INVALID
  83 } literalhint;
  84
  85 struct _stackmember {
  86     evaluate *eval;
  87     union {
  88         char *string;
  89         double floating;
  90         int integral;
  91     } value;
  92     literalhint valuestored;
  93     evaltype valuetype;
  94     int precedence;
  95 };
  96
  97 static void cleanmember (stackmember *);
  98 static void stackpop (stackmember * s, int *depth);
  99
 100 void
 101 cleanmember (stackmember * s)
 102 {
 103     if (s->valuetype == ESI_EXPR_LITERAL
 104             && s->valuestored == ESI_LITERAL_STRING) {
 105         safe_free (s->value.string);
 106         s->value.string = NULL;
 107     }
 108
 109 }
 110
 111 void
 112 stackpop (stackmember * s, int *depth)
 113 {
 114     if (!(*depth)--)
 115         return;
 116
 117     cleanmember (&s[*depth]);
 118 }
 119
 120 static evaluate evalnegate;
 121 static evaluate evalliteral;
 122 static evaluate evalor;
 123 static evaluate evaland;
 124 static evaluate evallesseq;
 125 static evaluate evallessthan;
 126 static evaluate evalmoreeq;
 127 static evaluate evalmorethan;
 128 static evaluate evalequals;
 129 static evaluate evalnotequals;
 130 static evaluate evalstartexpr;
 131 static evaluate evalendexpr;
 132 static evaluate evalexpr;
 133 static void dumpstack (stackmember * stack, int depth);
 134 static int addmember (stackmember * stack, int *stackdepth,
 135                       stackmember * candidate);
 136 static int membercompare (stackmember a, stackmember b);
 137 static char const *trim (char const *s);
 138 static stackmember getsymbol (const char *s, char const **endptr);
 139 static void printliteral (stackmember s);
 140 static void printmember (stackmember s);
 141
 142 /* -2 = failed to compate
 143  * -1 = a less than b
 144  * 0 = a equal b
 145  * 2 - a more than b
 146  */
 147 int
 148 membercompare (stackmember a, stackmember b)
 149 {
 150     /* we can compare: sub expressions to sub expressions ,
 151      * literals to literals
 152      */
 153
 154     if (!((a.valuetype == ESI_EXPR_LITERAL && b.valuetype == ESI_EXPR_LITERAL &&
 155             a.valuestored != ESI_LITERAL_INVALID && b.valuestored != ESI_LITERAL_INVALID) ||
 156             (a.valuetype == ESI_EXPR_EXPR && b.valuetype == ESI_EXPR_EXPR)))
 157         return -2;
 158
 159     if (a.valuetype == ESI_EXPR_EXPR) {
 160         if (a.value.integral == b.value.integral)
 161             return 0;
 162         else
 163             return 1;
 164     } else if (a.valuestored == ESI_LITERAL_STRING) {
 165         if (b.valuestored == ESI_LITERAL_STRING) {
 166             int i =strcmp (a.value.string, b.value.string);
 167
 168             if (i < 0)
 169                 return -1;
 170
 171             if (i > 0)
 172                 return 1;
 173
 174             return 0;
 175         } else {
 176             /* TODO: numeric to string conversion ? */
 177             debugs(86, 1, "strcmp with non-string");
 178             return -2;
 179         }
 180     } else if (a.valuestored == ESI_LITERAL_FLOAT) {
 181         if (b.valuestored == ESI_LITERAL_INT) {
 182             if (fabs(a.value.floating - b.value.integral) < 0.00001)
 183                 return 0;
 184             else if (a.value.floating < b.value.integral)
 185                 return -1;
 186             else
 187                 return 1;
 188         } else if (b.valuestored == ESI_LITERAL_FLOAT) {
 189             if (a.value.floating == b.value.floating)
 190                 return 0;
 191             else if (a.value.floating < b.value.floating)
 192                 return -1;
 193             else
 194                 return 1;
 195         } else {
 196             /* TODO: attempt numeric converson again? */
 197             debugs(86, 1, "floatcomp with non float or int");
 198             return -2;
 199         }
 200     } else if (a.valuestored == ESI_LITERAL_INT) {
 201         if (b.valuestored == ESI_LITERAL_INT) {
 202             if (a.value.integral == b.value.integral)
 203                 return 0;
 204             else if (a.value.integral < b.value.integral)
 205                 return -1;
 206             else
 207                 return 1;
 208         } else if (b.valuestored == ESI_LITERAL_FLOAT) {
 209             if (fabs(a.value.integral - b.value.floating) < 0.00001)
 210                 return 0;
 211             else if (a.value.integral < b.value.floating)
 212                 return -1;
 213             else
 214                 return 1;
 215         } else {
 216             /* TODO: attempt numeric converson again? */
 217             debugs(86, 1, "intcomp vs non float non int");
 218             return -2;
 219         }
 220     }
 221
 222     return -2;
 223 }
 224
 225 /* return 0 on success, 1 on failure */
 226 int evalnegate
 227 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 228 {
 229     if (whereAmI != *depth - 2)
 230         /* invalid stack */
 231         return 1;
 232
 233     if (stack[whereAmI + 1].valuetype != ESI_EXPR_EXPR)
 234         /* invalid operand */
 235         return 1;
 236
 237     /* copy down */
 238     --(*depth);
 239
 240     stack[whereAmI] = stack[(*depth)];
 241
 242     cleanmember (candidate);
 243
 244     if (stack[whereAmI].value.integral == 1)
 245         stack[whereAmI].value.integral = 0;
 246     else
 247         stack[whereAmI].value.integral = 1;
 248
 249     return 0;
 250 }
 251
 252 int evalliteral
 253 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 254 {
 255     debugs(86, 1, "attempt to evaluate a literal");
 256     /* literals can't be evaluated */
 257     return 1;
 258 }
 259
 260 int evalexpr
 261 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 262 {
 263     debugs(86, 1, "attempt to evaluate a sub-expression result");
 264     /* sub-scpr's can't be evaluated */
 265     return 1;
 266 }
 267
 268
 269 int evalor
 270 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 271 {
 272     int rv;
 273     stackmember srv;
 274
 275     if (*depth < 3)
 276         /* Not enough operands */
 277         return 1;
 278
 279     if (whereAmI != *depth - 2)
 280         /* invalid stack */
 281         return 1;
 282
 283     if (stack[whereAmI + 1].valuetype != ESI_EXPR_EXPR ||
 284             stack[whereAmI - 1].valuetype != ESI_EXPR_EXPR)
 285         /* invalid operand */
 286         return 1;
 287
 288     rv = stack[whereAmI - 1].value.integral || stack[whereAmI + 1].value.integral;
 289
 290     if (rv == -2)
 291         /* invalid comparison */
 292         return 1;
 293
 294     stackpop (stack, depth);      /* arg rhs */
 295
 296     stackpop (stack, depth);      /* me */
 297
 298     stackpop (stack, depth);      /* arg lhs */
 299
 300     srv.valuetype = ESI_EXPR_EXPR;
 301
 302     srv.eval = evalliteral;
 303
 304     srv.valuestored = ESI_LITERAL_BOOL;
 305
 306     srv.value.integral = rv ? 1 : 0;
 307
 308     srv.precedence = 1;
 309
 310     stack[(*depth)++] = srv;
 311
 312     /* we're out of way, try adding now */
 313     if (!addmember (stack, depth, candidate))
 314         /* Something wrong upstream */
 315         return 1;
 316
 317     return 0;
 318 }
 319
 320 int evaland
 321 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 322 {
 323     int rv;
 324     stackmember srv;
 325
 326     if (*depth < 3)
 327         /* Not enough operands */
 328         return 1;
 329
 330     if (whereAmI != *depth - 2)
 331         /* invalid stack */
 332         return 1;
 333
 334     if (stack[whereAmI + 1].valuetype != ESI_EXPR_EXPR ||
 335             stack[whereAmI - 1].valuetype != ESI_EXPR_EXPR)
 336         /* invalid operand */
 337         return 1;
 338
 339     rv = stack[whereAmI - 1].value.integral && stack[whereAmI + 1].value.integral;
 340
 341     if (rv == -2)
 342         /* invalid comparison */
 343         return 1;
 344
 345     stackpop (stack, depth);      /* arg rhs */
 346
 347     stackpop (stack, depth);      /* me */
 348
 349     stackpop (stack, depth);      /* arg lhs */
 350
 351     srv.valuetype = ESI_EXPR_EXPR;
 352
 353     srv.eval = evalexpr;
 354
 355     srv.valuestored = ESI_LITERAL_BOOL;
 356
 357     srv.value.integral = rv ? 1 : 0;
 358
 359     srv.precedence = 1;
 360
 361     stack[(*depth)++] = srv;
 362
 363     /* we're out of way, try adding now */
 364     if (!addmember (stack, depth, candidate))
 365         /* Something wrong upstream */
 366         return 1;
 367
 368     return 0;
 369 }
 370
 371 int evallesseq
 372 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 373 {
 374     int rv;
 375     stackmember srv;
 376
 377     if (*depth < 3)
 378         /* Not enough operands */
 379         return 1;
 380
 381     if (whereAmI != *depth - 2)
 382         /* invalid stack */
 383         return 1;
 384
 385     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 386
 387     if (rv == -2)
 388         /* invalid comparison */
 389         return 1;
 390
 391     stackpop (stack, depth);      /* arg rhs */
 392
 393     stackpop (stack, depth);      /* me */
 394
 395     stackpop (stack, depth);      /* arg lhs */
 396
 397     srv.valuetype = ESI_EXPR_EXPR;
 398
 399     srv.eval = evalexpr;
 400
 401     srv.valuestored = ESI_LITERAL_BOOL;
 402
 403     srv.value.integral = rv <= 0 ? 1 : 0;
 404
 405     srv.precedence = 1;
 406
 407     stack[(*depth)++] = srv;
 408
 409     /* we're out of way, try adding now */
 410     if (!addmember (stack, depth, candidate))
 411         /* Something wrong upstream */
 412         return 1;
 413
 414     /*  debugs(86, 1, "?= " << srv.value.integral << " "); */
 415     return 0;
 416
 417
 418 }
 419
 420 int evallessthan
 421 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 422 {
 423     int rv;
 424     stackmember srv;
 425
 426     if (*depth < 3)
 427         /* Not enough operands */
 428         return 1;
 429
 430     if (whereAmI != *depth - 2)
 431         /* invalid stack */
 432         return 1;
 433
 434     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 435
 436     if (rv == -2)
 437         /* invalid comparison */
 438         return 1;
 439
 440     stackpop (stack, depth);      /* arg rhs */
 441
 442     stackpop (stack, depth);      /* me */
 443
 444     stackpop (stack, depth);      /* arg lhs */
 445
 446     srv.valuetype = ESI_EXPR_EXPR;
 447
 448     srv.eval = evalexpr;
 449
 450     srv.valuestored = ESI_LITERAL_BOOL;
 451
 452     srv.value.integral = rv < 0 ? 1 : 0;
 453
 454     srv.precedence = 1;
 455
 456     stack[(*depth)++] = srv;
 457
 458     /* we're out of way, try adding now */
 459     if (!addmember (stack, depth, candidate))
 460         /* Something wrong upstream */
 461         return 1;
 462
 463     /* debugs(86, 1, "?= " << srv.value.integral << " "); */
 464     return 0;
 465
 466
 467 }
 468
 469 int evalmoreeq
 470 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 471 {
 472     int rv;
 473     stackmember srv;
 474
 475     if (*depth < 3)
 476         /* Not enough operands */
 477         return 1;
 478
 479     if (whereAmI != *depth - 2)
 480         /* invalid stack */
 481         return 1;
 482
 483     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 484
 485     if (rv == -2)
 486         /* invalid comparison */
 487         return 1;
 488
 489     stackpop (stack, depth);      /* arg rhs */
 490
 491     stackpop (stack, depth);      /* me */
 492
 493     stackpop (stack, depth);      /* arg lhs */
 494
 495     srv.valuetype = ESI_EXPR_EXPR;
 496
 497     srv.eval = evalexpr;
 498
 499     srv.valuestored = ESI_LITERAL_BOOL;
 500
 501     srv.value.integral = rv >= 0 ? 1 : 0;
 502
 503     srv.precedence = 1;
 504
 505     stack[(*depth)++] = srv;
 506
 507     /* we're out of way, try adding now */
 508     if (!addmember (stack, depth, candidate))
 509         /* Something wrong upstream */
 510         return 1;
 511
 512     /* debugs(86, 1, "?= " << srv.value.integral << " "); */
 513     return 0;
 514
 515
 516 }
 517
 518 int evalmorethan
 519 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 520 {
 521     int rv;
 522     stackmember srv;
 523
 524     if (*depth < 3)
 525         /* Not enough operands */
 526         return 1;
 527
 528     if (whereAmI != *depth - 2)
 529         /* invalid stack */
 530         return 1;
 531
 532     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 533
 534     if (rv == -2)
 535         /* invalid comparison */
 536         return 1;
 537
 538     stackpop (stack, depth);    /* arg rhs */
 539
 540     stackpop (stack, depth);    /* me */
 541
 542     stackpop (stack, depth);    /* arg lhs */
 543
 544     srv.valuetype = ESI_EXPR_EXPR;
 545
 546     srv.eval = evalexpr;
 547
 548     srv.valuestored = ESI_LITERAL_BOOL;
 549
 550     srv.value.integral = rv > 0 ? 1 : 0;
 551
 552     srv.precedence = 1;
 553
 554     stack[(*depth)++] = srv;
 555
 556     /* we're out of way, try adding now */
 557     if (!addmember (stack, depth, candidate))
 558         /* Something wrong upstream */
 559         return 1;
 560
 561     /* debugs(86, 1, "?= " << srv.value.integral << " "); */
 562     return 0;
 563
 564 }
 565
 566 int
 567 evalequals (stackmember * stack, int *depth, int whereAmI,
 568             stackmember * candidate)
 569 {
 570     int rv;
 571     stackmember srv;
 572
 573     if (*depth < 3)
 574         /* Not enough operands */
 575         return 1;
 576
 577     if (whereAmI != *depth - 2)
 578         /* invalid stack */
 579         return 1;
 580
 581     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 582
 583     if (rv == -2)
 584         /* invalid comparison */
 585         return 1;
 586
 587     stackpop (stack, depth);    /* arg rhs */
 588
 589     stackpop (stack, depth);    /* me */
 590
 591     stackpop (stack, depth);    /* arg lhs */
 592
 593     srv.valuetype = ESI_EXPR_EXPR;
 594
 595     srv.eval = evalexpr;
 596
 597     srv.valuestored = ESI_LITERAL_BOOL;
 598
 599     srv.value.integral = rv ? 0 : 1;
 600
 601     srv.precedence = 1;
 602
 603     stack[(*depth)++] = srv;
 604
 605     /* we're out of way, try adding now */
 606     if (!addmember (stack, depth, candidate))
 607         /* Something wrong upstream */
 608         return 1;
 609
 610     /* debugs(86, 1, "?= " << srv.value.integral << " "); */
 611     return 0;
 612 }
 613
 614 int evalnotequals
 615 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 616 {
 617     int rv;
 618     stackmember srv;
 619
 620     if (*depth < 3)
 621         /* Not enough operands */
 622         return 1;
 623
 624     if (whereAmI != *depth - 2)
 625         /* invalid stack */
 626         return 1;
 627
 628     rv = membercompare (stack[whereAmI - 1], stack[whereAmI + 1]);
 629
 630     if (rv == -2)
 631         /* invalid comparison */
 632         return 1;
 633
 634     stackpop (stack, depth);    /* arg rhs */
 635
 636     stackpop (stack, depth);    /* me */
 637
 638     stackpop (stack, depth);    /* arg lhs */
 639
 640     srv.valuetype = ESI_EXPR_EXPR;
 641
 642     srv.eval = evalexpr;
 643
 644     srv.valuestored = ESI_LITERAL_BOOL;
 645
 646     srv.value.integral = rv ? 1 : 0;
 647
 648     srv.precedence = 1;
 649
 650     stack[(*depth)++] = srv;
 651
 652     /* we're out of way, try adding now */
 653     if (!addmember (stack, depth, candidate))
 654         /* Something wrong upstream */
 655         return 1;
 656
 657     /* debugs(86, 1, "?= " << srv.value.integral << " "); */
 658     return 0;
 659 }
 660
 661 int evalstartexpr
 662 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 663 {
 664     /* debugs(86, 1, "?("); */
 665
 666     if (whereAmI != *depth - 2)
 667         /* invalid stack */
 668         return 1;
 669
 670     /* Only valid when RHS is an end bracket */
 671     if (candidate->valuetype != ESI_EXPR_END)
 672         return 1;
 673
 674     --(*depth);
 675
 676     stack[whereAmI] = stack[(*depth)];
 677
 678     cleanmember (candidate);
 679
 680     return 0;
 681 }
 682
 683 int evalendexpr
 684 (stackmember * stack, int *depth, int whereAmI, stackmember * candidate)
 685 {
 686     /* Can't evaluate ) brackets */
 687     return 1;
 688 }
 689
 690 char const *
 691 trim (char const *s)
 692 {
 693     while (*s == ' ')
 694         ++s;
 695
 696     return s;
 697 }
 698
 699 stackmember
 700 getsymbol (const char *s, char const **endptr)
 701 {
 702     stackmember rv;
 703     char *end;
 704     char const *origs = s;
 705     /* trim whitespace */
 706     s = trim (s);
 707     rv.eval = NULL;             /* A literal */
 708     rv.valuetype = ESI_EXPR_INVALID;
 709     rv.valuestored = ESI_LITERAL_INVALID;
 710     rv..precedence = 1; /* A literal */
 711
 712     if (('0' <= *s && *s <= '9') || *s == '-') {
 713         size_t length = strspn (s, "0123456789.");
 714         char const *point;
 715
 716         if ((point = strchr (s, '.')) && point - s < (ssize_t)length) {
 717             /* floating point */
 718             errno=0; /* reset errno */
 719             rv.value.floating = strtod (s, &end);
 720
 721             if (s == end || errno) {
 722                 /* Couldn't convert to float */
 723                 debugs(86, 1, "failed to convert '" << s << "' to float ");
 724                 *endptr = origs;
 725             } else {
 726                 debugs (86,6, "found " << rv.value.floating << " of length " << end - s);
 727                 *endptr = end;
 728                 rv.eval = evalliteral;
 729                 rv.valuestored = ESI_LITERAL_FLOAT;
 730                 rv.valuetype = ESI_EXPR_LITERAL;
 731                 rv.precedence = 1;
 732             }
 733         } else {
 734             /* INT */
 735             errno=0; /* reset errno */
 736             rv.value.integral = strtol (s, &end, 0);
 737
 738             if (s == end || errno) {
 739                 /* Couldn't convert to int */
 740                 debugs(86, 1, "failed to convert '" << s << "' to int ");
 741                 *endptr = origs;
 742             } else {
 743                 debugs (86,6, "found " << rv.value.integral << " of length " << end - s);
 744                 *endptr = end;
 745                 rv.eval = evalliteral;
 746                 rv.valuestored = ESI_LITERAL_INT;
 747                 rv.valuetype = ESI_EXPR_LITERAL;
 748                 rv.precedence = 1;
 749             }
 750         }
 751     } else if ('!' == *s) {
 752         if ('=' == *(s + 1)) {
 753             debugs(86, 6, "found !=");
 754             *endptr = s + 2;
 755             rv.eval = evalnotequals;
 756             rv.valuetype = ESI_EXPR_NOTEQ;
 757             rv.precedence = 5;
 758         } else {
 759             debugs(86, 6, "found !");
 760             *endptr = s + 1;
 761             rv.valuetype = ESI_EXPR_NOT;
 762             rv.precedence = 4;
 763             rv.eval = evalnegate;
 764         }
 765     } else if ('\'' == *s) {
 766         char const *t = s + 1;
 767         debugs(86, 6, "found \'");
 768
 769         while (*t != '\'' && *t)
 770             ++t;
 771
 772         if (!*t) {
 773             debugs(86, 1, "missing end \' in '" << s << "'");
 774             *endptr = origs;
 775         } else {
 776             *endptr = t + 1;
 777             /* Special case for zero length strings */
 778
 779             if (t - s - 1)
 780                 rv.value.string = xstrndup (s + 1, t - s - 1);
 781             else
 782                 rv.value.string = static_cast<char *>(xcalloc (1,1));
 783
 784             rv.eval = evalliteral;
 785
 786             rv.valuestored = ESI_LITERAL_STRING;
 787
 788             rv.valuetype = ESI_EXPR_LITERAL;
 789
 790             rv.precedence = 1;
 791
 792             debugs(86, 6, "found  string '" << rv.value.string << "'");
 793         }
 794     } else if ('(' == *s) {
 795         debugs(86, 6, "found subexpr start");
 796         *endptr = s + 1;
 797         rv.valuetype = ESI_EXPR_START;
 798         rv.precedence = 5;
 799         rv.eval = evalstartexpr;
 800     } else if (')' == *s) {
 801         debugs(86, 6, "found subexpr end");
 802         *endptr = s + 1;
 803         rv.valuetype = ESI_EXPR_END;
 804         rv.precedence = 0;
 805         rv.eval = evalendexpr;
 806     } else if ('&' == *s) {
 807         debugs(86, 6, "found AND");
 808         *endptr = s + 1;
 809         rv.valuetype = ESI_EXPR_AND;
 810         rv.precedence = 3;
 811         rv.eval = evaland;
 812     } else if ('|' == *s) {
 813         debugs(86, 6, "found OR");
 814         *endptr = s + 1;
 815         rv.valuetype = ESI_EXPR_OR;
 816         rv.precedence = 2;
 817         rv.eval = evalor;
 818     } else if ('=' == *s) {
 819         if ('=' == *(s + 1)) {
 820             debugs(86, 6, "found equals");
 821             *endptr = s + 2;
 822             rv.valuetype = ESI_EXPR_EQ;
 823             rv.precedence = 5;
 824             rv.eval = evalequals;
 825         } else {
 826             debugs(86, 1, "invalid expr '" << s << "'");
 827             *endptr = origs;
 828         }
 829     } else if ('<' == *s) {
 830         if ('=' == *(s + 1)) {
 831             debugs(86, 6, "found less-equals");
 832             *endptr = s + 2;
 833             rv.valuetype = ESI_EXPR_LESSEQ;
 834             rv.precedence = 5;
 835             rv.eval = evallesseq;
 836         } else {
 837             debugs(86, 6, "found less than");
 838             *endptr = s + 1;
 839             rv.valuetype = ESI_EXPR_LESS;
 840             rv.precedence = 5;
 841             rv.eval = evallessthan;
 842         }
 843     } else if ('>' == *s) {
 844         if ('=' == *(s + 1)) {
 845             debugs(86, 6, "found more-equals");
 846             *endptr = s + 2;
 847             rv.valuetype = ESI_EXPR_MOREEQ;
 848             rv.precedence = 5;
 849             rv.eval = evalmoreeq;
 850         } else {
 851             debugs(86, 6, "found more than");
 852             *endptr = s + 1;
 853             rv.valuetype = ESI_EXPR_MORE;
 854             rv.precedence = 5;
 855             rv.eval = evalmorethan;
 856         }
 857     } else if (!strncmp (s, "false", 5)) {
 858         debugs(86, 5, "getsymbol: found variable result 'false'");
 859         *endptr = s + 5;
 860         rv.valuetype = ESI_EXPR_EXPR;
 861         rv.valuestored = ESI_LITERAL_BOOL;
 862         rv.value.integral = 0;
 863         rv.precedence = 1;
 864         rv.eval = evalexpr;
 865     } else if (!strncmp (s, "true", 4)) {
 866         debugs(86, 5, "getsymbol: found variable result 'true'");
 867         *endptr = s + 4;
 868         rv.valuetype = ESI_EXPR_EXPR;
 869         rv.valuestored = ESI_LITERAL_BOOL;
 870         rv.value.integral = 1;
 871         rv.precedence = 1;
 872         rv.eval = evalexpr;
 873     } else {
 874         debugs(86, 1, "invalid expr '" << s << "'");
 875         *endptr = origs;
 876     }
 877
 878     return rv;
 879 }
 880
 881 void
 882 printliteral (stackmember s)
 883 {
 884     switch (s.valuestored) {
 885
 886     case ESI_LITERAL_INVALID:
 887         old_debug(86, 1) ( " Invalid " );
 888         break;
 889
 890     case ESI_LITERAL_FLOAT:
 891         old_debug(86,1) ("%f", s.value.floating);
 892         break;
 893
 894     case ESI_LITERAL_STRING:
 895         old_debug(86,1) ("'%s'", s.value.string);
 896         break;
 897
 898     case ESI_LITERAL_INT:
 899         old_debug(86,1) ("%d", s.value.integral);
 900         break;
 901
 902     case ESI_LITERAL_BOOL:
 903         old_debug(86,1)("%s",s.value.integral ? "true" : "false");
 904     }
 905 }
 906
 907 void
 908 printmember (stackmember s)
 909 {
 910     switch (s.valuetype) {
 911
 912     case ESI_EXPR_INVALID:
 913         old_debug(86,1) (" Invalid ");
 914         break;
 915
 916     case ESI_EXPR_LITERAL:
 917         printliteral (s);
 918         break;
 919
 920     case ESI_EXPR_EXPR:
 921         old_debug(86,1) ("%s", s.value.integral ? "true" : "false");
 922         break;
 923
 924     case ESI_EXPR_OR:
 925         old_debug(86,1) ("|");
 926         break;
 927
 928     case ESI_EXPR_AND:
 929         old_debug(86,1) ("&");
 930         break;
 931
 932     case ESI_EXPR_NOT:
 933         old_debug(86,1) ("!");
 934         break;
 935
 936     case ESI_EXPR_START:
 937         old_debug(86,1) ("(");
 938         break;
 939
 940     case ESI_EXPR_END:
 941         old_debug(86,1) (")");
 942         break;
 943
 944     case ESI_EXPR_EQ:
 945         old_debug(86,1) ("==");
 946         break;
 947
 948     case ESI_EXPR_NOTEQ:
 949         old_debug(86,1) ("!=");
 950         break;
 951
 952     case ESI_EXPR_LESS:
 953         old_debug(86,1) ("<");
 954         break;
 955
 956     case ESI_EXPR_LESSEQ:
 957         old_debug(86,1) ("<=");
 958         break;
 959
 960     case ESI_EXPR_MORE:
 961         old_debug(86,1) (">");
 962         break;
 963
 964     case ESI_EXPR_MOREEQ:
 965         old_debug(86,1) (">=");
 966         break;
 967     }
 968 }
 969
 970 void
 971 dumpstack (stackmember * stack, int depth)
 972 {
 973     int i;
 974
 975     for (i = 0; i < depth; ++i)
 976         printmember (stack[i]);
 977
 978     if (depth)
 979         old_debug(86,1) ("\n");
 980 }
 981
 982 int
 983 addmember (stackmember * stack, int *stackdepth, stackmember * candidate)
 984 {
 985     if (candidate->valuetype != ESI_EXPR_LITERAL && *stackdepth > 1) {
 986         /* !(!(a==b))) is why thats safe */
 987         /* strictly less than until we unwind */
 988
 989         if (candidate->precedence < stack[*stackdepth - 1].precedence ||
 990                 candidate->precedence < stack[*stackdepth - 2].precedence) {
 991             /* must be an operator */
 992
 993             if (stack[*stackdepth - 2].valuetype == ESI_EXPR_LITERAL ||
 994                     stack[*stackdepth - 2].valuetype == ESI_EXPR_INVALID ||
 995                     stack[*stackdepth - 2].eval (stack, stackdepth,
 996                                                  *stackdepth - 2, candidate)) {
 997                 /* cleanup candidate and stack */
 998                 dumpstack (stack, *stackdepth);
 999                 cleanmember (candidate);
1000                 debugs(86, 1, "invalid expression");
1001                 return 0;
1002             }
1003         } else {
1004             stack[(*stackdepth)++] = *candidate;
1005         }
1006     } else if (candidate->valuetype != ESI_EXPR_INVALID)
1007         stack[(*stackdepth)++] = *candidate;
1008
1009     return 1;
1010 }
1011
1012 int
1013 ESIExpression::Evaluate (char const *s)
1014 {
1015     stackmember stack[20];
1016     int stackdepth = 0;
1017     char const *end;
1018     PROF_start(esiExpressionEval);
1019
1020     while (*s) {
1021         stackmember candidate = getsymbol (s, &end);
1022
1023         if (candidate.valuetype != ESI_EXPR_INVALID) {
1024             assert (s != end);
1025
1026             if (!addmember (stack, &stackdepth, &candidate)) {
1027                 PROF_stop(esiExpressionEval);
1028                 return 0;
1029             }
1030
1031             s = end;
1032         } else {
1033             assert (s == end);
1034             debugs(86, 1, "failed parsing expression");
1035             PROF_stop(esiExpressionEval);
1036             return 0;
1037         }
1038     }
1039
1040     if (stackdepth > 1) {
1041         stackmember rv;
1042         rv.valuetype = ESI_EXPR_INVALID;
1043         rv.precedence = 0;
1044
1045         if (stack[stackdepth - 2].
1046                 eval (stack, &stackdepth, stackdepth - 2, &rv)) {
1047             /* special case - leading operator failed */
1048             debugs(86, 1, "invalid expression");
1049             PROF_stop(esiExpressionEval);
1050             return 0;
1051         }
1052     }
1053
1054     if (stackdepth == 0) {
1055         /* Empty expression - evaluate to false */
1056         PROF_stop(esiExpressionEval);
1057         return 0;
1058     }
1059
1060     /* if we hit here, we think we have a valid result */
1061     assert (stackdepth == 1);
1062
1063     assert (stack[0].valuetype == ESI_EXPR_EXPR);
1064
1065     PROF_stop(esiExpressionEval);
1066
1067     return stack[0].value.integral ? 1 : 0;
1068 }