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