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

Does [T]::array_chunks really need to be an iterator? #76354

Open
scottmcm opened this issue Sep 5, 2020 · 16 comments
Open

Does [T]::array_chunks really need to be an iterator? #76354

scottmcm opened this issue Sep 5, 2020 · 16 comments
Labels
A-array Area: `[T; N]` B-unstable Blocker: Implemented in the nightly compiler and unstable. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@scottmcm
Copy link
Member

scottmcm commented Sep 5, 2020

After bit after reviewing the code in #75021 I had a thought: if this iterator is mostly just a wrapper on a slice iterator, does it even need to be an iterator at all?

The original .chunks() call does (as does .windows), because the slices it wants to return don't exist anywhere.

But the arrays returned by array_chunks are inline in the original slice allocation, so the API could just return the slice that the method is already creating, instead of hiding it in an iterator.

To be more concrete:

impl [T] { 
    pub fn array_chunks<const N: usize>(&self) -> (&[[T;N]], &[T]);
    pub fn array_chunks_mut<const N: usize>(&mut self) -> (&mut [[T;N]], &mut [T]);
}

Not only would this be more general (the ArrayChunks type doesn't currently expose the slice), but I think it would make it less likely that people would forget to correctly handle the .remainder(). (While still being easy to ignore it with .0 if they insist.) And returning tuples like this has precedent with split_* and align_to and such. (Many other names could work too, like .as_chunks(_mut).)

Also, such a method would be nice to have as the inverse of a hypothetical flatten: &[[T; N]] -> &[T]. (EDIT: No longer as hypothetical, #95629.)

array_chunks tracking issue #74985

@scottmcm scottmcm added B-unstable Blocker: Implemented in the nightly compiler and unstable. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. labels Sep 5, 2020
@cuviper
Copy link
Member

cuviper commented Sep 5, 2020

Also related, array_windows in #75026 does have to be an iterator.
So it might be strange if array_chunks/_mut were the odd ones out.

(the ArrayChunks type doesn't currently expose the slice)

It could though, just as Iter does.

@leonardo-m
Copy link

Let's compare the usage examples with the iterator and the slice.

@the8472
Copy link
Member

the8472 commented Sep 5, 2020

Also, such a method would be nice to have as the inverse of a hypothetical flatten: &[[T; N]] -> &[T].

#62765 indicates that's not allowed, at least in the general case where you don't know whether those slices really come from the same allocation rather than just happening to be adjacent by coincidence.

@cuviper
Copy link
Member

cuviper commented Sep 5, 2020

That's not multiple slices -- a slice of arrays is necessarily just one contiguous allocation.

@est31
Copy link
Member

est31 commented Oct 27, 2020

The chunks_exact function that array_chunks bases on also has a reverse analog: rchunks_exact where it iterates the chunks in reverse order, starting at the end. Obviously for this instance, one can't get a slice that has precisely the same behaviour. But maybe it's enough to tell people that they still need to do .iter().rev() if they want to traverse the slice of array chunks in reverse order?

@scottmcm
Copy link
Member Author

scottmcm commented Oct 27, 2020

The important difference with rchunks to me is that the remainder goes at the beginning, not the end. So I agree that saying "use .rev() to go backwards" would be fine.

So that would imply that there'd be both of these

I can go make a PR for the second one of those, if it sounds worthwhile...

EDIT: PR #78818

m-ou-se added a commit to m-ou-se/rust that referenced this issue Jan 16, 2021
Add `as_rchunks` (and friends) to slices

`@est31` mentioned (rust-lang#76354 (comment)) that, for completeness, there needed to be an `as_chunks`-like method that chunks from the end (with the remainder at the beginning) like `rchunks` does.

So here's a PR for `as_rchunks: &[T] -> (&[T], &[[T; N]])` and `as_rchunks_mut: &mut [T] -> (&mut [T], &mut [[T; N]])`.

But as I was doing this and copy-pasting `from_raw_parts` calls, I thought that I should extract that into an unsafe method.  It started out a private helper, but it seemed like `as_chunks_unchecked` could be reasonable as a "real" method, so I added docs and made it public.  Let me know if you think it doesn't pull its weight.
bors added a commit to rust-lang-ci/rust that referenced this issue Jan 17, 2021
Add `as_rchunks` (and friends) to slices

`@est31` mentioned (rust-lang#76354 (comment)) that, for completeness, there needed to be an `as_chunks`-like method that chunks from the end (with the remainder at the beginning) like `rchunks` does.

So here's a PR for `as_rchunks: &[T] -> (&[T], &[[T; N]])` and `as_rchunks_mut: &mut [T] -> (&mut [T], &mut [[T; N]])`.

But as I was doing this and copy-pasting `from_raw_parts` calls, I thought that I should extract that into an unsafe method.  It started out a private helper, but it seemed like `as_chunks_unchecked` could be reasonable as a "real" method, so I added docs and made it public.  Let me know if you think it doesn't pull its weight.
@not-an-aardvark
Copy link
Contributor

Is this issue resolved now that as_chunks and as_rchunks have been added? It seems like it wouldn't be necessary to access a slice with array_chunks if as_chunks can be used instead. (However, we should make sure to update #74985 to note that the issue is also gating #![feature(slice_as_chunks)] in addition to #![feature(array_chunks)].)

@scottmcm
Copy link
Member Author

scottmcm commented Feb 25, 2021

I think it still needs a libs decision for direction here. Could be neither, either, or both.

It could be argued that x.array_chunks() is still preferable for some uses, vs needing x.as_chunks().0.iter().

@not-an-aardvark
Copy link
Contributor

not-an-aardvark commented Feb 25, 2021

Thanks, that makes sense. For what it's worth, I found this issue today because I was looking for a way to safely convert &mut [T] to &mut [[T; N]]. So as a user it would be nice to be able to do that somehow, although I don't have a strong preference about whether that happens with as_chunks_mut or by changing array_chunks_mut.

(This use case might become more common when const generics are stabilized, so it would be great to be able to move the array chunks methods toward stabilization if this is the only outstanding blocker.)

@scottmcm
Copy link
Member Author

Oh, also there's the problem of what to do about N == 0. Not compiling would be nice, but isn't available with just min_const_generics. It currently panics, so one could just decide that that's fine. Or it could return (&[], original_slice) since making chunks of zero obviously doesn't help, but that has the downside of making the postcondition more complicated than one would like.

@not-an-aardvark If you want to try to push it forward, you could consider making a topic on zulip (https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs) to ask what directions libs would like to go for this -- it might be "actually things seem fine, can you make a stabilization PR with tweaks so that ________________________".

@not-an-aardvark
Copy link
Contributor

Thanks, I'll make a topic.

I was thinking that N == 0 would panic for now and then become a compile error when const generics are fully available. (Not sure what the backwards compatibility requirements are for that case -- it seems bad to stop compiling code that compiled before, but maybe it's ok if the code would have unconditionally panicked anyway?)

@cuviper
Copy link
Member

cuviper commented Feb 25, 2021

The unconditional panic can be made conditional by a user's own runtime check, if N > 0 { slice.as_chunks::<N>()... }

(Just as one might have "runtime" conditions for ZSTs.)

@newpavlov
Copy link
Contributor

In cryptographic code we need to be able to split &[T] into &[[T; N]] and &[T], since the former gets passed to code which processes data in blocks, while the tail gets either padded or saved for future processing. &[[T; N]] may even get split into &[[[T; N]; M]] in code which is able to process several blocks in parallel. The current ArrayChunks version of array_chunks is effectively useless for this use case.

@afetisov
Copy link

That doesn't mean that this behaviour needs to be stuffed into array_chunks rather than a separate method.

From my perspective, while a method which turns &[T] into (&[[T; N]], &[T]) is undoubtedly useful, so is the current array_chunks iterator. It's behaviour nicely parallels chunks, which makes it easily understandable and discoverable. It makes migrating between the const generic and dyn sized versions easier, and the same API provided by both iterators means that one can easily write a macro which will cover both const and dyn sized cases. All of that would be more complicated with a slice-based method, even if slightly so. It would also mean that where I was previously chaining iterator adapters, now I would need to create separate destructuring bindings and manually call iter.

Since the &[T] -> (&[[T; N]], &[T]) method is essentially a cheap reference reinterpretation, perhaps we could add something like fn as_arrays(&self) -> (&[[T; N]], &[T]) ?

@not-an-aardvark
Copy link
Contributor

I think this already exists as as_chunks.

@shepmaster
Copy link
Member

That doesn't mean that this behaviour needs to be stuffed into array_chunks rather than a separate method.

Make sure to read previous comments, such as #76354 (comment) and #76354 (comment)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-array Area: `[T; N]` B-unstable Blocker: Implemented in the nightly compiler and unstable. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

10 participants