src/librustc_metadata/index.rs

   1 use crate::schema::*;
   2
   3 use rustc::hir::def_id::{DefId, DefIndex};
   4 use rustc_serialize::opaque::Encoder;
   5 use std::marker::PhantomData;
   6 use std::u32;
   7 use log::debug;
   8
   9 /// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
  10 pub trait FixedSizeEncoding {
  11     const BYTE_LEN: usize;
  12
  13     // FIXME(eddyb) convert to and from `[u8; Self::BYTE_LEN]` instead,
  14     // once that starts being allowed by the compiler (i.e. lazy normalization).
  15     fn from_bytes(b: &[u8]) -> Self;
  16     fn write_to_bytes(self, b: &mut [u8]);
  17
  18     // FIXME(eddyb) make these generic functions, or at least defaults here.
  19     // (same problem as above, needs `[u8; Self::BYTE_LEN]`)
  20     // For now, a macro (`fixed_size_encoding_byte_len_and_defaults`) is used.
  21     fn read_from_bytes_at(b: &[u8], i: usize) -> Self;
  22     fn write_to_bytes_at(self, b: &mut [u8], i: usize);
  23 }
  24
  25 // HACK(eddyb) this shouldn't be needed (see comments on the methods above).
  26 macro_rules! fixed_size_encoding_byte_len_and_defaults {
  27     ($byte_len:expr) => {
  28         const BYTE_LEN: usize = $byte_len;
  29         fn read_from_bytes_at(b: &[u8], i: usize) -> Self {
  30             const BYTE_LEN: usize = $byte_len;
  31             // HACK(eddyb) ideally this would be done with fully safe code,
  32             // but slicing `[u8]` with `i * N..` is optimized worse, due to the
  33             // possibility of `i * N` overflowing, than indexing `[[u8; N]]`.
  34             let b = unsafe {
  35                 std::slice::from_raw_parts(
  36                     b.as_ptr() as *const [u8; BYTE_LEN],
  37                     b.len() / BYTE_LEN,
  38                 )
  39             };
  40             Self::from_bytes(&b[i])
  41         }
  42         fn write_to_bytes_at(self, b: &mut [u8], i: usize) {
  43             const BYTE_LEN: usize = $byte_len;
  44             // HACK(eddyb) ideally this would be done with fully safe code,
  45             // see similar comment in `read_from_bytes_at` for why it can't yet.
  46             let b = unsafe {
  47                 std::slice::from_raw_parts_mut(
  48                     b.as_mut_ptr() as *mut [u8; BYTE_LEN],
  49                     b.len() / BYTE_LEN,
  50                 )
  51             };
  52             self.write_to_bytes(&mut b[i]);
  53         }
  54     }
  55 }
  56
  57 impl FixedSizeEncoding for u32 {
  58     fixed_size_encoding_byte_len_and_defaults!(4);
  59
  60     fn from_bytes(b: &[u8]) -> Self {
  61         let mut bytes = [0; Self::BYTE_LEN];
  62         bytes.copy_from_slice(&b[..Self::BYTE_LEN]);
  63         Self::from_le_bytes(bytes)
  64     }
  65
  66     fn write_to_bytes(self, b: &mut [u8]) {
  67         b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
  68     }
  69 }
  70
  71 /// While we are generating the metadata, we also track the position
  72 /// of each DefIndex. It is not required that all definitions appear
  73 /// in the metadata, nor that they are serialized in order, and
  74 /// therefore we first allocate the vector here and fill it with
  75 /// `u32::MAX`. Whenever an index is visited, we fill in the
  76 /// appropriate spot by calling `record_position`. We should never
  77 /// visit the same index twice.
  78 pub struct Index<'tcx> {
  79     positions: Vec<u8>,
  80     _marker: PhantomData<&'tcx ()>,
  81 }
  82
  83 impl Index<'tcx> {
  84     pub fn new(max_index: usize) -> Self {
  85         Index {
  86             positions: vec![0xff; max_index * 4],
  87             _marker: PhantomData,
  88         }
  89     }
  90
  91     pub fn record(&mut self, def_id: DefId, entry: Lazy<Entry<'tcx>>) {
  92         assert!(def_id.is_local());
  93         self.record_index(def_id.index, entry);
  94     }
  95
  96     pub fn record_index(&mut self, item: DefIndex, entry: Lazy<Entry<'tcx>>) {
  97         assert!(entry.position < (u32::MAX as usize));
  98         let position = entry.position as u32;
  99         let array_index = item.index();
 100
 101         let positions = &mut self.positions;
 102         assert!(u32::read_from_bytes_at(positions, array_index) == u32::MAX,
 103                 "recorded position for item {:?} twice, first at {:?} and now at {:?}",
 104                 item,
 105                 u32::read_from_bytes_at(positions, array_index),
 106                 position);
 107
 108         position.write_to_bytes_at(positions, array_index)
 109     }
 110
 111     pub fn write_index(&self, buf: &mut Encoder) -> LazySeq<Self> {
 112         let pos = buf.position();
 113
 114         // First we write the length of the lower range ...
 115         buf.emit_raw_bytes(&(self.positions.len() as u32 / 4).to_le_bytes());
 116         // ... then the values.
 117         buf.emit_raw_bytes(&self.positions);
 118         LazySeq::with_position_and_length(pos as usize, self.positions.len() / 4 + 1)
 119     }
 120 }
 121
 122 impl LazySeq<Index<'tcx>> {
 123     /// Given the metadata, extract out the offset of a particular
 124     /// DefIndex (if any).
 125     #[inline(never)]
 126     pub fn lookup(&self, bytes: &[u8], def_index: DefIndex) -> Option<Lazy<Entry<'tcx>>> {
 127         let bytes = &bytes[self.position..];
 128         debug!("Index::lookup: index={:?} len={:?}",
 129                def_index,
 130                self.len);
 131
 132         let position = u32::read_from_bytes_at(bytes, 1 + def_index.index());
 133         if position == u32::MAX {
 134             debug!("Index::lookup: position=u32::MAX");
 135             None
 136         } else {
 137             debug!("Index::lookup: position={:?}", position);
 138             Some(Lazy::with_position(position as usize))
 139         }
 140     }
 141 }