diff options
| -rw-r--r-- | src/librustc_metadata/decoder.rs | 47 | ||||
| -rw-r--r-- | src/librustc_metadata/encoder.rs | 73 | ||||
| -rw-r--r-- | src/librustc_metadata/schema.rs | 54 |
3 files changed, 148 insertions, 26 deletions
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs index 7a4d3ed657a..973ef6030a3 100644 --- a/src/librustc_metadata/decoder.rs +++ b/src/librustc_metadata/decoder.rs @@ -52,8 +52,11 @@ pub struct DecodeContext<'a, 'tcx: 'a> { cdata: Option<&'a CrateMetadata>, from_id_range: IdRange, to_id_range: IdRange, + // Cache the last used filemap for translating spans as an optimization. last_filemap_index: usize, + + lazy_state: LazyState } /// Abstract over the various ways one can create metadata decoders. @@ -73,7 +76,8 @@ pub trait Metadata<'a, 'tcx>: Copy { tcx: self.tcx(), from_id_range: id_range, to_id_range: id_range, - last_filemap_index: 0 + last_filemap_index: 0, + lazy_state: LazyState::NoNode } } } @@ -114,13 +118,16 @@ impl<'a, 'tcx> Metadata<'a, 'tcx> for (&'a CrateMetadata, TyCtxt<'a, 'tcx, 'tcx> impl<'a, 'tcx: 'a, T: Decodable> Lazy<T> { pub fn decode<M: Metadata<'a, 'tcx>>(self, meta: M) -> T { - T::decode(&mut meta.decoder(self.position)).unwrap() + let mut dcx = meta.decoder(self.position); + dcx.lazy_state = LazyState::NodeStart(self.position); + T::decode(&mut dcx).unwrap() } } impl<'a, 'tcx: 'a, T: Decodable> LazySeq<T> { pub fn decode<M: Metadata<'a, 'tcx>>(self, meta: M) -> impl Iterator<Item=T> + 'a { let mut dcx = meta.decoder(self.position); + dcx.lazy_state = LazyState::NodeStart(self.position); (0..self.len).map(move |_| { T::decode(&mut dcx).unwrap() }) @@ -137,12 +144,33 @@ impl<'a, 'tcx> DecodeContext<'a, 'tcx> { } fn with_position<F: FnOnce(&mut Self) -> R, R>(&mut self, pos: usize, f: F) -> R { - let new = opaque::Decoder::new(self.opaque.data, pos); - let old = mem::replace(&mut self.opaque, new); + let new_opaque = opaque::Decoder::new(self.opaque.data, pos); + let old_opaque = mem::replace(&mut self.opaque, new_opaque); + let old_state = mem::replace(&mut self.lazy_state, LazyState::NoNode); let r = f(self); - self.opaque = old; + self.opaque = old_opaque; + self.lazy_state = old_state; r } + + fn read_lazy_distance(&mut self, min_size: usize) + -> Result<usize, <Self as Decoder>::Error> { + let distance = self.read_usize()?; + let position = match self.lazy_state { + LazyState::NoNode => { + bug!("read_lazy_distance: outside of a metadata node") + } + LazyState::NodeStart(start) => { + assert!(distance + min_size <= start); + start - distance - min_size + } + LazyState::Previous(last_min_end) => { + last_min_end + distance + } + }; + self.lazy_state = LazyState::Previous(position + min_size); + Ok(position) + } } macro_rules! decoder_methods { @@ -185,14 +213,19 @@ impl<'doc, 'tcx> Decoder for DecodeContext<'doc, 'tcx> { impl<'a, 'tcx, T> SpecializedDecoder<Lazy<T>> for DecodeContext<'a, 'tcx> { fn specialized_decode(&mut self) -> Result<Lazy<T>, Self::Error> { - Ok(Lazy::with_position(self.read_usize()?)) + Ok(Lazy::with_position(self.read_lazy_distance(Lazy::<T>::min_size())?)) } } impl<'a, 'tcx, T> SpecializedDecoder<LazySeq<T>> for DecodeContext<'a, 'tcx> { fn specialized_decode(&mut self) -> Result<LazySeq<T>, Self::Error> { let len = self.read_usize()?; - Ok(LazySeq::with_position_and_length(self.read_usize()?, len)) + let position = if len == 0 { + 0 + } else { + self.read_lazy_distance(LazySeq::<T>::min_size(len))? + }; + Ok(LazySeq::with_position_and_length(position, len)) } } diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs index 185aa9e3b92..0f067270b80 100644 --- a/src/librustc_metadata/encoder.rs +++ b/src/librustc_metadata/encoder.rs @@ -53,6 +53,7 @@ pub struct EncodeContext<'a, 'tcx: 'a> { reachable: &'a NodeSet, mir_map: &'a MirMap<'tcx>, + lazy_state: LazyState, type_shorthands: FnvHashMap<Ty<'tcx>, usize>, predicate_shorthands: FnvHashMap<ty::Predicate<'tcx>, usize>, } @@ -95,14 +96,17 @@ impl<'a, 'tcx> Encoder for EncodeContext<'a, 'tcx> { impl<'a, 'tcx, T> SpecializedEncoder<Lazy<T>> for EncodeContext<'a, 'tcx> { fn specialized_encode(&mut self, lazy: &Lazy<T>) -> Result<(), Self::Error> { - self.emit_usize(lazy.position) + self.emit_lazy_distance(lazy.position, Lazy::<T>::min_size()) } } impl<'a, 'tcx, T> SpecializedEncoder<LazySeq<T>> for EncodeContext<'a, 'tcx> { fn specialized_encode(&mut self, seq: &LazySeq<T>) -> Result<(), Self::Error> { self.emit_usize(seq.len)?; - self.emit_usize(seq.position) + if seq.len == 0 { + return Ok(()); + } + self.emit_lazy_distance(seq.position, LazySeq::<T>::min_size(seq.len)) } } @@ -129,24 +133,62 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { self.opaque.position() } - pub fn lazy<T: Encodable>(&mut self, value: &T) -> Lazy<T> { + fn emit_node<F: FnOnce(&mut Self, usize) -> R, R>(&mut self, f: F) -> R { + assert_eq!(self.lazy_state, LazyState::NoNode); let pos = self.position(); - value.encode(self).unwrap(); - Lazy::with_position(pos) + self.lazy_state = LazyState::NodeStart(pos); + let r = f(self, pos); + self.lazy_state = LazyState::NoNode; + r + } + + fn emit_lazy_distance(&mut self, position: usize, min_size: usize) + -> Result<(), <Self as Encoder>::Error> { + let min_end = position + min_size; + let distance = match self.lazy_state { + LazyState::NoNode => { + bug!("emit_lazy_distance: outside of a metadata node") + } + LazyState::NodeStart(start) => { + assert!(min_end <= start); + start - min_end + } + LazyState::Previous(last_min_end) => { + assert!(last_min_end <= position); + position - last_min_end + } + }; + self.lazy_state = LazyState::Previous(min_end); + self.emit_usize(distance) + } + + pub fn lazy<T: Encodable>(&mut self, value: &T) -> Lazy<T> { + self.emit_node(|ecx, pos| { + value.encode(ecx).unwrap(); + + assert!(pos + Lazy::<T>::min_size() <= ecx.position()); + Lazy::with_position(pos) + }) } fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T> where I: IntoIterator<Item=T>, T: Encodable { - let pos = self.position(); - let len = iter.into_iter().map(|value| value.encode(self).unwrap()).count(); - LazySeq::with_position_and_length(pos, len) + self.emit_node(|ecx, pos| { + let len = iter.into_iter().map(|value| value.encode(ecx).unwrap()).count(); + + assert!(pos + LazySeq::<T>::min_size(len) <= ecx.position()); + LazySeq::with_position_and_length(pos, len) + }) } fn lazy_seq_ref<'b, I, T>(&mut self, iter: I) -> LazySeq<T> where I: IntoIterator<Item=&'b T>, T: 'b + Encodable { - let pos = self.position(); - let len = iter.into_iter().map(|value| value.encode(self).unwrap()).count(); - LazySeq::with_position_and_length(pos, len) + self.emit_node(|ecx, pos| { + let len = iter.into_iter().map(|value| value.encode(ecx).unwrap()).count(); + + assert!(pos + LazySeq::<T>::min_size(len) <= ecx.position()); + LazySeq::with_position_and_length(pos, len) + }) } /// Encode the given value or a previously cached shorthand. @@ -1262,16 +1304,16 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> { None }, - index: index, crate_deps: crate_deps, dylib_dependency_formats: dylib_dependency_formats, - native_libraries: native_libraries, lang_items: lang_items, lang_items_missing: lang_items_missing, + native_libraries: native_libraries, + codemap: codemap, + macro_defs: macro_defs, impls: impls, reachable_ids: reachable_ids, - macro_defs: macro_defs, - codemap: codemap + index: index, }); let total_bytes = self.position(); @@ -1345,6 +1387,7 @@ pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, cstore: cstore, reachable: reachable, mir_map: mir_map, + lazy_state: LazyState::NoNode, type_shorthands: Default::default(), predicate_shorthands: Default::default() }.encode_crate_root(); diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs index b4ea2b19bf0..956577ed8fb 100644 --- a/src/librustc_metadata/schema.rs +++ b/src/librustc_metadata/schema.rs @@ -52,6 +52,19 @@ pub const SHORTHAND_OFFSET: usize = 0x80; /// A value of type T referred to by its absolute position /// in the metadata, and which can be decoded lazily. +/// +/// Metadata is effective a tree, encoded in post-order, +/// and with the root's position written next to the header. +/// That means every single `Lazy` points to some previous +/// location in the metadata and is part of a larger node. +/// +/// The first `Lazy` in a node is encoded as the backwards +/// distance from the position where the containing node +/// starts and where the `Lazy` points to, while the rest +/// use the forward distance from the previous `Lazy`. +/// Distances start at 1, as 0-byte nodes are invalid. +/// Also invalid are nodes being referred in a different +/// order than they were encoded in. #[must_use] pub struct Lazy<T> { pub position: usize, @@ -65,6 +78,12 @@ impl<T> Lazy<T> { _marker: PhantomData } } + + /// Returns the minimum encoded size of a value of type `T`. + // FIXME(eddyb) Give better estimates for certain types. + pub fn min_size() -> usize { + 1 + } } impl<T> Copy for Lazy<T> {} @@ -77,10 +96,16 @@ impl<T> serialize::UseSpecializedDecodable for Lazy<T> {} /// A sequence of type T referred to by its absolute position /// in the metadata and length, and which can be decoded lazily. +/// The sequence is a single node for the purposes of `Lazy`. /// /// Unlike `Lazy<Vec<T>>`, the length is encoded next to the /// position, not at the position, which means that the length /// doesn't need to be known before encoding all the elements. +/// +/// If the length is 0, no position is encoded, but otherwise, +/// the encoding is that of `Lazy`, with the distinction that +/// the minimal distance the length of the sequence, i.e. +/// it's assumed there's no 0-byte element in the sequence. #[must_use] pub struct LazySeq<T> { pub len: usize, @@ -100,6 +125,11 @@ impl<T> LazySeq<T> { _marker: PhantomData } } + + /// Returns the minimum encoded size of `length` values of type `T`. + pub fn min_size(length: usize) -> usize { + length + } } impl<T> Copy for LazySeq<T> {} @@ -110,6 +140,22 @@ impl<T> Clone for LazySeq<T> { impl<T> serialize::UseSpecializedEncodable for LazySeq<T> {} impl<T> serialize::UseSpecializedDecodable for LazySeq<T> {} +/// Encoding / decoding state for `Lazy` and `LazySeq`. +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +pub enum LazyState { + /// Outside of a metadata node. + NoNode, + + /// Inside a metadata node, and before any `Lazy` or `LazySeq`. + /// The position is that of the node itself. + NodeStart(usize), + + /// Inside a metadata node, with a previous `Lazy` or `LazySeq`. + /// The position is a conservative estimate of where that + /// previous `Lazy` / `LazySeq` would end (see their comments). + Previous(usize) +} + #[derive(RustcEncodable, RustcDecodable)] pub struct CrateRoot { pub rustc_version: String, @@ -121,16 +167,16 @@ pub struct CrateRoot { pub plugin_registrar_fn: Option<DefIndex>, pub macro_derive_registrar: Option<DefIndex>, - pub index: LazySeq<index::Index>, pub crate_deps: LazySeq<CrateDep>, pub dylib_dependency_formats: LazySeq<Option<LinkagePreference>>, - pub native_libraries: LazySeq<(NativeLibraryKind, String)>, pub lang_items: LazySeq<(DefIndex, usize)>, pub lang_items_missing: LazySeq<lang_items::LangItem>, + pub native_libraries: LazySeq<(NativeLibraryKind, String)>, + pub codemap: LazySeq<syntax_pos::FileMap>, + pub macro_defs: LazySeq<MacroDef>, pub impls: LazySeq<TraitImpls>, pub reachable_ids: LazySeq<DefIndex>, - pub macro_defs: LazySeq<MacroDef>, - pub codemap: LazySeq<syntax_pos::FileMap> + pub index: LazySeq<index::Index>, } #[derive(RustcEncodable, RustcDecodable)] |