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