/*

 * Copyright (c) 2003, 2013, 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 com.sun.tools.javac.code;

import java.lang.ref.SoftReference;

import java.util.Comparator;

import java.util.HashSet;

import java.util.HashMap;

import java.util.Locale;

import java.util.Map;

import java.util.Set;

import java.util.WeakHashMap;

import javax.lang.model.type.TypeKind;

import com.sun.tools.javac.code.Attribute.RetentionPolicy;

import com.sun.tools.javac.code.Lint.LintCategory;

import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;

import com.sun.tools.javac.comp.Check;

import com.sun.tools.javac.jvm.ClassReader;

import com.sun.tools.javac.util.*;

import static com.sun.tools.javac.code.BoundKind.*;

import static com.sun.tools.javac.code.Flags.*;

import static com.sun.tools.javac.code.Scope.*;

import static com.sun.tools.javac.code.Symbol.*;

import static com.sun.tools.javac.code.Type.*;

import static com.sun.tools.javac.code.TypeTag.*;

import static com.sun.tools.javac.jvm.ClassFile.externalize;

import static com.sun.tools.javac.util.ListBuffer.lb;

/**

 * Utility class containing various operations on types.

 *

 * <p>Unless other names are more illustrative, the following naming

 * conventions should be observed in this file:

 *

 * <dl>

 * <dt>t</dt>

 * <dd>If the first argument to an operation is a type, it should be named t.</dd>

 * <dt>s</dt>

 * <dd>Similarly, if the second argument to an operation is a type, it should be named s.</dd>

 * <dt>ts</dt>

 * <dd>If an operations takes a list of types, the first should be named ts.</dd>

 * <dt>ss</dt>

 * <dd>A second list of types should be named ss.</dd>

 * </dl>

 *

 * <p><b>This is NOT part of any supported API.

 * If you write code that depends on this, you do so at your own risk.

 * This code and its internal interfaces are subject to change or

 * deletion without notice.</b>

 */

public class Types {

    protected static final Context.Key<Types> typesKey =

        new Context.Key<Types>();

    final Symtab syms;

    final JavacMessages messages;

    final Names names;

    final boolean allowBoxing;

    final boolean allowCovariantReturns;

    final boolean allowObjectToPrimitiveCast;

    final boolean allowDefaultMethods;

    final ClassReader reader;

    final Check chk;

    JCDiagnostic.Factory diags;

    List<Warner> warnStack = List.nil();

    final Name capturedName;

    private final FunctionDescriptorLookupError functionDescriptorLookupError;

    public final Warner noWarnings;

    // <editor-fold defaultstate="collapsed" desc="Instantiating">

    public static Types instance(Context context) {

        Types instance = context.get(typesKey);

        if (instance == null)

            instance = new Types(context);

        return instance;

    }

    protected Types(Context context) {

        context.put(typesKey, this);

        syms = Symtab.instance(context);

        names = Names.instance(context);

        Source source = Source.instance(context);

        allowBoxing = source.allowBoxing();

        allowCovariantReturns = source.allowCovariantReturns();

        allowObjectToPrimitiveCast = source.allowObjectToPrimitiveCast();

        allowDefaultMethods = source.allowDefaultMethods();

        reader = ClassReader.instance(context);

        chk = Check.instance(context);

        capturedName = names.fromString("<captured wildcard>");

        messages = JavacMessages.instance(context);

        diags = JCDiagnostic.Factory.instance(context);

        functionDescriptorLookupError = new FunctionDescriptorLookupError();

        noWarnings = new Warner(null);

    }

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="upperBound">

    /**

     * The "rvalue conversion".<br>

     * The upper bound of most types is the type

     * itself.  Wildcards, on the other hand have upper

     * and lower bounds.

     * @param t a type

     * @return the upper bound of the given type

     */

    public Type upperBound(Type t) {

        return upperBound.visit(t);

    }

    // where

