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