Skip to content

Instantly share code, notes, and snippets.

@Manishearth
Created June 7, 2015 18:16
Show Gist options
  • Save Manishearth/7ed4ec6e555be5fb7468 to your computer and use it in GitHub Desktop.
Save Manishearth/7ed4ec6e555be5fb7468 to your computer and use it in GitHub Desktop.
Gc dsign #2: No owned Gc on the stack

Three GC pointers: Gc<T>, GcRef<'a, T>, and GcMove<T> (aka GcRoot<T>). T: Trace for all three

GcRef<'a, T> is really just &'a Gc<T> without the extra indirection. Moving on.

Gc<T> is never to be used on the stack. it is only to be used inside struct fields. It implements Trace. On the stack, it must be referred to via GcRef or &Gc

We abuse the fact that rust doesn't let one move out of a borrow to enforce this. The only thing that is allowed is taking borrows of it.

The idea is:

  • Assume bare Gcs are not allowed on the stack
  • Since Gcs are only found in the form of &Gc and GcRef, we can only ever extract an &Gc field out of these because of the no-move-out-of-borrow rule. (Caveat: mem::swap may cause trouble here once we add internal mutability to the mix. I doubt it though). Gc is neither Copy nor Clone, so (&Gc).clone() can't be done.
  • So, Gcs not being allowed on the stack is self-consistent; a state with no Gcs on the stack cannot be used to create another state with no Gcs on the stack.
  • To top it off, we structure our APIs to never provide bare Gcs.

This means that Gcs will only live in the great big arena in the sky (well, for now we can just use the regular allocator).

However, this provides no way to move out of scope, since we only have borrowed data. For this, the method .to_move() will create a GcMove. This will be opaque (and is NOT Trace), but can be moved around freely. It adds a root when constructed, and removes a root when dropped. It can provide GcRefs. We might want to make it cloneable which will increase the rootcount.

Of course, this presents us with a small problem. It is now impossible to create Gcs in the first place.

Instead of providing APIs that create GCs, we instead provide macros that internally create Gcs and ensure that they are used correctly.

For example, if I wish to create a Gc from a given Foo, I must use gc!(Foo), which provides me with a GcMove (which can then be converted to a GcRef)

On the other hand, if I wish to create a Gc where Foo itself contains a Gc<T>, I use:

gc!(
Foo {
 .....
 thing: Gc::new(...)
}
)

The macro will allow the internal Gc::new() to exist, converting it into a hidden function, but will always return a GcMove on the outside. We can, of course, provide a macro that spits out local GcRefs too.

The gc macro will also allow for setting fields on another GC.

gc!( *some_gc_ref.foo.borrow_mut() = another_gc_ref.to_gc() )

to_gc() will again be converted to a hidden function that allows for GcRef to be converted into a Gc

The advantage here is that tracking roots is simple now; we don't need to worry about leaking roots when a GC goes into the heap.

However, this API is much more verbose since the rooting is explicit. Plus macros. Ick.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment