src/librustc/ich/hcx.rs

   1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use hir;
  12 use hir::def_id::{DefId, DefIndex};
  13 use hir::map::DefPathHash;
  14 use hir::map::definitions::Definitions;
  15 use ich::{self, CachingSourceMapView, Fingerprint};
  16 use middle::cstore::CrateStore;
  17 use ty::{TyCtxt, fast_reject};
  18 use mir::interpret::AllocId;
  19 use session::Session;
  20
  21 use std::cmp::Ord;
  22 use std::hash as std_hash;
  23 use std::collections::HashMap;
  24 use std::cell::RefCell;
  25
  26 use syntax::ast;
  27
  28 use syntax::source_map::SourceMap;
  29 use syntax::ext::hygiene::SyntaxContext;
  30 use syntax::symbol::Symbol;
  31 use syntax_pos::{Span, DUMMY_SP};
  32 use syntax_pos::hygiene;
  33
  34 use rustc_data_structures::stable_hasher::{HashStable,
  35                                            StableHasher, StableHasherResult,
  36                                            ToStableHashKey};
  37 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
  38 use smallvec::SmallVec;
  39
  40 fn compute_ignored_attr_names() -> FxHashSet<Symbol> {
  41     debug_assert!(ich::IGNORED_ATTRIBUTES.len() > 0);
  42     ich::IGNORED_ATTRIBUTES.iter().map(|&s| Symbol::intern(s)).collect()
  43 }
  44
  45 /// This is the context state available during incr. comp. hashing. It contains
  46 /// enough information to transform DefIds and HirIds into stable DefPaths (i.e.
  47 /// a reference to the TyCtxt) and it holds a few caches for speeding up various
  48 /// things (e.g. each DefId/DefPath is only hashed once).
  49 #[derive(Clone)]
  50 pub struct StableHashingContext<'a> {
  51     sess: &'a Session,
  52     definitions: &'a Definitions,
  53     cstore: &'a dyn CrateStore,
  54     body_resolver: BodyResolver<'a>,
  55     hash_spans: bool,
  56     hash_bodies: bool,
  57     node_id_hashing_mode: NodeIdHashingMode,
  58
  59     // Very often, we are hashing something that does not need the
  60     // CachingSourceMapView, so we initialize it lazily.
  61     raw_source_map: &'a SourceMap,
  62     caching_source_map: Option<CachingSourceMapView<'a>>,
  63
  64     pub(super) alloc_id_recursion_tracker: FxHashSet<AllocId>,
  65 }
  66
  67 #[derive(PartialEq, Eq, Clone, Copy)]
  68 pub enum NodeIdHashingMode {
  69     Ignore,
  70     HashDefPath,
  71 }
  72
  73 /// The BodyResolver allows to map a BodyId to the corresponding hir::Body.
  74 /// We could also just store a plain reference to the hir::Crate but we want
  75 /// to avoid that the crate is used to get untracked access to all of the HIR.
  76 #[derive(Clone, Copy)]
  77 struct BodyResolver<'gcx>(&'gcx hir::Crate);
  78
  79 impl<'gcx> BodyResolver<'gcx> {
  80     // Return a reference to the hir::Body with the given BodyId.
  81     // DOES NOT DO ANY TRACKING, use carefully.
  82     fn body(self, id: hir::BodyId) -> &'gcx hir::Body {
  83         self.0.body(id)
  84     }
  85 }
  86
  87 impl<'a> StableHashingContext<'a> {
  88     // The `krate` here is only used for mapping BodyIds to Bodies.
  89     // Don't use it for anything else or you'll run the risk of
  90     // leaking data out of the tracking system.
  91     pub fn new(sess: &'a Session,
  92                krate: &'a hir::Crate,
  93                definitions: &'a Definitions,
  94                cstore: &'a dyn CrateStore)
  95                -> Self {
  96         let hash_spans_initial = !sess.opts.debugging_opts.incremental_ignore_spans;
  97
  98         StableHashingContext {
  99             sess,
 100             body_resolver: BodyResolver(krate),
 101             definitions,
 102             cstore,
 103             caching_source_map: None,
 104             raw_source_map: sess.source_map(),
 105             hash_spans: hash_spans_initial,
 106             hash_bodies: true,
 107             node_id_hashing_mode: NodeIdHashingMode::HashDefPath,
 108             alloc_id_recursion_tracker: Default::default(),
 109         }
 110     }
 111
 112     #[inline]
 113     pub fn sess(&self) -> &'a Session {
 114         self.sess
 115     }
 116
 117     #[inline]
 118     pub fn while_hashing_hir_bodies<F: FnOnce(&mut Self)>(&mut self,
 119                                                           hash_bodies: bool,
 120                                                           f: F) {
 121         let prev_hash_bodies = self.hash_bodies;
 122         self.hash_bodies = hash_bodies;
 123         f(self);
 124         self.hash_bodies = prev_hash_bodies;
 125     }
 126
 127     #[inline]
 128     pub fn while_hashing_spans<F: FnOnce(&mut Self)>(&mut self,
 129                                                      hash_spans: bool,
 130                                                      f: F) {
 131         let prev_hash_spans = self.hash_spans;
 132         self.hash_spans = hash_spans;
 133         f(self);
 134         self.hash_spans = prev_hash_spans;
 135     }
 136
 137     #[inline]
 138     pub fn with_node_id_hashing_mode<F: FnOnce(&mut Self)>(&mut self,
 139                                                            mode: NodeIdHashingMode,
 140                                                            f: F) {
 141         let prev = self.node_id_hashing_mode;
 142         self.node_id_hashing_mode = mode;
 143         f(self);
 144         self.node_id_hashing_mode = prev;
 145     }
 146
 147     #[inline]
 148     pub fn def_path_hash(&self, def_id: DefId) -> DefPathHash {
 149         if def_id.is_local() {
 150             self.definitions.def_path_hash(def_id.index)
 151         } else {
 152             self.cstore.def_path_hash(def_id)
 153         }
 154     }
 155
 156     #[inline]
 157     pub fn local_def_path_hash(&self, def_index: DefIndex) -> DefPathHash {
 158         self.definitions.def_path_hash(def_index)
 159     }
 160
 161     #[inline]
 162     pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
 163         self.definitions.node_to_hir_id(node_id)
 164     }
 165
 166     #[inline]
 167     pub fn hash_bodies(&self) -> bool {
 168         self.hash_bodies
 169     }
 170
 171     #[inline]
 172     pub fn source_map(&mut self) -> &mut CachingSourceMapView<'a> {
 173         match self.caching_source_map {
 174             Some(ref mut cm) => {
 175                 cm
 176             }
 177             ref mut none => {
 178                 *none = Some(CachingSourceMapView::new(self.raw_source_map));
 179                 none.as_mut().unwrap()
 180             }
 181         }
 182     }
 183
 184     #[inline]
 185     pub fn is_ignored_attr(&self, name: Symbol) -> bool {
 186         thread_local! {
 187             static IGNORED_ATTRIBUTES: FxHashSet<Symbol> = compute_ignored_attr_names();
 188         }
 189         IGNORED_ATTRIBUTES.with(|attrs| attrs.contains(&name))
 190     }
 191
 192     pub fn hash_hir_item_like<F: FnOnce(&mut Self)>(&mut self, f: F) {
 193         let prev_hash_node_ids = self.node_id_hashing_mode;
 194         self.node_id_hashing_mode = NodeIdHashingMode::Ignore;
 195
 196         f(self);
 197
 198         self.node_id_hashing_mode = prev_hash_node_ids;
 199     }
 200 }
 201
 202 /// Something that can provide a stable hashing context.
 203 pub trait StableHashingContextProvider<'a> {
 204     fn get_stable_hashing_context(&self) -> StableHashingContext<'a>;
 205 }
 206
 207 impl<'a, 'b, T: StableHashingContextProvider<'a>> StableHashingContextProvider<'a>
 208 for &'b T {
 209     fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
 210         (**self).get_stable_hashing_context()
 211     }
 212 }
 213
 214 impl<'a, 'b, T: StableHashingContextProvider<'a>> StableHashingContextProvider<'a>
 215 for &'b mut T {
 216     fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
 217         (**self).get_stable_hashing_context()
 218     }
 219 }
 220
 221 impl<'a, 'gcx, 'lcx> StableHashingContextProvider<'a> for TyCtxt<'a, 'gcx, 'lcx> {
 222     fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
 223         (*self).create_stable_hashing_context()
 224     }
 225 }
 226
 227 impl<'a> StableHashingContextProvider<'a> for StableHashingContext<'a> {
 228     fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
 229         self.clone()
 230     }
 231 }
 232
 233 impl<'a> ::dep_graph::DepGraphSafe for StableHashingContext<'a> {
 234 }
 235
 236
 237 impl<'a> HashStable<StableHashingContext<'a>> for hir::BodyId {
 238     fn hash_stable<W: StableHasherResult>(&self,
 239                                           hcx: &mut StableHashingContext<'a>,
 240                                           hasher: &mut StableHasher<W>) {
 241         if hcx.hash_bodies() {
 242             hcx.body_resolver.body(*self).hash_stable(hcx, hasher);
 243         }
 244     }
 245 }
 246
 247 impl<'a> HashStable<StableHashingContext<'a>> for hir::HirId {
 248     #[inline]
 249     fn hash_stable<W: StableHasherResult>(&self,
 250                                           hcx: &mut StableHashingContext<'a>,
 251                                           hasher: &mut StableHasher<W>) {
 252         match hcx.node_id_hashing_mode {
 253             NodeIdHashingMode::Ignore => {
 254                 // Don't do anything.
 255             }
 256             NodeIdHashingMode::HashDefPath => {
 257                 let hir::HirId {
 258                     owner,
 259                     local_id,
 260                 } = *self;
 261
 262                 hcx.local_def_path_hash(owner).hash_stable(hcx, hasher);
 263                 local_id.hash_stable(hcx, hasher);
 264             }
 265         }
 266     }
 267 }
 268
 269 impl<'a> ToStableHashKey<StableHashingContext<'a>> for hir::HirId {
 270     type KeyType = (DefPathHash, hir::ItemLocalId);
 271
 272     #[inline]
 273     fn to_stable_hash_key(&self,
 274                           hcx: &StableHashingContext<'a>)
 275                           -> (DefPathHash, hir::ItemLocalId) {
 276         let def_path_hash = hcx.local_def_path_hash(self.owner);
 277         (def_path_hash, self.local_id)
 278     }
 279 }
 280
 281 impl<'a> HashStable<StableHashingContext<'a>> for ast::NodeId {
 282     fn hash_stable<W: StableHasherResult>(&self,
 283                                           hcx: &mut StableHashingContext<'a>,
 284                                           hasher: &mut StableHasher<W>) {
 285         match hcx.node_id_hashing_mode {
 286             NodeIdHashingMode::Ignore => {
 287                 // Don't do anything.
 288             }
 289             NodeIdHashingMode::HashDefPath => {
 290                 hcx.definitions.node_to_hir_id(*self).hash_stable(hcx, hasher);
 291             }
 292         }
 293     }
 294 }
 295
 296 impl<'a> ToStableHashKey<StableHashingContext<'a>> for ast::NodeId {
 297     type KeyType = (DefPathHash, hir::ItemLocalId);
 298
 299     #[inline]
 300     fn to_stable_hash_key(&self,
 301                           hcx: &StableHashingContext<'a>)
 302                           -> (DefPathHash, hir::ItemLocalId) {
 303         hcx.definitions.node_to_hir_id(*self).to_stable_hash_key(hcx)
 304     }
 305 }
 306
 307 impl<'a> HashStable<StableHashingContext<'a>> for Span {
 308
 309     // Hash a span in a stable way. We can't directly hash the span's BytePos
 310     // fields (that would be similar to hashing pointers, since those are just
 311     // offsets into the SourceMap). Instead, we hash the (file name, line, column)
 312     // triple, which stays the same even if the containing SourceFile has moved
 313     // within the SourceMap.
 314     // Also note that we are hashing byte offsets for the column, not unicode
 315     // codepoint offsets. For the purpose of the hash that's sufficient.
 316     // Also, hashing filenames is expensive so we avoid doing it twice when the
 317     // span starts and ends in the same file, which is almost always the case.
 318     fn hash_stable<W: StableHasherResult>(&self,
 319                                           hcx: &mut StableHashingContext<'a>,
 320                                           hasher: &mut StableHasher<W>) {
 321         const TAG_VALID_SPAN: u8 = 0;
 322         const TAG_INVALID_SPAN: u8 = 1;
 323         const TAG_EXPANSION: u8 = 0;
 324         const TAG_NO_EXPANSION: u8 = 1;
 325
 326         if !hcx.hash_spans {
 327             return
 328         }
 329
 330         if *self == DUMMY_SP {
 331             return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
 332         }
 333
 334         // If this is not an empty or invalid span, we want to hash the last
 335         // position that belongs to it, as opposed to hashing the first
 336         // position past it.
 337         let span = self.data();
 338
 339         if span.hi < span.lo {
 340             return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
 341         }
 342
 343         let (file_lo, line_lo, col_lo) = match hcx.source_map()
 344                                                   .byte_pos_to_line_and_col(span.lo) {
 345             Some(pos) => pos,
 346             None => {
 347                 return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
 348             }
 349         };
 350
 351         if !file_lo.contains(span.hi) {
 352             return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
 353         }
 354
 355         std_hash::Hash::hash(&TAG_VALID_SPAN, hasher);
 356         // We truncate the stable_id hash and line and col numbers. The chances
 357         // of causing a collision this way should be minimal.
 358         std_hash::Hash::hash(&(file_lo.name_hash as u64), hasher);
 359
 360         let col = (col_lo.0 as u64) & 0xFF;
 361         let line = ((line_lo as u64) & 0xFF_FF_FF) << 8;
 362         let len = ((span.hi - span.lo).0 as u64) << 32;
 363         let line_col_len = col | line | len;
 364         std_hash::Hash::hash(&line_col_len, hasher);
 365
 366         if span.ctxt == SyntaxContext::empty() {
 367             TAG_NO_EXPANSION.hash_stable(hcx, hasher);
 368         } else {
 369             TAG_EXPANSION.hash_stable(hcx, hasher);
 370
 371             // Since the same expansion context is usually referenced many
 372             // times, we cache a stable hash of it and hash that instead of
 373             // recursing every time.
 374             thread_local! {
 375                 static CACHE: RefCell<FxHashMap<hygiene::Mark, u64>> =
 376                     RefCell::new(FxHashMap());
 377             }
 378
 379             let sub_hash: u64 = CACHE.with(|cache| {
 380                 let mark = span.ctxt.outer();
 381
 382                 if let Some(&sub_hash) = cache.borrow().get(&mark) {
 383                     return sub_hash;
 384                 }
 385
 386                 let mut hasher = StableHasher::new();
 387                 mark.expn_info().hash_stable(hcx, &mut hasher);
 388                 let sub_hash: Fingerprint = hasher.finish();
 389                 let sub_hash = sub_hash.to_smaller_hash();
 390                 cache.borrow_mut().insert(mark, sub_hash);
 391                 sub_hash
 392             });
 393
 394             sub_hash.hash_stable(hcx, hasher);
 395         }
 396     }
 397 }
 398
 399 pub fn hash_stable_trait_impls<'a, 'gcx, W, R>(
 400     hcx: &mut StableHashingContext<'a>,
 401     hasher: &mut StableHasher<W>,
 402     blanket_impls: &[DefId],
 403     non_blanket_impls: &HashMap<fast_reject::SimplifiedType, Vec<DefId>, R>)
 404     where W: StableHasherResult,
 405           R: std_hash::BuildHasher,
 406 {
 407     {
 408         let mut blanket_impls: SmallVec<[_; 8]> = blanket_impls
 409             .iter()
 410             .map(|&def_id| hcx.def_path_hash(def_id))
 411             .collect();
 412
 413         if blanket_impls.len() > 1 {
 414             blanket_impls.sort_unstable();
 415         }
 416
 417         blanket_impls.hash_stable(hcx, hasher);
 418     }
 419
 420     {
 421         let mut keys: SmallVec<[_; 8]> =
 422             non_blanket_impls.keys()
 423                              .map(|k| (k, k.map_def(|d| hcx.def_path_hash(d))))
 424                              .collect();
 425         keys.sort_unstable_by(|&(_, ref k1), &(_, ref k2)| k1.cmp(k2));
 426         keys.len().hash_stable(hcx, hasher);
 427         for (key, ref stable_key) in keys {
 428             stable_key.hash_stable(hcx, hasher);
 429             let mut impls : SmallVec<[_; 8]> = non_blanket_impls[key]
 430                 .iter()
 431                 .map(|&impl_id| hcx.def_path_hash(impl_id))
 432                 .collect();
 433
 434             if impls.len() > 1 {
 435                 impls.sort_unstable();
 436             }
 437
 438             impls.hash_stable(hcx, hasher);
 439         }
 440     }
 441 }
 442