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