Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

distributions/uniform: fix panic in gen_range(0..=MAX) #1087

Conversation

mautier
Copy link
Contributor

@mautier mautier commented Jan 12, 2021

This commit fixes a panic when generating a single sample in an
inclusive range that spans the entire integer range, eg for u8:

rng.gen_range(0..=u8::MAX)
// panicked at 'attempt to add with overflow', src/distributions/uniform.rs:529:42

Playground example.

The cause is a discrepancy between the "single sample" and the "many
samples" codepaths:

// Ok
UniformSampler::new_inclusive(u8::MIN, u8::MAX).sample(&mut rng);
// Panic
UniformSampler::sample_single_inclusive(u8::MIN, u8::MAX, &mut rng);

In sample, a range of 0 is interpreted to mean "sample from the
whole range" (documented here)
In sample_range_inclusive, no check is performed, which leads to
overflow when computing the ints_to_reject.

Testing

  • Added a test case.
  • Old code panics, new code passes.

This commit fixes a panic when generating a single sample in an
inclusive range that spans the entire integer range, eg for u8:
```rust
rng.gen_range(0..=u8::MAX)
// panicked at 'attempt to add with overflow', src/distributions/uniform.rs:529:42
```
[Playground example](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&code=use%20rand%3A%3ARng%3B%0A%0Afn%20main()%20%7B%0A%20%20%20%20rand%3A%3Athread_rng().gen_range(0u8..%3D255u8)%3B%0A%7D).

The cause is a discrepancy between the "single sample" and the "many
samples" codepaths:
```rust
// Ok
UniformSampler::new_inclusive(u8::MIN, u8::MAX).sample(&mut rng);
// Panic
UniformSampler::sample_single_inclusive(u8::MIN, u8::MAX, &mut rng);
```
In `sample`, a `range` of 0 is interpreted to mean "sample from the
whole range".
In `sample_range_inclusive`, no check is performed, which leads to
overflow when computing the `ints_to_reject`.

**Testing**
- Added a test case.
- Old code panics, new code passes.
@mautier mautier marked this pull request as ready for review January 12, 2021 16:17
Copy link
Member

@dhardy dhardy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good to me.

Can you please bump the patch version and add a note in the changelog?

@mautier
Copy link
Contributor Author

mautier commented Jan 12, 2021

@dhardy Done! Let me know if you want me to change or add anything else.

@mautier mautier force-pushed the fix_uniform_int_panic_on_full_inclusive_range branch from 3d2312b to 2c9085a Compare January 12, 2021 23:16
@mautier
Copy link
Contributor Author

mautier commented Jan 12, 2021

One of the CI actions failed due to an unrelated error (issue when installing apt packages); I haven't been able to find a retry button anywhere, so I just repushed the latest commit.

@dhardy
Copy link
Member

dhardy commented Jan 13, 2021

Yeah, I think only project admins get a retry button. Looks perfect, thanks!

@dhardy dhardy merged commit 6a6b9fd into rust-random:master Jan 13, 2021
bors bot added a commit to comit-network/comit-rs that referenced this pull request Mar 17, 2021
3538: Bump rand from 0.8.1 to 0.8.3 r=mergify[bot] a=dependabot[bot]

