Infer.java revision 3613:34dea0a7b9ab
1240616Sjimharris/* 2253296Sjimharris * Copyright (c) 1999, 2016, Oracle and/or its affiliates. All rights reserved. 3240616Sjimharris * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4240616Sjimharris * 5240616Sjimharris * This code is free software; you can redistribute it and/or modify it 6240616Sjimharris * under the terms of the GNU General Public License version 2 only, as 7240616Sjimharris * published by the Free Software Foundation. Oracle designates this 8240616Sjimharris * particular file as subject to the "Classpath" exception as provided 9240616Sjimharris * by Oracle in the LICENSE file that accompanied this code. 10240616Sjimharris * 11240616Sjimharris * This code is distributed in the hope that it will be useful, but WITHOUT 12240616Sjimharris * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13240616Sjimharris * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14240616Sjimharris * version 2 for more details (a copy is included in the LICENSE file that 15240616Sjimharris * accompanied this code). 16240616Sjimharris * 17240616Sjimharris * You should have received a copy of the GNU General Public License version 18240616Sjimharris * 2 along with this work; if not, write to the Free Software Foundation, 19240616Sjimharris * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20240616Sjimharris * 21240616Sjimharris * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22240616Sjimharris * or visit www.oracle.com if you need additional information or have any 23240616Sjimharris * questions. 24240616Sjimharris */ 25240616Sjimharris 26240616Sjimharrispackage com.sun.tools.javac.comp; 27240616Sjimharris 28240616Sjimharrisimport com.sun.tools.javac.code.Type.UndetVar.UndetVarListener; 29240616Sjimharrisimport com.sun.tools.javac.tree.JCTree; 30240616Sjimharrisimport com.sun.tools.javac.tree.JCTree.JCTypeCast; 31240616Sjimharrisimport com.sun.tools.javac.tree.TreeInfo; 32240616Sjimharrisimport com.sun.tools.javac.util.*; 33240616Sjimharrisimport com.sun.tools.javac.util.GraphUtils.DottableNode; 34240616Sjimharrisimport com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition; 35240616Sjimharrisimport com.sun.tools.javac.util.List; 36240616Sjimharrisimport com.sun.tools.javac.code.*; 37240616Sjimharrisimport com.sun.tools.javac.code.Type.*; 38240616Sjimharrisimport com.sun.tools.javac.code.Type.UndetVar.InferenceBound; 39240616Sjimharrisimport com.sun.tools.javac.code.Symbol.*; 40240616Sjimharrisimport com.sun.tools.javac.comp.DeferredAttr.AttrMode; 41240616Sjimharrisimport com.sun.tools.javac.comp.DeferredAttr.DeferredAttrContext; 42240616Sjimharrisimport com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; 43253631Sjimharrisimport com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; 44253631Sjimharrisimport com.sun.tools.javac.comp.Resolve.InapplicableMethodException; 45240616Sjimharrisimport com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; 46240616Sjimharris 47240616Sjimharrisimport java.io.IOException; 48240616Sjimharrisimport java.io.Writer; 49240616Sjimharrisimport java.nio.file.Files; 50252222Sjimharrisimport java.nio.file.Path; 51240616Sjimharrisimport java.nio.file.Paths; 52240616Sjimharrisimport java.util.ArrayList; 53252222Sjimharrisimport java.util.Collection; 54252222Sjimharrisimport java.util.Collections; 55252222Sjimharrisimport java.util.EnumSet; 56240616Sjimharrisimport java.util.HashMap; 57240616Sjimharrisimport java.util.HashSet; 58240616Sjimharrisimport java.util.Map; 59240616Sjimharrisimport java.util.Optional; 60240616Sjimharrisimport java.util.Properties; 61240616Sjimharrisimport java.util.Set; 62240616Sjimharrisimport java.util.function.BiFunction; 63240616Sjimharrisimport java.util.function.BiPredicate; 64240616Sjimharrisimport java.util.stream.Collectors; 65240616Sjimharris 66240616Sjimharrisimport com.sun.tools.javac.main.Option; 67240616Sjimharris 68240616Sjimharrisimport static com.sun.tools.javac.code.TypeTag.*; 69240616Sjimharris 70240616Sjimharris/** Helper class for type parameter inference, used by the attribution phase. 71240616Sjimharris * 72240616Sjimharris * <p><b>This is NOT part of any supported API. 73240616Sjimharris * If you write code that depends on this, you do so at your own risk. 74240616Sjimharris * This code and its internal interfaces are subject to change or 75252222Sjimharris * deletion without notice.</b> 76252222Sjimharris */ 77240616Sjimharrispublic class Infer { 78240616Sjimharris protected static final Context.Key<Infer> inferKey = new Context.Key<>(); 79252222Sjimharris 80240616Sjimharris Resolve rs; 81252222Sjimharris Check chk; 82252222Sjimharris Symtab syms; 83252222Sjimharris Types types; 84252222Sjimharris JCDiagnostic.Factory diags; 85252222Sjimharris Log log; 86252222Sjimharris 87252222Sjimharris /** should the graph solver be used? */ 88240616Sjimharris boolean allowGraphInference; 89240616Sjimharris 90240616Sjimharris /** 91240616Sjimharris * folder in which the inference dependency graphs should be written. 92240616Sjimharris */ 93240616Sjimharris private final String dependenciesFolder; 94240616Sjimharris 95240616Sjimharris /** 96240616Sjimharris * List of graphs awaiting to be dumped to a file. 97240616Sjimharris */ 98240616Sjimharris private List<String> pendingGraphs; 99240616Sjimharris 100240616Sjimharris public static Infer instance(Context context) { 101240616Sjimharris Infer instance = context.get(inferKey); 102240616Sjimharris if (instance == null) 103240616Sjimharris instance = new Infer(context); 104240616Sjimharris return instance; 105240616Sjimharris } 106240616Sjimharris 107253631Sjimharris protected Infer(Context context) { 108240616Sjimharris context.put(inferKey, this); 109240616Sjimharris 110240616Sjimharris rs = Resolve.instance(context); 111240616Sjimharris chk = Check.instance(context); 112240616Sjimharris syms = Symtab.instance(context); 113240616Sjimharris types = Types.instance(context); 114240616Sjimharris diags = JCDiagnostic.Factory.instance(context); 115240616Sjimharris log = Log.instance(context); 116240616Sjimharris inferenceException = new InferenceException(diags); 117240616Sjimharris Options options = Options.instance(context); 118240616Sjimharris allowGraphInference = Source.instance(context).allowGraphInference() 119240616Sjimharris && options.isUnset("useLegacyInference"); 120252222Sjimharris dependenciesFolder = options.get("debug.dumpInferenceGraphsTo"); 121252222Sjimharris pendingGraphs = List.nil(); 122240616Sjimharris 123252222Sjimharris emptyContext = new InferenceContext(this, List.<Type>nil()); 124252222Sjimharris } 125252222Sjimharris 126240616Sjimharris /** A value for prototypes that admit any type, including polymorphic ones. */ 127240616Sjimharris public static final Type anyPoly = new JCNoType(); 128240616Sjimharris 129240616Sjimharris /** 130240616Sjimharris * This exception class is design to store a list of diagnostics corresponding 131240616Sjimharris * to inference errors that can arise during a method applicability check. 132252222Sjimharris */ 133252222Sjimharris public static class InferenceException extends InapplicableMethodException { 134240616Sjimharris private static final long serialVersionUID = 0; 135252222Sjimharris 136252222Sjimharris List<JCDiagnostic> messages = List.nil(); 137252222Sjimharris 138252222Sjimharris InferenceException(JCDiagnostic.Factory diags) { 139240616Sjimharris super(diags); 140240616Sjimharris } 141252222Sjimharris 142252222Sjimharris @Override 143252222Sjimharris InapplicableMethodException setMessage() { 144252222Sjimharris //no message to set 145252222Sjimharris return this; 146252222Sjimharris } 147252222Sjimharris 148240616Sjimharris @Override 149240616Sjimharris InapplicableMethodException setMessage(JCDiagnostic diag) { 150240616Sjimharris messages = messages.append(diag); 151240616Sjimharris return this; 152240616Sjimharris } 153240616Sjimharris 154240616Sjimharris @Override 155240616Sjimharris public JCDiagnostic getDiagnostic() { 156240616Sjimharris return messages.head; 157240616Sjimharris } 158240616Sjimharris 159240616Sjimharris void clear() { 160240616Sjimharris messages = List.nil(); 161240616Sjimharris } 162240616Sjimharris } 163240616Sjimharris 164240616Sjimharris protected final InferenceException inferenceException; 165240616Sjimharris 166240616Sjimharris // <editor-fold defaultstate="collapsed" desc="Inference routines"> 167240616Sjimharris /** 168240616Sjimharris * Main inference entry point - instantiate a generic method type 169240616Sjimharris * using given argument types and (possibly) an expected target-type. 170240616Sjimharris */ 171240616Sjimharris Type instantiateMethod( Env<AttrContext> env, 172240616Sjimharris List<Type> tvars, 173240616Sjimharris MethodType mt, 174240616Sjimharris Attr.ResultInfo resultInfo, 175240616Sjimharris MethodSymbol msym, 176240616Sjimharris List<Type> argtypes, 177240616Sjimharris boolean allowBoxing, 178240616Sjimharris boolean useVarargs, 179252222Sjimharris Resolve.MethodResolutionContext resolveContext, 180240616Sjimharris Warner warn) throws InferenceException { 181240616Sjimharris //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG 182240616Sjimharris final InferenceContext inferenceContext = new InferenceContext(this, tvars); //B0 183240616Sjimharris inferenceException.clear(); 184240616Sjimharris try { 185240616Sjimharris DeferredAttr.DeferredAttrContext deferredAttrContext = 186240616Sjimharris resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn); 187240616Sjimharris 188252222Sjimharris resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2 189240616Sjimharris argtypes, mt.getParameterTypes(), warn); 190240616Sjimharris 191240616Sjimharris if (allowGraphInference && resultInfo != null && resultInfo.pt == anyPoly) { 192240616Sjimharris doIncorporation(inferenceContext, warn); 193240616Sjimharris //we are inside method attribution - just return a partially inferred type 194252222Sjimharris return new PartiallyInferredMethodType(mt, inferenceContext, env, warn); 195240616Sjimharris } else if (allowGraphInference && 196240616Sjimharris resultInfo != null && 197240616Sjimharris !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 198240616Sjimharris //inject return constraints earlier 199240616Sjimharris doIncorporation(inferenceContext, warn); //propagation 200240616Sjimharris 201240616Sjimharris boolean shouldPropagate = shouldPropagate(mt.getReturnType(), resultInfo, inferenceContext); 202240616Sjimharris 203240616Sjimharris InferenceContext minContext = shouldPropagate ? 204240616Sjimharris inferenceContext.min(roots(mt, deferredAttrContext), true, warn) : 205240616Sjimharris inferenceContext; 206240616Sjimharris 207240616Sjimharris Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3 208240616Sjimharris mt, minContext); 209240616Sjimharris mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype); 210240616Sjimharris 211240616Sjimharris //propagate outwards if needed 212240616Sjimharris if (shouldPropagate) { 213240616Sjimharris //propagate inference context outwards and exit 214240616Sjimharris minContext.dupTo(resultInfo.checkContext.inferenceContext()); 215240616Sjimharris deferredAttrContext.complete(); 216240616Sjimharris return mt; 217240616Sjimharris } 218240616Sjimharris } 219240616Sjimharris 220240616Sjimharris deferredAttrContext.complete(); 221240616Sjimharris 222240616Sjimharris // minimize as yet undetermined type variables 223240616Sjimharris if (allowGraphInference) { 224240616Sjimharris inferenceContext.solve(warn); 225240616Sjimharris } else { 226240616Sjimharris inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst 227240616Sjimharris } 228240616Sjimharris 229240616Sjimharris mt = (MethodType)inferenceContext.asInstType(mt); 230240616Sjimharris 231240616Sjimharris if (!allowGraphInference && 232252222Sjimharris inferenceContext.restvars().nonEmpty() && 233240616Sjimharris resultInfo != null && 234240616Sjimharris !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 235240616Sjimharris generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext); 236240616Sjimharris inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst 237252222Sjimharris mt = (MethodType)inferenceContext.asInstType(mt); 238252222Sjimharris } 239240616Sjimharris 240240616Sjimharris if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) { 241240616Sjimharris log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt); 242240616Sjimharris } 243240616Sjimharris 244240616Sjimharris // return instantiated version of method type 245240616Sjimharris return mt; 246240616Sjimharris } finally { 247240616Sjimharris if (resultInfo != null || !allowGraphInference) { 248240616Sjimharris inferenceContext.notifyChange(); 249240616Sjimharris } else { 250240616Sjimharris inferenceContext.notifyChange(inferenceContext.boundedVars()); 251240616Sjimharris } 252240616Sjimharris if (resultInfo == null) { 253240616Sjimharris /* if the is no result info then we can clear the capture types 254240616Sjimharris * cache without affecting any result info check 255240616Sjimharris */ 256240616Sjimharris inferenceContext.captureTypeCache.clear(); 257240616Sjimharris } 258240616Sjimharris dumpGraphsIfNeeded(env.tree, msym, resolveContext); 259252222Sjimharris } 260252222Sjimharris } 261240616Sjimharris //where 262252222Sjimharris private boolean shouldPropagate(Type restype, Attr.ResultInfo target, InferenceContext inferenceContext) { 263240616Sjimharris return target.checkContext.inferenceContext() != emptyContext && //enclosing context is a generic method 264252222Sjimharris inferenceContext.free(restype) && //return type contains inference vars 265252222Sjimharris (!inferenceContext.inferencevars.contains(restype) || //no eager instantiation is required (as per 18.5.2) 266240616Sjimharris !needsEagerInstantiation((UndetVar)inferenceContext.asUndetVar(restype), target.pt, inferenceContext)); 267252222Sjimharris } 268252222Sjimharris 269252222Sjimharris private List<Type> roots(MethodType mt, DeferredAttrContext deferredAttrContext) { 270252222Sjimharris ListBuffer<Type> roots = new ListBuffer<>(); 271252222Sjimharris roots.add(mt.getReturnType()); 272252222Sjimharris if (deferredAttrContext != null && deferredAttrContext.mode == AttrMode.CHECK) { 273252222Sjimharris roots.addAll(mt.getThrownTypes()); 274252222Sjimharris for (DeferredAttr.DeferredAttrNode n : deferredAttrContext.deferredAttrNodes) { 275252222Sjimharris roots.addAll(n.deferredStuckPolicy.stuckVars()); 276253631Sjimharris roots.addAll(n.deferredStuckPolicy.depVars()); 277252222Sjimharris } 278252222Sjimharris } 279252222Sjimharris return roots.toList(); 280252222Sjimharris } 281252222Sjimharris 282252222Sjimharris /** 283240616Sjimharris * A partially infered method/constructor type; such a type can be checked multiple times 284240616Sjimharris * against different targets. 285240616Sjimharris */ 286253631Sjimharris public class PartiallyInferredMethodType extends MethodType { 287240616Sjimharris public PartiallyInferredMethodType(MethodType mtype, InferenceContext inferenceContext, Env<AttrContext> env, Warner warn) { 288240616Sjimharris super(mtype.getParameterTypes(), mtype.getReturnType(), mtype.getThrownTypes(), mtype.tsym); 289240616Sjimharris this.inferenceContext = inferenceContext; 290240616Sjimharris this.env = env; 291240616Sjimharris this.warn = warn; 292240616Sjimharris } 293252222Sjimharris 294240616Sjimharris /** The inference context. */ 295240616Sjimharris final InferenceContext inferenceContext; 296252222Sjimharris 297252222Sjimharris /** The attribution environment. */ 298240616Sjimharris Env<AttrContext> env; 299240616Sjimharris 300240616Sjimharris /** The warner. */ 301240616Sjimharris final Warner warn; 302240616Sjimharris 303240616Sjimharris @Override 304240616Sjimharris public boolean isPartial() { 305240616Sjimharris return true; 306240616Sjimharris } 307252222Sjimharris 308252222Sjimharris /** 309252222Sjimharris * Checks this type against a target; this means generating return type constraints, solve 310252222Sjimharris * and then roll back the results (to avoid poolluting the context). 311252222Sjimharris */ 312253626Sjimharris Type check(Attr.ResultInfo resultInfo) { 313253626Sjimharris Warner noWarnings = new Warner(null); 314253626Sjimharris inferenceException.clear(); 315253626Sjimharris List<Type> saved_undet = null; 316253631Sjimharris try { 317253631Sjimharris /** we need to save the inference context before generating target type constraints. 318240616Sjimharris * This constraints may pollute the inference context and make it useless in case we 319253631Sjimharris * need to use it several times: with several targets. 320253631Sjimharris */ 321253631Sjimharris saved_undet = inferenceContext.save(); 322240616Sjimharris if (allowGraphInference && !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { 323253631Sjimharris boolean shouldPropagate = shouldPropagate(getReturnType(), resultInfo, inferenceContext); 324240616Sjimharris 325240616Sjimharris InferenceContext minContext = shouldPropagate ? 326240616Sjimharris inferenceContext.min(roots(asMethodType(), null), false, warn) : 327240616Sjimharris inferenceContext; 328240616Sjimharris 329240616Sjimharris MethodType other = (MethodType)minContext.update(asMethodType()); 330240616Sjimharris Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3 331240616Sjimharris other, minContext); 332240616Sjimharris 333240616Sjimharris if (shouldPropagate) { 334240616Sjimharris //propagate inference context outwards and exit 335240616Sjimharris minContext.dupTo(resultInfo.checkContext.inferenceContext(), 336240616Sjimharris resultInfo.checkContext.deferredAttrContext().insideOverloadPhase()); 337240616Sjimharris return newRestype; 338252222Sjimharris } 339252222Sjimharris } 340252222Sjimharris inferenceContext.solve(noWarnings); 341253629Sjimharris return inferenceContext.asInstType(this).getReturnType(); 342253629Sjimharris } catch (InferenceException ex) { 343253631Sjimharris resultInfo.checkContext.report(null, ex.getDiagnostic()); 344253631Sjimharris Assert.error(); //cannot get here (the above should throw) 345253631Sjimharris return null; 346253631Sjimharris } finally { 347253631Sjimharris if (saved_undet != null) { 348253631Sjimharris inferenceContext.rollback(saved_undet); 349252222Sjimharris } 350240616Sjimharris } 351240616Sjimharris } 352240616Sjimharris } 353240616Sjimharris 354240616Sjimharris private void dumpGraphsIfNeeded(DiagnosticPosition pos, Symbol msym, Resolve.MethodResolutionContext rsContext) { 355253631Sjimharris int round = 0; 356253631Sjimharris try { 357253631Sjimharris for (String graph : pendingGraphs.reverse()) { 358253631Sjimharris Assert.checkNonNull(dependenciesFolder); 359240616Sjimharris Name name = msym.name == msym.name.table.names.init ? 360253631Sjimharris msym.owner.name : msym.name; 361253631Sjimharris String filename = String.format("%s@%s[mode=%s,step=%s]_%d.dot", 362240616Sjimharris name, 363253631Sjimharris pos.getStartPosition(), 364240616Sjimharris rsContext.attrMode(), 365240616Sjimharris rsContext.step, 366240616Sjimharris round); 367240616Sjimharris Path dotFile = Paths.get(dependenciesFolder, filename); 368240616Sjimharris try (Writer w = Files.newBufferedWriter(dotFile)) { 369240616Sjimharris w.append(graph); 370240616Sjimharris } 371240616Sjimharris round++; 372240616Sjimharris } 373240616Sjimharris } catch (IOException ex) { 374253631Sjimharris Assert.error("Error occurred when dumping inference graph: " + ex.getMessage()); 375240616Sjimharris } finally { 376240616Sjimharris pendingGraphs = List.nil(); 377253631Sjimharris } 378253631Sjimharris } 379253631Sjimharris 380253631Sjimharris /** 381240616Sjimharris * Generate constraints from the generic method's return type. If the method 382240616Sjimharris * call occurs in a context where a type T is expected, use the expected 383240616Sjimharris * type to derive more constraints on the generic method inference variables. 384240616Sjimharris */ 385252222Sjimharris Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo, 386252222Sjimharris MethodType mt, InferenceContext inferenceContext) { 387252222Sjimharris InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext(); 388252222Sjimharris Type from = mt.getReturnType(); 389252222Sjimharris if (mt.getReturnType().containsAny(inferenceContext.inferencevars) && 390252222Sjimharris rsInfoInfContext != emptyContext) { 391252222Sjimharris from = types.capture(from); 392252222Sjimharris //add synthetic captured ivars 393252222Sjimharris for (Type t : from.getTypeArguments()) { 394252222Sjimharris if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) { 395252222Sjimharris inferenceContext.addVar((TypeVar)t); 396252222Sjimharris } 397252222Sjimharris } 398252222Sjimharris } 399252222Sjimharris Type qtype = inferenceContext.asUndetVar(from); 400252222Sjimharris Type to = resultInfo.pt; 401252222Sjimharris 402252222Sjimharris if (qtype.hasTag(VOID)) { 403252222Sjimharris to = syms.voidType; 404 } else if (to.hasTag(NONE)) { 405 to = from.isPrimitive() ? from : syms.objectType; 406 } else if (qtype.hasTag(UNDETVAR)) { 407 if (resultInfo.pt.isReference()) { 408 if (needsEagerInstantiation((UndetVar)qtype, to, inferenceContext)) { 409 to = generateReferenceToTargetConstraint(tree, (UndetVar)qtype, to, resultInfo, inferenceContext); 410 } 411 } else { 412 if (to.isPrimitive()) { 413 to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to, 414 resultInfo, inferenceContext); 415 } 416 } 417 } else if (rsInfoInfContext.free(resultInfo.pt)) { 418 //propagation - cache captured vars 419 qtype = inferenceContext.asUndetVar(rsInfoInfContext.cachedCapture(tree, from, false)); 420 } 421 Assert.check(allowGraphInference || !rsInfoInfContext.free(to), 422 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion"); 423 //we need to skip capture? 424 Warner retWarn = new Warner(); 425 if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) || 426 //unchecked conversion is not allowed in source 7 mode 427 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) { 428 throw inferenceException 429 .setMessage("infer.no.conforming.instance.exists", 430 inferenceContext.restvars(), mt.getReturnType(), to); 431 } 432 return from; 433 } 434 435 private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from, 436 Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) { 437 if (!allowGraphInference) { 438 //if legacy, just return boxed type 439 return types.boxedClass(to).type; 440 } 441 //if graph inference we need to skip conflicting boxed bounds... 442 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER, 443 InferenceBound.LOWER)) { 444 Type boundAsPrimitive = types.unboxedType(t); 445 if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) { 446 continue; 447 } 448 return generateReferenceToTargetConstraint(tree, from, to, 449 resultInfo, inferenceContext); 450 } 451 return types.boxedClass(to).type; 452 } 453 454 private boolean needsEagerInstantiation(UndetVar from, Type to, InferenceContext inferenceContext) { 455 Type captureOfTo = types.capture(to); 456 /* T is a reference type, but is not a wildcard-parameterized type, and either 457 */ 458 if (captureOfTo == to) { //not a wildcard parameterized type 459 /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha, 460 * where S is a wildcard-parameterized type, or 461 */ 462 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { 463 Type captureOfBound = types.capture(t); 464 if (captureOfBound != t) { 465 return true; 466 } 467 } 468 469 /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha, 470 * where S1 and S2 have supertypes that are two different 471 * parameterizations of the same generic class or interface. 472 */ 473 for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) { 474 for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) { 475 if (aLowerBound != anotherLowerBound && 476 !inferenceContext.free(aLowerBound) && 477 !inferenceContext.free(anotherLowerBound) && 478 commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) { 479 return true; 480 } 481 } 482 } 483 } 484 485 /* T is a parameterization of a generic class or interface, G, 486 * and B2 contains a bound of one of the forms alpha = S or S <: alpha, 487 * where there exists no type of the form G<...> that is a 488 * supertype of S, but the raw type G is a supertype of S 489 */ 490 if (to.isParameterized()) { 491 for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { 492 Type sup = types.asSuper(t, to.tsym); 493 if (sup != null && sup.isRaw()) { 494 return true; 495 } 496 } 497 } 498 return false; 499 } 500 501 private boolean commonSuperWithDiffParameterization(Type t, Type s) { 502 for (Pair<Type, Type> supers : getParameterizedSupers(t, s)) { 503 if (!types.isSameType(supers.fst, supers.snd)) return true; 504 } 505 return false; 506 } 507 508 private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from, 509 Type to, Attr.ResultInfo resultInfo, 510 InferenceContext inferenceContext) { 511 inferenceContext.solve(List.of(from.qtype), new Warner()); 512 inferenceContext.notifyChange(); 513 Type capturedType = resultInfo.checkContext.inferenceContext() 514 .cachedCapture(tree, from.getInst(), false); 515 if (types.isConvertible(capturedType, 516 resultInfo.checkContext.inferenceContext().asUndetVar(to))) { 517 //effectively skip additional return-type constraint generation (compatibility) 518 return syms.objectType; 519 } 520 return to; 521 } 522 523 /** 524 * Infer cyclic inference variables as described in 15.12.2.8. 525 */ 526 void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) { 527 ListBuffer<Type> todo = new ListBuffer<>(); 528 //step 1 - create fresh tvars 529 for (Type t : vars) { 530 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t); 531 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER); 532 if (Type.containsAny(upperBounds, vars)) { 533 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner); 534 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeIntersectionType(uv.getBounds(InferenceBound.UPPER)), null); 535 todo.append(uv); 536 uv.setInst(fresh_tvar.type); 537 } else if (upperBounds.nonEmpty()) { 538 uv.setInst(types.glb(upperBounds)); 539 } else { 540 uv.setInst(syms.objectType); 541 } 542 } 543 //step 2 - replace fresh tvars in their bounds 544 List<Type> formals = vars; 545 for (Type t : todo) { 546 UndetVar uv = (UndetVar)t; 547 TypeVar ct = (TypeVar)uv.getInst(); 548 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct))); 549 if (ct.bound.isErroneous()) { 550 //report inference error if glb fails 551 reportBoundError(uv, InferenceBound.UPPER); 552 } 553 formals = formals.tail; 554 } 555 } 556 557 /** 558 * Compute a synthetic method type corresponding to the requested polymorphic 559 * method signature. The target return type is computed from the immediately 560 * enclosing scope surrounding the polymorphic-signature call. 561 */ 562 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, 563 MethodSymbol spMethod, // sig. poly. method or null if none 564 Resolve.MethodResolutionContext resolveContext, 565 List<Type> argtypes) { 566 final Type restype; 567 568 if (spMethod == null || types.isSameType(spMethod.getReturnType(), syms.objectType, true)) { 569 // The return type of the polymorphic signature is polymorphic, 570 // and is computed from the enclosing tree E, as follows: 571 // if E is a cast, then use the target type of the cast expression 572 // as a return type; if E is an expression statement, the return 573 // type is 'void'; otherwise 574 // the return type is simply 'Object'. A correctness check ensures 575 // that env.next refers to the lexically enclosing environment in 576 // which the polymorphic signature call environment is nested. 577 578 switch (env.next.tree.getTag()) { 579 case TYPECAST: 580 JCTypeCast castTree = (JCTypeCast)env.next.tree; 581 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ? 582 castTree.clazz.type : 583 syms.objectType; 584 break; 585 case EXEC: 586 JCTree.JCExpressionStatement execTree = 587 (JCTree.JCExpressionStatement)env.next.tree; 588 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ? 589 syms.voidType : 590 syms.objectType; 591 break; 592 default: 593 restype = syms.objectType; 594 } 595 } else { 596 // The return type of the polymorphic signature is fixed 597 // (not polymorphic) 598 restype = spMethod.getReturnType(); 599 } 600 601 List<Type> paramtypes = argtypes.map(new ImplicitArgType(spMethod, resolveContext.step)); 602 List<Type> exType = spMethod != null ? 603 spMethod.getThrownTypes() : 604 List.of(syms.throwableType); // make it throw all exceptions 605 606 MethodType mtype = new MethodType(paramtypes, 607 restype, 608 exType, 609 syms.methodClass); 610 return mtype; 611 } 612 //where 613 class ImplicitArgType extends DeferredAttr.DeferredTypeMap { 614 615 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) { 616 (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase); 617 } 618 619 @Override 620 public Type visitClassType(ClassType t, Void aVoid) { 621 return types.erasure(t); 622 } 623 624 @Override 625 public Type visitType(Type t, Void _unused) { 626 if (t.hasTag(DEFERRED)) { 627 return visit(super.visitType(t, null)); 628 } else if (t.hasTag(BOT)) 629 // nulls type as the marker type Null (which has no instances) 630 // infer as java.lang.Void for now 631 t = types.boxedClass(syms.voidType).type; 632 return t; 633 } 634 } 635 636 TypeMapping<Void> fromTypeVarFun = new TypeMapping<Void>() { 637 @Override 638 public Type visitTypeVar(TypeVar tv, Void aVoid) { 639 return new UndetVar(tv, incorporationEngine(), types); 640 } 641 642 @Override 643 public Type visitCapturedType(CapturedType t, Void aVoid) { 644 return new CapturedUndetVar(t, incorporationEngine(), types); 645 } 646 }; 647 648 /** 649 * This method is used to infer a suitable target SAM in case the original 650 * SAM type contains one or more wildcards. An inference process is applied 651 * so that wildcard bounds, as well as explicit lambda/method ref parameters 652 * (where applicable) are used to constraint the solution. 653 */ 654 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface, 655 List<Type> paramTypes, Check.CheckContext checkContext) { 656 if (types.capture(funcInterface) == funcInterface) { 657 //if capture doesn't change the type then return the target unchanged 658 //(this means the target contains no wildcards!) 659 return funcInterface; 660 } else { 661 Type formalInterface = funcInterface.tsym.type; 662 InferenceContext funcInterfaceContext = 663 new InferenceContext(this, funcInterface.tsym.type.getTypeArguments()); 664 665 Assert.check(paramTypes != null); 666 //get constraints from explicit params (this is done by 667 //checking that explicit param types are equal to the ones 668 //in the functional interface descriptors) 669 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes(); 670 if (descParameterTypes.size() != paramTypes.size()) { 671 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda")); 672 return types.createErrorType(funcInterface); 673 } 674 for (Type p : descParameterTypes) { 675 if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) { 676 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); 677 return types.createErrorType(funcInterface); 678 } 679 paramTypes = paramTypes.tail; 680 } 681 682 List<Type> actualTypeargs = funcInterface.getTypeArguments(); 683 for (Type t : funcInterfaceContext.undetvars) { 684 UndetVar uv = (UndetVar)t; 685 Optional<Type> inst = uv.getBounds(InferenceBound.EQ).stream() 686 .filter(b -> !b.containsAny(formalInterface.getTypeArguments())).findFirst(); 687 uv.setInst(inst.orElse(actualTypeargs.head)); 688 actualTypeargs = actualTypeargs.tail; 689 } 690 691 Type owntype = funcInterfaceContext.asInstType(formalInterface); 692 if (!chk.checkValidGenericType(owntype)) { 693 //if the inferred functional interface type is not well-formed, 694 //or if it's not a subtype of the original target, issue an error 695 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); 696 } 697 //propagate constraints as per JLS 18.2.1 698 checkContext.compatible(owntype, funcInterface, types.noWarnings); 699 return owntype; 700 } 701 } 702 // </editor-fold> 703 704 // <editor-fold defaultstate="collapsed" desc="Incorporation"> 705 706 /** 707 * This class is the root of all incorporation actions. 708 */ 709 public abstract class IncorporationAction { 710 UndetVar uv; 711 Type t; 712 713 IncorporationAction(UndetVar uv, Type t) { 714 this.uv = uv; 715 this.t = t; 716 } 717 718 public abstract IncorporationAction dup(UndetVar that); 719 720 /** 721 * Incorporation action entry-point. Subclasses should define the logic associated with 722 * this incorporation action. 723 */ 724 abstract void apply(InferenceContext ic, Warner warn); 725 726 /** 727 * Helper function: perform subtyping through incorporation cache. 728 */ 729 boolean isSubtype(Type s, Type t, Warner warn) { 730 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn); 731 } 732 733 /** 734 * Helper function: perform type-equivalence through incorporation cache. 735 */ 736 boolean isSameType(Type s, Type t) { 737 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null); 738 } 739 740 @Override 741 public String toString() { 742 return String.format("%s[undet=%s,t=%s]", getClass().getSimpleName(), uv.qtype, t); 743 } 744 } 745 746 /** 747 * Bound-check incorporation action. A newly added bound is checked against existing bounds, 748 * to verify its compatibility; each bound is checked using either subtyping or type equivalence. 749 */ 750 class CheckBounds extends IncorporationAction { 751 752 InferenceBound from; 753 BiFunction<InferenceContext, Type, Type> typeFunc; 754 BiPredicate<InferenceContext, Type> optFilter; 755 756 CheckBounds(UndetVar uv, Type t, InferenceBound from) { 757 this(uv, t, InferenceContext::asUndetVar, null, from); 758 } 759 760 CheckBounds(UndetVar uv, Type t, BiFunction<InferenceContext, Type, Type> typeFunc, 761 BiPredicate<InferenceContext, Type> typeFilter, InferenceBound from) { 762 super(uv, t); 763 this.from = from; 764 this.typeFunc = typeFunc; 765 this.optFilter = typeFilter; 766 } 767 768 @Override 769 public IncorporationAction dup(UndetVar that) { 770 return new CheckBounds(that, t, typeFunc, optFilter, from); 771 } 772 773 @Override 774 void apply(InferenceContext inferenceContext, Warner warn) { 775 t = typeFunc.apply(inferenceContext, t); 776 if (optFilter != null && optFilter.test(inferenceContext, t)) return; 777 for (InferenceBound to : boundsToCheck()) { 778 for (Type b : uv.getBounds(to)) { 779 b = typeFunc.apply(inferenceContext, b); 780 if (optFilter != null && optFilter.test(inferenceContext, b)) continue; 781 boolean success = checkBound(t, b, from, to, warn); 782 if (!success) { 783 report(from, to); 784 } 785 } 786 } 787 } 788 789 /** 790 * The list of bound kinds to be checked. 791 */ 792 EnumSet<InferenceBound> boundsToCheck() { 793 return (from == InferenceBound.EQ) ? 794 EnumSet.allOf(InferenceBound.class) : 795 EnumSet.complementOf(EnumSet.of(from)); 796 } 797 798 /** 799 * Is source type 's' compatible with target type 't' given source and target bound kinds? 800 */ 801 boolean checkBound(Type s, Type t, InferenceBound ib_s, InferenceBound ib_t, Warner warn) { 802 if (ib_s.lessThan(ib_t)) { 803 return isSubtype(s, t, warn); 804 } else if (ib_t.lessThan(ib_s)) { 805 return isSubtype(t, s, warn); 806 } else { 807 return isSameType(s, t); 808 } 809 } 810 811 /** 812 * Report a bound check error. 813 */ 814 void report(InferenceBound from, InferenceBound to) { 815 //this is a workaround to preserve compatibility with existing messages 816 if (from == to) { 817 reportBoundError(uv, from); 818 } else if (from == InferenceBound.LOWER || to == InferenceBound.EQ) { 819 reportBoundError(uv, to, from); 820 } else { 821 reportBoundError(uv, from, to); 822 } 823 } 824 825 @Override 826 public String toString() { 827 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, from); 828 } 829 } 830 831 /** 832 * Custom check executed by the legacy incorporation engine. Newly added bounds are checked 833 * against existing eq bounds. 834 */ 835 class EqCheckLegacy extends CheckBounds { 836 EqCheckLegacy(UndetVar uv, Type t, InferenceBound from) { 837 super(uv, t, InferenceContext::asInstType, InferenceContext::free, from); 838 } 839 840 @Override 841 public IncorporationAction dup(UndetVar that) { 842 return new EqCheckLegacy(that, t, from); 843 } 844 845 @Override 846 EnumSet<InferenceBound> boundsToCheck() { 847 return (from == InferenceBound.EQ) ? 848 EnumSet.allOf(InferenceBound.class) : 849 EnumSet.of(InferenceBound.EQ); 850 } 851 } 852 853 /** 854 * Check that the inferred type conforms to all bounds. 855 */ 856 class CheckInst extends CheckBounds { 857 858 EnumSet<InferenceBound> to; 859 860 CheckInst(UndetVar uv, InferenceBound ib, InferenceBound... rest) { 861 this(uv, EnumSet.of(ib, rest)); 862 } 863 864 CheckInst(UndetVar uv, EnumSet<InferenceBound> to) { 865 super(uv, uv.getInst(), InferenceBound.EQ); 866 this.to = to; 867 } 868 869 @Override 870 public IncorporationAction dup(UndetVar that) { 871 return new CheckInst(that, to); 872 } 873 874 @Override 875 EnumSet<InferenceBound> boundsToCheck() { 876 return to; 877 } 878 879 @Override 880 void report(InferenceBound from, InferenceBound to) { 881 reportInstError(uv, to); 882 } 883 } 884 885 /** 886 * Replace undetvars in bounds and check that the inferred type conforms to all bounds. 887 */ 888 class SubstBounds extends CheckInst { 889 SubstBounds(UndetVar uv) { 890 super(uv, InferenceBound.LOWER, InferenceBound.EQ, InferenceBound.UPPER); 891 } 892 893 @Override 894 public IncorporationAction dup(UndetVar that) { 895 return new SubstBounds(that); 896 } 897 898 @Override 899 void apply(InferenceContext inferenceContext, Warner warn) { 900 for (Type undet : inferenceContext.undetvars) { 901 //we could filter out variables not mentioning uv2... 902 UndetVar uv2 = (UndetVar)undet; 903 uv2.substBounds(List.of(uv.qtype), List.of(uv.getInst()), types); 904 checkCompatibleUpperBounds(uv2, inferenceContext); 905 } 906 super.apply(inferenceContext, warn); 907 } 908 909 /** 910 * Make sure that the upper bounds we got so far lead to a solvable inference 911 * variable by making sure that a glb exists. 912 */ 913 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) { 914 List<Type> hibounds = 915 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext)); 916 final Type hb; 917 if (hibounds.isEmpty()) 918 hb = syms.objectType; 919 else if (hibounds.tail.isEmpty()) 920 hb = hibounds.head; 921 else 922 hb = types.glb(hibounds); 923 if (hb == null || hb.isErroneous()) 924 reportBoundError(uv, InferenceBound.UPPER); 925 } 926 } 927 928 /** 929 * Perform pairwise comparison between common generic supertypes of two upper bounds. 930 */ 931 class CheckUpperBounds extends IncorporationAction { 932 933 public CheckUpperBounds(UndetVar uv, Type t) { 934 super(uv, t); 935 } 936 937 @Override 938 public IncorporationAction dup(UndetVar that) { 939 return new CheckUpperBounds(that, t); 940 } 941 942 @Override 943 void apply(InferenceContext inferenceContext, Warner warn) { 944 List<Type> boundList = uv.getBounds(InferenceBound.UPPER).stream() 945 .collect(types.closureCollector(true, types::isSameType)); 946 for (Type b2 : boundList) { 947 if (t == b2) continue; 948 /* This wildcard check is temporary workaround. This code may need to be 949 * revisited once spec bug JDK-7034922 is fixed. 950 */ 951 if (t != b2 && !t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) { 952 for (Pair<Type, Type> commonSupers : getParameterizedSupers(t, b2)) { 953 List<Type> allParamsSuperBound1 = commonSupers.fst.allparams(); 954 List<Type> allParamsSuperBound2 = commonSupers.snd.allparams(); 955 while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) { 956 //traverse the list of all params comparing them 957 if (!allParamsSuperBound1.head.hasTag(WILDCARD) && 958 !allParamsSuperBound2.head.hasTag(WILDCARD)) { 959 if (!isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head), 960 inferenceContext.asUndetVar(allParamsSuperBound2.head))) { 961 reportBoundError(uv, InferenceBound.UPPER); 962 } 963 } 964 allParamsSuperBound1 = allParamsSuperBound1.tail; 965 allParamsSuperBound2 = allParamsSuperBound2.tail; 966 } 967 Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty()); 968 } 969 } 970 } 971 } 972 } 973 974 /** 975 * Perform propagation of bounds. Given a constraint of the kind {@code alpha <: T}, three 976 * kind of propagation occur: 977 * 978 * <li>T is copied into all matching bounds (i.e. lower/eq bounds) B of alpha such that B=beta (forward propagation)</li> 979 * <li>if T=beta, matching bounds (i.e. upper bounds) of beta are copied into alpha (backwards propagation)</li> 980 * <li>if T=beta, sets a symmetric bound on beta (i.e. beta :> alpha) (symmetric propagation) </li> 981 */ 982 class PropagateBounds extends IncorporationAction { 983 984 InferenceBound ib; 985 986 public PropagateBounds(UndetVar uv, Type t, InferenceBound ib) { 987 super(uv, t); 988 this.ib = ib; 989 } 990 991 @Override 992 public IncorporationAction dup(UndetVar that) { 993 return new PropagateBounds(that, t, ib); 994 } 995 996 void apply(InferenceContext inferenceContext, Warner warner) { 997 Type undetT = inferenceContext.asUndetVar(t); 998 if (undetT.hasTag(UNDETVAR) && !((UndetVar)undetT).isCaptured()) { 999 UndetVar uv2 = (UndetVar)undetT; 1000 //symmetric propagation 1001 uv2.addBound(ib.complement(), uv, types); 1002 //backwards propagation 1003 for (InferenceBound ib2 : backwards()) { 1004 for (Type b : uv2.getBounds(ib2)) { 1005 uv.addBound(ib2, b, types); 1006 } 1007 } 1008 } 1009 //forward propagation 1010 for (InferenceBound ib2 : forward()) { 1011 for (Type l : uv.getBounds(ib2)) { 1012 Type undet = inferenceContext.asUndetVar(l); 1013 if (undet.hasTag(TypeTag.UNDETVAR) && !((UndetVar)undet).isCaptured()) { 1014 UndetVar uv2 = (UndetVar)undet; 1015 uv2.addBound(ib, inferenceContext.asInstType(t), types); 1016 } 1017 } 1018 } 1019 } 1020 1021 EnumSet<InferenceBound> forward() { 1022 return (ib == InferenceBound.EQ) ? 1023 EnumSet.of(InferenceBound.EQ) : EnumSet.complementOf(EnumSet.of(ib)); 1024 } 1025 1026 EnumSet<InferenceBound> backwards() { 1027 return (ib == InferenceBound.EQ) ? 1028 EnumSet.allOf(InferenceBound.class) : EnumSet.of(ib); 1029 } 1030 1031 @Override 1032 public String toString() { 1033 return String.format("%s[undet=%s,t=%s,bound=%s]", getClass().getSimpleName(), uv.qtype, t, ib); 1034 } 1035 } 1036 1037 /** 1038 * This class models an incorporation engine. The engine is responsible for listening to 1039 * changes in inference variables and register incorporation actions accordingly. 1040 */ 1041 abstract class AbstractIncorporationEngine implements UndetVarListener { 1042 1043 @Override 1044 public void varInstantiated(UndetVar uv) { 1045 uv.incorporationActions.addFirst(new SubstBounds(uv)); 1046 } 1047 1048 @Override 1049 public void varBoundChanged(UndetVar uv, InferenceBound ib, Type bound, boolean update) { 1050 if (uv.isCaptured()) return; 1051 uv.incorporationActions.addAll(getIncorporationActions(uv, ib, bound, update)); 1052 } 1053 1054 abstract List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update); 1055 } 1056 1057 /** 1058 * A legacy incorporation engine. Used for source <= 7. 1059 */ 1060 AbstractIncorporationEngine legacyEngine = new AbstractIncorporationEngine() { 1061 1062 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) { 1063 ListBuffer<IncorporationAction> actions = new ListBuffer<>(); 1064 Type inst = uv.getInst(); 1065 if (inst != null) { 1066 actions.add(new CheckInst(uv, ib)); 1067 } 1068 actions.add(new EqCheckLegacy(uv, t, ib)); 1069 return actions.toList(); 1070 } 1071 }; 1072 1073 /** 1074 * The standard incorporation engine. Used for source >= 8. 1075 */ 1076 AbstractIncorporationEngine graphEngine = new AbstractIncorporationEngine() { 1077 1078 @Override 1079 List<IncorporationAction> getIncorporationActions(UndetVar uv, InferenceBound ib, Type t, boolean update) { 1080 ListBuffer<IncorporationAction> actions = new ListBuffer<>(); 1081 Type inst = uv.getInst(); 1082 if (inst != null) { 1083 actions.add(new CheckInst(uv, ib)); 1084 } 1085 actions.add(new CheckBounds(uv, t, ib)); 1086 1087 if (update) { 1088 return actions.toList(); 1089 } 1090 1091 if (ib == InferenceBound.UPPER) { 1092 actions.add(new CheckUpperBounds(uv, t)); 1093 } 1094 1095 actions.add(new PropagateBounds(uv, t, ib)); 1096 1097 return actions.toList(); 1098 } 1099 }; 1100 1101 /** 1102 * Get the incorporation engine to be used in this compilation. 1103 */ 1104 AbstractIncorporationEngine incorporationEngine() { 1105 return allowGraphInference ? graphEngine : legacyEngine; 1106 } 1107 1108 /** max number of incorporation rounds. */ 1109 static final int MAX_INCORPORATION_STEPS = 10000; 1110 1111 /** 1112 * Check bounds and perform incorporation. 1113 */ 1114 void doIncorporation(InferenceContext inferenceContext, Warner warn) throws InferenceException { 1115 try { 1116 boolean progress = true; 1117 int round = 0; 1118 while (progress && round < MAX_INCORPORATION_STEPS) { 1119 progress = false; 1120 for (Type t : inferenceContext.undetvars) { 1121 UndetVar uv = (UndetVar)t; 1122 if (!uv.incorporationActions.isEmpty()) { 1123 progress = true; 1124 uv.incorporationActions.removeFirst().apply(inferenceContext, warn); 1125 } 1126 } 1127 round++; 1128 } 1129 } finally { 1130 incorporationCache.clear(); 1131 } 1132 } 1133 1134 /* If for two types t and s there is a least upper bound that contains 1135 * parameterized types G1, G2 ... Gn, then there exists supertypes of 't' of the form 1136 * G1<T1, ..., Tn>, G2<T1, ..., Tn>, ... Gn<T1, ..., Tn> and supertypes of 's' of the form 1137 * G1<S1, ..., Sn>, G2<S1, ..., Sn>, ... Gn<S1, ..., Sn> which will be returned by this method. 1138 * If no such common supertypes exists then an empty list is returned. 1139 * 1140 * As an example for the following input: 1141 * 1142 * t = java.util.ArrayList<java.lang.String> 1143 * s = java.util.List<T> 1144 * 1145 * we get this ouput (singleton list): 1146 * 1147 * [Pair[java.util.List<java.lang.String>,java.util.List<T>]] 1148 */ 1149 private List<Pair<Type, Type>> getParameterizedSupers(Type t, Type s) { 1150 Type lubResult = types.lub(t, s); 1151 if (lubResult == syms.errType || lubResult == syms.botType) { 1152 return List.nil(); 1153 } 1154 List<Type> supertypesToCheck = lubResult.isIntersection() ? 1155 ((IntersectionClassType)lubResult).getComponents() : 1156 List.of(lubResult); 1157 ListBuffer<Pair<Type, Type>> commonSupertypes = new ListBuffer<>(); 1158 for (Type sup : supertypesToCheck) { 1159 if (sup.isParameterized()) { 1160 Type asSuperOfT = asSuper(t, sup); 1161 Type asSuperOfS = asSuper(s, sup); 1162 commonSupertypes.add(new Pair<>(asSuperOfT, asSuperOfS)); 1163 } 1164 } 1165 return commonSupertypes.toList(); 1166 } 1167 //where 1168 private Type asSuper(Type t, Type sup) { 1169 return (sup.hasTag(ARRAY)) ? 1170 new ArrayType(asSuper(types.elemtype(t), types.elemtype(sup)), syms.arrayClass) : 1171 types.asSuper(t, sup.tsym); 1172 } 1173 1174 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn) { 1175 IncorporationBinaryOp newOp = new IncorporationBinaryOp(opKind, op1, op2); 1176 Boolean res = incorporationCache.get(newOp); 1177 if (res == null) { 1178 incorporationCache.put(newOp, res = newOp.apply(warn)); 1179 } 1180 return res; 1181 } 1182 1183 /** 1184 * Three kinds of basic operation are supported as part of an incorporation step: 1185 * (i) subtype check, (ii) same type check and (iii) bound addition (either 1186 * upper/lower/eq bound). 1187 */ 1188 enum IncorporationBinaryOpKind { 1189 IS_SUBTYPE() { 1190 @Override 1191 boolean apply(Type op1, Type op2, Warner warn, Types types) { 1192 return types.isSubtypeUnchecked(op1, op2, warn); 1193 } 1194 }, 1195 IS_SAME_TYPE() { 1196 @Override 1197 boolean apply(Type op1, Type op2, Warner warn, Types types) { 1198 return types.isSameType(op1, op2); 1199 } 1200 }; 1201 1202 abstract boolean apply(Type op1, Type op2, Warner warn, Types types); 1203 } 1204 1205 /** 1206 * This class encapsulates a basic incorporation operation; incorporation 1207 * operations takes two type operands and a kind. Each operation performed 1208 * during an incorporation round is stored in a cache, so that operations 1209 * are not executed unnecessarily (which would potentially lead to adding 1210 * same bounds over and over). 1211 */ 1212 class IncorporationBinaryOp { 1213 1214 IncorporationBinaryOpKind opKind; 1215 Type op1; 1216 Type op2; 1217 1218 IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) { 1219 this.opKind = opKind; 1220 this.op1 = op1; 1221 this.op2 = op2; 1222 } 1223 1224 @Override 1225 public boolean equals(Object o) { 1226 if (!(o instanceof IncorporationBinaryOp)) { 1227 return false; 1228 } else { 1229 IncorporationBinaryOp that = (IncorporationBinaryOp)o; 1230 return opKind == that.opKind && 1231 types.isSameType(op1, that.op1, true) && 1232 types.isSameType(op2, that.op2, true); 1233 } 1234 } 1235 1236 @Override 1237 public int hashCode() { 1238 int result = opKind.hashCode(); 1239 result *= 127; 1240 result += types.hashCode(op1); 1241 result *= 127; 1242 result += types.hashCode(op2); 1243 return result; 1244 } 1245 1246 boolean apply(Warner warn) { 1247 return opKind.apply(op1, op2, warn, types); 1248 } 1249 } 1250 1251 /** an incorporation cache keeps track of all executed incorporation-related operations */ 1252 Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>(); 1253 1254 protected static class BoundFilter implements Filter<Type> { 1255 1256 InferenceContext inferenceContext; 1257 1258 public BoundFilter(InferenceContext inferenceContext) { 1259 this.inferenceContext = inferenceContext; 1260 } 1261 1262 @Override 1263 public boolean accepts(Type t) { 1264 return !t.isErroneous() && !inferenceContext.free(t) && 1265 !t.hasTag(BOT); 1266 } 1267 } 1268 1269 /** 1270 * Incorporation error: mismatch between inferred type and given bound. 1271 */ 1272 void reportInstError(UndetVar uv, InferenceBound ib) { 1273 reportInferenceError( 1274 String.format("inferred.do.not.conform.to.%s.bounds", StringUtils.toLowerCase(ib.name())), 1275 uv.getInst(), 1276 uv.getBounds(ib)); 1277 } 1278 1279 /** 1280 * Incorporation error: mismatch between two (or more) bounds of same kind. 1281 */ 1282 void reportBoundError(UndetVar uv, InferenceBound ib) { 1283 reportInferenceError( 1284 String.format("incompatible.%s.bounds", StringUtils.toLowerCase(ib.name())), 1285 uv.qtype, 1286 uv.getBounds(ib)); 1287 } 1288 1289 /** 1290 * Incorporation error: mismatch between two (or more) bounds of different kinds. 1291 */ 1292 void reportBoundError(UndetVar uv, InferenceBound ib1, InferenceBound ib2) { 1293 reportInferenceError( 1294 String.format("incompatible.%s.%s.bounds", 1295 StringUtils.toLowerCase(ib1.name()), 1296 StringUtils.toLowerCase(ib2.name())), 1297 uv.qtype, 1298 uv.getBounds(ib1), 1299 uv.getBounds(ib2)); 1300 } 1301 1302 /** 1303 * Helper method: reports an inference error. 1304 */ 1305 void reportInferenceError(String key, Object... args) { 1306 throw inferenceException.setMessage(key, args); 1307 } 1308 // </editor-fold> 1309 1310 // <editor-fold defaultstate="collapsed" desc="Inference engine"> 1311 /** 1312 * Graph inference strategy - act as an input to the inference solver; a strategy is 1313 * composed of two ingredients: (i) find a node to solve in the inference graph, 1314 * and (ii) tell th engine when we are done fixing inference variables 1315 */ 1316 interface GraphStrategy { 1317 1318 /** 1319 * A NodeNotFoundException is thrown whenever an inference strategy fails 1320 * to pick the next node to solve in the inference graph. 1321 */ 1322 public static class NodeNotFoundException extends RuntimeException { 1323 private static final long serialVersionUID = 0; 1324 1325 InferenceGraph graph; 1326 1327 public NodeNotFoundException(InferenceGraph graph) { 1328 this.graph = graph; 1329 } 1330 } 1331 /** 1332 * Pick the next node (leaf) to solve in the graph 1333 */ 1334 Node pickNode(InferenceGraph g) throws NodeNotFoundException; 1335 /** 1336 * Is this the last step? 1337 */ 1338 boolean done(); 1339 } 1340 1341 /** 1342 * Simple solver strategy class that locates all leaves inside a graph 1343 * and picks the first leaf as the next node to solve 1344 */ 1345 abstract class LeafSolver implements GraphStrategy { 1346 public Node pickNode(InferenceGraph g) { 1347 if (g.nodes.isEmpty()) { 1348 //should not happen 1349 throw new NodeNotFoundException(g); 1350 } 1351 return g.nodes.get(0); 1352 } 1353 } 1354 1355 /** 1356 * This solver uses an heuristic to pick the best leaf - the heuristic 1357 * tries to select the node that has maximal probability to contain one 1358 * or more inference variables in a given list 1359 */ 1360 abstract class BestLeafSolver extends LeafSolver { 1361 1362 /** list of ivars of which at least one must be solved */ 1363 List<Type> varsToSolve; 1364 1365 BestLeafSolver(List<Type> varsToSolve) { 1366 this.varsToSolve = varsToSolve; 1367 } 1368 1369 /** 1370 * Computes a path that goes from a given node to the leafs in the graph. 1371 * Typically this will start from a node containing a variable in 1372 * {@code varsToSolve}. For any given path, the cost is computed as the total 1373 * number of type-variables that should be eagerly instantiated across that path. 1374 */ 1375 Pair<List<Node>, Integer> computeTreeToLeafs(Node n) { 1376 Pair<List<Node>, Integer> cachedPath = treeCache.get(n); 1377 if (cachedPath == null) { 1378 //cache miss 1379 if (n.isLeaf()) { 1380 //if leaf, stop 1381 cachedPath = new Pair<>(List.of(n), n.data.length()); 1382 } else { 1383 //if non-leaf, proceed recursively 1384 Pair<List<Node>, Integer> path = new Pair<>(List.of(n), n.data.length()); 1385 for (Node n2 : n.getAllDependencies()) { 1386 if (n2 == n) continue; 1387 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2); 1388 path = new Pair<>(path.fst.prependList(subpath.fst), 1389 path.snd + subpath.snd); 1390 } 1391 cachedPath = path; 1392 } 1393 //save results in cache 1394 treeCache.put(n, cachedPath); 1395 } 1396 return cachedPath; 1397 } 1398 1399 /** cache used to avoid redundant computation of tree costs */ 1400 final Map<Node, Pair<List<Node>, Integer>> treeCache = new HashMap<>(); 1401 1402 /** constant value used to mark non-existent paths */ 1403 final Pair<List<Node>, Integer> noPath = new Pair<>(null, Integer.MAX_VALUE); 1404 1405 /** 1406 * Pick the leaf that minimize cost 1407 */ 1408 @Override 1409 public Node pickNode(final InferenceGraph g) { 1410 treeCache.clear(); //graph changes at every step - cache must be cleared 1411 Pair<List<Node>, Integer> bestPath = noPath; 1412 for (Node n : g.nodes) { 1413 if (!Collections.disjoint(n.data, varsToSolve)) { 1414 Pair<List<Node>, Integer> path = computeTreeToLeafs(n); 1415 //discard all paths containing at least a node in the 1416 //closure computed above 1417 if (path.snd < bestPath.snd) { 1418 bestPath = path; 1419 } 1420 } 1421 } 1422 if (bestPath == noPath) { 1423 //no path leads there 1424 throw new NodeNotFoundException(g); 1425 } 1426 return bestPath.fst.head; 1427 } 1428 } 1429 1430 /** 1431 * The inference process can be thought of as a sequence of steps. Each step 1432 * instantiates an inference variable using a subset of the inference variable 1433 * bounds, if certain condition are met. Decisions such as the sequence in which 1434 * steps are applied, or which steps are to be applied are left to the inference engine. 1435 */ 1436 enum InferenceStep { 1437 1438 /** 1439 * Instantiate an inference variables using one of its (ground) equality 1440 * constraints 1441 */ 1442 EQ(InferenceBound.EQ) { 1443 @Override 1444 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1445 return filterBounds(uv, inferenceContext).head; 1446 } 1447 }, 1448 /** 1449 * Instantiate an inference variables using its (ground) lower bounds. Such 1450 * bounds are merged together using lub(). 1451 */ 1452 LOWER(InferenceBound.LOWER) { 1453 @Override 1454 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1455 Infer infer = inferenceContext.infer; 1456 List<Type> lobounds = filterBounds(uv, inferenceContext); 1457 //note: lobounds should have at least one element 1458 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds); 1459 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { 1460 throw infer.inferenceException 1461 .setMessage("no.unique.minimal.instance.exists", 1462 uv.qtype, lobounds); 1463 } else { 1464 return owntype; 1465 } 1466 } 1467 }, 1468 /** 1469 * Infer uninstantiated/unbound inference variables occurring in 'throws' 1470 * clause as RuntimeException 1471 */ 1472 THROWS(InferenceBound.UPPER) { 1473 @Override 1474 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1475 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) { 1476 //not a throws undet var 1477 return false; 1478 } 1479 Types types = inferenceContext.types; 1480 Symtab syms = inferenceContext.infer.syms; 1481 return t.getBounds(InferenceBound.UPPER).stream() 1482 .filter(b -> !inferenceContext.free(b)) 1483 .allMatch(u -> types.isSubtype(syms.runtimeExceptionType, u)); 1484 } 1485 1486 @Override 1487 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1488 return inferenceContext.infer.syms.runtimeExceptionType; 1489 } 1490 }, 1491 /** 1492 * Instantiate an inference variables using its (ground) upper bounds. Such 1493 * bounds are merged together using glb(). 1494 */ 1495 UPPER(InferenceBound.UPPER) { 1496 @Override 1497 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1498 Infer infer = inferenceContext.infer; 1499 List<Type> hibounds = filterBounds(uv, inferenceContext); 1500 //note: hibounds should have at least one element 1501 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds); 1502 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { 1503 throw infer.inferenceException 1504 .setMessage("no.unique.maximal.instance.exists", 1505 uv.qtype, hibounds); 1506 } else { 1507 return owntype; 1508 } 1509 } 1510 }, 1511 /** 1512 * Like the former; the only difference is that this step can only be applied 1513 * if all upper bounds are ground. 1514 */ 1515 UPPER_LEGACY(InferenceBound.UPPER) { 1516 @Override 1517 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1518 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured(); 1519 } 1520 1521 @Override 1522 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1523 return UPPER.solve(uv, inferenceContext); 1524 } 1525 }, 1526 /** 1527 * Like the former; the only difference is that this step can only be applied 1528 * if all upper/lower bounds are ground. 1529 */ 1530 CAPTURED(InferenceBound.UPPER) { 1531 @Override 1532 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1533 return t.isCaptured() && 1534 !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER)); 1535 } 1536 1537 @Override 1538 Type solve(UndetVar uv, InferenceContext inferenceContext) { 1539 Infer infer = inferenceContext.infer; 1540 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ? 1541 UPPER.solve(uv, inferenceContext) : 1542 infer.syms.objectType; 1543 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ? 1544 LOWER.solve(uv, inferenceContext) : 1545 infer.syms.botType; 1546 CapturedType prevCaptured = (CapturedType)uv.qtype; 1547 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, 1548 upper, lower, prevCaptured.wildcard); 1549 } 1550 }; 1551 1552 final InferenceBound ib; 1553 1554 InferenceStep(InferenceBound ib) { 1555 this.ib = ib; 1556 } 1557 1558 /** 1559 * Find an instantiated type for a given inference variable within 1560 * a given inference context 1561 */ 1562 abstract Type solve(UndetVar uv, InferenceContext inferenceContext); 1563 1564 /** 1565 * Can the inference variable be instantiated using this step? 1566 */ 1567 public boolean accepts(UndetVar t, InferenceContext inferenceContext) { 1568 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured(); 1569 } 1570 1571 /** 1572 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper) 1573 */ 1574 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) { 1575 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext)); 1576 } 1577 } 1578 1579 /** 1580 * This enumeration defines the sequence of steps to be applied when the 1581 * solver works in legacy mode. The steps in this enumeration reflect 1582 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). 1583 */ 1584 enum LegacyInferenceSteps { 1585 1586 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), 1587 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY)); 1588 1589 final EnumSet<InferenceStep> steps; 1590 1591 LegacyInferenceSteps(EnumSet<InferenceStep> steps) { 1592 this.steps = steps; 1593 } 1594 } 1595 1596 /** 1597 * This enumeration defines the sequence of steps to be applied when the 1598 * graph solver is used. This order is defined so as to maximize compatibility 1599 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). 1600 */ 1601 enum GraphInferenceSteps { 1602 1603 EQ(EnumSet.of(InferenceStep.EQ)), 1604 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), 1605 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED)); 1606 1607 final EnumSet<InferenceStep> steps; 1608 1609 GraphInferenceSteps(EnumSet<InferenceStep> steps) { 1610 this.steps = steps; 1611 } 1612 } 1613 1614 /** 1615 * There are two kinds of dependencies between inference variables. The basic 1616 * kind of dependency (or bound dependency) arises when a variable mention 1617 * another variable in one of its bounds. There's also a more subtle kind 1618 * of dependency that arises when a variable 'might' lead to better constraints 1619 * on another variable (this is typically the case with variables holding up 1620 * stuck expressions). 1621 */ 1622 enum DependencyKind implements GraphUtils.DependencyKind { 1623 1624 /** bound dependency */ 1625 BOUND("dotted"), 1626 /** stuck dependency */ 1627 STUCK("dashed"); 1628 1629 final String dotSyle; 1630 1631 private DependencyKind(String dotSyle) { 1632 this.dotSyle = dotSyle; 1633 } 1634 } 1635 1636 /** 1637 * This is the graph inference solver - the solver organizes all inference variables in 1638 * a given inference context by bound dependencies - in the general case, such dependencies 1639 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build 1640 * an acyclic graph, where all cyclic variables are bundled together. An inference 1641 * step corresponds to solving a node in the acyclic graph - this is done by 1642 * relying on a given strategy (see GraphStrategy). 1643 */ 1644 class GraphSolver { 1645 1646 InferenceContext inferenceContext; 1647 Warner warn; 1648 1649 GraphSolver(InferenceContext inferenceContext, Warner warn) { 1650 this.inferenceContext = inferenceContext; 1651 this.warn = warn; 1652 } 1653 1654 /** 1655 * Solve variables in a given inference context. The amount of variables 1656 * to be solved, and the way in which the underlying acyclic graph is explored 1657 * depends on the selected solver strategy. 1658 */ 1659 void solve(GraphStrategy sstrategy) { 1660 doIncorporation(inferenceContext, warn); //initial propagation of bounds 1661 InferenceGraph inferenceGraph = new InferenceGraph(); 1662 while (!sstrategy.done()) { 1663 if (dependenciesFolder != null) { 1664 //add this graph to the pending queue 1665 pendingGraphs = pendingGraphs.prepend(inferenceGraph.toDot()); 1666 } 1667 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph); 1668 List<Type> varsToSolve = List.from(nodeToSolve.data); 1669 List<Type> saved_undet = inferenceContext.save(); 1670 try { 1671 //repeat until all variables are solved 1672 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) { 1673 //for each inference phase 1674 for (GraphInferenceSteps step : GraphInferenceSteps.values()) { 1675 if (inferenceContext.solveBasic(varsToSolve, step.steps).nonEmpty()) { 1676 doIncorporation(inferenceContext, warn); 1677 continue outer; 1678 } 1679 } 1680 //no progress 1681 throw inferenceException.setMessage(); 1682 } 1683 } 1684 catch (InferenceException ex) { 1685 //did we fail because of interdependent ivars? 1686 inferenceContext.rollback(saved_undet); 1687 instantiateAsUninferredVars(varsToSolve, inferenceContext); 1688 doIncorporation(inferenceContext, warn); 1689 } 1690 inferenceGraph.deleteNode(nodeToSolve); 1691 } 1692 } 1693 1694 /** 1695 * The dependencies between the inference variables that need to be solved 1696 * form a (possibly cyclic) graph. This class reduces the original dependency graph 1697 * to an acyclic version, where cyclic nodes are folded into a single 'super node'. 1698 */ 1699 class InferenceGraph { 1700 1701 /** 1702 * This class represents a node in the graph. Each node corresponds 1703 * to an inference variable and has edges (dependencies) on other 1704 * nodes. The node defines an entry point that can be used to receive 1705 * updates on the structure of the graph this node belongs to (used to 1706 * keep dependencies in sync). 1707 */ 1708 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements DottableNode<ListBuffer<Type>, Node> { 1709 1710 /** node dependencies */ 1711 Set<Node> deps; 1712 1713 Node(Type ivar) { 1714 super(ListBuffer.of(ivar)); 1715 this.deps = new HashSet<>(); 1716 } 1717 1718 @Override 1719 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() { 1720 return new GraphUtils.DependencyKind[] { DependencyKind.BOUND }; 1721 } 1722 1723 public Iterable<? extends Node> getAllDependencies() { 1724 return deps; 1725 } 1726 1727 @Override 1728 public Collection<? extends Node> getDependenciesByKind(GraphUtils.DependencyKind dk) { 1729 if (dk == DependencyKind.BOUND) { 1730 return deps; 1731 } else { 1732 throw new IllegalStateException(); 1733 } 1734 } 1735 1736 /** 1737 * Adds dependency with given kind. 1738 */ 1739 protected void addDependency(Node depToAdd) { 1740 deps.add(depToAdd); 1741 } 1742 1743 /** 1744 * Add multiple dependencies of same given kind. 1745 */ 1746 protected void addDependencies(Set<Node> depsToAdd) { 1747 for (Node n : depsToAdd) { 1748 addDependency(n); 1749 } 1750 } 1751 1752 /** 1753 * Remove a dependency, regardless of its kind. 1754 */ 1755 protected boolean removeDependency(Node n) { 1756 return deps.remove(n); 1757 } 1758 1759 /** 1760 * Compute closure of a give node, by recursively walking 1761 * through all its dependencies (of given kinds) 1762 */ 1763 protected Set<Node> closure() { 1764 boolean progress = true; 1765 Set<Node> closure = new HashSet<>(); 1766 closure.add(this); 1767 while (progress) { 1768 progress = false; 1769 for (Node n1 : new HashSet<>(closure)) { 1770 progress = closure.addAll(n1.deps); 1771 } 1772 } 1773 return closure; 1774 } 1775 1776 /** 1777 * Is this node a leaf? This means either the node has no dependencies, 1778 * or it just has self-dependencies. 1779 */ 1780 protected boolean isLeaf() { 1781 //no deps, or only one self dep 1782 if (deps.isEmpty()) return true; 1783 for (Node n : deps) { 1784 if (n != this) { 1785 return false; 1786 } 1787 } 1788 return true; 1789 } 1790 1791 /** 1792 * Merge this node with another node, acquiring its dependencies. 1793 * This routine is used to merge all cyclic node together and 1794 * form an acyclic graph. 1795 */ 1796 protected void mergeWith(List<? extends Node> nodes) { 1797 for (Node n : nodes) { 1798 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!"); 1799 data.appendList(n.data); 1800 addDependencies(n.deps); 1801 } 1802 //update deps 1803 Set<Node> deps2 = new HashSet<>(); 1804 for (Node d : deps) { 1805 if (data.contains(d.data.first())) { 1806 deps2.add(this); 1807 } else { 1808 deps2.add(d); 1809 } 1810 } 1811 deps = deps2; 1812 } 1813 1814 /** 1815 * Notify all nodes that something has changed in the graph 1816 * topology. 1817 */ 1818 private void graphChanged(Node from, Node to) { 1819 if (removeDependency(from)) { 1820 if (to != null) { 1821 addDependency(to); 1822 } 1823 } 1824 } 1825 1826 @Override 1827 public Properties nodeAttributes() { 1828 Properties p = new Properties(); 1829 p.put("label", "\"" + toString() + "\""); 1830 return p; 1831 } 1832 1833 @Override 1834 public Properties dependencyAttributes(Node sink, GraphUtils.DependencyKind dk) { 1835 Properties p = new Properties(); 1836 p.put("style", ((DependencyKind)dk).dotSyle); 1837 StringBuilder buf = new StringBuilder(); 1838 String sep = ""; 1839 for (Type from : data) { 1840 UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from); 1841 for (Type bound : uv.getBounds(InferenceBound.values())) { 1842 if (bound.containsAny(List.from(sink.data))) { 1843 buf.append(sep); 1844 buf.append(bound); 1845 sep = ","; 1846 } 1847 } 1848 } 1849 p.put("label", "\"" + buf.toString() + "\""); 1850 return p; 1851 } 1852 } 1853 1854 /** the nodes in the inference graph */ 1855 ArrayList<Node> nodes; 1856 1857 InferenceGraph() { 1858 initNodes(); 1859 } 1860 1861 /** 1862 * Basic lookup helper for retrieving a graph node given an inference 1863 * variable type. 1864 */ 1865 public Node findNode(Type t) { 1866 for (Node n : nodes) { 1867 if (n.data.contains(t)) { 1868 return n; 1869 } 1870 } 1871 return null; 1872 } 1873 1874 /** 1875 * Delete a node from the graph. This update the underlying structure 1876 * of the graph (including dependencies) via listeners updates. 1877 */ 1878 public void deleteNode(Node n) { 1879 Assert.check(nodes.contains(n)); 1880 nodes.remove(n); 1881 notifyUpdate(n, null); 1882 } 1883 1884 /** 1885 * Notify all nodes of a change in the graph. If the target node is 1886 * {@code null} the source node is assumed to be removed. 1887 */ 1888 void notifyUpdate(Node from, Node to) { 1889 for (Node n : nodes) { 1890 n.graphChanged(from, to); 1891 } 1892 } 1893 1894 /** 1895 * Create the graph nodes. First a simple node is created for every inference 1896 * variables to be solved. Then Tarjan is used to found all connected components 1897 * in the graph. For each component containing more than one node, a super node is 1898 * created, effectively replacing the original cyclic nodes. 1899 */ 1900 void initNodes() { 1901 //add nodes 1902 nodes = new ArrayList<>(); 1903 for (Type t : inferenceContext.restvars()) { 1904 nodes.add(new Node(t)); 1905 } 1906 //add dependencies 1907 for (Node n_i : nodes) { 1908 Type i = n_i.data.first(); 1909 for (Node n_j : nodes) { 1910 Type j = n_j.data.first(); 1911 UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i); 1912 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) { 1913 //update i's bound dependencies 1914 n_i.addDependency(n_j); 1915 } 1916 } 1917 } 1918 //merge cyclic nodes 1919 ArrayList<Node> acyclicNodes = new ArrayList<>(); 1920 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { 1921 if (conSubGraph.length() > 1) { 1922 Node root = conSubGraph.head; 1923 root.mergeWith(conSubGraph.tail); 1924 for (Node n : conSubGraph) { 1925 notifyUpdate(n, root); 1926 } 1927 } 1928 acyclicNodes.add(conSubGraph.head); 1929 } 1930 nodes = acyclicNodes; 1931 } 1932 1933 /** 1934 * Debugging: dot representation of this graph 1935 */ 1936 String toDot() { 1937 StringBuilder buf = new StringBuilder(); 1938 for (Type t : inferenceContext.undetvars) { 1939 UndetVar uv = (UndetVar)t; 1940 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n", 1941 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER), 1942 uv.getBounds(InferenceBound.EQ))); 1943 } 1944 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString()); 1945 } 1946 } 1947 } 1948 // </editor-fold> 1949 1950 // <editor-fold defaultstate="collapsed" desc="Inference context"> 1951 /** 1952 * Functional interface for defining inference callbacks. Certain actions 1953 * (i.e. subtyping checks) might need to be redone after all inference variables 1954 * have been fixed. 1955 */ 1956 interface FreeTypeListener { 1957 void typesInferred(InferenceContext inferenceContext); 1958 } 1959 1960 final InferenceContext emptyContext; 1961 // </editor-fold> 1962} 1963