src/librustc_mir/dataflow/generic/graphviz.rs

   1 use std::cell::RefCell;
   2 use std::io::{self, Write};
   3 use std::{ops, str};
   4
   5 use rustc::mir::{self, BasicBlock, Body, Location};
   6 use rustc_hir::def_id::DefId;
   7 use rustc_index::bit_set::{BitSet, HybridBitSet};
   8 use rustc_index::vec::Idx;
   9
  10 use super::{Analysis, Results, ResultsRefCursor};
  11 use crate::util::graphviz_safe_def_name;
  12
  13 pub struct Formatter<'a, 'tcx, A>
  14 where
  15     A: Analysis<'tcx>,
  16 {
  17     body: &'a Body<'tcx>,
  18     def_id: DefId,
  19
  20     // This must be behind a `RefCell` because `dot::Labeller` takes `&self`.
  21     block_formatter: RefCell<BlockFormatter<'a, 'tcx, A>>,
  22 }
  23
  24 impl<A> Formatter<'a, 'tcx, A>
  25 where
  26     A: Analysis<'tcx>,
  27 {
  28     pub fn new(body: &'a Body<'tcx>, def_id: DefId, results: &'a Results<'tcx, A>) -> Self {
  29         let block_formatter = BlockFormatter {
  30             bg: Background::Light,
  31             prev_state: BitSet::new_empty(results.analysis.bits_per_block(body)),
  32             results: ResultsRefCursor::new(body, results),
  33         };
  34
  35         Formatter { body, def_id, block_formatter: RefCell::new(block_formatter) }
  36     }
  37 }
  38
  39 /// A pair of a basic block and an index into that basic blocks `successors`.
  40 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  41 pub struct CfgEdge {
  42     source: BasicBlock,
  43     index: usize,
  44 }
  45
  46 fn outgoing_edges(body: &Body<'_>, bb: BasicBlock) -> Vec<CfgEdge> {
  47     body[bb]
  48         .terminator()
  49         .successors()
  50         .enumerate()
  51         .map(|(index, _)| CfgEdge { source: bb, index })
  52         .collect()
  53 }
  54
  55 impl<A> dot::Labeller<'_> for Formatter<'a, 'tcx, A>
  56 where
  57     A: Analysis<'tcx>,
  58 {
  59     type Node = BasicBlock;
  60     type Edge = CfgEdge;
  61
  62     fn graph_id(&self) -> dot::Id<'_> {
  63         let name = graphviz_safe_def_name(self.def_id);
  64         dot::Id::new(format!("graph_for_def_id_{}", name)).unwrap()
  65     }
  66
  67     fn node_id(&self, n: &Self::Node) -> dot::Id<'_> {
  68         dot::Id::new(format!("bb_{}", n.index())).unwrap()
  69     }
  70
  71     fn node_label(&self, block: &Self::Node) -> dot::LabelText<'_> {
  72         let mut label = Vec::new();
  73         self.block_formatter.borrow_mut().write_node_label(&mut label, self.body, *block).unwrap();
  74         dot::LabelText::html(String::from_utf8(label).unwrap())
  75     }
  76
  77     fn node_shape(&self, _n: &Self::Node) -> Option<dot::LabelText<'_>> {
  78         Some(dot::LabelText::label("none"))
  79     }
  80
  81     fn edge_label(&self, e: &Self::Edge) -> dot::LabelText<'_> {
  82         let label = &self.body[e.source].terminator().kind.fmt_successor_labels()[e.index];
  83         dot::LabelText::label(label.clone())
  84     }
  85 }
  86
  87 impl<A> dot::GraphWalk<'a> for Formatter<'a, 'tcx, A>
  88 where
  89     A: Analysis<'tcx>,
  90 {
  91     type Node = BasicBlock;
  92     type Edge = CfgEdge;
  93
  94     fn nodes(&self) -> dot::Nodes<'_, Self::Node> {
  95         self.body.basic_blocks().indices().collect::<Vec<_>>().into()
  96     }
  97
  98     fn edges(&self) -> dot::Edges<'_, Self::Edge> {
  99         self.body
 100             .basic_blocks()
 101             .indices()
 102             .flat_map(|bb| outgoing_edges(self.body, bb))
 103             .collect::<Vec<_>>()
 104             .into()
 105     }
 106
 107     fn source(&self, edge: &Self::Edge) -> Self::Node {
 108         edge.source
 109     }
 110
 111     fn target(&self, edge: &Self::Edge) -> Self::Node {
 112         self.body[edge.source].terminator().successors().nth(edge.index).copied().unwrap()
 113     }
 114 }
 115
 116 struct BlockFormatter<'a, 'tcx, A>
 117 where
 118     A: Analysis<'tcx>,
 119 {
 120     prev_state: BitSet<A::Idx>,
 121     results: ResultsRefCursor<'a, 'a, 'tcx, A>,
 122     bg: Background,
 123 }
 124
 125 impl<A> BlockFormatter<'a, 'tcx, A>
 126 where
 127     A: Analysis<'tcx>,
 128 {
 129     fn toggle_background(&mut self) -> Background {
 130         let bg = self.bg;
 131         self.bg = !bg;
 132         bg
 133     }
 134
 135     fn write_node_label(
 136         &mut self,
 137         w: &mut impl io::Write,
 138         body: &'a Body<'tcx>,
 139         block: BasicBlock,
 140     ) -> io::Result<()> {
 141         //   Sample output:
 142         //   +-+-----------------------------------------------+
 143         // A |                      bb4                        |
 144         //   +-+----------------------------------+------------+
 145         // B |                MIR                 |   STATE    |
 146         //   +-+----------------------------------+------------+
 147         // C | | (on entry)                       | {_0,_2,_3} |
 148         //   +-+----------------------------------+------------+
 149         // D |0| StorageLive(_7)                  |            |
 150         //   +-+----------------------------------+------------+
 151         //   |1| StorageLive(_8)                  |            |
 152         //   +-+----------------------------------+------------+
 153         //   |2| _8 = &mut _1                     | +_8        |
 154         //   +-+----------------------------------+------------+
 155         // E |T| _4 = const Foo::twiddle(move _2) | -_2        |
 156         //   +-+----------------------------------+------------+
 157         // F | | (on unwind)                      | {_0,_3,_8} |
 158         //   +-+----------------------------------+------------+
 159         //   | | (on successful return)           | +_4        |
 160         //   +-+----------------------------------+------------+
 161
 162         write!(
 163             w,
 164             r#"<table border="1" cellborder="1" cellspacing="0" cellpadding="3" sides="rb">"#,
 165         )?;
 166
 167         // A: Block info
 168         write!(
 169             w,
 170             r#"<tr>
 171                  <td colspan="{num_headers}" sides="tl">bb{block_id}</td>
 172                </tr>"#,
 173             num_headers = 3,
 174             block_id = block.index(),
 175         )?;
 176
 177         // B: Column headings
 178         write!(
 179             w,
 180             r#"<tr>
 181                  <td colspan="2" {fmt}>MIR</td>
 182                  <td {fmt}>STATE</td>
 183                </tr>"#,
 184             fmt = r##"bgcolor="#a0a0a0" sides="tl""##,
 185         )?;
 186
 187         // C: Entry state
 188         self.bg = Background::Light;
 189         self.results.seek_to_block_start(block);
 190         self.write_row_with_curr_state(w, "", "(on entry)")?;
 191         self.prev_state.overwrite(self.results.get());
 192
 193         // D: Statement transfer functions
 194         for (i, statement) in body[block].statements.iter().enumerate() {
 195             let location = Location { block, statement_index: i };
 196
 197             let mir_col = format!("{:?}", statement);
 198             let i_col = i.to_string();
 199
 200             self.results.seek_after(location);
 201             self.write_row_with_curr_diff(w, &i_col, &mir_col)?;
 202             self.prev_state.overwrite(self.results.get());
 203         }
 204
 205         // E: Terminator transfer function
 206         let terminator = body[block].terminator();
 207         let location = body.terminator_loc(block);
 208
 209         let mut mir_col = String::new();
 210         terminator.kind.fmt_head(&mut mir_col).unwrap();
 211
 212         self.results.seek_after(location);
 213         self.write_row_with_curr_diff(w, "T", &mir_col)?;
 214         self.prev_state.overwrite(self.results.get());
 215
 216         // F: Exit state
 217         if let mir::TerminatorKind::Call { destination: Some(_), .. } = &terminator.kind {
 218             self.write_row_with_curr_state(w, "", "(on unwind)")?;
 219
 220             self.results.seek_after_assume_call_returns(location);
 221             self.write_row_with_curr_diff(w, "", "(on successful return)")?;
 222         } else {
 223             self.write_row_with_curr_state(w, "", "(on exit)")?;
 224         }
 225
 226         write!(w, "</table>")
 227     }
 228
 229     fn write_row_with_curr_state(
 230         &mut self,
 231         w: &mut impl io::Write,
 232         i: &str,
 233         mir: &str,
 234     ) -> io::Result<()> {
 235         let bg = self.toggle_background();
 236
 237         let mut out = Vec::new();
 238         write!(&mut out, "{{")?;
 239         pretty_print_state_elems(&mut out, self.results.analysis(), self.results.get().iter())?;
 240         write!(&mut out, "}}")?;
 241
 242         write!(
 243             w,
 244             r#"<tr>
 245                  <td {fmt} align="right">{i}</td>
 246                  <td {fmt} align="left">{mir}</td>
 247                  <td {fmt} align="left">{state}</td>
 248                </tr>"#,
 249             fmt = &["sides=\"tl\"", bg.attr()].join(" "),
 250             i = i,
 251             mir = dot::escape_html(mir),
 252             state = dot::escape_html(str::from_utf8(&out).unwrap()),
 253         )
 254     }
 255
 256     fn write_row_with_curr_diff(
 257         &mut self,
 258         w: &mut impl io::Write,
 259         i: &str,
 260         mir: &str,
 261     ) -> io::Result<()> {
 262         let bg = self.toggle_background();
 263         let analysis = self.results.analysis();
 264
 265         let diff = BitSetDiff::compute(&self.prev_state, self.results.get());
 266
 267         let mut set = Vec::new();
 268         pretty_print_state_elems(&mut set, analysis, diff.set.iter())?;
 269
 270         let mut clear = Vec::new();
 271         pretty_print_state_elems(&mut clear, analysis, diff.clear.iter())?;
 272
 273         write!(
 274             w,
 275             r#"<tr>
 276                  <td {fmt} align="right">{i}</td>
 277                  <td {fmt} align="left">{mir}</td>
 278                  <td {fmt} align="left">"#,
 279             i = i,
 280             fmt = &["sides=\"tl\"", bg.attr()].join(" "),
 281             mir = dot::escape_html(mir),
 282         )?;
 283
 284         if !set.is_empty() {
 285             write!(
 286                 w,
 287                 r#"<font color="darkgreen">+{}</font>"#,
 288                 dot::escape_html(str::from_utf8(&set).unwrap()),
 289             )?;
 290         }
 291
 292         if !set.is_empty() && !clear.is_empty() {
 293             write!(w, "  ")?;
 294         }
 295
 296         if !clear.is_empty() {
 297             write!(
 298                 w,
 299                 r#"<font color="red">-{}</font>"#,
 300                 dot::escape_html(str::from_utf8(&clear).unwrap()),
 301             )?;
 302         }
 303
 304         write!(w, "</td></tr>")
 305     }
 306 }
 307
 308 /// The operations required to transform one `BitSet` into another.
 309 struct BitSetDiff<T: Idx> {
 310     set: HybridBitSet<T>,
 311     clear: HybridBitSet<T>,
 312 }
 313
 314 impl<T: Idx> BitSetDiff<T> {
 315     fn compute(from: &BitSet<T>, to: &BitSet<T>) -> Self {
 316         assert_eq!(from.domain_size(), to.domain_size());
 317         let len = from.domain_size();
 318
 319         let mut set = HybridBitSet::new_empty(len);
 320         let mut clear = HybridBitSet::new_empty(len);
 321
 322         // FIXME: This could be made faster if `BitSet::xor` were implemented.
 323         for i in (0..len).map(|i| T::new(i)) {
 324             match (from.contains(i), to.contains(i)) {
 325                 (false, true) => set.insert(i),
 326                 (true, false) => clear.insert(i),
 327                 _ => continue,
 328             };
 329         }
 330
 331         BitSetDiff { set, clear }
 332     }
 333 }
 334
 335 /// Formats each `elem` using the pretty printer provided by `analysis` into a comma-separated
 336 /// list.
 337 fn pretty_print_state_elems<A>(
 338     w: &mut impl io::Write,
 339     analysis: &A,
 340     elems: impl Iterator<Item = A::Idx>,
 341 ) -> io::Result<()>
 342 where
 343     A: Analysis<'tcx>,
 344 {
 345     let mut first = true;
 346     for idx in elems {
 347         if first {
 348             first = false;
 349         } else {
 350             write!(w, ",")?;
 351         }
 352
 353         analysis.pretty_print_idx(w, idx)?;
 354     }
 355
 356     Ok(())
 357 }
 358
 359 /// The background color used for zebra-striping the table.
 360 #[derive(Clone, Copy)]
 361 enum Background {
 362     Light,
 363     Dark,
 364 }
 365
 366 impl Background {
 367     fn attr(self) -> &'static str {
 368         match self {
 369             Self::Dark => "bgcolor=\"#f0f0f0\"",
 370             Self::Light => "",
 371         }
 372     }
 373 }
 374
 375 impl ops::Not for Background {
 376     type Output = Self;
 377
 378     fn not(self) -> Self {
 379         match self {
 380             Self::Light => Self::Dark,
 381             Self::Dark => Self::Light,
 382         }
 383     }
 384 }