title: Hand-over-hand locking with Rust
body: <p>I'm trying to write an implementation of <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">union-find</a> in Rust. This is famously very simple to implement in languages like C, while still having a complex run time analysis.</p>
  
  <p><strong>I'm having trouble getting Rust's mutex semantics to allow iterative hand-over-hand locking.</strong></p>
  
  <p>Here's how I got where I am now.</p>
  
  <p>First, this is a very simple implementation of part of the structure I want in C:</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  
  struct node {
    struct node * parent;
  };
  
  struct node * create(struct node * parent) {
    struct node * ans = malloc(sizeof(struct node));
    ans-&gt;parent = parent;
    return ans;
  }
  
  struct node * find_root(struct node * x) {
    while (x-&gt;parent) {
      x = x-&gt;parent;
    }
    return x;
  }
  
  int main() {
    struct node * foo = create(NULL);
    struct node * bar = create(foo);
    struct node * baz = create(bar);
    baz-&gt;parent = find_root(bar);
  }
  </code></pre>
  
  <p>Note that the structure of the pointers is that of an <strong>inverted tree</strong>; multiple pointers may point at a single location, and there are no cycles.</p>
  
  <p>At this point, there is no path compression.</p>
  
  <p>Here is a Rust translation. I chose to use Rust's reference-counted pointer type to support the inverted tree type I referenced above.</p>
  
  <p>Note that this implementation is much more verbose, possibly due to the increased safety that Rust offers, but possibly due to my inexperience with Rust.</p>
  
  <pre><code>use std::rc::Rc;
  
  struct Node {
      parent: Option&lt;Rc&lt;Node&gt;&gt;
  }
  
  fn create(parent: Option&lt;Rc&lt;Node&gt;&gt;) -&gt; Node {
      Node {parent: parent.clone()}
  }
  
  fn find_root(x: Rc&lt;Node&gt;) -&gt; Rc&lt;Node&gt; {
      let mut ans = x.clone();
      while ans.parent.is_some() {
          ans = ans.parent.clone().unwrap();
      }
      ans
  }
  
  fn main() {
      let foo = Rc::new(create(None));
      let bar = Rc::new(create(Some(foo.clone())));
      let mut prebaz = create(Some(bar.clone()));
      prebaz.parent = Some(find_root(bar.clone()));
  }
  </code></pre>
  
  <p>Path compression re-parents each node along a path to the root every time <code>find_root</code> is called. To add this feature to the C code, only two new small functions are needed:</p>
  
  <pre><code>void change_root(struct node * x, struct node * root) {
    while (x) {
      struct node * tmp = x-&gt;parent;
      x-&gt;parent = root;
      x = tmp;
    }
  }
  
  struct node * root(struct node * x) {
    struct node * ans = find_root(x);
    change_root(x, ans);
    return ans;
  }
  </code></pre>
  
  <p>The function <code>change_root</code> does all the re-parenting, while the function <code>root</code> is just a wrapper to use the results of <code>find_root</code> to re-parent the nodes on the path to the root.</p>
  
  <p>In order to do this in Rust, I decided I would have to use a <code>Mutex</code> rather than just a reference counted pointer, since the <code>Rc</code> interface only allows mutable access by copy-on-write when more than one pointer to the item is live. As a result, all of the code would have to change. Before even getting to the path compression part, I got hung up on <code>find_root</code>:</p>
  
  <pre><code>use std::sync::{Mutex,Arc};
  
  struct Node {
      parent: Option&lt;Arc&lt;Mutex&lt;Node&gt;&gt;&gt;
  }
  
  fn create(parent: Option&lt;Arc&lt;Mutex&lt;Node&gt;&gt;&gt;) -&gt; Node {
      Node {parent: parent.clone()}
  }
  
  fn find_root(x: Arc&lt;Mutex&lt;Node&gt;&gt;) -&gt; Arc&lt;Mutex&lt;Node&gt;&gt; {
      let mut ans = x.clone();
      let mut inner = ans.lock();
      while inner.parent.is_some() {
          ans = inner.parent.clone().unwrap();
          inner = ans.lock();
      }
      ans.clone()
  }
  </code></pre>
  
  <p>This produces the error (with 0.12.0)</p>
  
  <pre><code>error: cannot assign to `ans` because it is borrowed
  ans = inner.parent.clone().unwrap();
  
  note: borrow of `ans` occurs here
  let mut inner = ans.lock();
  </code></pre>
  
  <p>What I think I need here is hand-over-hand locking. For the path A -> B -> C -> ..., I need to lock A, lock B, unlock A, lock C, unlock B, ... Of course, I could keep all of the locks open: lock A, lock B, lock C, ... unlock C, unlock B, unlock A, but this seems inefficient.</p>
  
  <p>However, <code>Mutex</code> does not offer unlock, and uses RAII instead. <strong>How can I achieve hand-over-hand locking in Rust without being able to directly call <code>unlock</code>?</strong></p>
  
  <hr>
  
  <p><strong>EDIT</strong>: As the comments noted, I could use <code>Rc&lt;RefCell&lt;Node&gt;&gt;</code> rather than <code>Arc&lt;Mutex&lt;Node&gt;&gt;</code>. Doing so leads to the same compiler error.</p>
  
  <p>For clarity about what I'm trying to avoid by using hand-over-hand locking, here is a <code>RefCell</code> version that compiles but used space linear in the length of the path.</p>
  
  <pre><code>fn find_root(x: Rc&lt;RefCell&lt;Node&gt;&gt;) -&gt; Rc&lt;RefCell&lt;Node&gt;&gt; {
      let mut inner : RefMut&lt;Node&gt; = x.borrow_mut();
      if inner.parent.is_some() {
          find_root(inner.parent.clone().unwrap())
      } else {
          x.clone()
      }
  }
  </code></pre>