Generalize ExactSizeIterator to QuantifiedIterator

[414owen]

Proposal

Problem statement

I use bumpalo to amortize allocations.
One of the main functions I call is alloc_slice_fill_iter.
This only works on iterators which implement ExactSizeIterator.

I have iterators which have a known size, but don't implement this trait.

Motivating examples or use cases

Here are some iterators whose exact size is known at runtime, but which don't implement ExactSizeIterator.

• (0..).map(|a| a + 3).take(20)
• [1, 2].into_iter().zip(repeat(3))
• repeat(a).copied().take(3)
• once(42).chain((0..).filter(|a| a % 2 == 0)).take(2)

These all combine iterators which never return None (hereby refered to as infinite), with a limit from a call to .take(), or by .zip()ping with an ExactSizeIterator.

Solution sketch

My previous attempt introduced an InfiniteIterator trait, which can be used in combination with .take(), or .zip() to obtain an ExactSizeIterator.

This approach encountered problematic instances, for example on Zip, where I had implemented ExactSizeIterator for the sub-iterator combinations (Exact, Infinite), and (Infinite, Exact), on top of the existing implementation for (Exact, Exact). I tried solving this with negative bounds, which are probably unsound.

There is, however, a solution which works fine in stable rust, and covers all combinations of infinite and exact size iterator adapters.

Unfortunately, it somewhat generalizes and subsumes ExactSizeIterator, hence the ACP.

struct Exact {}
struct Infinite {}

trait QuantifiedIterator: Iterator {
    type Quantity;
}

The idea here, is to classify iterators into either Exact, or Infinite. Other quantifications are possible, but these are the two that seems immediately useful.

With this setup, we only need one implementation of QuantifiedIterator for Zip:

trait ZipQuantity {
    type Result;
}

impl ZipQuantity for (Exact, Exact) {
    type Result = Exact;
}

impl<A> ZipQuantity for (Infinite, Exact) {
    type Result = Exact;
}

impl ZipQuantity for (Exact, Infinite) {
    type Result = Exact;
}

impl<A, B> QuantifiedIterator for Zip<A, B>
where
    A: QuantifiedIter,
    B: QuantifiedIter,
    (A::Quantity, B::Quantity): ZipQuantity,
{
    type Quantity = <(A::Quantity, B::Quantity) as ZipQuantity>::Result;
}

ZipQuantity is a type-level function which maps two quantities to a resulting quantity.

A similar setup works for Chain (note that I've macroized the type-level function.

Another important adapter is Take. Its implementation is here.

Most iterator adapters have instances (an example of one which doesn't is take_while).

All sources of infinite iteration and exact iteration will have concrete implementations of QuantifiedIterator.

ExactSizeIterator can still exist, and can be implemented in terms of QuantifiedIterator.

The incompatibility comes from this (or at least, one source I've wrapped my head around):

At the moment, the standard library iterator adapters will work for third-party iterators, if they implement ExactSizeIterator.
With this change, at least some iterator adapters in the standard library will be implemented in terms of QuantifiedIterator (at least Zip, Chain, and Take).
This will break the ExactSizeIterator instance for existing third-party iterators, adapted by the stdlib.

Alternatives

Adding concrete instances piecemeal

I initially did this here.

Obviously, you can't cover every combination of iterator adapters like this, and it would be foolish to try.

At the moment, I know of two concrete instance in core, which are for Take<Repeat>, and Take<RepeatWith>, here

Adding a simple InfiniteIterator trait

I tried this here.

This used negative bounds to deal with the overlapping instance for Zip. It's probably unsound. I certainly ran into places where I couldn't figure out why it wasn't choosing my new instance.

Links and related work

Links to my previous attempts are above, under Alternatives.

here is another attempt.

Some discussion on discourse

I have an implementation of this proposal here, with all core and std iterators, and iterator adapters, updated.

[the8472]

We discussed this during a libs-api meeting and consider the following point a show-stopper:

This will break the ExactSizeIterator instance for existing third-party iterators, adapted by the stdlib.

A 3rd-party iterator implementing ESI, applying std adapters and then passing it to a method expecting ESI would no longer compile. That's the kind of breaking change we generally avoid unless there are very strong reasons to do it anyway, such as soundness fixes.

So if possible please update your proposal to maintain backwards-compatibility.

One alternative that was discussed was adding a take_exact(n) adapter that would panic if the iterator is exhausted before n, but that wouldn't really help with the exact.zip(repeat(_)) case. Plus panicking is not as nice as encoding things in the type system.

[pitaj]

Could we accomplish this without breakage using Default Associated Types?

We would add

trait QuantifiedIterator: Iterator {
    type Quantity = Exact;
}
pub use self::QuantifiedIterator as ExactSizeIterator;

[414owen]

@pitaj that's an interesting idea...

I think that, by doing this, ExactSizeIterator would no longer contain a .len() function.
Instead we'd have to expose another trait (ExactSizeIteratorCompat, or something), which provides that function.

This is a different breaking change to the one in my proposal, but I guess it's at least more obvious.

---

I don't yet see a way to do this in a 100% backward-compatible way.

[pitaj]

I think that, by doing this, ExactSizeIterator would no longer contain a .len() function.
Instead we'd have to expose another trait (ExactSizeIteratorCompat, or something), which provides that function.

Couldn't you do something like this?

fn len() -> usize
where Self: QuantifiedIterator<Quantity = Exact>

[414owen]

@pitaj I tried this strategy out.
It looks like this works for implementing ExactSizeIterator. This becomes the correct QuantifiedIterator instance.

The problem is when a library uses ExactSizeIterator as a bound. This becomes a QuantifiedIterator bound, without constraining the quantity to Quantity = Exact, so you end up with constraints on non-exact quantified iterators...

[pitaj]

Hmm then maybe we have to wait for something like implementable trait aliases.

[414owen]

@pitaj Sounds like Haskell's ConstraintKinds extension...

---

Assuming it's currently impossible to express this change in a backwards compatible way, does that mean there's no chance of getting this in?

What if I line this change up to be included in a breaking way in the next rust edition?
We should be able to follow the stability without stagnation ethos, right?

[pitaj]

There's an active RFC open for implementable trait aliases:

rust-lang/rfcs#3437

A competing concept is "Automatically implement super traits" which may also help prevent breakage for this ACP:

https://hackmd.io/@rust-for-linux-/SJd7zyFDel

[the8472]

Ok, marking this as blocked on new language features then.

What if I line this change up to be included in a breaking way in the next rust edition?
We should be able to follow the stability without stagnation ethos, right?

Editions aren't magic. Old-edition code still has to interoperte with new-edition code, including standard library things, which means traits have to remain compatible.

We can change the prelude, language surface syntax and I think changes to name resolution have been discussed (not sure if something has been implemented), but breaking changes to traits is not something edition enable unless we basically swap out the types that use those traits too (which in this case would be all iterators, which isn't feasible)...

[tomassedovic]

The Lang team has an active goal that could help here: Evolving trait hierarchies.

It allows evolving existing traits (and e.g. splitting them into a trait and supertrait) without breaking code.