        private final MapVisitor<Void> upperBound = new MapVisitor<Void>() {

            @Override

            public Type visitWildcardType(WildcardType t, Void ignored) {

                if (t.isSuperBound())

                    return t.bound == null ? syms.objectType : t.bound.bound;

                else

                    return visit(t.type);

            }

            @Override

            public Type visitCapturedType(CapturedType t, Void ignored) {

                return visit(t.bound);

            }

        };

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="lowerBound">

    /**

     * The "lvalue conversion".<br>

     * The lower bound of most types is the type

     * itself.  Wildcards, on the other hand have upper

     * and lower bounds.

     * @param t a type

     * @return the lower bound of the given type

     */

    public Type lowerBound(Type t) {

        return lowerBound.visit(t);

    }

    // where

        private final MapVisitor<Void> lowerBound = new MapVisitor<Void>() {

            @Override

            public Type visitWildcardType(WildcardType t, Void ignored) {

                return t.isExtendsBound() ? syms.botType : visit(t.type);

            }

            @Override

            public Type visitCapturedType(CapturedType t, Void ignored) {

                return visit(t.getLowerBound());

            }

        };

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="isUnbounded">

    /**

     * Checks that all the arguments to a class are unbounded

     * wildcards or something else that doesn't make any restrictions

     * on the arguments. If a class isUnbounded, a raw super- or

     * subclass can be cast to it without a warning.

     * @param t a type

     * @return true iff the given type is unbounded or raw

     */

    public boolean isUnbounded(Type t) {

        return isUnbounded.visit(t);

    }

    // where

        private final UnaryVisitor<Boolean> isUnbounded = new UnaryVisitor<Boolean>() {

            public Boolean visitType(Type t, Void ignored) {

                return true;

            }

            @Override

            public Boolean visitClassType(ClassType t, Void ignored) {

                List<Type> parms = t.tsym.type.allparams();

                List<Type> args = t.allparams();

                while (parms.nonEmpty()) {

                    WildcardType unb = new WildcardType(syms.objectType,

                                                        BoundKind.UNBOUND,

                                                        syms.boundClass,

                                                        (TypeVar)parms.head);

                    if (!containsType(args.head, unb))

                        return false;

                    parms = parms.tail;

                    args = args.tail;

                }

                return true;

            }

        };

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="asSub">

    /**

     * Return the least specific subtype of t that starts with symbol

     * sym.  If none exists, return null.  The least specific subtype

     * is determined as follows:

     *

     * <p>If there is exactly one parameterized instance of sym that is a

     * subtype of t, that parameterized instance is returned.<br>

     * Otherwise, if the plain type or raw type `sym' is a subtype of

     * type t, the type `sym' itself is returned.  Otherwise, null is

     * returned.

     */

    public Type asSub(Type t, Symbol sym) {

        return asSub.visit(t, sym);

    }

    // where

        private final SimpleVisitor<Type,Symbol> asSub = new SimpleVisitor<Type,Symbol>() {

            public Type visitType(Type t, Symbol sym) {

                return null;

            }

            @Override

            public Type visitClassType(ClassType t, Symbol sym) {

                if (t.tsym == sym)

                    return t;

                Type base = asSuper(sym.type, t.tsym);

                if (base == null)

                    return null;

                ListBuffer<Type> from = new ListBuffer<Type>();

                ListBuffer<Type> to = new ListBuffer<Type>();

                try {

                    adapt(base, t, from, to);

                } catch (AdaptFailure ex) {

                    return null;

                }

                Type res = subst(sym.type, from.toList(), to.toList());

                if (!isSubtype(res, t))

                    return null;

                ListBuffer<Type> openVars = new ListBuffer<Type>();

                for (List<Type> l = sym.type.allparams();

                     l.nonEmpty(); l = l.tail)

                    if (res.contains(l.head) && !t.contains(l.head))

                        openVars.append(l.head);

                if (openVars.nonEmpty()) {

                    if (t.isRaw()) {

                        // The subtype of a raw type is raw

                        res = erasure(res);

                    } else {

                        // Unbound type arguments default to ?

                        List<Type> opens = openVars.toList();

                        ListBuffer<Type> qs = new ListBuffer<Type>();

                        for (List<Type> iter = opens; iter.nonEmpty(); iter = iter.tail) {

                            qs.append(new WildcardType(syms.objectType, BoundKind.UNBOUND, syms.boundClass, (TypeVar) iter.head));

                        }

                        res = subst(res, opens, qs.toList());

                    }

                }

                return res;

            }

            @Override

            public Type visitErrorType(ErrorType t, Symbol sym) {

                return t;

            }

        };

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="isConvertible">

