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