src/esi/Expression.cc

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