traits/hrtb.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>Higher-ranked trait bounds - 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/traits/hrtb.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="higher-ranked-trait-bounds"><a class="header" href="#higher-ranked-trait-bounds">Higher-ranked trait bounds</a></h1>
 <p>One of the more subtle concepts in trait resolution is <em>higher-ranked trait
 bounds</em>. An example of such a bound is <code>for&lt;'a&gt; MyTrait&lt;&amp;'a isize&gt;</code>.
 Let's walk through how selection on higher-ranked trait references
 works.</p>
 <h2 id="basic-matching-and-placeholder-leaks"><a class="header" href="#basic-matching-and-placeholder-leaks">Basic matching and placeholder leaks</a></h2>
 <p>Suppose we have a trait <code>Foo</code>:</p>
 <pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
 </span><span class="boring">fn main() {
 </span>trait Foo&lt;X&gt; {
     fn foo(&amp;self, x: X) { }
 }
 <span class="boring">}</span></code></pre></pre>
 <p>Let's say we have a function <code>want_hrtb</code> that wants a type which
 implements <code>Foo&lt;&amp;'a isize&gt;</code> for any <code>'a</code>:</p>
 <pre><code class="language-rust ignore">fn want_hrtb&lt;T&gt;() where T : for&lt;'a&gt; Foo&lt;&amp;'a isize&gt; { ... }</code></pre>
 <p>Now we have a struct <code>AnyInt</code> that implements <code>Foo&lt;&amp;'a isize&gt;</code> for any
 <code>'a</code>:</p>
 <pre><code class="language-rust ignore">struct AnyInt;
 impl&lt;'a&gt; Foo&lt;&amp;'a isize&gt; for AnyInt { }</code></pre>
 <p>And the question is, does <code>AnyInt : for&lt;'a&gt; Foo&lt;&amp;'a isize&gt;</code>? We want the
 answer to be yes. The algorithm for figuring it out is closely related
 to the subtyping for higher-ranked types (which is described <a href="./hrtb.html">here</a>
 and also in a <a href="https://www.microsoft.com/en-us/research/publication/practical-type-inference-for-arbitrary-rank-types">paper by SPJ</a>. If you wish to understand higher-ranked
 subtyping, we recommend you read the paper). There are a few parts:</p>
 <ol>
 <li>Replace bound regions in the obligation with placeholders.</li>
 <li>Match the impl against the <a href="../appendix/glossary.html#placeholder">placeholder</a> obligation.</li>
 <li>Check for <em>placeholder leaks</em>.</li>
 </ol>
 <p>So let's work through our example.</p>
 <ol>
 <li>
 <p>The first thing we would do is to
 replace the bound region in the obligation with a placeholder, yielding
 <code>AnyInt : Foo&lt;&amp;'0 isize&gt;</code> (here <code>'0</code> represents placeholder region #0).
 Note that we now have no quantifiers;
 in terms of the compiler type, this changes from a <code>ty::PolyTraitRef</code>
 to a <code>TraitRef</code>. We would then create the <code>TraitRef</code> from the impl,
 using fresh variables for it's bound regions (and thus getting
 <code>Foo&lt;&amp;'$a isize&gt;</code>, where <code>'$a</code> is the inference variable for <code>'a</code>).</p>
 </li>
 <li>
 <p>Next
 we relate the two trait refs, yielding a graph with the constraint
 that <code>'0 == '$a</code>.</p>
 </li>
 <li>
 <p>Finally, we check for placeholder "leaks" – a
 leak is basically any attempt to relate a placeholder region to another
 placeholder region, or to any region that pre-existed the impl match.
 The leak check is done by searching from the placeholder region to find
 the set of regions that it is related to in any way. This is called
 the "taint" set. To pass the check, that set must consist <em>solely</em> of
 itself and region variables from the impl. If the taint set includes
 any other region, then the match is a failure. In this case, the taint
 set for <code>'0</code> is <code>{'0, '$a}</code>, and hence the check will succeed.</p>
 </li>
 </ol>
 <p>Let's consider a failure case. Imagine we also have a struct</p>
 <pre><code class="language-rust ignore">struct StaticInt;
 impl Foo&lt;&amp;'static isize&gt; for StaticInt;</code></pre>
 <p>We want the obligation <code>StaticInt : for&lt;'a&gt; Foo&lt;&amp;'a isize&gt;</code> to be
 considered unsatisfied. The check begins just as before. <code>'a</code> is
 replaced with a placeholder <code>'0</code> and the impl trait reference is instantiated to
 <code>Foo&lt;&amp;'static isize&gt;</code>. When we relate those two, we get a constraint
 like <code>'static == '0</code>. This means that the taint set for <code>'0</code> is <code>{'0, 'static}</code>, which fails the leak check.</p>
 <p><strong>TODO</strong>: This is because <code>'static</code> is not a region variable but is in the
 taint set, right?</p>
 <h2 id="higher-ranked-trait-obligations"><a class="header" href="#higher-ranked-trait-obligations">Higher-ranked trait obligations</a></h2>
 <p>Once the basic matching is done, we get to another interesting topic:
 how to deal with impl obligations. I'll work through a simple example
 here. Imagine we have the traits <code>Foo</code> and <code>Bar</code> and an associated impl:</p>
 <pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
 </span><span class="boring">fn main() {
 </span>trait Foo&lt;X&gt; {
     fn foo(&amp;self, x: X) { }
 }

 trait Bar&lt;X&gt; {
     fn bar(&amp;self, x: X) { }
 }

 impl&lt;X,F&gt; Foo&lt;X&gt; for F
     where F : Bar&lt;X&gt;
 {
 }
 <span class="boring">}</span></code></pre></pre>
 <p>Now let's say we have an obligation <code>Baz: for&lt;'a&gt; Foo&lt;&amp;'a isize&gt;</code> and we match
 this impl. What obligation is generated as a result? We want to get
 <code>Baz: for&lt;'a&gt; Bar&lt;&amp;'a isize&gt;</code>, but how does that happen?</p>
 <p>After the matching, we are in a position where we have a placeholder
 substitution like <code>X =&gt; &amp;'0 isize</code>. If we apply this substitution to the
 impl obligations, we get <code>F : Bar&lt;&amp;'0 isize&gt;</code>. Obviously this is not
 directly usable because the placeholder region <code>'0</code> cannot leak out of
 our computation.</p>
 <p>What we do is to create an inverse mapping from the taint set of <code>'0</code>
 back to the original bound region (<code>'a</code>, here) that <code>'0</code> resulted
 from. (This is done in <code>higher_ranked::plug_leaks</code>). We know that the
 leak check passed, so this taint set consists solely of the placeholder
 region itself plus various intermediate region variables. We then walk
 the trait-reference and convert every region in that taint set back to
 a late-bound region, so in this case we'd wind up with
 <code>Baz: for&lt;'a&gt; Bar&lt;&amp;'a isize&gt;</code>.</p>

                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="../traits/resolution.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="../traits/caching.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="../traits/resolution.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="../traits/caching.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>Higher-ranked trait bounds - 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/traits/hrtb.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="higher-ranked-trait-bounds"><a class="header" href="#higher-ranked-trait-bounds">Higher-ranked trait bounds</a></h1>
	<p>One of the more subtle concepts in trait resolution is <em>higher-ranked trait
	bounds</em>. An example of such a bound is <code>for<'a> MyTrait<&'a isize></code>.
	Let's walk through how selection on higher-ranked trait references
	works.</p>
	<h2 id="basic-matching-and-placeholder-leaks"><a class="header" href="#basic-matching-and-placeholder-leaks">Basic matching and placeholder leaks</a></h2>
	<p>Suppose we have a trait <code>Foo</code>:</p>
	<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
	</span><span class="boring">fn main() {
	</span>trait Foo<X> {
	fn foo(&self, x: X) { }
	}
	<span class="boring">}</span></code></pre></pre>
	<p>Let's say we have a function <code>want_hrtb</code> that wants a type which
	implements <code>Foo<&'a isize></code> for any <code>'a</code>:</p>
	<pre><code class="language-rust ignore">fn want_hrtb<T>() where T : for<'a> Foo<&'a isize> { ... }</code></pre>
	<p>Now we have a struct <code>AnyInt</code> that implements <code>Foo<&'a isize></code> for any
	<code>'a</code>:</p>
	<pre><code class="language-rust ignore">struct AnyInt;
	impl<'a> Foo<&'a isize> for AnyInt { }</code></pre>
	<p>And the question is, does <code>AnyInt : for<'a> Foo<&'a isize></code>? We want the
	answer to be yes. The algorithm for figuring it out is closely related
	to the subtyping for higher-ranked types (which is described <a href="./hrtb.html">here</a>
	and also in a <a href="https://www.microsoft.com/en-us/research/publication/practical-type-inference-for-arbitrary-rank-types">paper by SPJ</a>. If you wish to understand higher-ranked
	subtyping, we recommend you read the paper). There are a few parts:</p>
	<ol>
	<li>Replace bound regions in the obligation with placeholders.</li>
	<li>Match the impl against the <a href="../appendix/glossary.html#placeholder">placeholder</a> obligation.</li>
	<li>Check for <em>placeholder leaks</em>.</li>
	</ol>
	<p>So let's work through our example.</p>
	<ol>
	<li>
	<p>The first thing we would do is to
	replace the bound region in the obligation with a placeholder, yielding
	<code>AnyInt : Foo<&'0 isize></code> (here <code>'0</code> represents placeholder region #0).
	Note that we now have no quantifiers;
	in terms of the compiler type, this changes from a <code>ty::PolyTraitRef</code>
	to a <code>TraitRef</code>. We would then create the <code>TraitRef</code> from the impl,
	using fresh variables for it's bound regions (and thus getting
	<code>Foo<&'$a isize></code>, where <code>'$a</code> is the inference variable for <code>'a</code>).</p>
	</li>
	<li>
	<p>Next
	we relate the two trait refs, yielding a graph with the constraint
	that <code>'0 == '$a</code>.</p>
	</li>
	<li>
	<p>Finally, we check for placeholder "leaks" – a
	leak is basically any attempt to relate a placeholder region to another
	placeholder region, or to any region that pre-existed the impl match.
	The leak check is done by searching from the placeholder region to find
	the set of regions that it is related to in any way. This is called
	the "taint" set. To pass the check, that set must consist <em>solely</em> of
	itself and region variables from the impl. If the taint set includes
	any other region, then the match is a failure. In this case, the taint
	set for <code>'0</code> is <code>{'0, '$a}</code>, and hence the check will succeed.</p>
	</li>
	</ol>
	<p>Let's consider a failure case. Imagine we also have a struct</p>
	<pre><code class="language-rust ignore">struct StaticInt;
	impl Foo<&'static isize> for StaticInt;</code></pre>
	<p>We want the obligation <code>StaticInt : for<'a> Foo<&'a isize></code> to be
	considered unsatisfied. The check begins just as before. <code>'a</code> is
	replaced with a placeholder <code>'0</code> and the impl trait reference is instantiated to
	<code>Foo<&'static isize></code>. When we relate those two, we get a constraint
	like <code>'static == '0</code>. This means that the taint set for <code>'0</code> is <code>{'0, 'static}</code>, which fails the leak check.</p>
	<p><strong>TODO</strong>: This is because <code>'static</code> is not a region variable but is in the
	taint set, right?</p>
	<h2 id="higher-ranked-trait-obligations"><a class="header" href="#higher-ranked-trait-obligations">Higher-ranked trait obligations</a></h2>
	<p>Once the basic matching is done, we get to another interesting topic:
	how to deal with impl obligations. I'll work through a simple example
	here. Imagine we have the traits <code>Foo</code> and <code>Bar</code> and an associated impl:</p>
	<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
	</span><span class="boring">fn main() {
	</span>trait Foo<X> {
	fn foo(&self, x: X) { }
	}

	trait Bar<X> {
	fn bar(&self, x: X) { }
	}

	impl<X,F> Foo<X> for F
	where F : Bar<X>
	{
	}
	<span class="boring">}</span></code></pre></pre>
	<p>Now let's say we have an obligation <code>Baz: for<'a> Foo<&'a isize></code> and we match
	this impl. What obligation is generated as a result? We want to get
	<code>Baz: for<'a> Bar<&'a isize></code>, but how does that happen?</p>
	<p>After the matching, we are in a position where we have a placeholder
	substitution like <code>X => &'0 isize</code>. If we apply this substitution to the
	impl obligations, we get <code>F : Bar<&'0 isize></code>. Obviously this is not
	directly usable because the placeholder region <code>'0</code> cannot leak out of
	our computation.</p>
	<p>What we do is to create an inverse mapping from the taint set of <code>'0</code>
	back to the original bound region (<code>'a</code>, here) that <code>'0</code> resulted
	from. (This is done in <code>higher_ranked::plug_leaks</code>). We know that the
	leak check passed, so this taint set consists solely of the placeholder
	region itself plus various intermediate region variables. We then walk
	the trait-reference and convert every region in that taint set back to
	a late-bound region, so in this case we'd wind up with
	<code>Baz: for<'a> Bar<&'a isize></code>.</p>

	</main>

	<nav class="nav-wrapper" aria-label="Page navigation">
	<!-- Mobile navigation buttons -->
	<a rel="prev" href="../traits/resolution.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="../traits/caching.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="../traits/resolution.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="../traits/caching.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>