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