Separate the analysis framework in a different file.

4 files changed, 260 insertions, 256 deletions

diff --git a/src/ir/analysis.rs b/src/ir/analysis.rs
new file mode 100644
index 00000000..28425a2c
--- /dev/null
+++ b/src/ir/analysis.rs
@@ -0,0 +1,256 @@
+//! Fix-point analyses on the IR using the monotone framework.
+use std::fmt;
+
+/// An analysis in the monotone framework.
+///
+/// Implementors of this trait must maintain the following two invariants:
+///
+/// 1. The concrete data must be a member of a finite-height lattice.
+/// 2. The concrete `constrain` method must be monotone: that is,
+///    if `x <= y`, then `constrain(x) <= constrain(y)`.
+///
+/// If these invariants do not hold, iteration to a fix-point might never
+/// complete.
+///
+/// For a simple example analysis, see the `ReachableFrom` type in the `tests`
+/// module below.
+pub trait MonotoneFramework: Sized + fmt::Debug {
+    /// The type of node in our dependency graph.
+    ///
+    /// This is just generic (and not `ItemId`) so that we can easily unit test
+    /// without constructing real `Item`s and their `ItemId`s.
+    type Node: Copy;
+
+    /// Any extra data that is needed during computation.
+    ///
+    /// Again, this is just generic (and not `&BindgenContext`) so that we can
+    /// easily unit test without constructing real `BindgenContext`s full of
+    /// real `Item`s and real `ItemId`s.
+    type Extra: Sized;
+
+    /// The final output of this analysis. Once we have reached a fix-point, we
+    /// convert `self` into this type, and return it as the final result of the
+    /// analysis.
+    type Output: From<Self> + fmt::Debug;
+
+    /// Construct a new instance of this analysis.
+    fn new(extra: Self::Extra) -> Self;
+
+    /// Get the initial set of nodes from which to start the analysis. Unless
+    /// you are sure of some domain-specific knowledge, this should be the
+    /// complete set of nodes.
+    fn initial_worklist(&self) -> Vec<Self::Node>;
+
+    /// Update the analysis for the given node.
+    ///
+    /// If this results in changing our internal state (ie, we discovered that
+    /// we have not reached a fix-point and iteration should continue), return
+    /// `true`. Otherwise, return `false`. When `constrain` returns false for
+    /// all nodes in the set, we have reached a fix-point and the analysis is
+    /// complete.
+    fn constrain(&mut self, node: Self::Node) -> bool;
+
+    /// For each node `d` that depends on the given `node`'s current answer when
+    /// running `constrain(d)`, call `f(d)`. This informs us which new nodes to
+    /// queue up in the worklist when `constrain(node)` reports updated
+    /// information.
+    fn each_depending_on<F>(&self, node: Self::Node, f: F)
+        where F: FnMut(Self::Node);
+}
+
+/// Run an analysis in the monotone framework.
+pub fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
+    where Analysis: MonotoneFramework,
+{
+    let mut analysis = Analysis::new(extra);
+    let mut worklist = analysis.initial_worklist();
+
+    while let Some(node) = worklist.pop() {
+        if analysis.constrain(node) {
+            analysis.each_depending_on(node, |needs_work| {
+                worklist.push(needs_work);
+            });
+        }
+    }
+
+    analysis.into()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use std::collections::{HashMap, HashSet};
+
+    // Here we find the set of nodes that are reachable from any given
+    // node. This is a lattice mapping nodes to subsets of all nodes. Our join
+    // function is set union.
+    //
+    // This is our test graph:
+    //
+    //     +---+                    +---+
+    //     |   |                    |   |
+    //     | 1 |               .----| 2 |
+    //     |   |               |    |   |
+    //     +---+               |    +---+
+    //       |                 |      ^
+    //       |                 |      |
+    //       |      +---+      '------'
+    //       '----->|   |
+    //              | 3 |
+    //       .------|   |------.
+    //       |      +---+      |
+    //       |        ^        |
+    //       v        |        v
+    //     +---+      |      +---+    +---+
+    //     |   |      |      |   |    |   |
+    //     | 4 |      |      | 5 |--->| 6 |
+    //     |   |      |      |   |    |   |
+    //     +---+      |      +---+    +---+
+    //       |        |        |        |
+    //       |        |        |        v
+    //       |      +---+      |      +---+
+    //       |      |   |      |      |   |
+    //       '----->| 7 |<-----'      | 8 |
+    //              |   |             |   |
+    //              +---+             +---+
+    //
+    // And here is the mapping from a node to the set of nodes that are
+    // reachable from it within the test graph:
+    //
+    //     1: {3,4,5,6,7,8}
+    //     2: {2}
+    //     3: {3,4,5,6,7,8}
+    //     4: {3,4,5,6,7,8}
+    //     5: {3,4,5,6,7,8}
+    //     6: {8}
+    //     7: {3,4,5,6,7,8}
+    //     8: {}
+
+    #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
+    struct Node(usize);
+
+    #[derive(Clone, Debug, Default, PartialEq, Eq)]
+    struct Graph(HashMap<Node, Vec<Node>>);
+
+    impl Graph {
+        fn make_test_graph() -> Graph {
+            let mut g = Graph::default();
+            g.0.insert(Node(1), vec![Node(3)]);
+            g.0.insert(Node(2), vec![Node(2)]);
+            g.0.insert(Node(3), vec![Node(4), Node(5)]);
+            g.0.insert(Node(4), vec![Node(7)]);
+            g.0.insert(Node(5), vec![Node(6), Node(7)]);
+            g.0.insert(Node(6), vec![Node(8)]);
+            g.0.insert(Node(7), vec![Node(3)]);
+            g.0.insert(Node(8), vec![]);
+            g
+        }
+
+        fn reverse(&self) -> Graph {
+            let mut reversed = Graph::default();
+            for (node, edges) in self.0.iter() {
+                reversed.0.entry(*node).or_insert(vec![]);
+                for referent in edges.iter() {
+                    reversed.0.entry(*referent).or_insert(vec![]).push(*node);
+                }
+            }
+            reversed
+        }
+    }
+
+    #[derive(Clone, Debug, PartialEq, Eq)]
+    struct ReachableFrom<'a> {
+        reachable: HashMap<Node, HashSet<Node>>,
+        graph: &'a Graph,
+        reversed: Graph,
+    }
+
+    impl<'a> MonotoneFramework for ReachableFrom<'a> {
+        type Node = Node;
+        type Extra = &'a Graph;
+        type Output = HashMap<Node, HashSet<Node>>;
+
+        fn new(graph: &'a Graph) -> ReachableFrom {
+            let reversed = graph.reverse();
+            ReachableFrom {
+                reachable: Default::default(),
+                graph: graph,
+                reversed: reversed,
+            }
+        }
+
+        fn initial_worklist(&self) -> Vec<Node> {
+            self.graph.0.keys().cloned().collect()
+        }
+
+        fn constrain(&mut self, node: Node) -> bool {
+            // The set of nodes reachable from a node `x` is
+            //
+            //     reachable(x) = s_0 U s_1 U ... U reachable(s_0) U reachable(s_1) U ...
+            //
+            // where there exist edges from `x` to each of `s_0, s_1, ...`.
+            //
+            // Yes, what follows is a **terribly** inefficient set union
+            // implementation. Don't copy this code outside of this test!
+
+            let original_size =
+                self.reachable.entry(node).or_insert(HashSet::new()).len();
+
+            for sub_node in self.graph.0[&node].iter() {
+                self.reachable.get_mut(&node).unwrap().insert(*sub_node);
+
+                let sub_reachable = self.reachable
+                    .entry(*sub_node)
+                    .or_insert(HashSet::new())
+                    .clone();
+
+                for transitive in sub_reachable {
+                    self.reachable.get_mut(&node).unwrap().insert(transitive);
+                }
+            }
+
+            let new_size = self.reachable[&node].len();
+            original_size != new_size
+        }
+
+        fn each_depending_on<F>(&self, node: Node, mut f: F)
+            where F: FnMut(Node),
+        {
+            for dep in self.reversed.0[&node].iter() {
+                f(*dep);
+            }
+        }
+    }
+
+    impl<'a> From<ReachableFrom<'a>> for HashMap<Node, HashSet<Node>> {
+        fn from(reachable: ReachableFrom<'a>) -> Self {
+            reachable.reachable
+        }
+    }
+
+    #[test]
+    fn monotone() {
+        let g = Graph::make_test_graph();
+        let reachable = analyze::<ReachableFrom>(&g);
+        println!("reachable = {:#?}", reachable);
+
+        fn nodes<A>(nodes: A) -> HashSet<Node>
+            where A: AsRef<[usize]>,
+        {
+            nodes.as_ref().iter().cloned().map(Node).collect()
+        }
+
+        let mut expected = HashMap::new();
+        expected.insert(Node(1), nodes([3, 4, 5, 6, 7, 8]));
+        expected.insert(Node(2), nodes([2]));
+        expected.insert(Node(3), nodes([3, 4, 5, 6, 7, 8]));
+        expected.insert(Node(4), nodes([3, 4, 5, 6, 7, 8]));
+        expected.insert(Node(5), nodes([3, 4, 5, 6, 7, 8]));
+        expected.insert(Node(6), nodes([8]));
+        expected.insert(Node(7), nodes([3, 4, 5, 6, 7, 8]));
+        expected.insert(Node(8), nodes([]));
+        println!("expected = {:#?}", expected);
+
+        assert_eq!(reachable, expected);
+    }
+}
diff --git a/src/ir/context.rs b/src/ir/context.rs
index b14d963b..c3a0dd5a 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -5,7 +5,8 @@ use super::int::IntKind;
 use super::item::{IsOpaque, Item, ItemAncestors, ItemCanonicalPath, ItemSet};
 use super::item_kind::ItemKind;
 use super::module::{Module, ModuleKind};
