Typing is fun! Another crate for self-referential structs

code review
1

I recently came across self-referential structs and found some execellent solutions like self_cell and yoke. They should probably be the go-to choice these days, but I still gave a thought about how these patterns should really work.

My idea is to use HRTB on the function for<'a> fn derive(&'a Owner)->View<'a> to require this function prove that View<'a> is valid for all lifetimes of &'a owner, which happens to include the hypothetical 'self. We can't get the real 'self, but we enforce every action taken on the view to be valid for any possible 'self. Note that View<'a> can be invariant over 'a, but this is not a contradiction, because we never actually does any lifetime conversion. (The lifetime appearing in the struct only acts as a placeholder.)

It seems sound to me, so I took some time to implement it. I did not hit the wall of #![feature(fn_traits)] I originally anticipated, but I was troubled by #![feature(closure_lifetime_binder)] instead and I had to workaround it with some tricks. Here's what I got:

My personal favorite is the elegance of into_parts(). It allows you to decouple the owner and the view if and only if the view is no longer dependent on the owner, e.g. after a series of transformation via map(). This is one of the amazing side effects I got with correct typing.

When I first heard about the Japanese dish Oyakodon(č¦Ŗ子äø¼), I thought it was some sort of dark joke. It's serving chicken and egg together with rice in a bowl, so they call it "parent-and-child bowl". What amuses me is that the word "Oyako" in Japanese sounds like a happy family. I bet chickens would not be thrilled about this, but I thought it made for a great name for the crate.

Any feedback would be appreciated!

2

The first gotcha I checked for is whether Box<T> and &mut T are correctly handled. Glad thatā€™s covered! Though, my understanding is that BowlRef currently has no niche, due to internally using MaybeUninit to get the desired properties. That seems unfortunate, though I suppose that can be improved once std::mem::MaybeDangling is stabilized. My personal solution is to create Box and &mut equivalents which use NonNull, which admittedly loses the possible alignment niches (which the compiler doesnā€™t currently exploit anyway).

3

Iā€™m worried about what could happen when T::Target contains non-'static data. Such cases can introduce implied bounds that might mess up your unsafe codeā€™s reasoning about for<> binders. Combined with contravariance, that can cause problems in yoke (which necessitated some additional bounds to prevent this problem). So, Iā€™m concerned about the map method, for instance.

Iā€™m also not convinced by the safety comment of impl AsRef<BowlRef<'b, T, F>> for BowlRef<'a, T, F>. I donā€™t see why invariance canā€™t cause unsoundness. Iā€™ll try to explore some edge cases.

4

I actually found the aliasable crate using the same NonNull solution, too. I like this approach pretty much but it makes the API more complicated.

5

I would like to hear more about the implied bounds as I figured it's currently an undocumented behavior of HRTB. About AsRef, I'm not claiming that the View<'_> is covariant or contravariant. My proof is to argue that View<'_> can be valid for all lifetimes despite being invariant. And the lifetime used in the struct is merely a placeholder of "all lifetimes" so the major issue is not on AsRef and more on the get()/get_mut() method, I guess.

6

For implied bounds + contravariance, hereā€™s a (now fixed) yoke bug: `yoke` soundness issue with non-`'static` and contravariant cart, using `Yoke::attach_to_cart` + `Yoke::get`. Ā· Issue #2926 Ā· unicode-org/icu4x Ā· GitHub

7

Thanks! I'll take a look at it.

EDIT: This is a really clever hack. If I'm understanding it correctly, yoke is using whatever lifetime of the reference returned by the constructor. oyakodon might not suffer from this issue because it can distinguish the lifetime returned by the constructor from the lifetime of the owner. So:

use yoke::Yoke;

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

fn main() {
    let n = String::from("Hello World!"); // let's call this '1
    let x: Yoke<&'static str, Box<F<'_>>> = Yoke::attach_to_cart(Box::new((|_| {}) as _), |_| &n[..]);
    // infering '_ = '1
    // In oyakodon, `for<'a> F<'a>=&'1 String`
    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();
    // here s.get() returns '1 too

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

One of the Views can create an Output for any given lifetime, but that does not imply that any given Output could have been produced from any lifetime.

Counterexample (which triggers UB):

use std::cell::Cell;

use oyakodon::{BowlRef, Derive, View};


struct CellMaker;

impl<'a> View<&'a str> for CellMaker {
    type Output = Cell<&'a str>;
}

impl<'a> Derive<&'a str> for CellMaker {
    fn call(self, input: &'a str) -> Self::Output {
        Cell::new(input)
    }
}

fn main() {
    let bowl = BowlRef::new("Hello", CellMaker);

    {
        let cell = bowl.get();
        cell.set(&"Goodbye".to_owned());
    }

    println!("{}, world!", bowl.get().get());
}
9

Wow, that was fast! It is a UB. Though I still need some time to figure out why it worked...

10

I'm currently working on a variance-family crate that makes requirements of covariance (or contravariance, if ever needed) easier to express.

...I lowkey spent all of Wednesday working on a particular issue in the ergonomics of that crate only to give up and declare that Rust's trait solver just cannot perfectly express what I want. So when I say it makes the requirement "easier" to express.... I think that I can move almost all the complexity into variance-family so that its users (usually) get to see sunshine and rainbows, though any edge cases that stray off the happy path require implementing three unsafe traits.

11

Update on concerns about variance: BowlBox, BowlRef, and BowlMut are each invariant over all their parameters, so concerns about soundness are limited to the explicit cast* methods. No cast methods are capable of changing the owner type, so contravariance of the owner does not matter.

Here's my (failed) attempt to use contravariance + implied bounds to cause unsoundness:

struct StrView<'a>(&'a String);

