title: Managing the lifetimes of garbage-collected objects
body: <p>I am making a simplistic <a href="https://gist.github.com/anonymous/79fb0bd4dc4d55e67e6b" rel="noreferrer">mark-and-compact garbage collector</a>. Without going too much into details, the API it exposes is like this:</p>
  <pre class="lang-rust prettyprint-override"><code>/// Describes the internal structure of a managed object.
  pub struct Tag { ... }
  
  /// An unmanaged pointer to a managed object.
  pub type Pointer = *mut usize;
  
  /// Mapping from old to new locations.
  pub type Adjust = BTreeMap&lt;usize, Pointer&gt;;
  
  /// Mark this object and anything it points to as non-garbage.
  pub unsafe fn survive(ptr: Pointer);
  
  pub struct Heap { ... }
  
  impl Heap {
      pub fn new() -&gt; Heap;
      
      // Allocate an object with the specified structure.
      pub fn allocate(&amp;mut self, tag: Tag) -&gt; Pointer;
      
      /// Move all live objects from `heap` into `self`.
      pub unsafe fn reallocate(&amp;mut self, heap: Heap) -&gt; Adjust;
  }
  </code></pre>
  <p>This API is obviously fundamentally unsafe. I would like to rework the API (without changing the internals, which are just fine!) to account for the following facts:</p>
  <ol>
  <li><p>All <code>Pointer</code>s to (objects allocated in) a <code>Heap</code> become invalid when the heap is <code>merge</code>d into another heap.</p>
  </li>
  <li><p><code>merge</code> returns an <code>Adjust</code> whose values are valid <code>Pointer</code>s to (objects allocated in) <code>self</code>.</p>
  </li>
  </ol>
  <p>I have the following tentative solution:</p>
  <pre class="lang-rust prettyprint-override"><code>// Replaces Pointer.
  #[derive(Copy, Clone)]
  pub struct Object&lt;'a&gt; {
      ptr: *mut AtomicUsize,
      mark: PhantomData&lt;&amp;'a usize&gt;
  }
  
  impl&lt;'a&gt; Object&lt;'a&gt; {
      pub fn survive(self); // Now supposed to be perfectly safe!
  }
  
  pub type Adjust&lt;'a&gt; = BTreeMap&lt;usize, Object&lt;'a&gt;&gt;;
  
  pub struct Heap { ... }
  pub struct Allocator&lt;'a&gt; { ... }
  
  impl Heap {
      fn allocator(&amp;'a self) -&gt; Allocator&lt;'a&gt;;
      // The following doesn't work:
      // 
      //  fn allocate(&amp;'a mut self) -&gt; Object&lt;'a&gt;;
      //  fn reallocate(&amp;'a mut self, heap: Heap) -&gt; Adjust&lt;'a&gt;;
      // 
      // Because it doesn't allow the user to allocate more
      // than one `Object` at a time (!) in a `Heap`.
  }
  
  impl&lt;'a&gt; Allocator&lt;'a&gt; {
      // Note that the resulting `Object`s are tied to the `Heap`,
      // but not to the allocator itself.
      fn allocate(&amp;mut self, tag: Tag) -&gt; Object&lt;'a&gt;;
      fn reallocate(&amp;mut self, heap: Heap) -&gt; Adjust&lt;'a&gt;;
  }
  </code></pre>
  <p>Is this design correct? If not, what needs to be changed?</p>