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     MirKrate,
  91     Mir(D),
  92     MirShim(Vec<D>),
  93
  94     BorrowCheckKrate,
  95     BorrowCheck(D),
  96     RvalueCheck(D),
  97     Reachability,
  98     DeadCheck,
  99     StabilityCheck(D),
 100     LateLintCheck,
 101     TransCrate,
 102     TransCrateItem(D),
 103     TransInlinedItem(D),
 104     TransWriteMetadata,
 105     LinkBinary,
 106
 107     // Nodes representing bits of computed IR in the tcx. Each shared
 108     // table in the tcx (or elsewhere) maps to one of these
 109     // nodes. Often we map multiple tables to the same node if there
 110     // is no point in distinguishing them (e.g., both the type and
 111     // predicates for an item wind up in `ItemSignature`).
 112     AssociatedItems(D),
 113     ItemSignature(D),
 114     TypeParamPredicates((D, D)),
 115     SizedConstraint(D),
 116     AdtDestructor(D),
 117     AssociatedItemDefIds(D),
 118     InherentImpls(D),
 119     TypeckBodiesKrate,
 120     TypeckTables(D),
 121     UsedTraitImports(D),
 122     MonomorphicConstEval(D),
 123
 124     // The set of impls for a given trait. Ultimately, it would be
 125     // nice to get more fine-grained here (e.g., to include a
 126     // simplified type), but we can't do that until we restructure the
 127     // HIR to distinguish the *header* of an impl from its body.  This
 128     // is because changes to the header may change the self-type of
 129     // the impl and hence would require us to be more conservative
 130     // than changes in the impl body.
 131     TraitImpls(D),
 132
 133     // Nodes representing caches. To properly handle a true cache, we
 134     // don't use a DepTrackingMap, but rather we push a task node.
 135     // Otherwise the write into the map would be incorrectly
 136     // attributed to the first task that happened to fill the cache,
 137     // which would yield an overly conservative dep-graph.
 138     TraitItems(D),
 139     ReprHints(D),
 140
 141     // Trait selection cache is a little funny. Given a trait
 142     // reference like `Foo: SomeTrait<Bar>`, there could be
 143     // arbitrarily many def-ids to map on in there (e.g., `Foo`,
 144     // `SomeTrait`, `Bar`). We could have a vector of them, but it
 145     // requires heap-allocation, and trait sel in general can be a
 146     // surprisingly hot path. So instead we pick two def-ids: the
 147     // trait def-id, and the first def-id in the input types. If there
 148     // is no def-id in the input types, then we use the trait def-id
 149     // again. So for example:
 150     //
 151     // - `i32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 152     // - `u32: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 153     // - `Clone: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Clone }`
 154     // - `Vec<i32>: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: Vec }`
 155     // - `String: Clone` -> `TraitSelect { trait_def_id: Clone, self_def_id: String }`
 156     // - `Foo: Trait<Bar>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 157     // - `Foo: Trait<i32>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 158     // - `(Foo, Bar): Trait` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 159     // - `i32: Trait<Foo>` -> `TraitSelect { trait_def_id: Trait, self_def_id: Foo }`
 160     //
 161     // You can see that we map many trait refs to the same
 162     // trait-select node.  This is not a problem, it just means
 163     // imprecision in our dep-graph tracking.  The important thing is
 164     // that for any given trait-ref, we always map to the **same**
 165     // trait-select node.
 166     TraitSelect { trait_def_id: D, input_def_id: D },
 167
 168     // For proj. cache, we just keep a list of all def-ids, since it is
 169     // not a hotspot.
 170     ProjectionCache { def_ids: Vec<D> },
 171 }
 172
 173 impl<D: Clone + Debug> DepNode<D> {
 174     /// Used in testing
 175     pub fn from_label_string(label: &str, data: D) -> Result<DepNode<D>, ()> {
 176         macro_rules! check {
 177             ($($name:ident,)*) => {
 178                 match label {
 179                     $(stringify!($name) => Ok(DepNode::$name(data)),)*
 180                     _ => Err(())
 181                 }
 182             }
 183         }
 184
 185         if label == "Krate" {
 186             // special case
 187             return Ok(DepNode::Krate);
 188         }
 189
 190         check! {
 191             CollectItem,
 192             BorrowCheck,
 193             Hir,
 194             HirBody,
 195             TransCrateItem,
 196             TypeckItemType,
 197             AssociatedItems,
 198             ItemSignature,
 199             AssociatedItemDefIds,
 200             InherentImpls,
 201             TypeckTables,
 202             UsedTraitImports,
 203             TraitImpls,
 204             ReprHints,
 205         }
 206     }
 207
 208     pub fn map_def<E, OP>(&self, mut op: OP) -> Option<DepNode<E>>
 209         where OP: FnMut(&D) -> Option<E>, E: Clone + Debug
 210     {
 211         use self::DepNode::*;
 212
 213         match *self {
 214             Krate => Some(Krate),
 215             BorrowCheckKrate => Some(BorrowCheckKrate),
 216             MirKrate => Some(MirKrate),
 217             TypeckBodiesKrate => Some(TypeckBodiesKrate),
 218             CollectLanguageItems => Some(CollectLanguageItems),
 219             CheckStaticRecursion => Some(CheckStaticRecursion),
 220             ResolveLifetimes => Some(ResolveLifetimes),
 221             RegionResolveCrate => Some(RegionResolveCrate),
 222             CheckLoops => Some(CheckLoops),
 223             PluginRegistrar => Some(PluginRegistrar),
 224             StabilityIndex => Some(StabilityIndex),
 225             Coherence => Some(Coherence),
 226             EffectCheck => Some(EffectCheck),
 227             Liveness => Some(Liveness),
 228             Resolve => Some(Resolve),
 229             EntryPoint => Some(EntryPoint),
 230             CheckEntryFn => Some(CheckEntryFn),
 231             Variance => Some(Variance),
 232             UnusedTraitCheck => Some(UnusedTraitCheck),
 233             Privacy => Some(Privacy),
 234             Reachability => Some(Reachability),
 235             DeadCheck => Some(DeadCheck),
 236             LateLintCheck => Some(LateLintCheck),
 237             TransCrate => Some(TransCrate),
 238             TransWriteMetadata => Some(TransWriteMetadata),
 239             LinkBinary => Some(LinkBinary),
 240
 241             // work product names do not need to be mapped, because
 242             // they are always absolute.
 243             WorkProduct(ref id) => Some(WorkProduct(id.clone())),
 244
 245             Hir(ref d) => op(d).map(Hir),
 246             HirBody(ref d) => op(d).map(HirBody),
 247             MetaData(ref d) => op(d).map(MetaData),
 248             CollectItem(ref d) => op(d).map(CollectItem),
 249             CollectItemSig(ref d) => op(d).map(CollectItemSig),
 250             CoherenceCheckTrait(ref d) => op(d).map(CoherenceCheckTrait),
 251             CoherenceCheckImpl(ref d) => op(d).map(CoherenceCheckImpl),
 252             CoherenceOverlapCheck(ref d) => op(d).map(CoherenceOverlapCheck),
 253             CoherenceOverlapCheckSpecial(ref d) => op(d).map(CoherenceOverlapCheckSpecial),
 254             CoherenceOverlapInherentCheck(ref d) => op(d).map(CoherenceOverlapInherentCheck),
 255             CoherenceOrphanCheck(ref d) => op(d).map(CoherenceOrphanCheck),
 256             WfCheck(ref d) => op(d).map(WfCheck),
 257             TypeckItemType(ref d) => op(d).map(TypeckItemType),
 258             CheckConst(ref d) => op(d).map(CheckConst),
 259             IntrinsicCheck(ref d) => op(d).map(IntrinsicCheck),
 260             MatchCheck(ref d) => op(d).map(MatchCheck),
 261             Mir(ref d) => op(d).map(Mir),
 262             MirShim(ref def_ids) => {
 263                 let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
 264                 def_ids.map(MirShim)
 265             }
 266             BorrowCheck(ref d) => op(d).map(BorrowCheck),
 267             RvalueCheck(ref d) => op(d).map(RvalueCheck),
 268             StabilityCheck(ref d) => op(d).map(StabilityCheck),
 269             TransCrateItem(ref d) => op(d).map(TransCrateItem),
 270             TransInlinedItem(ref d) => op(d).map(TransInlinedItem),
 271             AssociatedItems(ref d) => op(d).map(AssociatedItems),
 272             ItemSignature(ref d) => op(d).map(ItemSignature),
 273             TypeParamPredicates((ref item, ref param)) => {
 274                 Some(TypeParamPredicates((try_opt!(op(item)), try_opt!(op(param)))))
 275             }
 276             SizedConstraint(ref d) => op(d).map(SizedConstraint),
 277             AdtDestructor(ref d) => op(d).map(AdtDestructor),
 278             AssociatedItemDefIds(ref d) => op(d).map(AssociatedItemDefIds),
 279             InherentImpls(ref d) => op(d).map(InherentImpls),
 280             TypeckTables(ref d) => op(d).map(TypeckTables),
 281             UsedTraitImports(ref d) => op(d).map(UsedTraitImports),
 282             MonomorphicConstEval(ref d) => op(d).map(MonomorphicConstEval),
 283             TraitImpls(ref d) => op(d).map(TraitImpls),
 284             TraitItems(ref d) => op(d).map(TraitItems),
 285             ReprHints(ref d) => op(d).map(ReprHints),
 286             TraitSelect { ref trait_def_id, ref input_def_id } => {
 287                 op(trait_def_id).and_then(|trait_def_id| {
 288                     op(input_def_id).and_then(|input_def_id| {
 289                         Some(TraitSelect { trait_def_id: trait_def_id,
 290                                            input_def_id: input_def_id })
 291                     })
 292                 })
 293             }
 294             ProjectionCache { ref def_ids } => {
 295                 let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
 296                 def_ids.map(|d| ProjectionCache { def_ids: d })
 297             }
 298         }
 299     }
 300 }
 301
 302 /// A "work product" corresponds to a `.o` (or other) file that we
 303 /// save in between runs. These ids do not have a DefId but rather
 304 /// some independent path or string that persists between runs without
 305 /// the need to be mapped or unmapped. (This ensures we can serialize
 306 /// them even in the absence of a tcx.)
 307 #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 308 pub struct WorkProductId(pub String);