Implementable trait aliases

[Jules-Bertholet]

With the stabilization of GATs, there has been some discussion on how some standard library traits, like Iterator and FnMut, could be backward-compatibly GATified. This recent blog post, for example. This is challenging because we can't break existing trait bounds.

This post proposes a possible solution, that I haven't seen discussed anywhere before.

1. Allow writing impl blocks for certain trait aliases, that only alias to a single trait plus some number of where clauses. For example,

trait Foo {
    type Assoc;
}

#[bikeshed::implementable_alias]
trait Bar = Foo where Self::Assoc: Copy;

impl Bar for u32 {
    type Assoc = u32;
}

2. Add LendingIterator (or LendingFnMut, etc) to the standard library, as a new trait.

pub trait LendingIterator {
    type Item<'a>;
    fn next(&mut self) -> Self::Item<'a>;

    // ...
}

3. Add some form of variance bounds to the language.

4. Delete the existing Iterator (or FnMut, etc) trait entirely, and replace it with an implementable alias.

#[bikeshed::implementable_alias]
pub trait Iterator = LendingIterator
where // bikesheddable
    for<'a> Self::Item<'a>: bivariant_in<'a>;

5. Allow omitting lifetime parameters in signatures when those parameters are determined to be bivariant.

---

Under this scheme, existing impl blocks keep their meaning, and so do existing trait bounds. The meaning of Iterator and Iterator::Item doesn't change at all, but APIs that want to start accepting LendingIterator can do so fully backwards-compatibly. Because there is only one trait, there are no coherence issues.

[steffahn]

Here’s a rough idea I’ve had before that I want to develop further, eventually.

My idea was not to use trait aliases but still actual traits, while de-coupling the implementation from the trait itself. The trait template idea could also be useful if someone wanted to define e.g. convenient ways of implementing trait hierarchies without boilerplate (and without macros), e.g. someone might want to be able to implement Eq + PartialEq + Ord + PartialOrd all with a single impl defining the single method cmp, and this could become convenient with a trait template OrdEq that implies all of Eq + PartialEq + Ord + PartialOrd, implementing the missing methods such as eq in terms of cmp.

A benefit of having Iterator still be an ordinary (yet no longer directly implementable) trait would be that it’s easy to avoid any need to new ideas like the “bivariant_in” you proposed. In the linked post, the Async and Future traits are analogues to the LendinIterator and Iterator traits in this case, respectively.

[afetisov]

LendingIterator::next is supposed to have the signature

fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>

That's the point - you can borrow data from the specific next invokation. I don't see how your proposal helps to disentangle the input and output lifetimes, so that it would reduce to Iterator.

I also don't see how that's different from allowing defaulted lifetimes and associated types.

[2e71828]

In the case that the definition of Item<'a> doesn't actually depend on 'a for a particular impl, it can still be returned from LendingIterator::next without issue in a generic context. If there's a bound that represents this non-dependence property, then Iterator is equivalent to LendingIterator where for<'a> Self::Item<'a>: DoesNotActuallyUse<'a>.

[afetisov]

Kinda. But we don't have a way to express such bounds in current Rust. It looks like something fundamental and a bit like specialization (and thus may have problematic soundness).

Anyway, the trait syntax isn't the issue here.

[2e71828]

It is sort-of possible to express today, except that it only works for 'static types due to the requirement for where Self:'a on GATs:

trait LendingIterator {
    type Item<'a> where Self:'a;
    fn next<'a>(&'a mut self)->Option<Self::Item<'a>>;
}

trait MyIterator {
    type Item;
    fn next(&mut self)->Option<Self::Item>;
}

impl<I,T> MyIterator for I where for<'a> I:'a + LendingIterator<Item<'a>=T> {
    type Item = T;
    fn next(&mut self)->Option<T> {
        <Self as LendingIterator>::next(self)
    }
}

struct A(i32);

impl LendingIterator for A {
    type Item<'a> = i32 where Self:'a;
    fn next<'a>(&'a mut self)->Option<i32> { unimplemented!() }
}

fn main() {
    let _:Box<dyn MyIterator<Item=i32>> = Box::new(A(42));
}

Rust Playground

[Jules-Bertholet]

I previously sketched out the idea of "variance bounds" here. But it's not a unique idea; Niko's blog post has a version of it, for example ("for<'a> LendingIterator<Item<'a> = U>"). I didn't go into much detail here, because even alternative schemes will probably need something like it.

[afetisov]

I don't see how that's relevant. The problem isn't variance, but the constraint on input and output lifetime parameters. Do you want to use Self::Item variance to arbitrarily expand the output lifetime at call site? This looks like a way stronger requirement than necessary, and also doesn't solve the issue at hand (the interface still isn't satisfied).

[Jules-Bertholet]

@afetisov

Do you want to use Self::Item variance to arbitrarily expand the output lifetime at call site?

Yes, exactly. The point of variance bounds is to allow the borrow checker to make use of the information they encode. There isn't much reason to have them otherwise.

[Jules-Bertholet]

RFC posted: RFC: Implementable trait aliases by Jules-Bertholet · Pull Request #3437 · rust-lang/rfcs · GitHub