Implement debugging output of the bootstrap Step graph into a DOT file

6 files changed, 223 insertions, 2 deletions

diff --git a/src/bootstrap/src/bin/main.rs b/src/bootstrap/src/bin/main.rs
index 181d71f63c2..cf24fedaebb 100644
--- a/src/bootstrap/src/bin/main.rs
+++ b/src/bootstrap/src/bin/main.rs
@@ -159,6 +159,9 @@ fn main() {
     if is_bootstrap_profiling_enabled() {
         build.report_summary(start_time);
     }
+
+    #[cfg(feature = "tracing")]
+    build.report_step_graph();
 }
 
 fn check_version(config: &Config) -> Option<String> {
diff --git a/src/bootstrap/src/core/builder/mod.rs b/src/bootstrap/src/core/builder/mod.rs
index 96289a63785..20f3fee1c6c 100644
--- a/src/bootstrap/src/core/builder/mod.rs
+++ b/src/bootstrap/src/core/builder/mod.rs
@@ -77,7 +77,7 @@ impl Deref for Builder<'_> {
 /// type's [`Debug`] implementation.
 ///
 /// (Trying to debug-print `dyn Any` results in the unhelpful `"Any { .. }"`.)
-trait AnyDebug: Any + Debug {}
+pub trait AnyDebug: Any + Debug {}
 impl<T: Any + Debug> AnyDebug for T {}
 impl dyn AnyDebug {
     /// Equivalent to `<dyn Any>::downcast_ref`.
@@ -197,6 +197,14 @@ impl StepMetadata {
             // For everything else, a stage N things gets built by a stage N-1 compiler.
             .map(|compiler| if self.name == "std" { compiler.stage } else { compiler.stage + 1 }))
     }
+
+    pub fn get_name(&self) -> &str {
+        &self.name
+    }
+
+    pub fn get_target(&self) -> TargetSelection {
+        self.target
+    }
 }
 
 pub struct RunConfig<'a> {
@@ -1657,9 +1665,24 @@ You have to build a stage1 compiler for `{}` first, and then use it to build a s
             if let Some(out) = self.cache.get(&step) {
                 self.verbose_than(1, || println!("{}c {:?}", "  ".repeat(stack.len()), step));
 
+                #[cfg(feature = "tracing")]
+                {
+                    if let Some(parent) = stack.last() {
+                        let mut graph = self.build.step_graph.borrow_mut();
+                        graph.register_cached_step(&step, parent, self.config.dry_run());
+                    }
+                }
                 return out;
             }
             self.verbose_than(1, || println!("{}> {:?}", "  ".repeat(stack.len()), step));
+
+            #[cfg(feature = "tracing")]
+            {
+                let parent = stack.last();
+                let mut graph = self.build.step_graph.borrow_mut();
+                graph.register_step_execution(&step, parent, self.config.dry_run());
+            }
+
             stack.push(Box::new(step.clone()));
         }
 
