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