Bumps [rand](https://github.com/rust-random/rand) from 0.8.1 to 0.8.3.
<details>
<summary>Changelog</summary>
<p><em>Sourced from <a href="https://github.com/rust-random/rand/blob/master/CHANGELOG.md">rand's changelog</a>.</em></p>
<blockquote>
<h2>[0.8.3] - 2021-01-25</h2>
<h3>Fixes</h3>
<ul>
<li>Fix <code>no-std</code> + <code>alloc</code> build by gating <code>choose_multiple_weighted</code> on <code>std</code> (<a href="https://github.com/rust-random/rand/issues/1088">#1088</a>)</li>
</ul>
<h2>[0.8.2] - 2021-01-12</h2>
<h3>Fixes</h3>
<ul>
<li>Fix panic in <code>UniformInt::sample_single_inclusive</code> and <code>Rng::gen_range</code> when
providing a full integer range (eg <code>0..=MAX</code>) (<a href="https://github.com/rust-random/rand/issues/1087">#1087</a>)</li>
</ul>
</blockquote>
</details>
<details>
<summary>Commits</summary>
<ul>
<li><a href="https://github.com/rust-random/rand/commit/6ecbe2626b2cc6110a25c97b1702b347574febc7"><code>6ecbe26</code></a> Merge pull request <a href="https://github.com/rust-random/rand/issues/1089">#1089</a> from dhardy/work</li>
<li><a href="https://github.com/rust-random/rand/commit/8821743325303e4deb6c4a6c934f0e2eb9680205"><code>8821743</code></a> Prepare 0.8.3</li>
<li><a href="https://github.com/rust-random/rand/commit/fa615efd91f83fe8e56799cfa9217d67f7625fb7"><code>fa615ef</code></a> Feature gate choose_multiple_weighted on std</li>
<li><a href="https://github.com/rust-random/rand/commit/22dec87aac43e0e92eb15fa85b2de6da5b3c95b7"><code>22dec87</code></a> CI: more accurate no-default-feature and nightly test targets</li>
<li><a href="https://github.com/rust-random/rand/commit/6a6b9fd06dbf54538d250dfbc4c918f79daa9299"><code>6a6b9fd</code></a> Merge pull request <a href="https://github.com/rust-random/rand/issues/1087">#1087</a> from GautierMinster/fix_uniform_int_panic_on_full_in...</li>
<li><a href="https://github.com/rust-random/rand/commit/2c9085a2de8864ee327af0311f6a8e5747cf25b7"><code>2c9085a</code></a> Bump to 0.8.2 and update changelog</li>
<li><a href="https://github.com/rust-random/rand/commit/4e8c7a4ca2963797d0ec414d04b6239ece905165"><code>4e8c7a4</code></a> distributions/uniform: fix panic in gen_range(0..=MAX)</li>
<li>See full diff in <a href="https://github.com/rust-random/rand/compare/0.8.1...0.8.3">compare view</a></li>
</ul>
</details>
<br />


[![Dependabot compatibility score](https://dependabot-badges.githubapp.com/badges/compatibility_score?dependency-name=rand&package-manager=cargo&previous-version=0.8.1&new-version=0.8.3)](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores)

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting `@dependabot rebase`.

[//]: # (dependabot-automerge-start)
[//]: # (dependabot-automerge-end)

---

<details>
<summary>Dependabot commands and options</summary>
<br />

You can trigger Dependabot actions by commenting on this PR:
- `@dependabot rebase` will rebase this PR
- `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it
- `@dependabot merge` will merge this PR after your CI passes on it
- `@dependabot squash and merge` will squash and merge this PR after your CI passes on it
- `@dependabot cancel merge` will cancel a previously requested merge and block automerging
- `@dependabot reopen` will reopen this PR if it is closed
- `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually


</details>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
bors bot added a commit to comit-network/comit-rs that referenced this pull request Mar 17, 2021
3538: Bump rand from 0.8.1 to 0.8.3 r=mergify[bot] a=dependabot[bot]

Bumps [rand](https://github.com/rust-random/rand) from 0.8.1 to 0.8.3.
<details>
<summary>Changelog</summary>
<p><em>Sourced from <a href="https://github.com/rust-random/rand/blob/master/CHANGELOG.md">rand's changelog</a>.</em></p>
<blockquote>
<h2>[0.8.3] - 2021-01-25</h2>
<h3>Fixes</h3>
<ul>
<li>Fix <code>no-std</code> + <code>alloc</code> build by gating <code>choose_multiple_weighted</code> on <code>std</code> (<a href="https://github.com/rust-random/rand/issues/1088">#1088</a>)</li>
</ul>
<h2>[0.8.2] - 2021-01-12</h2>
<h3>Fixes</h3>
<ul>
<li>Fix panic in <code>UniformInt::sample_single_inclusive</code> and <code>Rng::gen_range</code> when
providing a full integer range (eg <code>0..=MAX</code>) (<a href="https://github.com/rust-random/rand/issues/1087">#1087</a>)</li>
</ul>
</blockquote>
</details>
<details>
<summary>Commits</summary>
<ul>
<li><a href="https://github.com/rust-random/rand/commit/6ecbe2626b2cc6110a25c97b1702b347574febc7"><code>6ecbe26</code></a> Merge pull request <a href="https://github.com/rust-random/rand/issues/1089">#1089</a> from dhardy/work</li>
<li><a href="https://github.com/rust-random/rand/commit/8821743325303e4deb6c4a6c934f0e2eb9680205"><code>8821743</code></a> Prepare 0.8.3</li>
<li><a href="https://github.com/rust-random/rand/commit/fa615efd91f83fe8e56799cfa9217d67f7625fb7"><code>fa615ef</code></a> Feature gate choose_multiple_weighted on std</li>
<li><a href="https://github.com/rust-random/rand/commit/22dec87aac43e0e92eb15fa85b2de6da5b3c95b7"><code>22dec87</code></a> CI: more accurate no-default-feature and nightly test targets</li>
<li><a href="https://github.com/rust-random/rand/commit/6a6b9fd06dbf54538d250dfbc4c918f79daa9299"><code>6a6b9fd</code></a> Merge pull request <a href="https://github.com/rust-random/rand/issues/1087">#1087</a> from GautierMinster/fix_uniform_int_panic_on_full_in...</li>
<li><a href="https://github.com/rust-random/rand/commit/2c9085a2de8864ee327af0311f6a8e5747cf25b7"><code>2c9085a</code></a> Bump to 0.8.2 and update changelog</li>
<li><a href="https://github.com/rust-random/rand/commit/4e8c7a4ca2963797d0ec414d04b6239ece905165"><code>4e8c7a4</code></a> distributions/uniform: fix panic in gen_range(0..=MAX)</li>
<li>See full diff in <a href="https://github.com/rust-random/rand/compare/0.8.1...0.8.3">compare view</a></li>
</ul>
</details>
<br />


[![Dependabot compatibility score](https://dependabot-badges.githubapp.com/badges/compatibility_score?dependency-name=rand&package-manager=cargo&previous-version=0.8.1&new-version=0.8.3)](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores)

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting `@dependabot rebase`.

[//]: # (dependabot-automerge-start)
[//]: # (dependabot-automerge-end)

---

<details>
<summary>Dependabot commands and options</summary>
<br />

You can trigger Dependabot actions by commenting on this PR:
- `@dependabot rebase` will rebase this PR
- `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it
- `@dependabot merge` will merge this PR after your CI passes on it
- `@dependabot squash and merge` will squash and merge this PR after your CI passes on it
- `@dependabot cancel merge` will cancel a previously requested merge and block automerging
- `@dependabot reopen` will reopen this PR if it is closed
- `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually


</details>

Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants