method-lookup.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>Method lookup - 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/method-lookup.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="method-lookup"><a class="header" href="#method-lookup">Method lookup</a></h1>
 <p>Method lookup can be rather complex due to the interaction of a number
 of factors, such as self types, autoderef, trait lookup, etc. This
 file provides an overview of the process. More detailed notes are in
 the code itself, naturally.</p>
 <p>One way to think of method lookup is that we convert an expression of
 the form <code>receiver.method(...)</code> into a more explicit <a href="https://doc.rust-lang.org/nightly/book/ch19-03-advanced-traits.html#fully-qualified-syntax-for-disambiguation-calling-methods-with-the-same-name">fully-qualified syntax</a>
 (formerly called <a href="https://github.com/rust-lang/rfcs/blob/master/text/0132-ufcs.md">UFCS</a>):</p>
 <ul>
 <li><code>Trait::method(ADJ(receiver), ...)</code> for a trait call</li>
 <li><code>ReceiverType::method(ADJ(receiver), ...)</code> for an inherent method call</li>
 </ul>
 <p>Here <code>ADJ</code> is some kind of adjustment, which is typically a series of
 autoderefs and then possibly an autoref (e.g., <code>&amp;**receiver</code>). However
 we sometimes do other adjustments and coercions along the way, in
 particular unsizing (e.g., converting from <code>[T; n]</code> to <code>[T]</code>).</p>
 <p>Method lookup is divided into two major phases:</p>
 <ol>
 <li>Probing (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir_typeck/method/probe/"><code>probe.rs</code></a>). The probe phase is when we decide what method
 to call and how to adjust the receiver.</li>
 <li>Confirmation (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir_typeck/method/confirm/"><code>confirm.rs</code></a>). The confirmation phase "applies"
 this selection, updating the side-tables, unifying type variables, and
 otherwise doing side-effectful things.</li>
 </ol>
 <p>One reason for this division is to be more amenable to caching.  The
 probe phase produces a "pick" (<code>probe::Pick</code>), which is designed to be
 cacheable across method-call sites. Therefore, it does not include
 inference variables or other information.</p>
 <h2 id="the-probe-phase"><a class="header" href="#the-probe-phase">The Probe phase</a></h2>
 <h3 id="steps"><a class="header" href="#steps">Steps</a></h3>
 <p>The first thing that the probe phase does is to create a series of
 <em>steps</em>. This is done by progressively dereferencing the receiver type
 until it cannot be deref'd anymore, as well as applying an optional
 "unsize" step. So if the receiver has type <code>Rc&lt;Box&lt;[T; 3]&gt;&gt;</code>, this
 might yield:</p>
 <ol>
 <li><code>Rc&lt;Box&lt;[T; 3]&gt;&gt;</code></li>
 <li><code>Box&lt;[T; 3]&gt;</code></li>
 <li><code>[T; 3]</code></li>
 <li><code>[T]</code></li>
 </ol>
 <h3 id="candidate-assembly"><a class="header" href="#candidate-assembly">Candidate assembly</a></h3>
 <p>We then search along those steps to create a list of <em>candidates</em>. A
 <code>Candidate</code> is a method item that might plausibly be the method being
 invoked. For each candidate, we'll derive a "transformed self type"
 that takes into account explicit self.</p>
 <p>Candidates are grouped into two kinds, inherent and extension.</p>
 <p><strong>Inherent candidates</strong> are those that are derived from the
 type of the receiver itself.  So, if you have a receiver of some
 nominal type <code>Foo</code> (e.g., a struct), any methods defined within an
 impl like <code>impl Foo</code> are inherent methods.  Nothing needs to be
 imported to use an inherent method, they are associated with the type
 itself (note that inherent impls can only be defined in the same
 crate as the type itself).</p>
 <!--
 FIXME: Inherent candidates are not always derived from impls.  If you
 have a trait object, such as a value of type `Box<ToString>`, then the
 trait methods (`to_string()`, in this case) are inherently associated
 with it. Another case is type parameters, in which case the methods of
 their bounds are inherent. However, this part of the rules is subject
 to change: when DST's "impl Trait for Trait" is complete, trait object
 dispatch could be subsumed into trait matching, and the type parameter
 behavior should be reconsidered in light of where clauses.

 Is this still accurate?
 -->
 <p><strong>Extension candidates</strong> are derived from imported traits.  If I have
 the trait <code>ToString</code> imported, and I call <code>to_string()</code> as a method,
 then we will list the <code>to_string()</code> definition in each impl of
 <code>ToString</code> as a candidate. These kinds of method calls are called
 "extension methods".</p>
 <p>So, let's continue our example. Imagine that we were calling a method
 <code>foo</code> with the receiver <code>Rc&lt;Box&lt;[T; 3]&gt;&gt;</code> and there is a trait <code>Foo</code>
 that defines it with <code>&amp;self</code> for the type <code>Rc&lt;U&gt;</code> as well as a method
 on the type <code>Box</code> that defines <code>foo</code> but with <code>&amp;mut self</code>. Then we
 might have two candidates:</p>
 <ul>
 <li><code>&amp;Rc&lt;U&gt;</code> as an extension candidate</li>
 <li><code>&amp;mut Box&lt;U&gt;</code> as an inherent candidate</li>
 </ul>
 <h3 id="candidate-search"><a class="header" href="#candidate-search">Candidate search</a></h3>
 <p>Finally, to actually pick the method, we will search down the steps,
 trying to match the receiver type against the candidate types. At
 each step, we also consider an auto-ref and auto-mut-ref to see whether
 that makes any of the candidates match. For each resulting receiver
 type, we consider inherent candidates before extension candidates.
 If there are multiple matching candidates in a group, we report an
 error, except that multiple impls of the same trait are treated as a
 single match. Otherwise we pick the first match we find.</p>
 <p>In the case of our example, the first step is <code>Rc&lt;Box&lt;[T; 3]&gt;&gt;</code>,
 which does not itself match any candidate. But when we autoref it, we
 get the type <code>&amp;Rc&lt;Box&lt;[T; 3]&gt;&gt;</code> which matches <code>&amp;Rc&lt;U&gt;</code>. We would then
 recursively consider all where-clauses that appear on the impl: if
 those match (or we cannot rule out that they do), then this is the
 method we would pick. Otherwise, we would continue down the series of
 steps.</p>

                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="type-checking.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="variance.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="type-checking.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="variance.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>Method lookup - 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/method-lookup.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="method-lookup"><a class="header" href="#method-lookup">Method lookup</a></h1>
	<p>Method lookup can be rather complex due to the interaction of a number
	of factors, such as self types, autoderef, trait lookup, etc. This
	file provides an overview of the process. More detailed notes are in
	the code itself, naturally.</p>
	<p>One way to think of method lookup is that we convert an expression of
	the form <code>receiver.method(...)</code> into a more explicit <a href="https://doc.rust-lang.org/nightly/book/ch19-03-advanced-traits.html#fully-qualified-syntax-for-disambiguation-calling-methods-with-the-same-name">fully-qualified syntax</a>
	(formerly called <a href="https://github.com/rust-lang/rfcs/blob/master/text/0132-ufcs.md">UFCS</a>):</p>
	<ul>
	<li><code>Trait::method(ADJ(receiver), ...)</code> for a trait call</li>
	<li><code>ReceiverType::method(ADJ(receiver), ...)</code> for an inherent method call</li>
	</ul>
	<p>Here <code>ADJ</code> is some kind of adjustment, which is typically a series of
	autoderefs and then possibly an autoref (e.g., <code>&**receiver</code>). However
	we sometimes do other adjustments and coercions along the way, in
	particular unsizing (e.g., converting from <code>[T; n]</code> to <code>[T]</code>).</p>
	<p>Method lookup is divided into two major phases:</p>
	<ol>
	<li>Probing (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir_typeck/method/probe/"><code>probe.rs</code></a>). The probe phase is when we decide what method
	to call and how to adjust the receiver.</li>
	<li>Confirmation (<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir_typeck/method/confirm/"><code>confirm.rs</code></a>). The confirmation phase "applies"
	this selection, updating the side-tables, unifying type variables, and
	otherwise doing side-effectful things.</li>
	</ol>
	<p>One reason for this division is to be more amenable to caching. The
	probe phase produces a "pick" (<code>probe::Pick</code>), which is designed to be
	cacheable across method-call sites. Therefore, it does not include
	inference variables or other information.</p>
	<h2 id="the-probe-phase"><a class="header" href="#the-probe-phase">The Probe phase</a></h2>
	<h3 id="steps"><a class="header" href="#steps">Steps</a></h3>
	<p>The first thing that the probe phase does is to create a series of
	<em>steps</em>. This is done by progressively dereferencing the receiver type
	until it cannot be deref'd anymore, as well as applying an optional
	"unsize" step. So if the receiver has type <code>Rc<Box<[T; 3]>></code>, this
	might yield:</p>
	<ol>
	<li><code>Rc<Box<[T; 3]>></code></li>
	<li><code>Box<[T; 3]></code></li>
	<li><code>[T; 3]</code></li>
	<li><code>[T]</code></li>
	</ol>
	<h3 id="candidate-assembly"><a class="header" href="#candidate-assembly">Candidate assembly</a></h3>
	<p>We then search along those steps to create a list of <em>candidates</em>. A
	<code>Candidate</code> is a method item that might plausibly be the method being
	invoked. For each candidate, we'll derive a "transformed self type"
	that takes into account explicit self.</p>
	<p>Candidates are grouped into two kinds, inherent and extension.</p>
	<p><strong>Inherent candidates</strong> are those that are derived from the
	type of the receiver itself. So, if you have a receiver of some
	nominal type <code>Foo</code> (e.g., a struct), any methods defined within an
	impl like <code>impl Foo</code> are inherent methods. Nothing needs to be
	imported to use an inherent method, they are associated with the type
	itself (note that inherent impls can only be defined in the same
	crate as the type itself).</p>
	<!--
	FIXME: Inherent candidates are not always derived from impls. If you
	have a trait object, such as a value of type `Box<ToString>`, then the
	trait methods (`to_string()`, in this case) are inherently associated
	with it. Another case is type parameters, in which case the methods of
	their bounds are inherent. However, this part of the rules is subject
	to change: when DST's "impl Trait for Trait" is complete, trait object
	dispatch could be subsumed into trait matching, and the type parameter
	behavior should be reconsidered in light of where clauses.

	Is this still accurate?
	-->
	<p><strong>Extension candidates</strong> are derived from imported traits. If I have
	the trait <code>ToString</code> imported, and I call <code>to_string()</code> as a method,
	then we will list the <code>to_string()</code> definition in each impl of
	<code>ToString</code> as a candidate. These kinds of method calls are called
	"extension methods".</p>
	<p>So, let's continue our example. Imagine that we were calling a method
	<code>foo</code> with the receiver <code>Rc<Box<[T; 3]>></code> and there is a trait <code>Foo</code>
	that defines it with <code>&self</code> for the type <code>Rc<U></code> as well as a method
	on the type <code>Box</code> that defines <code>foo</code> but with <code>&mut self</code>. Then we
	might have two candidates:</p>
	<ul>
	<li><code>&Rc<U></code> as an extension candidate</li>
	<li><code>&mut Box<U></code> as an inherent candidate</li>
	</ul>
	<h3 id="candidate-search"><a class="header" href="#candidate-search">Candidate search</a></h3>
	<p>Finally, to actually pick the method, we will search down the steps,
	trying to match the receiver type against the candidate types. At
	each step, we also consider an auto-ref and auto-mut-ref to see whether
	that makes any of the candidates match. For each resulting receiver
	type, we consider inherent candidates before extension candidates.
	If there are multiple matching candidates in a group, we report an
	error, except that multiple impls of the same trait are treated as a
	single match. Otherwise we pick the first match we find.</p>
	<p>In the case of our example, the first step is <code>Rc<Box<[T; 3]>></code>,
	which does not itself match any candidate. But when we autoref it, we
	get the type <code>&Rc<Box<[T; 3]>></code> which matches <code>&Rc<U></code>. We would then
	recursively consider all where-clauses that appear on the impl: if
	those match (or we cannot rule out that they do), then this is the
	method we would pick. Otherwise, we would continue down the series of
	steps.</p>

	</main>

	<nav class="nav-wrapper" aria-label="Page navigation">
	<!-- Mobile navigation buttons -->
	<a rel="prev" href="type-checking.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="variance.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="type-checking.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="variance.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>