register_allocator/src/interned.rs

   1 use hashbrown::{hash_map::RawEntryMut, HashMap};
   2 use serde::Serialize;
   3 use std::{
   4     cell::RefCell,
   5     cmp::Ordering,
   6     fmt,
   7     hash::{Hash, Hasher},
   8     ops::Deref,
   9     rc::Rc,
  10 };
  11
  12 #[derive(Clone)]
  13 pub struct Interned<T: ?Sized> {
  14     ptr: Rc<T>,
  15 }
  16
  17 impl<T: ?Sized> Deref for Interned<T> {
  18     type Target = T;
  19
  20     fn deref(&self) -> &Self::Target {
  21         self.ptr.deref()
  22     }
  23 }
  24
  25 impl<T: ?Sized> Hash for Interned<T> {
  26     fn hash<H: Hasher>(&self, state: &mut H) {
  27         Rc::as_ptr(&self.ptr).hash(state);
  28     }
  29 }
  30
  31 impl<T: ?Sized> Eq for Interned<T> {}
  32
  33 impl<T: ?Sized + fmt::Debug> fmt::Debug for Interned<T> {
  34     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  35         self.ptr.fmt(f)
  36     }
  37 }
  38
  39 impl<T: ?Sized + fmt::Display> fmt::Display for Interned<T> {
  40     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  41         self.ptr.fmt(f)
  42     }
  43 }
  44
  45 impl<T: ?Sized + Serialize> Serialize for Interned<T> {
  46     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
  47     where
  48         S: serde::Serializer,
  49     {
  50         self.ptr.serialize(serializer)
  51     }
  52 }
  53
  54 impl<T: ?Sized> PartialEq for Interned<T> {
  55     fn eq(&self, other: &Interned<T>) -> bool {
  56         Rc::ptr_eq(&self.ptr, &other.ptr)
  57     }
  58 }
  59
  60 impl<T: ?Sized> PartialOrd for Interned<T> {
  61     fn partial_cmp(&self, other: &Interned<T>) -> Option<Ordering> {
  62         Some(self.cmp(other))
  63     }
  64 }
  65
  66 impl<T: ?Sized> Ord for Interned<T> {
  67     fn cmp(&self, other: &Interned<T>) -> Ordering {
  68         Rc::as_ptr(&self.ptr).cmp(&Rc::as_ptr(&other.ptr))
  69     }
  70 }
  71
  72 #[derive(Default)]
  73 struct Interners {
  74     str: Interner<str>,
  75 }
  76
  77 pub struct GlobalArena {
  78     interners: Interners,
  79 }
  80
  81 scoped_tls::scoped_thread_local!(static GLOBAL_ARENA: GlobalArena);
  82
  83 impl GlobalArena {
  84     pub fn scope<R>(f: impl FnOnce() -> R) -> R {
  85         GLOBAL_ARENA.set(
  86             &GlobalArena {
  87                 interners: Interners::default(),
  88             },
  89             f,
  90         )
  91     }
  92     pub fn get<R>(f: impl for<'a> FnOnce(&'a GlobalArena) -> R) -> R {
  93         GLOBAL_ARENA.with(f)
  94     }
  95 }
  96
  97 pub struct Interner<T: ?Sized>(RefCell<HashMap<Rc<T>, ()>>);
  98
  99 impl<T: ?Sized> Default for Interner<T> {
 100     fn default() -> Self {
 101         Self(Default::default())
 102     }
 103 }
 104
 105 pub struct InternInput<
 106     Input,
 107     T: ?Sized + Eq + Hash,
 108     B: FnOnce(&Input) -> &T,
 109     R: FnOnce(Input) -> Rc<T>,
 110 > {
 111     input: Input,
 112     borrow: B,
 113     into_rc: R,
 114 }
 115
 116 impl<T: ?Sized + Eq + Hash> Interner<T> {
 117     fn intern<Input>(
 118         &self,
 119         v: InternInput<Input, T, impl FnOnce(&Input) -> &T, impl FnOnce(Input) -> Rc<T>>,
 120     ) -> Interned<T> {
 121         let InternInput {
 122             input,
 123             borrow,
 124             into_rc,
 125         } = v;
 126         match self.0.borrow_mut().raw_entry_mut().from_key(borrow(&input)) {
 127             RawEntryMut::Occupied(entry) => Interned {
 128                 ptr: entry.key().clone(),
 129             },
 130             RawEntryMut::Vacant(entry) => Interned {
 131                 ptr: entry.insert(into_rc(input), ()).0.clone(),
 132             },
 133         }
 134     }
 135 }
 136
 137 pub trait InternTarget: Intern<Target = Self> + Hash + Eq {
 138     fn get_interner(global_arena: &GlobalArena) -> &Interner<Self>;
 139     fn into_interned(input: Self, global_arena: &GlobalArena) -> Interned<Self>
 140     where
 141         Self: Sized,
 142     {
 143         Self::get_interner(global_arena).intern(InternInput {
 144             input,
 145             borrow: |v| v,
 146             into_rc: Rc::new,
 147         })
 148     }
 149     fn rc_into_interned(input: Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
 150         Self::get_interner(global_arena).intern(InternInput {
 151             input,
 152             borrow: |v| &**v,
 153             into_rc: |v| v,
 154         })
 155     }
 156     fn rc_to_interned(input: &Rc<Self>, global_arena: &GlobalArena) -> Interned<Self> {
 157         Self::get_interner(global_arena).intern(InternInput {
 158             input,
 159             borrow: |v| &***v,
 160             into_rc: |v| v.clone(),
 161         })
 162     }
 163 }
 164
 165 impl InternTarget for str {
 166     fn get_interner(global_arena: &GlobalArena) -> &Interner<Self> {
 167         &global_arena.interners.str
 168     }
 169 }
 170
 171 impl Intern for str {
 172     type Target = str;
 173
 174     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 175         v.into()
 176     }
 177
 178     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 179         Self::get_interner(global_arena).intern(InternInput {
 180             input: self,
 181             borrow: |v| &**v,
 182             into_rc: Self::to_rc_target,
 183         })
 184     }
 185 }
 186
 187 impl Intern for &'_ str {
 188     type Target = str;
 189
 190     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 191         Rc::from(*v)
 192     }
 193
 194     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 195         Self::Target::to_interned(self, global_arena)
 196     }
 197
 198     fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
 199     where
 200         Self: Sized,
 201     {
 202         Self::Target::to_interned(self, global_arena)
 203     }
 204 }
 205
 206 impl Intern for &'_ mut str {
 207     type Target = str;
 208
 209     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 210         Rc::from(&**v)
 211     }
 212
 213     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 214         Self::Target::to_interned(self, global_arena)
 215     }
 216
 217     fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
 218     where
 219         Self: Sized,
 220     {
 221         Self::Target::to_interned(self, global_arena)
 222     }
 223 }
 224
 225 impl Intern for String {
 226     type Target = str;
 227
 228     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 229         Rc::from(&**v)
 230     }
 231
 232     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 233         Self::Target::to_interned(self, global_arena)
 234     }
 235
 236     fn into_rc_target(v: Self) -> Rc<Self::Target>
 237     where
 238         Self: Sized,
 239     {
 240         Rc::from(v)
 241     }
 242
 243     fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
 244     where
 245         Self: Sized,
 246     {
 247         Self::Target::to_interned(&self, global_arena)
 248     }
 249 }
 250
 251 pub trait Intern {
 252     type Target: ?Sized + InternTarget;
 253     fn into_rc_target(v: Self) -> Rc<Self::Target>
 254     where
 255         Self: Sized,
 256     {
 257         Self::to_rc_target(&v)
 258     }
 259     fn to_rc_target(v: &Self) -> Rc<Self::Target>;
 260     fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
 261     where
 262         Self: Sized,
 263     {
 264         <<Self as Intern>::Target as InternTarget>::rc_into_interned(
 265             Self::into_rc_target(self),
 266             global_arena,
 267         )
 268     }
 269     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 270         Self::Target::rc_into_interned(Self::to_rc_target(self), global_arena)
 271     }
 272 }
 273
 274 impl<T: ?Sized + InternTarget> Intern for Rc<T> {
 275     type Target = T;
 276
 277     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 278         v.clone()
 279     }
 280
 281     fn into_rc_target(v: Self) -> Rc<Self::Target>
 282     where
 283         Self: Sized,
 284     {
 285         v
 286     }
 287 }
 288
 289 impl<T: Clone + InternTarget> Intern for T {
 290     type Target = T;
 291
 292     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 293         v.clone().into()
 294     }
 295
 296     fn into_rc_target(v: Self) -> Rc<Self::Target>
 297     where
 298         Self: Sized,
 299     {
 300         v.into()
 301     }
 302
 303     fn into_interned(self, global_arena: &GlobalArena) -> Interned<Self::Target>
 304     where
 305         Self: Sized,
 306     {
 307         InternTarget::into_interned(self, global_arena)
 308     }
 309
 310     fn to_interned(&self, global_arena: &GlobalArena) -> Interned<Self::Target> {
 311         InternTarget::get_interner(global_arena).intern(InternInput {
 312             input: self,
 313             borrow: |v| &**v,
 314             into_rc: |v| v.clone().into(),
 315         })
 316     }
 317 }