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

Tracking Issue for slice::array_windows #75027

Open
3 tasks
lcnr opened this issue Aug 1, 2020 · 12 comments
Open
3 tasks

Tracking Issue for slice::array_windows #75027

lcnr opened this issue Aug 1, 2020 · 12 comments
Labels
A-array Area: [T; N] A-const-generics Area: const generics (parameters and arguments) A-slice Area: [T] C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. F-generic_const_exprs `#![feature(generic_const_exprs)]` Libs-Tracked Libs issues that are tracked on the team's project board. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@lcnr
Copy link
Contributor

lcnr commented Aug 1, 2020

The feature gate for the issue is #![feature(array_windows)].

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also uses as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

Unresolved Questions

Implementation history

@lcnr lcnr added T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. A-const-generics Area: const generics (parameters and arguments) F-const_generics `#![feature(const_generics)]` labels Aug 1, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 1, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 2, 2020
@KodrAus KodrAus added Libs-Tracked Libs issues that are tracked on the team's project board. A-slice Area: [T] labels Aug 6, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 7, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 13, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 13, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Aug 30, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 12, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
JulianKnodt added a commit to JulianKnodt/rust that referenced this issue Sep 16, 2020
Updated issue to rust-lang#75027

Update to rm oob access

And hopefully fix docs as well

Fixed naming conflict in test

Fix test which used 1-indexing

Nth starts from 0, woops

Fix a bunch of off by 1 errors

See https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=757b311987e3fae1ca47122969acda5a

Add even more off by 1 errors

And also write `next` and `next_back` in terms of `nth` and `nth_back`.

Run fmt

Fix forgetting to change fn name in test

add nth_back test & document unsafe

Remove as_ref().unwrap()
Documented occurrences of unsafe, noting what invariants are maintained
tmandry added a commit to tmandry/rust that referenced this issue Sep 16, 2020
Add array_windows fn

This mimicks the functionality added by array_chunks, and implements a const-generic form of
`windows`. It makes egregious use of `unsafe`, but by necessity because the array must be
re-interpreted as a slice of arrays, and unlike array_chunks this cannot be done by casting the
original array once, since each time the index is advanced it needs to move one element, not
`N`.

I'm planning on adding more tests, but this should be good enough as a premise for the functionality.
Notably: should there be more functions overwritten for the iterator implementation/in general?

~~I've marked the issue as rust-lang#74985 as there is no corresponding exact issue for `array_windows`, but it's based of off `array_chunks`.~~

Edit: See Issue rust-lang#75027 created by @lcnr for tracking issue

~~Do not merge until I add more tests, please.~~

r? @lcnr
@yoshuawuyts
Copy link
Member

In the docs it says:

If N is smaller than the size of the array, it will return no windows.

I'm a bit confused what that refers to; it's the first use of "array" in that section of the docs. Perhaps there's a way to phrase that more clearly?

@lcnr
Copy link
Contributor Author

lcnr commented Sep 18, 2020

@yoshuawuyts see #76827 😆

@leonardo-m
Copy link

leonardo-m commented Nov 17, 2020

Is it now possible to forbid N==0 like this?

#![feature(
    const_evaluatable_checked,
    const_generics,
    const_panic,
)]
#![allow(incomplete_features)]

const fn nonzero(n: usize) -> usize {
    assert!(n > 0);
    n
}

fn foo<const N: usize>() -> [u8; nonzero(N)] {
    [0; nonzero(N)]
}

fn main() {
    foo::<5>();
}

@lcnr
Copy link
Contributor Author

lcnr commented Nov 17, 2020

