src/librustc/ty/query/on_disk_cache.rs

   1 use crate::dep_graph::{DepNodeIndex, SerializedDepNodeIndex};
   2 use crate::hir;
   3 use crate::hir::def_id::{CrateNum, DefIndex, DefId, LocalDefId, LOCAL_CRATE};
   4 use crate::hir::map::definitions::DefPathHash;
   5 use crate::ich::{CachingSourceMapView, Fingerprint};
   6 use crate::mir::{self, interpret};
   7 use crate::mir::interpret::{AllocDecodingSession, AllocDecodingState};
   8 use crate::rustc_serialize::{Decodable, Decoder, Encodable, Encoder, opaque,
   9                       SpecializedDecoder, SpecializedEncoder,
  10                       UseSpecializedDecodable, UseSpecializedEncodable};
  11 use crate::session::{CrateDisambiguator, Session};
  12 use crate::ty::{self, Ty};
  13 use crate::ty::codec::{self as ty_codec, TyDecoder, TyEncoder};
  14 use crate::ty::context::TyCtxt;
  15 use crate::util::common::{time, time_ext};
  16
  17 use errors::Diagnostic;
  18 use rustc_data_structures::fx::FxHashMap;
  19 use rustc_data_structures::thin_vec::ThinVec;
  20 use rustc_data_structures::sync::{Lrc, Lock, HashMapExt, Once};
  21 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  22 use std::mem;
  23 use syntax::ast::NodeId;
  24 use syntax::source_map::{SourceMap, StableSourceFileId};
  25 use syntax_pos::{BytePos, Span, DUMMY_SP, SourceFile};
  26 use syntax_pos::hygiene::{Mark, SyntaxContext, ExpnInfo};
  27
  28 const TAG_FILE_FOOTER: u128 = 0xC0FFEE_C0FFEE_C0FFEE_C0FFEE_C0FFEE;
  29
  30 const TAG_CLEAR_CROSS_CRATE_CLEAR: u8 = 0;
  31 const TAG_CLEAR_CROSS_CRATE_SET: u8 = 1;
  32
  33 const TAG_NO_EXPANSION_INFO: u8 = 0;
  34 const TAG_EXPANSION_INFO_SHORTHAND: u8 = 1;
  35 const TAG_EXPANSION_INFO_INLINE: u8 = 2;
  36
  37 const TAG_VALID_SPAN: u8 = 0;
  38 const TAG_INVALID_SPAN: u8 = 1;
  39
  40 /// `OnDiskCache` provides an interface to incr. comp. data cached from the
  41 /// previous compilation session. This data will eventually include the results
  42 /// of a few selected queries (like `typeck_tables_of` and `mir_optimized`) and
  43 /// any diagnostics that have been emitted during a query.
  44 pub struct OnDiskCache<'sess> {
  45
  46     // The complete cache data in serialized form.
  47     serialized_data: Vec<u8>,
  48
  49     // This field collects all Diagnostics emitted during the current
  50     // compilation session.
  51     current_diagnostics: Lock<FxHashMap<DepNodeIndex, Vec<Diagnostic>>>,
  52
  53     prev_cnums: Vec<(u32, String, CrateDisambiguator)>,
  54     cnum_map: Once<IndexVec<CrateNum, Option<CrateNum>>>,
  55
  56     source_map: &'sess SourceMap,
  57     file_index_to_stable_id: FxHashMap<SourceFileIndex, StableSourceFileId>,
  58
  59     // These two fields caches that are populated lazily during decoding.
  60     file_index_to_file: Lock<FxHashMap<SourceFileIndex, Lrc<SourceFile>>>,
  61     synthetic_expansion_infos: Lock<FxHashMap<AbsoluteBytePos, SyntaxContext>>,
  62
  63     // A map from dep-node to the position of the cached query result in
  64     // `serialized_data`.
  65     query_result_index: FxHashMap<SerializedDepNodeIndex, AbsoluteBytePos>,
  66
  67     // A map from dep-node to the position of any associated diagnostics in
  68     // `serialized_data`.
  69     prev_diagnostics_index: FxHashMap<SerializedDepNodeIndex, AbsoluteBytePos>,
  70
  71     alloc_decoding_state: AllocDecodingState,
  72 }
  73
  74 // This type is used only for (de-)serialization.
  75 #[derive(RustcEncodable, RustcDecodable)]
  76 struct Footer {
  77     file_index_to_stable_id: FxHashMap<SourceFileIndex, StableSourceFileId>,
  78     prev_cnums: Vec<(u32, String, CrateDisambiguator)>,
  79     query_result_index: EncodedQueryResultIndex,
  80     diagnostics_index: EncodedQueryResultIndex,
  81     // the location of all allocations
  82     interpret_alloc_index: Vec<u32>,
  83 }
  84
  85 type EncodedQueryResultIndex = Vec<(SerializedDepNodeIndex, AbsoluteBytePos)>;
  86 type EncodedDiagnosticsIndex = Vec<(SerializedDepNodeIndex, AbsoluteBytePos)>;
  87 type EncodedDiagnostics = Vec<Diagnostic>;
  88
  89 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
  90 struct SourceFileIndex(u32);
  91
  92 #[derive(Copy, Clone, Debug, Hash, Eq, PartialEq, RustcEncodable, RustcDecodable)]
  93 struct AbsoluteBytePos(u32);
  94
  95 impl AbsoluteBytePos {
  96     fn new(pos: usize) -> AbsoluteBytePos {
  97         debug_assert!(pos <= ::std::u32::MAX as usize);
  98         AbsoluteBytePos(pos as u32)
  99     }
 100
 101     fn to_usize(self) -> usize {
 102         self.0 as usize
 103     }
 104 }
 105
 106 impl<'sess> OnDiskCache<'sess> {
 107     /// Creates a new OnDiskCache instance from the serialized data in `data`.
 108     pub fn new(sess: &'sess Session, data: Vec<u8>, start_pos: usize) -> OnDiskCache<'sess> {
 109         debug_assert!(sess.opts.incremental.is_some());
 110
 111         // Wrapping in a scope so we can borrow `data`
 112         let footer: Footer = {
 113             let mut decoder = opaque::Decoder::new(&data[..], start_pos);
 114
 115             // Decode the *position* of the footer which can be found in the
 116             // last 8 bytes of the file.
 117             decoder.set_position(data.len() - IntEncodedWithFixedSize::ENCODED_SIZE);
 118             let query_result_index_pos = IntEncodedWithFixedSize::decode(&mut decoder)
 119                 .expect("Error while trying to decode query result index position.")
 120                 .0 as usize;
 121
 122             // Decoder the file footer which contains all the lookup tables, etc.
 123             decoder.set_position(query_result_index_pos);
 124             decode_tagged(&mut decoder, TAG_FILE_FOOTER)
 125                 .expect("Error while trying to decode query result index position.")
 126         };
 127
 128         OnDiskCache {
 129             serialized_data: data,
 130             file_index_to_stable_id: footer.file_index_to_stable_id,
 131             file_index_to_file: Default::default(),
 132             prev_cnums: footer.prev_cnums,
 133             cnum_map: Once::new(),
 134             source_map: sess.source_map(),
 135             current_diagnostics: Default::default(),
 136             query_result_index: footer.query_result_index.into_iter().collect(),
 137             prev_diagnostics_index: footer.diagnostics_index.into_iter().collect(),
 138             synthetic_expansion_infos: Default::default(),
 139             alloc_decoding_state: AllocDecodingState::new(footer.interpret_alloc_index),
 140         }
 141     }
 142
 143     pub fn new_empty(source_map: &'sess SourceMap) -> OnDiskCache<'sess> {
 144         OnDiskCache {
 145             serialized_data: Vec::new(),
 146             file_index_to_stable_id: Default::default(),
 147             file_index_to_file: Default::default(),
 148             prev_cnums: vec![],
 149             cnum_map: Once::new(),
 150             source_map,
 151             current_diagnostics: Default::default(),
 152             query_result_index: Default::default(),
 153             prev_diagnostics_index: Default::default(),
 154             synthetic_expansion_infos: Default::default(),
 155             alloc_decoding_state: AllocDecodingState::new(Vec::new()),
 156         }
 157     }
 158
 159     pub fn serialize<'tcx, E>(&self, tcx: TyCtxt<'tcx>, encoder: &mut E) -> Result<(), E::Error>
 160     where
 161         E: ty_codec::TyEncoder,
 162     {
 163         // Serializing the DepGraph should not modify it:
 164         tcx.dep_graph.with_ignore(|| {
 165             // Allocate SourceFileIndices
 166             let (file_to_file_index, file_index_to_stable_id) = {
 167                 let files = tcx.sess.source_map().files();
 168                 let mut file_to_file_index = FxHashMap::with_capacity_and_hasher(
 169                     files.len(), Default::default());
 170                 let mut file_index_to_stable_id = FxHashMap::with_capacity_and_hasher(
 171                     files.len(), Default::default());
 172
 173                 for (index, file) in files.iter().enumerate() {
 174                     let index = SourceFileIndex(index as u32);
 175                     let file_ptr: *const SourceFile = &**file as *const _;
 176                     file_to_file_index.insert(file_ptr, index);
 177                     file_index_to_stable_id.insert(index, StableSourceFileId::new(&file));
 178                 }
 179
 180                 (file_to_file_index, file_index_to_stable_id)
 181             };
 182
 183             let mut encoder = CacheEncoder {
 184                 tcx,
 185                 encoder,
 186                 type_shorthands: Default::default(),
 187                 predicate_shorthands: Default::default(),
 188                 expn_info_shorthands: Default::default(),
 189                 interpret_allocs: Default::default(),
 190                 interpret_allocs_inverse: Vec::new(),
 191                 source_map: CachingSourceMapView::new(tcx.sess.source_map()),
 192                 file_to_file_index,
 193             };
 194
 195             // Load everything into memory so we can write it out to the on-disk
 196             // cache. The vast majority of cacheable query results should already
 197             // be in memory, so this should be a cheap operation.
 198             tcx.dep_graph.exec_cache_promotions(tcx);
 199
 200             // Encode query results
 201             let mut query_result_index = EncodedQueryResultIndex::new();
 202
 203             time(tcx.sess, "encode query results", || {
 204                 use crate::ty::query::queries::*;
 205                 let enc = &mut encoder;
 206                 let qri = &mut query_result_index;
 207
 208                 encode_query_results::<type_of<'_>, _>(tcx, enc, qri)?;
 209                 encode_query_results::<generics_of<'_>, _>(tcx, enc, qri)?;
 210                 encode_query_results::<predicates_of<'_>, _>(tcx, enc, qri)?;
 211                 encode_query_results::<used_trait_imports<'_>, _>(tcx, enc, qri)?;
 212                 encode_query_results::<typeck_tables_of<'_>, _>(tcx, enc, qri)?;
 213                 encode_query_results::<codegen_fulfill_obligation<'_>, _>(tcx, enc, qri)?;
 214                 encode_query_results::<optimized_mir<'_>, _>(tcx, enc, qri)?;
 215                 encode_query_results::<unsafety_check_result<'_>, _>(tcx, enc, qri)?;
 216                 encode_query_results::<borrowck<'_>, _>(tcx, enc, qri)?;
 217                 encode_query_results::<mir_borrowck<'_>, _>(tcx, enc, qri)?;
 218                 encode_query_results::<mir_const_qualif<'_>, _>(tcx, enc, qri)?;
 219                 encode_query_results::<const_is_rvalue_promotable_to_static<'_>, _>(tcx, enc, qri)?;
 220                 encode_query_results::<symbol_name<'_>, _>(tcx, enc, qri)?;
 221                 encode_query_results::<check_match<'_>, _>(tcx, enc, qri)?;
 222                 encode_query_results::<codegen_fn_attrs<'_>, _>(tcx, enc, qri)?;
 223                 encode_query_results::<specialization_graph_of<'_>, _>(tcx, enc, qri)?;
 224                 encode_query_results::<const_eval<'_>, _>(tcx, enc, qri)?;
 225                 // FIXME: Include const_eval_raw?
 226
 227                 Ok(())
 228             })?;
 229
 230             // Encode diagnostics
 231             let diagnostics_index: EncodedDiagnosticsIndex = self.current_diagnostics.borrow()
 232                 .iter()
 233                 .map(|(dep_node_index, diagnostics)|
 234             {
 235                 let pos = AbsoluteBytePos::new(encoder.position());
 236                 // Let's make sure we get the expected type here:
 237                 let diagnostics: &EncodedDiagnostics = diagnostics;
 238                 let dep_node_index = SerializedDepNodeIndex::new(dep_node_index.index());
 239                 encoder.encode_tagged(dep_node_index, diagnostics)?;
 240
 241                 Ok((dep_node_index, pos))
 242             })
 243             .collect::<Result<_, _>>()?;
 244
 245             let interpret_alloc_index = {
 246                 let mut interpret_alloc_index = Vec::new();
 247                 let mut n = 0;
 248                 loop {
 249                     let new_n = encoder.interpret_allocs_inverse.len();
 250                     // if we have found new ids, serialize those, too
 251                     if n == new_n {
 252                         // otherwise, abort
 253                         break;
 254                     }
 255                     interpret_alloc_index.reserve(new_n - n);
 256                     for idx in n..new_n {
 257                         let id = encoder.interpret_allocs_inverse[idx];
 258                         let pos = encoder.position() as u32;
 259                         interpret_alloc_index.push(pos);
 260                         interpret::specialized_encode_alloc_id(
 261                             &mut encoder,
 262                             tcx,
 263                             id,
 264                         )?;
 265                     }
 266                     n = new_n;
 267                 }
 268                 interpret_alloc_index
 269             };
 270
 271             let sorted_cnums = sorted_cnums_including_local_crate(tcx);
 272             let prev_cnums: Vec<_> = sorted_cnums.iter().map(|&cnum| {
 273                 let crate_name = tcx.original_crate_name(cnum).as_str().to_string();
 274                 let crate_disambiguator = tcx.crate_disambiguator(cnum);
 275                 (cnum.as_u32(), crate_name, crate_disambiguator)
 276             }).collect();
 277
 278             // Encode the file footer
 279             let footer_pos = encoder.position() as u64;
 280             encoder.encode_tagged(TAG_FILE_FOOTER, &Footer {
 281                 file_index_to_stable_id,
 282                 prev_cnums,
 283                 query_result_index,
 284                 diagnostics_index,
 285                 interpret_alloc_index,
 286             })?;
 287
 288             // Encode the position of the footer as the last 8 bytes of the
 289             // file so we know where to look for it.
 290             IntEncodedWithFixedSize(footer_pos).encode(encoder.encoder)?;
 291
 292             // DO NOT WRITE ANYTHING TO THE ENCODER AFTER THIS POINT! The address
 293             // of the footer must be the last thing in the data stream.
 294
 295             return Ok(());
 296
 297             fn sorted_cnums_including_local_crate(tcx: TyCtxt<'_>) -> Vec<CrateNum> {
 298                 let mut cnums = vec![LOCAL_CRATE];
 299                 cnums.extend_from_slice(&tcx.crates()[..]);
 300                 cnums.sort_unstable();
 301                 // Just to be sure...
 302                 cnums.dedup();
 303                 cnums
 304             }
 305         })
 306     }
 307
 308     /// Loads a diagnostic emitted during the previous compilation session.
 309     pub fn load_diagnostics<'tcx>(
 310         &self,
 311         tcx: TyCtxt<'tcx>,
 312         dep_node_index: SerializedDepNodeIndex,
 313     ) -> Vec<Diagnostic> {
 314         let diagnostics: Option<EncodedDiagnostics> = self.load_indexed(
 315             tcx,
 316             dep_node_index,
 317             &self.prev_diagnostics_index,
 318             "diagnostics");
 319
 320         diagnostics.unwrap_or_default()
 321     }
 322
 323     /// Stores a diagnostic emitted during the current compilation session.
 324     /// Anything stored like this will be available via `load_diagnostics` in
 325     /// the next compilation session.
 326     #[inline(never)]
 327     #[cold]
 328     pub fn store_diagnostics(&self,
 329                              dep_node_index: DepNodeIndex,
 330                              diagnostics: ThinVec<Diagnostic>) {
 331         let mut current_diagnostics = self.current_diagnostics.borrow_mut();
 332         let prev = current_diagnostics.insert(dep_node_index, diagnostics.into());
 333         debug_assert!(prev.is_none());
 334     }
 335
 336     /// Returns the cached query result if there is something in the cache for
 337     /// the given `SerializedDepNodeIndex`; otherwise returns `None`.
 338     pub fn try_load_query_result<'tcx, T>(
 339         &self,
 340         tcx: TyCtxt<'tcx>,
 341         dep_node_index: SerializedDepNodeIndex,
 342     ) -> Option<T>
 343     where
 344         T: Decodable,
 345     {
 346         self.load_indexed(tcx,
 347                           dep_node_index,
 348                           &self.query_result_index,
 349                           "query result")
 350     }
 351
 352     /// Stores a diagnostic emitted during computation of an anonymous query.
 353     /// Since many anonymous queries can share the same `DepNode`, we aggregate
 354     /// them -- as opposed to regular queries where we assume that there is a
 355     /// 1:1 relationship between query-key and `DepNode`.
 356     #[inline(never)]
 357     #[cold]
 358     pub fn store_diagnostics_for_anon_node(&self,
 359                                            dep_node_index: DepNodeIndex,
 360                                            diagnostics: ThinVec<Diagnostic>) {
 361         let mut current_diagnostics = self.current_diagnostics.borrow_mut();
 362
 363         let x = current_diagnostics.entry(dep_node_index).or_insert(Vec::new());
 364
 365         x.extend(Into::<Vec<_>>::into(diagnostics));
 366     }
 367
 368     fn load_indexed<'tcx, T>(
 369         &self,
 370         tcx: TyCtxt<'tcx>,
 371         dep_node_index: SerializedDepNodeIndex,
 372         index: &FxHashMap<SerializedDepNodeIndex, AbsoluteBytePos>,
 373         debug_tag: &'static str,
 374     ) -> Option<T>
 375     where
 376         T: Decodable,
 377     {
 378         let pos = index.get(&dep_node_index).cloned()?;
 379
 380         // Initialize the cnum_map using the value from the thread which finishes the closure first
 381         self.cnum_map.init_nonlocking_same(|| {
 382             Self::compute_cnum_map(tcx, &self.prev_cnums[..])
 383         });
 384
 385         let mut decoder = CacheDecoder {
 386             tcx,
 387             opaque: opaque::Decoder::new(&self.serialized_data[..], pos.to_usize()),
 388             source_map: self.source_map,
 389             cnum_map: self.cnum_map.get(),
 390             file_index_to_file: &self.file_index_to_file,
 391             file_index_to_stable_id: &self.file_index_to_stable_id,
 392             synthetic_expansion_infos: &self.synthetic_expansion_infos,
 393             alloc_decoding_session: self.alloc_decoding_state.new_decoding_session(),
 394         };
 395
 396         match decode_tagged(&mut decoder, dep_node_index) {
 397             Ok(value) => {
 398                 Some(value)
 399             }
 400             Err(e) => {
 401                 bug!("Could not decode cached {}: {}", debug_tag, e)
 402             }
 403         }
 404     }
 405
 406     // This function builds mapping from previous-session-CrateNum to
 407     // current-session-CrateNum. There might be CrateNums from the previous
 408     // Session that don't occur in the current one. For these, the mapping
 409     // maps to None.
 410     fn compute_cnum_map(
 411         tcx: TyCtxt<'_>,
 412         prev_cnums: &[(u32, String, CrateDisambiguator)],
 413     ) -> IndexVec<CrateNum, Option<CrateNum>> {
 414         tcx.dep_graph.with_ignore(|| {
 415             let current_cnums = tcx.all_crate_nums(LOCAL_CRATE).iter().map(|&cnum| {
 416                 let crate_name = tcx.original_crate_name(cnum)
 417                                     .to_string();
 418                 let crate_disambiguator = tcx.crate_disambiguator(cnum);
 419                 ((crate_name, crate_disambiguator), cnum)
 420             }).collect::<FxHashMap<_,_>>();
 421
 422             let map_size = prev_cnums.iter()
 423                                      .map(|&(cnum, ..)| cnum)
 424                                      .max()
 425                                      .unwrap_or(0) + 1;
 426             let mut map = IndexVec::from_elem_n(None, map_size as usize);
 427
 428             for &(prev_cnum, ref crate_name, crate_disambiguator) in prev_cnums {
 429                 let key = (crate_name.clone(), crate_disambiguator);
 430                 map[CrateNum::from_u32(prev_cnum)] = current_cnums.get(&key).cloned();
 431             }
 432
 433             map[LOCAL_CRATE] = Some(LOCAL_CRATE);
 434             map
 435         })
 436     }
 437 }
 438
 439 //- DECODING -------------------------------------------------------------------
 440
 441 /// A decoder that can read the incr. comp. cache. It is similar to the one
 442 /// we use for crate metadata decoding in that it can rebase spans and
 443 /// eventually will also handle things that contain `Ty` instances.
 444 struct CacheDecoder<'a, 'tcx> {
 445     tcx: TyCtxt<'tcx>,
 446     opaque: opaque::Decoder<'a>,
 447     source_map: &'a SourceMap,
 448     cnum_map: &'a IndexVec<CrateNum, Option<CrateNum>>,
 449     synthetic_expansion_infos: &'a Lock<FxHashMap<AbsoluteBytePos, SyntaxContext>>,
 450     file_index_to_file: &'a Lock<FxHashMap<SourceFileIndex, Lrc<SourceFile>>>,
 451     file_index_to_stable_id: &'a FxHashMap<SourceFileIndex, StableSourceFileId>,
 452     alloc_decoding_session: AllocDecodingSession<'a>,
 453 }
 454
 455 impl<'a, 'tcx> CacheDecoder<'a, 'tcx> {
 456     fn file_index_to_file(&self, index: SourceFileIndex) -> Lrc<SourceFile> {
 457         let CacheDecoder {
 458             ref file_index_to_file,
 459             ref file_index_to_stable_id,
 460             ref source_map,
 461             ..
 462         } = *self;
 463
 464         file_index_to_file.borrow_mut().entry(index).or_insert_with(|| {
 465             let stable_id = file_index_to_stable_id[&index];
 466             source_map.source_file_by_stable_id(stable_id)
 467                 .expect("Failed to lookup SourceFile in new context.")
 468         }).clone()
 469     }
 470 }
 471
 472 trait DecoderWithPosition: Decoder {
 473     fn position(&self) -> usize;
 474 }
 475
 476 impl<'a> DecoderWithPosition for opaque::Decoder<'a> {
 477     fn position(&self) -> usize {
 478         self.position()
 479     }
 480 }
 481
 482 impl<'a, 'tcx> DecoderWithPosition for CacheDecoder<'a, 'tcx> {
 483     fn position(&self) -> usize {
 484         self.opaque.position()
 485     }
 486 }
 487
 488 // Decode something that was encoded with encode_tagged() and verify that the
 489 // tag matches and the correct amount of bytes was read.
 490 fn decode_tagged<D, T, V>(decoder: &mut D, expected_tag: T) -> Result<V, D::Error>
 491 where
 492     T: Decodable + Eq + ::std::fmt::Debug,
 493     V: Decodable,
 494     D: DecoderWithPosition,
 495 {
 496     let start_pos = decoder.position();
 497
 498     let actual_tag = T::decode(decoder)?;
 499     assert_eq!(actual_tag, expected_tag);
 500     let value = V::decode(decoder)?;
 501     let end_pos = decoder.position();
 502
 503     let expected_len: u64 = Decodable::decode(decoder)?;
 504     assert_eq!((end_pos - start_pos) as u64, expected_len);
 505
 506     Ok(value)
 507 }
 508
 509 impl<'a, 'tcx> ty_codec::TyDecoder<'tcx> for CacheDecoder<'a, 'tcx> {
 510     #[inline]
 511     fn tcx(&self) -> TyCtxt<'tcx> {
 512         self.tcx
 513     }
 514
 515     #[inline]
 516     fn position(&self) -> usize {
 517         self.opaque.position()
 518     }
 519
 520     #[inline]
 521     fn peek_byte(&self) -> u8 {
 522         self.opaque.data[self.opaque.position()]
 523     }
 524
 525     fn cached_ty_for_shorthand<F>(&mut self,
 526                                   shorthand: usize,
 527                                   or_insert_with: F)
 528                                   -> Result<Ty<'tcx>, Self::Error>
 529         where F: FnOnce(&mut Self) -> Result<Ty<'tcx>, Self::Error>
 530     {
 531         let tcx = self.tcx();
 532
 533         let cache_key = ty::CReaderCacheKey {
 534             cnum: CrateNum::ReservedForIncrCompCache,
 535             pos: shorthand,
 536         };
 537
 538         if let Some(&ty) = tcx.rcache.borrow().get(&cache_key) {
 539             return Ok(ty);
 540         }
 541
 542         let ty = or_insert_with(self)?;
 543         // This may overwrite the entry, but it should overwrite with the same value
 544         tcx.rcache.borrow_mut().insert_same(cache_key, ty);
 545         Ok(ty)
 546     }
 547
 548     fn with_position<F, R>(&mut self, pos: usize, f: F) -> R
 549         where F: FnOnce(&mut Self) -> R
 550     {
 551         debug_assert!(pos < self.opaque.data.len());
 552
 553         let new_opaque = opaque::Decoder::new(self.opaque.data, pos);
 554         let old_opaque = mem::replace(&mut self.opaque, new_opaque);
 555         let r = f(self);
 556         self.opaque = old_opaque;
 557         r
 558     }
 559
 560     fn map_encoded_cnum_to_current(&self, cnum: CrateNum) -> CrateNum {
 561         self.cnum_map[cnum].unwrap_or_else(|| {
 562             bug!("Could not find new CrateNum for {:?}", cnum)
 563         })
 564     }
 565 }
 566
 567 implement_ty_decoder!(CacheDecoder<'a, 'tcx>);
 568
 569 impl<'a, 'tcx> SpecializedDecoder<interpret::AllocId> for CacheDecoder<'a, 'tcx> {
 570     fn specialized_decode(&mut self) -> Result<interpret::AllocId, Self::Error> {
 571         let alloc_decoding_session = self.alloc_decoding_session;
 572         alloc_decoding_session.decode_alloc_id(self)
 573     }
 574 }
 575
 576 impl<'a, 'tcx> SpecializedDecoder<Span> for CacheDecoder<'a, 'tcx> {
 577     fn specialized_decode(&mut self) -> Result<Span, Self::Error> {
 578         let tag: u8 = Decodable::decode(self)?;
 579
 580         if tag == TAG_INVALID_SPAN {
 581             return Ok(DUMMY_SP);
 582         } else {
 583             debug_assert_eq!(tag, TAG_VALID_SPAN);
 584         }
 585
 586         let file_lo_index = SourceFileIndex::decode(self)?;
 587         let line_lo = usize::decode(self)?;
 588         let col_lo = BytePos::decode(self)?;
 589         let len = BytePos::decode(self)?;
 590
 591         let file_lo = self.file_index_to_file(file_lo_index);
 592         let lo = file_lo.lines[line_lo - 1] + col_lo;
 593         let hi = lo + len;
 594
 595         let expn_info_tag = u8::decode(self)?;
 596
 597         let ctxt = match expn_info_tag {
 598             TAG_NO_EXPANSION_INFO => {
 599                 SyntaxContext::empty()
 600             }
 601             TAG_EXPANSION_INFO_INLINE => {
 602                 let pos = AbsoluteBytePos::new(self.opaque.position());
 603                 let expn_info: ExpnInfo = Decodable::decode(self)?;
 604                 let ctxt = SyntaxContext::allocate_directly(expn_info);
 605                 self.synthetic_expansion_infos.borrow_mut().insert(pos, ctxt);
 606                 ctxt
 607             }
 608             TAG_EXPANSION_INFO_SHORTHAND => {
 609                 let pos = AbsoluteBytePos::decode(self)?;
 610                 let cached_ctxt = self.synthetic_expansion_infos
 611                                       .borrow()
 612                                       .get(&pos)
 613                                       .cloned();
 614
 615                 if let Some(ctxt) = cached_ctxt {
 616                     ctxt
 617                 } else {
 618                     let expn_info = self.with_position(pos.to_usize(), |this| {
 619                          ExpnInfo::decode(this)
 620                     })?;
 621                     let ctxt = SyntaxContext::allocate_directly(expn_info);
 622                     self.synthetic_expansion_infos.borrow_mut().insert(pos, ctxt);
 623                     ctxt
 624                 }
 625             }
 626             _ => {
 627                 unreachable!()
 628             }
 629         };
 630
 631         Ok(Span::new(lo, hi, ctxt))
 632     }
 633 }
 634
 635 // This impl makes sure that we get a runtime error when we try decode a
 636 // DefIndex that is not contained in a DefId. Such a case would be problematic
 637 // because we would not know how to transform the DefIndex to the current
 638 // context.
 639 impl<'a, 'tcx> SpecializedDecoder<DefIndex> for CacheDecoder<'a, 'tcx> {
 640     fn specialized_decode(&mut self) -> Result<DefIndex, Self::Error> {
 641         bug!("Trying to decode DefIndex outside the context of a DefId")
 642     }
 643 }
 644
 645 // Both the CrateNum and the DefIndex of a DefId can change in between two
 646 // compilation sessions. We use the DefPathHash, which is stable across
 647 // sessions, to map the old DefId to the new one.
 648 impl<'a, 'tcx> SpecializedDecoder<DefId> for CacheDecoder<'a, 'tcx> {
 649     #[inline]
 650     fn specialized_decode(&mut self) -> Result<DefId, Self::Error> {
 651         // Load the DefPathHash which is was we encoded the DefId as.
 652         let def_path_hash = DefPathHash::decode(self)?;
 653
 654         // Using the DefPathHash, we can lookup the new DefId
 655         Ok(self.tcx().def_path_hash_to_def_id.as_ref().unwrap()[&def_path_hash])
 656     }
 657 }
 658
 659 impl<'a, 'tcx> SpecializedDecoder<LocalDefId> for CacheDecoder<'a, 'tcx> {
 660     #[inline]
 661     fn specialized_decode(&mut self) -> Result<LocalDefId, Self::Error> {
 662         Ok(LocalDefId::from_def_id(DefId::decode(self)?))
 663     }
 664 }
 665
 666 impl<'a, 'tcx> SpecializedDecoder<hir::HirId> for CacheDecoder<'a, 'tcx> {
 667     fn specialized_decode(&mut self) -> Result<hir::HirId, Self::Error> {
 668         // Load the DefPathHash which is was we encoded the DefIndex as.
 669         let def_path_hash = DefPathHash::decode(self)?;
 670
 671         // Use the DefPathHash to map to the current DefId.
 672         let def_id = self.tcx()
 673                          .def_path_hash_to_def_id
 674                          .as_ref()
 675                          .unwrap()[&def_path_hash];
 676
 677         debug_assert!(def_id.is_local());
 678
 679         // The ItemLocalId needs no remapping.
 680         let local_id = hir::ItemLocalId::decode(self)?;
 681
 682         // Reconstruct the HirId and look up the corresponding NodeId in the
 683         // context of the current session.
 684         Ok(hir::HirId {
 685             owner: def_id.index,
 686             local_id
 687         })
 688     }
 689 }
 690
 691 // NodeIds are not stable across compilation sessions, so we store them in their
 692 // HirId representation. This allows use to map them to the current NodeId.
 693 impl<'a, 'tcx> SpecializedDecoder<NodeId> for CacheDecoder<'a, 'tcx> {
 694     #[inline]
 695     fn specialized_decode(&mut self) -> Result<NodeId, Self::Error> {
 696         let hir_id = hir::HirId::decode(self)?;
 697         Ok(self.tcx().hir().hir_to_node_id(hir_id))
 698     }
 699 }
 700
 701 impl<'a, 'tcx> SpecializedDecoder<Fingerprint> for CacheDecoder<'a, 'tcx> {
 702     fn specialized_decode(&mut self) -> Result<Fingerprint, Self::Error> {
 703         Fingerprint::decode_opaque(&mut self.opaque)
 704     }
 705 }
 706
 707 impl<'a, 'tcx, T: Decodable> SpecializedDecoder<mir::ClearCrossCrate<T>>
 708     for CacheDecoder<'a, 'tcx>
 709 {
 710     #[inline]
 711     fn specialized_decode(&mut self) -> Result<mir::ClearCrossCrate<T>, Self::Error> {
 712         let discr = u8::decode(self)?;
 713
 714         match discr {
 715             TAG_CLEAR_CROSS_CRATE_CLEAR => Ok(mir::ClearCrossCrate::Clear),
 716             TAG_CLEAR_CROSS_CRATE_SET => {
 717                 let val = T::decode(self)?;
 718                 Ok(mir::ClearCrossCrate::Set(val))
 719             }
 720             _ => {
 721                 unreachable!()
 722             }
 723         }
 724     }
 725 }
 726
 727 //- ENCODING -------------------------------------------------------------------
 728
 729 struct CacheEncoder<'a, 'tcx, E: ty_codec::TyEncoder> {
 730     tcx: TyCtxt<'tcx>,
 731     encoder: &'a mut E,
 732     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
 733     predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
 734     expn_info_shorthands: FxHashMap<Mark, AbsoluteBytePos>,
 735     interpret_allocs: FxHashMap<interpret::AllocId, usize>,
 736     interpret_allocs_inverse: Vec<interpret::AllocId>,
 737     source_map: CachingSourceMapView<'tcx>,
 738     file_to_file_index: FxHashMap<*const SourceFile, SourceFileIndex>,
 739 }
 740
 741 impl<'a, 'tcx, E> CacheEncoder<'a, 'tcx, E>
 742 where
 743     E: 'a + ty_codec::TyEncoder,
 744 {
 745     fn source_file_index(&mut self, source_file: Lrc<SourceFile>) -> SourceFileIndex {
 746         self.file_to_file_index[&(&*source_file as *const SourceFile)]
 747     }
 748
 749     /// Encode something with additional information that allows to do some
 750     /// sanity checks when decoding the data again. This method will first
 751     /// encode the specified tag, then the given value, then the number of
 752     /// bytes taken up by tag and value. On decoding, we can then verify that
 753     /// we get the expected tag and read the expected number of bytes.
 754     fn encode_tagged<T: Encodable, V: Encodable>(&mut self,
 755                                                  tag: T,
 756                                                  value: &V)
 757                                                  -> Result<(), E::Error>
 758     {
 759         let start_pos = self.position();
 760
 761         tag.encode(self)?;
 762         value.encode(self)?;
 763
 764         let end_pos = self.position();
 765         ((end_pos - start_pos) as u64).encode(self)
 766     }
 767 }
 768
 769 impl<'a, 'tcx, E> SpecializedEncoder<interpret::AllocId> for CacheEncoder<'a, 'tcx, E>
 770 where
 771     E: 'a + ty_codec::TyEncoder,
 772 {
 773     fn specialized_encode(&mut self, alloc_id: &interpret::AllocId) -> Result<(), Self::Error> {
 774         use std::collections::hash_map::Entry;
 775         let index = match self.interpret_allocs.entry(*alloc_id) {
 776             Entry::Occupied(e) => *e.get(),
 777             Entry::Vacant(e) => {
 778                 let idx = self.interpret_allocs_inverse.len();
 779                 self.interpret_allocs_inverse.push(*alloc_id);
 780                 e.insert(idx);
 781                 idx
 782             },
 783         };
 784
 785         index.encode(self)
 786     }
 787 }
 788
 789 impl<'a, 'tcx, E> SpecializedEncoder<Span> for CacheEncoder<'a, 'tcx, E>
 790 where
 791     E: 'a + ty_codec::TyEncoder,
 792 {
 793     fn specialized_encode(&mut self, span: &Span) -> Result<(), Self::Error> {
 794
 795         if *span == DUMMY_SP {
 796             return TAG_INVALID_SPAN.encode(self);
 797         }
 798
 799         let span_data = span.data();
 800
 801         if span_data.hi < span_data.lo {
 802             return TAG_INVALID_SPAN.encode(self);
 803         }
 804
 805         let (file_lo, line_lo, col_lo) = match self.source_map
 806                                                    .byte_pos_to_line_and_col(span_data.lo) {
 807             Some(pos) => pos,
 808             None => return TAG_INVALID_SPAN.encode(self)
 809         };
 810
 811         if !file_lo.contains(span_data.hi) {
 812             return TAG_INVALID_SPAN.encode(self);
 813         }
 814
 815         let len = span_data.hi - span_data.lo;
 816
 817         let source_file_index = self.source_file_index(file_lo);
 818
 819         TAG_VALID_SPAN.encode(self)?;
 820         source_file_index.encode(self)?;
 821         line_lo.encode(self)?;
 822         col_lo.encode(self)?;
 823         len.encode(self)?;
 824
 825         if span_data.ctxt == SyntaxContext::empty() {
 826             TAG_NO_EXPANSION_INFO.encode(self)
 827         } else {
 828             let (mark, expn_info) = span_data.ctxt.outer_and_expn_info();
 829             if let Some(expn_info) = expn_info {
 830                 if let Some(pos) = self.expn_info_shorthands.get(&mark).cloned() {
 831                     TAG_EXPANSION_INFO_SHORTHAND.encode(self)?;
 832                     pos.encode(self)
 833                 } else {
 834                     TAG_EXPANSION_INFO_INLINE.encode(self)?;
 835                     let pos = AbsoluteBytePos::new(self.position());
 836                     self.expn_info_shorthands.insert(mark, pos);
 837                     expn_info.encode(self)
 838                 }
 839             } else {
 840                 TAG_NO_EXPANSION_INFO.encode(self)
 841             }
 842         }
 843     }
 844 }
 845
 846 impl<'a, 'tcx, E> ty_codec::TyEncoder for CacheEncoder<'a, 'tcx, E>
 847 where
 848     E: 'a + ty_codec::TyEncoder,
 849 {
 850     #[inline]
 851     fn position(&self) -> usize {
 852         self.encoder.position()
 853     }
 854 }
 855
 856 impl<'a, 'tcx, E> SpecializedEncoder<CrateNum> for CacheEncoder<'a, 'tcx, E>
 857 where
 858     E: 'a + ty_codec::TyEncoder,
 859 {
 860     #[inline]
 861     fn specialized_encode(&mut self, cnum: &CrateNum) -> Result<(), Self::Error> {
 862         self.emit_u32(cnum.as_u32())
 863     }
 864 }
 865
 866 impl<'a, 'tcx, E> SpecializedEncoder<Ty<'tcx>> for CacheEncoder<'a, 'tcx, E>
 867 where
 868     E: 'a + ty_codec::TyEncoder,
 869 {
 870     #[inline]
 871     fn specialized_encode(&mut self, ty: &Ty<'tcx>) -> Result<(), Self::Error> {
 872         ty_codec::encode_with_shorthand(self, ty,
 873             |encoder| &mut encoder.type_shorthands)
 874     }
 875 }
 876
 877 impl<'a, 'tcx, E> SpecializedEncoder<ty::GenericPredicates<'tcx>> for CacheEncoder<'a, 'tcx, E>
 878 where
 879     E: 'a + ty_codec::TyEncoder,
 880 {
 881     #[inline]
 882     fn specialized_encode(&mut self,
 883                           predicates: &ty::GenericPredicates<'tcx>)
 884                           -> Result<(), Self::Error> {
 885         ty_codec::encode_predicates(self, predicates,
 886             |encoder| &mut encoder.predicate_shorthands)
 887     }
 888 }
 889
 890 impl<'a, 'tcx, E> SpecializedEncoder<hir::HirId> for CacheEncoder<'a, 'tcx, E>
 891 where
 892     E: 'a + ty_codec::TyEncoder,
 893 {
 894     #[inline]
 895     fn specialized_encode(&mut self, id: &hir::HirId) -> Result<(), Self::Error> {
 896         let hir::HirId {
 897             owner,
 898             local_id,
 899         } = *id;
 900
 901         let def_path_hash = self.tcx.hir().definitions().def_path_hash(owner);
 902
 903         def_path_hash.encode(self)?;
 904         local_id.encode(self)
 905     }
 906 }
 907
 908 impl<'a, 'tcx, E> SpecializedEncoder<DefId> for CacheEncoder<'a, 'tcx, E>
 909 where
 910     E: 'a + ty_codec::TyEncoder,
 911 {
 912     #[inline]
 913     fn specialized_encode(&mut self, id: &DefId) -> Result<(), Self::Error> {
 914         let def_path_hash = self.tcx.def_path_hash(*id);
 915         def_path_hash.encode(self)
 916     }
 917 }
 918
 919 impl<'a, 'tcx, E> SpecializedEncoder<LocalDefId> for CacheEncoder<'a, 'tcx, E>
 920 where
 921     E: 'a + ty_codec::TyEncoder,
 922 {
 923     #[inline]
 924     fn specialized_encode(&mut self, id: &LocalDefId) -> Result<(), Self::Error> {
 925         id.to_def_id().encode(self)
 926     }
 927 }
 928
 929 impl<'a, 'tcx, E> SpecializedEncoder<DefIndex> for CacheEncoder<'a, 'tcx, E>
 930 where
 931     E: 'a + ty_codec::TyEncoder,
 932 {
 933     fn specialized_encode(&mut self, _: &DefIndex) -> Result<(), Self::Error> {
 934         bug!("Encoding DefIndex without context.")
 935     }
 936 }
 937
 938 // NodeIds are not stable across compilation sessions, so we store them in their
 939 // HirId representation. This allows use to map them to the current NodeId.
 940 impl<'a, 'tcx, E> SpecializedEncoder<NodeId> for CacheEncoder<'a, 'tcx, E>
 941 where
 942     E: 'a + ty_codec::TyEncoder,
 943 {
 944     #[inline]
 945     fn specialized_encode(&mut self, node_id: &NodeId) -> Result<(), Self::Error> {
 946         let hir_id = self.tcx.hir().node_to_hir_id(*node_id);
 947         hir_id.encode(self)
 948     }
 949 }
 950
 951 impl<'a, 'tcx> SpecializedEncoder<Fingerprint> for CacheEncoder<'a, 'tcx, opaque::Encoder> {
 952     fn specialized_encode(&mut self, f: &Fingerprint) -> Result<(), Self::Error> {
 953         f.encode_opaque(&mut self.encoder)
 954     }
 955 }
 956
 957 impl<'a, 'tcx, E, T> SpecializedEncoder<mir::ClearCrossCrate<T>> for CacheEncoder<'a, 'tcx, E>
 958 where
 959     E: 'a + ty_codec::TyEncoder,
 960     T: Encodable,
 961 {
 962     #[inline]
 963     fn specialized_encode(&mut self,
 964                           val: &mir::ClearCrossCrate<T>)
 965                           -> Result<(), Self::Error> {
 966         match *val {
 967             mir::ClearCrossCrate::Clear => {
 968                 TAG_CLEAR_CROSS_CRATE_CLEAR.encode(self)
 969             }
 970             mir::ClearCrossCrate::Set(ref val) => {
 971                 TAG_CLEAR_CROSS_CRATE_SET.encode(self)?;
 972                 val.encode(self)
 973             }
 974         }
 975     }
 976 }
 977
 978 macro_rules! encoder_methods {
 979     ($($name:ident($ty:ty);)*) => {
 980         $(fn $name(&mut self, value: $ty) -> Result<(), Self::Error> {
 981             self.encoder.$name(value)
 982         })*
 983     }
 984 }
 985
 986 impl<'a, 'tcx, E> Encoder for CacheEncoder<'a, 'tcx, E>
 987 where
 988     E: 'a + ty_codec::TyEncoder,
 989 {
 990     type Error = E::Error;
 991
 992     fn emit_unit(&mut self) -> Result<(), Self::Error> {
 993         Ok(())
 994     }
 995
 996     encoder_methods! {
 997         emit_usize(usize);
 998         emit_u128(u128);
 999         emit_u64(u64);
1000         emit_u32(u32);
1001         emit_u16(u16);
1002         emit_u8(u8);
1003
1004         emit_isize(isize);
1005         emit_i128(i128);
1006         emit_i64(i64);
1007         emit_i32(i32);
1008         emit_i16(i16);
1009         emit_i8(i8);
1010
1011         emit_bool(bool);
1012         emit_f64(f64);
1013         emit_f32(f32);
1014         emit_char(char);
1015         emit_str(&str);
1016     }
1017 }
1018
1019 // An integer that will always encode to 8 bytes.
1020 struct IntEncodedWithFixedSize(u64);
1021
1022 impl IntEncodedWithFixedSize {
1023     pub const ENCODED_SIZE: usize = 8;
1024 }
1025
1026 impl UseSpecializedEncodable for IntEncodedWithFixedSize {}
1027 impl UseSpecializedDecodable for IntEncodedWithFixedSize {}
1028
1029 impl SpecializedEncoder<IntEncodedWithFixedSize> for opaque::Encoder {
1030     fn specialized_encode(&mut self, x: &IntEncodedWithFixedSize) -> Result<(), Self::Error> {
1031         let start_pos = self.position();
1032         for i in 0 .. IntEncodedWithFixedSize::ENCODED_SIZE {
1033             ((x.0 >> i * 8) as u8).encode(self)?;
1034         }
1035         let end_pos = self.position();
1036         assert_eq!((end_pos - start_pos), IntEncodedWithFixedSize::ENCODED_SIZE);
1037         Ok(())
1038     }
1039 }
1040
1041 impl<'a> SpecializedDecoder<IntEncodedWithFixedSize> for opaque::Decoder<'a> {
1042     fn specialized_decode(&mut self) -> Result<IntEncodedWithFixedSize, Self::Error> {
1043         let mut value: u64 = 0;
1044         let start_pos = self.position();
1045
1046         for i in 0 .. IntEncodedWithFixedSize::ENCODED_SIZE {
1047             let byte: u8 = Decodable::decode(self)?;
1048             value |= (byte as u64) << (i * 8);
1049         }
1050
1051         let end_pos = self.position();
1052         assert_eq!((end_pos - start_pos), IntEncodedWithFixedSize::ENCODED_SIZE);
1053
1054         Ok(IntEncodedWithFixedSize(value))
1055     }
1056 }
1057
1058 fn encode_query_results<'a, 'tcx, Q, E>(
1059     tcx: TyCtxt<'tcx>,
1060     encoder: &mut CacheEncoder<'a, 'tcx, E>,
1061     query_result_index: &mut EncodedQueryResultIndex,
1062 ) -> Result<(), E::Error>
1063 where
1064     Q: super::config::QueryDescription<'tcx>,
1065     E: 'a + TyEncoder,
1066     Q::Value: Encodable,
1067 {
1068     let desc = &format!("encode_query_results for {}",
1069         unsafe { ::std::intrinsics::type_name::<Q>() });
1070
1071     time_ext(tcx.sess.time_extended(), Some(tcx.sess), desc, || {
1072         let map = Q::query_cache(tcx).borrow();
1073         assert!(map.active.is_empty());
1074         for (key, entry) in map.results.iter() {
1075             if Q::cache_on_disk(tcx, key.clone(), Some(&entry.value)) {
1076                 let dep_node = SerializedDepNodeIndex::new(entry.index.index());
1077
1078                 // Record position of the cache entry
1079                 query_result_index.push((dep_node, AbsoluteBytePos::new(encoder.position())));
1080
1081                 // Encode the type check tables with the SerializedDepNodeIndex
1082                 // as tag.
1083                 encoder.encode_tagged(dep_node, &entry.value)?;
1084             }
1085         }
1086
1087         Ok(())
1088     })
1089 }