<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>src/librustc_ast_borrowck/borrowck/README.md - fork/rust @ 1.39.0</title>
<meta name="description" content="src/librustc_ast_borrowck/borrowck/README.md in fork/rust at 1.39.0.">
<meta property="og:title" content="src/librustc_ast_borrowck/borrowck/README.md - fork/rust @ 1.39.0">
<meta property="og:description" content="src/librustc_ast_borrowck/borrowck/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_ast_borrowck/">librustc_ast_borrowck</a> / <a href="/fork/rust/ref/1.39.0/tree/src/librustc_ast_borrowck/borrowck/">borrowck</a> / <span class="cur">README.md</span></nav>
<span class="view-stats"><span>44.5 KiB</span><span>1167 lines</span></span><span class="actions"><a class="raw" href="/fork/rust/raw/3f2175921d48c45a24f22a4a3055d8577956b214/src/librustc_ast_borrowck/borrowck/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"><p>% The Borrow Checker</p>
<blockquote>
<p>WARNING: This README is more or less obsolete, and will be removed
soon! The new system is described in the <a href="https://rust-lang.github.io/rustc-guide/borrow_check.html">rustc guide</a>.</p>
</blockquote>
<p>This pass has the job of enforcing memory safety. This is a subtle
topic. This docs aim to explain both the practice and the theory
behind the borrow checker. They start with a high-level overview of
how it works, and then proceed to dive into the theoretical
background. Finally, they go into detail on some of the more subtle
aspects.</p>
<h1>Table of contents</h1>
<p>These docs are long. Search for the section you are interested in.</p>
<ul>
<li>Overview</li>
<li>Formal model</li>
<li>Borrowing and loans</li>
<li>Moves and initialization</li>
<li>Drop flags and structural fragments</li>
<li>Future work</li>
</ul>
<h1>Overview</h1>
<p>The borrow checker checks one function at a time. It operates in two
passes. The first pass, called <code>gather_loans</code>, walks over the function
and identifies all of the places where borrows (e.g., <code>&amp;</code> expressions
and <code>ref</code> bindings) and moves (copies or captures of a linear value)
occur. It also tracks initialization sites. For each borrow and move,
it checks various basic safety conditions at this time (for example,
that the lifetime of the borrow doesn't exceed the lifetime of the
value being borrowed, or that there is no move out of an <code>&amp;T</code>
referent).</p>
<p>It then uses the dataflow module to propagate which of those borrows
may be in scope at each point in the procedure. A loan is considered
to come into scope at the expression that caused it and to go out of
scope when the lifetime of the resulting reference expires.</p>
<p>Once the in-scope loans are known for each point in the program, the
borrow checker walks the IR again in a second pass called
<code>check_loans</code>. This pass examines each statement and makes sure that
it is safe with respect to the in-scope loans.</p>
<h1>Formal model</h1>
<p>Throughout the docs we'll consider a simple subset of Rust in which
you can only borrow from places, defined like so:</p>
<pre>P = x | P.f | *P
</pre>
<p>Here <code>x</code> represents some variable, <code>P.f</code> is a field reference,
and <code>*P</code> is a pointer dereference. There is no auto-deref or other
niceties. This means that if you have a type like:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>S</a-t> <a-p>{</a-p> <a-pr>f</a-pr><a-p>:</a-p> <a-t>i32</a-t> <a-p>}</a-p></pre>
<p>and a variable <code>a: Box&lt;S&gt;</code>, then the rust expression <code>a.f</code> would correspond
to an <code>P</code> of <code>(*a).f</code>.</p>
<p>Here is the formal grammar for the types we'll consider:</p>
<pre>TY = i32 | bool | S&lt;'LT...&gt; | Box&lt;TY&gt; | &amp; 'LT MQ TY
MQ = mut | imm
</pre>
<p>Most of these types should be pretty self explanatory. Here <code>S</code> is a
struct name and we assume structs are declared like so:</p>
<pre>SD = struct S&lt;'LT...&gt; { (f: TY)... }
</pre>
<h1>Borrowing and loans</h1>
<h2>An intuitive explanation</h2>
<h3>Issuing loans</h3>
<p>Now, imagine we had a program like this:</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>i32</a-t><a-p>,</a-p> <a-pr>g</a-pr><a-p>:</a-p> <a-t>i32</a-t> <a-p>}</a-p>
..<a-p>.</a-p>
<a-o>&#39;</a-o>a<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> = ..<a-p>.</a-p><a-pr>;</a-pr><a-pr>
    </a-pr><a-k>let</a-k><a-pr> y = </a-pr><a-o>&amp;</a-o><a-k>mut</a-k><a-pr> </a-pr><a-p>(</a-p><a-o>*</a-o><a-pr>x</a-pr><a-p>).</a-p><a-pr>f</a-pr><a-p>;</a-p><a-pr>
    x = ..</a-pr><a-p>.;</a-p><a-pr>
</a-pr><a-p>}</a-p></pre>
<p>This is of course dangerous because mutating <code>x</code> will free the old
value and hence invalidate <code>y</code>. The borrow checker aims to prevent
this sort of thing.</p>
<h4>Loans and restrictions</h4>
<p>The way the borrow checker works is that it analyzes each borrow
expression (in our simple model, that's stuff like <code>&amp;P</code>, though in
real life there are a few other cases to consider). For each borrow
expression, it computes a <code>Loan</code>, which is a data structure that
records (1) the value being borrowed, (2) the mutability and scope of
the borrow, and (3) a set of restrictions. In the code, <code>Loan</code> is a
struct defined in <code>middle::borrowck</code>. Formally, we define <code>LOAN</code> as
follows:</p>
<pre>LOAN = (P, LT, MQ, RESTRICTION*)
RESTRICTION = (P, ACTION*)
ACTION = MUTATE | CLAIM | FREEZE
</pre>
<p>Here the <code>LOAN</code> tuple defines the place <code>P</code> being borrowed; the
lifetime <code>LT</code> of that borrow; the mutability <code>MQ</code> of the borrow; and a
list of restrictions. The restrictions indicate actions which, if
taken, could invalidate the loan and lead to type safety violations.</p>
<p>Each <code>RESTRICTION</code> is a pair of a restrictive place <code>P</code> (which will
either be the path that was borrowed or some prefix of the path that
was borrowed) and a set of restricted actions.  There are three kinds
of actions that may be restricted for the path <code>P</code>:</p>
<ul>
<li><code>MUTATE</code> means that <code>P</code> cannot be assigned to;</li>
<li><code>CLAIM</code> means that the <code>P</code> cannot be borrowed mutably;</li>
<li><code>FREEZE</code> means that the <code>P</code> cannot be borrowed immutably;</li>
</ul>
<p>Finally, it is never possible to move from a place that appears in a
restriction. This implies that the "empty restriction" <code>(P, [])</code>,
which contains an empty set of actions, still has a purpose---it
prevents moves from <code>P</code>. I chose not to make <code>MOVE</code> a fourth kind of
action because that would imply that sometimes moves are permitted
from restricted values, which is not the case.</p>
<h4>Example</h4>
<p>To give you a better feeling for what kind of restrictions derived
from a loan, let's look at the loan <code>L</code> that would be issued as a
result of the borrow <code>&amp;mut (*x).f</code> in the example above:</p>
<pre>L = ((*x).f, 'a, mut, RS) where
    RS = [((*x).f, [MUTATE, CLAIM, FREEZE]),
          (*x, [MUTATE, CLAIM, FREEZE]),
          (x, [MUTATE, CLAIM, FREEZE])]
</pre>
<p>The loan states that the expression <code>(*x).f</code> has been loaned as
mutable for the lifetime <code>'a</code>. Because the loan is mutable, that means
that the value <code>(*x).f</code> may be mutated via the newly created reference
(and <em>only</em> via that pointer). This is reflected in the
restrictions <code>RS</code> that accompany the loan.</p>
<p>The first restriction <code>((*x).f, [MUTATE, CLAIM, FREEZE])</code> states that
the lender may not mutate, freeze, nor alias <code>(*x).f</code>. Mutation is
illegal because <code>(*x).f</code> is only supposed to be mutated via the new
reference, not by mutating the original path <code>(*x).f</code>. Freezing is
illegal because the path now has an <code>&amp;mut</code> alias; so even if we the
lender were to consider <code>(*x).f</code> to be immutable, it might be mutated
via this alias. They will be enforced for the lifetime <code>'a</code> of the
loan. After the loan expires, the restrictions no longer apply.</p>
<p>The second restriction on <code>*x</code> is interesting because it does not
apply to the path that was lent (<code>(*x).f</code>) but rather to a prefix of
the borrowed path. This is due to the rules of inherited mutability:
if the user were to assign to (or freeze) <code>*x</code>, they would indirectly
overwrite (or freeze) <code>(*x).f</code>, and thus invalidate the reference
that was created. In general it holds that when a path is
lent, restrictions are issued for all the owning prefixes of that
path. In this case, the path <code>*x</code> owns the path <code>(*x).f</code> and,
because <code>x</code> has ownership, the path <code>x</code> owns the path <code>*x</code>.
Therefore, borrowing <code>(*x).f</code> yields restrictions on both
<code>*x</code> and <code>x</code>.</p>
<h3>Checking for illegal assignments, moves, and reborrows</h3>
<p>Once we have computed the loans introduced by each borrow, the borrow
checker uses a data flow propagation to compute the full set of loans
in scope at each expression and then uses that set to decide whether
that expression is legal.  Remember that the scope of loan is defined
by its lifetime LT.  We sometimes say that a loan which is in-scope at
a particular point is an "outstanding loan", and the set of
restrictions included in those loans as the "outstanding
restrictions".</p>
<p>The kinds of expressions which in-scope loans can render illegal are:</p>
<ul>
<li><em>assignments</em> (<code>lv = v</code>): illegal if there is an in-scope restriction
against mutating <code>lv</code>;</li>
<li><em>moves</em>: illegal if there is any in-scope restriction on <code>lv</code> at all;</li>
<li><em>mutable borrows</em> (<code>&amp;mut lv</code>): illegal there is an in-scope restriction
against claiming <code>lv</code>;</li>
<li><em>immutable borrows</em> (<code>&amp;lv</code>): illegal there is an in-scope restriction
against freezing <code>lv</code>.</li>
</ul>
<h2>Formal rules</h2>
<p>Now that we hopefully have some kind of intuitive feeling for how the
borrow checker works, let's look a bit more closely now at the precise
conditions that it uses.</p>
<p>I will present the rules in a modified form of standard inference
rules, which looks as follows:</p>
<pre>PREDICATE(X, Y, Z)                  // Rule-Name
  Condition 1
  Condition 2
  Condition 3
</pre>
<p>The initial line states the predicate that is to be satisfied.  The
indented lines indicate the conditions that must be met for the
predicate to be satisfied. The right-justified comment states the name
of this rule: there are comments in the borrowck source referencing
these names, so that you can cross reference to find the actual code
that corresponds to the formal rule.</p>
<h3>Invariants</h3>
<p>I want to collect, at a high-level, the invariants the borrow checker
maintains. I will give them names and refer to them throughout the
text. Together these invariants are crucial for the overall soundness
of the system.</p>
<p><strong>Mutability requires uniqueness.</strong> To mutate a path</p>
<p><strong>Unique mutability.</strong> There is only one <em>usable</em> mutable path to any
given memory at any given time. This implies that when claiming memory
with an expression like <code>p = &amp;mut x</code>, the compiler must guarantee that
the borrowed value <code>x</code> can no longer be mutated so long as <code>p</code> is
live. (This is done via restrictions, read on.)</p>
<p><strong>.</strong></p>
<h3>The <code>gather_loans</code> pass</h3>
<p>We start with the <code>gather_loans</code> pass, which walks the AST looking for
borrows.  For each borrow, there are three bits of information: the
place <code>P</code> being borrowed and the mutability <code>MQ</code> and lifetime <code>LT</code>
of the resulting pointer. Given those, <code>gather_loans</code> applies four
validity tests:</p>
<ol>
<li>
<p><code>MUTABILITY(P, MQ)</code>: The mutability of the reference is
compatible with the mutability of <code>P</code> (i.e., not borrowing immutable
data as mutable).</p>
</li>
<li>
<p><code>ALIASABLE(P, MQ)</code>: The aliasability of the reference is
compatible with the aliasability of <code>P</code>. The goal is to prevent
<code>&amp;mut</code> borrows of aliasability data.</p>
</li>
<li>
<p><code>LIFETIME(P, LT, MQ)</code>: The lifetime of the borrow does not exceed
the lifetime of the value being borrowed.</p>
</li>
<li>
<p><code>RESTRICTIONS(P, LT, ACTIONS) = RS</code>: This pass checks and computes the
restrictions to maintain memory safety. These are the restrictions
that will go into the final loan. We'll discuss in more detail below.</p>
</li>
</ol>
<h2>Checking mutability</h2>
<p>Checking mutability is fairly straightforward. We just want to prevent
immutable data from being borrowed as mutable. Note that it is ok to borrow
mutable data as immutable, since that is simply a freeze. The judgement
<code>MUTABILITY(P, MQ)</code> means the mutability of <code>P</code> is compatible with a borrow
of mutability <code>MQ</code>. The Rust code corresponding to this predicate is the
function <code>check_mutability</code> in <code>middle::borrowck::gather_loans</code>.</p>
<h3>Checking mutability of variables</h3>
<p><em>Code pointer:</em> Function <code>check_mutability()</code> in <code>gather_loans/mod.rs</code>,
but also the code in <code>mem_categorization</code>.</p>
<p>Let's begin with the rules for variables, which state that if a
variable is declared as mutable, it may be borrowed any which way, but
otherwise the variable must be borrowed as immutable:</p>
<pre>MUTABILITY(X, MQ)                   // M-Var-Mut
  DECL(X) = mut

MUTABILITY(X, imm)                  // M-Var-Imm
  DECL(X) = imm
</pre>
<h3>Checking mutability of owned content</h3>
<p>Fields and boxes inherit their mutability from
their base expressions, so both of their rules basically
delegate the check to the base expression <code>P</code>:</p>
<pre>MUTABILITY(P.f, MQ)                // M-Field
  MUTABILITY(P, MQ)

MUTABILITY(*P, MQ)                 // M-Deref-Unique
  TYPE(P) = Box&lt;Ty&gt;
  MUTABILITY(P, MQ)
</pre>
<h3>Checking mutability of immutable pointer types</h3>
<p>Immutable pointer types like <code>&amp;T</code> can only
be borrowed if MQ is immutable:</p>
<pre>MUTABILITY(*P, imm)               // M-Deref-Borrowed-Imm
  TYPE(P) = &amp;Ty
</pre>
<h3>Checking mutability of mutable pointer types</h3>
<p><code>&amp;mut T</code> can be frozen, so it is acceptable to borrow it as either imm or mut:</p>
<pre>MUTABILITY(*P, MQ)                 // M-Deref-Borrowed-Mut
  TYPE(P) = &amp;mut Ty
</pre>
<h2>Checking aliasability</h2>
<p>The goal of the aliasability check is to ensure that we never permit <code>&amp;mut</code>
borrows of aliasable data. The judgement <code>ALIASABLE(P, MQ)</code> means the
aliasability of <code>P</code> is compatible with a borrow of mutability <code>MQ</code>. The Rust
code corresponding to this predicate is the function <code>check_aliasability()</code> in
<code>middle::borrowck::gather_loans</code>.</p>
<h3>Checking aliasability of variables</h3>
<p>Local variables are never aliasable as they are accessible only within
the stack frame.</p>
<pre>    ALIASABLE(X, MQ)                   // M-Var-Mut
</pre>
<h3>Checking aliasable of owned content</h3>
<p>Owned content is aliasable if it is found in an aliasable location:</p>
<pre>ALIASABLE(P.f, MQ)                // M-Field
  ALIASABLE(P, MQ)

ALIASABLE(*P, MQ)                 // M-Deref-Unique
  ALIASABLE(P, MQ)
</pre>
<h3>Checking aliasability of immutable pointer types</h3>
<p>Immutable pointer types like <code>&amp;T</code> are aliasable, and hence can only be
borrowed immutably:</p>
<pre>ALIASABLE(*P, imm)                // M-Deref-Borrowed-Imm
  TYPE(P) = &amp;Ty
</pre>
<h3>Checking aliasability of mutable pointer types</h3>
<p><code>&amp;mut T</code> can be frozen, so it is acceptable to borrow it as either imm or mut:</p>
<pre>ALIASABLE(*P, MQ)                 // M-Deref-Borrowed-Mut
  TYPE(P) = &amp;mut Ty
</pre>
<h2>Checking lifetime</h2>
<p>These rules aim to ensure that no data is borrowed for a scope that exceeds
its lifetime. These two computations wind up being intimately related.
Formally, we define a predicate <code>LIFETIME(P, LT, MQ)</code>, which states that
"the place <code>P</code> can be safely borrowed for the lifetime <code>LT</code> with mutability
<code>MQ</code>". The Rust code corresponding to this predicate is the module
<code>middle::borrowck::gather_loans::lifetime</code>.</p>
<h3>Checking lifetime of variables</h3>
<p>The rule for variables states that a variable can only be borrowed a
lifetime <code>LT</code> that is a subregion of the variable's scope:</p>
<pre>LIFETIME(X, LT, MQ)                 // L-Local
  LT &lt;= block where X is declared
</pre>
<h3>Checking lifetime for owned content</h3>
<p>The lifetime of a field or box is the same as the lifetime
of its owner:</p>
<pre>LIFETIME(P.f, LT, MQ)              // L-Field
  LIFETIME(P, LT, MQ)

LIFETIME(*P, LT, MQ)               // L-Deref-Send
  TYPE(P) = Box&lt;Ty&gt;
  LIFETIME(P, LT, MQ)
</pre>
<h3>Checking lifetime for derefs of references</h3>
<p>References have a lifetime <code>LT'</code> associated with them.  The
data they point at has been guaranteed to be valid for at least this
lifetime. Therefore, the borrow is valid so long as the lifetime <code>LT</code>
of the borrow is shorter than the lifetime <code>LT'</code> of the pointer
itself:</p>
<pre>LIFETIME(*P, LT, MQ)               // L-Deref-Borrowed
  TYPE(P) = &amp;LT' Ty OR &amp;LT' mut Ty
  LT &lt;= LT'
</pre>
<h2>Computing the restrictions</h2>
<p>The final rules govern the computation of <em>restrictions</em>, meaning that
we compute the set of actions that will be illegal for the life of the
loan. The predicate is written <code>RESTRICTIONS(P, LT, ACTIONS) = RESTRICTION*</code>, which can be read "in order to prevent <code>ACTIONS</code> from
occurring on <code>P</code>, the restrictions <code>RESTRICTION*</code> must be respected
for the lifetime of the loan".</p>
<p>Note that there is an initial set of restrictions: these restrictions
are computed based on the kind of borrow:</p>
<pre>&amp;mut P =&gt;   RESTRICTIONS(P, LT, MUTATE|CLAIM|FREEZE)
&amp;P =&gt;       RESTRICTIONS(P, LT, MUTATE|CLAIM)
</pre>
<p>The reasoning here is that a mutable borrow must be the only writer,
therefore it prevents other writes (<code>MUTATE</code>), mutable borrows
(<code>CLAIM</code>), and immutable borrows (<code>FREEZE</code>). An immutable borrow
permits other immutable borrows but forbids writes and mutable borrows.</p>
<h3>Restrictions for loans of a local variable</h3>
<p>The simplest case is a borrow of a local variable <code>X</code>:</p>
<pre>RESTRICTIONS(X, LT, ACTIONS) = (X, ACTIONS)            // R-Variable
</pre>
<p>In such cases we just record the actions that are not permitted.</p>
<h3>Restrictions for loans of fields</h3>
<p>Restricting a field is the same as restricting the owner of that
field:</p>
<pre>RESTRICTIONS(P.f, LT, ACTIONS) = RS, (P.f, ACTIONS)  // R-Field
  RESTRICTIONS(P, LT, ACTIONS) = RS
</pre>
<p>The reasoning here is as follows. If the field must not be mutated,
then you must not mutate the owner of the field either, since that
would indirectly modify the field. Similarly, if the field cannot be
frozen or aliased, we cannot allow the owner to be frozen or aliased,
since doing so indirectly freezes/aliases the field. This is the
origin of inherited mutability.</p>
<h3>Restrictions for loans of owned referents</h3>
<p>Because the mutability of owned referents is inherited, restricting an
owned referent is similar to restricting a field, in that it implies
restrictions on the pointer. However, boxes have an important
twist: if the owner <code>P</code> is mutated, that causes the owned referent
<code>*P</code> to be freed! So whenever an owned referent <code>*P</code> is borrowed, we
must prevent the box <code>P</code> from being mutated, which means
that we always add <code>MUTATE</code> and <code>CLAIM</code> to the restriction set imposed
on <code>P</code>:</p>
<pre>RESTRICTIONS(*P, LT, ACTIONS) = RS, (*P, ACTIONS)    // R-Deref-Send-Pointer
  TYPE(P) = Box&lt;Ty&gt;
  RESTRICTIONS(P, LT, ACTIONS|MUTATE|CLAIM) = RS
</pre>
<h3>Restrictions for loans of immutable borrowed referents</h3>
<p>Immutable borrowed referents are freely aliasable, meaning that
the compiler does not prevent you from copying the pointer.  This
implies that issuing restrictions is useless. We might prevent the
user from acting on <code>*P</code> itself, but there could be another path
<code>*P1</code> that refers to the exact same memory, and we would not be
restricting that path. Therefore, the rule for <code>&amp;Ty</code> pointers
always returns an empty set of restrictions, and it only permits
restricting <code>MUTATE</code> and <code>CLAIM</code> actions:</p>
<pre>RESTRICTIONS(*P, LT, ACTIONS) = []                    // R-Deref-Imm-Borrowed
  TYPE(P) = &amp;LT' Ty
  LT &lt;= LT'                                            // (1)
  ACTIONS subset of [MUTATE, CLAIM]
</pre>
<p>The reason that we can restrict <code>MUTATE</code> and <code>CLAIM</code> actions even
without a restrictions list is that it is never legal to mutate nor to
borrow mutably the contents of a <code>&amp;Ty</code> pointer. In other words,
those restrictions are already inherent in the type.</p>
<p>Clause (1) in the rule for <code>&amp;Ty</code> deserves mention. Here I
specify that the lifetime of the loan must be less than the lifetime
of the <code>&amp;Ty</code> pointer. In simple cases, this clause is redundant, since
the <code>LIFETIME()</code> function will already enforce the required rule:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>point</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-t>Point</a-t><a-p>)</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>static</a-l> <a-t>i32</a-t> <a-p>{</a-p>
    <a-o>&amp;</a-o>point<a-p>.</a-p><a-pr>x</a-pr> <a-c>// Error</a-c>
<a-p>}</a-p></pre>
<p>The above example fails to compile both because of clause (1) above
but also by the basic <code>LIFETIME()</code> check. However, in more advanced
examples involving multiple nested pointers, clause (1) is needed:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>point</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-k>mut</a-k> <a-t>Point</a-t><a-p>)</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-t>i32</a-t> <a-p>{</a-p>
    <a-o>&amp;</a-o>point<a-p>.</a-p><a-pr>x</a-pr> <a-c>// Error</a-c>
<a-p>}</a-p></pre>
<p>The <code>LIFETIME</code> rule here would accept <code>'b</code> because, in fact, the
<em>memory is</em> guaranteed to remain valid (i.e., not be freed) for the
lifetime <code>'b</code>, since the <code>&amp;mut</code> pointer is valid for <code>'b</code>. However, we
are returning an immutable reference, so we need the memory to be both
valid and immutable. Even though <code>point.x</code> is referenced by an <code>&amp;mut</code>
pointer, it can still be considered immutable so long as that <code>&amp;mut</code>
pointer is found in an aliased location. That means the memory is
guaranteed to be <em>immutable</em> for the lifetime of the <code>&amp;</code> pointer,
which is only <code>'a</code>, not <code>'b</code>. Hence this example yields an error.</p>
<p>As a final twist, consider the case of two nested <em>immutable</em>
pointers, rather than a mutable pointer within an immutable one:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>point</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-t>Point</a-t><a-p>)</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-t>i32</a-t> <a-p>{</a-p>
    <a-o>&amp;</a-o>point<a-p>.</a-p><a-pr>x</a-pr> <a-c>// OK</a-c>
<a-p>}</a-p></pre>
<p>This function is legal. The reason for this is that the inner pointer
(<code>*point : &amp;'b Point</code>) is enough to guarantee the memory is immutable
and valid for the lifetime <code>'b</code>.  This is reflected in
<code>RESTRICTIONS()</code> by the fact that we do not recurse (i.e., we impose
no restrictions on <code>P</code>, which in this particular case is the pointer
<code>point : &amp;'a &amp;'b Point</code>).</p>
<h4>Why both <code>LIFETIME()</code> and <code>RESTRICTIONS()</code>?</h4>
<p>Given the previous text, it might seem that <code>LIFETIME</code> and
<code>RESTRICTIONS</code> should be folded together into one check, but there is
a reason that they are separated. They answer separate concerns.
The rules pertaining to <code>LIFETIME</code> exist to ensure that we don't
create a borrowed pointer that outlives the memory it points at. So
<code>LIFETIME</code> prevents a function like this:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>get_1</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;()</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-t>i32</a-t> <a-p>{</a-p>
    <a-k>let</a-k> x = <a-co>1</a-co><a-p>;</a-p>
    <a-o>&amp;</a-o>x
<a-p>}</a-p></pre>
<p>Here we would be returning a pointer into the stack. Clearly bad.</p>
<p>However, the <code>RESTRICTIONS</code> rules are more concerned with how memory
is used. The example above doesn't generate an error according to
<code>RESTRICTIONS</code> because, for local variables, we don't require that the
loan lifetime be a subset of the local variable lifetime. The idea
here is that we <em>can</em> guarantee that <code>x</code> is not (e.g.) mutated for the
lifetime <code>'a</code>, even though <code>'a</code> exceeds the function body and thus
involves unknown code in the caller -- after all, <code>x</code> ceases to exist
after we return and hence the remaining code in <code>'a</code> cannot possibly
mutate it. This distinction is important for type checking functions
like this one:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>inc_and_get</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;(</a-p><a-v>p</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>Point</a-t><a-p>)</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-t>i32</a-t> <a-p>{</a-p>
    p<a-p>.</a-p><a-pr>x</a-pr> += <a-co>1</a-co><a-p>;</a-p>
    <a-o>&amp;</a-o>p<a-p>.</a-p><a-pr>x</a-pr>
<a-p>}</a-p></pre>
<p>In this case, we take in a <code>&amp;mut</code> and return a frozen borrowed pointer
with the same lifetime. So long as the lifetime of the returned value
doesn't exceed the lifetime of the <code>&amp;mut</code> we receive as input, this is
fine, though it may seem surprising at first (it surprised me when I
first worked it through). After all, we're guaranteeing that <code>*p</code>
won't be mutated for the lifetime <code>'a</code>, even though we can't "see" the
entirety of the code during that lifetime, since some of it occurs in
our caller. But we <em>do</em> know that nobody can mutate <code>*p</code> except
through <code>p</code>. So if we don't mutate <code>*p</code> and we don't return <code>p</code>, then
we know that the right to mutate <code>*p</code> has been lost to our caller --
in terms of capability, the caller passed in the ability to mutate
<code>*p</code>, and we never gave it back. (Note that we can't return <code>p</code> while
<code>*p</code> is borrowed since that would be a move of <code>p</code>, as <code>&amp;mut</code> pointers
are affine.)</p>
<h3>Restrictions for loans of mutable borrowed referents</h3>
<p>Mutable borrowed pointers are guaranteed to be the only way to mutate
their referent. This permits us to take greater license with them; for
example, the referent can be frozen simply be ensuring that we do not
use the original pointer to perform mutate. Similarly, we can allow
the referent to be claimed, so long as the original pointer is unused
while the new claimant is live.</p>
<p>The rule for mutable borrowed pointers is as follows:</p>
<pre>RESTRICTIONS(*P, LT, ACTIONS) = RS, (*P, ACTIONS)    // R-Deref-Mut-Borrowed
  TYPE(P) = &amp;LT' mut Ty
  LT &lt;= LT'                                            // (1)
  RESTRICTIONS(P, LT, ACTIONS) = RS                   // (2)
</pre>
<p>Let's examine the two numbered clauses:</p>
<p>Clause (1) specifies that the lifetime of the loan (<code>LT</code>) cannot
exceed the lifetime of the <code>&amp;mut</code> pointer (<code>LT'</code>). The reason for this
is that the <code>&amp;mut</code> pointer is guaranteed to be the only legal way to
mutate its referent -- but only for the lifetime <code>LT'</code>.  After that
lifetime, the loan on the referent expires and hence the data may be
modified by its owner again. This implies that we are only able to
guarantee that the referent will not be modified or aliased for a
maximum of <code>LT'</code>.</p>
<p>Here is a concrete example of a bug this rule prevents:</p>
<pre class="language-rust"><a-c>// Test region-reborrow-from-shorter-mut-ref.rs:</a-c>
<a-k>fn</a-k> <a-f>copy_borrowed_ptr</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>,</a-p><a-o>&#39;</a-o><a-l>b</a-l><a-p>,</a-p><a-t>T</a-t><a-p>&gt;(</a-p><a-v>x</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-k>mut</a-k> <a-t>T</a-t><a-p>)</a-p> -&gt; <a-o>&amp;&#39;</a-o><a-l>b</a-l> <a-k>mut</a-k> <a-t>T</a-t> <a-p>{</a-p>
    <a-o>&amp;</a-o><a-k>mut</a-k> <a-o>**</a-o>p <a-c>// ERROR due to clause (1)</a-c>
<a-p>}</a-p>
<a-k>fn</a-k> <a-f>main</a-f><a-p>()</a-p> <a-p>{</a-p>
    <a-k>let</a-k> <a-k>mut</a-k> x = <a-co>1</a-co><a-p>;</a-p>
    <a-k>let</a-k> <a-k>mut</a-k> y = <a-o>&amp;</a-o><a-k>mut</a-k> x<a-p>;</a-p> <a-c>// &lt;-&#39;b-----------------------------+</a-c>
    <a-c>//      +-&#39;a--------------------+                       |</a-c>
    <a-c>//      v                       v                       |</a-c>
    <a-k>let</a-k> z = <a-f>copy_borrowed_ptr</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> y<a-p>);</a-p> <a-c>// y is lent         |</a-c>
    <a-o>*</a-o>y += <a-co>1</a-co><a-p>;</a-p> <a-c>// Here y==z, so both should not be usable...  |</a-c>
    <a-o>*</a-o>z += <a-co>1</a-co><a-p>;</a-p> <a-c>// ...and yet they would be, but for clause 1. |</a-c>
<a-p>}</a-p> <a-c>// &lt;------------------------------------------------------+</a-c></pre>
<p>Clause (2) propagates the restrictions on the referent to the pointer
itself. This is the same as with an box, though the
reasoning is mildly different. The basic goal in all cases is to
prevent the user from establishing another route to the same data. To
see what I mean, let's examine various cases of what can go wrong and
show how it is prevented.</p>
<p><strong>Example danger 1: Moving the base pointer.</strong> One of the simplest
ways to violate the rules is to move the base pointer to a new name
and access it via that new name, thus bypassing the restrictions on
the old name. Here is an example:</p>
<pre class="language-rust"><a-c>// src/test/compile-fail/borrowck-move-mut-base-ptr.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t0<a-p>;</a-p> <a-c>// Freezes `*t0`</a-c>
    <a-k>let</a-k> t1 = t0<a-p>;</a-p>        <a-c>//~ ERROR cannot move out of `t0`</a-c>
    <a-o>*</a-o>t1 = <a-co>22</a-co><a-p>;</a-p>           <a-c>// OK, not a write through `*t0`</a-c>
