Avoid the orphan rule for Rt Deref (splitting the core)

[CeleritasCelery]

I think we might be able to work around this by introducing a new trait. Right now the generated Deref for Env would look like this.

impl std::ops::Deref for crate::core::gc::Rt<Env> {
    type Target = __Rooted_Env;
    fn deref(&self) -> &Self::Target {
        unsafe { &*(self as *const Self).cast::<Self::Target>() }
    }
}
impl std::ops::DerefMut for crate::core::gc::Rt<Env> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { &mut *(self as *mut Self).cast::<Self::Target>() }
    }
}

We are always just doing a transmute (via pointer cast) to get the Rooted type. If we defined another trait like this:

pub trait RootedDeref {
    type Target;
    fn rooted_deref(&Rt<Self>) -> &Self::Target;
}

Then we could define a blanket Deref impl like this:

impl<T: RootedDeref> Deref for Rt<T> {
    type Target =  <T as RootedDeref>::Target;
    fn deref(&self) -> &Self::Target {
        RootedDeref::rooted_deref(self)
        
    }
}

Then in the proc macro we could define an impl like this:

impl RootedDeref for Env {
    type Target = __Rooted_Env;
    fn rooted_deref(rt: &Rt<Self>) -> &Self::Target {
        unsafe { &*(rt as *const Rt<Self>).cast::<Self::Target>() }
    }
}

That would avoid the orphan rule because we are not using a foreign type anymore. That would let us keep Rt in the core but still #[derive(Trace)] outside of the core.

[Qkessler]

I'm guessing you are using Env as an example, as they are others impls of Rt in level 3, right?

I'm thinking about the constraints of the new trait. Would that trait be defined in level 3 (with the defuns) as well? Just to avoid falling into the orphan rule again.

[CeleritasCelery]

Yes just using Env as an example. The trait would be defined in the core (level 1). The orphan rule says you can’t implement a foreign trait on a foreign type. So to avoid it one of those needs to be crate local. RootedDeref would be a foreign trait, but you would implement it on a local type.

[Qkessler]

Yes, that looks good. Just to make sure I understood. For any types in all levels to derive Trace, the proc macro generates Deref and Deref Mut, but if they are not in the same crate as the types we are implementing, we fall into the orphan rule? (Foreign trait as well). I may be missing something. On the current state of the code, say Env is in core and the Rt is defined there, we wouldn't have issues, but if we try to derive Trace, as Rt is foreign there are issues? Wouldn't the type be local, although Rt act as foreign?

Sorry, hard to grasp.

[CeleritasCelery]

When we add #[derive(Trace)] to type, it adds three impl’s; Trace, Deref, and DerefMut. The deref ones are the problem with the orphan rule, because they are derived for Rt<T> and not just T. Since Rt would be in a different crate after the refactor, that is a foreign type and blocked by the orphan rule. So instead of deriving Deref in the proc macro, we could instead derive our new foreign trait RootedDeref. We are not deriving it for Rt<T> anymore, but deriving it for T. This means that the type is no longer a foreign type, since T is the type we added #[derive(Trace)] to.

Now inside core we create a blanket impl of Deref and DerefMut that has a bound on RootedDeref.

the key thing that makes this work is that RootedDeref is implemented for the local type and not a Rt wrapper of that type.

[Qkessler]

Makes lots of sense, thanks for clarifying.

[Qkessler]

I'm just facing this issue now. There are other examples of foreign traits that are causing us falling into the orphan rule (not quite, but a variation of it). Here's an example:

