src/esi/Expression.cc

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