Trouble implementing higher ranked lifetime type bound for a byte slice

Question

I am trying to implement a trait on a &'a [u8] and use it in an implementation that uses higher ranked lifetimes, e.g.:

pub trait IntoTest<'a, T> {
    fn into_test(&'a self) -> T where Self: Sized;
}

impl<'a> IntoTest<'a, &'a [u8]> for &'a [u8] {
    fn into_test(&'a self) -> &'a [u8] {
        self
    }
}

fn higher_ranked_lifetime<T>(test: T) where T: for<'a> IntoTest<'a, &'a [u8]> {
    let _t = test.into_test();
}

fn main() {
    println!("Hello, world!");
    let vec = vec![1u8];
    let slice = &vec[..];
    higher_ranked_lifetime(slice);
}

Short URL: http://is.gd/1QKhYk

The error I am getting is:

<anon>:19:5: 19:27 error: the trait `for<'a> IntoTest<'a, &'a [u8]>` is not implemented for the type `&[u8]` [E0277]
<anon>:19     higher_ranked_lifetime(slice);

How should I be doing this? Is this even the right thing to do? I do not want to scope my higher_ranked_lifetime to a specific lifetime, but have it be applicable to any byte slice passed to it.

Answer 1

This is not a correct way, and the compiler is right.

One way you can see why it is so is to look at the type (the slice) and the trait you think it implements side by side:

for<'a> IntoTest<'a, &'a [u8]>
&'a [u8]

Here I've added a lifetime parameter on the slice for clarity. You can see that in the trait bound the lifetime parameter 'a is bound by the for qualifier, in other words, this declaration is self-contained, it does not depend on anything in the external scope.

In the slice, however, lifetime parameter 'a is free - it is defined in some external scope, for example, through lifetime elision. Therefore, there is simply no way the slice can satisfy your trait implementation. For it to work your trait should be implemented like this:

impl<'a, 'b> IntoTest<'a, &'a [u8]> for &'b [u8] {
    fn into_test(&'a self) -> &'a [u8] {
        unimplemented!()
    }
}

which compiles, although it doesn't and couldn't do what you want. You can see that in this declaration lifetimes of the slice and in the trait signature are disjoint, therefore slices now do satisfy the for<'a>-based bound.

There is another way to look at this problem. T: for<'a> IntoTest<'a, &'a [u8]> bound means that type T implements the trait for every possible lifetime parameter of that trait, so the function itself can decide which lifetime it wants. For example, it could request 'static. But naturally in your code &[u8] is tied to the vector in the main method and cannot be 'static. Therefore the soundness is violated - this &[u8] can't provide any lifetime the user wants, and so it does not implement for<'a> IntoTest<'a, &'a [u8]>.

Note that just adding a lifetime parameter to the generic function won't work either:

fn higher_ranked_lifetime<'a, T>(test: T) where T: IntoTest<'a, &'a [u8]> {
    let _t = test.into_test();
}

There will be this error:

<anon>:12:14: 12:18 error: `test` does not live long enough
<anon>:12     let _t = test.into_test();
                       ^~~~
<anon>:11:79: 13:2 note: reference must be valid for the lifetime 'a as defined on the block at 11:78...
<anon>:11 fn higher_ranked_lifetime<'a, T>(test: T) where T: IntoTest<'a, &'a [u8]> {
<anon>:12     let _t = test.into_test();
<anon>:13 }
<anon>:11:79: 13:2 note: ...but borrowed value is only valid for the scope of parameters for function at 11:78
<anon>:11 fn higher_ranked_lifetime<'a, T>(test: T) where T: IntoTest<'a, &'a [u8]> {
<anon>:12     let _t = test.into_test();
<anon>:13 }

And this is again correct. Remember that your trait is defined like this:

pub trait IntoTest<'a, T> {
    fn into_test(&'a self) -> T where Self: Sized;
}

Here you require that self is passed by reference with the same lifetime as the lifetime parameter of the trait. However, the above declaration of the generic function makes this method not callable in principle:

fn higher_ranked_lifetime<'a, T>(test: T) where T: IntoTest<'a, &'a [u8]>

Here the trait is specified to have lifetime parameter equal to the lifetime parameter of the function. However, test parameter itself lives only through the body of the function. Therefore, any reference taken to test, including the implicit one when calling into_test():

let _t = (&test).into_test();

will have lifetime strictly less than the lifetime parameter, and so it can't be used as a parameter for into_test() method. This is exactly what the error is about.

Because you didn't explain what you really need, it's hard to say what you should do. I guess one of the most general ways would be to just drop your lifetime parameter on a trait and make the trait method accept self by value, and fix the generic function accordingly:

pub trait IntoTest<T> {
    fn into_test(self) -> T;
}

impl<'a> IntoTest<&'a [u8]> for &'a [u8] {
    fn into_test(self) -> &'a [u8] {
        self
    }
}

fn higher_ranked_lifetime<'a, T>(test: T) where T: IntoTest<&'a [u8]> {
    let _t = test.into_test();
}

fn main() {
    println!("Hello, world!");
    let vec = vec![1u8];
    let slice = &vec[..];
    higher_ranked_lifetime(slice);
}

This does work because now the trait itself does not have any lifetime parameters and does not add any requirements on how to call it. Lifetime parameters are now moved to types which implement it.