aoqi@0: /*
aoqi@0: * Copyright (c) 1999, 2014, Oracle and/or its affiliates. All rights reserved.
aoqi@0: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
aoqi@0: *
aoqi@0: * This code is free software; you can redistribute it and/or modify it
aoqi@0: * under the terms of the GNU General Public License version 2 only, as
aoqi@0: * published by the Free Software Foundation. Oracle designates this
aoqi@0: * particular file as subject to the "Classpath" exception as provided
aoqi@0: * by Oracle in the LICENSE file that accompanied this code.
aoqi@0: *
aoqi@0: * This code is distributed in the hope that it will be useful, but WITHOUT
aoqi@0: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
aoqi@0: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
aoqi@0: * version 2 for more details (a copy is included in the LICENSE file that
aoqi@0: * accompanied this code).
aoqi@0: *
aoqi@0: * You should have received a copy of the GNU General Public License version
aoqi@0: * 2 along with this work; if not, write to the Free Software Foundation,
aoqi@0: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
aoqi@0: *
aoqi@0: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
aoqi@0: * or visit www.oracle.com if you need additional information or have any
aoqi@0: * questions.
aoqi@0: */
aoqi@0:
aoqi@0: package com.sun.tools.javac.comp;
aoqi@0:
aoqi@0: import com.sun.tools.javac.tree.JCTree;
aoqi@0: import com.sun.tools.javac.tree.JCTree.JCTypeCast;
aoqi@0: import com.sun.tools.javac.tree.TreeInfo;
aoqi@0: import com.sun.tools.javac.util.*;
aoqi@0: import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
aoqi@0: import com.sun.tools.javac.util.List;
aoqi@0: import com.sun.tools.javac.code.*;
aoqi@0: import com.sun.tools.javac.code.Type.*;
aoqi@0: import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
aoqi@0: import com.sun.tools.javac.code.Symbol.*;
aoqi@0: import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
aoqi@0: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
aoqi@0: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
aoqi@0: import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
aoqi@0: import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
aoqi@0: import com.sun.tools.javac.util.GraphUtils.TarjanNode;
aoqi@0:
aoqi@0: import java.util.ArrayList;
aoqi@0: import java.util.Collections;
aoqi@0: import java.util.EnumMap;
aoqi@0: import java.util.EnumSet;
aoqi@0: import java.util.HashMap;
aoqi@0: import java.util.HashSet;
aoqi@0: import java.util.LinkedHashSet;
aoqi@0: import java.util.Map;
aoqi@0: import java.util.Set;
aoqi@0:
aoqi@0: import static com.sun.tools.javac.code.TypeTag.*;
aoqi@0:
aoqi@0: /** Helper class for type parameter inference, used by the attribution phase.
aoqi@0: *
aoqi@0: *
This is NOT part of any supported API.
aoqi@0: * If you write code that depends on this, you do so at your own risk.
aoqi@0: * This code and its internal interfaces are subject to change or
aoqi@0: * deletion without notice.
aoqi@0: */
aoqi@0: public class Infer {
aoqi@0: protected static final Context.Key inferKey =
aoqi@0: new Context.Key();
aoqi@0:
aoqi@0: Resolve rs;
aoqi@0: Check chk;
aoqi@0: Symtab syms;
aoqi@0: Types types;
aoqi@0: JCDiagnostic.Factory diags;
aoqi@0: Log log;
aoqi@0:
aoqi@0: /** should the graph solver be used? */
aoqi@0: boolean allowGraphInference;
aoqi@0:
aoqi@0: public static Infer instance(Context context) {
aoqi@0: Infer instance = context.get(inferKey);
aoqi@0: if (instance == null)
aoqi@0: instance = new Infer(context);
aoqi@0: return instance;
aoqi@0: }
aoqi@0:
aoqi@0: protected Infer(Context context) {
aoqi@0: context.put(inferKey, this);
aoqi@0:
aoqi@0: rs = Resolve.instance(context);
aoqi@0: chk = Check.instance(context);
aoqi@0: syms = Symtab.instance(context);
aoqi@0: types = Types.instance(context);
aoqi@0: diags = JCDiagnostic.Factory.instance(context);
aoqi@0: log = Log.instance(context);
aoqi@0: inferenceException = new InferenceException(diags);
aoqi@0: Options options = Options.instance(context);
aoqi@0: allowGraphInference = Source.instance(context).allowGraphInference()
aoqi@0: && options.isUnset("useLegacyInference");
aoqi@0: }
aoqi@0:
aoqi@0: /** A value for prototypes that admit any type, including polymorphic ones. */
aoqi@0: public static final Type anyPoly = new JCNoType();
aoqi@0:
aoqi@0: /**
aoqi@0: * This exception class is design to store a list of diagnostics corresponding
aoqi@0: * to inference errors that can arise during a method applicability check.
aoqi@0: */
aoqi@0: public static class InferenceException extends InapplicableMethodException {
aoqi@0: private static final long serialVersionUID = 0;
aoqi@0:
aoqi@0: List messages = List.nil();
aoqi@0:
aoqi@0: InferenceException(JCDiagnostic.Factory diags) {
aoqi@0: super(diags);
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage() {
aoqi@0: //no message to set
aoqi@0: return this;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(JCDiagnostic diag) {
aoqi@0: messages = messages.append(diag);
aoqi@0: return this;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public JCDiagnostic getDiagnostic() {
aoqi@0: return messages.head;
aoqi@0: }
aoqi@0:
aoqi@0: void clear() {
aoqi@0: messages = List.nil();
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: protected final InferenceException inferenceException;
aoqi@0:
aoqi@0: //
aoqi@0: /**
aoqi@0: * Main inference entry point - instantiate a generic method type
aoqi@0: * using given argument types and (possibly) an expected target-type.
aoqi@0: */
aoqi@0: Type instantiateMethod( Env env,
aoqi@0: List tvars,
aoqi@0: MethodType mt,
aoqi@0: Attr.ResultInfo resultInfo,
aoqi@0: MethodSymbol msym,
aoqi@0: List argtypes,
aoqi@0: boolean allowBoxing,
aoqi@0: boolean useVarargs,
aoqi@0: Resolve.MethodResolutionContext resolveContext,
aoqi@0: Warner warn) throws InferenceException {
aoqi@0: //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
aoqi@0: final InferenceContext inferenceContext = new InferenceContext(tvars); //B0
aoqi@0: inferenceException.clear();
aoqi@0: try {
aoqi@0: DeferredAttr.DeferredAttrContext deferredAttrContext =
aoqi@0: resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
aoqi@0:
aoqi@0: resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2
aoqi@0: argtypes, mt.getParameterTypes(), warn);
aoqi@0:
aoqi@0: if (allowGraphInference &&
aoqi@0: resultInfo != null &&
aoqi@0: !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
aoqi@0: //inject return constraints earlier
aoqi@0: checkWithinBounds(inferenceContext, warn); //propagation
aoqi@0: Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3
aoqi@0: mt, inferenceContext);
aoqi@0: mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
aoqi@0: //propagate outwards if needed
aoqi@0: if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
aoqi@0: //propagate inference context outwards and exit
aoqi@0: inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
aoqi@0: deferredAttrContext.complete();
aoqi@0: return mt;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: deferredAttrContext.complete();
aoqi@0:
aoqi@0: // minimize as yet undetermined type variables
aoqi@0: if (allowGraphInference) {
aoqi@0: inferenceContext.solve(warn);
aoqi@0: } else {
aoqi@0: inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
aoqi@0: }
aoqi@0:
aoqi@0: mt = (MethodType)inferenceContext.asInstType(mt);
aoqi@0:
aoqi@0: if (!allowGraphInference &&
aoqi@0: inferenceContext.restvars().nonEmpty() &&
aoqi@0: resultInfo != null &&
aoqi@0: !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
aoqi@0: generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext);
aoqi@0: inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
aoqi@0: mt = (MethodType)inferenceContext.asInstType(mt);
aoqi@0: }
aoqi@0:
aoqi@0: if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
aoqi@0: log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
aoqi@0: }
aoqi@0:
aoqi@0: // return instantiated version of method type
aoqi@0: return mt;
aoqi@0: } finally {
aoqi@0: if (resultInfo != null || !allowGraphInference) {
aoqi@0: inferenceContext.notifyChange();
aoqi@0: } else {
aoqi@0: inferenceContext.notifyChange(inferenceContext.boundedVars());
aoqi@0: }
aoqi@0: if (resultInfo == null) {
aoqi@0: /* if the is no result info then we can clear the capture types
aoqi@0: * cache without affecting any result info check
aoqi@0: */
aoqi@0: inferenceContext.captureTypeCache.clear();
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Generate constraints from the generic method's return type. If the method
aoqi@0: * call occurs in a context where a type T is expected, use the expected
aoqi@0: * type to derive more constraints on the generic method inference variables.
aoqi@0: */
aoqi@0: Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo,
aoqi@0: MethodType mt, InferenceContext inferenceContext) {
aoqi@0: InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext();
aoqi@0: Type from = mt.getReturnType();
aoqi@0: if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
aoqi@0: rsInfoInfContext != emptyContext) {
aoqi@0: from = types.capture(from);
aoqi@0: //add synthetic captured ivars
aoqi@0: for (Type t : from.getTypeArguments()) {
aoqi@0: if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
aoqi@0: inferenceContext.addVar((TypeVar)t);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: Type qtype = inferenceContext.asUndetVar(from);
aoqi@0: Type to = resultInfo.pt;
aoqi@0:
aoqi@0: if (qtype.hasTag(VOID)) {
aoqi@0: to = syms.voidType;
aoqi@0: } else if (to.hasTag(NONE)) {
aoqi@0: to = from.isPrimitive() ? from : syms.objectType;
aoqi@0: } else if (qtype.hasTag(UNDETVAR)) {
aoqi@0: if (resultInfo.pt.isReference()) {
aoqi@0: to = generateReturnConstraintsUndetVarToReference(
aoqi@0: tree, (UndetVar)qtype, to, resultInfo, inferenceContext);
aoqi@0: } else {
aoqi@0: if (to.isPrimitive()) {
aoqi@0: to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to,
aoqi@0: resultInfo, inferenceContext);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: Assert.check(allowGraphInference || !rsInfoInfContext.free(to),
aoqi@0: "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
aoqi@0: //we need to skip capture?
aoqi@0: Warner retWarn = new Warner();
aoqi@0: if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) ||
aoqi@0: //unchecked conversion is not allowed in source 7 mode
aoqi@0: (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
aoqi@0: throw inferenceException
aoqi@0: .setMessage("infer.no.conforming.instance.exists",
aoqi@0: inferenceContext.restvars(), mt.getReturnType(), to);
aoqi@0: }
aoqi@0: return from;
aoqi@0: }
aoqi@0:
aoqi@0: private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from,
aoqi@0: Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) {
aoqi@0: if (!allowGraphInference) {
aoqi@0: //if legacy, just return boxed type
aoqi@0: return types.boxedClass(to).type;
aoqi@0: }
aoqi@0: //if graph inference we need to skip conflicting boxed bounds...
aoqi@0: for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER,
aoqi@0: InferenceBound.LOWER)) {
aoqi@0: Type boundAsPrimitive = types.unboxedType(t);
aoqi@0: if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) {
aoqi@0: continue;
aoqi@0: }
aoqi@0: return generateReferenceToTargetConstraint(tree, from, to,
aoqi@0: resultInfo, inferenceContext);
aoqi@0: }
aoqi@0: return types.boxedClass(to).type;
aoqi@0: }
aoqi@0:
aoqi@0: private Type generateReturnConstraintsUndetVarToReference(JCTree tree,
aoqi@0: UndetVar from, Type to, Attr.ResultInfo resultInfo,
aoqi@0: InferenceContext inferenceContext) {
aoqi@0: Type captureOfTo = types.capture(to);
aoqi@0: /* T is a reference type, but is not a wildcard-parameterized type, and either
aoqi@0: */
aoqi@0: if (captureOfTo == to) { //not a wildcard parameterized type
aoqi@0: /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha,
aoqi@0: * where S is a wildcard-parameterized type, or
aoqi@0: */
aoqi@0: for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
aoqi@0: Type captureOfBound = types.capture(t);
aoqi@0: if (captureOfBound != t) {
aoqi@0: return generateReferenceToTargetConstraint(tree, from, to,
aoqi@0: resultInfo, inferenceContext);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
aoqi@0: * where S1 and S2 have supertypes that are two different
aoqi@0: * parameterizations of the same generic class or interface.
aoqi@0: */
aoqi@0: for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) {
aoqi@0: for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) {
aoqi@0: if (aLowerBound != anotherLowerBound &&
aoqi@0: commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) {
aoqi@0: /* self comment check if any lower bound may be and undetVar,
aoqi@0: * in that case the result of this call may be a false positive.
aoqi@0: * Should this be restricted to non free types?
aoqi@0: */
aoqi@0: return generateReferenceToTargetConstraint(tree, from, to,
aoqi@0: resultInfo, inferenceContext);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /* T is a parameterization of a generic class or interface, G,
aoqi@0: * and B2 contains a bound of one of the forms alpha = S or S <: alpha,
aoqi@0: * where there exists no type of the form G<...> that is a
aoqi@0: * supertype of S, but the raw type G is a supertype of S
aoqi@0: */
aoqi@0: if (to.isParameterized()) {
aoqi@0: for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
aoqi@0: Type sup = types.asSuper(t, to.tsym);
aoqi@0: if (sup != null && sup.isRaw()) {
aoqi@0: return generateReferenceToTargetConstraint(tree, from, to,
aoqi@0: resultInfo, inferenceContext);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: return to;
aoqi@0: }
aoqi@0:
aoqi@0: private boolean commonSuperWithDiffParameterization(Type t, Type s) {
aoqi@0: Pair supers = getParameterizedSupers(t, s);
aoqi@0: return (supers != null && !types.isSameType(supers.fst, supers.snd));
aoqi@0: }
aoqi@0:
aoqi@0: private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from,
aoqi@0: Type to, Attr.ResultInfo resultInfo,
aoqi@0: InferenceContext inferenceContext) {
aoqi@0: inferenceContext.solve(List.of(from.qtype), new Warner());
vromero@2543: inferenceContext.notifyChange();
aoqi@0: Type capturedType = resultInfo.checkContext.inferenceContext()
aoqi@0: .cachedCapture(tree, from.inst, false);
aoqi@0: if (types.isConvertible(capturedType,
aoqi@0: resultInfo.checkContext.inferenceContext().asUndetVar(to))) {
aoqi@0: //effectively skip additional return-type constraint generation (compatibility)
aoqi@0: return syms.objectType;
aoqi@0: }
aoqi@0: return to;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Infer cyclic inference variables as described in 15.12.2.8.
aoqi@0: */
aoqi@0: private void instantiateAsUninferredVars(List vars, InferenceContext inferenceContext) {
aoqi@0: ListBuffer todo = new ListBuffer<>();
aoqi@0: //step 1 - create fresh tvars
aoqi@0: for (Type t : vars) {
aoqi@0: UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
aoqi@0: List upperBounds = uv.getBounds(InferenceBound.UPPER);
aoqi@0: if (Type.containsAny(upperBounds, vars)) {
aoqi@0: TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
aoqi@0: fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
aoqi@0: todo.append(uv);
aoqi@0: uv.inst = fresh_tvar.type;
aoqi@0: } else if (upperBounds.nonEmpty()) {
aoqi@0: uv.inst = types.glb(upperBounds);
aoqi@0: } else {
aoqi@0: uv.inst = syms.objectType;
aoqi@0: }
aoqi@0: }
aoqi@0: //step 2 - replace fresh tvars in their bounds
aoqi@0: List formals = vars;
aoqi@0: for (Type t : todo) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: TypeVar ct = (TypeVar)uv.inst;
aoqi@0: ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
aoqi@0: if (ct.bound.isErroneous()) {
aoqi@0: //report inference error if glb fails
aoqi@0: reportBoundError(uv, BoundErrorKind.BAD_UPPER);
aoqi@0: }
aoqi@0: formals = formals.tail;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Compute a synthetic method type corresponding to the requested polymorphic
aoqi@0: * method signature. The target return type is computed from the immediately
aoqi@0: * enclosing scope surrounding the polymorphic-signature call.
aoqi@0: */
aoqi@0: Type instantiatePolymorphicSignatureInstance(Env env,
aoqi@0: MethodSymbol spMethod, // sig. poly. method or null if none
aoqi@0: Resolve.MethodResolutionContext resolveContext,
aoqi@0: List argtypes) {
aoqi@0: final Type restype;
aoqi@0:
aoqi@0: //The return type for a polymorphic signature call is computed from
aoqi@0: //the enclosing tree E, as follows: if E is a cast, then use the
aoqi@0: //target type of the cast expression as a return type; if E is an
aoqi@0: //expression statement, the return type is 'void' - otherwise the
aoqi@0: //return type is simply 'Object'. A correctness check ensures that
aoqi@0: //env.next refers to the lexically enclosing environment in which
aoqi@0: //the polymorphic signature call environment is nested.
aoqi@0:
aoqi@0: switch (env.next.tree.getTag()) {
aoqi@0: case TYPECAST:
aoqi@0: JCTypeCast castTree = (JCTypeCast)env.next.tree;
aoqi@0: restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
aoqi@0: castTree.clazz.type :
aoqi@0: syms.objectType;
aoqi@0: break;
aoqi@0: case EXEC:
aoqi@0: JCTree.JCExpressionStatement execTree =
aoqi@0: (JCTree.JCExpressionStatement)env.next.tree;
aoqi@0: restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
aoqi@0: syms.voidType :
aoqi@0: syms.objectType;
aoqi@0: break;
aoqi@0: default:
aoqi@0: restype = syms.objectType;
aoqi@0: }
aoqi@0:
aoqi@0: List paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
aoqi@0: List exType = spMethod != null ?
aoqi@0: spMethod.getThrownTypes() :
aoqi@0: List.of(syms.throwableType); // make it throw all exceptions
aoqi@0:
aoqi@0: MethodType mtype = new MethodType(paramtypes,
aoqi@0: restype,
aoqi@0: exType,
aoqi@0: syms.methodClass);
aoqi@0: return mtype;
aoqi@0: }
aoqi@0: //where
aoqi@0: class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
aoqi@0:
aoqi@0: public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
vromero@2543: (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase);
aoqi@0: }
aoqi@0:
aoqi@0: public Type apply(Type t) {
aoqi@0: t = types.erasure(super.apply(t));
aoqi@0: if (t.hasTag(BOT))
aoqi@0: // nulls type as the marker type Null (which has no instances)
aoqi@0: // infer as java.lang.Void for now
aoqi@0: t = types.boxedClass(syms.voidType).type;
aoqi@0: return t;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This method is used to infer a suitable target SAM in case the original
aoqi@0: * SAM type contains one or more wildcards. An inference process is applied
aoqi@0: * so that wildcard bounds, as well as explicit lambda/method ref parameters
aoqi@0: * (where applicable) are used to constraint the solution.
aoqi@0: */
aoqi@0: public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
aoqi@0: List paramTypes, Check.CheckContext checkContext) {
aoqi@0: if (types.capture(funcInterface) == funcInterface) {
aoqi@0: //if capture doesn't change the type then return the target unchanged
aoqi@0: //(this means the target contains no wildcards!)
aoqi@0: return funcInterface;
aoqi@0: } else {
aoqi@0: Type formalInterface = funcInterface.tsym.type;
aoqi@0: InferenceContext funcInterfaceContext =
aoqi@0: new InferenceContext(funcInterface.tsym.type.getTypeArguments());
aoqi@0:
aoqi@0: Assert.check(paramTypes != null);
aoqi@0: //get constraints from explicit params (this is done by
aoqi@0: //checking that explicit param types are equal to the ones
aoqi@0: //in the functional interface descriptors)
aoqi@0: List descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
aoqi@0: if (descParameterTypes.size() != paramTypes.size()) {
aoqi@0: checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
aoqi@0: return types.createErrorType(funcInterface);
aoqi@0: }
aoqi@0: for (Type p : descParameterTypes) {
aoqi@0: if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) {
aoqi@0: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
aoqi@0: return types.createErrorType(funcInterface);
aoqi@0: }
aoqi@0: paramTypes = paramTypes.tail;
aoqi@0: }
aoqi@0:
aoqi@0: try {
aoqi@0: funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
aoqi@0: } catch (InferenceException ex) {
aoqi@0: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
aoqi@0: }
aoqi@0:
aoqi@0: List actualTypeargs = funcInterface.getTypeArguments();
aoqi@0: for (Type t : funcInterfaceContext.undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: if (uv.inst == null) {
aoqi@0: uv.inst = actualTypeargs.head;
aoqi@0: }
aoqi@0: actualTypeargs = actualTypeargs.tail;
aoqi@0: }
aoqi@0:
aoqi@0: Type owntype = funcInterfaceContext.asInstType(formalInterface);
aoqi@0: if (!chk.checkValidGenericType(owntype)) {
aoqi@0: //if the inferred functional interface type is not well-formed,
aoqi@0: //or if it's not a subtype of the original target, issue an error
aoqi@0: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
aoqi@0: }
vromero@2543: //propagate constraints as per JLS 18.2.1
vromero@2543: checkContext.compatible(owntype, funcInterface, types.noWarnings);
aoqi@0: return owntype;
aoqi@0: }
aoqi@0: }
aoqi@0: //
aoqi@0:
aoqi@0: //
aoqi@0: /**
aoqi@0: * Check bounds and perform incorporation
aoqi@0: */
aoqi@0: void checkWithinBounds(InferenceContext inferenceContext,
aoqi@0: Warner warn) throws InferenceException {
aoqi@0: MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
aoqi@0: List saved_undet = inferenceContext.save();
aoqi@0: try {
aoqi@0: while (true) {
aoqi@0: mlistener.reset();
aoqi@0: if (!allowGraphInference) {
aoqi@0: //in legacy mode we lack of transitivity, so bound check
aoqi@0: //cannot be run in parallel with other incoprporation rounds
aoqi@0: for (Type t : inferenceContext.undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
aoqi@0: }
aoqi@0: }
aoqi@0: for (Type t : inferenceContext.undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: //bound incorporation
aoqi@0: EnumSet incorporationSteps = allowGraphInference ?
aoqi@0: incorporationStepsGraph : incorporationStepsLegacy;
aoqi@0: for (IncorporationStep is : incorporationSteps) {
aoqi@0: if (is.accepts(uv, inferenceContext)) {
aoqi@0: is.apply(uv, inferenceContext, warn);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: if (!mlistener.changed || !allowGraphInference) break;
aoqi@0: }
aoqi@0: }
aoqi@0: finally {
aoqi@0: mlistener.detach();
aoqi@0: if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {
aoqi@0: inferenceContext.rollback(saved_undet);
aoqi@0: }
aoqi@0: incorporationCache.clear();
aoqi@0: }
aoqi@0: }
aoqi@0: //where
aoqi@0: /**
aoqi@0: * This listener keeps track of changes on a group of inference variable
aoqi@0: * bounds. Note: the listener must be detached (calling corresponding
aoqi@0: * method) to make sure that the underlying inference variable is
aoqi@0: * left in a clean state.
aoqi@0: */
aoqi@0: class MultiUndetVarListener implements UndetVar.UndetVarListener {
aoqi@0:
aoqi@0: boolean changed;
aoqi@0: List undetvars;
aoqi@0:
aoqi@0: public MultiUndetVarListener(List undetvars) {
aoqi@0: this.undetvars = undetvars;
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: uv.listener = this;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: public void varChanged(UndetVar uv, Set ibs) {
aoqi@0: //avoid non-termination
aoqi@0: if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {
aoqi@0: changed = true;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: void reset() {
aoqi@0: changed = false;
aoqi@0: }
aoqi@0:
aoqi@0: void detach() {
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: uv.listener = null;
aoqi@0: }
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: /** max number of incorporation rounds */
aoqi@0: static final int MAX_INCORPORATION_STEPS = 100;
aoqi@0:
aoqi@0: /* If for two types t and s there is a least upper bound that is a
aoqi@0: * parameterized type G, then there exists a supertype of 't' of the form
aoqi@0: * G and a supertype of 's' of the form G
aoqi@0: * which will be returned by this method. If no such supertypes exists then
aoqi@0: * null is returned.
aoqi@0: *
aoqi@0: * As an example for the following input:
aoqi@0: *
aoqi@0: * t = java.util.ArrayList
aoqi@0: * s = java.util.List
aoqi@0: *
aoqi@0: * we get this ouput:
aoqi@0: *
aoqi@0: * Pair[java.util.List,java.util.List]
aoqi@0: */
aoqi@0: private Pair getParameterizedSupers(Type t, Type s) {
aoqi@0: Type lubResult = types.lub(t, s);
aoqi@0: if (lubResult == syms.errType || lubResult == syms.botType ||
aoqi@0: !lubResult.isParameterized()) {
aoqi@0: return null;
aoqi@0: }
aoqi@0: Type asSuperOfT = types.asSuper(t, lubResult.tsym);
aoqi@0: Type asSuperOfS = types.asSuper(s, lubResult.tsym);
aoqi@0: return new Pair<>(asSuperOfT, asSuperOfS);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This enumeration defines an entry point for doing inference variable
aoqi@0: * bound incorporation - it can be used to inject custom incorporation
aoqi@0: * logic into the basic bound checking routine
aoqi@0: */
aoqi@0: enum IncorporationStep {
aoqi@0: /**
aoqi@0: * Performs basic bound checking - i.e. is the instantiated type for a given
aoqi@0: * inference variable compatible with its bounds?
aoqi@0: */
aoqi@0: CHECK_BOUNDS() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
aoqi@0: infer.checkCompatibleUpperBounds(uv, inferenceContext);
aoqi@0: if (uv.inst != null) {
aoqi@0: Type inst = uv.inst;
aoqi@0: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: if (!isSubtype(inst, inferenceContext.asUndetVar(u), warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.UPPER);
aoqi@0: }
aoqi@0: }
aoqi@0: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: if (!isSubtype(inferenceContext.asUndetVar(l), inst, warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.LOWER);
aoqi@0: }
aoqi@0: }
aoqi@0: for (Type e : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: if (!isSameType(inst, inferenceContext.asUndetVar(e), infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.EQ);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: //applies to all undetvars
aoqi@0: return true;
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Check consistency of equality constraints. This is a slightly more aggressive
aoqi@0: * inference routine that is designed as to maximize compatibility with JDK 7.
aoqi@0: * Note: this is not used in graph mode.
aoqi@0: */
aoqi@0: EQ_CHECK_LEGACY() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: Type eq = null;
aoqi@0: for (Type e : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: Assert.check(!inferenceContext.free(e));
aoqi@0: if (eq != null && !isSameType(e, eq, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.EQ);
aoqi@0: }
aoqi@0: eq = e;
aoqi@0: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: Assert.check(!inferenceContext.free(l));
aoqi@0: if (!isSubtype(l, e, warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
aoqi@0: }
aoqi@0: }
aoqi@0: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: if (inferenceContext.free(u)) continue;
aoqi@0: if (!isSubtype(e, u, warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Check consistency of equality constraints.
aoqi@0: */
aoqi@0: EQ_CHECK() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type e : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: if (e.containsAny(inferenceContext.inferenceVars())) continue;
aoqi@0: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: if (!isSubtype(e, inferenceContext.asUndetVar(u), warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
aoqi@0: }
aoqi@0: }
aoqi@0: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: if (!isSubtype(inferenceContext.asUndetVar(l), e, warn, infer)) {
aoqi@0: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
aoqi@0: * perform {@code S <: T} (which could lead to new bounds).
aoqi@0: */
aoqi@0: CROSS_UPPER_LOWER() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn , infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
aoqi@0: * perform {@code S <: T} (which could lead to new bounds).
aoqi@0: */
aoqi@0: CROSS_UPPER_EQ() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
aoqi@0: * perform {@code S <: T} (which could lead to new bounds).
aoqi@0: */
aoqi@0: CROSS_EQ_LOWER() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha <: P} and
aoqi@0: * {@code alpha <: P} where P is a parameterized type,
aoqi@0: * perform {@code T = S} (which could lead to new bounds).
aoqi@0: */
aoqi@0: CROSS_UPPER_UPPER() {
aoqi@0: @Override
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: List boundList = uv.getBounds(InferenceBound.UPPER);
aoqi@0: List boundListTail = boundList.tail;
aoqi@0: while (boundList.nonEmpty()) {
aoqi@0: List tmpTail = boundListTail;
aoqi@0: while (tmpTail.nonEmpty()) {
aoqi@0: Type b1 = boundList.head;
aoqi@0: Type b2 = tmpTail.head;
vromero@2601: /* This wildcard check is temporary workaround. This code may need to be
vromero@2601: * revisited once spec bug JDK-7034922 is fixed.
vromero@2601: */
vromero@2601: if (b1 != b2 && !b1.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) {
aoqi@0: Pair commonSupers = infer.getParameterizedSupers(b1, b2);
aoqi@0: if (commonSupers != null) {
aoqi@0: List allParamsSuperBound1 = commonSupers.fst.allparams();
aoqi@0: List allParamsSuperBound2 = commonSupers.snd.allparams();
aoqi@0: while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) {
aoqi@0: //traverse the list of all params comparing them
aoqi@0: if (!allParamsSuperBound1.head.hasTag(WILDCARD) &&
aoqi@0: !allParamsSuperBound2.head.hasTag(WILDCARD)) {
aoqi@0: isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head),
aoqi@0: inferenceContext.asUndetVar(allParamsSuperBound2.head), infer);
aoqi@0: }
aoqi@0: allParamsSuperBound1 = allParamsSuperBound1.tail;
aoqi@0: allParamsSuperBound2 = allParamsSuperBound2.tail;
aoqi@0: }
aoqi@0: Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty());
aoqi@0: }
aoqi@0: }
aoqi@0: tmpTail = tmpTail.tail;
aoqi@0: }
aoqi@0: boundList = boundList.tail;
aoqi@0: boundListTail = boundList.tail;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return !uv.isCaptured() &&
aoqi@0: uv.getBounds(InferenceBound.UPPER).nonEmpty();
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha == S} and {@code alpha == T}
aoqi@0: * perform {@code S == T} (which could lead to new bounds).
aoqi@0: */
aoqi@0: CROSS_EQ_EQ() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: if (b1 != b2) {
aoqi@0: isSameType(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha <: beta} propagate lower bounds
aoqi@0: * from alpha to beta; also propagate upper bounds from beta to alpha.
aoqi@0: */
aoqi@0: PROP_UPPER() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: if (inferenceContext.inferenceVars().contains(b)) {
aoqi@0: UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
aoqi@0: if (uv2.isCaptured()) continue;
aoqi@0: //alpha <: beta
aoqi@0: //0. set beta :> alpha
aoqi@0: addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);
aoqi@0: //1. copy alpha's lower to beta's
aoqi@0: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer);
aoqi@0: }
aoqi@0: //2. copy beta's upper to alpha's
aoqi@0: for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
aoqi@0: addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha :> beta} propagate lower bounds
aoqi@0: * from beta to alpha; also propagate upper bounds from alpha to beta.
aoqi@0: */
aoqi@0: PROP_LOWER() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b : uv.getBounds(InferenceBound.LOWER)) {
aoqi@0: if (inferenceContext.inferenceVars().contains(b)) {
aoqi@0: UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
aoqi@0: if (uv2.isCaptured()) continue;
aoqi@0: //alpha :> beta
aoqi@0: //0. set beta <: alpha
aoqi@0: addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);
aoqi@0: //1. copy alpha's upper to beta's
aoqi@0: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
aoqi@0: addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer);
aoqi@0: }
aoqi@0: //2. copy beta's lower to alpha's
aoqi@0: for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
aoqi@0: addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Given a bound set containing {@code alpha == beta} propagate lower/upper
aoqi@0: * bounds from alpha to beta and back.
aoqi@0: */
aoqi@0: PROP_EQ() {
aoqi@0: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type b : uv.getBounds(InferenceBound.EQ)) {
aoqi@0: if (inferenceContext.inferenceVars().contains(b)) {
aoqi@0: UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
aoqi@0: if (uv2.isCaptured()) continue;
aoqi@0: //alpha == beta
aoqi@0: //0. set beta == alpha
aoqi@0: addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);
aoqi@0: //1. copy all alpha's bounds to beta's
aoqi@0: for (InferenceBound ib : InferenceBound.values()) {
aoqi@0: for (Type b2 : uv.getBounds(ib)) {
aoqi@0: if (b2 != uv2) {
aoqi@0: addBound(ib, uv2, inferenceContext.asInstType(b2), infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: //2. copy all beta's bounds to alpha's
aoqi@0: for (InferenceBound ib : InferenceBound.values()) {
aoqi@0: for (Type b2 : uv2.getBounds(ib)) {
aoqi@0: if (b2 != uv) {
aoqi@0: addBound(ib, uv, inferenceContext.asInstType(b2), infer);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
aoqi@0:
aoqi@0: boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return !uv.isCaptured();
aoqi@0: }
aoqi@0:
aoqi@0: boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
aoqi@0: return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
aoqi@0: }
aoqi@0:
aoqi@0: boolean isSameType(Type s, Type t, Infer infer) {
aoqi@0: return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
aoqi@0: }
aoqi@0:
aoqi@0: void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
aoqi@0: doIncorporationOp(opFor(ib), uv, b, null, infer);
aoqi@0: }
aoqi@0:
aoqi@0: IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
aoqi@0: switch (boundKind) {
aoqi@0: case EQ:
aoqi@0: return IncorporationBinaryOpKind.ADD_EQ_BOUND;
aoqi@0: case LOWER:
aoqi@0: return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
aoqi@0: case UPPER:
aoqi@0: return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
aoqi@0: default:
aoqi@0: Assert.error("Can't get here!");
aoqi@0: return null;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
aoqi@0: IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
aoqi@0: Boolean res = infer.incorporationCache.get(newOp);
aoqi@0: if (res == null) {
aoqi@0: infer.incorporationCache.put(newOp, res = newOp.apply(warn));
aoqi@0: }
aoqi@0: return res;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /** incorporation steps to be executed when running in legacy mode */
aoqi@0: EnumSet incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
aoqi@0:
aoqi@0: /** incorporation steps to be executed when running in graph mode */
aoqi@0: EnumSet incorporationStepsGraph =
aoqi@0: EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
aoqi@0:
aoqi@0: /**
aoqi@0: * Three kinds of basic operation are supported as part of an incorporation step:
aoqi@0: * (i) subtype check, (ii) same type check and (iii) bound addition (either
aoqi@0: * upper/lower/eq bound).
aoqi@0: */
aoqi@0: enum IncorporationBinaryOpKind {
aoqi@0: IS_SUBTYPE() {
aoqi@0: @Override
aoqi@0: boolean apply(Type op1, Type op2, Warner warn, Types types) {
aoqi@0: return types.isSubtypeUnchecked(op1, op2, warn);
aoqi@0: }
aoqi@0: },
aoqi@0: IS_SAME_TYPE() {
aoqi@0: @Override
aoqi@0: boolean apply(Type op1, Type op2, Warner warn, Types types) {
aoqi@0: return types.isSameType(op1, op2);
aoqi@0: }
aoqi@0: },
aoqi@0: ADD_UPPER_BOUND() {
aoqi@0: @Override
aoqi@0: boolean apply(Type op1, Type op2, Warner warn, Types types) {
aoqi@0: UndetVar uv = (UndetVar)op1;
aoqi@0: uv.addBound(InferenceBound.UPPER, op2, types);
aoqi@0: return true;
aoqi@0: }
aoqi@0: },
aoqi@0: ADD_LOWER_BOUND() {
aoqi@0: @Override
aoqi@0: boolean apply(Type op1, Type op2, Warner warn, Types types) {
aoqi@0: UndetVar uv = (UndetVar)op1;
aoqi@0: uv.addBound(InferenceBound.LOWER, op2, types);
aoqi@0: return true;
aoqi@0: }
aoqi@0: },
aoqi@0: ADD_EQ_BOUND() {
aoqi@0: @Override
aoqi@0: boolean apply(Type op1, Type op2, Warner warn, Types types) {
aoqi@0: UndetVar uv = (UndetVar)op1;
aoqi@0: uv.addBound(InferenceBound.EQ, op2, types);
aoqi@0: return true;
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This class encapsulates a basic incorporation operation; incorporation
aoqi@0: * operations takes two type operands and a kind. Each operation performed
aoqi@0: * during an incorporation round is stored in a cache, so that operations
aoqi@0: * are not executed unnecessarily (which would potentially lead to adding
aoqi@0: * same bounds over and over).
aoqi@0: */
aoqi@0: class IncorporationBinaryOp {
aoqi@0:
aoqi@0: IncorporationBinaryOpKind opKind;
aoqi@0: Type op1;
aoqi@0: Type op2;
aoqi@0:
aoqi@0: IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
aoqi@0: this.opKind = opKind;
aoqi@0: this.op1 = op1;
aoqi@0: this.op2 = op2;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public boolean equals(Object o) {
aoqi@0: if (!(o instanceof IncorporationBinaryOp)) {
aoqi@0: return false;
aoqi@0: } else {
aoqi@0: IncorporationBinaryOp that = (IncorporationBinaryOp)o;
aoqi@0: return opKind == that.opKind &&
aoqi@0: types.isSameType(op1, that.op1, true) &&
aoqi@0: types.isSameType(op2, that.op2, true);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public int hashCode() {
aoqi@0: int result = opKind.hashCode();
aoqi@0: result *= 127;
aoqi@0: result += types.hashCode(op1);
aoqi@0: result *= 127;
aoqi@0: result += types.hashCode(op2);
aoqi@0: return result;
aoqi@0: }
aoqi@0:
aoqi@0: boolean apply(Warner warn) {
aoqi@0: return opKind.apply(op1, op2, warn, types);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /** an incorporation cache keeps track of all executed incorporation-related operations */
aoqi@0: Map incorporationCache =
aoqi@0: new HashMap();
aoqi@0:
aoqi@0: /**
aoqi@0: * Make sure that the upper bounds we got so far lead to a solvable inference
aoqi@0: * variable by making sure that a glb exists.
aoqi@0: */
aoqi@0: void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: List hibounds =
aoqi@0: Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
aoqi@0: Type hb = null;
aoqi@0: if (hibounds.isEmpty())
aoqi@0: hb = syms.objectType;
aoqi@0: else if (hibounds.tail.isEmpty())
aoqi@0: hb = hibounds.head;
aoqi@0: else
aoqi@0: hb = types.glb(hibounds);
aoqi@0: if (hb == null || hb.isErroneous())
aoqi@0: reportBoundError(uv, BoundErrorKind.BAD_UPPER);
aoqi@0: }
aoqi@0: //where
aoqi@0: protected static class BoundFilter implements Filter {
aoqi@0:
aoqi@0: InferenceContext inferenceContext;
aoqi@0:
aoqi@0: public BoundFilter(InferenceContext inferenceContext) {
aoqi@0: this.inferenceContext = inferenceContext;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public boolean accepts(Type t) {
aoqi@0: return !t.isErroneous() && !inferenceContext.free(t) &&
aoqi@0: !t.hasTag(BOT);
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: /**
aoqi@0: * This enumeration defines all possible bound-checking related errors.
aoqi@0: */
aoqi@0: enum BoundErrorKind {
aoqi@0: /**
aoqi@0: * The (uninstantiated) inference variable has incompatible upper bounds.
aoqi@0: */
aoqi@0: BAD_UPPER() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("incompatible.upper.bounds", uv.qtype,
aoqi@0: uv.getBounds(InferenceBound.UPPER));
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * An equality constraint is not compatible with an upper bound.
aoqi@0: */
aoqi@0: BAD_EQ_UPPER() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
aoqi@0: uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * An equality constraint is not compatible with a lower bound.
aoqi@0: */
aoqi@0: BAD_EQ_LOWER() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
aoqi@0: uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Instantiated inference variable is not compatible with an upper bound.
aoqi@0: */
aoqi@0: UPPER() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
aoqi@0: uv.getBounds(InferenceBound.UPPER));
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Instantiated inference variable is not compatible with a lower bound.
aoqi@0: */
aoqi@0: LOWER() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
aoqi@0: uv.getBounds(InferenceBound.LOWER));
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Instantiated inference variable is not compatible with an equality constraint.
aoqi@0: */
aoqi@0: EQ() {
aoqi@0: @Override
aoqi@0: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
aoqi@0: return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
aoqi@0: uv.getBounds(InferenceBound.EQ));
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Report a bound-checking error of given kind
aoqi@0: */
aoqi@0: void reportBoundError(UndetVar uv, BoundErrorKind bk) {
aoqi@0: throw bk.setMessage(inferenceException, uv);
aoqi@0: }
aoqi@0: //
aoqi@0:
aoqi@0: //
aoqi@0: /**
aoqi@0: * Graph inference strategy - act as an input to the inference solver; a strategy is
aoqi@0: * composed of two ingredients: (i) find a node to solve in the inference graph,
aoqi@0: * and (ii) tell th engine when we are done fixing inference variables
aoqi@0: */
aoqi@0: interface GraphStrategy {
aoqi@0:
aoqi@0: /**
aoqi@0: * A NodeNotFoundException is thrown whenever an inference strategy fails
aoqi@0: * to pick the next node to solve in the inference graph.
aoqi@0: */
aoqi@0: public static class NodeNotFoundException extends RuntimeException {
aoqi@0: private static final long serialVersionUID = 0;
aoqi@0:
aoqi@0: InferenceGraph graph;
aoqi@0:
aoqi@0: public NodeNotFoundException(InferenceGraph graph) {
aoqi@0: this.graph = graph;
aoqi@0: }
aoqi@0: }
aoqi@0: /**
aoqi@0: * Pick the next node (leaf) to solve in the graph
aoqi@0: */
aoqi@0: Node pickNode(InferenceGraph g) throws NodeNotFoundException;
aoqi@0: /**
aoqi@0: * Is this the last step?
aoqi@0: */
aoqi@0: boolean done();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Simple solver strategy class that locates all leaves inside a graph
aoqi@0: * and picks the first leaf as the next node to solve
aoqi@0: */
aoqi@0: abstract class LeafSolver implements GraphStrategy {
aoqi@0: public Node pickNode(InferenceGraph g) {
aoqi@0: if (g.nodes.isEmpty()) {
aoqi@0: //should not happen
aoqi@0: throw new NodeNotFoundException(g);
aoqi@0: };
aoqi@0: return g.nodes.get(0);
aoqi@0: }
aoqi@0:
aoqi@0: boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
aoqi@0: return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
aoqi@0: }
aoqi@0:
aoqi@0: boolean isSameType(Type s, Type t, Infer infer) {
aoqi@0: return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
aoqi@0: }
aoqi@0:
aoqi@0: void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
aoqi@0: doIncorporationOp(opFor(ib), uv, b, null, infer);
aoqi@0: }
aoqi@0:
aoqi@0: IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
aoqi@0: switch (boundKind) {
aoqi@0: case EQ:
aoqi@0: return IncorporationBinaryOpKind.ADD_EQ_BOUND;
aoqi@0: case LOWER:
aoqi@0: return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
aoqi@0: case UPPER:
aoqi@0: return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
aoqi@0: default:
aoqi@0: Assert.error("Can't get here!");
aoqi@0: return null;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
aoqi@0: IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
aoqi@0: Boolean res = infer.incorporationCache.get(newOp);
aoqi@0: if (res == null) {
aoqi@0: infer.incorporationCache.put(newOp, res = newOp.apply(warn));
aoqi@0: }
aoqi@0: return res;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This solver uses an heuristic to pick the best leaf - the heuristic
aoqi@0: * tries to select the node that has maximal probability to contain one
aoqi@0: * or more inference variables in a given list
aoqi@0: */
aoqi@0: abstract class BestLeafSolver extends LeafSolver {
aoqi@0:
aoqi@0: /** list of ivars of which at least one must be solved */
aoqi@0: List varsToSolve;
aoqi@0:
aoqi@0: BestLeafSolver(List varsToSolve) {
aoqi@0: this.varsToSolve = varsToSolve;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Computes a path that goes from a given node to the leafs in the graph.
aoqi@0: * Typically this will start from a node containing a variable in
aoqi@0: * {@code varsToSolve}. For any given path, the cost is computed as the total
aoqi@0: * number of type-variables that should be eagerly instantiated across that path.
aoqi@0: */
aoqi@0: Pair, Integer> computeTreeToLeafs(Node n) {
aoqi@0: Pair, Integer> cachedPath = treeCache.get(n);
aoqi@0: if (cachedPath == null) {
aoqi@0: //cache miss
aoqi@0: if (n.isLeaf()) {
aoqi@0: //if leaf, stop
aoqi@0: cachedPath = new Pair, Integer>(List.of(n), n.data.length());
aoqi@0: } else {
aoqi@0: //if non-leaf, proceed recursively
aoqi@0: Pair, Integer> path = new Pair, Integer>(List.of(n), n.data.length());
aoqi@0: for (Node n2 : n.getAllDependencies()) {
aoqi@0: if (n2 == n) continue;
aoqi@0: Pair, Integer> subpath = computeTreeToLeafs(n2);
aoqi@0: path = new Pair, Integer>(
aoqi@0: path.fst.prependList(subpath.fst),
aoqi@0: path.snd + subpath.snd);
aoqi@0: }
aoqi@0: cachedPath = path;
aoqi@0: }
aoqi@0: //save results in cache
aoqi@0: treeCache.put(n, cachedPath);
aoqi@0: }
aoqi@0: return cachedPath;
aoqi@0: }
aoqi@0:
aoqi@0: /** cache used to avoid redundant computation of tree costs */
aoqi@0: final Map, Integer>> treeCache =
aoqi@0: new HashMap, Integer>>();
aoqi@0:
aoqi@0: /** constant value used to mark non-existent paths */
aoqi@0: final Pair, Integer> noPath =
aoqi@0: new Pair, Integer>(null, Integer.MAX_VALUE);
aoqi@0:
aoqi@0: /**
aoqi@0: * Pick the leaf that minimize cost
aoqi@0: */
aoqi@0: @Override
aoqi@0: public Node pickNode(final InferenceGraph g) {
aoqi@0: treeCache.clear(); //graph changes at every step - cache must be cleared
aoqi@0: Pair, Integer> bestPath = noPath;
aoqi@0: for (Node n : g.nodes) {
aoqi@0: if (!Collections.disjoint(n.data, varsToSolve)) {
aoqi@0: Pair, Integer> path = computeTreeToLeafs(n);
aoqi@0: //discard all paths containing at least a node in the
aoqi@0: //closure computed above
aoqi@0: if (path.snd < bestPath.snd) {
aoqi@0: bestPath = path;
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: if (bestPath == noPath) {
aoqi@0: //no path leads there
aoqi@0: throw new NodeNotFoundException(g);
aoqi@0: }
aoqi@0: return bestPath.fst.head;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * The inference process can be thought of as a sequence of steps. Each step
aoqi@0: * instantiates an inference variable using a subset of the inference variable
aoqi@0: * bounds, if certain condition are met. Decisions such as the sequence in which
aoqi@0: * steps are applied, or which steps are to be applied are left to the inference engine.
aoqi@0: */
aoqi@0: enum InferenceStep {
aoqi@0:
aoqi@0: /**
aoqi@0: * Instantiate an inference variables using one of its (ground) equality
aoqi@0: * constraints
aoqi@0: */
aoqi@0: EQ(InferenceBound.EQ) {
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return filterBounds(uv, inferenceContext).head;
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Instantiate an inference variables using its (ground) lower bounds. Such
aoqi@0: * bounds are merged together using lub().
aoqi@0: */
aoqi@0: LOWER(InferenceBound.LOWER) {
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: List lobounds = filterBounds(uv, inferenceContext);
aoqi@0: //note: lobounds should have at least one element
aoqi@0: Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds);
aoqi@0: if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
aoqi@0: throw infer.inferenceException
aoqi@0: .setMessage("no.unique.minimal.instance.exists",
aoqi@0: uv.qtype, lobounds);
aoqi@0: } else {
aoqi@0: return owntype;
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Infer uninstantiated/unbound inference variables occurring in 'throws'
aoqi@0: * clause as RuntimeException
aoqi@0: */
aoqi@0: THROWS(InferenceBound.UPPER) {
aoqi@0: @Override
aoqi@0: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
aoqi@0: if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
aoqi@0: //not a throws undet var
aoqi@0: return false;
aoqi@0: }
aoqi@0: if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
aoqi@0: .diff(t.getDeclaredBounds()).nonEmpty()) {
aoqi@0: //not an unbounded undet var
aoqi@0: return false;
aoqi@0: }
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: for (Type db : t.getDeclaredBounds()) {
aoqi@0: if (t.isInterface()) continue;
aoqi@0: if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
aoqi@0: //declared bound is a supertype of RuntimeException
aoqi@0: return true;
aoqi@0: }
aoqi@0: }
aoqi@0: //declared bound is more specific then RuntimeException - give up
aoqi@0: return false;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return inferenceContext.infer().syms.runtimeExceptionType;
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Instantiate an inference variables using its (ground) upper bounds. Such
aoqi@0: * bounds are merged together using glb().
aoqi@0: */
aoqi@0: UPPER(InferenceBound.UPPER) {
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: List hibounds = filterBounds(uv, inferenceContext);
aoqi@0: //note: hibounds should have at least one element
aoqi@0: Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds);
aoqi@0: if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
aoqi@0: throw infer.inferenceException
aoqi@0: .setMessage("no.unique.maximal.instance.exists",
aoqi@0: uv.qtype, hibounds);
aoqi@0: } else {
aoqi@0: return owntype;
aoqi@0: }
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Like the former; the only difference is that this step can only be applied
aoqi@0: * if all upper bounds are ground.
aoqi@0: */
aoqi@0: UPPER_LEGACY(InferenceBound.UPPER) {
aoqi@0: @Override
aoqi@0: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
aoqi@0: return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return UPPER.solve(uv, inferenceContext);
aoqi@0: }
aoqi@0: },
aoqi@0: /**
aoqi@0: * Like the former; the only difference is that this step can only be applied
aoqi@0: * if all upper/lower bounds are ground.
aoqi@0: */
aoqi@0: CAPTURED(InferenceBound.UPPER) {
aoqi@0: @Override
aoqi@0: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
aoqi@0: return t.isCaptured() &&
aoqi@0: !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: Type solve(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: Infer infer = inferenceContext.infer();
aoqi@0: Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
aoqi@0: UPPER.solve(uv, inferenceContext) :
aoqi@0: infer.syms.objectType;
aoqi@0: Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
aoqi@0: LOWER.solve(uv, inferenceContext) :
aoqi@0: infer.syms.botType;
aoqi@0: CapturedType prevCaptured = (CapturedType)uv.qtype;
aoqi@0: return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: final InferenceBound ib;
aoqi@0:
aoqi@0: InferenceStep(InferenceBound ib) {
aoqi@0: this.ib = ib;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Find an instantiated type for a given inference variable within
aoqi@0: * a given inference context
aoqi@0: */
aoqi@0: abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
aoqi@0:
aoqi@0: /**
aoqi@0: * Can the inference variable be instantiated using this step?
aoqi@0: */
aoqi@0: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
aoqi@0: return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
aoqi@0: */
aoqi@0: List filterBounds(UndetVar uv, InferenceContext inferenceContext) {
aoqi@0: return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This enumeration defines the sequence of steps to be applied when the
aoqi@0: * solver works in legacy mode. The steps in this enumeration reflect
aoqi@0: * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
aoqi@0: */
aoqi@0: enum LegacyInferenceSteps {
aoqi@0:
aoqi@0: EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
aoqi@0: EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
aoqi@0:
aoqi@0: final EnumSet steps;
aoqi@0:
aoqi@0: LegacyInferenceSteps(EnumSet steps) {
aoqi@0: this.steps = steps;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This enumeration defines the sequence of steps to be applied when the
aoqi@0: * graph solver is used. This order is defined so as to maximize compatibility
aoqi@0: * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
aoqi@0: */
aoqi@0: enum GraphInferenceSteps {
aoqi@0:
aoqi@0: EQ(EnumSet.of(InferenceStep.EQ)),
aoqi@0: EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
aoqi@0: EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
aoqi@0:
aoqi@0: final EnumSet steps;
aoqi@0:
aoqi@0: GraphInferenceSteps(EnumSet steps) {
aoqi@0: this.steps = steps;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * There are two kinds of dependencies between inference variables. The basic
aoqi@0: * kind of dependency (or bound dependency) arises when a variable mention
aoqi@0: * another variable in one of its bounds. There's also a more subtle kind
aoqi@0: * of dependency that arises when a variable 'might' lead to better constraints
aoqi@0: * on another variable (this is typically the case with variables holding up
aoqi@0: * stuck expressions).
aoqi@0: */
aoqi@0: enum DependencyKind implements GraphUtils.DependencyKind {
aoqi@0:
aoqi@0: /** bound dependency */
aoqi@0: BOUND("dotted"),
aoqi@0: /** stuck dependency */
aoqi@0: STUCK("dashed");
aoqi@0:
aoqi@0: final String dotSyle;
aoqi@0:
aoqi@0: private DependencyKind(String dotSyle) {
aoqi@0: this.dotSyle = dotSyle;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public String getDotStyle() {
aoqi@0: return dotSyle;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * This is the graph inference solver - the solver organizes all inference variables in
aoqi@0: * a given inference context by bound dependencies - in the general case, such dependencies
aoqi@0: * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
aoqi@0: * an acyclic graph, where all cyclic variables are bundled together. An inference
aoqi@0: * step corresponds to solving a node in the acyclic graph - this is done by
aoqi@0: * relying on a given strategy (see GraphStrategy).
aoqi@0: */
aoqi@0: class GraphSolver {
aoqi@0:
aoqi@0: InferenceContext inferenceContext;
aoqi@0: Map> stuckDeps;
aoqi@0: Warner warn;
aoqi@0:
aoqi@0: GraphSolver(InferenceContext inferenceContext, Map> stuckDeps, Warner warn) {
aoqi@0: this.inferenceContext = inferenceContext;
aoqi@0: this.stuckDeps = stuckDeps;
aoqi@0: this.warn = warn;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Solve variables in a given inference context. The amount of variables
aoqi@0: * to be solved, and the way in which the underlying acyclic graph is explored
aoqi@0: * depends on the selected solver strategy.
aoqi@0: */
aoqi@0: void solve(GraphStrategy sstrategy) {
aoqi@0: checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
aoqi@0: InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps);
aoqi@0: while (!sstrategy.done()) {
aoqi@0: InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
aoqi@0: List varsToSolve = List.from(nodeToSolve.data);
aoqi@0: List saved_undet = inferenceContext.save();
aoqi@0: try {
aoqi@0: //repeat until all variables are solved
aoqi@0: outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
aoqi@0: //for each inference phase
aoqi@0: for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
aoqi@0: if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
aoqi@0: checkWithinBounds(inferenceContext, warn);
aoqi@0: continue outer;
aoqi@0: }
aoqi@0: }
aoqi@0: //no progress
aoqi@0: throw inferenceException.setMessage();
aoqi@0: }
aoqi@0: }
aoqi@0: catch (InferenceException ex) {
aoqi@0: //did we fail because of interdependent ivars?
aoqi@0: inferenceContext.rollback(saved_undet);
aoqi@0: instantiateAsUninferredVars(varsToSolve, inferenceContext);
aoqi@0: checkWithinBounds(inferenceContext, warn);
aoqi@0: }
aoqi@0: inferenceGraph.deleteNode(nodeToSolve);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * The dependencies between the inference variables that need to be solved
aoqi@0: * form a (possibly cyclic) graph. This class reduces the original dependency graph
aoqi@0: * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
aoqi@0: */
aoqi@0: class InferenceGraph {
aoqi@0:
aoqi@0: /**
aoqi@0: * This class represents a node in the graph. Each node corresponds
aoqi@0: * to an inference variable and has edges (dependencies) on other
aoqi@0: * nodes. The node defines an entry point that can be used to receive
aoqi@0: * updates on the structure of the graph this node belongs to (used to
aoqi@0: * keep dependencies in sync).
aoqi@0: */
aoqi@0: class Node extends GraphUtils.TarjanNode> {
aoqi@0:
aoqi@0: /** map listing all dependencies (grouped by kind) */
aoqi@0: EnumMap> deps;
aoqi@0:
aoqi@0: Node(Type ivar) {
aoqi@0: super(ListBuffer.of(ivar));
aoqi@0: this.deps = new EnumMap>(DependencyKind.class);
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
aoqi@0: return DependencyKind.values();
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public String getDependencyName(GraphUtils.Node> to, GraphUtils.DependencyKind dk) {
aoqi@0: if (dk == DependencyKind.STUCK) return "";
aoqi@0: else {
aoqi@0: StringBuilder buf = new StringBuilder();
aoqi@0: String sep = "";
aoqi@0: for (Type from : data) {
aoqi@0: UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from);
aoqi@0: for (Type bound : uv.getBounds(InferenceBound.values())) {
aoqi@0: if (bound.containsAny(List.from(to.data))) {
aoqi@0: buf.append(sep);
aoqi@0: buf.append(bound);
aoqi@0: sep = ",";
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: return buf.toString();
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public Iterable extends Node> getAllDependencies() {
aoqi@0: return getDependencies(DependencyKind.values());
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public Iterable extends TarjanNode>> getDependenciesByKind(GraphUtils.DependencyKind dk) {
aoqi@0: return getDependencies((DependencyKind)dk);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Retrieves all dependencies with given kind(s).
aoqi@0: */
aoqi@0: protected Set getDependencies(DependencyKind... depKinds) {
aoqi@0: Set buf = new LinkedHashSet();
aoqi@0: for (DependencyKind dk : depKinds) {
aoqi@0: Set depsByKind = deps.get(dk);
aoqi@0: if (depsByKind != null) {
aoqi@0: buf.addAll(depsByKind);
aoqi@0: }
aoqi@0: }
aoqi@0: return buf;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Adds dependency with given kind.
aoqi@0: */
aoqi@0: protected void addDependency(DependencyKind dk, Node depToAdd) {
aoqi@0: Set depsByKind = deps.get(dk);
aoqi@0: if (depsByKind == null) {
aoqi@0: depsByKind = new LinkedHashSet();
aoqi@0: deps.put(dk, depsByKind);
aoqi@0: }
aoqi@0: depsByKind.add(depToAdd);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Add multiple dependencies of same given kind.
aoqi@0: */
aoqi@0: protected void addDependencies(DependencyKind dk, Set depsToAdd) {
aoqi@0: for (Node n : depsToAdd) {
aoqi@0: addDependency(dk, n);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Remove a dependency, regardless of its kind.
aoqi@0: */
aoqi@0: protected Set removeDependency(Node n) {
aoqi@0: Set removedKinds = new HashSet<>();
aoqi@0: for (DependencyKind dk : DependencyKind.values()) {
aoqi@0: Set depsByKind = deps.get(dk);
aoqi@0: if (depsByKind == null) continue;
aoqi@0: if (depsByKind.remove(n)) {
aoqi@0: removedKinds.add(dk);
aoqi@0: }
aoqi@0: }
aoqi@0: return removedKinds;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Compute closure of a give node, by recursively walking
aoqi@0: * through all its dependencies (of given kinds)
aoqi@0: */
aoqi@0: protected Set closure(DependencyKind... depKinds) {
aoqi@0: boolean progress = true;
aoqi@0: Set closure = new HashSet();
aoqi@0: closure.add(this);
aoqi@0: while (progress) {
aoqi@0: progress = false;
aoqi@0: for (Node n1 : new HashSet(closure)) {
aoqi@0: progress = closure.addAll(n1.getDependencies(depKinds));
aoqi@0: }
aoqi@0: }
aoqi@0: return closure;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Is this node a leaf? This means either the node has no dependencies,
aoqi@0: * or it just has self-dependencies.
aoqi@0: */
aoqi@0: protected boolean isLeaf() {
aoqi@0: //no deps, or only one self dep
aoqi@0: Set allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK);
aoqi@0: if (allDeps.isEmpty()) return true;
aoqi@0: for (Node n : allDeps) {
aoqi@0: if (n != this) {
aoqi@0: return false;
aoqi@0: }
aoqi@0: }
aoqi@0: return true;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Merge this node with another node, acquiring its dependencies.
aoqi@0: * This routine is used to merge all cyclic node together and
aoqi@0: * form an acyclic graph.
aoqi@0: */
aoqi@0: protected void mergeWith(List extends Node> nodes) {
aoqi@0: for (Node n : nodes) {
aoqi@0: Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
aoqi@0: data.appendList(n.data);
aoqi@0: for (DependencyKind dk : DependencyKind.values()) {
aoqi@0: addDependencies(dk, n.getDependencies(dk));
aoqi@0: }
aoqi@0: }
aoqi@0: //update deps
aoqi@0: EnumMap> deps2 = new EnumMap>(DependencyKind.class);
aoqi@0: for (DependencyKind dk : DependencyKind.values()) {
aoqi@0: for (Node d : getDependencies(dk)) {
aoqi@0: Set depsByKind = deps2.get(dk);
aoqi@0: if (depsByKind == null) {
aoqi@0: depsByKind = new LinkedHashSet();
aoqi@0: deps2.put(dk, depsByKind);
aoqi@0: }
aoqi@0: if (data.contains(d.data.first())) {
aoqi@0: depsByKind.add(this);
aoqi@0: } else {
aoqi@0: depsByKind.add(d);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: deps = deps2;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Notify all nodes that something has changed in the graph
aoqi@0: * topology.
aoqi@0: */
aoqi@0: private void graphChanged(Node from, Node to) {
aoqi@0: for (DependencyKind dk : removeDependency(from)) {
aoqi@0: if (to != null) {
aoqi@0: addDependency(dk, to);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /** the nodes in the inference graph */
aoqi@0: ArrayList nodes;
aoqi@0:
aoqi@0: InferenceGraph(Map> optDeps) {
aoqi@0: initNodes(optDeps);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Basic lookup helper for retrieving a graph node given an inference
aoqi@0: * variable type.
aoqi@0: */
aoqi@0: public Node findNode(Type t) {
aoqi@0: for (Node n : nodes) {
aoqi@0: if (n.data.contains(t)) {
aoqi@0: return n;
aoqi@0: }
aoqi@0: }
aoqi@0: return null;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Delete a node from the graph. This update the underlying structure
aoqi@0: * of the graph (including dependencies) via listeners updates.
aoqi@0: */
aoqi@0: public void deleteNode(Node n) {
aoqi@0: Assert.check(nodes.contains(n));
aoqi@0: nodes.remove(n);
aoqi@0: notifyUpdate(n, null);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Notify all nodes of a change in the graph. If the target node is
aoqi@0: * {@code null} the source node is assumed to be removed.
aoqi@0: */
aoqi@0: void notifyUpdate(Node from, Node to) {
aoqi@0: for (Node n : nodes) {
aoqi@0: n.graphChanged(from, to);
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Create the graph nodes. First a simple node is created for every inference
aoqi@0: * variables to be solved. Then Tarjan is used to found all connected components
aoqi@0: * in the graph. For each component containing more than one node, a super node is
aoqi@0: * created, effectively replacing the original cyclic nodes.
aoqi@0: */
aoqi@0: void initNodes(Map> stuckDeps) {
aoqi@0: //add nodes
aoqi@0: nodes = new ArrayList();
aoqi@0: for (Type t : inferenceContext.restvars()) {
aoqi@0: nodes.add(new Node(t));
aoqi@0: }
aoqi@0: //add dependencies
aoqi@0: for (Node n_i : nodes) {
aoqi@0: Type i = n_i.data.first();
aoqi@0: Set optDepsByNode = stuckDeps.get(i);
aoqi@0: for (Node n_j : nodes) {
aoqi@0: Type j = n_j.data.first();
aoqi@0: UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i);
aoqi@0: if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
aoqi@0: //update i's bound dependencies
aoqi@0: n_i.addDependency(DependencyKind.BOUND, n_j);
aoqi@0: }
aoqi@0: if (optDepsByNode != null && optDepsByNode.contains(j)) {
aoqi@0: //update i's stuck dependencies
aoqi@0: n_i.addDependency(DependencyKind.STUCK, n_j);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: //merge cyclic nodes
aoqi@0: ArrayList acyclicNodes = new ArrayList();
aoqi@0: for (List extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
aoqi@0: if (conSubGraph.length() > 1) {
aoqi@0: Node root = conSubGraph.head;
aoqi@0: root.mergeWith(conSubGraph.tail);
aoqi@0: for (Node n : conSubGraph) {
aoqi@0: notifyUpdate(n, root);
aoqi@0: }
aoqi@0: }
aoqi@0: acyclicNodes.add(conSubGraph.head);
aoqi@0: }
aoqi@0: nodes = acyclicNodes;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Debugging: dot representation of this graph
aoqi@0: */
aoqi@0: String toDot() {
aoqi@0: StringBuilder buf = new StringBuilder();
aoqi@0: for (Type t : inferenceContext.undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
aoqi@0: uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
aoqi@0: uv.getBounds(InferenceBound.EQ)));
aoqi@0: }
aoqi@0: return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: //
aoqi@0:
aoqi@0: //
aoqi@0: /**
aoqi@0: * Functional interface for defining inference callbacks. Certain actions
aoqi@0: * (i.e. subtyping checks) might need to be redone after all inference variables
aoqi@0: * have been fixed.
aoqi@0: */
aoqi@0: interface FreeTypeListener {
aoqi@0: void typesInferred(InferenceContext inferenceContext);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * An inference context keeps track of the set of variables that are free
aoqi@0: * in the current context. It provides utility methods for opening/closing
aoqi@0: * types to their corresponding free/closed forms. It also provide hooks for
aoqi@0: * attaching deferred post-inference action (see PendingCheck). Finally,
aoqi@0: * it can be used as an entry point for performing upper/lower bound inference
aoqi@0: * (see InferenceKind).
aoqi@0: */
aoqi@0: class InferenceContext {
aoqi@0:
aoqi@0: /** list of inference vars as undet vars */
aoqi@0: List undetvars;
aoqi@0:
aoqi@0: /** list of inference vars in this context */
aoqi@0: List inferencevars;
aoqi@0:
aoqi@0: java.util.Map> freeTypeListeners =
aoqi@0: new java.util.HashMap>();
aoqi@0:
aoqi@0: List freetypeListeners = List.nil();
aoqi@0:
aoqi@0: public InferenceContext(List inferencevars) {
aoqi@0: this.undetvars = Type.map(inferencevars, fromTypeVarFun);
aoqi@0: this.inferencevars = inferencevars;
aoqi@0: }
aoqi@0: //where
aoqi@0: Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
aoqi@0: // mapping that turns inference variables into undet vars
aoqi@0: public Type apply(Type t) {
aoqi@0: if (t.hasTag(TYPEVAR)) {
aoqi@0: TypeVar tv = (TypeVar)t;
aoqi@0: if (tv.isCaptured()) {
aoqi@0: return new CapturedUndetVar((CapturedType)tv, types);
aoqi@0: } else {
aoqi@0: return new UndetVar(tv, types);
aoqi@0: }
aoqi@0: } else {
aoqi@0: return t.map(this);
aoqi@0: }
aoqi@0: }
aoqi@0: };
aoqi@0:
aoqi@0: /**
aoqi@0: * add a new inference var to this inference context
aoqi@0: */
aoqi@0: void addVar(TypeVar t) {
aoqi@0: this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));
aoqi@0: this.inferencevars = this.inferencevars.prepend(t);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * returns the list of free variables (as type-variables) in this
aoqi@0: * inference context
aoqi@0: */
aoqi@0: List inferenceVars() {
aoqi@0: return inferencevars;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * returns the list of uninstantiated variables (as type-variables) in this
aoqi@0: * inference context
aoqi@0: */
aoqi@0: List restvars() {
aoqi@0: return filterVars(new Filter() {
aoqi@0: public boolean accepts(UndetVar uv) {
aoqi@0: return uv.inst == null;
aoqi@0: }
aoqi@0: });
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * returns the list of instantiated variables (as type-variables) in this
aoqi@0: * inference context
aoqi@0: */
aoqi@0: List instvars() {
aoqi@0: return filterVars(new Filter() {
aoqi@0: public boolean accepts(UndetVar uv) {
aoqi@0: return uv.inst != null;
aoqi@0: }
aoqi@0: });
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Get list of bounded inference variables (where bound is other than
aoqi@0: * declared bounds).
aoqi@0: */
aoqi@0: final List boundedVars() {
aoqi@0: return filterVars(new Filter() {
aoqi@0: public boolean accepts(UndetVar uv) {
aoqi@0: return uv.getBounds(InferenceBound.UPPER)
aoqi@0: .diff(uv.getDeclaredBounds())
aoqi@0: .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
aoqi@0: }
aoqi@0: });
aoqi@0: }
aoqi@0:
aoqi@0: /* Returns the corresponding inference variables.
aoqi@0: */
aoqi@0: private List filterVars(Filter fu) {
aoqi@0: ListBuffer res = new ListBuffer<>();
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: if (fu.accepts(uv)) {
aoqi@0: res.append(uv.qtype);
aoqi@0: }
aoqi@0: }
aoqi@0: return res.toList();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * is this type free?
aoqi@0: */
aoqi@0: final boolean free(Type t) {
aoqi@0: return t.containsAny(inferencevars);
aoqi@0: }
aoqi@0:
aoqi@0: final boolean free(List ts) {
aoqi@0: for (Type t : ts) {
aoqi@0: if (free(t)) return true;
aoqi@0: }
aoqi@0: return false;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Returns a list of free variables in a given type
aoqi@0: */
aoqi@0: final List freeVarsIn(Type t) {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type iv : inferenceVars()) {
aoqi@0: if (t.contains(iv)) {
aoqi@0: buf.add(iv);
aoqi@0: }
aoqi@0: }
aoqi@0: return buf.toList();
aoqi@0: }
aoqi@0:
aoqi@0: final List freeVarsIn(List ts) {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type t : ts) {
aoqi@0: buf.appendList(freeVarsIn(t));
aoqi@0: }
aoqi@0: ListBuffer buf2 = new ListBuffer<>();
aoqi@0: for (Type t : buf) {
aoqi@0: if (!buf2.contains(t)) {
aoqi@0: buf2.add(t);
aoqi@0: }
aoqi@0: }
aoqi@0: return buf2.toList();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Replace all free variables in a given type with corresponding
aoqi@0: * undet vars (used ahead of subtyping/compatibility checks to allow propagation
aoqi@0: * of inference constraints).
aoqi@0: */
aoqi@0: final Type asUndetVar(Type t) {
aoqi@0: return types.subst(t, inferencevars, undetvars);
aoqi@0: }
aoqi@0:
aoqi@0: final List asUndetVars(List ts) {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type t : ts) {
aoqi@0: buf.append(asUndetVar(t));
aoqi@0: }
aoqi@0: return buf.toList();
aoqi@0: }
aoqi@0:
aoqi@0: List instTypes() {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: buf.append(uv.inst != null ? uv.inst : uv.qtype);
aoqi@0: }
aoqi@0: return buf.toList();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Replace all free variables in a given type with corresponding
aoqi@0: * instantiated types - if one or more free variable has not been
aoqi@0: * fully instantiated, it will still be available in the resulting type.
aoqi@0: */
aoqi@0: Type asInstType(Type t) {
aoqi@0: return types.subst(t, inferencevars, instTypes());
aoqi@0: }
aoqi@0:
aoqi@0: List asInstTypes(List ts) {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type t : ts) {
aoqi@0: buf.append(asInstType(t));
aoqi@0: }
aoqi@0: return buf.toList();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Add custom hook for performing post-inference action
aoqi@0: */
aoqi@0: void addFreeTypeListener(List types, FreeTypeListener ftl) {
aoqi@0: freeTypeListeners.put(ftl, freeVarsIn(types));
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Mark the inference context as complete and trigger evaluation
aoqi@0: * of all deferred checks.
aoqi@0: */
aoqi@0: void notifyChange() {
aoqi@0: notifyChange(inferencevars.diff(restvars()));
aoqi@0: }
aoqi@0:
aoqi@0: void notifyChange(List inferredVars) {
aoqi@0: InferenceException thrownEx = null;
aoqi@0: for (Map.Entry> entry :
aoqi@0: new HashMap>(freeTypeListeners).entrySet()) {
aoqi@0: if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
aoqi@0: try {
aoqi@0: entry.getKey().typesInferred(this);
aoqi@0: freeTypeListeners.remove(entry.getKey());
aoqi@0: } catch (InferenceException ex) {
aoqi@0: if (thrownEx == null) {
aoqi@0: thrownEx = ex;
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: //inference exception multiplexing - present any inference exception
aoqi@0: //thrown when processing listeners as a single one
aoqi@0: if (thrownEx != null) {
aoqi@0: throw thrownEx;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Save the state of this inference context
aoqi@0: */
aoqi@0: List save() {
aoqi@0: ListBuffer buf = new ListBuffer<>();
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
aoqi@0: for (InferenceBound ib : InferenceBound.values()) {
aoqi@0: for (Type b : uv.getBounds(ib)) {
aoqi@0: uv2.addBound(ib, b, types);
aoqi@0: }
aoqi@0: }
aoqi@0: uv2.inst = uv.inst;
aoqi@0: buf.add(uv2);
aoqi@0: }
aoqi@0: return buf.toList();
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Restore the state of this inference context to the previous known checkpoint
aoqi@0: */
aoqi@0: void rollback(List saved_undet) {
aoqi@0: Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
aoqi@0: //restore bounds (note: we need to preserve the old instances)
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: UndetVar uv_saved = (UndetVar)saved_undet.head;
aoqi@0: for (InferenceBound ib : InferenceBound.values()) {
aoqi@0: uv.setBounds(ib, uv_saved.getBounds(ib));
aoqi@0: }
aoqi@0: uv.inst = uv_saved.inst;
aoqi@0: saved_undet = saved_undet.tail;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Copy variable in this inference context to the given context
aoqi@0: */
aoqi@0: void dupTo(final InferenceContext that) {
aoqi@0: that.inferencevars = that.inferencevars.appendList(
aoqi@0: inferencevars.diff(that.inferencevars));
aoqi@0: that.undetvars = that.undetvars.appendList(
aoqi@0: undetvars.diff(that.undetvars));
aoqi@0: //set up listeners to notify original inference contexts as
aoqi@0: //propagated vars are inferred in new context
aoqi@0: for (Type t : inferencevars) {
aoqi@0: that.freeTypeListeners.put(new FreeTypeListener() {
aoqi@0: public void typesInferred(InferenceContext inferenceContext) {
aoqi@0: InferenceContext.this.notifyChange();
aoqi@0: }
aoqi@0: }, List.of(t));
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: private void solve(GraphStrategy ss, Warner warn) {
aoqi@0: solve(ss, new HashMap>(), warn);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Solve with given graph strategy.
aoqi@0: */
aoqi@0: private void solve(GraphStrategy ss, Map> stuckDeps, Warner warn) {
aoqi@0: GraphSolver s = new GraphSolver(this, stuckDeps, warn);
aoqi@0: s.solve(ss);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Solve all variables in this context.
aoqi@0: */
aoqi@0: public void solve(Warner warn) {
aoqi@0: solve(new LeafSolver() {
aoqi@0: public boolean done() {
aoqi@0: return restvars().isEmpty();
aoqi@0: }
aoqi@0: }, warn);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Solve all variables in the given list.
aoqi@0: */
aoqi@0: public void solve(final List vars, Warner warn) {
aoqi@0: solve(new BestLeafSolver(vars) {
aoqi@0: public boolean done() {
aoqi@0: return !free(asInstTypes(vars));
aoqi@0: }
aoqi@0: }, warn);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Solve at least one variable in given list.
aoqi@0: */
aoqi@0: public void solveAny(List varsToSolve, Map> optDeps, Warner warn) {
aoqi@0: solve(new BestLeafSolver(varsToSolve.intersect(restvars())) {
aoqi@0: public boolean done() {
aoqi@0: return instvars().intersect(varsToSolve).nonEmpty();
aoqi@0: }
aoqi@0: }, optDeps, warn);
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Apply a set of inference steps
aoqi@0: */
aoqi@0: private boolean solveBasic(EnumSet steps) {
aoqi@0: return solveBasic(inferencevars, steps);
aoqi@0: }
aoqi@0:
aoqi@0: private boolean solveBasic(List varsToSolve, EnumSet steps) {
aoqi@0: boolean changed = false;
aoqi@0: for (Type t : varsToSolve.intersect(restvars())) {
aoqi@0: UndetVar uv = (UndetVar)asUndetVar(t);
aoqi@0: for (InferenceStep step : steps) {
aoqi@0: if (step.accepts(uv, this)) {
aoqi@0: uv.inst = step.solve(uv, this);
aoqi@0: changed = true;
aoqi@0: break;
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: return changed;
aoqi@0: }
aoqi@0:
aoqi@0: /**
aoqi@0: * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
aoqi@0: * During overload resolution, instantiation is done by doing a partial
aoqi@0: * inference process using eq/lower bound instantiation. During check,
aoqi@0: * we also instantiate any remaining vars by repeatedly using eq/upper
aoqi@0: * instantiation, until all variables are solved.
aoqi@0: */
aoqi@0: public void solveLegacy(boolean partial, Warner warn, EnumSet steps) {
aoqi@0: while (true) {
aoqi@0: boolean stuck = !solveBasic(steps);
aoqi@0: if (restvars().isEmpty() || partial) {
aoqi@0: //all variables have been instantiated - exit
aoqi@0: break;
aoqi@0: } else if (stuck) {
aoqi@0: //some variables could not be instantiated because of cycles in
aoqi@0: //upper bounds - provide a (possibly recursive) default instantiation
aoqi@0: instantiateAsUninferredVars(restvars(), this);
aoqi@0: break;
aoqi@0: } else {
aoqi@0: //some variables have been instantiated - replace newly instantiated
aoqi@0: //variables in remaining upper bounds and continue
aoqi@0: for (Type t : undetvars) {
aoqi@0: UndetVar uv = (UndetVar)t;
aoqi@0: uv.substBounds(inferenceVars(), instTypes(), types);
aoqi@0: }
aoqi@0: }
aoqi@0: }
aoqi@0: checkWithinBounds(this, warn);
aoqi@0: }
aoqi@0:
aoqi@0: private Infer infer() {
aoqi@0: //back-door to infer
aoqi@0: return Infer.this;
aoqi@0: }
aoqi@0:
aoqi@0: @Override
aoqi@0: public String toString() {
aoqi@0: return "Inference vars: " + inferencevars + '\n' +
aoqi@0: "Undet vars: " + undetvars;
aoqi@0: }
aoqi@0:
aoqi@0: /* Method Types.capture() generates a new type every time it's applied
aoqi@0: * to a wildcard parameterized type. This is intended functionality but
aoqi@0: * there are some cases when what you need is not to generate a new
aoqi@0: * captured type but to check that a previously generated captured type
aoqi@0: * is correct. There are cases when caching a captured type for later
aoqi@0: * reuse is sound. In general two captures from the same AST are equal.
aoqi@0: * This is why the tree is used as the key of the map below. This map
aoqi@0: * stores a Type per AST.
aoqi@0: */
aoqi@0: Map captureTypeCache = new HashMap<>();
aoqi@0:
aoqi@0: Type cachedCapture(JCTree tree, Type t, boolean readOnly) {
aoqi@0: Type captured = captureTypeCache.get(tree);
aoqi@0: if (captured != null) {
aoqi@0: return captured;
aoqi@0: }
aoqi@0:
aoqi@0: Type result = types.capture(t);
aoqi@0: if (result != t && !readOnly) { // then t is a wildcard parameterized type
aoqi@0: captureTypeCache.put(tree, result);
aoqi@0: }
aoqi@0: return result;
aoqi@0: }
aoqi@0: }
aoqi@0:
aoqi@0: final InferenceContext emptyContext = new InferenceContext(List.nil());
aoqi@0: //
aoqi@0: }