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