src/share/classes/com/sun/tools/javac/comp/Infer.java

Fri, 02 May 2014 01:25:26 +0100

author
vromero
date
Fri, 02 May 2014 01:25:26 +0100
changeset 2382
14979dd5e034
parent 2369
77352397867a
child 2384
327122b01a9e
permissions
-rw-r--r--

8030741: Inference: implement eager resolution of return types, consistent with JDK-8028800
Reviewed-by: dlsmith, jjg

duke@1 1 /*
vromero@2302 2 * Copyright (c) 1999, 2014, Oracle and/or its affiliates. All rights reserved.
duke@1 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1 4 *
duke@1 5 * This code is free software; you can redistribute it and/or modify it
duke@1 6 * under the terms of the GNU General Public License version 2 only, as
ohair@554 7 * published by the Free Software Foundation. Oracle designates this
duke@1 8 * particular file as subject to the "Classpath" exception as provided
ohair@554 9 * by Oracle in the LICENSE file that accompanied this code.
duke@1 10 *
duke@1 11 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1 14 * version 2 for more details (a copy is included in the LICENSE file that
duke@1 15 * accompanied this code).
duke@1 16 *
duke@1 17 * You should have received a copy of the GNU General Public License version
duke@1 18 * 2 along with this work; if not, write to the Free Software Foundation,
duke@1 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1 20 *
ohair@554 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@554 22 * or visit www.oracle.com if you need additional information or have any
ohair@554 23 * questions.
duke@1 24 */
duke@1 25
duke@1 26 package com.sun.tools.javac.comp;
duke@1 27
mcimadamore@674 28 import com.sun.tools.javac.tree.JCTree;
mcimadamore@674 29 import com.sun.tools.javac.tree.JCTree.JCTypeCast;
mcimadamore@820 30 import com.sun.tools.javac.tree.TreeInfo;
duke@1 31 import com.sun.tools.javac.util.*;
mcimadamore@1562 32 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
duke@1 33 import com.sun.tools.javac.util.List;
mcimadamore@1562 34 import com.sun.tools.javac.code.*;
mcimadamore@1562 35 import com.sun.tools.javac.code.Type.*;
mcimadamore@1562 36 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
mcimadamore@1562 37 import com.sun.tools.javac.code.Symbol.*;
mcimadamore@1562 38 import com.sun.tools.javac.comp.DeferredAttr.AttrMode;
mcimadamore@1562 39 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
mcimadamore@1562 40 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node;
mcimadamore@1562 41 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
mcimadamore@1562 42 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
vromero@2000 43 import com.sun.tools.javac.util.GraphUtils.TarjanNode;
mcimadamore@1562 44
mcimadamore@1562 45 import java.util.ArrayList;
mcimadamore@1562 46 import java.util.Collections;
vromero@2000 47 import java.util.EnumMap;
mcimadamore@1562 48 import java.util.EnumSet;
vromero@2000 49 import java.util.HashMap;
mcimadamore@1562 50 import java.util.HashSet;
vromero@2000 51 import java.util.LinkedHashSet;
vromero@2000 52 import java.util.Map;
vromero@2000 53 import java.util.Set;
mcimadamore@1337 54
jjg@1374 55 import static com.sun.tools.javac.code.TypeTag.*;
duke@1 56
duke@1 57 /** Helper class for type parameter inference, used by the attribution phase.
duke@1 58 *
jjg@581 59 * <p><b>This is NOT part of any supported API.
jjg@581 60 * If you write code that depends on this, you do so at your own risk.
duke@1 61 * This code and its internal interfaces are subject to change or
duke@1 62 * deletion without notice.</b>
duke@1 63 */
duke@1 64 public class Infer {
duke@1 65 protected static final Context.Key<Infer> inferKey =
duke@1 66 new Context.Key<Infer>();
duke@1 67
mcimadamore@1562 68 Resolve rs;
mcimadamore@1562 69 Check chk;
duke@1 70 Symtab syms;
duke@1 71 Types types;
mcimadamore@1562 72 JCDiagnostic.Factory diags;
mcimadamore@1114 73 Log log;
duke@1 74
mcimadamore@1562 75 /** should the graph solver be used? */
mcimadamore@1562 76 boolean allowGraphInference;
mcimadamore@1510 77
duke@1 78 public static Infer instance(Context context) {
duke@1 79 Infer instance = context.get(inferKey);
duke@1 80 if (instance == null)
duke@1 81 instance = new Infer(context);
duke@1 82 return instance;
duke@1 83 }
duke@1 84
duke@1 85 protected Infer(Context context) {
duke@1 86 context.put(inferKey, this);
mcimadamore@1562 87
mcimadamore@1562 88 rs = Resolve.instance(context);
mcimadamore@1562 89 chk = Check.instance(context);
duke@1 90 syms = Symtab.instance(context);
duke@1 91 types = Types.instance(context);
mcimadamore@1562 92 diags = JCDiagnostic.Factory.instance(context);
mcimadamore@1114 93 log = Log.instance(context);
mcimadamore@1298 94 inferenceException = new InferenceException(diags);
mcimadamore@1562 95 Options options = Options.instance(context);
mcimadamore@1562 96 allowGraphInference = Source.instance(context).allowGraphInference()
mcimadamore@1562 97 && options.isUnset("useLegacyInference");
duke@1 98 }
duke@1 99
mcimadamore@1562 100 /** A value for prototypes that admit any type, including polymorphic ones. */
vromero@1853 101 public static final Type anyPoly = new JCNoType();
mcimadamore@1562 102
mcimadamore@1337 103 /**
mcimadamore@1337 104 * This exception class is design to store a list of diagnostics corresponding
mcimadamore@1337 105 * to inference errors that can arise during a method applicability check.
mcimadamore@1337 106 */
mcimadamore@1186 107 public static class InferenceException extends InapplicableMethodException {
duke@1 108 private static final long serialVersionUID = 0;
duke@1 109
mcimadamore@1337 110 List<JCDiagnostic> messages = List.nil();
mcimadamore@1337 111
mcimadamore@299 112 InferenceException(JCDiagnostic.Factory diags) {
mcimadamore@689 113 super(diags);
duke@1 114 }
mcimadamore@1337 115
mcimadamore@1337 116 @Override
vromero@2000 117 InapplicableMethodException setMessage() {
vromero@2000 118 //no message to set
vromero@2000 119 return this;
vromero@2000 120 }
vromero@2000 121
vromero@2000 122 @Override
mcimadamore@1337 123 InapplicableMethodException setMessage(JCDiagnostic diag) {
mcimadamore@1337 124 messages = messages.append(diag);
mcimadamore@1337 125 return this;
mcimadamore@1337 126 }
mcimadamore@1337 127
mcimadamore@1337 128 @Override
mcimadamore@1337 129 public JCDiagnostic getDiagnostic() {
mcimadamore@1337 130 return messages.head;
mcimadamore@1337 131 }
mcimadamore@1337 132
mcimadamore@1337 133 void clear() {
mcimadamore@1337 134 messages = List.nil();
mcimadamore@1337 135 }
mcimadamore@299 136 }
mcimadamore@299 137
mcimadamore@1562 138 protected final InferenceException inferenceException;
duke@1 139
mcimadamore@1562 140 // <editor-fold defaultstate="collapsed" desc="Inference routines">
mcimadamore@1337 141 /**
mcimadamore@1562 142 * Main inference entry point - instantiate a generic method type
mcimadamore@1562 143 * using given argument types and (possibly) an expected target-type.
duke@1 144 */
vromero@2382 145 Type instantiateMethod( Env<AttrContext> env,
vromero@2382 146 List<Type> tvars,
vromero@2382 147 MethodType mt,
vromero@2382 148 Attr.ResultInfo resultInfo,
vromero@2382 149 MethodSymbol msym,
vromero@2382 150 List<Type> argtypes,
vromero@2382 151 boolean allowBoxing,
vromero@2382 152 boolean useVarargs,
vromero@2382 153 Resolve.MethodResolutionContext resolveContext,
vromero@2382 154 Warner warn) throws InferenceException {
duke@1 155 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
vromero@2382 156 final InferenceContext inferenceContext = new InferenceContext(tvars); //B0
mcimadamore@1337 157 inferenceException.clear();
mcimadamore@1562 158 try {
mcimadamore@1562 159 DeferredAttr.DeferredAttrContext deferredAttrContext =
mcimadamore@1897 160 resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
mcimadamore@689 161
vromero@2382 162 resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2
mcimadamore@1562 163 argtypes, mt.getParameterTypes(), warn);
mcimadamore@1479 164
mcimadamore@1562 165 if (allowGraphInference &&
mcimadamore@1562 166 resultInfo != null &&
mcimadamore@1510 167 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
mcimadamore@1562 168 //inject return constraints earlier
mcimadamore@1562 169 checkWithinBounds(inferenceContext, warn); //propagation
vromero@2382 170 Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3
vromero@2382 171 mt, inferenceContext);
mcimadamore@1898 172 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
mcimadamore@1562 173 //propagate outwards if needed
mcimadamore@1562 174 if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
mcimadamore@1562 175 //propagate inference context outwards and exit
mcimadamore@1562 176 inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
mcimadamore@1562 177 deferredAttrContext.complete();
mcimadamore@1562 178 return mt;
mcimadamore@1562 179 }
mcimadamore@1510 180 }
mcimadamore@1510 181
mcimadamore@1479 182 deferredAttrContext.complete();
duke@1 183
mcimadamore@1337 184 // minimize as yet undetermined type variables
mcimadamore@1562 185 if (allowGraphInference) {
mcimadamore@1562 186 inferenceContext.solve(warn);
mcimadamore@1562 187 } else {
mcimadamore@1562 188 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
mcimadamore@1337 189 }
duke@1 190
mcimadamore@1550 191 mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@396 192
mcimadamore@1562 193 if (!allowGraphInference &&
mcimadamore@1562 194 inferenceContext.restvars().nonEmpty() &&
mcimadamore@1562 195 resultInfo != null &&
mcimadamore@1562 196 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
vromero@2382 197 generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext);
mcimadamore@1562 198 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
mcimadamore@1562 199 mt = (MethodType)inferenceContext.asInstType(mt);
mcimadamore@1562 200 }
duke@1 201
mcimadamore@1562 202 if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
mcimadamore@1562 203 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
mcimadamore@1337 204 }
duke@1 205
mcimadamore@1337 206 // return instantiated version of method type
mcimadamore@1337 207 return mt;
mcimadamore@1337 208 } finally {
mcimadamore@1562 209 if (resultInfo != null || !allowGraphInference) {
mcimadamore@1562 210 inferenceContext.notifyChange();
mcimadamore@1562 211 } else {
mcimadamore@1562 212 inferenceContext.notifyChange(inferenceContext.boundedVars());
mcimadamore@1338 213 }
vromero@2382 214 if (resultInfo == null) {
vromero@2382 215 /* if the is no result info then we can clear the capture types
vromero@2382 216 * cache without affecting any result info check
vromero@2382 217 */
vromero@2382 218 inferenceContext.captureTypeCache.clear();
vromero@2382 219 }
duke@1 220 }
mcimadamore@895 221 }
duke@1 222
mcimadamore@1562 223 /**
mcimadamore@1562 224 * Generate constraints from the generic method's return type. If the method
mcimadamore@1562 225 * call occurs in a context where a type T is expected, use the expected
mcimadamore@1562 226 * type to derive more constraints on the generic method inference variables.
mcimadamore@1562 227 */
vromero@2382 228 Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo,
mcimadamore@1562 229 MethodType mt, InferenceContext inferenceContext) {
vromero@2368 230 InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext();
mcimadamore@1898 231 Type from = mt.getReturnType();
mcimadamore@1898 232 if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
vromero@2368 233 rsInfoInfContext != emptyContext) {
mcimadamore@1898 234 from = types.capture(from);
mcimadamore@1898 235 //add synthetic captured ivars
mcimadamore@1898 236 for (Type t : from.getTypeArguments()) {
mcimadamore@1898 237 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
mcimadamore@1898 238 inferenceContext.addVar((TypeVar)t);
mcimadamore@1898 239 }
mcimadamore@1898 240 }
mcimadamore@1898 241 }
vromero@2382 242 Type qtype = inferenceContext.asUndetVar(from);
vromero@2382 243 Type to = resultInfo.pt;
vromero@2382 244
vromero@2382 245 if (qtype.hasTag(VOID)) {
vromero@2382 246 to = syms.voidType;
vromero@2382 247 } else if (to.hasTag(NONE)) {
vromero@2382 248 to = from.isPrimitive() ? from : syms.objectType;
vromero@2382 249 } else if (qtype.hasTag(UNDETVAR)) {
vromero@2382 250 if (resultInfo.pt.isReference()) {
vromero@2382 251 to = generateReturnConstraintsUndetVarToReference(
vromero@2382 252 tree, (UndetVar)qtype, to, resultInfo, inferenceContext);
vromero@2382 253 } else {
vromero@2382 254 if (to.isPrimitive()) {
vromero@2382 255 to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to,
vromero@2382 256 resultInfo, inferenceContext);
vromero@2382 257 }
vromero@2382 258 }
vromero@2382 259 }
vromero@2368 260 Assert.check(allowGraphInference || !rsInfoInfContext.free(to),
mcimadamore@1562 261 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
mcimadamore@1562 262 //we need to skip capture?
mcimadamore@1562 263 Warner retWarn = new Warner();
vromero@2382 264 if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) ||
mcimadamore@1800 265 //unchecked conversion is not allowed in source 7 mode
mcimadamore@1800 266 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
mcimadamore@1562 267 throw inferenceException
mcimadamore@1562 268 .setMessage("infer.no.conforming.instance.exists",
mcimadamore@1562 269 inferenceContext.restvars(), mt.getReturnType(), to);
mcimadamore@1562 270 }
mcimadamore@1898 271 return from;
mcimadamore@1562 272 }
mcimadamore@1897 273
vromero@2382 274 private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from,
vromero@2382 275 Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) {
vromero@2382 276 if (!allowGraphInference) {
vromero@2382 277 //if legacy, just return boxed type
vromero@2382 278 return types.boxedClass(to).type;
vromero@2382 279 }
vromero@2382 280 //if graph inference we need to skip conflicting boxed bounds...
vromero@2382 281 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER,
vromero@2382 282 InferenceBound.LOWER)) {
vromero@2382 283 Type boundAsPrimitive = types.unboxedType(t);
vromero@2382 284 if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) {
vromero@2382 285 continue;
mcimadamore@1897 286 }
vromero@2382 287 return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382 288 resultInfo, inferenceContext);
vromero@2382 289 }
vromero@2382 290 return types.boxedClass(to).type;
vromero@2382 291 }
vromero@2382 292
vromero@2382 293 private Type generateReturnConstraintsUndetVarToReference(JCTree tree,
vromero@2382 294 UndetVar from, Type to, Attr.ResultInfo resultInfo,
vromero@2382 295 InferenceContext inferenceContext) {
vromero@2382 296 Type captureOfTo = types.capture(to);
vromero@2382 297 /* T is a reference type, but is not a wildcard-parameterized type, and either
vromero@2382 298 */
vromero@2382 299 if (captureOfTo == to) { //not a wildcard parameterized type
vromero@2382 300 /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha,
vromero@2382 301 * where S is a wildcard-parameterized type, or
vromero@2382 302 */
vromero@2382 303 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
vromero@2382 304 Type captureOfBound = types.capture(t);
vromero@2382 305 if (captureOfBound != t) {
vromero@2382 306 return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382 307 resultInfo, inferenceContext);
mcimadamore@1562 308 }
mcimadamore@1251 309 }
vromero@2382 310
vromero@2382 311 /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha,
vromero@2382 312 * where S1 and S2 have supertypes that are two different
vromero@2382 313 * parameterizations of the same generic class or interface.
vromero@2382 314 */
vromero@2382 315 for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) {
vromero@2382 316 for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) {
vromero@2382 317 if (aLowerBound != anotherLowerBound &&
vromero@2382 318 commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) {
vromero@2382 319 /* self comment check if any lower bound may be and undetVar,
vromero@2382 320 * in that case the result of this call may be a false positive.
vromero@2382 321 * Should this be restricted to non free types?
vromero@2382 322 */
vromero@2382 323 return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382 324 resultInfo, inferenceContext);
vromero@2382 325 }
vromero@2382 326 }
vromero@2382 327 }
duke@1 328 }
vromero@2382 329
vromero@2382 330 /* T is a parameterization of a generic class or interface, G,
vromero@2382 331 * and B2 contains a bound of one of the forms alpha = S or S <: alpha,
vromero@2382 332 * where there exists no type of the form G<...> that is a
vromero@2382 333 * supertype of S, but the raw type G is a supertype of S
vromero@2382 334 */
vromero@2382 335 if (to.isParameterized()) {
vromero@2382 336 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
vromero@2382 337 Type sup = types.asSuper(t, to.tsym);
vromero@2382 338 if (sup != null && sup.isRaw()) {
vromero@2382 339 return generateReferenceToTargetConstraint(tree, from, to,
vromero@2382 340 resultInfo, inferenceContext);
vromero@2382 341 }
vromero@2382 342 }
vromero@2382 343 }
vromero@2382 344 return to;
vromero@2382 345 }
vromero@2382 346
vromero@2382 347 private boolean commonSuperWithDiffParameterization(Type t, Type s) {
vromero@2382 348 Pair<Type, Type> supers = getParameterizedSupers(t, s);
vromero@2382 349 return (supers != null && !types.isSameType(supers.fst, supers.snd));
vromero@2382 350 }
vromero@2382 351
vromero@2382 352 private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from,
vromero@2382 353 Type to, Attr.ResultInfo resultInfo,
vromero@2382 354 InferenceContext inferenceContext) {
vromero@2382 355 inferenceContext.solve(List.of(from.qtype), new Warner());
vromero@2382 356 Type capturedType = resultInfo.checkContext.inferenceContext()
vromero@2382 357 .cachedCapture(tree, from.inst, false);
vromero@2382 358 if (types.isConvertible(capturedType,
vromero@2382 359 resultInfo.checkContext.inferenceContext().asUndetVar(to))) {
vromero@2382 360 //effectively skip additional return-type constraint generation (compatibility)
vromero@2382 361 return syms.objectType;
vromero@2382 362 }
vromero@2382 363 return to;
mcimadamore@1897 364 }
mcimadamore@1251 365
mcimadamore@1562 366 /**
mcimadamore@1562 367 * Infer cyclic inference variables as described in 15.12.2.8.
mcimadamore@1562 368 */
mcimadamore@1562 369 private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
alundblad@2047 370 ListBuffer<Type> todo = new ListBuffer<>();
mcimadamore@1562 371 //step 1 - create fresh tvars
mcimadamore@1562 372 for (Type t : vars) {
vromero@2368 373 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
mcimadamore@1562 374 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
mcimadamore@1562 375 if (Type.containsAny(upperBounds, vars)) {
jfranck@1689 376 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
mcimadamore@1562 377 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
mcimadamore@1562 378 todo.append(uv);
mcimadamore@1562 379 uv.inst = fresh_tvar.type;
mcimadamore@1562 380 } else if (upperBounds.nonEmpty()) {
mcimadamore@1562 381 uv.inst = types.glb(upperBounds);
mcimadamore@1562 382 } else {
mcimadamore@1562 383 uv.inst = syms.objectType;
mcimadamore@1338 384 }
mcimadamore@1562 385 }
mcimadamore@1562 386 //step 2 - replace fresh tvars in their bounds
mcimadamore@1562 387 List<Type> formals = vars;
mcimadamore@1562 388 for (Type t : todo) {
mcimadamore@1562 389 UndetVar uv = (UndetVar)t;
mcimadamore@1562 390 TypeVar ct = (TypeVar)uv.inst;
mcimadamore@1562 391 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
mcimadamore@1562 392 if (ct.bound.isErroneous()) {
mcimadamore@1562 393 //report inference error if glb fails
mcimadamore@1562 394 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1338 395 }
mcimadamore@1562 396 formals = formals.tail;
mcimadamore@1348 397 }
mcimadamore@1348 398 }
mcimadamore@1348 399
mcimadamore@674 400 /**
mcimadamore@674 401 * Compute a synthetic method type corresponding to the requested polymorphic
mcimadamore@820 402 * method signature. The target return type is computed from the immediately
mcimadamore@820 403 * enclosing scope surrounding the polymorphic-signature call.
mcimadamore@674 404 */
mcimadamore@1239 405 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
mcimadamore@674 406 MethodSymbol spMethod, // sig. poly. method or null if none
mcimadamore@1347 407 Resolve.MethodResolutionContext resolveContext,
mcimadamore@820 408 List<Type> argtypes) {
mcimadamore@674 409 final Type restype;
mcimadamore@716 410
mcimadamore@820 411 //The return type for a polymorphic signature call is computed from
mcimadamore@820 412 //the enclosing tree E, as follows: if E is a cast, then use the
mcimadamore@820 413 //target type of the cast expression as a return type; if E is an
mcimadamore@820 414 //expression statement, the return type is 'void' - otherwise the
mcimadamore@820 415 //return type is simply 'Object'. A correctness check ensures that
mcimadamore@820 416 //env.next refers to the lexically enclosing environment in which
mcimadamore@820 417 //the polymorphic signature call environment is nested.
mcimadamore@820 418
mcimadamore@820 419 switch (env.next.tree.getTag()) {
jjg@1127 420 case TYPECAST:
mcimadamore@820 421 JCTypeCast castTree = (JCTypeCast)env.next.tree;
mcimadamore@820 422 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
mcimadamore@820 423 castTree.clazz.type :
mcimadamore@820 424 syms.objectType;
mcimadamore@820 425 break;
jjg@1127 426 case EXEC:
mcimadamore@820 427 JCTree.JCExpressionStatement execTree =
mcimadamore@820 428 (JCTree.JCExpressionStatement)env.next.tree;
mcimadamore@820 429 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
mcimadamore@820 430 syms.voidType :
mcimadamore@820 431 syms.objectType;
mcimadamore@820 432 break;
mcimadamore@820 433 default:
mcimadamore@820 434 restype = syms.objectType;
mcimadamore@674 435 }
mcimadamore@674 436
mcimadamore@1347 437 List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
mcimadamore@674 438 List<Type> exType = spMethod != null ?
mcimadamore@674 439 spMethod.getThrownTypes() :
mcimadamore@674 440 List.of(syms.throwableType); // make it throw all exceptions
mcimadamore@674 441
mcimadamore@674 442 MethodType mtype = new MethodType(paramtypes,
mcimadamore@674 443 restype,
mcimadamore@674 444 exType,
mcimadamore@674 445 syms.methodClass);
mcimadamore@674 446 return mtype;
mcimadamore@674 447 }
mcimadamore@674 448 //where
mcimadamore@1347 449 class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
mcimadamore@1347 450
mcimadamore@1347 451 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
mcimadamore@1562 452 rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase);
mcimadamore@1347 453 }
mcimadamore@1347 454
mcimadamore@1347 455 public Type apply(Type t) {
mcimadamore@1347 456 t = types.erasure(super.apply(t));
jjg@1374 457 if (t.hasTag(BOT))
mcimadamore@1347 458 // nulls type as the marker type Null (which has no instances)
mcimadamore@1347 459 // infer as java.lang.Void for now
mcimadamore@1347 460 t = types.boxedClass(syms.voidType).type;
mcimadamore@1347 461 return t;
mcimadamore@1347 462 }
mcimadamore@1347 463 }
mcimadamore@1337 464
mcimadamore@1337 465 /**
mcimadamore@1562 466 * This method is used to infer a suitable target SAM in case the original
mcimadamore@1562 467 * SAM type contains one or more wildcards. An inference process is applied
mcimadamore@1562 468 * so that wildcard bounds, as well as explicit lambda/method ref parameters
mcimadamore@1562 469 * (where applicable) are used to constraint the solution.
mcimadamore@1562 470 */
mcimadamore@1562 471 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
mcimadamore@1562 472 List<Type> paramTypes, Check.CheckContext checkContext) {
mcimadamore@1562 473 if (types.capture(funcInterface) == funcInterface) {
mcimadamore@1562 474 //if capture doesn't change the type then return the target unchanged
mcimadamore@1562 475 //(this means the target contains no wildcards!)
mcimadamore@1562 476 return funcInterface;
mcimadamore@1562 477 } else {
mcimadamore@1562 478 Type formalInterface = funcInterface.tsym.type;
mcimadamore@1562 479 InferenceContext funcInterfaceContext =
mcimadamore@1562 480 new InferenceContext(funcInterface.tsym.type.getTypeArguments());
mcimadamore@1562 481
mcimadamore@1562 482 Assert.check(paramTypes != null);
mcimadamore@1562 483 //get constraints from explicit params (this is done by
mcimadamore@1562 484 //checking that explicit param types are equal to the ones
mcimadamore@1562 485 //in the functional interface descriptors)
mcimadamore@1562 486 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
mcimadamore@1562 487 if (descParameterTypes.size() != paramTypes.size()) {
mcimadamore@1562 488 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
mcimadamore@1562 489 return types.createErrorType(funcInterface);
mcimadamore@1562 490 }
mcimadamore@1562 491 for (Type p : descParameterTypes) {
vromero@2368 492 if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) {
mcimadamore@1562 493 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562 494 return types.createErrorType(funcInterface);
mcimadamore@1562 495 }
mcimadamore@1562 496 paramTypes = paramTypes.tail;
mcimadamore@1562 497 }
mcimadamore@1562 498
mcimadamore@1562 499 try {
mcimadamore@1562 500 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
mcimadamore@1562 501 } catch (InferenceException ex) {
mcimadamore@1562 502 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562 503 }
mcimadamore@1562 504
mcimadamore@1562 505 List<Type> actualTypeargs = funcInterface.getTypeArguments();
mcimadamore@1562 506 for (Type t : funcInterfaceContext.undetvars) {
mcimadamore@1562 507 UndetVar uv = (UndetVar)t;
mcimadamore@1562 508 if (uv.inst == null) {
mcimadamore@1562 509 uv.inst = actualTypeargs.head;
mcimadamore@1562 510 }
mcimadamore@1562 511 actualTypeargs = actualTypeargs.tail;
mcimadamore@1562 512 }
mcimadamore@1562 513
mcimadamore@1562 514 Type owntype = funcInterfaceContext.asInstType(formalInterface);
mcimadamore@1562 515 if (!chk.checkValidGenericType(owntype)) {
mcimadamore@1562 516 //if the inferred functional interface type is not well-formed,
mcimadamore@1562 517 //or if it's not a subtype of the original target, issue an error
mcimadamore@1562 518 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
mcimadamore@1562 519 }
mcimadamore@1562 520 return owntype;
mcimadamore@1562 521 }
mcimadamore@1562 522 }
mcimadamore@1562 523 // </editor-fold>
mcimadamore@1562 524
mcimadamore@1562 525 // <editor-fold defaultstate="collapsed" desc="Bound checking">
mcimadamore@1562 526 /**
mcimadamore@1562 527 * Check bounds and perform incorporation
mcimadamore@1562 528 */
mcimadamore@1562 529 void checkWithinBounds(InferenceContext inferenceContext,
mcimadamore@1562 530 Warner warn) throws InferenceException {
mcimadamore@1562 531 MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
mcimadamore@1891 532 List<Type> saved_undet = inferenceContext.save();
mcimadamore@1562 533 try {
mcimadamore@1562 534 while (true) {
mcimadamore@1562 535 mlistener.reset();
mcimadamore@1562 536 if (!allowGraphInference) {
mcimadamore@1562 537 //in legacy mode we lack of transitivity, so bound check
mcimadamore@1562 538 //cannot be run in parallel with other incoprporation rounds
mcimadamore@1562 539 for (Type t : inferenceContext.undetvars) {
mcimadamore@1562 540 UndetVar uv = (UndetVar)t;
mcimadamore@1562 541 IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
mcimadamore@1562 542 }
mcimadamore@1562 543 }
mcimadamore@1562 544 for (Type t : inferenceContext.undetvars) {
mcimadamore@1562 545 UndetVar uv = (UndetVar)t;
mcimadamore@1562 546 //bound incorporation
mcimadamore@1562 547 EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?
mcimadamore@1562 548 incorporationStepsGraph : incorporationStepsLegacy;
mcimadamore@1562 549 for (IncorporationStep is : incorporationSteps) {
mcimadamore@1898 550 if (is.accepts(uv, inferenceContext)) {
mcimadamore@1898 551 is.apply(uv, inferenceContext, warn);
mcimadamore@1898 552 }
mcimadamore@1562 553 }
mcimadamore@1562 554 }
mcimadamore@1562 555 if (!mlistener.changed || !allowGraphInference) break;
mcimadamore@1562 556 }
mcimadamore@1562 557 }
mcimadamore@1562 558 finally {
mcimadamore@1562 559 mlistener.detach();
mcimadamore@1905 560 if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {
mcimadamore@1891 561 inferenceContext.rollback(saved_undet);
mcimadamore@1891 562 }
mcimadamore@1905 563 incorporationCache.clear();
mcimadamore@1562 564 }
mcimadamore@1562 565 }
mcimadamore@1562 566 //where
mcimadamore@1562 567 /**
mcimadamore@1562 568 * This listener keeps track of changes on a group of inference variable
mcimadamore@1562 569 * bounds. Note: the listener must be detached (calling corresponding
mcimadamore@1562 570 * method) to make sure that the underlying inference variable is
mcimadamore@1562 571 * left in a clean state.
mcimadamore@1562 572 */
mcimadamore@1562 573 class MultiUndetVarListener implements UndetVar.UndetVarListener {
mcimadamore@1562 574
mcimadamore@1562 575 boolean changed;
mcimadamore@1562 576 List<Type> undetvars;
mcimadamore@1562 577
mcimadamore@1562 578 public MultiUndetVarListener(List<Type> undetvars) {
mcimadamore@1562 579 this.undetvars = undetvars;
mcimadamore@1562 580 for (Type t : undetvars) {
mcimadamore@1562 581 UndetVar uv = (UndetVar)t;
mcimadamore@1562 582 uv.listener = this;
mcimadamore@1562 583 }
mcimadamore@1562 584 }
mcimadamore@1562 585
mcimadamore@1562 586 public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {
mcimadamore@1562 587 //avoid non-termination
mcimadamore@1905 588 if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {
mcimadamore@1562 589 changed = true;
mcimadamore@1562 590 }
mcimadamore@1562 591 }
mcimadamore@1562 592
mcimadamore@1562 593 void reset() {
mcimadamore@1562 594 changed = false;
mcimadamore@1562 595 }
mcimadamore@1562 596
mcimadamore@1562 597 void detach() {
mcimadamore@1562 598 for (Type t : undetvars) {
mcimadamore@1562 599 UndetVar uv = (UndetVar)t;
mcimadamore@1562 600 uv.listener = null;
mcimadamore@1562 601 }
mcimadamore@1562 602 }
mcimadamore@1562 603 };
mcimadamore@1562 604
mcimadamore@1562 605 /** max number of incorporation rounds */
mcimadamore@1562 606 static final int MAX_INCORPORATION_STEPS = 100;
mcimadamore@1562 607
vromero@2369 608 /* If for two types t and s there is a least upper bound that is a
vromero@2369 609 * parameterized type G, then there exists a supertype of 't' of the form
vromero@2369 610 * G<T1, ..., Tn> and a supertype of 's' of the form G<S1, ..., Sn>
vromero@2369 611 * which will be returned by this method. If no such supertypes exists then
vromero@2369 612 * null is returned.
vromero@2369 613 *
vromero@2369 614 * As an example for the following input:
vromero@2369 615 *
vromero@2369 616 * t = java.util.ArrayList<java.lang.String>
vromero@2369 617 * s = java.util.List<T>
vromero@2369 618 *
vromero@2369 619 * we get this ouput:
vromero@2369 620 *
vromero@2369 621 * Pair[java.util.List<java.lang.String>,java.util.List<T>]
vromero@2369 622 */
vromero@2369 623 private Pair<Type, Type> getParameterizedSupers(Type t, Type s) {
vromero@2369 624 Type lubResult = types.lub(t, s);
vromero@2369 625 if (lubResult == syms.errType || lubResult == syms.botType ||
vromero@2369 626 !lubResult.isParameterized()) {
vromero@2369 627 return null;
vromero@2369 628 }
vromero@2369 629 Type asSuperOfT = types.asSuper(t, lubResult.tsym);
vromero@2369 630 Type asSuperOfS = types.asSuper(s, lubResult.tsym);
vromero@2369 631 return new Pair<>(asSuperOfT, asSuperOfS);
vromero@2369 632 }
vromero@2369 633
mcimadamore@1562 634 /**
mcimadamore@1562 635 * This enumeration defines an entry point for doing inference variable
mcimadamore@1562 636 * bound incorporation - it can be used to inject custom incorporation
mcimadamore@1562 637 * logic into the basic bound checking routine
mcimadamore@1562 638 */
mcimadamore@1562 639 enum IncorporationStep {
mcimadamore@1562 640 /**
mcimadamore@1562 641 * Performs basic bound checking - i.e. is the instantiated type for a given
mcimadamore@1562 642 * inference variable compatible with its bounds?
mcimadamore@1562 643 */
mcimadamore@1562 644 CHECK_BOUNDS() {
mcimadamore@1562 645 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 646 Infer infer = inferenceContext.infer();
mcimadamore@1562 647 uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
mcimadamore@1562 648 infer.checkCompatibleUpperBounds(uv, inferenceContext);
mcimadamore@1562 649 if (uv.inst != null) {
mcimadamore@1562 650 Type inst = uv.inst;
mcimadamore@1562 651 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
vromero@2368 652 if (!isSubtype(inst, inferenceContext.asUndetVar(u), warn, infer)) {
mcimadamore@1562 653 infer.reportBoundError(uv, BoundErrorKind.UPPER);
mcimadamore@1562 654 }
mcimadamore@1562 655 }
mcimadamore@1562 656 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368 657 if (!isSubtype(inferenceContext.asUndetVar(l), inst, warn, infer)) {
mcimadamore@1562 658 infer.reportBoundError(uv, BoundErrorKind.LOWER);
mcimadamore@1562 659 }
mcimadamore@1562 660 }
mcimadamore@1562 661 for (Type e : uv.getBounds(InferenceBound.EQ)) {
vromero@2368 662 if (!isSameType(inst, inferenceContext.asUndetVar(e), infer)) {
mcimadamore@1562 663 infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562 664 }
mcimadamore@1562 665 }
mcimadamore@1562 666 }
mcimadamore@1562 667 }
vromero@2368 668
mcimadamore@1898 669 @Override
mcimadamore@1898 670 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898 671 //applies to all undetvars
mcimadamore@1898 672 return true;
mcimadamore@1898 673 }
mcimadamore@1562 674 },
mcimadamore@1562 675 /**
mcimadamore@1562 676 * Check consistency of equality constraints. This is a slightly more aggressive
mcimadamore@1562 677 * inference routine that is designed as to maximize compatibility with JDK 7.
mcimadamore@1562 678 * Note: this is not used in graph mode.
mcimadamore@1562 679 */
mcimadamore@1562 680 EQ_CHECK_LEGACY() {
mcimadamore@1562 681 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 682 Infer infer = inferenceContext.infer();
mcimadamore@1562 683 Type eq = null;
mcimadamore@1562 684 for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562 685 Assert.check(!inferenceContext.free(e));
mcimadamore@1905 686 if (eq != null && !isSameType(e, eq, infer)) {
mcimadamore@1562 687 infer.reportBoundError(uv, BoundErrorKind.EQ);
mcimadamore@1562 688 }
mcimadamore@1562 689 eq = e;
mcimadamore@1562 690 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562 691 Assert.check(!inferenceContext.free(l));
mcimadamore@1905 692 if (!isSubtype(l, e, warn, infer)) {
mcimadamore@1562 693 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562 694 }
mcimadamore@1562 695 }
mcimadamore@1562 696 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562 697 if (inferenceContext.free(u)) continue;
mcimadamore@1905 698 if (!isSubtype(e, u, warn, infer)) {
mcimadamore@1562 699 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562 700 }
mcimadamore@1562 701 }
mcimadamore@1562 702 }
mcimadamore@1562 703 }
mcimadamore@1562 704 },
mcimadamore@1562 705 /**
mcimadamore@1562 706 * Check consistency of equality constraints.
mcimadamore@1562 707 */
mcimadamore@1562 708 EQ_CHECK() {
mcimadamore@1562 709 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 710 Infer infer = inferenceContext.infer();
mcimadamore@1562 711 for (Type e : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562 712 if (e.containsAny(inferenceContext.inferenceVars())) continue;
mcimadamore@1562 713 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
vromero@2368 714 if (!isSubtype(e, inferenceContext.asUndetVar(u), warn, infer)) {
mcimadamore@1562 715 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
mcimadamore@1562 716 }
mcimadamore@1562 717 }
mcimadamore@1562 718 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368 719 if (!isSubtype(inferenceContext.asUndetVar(l), e, warn, infer)) {
mcimadamore@1562 720 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
mcimadamore@1562 721 }
mcimadamore@1562 722 }
mcimadamore@1562 723 }
mcimadamore@1562 724 }
mcimadamore@1562 725 },
mcimadamore@1562 726 /**
mcimadamore@1562 727 * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
mcimadamore@1562 728 * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562 729 */
mcimadamore@1562 730 CROSS_UPPER_LOWER() {
mcimadamore@1562 731 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 732 Infer infer = inferenceContext.infer();
mcimadamore@1562 733 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562 734 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368 735 isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn , infer);
mcimadamore@1562 736 }
mcimadamore@1562 737 }
mcimadamore@1562 738 }
mcimadamore@1562 739 },
mcimadamore@1562 740 /**
mcimadamore@1562 741 * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
mcimadamore@1562 742 * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562 743 */
mcimadamore@1562 744 CROSS_UPPER_EQ() {
mcimadamore@1562 745 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 746 Infer infer = inferenceContext.infer();
mcimadamore@1562 747 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562 748 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
vromero@2368 749 isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
mcimadamore@1562 750 }
mcimadamore@1562 751 }
mcimadamore@1562 752 }
mcimadamore@1562 753 },
mcimadamore@1562 754 /**
mcimadamore@1562 755 * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
mcimadamore@1562 756 * perform {@code S <: T} (which could lead to new bounds).
mcimadamore@1562 757 */
mcimadamore@1562 758 CROSS_EQ_LOWER() {
mcimadamore@1562 759 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 760 Infer infer = inferenceContext.infer();
mcimadamore@1562 761 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562 762 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
vromero@2368 763 isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer);
mcimadamore@1655 764 }
mcimadamore@1655 765 }
mcimadamore@1655 766 }
mcimadamore@1655 767 },
mcimadamore@1655 768 /**
vromero@2369 769 * Given a bound set containing {@code alpha <: P<T>} and
vromero@2369 770 * {@code alpha <: P<S>} where P is a parameterized type,
vromero@2369 771 * perform {@code T = S} (which could lead to new bounds).
vromero@2369 772 */
vromero@2369 773 CROSS_UPPER_UPPER() {
vromero@2369 774 @Override
vromero@2369 775 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
vromero@2369 776 Infer infer = inferenceContext.infer();
vromero@2369 777 List<Type> boundList = uv.getBounds(InferenceBound.UPPER);
vromero@2369 778 List<Type> boundListTail = boundList.tail;
vromero@2369 779 while (boundList.nonEmpty()) {
vromero@2369 780 List<Type> tmpTail = boundListTail;
vromero@2369 781 while (tmpTail.nonEmpty()) {
vromero@2369 782 Type b1 = boundList.head;
vromero@2369 783 Type b2 = tmpTail.head;
vromero@2369 784 if (b1 != b2) {
vromero@2369 785 Pair<Type, Type> commonSupers = infer.getParameterizedSupers(b1, b2);
vromero@2369 786 if (commonSupers != null) {
vromero@2369 787 List<Type> allParamsSuperBound1 = commonSupers.fst.allparams();
vromero@2369 788 List<Type> allParamsSuperBound2 = commonSupers.snd.allparams();
vromero@2369 789 while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) {
vromero@2369 790 //traverse the list of all params comparing them
vromero@2369 791 if (!allParamsSuperBound1.head.hasTag(WILDCARD) &&
vromero@2369 792 !allParamsSuperBound2.head.hasTag(WILDCARD)) {
vromero@2369 793 isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head),
vromero@2369 794 inferenceContext.asUndetVar(allParamsSuperBound2.head), infer);
vromero@2369 795 }
vromero@2369 796 allParamsSuperBound1 = allParamsSuperBound1.tail;
vromero@2369 797 allParamsSuperBound2 = allParamsSuperBound2.tail;
vromero@2369 798 }
vromero@2369 799 Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty());
vromero@2369 800 }
vromero@2369 801 }
vromero@2369 802 tmpTail = tmpTail.tail;
vromero@2369 803 }
vromero@2369 804 boundList = boundList.tail;
vromero@2369 805 boundListTail = boundList.tail;
vromero@2369 806 }
vromero@2369 807 }
vromero@2369 808
vromero@2369 809 @Override
vromero@2369 810 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
vromero@2369 811 return !uv.isCaptured() &&
vromero@2369 812 uv.getBounds(InferenceBound.UPPER).nonEmpty();
vromero@2369 813 }
vromero@2369 814 },
vromero@2369 815 /**
mcimadamore@1655 816 * Given a bound set containing {@code alpha == S} and {@code alpha == T}
mcimadamore@1655 817 * perform {@code S == T} (which could lead to new bounds).
mcimadamore@1655 818 */
mcimadamore@1655 819 CROSS_EQ_EQ() {
mcimadamore@1655 820 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1655 821 Infer infer = inferenceContext.infer();
mcimadamore@1655 822 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1655 823 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1655 824 if (b1 != b2) {
vromero@2368 825 isSameType(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), infer);
mcimadamore@1562 826 }
mcimadamore@1562 827 }
mcimadamore@1562 828 }
mcimadamore@1562 829 }
mcimadamore@1562 830 },
mcimadamore@1562 831 /**
mcimadamore@1562 832 * Given a bound set containing {@code alpha <: beta} propagate lower bounds
mcimadamore@1562 833 * from alpha to beta; also propagate upper bounds from beta to alpha.
mcimadamore@1562 834 */
mcimadamore@1562 835 PROP_UPPER() {
mcimadamore@1562 836 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 837 Infer infer = inferenceContext.infer();
mcimadamore@1562 838 for (Type b : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1562 839 if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368 840 UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898 841 if (uv2.isCaptured()) continue;
mcimadamore@1562 842 //alpha <: beta
mcimadamore@1628 843 //0. set beta :> alpha
mcimadamore@1905 844 addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562 845 //1. copy alpha's lower to beta's
mcimadamore@1562 846 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1905 847 addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer);
mcimadamore@1562 848 }
mcimadamore@1562 849 //2. copy beta's upper to alpha's
mcimadamore@1562 850 for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
mcimadamore@1905 851 addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer);
mcimadamore@1562 852 }
mcimadamore@1562 853 }
mcimadamore@1562 854 }
mcimadamore@1562 855 }
mcimadamore@1562 856 },
mcimadamore@1562 857 /**
mcimadamore@1562 858 * Given a bound set containing {@code alpha :> beta} propagate lower bounds
mcimadamore@1562 859 * from beta to alpha; also propagate upper bounds from alpha to beta.
mcimadamore@1562 860 */
mcimadamore@1562 861 PROP_LOWER() {
mcimadamore@1562 862 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 863 Infer infer = inferenceContext.infer();
mcimadamore@1562 864 for (Type b : uv.getBounds(InferenceBound.LOWER)) {
mcimadamore@1562 865 if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368 866 UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898 867 if (uv2.isCaptured()) continue;
mcimadamore@1562 868 //alpha :> beta
mcimadamore@1628 869 //0. set beta <: alpha
mcimadamore@1905 870 addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562 871 //1. copy alpha's upper to beta's
mcimadamore@1562 872 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
mcimadamore@1905 873 addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer);
mcimadamore@1562 874 }
mcimadamore@1562 875 //2. copy beta's lower to alpha's
mcimadamore@1562 876 for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
mcimadamore@1905 877 addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer);
mcimadamore@1562 878 }
mcimadamore@1562 879 }
mcimadamore@1562 880 }
mcimadamore@1562 881 }
mcimadamore@1562 882 },
mcimadamore@1562 883 /**
mcimadamore@1562 884 * Given a bound set containing {@code alpha == beta} propagate lower/upper
mcimadamore@1562 885 * bounds from alpha to beta and back.
mcimadamore@1562 886 */
mcimadamore@1562 887 PROP_EQ() {
mcimadamore@1562 888 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
mcimadamore@1562 889 Infer infer = inferenceContext.infer();
mcimadamore@1562 890 for (Type b : uv.getBounds(InferenceBound.EQ)) {
mcimadamore@1562 891 if (inferenceContext.inferenceVars().contains(b)) {
vromero@2368 892 UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b);
mcimadamore@1898 893 if (uv2.isCaptured()) continue;
mcimadamore@1562 894 //alpha == beta
mcimadamore@1628 895 //0. set beta == alpha
mcimadamore@1905 896 addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);
mcimadamore@1562 897 //1. copy all alpha's bounds to beta's
mcimadamore@1562 898 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562 899 for (Type b2 : uv.getBounds(ib)) {
mcimadamore@1562 900 if (b2 != uv2) {
mcimadamore@1905 901 addBound(ib, uv2, inferenceContext.asInstType(b2), infer);
mcimadamore@1562 902 }
mcimadamore@1562 903 }
mcimadamore@1562 904 }
mcimadamore@1562 905 //2. copy all beta's bounds to alpha's
mcimadamore@1562 906 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562 907 for (Type b2 : uv2.getBounds(ib)) {
mcimadamore@1562 908 if (b2 != uv) {
mcimadamore@1905 909 addBound(ib, uv, inferenceContext.asInstType(b2), infer);
mcimadamore@1562 910 }
mcimadamore@1562 911 }
mcimadamore@1562 912 }
mcimadamore@1562 913 }
mcimadamore@1562 914 }
mcimadamore@1562 915 }
mcimadamore@1562 916 };
mcimadamore@1562 917
mcimadamore@1562 918 abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
mcimadamore@1898 919
mcimadamore@1898 920 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898 921 return !uv.isCaptured();
mcimadamore@1898 922 }
mcimadamore@1905 923
mcimadamore@1905 924 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
mcimadamore@1905 925 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
mcimadamore@1905 926 }
mcimadamore@1905 927
mcimadamore@1905 928 boolean isSameType(Type s, Type t, Infer infer) {
mcimadamore@1905 929 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
mcimadamore@1905 930 }
mcimadamore@1905 931
mcimadamore@1905 932 void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
mcimadamore@1905 933 doIncorporationOp(opFor(ib), uv, b, null, infer);
mcimadamore@1905 934 }
mcimadamore@1905 935
mcimadamore@1905 936 IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
mcimadamore@1905 937 switch (boundKind) {
mcimadamore@1905 938 case EQ:
mcimadamore@1905 939 return IncorporationBinaryOpKind.ADD_EQ_BOUND;
mcimadamore@1905 940 case LOWER:
mcimadamore@1905 941 return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
mcimadamore@1905 942 case UPPER:
mcimadamore@1905 943 return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
mcimadamore@1905 944 default:
mcimadamore@1905 945 Assert.error("Can't get here!");
mcimadamore@1905 946 return null;
mcimadamore@1905 947 }
mcimadamore@1905 948 }
mcimadamore@1905 949
mcimadamore@1905 950 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
mcimadamore@1905 951 IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
mcimadamore@1905 952 Boolean res = infer.incorporationCache.get(newOp);
mcimadamore@1905 953 if (res == null) {
mcimadamore@1905 954 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
mcimadamore@1905 955 }
mcimadamore@1905 956 return res;
mcimadamore@1905 957 }
mcimadamore@1562 958 }
mcimadamore@1562 959
mcimadamore@1562 960 /** incorporation steps to be executed when running in legacy mode */
mcimadamore@1562 961 EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
mcimadamore@1562 962
mcimadamore@1562 963 /** incorporation steps to be executed when running in graph mode */
mcimadamore@1562 964 EnumSet<IncorporationStep> incorporationStepsGraph =
mcimadamore@1562 965 EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
mcimadamore@1562 966
mcimadamore@1562 967 /**
mcimadamore@1905 968 * Three kinds of basic operation are supported as part of an incorporation step:
mcimadamore@1905 969 * (i) subtype check, (ii) same type check and (iii) bound addition (either
mcimadamore@1905 970 * upper/lower/eq bound).
mcimadamore@1905 971 */
mcimadamore@1905 972 enum IncorporationBinaryOpKind {
mcimadamore@1905 973 IS_SUBTYPE() {
mcimadamore@1905 974 @Override
mcimadamore@1905 975 boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905 976 return types.isSubtypeUnchecked(op1, op2, warn);
mcimadamore@1905 977 }
mcimadamore@1905 978 },
mcimadamore@1905 979 IS_SAME_TYPE() {
mcimadamore@1905 980 @Override
mcimadamore@1905 981 boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905 982 return types.isSameType(op1, op2);
mcimadamore@1905 983 }
mcimadamore@1905 984 },
mcimadamore@1905 985 ADD_UPPER_BOUND() {
mcimadamore@1905 986 @Override
mcimadamore@1905 987 boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905 988 UndetVar uv = (UndetVar)op1;
mcimadamore@1905 989 uv.addBound(InferenceBound.UPPER, op2, types);
mcimadamore@1905 990 return true;
mcimadamore@1905 991 }
mcimadamore@1905 992 },
mcimadamore@1905 993 ADD_LOWER_BOUND() {
mcimadamore@1905 994 @Override
mcimadamore@1905 995 boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905 996 UndetVar uv = (UndetVar)op1;
mcimadamore@1905 997 uv.addBound(InferenceBound.LOWER, op2, types);
mcimadamore@1905 998 return true;
mcimadamore@1905 999 }
mcimadamore@1905 1000 },
mcimadamore@1905 1001 ADD_EQ_BOUND() {
mcimadamore@1905 1002 @Override
mcimadamore@1905 1003 boolean apply(Type op1, Type op2, Warner warn, Types types) {
mcimadamore@1905 1004 UndetVar uv = (UndetVar)op1;
mcimadamore@1905 1005 uv.addBound(InferenceBound.EQ, op2, types);
mcimadamore@1905 1006 return true;
mcimadamore@1905 1007 }
mcimadamore@1905 1008 };
mcimadamore@1905 1009
mcimadamore@1905 1010 abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
mcimadamore@1905 1011 }
mcimadamore@1905 1012
mcimadamore@1905 1013 /**
mcimadamore@1905 1014 * This class encapsulates a basic incorporation operation; incorporation
mcimadamore@1905 1015 * operations takes two type operands and a kind. Each operation performed
mcimadamore@1905 1016 * during an incorporation round is stored in a cache, so that operations
mcimadamore@1905 1017 * are not executed unnecessarily (which would potentially lead to adding
mcimadamore@1905 1018 * same bounds over and over).
mcimadamore@1905 1019 */
mcimadamore@1905 1020 class IncorporationBinaryOp {
mcimadamore@1905 1021
mcimadamore@1905 1022 IncorporationBinaryOpKind opKind;
mcimadamore@1905 1023 Type op1;
mcimadamore@1905 1024 Type op2;
mcimadamore@1905 1025
mcimadamore@1905 1026 IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
mcimadamore@1905 1027 this.opKind = opKind;
mcimadamore@1905 1028 this.op1 = op1;
mcimadamore@1905 1029 this.op2 = op2;
mcimadamore@1905 1030 }
mcimadamore@1905 1031
mcimadamore@1905 1032 @Override
mcimadamore@1905 1033 public boolean equals(Object o) {
mcimadamore@1905 1034 if (!(o instanceof IncorporationBinaryOp)) {
mcimadamore@1905 1035 return false;
mcimadamore@1905 1036 } else {
mcimadamore@1905 1037 IncorporationBinaryOp that = (IncorporationBinaryOp)o;
mcimadamore@1905 1038 return opKind == that.opKind &&
mcimadamore@1905 1039 types.isSameType(op1, that.op1, true) &&
mcimadamore@1905 1040 types.isSameType(op2, that.op2, true);
mcimadamore@1905 1041 }
mcimadamore@1905 1042 }
mcimadamore@1905 1043
mcimadamore@1905 1044 @Override
mcimadamore@1905 1045 public int hashCode() {
mcimadamore@1905 1046 int result = opKind.hashCode();
mcimadamore@1905 1047 result *= 127;
mcimadamore@1905 1048 result += types.hashCode(op1);
mcimadamore@1905 1049 result *= 127;
mcimadamore@1905 1050 result += types.hashCode(op2);
mcimadamore@1905 1051 return result;
mcimadamore@1905 1052 }
mcimadamore@1905 1053
mcimadamore@1905 1054 boolean apply(Warner warn) {
mcimadamore@1905 1055 return opKind.apply(op1, op2, warn, types);
mcimadamore@1905 1056 }
mcimadamore@1905 1057 }
mcimadamore@1905 1058
mcimadamore@1905 1059 /** an incorporation cache keeps track of all executed incorporation-related operations */
mcimadamore@1905 1060 Map<IncorporationBinaryOp, Boolean> incorporationCache =
mcimadamore@1905 1061 new HashMap<IncorporationBinaryOp, Boolean>();
mcimadamore@1905 1062
mcimadamore@1905 1063 /**
mcimadamore@1562 1064 * Make sure that the upper bounds we got so far lead to a solvable inference
mcimadamore@1562 1065 * variable by making sure that a glb exists.
mcimadamore@1562 1066 */
mcimadamore@1562 1067 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1068 List<Type> hibounds =
mcimadamore@1562 1069 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
mcimadamore@1562 1070 Type hb = null;
mcimadamore@1562 1071 if (hibounds.isEmpty())
mcimadamore@1562 1072 hb = syms.objectType;
mcimadamore@1562 1073 else if (hibounds.tail.isEmpty())
mcimadamore@1562 1074 hb = hibounds.head;
mcimadamore@1562 1075 else
mcimadamore@1562 1076 hb = types.glb(hibounds);
mcimadamore@1562 1077 if (hb == null || hb.isErroneous())
mcimadamore@1562 1078 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
mcimadamore@1562 1079 }
mcimadamore@1562 1080 //where
mcimadamore@1562 1081 protected static class BoundFilter implements Filter<Type> {
mcimadamore@1562 1082
mcimadamore@1562 1083 InferenceContext inferenceContext;
mcimadamore@1562 1084
mcimadamore@1562 1085 public BoundFilter(InferenceContext inferenceContext) {
mcimadamore@1562 1086 this.inferenceContext = inferenceContext;
mcimadamore@1562 1087 }
mcimadamore@1562 1088
mcimadamore@1562 1089 @Override
mcimadamore@1562 1090 public boolean accepts(Type t) {
mcimadamore@1562 1091 return !t.isErroneous() && !inferenceContext.free(t) &&
mcimadamore@1562 1092 !t.hasTag(BOT);
mcimadamore@1562 1093 }
mcimadamore@1562 1094 };
mcimadamore@1562 1095
mcimadamore@1562 1096 /**
mcimadamore@1562 1097 * This enumeration defines all possible bound-checking related errors.
mcimadamore@1562 1098 */
mcimadamore@1562 1099 enum BoundErrorKind {
mcimadamore@1562 1100 /**
mcimadamore@1562 1101 * The (uninstantiated) inference variable has incompatible upper bounds.
mcimadamore@1562 1102 */
mcimadamore@1562 1103 BAD_UPPER() {
mcimadamore@1562 1104 @Override
mcimadamore@1562 1105 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1106 return ex.setMessage("incompatible.upper.bounds", uv.qtype,
mcimadamore@1562 1107 uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562 1108 }
mcimadamore@1562 1109 },
mcimadamore@1562 1110 /**
mcimadamore@1562 1111 * An equality constraint is not compatible with an upper bound.
mcimadamore@1562 1112 */
mcimadamore@1562 1113 BAD_EQ_UPPER() {
mcimadamore@1562 1114 @Override
mcimadamore@1562 1115 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1116 return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
mcimadamore@1562 1117 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562 1118 }
mcimadamore@1562 1119 },
mcimadamore@1562 1120 /**
mcimadamore@1562 1121 * An equality constraint is not compatible with a lower bound.
mcimadamore@1562 1122 */
mcimadamore@1562 1123 BAD_EQ_LOWER() {
mcimadamore@1562 1124 @Override
mcimadamore@1562 1125 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1126 return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
mcimadamore@1562 1127 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562 1128 }
mcimadamore@1562 1129 },
mcimadamore@1562 1130 /**
mcimadamore@1562 1131 * Instantiated inference variable is not compatible with an upper bound.
mcimadamore@1562 1132 */
mcimadamore@1562 1133 UPPER() {
mcimadamore@1562 1134 @Override
mcimadamore@1562 1135 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1136 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
mcimadamore@1562 1137 uv.getBounds(InferenceBound.UPPER));
mcimadamore@1562 1138 }
mcimadamore@1562 1139 },
mcimadamore@1562 1140 /**
mcimadamore@1562 1141 * Instantiated inference variable is not compatible with a lower bound.
mcimadamore@1562 1142 */
mcimadamore@1562 1143 LOWER() {
mcimadamore@1562 1144 @Override
mcimadamore@1562 1145 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1146 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
mcimadamore@1562 1147 uv.getBounds(InferenceBound.LOWER));
mcimadamore@1562 1148 }
mcimadamore@1562 1149 },
mcimadamore@1562 1150 /**
mcimadamore@1562 1151 * Instantiated inference variable is not compatible with an equality constraint.
mcimadamore@1562 1152 */
mcimadamore@1562 1153 EQ() {
mcimadamore@1562 1154 @Override
mcimadamore@1562 1155 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
mcimadamore@1562 1156 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
mcimadamore@1562 1157 uv.getBounds(InferenceBound.EQ));
mcimadamore@1562 1158 }
mcimadamore@1562 1159 };
mcimadamore@1562 1160
mcimadamore@1562 1161 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
mcimadamore@1562 1162 }
mcimadamore@1562 1163
mcimadamore@1562 1164 /**
mcimadamore@1562 1165 * Report a bound-checking error of given kind
mcimadamore@1562 1166 */
mcimadamore@1562 1167 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
mcimadamore@1562 1168 throw bk.setMessage(inferenceException, uv);
mcimadamore@1562 1169 }
mcimadamore@1562 1170 // </editor-fold>
mcimadamore@1562 1171
mcimadamore@1562 1172 // <editor-fold defaultstate="collapsed" desc="Inference engine">
mcimadamore@1562 1173 /**
mcimadamore@1562 1174 * Graph inference strategy - act as an input to the inference solver; a strategy is
mcimadamore@1562 1175 * composed of two ingredients: (i) find a node to solve in the inference graph,
mcimadamore@1562 1176 * and (ii) tell th engine when we are done fixing inference variables
mcimadamore@1562 1177 */
mcimadamore@1562 1178 interface GraphStrategy {
vromero@2000 1179
vromero@2000 1180 /**
vromero@2000 1181 * A NodeNotFoundException is thrown whenever an inference strategy fails
vromero@2000 1182 * to pick the next node to solve in the inference graph.
vromero@2000 1183 */
vromero@2000 1184 public static class NodeNotFoundException extends RuntimeException {
vromero@2000 1185 private static final long serialVersionUID = 0;
vromero@2000 1186
vromero@2000 1187 InferenceGraph graph;
vromero@2000 1188
vromero@2000 1189 public NodeNotFoundException(InferenceGraph graph) {
vromero@2000 1190 this.graph = graph;
vromero@2000 1191 }
vromero@2000 1192 }
mcimadamore@1562 1193 /**
mcimadamore@1562 1194 * Pick the next node (leaf) to solve in the graph
mcimadamore@1562 1195 */
vromero@2000 1196 Node pickNode(InferenceGraph g) throws NodeNotFoundException;
mcimadamore@1562 1197 /**
mcimadamore@1562 1198 * Is this the last step?
mcimadamore@1562 1199 */
mcimadamore@1562 1200 boolean done();
mcimadamore@1562 1201 }
mcimadamore@1562 1202
mcimadamore@1562 1203 /**
mcimadamore@1562 1204 * Simple solver strategy class that locates all leaves inside a graph
mcimadamore@1562 1205 * and picks the first leaf as the next node to solve
mcimadamore@1562 1206 */
mcimadamore@1562 1207 abstract class LeafSolver implements GraphStrategy {
mcimadamore@1562 1208 public Node pickNode(InferenceGraph g) {
vromero@2000 1209 if (g.nodes.isEmpty()) {
vromero@2000 1210 //should not happen
vromero@2000 1211 throw new NodeNotFoundException(g);
vromero@2000 1212 };
mcimadamore@1562 1213 return g.nodes.get(0);
mcimadamore@1562 1214 }
mcimadamore@1905 1215
mcimadamore@1905 1216 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
mcimadamore@1905 1217 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
mcimadamore@1905 1218 }
mcimadamore@1905 1219
mcimadamore@1905 1220 boolean isSameType(Type s, Type t, Infer infer) {
mcimadamore@1905 1221 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
mcimadamore@1905 1222 }
mcimadamore@1905 1223
mcimadamore@1905 1224 void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
mcimadamore@1905 1225 doIncorporationOp(opFor(ib), uv, b, null, infer);
mcimadamore@1905 1226 }
mcimadamore@1905 1227
mcimadamore@1905 1228 IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
mcimadamore@1905 1229 switch (boundKind) {
mcimadamore@1905 1230 case EQ:
mcimadamore@1905 1231 return IncorporationBinaryOpKind.ADD_EQ_BOUND;
mcimadamore@1905 1232 case LOWER:
mcimadamore@1905 1233 return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
mcimadamore@1905 1234 case UPPER:
mcimadamore@1905 1235 return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
mcimadamore@1905 1236 default:
mcimadamore@1905 1237 Assert.error("Can't get here!");
mcimadamore@1905 1238 return null;
mcimadamore@1905 1239 }
mcimadamore@1905 1240 }
mcimadamore@1905 1241
mcimadamore@1905 1242 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
mcimadamore@1905 1243 IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
mcimadamore@1905 1244 Boolean res = infer.incorporationCache.get(newOp);
mcimadamore@1905 1245 if (res == null) {
mcimadamore@1905 1246 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
mcimadamore@1905 1247 }
mcimadamore@1905 1248 return res;
mcimadamore@1905 1249 }
mcimadamore@1562 1250 }
mcimadamore@1562 1251
mcimadamore@1562 1252 /**
mcimadamore@1562 1253 * This solver uses an heuristic to pick the best leaf - the heuristic
mcimadamore@1562 1254 * tries to select the node that has maximal probability to contain one
mcimadamore@1562 1255 * or more inference variables in a given list
mcimadamore@1562 1256 */
mcimadamore@1562 1257 abstract class BestLeafSolver extends LeafSolver {
mcimadamore@1562 1258
vromero@2000 1259 /** list of ivars of which at least one must be solved */
mcimadamore@1562 1260 List<Type> varsToSolve;
mcimadamore@1562 1261
mcimadamore@1562 1262 BestLeafSolver(List<Type> varsToSolve) {
mcimadamore@1562 1263 this.varsToSolve = varsToSolve;
mcimadamore@1562 1264 }
mcimadamore@1562 1265
mcimadamore@1562 1266 /**
vromero@2000 1267 * Computes a path that goes from a given node to the leafs in the graph.
vromero@2000 1268 * Typically this will start from a node containing a variable in
vromero@2000 1269 * {@code varsToSolve}. For any given path, the cost is computed as the total
vromero@2000 1270 * number of type-variables that should be eagerly instantiated across that path.
mcimadamore@1562 1271 */
vromero@2000 1272 Pair<List<Node>, Integer> computeTreeToLeafs(Node n) {
vromero@2000 1273 Pair<List<Node>, Integer> cachedPath = treeCache.get(n);
vromero@2000 1274 if (cachedPath == null) {
vromero@2000 1275 //cache miss
vromero@2000 1276 if (n.isLeaf()) {
vromero@2000 1277 //if leaf, stop
vromero@2000 1278 cachedPath = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
vromero@2000 1279 } else {
vromero@2000 1280 //if non-leaf, proceed recursively
vromero@2000 1281 Pair<List<Node>, Integer> path = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
vromero@2000 1282 for (Node n2 : n.getAllDependencies()) {
vromero@2000 1283 if (n2 == n) continue;
vromero@2000 1284 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2);
vromero@2000 1285 path = new Pair<List<Node>, Integer>(
vromero@2000 1286 path.fst.prependList(subpath.fst),
vromero@2000 1287 path.snd + subpath.snd);
vromero@2000 1288 }
vromero@2000 1289 cachedPath = path;
vromero@2000 1290 }
vromero@2000 1291 //save results in cache
vromero@2000 1292 treeCache.put(n, cachedPath);
vromero@2000 1293 }
vromero@2000 1294 return cachedPath;
mcimadamore@1903 1295 }
mcimadamore@1903 1296
vromero@2000 1297 /** cache used to avoid redundant computation of tree costs */
vromero@2000 1298 final Map<Node, Pair<List<Node>, Integer>> treeCache =
vromero@2000 1299 new HashMap<Node, Pair<List<Node>, Integer>>();
vromero@2000 1300
vromero@2000 1301 /** constant value used to mark non-existent paths */
vromero@2000 1302 final Pair<List<Node>, Integer> noPath =
vromero@2000 1303 new Pair<List<Node>, Integer>(null, Integer.MAX_VALUE);
mcimadamore@1562 1304
mcimadamore@1562 1305 /**
mcimadamore@1562 1306 * Pick the leaf that minimize cost
mcimadamore@1562 1307 */
mcimadamore@1562 1308 @Override
mcimadamore@1562 1309 public Node pickNode(final InferenceGraph g) {
vromero@2000 1310 treeCache.clear(); //graph changes at every step - cache must be cleared
vromero@2000 1311 Pair<List<Node>, Integer> bestPath = noPath;
mcimadamore@1562 1312 for (Node n : g.nodes) {
vromero@2000 1313 if (!Collections.disjoint(n.data, varsToSolve)) {
vromero@2000 1314 Pair<List<Node>, Integer> path = computeTreeToLeafs(n);
vromero@2000 1315 //discard all paths containing at least a node in the
vromero@2000 1316 //closure computed above
vromero@2000 1317 if (path.snd < bestPath.snd) {
vromero@2000 1318 bestPath = path;
vromero@2000 1319 }
mcimadamore@1562 1320 }
mcimadamore@1562 1321 }
vromero@2000 1322 if (bestPath == noPath) {
vromero@2000 1323 //no path leads there
vromero@2000 1324 throw new NodeNotFoundException(g);
vromero@2000 1325 }
vromero@2000 1326 return bestPath.fst.head;
mcimadamore@1562 1327 }
mcimadamore@1562 1328 }
mcimadamore@1562 1329
mcimadamore@1562 1330 /**
mcimadamore@1562 1331 * The inference process can be thought of as a sequence of steps. Each step
mcimadamore@1562 1332 * instantiates an inference variable using a subset of the inference variable
mcimadamore@1562 1333 * bounds, if certain condition are met. Decisions such as the sequence in which
mcimadamore@1562 1334 * steps are applied, or which steps are to be applied are left to the inference engine.
mcimadamore@1562 1335 */
mcimadamore@1562 1336 enum InferenceStep {
mcimadamore@1562 1337
mcimadamore@1562 1338 /**
mcimadamore@1562 1339 * Instantiate an inference variables using one of its (ground) equality
mcimadamore@1562 1340 * constraints
mcimadamore@1562 1341 */
mcimadamore@1562 1342 EQ(InferenceBound.EQ) {
mcimadamore@1562 1343 @Override
mcimadamore@1562 1344 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1345 return filterBounds(uv, inferenceContext).head;
mcimadamore@1562 1346 }
mcimadamore@1562 1347 },
mcimadamore@1562 1348 /**
mcimadamore@1562 1349 * Instantiate an inference variables using its (ground) lower bounds. Such
mcimadamore@1562 1350 * bounds are merged together using lub().
mcimadamore@1562 1351 */
mcimadamore@1562 1352 LOWER(InferenceBound.LOWER) {
mcimadamore@1562 1353 @Override
mcimadamore@1562 1354 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1355 Infer infer = inferenceContext.infer();
mcimadamore@1562 1356 List<Type> lobounds = filterBounds(uv, inferenceContext);
vromero@1826 1357 //note: lobounds should have at least one element
vromero@1826 1358 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds);
vromero@1826 1359 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
mcimadamore@1562 1360 throw infer.inferenceException
mcimadamore@1562 1361 .setMessage("no.unique.minimal.instance.exists",
mcimadamore@1562 1362 uv.qtype, lobounds);
mcimadamore@1562 1363 } else {
mcimadamore@1562 1364 return owntype;
mcimadamore@1562 1365 }
mcimadamore@1562 1366 }
mcimadamore@1562 1367 },
mcimadamore@1562 1368 /**
mcimadamore@1896 1369 * Infer uninstantiated/unbound inference variables occurring in 'throws'
mcimadamore@1896 1370 * clause as RuntimeException
mcimadamore@1896 1371 */
mcimadamore@1896 1372 THROWS(InferenceBound.UPPER) {
mcimadamore@1896 1373 @Override
mcimadamore@1896 1374 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1896 1375 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
mcimadamore@1896 1376 //not a throws undet var
mcimadamore@1896 1377 return false;
mcimadamore@1896 1378 }
mcimadamore@1896 1379 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
mcimadamore@1896 1380 .diff(t.getDeclaredBounds()).nonEmpty()) {
mcimadamore@1896 1381 //not an unbounded undet var
mcimadamore@1896 1382 return false;
mcimadamore@1896 1383 }
mcimadamore@1896 1384 Infer infer = inferenceContext.infer();
mcimadamore@1896 1385 for (Type db : t.getDeclaredBounds()) {
mcimadamore@1896 1386 if (t.isInterface()) continue;
mcimadamore@1896 1387 if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
mcimadamore@1896 1388 //declared bound is a supertype of RuntimeException
mcimadamore@1896 1389 return true;
mcimadamore@1896 1390 }
mcimadamore@1896 1391 }
mcimadamore@1896 1392 //declared bound is more specific then RuntimeException - give up
mcimadamore@1896 1393 return false;
mcimadamore@1896 1394 }
mcimadamore@1896 1395
mcimadamore@1896 1396 @Override
mcimadamore@1896 1397 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1896 1398 return inferenceContext.infer().syms.runtimeExceptionType;
mcimadamore@1896 1399 }
mcimadamore@1896 1400 },
mcimadamore@1896 1401 /**
mcimadamore@1562 1402 * Instantiate an inference variables using its (ground) upper bounds. Such
mcimadamore@1562 1403 * bounds are merged together using glb().
mcimadamore@1562 1404 */
mcimadamore@1562 1405 UPPER(InferenceBound.UPPER) {
mcimadamore@1562 1406 @Override
mcimadamore@1562 1407 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1408 Infer infer = inferenceContext.infer();
mcimadamore@1562 1409 List<Type> hibounds = filterBounds(uv, inferenceContext);
vromero@1826 1410 //note: lobounds should have at least one element
vromero@1826 1411 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds);
vromero@1826 1412 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
mcimadamore@1562 1413 throw infer.inferenceException
mcimadamore@1562 1414 .setMessage("no.unique.maximal.instance.exists",
mcimadamore@1562 1415 uv.qtype, hibounds);
mcimadamore@1562 1416 } else {
mcimadamore@1562 1417 return owntype;
mcimadamore@1562 1418 }
mcimadamore@1562 1419 }
mcimadamore@1562 1420 },
mcimadamore@1562 1421 /**
mcimadamore@1562 1422 * Like the former; the only difference is that this step can only be applied
mcimadamore@1562 1423 * if all upper bounds are ground.
mcimadamore@1562 1424 */
mcimadamore@1562 1425 UPPER_LEGACY(InferenceBound.UPPER) {
mcimadamore@1562 1426 @Override
mcimadamore@1562 1427 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1898 1428 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
mcimadamore@1562 1429 }
mcimadamore@1562 1430
mcimadamore@1562 1431 @Override
mcimadamore@1562 1432 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1433 return UPPER.solve(uv, inferenceContext);
mcimadamore@1562 1434 }
mcimadamore@1898 1435 },
mcimadamore@1898 1436 /**
mcimadamore@1898 1437 * Like the former; the only difference is that this step can only be applied
mcimadamore@1898 1438 * if all upper/lower bounds are ground.
mcimadamore@1898 1439 */
mcimadamore@1898 1440 CAPTURED(InferenceBound.UPPER) {
mcimadamore@1898 1441 @Override
mcimadamore@1898 1442 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1919 1443 return t.isCaptured() &&
mcimadamore@1919 1444 !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
mcimadamore@1898 1445 }
mcimadamore@1898 1446
mcimadamore@1898 1447 @Override
mcimadamore@1898 1448 Type solve(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1898 1449 Infer infer = inferenceContext.infer();
mcimadamore@1898 1450 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
mcimadamore@1898 1451 UPPER.solve(uv, inferenceContext) :
mcimadamore@1898 1452 infer.syms.objectType;
mcimadamore@1898 1453 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
mcimadamore@1898 1454 LOWER.solve(uv, inferenceContext) :
mcimadamore@1898 1455 infer.syms.botType;
mcimadamore@1898 1456 CapturedType prevCaptured = (CapturedType)uv.qtype;
mcimadamore@1898 1457 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);
mcimadamore@1898 1458 }
mcimadamore@1562 1459 };
mcimadamore@1562 1460
mcimadamore@1562 1461 final InferenceBound ib;
mcimadamore@1562 1462
mcimadamore@1562 1463 InferenceStep(InferenceBound ib) {
mcimadamore@1562 1464 this.ib = ib;
mcimadamore@1562 1465 }
mcimadamore@1562 1466
mcimadamore@1562 1467 /**
mcimadamore@1562 1468 * Find an instantiated type for a given inference variable within
mcimadamore@1562 1469 * a given inference context
mcimadamore@1562 1470 */
mcimadamore@1562 1471 abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
mcimadamore@1562 1472
mcimadamore@1562 1473 /**
mcimadamore@1562 1474 * Can the inference variable be instantiated using this step?
mcimadamore@1562 1475 */
mcimadamore@1562 1476 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
mcimadamore@1898 1477 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
mcimadamore@1562 1478 }
mcimadamore@1562 1479
mcimadamore@1562 1480 /**
mcimadamore@1562 1481 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
mcimadamore@1562 1482 */
mcimadamore@1562 1483 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
mcimadamore@1562 1484 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
mcimadamore@1562 1485 }
mcimadamore@1562 1486 }
mcimadamore@1562 1487
mcimadamore@1562 1488 /**
mcimadamore@1562 1489 * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562 1490 * solver works in legacy mode. The steps in this enumeration reflect
mcimadamore@1562 1491 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562 1492 */
mcimadamore@1562 1493 enum LegacyInferenceSteps {
mcimadamore@1562 1494
mcimadamore@1562 1495 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1562 1496 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
mcimadamore@1562 1497
mcimadamore@1562 1498 final EnumSet<InferenceStep> steps;
mcimadamore@1562 1499
mcimadamore@1562 1500 LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
mcimadamore@1562 1501 this.steps = steps;
mcimadamore@1562 1502 }
mcimadamore@1562 1503 }
mcimadamore@1562 1504
mcimadamore@1562 1505 /**
mcimadamore@1562 1506 * This enumeration defines the sequence of steps to be applied when the
mcimadamore@1562 1507 * graph solver is used. This order is defined so as to maximize compatibility
mcimadamore@1562 1508 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
mcimadamore@1562 1509 */
mcimadamore@1562 1510 enum GraphInferenceSteps {
mcimadamore@1562 1511
mcimadamore@1562 1512 EQ(EnumSet.of(InferenceStep.EQ)),
mcimadamore@1562 1513 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
mcimadamore@1898 1514 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
mcimadamore@1562 1515
mcimadamore@1562 1516 final EnumSet<InferenceStep> steps;
mcimadamore@1562 1517
mcimadamore@1562 1518 GraphInferenceSteps(EnumSet<InferenceStep> steps) {
mcimadamore@1562 1519 this.steps = steps;
mcimadamore@1562 1520 }
mcimadamore@1562 1521 }
mcimadamore@1562 1522
mcimadamore@1562 1523 /**
vromero@2000 1524 * There are two kinds of dependencies between inference variables. The basic
vromero@2000 1525 * kind of dependency (or bound dependency) arises when a variable mention
vromero@2000 1526 * another variable in one of its bounds. There's also a more subtle kind
vromero@2000 1527 * of dependency that arises when a variable 'might' lead to better constraints
vromero@2000 1528 * on another variable (this is typically the case with variables holding up
vromero@2000 1529 * stuck expressions).
vromero@2000 1530 */
vromero@2000 1531 enum DependencyKind implements GraphUtils.DependencyKind {
vromero@2000 1532
vromero@2000 1533 /** bound dependency */
vromero@2000 1534 BOUND("dotted"),
vromero@2000 1535 /** stuck dependency */
vromero@2000 1536 STUCK("dashed");
vromero@2000 1537
vromero@2000 1538 final String dotSyle;
vromero@2000 1539
vromero@2000 1540 private DependencyKind(String dotSyle) {
vromero@2000 1541 this.dotSyle = dotSyle;
vromero@2000 1542 }
vromero@2000 1543
vromero@2000 1544 @Override
vromero@2000 1545 public String getDotStyle() {
vromero@2000 1546 return dotSyle;
vromero@2000 1547 }
vromero@2000 1548 }
vromero@2000 1549
vromero@2000 1550 /**
mcimadamore@1562 1551 * This is the graph inference solver - the solver organizes all inference variables in
mcimadamore@1562 1552 * a given inference context by bound dependencies - in the general case, such dependencies
mcimadamore@1562 1553 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
mcimadamore@1562 1554 * an acyclic graph, where all cyclic variables are bundled together. An inference
mcimadamore@1562 1555 * step corresponds to solving a node in the acyclic graph - this is done by
mcimadamore@1562 1556 * relying on a given strategy (see GraphStrategy).
mcimadamore@1562 1557 */
mcimadamore@1562 1558 class GraphSolver {
mcimadamore@1562 1559
mcimadamore@1562 1560 InferenceContext inferenceContext;
vromero@2000 1561 Map<Type, Set<Type>> stuckDeps;
mcimadamore@1562 1562 Warner warn;
mcimadamore@1562 1563
vromero@2000 1564 GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) {
mcimadamore@1562 1565 this.inferenceContext = inferenceContext;
vromero@2000 1566 this.stuckDeps = stuckDeps;
mcimadamore@1562 1567 this.warn = warn;
mcimadamore@1562 1568 }
mcimadamore@1562 1569
mcimadamore@1562 1570 /**
mcimadamore@1562 1571 * Solve variables in a given inference context. The amount of variables
mcimadamore@1562 1572 * to be solved, and the way in which the underlying acyclic graph is explored
mcimadamore@1562 1573 * depends on the selected solver strategy.
mcimadamore@1562 1574 */
mcimadamore@1562 1575 void solve(GraphStrategy sstrategy) {
mcimadamore@1562 1576 checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
vromero@2000 1577 InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps);
mcimadamore@1562 1578 while (!sstrategy.done()) {
mcimadamore@1562 1579 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
mcimadamore@1562 1580 List<Type> varsToSolve = List.from(nodeToSolve.data);
mcimadamore@1891 1581 List<Type> saved_undet = inferenceContext.save();
mcimadamore@1562 1582 try {
mcimadamore@1562 1583 //repeat until all variables are solved
mcimadamore@1562 1584 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
mcimadamore@1562 1585 //for each inference phase
mcimadamore@1562 1586 for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
mcimadamore@1562 1587 if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
mcimadamore@1562 1588 checkWithinBounds(inferenceContext, warn);
mcimadamore@1562 1589 continue outer;
mcimadamore@1562 1590 }
mcimadamore@1562 1591 }
mcimadamore@1562 1592 //no progress
vromero@1826 1593 throw inferenceException.setMessage();
mcimadamore@1562 1594 }
mcimadamore@1562 1595 }
mcimadamore@1562 1596 catch (InferenceException ex) {
vromero@1826 1597 //did we fail because of interdependent ivars?
mcimadamore@1891 1598 inferenceContext.rollback(saved_undet);
mcimadamore@1562 1599 instantiateAsUninferredVars(varsToSolve, inferenceContext);
mcimadamore@1562 1600 checkWithinBounds(inferenceContext, warn);
mcimadamore@1562 1601 }
mcimadamore@1562 1602 inferenceGraph.deleteNode(nodeToSolve);
mcimadamore@1562 1603 }
mcimadamore@1562 1604 }
mcimadamore@1562 1605
mcimadamore@1562 1606 /**
mcimadamore@1562 1607 * The dependencies between the inference variables that need to be solved
mcimadamore@1562 1608 * form a (possibly cyclic) graph. This class reduces the original dependency graph
mcimadamore@1562 1609 * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
mcimadamore@1562 1610 */
mcimadamore@1562 1611 class InferenceGraph {
mcimadamore@1562 1612
mcimadamore@1562 1613 /**
mcimadamore@1562 1614 * This class represents a node in the graph. Each node corresponds
mcimadamore@1562 1615 * to an inference variable and has edges (dependencies) on other
mcimadamore@1562 1616 * nodes. The node defines an entry point that can be used to receive
mcimadamore@1562 1617 * updates on the structure of the graph this node belongs to (used to
mcimadamore@1562 1618 * keep dependencies in sync).
mcimadamore@1562 1619 */
mcimadamore@1562 1620 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> {
mcimadamore@1562 1621
vromero@2000 1622 /** map listing all dependencies (grouped by kind) */
vromero@2000 1623 EnumMap<DependencyKind, Set<Node>> deps;
mcimadamore@1562 1624
mcimadamore@1562 1625 Node(Type ivar) {
mcimadamore@1562 1626 super(ListBuffer.of(ivar));
vromero@2000 1627 this.deps = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
mcimadamore@1562 1628 }
mcimadamore@1562 1629
mcimadamore@1562 1630 @Override
vromero@2000 1631 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
vromero@2000 1632 return DependencyKind.values();
mcimadamore@1562 1633 }
mcimadamore@1562 1634
mcimadamore@1562 1635 @Override
vromero@2000 1636 public String getDependencyName(GraphUtils.Node<ListBuffer<Type>> to, GraphUtils.DependencyKind dk) {
vromero@2000 1637 if (dk == DependencyKind.STUCK) return "";
vromero@2000 1638 else {
vromero@2000 1639 StringBuilder buf = new StringBuilder();
vromero@2000 1640 String sep = "";
vromero@2000 1641 for (Type from : data) {
vromero@2368 1642 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from);
vromero@2000 1643 for (Type bound : uv.getBounds(InferenceBound.values())) {
vromero@2000 1644 if (bound.containsAny(List.from(to.data))) {
vromero@2000 1645 buf.append(sep);
vromero@2000 1646 buf.append(bound);
vromero@2000 1647 sep = ",";
vromero@2000 1648 }
mcimadamore@1562 1649 }
mcimadamore@1562 1650 }
vromero@2000 1651 return buf.toString();
mcimadamore@1562 1652 }
mcimadamore@1562 1653 }
mcimadamore@1562 1654
vromero@2000 1655 @Override
vromero@2000 1656 public Iterable<? extends Node> getAllDependencies() {
vromero@2000 1657 return getDependencies(DependencyKind.values());
mcimadamore@1562 1658 }
mcimadamore@1562 1659
vromero@2000 1660 @Override
vromero@2000 1661 public Iterable<? extends TarjanNode<ListBuffer<Type>>> getDependenciesByKind(GraphUtils.DependencyKind dk) {
vromero@2000 1662 return getDependencies((DependencyKind)dk);
vromero@2000 1663 }
vromero@2000 1664
vromero@2000 1665 /**
vromero@2000 1666 * Retrieves all dependencies with given kind(s).
vromero@2000 1667 */
vromero@2000 1668 protected Set<Node> getDependencies(DependencyKind... depKinds) {
vromero@2000 1669 Set<Node> buf = new LinkedHashSet<Node>();
vromero@2000 1670 for (DependencyKind dk : depKinds) {
vromero@2000 1671 Set<Node> depsByKind = deps.get(dk);
vromero@2000 1672 if (depsByKind != null) {
vromero@2000 1673 buf.addAll(depsByKind);
vromero@2000 1674 }
vromero@2000 1675 }
vromero@2000 1676 return buf;
vromero@2000 1677 }
vromero@2000 1678
vromero@2000 1679 /**
vromero@2000 1680 * Adds dependency with given kind.
vromero@2000 1681 */
vromero@2000 1682 protected void addDependency(DependencyKind dk, Node depToAdd) {
vromero@2000 1683 Set<Node> depsByKind = deps.get(dk);
vromero@2000 1684 if (depsByKind == null) {
vromero@2000 1685 depsByKind = new LinkedHashSet<Node>();
vromero@2000 1686 deps.put(dk, depsByKind);
vromero@2000 1687 }
vromero@2000 1688 depsByKind.add(depToAdd);
vromero@2000 1689 }
vromero@2000 1690
vromero@2000 1691 /**
vromero@2000 1692 * Add multiple dependencies of same given kind.
vromero@2000 1693 */
vromero@2000 1694 protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) {
vromero@2000 1695 for (Node n : depsToAdd) {
vromero@2000 1696 addDependency(dk, n);
vromero@2000 1697 }
vromero@2000 1698 }
vromero@2000 1699
vromero@2000 1700 /**
vromero@2000 1701 * Remove a dependency, regardless of its kind.
vromero@2000 1702 */
vromero@2000 1703 protected Set<DependencyKind> removeDependency(Node n) {
vromero@2000 1704 Set<DependencyKind> removedKinds = new HashSet<>();
vromero@2000 1705 for (DependencyKind dk : DependencyKind.values()) {
vromero@2000 1706 Set<Node> depsByKind = deps.get(dk);
vromero@2000 1707 if (depsByKind == null) continue;
vromero@2000 1708 if (depsByKind.remove(n)) {
vromero@2000 1709 removedKinds.add(dk);
vromero@2000 1710 }
vromero@2000 1711 }
vromero@2000 1712 return removedKinds;
vromero@2000 1713 }
vromero@2000 1714
vromero@2000 1715 /**
vromero@2000 1716 * Compute closure of a give node, by recursively walking
vromero@2000 1717 * through all its dependencies (of given kinds)
vromero@2000 1718 */
vromero@2000 1719 protected Set<Node> closure(DependencyKind... depKinds) {
vromero@2000 1720 boolean progress = true;
vromero@2000 1721 Set<Node> closure = new HashSet<Node>();
vromero@2000 1722 closure.add(this);
vromero@2000 1723 while (progress) {
vromero@2000 1724 progress = false;
vromero@2000 1725 for (Node n1 : new HashSet<Node>(closure)) {
vromero@2000 1726 progress = closure.addAll(n1.getDependencies(depKinds));
vromero@2000 1727 }
vromero@2000 1728 }
vromero@2000 1729 return closure;
vromero@2000 1730 }
vromero@2000 1731
vromero@2000 1732 /**
vromero@2000 1733 * Is this node a leaf? This means either the node has no dependencies,
vromero@2000 1734 * or it just has self-dependencies.
vromero@2000 1735 */
vromero@2000 1736 protected boolean isLeaf() {
vromero@2000 1737 //no deps, or only one self dep
vromero@2000 1738 Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK);
vromero@2000 1739 if (allDeps.isEmpty()) return true;
vromero@2000 1740 for (Node n : allDeps) {
vromero@2000 1741 if (n != this) {
vromero@2000 1742 return false;
vromero@2000 1743 }
vromero@2000 1744 }
vromero@2000 1745 return true;
vromero@2000 1746 }
vromero@2000 1747
vromero@2000 1748 /**
vromero@2000 1749 * Merge this node with another node, acquiring its dependencies.
vromero@2000 1750 * This routine is used to merge all cyclic node together and
vromero@2000 1751 * form an acyclic graph.
vromero@2000 1752 */
vromero@2000 1753 protected void mergeWith(List<? extends Node> nodes) {
mcimadamore@1562 1754 for (Node n : nodes) {
mcimadamore@1562 1755 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
mcimadamore@1562 1756 data.appendList(n.data);
vromero@2000 1757 for (DependencyKind dk : DependencyKind.values()) {
vromero@2000 1758 addDependencies(dk, n.getDependencies(dk));
vromero@2000 1759 }
mcimadamore@1562 1760 }
mcimadamore@1562 1761 //update deps
vromero@2000 1762 EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
vromero@2000 1763 for (DependencyKind dk : DependencyKind.values()) {
vromero@2000 1764 for (Node d : getDependencies(dk)) {
vromero@2000 1765 Set<Node> depsByKind = deps2.get(dk);
vromero@2000 1766 if (depsByKind == null) {
vromero@2000 1767 depsByKind = new LinkedHashSet<Node>();
vromero@2000 1768 deps2.put(dk, depsByKind);
vromero@2000 1769 }
vromero@2000 1770 if (data.contains(d.data.first())) {
vromero@2000 1771 depsByKind.add(this);
vromero@2000 1772 } else {
vromero@2000 1773 depsByKind.add(d);
vromero@2000 1774 }
mcimadamore@1562 1775 }
mcimadamore@1562 1776 }
mcimadamore@1562 1777 deps = deps2;
mcimadamore@1562 1778 }
mcimadamore@1562 1779
vromero@2000 1780 /**
vromero@2000 1781 * Notify all nodes that something has changed in the graph
vromero@2000 1782 * topology.
vromero@2000 1783 */
vromero@2000 1784 private void graphChanged(Node from, Node to) {
vromero@2000 1785 for (DependencyKind dk : removeDependency(from)) {
mcimadamore@1562 1786 if (to != null) {
vromero@2000 1787 addDependency(dk, to);
mcimadamore@1562 1788 }
mcimadamore@1562 1789 }
mcimadamore@1562 1790 }
mcimadamore@1562 1791 }
mcimadamore@1562 1792
mcimadamore@1562 1793 /** the nodes in the inference graph */
mcimadamore@1562 1794 ArrayList<Node> nodes;
mcimadamore@1562 1795
vromero@2000 1796 InferenceGraph(Map<Type, Set<Type>> optDeps) {
vromero@2000 1797 initNodes(optDeps);
vromero@2000 1798 }
vromero@2000 1799
vromero@2000 1800 /**
vromero@2000 1801 * Basic lookup helper for retrieving a graph node given an inference
vromero@2000 1802 * variable type.
vromero@2000 1803 */
vromero@2000 1804 public Node findNode(Type t) {
vromero@2000 1805 for (Node n : nodes) {
vromero@2000 1806 if (n.data.contains(t)) {
vromero@2000 1807 return n;
vromero@2000 1808 }
vromero@2000 1809 }
vromero@2000 1810 return null;
mcimadamore@1562 1811 }
mcimadamore@1562 1812
mcimadamore@1562 1813 /**
mcimadamore@1562 1814 * Delete a node from the graph. This update the underlying structure
mcimadamore@1562 1815 * of the graph (including dependencies) via listeners updates.
mcimadamore@1562 1816 */
mcimadamore@1562 1817 public void deleteNode(Node n) {
mcimadamore@1562 1818 Assert.check(nodes.contains(n));
mcimadamore@1562 1819 nodes.remove(n);
mcimadamore@1562 1820 notifyUpdate(n, null);
mcimadamore@1562 1821 }
mcimadamore@1562 1822
mcimadamore@1562 1823 /**
mcimadamore@1562 1824 * Notify all nodes of a change in the graph. If the target node is
mcimadamore@1562 1825 * {@code null} the source node is assumed to be removed.
mcimadamore@1562 1826 */
mcimadamore@1562 1827 void notifyUpdate(Node from, Node to) {
mcimadamore@1562 1828 for (Node n : nodes) {
mcimadamore@1562 1829 n.graphChanged(from, to);
mcimadamore@1562 1830 }
mcimadamore@1562 1831 }
mcimadamore@1562 1832
mcimadamore@1562 1833 /**
mcimadamore@1562 1834 * Create the graph nodes. First a simple node is created for every inference
mcimadamore@1562 1835 * variables to be solved. Then Tarjan is used to found all connected components
mcimadamore@1562 1836 * in the graph. For each component containing more than one node, a super node is
vromero@2000 1837 * created, effectively replacing the original cyclic nodes.
mcimadamore@1562 1838 */
vromero@2000 1839 void initNodes(Map<Type, Set<Type>> stuckDeps) {
vromero@2000 1840 //add nodes
mcimadamore@1608 1841 nodes = new ArrayList<Node>();
mcimadamore@1562 1842 for (Type t : inferenceContext.restvars()) {
mcimadamore@1562 1843 nodes.add(new Node(t));
mcimadamore@1562 1844 }
vromero@2000 1845 //add dependencies
mcimadamore@1562 1846 for (Node n_i : nodes) {
mcimadamore@1562 1847 Type i = n_i.data.first();
vromero@2000 1848 Set<Type> optDepsByNode = stuckDeps.get(i);
mcimadamore@1562 1849 for (Node n_j : nodes) {
mcimadamore@1562 1850 Type j = n_j.data.first();
vromero@2368 1851 UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i);
mcimadamore@1562 1852 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
vromero@2000 1853 //update i's bound dependencies
vromero@2000 1854 n_i.addDependency(DependencyKind.BOUND, n_j);
vromero@2000 1855 }
vromero@2000 1856 if (optDepsByNode != null && optDepsByNode.contains(j)) {
vromero@2000 1857 //update i's stuck dependencies
vromero@2000 1858 n_i.addDependency(DependencyKind.STUCK, n_j);
mcimadamore@1562 1859 }
mcimadamore@1562 1860 }
mcimadamore@1562 1861 }
vromero@2000 1862 //merge cyclic nodes
mcimadamore@1608 1863 ArrayList<Node> acyclicNodes = new ArrayList<Node>();
mcimadamore@1562 1864 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
mcimadamore@1562 1865 if (conSubGraph.length() > 1) {
mcimadamore@1562 1866 Node root = conSubGraph.head;
mcimadamore@1562 1867 root.mergeWith(conSubGraph.tail);
mcimadamore@1562 1868 for (Node n : conSubGraph) {
mcimadamore@1562 1869 notifyUpdate(n, root);
mcimadamore@1562 1870 }
mcimadamore@1562 1871 }
mcimadamore@1608 1872 acyclicNodes.add(conSubGraph.head);
mcimadamore@1562 1873 }
mcimadamore@1608 1874 nodes = acyclicNodes;
mcimadamore@1562 1875 }
mcimadamore@1562 1876
mcimadamore@1562 1877 /**
mcimadamore@1562 1878 * Debugging: dot representation of this graph
mcimadamore@1562 1879 */
mcimadamore@1562 1880 String toDot() {
mcimadamore@1562 1881 StringBuilder buf = new StringBuilder();
mcimadamore@1562 1882 for (Type t : inferenceContext.undetvars) {
mcimadamore@1562 1883 UndetVar uv = (UndetVar)t;
mcimadamore@1562 1884 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
mcimadamore@1562 1885 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
mcimadamore@1562 1886 uv.getBounds(InferenceBound.EQ)));
mcimadamore@1562 1887 }
mcimadamore@1562 1888 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
mcimadamore@1562 1889 }
mcimadamore@1562 1890 }
mcimadamore@1562 1891 }
mcimadamore@1562 1892 // </editor-fold>
mcimadamore@1562 1893
mcimadamore@1562 1894 // <editor-fold defaultstate="collapsed" desc="Inference context">
mcimadamore@1562 1895 /**
mcimadamore@1550 1896 * Functional interface for defining inference callbacks. Certain actions
mcimadamore@1550 1897 * (i.e. subtyping checks) might need to be redone after all inference variables
mcimadamore@1550 1898 * have been fixed.
mcimadamore@1337 1899 */
mcimadamore@1550 1900 interface FreeTypeListener {
mcimadamore@1550 1901 void typesInferred(InferenceContext inferenceContext);
mcimadamore@1550 1902 }
mcimadamore@1337 1903
mcimadamore@1337 1904 /**
mcimadamore@1337 1905 * An inference context keeps track of the set of variables that are free
mcimadamore@1337 1906 * in the current context. It provides utility methods for opening/closing
mcimadamore@1337 1907 * types to their corresponding free/closed forms. It also provide hooks for
mcimadamore@1337 1908 * attaching deferred post-inference action (see PendingCheck). Finally,
mcimadamore@1337 1909 * it can be used as an entry point for performing upper/lower bound inference
mcimadamore@1337 1910 * (see InferenceKind).
mcimadamore@1337 1911 */
mcimadamore@1562 1912 class InferenceContext {
mcimadamore@1337 1913
mcimadamore@1337 1914 /** list of inference vars as undet vars */
mcimadamore@1337 1915 List<Type> undetvars;
mcimadamore@1337 1916
mcimadamore@1337 1917 /** list of inference vars in this context */
mcimadamore@1337 1918 List<Type> inferencevars;
mcimadamore@1337 1919
mcimadamore@1337 1920 java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =
mcimadamore@1337 1921 new java.util.HashMap<FreeTypeListener, List<Type>>();
mcimadamore@1337 1922
mcimadamore@1337 1923 List<FreeTypeListener> freetypeListeners = List.nil();
mcimadamore@1337 1924
mcimadamore@1550 1925 public InferenceContext(List<Type> inferencevars) {
mcimadamore@1550 1926 this.undetvars = Type.map(inferencevars, fromTypeVarFun);
mcimadamore@1337 1927 this.inferencevars = inferencevars;
mcimadamore@1337 1928 }
mcimadamore@1550 1929 //where
mcimadamore@1550 1930 Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
mcimadamore@1550 1931 // mapping that turns inference variables into undet vars
mcimadamore@1550 1932 public Type apply(Type t) {
mcimadamore@1898 1933 if (t.hasTag(TYPEVAR)) {
mcimadamore@1898 1934 TypeVar tv = (TypeVar)t;
vromero@2157 1935 if (tv.isCaptured()) {
vromero@2157 1936 return new CapturedUndetVar((CapturedType)tv, types);
vromero@2157 1937 } else {
vromero@2157 1938 return new UndetVar(tv, types);
vromero@2157 1939 }
mcimadamore@1898 1940 } else {
mcimadamore@1898 1941 return t.map(this);
mcimadamore@1898 1942 }
mcimadamore@1550 1943 }
mcimadamore@1550 1944 };
mcimadamore@1337 1945
mcimadamore@1337 1946 /**
mcimadamore@1898 1947 * add a new inference var to this inference context
mcimadamore@1898 1948 */
mcimadamore@1898 1949 void addVar(TypeVar t) {
mcimadamore@1898 1950 this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));
mcimadamore@1898 1951 this.inferencevars = this.inferencevars.prepend(t);
mcimadamore@1898 1952 }
mcimadamore@1898 1953
mcimadamore@1898 1954 /**
mcimadamore@1337 1955 * returns the list of free variables (as type-variables) in this
mcimadamore@1337 1956 * inference context
mcimadamore@1337 1957 */
mcimadamore@1337 1958 List<Type> inferenceVars() {
mcimadamore@1337 1959 return inferencevars;
mcimadamore@1337 1960 }
mcimadamore@1337 1961
mcimadamore@1337 1962 /**
mcimadamore@1337 1963 * returns the list of uninstantiated variables (as type-variables) in this
mcimadamore@1550 1964 * inference context
mcimadamore@1337 1965 */
mcimadamore@1337 1966 List<Type> restvars() {
mcimadamore@1550 1967 return filterVars(new Filter<UndetVar>() {
mcimadamore@1550 1968 public boolean accepts(UndetVar uv) {
mcimadamore@1550 1969 return uv.inst == null;
mcimadamore@1337 1970 }
mcimadamore@1550 1971 });
mcimadamore@1550 1972 }
mcimadamore@1550 1973
mcimadamore@1550 1974 /**
mcimadamore@1550 1975 * returns the list of instantiated variables (as type-variables) in this
mcimadamore@1550 1976 * inference context
mcimadamore@1550 1977 */
mcimadamore@1550 1978 List<Type> instvars() {
mcimadamore@1550 1979 return filterVars(new Filter<UndetVar>() {
mcimadamore@1550 1980 public boolean accepts(UndetVar uv) {
mcimadamore@1550 1981 return uv.inst != null;
mcimadamore@1550 1982 }
mcimadamore@1550 1983 });
mcimadamore@1550 1984 }
mcimadamore@1550 1985
mcimadamore@1550 1986 /**
mcimadamore@1550 1987 * Get list of bounded inference variables (where bound is other than
mcimadamore@1550 1988 * declared bounds).
mcimadamore@1550 1989 */
mcimadamore@1550 1990 final List<Type> boundedVars() {
mcimadamore@1550 1991 return filterVars(new Filter<UndetVar>() {
mcimadamore@1550 1992 public boolean accepts(UndetVar uv) {
mcimadamore@1550 1993 return uv.getBounds(InferenceBound.UPPER)
vromero@2000 1994 .diff(uv.getDeclaredBounds())
vromero@2000 1995 .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
mcimadamore@1550 1996 }
mcimadamore@1550 1997 });
mcimadamore@1550 1998 }
mcimadamore@1550 1999
vromero@2368 2000 /* Returns the corresponding inference variables.
vromero@2368 2001 */
mcimadamore@1550 2002 private List<Type> filterVars(Filter<UndetVar> fu) {
alundblad@2047 2003 ListBuffer<Type> res = new ListBuffer<>();
mcimadamore@1550 2004 for (Type t : undetvars) {
mcimadamore@1550 2005 UndetVar uv = (UndetVar)t;
mcimadamore@1550 2006 if (fu.accepts(uv)) {
mcimadamore@1550 2007 res.append(uv.qtype);
mcimadamore@1550 2008 }
mcimadamore@1337 2009 }
mcimadamore@1550 2010 return res.toList();
mcimadamore@1337 2011 }
mcimadamore@1337 2012
mcimadamore@1337 2013 /**
mcimadamore@1337 2014 * is this type free?
mcimadamore@1337 2015 */
mcimadamore@1337 2016 final boolean free(Type t) {
mcimadamore@1337 2017 return t.containsAny(inferencevars);
mcimadamore@1337 2018 }
mcimadamore@1337 2019
mcimadamore@1337 2020 final boolean free(List<Type> ts) {
mcimadamore@1337 2021 for (Type t : ts) {
mcimadamore@1337 2022 if (free(t)) return true;
mcimadamore@1337 2023 }
mcimadamore@1337 2024 return false;
mcimadamore@1337 2025 }
mcimadamore@1337 2026
mcimadamore@1337 2027 /**
mcimadamore@1337 2028 * Returns a list of free variables in a given type
mcimadamore@1337 2029 */
mcimadamore@1337 2030 final List<Type> freeVarsIn(Type t) {
alundblad@2047 2031 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337 2032 for (Type iv : inferenceVars()) {
mcimadamore@1337 2033 if (t.contains(iv)) {
mcimadamore@1337 2034 buf.add(iv);
mcimadamore@1337 2035 }
mcimadamore@1337 2036 }
mcimadamore@1337 2037 return buf.toList();
mcimadamore@1337 2038 }
mcimadamore@1337 2039
mcimadamore@1337 2040 final List<Type> freeVarsIn(List<Type> ts) {
alundblad@2047 2041 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337 2042 for (Type t : ts) {
mcimadamore@1337 2043 buf.appendList(freeVarsIn(t));
mcimadamore@1337 2044 }
alundblad@2047 2045 ListBuffer<Type> buf2 = new ListBuffer<>();
mcimadamore@1337 2046 for (Type t : buf) {
mcimadamore@1337 2047 if (!buf2.contains(t)) {
mcimadamore@1337 2048 buf2.add(t);
mcimadamore@1337 2049 }
mcimadamore@1337 2050 }
mcimadamore@1337 2051 return buf2.toList();
mcimadamore@1337 2052 }
mcimadamore@1337 2053
mcimadamore@1337 2054 /**
mcimadamore@1337 2055 * Replace all free variables in a given type with corresponding
mcimadamore@1337 2056 * undet vars (used ahead of subtyping/compatibility checks to allow propagation
mcimadamore@1337 2057 * of inference constraints).
mcimadamore@1337 2058 */
vromero@2368 2059 final Type asUndetVar(Type t) {
mcimadamore@1337 2060 return types.subst(t, inferencevars, undetvars);
mcimadamore@1337 2061 }
mcimadamore@1337 2062
vromero@2368 2063 final List<Type> asUndetVars(List<Type> ts) {
alundblad@2047 2064 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337 2065 for (Type t : ts) {
vromero@2368 2066 buf.append(asUndetVar(t));
mcimadamore@1337 2067 }
mcimadamore@1337 2068 return buf.toList();
mcimadamore@1337 2069 }
mcimadamore@1337 2070
mcimadamore@1337 2071 List<Type> instTypes() {
alundblad@2047 2072 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337 2073 for (Type t : undetvars) {
mcimadamore@1337 2074 UndetVar uv = (UndetVar)t;
mcimadamore@1337 2075 buf.append(uv.inst != null ? uv.inst : uv.qtype);
mcimadamore@1337 2076 }
mcimadamore@1337 2077 return buf.toList();
mcimadamore@1337 2078 }
mcimadamore@1337 2079
mcimadamore@1337 2080 /**
mcimadamore@1337 2081 * Replace all free variables in a given type with corresponding
mcimadamore@1337 2082 * instantiated types - if one or more free variable has not been
mcimadamore@1337 2083 * fully instantiated, it will still be available in the resulting type.
mcimadamore@1337 2084 */
mcimadamore@1550 2085 Type asInstType(Type t) {
mcimadamore@1337 2086 return types.subst(t, inferencevars, instTypes());
mcimadamore@1337 2087 }
mcimadamore@1337 2088
mcimadamore@1550 2089 List<Type> asInstTypes(List<Type> ts) {
alundblad@2047 2090 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1337 2091 for (Type t : ts) {
mcimadamore@1550 2092 buf.append(asInstType(t));
mcimadamore@1337 2093 }
mcimadamore@1337 2094 return buf.toList();
mcimadamore@1337 2095 }
mcimadamore@1337 2096
mcimadamore@1337 2097 /**
mcimadamore@1337 2098 * Add custom hook for performing post-inference action
mcimadamore@1337 2099 */
mcimadamore@1337 2100 void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
mcimadamore@1337 2101 freeTypeListeners.put(ftl, freeVarsIn(types));
mcimadamore@1337 2102 }
mcimadamore@1337 2103
mcimadamore@1337 2104 /**
mcimadamore@1337 2105 * Mark the inference context as complete and trigger evaluation
mcimadamore@1337 2106 * of all deferred checks.
mcimadamore@1337 2107 */
mcimadamore@1550 2108 void notifyChange() {
mcimadamore@1562 2109 notifyChange(inferencevars.diff(restvars()));
mcimadamore@1562 2110 }
mcimadamore@1562 2111
mcimadamore@1562 2112 void notifyChange(List<Type> inferredVars) {
mcimadamore@1337 2113 InferenceException thrownEx = null;
mcimadamore@1337 2114 for (Map.Entry<FreeTypeListener, List<Type>> entry :
mcimadamore@1337 2115 new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {
mcimadamore@1562 2116 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
mcimadamore@1337 2117 try {
mcimadamore@1337 2118 entry.getKey().typesInferred(this);
mcimadamore@1337 2119 freeTypeListeners.remove(entry.getKey());
mcimadamore@1337 2120 } catch (InferenceException ex) {
mcimadamore@1337 2121 if (thrownEx == null) {
mcimadamore@1337 2122 thrownEx = ex;
mcimadamore@1337 2123 }
mcimadamore@1337 2124 }
mcimadamore@1337 2125 }
mcimadamore@1337 2126 }
mcimadamore@1337 2127 //inference exception multiplexing - present any inference exception
mcimadamore@1337 2128 //thrown when processing listeners as a single one
mcimadamore@1337 2129 if (thrownEx != null) {
mcimadamore@1337 2130 throw thrownEx;
mcimadamore@1337 2131 }
mcimadamore@1337 2132 }
mcimadamore@1347 2133
mcimadamore@1562 2134 /**
mcimadamore@1562 2135 * Save the state of this inference context
mcimadamore@1562 2136 */
mcimadamore@1891 2137 List<Type> save() {
alundblad@2047 2138 ListBuffer<Type> buf = new ListBuffer<>();
mcimadamore@1562 2139 for (Type t : undetvars) {
mcimadamore@1562 2140 UndetVar uv = (UndetVar)t;
mcimadamore@1562 2141 UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
mcimadamore@1562 2142 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1562 2143 for (Type b : uv.getBounds(ib)) {
mcimadamore@1562 2144 uv2.addBound(ib, b, types);
mcimadamore@1562 2145 }
mcimadamore@1562 2146 }
mcimadamore@1562 2147 uv2.inst = uv.inst;
mcimadamore@1562 2148 buf.add(uv2);
mcimadamore@1562 2149 }
mcimadamore@1891 2150 return buf.toList();
mcimadamore@1562 2151 }
mcimadamore@1562 2152
mcimadamore@1562 2153 /**
mcimadamore@1562 2154 * Restore the state of this inference context to the previous known checkpoint
mcimadamore@1562 2155 */
mcimadamore@1891 2156 void rollback(List<Type> saved_undet) {
mcimadamore@1891 2157 Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
mcimadamore@1891 2158 //restore bounds (note: we need to preserve the old instances)
mcimadamore@1891 2159 for (Type t : undetvars) {
mcimadamore@1891 2160 UndetVar uv = (UndetVar)t;
mcimadamore@1891 2161 UndetVar uv_saved = (UndetVar)saved_undet.head;
mcimadamore@1891 2162 for (InferenceBound ib : InferenceBound.values()) {
mcimadamore@1891 2163 uv.setBounds(ib, uv_saved.getBounds(ib));
mcimadamore@1891 2164 }
mcimadamore@1891 2165 uv.inst = uv_saved.inst;
mcimadamore@1891 2166 saved_undet = saved_undet.tail;
mcimadamore@1891 2167 }
mcimadamore@1562 2168 }
mcimadamore@1562 2169
mcimadamore@1562 2170 /**
mcimadamore@1562 2171 * Copy variable in this inference context to the given context
mcimadamore@1562 2172 */
mcimadamore@1562 2173 void dupTo(final InferenceContext that) {
vromero@2382 2174 that.inferencevars = that.inferencevars.appendList(
vromero@2382 2175 inferencevars.diff(that.inferencevars));
vromero@2382 2176 that.undetvars = that.undetvars.appendList(
vromero@2382 2177 undetvars.diff(that.undetvars));
mcimadamore@1562 2178 //set up listeners to notify original inference contexts as
mcimadamore@1562 2179 //propagated vars are inferred in new context
mcimadamore@1562 2180 for (Type t : inferencevars) {
mcimadamore@1562 2181 that.freeTypeListeners.put(new FreeTypeListener() {
mcimadamore@1562 2182 public void typesInferred(InferenceContext inferenceContext) {
mcimadamore@1562 2183 InferenceContext.this.notifyChange();
mcimadamore@1562 2184 }
mcimadamore@1562 2185 }, List.of(t));
mcimadamore@1562 2186 }
mcimadamore@1562 2187 }
mcimadamore@1562 2188
vromero@2000 2189 private void solve(GraphStrategy ss, Warner warn) {
vromero@2000 2190 solve(ss, new HashMap<Type, Set<Type>>(), warn);
vromero@2000 2191 }
vromero@2000 2192
mcimadamore@1562 2193 /**
mcimadamore@1562 2194 * Solve with given graph strategy.
mcimadamore@1562 2195 */
vromero@2000 2196 private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) {
vromero@2000 2197 GraphSolver s = new GraphSolver(this, stuckDeps, warn);
mcimadamore@1562 2198 s.solve(ss);
mcimadamore@1562 2199 }
mcimadamore@1562 2200
mcimadamore@1562 2201 /**
mcimadamore@1562 2202 * Solve all variables in this context.
mcimadamore@1562 2203 */
mcimadamore@1562 2204 public void solve(Warner warn) {
mcimadamore@1562 2205 solve(new LeafSolver() {
mcimadamore@1562 2206 public boolean done() {
mcimadamore@1562 2207 return restvars().isEmpty();
mcimadamore@1562 2208 }
mcimadamore@1562 2209 }, warn);
mcimadamore@1562 2210 }
mcimadamore@1562 2211
mcimadamore@1562 2212 /**
mcimadamore@1562 2213 * Solve all variables in the given list.
mcimadamore@1562 2214 */
mcimadamore@1562 2215 public void solve(final List<Type> vars, Warner warn) {
mcimadamore@1562 2216 solve(new BestLeafSolver(vars) {
mcimadamore@1562 2217 public boolean done() {
mcimadamore@1562 2218 return !free(asInstTypes(vars));
mcimadamore@1562 2219 }
mcimadamore@1562 2220 }, warn);
mcimadamore@1562 2221 }
mcimadamore@1562 2222
mcimadamore@1562 2223 /**
mcimadamore@1562 2224 * Solve at least one variable in given list.
mcimadamore@1562 2225 */
vromero@2000 2226 public void solveAny(List<Type> varsToSolve, Map<Type, Set<Type>> optDeps, Warner warn) {
vromero@2000 2227 solve(new BestLeafSolver(varsToSolve.intersect(restvars())) {
mcimadamore@1562 2228 public boolean done() {
mcimadamore@1562 2229 return instvars().intersect(varsToSolve).nonEmpty();
mcimadamore@1562 2230 }
vromero@2000 2231 }, optDeps, warn);
mcimadamore@1562 2232 }
mcimadamore@1562 2233
mcimadamore@1562 2234 /**
mcimadamore@1562 2235 * Apply a set of inference steps
mcimadamore@1562 2236 */
mcimadamore@1562 2237 private boolean solveBasic(EnumSet<InferenceStep> steps) {
mcimadamore@1562 2238 return solveBasic(inferencevars, steps);
mcimadamore@1562 2239 }
mcimadamore@1562 2240
mcimadamore@1562 2241 private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
mcimadamore@1562 2242 boolean changed = false;
mcimadamore@1562 2243 for (Type t : varsToSolve.intersect(restvars())) {
vromero@2368 2244 UndetVar uv = (UndetVar)asUndetVar(t);
mcimadamore@1562 2245 for (InferenceStep step : steps) {
mcimadamore@1562 2246 if (step.accepts(uv, this)) {
mcimadamore@1562 2247 uv.inst = step.solve(uv, this);
mcimadamore@1562 2248 changed = true;
mcimadamore@1562 2249 break;
mcimadamore@1347 2250 }
mcimadamore@1347 2251 }
mcimadamore@1347 2252 }
mcimadamore@1562 2253 return changed;
mcimadamore@1562 2254 }
mcimadamore@1562 2255
mcimadamore@1562 2256 /**
mcimadamore@1562 2257 * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
mcimadamore@1562 2258 * During overload resolution, instantiation is done by doing a partial
mcimadamore@1562 2259 * inference process using eq/lower bound instantiation. During check,
mcimadamore@1562 2260 * we also instantiate any remaining vars by repeatedly using eq/upper
mcimadamore@1562 2261 * instantiation, until all variables are solved.
mcimadamore@1562 2262 */
mcimadamore@1562 2263 public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
mcimadamore@1562 2264 while (true) {
mcimadamore@1562 2265 boolean stuck = !solveBasic(steps);
mcimadamore@1562 2266 if (restvars().isEmpty() || partial) {
mcimadamore@1562 2267 //all variables have been instantiated - exit
mcimadamore@1562 2268 break;
mcimadamore@1562 2269 } else if (stuck) {
mcimadamore@1562 2270 //some variables could not be instantiated because of cycles in
mcimadamore@1562 2271 //upper bounds - provide a (possibly recursive) default instantiation
mcimadamore@1562 2272 instantiateAsUninferredVars(restvars(), this);
mcimadamore@1562 2273 break;
mcimadamore@1562 2274 } else {
mcimadamore@1562 2275 //some variables have been instantiated - replace newly instantiated
mcimadamore@1562 2276 //variables in remaining upper bounds and continue
mcimadamore@1562 2277 for (Type t : undetvars) {
mcimadamore@1562 2278 UndetVar uv = (UndetVar)t;
mcimadamore@1562 2279 uv.substBounds(inferenceVars(), instTypes(), types);
mcimadamore@1562 2280 }
mcimadamore@1562 2281 }
mcimadamore@1347 2282 }
mcimadamore@1562 2283 checkWithinBounds(this, warn);
mcimadamore@1562 2284 }
mcimadamore@1562 2285
mcimadamore@1562 2286 private Infer infer() {
mcimadamore@1562 2287 //back-door to infer
mcimadamore@1562 2288 return Infer.this;
mcimadamore@1347 2289 }
vromero@2302 2290
vromero@2302 2291 @Override
vromero@2302 2292 public String toString() {
vromero@2302 2293 return "Inference vars: " + inferencevars + '\n' +
vromero@2302 2294 "Undet vars: " + undetvars;
vromero@2302 2295 }
vromero@2382 2296
vromero@2382 2297 /* Method Types.capture() generates a new type every time it's applied
vromero@2382 2298 * to a wildcard parameterized type. This is intended functionality but
vromero@2382 2299 * there are some cases when what you need is not to generate a new
vromero@2382 2300 * captured type but to check that a previously generated captured type
vromero@2382 2301 * is correct. There are cases when caching a captured type for later
vromero@2382 2302 * reuse is sound. In general two captures from the same AST are equal.
vromero@2382 2303 * This is why the tree is used as the key of the map below. This map
vromero@2382 2304 * stores a Type per AST.
vromero@2382 2305 */
vromero@2382 2306 Map<JCTree, Type> captureTypeCache = new HashMap<>();
vromero@2382 2307
vromero@2382 2308 Type cachedCapture(JCTree tree, Type t, boolean readOnly) {
vromero@2382 2309 Type captured = captureTypeCache.get(tree);
vromero@2382 2310 if (captured != null) {
vromero@2382 2311 return captured;
vromero@2382 2312 }
vromero@2382 2313
vromero@2382 2314 Type result = types.capture(t);
vromero@2382 2315 if (result != t && !readOnly) { // then t is a wildcard parameterized type
vromero@2382 2316 captureTypeCache.put(tree, result);
vromero@2382 2317 }
vromero@2382 2318 return result;
vromero@2382 2319 }
mcimadamore@895 2320 }
mcimadamore@1337 2321
mcimadamore@1550 2322 final InferenceContext emptyContext = new InferenceContext(List.<Type>nil());
mcimadamore@1550 2323 // </editor-fold>
mcimadamore@1337 2324 }

mercurial