bootstrap/utils/
cache.rs

1//! This module helps you efficiently store and retrieve values using interning.
2//!
3//! Interning is a neat trick that keeps only one copy of identical values, saving memory
4//! and making comparisons super fast. Here, we provide the `Interned<T>` struct and the `Internable` trait
5//! to make interning easy for different data types.
6//!
7//! The `Interner` struct handles caching for common types like `String`, `PathBuf`, and `Vec<String>`,
8//! while the `Cache` struct acts as a write-once storage for linking computation steps with their results.
9//!
10//! # Thread Safety
11//!
12//! We use `Mutex` to make sure interning and retrieval are thread-safe. But keep in mind—once a value is
13//! interned, it sticks around for the entire lifetime of the program.
14
15use std::any::{Any, TypeId};
16use std::borrow::Borrow;
17use std::cell::RefCell;
18use std::cmp::Ordering;
19use std::collections::HashMap;
20use std::fmt::Debug;
21use std::hash::{Hash, Hasher};
22use std::marker::PhantomData;
23use std::ops::Deref;
24use std::sync::{LazyLock, Mutex};
25use std::{fmt, mem};
26
27use crate::core::builder::Step;
28
29/// Represents an interned value of type `T`, allowing for efficient comparisons and retrieval.
30///
31/// This struct stores a unique index referencing the interned value within an internal cache.
32pub struct Interned<T>(usize, PhantomData<*const T>);
33
34impl<T: Internable + Default> Default for Interned<T> {
35    fn default() -> Self {
36        T::default().intern()
37    }
38}
39
40impl<T> Copy for Interned<T> {}
41impl<T> Clone for Interned<T> {
42    fn clone(&self) -> Interned<T> {
43        *self
44    }
45}
46
47impl<T> PartialEq for Interned<T> {
48    fn eq(&self, other: &Self) -> bool {
49        self.0 == other.0
50    }
51}
52impl<T> Eq for Interned<T> {}
53
54impl PartialEq<&str> for Interned<String> {
55    fn eq(&self, other: &&str) -> bool {
56        **self == **other
57    }
58}
59
60unsafe impl<T> Send for Interned<T> {}
61unsafe impl<T> Sync for Interned<T> {}
62
63impl fmt::Display for Interned<String> {
64    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65        let s: &str = self;
66        f.write_str(s)
67    }
68}
69
70impl<T, U: ?Sized + fmt::Debug> fmt::Debug for Interned<T>
71where
72    Self: Deref<Target = U>,
73{
74    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75        let s: &U = self;
76        f.write_fmt(format_args!("{s:?}"))
77    }
78}
79
80impl<T: Internable + Hash> Hash for Interned<T> {
81    fn hash<H: Hasher>(&self, state: &mut H) {
82        let l = T::intern_cache().lock().unwrap();
83        l.get(*self).hash(state)
84    }
85}
86
87impl<T: Internable + Deref> Deref for Interned<T> {
88    type Target = T::Target;
89    fn deref(&self) -> &Self::Target {
90        let l = T::intern_cache().lock().unwrap();
91        unsafe { mem::transmute::<&Self::Target, &Self::Target>(l.get(*self)) }
92    }
93}
94
95impl<T: Internable + AsRef<U>, U: ?Sized> AsRef<U> for Interned<T> {
96    fn as_ref(&self) -> &U {
97        let l = T::intern_cache().lock().unwrap();
98        unsafe { mem::transmute::<&U, &U>(l.get(*self).as_ref()) }
99    }
100}
101
102impl<T: Internable + PartialOrd> PartialOrd for Interned<T> {
103    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
104        let l = T::intern_cache().lock().unwrap();
105        l.get(*self).partial_cmp(l.get(*other))
106    }
107}
108
109impl<T: Internable + Ord> Ord for Interned<T> {
110    fn cmp(&self, other: &Self) -> Ordering {
111        let l = T::intern_cache().lock().unwrap();
112        l.get(*self).cmp(l.get(*other))
113    }
114}
115
116/// A structure for managing the interning of values of type `T`.
117///
118/// `TyIntern<T>` maintains a mapping between values and their interned representations,
119/// ensuring that duplicate values are not stored multiple times.
120struct TyIntern<T: Clone + Eq> {
121    items: Vec<T>,
122    set: HashMap<T, Interned<T>>,
123}
124
125impl<T: Hash + Clone + Eq> Default for TyIntern<T> {
126    fn default() -> Self {
127        TyIntern { items: Vec::new(), set: Default::default() }
128    }
129}
130
131impl<T: Hash + Clone + Eq> TyIntern<T> {
132    /// Interns a borrowed value, ensuring it is stored uniquely.
133    ///
134    /// If the value has been previously interned, the same `Interned<T>` instance is returned.
135    fn intern_borrow<B>(&mut self, item: &B) -> Interned<T>
136    where
137        B: Eq + Hash + ToOwned<Owned = T> + ?Sized,
138        T: Borrow<B>,
139    {
140        if let Some(i) = self.set.get(item) {
141            return *i;
142        }
143        let item = item.to_owned();
144        let interned = Interned(self.items.len(), PhantomData::<*const T>);
145        self.set.insert(item.clone(), interned);
146        self.items.push(item);
147        interned
148    }
149
150    /// Interns an owned value, storing it uniquely.
151    ///
152    /// If the value has been previously interned, the existing `Interned<T>` is returned.
153    fn intern(&mut self, item: T) -> Interned<T> {
154        if let Some(i) = self.set.get(&item) {
155            return *i;
156        }
157        let interned = Interned(self.items.len(), PhantomData::<*const T>);
158        self.set.insert(item.clone(), interned);
159        self.items.push(item);
160        interned
161    }
162
163    /// Retrieves a reference to the interned value associated with the given `Interned<T>` instance.
164    fn get(&self, i: Interned<T>) -> &T {
165        &self.items[i.0]
166    }
167}
168
169/// A global interner for managing interned values of common types.
170///
171/// This structure maintains caches for `String`, `PathBuf`, and `Vec<String>`, ensuring efficient storage
172/// and retrieval of frequently used values.
173#[derive(Default)]
174pub struct Interner {
175    strs: Mutex<TyIntern<String>>,
176}
177
178/// Defines the behavior required for a type to be internable.
179///
180/// Types implementing this trait must provide access to a static cache and define an `intern` method
181/// that ensures values are stored uniquely.
182trait Internable: Clone + Eq + Hash + 'static {
183    fn intern_cache() -> &'static Mutex<TyIntern<Self>>;
184
185    fn intern(self) -> Interned<Self> {
186        Self::intern_cache().lock().unwrap().intern(self)
187    }
188}
189
190impl Internable for String {
191    fn intern_cache() -> &'static Mutex<TyIntern<Self>> {
192        &INTERNER.strs
193    }
194}
195
196impl Interner {
197    /// Interns a string reference, ensuring it is stored uniquely.
198    ///
199    /// If the string has been previously interned, the same `Interned<String>` instance is returned.
200    pub fn intern_str(&self, s: &str) -> Interned<String> {
201        self.strs.lock().unwrap().intern_borrow(s)
202    }
203}
204
205/// A global instance of `Interner` that caches common interned values.
206pub static INTERNER: LazyLock<Interner> = LazyLock::new(Interner::default);
207
208/// This is essentially a `HashMap` which allows storing any type in its input and
209/// any type in its output. It is a write-once cache; values are never evicted,
210/// which means that references to the value can safely be returned from the
211/// `get()` method.
212#[derive(Debug, Default)]
213pub struct Cache {
214    cache: RefCell<
215        HashMap<
216            TypeId,
217            Box<dyn Any>, // actually a HashMap<Step, Interned<Step::Output>>
218        >,
219    >,
220    #[cfg(test)]
221    /// Contains step metadata of executed steps (in the same order in which they were executed).
222    /// Useful for tests.
223    executed_steps: RefCell<Vec<ExecutedStep>>,
224}
225
226#[cfg(test)]
227#[derive(Debug)]
228pub struct ExecutedStep {
229    pub metadata: Option<crate::core::builder::StepMetadata>,
230}
231
232impl Cache {
233    /// Creates a new empty cache.
234    pub fn new() -> Cache {
235        Cache::default()
236    }
237
238    /// Stores the result of a computation step in the cache.
239    pub fn put<S: Step>(&self, step: S, value: S::Output) {
240        let mut cache = self.cache.borrow_mut();
241        let type_id = TypeId::of::<S>();
242        let stepcache = cache
243            .entry(type_id)
244            .or_insert_with(|| Box::<HashMap<S, S::Output>>::default())
245            .downcast_mut::<HashMap<S, S::Output>>()
246            .expect("invalid type mapped");
247        assert!(!stepcache.contains_key(&step), "processing {step:?} a second time");
248
249        #[cfg(test)]
250        {
251            let metadata = step.metadata();
252            self.executed_steps.borrow_mut().push(ExecutedStep { metadata });
253        }
254
255        stepcache.insert(step, value);
256    }
257
258    /// Retrieves a cached result for the given step, if available.
259    pub fn get<S: Step>(&self, step: &S) -> Option<S::Output> {
260        let mut cache = self.cache.borrow_mut();
261        let type_id = TypeId::of::<S>();
262        let stepcache = cache
263            .entry(type_id)
264            .or_insert_with(|| Box::<HashMap<S, S::Output>>::default())
265            .downcast_mut::<HashMap<S, S::Output>>()
266            .expect("invalid type mapped");
267        stepcache.get(step).cloned()
268    }
269}
270
271#[cfg(test)]
272impl Cache {
273    pub fn all<S: Ord + Step>(&mut self) -> Vec<(S, S::Output)> {
274        let cache = self.cache.get_mut();
275        let type_id = TypeId::of::<S>();
276        let mut v = cache
277            .remove(&type_id)
278            .map(|b| b.downcast::<HashMap<S, S::Output>>().expect("correct type"))
279            .map(|m| m.into_iter().collect::<Vec<_>>())
280            .unwrap_or_default();
281        v.sort_by_key(|(s, _)| s.clone());
282        v
283    }
284
285    pub fn contains<S: Step>(&self) -> bool {
286        self.cache.borrow().contains_key(&TypeId::of::<S>())
287    }
288
289    #[cfg(test)]
290    pub fn into_executed_steps(mut self) -> Vec<ExecutedStep> {
291        mem::take(&mut self.executed_steps.borrow_mut())
292    }
293}
294
295#[cfg(test)]
296mod tests;