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