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