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