-use super::named::{UsedTemplateParameters, analyze};
+use super::named::UsedTemplateParameters;
+use super::analysis::analyze;
 use super::template::{TemplateInstantiation, TemplateParameters};
 use super::traversal::{self, Edge, ItemTraversal};
 use super::ty::{FloatKind, Type, TypeKind};
diff --git a/src/ir/mod.rs b/src/ir/mod.rs
index d703e53d..f28ca9cb 100644
--- a/src/ir/mod.rs
+++ b/src/ir/mod.rs
@@ -4,6 +4,7 @@
 //! the IR.
 
 pub mod annotations;
+pub mod analysis;
 pub mod comp;
 pub mod context;
 pub mod derive;
diff --git a/src/ir/named.rs b/src/ir/named.rs
index 943d3a57..a36ded64 100644
--- a/src/ir/named.rs
+++ b/src/ir/named.rs
@@ -126,88 +126,13 @@
 //!
 //! [spa]: https://cs.au.dk/~amoeller/spa/spa.pdf
 
+use super::analysis::MonotoneFramework;
 use super::context::{BindgenContext, ItemId};
 use super::item::{Item, ItemSet};
 use super::template::{TemplateInstantiation, TemplateParameters};
 use super::traversal::{EdgeKind, Trace};
 use super::ty::TypeKind;
 use std::collections::{HashMap, HashSet};
-use std::fmt;
-
-/// An analysis in the monotone framework.
-///
-/// Implementors of this trait must maintain the following two invariants:
-///
-/// 1. The concrete data must be a member of a finite-height lattice.
-/// 2. The concrete `constrain` method must be monotone: that is,
-///    if `x <= y`, then `constrain(x) <= constrain(y)`.
-///
-/// If these invariants do not hold, iteration to a fix-point might never
-/// complete.
-///
-/// For a simple example analysis, see the `ReachableFrom` type in the `tests`
-/// module below.
-pub trait MonotoneFramework: Sized + fmt::Debug {
-    /// The type of node in our dependency graph.
-    ///
-    /// This is just generic (and not `ItemId`) so that we can easily unit test
-    /// without constructing real `Item`s and their `ItemId`s.
-    type Node: Copy;
-
-    /// Any extra data that is needed during computation.
-    ///
-    /// Again, this is just generic (and not `&BindgenContext`) so that we can
-    /// easily unit test without constructing real `BindgenContext`s full of
-    /// real `Item`s and real `ItemId`s.
-    type Extra: Sized;
-
-    /// The final output of this analysis. Once we have reached a fix-point, we
-    /// convert `self` into this type, and return it as the final result of the
-    /// analysis.
-    type Output: From<Self> + fmt::Debug;
-
-    /// Construct a new instance of this analysis.
-    fn new(extra: Self::Extra) -> Self;
-
-    /// Get the initial set of nodes from which to start the analysis. Unless
-    /// you are sure of some domain-specific knowledge, this should be the
-    /// complete set of nodes.
-    fn initial_worklist(&self) -> Vec<Self::Node>;
-
-    /// Update the analysis for the given node.
-    ///
-    /// If this results in changing our internal state (ie, we discovered that
-    /// we have not reached a fix-point and iteration should continue), return
-    /// `true`. Otherwise, return `false`. When `constrain` returns false for
-    /// all nodes in the set, we have reached a fix-point and the analysis is
-    /// complete.
-    fn constrain(&mut self, node: Self::Node) -> bool;
-
-    /// For each node `d` that depends on the given `node`'s current answer when
-    /// running `constrain(d)`, call `f(d)`. This informs us which new nodes to
-    /// queue up in the worklist when `constrain(node)` reports updated
-    /// information.
-    fn each_depending_on<F>(&self, node: Self::Node, f: F)
-        where F: FnMut(Self::Node);
-}
-
-/// Run an analysis in the monotone framework.
-pub fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
-    where Analysis: MonotoneFramework,
-{
-    let mut analysis = Analysis::new(extra);
-    let mut worklist = analysis.initial_worklist();
-
-    while let Some(node) = worklist.pop() {
-        if analysis.constrain(node) {
-            analysis.each_depending_on(node, |needs_work| {
-                worklist.push(needs_work);
-            });
-        }
-    }
-
-    analysis.into()
-}
 
 /// An analysis that finds for each IR item its set of template parameters that
 /// it uses.
