<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>src/librustc/infer/lexical_region_resolve/README.md - fork/rust @ 1.39.0</title>
<meta name="description" content="src/librustc/infer/lexical_region_resolve/README.md in fork/rust at 1.39.0.">
<meta property="og:title" content="src/librustc/infer/lexical_region_resolve/README.md - fork/rust @ 1.39.0">
<meta property="og:description" content="src/librustc/infer/lexical_region_resolve/README.md in fork/rust at 1.39.0.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="1.39.0" data-tip="4560ea788cb760f0a34127156c78e2552949f734">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>fork/rust</h1>
</div>
<pre class="clone">git clone https://git.julia.blue/fork/rust</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">bors</span><span class="commit-message" data-commit="4560ea788cb760f0a34127156c78e2552949f734">Auto merge of #66089 - Mark-Simulacrum:stable-next, r=Mark-Simulacrum</span><span class="snapshot-sha sha" data-commit="4560ea788cb760f0a34127156c78e2552949f734">4560ea788cb</span><time datetime="2019-11-04T15:43:19+00:00" title="2019-11-04 15:43:19 +0000">2019-11-04</time></p>
<header class="topbar"><details class="switcher"><summary>1.39.0</summary><div class="menu"><strong>branches</strong><a href="/fork/rust/ref/master/">master</a><strong>tags</strong><a class="current" href="/fork/rust/ref/1.39.0/">1.39.0</a><a href="/fork/rust/ref/1.40.0/">1.40.0</a><a href="/fork/rust/ref/1.41.0/">1.41.0</a><a href="/fork/rust/ref/1.41.1/">1.41.1</a><a href="/fork/rust/ref/1.42.0/">1.42.0</a><a href="/fork/rust/ref/1.43.0/">1.43.0</a><a href="/fork/rust/ref/1.43.1/">1.43.1</a><a href="/fork/rust/ref/1.44.0/">1.44.0</a><a class="all" href="/fork/rust/refs">all refs →</a></div></details><nav class="crumbs"><a href="/fork/rust/">rust</a> / <a href="/fork/rust/ref/1.39.0/tree/src/">src</a> / <a href="/fork/rust/ref/1.39.0/tree/src/librustc/">librustc</a> / <a href="/fork/rust/ref/1.39.0/tree/src/librustc/infer/">infer</a> / <a href="/fork/rust/ref/1.39.0/tree/src/librustc/infer/lexical_region_resolve/">lexical_region_resolve</a> / <span class="cur">README.md</span></nav>
<span class="view-stats"><span>10.6 KiB</span><span>268 lines</span></span><span class="actions"><a class="raw" href="/fork/rust/raw/7eb4da86ec081fb82b144431409186f0da1471f8/src/librustc/infer/lexical_region_resolve/README.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h1>Region inference</h1>
<blockquote>
<p>WARNING: This README is obsolete and will be removed soon! For
more info on how the current borrowck works, see the <a href="https://rust-lang.github.io/rustc-guide/borrow_check/region_inference.html">rustc guide</a>.</p>
<p>As of edition 2018, region inference is done using Non-lexical lifetimes,
which is described in the guide and <a href="https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md">this RFC</a>.</p>
</blockquote>
<h2>Terminology</h2>
<p>Note that we use the terms region and lifetime interchangeably.</p>
<h2>Introduction</h2>
<p>Region inference uses a somewhat more involved algorithm than type
inference. It is not the most efficient thing ever written though it
seems to work well enough in practice (famous last words).  The reason
that we use a different algorithm is because, unlike with types, it is
impractical to hand-annotate with regions (in some cases, there aren't
even the requisite syntactic forms).  So we have to get it right, and
it's worth spending more time on a more involved analysis.  Moreover,
regions are a simpler case than types: they don't have aggregate
structure, for example.</p>
<h2>The problem</h2>
<p>Basically our input is a directed graph where nodes can be divided
into two categories: region variables and concrete regions.  Each edge
<code>R -&gt; S</code> in the graph represents a constraint that the region <code>R</code> is a
subregion of the region <code>S</code>.</p>
<p>Region variable nodes can have arbitrary degree.  There is one region
variable node per region variable.</p>
<p>Each concrete region node is associated with some, well, concrete
region: e.g., a free lifetime, or the region for a particular scope.
Note that there may be more than one concrete region node for a
particular region value.  Moreover, because of how the graph is built,
we know that all concrete region nodes have either in-degree 1 or
out-degree 1.</p>
<p>Before resolution begins, we build up the constraints in a hashmap
that maps <code>Constraint</code> keys to spans.  During resolution, we construct
the actual <code>Graph</code> structure that we describe here.</p>
<h2>Computing the values for region variables</h2>
<p>The algorithm is a simple dataflow algorithm. Each region variable
begins as empty. We iterate over the constraints, and for each constraint
we grow the relevant region variable to be as big as it must be to meet all the
constraints. This means the region variables can grow to be <code>'static</code> if
necessary.</p>
<h2>Verification</h2>
<p>After all constraints are fully propoagated, we do a "verification"
step where we walk over the verify bounds and check that they are
satisfied. These bounds represent the "maximal" values that a region
variable can take on, basically.</p>
<h2>The Region Hierarchy</h2>
<h3>Without closures</h3>
<p>Let's first consider the region hierarchy without thinking about
closures, because they add a lot of complications. The region
hierarchy <em>basically</em> mirrors the lexical structure of the code.
There is a region for every piece of 'evaluation' that occurs, meaning
every expression, block, and pattern (patterns are considered to
"execute" by testing the value they are applied to and creating any
relevant bindings).  So, for example:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>x</a-v><a-p>:</a-p> <a-t>isize</a-t><a-p>,</a-p> <a-v>y</a-v><a-p>:</a-p> <a-t>isize</a-t><a-p>)</a-p> <a-p>{</a-p> <a-c>// -+</a-c>
<a-c>//  +------------+           //  |</a-c>
<a-c>//  |      +-----+           //  |</a-c>
<a-c>//  |  +-+ +-+ +-+           //  |</a-c>
<a-c>//  |  | | | | | |           //  |</a-c>
<a-c>//  v  v v v v v v           //  |</a-c>
    <a-k>let</a-k> z = x + y<a-p>;</a-p>           <a-c>//  |</a-c>
    ..<a-p>.</a-p>                      <a-c>//  |</a-c><a-pr>
</a-pr><a-p>}</a-p><a-pr>                            </a-pr><a-c>// -+</a-c><a-pr>

