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