/*
 * Copyright (c) 2003, 2016, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package sun.reflect.generics.parser;

import java.lang.reflect.GenericSignatureFormatError;
import java.util.*;
import sun.reflect.generics.tree.*;

Parser for type signatures, as defined in the Java Virtual
Machine Specification (JVMS) chapter 4.
Converts the signatures into an abstract syntax tree (AST) representation.
See the package sun.reflect.generics.tree for details of the AST.
/**
 * Parser for type signatures, as defined in the Java Virtual
 * Machine Specification (JVMS) chapter 4.
 * Converts the signatures into an abstract syntax tree (AST) representation.
 * See the package sun.reflect.generics.tree for details of the AST.
 */
public class SignatureParser {
    // The input is conceptually a character stream (though currently it's
    // a string). This is slightly different than traditional parsers,
    // because there is no lexical scanner performing tokenization.
    // Having a separate tokenizer does not fit with the nature of the
    // input format.
    // Other than the absence of a tokenizer, this parser is a classic
    // recursive descent parser. Its structure corresponds as closely
    // as possible to the grammar in the JVMS.
    //
    // A note on asserts vs. errors: The code contains assertions
    // in situations that should never occur. An assertion failure
    // indicates a failure of the parser logic. A common pattern
    // is an assertion that the current input is a particular
    // character. This is often paired with a separate check
    // that this is the case, which seems redundant. For example:
    //
    // assert(current() != x);
    // if (current != x {error("expected an x");
    //
    // where x is some character constant.
    // The assertion indicates, that, as currently written,
    // the code should never reach this point unless the input is an
    // x. On the other hand, the test is there to check the legality
    // of the input wrt to a given production. It may be that at a later
    // time the code might be called directly, and if the input is
    // invalid, the parser should flag an error in accordance
    // with its logic.

    private String input; // the input signature
    private int index;    // index into the input
    private int mark;     // index of mark
    // used to mark end of input
    private static final char EOI = ':';
    private static final boolean DEBUG = false;

    // private constructor - enforces use of static factory
    private SignatureParser(){}

    // prepares parser for new parsing session
    private void init(String s) {
        input = s;
        mark = index = 0;
    }

    // Utility methods.

    // Most parsing routines use the following routines to access the
    // input stream, and advance it as necessary.
    // This makes it easy to adapt the parser to operate on streams
    // of various kinds as well as strings.

    // returns current element of the input
    private char current(){
        assert(index <= input.length());
        return index < input.length() ? input.charAt(index) : EOI;
    }

    // advance the input
    private void advance(){
        assert(index <= input.length());
        if (index < input.length()) index++;
    }

    // mark current position
    private void mark() {
        mark = index;
    }

    // For debugging, prints current character to the end of the input.
    private String remainder() {
        return input.substring(index);
    }

    // returns a substring of input from mark (inclusive)
    // to current position (exclusive)
    private String markToCurrent() {
        return input.substring(mark, index);
    }

    // Error handling routine. Encapsulates error handling.
    // Takes a string error message as argument.
    // Currently throws a GenericSignatureFormatError.