yes, this is possible, it does require us to use `const_evaluatable_checked' in the standard library though.

That's not yet something I feel comfortable with

@the8472
Copy link
Member

the8472 commented Feb 23, 2021

Bikeshed:

Would windowed_iter() be a better name? It follows the convention that iter() usually returns borrowed iterators.

@TrolledWoods
Copy link
Contributor

@the8472 While it's true that iter usually returns borrowed iterators, there are a lot of borrowed iterators that do not have iter in their name. values, keys, chunks, windows, e.t.c. Considering that windows is already a stabilized name too, it would make sense for this name to also contain windows.

Additionally, if there are any better name suggestions for these const generic equivalents, we need change array_chunks too to follow that convention.

@Stargateur
Copy link
Contributor

Stargateur commented Dec 1, 2021

Is compile time check of N == 0 a real problem ? I expect LLVM to remove this check for free. The only thing I could think of is we consider it's breaking change to add the compile time check in the future but I hardly can imagine break someone workflow with that, cause it's a hard panic anyway, user code would be considered totally bogus ? But we could decide this stay an assert forever if LLVM optimize it. Maybe replace the panic by an abort ?

Would be amazing to be able to write: const N: NonZeroUsize

@leonardo-m
Copy link

Is compile time check of N == 0 a real problem ? I expect LLVM to remove this check for free.

That's beside the point. The point is spotting at compile-time some wrong code.

@Stargateur
Copy link
Contributor

Stargateur commented Dec 1, 2021

Is compile time check of N == 0 a real problem ? I expect LLVM to remove this check for free.

That's beside the point. The point is spotting at compile-time some wrong code.

I know, of course it would be better, but my point is how many time we need to wait to be able to have this on stable ? const_panic is expected for 1.57 source but const_evaluatable_checked doesn't look stable at all and look really really hard to implement, so I wonder if this would even ever land on stable if we want the compile time check of 0. Thus my though, do we really want this ? It could take years before const_evaluatable_checked is stable it has several ICE issue open. Do we have any clues on #76560 release ?

My point is, could we have the panic (or abort) version and then have the compile time check later ? would we consider it breaking change (I don't know any guideline about breaking change on const generic) ? I just ask open question, I don't really have a strong need or opinion for this anyway. And As I said, could we just... live with it ?

The current main problem of windows is the slice forcing to use try_from or use index, the array_windows is already way better than windows but here we block cause we want the grail by having compile time check of 0 even if current windows also do that and we live with it for years.

@yoshuawuyts
Copy link
Member

I used Slice::array_windows for a project yesterday, and it worked really well. I'm excited for this to be stabilized! The only downside is that when we're dealing with streaming data it requires collecting into a vec first.

It'd be neat if once we merge Slice::array_windows, we can look towards adding a variant of Iterator::array_windows as well (example impl). In order for it to have the same yield type as Slice::array_windows we'll first need GATs and lending iterators to land first though; so it'll still be a while longer out. But I hope that once those land we can start experimenting with those.

Examples

Usage example of Slice::array_windows

fn parse1(input: &str) -> usize {
    let lines: Vec<u16> = input.lines().map(|line| line.parse().unwrap()).collect();
    lines.array_windows().filter(|[n1, n2]| n2 > n1).count()
}

Usage example of Iterator::array_windows
This is slightly nicer to use when dealing with streaming data, but requires lending iterators to land in order to have the right return signature.

fn parse1(input: &str) -> usize {
    input
        .lines()
        .map(|line| line.parse::<u16>().unwrap())
        .array_windows()
        .filter(|[n1, n2]| n2 > n1)
        .count()
}

@steffahn
Copy link
Contributor

I'm noticing some missing Send/Sync implementations on the iterator. (Due to the usage of *const T, they are not auto-implemented.)

@lcnr lcnr added F-generic_const_exprs `#![feature(generic_const_exprs)]` and removed F-const_generics `#![feature(const_generics)]` labels Jun 28, 2022
AngelicosPhosphoros added a commit to AngelicosPhosphoros/rust that referenced this issue Jul 19, 2022
Methods updated: `array_windows`, `array_chunks`, `array_chunks_mut`.

I implemented this using compile time evaluation of trait constants and compile time panics.

Example compilation error:

```
> rustc +stage1 .\improper_array_windows.rs --crate-type=rlib
error[E0080]: evaluation of `<[u32; 0] as core::slice::<impl [T]>::array_windows::CompileAssert>::TRIGGER` failed
    --> D:\rust_dev\rust\library\core\src\slice\mod.rs:1286:9
     |
1286 |         compile_assert_non_zero_array!(array_windows, "Window", T, N);
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'Window size in `array_windows` must be bigger than zero.', D:\rust_dev\rust\library\core\src\slice\mod.rs:1286:9
     |
     = note: this error originates in the macro `$crate::panic::panic_2021` (in Nightly builds, run with -Z macro-backtrace for more info)

note: the above error was encountered while instantiating `fn core::slice::<impl [u32]>::array_windows::<0_usize>`
 --> .\improper_array_windows.rs:4:13
  |
4 |     let _ = s.array_windows::<0>();
  |             ^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error
```

I also added doctests and adjusted documentation.

r? @lcnr

Relates:
rust-lang#74985
rust-lang#75027
AngelicosPhosphoros added a commit to AngelicosPhosphoros/rust that referenced this issue Jul 19, 2022
Methods updated:
* `array_windows`
* `array_chunks`
* `array_chunks_mut`
* `as_chunks`
* `as_chunks_mut`
* `as_chunks_unchecked`
* `as_rchunks`
* `as_rchunks_mut`
* `as_chunks_unchecked_mut`

I implemented this using compile time evaluation of trait constants and compile time panics.

Example compilation error:

```
> rustc +stage1 .\improper_array_windows.rs --crate-type=rlib
error[E0080]: evaluation of `<[u32; 0] as core::slice::<impl [T]>::array_windows::CompileAssert>::TRIGGER` failed
    --> D:\rust_dev\rust\library\core\src\slice\mod.rs:1286:9
     |
1286 |         compile_assert_non_zero_array!(array_windows, "Window", T, N);
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'Window size in `array_windows` must be bigger than zero.', D:\rust_dev\rust\library\core\src\slice\mod.rs:1286:9
     |
     = note: this error originates in the macro `$crate::panic::panic_2021` (in Nightly builds, run with -Z macro-backtrace for more info)

note: the above error was encountered while instantiating `fn core::slice::<impl [u32]>::array_windows::<0_usize>`
 --> .\improper_array_windows.rs:4:13
  |
4 |     let _ = s.array_windows::<0>();
  |             ^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error
```

I also added doctests and adjusted documentation.

r? @lcnr

Relates:
rust-lang#74985
rust-lang#75027
@clarkmcc
Copy link

I'm getting the following error. I'm wondering if it's related to @steffahn's comment, since I can drop-in my own windowing iterator and everything compiles fine.

has type `ArrayWindows<'_, Foobar, 3>` which is not `Send`

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-array Area: [T; N] A-const-generics Area: const generics (parameters and arguments) A-slice Area: [T] C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. F-generic_const_exprs `#![feature(generic_const_exprs)]` Libs-Tracked Libs issues that are tracked on the team's project board. 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