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?
6 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?