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 rustc::hir::def_id::{DefId, DefIndex};
  12 use rbml;
  13 use std::io::{Cursor, Write};
  14 use std::slice;
  15 use std::u32;
  16
  17 /// As part of the metadata, we generate an index that stores, for
  18 /// each DefIndex, the position of the corresponding RBML document (if
  19 /// any).  This is just a big `[u32]` slice, where an entry of
  20 /// `u32::MAX` indicates that there is no RBML document. This little
  21 /// struct just stores the offsets within the metadata of the start
  22 /// and end of this slice. These are actually part of an RBML
  23 /// document, but for looking things up in the metadata, we just
  24 /// discard the RBML positioning and jump directly to the data.
  25 pub struct Index {
  26     data_start: usize,
  27     data_end: usize,
  28 }
  29
  30 impl Index {
  31     /// Given the RBML doc representing the index, save the offests
  32     /// for later.
  33     pub fn from_rbml(index: rbml::Doc) -> Index {
  34         Index { data_start: index.start, data_end: index.end }
  35     }
  36
  37     /// Given the metadata, extract out the offset of a particular
  38     /// DefIndex (if any).
  39     #[inline(never)]
  40     pub fn lookup_item(&self, bytes: &[u8], def_index: DefIndex) -> Option<u32> {
  41         let words = bytes_to_words(&bytes[self.data_start..self.data_end]);
  42         let index = def_index.as_usize();
  43
  44         debug!("lookup_item: index={:?} words.len={:?}",
  45                index, words.len());
  46
  47         let position = u32::from_be(words[index]);
  48         if position == u32::MAX {
  49             debug!("lookup_item: position=u32::MAX");
  50             None
  51         } else {
  52             debug!("lookup_item: position={:?}", position);
  53             Some(position)
  54         }
  55     }
  56 }
  57
  58 /// While we are generating the metadata, we also track the position
  59 /// of each DefIndex. It is not required that all definitions appear
  60 /// in the metadata, nor that they are serialized in order, and
  61 /// therefore we first allocate the vector here and fill it with
  62 /// `u32::MAX`. Whenever an index is visited, we fill in the
  63 /// appropriate spot by calling `record_position`. We should never
  64 /// visit the same index twice.
  65 pub struct IndexData {
  66     positions: Vec<u32>,
  67 }
  68
  69 impl IndexData {
  70     pub fn new(max_index: usize) -> IndexData {
  71         IndexData {
  72             positions: vec![u32::MAX; max_index]
  73         }
  74     }
  75
  76     pub fn record(&mut self, def_id: DefId, position: u64) {
  77         assert!(def_id.is_local());
  78         self.record_index(def_id.index, position)
  79     }
  80
  81     pub fn record_index(&mut self, item: DefIndex, position: u64) {
  82         let item = item.as_usize();
  83
  84         assert!(position < (u32::MAX as u64));
  85         let position = position as u32;
  86
  87         assert!(self.positions[item] == u32::MAX,
  88                 "recorded position for item {:?} twice, first at {:?} and now at {:?}",
  89                 item, self.positions[item], position);
  90
  91         self.positions[item] = position;
  92     }
  93
  94     pub fn write_index(&self, buf: &mut Cursor<Vec<u8>>) {
  95         for &position in &self.positions {
  96             write_be_u32(buf, position);
  97         }
  98     }
  99 }
 100
 101 /// A dense index with integer keys. Different API from IndexData (should
 102 /// these be merged?)
 103 pub struct DenseIndex {
 104     start: usize,
 105     end: usize
 106 }
 107
 108 impl DenseIndex {
 109     pub fn lookup(&self, buf: &[u8], ix: u32) -> Option<u32> {
 110         let data = bytes_to_words(&buf[self.start..self.end]);
 111         data.get(ix as usize).map(|d| u32::from_be(*d))
 112     }
 113     pub fn from_buf(buf: &[u8], start: usize, end: usize) -> Self {
 114         assert!((end-start)%4 == 0 && start <= end && end <= buf.len());
 115         DenseIndex {
 116             start: start,
 117             end: end
 118         }
 119     }
 120 }
 121
 122 pub fn write_dense_index(entries: Vec<u32>, buf: &mut Cursor<Vec<u8>>) {
 123     let elen = entries.len();
 124     assert!(elen < u32::MAX as usize);
 125
 126     for entry in entries {
 127         write_be_u32(buf, entry);
 128     }
 129
 130     info!("write_dense_index: {} entries", elen);
 131 }
 132
 133 fn write_be_u32<W: Write>(w: &mut W, u: u32) {
 134     let _ = w.write_all(&[
 135         (u >> 24) as u8,
 136         (u >> 16) as u8,
 137         (u >>  8) as u8,
 138         (u >>  0) as u8,
 139     ]);
 140 }
 141
 142 fn bytes_to_words(b: &[u8]) -> &[u32] {
 143     assert!(b.len() % 4 == 0);
 144     unsafe { slice::from_raw_parts(b.as_ptr() as *const u32, b.len()/4) }
 145 }