<a-p>}</a-p></pre>
<p>Remember that <code>&amp;mut</code> pointers are linear, and hence <code>let t1 = t0</code> is a
move of <code>t0</code> -- or would be, if it were legal. Instead, we get an
error, because clause (2) imposes restrictions on <code>P</code> (<code>t0</code>, here),
and any restrictions on a path make it impossible to move from that
path.</p>
<p><strong>Example danger 2: Claiming the base pointer.</strong> Another possible
danger is to mutably borrow the base path. This can lead to two bad
scenarios. The most obvious is that the mutable borrow itself becomes
another path to access the same data, as shown here:</p>
<pre class="language-rust"><a-c>// src/test/compile-fail/borrowck-mut-borrow-of-mut-base-ptr.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;(</a-p><a-k>mut</a-k> <a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>,</a-p>
           <a-k>mut</a-k> <a-v>t1</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t0<a-p>;</a-p>     <a-c>// Freezes `*t0`</a-c>
    <a-k>let</a-k> <a-k>mut</a-k> t2 = <a-o>&amp;</a-o><a-k>mut</a-k> t0<a-p>;</a-p>   <a-c>//~ ERROR cannot borrow `t0`</a-c>
    <a-o>**</a-o>t2 += <a-co>1</a-co><a-p>;</a-p>              <a-c>// Mutates `*t0`</a-c>
<a-p>}</a-p></pre>
<p>In this example, <code>**t2</code> is the same memory as <code>*t0</code>. Because <code>t2</code> is
an <code>&amp;mut</code> pointer, <code>**t2</code> is a unique path and hence it would be
possible to mutate <code>**t2</code> even though that memory was supposed to be
frozen by the creation of <code>p</code>. However, an error is reported -- the
reason is that the freeze <code>&amp;*t0</code> will restrict claims and mutation
against <code>*t0</code> which, by clause 2, in turn prevents claims and mutation
of <code>t0</code>. Hence the claim <code>&amp;mut t0</code> is illegal.</p>
<p>Another danger with an <code>&amp;mut</code> pointer is that we could swap the <code>t0</code>
value away to create a new path:</p>
<pre class="language-rust"><a-c>// src/test/compile-fail/borrowck-swap-mut-base-ptr.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;(</a-p><a-k>mut</a-k> <a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>,</a-p>
           <a-k>mut</a-k> <a-v>t1</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t0<a-p>;</a-p>     <a-c>// Freezes `*t0`</a-c>
    <a-f>swap</a-f><a-p>(</a-p><a-o>&amp;</a-o><a-k>mut</a-k> t0<a-p>,</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> t1<a-p>);</a-p> <a-c>//~ ERROR cannot borrow `t0`</a-c>
    <a-o>*</a-o>t1 = <a-co>22</a-co><a-p>;</a-p>
<a-p>}</a-p></pre>
<p>This is illegal for the same reason as above. Note that if we added
back a swap operator -- as we used to have -- we would want to be very
careful to ensure this example is still illegal.</p>
<p><strong>Example danger 3: Freeze the base pointer.</strong> In the case where the
referent is claimed, even freezing the base pointer can be dangerous,
as shown in the following example:</p>
<pre class="language-rust"><a-c>// src/test/compile-fail/borrowck-borrow-of-mut-base-ptr.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;(</a-p><a-k>mut</a-k> <a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>,</a-p>
           <a-k>mut</a-k> <a-v>t1</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>i32</a-t> = <a-o>&amp;</a-o><a-k>mut</a-k> <a-o>*</a-o>t0<a-p>;</a-p> <a-c>// Claims `*t0`</a-c>
    <a-k>let</a-k> <a-k>mut</a-k> t2 = <a-o>&amp;</a-o>t0<a-p>;</a-p>           <a-c>//~ ERROR cannot borrow `t0`</a-c>
    <a-k>let</a-k> q<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t2<a-p>;</a-p>         <a-c>// Freezes `*t0` but not through `*p`</a-c>
    <a-o>*</a-o>p += <a-co>1</a-co><a-p>;</a-p>                    <a-c>// violates type of `*q`</a-c>
<a-p>}</a-p></pre>
<p>Here the problem is that <code>*t0</code> is claimed by <code>p</code>, and hence <code>p</code> wants
to be the controlling pointer through which mutation or freezes occur.
But <code>t2</code> would -- if it were legal -- have the type <code>&amp; &amp;mut i32</code>, and
hence would be a mutable pointer in an aliasable location, which is
considered frozen (since no one can write to <code>**t2</code> as it is not a
unique path). Therefore, we could reasonably create a frozen <code>&amp;i32</code>
pointer pointing at <code>*t0</code> that coexists with the mutable pointer <code>p</code>,
which is clearly unsound.</p>
<p>However, it is not always unsafe to freeze the base pointer. In
particular, if the referent is frozen, there is no harm in it:</p>
<pre class="language-rust"><a-c>// src/test/ui/borrowck-borrow-of-mut-base-ptr-safe.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>&lt;</a-p><a-o>&#39;</a-o><a-l>a</a-l><a-p>&gt;(</a-p><a-k>mut</a-k> <a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>,</a-p>
           <a-k>mut</a-k> <a-v>t1</a-v><a-p>:</a-p> <a-o>&amp;&#39;</a-o><a-l>a</a-l> <a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t0<a-p>;</a-p> <a-c>// Freezes `*t0`</a-c>
    <a-k>let</a-k> <a-k>mut</a-k> t2 = <a-o>&amp;</a-o>t0<a-p>;</a-p>
    <a-k>let</a-k> q<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t2<a-p>;</a-p> <a-c>// Freezes `*t0`, but that&#39;s ok...</a-c>
    <a-k>let</a-k> r<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;*</a-o>t0<a-p>;</a-p> <a-c>// ...after all, could do same thing directly.</a-c>
<a-p>}</a-p></pre>
<p>In this case, creating the alias <code>t2</code> of <code>t0</code> is safe because the only
thing <code>t2</code> can be used for is to further freeze <code>*t0</code>, which is
already frozen. In particular, we cannot assign to <code>*t0</code> through the
new alias <code>t2</code>, as demonstrated in this test case:</p>
<pre class="language-rust"><a-c>// src/test/ui/borrowck-borrow-mut-base-ptr-in-aliasable-loc.rs</a-c>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>t0</a-v><a-p>:</a-p> <a-o>&amp;</a-o> <a-o>&amp;</a-o><a-k>mut</a-k> <a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> t1 = t0<a-p>;</a-p>
    <a-k>let</a-k> p<a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t> = <a-o>&amp;**</a-o>t0<a-p>;</a-p>
    <a-o>**</a-o>t1 = <a-co>22</a-co><a-p>;</a-p> <a-c>//~ ERROR cannot assign</a-c>
