traits/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>Trait solving - 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-de23e50b.svg">
         <link rel="shortcut icon" href="../favicon-8114d1fc.png">
         <link rel="stylesheet" href="../css/variables-8adf115d.css">
         <link rel="stylesheet" href="../css/general-2459343d.css">
         <link rel="stylesheet" href="../css/chrome-ae938929.css">
         <link rel="stylesheet" href="../css/print-9e4910d8.css" media="print">

         <!-- Fonts -->
         <link rel="stylesheet" href="../fonts/fonts-9644e21d.css">

         <!-- Highlight.js Stylesheets -->
         <link rel="stylesheet" id="mdbook-highlight-css" href="../highlight-493f70e1.css">
         <link rel="stylesheet" id="mdbook-tomorrow-night-css" href="../tomorrow-night-4c0ae647.css">
         <link rel="stylesheet" id="mdbook-ayu-highlight-css" href="../ayu-highlight-3fdfc3ac.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";
             window.path_to_searchindex_js = "../searchindex-1dcc4ecd.js";
         </script>
         <!-- Start loading toc.js asap -->
         <script src="../toc-39e8ee02.js"></script>
     </head>
     <body>
     <div id="mdbook-help-container">
         <div id="mdbook-help-popup">
             <h2 class="mdbook-help-title">Keyboard shortcuts</h2>
             <div>
                 <p>Press <kbd>←</kbd> or <kbd>→</kbd> to navigate between chapters</p>
                 <p>Press <kbd>S</kbd> or <kbd>/</kbd> to search in the book</p>
                 <p>Press <kbd>?</kbd> to show this help</p>
                 <p>Press <kbd>Esc</kbd> to hide this help</p>
             </div>
         </div>
     </div>
     <div id="mdbook-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="mdbook-sidebar-toggle-anchor" class="hidden">

         <!-- Hide / unhide sidebar before it is displayed -->
         <script>
             let sidebar = null;
             const sidebar_toggle = document.getElementById("mdbook-sidebar-toggle-anchor");
             if (document.body.clientWidth >= 1080) {
                 try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                 sidebar = sidebar || 'visible';
             } else {
                 sidebar = 'hidden';
                 sidebar_toggle.checked = false;
             }
             if (sidebar === 'visible') {
                 sidebar_toggle.checked = true;
             } else {
                 html.classList.remove('sidebar-visible');
             }
         </script>

         <nav id="mdbook-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="mdbook-sidebar-resize-handle" class="sidebar-resize-handle">
                 <div class="sidebar-resize-indicator"></div>
             </div>
         </nav>

         <div id="mdbook-page-wrapper" class="page-wrapper">

             <div class="page">
                 <div id="mdbook-menu-bar-hover-placeholder"></div>
                 <div id="mdbook-menu-bar" class="menu-bar sticky">
                     <div class="left-buttons">
                         <label id="mdbook-sidebar-toggle" class="icon-button" for="mdbook-sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="mdbook-sidebar">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M0 96C0 78.3 14.3 64 32 64H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32C14.3 128 0 113.7 0 96zM0 256c0-17.7 14.3-32 32-32H416c17.7 0 32 14.3 32 32s-14.3 32-32 32H32c-17.7 0-32-14.3-32-32zM448 416c0 17.7-14.3 32-32 32H32c-17.7 0-32-14.3-32-32s14.3-32 32-32H416c17.7 0 32 14.3 32 32z"/></svg></span>
                         </label>
                         <button id="mdbook-theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="mdbook-theme-list">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M371.3 367.1c27.3-3.9 51.9-19.4 67.2-42.9L600.2 74.1c12.6-19.5 9.4-45.3-7.6-61.2S549.7-4.4 531.1 9.6L294.4 187.2c-24 18-38.2 46.1-38.4 76.1L371.3 367.1zm-19.6 25.4l-116-104.4C175.9 290.3 128 339.6 128 400c0 3.9 .2 7.8 .6 11.6c1.8 17.5-10.2 36.4-27.8 36.4H96c-17.7 0-32 14.3-32 32s14.3 32 32 32H240c61.9 0 112-50.1 112-112c0-2.5-.1-5-.2-7.5z"/></svg></span>
                         </button>
                         <ul id="mdbook-theme-list" class="theme-popup" aria-label="Themes" role="menu">
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-default_theme">Auto</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-light">Light</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-rust">Rust</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-coal">Coal</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-navy">Navy</button></li>
                             <li role="none"><button role="menuitem" class="theme" id="mdbook-theme-ayu">Ayu</button></li>
                         </ul>
                         <button id="mdbook-search-toggle" class="icon-button" type="button" title="Search (`/`)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="/ s" aria-controls="mdbook-searchbar">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M416 208c0 45.9-14.9 88.3-40 122.7L502.6 457.4c12.5 12.5 12.5 32.8 0 45.3s-32.8 12.5-45.3 0L330.7 376c-34.4 25.2-76.8 40-122.7 40C93.1 416 0 322.9 0 208S93.1 0 208 0S416 93.1 416 208zM208 352c79.5 0 144-64.5 144-144s-64.5-144-144-144S64 128.5 64 208s64.5 144 144 144z"/></svg></span>
                         </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">
                             <span class=fa-svg id="print-button"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M128 0C92.7 0 64 28.7 64 64v96h64V64H354.7L384 93.3V160h64V93.3c0-17-6.7-33.3-18.7-45.3L400 18.7C388 6.7 371.7 0 354.7 0H128zM384 352v32 64H128V384 368 352H384zm64 32h32c17.7 0 32-14.3 32-32V256c0-35.3-28.7-64-64-64H64c-35.3 0-64 28.7-64 64v96c0 17.7 14.3 32 32 32H64v64c0 35.3 28.7 64 64 64H384c35.3 0 64-28.7 64-64V384zm-16-88c-13.3 0-24-10.7-24-24s10.7-24 24-24s24 10.7 24 24s-10.7 24-24 24z"/></svg></span>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
                             <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 496 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M165.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6zm-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3zm44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9zM244.8 8C106.1 8 0 113.3 0 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C428.2 457.8 496 362.9 496 252 496 113.3 383.5 8 244.8 8zM97.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1zm-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7zm32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1zm-11.4-14.7c-1.6 1-1.6 3.6 0 5.9 1.6 2.3 4.3 3.3 5.6 2.3 1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2z"/></svg></span>
                         </a>
                         <a href="https://github.com/rust-lang/rustc-dev-guide/edit/main/src/traits/resolution.md" title="Suggest an edit" aria-label="Suggest an edit" rel="edit">
                             <span class=fa-svg id="git-edit-button"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M421.7 220.3l-11.3 11.3-22.6 22.6-205 205c-6.6 6.6-14.8 11.5-23.8 14.1L30.8 511c-8.4 2.5-17.5 .2-23.7-6.1S-1.5 489.7 1 481.2L38.7 353.1c2.6-9 7.5-17.2 14.1-23.8l205-205 22.6-22.6 11.3-11.3 33.9 33.9 62.1 62.1 33.9 33.9zM96 353.9l-9.3 9.3c-.9 .9-1.6 2.1-2 3.4l-25.3 86 86-25.3c1.3-.4 2.5-1.1 3.4-2l9.3-9.3H112c-8.8 0-16-7.2-16-16V353.9zM453.3 19.3l39.4 39.4c25 25 25 65.5 0 90.5l-14.5 14.5-22.6 22.6-11.3 11.3-33.9-33.9-62.1-62.1L314.3 67.7l11.3-11.3 22.6-22.6 14.5-14.5c25-25 65.5-25 90.5 0z"/></svg></span>
                         </a>

                     </div>
                 </div>

                 <div id="mdbook-search-wrapper" class="hidden">
                     <form id="mdbook-searchbar-outer" class="searchbar-outer">
                         <div class="search-wrapper">
                             <input type="search" id="mdbook-searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="mdbook-searchresults-outer" aria-describedby="searchresults-header">
                             <div class="spinner-wrapper">
                                 <span class=fa-svg id="fa-spin"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M304 48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zm0 416c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM48 304c26.5 0 48-21.5 48-48s-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48zm464-48c0-26.5-21.5-48-48-48s-48 21.5-48 48s21.5 48 48 48s48-21.5 48-48zM142.9 437c18.7-18.7 18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zm0-294.2c18.7-18.7 18.7-49.1 0-67.9S93.7 56.2 75 75s-18.7 49.1 0 67.9s49.1 18.7 67.9 0zM369.1 437c18.7 18.7 49.1 18.7 67.9 0s18.7-49.1 0-67.9s-49.1-18.7-67.9 0s-18.7 49.1 0 67.9z"/></svg></span>
                             </div>
                         </div>
                     </form>
                     <div id="mdbook-searchresults-outer" class="searchresults-outer hidden">
                         <div id="mdbook-searchresults-header" class="searchresults-header"></div>
                         <ul id="mdbook-searchresults">
                         </ul>
                     </div>
                 </div>

                 <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                 <script>
                     document.getElementById('mdbook-sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                     document.getElementById('mdbook-sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                     Array.from(document.querySelectorAll('#mdbook-sidebar a')).forEach(function(link) {
                         link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                     });
                 </script>

                 <div id="mdbook-content" class="content">
                     <main>
                         <h1 id="trait-resolution-old-style"><a class="header" href="#trait-resolution-old-style">Trait resolution (old-style)</a></h1>
 <p>This chapter describes the general process of <em>trait resolution</em> and points out
 some non-obvious things.</p>
 <p><strong>Note:</strong> This chapter (and its subchapters) describe how the trait
 solver <strong>currently</strong> works. However, we are in the process of
 designing a new trait solver. If you’d prefer to read about <em>that</em>,
 see <a href="./chalk.html"><em>this</em> subchapter</a>.</p>
 <h2 id="major-concepts"><a class="header" href="#major-concepts">Major concepts</a></h2>
 <p>Trait resolution is the process of pairing up an impl with each
 reference to a trait. So, for example, if there is a generic function like:</p>
 <pre><code class="language-rust ignore">fn clone_slice&lt;T:Clone&gt;(x: &amp;[T]) -&gt; Vec&lt;T&gt; { ... }</code></pre>
 <p>and then a call to that function:</p>
 <pre><code class="language-rust ignore">let v: Vec&lt;isize&gt; = clone_slice(&amp;[1, 2, 3])</code></pre>
 <p>it is the job of trait resolution to figure out whether there exists an impl of
 (in this case) <code>isize : Clone</code>.</p>
 <p>Note that in some cases, like generic functions, we may not be able to
 find a specific impl, but we can figure out that the caller must
 provide an impl. For example, consider the body of <code>clone_slice</code>:</p>
 <pre><code class="language-rust ignore">fn clone_slice&lt;T:Clone&gt;(x: &amp;[T]) -&gt; Vec&lt;T&gt; {
     let mut v = Vec::new();
     for e in &amp;x {
         v.push((*e).clone()); // (*)
     }
 }</code></pre>
 <p>The line marked <code>(*)</code> is only legal if <code>T</code> (the type of <code>*e</code>)
 implements the <code>Clone</code> trait. Naturally, since we don’t know what <code>T</code>
 is, we can’t find the specific impl; but based on the bound <code>T:Clone</code>,
 we can say that there exists an impl which the caller must provide.</p>
 <p>We use the term <em>obligation</em> to refer to a trait reference in need of
 an impl. Basically, the trait resolution system resolves an obligation
 by proving that an appropriate impl does exist.</p>
 <p>During type checking, we do not store the results of trait selection.
 We simply wish to verify that trait selection will succeed. Then
 later, at codegen time, when we have all concrete types available, we
 can repeat the trait selection to choose an actual implementation, which
 will then be generated in the output binary.</p>
 <h2 id="overview"><a class="header" href="#overview">Overview</a></h2>
 <p>Trait resolution consists of three major parts:</p>
 <ul>
 <li>
 <p><strong>Selection</strong>: Deciding how to resolve a specific obligation. For
 example, selection might decide that a specific obligation can be
 resolved by employing an impl which matches the <code>Self</code> type, or by using a
 parameter bound (e.g. <code>T: Trait</code>). In the case of an impl, selecting one
 obligation can create <em>nested obligations</em> because of where clauses
 on the impl itself. It may also require evaluating those nested
 obligations to resolve ambiguities.</p>
 </li>
 <li>
 <p><strong>Fulfillment</strong>: The fulfillment code is what tracks that obligations
 are completely fulfilled. Basically it is a worklist of obligations
 to be selected: once selection is successful, the obligation is
 removed from the worklist and any nested obligations are enqueued.
 Fulfillment constrains inference variables.</p>
 </li>
 <li>
 <p><strong>Evaluation</strong>: Checks whether obligations holds without constraining
 any inference variables. Used by selection.</p>
 </li>
 </ul>
 <h2 id="selection"><a class="header" href="#selection">Selection</a></h2>
 <p>Selection is the process of deciding whether an obligation can be
 resolved and, if so, how it is to be resolved (via impl, where clause, etc).
 The main interface is the <code>select()</code> function, which takes an obligation
 and returns a <code>SelectionResult</code>. There are three possible outcomes:</p>
 <ul>
 <li>
 <p><code>Ok(Some(selection))</code> – yes, the obligation can be resolved, and
 <code>selection</code> indicates how. If the impl was resolved via an impl,
 then <code>selection</code> may also indicate nested obligations that are required
 by the impl.</p>
 </li>
 <li>
 <p><code>Ok(None)</code> – we are not yet sure whether the obligation can be
 resolved or not. This happens most commonly when the obligation
 contains unbound type variables.</p>
 </li>
 <li>
 <p><code>Err(err)</code> – the obligation definitely cannot be resolved due to a
 type error or because there are no impls that could possibly apply.</p>
 </li>
 </ul>
 <p>The basic algorithm for selection is broken into two big phases:
 candidate assembly and confirmation.</p>
 <p>Note that because of how lifetime inference works, it is not possible to
 give back immediate feedback as to whether a unification or subtype
 relationship between lifetimes holds or not. Therefore, lifetime
 matching is <em>not</em> considered during selection. This is reflected in
 the fact that subregion assignment is infallible. This may yield
 lifetime constraints that will later be found to be in error (in
 contrast, the non-lifetime-constraints have already been checked
 during selection and can never cause an error, though naturally they
 may lead to other errors downstream).</p>
 <h3 id="candidate-assembly"><a class="header" href="#candidate-assembly">Candidate assembly</a></h3>
 <p><strong>TODO</strong>: Talk about <em>why</em> we have different candidates, and why it needs to happen in a probe.</p>
 <p>Searches for impls/where-clauses/etc that might
 possibly be used to satisfy the obligation. Each of those is called
 a candidate. To avoid ambiguity, we want to find exactly one
 candidate that is definitively applicable. In some cases, we may not
 know whether an impl/where-clause applies or not – this occurs when
 the obligation contains unbound inference variables.</p>
 <p>The subroutines that decide whether a particular impl/where-clause/etc applies
 to a particular obligation are collectively referred to as the process of
 <em>matching</em>. For <code>impl</code> candidates <!-- date-check: Oct 2022 -->,
 this amounts to unifying the impl header (the <code>Self</code> type and the trait arguments)
 while ignoring  nested obligations. If matching succeeds then we add it
 to a set of candidates. There are other rules when assembling candidates for
 built-in traits such as <code>Copy</code>, <code>Sized</code>, and <code>CoerceUnsized</code>.</p>
 <p>Once this first pass is done, we can examine the set of candidates. If
 it is a singleton set, then we are done: this is the only impl in
 scope that could possibly apply. Otherwise, we can <strong>winnow</strong> down the set
 of candidates by using where clauses and other conditions. Winnowing uses
 <code>evaluate_candidate</code> to check whether the nested obligations may apply.
 If this still leaves more than 1 candidate, we use <code> fn candidate_should_be_dropped_in_favor_of</code>
 to prefer some candidates over others.</p>
 <p>If this reduced set yields a single, unambiguous entry, we’re good to go,
 otherwise the result is considered ambiguous.</p>
 <h4 id="winnowing-resolving-ambiguities"><a class="header" href="#winnowing-resolving-ambiguities">Winnowing: Resolving ambiguities</a></h4>
 <p>But what happens if there are multiple impls where all the types
 unify? Consider this example:</p>
 <pre><code class="language-rust ignore">trait Get {
     fn get(&amp;self) -&gt; Self;
 }

 impl&lt;T: Copy&gt; Get for T {
     fn get(&amp;self) -&gt; T {
         *self
     }
 }

 impl&lt;T: Get&gt; Get for Box&lt;T&gt; {
     fn get(&amp;self) -&gt; Box&lt;T&gt; {
         Box::new(&lt;T&gt;::get(self))
     }
 }</code></pre>
 <p>What happens when we invoke <code>get(&amp;Box::new(1_u16))</code>, for example? In this
 case, the <code>Self</code> type is <code>Box&lt;u16&gt;</code> – that unifies with both impls,
 because the first applies to all types <code>T</code>, and the second to all
 <code>Box&lt;T&gt;</code>. In order for this to be unambiguous, the compiler does a <em>winnowing</em>
 pass that considers <code>where</code> clauses
 and attempts to remove candidates. In this case, the first impl only
 applies if <code>Box&lt;u16&gt; : Copy</code>, which doesn’t hold. After winnowing,
 then, we are left with just one candidate, so we can proceed.</p>
 <h4 id="where-clauses"><a class="header" href="#where-clauses"><code>where</code> clauses</a></h4>
 <p>Besides an impl, the other major way to resolve an obligation is via a
 where clause. The selection process is always given a <a href="../typing_parameter_envs.html">parameter
 environment</a> which contains a list of where clauses, which are
 basically obligations that we can assume are satisfiable. We will iterate
 over that list and check whether our current obligation can be found
 in that list. If so, it is considered satisfied. More precisely, we
 want to check whether there is a where-clause obligation that is for
 the same trait (or some subtrait) and which can match against the obligation.</p>
 <p>Consider this simple example:</p>
 <pre><code class="language-rust ignore">trait A1 {
     fn do_a1(&amp;self);
 }
 trait A2 : A1 { ... }

 trait B {
     fn do_b(&amp;self);
 }

 fn foo&lt;X:A2+B&gt;(x: X) {
     x.do_a1(); // (*)
     x.do_b();  // (#)
 }</code></pre>
 <p>In the body of <code>foo</code>, clearly we can use methods of <code>A1</code>, <code>A2</code>, or <code>B</code>
 on variable <code>x</code>. The line marked <code>(*)</code> will incur an obligation <code>X: A1</code>,
 while the line marked <code>(#)</code> will incur an obligation <code>X: B</code>. Meanwhile,
 the parameter environment will contain two where-clauses: <code>X : A2</code> and <code>X : B</code>.
 For each obligation, then, we search this list of where-clauses. The
 obligation <code>X: B</code> trivially matches against the where-clause <code>X: B</code>.
 To resolve an obligation <code>X:A1</code>, we would note that <code>X:A2</code> implies that <code>X:A1</code>.</p>
 <h3 id="confirmation"><a class="header" href="#confirmation">Confirmation</a></h3>
 <p><em>Confirmation</em> unifies the output type parameters of the trait with the
 values found in the obligation, possibly yielding a type error.</p>
 <p>Suppose we have the following variation of the <code>Convert</code> example in the
 previous section:</p>
 <pre><code class="language-rust ignore">trait Convert&lt;Target&gt; {
     fn convert(&amp;self) -&gt; Target;
 }

 impl Convert&lt;usize&gt; for isize { ... } // isize -&gt; usize
 impl Convert&lt;isize&gt; for usize { ... } // usize -&gt; isize

 let x: isize = ...;
 let y: char = x.convert(); // NOTE: `y: char` now!</code></pre>
 <p>Confirmation is where an error would be reported because the impl specified
 that <code>Target</code> would be <code>usize</code>, but the obligation reported <code>char</code>. Hence the
 result of selection would be an error.</p>
 <p>Note that the candidate impl is chosen based on the <code>Self</code> type, but
 confirmation is done based on (in this case) the <code>Target</code> type parameter.</p>
 <h3 id="selection-during-codegen"><a class="header" href="#selection-during-codegen">Selection during codegen</a></h3>
 <p>As mentioned above, during type checking, we do not store the results of trait
 selection. At codegen time, we repeat the trait selection to choose a particular
 impl for each method call. This is done using <code>fn codegen_select_candidate</code>.
 In this second selection, we do not consider any where-clauses to be in scope
 because we know that each resolution will resolve to a particular impl.</p>
 <p>One interesting twist has to do with nested obligations. In general, in codegen,
 we only need to figure out which candidate applies, and we do not care about nested obligations,
 as these are already assumed to be true. Nonetheless, we <em>do</em> currently fulfill all of them.
 That is because it can sometimes inform the results of type inference.
 That is, we do not have the full substitutions in terms of the type variables
 of the impl available to us, so we must run trait selection to figure
 everything out.</p>

                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="../type-inference.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                 <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
                             </a>

                             <a rel="next prefetch" href="../traits/hrtb.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                 <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
                             </a>

                         <div style="clear: both"></div>
                     </nav>
                 </div>
             </div>

             <nav class="nav-wide-wrapper" aria-label="Page navigation">
                     <a rel="prev" href="../type-inference.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                         <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M41.4 233.4c-12.5 12.5-12.5 32.8 0 45.3l160 160c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L109.3 256 246.6 118.6c12.5-12.5 12.5-32.8 0-45.3s-32.8-12.5-45.3 0l-160 160z"/></svg></span>
                     </a>

                     <a rel="next prefetch" href="../traits/hrtb.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                         <span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M278.6 233.4c12.5 12.5 12.5 32.8 0 45.3l-160 160c-12.5 12.5-32.8 12.5-45.3 0s-12.5-32.8 0-45.3L210.7 256 73.4 118.6c-12.5-12.5-12.5-32.8 0-45.3s32.8-12.5 45.3 0l160 160z"/></svg></span>
                     </a>
             </nav>

         </div>

         <template id=fa-eye><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 576 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M288 32c-80.8 0-145.5 36.8-192.6 80.6C48.6 156 17.3 208 2.5 243.7c-3.3 7.9-3.3 16.7 0 24.6C17.3 304 48.6 356 95.4 399.4C142.5 443.2 207.2 480 288 480s145.5-36.8 192.6-80.6c46.8-43.5 78.1-95.4 93-131.1c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C433.5 68.8 368.8 32 288 32zM432 256c0 79.5-64.5 144-144 144s-144-64.5-144-144s64.5-144 144-144s144 64.5 144 144zM288 192c0 35.3-28.7 64-64 64c-11.5 0-22.3-3-31.6-8.4c-.2 2.8-.4 5.5-.4 8.4c0 53 43 96 96 96s96-43 96-96s-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6z"/></svg></span></template>
         <template id=fa-eye-slash><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 640 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M38.8 5.1C28.4-3.1 13.3-1.2 5.1 9.2S-1.2 34.7 9.2 42.9l592 464c10.4 8.2 25.5 6.3 33.7-4.1s6.3-25.5-4.1-33.7L525.6 386.7c39.6-40.6 66.4-86.1 79.9-118.4c3.3-7.9 3.3-16.7 0-24.6c-14.9-35.7-46.2-87.7-93-131.1C465.5 68.8 400.8 32 320 32c-68.2 0-125 26.3-169.3 60.8L38.8 5.1zM223.1 149.5C248.6 126.2 282.7 112 320 112c79.5 0 144 64.5 144 144c0 24.9-6.3 48.3-17.4 68.7L408 294.5c5.2-11.8 8-24.8 8-38.5c0-53-43-96-96-96c-2.8 0-5.6 .1-8.4 .4c5.3 9.3 8.4 20.1 8.4 31.6c0 10.2-2.4 19.8-6.6 28.3l-90.3-70.8zm223.1 298L373 389.9c-16.4 6.5-34.3 10.1-53 10.1c-79.5 0-144-64.5-144-144c0-6.9 .5-13.6 1.4-20.2L83.1 161.5C60.3 191.2 44 220.8 34.5 243.7c-3.3 7.9-3.3 16.7 0 24.6c14.9 35.7 46.2 87.7 93 131.1C174.5 443.2 239.2 480 320 480c47.8 0 89.9-12.9 126.2-32.5z"/></svg></span></template>
         <template id=fa-copy><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M502.6 70.63l-61.25-61.25C435.4 3.371 427.2 0 418.7 0H255.1c-35.35 0-64 28.66-64 64l.0195 256C192 355.4 220.7 384 256 384h192c35.2 0 64-28.8 64-64V93.25C512 84.77 508.6 76.63 502.6 70.63zM464 320c0 8.836-7.164 16-16 16H255.1c-8.838 0-16-7.164-16-16L239.1 64.13c0-8.836 7.164-16 16-16h128L384 96c0 17.67 14.33 32 32 32h47.1V320zM272 448c0 8.836-7.164 16-16 16H63.1c-8.838 0-16-7.164-16-16L47.98 192.1c0-8.836 7.164-16 16-16H160V128H63.99c-35.35 0-64 28.65-64 64l.0098 256C.002 483.3 28.66 512 64 512h192c35.2 0 64-28.8 64-64v-32h-47.1L272 448z"/></svg></span></template>
         <template id=fa-play><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 384 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M73 39c-14.8-9.1-33.4-9.4-48.5-.9S0 62.6 0 80V432c0 17.4 9.4 33.4 24.5 41.9s33.7 8.1 48.5-.9L361 297c14.3-8.7 23-24.2 23-41s-8.7-32.2-23-41L73 39z"/></svg></span></template>
         <template id=fa-clock-rotate-left><span class=fa-svg><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc. --><path d="M75 75L41 41C25.9 25.9 0 36.6 0 57.9V168c0 13.3 10.7 24 24 24H134.1c21.4 0 32.1-25.9 17-41l-30.8-30.8C155 85.5 203 64 256 64c106 0 192 86 192 192s-86 192-192 192c-40.8 0-78.6-12.7-109.7-34.4c-14.5-10.1-34.4-6.6-44.6 7.9s-6.6 34.4 7.9 44.6C151.2 495 201.7 512 256 512c141.4 0 256-114.6 256-256S397.4 0 256 0C185.3 0 121.3 28.7 75 75zm181 53c-13.3 0-24 10.7-24 24V256c0 6.4 2.5 12.5 7 17l72 72c9.4 9.4 24.6 9.4 33.9 0s9.4-24.6 0-33.9l-65-65V152c0-13.3-10.7-24-24-24z"/></svg></span></template>


         <script>
             window.playground_copyable = true;
         </script>


         <script src="../elasticlunr-ef4e11c1.min.js"></script>
         <script src="../mark-09e88c2c.min.js"></script>
         <script src="../searcher-c2a407aa.js"></script>

         <script src="../clipboard-1626706a.min.js"></script>
         <script src="../highlight-abc7f01d.js"></script>
         <script src="../book-a0b12cfe.js"></script>

         <!-- Custom JS scripts -->
         <script src="../mermaid-cc85ecea.min.js"></script>
         <script src="../mermaid-init-4533fb11.js"></script>


     </div>
     </body>
 </html>