yoke soundness issue with non-'static and contravariant cart, using Yoke::attach_to_cart + Yoke::get.

[steffahn]

Here’s a repro, in small steps with useful type annotations

use yoke::Yoke;

type F<'a> = fn(&'a ());

fn main() {
    let n = String::from("Hello World!");
    let x: Yoke<&'static str, Box<F<'_>>> = Yoke::attach_to_cart(Box::new((|_| {}) as _), |_| &n[..]);
    let y: Yoke<&'static str, Box<F<'static>>> = x;
    let s: &'static Yoke<&'static str, Box<F<'static>>> = Box::leak(Box::new(y));
    let r: &'static str = s.get();

    println!("pre-drop: {r}");
    drop(n);
    println!("post-drop: {r}");
}

Run Online in Rust Explorer

pre-drop: Hello World!
post-drop: �[YU��Es

[robertbastian]

@Manishearth

[Manishearth]

Oh, that's pretty insidious.

Some easy fixes would be to either restrict carts to 'static (then we lose the abiltiy to have borrowed carts, which I don't want to lose), or to restrict carts to some unsafe Cart trait (that woudl also fix #2095)

However I think we might be able to handle this by PhantomData'ing the cart so that it's forced to be covariant (which when mixed with contravariance, leads to invariance, so we're golden)

[Manishearth]

I have a fix that forces things to be invariant, which basically stops the step from x to y.

However, I'm somewhat uneasy because I'm not convinced that the attach_to_cart call should compile in the first place: This may be a compiler bug.

This is a very subtle interaction between variance, HRTBs, and well-formedness, and WFness isn't documented well enough for me to be able to give a clear answer, but I'm investigating by poking around and I'll see what I find.

[steffahn]

Forcing the cart to be invariant should indeed fix the problem; forcing "covariance" in the right sense - while perhaps more desirable (since it's less restrictive) - is not really possible with the yoke API, AFAICT. The cart's type parameter itself already is covariant in Yoke, the problem is determining whether the type of the cart itself contains contravariant lifetimes.

[steffahn]

For context: this issue in a different crate had a comparable underlying problem

Voultapher/self_cell#18

but their API involves a macro call that can know about all the lifetime parameters of the (equivalent of the) cart type, so forcing covariance (or else making the cart invariant) is as easy as adding another field covariantly using all the lifetimes of the cart.

[steffahn]

Another way to fix this issue would be to introduce a (covariant) lifetime argument for Yoke as in Yoke<'a, Y, C> and add a C: 'a bound to Yoke.

[Manishearth]

forcing "covariance" in the right sense - while perhaps more desirable - is not really possible (since it's less restrictive) with the yoke API

Yep, Rust does let you force all lifetimes in a parameter to be invariant, but it does not let you force them to be "at most covariant", since Rust's variance tools are the ability to:

• create covariant lifetimes (using references)
• force invariance on lifetimes (using cells/mut)
• pass through the variance of lifetimes (using simple wrappers)
• invert the variance of lifetimes (using fn parameters)

So the only tools that let you change variance are the ones that invert it (we don't want that), and the ones that force invariance.

---

But anyway, I'm now convinced this is a compiler/language bug (likely related to rust-lang/rust#25860), and am in the process of filing one. Might still land a fix here since it's a complex bug that may never get fixed.

[steffahn]

I'm not seeing any compiler bugs here, but feel free to elaborate, and I can add my interpretation of the situation when I have more time at hand, later today.

[Manishearth]

@steffahn Bug filed at rust-lang/rust#106431

The bug is that your attach_to_cart call should never have compiled: attach_to_cart's signature requires the closure to work for all 'de, and the closure clearly only works for 'de that is shorter than or equal to the lifetime of s.

My mitigation tactic (force all lifetimes in the cart to be treated as invariant) prevents such a contravariant carted Yoke from being used maliciously after the Yoke is created; however the Yoke should not have been possible to create in the first place.

[Manishearth]

Another potential fix would be to make C::Target: 'static in the attach_to_cart bounds. This means that:

• &'a [u8] still works as a cart in attach_to_cart() (but Box<&'a [u8]> does not)
• complex carts with borrows are still allowed (unsafely, via replace_cart and friends)
• carts retain variance

This gives maximum flexibility but disallows a couple things (that I personally don't care about) from going through the attach_to_cart signature (but they are still possible). OTOH the current proposed solution retains maximum flexibility of attach_to_cart, but then we get an insurmountable variance restriction.

Either way, let me make my PR with the current fix, and we can debate whether we should force invariance on carts or force C::Target: 'static in the attach signature.

[Manishearth]

Fix in #2949

[CAD97]

(I didn't read enough of the yoke PR and misinterpreted bits; what I say here is not new information and matches what you've said.)

I don't fully understand the interaction going on here, but given

F: for<'de> FnOnce(&'de <C as Deref>::Target) -> <Y as Yokeable<'de>>::Output,

and this supposedly implying C: 'de being the issue (in limiting the universality of 'de) — if this is caused by a Rust bug, I don't think it's related to variance in any way as implied by blaming rust-lang/rust#10643. Rather, I think the issue is that &'de <C as Deref>::Target is implying C: 'de at all (it's not required for WF), instead of <C as Deref>::Target: 'de (required for WF).

This matches some vague memory of mine as well, where projections interact with implied bounds poorly.

If the goal is forcing that the output borrows from the input, for<'a> fn(&'a T) -> &'a U is the standard way of accomplishing it, and the indirection of Deref and Yokeable shouldn't matter... so long as you remember that's a maximum bound. It's of course always been possible that the output borrows from anything guaranteed to outlive T. That's typically 'static data, but given a short-lived T, a longer-short-lived loaner can be validly borrowed from.

[CAD97]

W.r.t. #2095, a trait Cart would help, but making a fix without a language addition (as discussed in the issue) is still difficult. What needs to happen is to define some sort of Dormant<C> type(alias¹) which is used instead of C by-value. With that, the only API which needs to change is replace_cart²; backing_cart and even wrap_cart_in_* can be rewritten to never use C by-value, only Dormant<C>.

W.r.t. this issue, though, I don't know if it's possible for the trait to guarantee <C as Deref>::Target to not be contravariant, without a trait manually implemented for all pointee types as well. That really starts to get into overburdensome requirements, especially since we can't even provide a blanket for 'static values since that conflicts with the useful impls, making it no different than a plain 'static bound.

As such, while I'm still weakly in favor of introducing our own Cart trait instead of using StableDeref, I don't see it helping much with this issue, thus don't see this issue as being a motivator towards introducing the trait.

... would it be a sufficient fix to make C::Target invariant just for the attach_to_cart closure? That is, the bound becomes

F: for<'de> FnOnce(CartView<'de, C>) -> <Y as Yokeable<'de>>::Output,

with the goal of CartView: 'de being nonproblematic, perhaps as

struct CartView<'de, C> {
    view: &'de <C as Deref>::Target,
    safe: InvariantMarker<<C as Deref>::Target>,
}
impl Deref for CartView<'de, C> {
    type Target = <C as Deref>::Target;
    fn deref(&self) -> &Self::Target {
        self.view
    }
}

