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