    private Error error(String errorMsg) {
        return new GenericSignatureFormatError("Signature Parse error: " + errorMsg +
                                               "\n\tRemaining input: " + remainder());
    }

    
Verify the parse has made forward progress; throw an exception
if no progress.
/**
     * Verify the parse has made forward progress; throw an exception
     * if no progress.
     */
    private void progress(int startingPosition) {
        if (index <= startingPosition)
            throw error("Failure to make progress!");
    }

    
Static factory method. Produces a parser instance.
Returns:
an instance of SignatureParser/**
     * Static factory method. Produces a parser instance.
     * @return an instance of {@code SignatureParser}
     */
    public static SignatureParser make() {
        return new SignatureParser();
    }

    
Parses a class signature (as defined in the JVMS, chapter 4)
and produces an abstract syntax tree representing it.
Params:
s – a string representing the input class signature
Throws:
GenericSignatureFormatError – if the input is not a valid
class signature
Returns:
An abstract syntax tree for a class signature
corresponding to the input string/**
     * Parses a class signature (as defined in the JVMS, chapter 4)
     * and produces an abstract syntax tree representing it.
     * @param s a string representing the input class signature
     * @return An abstract syntax tree for a class signature
     * corresponding to the input string
     * @throws GenericSignatureFormatError if the input is not a valid
     * class signature
     */
    public ClassSignature parseClassSig(String s) {
        if (DEBUG) System.out.println("Parsing class sig:" + s);
        init(s);
        return parseClassSignature();
    }

    
Parses a method signature (as defined in the JVMS, chapter 4)
and produces an abstract syntax tree representing it.
Params:
s – a string representing the input method signature
Throws:
GenericSignatureFormatError – if the input is not a valid
method signature
Returns:
An abstract syntax tree for a method signature
corresponding to the input string/**
     * Parses a method signature (as defined in the JVMS, chapter 4)
     * and produces an abstract syntax tree representing it.
     * @param s a string representing the input method signature
     * @return An abstract syntax tree for a method signature
     * corresponding to the input string
     * @throws GenericSignatureFormatError if the input is not a valid
     * method signature
     */
    public MethodTypeSignature parseMethodSig(String s) {
        if (DEBUG) System.out.println("Parsing method sig:" + s);
        init(s);
        return parseMethodTypeSignature();
    }


    
Parses a type signature
and produces an abstract syntax tree representing it.
Params:
s – a string representing the input type signature
Throws:
GenericSignatureFormatError – if the input is not a valid
type signature
Returns:
An abstract syntax tree for a type signature
corresponding to the input string/**
     * Parses a type signature
     * and produces an abstract syntax tree representing it.
     *
     * @param s a string representing the input type signature
     * @return An abstract syntax tree for a type signature
     * corresponding to the input string
     * @throws GenericSignatureFormatError if the input is not a valid
     * type signature
     */
    public TypeSignature parseTypeSig(String s) {
        if (DEBUG) System.out.println("Parsing type sig:" + s);
        init(s);
        return parseTypeSignature();
    }

    // Parsing routines.
    // As a rule, the parsing routines access the input using the
    // utilities current() and advance().
    // The convention is that when a parsing routine is invoked
    // it expects the current input to be the first character it should parse
    // and when it completes parsing, it leaves the input at the first
    // character after the input parses.

    /*
     * Note on grammar conventions: a trailing "*" matches zero or
     * more occurrences, a trailing "+" matches one or more occurrences,
     * "_opt" indicates an optional component.
     */

    
ClassSignature:
    FormalTypeParameters_opt SuperclassSignature SuperinterfaceSignature*
/**
     * ClassSignature:
     *     FormalTypeParameters_opt SuperclassSignature SuperinterfaceSignature*
     */
    private ClassSignature parseClassSignature() {
        // parse a class signature based on the implicit input.
        assert(index == 0);
        return ClassSignature.make(parseZeroOrMoreFormalTypeParameters(),
                                   parseClassTypeSignature(), // Only rule for SuperclassSignature
                                   parseSuperInterfaces());
    }

    private FormalTypeParameter[] parseZeroOrMoreFormalTypeParameters(){
        if (current() == '<') {
            return parseFormalTypeParameters();
        } else {
            return new FormalTypeParameter[0];
        }
    }

    
FormalTypeParameters:
    "<" FormalTypeParameter+ ">"
/**
     * FormalTypeParameters:
     *     "<" FormalTypeParameter+ ">"
     */
    private FormalTypeParameter[] parseFormalTypeParameters(){
        List<FormalTypeParameter> ftps = new ArrayList<>(3);
        assert(current() == '<'); // should not have been called at all
        if (current() != '<') { throw error("expected '<'");}
        advance();
        ftps.add(parseFormalTypeParameter());
        while (current() != '>') {
            int startingPosition = index;
            ftps.add(parseFormalTypeParameter());
            progress(startingPosition);
        }
        advance();
        return ftps.toArray(new FormalTypeParameter[ftps.size()]);
    }

    
FormalTypeParameter:
    Identifier ClassBound InterfaceBound*
/**
     * FormalTypeParameter:
     *     Identifier ClassBound InterfaceBound*
     */
    private FormalTypeParameter parseFormalTypeParameter(){
        String id = parseIdentifier();
        FieldTypeSignature[] bs = parseBounds();
        return FormalTypeParameter.make(id, bs);
    }

