1/* 2 * Copyright (c) 2003, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package sun.reflect.generics.parser; 27 28import java.lang.reflect.GenericSignatureFormatError; 29import java.util.*; 30import sun.reflect.generics.tree.*; 31 32/** 33 * Parser for type signatures, as defined in the Java Virtual 34 * Machine Specification (JVMS) chapter 4. 35 * Converts the signatures into an abstract syntax tree (AST) representation. 36 * See the package sun.reflect.generics.tree for details of the AST. 37 */ 38public class SignatureParser { 39 // The input is conceptually a character stream (though currently it's 40 // a string). This is slightly different than traditional parsers, 41 // because there is no lexical scanner performing tokenization. 42 // Having a separate tokenizer does not fit with the nature of the 43 // input format. 44 // Other than the absence of a tokenizer, this parser is a classic 45 // recursive descent parser. Its structure corresponds as closely 46 // as possible to the grammar in the JVMS. 47 // 48 // A note on asserts vs. errors: The code contains assertions 49 // in situations that should never occur. An assertion failure 50 // indicates a failure of the parser logic. A common pattern 51 // is an assertion that the current input is a particular 52 // character. This is often paired with a separate check 53 // that this is the case, which seems redundant. For example: 54 // 55 // assert(current() != x); 56 // if (current != x {error("expected an x"); 57 // 58 // where x is some character constant. 59 // The assertion indicates, that, as currently written, 60 // the code should never reach this point unless the input is an 61 // x. On the other hand, the test is there to check the legality 62 // of the input wrt to a given production. It may be that at a later 63 // time the code might be called directly, and if the input is 64 // invalid, the parser should flag an error in accordance 65 // with its logic. 66 67 private String input; // the input signature 68 private int index; // index into the input 69 private int mark; // index of mark 70 // used to mark end of input 71 private static final char EOI = ':'; 72 private static final boolean DEBUG = false; 73 74 // private constructor - enforces use of static factory 75 private SignatureParser(){} 76 77 // prepares parser for new parsing session 78 private void init(String s) { 79 input = s; 80 mark = index = 0; 81 } 82 83 // Utility methods. 84 85 // Most parsing routines use the following routines to access the 86 // input stream, and advance it as necessary. 87 // This makes it easy to adapt the parser to operate on streams 88 // of various kinds as well as strings. 89 90 // returns current element of the input 91 private char current(){ 92 assert(index <= input.length()); 93 return index < input.length() ? input.charAt(index) : EOI; 94 } 95 96 // advance the input 97 private void advance(){ 98 assert(index <= input.length()); 99 if (index < input.length()) index++; 100 } 101 102 // mark current position 103 private void mark() { 104 mark = index; 105 } 106 107 // For debugging, prints current character to the end of the input. 108 private String remainder() { 109 return input.substring(index); 110 } 111 112 // returns a substring of input from mark (inclusive) 113 // to current position (exclusive) 114 private String markToCurrent() { 115 return input.substring(mark, index); 116 } 117 118 // Error handling routine. Encapsulates error handling. 119 // Takes a string error message as argument. 120 // Currently throws a GenericSignatureFormatError. 121 122 private Error error(String errorMsg) { 123 return new GenericSignatureFormatError("Signature Parse error: " + errorMsg + 124 "\n\tRemaining input: " + remainder()); 125 } 126 127 /** 128 * Verify the parse has made forward progress; throw an exception 129 * if no progress. 130 */ 131 private void progress(int startingPosition) { 132 if (index <= startingPosition) 133 throw error("Failure to make progress!"); 134 } 135 136 /** 137 * Static factory method. Produces a parser instance. 138 * @return an instance of {@code SignatureParser} 139 */ 140 public static SignatureParser make() { 141 return new SignatureParser(); 142 } 143 144 /** 145 * Parses a class signature (as defined in the JVMS, chapter 4) 146 * and produces an abstract syntax tree representing it. 147 * @param s a string representing the input class signature 148 * @return An abstract syntax tree for a class signature 149 * corresponding to the input string 150 * @throws GenericSignatureFormatError if the input is not a valid 151 * class signature 152 */ 153 public ClassSignature parseClassSig(String s) { 154 if (DEBUG) System.out.println("Parsing class sig:" + s); 155 init(s); 156 return parseClassSignature(); 157 } 158 159 /** 160 * Parses a method signature (as defined in the JVMS, chapter 4) 161 * and produces an abstract syntax tree representing it. 162 * @param s a string representing the input method signature 163 * @return An abstract syntax tree for a method signature 164 * corresponding to the input string 165 * @throws GenericSignatureFormatError if the input is not a valid 166 * method signature 167 */ 168 public MethodTypeSignature parseMethodSig(String s) { 169 if (DEBUG) System.out.println("Parsing method sig:" + s); 170 init(s); 171 return parseMethodTypeSignature(); 172 } 173 174 175 /** 176 * Parses a type signature 177 * and produces an abstract syntax tree representing it. 178 * 179 * @param s a string representing the input type signature 180 * @return An abstract syntax tree for a type signature 181 * corresponding to the input string 182 * @throws GenericSignatureFormatError if the input is not a valid 183 * type signature 184 */ 185 public TypeSignature parseTypeSig(String s) { 186 if (DEBUG) System.out.println("Parsing type sig:" + s); 187 init(s); 188 return parseTypeSignature(); 189 } 190 191 // Parsing routines. 192 // As a rule, the parsing routines access the input using the 193 // utilities current() and advance(). 194 // The convention is that when a parsing routine is invoked 195 // it expects the current input to be the first character it should parse 196 // and when it completes parsing, it leaves the input at the first 197 // character after the input parses. 198 199 /* 200 * Note on grammar conventions: a trailing "*" matches zero or 201 * more occurrences, a trailing "+" matches one or more occurrences, 202 * "_opt" indicates an optional component. 203 */ 204 205 /** 206 * ClassSignature: 207 * FormalTypeParameters_opt SuperclassSignature SuperinterfaceSignature* 208 */ 209 private ClassSignature parseClassSignature() { 210 // parse a class signature based on the implicit input. 211 assert(index == 0); 212 return ClassSignature.make(parseZeroOrMoreFormalTypeParameters(), 213 parseClassTypeSignature(), // Only rule for SuperclassSignature 214 parseSuperInterfaces()); 215 } 216 217 private FormalTypeParameter[] parseZeroOrMoreFormalTypeParameters(){ 218 if (current() == '<') { 219 return parseFormalTypeParameters(); 220 } else { 221 return new FormalTypeParameter[0]; 222 } 223 } 224 225 /** 226 * FormalTypeParameters: 227 * "<" FormalTypeParameter+ ">" 228 */ 229 private FormalTypeParameter[] parseFormalTypeParameters(){ 230 List<FormalTypeParameter> ftps = new ArrayList<>(3); 231 assert(current() == '<'); // should not have been called at all 232 if (current() != '<') { throw error("expected '<'");} 233 advance(); 234 ftps.add(parseFormalTypeParameter()); 235 while (current() != '>') { 236 int startingPosition = index; 237 ftps.add(parseFormalTypeParameter()); 238 progress(startingPosition); 239 } 240 advance(); 241 return ftps.toArray(new FormalTypeParameter[ftps.size()]); 242 } 243 244 /** 245 * FormalTypeParameter: 246 * Identifier ClassBound InterfaceBound* 247 */ 248 private FormalTypeParameter parseFormalTypeParameter(){ 249 String id = parseIdentifier(); 250 FieldTypeSignature[] bs = parseBounds(); 251 return FormalTypeParameter.make(id, bs); 252 } 253 254 private String parseIdentifier() { 255 mark(); 256 skipIdentifier(); 257 return markToCurrent(); 258 } 259 260 private void skipIdentifier() { 261 char c = current(); 262 while (c != ';' && c != '.' && c != '/' && 263 c != '[' && c != ':' && c != '>' && 264 c != '<' && !Character.isWhitespace(c)) { 265 advance(); 266 c = current(); 267 } 268 } 269 270 /** 271 * FieldTypeSignature: 272 * ClassTypeSignature 273 * ArrayTypeSignature 274 * TypeVariableSignature 275 */ 276 private FieldTypeSignature parseFieldTypeSignature() { 277 return parseFieldTypeSignature(true); 278 } 279 280 private FieldTypeSignature parseFieldTypeSignature(boolean allowArrays) { 281 switch(current()) { 282 case 'L': 283 return parseClassTypeSignature(); 284 case 'T': 285 return parseTypeVariableSignature(); 286 case '[': 287 if (allowArrays) 288 return parseArrayTypeSignature(); 289 else 290 throw error("Array signature not allowed here."); 291 default: throw error("Expected Field Type Signature"); 292 } 293 } 294 295 /** 296 * ClassTypeSignature: 297 * "L" PackageSpecifier_opt SimpleClassTypeSignature ClassTypeSignatureSuffix* ";" 298 */ 299 private ClassTypeSignature parseClassTypeSignature(){ 300 assert(current() == 'L'); 301 if (current() != 'L') { throw error("expected a class type");} 302 advance(); 303 List<SimpleClassTypeSignature> scts = new ArrayList<>(5); 304 scts.add(parsePackageNameAndSimpleClassTypeSignature()); 305 306 parseClassTypeSignatureSuffix(scts); 307 if (current() != ';') 308 throw error("expected ';' got '" + current() + "'"); 309 310 advance(); 311 return ClassTypeSignature.make(scts); 312 } 313 314 /** 315 * PackageSpecifier: 316 * Identifier "/" PackageSpecifier* 317 */ 318 private SimpleClassTypeSignature parsePackageNameAndSimpleClassTypeSignature() { 319 // Parse both any optional leading PackageSpecifier as well as 320 // the following SimpleClassTypeSignature. 321 322 mark(); 323 skipIdentifier(); 324 while (current() == '/') { 325 advance(); 326 skipIdentifier(); 327 } 328 String id = markToCurrent().replace('/', '.'); 329 330 switch (current()) { 331 case ';': 332 return SimpleClassTypeSignature.make(id, false, new TypeArgument[0]); // all done! 333 case '<': 334 if (DEBUG) System.out.println("\t remainder: " + remainder()); 335 return SimpleClassTypeSignature.make(id, false, parseTypeArguments()); 336 default: 337 throw error("expected '<' or ';' but got " + current()); 338 } 339 } 340 341 /** 342 * SimpleClassTypeSignature: 343 * Identifier TypeArguments_opt 344 */ 345 private SimpleClassTypeSignature parseSimpleClassTypeSignature(boolean dollar){ 346 String id = parseIdentifier(); 347 char c = current(); 348 349 switch (c) { 350 case ';': 351 case '.': 352 return SimpleClassTypeSignature.make(id, dollar, new TypeArgument[0]) ; 353 case '<': 354 return SimpleClassTypeSignature.make(id, dollar, parseTypeArguments()); 355 default: 356 throw error("expected '<' or ';' or '.', got '" + c + "'."); 357 } 358 } 359 360 /** 361 * ClassTypeSignatureSuffix: 362 * "." SimpleClassTypeSignature 363 */ 364 private void parseClassTypeSignatureSuffix(List<SimpleClassTypeSignature> scts) { 365 while (current() == '.') { 366 advance(); 367 scts.add(parseSimpleClassTypeSignature(true)); 368 } 369 } 370 371 /** 372 * TypeArguments: 373 * "<" TypeArgument+ ">" 374 */ 375 private TypeArgument[] parseTypeArguments() { 376 List<TypeArgument> tas = new ArrayList<>(3); 377 assert(current() == '<'); 378 if (current() != '<') { throw error("expected '<'");} 379 advance(); 380 tas.add(parseTypeArgument()); 381 while (current() != '>') { 382 //(matches(current(), '+', '-', 'L', '[', 'T', '*')) { 383 tas.add(parseTypeArgument()); 384 } 385 advance(); 386 return tas.toArray(new TypeArgument[tas.size()]); 387 } 388 389 /** 390 * TypeArgument: 391 * WildcardIndicator_opt FieldTypeSignature 392 * "*" 393 */ 394 private TypeArgument parseTypeArgument() { 395 FieldTypeSignature[] ub, lb; 396 ub = new FieldTypeSignature[1]; 397 lb = new FieldTypeSignature[1]; 398 TypeArgument[] ta = new TypeArgument[0]; 399 char c = current(); 400 switch (c) { 401 case '+': { 402 advance(); 403 ub[0] = parseFieldTypeSignature(); 404 lb[0] = BottomSignature.make(); // bottom 405 return Wildcard.make(ub, lb); 406 } 407 case '*':{ 408 advance(); 409 ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta); 410 lb[0] = BottomSignature.make(); // bottom 411 return Wildcard.make(ub, lb); 412 } 413 case '-': { 414 advance(); 415 lb[0] = parseFieldTypeSignature(); 416 ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta); 417 return Wildcard.make(ub, lb); 418 } 419 default: 420 return parseFieldTypeSignature(); 421 } 422 } 423 424 /** 425 * TypeVariableSignature: 426 * "T" Identifier ";" 427 */ 428 private TypeVariableSignature parseTypeVariableSignature() { 429 assert(current() == 'T'); 430 if (current() != 'T') { throw error("expected a type variable usage");} 431 advance(); 432 TypeVariableSignature ts = TypeVariableSignature.make(parseIdentifier()); 433 if (current() != ';') { 434 throw error("; expected in signature of type variable named" + 435 ts.getIdentifier()); 436 } 437 advance(); 438 return ts; 439 } 440 441 /** 442 * ArrayTypeSignature: 443 * "[" TypeSignature 444 */ 445 private ArrayTypeSignature parseArrayTypeSignature() { 446 if (current() != '[') {throw error("expected array type signature");} 447 advance(); 448 return ArrayTypeSignature.make(parseTypeSignature()); 449 } 450 451 /** 452 * TypeSignature: 453 * FieldTypeSignature 454 * BaseType 455 */ 456 private TypeSignature parseTypeSignature() { 457 switch (current()) { 458 case 'B': 459 case 'C': 460 case 'D': 461 case 'F': 462 case 'I': 463 case 'J': 464 case 'S': 465 case 'Z': 466 return parseBaseType(); 467 468 default: 469 return parseFieldTypeSignature(); 470 } 471 } 472 473 private BaseType parseBaseType() { 474 switch(current()) { 475 case 'B': 476 advance(); 477 return ByteSignature.make(); 478 case 'C': 479 advance(); 480 return CharSignature.make(); 481 case 'D': 482 advance(); 483 return DoubleSignature.make(); 484 case 'F': 485 advance(); 486 return FloatSignature.make(); 487 case 'I': 488 advance(); 489 return IntSignature.make(); 490 case 'J': 491 advance(); 492 return LongSignature.make(); 493 case 'S': 494 advance(); 495 return ShortSignature.make(); 496 case 'Z': 497 advance(); 498 return BooleanSignature.make(); 499 default: { 500 assert(false); 501 throw error("expected primitive type"); 502 } 503 } 504 } 505 506 /** 507 * ClassBound: 508 * ":" FieldTypeSignature_opt 509 * 510 * InterfaceBound: 511 * ":" FieldTypeSignature 512 */ 513 private FieldTypeSignature[] parseBounds() { 514 List<FieldTypeSignature> fts = new ArrayList<>(3); 515 516 if (current() == ':') { 517 advance(); 518 switch(current()) { 519 case ':': // empty class bound 520 break; 521 522 default: // parse class bound 523 fts.add(parseFieldTypeSignature()); 524 } 525 526 // zero or more interface bounds 527 while (current() == ':') { 528 advance(); 529 fts.add(parseFieldTypeSignature()); 530 } 531 } else 532 error("Bound expected"); 533 534 return fts.toArray(new FieldTypeSignature[fts.size()]); 535 } 536 537 /** 538 * SuperclassSignature: 539 * ClassTypeSignature 540 */ 541 private ClassTypeSignature[] parseSuperInterfaces() { 542 List<ClassTypeSignature> cts = new ArrayList<>(5); 543 while(current() == 'L') { 544 cts.add(parseClassTypeSignature()); 545 } 546 return cts.toArray(new ClassTypeSignature[cts.size()]); 547 } 548 549 550 /** 551 * MethodTypeSignature: 552 * FormalTypeParameters_opt "(" TypeSignature* ")" ReturnType ThrowsSignature* 553 */ 554 private MethodTypeSignature parseMethodTypeSignature() { 555 // Parse a method signature based on the implicit input. 556 FieldTypeSignature[] ets; 557 558 assert(index == 0); 559 return MethodTypeSignature.make(parseZeroOrMoreFormalTypeParameters(), 560 parseFormalParameters(), 561 parseReturnType(), 562 parseZeroOrMoreThrowsSignatures()); 563 } 564 565 // "(" TypeSignature* ")" 566 private TypeSignature[] parseFormalParameters() { 567 if (current() != '(') {throw error("expected '('");} 568 advance(); 569 TypeSignature[] pts = parseZeroOrMoreTypeSignatures(); 570 if (current() != ')') {throw error("expected ')'");} 571 advance(); 572 return pts; 573 } 574 575 // TypeSignature* 576 private TypeSignature[] parseZeroOrMoreTypeSignatures() { 577 List<TypeSignature> ts = new ArrayList<>(); 578 boolean stop = false; 579 while (!stop) { 580 switch(current()) { 581 case 'B': 582 case 'C': 583 case 'D': 584 case 'F': 585 case 'I': 586 case 'J': 587 case 'S': 588 case 'Z': 589 case 'L': 590 case 'T': 591 case '[': { 592 ts.add(parseTypeSignature()); 593 break; 594 } 595 default: stop = true; 596 } 597 } 598 return ts.toArray(new TypeSignature[ts.size()]); 599 } 600 601 /** 602 * ReturnType: 603 * TypeSignature 604 * VoidDescriptor 605 */ 606 private ReturnType parseReturnType(){ 607 if (current() == 'V') { 608 advance(); 609 return VoidDescriptor.make(); 610 } else 611 return parseTypeSignature(); 612 } 613 614 // ThrowSignature* 615 private FieldTypeSignature[] parseZeroOrMoreThrowsSignatures(){ 616 List<FieldTypeSignature> ets = new ArrayList<>(3); 617 while( current() == '^') { 618 ets.add(parseThrowsSignature()); 619 } 620 return ets.toArray(new FieldTypeSignature[ets.size()]); 621 } 622 623 /** 624 * ThrowsSignature: 625 * "^" ClassTypeSignature 626 * "^" TypeVariableSignature 627 */ 628 private FieldTypeSignature parseThrowsSignature() { 629 assert(current() == '^'); 630 if (current() != '^') { throw error("expected throws signature");} 631 advance(); 632 return parseFieldTypeSignature(false); 633 } 634 } 635