If I've understood the unsoundness attack properly, this might be sufficient to block it while only making attach_to_cart a little more annoying to use.

Though note that a targeted fix to attach_to_cart also needs to apply to map_project as well, so it's not possible to attach a fine yoke but then still map_project to the problematic one.

Footnotes

1. Doing so at a library level, it's potentially sufficient to define Dormant as a MaybeUninit wrapper that implements Drop, though that breaks the #[may_dangle] behavior by introducing nontrivial drop glue. The more targeted is to make a RawBox that acts like Box but stores ptr::NonNull, then make Dormant<C> a <C as Cart>::Dormant projection equal to C except for Box which projects to RawBox. The trick is that the two are transmute-compatible, so once behind an indirection, it can be reinterpreted back to just C instead of Dormant<C>. ↩

2. It's sufficient to make replace_cart take FnOnce(Dormant<C>) -> Dormant<C2>. The extra condition is that the carts must never be used except behind an indirection. Concrete unsizing is thankfully still trivial (but can't use the unsize crate's interface). Wrapping needs to move Dormant<C> into place and then transmute the Dormant wrapper to the base level. ↩

[steffahn]

Another way to fix this issue would be to introduce a (covariant) lifetime argument for Yoke as in Yoke<'a, Y, C> and add a C: 'a bound to Yoke.

Maybe to add more explanation, since it’s not the most intuitive thing how adding a lifetime argument alone fixes the issue: The 'a argument would be some lower bound for the lifetimes (syntactically) appearing in C that needs to be decided at construction time. The implementation would literally involve nothing more than adding (something like) a PhantomData<fn() -> &'a C> field to the Yoke struct, and making all other API fully generic over the lifetime.

