Traits can no longer be mutually dependent

[apasel422]

Before #23026, it was possible to use where clauses to have traits that must be implemented together, like:

pub trait Map where Self: Lookup<Self::Key> {
    type Key;
    type Value;
    fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
}

pub trait Lookup<Q: ?Sized> where Self: Map {
    fn get(&self, key: &Q) -> Option<&Self::Value>;
}

The new version (using either the newly supported supertrait syntax or where clauses) now causes a cycle error:

src/lib.rs:1:1: 5:2 error: unsupported cyclic reference between types/traits detected
src/lib.rs:1 pub trait Map where Self: Lookup<<Self as Map>::Key> {
src/lib.rs:2     type Key;
src/lib.rs:3     type Value;
src/lib.rs:4     fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
src/lib.rs:5 }
note: the cycle begins when computing the supertraits of `Map`...
note: ...which then requires computing the supertraits of `Lookup`...
note: ...which then again requires computing the supertraits of `Map`, completing the cycle.
src/lib.rs:4:31: 4:40 error: unsupported cyclic reference between types/traits detected
src/lib.rs:4     fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
                                           ^~~~~~~~~
note: the cycle begins when computing the supertraits of `Lookup`...
note: ...which then requires computing the supertraits of `Map`...
note: ...which then again requires computing the supertraits of `Lookup`, completing the cycle.
src/lib.rs:4:49: 4:60 error: unsupported cyclic reference between types/traits detected
src/lib.rs:4     fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
                                                             ^~~~~~~~~~~
note: the cycle begins when computing the supertraits of `Lookup`...
note: ...which then requires computing the supertraits of `Map`...
note: ...which then again requires computing the supertraits of `Lookup`, completing the cycle.
src/lib.rs:4:72: 4:83 error: unsupported cyclic reference between types/traits detected
src/lib.rs:4     fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
                                                                                    ^~~~~~~~~~~
note: the cycle begins when computing the supertraits of `Lookup`...
note: ...which then requires computing the supertraits of `Map`...
note: ...which then again requires computing the supertraits of `Lookup`, completing the cycle.
src/lib.rs:7:1: 9:2 error: unsupported cyclic reference between types/traits detected
src/lib.rs:7 pub trait Lookup<Q: ?Sized> where Self: Map {
src/lib.rs:8     fn get(&self, key: &Q) -> Option<&Self::Value>;
src/lib.rs:9 }
note: the cycle begins when computing the supertraits of `Lookup`...
note: ...which then requires computing the supertraits of `Map`...
note: ...which then again requires computing the supertraits of `Lookup`, completing the cycle.
src/lib.rs:8:39: 8:50 error: unsupported cyclic reference between types/traits detected
src/lib.rs:8     fn get(&self, key: &Q) -> Option<&Self::Value>;
                                                   ^~~~~~~~~~~
note: the cycle begins when computing the supertraits of `Map`...
note: ...which then requires computing the supertraits of `Lookup`...
note: ...which then again requires computing the supertraits of `Map`, completing the cycle.

This is expected, based on @nikomatsakis's comment in the PR:

This is technically a [breaking-change] because it affects the definition of a super-trait. Anything in a where clause that looks like where Self : Foo is now considered a supertrait. Because cycles are disallowed in supertraits, that could lead to some errors. This has not been observed in any existing code.

However, this seems like a useful pattern.

[nikomatsakis]

On Fri, Mar 06, 2015 at 06:10:52AM -0800, Andrew Paseltiner wrote:

However, this seems like a useful pattern.

Why not merge the two traits, if implementing one always implies
implementing the other? I think we could lift the restriction on
acyclic supertraits, but it would have some implications elsewhere to
do so, such as vtable layout and so forth. Alternatively, we could
continue to distinguish supertraits from traits appearing with Self
in where-clause, but that would remove the intention that
where-clauses are the "desugared" form for constraints.

[apasel422]

For this specific example, I'd like to allow multiple implementations of Lookup but require types to implement Map only once. In other words, all types that implement Map must implement Lookup<<Self as Map>::Key>, but may also provide alternate key lookups. This corresponds to lifting Q from the fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> found in most current concrete map types into a trait for generic programming. The reason I have Lookup also inherit from Map is to avoid a redundant associated type like

pub trait Lookup<Q: ?Sized> {
    type Value;
    fn get(&self, key: &Q) -> Option<&Self::Value>;
}

and to enforce, at the trait level, that Lookup impls only yield values of the same type as the Map impl.

[arielb1]

Supertraits are explicitly required to be acyclic. This is intentional (@apasel422's specific example can be broken by moving the Value associated-type to a Container supertrait).

[apasel422]

@arielb1 Could you explain your suggested refactoring a bit more?

On Tuesday, July 7, 2015, arielb1 notifications@github.com wrote:

Supertraits are explicitly required to be acyclic. This is intentional (
@apasel422 https://github.com/apasel422's specific example can be
broken by moving the Value associated-type to a Container supertrait).

—
Reply to this email directly or view it on GitHub
#23118 (comment).

[apasel422]

For anyone who comes across this later, the pattern ends up being something like:

pub trait Container {
    type Key;
    type Value;
}

pub trait MapLookup<Q: ?Sized>: Container {
    fn get(&self, key: &Q) -> Option<&Self::Value>;
}

pub trait Map: MapLookup<<Self as Container>::Key> {
    fn insert(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
}