</a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>bar</a-f><a-p>()</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr> ..</a-pr><a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p></pre>
<p>In this example, there is a region for the fn body block as a whole,
and then a subregion for the declaration of the local variable.
Within that, there are sublifetimes for the assignment pattern and
also the expression <code>x + y</code>. The expression itself has sublifetimes
for evaluating <code>x</code> and <code>y</code>.</p>
<p>#s## Function calls</p>
<p>Function calls are a bit tricky. I will describe how we handle them
<em>now</em> and then a bit about how we can improve them (Issue #6268).</p>
<p>Consider a function call like <code>func(expr1, expr2)</code>, where <code>func</code>,
<code>arg1</code>, and <code>arg2</code> are all arbitrary expressions. Currently,
we construct a region hierarchy like:</p>
<pre><code>+----------------+
|                |
+--+ +---+  +---+|
v  v v   v  v   vv
func(expr1, expr2)
</code></pre>
<p>Here you can see that the call as a whole has a region and the
function plus arguments are subregions of that. As a side-effect of
this, we get a lot of spurious errors around nested calls, in
particular when combined with <code>&amp;mut</code> functions. For example, a call
like this one</p>
<pre class="language-rust"><a-v>self</a-v><a-p>.</a-p><a-f>foo</a-f><a-p>(</a-p><a-v>self</a-v><a-p>.</a-p><a-f>bar</a-f><a-p>())</a-p></pre>
<p>where both <code>foo</code> and <code>bar</code> are <code>&amp;mut self</code> functions will always yield
an error.</p>
<p>Here is a more involved example (which is safe) so we can see what's
going on:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>Foo</a-t> <a-p>{</a-p> <a-pr>f</a-pr><a-p>:</a-p> <a-t>usize</a-t><a-p>,</a-p> <a-pr>g</a-pr><a-p>:</a-p> <a-t>usize</a-t> <a-p>}</a-p>
<a-c>// ...</a-c>
<a-k>fn</a-k> <a-f>add</a-f><a-p>(</a-p><a-v>p</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>usize</a-t><a-p>,</a-p> <a-v>v</a-v><a-p>:</a-p> <a-t>usize</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-o>*</a-o>p += v<a-p>;</a-p>
<a-p>}</a-p>
<a-c>// ...</a-c>
<a-k>fn</a-k> <a-f>inc</a-f><a-p>(</a-p><a-v>p</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>usize</a-t><a-p>)</a-p> -&gt; <a-t>usize</a-t> <a-p>{</a-p>
    <a-o>*</a-o>p += <a-co>1</a-co><a-p>;</a-p> <a-o>*</a-o>p
<a-p>}</a-p>
<a-k>fn</a-k> <a-f>weird</a-f><a-p>()</a-p> <a-p>{</a-p>
    <a-k>let</a-k> <a-k>mut</a-k> x<a-p>:</a-p> <a-t>Box</a-t><a-p>&lt;</a-p><a-t>Foo</a-t><a-p>&gt;</a-p> = box <a-t>Foo</a-t> <a-p>{</a-p> <a-c>/* ... */</a-c> <a-p>};</a-p>
    <a-o>&#39;</a-o>a<a-p>:</a-p> <a-f>add</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-p>(</a-p><a-o>*</a-o>x<a-p>).</a-p><a-pr>f</a-pr><a-p>,</a-p>
            <a-o>&#39;</a-o>b<a-p>:</a-p> <a-f>inc</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-p>(</a-p><a-o>*</a-o>x<a-p>).</a-p><a-pr>f</a-pr><a-p>))</a-p> <a-c>// (..)</a-c>
<a-p>}</a-p></pre>
<p>The important part is the line marked <code>(..)</code> which contains a call to
<code>add()</code>. The first argument is a mutable borrow of the field <code>f</code>.  The
second argument also borrows the field <code>f</code>. Now, in the current borrow
checker, the first borrow is given the lifetime of the call to
<code>add()</code>, <code>'a</code>.  The second borrow is given the lifetime of <code>'b</code> of the
call to <code>inc()</code>. Because <code>'b</code> is considered to be a sublifetime of
<code>'a</code>, an error is reported since there are two co-existing mutable
borrows of the same data.</p>
<p>However, if we were to examine the lifetimes a bit more carefully, we
can see that this error is unnecessary. Let's examine the lifetimes
involved with <code>'a</code> in detail. We'll break apart all the steps involved
in a call expression:</p>
<pre class="language-rust"><a-o>&#39;</a-o>a<a-p>:</a-p> <a-p>{</a-p>
    <a-o>&#39;</a-o>a_arg1<a-p>:</a-p> <a-k>let</a-k> a_temp1<a-p>:</a-p> ... = add<a-p>;</a-p>
    <a-o>&#39;</a-o>a_arg2<a-p>:</a-p> <a-k>let</a-k> a_temp2<a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>usize</a-t> = <a-o>&amp;&#39;</a-o>a mut <a-p>(</a-p><a-o>*</a-o>x<a-p>).</a-p>f<a-p>;</a-p>
    <a-o>&#39;</a-o>a_arg3<a-p>:</a-p> let a_temp3<a-p>:</a-p> usize = <a-p>{</a-p>
        <a-k>let</a-k> b_temp1<a-p>:</a-p> ... = inc<a-p>;</a-p>
        <a-k>let</a-k> b_temp2<a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>b</a-l> = <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-k>mut</a-k> <a-p>(</a-p><a-o>*</a-o><a-t>x</a-t><a-p>).</a-p>f<a-p>;</a-p>
        <a-o>&#39;</a-o>b_call<a-p>:</a-p> <a-f>b_temp1</a-f><a-p>(</a-p>b_temp2<a-p>)</a-p>
    <a-p>};</a-p>
    <a-o>&#39;</a-o>a_call<a-p>:</a-p> <a-f>a_temp1</a-f><a-p>(</a-p>a_temp2<a-p>,</a-p> a_temp3<a-p>)</a-p> <a-c>// (**)</a-c>
