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