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