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