duke@1: /*
mcimadamore@1562: * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved.
duke@1: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1: *
duke@1: * This code is free software; you can redistribute it and/or modify it
duke@1: * under the terms of the GNU General Public License version 2 only, as
ohair@554: * published by the Free Software Foundation. Oracle designates this
duke@1: * particular file as subject to the "Classpath" exception as provided
ohair@554: * by Oracle in the LICENSE file that accompanied this code.
duke@1: *
duke@1: * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1: * version 2 for more details (a copy is included in the LICENSE file that
duke@1: * accompanied this code).
duke@1: *
duke@1: * You should have received a copy of the GNU General Public License version
duke@1: * 2 along with this work; if not, write to the Free Software Foundation,
duke@1: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1: *
ohair@554: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554: * or visit www.oracle.com if you need additional information or have any
ohair@554: * questions.
duke@1: */
duke@1:
duke@1: package com.sun.tools.javac.comp;
duke@1:
mcimadamore@674: import com.sun.tools.javac.tree.JCTree;
mcimadamore@674: import com.sun.tools.javac.tree.JCTree.JCTypeCast;
mcimadamore@820: import com.sun.tools.javac.tree.TreeInfo;
duke@1: import com.sun.tools.javac.util.*;
mcimadamore@1562: import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
duke@1: import com.sun.tools.javac.util.List;
mcimadamore@1562: import com.sun.tools.javac.code.*;
mcimadamore@1562: import com.sun.tools.javac.code.Type.*;
mcimadamore@1562: import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
mcimadamore@1562: import com.sun.tools.javac.code.Symbol.*;
mcimadamore@1562: import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
mcimadamore@1562: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
mcimadamore@1562: import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
mcimadamore@1562: import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
mcimadamore@1562: import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
duke@1:
mcimadamore@1337: import java.util.HashMap;
mcimadamore@1337: import java.util.Map;
mcimadamore@1562: import java.util.Set;
mcimadamore@1562:
mcimadamore@1562: import java.util.ArrayList;
mcimadamore@1562: import java.util.Collections;
mcimadamore@1562: import java.util.EnumSet;
mcimadamore@1562: import java.util.HashSet;
mcimadamore@1337:
jjg@1374: import static com.sun.tools.javac.code.TypeTag.*;
duke@1:
duke@1: /** Helper class for type parameter inference, used by the attribution phase.
duke@1: *
jjg@581: *
This is NOT part of any supported API.
jjg@581: * If you write code that depends on this, you do so at your own risk.
duke@1: * This code and its internal interfaces are subject to change or
duke@1: * deletion without notice.
duke@1: */
duke@1: public class Infer {
duke@1: protected static final Context.Key inferKey =
duke@1: new Context.Key();
duke@1:
mcimadamore@1562: Resolve rs;
mcimadamore@1562: Check chk;
duke@1: Symtab syms;
duke@1: Types types;
mcimadamore@1562: JCDiagnostic.Factory diags;
mcimadamore@1114: Log log;
duke@1:
mcimadamore@1562: /** should the graph solver be used? */
mcimadamore@1562: boolean allowGraphInference;
mcimadamore@1510:
duke@1: public static Infer instance(Context context) {
duke@1: Infer instance = context.get(inferKey);
duke@1: if (instance == null)
duke@1: instance = new Infer(context);
duke@1: return instance;
duke@1: }
duke@1:
duke@1: protected Infer(Context context) {
duke@1: context.put(inferKey, this);
mcimadamore@1562:
mcimadamore@1562: rs = Resolve.instance(context);
mcimadamore@1562: chk = Check.instance(context);
duke@1: syms = Symtab.instance(context);
duke@1: types = Types.instance(context);
mcimadamore@1562: diags = JCDiagnostic.Factory.instance(context);
mcimadamore@1114: log = Log.instance(context);
mcimadamore@1298: inferenceException = new InferenceException(diags);
mcimadamore@1562: Options options = Options.instance(context);
mcimadamore@1562: allowGraphInference = Source.instance(context).allowGraphInference()
mcimadamore@1562: && options.isUnset("useLegacyInference");
duke@1: }
duke@1:
mcimadamore@1562: /** A value for prototypes that admit any type, including polymorphic ones. */
mcimadamore@1562: public static final Type anyPoly = new Type(NONE, null);
mcimadamore@1562:
mcimadamore@1337: /**
mcimadamore@1337: * This exception class is design to store a list of diagnostics corresponding
mcimadamore@1337: * to inference errors that can arise during a method applicability check.
mcimadamore@1337: */
mcimadamore@1186: public static class InferenceException extends InapplicableMethodException {
duke@1: private static final long serialVersionUID = 0;
duke@1:
mcimadamore@1337: List messages = List.nil();
mcimadamore@1337:
mcimadamore@299: InferenceException(JCDiagnostic.Factory diags) {
mcimadamore@689: super(diags);
duke@1: }
mcimadamore@1337:
mcimadamore@1337: @Override
mcimadamore@1337: InapplicableMethodException setMessage(JCDiagnostic diag) {
mcimadamore@1337: messages = messages.append(diag);
mcimadamore@1337: return this;
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: @Override
mcimadamore@1337: public JCDiagnostic getDiagnostic() {
mcimadamore@1337: return messages.head;
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: void clear() {
mcimadamore@1337: messages = List.nil();
mcimadamore@1337: }
mcimadamore@299: }
mcimadamore@299:
mcimadamore@1562: protected final InferenceException inferenceException;
duke@1:
mcimadamore@1562: //
mcimadamore@1337: /**
mcimadamore@1562: * Main inference entry point - instantiate a generic method type
mcimadamore@1562: * using given argument types and (possibly) an expected target-type.
duke@1: */
mcimadamore@1268: public Type instantiateMethod(Env env,
mcimadamore@547: List tvars,
duke@1: MethodType mt,
mcimadamore@1268: Attr.ResultInfo resultInfo,
mcimadamore@1268: Symbol msym,
mcimadamore@1268: List argtypes,
mcimadamore@1268: boolean allowBoxing,
mcimadamore@1268: boolean useVarargs,
mcimadamore@1347: Resolve.MethodResolutionContext resolveContext,
mcimadamore@1479: Resolve.MethodCheck methodCheck,
mcimadamore@1268: Warner warn) throws InferenceException {
duke@1: //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
mcimadamore@1550: final InferenceContext inferenceContext = new InferenceContext(tvars);
mcimadamore@1337: inferenceException.clear();
mcimadamore@1562: try {
mcimadamore@1562: DeferredAttr.DeferredAttrContext deferredAttrContext =
mcimadamore@1562: resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
mcimadamore@689:
mcimadamore@1562: methodCheck.argumentsAcceptable(env, deferredAttrContext,
mcimadamore@1562: argtypes, mt.getParameterTypes(), warn);
mcimadamore@1479:
mcimadamore@1562: if (allowGraphInference &&
mcimadamore@1562: resultInfo != null &&
mcimadamore@1510: !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
mcimadamore@1562: //inject return constraints earlier
mcimadamore@1562: checkWithinBounds(inferenceContext, warn); //propagation
mcimadamore@1562: generateReturnConstraints(resultInfo, mt, inferenceContext);
mcimadamore@1562: //propagate outwards if needed
mcimadamore@1562: if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
mcimadamore@1562: //propagate inference context outwards and exit
mcimadamore@1562: inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
mcimadamore@1562: deferredAttrContext.complete();
mcimadamore@1562: return mt;
mcimadamore@1562: }
mcimadamore@1510: }
mcimadamore@1510:
mcimadamore@1479: deferredAttrContext.complete();
duke@1:
mcimadamore@1337: // minimize as yet undetermined type variables
mcimadamore@1562: if (allowGraphInference) {
mcimadamore@1562: inferenceContext.solve(warn);
mcimadamore@1562: } else {
mcimadamore@1562: inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
mcimadamore@1337: }
duke@1:
mcimadamore@1550: mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@396:
mcimadamore@1562: if (!allowGraphInference &&
mcimadamore@1562: inferenceContext.restvars().nonEmpty() &&
mcimadamore@1562: resultInfo != null &&
mcimadamore@1562: !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
mcimadamore@1562: generateReturnConstraints(resultInfo, mt, inferenceContext);
mcimadamore@1562: inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
mcimadamore@1562: mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@1562: }
duke@1:
mcimadamore@1562: if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
mcimadamore@1562: log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
mcimadamore@1337: }
duke@1:
mcimadamore@1337: // return instantiated version of method type
mcimadamore@1337: return mt;
mcimadamore@1337: } finally {
mcimadamore@1562: if (resultInfo != null || !allowGraphInference) {
mcimadamore@1562: inferenceContext.notifyChange();
mcimadamore@1562: } else {
mcimadamore@1562: inferenceContext.notifyChange(inferenceContext.boundedVars());
mcimadamore@1338: }
duke@1: }
mcimadamore@895: }
duke@1:
mcimadamore@1562: /**
mcimadamore@1562: * Generate constraints from the generic method's return type. If the method
mcimadamore@1562: * call occurs in a context where a type T is expected, use the expected
mcimadamore@1562: * type to derive more constraints on the generic method inference variables.
mcimadamore@1562: */
mcimadamore@1562: void generateReturnConstraints(Attr.ResultInfo resultInfo,
mcimadamore@1562: MethodType mt, InferenceContext inferenceContext) {
mcimadamore@1562: Type qtype1 = inferenceContext.asFree(mt.getReturnType());
mcimadamore@1562: Type to = returnConstraintTarget(qtype1, resultInfo.pt);
mcimadamore@1562: Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().free(to),
mcimadamore@1562: "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
mcimadamore@1562: //we need to skip capture?
mcimadamore@1562: Warner retWarn = new Warner();
mcimadamore@1562: if (!resultInfo.checkContext.compatible(qtype1, resultInfo.checkContext.inferenceContext().asFree(to), retWarn) ||
mcimadamore@1562: //unchecked conversion is not allowed
mcimadamore@1562: retWarn.hasLint(Lint.LintCategory.UNCHECKED)) {
mcimadamore@1562: throw inferenceException
mcimadamore@1562: .setMessage("infer.no.conforming.instance.exists",
mcimadamore@1562: inferenceContext.restvars(), mt.getReturnType(), to);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //where
mcimadamore@1562: private Type returnConstraintTarget(Type from, Type to) {
mcimadamore@1562: if (from.hasTag(VOID)) {
mcimadamore@1562: return syms.voidType;
mcimadamore@1562: } else if (to.hasTag(NONE)) {
mcimadamore@1562: return from.isPrimitive() ? from : syms.objectType;
mcimadamore@1562: } else if (from.hasTag(UNDETVAR) && to.isPrimitive()) {
mcimadamore@1562: if (!allowGraphInference) {
mcimadamore@1562: //if legacy, just return boxed type
mcimadamore@1562: return types.boxedClass(to).type;
mcimadamore@1562: }
mcimadamore@1562: //if graph inference we need to skip conflicting boxed bounds...
mcimadamore@1562: UndetVar uv = (UndetVar)from;
mcimadamore@1562: for (Type t : uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
mcimadamore@1562: Type boundAsPrimitive = types.unboxedType(t);
mcimadamore@1562: if (boundAsPrimitive == null) continue;
mcimadamore@1562: if (types.isConvertible(boundAsPrimitive, to)) {
mcimadamore@1562: //effectively skip return-type constraint generation (compatibility)
mcimadamore@1562: return syms.objectType;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: return types.boxedClass(to).type;
mcimadamore@1562: } else {
mcimadamore@1562: return to;
mcimadamore@1251: }
duke@1: }
mcimadamore@1251:
mcimadamore@1562: /**
mcimadamore@1562: * Infer cyclic inference variables as described in 15.12.2.8.
mcimadamore@1562: */
mcimadamore@1562: private void instantiateAsUninferredVars(List vars, InferenceContext inferenceContext) {
mcimadamore@1562: ListBuffer todo = ListBuffer.lb();
mcimadamore@1562: //step 1 - create fresh tvars
mcimadamore@1562: for (Type t : vars) {
mcimadamore@1562: UndetVar uv = (UndetVar)inferenceContext.asFree(t);
mcimadamore@1562: List upperBounds = uv.getBounds(InferenceBound.UPPER);
mcimadamore@1562: if (Type.containsAny(upperBounds, vars)) {
mcimadamore@1562: TypeSymbol fresh_tvar = new TypeSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
mcimadamore@1562: fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
mcimadamore@1562: todo.append(uv);
mcimadamore@1562: uv.inst = fresh_tvar.type;
mcimadamore@1562: } else if (upperBounds.nonEmpty()) {
mcimadamore@1562: uv.inst = types.glb(upperBounds);
mcimadamore@1562: } else {
mcimadamore@1562: uv.inst = syms.objectType;
mcimadamore@1338: }
mcimadamore@1562: }
mcimadamore@1562: //step 2 - replace fresh tvars in their bounds
mcimadamore@1562: List formals = vars;
mcimadamore@1562: for (Type t : todo) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: TypeVar ct = (TypeVar)uv.inst;
mcimadamore@1562: ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
mcimadamore@1562: if (ct.bound.isErroneous()) {
mcimadamore@1562: //report inference error if glb fails
mcimadamore@1562: reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1338: }
mcimadamore@1562: formals = formals.tail;
mcimadamore@1348: }
mcimadamore@1348: }
mcimadamore@1348:
mcimadamore@674: /**
mcimadamore@674: * Compute a synthetic method type corresponding to the requested polymorphic
mcimadamore@820: * method signature. The target return type is computed from the immediately
mcimadamore@820: * enclosing scope surrounding the polymorphic-signature call.
mcimadamore@674: */
mcimadamore@1239: Type instantiatePolymorphicSignatureInstance(Env env,
mcimadamore@674: MethodSymbol spMethod, // sig. poly. method or null if none
mcimadamore@1347: Resolve.MethodResolutionContext resolveContext,
mcimadamore@820: List argtypes) {
mcimadamore@674: final Type restype;
mcimadamore@716:
mcimadamore@820: //The return type for a polymorphic signature call is computed from
mcimadamore@820: //the enclosing tree E, as follows: if E is a cast, then use the
mcimadamore@820: //target type of the cast expression as a return type; if E is an
mcimadamore@820: //expression statement, the return type is 'void' - otherwise the
mcimadamore@820: //return type is simply 'Object'. A correctness check ensures that
mcimadamore@820: //env.next refers to the lexically enclosing environment in which
mcimadamore@820: //the polymorphic signature call environment is nested.
mcimadamore@820:
mcimadamore@820: switch (env.next.tree.getTag()) {
jjg@1127: case TYPECAST:
mcimadamore@820: JCTypeCast castTree = (JCTypeCast)env.next.tree;
mcimadamore@820: restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
mcimadamore@820: castTree.clazz.type :
mcimadamore@820: syms.objectType;
mcimadamore@820: break;
jjg@1127: case EXEC:
mcimadamore@820: JCTree.JCExpressionStatement execTree =
mcimadamore@820: (JCTree.JCExpressionStatement)env.next.tree;
mcimadamore@820: restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
mcimadamore@820: syms.voidType :
mcimadamore@820: syms.objectType;
mcimadamore@820: break;
mcimadamore@820: default:
mcimadamore@820: restype = syms.objectType;
mcimadamore@674: }
mcimadamore@674:
mcimadamore@1347: List paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
mcimadamore@674: List exType = spMethod != null ?
mcimadamore@674: spMethod.getThrownTypes() :
mcimadamore@674: List.of(syms.throwableType); // make it throw all exceptions
mcimadamore@674:
mcimadamore@674: MethodType mtype = new MethodType(paramtypes,
mcimadamore@674: restype,
mcimadamore@674: exType,
mcimadamore@674: syms.methodClass);
mcimadamore@674: return mtype;
mcimadamore@674: }
mcimadamore@674: //where
mcimadamore@1347: class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
mcimadamore@1347:
mcimadamore@1347: public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
mcimadamore@1562: rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase);
mcimadamore@1347: }
mcimadamore@1347:
mcimadamore@1347: public Type apply(Type t) {
mcimadamore@1347: t = types.erasure(super.apply(t));
jjg@1374: if (t.hasTag(BOT))
mcimadamore@1347: // nulls type as the marker type Null (which has no instances)
mcimadamore@1347: // infer as java.lang.Void for now
mcimadamore@1347: t = types.boxedClass(syms.voidType).type;
mcimadamore@1347: return t;
mcimadamore@1347: }
mcimadamore@1347: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1562: * This method is used to infer a suitable target SAM in case the original
mcimadamore@1562: * SAM type contains one or more wildcards. An inference process is applied
mcimadamore@1562: * so that wildcard bounds, as well as explicit lambda/method ref parameters
mcimadamore@1562: * (where applicable) are used to constraint the solution.
mcimadamore@1562: */
mcimadamore@1562: public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
mcimadamore@1562: List paramTypes, Check.CheckContext checkContext) {
mcimadamore@1562: if (types.capture(funcInterface) == funcInterface) {
mcimadamore@1562: //if capture doesn't change the type then return the target unchanged
mcimadamore@1562: //(this means the target contains no wildcards!)
mcimadamore@1562: return funcInterface;
mcimadamore@1562: } else {
mcimadamore@1562: Type formalInterface = funcInterface.tsym.type;
mcimadamore@1562: InferenceContext funcInterfaceContext =
mcimadamore@1562: new InferenceContext(funcInterface.tsym.type.getTypeArguments());
mcimadamore@1562:
mcimadamore@1562: Assert.check(paramTypes != null);
mcimadamore@1562: //get constraints from explicit params (this is done by
mcimadamore@1562: //checking that explicit param types are equal to the ones
mcimadamore@1562: //in the functional interface descriptors)
mcimadamore@1562: List descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
mcimadamore@1562: if (descParameterTypes.size() != paramTypes.size()) {
mcimadamore@1562: checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
mcimadamore@1562: return types.createErrorType(funcInterface);
mcimadamore@1562: }
mcimadamore@1562: for (Type p : descParameterTypes) {
mcimadamore@1562: if (!types.isSameType(funcInterfaceContext.asFree(p), paramTypes.head)) {
mcimadamore@1562: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562: return types.createErrorType(funcInterface);
mcimadamore@1562: }
mcimadamore@1562: paramTypes = paramTypes.tail;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: try {
mcimadamore@1562: funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
mcimadamore@1562: } catch (InferenceException ex) {
mcimadamore@1562: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: List actualTypeargs = funcInterface.getTypeArguments();
mcimadamore@1562: for (Type t : funcInterfaceContext.undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: if (uv.inst == null) {
mcimadamore@1562: uv.inst = actualTypeargs.head;
mcimadamore@1562: }
mcimadamore@1562: actualTypeargs = actualTypeargs.tail;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: Type owntype = funcInterfaceContext.asInstType(formalInterface);
mcimadamore@1562: if (!chk.checkValidGenericType(owntype)) {
mcimadamore@1562: //if the inferred functional interface type is not well-formed,
mcimadamore@1562: //or if it's not a subtype of the original target, issue an error
mcimadamore@1562: checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562: }
mcimadamore@1562: return owntype;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //
mcimadamore@1562:
mcimadamore@1562: //
mcimadamore@1562: /**
mcimadamore@1562: * Check bounds and perform incorporation
mcimadamore@1562: */
mcimadamore@1562: void checkWithinBounds(InferenceContext inferenceContext,
mcimadamore@1562: Warner warn) throws InferenceException {
mcimadamore@1562: MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
mcimadamore@1562: try {
mcimadamore@1562: while (true) {
mcimadamore@1562: mlistener.reset();
mcimadamore@1562: if (!allowGraphInference) {
mcimadamore@1562: //in legacy mode we lack of transitivity, so bound check
mcimadamore@1562: //cannot be run in parallel with other incoprporation rounds
mcimadamore@1562: for (Type t : inferenceContext.undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: for (Type t : inferenceContext.undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: //bound incorporation
mcimadamore@1562: EnumSet incorporationSteps = allowGraphInference ?
mcimadamore@1562: incorporationStepsGraph : incorporationStepsLegacy;
mcimadamore@1562: for (IncorporationStep is : incorporationSteps) {
mcimadamore@1562: is.apply(uv, inferenceContext, warn);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: if (!mlistener.changed || !allowGraphInference) break;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: finally {
mcimadamore@1562: mlistener.detach();
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //where
mcimadamore@1562: /**
mcimadamore@1562: * This listener keeps track of changes on a group of inference variable
mcimadamore@1562: * bounds. Note: the listener must be detached (calling corresponding
mcimadamore@1562: * method) to make sure that the underlying inference variable is
mcimadamore@1562: * left in a clean state.
mcimadamore@1562: */
mcimadamore@1562: class MultiUndetVarListener implements UndetVar.UndetVarListener {
mcimadamore@1562:
mcimadamore@1562: int rounds;
mcimadamore@1562: boolean changed;
mcimadamore@1562: List undetvars;
mcimadamore@1562:
mcimadamore@1562: public MultiUndetVarListener(List undetvars) {
mcimadamore@1562: this.undetvars = undetvars;
mcimadamore@1562: for (Type t : undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: uv.listener = this;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: public void varChanged(UndetVar uv, Set ibs) {
mcimadamore@1562: //avoid non-termination
mcimadamore@1562: if (rounds < MAX_INCORPORATION_STEPS) {
mcimadamore@1562: changed = true;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: void reset() {
mcimadamore@1562: rounds++;
mcimadamore@1562: changed = false;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: void detach() {
mcimadamore@1562: for (Type t : undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: uv.listener = null;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: };
mcimadamore@1562:
mcimadamore@1562: /** max number of incorporation rounds */
mcimadamore@1562: static final int MAX_INCORPORATION_STEPS = 100;
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This enumeration defines an entry point for doing inference variable
mcimadamore@1562: * bound incorporation - it can be used to inject custom incorporation
mcimadamore@1562: * logic into the basic bound checking routine
mcimadamore@1562: */
mcimadamore@1562: enum IncorporationStep {
mcimadamore@1562: /**
mcimadamore@1562: * Performs basic bound checking - i.e. is the instantiated type for a given
mcimadamore@1562: * inference variable compatible with its bounds?
mcimadamore@1562: */
mcimadamore@1562: CHECK_BOUNDS() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
mcimadamore@1562: infer.checkCompatibleUpperBounds(uv, inferenceContext);
mcimadamore@1562: if (uv.inst != null) {
mcimadamore@1562: Type inst = uv.inst;
mcimadamore@1562: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(inst, inferenceContext.asFree(u), warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.UPPER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), inst, warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.LOWER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: if (!infer.types.isSameType(inst, inferenceContext.asFree(e))) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Check consistency of equality constraints. This is a slightly more aggressive
mcimadamore@1562: * inference routine that is designed as to maximize compatibility with JDK 7.
mcimadamore@1562: * Note: this is not used in graph mode.
mcimadamore@1562: */
mcimadamore@1562: EQ_CHECK_LEGACY() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: Type eq = null;
mcimadamore@1562: for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: Assert.check(!inferenceContext.free(e));
mcimadamore@1562: if (eq != null && !infer.types.isSameType(e, eq)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562: }
mcimadamore@1562: eq = e;
mcimadamore@1562: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: Assert.check(!inferenceContext.free(l));
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(l, e, warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: if (inferenceContext.free(u)) continue;
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(e, u, warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Check consistency of equality constraints.
mcimadamore@1562: */
mcimadamore@1562: EQ_CHECK() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: if (e.containsAny(inferenceContext.inferenceVars())) continue;
mcimadamore@1562: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(e, inferenceContext.asFree(u), warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), e, warn)) {
mcimadamore@1562: infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
mcimadamore@1562: * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562: */
mcimadamore@1562: CROSS_UPPER_LOWER() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: if (!inferenceContext.inferenceVars().contains(b1) &&
mcimadamore@1562: !inferenceContext.inferenceVars().contains(b2) &&
mcimadamore@1562: infer.types.asSuper(b2, b1.tsym) != null) {
mcimadamore@1562: infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
mcimadamore@1562: * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562: */
mcimadamore@1562: CROSS_UPPER_EQ() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: if (!inferenceContext.inferenceVars().contains(b1) &&
mcimadamore@1562: !inferenceContext.inferenceVars().contains(b2) &&
mcimadamore@1562: infer.types.asSuper(b2, b1.tsym) != null) {
mcimadamore@1562: infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
mcimadamore@1562: * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562: */
mcimadamore@1562: CROSS_EQ_LOWER() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: if (!inferenceContext.inferenceVars().contains(b1) &&
mcimadamore@1562: !inferenceContext.inferenceVars().contains(b2) &&
mcimadamore@1562: infer.types.asSuper(b2, b1.tsym) != null) {
mcimadamore@1562: infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha <: beta} propagate lower bounds
mcimadamore@1562: * from alpha to beta; also propagate upper bounds from beta to alpha.
mcimadamore@1562: */
mcimadamore@1562: PROP_UPPER() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: if (inferenceContext.inferenceVars().contains(b)) {
mcimadamore@1562: UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
mcimadamore@1562: //alpha <: beta
mcimadamore@1562: //1. copy alpha's lower to beta's
mcimadamore@1562: for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: uv2.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
mcimadamore@1562: }
mcimadamore@1562: //2. copy beta's upper to alpha's
mcimadamore@1562: for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: uv.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha :> beta} propagate lower bounds
mcimadamore@1562: * from beta to alpha; also propagate upper bounds from alpha to beta.
mcimadamore@1562: */
mcimadamore@1562: PROP_LOWER() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: if (inferenceContext.inferenceVars().contains(b)) {
mcimadamore@1562: UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
mcimadamore@1562: //alpha :> beta
mcimadamore@1562: //1. copy alpha's upper to beta's
mcimadamore@1562: for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562: uv2.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
mcimadamore@1562: }
mcimadamore@1562: //2. copy beta's lower to alpha's
mcimadamore@1562: for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562: uv.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Given a bound set containing {@code alpha == beta} propagate lower/upper
mcimadamore@1562: * bounds from alpha to beta and back.
mcimadamore@1562: */
mcimadamore@1562: PROP_EQ() {
mcimadamore@1562: public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: for (Type b : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562: if (inferenceContext.inferenceVars().contains(b)) {
mcimadamore@1562: UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
mcimadamore@1562: //alpha == beta
mcimadamore@1562: //1. copy all alpha's bounds to beta's
mcimadamore@1562: for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562: for (Type b2 : uv.getBounds(ib)) {
mcimadamore@1562: if (b2 != uv2) {
mcimadamore@1562: uv2.addBound(ib, inferenceContext.asInstType(b2), infer.types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //2. copy all beta's bounds to alpha's
mcimadamore@1562: for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562: for (Type b2 : uv2.getBounds(ib)) {
mcimadamore@1562: if (b2 != uv) {
mcimadamore@1562: uv.addBound(ib, inferenceContext.asInstType(b2), infer.types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: };
mcimadamore@1562:
mcimadamore@1562: abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /** incorporation steps to be executed when running in legacy mode */
mcimadamore@1562: EnumSet incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
mcimadamore@1562:
mcimadamore@1562: /** incorporation steps to be executed when running in graph mode */
mcimadamore@1562: EnumSet incorporationStepsGraph =
mcimadamore@1562: EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Make sure that the upper bounds we got so far lead to a solvable inference
mcimadamore@1562: * variable by making sure that a glb exists.
mcimadamore@1562: */
mcimadamore@1562: void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: List hibounds =
mcimadamore@1562: Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
mcimadamore@1562: Type hb = null;
mcimadamore@1562: if (hibounds.isEmpty())
mcimadamore@1562: hb = syms.objectType;
mcimadamore@1562: else if (hibounds.tail.isEmpty())
mcimadamore@1562: hb = hibounds.head;
mcimadamore@1562: else
mcimadamore@1562: hb = types.glb(hibounds);
mcimadamore@1562: if (hb == null || hb.isErroneous())
mcimadamore@1562: reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1562: }
mcimadamore@1562: //where
mcimadamore@1562: protected static class BoundFilter implements Filter {
mcimadamore@1562:
mcimadamore@1562: InferenceContext inferenceContext;
mcimadamore@1562:
mcimadamore@1562: public BoundFilter(InferenceContext inferenceContext) {
mcimadamore@1562: this.inferenceContext = inferenceContext;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: @Override
mcimadamore@1562: public boolean accepts(Type t) {
mcimadamore@1562: return !t.isErroneous() && !inferenceContext.free(t) &&
mcimadamore@1562: !t.hasTag(BOT);
mcimadamore@1562: }
mcimadamore@1562: };
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This enumeration defines all possible bound-checking related errors.
mcimadamore@1562: */
mcimadamore@1562: enum BoundErrorKind {
mcimadamore@1562: /**
mcimadamore@1562: * The (uninstantiated) inference variable has incompatible upper bounds.
mcimadamore@1562: */
mcimadamore@1562: BAD_UPPER() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("incompatible.upper.bounds", uv.qtype,
mcimadamore@1562: uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * An equality constraint is not compatible with an upper bound.
mcimadamore@1562: */
mcimadamore@1562: BAD_EQ_UPPER() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
mcimadamore@1562: uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * An equality constraint is not compatible with a lower bound.
mcimadamore@1562: */
mcimadamore@1562: BAD_EQ_LOWER() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
mcimadamore@1562: uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Instantiated inference variable is not compatible with an upper bound.
mcimadamore@1562: */
mcimadamore@1562: UPPER() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
mcimadamore@1562: uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Instantiated inference variable is not compatible with a lower bound.
mcimadamore@1562: */
mcimadamore@1562: LOWER() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
mcimadamore@1562: uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Instantiated inference variable is not compatible with an equality constraint.
mcimadamore@1562: */
mcimadamore@1562: EQ() {
mcimadamore@1562: @Override
mcimadamore@1562: InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562: return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
mcimadamore@1562: uv.getBounds(InferenceBound.EQ));
mcimadamore@1562: }
mcimadamore@1562: };
mcimadamore@1562:
mcimadamore@1562: abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Report a bound-checking error of given kind
mcimadamore@1562: */
mcimadamore@1562: void reportBoundError(UndetVar uv, BoundErrorKind bk) {
mcimadamore@1562: throw bk.setMessage(inferenceException, uv);
mcimadamore@1562: }
mcimadamore@1562: //
mcimadamore@1562:
mcimadamore@1562: //
mcimadamore@1562: /**
mcimadamore@1562: * Graph inference strategy - act as an input to the inference solver; a strategy is
mcimadamore@1562: * composed of two ingredients: (i) find a node to solve in the inference graph,
mcimadamore@1562: * and (ii) tell th engine when we are done fixing inference variables
mcimadamore@1562: */
mcimadamore@1562: interface GraphStrategy {
mcimadamore@1562: /**
mcimadamore@1562: * Pick the next node (leaf) to solve in the graph
mcimadamore@1562: */
mcimadamore@1562: Node pickNode(InferenceGraph g);
mcimadamore@1562: /**
mcimadamore@1562: * Is this the last step?
mcimadamore@1562: */
mcimadamore@1562: boolean done();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Simple solver strategy class that locates all leaves inside a graph
mcimadamore@1562: * and picks the first leaf as the next node to solve
mcimadamore@1562: */
mcimadamore@1562: abstract class LeafSolver implements GraphStrategy {
mcimadamore@1562: public Node pickNode(InferenceGraph g) {
mcimadamore@1562: Assert.check(!g.nodes.isEmpty(), "No nodes to solve!");
mcimadamore@1562: return g.nodes.get(0);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This solver uses an heuristic to pick the best leaf - the heuristic
mcimadamore@1562: * tries to select the node that has maximal probability to contain one
mcimadamore@1562: * or more inference variables in a given list
mcimadamore@1562: */
mcimadamore@1562: abstract class BestLeafSolver extends LeafSolver {
mcimadamore@1562:
mcimadamore@1562: List varsToSolve;
mcimadamore@1562:
mcimadamore@1562: BestLeafSolver(List varsToSolve) {
mcimadamore@1562: this.varsToSolve = varsToSolve;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Computes the cost associated with a given node; the cost is computed
mcimadamore@1562: * as the total number of type-variables that should be eagerly instantiated
mcimadamore@1562: * in order to get to some of the variables in {@code varsToSolve} from
mcimadamore@1562: * a given node
mcimadamore@1562: */
mcimadamore@1562: void computeCostIfNeeded(Node n, Map costMap) {
mcimadamore@1562: if (costMap.containsKey(n)) {
mcimadamore@1562: return;
mcimadamore@1562: } else if (!Collections.disjoint(n.data, varsToSolve)) {
mcimadamore@1562: costMap.put(n, n.data.size());
mcimadamore@1562: } else {
mcimadamore@1562: int subcost = Integer.MAX_VALUE;
mcimadamore@1562: costMap.put(n, subcost); //avoid loops
mcimadamore@1562: for (Node n2 : n.getDependencies()) {
mcimadamore@1562: computeCostIfNeeded(n2, costMap);
mcimadamore@1562: subcost = Math.min(costMap.get(n2), subcost);
mcimadamore@1562: }
mcimadamore@1562: //update cost map to reflect real cost
mcimadamore@1562: costMap.put(n, subcost == Integer.MAX_VALUE ?
mcimadamore@1562: Integer.MAX_VALUE :
mcimadamore@1562: n.data.size() + subcost);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Pick the leaf that minimize cost
mcimadamore@1562: */
mcimadamore@1562: @Override
mcimadamore@1562: public Node pickNode(final InferenceGraph g) {
mcimadamore@1562: final Map costMap = new HashMap();
mcimadamore@1562: ArrayList leaves = new ArrayList();
mcimadamore@1562: for (Node n : g.nodes) {
mcimadamore@1562: computeCostIfNeeded(n, costMap);
mcimadamore@1562: if (n.isLeaf(n)) {
mcimadamore@1562: leaves.add(n);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: Assert.check(!leaves.isEmpty(), "No nodes to solve!");
mcimadamore@1562: Collections.sort(leaves, new java.util.Comparator() {
mcimadamore@1562: public int compare(Node n1, Node n2) {
mcimadamore@1562: return costMap.get(n1) - costMap.get(n2);
mcimadamore@1562: }
mcimadamore@1562: });
mcimadamore@1562: return leaves.get(0);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * The inference process can be thought of as a sequence of steps. Each step
mcimadamore@1562: * instantiates an inference variable using a subset of the inference variable
mcimadamore@1562: * bounds, if certain condition are met. Decisions such as the sequence in which
mcimadamore@1562: * steps are applied, or which steps are to be applied are left to the inference engine.
mcimadamore@1562: */
mcimadamore@1562: enum InferenceStep {
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Instantiate an inference variables using one of its (ground) equality
mcimadamore@1562: * constraints
mcimadamore@1562: */
mcimadamore@1562: EQ(InferenceBound.EQ) {
mcimadamore@1562: @Override
mcimadamore@1562: Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: return filterBounds(uv, inferenceContext).head;
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Instantiate an inference variables using its (ground) lower bounds. Such
mcimadamore@1562: * bounds are merged together using lub().
mcimadamore@1562: */
mcimadamore@1562: LOWER(InferenceBound.LOWER) {
mcimadamore@1562: @Override
mcimadamore@1562: Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: List lobounds = filterBounds(uv, inferenceContext);
mcimadamore@1562: Type owntype = infer.types.lub(lobounds);
mcimadamore@1562: if (owntype.hasTag(ERROR)) {
mcimadamore@1562: throw infer.inferenceException
mcimadamore@1562: .setMessage("no.unique.minimal.instance.exists",
mcimadamore@1562: uv.qtype, lobounds);
mcimadamore@1562: } else {
mcimadamore@1562: return owntype;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Instantiate an inference variables using its (ground) upper bounds. Such
mcimadamore@1562: * bounds are merged together using glb().
mcimadamore@1562: */
mcimadamore@1562: UPPER(InferenceBound.UPPER) {
mcimadamore@1562: @Override
mcimadamore@1562: Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: Infer infer = inferenceContext.infer();
mcimadamore@1562: List hibounds = filterBounds(uv, inferenceContext);
mcimadamore@1562: Type owntype = infer.types.glb(hibounds);
mcimadamore@1562: if (owntype.isErroneous()) {
mcimadamore@1562: throw infer.inferenceException
mcimadamore@1562: .setMessage("no.unique.maximal.instance.exists",
mcimadamore@1562: uv.qtype, hibounds);
mcimadamore@1562: } else {
mcimadamore@1562: return owntype;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: },
mcimadamore@1562: /**
mcimadamore@1562: * Like the former; the only difference is that this step can only be applied
mcimadamore@1562: * if all upper bounds are ground.
mcimadamore@1562: */
mcimadamore@1562: UPPER_LEGACY(InferenceBound.UPPER) {
mcimadamore@1562: @Override
mcimadamore@1562: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1562: return !inferenceContext.free(t.getBounds(ib));
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: @Override
mcimadamore@1562: Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: return UPPER.solve(uv, inferenceContext);
mcimadamore@1562: }
mcimadamore@1562: };
mcimadamore@1562:
mcimadamore@1562: final InferenceBound ib;
mcimadamore@1562:
mcimadamore@1562: InferenceStep(InferenceBound ib) {
mcimadamore@1562: this.ib = ib;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Find an instantiated type for a given inference variable within
mcimadamore@1562: * a given inference context
mcimadamore@1562: */
mcimadamore@1562: abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Can the inference variable be instantiated using this step?
mcimadamore@1562: */
mcimadamore@1562: public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1562: return filterBounds(t, inferenceContext).nonEmpty();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
mcimadamore@1562: */
mcimadamore@1562: List filterBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562: return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562: * solver works in legacy mode. The steps in this enumeration reflect
mcimadamore@1562: * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562: */
mcimadamore@1562: enum LegacyInferenceSteps {
mcimadamore@1562:
mcimadamore@1562: EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1562: EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
mcimadamore@1562:
mcimadamore@1562: final EnumSet steps;
mcimadamore@1562:
mcimadamore@1562: LegacyInferenceSteps(EnumSet steps) {
mcimadamore@1562: this.steps = steps;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562: * graph solver is used. This order is defined so as to maximize compatibility
mcimadamore@1562: * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562: */
mcimadamore@1562: enum GraphInferenceSteps {
mcimadamore@1562:
mcimadamore@1562: EQ(EnumSet.of(InferenceStep.EQ)),
mcimadamore@1562: EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1562: EQ_LOWER_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER));
mcimadamore@1562:
mcimadamore@1562: final EnumSet steps;
mcimadamore@1562:
mcimadamore@1562: GraphInferenceSteps(EnumSet steps) {
mcimadamore@1562: this.steps = steps;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This is the graph inference solver - the solver organizes all inference variables in
mcimadamore@1562: * a given inference context by bound dependencies - in the general case, such dependencies
mcimadamore@1562: * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
mcimadamore@1562: * an acyclic graph, where all cyclic variables are bundled together. An inference
mcimadamore@1562: * step corresponds to solving a node in the acyclic graph - this is done by
mcimadamore@1562: * relying on a given strategy (see GraphStrategy).
mcimadamore@1562: */
mcimadamore@1562: class GraphSolver {
mcimadamore@1562:
mcimadamore@1562: InferenceContext inferenceContext;
mcimadamore@1562: Warner warn;
mcimadamore@1562:
mcimadamore@1562: GraphSolver(InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562: this.inferenceContext = inferenceContext;
mcimadamore@1562: this.warn = warn;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Solve variables in a given inference context. The amount of variables
mcimadamore@1562: * to be solved, and the way in which the underlying acyclic graph is explored
mcimadamore@1562: * depends on the selected solver strategy.
mcimadamore@1562: */
mcimadamore@1562: void solve(GraphStrategy sstrategy) {
mcimadamore@1562: checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
mcimadamore@1562: InferenceGraph inferenceGraph = new InferenceGraph();
mcimadamore@1562: while (!sstrategy.done()) {
mcimadamore@1562: InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
mcimadamore@1562: List varsToSolve = List.from(nodeToSolve.data);
mcimadamore@1562: inferenceContext.save();
mcimadamore@1562: try {
mcimadamore@1562: //repeat until all variables are solved
mcimadamore@1562: outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
mcimadamore@1562: //for each inference phase
mcimadamore@1562: for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
mcimadamore@1562: if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
mcimadamore@1562: checkWithinBounds(inferenceContext, warn);
mcimadamore@1562: continue outer;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //no progress
mcimadamore@1562: throw inferenceException;
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: catch (InferenceException ex) {
mcimadamore@1562: inferenceContext.rollback();
mcimadamore@1562: instantiateAsUninferredVars(varsToSolve, inferenceContext);
mcimadamore@1562: checkWithinBounds(inferenceContext, warn);
mcimadamore@1562: }
mcimadamore@1562: inferenceGraph.deleteNode(nodeToSolve);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * The dependencies between the inference variables that need to be solved
mcimadamore@1562: * form a (possibly cyclic) graph. This class reduces the original dependency graph
mcimadamore@1562: * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
mcimadamore@1562: */
mcimadamore@1562: class InferenceGraph {
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * This class represents a node in the graph. Each node corresponds
mcimadamore@1562: * to an inference variable and has edges (dependencies) on other
mcimadamore@1562: * nodes. The node defines an entry point that can be used to receive
mcimadamore@1562: * updates on the structure of the graph this node belongs to (used to
mcimadamore@1562: * keep dependencies in sync).
mcimadamore@1562: */
mcimadamore@1562: class Node extends GraphUtils.TarjanNode> {
mcimadamore@1562:
mcimadamore@1562: Set deps;
mcimadamore@1562:
mcimadamore@1562: Node(Type ivar) {
mcimadamore@1562: super(ListBuffer.of(ivar));
mcimadamore@1562: this.deps = new HashSet();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: @Override
mcimadamore@1562: public Iterable extends Node> getDependencies() {
mcimadamore@1562: return deps;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: @Override
mcimadamore@1562: public String printDependency(GraphUtils.Node> to) {
mcimadamore@1562: StringBuilder buf = new StringBuilder();
mcimadamore@1562: String sep = "";
mcimadamore@1562: for (Type from : data) {
mcimadamore@1562: UndetVar uv = (UndetVar)inferenceContext.asFree(from);
mcimadamore@1562: for (Type bound : uv.getBounds(InferenceBound.values())) {
mcimadamore@1562: if (bound.containsAny(List.from(to.data))) {
mcimadamore@1562: buf.append(sep);
mcimadamore@1562: buf.append(bound);
mcimadamore@1562: sep = ",";
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: return buf.toString();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: boolean isLeaf(Node n) {
mcimadamore@1562: //no deps, or only one self dep
mcimadamore@1562: return (n.deps.isEmpty() ||
mcimadamore@1562: n.deps.size() == 1 && n.deps.contains(n));
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: void mergeWith(List extends Node> nodes) {
mcimadamore@1562: for (Node n : nodes) {
mcimadamore@1562: Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
mcimadamore@1562: data.appendList(n.data);
mcimadamore@1562: deps.addAll(n.deps);
mcimadamore@1562: }
mcimadamore@1562: //update deps
mcimadamore@1562: Set deps2 = new HashSet();
mcimadamore@1562: for (Node d : deps) {
mcimadamore@1562: if (data.contains(d.data.first())) {
mcimadamore@1562: deps2.add(this);
mcimadamore@1562: } else {
mcimadamore@1562: deps2.add(d);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: deps = deps2;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: void graphChanged(Node from, Node to) {
mcimadamore@1562: if (deps.contains(from)) {
mcimadamore@1562: deps.remove(from);
mcimadamore@1562: if (to != null) {
mcimadamore@1562: deps.add(to);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /** the nodes in the inference graph */
mcimadamore@1562: ArrayList nodes;
mcimadamore@1562:
mcimadamore@1562: InferenceGraph() {
mcimadamore@1562: initNodes();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Delete a node from the graph. This update the underlying structure
mcimadamore@1562: * of the graph (including dependencies) via listeners updates.
mcimadamore@1562: */
mcimadamore@1562: public void deleteNode(Node n) {
mcimadamore@1562: Assert.check(nodes.contains(n));
mcimadamore@1562: nodes.remove(n);
mcimadamore@1562: notifyUpdate(n, null);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Notify all nodes of a change in the graph. If the target node is
mcimadamore@1562: * {@code null} the source node is assumed to be removed.
mcimadamore@1562: */
mcimadamore@1562: void notifyUpdate(Node from, Node to) {
mcimadamore@1562: for (Node n : nodes) {
mcimadamore@1562: n.graphChanged(from, to);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Create the graph nodes. First a simple node is created for every inference
mcimadamore@1562: * variables to be solved. Then Tarjan is used to found all connected components
mcimadamore@1562: * in the graph. For each component containing more than one node, a super node is
mcimadamore@1562: * created, effectively replacing the original cyclic nodes.
mcimadamore@1562: */
mcimadamore@1562: void initNodes() {
mcimadamore@1562: ArrayList nodes = new ArrayList();
mcimadamore@1562: for (Type t : inferenceContext.restvars()) {
mcimadamore@1562: nodes.add(new Node(t));
mcimadamore@1562: }
mcimadamore@1562: for (Node n_i : nodes) {
mcimadamore@1562: Type i = n_i.data.first();
mcimadamore@1562: for (Node n_j : nodes) {
mcimadamore@1562: Type j = n_j.data.first();
mcimadamore@1562: UndetVar uv_i = (UndetVar)inferenceContext.asFree(i);
mcimadamore@1562: if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
mcimadamore@1562: //update i's deps
mcimadamore@1562: n_i.deps.add(n_j);
mcimadamore@1562: //update j's deps - only if i's bounds contain _exactly_ j
mcimadamore@1562: if (uv_i.getBounds(InferenceBound.values()).contains(j)) {
mcimadamore@1562: n_j.deps.add(n_i);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: this.nodes = new ArrayList();
mcimadamore@1562: for (List extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
mcimadamore@1562: if (conSubGraph.length() > 1) {
mcimadamore@1562: Node root = conSubGraph.head;
mcimadamore@1562: root.mergeWith(conSubGraph.tail);
mcimadamore@1562: for (Node n : conSubGraph) {
mcimadamore@1562: notifyUpdate(n, root);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: this.nodes.add(conSubGraph.head);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Debugging: dot representation of this graph
mcimadamore@1562: */
mcimadamore@1562: String toDot() {
mcimadamore@1562: StringBuilder buf = new StringBuilder();
mcimadamore@1562: for (Type t : inferenceContext.undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
mcimadamore@1562: uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
mcimadamore@1562: uv.getBounds(InferenceBound.EQ)));
mcimadamore@1562: }
mcimadamore@1562: return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: //
mcimadamore@1562:
mcimadamore@1562: //
mcimadamore@1562: /**
mcimadamore@1550: * Functional interface for defining inference callbacks. Certain actions
mcimadamore@1550: * (i.e. subtyping checks) might need to be redone after all inference variables
mcimadamore@1550: * have been fixed.
mcimadamore@1337: */
mcimadamore@1550: interface FreeTypeListener {
mcimadamore@1550: void typesInferred(InferenceContext inferenceContext);
mcimadamore@1550: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * An inference context keeps track of the set of variables that are free
mcimadamore@1337: * in the current context. It provides utility methods for opening/closing
mcimadamore@1337: * types to their corresponding free/closed forms. It also provide hooks for
mcimadamore@1337: * attaching deferred post-inference action (see PendingCheck). Finally,
mcimadamore@1337: * it can be used as an entry point for performing upper/lower bound inference
mcimadamore@1337: * (see InferenceKind).
mcimadamore@1337: */
mcimadamore@1562: class InferenceContext {
mcimadamore@1337:
mcimadamore@1337: /** list of inference vars as undet vars */
mcimadamore@1337: List undetvars;
mcimadamore@1337:
mcimadamore@1337: /** list of inference vars in this context */
mcimadamore@1337: List inferencevars;
mcimadamore@1337:
mcimadamore@1562: /** backed up inference variables */
mcimadamore@1562: List saved_undet;
mcimadamore@1562:
mcimadamore@1337: java.util.Map> freeTypeListeners =
mcimadamore@1337: new java.util.HashMap>();
mcimadamore@1337:
mcimadamore@1337: List freetypeListeners = List.nil();
mcimadamore@1337:
mcimadamore@1550: public InferenceContext(List inferencevars) {
mcimadamore@1550: this.undetvars = Type.map(inferencevars, fromTypeVarFun);
mcimadamore@1337: this.inferencevars = inferencevars;
mcimadamore@1337: }
mcimadamore@1550: //where
mcimadamore@1550: Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
mcimadamore@1550: // mapping that turns inference variables into undet vars
mcimadamore@1550: public Type apply(Type t) {
mcimadamore@1550: if (t.hasTag(TYPEVAR)) return new UndetVar((TypeVar)t, types);
mcimadamore@1550: else return t.map(this);
mcimadamore@1550: }
mcimadamore@1550: };
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * returns the list of free variables (as type-variables) in this
mcimadamore@1337: * inference context
mcimadamore@1337: */
mcimadamore@1337: List inferenceVars() {
mcimadamore@1337: return inferencevars;
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * returns the list of uninstantiated variables (as type-variables) in this
mcimadamore@1550: * inference context
mcimadamore@1337: */
mcimadamore@1337: List restvars() {
mcimadamore@1550: return filterVars(new Filter() {
mcimadamore@1550: public boolean accepts(UndetVar uv) {
mcimadamore@1550: return uv.inst == null;
mcimadamore@1337: }
mcimadamore@1550: });
mcimadamore@1550: }
mcimadamore@1550:
mcimadamore@1550: /**
mcimadamore@1550: * returns the list of instantiated variables (as type-variables) in this
mcimadamore@1550: * inference context
mcimadamore@1550: */
mcimadamore@1550: List instvars() {
mcimadamore@1550: return filterVars(new Filter() {
mcimadamore@1550: public boolean accepts(UndetVar uv) {
mcimadamore@1550: return uv.inst != null;
mcimadamore@1550: }
mcimadamore@1550: });
mcimadamore@1550: }
mcimadamore@1550:
mcimadamore@1550: /**
mcimadamore@1550: * Get list of bounded inference variables (where bound is other than
mcimadamore@1550: * declared bounds).
mcimadamore@1550: */
mcimadamore@1550: final List boundedVars() {
mcimadamore@1550: return filterVars(new Filter() {
mcimadamore@1550: public boolean accepts(UndetVar uv) {
mcimadamore@1550: return uv.getBounds(InferenceBound.UPPER)
mcimadamore@1550: .diff(uv.getDeclaredBounds())
mcimadamore@1550: .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
mcimadamore@1550: }
mcimadamore@1550: });
mcimadamore@1550: }
mcimadamore@1550:
mcimadamore@1550: private List filterVars(Filter fu) {
mcimadamore@1550: ListBuffer res = ListBuffer.lb();
mcimadamore@1550: for (Type t : undetvars) {
mcimadamore@1550: UndetVar uv = (UndetVar)t;
mcimadamore@1550: if (fu.accepts(uv)) {
mcimadamore@1550: res.append(uv.qtype);
mcimadamore@1550: }
mcimadamore@1337: }
mcimadamore@1550: return res.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * is this type free?
mcimadamore@1337: */
mcimadamore@1337: final boolean free(Type t) {
mcimadamore@1337: return t.containsAny(inferencevars);
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: final boolean free(List ts) {
mcimadamore@1337: for (Type t : ts) {
mcimadamore@1337: if (free(t)) return true;
mcimadamore@1337: }
mcimadamore@1337: return false;
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * Returns a list of free variables in a given type
mcimadamore@1337: */
mcimadamore@1337: final List freeVarsIn(Type t) {
mcimadamore@1337: ListBuffer buf = ListBuffer.lb();
mcimadamore@1337: for (Type iv : inferenceVars()) {
mcimadamore@1337: if (t.contains(iv)) {
mcimadamore@1337: buf.add(iv);
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1337: return buf.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: final List freeVarsIn(List ts) {
mcimadamore@1337: ListBuffer buf = ListBuffer.lb();
mcimadamore@1337: for (Type t : ts) {
mcimadamore@1337: buf.appendList(freeVarsIn(t));
mcimadamore@1337: }
mcimadamore@1337: ListBuffer buf2 = ListBuffer.lb();
mcimadamore@1337: for (Type t : buf) {
mcimadamore@1337: if (!buf2.contains(t)) {
mcimadamore@1337: buf2.add(t);
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1337: return buf2.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * Replace all free variables in a given type with corresponding
mcimadamore@1337: * undet vars (used ahead of subtyping/compatibility checks to allow propagation
mcimadamore@1337: * of inference constraints).
mcimadamore@1337: */
mcimadamore@1550: final Type asFree(Type t) {
mcimadamore@1337: return types.subst(t, inferencevars, undetvars);
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1550: final List asFree(List ts) {
mcimadamore@1337: ListBuffer buf = ListBuffer.lb();
mcimadamore@1337: for (Type t : ts) {
mcimadamore@1550: buf.append(asFree(t));
mcimadamore@1337: }
mcimadamore@1337: return buf.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: List instTypes() {
mcimadamore@1337: ListBuffer buf = ListBuffer.lb();
mcimadamore@1337: for (Type t : undetvars) {
mcimadamore@1337: UndetVar uv = (UndetVar)t;
mcimadamore@1337: buf.append(uv.inst != null ? uv.inst : uv.qtype);
mcimadamore@1337: }
mcimadamore@1337: return buf.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * Replace all free variables in a given type with corresponding
mcimadamore@1337: * instantiated types - if one or more free variable has not been
mcimadamore@1337: * fully instantiated, it will still be available in the resulting type.
mcimadamore@1337: */
mcimadamore@1550: Type asInstType(Type t) {
mcimadamore@1337: return types.subst(t, inferencevars, instTypes());
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1550: List asInstTypes(List ts) {
mcimadamore@1337: ListBuffer buf = ListBuffer.lb();
mcimadamore@1337: for (Type t : ts) {
mcimadamore@1550: buf.append(asInstType(t));
mcimadamore@1337: }
mcimadamore@1337: return buf.toList();
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * Add custom hook for performing post-inference action
mcimadamore@1337: */
mcimadamore@1337: void addFreeTypeListener(List types, FreeTypeListener ftl) {
mcimadamore@1337: freeTypeListeners.put(ftl, freeVarsIn(types));
mcimadamore@1337: }
mcimadamore@1337:
mcimadamore@1337: /**
mcimadamore@1337: * Mark the inference context as complete and trigger evaluation
mcimadamore@1337: * of all deferred checks.
mcimadamore@1337: */
mcimadamore@1550: void notifyChange() {
mcimadamore@1562: notifyChange(inferencevars.diff(restvars()));
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: void notifyChange(List inferredVars) {
mcimadamore@1337: InferenceException thrownEx = null;
mcimadamore@1337: for (Map.Entry> entry :
mcimadamore@1337: new HashMap>(freeTypeListeners).entrySet()) {
mcimadamore@1562: if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
mcimadamore@1337: try {
mcimadamore@1337: entry.getKey().typesInferred(this);
mcimadamore@1337: freeTypeListeners.remove(entry.getKey());
mcimadamore@1337: } catch (InferenceException ex) {
mcimadamore@1337: if (thrownEx == null) {
mcimadamore@1337: thrownEx = ex;
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1337: //inference exception multiplexing - present any inference exception
mcimadamore@1337: //thrown when processing listeners as a single one
mcimadamore@1337: if (thrownEx != null) {
mcimadamore@1337: throw thrownEx;
mcimadamore@1337: }
mcimadamore@1337: }
mcimadamore@1347:
mcimadamore@1562: /**
mcimadamore@1562: * Save the state of this inference context
mcimadamore@1562: */
mcimadamore@1562: void save() {
mcimadamore@1562: ListBuffer buf = ListBuffer.lb();
mcimadamore@1562: for (Type t : undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
mcimadamore@1562: for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562: for (Type b : uv.getBounds(ib)) {
mcimadamore@1562: uv2.addBound(ib, b, types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562: uv2.inst = uv.inst;
mcimadamore@1562: buf.add(uv2);
mcimadamore@1562: }
mcimadamore@1562: saved_undet = buf.toList();
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Restore the state of this inference context to the previous known checkpoint
mcimadamore@1562: */
mcimadamore@1562: void rollback() {
mcimadamore@1562: Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
mcimadamore@1562: undetvars = saved_undet;
mcimadamore@1562: saved_undet = null;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Copy variable in this inference context to the given context
mcimadamore@1562: */
mcimadamore@1562: void dupTo(final InferenceContext that) {
mcimadamore@1562: that.inferencevars = that.inferencevars.appendList(inferencevars);
mcimadamore@1562: that.undetvars = that.undetvars.appendList(undetvars);
mcimadamore@1562: //set up listeners to notify original inference contexts as
mcimadamore@1562: //propagated vars are inferred in new context
mcimadamore@1562: for (Type t : inferencevars) {
mcimadamore@1562: that.freeTypeListeners.put(new FreeTypeListener() {
mcimadamore@1562: public void typesInferred(InferenceContext inferenceContext) {
mcimadamore@1562: InferenceContext.this.notifyChange();
mcimadamore@1562: }
mcimadamore@1562: }, List.of(t));
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Solve with given graph strategy.
mcimadamore@1562: */
mcimadamore@1562: private void solve(GraphStrategy ss, Warner warn) {
mcimadamore@1562: GraphSolver s = new GraphSolver(this, warn);
mcimadamore@1562: s.solve(ss);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Solve all variables in this context.
mcimadamore@1562: */
mcimadamore@1562: public void solve(Warner warn) {
mcimadamore@1562: solve(new LeafSolver() {
mcimadamore@1562: public boolean done() {
mcimadamore@1562: return restvars().isEmpty();
mcimadamore@1562: }
mcimadamore@1562: }, warn);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Solve all variables in the given list.
mcimadamore@1562: */
mcimadamore@1562: public void solve(final List vars, Warner warn) {
mcimadamore@1562: solve(new BestLeafSolver(vars) {
mcimadamore@1562: public boolean done() {
mcimadamore@1562: return !free(asInstTypes(vars));
mcimadamore@1562: }
mcimadamore@1562: }, warn);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Solve at least one variable in given list.
mcimadamore@1562: */
mcimadamore@1562: public void solveAny(List varsToSolve, Warner warn) {
mcimadamore@1562: checkWithinBounds(this, warn); //propagate bounds
mcimadamore@1562: List boundedVars = boundedVars().intersect(restvars()).intersect(varsToSolve);
mcimadamore@1562: if (boundedVars.isEmpty()) {
mcimadamore@1562: throw inferenceException.setMessage("cyclic.inference",
mcimadamore@1562: freeVarsIn(varsToSolve));
mcimadamore@1562: }
mcimadamore@1562: solve(new BestLeafSolver(boundedVars) {
mcimadamore@1562: public boolean done() {
mcimadamore@1562: return instvars().intersect(varsToSolve).nonEmpty();
mcimadamore@1562: }
mcimadamore@1562: }, warn);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Apply a set of inference steps
mcimadamore@1562: */
mcimadamore@1562: private boolean solveBasic(EnumSet steps) {
mcimadamore@1562: return solveBasic(inferencevars, steps);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: private boolean solveBasic(List varsToSolve, EnumSet steps) {
mcimadamore@1562: boolean changed = false;
mcimadamore@1562: for (Type t : varsToSolve.intersect(restvars())) {
mcimadamore@1550: UndetVar uv = (UndetVar)asFree(t);
mcimadamore@1562: for (InferenceStep step : steps) {
mcimadamore@1562: if (step.accepts(uv, this)) {
mcimadamore@1562: uv.inst = step.solve(uv, this);
mcimadamore@1562: changed = true;
mcimadamore@1562: break;
mcimadamore@1347: }
mcimadamore@1347: }
mcimadamore@1347: }
mcimadamore@1562: return changed;
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: /**
mcimadamore@1562: * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
mcimadamore@1562: * During overload resolution, instantiation is done by doing a partial
mcimadamore@1562: * inference process using eq/lower bound instantiation. During check,
mcimadamore@1562: * we also instantiate any remaining vars by repeatedly using eq/upper
mcimadamore@1562: * instantiation, until all variables are solved.
mcimadamore@1562: */
mcimadamore@1562: public void solveLegacy(boolean partial, Warner warn, EnumSet steps) {
mcimadamore@1562: while (true) {
mcimadamore@1562: boolean stuck = !solveBasic(steps);
mcimadamore@1562: if (restvars().isEmpty() || partial) {
mcimadamore@1562: //all variables have been instantiated - exit
mcimadamore@1562: break;
mcimadamore@1562: } else if (stuck) {
mcimadamore@1562: //some variables could not be instantiated because of cycles in
mcimadamore@1562: //upper bounds - provide a (possibly recursive) default instantiation
mcimadamore@1562: instantiateAsUninferredVars(restvars(), this);
mcimadamore@1562: break;
mcimadamore@1562: } else {
mcimadamore@1562: //some variables have been instantiated - replace newly instantiated
mcimadamore@1562: //variables in remaining upper bounds and continue
mcimadamore@1562: for (Type t : undetvars) {
mcimadamore@1562: UndetVar uv = (UndetVar)t;
mcimadamore@1562: uv.substBounds(inferenceVars(), instTypes(), types);
mcimadamore@1562: }
mcimadamore@1562: }
mcimadamore@1347: }
mcimadamore@1562: checkWithinBounds(this, warn);
mcimadamore@1562: }
mcimadamore@1562:
mcimadamore@1562: private Infer infer() {
mcimadamore@1562: //back-door to infer
mcimadamore@1562: return Infer.this;
mcimadamore@1347: }
mcimadamore@895: }
mcimadamore@1337:
mcimadamore@1550: final InferenceContext emptyContext = new InferenceContext(List.nil());
mcimadamore@1550: //
mcimadamore@1337: }