WeightedIndex produces unexpected results when sum of weights does not fit in the integer type

[tibordp]

WeightedIndex distribution does not explicitely check that the sum of weights fits into the target type X (if it is an integer). When compiling in release mode (with overflow checking disabled), this code will almost always print 0 rather than the expected 1.

use rand::thread_rng;
use rand_distr::{WeightedIndex, Distribution};

fn main() {
    let dist = WeightedIndex::new([2, usize::MAX]).unwrap();
    println!("{}", dist.sample(&mut thread_rng()));
}

I would expect WeightedIndex::new to either return an Err or panic if the sum of weights does not fit into X.

[dhardy]

Reproduced: new panics in debug builds but succeeds in release builds.

The standard way to check for overflow would be using checked_add, unfortunately we can't here: we're using generics over X: SampleUniform + PartialOrd + for<'a> ::core::ops::AddAssign<&'a X> + Clone + Default.

Alternative approach: check that the sum is not less than either operand. This fails in debug builds with a panic instead of an Err(..). I don't like the idea of deliberately introducing deviations between debug and release behaviour, even if it's only different failure modes.

We can't circumvent this with wrapping_add either.

We could use separate impls of new for integer types vs float types, however:

• we can't use traits for this due to overlapping-impl rules (even in practice no impls would overlap)
• we would not be able to cover user-defined types covered by the current generics

So I'm not sure how to solve this!

[dhardy]

Hacky patch: master...dhardy:rand:weighted_index_overflow