Skip to content

Fix subtraction overflow in DuplicatesBy size_hint#552

Merged
bors[bot] merged 4 commits intorust-itertools:masterfrom
arpankapoor:master
Aug 16, 2021
Merged

Fix subtraction overflow in DuplicatesBy size_hint#552
bors[bot] merged 4 commits intorust-itertools:masterfrom
arpankapoor:master

Conversation

@arpankapoor
Copy link
Contributor

@arpankapoor arpankapoor commented Jun 17, 2021

Sample that panics with attempt to subtract with overflow in a debug build:

use itertools::Itertools;

fn main() {
    println!("{:?}", vec!["a", "b", "c", "c"].iter().duplicates().collect_vec());
}

@phimuemue
Copy link
Member

phimuemue commented Jun 18, 2021

Thanks for this. Yes, cmp::max(a-b, 0) seems strange on usize. I do not have much time right now, so just two questions:

  • Do you know if there are other occurences of this pattern in the code? (A "no, I do not know" is fine, we should just look ourselves, then.)
  • Should we add tests for this case?

@arpankapoor
Copy link
Contributor Author

arpankapoor commented Jun 18, 2021

  • I haven't seen this pattern repeated elsewhere on a cursory glance.
  • Added a test similar to the above example. Let me know if that seems sufficient.

I've also changed the checked_sub call to saturating_sub as per clippy's suggestion.

@phimuemue phimuemue mentioned this pull request Aug 15, 2021
Closed
phimuemue
phimuemue reviewed Aug 15, 2021
View reviewed changes
src/duplicates_impl.rs Outdated
Comment on lines 91 to 93
let max_pending = std::cmp::min(self.meta.pending, hi);
let max_new = std::cmp::max(hi - self.meta.pending, 0) / 2;
let max_new = hi.saturating_sub(self.meta.pending) / 2;
max_pending + max_new
Copy link
Member

@phimuemue phimuemue Aug 15, 2021

Choose a reason for hiding this comment

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

Hi there, one thing that bothers me is that cmp::min and saturating_sub actually answer the same question twice. (Namely: is hi <= self.meta.pending?)

I think it would be clearer to do this:

if hi <= self.meta.pending {
    // fewer or equally many iter-remaining elements than pending elements
    // => at most, each iter-remaining element is matched
    hi
} else {
    // fewer pending elements than iter-remaining elements
    // => at most:
    //    * each pending element is matched
    //    * the other iter-remaining elements come in pairs
    self.meta.pending + (hi-self.meta.pending)/2
}

Copy link
Contributor Author

@arpankapoor arpankapoor Aug 16, 2021

Choose a reason for hiding this comment

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

updated as per your suggestion

@phimuemue
Copy link
Member

phimuemue commented Aug 16, 2021

Thank you.

bors r+

@phimuemue
Copy link
Member

phimuemue commented Aug 16, 2021

Merged as this improves the current size_hint. Maybe we should use our size_hint::add et al instead of plain + and others.

@bors
Copy link
Contributor

bors bot commented Aug 16, 2021

Build succeeded:

@bors bors bot merged commit 2c82c5e into rust-itertools:master Aug 16, 2021
@jswrenn jswrenn added this to the next milestone Sep 13, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@phimuemue phimuemue phimuemue left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

0.10.3

Development

Successfully merging this pull request may close these issues.

3 participants

@arpankapoor @phimuemue @jswrenn