    private String parseIdentifier() {
        mark();
        skipIdentifier();
        return markToCurrent();
    }

    private void skipIdentifier() {
        char c = current();
        while (c != ';' && c != '.' && c != '/' &&
               c != '[' && c != ':' && c != '>' &&
               c != '<' && !Character.isWhitespace(c)) {
            advance();
            c = current();
        }
    }

    
FieldTypeSignature:
    ClassTypeSignature
    ArrayTypeSignature
    TypeVariableSignature
/**
     * FieldTypeSignature:
     *     ClassTypeSignature
     *     ArrayTypeSignature
     *     TypeVariableSignature
     */
    private FieldTypeSignature parseFieldTypeSignature() {
        return parseFieldTypeSignature(true);
    }

    private FieldTypeSignature parseFieldTypeSignature(boolean allowArrays) {
        switch(current()) {
        case 'L':
           return parseClassTypeSignature();
        case 'T':
            return parseTypeVariableSignature();
        case '[':
            if (allowArrays)
                return parseArrayTypeSignature();
            else
                throw error("Array signature not allowed here.");
        default: throw error("Expected Field Type Signature");
        }
    }

    
ClassTypeSignature:
    "L" PackageSpecifier_opt SimpleClassTypeSignature ClassTypeSignatureSuffix* ";"
/**
     * ClassTypeSignature:
     *     "L" PackageSpecifier_opt SimpleClassTypeSignature ClassTypeSignatureSuffix* ";"
     */
    private ClassTypeSignature parseClassTypeSignature(){
        assert(current() == 'L');
        if (current() != 'L') { throw error("expected a class type");}
        advance();
        List<SimpleClassTypeSignature> scts = new ArrayList<>(5);
        scts.add(parsePackageNameAndSimpleClassTypeSignature());

        parseClassTypeSignatureSuffix(scts);
        if (current() != ';')
            throw error("expected ';' got '" + current() + "'");

        advance();
        return ClassTypeSignature.make(scts);
    }

    
PackageSpecifier:
    Identifier "/" PackageSpecifier*
/**
     * PackageSpecifier:
     *     Identifier "/" PackageSpecifier*
     */
    private SimpleClassTypeSignature parsePackageNameAndSimpleClassTypeSignature() {
        // Parse both any optional leading PackageSpecifier as well as
        // the following SimpleClassTypeSignature.

        mark();
        skipIdentifier();
        while (current() == '/') {
            advance();
            skipIdentifier();
        }
        String id = markToCurrent().replace('/', '.');

        switch (current()) {
        case ';':
            return SimpleClassTypeSignature.make(id, false, new TypeArgument[0]); // all done!
        case '<':
            if (DEBUG) System.out.println("\t remainder: " + remainder());
            return SimpleClassTypeSignature.make(id, false, parseTypeArguments());
        default:
            throw error("expected '<' or ';' but got " + current());
        }
    }

    
SimpleClassTypeSignature:
    Identifier TypeArguments_opt
/**
     * SimpleClassTypeSignature:
     *     Identifier TypeArguments_opt
     */
    private SimpleClassTypeSignature parseSimpleClassTypeSignature(boolean dollar){
        String id = parseIdentifier();
        char c = current();

        switch (c) {
        case ';':
        case '.':
            return SimpleClassTypeSignature.make(id, dollar, new TypeArgument[0]) ;
        case '<':
            return SimpleClassTypeSignature.make(id, dollar, parseTypeArguments());
        default:
            throw error("expected '<' or ';' or '.', got '" + c + "'.");
        }
    }

    
ClassTypeSignatureSuffix:
    "." SimpleClassTypeSignature
/**
     * ClassTypeSignatureSuffix:
     *     "." SimpleClassTypeSignature
     */
    private void parseClassTypeSignatureSuffix(List<SimpleClassTypeSignature> scts) {
        while (current() == '.') {
            advance();
            scts.add(parseSimpleClassTypeSignature(true));
        }
    }

    
TypeArguments:
    "<" TypeArgument+ ">"
/**
     * TypeArguments:
     *     "<" TypeArgument+ ">"
     */
    private TypeArgument[] parseTypeArguments() {
        List<TypeArgument> tas = new ArrayList<>(3);
        assert(current() == '<');
        if (current() != '<') { throw error("expected '<'");}
        advance();
        tas.add(parseTypeArgument());
        while (current() != '>') {
                //(matches(current(),  '+', '-', 'L', '[', 'T', '*')) {
            tas.add(parseTypeArgument());
        }
        advance();
        return tas.toArray(new TypeArgument[tas.size()]);
    }

    
TypeArgument:
    WildcardIndicator_opt FieldTypeSignature
    "*"
/**
     * TypeArgument:
     *     WildcardIndicator_opt FieldTypeSignature
     *     "*"
     */
    private TypeArgument parseTypeArgument() {
        FieldTypeSignature[] ub, lb;
        ub = new FieldTypeSignature[1];
        lb = new FieldTypeSignature[1];
        TypeArgument[] ta = new TypeArgument[0];
        char c = current();
        switch (c) {
        case '+': {
            advance();
            ub[0] = parseFieldTypeSignature();
            lb[0] = BottomSignature.make(); // bottom
            return Wildcard.make(ub, lb);
        }
        case '*':{
            advance();
            ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta);
            lb[0] = BottomSignature.make(); // bottom
            return Wildcard.make(ub, lb);
        }
        case '-': {
            advance();
            lb[0] = parseFieldTypeSignature();
            ub[0] = SimpleClassTypeSignature.make("java.lang.Object", false, ta);
            return Wildcard.make(ub, lb);
        }
        default:
            return parseFieldTypeSignature();
        }
    }

    
