[Pre-RFC] Scoped `impl Trait for Type`

language design
20

I just pushed an update to the draft that now includes this example here. Overall changes:

  • Added a list of bullet points to the Summary and revised it slightly
  • Coined the term implementation environment to refer to the set of all implementations applicable (to a given type) in a given place
  • Near-completely rewrote the Logical consistency subsection to add subheadings and examples
  • Small fixes and adjustments

For convenience, here's that section in full as of right now (with a tiny formatting fix that's already in my draft here):

Logical consistency

Binding external top-level implementations to types is equivalent to using their public API in different ways, so no instance-associated consistency is expected here. Rather, values that are used in the same scope behave consistently with regard to that scope's visible implementations.

of generic collections

Generics are trickier, as their instances often do expect trait implementations on generic type parameters that are consistent between uses but not necessarily declared as bounded on the struct definition itself.

This problem is solved by making the impls available to each type parameter part of the the type identity of the discretised host generic, including a difference in TypeId there as with existing monomorphisation.

(See type-parameters-capture-their-implementation-environment and type-identity-of-generic-types in the reference-level-explanation above for more detailed information.)

Here is an example of how captured implementation environments safely flow across module boundaries, often seamlessly due to type inference:

pub mod a {
    // ⓐ == ◯

    use std::collections::HashSet;

    #[derive(PartialEq, Eq)]
    pub struct A;

    pub type HashSetA = HashSet<A>;
    pub fn aliased(_: HashSetA) {}
    pub fn discrete(_: HashSet<A>) {}
    pub fn generic<T>(_: HashSet<T>) {}
}

pub mod b {
    // ⓑ

    use std::{
        collections::HashSet,
        hash::{Hash, Hasher},
    };

    #[derive(PartialEq, Eq)]
    pub struct B;
    use impl Hash for B {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }

    pub type HashSetB = HashSet<B>; // ⚠
    pub fn aliased(_: HashSetB) {}
    pub fn discrete(_: HashSet<B>) {} // ⚠
    pub fn generic<T>(_: HashSet<T>) {}
}

pub mod c {
    // ⓒ == ◯

    use std::collections::HashSet;

    #[derive(PartialEq, Eq, Hash)]
    pub struct C;

    pub type HashSetC = HashSet<C>;
    pub fn aliased(_: HashSetC) {}
    pub fn discrete(_: HashSet<C>) {}
    pub fn generic<T>(_: HashSet<T>) {}
}

pub mod d {
    // ⓓ

    use std::{
        collections::HashSet,
        hash::{Hash, Hasher},
        iter::once,
    };

    use super::{
        a::{self, A},
        b::{self, B},
        c::{self, C},
    };

    use impl Hash for A {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }
    use impl Hash for B {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }
    use impl Hash for C {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }

    fn call_functions() {
        a::aliased(HashSet::new()); // ⓐ == ◯
        a::discrete(HashSet::new()); // ⓐ == ◯
        a::generic(HashSet::from_iter(once(A))); // ⊙ == ⓓ

        b::aliased(HashSet::from_iter(once(B))); // ⓑ
        b::discrete(HashSet::from_iter(once(B))); // ⓑ
        b::generic(HashSet::from_iter(once(B))); // ⊙ == ⓓ

        c::aliased(HashSet::from_iter(once(C))); // ⓒ == ◯
        c::discrete(HashSet::from_iter(once(C))); // ⓒ == ◯
        c::generic(HashSet::from_iter(once(C))); // ⊙ == ⓓ
    }
}

Note that the lines annotated with // ⚠ produce a warning due to the lower visibility of the scoped implementation in b.

Circles denote implementation environments:
◯ indistinct from global
ⓐ, ⓑ, ⓒ, ⓓ respectively as in module a, b, c, d
⊙ caller-side

The calls infer discrete HashSets with different Hash implementations as follows:

call in call_functions impl Hash in captured in/at notes
a::aliased - type alias The implementation cannot be 'inserted' into an already-specified type parameter, even if it is missing.
a::discrete - fn signature See a::aliased.
a::generic d once<T> call
b::aliased b type alias
b::discrete b fn signature
b::generic d once<T> call b's narrow implementation cannot bind to the opaque T.
c::aliased :: type alias Since the global implementation is visible in c.
c::discrete :: fn signature See c::aliased.
c::generic d once<T> call The narrow global implementation cannot bind to the opaque T.

of type-erased collections

