60 * If you write code that depends on this, you do so at your own risk. |
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 |
61 * This code and its internal interfaces are subject to change or |
62 * deletion without notice.</b> |
62 * deletion without notice.</b> |
63 */ |
63 */ |
64 public class Infer { |
64 public class Infer { |
65 protected static final Context.Key<Infer> inferKey = |
65 protected static final Context.Key<Infer> inferKey = new Context.Key<>(); |
66 new Context.Key<Infer>(); |
|
67 |
66 |
68 Resolve rs; |
67 Resolve rs; |
69 Check chk; |
68 Check chk; |
70 Symtab syms; |
69 Symtab syms; |
71 Types types; |
70 Types types; |
508 for (Type t : undetvars) { |
507 for (Type t : undetvars) { |
509 UndetVar uv = (UndetVar)t; |
508 UndetVar uv = (UndetVar)t; |
510 uv.listener = null; |
509 uv.listener = null; |
511 } |
510 } |
512 } |
511 } |
513 }; |
512 } |
514 |
513 |
515 /** max number of incorporation rounds */ |
514 /** max number of incorporation rounds */ |
516 static final int MAX_INCORPORATION_STEPS = 100; |
515 static final int MAX_INCORPORATION_STEPS = 100; |
517 |
516 |
518 /** |
517 /** |
519 * This enumeration defines an entry point for doing inference variable |
518 * This enumeration defines an entry point for doing inference variable |
520 * bound incorporation - it can be used to inject custom incorporation |
519 * bound incorporation - it can be used to inject custom incorporation |
891 return opKind.apply(op1, op2, warn, types); |
890 return opKind.apply(op1, op2, warn, types); |
892 } |
891 } |
893 } |
892 } |
894 |
893 |
895 /** an incorporation cache keeps track of all executed incorporation-related operations */ |
894 /** an incorporation cache keeps track of all executed incorporation-related operations */ |
896 Map<IncorporationBinaryOp, Boolean> incorporationCache = |
895 Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>(); |
897 new HashMap<IncorporationBinaryOp, Boolean>(); |
|
898 |
896 |
899 /** |
897 /** |
900 * Make sure that the upper bounds we got so far lead to a solvable inference |
898 * Make sure that the upper bounds we got so far lead to a solvable inference |
901 * variable by making sure that a glb exists. |
899 * variable by making sure that a glb exists. |
902 */ |
900 */ |
1043 abstract class LeafSolver implements GraphStrategy { |
1041 abstract class LeafSolver implements GraphStrategy { |
1044 public Node pickNode(InferenceGraph g) { |
1042 public Node pickNode(InferenceGraph g) { |
1045 if (g.nodes.isEmpty()) { |
1043 if (g.nodes.isEmpty()) { |
1046 //should not happen |
1044 //should not happen |
1047 throw new NodeNotFoundException(g); |
1045 throw new NodeNotFoundException(g); |
1048 }; |
1046 } |
1049 return g.nodes.get(0); |
1047 return g.nodes.get(0); |
1050 } |
1048 } |
1051 |
1049 |
1052 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) { |
1050 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) { |
1053 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer); |
1051 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer); |
1109 Pair<List<Node>, Integer> cachedPath = treeCache.get(n); |
1107 Pair<List<Node>, Integer> cachedPath = treeCache.get(n); |
1110 if (cachedPath == null) { |
1108 if (cachedPath == null) { |
1111 //cache miss |
1109 //cache miss |
1112 if (n.isLeaf()) { |
1110 if (n.isLeaf()) { |
1113 //if leaf, stop |
1111 //if leaf, stop |
1114 cachedPath = new Pair<List<Node>, Integer>(List.of(n), n.data.length()); |
1112 cachedPath = new Pair<>(List.of(n), n.data.length()); |
1115 } else { |
1113 } else { |
1116 //if non-leaf, proceed recursively |
1114 //if non-leaf, proceed recursively |
1117 Pair<List<Node>, Integer> path = new Pair<List<Node>, Integer>(List.of(n), n.data.length()); |
1115 Pair<List<Node>, Integer> path = new Pair<>(List.of(n), n.data.length()); |
1118 for (Node n2 : n.getAllDependencies()) { |
1116 for (Node n2 : n.getAllDependencies()) { |
1119 if (n2 == n) continue; |
1117 if (n2 == n) continue; |
1120 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2); |
1118 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2); |
1121 path = new Pair<List<Node>, Integer>( |
1119 path = new Pair<>(path.fst.prependList(subpath.fst), |
1122 path.fst.prependList(subpath.fst), |
1120 path.snd + subpath.snd); |
1123 path.snd + subpath.snd); |
|
1124 } |
1121 } |
1125 cachedPath = path; |
1122 cachedPath = path; |
1126 } |
1123 } |
1127 //save results in cache |
1124 //save results in cache |
1128 treeCache.put(n, cachedPath); |
1125 treeCache.put(n, cachedPath); |
1129 } |
1126 } |
1130 return cachedPath; |
1127 return cachedPath; |
1131 } |
1128 } |
1132 |
1129 |
1133 /** cache used to avoid redundant computation of tree costs */ |
1130 /** cache used to avoid redundant computation of tree costs */ |
1134 final Map<Node, Pair<List<Node>, Integer>> treeCache = |
1131 final Map<Node, Pair<List<Node>, Integer>> treeCache = new HashMap<>(); |
1135 new HashMap<Node, Pair<List<Node>, Integer>>(); |
|
1136 |
1132 |
1137 /** constant value used to mark non-existent paths */ |
1133 /** constant value used to mark non-existent paths */ |
1138 final Pair<List<Node>, Integer> noPath = |
1134 final Pair<List<Node>, Integer> noPath = new Pair<>(null, Integer.MAX_VALUE); |
1139 new Pair<List<Node>, Integer>(null, Integer.MAX_VALUE); |
|
1140 |
1135 |
1141 /** |
1136 /** |
1142 * Pick the leaf that minimize cost |
1137 * Pick the leaf that minimize cost |
1143 */ |
1138 */ |
1144 @Override |
1139 @Override |
1458 /** map listing all dependencies (grouped by kind) */ |
1453 /** map listing all dependencies (grouped by kind) */ |
1459 EnumMap<DependencyKind, Set<Node>> deps; |
1454 EnumMap<DependencyKind, Set<Node>> deps; |
1460 |
1455 |
1461 Node(Type ivar) { |
1456 Node(Type ivar) { |
1462 super(ListBuffer.of(ivar)); |
1457 super(ListBuffer.of(ivar)); |
1463 this.deps = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class); |
1458 this.deps = new EnumMap<>(DependencyKind.class); |
1464 } |
1459 } |
1465 |
1460 |
1466 @Override |
1461 @Override |
1467 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() { |
1462 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() { |
1468 return DependencyKind.values(); |
1463 return DependencyKind.values(); |
1500 |
1495 |
1501 /** |
1496 /** |
1502 * Retrieves all dependencies with given kind(s). |
1497 * Retrieves all dependencies with given kind(s). |
1503 */ |
1498 */ |
1504 protected Set<Node> getDependencies(DependencyKind... depKinds) { |
1499 protected Set<Node> getDependencies(DependencyKind... depKinds) { |
1505 Set<Node> buf = new LinkedHashSet<Node>(); |
1500 Set<Node> buf = new LinkedHashSet<>(); |
1506 for (DependencyKind dk : depKinds) { |
1501 for (DependencyKind dk : depKinds) { |
1507 Set<Node> depsByKind = deps.get(dk); |
1502 Set<Node> depsByKind = deps.get(dk); |
1508 if (depsByKind != null) { |
1503 if (depsByKind != null) { |
1509 buf.addAll(depsByKind); |
1504 buf.addAll(depsByKind); |
1510 } |
1505 } |
1516 * Adds dependency with given kind. |
1511 * Adds dependency with given kind. |
1517 */ |
1512 */ |
1518 protected void addDependency(DependencyKind dk, Node depToAdd) { |
1513 protected void addDependency(DependencyKind dk, Node depToAdd) { |
1519 Set<Node> depsByKind = deps.get(dk); |
1514 Set<Node> depsByKind = deps.get(dk); |
1520 if (depsByKind == null) { |
1515 if (depsByKind == null) { |
1521 depsByKind = new LinkedHashSet<Node>(); |
1516 depsByKind = new LinkedHashSet<>(); |
1522 deps.put(dk, depsByKind); |
1517 deps.put(dk, depsByKind); |
1523 } |
1518 } |
1524 depsByKind.add(depToAdd); |
1519 depsByKind.add(depToAdd); |
1525 } |
1520 } |
1526 |
1521 |
1552 * Compute closure of a give node, by recursively walking |
1547 * Compute closure of a give node, by recursively walking |
1553 * through all its dependencies (of given kinds) |
1548 * through all its dependencies (of given kinds) |
1554 */ |
1549 */ |
1555 protected Set<Node> closure(DependencyKind... depKinds) { |
1550 protected Set<Node> closure(DependencyKind... depKinds) { |
1556 boolean progress = true; |
1551 boolean progress = true; |
1557 Set<Node> closure = new HashSet<Node>(); |
1552 Set<Node> closure = new HashSet<>(); |
1558 closure.add(this); |
1553 closure.add(this); |
1559 while (progress) { |
1554 while (progress) { |
1560 progress = false; |
1555 progress = false; |
1561 for (Node n1 : new HashSet<Node>(closure)) { |
1556 for (Node n1 : new HashSet<>(closure)) { |
1562 progress = closure.addAll(n1.getDependencies(depKinds)); |
1557 progress = closure.addAll(n1.getDependencies(depKinds)); |
1563 } |
1558 } |
1564 } |
1559 } |
1565 return closure; |
1560 return closure; |
1566 } |
1561 } |
1593 for (DependencyKind dk : DependencyKind.values()) { |
1588 for (DependencyKind dk : DependencyKind.values()) { |
1594 addDependencies(dk, n.getDependencies(dk)); |
1589 addDependencies(dk, n.getDependencies(dk)); |
1595 } |
1590 } |
1596 } |
1591 } |
1597 //update deps |
1592 //update deps |
1598 EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class); |
1593 EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<>(DependencyKind.class); |
1599 for (DependencyKind dk : DependencyKind.values()) { |
1594 for (DependencyKind dk : DependencyKind.values()) { |
1600 for (Node d : getDependencies(dk)) { |
1595 for (Node d : getDependencies(dk)) { |
1601 Set<Node> depsByKind = deps2.get(dk); |
1596 Set<Node> depsByKind = deps2.get(dk); |
1602 if (depsByKind == null) { |
1597 if (depsByKind == null) { |
1603 depsByKind = new LinkedHashSet<Node>(); |
1598 depsByKind = new LinkedHashSet<>(); |
1604 deps2.put(dk, depsByKind); |
1599 deps2.put(dk, depsByKind); |
1605 } |
1600 } |
1606 if (data.contains(d.data.first())) { |
1601 if (data.contains(d.data.first())) { |
1607 depsByKind.add(this); |
1602 depsByKind.add(this); |
1608 } else { |
1603 } else { |
1672 * in the graph. For each component containing more than one node, a super node is |
1667 * in the graph. For each component containing more than one node, a super node is |
1673 * created, effectively replacing the original cyclic nodes. |
1668 * created, effectively replacing the original cyclic nodes. |
1674 */ |
1669 */ |
1675 void initNodes(Map<Type, Set<Type>> stuckDeps) { |
1670 void initNodes(Map<Type, Set<Type>> stuckDeps) { |
1676 //add nodes |
1671 //add nodes |
1677 nodes = new ArrayList<Node>(); |
1672 nodes = new ArrayList<>(); |
1678 for (Type t : inferenceContext.restvars()) { |
1673 for (Type t : inferenceContext.restvars()) { |
1679 nodes.add(new Node(t)); |
1674 nodes.add(new Node(t)); |
1680 } |
1675 } |
1681 //add dependencies |
1676 //add dependencies |
1682 for (Node n_i : nodes) { |
1677 for (Node n_i : nodes) { |
1694 n_i.addDependency(DependencyKind.STUCK, n_j); |
1689 n_i.addDependency(DependencyKind.STUCK, n_j); |
1695 } |
1690 } |
1696 } |
1691 } |
1697 } |
1692 } |
1698 //merge cyclic nodes |
1693 //merge cyclic nodes |
1699 ArrayList<Node> acyclicNodes = new ArrayList<Node>(); |
1694 ArrayList<Node> acyclicNodes = new ArrayList<>(); |
1700 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { |
1695 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { |
1701 if (conSubGraph.length() > 1) { |
1696 if (conSubGraph.length() > 1) { |
1702 Node root = conSubGraph.head; |
1697 Node root = conSubGraph.head; |
1703 root.mergeWith(conSubGraph.tail); |
1698 root.mergeWith(conSubGraph.tail); |
1704 for (Node n : conSubGraph) { |
1699 for (Node n : conSubGraph) { |
1751 List<Type> undetvars; |
1746 List<Type> undetvars; |
1752 |
1747 |
1753 /** list of inference vars in this context */ |
1748 /** list of inference vars in this context */ |
1754 List<Type> inferencevars; |
1749 List<Type> inferencevars; |
1755 |
1750 |
1756 java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners = |
1751 Map<FreeTypeListener, List<Type>> freeTypeListeners = new HashMap<>(); |
1757 new java.util.HashMap<FreeTypeListener, List<Type>>(); |
|
1758 |
1752 |
1759 List<FreeTypeListener> freetypeListeners = List.nil(); |
1753 List<FreeTypeListener> freetypeListeners = List.nil(); |
1760 |
1754 |
1761 public InferenceContext(List<Type> inferencevars) { |
1755 public InferenceContext(List<Type> inferencevars) { |
1762 this.undetvars = Type.map(inferencevars, fromTypeVarFun); |
1756 this.undetvars = Type.map(inferencevars, fromTypeVarFun); |
1944 } |
1938 } |
1945 |
1939 |
1946 void notifyChange(List<Type> inferredVars) { |
1940 void notifyChange(List<Type> inferredVars) { |
1947 InferenceException thrownEx = null; |
1941 InferenceException thrownEx = null; |
1948 for (Map.Entry<FreeTypeListener, List<Type>> entry : |
1942 for (Map.Entry<FreeTypeListener, List<Type>> entry : |
1949 new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) { |
1943 new HashMap<>(freeTypeListeners).entrySet()) { |
1950 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) { |
1944 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) { |
1951 try { |
1945 try { |
1952 entry.getKey().typesInferred(this); |
1946 entry.getKey().typesInferred(this); |
1953 freeTypeListeners.remove(entry.getKey()); |
1947 freeTypeListeners.remove(entry.getKey()); |
1954 } catch (InferenceException ex) { |
1948 } catch (InferenceException ex) { |