register_allocator/src/interned.rs

   1 use crate::{
   2     loc::Loc,
   3     loc_set::{LocSet, LocSetMaxConflictsWith},
   4 };
   5 use hashbrown::{
   6     hash_map::{Entry, RawEntryMut},
   7     HashMap,
   8 };
   9 use serde::{de, Deserialize, Serialize};
  10 use std::{
  11     cell::RefCell,
  12     cmp::Ordering,
  13     fmt,
  14     hash::{Hash, Hasher},
  15     ops::Deref,
  16     rc::Rc,
  17 };
  18
  19 pub struct Interned<T: ?Sized> {
  20     ptr: Rc<T>,
  21 }
  22
  23 impl<T: ?Sized> Deref for Interned<T> {
  24     type Target = T;
  25
  26     fn deref(&self) -> &Self::Target {
  27         self.ptr.deref()
  28     }
  29 }
  30
  31 impl<T: ?Sized> Clone for Interned<T> {
  32     fn clone(&self) -> Self {
  33         Self {
  34             ptr: self.ptr.clone(),
  35         }
  36     }
  37 }
  38
  39 impl<T: ?Sized> Hash for Interned<T> {
  40     fn hash<H: Hasher>(&self, state: &mut H) {
  41         Rc::as_ptr(&self.ptr).hash(state);
  42     }
  43 }
  44
  45 impl<T: ?Sized> Eq for Interned<T> {}
  46
  47 impl<T: ?Sized + fmt::Debug> fmt::Debug for Interned<T> {
  48     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  49         self.ptr.fmt(f)
  50     }
  51 }
  52
  53 impl<T: ?Sized + fmt::Display> fmt::Display for Interned<T> {
  54     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  55         self.ptr.fmt(f)
  56     }
  57 }
  58
  59 pub struct SerdeState {
  60     global_state: Rc<GlobalState>,
  61     inner: SerdeStateInner,
  62 }
  63
  64 scoped_tls::scoped_thread_local!(static SERDE_STATE: SerdeState);
  65
  66 impl SerdeState {
  67     pub fn global_state(&self) -> &Rc<GlobalState> {
  68         &self.global_state
  69     }
  70     #[cold]
  71     pub fn scope<R>(global_state: &Rc<GlobalState>, f: impl FnOnce() -> R) -> R {
  72         SERDE_STATE.set(
  73             &SerdeState {
  74                 global_state: global_state.clone(),
  75                 inner: SerdeStateInner::default(),
  76             },
  77             f,
  78         )
  79     }
  80     pub fn get_or_scope<R>(f: impl for<'a> FnOnce(&'a SerdeState) -> R) -> R {
  81         if SERDE_STATE.is_set() {
  82             SERDE_STATE.with(f)
  83         } else {
  84             GlobalState::get(|global_state| Self::scope(global_state, || SERDE_STATE.with(f)))
  85         }
  86     }
  87 }
  88
  89 pub struct SerdeStateFor<T: ?Sized> {
  90     de: RefCell<Vec<Interned<T>>>,
  91     ser: RefCell<HashMap<Interned<T>, usize>>,
  92 }
  93
  94 impl<T: ?Sized> Default for SerdeStateFor<T> {
  95     fn default() -> Self {
  96         Self {
  97             de: Default::default(),
  98             ser: Default::default(),
  99         }
 100     }
 101 }
 102
 103 #[derive(Serialize, Deserialize)]
 104 enum SerializedInterned<T> {
 105     Old(usize),
 106     New(T),
 107 }
 108
 109 impl<T: ?Sized + Serialize + InternTarget> Serialize for Interned<T> {
 110     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
 111     where
 112         S: serde::Serializer,
 113     {
 114         SerdeState::get_or_scope(|serde_state| {
 115             let mut state = T::get_serde_state_for(serde_state).ser.borrow_mut();
 116             let next_index = state.len();
 117             match state.entry(self.clone()) {
 118                 Entry::Occupied(entry) => SerializedInterned::Old(*entry.get()),
 119                 Entry::Vacant(entry) => {
 120                     entry.insert(next_index);
 121                     SerializedInterned::<&T>::New(self)
 122                 }
 123             }
 124             .serialize(serializer)
 125         })
 126     }
 127 }
 128
 129 impl<'de, T, Owned> Deserialize<'de> for Interned<T>
 130 where
 131     T: ?Sized + InternTarget + ToOwned<Owned = Owned>,
 132     Owned: Deserialize<'de> + Intern<Target = T>,
 133 {
 134     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
 135     where
 136         D: serde::Deserializer<'de>,
 137     {
 138         SerdeState::get_or_scope(|serde_state| {
 139             let mut state = T::get_serde_state_for(serde_state).de.borrow_mut();
 140             match SerializedInterned::<Owned>::deserialize(deserializer)? {
 141                 SerializedInterned::Old(index) => state
 142                     .get(index)
 143                     .cloned()
 144                     .ok_or_else(|| <D::Error as de::Error>::custom("index out of range")),
 145                 SerializedInterned::New(value) => {
 146                     let retval = value.into_interned(&serde_state.global_state);
 147                     state.push(retval.clone());
 148                     Ok(retval)
 149                 }
 150             }
 151         })
 152     }
 153 }
 154
 155 impl<T: ?Sized> PartialEq for Interned<T> {
 156     fn eq(&self, other: &Interned<T>) -> bool {
 157         Rc::ptr_eq(&self.ptr, &other.ptr)
 158     }
 159 }
 160
 161 impl<T: ?Sized> PartialOrd for Interned<T> {
 162     fn partial_cmp(&self, other: &Interned<T>) -> Option<Ordering> {
 163         Some(self.cmp(other))
 164     }
 165 }
 166
 167 impl<T: ?Sized> Ord for Interned<T> {
 168     fn cmp(&self, other: &Interned<T>) -> Ordering {
 169         Rc::as_ptr(&self.ptr).cmp(&Rc::as_ptr(&other.ptr))
 170     }
 171 }
 172
 173 macro_rules! make_interners {
 174     {
 175         $(
 176             $(#[$impl_intern_target:ident intern_target])?
 177             $name:ident: $ty:ty,
 178         )*
 179     } => {
 180         #[derive(Default)]
 181         struct Interners {
 182             $($name: Interner<$ty>,)*
 183         }
 184
 185         #[derive(Default)]
 186         struct SerdeStateInner {
 187             $($name: SerdeStateFor<$ty>,)*
 188         }
 189
 190         $($(
 191             $impl_intern_target InternTarget for $ty {
 192                 fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
 193                     &global_state.interners.$name
 194                 }
 195
 196                 fn get_serde_state_for(serde_state: &SerdeState) -> &SerdeStateFor<Self> {
 197                     &serde_state.inner.$name
 198                 }
 199             }
 200         )?)*
 201     };
 202 }
 203
 204 make_interners! {
 205     str: str,
 206     #[impl intern_target]
 207     loc_set: LocSet,
 208     #[impl intern_target]
 209     loc_set_max_conflicts_with_loc_set: LocSetMaxConflictsWith<Interned<LocSet>>,
 210     #[impl intern_target]
 211     loc_set_max_conflicts_with_loc: LocSetMaxConflictsWith<Loc>,
 212 }
 213
 214 pub struct GlobalState {
 215     interners: Interners,
 216 }
 217
 218 scoped_tls::scoped_thread_local!(static GLOBAL_STATE: Rc<GlobalState>);
 219
 220 impl GlobalState {
 221     #[cold]
 222     pub fn scope<R>(f: impl FnOnce() -> R) -> R {
 223         GLOBAL_STATE.set(
 224             &Rc::new(GlobalState {
 225                 interners: Interners::default(),
 226             }),
 227             f,
 228         )
 229     }
 230     pub fn get<R>(f: impl for<'a> FnOnce(&'a Rc<GlobalState>) -> R) -> R {
 231         GLOBAL_STATE.with(f)
 232     }
 233 }
 234
 235 pub struct Interner<T: ?Sized>(RefCell<HashMap<Rc<T>, ()>>);
 236
 237 impl<T: ?Sized> Default for Interner<T> {
 238     fn default() -> Self {
 239         Self(Default::default())
 240     }
 241 }
 242
 243 pub struct InternInput<
 244     Input,
 245     T: ?Sized + Eq + Hash,
 246     B: FnOnce(&Input) -> &T,
 247     R: FnOnce(Input) -> Rc<T>,
 248 > {
 249     input: Input,
 250     borrow: B,
 251     into_rc: R,
 252 }
 253
 254 impl<T: ?Sized + Eq + Hash> Interner<T> {
 255     fn intern<Input>(
 256         &self,
 257         v: InternInput<Input, T, impl FnOnce(&Input) -> &T, impl FnOnce(Input) -> Rc<T>>,
 258     ) -> Interned<T> {
 259         let InternInput {
 260             input,
 261             borrow,
 262             into_rc,
 263         } = v;
 264         match self.0.borrow_mut().raw_entry_mut().from_key(borrow(&input)) {
 265             RawEntryMut::Occupied(entry) => Interned {
 266                 ptr: entry.key().clone(),
 267             },
 268             RawEntryMut::Vacant(entry) => Interned {
 269                 ptr: entry.insert(into_rc(input), ()).0.clone(),
 270             },
 271         }
 272     }
 273 }
 274
 275 pub trait InternTarget: Intern<Target = Self> + Hash + Eq {
 276     fn get_interner(global_state: &GlobalState) -> &Interner<Self>;
 277     fn get_serde_state_for(serde_state: &SerdeState) -> &SerdeStateFor<Self>;
 278     fn into_interned(input: Self, global_state: &GlobalState) -> Interned<Self>
 279     where
 280         Self: Sized,
 281     {
 282         Self::get_interner(global_state).intern(InternInput {
 283             input,
 284             borrow: |v| v,
 285             into_rc: Rc::new,
 286         })
 287     }
 288     fn rc_into_interned(input: Rc<Self>, global_state: &GlobalState) -> Interned<Self> {
 289         Self::get_interner(global_state).intern(InternInput {
 290             input,
 291             borrow: |v| &**v,
 292             into_rc: |v| v,
 293         })
 294     }
 295     fn rc_to_interned(input: &Rc<Self>, global_state: &GlobalState) -> Interned<Self> {
 296         Self::get_interner(global_state).intern(InternInput {
 297             input,
 298             borrow: |v| &***v,
 299             into_rc: |v| v.clone(),
 300         })
 301     }
 302 }
 303
 304 impl<'a, T: arbitrary::Arbitrary<'a> + InternTarget> arbitrary::Arbitrary<'a> for Interned<T> {
 305     fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
 306         let retval: T = u.arbitrary()?;
 307         Ok(GlobalState::get(|global_state| {
 308             retval.into_interned(global_state)
 309         }))
 310     }
 311 }
 312
 313 impl InternTarget for str {
 314     fn get_interner(global_state: &GlobalState) -> &Interner<Self> {
 315         &global_state.interners.str
 316     }
 317     fn get_serde_state_for(serde_state: &SerdeState) -> &SerdeStateFor<Self> {
 318         &serde_state.inner.str
 319     }
 320 }
 321
 322 impl Intern for str {
 323     type Target = str;
 324
 325     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 326         v.into()
 327     }
 328
 329     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 330         Self::get_interner(global_state).intern(InternInput {
 331             input: self,
 332             borrow: |v| &**v,
 333             into_rc: Self::to_rc_target,
 334         })
 335     }
 336 }
 337
 338 impl Intern for &'_ str {
 339     type Target = str;
 340
 341     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 342         Rc::from(*v)
 343     }
 344
 345     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 346         Self::Target::to_interned(self, global_state)
 347     }
 348
 349     fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
 350     where
 351         Self: Sized,
 352     {
 353         Self::Target::to_interned(self, global_state)
 354     }
 355 }
 356
 357 impl Intern for &'_ mut str {
 358     type Target = str;
 359
 360     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 361         Rc::from(&**v)
 362     }
 363
 364     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 365         Self::Target::to_interned(self, global_state)
 366     }
 367
 368     fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
 369     where
 370         Self: Sized,
 371     {
 372         Self::Target::to_interned(self, global_state)
 373     }
 374 }
 375
 376 impl Intern for String {
 377     type Target = str;
 378
 379     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 380         Rc::from(&**v)
 381     }
 382
 383     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 384         Self::Target::to_interned(self, global_state)
 385     }
 386
 387     fn into_rc_target(v: Self) -> Rc<Self::Target>
 388     where
 389         Self: Sized,
 390     {
 391         Rc::from(v)
 392     }
 393
 394     fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
 395     where
 396         Self: Sized,
 397     {
 398         Self::Target::to_interned(&self, global_state)
 399     }
 400 }
 401
 402 pub trait Intern {
 403     type Target: ?Sized + InternTarget;
 404     fn into_rc_target(v: Self) -> Rc<Self::Target>
 405     where
 406         Self: Sized,
 407     {
 408         Self::to_rc_target(&v)
 409     }
 410     fn to_rc_target(v: &Self) -> Rc<Self::Target>;
 411     fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
 412     where
 413         Self: Sized,
 414     {
 415         <<Self as Intern>::Target as InternTarget>::rc_into_interned(
 416             Self::into_rc_target(self),
 417             global_state,
 418         )
 419     }
 420     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 421         Self::Target::rc_into_interned(Self::to_rc_target(self), global_state)
 422     }
 423 }
 424
 425 impl<T: ?Sized + InternTarget> Intern for Rc<T> {
 426     type Target = T;
 427
 428     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 429         v.clone()
 430     }
 431
 432     fn into_rc_target(v: Self) -> Rc<Self::Target>
 433     where
 434         Self: Sized,
 435     {
 436         v
 437     }
 438 }
 439
 440 impl<T: Clone + InternTarget> Intern for T {
 441     type Target = T;
 442
 443     fn to_rc_target(v: &Self) -> Rc<Self::Target> {
 444         v.clone().into()
 445     }
 446
 447     fn into_rc_target(v: Self) -> Rc<Self::Target>
 448     where
 449         Self: Sized,
 450     {
 451         v.into()
 452     }
 453
 454     fn into_interned(self, global_state: &GlobalState) -> Interned<Self::Target>
 455     where
 456         Self: Sized,
 457     {
 458         InternTarget::into_interned(self, global_state)
 459     }
 460
 461     fn to_interned(&self, global_state: &GlobalState) -> Interned<Self::Target> {
 462         InternTarget::get_interner(global_state).intern(InternInput {
 463             input: self,
 464             borrow: |v| &**v,
 465             into_rc: |v| v.clone().into(),
 466         })
 467     }
 468 }