Make `sum` and `product` inherent methods on `Iterator`

In addition to being nicer, this also allows you to use `sum` and `product` for
iterators yielding custom types aside from the standard integers.

Due to removing the `AdditiveIterator` and `MultiplicativeIterator` trait, this
is a breaking change.

[breaking-change]

16 files changed, 89 insertions, 189 deletions

diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index ff923fb1906..8622b8cd935 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -85,7 +85,6 @@ use core::clone::Clone;
 use core::cmp::Ordering::{self, Greater, Less};
 use core::cmp::{self, Ord, PartialEq};
 use core::iter::Iterator;
-use core::iter::MultiplicativeIterator;
 use core::marker::Sized;
 use core::mem::size_of;
 use core::mem;
@@ -1182,7 +1181,7 @@ impl Iterator for ElementSwaps {
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         // For a vector of size n, there are exactly n! permutations.
-        let n = (2..self.sdir.len() + 1).product();
+        let n: usize = (2..self.sdir.len() + 1).product();
         (n - self.swaps_made, Some(n - self.swaps_made))
     }
 }
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index c22b6fb9286..c5de430ae8c 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -53,7 +53,6 @@ use self::RecompositionState::*;
 use self::DecompositionType::*;
 
 use core::clone::Clone;
-use core::iter::AdditiveIterator;
 use core::iter::{Iterator, Extend};
 use core::option::Option::{self, Some, None};
 use core::result::Result;
@@ -112,7 +111,7 @@ impl<S: AsRef<str>> SliceConcatExt<str, String> for [S] {
         // this is wrong without the guarantee that `self` is non-empty
         // `len` calculation may overflow but push_str but will check boundaries
         let len = sep.len() * (self.len() - 1)
-            + self.iter().map(|s| s.as_ref().len()).sum();
+            + self.iter().map(|s| s.as_ref().len()).sum::<usize>();
         let mut result = String::with_capacity(len);
         let mut first = true;
 
diff --git a/src/libcollectionstest/str.rs b/src/libcollectionstest/str.rs
index 495a961fa36..63e4005fade 100644
--- a/src/libcollectionstest/str.rs
+++ b/src/libcollectionstest/str.rs
@@ -9,7 +9,6 @@
 // except according to those terms.
 
 use std::cmp::Ordering::{Equal, Greater, Less};
-use std::iter::AdditiveIterator;
 use std::str::{Utf8Error, from_utf8};
 
 #[test]
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 52bad579f47..84726df8fdb 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -65,7 +65,7 @@ use default::Default;
 use marker;
 use mem;
 use num::{Int, Zero, One};
-use ops::{self, Add, Sub, FnMut, RangeFrom};
+use ops::{self, Add, Sub, FnMut, Mul, RangeFrom};
 use option::Option::{self, Some, None};
 use marker::Sized;
 use usize;
@@ -489,15 +489,14 @@ pub trait Iterator {
     ///
     /// ```
     /// # #![feature(core)]
-    /// use std::iter::AdditiveIterator;
     ///
     /// let a = [1, 4, 2, 3, 8, 9, 6];
-    /// let sum = a.iter()
-    ///            .map(|x| *x)
-    ///            .inspect(|&x| println!("filtering {}", x))
-    ///            .filter(|&x| x % 2 == 0)
-    ///            .inspect(|&x| println!("{} made it through", x))
-    ///            .sum();
+    /// let sum: i32 = a.iter()
+    ///                 .map(|x| *x)
+    ///                 .inspect(|&x| println!("filtering {}", x))
+    ///                 .filter(|&x| x % 2 == 0)
+    ///                 .inspect(|&x| println!("{} made it through", x))
+    ///                 .sum();
     /// println!("{}", sum);
     /// ```
     #[inline]
@@ -1022,6 +1021,47 @@ pub trait Iterator {
             }
         }
     }
