1 /*

     2  * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package com.sun.tools.javac.comp;

    27 

    28 import java.util.EnumSet;

    29 import java.util.HashMap;

    30 import java.util.Map;

    31 import java.util.Set;

    32 

    33 import com.sun.tools.javac.code.Symtab;

    34 import com.sun.tools.javac.code.Type;

    35 import com.sun.tools.javac.code.Type.CapturedType;

    36 import com.sun.tools.javac.code.Type.CapturedUndetVar;

    37 import com.sun.tools.javac.code.Type.TypeMapping;

    38 import com.sun.tools.javac.code.Type.TypeVar;

    39 import com.sun.tools.javac.code.Type.UndetVar;

    40 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;

    41 import com.sun.tools.javac.code.Types;

    42 import com.sun.tools.javac.comp.Infer.BestLeafSolver;

    43 import com.sun.tools.javac.comp.Infer.FreeTypeListener;

    44 import com.sun.tools.javac.comp.Infer.GraphSolver;

    45 import com.sun.tools.javac.comp.Infer.GraphStrategy;

    46 import com.sun.tools.javac.comp.Infer.InferenceException;

    47 import com.sun.tools.javac.comp.Infer.InferenceStep;

    48 import com.sun.tools.javac.comp.Infer.LeafSolver;

    49 import com.sun.tools.javac.tree.JCTree;

    50 import com.sun.tools.javac.tree.TreeMaker;

    51 import com.sun.tools.javac.util.Assert;

    52 import com.sun.tools.javac.util.Context;

    53 import com.sun.tools.javac.util.Filter;

    54 import com.sun.tools.javac.util.JCDiagnostic;

    55 import com.sun.tools.javac.util.JCDiagnostic.Factory;

    56 import com.sun.tools.javac.util.List;

    57 import com.sun.tools.javac.util.ListBuffer;

    58 import com.sun.tools.javac.util.Log;

    59 import com.sun.tools.javac.util.Warner;

    60 

    61 /**

    62  * An inference context keeps track of the set of variables that are free

    63  * in the current context. It provides utility methods for opening/closing

    64  * types to their corresponding free/closed forms. It also provide hooks for

    65  * attaching deferred post-inference action (see PendingCheck). Finally,

    66  * it can be used as an entry point for performing upper/lower bound inference

    67  * (see InferenceKind).

    68  *

    69  * <p><b>This is NOT part of any supported API.

    70  * If you write code that depends on this, you do so at your own risk.

    71  * This code and its internal interfaces are subject to change or

    72  * deletion without notice.</b>

    73  */

    74 class InferenceContext {

    75 

    76     /** list of inference vars as undet vars */

    77     List<Type> undetvars;

    78 

    79     /** list of inference vars in this context */

    80     List<Type> inferencevars;

    81 

    82     Map<FreeTypeListener, List<Type>> freeTypeListeners = new HashMap<>();

    83 

    84     List<FreeTypeListener> freetypeListeners = List.nil();

    85 

    86     Types types;

    87     Infer infer;

    88 

    89     public InferenceContext(Infer infer, List<Type> inferencevars) {

    90         this.inferencevars = inferencevars;

    91 

    92         this.infer = infer;

    93         this.types = infer.types;

    94 

    95         fromTypeVarFun = new TypeMapping<Void>() {

    96             @Override

    97             public Type visitTypeVar(TypeVar tv, Void aVoid) {

    98                 return new UndetVar(tv, types);

    99             }

   100 

   101             @Override

   102             public Type visitCapturedType(CapturedType t, Void aVoid) {

   103                 return new CapturedUndetVar(t, types);

   104             }

   105         };

   106         this.undetvars = inferencevars.map(fromTypeVarFun);

   107     }

   108 

   109     TypeMapping<Void> fromTypeVarFun;

   110 

   111     /**

   112      * add a new inference var to this inference context

   113      */

   114     void addVar(TypeVar t) {

   115         this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));

   116         this.inferencevars = this.inferencevars.prepend(t);

   117     }

   118 

   119     /**

   120      * returns the list of free variables (as type-variables) in this

   121      * inference context

   122      */

   123     List<Type> inferenceVars() {

   124         return inferencevars;

   125     }

   126 

   127     /**

   128      * returns the list of uninstantiated variables (as type-variables) in this

   129      * inference context

   130      */

   131     List<Type> restvars() {

   132         return filterVars(new Filter<UndetVar>() {

   133             public boolean accepts(UndetVar uv) {

   134                 return uv.inst == null;

   135             }

   136         });

   137     }

   138 

   139     /**

   140      * returns the list of instantiated variables (as type-variables) in this

   141      * inference context

   142      */

   143     List<Type> instvars() {

   144         return filterVars(new Filter<UndetVar>() {

   145             public boolean accepts(UndetVar uv) {

   146                 return uv.inst != null;

   147             }

   148         });

   149     }

   150 

   151     /**

   152      * Get list of bounded inference variables (where bound is other than

   153      * declared bounds).

   154      */

   155     final List<Type> boundedVars() {

   156         return filterVars(new Filter<UndetVar>() {

   157             public boolean accepts(UndetVar uv) {

   158                 return uv.getBounds(InferenceBound.UPPER)

   159                          .diff(uv.getDeclaredBounds())

   160                          .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();

   161             }

   162         });

   163     }

   164 

   165     /* Returns the corresponding inference variables.

   166      */

   167     private List<Type> filterVars(Filter<UndetVar> fu) {

   168         ListBuffer<Type> res = new ListBuffer<>();

   169         for (Type t : undetvars) {

   170             UndetVar uv = (UndetVar)t;

   171             if (fu.accepts(uv)) {

   172                 res.append(uv.qtype);

   173             }

   174         }

   175         return res.toList();

   176     }

   177 

   178     /**

   179      * is this type free?

   180      */

   181     final boolean free(Type t) {

   182         return t.containsAny(inferencevars);

   183     }

   184 

   185     final boolean free(List<Type> ts) {

   186         for (Type t : ts) {

   187             if (free(t)) return true;

   188         }

   189         return false;

   190     }

   191 

   192     /**

   193      * Returns a list of free variables in a given type

   194      */

   195     final List<Type> freeVarsIn(Type t) {

   196         ListBuffer<Type> buf = new ListBuffer<>();

   197         for (Type iv : inferenceVars()) {

   198             if (t.contains(iv)) {

   199                 buf.add(iv);

   200             }

   201         }

   202         return buf.toList();

   203     }

   204 

   205     final List<Type> freeVarsIn(List<Type> ts) {

   206         ListBuffer<Type> buf = new ListBuffer<>();

   207         for (Type t : ts) {

   208             buf.appendList(freeVarsIn(t));

   209         }

   210         ListBuffer<Type> buf2 = new ListBuffer<>();

   211         for (Type t : buf) {

   212             if (!buf2.contains(t)) {

   213                 buf2.add(t);

   214             }

   215         }

   216         return buf2.toList();

   217     }

   218 

   219     /**

   220      * Replace all free variables in a given type with corresponding

   221      * undet vars (used ahead of subtyping/compatibility checks to allow propagation

   222      * of inference constraints).

   223      */

   224     final Type asUndetVar(Type t) {

   225         return types.subst(t, inferencevars, undetvars);

   226     }

   227 

   228     final List<Type> asUndetVars(List<Type> ts) {

   229         ListBuffer<Type> buf = new ListBuffer<>();

   230         for (Type t : ts) {

   231             buf.append(asUndetVar(t));

   232         }

   233         return buf.toList();

   234     }

   235 

   236     List<Type> instTypes() {

   237         ListBuffer<Type> buf = new ListBuffer<>();

   238         for (Type t : undetvars) {

   239             UndetVar uv = (UndetVar)t;

   240             buf.append(uv.inst != null ? uv.inst : uv.qtype);

   241         }

   242         return buf.toList();

   243     }

   244 

   245     /**

   246      * Replace all free variables in a given type with corresponding

   247      * instantiated types - if one or more free variable has not been

   248      * fully instantiated, it will still be available in the resulting type.

   249      */

   250     Type asInstType(Type t) {

   251         return types.subst(t, inferencevars, instTypes());

   252     }

   253 

   254     List<Type> asInstTypes(List<Type> ts) {

   255         ListBuffer<Type> buf = new ListBuffer<>();

   256         for (Type t : ts) {

   257             buf.append(asInstType(t));

   258         }

   259         return buf.toList();

   260     }

   261 

   262     /**

   263      * Add custom hook for performing post-inference action

   264      */

   265     void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {

   266         freeTypeListeners.put(ftl, freeVarsIn(types));

   267     }

   268 

   269     /**

   270      * Mark the inference context as complete and trigger evaluation

   271      * of all deferred checks.

   272      */

   273     void notifyChange() {

   274         notifyChange(inferencevars.diff(restvars()));

   275     }

   276 

   277     void notifyChange(List<Type> inferredVars) {

   278         InferenceException thrownEx = null;

   279         for (Map.Entry<FreeTypeListener, List<Type>> entry :

   280                 new HashMap<>(freeTypeListeners).entrySet()) {

   281             if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {

   282                 try {

   283                     entry.getKey().typesInferred(this);

   284                     freeTypeListeners.remove(entry.getKey());

   285                 } catch (InferenceException ex) {

   286                     if (thrownEx == null) {

   287                         thrownEx = ex;

   288                     }

   289                 }

   290             }

   291         }

   292         //inference exception multiplexing - present any inference exception

   293         //thrown when processing listeners as a single one

   294         if (thrownEx != null) {

   295             throw thrownEx;

   296         }

   297     }

   298 

   299     /**

   300      * Save the state of this inference context

   301      */

   302     List<Type> save() {

   303         ListBuffer<Type> buf = new ListBuffer<>();

   304         for (Type t : undetvars) {

   305             UndetVar uv = (UndetVar)t;

   306             UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);

   307             for (InferenceBound ib : InferenceBound.values()) {

   308                 for (Type b : uv.getBounds(ib)) {

   309                     uv2.addBound(ib, b, types);

   310                 }

   311             }

   312             uv2.inst = uv.inst;

   313             buf.add(uv2);

   314         }

   315         return buf.toList();

   316     }

   317 

   318     /**

   319      * Restore the state of this inference context to the previous known checkpoint

   320      */

   321     void rollback(List<Type> saved_undet) {

   322          Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());

   323         //restore bounds (note: we need to preserve the old instances)

   324         for (Type t : undetvars) {

   325             UndetVar uv = (UndetVar)t;

   326             UndetVar uv_saved = (UndetVar)saved_undet.head;

   327             for (InferenceBound ib : InferenceBound.values()) {

   328                 uv.setBounds(ib, uv_saved.getBounds(ib));

   329             }

   330             uv.inst = uv_saved.inst;

   331             saved_undet = saved_undet.tail;

   332         }

   333     }

   334 

   335     /**

   336      * Copy variable in this inference context to the given context

   337      */

   338     void dupTo(final InferenceContext that) {

   339         that.inferencevars = that.inferencevars.appendList(

   340                 inferencevars.diff(that.inferencevars));

   341         that.undetvars = that.undetvars.appendList(

   342                 undetvars.diff(that.undetvars));

   343         //set up listeners to notify original inference contexts as

   344         //propagated vars are inferred in new context

   345         for (Type t : inferencevars) {

   346             that.freeTypeListeners.put(new FreeTypeListener() {

   347                 public void typesInferred(InferenceContext inferenceContext) {

   348                     InferenceContext.this.notifyChange();

   349                 }

   350             }, List.of(t));

   351         }

   352     }

   353 

   354     private void solve(GraphStrategy ss, Warner warn) {

   355         solve(ss, new HashMap<Type, Set<Type>>(), warn);

   356     }

   357 

   358     /**

   359      * Solve with given graph strategy.

   360      */

   361     private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) {

   362         GraphSolver s = infer.new GraphSolver(this, stuckDeps, warn);

   363         s.solve(ss);

   364     }

   365 

   366     /**

   367      * Solve all variables in this context.

   368      */

   369     public void solve(Warner warn) {

   370         solve(infer.new LeafSolver() {

   371             public boolean done() {

   372                 return restvars().isEmpty();

   373             }

   374         }, warn);

   375     }

   376 

   377     /**

   378      * Solve all variables in the given list.

   379      */

   380     public void solve(final List<Type> vars, Warner warn) {

   381         solve(infer.new BestLeafSolver(vars) {

   382             public boolean done() {

   383                 return !free(asInstTypes(vars));

   384             }

   385         }, warn);

   386     }

   387 

   388     /**

   389      * Solve at least one variable in given list.

   390      */

   391     public void solveAny(List<Type> varsToSolve, Map<Type, Set<Type>> optDeps, Warner warn) {

   392         solve(infer.new BestLeafSolver(varsToSolve.intersect(restvars())) {

   393             public boolean done() {

   394                 return instvars().intersect(varsToSolve).nonEmpty();

   395             }

   396         }, optDeps, warn);

   397     }

   398 

   399     /**

   400      * Apply a set of inference steps

   401      */

   402     private boolean solveBasic(EnumSet<InferenceStep> steps) {

   403         return solveBasic(inferencevars, steps);

   404     }

   405 

   406     boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {

   407         boolean changed = false;

   408         for (Type t : varsToSolve.intersect(restvars())) {

   409             UndetVar uv = (UndetVar)asUndetVar(t);

   410             for (InferenceStep step : steps) {

   411                 if (step.accepts(uv, this)) {

   412                     uv.inst = step.solve(uv, this);

   413                     changed = true;

   414                     break;

   415                 }

   416             }

   417         }

   418         return changed;

   419     }

   420 

   421     /**

   422      * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).

   423      * During overload resolution, instantiation is done by doing a partial

   424      * inference process using eq/lower bound instantiation. During check,

   425      * we also instantiate any remaining vars by repeatedly using eq/upper

   426      * instantiation, until all variables are solved.

   427      */

   428     public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {

   429         while (true) {

   430             boolean stuck = !solveBasic(steps);

   431             if (restvars().isEmpty() || partial) {

   432                 //all variables have been instantiated - exit

   433                 break;

   434             } else if (stuck) {

   435                 //some variables could not be instantiated because of cycles in

   436                 //upper bounds - provide a (possibly recursive) default instantiation

   437                 infer.instantiateAsUninferredVars(restvars(), this);

   438                 break;

   439             } else {

   440                 //some variables have been instantiated - replace newly instantiated

   441                 //variables in remaining upper bounds and continue

   442                 for (Type t : undetvars) {

   443                     UndetVar uv = (UndetVar)t;

   444                     uv.substBounds(inferenceVars(), instTypes(), types);

   445                 }

   446             }

   447         }

   448         infer.checkWithinBounds(this, warn);

   449     }

   450 

   451     @Override

   452     public String toString() {

   453         return "Inference vars: " + inferencevars + '\n' +

   454                "Undet vars: " + undetvars;

   455     }

   456 

   457     /* Method Types.capture() generates a new type every time it's applied

   458      * to a wildcard parameterized type. This is intended functionality but

   459      * there are some cases when what you need is not to generate a new

   460      * captured type but to check that a previously generated captured type

   461      * is correct. There are cases when caching a captured type for later

   462      * reuse is sound. In general two captures from the same AST are equal.

   463      * This is why the tree is used as the key of the map below. This map

   464      * stores a Type per AST.

   465      */

   466     Map<JCTree, Type> captureTypeCache = new HashMap<>();

   467 

   468     Type cachedCapture(JCTree tree, Type t, boolean readOnly) {

   469         Type captured = captureTypeCache.get(tree);

   470         if (captured != null) {

   471             return captured;

   472         }

   473 

   474         Type result = types.capture(t);

   475         if (result != t && !readOnly) { // then t is a wildcard parameterized type

   476             captureTypeCache.put(tree, result);

   477         }

   478         return result;

   479     }

   480 }