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