mirror
/
rustc-dev-guide
mirror of https://github.com/rust-lang/rustc-dev-guide.git
1
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
rustc-dev-guide/ty-fold.html

298 lines
17 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!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 -->
<!-- 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/ty-fold.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>
<!-- 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&lt;'tcx&gt; {
def_id: DefId,
ty: Ty&lt;'tcx&gt;,
}</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&lt;'tcx&gt;
my_foldable.subst(..., subst)
impl TypeFoldable for MyFoldable {
fn super_fold_with(&amp;self, folder: &amp;mut impl TypeFolder&lt;'tcx&gt;) -&gt; 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&lt;Vec&lt;X&gt;&gt;</code>. The
<code>ty::Ty</code> would look like: <code>Adt(Vec, &amp;[Adt(Vec, &amp;[Param(X)])])</code>. If we want to do <code>subst(X =&gt; 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, &amp;[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, &amp;[Adt(Vec, &amp;[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/master/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>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink