]>
Commit | Line | Data |
---|---|---|
e74abb32 XL |
1 | use crate::decoder::Metadata; |
2 | use crate::schema::*; | |
3 | ||
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; | |
9 | use log::debug; | |
10 | ||
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; | |
17 | ||
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]); | |
22 | ||
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. | |
26 | ||
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); | |
34 | } | |
35 | ||
36 | // HACK(eddyb) this shouldn't be needed (see comments on the methods above). | |
37 | macro_rules! fixed_size_encoding_byte_len_and_defaults { | |
38 | ($byte_len:expr) => { | |
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]]`. | |
45 | let b = unsafe { | |
46 | std::slice::from_raw_parts( | |
47 | b.as_ptr() as *const [u8; BYTE_LEN], | |
48 | b.len() / BYTE_LEN, | |
49 | ) | |
50 | }; | |
51 | b.get(i).map(|b| FixedSizeEncoding::from_bytes(b)) | |
52 | } | |
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. | |
57 | let b = unsafe { | |
58 | std::slice::from_raw_parts_mut( | |
59 | b.as_mut_ptr() as *mut [u8; BYTE_LEN], | |
60 | b.len() / BYTE_LEN, | |
61 | ) | |
62 | }; | |
63 | self.write_to_bytes(&mut b[i]); | |
64 | } | |
65 | } | |
66 | } | |
67 | ||
68 | impl FixedSizeEncoding for u32 { | |
69 | fixed_size_encoding_byte_len_and_defaults!(4); | |
70 | ||
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) | |
75 | } | |
76 | ||
77 | fn write_to_bytes(self, b: &mut [u8]) { | |
78 | b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes()); | |
79 | } | |
80 | } | |
81 | ||
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); | |
87 | ||
88 | fn from_bytes(b: &[u8]) -> Self { | |
89 | Some(Lazy::from_position(NonZeroUsize::new(u32::from_bytes(b) as usize)?)) | |
90 | } | |
91 | ||
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(); | |
95 | ||
96 | position.write_to_bytes(b) | |
97 | } | |
98 | } | |
99 | ||
100 | impl<T: Encodable> FixedSizeEncoding for Option<Lazy<[T]>> { | |
101 | fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN * 2); | |
102 | ||
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, | |
107 | )) | |
108 | } | |
109 | ||
110 | fn write_to_bytes(self, b: &mut [u8]) { | |
111 | self.map(|lazy| Lazy::<T>::from_position(lazy.position)) | |
112 | .write_to_bytes(b); | |
113 | ||
114 | let len = self.map_or(0, |lazy| lazy.meta); | |
115 | let len: u32 = len.try_into().unwrap(); | |
116 | ||
117 | len.write_to_bytes(&mut b[u32::BYTE_LEN..]); | |
118 | } | |
119 | } | |
120 | ||
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). | |
132 | bytes: Vec<u8>, | |
133 | _marker: PhantomData<T>, | |
134 | } | |
135 | ||
136 | impl<T> Default for Table<T> where Option<T>: FixedSizeEncoding { | |
137 | fn default() -> Self { | |
138 | Table { | |
139 | bytes: vec![], | |
140 | _marker: PhantomData, | |
141 | } | |
142 | } | |
143 | } | |
144 | ||
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); | |
155 | } | |
156 | ||
157 | Some(value).write_to_bytes_at(&mut self.bytes, i); | |
158 | } | |
159 | ||
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(), | |
165 | self.bytes.len(), | |
166 | ) | |
167 | } | |
168 | } | |
169 | ||
170 | impl<T> LazyMeta for Table<T> where Option<T>: FixedSizeEncoding { | |
171 | type Meta = usize; | |
172 | ||
173 | fn min_size(len: usize) -> usize { | |
174 | len | |
175 | } | |
176 | } | |
177 | ||
178 | impl<T> Lazy<Table<T>> where Option<T>: FixedSizeEncoding { | |
179 | /// Given the metadata, extract out the value at a particular index (if any). | |
180 | #[inline(never)] | |
181 | crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>( | |
182 | &self, | |
183 | metadata: M, | |
184 | i: usize, | |
185 | ) -> Option<T> { | |
186 | debug!("Table::lookup: index={:?} len={:?}", i, self.meta); | |
187 | ||
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)? | |
191 | } | |
192 | } | |
193 | ||
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; | |
198 | ||
199 | impl<T> Default for PerDefTable<T> where Option<T>: FixedSizeEncoding { | |
200 | fn default() -> Self { | |
201 | PerDefTable(Table::default()) | |
202 | } | |
203 | } | |
204 | ||
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); | |
209 | } | |
210 | ||
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) | |
214 | } | |
215 | } | |
216 | ||
217 | impl<T> LazyMeta for PerDefTable<T> where Option<T>: FixedSizeEncoding { | |
218 | type Meta = <Table<T> as LazyMeta>::Meta; | |
219 | ||
220 | fn min_size(meta: Self::Meta) -> usize { | |
221 | Table::<T>::min_size(meta) | |
222 | } | |
223 | } | |
224 | ||
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) | |
228 | } | |
229 | ||
230 | /// Given the metadata, extract out the value at a particular DefIndex (if any). | |
231 | #[inline(never)] | |
232 | crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>( | |
233 | &self, | |
234 | metadata: M, | |
235 | def_index: DefIndex, | |
236 | ) -> Option<T> { | |
237 | self.as_table().get(metadata, def_index.index()) | |
238 | } | |
239 | } |