Type-erased collections such as the ErasedHashSet shown in typeid-of-generic-type-parameters-opaque-types require slightly looser behaviour, as they are expected to mix instances between environments where only irrelevant implementations differ (since they don't prevent this mixing statically like std::collections::HashSet, as their generic type parameters are transient on their methods).

It is for this reason that the TypeId of generic type parameters disregards bounds-irrelevant implementations.

The example is similar to the previous one, but aliased has been removed since it continues to behave the same as discrete. A new set of functions bounded is added:

#![allow(unused_must_use)] // For the `TypeId::…` lines.

trait Trait {}

pub mod a {
    // ⓐ == ◯

    use std::{collections::HashSet, hash::Hash};

    #[derive(PartialEq, Eq)]
    pub struct A;

    pub fn discrete(_: HashSet<A>) {
        TypeId::of::<HashSet<A>>(); // ❶
        TypeId::of::<A>(); // ❷
    }
    pub fn generic<T: 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
    pub fn bounded<T: Hash + 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
}

pub mod b {
    // ⓑ

    use std::{
        collections::HashSet,
        hash::{Hash, Hasher},
    };

    use super::Trait;

    #[derive(PartialEq, Eq)]
    pub struct B;
    use impl Hash for B {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }
    use impl Trait for B {}

    pub fn discrete(_: HashSet<B>) { // ⚠⚠
        TypeId::of::<HashSet<B>>(); // ❶
        TypeId::of::<B>(); // ❷
    }
    pub fn generic<T: 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
    pub fn bounded<T: Hash + 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
}

pub mod c {
    // ⓒ == ◯

    use std::{collections::HashSet, hash::Hash};

    use super::Trait;

    #[derive(PartialEq, Eq, Hash)]
    pub struct C;
    impl Trait for C {}

    pub fn discrete(_: HashSet<C>) {
        TypeId::of::<HashSet<C>>(); // ❶
        TypeId::of::<C>(); // ❷
    }
    pub fn generic<T: 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
    pub fn bounded<T: Hash + 'static>(_: HashSet<T>) {
        TypeId::of::<HashSet<T>>(); // ❶
        TypeId::of::<T>(); // ❷
    }
}

pub mod d {
    // ⓓ

    use std::{
        collections::HashSet,
        hash::{Hash, Hasher},
        iter::once,
    };

    use super::{
        a::{self, A},
        b::{self, B},
        c::{self, C},
        Trait,
    };

    use impl Hash for A {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }
    use impl Hash for B {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }
    use impl Hash for C {
        fn hash<H: Hasher>(&self, _state: &mut H) {}
    }

    use impl Trait for A {}
    use impl Trait for B {}
    use impl Trait for C {}

    fn call_functions() {
        a::discrete(HashSet::new()); // ⓐ == ◯
        a::generic(HashSet::from_iter(once(A))); // ⊙ == ⓓ
        a::bounded(HashSet::from_iter(once(A))); // ⊙ == ⓓ

        b::discrete(HashSet::from_iter(once(B))); // ⓑ
        b::generic(HashSet::from_iter(once(B))); // ⊙ == ⓓ
        b::bounded(HashSet::from_iter(once(B))); // ⊙ == ⓓ

        c::discrete(HashSet::from_iter(once(C))); // ⓒ == ◯
        c::generic(HashSet::from_iter(once(C))); // ⊙ == ⓓ
        c::bounded(HashSet::from_iter(once(C))); // ⊙ == ⓓ
    }
}

// ⚠ and non-digit circles have the same meanings as above.

The following table describes how the types are observed at runtime in the lines marked with ❶ and ❷. It borrows some syntax from explicit-binding to express this clearly, but denotes types as if seen from the global implementation environment.

within function
(called by call_functions)		 ❶ (collection) ❷ (item)
a::discrete HashSet<A> A
a::generic HashSet<A: Hash in d + Trait in d> A
a::bounded HashSet<A: Hash in d + Trait in d> A ∘ Hash in d
b::discrete HashSet<B: Hash in b + Trait in b> B
b::generic HashSet<B: Hash in d + Trait in d> B
b::bounded HashSet<B: Hash in d + Trait in d> B ∘ Hash in d
c::discrete HashSet<C> C
c::generic HashSet<C: Hash in d + Trait in d> C
c::bounded HashSet<C: Hash in d + Trait in d> C ∘ Hash in d

The combination ∘ is not directly expressible in TypeId::of::<> calls (as even a direct top-level annotation would be ignored without bounds). Rather, it represents an observation like this:

{
    use std::{any::TypeId, hash::Hash};

    use a::A;
    use d::{impl Hash for A};

    fn observe<T: Hash + 'static>() {
        TypeId::of::<T>(); // '`A` ∘ `Hash in d`'
    }

    observe::<A>();
}
Yet another half-baked idea for working around the orphan rule