    /**

     * Is t a subtype of or convertible via boxing/unboxing

     * conversion to s?

     */

    public boolean isConvertible(Type t, Type s, Warner warn) {

        if (t.tag == ERROR)

            return true;

        boolean tPrimitive = t.isPrimitive();

        boolean sPrimitive = s.isPrimitive();

        if (tPrimitive == sPrimitive) {

            return isSubtypeUnchecked(t, s, warn);

        }

        if (!allowBoxing) return false;

        return tPrimitive

            ? isSubtype(boxedClass(t).type, s)

            : isSubtype(unboxedType(t), s);

    }

    /**

     * Is t a subtype of or convertiable via boxing/unboxing

     * convertions to s?

     */

    public boolean isConvertible(Type t, Type s) {

        return isConvertible(t, s, noWarnings);

    }

    // </editor-fold>

    // <editor-fold defaultstate="collapsed" desc="findSam">

    /**

     * Exception used to report a function descriptor lookup failure. The exception

     * wraps a diagnostic that can be used to generate more details error

     * messages.

     */

    public static class FunctionDescriptorLookupError extends RuntimeException {

        private static final long serialVersionUID = 0;

        JCDiagnostic diagnostic;

        FunctionDescriptorLookupError() {

            this.diagnostic = null;

        }

        FunctionDescriptorLookupError setMessage(JCDiagnostic diag) {

            this.diagnostic = diag;

            return this;

        }

        public JCDiagnostic getDiagnostic() {

            return diagnostic;

        }

    }

    /**

     * A cache that keeps track of function descriptors associated with given

     * functional interfaces.

     */

    class DescriptorCache {

        private WeakHashMap<TypeSymbol, Entry> _map = new WeakHashMap<TypeSymbol, Entry>();

        class FunctionDescriptor {

            Symbol descSym;

            FunctionDescriptor(Symbol descSym) {

                this.descSym = descSym;

            }

            public Symbol getSymbol() {

                return descSym;

            }

            public Type getType(Type site) {

                site = removeWildcards(site);

                if (!chk.checkValidGenericType(site)) {

                    //if the inferred functional interface type is not well-formed,

                    //or if it's not a subtype of the original target, issue an error

                    throw failure(diags.fragment("no.suitable.functional.intf.inst", site));

                }

                return memberType(site, descSym);

            }

        }

        class Entry {

            final FunctionDescriptor cachedDescRes;

            final int prevMark;

            public Entry(FunctionDescriptor cachedDescRes,

                    int prevMark) {

                this.cachedDescRes = cachedDescRes;

                this.prevMark = prevMark;

            }

            boolean matches(int mark) {

                return  this.prevMark == mark;

            }

        }

        FunctionDescriptor get(TypeSymbol origin) throws FunctionDescriptorLookupError {

            Entry e = _map.get(origin);

            CompoundScope members = membersClosure(origin.type, false);

            if (e == null ||

                    !e.matches(members.getMark())) {

                FunctionDescriptor descRes = findDescriptorInternal(origin, members);

                _map.put(origin, new Entry(descRes, members.getMark()));

                return descRes;

            }

            else {

                return e.cachedDescRes;

            }

        }

        /**

         * Compute the function descriptor associated with a given functional interface

         */

