Google Git
Sign in
rust / rust-lang / rustc-dev-guide / refs/heads/gh-pages / . / opaque-types-impl-trait-inference.html
blob: 9f590f844daf553d5de695f09a3f064aefc5bef8 [file] [log] [blame]
<!DOCTYPE HTML>
<html lang="en" class="light sidebar-visible" dir="ltr">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Inference details - Rust Compiler Development Guide</title>
<!-- Custom HTML head -->
<meta name="description" content="A guide to developing the Rust compiler (rustc)">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff">
<link rel="icon" href="favicon.svg">
<link rel="shortcut icon" href="favicon.png">
<link rel="stylesheet" href="css/variables.css">
<link rel="stylesheet" href="css/general.css">
<link rel="stylesheet" href="css/chrome.css">
<link rel="stylesheet" href="css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" id="highlight-css" href="highlight.css">
<link rel="stylesheet" id="tomorrow-night-css" href="tomorrow-night.css">
<link rel="stylesheet" id="ayu-highlight-css" href="ayu-highlight.css">
<!-- Custom theme stylesheets -->
<link rel="stylesheet" href="pagetoc.css">
<!-- Provide site root and default themes to javascript -->
<script>
const path_to_root = "";
const default_light_theme = "light";
const default_dark_theme = "navy";
window.path_to_searchindex_js = "searchindex.js";
</script>
<!-- Start loading toc.js asap -->
<script src="toc.js"></script>
</head>
<body>
<div id="mdbook-help-container">
<div id="mdbook-help-popup">
<h2 class="mdbook-help-title">Keyboard shortcuts</h2>
<div>
<p>Press <kbd>←</kbd> or <kbd>→</kbd> to navigate between chapters</p>
<p>Press <kbd>S</kbd> or <kbd>/</kbd> to search in the book</p>
<p>Press <kbd>?</kbd> to show this help</p>
<p>Press <kbd>Esc</kbd> to hide this help</p>
</div>
</div>
</div>
<div id="body-container">
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script>
try {
let theme = localStorage.getItem('mdbook-theme');
let sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script>
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
let theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
const html = document.documentElement;
html.classList.remove('light')
html.classList.add(theme);
html.classList.add("js");
</script>
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
<!-- Hide / unhide sidebar before it is displayed -->
<script>
let sidebar = null;
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
} else {
sidebar = 'hidden';
sidebar_toggle.checked = false;
}
if (sidebar === 'visible') {
sidebar_toggle.checked = true;
} else {
html.classList.remove('sidebar-visible');
}
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<!-- populated by js -->
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
<noscript>
<iframe class="sidebar-iframe-outer" src="toc.html"></iframe>
</noscript>
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
<div class="sidebar-resize-indicator"></div>
</div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky">
<div class="left-buttons">
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</label>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Rust Compiler Development Guide</h1>
<div class="right-buttons">
<a href="print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
<a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
<i id="git-repository-button" class="fa fa-github"></i>
</a>
<a href="https://github.com/rust-lang/rustc-dev-guide/edit/master/src/opaque-types-impl-trait-inference.md" title="Suggest an edit" aria-label="Suggest an edit" rel="edit">
<i id="git-edit-button" class="fa fa-edit"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<div class="search-wrapper">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
<div class="spinner-wrapper">
<i class="fa fa-spinner fa-spin"></i>
</div>
</div>
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script>
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="inference-of-opaque-types-impl-trait"><a class="header" href="#inference-of-opaque-types-impl-trait">Inference of opaque types (<code>impl Trait</code>)</a></h1>
<p>This page describes how the compiler infers the <a href="./borrow_check/region_inference/member_constraints.html?highlight=%22hidden%20type%22#member-constraints">hidden type</a> for an <a href="./opaque-types-type-alias-impl-trait.html">opaque type</a>.
This kind of type inference is particularly complex because,
unlike other kinds of type inference,
it can work across functions and function bodies.</p>
<h2 id="running-example"><a class="header" href="#running-example">Running example</a></h2>
<p>To help explain how it works, let's consider an example.</p>
<pre><pre class="playground"><code class="language-rust">#![feature(type_alias_impl_trait)]
mod m {
pub type Seq&lt;T&gt; = impl IntoIterator&lt;Item = T&gt;;
#[define_opaque(Seq)]
pub fn produce_singleton&lt;T&gt;(t: T) -&gt; Seq&lt;T&gt; {
vec![t]
}
#[define_opaque(Seq)]
pub fn produce_doubleton&lt;T&gt;(t: T, u: T) -&gt; Seq&lt;T&gt; {
vec![t, u]
}
}
fn is_send&lt;T: Send&gt;(_: &amp;T) {}
pub fn main() {
let elems = m::produce_singleton(22);
is_send(&amp;elems);
for elem in elems {
println!("elem = {:?}", elem);
}
}</code></pre></pre>
<p>In this code, the <em>opaque type</em> is <code>Seq&lt;T&gt;</code>.
Its defining scope is the module <code>m</code>.
Its <em>hidden type</em> is <code>Vec&lt;T&gt;</code>,
which is inferred from <code>m::produce_singleton</code> and <code>m::produce_doubleton</code>.</p>
<p>In the <code>main</code> function, the opaque type is out of its defining scope.
When <code>main</code> calls <code>m::produce_singleton</code>, it gets back a reference to the opaque type <code>Seq&lt;i32&gt;</code>.
The <code>is_send</code> call checks that <code>Seq&lt;i32&gt;: Send</code>.
<code>Send</code> is not listed amongst the bounds of the impl trait,
but because of auto-trait leakage, we are able to infer that it holds.
The <code>for</code> loop desugaring requires that <code>Seq&lt;T&gt;: IntoIterator</code>,
which is provable from the bounds declared on <code>Seq&lt;T&gt;</code>.</p>
<h3 id="type-checking-main"><a class="header" href="#type-checking-main">Type-checking <code>main</code></a></h3>
<p>Let's start by looking what happens when we type-check <code>main</code>.
Initially we invoke <code>produce_singleton</code> and the return type is an opaque type
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/hir/enum.ItemKind.html#variant.OpaqueTy"><code>OpaqueTy</code></a>.</p>
<h4 id="type-checking-the-for-loop"><a class="header" href="#type-checking-the-for-loop">Type-checking the for loop</a></h4>
<p>The for loop desugars the <code>in elems</code> part to <code>IntoIterator::into_iter(elems)</code>.
<code>elems</code> is of type <code>Seq&lt;T&gt;</code>, so the type checker registers a <code>Seq&lt;T&gt;: IntoIterator</code> obligation.
This obligation is trivially satisfied,
because <code>Seq&lt;T&gt;</code> is an opaque type (<code>impl IntoIterator&lt;Item = T&gt;</code>) that has a bound for the trait.
Similar to how a <code>U: Foo</code> where bound allows <code>U</code> to trivially satisfy <code>Foo</code>,
opaque types' bounds are available to the type checker and are used to fulfill obligations.</p>
<p>The type of <code>elem</code> in the for loop is inferred to be <code>&lt;Seq&lt;T&gt; as IntoIterator&gt;::Item</code>, which is <code>T</code>.
At no point is the type checker interested in the hidden type.</p>
<h4 id="type-checking-the-is_send-call"><a class="header" href="#type-checking-the-is_send-call">Type-checking the <code>is_send</code> call</a></h4>
<p>When trying to prove auto trait bounds,
we first repeat the process as above,
to see if the auto trait is in the bound list of the opaque type.
If that fails, we reveal the hidden type of the opaque type,
but only to prove this specific trait bound, not in general.
Revealing is done by invoking the <code>type_of</code> query on the <code>DefId</code> of the opaque type.
The query will internally request the hidden types from the defining function(s)
and return that (see <a href="#within-the-type_of-query">the section on <code>type_of</code></a> for more details).</p>
<h4 id="flowchart-of-type-checking-steps"><a class="header" href="#flowchart-of-type-checking-steps">Flowchart of type checking steps</a></h4>
<pre class="mermaid">flowchart TD
TypeChecking[&quot;type checking `main`&quot;]
subgraph TypeOfSeq[&quot;type_of(Seq&lt;T&gt;) query&quot;]
WalkModuleHir[&quot;Walk the HIR for the module `m`\nto find the hidden types from each\nfunction/const/static within&quot;]
VisitProduceSingleton[&quot;visit `produce_singleton`&quot;]
InterimType[&quot;`produce_singleton` hidden type is `Vec&lt;T&gt;`\nkeep searching&quot;]
VisitProduceDoubleton[&quot;visit `produce_doubleton`&quot;]
CompareType[&quot;`produce_doubleton` hidden type is also Vec&lt;T&gt;\nthis matches what we saw before ✅&quot;]
Done[&quot;No more items to look at in scope\nReturn `Vec&lt;T&gt;`&quot;]
end
BorrowCheckProduceSingleton[&quot;`borrow_check(produce_singleton)`&quot;]
TypeCheckProduceSingleton[&quot;`type_check(produce_singleton)`&quot;]
BorrowCheckProduceDoubleton[&quot;`borrow_check(produce_doubleton)`&quot;]
TypeCheckProduceDoubleton[&quot;`type_check(produce_doubleton)`&quot;]
Substitute[&quot;Substitute `T =&gt; u32`,\nyielding `Vec&lt;i32&gt;` as the hidden type&quot;]
CheckSend[&quot;Check that `Vec&lt;i32&gt;: Send` ✅&quot;]
TypeChecking -- trait code for auto traits --&gt; TypeOfSeq
TypeOfSeq --&gt; WalkModuleHir
WalkModuleHir --&gt; VisitProduceSingleton
VisitProduceSingleton --&gt; BorrowCheckProduceSingleton
BorrowCheckProduceSingleton --&gt; TypeCheckProduceSingleton
TypeCheckProduceSingleton --&gt; InterimType
InterimType --&gt; VisitProduceDoubleton
VisitProduceDoubleton --&gt; BorrowCheckProduceDoubleton
BorrowCheckProduceDoubleton --&gt; TypeCheckProduceDoubleton
TypeCheckProduceDoubleton --&gt; CompareType --&gt; Done
Done --&gt; Substitute --&gt; CheckSend
</pre>
<h3 id="within-the-type_of-query"><a class="header" href="#within-the-type_of-query">Within the <code>type_of</code> query</a></h3>
<p>The <code>type_of</code> query, when applied to an opaque type O, returns the hidden type.
That hidden type is computed by combining the results
from each constraining function within the defining scope of O.</p>
<pre class="mermaid">flowchart TD
TypeOf[&quot;type_of query&quot;]
TypeOf -- find_opaque_ty_constraints --&gt; FindOpaqueTyConstraints
FindOpaqueTyConstraints --&gt; Iterate
Iterate[&quot;Iterate over each item in defining scope&quot;]
Iterate -- For each item --&gt; TypeCheck
TypeCheck[&quot;Check typeck(I) to see if it constraints O&quot;]
TypeCheck -- I does not\nconstrain O --&gt; Iterate
TypeCheck -- I constrains O --&gt; BorrowCheck
BorrowCheck[&quot;Invoke mir_borrowck(I) to get hidden type\nfor O computed by I&quot;]
BorrowCheck --&gt; PreviousType
PreviousType[&quot;Hidden type from I\nsame as any previous hidden type\nfound so far?&quot;]
PreviousType -- Yes --&gt; Complete
PreviousType -- No --&gt; ReportError
ReportError[&quot;Report an error&quot;]
ReportError --&gt; Complete[&quot;Item I complete&quot;]
Complete --&gt; Iterate
FindOpaqueTyConstraints -- All constraints found --&gt; Done
Done[&quot;Done&quot;]
</pre>
<h3 id="relating-an-opaque-type-to-another-type"><a class="header" href="#relating-an-opaque-type-to-another-type">Relating an opaque type to another type</a></h3>
<p>There is one central place where an opaque type gets its hidden type constrained,
and that is the <code>handle_opaque_type</code> function.
Amusingly it takes two types, so you can pass any two types,
but one of them should be an opaque type.
The order is only important for diagnostics.</p>
<pre class="mermaid">flowchart TD
subgraph typecheck[&quot;type check comparison routines&quot;]
equate.rs
sub.rs
lub.rs
end
typecheck --&gt; TwoSimul
subgraph handleopaquetype[&quot;infcx.handle_opaque_type&quot;]
TwoSimul[&quot;Defining two opaque types simultaneously?&quot;]
TwoSimul -- Yes --&gt; ReportError[&quot;Report error&quot;]
TwoSimul -- No --&gt; MayDefine -- Yes --&gt; RegisterOpaqueType --&gt; AlreadyHasValue
MayDefine -- No --&gt; ReportError
MayDefine[&quot;In defining scope OR in query?&quot;]
AlreadyHasValue[&quot;Opaque type X already has\na registered value?&quot;]
AlreadyHasValue -- No --&gt; Obligations[&quot;Register opaque type bounds\nas obligations for hidden type&quot;]
RegisterOpaqueType[&quot;Register opaque type with\nother type as value&quot;]
AlreadyHasValue -- Yes --&gt; EquateOpaqueTypes[&quot;Equate new hidden type\nwith old hidden type&quot;]
end
</pre>
<h3 id="interactions-with-queries"><a class="header" href="#interactions-with-queries">Interactions with queries</a></h3>
<p>When queries handle opaque types,
they cannot figure out whether they are in a defining scope,
so they just assume they are.</p>
<p>The registered hidden types are stored into the <code>QueryResponse</code> struct
in the <code>opaque_types</code> field (the function
<code>take_opaque_types_for_query_response</code> reads them out).</p>
<p>When the <code>QueryResponse</code> is instantiated into the surrounding infcx in
<code>query_response_substitution_guess</code>,
we convert each hidden type constraint by invoking <code>handle_opaque_type</code> (as above).</p>
<p>There is one bit of "weirdness".
The instantiated opaque types have an order
(if one opaque type was compared with another,
and we have to pick one opaque type to use as the one that gets its hidden type assigned).
We use the one that is considered "expected".
But really both of the opaque types may have defining uses.
When the query result is instantiated,
that will be re-evaluated from the context that is using the query.
The final context (typeck of a function, mir borrowck or wf-checks)
will know which opaque type can actually be instantiated
and then handle it correctly.</p>
<h3 id="within-the-mir-borrow-checker"><a class="header" href="#within-the-mir-borrow-checker">Within the MIR borrow checker</a></h3>
<p>The MIR borrow checker relates things via <code>nll_relate</code> and only cares about regions.
Any type relation will trigger the binding of hidden types,
so the borrow checker is doing the same thing as the type checker,
but ignores obviously dead code (e.g. after a panic).
The borrow checker is also the source of truth when it comes to hidden types,
as it is the only one who can properly figure out what lifetimes on the hidden type correspond
to which lifetimes on the opaque type declaration.</p>
<h2 id="backwards-compatibility-hacks"><a class="header" href="#backwards-compatibility-hacks">Backwards compatibility hacks</a></h2>
<p><code>impl Trait</code> in return position has various quirks that were not part
of any RFCs and are likely accidental stabilization.
To support these,
the <code>replace_opaque_types_with_inference_vars</code> is being used to reintroduce the previous behaviour.</p>
<p>There are three backwards compatibility hacks:</p>
<ol>
<li>
<p>All return sites share the same inference variable,
so some return sites may only compile if another return site uses a concrete type.</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>fn foo() -&gt; impl Debug {
if false {
return std::iter::empty().collect();
}
vec![42]
}
<span class="boring">}</span></code></pre></pre>
</li>
<li>
<p>Associated type equality constraints for <code>impl Trait</code> can be used
as long as the hidden type satisfies the trait bounds on the associated type.
The opaque <code>impl Trait</code> signature does not need to satisfy them.</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>trait Duh {}
impl Duh for i32 {}
trait Trait {
type Assoc: Duh;
}
// the fact that `R` is the `::Output` projection on `F` causes
// an intermediate inference var to be generated which is then later
// compared against the actually found `Assoc` type.
impl&lt;R: Duh, F: FnMut() -&gt; R&gt; Trait for F {
type Assoc = R;
}
// The `impl Send` here is then later compared against the inference var
// created, causing the inference var to be set to `impl Send` instead of
// the hidden type. We already have obligations registered on the inference
// var to make it uphold the `: Duh` bound on `Trait::Assoc`. The opaque
// type does not implement `Duh`, even if its hidden type does.
// Lazy TAIT would error out, but we inserted a hack to make it work again,
// keeping backwards compatibility.
fn foo() -&gt; impl Trait&lt;Assoc = impl Send&gt; {
|| 42
}
<span class="boring">}</span></code></pre></pre>
</li>
<li>
<p>Closures cannot create hidden types for their parent function's <code>impl Trait</code>.
This point is mostly moot,
because of point 1 introducing inference vars,
so the closure only ever sees the inference var, but should we fix 1, this will become a problem.</p>
</li>
</ol>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="opaque-types-type-alias-impl-trait.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="return-position-impl-trait-in-trait.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="opaque-types-type-alias-impl-trait.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="return-position-impl-trait-in-trait.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script>
window.playground_copyable = true;
</script>
<script src="elasticlunr.min.js"></script>
<script src="mark.min.js"></script>
<script src="searcher.js"></script>
<script src="clipboard.min.js"></script>
<script src="highlight.js"></script>
<script src="book.js"></script>
<!-- Custom JS scripts -->
<script src="mermaid.min.js"></script>
<script src="mermaid-init.js"></script>
<script src="pagetoc.js"></script>
</div>
</body>
</html>