-
Notifications
You must be signed in to change notification settings - Fork 91
/
BooleanParser.php
473 lines (427 loc) · 12.3 KB
/
BooleanParser.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
<?php
/*
* This file belongs to the package "TYPO3 Fluid".
* See LICENSE.txt that was shipped with this package.
*/
namespace TYPO3Fluid\Fluid\Core\Parser;
/**
* This BooleanParser helps to parse and evaluate boolean expressions.
* it's basically a recursive decent parser that uses a tokenizing regex
* to walk a given expression while evaluating each step along the way.
*
* For a basic recursive decent exampel check out:
* http://stackoverflow.com/questions/2093138/what-is-the-algorithm-for-parsing-expressions-in-infix-notation
*
* Parsingtree:
*
* evaluate/compile: start the whole cycle
* parseOrToken: takes care of "||" parts
* evaluateOr: evaluate the "||" part if found
* parseAndToken: take care of "&&" parts
* evaluateAnd: evaluate "&&" part if found
* parseCompareToken: takes care any comparisons "==,!=,>,<,..."
* evaluateCompare: evaluate the comparison if found
* parseNotToken: takes care of any "!" negations
* evaluateNot: evaluate the negation if found
* parseBracketToken: takes care of any '()' parts and restarts the cycle
* parseStringToken: takes care of any strings
* evaluateTerm: evaluate terms from true/false/numeric/context
*/
class BooleanParser
{
/**
* List of comparators to check in the parseCompareToken if the current
* part of the expression is a comparator and needs to be compared
*/
public const COMPARATORS = '==,===,!==,!=,<=,>=,<,>,%';
/**
* Regex to parse a expression into tokens
*/
public const TOKENREGEX = '/
\s*(
\\\\\'
|
\\"
|
[\'"]
|
[_A-Za-z0-9\.\{\}\-\\\\]+
|
\=\=\=
|
\=\=
|
!\=\=
|
!\=
|
<\=
|
>\=
|
<
|
>
|
%
|
\|\|
|
[aA][nN][dD]
|
&&
|
[oO][rR]
|
.?
)\s*
/xsu';
/**
* Cursor that contains a integer value pointing to the location inside the
* expression string that is used by the peek function to look for the part of
* the expression that needs to be focused on next. This cursor is changed
* by the consume method, by "consuming" part of the expression.
*
* @var int
*/
protected $cursor = 0;
/**
* Expression that is parsed through peek and consume methods
*
* @var string
*/
protected $expression;
/**
* Context containing all variables that are references in the expression
*
* @var array
*/
protected $context;
/**
* Switch to enable compiling
*
* @var bool
*/
protected $compileToCode = false;
/**
* Evaluate a expression to a boolean
*
* @param string $expression to be parsed
* @param array $context containing variables that can be used in the expression
* @return bool
*/
public function evaluate($expression, $context)
{
$this->context = $context;
$this->expression = $expression;
$this->cursor = 0;
return $this->parseOrToken();
}
/**
* Parse and compile an expression into an php equivalent
*
* @param string $expression to be parsed
* @return string
*/
public function compile($expression)
{
$this->expression = $expression;
$this->cursor = 0;
$this->compileToCode = true;
return $this->parseOrToken();
}
/**
* The part of the expression we're currently focusing on based on the
* tokenizing regex offset by the internally tracked cursor.
*
* @param bool $includeWhitespace return surrounding whitespace with token
* @return string
*/
protected function peek($includeWhitespace = false)
{
preg_match(static::TOKENREGEX, mb_substr($this->expression, $this->cursor), $matches);
if ($includeWhitespace === true) {
return $matches[0];
}
return $matches[1];
}
/**
* Consume part of the current expression by setting the internal cursor
* to the position of the string in the expression and it's length
*
* @param string $string
*/
protected function consume($string)
{
if (mb_strlen($string) === 0) {
return;
}
$this->cursor = mb_strpos($this->expression, $string, $this->cursor) + mb_strlen($string);
}
/**
* Passes the torch down to the next deeper parsing leve (and)
* and checks then if there's a "or" expression that needs to be handled
*
* @return mixed
*/
protected function parseOrToken()
{
$x = $this->parseAndToken();
while (($token = $this->peek()) && in_array(strtolower($token), ['||', 'or'])) {
$this->consume($token);
$y = $this->parseAndToken();
if ($this->compileToCode === true) {
$x = '(' . $x . ' || ' . $y . ')';
continue;
}
$x = $this->evaluateOr($x, $y);
}
return $x;
}
/**
* Passes the torch down to the next deeper parsing leve (compare)
* and checks then if there's a "and" expression that needs to be handled
*
* @return mixed
*/
protected function parseAndToken()
{
$x = $this->parseCompareToken();
while (($token = $this->peek()) && in_array(strtolower($token), ['&&', 'and'])) {
$this->consume($token);
$y = $this->parseCompareToken();
if ($this->compileToCode === true) {
$x = '(' . $x . ' && ' . $y . ')';
continue;
}
$x = $this->evaluateAnd($x, $y);
}
return $x;
}
/**
* Passes the torch down to the next deeper parsing leven (not)
* and checks then if there's a "compare" expression that needs to be handled
*
* @return mixed
*/
protected function parseCompareToken()
{
$x = $this->parseNotToken();
while (in_array($comparator = $this->peek(), explode(',', static::COMPARATORS))) {
$this->consume($comparator);
$y = $this->parseNotToken();
$x = $this->evaluateCompare($x, $y, $comparator);
}
return $x;
}
/**
* Check if we have encountered an not expression or pass the torch down
* to the simpleToken method.
*
* @return mixed
*/
protected function parseNotToken()
{
if ($this->peek() === '!') {
$this->consume('!');
$x = $this->parseNotToken();
if ($this->compileToCode === true) {
return '!(' . $x . ')';
}
return $this->evaluateNot($x);
}
return $this->parseBracketToken();
}
/**
* Takes care of restarting the whole parsing loop if it encounters a "(" or ")"
* token or pass the torch down to the parseStringToken method
*
* @return mixed
*/
protected function parseBracketToken()
{
$t = $this->peek();
if ($t === '(') {
$this->consume('(');
$result = $this->parseOrToken();
$this->consume(')');
return $result;
}
return $this->parseStringToken();
}
/**
* Takes care of consuming pure string including whitespace or passes the torch
* down to the parseTermToken method
*
* @return mixed
*/
protected function parseStringToken()
{
$t = $this->peek();
if ($t === '\'' || $t === '"') {
$stringIdentifier = $t;
$string = $stringIdentifier;
$this->consume($stringIdentifier);
while (trim($t = $this->peek(true)) !== $stringIdentifier) {
$this->consume($t);
$string .= $t;
if ($t === '') {
throw new Exception(sprintf('Closing string token expected in boolean expression "%s".', $this->expression), 1697479462);
}
}
$this->consume($stringIdentifier);
$string .= $stringIdentifier;
if ($this->compileToCode === true) {
return $string;
}
return $this->evaluateTerm($string, $this->context);
}
return $this->parseTermToken();
}
/**
* Takes care of restarting the whole parsing loop if it encounters a "(" or ")"
* token, consumes a pure string including whitespace or passes the torch
* down to the evaluateTerm method
*
* @return mixed
*/
protected function parseTermToken()
{
$t = $this->peek();
$this->consume($t);
return $this->evaluateTerm($t, $this->context);
}
/**
* Evaluate an "and" comparison
*
* @param mixed $x
* @param mixed $y
* @return bool
*/
protected function evaluateAnd($x, $y)
{
return $x && $y;
}
/**
* Evaluate an "or" comparison
*
* @param mixed $x
* @param mixed $y
* @return bool
*/
protected function evaluateOr($x, $y)
{
return $x || $y;
}
/**
* Evaluate an "not" comparison
*
* @param mixed $x
* @return bool|string
*/
protected function evaluateNot($x)
{
return !$x;
}
/**
* Compare two variables based on a specified comparator
*
* @param mixed $x
* @param mixed $y
* @param string $comparator
* @return bool|string
*/
protected function evaluateCompare($x, $y, $comparator)
{
// enfore strong comparison for comparing two objects
if ($comparator === '==' && is_object($x) && is_object($y)) {
$comparator = '===';
}
if ($comparator === '!=' && is_object($x) && is_object($y)) {
$comparator = '!==';
}
if ($this->compileToCode === true) {
return sprintf('(%s %s %s)', $x, $comparator, $y);
}
switch ($comparator) {
case '==':
$x = ($x == $y);
break;
case '===':
$x = ($x === $y);
break;
case '!=':
$x = ($x != $y);
break;
case '!==':
$x = ($x !== $y);
break;
case '<=':
$x = ($x <= $y);
break;
case '>=':
$x = ($x >= $y);
break;
case '<':
$x = ($x < $y);
break;
case '>':
$x = ($x > $y);
break;
case '%':
$x = ($x % $y);
break;
}
return $x;
}
/**
* Takes care of fetching terms from the context, converting to float/int,
* converting true/false keywords into boolean or trim the final string of
* quotation marks
*
* @param string $x
* @param array $context
* @return mixed
*/
protected function evaluateTerm($x, $context)
{
if (isset($context[$x]) || (mb_strpos($x, '{') === 0 && mb_substr($x, -1) === '}')) {
if ($this->compileToCode === true) {
return BooleanParser::class . '::convertNodeToBoolean($context["' . trim($x, '{}') . '"])';
}
return self::convertNodeToBoolean($context[trim($x, '{}')]);
}
if (is_numeric($x)) {
if ($this->compileToCode === true) {
return $x;
}
if (mb_strpos($x, '.') !== false) {
return (float)$x;
}
return (int)$x;
}
if (trim(strtolower($x)) === 'true') {
if ($this->compileToCode === true) {
return 'TRUE';
}
return true;
}
if (trim(strtolower($x)) === 'false') {
if ($this->compileToCode === true) {
return 'FALSE';
}
return false;
}
if ($this->compileToCode === true) {
return '"' . trim($x, '\'"') . '"';
}
return trim($x, '\'"');
}
public static function convertNodeToBoolean($value)
{
if ($value instanceof \Countable) {
return count($value) > 0;
}
return $value;
}
}