www.aleph1.co.uk Git - yaffs-website/blob - vendor/symfony/expression-language/Parser.php

   1 <?php
   2
   3 /*
   4  * This file is part of the Symfony package.
   5  *
   6  * (c) Fabien Potencier <fabien@symfony.com>
   7  *
   8  * For the full copyright and license information, please view the LICENSE
   9  * file that was distributed with this source code.
  10  */
  11
  12 namespace Symfony\Component\ExpressionLanguage;
  13
  14 /**
  15  * Parsers a token stream.
  16  *
  17  * This parser implements a "Precedence climbing" algorithm.
  18  *
  19  * @see http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
  20  * @see http://en.wikipedia.org/wiki/Operator-precedence_parser
  21  *
  22  * @author Fabien Potencier <fabien@symfony.com>
  23  */
  24 class Parser
  25 {
  26     const OPERATOR_LEFT = 1;
  27     const OPERATOR_RIGHT = 2;
  28
  29     private $stream;
  30     private $unaryOperators;
  31     private $binaryOperators;
  32     private $functions;
  33     private $names;
  34
  35     public function __construct(array $functions)
  36     {
  37         $this->functions = $functions;
  38
  39         $this->unaryOperators = array(
  40             'not' => array('precedence' => 50),
  41             '!' => array('precedence' => 50),
  42             '-' => array('precedence' => 500),
  43             '+' => array('precedence' => 500),
  44         );
  45         $this->binaryOperators = array(
  46             'or' => array('precedence' => 10, 'associativity' => self::OPERATOR_LEFT),
  47             '||' => array('precedence' => 10, 'associativity' => self::OPERATOR_LEFT),
  48             'and' => array('precedence' => 15, 'associativity' => self::OPERATOR_LEFT),
  49             '&&' => array('precedence' => 15, 'associativity' => self::OPERATOR_LEFT),
  50             '|' => array('precedence' => 16, 'associativity' => self::OPERATOR_LEFT),
  51             '^' => array('precedence' => 17, 'associativity' => self::OPERATOR_LEFT),
  52             '&' => array('precedence' => 18, 'associativity' => self::OPERATOR_LEFT),
  53             '==' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  54             '===' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  55             '!=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  56             '!==' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  57             '<' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  58             '>' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  59             '>=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  60             '<=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  61             'not in' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  62             'in' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  63             'matches' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
  64             '..' => array('precedence' => 25, 'associativity' => self::OPERATOR_LEFT),
  65             '+' => array('precedence' => 30, 'associativity' => self::OPERATOR_LEFT),
  66             '-' => array('precedence' => 30, 'associativity' => self::OPERATOR_LEFT),
  67             '~' => array('precedence' => 40, 'associativity' => self::OPERATOR_LEFT),
  68             '*' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
  69             '/' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
  70             '%' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
  71             '**' => array('precedence' => 200, 'associativity' => self::OPERATOR_RIGHT),
  72         );
  73     }
  74
  75     /**
  76      * Converts a token stream to a node tree.
  77      *
  78      * The valid names is an array where the values
  79      * are the names that the user can use in an expression.
  80      *
  81      * If the variable name in the compiled PHP code must be
  82      * different, define it as the key.
  83      *
  84      * For instance, ['this' => 'container'] means that the
  85      * variable 'container' can be used in the expression
  86      * but the compiled code will use 'this'.
  87      *
  88      * @param TokenStream $stream A token stream instance
  89      * @param array       $names  An array of valid names
  90      *
  91      * @return Node\Node A node tree
  92      *
  93      * @throws SyntaxError
  94      */
  95     public function parse(TokenStream $stream, $names = array())
  96     {
  97         $this->stream = $stream;
  98         $this->names = $names;
  99
 100         $node = $this->parseExpression();
 101         if (!$stream->isEOF()) {
 102             throw new SyntaxError(sprintf('Unexpected token "%s" of value "%s"', $stream->current->type, $stream->current->value), $stream->current->cursor, $stream->getExpression());
 103         }
 104
 105         return $node;
 106     }
 107
 108     public function parseExpression($precedence = 0)
 109     {
 110         $expr = $this->getPrimary();
 111         $token = $this->stream->current;
 112         while ($token->test(Token::OPERATOR_TYPE) && isset($this->binaryOperators[$token->value]) && $this->binaryOperators[$token->value]['precedence'] >= $precedence) {
 113             $op = $this->binaryOperators[$token->value];
 114             $this->stream->next();
 115
 116             $expr1 = $this->parseExpression(self::OPERATOR_LEFT === $op['associativity'] ? $op['precedence'] + 1 : $op['precedence']);
 117             $expr = new Node\BinaryNode($token->value, $expr, $expr1);
 118
 119             $token = $this->stream->current;
 120         }
 121
 122         if (0 === $precedence) {
 123             return $this->parseConditionalExpression($expr);
 124         }
 125
 126         return $expr;
 127     }
 128
 129     protected function getPrimary()
 130     {
 131         $token = $this->stream->current;
 132
 133         if ($token->test(Token::OPERATOR_TYPE) && isset($this->unaryOperators[$token->value])) {
 134             $operator = $this->unaryOperators[$token->value];
 135             $this->stream->next();
 136             $expr = $this->parseExpression($operator['precedence']);
 137
 138             return $this->parsePostfixExpression(new Node\UnaryNode($token->value, $expr));
 139         }
 140
 141         if ($token->test(Token::PUNCTUATION_TYPE, '(')) {
 142             $this->stream->next();
 143             $expr = $this->parseExpression();
 144             $this->stream->expect(Token::PUNCTUATION_TYPE, ')', 'An opened parenthesis is not properly closed');
 145
 146             return $this->parsePostfixExpression($expr);
 147         }
 148
 149         return $this->parsePrimaryExpression();
 150     }
 151
 152     protected function parseConditionalExpression($expr)
 153     {
 154         while ($this->stream->current->test(Token::PUNCTUATION_TYPE, '?')) {
 155             $this->stream->next();
 156             if (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ':')) {
 157                 $expr2 = $this->parseExpression();
 158                 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, ':')) {
 159                     $this->stream->next();
 160                     $expr3 = $this->parseExpression();
 161                 } else {
 162                     $expr3 = new Node\ConstantNode(null);
 163                 }
 164             } else {
 165                 $this->stream->next();
 166                 $expr2 = $expr;
 167                 $expr3 = $this->parseExpression();
 168             }
 169
 170             $expr = new Node\ConditionalNode($expr, $expr2, $expr3);
 171         }
 172
 173         return $expr;
 174     }
 175
 176     public function parsePrimaryExpression()
 177     {
 178         $token = $this->stream->current;
 179         switch ($token->type) {
 180             case Token::NAME_TYPE:
 181                 $this->stream->next();
 182                 switch ($token->value) {
 183                     case 'true':
 184                     case 'TRUE':
 185                         return new Node\ConstantNode(true);
 186
 187                     case 'false':
 188                     case 'FALSE':
 189                         return new Node\ConstantNode(false);
 190
 191                     case 'null':
 192                     case 'NULL':
 193                         return new Node\ConstantNode(null);
 194
 195                     default:
 196                         if ('(' === $this->stream->current->value) {
 197                             if (false === isset($this->functions[$token->value])) {
 198                                 throw new SyntaxError(sprintf('The function "%s" does not exist', $token->value), $token->cursor, $this->stream->getExpression());
 199                             }
 200
 201                             $node = new Node\FunctionNode($token->value, $this->parseArguments());
 202                         } else {
 203                             if (!in_array($token->value, $this->names, true)) {
 204                                 throw new SyntaxError(sprintf('Variable "%s" is not valid', $token->value), $token->cursor, $this->stream->getExpression());
 205                             }
 206
 207                             // is the name used in the compiled code different
 208                             // from the name used in the expression?
 209                             if (is_int($name = array_search($token->value, $this->names))) {
 210                                 $name = $token->value;
 211                             }
 212
 213                             $node = new Node\NameNode($name);
 214                         }
 215                 }
 216                 break;
 217
 218             case Token::NUMBER_TYPE:
 219             case Token::STRING_TYPE:
 220                 $this->stream->next();
 221
 222                 return new Node\ConstantNode($token->value);
 223
 224             default:
 225                 if ($token->test(Token::PUNCTUATION_TYPE, '[')) {
 226                     $node = $this->parseArrayExpression();
 227                 } elseif ($token->test(Token::PUNCTUATION_TYPE, '{')) {
 228                     $node = $this->parseHashExpression();
 229                 } else {
 230                     throw new SyntaxError(sprintf('Unexpected token "%s" of value "%s"', $token->type, $token->value), $token->cursor, $this->stream->getExpression());
 231                 }
 232         }
 233
 234         return $this->parsePostfixExpression($node);
 235     }
 236
 237     public function parseArrayExpression()
 238     {
 239         $this->stream->expect(Token::PUNCTUATION_TYPE, '[', 'An array element was expected');
 240
 241         $node = new Node\ArrayNode();
 242         $first = true;
 243         while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ']')) {
 244             if (!$first) {
 245                 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'An array element must be followed by a comma');
 246
 247                 // trailing ,?
 248                 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, ']')) {
 249                     break;
 250                 }
 251             }
 252             $first = false;
 253
 254             $node->addElement($this->parseExpression());
 255         }
 256         $this->stream->expect(Token::PUNCTUATION_TYPE, ']', 'An opened array is not properly closed');
 257
 258         return $node;
 259     }
 260
 261     public function parseHashExpression()
 262     {
 263         $this->stream->expect(Token::PUNCTUATION_TYPE, '{', 'A hash element was expected');
 264
 265         $node = new Node\ArrayNode();
 266         $first = true;
 267         while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, '}')) {
 268             if (!$first) {
 269                 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'A hash value must be followed by a comma');
 270
 271                 // trailing ,?
 272                 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, '}')) {
 273                     break;
 274                 }
 275             }
 276             $first = false;
 277
 278             // a hash key can be:
 279             //
 280             //  * a number -- 12
 281             //  * a string -- 'a'
 282             //  * a name, which is equivalent to a string -- a
 283             //  * an expression, which must be enclosed in parentheses -- (1 + 2)
 284             if ($this->stream->current->test(Token::STRING_TYPE) || $this->stream->current->test(Token::NAME_TYPE) || $this->stream->current->test(Token::NUMBER_TYPE)) {
 285                 $key = new Node\ConstantNode($this->stream->current->value);
 286                 $this->stream->next();
 287             } elseif ($this->stream->current->test(Token::PUNCTUATION_TYPE, '(')) {
 288                 $key = $this->parseExpression();
 289             } else {
 290                 $current = $this->stream->current;
 291
 292                 throw new SyntaxError(sprintf('A hash key must be a quoted string, a number, a name, or an expression enclosed in parentheses (unexpected token "%s" of value "%s"', $current->type, $current->value), $current->cursor, $this->stream->getExpression());
 293             }
 294
 295             $this->stream->expect(Token::PUNCTUATION_TYPE, ':', 'A hash key must be followed by a colon (:)');
 296             $value = $this->parseExpression();
 297
 298             $node->addElement($value, $key);
 299         }
 300         $this->stream->expect(Token::PUNCTUATION_TYPE, '}', 'An opened hash is not properly closed');
 301
 302         return $node;
 303     }
 304
 305     public function parsePostfixExpression($node)
 306     {
 307         $token = $this->stream->current;
 308         while ($token->type == Token::PUNCTUATION_TYPE) {
 309             if ('.' === $token->value) {
 310                 $this->stream->next();
 311                 $token = $this->stream->current;
 312                 $this->stream->next();
 313
 314                 if (
 315                     $token->type !== Token::NAME_TYPE
 316                     &&
 317                     // Operators like "not" and "matches" are valid method or property names,
 318                     //
 319                     // In other words, besides NAME_TYPE, OPERATOR_TYPE could also be parsed as a property or method.
 320                     // This is because operators are processed by the lexer prior to names. So "not" in "foo.not()" or "matches" in "foo.matches" will be recognized as an operator first.
 321                     // But in fact, "not" and "matches" in such expressions shall be parsed as method or property names.
 322                     //
 323                     // And this ONLY works if the operator consists of valid characters for a property or method name.
 324                     //
 325                     // Other types, such as STRING_TYPE and NUMBER_TYPE, can't be parsed as property nor method names.
 326                     //
 327                     // As a result, if $token is NOT an operator OR $token->value is NOT a valid property or method name, an exception shall be thrown.
 328                     ($token->type !== Token::OPERATOR_TYPE || !preg_match('/[a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*/A', $token->value))
 329                 ) {
 330                     throw new SyntaxError('Expected name', $token->cursor, $this->stream->getExpression());
 331                 }
 332
 333                 $arg = new Node\ConstantNode($token->value);
 334
 335                 $arguments = new Node\ArgumentsNode();
 336                 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, '(')) {
 337                     $type = Node\GetAttrNode::METHOD_CALL;
 338                     foreach ($this->parseArguments()->nodes as $n) {
 339                         $arguments->addElement($n);
 340                     }
 341                 } else {
 342                     $type = Node\GetAttrNode::PROPERTY_CALL;
 343                 }
 344
 345                 $node = new Node\GetAttrNode($node, $arg, $arguments, $type);
 346             } elseif ('[' === $token->value) {
 347                 if ($node instanceof Node\GetAttrNode && Node\GetAttrNode::METHOD_CALL === $node->attributes['type'] && \PHP_VERSION_ID < 50400) {
 348                     throw new SyntaxError('Array calls on a method call is only supported on PHP 5.4+', $token->cursor, $this->stream->getExpression());
 349                 }
 350
 351                 $this->stream->next();
 352                 $arg = $this->parseExpression();
 353                 $this->stream->expect(Token::PUNCTUATION_TYPE, ']');
 354
 355                 $node = new Node\GetAttrNode($node, $arg, new Node\ArgumentsNode(), Node\GetAttrNode::ARRAY_CALL);
 356             } else {
 357                 break;
 358             }
 359
 360             $token = $this->stream->current;
 361         }
 362
 363         return $node;
 364     }
 365
 366     /**
 367      * Parses arguments.
 368      */
 369     public function parseArguments()
 370     {
 371         $args = array();
 372         $this->stream->expect(Token::PUNCTUATION_TYPE, '(', 'A list of arguments must begin with an opening parenthesis');
 373         while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ')')) {
 374             if (!empty($args)) {
 375                 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'Arguments must be separated by a comma');
 376             }
 377
 378             $args[] = $this->parseExpression();
 379         }
 380         $this->stream->expect(Token::PUNCTUATION_TYPE, ')', 'A list of arguments must be closed by a parenthesis');
 381
 382         return new Node\Node($args);
 383     }
 384 }