src/libgraphviz/lib.rs

   1 // Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Generate files suitable for use with [Graphviz](http://www.graphviz.org/)
  12 //!
  13 //! The `render` function generates output (e.g. an `output.dot` file) for
  14 //! use with [Graphviz](http://www.graphviz.org/) by walking a labelled
  15 //! graph. (Graphviz can then automatically lay out the nodes and edges
  16 //! of the graph, and also optionally render the graph as an image or
  17 //! other [output formats](
  18 //! http://www.graphviz.org/content/output-formats), such as SVG.)
  19 //!
  20 //! Rather than impose some particular graph data structure on clients,
  21 //! this library exposes two traits that clients can implement on their
  22 //! own structs before handing them over to the rendering function.
  23 //!
  24 //! Note: This library does not yet provide access to the full
  25 //! expressiveness of the [DOT language](
  26 //! http://www.graphviz.org/doc/info/lang.html). For example, there are
  27 //! many [attributes](http://www.graphviz.org/content/attrs) related to
  28 //! providing layout hints (e.g. left-to-right versus top-down, which
  29 //! algorithm to use, etc). The current intention of this library is to
  30 //! emit a human-readable .dot file with very regular structure suitable
  31 //! for easy post-processing.
  32 //!
  33 //! # Examples
  34 //!
  35 //! The first example uses a very simple graph representation: a list of
  36 //! pairs of ints, representing the edges (the node set is implicit).
  37 //! Each node label is derived directly from the int representing the node,
  38 //! while the edge labels are all empty strings.
  39 //!
  40 //! This example also illustrates how to use `Cow<[T]>` to return
  41 //! an owned vector or a borrowed slice as appropriate: we construct the
  42 //! node vector from scratch, but borrow the edge list (rather than
  43 //! constructing a copy of all the edges from scratch).
  44 //!
  45 //! The output from this example renders five nodes, with the first four
  46 //! forming a diamond-shaped acyclic graph and then pointing to the fifth
  47 //! which is cyclic.
  48 //!
  49 //! ```rust
  50 //! #![feature(rustc_private)]
  51 //!
  52 //! use graphviz::IntoCow;
  53 //! use std::io::Write;
  54 //! use graphviz as dot;
  55 //!
  56 //! type Nd = isize;
  57 //! type Ed = (isize,isize);
  58 //! struct Edges(Vec<Ed>);
  59 //!
  60 //! pub fn render_to<W: Write>(output: &mut W) {
  61 //!     let edges = Edges(vec![(0,1), (0,2), (1,3), (2,3), (3,4), (4,4)]);
  62 //!     dot::render(&edges, output).unwrap()
  63 //! }
  64 //!
  65 //! impl<'a> dot::Labeller<'a> for Edges {
  66 //!     type Node = Nd;
  67 //!     type Edge = Ed;
  68 //!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example1").unwrap() }
  69 //!
  70 //!     fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
  71 //!         dot::Id::new(format!("N{}", *n)).unwrap()
  72 //!     }
  73 //! }
  74 //!
  75 //! impl<'a> dot::GraphWalk<'a> for Edges {
  76 //!     type Node = Nd;
  77 //!     type Edge = Ed;
  78 //!     fn nodes(&self) -> dot::Nodes<'a,Nd> {
  79 //!         // (assumes that |N| \approxeq |E|)
  80 //!         let &Edges(ref v) = self;
  81 //!         let mut nodes = Vec::with_capacity(v.len());
  82 //!         for &(s,t) in v {
  83 //!             nodes.push(s); nodes.push(t);
  84 //!         }
  85 //!         nodes.sort();
  86 //!         nodes.dedup();
  87 //!         nodes.into_cow()
  88 //!     }
  89 //!
  90 //!     fn edges(&'a self) -> dot::Edges<'a,Ed> {
  91 //!         let &Edges(ref edges) = self;
  92 //!         (&edges[..]).into_cow()
  93 //!     }
  94 //!
  95 //!     fn source(&self, e: &Ed) -> Nd { let &(s,_) = e; s }
  96 //!
  97 //!     fn target(&self, e: &Ed) -> Nd { let &(_,t) = e; t }
  98 //! }
  99 //!
 100 //! # pub fn main() { render_to(&mut Vec::new()) }
 101 //! ```
 102 //!
 103 //! ```no_run
 104 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
 105 //! pub fn main() {
 106 //!     use std::fs::File;
 107 //!     let mut f = File::create("example1.dot").unwrap();
 108 //!     render_to(&mut f)
 109 //! }
 110 //! ```
 111 //!
 112 //! Output from first example (in `example1.dot`):
 113 //!
 114 //! ```ignore
 115 //! digraph example1 {
 116 //!     N0[label="N0"];
 117 //!     N1[label="N1"];
 118 //!     N2[label="N2"];
 119 //!     N3[label="N3"];
 120 //!     N4[label="N4"];
 121 //!     N0 -> N1[label=""];
 122 //!     N0 -> N2[label=""];
 123 //!     N1 -> N3[label=""];
 124 //!     N2 -> N3[label=""];
 125 //!     N3 -> N4[label=""];
 126 //!     N4 -> N4[label=""];
 127 //! }
 128 //! ```
 129 //!
 130 //! The second example illustrates using `node_label` and `edge_label` to
 131 //! add labels to the nodes and edges in the rendered graph. The graph
 132 //! here carries both `nodes` (the label text to use for rendering a
 133 //! particular node), and `edges` (again a list of `(source,target)`
 134 //! indices).
 135 //!
 136 //! This example also illustrates how to use a type (in this case the edge
 137 //! type) that shares substructure with the graph: the edge type here is a
 138 //! direct reference to the `(source,target)` pair stored in the graph's
 139 //! internal vector (rather than passing around a copy of the pair
 140 //! itself). Note that this implies that `fn edges(&'a self)` must
 141 //! construct a fresh `Vec<&'a (usize,usize)>` from the `Vec<(usize,usize)>`
 142 //! edges stored in `self`.
 143 //!
 144 //! Since both the set of nodes and the set of edges are always
 145 //! constructed from scratch via iterators, we use the `collect()` method
 146 //! from the `Iterator` trait to collect the nodes and edges into freshly
 147 //! constructed growable `Vec` values (rather use the `into_cow`
 148 //! from the `IntoCow` trait as was used in the first example
 149 //! above).
 150 //!
 151 //! The output from this example renders four nodes that make up the
 152 //! Hasse-diagram for the subsets of the set `{x, y}`. Each edge is
 153 //! labelled with the &sube; character (specified using the HTML character
 154 //! entity `&sube`).
 155 //!
 156 //! ```rust
 157 //! #![feature(rustc_private)]
 158 //!
 159 //! use std::io::Write;
 160 //! use graphviz as dot;
 161 //!
 162 //! type Nd = usize;
 163 //! type Ed<'a> = &'a (usize, usize);
 164 //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
 165 //!
 166 //! pub fn render_to<W: Write>(output: &mut W) {
 167 //!     let nodes = vec!["{x,y}","{x}","{y}","{}"];
 168 //!     let edges = vec![(0,1), (0,2), (1,3), (2,3)];
 169 //!     let graph = Graph { nodes: nodes, edges: edges };
 170 //!
 171 //!     dot::render(&graph, output).unwrap()
 172 //! }
 173 //!
 174 //! impl<'a> dot::Labeller<'a> for Graph {
 175 //!     type Node = Nd;
 176 //!     type Edge = Ed<'a>;
 177 //!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example2").unwrap() }
 178 //!     fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
 179 //!         dot::Id::new(format!("N{}", n)).unwrap()
 180 //!     }
 181 //!     fn node_label<'b>(&'b self, n: &Nd) -> dot::LabelText<'b> {
 182 //!         dot::LabelText::LabelStr(self.nodes[*n].into())
 183 //!     }
 184 //!     fn edge_label<'b>(&'b self, _: &Ed) -> dot::LabelText<'b> {
 185 //!         dot::LabelText::LabelStr("&sube;".into())
 186 //!     }
 187 //! }
 188 //!
 189 //! impl<'a> dot::GraphWalk<'a> for Graph {
 190 //!     type Node = Nd;
 191 //!     type Edge = Ed<'a>;
 192 //!     fn nodes(&self) -> dot::Nodes<'a,Nd> { (0..self.nodes.len()).collect() }
 193 //!     fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { self.edges.iter().collect() }
 194 //!     fn source(&self, e: &Ed) -> Nd { let & &(s,_) = e; s }
 195 //!     fn target(&self, e: &Ed) -> Nd { let & &(_,t) = e; t }
 196 //! }
 197 //!
 198 //! # pub fn main() { render_to(&mut Vec::new()) }
 199 //! ```
 200 //!
 201 //! ```no_run
 202 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
 203 //! pub fn main() {
 204 //!     use std::fs::File;
 205 //!     let mut f = File::create("example2.dot").unwrap();
 206 //!     render_to(&mut f)
 207 //! }
 208 //! ```
 209 //!
 210 //! The third example is similar to the second, except now each node and
 211 //! edge now carries a reference to the string label for each node as well
 212 //! as that node's index. (This is another illustration of how to share
 213 //! structure with the graph itself, and why one might want to do so.)
 214 //!
 215 //! The output from this example is the same as the second example: the
 216 //! Hasse-diagram for the subsets of the set `{x, y}`.
 217 //!
 218 //! ```rust
 219 //! #![feature(rustc_private)]
 220 //!
 221 //! use std::io::Write;
 222 //! use graphviz as dot;
 223 //!
 224 //! type Nd<'a> = (usize, &'a str);
 225 //! type Ed<'a> = (Nd<'a>, Nd<'a>);
 226 //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
 227 //!
 228 //! pub fn render_to<W: Write>(output: &mut W) {
 229 //!     let nodes = vec!["{x,y}","{x}","{y}","{}"];
 230 //!     let edges = vec![(0,1), (0,2), (1,3), (2,3)];
 231 //!     let graph = Graph { nodes: nodes, edges: edges };
 232 //!
 233 //!     dot::render(&graph, output).unwrap()
 234 //! }
 235 //!
 236 //! impl<'a> dot::Labeller<'a> for Graph {
 237 //!     type Node = Nd<'a>;
 238 //!     type Edge = Ed<'a>;
 239 //!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example3").unwrap() }
 240 //!     fn node_id(&'a self, n: &Nd<'a>) -> dot::Id<'a> {
 241 //!         dot::Id::new(format!("N{}", n.0)).unwrap()
 242 //!     }
 243 //!     fn node_label<'b>(&'b self, n: &Nd<'b>) -> dot::LabelText<'b> {
 244 //!         let &(i, _) = n;
 245 //!         dot::LabelText::LabelStr(self.nodes[i].into())
 246 //!     }
 247 //!     fn edge_label<'b>(&'b self, _: &Ed<'b>) -> dot::LabelText<'b> {
 248 //!         dot::LabelText::LabelStr("&sube;".into())
 249 //!     }
 250 //! }
 251 //!
 252 //! impl<'a> dot::GraphWalk<'a> for Graph {
 253 //!     type Node = Nd<'a>;
 254 //!     type Edge = Ed<'a>;
 255 //!     fn nodes(&'a self) -> dot::Nodes<'a,Nd<'a>> {
 256 //!         self.nodes.iter().map(|s| &s[..]).enumerate().collect()
 257 //!     }
 258 //!     fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> {
 259 //!         self.edges.iter()
 260 //!             .map(|&(i,j)|((i, &self.nodes[i][..]),
 261 //!                           (j, &self.nodes[j][..])))
 262 //!             .collect()
 263 //!     }
 264 //!     fn source(&self, e: &Ed<'a>) -> Nd<'a> { let &(s,_) = e; s }
 265 //!     fn target(&self, e: &Ed<'a>) -> Nd<'a> { let &(_,t) = e; t }
 266 //! }
 267 //!
 268 //! # pub fn main() { render_to(&mut Vec::new()) }
 269 //! ```
 270 //!
 271 //! ```no_run
 272 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
 273 //! pub fn main() {
 274 //!     use std::fs::File;
 275 //!     let mut f = File::create("example3.dot").unwrap();
 276 //!     render_to(&mut f)
 277 //! }
 278 //! ```
 279 //!
 280 //! # References
 281 //!
 282 //! * [Graphviz](http://www.graphviz.org/)
 283 //!
 284 //! * [DOT language](http://www.graphviz.org/doc/info/lang.html)
 285
 286 #![crate_name = "graphviz"]
 287 #![unstable(feature = "rustc_private", issue = "27812")]
 288 #![feature(staged_api)]
 289 #![crate_type = "rlib"]
 290 #![crate_type = "dylib"]
 291 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
 292        html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
 293        html_root_url = "https://doc.rust-lang.org/nightly/",
 294        test(attr(allow(unused_variables), deny(warnings))))]
 295 #![cfg_attr(not(stage0), deny(warnings))]
 296
 297 #![feature(str_escape)]
 298 #![cfg_attr(stage0, feature(question_mark))]
 299
 300 use self::LabelText::*;
 301
 302 use std::borrow::{Cow, ToOwned};
 303 use std::io::prelude::*;
 304 use std::io;
 305
 306 /// The text for a graphviz label on a node or edge.
 307 pub enum LabelText<'a> {
 308     /// This kind of label preserves the text directly as is.
 309     ///
 310     /// Occurrences of backslashes (`\`) are escaped, and thus appear
 311     /// as backslashes in the rendered label.
 312     LabelStr(Cow<'a, str>),
 313
 314     /// This kind of label uses the graphviz label escString type:
 315     /// http://www.graphviz.org/content/attrs#kescString
 316     ///
 317     /// Occurrences of backslashes (`\`) are not escaped; instead they
 318     /// are interpreted as initiating an escString escape sequence.
 319     ///
 320     /// Escape sequences of particular interest: in addition to `\n`
 321     /// to break a line (centering the line preceding the `\n`), there
 322     /// are also the escape sequences `\l` which left-justifies the
 323     /// preceding line and `\r` which right-justifies it.
 324     EscStr(Cow<'a, str>),
 325
 326     /// This uses a graphviz [HTML string label][html]. The string is
 327     /// printed exactly as given, but between `<` and `>`. **No
 328     /// escaping is performed.**
 329     ///
 330     /// [html]: http://www.graphviz.org/content/node-shapes#html
 331     HtmlStr(Cow<'a, str>),
 332 }
 333
 334 /// The style for a node or edge.
 335 /// See http://www.graphviz.org/doc/info/attrs.html#k:style for descriptions.
 336 /// Note that some of these are not valid for edges.
 337 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 338 pub enum Style {
 339     None,
 340     Solid,
 341     Dashed,
 342     Dotted,
 343     Bold,
 344     Rounded,
 345     Diagonals,
 346     Filled,
 347     Striped,
 348     Wedged,
 349 }
 350
 351 impl Style {
 352     pub fn as_slice(self) -> &'static str {
 353         match self {
 354             Style::None => "",
 355             Style::Solid => "solid",
 356             Style::Dashed => "dashed",
 357             Style::Dotted => "dotted",
 358             Style::Bold => "bold",
 359             Style::Rounded => "rounded",
 360             Style::Diagonals => "diagonals",
 361             Style::Filled => "filled",
 362             Style::Striped => "striped",
 363             Style::Wedged => "wedged",
 364         }
 365     }
 366 }
 367
 368 // There is a tension in the design of the labelling API.
 369 //
 370 // For example, I considered making a `Labeller<T>` trait that
 371 // provides labels for `T`, and then making the graph type `G`
 372 // implement `Labeller<Node>` and `Labeller<Edge>`. However, this is
 373 // not possible without functional dependencies. (One could work
 374 // around that, but I did not explore that avenue heavily.)
 375 //
 376 // Another approach that I actually used for a while was to make a
 377 // `Label<Context>` trait that is implemented by the client-specific
 378 // Node and Edge types (as well as an implementation on Graph itself
 379 // for the overall name for the graph). The main disadvantage of this
 380 // second approach (compared to having the `G` type parameter
 381 // implement a Labelling service) that I have encountered is that it
 382 // makes it impossible to use types outside of the current crate
 383 // directly as Nodes/Edges; you need to wrap them in newtype'd
 384 // structs. See e.g. the `No` and `Ed` structs in the examples. (In
 385 // practice clients using a graph in some other crate would need to
 386 // provide some sort of adapter shim over the graph anyway to
 387 // interface with this library).
 388 //
 389 // Another approach would be to make a single `Labeller<N,E>` trait
 390 // that provides three methods (graph_label, node_label, edge_label),
 391 // and then make `G` implement `Labeller<N,E>`. At first this did not
 392 // appeal to me, since I had thought I would need separate methods on
 393 // each data variant for dot-internal identifiers versus user-visible
 394 // labels. However, the identifier/label distinction only arises for
 395 // nodes; graphs themselves only have identifiers, and edges only have
 396 // labels.
 397 //
 398 // So in the end I decided to use the third approach described above.
 399
 400 /// `Id` is a Graphviz `ID`.
 401 pub struct Id<'a> {
 402     name: Cow<'a, str>,
 403 }
 404
 405 impl<'a> Id<'a> {
 406     /// Creates an `Id` named `name`.
 407     ///
 408     /// The caller must ensure that the input conforms to an
 409     /// identifier format: it must be a non-empty string made up of
 410     /// alphanumeric or underscore characters, not beginning with a
 411     /// digit (i.e. the regular expression `[a-zA-Z_][a-zA-Z_0-9]*`).
 412     ///
 413     /// (Note: this format is a strict subset of the `ID` format
 414     /// defined by the DOT language.  This function may change in the
 415     /// future to accept a broader subset, or the entirety, of DOT's
 416     /// `ID` format.)
 417     ///
 418     /// Passing an invalid string (containing spaces, brackets,
 419     /// quotes, ...) will return an empty `Err` value.
 420     pub fn new<Name: IntoCow<'a, str>>(name: Name) -> Result<Id<'a>, ()> {
 421         let name = name.into_cow();
 422         {
 423             let mut chars = name.chars();
 424             match chars.next() {
 425                 Some(c) if is_letter_or_underscore(c) => {}
 426                 _ => return Err(()),
 427             }
 428             if !chars.all(is_constituent) {
 429                 return Err(());
 430             }
 431         }
 432         return Ok(Id { name: name });
 433
 434         fn is_letter_or_underscore(c: char) -> bool {
 435             in_range('a', c, 'z') || in_range('A', c, 'Z') || c == '_'
 436         }
 437         fn is_constituent(c: char) -> bool {
 438             is_letter_or_underscore(c) || in_range('0', c, '9')
 439         }
 440         fn in_range(low: char, c: char, high: char) -> bool {
 441             low as usize <= c as usize && c as usize <= high as usize
 442         }
 443     }
 444
 445     pub fn as_slice(&'a self) -> &'a str {
 446         &*self.name
 447     }
 448
 449     pub fn name(self) -> Cow<'a, str> {
 450         self.name
 451     }
 452 }
 453
 454 /// Each instance of a type that implements `Label<C>` maps to a
 455 /// unique identifier with respect to `C`, which is used to identify
 456 /// it in the generated .dot file. They can also provide more
 457 /// elaborate (and non-unique) label text that is used in the graphviz
 458 /// rendered output.
 459
 460 /// The graph instance is responsible for providing the DOT compatible
 461 /// identifiers for the nodes and (optionally) rendered labels for the nodes and
 462 /// edges, as well as an identifier for the graph itself.
 463 pub trait Labeller<'a> {
 464     type Node;
 465     type Edge;
 466
 467     /// Must return a DOT compatible identifier naming the graph.
 468     fn graph_id(&'a self) -> Id<'a>;
 469
 470     /// Maps `n` to a unique identifier with respect to `self`. The
 471     /// implementor is responsible for ensuring that the returned name
 472     /// is a valid DOT identifier.
 473     fn node_id(&'a self, n: &Self::Node) -> Id<'a>;
 474
 475     /// Maps `n` to one of the [graphviz `shape` names][1]. If `None`
 476     /// is returned, no `shape` attribute is specified.
 477     ///
 478     /// [1]: http://www.graphviz.org/content/node-shapes
 479     fn node_shape(&'a self, _node: &Self::Node) -> Option<LabelText<'a>> {
 480         None
 481     }
 482
 483     /// Maps `n` to a label that will be used in the rendered output.
 484     /// The label need not be unique, and may be the empty string; the
 485     /// default is just the output from `node_id`.
 486     fn node_label(&'a self, n: &Self::Node) -> LabelText<'a> {
 487         LabelStr(self.node_id(n).name)
 488     }
 489
 490     /// Maps `e` to a label that will be used in the rendered output.
 491     /// The label need not be unique, and may be the empty string; the
 492     /// default is in fact the empty string.
 493     fn edge_label(&'a self, e: &Self::Edge) -> LabelText<'a> {
 494         let _ignored = e;
 495         LabelStr("".into_cow())
 496     }
 497
 498     /// Maps `n` to a style that will be used in the rendered output.
 499     fn node_style(&'a self, _n: &Self::Node) -> Style {
 500         Style::None
 501     }
 502
 503     /// Maps `e` to a style that will be used in the rendered output.
 504     fn edge_style(&'a self, _e: &Self::Edge) -> Style {
 505         Style::None
 506     }
 507 }
 508
 509 /// Escape tags in such a way that it is suitable for inclusion in a
 510 /// Graphviz HTML label.
 511 pub fn escape_html(s: &str) -> String {
 512     s.replace("&", "&amp;")
 513      .replace("\"", "&quot;")
 514      .replace("<", "&lt;")
 515      .replace(">", "&gt;")
 516 }
 517
 518 impl<'a> LabelText<'a> {
 519     pub fn label<S: IntoCow<'a, str>>(s: S) -> LabelText<'a> {
 520         LabelStr(s.into_cow())
 521     }
 522
 523     pub fn escaped<S: IntoCow<'a, str>>(s: S) -> LabelText<'a> {
 524         EscStr(s.into_cow())
 525     }
 526
 527     pub fn html<S: IntoCow<'a, str>>(s: S) -> LabelText<'a> {
 528         HtmlStr(s.into_cow())
 529     }
 530
 531     fn escape_char<F>(c: char, mut f: F)
 532         where F: FnMut(char)
 533     {
 534         match c {
 535             // not escaping \\, since Graphviz escString needs to
 536             // interpret backslashes; see EscStr above.
 537             '\\' => f(c),
 538             _ => {
 539                 for c in c.escape_default() {
 540                     f(c)
 541                 }
 542             }
 543         }
 544     }
 545     fn escape_str(s: &str) -> String {
 546         let mut out = String::with_capacity(s.len());
 547         for c in s.chars() {
 548             LabelText::escape_char(c, |c| out.push(c));
 549         }
 550         out
 551     }
 552
 553     /// Renders text as string suitable for a label in a .dot file.
 554     /// This includes quotes or suitable delimeters.
 555     pub fn to_dot_string(&self) -> String {
 556         match self {
 557             &LabelStr(ref s) => format!("\"{}\"", s.escape_default()),
 558             &EscStr(ref s) => format!("\"{}\"", LabelText::escape_str(&s[..])),
 559             &HtmlStr(ref s) => format!("<{}>", s),
 560         }
 561     }
 562
 563     /// Decomposes content into string suitable for making EscStr that
 564     /// yields same content as self.  The result obeys the law
 565     /// render(`lt`) == render(`EscStr(lt.pre_escaped_content())`) for
 566     /// all `lt: LabelText`.
 567     fn pre_escaped_content(self) -> Cow<'a, str> {
 568         match self {
 569             EscStr(s) => s,
 570             LabelStr(s) => {
 571                 if s.contains('\\') {
 572                     (&*s).escape_default().into_cow()
 573                 } else {
 574                     s
 575                 }
 576             }
 577             HtmlStr(s) => s,
 578         }
 579     }
 580
 581     /// Puts `prefix` on a line above this label, with a blank line separator.
 582     pub fn prefix_line(self, prefix: LabelText) -> LabelText<'static> {
 583         prefix.suffix_line(self)
 584     }
 585
 586     /// Puts `suffix` on a line below this label, with a blank line separator.
 587     pub fn suffix_line(self, suffix: LabelText) -> LabelText<'static> {
 588         let mut prefix = self.pre_escaped_content().into_owned();
 589         let suffix = suffix.pre_escaped_content();
 590         prefix.push_str(r"\n\n");
 591         prefix.push_str(&suffix[..]);
 592         EscStr(prefix.into_cow())
 593     }
 594 }
 595
 596 pub type Nodes<'a,N> = Cow<'a,[N]>;
 597 pub type Edges<'a,E> = Cow<'a,[E]>;
 598
 599 // (The type parameters in GraphWalk should be associated items,
 600 // when/if Rust supports such.)
 601
 602 /// GraphWalk is an abstraction over a directed graph = (nodes,edges)
 603 /// made up of node handles `N` and edge handles `E`, where each `E`
 604 /// can be mapped to its source and target nodes.
 605 ///
 606 /// The lifetime parameter `'a` is exposed in this trait (rather than
 607 /// introduced as a generic parameter on each method declaration) so
 608 /// that a client impl can choose `N` and `E` that have substructure
 609 /// that is bound by the self lifetime `'a`.
 610 ///
 611 /// The `nodes` and `edges` method each return instantiations of
 612 /// `Cow<[T]>` to leave implementors the freedom to create
 613 /// entirely new vectors or to pass back slices into internally owned
 614 /// vectors.
 615 pub trait GraphWalk<'a> {
 616     type Node: Clone;
 617     type Edge: Clone;
 618
 619     /// Returns all the nodes in this graph.
 620     fn nodes(&'a self) -> Nodes<'a, Self::Node>;
 621     /// Returns all of the edges in this graph.
 622     fn edges(&'a self) -> Edges<'a, Self::Edge>;
 623     /// The source node for `edge`.
 624     fn source(&'a self, edge: &Self::Edge) -> Self::Node;
 625     /// The target node for `edge`.
 626     fn target(&'a self, edge: &Self::Edge) -> Self::Node;
 627 }
 628
 629 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 630 pub enum RenderOption {
 631     NoEdgeLabels,
 632     NoNodeLabels,
 633     NoEdgeStyles,
 634     NoNodeStyles,
 635 }
 636
 637 /// Returns vec holding all the default render options.
 638 pub fn default_options() -> Vec<RenderOption> {
 639     vec![]
 640 }
 641
 642 /// Renders directed graph `g` into the writer `w` in DOT syntax.
 643 /// (Simple wrapper around `render_opts` that passes a default set of options.)
 644 pub fn render<'a,N,E,G,W>(g: &'a G, w: &mut W) -> io::Result<()>
 645     where N: Clone + 'a,
 646           E: Clone + 'a,
 647           G: Labeller<'a, Node=N, Edge=E> + GraphWalk<'a, Node=N, Edge=E>,
 648           W: Write
 649 {
 650     render_opts(g, w, &[])
 651 }
 652
 653 /// Renders directed graph `g` into the writer `w` in DOT syntax.
 654 /// (Main entry point for the library.)
 655 pub fn render_opts<'a, N, E, G, W>(g: &'a G,
 656                                    w: &mut W,
 657                                    options: &[RenderOption])
 658                                    -> io::Result<()>
 659     where N: Clone + 'a,
 660           E: Clone + 'a,
 661           G: Labeller<'a, Node=N, Edge=E> + GraphWalk<'a, Node=N, Edge=E>,
 662           W: Write
 663 {
 664     fn writeln<W: Write>(w: &mut W, arg: &[&str]) -> io::Result<()> {
 665         for &s in arg {
 666             w.write_all(s.as_bytes())?;
 667         }
 668         write!(w, "\n")
 669     }
 670
 671     fn indent<W: Write>(w: &mut W) -> io::Result<()> {
 672         w.write_all(b"    ")
 673     }
 674
 675     writeln(w, &["digraph ", g.graph_id().as_slice(), " {"])?;
 676     for n in g.nodes().iter() {
 677         indent(w)?;
 678         let id = g.node_id(n);
 679
 680         let escaped = &g.node_label(n).to_dot_string();
 681         let shape;
 682
 683         let mut text = vec![id.as_slice()];
 684
 685         if !options.contains(&RenderOption::NoNodeLabels) {
 686             text.push("[label=");
 687             text.push(escaped);
 688             text.push("]");
 689         }
 690
 691         let style = g.node_style(n);
 692         if !options.contains(&RenderOption::NoNodeStyles) && style != Style::None {
 693             text.push("[style=\"");
 694             text.push(style.as_slice());
 695             text.push("\"]");
 696         }
 697
 698         if let Some(s) = g.node_shape(n) {
 699             shape = s.to_dot_string();
 700             text.push("[shape=");
 701             text.push(&shape);
 702             text.push("]");
 703         }
 704
 705         text.push(";");
 706         writeln(w, &text)?;
 707     }
 708
 709     for e in g.edges().iter() {
 710         let escaped_label = &g.edge_label(e).to_dot_string();
 711         indent(w)?;
 712         let source = g.source(e);
 713         let target = g.target(e);
 714         let source_id = g.node_id(&source);
 715         let target_id = g.node_id(&target);
 716
 717         let mut text = vec![source_id.as_slice(), " -> ", target_id.as_slice()];
 718
 719         if !options.contains(&RenderOption::NoEdgeLabels) {
 720             text.push("[label=");
 721             text.push(escaped_label);
 722             text.push("]");
 723         }
 724
 725         let style = g.edge_style(e);
 726         if !options.contains(&RenderOption::NoEdgeStyles) && style != Style::None {
 727             text.push("[style=\"");
 728             text.push(style.as_slice());
 729             text.push("\"]");
 730         }
 731
 732         text.push(";");
 733         writeln(w, &text)?;
 734     }
 735
 736     writeln(w, &["}"])
 737 }
 738
 739 pub trait IntoCow<'a, B: ?Sized> where B: ToOwned {
 740     fn into_cow(self) -> Cow<'a, B>;
 741 }
 742
 743 impl<'a> IntoCow<'a, str> for String {
 744     fn into_cow(self) -> Cow<'a, str> {
 745         Cow::Owned(self)
 746     }
 747 }
 748
 749 impl<'a> IntoCow<'a, str> for &'a str {
 750     fn into_cow(self) -> Cow<'a, str> {
 751         Cow::Borrowed(self)
 752     }
 753 }
 754
 755 impl<'a, T: Clone> IntoCow<'a, [T]> for Vec<T> {
 756     fn into_cow(self) -> Cow<'a, [T]> {
 757         Cow::Owned(self)
 758     }
 759 }
 760
 761 impl<'a, T: Clone> IntoCow<'a, [T]> for &'a [T] {
 762     fn into_cow(self) -> Cow<'a, [T]> {
 763         Cow::Borrowed(self)
 764     }
 765 }
 766
 767 #[cfg(test)]
 768 mod tests {
 769     use self::NodeLabels::*;
 770     use super::{Id, Labeller, Nodes, Edges, GraphWalk, render, Style};
 771     use super::LabelText::{self, LabelStr, EscStr, HtmlStr};
 772     use std::io;
 773     use std::io::prelude::*;
 774     use IntoCow;
 775
 776     /// each node is an index in a vector in the graph.
 777     type Node = usize;
 778     struct Edge {
 779         from: usize,
 780         to: usize,
 781         label: &'static str,
 782         style: Style,
 783     }
 784
 785     fn edge(from: usize, to: usize, label: &'static str, style: Style) -> Edge {
 786         Edge {
 787             from: from,
 788             to: to,
 789             label: label,
 790             style: style,
 791         }
 792     }
 793
 794     struct LabelledGraph {
 795         /// The name for this graph. Used for labelling generated `digraph`.
 796         name: &'static str,
 797
 798         /// Each node is an index into `node_labels`; these labels are
 799         /// used as the label text for each node. (The node *names*,
 800         /// which are unique identifiers, are derived from their index
 801         /// in this array.)
 802         ///
 803         /// If a node maps to None here, then just use its name as its
 804         /// text.
 805         node_labels: Vec<Option<&'static str>>,
 806
 807         node_styles: Vec<Style>,
 808
 809         /// Each edge relates a from-index to a to-index along with a
 810         /// label; `edges` collects them.
 811         edges: Vec<Edge>,
 812     }
 813
 814     // A simple wrapper around LabelledGraph that forces the labels to
 815     // be emitted as EscStr.
 816     struct LabelledGraphWithEscStrs {
 817         graph: LabelledGraph,
 818     }
 819
 820     enum NodeLabels<L> {
 821         AllNodesLabelled(Vec<L>),
 822         UnlabelledNodes(usize),
 823         SomeNodesLabelled(Vec<Option<L>>),
 824     }
 825
 826     type Trivial = NodeLabels<&'static str>;
 827
 828     impl NodeLabels<&'static str> {
 829         fn to_opt_strs(self) -> Vec<Option<&'static str>> {
 830             match self {
 831                 UnlabelledNodes(len) => vec![None; len],
 832                 AllNodesLabelled(lbls) => lbls.into_iter().map(|l| Some(l)).collect(),
 833                 SomeNodesLabelled(lbls) => lbls.into_iter().collect(),
 834             }
 835         }
 836
 837         fn len(&self) -> usize {
 838             match self {
 839                 &UnlabelledNodes(len) => len,
 840                 &AllNodesLabelled(ref lbls) => lbls.len(),
 841                 &SomeNodesLabelled(ref lbls) => lbls.len(),
 842             }
 843         }
 844     }
 845
 846     impl LabelledGraph {
 847         fn new(name: &'static str,
 848                node_labels: Trivial,
 849                edges: Vec<Edge>,
 850                node_styles: Option<Vec<Style>>)
 851                -> LabelledGraph {
 852             let count = node_labels.len();
 853             LabelledGraph {
 854                 name: name,
 855                 node_labels: node_labels.to_opt_strs(),
 856                 edges: edges,
 857                 node_styles: match node_styles {
 858                     Some(nodes) => nodes,
 859                     None => vec![Style::None; count],
 860                 },
 861             }
 862         }
 863     }
 864
 865     impl LabelledGraphWithEscStrs {
 866         fn new(name: &'static str,
 867                node_labels: Trivial,
 868                edges: Vec<Edge>)
 869                -> LabelledGraphWithEscStrs {
 870             LabelledGraphWithEscStrs { graph: LabelledGraph::new(name, node_labels, edges, None) }
 871         }
 872     }
 873
 874     fn id_name<'a>(n: &Node) -> Id<'a> {
 875         Id::new(format!("N{}", *n)).unwrap()
 876     }
 877
 878     impl<'a> Labeller<'a> for LabelledGraph {
 879         type Node = Node;
 880         type Edge = &'a Edge;
 881         fn graph_id(&'a self) -> Id<'a> {
 882             Id::new(&self.name[..]).unwrap()
 883         }
 884         fn node_id(&'a self, n: &Node) -> Id<'a> {
 885             id_name(n)
 886         }
 887         fn node_label(&'a self, n: &Node) -> LabelText<'a> {
 888             match self.node_labels[*n] {
 889                 Some(ref l) => LabelStr(l.into_cow()),
 890                 None => LabelStr(id_name(n).name()),
 891             }
 892         }
 893         fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
 894             LabelStr(e.label.into_cow())
 895         }
 896         fn node_style(&'a self, n: &Node) -> Style {
 897             self.node_styles[*n]
 898         }
 899         fn edge_style(&'a self, e: &&'a Edge) -> Style {
 900             e.style
 901         }
 902     }
 903
 904     impl<'a> Labeller<'a> for LabelledGraphWithEscStrs {
 905         type Node = Node;
 906         type Edge = &'a Edge;
 907         fn graph_id(&'a self) -> Id<'a> {
 908             self.graph.graph_id()
 909         }
 910         fn node_id(&'a self, n: &Node) -> Id<'a> {
 911             self.graph.node_id(n)
 912         }
 913         fn node_label(&'a self, n: &Node) -> LabelText<'a> {
 914             match self.graph.node_label(n) {
 915                 LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
 916             }
 917         }
 918         fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
 919             match self.graph.edge_label(e) {
 920                 LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
 921             }
 922         }
 923     }
 924
 925     impl<'a> GraphWalk<'a> for LabelledGraph {
 926         type Node = Node;
 927         type Edge = &'a Edge;
 928         fn nodes(&'a self) -> Nodes<'a, Node> {
 929             (0..self.node_labels.len()).collect()
 930         }
 931         fn edges(&'a self) -> Edges<'a, &'a Edge> {
 932             self.edges.iter().collect()
 933         }
 934         fn source(&'a self, edge: &&'a Edge) -> Node {
 935             edge.from
 936         }
 937         fn target(&'a self, edge: &&'a Edge) -> Node {
 938             edge.to
 939         }
 940     }
 941
 942     impl<'a> GraphWalk<'a> for LabelledGraphWithEscStrs {
 943         type Node = Node;
 944         type Edge = &'a Edge;
 945         fn nodes(&'a self) -> Nodes<'a, Node> {
 946             self.graph.nodes()
 947         }
 948         fn edges(&'a self) -> Edges<'a, &'a Edge> {
 949             self.graph.edges()
 950         }
 951         fn source(&'a self, edge: &&'a Edge) -> Node {
 952             edge.from
 953         }
 954         fn target(&'a self, edge: &&'a Edge) -> Node {
 955             edge.to
 956         }
 957     }
 958
 959     fn test_input(g: LabelledGraph) -> io::Result<String> {
 960         let mut writer = Vec::new();
 961         render(&g, &mut writer).unwrap();
 962         let mut s = String::new();
 963         Read::read_to_string(&mut &*writer, &mut s)?;
 964         Ok(s)
 965     }
 966
 967     // All of the tests use raw-strings as the format for the expected outputs,
 968     // so that you can cut-and-paste the content into a .dot file yourself to
 969     // see what the graphviz visualizer would produce.
 970
 971     #[test]
 972     fn empty_graph() {
 973         let labels: Trivial = UnlabelledNodes(0);
 974         let r = test_input(LabelledGraph::new("empty_graph", labels, vec![], None));
 975         assert_eq!(r.unwrap(),
 976 r#"digraph empty_graph {
 977 }
 978 "#);
 979     }
 980
 981     #[test]
 982     fn single_node() {
 983         let labels: Trivial = UnlabelledNodes(1);
 984         let r = test_input(LabelledGraph::new("single_node", labels, vec![], None));
 985         assert_eq!(r.unwrap(),
 986 r#"digraph single_node {
 987     N0[label="N0"];
 988 }
 989 "#);
 990     }
 991
 992     #[test]
 993     fn single_node_with_style() {
 994         let labels: Trivial = UnlabelledNodes(1);
 995         let styles = Some(vec![Style::Dashed]);
 996         let r = test_input(LabelledGraph::new("single_node", labels, vec![], styles));
 997         assert_eq!(r.unwrap(),
 998 r#"digraph single_node {
 999     N0[label="N0"][style="dashed"];
1000 }
1001 "#);
1002     }
1003
1004     #[test]
1005     fn single_edge() {
1006         let labels: Trivial = UnlabelledNodes(2);
1007         let result = test_input(LabelledGraph::new("single_edge",
1008                                                    labels,
1009                                                    vec![edge(0, 1, "E", Style::None)],
1010                                                    None));
1011         assert_eq!(result.unwrap(),
1012 r#"digraph single_edge {
1013     N0[label="N0"];
1014     N1[label="N1"];
1015     N0 -> N1[label="E"];
1016 }
1017 "#);
1018     }
1019
1020     #[test]
1021     fn single_edge_with_style() {
1022         let labels: Trivial = UnlabelledNodes(2);
1023         let result = test_input(LabelledGraph::new("single_edge",
1024                                                    labels,
1025                                                    vec![edge(0, 1, "E", Style::Bold)],
1026                                                    None));
1027         assert_eq!(result.unwrap(),
1028 r#"digraph single_edge {
1029     N0[label="N0"];
1030     N1[label="N1"];
1031     N0 -> N1[label="E"][style="bold"];
1032 }
1033 "#);
1034     }
1035
1036     #[test]
1037     fn test_some_labelled() {
1038         let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]);
1039         let styles = Some(vec![Style::None, Style::Dotted]);
1040         let result = test_input(LabelledGraph::new("test_some_labelled",
1041                                                    labels,
1042                                                    vec![edge(0, 1, "A-1", Style::None)],
1043                                                    styles));
1044         assert_eq!(result.unwrap(),
1045 r#"digraph test_some_labelled {
1046     N0[label="A"];
1047     N1[label="N1"][style="dotted"];
1048     N0 -> N1[label="A-1"];
1049 }
1050 "#);
1051     }
1052
1053     #[test]
1054     fn single_cyclic_node() {
1055         let labels: Trivial = UnlabelledNodes(1);
1056         let r = test_input(LabelledGraph::new("single_cyclic_node",
1057                                               labels,
1058                                               vec![edge(0, 0, "E", Style::None)],
1059                                               None));
1060         assert_eq!(r.unwrap(),
1061 r#"digraph single_cyclic_node {
1062     N0[label="N0"];
1063     N0 -> N0[label="E"];
1064 }
1065 "#);
1066     }
1067
1068     #[test]
1069     fn hasse_diagram() {
1070         let labels = AllNodesLabelled(vec!["{x,y}", "{x}", "{y}", "{}"]);
1071         let r = test_input(LabelledGraph::new("hasse_diagram",
1072                                               labels,
1073                                               vec![edge(0, 1, "", Style::None),
1074                                                    edge(0, 2, "", Style::None),
1075                                                    edge(1, 3, "", Style::None),
1076                                                    edge(2, 3, "", Style::None)],
1077                                               None));
1078         assert_eq!(r.unwrap(),
1079 r#"digraph hasse_diagram {
1080     N0[label="{x,y}"];
1081     N1[label="{x}"];
1082     N2[label="{y}"];
1083     N3[label="{}"];
1084     N0 -> N1[label=""];
1085     N0 -> N2[label=""];
1086     N1 -> N3[label=""];
1087     N2 -> N3[label=""];
1088 }
1089 "#);
1090     }
1091
1092     #[test]
1093     fn left_aligned_text() {
1094         let labels = AllNodesLabelled(vec![
1095             "if test {\
1096            \\l    branch1\
1097            \\l} else {\
1098            \\l    branch2\
1099            \\l}\
1100            \\lafterward\
1101            \\l",
1102             "branch1",
1103             "branch2",
1104             "afterward"]);
1105
1106         let mut writer = Vec::new();
1107
1108         let g = LabelledGraphWithEscStrs::new("syntax_tree",
1109                                               labels,
1110                                               vec![edge(0, 1, "then", Style::None),
1111                                                    edge(0, 2, "else", Style::None),
1112                                                    edge(1, 3, ";", Style::None),
1113                                                    edge(2, 3, ";", Style::None)]);
1114
1115         render(&g, &mut writer).unwrap();
1116         let mut r = String::new();
1117         Read::read_to_string(&mut &*writer, &mut r).unwrap();
1118
1119         assert_eq!(r,
1120 r#"digraph syntax_tree {
1121     N0[label="if test {\l    branch1\l} else {\l    branch2\l}\lafterward\l"];
1122     N1[label="branch1"];
1123     N2[label="branch2"];
1124     N3[label="afterward"];
1125     N0 -> N1[label="then"];
1126     N0 -> N2[label="else"];
1127     N1 -> N3[label=";"];
1128     N2 -> N3[label=";"];
1129 }
1130 "#);
1131     }
1132
1133     #[test]
1134     fn simple_id_construction() {
1135         let id1 = Id::new("hello");
1136         match id1 {
1137             Ok(_) => {}
1138             Err(..) => panic!("'hello' is not a valid value for id anymore"),
1139         }
1140     }
1141
1142     #[test]
1143     fn badly_formatted_id() {
1144         let id2 = Id::new("Weird { struct : ure } !!!");
1145         match id2 {
1146             Ok(_) => panic!("graphviz id suddenly allows spaces, brackets and stuff"),
1147             Err(..) => {}
1148         }
1149     }
1150 }