rollup merge of #23601: nikomatsakis/by-value-index

This is a [breaking-change]. When indexing a generic map (hashmap, etc) using the `[]` operator, it is now necessary to borrow explicitly, so change `map[key]` to `map[&key]` (consistent with the `get` routine). However, indexing of string-valued maps with constant strings can now be written `map["abc"]`.

r? @japaric
cc @aturon @Gankro

7 files changed, 259 insertions, 3 deletions

diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index 90fbe04d348..e494527b6a6 100644
--- a/src/libcollections/bit.rs
+++ b/src/libcollections/bit.rs
@@ -169,6 +169,8 @@ pub struct BitVec {
 impl Index<usize> for BitVec {
     type Output = bool;
 
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, i: &usize) -> &bool {
         if self.get(*i).expect("index out of bounds") {
@@ -177,6 +179,16 @@ impl Index<usize> for BitVec {
             &FALSE
         }
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, i: usize) -> &bool {
+        if self.get(i).expect("index out of bounds") {
+            &TRUE
+        } else {
+            &FALSE
+        }
+    }
 }
 
 /// Computes how many blocks are needed to store that many bits
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index a9e1ce8d7ce..755f564621a 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -264,7 +264,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     ///     Some(x) => *x = "b",
     ///     None => (),
     /// }
-    /// assert_eq!(map[1], "b");
+    /// assert_eq!(map[&1], "b");
     /// ```
     // See `get` for implementation notes, this is basically a copy-paste with mut's added
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -326,7 +326,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     ///
     /// map.insert(37, "b");
     /// assert_eq!(map.insert(37, "c"), Some("b"));
-    /// assert_eq!(map[37], "c");
+    /// assert_eq!(map[&37], "c");
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
@@ -914,12 +914,27 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
     }
 }
 
+#[cfg(stage0)]
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V>
     where K: Borrow<Q>, Q: Ord
 {
     type Output = V;
 
+    #[inline]
+    fn index(&self, key: &Q) -> &V {
+        self.get(key).expect("no entry found for key")
+    }
+}
+
+#[cfg(not(stage0))]
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
+    where K: Borrow<Q>, Q: Ord
+{
+    type Output = V;
+
+    #[inline]
     fn index(&self, key: &Q) -> &V {
         self.get(key).expect("no entry found for key")
     }
diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs
index bfac3b2df5a..5b8a5f02976 100644
--- a/src/libcollections/btree/node.rs
+++ b/src/libcollections/btree/node.rs
@@ -1522,6 +1522,7 @@ macro_rules! node_slice_impl {
             }
 
             /// Returns a sub-slice with elements starting with `min_key`.
+            #[cfg(stage0)]
             pub fn slice_from(self, min_key: &K) -> $NodeSlice<'a, K, V> {
                 //  _______________
                 // |_1_|_3_|_5_|_7_|
@@ -1549,7 +1550,37 @@ macro_rules! node_slice_impl {
                 }
             }
 
+            /// Returns a sub-slice with elements starting with `min_key`.
+            #[cfg(not(stage0))]
+            pub fn slice_from(self, min_key: &K) -> $NodeSlice<'a, K, V> {
+                //  _______________
+                // |_1_|_3_|_5_|_7_|
+                // |   |   |   |   |
+                // 0 0 1 1 2 2 3 3 4  index
+                // |   |   |   |   |
+                // \___|___|___|___/  slice_from(&0); pos = 0
+                //     \___|___|___/  slice_from(&2); pos = 1
+                //     |___|___|___/  slice_from(&3); pos = 1; result.head_is_edge = false
+                //         \___|___/  slice_from(&4); pos = 2
+                //             \___/  slice_from(&6); pos = 3
+                //                \|/ slice_from(&999); pos = 4
+                let (pos, pos_is_kv) = self.search_linear(min_key);
+                $NodeSlice {
+                    has_edges: self.has_edges,
+                    edges: if !self.has_edges {
+                        self.edges
+                    } else {
+                        self.edges.$index(pos ..)
+                    },
+                    keys: &self.keys[pos ..],
+                    vals: self.vals.$index(pos ..),
+                    head_is_edge: !pos_is_kv,
+                    tail_is_edge: self.tail_is_edge,
+                }
+            }
+
             /// Returns a sub-slice with elements up to and including `max_key`.
