title: How can I deserialize a tree of references in Rust?
body: <p>I started using Rust yesterday for this year's Advent of Code. Challenge 7 has you parse a tree structure from a text file. Inputs look like this:</p>
  
  <pre class="lang-none prettyprint-override"><code>root -&gt; child1, child2
  child1 -&gt; child3
  child2
  child3
  </code></pre>
  
  <p>This format represents a tree that starts at "root"; "root" has two children ("child1" and "child2"), and "child1" has one child ("child3"). "child2" and "child3" have no children. The site will never send you input that has cycles.</p>
  
  <p>Parsing is not a problem but I'm having trouble building the tree structure.</p>
  
  <p>If this were C++, I'd write this:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>struct Program {
      string name;
      vector&lt;string&gt; children;
  };
  
  struct ProgramNode {
      string&amp; name;
      vector&lt;ProgramNode*&gt; children;
  
      ProgramNode(string&amp; name);
  };
  
  vector&lt;Program&gt; programs = parse_programs();
  unordered_map&lt;string, ProgramNode&gt; program_nodes;
  for (Program&amp; program : programs) {
      program_nodes.emplace(program.name, ProgramNode(program.name));
  }
  
  for (Program&amp; program : programs) {
      ProgramNode&amp; node = program_nodes.at(program.name);
      for (string&amp; child : program.children) {
          node.children.push_back(&amp;program_nodes.at(child));
      }
  }
  </code></pre>
  
  <p>This builds a map of name to "program" in a first step, and in a second step it fills in the references to "child programs". This is safe if you assume that <code>program_map</code> doesn't outlive <code>programs</code>. Then, if you know the name of the root node, you can do <code>ProgramNode&amp; root = program_nodes.at(root_name)</code> and play with your tree.</p>
  
  <p>I'm trying to write the same thing in Rust, but I'm having issues with the borrow checker. So far I have something like this (with uninteresting details <code>panic</code>'d out):
      use std::collections::HashMap;</p>
  
  <pre><code>struct Program {
      name: String,
      children: Vec&lt;String&gt;,
  }
  
  struct ProgramNode&lt;'a&gt; {
      name: &amp;'a str,
      children: Vec&lt;&amp;'a ProgramNode&lt;'a&gt;&gt;,
  }
  
  impl&lt;'a&gt; ProgramNode&lt;'a&gt; {
      fn new(input: &amp;'a Program) -&gt; ProgramNode {
          panic!();
      }
  }
  
  fn parse_programs() -&gt; Vec&lt;Program&gt; {
      panic!();
  }
  
  fn main() {
      let programs = parse_programs();
  
      let mut program_nodes = HashMap::new();
      for program in &amp;programs {
          program_nodes.insert(&amp;program.name, ProgramNode::new(&amp;program));
      }
  
      for program in &amp;programs {
          let mut program_node = program_nodes.get_mut(&amp;program.name).unwrap();
          for child in &amp;program.children {
              program_node
                  .children
                  .push(&amp;program_nodes.get_mut(&amp;child).unwrap());
          }
      }
  }
  </code></pre>
  
  <p>This doesn't build: the borrow checker is Very Unhappy that I'm trying to double-borrow as mutable from the loop that builds the tree.</p>
  
  <pre class="lang-none prettyprint-override"><code>error[E0597]: borrowed value does not live long enough
    --&gt; src/main.rs:36:63
     |
  36 |                 .push(&amp;program_nodes.get_mut(&amp;child).unwrap());
     |                        -------------------------------------- ^ temporary value dropped here while still borrowed
     |                        |
     |                        temporary value created here
  ...
  39 | }
     | - temporary value needs to live until here
     |
     = note: consider using a `let` binding to increase its lifetime
  
  error[E0499]: cannot borrow `program_nodes` as mutable more than once at a time
    --&gt; src/main.rs:32:32
     |
  32 |         let mut program_node = program_nodes.get_mut(&amp;program.name).unwrap();
     |                                ^^^^^^^^^^^^^ second mutable borrow occurs here
  ...
  36 |                 .push(&amp;program_nodes.get_mut(&amp;child).unwrap());
     |                        ------------- first mutable borrow occurs here
  ...
  39 | }
     | - first borrow ends here
  
  error[E0499]: cannot borrow `program_nodes` as mutable more than once at a time
    --&gt; src/main.rs:36:24
     |
  32 |         let mut program_node = program_nodes.get_mut(&amp;program.name).unwrap();
     |                                ------------- first mutable borrow occurs here
  ...
  36 |                 .push(&amp;program_nodes.get_mut(&amp;child).unwrap());
     |                        ^^^^^^^^^^^^^ second mutable borrow occurs here
  37 |         }
  38 |     }
     |     - first borrow ends here
  </code></pre>
  
  <p>Of course, the borrow checker is absolutely correct. Which leads me to the question: is what I'm trying to do possible at all?</p>