+
+    /// Iterates over the entire iterator, summing up all the elements
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(core)]
+    ///
+    /// let a = [1, 2, 3, 4, 5];
+    /// let mut it = a.iter().cloned();
+    /// assert!(it.sum::<i32>() == 15);
+    /// ```
+    #[unstable(feature="core")]
+    fn sum<S=<Self as Iterator>::Item>(self) -> S where
+        S: Add<Self::Item, Output=S> + Zero,
+        Self: Sized,
+    {
+        self.fold(Zero::zero(), |s, e| s + e)
+    }
+
+    /// Iterates over the entire iterator, multiplying all the elements
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(core)]
+    ///
+    /// fn factorial(n: u32) -> u32 {
+    ///     (1..).take_while(|&i| i <= n).product()
+    /// }
+    /// assert!(factorial(0) == 1);
+    /// assert!(factorial(1) == 1);
+    /// assert!(factorial(5) == 120);
+    /// ```
+    #[unstable(feature="core")]
+    fn product<P=<Self as Iterator>::Item>(self) -> P where
+        P: Mul<Self::Item, Output=P> + One,
+        Self: Sized,
+    {
+        self.fold(One::one(), |p, e| p * e)
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1222,151 +1262,6 @@ impl<I> RandomAccessIterator for Rev<I>
     }
 }
 
-/// A trait for iterators over elements which can be added together
-#[unstable(feature = "core",
-           reason = "needs to be re-evaluated as part of numerics reform")]
-pub trait AdditiveIterator {
-    /// The result of summing over the iterator.
-    type SumResult;
-
-    /// Iterates over the entire iterator, summing up all the elements
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// # #![feature(core)]
-    /// use std::iter::AdditiveIterator;
-    ///
-    /// let a = [1, 2, 3, 4, 5];
-    /// let mut it = a.iter().cloned();
-    /// assert!(it.sum() == 15);
-    /// ```
-    fn sum(self) -> Self::SumResult;
-}
-
-/// The sum operation of an iterator's item type. Implementing this allows
-/// calling `.sum()` on the iterator.
-#[unstable(feature = "core", reason = "trait is experimental")]
-pub trait AdditiveIteratorItem {
-    /// The type of the intermediate sums.
-    type SumResult;
-    /// The start value of the sum, usually something like `0`.
-    fn start() -> Self::SumResult;
-    /// Adds another element of the iterator to the intermediate sum.
-    fn combine(self, other: Self::SumResult) -> Self::SumResult;
-}
-
-#[unstable(feature = "core", reason = "trait is experimental")]
-impl<I: Iterator> AdditiveIterator for I where
-    <I as Iterator>::Item: AdditiveIteratorItem
-{
-    type SumResult = <<I as Iterator>::Item as AdditiveIteratorItem>::SumResult;
-    fn sum(self) -> <I as AdditiveIterator>::SumResult {
-        let mut sum = <<I as Iterator>::Item as AdditiveIteratorItem>::start();
-        for x in self {
-            sum = x.combine(sum);
-        }
-        sum
-    }
-}
-
-macro_rules! impl_additive {
-    ($T:ty, $init:expr) => {
-        #[unstable(feature = "core", reason = "trait is experimental")]
-        impl AdditiveIteratorItem for $T {
-            type SumResult = $T;
-            fn start() -> $T { $init }
-            fn combine(self, other: $T) -> $T { self + other }
-        }
-    };
-}
-impl_additive! { i8,    0 }
-impl_additive! { i16,   0 }
-impl_additive! { i32,   0 }
-impl_additive! { i64,   0 }
-impl_additive! { isize, 0 }
-impl_additive! { u8,    0 }
-impl_additive! { u16,   0 }
-impl_additive! { u32,   0 }
-impl_additive! { u64,   0 }
-impl_additive! { usize, 0 }
-impl_additive! { f32,   0.0 }
-impl_additive! { f64,   0.0 }
-
-/// A trait for iterators over elements which can be multiplied together.
-#[unstable(feature = "core",
-           reason = "needs to be re-evaluated as part of numerics reform")]
-pub trait MultiplicativeIterator {
-    /// The result of multiplying the elements of the iterator.
-    type ProductResult;
-
-    /// Iterates over the entire iterator, multiplying all the elements
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// # #![feature(core)]
-    /// use std::iter::MultiplicativeIterator;
-    ///
-    /// fn factorial(n: usize) -> usize {
-    ///     (1..).take_while(|&i| i <= n).product()
-    /// }
-    /// assert!(factorial(0) == 1);
-    /// assert!(factorial(1) == 1);
-    /// assert!(factorial(5) == 120);
-    /// ```
-    fn product(self) -> Self::ProductResult;
-}
-
-/// The product operation of an iterator's item type. Implementing this allows
-/// calling `.product()` on the iterator.
-#[unstable(feature = "core", reason = "trait is experimental")]
-pub trait MultiplicativeIteratorItem {
-    /// The type of the intermediate products.
-    type ProductResult;
-    /// The start value of the product, usually something like `1`.
-    fn start() -> Self::ProductResult;
-    /// Multiplies another element of the iterator to the intermediate product.
-    fn combine(self, other: Self::ProductResult) -> Self::ProductResult;
-}
-
-#[unstable(feature = "core", reason = "trait is experimental")]
-impl<I: Iterator> MultiplicativeIterator for I where
-    <I as Iterator>::Item: MultiplicativeIteratorItem
-{
-    type ProductResult = <<I as Iterator>::Item as MultiplicativeIteratorItem>::ProductResult;
-    fn product(self) -> <I as MultiplicativeIterator>::ProductResult {
-        let mut product = <<I as Iterator>::Item as MultiplicativeIteratorItem>::start();
-        for x in self {
-            product = x.combine(product);
-        }
-        product
-    }
-}
-
-macro_rules! impl_multiplicative  {
-    ($T:ty, $init:expr) => {
-        #[unstable(feature = "core", reason = "trait is experimental")]
-        impl MultiplicativeIteratorItem for $T {
-            type ProductResult = $T;
-            fn start() -> $T { $init }
-            fn combine(self, other: $T) -> $T { self * other }
-        }
-    };
-}
-impl_multiplicative! { i8,    1 }
-impl_multiplicative! { i16,   1 }
-impl_multiplicative! { i32,   1 }
-impl_multiplicative! { i64,   1 }
-impl_multiplicative! { isize, 1 }
-impl_multiplicative! { u8,    1 }
-impl_multiplicative! { u16,   1 }
-impl_multiplicative! { u32,   1 }
-impl_multiplicative! { u64,   1 }
-impl_multiplicative! { usize, 1 }
-impl_multiplicative! { f32,  1.0 }
-impl_multiplicative! { f64,  1.0 }
-
 /// `MinMaxResult` is an enum returned by `min_max`. See `Iterator::min_max` for
 /// more detail.
 #[derive(Clone, PartialEq, Debug)]
diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs
index 28e0bcf13dd..7868e299cfc 100644
--- a/src/libcore/num/mod.rs
+++ b/src/libcore/num/mod.rs
@@ -86,6 +86,20 @@ macro_rules! zero_one_impl {
 }
 zero_one_impl! { u8 u16 u32 u64 usize i8 i16 i32 i64 isize }
 
+macro_rules! zero_one_impl_float {
+    ($($t:ty)*) => ($(
+        impl Zero for $t {
+            #[inline]
+            fn zero() -> $t { 0.0 }
+        }
+        impl One for $t {
+            #[inline]
+            fn one() -> $t { 1.0 }
+        }
+    )*)
+}
+zero_one_impl_float! { f32 f64 }
+
 /// A built-in signed or unsigned integer.
 #[stable(feature = "rust1", since = "1.0.0")]
 #[deprecated(since = "1.0.0",
diff --git a/src/libcoretest/iter.rs b/src/libcoretest/iter.rs
index af80d347f02..bfa9c798d35 100644
--- a/src/libcoretest/iter.rs
+++ b/src/libcoretest/iter.rs
@@ -329,17 +329,17 @@ fn test_iterator_len() {
 #[test]
 fn test_iterator_sum() {
     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-    assert_eq!(v[..4].iter().cloned().sum(), 6);
-    assert_eq!(v.iter().cloned().sum(), 55);
-    assert_eq!(v[..0].iter().cloned().sum(), 0);
+    assert_eq!(v[..4].iter().cloned().sum::<i32>(), 6);
+    assert_eq!(v.iter().cloned().sum::<i32>(), 55);
+    assert_eq!(v[..0].iter().cloned().sum::<i32>(), 0);
 }
 
 #[test]
 fn test_iterator_product() {
     let v: &[i32] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-    assert_eq!(v[..4].iter().cloned().product(), 0);
-    assert_eq!(v[1..5].iter().cloned().product(), 24);
-    assert_eq!(v[..0].iter().cloned().product(), 1);
+    assert_eq!(v[..4].iter().cloned().product::<i32>(), 0);
+    assert_eq!(v[1..5].iter().cloned().product::<i32>(), 24);
+    assert_eq!(v[..0].iter().cloned().product::<i32>(), 1);
 }
 
 #[test]
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index 79f4d62b45e..14df040fb79 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -26,7 +26,7 @@ use middle::ty::*;
 use middle::ty;
 use std::cmp::Ordering;
 use std::fmt;
-use std::iter::{range_inclusive, AdditiveIterator, FromIterator, IntoIterator, repeat};
+use std::iter::{range_inclusive, FromIterator, IntoIterator, repeat};
 use std::slice;
 use syntax::ast::{self, DUMMY_NODE_ID, NodeId, Pat};
 use syntax::ast_util;
@@ -76,7 +76,7 @@ impl<'a> fmt::Debug for Matrix<'a> {
             pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0)
         }).collect();
 
