rust-random / rand

A Rust library for random number generation.
https://crates.io/crates/rand
Other
1.68k stars 430 forks source link

Trap weighted index overflow #1353

Closed dhardy closed 11 months ago

dhardy commented 1 year ago

Closes #1309. This approach is likely sub-optimal but without significant overhead (not benchmarked), and only to a distribution constructor.

dhardy commented 12 months ago

So cargo test fails: Rust detects an overflow in total_weight += w.borrow(); on debug builds.

We want checked_add here, but (like many things) there's no trait for that in std. (There is in num-traits.)

Alternative: use wrapping_add to disable the built-in overflow check, then manually check. But again, no trait. Instead, we can use core::num::Wrapping... but the method needs to support f32 which Wrapping does not.

So I think it comes down to:

  1. Depend on num-traits in rand (currently only rand_distr depends on this)
  2. Or add our own trait (already used in other places, e.g. Float).

I opted for the second choice here:

/// Bounds on a weight
///
/// See usage in [`WeightedIndex`].
pub trait Weight: Clone {
    /// Representation of 0
    const ZERO: Self;

    /// Checked addition
    ///
    /// -   `Result::Ok`: On success, `v` is added to `self`
    /// -   `Result::Err`: Returns an error when `Self` cannot represent the
    ///     result of `self + v` (i.e. overflow). The value of `self` should be
    ///     discarded.
    fn checked_add_assign(&mut self, v: &Self) -> Result<(), ()>;
}
dhardy commented 12 months ago

What this omits: the impls of checked_add_assign for float types always succeed since floats "overload to INF representation". It may be better for our use-case to error here.

Also: the signature of checked_add_assign is tailored to our use-case and differs from e.g. num_traits::ops::checked::CheckedAdd.

vks commented 11 months ago

I really like the simplified trait bounds!

My only concern is that Weight is public: Almost any change to it will be a breaking change.