langtools/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/InferenceContext.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 package com.sun.tools.javac.comp;

 import java.util.Collections;
 import java.util.EnumSet;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.Map;
 import java.util.Set;

 import com.sun.tools.javac.code.Type;
 import com.sun.tools.javac.code.Type.ArrayType;
 import com.sun.tools.javac.code.Type.ClassType;
 import com.sun.tools.javac.code.Type.TypeVar;
 import com.sun.tools.javac.code.Type.UndetVar;
 import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
 import com.sun.tools.javac.code.Type.WildcardType;
 import com.sun.tools.javac.code.TypeTag;
 import com.sun.tools.javac.code.Types;
 import com.sun.tools.javac.comp.Infer.FreeTypeListener;
 import com.sun.tools.javac.comp.Infer.GraphSolver;
 import com.sun.tools.javac.comp.Infer.GraphStrategy;
 import com.sun.tools.javac.comp.Infer.InferenceException;
 import com.sun.tools.javac.comp.Infer.InferenceStep;
 import com.sun.tools.javac.tree.JCTree;
 import com.sun.tools.javac.util.Assert;
 import com.sun.tools.javac.util.Filter;
 import com.sun.tools.javac.util.List;
 import com.sun.tools.javac.util.ListBuffer;
 import com.sun.tools.javac.util.Warner;

 /**
  * An inference context keeps track of the set of variables that are free
  * in the current context. It provides utility methods for opening/closing
  * types to their corresponding free/closed forms. It also provide hooks for
  * attaching deferred post-inference action (see PendingCheck). Finally,
  * it can be used as an entry point for performing upper/lower bound inference
  * (see InferenceKind).
  *
  * <p><b>This is NOT part of any supported API.
  * If you write code that depends on this, you do so at your own risk.
  * This code and its internal interfaces are subject to change or
  * deletion without notice.</b>
  */
 public class InferenceContext {

     /** list of inference vars as undet vars */
     List<Type> undetvars;

     Type update(Type t) {
         return t;
     }

     /** list of inference vars in this context */
     List<Type> inferencevars;

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

     Types types;
     Infer infer;

     public InferenceContext(Infer infer, List<Type> inferencevars) {
         this(infer, inferencevars, inferencevars.map(infer.fromTypeVarFun));
     }

     public InferenceContext(Infer infer, List<Type> inferencevars, List<Type> undetvars) {
         this.inferencevars = inferencevars;
         this.undetvars = undetvars;
         this.infer = infer;
         this.types = infer.types;
     }

     /**
      * add a new inference var to this inference context
      */
     void addVar(TypeVar t) {
         this.undetvars = this.undetvars.prepend(infer.fromTypeVarFun.apply(t));
         this.inferencevars = this.inferencevars.prepend(t);
     }

     /**
      * returns the list of free variables (as type-variables) in this
      * inference context
      */
     List<Type> inferenceVars() {
         return inferencevars;
     }

     /**
      * returns the list of undetermined variables in this inference context
      */
     public List<Type> undetVars() {
         return undetvars;
     }

     /**
      * returns the list of uninstantiated variables (as type-variables) in this
      * inference context
      */
     List<Type> restvars() {
         return filterVars(uv -> uv.getInst() == null);
     }

     /**
      * returns the list of instantiated variables (as type-variables) in this
      * inference context
      */
     List<Type> instvars() {
         return filterVars(uv -> uv.getInst() != null);
     }

     /**
      * Get list of bounded inference variables (where bound is other than
      * declared bounds).
      */
     final List<Type> boundedVars() {
         return filterVars(uv -> uv.getBounds(InferenceBound.UPPER)
                  .diff(uv.getDeclaredBounds())
                  .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty());
     }

     /* Returns the corresponding inference variables.
      */
     private List<Type> filterVars(Filter<UndetVar> fu) {
         ListBuffer<Type> res = new ListBuffer<>();
         for (Type t : undetvars) {
             UndetVar uv = (UndetVar)t;
             if (fu.accepts(uv)) {
                 res.append(uv.qtype);
             }
         }
         return res.toList();
     }

     /**
      * is this type free?
      */
     final boolean free(Type t) {
         return t.containsAny(inferencevars);
     }

     final boolean free(List<Type> ts) {
         for (Type t : ts) {
             if (free(t)) return true;
         }
         return false;
     }

     /**
      * Returns a list of free variables in a given type
      */
     final List<Type> freeVarsIn(Type t) {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type iv : inferenceVars()) {
             if (t.contains(iv)) {
                 buf.add(iv);
             }
         }
         return buf.toList();
     }

     final List<Type> freeVarsIn(List<Type> ts) {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type t : ts) {
             buf.appendList(freeVarsIn(t));
         }
         ListBuffer<Type> buf2 = new ListBuffer<>();
         for (Type t : buf) {
             if (!buf2.contains(t)) {
                 buf2.add(t);
             }
         }
         return buf2.toList();
     }

     /**
      * Replace all free variables in a given type with corresponding
      * undet vars (used ahead of subtyping/compatibility checks to allow propagation
      * of inference constraints).
      */
     public final Type asUndetVar(Type t) {
         return types.subst(t, inferencevars, undetvars);
     }

     final List<Type> asUndetVars(List<Type> ts) {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type t : ts) {
             buf.append(asUndetVar(t));
         }
         return buf.toList();
     }

     List<Type> instTypes() {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type t : undetvars) {
             UndetVar uv = (UndetVar)t;
             buf.append(uv.getInst() != null ? uv.getInst() : uv.qtype);
         }
         return buf.toList();
     }

     /**
      * Replace all free variables in a given type with corresponding
      * instantiated types - if one or more free variable has not been
      * fully instantiated, it will still be available in the resulting type.
      */
     Type asInstType(Type t) {
         return types.subst(t, inferencevars, instTypes());
     }

     List<Type> asInstTypes(List<Type> ts) {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type t : ts) {
             buf.append(asInstType(t));
         }
         return buf.toList();
     }

     /**
      * Add custom hook for performing post-inference action
      */
     void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
         freeTypeListeners.put(ftl, freeVarsIn(types));
     }

     /**
      * Mark the inference context as complete and trigger evaluation
      * of all deferred checks.
      */
     void notifyChange() {
         notifyChange(inferencevars.diff(restvars()));
     }

     void notifyChange(List<Type> inferredVars) {
         InferenceException thrownEx = null;
         for (Map.Entry<FreeTypeListener, List<Type>> entry :
                 new LinkedHashMap<>(freeTypeListeners).entrySet()) {
             if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
                 try {
                     entry.getKey().typesInferred(this);
                     freeTypeListeners.remove(entry.getKey());
                 } catch (InferenceException ex) {
                     if (thrownEx == null) {
                         thrownEx = ex;
                     }
                 }
             }
         }
         //inference exception multiplexing - present any inference exception
         //thrown when processing listeners as a single one
         if (thrownEx != null) {
             throw thrownEx;
         }
     }

     /**
      * Save the state of this inference context
      */
     public List<Type> save() {
         ListBuffer<Type> buf = new ListBuffer<>();
         for (Type t : undetvars) {
             buf.add(((UndetVar)t).dup(infer.types));
         }
         return buf.toList();
     }

     /** Restore the state of this inference context to the previous known checkpoint.
     *  Consider that the number of saved undetermined variables can be different to the current
     *  amount. This is because new captured variables could have been added.
     */
     public void rollback(List<Type> saved_undet) {
         Assert.check(saved_undet != null);
         //restore bounds (note: we need to preserve the old instances)
         ListBuffer<Type> newUndetVars = new ListBuffer<>();
         ListBuffer<Type> newInferenceVars = new ListBuffer<>();
         while (saved_undet.nonEmpty() && undetvars.nonEmpty()) {
             UndetVar uv = (UndetVar)undetvars.head;
             UndetVar uv_saved = (UndetVar)saved_undet.head;
             if (uv.qtype == uv_saved.qtype) {
                 uv_saved.dupTo(uv, types);
                 undetvars = undetvars.tail;
                 saved_undet = saved_undet.tail;
                 newUndetVars.add(uv);
                 newInferenceVars.add(uv.qtype);
             } else {
                 undetvars = undetvars.tail;
             }
         }
         undetvars = newUndetVars.toList();
         inferencevars = newInferenceVars.toList();
     }

     /**
      * Copy variable in this inference context to the given context
      */
     void dupTo(final InferenceContext that) {
         dupTo(that, false);
     }

     void dupTo(final InferenceContext that, boolean clone) {
         that.inferencevars = that.inferencevars.appendList(inferencevars.diff(that.inferencevars));
         List<Type> undetsToPropagate = clone ? save() : undetvars;
         that.undetvars = that.undetvars.appendList(undetsToPropagate.diff(that.undetvars)); //propagate cloned undet!!
         //set up listeners to notify original inference contexts as
         //propagated vars are inferred in new context
         for (Type t : inferencevars) {
             that.freeTypeListeners.put(inferenceContext -> InferenceContext.this.notifyChange(), List.of(t));
         }
     }

     InferenceContext min(List<Type> roots, boolean shouldSolve, Warner warn) {
         ReachabilityVisitor rv = new ReachabilityVisitor();
         rv.scan(roots);
         if (rv.min.size() == inferencevars.length()) {
             return this;
         }

         List<Type> minVars = List.from(rv.min);
         List<Type> redundantVars = inferencevars.diff(minVars);

         //compute new undet variables (bounds associated to redundant variables are dropped)
         ListBuffer<Type> minUndetVars = new ListBuffer<>();
         for (Type minVar : minVars) {
             UndetVar uv = (UndetVar)asUndetVar(minVar);
             Assert.check(uv.incorporationActions.size() == 0);
             UndetVar uv2 = new UndetVar((TypeVar)minVar, infer.incorporationEngine(), types);
             for (InferenceBound ib : InferenceBound.values()) {
                 List<Type> newBounds = uv.getBounds(ib).stream()
                         .filter(b -> !redundantVars.contains(b))
                         .collect(List.collector());
                 uv2.setBounds(ib, newBounds);
             }
             minUndetVars.add(uv2);
         }

         //compute new minimal inference context
         InferenceContext minContext = new InferenceContext(infer, minVars, minUndetVars.toList());
         for (Type t : minContext.inferencevars) {
             //add listener that forwards notifications to original context
             minContext.addFreeTypeListener(List.of(t), (inferenceContext) -> {
                     List<Type> depVars = List.from(rv.minMap.get(t));
                     solve(depVars, warn);
                     notifyChange();
             });
         }
         if (shouldSolve) {
             //solve definitively unreachable variables
             List<Type> unreachableVars = redundantVars.diff(List.from(rv.equiv));
             solve(unreachableVars, warn);
         }
         return minContext;
     }

     class ReachabilityVisitor extends Types.UnaryVisitor<Void> {

         Set<Type> equiv = new HashSet<>();
         Set<Type> min = new HashSet<>();
         Map<Type, Set<Type>> minMap = new HashMap<>();

         void scan(List<Type> roots) {
             roots.stream().forEach(this::visit);
         }

         @Override
         public Void visitType(Type t, Void _unused) {
             return null;
         }

         @Override
         public Void visitUndetVar(UndetVar t, Void _unused) {
             if (min.add(t.qtype)) {
                 Set<Type> deps = minMap.getOrDefault(t.qtype, new HashSet<>(Collections.singleton(t.qtype)));
                 for (InferenceBound boundKind : InferenceBound.values()) {
                     for (Type b : t.getBounds(boundKind)) {
                         Type undet = asUndetVar(b);
                         if (!undet.hasTag(TypeTag.UNDETVAR)) {
                             visit(undet);
                         } else if (isEquiv(t, b, boundKind)) {
                             deps.add(b);
                             equiv.add(b);
                         } else {
                             visit(undet);
                         }
                     }
                 }
                 minMap.put(t.qtype, deps);
             }
             return null;
         }

         @Override
         public Void visitWildcardType(WildcardType t, Void _unused) {
             return visit(t.type);
         }

         @Override
         public Void visitTypeVar(TypeVar t, Void aVoid) {
             Type undet = asUndetVar(t);
             if (undet.hasTag(TypeTag.UNDETVAR)) {
                 visitUndetVar((UndetVar)undet, null);
             }
             return null;
         }

         @Override
         public Void visitArrayType(ArrayType t, Void _unused) {
             return visit(t.elemtype);
         }

         @Override
         public Void visitClassType(ClassType t, Void _unused) {
             visit(t.getEnclosingType());
             for (Type targ : t.getTypeArguments()) {
                 visit(targ);
             }
             return null;
         }

         boolean isEquiv(UndetVar from, Type t, InferenceBound boundKind) {
             UndetVar uv = (UndetVar)asUndetVar(t);
             for (InferenceBound ib : InferenceBound.values()) {
                 List<Type> b1 = from.getBounds(ib);
                 if (ib == boundKind) {
                     b1 = b1.diff(List.of(t));
                 }
                 List<Type> b2 = uv.getBounds(ib);
                 if (ib == boundKind.complement()) {
                     b2 = b2.diff(List.of(from.qtype));
                 }
                 if (!b1.containsAll(b2) || !b2.containsAll(b1)) {
                     return false;
                 }
             }
             return true;
         }
     }

     /**
      * Solve with given graph strategy.
      */
     private void solve(GraphStrategy ss, Warner warn) {
         GraphSolver s = infer.new GraphSolver(this, warn);
         s.solve(ss);
     }

     /**
      * Solve all variables in this context.
      */
     public void solve(Warner warn) {
         solve(infer.new LeafSolver() {
             public boolean done() {
                 return restvars().isEmpty();
             }
         }, warn);
     }

     /**
      * Solve all variables in the given list.
      */
     public void solve(final List<Type> vars, Warner warn) {
         solve(infer.new BestLeafSolver(vars) {
             public boolean done() {
                 return !free(asInstTypes(vars));
             }
         }, warn);
     }

     /**
      * Solve at least one variable in given list.
      */
     public void solveAny(List<Type> varsToSolve, Warner warn) {
         solve(infer.new BestLeafSolver(varsToSolve.intersect(restvars())) {
             public boolean done() {
                 return instvars().intersect(varsToSolve).nonEmpty();
             }
         }, warn);
     }

     /**
      * Apply a set of inference steps
      */
     private List<Type> solveBasic(EnumSet<InferenceStep> steps) {
         return solveBasic(inferencevars, steps);
     }

     List<Type> solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
         ListBuffer<Type> solvedVars = new ListBuffer<>();
         for (Type t : varsToSolve.intersect(restvars())) {
             UndetVar uv = (UndetVar)asUndetVar(t);
             for (InferenceStep step : steps) {
                 if (step.accepts(uv, this)) {
                     uv.setInst(step.solve(uv, this));
                     solvedVars.add(uv.qtype);
                     break;
                 }
             }
         }
         return solvedVars.toList();
     }

     /**
      * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
      * During overload resolution, instantiation is done by doing a partial
      * inference process using eq/lower bound instantiation. During check,
      * we also instantiate any remaining vars by repeatedly using eq/upper
      * instantiation, until all variables are solved.
      */
     public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
         while (true) {
             List<Type> solvedVars = solveBasic(steps);
             if (restvars().isEmpty() || partial) {
                 //all variables have been instantiated - exit
                 break;
             } else if (solvedVars.isEmpty()) {
                 //some variables could not be instantiated because of cycles in
                 //upper bounds - provide a (possibly recursive) default instantiation
                 infer.instantiateAsUninferredVars(restvars(), this);
                 break;
             } else {
                 //some variables have been instantiated - replace newly instantiated
                 //variables in remaining upper bounds and continue
                 for (Type t : undetvars) {
                     UndetVar uv = (UndetVar)t;
                     uv.substBounds(solvedVars, asInstTypes(solvedVars), types);
                 }
             }
         }
         infer.doIncorporation(this, warn);
     }

     @Override
     public String toString() {
         return "Inference vars: " + inferencevars + '\n' +
                "Undet vars: " + undetvars;
     }

     /* Method Types.capture() generates a new type every time it's applied
      * to a wildcard parameterized type. This is intended functionality but
      * there are some cases when what you need is not to generate a new
      * captured type but to check that a previously generated captured type
      * is correct. There are cases when caching a captured type for later
      * reuse is sound. In general two captures from the same AST are equal.
      * This is why the tree is used as the key of the map below. This map
      * stores a Type per AST.
      */
     Map<JCTree, Type> captureTypeCache = new HashMap<>();

     Type cachedCapture(JCTree tree, Type t, boolean readOnly) {
         Type captured = captureTypeCache.get(tree);
         if (captured != null) {
             return captured;
         }

         Type result = types.capture(t);
         if (result != t && !readOnly) { // then t is a wildcard parameterized type
             captureTypeCache.put(tree, result);
         }
         return result;
     }
 }
	/*
	* Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package com.sun.tools.javac.comp;

	import java.util.Collections;
	import java.util.EnumSet;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.LinkedHashMap;
	import java.util.Map;
	import java.util.Set;

	import com.sun.tools.javac.code.Type;
	import com.sun.tools.javac.code.Type.ArrayType;
	import com.sun.tools.javac.code.Type.ClassType;
	import com.sun.tools.javac.code.Type.TypeVar;
	import com.sun.tools.javac.code.Type.UndetVar;
	import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
	import com.sun.tools.javac.code.Type.WildcardType;
	import com.sun.tools.javac.code.TypeTag;
	import com.sun.tools.javac.code.Types;
	import com.sun.tools.javac.comp.Infer.FreeTypeListener;
	import com.sun.tools.javac.comp.Infer.GraphSolver;
	import com.sun.tools.javac.comp.Infer.GraphStrategy;
	import com.sun.tools.javac.comp.Infer.InferenceException;
	import com.sun.tools.javac.comp.Infer.InferenceStep;
	import com.sun.tools.javac.tree.JCTree;
	import com.sun.tools.javac.util.Assert;
	import com.sun.tools.javac.util.Filter;
	import com.sun.tools.javac.util.List;
	import com.sun.tools.javac.util.ListBuffer;
	import com.sun.tools.javac.util.Warner;

	/**
	* An inference context keeps track of the set of variables that are free
	* in the current context. It provides utility methods for opening/closing
	* types to their corresponding free/closed forms. It also provide hooks for
	* attaching deferred post-inference action (see PendingCheck). Finally,
	* it can be used as an entry point for performing upper/lower bound inference
	* (see InferenceKind).
	*
	* <p><b>This is NOT part of any supported API.
	* If you write code that depends on this, you do so at your own risk.
	* This code and its internal interfaces are subject to change or
	* deletion without notice.</b>
	*/
	public class InferenceContext {

	/** list of inference vars as undet vars */
	List<Type> undetvars;

	Type update(Type t) {
	return t;
	}

	/** list of inference vars in this context */
	List<Type> inferencevars;

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

	Types types;
	Infer infer;

	public InferenceContext(Infer infer, List<Type> inferencevars) {
	this(infer, inferencevars, inferencevars.map(infer.fromTypeVarFun));
	}

	public InferenceContext(Infer infer, List<Type> inferencevars, List<Type> undetvars) {
	this.inferencevars = inferencevars;
	this.undetvars = undetvars;
	this.infer = infer;
	this.types = infer.types;
	}

	/**
	* add a new inference var to this inference context
	*/
	void addVar(TypeVar t) {
	this.undetvars = this.undetvars.prepend(infer.fromTypeVarFun.apply(t));
	this.inferencevars = this.inferencevars.prepend(t);
	}

	/**
	* returns the list of free variables (as type-variables) in this
	* inference context
	*/
	List<Type> inferenceVars() {
	return inferencevars;
	}

	/**
	* returns the list of undetermined variables in this inference context
	*/
	public List<Type> undetVars() {
	return undetvars;
	}

	/**
	* returns the list of uninstantiated variables (as type-variables) in this
	* inference context
	*/
	List<Type> restvars() {
	return filterVars(uv -> uv.getInst() == null);
	}

	/**
	* returns the list of instantiated variables (as type-variables) in this
	* inference context
	*/
	List<Type> instvars() {
	return filterVars(uv -> uv.getInst() != null);
	}

	/**
	* Get list of bounded inference variables (where bound is other than
	* declared bounds).
	*/
	final List<Type> boundedVars() {
	return filterVars(uv -> uv.getBounds(InferenceBound.UPPER)
	.diff(uv.getDeclaredBounds())
	.appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty());
	}

	/* Returns the corresponding inference variables.
	*/
	private List<Type> filterVars(Filter<UndetVar> fu) {
	ListBuffer<Type> res = new ListBuffer<>();
	for (Type t : undetvars) {
	UndetVar uv = (UndetVar)t;
	if (fu.accepts(uv)) {
	res.append(uv.qtype);
	}
	}
	return res.toList();
	}

	/**
	* is this type free?
	*/
	final boolean free(Type t) {
	return t.containsAny(inferencevars);
	}

	final boolean free(List<Type> ts) {
	for (Type t : ts) {
	if (free(t)) return true;
	}
	return false;
	}

	/**
	* Returns a list of free variables in a given type
	*/
	final List<Type> freeVarsIn(Type t) {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type iv : inferenceVars()) {
	if (t.contains(iv)) {
	buf.add(iv);
	}
	}
	return buf.toList();
	}

	final List<Type> freeVarsIn(List<Type> ts) {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type t : ts) {
	buf.appendList(freeVarsIn(t));
	}
	ListBuffer<Type> buf2 = new ListBuffer<>();
	for (Type t : buf) {
	if (!buf2.contains(t)) {
	buf2.add(t);
	}
	}
	return buf2.toList();
	}

	/**
	* Replace all free variables in a given type with corresponding
	* undet vars (used ahead of subtyping/compatibility checks to allow propagation
	* of inference constraints).
	*/
	public final Type asUndetVar(Type t) {
	return types.subst(t, inferencevars, undetvars);
	}

	final List<Type> asUndetVars(List<Type> ts) {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type t : ts) {
	buf.append(asUndetVar(t));
	}
	return buf.toList();
	}

	List<Type> instTypes() {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type t : undetvars) {
	UndetVar uv = (UndetVar)t;
	buf.append(uv.getInst() != null ? uv.getInst() : uv.qtype);
	}
	return buf.toList();
	}

	/**
	* Replace all free variables in a given type with corresponding
	* instantiated types - if one or more free variable has not been
	* fully instantiated, it will still be available in the resulting type.
	*/
	Type asInstType(Type t) {
	return types.subst(t, inferencevars, instTypes());
	}

	List<Type> asInstTypes(List<Type> ts) {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type t : ts) {
	buf.append(asInstType(t));
	}
	return buf.toList();
	}

	/**
	* Add custom hook for performing post-inference action
	*/
	void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
	freeTypeListeners.put(ftl, freeVarsIn(types));
	}

	/**
	* Mark the inference context as complete and trigger evaluation
	* of all deferred checks.
	*/
	void notifyChange() {
	notifyChange(inferencevars.diff(restvars()));
	}

	void notifyChange(List<Type> inferredVars) {
	InferenceException thrownEx = null;
	for (Map.Entry<FreeTypeListener, List<Type>> entry :
	new LinkedHashMap<>(freeTypeListeners).entrySet()) {
	if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
	try {
	entry.getKey().typesInferred(this);
	freeTypeListeners.remove(entry.getKey());
	} catch (InferenceException ex) {
	if (thrownEx == null) {
	thrownEx = ex;
	}
	}
	}
	}
	//inference exception multiplexing - present any inference exception
	//thrown when processing listeners as a single one
	if (thrownEx != null) {
	throw thrownEx;
	}
	}

	/**
	* Save the state of this inference context
	*/
	public List<Type> save() {
	ListBuffer<Type> buf = new ListBuffer<>();
	for (Type t : undetvars) {
	buf.add(((UndetVar)t).dup(infer.types));
	}
	return buf.toList();
	}

	/** Restore the state of this inference context to the previous known checkpoint.
	* Consider that the number of saved undetermined variables can be different to the current
	* amount. This is because new captured variables could have been added.
	*/
	public void rollback(List<Type> saved_undet) {
	Assert.check(saved_undet != null);
	//restore bounds (note: we need to preserve the old instances)
	ListBuffer<Type> newUndetVars = new ListBuffer<>();
	ListBuffer<Type> newInferenceVars = new ListBuffer<>();
	while (saved_undet.nonEmpty() && undetvars.nonEmpty()) {
	UndetVar uv = (UndetVar)undetvars.head;
	UndetVar uv_saved = (UndetVar)saved_undet.head;
	if (uv.qtype == uv_saved.qtype) {
	uv_saved.dupTo(uv, types);
	undetvars = undetvars.tail;
	saved_undet = saved_undet.tail;
	newUndetVars.add(uv);
	newInferenceVars.add(uv.qtype);
	} else {
	undetvars = undetvars.tail;
	}
	}
	undetvars = newUndetVars.toList();
	inferencevars = newInferenceVars.toList();
	}

	/**
	* Copy variable in this inference context to the given context
	*/
	void dupTo(final InferenceContext that) {
	dupTo(that, false);
	}

	void dupTo(final InferenceContext that, boolean clone) {
	that.inferencevars = that.inferencevars.appendList(inferencevars.diff(that.inferencevars));
	List<Type> undetsToPropagate = clone ? save() : undetvars;
	that.undetvars = that.undetvars.appendList(undetsToPropagate.diff(that.undetvars)); //propagate cloned undet!!
	//set up listeners to notify original inference contexts as
	//propagated vars are inferred in new context
	for (Type t : inferencevars) {
	that.freeTypeListeners.put(inferenceContext -> InferenceContext.this.notifyChange(), List.of(t));
	}
	}

	InferenceContext min(List<Type> roots, boolean shouldSolve, Warner warn) {
	ReachabilityVisitor rv = new ReachabilityVisitor();
	rv.scan(roots);
	if (rv.min.size() == inferencevars.length()) {
	return this;
	}

	List<Type> minVars = List.from(rv.min);
	List<Type> redundantVars = inferencevars.diff(minVars);

	//compute new undet variables (bounds associated to redundant variables are dropped)
	ListBuffer<Type> minUndetVars = new ListBuffer<>();
	for (Type minVar : minVars) {
	UndetVar uv = (UndetVar)asUndetVar(minVar);
	Assert.check(uv.incorporationActions.size() == 0);
	UndetVar uv2 = new UndetVar((TypeVar)minVar, infer.incorporationEngine(), types);
	for (InferenceBound ib : InferenceBound.values()) {
	List<Type> newBounds = uv.getBounds(ib).stream()
	.filter(b -> !redundantVars.contains(b))
	.collect(List.collector());
	uv2.setBounds(ib, newBounds);
	}
	minUndetVars.add(uv2);
	}

	//compute new minimal inference context
	InferenceContext minContext = new InferenceContext(infer, minVars, minUndetVars.toList());
	for (Type t : minContext.inferencevars) {
	//add listener that forwards notifications to original context
	minContext.addFreeTypeListener(List.of(t), (inferenceContext) -> {
	List<Type> depVars = List.from(rv.minMap.get(t));
	solve(depVars, warn);
	notifyChange();
	});
	}
	if (shouldSolve) {
	//solve definitively unreachable variables
	List<Type> unreachableVars = redundantVars.diff(List.from(rv.equiv));
	solve(unreachableVars, warn);
	}
	return minContext;
	}

	class ReachabilityVisitor extends Types.UnaryVisitor<Void> {

	Set<Type> equiv = new HashSet<>();
	Set<Type> min = new HashSet<>();
	Map<Type, Set<Type>> minMap = new HashMap<>();

	void scan(List<Type> roots) {
	roots.stream().forEach(this::visit);
	}

	@Override
	public Void visitType(Type t, Void _unused) {
	return null;
	}

	@Override
	public Void visitUndetVar(UndetVar t, Void _unused) {
	if (min.add(t.qtype)) {
	Set<Type> deps = minMap.getOrDefault(t.qtype, new HashSet<>(Collections.singleton(t.qtype)));
	for (InferenceBound boundKind : InferenceBound.values()) {
	for (Type b : t.getBounds(boundKind)) {
	Type undet = asUndetVar(b);
	if (!undet.hasTag(TypeTag.UNDETVAR)) {
	visit(undet);
	} else if (isEquiv(t, b, boundKind)) {
	deps.add(b);
	equiv.add(b);
	} else {
	visit(undet);
	}
	}
	}
	minMap.put(t.qtype, deps);
	}
	return null;
	}

	@Override
	public Void visitWildcardType(WildcardType t, Void _unused) {
	return visit(t.type);
	}

	@Override
	public Void visitTypeVar(TypeVar t, Void aVoid) {
	Type undet = asUndetVar(t);
	if (undet.hasTag(TypeTag.UNDETVAR)) {
	visitUndetVar((UndetVar)undet, null);
	}
	return null;
	}

	@Override
	public Void visitArrayType(ArrayType t, Void _unused) {
	return visit(t.elemtype);
	}

	@Override
	public Void visitClassType(ClassType t, Void _unused) {
	visit(t.getEnclosingType());
	for (Type targ : t.getTypeArguments()) {
	visit(targ);
	}
	return null;
	}

	boolean isEquiv(UndetVar from, Type t, InferenceBound boundKind) {
	UndetVar uv = (UndetVar)asUndetVar(t);
	for (InferenceBound ib : InferenceBound.values()) {
	List<Type> b1 = from.getBounds(ib);
	if (ib == boundKind) {
	b1 = b1.diff(List.of(t));
	}
	List<Type> b2 = uv.getBounds(ib);
	if (ib == boundKind.complement()) {
	b2 = b2.diff(List.of(from.qtype));
	}
	if (!b1.containsAll(b2) \|\| !b2.containsAll(b1)) {
	return false;
	}
	}
	return true;
	}
	}

	/**
	* Solve with given graph strategy.
	*/
	private void solve(GraphStrategy ss, Warner warn) {
	GraphSolver s = infer.new GraphSolver(this, warn);
	s.solve(ss);
	}

	/**
	* Solve all variables in this context.
	*/
	public void solve(Warner warn) {
	solve(infer.new LeafSolver() {
	public boolean done() {
	return restvars().isEmpty();
	}
	}, warn);
	}

	/**
	* Solve all variables in the given list.
	*/
	public void solve(final List<Type> vars, Warner warn) {
	solve(infer.new BestLeafSolver(vars) {
	public boolean done() {
	return !free(asInstTypes(vars));
	}
	}, warn);
	}

	/**
	* Solve at least one variable in given list.
	*/
	public void solveAny(List<Type> varsToSolve, Warner warn) {
	solve(infer.new BestLeafSolver(varsToSolve.intersect(restvars())) {
	public boolean done() {
	return instvars().intersect(varsToSolve).nonEmpty();
	}
	}, warn);
	}

	/**
	* Apply a set of inference steps
	*/
	private List<Type> solveBasic(EnumSet<InferenceStep> steps) {
	return solveBasic(inferencevars, steps);
	}

	List<Type> solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
	ListBuffer<Type> solvedVars = new ListBuffer<>();
	for (Type t : varsToSolve.intersect(restvars())) {
	UndetVar uv = (UndetVar)asUndetVar(t);
	for (InferenceStep step : steps) {
	if (step.accepts(uv, this)) {
	uv.setInst(step.solve(uv, this));
	solvedVars.add(uv.qtype);
	break;
	}
	}
	}
	return solvedVars.toList();
	}

	/**
	* Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
	* During overload resolution, instantiation is done by doing a partial
	* inference process using eq/lower bound instantiation. During check,
	* we also instantiate any remaining vars by repeatedly using eq/upper
	* instantiation, until all variables are solved.
	*/
	public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
	while (true) {
	List<Type> solvedVars = solveBasic(steps);
	if (restvars().isEmpty() \|\| partial) {
	//all variables have been instantiated - exit
	break;
	} else if (solvedVars.isEmpty()) {
	//some variables could not be instantiated because of cycles in
	//upper bounds - provide a (possibly recursive) default instantiation
	infer.instantiateAsUninferredVars(restvars(), this);
	break;
	} else {
	//some variables have been instantiated - replace newly instantiated
	//variables in remaining upper bounds and continue
	for (Type t : undetvars) {
	UndetVar uv = (UndetVar)t;
	uv.substBounds(solvedVars, asInstTypes(solvedVars), types);
	}
	}
	}
	infer.doIncorporation(this, warn);
	}

	@Override
	public String toString() {
	return "Inference vars: " + inferencevars + '\n' +
	"Undet vars: " + undetvars;
	}

	/* Method Types.capture() generates a new type every time it's applied
	* to a wildcard parameterized type. This is intended functionality but
	* there are some cases when what you need is not to generate a new
	* captured type but to check that a previously generated captured type
	* is correct. There are cases when caching a captured type for later
	* reuse is sound. In general two captures from the same AST are equal.
	* This is why the tree is used as the key of the map below. This map
	* stores a Type per AST.
	*/
	Map<JCTree, Type> captureTypeCache = new HashMap<>();

	Type cachedCapture(JCTree tree, Type t, boolean readOnly) {
	Type captured = captureTypeCache.get(tree);
	if (captured != null) {
	return captured;
	}

	Type result = types.capture(t);
	if (result != t && !readOnly) { // then t is a wildcard parameterized type
	captureTypeCache.put(tree, result);
	}
	return result;
	}
	}