src/librustc_incremental/persist/preds/mod.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::ich::Fingerprint;
  14 use rustc_data_structures::fx::FxHashMap;
  15 use rustc_data_structures::graph::{Graph, NodeIndex};
  16
  17 use super::hash::*;
  18
  19 mod compress;
  20
  21 /// A data-structure that makes it easy to enumerate the hashable
  22 /// predecessors of any given dep-node.
  23 pub struct Predecessors<'query> {
  24     // A reduced version of the input graph that contains fewer nodes.
  25     // This is intended to keep all of the base inputs (i.e., HIR
  26     // nodes) and all of the "work-products" we may care about
  27     // later. Other nodes may be retained if it keeps the overall size
  28     // of the graph down.
  29     pub reduced_graph: Graph<&'query DepNode<DefId>, ()>,
  30
  31     // These are output nodes that have no incoming edges. We have to
  32     // track these specially because, when we load the data back up
  33     // again, we want to make sure and recreate these nodes (we want
  34     // to recreate the nodes where all incoming edges are clean; but
  35     // since we ordinarily just serialize edges, we wind up just
  36     // forgetting that bootstrap outputs even exist in that case.)
  37     pub bootstrap_outputs: Vec<&'query DepNode<DefId>>,
  38
  39     // For the inputs (hir/foreign-metadata), we include hashes.
  40     pub hashes: FxHashMap<&'query DepNode<DefId>, Fingerprint>,
  41 }
  42
  43 impl<'q> Predecessors<'q> {
  44     pub fn new(query: &'q DepGraphQuery<DefId>, hcx: &mut HashContext) -> Self {
  45         let tcx = hcx.tcx;
  46
  47         // Find the set of "start nodes". These are nodes that we will
  48         // possibly query later.
  49         let is_output = |node: &DepNode<DefId>| -> bool {
  50             match *node {
  51                 DepNode::WorkProduct(_) => true,
  52                 DepNode::MetaData(ref def_id) => {
  53                     // We do *not* create dep-nodes for the current crate's
  54                     // metadata anymore, just for metadata that we import/read
  55                     // from other crates.
  56                     debug_assert!(!def_id.is_local());
  57                     false
  58                 }
  59                 // if -Z query-dep-graph is passed, save more extended data
  60                 // to enable better unit testing
  61                 DepNode::TypeckTables(_) |
  62                 DepNode::TransCrateItem(_) => tcx.sess.opts.debugging_opts.query_dep_graph,
  63
  64                 _ => false,
  65             }
  66         };
  67
  68         // Reduce the graph to the most important nodes.
  69         let compress::Reduction { graph, input_nodes } =
  70             compress::reduce_graph(&query.graph, HashContext::is_hashable, |n| is_output(n));
  71
  72         let mut hashes = FxHashMap();
  73         for input_index in input_nodes {
  74             let input = *graph.node_data(input_index);
  75             debug!("computing hash for input node `{:?}`", input);
  76             hashes.entry(input)
  77                   .or_insert_with(|| hcx.hash(input).unwrap());
  78         }
  79
  80         if tcx.sess.opts.debugging_opts.query_dep_graph {
  81             // Not all inputs might have been reachable from an output node,
  82             // but we still want their hash for our unit tests.
  83             let hir_nodes = query.graph.all_nodes().iter().filter_map(|node| {
  84                 match node.data {
  85                     DepNode::Hir(_) => Some(&node.data),
  86                     _ => None,
  87                 }
  88             });
  89
  90             for node in hir_nodes {
  91                 hashes.entry(node)
  92                       .or_insert_with(|| hcx.hash(node).unwrap());
  93             }
  94         }
  95
  96         let bootstrap_outputs: Vec<&'q DepNode<DefId>> =
  97             (0 .. graph.len_nodes())
  98             .map(NodeIndex)
  99             .filter(|&n| graph.incoming_edges(n).next().is_none())
 100             .map(|n| *graph.node_data(n))
 101             .filter(|n| is_output(n))
 102             .collect();
 103
 104         Predecessors {
 105             reduced_graph: graph,
 106             bootstrap_outputs: bootstrap_outputs,
 107             hashes: hashes,
 108         }
 109     }
 110 }