<a-p>}</a-p></pre>
<p>This distinction is reflected in the rules. When doing an <code>&amp;mut</code>
borrow -- as in the first example -- the set <code>ACTIONS</code> will be
<code>CLAIM|MUTATE|FREEZE</code>, because claiming the referent implies that it
cannot be claimed, mutated, or frozen by anyone else. These
restrictions are propagated back to the base path and hence the base
path is considered unfreezable.</p>
<p>In contrast, when the referent is merely frozen -- as in the second
example -- the set <code>ACTIONS</code> will be <code>CLAIM|MUTATE</code>, because freezing
the referent implies that it cannot be claimed or mutated but permits
others to freeze. Hence when these restrictions are propagated back to
the base path, it will still be considered freezable.</p>
<p><strong>FIXME <a href="https://github.com/rust-lang/rfcs/issues/1751">RFC 1751</a>
Restrictions against mutating the base pointer.</strong>
When an <code>&amp;mut</code> pointer is frozen or claimed, we currently pass along the
restriction against MUTATE to the base pointer. I do not believe this
restriction is needed. It dates from the days when we had a way to
mutate that preserved the value being mutated (i.e., swap). Nowadays
the only form of mutation is assignment, which destroys the pointer
being mutated -- therefore, a mutation cannot create a new path to the
same data. Rather, it removes an existing path. This implies that not
only can we permit mutation, we can have mutation kill restrictions in
the dataflow sense.</p>
<p><strong>WARNING:</strong> We do not currently have <code>const</code> borrows in the
language. If they are added back in, we must ensure that they are
consistent with all of these examples. The crucial question will be
what sorts of actions are permitted with a <code>&amp;const &amp;mut</code> pointer. I
would suggest that an <code>&amp;mut</code> referent found in an <code>&amp;const</code> location be
prohibited from both freezes and claims. This would avoid the need to
prevent <code>const</code> borrows of the base pointer when the referent is
borrowed.</p>
<p>[ Previous revisions of this document discussed <code>&amp;const</code> in more detail.
See the revision history. ]</p>
<h1>Moves and initialization</h1>
<p>The borrow checker is also in charge of ensuring that:</p>
<ul>
<li>all memory which is accessed is initialized</li>
<li>immutable local variables are assigned at most once.</li>
</ul>
<p>These are two separate dataflow analyses built on the same
framework. Let's look at checking that memory is initialized first;
the checking of immutable local variable assignments works in a very
similar way.</p>
<p>To track the initialization of memory, we actually track all the
points in the program that <em>create uninitialized memory</em>, meaning
moves and the declaration of uninitialized variables. For each of
these points, we create a bit in the dataflow set. Assignments to a
variable <code>x</code> or path <code>a.b.c</code> kill the move/uninitialization bits for
those paths and any subpaths (e.g., <code>x</code>, <code>x.y</code>, <code>a.b.c</code>, <code>*a.b.c</code>).
Bits are unioned when two control-flow paths join. Thus, the
presence of a bit indicates that the move may have occurred without an
intervening assignment to the same memory. At each use of a variable,
we examine the bits in scope, and check that none of them are
moves/uninitializations of the variable that is being used.</p>
<p>Let's look at a simple example:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p> <a-t>Box</a-t><a-p>&lt;</a-p><a-t>i32</a-t><a-p>&gt;)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> b<a-p>:</a-p> <a-t>Box</a-t><a-p>&lt;</a-p><a-t>i32</a-t><a-p>&gt;;</a-p>   <a-c>// Gen bit 0.</a-c>

    <a-k>if</a-k> cond <a-p>{</a-p>          <a-c>// Bits: 0</a-c>
        <a-k>use</a-k><a-p>(</a-p><a-o>&amp;*</a-o>a<a-p>);</a-p>
        b = a<a-p>;</a-p>         <a-c>// Gen bit 1, kill bit 0.</a-c>
        <a-k>use</a-k><a-p>(</a-p><a-o>&amp;*</a-o>b<a-p>);</a-p>
    <a-p>}</a-p> <a-k>else</a-k> <a-p>{</a-p>
                       <a-c>// Bits: 0</a-c>
    <a-p>}</a-p>
                       <a-c>// Bits: 0,1</a-c>
    <a-k>use</a-k><a-p>(</a-p><a-o>&amp;*</a-o>a<a-p>);</a-p>          <a-c>// Error.</a-c>
    <a-k>use</a-k><a-p>(</a-p><a-o>&amp;*</a-o>b<a-p>);</a-p>          <a-c>// Error.</a-c>
<a-p>}</a-p>

<a-k>fn</a-k> <a-f>use</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p> <a-o>&amp;</a-o><a-t>i32</a-t><a-p>)</a-p> <a-p>{</a-p> <a-p>}</a-p></pre>
<p>In this example, the variable <code>b</code> is created uninitialized. In one
branch of an <code>if</code>, we then move the variable <code>a</code> into <code>b</code>. Once we
exit the <code>if</code>, therefore, it is an error to use <code>a</code> or <code>b</code> since both
are only conditionally initialized. I have annotated the dataflow
state using comments. There are two dataflow bits, with bit 0
corresponding to the creation of <code>b</code> without an initializer, and bit 1
corresponding to the move of <code>a</code>. The assignment <code>b = a</code> both
generates bit 1, because it is a move of <code>a</code>, and kills bit 0, because
<code>b</code> is now initialized. On the else branch, though, <code>b</code> is never
initialized, and so bit 0 remains untouched. When the two flows of
control join, we union the bits from both sides, resulting in both
bits 0 and 1 being set. Thus any attempt to use <code>a</code> uncovers the bit 1
from the "then" branch, showing that <code>a</code> may be moved, and any attempt
to use <code>b</code> uncovers bit 0, from the "else" branch, showing that <code>b</code>
may not be initialized.</p>
<h2>Initialization of immutable variables</h2>
<p>Initialization of immutable variables works in a very similar way,
except that:</p>
<ol>
<li>we generate bits for each assignment to a variable;</li>
<li>the bits are never killed except when the variable goes out of scope.</li>
</ol>
<p>Thus the presence of an assignment bit indicates that the assignment
may have occurred. Note that assignments are only killed when the
variable goes out of scope, as it is not relevant whether or not there
has been a move in the meantime. Using these bits, we can declare that
an assignment to an immutable variable is legal iff there is no other
assignment bit to that same variable in scope.</p>
<h2>Why is the design made this way?</h2>
<p>It may seem surprising that we assign dataflow bits to <em>each move</em>
rather than <em>each path being moved</em>. This is somewhat less efficient,
since on each use, we must iterate through all moves and check whether
any of them correspond to the path in question. Similar concerns apply
to the analysis for double assignments to immutable variables. The
main reason to do it this way is that it allows us to print better
error messages, because when a use occurs, we can print out the
precise move that may be in scope, rather than simply having to say
"the variable may not be initialized".</p>
<h2>Data structures used in the move analysis</h2>
<p>The move analysis maintains several data structures that enable it to
cross-reference moves and assignments to determine when they may be
moving/assigning the same memory. These are all collected into the
<code>MoveData</code> and <code>FlowedMoveData</code> structs. The former represents the set
of move paths, moves, and assignments, and the latter adds in the
results of a dataflow computation.</p>
<h3>Move paths</h3>
<p>The <code>MovePath</code> tree tracks every path that is moved or assigned to.
These paths have the same form as the <code>LoanPath</code> data structure, which
in turn is the "real world version of the places <code>P</code> that we
introduced earlier. The difference between a <code>MovePath</code> and a <code>LoanPath</code>
is that move paths are:</p>
<ol>
<li>Canonicalized, so that we have exactly one copy of each, and
we can refer to move paths by index;</li>
<li>Cross-referenced with other paths into a tree, so that given a move
path we can efficiently find all parent move paths and all
extensions (e.g., given the <code>a.b</code> move path, we can easily find the
move path <code>a</code> and also the move paths <code>a.b.c</code>)</li>
<li>Cross-referenced with moves and assignments, so that we can
easily find all moves and assignments to a given path.</li>
</ol>
<p>The mechanism that we use is to create a <code>MovePath</code> record for each
move path. These are arranged in an array and are referenced using
<code>MovePathIndex</code> values, which are newtype'd indices. The <code>MovePath</code>
structs are arranged into a tree, representing using the standard
Knuth representation where each node has a child 'pointer' and a "next
sibling" 'pointer'. In addition, each <code>MovePath</code> has a parent
'pointer'.  In this case, the 'pointers' are just <code>MovePathIndex</code>
values.</p>
<p>In this way, if we want to find all base paths of a given move path,
we can just iterate up the parent pointers (see <code>each_base_path()</code> in
the <code>move_data</code> module). If we want to find all extensions, we can
iterate through the subtree (see <code>each_extending_path()</code>).</p>
<h3>Moves and assignments</h3>
<p>There are structs to represent moves (<code>Move</code>) and assignments
(<code>Assignment</code>), and these are also placed into arrays and referenced
by index. All moves of a particular path are arranged into a linked
lists, beginning with <code>MovePath.first_move</code> and continuing through
<code>Move.next_move</code>.</p>
<p>We distinguish between "var" assignments, which are assignments to a
variable like <code>x = foo</code>, and "path" assignments (<code>x.f = foo</code>).  This
is because we need to assign dataflows to the former, but not the
latter, so as to check for double initialization of immutable
variables.</p>
<h3>Gathering and checking moves</h3>
<p>Like loans, we distinguish two phases. The first, gathering, is where
we uncover all the moves and assignments. As with loans, we do some
basic sanity checking in this phase, so we'll report errors if you
attempt to move out of a borrowed pointer etc. Then we do the dataflow
(see <code>FlowedMoveData::new</code>). Finally, in the <code>check_loans.rs</code> code, we
walk back over, identify all uses, assignments, and captures, and
check that they are legal given the set of dataflow bits we have
computed for that program point.</p>
<h1>Drop flags and structural fragments</h1>
<p>In addition to the job of enforcing memory safety, the borrow checker
code is also responsible for identifying the <em>structural fragments</em> of
data in the function, to support out-of-band dynamic drop flags
allocated on the stack. (For background, see <a href="https://github.com/rust-lang/rfcs/pull/320">RFC PR #320</a>.)</p>
<p>Semantically, each piece of data that has a destructor may need a
boolean flag to indicate whether or not its destructor has been run
yet. However, in many cases there is no need to actually maintain such
a flag: It can be apparent from the code itself that a given path is
always initialized (or always deinitialized) when control reaches the
end of its owner's scope, and thus we can unconditionally emit (or
not) the destructor invocation for that path.</p>
<p>A simple example of this is the following:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>D</a-t> <a-p>{</a-p> <a-pr>p</a-pr><a-p>:</a-p> <a-t>i32</a-t> <a-p>}</a-p>
<a-k>impl</a-k> <a-t>D</a-t> <a-p>{</a-p> <a-k>fn</a-k> <a-f>new</a-f><a-p>(</a-p><a-v>x</a-v><a-p>:</a-p> <a-t>i32</a-t><a-p>)</a-p> -&gt; <a-t>D</a-t> <a-p>{</a-p> ..<a-p>.</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>
</a-pr><a-k>impl</a-k><a-pr> </a-pr><a-t>Drop</a-t><a-pr> </a-pr><a-k>for</a-k><a-pr> </a-pr><a-t>D</a-t><a-pr> </a-pr><a-p>{</a-p><a-pr> ... </a-pr><a-p>}</a-p><a-pr>

</a-pr><a-k>fn</a-k><a-pr> </a-pr><a-f>foo</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p><a-pr> </a-pr><a-t>D</a-t><a-p>,</a-p><a-pr> </a-pr><a-v>b</a-v><a-p>:</a-p><a-pr> </a-pr><a-t>D</a-t><a-p>,</a-p><a-pr> t</a-pr><a-p>:</a-p><a-pr> || -&gt; bool</a-pr><a-p>)</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr>
    </a-pr><a-k>let</a-k><a-pr> c</a-pr><a-p>:</a-p><a-pr> </a-pr><a-t>D</a-t><a-p>;</a-p><a-pr>
    </a-pr><a-k>let</a-k><a-pr> d</a-pr><a-p>:</a-p><a-pr> </a-pr><a-t>D</a-t><a-p>;</a-p><a-pr>
    </a-pr><a-k>if</a-k><a-pr> </a-pr><a-f>t</a-f><a-p>()</a-p><a-pr> </a-pr><a-p>{</a-p><a-pr> c = b</a-pr><a-p>;</a-p><a-pr> </a-pr><a-p>}</a-p><a-pr>
</a-pr><a-p>}</a-p></pre>
<p>At the end of the body of <code>foo</code>, the compiler knows that <code>a</code> is
initialized, introducing a drop obligation (deallocating the boxed
integer) for the end of <code>a</code>'s scope that is run unconditionally.
Likewise the compiler knows that <code>d</code> is not initialized, and thus it
leave out the drop code for <code>d</code>.</p>
<p>The compiler cannot statically know the drop-state of <code>b</code> nor <code>c</code> at
the end of their scope, since that depends on the value of
<code>t</code>. Therefore, we need to insert boolean flags to track whether we
need to drop <code>b</code> and <code>c</code>.</p>
<p>However, the matter is not as simple as just mapping local variables
to their corresponding drop flags when necessary. In particular, in
addition to being able to move data out of local variables, Rust
allows one to move values in and out of structured data.</p>
<p>Consider the following:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>S</a-t> <a-p>{</a-p> <a-pr>x</a-pr><a-p>:</a-p> <a-t>D</a-t><a-p>,</a-p> <a-pr>y</a-pr><a-p>:</a-p> <a-t>D</a-t><a-p>,</a-p> <a-pr>z</a-pr><a-p>:</a-p> <a-t>D</a-t> <a-p>}</a-p>

