Add a FusedIterator trait.

This trait can be used to avoid the overhead of a fuse wrapper when an iterator
is already well-behaved.

Conforming to: RFC 1581
Closes: #35602

5 files changed, 55 insertions, 3 deletions

diff --git a/src/libstd/ascii.rs b/src/libstd/ascii.rs
index 0db91034eb5..070d7ca1eef 100644
--- a/src/libstd/ascii.rs
+++ b/src/libstd/ascii.rs
@@ -16,6 +16,7 @@ use prelude::v1::*;
 
 use mem;
 use ops::Range;
+use iter::FusedIterator;
 
 /// Extension methods for ASCII-subset only operations on string slices.
 ///
@@ -368,6 +369,9 @@ impl DoubleEndedIterator for EscapeDefault {
 }
 #[stable(feature = "rust1", since = "1.0.0")]
 impl ExactSizeIterator for EscapeDefault {}
+#[unstable(feature = "fused", issue = "35602")]
+impl FusedIterator for EscapeDefault {}
+
 
 static ASCII_LOWERCASE_MAP: [u8; 256] = [
     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index cf6f76f914a..d844a213ce2 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -15,7 +15,7 @@ use borrow::Borrow;
 use cmp::max;
 use fmt::{self, Debug};
 use hash::{Hash, Hasher, BuildHasher, SipHasher13};
-use iter::FromIterator;
+use iter::{FromIterator, FusedIterator};
 use mem::{self, replace};
 use ops::{Deref, Index};
 use rand::{self, Rng};
@@ -1484,6 +1484,9 @@ impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
     type Item = (&'a K, &'a mut V);
@@ -1495,6 +1498,8 @@ impl<'a, K, V> Iterator for IterMut<'a, K, V> {
 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K, V> Iterator for IntoIter<K, V> {
@@ -1507,6 +1512,8 @@ impl<K, V> Iterator for IntoIter<K, V> {
 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<K, V> FusedIterator for IntoIter<K, V> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K, V> Iterator for Keys<'a, K, V> {
@@ -1519,6 +1526,8 @@ impl<'a, K, V> Iterator for Keys<'a, K, V> {
 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K, V> Iterator for Values<'a, K, V> {
@@ -1531,6 +1540,8 @@ impl<'a, K, V> Iterator for Values<'a, K, V> {
 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
 
 #[stable(feature = "map_values_mut", since = "1.10.0")]
 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
@@ -1543,6 +1554,8 @@ impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
 impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K, V> Iterator for Drain<'a, K, V> {
@@ -1555,6 +1568,8 @@ impl<'a, K, V> Iterator for Drain<'a, K, V> {
 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
     #[inline] fn len(&self) -> usize { self.inner.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K, V> FusedIterator for Drain<'a, K, V> {}
 
 impl<'a, K, V> Entry<'a, K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 837c5d8b8e1..96efff86abf 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -11,7 +11,7 @@
 use borrow::Borrow;
 use fmt;
 use hash::{Hash, BuildHasher};
-use iter::{Chain, FromIterator};
+use iter::{Chain, FromIterator, FusedIterator};
 use ops::{BitOr, BitAnd, BitXor, Sub};
 
 use super::Recover;
@@ -906,6 +906,8 @@ impl<'a, K> Iterator for Iter<'a, K> {
 impl<'a, K> ExactSizeIterator for Iter<'a, K> {
     fn len(&self) -> usize { self.iter.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K> FusedIterator for Iter<'a, K> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<K> Iterator for IntoIter<K> {
@@ -918,6 +920,8 @@ impl<K> Iterator for IntoIter<K> {
 impl<K> ExactSizeIterator for IntoIter<K> {
     fn len(&self) -> usize { self.iter.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<K> FusedIterator for IntoIter<K> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K> Iterator for Drain<'a, K> {
@@ -930,6 +934,8 @@ impl<'a, K> Iterator for Drain<'a, K> {
 impl<'a, K> ExactSizeIterator for Drain<'a, K> {
     fn len(&self) -> usize { self.iter.len() }
 }
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, K> FusedIterator for Drain<'a, K> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T, S> Clone for Intersection<'a, T, S> {
@@ -961,6 +967,11 @@ impl<'a, T, S> Iterator for Intersection<'a, T, S>
     }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T, S> FusedIterator for Intersection<'a, T, S>
+    where T: Eq + Hash, S: BuildHasher
+{}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T, S> Clone for Difference<'a, T, S> {
     fn clone(&self) -> Difference<'a, T, S> {
@@ -991,6 +1002,11 @@ impl<'a, T, S> Iterator for Difference<'a, T, S>
     }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T, S> FusedIterator for Difference<'a, T, S>
+    where T: Eq + Hash, S: BuildHasher
+{}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
     fn clone(&self) -> SymmetricDifference<'a, T, S> {
@@ -1008,11 +1024,21 @@ impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
     fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T, S> FusedIterator for SymmetricDifference<'a, T, S>
+    where T: Eq + Hash, S: BuildHasher
+{}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T, S> Clone for Union<'a, T, S> {
     fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T, S> FusedIterator for Union<'a, T, S>
+    where T: Eq + Hash, S: BuildHasher
+{}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T, S> Iterator for Union<'a, T, S>
     where T: Eq + Hash, S: BuildHasher
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index c05e0c3ca68..9807e383c5c 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -232,6 +232,7 @@
 #![feature(float_from_str_radix)]
 #![feature(fn_traits)]
 #![feature(fnbox)]
+#![feature(fused)]
 #![feature(hashmap_hasher)]
 #![feature(heap_api)]
 #![feature(inclusive_range)]
diff --git a/src/libstd/path.rs b/src/libstd/path.rs
index 2d19561139b..bc8fd66a438 100644
--- a/src/libstd/path.rs
+++ b/src/libstd/path.rs
@@ -107,7 +107,7 @@ use fmt;
 use fs;
 use hash::{Hash, Hasher};
 use io;
-use iter;
+use iter::{self, FusedIterator};
 use mem;
 use ops::{self, Deref};
 use string::String;
@@ -858,6 +858,9 @@ impl<'a> DoubleEndedIterator for Iter<'a> {
     }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a> FusedIterator for Iter<'a> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a> Iterator for Components<'a> {
     type Item = Component<'a>;
@@ -958,6 +961,9 @@ impl<'a> DoubleEndedIterator for Components<'a> {
     }
 }
 
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a> FusedIterator for Components<'a> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a> cmp::PartialEq for Components<'a> {
     fn eq(&self, other: &Components<'a>) -> bool {