src/librustc_metadata/table.rs

   1 use crate::decoder::Metadata;
   2 use crate::schema::*;
   3
   4 use rustc::hir::def_id::{DefId, DefIndex};
   5 use rustc_serialize::{Encodable, opaque::Encoder};
   6 use std::convert::TryInto;
   7 use std::marker::PhantomData;
   8 use std::num::NonZeroUsize;
   9 use log::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 crate 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(
  47                     b.as_ptr() as *const [u8; BYTE_LEN],
  48                     b.len() / BYTE_LEN,
  49                 )
  50             };
  51             b.get(i).map(|b| FixedSizeEncoding::from_bytes(b))
  52         }
  53         fn write_to_bytes_at(self, b: &mut [u8], i: usize) {
  54             const BYTE_LEN: usize = $byte_len;
  55             // HACK(eddyb) ideally this would be done with fully safe code,
  56             // see similar comment in `read_from_bytes_at` for why it can't yet.
  57             let b = unsafe {
  58                 std::slice::from_raw_parts_mut(
  59                     b.as_mut_ptr() as *mut [u8; BYTE_LEN],
  60                     b.len() / BYTE_LEN,
  61                 )
  62             };
  63             self.write_to_bytes(&mut b[i]);
  64         }
  65     }
  66 }
  67
  68 impl FixedSizeEncoding for u32 {
  69     fixed_size_encoding_byte_len_and_defaults!(4);
  70
  71     fn from_bytes(b: &[u8]) -> Self {
  72         let mut bytes = [0; Self::BYTE_LEN];
  73         bytes.copy_from_slice(&b[..Self::BYTE_LEN]);
  74         Self::from_le_bytes(bytes)
  75     }
  76
  77     fn write_to_bytes(self, b: &mut [u8]) {
  78         b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
  79     }
  80 }
  81
  82 // NOTE(eddyb) there could be an impl for `usize`, which would enable a more
  83 // generic `Lazy<T>` impl, but in the general case we might not need / want to
  84 // fit every `usize` in `u32`.
  85 impl<T: Encodable> FixedSizeEncoding for Option<Lazy<T>> {
  86     fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN);
  87
  88     fn from_bytes(b: &[u8]) -> Self {
  89         Some(Lazy::from_position(NonZeroUsize::new(u32::from_bytes(b) as usize)?))
  90     }
  91
  92     fn write_to_bytes(self, b: &mut [u8]) {
  93         let position = self.map_or(0, |lazy| lazy.position.get());
  94         let position: u32 = position.try_into().unwrap();
  95
  96         position.write_to_bytes(b)
  97     }
  98 }
  99
 100 impl<T: Encodable> FixedSizeEncoding for Option<Lazy<[T]>> {
 101     fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN * 2);
 102
 103     fn from_bytes(b: &[u8]) -> Self {
 104         Some(Lazy::from_position_and_meta(
 105             <Option<Lazy<T>>>::from_bytes(b)?.position,
 106             u32::from_bytes(&b[u32::BYTE_LEN..]) as usize,
 107         ))
 108     }
 109
 110     fn write_to_bytes(self, b: &mut [u8]) {
 111         self.map(|lazy| Lazy::<T>::from_position(lazy.position))
 112             .write_to_bytes(b);
 113
 114         let len = self.map_or(0, |lazy| lazy.meta);
 115         let len: u32 = len.try_into().unwrap();
 116
 117         len.write_to_bytes(&mut b[u32::BYTE_LEN..]);
 118     }
 119 }
 120
 121 /// Random-access table (i.e. offeringconstant-time `get`/`set`), similar to
 122 /// `Vec<Option<T>>`, but without requiring encoding or decoding all the values
 123 /// eagerly and in-order.
 124 /// A total of `(max_idx + 1) * <Option<T> as FixedSizeEncoding>::BYTE_LEN` bytes
 125 /// are used for a table, where `max_idx` is the largest index passed to `set`.
 126 // FIXME(eddyb) replace `Vec` with `[_]` here, such that `Box<Table<T>>` would be used
 127 // when building it, and `Lazy<Table<T>>` or `&Table<T>` when reading it.
 128 // (not sure if that is possible given that the `Vec` is being resized now)
 129 crate struct Table<T> where Option<T>: FixedSizeEncoding {
 130     // FIXME(eddyb) store `[u8; <Option<T>>::BYTE_LEN]` instead of `u8` in `Vec`,
 131     // once that starts being allowed by the compiler (i.e. lazy normalization).
 132     bytes: Vec<u8>,
 133     _marker: PhantomData<T>,
 134 }
 135
 136 impl<T> Default for Table<T> where Option<T>: FixedSizeEncoding {
 137     fn default() -> Self {
 138         Table {
 139             bytes: vec![],
 140             _marker: PhantomData,
 141         }
 142     }
 143 }
 144
 145 impl<T> Table<T> where Option<T>: FixedSizeEncoding {
 146     crate fn set(&mut self, i: usize, value: T) {
 147         // FIXME(eddyb) investigate more compact encodings for sparse tables.
 148         // On the PR @michaelwoerister mentioned:
 149         // > Space requirements could perhaps be optimized by using the HAMT `popcnt`
 150         // > trick (i.e. divide things into buckets of 32 or 64 items and then
 151         // > store bit-masks of which item in each bucket is actually serialized).
 152         let needed = (i + 1) * <Option<T>>::BYTE_LEN;
 153         if self.bytes.len() < needed {
 154             self.bytes.resize(needed, 0);
 155         }
 156
 157         Some(value).write_to_bytes_at(&mut self.bytes, i);
 158     }
 159
 160     crate fn encode(&self, buf: &mut Encoder) -> Lazy<Self> {
 161         let pos = buf.position();
 162         buf.emit_raw_bytes(&self.bytes);
 163         Lazy::from_position_and_meta(
 164             NonZeroUsize::new(pos as usize).unwrap(),
 165             self.bytes.len(),
 166         )
 167     }
 168 }
 169
 170 impl<T> LazyMeta for Table<T> where Option<T>: FixedSizeEncoding {
 171     type Meta = usize;
 172
 173     fn min_size(len: usize) -> usize {
 174         len
 175     }
 176 }
 177
 178 impl<T> Lazy<Table<T>> where Option<T>: FixedSizeEncoding {
 179     /// Given the metadata, extract out the value at a particular index (if any).
 180     #[inline(never)]
 181     crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
 182         &self,
 183         metadata: M,
 184         i: usize,
 185     ) -> Option<T> {
 186         debug!("Table::lookup: index={:?} len={:?}", i, self.meta);
 187
 188         let start = self.position.get();
 189         let bytes = &metadata.raw_bytes()[start..start + self.meta];
 190         <Option<T>>::maybe_read_from_bytes_at(bytes, i)?
 191     }
 192 }
 193
 194 /// Like a `Table` but using `DefIndex` instead of `usize` as keys.
 195 // FIXME(eddyb) replace by making `Table` behave like `IndexVec`,
 196 // and by using `newtype_index!` to define `DefIndex`.
 197 crate struct PerDefTable<T>(Table<T>) where Option<T>: FixedSizeEncoding;
 198
 199 impl<T> Default for PerDefTable<T> where Option<T>: FixedSizeEncoding {
 200     fn default() -> Self {
 201         PerDefTable(Table::default())
 202     }
 203 }
 204
 205 impl<T> PerDefTable<T> where Option<T>: FixedSizeEncoding {
 206     crate fn set(&mut self, def_id: DefId, value: T) {
 207         assert!(def_id.is_local());
 208         self.0.set(def_id.index.index(), value);
 209     }
 210
 211     crate fn encode(&self, buf: &mut Encoder) -> Lazy<Self> {
 212         let lazy = self.0.encode(buf);
 213         Lazy::from_position_and_meta(lazy.position, lazy.meta)
 214     }
 215 }
 216
 217 impl<T> LazyMeta for PerDefTable<T> where Option<T>: FixedSizeEncoding {
 218     type Meta = <Table<T> as LazyMeta>::Meta;
 219
 220     fn min_size(meta: Self::Meta) -> usize {
 221         Table::<T>::min_size(meta)
 222     }
 223 }
 224
 225 impl<T> Lazy<PerDefTable<T>> where Option<T>: FixedSizeEncoding {
 226     fn as_table(&self) -> Lazy<Table<T>> {
 227         Lazy::from_position_and_meta(self.position, self.meta)
 228     }
 229
 230     /// Given the metadata, extract out the value at a particular DefIndex (if any).
 231     #[inline(never)]
 232     crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
 233         &self,
 234         metadata: M,
 235         def_index: DefIndex,
 236     ) -> Option<T> {
 237         self.as_table().get(metadata, def_index.index())
 238     }
 239 }