How to implement a type-level map with an identity function?

[joshlf]

I'm working on a type-level map over a set of types. It looks like this:

trait Trait {
    type MappedTo<M: Mapping>: Trait;
}

trait Mapping {
    type FromA: Trait;
    type FromB: Trait;
}

enum Identity {}

impl Mapping for Identity {
    type FromA = A;
    type FromB = B;
}

enum A {}
impl Trait for A {
    type MappedTo<M: Mapping> = M::FromA;
}

enum B {}
impl Trait for B {
    type MappedTo<M: Mapping> = M::FromB;
}

#[allow(type_alias_bounds)]
type Mapped<T: Trait, M: Mapping> = T::MappedTo<M>;

The idea is that Mapped<T, M> applies the mapping M to the type T. We need to know that this mapping is applicable for all T: Trait, and so we put the actual mapping machinery in Trait itself (the associated MappedTo type).

This works, but it has a usability problem: In a context in which T: Trait is generic and Identity is concrete, the type system isn't smart enough to know that Mapped<T, Identity> = T.

I tried to solve that by adding the following bound to Trait:

// Polyfill for type equality in where bounds
trait Equal<T: ?Sized> {}
impl<T: ?Sized> Equal<T> for T {}

trait Trait
where
    <Self as Trait>::MappedTo<Identity>: Equal<Self>
{
    ...
}

That made the associated type itself choke:

error[E0277]: the trait bound `<<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>: Equal<<Self as Trait>::MappedTo<M>>` is not satisfied
  --> src/lib.rs:10:32
   |
10 |     type MappedTo<M: Mapping>: Trait;
   |                                ^^^^^ the trait `Equal<<Self as Trait>::MappedTo<M>>` is not implemented for `<<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>`
   |
note: required by a bound in `Trait`
  --> src/lib.rs:8:42
   |
6  | trait Trait
   |       ----- required by a bound in this trait
7  | where
8  |     <Self as Trait>::MappedTo<Identity>: Equal<Self>
   |                                          ^^^^^^^^^^^ required by this bound in `Trait`
help: consider further restricting the associated type
   |
8  |     <Self as Trait>::MappedTo<Identity>: Equal<Self>, <<Self as Trait>::MappedTo<M> as Trait>::MappedTo<Identity>: Equal<<Self as Trait>::MappedTo<M>>
   |                                                     ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

What if we move the where bound to type MappedTo?

trait Trait {
    type MappedTo<M: Mapping>: Trait
    where
        <Self as Trait>::MappedTo<Identity>: Equal<Self>;
}

This causes an overflow when evaluating the where bound requirement on the impls themselves:

error[E0275]: overflow evaluating the requirement `<A as Trait>::MappedTo<Identity> == _`
  --> src/lib.rs:26:5
   |
26 |     type MappedTo<M: Mapping> = M::FromA;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0275]: overflow evaluating the requirement `<B as Trait>::MappedTo<Identity> == _`
  --> src/lib.rs:31:5
   |
31 |     type MappedTo<M: Mapping> = M::FromB;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^

I've tried a few other things, similarly to no success. Any ideas on how I can get this to work?

[quinedot]

Does this work for you?

trait Trait: BaseTrait<MappedTo<Identity> = Self> {}

impl<T: ?Sized + BaseTrait> Trait for T
where 
    T: BaseTrait<MappedTo<Identity> = T>
{}

trait BaseTrait {
    type MappedTo<M: Mapping>: Trait;
}

impl BaseTrait for A {
    type MappedTo<M: Mapping> = M::FromA;
}

impl BaseTrait for B {
    type MappedTo<M: Mapping> = M::FromB;
}

// the rest unchanged

trait Mapping {
    type FromA: Trait;
    type FromB: Trait;
}

enum Identity {}

impl Mapping for Identity {
    type FromA = A;
    type FromB = B;
}

enum A {}
enum B {}

#[allow(type_alias_bounds)]
type Mapped<T: Trait, M: Mapping> = T::MappedTo<M>;

[joshlf]

Wooo that works! Thank you so much! Had been banging my head on that one for hours...