TypeVariableSignature:
    "T" Identifier ";"
/**
     * TypeVariableSignature:
     *     "T" Identifier ";"
     */
    private TypeVariableSignature parseTypeVariableSignature() {
        assert(current() == 'T');
        if (current() != 'T') { throw error("expected a type variable usage");}
        advance();
        TypeVariableSignature ts = TypeVariableSignature.make(parseIdentifier());
        if (current() != ';') {
            throw error("; expected in signature of type variable named" +
                  ts.getIdentifier());
        }
        advance();
        return ts;
    }

    
ArrayTypeSignature:
    "[" TypeSignature
/**
     * ArrayTypeSignature:
     *     "[" TypeSignature
     */
    private ArrayTypeSignature parseArrayTypeSignature() {
        if (current() != '[') {throw error("expected array type signature");}
        advance();
        return ArrayTypeSignature.make(parseTypeSignature());
    }

    
TypeSignature:
    FieldTypeSignature
    BaseType
/**
     * TypeSignature:
     *     FieldTypeSignature
     *     BaseType
     */
    private TypeSignature parseTypeSignature() {
        switch (current()) {
        case 'B':
        case 'C':
        case 'D':
        case 'F':
        case 'I':
        case 'J':
        case 'S':
        case 'Z':
            return parseBaseType();

        default:
            return parseFieldTypeSignature();
        }
    }

    private BaseType parseBaseType() {
        switch(current()) {
        case 'B':
            advance();
            return ByteSignature.make();
        case 'C':
            advance();
            return CharSignature.make();
        case 'D':
            advance();
            return DoubleSignature.make();
        case 'F':
            advance();
            return FloatSignature.make();
        case 'I':
            advance();
            return IntSignature.make();
        case 'J':
            advance();
            return LongSignature.make();
        case 'S':
            advance();
            return ShortSignature.make();
        case 'Z':
            advance();
            return BooleanSignature.make();
        default: {
            assert(false);
            throw error("expected primitive type");
        }
        }
    }

    
