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