1 use crate::decoder::Metadata;
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;
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;
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]);
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.
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);
36 // HACK(eddyb) this shouldn't be needed (see comments on the methods above).
37 macro_rules! fixed_size_encoding_byte_len_and_defaults {
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]]`.
46 std::slice::from_raw_parts(
47 b.as_ptr() as *const [u8; BYTE_LEN],
51 b.get(i).map(|b| FixedSizeEncoding::from_bytes(b))
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.
58 std::slice::from_raw_parts_mut(
59 b.as_mut_ptr() as *mut [u8; BYTE_LEN],
63 self.write_to_bytes(&mut b[i]);
68 impl FixedSizeEncoding for u32 {
69 fixed_size_encoding_byte_len_and_defaults!(4);
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)
77 fn write_to_bytes(self, b: &mut [u8]) {
78 b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
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);
88 fn from_bytes(b: &[u8]) -> Self {
89 Some(Lazy::from_position(NonZeroUsize::new(u32::from_bytes(b) as usize)?))
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();
96 position.write_to_bytes(b)
100 impl<T: Encodable> FixedSizeEncoding for Option<Lazy<[T]>> {
101 fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN * 2);
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,
110 fn write_to_bytes(self, b: &mut [u8]) {
111 self.map(|lazy| Lazy::<T>::from_position(lazy.position))
114 let len = self.map_or(0, |lazy| lazy.meta);
115 let len: u32 = len.try_into().unwrap();
117 len.write_to_bytes(&mut b[u32::BYTE_LEN..]);
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).
133 _marker: PhantomData<T>,
136 impl<T> Default for Table<T> where Option<T>: FixedSizeEncoding {
137 fn default() -> Self {
140 _marker: PhantomData,
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);
157 Some(value).write_to_bytes_at(&mut self.bytes, i);
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(),
170 impl<T> LazyMeta for Table<T> where Option<T>: FixedSizeEncoding {
173 fn min_size(len: usize) -> usize {
178 impl<T> Lazy<Table<T>> where Option<T>: FixedSizeEncoding {
179 /// Given the metadata, extract out the value at a particular index (if any).
181 crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
186 debug!("Table::lookup: index={:?} len={:?}", i, self.meta);
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)?
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;
199 impl<T> Default for PerDefTable<T> where Option<T>: FixedSizeEncoding {
200 fn default() -> Self {
201 PerDefTable(Table::default())
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);
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)
217 impl<T> LazyMeta for PerDefTable<T> where Option<T>: FixedSizeEncoding {
218 type Meta = <Table<T> as LazyMeta>::Meta;
220 fn min_size(meta: Self::Meta) -> usize {
221 Table::<T>::min_size(meta)
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)
230 /// Given the metadata, extract out the value at a particular DefIndex (if any).
232 crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
237 self.as_table().get(metadata, def_index.index())