<a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p> <a-t>S</a-t><a-p>,</a-p> <a-k>mut</a-k> <a-v>b</a-v><a-p>:</a-p> <a-t>S</a-t><a-p>,</a-p> t<a-p>:</a-p> || -&gt; bool<a-p>)</a-p> <a-p>{</a-p>
    <a-k>let</a-k> <a-k>mut</a-k> c<a-p>:</a-p> <a-t>S</a-t><a-p>;</a-p>
    <a-k>let</a-k> d<a-p>:</a-p> <a-t>S</a-t><a-p>;</a-p>
    <a-k>let</a-k> e<a-p>:</a-p> <a-t>S</a-t> = a<a-p>.</a-p><a-f>clone</a-f><a-p>();</a-p>
    <a-k>if</a-k> <a-f>t</a-f><a-p>()</a-p> <a-p>{</a-p>
        c = b<a-p>;</a-p>
        b<a-p>.</a-p><a-pr>x</a-pr> = e<a-p>.</a-p><a-pr>y</a-pr><a-p>;</a-p>
    <a-p>}</a-p>
    <a-k>if</a-k> <a-f>t</a-f><a-p>()</a-p> <a-p>{</a-p> c<a-p>.</a-p><a-pr>y</a-pr> = <a-t>D</a-t><a-p>::</a-p><a-f>new</a-f><a-p>(</a-p><a-co>4</a-co><a-p>);</a-p> <a-p>}</a-p>
<a-p>}</a-p></pre>
<p>As before, the drop obligations of <code>a</code> and <code>d</code> can be statically
determined, and again the state of <code>b</code> and <code>c</code> depend on dynamic
state. But additionally, the dynamic drop obligations introduced by
<code>b</code> and <code>c</code> are not just per-local boolean flags. For example, if the
first call to <code>t</code> returns <code>false</code> and the second call <code>true</code>, then at
the end of their scope, <code>b</code> will be completely initialized, but only
<code>c.y</code> in <code>c</code> will be initialized.  If both calls to <code>t</code> return <code>true</code>,
then at the end of their scope, <code>c</code> will be completely initialized,
but only <code>b.x</code> will be initialized in <code>b</code>, and only <code>e.x</code> and <code>e.z</code>
will be initialized in <code>e</code>.</p>
<p>Note that we need to cover the <code>z</code> field in each case in some way,
since it may (or may not) need to be dropped, even though <code>z</code> is never
directly mentioned in the body of the <code>foo</code> function. We call a path
like <code>b.z</code> a <em>fragment sibling</em> of <code>b.x</code>, since the field <code>z</code> comes
from the same structure <code>S</code> that declared the field <code>x</code> in <code>b.x</code>.</p>
<p>In general we need to maintain boolean flags that match the
<code>S</code>-structure of both <code>b</code> and <code>c</code>.  In addition, we need to consult
such a flag when doing an assignment (such as <code>c.y = D::new(4);</code>
above), in order to know whether or not there is a previous value that
needs to be dropped before we do the assignment.</p>
<p>So for any given function, we need to determine what flags are needed
to track its drop obligations. Our strategy for determining the set of
flags is to represent the fragmentation of the structure explicitly:
by starting initially from the paths that are explicitly mentioned in
moves and assignments (such as <code>b.x</code> and <code>c.y</code> above), and then
traversing the structure of the path's type to identify leftover
<em>unmoved fragments</em>: assigning into <code>c.y</code> means that <code>c.x</code> and <code>c.z</code>
are leftover unmoved fragments. Each fragment represents a drop
obligation that may need to be tracked. Paths that are only moved or
assigned in their entirety (like <code>a</code> and <code>d</code>) are treated as a single
drop obligation.</p>
<p>The fragment construction process works by piggy-backing on the
existing <code>move_data</code> module. We already have callbacks that visit each
direct move and assignment; these form the basis for the sets of
moved_leaf_paths and assigned_leaf_paths. From these leaves, we can
walk up their parent chain to identify all of their parent paths.
We need to identify the parents because of cases like the following:</p>
<pre class="language-rust"><a-k>struct</a-k> <a-t>Pair</a-t><a-p>&lt;</a-p><a-t>X</a-t><a-p>,</a-p><a-t>Y</a-t><a-p>&gt;{</a-p> <a-pr>x</a-pr><a-p>:</a-p> <a-t>X</a-t><a-p>,</a-p> <a-pr>y</a-pr><a-p>:</a-p> <a-t>Y</a-t> <a-p>}</a-p>
<a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>dd_d_d</a-v><a-p>:</a-p> <a-t>Pair</a-t><a-p>&lt;</a-p><a-t>Pair</a-t><a-p>&lt;</a-p><a-t>Pair</a-t><a-p>&lt;</a-p><a-t>D</a-t><a-p>,</a-p> <a-t>D</a-t><a-p>&gt;,</a-p> <a-t>D</a-t><a-p>&gt;,</a-p> <a-t>D</a-t><a-p>&gt;)</a-p> <a-p>{</a-p>
    <a-f>other_function</a-f><a-p>(</a-p>dd_d_d<a-p>.</a-p><a-pr>x</a-pr><a-p>.</a-p><a-pr>y</a-pr><a-p>);</a-p>
<a-p>}</a-p></pre>
<p>In this code, the move of the path <code>dd_d.x.y</code> leaves behind not only
the fragment drop-obligation <code>dd_d.x.x</code> but also <code>dd_d.y</code> as well.</p>
<p>Once we have identified the directly-referenced leaves and their
parents, we compute the left-over fragments, in the function
<code>fragments::add_fragment_siblings</code>. As of this writing this works by
looking at each directly-moved or assigned path P, and blindly
gathering all sibling fields of P (as well as siblings for the parents
of P, etc). After accumulating all such siblings, we filter out the
entries added as siblings of P that turned out to be
directly-referenced paths (or parents of directly referenced paths)
themselves, thus leaving the never-referenced "left-overs" as the only
thing left from the gathering step.</p>
<h2>Array structural fragments</h2>
<p>A special case of the structural fragments discussed above are
the elements of an array that has been passed by value, such as
the following:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p> <a-p>[</a-p><a-t>D</a-t><a-p>;</a-p> <a-co>10</a-co><a-p>],</a-p> <a-v>i</a-v><a-p>:</a-p> <a-t>i32</a-t><a-p>)</a-p> -&gt; <a-t>D</a-t> <a-p>{</a-p>
    a<a-p>[</a-p>i<a-p>]</a-p>
<a-p>}</a-p></pre>
<p>The above code moves a single element out of the input array <code>a</code>.
The remainder of the array still needs to be dropped; i.e., it
is a structural fragment. Note that after performing such a move,
it is not legal to read from the array <code>a</code>. There are a number of
ways to deal with this, but the important thing to note is that
the semantics needs to distinguish in some manner between a
fragment that is the <em>entire</em> array versus a fragment that represents
all-but-one element of the array.  A place where that distinction
would arise is the following:</p>
<pre class="language-rust"><a-k>fn</a-k> <a-f>foo</a-f><a-p>(</a-p><a-v>a</a-v><a-p>:</a-p> <a-p>[</a-p><a-t>D</a-t><a-p>;</a-p> <a-co>10</a-co><a-p>],</a-p> <a-v>b</a-v><a-p>:</a-p> <a-p>[</a-p><a-t>D</a-t><a-p>;</a-p> <a-co>10</a-co><a-p>],</a-p> <a-v>i</a-v><a-p>:</a-p> <a-t>i32</a-t><a-p>,</a-p> <a-v>t</a-v><a-p>:</a-p> <a-t>bool</a-t><a-p>)</a-p> -&gt; <a-t>D</a-t> <a-p>{</a-p>
    <a-k>if</a-k> t <a-p>{</a-p>
        a<a-p>[</a-p>i<a-p>]</a-p>
    <a-p>}</a-p> <a-k>else</a-k> <a-p>{</a-p>
        b<a-p>[</a-p>i<a-p>]</a-p>
    <a-p>}</a-p>

    <a-c>// When control exits, we will need either to drop all of `a`</a-c>
    <a-c>// and all-but-one of `b`, or to drop all of `b` and all-but-one</a-c>
    <a-c>// of `a`.</a-c>
<a-p>}</a-p></pre>
<p>There are a number of ways that the codegen backend could choose to
compile this (e.g. a <code>[bool; 10]</code> array for each such moved array;
or an <code>Option&lt;usize&gt;</code> for each moved array).  From the viewpoint of the
borrow-checker, the important thing is to record what kind of fragment
is implied by the relevant moves.</p>
<h1>Future work</h1>
<p>While writing up these docs, I encountered some rules I believe to be
stricter than necessary:</p>
<ul>
<li>
<p>I think restricting the <code>&amp;mut</code> P against moves and <code>ALIAS</code> is sufficient,
<code>MUTATE</code> and <code>CLAIM</code> are overkill. <code>MUTATE</code> was necessary when swap was
a built-in operator, but as it is not, it is implied by <code>CLAIM</code>,
and <code>CLAIM</code> is implied by <code>ALIAS</code>. The only net effect of this is an
extra error message in some cases, though.</p>
</li>
<li>
<p>I have not described how closures interact. Current code is unsound.
I am working on describing and implementing the fix.</p>
</li>
<li>
<p>If we wish, we can easily extend the move checking to allow finer-grained
tracking of what is initialized and what is not, enabling code like
this:</p>
<pre><code>a = x.f.g; // x.f.g is now uninitialized
// here, x and x.f are not usable, but x.f.h *is*
x.f.g = b; // x.f.g is not initialized
// now x, x.f, x.f.g, x.f.h are all usable
</code></pre>
<p>What needs to change here, most likely, is that the <code>moves</code> module
should record not only what paths are moved, but what expressions
are actual <em>uses</em>. For example, the reference to <code>x</code> in <code>x.f.g = b</code>
is not a true <em>use</em> in the sense that it requires <code>x</code> to be fully
initialized. This is in fact why the above code produces an error
today: the reference to <code>x</code> in <code>x.f.g = b</code> is considered illegal
because <code>x</code> is not fully initialized.</p>
</li>
</ul>
<p>There are also some possible refactorings:</p>
<ul>
<li>It might be nice to replace all loan paths with the MovePath mechanism,
since they allow lightweight comparison using an integer.</li>
</ul>
</section><div class="code-panel"><pre class="code src" data-hl="src/librustc_ast_borrowck/borrowck/README.md"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text">% The Borrow Checker</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 more or less obsolete, and will be removed</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; soon! The new system is described in 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"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text">[rustc guide]: https://rust-lang.github.io/rustc-guide/borrow_check.html</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text">This pass has the job of enforcing memory safety. This is a subtle</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text">topic. This docs aim to explain both the practice and the theory</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text">behind the borrow checker. They start with a high-level overview of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text">how it works, and then proceed to dive into the theoretical</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text">background. Finally, they go into detail on some of the more subtle</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text">aspects.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text"># Table of contents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text">These docs are long. Search for the section you are interested in.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text">- Overview</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text">- Formal model</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text">- Borrowing and loans</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text">- Moves and initialization</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text">- Drop flags and structural fragments</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text">- Future work</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text"># Overview</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 borrow checker checks one function at a time. It operates in two</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text">passes. The first pass, called `gather_loans`, walks over the function</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text">and identifies all of the places where borrows (e.g., `&amp;` expressions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text">and `ref` bindings) and moves (copies or captures of a linear value)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text">occur. It also tracks initialization sites. For each borrow and move,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text">it checks various basic safety conditions at this time (for example,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text">that the lifetime of the borrow doesn't exceed the lifetime of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text">value being borrowed, or that there is no move out of an `&amp;T`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text">referent).</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">It then uses the dataflow module to propagate which of those borrows</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text">may be in scope at each point in the procedure. A loan is considered</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text">to come into scope at the expression that caused it and to go out of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text">scope when the lifetime of the resulting reference expires.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text">Once the in-scope loans are known for each point in the program, the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text">borrow checker walks the IR again in a second pass called</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text">`check_loans`. This pass examines each statement and makes sure that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text">it is safe with respect to the in-scope loans.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"># Formal model</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text">Throughout the docs we'll consider a simple subset of Rust in which</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text">you can only borrow from places, defined like so:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text">P = x | P.f | *P</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text">```</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">Here `x` represents some variable, `P.f` is a field reference,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text">and `*P` is a pointer dereference. There is no auto-deref or other</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text">niceties. This means that if you have a type like:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text">struct S { f: i32 }</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"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L65" href="#L65">65</a><span class="code-text">and a variable `a: Box&lt;S&gt;`, then the rust expression `a.f` would correspond</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L66" href="#L66">66</a><span class="code-text">to an `P` of `(*a).f`.</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">Here is the formal grammar for the types we'll consider:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L69" href="#L69">69</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L70" href="#L70">70</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L71" href="#L71">71</a><span class="code-text">TY = i32 | bool | S&lt;'LT...&gt; | Box&lt;TY&gt; | &amp; 'LT MQ TY</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L72" href="#L72">72</a><span class="code-text">MQ = mut | imm</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L73" href="#L73">73</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L74" href="#L74">74</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L75" href="#L75">75</a><span class="code-text">Most of these types should be pretty self explanatory. Here `S` is a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L76" href="#L76">76</a><span class="code-text">struct name and we assume structs are declared like so:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L77" href="#L77">77</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L78" href="#L78">78</a><span class="code-text">```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">SD = struct S&lt;'LT...&gt; { (f: TY)... }</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"># Borrowing and loans</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L83" href="#L83">83</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L84" href="#L84">84</a><span class="code-text">## An intuitive explanation</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">### Issuing loans</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L87" href="#L87">87</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L88" href="#L88">88</a><span class="code-text">Now, imagine we had a program like this:</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">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L91" href="#L91">91</a><span class="code-text">struct Foo { f: i32, g: i32 }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L92" href="#L92">92</a><span class="code-text">...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L93" href="#L93">93</a><span class="code-text">'a: {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L94" href="#L94">94</a><span class="code-text">    let mut x: Box&lt;Foo&gt; = ...;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L95" href="#L95">95</a><span class="code-text">    let y = &amp;mut (*x).f;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L96" href="#L96">96</a><span class="code-text">    x = ...;</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">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L99" href="#L99">99</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L100" href="#L100">100</a><span class="code-text">This is of course dangerous because mutating `x` will free the old</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L101" href="#L101">101</a><span class="code-text">value and hence invalidate `y`. The borrow checker aims to prevent</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L102" href="#L102">102</a><span class="code-text">this sort of thing.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L103" href="#L103">103</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L104" href="#L104">104</a><span class="code-text">#### Loans and restrictions</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">The way the borrow checker works is that it analyzes each borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L107" href="#L107">107</a><span class="code-text">expression (in our simple model, that's stuff like `&amp;P`, though in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L108" href="#L108">108</a><span class="code-text">real life there are a few other cases to consider). For each borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L109" href="#L109">109</a><span class="code-text">expression, it computes a `Loan`, which is a data structure that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L110" href="#L110">110</a><span class="code-text">records (1) the value being borrowed, (2) the mutability and scope of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L111" href="#L111">111</a><span class="code-text">the borrow, and (3) a set of restrictions. In the code, `Loan` is a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L112" href="#L112">112</a><span class="code-text">struct defined in `middle::borrowck`. Formally, we define `LOAN` as</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L113" href="#L113">113</a><span class="code-text">follows:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L114" href="#L114">114</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L115" href="#L115">115</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L116" href="#L116">116</a><span class="code-text">LOAN = (P, LT, MQ, RESTRICTION*)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L117" href="#L117">117</a><span class="code-text">RESTRICTION = (P, ACTION*)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L118" href="#L118">118</a><span class="code-text">ACTION = MUTATE | CLAIM | FREEZE</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">Here the `LOAN` tuple defines the place `P` being borrowed; the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L122" href="#L122">122</a><span class="code-text">lifetime `LT` of that borrow; the mutability `MQ` of the borrow; and a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L123" href="#L123">123</a><span class="code-text">list of restrictions. The restrictions indicate actions which, if</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L124" href="#L124">124</a><span class="code-text">taken, could invalidate the loan and lead to type safety violations.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L125" href="#L125">125</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L126" href="#L126">126</a><span class="code-text">Each `RESTRICTION` is a pair of a restrictive place `P` (which will</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L127" href="#L127">127</a><span class="code-text">either be the path that was borrowed or some prefix of the path that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L128" href="#L128">128</a><span class="code-text">was borrowed) and a set of restricted actions.  There are three kinds</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L129" href="#L129">129</a><span class="code-text">of actions that may be restricted for the path `P`:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L130" href="#L130">130</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L131" href="#L131">131</a><span class="code-text">- `MUTATE` means that `P` cannot be assigned to;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L132" href="#L132">132</a><span class="code-text">- `CLAIM` means that the `P` cannot be borrowed mutably;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L133" href="#L133">133</a><span class="code-text">- `FREEZE` means that the `P` cannot be borrowed immutably;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L134" href="#L134">134</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L135" href="#L135">135</a><span class="code-text">Finally, it is never possible to move from a place that appears in a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L136" href="#L136">136</a><span class="code-text">restriction. This implies that the &quot;empty restriction&quot; `(P, [])`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L137" href="#L137">137</a><span class="code-text">which contains an empty set of actions, still has a purpose---it</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L138" href="#L138">138</a><span class="code-text">prevents moves from `P`. I chose not to make `MOVE` a fourth kind of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L139" href="#L139">139</a><span class="code-text">action because that would imply that sometimes moves are permitted</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L140" href="#L140">140</a><span class="code-text">from restricted values, which is not the case.</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">#### Example</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">To give you a better feeling for what kind of restrictions derived</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L145" href="#L145">145</a><span class="code-text">from a loan, let's look at the loan `L` that would be issued as a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L146" href="#L146">146</a><span class="code-text">result of the borrow `&amp;mut (*x).f` in the example above:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L147" href="#L147">147</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L148" href="#L148">148</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L149" href="#L149">149</a><span class="code-text">L = ((*x).f, 'a, mut, RS) where</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L150" href="#L150">150</a><span class="code-text">    RS = [((*x).f, [MUTATE, CLAIM, FREEZE]),</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L151" href="#L151">151</a><span class="code-text">          (*x, [MUTATE, CLAIM, FREEZE]),</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L152" href="#L152">152</a><span class="code-text">          (x, [MUTATE, CLAIM, FREEZE])]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L153" href="#L153">153</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L154" href="#L154">154</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L155" href="#L155">155</a><span class="code-text">The loan states that the expression `(*x).f` has been loaned as</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L156" href="#L156">156</a><span class="code-text">mutable for the lifetime `'a`. Because the loan is mutable, that means</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L157" href="#L157">157</a><span class="code-text">that the value `(*x).f` may be mutated via the newly created reference</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L158" href="#L158">158</a><span class="code-text">(and *only* via that pointer). This is reflected in the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L159" href="#L159">159</a><span class="code-text">restrictions `RS` that accompany the loan.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L160" href="#L160">160</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L161" href="#L161">161</a><span class="code-text">The first restriction `((*x).f, [MUTATE, CLAIM, FREEZE])` states that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L162" href="#L162">162</a><span class="code-text">the lender may not mutate, freeze, nor alias `(*x).f`. Mutation is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L163" href="#L163">163</a><span class="code-text">illegal because `(*x).f` is only supposed to be mutated via the new</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L164" href="#L164">164</a><span class="code-text">reference, not by mutating the original path `(*x).f`. Freezing is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L165" href="#L165">165</a><span class="code-text">illegal because the path now has an `&amp;mut` alias; so even if we the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L166" href="#L166">166</a><span class="code-text">lender were to consider `(*x).f` to be immutable, it might be mutated</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L167" href="#L167">167</a><span class="code-text">via this alias. They will be enforced for the lifetime `'a` of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L168" href="#L168">168</a><span class="code-text">loan. After the loan expires, the restrictions no longer apply.</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">The second restriction on `*x` is interesting because it does not</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L171" href="#L171">171</a><span class="code-text">apply to the path that was lent (`(*x).f`) but rather to a prefix of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L172" href="#L172">172</a><span class="code-text">the borrowed path. This is due to the rules of inherited mutability:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L173" href="#L173">173</a><span class="code-text">if the user were to assign to (or freeze) `*x`, they would indirectly</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L174" href="#L174">174</a><span class="code-text">overwrite (or freeze) `(*x).f`, and thus invalidate the reference</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L175" href="#L175">175</a><span class="code-text">that was created. In general it holds that when a path is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L176" href="#L176">176</a><span class="code-text">lent, restrictions are issued for all the owning prefixes of that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L177" href="#L177">177</a><span class="code-text">path. In this case, the path `*x` owns the path `(*x).f` and,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L178" href="#L178">178</a><span class="code-text">because `x` has ownership, the path `x` owns the path `*x`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L179" href="#L179">179</a><span class="code-text">Therefore, borrowing `(*x).f` yields restrictions on both</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L180" href="#L180">180</a><span class="code-text">`*x` and `x`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L181" href="#L181">181</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L182" href="#L182">182</a><span class="code-text">### Checking for illegal assignments, moves, and reborrows</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L183" href="#L183">183</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L184" href="#L184">184</a><span class="code-text">Once we have computed the loans introduced by each borrow, the borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L185" href="#L185">185</a><span class="code-text">checker uses a data flow propagation to compute the full set of loans</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L186" href="#L186">186</a><span class="code-text">in scope at each expression and then uses that set to decide whether</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L187" href="#L187">187</a><span class="code-text">that expression is legal.  Remember that the scope of loan is defined</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L188" href="#L188">188</a><span class="code-text">by its lifetime LT.  We sometimes say that a loan which is in-scope at</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L189" href="#L189">189</a><span class="code-text">a particular point is an &quot;outstanding loan&quot;, and the set of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L190" href="#L190">190</a><span class="code-text">restrictions included in those loans as the &quot;outstanding</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L191" href="#L191">191</a><span class="code-text">restrictions&quot;.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L192" href="#L192">192</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L193" href="#L193">193</a><span class="code-text">The kinds of expressions which in-scope loans can render illegal are:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L194" href="#L194">194</a><span class="code-text">- *assignments* (`lv = v`): illegal if there is an in-scope restriction</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L195" href="#L195">195</a><span class="code-text">  against mutating `lv`;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L196" href="#L196">196</a><span class="code-text">- *moves*: illegal if there is any in-scope restriction on `lv` at all;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L197" href="#L197">197</a><span class="code-text">- *mutable borrows* (`&amp;mut lv`): illegal there is an in-scope restriction</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L198" href="#L198">198</a><span class="code-text">  against claiming `lv`;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L199" href="#L199">199</a><span class="code-text">- *immutable borrows* (`&amp;lv`): illegal there is an in-scope restriction</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L200" href="#L200">200</a><span class="code-text">  against freezing `lv`.</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">## Formal rules</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">Now that we hopefully have some kind of intuitive feeling for how the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L205" href="#L205">205</a><span class="code-text">borrow checker works, let's look a bit more closely now at the precise</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L206" href="#L206">206</a><span class="code-text">conditions that it uses.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L207" href="#L207">207</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L208" href="#L208">208</a><span class="code-text">I will present the rules in a modified form of standard inference</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L209" href="#L209">209</a><span class="code-text">rules, which looks as follows:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L210" href="#L210">210</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L211" href="#L211">211</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L212" href="#L212">212</a><span class="code-text">PREDICATE(X, Y, Z)                  // Rule-Name</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L213" href="#L213">213</a><span class="code-text">  Condition 1</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L214" href="#L214">214</a><span class="code-text">  Condition 2</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L215" href="#L215">215</a><span class="code-text">  Condition 3</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L216" href="#L216">216</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L217" href="#L217">217</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L218" href="#L218">218</a><span class="code-text">The initial line states the predicate that is to be satisfied.  The</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L219" href="#L219">219</a><span class="code-text">indented lines indicate the conditions that must be met for the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L220" href="#L220">220</a><span class="code-text">predicate to be satisfied. The right-justified comment states the name</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L221" href="#L221">221</a><span class="code-text">of this rule: there are comments in the borrowck source referencing</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L222" href="#L222">222</a><span class="code-text">these names, so that you can cross reference to find the actual code</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L223" href="#L223">223</a><span class="code-text">that corresponds to the formal rule.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L224" href="#L224">224</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L225" href="#L225">225</a><span class="code-text">### Invariants</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L226" href="#L226">226</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L227" href="#L227">227</a><span class="code-text">I want to collect, at a high-level, the invariants the borrow checker</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L228" href="#L228">228</a><span class="code-text">maintains. I will give them names and refer to them throughout the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L229" href="#L229">229</a><span class="code-text">text. Together these invariants are crucial for the overall soundness</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L230" href="#L230">230</a><span class="code-text">of the system.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L231" href="#L231">231</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L232" href="#L232">232</a><span class="code-text">**Mutability requires uniqueness.** To mutate a path</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">**Unique mutability.** There is only one *usable* mutable path to any</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L235" href="#L235">235</a><span class="code-text">given memory at any given time. This implies that when claiming memory</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L236" href="#L236">236</a><span class="code-text">with an expression like `p = &amp;mut x`, the compiler must guarantee that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L237" href="#L237">237</a><span class="code-text">the borrowed value `x` can no longer be mutated so long as `p` is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L238" href="#L238">238</a><span class="code-text">live. (This is done via restrictions, read on.)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L239" href="#L239">239</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L240" href="#L240">240</a><span class="code-text">**.**</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L241" href="#L241">241</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L242" href="#L242">242</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L243" href="#L243">243</a><span class="code-text">### The `gather_loans` pass</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L244" href="#L244">244</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L245" href="#L245">245</a><span class="code-text">We start with the `gather_loans` pass, which walks the AST looking for</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L246" href="#L246">246</a><span class="code-text">borrows.  For each borrow, there are three bits of information: the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L247" href="#L247">247</a><span class="code-text">place `P` being borrowed and the mutability `MQ` and lifetime `LT`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L248" href="#L248">248</a><span class="code-text">of the resulting pointer. Given those, `gather_loans` applies four</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L249" href="#L249">249</a><span class="code-text">validity tests:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L250" href="#L250">250</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L251" href="#L251">251</a><span class="code-text">1. `MUTABILITY(P, MQ)`: The mutability of the reference is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L252" href="#L252">252</a><span class="code-text">compatible with the mutability of `P` (i.e., not borrowing immutable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L253" href="#L253">253</a><span class="code-text">data as mutable).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L254" href="#L254">254</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L255" href="#L255">255</a><span class="code-text">2. `ALIASABLE(P, MQ)`: The aliasability of the reference is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L256" href="#L256">256</a><span class="code-text">compatible with the aliasability of `P`. The goal is to prevent</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L257" href="#L257">257</a><span class="code-text">`&amp;mut` borrows of aliasability data.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L258" href="#L258">258</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L259" href="#L259">259</a><span class="code-text">3. `LIFETIME(P, LT, MQ)`: The lifetime of the borrow does not exceed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L260" href="#L260">260</a><span class="code-text">the lifetime of the value being borrowed.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L261" href="#L261">261</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L262" href="#L262">262</a><span class="code-text">4. `RESTRICTIONS(P, LT, ACTIONS) = RS`: This pass checks and computes the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L263" href="#L263">263</a><span class="code-text">restrictions to maintain memory safety. These are the restrictions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L264" href="#L264">264</a><span class="code-text">that will go into the final loan. We'll discuss in more detail below.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L265" href="#L265">265</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L266" href="#L266">266</a><span class="code-text">## Checking mutability</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L267" href="#L267">267</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L268" href="#L268">268</a><span class="code-text">Checking mutability is fairly straightforward. We just want to prevent</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L269" href="#L269">269</a><span class="code-text">immutable data from being borrowed as mutable. Note that it is ok to borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L270" href="#L270">270</a><span class="code-text">mutable data as immutable, since that is simply a freeze. The judgement</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L271" href="#L271">271</a><span class="code-text">`MUTABILITY(P, MQ)` means the mutability of `P` is compatible with a borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L272" href="#L272">272</a><span class="code-text">of mutability `MQ`. The Rust code corresponding to this predicate is the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L273" href="#L273">273</a><span class="code-text">function `check_mutability` in `middle::borrowck::gather_loans`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L274" href="#L274">274</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L275" href="#L275">275</a><span class="code-text">### Checking mutability of variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L276" href="#L276">276</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L277" href="#L277">277</a><span class="code-text">*Code pointer:* Function `check_mutability()` in `gather_loans/mod.rs`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L278" href="#L278">278</a><span class="code-text">but also the code in `mem_categorization`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L279" href="#L279">279</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L280" href="#L280">280</a><span class="code-text">Let's begin with the rules for variables, which state that if a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L281" href="#L281">281</a><span class="code-text">variable is declared as mutable, it may be borrowed any which way, but</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L282" href="#L282">282</a><span class="code-text">otherwise the variable must be borrowed as immutable:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L283" href="#L283">283</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L284" href="#L284">284</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L285" href="#L285">285</a><span class="code-text">MUTABILITY(X, MQ)                   // M-Var-Mut</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L286" href="#L286">286</a><span class="code-text">  DECL(X) = mut</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L287" href="#L287">287</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L288" href="#L288">288</a><span class="code-text">MUTABILITY(X, imm)                  // M-Var-Imm</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L289" href="#L289">289</a><span class="code-text">  DECL(X) = imm</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L290" href="#L290">290</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L291" href="#L291">291</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L292" href="#L292">292</a><span class="code-text">### Checking mutability of owned content</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L293" href="#L293">293</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L294" href="#L294">294</a><span class="code-text">Fields and boxes inherit their mutability from</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L295" href="#L295">295</a><span class="code-text">their base expressions, so both of their rules basically</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L296" href="#L296">296</a><span class="code-text">delegate the check to the base expression `P`:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L297" href="#L297">297</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L298" href="#L298">298</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L299" href="#L299">299</a><span class="code-text">MUTABILITY(P.f, MQ)                // M-Field</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L300" href="#L300">300</a><span class="code-text">  MUTABILITY(P, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L301" href="#L301">301</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L302" href="#L302">302</a><span class="code-text">MUTABILITY(*P, MQ)                 // M-Deref-Unique</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L303" href="#L303">303</a><span class="code-text">  TYPE(P) = Box&lt;Ty&gt;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L304" href="#L304">304</a><span class="code-text">  MUTABILITY(P, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L305" href="#L305">305</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L306" href="#L306">306</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L307" href="#L307">307</a><span class="code-text">### Checking mutability of immutable pointer types</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L308" href="#L308">308</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L309" href="#L309">309</a><span class="code-text">Immutable pointer types like `&amp;T` can only</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L310" href="#L310">310</a><span class="code-text">be borrowed if MQ is immutable:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L311" href="#L311">311</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L312" href="#L312">312</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L313" href="#L313">313</a><span class="code-text">MUTABILITY(*P, imm)               // M-Deref-Borrowed-Imm</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L314" href="#L314">314</a><span class="code-text">  TYPE(P) = &amp;Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L315" href="#L315">315</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L316" href="#L316">316</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L317" href="#L317">317</a><span class="code-text">### Checking mutability of mutable pointer types</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L318" href="#L318">318</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L319" href="#L319">319</a><span class="code-text">`&amp;mut T` can be frozen, so it is acceptable to borrow it as either imm or mut:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L320" href="#L320">320</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L321" href="#L321">321</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L322" href="#L322">322</a><span class="code-text">MUTABILITY(*P, MQ)                 // M-Deref-Borrowed-Mut</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L323" href="#L323">323</a><span class="code-text">  TYPE(P) = &amp;mut Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L324" href="#L324">324</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L325" href="#L325">325</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L326" href="#L326">326</a><span class="code-text">## Checking aliasability</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L327" href="#L327">327</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L328" href="#L328">328</a><span class="code-text">The goal of the aliasability check is to ensure that we never permit `&amp;mut`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L329" href="#L329">329</a><span class="code-text">borrows of aliasable data. The judgement `ALIASABLE(P, MQ)` means the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L330" href="#L330">330</a><span class="code-text">aliasability of `P` is compatible with a borrow of mutability `MQ`. The Rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L331" href="#L331">331</a><span class="code-text">code corresponding to this predicate is the function `check_aliasability()` in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L332" href="#L332">332</a><span class="code-text">`middle::borrowck::gather_loans`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L333" href="#L333">333</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L334" href="#L334">334</a><span class="code-text">### Checking aliasability of variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L335" href="#L335">335</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L336" href="#L336">336</a><span class="code-text">Local variables are never aliasable as they are accessible only within</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L337" href="#L337">337</a><span class="code-text">the stack frame.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L338" href="#L338">338</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L339" href="#L339">339</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L340" href="#L340">340</a><span class="code-text">    ALIASABLE(X, MQ)                   // M-Var-Mut</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L341" href="#L341">341</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L342" href="#L342">342</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L343" href="#L343">343</a><span class="code-text">### Checking aliasable of owned content</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L344" href="#L344">344</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L345" href="#L345">345</a><span class="code-text">Owned content is aliasable if it is found in an aliasable location:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L346" href="#L346">346</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L347" href="#L347">347</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L348" href="#L348">348</a><span class="code-text">ALIASABLE(P.f, MQ)                // M-Field</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L349" href="#L349">349</a><span class="code-text">  ALIASABLE(P, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L350" href="#L350">350</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L351" href="#L351">351</a><span class="code-text">ALIASABLE(*P, MQ)                 // M-Deref-Unique</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L352" href="#L352">352</a><span class="code-text">  ALIASABLE(P, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L353" href="#L353">353</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L354" href="#L354">354</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L355" href="#L355">355</a><span class="code-text">### Checking aliasability of immutable pointer types</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L356" href="#L356">356</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L357" href="#L357">357</a><span class="code-text">Immutable pointer types like `&amp;T` are aliasable, and hence can only be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L358" href="#L358">358</a><span class="code-text">borrowed immutably:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L359" href="#L359">359</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L360" href="#L360">360</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L361" href="#L361">361</a><span class="code-text">ALIASABLE(*P, imm)                // M-Deref-Borrowed-Imm</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L362" href="#L362">362</a><span class="code-text">  TYPE(P) = &amp;Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L363" href="#L363">363</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L364" href="#L364">364</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L365" href="#L365">365</a><span class="code-text">### Checking aliasability of mutable pointer types</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L366" href="#L366">366</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L367" href="#L367">367</a><span class="code-text">`&amp;mut T` can be frozen, so it is acceptable to borrow it as either imm or mut:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L368" href="#L368">368</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L369" href="#L369">369</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L370" href="#L370">370</a><span class="code-text">ALIASABLE(*P, MQ)                 // M-Deref-Borrowed-Mut</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L371" href="#L371">371</a><span class="code-text">  TYPE(P) = &amp;mut Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L372" href="#L372">372</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L373" href="#L373">373</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L374" href="#L374">374</a><span class="code-text">## Checking lifetime</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L375" href="#L375">375</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L376" href="#L376">376</a><span class="code-text">These rules aim to ensure that no data is borrowed for a scope that exceeds</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L377" href="#L377">377</a><span class="code-text">its lifetime. These two computations wind up being intimately related.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L378" href="#L378">378</a><span class="code-text">Formally, we define a predicate `LIFETIME(P, LT, MQ)`, which states that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L379" href="#L379">379</a><span class="code-text">&quot;the place `P` can be safely borrowed for the lifetime `LT` with mutability</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L380" href="#L380">380</a><span class="code-text">`MQ`&quot;. The Rust code corresponding to this predicate is the module</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L381" href="#L381">381</a><span class="code-text">`middle::borrowck::gather_loans::lifetime`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L382" href="#L382">382</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L383" href="#L383">383</a><span class="code-text">### Checking lifetime of variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L384" href="#L384">384</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L385" href="#L385">385</a><span class="code-text">The rule for variables states that a variable can only be borrowed a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L386" href="#L386">386</a><span class="code-text">lifetime `LT` that is a subregion of the variable's scope:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L387" href="#L387">387</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L388" href="#L388">388</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L389" href="#L389">389</a><span class="code-text">LIFETIME(X, LT, MQ)                 // L-Local</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L390" href="#L390">390</a><span class="code-text">  LT &lt;= block where X is declared</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L391" href="#L391">391</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L392" href="#L392">392</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L393" href="#L393">393</a><span class="code-text">### Checking lifetime for owned content</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L394" href="#L394">394</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L395" href="#L395">395</a><span class="code-text">The lifetime of a field or box is the same as the lifetime</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L396" href="#L396">396</a><span class="code-text">of its owner:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L397" href="#L397">397</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L398" href="#L398">398</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L399" href="#L399">399</a><span class="code-text">LIFETIME(P.f, LT, MQ)              // L-Field</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L400" href="#L400">400</a><span class="code-text">  LIFETIME(P, LT, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L401" href="#L401">401</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L402" href="#L402">402</a><span class="code-text">LIFETIME(*P, LT, MQ)               // L-Deref-Send</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L403" href="#L403">403</a><span class="code-text">  TYPE(P) = Box&lt;Ty&gt;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L404" href="#L404">404</a><span class="code-text">  LIFETIME(P, LT, MQ)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L405" href="#L405">405</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L406" href="#L406">406</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L407" href="#L407">407</a><span class="code-text">### Checking lifetime for derefs of references</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L408" href="#L408">408</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L409" href="#L409">409</a><span class="code-text">References have a lifetime `LT'` associated with them.  The</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L410" href="#L410">410</a><span class="code-text">data they point at has been guaranteed to be valid for at least this</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L411" href="#L411">411</a><span class="code-text">lifetime. Therefore, the borrow is valid so long as the lifetime `LT`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L412" href="#L412">412</a><span class="code-text">of the borrow is shorter than the lifetime `LT'` of the pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L413" href="#L413">413</a><span class="code-text">itself:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L414" href="#L414">414</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L415" href="#L415">415</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L416" href="#L416">416</a><span class="code-text">LIFETIME(*P, LT, MQ)               // L-Deref-Borrowed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L417" href="#L417">417</a><span class="code-text">  TYPE(P) = &amp;LT' Ty OR &amp;LT' mut Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L418" href="#L418">418</a><span class="code-text">  LT &lt;= LT'</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L419" href="#L419">419</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L420" href="#L420">420</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L421" href="#L421">421</a><span class="code-text">## Computing the restrictions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L422" href="#L422">422</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L423" href="#L423">423</a><span class="code-text">The final rules govern the computation of *restrictions*, meaning that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L424" href="#L424">424</a><span class="code-text">we compute the set of actions that will be illegal for the life of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L425" href="#L425">425</a><span class="code-text">loan. The predicate is written `RESTRICTIONS(P, LT, ACTIONS) =</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L426" href="#L426">426</a><span class="code-text">RESTRICTION*`, which can be read &quot;in order to prevent `ACTIONS` from</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L427" href="#L427">427</a><span class="code-text">occurring on `P`, the restrictions `RESTRICTION*` must be respected</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L428" href="#L428">428</a><span class="code-text">for the lifetime of the loan&quot;.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L429" href="#L429">429</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L430" href="#L430">430</a><span class="code-text">Note that there is an initial set of restrictions: these restrictions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L431" href="#L431">431</a><span class="code-text">are computed based on the kind of borrow:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L432" href="#L432">432</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L433" href="#L433">433</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L434" href="#L434">434</a><span class="code-text">&amp;mut P =&gt;   RESTRICTIONS(P, LT, MUTATE|CLAIM|FREEZE)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L435" href="#L435">435</a><span class="code-text">&amp;P =&gt;       RESTRICTIONS(P, LT, MUTATE|CLAIM)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L436" href="#L436">436</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L437" href="#L437">437</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L438" href="#L438">438</a><span class="code-text">The reasoning here is that a mutable borrow must be the only writer,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L439" href="#L439">439</a><span class="code-text">therefore it prevents other writes (`MUTATE`), mutable borrows</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L440" href="#L440">440</a><span class="code-text">(`CLAIM`), and immutable borrows (`FREEZE`). An immutable borrow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L441" href="#L441">441</a><span class="code-text">permits other immutable borrows but forbids writes and mutable borrows.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L442" href="#L442">442</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L443" href="#L443">443</a><span class="code-text">### Restrictions for loans of a local variable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L444" href="#L444">444</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L445" href="#L445">445</a><span class="code-text">The simplest case is a borrow of a local variable `X`:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L446" href="#L446">446</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L447" href="#L447">447</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L448" href="#L448">448</a><span class="code-text">RESTRICTIONS(X, LT, ACTIONS) = (X, ACTIONS)            // R-Variable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L449" href="#L449">449</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L450" href="#L450">450</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L451" href="#L451">451</a><span class="code-text">In such cases we just record the actions that are not permitted.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L452" href="#L452">452</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L453" href="#L453">453</a><span class="code-text">### Restrictions for loans of fields</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L454" href="#L454">454</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L455" href="#L455">455</a><span class="code-text">Restricting a field is the same as restricting the owner of that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L456" href="#L456">456</a><span class="code-text">field:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L457" href="#L457">457</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L458" href="#L458">458</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L459" href="#L459">459</a><span class="code-text">RESTRICTIONS(P.f, LT, ACTIONS) = RS, (P.f, ACTIONS)  // R-Field</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L460" href="#L460">460</a><span class="code-text">  RESTRICTIONS(P, LT, ACTIONS) = RS</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L461" href="#L461">461</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L462" href="#L462">462</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L463" href="#L463">463</a><span class="code-text">The reasoning here is as follows. If the field must not be mutated,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L464" href="#L464">464</a><span class="code-text">then you must not mutate the owner of the field either, since that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L465" href="#L465">465</a><span class="code-text">would indirectly modify the field. Similarly, if the field cannot be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L466" href="#L466">466</a><span class="code-text">frozen or aliased, we cannot allow the owner to be frozen or aliased,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L467" href="#L467">467</a><span class="code-text">since doing so indirectly freezes/aliases the field. This is the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L468" href="#L468">468</a><span class="code-text">origin of inherited mutability.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L469" href="#L469">469</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L470" href="#L470">470</a><span class="code-text">### Restrictions for loans of owned referents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L471" href="#L471">471</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L472" href="#L472">472</a><span class="code-text">Because the mutability of owned referents is inherited, restricting an</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L473" href="#L473">473</a><span class="code-text">owned referent is similar to restricting a field, in that it implies</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L474" href="#L474">474</a><span class="code-text">restrictions on the pointer. However, boxes have an important</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L475" href="#L475">475</a><span class="code-text">twist: if the owner `P` is mutated, that causes the owned referent</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L476" href="#L476">476</a><span class="code-text">`*P` to be freed! So whenever an owned referent `*P` is borrowed, we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L477" href="#L477">477</a><span class="code-text">must prevent the box `P` from being mutated, which means</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L478" href="#L478">478</a><span class="code-text">that we always add `MUTATE` and `CLAIM` to the restriction set imposed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L479" href="#L479">479</a><span class="code-text">on `P`:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L480" href="#L480">480</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L481" href="#L481">481</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L482" href="#L482">482</a><span class="code-text">RESTRICTIONS(*P, LT, ACTIONS) = RS, (*P, ACTIONS)    // R-Deref-Send-Pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L483" href="#L483">483</a><span class="code-text">  TYPE(P) = Box&lt;Ty&gt;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L484" href="#L484">484</a><span class="code-text">  RESTRICTIONS(P, LT, ACTIONS|MUTATE|CLAIM) = RS</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L485" href="#L485">485</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L486" href="#L486">486</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L487" href="#L487">487</a><span class="code-text">### Restrictions for loans of immutable borrowed referents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L488" href="#L488">488</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L489" href="#L489">489</a><span class="code-text">Immutable borrowed referents are freely aliasable, meaning that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L490" href="#L490">490</a><span class="code-text">the compiler does not prevent you from copying the pointer.  This</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L491" href="#L491">491</a><span class="code-text">implies that issuing restrictions is useless. We might prevent the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L492" href="#L492">492</a><span class="code-text">user from acting on `*P` itself, but there could be another path</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L493" href="#L493">493</a><span class="code-text">`*P1` that refers to the exact same memory, and we would not be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L494" href="#L494">494</a><span class="code-text">restricting that path. Therefore, the rule for `&amp;Ty` pointers</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L495" href="#L495">495</a><span class="code-text">always returns an empty set of restrictions, and it only permits</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L496" href="#L496">496</a><span class="code-text">restricting `MUTATE` and `CLAIM` actions:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L497" href="#L497">497</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L498" href="#L498">498</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L499" href="#L499">499</a><span class="code-text">RESTRICTIONS(*P, LT, ACTIONS) = []                    // R-Deref-Imm-Borrowed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L500" href="#L500">500</a><span class="code-text">  TYPE(P) = &amp;LT' Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L501" href="#L501">501</a><span class="code-text">  LT &lt;= LT'                                            // (1)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L502" href="#L502">502</a><span class="code-text">  ACTIONS subset of [MUTATE, CLAIM]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L503" href="#L503">503</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L504" href="#L504">504</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L505" href="#L505">505</a><span class="code-text">The reason that we can restrict `MUTATE` and `CLAIM` actions even</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L506" href="#L506">506</a><span class="code-text">without a restrictions list is that it is never legal to mutate nor to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L507" href="#L507">507</a><span class="code-text">borrow mutably the contents of a `&amp;Ty` pointer. In other words,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L508" href="#L508">508</a><span class="code-text">those restrictions are already inherent in the type.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L509" href="#L509">509</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L510" href="#L510">510</a><span class="code-text">Clause (1) in the rule for `&amp;Ty` deserves mention. Here I</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L511" href="#L511">511</a><span class="code-text">specify that the lifetime of the loan must be less than the lifetime</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L512" href="#L512">512</a><span class="code-text">of the `&amp;Ty` pointer. In simple cases, this clause is redundant, since</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L513" href="#L513">513</a><span class="code-text">the `LIFETIME()` function will already enforce the required rule:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L514" href="#L514">514</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L515" href="#L515">515</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L516" href="#L516">516</a><span class="code-text">fn foo(point: &amp;'a Point) -&gt; &amp;'static i32 {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L517" href="#L517">517</a><span class="code-text">    &amp;point.x // Error</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L518" href="#L518">518</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L519" href="#L519">519</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L520" href="#L520">520</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L521" href="#L521">521</a><span class="code-text">The above example fails to compile both because of clause (1) above</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L522" href="#L522">522</a><span class="code-text">but also by the basic `LIFETIME()` check. However, in more advanced</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L523" href="#L523">523</a><span class="code-text">examples involving multiple nested pointers, clause (1) is needed:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L524" href="#L524">524</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L525" href="#L525">525</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L526" href="#L526">526</a><span class="code-text">fn foo(point: &amp;'a &amp;'b mut Point) -&gt; &amp;'b i32 {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L527" href="#L527">527</a><span class="code-text">    &amp;point.x // Error</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L528" href="#L528">528</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L529" href="#L529">529</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L530" href="#L530">530</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L531" href="#L531">531</a><span class="code-text">The `LIFETIME` rule here would accept `'b` because, in fact, the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L532" href="#L532">532</a><span class="code-text">*memory is* guaranteed to remain valid (i.e., not be freed) for the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L533" href="#L533">533</a><span class="code-text">lifetime `'b`, since the `&amp;mut` pointer is valid for `'b`. However, we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L534" href="#L534">534</a><span class="code-text">are returning an immutable reference, so we need the memory to be both</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L535" href="#L535">535</a><span class="code-text">valid and immutable. Even though `point.x` is referenced by an `&amp;mut`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L536" href="#L536">536</a><span class="code-text">pointer, it can still be considered immutable so long as that `&amp;mut`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L537" href="#L537">537</a><span class="code-text">pointer is found in an aliased location. That means the memory is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L538" href="#L538">538</a><span class="code-text">guaranteed to be *immutable* for the lifetime of the `&amp;` pointer,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L539" href="#L539">539</a><span class="code-text">which is only `'a`, not `'b`. Hence this example yields an error.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L540" href="#L540">540</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L541" href="#L541">541</a><span class="code-text">As a final twist, consider the case of two nested *immutable*</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L542" href="#L542">542</a><span class="code-text">pointers, rather than a mutable pointer within an immutable one:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L543" href="#L543">543</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L544" href="#L544">544</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L545" href="#L545">545</a><span class="code-text">fn foo(point: &amp;'a &amp;'b Point) -&gt; &amp;'b i32 {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L546" href="#L546">546</a><span class="code-text">    &amp;point.x // OK</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L547" href="#L547">547</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L548" href="#L548">548</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L549" href="#L549">549</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L550" href="#L550">550</a><span class="code-text">This function is legal. The reason for this is that the inner pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L551" href="#L551">551</a><span class="code-text">(`*point : &amp;'b Point`) is enough to guarantee the memory is immutable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L552" href="#L552">552</a><span class="code-text">and valid for the lifetime `'b`.  This is reflected in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L553" href="#L553">553</a><span class="code-text">`RESTRICTIONS()` by the fact that we do not recurse (i.e., we impose</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L554" href="#L554">554</a><span class="code-text">no restrictions on `P`, which in this particular case is the pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L555" href="#L555">555</a><span class="code-text">`point : &amp;'a &amp;'b Point`).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L556" href="#L556">556</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L557" href="#L557">557</a><span class="code-text">#### Why both `LIFETIME()` and `RESTRICTIONS()`?</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L558" href="#L558">558</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L559" href="#L559">559</a><span class="code-text">Given the previous text, it might seem that `LIFETIME` and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L560" href="#L560">560</a><span class="code-text">`RESTRICTIONS` should be folded together into one check, but there is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L561" href="#L561">561</a><span class="code-text">a reason that they are separated. They answer separate concerns.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L562" href="#L562">562</a><span class="code-text">The rules pertaining to `LIFETIME` exist to ensure that we don't</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L563" href="#L563">563</a><span class="code-text">create a borrowed pointer that outlives the memory it points at. So</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L564" href="#L564">564</a><span class="code-text">`LIFETIME` prevents a function like this:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L565" href="#L565">565</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L566" href="#L566">566</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L567" href="#L567">567</a><span class="code-text">fn get_1&lt;'a&gt;() -&gt; &amp;'a i32 {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L568" href="#L568">568</a><span class="code-text">    let x = 1;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L569" href="#L569">569</a><span class="code-text">    &amp;x</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L570" href="#L570">570</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L571" href="#L571">571</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L572" href="#L572">572</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L573" href="#L573">573</a><span class="code-text">Here we would be returning a pointer into the stack. Clearly bad.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L574" href="#L574">574</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L575" href="#L575">575</a><span class="code-text">However, the `RESTRICTIONS` rules are more concerned with how memory</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L576" href="#L576">576</a><span class="code-text">is used. The example above doesn't generate an error according to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L577" href="#L577">577</a><span class="code-text">`RESTRICTIONS` because, for local variables, we don't require that the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L578" href="#L578">578</a><span class="code-text">loan lifetime be a subset of the local variable lifetime. The idea</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L579" href="#L579">579</a><span class="code-text">here is that we *can* guarantee that `x` is not (e.g.) mutated for the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L580" href="#L580">580</a><span class="code-text">lifetime `'a`, even though `'a` exceeds the function body and thus</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L581" href="#L581">581</a><span class="code-text">involves unknown code in the caller -- after all, `x` ceases to exist</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L582" href="#L582">582</a><span class="code-text">after we return and hence the remaining code in `'a` cannot possibly</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L583" href="#L583">583</a><span class="code-text">mutate it. This distinction is important for type checking functions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L584" href="#L584">584</a><span class="code-text">like this one:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L585" href="#L585">585</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L586" href="#L586">586</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L587" href="#L587">587</a><span class="code-text">fn inc_and_get&lt;'a&gt;(p: &amp;'a mut Point) -&gt; &amp;'a i32 {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L588" href="#L588">588</a><span class="code-text">    p.x += 1;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L589" href="#L589">589</a><span class="code-text">    &amp;p.x</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L590" href="#L590">590</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L591" href="#L591">591</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L592" href="#L592">592</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L593" href="#L593">593</a><span class="code-text">In this case, we take in a `&amp;mut` and return a frozen borrowed pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L594" href="#L594">594</a><span class="code-text">with the same lifetime. So long as the lifetime of the returned value</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L595" href="#L595">595</a><span class="code-text">doesn't exceed the lifetime of the `&amp;mut` we receive as input, this is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L596" href="#L596">596</a><span class="code-text">fine, though it may seem surprising at first (it surprised me when I</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L597" href="#L597">597</a><span class="code-text">first worked it through). After all, we're guaranteeing that `*p`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L598" href="#L598">598</a><span class="code-text">won't be mutated for the lifetime `'a`, even though we can't &quot;see&quot; the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L599" href="#L599">599</a><span class="code-text">entirety of the code during that lifetime, since some of it occurs in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L600" href="#L600">600</a><span class="code-text">our caller. But we *do* know that nobody can mutate `*p` except</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L601" href="#L601">601</a><span class="code-text">through `p`. So if we don't mutate `*p` and we don't return `p`, then</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L602" href="#L602">602</a><span class="code-text">we know that the right to mutate `*p` has been lost to our caller --</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L603" href="#L603">603</a><span class="code-text">in terms of capability, the caller passed in the ability to mutate</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L604" href="#L604">604</a><span class="code-text">`*p`, and we never gave it back. (Note that we can't return `p` while</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L605" href="#L605">605</a><span class="code-text">`*p` is borrowed since that would be a move of `p`, as `&amp;mut` pointers</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L606" href="#L606">606</a><span class="code-text">are affine.)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L607" href="#L607">607</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L608" href="#L608">608</a><span class="code-text">### Restrictions for loans of mutable borrowed referents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L609" href="#L609">609</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L610" href="#L610">610</a><span class="code-text">Mutable borrowed pointers are guaranteed to be the only way to mutate</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L611" href="#L611">611</a><span class="code-text">their referent. This permits us to take greater license with them; for</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L612" href="#L612">612</a><span class="code-text">example, the referent can be frozen simply be ensuring that we do not</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L613" href="#L613">613</a><span class="code-text">use the original pointer to perform mutate. Similarly, we can allow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L614" href="#L614">614</a><span class="code-text">the referent to be claimed, so long as the original pointer is unused</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L615" href="#L615">615</a><span class="code-text">while the new claimant is live.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L616" href="#L616">616</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L617" href="#L617">617</a><span class="code-text">The rule for mutable borrowed pointers is as follows:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L618" href="#L618">618</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L619" href="#L619">619</a><span class="code-text">```text</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L620" href="#L620">620</a><span class="code-text">RESTRICTIONS(*P, LT, ACTIONS) = RS, (*P, ACTIONS)    // R-Deref-Mut-Borrowed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L621" href="#L621">621</a><span class="code-text">  TYPE(P) = &amp;LT' mut Ty</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L622" href="#L622">622</a><span class="code-text">  LT &lt;= LT'                                            // (1)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L623" href="#L623">623</a><span class="code-text">  RESTRICTIONS(P, LT, ACTIONS) = RS                   // (2)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L624" href="#L624">624</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L625" href="#L625">625</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L626" href="#L626">626</a><span class="code-text">Let's examine the two numbered clauses:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L627" href="#L627">627</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L628" href="#L628">628</a><span class="code-text">Clause (1) specifies that the lifetime of the loan (`LT`) cannot</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L629" href="#L629">629</a><span class="code-text">exceed the lifetime of the `&amp;mut` pointer (`LT'`). The reason for this</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L630" href="#L630">630</a><span class="code-text">is that the `&amp;mut` pointer is guaranteed to be the only legal way to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L631" href="#L631">631</a><span class="code-text">mutate its referent -- but only for the lifetime `LT'`.  After that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L632" href="#L632">632</a><span class="code-text">lifetime, the loan on the referent expires and hence the data may be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L633" href="#L633">633</a><span class="code-text">modified by its owner again. This implies that we are only able to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L634" href="#L634">634</a><span class="code-text">guarantee that the referent will not be modified or aliased for a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L635" href="#L635">635</a><span class="code-text">maximum of `LT'`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L636" href="#L636">636</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L637" href="#L637">637</a><span class="code-text">Here is a concrete example of a bug this rule prevents:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L638" href="#L638">638</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L639" href="#L639">639</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L640" href="#L640">640</a><span class="code-text">// Test region-reborrow-from-shorter-mut-ref.rs:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L641" href="#L641">641</a><span class="code-text">fn copy_borrowed_ptr&lt;'a,'b,T&gt;(x: &amp;'a mut &amp;'b mut T) -&gt; &amp;'b mut T {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L642" href="#L642">642</a><span class="code-text">    &amp;mut **p // ERROR due to clause (1)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L643" href="#L643">643</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L644" href="#L644">644</a><span class="code-text">fn main() {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L645" href="#L645">645</a><span class="code-text">    let mut x = 1;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L646" href="#L646">646</a><span class="code-text">    let mut y = &amp;mut x; // &lt;-'b-----------------------------+</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L647" href="#L647">647</a><span class="code-text">    //      +-'a--------------------+                       |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L648" href="#L648">648</a><span class="code-text">    //      v                       v                       |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L649" href="#L649">649</a><span class="code-text">    let z = copy_borrowed_ptr(&amp;mut y); // y is lent         |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L650" href="#L650">650</a><span class="code-text">    *y += 1; // Here y==z, so both should not be usable...  |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L651" href="#L651">651</a><span class="code-text">    *z += 1; // ...and yet they would be, but for clause 1. |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L652" href="#L652">652</a><span class="code-text">} // &lt;------------------------------------------------------+</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L653" href="#L653">653</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L654" href="#L654">654</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L655" href="#L655">655</a><span class="code-text">Clause (2) propagates the restrictions on the referent to the pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L656" href="#L656">656</a><span class="code-text">itself. This is the same as with an box, though the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L657" href="#L657">657</a><span class="code-text">reasoning is mildly different. The basic goal in all cases is to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L658" href="#L658">658</a><span class="code-text">prevent the user from establishing another route to the same data. To</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L659" href="#L659">659</a><span class="code-text">see what I mean, let's examine various cases of what can go wrong and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L660" href="#L660">660</a><span class="code-text">show how it is prevented.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L661" href="#L661">661</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L662" href="#L662">662</a><span class="code-text">**Example danger 1: Moving the base pointer.** One of the simplest</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L663" href="#L663">663</a><span class="code-text">ways to violate the rules is to move the base pointer to a new name</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L664" href="#L664">664</a><span class="code-text">and access it via that new name, thus bypassing the restrictions on</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L665" href="#L665">665</a><span class="code-text">the old name. Here is an example:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L666" href="#L666">666</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L667" href="#L667">667</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L668" href="#L668">668</a><span class="code-text">// src/test/compile-fail/borrowck-move-mut-base-ptr.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L669" href="#L669">669</a><span class="code-text">fn foo(t0: &amp;mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L670" href="#L670">670</a><span class="code-text">    let p: &amp;i32 = &amp;*t0; // Freezes `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L671" href="#L671">671</a><span class="code-text">    let t1 = t0;        //~ ERROR cannot move out of `t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L672" href="#L672">672</a><span class="code-text">    *t1 = 22;           // OK, not a write through `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L673" href="#L673">673</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L674" href="#L674">674</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L675" href="#L675">675</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L676" href="#L676">676</a><span class="code-text">Remember that `&amp;mut` pointers are linear, and hence `let t1 = t0` is a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L677" href="#L677">677</a><span class="code-text">move of `t0` -- or would be, if it were legal. Instead, we get an</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L678" href="#L678">678</a><span class="code-text">error, because clause (2) imposes restrictions on `P` (`t0`, here),</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L679" href="#L679">679</a><span class="code-text">and any restrictions on a path make it impossible to move from that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L680" href="#L680">680</a><span class="code-text">path.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L681" href="#L681">681</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L682" href="#L682">682</a><span class="code-text">**Example danger 2: Claiming the base pointer.** Another possible</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L683" href="#L683">683</a><span class="code-text">danger is to mutably borrow the base path. This can lead to two bad</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L684" href="#L684">684</a><span class="code-text">scenarios. The most obvious is that the mutable borrow itself becomes</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L685" href="#L685">685</a><span class="code-text">another path to access the same data, as shown here:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L686" href="#L686">686</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L687" href="#L687">687</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L688" href="#L688">688</a><span class="code-text">// src/test/compile-fail/borrowck-mut-borrow-of-mut-base-ptr.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L689" href="#L689">689</a><span class="code-text">fn foo&lt;'a&gt;(mut t0: &amp;'a mut i32,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L690" href="#L690">690</a><span class="code-text">           mut t1: &amp;'a mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L691" href="#L691">691</a><span class="code-text">    let p: &amp;i32 = &amp;*t0;     // Freezes `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L692" href="#L692">692</a><span class="code-text">    let mut t2 = &amp;mut t0;   //~ ERROR cannot borrow `t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L693" href="#L693">693</a><span class="code-text">    **t2 += 1;              // Mutates `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L694" href="#L694">694</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L695" href="#L695">695</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L696" href="#L696">696</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L697" href="#L697">697</a><span class="code-text">In this example, `**t2` is the same memory as `*t0`. Because `t2` is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L698" href="#L698">698</a><span class="code-text">an `&amp;mut` pointer, `**t2` is a unique path and hence it would be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L699" href="#L699">699</a><span class="code-text">possible to mutate `**t2` even though that memory was supposed to be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L700" href="#L700">700</a><span class="code-text">frozen by the creation of `p`. However, an error is reported -- the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L701" href="#L701">701</a><span class="code-text">reason is that the freeze `&amp;*t0` will restrict claims and mutation</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L702" href="#L702">702</a><span class="code-text">against `*t0` which, by clause 2, in turn prevents claims and mutation</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L703" href="#L703">703</a><span class="code-text">of `t0`. Hence the claim `&amp;mut t0` is illegal.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L704" href="#L704">704</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L705" href="#L705">705</a><span class="code-text">Another danger with an `&amp;mut` pointer is that we could swap the `t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L706" href="#L706">706</a><span class="code-text">value away to create a new path:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L707" href="#L707">707</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L708" href="#L708">708</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L709" href="#L709">709</a><span class="code-text">// src/test/compile-fail/borrowck-swap-mut-base-ptr.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L710" href="#L710">710</a><span class="code-text">fn foo&lt;'a&gt;(mut t0: &amp;'a mut i32,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L711" href="#L711">711</a><span class="code-text">           mut t1: &amp;'a mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L712" href="#L712">712</a><span class="code-text">    let p: &amp;i32 = &amp;*t0;     // Freezes `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L713" href="#L713">713</a><span class="code-text">    swap(&amp;mut t0, &amp;mut t1); //~ ERROR cannot borrow `t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L714" href="#L714">714</a><span class="code-text">    *t1 = 22;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L715" href="#L715">715</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L716" href="#L716">716</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L717" href="#L717">717</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L718" href="#L718">718</a><span class="code-text">This is illegal for the same reason as above. Note that if we added</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L719" href="#L719">719</a><span class="code-text">back a swap operator -- as we used to have -- we would want to be very</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L720" href="#L720">720</a><span class="code-text">careful to ensure this example is still illegal.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L721" href="#L721">721</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L722" href="#L722">722</a><span class="code-text">**Example danger 3: Freeze the base pointer.** In the case where the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L723" href="#L723">723</a><span class="code-text">referent is claimed, even freezing the base pointer can be dangerous,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L724" href="#L724">724</a><span class="code-text">as shown in the following example:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L725" href="#L725">725</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L726" href="#L726">726</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L727" href="#L727">727</a><span class="code-text">// src/test/compile-fail/borrowck-borrow-of-mut-base-ptr.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L728" href="#L728">728</a><span class="code-text">fn foo&lt;'a&gt;(mut t0: &amp;'a mut i32,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L729" href="#L729">729</a><span class="code-text">           mut t1: &amp;'a mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L730" href="#L730">730</a><span class="code-text">    let p: &amp;mut i32 = &amp;mut *t0; // Claims `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L731" href="#L731">731</a><span class="code-text">    let mut t2 = &amp;t0;           //~ ERROR cannot borrow `t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L732" href="#L732">732</a><span class="code-text">    let q: &amp;i32 = &amp;*t2;         // Freezes `*t0` but not through `*p`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L733" href="#L733">733</a><span class="code-text">    *p += 1;                    // violates type of `*q`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L734" href="#L734">734</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L735" href="#L735">735</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L736" href="#L736">736</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L737" href="#L737">737</a><span class="code-text">Here the problem is that `*t0` is claimed by `p`, and hence `p` wants</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L738" href="#L738">738</a><span class="code-text">to be the controlling pointer through which mutation or freezes occur.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L739" href="#L739">739</a><span class="code-text">But `t2` would -- if it were legal -- have the type `&amp; &amp;mut i32`, and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L740" href="#L740">740</a><span class="code-text">hence would be a mutable pointer in an aliasable location, which is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L741" href="#L741">741</a><span class="code-text">considered frozen (since no one can write to `**t2` as it is not a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L742" href="#L742">742</a><span class="code-text">unique path). Therefore, we could reasonably create a frozen `&amp;i32`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L743" href="#L743">743</a><span class="code-text">pointer pointing at `*t0` that coexists with the mutable pointer `p`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L744" href="#L744">744</a><span class="code-text">which is clearly unsound.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L745" href="#L745">745</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L746" href="#L746">746</a><span class="code-text">However, it is not always unsafe to freeze the base pointer. In</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L747" href="#L747">747</a><span class="code-text">particular, if the referent is frozen, there is no harm in it:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L748" href="#L748">748</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L749" href="#L749">749</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L750" href="#L750">750</a><span class="code-text">// src/test/ui/borrowck-borrow-of-mut-base-ptr-safe.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L751" href="#L751">751</a><span class="code-text">fn foo&lt;'a&gt;(mut t0: &amp;'a mut i32,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L752" href="#L752">752</a><span class="code-text">           mut t1: &amp;'a mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L753" href="#L753">753</a><span class="code-text">    let p: &amp;i32 = &amp;*t0; // Freezes `*t0`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L754" href="#L754">754</a><span class="code-text">    let mut t2 = &amp;t0;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L755" href="#L755">755</a><span class="code-text">    let q: &amp;i32 = &amp;*t2; // Freezes `*t0`, but that's ok...</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L756" href="#L756">756</a><span class="code-text">    let r: &amp;i32 = &amp;*t0; // ...after all, could do same thing directly.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L757" href="#L757">757</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L758" href="#L758">758</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L759" href="#L759">759</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L760" href="#L760">760</a><span class="code-text">In this case, creating the alias `t2` of `t0` is safe because the only</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L761" href="#L761">761</a><span class="code-text">thing `t2` can be used for is to further freeze `*t0`, which is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L762" href="#L762">762</a><span class="code-text">already frozen. In particular, we cannot assign to `*t0` through the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L763" href="#L763">763</a><span class="code-text">new alias `t2`, as demonstrated in this test case:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L764" href="#L764">764</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L765" href="#L765">765</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L766" href="#L766">766</a><span class="code-text">// src/test/ui/borrowck-borrow-mut-base-ptr-in-aliasable-loc.rs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L767" href="#L767">767</a><span class="code-text">fn foo(t0: &amp; &amp;mut i32) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L768" href="#L768">768</a><span class="code-text">    let t1 = t0;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L769" href="#L769">769</a><span class="code-text">    let p: &amp;i32 = &amp;**t0;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L770" href="#L770">770</a><span class="code-text">    **t1 = 22; //~ ERROR cannot assign</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L771" href="#L771">771</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L772" href="#L772">772</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L773" href="#L773">773</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L774" href="#L774">774</a><span class="code-text">This distinction is reflected in the rules. When doing an `&amp;mut`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L775" href="#L775">775</a><span class="code-text">borrow -- as in the first example -- the set `ACTIONS` will be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L776" href="#L776">776</a><span class="code-text">`CLAIM|MUTATE|FREEZE`, because claiming the referent implies that it</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L777" href="#L777">777</a><span class="code-text">cannot be claimed, mutated, or frozen by anyone else. These</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L778" href="#L778">778</a><span class="code-text">restrictions are propagated back to the base path and hence the base</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L779" href="#L779">779</a><span class="code-text">path is considered unfreezable.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L780" href="#L780">780</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L781" href="#L781">781</a><span class="code-text">In contrast, when the referent is merely frozen -- as in the second</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L782" href="#L782">782</a><span class="code-text">example -- the set `ACTIONS` will be `CLAIM|MUTATE`, because freezing</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L783" href="#L783">783</a><span class="code-text">the referent implies that it cannot be claimed or mutated but permits</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L784" href="#L784">784</a><span class="code-text">others to freeze. Hence when these restrictions are propagated back to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L785" href="#L785">785</a><span class="code-text">the base path, it will still be considered freezable.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L786" href="#L786">786</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L787" href="#L787">787</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L788" href="#L788">788</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L789" href="#L789">789</a><span class="code-text">**FIXME [RFC 1751](https://github.com/rust-lang/rfcs/issues/1751)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L790" href="#L790">790</a><span class="code-text">Restrictions against mutating the base pointer.**</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L791" href="#L791">791</a><span class="code-text">When an `&amp;mut` pointer is frozen or claimed, we currently pass along the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L792" href="#L792">792</a><span class="code-text">restriction against MUTATE to the base pointer. I do not believe this</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L793" href="#L793">793</a><span class="code-text">restriction is needed. It dates from the days when we had a way to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L794" href="#L794">794</a><span class="code-text">mutate that preserved the value being mutated (i.e., swap). Nowadays</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L795" href="#L795">795</a><span class="code-text">the only form of mutation is assignment, which destroys the pointer</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L796" href="#L796">796</a><span class="code-text">being mutated -- therefore, a mutation cannot create a new path to the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L797" href="#L797">797</a><span class="code-text">same data. Rather, it removes an existing path. This implies that not</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L798" href="#L798">798</a><span class="code-text">only can we permit mutation, we can have mutation kill restrictions in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L799" href="#L799">799</a><span class="code-text">the dataflow sense.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L800" href="#L800">800</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L801" href="#L801">801</a><span class="code-text">**WARNING:** We do not currently have `const` borrows in the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L802" href="#L802">802</a><span class="code-text">language. If they are added back in, we must ensure that they are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L803" href="#L803">803</a><span class="code-text">consistent with all of these examples. The crucial question will be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L804" href="#L804">804</a><span class="code-text">what sorts of actions are permitted with a `&amp;const &amp;mut` pointer. I</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L805" href="#L805">805</a><span class="code-text">would suggest that an `&amp;mut` referent found in an `&amp;const` location be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L806" href="#L806">806</a><span class="code-text">prohibited from both freezes and claims. This would avoid the need to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L807" href="#L807">807</a><span class="code-text">prevent `const` borrows of the base pointer when the referent is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L808" href="#L808">808</a><span class="code-text">borrowed.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L809" href="#L809">809</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L810" href="#L810">810</a><span class="code-text">[ Previous revisions of this document discussed `&amp;const` in more detail.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L811" href="#L811">811</a><span class="code-text">See the revision history. ]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L812" href="#L812">812</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L813" href="#L813">813</a><span class="code-text"># Moves and initialization</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L814" href="#L814">814</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L815" href="#L815">815</a><span class="code-text">The borrow checker is also in charge of ensuring that:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L816" href="#L816">816</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L817" href="#L817">817</a><span class="code-text">- all memory which is accessed is initialized</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L818" href="#L818">818</a><span class="code-text">- immutable local variables are assigned at most once.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L819" href="#L819">819</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L820" href="#L820">820</a><span class="code-text">These are two separate dataflow analyses built on the same</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L821" href="#L821">821</a><span class="code-text">framework. Let's look at checking that memory is initialized first;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L822" href="#L822">822</a><span class="code-text">the checking of immutable local variable assignments works in a very</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L823" href="#L823">823</a><span class="code-text">similar way.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L824" href="#L824">824</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L825" href="#L825">825</a><span class="code-text">To track the initialization of memory, we actually track all the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L826" href="#L826">826</a><span class="code-text">points in the program that *create uninitialized memory*, meaning</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L827" href="#L827">827</a><span class="code-text">moves and the declaration of uninitialized variables. For each of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L828" href="#L828">828</a><span class="code-text">these points, we create a bit in the dataflow set. Assignments to a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L829" href="#L829">829</a><span class="code-text">variable `x` or path `a.b.c` kill the move/uninitialization bits for</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L830" href="#L830">830</a><span class="code-text">those paths and any subpaths (e.g., `x`, `x.y`, `a.b.c`, `*a.b.c`).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L831" href="#L831">831</a><span class="code-text">Bits are unioned when two control-flow paths join. Thus, the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L832" href="#L832">832</a><span class="code-text">presence of a bit indicates that the move may have occurred without an</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L833" href="#L833">833</a><span class="code-text">intervening assignment to the same memory. At each use of a variable,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L834" href="#L834">834</a><span class="code-text">we examine the bits in scope, and check that none of them are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L835" href="#L835">835</a><span class="code-text">moves/uninitializations of the variable that is being used.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L836" href="#L836">836</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L837" href="#L837">837</a><span class="code-text">Let's look at a simple example:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L838" href="#L838">838</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L839" href="#L839">839</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L840" href="#L840">840</a><span class="code-text">fn foo(a: Box&lt;i32&gt;) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L841" href="#L841">841</a><span class="code-text">    let b: Box&lt;i32&gt;;   // Gen bit 0.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L842" href="#L842">842</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L843" href="#L843">843</a><span class="code-text">    if cond {          // Bits: 0</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L844" href="#L844">844</a><span class="code-text">        use(&amp;*a);</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L845" href="#L845">845</a><span class="code-text">        b = a;         // Gen bit 1, kill bit 0.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L846" href="#L846">846</a><span class="code-text">        use(&amp;*b);</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L847" href="#L847">847</a><span class="code-text">    } else {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L848" href="#L848">848</a><span class="code-text">                       // Bits: 0</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L849" href="#L849">849</a><span class="code-text">    }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L850" href="#L850">850</a><span class="code-text">                       // Bits: 0,1</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L851" href="#L851">851</a><span class="code-text">    use(&amp;*a);          // Error.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L852" href="#L852">852</a><span class="code-text">    use(&amp;*b);          // Error.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L853" href="#L853">853</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L854" href="#L854">854</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L855" href="#L855">855</a><span class="code-text">fn use(a: &amp;i32) { }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L856" href="#L856">856</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L857" href="#L857">857</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L858" href="#L858">858</a><span class="code-text">In this example, the variable `b` is created uninitialized. In one</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L859" href="#L859">859</a><span class="code-text">branch of an `if`, we then move the variable `a` into `b`. Once we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L860" href="#L860">860</a><span class="code-text">exit the `if`, therefore, it is an error to use `a` or `b` since both</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L861" href="#L861">861</a><span class="code-text">are only conditionally initialized. I have annotated the dataflow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L862" href="#L862">862</a><span class="code-text">state using comments. There are two dataflow bits, with bit 0</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L863" href="#L863">863</a><span class="code-text">corresponding to the creation of `b` without an initializer, and bit 1</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L864" href="#L864">864</a><span class="code-text">corresponding to the move of `a`. The assignment `b = a` both</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L865" href="#L865">865</a><span class="code-text">generates bit 1, because it is a move of `a`, and kills bit 0, because</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L866" href="#L866">866</a><span class="code-text">`b` is now initialized. On the else branch, though, `b` is never</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L867" href="#L867">867</a><span class="code-text">initialized, and so bit 0 remains untouched. When the two flows of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L868" href="#L868">868</a><span class="code-text">control join, we union the bits from both sides, resulting in both</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L869" href="#L869">869</a><span class="code-text">bits 0 and 1 being set. Thus any attempt to use `a` uncovers the bit 1</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L870" href="#L870">870</a><span class="code-text">from the &quot;then&quot; branch, showing that `a` may be moved, and any attempt</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L871" href="#L871">871</a><span class="code-text">to use `b` uncovers bit 0, from the &quot;else&quot; branch, showing that `b`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L872" href="#L872">872</a><span class="code-text">may not be initialized.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L873" href="#L873">873</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L874" href="#L874">874</a><span class="code-text">## Initialization of immutable variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L875" href="#L875">875</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L876" href="#L876">876</a><span class="code-text">Initialization of immutable variables works in a very similar way,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L877" href="#L877">877</a><span class="code-text">except that:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L878" href="#L878">878</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L879" href="#L879">879</a><span class="code-text">1. we generate bits for each assignment to a variable;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L880" href="#L880">880</a><span class="code-text">2. the bits are never killed except when the variable goes out of scope.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L881" href="#L881">881</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L882" href="#L882">882</a><span class="code-text">Thus the presence of an assignment bit indicates that the assignment</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L883" href="#L883">883</a><span class="code-text">may have occurred. Note that assignments are only killed when the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L884" href="#L884">884</a><span class="code-text">variable goes out of scope, as it is not relevant whether or not there</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L885" href="#L885">885</a><span class="code-text">has been a move in the meantime. Using these bits, we can declare that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L886" href="#L886">886</a><span class="code-text">an assignment to an immutable variable is legal iff there is no other</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L887" href="#L887">887</a><span class="code-text">assignment bit to that same variable in scope.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L888" href="#L888">888</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L889" href="#L889">889</a><span class="code-text">## Why is the design made this way?</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L890" href="#L890">890</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L891" href="#L891">891</a><span class="code-text">It may seem surprising that we assign dataflow bits to *each move*</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L892" href="#L892">892</a><span class="code-text">rather than *each path being moved*. This is somewhat less efficient,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L893" href="#L893">893</a><span class="code-text">since on each use, we must iterate through all moves and check whether</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L894" href="#L894">894</a><span class="code-text">any of them correspond to the path in question. Similar concerns apply</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L895" href="#L895">895</a><span class="code-text">to the analysis for double assignments to immutable variables. The</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L896" href="#L896">896</a><span class="code-text">main reason to do it this way is that it allows us to print better</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L897" href="#L897">897</a><span class="code-text">error messages, because when a use occurs, we can print out the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L898" href="#L898">898</a><span class="code-text">precise move that may be in scope, rather than simply having to say</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L899" href="#L899">899</a><span class="code-text">&quot;the variable may not be initialized&quot;.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L900" href="#L900">900</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L901" href="#L901">901</a><span class="code-text">## Data structures used in the move analysis</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L902" href="#L902">902</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L903" href="#L903">903</a><span class="code-text">The move analysis maintains several data structures that enable it to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L904" href="#L904">904</a><span class="code-text">cross-reference moves and assignments to determine when they may be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L905" href="#L905">905</a><span class="code-text">moving/assigning the same memory. These are all collected into the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L906" href="#L906">906</a><span class="code-text">`MoveData` and `FlowedMoveData` structs. The former represents the set</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L907" href="#L907">907</a><span class="code-text">of move paths, moves, and assignments, and the latter adds in the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L908" href="#L908">908</a><span class="code-text">results of a dataflow computation.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L909" href="#L909">909</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L910" href="#L910">910</a><span class="code-text">### Move paths</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L911" href="#L911">911</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L912" href="#L912">912</a><span class="code-text">The `MovePath` tree tracks every path that is moved or assigned to.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L913" href="#L913">913</a><span class="code-text">These paths have the same form as the `LoanPath` data structure, which</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L914" href="#L914">914</a><span class="code-text">in turn is the &quot;real world version of the places `P` that we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L915" href="#L915">915</a><span class="code-text">introduced earlier. The difference between a `MovePath` and a `LoanPath`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L916" href="#L916">916</a><span class="code-text">is that move paths are:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L917" href="#L917">917</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L918" href="#L918">918</a><span class="code-text">1. Canonicalized, so that we have exactly one copy of each, and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L919" href="#L919">919</a><span class="code-text">   we can refer to move paths by index;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L920" href="#L920">920</a><span class="code-text">2. Cross-referenced with other paths into a tree, so that given a move</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L921" href="#L921">921</a><span class="code-text">   path we can efficiently find all parent move paths and all</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L922" href="#L922">922</a><span class="code-text">   extensions (e.g., given the `a.b` move path, we can easily find the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L923" href="#L923">923</a><span class="code-text">   move path `a` and also the move paths `a.b.c`)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L924" href="#L924">924</a><span class="code-text">3. Cross-referenced with moves and assignments, so that we can</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L925" href="#L925">925</a><span class="code-text">   easily find all moves and assignments to a given path.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L926" href="#L926">926</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L927" href="#L927">927</a><span class="code-text">The mechanism that we use is to create a `MovePath` record for each</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L928" href="#L928">928</a><span class="code-text">move path. These are arranged in an array and are referenced using</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L929" href="#L929">929</a><span class="code-text">`MovePathIndex` values, which are newtype'd indices. The `MovePath`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L930" href="#L930">930</a><span class="code-text">structs are arranged into a tree, representing using the standard</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L931" href="#L931">931</a><span class="code-text">Knuth representation where each node has a child 'pointer' and a &quot;next</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L932" href="#L932">932</a><span class="code-text">sibling&quot; 'pointer'. In addition, each `MovePath` has a parent</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L933" href="#L933">933</a><span class="code-text">'pointer'.  In this case, the 'pointers' are just `MovePathIndex`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L934" href="#L934">934</a><span class="code-text">values.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L935" href="#L935">935</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L936" href="#L936">936</a><span class="code-text">In this way, if we want to find all base paths of a given move path,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L937" href="#L937">937</a><span class="code-text">we can just iterate up the parent pointers (see `each_base_path()` in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L938" href="#L938">938</a><span class="code-text">the `move_data` module). If we want to find all extensions, we can</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L939" href="#L939">939</a><span class="code-text">iterate through the subtree (see `each_extending_path()`).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L940" href="#L940">940</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L941" href="#L941">941</a><span class="code-text">### Moves and assignments</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L942" href="#L942">942</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L943" href="#L943">943</a><span class="code-text">There are structs to represent moves (`Move`) and assignments</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L944" href="#L944">944</a><span class="code-text">(`Assignment`), and these are also placed into arrays and referenced</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L945" href="#L945">945</a><span class="code-text">by index. All moves of a particular path are arranged into a linked</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L946" href="#L946">946</a><span class="code-text">lists, beginning with `MovePath.first_move` and continuing through</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L947" href="#L947">947</a><span class="code-text">`Move.next_move`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L948" href="#L948">948</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L949" href="#L949">949</a><span class="code-text">We distinguish between &quot;var&quot; assignments, which are assignments to a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L950" href="#L950">950</a><span class="code-text">variable like `x = foo`, and &quot;path&quot; assignments (`x.f = foo`).  This</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L951" href="#L951">951</a><span class="code-text">is because we need to assign dataflows to the former, but not the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L952" href="#L952">952</a><span class="code-text">latter, so as to check for double initialization of immutable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L953" href="#L953">953</a><span class="code-text">variables.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L954" href="#L954">954</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L955" href="#L955">955</a><span class="code-text">### Gathering and checking moves</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L956" href="#L956">956</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L957" href="#L957">957</a><span class="code-text">Like loans, we distinguish two phases. The first, gathering, is where</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L958" href="#L958">958</a><span class="code-text">we uncover all the moves and assignments. As with loans, we do some</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L959" href="#L959">959</a><span class="code-text">basic sanity checking in this phase, so we'll report errors if you</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L960" href="#L960">960</a><span class="code-text">attempt to move out of a borrowed pointer etc. Then we do the dataflow</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L961" href="#L961">961</a><span class="code-text">(see `FlowedMoveData::new`). Finally, in the `check_loans.rs` code, we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L962" href="#L962">962</a><span class="code-text">walk back over, identify all uses, assignments, and captures, and</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L963" href="#L963">963</a><span class="code-text">check that they are legal given the set of dataflow bits we have</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L964" href="#L964">964</a><span class="code-text">computed for that program point.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L965" href="#L965">965</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L966" href="#L966">966</a><span class="code-text"># Drop flags and structural fragments</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L967" href="#L967">967</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L968" href="#L968">968</a><span class="code-text">In addition to the job of enforcing memory safety, the borrow checker</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L969" href="#L969">969</a><span class="code-text">code is also responsible for identifying the *structural fragments* of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L970" href="#L970">970</a><span class="code-text">data in the function, to support out-of-band dynamic drop flags</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L971" href="#L971">971</a><span class="code-text">allocated on the stack. (For background, see [RFC PR #320].)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L972" href="#L972">972</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L973" href="#L973">973</a><span class="code-text">[RFC PR #320]: https://github.com/rust-lang/rfcs/pull/320</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L974" href="#L974">974</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L975" href="#L975">975</a><span class="code-text">Semantically, each piece of data that has a destructor may need a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L976" href="#L976">976</a><span class="code-text">boolean flag to indicate whether or not its destructor has been run</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L977" href="#L977">977</a><span class="code-text">yet. However, in many cases there is no need to actually maintain such</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L978" href="#L978">978</a><span class="code-text">a flag: It can be apparent from the code itself that a given path is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L979" href="#L979">979</a><span class="code-text">always initialized (or always deinitialized) when control reaches the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L980" href="#L980">980</a><span class="code-text">end of its owner's scope, and thus we can unconditionally emit (or</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L981" href="#L981">981</a><span class="code-text">not) the destructor invocation for that path.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L982" href="#L982">982</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L983" href="#L983">983</a><span class="code-text">A simple example of this is the following:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L984" href="#L984">984</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L985" href="#L985">985</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L986" href="#L986">986</a><span class="code-text">struct D { p: i32 }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L987" href="#L987">987</a><span class="code-text">impl D { fn new(x: i32) -&gt; D { ... }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L988" href="#L988">988</a><span class="code-text">impl Drop for D { ... }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L989" href="#L989">989</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L990" href="#L990">990</a><span class="code-text">fn foo(a: D, b: D, t: || -&gt; bool) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L991" href="#L991">991</a><span class="code-text">    let c: D;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L992" href="#L992">992</a><span class="code-text">    let d: D;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L993" href="#L993">993</a><span class="code-text">    if t() { c = b; }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L994" href="#L994">994</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L995" href="#L995">995</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L996" href="#L996">996</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L997" href="#L997">997</a><span class="code-text">At the end of the body of `foo`, the compiler knows that `a` is</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L998" href="#L998">998</a><span class="code-text">initialized, introducing a drop obligation (deallocating the boxed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L999" href="#L999">999</a><span class="code-text">integer) for the end of `a`'s scope that is run unconditionally.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1000" href="#L1000">1000</a><span class="code-text">Likewise the compiler knows that `d` is not initialized, and thus it</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1001" href="#L1001">1001</a><span class="code-text">leave out the drop code for `d`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1002" href="#L1002">1002</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1003" href="#L1003">1003</a><span class="code-text">The compiler cannot statically know the drop-state of `b` nor `c` at</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1004" href="#L1004">1004</a><span class="code-text">the end of their scope, since that depends on the value of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1005" href="#L1005">1005</a><span class="code-text">`t`. Therefore, we need to insert boolean flags to track whether we</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1006" href="#L1006">1006</a><span class="code-text">need to drop `b` and `c`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1007" href="#L1007">1007</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1008" href="#L1008">1008</a><span class="code-text">However, the matter is not as simple as just mapping local variables</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1009" href="#L1009">1009</a><span class="code-text">to their corresponding drop flags when necessary. In particular, in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1010" href="#L1010">1010</a><span class="code-text">addition to being able to move data out of local variables, Rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1011" href="#L1011">1011</a><span class="code-text">allows one to move values in and out of structured data.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1012" href="#L1012">1012</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1013" href="#L1013">1013</a><span class="code-text">Consider the following:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1014" href="#L1014">1014</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1015" href="#L1015">1015</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1016" href="#L1016">1016</a><span class="code-text">struct S { x: D, y: D, z: D }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1017" href="#L1017">1017</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1018" href="#L1018">1018</a><span class="code-text">fn foo(a: S, mut b: S, t: || -&gt; bool) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1019" href="#L1019">1019</a><span class="code-text">    let mut c: S;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1020" href="#L1020">1020</a><span class="code-text">    let d: S;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1021" href="#L1021">1021</a><span class="code-text">    let e: S = a.clone();</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1022" href="#L1022">1022</a><span class="code-text">    if t() {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1023" href="#L1023">1023</a><span class="code-text">        c = b;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1024" href="#L1024">1024</a><span class="code-text">        b.x = e.y;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1025" href="#L1025">1025</a><span class="code-text">    }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1026" href="#L1026">1026</a><span class="code-text">    if t() { c.y = D::new(4); }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1027" href="#L1027">1027</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1028" href="#L1028">1028</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1029" href="#L1029">1029</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1030" href="#L1030">1030</a><span class="code-text">As before, the drop obligations of `a` and `d` can be statically</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1031" href="#L1031">1031</a><span class="code-text">determined, and again the state of `b` and `c` depend on dynamic</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1032" href="#L1032">1032</a><span class="code-text">state. But additionally, the dynamic drop obligations introduced by</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1033" href="#L1033">1033</a><span class="code-text">`b` and `c` are not just per-local boolean flags. For example, if the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1034" href="#L1034">1034</a><span class="code-text">first call to `t` returns `false` and the second call `true`, then at</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1035" href="#L1035">1035</a><span class="code-text">the end of their scope, `b` will be completely initialized, but only</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1036" href="#L1036">1036</a><span class="code-text">`c.y` in `c` will be initialized.  If both calls to `t` return `true`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1037" href="#L1037">1037</a><span class="code-text">then at the end of their scope, `c` will be completely initialized,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1038" href="#L1038">1038</a><span class="code-text">but only `b.x` will be initialized in `b`, and only `e.x` and `e.z`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1039" href="#L1039">1039</a><span class="code-text">will be initialized in `e`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1040" href="#L1040">1040</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1041" href="#L1041">1041</a><span class="code-text">Note that we need to cover the `z` field in each case in some way,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1042" href="#L1042">1042</a><span class="code-text">since it may (or may not) need to be dropped, even though `z` is never</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1043" href="#L1043">1043</a><span class="code-text">directly mentioned in the body of the `foo` function. We call a path</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1044" href="#L1044">1044</a><span class="code-text">like `b.z` a *fragment sibling* of `b.x`, since the field `z` comes</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1045" href="#L1045">1045</a><span class="code-text">from the same structure `S` that declared the field `x` in `b.x`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1046" href="#L1046">1046</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1047" href="#L1047">1047</a><span class="code-text">In general we need to maintain boolean flags that match the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1048" href="#L1048">1048</a><span class="code-text">`S`-structure of both `b` and `c`.  In addition, we need to consult</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1049" href="#L1049">1049</a><span class="code-text">such a flag when doing an assignment (such as `c.y = D::new(4);`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1050" href="#L1050">1050</a><span class="code-text">above), in order to know whether or not there is a previous value that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1051" href="#L1051">1051</a><span class="code-text">needs to be dropped before we do the assignment.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1052" href="#L1052">1052</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1053" href="#L1053">1053</a><span class="code-text">So for any given function, we need to determine what flags are needed</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1054" href="#L1054">1054</a><span class="code-text">to track its drop obligations. Our strategy for determining the set of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1055" href="#L1055">1055</a><span class="code-text">flags is to represent the fragmentation of the structure explicitly:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1056" href="#L1056">1056</a><span class="code-text">by starting initially from the paths that are explicitly mentioned in</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1057" href="#L1057">1057</a><span class="code-text">moves and assignments (such as `b.x` and `c.y` above), and then</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1058" href="#L1058">1058</a><span class="code-text">traversing the structure of the path's type to identify leftover</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1059" href="#L1059">1059</a><span class="code-text">*unmoved fragments*: assigning into `c.y` means that `c.x` and `c.z`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1060" href="#L1060">1060</a><span class="code-text">are leftover unmoved fragments. Each fragment represents a drop</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1061" href="#L1061">1061</a><span class="code-text">obligation that may need to be tracked. Paths that are only moved or</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1062" href="#L1062">1062</a><span class="code-text">assigned in their entirety (like `a` and `d`) are treated as a single</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1063" href="#L1063">1063</a><span class="code-text">drop obligation.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1064" href="#L1064">1064</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1065" href="#L1065">1065</a><span class="code-text">The fragment construction process works by piggy-backing on the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1066" href="#L1066">1066</a><span class="code-text">existing `move_data` module. We already have callbacks that visit each</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1067" href="#L1067">1067</a><span class="code-text">direct move and assignment; these form the basis for the sets of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1068" href="#L1068">1068</a><span class="code-text">moved_leaf_paths and assigned_leaf_paths. From these leaves, we can</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1069" href="#L1069">1069</a><span class="code-text">walk up their parent chain to identify all of their parent paths.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1070" href="#L1070">1070</a><span class="code-text">We need to identify the parents because of cases like the following:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1071" href="#L1071">1071</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1072" href="#L1072">1072</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1073" href="#L1073">1073</a><span class="code-text">struct Pair&lt;X,Y&gt;{ x: X, y: Y }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1074" href="#L1074">1074</a><span class="code-text">fn foo(dd_d_d: Pair&lt;Pair&lt;Pair&lt;D, D&gt;, D&gt;, D&gt;) {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1075" href="#L1075">1075</a><span class="code-text">    other_function(dd_d_d.x.y);</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1076" href="#L1076">1076</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1077" href="#L1077">1077</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1078" href="#L1078">1078</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1079" href="#L1079">1079</a><span class="code-text">In this code, the move of the path `dd_d.x.y` leaves behind not only</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1080" href="#L1080">1080</a><span class="code-text">the fragment drop-obligation `dd_d.x.x` but also `dd_d.y` as well.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1081" href="#L1081">1081</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1082" href="#L1082">1082</a><span class="code-text">Once we have identified the directly-referenced leaves and their</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1083" href="#L1083">1083</a><span class="code-text">parents, we compute the left-over fragments, in the function</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1084" href="#L1084">1084</a><span class="code-text">`fragments::add_fragment_siblings`. As of this writing this works by</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1085" href="#L1085">1085</a><span class="code-text">looking at each directly-moved or assigned path P, and blindly</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1086" href="#L1086">1086</a><span class="code-text">gathering all sibling fields of P (as well as siblings for the parents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1087" href="#L1087">1087</a><span class="code-text">of P, etc). After accumulating all such siblings, we filter out the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1088" href="#L1088">1088</a><span class="code-text">entries added as siblings of P that turned out to be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1089" href="#L1089">1089</a><span class="code-text">directly-referenced paths (or parents of directly referenced paths)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1090" href="#L1090">1090</a><span class="code-text">themselves, thus leaving the never-referenced &quot;left-overs&quot; as the only</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1091" href="#L1091">1091</a><span class="code-text">thing left from the gathering step.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1092" href="#L1092">1092</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1093" href="#L1093">1093</a><span class="code-text">## Array structural fragments</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1094" href="#L1094">1094</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1095" href="#L1095">1095</a><span class="code-text">A special case of the structural fragments discussed above are</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1096" href="#L1096">1096</a><span class="code-text">the elements of an array that has been passed by value, such as</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1097" href="#L1097">1097</a><span class="code-text">the following:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1098" href="#L1098">1098</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1099" href="#L1099">1099</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1100" href="#L1100">1100</a><span class="code-text">fn foo(a: [D; 10], i: i32) -&gt; D {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1101" href="#L1101">1101</a><span class="code-text">    a[i]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1102" href="#L1102">1102</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1103" href="#L1103">1103</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1104" href="#L1104">1104</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1105" href="#L1105">1105</a><span class="code-text">The above code moves a single element out of the input array `a`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1106" href="#L1106">1106</a><span class="code-text">The remainder of the array still needs to be dropped; i.e., it</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1107" href="#L1107">1107</a><span class="code-text">is a structural fragment. Note that after performing such a move,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1108" href="#L1108">1108</a><span class="code-text">it is not legal to read from the array `a`. There are a number of</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1109" href="#L1109">1109</a><span class="code-text">ways to deal with this, but the important thing to note is that</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1110" href="#L1110">1110</a><span class="code-text">the semantics needs to distinguish in some manner between a</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1111" href="#L1111">1111</a><span class="code-text">fragment that is the *entire* array versus a fragment that represents</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1112" href="#L1112">1112</a><span class="code-text">all-but-one element of the array.  A place where that distinction</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1113" href="#L1113">1113</a><span class="code-text">would arise is the following:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1114" href="#L1114">1114</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1115" href="#L1115">1115</a><span class="code-text">```rust</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1116" href="#L1116">1116</a><span class="code-text">fn foo(a: [D; 10], b: [D; 10], i: i32, t: bool) -&gt; D {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1117" href="#L1117">1117</a><span class="code-text">    if t {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1118" href="#L1118">1118</a><span class="code-text">        a[i]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1119" href="#L1119">1119</a><span class="code-text">    } else {</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1120" href="#L1120">1120</a><span class="code-text">        b[i]</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1121" href="#L1121">1121</a><span class="code-text">    }</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1122" href="#L1122">1122</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1123" href="#L1123">1123</a><span class="code-text">    // When control exits, we will need either to drop all of `a`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1124" href="#L1124">1124</a><span class="code-text">    // and all-but-one of `b`, or to drop all of `b` and all-but-one</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1125" href="#L1125">1125</a><span class="code-text">    // of `a`.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1126" href="#L1126">1126</a><span class="code-text">}</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1127" href="#L1127">1127</a><span class="code-text">```</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1128" href="#L1128">1128</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1129" href="#L1129">1129</a><span class="code-text">There are a number of ways that the codegen backend could choose to</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1130" href="#L1130">1130</a><span class="code-text">compile this (e.g. a `[bool; 10]` array for each such moved array;</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1131" href="#L1131">1131</a><span class="code-text">or an `Option&lt;usize&gt;` for each moved array).  From the viewpoint of the</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1132" href="#L1132">1132</a><span class="code-text">borrow-checker, the important thing is to record what kind of fragment</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1133" href="#L1133">1133</a><span class="code-text">is implied by the relevant moves.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1134" href="#L1134">1134</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1135" href="#L1135">1135</a><span class="code-text"># Future work</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1136" href="#L1136">1136</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1137" href="#L1137">1137</a><span class="code-text">While writing up these docs, I encountered some rules I believe to be</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1138" href="#L1138">1138</a><span class="code-text">stricter than necessary:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1139" href="#L1139">1139</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1140" href="#L1140">1140</a><span class="code-text">- I think restricting the `&amp;mut` P against moves and `ALIAS` is sufficient,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1141" href="#L1141">1141</a><span class="code-text">  `MUTATE` and `CLAIM` are overkill. `MUTATE` was necessary when swap was</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1142" href="#L1142">1142</a><span class="code-text">  a built-in operator, but as it is not, it is implied by `CLAIM`,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1143" href="#L1143">1143</a><span class="code-text">  and `CLAIM` is implied by `ALIAS`. The only net effect of this is an</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1144" href="#L1144">1144</a><span class="code-text">  extra error message in some cases, though.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1145" href="#L1145">1145</a><span class="code-text">- I have not described how closures interact. Current code is unsound.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1146" href="#L1146">1146</a><span class="code-text">  I am working on describing and implementing the fix.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1147" href="#L1147">1147</a><span class="code-text">- If we wish, we can easily extend the move checking to allow finer-grained</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1148" href="#L1148">1148</a><span class="code-text">  tracking of what is initialized and what is not, enabling code like</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1149" href="#L1149">1149</a><span class="code-text">  this:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1150" href="#L1150">1150</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1151" href="#L1151">1151</a><span class="code-text">      a = x.f.g; // x.f.g is now uninitialized</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1152" href="#L1152">1152</a><span class="code-text">      // here, x and x.f are not usable, but x.f.h *is*</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1153" href="#L1153">1153</a><span class="code-text">      x.f.g = b; // x.f.g is not initialized</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1154" href="#L1154">1154</a><span class="code-text">      // now x, x.f, x.f.g, x.f.h are all usable</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1155" href="#L1155">1155</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1156" href="#L1156">1156</a><span class="code-text">  What needs to change here, most likely, is that the `moves` module</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1157" href="#L1157">1157</a><span class="code-text">  should record not only what paths are moved, but what expressions</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1158" href="#L1158">1158</a><span class="code-text">  are actual *uses*. For example, the reference to `x` in `x.f.g = b`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1159" href="#L1159">1159</a><span class="code-text">  is not a true *use* in the sense that it requires `x` to be fully</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1160" href="#L1160">1160</a><span class="code-text">  initialized. This is in fact why the above code produces an error</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1161" href="#L1161">1161</a><span class="code-text">  today: the reference to `x` in `x.f.g = b` is considered illegal</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1162" href="#L1162">1162</a><span class="code-text">  because `x` is not fully initialized.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1163" href="#L1163">1163</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1164" href="#L1164">1164</a><span class="code-text">There are also some possible refactorings:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1165" href="#L1165">1165</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1166" href="#L1166">1166</a><span class="code-text">- It might be nice to replace all loan paths with the MovePath mechanism,</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L1167" href="#L1167">1167</a><span class="code-text">  since they allow lightweight comparison using an integer.</span></span></pre></div></div>
</main>
</body>
</html>
