Transitive Trait bound resolution

help
1

This compiles fine:

impl<T> Deref for Wrapper<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target { &self.inner }
}

let b = Wrapper{ inner: Wrapper { inner: Src{}}};
fn check_impl(_: &Src) -> bool {true};
check_impl(&b);

This does not:

fn check_impl(_: impl Deref<Target=Src>) -> bool {true};
check_impl(&b);

I'm trying to define an impl block with bounds that require that the innertmost type of a variable-depth chain of wrappers to be of a specific type. The deref coercion can clearly do this but can this also possible for trait bounds?

2

So, normally, if you try to implement a trait in such a way, you end up with overlapping impls. However, you can overcome this by adding an additional type parameters to disambiguate:

use std::ops::Deref;

pub struct Zero;
pub struct Succ<T>(T);

pub trait TransitiveDeref<Target, Index> {
    fn transitive_deref(&self) -> &Target;
}

impl<T> TransitiveDeref<T, Zero> for T {
    fn transitive_deref(&self) -> &T { self }
}

impl<U, U2, T, I> TransitiveDeref<T, Succ<I>> for U
where
    U: Deref<Target=U2>,
    U2: TransitiveDeref<T, I>,
{
    fn transitive_deref(&self) -> &T {
        U2::transitive_deref(U::deref(self))
    }
}

However, I'm still trying to work out the kinks...

In this case, for some reason I don't quite understand, this technique is producing a lifetime issue. You can kiiiiinda sort of work around it by modifying the trait to have a lifetime:


pub trait TransitiveDeref<'a, Target, Index>: 'a {
    fn transitive_deref(&'a self) -> &'a Target;
}

impl<'a, T: 'a> TransitiveDeref<'a, T, Zero> for T {
    fn transitive_deref(&'a self) -> &'a T { self }
}

impl<'a, U: 'a, U2, T: 'a, I> TransitiveDeref<'a, T, Succ<I>> for U
where
    U: Deref<Target=U2>,
    U2: TransitiveDeref<'a, T, I>,
{
    fn transitive_deref(&'a self) -> &'a T {
        U2::transitive_deref(U::deref(self))
    }
}

fn foo<Index>(x: impl for<'a> TransitiveDeref<'a, i32, Index>) {
    let x: &i32 = x.transitive_deref();
    println!("{}", x)
}

but all of the types need to be 'static.

fn main() {
    foo(&&&&&&4); // it works if all intermediate types are 'static

    let x = 4;
    foo(&&&&&&x); // this won't work because it has `&'a _` where 'a != 'static
}

To get around that, you need to give up on taking impl Trait and instead take &impl Trait so that you can specify the lifetime in &'a self:

fn foo<'a, Index>(x: &'a impl TransitiveDeref<'a, i32, Index>) {
    let x: &'a i32 = x.transitive_deref();
    println!("{}", x)
}

Playground: Rust Playground

1 Like
3

It doesn't have to work with Deref , I actually intend to use custom IntoInner traits for non-public use since Deref is part of the stdlib and only supposed to go onto smart pointers, I was just using it in the example since deref coercion already works recursively.

If I use a custom trait could TransitiveDeref and Deref be merged into a single one?
Anyway, I'll play around with this approach and see how far I get.

4

Thanks, your solution works pretty much verbatim, I only had to substitute Deref with a custom trait.

5

I think I have hit another snag. This has worked so far in a free-standing function. But now I want to move to using the transitive deref as a constraint on an impl block (as mentioned in my original question) and the Index is now considered an unconstrained Type parameter. Is I understand it this only works on functions because type inference figures out a unique solution on its own (if available) while implementations must guarantee a unique solution.

6

The way I like to think of it is: It must be possible to name the monomorphized functions somehow.

First let's get the lifetimes out of the way by changing it to some Clone based trait instead:


pub trait TransitiveClone<Output, Index> {
    fn transitive_clone(self) -> Output;
}

impl<T> TransitiveClone<T, Zero> for T {
    fn transitive_clone(self) -> T { self }
}

impl<'a, T, U, I> TransitiveClone<U, Succ<I>> for &'a T
where
    T: Clone + TransitiveClone<U, I>,
{
    fn transitive_clone(self) -> U {
        T::transitive_clone(T::clone(self))
    }
}

Here, the monomorphized forms of transitive_clone can be named using UFCS:

<&&i32 as TransitiveClone<i32, Succ<Succ<Zero>>>>::transitive_clone(&&3)

Similarly, we can name monomorphized forms of a generic free function:

fn foo<Index, T: TransitiveClone<i32, Index>>(x: T) {
    let x: i32 = x.transitive_clone();
    println!("{}", x)
}

// calling a monomorphized func
foo::<Succ<Succ<Zero>>, &&i32>(&&3)

However, if you put the index on an inherent impl, then there's no place to put the index in the path to the function:

struct MyStruct<T>(T);

impl<T, I> MyStruct<T> where T: TransitiveClone<i32, I> {
    fn get_i32(self) -> i32 { self.0.transitive_clone() }
}

// The fully qualified path does not specify Index.
// This could be ambiguous if e.g. somebody
// implemented `TransitiveClone<i32, Zero> for &&i32` to return 7.
<MyStruct<&&i32>>::get_i32(MyStruct(&&3));

To make it possible to specify Index, we need to move the Index type parameter onto the method:

impl<T> MyStruct<T> {
    fn get_i32<I>(self) -> i32
    where T: TransitiveClone<i32, I>
    {
        self.0.transitive_clone()
    }
}

// Now the fully qualified, monomorphized path includes Index.
<MyStruct<&&i32>>::get_i32::<Succ<Succ<Zero>>>(MyStruct(&&3));
7

Ah, too bad. Specialization needs the constraints to exist on the impl block and I wanted to optimize the case where a chain of wrappers contained a specific element.

8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.