rustc-dev-guide/query.html

431 lines
24 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>Queries: demand-driven compilation - 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/query.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="queries-demand-driven-compilation"><a class="header" href="#queries-demand-driven-compilation">Queries: demand-driven compilation</a></h1>
<ul>
<li><a href="#invoking-queries">Invoking queries</a></li>
<li><a href="#how-the-compiler-executes-a-query">How the compiler executes a query</a>
<ul>
<li><a href="#providers">Providers</a></li>
<li><a href="#how-providers-are-set-up">How providers are set up</a>
<ul>
<li><a href="#how-are-providers-registered">How are providers registered?</a></li>
<li><a href="#adding-a-new-provider">Adding a new provider</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#adding-a-new-query">Adding a new query</a></li>
<li><a href="#external-links">External links</a></li>
</ul>
<p>As described in <a href="overview.html#queries">Overview of the compiler</a>, the Rust compiler
is still (as of <!-- date-check --> July 2021) transitioning from a
traditional "pass-based" setup to a "demand-driven" system. The compiler query
system is the key to rustc's demand-driven organization.
The idea is pretty simple. Instead of entirely independent passes
(parsing, type-checking, etc.), a set of function-like <em>queries</em>
compute information about the input source. For example,
there is a query called <code>type_of</code> that, given the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_span/def_id/struct.DefId.html"><code>DefId</code></a> of
some item, will compute the type of that item and return it to you.</p>
<p>Query execution is <em>memoized</em>. The first time you invoke a
query, it will go do the computation, but the next time, the result is
returned from a hashtable. Moreover, query execution fits nicely into
<em>incremental computation</em>; the idea is roughly that, when you invoke a
query, the result <em>may</em> be returned to you by loading stored data
from disk.<sup class="footnote-reference" id="fr-incr-comp-detail-1"><a href="#footnote-incr-comp-detail">1</a></sup></p>
<p>Eventually, we want the entire compiler
control-flow to be query driven. There will effectively be one
top-level query (<code>compile</code>) that will run compilation on a crate; this
will in turn demand information about that crate, starting from the
<em>end</em>. For example:</p>
<ul>
<li>The <code>compile</code> query might demand to get a list of codegen-units
(i.e. modules that need to be compiled by LLVM).</li>
<li>But computing the list of codegen-units would invoke some subquery
that returns the list of all modules defined in the Rust source.</li>
<li>That query in turn would invoke something asking for the HIR.</li>
<li>This keeps going further and further back until we wind up doing the
actual parsing.</li>
</ul>
<p>Although this vision is not fully realized, large sections of the
compiler (for example, generating <a href="mir/index.html">MIR</a>) currently work exactly like this.</p>
<h2 id="invoking-queries"><a class="header" href="#invoking-queries">Invoking queries</a></h2>
<p>Invoking a query is simple. The <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TyCtxt.html"><code>TyCtxt</code></a> ("type context") struct offers a method
for each defined query. For example, to invoke the <code>type_of</code>
query, you would just do this:</p>
<pre><code class="language-rust ignore">let ty = tcx.type_of(some_def_id);</code></pre>
<h2 id="how-the-compiler-executes-a-query"><a class="header" href="#how-the-compiler-executes-a-query">How the compiler executes a query</a></h2>
<p>So you may be wondering what happens when you invoke a query
method. The answer is that, for each query, the compiler maintains a
cache if your query has already been executed, then, the answer is
simple: we clone the return value out of the cache and return it
(therefore, you should try to ensure that the return types of queries
are cheaply cloneable; insert an <code>Rc</code> if necessary).</p>
<h3 id="providers"><a class="header" href="#providers">Providers</a></h3>
<p>If, however, the query is <em>not</em> in the cache, then the compiler will
call the corresponding <strong>provider</strong> function. A provider is a function
implemented in a specific module and <strong>manually registered</strong> into the
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/struct.Providers.html"><code>Providers</code></a> struct during compiler initialization.
The macro system generates the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/struct.Providers.html"><code>Providers</code></a> struct,
which acts as a function table for all query implementations, where each
field is a function pointer to the actual provider.</p>
<p><strong>Note:</strong> The <code>Providers</code> struct is generated by macros and acts as a function table for all query implementations.
It is <strong>not</strong> a Rust trait, but a plain struct with function pointer fields.</p>
<p><strong>Providers are defined per-crate.</strong> The compiler maintains,
internally, a table of providers for every crate, at least
conceptually. Right now, there are really two sets: the providers for
queries about the <strong>local crate</strong> (that is, the one being compiled)
and providers for queries about <strong>external crates</strong> (that is,
dependencies of the local crate). Note that what determines the crate
that a query is targeting is not the <em>kind</em> of query, but the <em>key</em>.
For example, when you invoke <code>tcx.type_of(def_id)</code>, that could be a
local query or an external query, depending on what crate the <code>def_id</code>
is referring to (see the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/keys/trait.Key.html"><code>self::keys::Key</code></a> trait for more
information on how that works).</p>
<p>Providers always have the same signature:</p>
<pre><code class="language-rust ignore">fn provider&lt;'tcx&gt;(
tcx: TyCtxt&lt;'tcx&gt;,
key: QUERY_KEY,
) -&gt; QUERY_RESULT {
...
}</code></pre>
<p>Providers take two arguments: the <code>tcx</code> and the query key.
They return the result of the query.</p>
<p>N.B. Most of the <code>rustc_*</code> crates only provide <strong>local
providers</strong>. Almost all <strong>extern providers</strong> wind up going through the
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_metadata/index.html"><code>rustc_metadata</code> crate</a>, which loads the information
from the crate metadata. But in some cases there are crates that
provide queries for <em>both</em> local and external crates, in which case
they define both a <code>provide</code> and a <code>provide_extern</code> function, through
<a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_codegen_ssa/back/symbol_export/fn.wasm_import_module_map.html"><code>wasm_import_module_map</code></a>, that <code>rustc_driver</code> can invoke.</p>
<h3 id="how-providers-are-set-up"><a class="header" href="#how-providers-are-set-up">How providers are set up</a></h3>
<p>When the tcx is created, it is given the providers by its creator using
the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/struct.Providers.html"><code>Providers</code></a> struct. This struct is generated by
the macros here, but it is basically a big list of function pointers:</p>
<pre><code class="language-rust ignore">struct Providers {
type_of: for&lt;'tcx&gt; fn(TyCtxt&lt;'tcx&gt;, DefId) -&gt; Ty&lt;'tcx&gt;,
// ... one field for each query
}</code></pre>
<h4 id="how-are-providers-registered"><a class="header" href="#how-are-providers-registered">How are providers registered?</a></h4>
<p>The <code>Providers</code> struct is filled in during compiler initialization, mainly by the <code>rustc_driver</code> crate.<br />
But the actual provider functions are implemented in various <code>rustc_*</code> crates (like <code>rustc_middle</code>, <code>rustc_hir_analysis</code>, etc).</p>
<p>To register providers, each crate exposes a <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/hir/fn.provide.html"><code>provide</code></a> function that looks like this:</p>
<pre><code class="language-rust ignore">pub fn provide(providers: &amp;mut Providers) {
*providers = Providers {
type_of,
// ... add more providers here
..*providers
};
}</code></pre>
<ul>
<li>This function takes a mutable reference to the <code>Providers</code> struct and sets the fields to point to the correct provider functions.</li>
<li>You can also assign fields individually, e.g. <code>providers.type_of = type_of;</code>.</li>
</ul>
<h4 id="adding-a-new-provider"><a class="header" href="#adding-a-new-provider">Adding a new provider</a></h4>
<p>Suppose you want to add a new query called <code>fubar</code>. You would:</p>
<ol>
<li>Implement the provider function:
<pre><code class="language-rust ignore">fn fubar&lt;'tcx&gt;(tcx: TyCtxt&lt;'tcx&gt;, key: DefId) -&gt; Fubar&lt;'tcx&gt; { ... }</code></pre>
</li>
<li>Register it in the <code>provide</code> function:
<pre><code class="language-rust ignore">pub fn provide(providers: &amp;mut Providers) {
*providers = Providers {
fubar,
..*providers
};
}</code></pre>
</li>
</ol>
<hr />
<h2 id="adding-a-new-query"><a class="header" href="#adding-a-new-query">Adding a new query</a></h2>
<p>How do you add a new query?
Defining a query takes place in two steps:</p>
<ol>
<li>Declare the query name, its arguments and description.</li>
<li>Supply query providers where needed.</li>
</ol>
<p>To declare the query name and arguments, you simply add an entry to
the big macro invocation in <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/index.html"><code>compiler/rustc_middle/src/query/mod.rs</code></a>.
Then you need to add a documentation comment to it with some <em>internal</em> description.
Then, provide the <code>desc</code> attribute which contains a <em>user-facing</em> description of the query.
The <code>desc</code> attribute is shown to the user in query cycles.</p>
<p>This looks something like:</p>
<pre><code class="language-rust ignore">rustc_queries! {
/// Records the type of every item.
query type_of(key: DefId) -&gt; Ty&lt;'tcx&gt; {
cache_on_disk_if { key.is_local() }
desc { |tcx| "computing the type of `{}`", tcx.def_path_str(key) }
}
...
}</code></pre>
<p>A query definition has the following form:</p>
<pre><code class="language-rust ignore">query type_of(key: DefId) -&gt; Ty&lt;'tcx&gt; { ... }
^^^^^ ^^^^^^^ ^^^^^ ^^^^^^^^ ^^^
| | | | |
| | | | query modifiers
| | | result type
| | query key type
| name of query
query keyword</code></pre>
<p>Let's go over these elements one by one:</p>
<ul>
<li><strong>Query keyword:</strong> indicates a start of a query definition.</li>
<li><strong>Name of query:</strong> the name of the query method
(<code>tcx.type_of(..)</code>). Also used as the name of a struct
(<code>ty::queries::type_of</code>) that will be generated to represent
this query.</li>
<li><strong>Query key type:</strong> the type of the argument to this query.
This type must implement the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/query/keys/trait.Key.html"><code>ty::query::keys::Key</code></a> trait, which
defines (for example) how to map it to a crate, and so forth.</li>
<li><strong>Result type of query:</strong> the type produced by this query. This type
should (a) not use <code>RefCell</code> or other interior mutability and (b) be
cheaply cloneable. Interning or using <code>Rc</code> or <code>Arc</code> is recommended for
non-trivial data types.<sup class="footnote-reference" id="fr-steal-1"><a href="#footnote-steal">2</a></sup></li>
<li><strong>Query modifiers:</strong> various flags and options that customize how the
query is processed (mostly with respect to <a href="queries/incremental-compilation-in-detail.html#query-modifiers">incremental compilation</a>).</li>
</ul>
<p>So, to add a query:</p>
<ul>
<li>Add an entry to <code>rustc_queries!</code> using the format above.</li>
<li>Link the provider by modifying the appropriate <code>provide</code> method;
or add a new one if needed and ensure that <code>rustc_driver</code> is invoking it.</li>
</ul>
<h2 id="external-links"><a class="header" href="#external-links">External links</a></h2>
<p>Related design ideas, and tracking issues:</p>
<ul>
<li>Design document: <a href="https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md">On-demand Rustc incremental design doc</a></li>
<li>Tracking Issue: <a href="https://github.com/rust-lang/rust/issues/42293">"Red/Green" dependency tracking in compiler</a></li>
</ul>
<p>More discussion and issues:</p>
<ul>
<li><a href="https://github.com/rust-lang/rust/issues/42633">GitHub issue #42633</a></li>
<li><a href="https://internals.rust-lang.org/t/incremental-compilation-beta/4721">Incremental Compilation Beta</a></li>
<li><a href="https://blog.rust-lang.org/2016/09/08/incremental.html">Incremental Compilation Announcement</a></li>
</ul>
<hr>
<ol class="footnote-definition"><li id="footnote-incr-comp-detail">
<p>The <a href="queries/incremental-compilation-in-detail.html">Incremental compilation in detail</a> chapter gives a more
in-depth description of what queries are and how they work.
If you intend to write a query of your own, this is a good read. <a href="#fr-incr-comp-detail-1"></a></p>
</li>
<li id="footnote-steal">
<p>The one exception to those rules is the <code>ty::steal::Steal</code> type,
which is used to cheaply modify MIR in place. See the definition
of <code>Steal</code> for more details. New uses of <code>Steal</code> should <strong>not</strong> be
added without alerting <code>@rust-lang/compiler</code>. <a href="#fr-steal-1"></a></p>
</li>
</ol>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="compiler-src.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="queries/query-evaluation-model-in-detail.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="compiler-src.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="queries/query-evaluation-model-in-detail.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>