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 std::io::{Cursor, Write};
  12 use std::slice;
  13 use std::u32;
  14 use syntax::ast::NodeId;
  15
  16 #[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord)]
  17 pub struct IndexEntry {
  18     pub node: NodeId,
  19     pub pos: u64
  20 }
  21
  22 #[derive(Debug)]
  23 pub struct IndexArrayEntry {
  24     bits: u32,
  25     first_pos: u32
  26 }
  27
  28 impl IndexArrayEntry {
  29     fn encode_to<W: Write>(&self, b: &mut W) {
  30         write_be_u32(b, self.bits);
  31         write_be_u32(b, self.first_pos);
  32     }
  33
  34     fn decode_from(b: &[u32]) -> Self {
  35         IndexArrayEntry {
  36             bits: b[0].to_be(),
  37             first_pos: b[1].to_be()
  38         }
  39     }
  40 }
  41
  42 /// The Item Index
  43 ///
  44 /// This index maps the NodeId of each item to its location in the
  45 /// metadata.
  46 ///
  47 /// The index is a sparse bit-vector consisting of a index-array
  48 /// and a position-array. Each entry in the index-array handles 32 nodes.
  49 /// The first word is a bit-array consisting of the nodes that hold items,
  50 /// the second is the index of the first of the items in the position-array.
  51 /// If there is a large set of non-item trailing nodes, they can be omitted
  52 /// from the index-array.
  53 ///
  54 /// The index is serialized as an array of big-endian 32-bit words.
  55 /// The first word is the number of items in the position-array.
  56 /// Then, for each item, its position in the metadata follows.
  57 /// After that the index-array is stored.
  58 ///
  59 /// struct index {
  60 ///     u32 item_count;
  61 ///     u32 items[self.item_count];
  62 ///     struct { u32 bits; u32 offset; } positions[..];
  63 /// }
  64 pub struct Index {
  65     position_start: usize,
  66     index_start: usize,
  67     index_end: usize,
  68 }
  69
  70 pub fn write_index(mut entries: Vec<IndexEntry>, buf: &mut Cursor<Vec<u8>>) {
  71     assert!(entries.len() < u32::MAX as usize);
  72     entries.sort();
  73
  74     let mut last_entry = IndexArrayEntry { bits: 0, first_pos: 0 };
  75
  76     write_be_u32(buf, entries.len() as u32);
  77     for &IndexEntry { pos, .. } in &entries {
  78         assert!(pos < u32::MAX as u64);
  79         write_be_u32(buf, pos as u32);
  80     }
  81
  82     let mut pos_in_index_array = 0;
  83     for (i, &IndexEntry { node, .. }) in entries.iter().enumerate() {
  84         let (x, s) = (node / 32 as u32, node % 32 as u32);
  85         while x > pos_in_index_array {
  86             pos_in_index_array += 1;
  87             last_entry.encode_to(buf);
  88             last_entry = IndexArrayEntry { bits: 0, first_pos: i as u32 };
  89         }
  90         last_entry.bits |= 1<<s;
  91     }
  92     last_entry.encode_to(buf);
  93
  94     info!("write_index: {} items, {} array entries",
  95           entries.len(), pos_in_index_array);
  96 }
  97
  98 impl Index {
  99     fn lookup_index(&self, index: &[u32], i: u32) -> Option<IndexArrayEntry> {
 100         let ix = (i as usize)*2;
 101         if ix >= index.len() {
 102             None
 103         } else {
 104             Some(IndexArrayEntry::decode_from(&index[ix..ix+2]))
 105         }
 106     }
 107
 108     fn item_from_pos(&self, positions: &[u32], pos: u32) -> u32 {
 109         positions[pos as usize].to_be()
 110     }
 111
 112     #[inline(never)]
 113     pub fn lookup_item(&self, buf: &[u8], node: NodeId) -> Option<u32> {
 114         let index = bytes_to_words(&buf[self.index_start..self.index_end]);
 115         let positions = bytes_to_words(&buf[self.position_start..self.index_start]);
 116         let (x, s) = (node / 32 as u32, node % 32 as u32);
 117         let result = match self.lookup_index(index, x) {
 118             Some(IndexArrayEntry { bits, first_pos }) => {
 119                 let bit = 1<<s;
 120                 if bits & bit == 0 {
 121                     None
 122                 } else {
 123                     let prev_nodes_for_entry = (bits&(bit-1)).count_ones();
 124                     Some(self.item_from_pos(
 125                         positions,
 126                         first_pos+prev_nodes_for_entry))
 127                 }
 128             }
 129             None => None // trailing zero
 130         };
 131         debug!("lookup_item({:?}) = {:?}", node, result);
 132         result
 133     }
 134
 135     pub fn from_buf(buf: &[u8], start: usize, end: usize) -> Self {
 136         let buf = bytes_to_words(&buf[start..end]);
 137         let position_count = buf[0].to_be() as usize;
 138         let position_len = position_count*4;
 139         info!("loaded index - position: {}-{}-{}", start, start+position_len, end);
 140         debug!("index contents are {:?}",
 141                buf.iter().map(|b| format!("{:08x}", b)).collect::<Vec<_>>().concat());
 142         assert!(end-4-start >= position_len);
 143         assert_eq!((end-4-start-position_len)%8, 0);
 144         Index {
 145             position_start: start+4,
 146             index_start: start+position_len+4,
 147             index_end: end
 148         }
 149     }
 150 }
 151
 152 fn write_be_u32<W: Write>(w: &mut W, u: u32) {
 153     let _ = w.write_all(&[
 154         (u >> 24) as u8,
 155         (u >> 16) as u8,
 156         (u >>  8) as u8,
 157         (u >>  0) as u8,
 158     ]);
 159 }
 160
 161 fn bytes_to_words(b: &[u8]) -> &[u32] {
 162     assert!(b.len() % 4 == 0);
 163     unsafe { slice::from_raw_parts(b.as_ptr() as *const u32, b.len()/4) }
 164 }
 165
 166 #[test]
 167 fn test_index() {
 168     let entries = vec![
 169         IndexEntry { node: 0, pos: 17 },
 170         IndexEntry { node: 31, pos: 29 },
 171         IndexEntry { node: 32, pos: 1175 },
 172         IndexEntry { node: 191, pos: 21 },
 173         IndexEntry { node: 128, pos: 34 },
 174         IndexEntry { node: 145, pos: 70 },
 175         IndexEntry { node: 305, pos: 93214 },
 176         IndexEntry { node: 138, pos: 64 },
 177         IndexEntry { node: 129, pos: 53 },
 178         IndexEntry { node: 192, pos: 33334 },
 179         IndexEntry { node: 200, pos: 80123 },
 180     ];
 181     let mut c = Cursor::new(vec![]);
 182     write_index(entries.clone(), &mut c);
 183     let mut buf = c.into_inner();
 184     let expected: &[u8] = &[
 185         0, 0, 0, 11, // # entries
 186         // values:
 187         0,0,0,17, 0,0,0,29, 0,0,4,151, 0,0,0,34,
 188         0,0,0,53, 0,0,0,64, 0,0,0,70, 0,0,0,21,
 189         0,0,130,54, 0,1,56,251, 0,1,108,30,
 190         // index:
 191         128,0,0,1,0,0,0,0, 0,0,0,1,0,0,0,2,
 192         0,0,0,0,0,0,0,3,   0,0,0,0,0,0,0,3,
 193         0,2,4,3,0,0,0,3,   128,0,0,0,0,0,0,7,
 194         0,0,1,1,0,0,0,8,   0,0,0,0,0,0,0,10,
 195         0,0,0,0,0,0,0,10,  0,2,0,0,0,0,0,10
 196     ];
 197     assert_eq!(buf, expected);
 198
 199     // insert some junk padding
 200     for i in 0..17 { buf.insert(0, i); buf.push(i) }
 201     let index = Index::from_buf(&buf, 17, buf.len()-17);
 202
 203     // test round-trip
 204     for i in 0..4096 {
 205         assert_eq!(index.lookup_item(&buf, i),
 206                    entries.iter().find(|e| e.node == i).map(|n| n.pos as u32));
 207     }
 208 }