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; |