<a-p>}</a-p></pre>
<p>Here we see that the lifetime <code>'a</code> includes a number of substatements.
In particular, there is this lifetime I've called <code>'a_call</code> that
corresponds to the <em>actual execution of the function <code>add()</code></em>, after
all arguments have been evaluated. There is a corresponding lifetime
<code>'b_call</code> for the execution of <code>inc()</code>. If we wanted to be precise
about it, the lifetime of the two borrows should be <code>'a_call</code> and
<code>'b_call</code> respectively, since the references that were created
will not be dereferenced except during the execution itself.</p>
<p>However, this model by itself is not sound. The reason is that
while the two references that are created will never be used
simultaneously, it is still true that the first reference is
<em>created</em> before the second argument is evaluated, and so even though
it will not be <em>dereferenced</em> during the evaluation of the second
argument, it can still be <em>invalidated</em> by that evaluation. Consider
this similar but unsound example:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>Foo</a-t> <a-p>{</a-p> <a-pr>f</a-pr><a-p>:</a-p> <a-t>usize</a-t><a-p>,</a-p> <a-pr>g</a-pr><a-p>:</a-p> <a-t>usize</a-t> <a-p>}</a-p>
<a-c>// ...</a-c>
<a-k>fn</a-k> <a-f>add</a-f><a-p>(</a-p><a-v>p</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>usize</a-t><a-p>,</a-p> <a-v>v</a-v><a-p>:</a-p> <a-t>usize</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-o>*</a-o>p += v<a-p>;</a-p>
<a-p>}</a-p>
<a-c>// ...</a-c>
<a-k>fn</a-k> <a-f>consume</a-f><a-p>(</a-p><a-v>x</a-v><a-p>:</a-p> <a-t>Box</a-t><a-p>&lt;</a-p><a-t>Foo</a-t><a-p>&gt;)</a-p> -&gt; <a-t>usize</a-t> <a-p>{</a-p>
    x<a-p>.</a-p><a-pr>f</a-pr> + x<a-p>.</a-p><a-pr>g</a-pr>
<a-p>}</a-p>
<a-k>fn</a-k> <a-f>weird</a-f><a-p>()</a-p> <a-p>{</a-p>
    <a-k>let</a-k> <a-k>mut</a-k> x<a-p>:</a-p> <a-t>Box</a-t><a-p>&lt;</a-p><a-t>Foo</a-t><a-p>&gt;</a-p> = box <a-t>Foo</a-t> <a-p>{</a-p> ..<a-p>.</a-p> <a-p>};</a-p>
    <a-o>&#39;</a-o>a<a-p>:</a-p> <a-f>add</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> <a-p>(</a-p><a-o>*</a-o>x<a-p>).</a-p><a-pr>f</a-pr><a-p>,</a-p> <a-f>consume</a-f><a-p>(</a-p>x<a-p>))</a-p> <a-c>// (..)</a-c>
<a-p>}</a-p></pre>
<p>In this case, the second argument to <code>add</code> actually consumes <code>x</code>, thus
invalidating the first argument.</p>
<p>So, for now, we exclude the <code>call</code> lifetimes from our model.
Eventually I would like to include them, but we will have to make the
borrow checker handle this situation correctly. In particular, if
there is a reference created whose lifetime does not enclose
the borrow expression, we must issue sufficient restrictions to ensure
that the pointee remains valid.</p>
<h3>Modeling closures</h3>
<p>Integrating closures properly into the model is a bit of
work-in-progress. In an ideal world, we would model closures as
closely as possible after their desugared equivalents. That is, a
closure type would be modeled as a struct, and the region hierarchy of
different closure bodies would be completely distinct from all other
fns. We are generally moving in that direction but there are
complications in terms of the implementation.</p>
<p>In practice what we currently do is somewhat different. The basis for
the current approach is the observation that the only time that
regions from distinct fn bodies interact with one another is through
an upvar or the type of a fn parameter (since closures live in the fn
body namespace, they can in fact have fn parameters whose types
include regions from the surrounding fn body). For these cases, there
are separate mechanisms which ensure that the regions that appear in
upvars/parameters outlive the dynamic extent of each call to the
closure:</p>
<ol>
<li>Types must outlive the region of any expression where they are used.
For a closure type <code>C</code> to outlive a region <code>'r</code>, that implies that the
types of all its upvars must outlive <code>'r</code>.</li>
<li>Parameters must outlive the region of any fn that they are passed to.</li>
</ol>
<p>Therefore, we can -- sort of -- assume that any region from an
enclosing fns is larger than any region from one of its enclosed
fn. And that is precisely what we do: when building the region
hierarchy, each region lives in its own distinct subtree, but if we
are asked to compute the <code>LUB(r1, r2)</code> of two regions, and those
regions are in disjoint subtrees, we compare the lexical nesting of
the two regions.</p>
<p><em>Ideas for improving the situation:</em> (FIXME #3696) The correctness
argument here is subtle and a bit hand-wavy. The ideal, as stated
earlier, would be to model things in such a way that it corresponds
more closely to the desugared code. The best approach for doing this
is a bit unclear: it may in fact be possible to <em>actually</em> desugar
before we start, but I don't think so. The main option that I've been
thinking through is imposing a "view shift" as we enter the fn body,
so that regions appearing in the types of fn parameters and upvars are
translated from being regions in the outer fn into free region
parameters, just as they would be if we applied the desugaring. The
challenge here is that type inference may not have fully run, so the
types may not be fully known: we could probably do this translation
lazilly, as type variables are instantiated. We would also have to
apply a kind of inverse translation to the return value. This would be
a good idea anyway, as right now it is possible for free regions
instantiated within the closure to leak into the parent: this
currently leads to type errors, since those regions cannot outlive any
expressions within the parent hierarchy. Much like the current
handling of closures, there are no known cases where this leads to a
type-checking accepting incorrect code (though it sometimes rejects
what might be considered correct code; see rust-lang/rust#22557), but
it still doesn't feel like the right approach.</p>
</section><div class="code-panel"><pre class="code src" data-hl="src/librustc/infer/lexical_region_resolve/README.md"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"># Region inference</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text">&gt; WARNING: This README is obsolete and will be removed soon! For</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text">&gt; more info on how the current borrowck works, see the [rustc guide].</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text">&gt;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text">&gt; As of edition 2018, region inference is done using Non-lexical lifetimes,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text">&gt; which is described in the guide and [this RFC].</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text">[rustc guide]: https://rust-lang.github.io/rustc-guide/borrow_check/region_inference.html</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text">[this RFC]: https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text">## Terminology</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text">Note that we use the terms region and lifetime interchangeably.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text">## Introduction</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text">Region inference uses a somewhat more involved algorithm than type</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text">inference. It is not the most efficient thing ever written though it</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text">seems to work well enough in practice (famous last words).  The reason</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text">that we use a different algorithm is because, unlike with types, it is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text">impractical to hand-annotate with regions (in some cases, there aren't</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text">even the requisite syntactic forms).  So we have to get it right, and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text">it's worth spending more time on a more involved analysis.  Moreover,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text">regions are a simpler case than types: they don't have aggregate</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text">structure, for example.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text">## The problem</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text">Basically our input is a directed graph where nodes can be divided</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text">into two categories: region variables and concrete regions.  Each edge</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text">`R -&gt; S` in the graph represents a constraint that the region `R` is a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text">subregion of the region `S`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text">Region variable nodes can have arbitrary degree.  There is one region</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text">variable node per region variable.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L37" href="#L37">37</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L38" href="#L38">38</a><span class="code-text">Each concrete region node is associated with some, well, concrete</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text">region: e.g., a free lifetime, or the region for a particular scope.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text">Note that there may be more than one concrete region node for a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text">particular region value.  Moreover, because of how the graph is built,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text">we know that all concrete region nodes have either in-degree 1 or</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text">out-degree 1.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text">Before resolution begins, we build up the constraints in a hashmap</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text">that maps `Constraint` keys to spans.  During resolution, we construct</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text">the actual `Graph` structure that we describe here.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text">## Computing the values for region variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text">The algorithm is a simple dataflow algorithm. Each region variable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text">begins as empty. We iterate over the constraints, and for each constraint</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text">we grow the relevant region variable to be as big as it must be to meet all the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text">constraints. This means the region variables can grow to be `'static` if</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text">necessary.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L56" href="#L56">56</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L57" href="#L57">57</a><span class="code-text">## Verification</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text">After all constraints are fully propoagated, we do a &quot;verification&quot;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text">step where we walk over the verify bounds and check that they are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text">satisfied. These bounds represent the &quot;maximal&quot; values that a region</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text">variable can take on, basically.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L63" href="#L63">63</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L64" href="#L64">64</a><span class="code-text">## The Region Hierarchy</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L65" href="#L65">65</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L66" href="#L66">66</a><span class="code-text">### Without closures</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L67" href="#L67">67</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L68" href="#L68">68</a><span class="code-text">Let's first consider the region hierarchy without thinking about</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L69" href="#L69">69</a><span class="code-text">closures, because they add a lot of complications. The region</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L70" href="#L70">70</a><span class="code-text">hierarchy *basically* mirrors the lexical structure of the code.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L71" href="#L71">71</a><span class="code-text">There is a region for every piece of 'evaluation' that occurs, meaning</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L72" href="#L72">72</a><span class="code-text">every expression, block, and pattern (patterns are considered to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L73" href="#L73">73</a><span class="code-text">&quot;execute&quot; by testing the value they are applied to and creating any</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L74" href="#L74">74</a><span class="code-text">relevant bindings).  So, for example:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L75" href="#L75">75</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L76" href="#L76">76</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L77" href="#L77">77</a><span class="code-text">fn foo(x: isize, y: isize) { // -+</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L78" href="#L78">78</a><span class="code-text">//  +------------+           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L79" href="#L79">79</a><span class="code-text">//  |      +-----+           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L80" href="#L80">80</a><span class="code-text">//  |  +-+ +-+ +-+           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L81" href="#L81">81</a><span class="code-text">//  |  | | | | | |           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L82" href="#L82">82</a><span class="code-text">//  v  v v v v v v           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L83" href="#L83">83</a><span class="code-text">    let z = x + y;           //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L84" href="#L84">84</a><span class="code-text">    ...                      //  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L85" href="#L85">85</a><span class="code-text">}                            // -+</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L86" href="#L86">86</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L87" href="#L87">87</a><span class="code-text">fn bar() { ... }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L88" href="#L88">88</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L89" href="#L89">89</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L90" href="#L90">90</a><span class="code-text">In this example, there is a region for the fn body block as a whole,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L91" href="#L91">91</a><span class="code-text">and then a subregion for the declaration of the local variable.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L92" href="#L92">92</a><span class="code-text">Within that, there are sublifetimes for the assignment pattern and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L93" href="#L93">93</a><span class="code-text">also the expression `x + y`. The expression itself has sublifetimes</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L94" href="#L94">94</a><span class="code-text">for evaluating `x` and `y`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L95" href="#L95">95</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L96" href="#L96">96</a><span class="code-text">#s## Function calls</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L97" href="#L97">97</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L98" href="#L98">98</a><span class="code-text">Function calls are a bit tricky. I will describe how we handle them</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L99" href="#L99">99</a><span class="code-text">*now* and then a bit about how we can improve them (Issue #6268).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L100" href="#L100">100</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L101" href="#L101">101</a><span class="code-text">Consider a function call like `func(expr1, expr2)`, where `func`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L102" href="#L102">102</a><span class="code-text">`arg1`, and `arg2` are all arbitrary expressions. Currently,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L103" href="#L103">103</a><span class="code-text">we construct a region hierarchy like:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L104" href="#L104">104</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L105" href="#L105">105</a><span class="code-text">    +----------------+</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L106" href="#L106">106</a><span class="code-text">    |                |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L107" href="#L107">107</a><span class="code-text">    +--+ +---+  +---+|</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L108" href="#L108">108</a><span class="code-text">    v  v v   v  v   vv</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L109" href="#L109">109</a><span class="code-text">    func(expr1, expr2)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L110" href="#L110">110</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L111" href="#L111">111</a><span class="code-text">Here you can see that the call as a whole has a region and the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L112" href="#L112">112</a><span class="code-text">function plus arguments are subregions of that. As a side-effect of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L113" href="#L113">113</a><span class="code-text">this, we get a lot of spurious errors around nested calls, in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L114" href="#L114">114</a><span class="code-text">particular when combined with `&amp;mut` functions. For example, a call</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L115" href="#L115">115</a><span class="code-text">like this one</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L116" href="#L116">116</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L117" href="#L117">117</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L118" href="#L118">118</a><span class="code-text">self.foo(self.bar())</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L119" href="#L119">119</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L120" href="#L120">120</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L121" href="#L121">121</a><span class="code-text">where both `foo` and `bar` are `&amp;mut self` functions will always yield</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L122" href="#L122">122</a><span class="code-text">an error.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L123" href="#L123">123</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L124" href="#L124">124</a><span class="code-text">Here is a more involved example (which is safe) so we can see what's</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L125" href="#L125">125</a><span class="code-text">going on:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L126" href="#L126">126</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L127" href="#L127">127</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L128" href="#L128">128</a><span class="code-text">struct Foo { f: usize, g: usize }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L129" href="#L129">129</a><span class="code-text">// ...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L130" href="#L130">130</a><span class="code-text">fn add(p: &amp;mut usize, v: usize) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L131" href="#L131">131</a><span class="code-text">    *p += v;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L132" href="#L132">132</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L133" href="#L133">133</a><span class="code-text">// ...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L134" href="#L134">134</a><span class="code-text">fn inc(p: &amp;mut usize) -&gt; usize {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L135" href="#L135">135</a><span class="code-text">    *p += 1; *p</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L136" href="#L136">136</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L137" href="#L137">137</a><span class="code-text">fn weird() {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L138" href="#L138">138</a><span class="code-text">    let mut x: Box&lt;Foo&gt; = box Foo { /* ... */ };</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L139" href="#L139">139</a><span class="code-text">    'a: add(&amp;mut (*x).f,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L140" href="#L140">140</a><span class="code-text">            'b: inc(&amp;mut (*x).f)) // (..)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L141" href="#L141">141</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L142" href="#L142">142</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L143" href="#L143">143</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L144" href="#L144">144</a><span class="code-text">The important part is the line marked `(..)` which contains a call to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L145" href="#L145">145</a><span class="code-text">`add()`. The first argument is a mutable borrow of the field `f`.  The</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L146" href="#L146">146</a><span class="code-text">second argument also borrows the field `f`. Now, in the current borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L147" href="#L147">147</a><span class="code-text">checker, the first borrow is given the lifetime of the call to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L148" href="#L148">148</a><span class="code-text">`add()`, `'a`.  The second borrow is given the lifetime of `'b` of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L149" href="#L149">149</a><span class="code-text">call to `inc()`. Because `'b` is considered to be a sublifetime of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L150" href="#L150">150</a><span class="code-text">`'a`, an error is reported since there are two co-existing mutable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L151" href="#L151">151</a><span class="code-text">borrows of the same data.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L152" href="#L152">152</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L153" href="#L153">153</a><span class="code-text">However, if we were to examine the lifetimes a bit more carefully, we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L154" href="#L154">154</a><span class="code-text">can see that this error is unnecessary. Let's examine the lifetimes</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L155" href="#L155">155</a><span class="code-text">involved with `'a` in detail. We'll break apart all the steps involved</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L156" href="#L156">156</a><span class="code-text">in a call expression:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L157" href="#L157">157</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L158" href="#L158">158</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L159" href="#L159">159</a><span class="code-text">'a: {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L160" href="#L160">160</a><span class="code-text">    'a_arg1: let a_temp1: ... = add;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L161" href="#L161">161</a><span class="code-text">    'a_arg2: let a_temp2: &amp;'a mut usize = &amp;'a mut (*x).f;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L162" href="#L162">162</a><span class="code-text">    'a_arg3: let a_temp3: usize = {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L163" href="#L163">163</a><span class="code-text">        let b_temp1: ... = inc;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L164" href="#L164">164</a><span class="code-text">        let b_temp2: &amp;'b = &amp;'b mut (*x).f;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L165" href="#L165">165</a><span class="code-text">        'b_call: b_temp1(b_temp2)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L166" href="#L166">166</a><span class="code-text">    };</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L167" href="#L167">167</a><span class="code-text">    'a_call: a_temp1(a_temp2, a_temp3) // (**)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L168" href="#L168">168</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L169" href="#L169">169</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L170" href="#L170">170</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L171" href="#L171">171</a><span class="code-text">Here we see that the lifetime `'a` includes a number of substatements.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L172" href="#L172">172</a><span class="code-text">In particular, there is this lifetime I've called `'a_call` that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L173" href="#L173">173</a><span class="code-text">corresponds to the *actual execution of the function `add()`*, after</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L174" href="#L174">174</a><span class="code-text">all arguments have been evaluated. There is a corresponding lifetime</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L175" href="#L175">175</a><span class="code-text">`'b_call` for the execution of `inc()`. If we wanted to be precise</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L176" href="#L176">176</a><span class="code-text">about it, the lifetime of the two borrows should be `'a_call` and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L177" href="#L177">177</a><span class="code-text">`'b_call` respectively, since the references that were created</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L178" href="#L178">178</a><span class="code-text">will not be dereferenced except during the execution itself.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L179" href="#L179">179</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L180" href="#L180">180</a><span class="code-text">However, this model by itself is not sound. The reason is that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L181" href="#L181">181</a><span class="code-text">while the two references that are created will never be used</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L182" href="#L182">182</a><span class="code-text">simultaneously, it is still true that the first reference is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L183" href="#L183">183</a><span class="code-text">*created* before the second argument is evaluated, and so even though</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L184" href="#L184">184</a><span class="code-text">it will not be *dereferenced* during the evaluation of the second</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L185" href="#L185">185</a><span class="code-text">argument, it can still be *invalidated* by that evaluation. Consider</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L186" href="#L186">186</a><span class="code-text">this similar but unsound example:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L187" href="#L187">187</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L188" href="#L188">188</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L189" href="#L189">189</a><span class="code-text">struct Foo { f: usize, g: usize }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L190" href="#L190">190</a><span class="code-text">// ...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L191" href="#L191">191</a><span class="code-text">fn add(p: &amp;mut usize, v: usize) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L192" href="#L192">192</a><span class="code-text">    *p += v;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L193" href="#L193">193</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L194" href="#L194">194</a><span class="code-text">// ...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L195" href="#L195">195</a><span class="code-text">fn consume(x: Box&lt;Foo&gt;) -&gt; usize {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L196" href="#L196">196</a><span class="code-text">    x.f + x.g</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L197" href="#L197">197</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L198" href="#L198">198</a><span class="code-text">fn weird() {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L199" href="#L199">199</a><span class="code-text">    let mut x: Box&lt;Foo&gt; = box Foo { ... };</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L200" href="#L200">200</a><span class="code-text">    'a: add(&amp;mut (*x).f, consume(x)) // (..)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L201" href="#L201">201</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L202" href="#L202">202</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L203" href="#L203">203</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L204" href="#L204">204</a><span class="code-text">In this case, the second argument to `add` actually consumes `x`, thus</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L205" href="#L205">205</a><span class="code-text">invalidating the first argument.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L206" href="#L206">206</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L207" href="#L207">207</a><span class="code-text">So, for now, we exclude the `call` lifetimes from our model.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L208" href="#L208">208</a><span class="code-text">Eventually I would like to include them, but we will have to make the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L209" href="#L209">209</a><span class="code-text">borrow checker handle this situation correctly. In particular, if</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L210" href="#L210">210</a><span class="code-text">there is a reference created whose lifetime does not enclose</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L211" href="#L211">211</a><span class="code-text">the borrow expression, we must issue sufficient restrictions to ensure</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L212" href="#L212">212</a><span class="code-text">that the pointee remains valid.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L213" href="#L213">213</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L214" href="#L214">214</a><span class="code-text">### Modeling closures</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L215" href="#L215">215</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L216" href="#L216">216</a><span class="code-text">Integrating closures properly into the model is a bit of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L217" href="#L217">217</a><span class="code-text">work-in-progress. In an ideal world, we would model closures as</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L218" href="#L218">218</a><span class="code-text">closely as possible after their desugared equivalents. That is, a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L219" href="#L219">219</a><span class="code-text">closure type would be modeled as a struct, and the region hierarchy of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L220" href="#L220">220</a><span class="code-text">different closure bodies would be completely distinct from all other</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L221" href="#L221">221</a><span class="code-text">fns. We are generally moving in that direction but there are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L222" href="#L222">222</a><span class="code-text">complications in terms of the implementation.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L223" href="#L223">223</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L224" href="#L224">224</a><span class="code-text">In practice what we currently do is somewhat different. The basis for</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L225" href="#L225">225</a><span class="code-text">the current approach is the observation that the only time that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L226" href="#L226">226</a><span class="code-text">regions from distinct fn bodies interact with one another is through</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L227" href="#L227">227</a><span class="code-text">an upvar or the type of a fn parameter (since closures live in the fn</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L228" href="#L228">228</a><span class="code-text">body namespace, they can in fact have fn parameters whose types</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L229" href="#L229">229</a><span class="code-text">include regions from the surrounding fn body). For these cases, there</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L230" href="#L230">230</a><span class="code-text">are separate mechanisms which ensure that the regions that appear in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L231" href="#L231">231</a><span class="code-text">upvars/parameters outlive the dynamic extent of each call to the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L232" href="#L232">232</a><span class="code-text">closure:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L233" href="#L233">233</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L234" href="#L234">234</a><span class="code-text">1. Types must outlive the region of any expression where they are used.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L235" href="#L235">235</a><span class="code-text">   For a closure type `C` to outlive a region `'r`, that implies that the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L236" href="#L236">236</a><span class="code-text">   types of all its upvars must outlive `'r`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L237" href="#L237">237</a><span class="code-text">2. Parameters must outlive the region of any fn that they are passed to.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L238" href="#L238">238</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L239" href="#L239">239</a><span class="code-text">Therefore, we can -- sort of -- assume that any region from an</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L240" href="#L240">240</a><span class="code-text">enclosing fns is larger than any region from one of its enclosed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L241" href="#L241">241</a><span class="code-text">fn. And that is precisely what we do: when building the region</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L242" href="#L242">242</a><span class="code-text">hierarchy, each region lives in its own distinct subtree, but if we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L243" href="#L243">243</a><span class="code-text">are asked to compute the `LUB(r1, r2)` of two regions, and those</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L244" href="#L244">244</a><span class="code-text">regions are in disjoint subtrees, we compare the lexical nesting of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L245" href="#L245">245</a><span class="code-text">the two regions.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L246" href="#L246">246</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L247" href="#L247">247</a><span class="code-text">*Ideas for improving the situation:* (FIXME #3696) The correctness</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L248" href="#L248">248</a><span class="code-text">argument here is subtle and a bit hand-wavy. The ideal, as stated</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L249" href="#L249">249</a><span class="code-text">earlier, would be to model things in such a way that it corresponds</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L250" href="#L250">250</a><span class="code-text">more closely to the desugared code. The best approach for doing this</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L251" href="#L251">251</a><span class="code-text">is a bit unclear: it may in fact be possible to *actually* desugar</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L252" href="#L252">252</a><span class="code-text">before we start, but I don't think so. The main option that I've been</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L253" href="#L253">253</a><span class="code-text">thinking through is imposing a &quot;view shift&quot; as we enter the fn body,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L254" href="#L254">254</a><span class="code-text">so that regions appearing in the types of fn parameters and upvars are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L255" href="#L255">255</a><span class="code-text">translated from being regions in the outer fn into free region</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L256" href="#L256">256</a><span class="code-text">parameters, just as they would be if we applied the desugaring. The</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L257" href="#L257">257</a><span class="code-text">challenge here is that type inference may not have fully run, so the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L258" href="#L258">258</a><span class="code-text">types may not be fully known: we could probably do this translation</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L259" href="#L259">259</a><span class="code-text">lazilly, as type variables are instantiated. We would also have to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L260" href="#L260">260</a><span class="code-text">apply a kind of inverse translation to the return value. This would be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L261" href="#L261">261</a><span class="code-text">a good idea anyway, as right now it is possible for free regions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L262" href="#L262">262</a><span class="code-text">instantiated within the closure to leak into the parent: this</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L263" href="#L263">263</a><span class="code-text">currently leads to type errors, since those regions cannot outlive any</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L264" href="#L264">264</a><span class="code-text">expressions within the parent hierarchy. Much like the current</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L265" href="#L265">265</a><span class="code-text">handling of closures, there are no known cases where this leads to a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L266" href="#L266">266</a><span class="code-text">type-checking accepting incorrect code (though it sometimes rejects</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L267" href="#L267">267</a><span class="code-text">what might be considered correct code; see rust-lang/rust#22557), but</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L268" href="#L268">268</a><span class="code-text">it still doesn't feel like the right approach.</span></span></pre></div></div>
</main>
</body>
</html>
