373 lines
21 KiB
HTML
373 lines
21 KiB
HTML
<!DOCTYPE HTML>
|
||
<html lang="en" class="light sidebar-visible" dir="ltr">
|
||
<head>
|
||
<!-- Book generated using mdBook -->
|
||
<meta charset="UTF-8">
|
||
<title>Name resolution - Rust Compiler Development Guide</title>
|
||
|
||
|
||
<!-- Custom HTML head -->
|
||
|
||
<meta name="description" content="A guide to developing the Rust compiler (rustc)">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1">
|
||
<meta name="theme-color" content="#ffffff">
|
||
|
||
<link rel="icon" href="favicon.svg">
|
||
<link rel="shortcut icon" href="favicon.png">
|
||
<link rel="stylesheet" href="css/variables.css">
|
||
<link rel="stylesheet" href="css/general.css">
|
||
<link rel="stylesheet" href="css/chrome.css">
|
||
<link rel="stylesheet" href="css/print.css" media="print">
|
||
|
||
<!-- Fonts -->
|
||
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
|
||
<link rel="stylesheet" href="fonts/fonts.css">
|
||
|
||
<!-- Highlight.js Stylesheets -->
|
||
<link rel="stylesheet" id="highlight-css" href="highlight.css">
|
||
<link rel="stylesheet" id="tomorrow-night-css" href="tomorrow-night.css">
|
||
<link rel="stylesheet" id="ayu-highlight-css" href="ayu-highlight.css">
|
||
|
||
<!-- Custom theme stylesheets -->
|
||
|
||
|
||
<!-- Provide site root and default themes to javascript -->
|
||
<script>
|
||
const path_to_root = "";
|
||
const default_light_theme = "light";
|
||
const default_dark_theme = "navy";
|
||
</script>
|
||
<!-- Start loading toc.js asap -->
|
||
<script src="toc.js"></script>
|
||
</head>
|
||
<body>
|
||
<div id="body-container">
|
||
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
||
<script>
|
||
try {
|
||
let theme = localStorage.getItem('mdbook-theme');
|
||
let sidebar = localStorage.getItem('mdbook-sidebar');
|
||
|
||
if (theme.startsWith('"') && theme.endsWith('"')) {
|
||
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
||
}
|
||
|
||
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
||
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
||
}
|
||
} catch (e) { }
|
||
</script>
|
||
|
||
<!-- Set the theme before any content is loaded, prevents flash -->
|
||
<script>
|
||
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
|
||
let theme;
|
||
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
||
if (theme === null || theme === undefined) { theme = default_theme; }
|
||
const html = document.documentElement;
|
||
html.classList.remove('light')
|
||
html.classList.add(theme);
|
||
html.classList.add("js");
|
||
</script>
|
||
|
||
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
|
||
|
||
<!-- Hide / unhide sidebar before it is displayed -->
|
||
<script>
|
||
let sidebar = null;
|
||
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
|
||
if (document.body.clientWidth >= 1080) {
|
||
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
||
sidebar = sidebar || 'visible';
|
||
} else {
|
||
sidebar = 'hidden';
|
||
}
|
||
sidebar_toggle.checked = sidebar === 'visible';
|
||
html.classList.remove('sidebar-visible');
|
||
html.classList.add("sidebar-" + sidebar);
|
||
</script>
|
||
|
||
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
||
<!-- populated by js -->
|
||
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
|
||
<noscript>
|
||
<iframe class="sidebar-iframe-outer" src="toc.html"></iframe>
|
||
</noscript>
|
||
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
|
||
<div class="sidebar-resize-indicator"></div>
|
||
</div>
|
||
</nav>
|
||
|
||
<div id="page-wrapper" class="page-wrapper">
|
||
|
||
<div class="page">
|
||
<div id="menu-bar-hover-placeholder"></div>
|
||
<div id="menu-bar" class="menu-bar sticky">
|
||
<div class="left-buttons">
|
||
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
||
<i class="fa fa-bars"></i>
|
||
</label>
|
||
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
||
<i class="fa fa-paint-brush"></i>
|
||
</button>
|
||
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
||
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
||
</ul>
|
||
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
||
<i class="fa fa-search"></i>
|
||
</button>
|
||
</div>
|
||
|
||
<h1 class="menu-title">Rust Compiler Development Guide</h1>
|
||
|
||
<div class="right-buttons">
|
||
<a href="print.html" title="Print this book" aria-label="Print this book">
|
||
<i id="print-button" class="fa fa-print"></i>
|
||
</a>
|
||
<a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
|
||
<i id="git-repository-button" class="fa fa-github"></i>
|
||
</a>
|
||
<a href="https://github.com/rust-lang/rustc-dev-guide/edit/master/src/name-resolution.md" title="Suggest an edit" aria-label="Suggest an edit">
|
||
<i id="git-edit-button" class="fa fa-edit"></i>
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div id="search-wrapper" class="hidden">
|
||
<form id="searchbar-outer" class="searchbar-outer">
|
||
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
||
</form>
|
||
<div id="searchresults-outer" class="searchresults-outer hidden">
|
||
<div id="searchresults-header" class="searchresults-header"></div>
|
||
<ul id="searchresults">
|
||
</ul>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
||
<script>
|
||
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
||
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
||
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
||
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
||
});
|
||
</script>
|
||
|
||
<div id="content" class="content">
|
||
<main>
|
||
<h1 id="name-resolution"><a class="header" href="#name-resolution">Name resolution</a></h1>
|
||
<ul>
|
||
<li><a href="#basics">Basics</a></li>
|
||
<li><a href="#namespaces">Namespaces</a></li>
|
||
<li><a href="#scopes-and-ribs">Scopes and ribs</a></li>
|
||
<li><a href="#overall-strategy">Overall strategy</a></li>
|
||
<li><a href="#speculative-crate-loading">Speculative crate loading</a></li>
|
||
<li><a href="#todo-16">TODO: #16</a></li>
|
||
</ul>
|
||
<p>In the previous chapters, we saw how the <a href="./ast-validation.html"><em>Abstract Syntax Tree</em> (<code>AST</code>)</a>
|
||
is built with all macros expanded. We saw how doing that requires doing some
|
||
name resolution to resolve imports and macro names. In this chapter, we show
|
||
how this is actually done and more.</p>
|
||
<p>In fact, we don't do full name resolution during macro expansion -- we only
|
||
resolve imports and macros at that time. This is required to know what to even
|
||
expand. Later, after we have the whole AST, we do full name resolution to
|
||
resolve all names in the crate. This happens in <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/index.html"><code>rustc_resolve::late</code></a>.
|
||
Unlike during macro expansion, in this late expansion, we only need to try to
|
||
resolve a name once, since no new names can be added. If we fail to resolve a
|
||
name, then it is a compiler error.</p>
|
||
<p>Name resolution is complex. There are different namespaces (e.g.
|
||
macros, values, types, lifetimes), and names may be valid at different (nested)
|
||
scopes. Also, different types of names can fail resolution differently, and
|
||
failures can happen differently at different scopes. For example, in a module
|
||
scope, failure means no unexpanded macros and no unresolved glob imports in
|
||
that module. On the other hand, in a function body scope, failure requires that a
|
||
name be absent from the block we are in, all outer scopes, and the global
|
||
scope.</p>
|
||
<h2 id="basics"><a class="header" href="#basics">Basics</a></h2>
|
||
<p>In our programs we refer to variables, types, functions, etc, by giving them
|
||
a name. These names are not always unique. For example, take this valid Rust
|
||
program:</p>
|
||
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
||
</span><span class="boring">fn main() {
|
||
</span>type x = u32;
|
||
let x: x = 1;
|
||
let y: x = 2;
|
||
<span class="boring">}</span></code></pre></pre>
|
||
<p>How do we know on line 3 whether <code>x</code> is a type (<code>u32</code>) or a value (1)? These
|
||
conflicts are resolved during name resolution. In this specific case, name
|
||
resolution defines that type names and variable names live in separate
|
||
namespaces and therefore can co-exist.</p>
|
||
<p>The name resolution in Rust is a two-phase process. In the first phase, which runs
|
||
during <code>macro</code> expansion, we build a tree of modules and resolve imports. Macro
|
||
expansion and name resolution communicate with each other via the
|
||
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast_lowering/trait.ResolverAstLoweringExt.html"><code>ResolverAstLoweringExt</code></a> trait.</p>
|
||
<p>The input to the second phase is the syntax tree, produced by parsing input
|
||
files and expanding <code>macros</code>. This phase produces links from all the names in the
|
||
source to relevant places where the name was introduced. It also generates
|
||
helpful error messages, like typo suggestions, traits to import or lints about
|
||
unused items.</p>
|
||
<p>A successful run of the second phase (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/struct.Resolver.html#method.resolve_crate"><code>Resolver::resolve_crate</code></a>) creates kind
|
||
of an index the rest of the compilation may use to ask about the present names
|
||
(through the <code>hir::lowering::Resolver</code> interface).</p>
|
||
<p>The name resolution lives in the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/index.html"><code>rustc_resolve</code></a> crate, with the bulk in
|
||
<code>lib.rs</code> and some helpers or symbol-type specific logic in the other modules.</p>
|
||
<h2 id="namespaces"><a class="header" href="#namespaces">Namespaces</a></h2>
|
||
<p>Different kind of symbols live in different namespaces ‒ e.g. types don't
|
||
clash with variables. This usually doesn't happen, because variables start with
|
||
lower-case letter while types with upper-case one, but this is only a
|
||
convention. This is legal Rust code that will compile (with warnings):</p>
|
||
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
||
</span><span class="boring">fn main() {
|
||
</span>type x = u32;
|
||
let x: x = 1;
|
||
let y: x = 2; // See? x is still a type here.
|
||
<span class="boring">}</span></code></pre></pre>
|
||
<p>To cope with this, and with slightly different scoping rules for these
|
||
namespaces, the resolver keeps them separated and builds separate structures for
|
||
them.</p>
|
||
<p>In other words, when the code talks about namespaces, it doesn't mean the module
|
||
hierarchy, it's types vs. values vs. macros.</p>
|
||
<h2 id="scopes-and-ribs"><a class="header" href="#scopes-and-ribs">Scopes and ribs</a></h2>
|
||
<p>A name is visible only in certain area in the source code. This forms a
|
||
hierarchical structure, but not necessarily a simple one ‒ if one scope is
|
||
part of another, it doesn't mean a name visible in the outer scope is also
|
||
visible in the inner scope, or that it refers to the same thing.</p>
|
||
<p>To cope with that, the compiler introduces the concept of <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a>s. This is
|
||
an abstraction of a scope. Every time the set of visible names potentially changes,
|
||
a new <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a> is pushed onto a stack. The places where this can happen include for
|
||
example:</p>
|
||
<ul>
|
||
<li>The obvious places ‒ curly braces enclosing a block, function boundaries,
|
||
modules.</li>
|
||
<li>Introducing a <code>let</code> binding ‒ this can shadow another binding with the same
|
||
name.</li>
|
||
<li>Macro expansion border ‒ to cope with macro hygiene.</li>
|
||
</ul>
|
||
<p>When searching for a name, the stack of <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.LateResolutionVisitor.html#structfield.ribs"><code>ribs</code></a> is traversed from the innermost
|
||
outwards. This helps to find the closest meaning of the name (the one not
|
||
shadowed by anything else). The transition to outer <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a> may also affect
|
||
what names are usable ‒ if there are nested functions (not closures),
|
||
the inner one can't access parameters and local bindings of the outer one,
|
||
even though they should be visible by ordinary scoping rules. An example:</p>
|
||
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
|
||
</span><span class="boring">fn main() {
|
||
</span>fn do_something<T: Default>(val: T) { // <- New rib in both types and values (1)
|
||
// `val` is accessible, as is the helper function
|
||
// `T` is accessible
|
||
let helper = || { // New rib on the block (2)
|
||
// `val` is accessible here
|
||
}; // End of (2), new rib on `helper` (3)
|
||
// `val` is accessible, `helper` variable shadows `helper` function
|
||
fn helper() { // <- New rib in both types and values (4)
|
||
// `val` is not accessible here, (4) is not transparent for locals
|
||
// `T` is not accessible here
|
||
} // End of (4)
|
||
let val = T::default(); // New rib (5)
|
||
// `val` is the variable, not the parameter here
|
||
} // End of (5), (3) and (1)
|
||
<span class="boring">}</span></code></pre></pre>
|
||
<p>Because the rules for different namespaces are a bit different, each namespace
|
||
has its own independent <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a> stack that is constructed in parallel to the others.
|
||
In addition, there's also a <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a> stack for local labels (e.g. names of loops or
|
||
blocks), which isn't a full namespace in its own right.</p>
|
||
<h2 id="overall-strategy"><a class="header" href="#overall-strategy">Overall strategy</a></h2>
|
||
<p>To perform the name resolution of the whole crate, the syntax tree is traversed
|
||
top-down and every encountered name is resolved. This works for most kinds of
|
||
names, because at the point of use of a name it is already introduced in the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a>
|
||
hierarchy.</p>
|
||
<p>There are some exceptions to this. Items are bit tricky, because they can be
|
||
used even before encountered ‒ therefore every block needs to be first scanned
|
||
for items to fill in its <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/late/struct.Rib.html"><code>Rib</code></a>.</p>
|
||
<p>Other, even more problematic ones, are imports which need recursive fixed-point
|
||
resolution and macros, that need to be resolved and expanded before the rest of
|
||
the code can be processed.</p>
|
||
<p>Therefore, the resolution is performed in multiple stages.</p>
|
||
<h2 id="speculative-crate-loading"><a class="header" href="#speculative-crate-loading">Speculative crate loading</a></h2>
|
||
<p>To give useful errors, rustc suggests importing paths into scope if they're
|
||
not found. How does it do this? It looks through every module of every crate
|
||
and looks for possible matches. This even includes crates that haven't yet
|
||
been loaded!</p>
|
||
<p>Eagerly loading crates to include import suggestions that haven't yet been
|
||
loaded is called <em>speculative crate loading</em>, because any errors it encounters
|
||
shouldn't be reported: <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/index.html"><code>rustc_resolve</code></a> decided to load them, not the user. The function
|
||
that does this is <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/struct.Resolver.html#method.lookup_import_candidates"><code>lookup_import_candidates</code></a> and lives in
|
||
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/diagnostics/index.html"><code>rustc_resolve::diagnostics</code></a>.</p>
|
||
<p>To tell the difference between speculative loads and loads initiated by the
|
||
user, <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_resolve/index.html"><code>rustc_resolve</code></a> passes around a <code>record_used</code> parameter, which is <code>false</code> when
|
||
the load is speculative.</p>
|
||
<h2 id="todo-16"><a class="header" href="#todo-16">TODO: <a href="https://github.com/rust-lang/rustc-dev-guide/issues/16">#16</a></a></h2>
|
||
<p>This is a result of the first pass of learning the code. It is definitely
|
||
incomplete and not detailed enough. It also might be inaccurate in places.
|
||
Still, it probably provides useful first guidepost to what happens in there.</p>
|
||
<ul>
|
||
<li>What exactly does it link to and how is that published and consumed by
|
||
following stages of compilation?</li>
|
||
<li>Who calls it and how it is actually used.</li>
|
||
<li>Is it a pass and then the result is only used, or can it be computed
|
||
incrementally?</li>
|
||
<li>The overall strategy description is a bit vague.</li>
|
||
<li>Where does the name <code>Rib</code> come from?</li>
|
||
<li>Does this thing have its own tests, or is it tested only as part of some e2e
|
||
testing?</li>
|
||
</ul>
|
||
|
||
</main>
|
||
|
||
<nav class="nav-wrapper" aria-label="Page navigation">
|
||
<!-- Mobile navigation buttons -->
|
||
<a rel="prev" href="macro-expansion.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="attributes.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="macro-expansion.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="attributes.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
||
<i class="fa fa-angle-right"></i>
|
||
</a>
|
||
</nav>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
|
||
<script>
|
||
window.playground_copyable = true;
|
||
</script>
|
||
|
||
|
||
<script src="elasticlunr.min.js"></script>
|
||
<script src="mark.min.js"></script>
|
||
<script src="searcher.js"></script>
|
||
|
||
<script src="clipboard.min.js"></script>
|
||
<script src="highlight.js"></script>
|
||
<script src="book.js"></script>
|
||
|
||
<!-- Custom JS scripts -->
|
||
<script src="mermaid.min.js"></script>
|
||
<script src="mermaid-init.js"></script>
|
||
|
||
|
||
</div>
|
||
</body>
|
||
</html>
|