impl<'a: 'b, 'b> View<&fn(&'b String)> for StrView<'a> {
    type Output = &'b str;
}

impl<'a: 'b, 'b> Derive<&fn(&'b String)> for StrView<'a> {
    fn call(self, _input: &fn(&'b String)) -> Self::Output {
        self.0
    }
}

fn step1<'a>(
    string: &'a String,
) -> BowlRef<'a, Box<fn(&'a String)>, StrView<'a>> {
    BowlRef::new(
        Box::<fn(&'a String)>::new(|_| {}),
        // Oops! `StrView` doesn't implement `Derive<&'c _>` for *all* lifetimes,
        // but thanks to implied bounds, this still works.
        StrView(string),
    )
}

fn step2<'a>(
    bowl: BowlRef<'a, Box<fn(&'a String)>, StrView<'a>>,
) -> BowlRef<'a, Box<fn(&'a String)>, StrView<'static>> {
    // `StrView<'a>` and `StrView<'static>` have the same output for all lifetimes
    // which are at most `'a`, which is good enough thanks to implied bounds.
    bowl.cast_view()
}

fn step3<'a>(
    bowl: BowlRef<'a, Box<fn(&'a String)>, StrView<'static>>
) -> BowlRef<'static, Box<fn(&'static String)>, StrView<'static>> {
    // Since `Box<fn(&'a String)>` can be freely coerced into `Box<fn(&'static String)>`,
    // it sure would be nice if I could map the owner type like that.
    // However, your type is invariant over the owner type and exposes no way to change the
    // owner type.
    // This step is impossible, and is the reason that contravariance + implied bounds
    // do not manage to break your type.
    unimplemented!()
}
12

I slept over with it and figured that you are totally right about this. get()/get_mut() breaks the HRTB invariant and the view should not be accessed via these methods. I created a safer version, but it's much less ergonomic...

EDIT: I renamed the API.

I found your post about this :smirking_face:

It resembles the yoke issue you mentioned?

13

Exactly, I tried to translate that yoke problem into your crateā€™s types.

14

Life would be much easier if only I had some of your primitives like Varying when writing my crate. If I read it correctly, the problem of variance-family (other than soundness) is that the trait solver cannot prove complex tautologies about lifetimes and so users don't get happy times for free? I hit these issues when writing impl PartialEq and had to trial-and-error finding a way to hint the compiler.

15

Check the dev branch; I think I finally have what I need, though some of the bounds involved are gnarly:

(And yes, I also got those bounds by trial-and-error.)

Now I'm just fleshing out macros and std implementations for variance-family. Then I'll move on to aliasable-view.

16

Wish you luck with that. This is often the phase where rustc tells me that my brilliant idea does not work.

17

I fixed all the tests and am ready for another round of soundness challenge!

18

This is, apparently, the phase where I make a 500-line macro_rules! token tree muncher in the name of "reducing unnecessary repetition in my code".

19

@robofinch I was inspired by your variance-family crate about the organization of lifetime families and managed to prove that if there is a proper CovariantFamily trait, covariance-based self-referential structs can be constructed within the model of oyakodon:

This shows that oyakodon is stronger in terms of expressiveness. And yes, consequently, weaker in soundness. But I hope that provides more insights on what are the necessary conditions for building a self-referential struct. I suspect that HRTB style handlers are needed unless we know the lifetime for sure, otherwise an adversarial can always use the opposite of the length of the lifetime we guessed.

I was also reminded by your code that type View<'a>=&'lb &'a &'ub(); has two-sided constraints on 'a. Previously, my code only handled the upper bound. I tried to incoporate the lower bound but some code just stopped working and I'm not sure whether it's a limitation of the trait solver or a bug in my types. I stared at them for hours and I want to take a break away from it now. Thank you very much for your work on variance! I learned a lot from it!

EDIT: allowing a lower bound on the lifetime is unsound. Let fn derive=|s: &'self String| { cell.store(&'lb *s) } then later drop(bowl) and cell.get(). The cell would contain dangling pointer to a String. Seems that letting derive() skip handling any possible lifetime of owner is unsound.

20

@sshockwave, how's the project going? Here's the state of my project, lifetime-foundry: https://github.com/robofinch/lifetime-foundry/tree/b640df1ffdc2cb4b5c8663390563fb5caba0835a

My variance-family and stable-view crates are provisionally completed, I think, though once I actually go to use them in a self-referential struct crate, I might find problems to fix. I'm now working on an attached-ref crate.

Tentatively, one example of what I'll end up with is:

impl AttachedRef<'other_data, S, Data>
where
    S:    LendFamily<&'static (), Is: Sized>,
    Data: ?Sized + 'other_data,
{ 
    pub fn attach<F>(data: Data, f: F) -> Self
    where 
        // Either one of these next two bounds should work, I think:
        // D: for<'a> SetDefaultView<'a, 'other_data>,
        DefaultViewKind: for<'a> StableView<'a, 'other_data, D>,
        F: for<'a> FnOnce(
            View<'a, 'stable, 'other_data, Data>,
        ) -> Lend<'stable, &'other_data (), S>,
    {
        Self::attach_with::<DefaultViewKind, F>(data, f)
    }

    pub fn attach_with<V, F>(data: Data, f: F) -> Self
    where 
        V: for<'a> StableView<'a, 'other_data, D>,
        F: for<'a> FnOnce(
            CustomView<'a, 'stable, 'other_data, Data, V>,
        ) -> Lend<'stable, &'other_data (), S>,
    { /* ... */ }
}

where AttachedRef has a Lend<'stable, &'other_data (), S> self-reference to its Data field. ('stable would be unsafely lifetime-erased to 'other_data within the actual field.)