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