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