pub static TAB_INCR: &str = " ";
pub fn iterator_to_string<T>(
t_to_string: &dyn Fn(T) -> String,
it: impl Iterator<Item = T>,
) -> String {
let elems: Vec<String> = it.map(|x| format!(" {}", t_to_string(x))).collect();
if elems.is_empty() {
"[]".to_owned()
} else {
format!("[\n{}\n]", elems.join(",\n"))
}
}
pub fn vec_to_string<T>(t_to_string: &dyn Fn(&T) -> String, v: &[T]) -> String {
iterator_to_string(t_to_string, v.iter())
}
pub fn write_iterator<T: Copy>(
write_t: &dyn Fn(&mut std::fmt::Formatter<'_>, T) -> std::result::Result<(), std::fmt::Error>,
f: &mut std::fmt::Formatter<'_>,
it: impl Iterator<Item = T>,
) -> std::result::Result<(), std::fmt::Error> {
let elems: Vec<T> = it.collect();
if elems.is_empty() {
write!(f, "[]")
} else {
writeln!(f, "[")?;
for i in 0..elems.len() {
write_t(f, elems[i])?;
if i + 1 < elems.len() {
writeln!(f, ",")?;
}
}
write!(f, "\n]")
}
}
pub fn write_vec<T>(
write_t: &dyn Fn(&mut std::fmt::Formatter<'_>, &T) -> std::result::Result<(), std::fmt::Error>,
f: &mut std::fmt::Formatter<'_>,
v: &[T],
) -> std::result::Result<(), std::fmt::Error> {
write_iterator(write_t, f, v.iter())
}
pub mod type_map {
use std::{
any::{Any, TypeId},
collections::HashMap,
marker::PhantomData,
};
pub trait Mappable = Any + Send + Sync;
pub trait Mapper {
type Value<T: Mappable>: Mappable;
}
pub struct TypeMap<M> {
data: HashMap<TypeId, Box<dyn Mappable>>,
phantom: PhantomData<M>,
}
impl<M: Mapper> TypeMap<M> {
pub fn get<T: Mappable>(&self) -> Option<&M::Value<T>> {
self.data
.get(&TypeId::of::<T>())
.map(|val: &Box<dyn Mappable>| &**val)
.and_then(|val: &dyn Mappable| (val as &dyn Any).downcast_ref())
}
pub fn get_mut<T: Mappable>(&mut self) -> Option<&mut M::Value<T>> {
self.data
.get_mut(&TypeId::of::<T>())
.map(|val: &mut Box<dyn Mappable>| &mut **val)
.and_then(|val: &mut dyn Mappable| (val as &mut dyn Any).downcast_mut())
}
pub fn insert<T: Mappable>(&mut self, val: M::Value<T>) -> Option<Box<M::Value<T>>> {
self.data
.insert(TypeId::of::<T>(), Box::new(val))
.and_then(|val: Box<dyn Mappable>| (val as Box<dyn Any>).downcast().ok())
}
}
impl<M> Default for TypeMap<M> {
fn default() -> Self {
Self {
data: Default::default(),
phantom: Default::default(),
}
}
}
}
pub mod hash_consing {
use super::type_map::{Mappable, Mapper, TypeMap};
use derive_visitor::{Drive, DriveMut, Event, Visitor, VisitorMut};
use itertools::Either;
use serde::{Deserialize, Serialize};
use std::collections::HashMap;
use std::hash::Hash;
use std::sync::{Arc, LazyLock, RwLock};
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct HashConsed<T>(Arc<T>);
impl<T> HashConsed<T> {
pub fn inner(&self) -> &T {
self.0.as_ref()
}
}
impl<T> HashConsed<T>
where
T: Hash + PartialEq + Eq + Clone + Mappable,
{
pub fn new(inner: T) -> Self {
Self::intern(Either::Left(inner))
}
pub fn with_inner_mut<R>(&mut self, f: impl FnOnce(&mut T) -> R) -> R {
let kind = Arc::make_mut(&mut self.0);
let ret = f(kind);
*self = Self::intern(Either::Right(self.0.clone()));
ret
}
fn intern(inner: Either<T, Arc<T>>) -> Self {
struct InternMapper;
impl Mapper for InternMapper {
type Value<T: Mappable> = HashMap<T, Arc<T>>;
}
static INTERNED: LazyLock<RwLock<TypeMap<InternMapper>>> =
LazyLock::new(|| Default::default());
if INTERNED.read().unwrap().get::<T>().is_none() {
INTERNED.write().unwrap().insert::<T>(Default::default());
}
let read_guard = INTERNED.read().unwrap();
if let Some(inner) = (*read_guard)
.get::<T>()
.unwrap()
.get(inner.as_ref().either(|x| x, |x| x.as_ref()))
{
Self(inner.clone())
} else {
drop(read_guard);
let raw_val: T = inner.as_ref().either(T::clone, |x| x.as_ref().clone());
let arc: Arc<T> = inner.either(Arc::new, |x| x);
INTERNED
.write()
.unwrap()
.get_mut::<T>()
.unwrap()
.insert(raw_val, arc.clone());
Self(arc)
}
}
}
impl<T> std::hash::Hash for HashConsed<T> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
Arc::as_ptr(&self.0).hash(state);
}
}
impl<T> Drive for HashConsed<T>
where
T: Drive,
{
fn drive<V: Visitor>(&self, visitor: &mut V) {
visitor.visit(self, Event::Enter);
self.inner().drive(visitor);
visitor.visit(self, Event::Exit);
}
}
impl<T> DriveMut for HashConsed<T>
where
T: DriveMut + Hash + PartialEq + Eq + Clone + Mappable,
{
fn drive_mut<V: VisitorMut>(&mut self, visitor: &mut V) {
visitor.visit(self, Event::Enter);
self.with_inner_mut(|inner| inner.drive_mut(visitor));
visitor.visit(self, Event::Exit);
}
}
}
pub mod hash_by_addr {
use std::{
hash::{Hash, Hasher},
ops::Deref,
};
#[derive(Debug, Clone)]
pub struct HashByAddr<T>(pub T);
impl<T: Deref> HashByAddr<T> {
fn addr(&self) -> *const T::Target {
self.0.deref()
}
}
impl<T: Eq + Deref> Eq for HashByAddr<T> {}
impl<T: PartialEq + Deref> PartialEq for HashByAddr<T> {
fn eq(&self, other: &Self) -> bool {
std::ptr::addr_eq(self.addr(), other.addr())
}
}
impl<T: Hash + Deref> Hash for HashByAddr<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.addr().hash(state);
}
}
}
pub mod visitor_event {
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum VisitEvent {
Enter,
Exit,
}
impl From<&derive_visitor::Event> for VisitEvent {
fn from(value: &derive_visitor::Event) -> Self {
match value {
derive_visitor::Event::Enter => VisitEvent::Enter,
derive_visitor::Event::Exit => VisitEvent::Exit,
}
}
}
impl From<VisitEvent> for derive_visitor::Event {
fn from(value: VisitEvent) -> Self {
match value {
VisitEvent::Enter => derive_visitor::Event::Enter,
VisitEvent::Exit => derive_visitor::Event::Exit,
}
}
}
}
const RED_ZONE: usize = 100 * 1024; const STACK_PER_RECURSION: usize = 1024 * 1024; #[inline]
pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
stacker::maybe_grow(RED_ZONE, STACK_PER_RECURSION, f)
}