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;
  13 use hir::map::DefPathHash;
  14 use ich::{self, CachingCodemapView};
  15 use session::config::DebugInfoLevel::NoDebugInfo;
  16 use ty;
  17 use util::nodemap::{NodeMap, ItemLocalMap};
  18
  19 use std::hash as std_hash;
  20 use std::collections::{HashMap, HashSet, BTreeMap};
  21
  22 use syntax::ast;
  23 use syntax::attr;
  24 use syntax::ext::hygiene::SyntaxContext;
  25 use syntax::symbol::Symbol;
  26 use syntax_pos::Span;
  27
  28 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
  29                                            StableHasherResult};
  30 use rustc_data_structures::accumulate_vec::AccumulateVec;
  31
  32 /// This is the context state available during incr. comp. hashing. It contains
  33 /// enough information to transform DefIds and HirIds into stable DefPaths (i.e.
  34 /// a reference to the TyCtxt) and it holds a few caches for speeding up various
  35 /// things (e.g. each DefId/DefPath is only hashed once).
  36 pub struct StableHashingContext<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  37     tcx: ty::TyCtxt<'a, 'gcx, 'tcx>,
  38     codemap: CachingCodemapView<'gcx>,
  39     hash_spans: bool,
  40     hash_bodies: bool,
  41     overflow_checks_enabled: bool,
  42     node_id_hashing_mode: NodeIdHashingMode,
  43     // A sorted array of symbol keys for fast lookup.
  44     ignored_attr_names: Vec<Symbol>,
  45 }
  46
  47 #[derive(PartialEq, Eq, Clone, Copy)]
  48 pub enum NodeIdHashingMode {
  49     Ignore,
  50     HashDefPath,
  51     HashTraitsInScope,
  52 }
  53
  54 impl<'a, 'gcx, 'tcx> StableHashingContext<'a, 'gcx, 'tcx> {
  55
  56     pub fn new(tcx: ty::TyCtxt<'a, 'gcx, 'tcx>) -> Self {
  57         let hash_spans_initial = tcx.sess.opts.debuginfo != NoDebugInfo;
  58         let check_overflow_initial = tcx.sess.overflow_checks();
  59
  60         let mut ignored_attr_names: Vec<_> = ich::IGNORED_ATTRIBUTES
  61             .iter()
  62             .map(|&s| Symbol::intern(s))
  63             .collect();
  64
  65         ignored_attr_names.sort();
  66
  67         StableHashingContext {
  68             tcx,
  69             codemap: CachingCodemapView::new(tcx),
  70             hash_spans: hash_spans_initial,
  71             hash_bodies: true,
  72             overflow_checks_enabled: check_overflow_initial,
  73             node_id_hashing_mode: NodeIdHashingMode::HashDefPath,
  74             ignored_attr_names,
  75         }
  76     }
  77
  78     pub fn force_span_hashing(mut self) -> Self {
  79         self.hash_spans = true;
  80         self
  81     }
  82
  83     #[inline]
  84     pub fn while_hashing_hir_bodies<F: FnOnce(&mut Self)>(&mut self,
  85                                                           hash_bodies: bool,
  86                                                           f: F) {
  87         let prev_hash_bodies = self.hash_bodies;
  88         self.hash_bodies = hash_bodies;
  89         f(self);
  90         self.hash_bodies = prev_hash_bodies;
  91     }
  92
  93     #[inline]
  94     pub fn while_hashing_spans<F: FnOnce(&mut Self)>(&mut self,
  95                                                      hash_spans: bool,
  96                                                      f: F) {
  97         let prev_hash_spans = self.hash_spans;
  98         self.hash_spans = hash_spans;
  99         f(self);
 100         self.hash_spans = prev_hash_spans;
 101     }
 102
 103     #[inline]
 104     pub fn with_node_id_hashing_mode<F: FnOnce(&mut Self)>(&mut self,
 105                                                            mode: NodeIdHashingMode,
 106                                                            f: F) {
 107         let prev = self.node_id_hashing_mode;
 108         self.node_id_hashing_mode = mode;
 109         f(self);
 110         self.node_id_hashing_mode = prev;
 111     }
 112
 113     #[inline]
 114     pub fn tcx(&self) -> ty::TyCtxt<'a, 'gcx, 'tcx> {
 115         self.tcx
 116     }
 117
 118     #[inline]
 119     pub fn def_path_hash(&mut self, def_id: DefId) -> DefPathHash {
 120         self.tcx.def_path_hash(def_id)
 121     }
 122
 123     #[inline]
 124     pub fn hash_spans(&self) -> bool {
 125         self.hash_spans
 126     }
 127
 128     #[inline]
 129     pub fn hash_bodies(&self) -> bool {
 130         self.hash_bodies
 131     }
 132
 133     #[inline]
 134     pub fn codemap(&mut self) -> &mut CachingCodemapView<'gcx> {
 135         &mut self.codemap
 136     }
 137
 138     #[inline]
 139     pub fn is_ignored_attr(&self, name: Symbol) -> bool {
 140         self.ignored_attr_names.binary_search(&name).is_ok()
 141     }
 142
 143     pub fn hash_hir_item_like<F: FnOnce(&mut Self)>(&mut self,
 144                                                     item_attrs: &[ast::Attribute],
 145                                                     f: F) {
 146         let prev_overflow_checks = self.overflow_checks_enabled;
 147         if attr::contains_name(item_attrs, "rustc_inherit_overflow_checks") {
 148             self.overflow_checks_enabled = true;
 149         }
 150         let prev_hash_node_ids = self.node_id_hashing_mode;
 151         self.node_id_hashing_mode = NodeIdHashingMode::Ignore;
 152
 153         f(self);
 154
 155         self.node_id_hashing_mode = prev_hash_node_ids;
 156         self.overflow_checks_enabled = prev_overflow_checks;
 157     }
 158
 159     #[inline]
 160     pub fn binop_can_panic_at_runtime(&self, binop: hir::BinOp_) -> bool
 161     {
 162         match binop {
 163             hir::BiAdd |
 164             hir::BiSub |
 165             hir::BiMul => self.overflow_checks_enabled,
 166
 167             hir::BiDiv |
 168             hir::BiRem => true,
 169
 170             hir::BiAnd |
 171             hir::BiOr |
 172             hir::BiBitXor |
 173             hir::BiBitAnd |
 174             hir::BiBitOr |
 175             hir::BiShl |
 176             hir::BiShr |
 177             hir::BiEq |
 178             hir::BiLt |
 179             hir::BiLe |
 180             hir::BiNe |
 181             hir::BiGe |
 182             hir::BiGt => false
 183         }
 184     }
 185
 186     #[inline]
 187     pub fn unop_can_panic_at_runtime(&self, unop: hir::UnOp) -> bool
 188     {
 189         match unop {
 190             hir::UnDeref |
 191             hir::UnNot => false,
 192             hir::UnNeg => self.overflow_checks_enabled,
 193         }
 194     }
 195 }
 196
 197
 198 impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ast::NodeId {
 199     fn hash_stable<W: StableHasherResult>(&self,
 200                                           hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 201                                           hasher: &mut StableHasher<W>) {
 202         match hcx.node_id_hashing_mode {
 203             NodeIdHashingMode::Ignore => {
 204                 // Most NodeIds in the HIR can be ignored, but if there is a
 205                 // corresponding entry in the `trait_map` we need to hash that.
 206                 // Make sure we don't ignore too much by checking that there is
 207                 // no entry in a debug_assert!().
 208                 debug_assert!(hcx.tcx.trait_map.get(self).is_none());
 209             }
 210             NodeIdHashingMode::HashDefPath => {
 211                 hcx.tcx.hir.definitions().node_to_hir_id(*self).hash_stable(hcx, hasher);
 212             }
 213             NodeIdHashingMode::HashTraitsInScope => {
 214                 if let Some(traits) = hcx.tcx.trait_map.get(self) {
 215                     // The ordering of the candidates is not fixed. So we hash
 216                     // the def-ids and then sort them and hash the collection.
 217                     let mut candidates: AccumulateVec<[_; 8]> =
 218                         traits.iter()
 219                               .map(|&hir::TraitCandidate { def_id, import_id: _ }| {
 220                                   hcx.def_path_hash(def_id)
 221                               })
 222                               .collect();
 223                     if traits.len() > 1 {
 224                         candidates.sort();
 225                     }
 226                     candidates.hash_stable(hcx, hasher);
 227                 }
 228             }
 229         }
 230     }
 231 }
 232
 233 impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for Span {
 234
 235     // Hash a span in a stable way. We can't directly hash the span's BytePos
 236     // fields (that would be similar to hashing pointers, since those are just
 237     // offsets into the CodeMap). Instead, we hash the (file name, line, column)
 238     // triple, which stays the same even if the containing FileMap has moved
 239     // within the CodeMap.
 240     // Also note that we are hashing byte offsets for the column, not unicode
 241     // codepoint offsets. For the purpose of the hash that's sufficient.
 242     // Also, hashing filenames is expensive so we avoid doing it twice when the
 243     // span starts and ends in the same file, which is almost always the case.
 244     fn hash_stable<W: StableHasherResult>(&self,
 245                                           hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 246                                           hasher: &mut StableHasher<W>) {
 247         use syntax_pos::Pos;
 248
 249         if !hcx.hash_spans {
 250             return
 251         }
 252
 253         // If this is not an empty or invalid span, we want to hash the last
 254         // position that belongs to it, as opposed to hashing the first
 255         // position past it.
 256         let span_hi = if self.hi() > self.lo() {
 257             // We might end up in the middle of a multibyte character here,
 258             // but that's OK, since we are not trying to decode anything at
 259             // this position.
 260             self.hi() - ::syntax_pos::BytePos(1)
 261         } else {
 262             self.hi()
 263         };
 264
 265         {
 266             let loc1 = hcx.codemap().byte_pos_to_line_and_col(self.lo());
 267             let loc1 = loc1.as_ref()
 268                            .map(|&(ref fm, line, col)| (&fm.name[..], line, col.to_usize()))
 269                            .unwrap_or(("???", 0, 0));
 270
 271             let loc2 = hcx.codemap().byte_pos_to_line_and_col(span_hi);
 272             let loc2 = loc2.as_ref()
 273                            .map(|&(ref fm, line, col)| (&fm.name[..], line, col.to_usize()))
 274                            .unwrap_or(("???", 0, 0));
 275
 276             if loc1.0 == loc2.0 {
 277                 std_hash::Hash::hash(&0u8, hasher);
 278
 279                 std_hash::Hash::hash(loc1.0, hasher);
 280                 std_hash::Hash::hash(&loc1.1, hasher);
 281                 std_hash::Hash::hash(&loc1.2, hasher);
 282
 283                 // Do not hash the file name twice
 284                 std_hash::Hash::hash(&loc2.1, hasher);
 285                 std_hash::Hash::hash(&loc2.2, hasher);
 286             } else {
 287                 std_hash::Hash::hash(&1u8, hasher);
 288
 289                 std_hash::Hash::hash(loc1.0, hasher);
 290                 std_hash::Hash::hash(&loc1.1, hasher);
 291                 std_hash::Hash::hash(&loc1.2, hasher);
 292
 293                 std_hash::Hash::hash(loc2.0, hasher);
 294                 std_hash::Hash::hash(&loc2.1, hasher);
 295                 std_hash::Hash::hash(&loc2.2, hasher);
 296             }
 297         }
 298
 299         if self.ctxt() == SyntaxContext::empty() {
 300             0u8.hash_stable(hcx, hasher);
 301         } else {
 302             1u8.hash_stable(hcx, hasher);
 303             self.source_callsite().hash_stable(hcx, hasher);
 304         }
 305     }
 306 }
 307
 308 pub fn hash_stable_hashmap<'a, 'gcx, 'tcx, K, V, R, SK, F, W>(
 309     hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 310     hasher: &mut StableHasher<W>,
 311     map: &HashMap<K, V, R>,
 312     extract_stable_key: F)
 313     where K: Eq + std_hash::Hash,
 314           V: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
 315           R: std_hash::BuildHasher,
 316           SK: HashStable<StableHashingContext<'a, 'gcx, 'tcx>> + Ord + Clone,
 317           F: Fn(&mut StableHashingContext<'a, 'gcx, 'tcx>, &K) -> SK,
 318           W: StableHasherResult,
 319 {
 320     let mut keys: Vec<_> = map.keys()
 321                               .map(|k| (extract_stable_key(hcx, k), k))
 322                               .collect();
 323     keys.sort_unstable_by_key(|&(ref stable_key, _)| stable_key.clone());
 324     keys.len().hash_stable(hcx, hasher);
 325     for (stable_key, key) in keys {
 326         stable_key.hash_stable(hcx, hasher);
 327         map[key].hash_stable(hcx, hasher);
 328     }
 329 }
 330
 331 pub fn hash_stable_hashset<'a, 'tcx, 'gcx, K, R, SK, F, W>(
 332     hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 333     hasher: &mut StableHasher<W>,
 334     set: &HashSet<K, R>,
 335     extract_stable_key: F)
 336     where K: Eq + std_hash::Hash,
 337           R: std_hash::BuildHasher,
 338           SK: HashStable<StableHashingContext<'a, 'gcx, 'tcx>> + Ord + Clone,
 339           F: Fn(&mut StableHashingContext<'a, 'gcx, 'tcx>, &K) -> SK,
 340           W: StableHasherResult,
 341 {
 342     let mut keys: Vec<_> = set.iter()
 343                               .map(|k| extract_stable_key(hcx, k))
 344                               .collect();
 345     keys.sort_unstable();
 346     keys.hash_stable(hcx, hasher);
 347 }
 348
 349 pub fn hash_stable_nodemap<'a, 'tcx, 'gcx, V, W>(
 350     hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 351     hasher: &mut StableHasher<W>,
 352     map: &NodeMap<V>)
 353     where V: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
 354           W: StableHasherResult,
 355 {
 356     hash_stable_hashmap(hcx, hasher, map, |hcx, node_id| {
 357         hcx.tcx.hir.definitions().node_to_hir_id(*node_id).local_id
 358     });
 359 }
 360
 361 pub fn hash_stable_itemlocalmap<'a, 'tcx, 'gcx, V, W>(
 362     hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 363     hasher: &mut StableHasher<W>,
 364     map: &ItemLocalMap<V>)
 365     where V: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
 366           W: StableHasherResult,
 367 {
 368     hash_stable_hashmap(hcx, hasher, map, |_, local_id| {
 369         *local_id
 370     });
 371 }
 372
 373
 374 pub fn hash_stable_btreemap<'a, 'tcx, 'gcx, K, V, SK, F, W>(
 375     hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
 376     hasher: &mut StableHasher<W>,
 377     map: &BTreeMap<K, V>,
 378     extract_stable_key: F)
 379     where K: Eq + Ord,
 380           V: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
 381           SK: HashStable<StableHashingContext<'a, 'gcx, 'tcx>> + Ord + Clone,
 382           F: Fn(&mut StableHashingContext<'a, 'gcx, 'tcx>, &K) -> SK,
 383           W: StableHasherResult,
 384 {
 385     let mut keys: Vec<_> = map.keys()
 386                               .map(|k| (extract_stable_key(hcx, k), k))
 387                               .collect();
 388     keys.sort_unstable_by_key(|&(ref stable_key, _)| stable_key.clone());
 389     keys.len().hash_stable(hcx, hasher);
 390     for (stable_key, key) in keys {
 391         stable_key.hash_stable(hcx, hasher);
 392         map[key].hash_stable(hcx, hasher);
 393     }
 394 }