-        let total_width = column_widths.iter().cloned().sum() + column_count * 3 + 1;
+        let total_width = column_widths.iter().cloned().sum::<usize>() + column_count * 3 + 1;
         let br = repeat('+').take(total_width).collect::<String>();
         try!(write!(f, "{}\n", br));
         for row in pretty_printed_matrix {
diff --git a/src/librustc_trans/trans/_match.rs b/src/librustc_trans/trans/_match.rs
index ef599a01e7c..15d296f71bd 100644
--- a/src/librustc_trans/trans/_match.rs
+++ b/src/librustc_trans/trans/_match.rs
@@ -220,7 +220,6 @@ use util::ppaux::{Repr, vec_map_to_string};
 
 use std;
 use std::cmp::Ordering;
-use std::iter::AdditiveIterator;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::ast::{DUMMY_NODE_ID, Ident, NodeId};
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 939142cff1c..7a93873af03 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -61,7 +61,7 @@ use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
 use util::common::{ErrorReported, FN_OUTPUT_NAME};
 use util::ppaux::{self, Repr, UserString};
 
-use std::iter::{repeat, AdditiveIterator};
+use std::iter::repeat;
 use std::rc::Rc;
 use std::slice;
 use syntax::{abi, ast, ast_util};
@@ -517,12 +517,13 @@ fn find_implied_output_region(input_tys: &[Ty], input_pats: Vec<String>)
         lifetimes_for_params.push((input_pat, accumulator.len()));
     }
 
-    let implied_output_region = if lifetimes_for_params.iter().map(|&(_, n)| n).sum() == 1 {
-        assert!(possible_implied_output_region.is_some());
-        possible_implied_output_region
-    } else {
-        None
-    };
+    let implied_output_region =
+        if lifetimes_for_params.iter().map(|&(_, n)| n).sum::<usize>() == 1 {
+            assert!(possible_implied_output_region.is_some());
+            possible_implied_output_region
+        } else {
+            None
+        };
     (implied_output_region, lifetimes_for_params)
 }
 
diff --git a/src/libstd/old_path/posix.rs b/src/libstd/old_path/posix.rs
index c517fab257f..af63be2aa9e 100644
--- a/src/libstd/old_path/posix.rs
+++ b/src/libstd/old_path/posix.rs
@@ -15,8 +15,7 @@ use cmp::{Ordering, Eq, Ord, PartialEq, PartialOrd};
 use fmt;
 use hash;
 use old_io::Writer;
-use iter::{AdditiveIterator, Extend};
-use iter::{Iterator, Map};
+use iter::{Extend, Iterator, Map};
 use marker::Sized;
 use option::Option::{self, Some, None};
 use result::Result::{self, Ok, Err};
