3 use rustc_index
::vec
::Idx
;
4 use rustc_serialize
::opaque
::Encoder
;
5 use std
::convert
::TryInto
;
6 use std
::marker
::PhantomData
;
7 use std
::num
::NonZeroUsize
;
10 /// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
11 /// Used mainly for Lazy positions and lengths.
12 /// Unchecked invariant: `Self::default()` should encode as `[0; BYTE_LEN]`,
13 /// but this has no impact on safety.
14 pub(super) trait FixedSizeEncoding
: Default
{
15 const BYTE_LEN
: usize;
17 // FIXME(eddyb) convert to and from `[u8; Self::BYTE_LEN]` instead,
18 // once that starts being allowed by the compiler (i.e. lazy normalization).
19 fn from_bytes(b
: &[u8]) -> Self;
20 fn write_to_bytes(self, b
: &mut [u8]);
22 // FIXME(eddyb) make these generic functions, or at least defaults here.
23 // (same problem as above, needs `[u8; Self::BYTE_LEN]`)
24 // For now, a macro (`fixed_size_encoding_byte_len_and_defaults`) is used.
26 /// Read a `Self` value (encoded as `Self::BYTE_LEN` bytes),
27 /// from `&b[i * Self::BYTE_LEN..]`, returning `None` if `i`
28 /// is not in bounds, or `Some(Self::from_bytes(...))` otherwise.
29 fn maybe_read_from_bytes_at(b
: &[u8], i
: usize) -> Option
<Self>;
30 /// Write a `Self` value (encoded as `Self::BYTE_LEN` bytes),
31 /// at `&mut b[i * Self::BYTE_LEN..]`, using `Self::write_to_bytes`.
32 fn write_to_bytes_at(self, b
: &mut [u8], i
: usize);
35 // HACK(eddyb) this shouldn't be needed (see comments on the methods above).
36 macro_rules
! fixed_size_encoding_byte_len_and_defaults
{
38 const BYTE_LEN
: usize = $byte_len
;
39 fn maybe_read_from_bytes_at(b
: &[u8], i
: usize) -> Option
<Self> {
40 const BYTE_LEN
: usize = $byte_len
;
41 // HACK(eddyb) ideally this would be done with fully safe code,
42 // but slicing `[u8]` with `i * N..` is optimized worse, due to the
43 // possibility of `i * N` overflowing, than indexing `[[u8; N]]`.
45 std
::slice
::from_raw_parts(b
.as_ptr() as *const [u8; BYTE_LEN
], b
.len() / BYTE_LEN
)
47 b
.get(i
).map(|b
| FixedSizeEncoding
::from_bytes(b
))
49 fn write_to_bytes_at(self, b
: &mut [u8], i
: usize) {
50 const BYTE_LEN
: usize = $byte_len
;
51 // HACK(eddyb) ideally this would be done with fully safe code,
52 // see similar comment in `read_from_bytes_at` for why it can't yet.
54 std
::slice
::from_raw_parts_mut(
55 b
.as_mut_ptr() as *mut [u8; BYTE_LEN
],
59 self.write_to_bytes(&mut b
[i
]);
64 impl FixedSizeEncoding
for u32 {
65 fixed_size_encoding_byte_len_and_defaults
!(4);
67 fn from_bytes(b
: &[u8]) -> Self {
68 let mut bytes
= [0; Self::BYTE_LEN
];
69 bytes
.copy_from_slice(&b
[..Self::BYTE_LEN
]);
70 Self::from_le_bytes(bytes
)
73 fn write_to_bytes(self, b
: &mut [u8]) {
74 b
[..Self::BYTE_LEN
].copy_from_slice(&self.to_le_bytes());
78 // NOTE(eddyb) there could be an impl for `usize`, which would enable a more
79 // generic `Lazy<T>` impl, but in the general case we might not need / want to
80 // fit every `usize` in `u32`.
81 impl<T
> FixedSizeEncoding
for Option
<Lazy
<T
>> {
82 fixed_size_encoding_byte_len_and_defaults
!(u32::BYTE_LEN
);
84 fn from_bytes(b
: &[u8]) -> Self {
85 Some(Lazy
::from_position(NonZeroUsize
::new(u32::from_bytes(b
) as usize)?
))
88 fn write_to_bytes(self, b
: &mut [u8]) {
89 let position
= self.map_or(0, |lazy
| lazy
.position
.get());
90 let position
: u32 = position
.try_into().unwrap();
92 position
.write_to_bytes(b
)
96 impl<T
> FixedSizeEncoding
for Option
<Lazy
<[T
]>> {
97 fixed_size_encoding_byte_len_and_defaults
!(u32::BYTE_LEN
* 2);
99 fn from_bytes(b
: &[u8]) -> Self {
100 Some(Lazy
::from_position_and_meta(
101 <Option
<Lazy
<T
>>>::from_bytes(b
)?
.position
,
102 u32::from_bytes(&b
[u32::BYTE_LEN
..]) as usize,
106 fn write_to_bytes(self, b
: &mut [u8]) {
107 self.map(|lazy
| Lazy
::<T
>::from_position(lazy
.position
)).write_to_bytes(b
);
109 let len
= self.map_or(0, |lazy
| lazy
.meta
);
110 let len
: u32 = len
.try_into().unwrap();
112 len
.write_to_bytes(&mut b
[u32::BYTE_LEN
..]);
116 /// Random-access table (i.e. offering constant-time `get`/`set`), similar to
117 /// `Vec<Option<T>>`, but without requiring encoding or decoding all the values
118 /// eagerly and in-order.
119 /// A total of `(max_idx + 1) * <Option<T> as FixedSizeEncoding>::BYTE_LEN` bytes
120 /// are used for a table, where `max_idx` is the largest index passed to
121 /// `TableBuilder::set`.
122 pub(super) struct Table
<I
: Idx
, T
>
124 Option
<T
>: FixedSizeEncoding
,
126 _marker
: PhantomData
<(fn(&I
), T
)>,
127 // NOTE(eddyb) this makes `Table` not implement `Sized`, but no
128 // value of `Table` is ever created (it's always behind `Lazy`).
132 /// Helper for constructing a table's serialization (also see `Table`).
133 pub(super) struct TableBuilder
<I
: Idx
, T
>
135 Option
<T
>: FixedSizeEncoding
,
137 // FIXME(eddyb) use `IndexVec<I, [u8; <Option<T>>::BYTE_LEN]>` instead of
138 // `Vec<u8>`, once that starts working (i.e. lazy normalization).
139 // Then again, that has the downside of not allowing `TableBuilder::encode` to
140 // obtain a `&[u8]` entirely in safe code, for writing the bytes out.
142 _marker
: PhantomData
<(fn(&I
), T
)>,
145 impl<I
: Idx
, T
> Default
for TableBuilder
<I
, T
>
147 Option
<T
>: FixedSizeEncoding
,
149 fn default() -> Self {
150 TableBuilder { bytes: vec![], _marker: PhantomData }
154 impl<I
: Idx
, T
> TableBuilder
<I
, T
>
156 Option
<T
>: FixedSizeEncoding
,
158 pub(crate) fn set(&mut self, i
: I
, value
: T
) {
159 // FIXME(eddyb) investigate more compact encodings for sparse tables.
160 // On the PR @michaelwoerister mentioned:
161 // > Space requirements could perhaps be optimized by using the HAMT `popcnt`
162 // > trick (i.e. divide things into buckets of 32 or 64 items and then
163 // > store bit-masks of which item in each bucket is actually serialized).
165 let needed
= (i
+ 1) * <Option
<T
>>::BYTE_LEN
;
166 if self.bytes
.len() < needed
{
167 self.bytes
.resize(needed
, 0);
170 Some(value
).write_to_bytes_at(&mut self.bytes
, i
);
173 pub(crate) fn encode(&self, buf
: &mut Encoder
) -> Lazy
<Table
<I
, T
>> {
174 let pos
= buf
.position();
175 buf
.emit_raw_bytes(&self.bytes
);
176 Lazy
::from_position_and_meta(NonZeroUsize
::new(pos
as usize).unwrap(), self.bytes
.len())
180 impl<I
: Idx
, T
> LazyMeta
for Table
<I
, T
>
182 Option
<T
>: FixedSizeEncoding
,
186 fn min_size(len
: usize) -> usize {
191 impl<I
: Idx
, T
> Lazy
<Table
<I
, T
>>
193 Option
<T
>: FixedSizeEncoding
,
195 /// Given the metadata, extract out the value at a particular index (if any).
197 pub(super) fn get
<'a
, 'tcx
, M
: Metadata
<'a
, 'tcx
>>(&self, metadata
: M
, i
: I
) -> Option
<T
> {
198 debug
!("Table::lookup: index={:?} len={:?}", i
, self.meta
);
200 let start
= self.position
.get();
201 let bytes
= &metadata
.raw_bytes()[start
..start
+ self.meta
];
202 <Option
<T
>>::maybe_read_from_bytes_at(bytes
, i
.index())?
205 /// Size of the table in entries, including possible gaps.
206 pub(super) fn size(&self) -> usize {
207 self.meta
/ <Option
<T
>>::BYTE_LEN