Auto merge of #24209 - nikomatsakis:refactor-unification, r=nrc

I'm on a quest to slowly refactor a lot of the inference code. A first step for that is moving the "pure data structures" out so as to simplify what's left. This PR moves `snapshot_vec`, `graph`, and `unify` into their own crate (`librustc_data_structures`). They can then be unit-tested, benchmarked, etc more easily. As a benefit, I improved the performance of unification slightly on the benchmark I added vs the original code.

r? @nrc 

18 files changed, 782 insertions, 382 deletions

diff --git a/mk/crates.mk b/mk/crates.mk
index 666d95b6d65..f7237c90efc 100644
--- a/mk/crates.mk
+++ b/mk/crates.mk
@@ -54,7 +54,8 @@ TARGET_CRATES := libc std flate arena term \
                  log graphviz core rbml alloc \
                  unicode rustc_bitflags
 RUSTC_CRATES := rustc rustc_typeck rustc_borrowck rustc_resolve rustc_driver \
-                rustc_trans rustc_back rustc_llvm rustc_privacy rustc_lint
+                rustc_trans rustc_back rustc_llvm rustc_privacy rustc_lint \
+                rustc_data_structures
 HOST_CRATES := syntax $(RUSTC_CRATES) rustdoc fmt_macros
 CRATES := $(TARGET_CRATES) $(HOST_CRATES)
 TOOLS := compiletest rustdoc rustc rustbook
@@ -80,9 +81,10 @@ DEPS_rustc_resolve := rustc log syntax
 DEPS_rustc_privacy := rustc log syntax
 DEPS_rustc_lint := rustc log syntax
 DEPS_rustc := syntax flate arena serialize getopts rbml \
-              log graphviz rustc_llvm rustc_back
+              log graphviz rustc_llvm rustc_back rustc_data_structures
 DEPS_rustc_llvm := native:rustllvm libc std
 DEPS_rustc_back := std syntax rustc_llvm flate log libc
+DEPS_rustc_data_structures := std log serialize
 DEPS_rustdoc := rustc rustc_driver native:hoedown serialize getopts \
                 test rustc_lint
 DEPS_rustc_bitflags := core
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index a4bb17bc354..ab5c4e76966 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -54,6 +54,7 @@ extern crate graphviz;
 extern crate libc;
 extern crate rustc_llvm;
 extern crate rustc_back;
+extern crate rustc_data_structures;
 extern crate serialize;
 extern crate rbml;
 extern crate collections;
@@ -103,7 +104,6 @@ pub mod middle {
     pub mod entry;
     pub mod expr_use_visitor;
     pub mod fast_reject;
-    pub mod graph;
     pub mod intrinsicck;
     pub mod infer;
     pub mod lang_items;
@@ -141,7 +141,6 @@ pub mod util {
     pub mod common;
     pub mod ppaux;
     pub mod nodemap;
-    pub mod snapshot_vec;
     pub mod lev_distance;
 }
 
diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index cbc2ef1535e..359a1a486c9 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -8,9 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use rustc_data_structures::graph;
 use middle::cfg::*;
 use middle::def;
-use middle::graph;
 use middle::pat_util;
 use middle::region::CodeExtent;
 use middle::ty;
diff --git a/src/librustc/middle/cfg/mod.rs b/src/librustc/middle/cfg/mod.rs
index ad4fdcd7b83..3ca221c9630 100644
--- a/src/librustc/middle/cfg/mod.rs
+++ b/src/librustc/middle/cfg/mod.rs
@@ -11,7 +11,7 @@
 //! Module that constructs a control-flow graph representing an item.
 //! Uses `Graph` as the underlying representation.
 
-use middle::graph;
+use rustc_data_structures::graph;
 use middle::ty;
 use syntax::ast;
 
@@ -24,7 +24,7 @@ pub struct CFG {
     pub exit: CFGIndex,
 }
 
-#[derive(Copy, Clone, PartialEq)]
+#[derive(Copy, Clone, Debug, PartialEq)]
 pub enum CFGNodeData {
     AST(ast::NodeId),
     Entry,
@@ -43,6 +43,7 @@ impl CFGNodeData {
     }
 }
 
+#[derive(Debug)]
 pub struct CFGEdgeData {
     pub exiting_scopes: Vec<ast::NodeId>
 }
diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs
index 41b4495c5f0..1d5d4f72fc2 100644
--- a/src/librustc/middle/dataflow.rs
+++ b/src/librustc/middle/dataflow.rs
@@ -576,10 +576,9 @@ impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
                                                pred_bits: &[usize],
                                                cfg: &cfg::CFG,
                                                cfgidx: CFGIndex) {
-        cfg.graph.each_outgoing_edge(cfgidx, |_e_idx, edge| {
+        for (_, edge) in cfg.graph.outgoing_edges(cfgidx) {
             self.propagate_bits_into_entry_set_for(pred_bits, edge);
-            true
-        });
+        }
     }
 
     fn propagate_bits_into_entry_set_for(&mut self,
diff --git a/src/librustc/middle/infer/freshen.rs b/src/librustc/middle/infer/freshen.rs
index 29f74d12ea3..d93d13beec8 100644
--- a/src/librustc/middle/infer/freshen.rs
+++ b/src/librustc/middle/infer/freshen.rs
@@ -37,7 +37,7 @@ use middle::ty_fold::TypeFolder;
 use std::collections::hash_map::{self, Entry};
 
 use super::InferCtxt;
-use super::unify::ToType;
+use super::unify_key::ToType;
 
 pub struct TypeFreshener<'a, 'tcx:'a> {
     infcx: &'a InferCtxt<'a, 'tcx>,
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 0f62b440bf3..b0921a266f3 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -29,6 +29,7 @@ use middle::ty::replace_late_bound_regions;
 use middle::ty::{self, Ty};
 use middle::ty_fold::{TypeFolder, TypeFoldable};
 use middle::ty_relate::{Relate, RelateResult, TypeRelation};
+use rustc_data_structures::unify::{self, UnificationTable};
 use std::cell::{RefCell};
 use std::fmt;
 use std::rc::Rc;
@@ -41,8 +42,8 @@ use util::ppaux::{Repr, UserString};
 
 use self::combine::CombineFields;
 use self::region_inference::{RegionVarBindings, RegionSnapshot};
-use self::unify::{ToType, UnificationTable};
 use self::error_reporting::ErrorReporting;
+use self::unify_key::ToType;
 
 pub mod bivariate;
 pub mod combine;
@@ -57,7 +58,7 @@ pub mod resolve;
 mod freshen;
 pub mod sub;
 pub mod type_variable;
-pub mod unify;
+pub mod unify_key;
 
 pub type Bound<T> = Option<T>;
 pub type UnitResult<'tcx> = RelateResult<'tcx, ()>; // "unify result"
diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index c6be97e6dbe..e76468131e0 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -20,14 +20,13 @@ use self::Classification::*;
 
 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
 
+use rustc_data_structures::graph::{self, Direction, NodeIndex};
 use middle::region;
 use middle::ty::{self, Ty};
 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound};
 use middle::ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh};
 use middle::ty_relate::RelateResult;
-use middle::graph;
-use middle::graph::{Direction, NodeIndex};
 use util::common::indenter;
 use util::nodemap::{FnvHashMap, FnvHashSet};
 use util::ppaux::{Repr, UserString};
@@ -1325,10 +1324,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         let num_vars = self.num_vars();
 
         let constraints = self.constraints.borrow();