diff --git a/src/bootstrap/src/lib.rs b/src/bootstrap/src/lib.rs
index 011b52df97b..e49513a2116 100644
--- a/src/bootstrap/src/lib.rs
+++ b/src/bootstrap/src/lib.rs
@@ -188,7 +188,6 @@ pub enum GitRepo {
 /// although most functions are implemented as free functions rather than
 /// methods specifically on this structure itself (to make it easier to
 /// organize).
-#[derive(Clone)]
 pub struct Build {
     /// User-specified configuration from `bootstrap.toml`.
     config: Config,
@@ -244,6 +243,9 @@ pub struct Build {
 
     #[cfg(feature = "build-metrics")]
     metrics: crate::utils::metrics::BuildMetrics,
+
+    #[cfg(feature = "tracing")]
+    step_graph: std::cell::RefCell<crate::utils::step_graph::StepGraph>,
 }
 
 #[derive(Debug, Clone)]
@@ -547,6 +549,9 @@ impl Build {
 
             #[cfg(feature = "build-metrics")]
             metrics: crate::utils::metrics::BuildMetrics::init(),
+
+            #[cfg(feature = "tracing")]
+            step_graph: std::cell::RefCell::new(crate::utils::step_graph::StepGraph::default()),
         };
 
         // If local-rust is the same major.minor as the current version, then force a
@@ -2024,6 +2029,11 @@ to download LLVM rather than building it.
     pub fn report_summary(&self, start_time: Instant) {
         self.config.exec_ctx.profiler().report_summary(start_time);
     }
+
+    #[cfg(feature = "tracing")]
+    pub fn report_step_graph(self) {
+        self.step_graph.into_inner().store_to_dot_files();
+    }
 }
 
 impl AsRef<ExecutionContext> for Build {
diff --git a/src/bootstrap/src/utils/mod.rs b/src/bootstrap/src/utils/mod.rs
index 169fcec303e..97d8d274e8f 100644
--- a/src/bootstrap/src/utils/mod.rs
+++ b/src/bootstrap/src/utils/mod.rs
@@ -19,5 +19,8 @@ pub(crate) mod tracing;
 #[cfg(feature = "build-metrics")]
 pub(crate) mod metrics;
 
+#[cfg(feature = "tracing")]
+pub(crate) mod step_graph;
+
 #[cfg(test)]
 pub(crate) mod tests;
diff --git a/src/bootstrap/src/utils/step_graph.rs b/src/bootstrap/src/utils/step_graph.rs
new file mode 100644
index 00000000000..b1db9e61fda
--- /dev/null
+++ b/src/bootstrap/src/utils/step_graph.rs
@@ -0,0 +1,176 @@
+use std::collections::{HashMap, HashSet};
+use std::fmt::Debug;
+use std::io::BufWriter;
+
+use crate::core::builder::{AnyDebug, Step};
+
+/// Records the executed steps and their dependencies in a directed graph,
+/// which can then be rendered into a DOT file for visualization.
+///
+/// The graph visualizes the first execution of a step with a solid edge,
+/// and cached executions of steps with a dashed edge.
+/// If you only want to see first executions, you can modify the code in `DotGraph` to
+/// always set `cached: false`.
+#[derive(Default)]
+pub struct StepGraph {
+    /// We essentially store one graph per dry run mode.
+    graphs: HashMap<String, DotGraph>,
+}
+
+impl StepGraph {
+    pub fn register_step_execution<S: Step>(
+        &mut self,
+        step: &S,
+        parent: Option<&Box<dyn AnyDebug>>,
+        dry_run: bool,
+    ) {
+        let key = get_graph_key(dry_run);
+        let graph = self.graphs.entry(key.to_string()).or_insert_with(|| DotGraph::default());
+
+        // The debug output of the step sort of serves as the unique identifier of it.
+        // We use it to access the node ID of parents to generate edges.
+        // We could probably also use addresses on the heap from the `Box`, but this seems less
+        // magical.
+        let node_key = render_step(step);
+
+        let label = if let Some(metadata) = step.metadata() {
+            format!(
+                "{}{} [{}]",
+                metadata.get_name(),
+                metadata.get_stage().map(|s| format!(" stage {s}")).unwrap_or_default(),
+                metadata.get_target()
+            )
+        } else {
+            let type_name = std::any::type_name::<S>();
+            type_name
+                .strip_prefix("bootstrap::core::")
+                .unwrap_or(type_name)
+                .strip_prefix("build_steps::")
+                .unwrap_or(type_name)
+                .to_string()
+        };
+
+        let node = Node { label, tooltip: node_key.clone() };
+        let node_handle = graph.add_node(node_key, node);
+
+        if let Some(parent) = parent {
+            let parent_key = render_step(parent);
+            if let Some(src_node_handle) = graph.get_handle_by_key(&parent_key) {
+                graph.add_edge(src_node_handle, node_handle);
+            }
+        }
+    }
+
+    pub fn register_cached_step<S: Step>(
+        &mut self,
+        step: &S,
+        parent: &Box<dyn AnyDebug>,
+        dry_run: bool,
+    ) {
+        let key = get_graph_key(dry_run);
+        let graph = self.graphs.get_mut(key).unwrap();
+
+        let node_key = render_step(step);
+        let parent_key = render_step(parent);
+
+        if let Some(src_node_handle) = graph.get_handle_by_key(&parent_key) {
+            if let Some(dst_node_handle) = graph.get_handle_by_key(&node_key) {
+                graph.add_cached_edge(src_node_handle, dst_node_handle);
+            }
+        }
+    }
+
+    pub fn store_to_dot_files(self) {
+        for (key, graph) in self.graphs.into_iter() {
+            let filename = format!("bootstrap-steps{key}.dot");
+            graph.render(&filename).unwrap();
+        }
+    }
+}
+
+fn get_graph_key(dry_run: bool) -> &'static str {
+    if dry_run { ".dryrun" } else { "" }
+}
+
+struct Node {
+    label: String,
+    tooltip: String,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
+struct NodeHandle(usize);
+
+#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
+struct Edge {
+    src: NodeHandle,
+    dst: NodeHandle,
+    cached: bool,
+}
+
+// We could use a library for this, but they either:
+// - require lifetimes, which gets annoying (dot_writer)
+// - don't support tooltips (dot_graph)
+// - have a lot of dependencies (graphviz_rust)
+// - only have SVG export (layout-rs)
+// - use a builder pattern that is very annoying to use here (tabbycat)
+#[derive(Default)]
+struct DotGraph {
+    nodes: Vec<Node>,
+    /// The `NodeHandle` represents an index within `self.nodes`
+    edges: HashSet<Edge>,
+    key_to_index: HashMap<String, NodeHandle>,
+}
+
+impl DotGraph {
+    fn add_node(&mut self, key: String, node: Node) -> NodeHandle {
+        let handle = NodeHandle(self.nodes.len());
+        self.nodes.push(node);
+        self.key_to_index.insert(key, handle);
+        handle
+    }
+
+    fn add_edge(&mut self, src: NodeHandle, dst: NodeHandle) {
+        self.edges.insert(Edge { src, dst, cached: false });
+    }
+
+    fn add_cached_edge(&mut self, src: NodeHandle, dst: NodeHandle) {
+        self.edges.insert(Edge { src, dst, cached: true });
+    }
+
+    fn get_handle_by_key(&self, key: &str) -> Option<NodeHandle> {
+        self.key_to_index.get(key).copied()
+    }
+
+    fn render(&self, path: &str) -> std::io::Result<()> {
+        use std::io::Write;
+
+        let mut file = BufWriter::new(std::fs::File::create(path)?);
+        writeln!(file, "digraph bootstrap_steps {{")?;
+        for (index, node) in self.nodes.iter().enumerate() {
+            writeln!(
+                file,
+                r#"{index} [label="{}", tooltip="{}"]"#,
+                escape(&node.label),
+                escape(&node.tooltip)
+            )?;
+        }
+
+        let mut edges: Vec<&Edge> = self.edges.iter().collect();
+        edges.sort();
+        for edge in edges {
+            let style = if edge.cached { "dashed" } else { "solid" };
+            writeln!(file, r#"{} -> {} [style="{style}"]"#, edge.src.0, edge.dst.0)?;
+        }
+
+        writeln!(file, "}}")
+    }
+}
+
+fn render_step(step: &dyn Debug) -> String {
+    format!("{step:?}")
+}
+
+/// Normalizes the string so that it can be rendered into a DOT file.
+fn escape(input: &str) -> String {
+    input.replace("\"", "\\\"")
+}
diff --git a/src/doc/rustc-dev-guide/src/building/bootstrapping/debugging-bootstrap.md b/src/doc/rustc-dev-guide/src/building/bootstrapping/debugging-bootstrap.md
index c9c0d64a604..9c5ebbd36c4 100644
--- a/src/doc/rustc-dev-guide/src/building/bootstrapping/debugging-bootstrap.md
+++ b/src/doc/rustc-dev-guide/src/building/bootstrapping/debugging-bootstrap.md
@@ -123,6 +123,12 @@ if [#96176][cleanup-compiler-for] is resolved.
 
 [cleanup-compiler-for]: https://github.com/rust-lang/rust/issues/96176
 
+### Rendering step graph
+
+When you run bootstrap with the `BOOTSTRAP_TRACING` environment variable configured, bootstrap will automatically output a DOT file that shows all executed steps and their dependencies. The files will have a prefix `bootstrap-steps`. You can use e.g. `xdot` to visualize the file or e.g. `dot -Tsvg` to convert the DOT file to a SVG file.
+
+A separate DOT file will be outputted for dry-run and non-dry-run execution.
+
 ### Using `tracing` in bootstrap
 
 Both `tracing::*` macros and the `tracing::instrument` proc-macro attribute need to be gated behind `tracing` feature. Examples: