1 //! The data that we will serialize and deserialize.
3 //! The dep-graph is serialized as a sequence of NodeInfo, with the dependencies
4 //! specified inline. The total number of nodes and edges are stored as the last
5 //! 16 bytes of the file, so we can find them easily at decoding time.
7 //! The serialisation is performed on-demand when each node is emitted. Using this
8 //! scheme, we do not need to keep the current graph in memory.
10 //! The deserisalisation is performed manually, in order to convert from the stored
11 //! sequence of NodeInfos to the different arrays in SerializedDepGraph. Since the
12 //! node and edge count are stored at the end of the file, all the arrays can be
13 //! pre-allocated with the right length.
15 use super::query::DepGraphQuery;
16 use super::{DepKind, DepNode, DepNodeIndex};
17 use rustc_data_structures::fingerprint::Fingerprint;
18 use rustc_data_structures::fx::FxHashMap;
19 use rustc_data_structures::profiling::SelfProfilerRef;
20 use rustc_data_structures::sync::Lock;
21 use rustc_index::vec::{Idx, IndexVec};
22 use rustc_serialize::opaque::{self, FileEncodeResult, FileEncoder, IntEncodedWithFixedSize};
23 use rustc_serialize::{Decodable, Decoder, Encodable};
24 use smallvec::SmallVec;
25 use std::convert::TryInto;
27 // The maximum value of `SerializedDepNodeIndex` leaves the upper two bits
28 // unused so that we can store multiple index types in `CompressedHybridIndex`,
29 // and use those bits to encode which index type it contains.
30 rustc_index::newtype_index! {
31 pub struct SerializedDepNodeIndex {
36 /// Data for use when recompiling the **current crate**.
38 pub struct SerializedDepGraph<K: DepKind> {
39 /// The set of all DepNodes in the graph
40 nodes: IndexVec<SerializedDepNodeIndex, DepNode<K>>,
41 /// The set of all Fingerprints in the graph. Each Fingerprint corresponds to
42 /// the DepNode at the same index in the nodes vector.
43 fingerprints: IndexVec<SerializedDepNodeIndex, Fingerprint>,
44 /// For each DepNode, stores the list of edges originating from that
45 /// DepNode. Encoded as a [start, end) pair indexing into edge_list_data,
46 /// which holds the actual DepNodeIndices of the target nodes.
47 edge_list_indices: IndexVec<SerializedDepNodeIndex, (u32, u32)>,
48 /// A flattened list of all edge targets in the graph. Edge sources are
49 /// implicit in edge_list_indices.
50 edge_list_data: Vec<SerializedDepNodeIndex>,
51 /// Reciprocal map to `nodes`.
52 index: FxHashMap<DepNode<K>, SerializedDepNodeIndex>,
55 impl<K: DepKind> Default for SerializedDepGraph<K> {
56 fn default() -> Self {
58 nodes: Default::default(),
59 fingerprints: Default::default(),
60 edge_list_indices: Default::default(),
61 edge_list_data: Default::default(),
62 index: Default::default(),
67 impl<K: DepKind> SerializedDepGraph<K> {
69 pub fn edge_targets_from(&self, source: SerializedDepNodeIndex) -> &[SerializedDepNodeIndex] {
70 let targets = self.edge_list_indices[source];
71 &self.edge_list_data[targets.0 as usize..targets.1 as usize]
75 pub fn index_to_node(&self, dep_node_index: SerializedDepNodeIndex) -> DepNode<K> {
76 self.nodes[dep_node_index]
80 pub fn node_to_index_opt(&self, dep_node: &DepNode<K>) -> Option<SerializedDepNodeIndex> {
81 self.index.get(dep_node).cloned()
85 pub fn fingerprint_of(&self, dep_node: &DepNode<K>) -> Option<Fingerprint> {
86 self.index.get(dep_node).map(|&node_index| self.fingerprints[node_index])
90 pub fn fingerprint_by_index(&self, dep_node_index: SerializedDepNodeIndex) -> Fingerprint {
91 self.fingerprints[dep_node_index]
94 pub fn node_count(&self) -> usize {
99 impl<'a, K: DepKind + Decodable<opaque::Decoder<'a>>> Decodable<opaque::Decoder<'a>>
100 for SerializedDepGraph<K>
102 #[instrument(level = "debug", skip(d))]
103 fn decode(d: &mut opaque::Decoder<'a>) -> SerializedDepGraph<K> {
104 let start_position = d.position();
106 // The last 16 bytes are the node count and edge count.
107 debug!("position: {:?}", d.position());
108 d.set_position(d.data.len() - 2 * IntEncodedWithFixedSize::ENCODED_SIZE);
109 debug!("position: {:?}", d.position());
111 let node_count = IntEncodedWithFixedSize::decode(d).0 as usize;
112 let edge_count = IntEncodedWithFixedSize::decode(d).0 as usize;
113 debug!(?node_count, ?edge_count);
115 debug!("position: {:?}", d.position());
116 d.set_position(start_position);
117 debug!("position: {:?}", d.position());
119 let mut nodes = IndexVec::with_capacity(node_count);
120 let mut fingerprints = IndexVec::with_capacity(node_count);
121 let mut edge_list_indices = IndexVec::with_capacity(node_count);
122 let mut edge_list_data = Vec::with_capacity(edge_count);
124 for _index in 0..node_count {
125 let dep_node: DepNode<K> = Decodable::decode(d);
126 let _i: SerializedDepNodeIndex = nodes.push(dep_node);
127 debug_assert_eq!(_i.index(), _index);
129 let fingerprint: Fingerprint = Decodable::decode(d);
130 let _i: SerializedDepNodeIndex = fingerprints.push(fingerprint);
131 debug_assert_eq!(_i.index(), _index);
133 d.read_seq(|d, len| {
134 let start = edge_list_data.len().try_into().unwrap();
136 let edge = d.read_seq_elt(Decodable::decode);
137 edge_list_data.push(edge);
139 let end = edge_list_data.len().try_into().unwrap();
140 let _i: SerializedDepNodeIndex = edge_list_indices.push((start, end));
141 debug_assert_eq!(_i.index(), _index);
145 let index: FxHashMap<_, _> =
146 nodes.iter_enumerated().map(|(idx, &dep_node)| (dep_node, idx)).collect();
148 SerializedDepGraph { nodes, fingerprints, edge_list_indices, edge_list_data, index }
152 #[derive(Debug, Encodable, Decodable)]
153 pub struct NodeInfo<K: DepKind> {
155 fingerprint: Fingerprint,
156 edges: SmallVec<[DepNodeIndex; 8]>,
159 struct Stat<K: DepKind> {
165 struct EncoderState<K: DepKind> {
166 encoder: FileEncoder,
167 total_node_count: usize,
168 total_edge_count: usize,
169 result: FileEncodeResult,
170 stats: Option<FxHashMap<K, Stat<K>>>,
173 impl<K: DepKind> EncoderState<K> {
174 fn new(encoder: FileEncoder, record_stats: bool) -> Self {
180 stats: record_stats.then(FxHashMap::default),
184 #[instrument(level = "debug", skip(self, record_graph))]
188 record_graph: &Option<Lock<DepGraphQuery<K>>>,
190 let index = DepNodeIndex::new(self.total_node_count);
191 self.total_node_count += 1;
193 let edge_count = node.edges.len();
194 self.total_edge_count += edge_count;
196 if let Some(record_graph) = &record_graph {
197 // Do not ICE when a query is called from within `with_query`.
198 if let Some(record_graph) = &mut record_graph.try_lock() {
199 record_graph.push(index, node.node, &node.edges);
203 if let Some(stats) = &mut self.stats {
204 let kind = node.node.kind;
206 let stat = stats.entry(kind).or_insert(Stat { kind, node_counter: 0, edge_counter: 0 });
207 stat.node_counter += 1;
208 stat.edge_counter += edge_count as u64;
211 debug!(?index, ?node);
212 let encoder = &mut self.encoder;
213 if self.result.is_ok() {
214 self.result = node.encode(encoder);
219 fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult {
220 let Self { mut encoder, total_node_count, total_edge_count, result, stats: _ } = self;
223 let node_count = total_node_count.try_into().unwrap();
224 let edge_count = total_edge_count.try_into().unwrap();
226 debug!(?node_count, ?edge_count);
227 debug!("position: {:?}", encoder.position());
228 IntEncodedWithFixedSize(node_count).encode(&mut encoder)?;
229 IntEncodedWithFixedSize(edge_count).encode(&mut encoder)?;
230 debug!("position: {:?}", encoder.position());
231 // Drop the encoder so that nothing is written after the counts.
232 let result = encoder.flush();
233 // FIXME(rylev): we hardcode the dep graph file name so we don't need a dependency on
234 // rustc_incremental just for that.
235 profiler.artifact_size("dep_graph", "dep-graph.bin", encoder.position() as u64);
240 pub struct GraphEncoder<K: DepKind> {
241 status: Lock<EncoderState<K>>,
242 record_graph: Option<Lock<DepGraphQuery<K>>>,
245 impl<K: DepKind + Encodable<FileEncoder>> GraphEncoder<K> {
247 encoder: FileEncoder,
248 prev_node_count: usize,
253 if record_graph { Some(Lock::new(DepGraphQuery::new(prev_node_count))) } else { None };
254 let status = Lock::new(EncoderState::new(encoder, record_stats));
255 GraphEncoder { status, record_graph }
258 pub(crate) fn with_query(&self, f: impl Fn(&DepGraphQuery<K>)) {
259 if let Some(record_graph) = &self.record_graph {
260 f(&record_graph.lock())
264 pub(crate) fn print_incremental_info(
266 total_read_count: u64,
267 total_duplicate_read_count: u64,
269 let status = self.status.lock();
270 if let Some(record_stats) = &status.stats {
271 let mut stats: Vec<_> = record_stats.values().collect();
272 stats.sort_by_key(|s| -(s.node_counter as i64));
274 const SEPARATOR: &str = "[incremental] --------------------------------\
275 ----------------------------------------------\
278 eprintln!("[incremental]");
279 eprintln!("[incremental] DepGraph Statistics");
280 eprintln!("{}", SEPARATOR);
281 eprintln!("[incremental]");
282 eprintln!("[incremental] Total Node Count: {}", status.total_node_count);
283 eprintln!("[incremental] Total Edge Count: {}", status.total_edge_count);
285 if cfg!(debug_assertions) {
286 eprintln!("[incremental] Total Edge Reads: {}", total_read_count);
288 "[incremental] Total Duplicate Edge Reads: {}",
289 total_duplicate_read_count
293 eprintln!("[incremental]");
295 "[incremental] {:<36}| {:<17}| {:<12}| {:<17}|",
296 "Node Kind", "Node Frequency", "Node Count", "Avg. Edge Count"
298 eprintln!("{}", SEPARATOR);
301 let node_kind_ratio =
302 (100.0 * (stat.node_counter as f64)) / (status.total_node_count as f64);
303 let node_kind_avg_edges = (stat.edge_counter as f64) / (stat.node_counter as f64);
306 "[incremental] {:<36}|{:>16.1}% |{:>12} |{:>17.1} |",
307 format!("{:?}", stat.kind),
314 eprintln!("{}", SEPARATOR);
315 eprintln!("[incremental]");
321 profiler: &SelfProfilerRef,
323 fingerprint: Fingerprint,
324 edges: SmallVec<[DepNodeIndex; 8]>,
326 let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph");
327 let node = NodeInfo { node, fingerprint, edges };
328 self.status.lock().encode_node(&node, &self.record_graph)
331 pub fn finish(self, profiler: &SelfProfilerRef) -> FileEncodeResult {
332 let _prof_timer = profiler.generic_activity("incr_comp_encode_dep_graph");
333 self.status.into_inner().finish(profiler)