compiler/rustc_middle/src/ty/codec.rs

   1 // This module contains some shared code for encoding and decoding various
   2 // things from the `ty` module, and in particular implements support for
   3 // "shorthands" which allow to have pointers back into the already encoded
   4 // stream instead of re-encoding the same thing twice.
   5 //
   6 // The functionality in here is shared between persisting to crate metadata and
   7 // persisting to incr. comp. caches.
   8
   9 use crate::arena::ArenaAllocatable;
  10 use crate::infer::canonical::{CanonicalVarInfo, CanonicalVarInfos};
  11 use crate::mir::{
  12     self,
  13     interpret::{AllocId, Allocation},
  14 };
  15 use crate::ty::subst::SubstsRef;
  16 use crate::ty::{self, List, Ty, TyCtxt};
  17 use rustc_data_structures::fx::FxHashMap;
  18 use rustc_hir::def_id::DefId;
  19 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
  20 use rustc_span::Span;
  21 use std::hash::Hash;
  22 use std::intrinsics;
  23 use std::marker::DiscriminantKind;
  24
  25 /// The shorthand encoding uses an enum's variant index `usize`
  26 /// and is offset by this value so it never matches a real variant.
  27 /// This offset is also chosen so that the first byte is never < 0x80.
  28 pub const SHORTHAND_OFFSET: usize = 0x80;
  29
  30 pub trait EncodableWithShorthand<'tcx, E: TyEncoder<'tcx>>: Copy + Eq + Hash {
  31     type Variant: Encodable<E>;
  32     fn variant(&self) -> &Self::Variant;
  33 }
  34
  35 #[allow(rustc::usage_of_ty_tykind)]
  36 impl<'tcx, E: TyEncoder<'tcx>> EncodableWithShorthand<'tcx, E> for Ty<'tcx> {
  37     type Variant = ty::TyKind<'tcx>;
  38
  39     #[inline]
  40     fn variant(&self) -> &Self::Variant {
  41         self.kind()
  42     }
  43 }
  44
  45 impl<'tcx, E: TyEncoder<'tcx>> EncodableWithShorthand<'tcx, E> for ty::PredicateKind<'tcx> {
  46     type Variant = ty::PredicateKind<'tcx>;
  47
  48     #[inline]
  49     fn variant(&self) -> &Self::Variant {
  50         self
  51     }
  52 }
  53
  54 pub trait TyEncoder<'tcx>: Encoder {
  55     const CLEAR_CROSS_CRATE: bool;
  56
  57     fn position(&self) -> usize;
  58     fn type_shorthands(&mut self) -> &mut FxHashMap<Ty<'tcx>, usize>;
  59     fn predicate_shorthands(&mut self) -> &mut FxHashMap<ty::PredicateKind<'tcx>, usize>;
  60     fn encode_alloc_id(&mut self, alloc_id: &AllocId) -> Result<(), Self::Error>;
  61 }
  62
  63 /// Trait for decoding to a reference.
  64 ///
  65 /// This is a separate trait from `Decodable` so that we can implement it for
  66 /// upstream types, such as `FxHashSet`.
  67 ///
  68 /// The `TyDecodable` derive macro will use this trait for fields that are
  69 /// references (and don't use a type alias to hide that).
  70 ///
  71 /// `Decodable` can still be implemented in cases where `Decodable` is required
  72 /// by a trait bound.
  73 pub trait RefDecodable<'tcx, D: TyDecoder<'tcx>> {
  74     fn decode(d: &mut D) -> Result<&'tcx Self, D::Error>;
  75 }
  76
  77 /// Encode the given value or a previously cached shorthand.
  78 pub fn encode_with_shorthand<E, T, M>(encoder: &mut E, value: &T, cache: M) -> Result<(), E::Error>
  79 where
  80     E: TyEncoder<'tcx>,
  81     M: for<'b> Fn(&'b mut E) -> &'b mut FxHashMap<T, usize>,
  82     T: EncodableWithShorthand<'tcx, E>,
  83     // The discriminant and shorthand must have the same size.
  84     T::Variant: DiscriminantKind<Discriminant = isize>,
  85 {
  86     let existing_shorthand = cache(encoder).get(value).copied();
  87     if let Some(shorthand) = existing_shorthand {
  88         return encoder.emit_usize(shorthand);
  89     }
  90
  91     let variant = value.variant();
  92
  93     let start = encoder.position();
  94     variant.encode(encoder)?;
  95     let len = encoder.position() - start;
  96
  97     // The shorthand encoding uses the same usize as the
  98     // discriminant, with an offset so they can't conflict.
  99     let discriminant = intrinsics::discriminant_value(variant);
 100     assert!(SHORTHAND_OFFSET > discriminant as usize);
 101
 102     let shorthand = start + SHORTHAND_OFFSET;
 103
 104     // Get the number of bits that leb128 could fit
 105     // in the same space as the fully encoded type.
 106     let leb128_bits = len * 7;
 107
 108     // Check that the shorthand is a not longer than the
 109     // full encoding itself, i.e., it's an obvious win.
 110     if leb128_bits >= 64 || (shorthand as u64) < (1 << leb128_bits) {
 111         cache(encoder).insert(*value, shorthand);
 112     }
 113
 114     Ok(())
 115 }
 116
 117 impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for Ty<'tcx> {
 118     fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 119         encode_with_shorthand(e, self, TyEncoder::type_shorthands)
 120     }
 121 }
 122
 123 impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for ty::Binder<'tcx, ty::PredicateKind<'tcx>> {
 124     fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 125         self.bound_vars().encode(e)?;
 126         encode_with_shorthand(e, &self.skip_binder(), TyEncoder::predicate_shorthands)
 127     }
 128 }
 129
 130 impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for ty::Predicate<'tcx> {
 131     fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 132         self.kind().encode(e)
 133     }
 134 }
 135
 136 impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for AllocId {
 137     fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 138         e.encode_alloc_id(self)
 139     }
 140 }
 141
 142 macro_rules! encodable_via_deref {
 143     ($($t:ty),+) => {
 144         $(impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for $t {
 145             fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 146                 (**self).encode(e)
 147             }
 148         })*
 149     }
 150 }
 151
 152 encodable_via_deref! {
 153     &'tcx ty::TypeckResults<'tcx>,
 154     ty::Region<'tcx>,
 155     &'tcx mir::Body<'tcx>,
 156     &'tcx mir::UnsafetyCheckResult,
 157     &'tcx mir::BorrowCheckResult<'tcx>,
 158     &'tcx mir::coverage::CodeRegion
 159 }
 160
 161 pub trait TyDecoder<'tcx>: Decoder {
 162     const CLEAR_CROSS_CRATE: bool;
 163
 164     fn tcx(&self) -> TyCtxt<'tcx>;
 165
 166     fn peek_byte(&self) -> u8;
 167
 168     fn position(&self) -> usize;
 169
 170     fn cached_ty_for_shorthand<F>(
 171         &mut self,
 172         shorthand: usize,
 173         or_insert_with: F,
 174     ) -> Result<Ty<'tcx>, Self::Error>
 175     where
 176         F: FnOnce(&mut Self) -> Result<Ty<'tcx>, Self::Error>;
 177
 178     fn with_position<F, R>(&mut self, pos: usize, f: F) -> R
 179     where
 180         F: FnOnce(&mut Self) -> R;
 181
 182     fn positioned_at_shorthand(&self) -> bool {
 183         (self.peek_byte() & (SHORTHAND_OFFSET as u8)) != 0
 184     }
 185
 186     fn decode_alloc_id(&mut self) -> Result<AllocId, Self::Error>;
 187 }
 188
 189 #[inline]
 190 fn decode_arena_allocable<'tcx, D, T: ArenaAllocatable<'tcx> + Decodable<D>>(
 191     decoder: &mut D,
 192 ) -> Result<&'tcx T, D::Error>
 193 where
 194     D: TyDecoder<'tcx>,
 195 {
 196     Ok(decoder.tcx().arena.alloc(Decodable::decode(decoder)?))
 197 }
 198
 199 #[inline]
 200 fn decode_arena_allocable_slice<'tcx, D, T: ArenaAllocatable<'tcx> + Decodable<D>>(
 201     decoder: &mut D,
 202 ) -> Result<&'tcx [T], D::Error>
 203 where
 204     D: TyDecoder<'tcx>,
 205 {
 206     Ok(decoder.tcx().arena.alloc_from_iter(<Vec<T> as Decodable<D>>::decode(decoder)?))
 207 }
 208
 209 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for Ty<'tcx> {
 210     #[allow(rustc::usage_of_ty_tykind)]
 211     fn decode(decoder: &mut D) -> Result<Ty<'tcx>, D::Error> {
 212         // Handle shorthands first, if we have an usize > 0x80.
 213         if decoder.positioned_at_shorthand() {
 214             let pos = decoder.read_usize()?;
 215             assert!(pos >= SHORTHAND_OFFSET);
 216             let shorthand = pos - SHORTHAND_OFFSET;
 217
 218             decoder.cached_ty_for_shorthand(shorthand, |decoder| {
 219                 decoder.with_position(shorthand, Ty::decode)
 220             })
 221         } else {
 222             let tcx = decoder.tcx();
 223             Ok(tcx.mk_ty(ty::TyKind::decode(decoder)?))
 224         }
 225     }
 226 }
 227
 228 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Binder<'tcx, ty::PredicateKind<'tcx>> {
 229     fn decode(decoder: &mut D) -> Result<ty::Binder<'tcx, ty::PredicateKind<'tcx>>, D::Error> {
 230         let bound_vars = Decodable::decode(decoder)?;
 231         // Handle shorthands first, if we have an usize > 0x80.
 232         Ok(ty::Binder::bind_with_vars(
 233             if decoder.positioned_at_shorthand() {
 234                 let pos = decoder.read_usize()?;
 235                 assert!(pos >= SHORTHAND_OFFSET);
 236                 let shorthand = pos - SHORTHAND_OFFSET;
 237
 238                 decoder.with_position(shorthand, ty::PredicateKind::decode)?
 239             } else {
 240                 ty::PredicateKind::decode(decoder)?
 241             },
 242             bound_vars,
 243         ))
 244     }
 245 }
 246
 247 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Predicate<'tcx> {
 248     fn decode(decoder: &mut D) -> Result<ty::Predicate<'tcx>, D::Error> {
 249         let predicate_kind = Decodable::decode(decoder)?;
 250         let predicate = decoder.tcx().mk_predicate(predicate_kind);
 251         Ok(predicate)
 252     }
 253 }
 254
 255 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for SubstsRef<'tcx> {
 256     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 257         let len = decoder.read_usize()?;
 258         let tcx = decoder.tcx();
 259         tcx.mk_substs((0..len).map(|_| Decodable::decode(decoder)))
 260     }
 261 }
 262
 263 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for mir::Place<'tcx> {
 264     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 265         let local: mir::Local = Decodable::decode(decoder)?;
 266         let len = decoder.read_usize()?;
 267         let projection: &'tcx List<mir::PlaceElem<'tcx>> =
 268             decoder.tcx().mk_place_elems((0..len).map(|_| Decodable::decode(decoder)))?;
 269         Ok(mir::Place { local, projection })
 270     }
 271 }
 272
 273 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Region<'tcx> {
 274     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 275         Ok(decoder.tcx().mk_region(Decodable::decode(decoder)?))
 276     }
 277 }
 278
 279 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for CanonicalVarInfos<'tcx> {
 280     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 281         let len = decoder.read_usize()?;
 282         let interned: Result<Vec<CanonicalVarInfo<'tcx>>, _> =
 283             (0..len).map(|_| Decodable::decode(decoder)).collect();
 284         Ok(decoder.tcx().intern_canonical_var_infos(interned?.as_slice()))
 285     }
 286 }
 287
 288 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for AllocId {
 289     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 290         decoder.decode_alloc_id()
 291     }
 292 }
 293
 294 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::SymbolName<'tcx> {
 295     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 296         Ok(ty::SymbolName::new(decoder.tcx(), &decoder.read_str()?))
 297     }
 298 }
 299
 300 macro_rules! impl_decodable_via_ref {
 301     ($($t:ty),+) => {
 302         $(impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for $t {
 303             fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 304                 RefDecodable::decode(decoder)
 305             }
 306         })*
 307     }
 308 }
 309
 310 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::AdtDef {
 311     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 312         let def_id = <DefId as Decodable<D>>::decode(decoder)?;
 313         Ok(decoder.tcx().adt_def(def_id))
 314     }
 315 }
 316
 317 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<Ty<'tcx>> {
 318     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 319         let len = decoder.read_usize()?;
 320         decoder.tcx().mk_type_list((0..len).map(|_| Decodable::decode(decoder)))
 321     }
 322 }
 323
 324 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D>
 325     for ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>
 326 {
 327     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 328         let len = decoder.read_usize()?;
 329         decoder.tcx().mk_poly_existential_predicates((0..len).map(|_| Decodable::decode(decoder)))
 330     }
 331 }
 332
 333 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::Const<'tcx> {
 334     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 335         Ok(decoder.tcx().mk_const(Decodable::decode(decoder)?))
 336     }
 337 }
 338
 339 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [ty::ValTree<'tcx>] {
 340     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 341         Ok(decoder.tcx().arena.alloc_from_iter(
 342             (0..decoder.read_usize()?)
 343                 .map(|_| Decodable::decode(decoder))
 344                 .collect::<Result<Vec<_>, _>>()?,
 345         ))
 346     }
 347 }
 348
 349 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for Allocation {
 350     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 351         Ok(decoder.tcx().intern_const_alloc(Decodable::decode(decoder)?))
 352     }
 353 }
 354
 355 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [(ty::Predicate<'tcx>, Span)] {
 356     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 357         Ok(decoder.tcx().arena.alloc_from_iter(
 358             (0..decoder.read_usize()?)
 359                 .map(|_| Decodable::decode(decoder))
 360                 .collect::<Result<Vec<_>, _>>()?,
 361         ))
 362     }
 363 }
 364
 365 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [mir::abstract_const::Node<'tcx>] {
 366     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 367         Ok(decoder.tcx().arena.alloc_from_iter(
 368             (0..decoder.read_usize()?)
 369                 .map(|_| Decodable::decode(decoder))
 370                 .collect::<Result<Vec<_>, _>>()?,
 371         ))
 372     }
 373 }
 374
 375 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [mir::abstract_const::NodeId] {
 376     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 377         Ok(decoder.tcx().arena.alloc_from_iter(
 378             (0..decoder.read_usize()?)
 379                 .map(|_| Decodable::decode(decoder))
 380                 .collect::<Result<Vec<_>, _>>()?,
 381         ))
 382     }
 383 }
 384
 385 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<ty::BoundVariableKind> {
 386     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 387         let len = decoder.read_usize()?;
 388         Ok(decoder.tcx().mk_bound_variable_kinds((0..len).map(|_| Decodable::decode(decoder)))?)
 389     }
 390 }
 391
 392 impl_decodable_via_ref! {
 393     &'tcx ty::TypeckResults<'tcx>,
 394     &'tcx ty::List<Ty<'tcx>>,
 395     &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
 396     &'tcx Allocation,
 397     &'tcx mir::Body<'tcx>,
 398     &'tcx mir::UnsafetyCheckResult,
 399     &'tcx mir::BorrowCheckResult<'tcx>,
 400     &'tcx mir::coverage::CodeRegion,
 401     &'tcx ty::List<ty::BoundVariableKind>
 402 }
 403
 404 #[macro_export]
 405 macro_rules! __impl_decoder_methods {
 406     ($($name:ident -> $ty:ty;)*) => {
 407         $(
 408             #[inline]
 409             fn $name(&mut self) -> Result<$ty, Self::Error> {
 410                 self.opaque.$name()
 411             }
 412         )*
 413     }
 414 }
 415
 416 macro_rules! impl_arena_allocatable_decoder {
 417     ([]$args:tt) => {};
 418     ([decode $(, $attrs:ident)*]
 419      [[$name:ident: $ty:ty], $tcx:lifetime]) => {
 420         impl<$tcx, D: TyDecoder<$tcx>> RefDecodable<$tcx, D> for $ty {
 421             #[inline]
 422             fn decode(decoder: &mut D) -> Result<&$tcx Self, D::Error> {
 423                 decode_arena_allocable(decoder)
 424             }
 425         }
 426
 427         impl<$tcx, D: TyDecoder<$tcx>> RefDecodable<$tcx, D> for [$ty] {
 428             #[inline]
 429             fn decode(decoder: &mut D) -> Result<&$tcx Self, D::Error> {
 430                 decode_arena_allocable_slice(decoder)
 431             }
 432         }
 433     };
 434     ([$ignore:ident $(, $attrs:ident)*]$args:tt) => {
 435         impl_arena_allocatable_decoder!([$($attrs),*]$args);
 436     };
 437 }
 438
 439 macro_rules! impl_arena_allocatable_decoders {
 440     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
 441         $(
 442             impl_arena_allocatable_decoder!($a [[$name: $ty], $tcx]);
 443         )*
 444     }
 445 }
 446
 447 rustc_hir::arena_types!(impl_arena_allocatable_decoders, [], 'tcx);
 448 arena_types!(impl_arena_allocatable_decoders, [], 'tcx);
 449
 450 #[macro_export]
 451 macro_rules! implement_ty_decoder {
 452     ($DecoderName:ident <$($typaram:tt),*>) => {
 453         mod __ty_decoder_impl {
 454             use std::borrow::Cow;
 455             use rustc_serialize::Decoder;
 456
 457             use super::$DecoderName;
 458
 459             impl<$($typaram ),*> Decoder for $DecoderName<$($typaram),*> {
 460                 type Error = String;
 461
 462                 $crate::__impl_decoder_methods! {
 463                     read_nil -> ();
 464
 465                     read_u128 -> u128;
 466                     read_u64 -> u64;
 467                     read_u32 -> u32;
 468                     read_u16 -> u16;
 469                     read_u8 -> u8;
 470                     read_usize -> usize;
 471
 472                     read_i128 -> i128;
 473                     read_i64 -> i64;
 474                     read_i32 -> i32;
 475                     read_i16 -> i16;
 476                     read_i8 -> i8;
 477                     read_isize -> isize;
 478
 479                     read_bool -> bool;
 480                     read_f64 -> f64;
 481                     read_f32 -> f32;
 482                     read_char -> char;
 483                     read_str -> Cow<'_, str>;
 484                 }
 485
 486                 #[inline]
 487                 fn read_raw_bytes_into(&mut self, bytes: &mut [u8]) -> Result<(), Self::Error> {
 488                     self.opaque.read_raw_bytes_into(bytes)
 489                 }
 490
 491                 fn error(&mut self, err: &str) -> Self::Error {
 492                     self.opaque.error(err)
 493                 }
 494             }
 495         }
 496     }
 497 }
 498
 499 macro_rules! impl_binder_encode_decode {
 500     ($($t:ty),+ $(,)?) => {
 501         $(
 502             impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for ty::Binder<'tcx, $t> {
 503                 fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 504                     self.bound_vars().encode(e)?;
 505                     self.as_ref().skip_binder().encode(e)
 506                 }
 507             }
 508             impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Binder<'tcx, $t> {
 509                 fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 510                     let bound_vars = Decodable::decode(decoder)?;
 511                     Ok(ty::Binder::bind_with_vars(Decodable::decode(decoder)?, bound_vars))
 512                 }
 513             }
 514         )*
 515     }
 516 }
 517
 518 impl_binder_encode_decode! {
 519     &'tcx ty::List<Ty<'tcx>>,
 520     ty::FnSig<'tcx>,
 521     ty::ExistentialPredicate<'tcx>,
 522     ty::TraitRef<'tcx>,
 523     Vec<ty::GeneratorInteriorTypeCause<'tcx>>,
 524 }