compiler/rustc_metadata/src/rmeta/table.rs

   1 use crate::rmeta::*;
   2
   3 use rustc_index::vec::Idx;
   4 use rustc_serialize::opaque::Encoder;
   5 use rustc_serialize::Encoder as _;
   6 use std::convert::TryInto;
   7 use std::marker::PhantomData;
   8 use std::num::NonZeroUsize;
   9 use tracing::debug;
  10
  11 /// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
  12 /// Used mainly for Lazy positions and lengths.
  13 /// Unchecked invariant: `Self::default()` should encode as `[0; BYTE_LEN]`,
  14 /// but this has no impact on safety.
  15 pub(super) trait FixedSizeEncoding: Default {
  16     const BYTE_LEN: usize;
  17
  18     // FIXME(eddyb) convert to and from `[u8; Self::BYTE_LEN]` instead,
  19     // once that starts being allowed by the compiler (i.e. lazy normalization).
  20     fn from_bytes(b: &[u8]) -> Self;
  21     fn write_to_bytes(self, b: &mut [u8]);
  22
  23     // FIXME(eddyb) make these generic functions, or at least defaults here.
  24     // (same problem as above, needs `[u8; Self::BYTE_LEN]`)
  25     // For now, a macro (`fixed_size_encoding_byte_len_and_defaults`) is used.
  26
  27     /// Read a `Self` value (encoded as `Self::BYTE_LEN` bytes),
  28     /// from `&b[i * Self::BYTE_LEN..]`, returning `None` if `i`
  29     /// is not in bounds, or `Some(Self::from_bytes(...))` otherwise.
  30     fn maybe_read_from_bytes_at(b: &[u8], i: usize) -> Option<Self>;
  31     /// Write a `Self` value (encoded as `Self::BYTE_LEN` bytes),
  32     /// at `&mut b[i * Self::BYTE_LEN..]`, using `Self::write_to_bytes`.
  33     fn write_to_bytes_at(self, b: &mut [u8], i: usize);
  34 }
  35
  36 // HACK(eddyb) this shouldn't be needed (see comments on the methods above).
  37 macro_rules! fixed_size_encoding_byte_len_and_defaults {
  38     ($byte_len:expr) => {
  39         const BYTE_LEN: usize = $byte_len;
  40         fn maybe_read_from_bytes_at(b: &[u8], i: usize) -> Option<Self> {
  41             const BYTE_LEN: usize = $byte_len;
  42             // HACK(eddyb) ideally this would be done with fully safe code,
  43             // but slicing `[u8]` with `i * N..` is optimized worse, due to the
  44             // possibility of `i * N` overflowing, than indexing `[[u8; N]]`.
  45             let b = unsafe {
  46                 std::slice::from_raw_parts(b.as_ptr() as *const [u8; BYTE_LEN], b.len() / BYTE_LEN)
  47             };
  48             b.get(i).map(|b| FixedSizeEncoding::from_bytes(b))
  49         }
  50         fn write_to_bytes_at(self, b: &mut [u8], i: usize) {
  51             const BYTE_LEN: usize = $byte_len;
  52             // HACK(eddyb) ideally this would be done with fully safe code,
  53             // see similar comment in `read_from_bytes_at` for why it can't yet.
  54             let b = unsafe {
  55                 std::slice::from_raw_parts_mut(
  56                     b.as_mut_ptr() as *mut [u8; BYTE_LEN],
  57                     b.len() / BYTE_LEN,
  58                 )
  59             };
  60             self.write_to_bytes(&mut b[i]);
  61         }
  62     };
  63 }
  64
  65 impl FixedSizeEncoding for u32 {
  66     fixed_size_encoding_byte_len_and_defaults!(4);
  67
  68     fn from_bytes(b: &[u8]) -> Self {
  69         let mut bytes = [0; Self::BYTE_LEN];
  70         bytes.copy_from_slice(&b[..Self::BYTE_LEN]);
  71         Self::from_le_bytes(bytes)
  72     }
  73
  74     fn write_to_bytes(self, b: &mut [u8]) {
  75         b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
  76     }
  77 }
  78
  79 // NOTE(eddyb) there could be an impl for `usize`, which would enable a more
  80 // generic `Lazy<T>` impl, but in the general case we might not need / want to
  81 // fit every `usize` in `u32`.
  82 impl<T> FixedSizeEncoding for Option<Lazy<T>> {
  83     fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN);
  84
  85     fn from_bytes(b: &[u8]) -> Self {
  86         Some(Lazy::from_position(NonZeroUsize::new(u32::from_bytes(b) as usize)?))
  87     }
  88
  89     fn write_to_bytes(self, b: &mut [u8]) {
  90         let position = self.map_or(0, |lazy| lazy.position.get());
  91         let position: u32 = position.try_into().unwrap();
  92
  93         position.write_to_bytes(b)
  94     }
  95 }
  96
  97 impl<T> FixedSizeEncoding for Option<Lazy<[T]>> {
  98     fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN * 2);
  99
 100     fn from_bytes(b: &[u8]) -> Self {
 101         Some(Lazy::from_position_and_meta(
 102             <Option<Lazy<T>>>::from_bytes(b)?.position,
 103             u32::from_bytes(&b[u32::BYTE_LEN..]) as usize,
 104         ))
 105     }
 106
 107     fn write_to_bytes(self, b: &mut [u8]) {
 108         self.map(|lazy| Lazy::<T>::from_position(lazy.position)).write_to_bytes(b);
 109
 110         let len = self.map_or(0, |lazy| lazy.meta);
 111         let len: u32 = len.try_into().unwrap();
 112
 113         len.write_to_bytes(&mut b[u32::BYTE_LEN..]);
 114     }
 115 }
 116
 117 /// Random-access table (i.e. offering constant-time `get`/`set`), similar to
 118 /// `Vec<Option<T>>`, but without requiring encoding or decoding all the values
 119 /// eagerly and in-order.
 120 /// A total of `(max_idx + 1) * <Option<T> as FixedSizeEncoding>::BYTE_LEN` bytes
 121 /// are used for a table, where `max_idx` is the largest index passed to
 122 /// `TableBuilder::set`.
 123 pub(super) struct Table<I: Idx, T>
 124 where
 125     Option<T>: FixedSizeEncoding,
 126 {
 127     _marker: PhantomData<(fn(&I), T)>,
 128     // NOTE(eddyb) this makes `Table` not implement `Sized`, but no
 129     // value of `Table` is ever created (it's always behind `Lazy`).
 130     _bytes: [u8],
 131 }
 132
 133 /// Helper for constructing a table's serialization (also see `Table`).
 134 pub(super) struct TableBuilder<I: Idx, T>
 135 where
 136     Option<T>: FixedSizeEncoding,
 137 {
 138     // FIXME(eddyb) use `IndexVec<I, [u8; <Option<T>>::BYTE_LEN]>` instead of
 139     // `Vec<u8>`, once that starts working (i.e. lazy normalization).
 140     // Then again, that has the downside of not allowing `TableBuilder::encode` to
 141     // obtain a `&[u8]` entirely in safe code, for writing the bytes out.
 142     bytes: Vec<u8>,
 143     _marker: PhantomData<(fn(&I), T)>,
 144 }
 145
 146 impl<I: Idx, T> Default for TableBuilder<I, T>
 147 where
 148     Option<T>: FixedSizeEncoding,
 149 {
 150     fn default() -> Self {
 151         TableBuilder { bytes: vec![], _marker: PhantomData }
 152     }
 153 }
 154
 155 impl<I: Idx, T> TableBuilder<I, T>
 156 where
 157     Option<T>: FixedSizeEncoding,
 158 {
 159     pub(crate) fn set(&mut self, i: I, value: T) {
 160         // FIXME(eddyb) investigate more compact encodings for sparse tables.
 161         // On the PR @michaelwoerister mentioned:
 162         // > Space requirements could perhaps be optimized by using the HAMT `popcnt`
 163         // > trick (i.e. divide things into buckets of 32 or 64 items and then
 164         // > store bit-masks of which item in each bucket is actually serialized).
 165         let i = i.index();
 166         let needed = (i + 1) * <Option<T>>::BYTE_LEN;
 167         if self.bytes.len() < needed {
 168             self.bytes.resize(needed, 0);
 169         }
 170
 171         Some(value).write_to_bytes_at(&mut self.bytes, i);
 172     }
 173
 174     pub(crate) fn encode(&self, buf: &mut Encoder) -> Lazy<Table<I, T>> {
 175         let pos = buf.position();
 176         buf.emit_raw_bytes(&self.bytes).unwrap();
 177         Lazy::from_position_and_meta(NonZeroUsize::new(pos as usize).unwrap(), self.bytes.len())
 178     }
 179 }
 180
 181 impl<I: Idx, T> LazyMeta for Table<I, T>
 182 where
 183     Option<T>: FixedSizeEncoding,
 184 {
 185     type Meta = usize;
 186
 187     fn min_size(len: usize) -> usize {
 188         len
 189     }
 190 }
 191
 192 impl<I: Idx, T> Lazy<Table<I, T>>
 193 where
 194     Option<T>: FixedSizeEncoding,
 195 {
 196     /// Given the metadata, extract out the value at a particular index (if any).
 197     #[inline(never)]
 198     pub(super) fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(&self, metadata: M, i: I) -> Option<T> {
 199         debug!("Table::lookup: index={:?} len={:?}", i, self.meta);
 200
 201         let start = self.position.get();
 202         let bytes = &metadata.blob()[start..start + self.meta];
 203         <Option<T>>::maybe_read_from_bytes_at(bytes, i.index())?
 204     }
 205
 206     /// Size of the table in entries, including possible gaps.
 207     pub(super) fn size(&self) -> usize {
 208         self.meta / <Option<T>>::BYTE_LEN
 209     }
 210 }