src/librustc/dep_graph/dep_node.rs

   1 //! This module defines the `DepNode` type which the compiler uses to represent
   2 //! nodes in the dependency graph. A `DepNode` consists of a `DepKind` (which
   3 //! specifies the kind of thing it represents, like a piece of HIR, MIR, etc)
   4 //! and a `Fingerprint`, a 128 bit hash value the exact meaning of which
   5 //! depends on the node's `DepKind`. Together, the kind and the fingerprint
   6 //! fully identify a dependency node, even across multiple compilation sessions.
   7 //! In other words, the value of the fingerprint does not depend on anything
   8 //! that is specific to a given compilation session, like an unpredictable
   9 //! interning key (e.g., NodeId, DefId, Symbol) or the numeric value of a
  10 //! pointer. The concept behind this could be compared to how git commit hashes
  11 //! uniquely identify a given commit and has a few advantages:
  12 //!
  13 //! * A `DepNode` can simply be serialized to disk and loaded in another session
  14 //!   without the need to do any "rebasing (like we have to do for Spans and
  15 //!   NodeIds) or "retracing" like we had to do for `DefId` in earlier
  16 //!   implementations of the dependency graph.
  17 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
  18 //!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
  19 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
  20 //!   memory without any post-processing (e.g., "abomination-style" pointer
  21 //!   reconstruction).
  22 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
  23 //!   refer to things that do not exist anymore. In previous implementations
  24 //!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
  25 //!   had been removed between the previous and the current compilation session
  26 //!   could not be instantiated because the current compilation session
  27 //!   contained no `DefId` for thing that had been removed.
  28 //!
  29 //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
  30 //! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
  31 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
  32 //! runtime in order to construct a valid `DepNode` fingerprint.
  33 //!
  34 //! Because the macro sees what parameters a given `DepKind` requires, it can
  35 //! "infer" some properties for each kind of `DepNode`:
  36 //!
  37 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
  38 //!   `DepNode`s, like `Krate`, represent global concepts with only one value.
  39 //! * Whether it is possible, in principle, to reconstruct a query key from a
  40 //!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
  41 //!   in which case it is possible to map the node's fingerprint back to the
  42 //!   `DefId` it was computed from. In other cases, too much information gets
  43 //!   lost during fingerprint computation.
  44 //!
  45 //! The `DepConstructor` enum, together with `DepNode::new()` ensures that only
  46 //! valid `DepNode` instances can be constructed. For example, the API does not
  47 //! allow for constructing parameterless `DepNode`s with anything other
  48 //! than a zeroed out fingerprint. More generally speaking, it relieves the
  49 //! user of the `DepNode` API of having to know how to compute the expected
  50 //! fingerprint for a given set of node parameters.
  51
  52 use crate::hir::map::DefPathHash;
  53 use crate::ich::{Fingerprint, StableHashingContext};
  54 use crate::mir;
  55 use crate::mir::interpret::{GlobalId, LitToConstInput};
  56 use crate::traits;
  57 use crate::traits::query::{
  58     CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal,
  59     CanonicalTypeOpAscribeUserTypeGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpNormalizeGoal,
  60     CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpSubtypeGoal,
  61 };
  62 use crate::ty::subst::SubstsRef;
  63 use crate::ty::{self, ParamEnvAnd, Ty, TyCtxt};
  64
  65 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  66 use rustc_hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX};
  67 use rustc_hir::HirId;
  68 use rustc_span::symbol::Symbol;
  69 use std::fmt;
  70 use std::hash::Hash;
  71
  72 // erase!() just makes tokens go away. It's used to specify which macro argument
  73 // is repeated (i.e., which sub-expression of the macro we are in) but don't need
  74 // to actually use any of the arguments.
  75 macro_rules! erase {
  76     ($x:tt) => {{}};
  77 }
  78
  79 macro_rules! replace {
  80     ($x:tt with $($y:tt)*) => ($($y)*)
  81 }
  82
  83 macro_rules! is_anon_attr {
  84     (anon) => {
  85         true
  86     };
  87     ($attr:ident) => {
  88         false
  89     };
  90 }
  91
  92 macro_rules! is_eval_always_attr {
  93     (eval_always) => {
  94         true
  95     };
  96     ($attr:ident) => {
  97         false
  98     };
  99 }
 100
 101 macro_rules! contains_anon_attr {
 102     ($($attr:ident),*) => ({$(is_anon_attr!($attr) | )* false});
 103 }
 104
 105 macro_rules! contains_eval_always_attr {
 106     ($($attr:ident),*) => ({$(is_eval_always_attr!($attr) | )* false});
 107 }
 108
 109 macro_rules! define_dep_nodes {
 110     (<$tcx:tt>
 111     $(
 112         [$($attr:ident),* ]
 113         $variant:ident $(( $tuple_arg_ty:ty $(,)? ))*
 114                        $({ $($struct_arg_name:ident : $struct_arg_ty:ty),* })*
 115       ,)*
 116     ) => (
 117         #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
 118                  RustcEncodable, RustcDecodable)]
 119         pub enum DepKind {
 120             $($variant),*
 121         }
 122
 123         impl DepKind {
 124             #[allow(unreachable_code)]
 125             pub fn can_reconstruct_query_key<$tcx>(&self) -> bool {
 126                 match *self {
 127                     $(
 128                         DepKind :: $variant => {
 129                             if contains_anon_attr!($($attr),*) {
 130                                 return false;
 131                             }
 132
 133                             // tuple args
 134                             $({
 135                                 return <$tuple_arg_ty as DepNodeParams>
 136                                     ::CAN_RECONSTRUCT_QUERY_KEY;
 137                             })*
 138
 139                             // struct args
 140                             $({
 141
 142                                 return <( $($struct_arg_ty,)* ) as DepNodeParams>
 143                                     ::CAN_RECONSTRUCT_QUERY_KEY;
 144                             })*
 145
 146                             true
 147                         }
 148                     )*
 149                 }
 150             }
 151
 152             pub fn is_anon(&self) -> bool {
 153                 match *self {
 154                     $(
 155                         DepKind :: $variant => { contains_anon_attr!($($attr),*) }
 156                     )*
 157                 }
 158             }
 159
 160             pub fn is_eval_always(&self) -> bool {
 161                 match *self {
 162                     $(
 163                         DepKind :: $variant => { contains_eval_always_attr!($($attr), *) }
 164                     )*
 165                 }
 166             }
 167
 168             #[allow(unreachable_code)]
 169             pub fn has_params(&self) -> bool {
 170                 match *self {
 171                     $(
 172                         DepKind :: $variant => {
 173                             // tuple args
 174                             $({
 175                                 erase!($tuple_arg_ty);
 176                                 return true;
 177                             })*
 178
 179                             // struct args
 180                             $({
 181                                 $(erase!($struct_arg_name);)*
 182                                 return true;
 183                             })*
 184
 185                             false
 186                         }
 187                     )*
 188                 }
 189             }
 190         }
 191
 192         pub enum DepConstructor<$tcx> {
 193             $(
 194                 $variant $(( $tuple_arg_ty ))*
 195                          $({ $($struct_arg_name : $struct_arg_ty),* })*
 196             ),*
 197         }
 198
 199         #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash,
 200                  RustcEncodable, RustcDecodable)]
 201         pub struct DepNode {
 202             pub kind: DepKind,
 203             pub hash: Fingerprint,
 204         }
 205
 206         impl DepNode {
 207             #[allow(unreachable_code, non_snake_case)]
 208             pub fn new<'tcx>(tcx: TyCtxt<'tcx>,
 209                                        dep: DepConstructor<'tcx>)
 210                                        -> DepNode
 211             {
 212                 match dep {
 213                     $(
 214                         DepConstructor :: $variant $(( replace!(($tuple_arg_ty) with arg) ))*
 215                                                    $({ $($struct_arg_name),* })*
 216                             =>
 217                         {
 218                             // tuple args
 219                             $({
 220                                 erase!($tuple_arg_ty);
 221                                 let hash = DepNodeParams::to_fingerprint(&arg, tcx);
 222                                 let dep_node = DepNode {
 223                                     kind: DepKind::$variant,
 224                                     hash
 225                                 };
 226
 227                                 #[cfg(debug_assertions)]
 228                                 {
 229                                     if !dep_node.kind.can_reconstruct_query_key() &&
 230                                     (tcx.sess.opts.debugging_opts.incremental_info ||
 231                                         tcx.sess.opts.debugging_opts.query_dep_graph)
 232                                     {
 233                                         tcx.dep_graph.register_dep_node_debug_str(dep_node, || {
 234                                             arg.to_debug_str(tcx)
 235                                         });
 236                                     }
 237                                 }
 238
 239                                 return dep_node;
 240                             })*
 241
 242                             // struct args
 243                             $({
 244                                 let tupled_args = ( $($struct_arg_name,)* );
 245                                 let hash = DepNodeParams::to_fingerprint(&tupled_args,
 246                                                                          tcx);
 247                                 let dep_node = DepNode {
 248                                     kind: DepKind::$variant,
 249                                     hash
 250                                 };
 251
 252                                 #[cfg(debug_assertions)]
 253                                 {
 254                                     if !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                                             tupled_args.to_debug_str(tcx)
 260                                         });
 261                                     }
 262                                 }
 263
 264                                 return dep_node;
 265                             })*
 266
 267                             DepNode {
 268                                 kind: DepKind::$variant,
 269                                 hash: Fingerprint::ZERO,
 270                             }
 271                         }
 272                     )*
 273                 }
 274             }
 275
 276             /// Construct a DepNode from the given DepKind and DefPathHash. This
 277             /// method will assert that the given DepKind actually requires a
 278             /// single DefId/DefPathHash parameter.
 279             pub fn from_def_path_hash(kind: DepKind,
 280                                       def_path_hash: DefPathHash)
 281                                       -> DepNode {
 282                 debug_assert!(kind.can_reconstruct_query_key() && kind.has_params());
 283                 DepNode {
 284                     kind,
 285                     hash: def_path_hash.0,
 286                 }
 287             }
 288
 289             /// Creates a new, parameterless DepNode. This method will assert
 290             /// that the DepNode corresponding to the given DepKind actually
 291             /// does not require any parameters.
 292             pub fn new_no_params(kind: DepKind) -> DepNode {
 293                 debug_assert!(!kind.has_params());
 294                 DepNode {
 295                     kind,
 296                     hash: Fingerprint::ZERO,
 297                 }
 298             }
 299
 300             /// Extracts the DefId corresponding to this DepNode. This will work
 301             /// if two conditions are met:
 302             ///
 303             /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
 304             /// 2. the item that the DefPath refers to exists in the current tcx.
 305             ///
 306             /// Condition (1) is determined by the DepKind variant of the
 307             /// DepNode. Condition (2) might not be fulfilled if a DepNode
 308             /// refers to something from the previous compilation session that
 309             /// has been removed.
 310             pub fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId> {
 311                 if self.kind.can_reconstruct_query_key() {
 312                     let def_path_hash = DefPathHash(self.hash);
 313                     tcx.def_path_hash_to_def_id.as_ref()?
 314                         .get(&def_path_hash).cloned()
 315                 } else {
 316                     None
 317                 }
 318             }
 319
 320             /// Used in testing
 321             pub fn from_label_string(label: &str,
 322                                      def_path_hash: DefPathHash)
 323                                      -> Result<DepNode, ()> {
 324                 let kind = match label {
 325                     $(
 326                         stringify!($variant) => DepKind::$variant,
 327                     )*
 328                     _ => return Err(()),
 329                 };
 330
 331                 if !kind.can_reconstruct_query_key() {
 332                     return Err(());
 333                 }
 334
 335                 if kind.has_params() {
 336                     Ok(def_path_hash.to_dep_node(kind))
 337                 } else {
 338                     Ok(DepNode::new_no_params(kind))
 339                 }
 340             }
 341
 342             /// Used in testing
 343             pub fn has_label_string(label: &str) -> bool {
 344                 match label {
 345                     $(
 346                         stringify!($variant) => true,
 347                     )*
 348                     _ => false,
 349                 }
 350             }
 351         }
 352
 353         /// Contains variant => str representations for constructing
 354         /// DepNode groups for tests.
 355         #[allow(dead_code, non_upper_case_globals)]
 356         pub mod label_strs {
 357            $(
 358                 pub const $variant: &str = stringify!($variant);
 359             )*
 360         }
 361     );
 362 }
 363
 364 impl fmt::Debug for DepNode {
 365     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 366         write!(f, "{:?}", self.kind)?;
 367
 368         if !self.kind.has_params() && !self.kind.is_anon() {
 369             return Ok(());
 370         }
 371
 372         write!(f, "(")?;
 373
 374         crate::ty::tls::with_opt(|opt_tcx| {
 375             if let Some(tcx) = opt_tcx {
 376                 if let Some(def_id) = self.extract_def_id(tcx) {
 377                     write!(f, "{}", tcx.def_path_debug_str(def_id))?;
 378                 } else if let Some(ref s) = tcx.dep_graph.dep_node_debug_str(*self) {
 379                     write!(f, "{}", s)?;
 380                 } else {
 381                     write!(f, "{}", self.hash)?;
 382                 }
 383             } else {
 384                 write!(f, "{}", self.hash)?;
 385             }
 386             Ok(())
 387         })?;
 388
 389         write!(f, ")")
 390     }
 391 }
 392
 393 impl DefPathHash {
 394     pub fn to_dep_node(self, kind: DepKind) -> DepNode {
 395         DepNode::from_def_path_hash(kind, self)
 396     }
 397 }
 398
 399 rustc_dep_node_append!([define_dep_nodes!][ <'tcx>
 400     // We use this for most things when incr. comp. is turned off.
 401     [] Null,
 402
 403     // Represents the `Krate` as a whole (the `hir::Krate` value) (as
 404     // distinct from the krate module). This is basically a hash of
 405     // the entire krate, so if you read from `Krate` (e.g., by calling
 406     // `tcx.hir().krate()`), we will have to assume that any change
 407     // means that you need to be recompiled. This is because the
 408     // `Krate` value gives you access to all other items. To avoid
 409     // this fate, do not call `tcx.hir().krate()`; instead, prefer
 410     // wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
 411     // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
 412     // access to the krate, but you must remember to add suitable
 413     // edges yourself for the individual items that you read.
 414     [eval_always] Krate,
 415
 416     // Represents the body of a function or method. The def-id is that of the
 417     // function/method.
 418     [eval_always] HirBody(DefId),
 419
 420     // Represents the HIR node with the given node-id
 421     [eval_always] Hir(DefId),
 422
 423     // Represents metadata from an extern crate.
 424     [eval_always] CrateMetadata(CrateNum),
 425
 426     [eval_always] AllLocalTraitImpls,
 427
 428     [anon] TraitSelect,
 429
 430     [] CompileCodegenUnit(Symbol),
 431
 432     [eval_always] Analysis(CrateNum),
 433 ]);
 434
 435 pub trait RecoverKey<'tcx>: Sized {
 436     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self>;
 437 }
 438
 439 impl RecoverKey<'tcx> for CrateNum {
 440     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 441         dep_node.extract_def_id(tcx).map(|id| id.krate)
 442     }
 443 }
 444
 445 impl RecoverKey<'tcx> for DefId {
 446     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 447         dep_node.extract_def_id(tcx)
 448     }
 449 }
 450
 451 impl RecoverKey<'tcx> for DefIndex {
 452     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 453         dep_node.extract_def_id(tcx).map(|id| id.index)
 454     }
 455 }
 456
 457 trait DepNodeParams<'tcx>: fmt::Debug {
 458     const CAN_RECONSTRUCT_QUERY_KEY: bool;
 459
 460     /// This method turns the parameters of a DepNodeConstructor into an opaque
 461     /// Fingerprint to be used in DepNode.
 462     /// Not all DepNodeParams support being turned into a Fingerprint (they
 463     /// don't need to if the corresponding DepNode is anonymous).
 464     fn to_fingerprint(&self, _: TyCtxt<'tcx>) -> Fingerprint {
 465         panic!("Not implemented. Accidentally called on anonymous node?")
 466     }
 467
 468     fn to_debug_str(&self, _: TyCtxt<'tcx>) -> String {
 469         format!("{:?}", self)
 470     }
 471 }
 472
 473 impl<'tcx, T> DepNodeParams<'tcx> for T
 474 where
 475     T: HashStable<StableHashingContext<'tcx>> + fmt::Debug,
 476 {
 477     default const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 478
 479     default fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 480         let mut hcx = tcx.create_stable_hashing_context();
 481         let mut hasher = StableHasher::new();
 482
 483         self.hash_stable(&mut hcx, &mut hasher);
 484
 485         hasher.finish()
 486     }
 487
 488     default fn to_debug_str(&self, _: TyCtxt<'tcx>) -> String {
 489         format!("{:?}", *self)
 490     }
 491 }
 492
 493 impl<'tcx> DepNodeParams<'tcx> for DefId {
 494     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 495
 496     fn to_fingerprint(&self, tcx: TyCtxt<'_>) -> Fingerprint {
 497         tcx.def_path_hash(*self).0
 498     }
 499
 500     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 501         tcx.def_path_str(*self)
 502     }
 503 }
 504
 505 impl<'tcx> DepNodeParams<'tcx> for DefIndex {
 506     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 507
 508     fn to_fingerprint(&self, tcx: TyCtxt<'_>) -> Fingerprint {
 509         tcx.hir().definitions().def_path_hash(*self).0
 510     }
 511
 512     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 513         tcx.def_path_str(DefId::local(*self))
 514     }
 515 }
 516
 517 impl<'tcx> DepNodeParams<'tcx> for CrateNum {
 518     const CAN_RECONSTRUCT_QUERY_KEY: bool = true;
 519
 520     fn to_fingerprint(&self, tcx: TyCtxt<'_>) -> Fingerprint {
 521         let def_id = DefId { krate: *self, index: CRATE_DEF_INDEX };
 522         tcx.def_path_hash(def_id).0
 523     }
 524
 525     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 526         tcx.crate_name(*self).to_string()
 527     }
 528 }
 529
 530 impl<'tcx> DepNodeParams<'tcx> for (DefId, DefId) {
 531     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 532
 533     // We actually would not need to specialize the implementation of this
 534     // method but it's faster to combine the hashes than to instantiate a full
 535     // hashing context and stable-hashing state.
 536     fn to_fingerprint(&self, tcx: TyCtxt<'_>) -> Fingerprint {
 537         let (def_id_0, def_id_1) = *self;
 538
 539         let def_path_hash_0 = tcx.def_path_hash(def_id_0);
 540         let def_path_hash_1 = tcx.def_path_hash(def_id_1);
 541
 542         def_path_hash_0.0.combine(def_path_hash_1.0)
 543     }
 544
 545     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 546         let (def_id_0, def_id_1) = *self;
 547
 548         format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1))
 549     }
 550 }
 551
 552 impl<'tcx> DepNodeParams<'tcx> for HirId {
 553     const CAN_RECONSTRUCT_QUERY_KEY: bool = false;
 554
 555     // We actually would not need to specialize the implementation of this
 556     // method but it's faster to combine the hashes than to instantiate a full
 557     // hashing context and stable-hashing state.
 558     fn to_fingerprint(&self, tcx: TyCtxt<'_>) -> Fingerprint {
 559         let HirId { owner, local_id } = *self;
 560
 561         let def_path_hash = tcx.def_path_hash(DefId::local(owner));
 562         let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into());
 563
 564         def_path_hash.0.combine(local_id)
 565     }
 566 }
 567
 568 /// A "work product" corresponds to a `.o` (or other) file that we
 569 /// save in between runs. These IDs do not have a `DefId` but rather
 570 /// some independent path or string that persists between runs without
 571 /// the need to be mapped or unmapped. (This ensures we can serialize
 572 /// them even in the absence of a tcx.)
 573 #[derive(
 574     Clone,
 575     Copy,
 576     Debug,
 577     PartialEq,
 578     Eq,
 579     PartialOrd,
 580     Ord,
 581     Hash,
 582     RustcEncodable,
 583     RustcDecodable,
 584     HashStable
 585 )]
 586 pub struct WorkProductId {
 587     hash: Fingerprint,
 588 }
 589
 590 impl WorkProductId {
 591     pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
 592         let mut hasher = StableHasher::new();
 593         cgu_name.len().hash(&mut hasher);
 594         cgu_name.hash(&mut hasher);
 595         WorkProductId { hash: hasher.finish() }
 596     }
 597
 598     pub fn from_fingerprint(fingerprint: Fingerprint) -> WorkProductId {
 599         WorkProductId { hash: fingerprint }
 600     }
 601 }