Asserting covariance naively

For a crate I'm working on (a souped-up version of yoke, tentatively named attached-ref), I need to be able to assert that some higher-kinded type T<'varying> is covariant over its 'varying parameter in a macro^[1].

Brushing past all the details about how I'm implementing higher-kinded types with a lifetime parameter, one might naively try the following^[2]:

macro_rules! assert_covariant {
    ($type_path:path) => {
        fn __coerce_owned<'long: 'short, 'short>(
            this: $type_path<'long>
        ) -> $type_path<'short> {
            this
        }
        
        fn __coerce_ref<'r, 'long: 'short, 'short>(
            this: &'r $type_path<'long>
        ) -> &'r $type_path<'short> {
            this
        }
    };
}

If T<'varying> is covariant, then the 'long lifetime can be shortened to 'short in covariant positions, and the above compiles. The assumption is that the reverse should also hold: if assert_covariant!(T) compiles, then T<'varying> should be covariant over 'varying. The above two checks are essentially what derive(Yokeable) performs.

An obstacle: Deref

However, proving that T<'long> can coerce to T<'short> in a few covariant positions doesn't imply that a covariant coercion was the thing responsible. There are several other possible coercions (with variance-based coercions falling in the category of subtyping coercions): Type coercions - The Rust Reference

The most "interesting" to me is Deref coercion, which lets you run arbitrary code and perhaps produce some very pathological implementations. (See also https://internals.rust-lang.org/t/unsoundness-in-pin/11311.) I was able to whip up the following, which (for at least a little while) made me fear for derive(Yokeable)'s soundness:

struct Invariant<'a>(&'a mut &'a str);
struct Covariant<'a>(&'a str);

// Idea:
// &'long Invariant<'long> coerces (via Deref) to
// &'long Covariant<'long> which coerces (via subtyping) to
// &'short Covariant<'short> which coerces (via Deref) to
// &'short Invariant<'short>

impl<'a> core::ops::Deref for Invariant<'a> {
    type Target = Covariant<'a>;

    fn deref(&self) -> &Self::Target {
        Box::leak(Box::new(Covariant("hello")))
    }
}

impl<'a> core::ops::Deref for Covariant<'a> {
    type Target = Invariant<'a>;

    fn deref(&self) -> &Self::Target {
        Box::leak(Box::new(
            Invariant(
                Box::leak(Box::new("hi"))
            )
        ))
    }
}

Fortunately, the impl generated by derive(Yokeable) fails, and the closest I could come to causing a problem is the following:

unsafe impl<'a> yoke::Yokeable<'a> for Invariant<'static> {
    type Output = Invariant<'a>;
    #[inline]
    fn transform(&'a self) -> &'a Self::Output {
        self as &Covariant<'_>// as &Invariant<'_>
    }
    #[inline]
    fn transform_owned(self) -> Self::Output {
        *(&self as &Covariant<'_> as &Invariant<'_>)
    }

    // ...
}

Crucially, an arbitrary owned self is not necessarily a position where deref coercion can occur; I needed to throw in a & to enable the coercions. The compiler should never insert a *& in an implicit coercion. (Plus, it fails for other reasons, too; implicit autoderefs would hit the recursion limit, and while a Sufficiently Smart Compiler™ might figure out which coercions to apply to transitively coerce Invariant<'long> to Invariant<'short>, the current compiler would need to be manually informed of the middle Covariant step.)

Moreover, derive(Yokeable) cannot be applied to any of the std types for which deref coercion can occur (that is, derive(Yokeable) does not have to work when Self is &'static Invariant<'static>, in which case deref coercion could apply).

However, I'm not implementing yoke. My crate is much more generalized, and, unfortunately, I do also need to care about T<'varying> HKTs where the outermost type may be (for instance) a reference, including the &'varying Invariant<'varying> HKT. While I could simply rely on rustc being far from a Sufficiently Smart Compiler™ capable of causing a problem... I hate that approach.

Properly (I hope) asserting covariance

So, I need to get a wrapper W around T<'varying> such that W<T<'long>> coerces to W<T<'short> if and only if a T<'varying> is covariant over 'varying. Assuming that W is covariant over its parameter, that's equivalent to requiring that a subtyping coercion be the only possible coercion from W<T<'long>> to W<T<'short>. My revised attempt, then, is

macro_rules! assert_covariant_improved {
    ($type_path:path) => {        
        fn __coerce_option<'long: 'short, 'short>(
            this: ::core::option::Option<*const $type_path<'long>>
        ) -> ::core::option::Option<*const $type_path<'short>> {
            this
        }
    };
}

Going through the possible coercions (and using 'lt_1 and 'lt_2, since the below reasoning should also apply to showing that T<'varying> is contravariant over 'varying):

• Option<*const T<'lt_1>> can coerce to Option<*const T<'lt_2>> if Option<*const T<'lt_1>> is a subtype of Option<*const T<'lt_2>>. (By the covariance of Option and *const over their sole parameters, this subtyping occurs if T<'lt_1> is a subtype of T<'lt_2>. Unless I'm missing something really important, at least in simple cases like Option and *const if not in some pathological edge case I'm unaware of, it also occurs only if T<'lt_1> is a subtype of T<'lt_2>.)
• Transitive coercions build on other coercions, and subtyping relationships are transitive; so, if subtyping coercions are the only possible coercion from Option<*const T<'lt_1>> to Option<*const T<'lt_2>> other than transitive coercions, then all possible coercions between the types are subtyping coercions.
• &mut T to &T, *mut T to *const T, &T to *const T, and &mut T to *mut T do not apply, since Option<*const T<'lt_1>> is not a reference or raw pointer. Only the outer type matters (and a quick test on the playground, just in case the reference is wrong, confirmed as much).
• Neither &T or &mut T to &U if T implements Deref<Target = U> nor &mut T to &mut U if T implements DerefMut<Target = U> apply, since Option<*const T<'lt_1>> is not a reference. The dreaded pathological Deref coercion cannot harm us!
• Unsizing coercions cannot coerce Option<*const T<'lt_1>> to Option<*const T<'lt_2>>, since Option<*const T<'lt_1>> is not &_, &mut _, *const _, *mut _, or Box<_>.
• Option<*const T<'lt_1>> is not a function item type or a non-capturing closure.
• Option<*const T<'lt_1>> is not !.

Therefore, only subtyping coercions can apply; assert_covariant_improved should work. I suppose one (extreme) potential fear, then, is that some new coercion gets introduced into a future Rust version which somehow manages to break no safe code and no unsafe code other than mine (due to letting more stuff compile than I assume possible), making my code then be unsound.

Review

Since there's not much point in worrying about hypothetical breakage, the most relevant fear is that something about my above reasoning is wrong. (Maybe there's a form of coercion not listed in the reference that I'm unaware of.) Thus why I've marked this post as a code review; I'd like a few more eyes on these ideas. Is assert_covariant_improved as correct as I think it is?

I threw together a few things in this playground (some of it slightly out of date from above code) that might serve as a starting point for messing around:

1. This is needed to provide a macro that soundly implements an unsafe trait indicating that a HKT is covariant, for user convenience in cases simple enough for the macro to implement the trait. ↩︎

2. setting aside details like generic parameters and where-bounds ↩︎

1 post - 1 participant

Read full topic