| <!DOCTYPE HTML> |
| <html lang="en" class="light sidebar-visible" dir="ltr"> |
| <head> |
| <!-- Book generated using mdBook --> |
| <meta charset="UTF-8"> |
| <title>TypeFolder and TypeFoldable - 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/main/src/ty-fold.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> |
| <!-- date-check: may 2024 --> |
| <h1 id="typefoldable-and-typefolder"><a class="header" href="#typefoldable-and-typefolder"><code>TypeFoldable</code> and <code>TypeFolder</code></a></h1> |
| <p>In <a href="ty_module/instantiating_binders.html">a previous chapter</a>, we discussed instantiating binders. |
| This involves looking at everything inside of a <code>Early(Binder)</code> |
| to find any usages of the bound vars in order to replace them. |
| Binders can wrap an arbitrary Rust type <code>T</code>, not just a <code>Ty</code>. |
| So, how do we implement the <code>instantiate</code> methods on the <code>Early/Binder</code> types?</p> |
| <p>The answer is a couple of traits: |
| <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.TypeFoldable.html"><code>TypeFoldable</code></a> |
| and |
| <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.TypeFolder.html"><code>TypeFolder</code></a>.</p> |
| <ul> |
| <li><code>TypeFoldable</code> is implemented by types that embed type information. It allows you to recursively |
| process the contents of the <code>TypeFoldable</code> and do stuff to them.</li> |
| <li><code>TypeFolder</code> defines what you want to do with the types you encounter while processing the |
| <code>TypeFoldable</code>.</li> |
| </ul> |
| <p>For example, the <code>TypeFolder</code> trait has a method <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/trait.TypeFolder.html#method.fold_ty"><code>fold_ty</code></a> |
| that takes a type as input and returns a new type as a result. |
| <code>TypeFoldable</code> invokes the <code>TypeFolder</code> <code>fold_foo</code> methods on itself, |
| giving the <code>TypeFolder</code> access to its contents (the types, regions, etc that are contained within).</p> |
| <p>You can think of it with this analogy to the iterator combinators we have come to love in Rust:</p> |
| <pre><code class="language-rust ignore">vec.iter().map(|e1| foo(e2)).collect() |
| // ^^^^^^^^^^^^ analogous to `TypeFolder` |
| // ^^^ analogous to `TypeFoldable`</code></pre> |
| <p>So to reiterate:</p> |
| <ul> |
| <li><code>TypeFolder</code> is a trait that defines a “map” operation.</li> |
| <li><code>TypeFoldable</code> is a trait that is implemented by things that embed types.</li> |
| </ul> |
| <p>In the case of <code>subst</code>, we can see that it is implemented as a <code>TypeFolder</code>: <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_type_ir/binder/struct.ArgFolder.html"><code>ArgFolder</code></a>. |
| Looking at its implementation, we see where the actual substitutions are happening.</p> |
| <p>However, you might also notice that the implementation calls this <code>super_fold_with</code> method. What is |
| that? It is a method of <code>TypeFoldable</code>. Consider the following <code>TypeFoldable</code> type <code>MyFoldable</code>:</p> |
| <pre><code class="language-rust ignore">struct MyFoldable<'tcx> { |
| def_id: DefId, |
| ty: Ty<'tcx>, |
| }</code></pre> |
| <p>The <code>TypeFolder</code> can call <code>super_fold_with</code> on <code>MyFoldable</code> if it just wants to replace some of the |
| fields of <code>MyFoldable</code> with new values. If it instead wants to replace the whole <code>MyFoldable</code> with a |
| different one, it would call <code>fold_with</code> instead (a different method on <code>TypeFoldable</code>).</p> |
| <p>In almost all cases, we don’t want to replace the whole struct; we only want to replace <code>ty::Ty</code>s in |
| the struct, so usually we call <code>super_fold_with</code>. A typical implementation that <code>MyFoldable</code> could |
| have might do something like this:</p> |
| <pre><code class="language-rust ignore">my_foldable: MyFoldable<'tcx> |
| my_foldable.subst(..., subst) |
| |
| impl TypeFoldable for MyFoldable { |
| fn super_fold_with(&self, folder: &mut impl TypeFolder<'tcx>) -> MyFoldable { |
| MyFoldable { |
| def_id: self.def_id.fold_with(folder), |
| ty: self.ty.fold_with(folder), |
| } |
| } |
| |
| fn super_visit_with(..) { } |
| }</code></pre> |
| <p>Notice that here, we implement <code>super_fold_with</code> to go over the fields of <code>MyFoldable</code> and call |
| <code>fold_with</code> on <em>them</em>. That is, a folder may replace <code>def_id</code> and <code>ty</code>, but not the whole |
| <code>MyFoldable</code> struct.</p> |
| <p>Here is another example to put things together: suppose we have a type like <code>Vec<Vec<X>></code>. The |
| <code>ty::Ty</code> would look like: <code>Adt(Vec, &[Adt(Vec, &[Param(X)])])</code>. If we want to do <code>subst(X => u32)</code>, |
| then we would first look at the overall type. We would see that there are no substitutions to be |
| made at the outer level, so we would descend one level and look at <code>Adt(Vec, &[Param(X)])</code>. There |
| are still no substitutions to be made here, so we would descend again. Now we are looking at |
| <code>Param(X)</code>, which can be substituted, so we replace it with <code>u32</code>. We can’t descend any more, so we |
| are done, and the overall result is <code>Adt(Vec, &[Adt(Vec, &[u32])])</code>.</p> |
| <p>One last thing to mention: often when folding over a <code>TypeFoldable</code>, we don’t want to change most |
| things. We only want to do something when we reach a type. That means there may be a lot of |
| <code>TypeFoldable</code> types whose implementations basically just forward to their fields’ <code>TypeFoldable</code> |
| implementations. Such implementations of <code>TypeFoldable</code> tend to be pretty tedious to write by hand. |
| For this reason, there is a <code>derive</code> macro that allows you to <code>#![derive(TypeFoldable)]</code>. It is |
| defined <a href="https://github.com/rust-lang/rust/blob/HEAD/compiler/rustc_macros/src/type_foldable.rs">here</a>.</p> |
| <p><strong><code>subst</code></strong> In the case of substitutions the <a href="https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L440-L451">actual folder</a> |
| is going to be doing the indexing we’ve already mentioned. |
| There we define a <code>Folder</code> and call <code>fold_with</code> on the <code>TypeFoldable</code> to process yourself. |
| Then <a href="https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L512-L536">fold_ty</a> the method that process each type it looks for a <code>ty::Param</code> and for those |
| it replaces it for something from the list of substitutions, otherwise recursively process the type. |
| To replace it, calls <a href="https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L552-L587">ty_for_param</a> |
| and all that does is index into the list of substitutions with the index of the <code>Param</code>.</p> |
| |
| </main> |
| |
| <nav class="nav-wrapper" aria-label="Page navigation"> |
| <!-- Mobile navigation buttons --> |
| <a rel="prev" href="ty_module/param_ty_const_regions.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="normalization.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="ty_module/param_ty_const_regions.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="normalization.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> |
