langtools/src/share/classes/com/sun/tools/javac/comp/Infer.java
changeset 22163 3651128c74eb
parent 21488 4a69e26aa999
child 22165 ec53c8946fc2
equal deleted inserted replaced
22162:3b3e23e67329 22163:3651128c74eb
    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      */
   925             @Override
   923             @Override
   926             public boolean accepts(Type t) {
   924             public boolean accepts(Type t) {
   927                 return !t.isErroneous() && !inferenceContext.free(t) &&
   925                 return !t.isErroneous() && !inferenceContext.free(t) &&
   928                         !t.hasTag(BOT);
   926                         !t.hasTag(BOT);
   929             }
   927             }
   930         };
   928         }
   931 
   929 
   932     /**
   930     /**
   933      * This enumeration defines all possible bound-checking related errors.
   931      * This enumeration defines all possible bound-checking related errors.
   934      */
   932      */
   935     enum BoundErrorKind {
   933     enum BoundErrorKind {
  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) {
  2017                 }, List.of(t));
  2011                 }, List.of(t));
  2018             }
  2012             }
  2019         }
  2013         }
  2020 
  2014 
  2021         private void solve(GraphStrategy ss, Warner warn) {
  2015         private void solve(GraphStrategy ss, Warner warn) {
  2022             solve(ss, new HashMap<Type, Set<Type>>(), warn);
  2016             solve(ss, new HashMap<>(), warn);
  2023         }
  2017         }
  2024 
  2018 
  2025         /**
  2019         /**
  2026          * Solve with given graph strategy.
  2020          * Solve with given graph strategy.
  2027          */
  2021          */