1 /* 2 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"). 5 * You may not use this file except in compliance with the License. 6 * A copy of the License is located at 7 * 8 * http://aws.amazon.com/apache2.0 9 * 10 * or in the "license" file accompanying this file. This file is distributed 11 * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 12 * express or implied. See the License for the specific language governing 13 * permissions and limitations under the License. 14 */ 15 16 package software.amazon.awssdk.codegen.jmespath.parser; 17 18 import java.io.IOException; 19 import java.util.ArrayList; 20 import java.util.Collections; 21 import java.util.List; 22 import java.util.Optional; 23 import java.util.OptionalInt; 24 import java.util.function.BiFunction; 25 import software.amazon.awssdk.codegen.internal.Jackson; 26 import software.amazon.awssdk.codegen.jmespath.component.AndExpression; 27 import software.amazon.awssdk.codegen.jmespath.component.BracketSpecifier; 28 import software.amazon.awssdk.codegen.jmespath.component.BracketSpecifierWithQuestionMark; 29 import software.amazon.awssdk.codegen.jmespath.component.Comparator; 30 import software.amazon.awssdk.codegen.jmespath.component.ComparatorExpression; 31 import software.amazon.awssdk.codegen.jmespath.component.CurrentNode; 32 import software.amazon.awssdk.codegen.jmespath.component.Expression; 33 import software.amazon.awssdk.codegen.jmespath.component.ExpressionType; 34 import software.amazon.awssdk.codegen.jmespath.component.FunctionArg; 35 import software.amazon.awssdk.codegen.jmespath.component.FunctionExpression; 36 import software.amazon.awssdk.codegen.jmespath.component.IndexExpression; 37 import software.amazon.awssdk.codegen.jmespath.component.KeyValueExpression; 38 import software.amazon.awssdk.codegen.jmespath.component.Literal; 39 import software.amazon.awssdk.codegen.jmespath.component.MultiSelectHash; 40 import software.amazon.awssdk.codegen.jmespath.component.MultiSelectList; 41 import software.amazon.awssdk.codegen.jmespath.component.NotExpression; 42 import software.amazon.awssdk.codegen.jmespath.component.OrExpression; 43 import software.amazon.awssdk.codegen.jmespath.component.ParenExpression; 44 import software.amazon.awssdk.codegen.jmespath.component.PipeExpression; 45 import software.amazon.awssdk.codegen.jmespath.component.SliceExpression; 46 import software.amazon.awssdk.codegen.jmespath.component.SubExpression; 47 import software.amazon.awssdk.codegen.jmespath.component.SubExpressionRight; 48 import software.amazon.awssdk.codegen.jmespath.component.WildcardExpression; 49 import software.amazon.awssdk.codegen.jmespath.parser.util.CompositeParser; 50 import software.amazon.awssdk.utils.Logger; 51 52 /** 53 * Parses a JMESPath expression string into an {@link Expression}. 54 * 55 * This implements the grammar described here: https://jmespath.org/specification.html#grammar 56 */ 57 public class JmesPathParser { 58 private static final Logger log = Logger.loggerFor(JmesPathParser.class); 59 60 private final String input; 61 JmesPathParser(String input)62 private JmesPathParser(String input) { 63 this.input = input; 64 } 65 66 /** 67 * Parses a JMESPath expression string into a {@link Expression}. 68 */ parse(String jmesPathString)69 public static Expression parse(String jmesPathString) { 70 return new JmesPathParser(jmesPathString).parse(); 71 } 72 parse()73 private Expression parse() { 74 ParseResult<Expression> expression = parseExpression(0, input.length()); 75 if (!expression.hasResult()) { 76 throw new IllegalArgumentException("Failed to parse expression."); 77 } 78 79 return expression.result(); 80 } 81 82 /** 83 * expression = sub-expression / index-expression / comparator-expression 84 * expression =/ or-expression / identifier 85 * expression =/ and-expression / not-expression / paren-expression 86 * expression =/ "*" / multi-select-list / multi-select-hash / literal 87 * expression =/ function-expression / pipe-expression / raw-string 88 * expression =/ current-node 89 */ parseExpression(int startPosition, int endPosition)90 private ParseResult<Expression> parseExpression(int startPosition, int endPosition) { 91 startPosition = trimLeftWhitespace(startPosition, endPosition); 92 endPosition = trimRightWhitespace(startPosition, endPosition); 93 94 if (startPosition < 0 || endPosition > input.length() + 1) { 95 return ParseResult.error(); 96 } 97 98 return CompositeParser.firstTry(this::parseSubExpression, Expression::subExpression) 99 .thenTry(this::parseIndexExpression, Expression::indexExpression) 100 .thenTry(this::parseNotExpression, Expression::notExpression) 101 .thenTry(this::parseAndExpression, Expression::andExpression) 102 .thenTry(this::parseOrExpression, Expression::orExpression) 103 .thenTry(this::parseComparatorExpression, Expression::comparatorExpression) 104 .thenTry(this::parsePipeExpression, Expression::pipeExpression) 105 .thenTry(this::parseIdentifier, Expression::identifier) 106 .thenTry(this::parseParenExpression, Expression::parenExpression) 107 .thenTry(this::parseWildcardExpression, Expression::wildcardExpression) 108 .thenTry(this::parseMultiSelectList, Expression::multiSelectList) 109 .thenTry(this::parseMultiSelectHash, Expression::multiSelectHash) 110 .thenTry(this::parseLiteral, Expression::literal) 111 .thenTry(this::parseFunctionExpression, Expression::functionExpression) 112 .thenTry(this::parseRawString, Expression::rawString) 113 .thenTry(this::parseCurrentNode, Expression::currentNode) 114 .parse(startPosition, endPosition); 115 } 116 117 /** 118 * sub-expression = expression "." ( identifier / 119 * multi-select-list / 120 * multi-select-hash / 121 * function-expression / 122 * "*" ) 123 */ parseSubExpression(int startPosition, int endPosition)124 private ParseResult<SubExpression> parseSubExpression(int startPosition, int endPosition) { 125 startPosition = trimLeftWhitespace(startPosition, endPosition); 126 endPosition = trimRightWhitespace(startPosition, endPosition); 127 128 List<Integer> dotPositions = findCharacters(startPosition + 1, endPosition - 1, "."); 129 for (Integer dotPosition : dotPositions) { 130 ParseResult<Expression> leftSide = parseExpression(startPosition, dotPosition); 131 if (!leftSide.hasResult()) { 132 continue; 133 } 134 135 ParseResult<SubExpressionRight> rightSide = 136 CompositeParser.firstTry(this::parseIdentifier, SubExpressionRight::identifier) 137 .thenTry(this::parseMultiSelectList, SubExpressionRight::multiSelectList) 138 .thenTry(this::parseMultiSelectHash, SubExpressionRight::multiSelectHash) 139 .thenTry(this::parseFunctionExpression, SubExpressionRight::functionExpression) 140 .thenTry(this::parseWildcardExpression, SubExpressionRight::wildcardExpression) 141 .parse(dotPosition + 1, endPosition); 142 143 if (!rightSide.hasResult()) { 144 continue; 145 } 146 147 return ParseResult.success(new SubExpression(leftSide.result(), rightSide.result())); 148 } 149 150 logError("sub-expression", "Invalid sub-expression", startPosition); 151 return ParseResult.error(); 152 } 153 154 /** 155 * pipe-expression = expression "|" expression 156 */ parsePipeExpression(int startPosition, int endPosition)157 private ParseResult<PipeExpression> parsePipeExpression(int startPosition, int endPosition) { 158 return parseBinaryExpression(startPosition, endPosition, "|", PipeExpression::new); 159 } 160 161 /** 162 * or-expression = expression "||" expression 163 */ parseOrExpression(int startPosition, int endPosition)164 private ParseResult<OrExpression> parseOrExpression(int startPosition, int endPosition) { 165 return parseBinaryExpression(startPosition, endPosition, "||", OrExpression::new); 166 } 167 168 /** 169 * and-expression = expression "&&" expression 170 */ parseAndExpression(int startPosition, int endPosition)171 private ParseResult<AndExpression> parseAndExpression(int startPosition, int endPosition) { 172 return parseBinaryExpression(startPosition, endPosition, "&&", AndExpression::new); 173 } 174 parseBinaryExpression(int startPosition, int endPosition, String delimiter, BiFunction<Expression, Expression, T> constructor)175 private <T> ParseResult<T> parseBinaryExpression(int startPosition, int endPosition, String delimiter, 176 BiFunction<Expression, Expression, T> constructor) { 177 startPosition = trimLeftWhitespace(startPosition, endPosition); 178 endPosition = trimRightWhitespace(startPosition, endPosition); 179 180 List<Integer> delimiterPositions = findCharacters(startPosition + 1, endPosition - 1, delimiter); 181 for (Integer delimiterPosition : delimiterPositions) { 182 ParseResult<Expression> leftSide = parseExpression(startPosition, delimiterPosition); 183 if (!leftSide.hasResult()) { 184 continue; 185 } 186 187 ParseResult<Expression> rightSide = parseExpression(delimiterPosition + delimiter.length(), endPosition); 188 if (!rightSide.hasResult()) { 189 continue; 190 } 191 192 return ParseResult.success(constructor.apply(leftSide.result(), rightSide.result())); 193 } 194 195 logError("binary-expression", "Invalid binary-expression", startPosition); 196 return ParseResult.error(); 197 } 198 199 /** 200 * not-expression = "!" expression 201 */ parseNotExpression(int startPosition, int endPosition)202 private ParseResult<NotExpression> parseNotExpression(int startPosition, int endPosition) { 203 startPosition = trimLeftWhitespace(startPosition, endPosition); 204 endPosition = trimRightWhitespace(startPosition, endPosition); 205 206 if (!startsWith(startPosition, '!')) { 207 logError("not-expression", "Expected '!'", startPosition); 208 return ParseResult.error(); 209 } 210 211 return parseExpression(startPosition + 1, endPosition).mapResult(NotExpression::new); 212 } 213 214 /** 215 * paren-expression = "(" expression ")" 216 */ parseParenExpression(int startPosition, int endPosition)217 private ParseResult<ParenExpression> parseParenExpression(int startPosition, int endPosition) { 218 startPosition = trimLeftWhitespace(startPosition, endPosition); 219 endPosition = trimRightWhitespace(startPosition, endPosition); 220 221 if (!startsAndEndsWith(startPosition, endPosition, '(', ')')) { 222 logError("paren-expression", "Expected '(' and ')'", startPosition); 223 return ParseResult.error(); 224 } 225 226 return parseExpression(startPosition + 1, endPosition - 1).mapResult(ParenExpression::new); 227 } 228 229 /** 230 * index-expression = expression bracket-specifier / bracket-specifier 231 */ parseIndexExpression(int startPosition, int endPosition)232 private ParseResult<IndexExpression> parseIndexExpression(int startPosition, int endPosition) { 233 startPosition = trimLeftWhitespace(startPosition, endPosition); 234 endPosition = trimRightWhitespace(startPosition, endPosition); 235 236 return CompositeParser.firstTry(this::parseIndexExpressionWithLhsExpression) 237 .thenTry(this::parseBracketSpecifier, b -> IndexExpression.indexExpression(null, b)) 238 .parse(startPosition, endPosition); 239 } 240 241 /** 242 * expression bracket-specifier 243 */ parseIndexExpressionWithLhsExpression(int startPosition, int endPosition)244 private ParseResult<IndexExpression> parseIndexExpressionWithLhsExpression(int startPosition, int endPosition) { 245 startPosition = trimLeftWhitespace(startPosition, endPosition); 246 endPosition = trimRightWhitespace(startPosition, endPosition); 247 248 List<Integer> bracketPositions = findCharacters(startPosition + 1, endPosition - 1, "["); 249 for (Integer bracketPosition : bracketPositions) { 250 ParseResult<Expression> leftSide = parseExpression(startPosition, bracketPosition); 251 if (!leftSide.hasResult()) { 252 continue; 253 } 254 255 ParseResult<BracketSpecifier> rightSide = parseBracketSpecifier(bracketPosition, endPosition); 256 if (!rightSide.hasResult()) { 257 continue; 258 } 259 260 return ParseResult.success(IndexExpression.indexExpression(leftSide.result(), rightSide.result())); 261 } 262 263 logError("index-expression with lhs-expression", "Invalid index-expression with lhs-expression", startPosition); 264 return ParseResult.error(); 265 } 266 267 /** 268 * multi-select-list = "[" ( expression *( "," expression ) ) "]" 269 */ parseMultiSelectList(int startPosition, int endPosition)270 private ParseResult<MultiSelectList> parseMultiSelectList(int startPosition, int endPosition) { 271 return parseMultiSelect(startPosition, endPosition, '[', ']', this::parseExpression) 272 .mapResult(MultiSelectList::new); 273 } 274 275 /** 276 * multi-select-hash = "{" ( keyval-expr *( "," keyval-expr ) ) "}" 277 */ parseMultiSelectHash(int startPosition, int endPosition)278 private ParseResult<MultiSelectHash> parseMultiSelectHash(int startPosition, int endPosition) { 279 return parseMultiSelect(startPosition, endPosition, '{', '}', this::parseKeyValueExpression) 280 .mapResult(MultiSelectHash::new); 281 } 282 283 /** 284 * Parses "startDelimiter" ( entryParserType *( "," entryParserType ) ) "endDelimiter" 285 * <p> 286 * Used by {@link #parseMultiSelectHash}, {@link #parseMultiSelectList}. 287 */ parseMultiSelect(int startPosition, int endPosition, char startDelimiter, char endDelimiter, Parser<T> entryParser)288 private <T> ParseResult<List<T>> parseMultiSelect(int startPosition, int endPosition, 289 char startDelimiter, char endDelimiter, 290 Parser<T> entryParser) { 291 startPosition = trimLeftWhitespace(startPosition, endPosition); 292 endPosition = trimRightWhitespace(startPosition, endPosition); 293 294 if (!startsAndEndsWith(startPosition, endPosition, startDelimiter, endDelimiter)) { 295 logError("multi-select", "Expected '" + startDelimiter + "' and '" + endDelimiter + "'", startPosition); 296 return ParseResult.error(); 297 } 298 299 List<Integer> commaPositions = findCharacters(startPosition + 1, endPosition - 1, ","); 300 301 if (commaPositions.isEmpty()) { 302 return entryParser.parse(startPosition + 1, endPosition - 1).mapResult(Collections::singletonList); 303 } 304 305 List<T> results = new ArrayList<>(); 306 307 // Find first valid entries before a comma 308 int startOfSecondEntry = -1; 309 for (Integer comma : commaPositions) { 310 ParseResult<T> result = entryParser.parse(startPosition + 1, comma); 311 if (!result.hasResult()) { 312 continue; 313 } 314 315 results.add(result.result()); 316 startOfSecondEntry = comma + 1; 317 } 318 319 if (results.size() == 0) { 320 logError("multi-select", "Invalid value", startPosition + 1); 321 return ParseResult.error(); 322 } 323 324 if (results.size() > 1) { 325 logError("multi-select", "Ambiguous separation", startPosition); 326 return ParseResult.error(); 327 } 328 329 // Find any subsequent entries 330 int startPositionAfterComma = startOfSecondEntry; 331 for (Integer commaPosition : commaPositions) { 332 if (startPositionAfterComma > commaPosition) { 333 continue; 334 } 335 336 ParseResult<T> entry = entryParser.parse(startPositionAfterComma, commaPosition); 337 if (!entry.hasResult()) { 338 continue; 339 } 340 341 results.add(entry.result()); 342 343 startPositionAfterComma = commaPosition + 1; 344 } 345 346 ParseResult<T> entry = entryParser.parse(startPositionAfterComma, endPosition - 1); 347 if (!entry.hasResult()) { 348 logError("multi-select", "Ambiguous separation", startPosition); 349 return ParseResult.error(); 350 } 351 results.add(entry.result()); 352 353 return ParseResult.success(results); 354 } 355 356 /** 357 * keyval-expr = identifier ":" expression 358 */ parseKeyValueExpression(int startPosition, int endPosition)359 private ParseResult<KeyValueExpression> parseKeyValueExpression(int startPosition, int endPosition) { 360 startPosition = trimLeftWhitespace(startPosition, endPosition); 361 endPosition = trimRightWhitespace(startPosition, endPosition); 362 363 List<Integer> delimiterPositions = findCharacters(startPosition + 1, endPosition - 1, ":"); 364 for (Integer delimiterPosition : delimiterPositions) { 365 ParseResult<String> identifier = parseIdentifier(startPosition, delimiterPosition); 366 if (!identifier.hasResult()) { 367 continue; 368 } 369 370 ParseResult<Expression> expression = parseExpression(delimiterPosition + 1, endPosition); 371 if (!expression.hasResult()) { 372 continue; 373 } 374 375 return ParseResult.success(new KeyValueExpression(identifier.result(), expression.result())); 376 } 377 378 logError("keyval-expr", "Invalid keyval-expr", startPosition); 379 return ParseResult.error(); 380 } 381 382 /** 383 * bracket-specifier = "[" (number / "*" / slice-expression) "]" / "[]" 384 * bracket-specifier =/ "[?" expression "]" 385 */ parseBracketSpecifier(int startPosition, int endPosition)386 private ParseResult<BracketSpecifier> parseBracketSpecifier(int startPosition, int endPosition) { 387 startPosition = trimLeftWhitespace(startPosition, endPosition); 388 endPosition = trimRightWhitespace(startPosition, endPosition); 389 390 if (!startsAndEndsWith(startPosition, endPosition, '[', ']')) { 391 logError("bracket-specifier", "Expecting '[' and ']'", startPosition); 392 return ParseResult.error(); 393 } 394 395 // "[]" 396 if (charsInRange(startPosition, endPosition) == 2) { 397 return ParseResult.success(BracketSpecifier.withoutContents()); 398 } 399 400 // "[?" expression "]" 401 if (input.charAt(startPosition + 1) == '?') { 402 return parseExpression(startPosition + 2, endPosition - 1) 403 .mapResult(e -> BracketSpecifier.withQuestionMark(new BracketSpecifierWithQuestionMark(e))); 404 } 405 406 // "[" (number / "*" / slice-expression) "]" 407 return CompositeParser.firstTry(this::parseNumber, BracketSpecifier::withNumberContents) 408 .thenTry(this::parseWildcardExpression, BracketSpecifier::withWildcardExpressionContents) 409 .thenTry(this::parseSliceExpression, BracketSpecifier::withSliceExpressionContents) 410 .parse(startPosition + 1, endPosition - 1); 411 } 412 413 /** 414 * comparator-expression = expression comparator expression 415 */ parseComparatorExpression(int startPosition, int endPosition)416 private ParseResult<ComparatorExpression> parseComparatorExpression(int startPosition, int endPosition) { 417 startPosition = trimLeftWhitespace(startPosition, endPosition); 418 endPosition = trimRightWhitespace(startPosition, endPosition); 419 420 for (Comparator comparator : Comparator.values()) { 421 List<Integer> comparatorPositions = findCharacters(startPosition, endPosition, comparator.tokenSymbol()); 422 423 for (Integer comparatorPosition : comparatorPositions) { 424 ParseResult<Expression> lhsExpression = parseExpression(startPosition, comparatorPosition); 425 if (!lhsExpression.hasResult()) { 426 continue; 427 } 428 429 ParseResult<Expression> rhsExpression = 430 parseExpression(comparatorPosition + comparator.tokenSymbol().length(), endPosition); 431 if (!rhsExpression.hasResult()) { 432 continue; 433 } 434 435 return ParseResult.success(new ComparatorExpression(lhsExpression.result(), 436 comparator, 437 rhsExpression.result())); 438 } 439 } 440 441 442 logError("comparator-expression", "Invalid comparator expression", startPosition); 443 return ParseResult.error(); 444 } 445 446 /** 447 * slice-expression = [number] ":" [number] [ ":" [number] ] 448 */ parseSliceExpression(int startPosition, int endPosition)449 private ParseResult<SliceExpression> parseSliceExpression(int startPosition, int endPosition) { 450 startPosition = trimLeftWhitespace(startPosition, endPosition); 451 endPosition = trimRightWhitespace(startPosition, endPosition); 452 453 // Find the first colon 454 int firstColonIndex = input.indexOf(':', startPosition); 455 if (firstColonIndex < 0 || firstColonIndex >= endPosition) { 456 logError("slice-expression", "Expected slice expression", startPosition); 457 return ParseResult.error(); 458 } 459 460 // Find the second colon (if it exists) 461 int maybeSecondColonIndex = input.indexOf(':', firstColonIndex + 1); 462 OptionalInt secondColonIndex = maybeSecondColonIndex < 0 || maybeSecondColonIndex >= endPosition 463 ? OptionalInt.empty() 464 : OptionalInt.of(maybeSecondColonIndex); 465 466 // Find the first number bounds (if it exists) 467 int firstNumberStart = startPosition; 468 int firstNumberEnd = firstColonIndex; 469 470 // Find the second number bounds (if it exists) 471 int secondNumberStart = firstColonIndex + 1; 472 int secondNumberEnd = secondColonIndex.orElse(endPosition); 473 474 // Find the third number bounds (if it exists) 475 int thirdNumberStart = secondColonIndex.orElse(endPosition) + 1; 476 int thirdNumberEnd = endPosition; 477 478 // Parse the first number (if it exists) 479 Optional<Integer> firstNumber = Optional.empty(); 480 if (firstNumberStart < firstNumberEnd) { 481 ParseResult<Integer> firstNumberParse = parseNumber(firstNumberStart, firstNumberEnd); 482 if (!firstNumberParse.hasResult()) { 483 return ParseResult.error(); 484 } 485 firstNumber = Optional.of(firstNumberParse.result()); 486 } 487 488 // Parse the second number (if it exists) 489 Optional<Integer> secondNumber = Optional.empty(); 490 if (secondNumberStart < secondNumberEnd) { 491 ParseResult<Integer> secondNumberParse = parseNumber(secondNumberStart, secondNumberEnd); 492 if (!secondNumberParse.hasResult()) { 493 return ParseResult.error(); 494 } 495 secondNumber = Optional.of(secondNumberParse.result()); 496 } 497 498 // Parse the third number (if it exists) 499 Optional<Integer> thirdNumber = Optional.empty(); 500 if (thirdNumberStart < thirdNumberEnd) { 501 ParseResult<Integer> thirdNumberParse = parseNumber(thirdNumberStart, thirdNumberEnd); 502 if (!thirdNumberParse.hasResult()) { 503 return ParseResult.error(); 504 } 505 thirdNumber = Optional.of(thirdNumberParse.result()); 506 } 507 508 return ParseResult.success(new SliceExpression(firstNumber.orElse(null), 509 secondNumber.orElse(null), 510 thirdNumber.orElse(null))); 511 } 512 513 /** 514 * function-expression = unquoted-string ( no-args / one-or-more-args ) 515 */ parseFunctionExpression(int startPosition, int endPosition)516 private ParseResult<FunctionExpression> parseFunctionExpression(int startPosition, int endPosition) { 517 startPosition = trimLeftWhitespace(startPosition, endPosition); 518 endPosition = trimRightWhitespace(startPosition, endPosition); 519 520 int paramIndex = input.indexOf('(', startPosition); 521 if (paramIndex <= 0) { 522 logError("function-expression", "Expected function", startPosition); 523 return ParseResult.error(); 524 } 525 526 ParseResult<String> functionNameParse = parseUnquotedString(startPosition, paramIndex); 527 if (!functionNameParse.hasResult()) { 528 logError("function-expression", "Expected valid function name", startPosition); 529 return ParseResult.error(); 530 } 531 532 return CompositeParser.firstTry(this::parseNoArgs) 533 .thenTry(this::parseOneOrMoreArgs) 534 .parse(paramIndex, endPosition) 535 .mapResult(args -> new FunctionExpression(functionNameParse.result(), args)); 536 } 537 538 /** 539 * no-args = "(" ")" 540 */ parseNoArgs(int startPosition, int endPosition)541 private ParseResult<List<FunctionArg>> parseNoArgs(int startPosition, int endPosition) { 542 startPosition = trimLeftWhitespace(startPosition, endPosition); 543 endPosition = trimRightWhitespace(startPosition, endPosition); 544 545 if (!startsWith(startPosition, '(')) { 546 logError("no-args", "Expected '('", startPosition); 547 return ParseResult.error(); 548 } 549 550 int closePosition = trimLeftWhitespace(startPosition + 1, endPosition); 551 552 if (input.charAt(closePosition) != ')') { 553 logError("no-args", "Expected ')'", closePosition); 554 return ParseResult.error(); 555 } 556 557 if (closePosition + 1 != endPosition) { 558 logError("no-args", "Unexpected character", closePosition + 1); 559 return ParseResult.error(); 560 } 561 562 return ParseResult.success(Collections.emptyList()); 563 } 564 565 /** 566 * one-or-more-args = "(" ( function-arg *( "," function-arg ) ) ")" 567 */ parseOneOrMoreArgs(int startPosition, int endPosition)568 private ParseResult<List<FunctionArg>> parseOneOrMoreArgs(int startPosition, int endPosition) { 569 return parseMultiSelect(startPosition, endPosition, '(', ')', this::parseFunctionArg); 570 } 571 572 /** 573 * function-arg = expression / expression-type 574 */ parseFunctionArg(int startPosition, int endPosition)575 private ParseResult<FunctionArg> parseFunctionArg(int startPosition, int endPosition) { 576 return CompositeParser.firstTry(this::parseExpression, FunctionArg::expression) 577 .thenTry(this::parseExpressionType, FunctionArg::expressionType) 578 .parse(startPosition, endPosition); 579 } 580 581 /** 582 * current-node = "@" 583 */ parseCurrentNode(int startPosition, int endPosition)584 private ParseResult<CurrentNode> parseCurrentNode(int startPosition, int endPosition) { 585 startPosition = trimLeftWhitespace(startPosition, endPosition); 586 endPosition = trimRightWhitespace(startPosition, endPosition); 587 588 return parseExpectedToken("current-node", startPosition, endPosition, '@').mapResult(x -> new CurrentNode()); 589 } 590 591 /** 592 * expression-type = "&" expression 593 */ parseExpressionType(int startPosition, int endPosition)594 private ParseResult<ExpressionType> parseExpressionType(int startPosition, int endPosition) { 595 startPosition = trimLeftWhitespace(startPosition, endPosition); 596 endPosition = trimRightWhitespace(startPosition, endPosition); 597 598 if (!startsWith(startPosition, '&')) { 599 logError("expression-type", "Expected '&'", startPosition); 600 return ParseResult.error(); 601 } 602 603 return parseExpression(startPosition + 1, endPosition).mapResult(ExpressionType::new); 604 } 605 606 /** 607 * raw-string = "'" *raw-string-char "'" 608 */ parseRawString(int startPosition, int endPosition)609 private ParseResult<String> parseRawString(int startPosition, int endPosition) { 610 startPosition = trimLeftWhitespace(startPosition, endPosition); 611 endPosition = trimRightWhitespace(startPosition, endPosition); 612 613 if (charsInRange(startPosition, endPosition) < 2) { 614 logError("raw-string", "Invalid length", startPosition); 615 return ParseResult.error(); 616 } 617 618 if (!startsAndEndsWith(startPosition, endPosition, '\'', '\'')) { 619 logError("raw-string", "Expected opening and closing \"'\"", startPosition); 620 return ParseResult.error(); 621 } 622 623 if (charsInRange(startPosition, endPosition) == 2) { 624 return ParseResult.success(""); 625 } 626 627 return parseRawStringChars(startPosition + 1, endPosition - 1); 628 } 629 630 /** 631 * raw-string-char = (%x20-26 / %x28-5B / %x5D-10FFFF) / preserved-escape / raw-string-escape 632 */ parseRawStringChars(int startPosition, int endPosition)633 private ParseResult<String> parseRawStringChars(int startPosition, int endPosition) { 634 StringBuilder result = new StringBuilder(); 635 for (int i = startPosition; i < endPosition; i++) { 636 ParseResult<String> rawStringChar = parseLegalRawStringChar(i, i + 1); 637 if (rawStringChar.hasResult()) { 638 result.append(rawStringChar.result()); 639 continue; 640 } 641 642 ParseResult<String> preservedEscape = parsePreservedEscape(i, i + 2); 643 if (preservedEscape.hasResult()) { 644 result.append(preservedEscape.result()); 645 ++i; 646 continue; 647 } 648 649 ParseResult<String> rawStringEscape = parseRawStringEscape(i, i + 2); 650 if (rawStringEscape.hasResult()) { 651 result.append(rawStringEscape.result()); 652 ++i; 653 continue; 654 } 655 656 logError("raw-string", "Unexpected character", i); 657 return ParseResult.error(); 658 } 659 660 return ParseResult.success(result.toString()); 661 } 662 663 /** 664 * %x20-26 / %x28-5B / %x5D-10FFFF 665 */ parseLegalRawStringChar(int startPosition, int endPosition)666 private ParseResult<String> parseLegalRawStringChar(int startPosition, int endPosition) { 667 if (charsInRange(startPosition, endPosition) != 1) { 668 logError("raw-string-chars", "Invalid bounds", startPosition); 669 return ParseResult.error(); 670 } 671 672 if (!isLegalRawStringChar(input.charAt(startPosition))) { 673 logError("raw-string-chars", "Invalid character in sequence", startPosition); 674 return ParseResult.error(); 675 } 676 677 return ParseResult.success(input.substring(startPosition, endPosition)); 678 } 679 isLegalRawStringChar(char c)680 private boolean isLegalRawStringChar(char c) { 681 return (c >= 0x20 && c <= 0x26) || 682 (c >= 0x28 && c <= 0x5B) || 683 (c >= 0x5D); 684 } 685 686 /** 687 * preserved-escape = escape (%x20-26 / %28-5B / %x5D-10FFFF) 688 */ parsePreservedEscape(int startPosition, int endPosition)689 private ParseResult<String> parsePreservedEscape(int startPosition, int endPosition) { 690 if (endPosition > input.length()) { 691 logError("preserved-escape", "Invalid end position", startPosition); 692 return ParseResult.error(); 693 } 694 695 if (charsInRange(startPosition, endPosition) != 2) { 696 logError("preserved-escape", "Invalid length", startPosition); 697 return ParseResult.error(); 698 } 699 700 if (!startsWith(startPosition, '\\')) { 701 logError("preserved-escape", "Expected \\", startPosition); 702 return ParseResult.error(); 703 } 704 705 return parseLegalRawStringChar(startPosition + 1, endPosition).mapResult(v -> "\\" + v); 706 } 707 708 /** 709 * raw-string-escape = escape ("'" / escape) 710 */ parseRawStringEscape(int startPosition, int endPosition)711 private ParseResult<String> parseRawStringEscape(int startPosition, int endPosition) { 712 if (endPosition > input.length()) { 713 logError("preserved-escape", "Invalid end position", startPosition); 714 return ParseResult.error(); 715 } 716 717 if (charsInRange(startPosition, endPosition) != 2) { 718 logError("raw-string-escape", "Invalid length", startPosition); 719 return ParseResult.error(); 720 } 721 722 if (!startsWith(startPosition, '\\')) { 723 logError("raw-string-escape", "Expected '\\'", startPosition); 724 return ParseResult.error(); 725 } 726 727 if (input.charAt(startPosition + 1) != '\'' && input.charAt(startPosition + 1) != '\\') { 728 logError("raw-string-escape", "Expected \"'\" or \"\\\"", startPosition); 729 return ParseResult.error(); 730 } 731 732 return ParseResult.success(input.substring(startPosition, endPosition)); 733 } 734 735 /** 736 * literal = "`" json-value "`" 737 */ parseLiteral(int startPosition, int endPosition)738 private ParseResult<Literal> parseLiteral(int startPosition, int endPosition) { 739 startPosition = trimLeftWhitespace(startPosition, endPosition); 740 endPosition = trimRightWhitespace(startPosition, endPosition); 741 742 if (charsInRange(startPosition, endPosition) < 2) { 743 logError("literal", "Invalid bounds", startPosition); 744 return ParseResult.error(); 745 } 746 747 if (!startsAndEndsWith(startPosition, endPosition, '`', '`')) { 748 logError("literal", "Expected opening and closing '`'", startPosition); 749 return ParseResult.error(); 750 } 751 752 StringBuilder jsonString = new StringBuilder(); 753 for (int i = startPosition + 1; i < endPosition - 1; i++) { 754 char character = input.charAt(i); 755 if (character == '`') { 756 int lastChar = i - 1; 757 if (lastChar <= 0) { 758 logError("literal", "Unexpected '`'", startPosition); 759 return ParseResult.error(); 760 } 761 762 int escapeCount = 0; 763 for (int j = i - 1; j >= startPosition; j--) { 764 if (input.charAt(j) == '\\') { 765 ++escapeCount; 766 } else { 767 break; 768 } 769 } 770 771 if (escapeCount % 2 == 0) { 772 logError("literal", "Unescaped '`'", startPosition); 773 return ParseResult.error(); 774 } 775 776 jsonString.setLength(jsonString.length() - 1); // Remove escape. 777 jsonString.append('`'); 778 } else { 779 jsonString.append(character); 780 } 781 } 782 783 try { 784 return ParseResult.success(new Literal(Jackson.readJrsValue(jsonString.toString()))); 785 } catch (IOException e) { 786 logError("literal", "Invalid JSON: " + e.getMessage(), startPosition); 787 return ParseResult.error(); 788 } 789 } 790 791 /** 792 * number = ["-"]1*digit 793 * digit = %x30-39 794 */ parseNumber(int startPosition, int endPosition)795 private ParseResult<Integer> parseNumber(int startPosition, int endPosition) { 796 startPosition = trimLeftWhitespace(startPosition, endPosition); 797 endPosition = trimRightWhitespace(startPosition, endPosition); 798 799 if (startsWith(startPosition, '-')) { 800 return parseNonNegativeNumber(startPosition + 1, endPosition).mapResult(i -> -i); 801 } 802 803 return parseNonNegativeNumber(startPosition, endPosition); 804 } 805 parseNonNegativeNumber(int startPosition, int endPosition)806 private ParseResult<Integer> parseNonNegativeNumber(int startPosition, int endPosition) { 807 startPosition = trimLeftWhitespace(startPosition, endPosition); 808 endPosition = trimRightWhitespace(startPosition, endPosition); 809 810 if (charsInRange(startPosition, endPosition) < 1) { 811 logError("number", "Expected number", startPosition); 812 return ParseResult.error(); 813 } 814 815 try { 816 return ParseResult.success(Integer.parseInt(input.substring(startPosition, endPosition))); 817 } catch (NumberFormatException e) { 818 logError("number", "Expected number", startPosition); 819 return ParseResult.error(); 820 } 821 } 822 823 /** 824 * identifier = unquoted-string / quoted-string 825 */ parseIdentifier(int startPosition, int endPosition)826 private ParseResult<String> parseIdentifier(int startPosition, int endPosition) { 827 return CompositeParser.firstTry(this::parseUnquotedString) 828 .thenTry(this::parseQuotedString) 829 .parse(startPosition, endPosition); 830 } 831 832 /** 833 * unquoted-string = (%x41-5A / %x61-7A / %x5F) *( ; A-Za-z_ 834 * %x30-39 / ; 0-9 835 * %x41-5A / ; A-Z 836 * %x5F / ; _ 837 * %x61-7A) ; a-z 838 */ parseUnquotedString(int startPosition, int endPosition)839 private ParseResult<String> parseUnquotedString(int startPosition, int endPosition) { 840 startPosition = trimLeftWhitespace(startPosition, endPosition); 841 endPosition = trimRightWhitespace(startPosition, endPosition); 842 843 if (charsInRange(startPosition, endPosition) < 1) { 844 logError("unquoted-string", "Invalid unquoted-string", startPosition); 845 return ParseResult.error(); 846 } 847 848 char firstToken = input.charAt(startPosition); 849 if (!Character.isLetter(firstToken) && firstToken != '_') { 850 logError("unquoted-string", "Unescaped strings must start with [A-Za-z_]", startPosition); 851 return ParseResult.error(); 852 } 853 854 for (int i = startPosition; i < endPosition; i++) { 855 char c = input.charAt(i); 856 if (!Character.isLetterOrDigit(c) && c != '_') { 857 logError("unquoted-string", "Invalid character in unescaped-string", i); 858 return ParseResult.error(); 859 } 860 } 861 862 return ParseResult.success(input.substring(startPosition, endPosition)); 863 } 864 865 /** 866 * quoted-string = quote 1*(unescaped-char / escaped-char) quote 867 * quote = '"' 868 */ parseQuotedString(int startPosition, int endPosition)869 private ParseResult<String> parseQuotedString(int startPosition, int endPosition) { 870 startPosition = trimLeftWhitespace(startPosition, endPosition); 871 endPosition = trimRightWhitespace(startPosition, endPosition); 872 873 if (!startsAndEndsWith(startPosition, endPosition, '"', '"')) { 874 logError("quoted-string", "Expected opening and closing '\"'", startPosition); 875 return ParseResult.error(); 876 } 877 878 int stringStart = startPosition + 1; 879 int stringEnd = endPosition - 1; 880 881 int stringTokenCount = charsInRange(stringStart, stringEnd); 882 if (stringTokenCount < 1) { 883 logError("quoted-string", "Invalid quoted-string", startPosition); 884 return ParseResult.error(); 885 } 886 887 StringBuilder result = new StringBuilder(); 888 for (int i = stringStart; i < stringEnd; i++) { 889 ParseResult<String> unescapedChar = parseUnescapedChar(i, i + 1); 890 if (unescapedChar.hasResult()) { 891 result.append(unescapedChar.result()); 892 continue; 893 } 894 895 ParseResult<String> escapedChar = parseEscapedChar(i, i + 2); 896 if (escapedChar.hasResult()) { 897 result.append(escapedChar.result()); 898 ++i; 899 continue; 900 } 901 902 ParseResult<String> escapedUnicodeSequence = parseEscapedUnicodeSequence(i, i + 6); 903 if (escapedUnicodeSequence.hasResult()) { 904 result.append(escapedUnicodeSequence.result()); 905 i += 5; 906 continue; 907 } 908 909 if (input.charAt(i) == '\\') { 910 logError("quoted-string", "Unsupported escape sequence", i); 911 } else { 912 logError("quoted-string", "Unexpected character", i); 913 } 914 return ParseResult.error(); 915 } 916 917 return ParseResult.success(result.toString()); 918 } 919 920 /** 921 * unescaped-char = %x20-21 / %x23-5B / %x5D-10FFFF 922 */ parseUnescapedChar(int startPosition, int endPosition)923 private ParseResult<String> parseUnescapedChar(int startPosition, int endPosition) { 924 for (int i = startPosition; i < endPosition; i++) { 925 if (!isLegalUnescapedChar(input.charAt(i))) { 926 logError("unescaped-char", "Invalid character in sequence", startPosition); 927 return ParseResult.error(); 928 } 929 } 930 931 return ParseResult.success(input.substring(startPosition, endPosition)); 932 } 933 isLegalUnescapedChar(char c)934 private boolean isLegalUnescapedChar(char c) { 935 return (c >= 0x20 && c <= 0x21) || 936 (c >= 0x23 && c <= 0x5B) || 937 (c >= 0x5D); 938 } 939 940 /** 941 * escaped-char = escape ( 942 * %x22 / ; " quotation mark U+0022 943 * %x5C / ; \ reverse solidus U+005C 944 * %x2F / ; / solidus U+002F 945 * %x62 / ; b backspace U+0008 946 * %x66 / ; f form feed U+000C 947 * %x6E / ; n line feed U+000A 948 * %x72 / ; r carriage return U+000D 949 * %x74 / ; t tab U+0009 950 * %x75 4HEXDIG ) ; uXXXX U+XXXX (this is handled as part of parseEscapedUnicodeSequence) 951 */ parseEscapedChar(int startPosition, int endPosition)952 private ParseResult<String> parseEscapedChar(int startPosition, int endPosition) { 953 if (endPosition > input.length()) { 954 logError("escaped-char", "Invalid end position", startPosition); 955 return ParseResult.error(); 956 } 957 958 if (charsInRange(startPosition, endPosition) != 2) { 959 logError("escaped-char", "Invalid length", startPosition); 960 return ParseResult.error(); 961 } 962 963 if (!startsWith(startPosition, '\\')) { 964 logError("escaped-char", "Expected '\\'", startPosition); 965 return ParseResult.error(); 966 } 967 968 char escapedChar = input.charAt(startPosition + 1); 969 switch (escapedChar) { 970 case '"': return ParseResult.success("\""); 971 case '\\': return ParseResult.success("\\"); 972 case '/': return ParseResult.success("/"); 973 case 'b': return ParseResult.success("\b"); 974 case 'f': return ParseResult.success("\f"); 975 case 'n': return ParseResult.success("\n"); 976 case 'r': return ParseResult.success("\r"); 977 case 't': return ParseResult.success("\t"); 978 default: 979 logError("escaped-char", "Invalid escape sequence", startPosition); 980 return ParseResult.error(); 981 } 982 } 983 parseEscapedUnicodeSequence(int startPosition, int endPosition)984 private ParseResult<String> parseEscapedUnicodeSequence(int startPosition, int endPosition) { 985 if (endPosition > input.length()) { 986 logError("escaped-unicode-sequence", "Invalid end position", startPosition); 987 return ParseResult.error(); 988 } 989 990 if (charsInRange(startPosition, endPosition) != 6) { 991 logError("escaped-unicode-sequence", "Invalid length", startPosition); 992 return ParseResult.error(); 993 } 994 995 if (input.charAt(startPosition) != '\\') { 996 logError("escaped-unicode-sequence", "Expected '\\'", startPosition); 997 return ParseResult.error(); 998 } 999 1000 char escapedChar = input.charAt(startPosition + 1); 1001 if (escapedChar != 'u') { 1002 logError("escaped-unicode-sequence", "Invalid escape sequence", startPosition); 1003 return ParseResult.error(); 1004 } 1005 1006 String unicodePattern = input.substring(startPosition + 2, startPosition + 2 + 4); 1007 char unicodeChar; 1008 try { 1009 unicodeChar = (char) Integer.parseInt(unicodePattern, 16); 1010 } catch (NumberFormatException e) { 1011 logError("escaped-unicode-sequence", "Invalid unicode hex sequence", startPosition); 1012 return ParseResult.error(); 1013 } 1014 1015 return ParseResult.success(String.valueOf(unicodeChar)); 1016 } 1017 1018 /** 1019 * "*" 1020 */ parseWildcardExpression(int startPosition, int endPosition)1021 private ParseResult<WildcardExpression> parseWildcardExpression(int startPosition, int endPosition) { 1022 return parseExpectedToken("star-expression", startPosition, endPosition, '*').mapResult(v -> new WildcardExpression()); 1023 } 1024 charsInRange(int startPosition, int endPosition)1025 private int charsInRange(int startPosition, int endPosition) { 1026 return endPosition - startPosition; 1027 } 1028 findCharacters(int startPosition, int endPosition, String symbol)1029 private List<Integer> findCharacters(int startPosition, int endPosition, String symbol) { 1030 List<Integer> results = new ArrayList<>(); 1031 1032 int start = startPosition; 1033 while (true) { 1034 int match = input.indexOf(symbol, start); 1035 if (match < 0 || match >= endPosition) { 1036 break; 1037 } 1038 results.add(match); 1039 start = match + 1; 1040 } 1041 1042 return results; 1043 } 1044 parseExpectedToken(String parser, int startPosition, int endPosition, char expectedToken)1045 private ParseResult<Character> parseExpectedToken(String parser, int startPosition, int endPosition, char expectedToken) { 1046 if (input.charAt(startPosition) != expectedToken) { 1047 logError(parser, "Expected '" + expectedToken + "'", startPosition); 1048 return ParseResult.error(); 1049 } 1050 1051 if (charsInRange(startPosition, endPosition) != 1) { 1052 logError(parser, "Unexpected character", startPosition + 1); 1053 return ParseResult.error(); 1054 } 1055 1056 return ParseResult.success(expectedToken); 1057 } 1058 trimLeftWhitespace(int startPosition, int endPosition)1059 private int trimLeftWhitespace(int startPosition, int endPosition) { 1060 while (input.charAt(startPosition) == ' ' && startPosition < endPosition - 1) { 1061 ++startPosition; 1062 } 1063 1064 return startPosition; 1065 } 1066 trimRightWhitespace(int startPosition, int endPosition)1067 private int trimRightWhitespace(int startPosition, int endPosition) { 1068 while (input.charAt(endPosition - 1) == ' ' && startPosition < endPosition - 1) { 1069 --endPosition; 1070 } 1071 1072 return endPosition; 1073 } 1074 startsWith(int startPosition, char character)1075 private boolean startsWith(int startPosition, char character) { 1076 return input.charAt(startPosition) == character; 1077 } 1078 endsWith(int endPosition, char character)1079 private boolean endsWith(int endPosition, char character) { 1080 return input.charAt(endPosition - 1) == character; 1081 } 1082 startsAndEndsWith(int startPosition, int endPosition, char startChar, char endChar)1083 private boolean startsAndEndsWith(int startPosition, int endPosition, char startChar, char endChar) { 1084 return startsWith(startPosition, startChar) && endsWith(endPosition, endChar); 1085 } 1086 logError(String parser, String message, int position)1087 private void logError(String parser, String message, int position) { 1088 log.debug(() -> parser + " at " + position + ": " + message); 1089 } 1090 }