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