compiler/rustc_metadata/src/rmeta/table.rs

   1 use crate::rmeta::*;
   2
   3 use rustc_data_structures::fingerprint::Fingerprint;
   4 use rustc_hir::def::{CtorKind, CtorOf};
   5 use rustc_index::vec::Idx;
   6 use rustc_middle::ty::ParameterizedOverTcx;
   7 use rustc_serialize::opaque::FileEncoder;
   8 use rustc_serialize::Encoder as _;
   9 use rustc_span::hygiene::MacroKind;
  10 use std::marker::PhantomData;
  11 use std::num::NonZeroUsize;
  12
  13 /// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
  14 /// Used mainly for Lazy positions and lengths.
  15 /// Unchecked invariant: `Self::default()` should encode as `[0; BYTE_LEN]`,
  16 /// but this has no impact on safety.
  17 pub(super) trait FixedSizeEncoding: Default {
  18     /// This should be `[u8; BYTE_LEN]`;
  19     type ByteArray;
  20
  21     fn from_bytes(b: &Self::ByteArray) -> Self;
  22     fn write_to_bytes(self, b: &mut Self::ByteArray);
  23 }
  24
  25 impl FixedSizeEncoding for u32 {
  26     type ByteArray = [u8; 4];
  27
  28     #[inline]
  29     fn from_bytes(b: &[u8; 4]) -> Self {
  30         Self::from_le_bytes(*b)
  31     }
  32
  33     #[inline]
  34     fn write_to_bytes(self, b: &mut [u8; 4]) {
  35         *b = self.to_le_bytes();
  36     }
  37 }
  38
  39 macro_rules! fixed_size_enum {
  40     ($ty:ty { $(($($pat:tt)*))* }) => {
  41         impl FixedSizeEncoding for Option<$ty> {
  42             type ByteArray = [u8;1];
  43
  44             #[inline]
  45             fn from_bytes(b: &[u8;1]) -> Self {
  46                 use $ty::*;
  47                 if b[0] == 0 {
  48                     return None;
  49                 }
  50                 match b[0] - 1 {
  51                     $(${index()} => Some($($pat)*),)*
  52                     _ => panic!("Unexpected {} code: {:?}", stringify!($ty), b[0]),
  53                 }
  54             }
  55
  56             #[inline]
  57             fn write_to_bytes(self, b: &mut [u8;1]) {
  58                 use $ty::*;
  59                 b[0] = match self {
  60                     None => 0,
  61                     $(Some($($pat)*) => 1 + ${index()},)*
  62                 }
  63             }
  64         }
  65     }
  66 }
  67
  68 fixed_size_enum! {
  69     DefKind {
  70         ( Mod                                      )
  71         ( Struct                                   )
  72         ( Union                                    )
  73         ( Enum                                     )
  74         ( Variant                                  )
  75         ( Trait                                    )
  76         ( TyAlias                                  )
  77         ( ForeignTy                                )
  78         ( TraitAlias                               )
  79         ( AssocTy                                  )
  80         ( TyParam                                  )
  81         ( Fn                                       )
  82         ( Const                                    )
  83         ( ConstParam                               )
  84         ( AssocFn                                  )
  85         ( AssocConst                               )
  86         ( ExternCrate                              )
  87         ( Use                                      )
  88         ( ForeignMod                               )
  89         ( AnonConst                                )
  90         ( InlineConst                              )
  91         ( OpaqueTy                                 )
  92         ( ImplTraitPlaceholder                     )
  93         ( Field                                    )
  94         ( LifetimeParam                            )
  95         ( GlobalAsm                                )
  96         ( Impl                                     )
  97         ( Closure                                  )
  98         ( Generator                                )
  99         ( Static(ast::Mutability::Not)             )
 100         ( Static(ast::Mutability::Mut)             )
 101         ( Ctor(CtorOf::Struct, CtorKind::Fn)       )
 102         ( Ctor(CtorOf::Struct, CtorKind::Const)    )
 103         ( Ctor(CtorOf::Variant, CtorKind::Fn)      )
 104         ( Ctor(CtorOf::Variant, CtorKind::Const)   )
 105         ( Macro(MacroKind::Bang)                   )
 106         ( Macro(MacroKind::Attr)                   )
 107         ( Macro(MacroKind::Derive)                 )
 108     }
 109 }
 110
 111 fixed_size_enum! {
 112     ty::ImplPolarity {
 113         ( Positive    )
 114         ( Negative    )
 115         ( Reservation )
 116     }
 117 }
 118
 119 fixed_size_enum! {
 120     hir::Constness {
 121         ( NotConst )
 122         ( Const    )
 123     }
 124 }
 125
 126 fixed_size_enum! {
 127     hir::Defaultness {
 128         ( Final                        )
 129         ( Default { has_value: false } )
 130         ( Default { has_value: true }  )
 131     }
 132 }
 133
 134 fixed_size_enum! {
 135     hir::IsAsync {
 136         ( NotAsync )
 137         ( Async    )
 138     }
 139 }
 140
 141 fixed_size_enum! {
 142     ty::AssocItemContainer {
 143         ( TraitContainer )
 144         ( ImplContainer  )
 145     }
 146 }
 147
 148 fixed_size_enum! {
 149     MacroKind {
 150         ( Attr   )
 151         ( Bang   )
 152         ( Derive )
 153     }
 154 }
 155
 156 // We directly encode `DefPathHash` because a `LazyValue` would incur a 25% cost.
 157 impl FixedSizeEncoding for Option<DefPathHash> {
 158     type ByteArray = [u8; 16];
 159
 160     #[inline]
 161     fn from_bytes(b: &[u8; 16]) -> Self {
 162         Some(DefPathHash(Fingerprint::from_le_bytes(*b)))
 163     }
 164
 165     #[inline]
 166     fn write_to_bytes(self, b: &mut [u8; 16]) {
 167         let Some(DefPathHash(fingerprint)) = self else {
 168             panic!("Trying to encode absent DefPathHash.")
 169         };
 170         *b = fingerprint.to_le_bytes();
 171     }
 172 }
 173
 174 // We directly encode RawDefId because using a `LazyValue` would incur a 50% overhead in the worst case.
 175 impl FixedSizeEncoding for Option<RawDefId> {
 176     type ByteArray = [u8; 8];
 177
 178     #[inline]
 179     fn from_bytes(b: &[u8; 8]) -> Self {
 180         let krate = u32::from_le_bytes(b[0..4].try_into().unwrap());
 181         let index = u32::from_le_bytes(b[4..8].try_into().unwrap());
 182         if krate == 0 {
 183             return None;
 184         }
 185         Some(RawDefId { krate: krate - 1, index })
 186     }
 187
 188     #[inline]
 189     fn write_to_bytes(self, b: &mut [u8; 8]) {
 190         match self {
 191             None => *b = [0; 8],
 192             Some(RawDefId { krate, index }) => {
 193                 // CrateNum is less than `CrateNum::MAX_AS_U32`.
 194                 debug_assert!(krate < u32::MAX);
 195                 b[0..4].copy_from_slice(&(1 + krate).to_le_bytes());
 196                 b[4..8].copy_from_slice(&index.to_le_bytes());
 197             }
 198         }
 199     }
 200 }
 201
 202 impl FixedSizeEncoding for Option<AttrFlags> {
 203     type ByteArray = [u8; 1];
 204
 205     #[inline]
 206     fn from_bytes(b: &[u8; 1]) -> Self {
 207         (b[0] != 0).then(|| AttrFlags::from_bits_truncate(b[0]))
 208     }
 209
 210     #[inline]
 211     fn write_to_bytes(self, b: &mut [u8; 1]) {
 212         b[0] = self.map_or(0, |flags| flags.bits())
 213     }
 214 }
 215
 216 impl FixedSizeEncoding for Option<()> {
 217     type ByteArray = [u8; 1];
 218
 219     #[inline]
 220     fn from_bytes(b: &[u8; 1]) -> Self {
 221         (b[0] != 0).then(|| ())
 222     }
 223
 224     #[inline]
 225     fn write_to_bytes(self, b: &mut [u8; 1]) {
 226         b[0] = self.is_some() as u8
 227     }
 228 }
 229
 230 // NOTE(eddyb) there could be an impl for `usize`, which would enable a more
 231 // generic `LazyValue<T>` impl, but in the general case we might not need / want
 232 // to fit every `usize` in `u32`.
 233 impl<T> FixedSizeEncoding for Option<LazyValue<T>> {
 234     type ByteArray = [u8; 4];
 235
 236     #[inline]
 237     fn from_bytes(b: &[u8; 4]) -> Self {
 238         let position = NonZeroUsize::new(u32::from_bytes(b) as usize)?;
 239         Some(LazyValue::from_position(position))
 240     }
 241
 242     #[inline]
 243     fn write_to_bytes(self, b: &mut [u8; 4]) {
 244         let position = self.map_or(0, |lazy| lazy.position.get());
 245         let position: u32 = position.try_into().unwrap();
 246         position.write_to_bytes(b)
 247     }
 248 }
 249
 250 impl<T> FixedSizeEncoding for Option<LazyArray<T>> {
 251     type ByteArray = [u8; 8];
 252
 253     #[inline]
 254     fn from_bytes(b: &[u8; 8]) -> Self {
 255         let ([ref position_bytes, ref meta_bytes],[])= b.as_chunks::<4>() else { panic!() };
 256         let position = NonZeroUsize::new(u32::from_bytes(position_bytes) as usize)?;
 257         let len = u32::from_bytes(meta_bytes) as usize;
 258         Some(LazyArray::from_position_and_num_elems(position, len))
 259     }
 260
 261     #[inline]
 262     fn write_to_bytes(self, b: &mut [u8; 8]) {
 263         let ([ref mut position_bytes, ref mut meta_bytes],[])= b.as_chunks_mut::<4>() else { panic!() };
 264
 265         let position = self.map_or(0, |lazy| lazy.position.get());
 266         let position: u32 = position.try_into().unwrap();
 267         position.write_to_bytes(position_bytes);
 268
 269         let len = self.map_or(0, |lazy| lazy.num_elems);
 270         let len: u32 = len.try_into().unwrap();
 271         len.write_to_bytes(meta_bytes);
 272     }
 273 }
 274
 275 /// Helper for constructing a table's serialization (also see `Table`).
 276 pub(super) struct TableBuilder<I: Idx, T>
 277 where
 278     Option<T>: FixedSizeEncoding,
 279 {
 280     blocks: IndexVec<I, <Option<T> as FixedSizeEncoding>::ByteArray>,
 281     _marker: PhantomData<T>,
 282 }
 283
 284 impl<I: Idx, T> Default for TableBuilder<I, T>
 285 where
 286     Option<T>: FixedSizeEncoding,
 287 {
 288     fn default() -> Self {
 289         TableBuilder { blocks: Default::default(), _marker: PhantomData }
 290     }
 291 }
 292
 293 impl<I: Idx, T> TableBuilder<I, T>
 294 where
 295     Option<T>: FixedSizeEncoding,
 296 {
 297     pub(crate) fn set<const N: usize>(&mut self, i: I, value: T)
 298     where
 299         Option<T>: FixedSizeEncoding<ByteArray = [u8; N]>,
 300     {
 301         // FIXME(eddyb) investigate more compact encodings for sparse tables.
 302         // On the PR @michaelwoerister mentioned:
 303         // > Space requirements could perhaps be optimized by using the HAMT `popcnt`
 304         // > trick (i.e. divide things into buckets of 32 or 64 items and then
 305         // > store bit-masks of which item in each bucket is actually serialized).
 306         self.blocks.ensure_contains_elem(i, || [0; N]);
 307         Some(value).write_to_bytes(&mut self.blocks[i]);
 308     }
 309
 310     pub(crate) fn encode<const N: usize>(&self, buf: &mut FileEncoder) -> LazyTable<I, T>
 311     where
 312         Option<T>: FixedSizeEncoding<ByteArray = [u8; N]>,
 313     {
 314         let pos = buf.position();
 315         for block in &self.blocks {
 316             buf.emit_raw_bytes(block);
 317         }
 318         let num_bytes = self.blocks.len() * N;
 319         LazyTable::from_position_and_encoded_size(
 320             NonZeroUsize::new(pos as usize).unwrap(),
 321             num_bytes,
 322         )
 323     }
 324 }
 325
 326 impl<I: Idx, T: ParameterizedOverTcx> LazyTable<I, T>
 327 where
 328     Option<T>: FixedSizeEncoding,
 329 {
 330     /// Given the metadata, extract out the value at a particular index (if any).
 331     #[inline(never)]
 332     pub(super) fn get<'a, 'tcx, M: Metadata<'a, 'tcx>, const N: usize>(
 333         &self,
 334         metadata: M,
 335         i: I,
 336     ) -> Option<T::Value<'tcx>>
 337     where
 338         Option<T::Value<'tcx>>: FixedSizeEncoding<ByteArray = [u8; N]>,
 339     {
 340         debug!("LazyTable::lookup: index={:?} len={:?}", i, self.encoded_size);
 341
 342         let start = self.position.get();
 343         let bytes = &metadata.blob()[start..start + self.encoded_size];
 344         let (bytes, []) = bytes.as_chunks::<N>() else { panic!() };
 345         let bytes = bytes.get(i.index())?;
 346         FixedSizeEncoding::from_bytes(bytes)
 347     }
 348
 349     /// Size of the table in entries, including possible gaps.
 350     pub(super) fn size<const N: usize>(&self) -> usize
 351     where
 352         for<'tcx> Option<T::Value<'tcx>>: FixedSizeEncoding<ByteArray = [u8; N]>,
 353     {
 354         self.encoded_size / N
 355     }
 356 }