        public FunctionDescriptor findDescriptorInternal(TypeSymbol origin, CompoundScope membersCache) throws FunctionDescriptorLookupError {

            if (!origin.isInterface() || (origin.flags() & ANNOTATION) != 0) {

                //t must be an interface

                throw failure("not.a.functional.intf", origin);

            }

            final ListBuffer<Symbol> abstracts = ListBuffer.lb();

            for (Symbol sym : membersCache.getElements(new DescriptorFilter(origin))) {

                Type mtype = memberType(origin.type, sym);

                if (abstracts.isEmpty() ||

                        (sym.name == abstracts.first().name &&

                        overrideEquivalent(mtype, memberType(origin.type, abstracts.first())))) {

                    abstracts.append(sym);

                } else {

                    //the target method(s) should be the only abstract members of t

                    throw failure("not.a.functional.intf.1",  origin,

                            diags.fragment("incompatible.abstracts", Kinds.kindName(origin), origin));

                }

            }

            if (abstracts.isEmpty()) {

                //t must define a suitable non-generic method

                throw failure("not.a.functional.intf.1", origin,

                            diags.fragment("no.abstracts", Kinds.kindName(origin), origin));

            } else if (abstracts.size() == 1) {

                return new FunctionDescriptor(abstracts.first());

            } else { // size > 1

                FunctionDescriptor descRes = mergeDescriptors(origin, abstracts.toList());

                if (descRes == null) {

                    //we can get here if the functional interface is ill-formed

                    ListBuffer<JCDiagnostic> descriptors = ListBuffer.lb();

                    for (Symbol desc : abstracts) {

                        String key = desc.type.getThrownTypes().nonEmpty() ?

                                "descriptor.throws" : "descriptor";

                        descriptors.append(diags.fragment(key, desc.name,

                                desc.type.getParameterTypes(),

                                desc.type.getReturnType(),

                                desc.type.getThrownTypes()));

                    }

                    JCDiagnostic.MultilineDiagnostic incompatibleDescriptors =

                            new JCDiagnostic.MultilineDiagnostic(diags.fragment("incompatible.descs.in.functional.intf",

                            Kinds.kindName(origin), origin), descriptors.toList());

                    throw failure(incompatibleDescriptors);

                }

                return descRes;

            }

        }

        /**

         * Compute a synthetic type for the target descriptor given a list

         * of override-equivalent methods in the functional interface type.

         * The resulting method type is a method type that is override-equivalent

         * and return-type substitutable with each method in the original list.

         */

        private FunctionDescriptor mergeDescriptors(TypeSymbol origin, List<Symbol> methodSyms) {

            //pick argument types - simply take the signature that is a

            //subsignature of all other signatures in the list (as per JLS 8.4.2)

            List<Symbol> mostSpecific = List.nil();

            outer: for (Symbol msym1 : methodSyms) {

                Type mt1 = memberType(origin.type, msym1);

                for (Symbol msym2 : methodSyms) {

                    Type mt2 = memberType(origin.type, msym2);

                    if (!isSubSignature(mt1, mt2)) {

                        continue outer;

                    }

                }

                mostSpecific = mostSpecific.prepend(msym1);

            }

            if (mostSpecific.isEmpty()) {

                return null;

            }

            //pick return types - this is done in two phases: (i) first, the most

            //specific return type is chosen using strict subtyping; if this fails,

            //a second attempt is made using return type substitutability (see JLS 8.4.5)

            boolean phase2 = false;

            Symbol bestSoFar = null;

            while (bestSoFar == null) {

                outer: for (Symbol msym1 : mostSpecific) {

                    Type mt1 = memberType(origin.type, msym1);

                    for (Symbol msym2 : methodSyms) {

                        Type mt2 = memberType(origin.type, msym2);

                        if (phase2 ?

                                !returnTypeSubstitutable(mt1, mt2) :

                                !isSubtypeInternal(mt1.getReturnType(), mt2.getReturnType())) {

                            continue outer;

                        }

                    }

                    bestSoFar = msym1;

                }

                if (phase2) {

                    break;

                } else {

                    phase2 = true;

                }

            }

            if (bestSoFar == null) return null;

            //merge thrown types - form the intersection of all the thrown types in

            //all the signatures in the list

            List<Type> thrown = null;

            for (Symbol msym1 : methodSyms) {

                Type mt1 = memberType(origin.type, msym1);

                thrown = (thrown == null) ?

                    mt1.getThrownTypes() :

                    chk.intersect(mt1.getThrownTypes(), thrown);