title: Is there a way to avoid using RefCell in a tree that will not be mutated after it's created?
body: <p>I'm writing a short program to <a href="https://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation" rel="nofollow noreferrer">randomly generate a video game dungeon</a>, but I'm having some trouble with creating the sub-dungeons in the tree cleanly.</p>
  
  <p>What I have is ugly and means runtime checked borrowing because of <code>RefCell</code>, even though the tree doesn't need mutability after creation.</p>
  
  <p>Since it's a tree, I used an <code>Rc&lt;T&gt;</code> and <code>Weak&lt;T&gt;</code> to hold references to the child nodes and parent node respectively. This creates the problem that because the values of the child nodes depend on those of their parent, the parent needs to be created in order to give its children their parent reference, while the children need to be created to give the parent its children fields.</p>
  
  <p>If I use a function where child nodes are created before the parent (for example, by passing them the relevant values for the parent fields before the parent is instantiated), they of course won't be able to get the reference to their parent.</p>
  
  <p>The only way I could get this to work was to use <code>RefCell</code> to set the children for each node after they are created, as shown.</p>
  
  <p>This is the struct for each node:</p>
  
  <pre class="lang-rust prettyprint-override"><code>pub struct Dungeon {
      x: u32,
      y: u32,
      end_x: u32,
      end_y: u32,
      parent: Option&lt;Weak&lt;RefCell&lt;Dungeon&gt;&gt;&gt;,
      left: Option&lt;Rc&lt;RefCell&lt;Dungeon&gt;&gt;&gt;,
      right: Option&lt;Rc&lt;RefCell&lt;Dungeon&gt;&gt;&gt;,
  }
  </code></pre>
  
  <p>And this is an outline of the function used to generate the tree given a root dungeon:</p>
  
  <pre class="lang-rust prettyprint-override"><code>fn subdungeons(
      parent: Rc&lt;RefCell&lt;SubDungeon&gt;&gt;,
      level: u32,
  ) -&gt; (Option&lt;Rc&lt;RefCell&lt;Dungeon&gt;&gt;&gt;, Option&lt;Rc&lt;RefCell&lt;Dungeon&gt;&gt;&gt;) {
      // These two lines are a stand-in for the actual code used to generate
      // the values for a child dungeon given its parent. The 'left'
      // and 'right' fields are necessarily 'None' after creation
      let mut left_sub: Dungeon = Dungeon::generate(Rc::downgrade(&amp;parent));
      let mut right_sub: Dungeon = Dungeon::generate(Rc::downgrade(&amp;parent));
  
      if level != 0 {
          let (l, r) = subdungeons(Rc::clone(&amp;left_sub), level - 1);
          left_sub.borrow_mut().left = l;
          left_sub.borrow_mut().right = r;
  
          let (l, r) = subdungeons(Rc::clone(&amp;right_sub), level - 1);
          right_sub.borrow_mut().left = l;
          right_sub.borrow_mut().right = r;
      }
  
      (Some(left_sub), Some(right_sub))
  }
  </code></pre>
  
  <p>Is there a way to re-write this in a way that doesn't involve introducing <code>RefCell</code>? The tree does not need to be mutable after creation, but I can't think of any other way to break the cycle where the parent needs the children to be created in order to be instantiated, but the children also need the parent to have been created in order to get their parent reference.</p>
  
  <p>Naturally this wouldn't be a problem in a normal tree where values of the nodes pushed to a parent are usually unrelated to those of the parent, but I can't seem to find a good Rust solution to a situation like this where they are.</p>