@@ -651,182 +576,3 @@ impl<'ctx, 'gen> From<UsedTemplateParameters<'ctx, 'gen>>
             .collect()
     }
 }
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-    use std::collections::{HashMap, HashSet};
-
-    // Here we find the set of nodes that are reachable from any given
-    // node. This is a lattice mapping nodes to subsets of all nodes. Our join
-    // function is set union.
-    //
-    // This is our test graph:
-    //
-    //     +---+                    +---+
-    //     |   |                    |   |
-    //     | 1 |               .----| 2 |
-    //     |   |               |    |   |
-    //     +---+               |    +---+
-    //       |                 |      ^
-    //       |                 |      |
-    //       |      +---+      '------'
-    //       '----->|   |
-    //              | 3 |
-    //       .------|   |------.
-    //       |      +---+      |
-    //       |        ^        |
-    //       v        |        v
-    //     +---+      |      +---+    +---+
-    //     |   |      |      |   |    |   |
-    //     | 4 |      |      | 5 |--->| 6 |
-    //     |   |      |      |   |    |   |
-    //     +---+      |      +---+    +---+
-    //       |        |        |        |
-    //       |        |        |        v
-    //       |      +---+      |      +---+
-    //       |      |   |      |      |   |
-    //       '----->| 7 |<-----'      | 8 |
-    //              |   |             |   |
-    //              +---+             +---+
-    //
-    // And here is the mapping from a node to the set of nodes that are
-    // reachable from it within the test graph:
-    //
-    //     1: {3,4,5,6,7,8}
-    //     2: {2}
-    //     3: {3,4,5,6,7,8}
-    //     4: {3,4,5,6,7,8}
-    //     5: {3,4,5,6,7,8}
-    //     6: {8}
-    //     7: {3,4,5,6,7,8}
-    //     8: {}
-
-    #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
-    struct Node(usize);
-
-    #[derive(Clone, Debug, Default, PartialEq, Eq)]
-    struct Graph(HashMap<Node, Vec<Node>>);
-
-    impl Graph {
-        fn make_test_graph() -> Graph {
-            let mut g = Graph::default();
-            g.0.insert(Node(1), vec![Node(3)]);
-            g.0.insert(Node(2), vec![Node(2)]);
-            g.0.insert(Node(3), vec![Node(4), Node(5)]);
-            g.0.insert(Node(4), vec![Node(7)]);
-            g.0.insert(Node(5), vec![Node(6), Node(7)]);
-            g.0.insert(Node(6), vec![Node(8)]);
-            g.0.insert(Node(7), vec![Node(3)]);
-            g.0.insert(Node(8), vec![]);
-            g
-        }
-
-        fn reverse(&self) -> Graph {
-            let mut reversed = Graph::default();
-            for (node, edges) in self.0.iter() {
-                reversed.0.entry(*node).or_insert(vec![]);
-                for referent in edges.iter() {
-                    reversed.0.entry(*referent).or_insert(vec![]).push(*node);
-                }
-            }
-            reversed
-        }
-    }
-
-    #[derive(Clone, Debug, PartialEq, Eq)]
-    struct ReachableFrom<'a> {
-        reachable: HashMap<Node, HashSet<Node>>,
-        graph: &'a Graph,
-        reversed: Graph,
-    }
-
-    impl<'a> MonotoneFramework for ReachableFrom<'a> {
-        type Node = Node;
-        type Extra = &'a Graph;
-        type Output = HashMap<Node, HashSet<Node>>;
-
-        fn new(graph: &'a Graph) -> ReachableFrom {
-            let reversed = graph.reverse();
-            ReachableFrom {
-                reachable: Default::default(),
-                graph: graph,
-                reversed: reversed,
-            }
-        }
-
-        fn initial_worklist(&self) -> Vec<Node> {
-            self.graph.0.keys().cloned().collect()
-        }
-
-        fn constrain(&mut self, node: Node) -> bool {
-            // The set of nodes reachable from a node `x` is
-            //
-            //     reachable(x) = s_0 U s_1 U ... U reachable(s_0) U reachable(s_1) U ...
-            //
-            // where there exist edges from `x` to each of `s_0, s_1, ...`.
-            //
-            // Yes, what follows is a **terribly** inefficient set union
-            // implementation. Don't copy this code outside of this test!
-
-            let original_size =
-                self.reachable.entry(node).or_insert(HashSet::new()).len();
-
-            for sub_node in self.graph.0[&node].iter() {
-                self.reachable.get_mut(&node).unwrap().insert(*sub_node);
-
-                let sub_reachable = self.reachable
-                    .entry(*sub_node)
-                    .or_insert(HashSet::new())
-                    .clone();
-
-                for transitive in sub_reachable {
-                    self.reachable.get_mut(&node).unwrap().insert(transitive);
-                }
-            }
-
-            let new_size = self.reachable[&node].len();
-            original_size != new_size
-        }
-
-        fn each_depending_on<F>(&self, node: Node, mut f: F)
-            where F: FnMut(Node),
-        {
-            for dep in self.reversed.0[&node].iter() {
-                f(*dep);
-            }
-        }
-    }
-
-    impl<'a> From<ReachableFrom<'a>> for HashMap<Node, HashSet<Node>> {
-        fn from(reachable: ReachableFrom<'a>) -> Self {
-            reachable.reachable
-        }
-    }
-
-    #[test]
-    fn monotone() {
-        let g = Graph::make_test_graph();
-        let reachable = analyze::<ReachableFrom>(&g);
-        println!("reachable = {:#?}", reachable);
-
-        fn nodes<A>(nodes: A) -> HashSet<Node>
-            where A: AsRef<[usize]>,
-        {
-            nodes.as_ref().iter().cloned().map(Node).collect()
-        }
-
-        let mut expected = HashMap::new();
-        expected.insert(Node(1), nodes([3, 4, 5, 6, 7, 8]));
-        expected.insert(Node(2), nodes([2]));
-        expected.insert(Node(3), nodes([3, 4, 5, 6, 7, 8]));
-        expected.insert(Node(4), nodes([3, 4, 5, 6, 7, 8]));
-        expected.insert(Node(5), nodes([3, 4, 5, 6, 7, 8]));
-        expected.insert(Node(6), nodes([8]));
-        expected.insert(Node(7), nodes([3, 4, 5, 6, 7, 8]));
-        expected.insert(Node(8), nodes([]));
-        println!("expected = {:#?}", expected);
-
-        assert_eq!(reachable, expected);
-    }
-}