title: Why are non-lexical lifetimes not working when mutably traversing a linked list?
body: <p>Consider the following linked list structure:</p>
  <pre class="lang-rust prettyprint-override"><code>struct Node {
      value: i64,
      next_ptr: Option&lt;Box&lt;Node&gt;&gt;,
  }
  
  struct SortedList {
      head_ptr: Option&lt;Box&lt;Node&gt;&gt;,
  }
  </code></pre>
  <p>Assume that the list is always sorted with respect to node values. I would like to write a (private) method that looks for a position where a given value should be if it is in the list (&quot;a position&quot; in this case is <code>&amp;mut Option&lt;Box&lt;Node&gt;&gt;</code>):</p>
  <pre class="lang-rust prettyprint-override"><code>impl List {
      fn find_mut(&amp;mut self, value: i64) -&gt; &amp;mut Option&lt;Box&lt;Node&gt;&gt; {
          let mut node_ptr = &amp;mut self.head_ptr;
          while let Some(node) = node_ptr {
              if node.value &gt;= value {
                  return node_ptr;
              }
              node_ptr = &amp;mut node.next_ptr;
          }
          node_ptr
      }
  }
  </code></pre>
  <p><a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=0052a4239d647e509905e84c400dc264" rel="nofollow noreferrer">Playground</a></p>
  <p>This doesn't compile:</p>
  <pre class="lang-none prettyprint-override"><code>error[E0499]: cannot borrow `*node_ptr` as mutable more than once at a time
    --&gt; src/lib.rs:15:24
     |
  11 |     fn find_mut(&amp;mut self, value: i64) -&gt; &amp;mut Option&lt;Box&lt;Node&gt;&gt; {
     |                 - let's call the lifetime of this reference `'1`
  12 |         let mut node_ptr = &amp;mut self.head_ptr;
  13 |         while let Some(node) = node_ptr {
     |                        ---- first mutable borrow occurs here
  14 |             if node.value &gt;= value {
  15 |                 return node_ptr;
     |                        ^^^^^^^^
     |                        |
     |                        second mutable borrow occurs here
     |                        returning this value requires that `node_ptr.0` is borrowed for `'1`
  </code></pre>
  <p>I am not quite sure why the borrow checker is unhappy, since the <code>node</code> variable can be considered no longer used once we do <code>return node_ptr</code>, so with non-lexical lifetimes this should work. I was able to make it compile with, arguably, less readable code:</p>
  <pre class="lang-rust prettyprint-override"><code>fn find_mut(&amp;mut self, value: i64) -&gt; &amp;mut Option&lt;Box&lt;Node&gt;&gt; {
      let mut node_ptr = &amp;mut self.head_ptr;
      while node_ptr.as_ref().map(|n| n.value &gt;= value).unwrap_or(false) {
          node_ptr = &amp;mut node_ptr.as_mut().unwrap().next_ptr;
      }
      node_ptr
  }
  </code></pre>
  <p>But why did NLL not help in the first version?</p>
  <p>Notice that this question is different from <a href="https://stackoverflow.com/questions/37986640/cannot-obtain-a-mutable-reference-when-iterating-a-recursive-structure-cannot-b">How do I keep a mutable reference to the last node while building a linked list?</a> since NLL actually did allow the code compile as-is in this question, while in my case it doesn't. It looks like the &quot;if&quot; in the loop body makes all the difference.</p>