| 1 |
<?php |
| 2 |
|
| 3 |
namespace Dudlewebs\WPMCS\s3\JmesPath; |
| 4 |
|
| 5 |
use Dudlewebs\WPMCS\s3\JmesPath\Lexer as T; |
| 6 |
/** |
| 7 |
* JMESPath Pratt parser |
| 8 |
* @link http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf |
| 9 |
*/ |
| 10 |
class Parser |
| 11 |
{ |
| 12 |
/** @var Lexer */ |
| 13 |
private $lexer; |
| 14 |
private $tokens; |
| 15 |
private $token; |
| 16 |
private $tpos; |
| 17 |
private $expression; |
| 18 |
private static $nullToken = ['type' => T::T_EOF]; |
| 19 |
private static $currentNode = ['type' => T::T_CURRENT]; |
| 20 |
private static $bp = [T::T_EOF => 0, T::T_QUOTED_IDENTIFIER => 0, T::T_IDENTIFIER => 0, T::T_RBRACKET => 0, T::T_RPAREN => 0, T::T_COMMA => 0, T::T_RBRACE => 0, T::T_NUMBER => 0, T::T_CURRENT => 0, T::T_EXPREF => 0, T::T_COLON => 0, T::T_PIPE => 1, T::T_OR => 2, T::T_AND => 3, T::T_COMPARATOR => 5, T::T_FLATTEN => 9, T::T_STAR => 20, T::T_FILTER => 21, T::T_DOT => 40, T::T_NOT => 45, T::T_LBRACE => 50, T::T_LBRACKET => 55, T::T_LPAREN => 60]; |
| 21 |
/** @var array Acceptable tokens after a dot token */ |
| 22 |
private static $afterDot = [ |
| 23 |
T::T_IDENTIFIER => \true, |
| 24 |
// foo.bar |
| 25 |
T::T_QUOTED_IDENTIFIER => \true, |
| 26 |
// foo."bar" |
| 27 |
T::T_STAR => \true, |
| 28 |
// foo.* |
| 29 |
T::T_LBRACE => \true, |
| 30 |
// foo[1] |
| 31 |
T::T_LBRACKET => \true, |
| 32 |
// foo{a: 0} |
| 33 |
T::T_FILTER => \true, |
| 34 |
]; |
| 35 |
/** |
| 36 |
* @param Lexer|null $lexer Lexer used to tokenize expressions |
| 37 |
*/ |
| 38 |
public function __construct(?Lexer $lexer = null) |
| 39 |
{ |
| 40 |
$this->lexer = $lexer ?: new Lexer(); |
| 41 |
} |
| 42 |
/** |
| 43 |
* Parses a JMESPath expression into an AST |
| 44 |
* |
| 45 |
* @param string $expression JMESPath expression to compile |
| 46 |
* |
| 47 |
* @return array Returns an array based AST |
| 48 |
* @throws SyntaxErrorException |
| 49 |
*/ |
| 50 |
public function parse($expression) |
| 51 |
{ |
| 52 |
$this->expression = $expression; |
| 53 |
$this->tokens = $this->lexer->tokenize($expression); |
| 54 |
$this->tpos = -1; |
| 55 |
$this->next(); |
| 56 |
$result = $this->expr(); |
| 57 |
if ($this->token['type'] === T::T_EOF) { |
| 58 |
return $result; |
| 59 |
} |
| 60 |
throw $this->syntax('Did not reach the end of the token stream'); |
| 61 |
} |
| 62 |
/** |
| 63 |
* Parses an expression while rbp < lbp. |
| 64 |
* |
| 65 |
* @param int $rbp Right bound precedence |
| 66 |
* |
| 67 |
* @return array |
| 68 |
*/ |
| 69 |
private function expr($rbp = 0) |
| 70 |
{ |
| 71 |
$left = $this->{"nud_{$this->token['type']}"}(); |
| 72 |
while ($rbp < self::$bp[$this->token['type']]) { |
| 73 |
$left = $this->{"led_{$this->token['type']}"}($left); |
| 74 |
} |
| 75 |
return $left; |
| 76 |
} |
| 77 |
private function nud_identifier() |
| 78 |
{ |
| 79 |
$token = $this->token; |
| 80 |
$this->next(); |
| 81 |
return ['type' => 'field', 'value' => $token['value']]; |
| 82 |
} |
| 83 |
private function nud_quoted_identifier() |
| 84 |
{ |
| 85 |
$token = $this->token; |
| 86 |
$this->next(); |
| 87 |
$this->assertNotToken(T::T_LPAREN); |
| 88 |
return ['type' => 'field', 'value' => $token['value']]; |
| 89 |
} |
| 90 |
private function nud_current() |
| 91 |
{ |
| 92 |
$this->next(); |
| 93 |
return self::$currentNode; |
| 94 |
} |
| 95 |
private function nud_literal() |
| 96 |
{ |
| 97 |
$token = $this->token; |
| 98 |
$this->next(); |
| 99 |
return ['type' => 'literal', 'value' => $token['value']]; |
| 100 |
} |
| 101 |
private function nud_expref() |
| 102 |
{ |
| 103 |
$this->next(); |
| 104 |
return ['type' => T::T_EXPREF, 'children' => [$this->expr(self::$bp[T::T_EXPREF])]]; |
| 105 |
} |
| 106 |
private function nud_not() |
| 107 |
{ |
| 108 |
$this->next(); |
| 109 |
return ['type' => T::T_NOT, 'children' => [$this->expr(self::$bp[T::T_NOT])]]; |
| 110 |
} |
| 111 |
private function nud_lparen() |
| 112 |
{ |
| 113 |
$this->next(); |
| 114 |
$result = $this->expr(0); |
| 115 |
if ($this->token['type'] !== T::T_RPAREN) { |
| 116 |
throw $this->syntax('Unclosed `(`'); |
| 117 |
} |
| 118 |
$this->next(); |
| 119 |
return $result; |
| 120 |
} |
| 121 |
private function nud_lbrace() |
| 122 |
{ |
| 123 |
static $validKeys = [T::T_QUOTED_IDENTIFIER => \true, T::T_IDENTIFIER => \true]; |
| 124 |
$this->next($validKeys); |
| 125 |
$pairs = []; |
| 126 |
do { |
| 127 |
$pairs[] = $this->parseKeyValuePair(); |
| 128 |
if ($this->token['type'] == T::T_COMMA) { |
| 129 |
$this->next($validKeys); |
| 130 |
} |
| 131 |
} while ($this->token['type'] !== T::T_RBRACE); |
| 132 |
$this->next(); |
| 133 |
return ['type' => 'multi_select_hash', 'children' => $pairs]; |
| 134 |
} |
| 135 |
private function nud_flatten() |
| 136 |
{ |
| 137 |
return $this->led_flatten(self::$currentNode); |
| 138 |
} |
| 139 |
private function nud_filter() |
| 140 |
{ |
| 141 |
return $this->led_filter(self::$currentNode); |
| 142 |
} |
| 143 |
private function nud_star() |
| 144 |
{ |
| 145 |
return $this->parseWildcardObject(self::$currentNode); |
| 146 |
} |
| 147 |
private function nud_lbracket() |
| 148 |
{ |
| 149 |
$this->next(); |
| 150 |
$type = $this->token['type']; |
| 151 |
if ($type == T::T_NUMBER || $type == T::T_COLON) { |
| 152 |
return $this->parseArrayIndexExpression(); |
| 153 |
} elseif ($type == T::T_STAR && $this->lookahead() == T::T_RBRACKET) { |
| 154 |
return $this->parseWildcardArray(); |
| 155 |
} else { |
| 156 |
return $this->parseMultiSelectList(); |
| 157 |
} |
| 158 |
} |
| 159 |
private function led_lbracket(array $left) |
| 160 |
{ |
| 161 |
static $nextTypes = [T::T_NUMBER => \true, T::T_COLON => \true, T::T_STAR => \true]; |
| 162 |
$this->next($nextTypes); |
| 163 |
switch ($this->token['type']) { |
| 164 |
case T::T_NUMBER: |
| 165 |
case T::T_COLON: |
| 166 |
return ['type' => 'subexpression', 'children' => [$left, $this->parseArrayIndexExpression()]]; |
| 167 |
default: |
| 168 |
return $this->parseWildcardArray($left); |
| 169 |
} |
| 170 |
} |
| 171 |
private function led_flatten(array $left) |
| 172 |
{ |
| 173 |
$this->next(); |
| 174 |
return ['type' => 'projection', 'from' => 'array', 'children' => [['type' => T::T_FLATTEN, 'children' => [$left]], $this->parseProjection(self::$bp[T::T_FLATTEN])]]; |
| 175 |
} |
| 176 |
private function led_dot(array $left) |
| 177 |
{ |
| 178 |
$this->next(self::$afterDot); |
| 179 |
if ($this->token['type'] == T::T_STAR) { |
| 180 |
return $this->parseWildcardObject($left); |
| 181 |
} |
| 182 |
return ['type' => 'subexpression', 'children' => [$left, $this->parseDot(self::$bp[T::T_DOT])]]; |
| 183 |
} |
| 184 |
private function led_or(array $left) |
| 185 |
{ |
| 186 |
$this->next(); |
| 187 |
return ['type' => T::T_OR, 'children' => [$left, $this->expr(self::$bp[T::T_OR])]]; |
| 188 |
} |
| 189 |
private function led_and(array $left) |
| 190 |
{ |
| 191 |
$this->next(); |
| 192 |
return ['type' => T::T_AND, 'children' => [$left, $this->expr(self::$bp[T::T_AND])]]; |
| 193 |
} |
| 194 |
private function led_pipe(array $left) |
| 195 |
{ |
| 196 |
$this->next(); |
| 197 |
return ['type' => T::T_PIPE, 'children' => [$left, $this->expr(self::$bp[T::T_PIPE])]]; |
| 198 |
} |
| 199 |
private function led_lparen(array $left) |
| 200 |
{ |
| 201 |
$args = []; |
| 202 |
$this->next(); |
| 203 |
while ($this->token['type'] != T::T_RPAREN) { |
| 204 |
$args[] = $this->expr(0); |
| 205 |
if ($this->token['type'] == T::T_COMMA) { |
| 206 |
$this->next(); |
| 207 |
} |
| 208 |
} |
| 209 |
$this->next(); |
| 210 |
return ['type' => 'function', 'value' => $left['value'], 'children' => $args]; |
| 211 |
} |
| 212 |
private function led_filter(array $left) |
| 213 |
{ |
| 214 |
$this->next(); |
| 215 |
$expression = $this->expr(); |
| 216 |
if ($this->token['type'] != T::T_RBRACKET) { |
| 217 |
throw $this->syntax('Expected a closing rbracket for the filter'); |
| 218 |
} |
| 219 |
$this->next(); |
| 220 |
$rhs = $this->parseProjection(self::$bp[T::T_FILTER]); |
| 221 |
return ['type' => 'projection', 'from' => 'array', 'children' => [$left ?: self::$currentNode, ['type' => 'condition', 'children' => [$expression, $rhs]]]]; |
| 222 |
} |
| 223 |
private function led_comparator(array $left) |
| 224 |
{ |
| 225 |
$token = $this->token; |
| 226 |
$this->next(); |
| 227 |
return ['type' => T::T_COMPARATOR, 'value' => $token['value'], 'children' => [$left, $this->expr(self::$bp[T::T_COMPARATOR])]]; |
| 228 |
} |
| 229 |
private function parseProjection($bp) |
| 230 |
{ |
| 231 |
$type = $this->token['type']; |
| 232 |
if (self::$bp[$type] < 10) { |
| 233 |
return self::$currentNode; |
| 234 |
} elseif ($type == T::T_DOT) { |
| 235 |
$this->next(self::$afterDot); |
| 236 |
return $this->parseDot($bp); |
| 237 |
} elseif ($type == T::T_LBRACKET || $type == T::T_FILTER) { |
| 238 |
return $this->expr($bp); |
| 239 |
} |
| 240 |
throw $this->syntax('Syntax error after projection'); |
| 241 |
} |
| 242 |
private function parseDot($bp) |
| 243 |
{ |
| 244 |
if ($this->token['type'] == T::T_LBRACKET) { |
| 245 |
$this->next(); |
| 246 |
return $this->parseMultiSelectList(); |
| 247 |
} |
| 248 |
return $this->expr($bp); |
| 249 |
} |
| 250 |
private function parseKeyValuePair() |
| 251 |
{ |
| 252 |
static $validColon = [T::T_COLON => \true]; |
| 253 |
$key = $this->token['value']; |
| 254 |
$this->next($validColon); |
| 255 |
$this->next(); |
| 256 |
return ['type' => 'key_val_pair', 'value' => $key, 'children' => [$this->expr()]]; |
| 257 |
} |
| 258 |
private function parseWildcardObject(?array $left = null) |
| 259 |
{ |
| 260 |
$this->next(); |
| 261 |
return ['type' => 'projection', 'from' => 'object', 'children' => [$left ?: self::$currentNode, $this->parseProjection(self::$bp[T::T_STAR])]]; |
| 262 |
} |
| 263 |
private function parseWildcardArray(?array $left = null) |
| 264 |
{ |
| 265 |
static $getRbracket = [T::T_RBRACKET => \true]; |
| 266 |
$this->next($getRbracket); |
| 267 |
$this->next(); |
| 268 |
return ['type' => 'projection', 'from' => 'array', 'children' => [$left ?: self::$currentNode, $this->parseProjection(self::$bp[T::T_STAR])]]; |
| 269 |
} |
| 270 |
/** |
| 271 |
* Parses an array index expression (e.g., [0], [1:2:3] |
| 272 |
*/ |
| 273 |
private function parseArrayIndexExpression() |
| 274 |
{ |
| 275 |
static $matchNext = [T::T_NUMBER => \true, T::T_COLON => \true, T::T_RBRACKET => \true]; |
| 276 |
$pos = 0; |
| 277 |
$parts = [null, null, null]; |
| 278 |
$expected = $matchNext; |
| 279 |
do { |
| 280 |
if ($this->token['type'] == T::T_COLON) { |
| 281 |
$pos++; |
| 282 |
$expected = $matchNext; |
| 283 |
} elseif ($this->token['type'] == T::T_NUMBER) { |
| 284 |
$parts[$pos] = $this->token['value']; |
| 285 |
$expected = [T::T_COLON => \true, T::T_RBRACKET => \true]; |
| 286 |
} |
| 287 |
$this->next($expected); |
| 288 |
} while ($this->token['type'] != T::T_RBRACKET); |
| 289 |
// Consume the closing bracket |
| 290 |
$this->next(); |
| 291 |
if ($pos === 0) { |
| 292 |
// No colons were found so this is a simple index extraction |
| 293 |
return ['type' => 'index', 'value' => $parts[0]]; |
| 294 |
} |
| 295 |
if ($pos > 2) { |
| 296 |
throw $this->syntax('Invalid array slice syntax: too many colons'); |
| 297 |
} |
| 298 |
// Sliced array from start (e.g., [2:]) |
| 299 |
return ['type' => 'projection', 'from' => 'array', 'children' => [['type' => 'slice', 'value' => $parts], $this->parseProjection(self::$bp[T::T_STAR])]]; |
| 300 |
} |
| 301 |
private function parseMultiSelectList() |
| 302 |
{ |
| 303 |
$nodes = []; |
| 304 |
do { |
| 305 |
$nodes[] = $this->expr(); |
| 306 |
if ($this->token['type'] == T::T_COMMA) { |
| 307 |
$this->next(); |
| 308 |
$this->assertNotToken(T::T_RBRACKET); |
| 309 |
} |
| 310 |
} while ($this->token['type'] !== T::T_RBRACKET); |
| 311 |
$this->next(); |
| 312 |
return ['type' => 'multi_select_list', 'children' => $nodes]; |
| 313 |
} |
| 314 |
private function syntax($msg) |
| 315 |
{ |
| 316 |
return new SyntaxErrorException($msg, $this->token, $this->expression); |
| 317 |
} |
| 318 |
private function lookahead() |
| 319 |
{ |
| 320 |
return !isset($this->tokens[$this->tpos + 1]) ? T::T_EOF : $this->tokens[$this->tpos + 1]['type']; |
| 321 |
} |
| 322 |
private function next(?array $match = null) |
| 323 |
{ |
| 324 |
if (!isset($this->tokens[$this->tpos + 1])) { |
| 325 |
$this->token = self::$nullToken; |
| 326 |
} else { |
| 327 |
$this->token = $this->tokens[++$this->tpos]; |
| 328 |
} |
| 329 |
if ($match && !isset($match[$this->token['type']])) { |
| 330 |
throw $this->syntax($match); |
| 331 |
} |
| 332 |
} |
| 333 |
private function assertNotToken($type) |
| 334 |
{ |
| 335 |
if ($this->token['type'] == $type) { |
| 336 |
throw $this->syntax("Token {$this->tpos} not allowed to be {$type}"); |
| 337 |
} |
| 338 |
} |
| 339 |
/** |
| 340 |
* @internal Handles undefined tokens without paying the cost of validation |
| 341 |
*/ |
| 342 |
public function __call($method, $args) |
| 343 |
{ |
| 344 |
$prefix = \substr($method, 0, 4); |
| 345 |
if ($prefix == 'nud_' || $prefix == 'led_') { |
| 346 |
$token = \substr($method, 4); |
| 347 |
$message = "Unexpected \"{$token}\" token ({$method}). Expected one of" . " the following tokens: " . \implode(', ', \array_map(function ($i) { |
| 348 |
return '"' . \substr($i, 4) . '"'; |
| 349 |
}, \array_filter(\get_class_methods($this), function ($i) use($prefix) { |
| 350 |
return \strpos($i, $prefix) === 0; |
| 351 |
}))); |
| 352 |
throw $this->syntax($message); |
| 353 |
} |
| 354 |
throw new \BadMethodCallException("Call to undefined method {$method}"); |
| 355 |
} |
| 356 |
} |
| 357 |
|
