ACP: Uplift `iter::repeat_n` from itertools

[scottmcm]

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();

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=74ea40842f56f87224a4bb2411967ec6

  |     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.

[the8472]

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.

Smaller hammer:

impl<T> ExactSizeIterator for Take<Repeat<T>> where T: Clone {}

It has to always clone value, never move it

This could be solved with specialization on Take and a MaybeUninit. But yeah, now the hammer sizes are going up again.

[thomcc]

This could be solved with specialization on Take and a MaybeUninit. But yeah, now the hammer sizes are going up again.

It's also a specialization observable by users, which is unfortunate.

[mina86]

By the way, I was unaware of repeat_n and ended up implementing Take<Repeat<T>> in rust-lang/rust#106943

It's also a specialization observable by users, which is unfortunate.

I think this is unnecessarily strict view of observable behaviour especially since documentation doesn’t state whether repeat clones every value or not.

I think the bigger issue is to consider timeline of specialisation becoming.

[joshtriplett]

We discussed this in today's libs-api meeting. Seems good; it's clearer and a slight optimization.

Feel free to open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature.

[scottmcm]

Tracking issue: rust-lang/rust#104434

I'll make a PR to remove the doc(hidden) 🙂

EDIT: rust-lang/rust#120045