Rollup merge of #144779 - Kobzol:bootstrap-dot, r=jieyouxu

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

There are already a bunch of ways how we can debug bootstrap, so why not add one more =D (ideally I'd like to consolidate these approaches somewhat, ```@Shourya742``` is looking into that, but I think that this specific debugging tool is orthogonal to the rest of them, and is quite useful).

This PR adds the option to render the bootstrap step graph into the DOT format, in order to understand what steps were executed, along with their fields (`Debug` output).

Here you can see an example of the generated DOT files for the `BOOTSTRAP_TRACING=1 ./x build compiler --stage 2 --dry-run` command on x64 Linux. One is with cached deps (what this PR does), the other one without.

[bootstrap-dot.zip](https://github.com/user-attachments/files/21548679/bootstrap-dot.zip)

Visual example:
<img width="1899" height="445" alt="image" src="https://github.com/user-attachments/assets/ae40e6d2-0ea8-48bb-b77e-6b21700b95ee" />

r? ```@jieyouxu```

6 files changed, 229 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..c45825a4222
--- /dev/null
+++ b/src/bootstrap/src/utils/step_graph.rs
@@ -0,0 +1,182 @@
+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);
+
+/// Represents a dependency between two bootstrap steps.
+#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
+struct Edge {
+    src: NodeHandle,
+    dst: NodeHandle,
+    // Was the corresponding execution of a step cached, or was the step actually executed?
+    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) {
+        // There's no point in rendering both cached and uncached edge
+        let uncached = Edge { src, dst, cached: false };
+        if !self.edges.contains(&uncached) {
+            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: