1 /*
   2  * Copyright (c) 2003, 2011, 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 
  26 package sun.reflect.generics.parser;
  27 
  28 import java.lang.reflect.GenericSignatureFormatError;
  29 import java.util.*;
  30 import 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  */
  38 public 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 char[] input; // the input signature
  68     private int index = 0; // index into the input
  69     // used to mark end of input
  70     private static final char EOI = ':';
  71     private static final boolean DEBUG = false;
  72 
  73     // private constructor - enforces use of static factory
  74     private SignatureParser(){}
  75 
  76     // Utility methods.
  77 
  78     // Most parsing routines use the following routines to access the
  79     // input stream, and advance it as necessary.
  80     // This makes it easy to adapt the parser to operate on streams
  81     // of various kinds as well as strings.
  82 
  83     // returns current element of the input and advances the input
  84     private char getNext(){
  85         assert(index <= input.length);
  86         try {
  87             return input[index++];
  88         } catch (ArrayIndexOutOfBoundsException e) { return EOI;}
  89     }
  90 
  91     // returns current element of the input
  92     private char current(){
  93         assert(index <= input.length);
  94         try {
  95             return input[index];
  96         } catch (ArrayIndexOutOfBoundsException e) { return EOI;}
  97     }
  98 
  99     // advance the input
 100     private void advance(){
 101         assert(index <= input.length);
 102         index++;
 103     }
 104 
 105     // For debugging, prints current character to the end of the input.
 106     private String remainder() {
 107         return new String(input, index, input.length-index);
 108     }
 109 
 110     // Match c against a "set" of characters
 111     private boolean matches(char c, char... set) {
 112         for (char e : set) {
 113             if (c == e) return true;
 114         }
 115         return false;
 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 <tt>SignatureParser</tt>
 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         input = s.toCharArray();
 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         input = s.toCharArray();
 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         input = s.toCharArray();
 188         return parseTypeSignature();
 189     }
 190 
 191     // Parsing routines.
 192     // As a rule, the parsing routines access the input using the
 193     // utilities current(), getNext() and/or 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         StringBuilder result = new StringBuilder();
 256         while (!Character.isWhitespace(current())) {
 257             char c = current();
 258             switch(c) {
 259             case ';':
 260             case '.':
 261             case '/':
 262             case '[':
 263             case ':':
 264             case '>':
 265             case '<':
 266                 return result.toString();
 267             default:{
 268                 result.append(c);
 269                 advance();
 270             }
 271 
 272             }
 273         }
 274         return result.toString();
 275     }
 276     /**
 277      * FieldTypeSignature:
 278      *     ClassTypeSignature
 279      *     ArrayTypeSignature
 280      *     TypeVariableSignature
 281      */
 282     private FieldTypeSignature parseFieldTypeSignature() {
 283         return parseFieldTypeSignature(true);
 284     }
 285 
 286     private FieldTypeSignature parseFieldTypeSignature(boolean allowArrays) {
 287         switch(current()) {
 288         case 'L':
 289            return parseClassTypeSignature();
 290         case 'T':
 291             return parseTypeVariableSignature();
 292         case '[':
 293             if (allowArrays)
 294                 return parseArrayTypeSignature();
 295             else
 296                 throw error("Array signature not allowed here.");
 297         default: throw error("Expected Field Type Signature");
 298         }
 299     }
 300 
 301     /**
 302      * ClassTypeSignature:
 303      *     "L" PackageSpecifier_opt SimpleClassTypeSignature ClassTypeSignatureSuffix* ";"
 304      */
 305     private ClassTypeSignature parseClassTypeSignature(){
 306         assert(current() == 'L');
 307         if (current() != 'L') { throw error("expected a class type");}
 308         advance();
 309         List<SimpleClassTypeSignature> scts = new ArrayList<>(5);
 310         scts.add(parsePackageNameAndSimpleClassTypeSignature());
 311 
 312         parseClassTypeSignatureSuffix(scts);
 313         if (current() != ';')
 314             throw error("expected ';' got '" + current() + "'");
 315 
 316         advance();
 317         return ClassTypeSignature.make(scts);
 318     }
 319 
 320     /**
 321      * PackageSpecifier:
 322      *     Identifier "/" PackageSpecifier*
 323      */
 324     private SimpleClassTypeSignature parsePackageNameAndSimpleClassTypeSignature() {
 325         // Parse both any optional leading PackageSpecifier as well as
 326         // the following SimpleClassTypeSignature.
 327 
 328         String id = parseIdentifier();
 329 
 330         if (current() == '/') { // package name
 331             StringBuilder idBuild = new StringBuilder(id);
 332 
 333             while(current() == '/') {
 334                 advance();
 335                 idBuild.append(".");
 336                 idBuild.append(parseIdentifier());
 337             }
 338             id = idBuild.toString();
 339         }
 340 
 341         switch (current()) {
 342         case ';':
 343             return SimpleClassTypeSignature.make(id, false, new TypeArgument[0]); // all done!
 344         case '<':
 345             if (DEBUG) System.out.println("\t remainder: " + remainder());
 346             return SimpleClassTypeSignature.make(id, false, parseTypeArguments());
 347         default:
 348             throw error("expected '<' or ';' but got " + current());
 349         }
 350     }
 351 
 352     /**
 353      * SimpleClassTypeSignature:
 354      *     Identifier TypeArguments_opt
 355      */
 356     private SimpleClassTypeSignature parseSimpleClassTypeSignature(boolean dollar){
 357         String id = parseIdentifier();
 358         char c = current();
 359 
 360         switch (c) {
 361         case ';':
 362         case '.':
 363             return SimpleClassTypeSignature.make(id, dollar, new TypeArgument[0]) ;
 364         case '<':
 365             return SimpleClassTypeSignature.make(id, dollar, parseTypeArguments());
 366         default:
 367             throw error("expected '<' or ';' or '.', got '" + c + "'.");
 368         }
 369     }
 370 
 371     /**
 372      * ClassTypeSignatureSuffix:
 373      *     "." SimpleClassTypeSignature
 374      */
 375     private void parseClassTypeSignatureSuffix(List<SimpleClassTypeSignature> scts) {
 376         while (current() == '.') {
 377             advance();
 378             scts.add(parseSimpleClassTypeSignature(true));
 379         }
 380     }
 381 
 382     private TypeArgument[] parseTypeArgumentsOpt() {
 383         if (current() == '<') {return parseTypeArguments();}
 384         else {return new TypeArgument[0];}
 385     }
 386 
 387     /**
 388      * TypeArguments:
 389      *     "<" TypeArgument+ ">"
 390      */
 391     private TypeArgument[] parseTypeArguments() {
 392         List<TypeArgument> tas = new ArrayList<>(3);
 393         assert(current() == '<');
 394         if (current() != '<') { throw error("expected '<'");}
 395         advance();
 396         tas.add(parseTypeArgument());
 397         while (current() != '>') {
 398                 //(matches(current(),  '+', '-', 'L', '[', 'T', '*')) {
 399             tas.add(parseTypeArgument());
 400         }
 401         advance();
 402         return tas.toArray(new TypeArgument[tas.size()]);
 403     }
 404 
 405     /**
 406      * TypeArgument:
 407      *     WildcardIndicator_opt FieldTypeSignature
 408      *     "*"
 409      */
 410     private TypeArgument parseTypeArgument() {
 411         FieldTypeSignature[] ub, lb;
 412         ub = new FieldTypeSignature[1];
 413         lb = new FieldTypeSignature[1];
 414         TypeArgument[] ta = new TypeArgument[0];
 415         char c = current();
 416         switch (c) {
 417         case '+': {
 418             advance();
 419             ub[0] = parseFieldTypeSignature();
 420             lb[0] = BottomSignature.make(); // bottom
 421             return Wildcard.make(ub, lb);
 422         }
 423         case '*':{
 424             advance();
 425             ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta);
 426             lb[0] = BottomSignature.make(); // bottom
 427             return Wildcard.make(ub, lb);
 428         }
 429         case '-': {
 430             advance();
 431             lb[0] = parseFieldTypeSignature();
 432             ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta);
 433             return Wildcard.make(ub, lb);
 434         }
 435         default:
 436             return parseFieldTypeSignature();
 437         }
 438     }
 439 
 440     /**
 441      * TypeVariableSignature:
 442      *     "T" Identifier ";"
 443      */
 444     private TypeVariableSignature parseTypeVariableSignature() {
 445         assert(current() == 'T');
 446         if (current() != 'T') { throw error("expected a type variable usage");}
 447         advance();
 448         TypeVariableSignature ts = TypeVariableSignature.make(parseIdentifier());
 449         if (current() != ';') {
 450             throw error("; expected in signature of type variable named" +
 451                   ts.getIdentifier());
 452         }
 453         advance();
 454         return ts;
 455     }
 456 
 457     /**
 458      * ArrayTypeSignature:
 459      *     "[" TypeSignature
 460      */
 461     private ArrayTypeSignature parseArrayTypeSignature() {
 462         if (current() != '[') {throw error("expected array type signature");}
 463         advance();
 464         return ArrayTypeSignature.make(parseTypeSignature());
 465     }
 466 
 467     /**
 468      * TypeSignature:
 469      *     FieldTypeSignature
 470      *     BaseType
 471      */
 472     private TypeSignature parseTypeSignature() {
 473         switch (current()) {
 474         case 'B':
 475         case 'C':
 476         case 'D':
 477         case 'F':
 478         case 'I':
 479         case 'J':
 480         case 'S':
 481         case 'Z':
 482             return parseBaseType();
 483 
 484         default:
 485             return parseFieldTypeSignature();
 486         }
 487     }
 488 
 489     private BaseType parseBaseType() {
 490         switch(current()) {
 491         case 'B':
 492             advance();
 493             return ByteSignature.make();
 494         case 'C':
 495             advance();
 496             return CharSignature.make();
 497         case 'D':
 498             advance();
 499             return DoubleSignature.make();
 500         case 'F':
 501             advance();
 502             return FloatSignature.make();
 503         case 'I':
 504             advance();
 505             return IntSignature.make();
 506         case 'J':
 507             advance();
 508             return LongSignature.make();
 509         case 'S':
 510             advance();
 511             return ShortSignature.make();
 512         case 'Z':
 513             advance();
 514             return BooleanSignature.make();
 515         default: {
 516             assert(false);
 517             throw error("expected primitive type");
 518         }
 519         }
 520     }
 521 
 522     /**
 523      * ClassBound:
 524      *     ":" FieldTypeSignature_opt
 525      *
 526      * InterfaceBound:
 527      *     ":" FieldTypeSignature
 528      */
 529     private FieldTypeSignature[] parseBounds() {
 530         List<FieldTypeSignature> fts = new ArrayList<>(3);
 531 
 532         if (current() == ':') {
 533             advance();
 534             switch(current()) {
 535             case ':': // empty class bound
 536                 break;
 537 
 538             default: // parse class bound
 539                 fts.add(parseFieldTypeSignature());
 540             }
 541 
 542             // zero or more interface bounds
 543             while (current() == ':') {
 544                 advance();
 545                 fts.add(parseFieldTypeSignature());
 546             }
 547         } else
 548             error("Bound expected");
 549 
 550         return fts.toArray(new FieldTypeSignature[fts.size()]);
 551     }
 552 
 553     /**
 554      * SuperclassSignature:
 555      *     ClassTypeSignature
 556      */
 557     private ClassTypeSignature[] parseSuperInterfaces() {
 558         List<ClassTypeSignature> cts = new ArrayList<>(5);
 559         while(current() == 'L') {
 560             cts.add(parseClassTypeSignature());
 561         }
 562         return cts.toArray(new ClassTypeSignature[cts.size()]);
 563     }
 564 
 565 
 566     /**
 567      * MethodTypeSignature:
 568      *     FormalTypeParameters_opt "(" TypeSignature* ")" ReturnType ThrowsSignature*
 569      */
 570     private MethodTypeSignature parseMethodTypeSignature() {
 571         // Parse a method signature based on the implicit input.
 572         FieldTypeSignature[] ets;
 573 
 574         assert(index == 0);
 575         return MethodTypeSignature.make(parseZeroOrMoreFormalTypeParameters(),
 576                                         parseFormalParameters(),
 577                                         parseReturnType(),
 578                                         parseZeroOrMoreThrowsSignatures());
 579     }
 580 
 581     // "(" TypeSignature* ")"
 582     private TypeSignature[] parseFormalParameters() {
 583         if (current() != '(') {throw error("expected '('");}
 584         advance();
 585         TypeSignature[] pts = parseZeroOrMoreTypeSignatures();
 586         if (current() != ')') {throw error("expected ')'");}
 587         advance();
 588         return pts;
 589     }
 590 
 591     // TypeSignature*
 592     private TypeSignature[] parseZeroOrMoreTypeSignatures() {
 593         List<TypeSignature> ts = new ArrayList<>();
 594         boolean stop = false;
 595         while (!stop) {
 596             switch(current()) {
 597             case 'B':
 598             case 'C':
 599             case 'D':
 600             case 'F':
 601             case 'I':
 602             case 'J':
 603             case 'S':
 604             case 'Z':
 605             case 'L':
 606             case 'T':
 607             case '[': {
 608                 ts.add(parseTypeSignature());
 609                 break;
 610             }
 611             default: stop = true;
 612             }
 613         }
 614         return ts.toArray(new TypeSignature[ts.size()]);
 615     }
 616 
 617     /**
 618      * ReturnType:
 619      *     TypeSignature
 620      *     VoidDescriptor
 621      */
 622     private ReturnType parseReturnType(){
 623         if (current() == 'V') {
 624             advance();
 625             return VoidDescriptor.make();
 626         } else
 627             return parseTypeSignature();
 628     }
 629 
 630     // ThrowSignature*
 631     private FieldTypeSignature[] parseZeroOrMoreThrowsSignatures(){
 632         List<FieldTypeSignature> ets = new ArrayList<>(3);
 633         while( current() == '^') {
 634             ets.add(parseThrowsSignature());
 635         }
 636         return ets.toArray(new FieldTypeSignature[ets.size()]);
 637     }
 638 
 639     /**
 640      * ThrowsSignature:
 641      *     "^" ClassTypeSignature
 642      *     "^" TypeVariableSignature
 643      */
 644     private FieldTypeSignature parseThrowsSignature() {
 645         assert(current() == '^');
 646         if (current() != '^') { throw error("expected throws signature");}
 647         advance();
 648         return parseFieldTypeSignature(false);
 649     }
 650  }