Fixed length iterators

code review
1

Hi everyone!

There is an issue on rusts github about collecting iterators into arrays. The scenario mostly focused on in that issue is turning arbitrary iterators of, at compile time, unknown length into arrays.

However it turns out that quite a large subset of iterators and their methods affect the length in a way that would be possible to track in the type system. Some examples of methods on Iterator that affect the length in a predictable way:

  • map
  • inspect
  • skip (with const skip-count)
  • step_by (with const step)
  • chain
  • enumerate
  • take (with const step)
  • zip
  • rev
  • copied
  • cloned

These iterators should then be possible to safely collect into an array without any unnecessary runtime checks.

I have started working on a proof of concept crate iter_fixed that implements this (using several nightly features, mostly related to const_generics).
It is work in progress but I thought I would kindly ask about your thoughts :slight_smile:

This is my very first project that might potentially be used by others. Also, I am not too comfortable with very generic(that's the word?) code and weird trait bounds

  • Do you think something like this would be useful to you?
  • Project
    • Anything related to license, MIT Apache is the preferred for rust right? (I have no opinion on the matter)
    • Should the version in Cargo.toml start even lower like 0.0.x or is 0.1.0 fine this early on?
    • Is there anything else that is wrong or could be improved with the project :slight_smile:
    • When does it make most sense to publish to crates.io? Anything to think about other than Publishing on crates.io?
  • Code (The code is currently not much more than a const generic wrapper struct wrapping an ordinary Iterator only exposing some of its methods to the public)
    • Does the architecture(?) make sense?
    • Naming :slight_smile: - Reason for the name iter_fixed is because iter_mut is called iter_mut and not mut_iter. Does this make sense or do you have other suggestions(both for crate/repo and types and functions)
    • Do you have any generics related suggestions?
      • Should I switch out Iterator[Fixed] with IntoIterator[Fixed] anywhere?
      • Other things :slight_smile:
      • Should I try to hide the exact return types? How do I do that?(If I remember correctly fn zip(..)-> IteratorFixed<impl Iterator<..>> did not compile)
    • Anything else I can improve?
8 Likes
2

Starting at 0.1.0 is fine. As long as you are using a 0.x version and will bump the second number when making backwards incompatible changes, the actual number doesn't really matter. You could even start at 0.42.0 if you wanted.

I'd recommend copying the standard library because the way they chose their trait bounds turns out to be pretty ergonomic.

What made you choose to use a struct wrapper instead of some FixedLengthIterator trait?

If everything is unified with a trait then you could use impl Trait to hide a lot of implementation details (e.g. fn zip<I, T>(iter: I) -> impl FixedLengthIterator<Item=T> where I: Iterator<Item=T>).

3

Note that zip of two iterators will have statically-known length, only if both of them have statically-known length (or if one iterator is statically known to be empty, in which case the second one will not matter anyway).

1 Like
4

Another thing i've needed before is std::iter::repeat(0).take(n) not being an ExactSizeIterator because Repeat is not ExactSizeIterator take is not (similarly to how @Cerberusers mentions zip above.), I used itertools::repeat_n - Rust It seems there is a case to be made though that you should be able to extract a FixedLengthIterator from an InfiniteLengthIterator if there were such a thing.

1 Like
5

Starting at 0.1.0 is fine. [...]

Ok, thanks.

I'd recommend copying the standard library[...]

Ok, I will have another look.

What made you choose to use a struct wrapper instead of some FixedLengthIterator trait?

I am not sure how that would look. Do you mean to have a publicly exposed trait and then the actual implementation would be a wrapper similar to the one I have? That wrapper would then implement FixedLengthIterator?

6

Would something like this be acceptable:

// Safety: core::iter::repeat(_).take(N) always yields N elements
unsafe impl<T: Clone, const N: usize> IntoIteratorFixed<core::iter::Take<core::iter::Repeat<T>>, N> for core::iter::Repeat<T> {
    fn into_iter_fixed(self) -> IteratorFixed<core::iter::Take<core::iter::Repeat<T>>, N> {
        unsafe { IteratorFixed::from_iter(self.take(N)) }
    }
}
7

I think that would definitely convey the intent better, the only hestitation is i'm not familiar enough with const generics yet to know the situation with type inference of N, and how that'll permeate my program but I'll mess around with that in a branch.

8

Note that zip of two iterators will have statically-known length, only if both of them have statically-known length[...]

This should make sure of that right?

pub fn zip<U, IIF, I2>(self, other: IIF) -> IteratorFixed<iter::Zip<I, I2>, N>
where
    IIF: IntoIteratorFixed<I2, N>,
    I2: Iterator<Item = U> { ... }

and with the impl from my last post that would also allow something like

let foo: [(_, _); 3] = [1, 2, 3]
    .into_iter_fixed()
    .zip(iter::repeat(42))
    .collect();

if I am not mistaken?

9

May I ask you to clarify how the trait solution would work? :slight_smile:

Does that mean trait FixedLengthIterator should have all of the methods map, zip, skip etc specified in a way similar to your zip example, hiding the return type?

Then I would use a private wrapper similar to my current IteratorFixed which implements the trait with all of its methods?

10

I have now published iter_fixed to crates.io in case anyone would like to give it a try. As I believe I have said earlier the crate does depend on several unstable features and thus requires a nightly compiler...

1 Like
11

I have been trying to get Iterator::flatten to be more like flatten from std that allows IntoIterator as items. This would in my case mean accepting IntoIteratorFixed instead of IteratorFixed as items for the outer iterator.

I tried with(see commit):

impl<I, IIF, const M: usize, const N: usize> IteratorFixed<I, N>
where
    I: Iterator<Item = IIF>,
    IIF: IntoIteratorFixed<M> + IntoIterator,
{
    pub fn flatten(self) -> IteratorFixed<iter::Flatten<I>, { N * M }> {
        IteratorFixed {
            inner: self.inner.flatten()
        }
    }
}

however that does not quite seem to work:

error[E0207]: the const parameter `M` is not constrained by the impl trait, self type, or predicates
   --> src/lib.rs:199:20
    |
199 | impl<I, IIF, const M: usize, const N: usize> IteratorFixed<I, N>
    |                    ^ unconstrained const parameter
    |
    = note: expressions using a const parameter must map each value to a distinct output value
    = note: proving the result of expressions other than the parameter are unique is not supported

after some searching I found stackoverflow and rust-lang/rust#60712 that might possibly be related, maybe?

Do think the error is me doing something wrong, if so what can I change to achieve something similar? Or is this simply #[feature(const_generics)] having some quirks not quite done yet?

For reference replacing M with N everywhere does compile just fine

Edit: cargo fmt the commit

12

Oh never mind, I should not have declared the const generics on the impl block but rather on the function inside it which actually uses them.:person_facepalming:

13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.