# async `Iterator` roadmap

We want to change `Iterator` to allow implementations that have an `async` `next` method. For now we are focussing on getting the desugared version working, so this document does not discuss what we want to stabilize, but what we want to do to remove the unstable `AsyncIterator` from libcore by replacing it with an unstable way to use `Iterator` for the same use case.

Iterator would look something like the following (I stripped stability attributes to make it more readable)

// the `= false` makes it so that stable users will just keep using `Iterator` the same way they used it before.
// the `ASYNC` generic param is unstable, but we'll need to figure out how to hide it from rustdoc, too.
trait Iterator<const ASYNC: bool = false> {
    // Unchanged
    type Next;
    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, None)
    }
    
    // Here be changes
    fn next<'a>(self: &'a mut Self) -> <() as Helper<Self, ASYNC>>::Ret<'a>;
    
    type Rettie<'a>: crate::future::Future<
        Output = Option<
            <Self as Iterator<true>>::Item
        >
    > = Dummy<<Self as Iterator<true>>::Item> where Self: Iterator<true> + Sized + 'a;
}

Helper trait to change the return type of `next` depending on the `ASYNC` generic parameter

pub trait Helper<T: Iterator<B> + ?Sized, const B: bool> {
    type Ret<'a>
    where
        T: 'a;
}

impl<T: Iterator<false> + ?Sized> Helper<T, false> for () {
    type Ret<'a> = Option<T::Item> where T: 'a;
}

impl<T: Iterator<true>> Helper<T, true> for () {
    type Ret<'a> = T::Rettie<'a> where T: 'a;
}

// specialization hack to implement a trait for both `true` and `false` and have it mean the trait is satisfied for `const B: bool`. This impl is never used.
impl<const B: bool, T: Iterator<B> + ?Sized> Helper<T, B> for () {
    default type Ret<'a> = super::Dummy<T::Item> where T: 'a;
}

Helper struct to have a dummy default value in `Rettie`. See also [this section](#Breaking-change-users-need-to-specify-the-Rettie-associated-type)

#[derive(Debug)]
pub struct Dummy<T>(T);

impl<T> crate::future::Future for Dummy<T> {
    type Output = Option<T>;

    fn poll(
        self: crate::pin::Pin<&mut Self>,
        _cx: &mut crate::task::Context<'_>,
    ) -> crate::task::Poll<Self::Output> {
        // Post monomorphization error if `Rettie` was not overwritten in an async impl.
        const {
            assert!(
                crate::mem::size_of::<T>() == usize::MAX,
                "You must override `Iterator::Rettie` if you are using `Iterator<true>`"
            );
        }
        unreachable!()
    }
}

## Blockers and schemes to address them

### Breaking change: users need to specify the `Rettie` associated type

The following snippet does not compile, because the user needs to add the `foo` method to the impl, even though that is obviously not a function that can ever be called.

trait Trait<const B: bool> {
    fn foo() where Self: Trait<true>;
}

impl Trait<false> for () {}

Workarounds: add a dummy default body (this is unstable for associated types.

### `where Self: Sized` bounds do not work on associated types to make the trait object safe

To keep `dyn Iterator<Item = Foo>` working (the non-async case), we need to remove the need for users to specify the associated type that is used for the return type of `next`. Ideally we'd be able to just slap a `where Self: Iterator<true>` on it, so that the associated type is actually irrelevant for anyone implementing `Iterator<false>` (the default). This requires a few features, but seems totally doable.

[See zulip discussion here](https://rust-lang.zulipchat.com/#narrow/stream/144729-t-types/topic/.60where.20Self.3ASized.60.20on.20assoc.20types/near/351260928)

This does not compile, it wants `dyn Foo<Bar = SomeType>`

fn _assert_is_object_safe(_: &dyn Foo) {}

pub trait Foo {
    type Bar where Self: Sized;
}

This does compile, the method just isn't callable on trait objects:

fn _assert_is_object_safe(_: &dyn Foo) {}

pub trait Foo {
    fn foo() where Self: Sized;
}

### breaks impls that use concrete types where the trait has associated types

we don't want to make all functions `async` immediately. So we want to mark them with `where Self: Iterator<false>` at the beginning. But that has issues.

The `impl<T, A: Allocator> Iterator for IntoIter<T, A>` impl uses

fn next_chunk<const N: usize>(
    &mut self,
) -> Result<
    [T; N],
    core::array::IntoIter<T, N>
>

as the signature of `next_chunk`, while the trait declares this to be

fn next_chunk<const N: usize>(
    &mut self,
) -> Result<
    [Self::Item; N],
    array::IntoIter<Self::Item, N>
>
where
    Self: Sized,

The incremental step where we try to make `async Iterator` not have most methods so we can make a decision on a per-method basis changes that signature to

fn next_chunk<const N: usize>(
        &mut self,
) -> Result<
    [<Self as Iterator>::Item; N],
    array::IntoIter<<Self as Iterator>::Item, N>
>
where
    Self: Iterator,
    Self: Sized,

but this causes

error[E0053]: method `next_chunk` has an incompatible type for trait
   --> library/alloc/src/vec/into_iter.rs:240:49
    |
184 | impl<T, A: Allocator> Iterator for IntoIter<T, A> {
    |      - this type parameter
...
240 |     fn next_chunk<const N: usize>(&mut self) -> Result<[T; N], core::array::IntoIter<T, N>> {
    |                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                                                 |
    |                                                 expected associated type, found type parameter `T`
    |                                                 help: change the output type to match the trait: `Result<[<vec::into_iter::IntoIter<T, A> as Iterator>::Item; N], core::array::IntoIter<<vec::into_iter::IntoIter<T, A> as Iterator>::Item, N>>`
    |
    = note: expected signature `fn(&mut vec::into_iter::IntoIter<T, A>) -> Result<[<vec::into_iter::IntoIter<T, A> as Iterator>::Item; N], core::array::IntoIter<<vec::into_iter::IntoIter<T, A> as Iterator>::Item, _>>`
               found signature `fn(&mut vec::into_iter::IntoIter<T, A>) -> Result<[T; N], core::array::IntoIter<T, _>>`
    = note: you might be missing a type parameter or trait bound

I simplified this to the following repro.

pub trait Foo<T = ()> {
    type Bop;
    fn foo() -> <Self as Foo>::Bop
    where
        Self: Foo,
    {
        unimplemented!()
    }
}

// Doesn't work

struct Bar<T>(T);

impl<T> Foo for Bar<T> {
    type Bop = T;
    fn foo() -> T {
        unimplemented!()
    }
}

// Works

struct Beep;

impl Foo for Beep {
    type Bop = i32;
    fn foo() -> i32 {
        unimplemented!()
    }
}

This can't be fixed. [See also the discussion on zulip](https://rust-lang.zulipchat.com/#narrow/stream/144729-t-types/topic/Missing.20associated.20type.20normalization/near/351278199). TLDR: new solver can fix this, but we should look into alternatives.