1 //! A helpful diagram for debugging dataflow problems.
4 use std::lazy::SyncOnceCell;
5 use std::{io, ops, str};
8 use rustc_graphviz as dot;
9 use rustc_hir::def_id::DefId;
10 use rustc_middle::mir::{self, BasicBlock, Body, Location};
12 use super::fmt::{DebugDiffWithAdapter, DebugWithAdapter, DebugWithContext};
13 use super::{Analysis, Direction, Results, ResultsRefCursor, ResultsVisitor};
14 use crate::util::graphviz_safe_def_name;
16 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
17 pub enum OutputStyle {
23 fn num_state_columns(&self) -> usize {
26 Self::BeforeAndAfter => 2,
31 pub struct Formatter<'a, 'tcx, A>
37 results: &'a Results<'tcx, A>,
41 impl<A> Formatter<'a, 'tcx, A>
48 results: &'a Results<'tcx, A>,
51 Formatter { body, def_id, results, style }
55 /// A pair of a basic block and an index into that basic blocks `successors`.
56 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
62 fn dataflow_successors(body: &Body<'tcx>, bb: BasicBlock) -> Vec<CfgEdge> {
67 .map(|(index, _)| CfgEdge { source: bb, index })
71 impl<A> dot::Labeller<'_> for Formatter<'a, 'tcx, A>
74 A::Domain: DebugWithContext<A>,
76 type Node = BasicBlock;
79 fn graph_id(&self) -> dot::Id<'_> {
80 let name = graphviz_safe_def_name(self.def_id);
81 dot::Id::new(format!("graph_for_def_id_{}", name)).unwrap()
84 fn node_id(&self, n: &Self::Node) -> dot::Id<'_> {
85 dot::Id::new(format!("bb_{}", n.index())).unwrap()
88 fn node_label(&self, block: &Self::Node) -> dot::LabelText<'_> {
89 let mut label = Vec::new();
90 let mut fmt = BlockFormatter {
91 results: ResultsRefCursor::new(self.body, self.results),
93 bg: Background::Light,
96 fmt.write_node_label(&mut label, self.body, *block).unwrap();
97 dot::LabelText::html(String::from_utf8(label).unwrap())
100 fn node_shape(&self, _n: &Self::Node) -> Option<dot::LabelText<'_>> {
101 Some(dot::LabelText::label("none"))
104 fn edge_label(&self, e: &Self::Edge) -> dot::LabelText<'_> {
105 let label = &self.body[e.source].terminator().kind.fmt_successor_labels()[e.index];
106 dot::LabelText::label(label.clone())
110 impl<A> dot::GraphWalk<'a> for Formatter<'a, 'tcx, A>
114 type Node = BasicBlock;
117 fn nodes(&self) -> dot::Nodes<'_, Self::Node> {
118 self.body.basic_blocks().indices().collect::<Vec<_>>().into()
121 fn edges(&self) -> dot::Edges<'_, Self::Edge> {
125 .flat_map(|bb| dataflow_successors(self.body, bb))
130 fn source(&self, edge: &Self::Edge) -> Self::Node {
134 fn target(&self, edge: &Self::Edge) -> Self::Node {
135 self.body[edge.source].terminator().successors().nth(edge.index).copied().unwrap()
139 struct BlockFormatter<'a, 'tcx, A>
143 results: ResultsRefCursor<'a, 'a, 'tcx, A>,
148 impl<A> BlockFormatter<'a, 'tcx, A>
151 A::Domain: DebugWithContext<A>,
153 const HEADER_COLOR: &'static str = "#a0a0a0";
155 fn toggle_background(&mut self) -> Background {
163 w: &mut impl io::Write,
164 body: &'a Body<'tcx>,
166 ) -> io::Result<()> {
168 // +-+-----------------------------------------------+
170 // +-+----------------------------------+------------+
172 // +-+----------------------------------+------------+
173 // C | | (on entry) | {_0,_2,_3} |
174 // +-+----------------------------------+------------+
175 // D |0| StorageLive(_7) | |
176 // +-+----------------------------------+------------+
177 // |1| StorageLive(_8) | |
178 // +-+----------------------------------+------------+
179 // |2| _8 = &mut _1 | +_8 |
180 // +-+----------------------------------+------------+
181 // E |T| _4 = const Foo::twiddle(move _2) | -_2 |
182 // +-+----------------------------------+------------+
183 // F | | (on unwind) | {_0,_3,_8} |
184 // +-+----------------------------------+------------+
185 // | | (on successful return) | +_4 |
186 // +-+----------------------------------+------------+
188 // N.B., Some attributes (`align`, `balign`) are repeated on parent elements and their
189 // children. This is because `xdot` seemed to have a hard time correctly propagating
190 // attributes. Make sure to test the output before trying to remove the redundancy.
191 // Notably, `align` was found to have no effect when applied only to <table>.
193 let table_fmt = concat!(
196 " cellspacing=\"0\"",
197 " cellpadding=\"3\"",
200 write!(w, r#"<table{fmt}>"#, fmt = table_fmt)?;
202 // A + B: Block header
204 OutputStyle::AfterOnly => self.write_block_header_simple(w, block)?,
205 OutputStyle::BeforeAndAfter => {
206 self.write_block_header_with_state_columns(w, block, &["BEFORE", "AFTER"])?
210 // C: State at start of block
211 self.bg = Background::Light;
212 self.results.seek_to_block_start(block);
213 let block_start_state = self.results.get().clone();
214 self.write_row_with_full_state(w, "", "(on start)")?;
216 // D + E: Statement and terminator transfer functions
217 self.write_statements_and_terminator(w, body, block)?;
219 // F: State at end of block
221 let terminator = body[block].terminator();
223 // Write the full dataflow state immediately after the terminator if it differs from the
224 // state at block entry.
225 self.results.seek_to_block_end(block);
226 if self.results.get() != &block_start_state || A::Direction::is_backward() {
227 let after_terminator_name = match terminator.kind {
228 mir::TerminatorKind::Call { destination: Some(_), .. } => "(on unwind)",
232 self.write_row_with_full_state(w, "", after_terminator_name)?;
235 // Write any changes caused by terminator-specific effects.
237 // FIXME: These should really be printed as part of each outgoing edge rather than the node
238 // for the basic block itself. That way, we could display terminator-specific effects for
239 // backward dataflow analyses as well as effects for `SwitchInt` terminators.
240 match terminator.kind {
241 mir::TerminatorKind::Call {
242 destination: Some((return_place, _)),
247 self.write_row(w, "", "(on successful return)", |this, w, fmt| {
248 let state_on_unwind = this.results.get().clone();
249 this.results.apply_custom_effect(|analysis, state| {
250 analysis.apply_call_return_effect(state, block, func, args, return_place);
255 r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
256 colspan = this.style.num_state_columns(),
261 this.results.analysis()
267 mir::TerminatorKind::Yield { resume, resume_arg, .. } => {
268 self.write_row(w, "", "(on yield resume)", |this, w, fmt| {
269 let state_on_generator_drop = this.results.get().clone();
270 this.results.apply_custom_effect(|analysis, state| {
271 analysis.apply_yield_resume_effect(state, resume, resume_arg);
276 r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
277 colspan = this.style.num_state_columns(),
281 &state_on_generator_drop,
282 this.results.analysis()
291 write!(w, "</table>")
294 fn write_block_header_simple(
296 w: &mut impl io::Write,
298 ) -> io::Result<()> {
299 // +-------------------------------------------------+
301 // +-----------------------------------+-------------+
303 // +-+---------------------------------+-------------+
309 concat!("<tr>", r#"<td colspan="3" sides="tl">bb{block_id}</td>"#, "</tr>",),
310 block_id = block.index(),
318 r#"<td colspan="2" {fmt}>MIR</td>"#,
319 r#"<td {fmt}>STATE</td>"#,
322 fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR),
326 fn write_block_header_with_state_columns(
328 w: &mut impl io::Write,
330 state_column_names: &[&str],
331 ) -> io::Result<()> {
332 // +------------------------------------+-------------+
334 // +------------------------------------+------+------+
335 // B | MIR | GEN | KILL |
336 // +-+----------------------------------+------+------+
344 r#"<td {fmt} colspan="2">bb{block_id}</td>"#,
345 r#"<td {fmt} colspan="{num_state_cols}">STATE</td>"#,
348 fmt = "sides=\"tl\"",
349 num_state_cols = state_column_names.len(),
350 block_id = block.index(),
354 let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR);
355 write!(w, concat!("<tr>", r#"<td colspan="2" {fmt}>MIR</td>"#,), fmt = fmt,)?;
357 for name in state_column_names {
358 write!(w, "<td {fmt}>{name}</td>", fmt = fmt, name = name)?;
364 fn write_statements_and_terminator(
366 w: &mut impl io::Write,
367 body: &'a Body<'tcx>,
369 ) -> io::Result<()> {
370 let diffs = StateDiffCollector::run(body, block, self.results.results(), self.style);
372 let mut befores = diffs.before.map(|v| v.into_iter());
373 let mut afters = diffs.after.into_iter();
375 let next_in_dataflow_order = |it: &mut std::vec::IntoIter<_>| {
376 if A::Direction::is_forward() { it.next().unwrap() } else { it.next_back().unwrap() }
379 for (i, statement) in body[block].statements.iter().enumerate() {
380 let statement_str = format!("{:?}", statement);
381 let index_str = format!("{}", i);
383 let after = next_in_dataflow_order(&mut afters);
384 let before = befores.as_mut().map(next_in_dataflow_order);
386 self.write_row(w, &index_str, &statement_str, |_this, w, fmt| {
387 if let Some(before) = before {
388 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
391 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
395 let after = next_in_dataflow_order(&mut afters);
396 let before = befores.as_mut().map(next_in_dataflow_order);
398 assert!(afters.is_empty());
399 assert!(befores.as_ref().map_or(true, ExactSizeIterator::is_empty));
401 let terminator = body[block].terminator();
402 let mut terminator_str = String::new();
403 terminator.kind.fmt_head(&mut terminator_str).unwrap();
405 self.write_row(w, "T", &terminator_str, |_this, w, fmt| {
406 if let Some(before) = before {
407 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
410 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
414 /// Write a row with the given index and MIR, using the function argument to fill in the
415 /// "STATE" column(s).
416 fn write_row<W: io::Write>(
421 f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>,
422 ) -> io::Result<()> {
423 let bg = self.toggle_background();
424 let valign = if mir.starts_with("(on ") && mir != "(on entry)" { "bottom" } else { "top" };
426 let fmt = format!("valign=\"{}\" sides=\"tl\" {}", valign, bg.attr());
432 r#"<td {fmt} align="right">{i}</td>"#,
433 r#"<td {fmt} align="left">{mir}</td>"#,
437 mir = dot::escape_html(mir),
444 fn write_row_with_full_state(
446 w: &mut impl io::Write,
449 ) -> io::Result<()> {
450 self.write_row(w, i, mir, |this, w, fmt| {
451 let state = this.results.get();
452 let analysis = this.results.analysis();
454 // FIXME: The full state vector can be quite long. It would be nice to split on commas
455 // and use some text wrapping algorithm.
458 r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#,
459 colspan = this.style.num_state_columns(),
461 state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }),
467 struct StateDiffCollector<'a, 'tcx, A>
472 prev_state: A::Domain,
473 before: Option<Vec<String>>,
477 impl<A> StateDiffCollector<'a, 'tcx, A>
480 A::Domain: DebugWithContext<A>,
483 body: &'a mir::Body<'tcx>,
485 results: &'a Results<'tcx, A>,
488 let mut collector = StateDiffCollector {
489 analysis: &results.analysis,
490 prev_state: results.analysis.bottom_value(body),
492 before: (style == OutputStyle::BeforeAndAfter).then_some(vec![]),
495 results.visit_with(body, std::iter::once(block), &mut collector);
500 impl<A> ResultsVisitor<'a, 'tcx> for StateDiffCollector<'a, 'tcx, A>
503 A::Domain: DebugWithContext<A>,
505 type FlowState = A::Domain;
507 fn visit_block_start(
509 state: &Self::FlowState,
510 _block_data: &'mir mir::BasicBlockData<'tcx>,
513 if A::Direction::is_forward() {
514 self.prev_state.clone_from(state);
520 state: &Self::FlowState,
521 _block_data: &'mir mir::BasicBlockData<'tcx>,
524 if A::Direction::is_backward() {
525 self.prev_state.clone_from(state);
529 fn visit_statement_before_primary_effect(
531 state: &Self::FlowState,
532 _statement: &'mir mir::Statement<'tcx>,
535 if let Some(before) = self.before.as_mut() {
536 before.push(diff_pretty(state, &self.prev_state, self.analysis));
537 self.prev_state.clone_from(state)
541 fn visit_statement_after_primary_effect(
543 state: &Self::FlowState,
544 _statement: &'mir mir::Statement<'tcx>,
547 self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
548 self.prev_state.clone_from(state)
551 fn visit_terminator_before_primary_effect(
553 state: &Self::FlowState,
554 _terminator: &'mir mir::Terminator<'tcx>,
557 if let Some(before) = self.before.as_mut() {
558 before.push(diff_pretty(state, &self.prev_state, self.analysis));
559 self.prev_state.clone_from(state)
563 fn visit_terminator_after_primary_effect(
565 state: &Self::FlowState,
566 _terminator: &'mir mir::Terminator<'tcx>,
569 self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
570 self.prev_state.clone_from(state)
575 ($re:literal $(,)?) => {{
576 static RE: SyncOnceCell<regex::Regex> = SyncOnceCell::new();
577 RE.get_or_init(|| Regex::new($re).unwrap())
581 fn diff_pretty<T, C>(new: T, old: T, ctxt: &C) -> String
583 T: DebugWithContext<C>,
586 return String::new();
589 let re = regex!("\t?\u{001f}([+-])");
591 let raw_diff = format!("{:#?}", DebugDiffWithAdapter { new, old, ctxt });
593 // Replace newlines in the `Debug` output with `<br/>`
594 let raw_diff = raw_diff.replace('\n', r#"<br align="left"/>"#);
596 let mut inside_font_tag = false;
597 let html_diff = re.replace_all(&raw_diff, |captures: ®ex::Captures<'_>| {
598 let mut ret = String::new();
600 ret.push_str(r#"</font>"#);
603 let tag = match &captures[1] {
604 "+" => r#"<font color="darkgreen">+"#,
605 "-" => r#"<font color="red">-"#,
609 inside_font_tag = true;
614 let mut html_diff = match html_diff {
615 Cow::Borrowed(_) => return raw_diff,
620 html_diff.push_str("</font>");
626 /// The background color used for zebra-striping the table.
627 #[derive(Clone, Copy)]
634 fn attr(self) -> &'static str {
636 Self::Dark => "bgcolor=\"#f0f0f0\"",
642 impl ops::Not for Background {
645 fn not(self) -> Self {
647 Self::Light => Self::Dark,
648 Self::Dark => Self::Light,