-        let num_edges = constraints.len();
 
-        let mut graph = graph::Graph::with_capacity(num_vars as usize + 1,
-                                                    num_edges);
+        let mut graph = graph::Graph::new();
 
         for _ in 0..num_vars {
             graph.add_node(());
@@ -1370,10 +1367,10 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         // not contained by an upper-bound.
         let (mut lower_bounds, lower_dup) =
             self.collect_concrete_regions(graph, var_data, node_idx,
-                                          graph::Incoming, dup_vec);
+                                          graph::INCOMING, dup_vec);
         let (mut upper_bounds, upper_dup) =
             self.collect_concrete_regions(graph, var_data, node_idx,
-                                          graph::Outgoing, dup_vec);
+                                          graph::OUTGOING, dup_vec);
 
         if lower_dup || upper_dup {
             return;
@@ -1433,7 +1430,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         // that have no intersection.
         let (upper_bounds, dup_found) =
             self.collect_concrete_regions(graph, var_data, node_idx,
-                                          graph::Outgoing, dup_vec);
+                                          graph::OUTGOING, dup_vec);
 
         if dup_found {
             return;
@@ -1508,8 +1505,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             // figure out the direction from which this node takes its
             // values, and search for concrete regions etc in that direction
             let dir = match classification {
-                Expanding => graph::Incoming,
-                Contracting => graph::Outgoing,
+                Expanding => graph::INCOMING,
+                Contracting => graph::OUTGOING,
             };
 
             process_edges(self, &mut state, graph, node_idx, dir);
@@ -1519,14 +1516,14 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         return (result, dup_found);
 
         fn process_edges<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
-                         state: &mut WalkState<'tcx>,
-                         graph: &RegionGraph,
-                         source_vid: RegionVid,
-                         dir: Direction) {
+                                   state: &mut WalkState<'tcx>,
+                                   graph: &RegionGraph,
+                                   source_vid: RegionVid,
+                                   dir: Direction) {
             debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
 
             let source_node_index = NodeIndex(source_vid.index as usize);
-            graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
+            for (_, edge) in graph.adjacent_edges(source_node_index, dir) {
                 match edge.data {
                     ConstrainVarSubVar(from_vid, to_vid) => {
                         let opp_vid =
@@ -1544,8 +1541,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                         });
                     }
                 }
-                true
-            });
+            }
         }
     }
 
diff --git a/src/librustc/middle/infer/type_variable.rs b/src/librustc/middle/infer/type_variable.rs
index 03612a6c1ae..b3e3e016d85 100644
--- a/src/librustc/middle/infer/type_variable.rs
+++ b/src/librustc/middle/infer/type_variable.rs
@@ -17,7 +17,7 @@ use std::cmp::min;
 use std::marker::PhantomData;
 use std::mem;
 use std::u32;
-use util::snapshot_vec as sv;
+use rustc_data_structures::snapshot_vec as sv;
 
 pub struct TypeVariableTable<'tcx> {
     values: sv::SnapshotVec<Delegate<'tcx>>,
