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