src/librustc_incremental/persist/preds.rs

   1 // Copyright 2012-2015 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 rustc::dep_graph::{DepGraphQuery, DepNode};
  12 use rustc::hir::def_id::DefId;
  13 use rustc_data_structures::fnv::FnvHashMap;
  14 use rustc_data_structures::graph::{DepthFirstTraversal, INCOMING, NodeIndex};
  15
  16 use super::hash::*;
  17 use ich::Fingerprint;
  18
  19 /// A data-structure that makes it easy to enumerate the hashable
  20 /// predecessors of any given dep-node.
  21 pub struct Predecessors<'query> {
  22     // - Keys: dep-nodes that may have work-products, output meta-data
  23     //   nodes.
  24     // - Values: transitive predecessors of the key that are hashable
  25     //   (e.g., HIR nodes, input meta-data nodes)
  26     pub inputs: FnvHashMap<&'query DepNode<DefId>, Vec<&'query DepNode<DefId>>>,
  27
  28     // - Keys: some hashable node
  29     // - Values: the hash thereof
  30     pub hashes: FnvHashMap<&'query DepNode<DefId>, Fingerprint>,
  31 }
  32
  33 impl<'q> Predecessors<'q> {
  34     pub fn new(query: &'q DepGraphQuery<DefId>, hcx: &mut HashContext) -> Self {
  35         // Find nodes for which we want to know the full set of preds
  36         let mut dfs = DepthFirstTraversal::new(&query.graph, INCOMING);
  37         let all_nodes = query.graph.all_nodes();
  38         let tcx = hcx.tcx;
  39
  40         let inputs: FnvHashMap<_, _> = all_nodes.iter()
  41             .enumerate()
  42             .filter(|&(_, node)| match node.data {
  43                 DepNode::WorkProduct(_) => true,
  44                 DepNode::MetaData(ref def_id) => def_id.is_local(),
  45
  46                 // if -Z query-dep-graph is passed, save more extended data
  47                 // to enable better unit testing
  48                 DepNode::TypeckItemBody(_) |
  49                 DepNode::TransCrateItem(_) => tcx.sess.opts.debugging_opts.query_dep_graph,
  50
  51                 _ => false,
  52             })
  53             .map(|(node_index, node)| {
  54                 dfs.reset(NodeIndex(node_index));
  55                 let inputs: Vec<_> = dfs.by_ref()
  56                     .map(|i| &all_nodes[i.node_id()].data)
  57                     .filter(|d| HashContext::is_hashable(d))
  58                     .collect();
  59                 (&node.data, inputs)
  60             })
  61             .collect();
  62
  63         let mut hashes = FnvHashMap();
  64         for input in inputs.values().flat_map(|v| v.iter().cloned()) {
  65             hashes.entry(input)
  66                   .or_insert_with(|| hcx.hash(input).unwrap());
  67         }
  68
  69         Predecessors {
  70             inputs: inputs,
  71             hashes: hashes,
  72         }
  73     }
  74 }