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