+            #[cfg(stage0)]
             pub fn slice_to(self, max_key: &K) -> $NodeSlice<'a, K, V> {
                 //  _______________
                 // |_1_|_3_|_5_|_7_|
@@ -1577,6 +1608,36 @@ macro_rules! node_slice_impl {
                     tail_is_edge: !pos_is_kv,
                 }
             }
+
+            /// Returns a sub-slice with elements up to and including `max_key`.
+            #[cfg(not(stage0))]
+            pub fn slice_to(self, max_key: &K) -> $NodeSlice<'a, K, V> {
+                //  _______________
+                // |_1_|_3_|_5_|_7_|
+                // |   |   |   |   |
+                // 0 0 1 1 2 2 3 3 4  index
+                // |   |   |   |   |
+                //\|/  |   |   |   |  slice_to(&0); pos = 0
+                // \___/   |   |   |  slice_to(&2); pos = 1
+                // \___|___|   |   |  slice_to(&3); pos = 1; result.tail_is_edge = false
+                // \___|___/   |   |  slice_to(&4); pos = 2
+                // \___|___|___/   |  slice_to(&6); pos = 3
+                // \___|___|___|___/  slice_to(&999); pos = 4
+                let (pos, pos_is_kv) = self.search_linear(max_key);
+                let pos = pos + if pos_is_kv { 1 } else { 0 };
+                $NodeSlice {
+                    has_edges: self.has_edges,
+                    edges: if !self.has_edges {
+                        self.edges
+                    } else {
+                        self.edges.$index(.. (pos + 1))
+                    },
+                    keys: &self.keys[..pos],
+                    vals: self.vals.$index(.. pos),
+                    head_is_edge: self.head_is_edge,
+                    tail_is_edge: !pos_is_kv,
+                }
+            }
         }
 
         impl<'a, K: 'a, V: 'a> $NodeSlice<'a, K, V> {
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index a5d788143b0..0d55dc7dba9 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -891,34 +891,66 @@ impl<'a> Add<&'a str> for String {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl ops::Index<ops::Range<usize>> for String {
     type Output = str;
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::Range<usize>) -> &str {
         &self[..][*index]
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::Range<usize>) -> &str {
+        &self[..][index]
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl ops::Index<ops::RangeTo<usize>> for String {
     type Output = str;
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::RangeTo<usize>) -> &str {
         &self[..][*index]
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::RangeTo<usize>) -> &str {
+        &self[..][index]
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl ops::Index<ops::RangeFrom<usize>> for String {
     type Output = str;
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::RangeFrom<usize>) -> &str {
         &self[..][*index]
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::RangeFrom<usize>) -> &str {
+        &self[..][index]
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl ops::Index<ops::RangeFull> for String {
     type Output = str;
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, _index: &ops::RangeFull) -> &str {
         unsafe { mem::transmute(&*self.vec) }
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, _index: ops::RangeFull) -> &str {
+        unsafe { mem::transmute(&*self.vec) }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 85833c34049..1d76224bd84 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1323,83 +1323,165 @@ impl<T: Hash> Hash for Vec<T> {
 impl<T> Index<usize> for Vec<T> {
     type Output = T;
 
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &usize) -> &T {
         // NB built-in indexing via `&[T]`
         &(**self)[*index]
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: usize) -> &T {
+        // NB built-in indexing via `&[T]`
+        &(**self)[index]
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> IndexMut<usize> for Vec<T> {
+
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, index: &usize) -> &mut T {
         // NB built-in indexing via `&mut [T]`
         &mut (**self)[*index]
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, index: usize) -> &mut T {
+        // NB built-in indexing via `&mut [T]`
+        &mut (**self)[index]
+    }
 }
 
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::Index<ops::Range<usize>> for Vec<T> {
     type Output = [T];
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::Range<usize>) -> &[T] {
         Index::index(&**self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::Range<usize>) -> &[T] {
+        Index::index(&**self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::Index<ops::RangeTo<usize>> for Vec<T> {
     type Output = [T];
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::RangeTo<usize>) -> &[T] {
         Index::index(&**self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
+        Index::index(&**self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::Index<ops::RangeFrom<usize>> for Vec<T> {
     type Output = [T];
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, index: &ops::RangeFrom<usize>) -> &[T] {
         Index::index(&**self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
+        Index::index(&**self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::Index<ops::RangeFull> for Vec<T> {
     type Output = [T];
+
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, _index: &ops::RangeFull) -> &[T] {
         self
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, _index: ops::RangeFull) -> &[T] {
+        self.as_slice()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::IndexMut<ops::Range<usize>> for Vec<T> {
+
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, index: &ops::Range<usize>) -> &mut [T] {
         IndexMut::index_mut(&mut **self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
+        IndexMut::index_mut(&mut **self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::IndexMut<ops::RangeTo<usize>> for Vec<T> {
+
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, index: &ops::RangeTo<usize>) -> &mut [T] {
         IndexMut::index_mut(&mut **self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
+        IndexMut::index_mut(&mut **self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for Vec<T> {
+
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, index: &ops::RangeFrom<usize>) -> &mut [T] {
         IndexMut::index_mut(&mut **self, index)
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
+        IndexMut::index_mut(&mut **self, index)
+    }
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ops::IndexMut<ops::RangeFull> for Vec<T> {
+
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, _index: &ops::RangeFull) -> &mut [T] {
         self.as_mut_slice()
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, _index: ops::RangeFull) -> &mut [T] {
+        self.as_mut_slice()
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs
index 56ca74dab1f..591ad48f579 100644
--- a/src/libcollections/vec_deque.rs
+++ b/src/libcollections/vec_deque.rs
@@ -1689,18 +1689,32 @@ impl<A: Hash> Hash for VecDeque<A> {
 impl<A> Index<usize> for VecDeque<A> {
     type Output = A;
 
+    #[cfg(stage0)]
     #[inline]
     fn index(&self, i: &usize) -> &A {
         self.get(*i).expect("Out of bounds access")
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index(&self, i: usize) -> &A {
+        self.get(i).expect("Out of bounds access")
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A> IndexMut<usize> for VecDeque<A> {
+    #[cfg(stage0)]
     #[inline]
     fn index_mut(&mut self, i: &usize) -> &mut A {
         self.get_mut(*i).expect("Out of bounds access")
     }
+
+    #[cfg(not(stage0))]
+    #[inline]
+    fn index_mut(&mut self, i: usize) -> &mut A {
+        self.get_mut(i).expect("Out of bounds access")
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs
index 6e67d876327..05693ec5275 100644
--- a/src/libcollections/vec_map.rs
+++ b/src/libcollections/vec_map.rs
@@ -798,6 +798,7 @@ impl<V> Extend<(usize, V)> for VecMap<V> {
     }
 }
 
+#[cfg(stage0)]
 impl<V> Index<usize> for VecMap<V> {
     type Output = V;
 
@@ -807,10 +808,49 @@ impl<V> Index<usize> for VecMap<V> {
     }
 }
 
+#[cfg(not(stage0))]
+impl<V> Index<usize> for VecMap<V> {
+    type Output = V;
+
+    #[inline]
+    fn index<'a>(&'a self, i: usize) -> &'a V {
+        self.get(&i).expect("key not present")
+    }
+}
+
+#[cfg(not(stage0))]
+impl<'a,V> Index<&'a usize> for VecMap<V> {
+    type Output = V;
+
+    #[inline]
+    fn index(&self, i: &usize) -> &V {
+        self.get(i).expect("key not present")
+    }
+}
+
+#[cfg(stage0)]
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<V> IndexMut<usize> for VecMap<V> {
+    #[inline]
+    fn index_mut(&mut self, i: &usize) -> &mut V {
+        self.get_mut(&i).expect("key not present")
+    }
+}
+
+#[cfg(not(stage0))]
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<V> IndexMut<usize> for VecMap<V> {
     #[inline]
-    fn index_mut<'a>(&'a mut self, i: &usize) -> &'a mut V {
+    fn index_mut(&mut self, i: usize) -> &mut V {
+        self.get_mut(&i).expect("key not present")
+    }
+}
+
+#[cfg(not(stage0))]
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, V> IndexMut<&'a usize> for VecMap<V> {
+    #[inline]
+    fn index_mut(&mut self, i: &usize) -> &mut V {
         self.get_mut(i).expect("key not present")
     }
 }