39 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; |
39 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; |
40 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; |
40 import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; |
41 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException; |
41 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException; |
42 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; |
42 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; |
43 |
43 |
|
44 import java.util.Comparator; |
44 import java.util.HashMap; |
45 import java.util.HashMap; |
45 import java.util.Map; |
46 import java.util.Map; |
46 import java.util.Set; |
47 import java.util.Set; |
|
48 import java.util.TreeSet; |
47 |
49 |
48 import java.util.ArrayList; |
50 import java.util.ArrayList; |
49 import java.util.Collections; |
51 import java.util.Collections; |
50 import java.util.EnumSet; |
52 import java.util.EnumSet; |
51 import java.util.HashSet; |
53 import java.util.HashSet; |
907 BestLeafSolver(List<Type> varsToSolve) { |
909 BestLeafSolver(List<Type> varsToSolve) { |
908 this.varsToSolve = varsToSolve; |
910 this.varsToSolve = varsToSolve; |
909 } |
911 } |
910 |
912 |
911 /** |
913 /** |
912 * Computes the cost associated with a given node; the cost is computed |
914 * Computes the minimum path that goes from a given node to any of the nodes |
913 * as the total number of type-variables that should be eagerly instantiated |
915 * containing a variable in {@code varsToSolve}. For any given path, the cost |
914 * in order to get to some of the variables in {@code varsToSolve} from |
916 * is computed as the total number of type-variables that should be eagerly |
915 * a given node |
917 * instantiated across that path. |
916 */ |
918 */ |
917 void computeCostIfNeeded(Node n, Map<Node, Integer> costMap) { |
919 int computeMinPath(InferenceGraph g, Node n) { |
918 if (costMap.containsKey(n)) { |
920 return computeMinPath(g, n, List.<Node>nil(), 0); |
919 return; |
921 } |
920 } else if (!Collections.disjoint(n.data, varsToSolve)) { |
922 |
921 costMap.put(n, n.data.size()); |
923 int computeMinPath(InferenceGraph g, Node n, List<Node> path, int cost) { |
|
924 if (path.contains(n)) return Integer.MAX_VALUE; |
|
925 List<Node> path2 = path.prepend(n); |
|
926 int cost2 = cost + n.data.size(); |
|
927 if (!Collections.disjoint(n.data, varsToSolve)) { |
|
928 return cost2; |
922 } else { |
929 } else { |
923 int subcost = Integer.MAX_VALUE; |
930 int bestPath = Integer.MAX_VALUE; |
924 costMap.put(n, subcost); //avoid loops |
931 for (Node n2 : g.nodes) { |
925 for (Node n2 : n.getDependencies()) { |
932 if (n2.deps.contains(n)) { |
926 computeCostIfNeeded(n2, costMap); |
933 int res = computeMinPath(g, n2, path2, cost2); |
927 subcost = Math.min(costMap.get(n2), subcost); |
934 if (res < bestPath) { |
928 } |
935 bestPath = res; |
929 //update cost map to reflect real cost |
936 } |
930 costMap.put(n, subcost == Integer.MAX_VALUE ? |
937 } |
931 Integer.MAX_VALUE : |
938 } |
932 n.data.size() + subcost); |
939 return bestPath; |
933 } |
940 } |
934 } |
941 } |
935 |
942 |
936 /** |
943 /** |
937 * Pick the leaf that minimize cost |
944 * Pick the leaf that minimize cost |
938 */ |
945 */ |
939 @Override |
946 @Override |
940 public Node pickNode(final InferenceGraph g) { |
947 public Node pickNode(final InferenceGraph g) { |
941 final Map<Node, Integer> costMap = new HashMap<Node, Integer>(); |
948 final Map<Node, Integer> leavesMap = new HashMap<Node, Integer>(); |
942 ArrayList<Node> leaves = new ArrayList<Node>(); |
|
943 for (Node n : g.nodes) { |
949 for (Node n : g.nodes) { |
944 computeCostIfNeeded(n, costMap); |
|
945 if (n.isLeaf(n)) { |
950 if (n.isLeaf(n)) { |
946 leaves.add(n); |
951 leavesMap.put(n, computeMinPath(g, n)); |
947 } |
952 } |
948 } |
953 } |
949 Assert.check(!leaves.isEmpty(), "No nodes to solve!"); |
954 Assert.check(!leavesMap.isEmpty(), "No nodes to solve!"); |
950 Collections.sort(leaves, new java.util.Comparator<Node>() { |
955 TreeSet<Node> orderedLeaves = new TreeSet<Node>(new Comparator<Node>() { |
951 public int compare(Node n1, Node n2) { |
956 public int compare(Node n1, Node n2) { |
952 return costMap.get(n1) - costMap.get(n2); |
957 return leavesMap.get(n1) - leavesMap.get(n2); |
953 } |
958 } |
954 }); |
959 }); |
955 return leaves.get(0); |
960 orderedLeaves.addAll(leavesMap.keySet()); |
|
961 return orderedLeaves.first(); |
956 } |
962 } |
957 } |
963 } |
958 |
964 |
959 /** |
965 /** |
960 * The inference process can be thought of as a sequence of steps. Each step |
966 * The inference process can be thought of as a sequence of steps. Each step |