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