The covariance of 'a in &'a C would then mean that even though all the lifetime in C could grow (i.e. become larger / closer to 'static), but 'a will always stay part of the Yoke and never grow, only possibly shrink. At construction time, the C: 'a bound made sure that the for<'de> FnOnce(&'de <C as Deref>::Target) -> <Y as Yokeable<'de>>::Output closure passed to attach_to_cart had to allow all lifetimes 'de up to 'a: 'de, but no fewer, so references of lifetime 'a or larger might have made it into the <Y as Yokeable<'de>>::Output from the closure captures, but no shorter ones.

Then, the get method has a &self argument which means that get<'s>(&'s self) -> &'s <Y as Yokeable<'s>>::Output, has a &'s Yoke<'a, Y, C> parameter, which comes with an implicit 'a: 's bound. So get can only return references with lifetimes up to 'a and hence shorter than any reference that could have made it into the value from closure captures of the attach_to_cart call.

---

Regarding usage, the common case of carts without lifetimes could just use Yoke<'static, Y, C> which is equivalent to the “require C: 'static” solution. The other common case of a cart with a single covariant lifetime Cart<'a> could just use YokeUsage<'a> = Yoke<'a, Y, Cart<'a>>, and the whole YokeUsage type like this would still be covariant in 'a. But if the same was done to a contravariant Cart<'a>, the resulting YokeUsage<'a> would become invariant.

If the cart had two lifetime Cart<'a, 'b>, but came with a constraint like e.g. 'a: 'b, then we’d use the shorter one, as in Yoke<'b, Y, Cart<'a, 'b>>; downsides of adding the lifetime argument like this would only show up once we have multiple unrelated lifetimes, because in this case, we would be required to add a new lifetime parameter.

In other words: Previous users that might have had used yoke in a struct as struct S<'a, 'b>(Yoke<Y, Cart<'a, 'b>>) could simply adapt their type to being struct S<'a, 'b>(Yoke<'b, Y, Cart<'a, 'b>>) if Cart comes with a 'a: 'b bound, but might be forced to add another lifetime argument themselfes, too, if that wasn’t the case, as in struct S<'a, 'b, 'c>(Yoke<'c, Y, Cart<'a, 'b>>) which would not be a struct S<'a, 'b, 'c> with a 'a: 'c and 'b: 'c bound. However, I assume this approach should still be workable in most cases, and also the Cart<'a, 'b> case (with unrelated lifetimes 'a and 'b) should be relatively uncommon already anyways.

[Manishearth]

Yeah, I'd rather not change the Yoke API to include a lifetime, even if the common case gets a 'static

I think the plan of restricting C::Target: 'static should be enough here.

[CAD97]

I agree that C::Target: 'static is minimally restrictive to any intended use case. It's a reasonably common restriction among self-referential providers, and especially among specifically Arc projection, where Arc<dyn Any + Send + Sync> tends to get used (essentially yoke's erase_arc_cart, but mandatory) by default for simplicity/uniformity.

Though perhaps as an alternative middle ground, we could define type Yoke<Y, C> = PowerYoke<'static, Y, C>? Then most cases get the 'static bound by default without needing to state it, but it's possible to drop down and loosen in the rare cases where someone wants a non-'static cart; as steffahn shows, the fully elaborated type probably already has the appropriate lifetime to slot in there.

Not doing so is certainly much simpler, though, and I'm having trouble coming up with a use-case that wants a non-'static cart payload.

Most somewhat realistic cases I can come up with are yoking to another zero-copy structure, e.g. Yoke<&Item, &ZeroMap>, but it doesn't seem actually beneficial, especially since you can probably go &'a ZeroMap -> &'a Item and don't need to yoke to most zero-copy structures to avoid introducing a new lifetime.

It's perhaps an unfortunate restriction as only an approximation of the actual requirement, and thus probably deserves a note in the docs somewhere, but I don't see it being much more than a technical footnote in practice. I'll often point to the hoops yoke jumps through as fundamentally required for generalized self-heap-referencing; for that purpose it's good if "cart pointee is 'static" and "only shared cart access" are publicly documented as simplifying assumptions rather than fundamental to the problem domain.

(Having a power-yoke crate sacrificing usability for maximum generality might be a useful teaching tool, but yoke isn't intended to be that. It's probably the most general self-referential servicer, but it absolutely should be making compromises of generality to improve usability if it doesn't prevent the desired zero-copy owner-and-view bundling.)

[steffahn]

On the note of more powerful extensions that can be narrowed down with a type synonym: There could be two alternative wrappers for the cart to choose from, and an unsafe trait. E. g. a trait CartContainer so that then a more powerful PowerYoke<Y, CC> would require CC: CartContainer. One such container would be Invariant<C> which wraps up any type qualifies as cart in the status quo, but makes it invariant with a phantomdata marker. The other container would be LifetimeBound<'a, C> and comes with a covariant 'a lifetime argument as well as C::Target: 'a bound. Depending on what the preferred canonical/simple solution is (between invariance or requiring 'static), the simplified type would be Yoke<Y, C> = PowerYoke<Y, Invariant<C>> or Yoke<Y, C> = PowerYoke<Y, LifetimeBound<'static, C>>.

This naturally does not discuss the trade-off of leaving the API more simple vs. more powerful; especially since type synonyms like this tend to make reading the docs a bit harder.

[Manishearth]

Yeah, also it's worth noting that C::Target: 'static will only restrict attach_to_cart, not the general usage of Yoke, so it's totally fine to build this as a safe API on top of Yoke + replace_cart() (and we can provide other yoke raw-construction APIs if necessary)

(even though yes, replace_cart still has issues)

[Manishearth]

Yeah I'm deliberately avoiding PowerYoke-type solutions because those types leak out quickly and Yoke already is in a situation where it can both lead to gnarly compiler bugs (hopefully mostly fixed), and gnarly error messages.

[sffc]

If you want Box<&[u8]>, you can always make your own BoxWrap<[u8]> that derefs directly to [u8]

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2867a8da5de811e03d69c33885e5440c

If attach_to_cart wants to borrow local variables, it would need to put the local variables into the cart. It's easy to do that with a single variable, but two variables with potentially different lifetimes might be tricky. You would need to copy them into a lifetimeless struct, which defeats the purpose of borrowing the local variables.