Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
Total | |
98.40% |
369 / 375 |
|
0.00% |
0 / 2 |
CRAP | |
0.00% |
0 / 1 |
ExprParser | |
98.40% |
369 / 375 |
|
0.00% |
0 / 2 |
142 | |
0.00% |
0 / 1 |
doExpression | |
97.26% |
142 / 146 |
|
0.00% |
0 / 1 |
54 | |||
doOperation | |
99.13% |
227 / 229 |
|
0.00% |
0 / 1 |
88 |
1 | <?php |
2 | /** |
3 | * This program is free software; you can redistribute it and/or modify |
4 | * it under the terms of the GNU General Public License as published by |
5 | * the Free Software Foundation; either version 2 of the License, or |
6 | * (at your option) any later version. |
7 | * |
8 | * This program is distributed in the hope that it will be useful, |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
11 | * GNU General Public License for more details. |
12 | * |
13 | * You should have received a copy of the GNU General Public License along |
14 | * with this program; if not, write to the Free Software Foundation, Inc., |
15 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
16 | * |
17 | */ |
18 | |
19 | namespace MediaWiki\Extension\ParserFunctions; |
20 | |
21 | use UtfNormal\Validator; |
22 | |
23 | class ExprParser { |
24 | |
25 | // Character classes |
26 | private const EXPR_WHITE_CLASS = " \t\r\n"; |
27 | private const EXPR_NUMBER_CLASS = '0123456789.'; |
28 | |
29 | // Token types |
30 | private const EXPR_WHITE = 1; |
31 | private const EXPR_NUMBER = 2; |
32 | private const EXPR_NEGATIVE = 3; |
33 | private const EXPR_POSITIVE = 4; |
34 | private const EXPR_PLUS = 5; |
35 | private const EXPR_MINUS = 6; |
36 | private const EXPR_TIMES = 7; |
37 | private const EXPR_DIVIDE = 8; |
38 | private const EXPR_MOD = 9; |
39 | private const EXPR_OPEN = 10; |
40 | private const EXPR_CLOSE = 11; |
41 | private const EXPR_AND = 12; |
42 | private const EXPR_OR = 13; |
43 | private const EXPR_NOT = 14; |
44 | private const EXPR_EQUALITY = 15; |
45 | private const EXPR_LESS = 16; |
46 | private const EXPR_GREATER = 17; |
47 | private const EXPR_LESSEQ = 18; |
48 | private const EXPR_GREATEREQ = 19; |
49 | private const EXPR_NOTEQ = 20; |
50 | private const EXPR_ROUND = 21; |
51 | private const EXPR_EXPONENT = 22; |
52 | private const EXPR_SINE = 23; |
53 | private const EXPR_COSINE = 24; |
54 | private const EXPR_TANGENS = 25; |
55 | private const EXPR_ARCSINE = 26; |
56 | private const EXPR_ARCCOS = 27; |
57 | private const EXPR_ARCTAN = 28; |
58 | private const EXPR_EXP = 29; |
59 | private const EXPR_LN = 30; |
60 | private const EXPR_ABS = 31; |
61 | private const EXPR_FLOOR = 32; |
62 | private const EXPR_TRUNC = 33; |
63 | private const EXPR_CEIL = 34; |
64 | private const EXPR_POW = 35; |
65 | private const EXPR_PI = 36; |
66 | private const EXPR_FMOD = 37; |
67 | private const EXPR_SQRT = 38; |
68 | |
69 | private const MAX_STACK_SIZE = 100; |
70 | |
71 | private const PRECEDENCE = [ |
72 | self::EXPR_NEGATIVE => 10, |
73 | self::EXPR_POSITIVE => 10, |
74 | self::EXPR_EXPONENT => 10, |
75 | self::EXPR_SINE => 9, |
76 | self::EXPR_COSINE => 9, |
77 | self::EXPR_TANGENS => 9, |
78 | self::EXPR_ARCSINE => 9, |
79 | self::EXPR_ARCCOS => 9, |
80 | self::EXPR_ARCTAN => 9, |
81 | self::EXPR_EXP => 9, |
82 | self::EXPR_LN => 9, |
83 | self::EXPR_ABS => 9, |
84 | self::EXPR_FLOOR => 9, |
85 | self::EXPR_TRUNC => 9, |
86 | self::EXPR_CEIL => 9, |
87 | self::EXPR_NOT => 9, |
88 | self::EXPR_SQRT => 9, |
89 | self::EXPR_POW => 8, |
90 | self::EXPR_TIMES => 7, |
91 | self::EXPR_DIVIDE => 7, |
92 | self::EXPR_MOD => 7, |
93 | self::EXPR_FMOD => 7, |
94 | self::EXPR_PLUS => 6, |
95 | self::EXPR_MINUS => 6, |
96 | self::EXPR_ROUND => 5, |
97 | self::EXPR_EQUALITY => 4, |
98 | self::EXPR_LESS => 4, |
99 | self::EXPR_GREATER => 4, |
100 | self::EXPR_LESSEQ => 4, |
101 | self::EXPR_GREATEREQ => 4, |
102 | self::EXPR_NOTEQ => 4, |
103 | self::EXPR_AND => 3, |
104 | self::EXPR_OR => 2, |
105 | self::EXPR_PI => 0, |
106 | self::EXPR_OPEN => -1, |
107 | self::EXPR_CLOSE => -1, |
108 | ]; |
109 | |
110 | private const NAMES = [ |
111 | self::EXPR_NEGATIVE => '-', |
112 | self::EXPR_POSITIVE => '+', |
113 | self::EXPR_NOT => 'not', |
114 | self::EXPR_TIMES => '*', |
115 | self::EXPR_DIVIDE => '/', |
116 | self::EXPR_MOD => 'mod', |
117 | self::EXPR_FMOD => 'fmod', |
118 | self::EXPR_PLUS => '+', |
119 | self::EXPR_MINUS => '-', |
120 | self::EXPR_ROUND => 'round', |
121 | self::EXPR_EQUALITY => '=', |
122 | self::EXPR_LESS => '<', |
123 | self::EXPR_GREATER => '>', |
124 | self::EXPR_LESSEQ => '<=', |
125 | self::EXPR_GREATEREQ => '>=', |
126 | self::EXPR_NOTEQ => '<>', |
127 | self::EXPR_AND => 'and', |
128 | self::EXPR_OR => 'or', |
129 | self::EXPR_EXPONENT => 'e', |
130 | self::EXPR_SINE => 'sin', |
131 | self::EXPR_COSINE => 'cos', |
132 | self::EXPR_TANGENS => 'tan', |
133 | self::EXPR_ARCSINE => 'asin', |
134 | self::EXPR_ARCCOS => 'acos', |
135 | self::EXPR_ARCTAN => 'atan', |
136 | self::EXPR_LN => 'ln', |
137 | self::EXPR_EXP => 'exp', |
138 | self::EXPR_ABS => 'abs', |
139 | self::EXPR_FLOOR => 'floor', |
140 | self::EXPR_TRUNC => 'trunc', |
141 | self::EXPR_CEIL => 'ceil', |
142 | self::EXPR_POW => '^', |
143 | self::EXPR_PI => 'pi', |
144 | self::EXPR_SQRT => 'sqrt', |
145 | ]; |
146 | |
147 | private const WORDS = [ |
148 | 'mod' => self::EXPR_MOD, |
149 | 'fmod' => self::EXPR_FMOD, |
150 | 'and' => self::EXPR_AND, |
151 | 'or' => self::EXPR_OR, |
152 | 'not' => self::EXPR_NOT, |
153 | 'round' => self::EXPR_ROUND, |
154 | 'div' => self::EXPR_DIVIDE, |
155 | 'e' => self::EXPR_EXPONENT, |
156 | 'sin' => self::EXPR_SINE, |
157 | 'cos' => self::EXPR_COSINE, |
158 | 'tan' => self::EXPR_TANGENS, |
159 | 'asin' => self::EXPR_ARCSINE, |
160 | 'acos' => self::EXPR_ARCCOS, |
161 | 'atan' => self::EXPR_ARCTAN, |
162 | 'exp' => self::EXPR_EXP, |
163 | 'ln' => self::EXPR_LN, |
164 | 'abs' => self::EXPR_ABS, |
165 | 'trunc' => self::EXPR_TRUNC, |
166 | 'floor' => self::EXPR_FLOOR, |
167 | 'ceil' => self::EXPR_CEIL, |
168 | 'pi' => self::EXPR_PI, |
169 | 'sqrt' => self::EXPR_SQRT, |
170 | ]; |
171 | |
172 | /** |
173 | * Evaluate a mathematical expression |
174 | * |
175 | * The algorithm here is based on the infix to RPN algorithm given in |
176 | * http://montcs.bloomu.edu/~bobmon/Information/RPN/infix2rpn.shtml |
177 | * It's essentially the same as Dijkstra's shunting yard algorithm. |
178 | * @param string $expr |
179 | * @return string |
180 | * @throws ExprError |
181 | */ |
182 | public function doExpression( $expr ) { |
183 | $operands = []; |
184 | $operators = []; |
185 | |
186 | # Unescape inequality operators |
187 | $expr = strtr( $expr, [ '<' => '<', '>' => '>', |
188 | '−' => '-', '−' => '-' ] ); |
189 | |
190 | $p = 0; |
191 | $end = strlen( $expr ); |
192 | $expecting = 'expression'; |
193 | $name = ''; |
194 | |
195 | while ( $p < $end ) { |
196 | if ( count( $operands ) > self::MAX_STACK_SIZE || count( $operators ) > self::MAX_STACK_SIZE ) { |
197 | throw new ExprError( 'stack_exhausted' ); |
198 | } |
199 | $char = $expr[$p]; |
200 | $char2 = substr( $expr, $p, 2 ); |
201 | |
202 | // Mega if-elseif-else construct |
203 | // Only binary operators fall through for processing at the bottom, the rest |
204 | // finish their processing and continue |
205 | |
206 | // First the unlimited length classes |
207 | |
208 | // @phan-suppress-next-line PhanParamSuspiciousOrder false positive |
209 | if ( strpos( self::EXPR_WHITE_CLASS, $char ) !== false ) { |
210 | // Whitespace |
211 | $p += strspn( $expr, self::EXPR_WHITE_CLASS, $p ); |
212 | continue; |
213 | // @phan-suppress-next-line PhanParamSuspiciousOrder false positive |
214 | } elseif ( strpos( self::EXPR_NUMBER_CLASS, $char ) !== false ) { |
215 | // Number |
216 | if ( $expecting !== 'expression' ) { |
217 | throw new ExprError( 'unexpected_number' ); |
218 | } |
219 | |
220 | // Find the rest of it |
221 | $length = strspn( $expr, self::EXPR_NUMBER_CLASS, $p ); |
222 | // Convert it to float, silently removing double decimal points |
223 | $operands[] = (float)substr( $expr, $p, $length ); |
224 | $p += $length; |
225 | $expecting = 'operator'; |
226 | continue; |
227 | } elseif ( ctype_alpha( $char ) ) { |
228 | // Word |
229 | // Find the rest of it |
230 | $remaining = substr( $expr, $p ); |
231 | if ( !preg_match( '/^[A-Za-z]*/', $remaining, $matches ) ) { |
232 | // This should be unreachable |
233 | throw new ExprError( 'preg_match_failure' ); |
234 | } |
235 | $word = strtolower( $matches[0] ); |
236 | $p += strlen( $word ); |
237 | |
238 | // Interpret the word |
239 | if ( !isset( self::WORDS[$word] ) ) { |
240 | throw new ExprError( 'unrecognised_word', $word ); |
241 | } |
242 | $op = self::WORDS[$word]; |
243 | switch ( $op ) { |
244 | // constant |
245 | case self::EXPR_EXPONENT: |
246 | if ( $expecting !== 'expression' ) { |
247 | break; |
248 | } |
249 | $operands[] = exp( 1 ); |
250 | $expecting = 'operator'; |
251 | continue 2; |
252 | case self::EXPR_PI: |
253 | if ( $expecting !== 'expression' ) { |
254 | throw new ExprError( 'unexpected_number' ); |
255 | } |
256 | $operands[] = pi(); |
257 | $expecting = 'operator'; |
258 | continue 2; |
259 | // Unary operator |
260 | case self::EXPR_NOT: |
261 | case self::EXPR_SINE: |
262 | case self::EXPR_COSINE: |
263 | case self::EXPR_TANGENS: |
264 | case self::EXPR_ARCSINE: |
265 | case self::EXPR_ARCCOS: |
266 | case self::EXPR_ARCTAN: |
267 | case self::EXPR_EXP: |
268 | case self::EXPR_LN: |
269 | case self::EXPR_ABS: |
270 | case self::EXPR_FLOOR: |
271 | case self::EXPR_TRUNC: |
272 | case self::EXPR_CEIL: |
273 | case self::EXPR_SQRT: |
274 | if ( $expecting !== 'expression' ) { |
275 | throw new ExprError( 'unexpected_operator', $word ); |
276 | } |
277 | $operators[] = $op; |
278 | continue 2; |
279 | } |
280 | // Binary operator, fall through |
281 | $name = $word; |
282 | } elseif ( $char2 === '<=' ) { |
283 | $name = $char2; |
284 | $op = self::EXPR_LESSEQ; |
285 | $p += 2; |
286 | } elseif ( $char2 === '>=' ) { |
287 | $name = $char2; |
288 | $op = self::EXPR_GREATEREQ; |
289 | $p += 2; |
290 | } elseif ( $char2 === '<>' || $char2 === '!=' ) { |
291 | $name = $char2; |
292 | $op = self::EXPR_NOTEQ; |
293 | $p += 2; |
294 | } elseif ( $char === '+' ) { |
295 | ++$p; |
296 | if ( $expecting === 'expression' ) { |
297 | // Unary plus |
298 | $operators[] = self::EXPR_POSITIVE; |
299 | continue; |
300 | } else { |
301 | // Binary plus |
302 | $op = self::EXPR_PLUS; |
303 | } |
304 | } elseif ( $char === '-' ) { |
305 | ++$p; |
306 | if ( $expecting === 'expression' ) { |
307 | // Unary minus |
308 | $operators[] = self::EXPR_NEGATIVE; |
309 | continue; |
310 | } else { |
311 | // Binary minus |
312 | $op = self::EXPR_MINUS; |
313 | } |
314 | } elseif ( $char === '*' ) { |
315 | $name = $char; |
316 | $op = self::EXPR_TIMES; |
317 | ++$p; |
318 | } elseif ( $char === '/' ) { |
319 | $name = $char; |
320 | $op = self::EXPR_DIVIDE; |
321 | ++$p; |
322 | } elseif ( $char === '^' ) { |
323 | $name = $char; |
324 | $op = self::EXPR_POW; |
325 | ++$p; |
326 | } elseif ( $char === '(' ) { |
327 | if ( $expecting === 'operator' ) { |
328 | throw new ExprError( 'unexpected_operator', '(' ); |
329 | } |
330 | $operators[] = self::EXPR_OPEN; |
331 | ++$p; |
332 | continue; |
333 | } elseif ( $char === ')' ) { |
334 | $lastOp = end( $operators ); |
335 | while ( $lastOp && $lastOp !== self::EXPR_OPEN ) { |
336 | $this->doOperation( $lastOp, $operands ); |
337 | array_pop( $operators ); |
338 | $lastOp = end( $operators ); |
339 | } |
340 | if ( $lastOp ) { |
341 | array_pop( $operators ); |
342 | } else { |
343 | throw new ExprError( 'unexpected_closing_bracket' ); |
344 | } |
345 | $expecting = 'operator'; |
346 | ++$p; |
347 | continue; |
348 | } elseif ( $char === '=' ) { |
349 | $name = $char; |
350 | $op = self::EXPR_EQUALITY; |
351 | ++$p; |
352 | } elseif ( $char === '<' ) { |
353 | $name = $char; |
354 | $op = self::EXPR_LESS; |
355 | ++$p; |
356 | } elseif ( $char === '>' ) { |
357 | $name = $char; |
358 | $op = self::EXPR_GREATER; |
359 | ++$p; |
360 | } else { |
361 | $utfExpr = Validator::cleanUp( substr( $expr, $p ) ); |
362 | throw new ExprError( 'unrecognised_punctuation', mb_substr( $utfExpr, 0, 1 ) ); |
363 | } |
364 | |
365 | // Binary operator processing |
366 | if ( $expecting === 'expression' ) { |
367 | throw new ExprError( 'unexpected_operator', $name ); |
368 | } |
369 | |
370 | // Shunting yard magic |
371 | $lastOp = end( $operators ); |
372 | while ( $lastOp && self::PRECEDENCE[$op] <= self::PRECEDENCE[$lastOp] ) { |
373 | $this->doOperation( $lastOp, $operands ); |
374 | array_pop( $operators ); |
375 | $lastOp = end( $operators ); |
376 | } |
377 | $operators[] = $op; |
378 | $expecting = 'expression'; |
379 | } |
380 | |
381 | // Finish off the operator array |
382 | // phpcs:ignore Generic.CodeAnalysis.AssignmentInCondition.FoundInWhileCondition |
383 | while ( $op = array_pop( $operators ) ) { |
384 | if ( $op === self::EXPR_OPEN ) { |
385 | throw new ExprError( 'unclosed_bracket' ); |
386 | } |
387 | $this->doOperation( $op, $operands ); |
388 | } |
389 | |
390 | return implode( "<br />\n", $operands ); |
391 | } |
392 | |
393 | /** |
394 | * @param int $op |
395 | * @param array &$stack |
396 | * @throws ExprError |
397 | */ |
398 | public function doOperation( $op, &$stack ) { |
399 | switch ( $op ) { |
400 | case self::EXPR_NEGATIVE: |
401 | if ( count( $stack ) < 1 ) { |
402 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
403 | } |
404 | $arg = array_pop( $stack ); |
405 | $stack[] = -$arg; |
406 | break; |
407 | case self::EXPR_POSITIVE: |
408 | if ( count( $stack ) < 1 ) { |
409 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
410 | } |
411 | break; |
412 | case self::EXPR_TIMES: |
413 | if ( count( $stack ) < 2 ) { |
414 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
415 | } |
416 | $right = array_pop( $stack ); |
417 | $left = array_pop( $stack ); |
418 | $stack[] = $left * $right; |
419 | break; |
420 | case self::EXPR_DIVIDE: |
421 | if ( count( $stack ) < 2 ) { |
422 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
423 | } |
424 | $right = array_pop( $stack ); |
425 | $left = array_pop( $stack ); |
426 | if ( !$right ) { |
427 | throw new ExprError( 'division_by_zero', self::NAMES[$op] ); |
428 | } |
429 | $stack[] = $left / $right; |
430 | break; |
431 | case self::EXPR_MOD: |
432 | if ( count( $stack ) < 2 ) { |
433 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
434 | } |
435 | $right = (int)array_pop( $stack ); |
436 | $left = (int)array_pop( $stack ); |
437 | if ( !$right ) { |
438 | throw new ExprError( 'division_by_zero', self::NAMES[$op] ); |
439 | } |
440 | $stack[] = $left % $right; |
441 | break; |
442 | case self::EXPR_FMOD: |
443 | if ( count( $stack ) < 2 ) { |
444 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
445 | } |
446 | $right = (double)array_pop( $stack ); |
447 | $left = (double)array_pop( $stack ); |
448 | if ( !$right ) { |
449 | throw new ExprError( 'division_by_zero', self::NAMES[$op] ); |
450 | } |
451 | $stack[] = fmod( $left, $right ); |
452 | break; |
453 | case self::EXPR_PLUS: |
454 | if ( count( $stack ) < 2 ) { |
455 | throw new ExprError( 'missing_operand', self::NAMES[$op] ); |
456 | } |
457 | $right = array_pop( $stack ); |
458 | $left = array_pop( $stack ); |
459 | $stack[] = $left + $right; |
460 | break; |