Is this function sound which clones a `&'a A::T<'b>` into a `A::T<'a>` where `A::T` is a generic covariant higher kinded type?

help
1

First, I need a trait for expressing higher kinded types, and one for covariant higher kinded types:

trait Hk {
    type T<'a>;
}

trait Covariant: Hk
{
    fn covariant<'a: 'b, 'b>(
        x: Self::T<'a>,
    ) -> Self::T<'b>;
}

Using these traits, this function doesn't compile:

fn failing<'a, 'b, A: Covariant>(
    x: &'a A::T<'b>,
) -> A::T<'a>
where
    for<'p> A::T<'p>: Clone,
{
    A::covariant(x.clone())
}

I can understand why the rust compiler doesn't let this compile. But I think that it would be sound to force this to compile by using unsafe. What follows is an explanation for why I think so.

An implementation of Hk can either use or not use 'a in T. I will start with the case where it does not use the lifetime (I replaced the generic A with NotContaining in the failing function to create the not_failing1 function):

struct NotContaining<'a>(PhantomData<*mut &'a ()>);

struct InnerNotContatining<'a>(PhantomData<*mut &'a ()>);

impl<'a> Hk for NotContaining<'a> {
    // The type does not depend on 'b
    type T<'b> = InnerNotContatining<'a>;
}

impl<'o> Covariant for NotContaining<'o> {
    fn covariant<'a: 'b, 'b>(
            x: Self::T<'a>,
        ) -> Self::T<'b> {
        InnerNotContatining(PhantomData)
    }
}

fn not_failing1<'a, 'b, 'c>(
    x: &'a <NotContaining<'c> as Hk>::T<'b>,
) -> <NotContaining<'c> as Hk>::T<'a>
where
    for<'p> <NotContaining<'c> as Hk>::T<'p>: Clone,
{
    NotContaining::covariant(x.clone())
}

I added an extra lifetime to NotContaining to emphasize that this should always work, even when NotContaining is not 'static.

Now we will look at the case where the type contains the lifetime (I replaced the generic A with Containing in the failing function to create the not_failing2 function):

struct Containing;

struct InnerContaining<'a>(PhantomData<*mut &'a ()>);

impl Hk for Containing {
    type T<'a> = InnerContaining<'a>;
}

impl Covariant for Containing {
    fn covariant<'a: 'b, 'b>(
            x: Self::T<'a>,
        ) -> Self::T<'b> {
        InnerContaining(PhantomData)
    }
}

fn not_failing2<'a, 'b>(
    x: &'a <Containing as Hk>::T<'b>,
) -> <Containing as Hk>::T<'a>
where
    for<'p> <Containing as Hk>::T<'p>: Clone,
{
    Containing::covariant(x.clone())
}

Note that the type InnerContaining is as restrictive as possible; it is invariant over 'a to force the usage of Containing::covariant.

As far as I understand, this works because the existence of the type &'a <Containing as Hk>::T<'b> proves that 'b: 'a, which makes it possible to cast <Containing as Hk>::T<'b> to <Containing as Hk>::T<'a> using Containing::covariant. This should work for all types containing the lifetime.

In both cases described above, which I think covers all cases, the code compiles. Therefore, it should be sound to use unsafe to force it to compile:

fn not_failing_generic<'a, 'b, A: Covariant>(
    x: &'a A::T<'b>,
) -> A::T<'a>
where
    for<'p> A::T<'p>: Clone,
{
    unsafe{ core::mem::transmute(A::covariant(x.clone()))}
}

I am not at all certain that my logic is right. Therefore, I would like if someone confirms this logic or give an example where this function can be used to invoke undefined behavior. I am sorry if this has been discussed earlier, but it is so specific and obscure that I do not think I could find it in that case.

In case anyone wonders, I don't really have a good use case for this. This is mostly hypothetical. I have a little more real use case, but unless someone actually cares, I will not take the time to write it down.

Playground link

2

You probably know this, but you make it work by adding an explicit bound 'b: 'a even if it may seem redundant.

fn failing<'a, 'b, A: Covariant>(
    x: &'a A::T<'b>,
) -> A::T<'a>
where
    for<'p> A::T<'p>: Clone,
+    'b: 'a
{
    A::covariant(x.clone())
}
3

I am sorry for not mentioning why that can't work in the original question.

The usage for the function is as follows

struct SomeType;
fn with_something<'outer_borrow, ReturnType, A: Hk>(_: &'outer_borrow mut SomeType, user: impl for<'this> ::core::ops::FnOnce(&'outer_borrow A::T<'this>) -> ReturnType) -> ReturnType {
    unimplemented!()
}

fn user<A: Covariant>()
where
    for<'p> A::T<'p>: Clone
{
    with_something::<_, A>(todo!(), not_failing_generic::<A>);
}

The with_something function is generated by ouroboros. This means I can't add another bound to not_failing_generic as it needs to satisfy for<'this> ::core::ops::FnOnce(&'outer_borrow A::T<'this>) -> ReturnType.

4

I think the argument can be reduced to

  • If T<'t> captures 't, &'r T<'t> implies 't: 'r and the covariance call will be fine
    • And it's ok if I call covariance::<'t, 't> and then transmute because the method can't specialize based on lifetimes
  • Else, T<'t> must be the same for all 't
    • And it's ok if I call covariance::<'t, 't> and then transmute because the types are actually the same

Still makes me uncomfortable but I haven't been able to knock a hole in it either.[1]

Alternatively though, you could just make Covariance implementors implement the necessary functionality and avoid unsafe.

trait Covariant: Hk {
    fn covariant<'t: 'u, 'u>(x: Self::T<'t>) -> Self::T<'u>;

    fn covar_clone<'t, 'r>(x: &'r Self::T<'t>) -> Self::T<'r>
    where
        Self::T<'t>: Clone;
    // This should work for all implementors
    // {
    //     Self::covariant(x.clone())
    // }
}

fn failing<'a, 'b, A: Covariant>(x: &'a A::T<'b>) -> A::T<'a>
where
    for<'p> A::T<'p>: Clone,
{
    A::covar_clone(x)
}

  1. There's some weirdness you can pull with higher-ranked types, but I think it's orthogonal to the question. ↩ī¸Ž

1 Like
5

I didn't think of that workaround. Clever!

But because this question is actually entirely hypothetical, I care more about the original method (it's more fun). As you couldn't find any soundness hole I will assume for now that this is sound. If no-one else answers, I will mark your post as the solution.