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::{CrateNum, 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 map_encoded_cnum_to_current(&self, cnum: CrateNum) -> CrateNum;
 183
 184     fn positioned_at_shorthand(&self) -> bool {
 185         (self.peek_byte() & (SHORTHAND_OFFSET as u8)) != 0
 186     }
 187
 188     fn decode_alloc_id(&mut self) -> Result<AllocId, Self::Error>;
 189 }
 190
 191 #[inline]
 192 fn decode_arena_allocable<'tcx, D, T: ArenaAllocatable<'tcx> + Decodable<D>>(
 193     decoder: &mut D,
 194 ) -> Result<&'tcx T, D::Error>
 195 where
 196     D: TyDecoder<'tcx>,
 197 {
 198     Ok(decoder.tcx().arena.alloc(Decodable::decode(decoder)?))
 199 }
 200
 201 #[inline]
 202 fn decode_arena_allocable_slice<'tcx, D, T: ArenaAllocatable<'tcx> + Decodable<D>>(
 203     decoder: &mut D,
 204 ) -> Result<&'tcx [T], D::Error>
 205 where
 206     D: TyDecoder<'tcx>,
 207 {
 208     Ok(decoder.tcx().arena.alloc_from_iter(<Vec<T> as Decodable<D>>::decode(decoder)?))
 209 }
 210
 211 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for Ty<'tcx> {
 212     #[allow(rustc::usage_of_ty_tykind)]
 213     fn decode(decoder: &mut D) -> Result<Ty<'tcx>, D::Error> {
 214         // Handle shorthands first, if we have an usize > 0x80.
 215         if decoder.positioned_at_shorthand() {
 216             let pos = decoder.read_usize()?;
 217             assert!(pos >= SHORTHAND_OFFSET);
 218             let shorthand = pos - SHORTHAND_OFFSET;
 219
 220             decoder.cached_ty_for_shorthand(shorthand, |decoder| {
 221                 decoder.with_position(shorthand, Ty::decode)
 222             })
 223         } else {
 224             let tcx = decoder.tcx();
 225             Ok(tcx.mk_ty(ty::TyKind::decode(decoder)?))
 226         }
 227     }
 228 }
 229
 230 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Binder<'tcx, ty::PredicateKind<'tcx>> {
 231     fn decode(decoder: &mut D) -> Result<ty::Binder<'tcx, ty::PredicateKind<'tcx>>, D::Error> {
 232         let bound_vars = Decodable::decode(decoder)?;
 233         // Handle shorthands first, if we have an usize > 0x80.
 234         Ok(ty::Binder::bind_with_vars(
 235             if decoder.positioned_at_shorthand() {
 236                 let pos = decoder.read_usize()?;
 237                 assert!(pos >= SHORTHAND_OFFSET);
 238                 let shorthand = pos - SHORTHAND_OFFSET;
 239
 240                 decoder.with_position(shorthand, ty::PredicateKind::decode)?
 241             } else {
 242                 ty::PredicateKind::decode(decoder)?
 243             },
 244             bound_vars,
 245         ))
 246     }
 247 }
 248
 249 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Predicate<'tcx> {
 250     fn decode(decoder: &mut D) -> Result<ty::Predicate<'tcx>, D::Error> {
 251         let predicate_kind = Decodable::decode(decoder)?;
 252         let predicate = decoder.tcx().mk_predicate(predicate_kind);
 253         Ok(predicate)
 254     }
 255 }
 256
 257 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for SubstsRef<'tcx> {
 258     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 259         let len = decoder.read_usize()?;
 260         let tcx = decoder.tcx();
 261         tcx.mk_substs((0..len).map(|_| Decodable::decode(decoder)))
 262     }
 263 }
 264
 265 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for mir::Place<'tcx> {
 266     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 267         let local: mir::Local = Decodable::decode(decoder)?;
 268         let len = decoder.read_usize()?;
 269         let projection: &'tcx List<mir::PlaceElem<'tcx>> =
 270             decoder.tcx().mk_place_elems((0..len).map(|_| Decodable::decode(decoder)))?;
 271         Ok(mir::Place { local, projection })
 272     }
 273 }
 274
 275 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Region<'tcx> {
 276     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 277         Ok(decoder.tcx().mk_region(Decodable::decode(decoder)?))
 278     }
 279 }
 280
 281 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for CanonicalVarInfos<'tcx> {
 282     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 283         let len = decoder.read_usize()?;
 284         let interned: Result<Vec<CanonicalVarInfo<'tcx>>, _> =
 285             (0..len).map(|_| Decodable::decode(decoder)).collect();
 286         Ok(decoder.tcx().intern_canonical_var_infos(interned?.as_slice()))
 287     }
 288 }
 289
 290 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for AllocId {
 291     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 292         decoder.decode_alloc_id()
 293     }
 294 }
 295
 296 impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::SymbolName<'tcx> {
 297     fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 298         Ok(ty::SymbolName::new(decoder.tcx(), &decoder.read_str()?))
 299     }
 300 }
 301
 302 macro_rules! impl_decodable_via_ref {
 303     ($($t:ty),+) => {
 304         $(impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for $t {
 305             fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 306                 RefDecodable::decode(decoder)
 307             }
 308         })*
 309     }
 310 }
 311
 312 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::AdtDef {
 313     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 314         let def_id = <DefId as Decodable<D>>::decode(decoder)?;
 315         Ok(decoder.tcx().adt_def(def_id))
 316     }
 317 }
 318
 319 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<Ty<'tcx>> {
 320     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 321         let len = decoder.read_usize()?;
 322         decoder.tcx().mk_type_list((0..len).map(|_| Decodable::decode(decoder)))
 323     }
 324 }
 325
 326 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D>
 327     for ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>
 328 {
 329     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 330         let len = decoder.read_usize()?;
 331         decoder.tcx().mk_poly_existential_predicates((0..len).map(|_| Decodable::decode(decoder)))
 332     }
 333 }
 334
 335 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::Const<'tcx> {
 336     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 337         Ok(decoder.tcx().mk_const(Decodable::decode(decoder)?))
 338     }
 339 }
 340
 341 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [ty::ValTree<'tcx>] {
 342     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 343         Ok(decoder.tcx().arena.alloc_from_iter(
 344             (0..decoder.read_usize()?)
 345                 .map(|_| Decodable::decode(decoder))
 346                 .collect::<Result<Vec<_>, _>>()?,
 347         ))
 348     }
 349 }
 350
 351 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for Allocation {
 352     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 353         Ok(decoder.tcx().intern_const_alloc(Decodable::decode(decoder)?))
 354     }
 355 }
 356
 357 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [(ty::Predicate<'tcx>, Span)] {
 358     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 359         Ok(decoder.tcx().arena.alloc_from_iter(
 360             (0..decoder.read_usize()?)
 361                 .map(|_| Decodable::decode(decoder))
 362                 .collect::<Result<Vec<_>, _>>()?,
 363         ))
 364     }
 365 }
 366
 367 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [mir::abstract_const::Node<'tcx>] {
 368     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 369         Ok(decoder.tcx().arena.alloc_from_iter(
 370             (0..decoder.read_usize()?)
 371                 .map(|_| Decodable::decode(decoder))
 372                 .collect::<Result<Vec<_>, _>>()?,
 373         ))
 374     }
 375 }
 376
 377 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [mir::abstract_const::NodeId] {
 378     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 379         Ok(decoder.tcx().arena.alloc_from_iter(
 380             (0..decoder.read_usize()?)
 381                 .map(|_| Decodable::decode(decoder))
 382                 .collect::<Result<Vec<_>, _>>()?,
 383         ))
 384     }
 385 }
 386
 387 impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<ty::BoundVariableKind> {
 388     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
 389         let len = decoder.read_usize()?;
 390         Ok(decoder.tcx().mk_bound_variable_kinds((0..len).map(|_| Decodable::decode(decoder)))?)
 391     }
 392 }
 393
 394 impl_decodable_via_ref! {
 395     &'tcx ty::TypeckResults<'tcx>,
 396     &'tcx ty::List<Ty<'tcx>>,
 397     &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
 398     &'tcx Allocation,
 399     &'tcx mir::Body<'tcx>,
 400     &'tcx mir::UnsafetyCheckResult,
 401     &'tcx mir::BorrowCheckResult<'tcx>,
 402     &'tcx mir::coverage::CodeRegion,
 403     &'tcx ty::List<ty::BoundVariableKind>
 404 }
 405
 406 #[macro_export]
 407 macro_rules! __impl_decoder_methods {
 408     ($($name:ident -> $ty:ty;)*) => {
 409         $(
 410             #[inline]
 411             fn $name(&mut self) -> Result<$ty, Self::Error> {
 412                 self.opaque.$name()
 413             }
 414         )*
 415     }
 416 }
 417
 418 macro_rules! impl_arena_allocatable_decoder {
 419     ([]$args:tt) => {};
 420     ([decode $(, $attrs:ident)*]
 421      [[$name:ident: $ty:ty], $tcx:lifetime]) => {
 422         impl<$tcx, D: TyDecoder<$tcx>> RefDecodable<$tcx, D> for $ty {
 423             #[inline]
 424             fn decode(decoder: &mut D) -> Result<&$tcx Self, D::Error> {
 425                 decode_arena_allocable(decoder)
 426             }
 427         }
 428
 429         impl<$tcx, D: TyDecoder<$tcx>> RefDecodable<$tcx, D> for [$ty] {
 430             #[inline]
 431             fn decode(decoder: &mut D) -> Result<&$tcx Self, D::Error> {
 432                 decode_arena_allocable_slice(decoder)
 433             }
 434         }
 435     };
 436     ([$ignore:ident $(, $attrs:ident)*]$args:tt) => {
 437         impl_arena_allocatable_decoder!([$($attrs),*]$args);
 438     };
 439 }
 440
 441 macro_rules! impl_arena_allocatable_decoders {
 442     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
 443         $(
 444             impl_arena_allocatable_decoder!($a [[$name: $ty], $tcx]);
 445         )*
 446     }
 447 }
 448
 449 rustc_hir::arena_types!(impl_arena_allocatable_decoders, [], 'tcx);
 450 arena_types!(impl_arena_allocatable_decoders, [], 'tcx);
 451
 452 #[macro_export]
 453 macro_rules! implement_ty_decoder {
 454     ($DecoderName:ident <$($typaram:tt),*>) => {
 455         mod __ty_decoder_impl {
 456             use std::borrow::Cow;
 457             use rustc_serialize::Decoder;
 458
 459             use super::$DecoderName;
 460
 461             impl<$($typaram ),*> Decoder for $DecoderName<$($typaram),*> {
 462                 type Error = String;
 463
 464                 $crate::__impl_decoder_methods! {
 465                     read_nil -> ();
 466
 467                     read_u128 -> u128;
 468                     read_u64 -> u64;
 469                     read_u32 -> u32;
 470                     read_u16 -> u16;
 471                     read_u8 -> u8;
 472                     read_usize -> usize;
 473
 474                     read_i128 -> i128;
 475                     read_i64 -> i64;
 476                     read_i32 -> i32;
 477                     read_i16 -> i16;
 478                     read_i8 -> i8;
 479                     read_isize -> isize;
 480
 481                     read_bool -> bool;
 482                     read_f64 -> f64;
 483                     read_f32 -> f32;
 484                     read_char -> char;
 485                     read_str -> Cow<'_, str>;
 486                 }
 487
 488                 #[inline]
 489                 fn read_raw_bytes_into(&mut self, bytes: &mut [u8]) -> Result<(), Self::Error> {
 490                     self.opaque.read_raw_bytes_into(bytes)
 491                 }
 492
 493                 fn error(&mut self, err: &str) -> Self::Error {
 494                     self.opaque.error(err)
 495                 }
 496             }
 497         }
 498     }
 499 }
 500
 501 macro_rules! impl_binder_encode_decode {
 502     ($($t:ty),+ $(,)?) => {
 503         $(
 504             impl<'tcx, E: TyEncoder<'tcx>> Encodable<E> for ty::Binder<'tcx, $t> {
 505                 fn encode(&self, e: &mut E) -> Result<(), E::Error> {
 506                     self.bound_vars().encode(e)?;
 507                     self.as_ref().skip_binder().encode(e)
 508                 }
 509             }
 510             impl<'tcx, D: TyDecoder<'tcx>> Decodable<D> for ty::Binder<'tcx, $t> {
 511                 fn decode(decoder: &mut D) -> Result<Self, D::Error> {
 512                     let bound_vars = Decodable::decode(decoder)?;
 513                     Ok(ty::Binder::bind_with_vars(Decodable::decode(decoder)?, bound_vars))
 514                 }
 515             }
 516         )*
 517     }
 518 }
 519
 520 impl_binder_encode_decode! {
 521     &'tcx ty::List<Ty<'tcx>>,
 522     ty::FnSig<'tcx>,
 523     ty::ExistentialPredicate<'tcx>,
 524     ty::TraitRef<'tcx>,
 525     Vec<ty::GeneratorInteriorTypeCause<'tcx>>,
 526 }