/*

 * Copyright (c) 2003, 2017, 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.HashSet;

import java.util.HashMap;

import java.util.Locale;

import java.util.Map;

import java.util.Optional;

import java.util.Set;

import java.util.WeakHashMap;

import java.util.function.BiPredicate;

import java.util.function.Function;

import java.util.stream.Collector;

import javax.tools.JavaFileObject;

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

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

import com.sun.tools.javac.code.Source.Feature;

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

import com.sun.tools.javac.code.TypeMetadata.Entry.Kind;

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

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

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

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

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.Kinds.Kind.*;

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

import static com.sun.tools.javac.code.Scope.LookupKind.NON_RECURSIVE;

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 com.sun.tools.javac.resources.CompilerProperties.Fragments;

/**

 * 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<>();

    final Symtab syms;

    final JavacMessages messages;

    final Names names;

    final boolean allowObjectToPrimitiveCast;

    final boolean allowDefaultMethods;

    final boolean mapCapturesToBounds;

    final Check chk;

    final Enter enter;

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

        allowObjectToPrimitiveCast = Feature.OBJECT_TO_PRIMITIVE_CAST.allowedInSource(source);

        allowDefaultMethods = Feature.DEFAULT_METHODS.allowedInSource(source);

        mapCapturesToBounds = Feature.MAP_CAPTURES_TO_BOUNDS.allowedInSource(source);

        chk = Check.instance(context);

        enter = Enter.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="bounds">

    /**

     * Get a wildcard's upper bound, returning non-wildcards unchanged.

     * @param t a type argument, either a wildcard or a type

     */

    public Type wildUpperBound(Type t) {

        if (t.hasTag(WILDCARD)) {

            WildcardType w = (WildcardType) t;

            if (w.isSuperBound())

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

            else

                return wildUpperBound(w.type);

        }

        else return t;

    }

    /**

     * Get a capture variable's upper bound, returning other types unchanged.

     * @param t a type

     */

    public Type cvarUpperBound(Type t) {

        if (t.hasTag(TYPEVAR)) {

            TypeVar v = (TypeVar) t;

            return v.isCaptured() ? cvarUpperBound(v.bound) : v;

        }

        else return t;

    }

    /**

     * Get a wildcard's lower bound, returning non-wildcards unchanged.

     * @param t a type argument, either a wildcard or a type

     */

    public Type wildLowerBound(Type t) {

        if (t.hasTag(WILDCARD)) {

            WildcardType w = (WildcardType) t;

            return w.isExtendsBound() ? syms.botType : wildLowerBound(w.type);

        }

        else return t;

    }

    /**

     * Get a capture variable's lower bound, returning other types unchanged.

     * @param t a type

     */

    public Type cvarLowerBound(Type t) {

        if (t.hasTag(TYPEVAR) && ((TypeVar) t).isCaptured()) {

            return cvarLowerBound(t.getLowerBound());

        }

        else return t;

    }

    /**

     * Recursively skip type-variables until a class/array type is found; capture conversion is then

     * (optionally) applied to the resulting type. This is useful for i.e. computing a site that is

     * suitable for a method lookup.

     */

    public Type skipTypeVars(Type site, boolean capture) {

        while (site.hasTag(TYPEVAR)) {

            site = site.getUpperBound();

        }

        return capture ? capture(site) : site;

    }

    // </editor-fold>

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

    /**

     * A projection kind. See {@link TypeProjection}

     */

    enum ProjectionKind {

        UPWARDS() {

            @Override

            ProjectionKind complement() {

                return DOWNWARDS;

            }

        },

        DOWNWARDS() {

            @Override

            ProjectionKind complement() {

                return UPWARDS;

            }

        };

        abstract ProjectionKind complement();

    }

    /**

     * This visitor performs upwards and downwards projections on types.

     *

     * A projection is defined as a function that takes a type T, a set of type variables V and that

     * produces another type S.

     *

     * An upwards projection maps a type T into a type S such that (i) T has no variables in V,

     * and (ii) S is an upper bound of T.

     *

     * A downwards projection maps a type T into a type S such that (i) T has no variables in V,

     * and (ii) S is a lower bound of T.

     *

     * Note that projections are only allowed to touch variables in V. Theferore it is possible for

     * a projection to leave its input type unchanged if it does not contain any variables in V.

     *

     * Moreover, note that while an upwards projection is always defined (every type as an upper bound),

     * a downwards projection is not always defined.

     *

     * Examples:

     *

     * {@code upwards(List<#CAP1>, [#CAP1]) = List<? extends String>, where #CAP1 <: String }

     * {@code downwards(List<#CAP2>, [#CAP2]) = List<? super String>, where #CAP2 :> String }

     * {@code upwards(List<#CAP1>, [#CAP2]) = List<#CAP1> }

     * {@code downwards(List<#CAP1>, [#CAP1]) = not defined }

     */

    class TypeProjection extends TypeMapping<ProjectionKind> {

        List<Type> vars;

        Set<Type> seen = new HashSet<>();

        public TypeProjection(List<Type> vars) {

            this.vars = vars;

        }

        @Override

        public Type visitClassType(ClassType t, ProjectionKind pkind) {

            if (t.isCompound()) {

                List<Type> components = directSupertypes(t);

                List<Type> components1 = components.map(c -> c.map(this, pkind));

                if (components == components1) return t;

                else return makeIntersectionType(components1);

            } else {

                Type outer = t.getEnclosingType();

                Type outer1 = visit(outer, pkind);

                List<Type> typarams = t.getTypeArguments();

                List<Type> formals = t.tsym.type.getTypeArguments();

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

                boolean changed = false;

                for (Type actual : typarams) {

                    Type t2 = mapTypeArgument(t, formals.head.getUpperBound(), actual, pkind);

                    if (t2.hasTag(BOT)) {

                        //not defined

                        return syms.botType;

                    }

                    typarams1.add(t2);

                    changed |= actual != t2;

                    formals = formals.tail;

                }

                if (outer1 == outer && !changed) return t;

                else return new ClassType(outer1, typarams1.toList(), t.tsym, t.getMetadata()) {

                    @Override

                    protected boolean needsStripping() {

                        return true;

                    }

                };

            }

        }

        @Override

        public Type visitArrayType(ArrayType t, ProjectionKind s) {

            Type elemtype = t.elemtype;

            Type elemtype1 = visit(elemtype, s);

            if (elemtype1 == elemtype) {

                return t;

            } else if (elemtype1.hasTag(BOT)) {

                //undefined

                return syms.botType;

            } else {

                return new ArrayType(elemtype1, t.tsym, t.metadata) {

                    @Override

                    protected boolean needsStripping() {

                        return true;

                    }

                };

            }

        }

        @Override

        public Type visitTypeVar(TypeVar t, ProjectionKind pkind) {

            if (vars.contains(t)) {

                if (seen.add(t)) {

                    try {

                        final Type bound;

                        switch (pkind) {

                            case UPWARDS:

                                bound = t.getUpperBound();

                                break;

                            case DOWNWARDS:

                                bound = (t.getLowerBound() == null) ?

                                        syms.botType :

                                        t.getLowerBound();

                                break;

                            default:

                                Assert.error();

                                return null;

                        }

                        return bound.map(this, pkind);

                    } finally {

                        seen.remove(t);

                    }

                } else {

                    //cycle

                    return pkind == ProjectionKind.UPWARDS ?

                            syms.objectType : syms.botType;

                }

            } else {

                return t;

            }

        }

        private Type mapTypeArgument(Type site, Type declaredBound, Type t, ProjectionKind pkind) {

            return t.containsAny(vars) ?

                    t.map(new TypeArgumentProjection(site, declaredBound), pkind) :

                    t;

        }

        class TypeArgumentProjection extends TypeMapping<ProjectionKind> {

            Type site;

            Type declaredBound;

            TypeArgumentProjection(Type site, Type declaredBound) {

                this.site = site;

                this.declaredBound = declaredBound;

            }

            @Override

            public Type visitType(Type t, ProjectionKind pkind) {

                //type argument is some type containing restricted vars

                if (pkind == ProjectionKind.DOWNWARDS) {

                    //not defined

                    return syms.botType;

                }

                Type upper = t.map(TypeProjection.this, ProjectionKind.UPWARDS);

                Type lower = t.map(TypeProjection.this, ProjectionKind.DOWNWARDS);

                List<Type> formals = site.tsym.type.getTypeArguments();

                BoundKind bk;

                Type bound;

                if (!isSameType(upper, syms.objectType) &&

                        (declaredBound.containsAny(formals) ||

                         !isSubtype(declaredBound, upper))) {

                    bound = upper;

                    bk = EXTENDS;

                } else if (!lower.hasTag(BOT)) {

                    bound = lower;

                    bk = SUPER;

                } else {

                    bound = syms.objectType;

                    bk = UNBOUND;

                }

                return makeWildcard(bound, bk);

            }

            @Override

            public Type visitWildcardType(WildcardType wt, ProjectionKind pkind) {

                //type argument is some wildcard whose bound contains restricted vars

                Type bound = syms.botType;

                BoundKind bk = wt.kind;

                switch (wt.kind) {

                    case EXTENDS:

                        bound = wt.type.map(TypeProjection.this, pkind);

                        if (bound.hasTag(BOT)) {

                            return syms.botType;

                        }

                        break;

                    case SUPER:

                        bound = wt.type.map(TypeProjection.this, pkind.complement());

                        if (bound.hasTag(BOT)) {

                            bound = syms.objectType;

                            bk = UNBOUND;

                        }

                        break;

                }

                return makeWildcard(bound, bk);

            }

            private Type makeWildcard(Type bound, BoundKind bk) {

                return new WildcardType(bound, bk, syms.boundClass) {

                    @Override

                    protected boolean needsStripping() {

                        return true;

                    }

                };

            }

        }

    }

    /**

     * Computes an upward projection of given type, and vars. See {@link TypeProjection}.

     *

     * @param t the type to be projected

     * @param vars the set of type variables to be mapped

     * @return the type obtained as result of the projection

     */

    public Type upward(Type t, List<Type> vars) {

        return t.map(new TypeProjection(vars), ProjectionKind.UPWARDS);

    }

    /**

     * Computes the set of captured variables mentioned in a given type. See {@link CaptureScanner}.

     * This routine is typically used to computed the input set of variables to be used during

     * an upwards projection (see {@link Types#upward(Type, List)}).

     *

     * @param t the type where occurrences of captured variables have to be found

     * @return the set of captured variables found in t

     */

    public List<Type> captures(Type t) {

        CaptureScanner cs = new CaptureScanner();

        Set<Type> captures = new HashSet<>();

        cs.visit(t, captures);

        return List.from(captures);

    }

    /**

     * This visitor scans a type recursively looking for occurrences of captured type variables.

     */

    class CaptureScanner extends SimpleVisitor<Void, Set<Type>> {

        @Override

        public Void visitType(Type t, Set<Type> types) {

            return null;

        }

        @Override

        public Void visitClassType(ClassType t, Set<Type> seen) {

            if (t.isCompound()) {

                directSupertypes(t).forEach(s -> visit(s, seen));

            } else {

                t.allparams().forEach(ta -> visit(ta, seen));

            }

            return null;

        }

        @Override

        public Void visitArrayType(ArrayType t, Set<Type> seen) {

            return visit(t.elemtype, seen);

        }

        @Override

        public Void visitWildcardType(WildcardType t, Set<Type> seen) {

            visit(t.type, seen);

            return null;

        }

        @Override

        public Void visitTypeVar(TypeVar t, Set<Type> seen) {

            if ((t.tsym.flags() & Flags.SYNTHETIC) != 0 && seen.add(t)) {

                visit(t.getUpperBound(), seen);

            }

            return null;

        }

        @Override

        public Void visitCapturedType(CapturedType t, Set<Type> seen) {

            if (seen.add(t)) {

                visit(t.getUpperBound(), seen);

                visit(t.getLowerBound(), seen);

            }

            return null;

        }

    }

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