src/librustc/dep_graph/dep_node.rs

   1 // Copyright 2014 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
  12 //! This module defines the `DepNode` type which the compiler uses to represent
  13 //! nodes in the dependency graph. A `DepNode` consists of a `DepKind` (which
  14 //! specifies the kind of thing it represents, like a piece of HIR, MIR, etc)
  15 //! and a `Fingerprint`, a 128 bit hash value the exact meaning of which
  16 //! depends on the node's `DepKind`. Together, the kind and the fingerprint
  17 //! fully identify a dependency node, even across multiple compilation sessions.
  18 //! In other words, the value of the fingerprint does not depend on anything
  19 //! that is specific to a given compilation session, like an unpredictable
  20 //! interning key (e.g. NodeId, DefId, Symbol) or the numeric value of a
  21 //! pointer. The concept behind this could be compared to how git commit hashes
  22 //! uniquely identify a given commit and has a few advantages:
  23 //!
  24 //! * A `DepNode` can simply be serialized to disk and loaded in another session
  25 //!   without the need to do any "rebasing (like we have to do for Spans and
  26 //!   NodeIds) or "retracing" like we had to do for `DefId` in earlier
  27 //!   implementations of the dependency graph.
  28 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
  29 //!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
  30 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
  31 //!   memory without any post-processing (e.g. "abomination-style" pointer
  32 //!   reconstruction).
  33 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
  34 //!   refer to things that do not exist anymore. In previous implementations
  35 //!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
  36 //!   had been removed between the previous and the current compilation session
  37 //!   could not be instantiated because the current compilation session
  38 //!   contained no `DefId` for thing that had been removed.
  39 //!
  40 //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
  41 //! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
  42 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
  43 //! runtime in order to construct a valid `DepNode` fingerprint.
  44 //!
  45 //! Because the macro sees what parameters a given `DepKind` requires, it can
  46 //! "infer" some properties for each kind of `DepNode`:
  47 //!
  48 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
  49 //!   `DepNode`s, like `Krate`, represent global concepts with only one value.
  50 //! * Whether it is possible, in principle, to reconstruct a query key from a
  51 //!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
  52 //!   in which case it is possible to map the node's fingerprint back to the
  53 //!   `DefId` it was computed from. In other cases, too much information gets
  54 //!   lost during fingerprint computation.
  55 //!
  56 //! The `DepConstructor` enum, together with `DepNode::new()` ensures that only
  57 //! valid `DepNode` instances can be constructed. For example, the API does not
  58 //! allow for constructing parameterless `DepNode`s with anything other
  59 //! than a zeroed out fingerprint. More generally speaking, it relieves the
  60 //! user of the `DepNode` API of having to know how to compute the expected
  61 //! fingerprint for a given set of node parameters.
  62
  63 use mir::interpret::GlobalId;
  64 use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX};
  65 use hir::map::DefPathHash;
  66 use hir::{HirId, ItemLocalId};
  67
  68 use ich::{Fingerprint, StableHashingContext};
  69 use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
  70 use std::fmt;
  71 use std::hash::Hash;
  72 use syntax_pos::symbol::InternedString;
  73 use traits::query::{
  74     CanonicalProjectionGoal, CanonicalTyGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpSubtypeGoal,
  75     CanonicalPredicateGoal, CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpNormalizeGoal,
  76 };
  77 use ty::{TyCtxt, FnSig, Instance, InstanceDef,
  78          ParamEnv, ParamEnvAnd, Predicate, PolyFnSig, PolyTraitRef, Ty};
  79 use ty::subst::Substs;
  80
  81 // erase!() just makes tokens go away. It's used to specify which macro argument
  82 // is repeated (i.e. which sub-expression of the macro we are in) but don't need
  83 // to actually use any of the arguments.
  84 macro_rules! erase {
  85     ($x:tt) => ({})
  86 }
  87
  88 macro_rules! replace {
  89     ($x:tt with $($y:tt)*) => ($($y)*)
  90 }
  91
  92 macro_rules! is_anon_attr {
  93     (anon) => (true);
  94     ($attr:ident) => (false);
  95 }
  96
  97 macro_rules! is_input_attr {
  98     (input) => (true);
  99     ($attr:ident) => (false);
 100 }
 101
 102 macro_rules! is_eval_always_attr {
 103     (eval_always) => (true);
 104     ($attr:ident) => (false);
 105 }
 106
 107 macro_rules! contains_anon_attr {
 108     ($($attr:ident),*) => ({$(is_anon_attr!($attr) | )* false});
 109 }
 110
 111 macro_rules! contains_input_attr {
 112     ($($attr:ident),*) => ({$(is_input_attr!($attr) | )* false});
 113 }
 114
 115 macro_rules! contains_eval_always_attr {
 116     ($($attr:ident),*) => ({$(is_eval_always_attr!($attr) | )* false});
 117 }
 118
 119 macro_rules! define_dep_nodes {
 120     (<$tcx:tt>
 121     $(
 122         [$($attr:ident),* ]
 123         $variant:ident $(( $tuple_arg_ty:ty $(,)* ))*
 124                        $({ $($struct_arg_name:ident : $struct_arg_ty:ty),* })*
 125       ,)*
 126     ) => (
 127         #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
 128                  RustcEncodable, RustcDecodable)]
 129         pub enum DepKind {
 130             $($variant),*
 131         }
 132
 133         impl DepKind {
 134             #[allow(unreachable_code)]
 135             #[inline]
 136             pub fn can_reconstruct_query_key<$tcx>(&self) -> bool {
 137                 match *self {
 138                     $(
 139                         DepKind :: $variant => {
 140                             if contains_anon_attr!($($attr),*) {
 141                                 return false;
 142                             }
 143
 144                             // tuple args
 145                             $({
 146                                 return <$tuple_arg_ty as DepNodeParams>
 147                                     ::CAN_RECONSTRUCT_QUERY_KEY;
 148                             })*
 149
 150                             // struct args
 151                             $({
 152
 153                                 return <( $($struct_arg_ty,)* ) as DepNodeParams>
 154                                     ::CAN_RECONSTRUCT_QUERY_KEY;
 155                             })*
 156
 157                             true
 158                         }
 159                     )*
 160                 }
 161             }
 162
 163             #[inline]
 164             pub fn is_anon(&self) -> bool {
 165                 match *self {
 166                     $(
 167                         DepKind :: $variant => { contains_anon_attr!($($attr),*) }
 168                     )*
 169                 }
 170             }
 171
 172             #[inline]
 173             pub fn is_input(&self) -> bool {
 174                 match *self {
 175                     $(
 176                         DepKind :: $variant => { contains_input_attr!($($attr),*) }
 177                     )*
 178                 }
 179             }
 180
 181             #[inline]
 182             pub fn is_eval_always(&self) -> bool {
 183                 match *self {
 184                     $(
 185                         DepKind :: $variant => { contains_eval_always_attr!($($attr), *) }
 186                     )*
 187                 }
 188             }
 189
 190             #[allow(unreachable_code)]
 191             #[inline]
 192             pub fn has_params(&self) -> bool {
 193                 match *self {
 194                     $(
 195                         DepKind :: $variant => {
 196                             // tuple args
 197                             $({
 198                                 erase!($tuple_arg_ty);
 199                                 return true;
 200                             })*
 201
 202                             // struct args
 203                             $({
 204                                 $(erase!($struct_arg_name);)*
 205                                 return true;
 206                             })*
 207
 208                             false
 209                         }
 210                     )*
 211                 }
 212             }
 213         }
 214
 215         pub enum DepConstructor<$tcx> {
 216             $(
 217                 $variant $(( $tuple_arg_ty ))*
 218                          $({ $($struct_arg_name : $struct_arg_ty),* })*
 219             ),*
 220         }
 221
 222         #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash,
 223                  RustcEncodable, RustcDecodable)]
 224         pub struct DepNode {
 225             pub kind: DepKind,
 226             pub hash: Fingerprint,
 227         }
 228
 229         impl DepNode {
 230             #[allow(unreachable_code, non_snake_case)]
 231             pub fn new<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 232                                        dep: DepConstructor<'gcx>)
 233                                        -> DepNode
 234                 where 'gcx: 'a + 'tcx,
 235                       'tcx: 'a
 236             {
 237                 match dep {
 238                     $(
 239                         DepConstructor :: $variant $(( replace!(($tuple_arg_ty) with arg) ))*
 240                                                    $({ $($struct_arg_name),* })*
 241                             =>
 242                         {
 243                             // tuple args
 244                             $({
 245                                 erase!($tuple_arg_ty);
 246                                 let hash = DepNodeParams::to_fingerprint(&arg, tcx);
 247                                 let dep_node = DepNode {
 248                                     kind: DepKind::$variant,
 249                                     hash
 250                                 };
 251
 252                                 if cfg!(debug_assertions) &&
 253                                    !dep_node.kind.can_reconstruct_query_key() &&
 254                                    (tcx.sess.opts.debugging_opts.incremental_info ||
 255                                     tcx.sess.opts.debugging_opts.query_dep_graph)
 256                                 {
 257                                     tcx.dep_graph.register_dep_node_debug_str(dep_node, || {
 258                                         arg.to_debug_str(tcx)
 259                                     });
 260                                 }
 261
 262                                 return dep_node;
 263                             })*
 264
 265                             // struct args
 266                             $({
 267                                 let tupled_args = ( $($struct_arg_name,)* );
 268                                 let hash = DepNodeParams::to_fingerprint(&tupled_args,
 269                                                                          tcx);
 270                                 let dep_node = DepNode {
 271                                     kind: DepKind::$variant,
 272                                     hash
 273                                 };
 274
 275                                 if cfg!(debug_assertions) &&
 276                                    !dep_node.kind.can_reconstruct_query_key() &&
 277                                    (tcx.sess.opts.debugging_opts.incremental_info ||
 278                                     tcx.sess.opts.debugging_opts.query_dep_graph)
 279                                 {
 280                                     tcx.dep_graph.register_dep_node_debug_str(dep_node, || {
 281                                         tupled_args.to_debug_str(tcx)
 282                                     });
 283                                 }
 284
 285                                 return dep_node;
 286                             })*
 287
 288                             DepNode {
 289                                 kind: DepKind::$variant,
 290                                 hash: Fingerprint::ZERO,
 291                             }
 292                         }
 293                     )*
 294                 }
 295             }
 296
 297             /// Construct a DepNode from the given DepKind and DefPathHash. This
 298             /// method will assert that the given DepKind actually requires a
 299             /// single DefId/DefPathHash parameter.
 300             #[inline]
 301             pub fn from_def_path_hash(kind: DepKind,
 302                                       def_path_hash: DefPathHash)
 303                                       -> DepNode {
 304                 assert!(kind.can_reconstruct_query_key() && kind.has_params());
 305                 DepNode {
 306                     kind,
 307                     hash: def_path_hash.0,
 308                 }
 309             }
 310
 311             /// Create a new, parameterless DepNode. This method will assert
 312             /// that the DepNode corresponding to the given DepKind actually
 313             /// does not require any parameters.
 314             #[inline]
 315             pub fn new_no_params(kind: DepKind) -> DepNode {
 316                 assert!(!kind.has_params());
 317                 DepNode {
 318                     kind,
 319                     hash: Fingerprint::ZERO,
 320                 }
 321             }
 322
 323             /// Extract the DefId corresponding to this DepNode. This will work
 324             /// if two conditions are met:
 325             ///
 326             /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
 327             /// 2. the item that the DefPath refers to exists in the current tcx.
 328             ///
 329             /// Condition (1) is determined by the DepKind variant of the
 330             /// DepNode. Condition (2) might not be fulfilled if a DepNode
 331             /// refers to something from the previous compilation session that
 332             /// has been removed.
 333             #[inline]
 334             pub fn extract_def_id(&self, tcx: TyCtxt) -> Option<DefId> {
 335                 if self.kind.can_reconstruct_query_key() {
 336                     let def_path_hash = DefPathHash(self.hash);
 337                     tcx.def_path_hash_to_def_id.as_ref()?
 338                         .get(&def_path_hash).cloned()
 339                 } else {
 340                     None
 341                 }
 342             }
 343
 344             /// Used in testing
 345             pub fn from_label_string(label: &str,
 346                                      def_path_hash: DefPathHash)
 347                                      -> Result<DepNode, ()> {
 348                 let kind = match label {
 349                     $(
 350                         stringify!($variant) => DepKind::$variant,
 351                     )*
 352                     _ => return Err(()),
 353                 };
 354
 355                 if !kind.can_reconstruct_query_key() {
 356                     return Err(());
 357                 }
 358
 359                 if kind.has_params() {
 360                     Ok(def_path_hash.to_dep_node(kind))
 361                 } else {
 362                     Ok(DepNode::new_no_params(kind))
 363                 }
 364             }
 365
 366             /// Used in testing
 367             pub fn has_label_string(label: &str) -> bool {
 368                 match label {
 369                     $(
 370                         stringify!($variant) => true,
 371                     )*
 372                     _ => false,
 373                 }
 374             }
 375         }
 376
 377         /// Contains variant => str representations for constructing
 378         /// DepNode groups for tests.
 379         #[allow(dead_code, non_upper_case_globals)]
 380         pub mod label_strs {
 381            $(
 382                 pub const $variant: &'static str = stringify!($variant);
 383             )*
 384         }
 385     );
 386 }
 387
 388 impl fmt::Debug for DepNode {
 389     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 390         write!(f, "{:?}", self.kind)?;
 391
 392         if !self.kind.has_params() && !self.kind.is_anon() {
 393             return Ok(());
 394         }
 395
 396         write!(f, "(")?;
 397
 398         ::ty::tls::with_opt(|opt_tcx| {
 399             if let Some(tcx) = opt_tcx {
 400                 if let Some(def_id) = self.extract_def_id(tcx) {
 401                     write!(f, "{}", tcx.def_path_debug_str(def_id))?;
 402                 } else if let Some(ref s) = tcx.dep_graph.dep_node_debug_str(*self) {
 403                     write!(f, "{}", s)?;
 404                 } else {
 405                     write!(f, "{}", self.hash)?;
 406                 }
 407             } else {
 408                 write!(f, "{}", self.hash)?;
 409             }
 410             Ok(())
 411         })?;
 412
 413         write!(f, ")")
 414     }
 415 }
 416
 417
 418 impl DefPathHash {
 419     #[inline]
 420     pub fn to_dep_node(self, kind: DepKind) -> DepNode {
 421         DepNode::from_def_path_hash(kind, self)
 422     }
 423 }
 424
 425 impl DefId {
 426     #[inline]
 427     pub fn to_dep_node(self, tcx: TyCtxt, kind: DepKind) -> DepNode {
 428         DepNode::from_def_path_hash(kind, tcx.def_path_hash(self))
 429     }
 430 }
 431
 432 impl DepKind {
 433     #[inline]
 434     pub fn fingerprint_needed_for_crate_hash(self) -> bool {
 435         match self {
 436             DepKind::HirBody |
 437             DepKind::Krate => true,
 438             _ => false,
 439         }
 440     }
 441 }
 442
 443 define_dep_nodes!( <'tcx>
 444     // We use this for most things when incr. comp. is turned off.
 445     [] Null,
 446
 447     // Represents the `Krate` as a whole (the `hir::Krate` value) (as
 448     // distinct from the krate module). This is basically a hash of
 449     // the entire krate, so if you read from `Krate` (e.g., by calling
 450     // `tcx.hir.krate()`), we will have to assume that any change
 451     // means that you need to be recompiled. This is because the
 452     // `Krate` value gives you access to all other items. To avoid
 453     // this fate, do not call `tcx.hir.krate()`; instead, prefer
 454     // wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
 455     // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
 456     // access to the krate, but you must remember to add suitable
 457     // edges yourself for the individual items that you read.
 458     [input] Krate,
 459
 460     // Represents the body of a function or method. The def-id is that of the
 461     // function/method.
 462     [input] HirBody(DefId),
 463
 464     // Represents the HIR node with the given node-id
 465     [input] Hir(DefId),
 466
 467     // Represents metadata from an extern crate.
 468     [input] CrateMetadata(CrateNum),
 469
 470     // Represents different phases in the compiler.
 471     [] RegionScopeTree(DefId),
 472     [eval_always] Coherence,
 473     [eval_always] CoherenceInherentImplOverlapCheck,
 474     [] CoherenceCheckTrait(DefId),
 475     [eval_always] PrivacyAccessLevels(CrateNum),
 476
 477     // Represents the MIR for a fn; also used as the task node for
 478     // things read/modify that MIR.
 479     [] MirConstQualif(DefId),
 480     [] MirBuilt(DefId),
 481     [] MirConst(DefId),
 482     [] MirValidated(DefId),
 483     [] MirOptimized(DefId),
 484     [] MirShim { instance_def: InstanceDef<'tcx> },
 485
 486     [] BorrowCheckKrate,
 487     [] BorrowCheck(DefId),
 488     [] MirBorrowCheck(DefId),
 489     [] UnsafetyCheckResult(DefId),
 490     [] UnsafeDeriveOnReprPacked(DefId),
 491
 492     [] Reachability,
 493     [] MirKeys,
 494     [eval_always] CrateVariances,
 495
 496     // Nodes representing bits of computed IR in the tcx. Each shared
 497     // table in the tcx (or elsewhere) maps to one of these
 498     // nodes.
 499     [] AssociatedItems(DefId),
 500     [] TypeOfItem(DefId),
 501     [] GenericsOfItem(DefId),
 502     [] PredicatesOfItem(DefId),
 503     [] ExplicitPredicatesOfItem(DefId),
 504     [] PredicatesDefinedOnItem(DefId),
 505     [] InferredOutlivesOf(DefId),
 506     [] InferredOutlivesCrate(CrateNum),
 507     [] SuperPredicatesOfItem(DefId),
 508     [] TraitDefOfItem(DefId),
 509     [] AdtDefOfItem(DefId),
 510     [] ImplTraitRef(DefId),
 511     [] ImplPolarity(DefId),
 512     [] FnSignature(DefId),
 513     [] CoerceUnsizedInfo(DefId),
 514
 515     [] ItemVarianceConstraints(DefId),
 516     [] ItemVariances(DefId),
 517     [] IsConstFn(DefId),
 518     [] IsForeignItem(DefId),
 519     [] TypeParamPredicates { item_id: DefId, param_id: DefId },
 520     [] SizedConstraint(DefId),
 521     [] DtorckConstraint(DefId),
 522     [] AdtDestructor(DefId),
 523     [] AssociatedItemDefIds(DefId),
 524     [eval_always] InherentImpls(DefId),
 525     [] TypeckBodiesKrate,
 526     [] TypeckTables(DefId),
 527     [] UsedTraitImports(DefId),
 528     [] HasTypeckTables(DefId),
 529     [] ConstEval { param_env: ParamEnvAnd<'tcx, GlobalId<'tcx>> },
 530     [] CheckMatch(DefId),
 531     [] SymbolName(DefId),
 532     [] InstanceSymbolName { instance: Instance<'tcx> },
 533     [] SpecializationGraph(DefId),
 534     [] ObjectSafety(DefId),
 535     [] FulfillObligation { param_env: ParamEnv<'tcx>, trait_ref: PolyTraitRef<'tcx> },
 536     [] VtableMethods { trait_ref: PolyTraitRef<'tcx> },
 537
 538     [] IsCopy { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 539     [] IsSized { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 540     [] IsFreeze { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 541     [] NeedsDrop { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 542     [] Layout { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 543
 544     // The set of impls for a given trait.
 545     [] TraitImpls(DefId),
 546
 547     [input] AllLocalTraitImpls,
 548
 549     [anon] TraitSelect,
 550
 551     [] ParamEnv(DefId),
 552     [] DescribeDef(DefId),
 553
 554     // FIXME(mw): DefSpans are not really inputs since they are derived from
 555     // HIR. But at the moment HIR hashing still contains some hacks that allow
 556     // to make type debuginfo to be source location independent. Declaring
 557     // DefSpan an input makes sure that changes to these are always detected
 558     // regardless of HIR hashing.
 559     [input] DefSpan(DefId),
 560     [] LookupStability(DefId),
 561     [] LookupDeprecationEntry(DefId),
 562     [] ConstIsRvaluePromotableToStatic(DefId),
 563     [] RvaluePromotableMap(DefId),
 564     [] ImplParent(DefId),
 565     [] TraitOfItem(DefId),
 566     [] IsReachableNonGeneric(DefId),
 567     [] IsUnreachableLocalDefinition(DefId),
 568     [] IsMirAvailable(DefId),
 569     [] ItemAttrs(DefId),
 570     [] CodegenFnAttrs(DefId),
 571     [] FnArgNames(DefId),
 572     [] RenderedConst(DefId),
 573     [] DylibDepFormats(CrateNum),
 574     [] IsPanicRuntime(CrateNum),
 575     [] IsCompilerBuiltins(CrateNum),
 576     [] HasGlobalAllocator(CrateNum),
 577     [] HasPanicHandler(CrateNum),
 578     [input] ExternCrate(DefId),
 579     [eval_always] LintLevels,
 580     [] Specializes { impl1: DefId, impl2: DefId },
 581     [input] InScopeTraits(DefIndex),
 582     [input] ModuleExports(DefId),
 583     [] IsSanitizerRuntime(CrateNum),
 584     [] IsProfilerRuntime(CrateNum),
 585     [] GetPanicStrategy(CrateNum),
 586     [] IsNoBuiltins(CrateNum),
 587     [] ImplDefaultness(DefId),
 588     [] CheckItemWellFormed(DefId),
 589     [] CheckTraitItemWellFormed(DefId),
 590     [] CheckImplItemWellFormed(DefId),
 591     [] ReachableNonGenerics(CrateNum),
 592     [] NativeLibraries(CrateNum),
 593     [] PluginRegistrarFn(CrateNum),
 594     [] DeriveRegistrarFn(CrateNum),
 595     [input] CrateDisambiguator(CrateNum),
 596     [input] CrateHash(CrateNum),
 597     [input] OriginalCrateName(CrateNum),
 598     [input] ExtraFileName(CrateNum),
 599
 600     [] ImplementationsOfTrait { krate: CrateNum, trait_id: DefId },
 601     [] AllTraitImplementations(CrateNum),
 602
 603     [] DllimportForeignItems(CrateNum),
 604     [] IsDllimportForeignItem(DefId),
 605     [] IsStaticallyIncludedForeignItem(DefId),
 606     [] NativeLibraryKind(DefId),
 607     [input] LinkArgs,
 608
 609     [] ResolveLifetimes(CrateNum),
 610     [] NamedRegion(DefIndex),
 611     [] IsLateBound(DefIndex),
 612     [] ObjectLifetimeDefaults(DefIndex),
 613
 614     [] Visibility(DefId),
 615     [input] DepKind(CrateNum),
 616     [input] CrateName(CrateNum),
 617     [] ItemChildren(DefId),
 618     [] ExternModStmtCnum(DefId),
 619     [eval_always] GetLibFeatures,
 620     [] DefinedLibFeatures(CrateNum),
 621     [eval_always] GetLangItems,
 622     [] DefinedLangItems(CrateNum),
 623     [] MissingLangItems(CrateNum),
 624     [] VisibleParentMap,
 625     [input] MissingExternCrateItem(CrateNum),
 626     [input] UsedCrateSource(CrateNum),
 627     [input] PostorderCnums,
 628
 629     // These queries are not expected to have inputs -- as a result, they
 630     // are not good candidates for "replay" because they are essentially
 631     // pure functions of their input (and hence the expectation is that
 632     // no caller would be green **apart** from just these
 633     // queries). Making them anonymous avoids hashing the result, which
 634     // may save a bit of time.
 635     [anon] EraseRegionsTy { ty: Ty<'tcx> },
 636
 637     [input] Freevars(DefId),
 638     [input] MaybeUnusedTraitImport(DefId),
 639     [input] MaybeUnusedExternCrates,
 640     [eval_always] StabilityIndex,
 641     [eval_always] AllTraits,
 642     [input] AllCrateNums,
 643     [] ExportedSymbols(CrateNum),
 644     [eval_always] CollectAndPartitionMonoItems,
 645     [] IsCodegenedItem(DefId),
 646     [] CodegenUnit(InternedString),
 647     [] CompileCodegenUnit(InternedString),
 648     [input] OutputFilenames,
 649     [] NormalizeProjectionTy(CanonicalProjectionGoal<'tcx>),
 650     [] NormalizeTyAfterErasingRegions(ParamEnvAnd<'tcx, Ty<'tcx>>),
 651     [] ImpliedOutlivesBounds(CanonicalTyGoal<'tcx>),
 652     [] DropckOutlives(CanonicalTyGoal<'tcx>),
 653     [] EvaluateObligation(CanonicalPredicateGoal<'tcx>),
 654     [] TypeOpEq(CanonicalTypeOpEqGoal<'tcx>),
 655     [] TypeOpSubtype(CanonicalTypeOpSubtypeGoal<'tcx>),
 656     [] TypeOpProvePredicate(CanonicalTypeOpProvePredicateGoal<'tcx>),
 657     [] TypeOpNormalizeTy(CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>>),
 658     [] TypeOpNormalizePredicate(CanonicalTypeOpNormalizeGoal<'tcx, Predicate<'tcx>>),
 659     [] TypeOpNormalizePolyFnSig(CanonicalTypeOpNormalizeGoal<'tcx, PolyFnSig<'tcx>>),
 660     [] TypeOpNormalizeFnSig(CanonicalTypeOpNormalizeGoal<'tcx, FnSig<'tcx>>),
 661
 662     [] SubstituteNormalizeAndTestPredicates { key: (DefId, &'tcx Substs<'tcx>) },
 663
 664     [input] TargetFeaturesWhitelist,
 665
 666     [] InstanceDefSizeEstimate { instance_def: InstanceDef<'tcx> },
 667
 668     [input] Features,
 669
 670     [] ProgramClausesFor(DefId),
 671     [] ProgramClausesForEnv(ParamEnv<'tcx>),
 672     [] WasmImportModuleMap(CrateNum),
 673     [] ForeignModules(CrateNum),
 674
 675     [] UpstreamMonomorphizations(CrateNum),
 676     [] UpstreamMonomorphizationsFor(DefId),
 677 );
 678
 679 trait DepNodeParams<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> : fmt::Debug {
 680     const CAN_RECONSTRUCT_QUERY_KEY: bool;
 681
 682     /// This method turns the parameters of a DepNodeConstructor into an opaque
 683     /// Fingerprint to be used in DepNode.
 684     /// Not all DepNodeParams support being turned into a Fingerprint (they
 685     /// don't need to if the corresponding DepNode is anonymous).
 686     fn to_fingerprint(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint {
 687         panic!("Not implemented. Accidentally called on anonymous node?")
 688     }
 689
 690     fn to_debug_str(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 691         format!("{:?}", self)
 692     }
 693 }
 694
 695 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a, T> DepNodeParams<'a, 'gcx, 'tcx> for T
 696     where T: HashStable<StableHashingContext<'a>> + fmt::Debug
 697 {
 698     default const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 699
 700     default fn to_fingerprint(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint {
 701         let mut hcx = tcx.create_stable_hashing_context();
 702         let mut hasher = StableHasher::new();
 703
 704         self.hash_stable(&mut hcx, &mut hasher);
 705
 706         hasher.finish()
 707     }
 708
 709     default fn to_debug_str(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 710         format!("{:?}", *self)
 711     }
 712 }
 713
 714 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for DefId {
 715     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 716
 717     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 718         tcx.def_path_hash(*self).0
 719     }
 720
 721     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 722         tcx.item_path_str(*self)
 723     }
 724 }
 725
 726 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for DefIndex {
 727     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 728
 729     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 730         tcx.hir.definitions().def_path_hash(*self).0
 731     }
 732
 733     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 734         tcx.item_path_str(DefId::local(*self))
 735     }
 736 }
 737
 738 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for CrateNum {
 739     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 740
 741     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 742         let def_id = DefId {
 743             krate: *self,
 744             index: CRATE_DEF_INDEX,
 745         };
 746         tcx.def_path_hash(def_id).0
 747     }
 748
 749     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 750         tcx.crate_name(*self).as_str().to_string()
 751     }
 752 }
 753
 754 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for (DefId, DefId) {
 755     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 756
 757     // We actually would not need to specialize the implementation of this
 758     // method but it's faster to combine the hashes than to instantiate a full
 759     // hashing context and stable-hashing state.
 760     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 761         let (def_id_0, def_id_1) = *self;
 762
 763         let def_path_hash_0 = tcx.def_path_hash(def_id_0);
 764         let def_path_hash_1 = tcx.def_path_hash(def_id_1);
 765
 766         def_path_hash_0.0.combine(def_path_hash_1.0)
 767     }
 768
 769     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 770         let (def_id_0, def_id_1) = *self;
 771
 772         format!("({}, {})",
 773                 tcx.def_path_debug_str(def_id_0),
 774                 tcx.def_path_debug_str(def_id_1))
 775     }
 776 }
 777
 778 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for HirId {
 779     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 780
 781     // We actually would not need to specialize the implementation of this
 782     // method but it's faster to combine the hashes than to instantiate a full
 783     // hashing context and stable-hashing state.
 784     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 785         let HirId {
 786             owner,
 787             local_id: ItemLocalId(local_id),
 788         } = *self;
 789
 790         let def_path_hash = tcx.def_path_hash(DefId::local(owner));
 791         let local_id = Fingerprint::from_smaller_hash(local_id as u64);
 792
 793         def_path_hash.0.combine(local_id)
 794     }
 795 }
 796
 797 /// A "work product" corresponds to a `.o` (or other) file that we
 798 /// save in between runs. These ids do not have a DefId but rather
 799 /// some independent path or string that persists between runs without
 800 /// the need to be mapped or unmapped. (This ensures we can serialize
 801 /// them even in the absence of a tcx.)
 802 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
 803          RustcEncodable, RustcDecodable)]
 804 pub struct WorkProductId {
 805     hash: Fingerprint
 806 }
 807
 808 impl WorkProductId {
 809     pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
 810         let mut hasher = StableHasher::new();
 811         cgu_name.len().hash(&mut hasher);
 812         cgu_name.hash(&mut hasher);
 813         WorkProductId {
 814             hash: hasher.finish()
 815         }
 816     }
 817
 818     pub fn from_fingerprint(fingerprint: Fingerprint) -> WorkProductId {
 819         WorkProductId {
 820             hash: fingerprint
 821         }
 822     }
 823 }
 824
 825 impl_stable_hash_for!(struct ::dep_graph::WorkProductId {
 826     hash
 827 });