@@ -65,7 +65,7 @@ impl RelationDir {
 
 impl<'tcx> TypeVariableTable<'tcx> {
     pub fn new() -> TypeVariableTable<'tcx> {
-        TypeVariableTable { values: sv::SnapshotVec::new(Delegate(PhantomData)) }
+        TypeVariableTable { values: sv::SnapshotVec::new() }
     }
 
     fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
@@ -201,9 +201,7 @@ impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
     type Value = TypeVariableData<'tcx>;
     type Undo = UndoEntry;
 
-    fn reverse(&mut self,
-               values: &mut Vec<TypeVariableData<'tcx>>,
-               action: UndoEntry) {
+    fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: UndoEntry) {
         match action {
             SpecifyVar(vid, relations) => {
                 values[vid.index as usize].value = Bounded(relations);
diff --git a/src/librustc/middle/infer/unify_key.rs b/src/librustc/middle/infer/unify_key.rs
new file mode 100644
index 00000000000..6b23e2c5029
--- /dev/null
+++ b/src/librustc/middle/infer/unify_key.rs
@@ -0,0 +1,48 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use middle::ty::{self, IntVarValue, Ty};
+use rustc_data_structures::unify::UnifyKey;
+use syntax::ast;
+
+pub trait ToType<'tcx> {
+    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
+}
+
+impl UnifyKey for ty::IntVid {
+    type Value = Option<IntVarValue>;
+    fn index(&self) -> u32 { self.index }
+    fn from_index(i: u32) -> ty::IntVid { ty::IntVid { index: i } }
+    fn tag(_: Option<ty::IntVid>) -> &'static str { "IntVid" }
+}
+
+impl<'tcx> ToType<'tcx> for IntVarValue {
+    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
+        match *self {
+            ty::IntType(i) => ty::mk_mach_int(tcx, i),
+            ty::UintType(i) => ty::mk_mach_uint(tcx, i),
+        }
+    }
+}
+
+// Floating point type keys
+
+impl UnifyKey for ty::FloatVid {
+    type Value = Option<ast::FloatTy>;
+    fn index(&self) -> u32 { self.index }
+    fn from_index(i: u32) -> ty::FloatVid { ty::FloatVid { index: i } }
+    fn tag(_: Option<ty::FloatVid>) -> &'static str { "FloatVid" }
+}
+
+impl<'tcx> ToType<'tcx> for ast::FloatTy {
+    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
+        ty::mk_mach_float(tcx, *self)
+    }
+}
diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
new file mode 100644
index 00000000000..983601771a0
--- /dev/null
+++ b/src/librustc_data_structures/bitvec.rs
@@ -0,0 +1,42 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::iter;
+
+/// A very simple BitVector type.
+pub struct BitVector {
+    data: Vec<u64>
+}
+
+impl BitVector {
+    pub fn new(num_bits: usize) -> BitVector {
+        let num_words = (num_bits + 63) / 64;
+        BitVector { data: iter::repeat(0).take(num_words).collect() }
+    }
+
+    fn word_mask(&self, bit: usize) -> (usize, u64) {
+        let word = bit / 64;
+        let mask = 1 << (bit % 64);
+        (word, mask)
+    }
+
+    pub fn contains(&self, bit: usize) -> bool {
+        let (word, mask) = self.word_mask(bit);
+        (self.data[word] & mask) != 0
+    }
+
+    pub fn insert(&mut self, bit: usize) -> bool {
+        let (word, mask) = self.word_mask(bit);
+        let data = &mut self.data[word];
+        let value = *data;
+        *data = value | mask;
+        (value | mask) != value
+    }
+}
diff --git a/src/librustc/middle/graph.rs b/src/librustc_data_structures/graph/mod.rs
index a9ac61b49ec..5741544fe54 100644
--- a/src/librustc/middle/graph.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -30,15 +30,17 @@
 //! the field `next_edge`). Each of those fields is an array that should
 //! be indexed by the direction (see the type `Direction`).
 
-#![allow(dead_code)] // still WIP
-
+use bitvec::BitVector;
 use std::fmt::{Formatter, Error, Debug};
 use std::usize;
-use std::collections::BitSet;
+use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
+
+#[cfg(test)]
+mod test;
 
 pub struct Graph<N,E> {
-    nodes: Vec<Node<N>> ,
-    edges: Vec<Edge<E>> ,
+    nodes: SnapshotVec<Node<N>> ,
+    edges: SnapshotVec<Edge<E>> ,
 }
 
 pub struct Node<N> {
@@ -53,6 +55,20 @@ pub struct Edge<E> {
     pub data: E,
 }
 
+impl<N> SnapshotVecDelegate for Node<N> {
+    type Value = Node<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
+}
+
+impl<N> SnapshotVecDelegate for Edge<N> {
+    type Value = Edge<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
+}
+
 impl<E: Debug> Debug for Edge<E> {
     fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
         write!(f, "Edge {{ next_edge: [{:?}, {:?}], source: {:?}, target: {:?}, data: {:?} }}",
@@ -61,49 +77,37 @@ impl<E: Debug> Debug for Edge<E> {
     }
 }
 
-#[derive(Clone, Copy, PartialEq, Debug)]
+#[derive(Copy, Clone, PartialEq, Debug)]
 pub struct NodeIndex(pub usize);
-#[allow(non_upper_case_globals)]
-pub const InvalidNodeIndex: NodeIndex = NodeIndex(usize::MAX);
 
 #[derive(Copy, Clone, PartialEq, Debug)]
 pub struct EdgeIndex(pub usize);
-#[allow(non_upper_case_globals)]
-pub const InvalidEdgeIndex: EdgeIndex = EdgeIndex(usize::MAX);
+
+pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
 
 // Use a private field here to guarantee no more instances are created:
 #[derive(Copy, Clone, Debug)]
 pub struct Direction { repr: usize }
-#[allow(non_upper_case_globals)]
-pub const Outgoing: Direction = Direction { repr: 0 };
-#[allow(non_upper_case_globals)]
-pub const Incoming: Direction = Direction { repr: 1 };
+
+pub const OUTGOING: Direction = Direction { repr: 0 };
+
+pub const INCOMING: Direction = Direction { repr: 1 };
 
 impl NodeIndex {
-    fn get(&self) -> usize { let NodeIndex(v) = *self; v }
     /// Returns unique id (unique with respect to the graph holding associated node).
-    pub fn node_id(&self) -> usize { self.get() }
+    pub fn node_id(&self) -> usize { self.0 }
 }
 
 impl EdgeIndex {
-    fn get(&self) -> usize { let EdgeIndex(v) = *self; v }
     /// Returns unique id (unique with respect to the graph holding associated edge).
-    pub fn edge_id(&self) -> usize { self.get() }
+    pub fn edge_id(&self) -> usize { self.0 }
 }
 
-impl<N,E> Graph<N,E> {
+impl<N:Debug,E:Debug> Graph<N,E> {
     pub fn new() -> Graph<N,E> {
         Graph {
-            nodes: Vec::new(),
-            edges: Vec::new(),
-        }
-    }
-
-    pub fn with_capacity(num_nodes: usize,
-                         num_edges: usize) -> Graph<N,E> {
-        Graph {
-            nodes: Vec::with_capacity(num_nodes),
-            edges: Vec::with_capacity(num_edges),
+            nodes: SnapshotVec::new(),
+            edges: SnapshotVec::new(),
         }
     }
 
@@ -130,22 +134,22 @@ impl<N,E> Graph<N,E> {
     pub fn add_node(&mut self, data: N) -> NodeIndex {
         let idx = self.next_node_index();
         self.nodes.push(Node {
-            first_edge: [InvalidEdgeIndex, InvalidEdgeIndex],
+            first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
             data: data
         });
         idx
     }
 
     pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
-        &mut self.nodes[idx.get()].data
+        &mut self.nodes[idx.0].data
     }
 
     pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
-        &self.nodes[idx.get()].data
+        &self.nodes[idx.0].data
     }
 
     pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
-        &self.nodes[idx.get()]
+        &self.nodes[idx.0]
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -159,13 +163,15 @@ impl<N,E> Graph<N,E> {
                     source: NodeIndex,
                     target: NodeIndex,
                     data: E) -> EdgeIndex {
+        debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
+
         let idx = self.next_edge_index();
 
         // read current first of the list of edges from each node
-        let source_first = self.nodes[source.get()]
-                                     .first_edge[Outgoing.repr];
-        let target_first = self.nodes[target.get()]
-                                     .first_edge[Incoming.repr];
+        let source_first = self.nodes[source.0]
+                                     .first_edge[OUTGOING.repr];
+        let target_first = self.nodes[target.0]
+                                     .first_edge[INCOMING.repr];
 
         // create the new edge, with the previous firsts from each node
         // as the next pointers
@@ -177,22 +183,22 @@ impl<N,E> Graph<N,E> {
         });
 
         // adjust the firsts for each node target be the next object.
-        self.nodes[source.get()].first_edge[Outgoing.repr] = idx;
-        self.nodes[target.get()].first_edge[Incoming.repr] = idx;
+        self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
+        self.nodes[target.0].first_edge[INCOMING.repr] = idx;
 
         return idx;
     }
 
     pub fn mut_edge_data<'a>(&'a mut self, idx: EdgeIndex) -> &'a mut E {
-        &mut self.edges[idx.get()].data
+        &mut self.edges[idx.0].data
     }
 
     pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
-        &self.edges[idx.get()].data
+        &self.edges[idx.0].data
     }
 
     pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
-        &self.edges[idx.get()]
+        &self.edges[idx.0]
     }
 
     pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
@@ -200,7 +206,7 @@ impl<N,E> Graph<N,E> {
         //! This is useful if you wish to modify the graph while walking
         //! the linked list of edges.
 
-        self.nodes[node.get()].first_edge[dir.repr]
+        self.nodes[node.0].first_edge[dir.repr]
     }
 
     pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
@@ -208,7 +214,7 @@ impl<N,E> Graph<N,E> {
         //! This is useful if you wish to modify the graph while walking
         //! the linked list of edges.
 
-        self.edges[edge.get()].next_edge[dir.repr]
+        self.edges[edge.0].next_edge[dir.repr]
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -228,41 +234,25 @@ impl<N,E> Graph<N,E> {
         self.edges.iter().enumerate().all(|(i, edge)| f(EdgeIndex(i), edge))
     }
 
-    pub fn each_outgoing_edge<'a, F>(&'a self, source: NodeIndex, f: F) -> bool where
-        F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
-    {
-        //! Iterates over all outgoing edges from the node `from`
+    pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
+        self.adjacent_edges(source, OUTGOING)
+    }
 
-        self.each_adjacent_edge(source, Outgoing, f)
+    pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N,E> {
+        self.adjacent_edges(source, INCOMING)
     }
 
-    pub fn each_incoming_edge<'a, F>(&'a self, target: NodeIndex, f: F) -> bool where
-        F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
-    {
-        //! Iterates over all incoming edges to the node `target`
+    pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N,E> {
+        let first_edge = self.node(source).first_edge[direction.repr];
+        AdjacentEdges { graph: self, direction: direction, next: first_edge }
+    }
 
-        self.each_adjacent_edge(target, Incoming, f)
+    pub fn successor_nodes<'a>(&'a self, source: NodeIndex) -> AdjacentTargets<N,E> {
+        self.outgoing_edges(source).targets()
     }
 
