ACP: Uplift iter::repeat_n from itertools #120
Description
Proposal
Problem statement
Add the repeat_n<T>(value: T, n: usize) -> RepeatN<T> function and iterator type to iter.
This exists as itertools::repeat_n, but can easily be uplifted to core+std, like how iter::repeat_with has obviated itertools::repeat_call.
(This is a function, not a trait method, so doesn't have the resolution issues that make this hard for things like intersperse.)
Motivation, use-cases
The obvious alternative here is iter::repeat(value).take(n). But there's two gotchas with that approach:
It has to always clone value, never move it
If it's a string, for example, that buffer can never be reused (other than in specializations) since it needs to always keep the value around for the potentially-next iteration. (And even if it somehow knew it was the last element needed, it still can't move it in non-consuming calls as it'd make a follow-up .next() call UB, and the Drop would double-free.)
Vec has the secret from_elem for vec! to use to overcome this problem, as well as a bunch of extra internal stuff like ExtendElement for other places that want this functionality.
But other containers don't have this. For example,
iter::repeat(my_string).take(10).collect::<VecDeque<String>>()will do 10 clones (instead of the 9 that are really needed) and there's no nice way to avoid that.
Even VecDeque::resize didn't bother doing better here, as it just calls .resize_with(n, || value.clone()), which will also do the extra clone.
Thus one would need to do some long dance like
let mut v = VecDeque::with_capacity(10);
v.extend(iter::repeat(&my_string).cloned().take(9));
v.push_back(my_string);and that's enough of a pain that it's almost certainly not happening.
It would be nice to be able to just do iter::repeat_n(my_string, n).collect() and have that work great in containers, rather than needing them all to add from_elem-like methods or recreate extend specialization infrastructure for all of them like Vec is doing.
It's not ExactSizeIterator.
While that does have a perfect size_hint, iter::Repeat<_>: !ExactSizeIterator (and must not be) and thus the Take<…> isn't either:
iter::repeat(1).take(10).len(); | iter::repeat(1).take(10).len();
| ^^^ method cannot be called on `std::iter::Take<std::iter::Repeat<{integer}>>` due to unsatisfied trait bounds
|
= note: the following trait bounds were not satisfied:
`std::iter::Repeat<{integer}>: ExactSizeIterator`
which is required by `std::iter::Take<std::iter::Repeat<{integer}>>: ExactSizeIterator`
That could be made to work, but the "obvious" way would need both an InfiniteIterator trait and some #[marker] traits to express the bound, which combined make a pretty big hammer.
Whereas RepeatN<_> is non-infinite -- limited by the usize -- so is naturally ExactSizeIterator. Thus even for things like repeat(0).take(n) where buffer reuse is irrelevant, this is still useful. (Such as in -> impl ExactSizeIterator<Item = …> APIs.)
Solution sketches
So long as cloneing in this isn't considered a side effect, it can be made to work nicely. That should be uncontroversial, as the existing repeat doesn't either -- for example iter::repeat(NoisyClone).nth(10) only clones once: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=b8455030a83615d6b4a1b92c25d65571
A straight-forward and natural implementation even allows LLVM to unify the "clone" and "move the last time" branches for trivial-to-clone types even if they're not Copy -- with no special needs_drop checks or specialization: https://rust.godbolt.org/z/drjzsdfoe
Links and related work
As mentioned, https://docs.rs/itertools/latest/itertools/fn.repeat_n.html
The suffix _n for "counted" versions of methods is used in Elements of Programming and common in C++ functions like copy_n.
What happens now?
This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.