# Pre-RFC: Add a chunk iterator to libcore

**URL:** <https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101>\
**Category:** libs\
**Created:** [July 29, 2021, 1:48am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101 "2021-07-29T01:48:56Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [July 29, 2021, 1:48am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/1 "2021-07-29T01:48:56Z")

</div>

I'm drafting up an RFC to add an iterator that groups elements it receives into arrays and then returns those arrays. Could I add anything to this RFC?

> <https://github.com/notgull/rfcs/blob/chunks/text/0000-iterator-chunks.md>

---

<div class="post-metadata">

**Author:** ![mbrubeck](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mbrubeck/32/174_2.png) [@mbrubeck](https://internals.rust-lang.org/u/mbrubeck)\
**Post date:** [July 29, 2021, 3:23am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/2 "2021-07-29T03:23:12Z")

</div>

Perhaps the new method should be called `chunks_exact`, because it behaves like [`slice.chunks_exact()`](https://doc.rust-lang.org/std/primitive.slice.html#method.chunks_exact) rather than like [`slice.chunks()`](https://doc.rust-lang.org/std/primitive.slice.html#method.chunks).

It could also use a method like [`ChunksExact::remainder`](https://doc.rust-lang.org/std/slice/struct.ChunksExact.html#method.remainder) to access the left-over elements.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [July 29, 2021, 8:39am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/3 "2021-07-29T08:39:25Z")

</div>

- `remainder` is definitely a concern, and it's probably the most complicated part of the API:
  - What should it return?
    - a (possibly mutable) slice?
    - some kinds of `ArrayVec`?
    - an iterator over owned items? Could this be an already advanced `array::IntoIter`?

  - Even if we ignored it, it can still affect other methods
    - For example implementing `DoubleEndedIterator` should require the underlying iterator to implement `DoubleEndedIterator`, otherwise calling `.next_back()` would yield different chunks than `.next()`

- Do we really need `ChunkBuffer`? Couldn't this reuse [`collect_into_array`](https://github.com/rust-lang/rust/blob/581b1664c92f78f3d15181c78a16480987256ecb/library/core/src/array/mod.rs#L456)?
- `N` possibly being 0 is also a concern. Note that this is currently a blocker for stabilizing the `array_chunks` feature.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [July 29, 2021, 5:50pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/4 "2021-07-29T17:50:58Z")

</div>

One thing you might consider is how you're going to get the chunks, and whether that's well optimized today. Even on a simple iterator like a slice one, [https://rust.godbolt.org/z/fPdjWYjT5](https://rust.godbolt.org/z/fPdjWYjT5) ends up having poor codegen.

So consider whether a first step here might be a `next_chunk` method on `Iterator` so that different implementations have have it behave more efficiently that the default `try_fold`-based one would.

(Or maybe you've found a smarter implementation than I could for it and none of this is a concern.)

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [July 29, 2021, 6:10pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/5 "2021-07-29T18:10:35Z")

</div>

> [@mbrubeck](#):
>
> Perhaps the new method should be called `chunks_exact` , because it behaves like [`slice.chunks_exact()`](https://doc.rust-lang.org/std/primitive.slice.html#method.chunks_exact) rather than like [`slice.chunks()`](https://doc.rust-lang.org/std/primitive.slice.html#method.chunks).

I guess, but it doesn't really behave like `chunks_exact` either, since it returns arrays instead of slices.

> [@mbrubeck](#):
>
> It could also use a method like [`ChunksExact::remainder`](https://doc.rust-lang.org/std/slice/struct.ChunksExact.html#method.remainder) to access the left-over elements.

I've added `remainder` and `remainder_mut` as methods. They return a slice and a mutable slice, respectively.

> [@SkiFire13](#):
>
> Do we really need `ChunkBuffer` ? Couldn't this reuse [`collect_into_array`](https://github.com/rust-lang/rust/blob/581b1664c92f78f3d15181c78a16480987256ecb/library/core/src/array/mod.rs#L456)?

`ChunkBuffer` provides functionality that is now used in the `remainder` method, as well as making folding/try-folding much easier.

> [@SkiFire13](#):
>
> `N` possibly being 0 is also a concern. Note that this is currently a blocker for stabilizing the `array_chunks` feature.

I've added a check to the `chunks()` method that panics if `N` is 0, since that's what `array_chunks` currently does.

> [@scottmcm](#):
>
> One thing you might consider is how you're going to get the chunks, and whether that's well optimized today. Even on a simple iterator like a slice one, [Compiler Explorer](https://rust.godbolt.org/z/fPdjWYjT5) ends up having poor codegen.

There's probably a better way of using `ChunkBuffer`, I agree. I wonder if using `InPlaceIterable` would help at all, like it does in `Zip`.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [July 29, 2021, 8:33pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/6 "2021-07-29T20:33:08Z")

</div>

> [@notgull](#):
>
> I've added `remainder` and `remainder_mut` as methods. They return a slice and a mutable slice, respectively.

It is quite unfortunate that they don't give owned access to those items. I would at least mention this.

> [@notgull](#):
>
> `ChunkBuffer` provides functionality that is now used in the `remainder` method, as well as making folding/try-folding much easier.

I would still consider extending `collect_into_array` to allow those functionalities, or maybe a potential `ArrayVec`, whenever that will be introduced. Anyway, even if it doesn't end up like this, I think this is something that should be discussed, so I would put it under a "possible concerns" or "unresolved questions" section.

> [@notgull](#):
>
> I've added a check to the `chunks()` method that panics if `N` is 0, since that's what `array_chunks` currently does.

Note that this is not supposed to be the correct/final behaviour, but you make it look like it is. I would mention that it will temporarily panic if `N` is 0, but it is supposed to give a compile time error and that this should be a blocker for stabilization.

> [@notgull](#):
>
> I wonder if using `InPlaceIterable` would help at all, like it does in `Zip` .

`Zip` doesn't use `InPlaceIterable`, that trait is used for in place collection. You might be thinking of `TrustedRandomAccess`. I think it might be worth specializing on `TrustedLen` and/or `TrustedRandomAccess`. The former might be more supported, but the latter may enable more optimizations.

By the way the proposed implementation of `advance_by` is wrong, it discards the remainder. The implementation of `DoubleEndedIterator` also ignores the remainder.

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [July 29, 2021, 10:05pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/7 "2021-07-29T22:05:47Z")

</div>

> [@SkiFire13](#):
>
> It is quite unfortunate that they don't give owned access to those items. I would at least mention this.

I've added an `into_remainder` method to `Chunks` that gives the remainder in the form of an owned iterator.

> [@SkiFire13](#):
>
> I would still consider extending `collect_into_array` to allow those functionalities, or maybe a potential `ArrayVec` , whenever that will be introduced. Anyway, even if it doesn't end up like this, I think this is something that should be discussed, so I would put it under a "possible concerns" or "unresolved questions" section.

I've noted that in the unresolved questions section.

> [@SkiFire13](#):
>
> Note that this is not supposed to be the correct/final behaviour, but you make it look like it is. I would mention that it will temporarily panic if `N` is 0, but it is supposed to give a compile time error and that this should be a blocker for stabilization.

Also noted this.

> [@SkiFire13](#):
>
> I think it might be worth specializing on `TrustedLen` and/or `TrustedRandomAccess` . The former might be more supported, but the latter may enable more optimizations.

`Chunks` already specializes on `TrustedLen`.

> [@SkiFire13](#):
>
> By the way the proposed implementation of `advance_by` is wrong, it discards the remainder. The implementation of `DoubleEndedIterator` also ignores the remainder.

Could you elaborate on this? How could I fix it so that it doesn't ignore the remainder?

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [July 30, 2021, 7:26am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/8 "2021-07-30T07:26:31Z")

</div>

> [@notgull](#):
>
> `Chunks` already specializes on `TrustedLen` .

I didn't mean to implement `TrustedLen` on `Chunks`, but to specialize `Chunks::next` for iterators that implement `TrustedLen`, this way it doesn't need to do a check for each item, you can just check that the number of remaining items is bigger than the chunk size and then you can just repeatedly call `.next().unwrap_unchecked()`. Similar for `TrustedRandomAccess`, except in that case you can call `__iterator_get_unchecked`.

> [@notgull](#):
>
> Could you elaborate on this? How could I fix it so that it doesn't ignore the remainder?

For `DoubledEndedIterator` I think you have to require that the underlying iterator implements `ExactSizeIterator`, then use its size hint to know how many items will be in the remainder. Then you can first take the remainder and then call `.next_back()` N times.

For `advance_by` I think it may be a bit more complex. In the worst case you could keep the default implementation.

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [July 31, 2021, 1:40am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/9 "2021-07-31T01:40:12Z")

</div>

> [@SkiFire13](#):
>
> For `DoubledEndedIterator` I think you have to require that the underlying iterator implements `ExactSizeIterator` , then use its size hint to know how many items will be in the remainder. Then you can first take the remainder and then call `.next_back()` N times.

Yeah I see that now. I've reworked the proposal as a whole to accommodate this.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [July 31, 2021, 9:19am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/10 "2021-07-31T09:19:07Z")

</div>

I still think `advance_by`'s implementation is wrong. For example I would expect this to succeed, instead the assertion after the `advance_by` fails:

```rust
fn test_advance_by() {
    let elems = &[1, 2, 3, 4, 5, 6, 7];

    // Manually advance 4 times
    let mut chunks = elems.iter().copied().chunks::<2>();
    chunks.next(); chunks.next(); chunks.next(); chunks.next();
    assert_eq!(chunks.remainder(), &[7]);

    // Use advance_by(4)
    let mut chunks = elems.iter().copied().chunks::<2>();
    chunks.advance_by(4);
    assert_eq!(chunks.remainder(), &[7]);
}

```

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [July 31, 2021, 4:47pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/11 "2021-07-31T16:47:43Z")

</div>

I see. I've removed the optimized `advance_by` for the time being until I can think of a better solution.

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [October 14, 2021, 9:43pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/12 "2021-10-14T21:43:53Z")

</div>

Is there anything else this proposal needs? I'm going to propose the RFC later today.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [October 14, 2021, 11:31pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/13 "2021-10-14T23:31:57Z")

</div>

I think the RFC should contain the signatures of the methods on `Chunks` (`remainder`, `remainder_mut`, and `into_remainder`) directly, not just under a link.

> The core of `Chunks` is built around the private `PartialArray` struct. Its definition looks like this:

If this is an implementation detail, it probably shouldn't be in the RFC.

Relatedly, `fn into_remainder(self) -> IntoRemainder<I::Item, N>` is introducing another new type -- which isn't even mentioned in the RFC -- and it probably shouldn't. I think that remainder type is functionally an `array::IntoIter<T, N>`? Can it just _be_ that?

(In general, the more public items something needs the more justification it needs.)

> However, they can still be accessed via the `remainder()` and `remainder_mut()` methods.

What do these do when the iterator has not yet been exhausted?

---

<div class="post-metadata">

**Author:** ![illicitonion](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/illicitonion/32/3886_2.png) [@illicitonion](https://internals.rust-lang.org/u/illicitonion)\
**Post date:** [October 15, 2021, 12:21am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/14 "2021-10-15T00:21:44Z")

</div>

A while ago I prototyped [a crate with a similar API](https://github.com/illicitonion/collect_array) - it was for collecting one array rather than into chunks, but the analogue here would be to implement `Iterator<Item = ArrayOrRemainder>`, with

```rust
enum ArrayOrRemainder<T, const N: usize> {
  Array([T; N]),
  Remainder { values: [MaybeUninit<t>; N], init_count: usize },
}

```

forcing the caller to handle the possibility of a remainder, rather than to require they know to call `remainder()` after iterating... What do you think about that as an alternative?

---

<div class="post-metadata">

**Author:** ![notgull](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/notgull/32/8412_2.png) [@notgull](https://internals.rust-lang.org/u/notgull)\
**Post date:** [October 15, 2021, 3:48am UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/15 "2021-10-15T03:48:39Z")

</div>

An interesting proposition; I'd prefer to use a `Result<[T; N], PartialArray<[T; N]>>` or something like that. However, this would require end users to pipe the iterator through a `.filter_map(Result::ok)` to use it for the intended N:1 transform purpose. Not sure how idiomatic that would be.

---

<div class="post-metadata">

**Author:** ![illicitonion](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/illicitonion/32/3886_2.png) [@illicitonion](https://internals.rust-lang.org/u/illicitonion)\
**Post date:** [October 15, 2021, 1:14pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/16 "2021-10-15T13:14:06Z")

</div>

I quite like it - I think in general "force the user to think about the extra cases, and be explicit about ignoring them" is definitely idiomatic rust 🙂

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [October 15, 2021, 2:01pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/17 "2021-10-15T14:01:41Z")

</div>

> [@scottmcm](#):
>
> I think that remainder type is functionally an `array::IntoIter<T, N>` ? Can it just _be_ that?

Already proposed here, didn't get much attention from op.

> [@SkiFire13](#):
>
> an iterator over owned items? Could this be an already advanced `array::IntoIter` ?

> [@illicitonion](#):
>
> forcing the caller to handle the possibility of a remainder

I don't like the fact that this forces the caller to handle the possibility of a remainder even in the middle of the iterator, which should be impossible.

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [October 15, 2021, 10:50pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/18 "2021-10-15T22:50:15Z")

</div>

> [@illicitonion](#):
>
> but the analogue here would be to implement `Iterator<Item = ArrayOrRemainder>`

I'm not fond of that for lazy iterators, since it keeps the type system from knowing that it'll always be the array for a while, then only the last one can be partial. And, relatedly, that keeps one from doing, say, `.map(u32::from_ne_bytes)` on the chunks directly.

(I do really like that for slices, where the chunking is eager and cheap, though: [https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.as\_chunks](https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.as_chunks))

`itertools` has had questions about things somewhat like this related to `zip_eq`. Here's a rust conversation about the same: [[ER] Iterator::zip\_exact · Issue #85342 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/85342#issuecomment-843507018)

There are a bunch of possible options about the remainder -- like requiring `ESI` and `assert!`ing there won't be one, or `panic!`king on `Drop` if there's known to be a remainder but it wasn't looked at, or ...

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [January 13, 2022, 10:50pm UTC](https://internals.rust-lang.org/t/pre-rfc-add-a-chunk-iterator-to-libcore/15101/19 "2022-01-13T22:50:49Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.