ClassBound:
    ":" FieldTypeSignature_opt
InterfaceBound:
    ":" FieldTypeSignature
/**
     * ClassBound:
     *     ":" FieldTypeSignature_opt
     *
     * InterfaceBound:
     *     ":" FieldTypeSignature
     */
    private FieldTypeSignature[] parseBounds() {
        List<FieldTypeSignature> fts = new ArrayList<>(3);

        if (current() == ':') {
            advance();
            switch(current()) {
            case ':': // empty class bound
                break;

            default: // parse class bound
                fts.add(parseFieldTypeSignature());
            }

            // zero or more interface bounds
            while (current() == ':') {
                advance();
                fts.add(parseFieldTypeSignature());
            }
        } else
            error("Bound expected");

        return fts.toArray(new FieldTypeSignature[fts.size()]);
    }

    
SuperclassSignature:
    ClassTypeSignature
/**
     * SuperclassSignature:
     *     ClassTypeSignature
     */
    private ClassTypeSignature[] parseSuperInterfaces() {
        List<ClassTypeSignature> cts = new ArrayList<>(5);
        while(current() == 'L') {
            cts.add(parseClassTypeSignature());
        }
        return cts.toArray(new ClassTypeSignature[cts.size()]);
    }


    
MethodTypeSignature:
    FormalTypeParameters_opt "(" TypeSignature* ")" ReturnType ThrowsSignature*
/**
     * MethodTypeSignature:
     *     FormalTypeParameters_opt "(" TypeSignature* ")" ReturnType ThrowsSignature*
     */
    private MethodTypeSignature parseMethodTypeSignature() {
        // Parse a method signature based on the implicit input.
        FieldTypeSignature[] ets;

        assert(index == 0);
        return MethodTypeSignature.make(parseZeroOrMoreFormalTypeParameters(),
                                        parseFormalParameters(),
                                        parseReturnType(),
                                        parseZeroOrMoreThrowsSignatures());
    }

    // "(" TypeSignature* ")"
    private TypeSignature[] parseFormalParameters() {
        if (current() != '(') {throw error("expected '('");}
        advance();
        TypeSignature[] pts = parseZeroOrMoreTypeSignatures();
        if (current() != ')') {throw error("expected ')'");}
        advance();
        return pts;
    }

    // TypeSignature*
    private TypeSignature[] parseZeroOrMoreTypeSignatures() {
        List<TypeSignature> ts = new ArrayList<>();
        boolean stop = false;
        while (!stop) {
            switch(current()) {
            case 'B':
            case 'C':
            case 'D':
            case 'F':
            case 'I':
            case 'J':
            case 'S':
            case 'Z':
            case 'L':
            case 'T':
            case '[': {
                ts.add(parseTypeSignature());
                break;
            }
            default: stop = true;
            }
        }
        return ts.toArray(new TypeSignature[ts.size()]);
    }

    
ReturnType:
    TypeSignature
    VoidDescriptor
/**
     * ReturnType:
     *     TypeSignature
     *     VoidDescriptor
     */
    private ReturnType parseReturnType(){
        if (current() == 'V') {
            advance();
            return VoidDescriptor.make();
        } else
            return parseTypeSignature();
    }

    // ThrowSignature*
    private FieldTypeSignature[] parseZeroOrMoreThrowsSignatures(){
        List<FieldTypeSignature> ets = new ArrayList<>(3);
        while( current() == '^') {
            ets.add(parseThrowsSignature());
        }
        return ets.toArray(new FieldTypeSignature[ets.size()]);
    }

    
ThrowsSignature:
    "^" ClassTypeSignature
    "^" TypeVariableSignature
/**
     * ThrowsSignature:
     *     "^" ClassTypeSignature
     *     "^" TypeVariableSignature
     */
    private FieldTypeSignature parseThrowsSignature() {
        assert(current() == '^');
        if (current() != '^') { throw error("expected throws signature");}
        advance();
        return parseFieldTypeSignature(false);
    }
 }