Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
98.40% covered (success)
98.40%
369 / 375
0.00% covered (danger)
0.00%
0 / 2
CRAP
0.00% covered (danger)
0.00%
0 / 1
ExprParser
98.40% covered (success)
98.40%
369 / 375
0.00% covered (danger)
0.00%
0 / 2
142
0.00% covered (danger)
0.00%
0 / 1
 doExpression
97.26% covered (success)
97.26%
142 / 146
0.00% covered (danger)
0.00%
0 / 1
54
 doOperation
99.13% covered (success)
99.13%
227 / 229
0.00% covered (danger)
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
19namespace MediaWiki\Extension\ParserFunctions;
20
21use UtfNormal\Validator;
22
23class 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, [ '&lt;' => '<', '&gt;' => '>',
188            '&minus;' => '-', '−' => '-' ] );
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;