auto merge of #7688 : nikomatsakis/rust/issue-6298-dataflow-graph, r=graydon

This patch is a step towards #6298. It extracts the graph abstraction from region inference into a library, and then ports the region inference to use it. It also adds a control-flow graph abstraction that will eventually be used by dataflow. The CFG code is not yet used, but I figured better to add it so as to make later rebasing etc easier.

8 files changed, 1178 insertions, 195 deletions

diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
new file mode 100644
index 00000000000..9ecb4dcaf5e
--- /dev/null
+++ b/src/librustc/middle/cfg/construct.rs
@@ -0,0 +1,523 @@
+// Copyright 2012 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::cfg::*;
+use middle::graph;
+use middle::typeck;
+use middle::ty;
+use std::hashmap::HashMap;
+use syntax::ast;
+use syntax::ast_util;
+use syntax::opt_vec;
+
+struct CFGBuilder {
+    tcx: ty::ctxt,
+    method_map: typeck::method_map,
+    exit_map: HashMap<ast::node_id, CFGIndex>,
+    graph: CFGGraph,
+    loop_scopes: ~[LoopScope],
+}
+
+struct LoopScope {
+    loop_id: ast::node_id,    // id of loop/while node
+    continue_index: CFGIndex, // where to go on a `loop`
+    break_index: CFGIndex,    // where to go on a `break
+}
+
+pub fn construct(tcx: ty::ctxt,
+                 method_map: typeck::method_map,
+                 blk: &ast::blk) -> CFG {
+    let mut cfg_builder = CFGBuilder {
+        exit_map: HashMap::new(),
+        graph: graph::Graph::new(),
+        tcx: tcx,
+        method_map: method_map,
+        loop_scopes: ~[]
+    };
+    let entry = cfg_builder.add_node(0, []);
+    let exit = cfg_builder.block(blk, entry);
+    let CFGBuilder {exit_map, graph, _} = cfg_builder;
+    CFG {exit_map: exit_map,
+         graph: graph,
+         entry: entry,
+         exit: exit}
+}
+
+impl CFGBuilder {
+    fn block(&mut self, blk: &ast::blk, pred: CFGIndex) -> CFGIndex {
+        let mut stmts_exit = pred;
+        for blk.node.stmts.iter().advance |&stmt| {
+            stmts_exit = self.stmt(stmt, stmts_exit);
+        }
+
+        let expr_exit = self.opt_expr(blk.node.expr, stmts_exit);
+
+        self.add_node(blk.node.id, [expr_exit])
+    }
+
+    fn stmt(&mut self, stmt: @ast::stmt, pred: CFGIndex) -> CFGIndex {
+        match stmt.node {
+            ast::stmt_decl(decl, _) => {
+                self.decl(decl, pred)
+            }
+
+            ast::stmt_expr(expr, _) | ast::stmt_semi(expr, _) => {
+                self.expr(expr, pred)
+            }
+
+            ast::stmt_mac(*) => {
+                self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
+            }
+        }
+    }
+
+    fn decl(&mut self, decl: @ast::decl, pred: CFGIndex) -> CFGIndex {
+        match decl.node {
+            ast::decl_local(local) => {
+                let init_exit = self.opt_expr(local.node.init, pred);
+                self.pat(local.node.pat, init_exit)
+            }
+
+            ast::decl_item(_) => {
+                pred
+            }
+        }
+    }
+
+    fn pat(&mut self, pat: @ast::pat, pred: CFGIndex) -> CFGIndex {
+        match pat.node {
+            ast::pat_ident(_, _, None) |
+            ast::pat_enum(_, None) |
+            ast::pat_lit(*) |
+            ast::pat_range(*) |
+            ast::pat_wild => {
+                self.add_node(pat.id, [pred])
+            }
+
+            ast::pat_box(subpat) |
+            ast::pat_uniq(subpat) |
+            ast::pat_region(subpat) |
+            ast::pat_ident(_, _, Some(subpat)) => {
+                let subpat_exit = self.pat(subpat, pred);
+                self.add_node(pat.id, [subpat_exit])
+            }
+
+            ast::pat_enum(_, Some(ref subpats)) |
+            ast::pat_tup(ref subpats) => {
+                let pats_exit =
+                    self.pats_all(subpats.iter().transform(|p| *p), pred);
+                self.add_node(pat.id, [pats_exit])
+            }
+
+            ast::pat_struct(_, ref subpats, _) => {
+                let pats_exit =
+                    self.pats_all(subpats.iter().transform(|f| f.pat), pred);
+                self.add_node(pat.id, [pats_exit])
+            }
+
+            ast::pat_vec(ref pre, ref vec, ref post) => {
+                let pre_exit =
+                    self.pats_all(pre.iter().transform(|p| *p), pred);
+                let vec_exit =
+                    self.pats_all(vec.iter().transform(|p| *p), pre_exit);
+                let post_exit =
+                    self.pats_all(post.iter().transform(|p| *p), vec_exit);
+                self.add_node(pat.id, [post_exit])
+            }
+        }
+    }
+
+    fn pats_all<I: Iterator<@ast::pat>>(&mut self,
+                                        pats: I,
+                                        pred: CFGIndex) -> CFGIndex {
+        //! Handles case where all of the patterns must match.
+        let mut pats = pats;
+        pats.fold(pred, |pred, pat| self.pat(pat, pred))
+    }
+
+    fn pats_any(&mut self,
+                pats: &[@ast::pat],
+                pred: CFGIndex) -> CFGIndex {
+        //! Handles case where just one of the patterns must match.
+
+        if pats.len() == 1 {
+            self.pat(pats[0], pred)
+        } else {
+            let collect = self.add_dummy_node([]);
+            for pats.iter().advance |&pat| {
+                let pat_exit = self.pat(pat, pred);
+                self.add_contained_edge(pat_exit, collect);
+            }
+            collect
+        }
+    }
+
+    fn expr(&mut self, expr: @ast::expr, pred: CFGIndex) -> CFGIndex {
+        match expr.node {
+            ast::expr_block(ref blk) => {
+                let blk_exit = self.block(blk, pred);
+                self.add_node(expr.id, [blk_exit])
+            }
+
+            ast::expr_if(cond, ref then, None) => {
+                //
+                //     [pred]
+                //       |
+                //       v 1
+                //     [cond]
+                //       |
+                //      / \
+                //     /   \
+                //    v 2   *
+                //  [then]  |
+                //    |     |
+                //    v 3   v 4
+                //   [..expr..]
+                //
+                let cond_exit = self.expr(cond, pred);                // 1
+                let then_exit = self.block(then, cond_exit);          // 2
+                self.add_node(expr.id, [cond_exit, then_exit])        // 3,4
+            }
+
+            ast::expr_if(cond, ref then, Some(otherwise)) => {
+                //
+                //     [pred]
+                //       |
+                //       v 1
+                //     [cond]
+                //       |
+                //      / \
+                //     /   \
+                //    v 2   v 3
+                //  [then][otherwise]
+                //    |     |
+                //    v 4   v 5
+                //   [..expr..]
+                //
+                let cond_exit = self.expr(cond, pred);                // 1
+                let then_exit = self.block(then, cond_exit);          // 2
+                let else_exit = self.expr(otherwise, cond_exit);      // 3
+                self.add_node(expr.id, [then_exit, else_exit])        // 4, 5
+            }
+
+            ast::expr_while(cond, ref body) => {
+                //
+                //         [pred]
+                //           |
+                //           v 1
+                //       [loopback] <--+ 5
+                //           |         |
+                //           v 2       |
+                //   +-----[cond]      |
+                //   |       |         |
+                //   |       v 4       |
+                //   |     [body] -----+
+                //   v 3
+                // [expr]
+                //
+                // Note that `break` and `loop` statements
+                // may cause additional edges.
+
+                // NOTE: Is the condition considered part of the loop?
+                let loopback = self.add_dummy_node([pred]);           // 1
+                let cond_exit = self.expr(cond, loopback);            // 2
+                let expr_exit = self.add_node(expr.id, [cond_exit]);  // 3
+                self.loop_scopes.push(LoopScope {
+                    loop_id: expr.id,
+                    continue_index: loopback,
+                    break_index: expr_exit
+                });
+                let body_exit = self.block(body, cond_exit);          // 4
+                self.add_contained_edge(body_exit, loopback);         // 5
+                expr_exit
+            }
+
+            ast::expr_loop(ref body, _) => {
+                //
+                //     [pred]
+                //       |
+                //       v 1
+                //   [loopback] <---+
+                //       |      4   |
+                //       v 3        |
+                //     [body] ------+
+                //
+                //     [expr] 2
+                //
+                // Note that `break` and `loop` statements
+                // may cause additional edges.
+
+                let loopback = self.add_dummy_node([pred]);           // 1
+                let expr_exit = self.add_node(expr.id, []);           // 2
+                self.loop_scopes.push(LoopScope {
+                    loop_id: expr.id,
+                    continue_index: loopback,
+                    break_index: expr_exit,
+                });
+                let body_exit = self.block(body, loopback);           // 3
+                self.add_contained_edge(body_exit, loopback);         // 4
+                self.loop_scopes.pop();
+                expr_exit
+            }
+
+            ast::expr_match(discr, ref arms) => {
+                //
+                //     [pred]
+                //       |
+                //       v 1
+                //    [discr]
+                //       |
+                //       v 2
+                //    [guard1]
+                //      /  \
+                //     |    \
+                //     v 3  |
+                //  [pat1]  |
+                //     |
+                //     v 4  |
+                // [body1]  v
+                //     |  [guard2]
+                //     |    /   \
+                //     | [body2] \
+                //     |    |   ...
+                //     |    |    |
+                //     v 5  v    v
+                //   [....expr....]
+                //
+                let discr_exit = self.expr(discr, pred);                 // 1
+
+                let expr_exit = self.add_node(expr.id, []);
+                let mut guard_exit = discr_exit;
+                for arms.iter().advance |arm| {
+                    guard_exit = self.opt_expr(arm.guard, guard_exit); // 2
+                    let pats_exit = self.pats_any(arm.pats, guard_exit); // 3
+                    let body_exit = self.block(&arm.body, pats_exit);    // 4
+                    self.add_contained_edge(body_exit, expr_exit);       // 5
+                }
+                expr_exit
+            }
+
+            ast::expr_binary(_, op, l, r) if ast_util::lazy_binop(op) => {
+                //
+                //     [pred]
+                //       |
+                //       v 1
+                //      [l]
+                //       |
+                //      / \
+                //     /   \
+                //    v 2  *
+                //   [r]   |
+                //    |    |
+                //    v 3  v 4
+                //   [..exit..]
+                //
+                let l_exit = self.expr(l, pred);                         // 1
+                let r_exit = self.expr(r, l_exit);                       // 2
+                self.add_node(expr.id, [l_exit, r_exit])                 // 3,4
+            }
+
+            ast::expr_ret(v) => {
+                let v_exit = self.opt_expr(v, pred);
+                let loop_scope = self.loop_scopes[0];
+                self.add_exiting_edge(expr, v_exit,
+                                      loop_scope, loop_scope.break_index);
+                self.add_node(expr.id, [])
+            }
+
+            ast::expr_break(label) => {
+                let loop_scope = self.find_scope(expr, label);
+                self.add_exiting_edge(expr, pred,
+                                      loop_scope, loop_scope.break_index);
+                self.add_node(expr.id, [])
+            }
+
+            ast::expr_again(label) => {
+                let loop_scope = self.find_scope(expr, label);
+                self.add_exiting_edge(expr, pred,
+                                      loop_scope, loop_scope.continue_index);
+                self.add_node(expr.id, [])
+            }
+
+            ast::expr_vec(ref elems, _) => {
+                self.straightline(expr, pred, *elems)
+            }
+
+            ast::expr_call(func, ref args, _) => {
+                self.call(expr, pred, func, *args)
+            }
+
+            ast::expr_method_call(_, rcvr, _, _, ref args, _) => {
+                self.call(expr, pred, rcvr, *args)
+            }
+
+            ast::expr_index(_, l, r) |
+            ast::expr_binary(_, _, l, r) if self.is_method_call(expr) => {
+                self.call(expr, pred, l, [r])
+            }
+
+            ast::expr_unary(_, _, e) if self.is_method_call(expr) => {
+                self.call(expr, pred, e, [])
+            }
+
+            ast::expr_tup(ref exprs) => {
+                self.straightline(expr, pred, *exprs)
+            }
+
+            ast::expr_struct(_, ref fields, base) => {
+                let base_exit = self.opt_expr(base, pred);
+                let field_exprs: ~[@ast::expr] =
+                    fields.iter().transform(|f| f.node.expr).collect();
+                self.straightline(expr, base_exit, field_exprs)
+            }
+
+            ast::expr_repeat(elem, count, _) => {
+                self.straightline(expr, pred, [elem, count])
+            }
+
+            ast::expr_assign(l, r) |
+            ast::expr_assign_op(_, _, l, r) => {
+                self.straightline(expr, pred, [r, l])
+            }
+
+            ast::expr_log(l, r) |
+            ast::expr_index(_, l, r) |
+            ast::expr_binary(_, _, l, r) => { // NB: && and || handled earlier
+                self.straightline(expr, pred, [l, r])
+            }
+
+            ast::expr_addr_of(_, e) |
+            ast::expr_copy(e) |
+            ast::expr_loop_body(e) |
+            ast::expr_do_body(e) |
+            ast::expr_cast(e, _) |
+            ast::expr_unary(_, _, e) |
+            ast::expr_paren(e) |
+            ast::expr_vstore(e, _) |
+            ast::expr_field(e, _, _) => {
+                self.straightline(expr, pred, [e])
+            }
+
+            ast::expr_mac(*) |
+            ast::expr_inline_asm(*) |
+            ast::expr_self |
+            ast::expr_fn_block(*) |
+            ast::expr_lit(*) |
+            ast::expr_path(*) => {
+                self.straightline(expr, pred, [])
+            }
+        }
+    }
+
+    fn call(&mut self,
+            call_expr: @ast::expr,
+            pred: CFGIndex,
+            func_or_rcvr: @ast::expr,
+            args: &[@ast::expr]) -> CFGIndex {
+        let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
+        self.straightline(call_expr, func_or_rcvr_exit, args)
+    }
+
+    fn exprs(&mut self,
+             exprs: &[@ast::expr],
+             pred: CFGIndex) -> CFGIndex {
+        //! Constructs graph for `exprs` evaluated in order
+
+        exprs.iter().fold(pred, |p, &e| self.expr(e, p))
+    }
+
+    fn opt_expr(&mut self,
+                opt_expr: Option<@ast::expr>,
+                pred: CFGIndex) -> CFGIndex {
+        //! Constructs graph for `opt_expr` evaluated, if Some
+
+        opt_expr.iter().fold(pred, |p, &e| self.expr(e, p))
+    }
+
+    fn straightline(&mut self,
+                    expr: @ast::expr,
+                    pred: CFGIndex,
+                    subexprs: &[@ast::expr]) -> CFGIndex {
+        //! Handles case of an expression that evaluates `subexprs` in order
+
+        let subexprs_exit = self.exprs(subexprs, pred);
+        self.add_node(expr.id, [subexprs_exit])
+    }
+
+    fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
+        self.add_node(0, preds)
+    }
+
+    fn add_node(&mut self, id: ast::node_id, preds: &[CFGIndex]) -> CFGIndex {
+        assert!(!self.exit_map.contains_key(&id));
+        let node = self.graph.add_node(CFGNodeData {id: id});
+        self.exit_map.insert(id, node);
+        for preds.iter().advance |&pred| {
+            self.add_contained_edge(pred, node);
+        }
+        node
+    }
+
+    fn add_contained_edge(&mut self,
+                          source: CFGIndex,
+                          target: CFGIndex) {
+        let data = CFGEdgeData {exiting_scopes: opt_vec::Empty};
+        self.graph.add_edge(source, target, data);
+    }
+
+    fn add_exiting_edge(&mut self,
+                        from_expr: @ast::expr,
+                        from_index: CFGIndex,
+                        to_loop: LoopScope,
+                        to_index: CFGIndex) {
+        let mut data = CFGEdgeData {exiting_scopes: opt_vec::Empty};
+        let mut scope_id = from_expr.id;
+        while scope_id != to_loop.loop_id {
+            data.exiting_scopes.push(scope_id);
+            scope_id = self.tcx.region_maps.encl_scope(scope_id);
+        }
+        self.graph.add_edge(from_index, to_index, data);
+    }
+
+    fn find_scope(&self,
+                  expr: @ast::expr,
+                  label: Option<ast::ident>) -> LoopScope {
+        match label {
+            None => {
+                return *self.loop_scopes.last();
+            }
+
+            Some(_) => {
+                match self.tcx.def_map.find(&expr.id) {
+                    Some(&ast::def_label(loop_id)) => {
+                        for self.loop_scopes.iter().advance |l| {
+                            if l.loop_id == loop_id {
+                                return *l;
+                            }
+                        }
+                        self.tcx.sess.span_bug(
+                            expr.span,
+                            fmt!("No loop scope for id %?", loop_id));
+                    }
+
+                    r => {
+                        self.tcx.sess.span_bug(
+                            expr.span,
+                            fmt!("Bad entry `%?` in def_map for label", r));
+                    }
+                }
+            }
+        }
+    }
+
+    fn is_method_call(&self, expr: &ast::expr) -> bool {
+        self.method_map.contains_key(&expr.id)
+    }
+}
\ No newline at end of file
diff --git a/src/librustc/middle/cfg/mod.rs b/src/librustc/middle/cfg/mod.rs
new file mode 100644
index 00000000000..68aee78f28f
--- /dev/null
+++ b/src/librustc/middle/cfg/mod.rs
@@ -0,0 +1,61 @@
+// Copyright 2012 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.
+
+/*!
+
+Module that constructs a control-flow graph representing an item.
+Uses `Graph` as the underlying representation.
+
+*/
+
+use middle::graph;
+use middle::ty;
+use middle::typeck;
+use std::hashmap::HashMap;
+use syntax::ast;
+use syntax::opt_vec::OptVec;
+
+mod construct;
+
+pub struct CFG {
+    exit_map: HashMap<ast::node_id, CFGIndex>,
+    graph: CFGGraph,
+    entry: CFGIndex,
+    exit: CFGIndex,
+}
+
+pub struct CFGNodeData {
+    id: ast::node_id
+}
+
+pub struct CFGEdgeData {
+    exiting_scopes: OptVec<ast::node_id>
+}
+
+pub type CFGIndex = graph::NodeIndex;
+
+pub type CFGGraph = graph::Graph<CFGNodeData, CFGEdgeData>;
+
+pub type CFGNode = graph::Node<CFGNodeData>;
+
+pub type CFGEdge = graph::Edge<CFGEdgeData>;
+
+pub struct CFGIndices {
+    entry: CFGIndex,
+    exit: CFGIndex,
+}
+
+impl CFG {
+    pub fn new(tcx: ty::ctxt,
+               method_map: typeck::method_map,
+               blk: &ast::blk) -> CFG {
+        construct::construct(tcx, method_map, blk)
+    }
+}
\ No newline at end of file
diff --git a/src/librustc/middle/graph.rs b/src/librustc/middle/graph.rs
new file mode 100644
index 00000000000..e37df6eda2d
--- /dev/null
+++ b/src/librustc/middle/graph.rs
@@ -0,0 +1,410 @@
+// Copyright 2012 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.
+
+/*!
+
+A graph module for use in dataflow, region resolution, and elsewhere.
+
+# Interface details
+
+You customize the graph by specifying a "node data" type `N` and an
+"edge data" type `E`. You can then later gain access (mutable or
+immutable) to these "user-data" bits. Currently, you can only add
+nodes or edges to the graph. You cannot remove or modify them once
+added. This could be changed if we have a need.
+
+# Implementation details
+
+The main tricky thing about this code is the way that edges are
+stored. The edges are stored in a central array, but they are also
+threaded onto two linked lists for each node, one for incoming edges
+and one for outgoing edges. Note that every edge is a member of some
+incoming list and some outgoing list.  Basically you can load the
+first index of the linked list from the node data structures (the
+field `first_edge`) and then, for each edge, load the next index from
+the field `next_edge`). Each of those fields is an array that should
+be indexed by the direction (see the type `Direction`).
+
+*/
+
+use std::uint;
+use std::vec;
+
+pub struct Graph<N,E> {
+    priv nodes: ~[Node<N>],
+    priv edges: ~[Edge<E>],
+}
+
+pub struct Node<N> {
+    priv first_edge: [EdgeIndex, ..2], // see module comment
+    data: N,
+}
+
+pub struct Edge<E> {
+    priv next_edge: [EdgeIndex, ..2], // see module comment
+    priv source: NodeIndex,
+    priv target: NodeIndex,
+    data: E,
+}
+
+#[deriving(Eq)]
+pub struct NodeIndex(uint);
+pub static InvalidNodeIndex: NodeIndex = NodeIndex(uint::max_value);
+
+#[deriving(Eq)]
+pub struct EdgeIndex(uint);
+pub static InvalidEdgeIndex: EdgeIndex = EdgeIndex(uint::max_value);
+
+// Use a private field here to guarantee no more instances are created:
+pub struct Direction { priv repr: uint }
+pub static Outgoing: Direction = Direction { repr: 0 };
+pub static Incoming: Direction = Direction { repr: 1 };
+
+impl<N,E> Graph<N,E> {
+    pub fn new() -> Graph<N,E> {
+        Graph {nodes: ~[], edges: ~[]}
+    }
+
+    pub fn with_capacity(num_nodes: uint,
+                         num_edges: uint) -> Graph<N,E> {
+        Graph {nodes: vec::with_capacity(num_nodes),
+               edges: vec::with_capacity(num_edges)}
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // Simple accessors
+
+    #[inline]
+    pub fn all_nodes<'a>(&'a self) -> &'a [Node<N>] {
+        let nodes: &'a [Node<N>] = self.nodes;
+        nodes
+    }
+
+    #[inline]
+    pub fn all_edges<'a>(&'a self) -> &'a [Edge<E>] {
+        let edges: &'a [Edge<E>] = self.edges;
+        edges
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // Node construction
+
+    pub fn next_node_index(&self) -> NodeIndex {
+        NodeIndex(self.nodes.len())
+    }
+
+    pub fn add_node(&mut self, data: N) -> NodeIndex {
+        let idx = self.next_node_index();
+        self.nodes.push(Node {
+            first_edge: [InvalidEdgeIndex, InvalidEdgeIndex],
+            data: data
+        });
+        idx
+    }
+
+    pub fn mut_node_data<'a>(&'a mut self, idx: NodeIndex) -> &'a mut N {
+        &mut self.nodes[*idx].data
+    }
+
+    pub fn node_data<'a>(&'a self, idx: NodeIndex) -> &'a N {
+        &self.nodes[*idx].data
+    }
+
+    pub fn node<'a>(&'a self, idx: NodeIndex) -> &'a Node<N> {
+        &self.nodes[*idx]
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // Edge construction and queries
+
+    pub fn next_edge_index(&self) -> EdgeIndex {
+        EdgeIndex(self.edges.len())
+    }
+
+    pub fn add_edge(&mut self,
+                    source: NodeIndex,
+                    target: NodeIndex,
+                    data: E) -> EdgeIndex {
+        let idx = self.next_edge_index();
+
+        // read current first of the list of edges from each node
+        let source_first = self.nodes[*source].first_edge[Outgoing.repr];
+        let target_first = self.nodes[*target].first_edge[Incoming.repr];
+
+        // create the new edge, with the previous firsts from each node
+        // as the next pointers
+        self.edges.push(Edge {
+            next_edge: [source_first, target_first],
+            source: source,
+            target: target,
+            data: data
+        });
+
+        // adjust the firsts for each node target be the next object.
+        self.nodes[*source].first_edge[Outgoing.repr] = idx;
+        self.nodes[*target].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].data
+    }
+
+    pub fn edge_data<'a>(&'a self, idx: EdgeIndex) -> &'a E {
+        &self.edges[*idx].data
+    }
+
+    pub fn edge<'a>(&'a self, idx: EdgeIndex) -> &'a Edge<E> {
+        &self.edges[*idx]
+    }
+
+    pub fn first_adjacent(&self, node: NodeIndex, dir: Direction) -> EdgeIndex {
+        //! Accesses the index of the first edge adjacent to `node`.
+        //! This is useful if you wish to modify the graph while walking
+        //! the linked list of edges.
+
+        self.nodes[*node].first_edge[dir.repr]
+    }
+
+    pub fn next_adjacent(&self, edge: EdgeIndex, dir: Direction) -> EdgeIndex {
+        //! Accesses the next edge in a given direction.
+        //! This is useful if you wish to modify the graph while walking
+        //! the linked list of edges.
+
+        self.edges[*edge].next_edge[dir.repr]
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // Iterating over nodes, edges
+
+    pub fn each_node(&self, f: &fn(NodeIndex, &Node<N>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph.
+
+        uint::range(0, self.nodes.len(),
+                    |i| f(NodeIndex(i), &self.nodes[i]))
+    }
+
+    pub fn each_edge(&self, f: &fn(EdgeIndex, &Edge<E>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph.
+
+        uint::range(0, self.nodes.len(),
+                    |i| f(EdgeIndex(i), &self.edges[i]))
+    }
+
+    pub fn each_outgoing_edge(&self,
+                              source: NodeIndex,
+                              f: &fn(EdgeIndex, &Edge<E>) -> bool) -> bool {
+        //! Iterates over all outgoing edges from the node `from`
+
+        self.each_adjacent_edge(source, Outgoing, f)
+    }
+
+    pub fn each_incoming_edge(&self,
+                              target: NodeIndex,
+                              f: &fn(EdgeIndex, &Edge<E>) -> bool) -> bool {
+        //! Iterates over all incoming edges to the node `target`
+
+        self.each_adjacent_edge(target, Incoming, f)
+    }
+
+    pub fn each_adjacent_edge(&self,
+                              node: NodeIndex,
+                              dir: Direction,
+                              f: &fn(EdgeIndex, &Edge<E>) -> bool) -> 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];
+            if !f(edge_idx, edge) {
+                return false;
+            }
+            edge_idx = edge.next_edge[dir.repr];
+        }
+        return true;
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // Fixed-point iteration
+    //
+    // A common use for graphs in our compiler is to perform
+    // fixed-point iteration. In this case, each edge represents a
+    // constaint, and the nodes themselves are associated with
+    // variables or other bitsets. This method facilitates such a
+    // computation.
+
+    pub fn iterate_until_fixed_point(&self,
+                                     op: &fn(iter_index: uint,
+                                             edge_index: EdgeIndex,
+                                             edge: &Edge<E>) -> bool) {
+        let mut iteration = 0;
+        let mut changed = true;
+        while changed {
+            changed = false;
+            iteration += 1;
+            for self.edges.iter().enumerate().advance |(i, edge)| {
+                changed |= op(iteration, EdgeIndex(i), edge);
+            }
+        }
+    }
+}
+
+pub fn each_edge_index(max_edge_index: EdgeIndex, f: &fn(EdgeIndex) -> bool) {
+    let mut i = 0;
+    let n = *max_edge_index;
+    while i < n {
+        if !f(EdgeIndex(i)) {
+            return;
+        }
+        i += 1;
+    }
+}
+
+impl<E> Edge<E> {
+    pub fn source(&self) -> NodeIndex {
+        self.source
+    }
+
+    pub fn target(&self) -> NodeIndex {
+        self.target
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use middle::graph::*;
+
+    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"];
+        for graph.each_node |idx, node| {
+            assert_eq!(&expected[*idx], graph.node_data(idx));
+            assert_eq!(expected[*idx], node.data);
+        }
+    }
+
+    #[test]
+    fn each_edge() {
+        let graph = create_graph();
+        let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
+        for graph.each_edge |idx, edge| {
+            assert_eq!(&expected[*idx], graph.edge_data(idx));
+            assert_eq!(expected[*idx], edge.data);
+        }
+    }
+
+    fn test_adjacent_edges<N:Eq,E:Eq>(graph: &Graph<N,E>,
+                                      start_index: NodeIndex,
+                                      start_data: N,
+                                      expected_incoming: &[(E,N)],
+                                      expected_outgoing: &[(E,N)]) {
+        assert_eq!(graph.node_data(start_index), &start_data);
+
+        let mut counter = 0;
+        for graph.each_incoming_edge(start_index) |edge_index, edge| {
+            assert_eq!(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_eq!(e, &edge.data);
+                    assert_eq!(n, graph.node_data(edge.source));
+                    assert_eq!(start_index, edge.target);
+                }
+            }
+            counter += 1;
+        }
+        assert_eq!(counter, expected_incoming.len());
+
+        let mut counter = 0;
+        for graph.each_outgoing_edge(start_index) |edge_index, edge| {
+            assert_eq!(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_eq!(e, &edge.data);
+                    assert_eq!(start_index, edge.source);
+                    assert_eq!(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")]);
+    }
+}
\ No newline at end of file
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index fed8c5e800e..4c401af8e8e 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -548,7 +548,6 @@ pub fn trans_trait_callee_from_llval(bcx: block,
 
     let _icx = push_ctxt("impl::trans_trait_callee");
     let ccx = bcx.ccx();
-    let bcx = bcx;
 
     // Load the vtable from the @Trait pair
     debug!("(translating trait callee) loading vtable from pair %s",
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index ae8cab4c4db..21f3fdf7b2c 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -372,9 +372,9 @@ impl ErrorReporting for InferCtxt {
                     sup,
                     "");
             }
-            infer::ReferenceOutlivesReferent(ty, _) => {
+            infer::ReferenceOutlivesReferent(ty, span) => {
                 self.tcx.sess.span_err(
-                    origin.span(),
+                    span,
                     fmt!("in type `%s`, pointer has a longer lifetime than \
                           the data it references",
                          ty.user_string(self.tcx)));
diff --git a/src/librustc/middle/typeck/infer/region_inference/mod.rs b/src/librustc/middle/typeck/infer/region_inference/mod.rs
index 50290ba752e..c3b35aba518 100644
--- a/src/librustc/middle/typeck/infer/region_inference/mod.rs
+++ b/src/librustc/middle/typeck/infer/region_inference/mod.rs
@@ -18,6 +18,8 @@ use middle::ty::{re_scope, ReVar, ReSkolemized, br_fresh};
 use middle::typeck::infer::cres;
 use middle::typeck::infer::{RegionVariableOrigin, SubregionOrigin};
 use middle::typeck::infer;
+use middle::graph;
+use middle::graph::{Direction, NodeIndex};
 use util::common::indenter;
 use util::ppaux::{Repr};
 
@@ -105,7 +107,7 @@ pub struct RegionVarBindings {
     // This contains the results of inference.  It begins as an empty
     // cell and only acquires a value after inference is complete.
     // We use a cell vs a mutable option to circumvent borrowck errors.
-    values: Cell<~[GraphNodeValue]>,
+    values: Cell<~[VarValue]>,
 }
 
 pub fn RegionVarBindings(tcx: ty::ctxt) -> RegionVarBindings {
@@ -168,7 +170,7 @@ impl RegionVarBindings {
         }
     }
 
-    pub fn num_vars(&mut self) -> uint {
+    pub fn num_vars(&self) -> uint {
         self.var_origins.len()
     }
 
@@ -706,28 +708,13 @@ impl RegionVarBindings {
 // ______________________________________________________________________
 
 #[deriving(Eq)]
-enum Direction { Incoming = 0, Outgoing = 1 }
-
-#[deriving(Eq)]
 enum Classification { Expanding, Contracting }
 
-enum GraphNodeValue { NoValue, Value(Region), ErrorValue }
+enum VarValue { NoValue, Value(Region), ErrorValue }
 
-struct GraphNode {
-    origin: RegionVariableOrigin,
+struct VarData {
     classification: Classification,
-    value: GraphNodeValue,
-    head_edge: [uint, ..2],
-}
-
-struct GraphEdge {
-    next_edge: [uint, ..2],
-    constraint: Constraint,
-}
-
-struct Graph {
-    nodes: ~[GraphNode],
-    edges: ~[GraphEdge],
+    value: VarValue,
 }
 
 struct RegionAndOrigin {
@@ -735,97 +722,44 @@ struct RegionAndOrigin {
     origin: SubregionOrigin,
 }
 
+type RegionGraph = graph::Graph<(), Constraint>;
+
 impl RegionVarBindings {
-    fn infer_variable_values(&mut self,
+    fn infer_variable_values(&self,
                              errors: &mut OptVec<RegionResolutionError>)
-                             -> ~[GraphNodeValue] {
-        let mut graph = self.construct_graph();
-        self.expansion(&mut graph);
-        self.contraction(&mut graph);
-        self.collect_concrete_region_errors(&graph, errors);
-        self.extract_values_and_collect_conflicts(&graph, errors)
+                             -> ~[VarValue] {
+        let mut var_data = self.construct_var_data();
+        self.expansion(var_data);
+        self.contraction(var_data);
+        self.collect_concrete_region_errors(errors);
+        self.extract_values_and_collect_conflicts(var_data, errors)
     }
 
-    fn construct_graph(&mut self) -> Graph {
-        let num_vars = self.num_vars();
-        let num_edges = self.constraints.len();
-
-        let nodes = vec::from_fn(num_vars, |var_idx| {
-            GraphNode {
+    fn construct_var_data(&self) -> ~[VarData] {
+        vec::from_fn(self.num_vars(), |_| {
+            VarData {
                 // All nodes are initially classified as contracting; during
                 // the expansion phase, we will shift the classification for
                 // those nodes that have a concrete region predecessor to
                 // Expanding.
                 classification: Contracting,
-                origin: self.var_origins[var_idx],
                 value: NoValue,
-                head_edge: [uint::max_value, uint::max_value]
-            }
-        });
-
-        // It would be nice to write this using map():
-        let mut edges = vec::with_capacity(num_edges);
-        for self.constraints.iter().advance |(constraint, _)| {
-            edges.push(GraphEdge {
-                next_edge: [uint::max_value, uint::max_value],
-                constraint: *constraint,
-            });
-        }
-
-        let mut graph = Graph {
-            nodes: nodes,
-            edges: edges
-        };
-
-        for uint::range(0, num_edges) |edge_idx| {
-            match graph.edges[edge_idx].constraint {
-              ConstrainVarSubVar(a_id, b_id) => {
-                insert_edge(&mut graph, a_id, Outgoing, edge_idx);
-                insert_edge(&mut graph, b_id, Incoming, edge_idx);
-              }
-              ConstrainRegSubVar(_, b_id) => {
-                insert_edge(&mut graph, b_id, Incoming, edge_idx);
-              }
-              ConstrainVarSubReg(a_id, _) => {
-                insert_edge(&mut graph, a_id, Outgoing, edge_idx);
-              }
-              ConstrainRegSubReg(*) => {
-                  // Relations between two concrete regions do not
-                  // require an edge in the graph.
-              }
             }
-        }
-
-        return (graph);
-
-        fn insert_edge(graph: &mut Graph,
-                       node_id: RegionVid,
-                       edge_dir: Direction,
-                       edge_idx: uint) {
-            //! Insert edge `edge_idx` on the link list of edges in direction
-            //! `edge_dir` for the node `node_id`
-            let edge_dir = edge_dir as uint;
-            assert_eq!(graph.edges[edge_idx].next_edge[edge_dir],
-                       uint::max_value);
-            let n = node_id.to_uint();
-            let prev_head = graph.nodes[n].head_edge[edge_dir];
-            graph.edges[edge_idx].next_edge[edge_dir] = prev_head;
-            graph.nodes[n].head_edge[edge_dir] = edge_idx;
-        }
+        })
     }
 
-    fn expansion(&mut self, graph: &mut Graph) {
-        do iterate_until_fixed_point(~"Expansion", graph) |nodes, edge| {
-            match edge.constraint {
+    fn expansion(&self, var_data: &mut [VarData]) {
+        do self.iterate_until_fixed_point("Expansion") |constraint| {
+            match *constraint {
               ConstrainRegSubVar(a_region, b_vid) => {
-                let b_node = &mut nodes[b_vid.to_uint()];
-                self.expand_node(a_region, b_vid, b_node)
+                let b_data = &mut var_data[b_vid.to_uint()];
+                self.expand_node(a_region, b_vid, b_data)
               }
               ConstrainVarSubVar(a_vid, b_vid) => {
-                match nodes[a_vid.to_uint()].value {
+                match var_data[a_vid.to_uint()].value {
                   NoValue | ErrorValue => false,
                   Value(a_region) => {
-                    let b_node = &mut nodes[b_vid.to_uint()];
+                    let b_node = &mut var_data[b_vid.to_uint()];
                     self.expand_node(a_region, b_vid, b_node)
                   }
                 }
@@ -842,20 +776,20 @@ impl RegionVarBindings {
         }
     }
 
-    fn expand_node(&mut self,
+    fn expand_node(&self,
                    a_region: Region,
                    b_vid: RegionVid,
-                   b_node: &mut GraphNode)
+                   b_data: &mut VarData)
                    -> bool {
         debug!("expand_node(%?, %? == %?)",
-               a_region, b_vid, b_node.value);
+               a_region, b_vid, b_data.value);
 
-        b_node.classification = Expanding;
-        match b_node.value {
+        b_data.classification = Expanding;
+        match b_data.value {
           NoValue => {
             debug!("Setting initial value of %? to %?", b_vid, a_region);
 
-            b_node.value = Value(a_region);
+            b_data.value = Value(a_region);
             return true;
           }
 
@@ -868,7 +802,7 @@ impl RegionVarBindings {
             debug!("Expanding value of %? from %? to %?",
                    b_vid, cur_region, lub);
 
-            b_node.value = Value(lub);
+            b_data.value = Value(lub);
             return true;
           }
 
@@ -878,26 +812,26 @@ impl RegionVarBindings {
         }
     }
 
-    fn contraction(&mut self,
-                   graph: &mut Graph) {
-        do iterate_until_fixed_point(~"Contraction", graph) |nodes, edge| {
-            match edge.constraint {
+    fn contraction(&self,
+                   var_data: &mut [VarData]) {
+        do self.iterate_until_fixed_point("Contraction") |constraint| {
+            match *constraint {
               ConstrainRegSubVar(*) => {
                 // This is an expansion constraint.  Ignore.
                 false
               }
               ConstrainVarSubVar(a_vid, b_vid) => {
-                match nodes[b_vid.to_uint()].value {
+                match var_data[b_vid.to_uint()].value {
                   NoValue | ErrorValue => false,
                   Value(b_region) => {
-                    let a_node = &mut nodes[a_vid.to_uint()];
-                    self.contract_node(a_vid, a_node, b_region)
+                    let a_data = &mut var_data[a_vid.to_uint()];
+                    self.contract_node(a_vid, a_data, b_region)
                   }
                 }
               }
               ConstrainVarSubReg(a_vid, b_region) => {
-                let a_node = &mut nodes[a_vid.to_uint()];
-                self.contract_node(a_vid, a_node, b_region)
+                let a_data = &mut var_data[a_vid.to_uint()];
+                self.contract_node(a_vid, a_data, b_region)
               }
               ConstrainRegSubReg(*) => {
                 // No region variables involved. Ignore.
@@ -907,18 +841,18 @@ impl RegionVarBindings {
         }
     }
 
-    fn contract_node(&mut self,
+    fn contract_node(&self,
                      a_vid: RegionVid,
-                     a_node: &mut GraphNode,
+                     a_data: &mut VarData,
                      b_region: Region)
                      -> bool {
         debug!("contract_node(%? == %?/%?, %?)",
-               a_vid, a_node.value, a_node.classification, b_region);
+               a_vid, a_data.value, a_data.classification, b_region);
 
-        return match a_node.value {
+        return match a_data.value {
             NoValue => {
-                assert_eq!(a_node.classification, Contracting);
-                a_node.value = Value(b_region);
+                assert_eq!(a_data.classification, Contracting);
+                a_data.value = Value(b_region);
                 true // changed
             }
 
@@ -927,34 +861,34 @@ impl RegionVarBindings {
             }
 
             Value(a_region) => {
-                match a_node.classification {
+                match a_data.classification {
                     Expanding => {
-                        check_node(self, a_vid, a_node, a_region, b_region)
+                        check_node(self, a_vid, a_data, a_region, b_region)
                     }
                     Contracting => {
-                        adjust_node(self, a_vid, a_node, a_region, b_region)
+                        adjust_node(self, a_vid, a_data, a_region, b_region)
                     }
                 }
             }
         };
 
-        fn check_node(this: &mut RegionVarBindings,
+        fn check_node(this: &RegionVarBindings,
                       a_vid: RegionVid,
-                      a_node: &mut GraphNode,
+                      a_data: &mut VarData,
                       a_region: Region,
                       b_region: Region)
                    -> bool {
             if !this.is_subregion_of(a_region, b_region) {
                 debug!("Setting %? to ErrorValue: %? not subregion of %?",
                        a_vid, a_region, b_region);
-                a_node.value = ErrorValue;
+                a_data.value = ErrorValue;
             }
             false
         }
 
-        fn adjust_node(this: &mut RegionVarBindings,
+        fn adjust_node(this: &RegionVarBindings,
                        a_vid: RegionVid,
-                       a_node: &mut GraphNode,
+                       a_data: &mut VarData,
                        a_region: Region,
                        b_region: Region)
                     -> bool {
@@ -965,14 +899,14 @@ impl RegionVarBindings {
                     } else {
                         debug!("Contracting value of %? from %? to %?",
                                a_vid, a_region, glb);
-                        a_node.value = Value(glb);
+                        a_data.value = Value(glb);
                         true
                     }
                 }
                 Err(_) => {
                     debug!("Setting %? to ErrorValue: no glb of %?, %?",
                            a_vid, a_region, b_region);
-                    a_node.value = ErrorValue;
+                    a_data.value = ErrorValue;
                     false
                 }
             }
@@ -980,16 +914,11 @@ impl RegionVarBindings {
     }
 
     fn collect_concrete_region_errors(
-        &mut self,
-        graph: &Graph,
+        &self,
         errors: &mut OptVec<RegionResolutionError>)
     {
-        let num_edges = graph.edges.len();
-        for uint::range(0, num_edges) |edge_idx| {
-            let edge = &graph.edges[edge_idx];
-            let origin = self.constraints.get_copy(&edge.constraint);
-
-            let (sub, sup) = match edge.constraint {
+        for self.constraints.iter().advance |(constraint, _)| {
+            let (sub, sup) = match *constraint {
                 ConstrainVarSubVar(*) |
                 ConstrainRegSubVar(*) |
                 ConstrainVarSubReg(*) => {
@@ -1006,15 +935,16 @@ impl RegionVarBindings {
 
             debug!("ConcreteFailure: !(sub <= sup): sub=%?, sup=%?",
                    sub, sup);
+            let origin = self.constraints.get_copy(constraint);
             errors.push(ConcreteFailure(origin, sub, sup));
         }
     }
 
     fn extract_values_and_collect_conflicts(
-        &mut self,
-        graph: &Graph,
+        &self,
+        var_data: &[VarData],
         errors: &mut OptVec<RegionResolutionError>)
-        -> ~[GraphNodeValue]
+        -> ~[VarValue]
     {
         debug!("extract_values_and_collect_conflicts()");
 
@@ -1029,10 +959,12 @@ impl RegionVarBindings {
         // idea is to report errors that derive from independent
         // regions of the graph, but not those that derive from
         // overlapping locations.
-        let mut dup_vec = graph.nodes.map(|_| uint::max_value);
+        let mut dup_vec = vec::from_elem(self.num_vars(), uint::max_value);
+
+        let mut opt_graph = None;
 
-        graph.nodes.iter().enumerate().transform(|(idx, node)| {
-            match node.value {
+        for uint::range(0, self.num_vars()) |idx| {
+            match var_data[idx].value {
                 Value(_) => {
                     /* Inference successful */
                 }
@@ -1066,27 +998,72 @@ impl RegionVarBindings {
                        starts to create problems we'll have to revisit
                        this portion of the code and think hard about it. =) */
 
+                    if opt_graph.is_none() {
+                        opt_graph = Some(self.construct_graph());
+                    }
+                    let graph = opt_graph.get_ref();
+
                     let node_vid = RegionVid { id: idx };
-                    match node.classification {
+                    match var_data[idx].classification {
                         Expanding => {
                             self.collect_error_for_expanding_node(
-                                graph, dup_vec, node_vid, errors);
+                                graph, var_data, dup_vec, node_vid, errors);
                         }
                         Contracting => {
                             self.collect_error_for_contracting_node(
-                                graph, dup_vec, node_vid, errors);
+                                graph, var_data, dup_vec, node_vid, errors);
                         }
                     }
                 }
             }
+        }
 
-            node.value
-        }).collect()
+        vec::from_fn(self.num_vars(), |idx| var_data[idx].value)
+    }
+
+    fn construct_graph(&self) -> RegionGraph {
+        let num_vars = self.num_vars();
+        let num_edges = self.constraints.len();
+
+        let mut graph = graph::Graph::with_capacity(num_vars + 1,
+                                                    num_edges);
+
+        for uint::range(0, num_vars) |_| {
+            graph.add_node(());
+        }
+        let dummy_idx = graph.add_node(());
+
+        for self.constraints.iter().advance |(constraint, _)| {
+            match *constraint {
+                ConstrainVarSubVar(a_id, b_id) => {
+                    graph.add_edge(NodeIndex(a_id.to_uint()),
+                                   NodeIndex(b_id.to_uint()),
+                                   *constraint);
+                }
+                ConstrainRegSubVar(_, b_id) => {
+                    graph.add_edge(dummy_idx,
+                                   NodeIndex(b_id.to_uint()),
+                                   *constraint);
+                }
+                ConstrainVarSubReg(a_id, _) => {
+                    graph.add_edge(NodeIndex(a_id.to_uint()),
+                                   dummy_idx,
+                                   *constraint);
+                }
+                ConstrainRegSubReg(*) => {
+                    // Relations between two concrete regions do not
+                    // require an edge in the graph.
+                }
+            }
+        }
+
+        return graph;
     }
 
     fn collect_error_for_expanding_node(
-        &mut self,
-        graph: &Graph,
+        &self,
+        graph: &RegionGraph,
+        var_data: &[VarData],
         dup_vec: &mut [uint],
         node_idx: RegionVid,
         errors: &mut OptVec<RegionResolutionError>)
@@ -1094,9 +1071,11 @@ impl RegionVarBindings {
         // Errors in expanding nodes result from a lower-bound that is
         // not contained by an upper-bound.
         let (lower_bounds, lower_dup) =
-            self.collect_concrete_regions(graph, node_idx, Incoming, dup_vec);
+            self.collect_concrete_regions(graph, var_data, node_idx,
+                                          graph::Incoming, dup_vec);
         let (upper_bounds, upper_dup) =
-            self.collect_concrete_regions(graph, node_idx, Outgoing, dup_vec);
+            self.collect_concrete_regions(graph, var_data, node_idx,
+                                          graph::Outgoing, dup_vec);
 
         if lower_dup || upper_dup {
             return;
@@ -1127,8 +1106,9 @@ impl RegionVarBindings {
     }
 
     fn collect_error_for_contracting_node(
-        &mut self,
-        graph: &Graph,
+        &self,
+        graph: &RegionGraph,
+        var_data: &[VarData],
         dup_vec: &mut [uint],
         node_idx: RegionVid,
         errors: &mut OptVec<RegionResolutionError>)
@@ -1136,7 +1116,8 @@ impl RegionVarBindings {
         // Errors in contracting nodes result from two upper-bounds
         // that have no intersection.
         let (upper_bounds, dup_found) =
-            self.collect_concrete_regions(graph, node_idx, Outgoing, dup_vec);
+            self.collect_concrete_regions(graph, var_data, node_idx,
+                                          graph::Outgoing, dup_vec);
 
         if dup_found {
             return;
@@ -1168,8 +1149,9 @@ impl RegionVarBindings {
                  upper_bounds.map(|x| x.region).repr(self.tcx)));
     }
 
-    fn collect_concrete_regions(&mut self,
-                                graph: &Graph,
+    fn collect_concrete_regions(&self,
+                                graph: &RegionGraph,
+                                var_data: &[VarData],
                                 orig_node_idx: RegionVid,
                                 dir: Direction,
                                 dup_vec: &mut [uint])
@@ -1194,7 +1176,7 @@ impl RegionVarBindings {
 
         while !state.stack.is_empty() {
             let node_idx = state.stack.pop();
-            let classification = graph.nodes[node_idx.to_uint()].classification;
+            let classification = var_data[node_idx.to_uint()].classification;
 
             // check whether we've visited this node on some previous walk
             if dup_vec[node_idx.to_uint()] == uint::max_value {
@@ -1210,8 +1192,8 @@ impl RegionVarBindings {
             // 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 => Incoming,
-                Contracting => Outgoing
+                Expanding => graph::Incoming,
+                Contracting => graph::Outgoing,
             };
 
             process_edges(self, &mut state, graph, node_idx, dir);
@@ -1220,15 +1202,16 @@ impl RegionVarBindings {
         let WalkState {result, dup_found, _} = state;
         return (result, dup_found);
 
-        fn process_edges(this: &mut RegionVarBindings,
+        fn process_edges(this: &RegionVarBindings,
                          state: &mut WalkState,
-                         graph: &Graph,
+                         graph: &RegionGraph,
                          source_vid: RegionVid,
                          dir: Direction) {
             debug!("process_edges(source_vid=%?, dir=%?)", source_vid, dir);
 
-            for this.each_edge(graph, source_vid, dir) |edge| {
-                match edge.constraint {
+            let source_node_index = NodeIndex(source_vid.to_uint());
+            for graph.each_adjacent_edge(source_node_index, dir) |_, edge| {
+                match edge.data {
                     ConstrainVarSubVar(from_vid, to_vid) => {
                         let opp_vid =
                             if from_vid == source_vid {to_vid} else {from_vid};
@@ -1241,7 +1224,7 @@ impl RegionVarBindings {
                     ConstrainVarSubReg(_, region) => {
                         state.result.push(RegionAndOrigin {
                             region: region,
-                            origin: this.constraints.get_copy(&edge.constraint)
+                            origin: this.constraints.get_copy(&edge.data)
                         });
                     }
 
@@ -1251,42 +1234,40 @@ impl RegionVarBindings {
         }
     }
 
-    pub fn each_edge(&self,
-                     graph: &Graph,
-                     node_idx: RegionVid,
-                     dir: Direction,
-                     op: &fn(edge: &GraphEdge) -> bool)
-                     -> bool {
-        let mut edge_idx =
-            graph.nodes[node_idx.to_uint()].head_edge[dir as uint];
-        while edge_idx != uint::max_value {
-            let edge_ptr = &graph.edges[edge_idx];
-            if !op(edge_ptr) {
-                return false;
+    fn iterate_until_fixed_point(&self,
+                                 tag: &str,
+                                 body: &fn(constraint: &Constraint) -> bool) {
+        let mut iteration = 0;
+        let mut changed = true;
+        while changed {
+            changed = false;
+            iteration += 1;
+            debug!("---- %s Iteration #%u", tag, iteration);
+            for self.constraints.iter().advance |(constraint, _)| {
+                let edge_changed = body(constraint);
+                if edge_changed {
+                    debug!("Updated due to constraint %s",
+                           constraint.repr(self.tcx));
+                    changed = true;
+                }
             }
-            edge_idx = edge_ptr.next_edge[dir as uint];
         }
-        return true;
+        debug!("---- %s Complete after %u iteration(s)", tag, iteration);
     }
+
 }
 
-fn iterate_until_fixed_point(
-    tag: ~str,
-    graph: &mut Graph,
-    body: &fn(nodes: &mut [GraphNode], edge: &GraphEdge) -> bool)
-{
-    let mut iteration = 0;
-    let mut changed = true;
-    let num_edges = graph.edges.len();
-    while changed {
-        changed = false;
-        iteration += 1;
-        debug!("---- %s Iteration #%u", tag, iteration);
-        for uint::range(0, num_edges) |edge_idx| {
-            changed |= body(graph.nodes, &graph.edges[edge_idx]);
-            debug!(" >> Change after edge #%?: %?",
-                   edge_idx, graph.edges[edge_idx]);
+impl Repr for Constraint {
+    fn repr(&self, tcx: ty::ctxt) -> ~str {
+        match *self {
+            ConstrainVarSubVar(a, b) => fmt!("ConstrainVarSubVar(%s, %s)",
+                                             a.repr(tcx), b.repr(tcx)),
+            ConstrainRegSubVar(a, b) => fmt!("ConstrainRegSubVar(%s, %s)",
+                                             a.repr(tcx), b.repr(tcx)),
+            ConstrainVarSubReg(a, b) => fmt!("ConstrainVarSubReg(%s, %s)",
+                                             a.repr(tcx), b.repr(tcx)),
+            ConstrainRegSubReg(a, b) => fmt!("ConstrainRegSubReg(%s, %s)",
+                                             a.repr(tcx), b.repr(tcx)),
         }
     }
-    debug!("---- %s Complete after %u iteration(s)", tag, iteration);
 }
diff --git a/src/librustc/rustc.rs b/src/librustc/rustc.rs
index f4014180c64..542183e24db 100644
--- a/src/librustc/rustc.rs
+++ b/src/librustc/rustc.rs
@@ -74,6 +74,9 @@ pub mod middle {
     pub mod entry;
     pub mod effect;
     pub mod reachable;
+    pub mod graph;
+    #[path = "cfg/mod.rs"]
+    pub mod cfg;
 }
 
 pub mod front {
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 0aae41941cd..07dd19a3fed 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -751,6 +751,12 @@ impl Repr for typeck::method_param {
     }
 }
 
+impl Repr for ty::RegionVid {
+    fn repr(&self, _tcx: ctxt) -> ~str {
+        fmt!("%?", *self)
+    }
+}
+
 impl Repr for ty::TraitStore {
     fn repr(&self, tcx: ctxt) -> ~str {
         match self {