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