Implement GC rooting for DOM objects

[jdm]

Dump from a previous IRC conversation:

17:32:53 <pcwalton> jdm: safe solution for rooting is: make JSManaged noncopyable, add a root!() macro that roots an object, giving you back a Rooted<T>, and places a borrowed pointer on the stack to the Rooted<T> to lock it in place
17:33:20 <pcwalton> the actual root() method is marked unsafe
17:34:13 <pcwalton> but the macro expands into something like: let tmp = $x; unsafe { let $rooted = JSManaged::root(tmp); let kung_fu_death_grip = &$rooted;  }
17:34:31 <jdm> and Rooted presumably does a special thing that ensures the contained value is rooted for the duration of its lifetime?
17:34:35 <pcwalton> yeah
17:34:37 <pcwalton> for now it does nothing
17:34:48 <pcwalton> when we upgrade SpiderMonkey to exact-rooting it'll do something more
17:35:03 <pcwalton> Rooted will have a .get() method that returns a borrowed pointer to the thingy
17:37:06 <jdm> pcwalton: so what are $x and $rooted in an example case?
17:37:22 <jdm> or is there something in the macro expansion that's missing?
17:40:04 <pcwalton> jdm: macro_rules! root( ($rooted:ident = $x:expr) => { …the above... } ) 
17:40:30 <pcwalton> usage: root!(x = node.parent.as_ref().unwrap())
17:40:53 <pcwalton> just use "root" instead of "let"
17:44:39 <pcwalton> hmm, we also need a solution for putting a copy of a JSManaged inside another JSManaged
17:45:53 <pcwalton> maybe that isn't so bad, just have something like JSManaged::set_field(&self, field_ref: &T, value: &JSManaged<T>) and assert that the field is inside "self" (since the sizes are statically known, LLVM will optimize out the assert)
17:46:42  * jdm doesn't follow the problem
17:47:12 <pcwalton> well, if JSManaged is non copyable then you can't do something like my_node.next_sibling = Some(other_node.next_sibling)
17:47:15 <pcwalton> err
17:47:23 <pcwalton> my_node.next_sibling = Some(other_node.prev_sibling)
17:49:33 <pcwalton> hmm, that signature doesn't work for Option
17:49:56 <pcwalton> maybe we should have Option<JSManaged> be a separate thing? doesn't seem particularly satisfying.
17:51:35 <pcwalton> well, hmm, Option has to be Traceable anyway so maybe we could add the "set" method to Traceable.
17:51:42 <pcwalton> that way it would be derived for Option.
17:54:07 <jdm> that feels like it's conflating two things
17:54:26 <pcwalton> yeah, you probably want immutable traceable data too
17:55:30 <pcwalton> jdm: I guess this isn't so hard. autogenerate setters in the Rust compiler too, as part of a different trait
17:55:33 <pcwalton> set_parent() etc
17:55:43 <pcwalton> if we can autogenerate trace hooks, we can autogenerate setters.
17:56:28 <jdm> where do the fields to autogenerate come from?
17:56:38 <pcwalton> deriving now supports special auxiliary metadata
17:57:13 <pcwalton> deriving(MutTraceable(parent, next_sibling, prev_sibling, …))
17:57:16 <pcwalton> or something
17:57:57 <jdm> and what do the setters end up doing? how do you get around the noncopyable restriction?
17:59:15 <pcwalton> they expand into some unsafe_clone() method call
17:59:40 <pcwalton> JSManaged would have an unsafe_clone() which would be marked unsafe
18:00:12 <jdm> also, do the setters really belong on JSManaged?
18:00:23 <jdm> it's the inner type that actually contains the fields
18:00:27 <pcwalton> no, they belong on the inner types
18:00:44 <jdm> oh right, and the traceable is also derived on the inner type

[jdm]

Extracting the key points from above:

macro_rules! root( ($rooted:ident = $x:expr) => {
    let tmp = $x;
    unsafe {
        let $rooted = JSManaged::root(tmp);
        let kung_fu_death_grip = &$rooted;
    }
})
root!(x = node.parent.as_ref().unwrap())

And root! replaces let when declaring JS objects on the stack.

[jdm]

More conversation:

[15:17:15] <jdm> pcwalton: when you talked about making JS<T> noncopyable, does that mean that clone would not work any more?
[15:17:22] <jdm> that's a pretty big change
[15:17:27]  * pcwalton thinks
[15:18:07] <pcwalton> I think it's fine for clone() to work, but it'd be a special kind of clone() that roots the thingy you cloned and pins it to the stack
[15:19:21] <pcwalton> yeah, so I think instead of .clone() it would be jsclone!()
[15:19:22] <pcwalton> or something
[15:20:02] <jdm> the bits about storing copies of other JS instances makes me worried
[15:20:04] <pcwalton> or maybe just call that macro root!()
[15:23:02] <jdm> pcwalton: do you think jsclone! would let us do things like |some_node.get_mut().next_sibling = Some(...some jsclone!'d value)| ?
[15:23:23] <pcwalton> I think so, if handled properly.
[15:23:53] <pcwalton> the jsclone!()'d value would be temporarily rooted to the stack, but then it would be moved away and un-rooted
[15:23:55] <pcwalton> well, hmm
[15:24:15] <pcwalton> I guess there were rooting hazards with moving values that are rooted
[15:24:24] <pcwalton> maybe jsclone!() needs to be separate from root!()
[15:24:50] <pcwalton> root!() is for your stack, jsclone!() is for putting JS values inside other JS values
[15:25:51] <jdm> pcwalton: so clone is used in many places for passing arguments right now; which one is appropriate there?
[15:26:25] <pcwalton> passing arguments to another Rust function probably uses root!()
[15:26:37] <pcwalton> because passing arguments is the stack
[15:26:42] <pcwalton> jsclone! is for the heap
[15:26:53] <pcwalton> maybe jsroot! and jsclone! for consistency?
[15:27:59] <jdm> pcwalton: so if we're not allowed to use .clone(), is there some way to make that a build error?
[15:28:05] <pcwalton> just don't implement it

[jdm]

Other interesting points:

[15:32:28] <jdm> does this address returning JS<T> from a function?
[15:33:06] <jdm> I guess callers would use root!(x = something_returning_js())
...
[15:34:33] <jdm> I bet we could make this properly root in current SM
[15:34:50] <jdm> just have another let decl in the macro that stores the JSObject*
[15:35:00] <jdm> then it's on the stack and the conservative scanner will see it
...
[15:38:07] <Ms2ger> jdm, so are we going to use JS<> for heap and stack pointers both?
[15:38:37] <jdm> Ms2ger: I think that's the idea, since we have trace hooks that should handle the heap ones correctly at all times

[pcwalton]

Here's a small proof-of-concept sketch gist showing what a rooting API might look like: https://gist.github.com/pcwalton/9280996

[jdm]

I have elaborated on the above to allow optional types. Unfortunately it requires two macros, root! and maybe_root!: https://gist.github.com/jdm/9332689

[nikomatsakis]

I guess you need the macro to be root!(... in ...) because of the limitation that a macro can only expand to a single expression, huh? That's interesting. The safe solution to this involves closures (hopefully unboxed once fns) and I figured the macro would avoid the rightward drift... looks like it almost does. It might be possible to fix that limitation in macro expansion, I imagine, though of course I haven't looked at the code in a long time.

[jdm]

New sketch: https://gist.github.com/jdm/9816586

Now stack-based, with dynamic failures for incorrect unrooting order (ie. ownership of a root was moved without re-rooting) and incorrectly initializing (ie. missing Root::init call). Neither of these should be too bad in practice, since the scope in which they can occur should be limited to the failing stack frame.

[jdm]

Improvement! No more need to call init, since moving the newly-created Root value will not cause any misordering problems. In addition, you now use unrooted_value.root(&roots) to create a root, which makes it easier to spot logic errors that occur due to copy and paste.

[jdm]

I've been putting this into practice, and come up with this rooting scheme which I believe is sound: https://gist.github.com/jdm/9920531

[jdm]

In particular, if all DOM constructors return Unrooted<T> then assigning an unrooted value into a member field will be safe, because either

• the enclosing DOM type will be safely rooted (passed in via &mut JSRef<T>), or
• the enclosing DOM type will be explicitly rooted (due to the barrier of Unrooted<T> for local values)

[jdm]

Two more thoughts:

• I can't figure out any way to avoid the danger of rooting an Unrooted value too late (ie. after a GC has occurred); the antidote to this is to root ASAP at all times, but I don't know that there's any way to enforce this statically.
• poisoning Unrooted values after they're rooted would avoid unsafe patterns like root/unroot/root, where there are no guarantees that the value has not been GCed in between the last two steps

[jdm]

Alternatively, do not implement Clonable for Unrooted, and make Unrooted::root take by-value self and ensure that Unrooted is not implicitly copyable.

[jdm]

It was pointed out to me that we could also create a static analysis to check that unrooted types are created immediately.

[jdm]

This happened.