The fold I wrote by hand and the standard library’s sum() panic in the same place, with the same message. In a release build they produce the same wrong number.
Both of those lines are in this file, one commented out directly above the other:
pub fn sum_of_array(nums: Vec<i32>) -> i32 {
// Iterative
// nums.iter().sum()
// Fold
nums.iter().fold(0, |acc, x| acc + x)
}
I wrote the fold. The sum() is the better line. It says what it does instead of describing how to do it, and it is the one I would reach for if I were writing this fresh.
What I want to write down is the part I did not expect, which is that acc + x compiles at all.
How acc + x compiles at all
In that closure, x has type &i32, not i32. iter() hands out references to the elements. So acc + x is an i32 plus a &i32, and there is no arithmetic operator for that in the obvious sense.
There is one, because the standard library generates it. The core library has a macro that implements the binary operators for every combination of value and reference:
macro_rules! forward_ref_binop {
(impl $imp:ident, $method:ident for $t:ty, $u:ty, $(#[$attr:meta])+) => {
$(#[$attr])+
const impl $imp<$u> for &$t {
type Output = <$t as $imp<$u>>::Output;
#[inline]
#[track_caller]
fn $method(self, other: $u) -> <$t as $imp<$u>>::Output {
$imp::$method(*self, other)
}
}
$(#[$attr])+
const impl $imp<&$u> for $t {
type Output = <$t as $imp<$u>>::Output;
#[inline]
#[track_caller]
fn $method(self, other: &$u) -> <$t as $imp<$u>>::Output {
$imp::$method(self, *other)
}
}
$(#[$attr])+
const impl $imp<&$u> for &$t {
type Output = <$t as $imp<$u>>::Output;
#[inline]
#[track_caller]
fn $method(self, other: &$u) -> <$t as $imp<$u>>::Output {
$imp::$method(*self, *other)
}
}
}
}
The middle one is the one that matters here: impl Add<&i32> for i32. It forwards to the ordinary Add by dereferencing the reference. So acc + x is acc + *x, and the compiler finds it without me naming a trait.
I confirmed this by writing the call out longhand:
let acc: i32 = 10;
let x: &i32 = &5;
let r: i32 = acc + x;
let r2: i32 = <i32 as std::ops::Add<&i32>>::add(acc, x);
Both give 15. The operator syntax is sugar over a trait method that exists for the reference case.
This is the part of Rust that surprised me most when I started writing it. The reference is not a separate numeric type that needs its own arithmetic. It is the same type with a lifetime attached, and the operators are generated for both.
Same panic, different line
Here is the part I care about, and it is the reason I would rather write sum() than the fold even though the fold is what I shipped.
Both versions panic in a debug build when the sum overflows:
thread 'main' panicked at src/main.rs:12:38:
attempt to add with overflow
and this, for sum():
thread 'main' panicked at .../library/core/src/iter/traits/accum.rs:206:1:
attempt to add with overflow
Same panic, same trigger, different source location. The stdlib version panics inside core, mine panics at my line.
And in a release build, both of them quietly lie:
fold = -2147483648
sum = -2147483648
i32::MAX plus one wraps to i32::MIN, and neither version complains. The exit code is 0.
The reason sum() behaves identically is that it is implemented as a fold. The stdlib defines Sum for the integer types with a macro that generates exactly this:
#[$attr]
impl<'a> Sum<&'a $a> for $a {
fn sum<I: Iterator<Item=&'a Self>>(iter: I) -> Self {
iter.fold(
$zero,
#[rustc_inherit_overflow_checks]
|a, b| a + b,
)
}
}
That is fold with the same +. The #[rustc_inherit_overflow_checks] attribute is what makes the stdlib inherit the overflow behavior of whatever crate calls it, so a debug build of my binary gets a debug build’s overflow checks out of code that was compiled with overflow checks off.
Which means the fold I wrote by hand did not avoid the panic that sum() has. It reproduced it. The sum() call is not a safer or an unsafe choice relative to my fold; they are the same computation with the same failure mode. The only thing my hand-written version bought was the chance to be the one that panics at my line number instead of inside core.
The comment says “Iterative”
The comment above sum() says // Iterative. Neither version is iterative in the sense the word usually carries, because sum() is also a fold under the hood, and a fold over an iterator is a loop with the accumulator threaded through it. The comment is a leftover from a different attempt, and it is describing the difference between two shapes that are, in the end, the same shape.
The line I would ship now is the commented-out one:
nums.iter().sum()
One line, no accumulator to name, and the compiler picks the integer type from the return type. The reason I did not ship it is not a good one. I wanted to see the accumulator, so I wrote the accumulator.
The next crate in this series gets sum() and a comment that says what it does.