@@ -351,7 +350,7 @@ impl Path {
                         Some(vec![SEP_BYTE])
                     } else {
                         let n = if is_abs { comps.len() } else { comps.len() - 1} +
-                                comps.iter().map(|v| v.len()).sum();
+                                comps.iter().map(|v| v.len()).sum::<usize>();
                         let mut v = Vec::with_capacity(n);
                         let mut it = comps.into_iter();
                         if !is_abs {
diff --git a/src/libstd/old_path/windows.rs b/src/libstd/old_path/windows.rs
index 0b88f368b39..65aad38a2b4 100644
--- a/src/libstd/old_path/windows.rs
+++ b/src/libstd/old_path/windows.rs
@@ -20,8 +20,7 @@ use cmp::{Ordering, Eq, Ord, PartialEq, PartialOrd};
 use fmt;
 use hash;
 use old_io::Writer;
-use iter::{AdditiveIterator, Extend};
-use iter::{Iterator, Map, repeat};
+use iter::{Extend, Iterator, Map, repeat};
 use mem;
 use option::Option::{self, Some, None};
 use result::Result::{self, Ok, Err};
@@ -785,7 +784,7 @@ impl Path {
                         let prefix_ = &s[..prefix_len(prefix)];
                         let n = prefix_.len() +
                                 if is_abs { comps.len() } else { comps.len() - 1} +
-                                comps.iter().map(|v| v.len()).sum();
+                                comps.iter().map(|v| v.len()).sum::<usize>();
                         let mut s = String::with_capacity(n);
                         match prefix {
                             Some(DiskPrefix) => {
diff --git a/src/libunicode/u_str.rs b/src/libunicode/u_str.rs
index 3f9dd8ab635..2af94bf30b1 100644
--- a/src/libunicode/u_str.rs
+++ b/src/libunicode/u_str.rs
@@ -20,7 +20,7 @@ use core::prelude::*;
 
 use core::char;
 use core::cmp;
-use core::iter::{Filter, AdditiveIterator};
+use core::iter::Filter;
 use core::mem;
 use core::slice;
 use core::str::Split;
diff --git a/src/rustbook/book.rs b/src/rustbook/book.rs
index a08481f8be9..2d630d8fe8d 100644
--- a/src/rustbook/book.rs
+++ b/src/rustbook/book.rs
@@ -13,7 +13,6 @@
 use std::io::prelude::*;
 use std::io::BufReader;
 use std::iter;
-use std::iter::AdditiveIterator;
 use std::path::{Path, PathBuf};
 
 pub struct BookItem {
@@ -151,7 +150,7 @@ pub fn parse_summary(input: &mut Read, src: &Path) -> Result<Book, Vec<String>>
                 '\t' => 4,
                 _ => unreachable!()
             }
-        }).sum() / 4 + 1;
+        }).sum::<usize>() / 4 + 1;
 
         if level > stack.len() + 1 {
             errors.push(format!("section '{}' is indented too deeply; \
diff --git a/src/test/bench/shootout-spectralnorm.rs b/src/test/bench/shootout-spectralnorm.rs
index c0268e816cf..5fcbe773299 100644
--- a/src/test/bench/shootout-spectralnorm.rs
+++ b/src/test/bench/shootout-spectralnorm.rs
@@ -43,7 +43,7 @@
 #![allow(non_snake_case)]
 #![feature(unboxed_closures, core, os)]
 
-use std::iter::{repeat, AdditiveIterator};
+use std::iter::repeat;
 use std::thread;
 use std::mem;
 use std::num::Float;
diff --git a/src/test/run-pass/issue-15673.rs b/src/test/run-pass/issue-15673.rs
index 6c76f1595dc..c1ecd3eba48 100644
--- a/src/test/run-pass/issue-15673.rs
+++ b/src/test/run-pass/issue-15673.rs
@@ -12,8 +12,7 @@
 
 #![feature(core)]
 
-use std::iter::AdditiveIterator;
 fn main() {
     let x: [u64; 3] = [1, 2, 3];
-    assert_eq!(6, (0..3).map(|i| x[i]).sum());
+    assert_eq!(6, (0..3).map(|i| x[i]).sum::<u64>());
 }
diff --git a/src/test/run-pass/iter-cloned-type-inference.rs b/src/test/run-pass/iter-cloned-type-inference.rs
index 12f6a7caf6c..d1f63564979 100644
--- a/src/test/run-pass/iter-cloned-type-inference.rs
+++ b/src/test/run-pass/iter-cloned-type-inference.rs
@@ -15,10 +15,8 @@
 
 #![feature(core)]
 
-use std::iter::AdditiveIterator;
-
 fn square_sum(v: &[i64]) -> i64 {
-    let sum = v.iter().cloned().sum();
+    let sum: i64 = v.iter().cloned().sum();
     sum * sum
 }