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 use std::fmt::Debug;
  12 use std::sync::Arc;
  13
  14 macro_rules! try_opt {
  15     ($e:expr) => (
  16         match $e {
  17             Some(r) => r,
  18             None => return None,
  19         }
  20     )
  21 }
  22
  23 #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
  24 pub enum DepNode<D: Clone + Debug> {
  25     // The `D` type is "how definitions are identified".
  26     // During compilation, it is always `DefId`, but when serializing
  27     // it is mapped to `DefPath`.
  28
  29     // Represents the `Krate` as a whole (the `hir::Krate` value) (as
  30     // distinct from the krate module). This is basically a hash of
  31     // the entire krate, so if you read from `Krate` (e.g., by calling
  32     // `tcx.hir.krate()`), we will have to assume that any change
  33     // means that you need to be recompiled. This is because the
  34     // `Krate` value gives you access to all other items. To avoid
  35     // this fate, do not call `tcx.hir.krate()`; instead, prefer
  36     // wrappers like `tcx.visit_all_items_in_krate()`.  If there is no
  37     // suitable wrapper, you can use `tcx.dep_graph.ignore()` to gain
  38     // access to the krate, but you must remember to add suitable
  39     // edges yourself for the individual items that you read.
  40     Krate,
  41
  42     // Represents the HIR node with the given node-id
  43     Hir(D),
  44
  45     // Represents the body of a function or method. The def-id is that of the
  46     // function/method.
  47     HirBody(D),
  48
  49     // Represents the metadata for a given HIR node, typically found
  50     // in an extern crate.
  51     MetaData(D),
  52
  53     // Represents some artifact that we save to disk. Note that these
  54     // do not have a def-id as part of their identifier.
  55     WorkProduct(Arc<WorkProductId>),
  56
  57     // Represents different phases in the compiler.
  58     CollectLanguageItems,
  59     CheckStaticRecursion,
  60     ResolveLifetimes,
  61     RegionResolveCrate,
  62     CheckLoops,
  63     PluginRegistrar,
  64     StabilityIndex,
  65     CollectItem(D),
  66     CollectItemSig(D),
  67     Coherence,
  68     EffectCheck,
  69     Liveness,
  70     Resolve,
  71     EntryPoint,
  72     CheckEntryFn,
  73     CoherenceCheckTrait(D),
  74     CoherenceCheckImpl(D),
  75     CoherenceOverlapCheck(D),
  76     CoherenceOverlapCheckSpecial(D),
  77     CoherenceOverlapInherentCheck(D),
  78     CoherenceOrphanCheck(D),
  79     Variance,
  80     WfCheck(D),
  81     TypeckItemType(D),
  82     UnusedTraitCheck,
  83     CheckConst(D),
  84     Privacy,
  85     IntrinsicCheck(D),
  86     MatchCheck(D),
  87
  88     // Represents the MIR for a fn; also used as the task node for
  89     // things read/modify that MIR.
  90     Mir(D),
  91
  92     BorrowCheck(D),
  93     RvalueCheck(D),
  94     Reachability,
  95     DeadCheck,
  96     StabilityCheck(D),
  97     LateLintCheck,
  98     TransCrate,
  99     TransCrateItem(D),
 100     TransInlinedItem(D),
 101     TransWriteMetadata,
 102     LinkBinary,
 103
 104     // Nodes representing bits of computed IR in the tcx. Each shared
 105     // table in the tcx (or elsewhere) maps to one of these
 106     // nodes. Often we map multiple tables to the same node if there
 107     // is no point in distinguishing them (e.g., both the type and
 108     // predicates for an item wind up in `ItemSignature`).
 109     AssociatedItems(D),
 110     ItemSignature(D),
 111     TypeParamPredicates((D, D)),
 112     SizedConstraint(D),
 113     AdtDestructor(D),
 114     AssociatedItemDefIds(D),
 115     InherentImpls(D),
 116     TypeckTables(D),
 117     UsedTraitImports(D),
 118     MonomorphicConstEval(D),
 119
 120     // The set of impls for a given trait. Ultimately, it would be
 121     // nice to get more fine-grained here (e.g., to include a
 122     // simplified type), but we can't do that until we restructure the
 123     // HIR to distinguish the *header* of an impl from its body.  This
 124     // is because changes to the header may change the self-type of
 125     // the impl and hence would require us to be more conservative
 126     // than changes in the impl body.
 127     TraitImpls(D),
 128
 129     // Nodes representing caches. To properly handle a true cache, we
 130     // don't use a DepTrackingMap, but rather we push a task node.
 131     // Otherwise the write into the map would be incorrectly
 132     // attributed to the first task that happened to fill the cache,
 133     // which would yield an overly conservative dep-graph.
 134     TraitItems(D),
 135     ReprHints(D),
 136
 137     // Trait selection cache is a little funny. Given a trait
 138     // reference like `Foo: SomeTrait<Bar>`, there could be
 139     // arbitrarily many def-ids to map on in there (e.g., `Foo`,
 140     // `SomeTrait`, `Bar`). We could have a vector of them, but it
 141     // requires heap-allocation, and trait sel in general can be a
 142     // surprisingly hot path. So instead we pick two def-ids: the
 143     // trait def-id, and the first def-id in the input types. If there
 144     // is no def-id in the input types, then we use the trait def-id
 145     // again. So for example:
 146     //
 147     // - `i32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 148     // - `u32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 149     // - `Clone: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 150     // - `Vec<i32>: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Vec }`
 151     // - `String: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: String }`
 152     // - `Foo: Trait<Bar>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 153     // - `Foo: Trait<i32>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 154     // - `(Foo, Bar): Trait` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 155     // - `i32: Trait<Foo>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 156     //
 157     // You can see that we map many trait refs to the same
 158     // trait-select node.  This is not a problem, it just means
 159     // imprecision in our dep-graph tracking.  The important thing is
 160     // that for any given trait-ref, we always map to the **same**
 161     // trait-select node.
 162     TraitSelect { trait_def_id: D, input_def_id: D },
 163
 164     // For proj. cache, we just keep a list of all def-ids, since it is
 165     // not a hotspot.
 166     ProjectionCache { def_ids: Vec<D> },
 167 }
 168
 169 impl<D: Clone + Debug> DepNode<D> {
 170     /// Used in testing
 171     pub fn from_label_string(label: &str, data: D) -> Result<DepNode<D>, ()> {
 172         macro_rules! check {
 173             ($($name:ident,)*) => {
 174                 match label {
 175                     $(stringify!($name) => Ok(DepNode::$name(data)),)*
 176                     _ => Err(())
 177                 }
 178             }
 179         }
 180
 181         if label == "Krate" {
 182             // special case
 183             return Ok(DepNode::Krate);
 184         }
 185
 186         check! {
 187             CollectItem,
 188             BorrowCheck,
 189             Hir,
 190             HirBody,
 191             TransCrateItem,
 192             TypeckItemType,
 193             AssociatedItems,
 194             ItemSignature,
 195             AssociatedItemDefIds,
 196             InherentImpls,
 197             TypeckTables,
 198             UsedTraitImports,
 199             TraitImpls,
 200             ReprHints,
 201         }
 202     }
 203
 204     pub fn map_def<E, OP>(&self, mut op: OP) -> Option<DepNode<E>>
 205         where OP: FnMut(&D) -> Option<E>, E: Clone + Debug
 206     {
 207         use self::DepNode::*;
 208
 209         match *self {
 210             Krate => Some(Krate),
 211             CollectLanguageItems => Some(CollectLanguageItems),
 212             CheckStaticRecursion => Some(CheckStaticRecursion),
 213             ResolveLifetimes => Some(ResolveLifetimes),
 214             RegionResolveCrate => Some(RegionResolveCrate),
 215             CheckLoops => Some(CheckLoops),
 216             PluginRegistrar => Some(PluginRegistrar),
 217             StabilityIndex => Some(StabilityIndex),
 218             Coherence => Some(Coherence),
 219             EffectCheck => Some(EffectCheck),
 220             Liveness => Some(Liveness),
 221             Resolve => Some(Resolve),
 222             EntryPoint => Some(EntryPoint),
 223             CheckEntryFn => Some(CheckEntryFn),
 224             Variance => Some(Variance),
 225             UnusedTraitCheck => Some(UnusedTraitCheck),
 226             Privacy => Some(Privacy),
 227             Reachability => Some(Reachability),
 228             DeadCheck => Some(DeadCheck),
 229             LateLintCheck => Some(LateLintCheck),
 230             TransCrate => Some(TransCrate),
 231             TransWriteMetadata => Some(TransWriteMetadata),
 232             LinkBinary => Some(LinkBinary),
 233
 234             // work product names do not need to be mapped, because
 235             // they are always absolute.
 236             WorkProduct(ref id) => Some(WorkProduct(id.clone())),
 237
 238             Hir(ref d) => op(d).map(Hir),
 239             HirBody(ref d) => op(d).map(HirBody),
 240             MetaData(ref d) => op(d).map(MetaData),
 241             CollectItem(ref d) => op(d).map(CollectItem),
 242             CollectItemSig(ref d) => op(d).map(CollectItemSig),
 243             CoherenceCheckTrait(ref d) => op(d).map(CoherenceCheckTrait),
 244             CoherenceCheckImpl(ref d) => op(d).map(CoherenceCheckImpl),
 245             CoherenceOverlapCheck(ref d) => op(d).map(CoherenceOverlapCheck),
 246             CoherenceOverlapCheckSpecial(ref d) => op(d).map(CoherenceOverlapCheckSpecial),
 247             CoherenceOverlapInherentCheck(ref d) => op(d).map(CoherenceOverlapInherentCheck),
 248             CoherenceOrphanCheck(ref d) => op(d).map(CoherenceOrphanCheck),
 249             WfCheck(ref d) => op(d).map(WfCheck),
 250             TypeckItemType(ref d) => op(d).map(TypeckItemType),
 251             CheckConst(ref d) => op(d).map(CheckConst),
 252             IntrinsicCheck(ref d) => op(d).map(IntrinsicCheck),
 253             MatchCheck(ref d) => op(d).map(MatchCheck),
 254             Mir(ref d) => op(d).map(Mir),
 255             BorrowCheck(ref d) => op(d).map(BorrowCheck),
 256             RvalueCheck(ref d) => op(d).map(RvalueCheck),
 257             StabilityCheck(ref d) => op(d).map(StabilityCheck),
 258             TransCrateItem(ref d) => op(d).map(TransCrateItem),
 259             TransInlinedItem(ref d) => op(d).map(TransInlinedItem),
 260             AssociatedItems(ref d) => op(d).map(AssociatedItems),
 261             ItemSignature(ref d) => op(d).map(ItemSignature),
 262             TypeParamPredicates((ref item, ref param)) => {
 263                 Some(TypeParamPredicates((try_opt!(op(item)), try_opt!(op(param)))))
 264             }
 265             SizedConstraint(ref d) => op(d).map(SizedConstraint),
 266             AdtDestructor(ref d) => op(d).map(AdtDestructor),
 267             AssociatedItemDefIds(ref d) => op(d).map(AssociatedItemDefIds),
 268             InherentImpls(ref d) => op(d).map(InherentImpls),
 269             TypeckTables(ref d) => op(d).map(TypeckTables),
 270             UsedTraitImports(ref d) => op(d).map(UsedTraitImports),
 271             MonomorphicConstEval(ref d) => op(d).map(MonomorphicConstEval),
 272             TraitImpls(ref d) => op(d).map(TraitImpls),
 273             TraitItems(ref d) => op(d).map(TraitItems),
 274             ReprHints(ref d) => op(d).map(ReprHints),
 275             TraitSelect { ref trait_def_id, ref input_def_id } => {
 276                 op(trait_def_id).and_then(|trait_def_id| {
 277                     op(input_def_id).and_then(|input_def_id| {
 278                         Some(TraitSelect { trait_def_id: trait_def_id,
 279                                            input_def_id: input_def_id })
 280                     })
 281                 })
 282             }
 283             ProjectionCache { ref def_ids } => {
 284                 let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
 285                 def_ids.map(|d| ProjectionCache { def_ids: d })
 286             }
 287         }
 288     }
 289 }
 290
 291 /// A "work product" corresponds to a `.o` (or other) file that we
 292 /// save in between runs. These ids do not have a DefId but rather
 293 /// some independent path or string that persists between runs without
 294 /// the need to be mapped or unmapped. (This ensures we can serialize
 295 /// them even in the absence of a tcx.)
 296 #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 297 pub struct WorkProductId(pub String);