| /* |
| * Copyright (c) 2015, 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.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> |
| */ |
| 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 HashMap<>(); |
| |
| 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 uninstantiated variables (as type-variables) in this |
| * inference context |
| */ |
| List<Type> restvars() { |
| return filterVars(new Filter<UndetVar>() { |
| public boolean accepts(UndetVar uv) { |
| return uv.getInst() == null; |
| } |
| }); |
| } |
| |
| /** |
| * returns the list of instantiated variables (as type-variables) in this |
| * inference context |
| */ |
| List<Type> instvars() { |
| return filterVars(new Filter<UndetVar>() { |
| public boolean accepts(UndetVar uv) { |
| return uv.getInst() != null; |
| } |
| }); |
| } |
| |
| /** |
| * Get list of bounded inference variables (where bound is other than |
| * declared bounds). |
| */ |
| final List<Type> boundedVars() { |
| return filterVars(new Filter<UndetVar>() { |
| public boolean accepts(UndetVar uv) { |
| return 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). |
| */ |
| 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 HashMap<>(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 |
| */ |
| 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. |
| */ |
| 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(new FreeTypeListener() { |
| public void typesInferred(InferenceContext 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); |
| 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 (Type b : t.getBounds(InferenceBound.values())) { |
| Type undet = asUndetVar(b); |
| if (!undet.hasTag(TypeTag.UNDETVAR)) { |
| visit(undet); |
| } else if (isEquiv((UndetVar)undet, b)){ |
| 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) { |
| UndetVar uv = (UndetVar)asUndetVar(t); |
| for (InferenceBound ib : InferenceBound.values()) { |
| List<Type> b1 = uv.getBounds(ib); |
| List<Type> b2 = from.getBounds(ib); |
| if (!b1.containsAll(b2) || !b2.containsAll(b1)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| } |
| |
| private void solve(GraphStrategy ss, Warner warn) { |
| solve(ss, new HashMap<Type, Set<Type>>(), warn); |
| } |
| |
| /** |
| * Solve with given graph strategy. |
| */ |
| private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) { |
| GraphSolver s = infer.new GraphSolver(this, stuckDeps, 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, Map<Type, Set<Type>> optDeps, Warner warn) { |
| solve(infer.new BestLeafSolver(varsToSolve.intersect(restvars())) { |
| public boolean done() { |
| return instvars().intersect(varsToSolve).nonEmpty(); |
| } |
| }, optDeps, 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; |
| } |
| } |