-    pub fn each_adjacent_edge<'a, F>(&'a self,
-                                     node: NodeIndex,
-                                     dir: Direction,
-                                     mut f: F)
-                                     -> bool where
-        F: FnMut(EdgeIndex, &'a Edge<E>) -> bool,
-    {
-        //! Iterates over all edges adjacent to the node `node`
-        //! in the direction `dir` (either `Outgoing` or `Incoming)
-
-        let mut edge_idx = self.first_adjacent(node, dir);
-        while edge_idx != InvalidEdgeIndex {
-            let edge = &self.edges[edge_idx.get()];
-            if !f(edge_idx, edge) {
-                return false;
-            }
-            edge_idx = edge.next_edge[dir.repr];
-        }
-        return true;
+    pub fn predecessor_nodes<'a>(&'a self, target: NodeIndex) -> AdjacentSources<N,E> {
+        self.incoming_edges(target).sources()
     }
 
     ///////////////////////////////////////////////////////////////////////////
@@ -292,18 +282,82 @@ impl<N,E> Graph<N,E> {
         DepthFirstTraversal {
             graph: self,
             stack: vec![start],
-            visited: BitSet::new()
+            visited: BitVector::new(self.nodes.len()),
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Iterators
+
+pub struct AdjacentEdges<'g,N,E>
+    where N:'g, E:'g
+{
+    graph: &'g Graph<N, E>,
+    direction: Direction,
+    next: EdgeIndex,
+}
+
+impl<'g,N,E> AdjacentEdges<'g,N,E> {
+    fn targets(self) -> AdjacentTargets<'g,N,E> {
+        AdjacentTargets { edges: self }
+    }
+
+    fn sources(self) -> AdjacentSources<'g,N,E> {
+        AdjacentSources { edges: self }
+    }
+}
+
+impl<'g, N:Debug, E:Debug> Iterator for AdjacentEdges<'g, N, E> {
+    type Item = (EdgeIndex, &'g Edge<E>);
+
+    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
+        let edge_index = self.next;
+        if edge_index == INVALID_EDGE_INDEX {
+            return None;
         }
+
+        let edge = self.graph.edge(edge_index);
+        self.next = edge.next_edge[self.direction.repr];
+        Some((edge_index, edge))
+    }
+}
+
+pub struct AdjacentTargets<'g,N:'g,E:'g>
+    where N:'g, E:'g
+{
+    edges: AdjacentEdges<'g,N,E>,
+}
+
+impl<'g, N:Debug, E:Debug> Iterator for AdjacentTargets<'g, N, E> {
+    type Item = NodeIndex;
+
+    fn next(&mut self) -> Option<NodeIndex> {
+        self.edges.next().map(|(_, edge)| edge.target)
+    }
+}
+
+pub struct AdjacentSources<'g,N:'g,E:'g>
+    where N:'g, E:'g
+{
+    edges: AdjacentEdges<'g,N,E>,
+}
+
+impl<'g, N:Debug, E:Debug> Iterator for AdjacentSources<'g, N, E> {
+    type Item = NodeIndex;
+
+    fn next(&mut self) -> Option<NodeIndex> {
+        self.edges.next().map(|(_, edge)| edge.source)
     }
 }
 
 pub struct DepthFirstTraversal<'g, N:'g, E:'g> {
     graph: &'g Graph<N, E>,
     stack: Vec<NodeIndex>,
-    visited: BitSet
+    visited: BitVector
 }
 
