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.
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.
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};
21 use std::hash as std_hash;
22 use std::collections::HashMap;
23 use std::cell::RefCell;
27 use syntax::source_map::SourceMap;
28 use syntax::ext::hygiene::SyntaxContext;
29 use syntax::symbol::Symbol;
30 use syntax::tokenstream::DelimSpan;
31 use syntax_pos::{Span, DUMMY_SP};
32 use syntax_pos::hygiene;
34 use rustc_data_structures::stable_hasher::{HashStable,
35 StableHasher, StableHasherResult,
37 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
38 use smallvec::SmallVec;
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()
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).
50 pub struct StableHashingContext<'a> {
52 definitions: &'a Definitions,
53 cstore: &'a dyn CrateStore,
54 body_resolver: BodyResolver<'a>,
57 node_id_hashing_mode: NodeIdHashingMode,
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>>,
65 #[derive(PartialEq, Eq, Clone, Copy)]
66 pub enum NodeIdHashingMode {
71 /// The BodyResolver allows to map a BodyId to the corresponding hir::Body.
72 /// We could also just store a plain reference to the hir::Crate but we want
73 /// to avoid that the crate is used to get untracked access to all of the HIR.
74 #[derive(Clone, Copy)]
75 struct BodyResolver<'gcx>(&'gcx hir::Crate);
77 impl<'gcx> BodyResolver<'gcx> {
78 // Return a reference to the hir::Body with the given BodyId.
79 // DOES NOT DO ANY TRACKING, use carefully.
80 fn body(self, id: hir::BodyId) -> &'gcx hir::Body {
85 impl<'a> StableHashingContext<'a> {
86 // The `krate` here is only used for mapping BodyIds to Bodies.
87 // Don't use it for anything else or you'll run the risk of
88 // leaking data out of the tracking system.
89 pub fn new(sess: &'a Session,
90 krate: &'a hir::Crate,
91 definitions: &'a Definitions,
92 cstore: &'a dyn CrateStore)
94 let hash_spans_initial = !sess.opts.debugging_opts.incremental_ignore_spans;
96 StableHashingContext {
98 body_resolver: BodyResolver(krate),
101 caching_source_map: None,
102 raw_source_map: sess.source_map(),
103 hash_spans: hash_spans_initial,
105 node_id_hashing_mode: NodeIdHashingMode::HashDefPath,
110 pub fn sess(&self) -> &'a Session {
115 pub fn while_hashing_hir_bodies<F: FnOnce(&mut Self)>(&mut self,
118 let prev_hash_bodies = self.hash_bodies;
119 self.hash_bodies = hash_bodies;
121 self.hash_bodies = prev_hash_bodies;
125 pub fn while_hashing_spans<F: FnOnce(&mut Self)>(&mut self,
128 let prev_hash_spans = self.hash_spans;
129 self.hash_spans = hash_spans;
131 self.hash_spans = prev_hash_spans;
135 pub fn with_node_id_hashing_mode<F: FnOnce(&mut Self)>(&mut self,
136 mode: NodeIdHashingMode,
138 let prev = self.node_id_hashing_mode;
139 self.node_id_hashing_mode = mode;
141 self.node_id_hashing_mode = prev;
145 pub fn def_path_hash(&self, def_id: DefId) -> DefPathHash {
146 if def_id.is_local() {
147 self.definitions.def_path_hash(def_id.index)
149 self.cstore.def_path_hash(def_id)
154 pub fn local_def_path_hash(&self, def_index: DefIndex) -> DefPathHash {
155 self.definitions.def_path_hash(def_index)
159 pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
160 self.definitions.node_to_hir_id(node_id)
164 pub fn hash_bodies(&self) -> bool {
169 pub fn source_map(&mut self) -> &mut CachingSourceMapView<'a> {
170 match self.caching_source_map {
171 Some(ref mut cm) => {
175 *none = Some(CachingSourceMapView::new(self.raw_source_map));
176 none.as_mut().unwrap()
182 pub fn is_ignored_attr(&self, name: Symbol) -> bool {
184 static IGNORED_ATTRIBUTES: FxHashSet<Symbol> = compute_ignored_attr_names();
186 IGNORED_ATTRIBUTES.with(|attrs| attrs.contains(&name))
189 pub fn hash_hir_item_like<F: FnOnce(&mut Self)>(&mut self, f: F) {
190 let prev_hash_node_ids = self.node_id_hashing_mode;
191 self.node_id_hashing_mode = NodeIdHashingMode::Ignore;
195 self.node_id_hashing_mode = prev_hash_node_ids;
199 /// Something that can provide a stable hashing context.
200 pub trait StableHashingContextProvider<'a> {
201 fn get_stable_hashing_context(&self) -> StableHashingContext<'a>;
204 impl<'a, 'b, T: StableHashingContextProvider<'a>> StableHashingContextProvider<'a>
206 fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
207 (**self).get_stable_hashing_context()
211 impl<'a, 'b, T: StableHashingContextProvider<'a>> StableHashingContextProvider<'a>
213 fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
214 (**self).get_stable_hashing_context()
218 impl<'a, 'gcx, 'lcx> StableHashingContextProvider<'a> for TyCtxt<'a, 'gcx, 'lcx> {
219 fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
220 (*self).create_stable_hashing_context()
224 impl<'a> StableHashingContextProvider<'a> for StableHashingContext<'a> {
225 fn get_stable_hashing_context(&self) -> StableHashingContext<'a> {
230 impl<'a> ::dep_graph::DepGraphSafe for StableHashingContext<'a> {
234 impl<'a> HashStable<StableHashingContext<'a>> for hir::BodyId {
235 fn hash_stable<W: StableHasherResult>(&self,
236 hcx: &mut StableHashingContext<'a>,
237 hasher: &mut StableHasher<W>) {
238 if hcx.hash_bodies() {
239 hcx.body_resolver.body(*self).hash_stable(hcx, hasher);
244 impl<'a> HashStable<StableHashingContext<'a>> for hir::HirId {
246 fn hash_stable<W: StableHasherResult>(&self,
247 hcx: &mut StableHashingContext<'a>,
248 hasher: &mut StableHasher<W>) {
249 match hcx.node_id_hashing_mode {
250 NodeIdHashingMode::Ignore => {
251 // Don't do anything.
253 NodeIdHashingMode::HashDefPath => {
259 hcx.local_def_path_hash(owner).hash_stable(hcx, hasher);
260 local_id.hash_stable(hcx, hasher);
266 impl<'a> ToStableHashKey<StableHashingContext<'a>> for hir::HirId {
267 type KeyType = (DefPathHash, hir::ItemLocalId);
270 fn to_stable_hash_key(&self,
271 hcx: &StableHashingContext<'a>)
272 -> (DefPathHash, hir::ItemLocalId) {
273 let def_path_hash = hcx.local_def_path_hash(self.owner);
274 (def_path_hash, self.local_id)
278 impl<'a> HashStable<StableHashingContext<'a>> for ast::NodeId {
279 fn hash_stable<W: StableHasherResult>(&self,
280 hcx: &mut StableHashingContext<'a>,
281 hasher: &mut StableHasher<W>) {
282 match hcx.node_id_hashing_mode {
283 NodeIdHashingMode::Ignore => {
284 // Don't do anything.
286 NodeIdHashingMode::HashDefPath => {
287 hcx.definitions.node_to_hir_id(*self).hash_stable(hcx, hasher);
293 impl<'a> ToStableHashKey<StableHashingContext<'a>> for ast::NodeId {
294 type KeyType = (DefPathHash, hir::ItemLocalId);
297 fn to_stable_hash_key(&self,
298 hcx: &StableHashingContext<'a>)
299 -> (DefPathHash, hir::ItemLocalId) {
300 hcx.definitions.node_to_hir_id(*self).to_stable_hash_key(hcx)
304 impl<'a> HashStable<StableHashingContext<'a>> for Span {
306 // Hash a span in a stable way. We can't directly hash the span's BytePos
307 // fields (that would be similar to hashing pointers, since those are just
308 // offsets into the SourceMap). Instead, we hash the (file name, line, column)
309 // triple, which stays the same even if the containing SourceFile has moved
310 // within the SourceMap.
311 // Also note that we are hashing byte offsets for the column, not unicode
312 // codepoint offsets. For the purpose of the hash that's sufficient.
313 // Also, hashing filenames is expensive so we avoid doing it twice when the
314 // span starts and ends in the same file, which is almost always the case.
315 fn hash_stable<W: StableHasherResult>(&self,
316 hcx: &mut StableHashingContext<'a>,
317 hasher: &mut StableHasher<W>) {
318 const TAG_VALID_SPAN: u8 = 0;
319 const TAG_INVALID_SPAN: u8 = 1;
320 const TAG_EXPANSION: u8 = 0;
321 const TAG_NO_EXPANSION: u8 = 1;
327 if *self == DUMMY_SP {
328 return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
331 // If this is not an empty or invalid span, we want to hash the last
332 // position that belongs to it, as opposed to hashing the first
334 let span = self.data();
336 if span.hi < span.lo {
337 return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
340 let (file_lo, line_lo, col_lo) = match hcx.source_map()
341 .byte_pos_to_line_and_col(span.lo) {
344 return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
348 if !file_lo.contains(span.hi) {
349 return std_hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
352 std_hash::Hash::hash(&TAG_VALID_SPAN, hasher);
353 // We truncate the stable_id hash and line and col numbers. The chances
354 // of causing a collision this way should be minimal.
355 std_hash::Hash::hash(&(file_lo.name_hash as u64), hasher);
357 let col = (col_lo.0 as u64) & 0xFF;
358 let line = ((line_lo as u64) & 0xFF_FF_FF) << 8;
359 let len = ((span.hi - span.lo).0 as u64) << 32;
360 let line_col_len = col | line | len;
361 std_hash::Hash::hash(&line_col_len, hasher);
363 if span.ctxt == SyntaxContext::empty() {
364 TAG_NO_EXPANSION.hash_stable(hcx, hasher);
366 TAG_EXPANSION.hash_stable(hcx, hasher);
368 // Since the same expansion context is usually referenced many
369 // times, we cache a stable hash of it and hash that instead of
370 // recursing every time.
372 static CACHE: RefCell<FxHashMap<hygiene::Mark, u64>> = Default::default();
375 let sub_hash: u64 = CACHE.with(|cache| {
376 let mark = span.ctxt.outer();
378 if let Some(&sub_hash) = cache.borrow().get(&mark) {
382 let mut hasher = StableHasher::new();
383 mark.expn_info().hash_stable(hcx, &mut hasher);
384 let sub_hash: Fingerprint = hasher.finish();
385 let sub_hash = sub_hash.to_smaller_hash();
386 cache.borrow_mut().insert(mark, sub_hash);
390 sub_hash.hash_stable(hcx, hasher);
395 impl<'a> HashStable<StableHashingContext<'a>> for DelimSpan {
396 fn hash_stable<W: StableHasherResult>(
398 hcx: &mut StableHashingContext<'a>,
399 hasher: &mut StableHasher<W>,
401 self.open.hash_stable(hcx, hasher);
402 self.close.hash_stable(hcx, hasher);
406 pub fn hash_stable_trait_impls<'a, 'gcx, W, R>(
407 hcx: &mut StableHashingContext<'a>,
408 hasher: &mut StableHasher<W>,
409 blanket_impls: &[DefId],
410 non_blanket_impls: &HashMap<fast_reject::SimplifiedType, Vec<DefId>, R>)
411 where W: StableHasherResult,
412 R: std_hash::BuildHasher,
415 let mut blanket_impls: SmallVec<[_; 8]> = blanket_impls
417 .map(|&def_id| hcx.def_path_hash(def_id))
420 if blanket_impls.len() > 1 {
421 blanket_impls.sort_unstable();
424 blanket_impls.hash_stable(hcx, hasher);
428 let mut keys: SmallVec<[_; 8]> =
429 non_blanket_impls.keys()
430 .map(|k| (k, k.map_def(|d| hcx.def_path_hash(d))))
432 keys.sort_unstable_by(|&(_, ref k1), &(_, ref k2)| k1.cmp(k2));
433 keys.len().hash_stable(hcx, hasher);
434 for (key, ref stable_key) in keys {
435 stable_key.hash_stable(hcx, hasher);
436 let mut impls : SmallVec<[_; 8]> = non_blanket_impls[key]
438 .map(|&impl_id| hcx.def_path_hash(impl_id))
442 impls.sort_unstable();
445 impls.hash_stable(hcx, hasher);