#[derive(Debug, Default)]
#[repr(transparent)]
struct LispStack(Vec<GcObj<'static>>);

We define the LispStack in the bytecode.rs file. The issue with that is that we then implement lots of foreign traits for its Rt version: Rt<LispStack>:

• Deref
• DerefMut
• Index<usize>
• Index<RangeTo<usize>>

We also implement Rt for LispStack, and Trace for LispStack.

Your solution would solve the Trace derive, but since we implement other foreign traits, this still won't work. I'm thinking that in those cases, we should be the struct to rune_core. LispStack is a core object, in my mind, so it would make sense to include under the objects module, along with its implementations. The bytecode module would then just import it.

[Qkessler]

In the commit that I added above, you can see what I meant with the previous comment. There are some structs that we have the opportunity to move to core and for consistency, we should do so. Since we have LispString and LispVec in core, we should have LispStack there as well.

[Qkessler]

Regarding the changes on the derive macro. Is that something you'll pick up, or should I, given I'm doing the refactoring either way? Probably that's something we can PR first, and once that's green, we'll continue with the rune-core refactoring.

[Qkessler]

Here's the documented trait. I'll make a first go and you can review it here, before PRing, to keep the context in the same issue:

/// Trait created to overpass the orphan rule when deriving the
/// [Trace](`rune_macros::Trace`) derive macro. The derive
/// macro contains a blanket deref like this:
///
/// ```ignore
/// unsafe { &*(rt as *const Rt<Self>).cast::<Self::Target>() }
/// ```
///
/// By creating a trait that the functions defined in the main crate
/// can define, we avoid the orphan rule by implementing `Deref`
/// on the rooted version of the types: [Rt<T>](`self::Rt`).
pub trait RootedDeref {
    type Target;
    fn rooted_deref(rooted: &Rt<Self>) -> &Self::Target;
}

[CeleritasCelery]

As far as LispStack goes, we have two 3 options.

1. Move it into the core. I am less of fan of this because it is only used by the bytecode VM
2. Implement a new trait like we did for Trace deref.
3. Use the new type pattern. I think this is the best approach, and will see if I can work on it today.

[CeleritasCelery]

I tried the new type pattern for LispStack. It worked, but I realized that we other types like you mentioned so I don't think this is the best approach.

A few thoughts:

First is that I think we should consider splitting the #[derive(Trace)] does. It does derive the Trace trait for the type (which is what you would expect), but then it also creates the __Rooted_* hidden struct that is used to Deref through an Rt. These are two separate things. I am thinking that we should split them into two different proc macros. What do you think?

Given that I think we could avoid the problem of implementing functions on Rt<T> by exposing the __Rooted_* struct. rather then implementing things on Rt<T>, we would instead implement them on __Rooted_T. This would avoid orphan rule problems because that new struct is local. And it shouldn't change the ergonomics because Rt<T> derefences into __Rooted_T.

[Qkessler]

Really liked that you suggested different options and tried them out, thanks! I was thinking about this. Regarding the LispStack. I still think that it should be moved to the objects module. Even though only used in bytecode, its responsibility is to define an object in Lisp, in par with the other structs already defined in objects: LispVec, LispFloat, LispString. The fact that it's only used in the bytecode module does not change its responsibility, hence why I would recommend moving there.

Regarding the Trace proc macro separation, I'm thinking about the upsides of the separation, other than actually making the intentions clearer. What you mean by exposing is this:

#[automatically_derived]
#[allow(non_camel_case_types)]
#vis struct #rooted_name #orig_generics #new_fields

I'm thinking a proc macro called Root where we would create the Rooted type and the implement Deref and DerefMut on it. Regarding the implementation of other traits on it, we would now have a RootedHandler (for example) type that we could add other foreign traits on, as it would now be local right?

I'm currently on the core refactoring, and I have already compiled cargo build --release on the core branch of my fork. I'll try to document stuff and make sure you can follow the PR.

[CeleritasCelery]

Even though only used in bytecode, its responsibility is to define an object in Lisp, in par with the other structs already defined in objects: LispVec, LispFloat, LispString.

LispStack is not a lisp object because it doesn’t implement IntoObject. You can’t put it in an object pointer. That is what separates it from LispVec, LispString, etc. it is purely an implementation detail of the bytecode.