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