-impl<'g, N, E> Iterator for DepthFirstTraversal<'g, N, E> {
+impl<'g, N:Debug, E:Debug> Iterator for DepthFirstTraversal<'g, N, E> {
     type Item = &'g N;
 
     fn next(&mut self) -> Option<&'g N> {
@@ -311,12 +365,12 @@ impl<'g, N, E> Iterator for DepthFirstTraversal<'g, N, E> {
             if !self.visited.insert(idx.node_id()) {
                 continue;
             }
-            self.graph.each_outgoing_edge(idx, |_, e| -> bool {
-                if !self.visited.contains(&e.target().node_id()) {
-                    self.stack.push(e.target());
+
+            for (_, edge) in self.graph.outgoing_edges(idx) {
+                if !self.visited.contains(edge.target().node_id()) {
+                    self.stack.push(edge.target());
                 }
-                true
-            });
+            }
 
             return Some(self.graph.node_data(idx));
         }
@@ -329,7 +383,7 @@ pub fn each_edge_index<F>(max_edge_index: EdgeIndex, mut f: F) where
     F: FnMut(EdgeIndex) -> bool,
 {
     let mut i = 0;
-    let n = max_edge_index.get();
+    let n = max_edge_index.0;
     while i < n {
         if !f(EdgeIndex(i)) {
             return;
@@ -347,138 +401,3 @@ impl<E> Edge<E> {
         self.target
     }
 }
-
-#[cfg(test)]
-mod test {
-    use middle::graph::*;
-    use std::fmt::Debug;
-
-    type TestNode = Node<&'static str>;
-    type TestEdge = Edge<&'static str>;
-    type TestGraph = Graph<&'static str, &'static str>;
-
-    fn create_graph() -> TestGraph {
-        let mut graph = Graph::new();
-
-        // Create a simple graph
-        //
-        //    A -+> B --> C
-        //       |  |     ^
-        //       |  v     |
-        //       F  D --> E
-
-        let a = graph.add_node("A");
-        let b = graph.add_node("B");
-        let c = graph.add_node("C");
-        let d = graph.add_node("D");
-        let e = graph.add_node("E");
-        let f = graph.add_node("F");
-
-        graph.add_edge(a, b, "AB");
-        graph.add_edge(b, c, "BC");
-        graph.add_edge(b, d, "BD");
-        graph.add_edge(d, e, "DE");
-        graph.add_edge(e, c, "EC");
-        graph.add_edge(f, b, "FB");
-
-        return graph;
-    }
-
-    #[test]
-    fn each_node() {
-        let graph = create_graph();
-        let expected = ["A", "B", "C", "D", "E", "F"];
-        graph.each_node(|idx, node| {
-            assert_eq!(&expected[idx.get()], graph.node_data(idx));
-            assert_eq!(expected[idx.get()], node.data);
-            true
-        });
-    }
-
-    #[test]
-    fn each_edge() {
-        let graph = create_graph();
-        let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
-        graph.each_edge(|idx, edge| {
-            assert_eq!(&expected[idx.get()], graph.edge_data(idx));
-            assert_eq!(expected[idx.get()], edge.data);
-            true
-        });
-    }
-
-    fn test_adjacent_edges<N:PartialEq+Debug,E:PartialEq+Debug>(graph: &Graph<N,E>,
-                                      start_index: NodeIndex,
-                                      start_data: N,
-                                      expected_incoming: &[(E,N)],
-                                      expected_outgoing: &[(E,N)]) {
-        assert!(graph.node_data(start_index) == &start_data);
-
-        let mut counter = 0;
-        graph.each_incoming_edge(start_index, |edge_index, edge| {
-            assert!(graph.edge_data(edge_index) == &edge.data);
-            assert!(counter < expected_incoming.len());
-            debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
-                   counter, expected_incoming[counter], edge_index, edge);
-            match expected_incoming[counter] {
-                (ref e, ref n) => {
-                    assert!(e == &edge.data);
-                    assert!(n == graph.node_data(edge.source));
-                    assert!(start_index == edge.target);
-                }
-            }
-            counter += 1;
-            true
-        });
-        assert_eq!(counter, expected_incoming.len());
-
-        let mut counter = 0;
-        graph.each_outgoing_edge(start_index, |edge_index, edge| {
-            assert!(graph.edge_data(edge_index) == &edge.data);
-            assert!(counter < expected_outgoing.len());
-            debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
-                   counter, expected_outgoing[counter], edge_index, edge);
-            match expected_outgoing[counter] {
-                (ref e, ref n) => {
-                    assert!(e == &edge.data);
-                    assert!(start_index == edge.source);
-                    assert!(n == graph.node_data(edge.target));
-                }
-            }
-            counter += 1;
-            true
-        });
-        assert_eq!(counter, expected_outgoing.len());
-    }
-
-    #[test]
-    fn each_adjacent_from_a() {
-        let graph = create_graph();
-        test_adjacent_edges(&graph, NodeIndex(0), "A",
-                            &[],
-                            &[("AB", "B")]);
-    }
-
-    #[test]
-    fn each_adjacent_from_b() {
-        let graph = create_graph();
-        test_adjacent_edges(&graph, NodeIndex(1), "B",
-                            &[("FB", "F"), ("AB", "A"),],
-                            &[("BD", "D"), ("BC", "C"),]);
-    }
-
-    #[test]
-    fn each_adjacent_from_c() {
-        let graph = create_graph();
-        test_adjacent_edges(&graph, NodeIndex(2), "C",
-                            &[("EC", "E"), ("BC", "B")],
-                            &[]);
-    }
-
-    #[test]
-    fn each_adjacent_from_d() {
-        let graph = create_graph();
-        test_adjacent_edges(&graph, NodeIndex(3), "D",
-                            &[("BD", "B")],
-                            &[("DE", "E")]);
-    }
-}
diff --git a/src/librustc_data_structures/graph/test.rs b/src/librustc_data_structures/graph/test.rs
new file mode 100644
index 00000000000..33b2edd2e10
--- /dev/null
+++ b/src/librustc_data_structures/graph/test.rs
@@ -0,0 +1,139 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use graph::*;
+use std::fmt::Debug;
+
+type TestNode = Node<&'static str>;
+type TestEdge = Edge<&'static str>;
+type TestGraph = Graph<&'static str, &'static str>;
+
+fn create_graph() -> TestGraph {
+    let mut graph = Graph::new();
+
+    // Create a simple graph
+    //
+    //    A -+> B --> C
+    //       |  |     ^
+    //       |  v     |
+    //       F  D --> E
+
+    let a = graph.add_node("A");
+    let b = graph.add_node("B");
+    let c = graph.add_node("C");
+    let d = graph.add_node("D");
+    let e = graph.add_node("E");
+    let f = graph.add_node("F");
+
+    graph.add_edge(a, b, "AB");
+    graph.add_edge(b, c, "BC");
+    graph.add_edge(b, d, "BD");
+    graph.add_edge(d, e, "DE");
+    graph.add_edge(e, c, "EC");
+    graph.add_edge(f, b, "FB");
+
+    return graph;
+}
+
+#[test]
+fn each_node() {
+    let graph = create_graph();
+    let expected = ["A", "B", "C", "D", "E", "F"];
+    graph.each_node(|idx, node| {
+        assert_eq!(&expected[idx.0], graph.node_data(idx));
+        assert_eq!(expected[idx.0], node.data);
+        true
+    });
+}
+
+#[test]
+fn each_edge() {
+    let graph = create_graph();
+    let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
+    graph.each_edge(|idx, edge| {
+        assert_eq!(&expected[idx.0], graph.edge_data(idx));
+        assert_eq!(expected[idx.0], edge.data);
+        true
+    });
+}
+
+fn test_adjacent_edges<N:PartialEq+Debug,E:PartialEq+Debug>(graph: &Graph<N,E>,
+                                                            start_index: NodeIndex,
+                                                            start_data: N,
+                                                            expected_incoming: &[(E,N)],
+                                                            expected_outgoing: &[(E,N)]) {
+    assert!(graph.node_data(start_index) == &start_data);
+
+    let mut counter = 0;
+    for (edge_index, edge) in graph.incoming_edges(start_index) {
+        assert!(graph.edge_data(edge_index) == &edge.data);
+        assert!(counter < expected_incoming.len());
+        debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
+               counter, expected_incoming[counter], edge_index, edge);
+        match expected_incoming[counter] {
+            (ref e, ref n) => {
+                assert!(e == &edge.data);
+                assert!(n == graph.node_data(edge.source()));
+                assert!(start_index == edge.target);
+            }
+        }
+        counter += 1;
+    }
+    assert_eq!(counter, expected_incoming.len());
+
+    let mut counter = 0;
+    for (edge_index, edge) in graph.outgoing_edges(start_index) {
+        assert!(graph.edge_data(edge_index) == &edge.data);
+        assert!(counter < expected_outgoing.len());
+        debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
+               counter, expected_outgoing[counter], edge_index, edge);
+        match expected_outgoing[counter] {
+            (ref e, ref n) => {
+                assert!(e == &edge.data);
+                assert!(start_index == edge.source);
+                assert!(n == graph.node_data(edge.target));
+            }
+        }
+        counter += 1;
+    }
+    assert_eq!(counter, expected_outgoing.len());
+}
+
+#[test]
+fn each_adjacent_from_a() {
+    let graph = create_graph();
+    test_adjacent_edges(&graph, NodeIndex(0), "A",
+                        &[],
+                        &[("AB", "B")]);
+}
+
+#[test]
+fn each_adjacent_from_b() {
+    let graph = create_graph();
+    test_adjacent_edges(&graph, NodeIndex(1), "B",
+                        &[("FB", "F"), ("AB", "A"),],
+                        &[("BD", "D"), ("BC", "C"),]);
+}
+
+#[test]
+fn each_adjacent_from_c() {
+    let graph = create_graph();
+    test_adjacent_edges(&graph, NodeIndex(2), "C",
+                        &[("EC", "E"), ("BC", "B")],
+                        &[]);
+}
+
+#[test]
+fn each_adjacent_from_d() {
+    let graph = create_graph();
+    test_adjacent_edges(&graph, NodeIndex(3), "D",
+                        &[("BD", "B")],
+                        &[("DE", "E")]);
+}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
new file mode 100644
index 00000000000..dc376deebc1
--- /dev/null
+++ b/src/librustc_data_structures/lib.rs
@@ -0,0 +1,38 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Various data structures used by the Rust compiler. The intention
+//! is that code in here should be not be *specific* to rustc, so that
+//! it can be easily unit tested and so forth.
+//!
+//! # Note
+//!
+//! This API is completely unstable and subject to change.
+
+// Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364)
+#![cfg_attr(stage0, feature(custom_attribute))]
+#![crate_name = "rustc_data_structures"]
+#![unstable(feature = "rustc_private")]
+#![crate_type = "dylib"]
+#![crate_type = "rlib"]
+#![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
+      html_favicon_url = "http://www.rust-lang.org/favicon.ico",
+      html_root_url = "http://doc.rust-lang.org/nightly/")]
+
+#![feature(rustc_private)]
+#![cfg_attr(test, feature(test))]
+
+#[macro_use] extern crate log;
+extern crate serialize as rustc_serialize; // used by deriving
+
+pub mod snapshot_vec;
+pub mod graph;
+pub mod bitvec;
+pub mod unify;
diff --git a/src/librustc/util/snapshot_vec.rs b/src/librustc_data_structures/snapshot_vec.rs
index d2e0b3aec2f..5ab740f3629 100644
--- a/src/librustc/util/snapshot_vec.rs
+++ b/src/librustc_data_structures/snapshot_vec.rs
@@ -21,6 +21,7 @@
 use self::UndoLog::*;
 
 use std::mem;
