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, self};
  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                     if let Some(ref def_path_map) = tcx.def_path_hash_to_def_id.as_ref() {
 338                         def_path_map.get(&def_path_hash).cloned()
 339                     } else {
 340                        None
 341                     }
 342                 } else {
 343                     None
 344                 }
 345             }
 346
 347             /// Used in testing
 348             pub fn from_label_string(label: &str,
 349                                      def_path_hash: DefPathHash)
 350                                      -> Result<DepNode, ()> {
 351                 let kind = match label {
 352                     $(
 353                         stringify!($variant) => DepKind::$variant,
 354                     )*
 355                     _ => return Err(()),
 356                 };
 357
 358                 if !kind.can_reconstruct_query_key() {
 359                     return Err(());
 360                 }
 361
 362                 if kind.has_params() {
 363                     Ok(def_path_hash.to_dep_node(kind))
 364                 } else {
 365                     Ok(DepNode::new_no_params(kind))
 366                 }
 367             }
 368
 369             /// Used in testing
 370             pub fn has_label_string(label: &str) -> bool {
 371                 match label {
 372                     $(
 373                         stringify!($variant) => true,
 374                     )*
 375                     _ => false,
 376                 }
 377             }
 378         }
 379
 380         /// Contains variant => str representations for constructing
 381         /// DepNode groups for tests.
 382         #[allow(dead_code, non_upper_case_globals)]
 383         pub mod label_strs {
 384            $(
 385                 pub const $variant: &'static str = stringify!($variant);
 386             )*
 387         }
 388     );
 389 }
 390
 391 impl fmt::Debug for DepNode {
 392     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 393         write!(f, "{:?}", self.kind)?;
 394
 395         if !self.kind.has_params() && !self.kind.is_anon() {
 396             return Ok(());
 397         }
 398
 399         write!(f, "(")?;
 400
 401         ::ty::tls::with_opt(|opt_tcx| {
 402             if let Some(tcx) = opt_tcx {
 403                 if let Some(def_id) = self.extract_def_id(tcx) {
 404                     write!(f, "{}", tcx.def_path_debug_str(def_id))?;
 405                 } else if let Some(ref s) = tcx.dep_graph.dep_node_debug_str(*self) {
 406                     write!(f, "{}", s)?;
 407                 } else {
 408                     write!(f, "{}", self.hash)?;
 409                 }
 410             } else {
 411                 write!(f, "{}", self.hash)?;
 412             }
 413             Ok(())
 414         })?;
 415
 416         write!(f, ")")
 417     }
 418 }
 419
 420
 421 impl DefPathHash {
 422     #[inline]
 423     pub fn to_dep_node(self, kind: DepKind) -> DepNode {
 424         DepNode::from_def_path_hash(kind, self)
 425     }
 426 }
 427
 428 impl DefId {
 429     #[inline]
 430     pub fn to_dep_node(self, tcx: TyCtxt, kind: DepKind) -> DepNode {
 431         DepNode::from_def_path_hash(kind, tcx.def_path_hash(self))
 432     }
 433 }
 434
 435 impl DepKind {
 436     #[inline]
 437     pub fn fingerprint_needed_for_crate_hash(self) -> bool {
 438         match self {
 439             DepKind::HirBody |
 440             DepKind::Krate => true,
 441             _ => false,
 442         }
 443     }
 444 }
 445
 446 define_dep_nodes!( <'tcx>
 447     // We use this for most things when incr. comp. is turned off.
 448     [] Null,
 449
 450     // Represents the `Krate` as a whole (the `hir::Krate` value) (as
 451     // distinct from the krate module). This is basically a hash of
 452     // the entire krate, so if you read from `Krate` (e.g., by calling
 453     // `tcx.hir.krate()`), we will have to assume that any change
 454     // means that you need to be recompiled. This is because the
 455     // `Krate` value gives you access to all other items. To avoid
 456     // this fate, do not call `tcx.hir.krate()`; instead, prefer
 457     // wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
 458     // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
 459     // access to the krate, but you must remember to add suitable
 460     // edges yourself for the individual items that you read.
 461     [input] Krate,
 462
 463     // Represents the body of a function or method. The def-id is that of the
 464     // function/method.
 465     [input] HirBody(DefId),
 466
 467     // Represents the HIR node with the given node-id
 468     [input] Hir(DefId),
 469
 470     // Represents metadata from an extern crate.
 471     [input] CrateMetadata(CrateNum),
 472
 473     // Represents different phases in the compiler.
 474     [] RegionScopeTree(DefId),
 475     [eval_always] Coherence,
 476     [eval_always] CoherenceInherentImplOverlapCheck,
 477     [] CoherenceCheckTrait(DefId),
 478     [eval_always] PrivacyAccessLevels(CrateNum),
 479
 480     // Represents the MIR for a fn; also used as the task node for
 481     // things read/modify that MIR.
 482     [] MirConstQualif(DefId),
 483     [] MirBuilt(DefId),
 484     [] MirConst(DefId),
 485     [] MirValidated(DefId),
 486     [] MirOptimized(DefId),
 487     [] MirShim { instance_def: InstanceDef<'tcx> },
 488
 489     [] BorrowCheckKrate,
 490     [] BorrowCheck(DefId),
 491     [] MirBorrowCheck(DefId),
 492     [] UnsafetyCheckResult(DefId),
 493     [] UnsafeDeriveOnReprPacked(DefId),
 494
 495     [] Reachability,
 496     [] MirKeys,
 497     [eval_always] CrateVariances,
 498
 499     // Nodes representing bits of computed IR in the tcx. Each shared
 500     // table in the tcx (or elsewhere) maps to one of these
 501     // nodes.
 502     [] AssociatedItems(DefId),
 503     [] TypeOfItem(DefId),
 504     [] GenericsOfItem(DefId),
 505     [] PredicatesOfItem(DefId),
 506     [] ExplicitPredicatesOfItem(DefId),
 507     [] InferredOutlivesOf(DefId),
 508     [] InferredOutlivesCrate(CrateNum),
 509     [] SuperPredicatesOfItem(DefId),
 510     [] TraitDefOfItem(DefId),
 511     [] AdtDefOfItem(DefId),
 512     [] ImplTraitRef(DefId),
 513     [] ImplPolarity(DefId),
 514     [] FnSignature(DefId),
 515     [] CoerceUnsizedInfo(DefId),
 516
 517     [] ItemVarianceConstraints(DefId),
 518     [] ItemVariances(DefId),
 519     [] IsConstFn(DefId),
 520     [] IsForeignItem(DefId),
 521     [] TypeParamPredicates { item_id: DefId, param_id: DefId },
 522     [] SizedConstraint(DefId),
 523     [] DtorckConstraint(DefId),
 524     [] AdtDestructor(DefId),
 525     [] AssociatedItemDefIds(DefId),
 526     [eval_always] InherentImpls(DefId),
 527     [] TypeckBodiesKrate,
 528     [] TypeckTables(DefId),
 529     [] UsedTraitImports(DefId),
 530     [] HasTypeckTables(DefId),
 531     [] ConstEval { param_env: ParamEnvAnd<'tcx, GlobalId<'tcx>> },
 532     [] CheckMatch(DefId),
 533     [] SymbolName(DefId),
 534     [] InstanceSymbolName { instance: Instance<'tcx> },
 535     [] SpecializationGraph(DefId),
 536     [] ObjectSafety(DefId),
 537     [] FulfillObligation { param_env: ParamEnv<'tcx>, trait_ref: PolyTraitRef<'tcx> },
 538     [] VtableMethods { trait_ref: PolyTraitRef<'tcx> },
 539
 540     [] IsCopy { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 541     [] IsSized { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 542     [] IsFreeze { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 543     [] NeedsDrop { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 544     [] Layout { param_env: ParamEnvAnd<'tcx, Ty<'tcx>> },
 545
 546     // The set of impls for a given trait.
 547     [] TraitImpls(DefId),
 548
 549     [input] AllLocalTraitImpls,
 550
 551     [anon] TraitSelect,
 552
 553     [] ParamEnv(DefId),
 554     [] DescribeDef(DefId),
 555
 556     // FIXME(mw): DefSpans are not really inputs since they are derived from
 557     // HIR. But at the moment HIR hashing still contains some hacks that allow
 558     // to make type debuginfo to be source location independent. Declaring
 559     // DefSpan an input makes sure that changes to these are always detected
 560     // regardless of HIR hashing.
 561     [input] DefSpan(DefId),
 562     [] LookupStability(DefId),
 563     [] LookupDeprecationEntry(DefId),
 564     [] ConstIsRvaluePromotableToStatic(DefId),
 565     [] RvaluePromotableMap(DefId),
 566     [] ImplParent(DefId),
 567     [] TraitOfItem(DefId),
 568     [] IsReachableNonGeneric(DefId),
 569     [] IsUnreachableLocalDefinition(DefId),
 570     [] IsMirAvailable(DefId),
 571     [] ItemAttrs(DefId),
 572     [] CodegenFnAttrs(DefId),
 573     [] FnArgNames(DefId),
 574     [] RenderedConst(DefId),
 575     [] DylibDepFormats(CrateNum),
 576     [] IsPanicRuntime(CrateNum),
 577     [] IsCompilerBuiltins(CrateNum),
 578     [] HasGlobalAllocator(CrateNum),
 579     [input] ExternCrate(DefId),
 580     [eval_always] LintLevels,
 581     [] Specializes { impl1: DefId, impl2: DefId },
 582     [input] InScopeTraits(DefIndex),
 583     [input] ModuleExports(DefId),
 584     [] IsSanitizerRuntime(CrateNum),
 585     [] IsProfilerRuntime(CrateNum),
 586     [] GetPanicStrategy(CrateNum),
 587     [] IsNoBuiltins(CrateNum),
 588     [] ImplDefaultness(DefId),
 589     [] CheckItemWellFormed(DefId),
 590     [] CheckTraitItemWellFormed(DefId),
 591     [] CheckImplItemWellFormed(DefId),
 592     [] ReachableNonGenerics(CrateNum),
 593     [] NativeLibraries(CrateNum),
 594     [] PluginRegistrarFn(CrateNum),
 595     [] DeriveRegistrarFn(CrateNum),
 596     [input] CrateDisambiguator(CrateNum),
 597     [input] CrateHash(CrateNum),
 598     [input] OriginalCrateName(CrateNum),
 599     [input] ExtraFileName(CrateNum),
 600
 601     [] ImplementationsOfTrait { krate: CrateNum, trait_id: DefId },
 602     [] AllTraitImplementations(CrateNum),
 603
 604     [] DllimportForeignItems(CrateNum),
 605     [] IsDllimportForeignItem(DefId),
 606     [] IsStaticallyIncludedForeignItem(DefId),
 607     [] NativeLibraryKind(DefId),
 608     [input] LinkArgs,
 609
 610     [] ResolveLifetimes(CrateNum),
 611     [] NamedRegion(DefIndex),
 612     [] IsLateBound(DefIndex),
 613     [] ObjectLifetimeDefaults(DefIndex),
 614
 615     [] Visibility(DefId),
 616     [input] DepKind(CrateNum),
 617     [input] CrateName(CrateNum),
 618     [] ItemChildren(DefId),
 619     [] ExternModStmtCnum(DefId),
 620     [input] GetLangItems,
 621     [] DefinedLangItems(CrateNum),
 622     [] MissingLangItems(CrateNum),
 623     [] VisibleParentMap,
 624     [input] MissingExternCrateItem(CrateNum),
 625     [input] UsedCrateSource(CrateNum),
 626     [input] PostorderCnums,
 627
 628     // These queries are not expected to have inputs -- as a result, they
 629     // are not good candidates for "replay" because they are essentially
 630     // pure functions of their input (and hence the expectation is that
 631     // no caller would be green **apart** from just these
 632     // queries). Making them anonymous avoids hashing the result, which
 633     // may save a bit of time.
 634     [anon] EraseRegionsTy { ty: Ty<'tcx> },
 635     [anon] ConstValueToAllocation { val: &'tcx ty::Const<'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     [] DropckOutlives(CanonicalTyGoal<'tcx>),
 652     [] EvaluateObligation(CanonicalPredicateGoal<'tcx>),
 653     [] TypeOpEq(CanonicalTypeOpEqGoal<'tcx>),
 654     [] TypeOpSubtype(CanonicalTypeOpSubtypeGoal<'tcx>),
 655     [] TypeOpProvePredicate(CanonicalTypeOpProvePredicateGoal<'tcx>),
 656     [] TypeOpNormalizeTy(CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>>),
 657     [] TypeOpNormalizePredicate(CanonicalTypeOpNormalizeGoal<'tcx, Predicate<'tcx>>),
 658     [] TypeOpNormalizePolyFnSig(CanonicalTypeOpNormalizeGoal<'tcx, PolyFnSig<'tcx>>),
 659     [] TypeOpNormalizeFnSig(CanonicalTypeOpNormalizeGoal<'tcx, FnSig<'tcx>>),
 660
 661     [] SubstituteNormalizeAndTestPredicates { key: (DefId, &'tcx Substs<'tcx>) },
 662
 663     [input] TargetFeaturesWhitelist,
 664
 665     [] InstanceDefSizeEstimate { instance_def: InstanceDef<'tcx> },
 666
 667     [] WasmCustomSections(CrateNum),
 668
 669     [input] Features,
 670
 671     [] ProgramClausesFor(DefId),
 672     [] ProgramClausesForEnv(ParamEnv<'tcx>),
 673     [] WasmImportModuleMap(CrateNum),
 674     [] ForeignModules(CrateNum),
 675
 676     [] UpstreamMonomorphizations(CrateNum),
 677     [] UpstreamMonomorphizationsFor(DefId),
 678 );
 679
 680 trait DepNodeParams<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> : fmt::Debug {
 681     const CAN_RECONSTRUCT_QUERY_KEY: bool;
 682
 683     /// This method turns the parameters of a DepNodeConstructor into an opaque
 684     /// Fingerprint to be used in DepNode.
 685     /// Not all DepNodeParams support being turned into a Fingerprint (they
 686     /// don't need to if the corresponding DepNode is anonymous).
 687     fn to_fingerprint(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint {
 688         panic!("Not implemented. Accidentally called on anonymous node?")
 689     }
 690
 691     fn to_debug_str(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 692         format!("{:?}", self)
 693     }
 694 }
 695
 696 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a, T> DepNodeParams<'a, 'gcx, 'tcx> for T
 697     where T: HashStable<StableHashingContext<'a>> + fmt::Debug
 698 {
 699     default const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 700
 701     default fn to_fingerprint(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Fingerprint {
 702         let mut hcx = tcx.create_stable_hashing_context();
 703         let mut hasher = StableHasher::new();
 704
 705         self.hash_stable(&mut hcx, &mut hasher);
 706
 707         hasher.finish()
 708     }
 709
 710     default fn to_debug_str(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 711         format!("{:?}", *self)
 712     }
 713 }
 714
 715 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for DefId {
 716     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 717
 718     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 719         tcx.def_path_hash(*self).0
 720     }
 721
 722     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 723         tcx.item_path_str(*self)
 724     }
 725 }
 726
 727 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for DefIndex {
 728     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 729
 730     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 731         tcx.hir.definitions().def_path_hash(*self).0
 732     }
 733
 734     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 735         tcx.item_path_str(DefId::local(*self))
 736     }
 737 }
 738
 739 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for CrateNum {
 740     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 741
 742     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 743         let def_id = DefId {
 744             krate: *self,
 745             index: CRATE_DEF_INDEX,
 746         };
 747         tcx.def_path_hash(def_id).0
 748     }
 749
 750     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 751         tcx.crate_name(*self).as_str().to_string()
 752     }
 753 }
 754
 755 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for (DefId, DefId) {
 756     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 757
 758     // We actually would not need to specialize the implementation of this
 759     // method but it's faster to combine the hashes than to instantiate a full
 760     // hashing context and stable-hashing state.
 761     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 762         let (def_id_0, def_id_1) = *self;
 763
 764         let def_path_hash_0 = tcx.def_path_hash(def_id_0);
 765         let def_path_hash_1 = tcx.def_path_hash(def_id_1);
 766
 767         def_path_hash_0.0.combine(def_path_hash_1.0)
 768     }
 769
 770     fn to_debug_str(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> String {
 771         let (def_id_0, def_id_1) = *self;
 772
 773         format!("({}, {})",
 774                 tcx.def_path_debug_str(def_id_0),
 775                 tcx.def_path_debug_str(def_id_1))
 776     }
 777 }
 778
 779 impl<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> DepNodeParams<'a, 'gcx, 'tcx> for HirId {
 780     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 781
 782     // We actually would not need to specialize the implementation of this
 783     // method but it's faster to combine the hashes than to instantiate a full
 784     // hashing context and stable-hashing state.
 785     fn to_fingerprint(&self, tcx: TyCtxt) -> Fingerprint {
 786         let HirId {
 787             owner,
 788             local_id: ItemLocalId(local_id),
 789         } = *self;
 790
 791         let def_path_hash = tcx.def_path_hash(DefId::local(owner));
 792         let local_id = Fingerprint::from_smaller_hash(local_id as u64);
 793
 794         def_path_hash.0.combine(local_id)
 795     }
 796 }
 797
 798 /// A "work product" corresponds to a `.o` (or other) file that we
 799 /// save in between runs. These ids do not have a DefId but rather
 800 /// some independent path or string that persists between runs without
 801 /// the need to be mapped or unmapped. (This ensures we can serialize
 802 /// them even in the absence of a tcx.)
 803 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
 804          RustcEncodable, RustcDecodable)]
 805 pub struct WorkProductId {
 806     hash: Fingerprint
 807 }
 808
 809 impl WorkProductId {
 810     pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
 811         let mut hasher = StableHasher::new();
 812         cgu_name.len().hash(&mut hasher);
 813         cgu_name.hash(&mut hasher);
 814         WorkProductId {
 815             hash: hasher.finish()
 816         }
 817     }
 818
 819     pub fn from_fingerprint(fingerprint: Fingerprint) -> WorkProductId {
 820         WorkProductId {
 821             hash: fingerprint
 822         }
 823     }
 824 }
 825
 826 impl_stable_hash_for!(struct ::dep_graph::WorkProductId {
 827     hash
 828 });