solve/caching.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>Caching - 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 -->
         <link rel="stylesheet" href="../pagetoc.css">


         <!-- 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.js";
         </script>
         <!-- Start loading toc.js asap -->
         <script src="../toc.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="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 = false;
             }
             if (sidebar === 'visible') {
                 sidebar_toggle.checked = true;
             } else {
                 html.classList.remove('sidebar-visible');
             }
         </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 (`/`)" 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/solve/caching.md" title="Suggest an edit" aria-label="Suggest an edit" rel="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">
                         <div class="search-wrapper">
                             <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                             <div class="spinner-wrapper">
                                 <i class="fa fa-spinner fa-spin"></i>
                             </div>
                         </div>
                     </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="caching-in-the-new-trait-solver"><a class="header" href="#caching-in-the-new-trait-solver">Caching in the new trait solver</a></h1>
 <p>Caching results of the trait solver is necessary for performance.
 We have to make sure that it is sound. Caching is handled by the
 <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L102-L117"><code>SearchGraph</code></a></p>
 <h2 id="the-global-cache"><a class="header" href="#the-global-cache">The global cache</a></h2>
 <p>At its core, the cache is fairly straightforward. When evaluating a goal, we
 check whether it's in the global cache. If so, we reuse that entry. If not, we
 compute the goal and then store its result in the cache.</p>
 <p>To handle incremental compilation the computation of a goal happens inside of
 <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L391"><code>DepGraph::with_anon_task</code></a> which creates a new <code>DepNode</code> which depends on all queries
 used inside of this computation. When accessing the global cache we then read this
 <code>DepNode</code>, manually adding a dependency edge to all the queries used: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L78">source</a>.</p>
 <h3 id="dealing-with-overflow"><a class="header" href="#dealing-with-overflow">Dealing with overflow</a></h3>
 <p>Hitting the recursion limit is not fatal in the new trait solver but instead simply
 causes it to return ambiguity: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L276">source</a>. Whether we hit the recursion limit
 can therefore change the result without resulting in a compilation failure. This
 means we must consider the remaining available depth when accessing a cache result.</p>
 <p>We do this by storing more information in the cache entry. For goals whose evaluation
 did not reach the recursion limit, we simply store its reached depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L102">source</a>.
 These results can freely be used as long as the current <code>available_depth</code> is higher than
 its <code>reached_depth</code>: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L76-L86">source</a>. We then update the reached depth of the
 current goal to make sure that whether we've used the global cache entry is not
 observable: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L308">source</a>.</p>
 <p>For goals which reach the recursion limit we currently only use the cached result if the
 available depth <em>exactly matches</em> the depth of the entry. The cache entry for each goal
 therefore contains a separate result for each remaining depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L124">source</a>.<sup class="footnote-reference" id="fr-1-1"><a href="#footnote-1">1</a></sup></p>
 <h2 id="handling-cycles"><a class="header" href="#handling-cycles">Handling cycles</a></h2>
 <p>The trait solver has to support cycles. These cycles are either inductive or coinductive,
 depending on the participating goals. See the <a href="./coinduction.html">chapter on coinduction</a> for more details.
 We distinguish between the cycle heads and the cycle root: a stack entry is a
 cycle head if it recursively accessed. The <em>root</em> is the deepest goal on the stack which
 is involved in any cycle. Given the following dependency tree, <code>A</code> and <code>B</code> are both cycle
 heads, while only <code>A</code> is a root.</p>
 <pre class="mermaid">graph TB
     A --&gt; B
     B --&gt; C
     C --&gt; B
     C --&gt; A
 </pre>
 <p>The result of cycle participants depends on the result of goals still on the stack.
 However, we are currently computing that result, so its result is still unknown. This is
 handled by evaluating cycle heads until we reach a fixpoint. In the first iteration, we
 return either success or overflow with no constraints, depending on whether the cycle is
 coinductive: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L366-L370">source</a>. After evaluating the head of a cycle, we
 check whether its <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L57"><code>provisional_result</code></a> is equal to the result of this iteration. If so,
 we've finished evaluating this cycle and return its result. If not, we update the provisional
 result and reevaluate the goal: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L425-L446">source</a>. After the first iteration it does not
 matter whether cycles are coinductive or inductive. We always use the provisional result.</p>
 <h3 id="only-caching-cycle-roots"><a class="header" href="#only-caching-cycle-roots">Only caching cycle roots</a></h3>
 <p>We cannot move the result of any cycle participant to the global cache until we've
 finished evaluating the cycle root. However, even after we've completely evaluated the
 cycle, we are still forced to discard the result of all participants apart from the root
 itself.</p>
 <p>We track the query dependencies of all global cache entries. This causes the caching of
 cycle participants to be non-trivial. We cannot simply reuse the <code>DepNode</code> of the cycle
 root.<sup class="footnote-reference" id="fr-2-1"><a href="#footnote-2">2</a></sup> If we have a cycle <code>A -&gt; B -&gt; A</code>, then the <code>DepNode</code> for <code>A</code> contains a dependency
 from <code>A -&gt; B</code>. Reusing this entry for <code>B</code> may break if the source is changed. The <code>B -&gt; A</code>
 edge may not exist anymore and <code>A</code> may have been completely removed. This can easily result
 in an ICE.</p>
 <p>However, it's even worse as the result of a cycle can change depending on which goal is
 the root: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/tests/ui/traits/next-solver/cycles/coinduction/incompleteness-unstable-result.rs#L4-L16">example</a>. This forces us to weaken caching even further.
 We must not use a cache entry of a cycle root, if there exists a stack entry, which was
 a participant of its cycle involving that root. We do this by storing all cycle participants
 of a given root in its global cache entry and checking that it contains no element of the
 stack: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L72-L74">source</a>.</p>
 <h3 id="the-provisional-cache"><a class="header" href="#the-provisional-cache">The provisional cache</a></h3>
 <p>TODO: write this :3</p>
 <ul>
 <li>stack dependence of provisional results</li>
 <li>edge case: provisional cache impacts behavior</li>
 </ul>
 <hr>
 <ol class="footnote-definition"><li id="footnote-1">
 <p>This is overly restrictive: if all nested goals return the overflow response with some
 available depth <code>n</code>, then their result should be the same for any depths smaller than <code>n</code>.
 We can implement this optimization in the future. <a href="#fr-1-1">↩</a></p>
 </li>
 <li id="footnote-2">
 <p>summarizing the relevant <a href="https://rust-lang.zulipchat.com/#narrow/stream/364551-t-types.2Ftrait-system-refactor/topic/global.20cache">Zulip thread</a> <a href="#fr-2-1">↩</a></p>
 </li>
 </ol>
                     </main>

                     <nav class="nav-wrapper" aria-label="Page navigation">
                         <!-- Mobile navigation buttons -->
                             <a rel="prev" href="../solve/coinduction.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="../solve/proof-trees.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="../solve/coinduction.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="../solve/proof-trees.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>
         <script src="../pagetoc.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>Caching - 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 -->
	<link rel="stylesheet" href="../pagetoc.css">


	<!-- 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.js";
	</script>
	<!-- Start loading toc.js asap -->
	<script src="../toc.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="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 = false;
	}
	if (sidebar === 'visible') {
	sidebar_toggle.checked = true;
	} else {
	html.classList.remove('sidebar-visible');
	}
	</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 (`/`)" 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/solve/caching.md" title="Suggest an edit" aria-label="Suggest an edit" rel="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">
	<div class="search-wrapper">
	<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
	<div class="spinner-wrapper">
	<i class="fa fa-spinner fa-spin"></i>
	</div>
	</div>
	</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="caching-in-the-new-trait-solver"><a class="header" href="#caching-in-the-new-trait-solver">Caching in the new trait solver</a></h1>
	<p>Caching results of the trait solver is necessary for performance.
	We have to make sure that it is sound. Caching is handled by the
	<a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L102-L117"><code>SearchGraph</code></a></p>
	<h2 id="the-global-cache"><a class="header" href="#the-global-cache">The global cache</a></h2>
	<p>At its core, the cache is fairly straightforward. When evaluating a goal, we
	check whether it's in the global cache. If so, we reuse that entry. If not, we
	compute the goal and then store its result in the cache.</p>
	<p>To handle incremental compilation the computation of a goal happens inside of
	<a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L391"><code>DepGraph::with_anon_task</code></a> which creates a new <code>DepNode</code> which depends on all queries
	used inside of this computation. When accessing the global cache we then read this
	<code>DepNode</code>, manually adding a dependency edge to all the queries used: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L78">source</a>.</p>
	<h3 id="dealing-with-overflow"><a class="header" href="#dealing-with-overflow">Dealing with overflow</a></h3>
	<p>Hitting the recursion limit is not fatal in the new trait solver but instead simply
	causes it to return ambiguity: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L276">source</a>. Whether we hit the recursion limit
	can therefore change the result without resulting in a compilation failure. This
	means we must consider the remaining available depth when accessing a cache result.</p>
	<p>We do this by storing more information in the cache entry. For goals whose evaluation
	did not reach the recursion limit, we simply store its reached depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L102">source</a>.
	These results can freely be used as long as the current <code>available_depth</code> is higher than
	its <code>reached_depth</code>: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L76-L86">source</a>. We then update the reached depth of the
	current goal to make sure that whether we've used the global cache entry is not
	observable: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L308">source</a>.</p>
	<p>For goals which reach the recursion limit we currently only use the cached result if the
	available depth <em>exactly matches</em> the depth of the entry. The cache entry for each goal
	therefore contains a separate result for each remaining depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L124">source</a>.<sup class="footnote-reference" id="fr-1-1"><a href="#footnote-1">1</a></sup></p>
	<h2 id="handling-cycles"><a class="header" href="#handling-cycles">Handling cycles</a></h2>
	<p>The trait solver has to support cycles. These cycles are either inductive or coinductive,
	depending on the participating goals. See the <a href="./coinduction.html">chapter on coinduction</a> for more details.
	We distinguish between the cycle heads and the cycle root: a stack entry is a
	cycle head if it recursively accessed. The <em>root</em> is the deepest goal on the stack which
	is involved in any cycle. Given the following dependency tree, <code>A</code> and <code>B</code> are both cycle
	heads, while only <code>A</code> is a root.</p>
	<pre class="mermaid">graph TB
	A --> B
	B --> C
	C --> B
	C --> A
	</pre>
	<p>The result of cycle participants depends on the result of goals still on the stack.
	However, we are currently computing that result, so its result is still unknown. This is
	handled by evaluating cycle heads until we reach a fixpoint. In the first iteration, we
	return either success or overflow with no constraints, depending on whether the cycle is
	coinductive: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L366-L370">source</a>. After evaluating the head of a cycle, we
	check whether its <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L57"><code>provisional_result</code></a> is equal to the result of this iteration. If so,
	we've finished evaluating this cycle and return its result. If not, we update the provisional
	result and reevaluate the goal: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L425-L446">source</a>. After the first iteration it does not
	matter whether cycles are coinductive or inductive. We always use the provisional result.</p>
	<h3 id="only-caching-cycle-roots"><a class="header" href="#only-caching-cycle-roots">Only caching cycle roots</a></h3>
	<p>We cannot move the result of any cycle participant to the global cache until we've
	finished evaluating the cycle root. However, even after we've completely evaluated the
	cycle, we are still forced to discard the result of all participants apart from the root
	itself.</p>
	<p>We track the query dependencies of all global cache entries. This causes the caching of
	cycle participants to be non-trivial. We cannot simply reuse the <code>DepNode</code> of the cycle
	root.<sup class="footnote-reference" id="fr-2-1"><a href="#footnote-2">2</a></sup> If we have a cycle <code>A -> B -> A</code>, then the <code>DepNode</code> for <code>A</code> contains a dependency
	from <code>A -> B</code>. Reusing this entry for <code>B</code> may break if the source is changed. The <code>B -> A</code>
	edge may not exist anymore and <code>A</code> may have been completely removed. This can easily result
	in an ICE.</p>
	<p>However, it's even worse as the result of a cycle can change depending on which goal is
	the root: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/tests/ui/traits/next-solver/cycles/coinduction/incompleteness-unstable-result.rs#L4-L16">example</a>. This forces us to weaken caching even further.
	We must not use a cache entry of a cycle root, if there exists a stack entry, which was
	a participant of its cycle involving that root. We do this by storing all cycle participants
	of a given root in its global cache entry and checking that it contains no element of the
	stack: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L72-L74">source</a>.</p>
	<h3 id="the-provisional-cache"><a class="header" href="#the-provisional-cache">The provisional cache</a></h3>
	<p>TODO: write this :3</p>
	<ul>
	<li>stack dependence of provisional results</li>
	<li>edge case: provisional cache impacts behavior</li>
	</ul>
	<hr>
	<ol class="footnote-definition"><li id="footnote-1">
	<p>This is overly restrictive: if all nested goals return the overflow response with some
	available depth <code>n</code>, then their result should be the same for any depths smaller than <code>n</code>.
	We can implement this optimization in the future. <a href="#fr-1-1">↩</a></p>
	</li>
	<li id="footnote-2">
	<p>summarizing the relevant <a href="https://rust-lang.zulipchat.com/#narrow/stream/364551-t-types.2Ftrait-system-refactor/topic/global.20cache">Zulip thread</a> <a href="#fr-2-1">↩</a></p>
	</li>
	</ol>
	</main>

	<nav class="nav-wrapper" aria-label="Page navigation">
	<!-- Mobile navigation buttons -->
	<a rel="prev" href="../solve/coinduction.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="../solve/proof-trees.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="../solve/coinduction.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="../solve/proof-trees.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>
	<script src="../pagetoc.js"></script>



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