+use std::ops;
 
 pub enum UndoLog<D:SnapshotVecDelegate> {
     /// Indicates where a snapshot started.
@@ -42,7 +43,6 @@ pub enum UndoLog<D:SnapshotVecDelegate> {
 pub struct SnapshotVec<D:SnapshotVecDelegate> {
     values: Vec<D::Value>,
     undo_log: Vec<UndoLog<D>>,
-    delegate: D
 }
 
 // Snapshots are tokens that should be created/consumed linearly.
@@ -55,15 +55,14 @@ pub trait SnapshotVecDelegate {
     type Value;
     type Undo;
 
-    fn reverse(&mut self, values: &mut Vec<Self::Value>, action: Self::Undo);
+    fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
 }
 
 impl<D:SnapshotVecDelegate> SnapshotVec<D> {
-    pub fn new(delegate: D) -> SnapshotVec<D> {
+    pub fn new() -> SnapshotVec<D> {
         SnapshotVec {
             values: Vec::new(),
             undo_log: Vec::new(),
-            delegate: delegate
         }
     }
 
@@ -77,6 +76,10 @@ impl<D:SnapshotVecDelegate> SnapshotVec<D> {
         }
     }
 
+    pub fn len(&self) -> usize {
+        self.values.len()
+    }
+
     pub fn push(&mut self, elem: D::Value) -> usize {
         let len = self.values.len();
         self.values.push(elem);
@@ -159,7 +162,7 @@ impl<D:SnapshotVecDelegate> SnapshotVec<D> {
                 }
 
                 Other(u) => {
-                    self.delegate.reverse(&mut self.values, u);
+                    D::reverse(&mut self.values, u);
                 }
             }
         }
@@ -184,3 +187,21 @@ impl<D:SnapshotVecDelegate> SnapshotVec<D> {
         }
     }
 }
+
+impl<D:SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
+    type Target = [D::Value];
+    fn deref(&self) -> &[D::Value] { &*self.values }
+}
+
+impl<D:SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
+    fn deref_mut(&mut self) -> &mut [D::Value] { &mut *self.values }
+}
+
+impl<D:SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
+    type Output = D::Value;
+    fn index(&self, index: usize) -> &D::Value { self.get(index) }
+}
+
+impl<D:SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
+    fn index_mut(&mut self, index: usize) -> &mut D::Value { self.get_mut(index) }
+}
diff --git a/src/librustc/middle/infer/unify.rs b/src/librustc_data_structures/unify/mod.rs
index 4bbced1d75c..7036c010c65 100644
--- a/src/librustc/middle/infer/unify.rs
+++ b/src/librustc_data_structures/unify/mod.rs
@@ -8,16 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-pub use self::VarValue::*;
-
 use std::marker;
-
-use middle::ty::{IntVarValue};
-use middle::ty::{self, Ty};
 use std::fmt::Debug;
 use std::marker::PhantomData;
-use syntax::ast;
-use util::snapshot_vec as sv;
+use snapshot_vec as sv;
+
+#[cfg(test)]
+mod test;
 
 /// This trait is implemented by any type that can serve as a type
 /// variable. We call such variables *unification keys*. For example,
@@ -28,9 +25,10 @@ use util::snapshot_vec as sv;
 /// `IntVid`, this is `Option<IntVarValue>`, representing some
 /// (possibly not yet known) sort of integer.
 ///
