Google Git
Sign in
rust / rustc-guide / refs/heads/gh-pages / . / traits / resolution.html
blob: 254a0868dfb045016004c0386015d725ea5612f2 [file] [log] [blame] [edit]
<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Trait solving - Guide to Rustc Development</title>
<!-- Custom HTML head -->
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="description" content="A guide to developing 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" href="../highlight.css">
<link rel="stylesheet" href="../tomorrow-night.css">
<link rel="stylesheet" href="../ayu-highlight.css">
<!-- Custom theme stylesheets -->
</head>
<body>
<!-- Provide site root to javascript -->
<script type="text/javascript">
var path_to_root = "../";
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
</script>
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script type="text/javascript">
try {
var theme = localStorage.getItem('mdbook-theme');
var 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 type="text/javascript">
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('no-js')
html.classList.remove('light')
html.classList.add(theme);
html.classList.add('js');
</script>
<!-- Hide / unhide sidebar before it is displayed -->
<script type="text/javascript">
var html = document.querySelector('html');
var sidebar = 'hidden';
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
}
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<div class="sidebar-scrollbox">
<ol class="chapter"><li class="chapter-item affix "><a href="../about-this-guide.html">About this guide</a></li><li class="chapter-item affix "><a href="../getting-started.html">Getting Started</a></li><li class="spacer"></li><li class="chapter-item affix "><li class="part-title">Building and debugging rustc</li><li class="chapter-item "><a href="../building/how-to-build-and-run.html"><strong aria-hidden="true">1.</strong> How to Build and Run the Compiler</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../building/prerequisites.html"><strong aria-hidden="true">1.1.</strong> Prerequisites</a></li><li class="chapter-item "><a href="../building/suggested.html"><strong aria-hidden="true">1.2.</strong> Suggested Workflows</a></li><li class="chapter-item "><a href="../building/build-install-distribution-artifacts.html"><strong aria-hidden="true">1.3.</strong> Distribution artifacts</a></li><li class="chapter-item "><a href="../building/compiler-documenting.html"><strong aria-hidden="true">1.4.</strong> Documenting Compiler</a></li><li class="chapter-item "><a href="../rustdoc.html"><strong aria-hidden="true">1.5.</strong> Rustdoc overview</a></li><li class="chapter-item "><a href="../building/new-target.html"><strong aria-hidden="true">1.6.</strong> Adding a new target</a></li></ol></li><li class="chapter-item "><a href="../tests/intro.html"><strong aria-hidden="true">2.</strong> The compiler testing framework</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../tests/running.html"><strong aria-hidden="true">2.1.</strong> Running tests</a></li><li class="chapter-item "><a href="../tests/adding.html"><strong aria-hidden="true">2.2.</strong> Adding new tests</a></li><li class="chapter-item "><a href="../compiletest.html"><strong aria-hidden="true">2.3.</strong> Using compiletest commands to control test execution</a></li></ol></li><li class="chapter-item "><a href="../compiler-debugging.html"><strong aria-hidden="true">3.</strong> Debugging the Compiler</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../tracing.html"><strong aria-hidden="true">3.1.</strong> Using the tracing/logging instrumentation</a></li></ol></li><li class="chapter-item "><a href="../profiling.html"><strong aria-hidden="true">4.</strong> Profiling the compiler</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../profiling/with_perf.html"><strong aria-hidden="true">4.1.</strong> with the linux perf tool</a></li><li class="chapter-item "><a href="../profiling/wpa_profiling.html"><strong aria-hidden="true">4.2.</strong> with Windows Performance Analyzer</a></li></ol></li><li class="chapter-item "><a href="../crates-io.html"><strong aria-hidden="true">5.</strong> crates.io Dependencies</a></li><li class="chapter-item affix "><li class="part-title">Contributing to Rust</li><li class="chapter-item "><a href="../contributing.html"><strong aria-hidden="true">6.</strong> Introduction</a></li><li class="chapter-item "><a href="../compiler-team.html"><strong aria-hidden="true">7.</strong> About the compiler team</a></li><li class="chapter-item "><a href="../git.html"><strong aria-hidden="true">8.</strong> Using Git</a></li><li class="chapter-item "><a href="../rustbot.html"><strong aria-hidden="true">9.</strong> Mastering @rustbot</a></li><li class="chapter-item "><a href="../walkthrough.html"><strong aria-hidden="true">10.</strong> Walkthrough: a typical contribution</a></li><li class="chapter-item "><a href="../bug-fix-procedure.html"><strong aria-hidden="true">11.</strong> Bug Fix Procedure</a></li><li class="chapter-item "><a href="../implementing_new_features.html"><strong aria-hidden="true">12.</strong> Implementing new features</a></li><li class="chapter-item "><a href="../stability.html"><strong aria-hidden="true">13.</strong> Stability attributes</a></li><li class="chapter-item "><a href="../stabilization_guide.html"><strong aria-hidden="true">14.</strong> Stabilizing Features</a></li><li class="chapter-item "><a href="../feature-gates.html"><strong aria-hidden="true">15.</strong> Feature Gates</a></li><li class="chapter-item "><a href="../conventions.html"><strong aria-hidden="true">16.</strong> Coding conventions</a></li><li class="chapter-item "><a href="../notification-groups/about.html"><strong aria-hidden="true">17.</strong> Notification groups</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../notification-groups/arm.html"><strong aria-hidden="true">17.1.</strong> ARM</a></li><li class="chapter-item "><a href="../notification-groups/cleanup-crew.html"><strong aria-hidden="true">17.2.</strong> Cleanup Crew</a></li><li class="chapter-item "><a href="../notification-groups/llvm.html"><strong aria-hidden="true">17.3.</strong> LLVM</a></li><li class="chapter-item "><a href="../notification-groups/risc-v.html"><strong aria-hidden="true">17.4.</strong> RISC-V</a></li><li class="chapter-item "><a href="../notification-groups/windows.html"><strong aria-hidden="true">17.5.</strong> Windows</a></li></ol></li><li class="chapter-item "><a href="../licenses.html"><strong aria-hidden="true">18.</strong> Licenses</a></li><li class="chapter-item affix "><li class="part-title">High-level Compiler Architecture</li><li class="chapter-item "><a href="../part-2-intro.html"><strong aria-hidden="true">19.</strong> Prologue</a></li><li class="chapter-item "><a href="../overview.html"><strong aria-hidden="true">20.</strong> Overview of the Compiler</a></li><li class="chapter-item "><a href="../compiler-src.html"><strong aria-hidden="true">21.</strong> The compiler source code</a></li><li class="chapter-item "><a href="../building/bootstrapping.html"><strong aria-hidden="true">22.</strong> Bootstrapping</a></li><li class="chapter-item "><a href="../query.html"><strong aria-hidden="true">23.</strong> Queries: demand-driven compilation</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../queries/query-evaluation-model-in-detail.html"><strong aria-hidden="true">23.1.</strong> The Query Evaluation Model in Detail</a></li><li class="chapter-item "><a href="../queries/incremental-compilation.html"><strong aria-hidden="true">23.2.</strong> Incremental compilation</a></li><li class="chapter-item "><a href="../queries/incremental-compilation-in-detail.html"><strong aria-hidden="true">23.3.</strong> Incremental compilation In Detail</a></li><li class="chapter-item "><a href="../incrcomp-debugging.html"><strong aria-hidden="true">23.4.</strong> Debugging and Testing</a></li><li class="chapter-item "><a href="../salsa.html"><strong aria-hidden="true">23.5.</strong> Salsa</a></li></ol></li><li class="chapter-item "><a href="../memory.html"><strong aria-hidden="true">24.</strong> Memory Management in Rustc</a></li><li class="chapter-item "><a href="../serialization.html"><strong aria-hidden="true">25.</strong> Serialization in Rustc</a></li><li class="chapter-item "><a href="../parallel-rustc.html"><strong aria-hidden="true">26.</strong> Parallel Compilation</a></li><li class="chapter-item "><a href="../rustdoc-internals.html"><strong aria-hidden="true">27.</strong> Rustdoc internals</a></li><li class="chapter-item affix "><li class="part-title">Source Code Representation</li><li class="chapter-item "><a href="../part-3-intro.html"><strong aria-hidden="true">28.</strong> Prologue</a></li><li class="chapter-item "><a href="../cli.html"><strong aria-hidden="true">29.</strong> Command-line arguments</a></li><li class="chapter-item "><a href="../rustc-driver.html"><strong aria-hidden="true">30.</strong> The Rustc Driver and Interface</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../rustc-driver-interacting-with-the-ast.html"><strong aria-hidden="true">30.1.</strong> Ex: Type checking through rustc_interface</a></li><li class="chapter-item "><a href="../rustc-driver-getting-diagnostics.html"><strong aria-hidden="true">30.2.</strong> Ex: Getting diagnostics through rustc_interface</a></li></ol></li><li class="chapter-item "><a href="../syntax-intro.html"><strong aria-hidden="true">31.</strong> Syntax and the AST</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../the-parser.html"><strong aria-hidden="true">31.1.</strong> Lexing and Parsing</a></li><li class="chapter-item "><a href="../macro-expansion.html"><strong aria-hidden="true">31.2.</strong> Macro expansion</a></li><li class="chapter-item "><a href="../name-resolution.html"><strong aria-hidden="true">31.3.</strong> Name resolution</a></li><li class="chapter-item "><a href="../test-implementation.html"><strong aria-hidden="true">31.4.</strong> #[test] Implementation</a></li><li class="chapter-item "><a href="../panic-implementation.html"><strong aria-hidden="true">31.5.</strong> Panic Implementation</a></li><li class="chapter-item "><a href="../ast-validation.html"><strong aria-hidden="true">31.6.</strong> AST Validation</a></li><li class="chapter-item "><a href="../feature-gate-ck.html"><strong aria-hidden="true">31.7.</strong> Feature Gate Checking</a></li><li class="chapter-item "><a href="../lang-items.html"><strong aria-hidden="true">31.8.</strong> Lang Items</a></li></ol></li><li class="chapter-item "><a href="../hir.html"><strong aria-hidden="true">32.</strong> The HIR (High-level IR)</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../lowering.html"><strong aria-hidden="true">32.1.</strong> Lowering AST to HIR</a></li><li class="chapter-item "><a href="../hir-debugging.html"><strong aria-hidden="true">32.2.</strong> Debugging</a></li></ol></li><li class="chapter-item "><a href="../thir.html"><strong aria-hidden="true">33.</strong> The THIR (Typed High-level IR)</a></li><li class="chapter-item "><a href="../mir/index.html"><strong aria-hidden="true">34.</strong> The MIR (Mid-level IR)</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../mir/construction.html"><strong aria-hidden="true">34.1.</strong> MIR construction</a></li><li class="chapter-item "><a href="../mir/visitor.html"><strong aria-hidden="true">34.2.</strong> MIR visitor and traversal</a></li><li class="chapter-item "><a href="../mir/passes.html"><strong aria-hidden="true">34.3.</strong> MIR passes: getting the MIR for a function</a></li></ol></li><li class="chapter-item "><a href="../identifiers.html"><strong aria-hidden="true">35.</strong> Identifiers in the Compiler</a></li><li class="chapter-item "><a href="../closure.html"><strong aria-hidden="true">36.</strong> Closure expansion</a></li><li class="chapter-item affix "><li class="part-title">Analysis</li><li class="chapter-item "><a href="../part-4-intro.html"><strong aria-hidden="true">37.</strong> Prologue</a></li><li class="chapter-item "><a href="../ty.html"><strong aria-hidden="true">38.</strong> The ty module: representing types</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../generics.html"><strong aria-hidden="true">38.1.</strong> Generics and substitutions</a></li><li class="chapter-item "><a href="../ty-fold.html"><strong aria-hidden="true">38.2.</strong> TypeFolder and TypeFoldable</a></li><li class="chapter-item "><a href="../generic_arguments.html"><strong aria-hidden="true">38.3.</strong> Generic arguments</a></li><li class="chapter-item "><a href="../constants.html"><strong aria-hidden="true">38.4.</strong> Constants in the type system</a></li></ol></li><li class="chapter-item "><a href="../type-inference.html"><strong aria-hidden="true">39.</strong> Type inference</a></li><li class="chapter-item expanded "><a href="../traits/resolution.html" class="active"><strong aria-hidden="true">40.</strong> Trait solving</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../early-late-bound.html"><strong aria-hidden="true">40.1.</strong> Early and Late Bound Parameters</a></li><li class="chapter-item "><a href="../traits/hrtb.html"><strong aria-hidden="true">40.2.</strong> Higher-ranked trait bounds</a></li><li class="chapter-item "><a href="../traits/caching.html"><strong aria-hidden="true">40.3.</strong> Caching subtleties</a></li><li class="chapter-item "><a href="../traits/specialization.html"><strong aria-hidden="true">40.4.</strong> Specialization</a></li><li class="chapter-item "><a href="../traits/chalk.html"><strong aria-hidden="true">40.5.</strong> Chalk-based trait solving</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../traits/lowering-to-logic.html"><strong aria-hidden="true">40.5.1.</strong> Lowering to logic</a></li><li class="chapter-item "><a href="../traits/goals-and-clauses.html"><strong aria-hidden="true">40.5.2.</strong> Goals and clauses</a></li><li class="chapter-item "><a href="../traits/canonical-queries.html"><strong aria-hidden="true">40.5.3.</strong> Canonical queries</a></li></ol></li></ol></li><li class="chapter-item "><a href="../type-checking.html"><strong aria-hidden="true">41.</strong> Type checking</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../method-lookup.html"><strong aria-hidden="true">41.1.</strong> Method Lookup</a></li><li class="chapter-item "><a href="../variance.html"><strong aria-hidden="true">41.2.</strong> Variance</a></li><li class="chapter-item "><a href="../opaque-types-type-alias-impl-trait.html"><strong aria-hidden="true">41.3.</strong> Opaque Types</a></li></ol></li><li class="chapter-item "><a href="../pat-exhaustive-checking.html"><strong aria-hidden="true">42.</strong> Pattern and Exhaustiveness Checking</a></li><li class="chapter-item "><a href="../mir/dataflow.html"><strong aria-hidden="true">43.</strong> MIR dataflow</a></li><li class="chapter-item "><a href="../borrow_check.html"><strong aria-hidden="true">44.</strong> The borrow checker</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../borrow_check/moves_and_initialization.html"><strong aria-hidden="true">44.1.</strong> Tracking moves and initialization</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../borrow_check/moves_and_initialization/move_paths.html"><strong aria-hidden="true">44.1.1.</strong> Move paths</a></li></ol></li><li class="chapter-item "><a href="../borrow_check/type_check.html"><strong aria-hidden="true">44.2.</strong> MIR type checker</a></li><li class="chapter-item "><a href="../borrow_check/region_inference.html"><strong aria-hidden="true">44.3.</strong> Region inference</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../borrow_check/region_inference/constraint_propagation.html"><strong aria-hidden="true">44.3.1.</strong> Constraint propagation</a></li><li class="chapter-item "><a href="../borrow_check/region_inference/lifetime_parameters.html"><strong aria-hidden="true">44.3.2.</strong> Lifetime parameters</a></li><li class="chapter-item "><a href="../borrow_check/region_inference/member_constraints.html"><strong aria-hidden="true">44.3.3.</strong> Member constraints</a></li><li class="chapter-item "><a href="../borrow_check/region_inference/placeholders_and_universes.html"><strong aria-hidden="true">44.3.4.</strong> Placeholders and universes</a></li><li class="chapter-item "><a href="../borrow_check/region_inference/closure_constraints.html"><strong aria-hidden="true">44.3.5.</strong> Closure constraints</a></li><li class="chapter-item "><a href="../borrow_check/region_inference/error_reporting.html"><strong aria-hidden="true">44.3.6.</strong> Error reporting</a></li></ol></li><li class="chapter-item "><a href="../borrow_check/two_phase_borrows.html"><strong aria-hidden="true">44.4.</strong> Two-phase-borrows</a></li></ol></li><li class="chapter-item "><a href="../param_env.html"><strong aria-hidden="true">45.</strong> Parameter Environments</a></li><li class="chapter-item "><a href="../diagnostics.html"><strong aria-hidden="true">46.</strong> Errors and Lints</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../diagnostics/sessiondiagnostic.html"><strong aria-hidden="true">46.1.</strong> Creating Errors With SessionDiagnostic</a></li><li class="chapter-item "><a href="../diagnostics/lintstore.html"><strong aria-hidden="true">46.2.</strong> LintStore</a></li><li class="chapter-item "><a href="../diagnostics/diagnostic-codes.html"><strong aria-hidden="true">46.3.</strong> Diagnostic Codes</a></li><li class="chapter-item "><a href="../diagnostics/diagnostic-items.html"><strong aria-hidden="true">46.4.</strong> Diagnostic Items</a></li></ol></li><li class="chapter-item "><li class="part-title">MIR to Binaries</li><li class="chapter-item "><a href="../part-5-intro.html"><strong aria-hidden="true">47.</strong> Prologue</a></li><li class="chapter-item "><a href="../mir/optimizations.html"><strong aria-hidden="true">48.</strong> MIR optimizations</a></li><li class="chapter-item "><a href="../mir/debugging.html"><strong aria-hidden="true">49.</strong> Debugging</a></li><li class="chapter-item "><a href="../const-eval.html"><strong aria-hidden="true">50.</strong> Constant evaluation</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../miri.html"><strong aria-hidden="true">50.1.</strong> miri const evaluator</a></li></ol></li><li class="chapter-item "><a href="../backend/monomorph.html"><strong aria-hidden="true">51.</strong> Monomorphization</a></li><li class="chapter-item "><a href="../backend/lowering-mir.html"><strong aria-hidden="true">52.</strong> Lowering MIR</a></li><li class="chapter-item "><a href="../backend/codegen.html"><strong aria-hidden="true">53.</strong> Code Generation</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../backend/updating-llvm.html"><strong aria-hidden="true">53.1.</strong> Updating LLVM</a></li><li class="chapter-item "><a href="../backend/debugging.html"><strong aria-hidden="true">53.2.</strong> Debugging LLVM</a></li><li class="chapter-item "><a href="../backend/backend-agnostic.html"><strong aria-hidden="true">53.3.</strong> Backend Agnostic Codegen</a></li><li class="chapter-item "><a href="../backend/implicit-caller-location.html"><strong aria-hidden="true">53.4.</strong> Implicit Caller Location</a></li></ol></li><li class="chapter-item "><a href="../backend/libs-and-metadata.html"><strong aria-hidden="true">54.</strong> Libraries and Metadata</a></li><li class="chapter-item "><a href="../profile-guided-optimization.html"><strong aria-hidden="true">55.</strong> Profile-guided Optimization</a></li><li class="chapter-item "><a href="../llvm-coverage-instrumentation.html"><strong aria-hidden="true">56.</strong> LLVM Source-Based Code Coverage</a></li><li class="chapter-item "><a href="../sanitizers.html"><strong aria-hidden="true">57.</strong> Sanitizers Support</a></li><li class="chapter-item "><a href="../debugging-support-in-rustc.html"><strong aria-hidden="true">58.</strong> Debugging Support in the Rust Compiler</a></li><li class="spacer"></li><li class="chapter-item affix "><a href="../appendix/background.html">Appendix A: Background topics</a></li><li class="chapter-item affix "><a href="../appendix/glossary.html">Appendix B: Glossary</a></li><li class="chapter-item affix "><a href="../appendix/code-index.html">Appendix C: Code Index</a></li><li class="chapter-item affix "><a href="../appendix/compiler-lecture.html">Appendix D: Compiler Lecture Series</a></li><li class="chapter-item affix "><a href="../appendix/bibliography.html">Appendix E: Bibliography</a></li><li class="chapter-item affix "><a href="../appendix/humorust.html">Appendix Z: HumorRust</a></li><li class="spacer"></li></ol>
</div>
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></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 bordered">
<div class="left-buttons">
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</button>
<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="light">Light (default)</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">Guide to Rustc Development</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/tree/master/src/traits/resolution.md?mode&#x3D;edit" 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 type="text/javascript">
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="trait-resolution-old-style"><a class="header" href="#trait-resolution-old-style">Trait resolution (old-style)</a></h1>
<ul>
<li><a href="#major-concepts">Major concepts</a></li>
<li><a href="#overview">Overview</a></li>
<li><a href="#selection">Selection</a>
<ul>
<li><a href="#candidate-assembly">Candidate assembly</a>
<ul>
<li><a href="#the-basic-process-inferring-based-on-the-impls-we-see">The basic process: Inferring based on the impls we see</a></li>
<li><a href="#winnowing-resolving-ambiguities">Winnowing: Resolving ambiguities</a></li>
<li><a href="#where-clauses"><code>where</code> clauses</a></li>
</ul>
</li>
<li><a href="#confirmation">Confirmation</a></li>
<li><a href="#selection-during-translation">Selection during translation</a></li>
</ul>
</li>
</ul>
<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 trans 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.</p>
</li>
<li>
<p><strong>Coherence</strong>: The coherence checks are intended to ensure that there
are never overlapping impls, where two impls could be used with
equal precedence.</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>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>. As of <!-- date: 2021-01 --> January 2021, this amounts to unifying
the <code>Self</code> types, but in the future we may also recursively consider some of the
nested obligations, in the case of an impl.</p>
<p><strong>TODO</strong>: what does &quot;unifying the <code>Self</code> types&quot; mean? The <code>Self</code> of the
obligation with that of an impl?</p>
<p>The basic idea for candidate assembly is to do a first pass in which
we identify all possible candidates. During this pass, all that we do
is try and unify the type parameters. (In particular, we ignore any
nested where clauses.) Presuming that this unification succeeds, the
impl is added as a candidate.</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 winnow down the set
of candidates by using where clauses and other conditions. If this
reduced set yields a single, unambiguous entry, we're good to go,
otherwise the result is considered ambiguous.</p>
<h4 id="the-basic-process-inferring-based-on-the-impls-we-see"><a class="header" href="#the-basic-process-inferring-based-on-the-impls-we-see">The basic process: Inferring based on the impls we see</a></h4>
<p>This process is easier if we work through some examples. Consider
the following trait:</p>
<pre><code class="language-rust ignore">trait Convert&lt;Target&gt; {
fn convert(&amp;self) -&gt; Target;
}
</code></pre>
<p>This trait just has one method. It's about as simple as it gets. It
converts from the (implicit) <code>Self</code> type to the <code>Target</code> type. If we
wanted to permit conversion between <code>isize</code> and <code>usize</code>, we might
implement <code>Convert</code> like so:</p>
<pre><code class="language-rust ignore">impl Convert&lt;usize&gt; for isize { ... } // isize -&gt; usize
impl Convert&lt;isize&gt; for usize { ... } // usize -&gt; isize
</code></pre>
<p>Now imagine there is some code like the following:</p>
<pre><code class="language-rust ignore">let x: isize = ...;
let y = x.convert();
</code></pre>
<p>The call to convert will generate a trait reference <code>Convert&lt;$Y&gt; for isize</code>, where <code>$Y</code> is the type variable representing the type of
<code>y</code>. Of the two impls we can see, the only one that matches is
<code>Convert&lt;usize&gt; for isize</code>. Therefore, we can
select this impl, which will cause the type of <code>$Y</code> to be unified to
<code>usize</code>. (Note that while assembling candidates, we do the initial
unifications in a transaction, so that they don't affect one another.)</p>
<p><strong>TODO</strong>: The example says we can &quot;select&quot; the impl, but this section is
talking specifically about candidate assembly. Does this mean we can sometimes
skip confirmation? Or is this poor wording?
<strong>TODO</strong>: Is the unification of <code>$Y</code> part of trait resolution or type
inference? Or is this not the same type of &quot;inference variable&quot; as in type
inference?</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_it(&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="../param_env.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-translation"><a class="header" href="#selection-during-translation">Selection during translation</a></h3>
<p>As mentioned above, during type checking, we do not store the results of trait
selection. At trans time, we repeat the trait selection to choose a particular
impl for each method call. 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 trans,
we only need to do a &quot;shallow&quot; selection for an obligation. That is, we wish to
identify which impl applies, but we do not (yet) need to decide how to select
any nested obligations. Nonetheless, we <em>do</em> currently do a complete resolution,
and 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>
<p><strong>TODO</strong>: is this still talking about trans?</p>
<p>Here is an example:</p>
<pre><code class="language-rust ignore">trait Foo { ... }
impl&lt;U, T:Bar&lt;U&gt;&gt; Foo for Vec&lt;T&gt; { ... }
impl Bar&lt;usize&gt; for isize { ... }
</code></pre>
<p>After one shallow round of selection for an obligation like <code>Vec&lt;isize&gt; : Foo</code>, we would know which impl we want, and we would know that
<code>T=isize</code>, but we do not know the type of <code>U</code>. We must select the
nested obligation <code>isize : Bar&lt;U&gt;</code> to find out that <code>U=usize</code>.</p>
<p>It would be good to only do <em>just as much</em> nested resolution as
necessary. Currently, though, we just do a full resolution.</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">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="../early-late-bound.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-inference.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" href="../early-late-bound.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 type="text/javascript">
window.playground_copyable = true;
</script>
<script src="../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../mark.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../searcher.js" type="text/javascript" charset="utf-8"></script>
<script src="../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
<script src="../highlight.js" type="text/javascript" charset="utf-8"></script>
<script src="../book.js" type="text/javascript" charset="utf-8"></script>
<!-- Custom JS scripts -->
</body>
</html>