Auto merge of #22541 - Manishearth:rollup, r=Gankro 1.0.0-alpha.2

Continued from #22520

4 files changed, 157 insertions, 12 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,
diff --git a/src/librustc/util/lev_distance.rs b/src/librustc/util/lev_distance.rs
index ca1bb7d7a94..10a7b2abea8 100644
--- a/src/librustc/util/lev_distance.rs
+++ b/src/librustc/util/lev_distance.rs
@@ -48,7 +48,7 @@ fn test_lev_distance() {
     for c in (0u32..MAX as u32)
              .filter_map(|i| from_u32(i))
              .map(|i| i.to_string()) {
-        assert_eq!(lev_distance(&c[], &c[]), 0);
+        assert_eq!(lev_distance(&c[..], &c[..]), 0);
     }
 
     let a = "\nMäry häd ä little lämb\n\nLittle lämb\n";
diff --git a/src/librustc/util/nodemap.rs b/src/librustc/util/nodemap.rs
index f8e3defe19d..1b07ce789e7 100644
--- a/src/librustc/util/nodemap.rs
+++ b/src/librustc/util/nodemap.rs
@@ -15,7 +15,8 @@
 use std::collections::hash_state::{DefaultState};
 use std::collections::{HashMap, HashSet};
 use std::default::Default;
-use std::hash::{Hasher, Writer, Hash};
+use std::hash::{Hasher, Hash};
+#[cfg(stage0)] use std::hash::Writer;
 use syntax::ast;
 
 pub type FnvHashMap<K, V> = HashMap<K, V, DefaultState<FnvHasher>>;
@@ -27,12 +28,22 @@ pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
 pub type NodeSet = FnvHashSet<ast::NodeId>;
 pub type DefIdSet = FnvHashSet<ast::DefId>;
 
+#[cfg(stage0)]
 pub fn FnvHashMap<K: Hash<FnvHasher> + Eq, V>() -> FnvHashMap<K, V> {
     Default::default()
 }
+#[cfg(stage0)]
 pub fn FnvHashSet<V: Hash<FnvHasher> + Eq>() -> FnvHashSet<V> {
     Default::default()
 }
+#[cfg(not(stage0))]
+pub fn FnvHashMap<K: Hash + Eq, V>() -> FnvHashMap<K, V> {
+    Default::default()
+}
+#[cfg(not(stage0))]
+pub fn FnvHashSet<V: Hash + Eq>() -> FnvHashSet<V> {
+    Default::default()
+}
 
 pub fn NodeMap<T>() -> NodeMap<T> { FnvHashMap() }
 pub fn DefIdMap<T>() -> DefIdMap<T> { FnvHashMap() }
@@ -52,12 +63,14 @@ impl Default for FnvHasher {
     fn default() -> FnvHasher { FnvHasher(0xcbf29ce484222325) }
 }
 
+#[cfg(stage0)]
 impl Hasher for FnvHasher {
     type Output = u64;
     fn reset(&mut self) { *self = Default::default(); }
     fn finish(&self) -> u64 { self.0 }
 }
 
+#[cfg(stage0)]
 impl Writer for FnvHasher {
     fn write(&mut self, bytes: &[u8]) {
         let FnvHasher(mut hash) = *self;
@@ -68,3 +81,16 @@ impl Writer for FnvHasher {
         *self = FnvHasher(hash);
     }
 }
+
+#[cfg(not(stage0))]
+impl Hasher for FnvHasher {
+    fn write(&mut self, bytes: &[u8]) {
+        let FnvHasher(mut hash) = *self;
+        for byte in bytes {
+            hash = hash ^ (*byte as u64);
+            hash = hash * 0x100000001b3;
+        }
+        *self = FnvHasher(hash);
+    }
+    fn finish(&self) -> u64 { self.0 }
+}
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index d54199a679a..1d46c011bb3 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -28,7 +28,8 @@ use middle::ty_fold::TypeFoldable;
 
 use std::collections::HashMap;
 use std::collections::hash_state::HashState;
-use std::hash::{Hash, Hasher};
+use std::hash::Hash;
+#[cfg(stage0)] use std::hash::Hasher;
 use std::rc::Rc;
 use syntax::abi;
 use syntax::ast_map;
@@ -292,7 +293,7 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
             Some(def_id) => {
                 s.push_str(" {");
                 let path_str = ty::item_path_str(cx, def_id);
-                s.push_str(&path_str[]);
+                s.push_str(&path_str[..]);
                 s.push_str("}");
             }
             None => { }
@@ -376,7 +377,7 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
                 .iter()
                 .map(|elem| ty_to_string(cx, *elem))
                 .collect::<Vec<_>>();
-            match &strs[] {
+            match &strs[..] {
                 [ref string] => format!("({},)", string),
                 strs => format!("({})", strs.connect(", "))
             }
@@ -508,13 +509,26 @@ pub fn parameterized<'tcx,GG>(cx: &ctxt<'tcx>,
     // avoid those ICEs.
     let generics = get_generics();
 
+    let has_self = substs.self_ty().is_some();
     let tps = substs.types.get_slice(subst::TypeSpace);
     let ty_params = generics.types.get_slice(subst::TypeSpace);
     let has_defaults = ty_params.last().map_or(false, |def| def.default.is_some());
     let num_defaults = if has_defaults {
         ty_params.iter().zip(tps.iter()).rev().take_while(|&(def, &actual)| {
             match def.default {
-                Some(default) => default.subst(cx, substs) == actual,
+                Some(default) => {
+                    if !has_self && ty::type_has_self(default) {
+                        // In an object type, there is no `Self`, and
+                        // thus if the default value references Self,
+                        // the user will be required to give an
+                        // explicit value. We can't even do the
+                        // substitution below to check without causing
+                        // an ICE. (#18956).
+                        false
+                    } else {
+                        default.subst(cx, substs) == actual
+                    }
+                }
                 None => false
             }
         }).count()
@@ -625,7 +639,7 @@ impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for [T] {
 
 impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for OwnedSlice<T> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        repr_vec(tcx, &self[])
+        repr_vec(tcx, &self[..])
     }
 }
 
@@ -633,7 +647,7 @@ impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for OwnedSlice<T> {
 // autoderef cannot convert the &[T] handler
 impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for Vec<T> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        repr_vec(tcx, &self[])
+        repr_vec(tcx, &self[..])
     }
 }
 
@@ -673,7 +687,7 @@ impl<'tcx> UserString<'tcx> for TraitAndProjections<'tcx> {
                       &base,
                       trait_ref.substs,
                       trait_ref.def_id,
-                      &projection_bounds[],
+                      &projection_bounds[..],
                       || ty::lookup_trait_def(tcx, trait_ref.def_id).generics.clone())
     }
 }