-/// Implementations of this trait are at the end of this file.
-pub trait UnifyKey : Clone + Debug + PartialEq {
-    type Value : UnifyValue;
+/// Clients are expected to provide implementations of this trait; you
+/// can see some examples in the `test` module.
+pub trait UnifyKey : Copy + Clone + Debug + PartialEq {
+    type Value: Clone + PartialEq + Debug;
 
     fn index(&self) -> u32;
 
@@ -39,15 +37,6 @@ pub trait UnifyKey : Clone + Debug + PartialEq {
     fn tag(k: Option<Self>) -> &'static str;
 }
 
-/// Trait for valid types that a type variable can be set to. Note that
-/// this is typically not the end type that the value will take on, but
-/// rather an `Option` wrapper (where `None` represents a variable
-/// whose value is not yet set).
-///
-/// Implementations of this trait are at the end of this file.
-pub trait UnifyValue : Clone + PartialEq + Debug {
-}
-
 /// Value of a unification key. We implement Tarjan's union-find
 /// algorithm: when two keys are unified, one of them is converted
 /// into a "redirect" pointing at the other. These redirects form a
@@ -57,9 +46,10 @@ pub trait UnifyValue : Clone + PartialEq + Debug {
 /// time of the algorithm under control. For more information, see
 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
 #[derive(PartialEq,Clone,Debug)]
-pub enum VarValue<K:UnifyKey> {
-    Redirect(K),
-    Root(K::Value, usize),
+pub struct VarValue<K:UnifyKey> {
+    parent: K,       // if equal to self, this is a root
+    value: K::Value, // value assigned (only relevant to root)
+    rank: u32,       // max depth (only relevant to root)
 }
 
 /// Table of unification keys and their values.
@@ -76,16 +66,46 @@ pub struct Snapshot<K:UnifyKey> {
     snapshot: sv::Snapshot,
 }
 
-/// Internal type used to represent the result of a `get()` operation.
-/// Conveys the current root and value of the key.
-pub struct Node<K:UnifyKey> {
-    pub key: K,
-    pub value: K::Value,
-    pub rank: usize,
-}
-
 #[derive(Copy, Clone)]
-pub struct Delegate<K>(PhantomData<K>);
+struct Delegate<K>(PhantomData<K>);
+
+impl<K:UnifyKey> VarValue<K> {
+    fn new_var(key: K, value: K::Value) -> VarValue<K> {
+        VarValue::new(key, value, 0)
+    }
+
+    fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> {
+        VarValue { parent: parent, // this is a root
+                   value: value,
+                   rank: rank }
+    }
+
+    fn redirect(self, to: K) -> VarValue<K> {
+        VarValue { parent: to, ..self }
+    }
+
+    fn root(self, rank: u32, value: K::Value) -> VarValue<K> {
+        VarValue { rank: rank, value: value, ..self }
+    }
+
+    /// Returns the key of this node. Only valid if this is a root
+    /// node, which you yourself must ensure.
+    fn key(&self) -> K {
+        self.parent
+    }
+
+    fn parent(&self, self_key: K) -> Option<K> {
+        self.if_not_self(self.parent, self_key)
+    }
+
+    fn if_not_self(&self, key: K, self_key: K) -> Option<K> {
+        if key == self_key {
+            None
+        } else {
+            Some(key)
+        }
+    }
+}
 
 // We can't use V:LatticeValue, much as I would like to,
 // because frequently the pattern is that V=Option<U> for some
@@ -95,7 +115,7 @@ pub struct Delegate<K>(PhantomData<K>);
 impl<K:UnifyKey> UnificationTable<K> {
     pub fn new() -> UnificationTable<K> {
         UnificationTable {
-            values: sv::SnapshotVec::new(Delegate(PhantomData)),
+            values: sv::SnapshotVec::new()
         }
     }
 
@@ -121,12 +141,13 @@ impl<K:UnifyKey> UnificationTable<K> {
     }
 
     pub fn new_key(&mut self, value: K::Value) -> K {
-        let index = self.values.push(Root(value, 0));
-        let k = UnifyKey::from_index(index as u32);
+        let len = self.values.len();
+        let key: K = UnifyKey::from_index(len as u32);
+        self.values.push(VarValue::new_var(key, value));
         debug!("{}: created new key: {:?}",
                UnifyKey::tag(None::<K>),
-               k);
-        k
+               key);
+        key
     }
 
     /// Find the root node for `vid`. This uses the standard
@@ -135,36 +156,34 @@ impl<K:UnifyKey> UnificationTable<K> {
     ///
     /// NB. This is a building-block operation and you would probably
     /// prefer to call `probe` below.
-    fn get(&mut self, vid: K) -> Node<K> {
+    fn get(&mut self, vid: K) -> VarValue<K> {
         let index = vid.index() as usize;
-        let value = (*self.values.get(index)).clone();
-        match value {
-            Redirect(redirect) => {
-                let node: Node<K> = self.get(redirect.clone());
-                if node.key != redirect {
+        let mut value: VarValue<K> = self.values.get(index).clone();
+        match value.parent(vid) {
+            Some(redirect) => {
+                let root: VarValue<K> = self.get(redirect);
+                if root.key() != redirect {
                     // Path compression
-                    self.values.set(index, Redirect(node.key.clone()));
+                    value.parent = root.key();
+                    self.values.set(index, value);
                 }
-                node
+                root
             }
-            Root(value, rank) => {
-                Node { key: vid, value: value, rank: rank }
+            None => {
+                value
             }
         }
     }
 
-    fn is_root(&self, key: &K) -> bool {
+    fn is_root(&self, key: K) -> bool {
         let index = key.index() as usize;
-        match *self.values.get(index) {
-            Redirect(..) => false,
-            Root(..) => true,
-        }
+        self.values.get(index).parent(key).is_none()
     }
 
     /// Sets the value for `vid` to `new_value`. `vid` MUST be a root
     /// node! This is an internal operation used to impl other things.
     fn set(&mut self, key: K, new_value: VarValue<K>) {
-        assert!(self.is_root(&key));
+        assert!(self.is_root(key));
 
         debug!("Updating variable {:?} to {:?}",
                key, new_value);
@@ -181,31 +200,36 @@ impl<K:UnifyKey> UnificationTable<K> {
     /// really more of a building block. If the values associated with
     /// your key are non-trivial, you would probably prefer to call
     /// `unify_var_var` below.
-    fn unify(&mut self, node_a: &Node<K>, node_b: &Node<K>, new_value: K::Value) {
-        debug!("unify(node_a(id={:?}, rank={:?}), node_b(id={:?}, rank={:?}))",
-               node_a.key,
-               node_a.rank,
-               node_b.key,
-               node_b.rank);
-
-        let (new_root, new_rank) = if node_a.rank > node_b.rank {
+    fn unify(&mut self, root_a: VarValue<K>, root_b: VarValue<K>, new_value: K::Value) {
+        debug!("unify(root_a(id={:?}, rank={:?}), root_b(id={:?}, rank={:?}))",
+               root_a.key(),
+               root_a.rank,
+               root_b.key(),
+               root_b.rank);
+
+        if root_a.rank > root_b.rank {
             // a has greater rank, so a should become b's parent,
             // i.e., b should redirect to a.
-            self.set(node_b.key.clone(), Redirect(node_a.key.clone()));
-            (node_a.key.clone(), node_a.rank)
-        } else if node_a.rank < node_b.rank {
+            self.redirect_root(root_a.rank, root_b, root_a, new_value);
+        } else if root_a.rank < root_b.rank {
             // b has greater rank, so a should redirect to b.
-            self.set(node_a.key.clone(), Redirect(node_b.key.clone()));
-            (node_b.key.clone(), node_b.rank)
+            self.redirect_root(root_b.rank, root_a, root_b, new_value);
         } else {
             // If equal, redirect one to the other and increment the
             // other's rank.
-            assert_eq!(node_a.rank, node_b.rank);
-            self.set(node_b.key.clone(), Redirect(node_a.key.clone()));
-            (node_a.key.clone(), node_a.rank + 1)
-        };
+            self.redirect_root(root_a.rank + 1, root_a, root_b, new_value);
+        }
+    }
 
-        self.set(new_root, Root(new_value, new_rank));
+    fn redirect_root(&mut self,
+                     new_rank: u32,
+                     old_root: VarValue<K>,
+                     new_root: VarValue<K>,
+                     new_value: K::Value) {
+        let old_root_key = old_root.key();
+        let new_root_key = new_root.key();
+        self.set(old_root_key, old_root.redirect(new_root_key));
+        self.set(new_root_key, new_root.root(new_rank, new_value));
     }
 }
 
@@ -213,8 +237,31 @@ impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
     type Value = VarValue<K>;
     type Undo = ();
 
-    fn reverse(&mut self, _: &mut Vec<VarValue<K>>, _: ()) {
-        panic!("Nothing to reverse");
+    fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Base union-find algorithm, where we are just making sets
+
+impl<'tcx,K> UnificationTable<K>
+    where K : UnifyKey<Value=()>,
+{
+    pub fn union(&mut self, a_id: K, b_id: K) {
+        let node_a = self.get(a_id);
+        let node_b = self.get(b_id);
+        let a_id = node_a.key();
+        let b_id = node_b.key();
+        if a_id != b_id {
+            self.unify(node_a, node_b, ());
+        }
+    }
+
+    pub fn find(&mut self, id: K) -> K {
+        self.get(id).key()
+    }
+
+    pub fn unioned(&mut self, a_id: K, b_id: K) -> bool {
+        self.find(a_id) == self.find(b_id)
     }
 }
 
@@ -226,7 +273,6 @@ impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
 impl<'tcx,K,V> UnificationTable<K>
     where K: UnifyKey<Value=Option<V>>,
           V: Clone+PartialEq,
-          Option<V>: UnifyValue,
 {
     pub fn unify_var_var(&mut self,
                          a_id: K,
@@ -235,8 +281,8 @@ impl<'tcx,K,V> UnificationTable<K>
     {
         let node_a = self.get(a_id);
         let node_b = self.get(b_id);
-        let a_id = node_a.key.clone();
-        let b_id = node_b.key.clone();
+        let a_id = node_a.key();
+        let b_id = node_b.key();
 
         if a_id == b_id { return Ok(()); }
 
@@ -257,7 +303,7 @@ impl<'tcx,K,V> UnificationTable<K>
             }
         };
 
-        Ok(self.unify(&node_a, &node_b, combined))
+        Ok(self.unify(node_a, node_b, combined))
     }
 
     /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
@@ -267,12 +313,12 @@ impl<'tcx,K,V> UnificationTable<K>
                            b: V)
                            -> Result<(),(V,V)>
     {
-        let node_a = self.get(a_id);
-        let a_id = node_a.key.clone();
+        let mut node_a = self.get(a_id);
 
         match node_a.value {
             None => {
-                self.set(a_id, Root(Some(b), node_a.rank));
+                node_a.value = Some(b);
+                self.set(node_a.key(), node_a);
                 Ok(())
             }
 
@@ -295,46 +341,3 @@ impl<'tcx,K,V> UnificationTable<K>
     }
 }
 
-///////////////////////////////////////////////////////////////////////////
-
-// Integral type keys
-
-pub trait ToType<'tcx> {
-    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
-}
-
-impl UnifyKey for ty::IntVid {
-    type Value = Option<IntVarValue>;
-    fn index(&self) -> u32 { self.index }
-    fn from_index(i: u32) -> ty::IntVid { ty::IntVid { index: i } }
-    fn tag(_: Option<ty::IntVid>) -> &'static str { "IntVid" }
-}
-
-impl<'tcx> ToType<'tcx> for IntVarValue {
-    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
-        match *self {
-            ty::IntType(i) => ty::mk_mach_int(tcx, i),
-            ty::UintType(i) => ty::mk_mach_uint(tcx, i),
-        }
-    }
-}
-
-impl UnifyValue for Option<IntVarValue> { }
-
-// Floating point type keys
-
-impl UnifyKey for ty::FloatVid {
-    type Value = Option<ast::FloatTy>;
-    fn index(&self) -> u32 { self.index }
-    fn from_index(i: u32) -> ty::FloatVid { ty::FloatVid { index: i } }
-    fn tag(_: Option<ty::FloatVid>) -> &'static str { "FloatVid" }
-}
-
-impl UnifyValue for Option<ast::FloatTy> {
-}
-
-impl<'tcx> ToType<'tcx> for ast::FloatTy {
-    fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
-        ty::mk_mach_float(tcx, *self)
-    }
-}
diff --git a/src/librustc_data_structures/unify/test.rs b/src/librustc_data_structures/unify/test.rs
new file mode 100644
index 00000000000..dbe3cfc7a48
--- /dev/null
+++ b/src/librustc_data_structures/unify/test.rs
@@ -0,0 +1,195 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![allow(non_snake_case)]
+
+extern crate test;
+use self::test::Bencher;
+use std::collections::HashSet;
+use unify::{UnifyKey, UnificationTable};
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct UnitKey(u32);
+
+impl UnifyKey for UnitKey {
+    type Value = ();
+    fn index(&self) -> u32 { self.0 }
+    fn from_index(u: u32) -> UnitKey { UnitKey(u) }
+    fn tag(_: Option<UnitKey>) -> &'static str { "UnitKey" }
+}
+
+#[test]
+fn basic() {
+    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
+    let k1 = ut.new_key(());
+    let k2 = ut.new_key(());
+    assert_eq!(ut.unioned(k1, k2), false);
+    ut.union(k1, k2);
+    assert_eq!(ut.unioned(k1, k2), true);
+}
+
+#[test]
+fn big_array() {
+    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 15;
+
+    for _ in 0..MAX {
+        keys.push(ut.new_key(()));
+    }
+
+    for i in 1..MAX {
+        let l = keys[i-1];
+        let r = keys[i];
+        ut.union(l, r);
+    }
+
+    for i in 0..MAX {
+        assert!(ut.unioned(keys[0], keys[i]));
+    }
+}
+
+#[bench]
+fn big_array_bench(b: &mut Bencher) {
+    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 15;
+
+    for _ in 0..MAX {
+        keys.push(ut.new_key(()));
+    }
+
+
+    b.iter(|| {
+        for i in 1..MAX {
+            let l = keys[i-1];
+            let r = keys[i];
+            ut.union(l, r);
+        }
+
+        for i in 0..MAX {
+            assert!(ut.unioned(keys[0], keys[i]));
+        }
+    })
+}
+
+#[test]
+fn even_odd() {
+    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
+    let mut keys = Vec::new();
+    const MAX: usize = 1 << 10;
+
+    for i in 0..MAX {
+        let key = ut.new_key(());
+        keys.push(key);
+
+        if i >= 2 {
+            ut.union(key, keys[i-2]);
+        }
+    }
+
+    for i in 1..MAX {
+        assert!(!ut.unioned(keys[i-1], keys[i]));
+    }
+
+    for i in 2..MAX {
+        assert!(ut.unioned(keys[i-2], keys[i]));
+    }
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct IntKey(u32);
+
+impl UnifyKey for IntKey {
+    type Value = Option<i32>;
+    fn index(&self) -> u32 { self.0 }
+    fn from_index(u: u32) -> IntKey { IntKey(u) }
+    fn tag(_: Option<IntKey>) -> &'static str { "IntKey" }
+}
+
+/// Test unifying a key whose value is `Some(_)`  with a key whose value is `None`.
+/// Afterwards both should be `Some(_)`.
+#[test]
+fn unify_key_Some_key_None() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    let k2 = ut.new_key(None);
+    assert!(ut.unify_var_var(k1, k2).is_ok());
+    assert_eq!(ut.probe(k2), Some(22));
+    assert_eq!(ut.probe(k1), Some(22));
+}
+
+/// Test unifying a key whose value is `None`  with a key whose value is `Some(_)`.
+/// Afterwards both should be `Some(_)`.
+#[test]
+fn unify_key_None_key_Some() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    let k2 = ut.new_key(None);
+    assert!(ut.unify_var_var(k2, k1).is_ok());
+    assert_eq!(ut.probe(k2), Some(22));
+    assert_eq!(ut.probe(k1), Some(22));
+}
+
+/// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(y)`.
+/// This should yield an error.
+#[test]
+fn unify_key_Some_x_key_Some_y() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    let k2 = ut.new_key(Some(23));
+    assert_eq!(ut.unify_var_var(k1, k2), Err((22, 23)));
+    assert_eq!(ut.unify_var_var(k2, k1), Err((23, 22)));
+    assert_eq!(ut.probe(k1), Some(22));
+    assert_eq!(ut.probe(k2), Some(23));
+}
+
+/// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(x)`.
+/// This should be ok.
+#[test]
+fn unify_key_Some_x_key_Some_x() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    let k2 = ut.new_key(Some(22));
+    assert!(ut.unify_var_var(k1, k2).is_ok());
+    assert_eq!(ut.probe(k1), Some(22));
+    assert_eq!(ut.probe(k2), Some(22));
+}
+
+/// Test unifying a key whose value is `None` with a value is `x`.
+/// Afterwards key should be `x`.
+#[test]
+fn unify_key_None_val() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(None);
+    assert!(ut.unify_var_value(k1, 22).is_ok());
+    assert_eq!(ut.probe(k1), Some(22));
+}
+
+/// Test unifying a key whose value is `Some(x)` with the value `y`.
+/// This should yield an error.
+#[test]
+fn unify_key_Some_x_val_y() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    assert_eq!(ut.unify_var_value(k1, 23), Err((22, 23)));
+    assert_eq!(ut.probe(k1), Some(22));
+}
+
+/// Test unifying a key whose value is `Some(x)` with the value `x`.
+/// This should be ok.
+#[test]
+fn unify_key_Some_x_val_x() {
+    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
+    let k1 = ut.new_key(Some(22));
+    assert!(ut.unify_var_value(k1, 22).is_ok());
+    assert_eq!(ut.probe(k1), Some(22));
+}
+
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index bdc3fdcfc14..33a817cfedb 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -1886,14 +1886,13 @@ impl LintPass for UnconditionalRecursion {
                 continue;
             }
             // add the successors of this node to explore the graph further.
-            cfg.graph.each_outgoing_edge(idx, |_, edge| {
+            for (_, edge) in cfg.graph.outgoing_edges(idx) {
                 let target_idx = edge.target();
                 let target_cfg_id = target_idx.node_id();
                 if !visited.contains(&target_cfg_id) {
                     work_queue.push(target_idx)
                 }
-                true
-            });
+            }
         }
 
         // Check the number of self calls because a function that