rustc_query_system/query/
caches.rs

1use std::fmt::Debug;
2use std::hash::Hash;
3use std::sync::OnceLock;
4
5use rustc_data_structures::sharded::ShardedHashMap;
6pub use rustc_data_structures::vec_cache::VecCache;
7use rustc_hir::def_id::LOCAL_CRATE;
8use rustc_index::Idx;
9use rustc_span::def_id::{DefId, DefIndex};
10
11use crate::dep_graph::DepNodeIndex;
12
13/// Trait for types that serve as an in-memory cache for query results,
14/// for a given key (argument) type and value (return) type.
15///
16/// Types implementing this trait are associated with actual key/value types
17/// by the `Cache` associated type of the `rustc_middle::query::Key` trait.
18pub trait QueryCache: Sized {
19    type Key: Hash + Eq + Copy + Debug;
20    type Value: Copy;
21
22    /// Returns the cached value (and other information) associated with the
23    /// given key, if it is present in the cache.
24    fn lookup(&self, key: &Self::Key) -> Option<(Self::Value, DepNodeIndex)>;
25
26    /// Adds a key/value entry to this cache.
27    ///
28    /// Called by some part of the query system, after having obtained the
29    /// value by executing the query or loading a cached value from disk.
30    fn complete(&self, key: Self::Key, value: Self::Value, index: DepNodeIndex);
31
32    fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex));
33}
34
35/// In-memory cache for queries whose keys aren't suitable for any of the
36/// more specialized kinds of cache. Backed by a sharded hashmap.
37pub struct DefaultCache<K, V> {
38    cache: ShardedHashMap<K, (V, DepNodeIndex)>,
39}
40
41impl<K, V> Default for DefaultCache<K, V> {
42    fn default() -> Self {
43        DefaultCache { cache: Default::default() }
44    }
45}
46
47impl<K, V> QueryCache for DefaultCache<K, V>
48where
49    K: Eq + Hash + Copy + Debug,
50    V: Copy,
51{
52    type Key = K;
53    type Value = V;
54
55    #[inline(always)]
56    fn lookup(&self, key: &K) -> Option<(V, DepNodeIndex)> {
57        self.cache.get(key)
58    }
59
60    #[inline]
61    fn complete(&self, key: K, value: V, index: DepNodeIndex) {
62        // We may be overwriting another value. This is all right, since the dep-graph
63        // will check that the fingerprint matches.
64        self.cache.insert(key, (value, index));
65    }
66
67    fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
68        for shard in self.cache.lock_shards() {
69            for (k, v) in shard.iter() {
70                f(k, &v.0, v.1);
71            }
72        }
73    }
74}
75
76/// In-memory cache for queries whose key type only has one value (e.g. `()`).
77/// The cache therefore only needs to store one query return value.
78pub struct SingleCache<V> {
79    cache: OnceLock<(V, DepNodeIndex)>,
80}
81
82impl<V> Default for SingleCache<V> {
83    fn default() -> Self {
84        SingleCache { cache: OnceLock::new() }
85    }
86}
87
88impl<V> QueryCache for SingleCache<V>
89where
90    V: Copy,
91{
92    type Key = ();
93    type Value = V;
94
95    #[inline(always)]
96    fn lookup(&self, _key: &()) -> Option<(V, DepNodeIndex)> {
97        self.cache.get().copied()
98    }
99
100    #[inline]
101    fn complete(&self, _key: (), value: V, index: DepNodeIndex) {
102        self.cache.set((value, index)).ok();
103    }
104
105    fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
106        if let Some(value) = self.cache.get() {
107            f(&(), &value.0, value.1)
108        }
109    }
110}
111
112/// In-memory cache for queries whose key is a [`DefId`].
113///
114/// Selects between one of two internal caches, depending on whether the key
115/// is a local ID or foreign-crate ID.
116pub struct DefIdCache<V> {
117    /// Stores the local DefIds in a dense map. Local queries are much more often dense, so this is
118    /// a win over hashing query keys at marginal memory cost (~5% at most) compared to FxHashMap.
119    local: VecCache<DefIndex, V, DepNodeIndex>,
120    foreign: DefaultCache<DefId, V>,
121}
122
123impl<V> Default for DefIdCache<V> {
124    fn default() -> Self {
125        DefIdCache { local: Default::default(), foreign: Default::default() }
126    }
127}
128
129impl<V> QueryCache for DefIdCache<V>
130where
131    V: Copy,
132{
133    type Key = DefId;
134    type Value = V;
135
136    #[inline(always)]
137    fn lookup(&self, key: &DefId) -> Option<(V, DepNodeIndex)> {
138        if key.krate == LOCAL_CRATE {
139            self.local.lookup(&key.index)
140        } else {
141            self.foreign.lookup(key)
142        }
143    }
144
145    #[inline]
146    fn complete(&self, key: DefId, value: V, index: DepNodeIndex) {
147        if key.krate == LOCAL_CRATE {
148            self.local.complete(key.index, value, index)
149        } else {
150            self.foreign.complete(key, value, index)
151        }
152    }
153
154    fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
155        self.local.iter(&mut |key, value, index| {
156            f(&DefId { krate: LOCAL_CRATE, index: *key }, value, index);
157        });
158        self.foreign.iter(f);
159    }
160}
161
162impl<K, V> QueryCache for VecCache<K, V, DepNodeIndex>
163where
164    K: Idx + Eq + Hash + Copy + Debug,
165    V: Copy,
166{
167    type Key = K;
168    type Value = V;
169
170    #[inline(always)]
171    fn lookup(&self, key: &K) -> Option<(V, DepNodeIndex)> {
172        self.lookup(key)
173    }
174
175    #[inline]
176    fn complete(&self, key: K, value: V, index: DepNodeIndex) {
177        self.complete(key, value, index)
178    }
179
180    fn iter(&self, f: &mut dyn FnMut(&Self::Key, &Self::Value, DepNodeIndex)) {
181        self.iter(f)
182    }
183}