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
30#[macro_export]
32macro_rules! impl_from_enum {
33 ($enum:ident::$variant:ident($ty:ty)) => {
34 impl From<$ty> for $enum {
35 fn from(x: $ty) -> Self {
36 $enum::$variant(x)
37 }
38 }
39 impl TryFrom<$enum> for $ty {
40 type Error = ();
41 fn try_from(e: $enum) -> Result<Self, Self::Error> {
42 match e {
43 $enum::$variant(x) => Ok(x),
44 _ => Err(()),
45 }
46 }
47 }
48 };
49}
50
51pub fn repeat_except_first<T: Clone>(x: T) -> impl Iterator<Item = Option<T>> {
53 [None].into_iter().chain(std::iter::repeat(Some(x)))
54}
55
56pub mod type_map {
57 use std::{
58 any::{Any, TypeId},
59 collections::HashMap,
60 marker::PhantomData,
61 };
62
63 pub trait Mappable = Any + Send + Sync;
64
65 pub trait Mapper {
66 type Value<T: Mappable>: Mappable;
67 }
68
69 pub struct TypeMap<M> {
72 data: HashMap<TypeId, Box<dyn Mappable>>,
73 phantom: PhantomData<M>,
74 }
75
76 impl<M: Mapper> TypeMap<M> {
77 pub fn get<T: Mappable>(&self) -> Option<&M::Value<T>> {
78 self.data
79 .get(&TypeId::of::<T>())
80 .map(|val: &Box<dyn Mappable>| &**val)
82 .and_then(|val: &dyn Mappable| (val as &dyn Any).downcast_ref())
83 }
84
85 pub fn get_mut<T: Mappable>(&mut self) -> Option<&mut M::Value<T>> {
86 self.data
87 .get_mut(&TypeId::of::<T>())
88 .map(|val: &mut Box<dyn Mappable>| &mut **val)
90 .and_then(|val: &mut dyn Mappable| (val as &mut dyn Any).downcast_mut())
91 }
92
93 pub fn insert<T: Mappable>(&mut self, val: M::Value<T>) -> Option<Box<M::Value<T>>> {
94 self.data
95 .insert(TypeId::of::<T>(), Box::new(val))
96 .and_then(|val: Box<dyn Mappable>| (val as Box<dyn Any>).downcast().ok())
97 }
98 }
99
100 impl<M> Default for TypeMap<M> {
101 fn default() -> Self {
102 Self {
103 data: Default::default(),
104 phantom: Default::default(),
105 }
106 }
107 }
108}
109
110pub mod hash_consing {
111 use derive_generic_visitor::{Drive, DriveMut, Visit, VisitMut};
112
113 use super::hash_by_addr::HashByAddr;
114 use super::type_map::{Mappable, Mapper, TypeMap};
115 use serde::{Deserialize, Serialize};
116 use std::collections::HashSet;
117 use std::hash::Hash;
118 use std::ops::ControlFlow;
119 use std::sync::{Arc, LazyLock, RwLock};
120
121 #[derive(Clone, PartialEq, Eq, Hash, Serialize)]
125 pub struct HashConsed<T>(HashByAddr<Arc<T>>);
126
127 impl<T> HashConsed<T> {
128 pub fn inner(&self) -> &T {
129 self.0.0.as_ref()
130 }
131 }
132
133 impl<T> HashConsed<T>
134 where
135 T: Hash + PartialEq + Eq + Clone + Mappable,
136 {
137 pub fn new(inner: T) -> Self {
138 Self::intern(inner)
139 }
140
141 pub fn with_inner_mut<R>(&mut self, f: impl FnOnce(&mut T) -> R) -> R {
143 let mut value = self.inner().clone();
145 let ret = f(&mut value);
146 *self = Self::intern(value);
148 ret
149 }
150
151 fn intern(inner: T) -> Self {
154 struct InternMapper;
155 impl Mapper for InternMapper {
156 type Value<T: Mappable> = HashSet<Arc<T>>;
157 }
158 static INTERNED: LazyLock<RwLock<TypeMap<InternMapper>>> =
165 LazyLock::new(|| Default::default());
166
167 if INTERNED.read().unwrap().get::<T>().is_none() {
168 INTERNED.write().unwrap().insert::<T>(HashSet::default());
169 }
170 let read_guard = INTERNED.read().unwrap();
171 let arc = if let Some(arc) = (*read_guard).get::<T>().unwrap().get(&inner) {
172 arc.clone()
173 } else {
174 drop(read_guard);
175 let arc: Arc<T> = Arc::new(inner);
176 INTERNED
177 .write()
178 .unwrap()
179 .get_mut::<T>()
180 .unwrap()
181 .insert(arc.clone());
182 arc
183 };
184 Self(HashByAddr(arc))
185 }
186 }
187
188 impl<T: std::fmt::Debug> std::fmt::Debug for HashConsed<T> {
189 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
190 f.debug_tuple("HashConsed").field(self.inner()).finish()
192 }
193 }
194
195 impl<'de, T> Deserialize<'de> for HashConsed<T>
197 where
198 T: Hash + PartialEq + Eq + Clone + Mappable,
199 T: Deserialize<'de>,
200 {
201 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
202 where
203 D: serde::Deserializer<'de>,
204 {
205 let x: T = T::deserialize(deserializer)?;
206 Ok(Self::new(x))
207 }
208 }
209
210 impl<'s, T, V: Visit<'s, T>> Drive<'s, V> for HashConsed<T> {
211 fn drive_inner(&'s self, v: &mut V) -> ControlFlow<V::Break> {
212 v.visit(self.inner())
213 }
214 }
215 impl<'s, T, V> DriveMut<'s, V> for HashConsed<T>
217 where
218 T: Hash + PartialEq + Eq + Clone + Mappable,
219 V: for<'a> VisitMut<'a, T>,
220 {
221 fn drive_inner_mut(&'s mut self, v: &mut V) -> ControlFlow<V::Break> {
222 self.with_inner_mut(|inner| v.visit(inner))
223 }
224 }
225
226 #[test]
227 fn test_hash_cons() {
228 let x = HashConsed::new(42u32);
229 let y = HashConsed::new(42u32);
230 assert_eq!(x, y);
231 let z = serde_json::from_value(serde_json::to_value(x.clone()).unwrap()).unwrap();
232 assert_eq!(x, z);
233 }
234}
235
236pub mod hash_by_addr {
237 use serde::{Deserialize, Serialize};
238 use std::{
239 hash::{Hash, Hasher},
240 ops::Deref,
241 };
242
243 #[derive(Debug, Clone, Serialize, Deserialize)]
246 pub struct HashByAddr<T>(pub T);
247
248 impl<T: Deref> HashByAddr<T> {
249 fn addr(&self) -> *const T::Target {
250 self.0.deref()
251 }
252 }
253
254 impl<T: Eq + Deref> Eq for HashByAddr<T> {}
255
256 impl<T: PartialEq + Deref> PartialEq for HashByAddr<T> {
257 fn eq(&self, other: &Self) -> bool {
258 std::ptr::addr_eq(self.addr(), other.addr())
259 }
260 }
261
262 impl<T: Hash + Deref> Hash for HashByAddr<T> {
263 fn hash<H: Hasher>(&self, state: &mut H) {
264 self.addr().hash(state);
265 }
266 }
267}
268
269const RED_ZONE: usize = 100 * 1024; const STACK_PER_RECURSION: usize = 1024 * 1024; #[inline]
281pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
282 stacker::maybe_grow(RED_ZONE, STACK_PER_RECURSION, f)
283}