src/librustc_middle/dep_graph/dep_node.rs

   1 //! This module defines the `DepNode` type which the compiler uses to represent
   2 //! nodes in the dependency graph.
   3 //!
   4 //! A `DepNode` consists of a `DepKind` (which
   5 //! specifies the kind of thing it represents, like a piece of HIR, MIR, etc)
   6 //! and a `Fingerprint`, a 128-bit hash value the exact meaning of which
   7 //! depends on the node's `DepKind`. Together, the kind and the fingerprint
   8 //! fully identify a dependency node, even across multiple compilation sessions.
   9 //! In other words, the value of the fingerprint does not depend on anything
  10 //! that is specific to a given compilation session, like an unpredictable
  11 //! interning key (e.g., NodeId, DefId, Symbol) or the numeric value of a
  12 //! pointer. The concept behind this could be compared to how git commit hashes
  13 //! uniquely identify a given commit and has a few advantages:
  14 //!
  15 //! * A `DepNode` can simply be serialized to disk and loaded in another session
  16 //!   without the need to do any "rebasing" (like we have to do for Spans and
  17 //!   NodeIds) or "retracing" (like we had to do for `DefId` in earlier
  18 //!   implementations of the dependency graph).
  19 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
  20 //!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
  21 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
  22 //!   memory without any post-processing (e.g., "abomination-style" pointer
  23 //!   reconstruction).
  24 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
  25 //!   refer to things that do not exist anymore. In previous implementations
  26 //!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
  27 //!   had been removed between the previous and the current compilation session
  28 //!   could not be instantiated because the current compilation session
  29 //!   contained no `DefId` for thing that had been removed.
  30 //!
  31 //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
  32 //! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
  33 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
  34 //! runtime in order to construct a valid `DepNode` fingerprint.
  35 //!
  36 //! Because the macro sees what parameters a given `DepKind` requires, it can
  37 //! "infer" some properties for each kind of `DepNode`:
  38 //!
  39 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
  40 //!   `DepNode`s could represent global concepts with only one value.
  41 //! * Whether it is possible, in principle, to reconstruct a query key from a
  42 //!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
  43 //!   in which case it is possible to map the node's fingerprint back to the
  44 //!   `DefId` it was computed from. In other cases, too much information gets
  45 //!   lost during fingerprint computation.
  46 //!
  47 //! The `DepConstructor` enum, together with `DepNode::new()`, ensures that only
  48 //! valid `DepNode` instances can be constructed. For example, the API does not
  49 //! allow for constructing parameterless `DepNode`s with anything other
  50 //! than a zeroed out fingerprint. More generally speaking, it relieves the
  51 //! user of the `DepNode` API of having to know how to compute the expected
  52 //! fingerprint for a given set of node parameters.
  53
  54 use crate::mir::interpret::{GlobalId, LitToConstInput};
  55 use crate::traits;
  56 use crate::traits::query::{
  57     CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal,
  58     CanonicalTypeOpAscribeUserTypeGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpNormalizeGoal,
  59     CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpSubtypeGoal,
  60 };
  61 use crate::ty::subst::{GenericArg, SubstsRef};
  62 use crate::ty::{self, ParamEnvAnd, Ty, TyCtxt};
  63
  64 use rustc_data_structures::fingerprint::Fingerprint;
  65 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId, CRATE_DEF_INDEX};
  66 use rustc_hir::definitions::DefPathHash;
  67 use rustc_hir::HirId;
  68 use rustc_span::symbol::Symbol;
  69 use std::hash::Hash;
  70
  71 pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams};
  72
  73 // erase!() just makes tokens go away. It's used to specify which macro argument
  74 // is repeated (i.e., which sub-expression of the macro we are in) but don't need
  75 // to actually use any of the arguments.
  76 macro_rules! erase {
  77     ($x:tt) => {{}};
  78 }
  79
  80 macro_rules! is_anon_attr {
  81     (anon) => {
  82         true
  83     };
  84     ($attr:ident) => {
  85         false
  86     };
  87 }
  88
  89 macro_rules! is_eval_always_attr {
  90     (eval_always) => {
  91         true
  92     };
  93     ($attr:ident) => {
  94         false
  95     };
  96 }
  97
  98 macro_rules! contains_anon_attr {
  99     ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_anon_attr!($attr) | )* false});
 100 }
 101
 102 macro_rules! contains_eval_always_attr {
 103     ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_eval_always_attr!($attr) | )* false});
 104 }
 105
 106 macro_rules! define_dep_nodes {
 107     (<$tcx:tt>
 108     $(
 109         [$($attrs:tt)*]
 110         $variant:ident $(( $tuple_arg_ty:ty $(,)? ))*
 111       ,)*
 112     ) => (
 113         #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
 114                  RustcEncodable, RustcDecodable)]
 115         #[allow(non_camel_case_types)]
 116         pub enum DepKind {
 117             $($variant),*
 118         }
 119
 120         impl DepKind {
 121             #[allow(unreachable_code)]
 122             pub fn can_reconstruct_query_key<$tcx>(&self) -> bool {
 123                 match *self {
 124                     $(
 125                         DepKind :: $variant => {
 126                             if contains_anon_attr!($($attrs)*) {
 127                                 return false;
 128                             }
 129
 130                             // tuple args
 131                             $({
 132                                 return <$tuple_arg_ty as DepNodeParams<TyCtxt<'_>>>
 133                                     ::can_reconstruct_query_key();
 134                             })*
 135
 136                             true
 137                         }
 138                     )*
 139                 }
 140             }
 141
 142             pub fn is_anon(&self) -> bool {
 143                 match *self {
 144                     $(
 145                         DepKind :: $variant => { contains_anon_attr!($($attrs)*) }
 146                     )*
 147                 }
 148             }
 149
 150             pub fn is_eval_always(&self) -> bool {
 151                 match *self {
 152                     $(
 153                         DepKind :: $variant => { contains_eval_always_attr!($($attrs)*) }
 154                     )*
 155                 }
 156             }
 157
 158             #[allow(unreachable_code)]
 159             pub fn has_params(&self) -> bool {
 160                 match *self {
 161                     $(
 162                         DepKind :: $variant => {
 163                             // tuple args
 164                             $({
 165                                 erase!($tuple_arg_ty);
 166                                 return true;
 167                             })*
 168
 169                             false
 170                         }
 171                     )*
 172                 }
 173             }
 174         }
 175
 176         pub struct DepConstructor;
 177
 178         #[allow(non_camel_case_types)]
 179         impl DepConstructor {
 180             $(
 181                 #[inline(always)]
 182                 #[allow(unreachable_code, non_snake_case)]
 183                 pub fn $variant(_tcx: TyCtxt<'_>, $(arg: $tuple_arg_ty)*) -> DepNode {
 184                     // tuple args
 185                     $({
 186                         erase!($tuple_arg_ty);
 187                         return DepNode::construct(_tcx, DepKind::$variant, &arg)
 188                     })*
 189
 190                     return DepNode::construct(_tcx, DepKind::$variant, &())
 191                 }
 192             )*
 193         }
 194
 195         pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>;
 196
 197         pub trait DepNodeExt: Sized {
 198             /// Construct a DepNode from the given DepKind and DefPathHash. This
 199             /// method will assert that the given DepKind actually requires a
 200             /// single DefId/DefPathHash parameter.
 201             fn from_def_path_hash(def_path_hash: DefPathHash, kind: DepKind) -> Self;
 202
 203             /// Extracts the DefId corresponding to this DepNode. This will work
 204             /// if two conditions are met:
 205             ///
 206             /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
 207             /// 2. the item that the DefPath refers to exists in the current tcx.
 208             ///
 209             /// Condition (1) is determined by the DepKind variant of the
 210             /// DepNode. Condition (2) might not be fulfilled if a DepNode
 211             /// refers to something from the previous compilation session that
 212             /// has been removed.
 213             fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId>;
 214
 215             /// Used in testing
 216             fn from_label_string(label: &str, def_path_hash: DefPathHash)
 217                 -> Result<Self, ()>;
 218
 219             /// Used in testing
 220             fn has_label_string(label: &str) -> bool;
 221         }
 222
 223         impl DepNodeExt for DepNode {
 224             /// Construct a DepNode from the given DepKind and DefPathHash. This
 225             /// method will assert that the given DepKind actually requires a
 226             /// single DefId/DefPathHash parameter.
 227             fn from_def_path_hash(def_path_hash: DefPathHash, kind: DepKind) -> DepNode {
 228                 debug_assert!(kind.can_reconstruct_query_key() && kind.has_params());
 229                 DepNode {
 230                     kind,
 231                     hash: def_path_hash.0,
 232                 }
 233             }
 234
 235             /// Extracts the DefId corresponding to this DepNode. This will work
 236             /// if two conditions are met:
 237             ///
 238             /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
 239             /// 2. the item that the DefPath refers to exists in the current tcx.
 240             ///
 241             /// Condition (1) is determined by the DepKind variant of the
 242             /// DepNode. Condition (2) might not be fulfilled if a DepNode
 243             /// refers to something from the previous compilation session that
 244             /// has been removed.
 245             fn extract_def_id(&self, tcx: TyCtxt<'tcx>) -> Option<DefId> {
 246                 if self.kind.can_reconstruct_query_key() {
 247                     let def_path_hash = DefPathHash(self.hash);
 248                     tcx.def_path_hash_to_def_id.as_ref()?.get(&def_path_hash).cloned()
 249                 } else {
 250                     None
 251                 }
 252             }
 253
 254             /// Used in testing
 255             fn from_label_string(label: &str, def_path_hash: DefPathHash) -> Result<DepNode, ()> {
 256                 let kind = match label {
 257                     $(
 258                         stringify!($variant) => DepKind::$variant,
 259                     )*
 260                     _ => return Err(()),
 261                 };
 262
 263                 if !kind.can_reconstruct_query_key() {
 264                     return Err(());
 265                 }
 266
 267                 if kind.has_params() {
 268                     Ok(DepNode::from_def_path_hash(def_path_hash, kind))
 269                 } else {
 270                     Ok(DepNode::new_no_params(kind))
 271                 }
 272             }
 273
 274             /// Used in testing
 275             fn has_label_string(label: &str) -> bool {
 276                 match label {
 277                     $(
 278                         stringify!($variant) => true,
 279                     )*
 280                     _ => false,
 281                 }
 282             }
 283         }
 284
 285         /// Contains variant => str representations for constructing
 286         /// DepNode groups for tests.
 287         #[allow(dead_code, non_upper_case_globals)]
 288         pub mod label_strs {
 289            $(
 290                 pub const $variant: &str = stringify!($variant);
 291             )*
 292         }
 293     );
 294 }
 295
 296 rustc_dep_node_append!([define_dep_nodes!][ <'tcx>
 297     // We use this for most things when incr. comp. is turned off.
 298     [] Null,
 299
 300     // Represents metadata from an extern crate.
 301     [eval_always] CrateMetadata(CrateNum),
 302
 303     [anon] TraitSelect,
 304
 305     [] CompileCodegenUnit(Symbol),
 306 ]);
 307
 308 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId {
 309     #[inline]
 310     fn can_reconstruct_query_key() -> bool {
 311         true
 312     }
 313
 314     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 315         tcx.def_path_hash(*self).0
 316     }
 317
 318     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 319         tcx.def_path_str(*self)
 320     }
 321
 322     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 323         dep_node.extract_def_id(tcx)
 324     }
 325 }
 326
 327 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId {
 328     #[inline]
 329     fn can_reconstruct_query_key() -> bool {
 330         true
 331     }
 332
 333     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 334         self.to_def_id().to_fingerprint(tcx)
 335     }
 336
 337     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 338         self.to_def_id().to_debug_str(tcx)
 339     }
 340
 341     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 342         dep_node.extract_def_id(tcx).map(|id| id.expect_local())
 343     }
 344 }
 345
 346 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum {
 347     #[inline]
 348     fn can_reconstruct_query_key() -> bool {
 349         true
 350     }
 351
 352     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 353         let def_id = DefId { krate: *self, index: CRATE_DEF_INDEX };
 354         tcx.def_path_hash(def_id).0
 355     }
 356
 357     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 358         tcx.crate_name(*self).to_string()
 359     }
 360
 361     fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
 362         dep_node.extract_def_id(tcx).map(|id| id.krate)
 363     }
 364 }
 365
 366 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) {
 367     #[inline]
 368     fn can_reconstruct_query_key() -> bool {
 369         false
 370     }
 371
 372     // We actually would not need to specialize the implementation of this
 373     // method but it's faster to combine the hashes than to instantiate a full
 374     // hashing context and stable-hashing state.
 375     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 376         let (def_id_0, def_id_1) = *self;
 377
 378         let def_path_hash_0 = tcx.def_path_hash(def_id_0);
 379         let def_path_hash_1 = tcx.def_path_hash(def_id_1);
 380
 381         def_path_hash_0.0.combine(def_path_hash_1.0)
 382     }
 383
 384     fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
 385         let (def_id_0, def_id_1) = *self;
 386
 387         format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1))
 388     }
 389 }
 390
 391 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId {
 392     #[inline]
 393     fn can_reconstruct_query_key() -> bool {
 394         false
 395     }
 396
 397     // We actually would not need to specialize the implementation of this
 398     // method but it's faster to combine the hashes than to instantiate a full
 399     // hashing context and stable-hashing state.
 400     fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
 401         let HirId { owner, local_id } = *self;
 402
 403         let def_path_hash = tcx.def_path_hash(owner.to_def_id());
 404         let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into());
 405
 406         def_path_hash.0.combine(local_id)
 407     }
 408 }