1 //! A helpful diagram for debugging dataflow problems.
4 use std::sync::OnceLock;
5 use std::{io, ops, str};
8 use rustc_graphviz as dot;
9 use rustc_middle::mir::graphviz_safe_def_name;
10 use rustc_middle::mir::{self, BasicBlock, Body, Location};
12 use super::fmt::{DebugDiffWithAdapter, DebugWithAdapter, DebugWithContext};
13 use super::{Analysis, CallReturnPlaces, Direction, Results, ResultsRefCursor, ResultsVisitor};
15 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
16 pub enum OutputStyle {
22 fn num_state_columns(&self) -> usize {
25 Self::BeforeAndAfter => 2,
30 pub struct Formatter<'a, 'tcx, A>
35 results: &'a Results<'tcx, A>,
39 impl<'a, 'tcx, A> Formatter<'a, 'tcx, A>
43 pub fn new(body: &'a Body<'tcx>, results: &'a Results<'tcx, A>, style: OutputStyle) -> Self {
44 Formatter { body, results, style }
48 /// A pair of a basic block and an index into that basic blocks `successors`.
49 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
55 fn dataflow_successors(body: &Body<'_>, bb: BasicBlock) -> Vec<CfgEdge> {
60 .map(|(index, _)| CfgEdge { source: bb, index })
64 impl<'tcx, A> dot::Labeller<'_> for Formatter<'_, 'tcx, A>
67 A::Domain: DebugWithContext<A>,
69 type Node = BasicBlock;
72 fn graph_id(&self) -> dot::Id<'_> {
73 let name = graphviz_safe_def_name(self.body.source.def_id());
74 dot::Id::new(format!("graph_for_def_id_{}", name)).unwrap()
77 fn node_id(&self, n: &Self::Node) -> dot::Id<'_> {
78 dot::Id::new(format!("bb_{}", n.index())).unwrap()
81 fn node_label(&self, block: &Self::Node) -> dot::LabelText<'_> {
82 let mut label = Vec::new();
83 let mut fmt = BlockFormatter {
84 results: ResultsRefCursor::new(self.body, self.results),
86 bg: Background::Light,
89 fmt.write_node_label(&mut label, self.body, *block).unwrap();
90 dot::LabelText::html(String::from_utf8(label).unwrap())
93 fn node_shape(&self, _n: &Self::Node) -> Option<dot::LabelText<'_>> {
94 Some(dot::LabelText::label("none"))
97 fn edge_label(&self, e: &Self::Edge) -> dot::LabelText<'_> {
98 let label = &self.body[e.source].terminator().kind.fmt_successor_labels()[e.index];
99 dot::LabelText::label(label.clone())
103 impl<'a, 'tcx, A> dot::GraphWalk<'a> for Formatter<'a, 'tcx, A>
107 type Node = BasicBlock;
110 fn nodes(&self) -> dot::Nodes<'_, Self::Node> {
111 self.body.basic_blocks().indices().collect::<Vec<_>>().into()
114 fn edges(&self) -> dot::Edges<'_, Self::Edge> {
118 .flat_map(|bb| dataflow_successors(self.body, bb))
123 fn source(&self, edge: &Self::Edge) -> Self::Node {
127 fn target(&self, edge: &Self::Edge) -> Self::Node {
128 self.body[edge.source].terminator().successors().nth(edge.index).unwrap()
132 struct BlockFormatter<'a, 'tcx, A>
136 results: ResultsRefCursor<'a, 'a, 'tcx, A>,
141 impl<'a, 'tcx, A> BlockFormatter<'a, 'tcx, A>
144 A::Domain: DebugWithContext<A>,
146 const HEADER_COLOR: &'static str = "#a0a0a0";
148 fn toggle_background(&mut self) -> Background {
156 w: &mut impl io::Write,
157 body: &'a Body<'tcx>,
159 ) -> io::Result<()> {
161 // +-+-----------------------------------------------+
163 // +-+----------------------------------+------------+
165 // +-+----------------------------------+------------+
166 // C | | (on entry) | {_0,_2,_3} |
167 // +-+----------------------------------+------------+
168 // D |0| StorageLive(_7) | |
169 // +-+----------------------------------+------------+
170 // |1| StorageLive(_8) | |
171 // +-+----------------------------------+------------+
172 // |2| _8 = &mut _1 | +_8 |
173 // +-+----------------------------------+------------+
174 // E |T| _4 = const Foo::twiddle(move _2) | -_2 |
175 // +-+----------------------------------+------------+
176 // F | | (on unwind) | {_0,_3,_8} |
177 // +-+----------------------------------+------------+
178 // | | (on successful return) | +_4 |
179 // +-+----------------------------------+------------+
181 // N.B., Some attributes (`align`, `balign`) are repeated on parent elements and their
182 // children. This is because `xdot` seemed to have a hard time correctly propagating
183 // attributes. Make sure to test the output before trying to remove the redundancy.
184 // Notably, `align` was found to have no effect when applied only to <table>.
186 let table_fmt = concat!(
189 " cellspacing=\"0\"",
190 " cellpadding=\"3\"",
193 write!(w, r#"<table{fmt}>"#, fmt = table_fmt)?;
195 // A + B: Block header
197 OutputStyle::AfterOnly => self.write_block_header_simple(w, block)?,
198 OutputStyle::BeforeAndAfter => {
199 self.write_block_header_with_state_columns(w, block, &["BEFORE", "AFTER"])?
203 // C: State at start of block
204 self.bg = Background::Light;
205 self.results.seek_to_block_start(block);
206 let block_start_state = self.results.get().clone();
207 self.write_row_with_full_state(w, "", "(on start)")?;
209 // D + E: Statement and terminator transfer functions
210 self.write_statements_and_terminator(w, body, block)?;
212 // F: State at end of block
214 let terminator = body[block].terminator();
216 // Write the full dataflow state immediately after the terminator if it differs from the
217 // state at block entry.
218 self.results.seek_to_block_end(block);
219 if self.results.get() != &block_start_state || A::Direction::IS_BACKWARD {
220 let after_terminator_name = match terminator.kind {
221 mir::TerminatorKind::Call { target: Some(_), .. } => "(on unwind)",
225 self.write_row_with_full_state(w, "", after_terminator_name)?;
228 // Write any changes caused by terminator-specific effects.
230 // FIXME: These should really be printed as part of each outgoing edge rather than the node
231 // for the basic block itself. That way, we could display terminator-specific effects for
232 // backward dataflow analyses as well as effects for `SwitchInt` terminators.
233 match terminator.kind {
234 mir::TerminatorKind::Call { destination, .. } => {
235 self.write_row(w, "", "(on successful return)", |this, w, fmt| {
236 let state_on_unwind = this.results.get().clone();
237 this.results.apply_custom_effect(|analysis, state| {
238 analysis.apply_call_return_effect(
241 CallReturnPlaces::Call(destination),
247 r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
248 colspan = this.style.num_state_columns(),
253 this.results.analysis()
259 mir::TerminatorKind::Yield { resume, resume_arg, .. } => {
260 self.write_row(w, "", "(on yield resume)", |this, w, fmt| {
261 let state_on_generator_drop = this.results.get().clone();
262 this.results.apply_custom_effect(|analysis, state| {
263 analysis.apply_yield_resume_effect(state, resume, resume_arg);
268 r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
269 colspan = this.style.num_state_columns(),
273 &state_on_generator_drop,
274 this.results.analysis()
280 mir::TerminatorKind::InlineAsm { destination: Some(_), ref operands, .. } => {
281 self.write_row(w, "", "(on successful return)", |this, w, fmt| {
282 let state_on_unwind = this.results.get().clone();
283 this.results.apply_custom_effect(|analysis, state| {
284 analysis.apply_call_return_effect(
287 CallReturnPlaces::InlineAsm(operands),
293 r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
294 colspan = this.style.num_state_columns(),
299 this.results.analysis()
308 write!(w, "</table>")
311 fn write_block_header_simple(
313 w: &mut impl io::Write,
315 ) -> io::Result<()> {
316 // +-------------------------------------------------+
318 // +-----------------------------------+-------------+
320 // +-+---------------------------------+-------------+
326 concat!("<tr>", r#"<td colspan="3" sides="tl">bb{block_id}</td>"#, "</tr>",),
327 block_id = block.index(),
335 r#"<td colspan="2" {fmt}>MIR</td>"#,
336 r#"<td {fmt}>STATE</td>"#,
339 fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR),
343 fn write_block_header_with_state_columns(
345 w: &mut impl io::Write,
347 state_column_names: &[&str],
348 ) -> io::Result<()> {
349 // +------------------------------------+-------------+
351 // +------------------------------------+------+------+
352 // B | MIR | GEN | KILL |
353 // +-+----------------------------------+------+------+
361 r#"<td {fmt} colspan="2">bb{block_id}</td>"#,
362 r#"<td {fmt} colspan="{num_state_cols}">STATE</td>"#,
365 fmt = "sides=\"tl\"",
366 num_state_cols = state_column_names.len(),
367 block_id = block.index(),
371 let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR);
372 write!(w, concat!("<tr>", r#"<td colspan="2" {fmt}>MIR</td>"#,), fmt = fmt,)?;
374 for name in state_column_names {
375 write!(w, "<td {fmt}>{name}</td>", fmt = fmt, name = name)?;
381 fn write_statements_and_terminator(
383 w: &mut impl io::Write,
384 body: &'a Body<'tcx>,
386 ) -> io::Result<()> {
387 let diffs = StateDiffCollector::run(body, block, self.results.results(), self.style);
389 let mut befores = diffs.before.map(|v| v.into_iter());
390 let mut afters = diffs.after.into_iter();
392 let next_in_dataflow_order = |it: &mut std::vec::IntoIter<_>| {
393 if A::Direction::IS_FORWARD { it.next().unwrap() } else { it.next_back().unwrap() }
396 for (i, statement) in body[block].statements.iter().enumerate() {
397 let statement_str = format!("{:?}", statement);
398 let index_str = format!("{}", i);
400 let after = next_in_dataflow_order(&mut afters);
401 let before = befores.as_mut().map(next_in_dataflow_order);
403 self.write_row(w, &index_str, &statement_str, |_this, w, fmt| {
404 if let Some(before) = before {
405 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
408 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
412 let after = next_in_dataflow_order(&mut afters);
413 let before = befores.as_mut().map(next_in_dataflow_order);
415 assert!(afters.is_empty());
416 assert!(befores.as_ref().map_or(true, ExactSizeIterator::is_empty));
418 let terminator = body[block].terminator();
419 let mut terminator_str = String::new();
420 terminator.kind.fmt_head(&mut terminator_str).unwrap();
422 self.write_row(w, "T", &terminator_str, |_this, w, fmt| {
423 if let Some(before) = before {
424 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
427 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
431 /// Write a row with the given index and MIR, using the function argument to fill in the
432 /// "STATE" column(s).
433 fn write_row<W: io::Write>(
438 f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>,
439 ) -> io::Result<()> {
440 let bg = self.toggle_background();
441 let valign = if mir.starts_with("(on ") && mir != "(on entry)" { "bottom" } else { "top" };
443 let fmt = format!("valign=\"{}\" sides=\"tl\" {}", valign, bg.attr());
449 r#"<td {fmt} align="right">{i}</td>"#,
450 r#"<td {fmt} align="left">{mir}</td>"#,
454 mir = dot::escape_html(mir),
461 fn write_row_with_full_state(
463 w: &mut impl io::Write,
466 ) -> io::Result<()> {
467 self.write_row(w, i, mir, |this, w, fmt| {
468 let state = this.results.get();
469 let analysis = this.results.analysis();
471 // FIXME: The full state vector can be quite long. It would be nice to split on commas
472 // and use some text wrapping algorithm.
475 r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#,
476 colspan = this.style.num_state_columns(),
478 state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }),
484 struct StateDiffCollector<'a, 'tcx, A>
489 prev_state: A::Domain,
490 before: Option<Vec<String>>,
494 impl<'a, 'tcx, A> StateDiffCollector<'a, 'tcx, A>
497 A::Domain: DebugWithContext<A>,
500 body: &'a mir::Body<'tcx>,
502 results: &'a Results<'tcx, A>,
505 let mut collector = StateDiffCollector {
506 analysis: &results.analysis,
507 prev_state: results.analysis.bottom_value(body),
509 before: (style == OutputStyle::BeforeAndAfter).then_some(vec![]),
512 results.visit_with(body, std::iter::once(block), &mut collector);
517 impl<'a, 'tcx, A> ResultsVisitor<'a, 'tcx> for StateDiffCollector<'a, 'tcx, A>
520 A::Domain: DebugWithContext<A>,
522 type FlowState = A::Domain;
524 fn visit_block_start(
526 state: &Self::FlowState,
527 _block_data: &mir::BasicBlockData<'tcx>,
530 if A::Direction::IS_FORWARD {
531 self.prev_state.clone_from(state);
537 state: &Self::FlowState,
538 _block_data: &mir::BasicBlockData<'tcx>,
541 if A::Direction::IS_BACKWARD {
542 self.prev_state.clone_from(state);
546 fn visit_statement_before_primary_effect(
548 state: &Self::FlowState,
549 _statement: &mir::Statement<'tcx>,
552 if let Some(before) = self.before.as_mut() {
553 before.push(diff_pretty(state, &self.prev_state, self.analysis));
554 self.prev_state.clone_from(state)
558 fn visit_statement_after_primary_effect(
560 state: &Self::FlowState,
561 _statement: &mir::Statement<'tcx>,
564 self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
565 self.prev_state.clone_from(state)
568 fn visit_terminator_before_primary_effect(
570 state: &Self::FlowState,
571 _terminator: &mir::Terminator<'tcx>,
574 if let Some(before) = self.before.as_mut() {
575 before.push(diff_pretty(state, &self.prev_state, self.analysis));
576 self.prev_state.clone_from(state)
580 fn visit_terminator_after_primary_effect(
582 state: &Self::FlowState,
583 _terminator: &mir::Terminator<'tcx>,
586 self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
587 self.prev_state.clone_from(state)
592 ($re:literal $(,)?) => {{
593 static RE: OnceLock<regex::Regex> = OnceLock::new();
594 RE.get_or_init(|| Regex::new($re).unwrap())
598 fn diff_pretty<T, C>(new: T, old: T, ctxt: &C) -> String
600 T: DebugWithContext<C>,
603 return String::new();
606 let re = regex!("\t?\u{001f}([+-])");
608 let raw_diff = format!("{:#?}", DebugDiffWithAdapter { new, old, ctxt });
610 // Replace newlines in the `Debug` output with `<br/>`
611 let raw_diff = raw_diff.replace('\n', r#"<br align="left"/>"#);
613 let mut inside_font_tag = false;
614 let html_diff = re.replace_all(&raw_diff, |captures: ®ex::Captures<'_>| {
615 let mut ret = String::new();
617 ret.push_str(r#"</font>"#);
620 let tag = match &captures[1] {
621 "+" => r#"<font color="darkgreen">+"#,
622 "-" => r#"<font color="red">-"#,
626 inside_font_tag = true;
631 let Cow::Owned(mut html_diff) = html_diff else {
636 html_diff.push_str("</font>");
642 /// The background color used for zebra-striping the table.
643 #[derive(Clone, Copy)]
650 fn attr(self) -> &'static str {
652 Self::Dark => "bgcolor=\"#f0f0f0\"",
658 impl ops::Not for Background {
661 fn not(self) -> Self {
663 Self::Light => Self::Dark,
664 Self::Dark => Self::Light,