Google Git
Sign in
rust / rust-lang / rustc-dev-guide / refs/heads/gh-pages / . / ty_module / binders.html
blob: 65ed3593cabda47c934da3542d51899823867b29 [file] [log] [blame] [edit]
<!DOCTYPE HTML>
<html lang="en" class="light sidebar-visible" dir="ltr">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Binders and Higher ranked regions - 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/main/src/ty_module/binders.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="binder-and-higher-ranked-regions"><a class="header" href="#binder-and-higher-ranked-regions"><code>Binder</code> and Higher ranked regions</a></h1>
<p>Sometimes we define generic parameters not on an item but as part of a type or a where clause. As an example the type <code>for&lt;'a&gt; fn(&amp;'a u32)</code> or the where clause <code>for&lt;'a&gt; T: Trait&lt;'a&gt;</code> both introduce a generic lifetime named <code>'a</code>. Currently there is no stable syntax for <code>for&lt;T&gt;</code> or <code>for&lt;const N: usize&gt;</code> but on nightly <code>feature(non_lifetime_binders)</code> can be used to write where clauses (but not types) using <code>for&lt;T&gt;</code>/<code>for&lt;const N: usize&gt;</code>.</p>
<p>The <code>for</code> is referred to as a "binder" because it brings new names into scope. In rustc we use the <code>Binder</code> type to track where these parameters are introduced and what the parameters are (i.e. how many and whether the parameter is a type/const/region). A type such as <code>for&lt;'a&gt; fn(&amp;'a u32)</code> would be
represented in rustc as:</p>
<pre><code>Binder(
fn(&amp;RegionKind::Bound(DebruijnIndex(0), BoundVar(0)) u32) -&gt; (),
&amp;[BoundVariableKind::Region(...)],
)
</code></pre>
<p>Usages of these parameters is represented by the <code>RegionKind::Bound</code> (or <code>TyKind::Bound</code>/<code>ConstKind::Bound</code> variants). These bound regions/types/consts are composed of two main pieces of data:</p>
<ul>
<li>A <a href="../appendix/background.html#what-is-a-de-bruijn-index">DebruijnIndex</a> to specify which binder we are referring to.</li>
<li>A <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.BoundVar.html"><code>BoundVar</code></a> which specifies which of the parameters that the <code>Binder</code> introduces we are referring to.</li>
</ul>
<p>We also sometimes store some extra information for diagnostics reasons via the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.BoundTyKind.html"><code>BoundTyKind</code></a>/<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.BoundRegionKind.html"><code>BoundRegionKind</code></a> but this is not important for type equality or more generally the semantics of <code>Ty</code>. (omitted from the above example)</p>
<p>In debug output (and also informally when talking to each other) we tend to write these bound variables in the format of <code>^DebruijnIndex_BoundVar</code>. The above example would instead be written as <code>Binder(fn(&amp;'^0_0), &amp;[BoundVariableKind::Region])</code>. Sometimes when the <code>DebruijnIndex</code> is <code>0</code> we just omit it and would write <code>^0</code>.</p>
<p>Another concrete example, this time a mixture of <code>for&lt;'a&gt;</code> in a where clause and a type:</p>
<pre><code>where
for&lt;'a&gt; Foo&lt;for&lt;'b&gt; fn(&amp;'a &amp;'b T)&gt;: Trait,
</code></pre>
<p>This would be represented as</p>
<pre><code>Binder(
Foo&lt;Binder(
fn(&amp;'^1_0 &amp;'^0 T/#0),
[BoundVariableKind::Region(...)]
)&gt;: Trait,
[BoundVariableKind::Region(...)]
)
</code></pre>
<p>Note how the <code>'^1_0</code> refers to the <code>'a</code> parameter. We use a <code>DebruijnIndex</code> of <code>1</code> to refer to the binder one level up from the innermost one, and a var of <code>0</code> to refer to the first parameter bound which is <code>'a</code>. We also use <code>'^0</code> to refer to the <code>'b</code> parameter, the <code>DebruijnIndex</code> is <code>0</code> (referring to the innermost binder) so we omit it, leaving only the boundvar of <code>0</code> referring to the first parameter bound which is <code>'b</code>.</p>
<p>We did not always explicitly track the set of bound vars introduced by each <code>Binder</code>, this caused a number of bugs (read: ICEs <a href="https://github.com/rust-lang/rust/issues/81193">#81193</a>, <a href="https://github.com/rust-lang/rust/issues/79949">#79949</a>, <a href="https://github.com/rust-lang/rust/issues/83017">#83017</a>). By tracking these explicitly we can assert when constructing higher ranked where clauses/types that there are no escaping bound variables or variables from a different binder. See the following example of an invalid type inside of a binder:</p>
<pre><code>Binder(
fn(&amp;'^1_0 &amp;'^1 T/#0),
&amp;[BoundVariableKind::Region(...)],
)
</code></pre>
<p>This would cause all kinds of issues as the region <code>'^1_0</code> refers to a binder at a higher level than the outermost binder i.e. it is an escaping bound var. The <code>'^1</code> region (also writeable as <code>'^0_1</code>) is also ill formed as the binder it refers to does not introduce a second parameter. Modern day rustc will ICE when constructing this binder due to both of those reasons, in the past we would have simply allowed this to work and then ran into issues in other parts of the codebase.</p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="../ty_module/early_binder.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="../ty_module/instantiating_binders.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="../ty_module/early_binder.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="../ty_module/instantiating_binders.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>