charon_lib/
common.rs

1use itertools::Itertools;
2
3pub static TAB_INCR: &str = "    ";
4
5/// Custom function to pretty-print elements from an iterator
6/// The output format is:
7/// ```text
8/// [
9///   elem_0,
10///   ...
11///   elem_n
12/// ]
13/// ```
14pub fn pretty_display_list<T>(
15    t_to_string: impl Fn(T) -> String,
16    it: impl IntoIterator<Item = T>,
17) -> String {
18    let mut elems = it
19        .into_iter()
20        .map(t_to_string)
21        .map(|x| format!("  {},\n", x))
22        .peekable();
23    if elems.peek().is_none() {
24        "[]".to_owned()
25    } else {
26        format!("[\n{}]", elems.format(""))
27    }
28}
29
30pub mod type_map {
31    use std::{
32        any::{Any, TypeId},
33        collections::HashMap,
34        marker::PhantomData,
35    };
36
37    pub trait Mappable = Any + Send + Sync;
38
39    pub trait Mapper {
40        type Value<T: Mappable>: Mappable;
41    }
42
43    /// A map that maps types to values in a generic manner: we store for each type `T` a value of
44    /// type `M::Value<T>`.
45    pub struct TypeMap<M> {
46        data: HashMap<TypeId, Box<dyn Mappable>>,
47        phantom: PhantomData<M>,
48    }
49
50    impl<M: Mapper> TypeMap<M> {
51        pub fn get<T: Mappable>(&self) -> Option<&M::Value<T>> {
52            self.data
53                .get(&TypeId::of::<T>())
54                // We must be careful to not accidentally cast the box itself as `dyn Any`.
55                .map(|val: &Box<dyn Mappable>| &**val)
56                .and_then(|val: &dyn Mappable| (val as &dyn Any).downcast_ref())
57        }
58
59        pub fn get_mut<T: Mappable>(&mut self) -> Option<&mut M::Value<T>> {
60            self.data
61                .get_mut(&TypeId::of::<T>())
62                // We must be careful to not accidentally cast the box itself as `dyn Any`.
63                .map(|val: &mut Box<dyn Mappable>| &mut **val)
64                .and_then(|val: &mut dyn Mappable| (val as &mut dyn Any).downcast_mut())
65        }
66
67        pub fn insert<T: Mappable>(&mut self, val: M::Value<T>) -> Option<Box<M::Value<T>>> {
68            self.data
69                .insert(TypeId::of::<T>(), Box::new(val))
70                .and_then(|val: Box<dyn Mappable>| (val as Box<dyn Any>).downcast().ok())
71        }
72    }
73
74    impl<M> Default for TypeMap<M> {
75        fn default() -> Self {
76            Self {
77                data: Default::default(),
78                phantom: Default::default(),
79            }
80        }
81    }
82}
83
84pub mod hash_consing {
85    use derive_generic_visitor::{Drive, DriveMut, Visit, VisitMut};
86
87    use super::type_map::{Mappable, Mapper, TypeMap};
88    use itertools::Either;
89    use serde::{Deserialize, Serialize};
90    use std::collections::HashMap;
91    use std::hash::Hash;
92    use std::ops::ControlFlow;
93    use std::sync::{Arc, LazyLock, RwLock};
94
95    /// Hash-consed data structure: a reference-counted wrapper that guarantees that two equal
96    /// value will be stored at the same address. This makes it possible to use the pointer address
97    /// as a hash value.
98    #[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
99    pub struct HashConsed<T>(Arc<T>);
100
101    impl<T> HashConsed<T> {
102        pub fn inner(&self) -> &T {
103            self.0.as_ref()
104        }
105    }
106
107    impl<T> HashConsed<T>
108    where
109        T: Hash + PartialEq + Eq + Clone + Mappable,
110    {
111        pub fn new(inner: T) -> Self {
112            Self::intern(Either::Left(inner))
113        }
114
115        /// Clones if needed to get mutable access to the inner value.
116        pub fn with_inner_mut<R>(&mut self, f: impl FnOnce(&mut T) -> R) -> R {
117            let kind = Arc::make_mut(&mut self.0);
118            let ret = f(kind);
119            // Re-establish sharing, crucial for the hashing function to be correct.
120            *self = Self::intern(Either::Right(self.0.clone()));
121            ret
122        }
123
124        /// Deduplicate the valuess by hashing them. This deduplication is crucial for the hashing
125        /// function to be correct. This is the only function allowed to create `Self` values.
126        fn intern(inner: Either<T, Arc<T>>) -> Self {
127            struct InternMapper;
128            impl Mapper for InternMapper {
129                type Value<T: Mappable> = HashMap<T, Arc<T>>;
130            }
131            static INTERNED: LazyLock<RwLock<TypeMap<InternMapper>>> =
132                LazyLock::new(|| Default::default());
133
134            if INTERNED.read().unwrap().get::<T>().is_none() {
135                INTERNED.write().unwrap().insert::<T>(Default::default());
136            }
137            let read_guard = INTERNED.read().unwrap();
138            if let Some(inner) = (*read_guard)
139                .get::<T>()
140                .unwrap()
141                .get(inner.as_ref().either(|x| x, |x| x.as_ref()))
142            {
143                Self(inner.clone())
144            } else {
145                drop(read_guard);
146                // We clone the value here in the slow path, which makes it possible to avoid an
147                // allocation in the fast path.
148                let raw_val: T = inner.as_ref().either(T::clone, |x| x.as_ref().clone());
149                let arc: Arc<T> = inner.either(Arc::new, |x| x);
150                INTERNED
151                    .write()
152                    .unwrap()
153                    .get_mut::<T>()
154                    .unwrap()
155                    .insert(raw_val, arc.clone());
156                Self(arc)
157            }
158        }
159    }
160
161    /// Hash the pointer; this is only correct if two identical values of `Self` are guaranteed to
162    /// point to the same memory location, which we carefully enforce above.
163    impl<T> std::hash::Hash for HashConsed<T> {
164        fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
165            Arc::as_ptr(&self.0).hash(state);
166        }
167    }
168
169    impl<'s, T, V: Visit<'s, T>> Drive<'s, V> for HashConsed<T> {
170        fn drive_inner(&'s self, v: &mut V) -> ControlFlow<V::Break> {
171            v.visit(self.inner())
172        }
173    }
174    /// Note: this explores the inner value mutably by cloning and re-hashing afterwards.
175    impl<'s, T, V> DriveMut<'s, V> for HashConsed<T>
176    where
177        T: Hash + PartialEq + Eq + Clone + Mappable,
178        V: for<'a> VisitMut<'a, T>,
179    {
180        fn drive_inner_mut(&'s mut self, v: &mut V) -> ControlFlow<V::Break> {
181            self.with_inner_mut(|inner| v.visit(inner))
182        }
183    }
184}
185
186pub mod hash_by_addr {
187    use std::{
188        hash::{Hash, Hasher},
189        ops::Deref,
190    };
191
192    /// A wrapper around a smart pointer that hashes and compares the contents by the address of
193    /// the pointee.
194    #[derive(Debug, Clone)]
195    pub struct HashByAddr<T>(pub T);
196
197    impl<T: Deref> HashByAddr<T> {
198        fn addr(&self) -> *const T::Target {
199            self.0.deref()
200        }
201    }
202
203    impl<T: Eq + Deref> Eq for HashByAddr<T> {}
204
205    impl<T: PartialEq + Deref> PartialEq for HashByAddr<T> {
206        fn eq(&self, other: &Self) -> bool {
207            std::ptr::addr_eq(self.addr(), other.addr())
208        }
209    }
210
211    impl<T: Hash + Deref> Hash for HashByAddr<T> {
212        fn hash<H: Hasher>(&self, state: &mut H) {
213            self.addr().hash(state);
214        }
215    }
216}
217
218// This is the amount of bytes that need to be left on the stack before increasing the size. It
219// must be at least as large as the stack required by any code that does not call
220// `ensure_sufficient_stack`.
221const RED_ZONE: usize = 100 * 1024; // 100k
222
223// Only the first stack that is pushed, grows exponentially (2^n * STACK_PER_RECURSION) from then
224// on. Values taken from rustc.
225const STACK_PER_RECURSION: usize = 1024 * 1024; // 1MB
226
227/// Grows the stack on demand to prevent stack overflow. Call this in strategic locations to "break
228/// up" recursive calls. E.g. most statement visitors can benefit from this.
229#[inline]
230pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
231    stacker::maybe_grow(RED_ZONE, STACK_PER_RECURSION, f)
232}