1use itertools::Itertools;
2
3pub static TAB_INCR: &str = " ";
4
5pub 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 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 .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 .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 #[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 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 *self = Self::intern(Either::Right(self.0.clone()));
121 ret
122 }
123
124 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 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 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 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 #[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
218const RED_ZONE: usize = 100 * 1024; const STACK_PER_RECURSION: usize = 1024 * 1024; #[inline]
230pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
231 stacker::maybe_grow(RED_ZONE, STACK_PER_RECURSION, f)
232}