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 {@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 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 }