@@ -1259,7 +1273,7 @@ impl<'tcx, T> UserString<'tcx> for ty::Binder<T>
                 }
             })
         });
-        let names: Vec<_> = names.iter().map(|s| &s[]).collect();
+        let names: Vec<_> = names.iter().map(|s| &s[..]).collect();
 
         let value_str = unbound_value.user_string(tcx);
         if names.len() == 0 {
@@ -1420,6 +1434,7 @@ impl<'tcx, T:Repr<'tcx>> Repr<'tcx> for ty::Binder<T> {
     }
 }
 
+#[cfg(stage0)]
 impl<'tcx, S, K, V> Repr<'tcx> for HashMap<K, V, S>
     where K: Hash<<S as HashState>::Hasher> + Eq + Repr<'tcx>,
           V: Repr<'tcx>,
@@ -1435,6 +1450,21 @@ impl<'tcx, S, K, V> Repr<'tcx> for HashMap<K, V, S>
     }
 }
 
+#[cfg(not(stage0))]
+impl<'tcx, S, K, V> Repr<'tcx> for HashMap<K, V, S>
+    where K: Hash + Eq + Repr<'tcx>,
+          V: Repr<'tcx>,
+          S: HashState,
+{
+    fn repr(&self, tcx: &ctxt<'tcx>) -> String {
+        format!("HashMap({})",
+                self.iter()
+                    .map(|(k,v)| format!("{} => {}", k.repr(tcx), v.repr(tcx)))
+                    .collect::<Vec<String>>()
+                    .connect(", "))
+    }
+}
+
 impl<'tcx, T, U> Repr<'tcx> for ty::OutlivesPredicate<T,U>
     where T : Repr<'tcx> + TypeFoldable<'tcx>,
           U : Repr<'tcx> + TypeFoldable<'tcx>,