name-resolution.html - rust-lang/rustc-dev-guide - Git at Google

 <!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&lt;T: Default&gt;(val: T) { // &lt;- 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() { // &lt;- 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>
	<!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>