src/esi/Expression.cc

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