1 files changed, 91 insertions, 2 deletions

diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index d3d0f56c3ce..c9d50b9cecf 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -13,7 +13,8 @@
 use std::cell::{RefCell, Cell};
 use std::collections::HashMap;
 use std::fmt::Debug;
-use std::hash::{Hash, Hasher};
+use std::hash::Hash;
+#[cfg(stage0)] use std::hash::Hasher;
 use std::iter::repeat;
 use std::time::Duration;
 use std::collections::hash_state::HashState;
@@ -144,11 +145,54 @@ pub fn block_query<P>(b: &ast::Block, p: P) -> bool where P: FnMut(&ast::Expr) -
 /// Efficiency note: This is implemented in an inefficient way because it is typically invoked on
 /// very small graphs. If the graphs become larger, a more efficient graph representation and
 /// algorithm would probably be advised.
+#[cfg(stage0)]
 pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
                        destination: T) -> bool
     where S: HashState,
           <S as HashState>::Hasher: Hasher<Output=u64>,
-          T: Hash< <S as HashState>::Hasher> + Eq + Clone,
+          T: Hash<<S as HashState>::Hasher> + Eq + Clone,
+{
+    if source == destination {
+        return true;
+    }
+
+    // Do a little breadth-first-search here.  The `queue` list
+    // doubles as a way to detect if we've seen a particular FR
+    // before.  Note that we expect this graph to be an *extremely
+    // shallow* tree.
+    let mut queue = vec!(source);
+    let mut i = 0;
+    while i < queue.len() {
+        match edges_map.get(&queue[i]) {
+            Some(edges) => {
+                for target in edges {
+                    if *target == destination {
+                        return true;
+                    }
+
+                    if !queue.iter().any(|x| x == target) {
+                        queue.push((*target).clone());
+                    }
+                }
+            }
+            None => {}
+        }
+        i += 1;
+    }
+    return false;
+}
+/// K: Eq + Hash<S>, V, S, H: Hasher<S>
+///
+/// Determines whether there exists a path from `source` to `destination`.  The graph is defined by
+/// the `edges_map`, which maps from a node `S` to a list of its adjacent nodes `T`.
+///
+/// Efficiency note: This is implemented in an inefficient way because it is typically invoked on
+/// very small graphs. If the graphs become larger, a more efficient graph representation and
+/// algorithm would probably be advised.
+#[cfg(not(stage0))]
+pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
+                       destination: T) -> bool
+    where S: HashState, T: Hash + Eq + Clone,
 {
     if source == destination {
         return true;
@@ -206,6 +250,7 @@ pub fn can_reach<T, S>(edges_map: &HashMap<T, Vec<T>, S>, source: T,
 /// }
 /// ```
 #[inline(always)]
+#[cfg(stage0)]
 pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U
     where T: Clone + Hash<<S as HashState>::Hasher> + Eq,
           U: Clone,
@@ -214,6 +259,50 @@ pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) ->
           F: FnOnce(T) -> U,
 {
     let key = arg.clone();
+    let result = cache.borrow().get(&key).cloned();
+    match result {
+        Some(result) => result,
+        None => {
+            let result = f(arg);
+            cache.borrow_mut().insert(key, result.clone());
+            result
+        }
+    }
+}
+/// Memoizes a one-argument closure using the given RefCell containing
+/// a type implementing MutableMap to serve as a cache.
+///
+/// In the future the signature of this function is expected to be:
+/// ```
+/// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
+///    cache: &RefCell<M>,
+///    f: &|T| -> U
+/// ) -> impl |T| -> U {
+/// ```
+/// but currently it is not possible.
+///
+/// # Example
+/// ```
+/// struct Context {
+///    cache: RefCell<HashMap<uint, uint>>
+/// }
+///
+/// fn factorial(ctxt: &Context, n: uint) -> uint {
+///     memoized(&ctxt.cache, n, |n| match n {
+///         0 | 1 => n,
+///         _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
+///     })
+/// }
+/// ```
+#[inline(always)]
+#[cfg(not(stage0))]
+pub fn memoized<T, U, S, F>(cache: &RefCell<HashMap<T, U, S>>, arg: T, f: F) -> U
+    where T: Clone + Hash + Eq,
+          U: Clone,
+          S: HashState,
+          F: FnOnce(T) -> U,
+{
+    let key = arg.clone();
     let result = cache.borrow().get(&key).map(|result| result.clone());
     match result {
         Some(result) => result,