Infer.java revision 3323:680712ce0386
1/* 2 * Copyright (c) 1999, 2016, 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.UndetVar.UndetVarListener; 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.DeferredAttr.DeferredAttrContext; 42import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; 43import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; 44import com.sun.tools.javac.comp.Resolve.InapplicableMethodException; 45import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; 46 47import java.io.IOException; 48import java.io.Writer; 49import java.nio.file.Files; 50import java.nio.file.Path; 51import java.nio.file.Paths; 52import java.util.ArrayList; 53import java.util.Collection; 54import java.util.Collections; 55import java.util.EnumMap; 56import java.util.EnumSet; 57import java.util.HashMap; 58import java.util.HashSet; 59import java.util.LinkedHashSet; 60import java.util.Map; 61import java.util.Properties; 62import java.util.Set; 63import java.util.function.BiFunction; 64import java.util.function.BiPredicate; 65 66import static com.sun.tools.javac.code.TypeTag.*; 67 68/** Helper class for type parameter inference, used by the attribution phase. 69 * 70 * <p><b>This is NOT part of any supported API. 71 * If you write code that depends on this, you do so at your own risk. 72 * This code and its internal interfaces are subject to change or 73 * deletion without notice.</b> 74 */ 75public class Infer { 76 protected static final Context.Key<Infer> inferKey = new Context.Key<>(); 77 78 Resolve rs; 79 Check chk; 80 Symtab syms; 81 Types types; 82 JCDiagnostic.Factory diags; 83 Log log; 84 85 /** should the graph solver be used? */ 86 boolean allowGraphInference; 87 88 /** 89 * folder in which the inference dependency graphs should be written. 90 */ 91 final private String dependenciesFolder; 92 93 /** 94 * List of graphs awaiting to be dumped to a file. 95 */ 96 private List<String> pendingGraphs; 97 98 public static Infer instance(Context context) { 99 Infer instance = context.get(inferKey); 100 if (instance == null) 101 instance = new Infer(context); 102 return instance; 103 } 104 105 protected Infer(Context context) { 106 context.put(inferKey, this); 107 108 rs = Resolve.instance(context); 109 chk = Check.instance(context); 110 syms = Symtab.instance(context); 111 types = Types.instance(context); 112 diags = JCDiagnostic.Factory.instance(context); 113 log = Log.instance(context); 114 inferenceException = new InferenceException(diags); 115 Options options = Options.instance(context); 116 allowGraphInference = Source.instance(context).allowGraphInference() 117 && options.isUnset("useLegacyInference"); 118 dependenciesFolder = options.get("dumpInferenceGraphsTo"); 119 pendingGraphs = List.nil(); 120 121 emptyContext = new InferenceContext(this, List.<Type>nil()); 122 } 123 124 /** A value for prototypes that admit any type, including polymorphic ones. */ 125 public static final Type anyPoly = new JCNoType(); 126 127 /** 128 * This exception class is design to store a list of diagnostics corresponding 129 * to inference errors that can arise during a method applicability check. 130 */ 131 public static class InferenceException extends InapplicableMethodException { 132 private static final long serialVersionUID = 0; 133 134 List<JCDiagnostic> messages = List.nil(); 135 136 InferenceException(JCDiagnostic.Factory diags) { 137 super(diags); 138 } 139 140 @Override 141 InapplicableMethodException setMessage() { 142 //no message to set 143 return this; 144 } 145 146 @Override 147 InapplicableMethodException setMessage(JCDiagnostic diag) { 148 messages = messages.append(diag); 149 return this; 150 } 151 152 @Override 153 public JCDiagnostic getDiagnostic() { 154 return messages.head; 155 } 156 157 void clear() { 158 messages = List.nil(); 159 } 160 } 161 162 protected final InferenceException inferenceException; 163 164 // <editor-fold defaultstate="collapsed" desc="Inference routines"> 165 /** 166 * Main inference entry point - instantiate a generic method type 167 * using given argument types and (possibly) an expected target-type. 168 */ 169 Type instantiateMethod( Env<AttrContext> env, 170 List<Type> tvars, 171 MethodType mt, 172 Attr.ResultInfo resultInfo, 173 MethodSymbol msym, 174 List<Type> argtypes, 175 boolean allowBoxing, 176 boolean useVarargs, 177 Resolve.MethodResolutionContext resolveContext, 178 Warner warn) throws InferenceException { 179 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG 180 final InferenceContext inferenceContext = new InferenceContext(this, tvars); //B0 181 inferenceException.clear(); 182 try { 183 DeferredAttr.DeferredAttrContext deferredAttrContext = 184 resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn); 185 186 resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2 187 argtypes, mt.getParameterTypes(), warn); 188 189 if (allowGraphInference && resultInfo != null && resultInfo.pt == anyPoly) { 190 doIncorporation(inferenceContext, warn); 191 //we are inside method attribution - just return a partially inferred type 192 return new PartiallyInferredMethodType(mt, inferenceContext, env, warn); 193 } else if (allowGraphInference && 194 resultInfo != null && 195 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 196 //inject return constraints earlier 197 doIncorporation(inferenceContext, warn); //propagation 198 199 boolean shouldPropagate = resultInfo.checkContext.inferenceContext().free(resultInfo.pt); 200 201 InferenceContext minContext = shouldPropagate ? 202 inferenceContext.min(roots(mt, deferredAttrContext), true, warn) : 203 inferenceContext; 204 205 Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3 206 mt, minContext); 207 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype); 208 209 //propagate outwards if needed 210 if (shouldPropagate) { 211 //propagate inference context outwards and exit 212 minContext.dupTo(resultInfo.checkContext.inferenceContext()); 213 deferredAttrContext.complete(); 214 return mt; 215 } 216 } 217 218 deferredAttrContext.complete(); 219 220 // minimize as yet undetermined type variables 221 if (allowGraphInference) { 222 inferenceContext.solve(warn); 223 } else { 224 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst 225 } 226 227 mt = (MethodType)inferenceContext.asInstType(mt); 228 229 if (!allowGraphInference && 230 inferenceContext.restvars().nonEmpty() && 231 resultInfo != null && 232 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 233 generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext); 234 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst 235 mt = (MethodType)inferenceContext.asInstType(mt); 236 } 237 238 if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) { 239 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt); 240 } 241 242 // return instantiated version of method type 243 return mt; 244 } finally { 245 if (resultInfo != null || !allowGraphInference) { 246 inferenceContext.notifyChange(); 247 } else { 248 inferenceContext.notifyChange(inferenceContext.boundedVars()); 249 } 250 if (resultInfo == null) { 251 /* if the is no result info then we can clear the capture types 252 * cache without affecting any result info check 253 */ 254 inferenceContext.captureTypeCache.clear(); 255 } 256 dumpGraphsIfNeeded(env.tree, msym, resolveContext); 257 } 258 } 259 //where 260 private List<Type> roots(MethodType mt, DeferredAttrContext deferredAttrContext) { 261 ListBuffer<Type> roots = new ListBuffer<>(); 262 roots.add(mt.getReturnType()); 263 if (deferredAttrContext != null && deferredAttrContext.mode == AttrMode.CHECK) { 264 roots.addAll(mt.getThrownTypes()); 265 for (DeferredAttr.DeferredAttrNode n : deferredAttrContext.deferredAttrNodes) { 266 roots.addAll(n.deferredStuckPolicy.stuckVars()); 267 roots.addAll(n.deferredStuckPolicy.depVars()); 268 } 269 } 270 return roots.toList(); 271 } 272 273 /** 274 * A partially infered method/constructor type; such a type can be checked multiple times 275 * against different targets. 276 */ 277 public class PartiallyInferredMethodType extends MethodType { 278 public PartiallyInferredMethodType(MethodType mtype, InferenceContext inferenceContext, Env<AttrContext> env, Warner warn) { 279 super(mtype.getParameterTypes(), mtype.getReturnType(), mtype.getThrownTypes(), mtype.tsym); 280 this.inferenceContext = inferenceContext; 281 this.env = env; 282 this.warn = warn; 283 } 284 285 /** The inference context. */ 286 final InferenceContext inferenceContext; 287 288 /** The attribution environment. */ 289 Env<AttrContext> env; 290 291 /** The warner. */ 292 final Warner warn; 293 294 @Override 295 public boolean isPartial() { 296 return true; 297 } 298 299 /** 300 * Checks this type against a target; this means generating return type constraints, solve 301 * and then roll back the results (to avoid poolluting the context). 302 */ 303 Type check(Attr.ResultInfo resultInfo) { 304 Warner noWarnings = new Warner(null); 305 inferenceException.clear(); 306 List<Type> saved_undet = null; 307 try { 308 /** we need to save the inference context before generating target type constraints. 309 * This constraints may pollute the inference context and make it useless in case we 310 * need to use it several times: with several targets. 311 */ 312 saved_undet = inferenceContext.save(); 313 if (allowGraphInference && !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 314 boolean shouldPropagate = resultInfo.checkContext.inferenceContext().free(resultInfo.pt); 315 316 InferenceContext minContext = shouldPropagate ? 317 inferenceContext.min(roots(asMethodType(), null), false, warn) : 318 inferenceContext; 319 320 MethodType other = (MethodType)minContext.update(asMethodType()); 321 Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3 322 other, minContext); 323 324 if (shouldPropagate) { 325 //propagate inference context outwards and exit 326 minContext.dupTo(resultInfo.checkContext.inferenceContext(), 327 resultInfo.checkContext.deferredAttrContext().insideOverloadPhase()); 328 return newRestype; 329 } 330 } 331 inferenceContext.solve(noWarnings); 332 return inferenceContext.asInstType(this).getReturnType(); 333 } catch (InferenceException ex) { 334 resultInfo.checkContext.report(null, ex.getDiagnostic()); 335 Assert.error(); //cannot get here (the above should throw) 336 return null; 337 } finally { 338 if (saved_undet != null) { 339 inferenceContext.rollback(saved_undet); 340 } 341 } 342 } 343 } 344 345 private void dumpGraphsIfNeeded(DiagnosticPosition pos, Symbol msym, Resolve.MethodResolutionContext rsContext) { 346 int round = 0; 347 try { 348 for (String graph : pendingGraphs.reverse()) { 349 Assert.checkNonNull(dependenciesFolder); 350 Name name = msym.name == msym.name.table.names.init ? 351 msym.owner.name : msym.name; 352 String filename = String.format("%s@%s[mode=%s,step=%s]_%d.dot", 353 name, 354 pos.getStartPosition(), 355 rsContext.attrMode(), 356 rsContext.step, 357 round); 358 Path dotFile = Paths.get(dependenciesFolder, filename); 359 try (Writer w = Files.newBufferedWriter(dotFile)) { 360 w.append(graph); 361 } 362 round++; 363 } 364 } catch (IOException ex) { 365 Assert.error("Error occurred when dumping inference graph: " + ex.getMessage()); 366 } finally { 367 pendingGraphs = List.nil(); 368 } 369 } 370 371 /** 372 * Generate constraints from the generic method's return type. If the method 373 * call occurs in a context where a type T is expected, use the expected 374 * type to derive more constraints on the generic method inference variables. 375 */ 376 Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo, 377 MethodType mt, InferenceContext inferenceContext) { 378 InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext(); 379 Type from = mt.getReturnType(); 380 if (mt.getReturnType().containsAny(inferenceContext.inferencevars) && 381 rsInfoInfContext != emptyContext) { 382 from = types.capture(from); 383 //add synthetic captured ivars 384 for (Type t : from.getTypeArguments()) { 385 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) { 386 inferenceContext.addVar((TypeVar)t); 387 } 388 } 389 } 390 Type qtype = inferenceContext.asUndetVar(from); 391 Type to = resultInfo.pt; 392 393 if (qtype.hasTag(VOID)) { 394 to = syms.voidType; 395 } else if (to.hasTag(NONE)) { 396 to = from.isPrimitive() ? from : syms.objectType; 397 } else if (qtype.hasTag(UNDETVAR)) { 398 if (resultInfo.pt.isReference()) { 399 to = generateReturnConstraintsUndetVarToReference( 400 tree, (UndetVar)qtype, to, resultInfo, inferenceContext); 401 } else { 402 if (to.isPrimitive()) { 403 to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to, 404 resultInfo, inferenceContext); 405 } 406 } 407 } else if (rsInfoInfContext.free(resultInfo.pt)) { 408 //propagation - cache captured vars 409 qtype = inferenceContext.asUndetVar(rsInfoInfContext.cachedCapture(tree, from, false)); 410 } 411 Assert.check(allowGraphInference || !rsInfoInfContext.free(to), 412 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion"); 413 //we need to skip capture? 414 Warner retWarn = new Warner(); 415 if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) || 416 //unchecked conversion is not allowed in source 7 mode 417 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) { 418 throw inferenceException 419 .setMessage("infer.no.conforming.instance.exists", 420 inferenceContext.restvars(), mt.getReturnType(), to); 421 } 422 return from; 423 } 424 425 private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from, 426 Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) { 427 if (!allowGraphInference) { 428 //if legacy, just return boxed type 429 return types.boxedClass(to).type; 430 } 431 //if graph inference we need to skip conflicting boxed bounds... 432 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER, 433 InferenceBound.LOWER)) { 434 Type boundAsPrimitive = types.unboxedType(t); 435 if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) { 436 continue; 437 } 438 return generateReferenceToTargetConstraint(tree, from, to, 439 resultInfo, inferenceContext); 440 } 441 return types.boxedClass(to).type; 442 } 443 444 private Type generateReturnConstraintsUndetVarToReference(JCTree tree, 445 UndetVar from, Type to, Attr.ResultInfo resultInfo, 446 InferenceContext inferenceContext) { 447 Type captureOfTo = types.capture(to); 448 /* T is a reference type, but is not a wildcard-parameterized type, and either 449 */ 450 if (captureOfTo == to) { //not a wildcard parameterized type 451 /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha, 452 * where S is a wildcard-parameterized type, or 453 */ 454 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { 455 Type captureOfBound = types.capture(t); 456 if (captureOfBound != t) { 457 return generateReferenceToTargetConstraint(tree, from, to, 458 resultInfo, inferenceContext); 459 } 460 } 461 462 /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha, 463 * where S1 and S2 have supertypes that are two different 464 * parameterizations of the same generic class or interface. 465 */ 466 for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) { 467 for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) { 468 if (aLowerBound != anotherLowerBound && 469 !inferenceContext.free(aLowerBound) && 470 !inferenceContext.free(anotherLowerBound) && 471 commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) { 472 return generateReferenceToTargetConstraint(tree, from, to, 473 resultInfo, inferenceContext); 474 } 475 } 476 } 477 } 478 479 /* T is a parameterization of a generic class or interface, G, 480 * and B2 contains a bound of one of the forms alpha = S or S <: alpha, 481 * where there exists no type of the form G<...> that is a 482 * supertype of S, but the raw type G is a supertype of S 483 */ 484 if (to.isParameterized()) { 485 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { 486 Type sup = types.asSuper(t, to.tsym); 487 if (sup != null && sup.isRaw()) { 488 return generateReferenceToTargetConstraint(tree, from, to, 489 resultInfo, inferenceContext); 490 } 491 } 492 } 493 return to; 494 } 495 496 private boolean commonSuperWithDiffParameterization(Type t, Type s) { 497 for (Pair<Type, Type> supers : getParameterizedSupers(t, s)) { 498 if (!types.isSameType(supers.fst, supers.snd)) return true; 499 } 500 return false; 501 } 502 503 private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from, 504 Type to, Attr.ResultInfo resultInfo, 505 InferenceContext inferenceContext) { 506 inferenceContext.solve(List.of(from.qtype), new Warner()); 507 inferenceContext.notifyChange(); 508 Type capturedType = resultInfo.checkContext.inferenceContext() 509 .cachedCapture(tree, from.getInst(), false); 510 if (types.isConvertible(capturedType, 511 resultInfo.checkContext.inferenceContext().asUndetVar(to))) { 512 //effectively skip additional return-type constraint generation (compatibility) 513 return syms.objectType; 514 } 515 return to; 516 } 517 518 /** 519 * Infer cyclic inference variables as described in 15.12.2.8. 520 */ 521 void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) { 522 ListBuffer<Type> todo = new ListBuffer<>(); 523 //step 1 - create fresh tvars 524 for (Type t : vars) { 525 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t); 526 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER); 527 if (Type.containsAny(upperBounds, vars)) { 528 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner); 529 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeIntersectionType(uv.getBounds(InferenceBound.UPPER)), null); 530 todo.append(uv); 531 uv.setInst(fresh_tvar.type); 532 } else if (upperBounds.nonEmpty()) { 533 uv.setInst(types.glb(upperBounds)); 534 } else { 535 uv.setInst(syms.objectType); 536 } 537 } 538 //step 2 - replace fresh tvars in their bounds 539 List<Type> formals = vars; 540 for (Type t : todo) { 541 UndetVar uv = (UndetVar)t; 542 TypeVar ct = (TypeVar)uv.getInst(); 543 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct))); 544 if (ct.bound.isErroneous()) { 545 //report inference error if glb fails 546 reportBoundError(uv, InferenceBound.UPPER); 547 } 548 formals = formals.tail; 549 } 550 } 551 552 /** 553 * Compute a synthetic method type corresponding to the requested polymorphic 554 * method signature. The target return type is computed from the immediately 555 * enclosing scope surrounding the polymorphic-signature call. 556 */ 557 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, 558 MethodSymbol spMethod, // sig. poly. method or null if none 559 Resolve.MethodResolutionContext resolveContext, 560 List<Type> argtypes) { 561 final Type restype; 562 563 if (spMethod == null || types.isSameType(spMethod.getReturnType(), syms.objectType, true)) { 564 // The return type of the polymorphic signature is polymorphic, 565 // and is computed from the enclosing tree E, as follows: 566 // if E is a cast, then use the target type of the cast expression 567 // as a return type; if E is an expression statement, the return 568 // type is 'void'; otherwise 569 // the return type is simply 'Object'. A correctness check ensures 570 // that env.next refers to the lexically enclosing environment in 571 // which the polymorphic signature call environment is nested. 572 573 switch (env.next.tree.getTag()) { 574 case TYPECAST: 575 JCTypeCast castTree = (JCTypeCast)env.next.tree; 576 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ? 577 castTree.clazz.type : 578 syms.objectType; 579 break; 580 case EXEC: 581 JCTree.JCExpressionStatement execTree = 582 (JCTree.JCExpressionStatement)env.next.tree; 583 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ? 584 syms.voidType : 585 syms.objectType; 586 break; 587 default: 588 restype = syms.objectType; 589 } 590 } else { 591 // The return type of the polymorphic signature is fixed 592 // (not polymorphic) 593 restype = spMethod.getReturnType(); 594 } 595 596 List<Type> paramtypes = argtypes.map(new ImplicitArgType(spMethod, resolveContext.step)); 597 List<Type> exType = spMethod != null ? 598 spMethod.getThrownTypes() : 599 List.of(syms.throwableType); // make it throw all exceptions 600 601 MethodType mtype = new MethodType(paramtypes, 602 restype, 603 exType, 604 syms.methodClass); 605 return mtype; 606 } 607 //where 608 class ImplicitArgType extends DeferredAttr.DeferredTypeMap { 609 610 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) { 611 (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase); 612 } 613 614 @Override 615 public Type visitClassType(ClassType t, Void aVoid) { 616 return types.erasure(t); 617 } 618 619 @Override 620 public Type visitType(Type t, Void _unused) { 621 if (t.hasTag(DEFERRED)) { 622 return visit(super.visitType(t, null)); 623 } else if (t.hasTag(BOT)) 624 // nulls type as the marker type Null (which has no instances) 625 // infer as java.lang.Void for now 626 t = types.boxedClass(syms.voidType).type; 627 return t; 628 } 629 } 630 631 TypeMapping<Void> fromTypeVarFun = new TypeMapping<Void>() { 632 @Override 633 public Type visitTypeVar(TypeVar tv, Void aVoid) { 634 return new UndetVar(tv, incorporationEngine(), types); 635 } 636 637 @Override 638 public Type visitCapturedType(CapturedType t, Void aVoid) { 639 return new CapturedUndetVar(t, incorporationEngine(), types); 640 } 641 }; 642 643 /** 644 * This method is used to infer a suitable target SAM in case the original 645 * SAM type contains one or more wildcards. An inference process is applied 646 * so that wildcard bounds, as well as explicit lambda/method ref parameters 647 * (where applicable) are used to constraint the solution. 648 */ 649 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface, 650 List<Type> paramTypes, Check.CheckContext checkContext) { 651 if (types.capture(funcInterface) == funcInterface) { 652 //if capture doesn't change the type then return the target unchanged 653 //(this means the target contains no wildcards!) 654 return funcInterface; 655 } else { 656 Type formalInterface = funcInterface.tsym.type; 657 InferenceContext funcInterfaceContext = 658 new InferenceContext(this, funcInterface.tsym.type.getTypeArguments()); 659 660 Assert.check(paramTypes != null); 661 //get constraints from explicit params (this is done by 662 //checking that explicit param types are equal to the ones 663 //in the functional interface descriptors) 664 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes(); 665 if (descParameterTypes.size() != paramTypes.size()) { 666 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda")); 667 return types.createErrorType(funcInterface); 668 } 669 for (Type p : descParameterTypes) { 670 if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) { 671 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); 672 return types.createErrorType(funcInterface); 673 } 674 paramTypes = paramTypes.tail; 675 } 676 677 try { 678 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings); 679 } catch (InferenceException ex) { 680 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); 681 } 682 683 List<Type> actualTypeargs = funcInterface.getTypeArguments(); 684 for (Type t : funcInterfaceContext.undetvars) { 685 UndetVar uv = (UndetVar)t; 686 if (uv.getInst() == null) { 687 uv.setInst(actualTypeargs.head); 688 } 689 actualTypeargs = actualTypeargs.tail; 690 } 691 692 Type owntype = funcInterfaceContext.asInstType(formalInterface); 693 if (!chk.checkValidGenericType(owntype)) { 694 //if the inferred functional interface type is not well-formed, 695 //or if it's not a subtype of the original target, issue an error 696 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); 697 } 698 //propagate constraints as per JLS 18.2.1 699 checkContext.compatible(owntype, funcInterface, types.noWarnings); 700 return owntype; 701 } 702 } 703 // </editor-fold> 704 705 // <editor-fold defaultstate="collapsed" desc="Incorporation"> 706 707 /** 708 * This class is the root of all incorporation actions. 709 */ 710 public abstract class IncorporationAction { 711 UndetVar uv; 712 Type t; 713 714 IncorporationAction(UndetVar uv, Type t) { 715 this.uv = uv; 716 this.t = t; 717 } 718 719 /** 720 * Incorporation action entry-point. Subclasses should define the logic associated with 721 * this incorporation action. 722 */ 723 abstract void apply(InferenceContext ic, Warner warn); 724 725 /** 726 * Helper function: perform subtyping through incorporation cache. 727 */ 728 boolean isSubtype(Type s, Type t, Warner warn) { 729 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn); 730 } 731 732 /** 733 * Helper function: perform type-equivalence through incorporation cache. 734 */ 735 boolean isSameType(Type s, Type t) { 736 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null); 737 } 738 739 @Override 740 public String toString() { 741 return String.format("%s[undet=%s,t=%s]", getClass().getSimpleName(), uv.qtype, t); 742 } 743 } 744 745 /** 746 * Bound-check incorporation action. A newly added bound is checked against existing bounds, 747 * to verify its compatibility; each bound is checked using either subtyping or type equivalence. 748 */ 749 class CheckBounds extends IncorporationAction { 750 751 InferenceBound from; 752 BiFunction<InferenceContext, Type, Type> typeFunc; 753 BiPredicate<InferenceContext, Type> optFilter; 754 755 CheckBounds(UndetVar uv, Type t, InferenceBound from) { 756 this(uv, t, InferenceContext::asUndetVar, null, from); 757 } 758 759 CheckBounds(UndetVar uv, Type t, BiFunction<InferenceContext, Type, Type> typeFunc, 760 BiPredicate<InferenceContext, Type> typeFilter, InferenceBound from) { 761 super(uv, t); 762 this.from = from; 763 this.typeFunc = typeFunc; 764 this.optFilter = typeFilter; 765 } 766 767 @Override 768 void apply(InferenceContext inferenceContext, Warner warn) { 769 t = typeFunc.apply(inferenceContext, t); 770 if (optFilter != null && optFilter.test(inferenceContext, t)) return; 771 for (InferenceBound to : boundsToCheck()) { 772 for (Type b : uv.getBounds(to)) { 773 b = typeFunc.apply(inferenceContext, b); 774 if (optFilter != null && optFilter.test(inferenceContext, b)) continue; 775 boolean success = checkBound(t, b, from, to, warn); 776 if (!success) { 777 report(from, to); 778 } 779 } 780 } 781 } 782 783 /** 784 * The list of bound kinds to be checked. 785 */ 786 EnumSet<InferenceBound> boundsToCheck() { 787 return (from == InferenceBound.EQ) ? 788 EnumSet.allOf(InferenceBound.class) : 789 EnumSet.complementOf(EnumSet.of(from)); 790 } 791 792 /** 793 * Is source type 's' compatible with target type 't' given source and target bound kinds? 794 */ 795 boolean checkBound(Type s, Type t, InferenceBound ib_s, InferenceBound ib_t, Warner warn) { 796 if (ib_s.lessThan(ib_t)) { 797 return isSubtype(s, t, warn); 798 } else if (ib_t.lessThan(ib_s)) { 799 return isSubtype(t, s, warn); 800 } else { 801 return isSameType(s, t); 802 } 803 } 804 805 /** 806 * Report a bound check error. 807 */ 808 void report(InferenceBound from, InferenceBound to) { 809 //this is a workaround to preserve compatibility with existing messages 810 if (from == to) { 811 reportBoundError(uv, from); 812 } else if (from == InferenceBound.LOWER || to == InferenceBound.EQ) { 813 reportBoundError(uv, to, from); 814 } else { 815 reportBoundError(uv, from, to); 816 } 817 } 818 819 @Override 820 public String toString() { 821 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, from); 822 } 823 } 824 825 /** 826 * Custom check executed by the legacy incorporation engine. Newly added bounds are checked 827 * against existing eq bounds. 828 */ 829 class EqCheckLegacy extends CheckBounds { 830 EqCheckLegacy(UndetVar uv, Type t, InferenceBound from) { 831 super(uv, t, InferenceContext::asInstType, InferenceContext::free, from); 832 } 833 834 @Override 835 EnumSet<InferenceBound> boundsToCheck() { 836 return (from == InferenceBound.EQ) ? 837 EnumSet.allOf(InferenceBound.class) : 838 EnumSet.of(InferenceBound.EQ); 839 } 840 } 841 842 /** 843 * Check that the inferred type conforms to all bounds. 844 */ 845 class CheckInst extends CheckBounds { 846 847 EnumSet<InferenceBound> to; 848 849 CheckInst(UndetVar uv, InferenceBound ib, InferenceBound... rest) { 850 super(uv, uv.getInst(), InferenceBound.EQ); 851 this.to = EnumSet.of(ib, rest); 852 } 853 854 @Override 855 EnumSet<InferenceBound> boundsToCheck() { 856 return to; 857 } 858 859 @Override 860 void report(InferenceBound from, InferenceBound to) { 861 reportInstError(uv, to); 862 } 863 } 864 865 /** 866 * Replace undetvars in bounds and check that the inferred type conforms to all bounds. 867 */ 868 class SubstBounds extends CheckInst { 869 SubstBounds(UndetVar uv) { 870 super(uv, InferenceBound.LOWER, InferenceBound.EQ, InferenceBound.UPPER); 871 } 872 873 @Override 874 void apply(InferenceContext inferenceContext, Warner warn) { 875 for (Type undet : inferenceContext.undetvars) { 876 //we could filter out variables not mentioning uv2... 877 UndetVar uv2 = (UndetVar)undet; 878 uv2.substBounds(List.of(uv.qtype), List.of(uv.getInst()), types); 879 checkCompatibleUpperBounds(uv2, inferenceContext); 880 } 881 super.apply(inferenceContext, warn); 882 } 883 884 /** 885 * Make sure that the upper bounds we got so far lead to a solvable inference 886 * variable by making sure that a glb exists. 887 */ 888 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) { 889 List<Type> hibounds = 890 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext)); 891 final Type hb; 892 if (hibounds.isEmpty()) 893 hb = syms.objectType; 894 else if (hibounds.tail.isEmpty()) 895 hb = hibounds.head; 896 else 897 hb = types.glb(hibounds); 898 if (hb == null || hb.isErroneous()) 899 reportBoundError(uv, InferenceBound.UPPER); 900 } 901 } 902 903 /** 904 * Perform pairwise comparison between common generic supertypes of two upper bounds. 905 */ 906 class CheckUpperBounds extends IncorporationAction { 907 908 public CheckUpperBounds(UndetVar uv, Type t) { 909 super(uv, t); 910 } 911 912 @Override 913 void apply(InferenceContext inferenceContext, Warner warn) { 914 List<Type> boundList = uv.getBounds(InferenceBound.UPPER).stream() 915 .collect(types.closureCollector(true, types::isSameType)); 916 for (Type b2 : boundList) { 917 if (t == b2) continue; 918 /* This wildcard check is temporary workaround. This code may need to be 919 * revisited once spec bug JDK-7034922 is fixed. 920 */ 921 if (t != b2 && !t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) { 922 for (Pair<Type, Type> commonSupers : getParameterizedSupers(t, b2)) { 923 List<Type> allParamsSuperBound1 = commonSupers.fst.allparams(); 924 List<Type> allParamsSuperBound2 = commonSupers.snd.allparams(); 925 while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) { 926 //traverse the list of all params comparing them 927 if (!allParamsSuperBound1.head.hasTag(WILDCARD) && 928 !allParamsSuperBound2.head.hasTag(WILDCARD)) { 929 if (!isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head), 930 inferenceContext.asUndetVar(allParamsSuperBound2.head))) { 931 reportBoundError(uv, InferenceBound.UPPER); 932 } 933 } 934 allParamsSuperBound1 = allParamsSuperBound1.tail; 935 allParamsSuperBound2 = allParamsSuperBound2.tail; 936 } 937 Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty()); 938 } 939 } 940 } 941 } 942 } 943 944 /** 945 * Perform propagation of bounds. Given a constraint of the kind {@code alpha <: T}, three 946 * kind of propagation occur: 947 * 948 * <li>T is copied into all matching bounds (i.e. lower/eq bounds) B of alpha such that B=beta (forward propagation)</li> 949 * <li>if T=beta, matching bounds (i.e. upper bounds) of beta are copied into alpha (backwards propagation)</li> 950 * <li>if T=beta, sets a symmetric bound on beta (i.e. beta :> alpha) (symmetric propagation) </li> 951 */ 952 class PropagateBounds extends IncorporationAction { 953 954 InferenceBound ib; 955 956 public PropagateBounds(UndetVar uv, Type t, InferenceBound ib) { 957 super(uv, t); 958 this.ib = ib; 959 } 960 961 void apply(InferenceContext inferenceContext, Warner warner) { 962 Type undetT = inferenceContext.asUndetVar(t); 963 if (undetT.hasTag(UNDETVAR) && !((UndetVar)undetT).isCaptured()) { 964 UndetVar uv2 = (UndetVar)undetT; 965 //symmetric propagation 966 uv2.addBound(ib.complement(), uv, types); 967 //backwards propagation 968 for (InferenceBound ib2 : backwards()) { 969 for (Type b : uv2.getBounds(ib2)) { 970 uv.addBound(ib2, b, types); 971 } 972 } 973 } 974 //forward propagation 975 for (InferenceBound ib2 : forward()) { 976 for (Type l : uv.getBounds(ib2)) { 977 Type undet = inferenceContext.asUndetVar(l); 978 if (undet.hasTag(TypeTag.UNDETVAR) && !((UndetVar)undet).isCaptured()) { 979 UndetVar uv2 = (UndetVar)undet; 980 uv2.addBound(ib, inferenceContext.asInstType(t), types); 981 } 982 } 983 } 984 } 985 986 EnumSet<InferenceBound> forward() { 987 return (ib == InferenceBound.EQ) ? 988 EnumSet.of(InferenceBound.EQ) : EnumSet.complementOf(EnumSet.of(ib)); 989 } 990 991 EnumSet<InferenceBound> backwards() { 992 return (ib == InferenceBound.EQ) ? 993 EnumSet.allOf(InferenceBound.class) : EnumSet.of(ib); 994 } 995 996 @Override 997 public String toString() { 998 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, ib); 999 } 1000 } 1001 1002 /** 1003 * This class models an incorporation engine. The engine is responsible for listening to 1004 * changes in inference variables and register incorporation actions accordingly. 1005 */ 1006 abstract class AbstractIncorporationEngine implements UndetVarListener { 1007 1008 @Override 1009 public void varInstantiated(UndetVar uv) { 1010 uv.incorporationActions.addFirst(new SubstBounds(uv)); 1011 } 1012 1013 @Override 1014 public void varBoundChanged(UndetVar uv, InferenceBound ib, Type bound, boolean update) { 1015 if (uv.isCaptured()) return; 1016 uv.incorporationActions.addAll(getIncorporationActions(uv, ib, bound, update)); 1017 } 1018 1019 abstract List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update); 1020 } 1021 1022 /** 1023 * A legacy incorporation engine. Used for source <= 7. 1024 */ 1025 AbstractIncorporationEngine legacyEngine = new AbstractIncorporationEngine() { 1026 1027 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) { 1028 ListBuffer<IncorporationAction> actions = new ListBuffer<>(); 1029 Type inst = uv.getInst(); 1030 if (inst != null) { 1031 actions.add(new CheckInst(uv, ib)); 1032 } 1033 actions.add(new EqCheckLegacy(uv, t, ib)); 1034 return actions.toList(); 1035 } 1036 }; 1037 1038 /** 1039 * The standard incorporation engine. Used for source >= 8. 1040 */ 1041 AbstractIncorporationEngine graphEngine = new AbstractIncorporationEngine() { 1042 1043 @Override 1044 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) { 1045 ListBuffer<IncorporationAction> actions = new ListBuffer<>(); 1046 Type inst = uv.getInst(); 1047 if (inst != null) { 1048 actions.add(new CheckInst(uv, ib)); 1049 } 1050 actions.add(new CheckBounds(uv, t, ib)); 1051 1052 if (update) { 1053 return actions.toList(); 1054 } 1055 1056 if (ib == InferenceBound.UPPER) { 1057 actions.add(new CheckUpperBounds(uv, t)); 1058 } 1059 1060 actions.add(new PropagateBounds(uv, t, ib)); 1061 1062 return actions.toList(); 1063 } 1064 }; 1065 1066 /** 1067 * Get the incorporation engine to be used in this compilation. 1068 */ 1069 AbstractIncorporationEngine incorporationEngine() { 1070 return allowGraphInference ? graphEngine : legacyEngine; 1071 } 1072 1073 /** max number of incorporation rounds. */ 1074 static final int MAX_INCORPORATION_STEPS = 10000; 1075 1076 /** 1077 * Check bounds and perform incorporation. 1078 */ 1079 void doIncorporation(InferenceContext inferenceContext, Warner warn) throws InferenceException { 1080 try { 1081 boolean progress = true; 1082 int round = 0; 1083 while (progress && round < MAX_INCORPORATION_STEPS) { 1084 progress = false; 1085 for (Type t : inferenceContext.undetvars) { 1086 UndetVar uv = (UndetVar)t; 1087 if (!uv.incorporationActions.isEmpty()) { 1088 progress = true; 1089 uv.incorporationActions.removeFirst().apply(inferenceContext, warn); 1090 } 1091 } 1092 round++; 1093 } 1094 } finally { 1095 incorporationCache.clear(); 1096 } 1097 } 1098 1099 /* If for two types t and s there is a least upper bound that contains 1100 * parameterized types G1, G2 ... Gn, then there exists supertypes of 't' of the form 1101 * G1<T1, ..., Tn>, G2<T1, ..., Tn>, ... Gn<T1, ..., Tn> and supertypes of 's' of the form 1102 * G1<S1, ..., Sn>, G2<S1, ..., Sn>, ... Gn<S1, ..., Sn> which will be returned by this method. 1103 * If no such common supertypes exists then an empty list is returned. 1104 * 1105 * As an example for the following input: 1106 * 1107 * t = java.util.ArrayList<java.lang.String> 1108 * s = java.util.List<T> 1109 * 1110 * we get this ouput (singleton list): 1111 * 1112 * [Pair[java.util.List<java.lang.String>,java.util.List<T>]] 1113 */ 1114 private List<Pair<Type, Type>> getParameterizedSupers(Type t, Type s) { 1115 Type lubResult = types.lub(t, s); 1116 if (lubResult == syms.errType || lubResult == syms.botType) { 1117 return List.nil(); 1118 } 1119 List<Type> supertypesToCheck = lubResult.isIntersection() ? 1120 ((IntersectionClassType)lubResult).getComponents() : 1121 List.of(lubResult); 1122 ListBuffer<Pair<Type, Type>> commonSupertypes = new ListBuffer<>(); 1123 for (Type sup : supertypesToCheck) { 1124 if (sup.isParameterized()) { 1125 Type asSuperOfT = asSuper(t, sup); 1126 Type asSuperOfS = asSuper(s, sup); 1127 commonSupertypes.add(new Pair<>(asSuperOfT, asSuperOfS)); 1128 } 1129 } 1130 return commonSupertypes.toList(); 1131 } 1132 //where 1133 private Type asSuper(Type t, Type sup) { 1134 return (sup.hasTag(ARRAY)) ? 1135 new ArrayType(asSuper(types.elemtype(t), types.elemtype(sup)), syms.arrayClass) : 1136 types.asSuper(t, sup.tsym); 1137 } 1138 1139 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn) { 1140 IncorporationBinaryOp newOp = new IncorporationBinaryOp(opKind, op1, op2); 1141 Boolean res = incorporationCache.get(newOp); 1142 if (res == null) { 1143 incorporationCache.put(newOp, res = newOp.apply(warn)); 1144 } 1145 return res; 1146 } 1147 1148 /** 1149 * Three kinds of basic operation are supported as part of an incorporation step: 1150 * (i) subtype check, (ii) same type check and (iii) bound addition (either 1151 * upper/lower/eq bound). 1152 */ 1153 enum IncorporationBinaryOpKind { 1154 IS_SUBTYPE() { 1155 @Override 1156 boolean apply(Type op1, Type op2, Warner warn, Types types) { 1157 return types.isSubtypeUnchecked(op1, op2, warn); 1158 } 1159 }, 1160 IS_SAME_TYPE() { 1161 @Override 1162 boolean apply(Type op1, Type op2, Warner warn, Types types) { 1163 return types.isSameType(op1, op2); 1164 } 1165 }; 1166 1167 abstract boolean apply(Type op1, Type op2, Warner warn, Types types); 1168 } 1169 1170 /** 1171 * This class encapsulates a basic incorporation operation; incorporation 1172 * operations takes two type operands and a kind. Each operation performed 1173 * during an incorporation round is stored in a cache, so that operations 1174 * are not executed unnecessarily (which would potentially lead to adding 1175 * same bounds over and over). 1176 */ 1177 class IncorporationBinaryOp { 1178 1179 IncorporationBinaryOpKind opKind; 1180 Type op1; 1181 Type op2; 1182 1183 IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) { 1184 this.opKind = opKind; 1185 this.op1 = op1; 1186 this.op2 = op2; 1187 } 1188 1189 @Override 1190 public boolean equals(Object o) { 1191 if (!(o instanceof IncorporationBinaryOp)) { 1192 return false; 1193 } else { 1194 IncorporationBinaryOp that = (IncorporationBinaryOp)o; 1195 return opKind == that.opKind && 1196 types.isSameType(op1, that.op1, true) && 1197 types.isSameType(op2, that.op2, true); 1198 } 1199 } 1200 1201 @Override 1202 public int hashCode() { 1203 int result = opKind.hashCode(); 1204 result *= 127; 1205 result += types.hashCode(op1); 1206 result *= 127; 1207 result += types.hashCode(op2); 1208 return result; 1209 } 1210 1211 boolean apply(Warner warn) { 1212 return opKind.apply(op1, op2, warn, types); 1213 } 1214 } 1215 1216 /** an incorporation cache keeps track of all executed incorporation-related operations */ 1217 Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>(); 1218 1219 protected static class BoundFilter implements Filter<Type> { 1220 1221 InferenceContext inferenceContext; 1222 1223 public BoundFilter(InferenceContext inferenceContext) { 1224 this.inferenceContext = inferenceContext; 1225 } 1226 1227 @Override 1228 public boolean accepts(Type t) { 1229 return !t.isErroneous() && !inferenceContext.free(t) && 1230 !t.hasTag(BOT); 1231 } 1232 } 1233 1234 /** 1235 * Incorporation error: mismatch between inferred type and given bound. 1236 */ 1237 void reportInstError(UndetVar uv, InferenceBound ib) { 1238 reportInferenceError( 1239 String.format("inferred.do.not.conform.to.%s.bounds", StringUtils.toLowerCase(ib.name())), 1240 uv.getInst(), 1241 uv.getBounds(ib)); 1242 } 1243 1244 /** 1245 * Incorporation error: mismatch between two (or more) bounds of same kind. 1246 */ 1247 void reportBoundError(UndetVar uv, InferenceBound ib) { 1248 reportInferenceError( 1249 String.format("incompatible.%s.bounds", StringUtils.toLowerCase(ib.name())), 1250 uv.qtype, 1251 uv.getBounds(ib)); 1252 } 1253 1254 /** 1255 * Incorporation error: mismatch between two (or more) bounds of different kinds. 1256 */ 1257 void reportBoundError(UndetVar uv, InferenceBound ib1, InferenceBound ib2) { 1258 reportInferenceError( 1259 String.format("incompatible.%s.%s.bounds", 1260 StringUtils.toLowerCase(ib1.name()), 1261 StringUtils.toLowerCase(ib2.name())), 1262 uv.qtype, 1263 uv.getBounds(ib1), 1264 uv.getBounds(ib2)); 1265 } 1266 1267 /** 1268 * Helper method: reports an inference error. 1269 */ 1270 void reportInferenceError(String key, Object... args) { 1271 throw inferenceException.setMessage(key, args); 1272 } 1273 // </editor-fold> 1274 1275 // <editor-fold defaultstate="collapsed" desc="Inference engine"> 1276 /** 1277 * Graph inference strategy - act as an input to the inference solver; a strategy is 1278 * composed of two ingredients: (i) find a node to solve in the inference graph, 1279 * and (ii) tell th engine when we are done fixing inference variables 1280 */ 1281 interface GraphStrategy { 1282 1283 /** 1284 * A NodeNotFoundException is thrown whenever an inference strategy fails 1285 * to pick the next node to solve in the inference graph. 1286 */ 1287 public static class NodeNotFoundException extends RuntimeException { 1288 private static final long serialVersionUID = 0; 1289 1290 InferenceGraph graph; 1291 1292 public NodeNotFoundException(InferenceGraph graph) { 1293 this.graph = graph; 1294 } 1295 } 1296 /** 1297 * Pick the next node (leaf) to solve in the graph 1298 */ 1299 Node pickNode(InferenceGraph g) throws NodeNotFoundException; 1300 /** 1301 * Is this the last step? 1302 */ 1303 boolean done(); 1304 } 1305 1306 /** 1307 * Simple solver strategy class that locates all leaves inside a graph 1308 * and picks the first leaf as the next node to solve 1309 */ 1310 abstract class LeafSolver implements GraphStrategy { 1311 public Node pickNode(InferenceGraph g) { 1312 if (g.nodes.isEmpty()) { 1313 //should not happen 1314 throw new NodeNotFoundException(g); 1315 } 1316 return g.nodes.get(0); 1317 } 1318 } 1319 1320 /** 1321 * This solver uses an heuristic to pick the best leaf - the heuristic 1322 * tries to select the node that has maximal probability to contain one 1323 * or more inference variables in a given list 1324 */ 1325 abstract class BestLeafSolver extends LeafSolver { 1326 1327 /** list of ivars of which at least one must be solved */ 1328 List<Type> varsToSolve; 1329 1330 BestLeafSolver(List<Type> varsToSolve) { 1331 this.varsToSolve = varsToSolve; 1332 } 1333 1334 /** 1335 * Computes a path that goes from a given node to the leafs in the graph. 1336 * Typically this will start from a node containing a variable in 1337 * {@code varsToSolve}. For any given path, the cost is computed as the total 1338 * number of type-variables that should be eagerly instantiated across that path. 1339 */ 1340 Pair<List<Node>, Integer> computeTreeToLeafs(Node n) { 1341 Pair<List<Node>, Integer> cachedPath = treeCache.get(n); 1342 if (cachedPath == null) { 1343 //cache miss 1344 if (n.isLeaf()) { 1345 //if leaf, stop 1346 cachedPath = new Pair<>(List.of(n), n.data.length()); 1347 } else { 1348 //if non-leaf, proceed recursively 1349 Pair<List<Node>, Integer> path = new Pair<>(List.of(n), n.data.length()); 1350 for (Node n2 : n.getAllDependencies()) { 1351 if (n2 == n) continue; 1352 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2); 1353 path = new Pair<>(path.fst.prependList(subpath.fst), 1354 path.snd + subpath.snd); 1355 } 1356 cachedPath = path; 1357 } 1358 //save results in cache 1359 treeCache.put(n, cachedPath); 1360 } 1361 return cachedPath; 1362 } 1363 1364 /** cache used to avoid redundant computation of tree costs */ 1365 final Map<Node, Pair<List<Node>, Integer>> treeCache = new HashMap<>(); 1366 1367 /** constant value used to mark non-existent paths */ 1368 final Pair<List<Node>, Integer> noPath = new Pair<>(null, Integer.MAX_VALUE); 1369 1370 /** 1371 * Pick the leaf that minimize cost 1372 */ 1373 @Override 1374 public Node pickNode(final InferenceGraph g) { 1375 treeCache.clear(); //graph changes at every step - cache must be cleared 1376 Pair<List<Node>, Integer> bestPath = noPath; 1377 for (Node n : g.nodes) { 1378 if (!Collections.disjoint(n.data, varsToSolve)) { 1379 Pair<List<Node>, Integer> path = computeTreeToLeafs(n); 1380 //discard all paths containing at least a node in the 1381 //closure computed above 1382 if (path.snd < bestPath.snd) { 1383 bestPath = path; 1384 } 1385 } 1386 } 1387 if (bestPath == noPath) { 1388 //no path leads there 1389 throw new NodeNotFoundException(g); 1390 } 1391 return bestPath.fst.head; 1392 } 1393 } 1394 1395 /** 1396 * The inference process can be thought of as a sequence of steps. Each step 1397 * instantiates an inference variable using a subset of the inference variable 1398 * bounds, if certain condition are met. Decisions such as the sequence in which 1399 * steps are applied, or which steps are to be applied are left to the inference engine. 1400 */ 1401 enum InferenceStep { 1402 1403 /** 1404 * Instantiate an inference variables using one of its (ground) equality 1405 * constraints 1406 */ 1407 EQ(InferenceBound.EQ) { 1408 @Override 1409 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1410 return filterBounds(uv, inferenceContext).head; 1411 } 1412 }, 1413 /** 1414 * Instantiate an inference variables using its (ground) lower bounds. Such 1415 * bounds are merged together using lub(). 1416 */ 1417 LOWER(InferenceBound.LOWER) { 1418 @Override 1419 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1420 Infer infer = inferenceContext.infer; 1421 List<Type> lobounds = filterBounds(uv, inferenceContext); 1422 //note: lobounds should have at least one element 1423 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds); 1424 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { 1425 throw infer.inferenceException 1426 .setMessage("no.unique.minimal.instance.exists", 1427 uv.qtype, lobounds); 1428 } else { 1429 return owntype; 1430 } 1431 } 1432 }, 1433 /** 1434 * Infer uninstantiated/unbound inference variables occurring in 'throws' 1435 * clause as RuntimeException 1436 */ 1437 THROWS(InferenceBound.UPPER) { 1438 @Override 1439 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1440 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) { 1441 //not a throws undet var 1442 return false; 1443 } 1444 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER) 1445 .diff(t.getDeclaredBounds()).nonEmpty()) { 1446 //not an unbounded undet var 1447 return false; 1448 } 1449 Infer infer = inferenceContext.infer; 1450 for (Type db : t.getDeclaredBounds()) { 1451 if (t.isInterface()) continue; 1452 if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) { 1453 //declared bound is a supertype of RuntimeException 1454 return true; 1455 } 1456 } 1457 //declared bound is more specific then RuntimeException - give up 1458 return false; 1459 } 1460 1461 @Override 1462 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1463 return inferenceContext.infer.syms.runtimeExceptionType; 1464 } 1465 }, 1466 /** 1467 * Instantiate an inference variables using its (ground) upper bounds. Such 1468 * bounds are merged together using glb(). 1469 */ 1470 UPPER(InferenceBound.UPPER) { 1471 @Override 1472 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1473 Infer infer = inferenceContext.infer; 1474 List<Type> hibounds = filterBounds(uv, inferenceContext); 1475 //note: hibounds should have at least one element 1476 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds); 1477 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { 1478 throw infer.inferenceException 1479 .setMessage("no.unique.maximal.instance.exists", 1480 uv.qtype, hibounds); 1481 } else { 1482 return owntype; 1483 } 1484 } 1485 }, 1486 /** 1487 * Like the former; the only difference is that this step can only be applied 1488 * if all upper bounds are ground. 1489 */ 1490 UPPER_LEGACY(InferenceBound.UPPER) { 1491 @Override 1492 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1493 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured(); 1494 } 1495 1496 @Override 1497 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1498 return UPPER.solve(uv, inferenceContext); 1499 } 1500 }, 1501 /** 1502 * Like the former; the only difference is that this step can only be applied 1503 * if all upper/lower bounds are ground. 1504 */ 1505 CAPTURED(InferenceBound.UPPER) { 1506 @Override 1507 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1508 return t.isCaptured() && 1509 !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER)); 1510 } 1511 1512 @Override 1513 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1514 Infer infer = inferenceContext.infer; 1515 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ? 1516 UPPER.solve(uv, inferenceContext) : 1517 infer.syms.objectType; 1518 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ? 1519 LOWER.solve(uv, inferenceContext) : 1520 infer.syms.botType; 1521 CapturedType prevCaptured = (CapturedType)uv.qtype; 1522 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, 1523 upper, lower, prevCaptured.wildcard); 1524 } 1525 }; 1526 1527 final InferenceBound ib; 1528 1529 InferenceStep(InferenceBound ib) { 1530 this.ib = ib; 1531 } 1532 1533 /** 1534 * Find an instantiated type for a given inference variable within 1535 * a given inference context 1536 */ 1537 abstract Type solve(UndetVar uv, InferenceContext inferenceContext); 1538 1539 /** 1540 * Can the inference variable be instantiated using this step? 1541 */ 1542 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1543 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured(); 1544 } 1545 1546 /** 1547 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper) 1548 */ 1549 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) { 1550 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext)); 1551 } 1552 } 1553 1554 /** 1555 * This enumeration defines the sequence of steps to be applied when the 1556 * solver works in legacy mode. The steps in this enumeration reflect 1557 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). 1558 */ 1559 enum LegacyInferenceSteps { 1560 1561 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), 1562 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY)); 1563 1564 final EnumSet<InferenceStep> steps; 1565 1566 LegacyInferenceSteps(EnumSet<InferenceStep> steps) { 1567 this.steps = steps; 1568 } 1569 } 1570 1571 /** 1572 * This enumeration defines the sequence of steps to be applied when the 1573 * graph solver is used. This order is defined so as to maximize compatibility 1574 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). 1575 */ 1576 enum GraphInferenceSteps { 1577 1578 EQ(EnumSet.of(InferenceStep.EQ)), 1579 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), 1580 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED)); 1581 1582 final EnumSet<InferenceStep> steps; 1583 1584 GraphInferenceSteps(EnumSet<InferenceStep> steps) { 1585 this.steps = steps; 1586 } 1587 } 1588 1589 /** 1590 * There are two kinds of dependencies between inference variables. The basic 1591 * kind of dependency (or bound dependency) arises when a variable mention 1592 * another variable in one of its bounds. There's also a more subtle kind 1593 * of dependency that arises when a variable 'might' lead to better constraints 1594 * on another variable (this is typically the case with variables holding up 1595 * stuck expressions). 1596 */ 1597 enum DependencyKind implements GraphUtils.DependencyKind { 1598 1599 /** bound dependency */ 1600 BOUND("dotted"), 1601 /** stuck dependency */ 1602 STUCK("dashed"); 1603 1604 final String dotSyle; 1605 1606 private DependencyKind(String dotSyle) { 1607 this.dotSyle = dotSyle; 1608 } 1609 } 1610 1611 /** 1612 * This is the graph inference solver - the solver organizes all inference variables in 1613 * a given inference context by bound dependencies - in the general case, such dependencies 1614 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build 1615 * an acyclic graph, where all cyclic variables are bundled together. An inference 1616 * step corresponds to solving a node in the acyclic graph - this is done by 1617 * relying on a given strategy (see GraphStrategy). 1618 */ 1619 class GraphSolver { 1620 1621 InferenceContext inferenceContext; 1622 Map<Type, Set<Type>> stuckDeps; 1623 Warner warn; 1624 1625 GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) { 1626 this.inferenceContext = inferenceContext; 1627 this.stuckDeps = stuckDeps; 1628 this.warn = warn; 1629 } 1630 1631 /** 1632 * Solve variables in a given inference context. The amount of variables 1633 * to be solved, and the way in which the underlying acyclic graph is explored 1634 * depends on the selected solver strategy. 1635 */ 1636 void solve(GraphStrategy sstrategy) { 1637 doIncorporation(inferenceContext, warn); //initial propagation of bounds 1638 InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps); 1639 while (!sstrategy.done()) { 1640 if (dependenciesFolder != null) { 1641 //add this graph to the pending queue 1642 pendingGraphs = pendingGraphs.prepend(inferenceGraph.toDot()); 1643 } 1644 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph); 1645 List<Type> varsToSolve = List.from(nodeToSolve.data); 1646 List<Type> saved_undet = inferenceContext.save(); 1647 try { 1648 //repeat until all variables are solved 1649 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) { 1650 //for each inference phase 1651 for (GraphInferenceSteps step : GraphInferenceSteps.values()) { 1652 if (inferenceContext.solveBasic(varsToSolve, step.steps).nonEmpty()) { 1653 doIncorporation(inferenceContext, warn); 1654 continue outer; 1655 } 1656 } 1657 //no progress 1658 throw inferenceException.setMessage(); 1659 } 1660 } 1661 catch (InferenceException ex) { 1662 //did we fail because of interdependent ivars? 1663 inferenceContext.rollback(saved_undet); 1664 instantiateAsUninferredVars(varsToSolve, inferenceContext); 1665 doIncorporation(inferenceContext, warn); 1666 } 1667 inferenceGraph.deleteNode(nodeToSolve); 1668 } 1669 } 1670 1671 /** 1672 * The dependencies between the inference variables that need to be solved 1673 * form a (possibly cyclic) graph. This class reduces the original dependency graph 1674 * to an acyclic version, where cyclic nodes are folded into a single 'super node'. 1675 */ 1676 class InferenceGraph { 1677 1678 /** 1679 * This class represents a node in the graph. Each node corresponds 1680 * to an inference variable and has edges (dependencies) on other 1681 * nodes. The node defines an entry point that can be used to receive 1682 * updates on the structure of the graph this node belongs to (used to 1683 * keep dependencies in sync). 1684 */ 1685 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements DottableNode<ListBuffer<Type>, Node> { 1686 1687 /** map listing all dependencies (grouped by kind) */ 1688 EnumMap<DependencyKind, Set<Node>> deps; 1689 1690 Node(Type ivar) { 1691 super(ListBuffer.of(ivar)); 1692 this.deps = new EnumMap<>(DependencyKind.class); 1693 } 1694 1695 @Override 1696 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() { 1697 return DependencyKind.values(); 1698 } 1699 1700 public Iterable<? extends Node> getAllDependencies() { 1701 return getDependencies(DependencyKind.values()); 1702 } 1703 1704 @Override 1705 public Collection<? extends Node> getDependenciesByKind(GraphUtils.DependencyKind dk) { 1706 return getDependencies((DependencyKind)dk); 1707 } 1708 1709 /** 1710 * Retrieves all dependencies with given kind(s). 1711 */ 1712 protected Set<Node> getDependencies(DependencyKind... depKinds) { 1713 Set<Node> buf = new LinkedHashSet<>(); 1714 for (DependencyKind dk : depKinds) { 1715 Set<Node> depsByKind = deps.get(dk); 1716 if (depsByKind != null) { 1717 buf.addAll(depsByKind); 1718 } 1719 } 1720 return buf; 1721 } 1722 1723 /** 1724 * Adds dependency with given kind. 1725 */ 1726 protected void addDependency(DependencyKind dk, Node depToAdd) { 1727 Set<Node> depsByKind = deps.get(dk); 1728 if (depsByKind == null) { 1729 depsByKind = new LinkedHashSet<>(); 1730 deps.put(dk, depsByKind); 1731 } 1732 depsByKind.add(depToAdd); 1733 } 1734 1735 /** 1736 * Add multiple dependencies of same given kind. 1737 */ 1738 protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) { 1739 for (Node n : depsToAdd) { 1740 addDependency(dk, n); 1741 } 1742 } 1743 1744 /** 1745 * Remove a dependency, regardless of its kind. 1746 */ 1747 protected Set<DependencyKind> removeDependency(Node n) { 1748 Set<DependencyKind> removedKinds = new HashSet<>(); 1749 for (DependencyKind dk : DependencyKind.values()) { 1750 Set<Node> depsByKind = deps.get(dk); 1751 if (depsByKind == null) continue; 1752 if (depsByKind.remove(n)) { 1753 removedKinds.add(dk); 1754 } 1755 } 1756 return removedKinds; 1757 } 1758 1759 /** 1760 * Compute closure of a give node, by recursively walking 1761 * through all its dependencies (of given kinds) 1762 */ 1763 protected Set<Node> closure(DependencyKind... depKinds) { 1764 boolean progress = true; 1765 Set<Node> closure = new HashSet<>(); 1766 closure.add(this); 1767 while (progress) { 1768 progress = false; 1769 for (Node n1 : new HashSet<>(closure)) { 1770 progress = closure.addAll(n1.getDependencies(depKinds)); 1771 } 1772 } 1773 return closure; 1774 } 1775 1776 /** 1777 * Is this node a leaf? This means either the node has no dependencies, 1778 * or it just has self-dependencies. 1779 */ 1780 protected boolean isLeaf() { 1781 //no deps, or only one self dep 1782 Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK); 1783 if (allDeps.isEmpty()) return true; 1784 for (Node n : allDeps) { 1785 if (n != this) { 1786 return false; 1787 } 1788 } 1789 return true; 1790 } 1791 1792 /** 1793 * Merge this node with another node, acquiring its dependencies. 1794 * This routine is used to merge all cyclic node together and 1795 * form an acyclic graph. 1796 */ 1797 protected void mergeWith(List<? extends Node> nodes) { 1798 for (Node n : nodes) { 1799 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!"); 1800 data.appendList(n.data); 1801 for (DependencyKind dk : DependencyKind.values()) { 1802 addDependencies(dk, n.getDependencies(dk)); 1803 } 1804 } 1805 //update deps 1806 EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<>(DependencyKind.class); 1807 for (DependencyKind dk : DependencyKind.values()) { 1808 for (Node d : getDependencies(dk)) { 1809 Set<Node> depsByKind = deps2.get(dk); 1810 if (depsByKind == null) { 1811 depsByKind = new LinkedHashSet<>(); 1812 deps2.put(dk, depsByKind); 1813 } 1814 if (data.contains(d.data.first())) { 1815 depsByKind.add(this); 1816 } else { 1817 depsByKind.add(d); 1818 } 1819 } 1820 } 1821 deps = deps2; 1822 } 1823 1824 /** 1825 * Notify all nodes that something has changed in the graph 1826 * topology. 1827 */ 1828 private void graphChanged(Node from, Node to) { 1829 for (DependencyKind dk : removeDependency(from)) { 1830 if (to != null) { 1831 addDependency(dk, to); 1832 } 1833 } 1834 } 1835 1836 @Override 1837 public Properties nodeAttributes() { 1838 Properties p = new Properties(); 1839 p.put("label", "\"" + toString() + "\""); 1840 return p; 1841 } 1842 1843 @Override 1844 public Properties dependencyAttributes(Node sink, GraphUtils.DependencyKind dk) { 1845 Properties p = new Properties(); 1846 p.put("style", ((DependencyKind)dk).dotSyle); 1847 if (dk == DependencyKind.STUCK) return p; 1848 else { 1849 StringBuilder buf = new StringBuilder(); 1850 String sep = ""; 1851 for (Type from : data) { 1852 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from); 1853 for (Type bound : uv.getBounds(InferenceBound.values())) { 1854 if (bound.containsAny(List.from(sink.data))) { 1855 buf.append(sep); 1856 buf.append(bound); 1857 sep = ","; 1858 } 1859 } 1860 } 1861 p.put("label", "\"" + buf.toString() + "\""); 1862 } 1863 return p; 1864 } 1865 } 1866 1867 /** the nodes in the inference graph */ 1868 ArrayList<Node> nodes; 1869 1870 InferenceGraph(Map<Type, Set<Type>> optDeps) { 1871 initNodes(optDeps); 1872 } 1873 1874 /** 1875 * Basic lookup helper for retrieving a graph node given an inference 1876 * variable type. 1877 */ 1878 public Node findNode(Type t) { 1879 for (Node n : nodes) { 1880 if (n.data.contains(t)) { 1881 return n; 1882 } 1883 } 1884 return null; 1885 } 1886 1887 /** 1888 * Delete a node from the graph. This update the underlying structure 1889 * of the graph (including dependencies) via listeners updates. 1890 */ 1891 public void deleteNode(Node n) { 1892 Assert.check(nodes.contains(n)); 1893 nodes.remove(n); 1894 notifyUpdate(n, null); 1895 } 1896 1897 /** 1898 * Notify all nodes of a change in the graph. If the target node is 1899 * {@code null} the source node is assumed to be removed. 1900 */ 1901 void notifyUpdate(Node from, Node to) { 1902 for (Node n : nodes) { 1903 n.graphChanged(from, to); 1904 } 1905 } 1906 1907 /** 1908 * Create the graph nodes. First a simple node is created for every inference 1909 * variables to be solved. Then Tarjan is used to found all connected components 1910 * in the graph. For each component containing more than one node, a super node is 1911 * created, effectively replacing the original cyclic nodes. 1912 */ 1913 void initNodes(Map<Type, Set<Type>> stuckDeps) { 1914 //add nodes 1915 nodes = new ArrayList<>(); 1916 for (Type t : inferenceContext.restvars()) { 1917 nodes.add(new Node(t)); 1918 } 1919 //add dependencies 1920 for (Node n_i : nodes) { 1921 Type i = n_i.data.first(); 1922 Set<Type> optDepsByNode = stuckDeps.get(i); 1923 for (Node n_j : nodes) { 1924 Type j = n_j.data.first(); 1925 UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i); 1926 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) { 1927 //update i's bound dependencies 1928 n_i.addDependency(DependencyKind.BOUND, n_j); 1929 } 1930 if (optDepsByNode != null && optDepsByNode.contains(j)) { 1931 //update i's stuck dependencies 1932 n_i.addDependency(DependencyKind.STUCK, n_j); 1933 } 1934 } 1935 } 1936 //merge cyclic nodes 1937 ArrayList<Node> acyclicNodes = new ArrayList<>(); 1938 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { 1939 if (conSubGraph.length() > 1) { 1940 Node root = conSubGraph.head; 1941 root.mergeWith(conSubGraph.tail); 1942 for (Node n : conSubGraph) { 1943 notifyUpdate(n, root); 1944 } 1945 } 1946 acyclicNodes.add(conSubGraph.head); 1947 } 1948 nodes = acyclicNodes; 1949 } 1950 1951 /** 1952 * Debugging: dot representation of this graph 1953 */ 1954 String toDot() { 1955 StringBuilder buf = new StringBuilder(); 1956 for (Type t : inferenceContext.undetvars) { 1957 UndetVar uv = (UndetVar)t; 1958 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n", 1959 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER), 1960 uv.getBounds(InferenceBound.EQ))); 1961 } 1962 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString()); 1963 } 1964 } 1965 } 1966 // </editor-fold> 1967 1968 // <editor-fold defaultstate="collapsed" desc="Inference context"> 1969 /** 1970 * Functional interface for defining inference callbacks. Certain actions 1971 * (i.e. subtyping checks) might need to be redone after all inference variables 1972 * have been fixed. 1973 */ 1974 interface FreeTypeListener { 1975 void typesInferred(InferenceContext inferenceContext); 1976 } 1977 1978 final InferenceContext emptyContext; 1979 // </editor-fold> 1980} 1981