diff options
| -rw-r--r-- | src/librustc/cfg/mod.rs | 2 | ||||
| -rw-r--r-- | src/librustc/dep_graph/query.rs | 21 | ||||
| -rw-r--r-- | src/librustc/infer/region_inference/mod.rs | 4 | ||||
| -rw-r--r-- | src/librustc_data_structures/graph/mod.rs | 14 | ||||
| -rw-r--r-- | src/librustc_incremental/assert_dep_graph.rs | 2 | ||||
| -rw-r--r-- | src/librustc_incremental/persist/data.rs | 34 | ||||
| -rw-r--r-- | src/librustc_incremental/persist/load.rs | 17 | ||||
| -rw-r--r-- | src/librustc_incremental/persist/save.rs | 172 | ||||
| -rw-r--r-- | src/librustc_incremental/persist/util.rs | 35 | ||||
| -rw-r--r-- | src/librustc_trans/base.rs | 3 |
10 files changed, 221 insertions, 83 deletions
diff --git a/src/librustc/cfg/mod.rs b/src/librustc/cfg/mod.rs index 617e2ed2f1a..d06f51073df 100644 --- a/src/librustc/cfg/mod.rs +++ b/src/librustc/cfg/mod.rs @@ -64,7 +64,7 @@ impl CFG { } pub fn node_is_reachable(&self, id: ast::NodeId) -> bool { - self.graph.depth_traverse(self.entry) + self.graph.depth_traverse(self.entry, graph::OUTGOING) .any(|idx| self.graph.node_data(idx).id() == id) } } diff --git a/src/librustc/dep_graph/query.rs b/src/librustc/dep_graph/query.rs index acc6660da6e..93248edb197 100644 --- a/src/librustc/dep_graph/query.rs +++ b/src/librustc/dep_graph/query.rs @@ -9,7 +9,7 @@ // except according to those terms. use rustc_data_structures::fnv::FnvHashMap; -use rustc_data_structures::graph::{Graph, NodeIndex}; +use rustc_data_structures::graph::{Direction, INCOMING, Graph, NodeIndex, OUTGOING}; use std::fmt::Debug; use std::hash::Hash; @@ -63,11 +63,9 @@ impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> { .collect() } - /// All nodes reachable from `node`. In other words, things that - /// will have to be recomputed if `node` changes. - pub fn transitive_dependents(&self, node: DepNode<D>) -> Vec<DepNode<D>> { + fn reachable_nodes(&self, node: DepNode<D>, direction: Direction) -> Vec<DepNode<D>> { if let Some(&index) = self.indices.get(&node) { - self.graph.depth_traverse(index) + self.graph.depth_traverse(index, direction) .map(|s| self.graph.node_data(s).clone()) .collect() } else { @@ -75,8 +73,19 @@ impl<D: Clone + Debug + Hash + Eq> DepGraphQuery<D> { } } + /// All nodes reachable from `node`. In other words, things that + /// will have to be recomputed if `node` changes. + pub fn transitive_successors(&self, node: DepNode<D>) -> Vec<DepNode<D>> { + self.reachable_nodes(node, OUTGOING) + } + + /// All nodes that can reach `node`. + pub fn transitive_predecessors(&self, node: DepNode<D>) -> Vec<DepNode<D>> { + self.reachable_nodes(node, INCOMING) + } + /// Just the outgoing edges from `node`. - pub fn immediate_dependents(&self, node: DepNode<D>) -> Vec<DepNode<D>> { + pub fn immediate_successors(&self, node: DepNode<D>) -> Vec<DepNode<D>> { if let Some(&index) = self.indices.get(&node) { self.graph.successor_nodes(index) .map(|s| self.graph.node_data(s).clone()) diff --git a/src/librustc/infer/region_inference/mod.rs b/src/librustc/infer/region_inference/mod.rs index 9d2d52015e3..5312d030525 100644 --- a/src/librustc/infer/region_inference/mod.rs +++ b/src/librustc/infer/region_inference/mod.rs @@ -20,7 +20,7 @@ pub use self::VarValue::*; use super::{RegionVariableOrigin, SubregionOrigin, MiscVariable}; use super::unify_key; -use rustc_data_structures::graph::{self, Direction, NodeIndex}; +use rustc_data_structures::graph::{self, Direction, NodeIndex, OUTGOING}; use rustc_data_structures::unify::{self, UnificationTable}; use middle::free_region::FreeRegionMap; use ty::{self, Ty, TyCtxt}; @@ -872,7 +872,7 @@ impl<'a, 'gcx, 'tcx> RegionVarBindings<'a, 'gcx, 'tcx> { let seeds: Vec<_> = givens.iter().cloned().collect(); for (fr, vid) in seeds { let seed_index = NodeIndex(vid.index as usize); - for succ_index in graph.depth_traverse(seed_index) { + for succ_index in graph.depth_traverse(seed_index, OUTGOING) { let succ_index = succ_index.0 as u32; if succ_index < self.num_vars() { let succ_vid = RegionVid { index: succ_index }; diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs index 99a87d1e760..731471b0600 100644 --- a/src/librustc_data_structures/graph/mod.rs +++ b/src/librustc_data_structures/graph/mod.rs @@ -292,11 +292,15 @@ impl<N: Debug, E: Debug> Graph<N, E> { } } - pub fn depth_traverse<'a>(&'a self, start: NodeIndex) -> DepthFirstTraversal<'a, N, E> { + pub fn depth_traverse<'a>(&'a self, + start: NodeIndex, + direction: Direction) + -> DepthFirstTraversal<'a, N, E> { DepthFirstTraversal { graph: self, stack: vec![start], visited: BitVector::new(self.nodes.len()), + direction: direction, } } } @@ -371,6 +375,7 @@ pub struct DepthFirstTraversal<'g, N: 'g, E: 'g> { graph: &'g Graph<N, E>, stack: Vec<NodeIndex>, visited: BitVector, + direction: Direction, } impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { @@ -382,9 +387,10 @@ impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { continue; } - for (_, edge) in self.graph.outgoing_edges(idx) { - if !self.visited.contains(edge.target().node_id()) { - self.stack.push(edge.target()); + for (_, edge) in self.graph.adjacent_edges(idx, self.direction) { + let target = edge.source_or_target(self.direction); + if !self.visited.contains(target.node_id()) { + self.stack.push(target); } } diff --git a/src/librustc_incremental/assert_dep_graph.rs b/src/librustc_incremental/assert_dep_graph.rs index b74e7e21226..e426e4d5b44 100644 --- a/src/librustc_incremental/assert_dep_graph.rs +++ b/src/librustc_incremental/assert_dep_graph.rs @@ -195,7 +195,7 @@ fn check_paths<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, }; for &(_, source_def_id, source_dep_node) in sources { - let dependents = query.transitive_dependents(source_dep_node); + let dependents = query.transitive_successors(source_dep_node); for &(target_span, ref target_pass, _, ref target_dep_node) in targets { if !dependents.contains(&target_dep_node) { tcx.sess.span_err( diff --git a/src/librustc_incremental/persist/data.rs b/src/librustc_incremental/persist/data.rs index 37d5f8937f1..5c68552b718 100644 --- a/src/librustc_incremental/persist/data.rs +++ b/src/librustc_incremental/persist/data.rs @@ -14,10 +14,40 @@ use rustc::dep_graph::DepNode; use super::directory::DefPathIndex; +/// Data for use when recompiling the **current crate**. #[derive(Debug, RustcEncodable, RustcDecodable)] pub struct SerializedDepGraph { pub nodes: Vec<DepNode<DefPathIndex>>, pub edges: Vec<SerializedEdge>, + + /// These are hashes of two things: + /// - the HIR nodes in this crate + /// - the metadata nodes from dependent crates we use + /// + /// In each case, we store a hash summarizing the contents of + /// those items as they were at the time we did this compilation. + /// In the case of HIR nodes, this hash is derived by walking the + /// HIR itself. In the case of metadata nodes, the hash is loaded + /// from saved state. + /// + /// When we do the next compile, we will load these back up and + /// compare them against the hashes we see at that time, which + /// will tell us what has changed, either in this crate or in some + /// crate that we depend on. + pub hashes: Vec<SerializedHash>, +} + +/// Data for use when downstream crates get recompiled. +#[derive(Debug, RustcEncodable, RustcDecodable)] +pub struct SerializedMetadataHashes { + /// For each def-id defined in this crate that appears in the + /// metadata, we hash all the inputs that were used when producing + /// the metadata. We save this after compilation is done. Then, + /// when some downstream crate is being recompiled, it can compare + /// the hashes we saved against the hashes that it saw from + /// before; this will tell it which of the items in this crate + /// changed, which in turn implies what items in the downstream + /// crate need to be recompiled. pub hashes: Vec<SerializedHash>, } @@ -25,7 +55,9 @@ pub type SerializedEdge = (DepNode<DefPathIndex>, DepNode<DefPathIndex>); #[derive(Debug, RustcEncodable, RustcDecodable)] pub struct SerializedHash { - pub index: DefPathIndex, + /// node being hashed; either a Hir or MetaData variant, in + /// practice + pub node: DepNode<DefPathIndex>, /// the hash itself, computed by `calculate_item_hash` pub hash: u64, diff --git a/src/librustc_incremental/persist/load.rs b/src/librustc_incremental/persist/load.rs index f9e479745d1..35ef0917517 100644 --- a/src/librustc_incremental/persist/load.rs +++ b/src/librustc_incremental/persist/load.rs @@ -10,7 +10,6 @@ //! Code to save/load the dep-graph from files. -use calculate_svh::SvhCalculate; use rbml::Error; use rbml::opaque::Decoder; use rustc::dep_graph::DepNode; @@ -131,20 +130,20 @@ pub fn decode_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, } fn initial_dirty_nodes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - hashed_items: &[SerializedHash], + hashes: &[SerializedHash], retraced: &RetracedDefIdDirectory) -> DirtyNodes { let mut items_removed = false; let mut dirty_nodes = FnvHashSet(); - for hashed_item in hashed_items { - match retraced.def_id(hashed_item.index) { - Some(def_id) => { + for hash in hashes { + match hash.node.map_def(|&i| retraced.def_id(i)) { + Some(dep_node) => { // FIXME(#32753) -- should we use a distinct hash here - let current_hash = tcx.calculate_item_hash(def_id); + let current_hash = dep_node.hash(tcx).unwrap(); debug!("initial_dirty_nodes: hash of {:?} is {:?}, was {:?}", - def_id, current_hash, hashed_item.hash); - if current_hash != hashed_item.hash { - dirty_nodes.insert(DepNode::Hir(def_id)); + dep_node, current_hash, hash.hash); + if current_hash != hash.hash { + dirty_nodes.insert(dep_node); } } None => { diff --git a/src/librustc_incremental/persist/save.rs b/src/librustc_incremental/persist/save.rs index cbb3464f3ef..40191cf758d 100644 --- a/src/librustc_incremental/persist/save.rs +++ b/src/librustc_incremental/persist/save.rs @@ -8,13 +8,14 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use calculate_svh::SvhCalculate; use rbml::opaque::Encoder; use rustc::dep_graph::DepNode; use rustc::ty::TyCtxt; use rustc_serialize::{Encodable as RustcEncodable}; +use std::hash::{Hasher, SipHasher}; use std::io::{self, Cursor, Write}; use std::fs::{self, File}; +use std::path::PathBuf; use super::data::*; use super::directory::*; @@ -23,47 +24,57 @@ use super::util::*; pub fn save_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { let _ignore = tcx.dep_graph.in_ignore(); - if let Some(dep_graph) = dep_graph_path(tcx) { - // FIXME(#32754) lock file? - - // delete the old dep-graph, if any - if dep_graph.exists() { - match fs::remove_file(&dep_graph) { - Ok(()) => { } - Err(err) => { - tcx.sess.err( - &format!("unable to delete old dep-graph at `{}`: {}", - dep_graph.display(), err)); - return; - } - } - } + save_in(tcx, dep_graph_path(tcx), encode_dep_graph); + save_in(tcx, metadata_hash_path(tcx), encode_metadata_hashes); +} - // generate the data in a memory buffer - let mut wr = Cursor::new(Vec::new()); - match encode_dep_graph(tcx, &mut Encoder::new(&mut wr)) { +fn save_in<'a,'tcx,F>(tcx: TyCtxt<'a, 'tcx, 'tcx>, opt_path_buf: Option<PathBuf>, encode: F) + where F: FnOnce(TyCtxt<'a, 'tcx, 'tcx>, &mut Encoder) -> io::Result<()> +{ + let path_buf = match opt_path_buf { + Some(p) => p, + None => return + }; + + // FIXME(#32754) lock file? + + // delete the old dep-graph, if any + if path_buf.exists() { + match fs::remove_file(&path_buf) { Ok(()) => { } Err(err) => { tcx.sess.err( - &format!("could not encode dep-graph to `{}`: {}", - dep_graph.display(), err)); + &format!("unable to delete old dep-graph at `{}`: {}", + path_buf.display(), err)); return; } } + } - // write the data out - let data = wr.into_inner(); - match - File::create(&dep_graph) - .and_then(|mut file| file.write_all(&data)) - { - Ok(_) => { } - Err(err) => { - tcx.sess.err( - &format!("failed to write dep-graph to `{}`: {}", - dep_graph.display(), err)); - return; - } + // generate the data in a memory buffer + let mut wr = Cursor::new(Vec::new()); + match encode(tcx, &mut Encoder::new(&mut wr)) { + Ok(()) => { } + Err(err) => { + tcx.sess.err( + &format!("could not encode dep-graph to `{}`: {}", + path_buf.display(), err)); + return; + } + } + + // write the data out + let data = wr.into_inner(); + match + File::create(&path_buf) + .and_then(|mut file| file.write_all(&data)) + { + Ok(_) => { } + Err(err) => { + tcx.sess.err( + &format!("failed to write dep-graph to `{}`: {}", + path_buf.display(), err)); + return; } } } @@ -71,35 +82,20 @@ pub fn save_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { pub fn encode_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, encoder: &mut Encoder) -> io::Result<()> { - // Here we take advantage of how RBML allows us to skip around - // and encode the depgraph as a two-part structure: - // - // ``` - // <dep-graph>[SerializedDepGraph]</dep-graph> // tag 0 - // <directory>[DefIdDirectory]</directory> // tag 1 - // ``` - // - // Then later we can load the directory by skipping to find tag 1. - let query = tcx.dep_graph.query(); let mut builder = DefIdDirectoryBuilder::new(tcx); - // Create hashes for things we can persist. + // Create hashes for inputs. let hashes = query.nodes() .into_iter() - .filter_map(|dep_node| match dep_node { - DepNode::Hir(def_id) => { - assert!(def_id.is_local()); - builder.add(def_id) - .map(|index| { - // FIXME(#32753) -- should we use a distinct hash here - let hash = tcx.calculate_item_hash(def_id); - SerializedHash { index: index, hash: hash } - }) - } - _ => None + .filter_map(|dep_node| { + dep_node.hash(tcx) + .map(|hash| { + let node = builder.map(dep_node).unwrap(); + SerializedHash { node: node, hash: hash } + }) }) .collect(); @@ -133,3 +129,67 @@ pub fn encode_dep_graph<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, Ok(()) } +pub fn encode_metadata_hashes<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + encoder: &mut Encoder) + -> io::Result<()> +{ + let query = tcx.dep_graph.query(); + + let mut builder = DefIdDirectoryBuilder::new(tcx); + + let serialized_hashes = { + // Identify the `MetaData(X)` nodes where `X` is local. These are + // the metadata items we export. Downstream crates will want to + // see a hash that tells them whether we might have changed the + // metadata for a given item since they last compiled. + let meta_data_def_ids = + query.nodes() + .into_iter() + .filter_map(|dep_node| match dep_node { + DepNode::MetaData(def_id) if def_id.is_local() => Some(def_id), + _ => None, + }); + + // To create the hash for each item `X`, we don't hash the raw + // bytes of the metadata (though in principle we could). Instead, + // we walk the predecessors of `MetaData(X)` from the + // dep-graph. This corresponds to all the inputs that were read to + // construct the metadata. To create the hash for the metadata, we + // hash (the hash of) all of those inputs. + let hashes = + meta_data_def_ids + .map(|def_id| { + let mut state = SipHasher::new(); + for node in query.transitive_predecessors(DepNode::MetaData(def_id)) { + if let Some(hash) = node.hash(tcx) { + state.write_u64(hash.to_le()); + } + } + (def_id, state.finish()) + }); + + // Now create the `SerializedHash` data structures that others + // will load later. + let hashes = + hashes + .map(|(def_id, hash)| { + let index = builder.add(def_id).unwrap(); + SerializedHash { + node: DepNode::MetaData(index), + hash: hash + } + }); + + // Collect these up into a vector. + SerializedMetadataHashes { + hashes: hashes.collect() + } + }; + + // Encode everything. + let directory = builder.into_directory(); + try!(directory.encode(encoder)); + try!(serialized_hashes.encode(encoder)); + + Ok(()) +} diff --git a/src/librustc_incremental/persist/util.rs b/src/librustc_incremental/persist/util.rs index 754292ba383..8a345583123 100644 --- a/src/librustc_incremental/persist/util.rs +++ b/src/librustc_incremental/persist/util.rs @@ -8,6 +8,9 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use calculate_svh::SvhCalculate; +use rustc::dep_graph::DepNode; +use rustc::hir::def_id::DefId; use rustc::middle::cstore::LOCAL_CRATE; use rustc::ty::TyCtxt; @@ -16,6 +19,14 @@ use std::io; use std::path::{PathBuf, Path}; pub fn dep_graph_path(tcx: TyCtxt) -> Option<PathBuf> { + path(tcx, "local") +} + +pub fn metadata_hash_path(tcx: TyCtxt) -> Option<PathBuf> { + path(tcx, "metadata") +} + +fn path(tcx: TyCtxt, suffix: &str) -> Option<PathBuf> { // For now, just save/load dep-graph from // directory/dep_graph.rbml tcx.sess.opts.incremental.as_ref().and_then(|incr_dir| { @@ -31,9 +42,10 @@ pub fn dep_graph_path(tcx: TyCtxt) -> Option<PathBuf> { let crate_name = tcx.crate_name(LOCAL_CRATE); let crate_disambiguator = tcx.crate_disambiguator(LOCAL_CRATE); - let file_name = format!("dep-graph-{}-{}.bin", + let file_name = format!("{}-{}.{}.bin", crate_name, - crate_disambiguator); + crate_disambiguator, + suffix); Some(incr_dir.join(file_name)) }) } @@ -58,3 +70,22 @@ fn create_dir_racy(path: &Path) -> io::Result<()> { Err(e) => Err(e), } } + +pub trait DepNodeHash { + /// Hash this dep-node, if it is of the kind that we know how to + /// hash. + fn hash<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option<u64>; +} + +impl DepNodeHash for DepNode<DefId> { + fn hash<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option<u64> { + match *self { + DepNode::Hir(def_id) => { + // FIXME(#32753) -- should we use a distinct hash here + assert!(def_id.is_local()); + Some(tcx.calculate_item_hash(def_id)) + } + _ => None + } + } +} diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs index 65c3aa12ba6..481154ba29f 100644 --- a/src/librustc_trans/base.rs +++ b/src/librustc_trans/base.rs @@ -47,6 +47,7 @@ use rustc::dep_graph::DepNode; use rustc::hir::map as hir_map; use rustc::util::common::time; use rustc::mir::mir_map::MirMap; +use rustc_data_structures::graph::OUTGOING; use session::config::{self, NoDebugInfo, FullDebugInfo}; use session::Session; use _match; @@ -1368,7 +1369,7 @@ fn build_cfg<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, // return slot alloca. This can cause errors related to clean-up due to // the clobbering of the existing value in the return slot. fn has_nested_returns(tcx: TyCtxt, cfg: &cfg::CFG, blk_id: ast::NodeId) -> bool { - for index in cfg.graph.depth_traverse(cfg.entry) { + for index in cfg.graph.depth_traverse(cfg.entry, OUTGOING) { let n = cfg.graph.node_data(index); match tcx.map.find(n.id()) { Some(hir_map::NodeExpr(ex)) => { |