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