]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/esi/Expression.cc
8a1d3e95c43b903b31b5a8d10aedd321a3fb4b16
2 * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 86 ESI processing */
13 #include "esi/Expression.h"
14 #include "profiler/Profiler.h"
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
24 * Start of expression has 5 precedence,
25 * end of expression has 0 precedence
26 * literal has 1 as does expression results
30 * == != < > <= >= has 5
35 typedef struct _stackmember stackmember
;
37 typedef int evaluate(stackmember
* stack
, int *depth
, int whereAmI
,
38 stackmember
* candidate
);
54 ESI_EXPR_EXPR
/* the result of an expr PRI 1 */
72 literalhint valuestored
;
77 static void cleanmember(stackmember
*);
78 static void stackpop(stackmember
* s
, int *depth
);
81 cleanmember(stackmember
* s
)
83 if (s
->valuetype
== ESI_EXPR_LITERAL
84 && s
->valuestored
== ESI_LITERAL_STRING
) {
85 safe_free(s
->value
.string
);
86 s
->value
.string
= NULL
;
92 stackpop(stackmember
* s
, int *depth
)
97 cleanmember(&s
[*depth
]);
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
);
120 /* -2 = failed to compate
126 membercompare(stackmember a
, stackmember b
)
128 /* we can compare: sub expressions to sub expressions ,
129 * literals to literals
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
)))
137 if (a
.valuetype
== ESI_EXPR_EXPR
) {
138 if (a
.value
.integral
== b
.value
.integral
)
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
);
154 /* TODO: numeric to string conversion ? */
155 debugs(86, DBG_IMPORTANT
, "strcmp with non-string");
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)
162 else if (a
.value
.floating
< b
.value
.integral
)
166 } else if (b
.valuestored
== ESI_LITERAL_FLOAT
) {
167 if (a
.value
.floating
== b
.value
.floating
)
169 else if (a
.value
.floating
< b
.value
.floating
)
174 /* TODO: attempt numeric converson again? */
175 debugs(86, DBG_IMPORTANT
, "floatcomp with non float or int");
178 } else if (a
.valuestored
== ESI_LITERAL_INT
) {
179 if (b
.valuestored
== ESI_LITERAL_INT
) {
180 if (a
.value
.integral
== b
.value
.integral
)
182 else if (a
.value
.integral
< b
.value
.integral
)
186 } else if (b
.valuestored
== ESI_LITERAL_FLOAT
) {
187 if (fabs(a
.value
.integral
- b
.value
.floating
) < 0.00001)
189 else if (a
.value
.integral
< b
.value
.floating
)
194 /* TODO: attempt numeric converson again? */
195 debugs(86, DBG_IMPORTANT
, "intcomp vs non float non int");
203 /* return 0 on success, 1 on failure */
205 evalnegate(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
207 if (whereAmI
!= *depth
- 2)
211 if (stack
[whereAmI
+ 1].valuetype
!= ESI_EXPR_EXPR
)
212 /* invalid operand */
218 stack
[whereAmI
] = stack
[(*depth
)];
220 cleanmember(candidate
);
222 if (stack
[whereAmI
].value
.integral
== 1)
223 stack
[whereAmI
].value
.integral
= 0;
225 stack
[whereAmI
].value
.integral
= 1;
231 evalliteral(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
233 debugs(86, DBG_IMPORTANT
, "attempt to evaluate a literal");
234 /* literals can't be evaluated */
239 evalexpr(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
241 debugs(86, DBG_IMPORTANT
, "attempt to evaluate a sub-expression result");
242 /* sub-scpr's can't be evaluated */
247 evalor(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
253 /* Not enough operands */
256 if (whereAmI
!= *depth
- 2)
260 if (stack
[whereAmI
+ 1].valuetype
!= ESI_EXPR_EXPR
||
261 stack
[whereAmI
- 1].valuetype
!= ESI_EXPR_EXPR
)
262 /* invalid operand */
265 rv
= stack
[whereAmI
- 1].value
.integral
|| stack
[whereAmI
+ 1].value
.integral
;
267 stackpop(stack
, depth
); /* arg rhs */
269 stackpop(stack
, depth
); /* me */
271 stackpop(stack
, depth
); /* arg lhs */
273 srv
.valuetype
= ESI_EXPR_EXPR
;
275 srv
.eval
= evalliteral
;
277 srv
.valuestored
= ESI_LITERAL_BOOL
;
279 srv
.value
.integral
= rv
? 1 : 0;
283 stack
[(*depth
)++] = srv
;
285 /* we're out of way, try adding now */
286 if (!addmember(stack
, depth
, candidate
))
287 /* Something wrong upstream */
294 evaland(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
300 /* Not enough operands */
303 if (whereAmI
!= *depth
- 2)
307 if (stack
[whereAmI
+ 1].valuetype
!= ESI_EXPR_EXPR
||
308 stack
[whereAmI
- 1].valuetype
!= ESI_EXPR_EXPR
)
309 /* invalid operand */
312 rv
= stack
[whereAmI
- 1].value
.integral
&& stack
[whereAmI
+ 1].value
.integral
;
314 stackpop(stack
, depth
); /* arg rhs */
316 stackpop(stack
, depth
); /* me */
318 stackpop(stack
, depth
); /* arg lhs */
320 srv
.valuetype
= ESI_EXPR_EXPR
;
324 srv
.valuestored
= ESI_LITERAL_BOOL
;
326 srv
.value
.integral
= rv
? 1 : 0;
330 stack
[(*depth
)++] = srv
;
332 /* we're out of way, try adding now */
333 if (!addmember(stack
, depth
, candidate
))
334 /* Something wrong upstream */
341 evallesseq(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
347 /* Not enough operands */
350 if (whereAmI
!= *depth
- 2)
354 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
357 /* invalid comparison */
360 stackpop(stack
, depth
); /* arg rhs */
362 stackpop(stack
, depth
); /* me */
364 stackpop(stack
, depth
); /* arg lhs */
366 srv
.valuetype
= ESI_EXPR_EXPR
;
370 srv
.valuestored
= ESI_LITERAL_BOOL
;
372 srv
.value
.integral
= rv
<= 0 ? 1 : 0;
376 stack
[(*depth
)++] = srv
;
378 /* we're out of way, try adding now */
379 if (!addmember(stack
, depth
, candidate
))
380 /* Something wrong upstream */
383 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
389 evallessthan(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
395 /* Not enough operands */
398 if (whereAmI
!= *depth
- 2)
402 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
405 /* invalid comparison */
408 stackpop(stack
, depth
); /* arg rhs */
410 stackpop(stack
, depth
); /* me */
412 stackpop(stack
, depth
); /* arg lhs */
414 srv
.valuetype
= ESI_EXPR_EXPR
;
418 srv
.valuestored
= ESI_LITERAL_BOOL
;
420 srv
.value
.integral
= rv
< 0 ? 1 : 0;
424 stack
[(*depth
)++] = srv
;
426 /* we're out of way, try adding now */
427 if (!addmember(stack
, depth
, candidate
))
428 /* Something wrong upstream */
431 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
437 evalmoreeq(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
443 /* Not enough operands */
446 if (whereAmI
!= *depth
- 2)
450 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
453 /* invalid comparison */
456 stackpop(stack
, depth
); /* arg rhs */
458 stackpop(stack
, depth
); /* me */
460 stackpop(stack
, depth
); /* arg lhs */
462 srv
.valuetype
= ESI_EXPR_EXPR
;
466 srv
.valuestored
= ESI_LITERAL_BOOL
;
468 srv
.value
.integral
= rv
>= 0 ? 1 : 0;
472 stack
[(*depth
)++] = srv
;
474 /* we're out of way, try adding now */
475 if (!addmember(stack
, depth
, candidate
))
476 /* Something wrong upstream */
479 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
485 evalmorethan(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
491 /* Not enough operands */
494 if (whereAmI
!= *depth
- 2)
498 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
501 /* invalid comparison */
504 stackpop(stack
, depth
); /* arg rhs */
506 stackpop(stack
, depth
); /* me */
508 stackpop(stack
, depth
); /* arg lhs */
510 srv
.valuetype
= ESI_EXPR_EXPR
;
514 srv
.valuestored
= ESI_LITERAL_BOOL
;
516 srv
.value
.integral
= rv
> 0 ? 1 : 0;
520 stack
[(*depth
)++] = srv
;
522 /* we're out of way, try adding now */
523 if (!addmember(stack
, depth
, candidate
))
524 /* Something wrong upstream */
527 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
533 evalequals(stackmember
* stack
, int *depth
, int whereAmI
,
534 stackmember
* candidate
)
540 /* Not enough operands */
543 if (whereAmI
!= *depth
- 2)
547 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
550 /* invalid comparison */
553 stackpop(stack
, depth
); /* arg rhs */
555 stackpop(stack
, depth
); /* me */
557 stackpop(stack
, depth
); /* arg lhs */
559 srv
.valuetype
= ESI_EXPR_EXPR
;
563 srv
.valuestored
= ESI_LITERAL_BOOL
;
565 srv
.value
.integral
= rv
? 0 : 1;
569 stack
[(*depth
)++] = srv
;
571 /* we're out of way, try adding now */
572 if (!addmember(stack
, depth
, candidate
))
573 /* Something wrong upstream */
576 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
581 evalnotequals(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
587 /* Not enough operands */
590 if (whereAmI
!= *depth
- 2)
594 rv
= membercompare(stack
[whereAmI
- 1], stack
[whereAmI
+ 1]);
597 /* invalid comparison */
600 stackpop(stack
, depth
); /* arg rhs */
602 stackpop(stack
, depth
); /* me */
604 stackpop(stack
, depth
); /* arg lhs */
606 srv
.valuetype
= ESI_EXPR_EXPR
;
610 srv
.valuestored
= ESI_LITERAL_BOOL
;
612 srv
.value
.integral
= rv
? 1 : 0;
616 stack
[(*depth
)++] = srv
;
618 /* we're out of way, try adding now */
619 if (!addmember(stack
, depth
, candidate
))
620 /* Something wrong upstream */
623 /* debugs(86, DBG_IMPORTANT, "?= " << srv.value.integral << " "); */
628 evalstartexpr(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
630 /* debugs(86, DBG_IMPORTANT, "?("); */
632 if (whereAmI
!= *depth
- 2)
636 /* Only valid when RHS is an end bracket */
637 if (candidate
->valuetype
!= ESI_EXPR_END
)
642 stack
[whereAmI
] = stack
[(*depth
)];
644 cleanmember(candidate
);
650 evalendexpr(stackmember
* stack
, int *depth
, int whereAmI
, stackmember
* candidate
)
652 /* Can't evaluate ) brackets */
666 getsymbol(const char *s
, char const **endptr
)
670 char const *origs
= s
;
671 /* trim whitespace */
673 rv
.eval
= NULL
; /* A literal */
674 rv
.valuetype
= ESI_EXPR_INVALID
;
675 rv
.valuestored
= ESI_LITERAL_INVALID
;
676 rv
.precedence
= 1; /* A literal */
678 if (('0' <= *s
&& *s
<= '9') || *s
== '-') {
679 size_t length
= strspn(s
, "0123456789.");
682 if ((point
= strchr(s
, '.')) && point
- s
< (ssize_t
)length
) {
684 errno
=0; /* reset errno */
685 rv
.value
.floating
= strtod(s
, &end
);
687 if (s
== end
|| errno
) {
688 /* Couldn't convert to float */
689 debugs(86, DBG_IMPORTANT
, "failed to convert '" << s
<< "' to float ");
692 debugs(86,6, "found " << rv
.value
.floating
<< " of length " << end
- s
);
694 rv
.eval
= evalliteral
;
695 rv
.valuestored
= ESI_LITERAL_FLOAT
;
696 rv
.valuetype
= ESI_EXPR_LITERAL
;
701 errno
=0; /* reset errno */
702 rv
.value
.integral
= strtol(s
, &end
, 0);
704 if (s
== end
|| errno
) {
705 /* Couldn't convert to int */
706 debugs(86, DBG_IMPORTANT
, "failed to convert '" << s
<< "' to int ");
709 debugs(86,6, "found " << rv
.value
.integral
<< " of length " << end
- s
);
711 rv
.eval
= evalliteral
;
712 rv
.valuestored
= ESI_LITERAL_INT
;
713 rv
.valuetype
= ESI_EXPR_LITERAL
;
717 } else if ('!' == *s
) {
718 if ('=' == *(s
+ 1)) {
719 debugs(86, 6, "found !=");
721 rv
.eval
= evalnotequals
;
722 rv
.valuetype
= ESI_EXPR_NOTEQ
;
725 debugs(86, 6, "found !");
727 rv
.valuetype
= ESI_EXPR_NOT
;
729 rv
.eval
= evalnegate
;
731 } else if ('\'' == *s
) {
732 char const *t
= s
+ 1;
733 debugs(86, 6, "found \'");
735 while (*t
!= '\'' && *t
)
739 debugs(86, DBG_IMPORTANT
, "missing end \' in '" << s
<< "'");
743 /* Special case for zero length strings */
746 rv
.value
.string
= xstrndup(s
+ 1, t
- s
- 1);
748 rv
.value
.string
= static_cast<char *>(xcalloc(1,1));
750 rv
.eval
= evalliteral
;
752 rv
.valuestored
= ESI_LITERAL_STRING
;
754 rv
.valuetype
= ESI_EXPR_LITERAL
;
758 debugs(86, 6, "found string '" << rv
.value
.string
<< "'");
760 } else if ('(' == *s
) {
761 debugs(86, 6, "found subexpr start");
763 rv
.valuetype
= ESI_EXPR_START
;
765 rv
.eval
= evalstartexpr
;
766 } else if (')' == *s
) {
767 debugs(86, 6, "found subexpr end");
769 rv
.valuetype
= ESI_EXPR_END
;
771 rv
.eval
= evalendexpr
;
772 } else if ('&' == *s
) {
773 debugs(86, 6, "found AND");
775 rv
.valuetype
= ESI_EXPR_AND
;
778 } else if ('|' == *s
) {
779 debugs(86, 6, "found OR");
781 rv
.valuetype
= ESI_EXPR_OR
;
784 } else if ('=' == *s
) {
785 if ('=' == *(s
+ 1)) {
786 debugs(86, 6, "found equals");
788 rv
.valuetype
= ESI_EXPR_EQ
;
790 rv
.eval
= evalequals
;
792 debugs(86, DBG_IMPORTANT
, "invalid expr '" << s
<< "'");
795 } else if ('<' == *s
) {
796 if ('=' == *(s
+ 1)) {
797 debugs(86, 6, "found less-equals");
799 rv
.valuetype
= ESI_EXPR_LESSEQ
;
801 rv
.eval
= evallesseq
;
803 debugs(86, 6, "found less than");
805 rv
.valuetype
= ESI_EXPR_LESS
;
807 rv
.eval
= evallessthan
;
809 } else if ('>' == *s
) {
810 if ('=' == *(s
+ 1)) {
811 debugs(86, 6, "found more-equals");
813 rv
.valuetype
= ESI_EXPR_MOREEQ
;
815 rv
.eval
= evalmoreeq
;
817 debugs(86, 6, "found more than");
819 rv
.valuetype
= ESI_EXPR_MORE
;
821 rv
.eval
= evalmorethan
;
823 } else if (!strncmp(s
, "false", 5)) {
824 debugs(86, 5, "getsymbol: found variable result 'false'");
826 rv
.valuetype
= ESI_EXPR_EXPR
;
827 rv
.valuestored
= ESI_LITERAL_BOOL
;
828 rv
.value
.integral
= 0;
831 } else if (!strncmp(s
, "true", 4)) {
832 debugs(86, 5, "getsymbol: found variable result 'true'");
834 rv
.valuetype
= ESI_EXPR_EXPR
;
835 rv
.valuestored
= ESI_LITERAL_BOOL
;
836 rv
.value
.integral
= 1;
840 debugs(86, DBG_IMPORTANT
, "invalid expr '" << s
<< "'");
848 printLiteral(std::ostream
&os
, const stackmember
&s
)
850 switch (s
.valuestored
) {
852 case ESI_LITERAL_INVALID
:
856 case ESI_LITERAL_FLOAT
:
857 os
<< s
.value
.floating
;
860 case ESI_LITERAL_STRING
:
861 os
<< '\'' << s
.value
.string
<< '\'';
864 case ESI_LITERAL_INT
:
865 os
<< s
.value
.integral
;
868 case ESI_LITERAL_BOOL
:
869 os
<< (s
.value
.integral
? "true" : "false");
873 static std::ostream
&
874 operator <<(std::ostream
&os
, const stackmember
&s
)
876 switch (s
.valuetype
) {
878 case ESI_EXPR_INVALID
:
882 case ESI_EXPR_LITERAL
:
887 os
<< (s
.value
.integral
? "true" : "false");
922 case ESI_EXPR_LESSEQ
:
930 case ESI_EXPR_MOREEQ
:
939 dumpstack(stackmember
* stack
, int depth
)
942 std::ostringstream buf
;
943 for (int i
= 0; i
< depth
; ++i
)
945 debugs(86,1, buf
.str());
950 addmember(stackmember
* stack
, int *stackdepth
, stackmember
* candidate
)
952 if (candidate
->valuetype
!= ESI_EXPR_LITERAL
&& *stackdepth
> 1) {
953 /* !(!(a==b))) is why thats safe */
954 /* strictly less than until we unwind */
956 if (candidate
->precedence
< stack
[*stackdepth
- 1].precedence
||
957 candidate
->precedence
< stack
[*stackdepth
- 2].precedence
) {
958 /* must be an operator */
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");
971 stack
[(*stackdepth
)++] = *candidate
;
973 } else if (candidate
->valuetype
!= ESI_EXPR_INVALID
)
974 stack
[(*stackdepth
)++] = *candidate
;
980 ESIExpression::Evaluate(char const *s
)
982 stackmember stack
[20];
985 PROF_start(esiExpressionEval
);
988 stackmember candidate
= getsymbol(s
, &end
);
990 if (candidate
.valuetype
!= ESI_EXPR_INVALID
) {
993 if (!addmember(stack
, &stackdepth
, &candidate
)) {
994 PROF_stop(esiExpressionEval
);
1001 debugs(86, DBG_IMPORTANT
, "failed parsing expression");
1002 PROF_stop(esiExpressionEval
);
1007 if (stackdepth
> 1) {
1009 rv
.valuetype
= ESI_EXPR_INVALID
;
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
);
1021 if (stackdepth
== 0) {
1022 /* Empty expression - evaluate to false */
1023 PROF_stop(esiExpressionEval
);
1027 /* if we hit here, we think we have a valid result */
1028 assert(stackdepth
== 1);
1030 assert(stack
[0].valuetype
== ESI_EXPR_EXPR
);
1032 PROF_stop(esiExpressionEval
);
1034 return stack
[0].value
.integral
? 1 : 0;