src/librustc_metadata/index.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use schema::*;
  12
  13 use rustc::hir::def_id::{DefId, DefIndex, DefIndexAddressSpace};
  14 use rustc_serialize::opaque::Encoder;
  15 use std::slice;
  16 use std::u32;
  17
  18 /// While we are generating the metadata, we also track the position
  19 /// of each DefIndex. It is not required that all definitions appear
  20 /// in the metadata, nor that they are serialized in order, and
  21 /// therefore we first allocate the vector here and fill it with
  22 /// `u32::MAX`. Whenever an index is visited, we fill in the
  23 /// appropriate spot by calling `record_position`. We should never
  24 /// visit the same index twice.
  25 pub struct Index {
  26     positions: [Vec<u32>; 2]
  27 }
  28
  29 impl Index {
  30     pub fn new((max_index_lo, max_index_hi): (usize, usize)) -> Index {
  31         Index {
  32             positions: [vec![u32::MAX; max_index_lo],
  33                         vec![u32::MAX; max_index_hi]],
  34         }
  35     }
  36
  37     pub fn record(&mut self, def_id: DefId, entry: Lazy<Entry>) {
  38         assert!(def_id.is_local());
  39         self.record_index(def_id.index, entry);
  40     }
  41
  42     pub fn record_index(&mut self, item: DefIndex, entry: Lazy<Entry>) {
  43         assert!(entry.position < (u32::MAX as usize));
  44         let position = entry.position as u32;
  45         let space_index = item.address_space().index();
  46         let array_index = item.as_array_index();
  47
  48         assert!(self.positions[space_index][array_index] == u32::MAX,
  49                 "recorded position for item {:?} twice, first at {:?} and now at {:?}",
  50                 item,
  51                 self.positions[space_index][array_index],
  52                 position);
  53
  54         self.positions[space_index][array_index] = position.to_le();
  55     }
  56
  57     pub fn write_index(&self, buf: &mut Encoder) -> LazySeq<Index> {
  58         let pos = buf.position();
  59
  60         // First we write the length of the lower range ...
  61         buf.emit_raw_bytes(words_to_bytes(&[(self.positions[0].len() as u32).to_le()]));
  62         // ... then the values in the lower range ...
  63         buf.emit_raw_bytes(words_to_bytes(&self.positions[0][..]));
  64         // ... then the values in the higher range.
  65         buf.emit_raw_bytes(words_to_bytes(&self.positions[1][..]));
  66         LazySeq::with_position_and_length(pos as usize,
  67             self.positions[0].len() + self.positions[1].len() + 1)
  68     }
  69 }
  70
  71 impl<'tcx> LazySeq<Index> {
  72     /// Given the metadata, extract out the offset of a particular
  73     /// DefIndex (if any).
  74     #[inline(never)]
  75     pub fn lookup(&self, bytes: &[u8], def_index: DefIndex) -> Option<Lazy<Entry<'tcx>>> {
  76         let words = &bytes_to_words(&bytes[self.position..])[..self.len];
  77
  78         debug!("Index::lookup: index={:?} words.len={:?}",
  79                def_index,
  80                words.len());
  81
  82         let positions = match def_index.address_space() {
  83             DefIndexAddressSpace::Low => &words[1..],
  84             DefIndexAddressSpace::High => {
  85                 // This is a DefIndex in the higher range, so find out where
  86                 // that starts:
  87                 let lo_count = u32::from_le(words[0].get()) as usize;
  88                 &words[lo_count + 1 .. ]
  89             }
  90         };
  91
  92         let array_index = def_index.as_array_index();
  93         let position = u32::from_le(positions[array_index].get());
  94         if position == u32::MAX {
  95             debug!("Index::lookup: position=u32::MAX");
  96             None
  97         } else {
  98             debug!("Index::lookup: position={:?}", position);
  99             Some(Lazy::with_position(position as usize))
 100         }
 101     }
 102 }
 103
 104 #[repr(packed)]
 105 #[derive(Copy)]
 106 struct Unaligned<T>(T);
 107
 108 // The derived Clone impl is unsafe for this packed struct since it needs to pass a reference to
 109 // the field to `T::clone`, but this reference may not be properly aligned.
 110 impl<T: Copy> Clone for Unaligned<T> {
 111     fn clone(&self) -> Self {
 112         *self
 113     }
 114 }
 115
 116 impl<T> Unaligned<T> {
 117     fn get(self) -> T { self.0 }
 118 }
 119
 120 fn bytes_to_words(b: &[u8]) -> &[Unaligned<u32>] {
 121     unsafe { slice::from_raw_parts(b.as_ptr() as *const Unaligned<u32>, b.len() / 4) }
 122 }
 123
 124 fn words_to_bytes(w: &[u32]) -> &[u8] {
 125     unsafe { slice::from_raw_parts(w.as_ptr() as *const u8, w.len() * 4) }
 126 }