blob: 4d1785c77a3de2ed233cef0abba29d45833670d2 [file] [log] [blame]
<!DOCTYPE HTML>
<html lang="en" class="light sidebar-visible" dir="ltr">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Region inference - Rust Compiler Development Guide</title>
<!-- Custom HTML head -->
<meta name="description" content="A guide to developing the Rust compiler (rustc)">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff">
<link rel="icon" href="../favicon.svg">
<link rel="shortcut icon" href="../favicon.png">
<link rel="stylesheet" href="../css/variables.css">
<link rel="stylesheet" href="../css/general.css">
<link rel="stylesheet" href="../css/chrome.css">
<link rel="stylesheet" href="../css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="../FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="../fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" id="highlight-css" href="../highlight.css">
<link rel="stylesheet" id="tomorrow-night-css" href="../tomorrow-night.css">
<link rel="stylesheet" id="ayu-highlight-css" href="../ayu-highlight.css">
<!-- Custom theme stylesheets -->
<!-- Provide site root and default themes to javascript -->
<script>
const path_to_root = "../";
const default_light_theme = "light";
const default_dark_theme = "navy";
</script>
<!-- Start loading toc.js asap -->
<script src="../toc.js"></script>
</head>
<body>
<div id="body-container">
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script>
try {
let theme = localStorage.getItem('mdbook-theme');
let sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script>
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
let theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
const html = document.documentElement;
html.classList.remove('light')
html.classList.add(theme);
html.classList.add("js");
</script>
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
<!-- Hide / unhide sidebar before it is displayed -->
<script>
let sidebar = null;
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
} else {
sidebar = 'hidden';
}
sidebar_toggle.checked = sidebar === 'visible';
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<!-- populated by js -->
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
<noscript>
<iframe class="sidebar-iframe-outer" src="../toc.html"></iframe>
</noscript>
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
<div class="sidebar-resize-indicator"></div>
</div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky">
<div class="left-buttons">
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</label>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Rust Compiler Development Guide</h1>
<div class="right-buttons">
<a href="../print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
<a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
<i id="git-repository-button" class="fa fa-github"></i>
</a>
<a href="https://github.com/rust-lang/rustc-dev-guide/edit/master/src/borrow_check/region_inference.md" title="Suggest an edit" aria-label="Suggest an edit">
<i id="git-edit-button" class="fa fa-edit"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script>
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="region-inference-nll"><a class="header" href="#region-inference-nll">Region inference (NLL)</a></h1>
<ul>
<li><a href="#universal-regions">Universal regions</a></li>
<li><a href="#region-variables">Region variables</a></li>
<li><a href="#constraints">Constraints</a></li>
<li><a href="#inference-overview">Inference Overview</a>
<ul>
<li><a href="#example">Example</a></li>
<li><a href="#some-details">Some details</a></li>
</ul>
</li>
</ul>
<p>The MIR-based region checking code is located in <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/index.html">the <code>rustc_mir::borrow_check</code>
module</a>.</p>
<p>The MIR-based region analysis consists of two major functions:</p>
<ul>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.replace_regions_in_mir.html"><code>replace_regions_in_mir</code></a>, invoked first, has two jobs:
<ul>
<li>First, it finds the set of regions that appear within the
signature of the function (e.g., <code>'a</code> in <code>fn foo&lt;'a&gt;(&amp;'a u32) { ... }</code>). These are called the "universal" or "free" regions – in
particular, they are the regions that <a href="../appendix/background.html#free-vs-bound">appear free</a> in the
function body.</li>
<li>Second, it replaces all the regions from the function body with
fresh inference variables. This is because (presently) those
regions are the results of lexical region inference and hence are
not of much interest. The intention is that – eventually – they
will be "erased regions" (i.e., no information at all), since we
won't be doing lexical region inference at all.</li>
</ul>
</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.compute_regions.html"><code>compute_regions</code></a>, invoked second: this is given as argument the
results of move analysis. It has the job of computing values for all
the inference variables that <code>replace_regions_in_mir</code> introduced.
<ul>
<li>To do that, it first runs the <a href="./type_check.html">MIR type checker</a>. This is
basically a normal type-checker but specialized to MIR, which is
much simpler than full Rust, of course. Running the MIR type
checker will however create various <a href="./region_inference/constraint_propagation.html">constraints</a> between region
variables, indicating their potential values and relationships to
one another.</li>
<li>After this, we perform <a href="./region_inference/constraint_propagation.html">constraint propagation</a> by creating a
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html"><code>RegionInferenceContext</code></a> and invoking its <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.solve"><code>solve</code></a>
method.</li>
<li>The <a href="https://rust-lang.github.io/rfcs/2094-nll.html">NLL RFC</a> also includes fairly thorough (and hopefully readable)
coverage.</li>
</ul>
</li>
</ul>
<h2 id="universal-regions"><a class="header" href="#universal-regions">Universal regions</a></h2>
<p>The <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/universal_regions/struct.UniversalRegions.html"><code>UniversalRegions</code></a> type represents a collection of <em>universal</em> regions
corresponding to some MIR <code>DefId</code>. It is constructed in
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.replace_regions_in_mir.html"><code>replace_regions_in_mir</code></a> when we replace all regions with fresh inference
variables. <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/universal_regions/struct.UniversalRegions.html"><code>UniversalRegions</code></a> contains indices for all the free regions in
the given MIR along with any relationships that are <em>known</em> to hold between
them (e.g. implied bounds, where clauses, etc.).</p>
<p>For example, given the MIR for the following function:</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>fn foo&lt;'a&gt;(x: &amp;'a u32) {
// ...
}
<span class="boring">}</span></code></pre></pre>
<p>we would create a universal region for <code>'a</code> and one for <code>'static</code>. There may
also be some complications for handling closures, but we will ignore those for
the moment.</p>
<p>TODO: write about <em>how</em> these regions are computed.</p>
<p><a id="region-variables"></a></p>
<h2 id="region-variables"><a class="header" href="#region-variables">Region variables</a></h2>
<p>The value of a region can be thought of as a <strong>set</strong>. This set contains all
points in the MIR where the region is valid along with any regions that are
outlived by this region (e.g. if <code>'a: 'b</code>, then <code>end('b)</code> is in the set for
<code>'a</code>); we call the domain of this set a <code>RegionElement</code>. In the code, the value
for all regions is maintained in <a href="https://github.com/rust-lang/rust/tree/master/compiler/rustc_borrowck/src/region_infer">the <code>rustc_borrowck::region_infer</code> module</a>.
For each region we maintain a set storing what elements are present in its value (to make this
efficient, we give each kind of element an index, the <code>RegionElementIndex</code>, and
use sparse bitsets).</p>
<p>The kinds of region elements are as follows:</p>
<ul>
<li>Each <strong><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/struct.Location.html"><code>location</code></a></strong> in the MIR control-flow graph: a location is just
the pair of a basic block and an index. This identifies the point
<strong>on entry</strong> to the statement with that index (or the terminator, if
the index is equal to <code>statements.len()</code>).</li>
<li>There is an element <code>end('a)</code> for each universal region <code>'a</code>,
corresponding to some portion of the caller's (or caller's caller,
etc) control-flow graph.</li>
<li>Similarly, there is an element denoted <code>end('static)</code> corresponding
to the remainder of program execution after this function returns.</li>
<li>There is an element <code>!1</code> for each placeholder region <code>!1</code>. This
corresponds (intuitively) to some unknown set of other elements –
for details on placeholders, see the section
<a href="region_inference/placeholders_and_universes.html">placeholders and universes</a>.</li>
</ul>
<h2 id="constraints"><a class="header" href="#constraints">Constraints</a></h2>
<p>Before we can infer the value of regions, we need to collect
constraints on the regions. The full set of constraints is described
in <a href="./region_inference/constraint_propagation.html">the section on constraint propagation</a>, but the two most
common sorts of constraints are:</p>
<ol>
<li>Outlives constraints. These are constraints that one region outlives another
(e.g. <code>'a: 'b</code>). Outlives constraints are generated by the <a href="./type_check.html">MIR type
checker</a>.</li>
<li>Liveness constraints. Each region needs to be live at points where it can be
used.</li>
</ol>
<h2 id="inference-overview"><a class="header" href="#inference-overview">Inference Overview</a></h2>
<p>So how do we compute the contents of a region? This process is called <em>region
inference</em>. The high-level idea is pretty simple, but there are some details we
need to take care of.</p>
<p>Here is the high-level idea: we start off each region with the MIR locations we
know must be in it from the liveness constraints. From there, we use all of the
outlives constraints computed from the type checker to <em>propagate</em> the
constraints: for each region <code>'a</code>, if <code>'a: 'b</code>, then we add all elements of
<code>'b</code> to <code>'a</code>, including <code>end('b)</code>. This all happens in
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.propagate_constraints"><code>propagate_constraints</code></a>.</p>
<p>Then, we will check for errors. We first check that type tests are satisfied by
calling <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.check_type_tests"><code>check_type_tests</code></a>. This checks constraints like <code>T: 'a</code>. Second, we
check that universal regions are not "too big". This is done by calling
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.check_universal_regions"><code>check_universal_regions</code></a>. This checks that for each region <code>'a</code> if <code>'a</code>
contains the element <code>end('b)</code>, then we must already know that <code>'a: 'b</code> holds
(e.g. from a where clause). If we don't already know this, that is an error...
well, almost. There is some special handling for closures that we will discuss
later.</p>
<h3 id="example"><a class="header" href="#example">Example</a></h3>
<p>Consider the following example:</p>
<pre><code class="language-rust ignore">fn foo&lt;'a, 'b&gt;(x: &amp;'a usize) -&gt; &amp;'b usize {
x
}</code></pre>
<p>Clearly, this should not compile because we don't know if <code>'a</code> outlives <code>'b</code>
(if it doesn't then the return value could be a dangling reference).</p>
<p>Let's back up a bit. We need to introduce some free inference variables (as is
done in <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.replace_regions_in_mir.html"><code>replace_regions_in_mir</code></a>). This example doesn't use the exact regions
produced, but it (hopefully) is enough to get the idea across.</p>
<pre><code class="language-rust ignore">fn foo&lt;'a, 'b&gt;(x: &amp;'a /* '#1 */ usize) -&gt; &amp;'b /* '#3 */ usize {
x // '#2, location L1
}</code></pre>
<p>Some notation: <code>'#1</code>, <code>'#3</code>, and <code>'#2</code> represent the universal regions for the
argument, return value, and the expression <code>x</code>, respectively. Additionally, I
will call the location of the expression <code>x</code> <code>L1</code>.</p>
<p>So now we can use the liveness constraints to get the following starting points:</p>
<div class="table-wrapper"><table><thead><tr><th>Region</th><th>Contents</th></tr></thead><tbody>
<tr><td>'#1</td><td></td></tr>
<tr><td>'#2</td><td><code>L1</code></td></tr>
<tr><td>'#3</td><td><code>L1</code></td></tr>
</tbody></table>
</div>
<p>Now we use the outlives constraints to expand each region. Specifically, we
know that <code>'#2: '#3</code> ...</p>
<div class="table-wrapper"><table><thead><tr><th>Region</th><th>Contents</th></tr></thead><tbody>
<tr><td>'#1</td><td><code>L1</code></td></tr>
<tr><td>'#2</td><td><code>L1, end('#3) // add contents of '#3 and end('#3)</code></td></tr>
<tr><td>'#3</td><td><code>L1</code></td></tr>
</tbody></table>
</div>
<p>... and <code>'#1: '#2</code>, so ...</p>
<div class="table-wrapper"><table><thead><tr><th>Region</th><th>Contents</th></tr></thead><tbody>
<tr><td>'#1</td><td><code>L1, end('#2), end('#3) // add contents of '#2 and end('#2)</code></td></tr>
<tr><td>'#2</td><td><code>L1, end('#3)</code></td></tr>
<tr><td>'#3</td><td><code>L1</code></td></tr>
</tbody></table>
</div>
<p>Now, we need to check that no regions were too big (we don't have any type
tests to check in this case). Notice that <code>'#1</code> now contains <code>end('#3)</code>, but
we have no <code>where</code> clause or implied bound to say that <code>'a: 'b</code>... that's an
error!</p>
<h3 id="some-details"><a class="header" href="#some-details">Some details</a></h3>
<p>The <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html"><code>RegionInferenceContext</code></a> type contains all of the information needed to
do inference, including the universal regions from <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.replace_regions_in_mir.html"><code>replace_regions_in_mir</code></a> and
the constraints computed for each region. It is constructed just after we
compute the liveness constraints.</p>
<p>Here are some of the fields of the struct:</p>
<ul>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.constraints"><code>constraints</code></a>: contains all the outlives constraints.</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.liveness_constraints"><code>liveness_constraints</code></a>: contains all the liveness constraints.</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.universal_regions"><code>universal_regions</code></a>: contains the <code>UniversalRegions</code> returned by
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/nll/fn.replace_regions_in_mir.html"><code>replace_regions_in_mir</code></a>.</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.universal_region_relations"><code>universal_region_relations</code></a>: contains relations known to be true about
universal regions. For example, if we have a where clause that <code>'a: 'b</code>, that
relation is assumed to be true while borrow checking the implementation (it
is checked at the caller), so <code>universal_region_relations</code> would contain <code>'a: 'b</code>.</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.type_tests"><code>type_tests</code></a>: contains some constraints on types that we must check after
inference (e.g. <code>T: 'a</code>).</li>
<li><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#structfield.closure_bounds_mapping"><code>closure_bounds_mapping</code></a>: used for propagating region constraints from
closures back out to the creator of the closure.</li>
</ul>
<p>TODO: should we discuss any of the others fields? What about the SCCs?</p>
<p>Ok, now that we have constructed a <code>RegionInferenceContext</code>, we can do
inference. This is done by calling the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.solve"><code>solve</code></a> method on the context. This
is where we call <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_borrowck/region_infer/struct.RegionInferenceContext.html#method.propagate_constraints"><code>propagate_constraints</code></a> and then check the resulting type
tests and universal regions, as discussed above.</p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="../borrow_check/drop_check.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="../borrow_check/region_inference/constraint_propagation.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="../borrow_check/drop_check.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="../borrow_check/region_inference/constraint_propagation.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script>
window.playground_copyable = true;
</script>
<script src="../elasticlunr.min.js"></script>
<script src="../mark.min.js"></script>
<script src="../searcher.js"></script>
<script src="../clipboard.min.js"></script>
<script src="../highlight.js"></script>
<script src="../book.js"></script>
<!-- Custom JS scripts -->
<script src="../mermaid.min.js"></script>
<script src="../mermaid-init.js"></script>
</div>
</body>
</html>