/*

 * Copyright 2003-2008 Sun Microsystems, Inc.  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.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package com.sun.tools.javac.code;

import java.util.*;

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

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

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

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

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

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

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

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

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

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 API supported by Sun Microsystems.

 * 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 ClassReader reader;

    final Source source;

    final Check chk;

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

    final Name capturedName;

    // <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);

        allowBoxing = Source.instance(context).allowBoxing();

        reader = ClassReader.instance(context);

        source = Source.instance(context);

        chk = Check.instance(context);

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

        messages = JavacMessages.instance(context);

    }

    // </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 convertiable via boxing/unboxing

     * convertions to s?

     */

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

        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, Warner.noWarnings);

    }

    // </editor-fold>

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

    /**

     * Is t an unchecked subtype of s?

     */

    public boolean isSubtypeUnchecked(Type t, Type s) {

        return isSubtypeUnchecked(t, s, Warner.noWarnings);

    }

    /**

     * Is t an unchecked subtype of s?

     */

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

        if (t.tag == ARRAY && s.tag == ARRAY) {

            return (((ArrayType)t).elemtype.tag <= lastBaseTag)

                ? isSameType(elemtype(t), elemtype(s))

                : isSubtypeUnchecked(elemtype(t), elemtype(s), warn);

        } else if (isSubtype(t, s)) {

            return true;

        }

        else if (t.tag == TYPEVAR) {

            return isSubtypeUnchecked(t.getUpperBound(), s, warn);

        }

        else if (s.tag == UNDETVAR) {

            UndetVar uv = (UndetVar)s;

            if (uv.inst != null)

                return isSubtypeUnchecked(t, uv.inst, warn);

        }

        else if (!s.isRaw()) {

            Type t2 = asSuper(t, s.tsym);

            if (t2 != null && t2.isRaw()) {

                if (isReifiable(s))

                    warn.silentUnchecked();

                else

                    warn.warnUnchecked();

                return true;

            }

        }

        return false;

    }

    /**

     * Is t a subtype of s?<br>

     * (not defined for Method and ForAll types)

     */

    final public boolean isSubtype(Type t, Type s) {

        return isSubtype(t, s, true);

    }

    final public boolean isSubtypeNoCapture(Type t, Type s) {

        return isSubtype(t, s, false);

    }

    public boolean isSubtype(Type t, Type s, boolean capture) {

        if (t == s)

            return true;

        if (s.tag >= firstPartialTag)

            return isSuperType(s, t);

        Type lower = lowerBound(s);

        if (s != lower)

            return isSubtype(capture ? capture(t) : t, lower, false);

        return isSubtype.visit(capture ? capture(t) : t, s);

    }

    // where

        private TypeRelation isSubtype = new TypeRelation()

        {

            public Boolean visitType(Type t, Type s) {

                switch (t.tag) {

                case BYTE: case CHAR:

                    return (t.tag == s.tag ||

                              t.tag + 2 <= s.tag && s.tag <= DOUBLE);

                case SHORT: case INT: case LONG: case FLOAT: case DOUBLE:

                    return t.tag <= s.tag && s.tag <= DOUBLE;

                case BOOLEAN: case VOID:

                    return t.tag == s.tag;

                case TYPEVAR:

                    return isSubtypeNoCapture(t.getUpperBound(), s);

                case BOT:

                    return

                        s.tag == BOT || s.tag == CLASS ||

                        s.tag == ARRAY || s.tag == TYPEVAR;

                case NONE:

                    return false;

                default:

                    throw new AssertionError("isSubtype " + t.tag);

                }

            }

            private Set<TypePair> cache = new HashSet<TypePair>();

            private boolean containsTypeRecursive(Type t, Type s) {

                TypePair pair = new TypePair(t, s);

                if (cache.add(pair)) {

                    try {

                        return containsType(t.getTypeArguments(),

                                            s.getTypeArguments());

                    } finally {

                        cache.remove(pair);

                    }

                } else {

                    return containsType(t.getTypeArguments(),

                                        rewriteSupers(s).getTypeArguments());

                }

            }

            private Type rewriteSupers(Type t) {

                if (!t.isParameterized())

                    return t;

                ListBuffer<Type> from = lb();

                ListBuffer<Type> to = lb();

                adaptSelf(t, from, to);

                if (from.isEmpty())

                    return t;

                ListBuffer<Type> rewrite = lb();

                boolean changed = false;

                for (Type orig : to.toList()) {

                    Type s = rewriteSupers(orig);

                    if (s.isSuperBound() && !s.isExtendsBound()) {

                        s = new WildcardType(syms.objectType,

                                             BoundKind.UNBOUND,

                                             syms.boundClass);

                        changed = true;

                    } else if (s != orig) {

                        s = new WildcardType(upperBound(s),

                                             BoundKind.EXTENDS,

                                             syms.boundClass);

                        changed = true;

                    }

                    rewrite.append(s);

                }

                if (changed)

                    return subst(t.tsym.type, from.toList(), rewrite.toList());

                else

                    return t;

            }

            @Override

            public Boolean visitClassType(ClassType t, Type s) {

                Type sup = asSuper(t, s.tsym);

                return sup != null

                    && sup.tsym == s.tsym

                    // You're not allowed to write

                    //     Vector<Object> vec = new Vector<String>();

                    // But with wildcards you can write

                    //     Vector<? extends Object> vec = new Vector<String>();

                    // which means that subtype checking must be done

                    // here instead of same-type checking (via containsType).

                    && (!s.isParameterized() || containsTypeRecursive(s, sup))

                    && isSubtypeNoCapture(sup.getEnclosingType(),

                                          s.getEnclosingType());

            }

            @Override

            public Boolean visitArrayType(ArrayType t, Type s) {

                if (s.tag == ARRAY) {

                    if (t.elemtype.tag <= lastBaseTag)

                        return isSameType(t.elemtype, elemtype(s));

                    else

                        return isSubtypeNoCapture(t.elemtype, elemtype(s));

                }

                if (s.tag == CLASS) {

                    Name sname = s.tsym.getQualifiedName();

                    return sname == names.java_lang_Object

                        || sname == names.java_lang_Cloneable

                        || sname == names.java_io_Serializable;

                }

                return false;

            }

            @Override

            public Boolean visitUndetVar(UndetVar t, Type s) {

                //todo: test against origin needed? or replace with substitution?

                if (t == s || t.qtype == s || s.tag == ERROR || s.tag == UNKNOWN)

                    return true;

                if (t.inst != null)

                    return isSubtypeNoCapture(t.inst, s); // TODO: ", warn"?

                t.hibounds = t.hibounds.prepend(s);

                return true;

            }

            @Override

            public Boolean visitErrorType(ErrorType t, Type s) {

                return true;

            }

        };

    /**

     * Is t a subtype of every type in given list `ts'?<br>

     * (not defined for Method and ForAll types)<br>

     * Allows unchecked conversions.

     */

    public boolean isSubtypeUnchecked(Type t, List<Type> ts, Warner warn) {

        for (List<Type> l = ts; l.nonEmpty(); l = l.tail)

            if (!isSubtypeUnchecked(t, l.head, warn))

                return false;

        return true;

    }

    /**

     * Are corresponding elements of ts subtypes of ss?  If lists are

     * of different length, return false.

     */

    public boolean isSubtypes(List<Type> ts, List<Type> ss) {

        while (ts.tail != null && ss.tail != null

               /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&

               isSubtype(ts.head, ss.head)) {

            ts = ts.tail;

            ss = ss.tail;

        }

        return ts.tail == null && ss.tail == null;

        /*inlined: ts.isEmpty() && ss.isEmpty();*/

    }

    /**

     * Are corresponding elements of ts subtypes of ss, allowing

     * unchecked conversions?  If lists are of different length,

     * return false.

     **/

    public boolean isSubtypesUnchecked(List<Type> ts, List<Type> ss, Warner warn) {

        while (ts.tail != null && ss.tail != null

               /*inlined: ts.nonEmpty() && ss.nonEmpty()*/ &&

               isSubtypeUnchecked(ts.head, ss.head, warn)) {

            ts = ts.tail;

            ss = ss.tail;

        }

        return ts.tail == null && ss.tail == null;

        /*inlined: ts.isEmpty() && ss.isEmpty();*/

    }

    // </editor-fold>

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

    /**

     * Is t a supertype of s?

     */

    public boolean isSuperType(Type t, Type s) {

        switch (t.tag) {

        case ERROR: