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