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 //! use std::borrow::Cow;
51 //! use std::io::Write;
52 //!
53 //! type Nd = isize;
54 //! type Ed = (isize,isize);
55 //! struct Edges(Vec<Ed>);
56 //!
57 //! pub fn render_to<W: Write>(output: &mut W) {
58 //! let edges = Edges(vec!((0,1), (0,2), (1,3), (2,3), (3,4), (4,4)));
59 //! dot::render(&edges, output).unwrap()
60 //! }
61 //!
62 //! impl<'a> dot::Labeller<'a, Nd, Ed> for Edges {
63 //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example1").unwrap() }
64 //!
65 //! fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
66 //! dot::Id::new(format!("N{}", *n)).unwrap()
67 //! }
68 //! }
69 //!
70 //! impl<'a> dot::GraphWalk<'a, Nd, Ed> for Edges {
71 //! fn nodes(&self) -> dot::Nodes<'a,Nd> {
72 //! // (assumes that |N| \approxeq |E|)
73 //! let &Edges(ref v) = self;
74 //! let mut nodes = Vec::with_capacity(v.len());
75 //! for &(s,t) in v {
76 //! nodes.push(s); nodes.push(t);
77 //! }
78 //! nodes.sort();
79 //! nodes.dedup();
80 //! Cow::Owned(nodes)
81 //! }
82 //!
83 //! fn edges(&'a self) -> dot::Edges<'a,Ed> {
84 //! let &Edges(ref edges) = self;
85 //! Cow::Borrowed(&edges[..])
86 //! }
87 //!
88 //! fn source(&self, e: &Ed) -> Nd { e.0 }
89 //!
90 //! fn target(&self, e: &Ed) -> Nd { e.1 }
91 //! }
92 //!
93 //! # pub fn main() { render_to(&mut Vec::new()) }
94 //! ```
95 //!
96 //! ```no_run
97 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
98 //! pub fn main() {
99 //! use std::fs::File;
100 //! let mut f = File::create("example1.dot").unwrap();
101 //! render_to(&mut f)
102 //! }
103 //! ```
104 //!
105 //! Output from first example (in `example1.dot`):
106 //!
107 //! ```ignore
108 //! digraph example1 {
109 //! N0[label="N0"];
110 //! N1[label="N1"];
111 //! N2[label="N2"];
112 //! N3[label="N3"];
113 //! N4[label="N4"];
114 //! N0 -> N1[label=""];
115 //! N0 -> N2[label=""];
116 //! N1 -> N3[label=""];
117 //! N2 -> N3[label=""];
118 //! N3 -> N4[label=""];
119 //! N4 -> N4[label=""];
120 //! }
121 //! ```
122 //!
123 //! The second example illustrates using `node_label` and `edge_label` to
124 //! add labels to the nodes and edges in the rendered graph. The graph
125 //! here carries both `nodes` (the label text to use for rendering a
126 //! particular node), and `edges` (again a list of `(source,target)`
127 //! indices).
128 //!
129 //! This example also illustrates how to use a type (in this case the edge
130 //! type) that shares substructure with the graph: the edge type here is a
131 //! direct reference to the `(source,target)` pair stored in the graph's
132 //! internal vector (rather than passing around a copy of the pair
133 //! itself). Note that this implies that `fn edges(&'a self)` must
134 //! construct a fresh `Vec<&'a (usize,usize)>` from the `Vec<(usize,usize)>`
135 //! edges stored in `self`.
136 //!
137 //! Since both the set of nodes and the set of edges are always
138 //! constructed from scratch via iterators, we use the `collect()` method
139 //! from the `Iterator` trait to collect the nodes and edges into freshly
140 //! constructed growable `Vec` values (rather use the `into`
141 //! from the `IntoCow` trait as was used in the first example
142 //! above).
143 //!
144 //! The output from this example renders four nodes that make up the
145 //! Hasse-diagram for the subsets of the set `{x, y}`. Each edge is
146 //! labelled with the ⊆ character (specified using the HTML character
147 //! entity `&sube`).
148 //!
149 //! ```rust
150 //! use std::io::Write;
151 //!
152 //! type Nd = usize;
153 //! type Ed<'a> = &'a (usize, usize);
154 //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
155 //!
156 //! pub fn render_to<W: Write>(output: &mut W) {
157 //! let nodes = vec!("{x,y}","{x}","{y}","{}");
158 //! let edges = vec!((0,1), (0,2), (1,3), (2,3));
159 //! let graph = Graph { nodes: nodes, edges: edges };
160 //!
161 //! dot::render(&graph, output).unwrap()
162 //! }
163 //!
164 //! impl<'a> dot::Labeller<'a, Nd, Ed<'a>> for Graph {
165 //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example2").unwrap() }
166 //! fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
167 //! dot::Id::new(format!("N{}", n)).unwrap()
168 //! }
169 //! fn node_label<'b>(&'b self, n: &Nd) -> dot::LabelText<'b> {
170 //! dot::LabelText::LabelStr(self.nodes[*n].into())
171 //! }
172 //! fn edge_label<'b>(&'b self, _: &Ed) -> dot::LabelText<'b> {
173 //! dot::LabelText::LabelStr("⊆".into())
174 //! }
175 //! }
176 //!
177 //! impl<'a> dot::GraphWalk<'a, Nd, Ed<'a>> for Graph {
178 //! fn nodes(&self) -> dot::Nodes<'a,Nd> { (0..self.nodes.len()).collect() }
179 //! fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { self.edges.iter().collect() }
180 //! fn source(&self, e: &Ed) -> Nd { e.0 }
181 //! fn target(&self, e: &Ed) -> Nd { e.1 }
182 //! }
183 //!
184 //! # pub fn main() { render_to(&mut Vec::new()) }
185 //! ```
186 //!
187 //! ```no_run
188 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
189 //! pub fn main() {
190 //! use std::fs::File;
191 //! let mut f = File::create("example2.dot").unwrap();
192 //! render_to(&mut f)
193 //! }
194 //! ```
195 //!
196 //! The third example is similar to the second, except now each node and
197 //! edge now carries a reference to the string label for each node as well
198 //! as that node's index. (This is another illustration of how to share
199 //! structure with the graph itself, and why one might want to do so.)
200 //!
201 //! The output from this example is the same as the second example: the
202 //! Hasse-diagram for the subsets of the set `{x, y}`.
203 //!
204 //! ```rust
205 //! use std::io::Write;
206 //!
207 //! type Nd<'a> = (usize, &'a str);
208 //! type Ed<'a> = (Nd<'a>, Nd<'a>);
209 //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
210 //!
211 //! pub fn render_to<W: Write>(output: &mut W) {
212 //! let nodes = vec!("{x,y}","{x}","{y}","{}");
213 //! let edges = vec!((0,1), (0,2), (1,3), (2,3));
214 //! let graph = Graph { nodes: nodes, edges: edges };
215 //!
216 //! dot::render(&graph, output).unwrap()
217 //! }
218 //!
219 //! impl<'a> dot::Labeller<'a, Nd<'a>, Ed<'a>> for Graph {
220 //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example3").unwrap() }
221 //! fn node_id(&'a self, n: &Nd<'a>) -> dot::Id<'a> {
222 //! dot::Id::new(format!("N{}", n.0)).unwrap()
223 //! }
224 //! fn node_label<'b>(&'b self, n: &Nd<'b>) -> dot::LabelText<'b> {
225 //! let &(i, _) = n;
226 //! dot::LabelText::LabelStr(self.nodes[i].into())
227 //! }
228 //! fn edge_label<'b>(&'b self, _: &Ed<'b>) -> dot::LabelText<'b> {
229 //! dot::LabelText::LabelStr("⊆".into())
230 //! }
231 //! }
232 //!
233 //! impl<'a> dot::GraphWalk<'a, Nd<'a>, Ed<'a>> for Graph {
234 //! fn nodes(&'a self) -> dot::Nodes<'a,Nd<'a>> {
235 //! self.nodes.iter().map(|s| &s[..]).enumerate().collect()
236 //! }
237 //! fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> {
238 //! self.edges.iter()
239 //! .map(|&(i,j)|((i, &self.nodes[i][..]),
240 //! (j, &self.nodes[j][..])))
241 //! .collect()
242 //! }
243 //! fn source(&self, e: &Ed<'a>) -> Nd<'a> { e.0 }
244 //! fn target(&self, e: &Ed<'a>) -> Nd<'a> { e.1 }
245 //! }
246 //!
247 //! # pub fn main() { render_to(&mut Vec::new()) }
248 //! ```
249 //!
250 //! ```no_run
251 //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
252 //! pub fn main() {
253 //! use std::fs::File;
254 //! let mut f = File::create("example3.dot").unwrap();
255 //! render_to(&mut f)
256 //! }
257 //! ```
258 //!
259 //! # References
260 //!
261 //! * [Graphviz](http://www.graphviz.org/)
262 //!
263 //! * [DOT language](http://www.graphviz.org/doc/info/lang.html)
264
265 #![crate_name = "dot"]
266 #![crate_type = "rlib"]
267 #![crate_type = "dylib"]
268 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
269 html_favicon_url = "https://doc.rust-lang.org/favicon.ico",
270 html_root_url = "https://doc.rust-lang.org/nightly/")]
271
272 use self::LabelText::*;
273
274 use std::borrow::Cow;
275 use std::io::prelude::*;
276 use std::io;
277
278 /// The text for a graphviz label on a node or edge.
279 pub enum LabelText<'a> {
280 /// This kind of label preserves the text directly as is.
281 ///
282 /// Occurrences of backslashes (`\`) are escaped, and thus appear
283 /// as backslashes in the rendered label.
284 LabelStr(Cow<'a, str>),
285
286 /// This kind of label uses the graphviz label escString type:
287 /// http://www.graphviz.org/content/attrs#kescString
288 ///
289 /// Occurrences of backslashes (`\`) are not escaped; instead they
290 /// are interpreted as initiating an escString escape sequence.
291 ///
292 /// Escape sequences of particular interest: in addition to `\n`
293 /// to break a line (centering the line preceding the `\n`), there
294 /// are also the escape sequences `\l` which left-justifies the
295 /// preceding line and `\r` which right-justifies it.
296 EscStr(Cow<'a, str>),
297
298 /// This uses a graphviz [HTML string label][html]. The string is
299 /// printed exactly as given, but between `<` and `>`. **No
300 /// escaping is performed.**
301 ///
302 /// [html]: http://www.graphviz.org/content/node-shapes#html
303 HtmlStr(Cow<'a, str>),
304 }
305
306 /// The style for a node or edge.
307 /// See http://www.graphviz.org/doc/info/attrs.html#k:style for descriptions.
308 /// Note that some of these are not valid for edges.
309 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
310 pub enum Style {
311 None,
312 Invisible,
313 Solid,
314 Dashed,
315 Dotted,
316 Bold,
317 Rounded,
318 Diagonals,
319 Filled,
320 Striped,
321 Wedged,
322 }
323
324 impl Style {
as_slice(self) -> &'static str325 pub fn as_slice(self) -> &'static str {
326 match self {
327 Style::None => "",
328 Style::Invisible => "invis",
329 Style::Solid => "solid",
330 Style::Dashed => "dashed",
331 Style::Dotted => "dotted",
332 Style::Bold => "bold",
333 Style::Rounded => "rounded",
334 Style::Diagonals => "diagonals",
335 Style::Filled => "filled",
336 Style::Striped => "striped",
337 Style::Wedged => "wedged",
338 }
339 }
340 }
341
342 // There is a tension in the design of the labelling API.
343 //
344 // For example, I considered making a `Labeller<T>` trait that
345 // provides labels for `T`, and then making the graph type `G`
346 // implement `Labeller<Node>` and `Labeller<Edge>`. However, this is
347 // not possible without functional dependencies. (One could work
348 // around that, but I did not explore that avenue heavily.)
349 //
350 // Another approach that I actually used for a while was to make a
351 // `Label<Context>` trait that is implemented by the client-specific
352 // Node and Edge types (as well as an implementation on Graph itself
353 // for the overall name for the graph). The main disadvantage of this
354 // second approach (compared to having the `G` type parameter
355 // implement a Labelling service) that I have encountered is that it
356 // makes it impossible to use types outside of the current crate
357 // directly as Nodes/Edges; you need to wrap them in newtype'd
358 // structs. See e.g. the `No` and `Ed` structs in the examples. (In
359 // practice clients using a graph in some other crate would need to
360 // provide some sort of adapter shim over the graph anyway to
361 // interface with this library).
362 //
363 // Another approach would be to make a single `Labeller<N,E>` trait
364 // that provides three methods (graph_label, node_label, edge_label),
365 // and then make `G` implement `Labeller<N,E>`. At first this did not
366 // appeal to me, since I had thought I would need separate methods on
367 // each data variant for dot-internal identifiers versus user-visible
368 // labels. However, the identifier/label distinction only arises for
369 // nodes; graphs themselves only have identifiers, and edges only have
370 // labels.
371 //
372 // So in the end I decided to use the third approach described above.
373
374 /// `Id` is a Graphviz `ID`.
375 pub struct Id<'a> {
376 name: Cow<'a, str>,
377 }
378
379 impl<'a> Id<'a> {
380 /// Creates an `Id` named `name`.
381 ///
382 /// The caller must ensure that the input conforms to an
383 /// identifier format: it must be a non-empty string made up of
384 /// alphanumeric or underscore characters, not beginning with a
385 /// digit (i.e. the regular expression `[a-zA-Z_][a-zA-Z_0-9]*`).
386 ///
387 /// (Note: this format is a strict subset of the `ID` format
388 /// defined by the DOT language. This function may change in the
389 /// future to accept a broader subset, or the entirety, of DOT's
390 /// `ID` format.)
391 ///
392 /// Passing an invalid string (containing spaces, brackets,
393 /// quotes, ...) will return an empty `Err` value.
new<Name: Into<Cow<'a, str>>>(name: Name) -> Result<Id<'a>, ()>394 pub fn new<Name: Into<Cow<'a, str>>>(name: Name) -> Result<Id<'a>, ()> {
395 let name = name.into();
396 {
397 let mut chars = name.chars();
398 match chars.next() {
399 Some(c) if is_letter_or_underscore(c) => {}
400 _ => return Err(()),
401 }
402 if !chars.all(is_constituent) {
403 return Err(())
404 }
405 }
406 return Ok(Id{ name: name });
407
408 fn is_letter_or_underscore(c: char) -> bool {
409 in_range('a', c, 'z') || in_range('A', c, 'Z') || c == '_'
410 }
411 fn is_constituent(c: char) -> bool {
412 is_letter_or_underscore(c) || in_range('0', c, '9')
413 }
414 fn in_range(low: char, c: char, high: char) -> bool {
415 low as usize <= c as usize && c as usize <= high as usize
416 }
417 }
418
as_slice(&'a self) -> &'a str419 pub fn as_slice(&'a self) -> &'a str {
420 &*self.name
421 }
422
name(self) -> Cow<'a, str>423 pub fn name(self) -> Cow<'a, str> {
424 self.name
425 }
426 }
427
428 /// Each instance of a type that implements `Label<C>` maps to a
429 /// unique identifier with respect to `C`, which is used to identify
430 /// it in the generated .dot file. They can also provide more
431 /// elaborate (and non-unique) label text that is used in the graphviz
432 /// rendered output.
433
434 /// The graph instance is responsible for providing the DOT compatible
435 /// identifiers for the nodes and (optionally) rendered labels for the nodes and
436 /// edges, as well as an identifier for the graph itself.
437 pub trait Labeller<'a,N,E> {
438 /// Must return a DOT compatible identifier naming the graph.
graph_id(&'a self) -> Id<'a>439 fn graph_id(&'a self) -> Id<'a>;
440
441 /// Maps `n` to a unique identifier with respect to `self`. The
442 /// implementer is responsible for ensuring that the returned name
443 /// is a valid DOT identifier.
node_id(&'a self, n: &N) -> Id<'a>444 fn node_id(&'a self, n: &N) -> Id<'a>;
445
446 /// Maps `n` to one of the [graphviz `shape` names][1]. If `None`
447 /// is returned, no `shape` attribute is specified.
448 ///
449 /// [1]: http://www.graphviz.org/content/node-shapes
node_shape(&'a self, _node: &N) -> Option<LabelText<'a>>450 fn node_shape(&'a self, _node: &N) -> Option<LabelText<'a>> {
451 None
452 }
453
454 /// Maps `n` to a label that will be used in the rendered output.
455 /// The label need not be unique, and may be the empty string; the
456 /// default is just the output from `node_id`.
node_label(&'a self, n: &N) -> LabelText<'a>457 fn node_label(&'a self, n: &N) -> LabelText<'a> {
458 LabelStr(self.node_id(n).name())
459 }
460
461 /// Maps `e` to a label that will be used in the rendered output.
462 /// The label need not be unique, and may be the empty string; the
463 /// default is in fact the empty string.
edge_label(&'a self, e: &E) -> LabelText<'a>464 fn edge_label(&'a self, e: &E) -> LabelText<'a> {
465 let _ignored = e;
466 LabelStr("".into())
467 }
468
469 /// Maps `n` to a style that will be used in the rendered output.
node_style(&'a self, _n: &N) -> Style470 fn node_style(&'a self, _n: &N) -> Style {
471 Style::None
472 }
473
474 /// Maps `n` to one of the [graphviz `color` names][1]. If `None`
475 /// is returned, no `color` attribute is specified.
476 ///
477 /// [1]: https://graphviz.gitlab.io/_pages/doc/info/colors.html
node_color(&'a self, _node: &N) -> Option<LabelText<'a>>478 fn node_color(&'a self, _node: &N) -> Option<LabelText<'a>> {
479 None
480 }
481
482 /// Maps `e` to arrow style that will be used on the end of an edge.
483 /// Defaults to default arrow style.
edge_end_arrow(&'a self, _e: &E) -> Arrow484 fn edge_end_arrow(&'a self, _e: &E) -> Arrow {
485 Arrow::default()
486 }
487
488 /// Maps `e` to arrow style that will be used on the end of an edge.
489 /// Defaults to default arrow style.
edge_start_arrow(&'a self, _e: &E) -> Arrow490 fn edge_start_arrow(&'a self, _e: &E) -> Arrow {
491 Arrow::default()
492 }
493
494 /// Maps `e` to a style that will be used in the rendered output.
edge_style(&'a self, _e: &E) -> Style495 fn edge_style(&'a self, _e: &E) -> Style {
496 Style::None
497 }
498
499 /// Maps `e` to one of the [graphviz `color` names][1]. If `None`
500 /// is returned, no `color` attribute is specified.
501 ///
502 /// [1]: https://graphviz.gitlab.io/_pages/doc/info/colors.html
edge_color(&'a self, _e: &E) -> Option<LabelText<'a>>503 fn edge_color(&'a self, _e: &E) -> Option<LabelText<'a>> {
504 None
505 }
506
507 /// The kind of graph, defaults to `Kind::Digraph`.
508 #[inline]
kind(&self) -> Kind509 fn kind(&self) -> Kind {
510 Kind::Digraph
511 }
512 }
513
514 /// Escape tags in such a way that it is suitable for inclusion in a
515 /// Graphviz HTML label.
escape_html(s: &str) -> String516 pub fn escape_html(s: &str) -> String {
517 s
518 .replace("&", "&")
519 .replace("\"", """)
520 .replace("<", "<")
521 .replace(">", ">")
522 }
523
524 impl<'a> LabelText<'a> {
label<S:Into<Cow<'a, str>>>(s: S) -> LabelText<'a>525 pub fn label<S:Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
526 LabelStr(s.into())
527 }
528
escaped<S:Into<Cow<'a, str>>>(s: S) -> LabelText<'a>529 pub fn escaped<S:Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
530 EscStr(s.into())
531 }
532
html<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a>533 pub fn html<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
534 HtmlStr(s.into())
535 }
536
escape_char<F>(c: char, mut f: F) where F: FnMut(char)537 fn escape_char<F>(c: char, mut f: F)
538 where F: FnMut(char)
539 {
540 match c {
541 // not escaping \\, since Graphviz escString needs to
542 // interpret backslashes; see EscStr above.
543 '\\' => f(c),
544 _ => for c in c.escape_default() {
545 f(c)
546 },
547 }
548 }
escape_str(s: &str) -> String549 fn escape_str(s: &str) -> String {
550 let mut out = String::with_capacity(s.len());
551 for c in s.chars() {
552 LabelText::escape_char(c, |c| out.push(c));
553 }
554 out
555 }
556
escape_default(s: &str) -> String557 fn escape_default(s: &str) -> String {
558 s.chars().flat_map(|c| c.escape_default()).collect()
559 }
560
561 /// Renders text as string suitable for a label in a .dot file.
562 /// This includes quotes or suitable delimeters.
to_dot_string(&self) -> String563 pub fn to_dot_string(&self) -> String {
564 match self {
565 &LabelStr(ref s) => format!("\"{}\"", LabelText::escape_default(s)),
566 &EscStr(ref s) => format!("\"{}\"", LabelText::escape_str(&s[..])),
567 &HtmlStr(ref s) => format!("<{}>", s),
568 }
569 }
570
571 /// Decomposes content into string suitable for making EscStr that
572 /// yields same content as self. The result obeys the law
573 /// render(`lt`) == render(`EscStr(lt.pre_escaped_content())`) for
574 /// all `lt: LabelText`.
pre_escaped_content(self) -> Cow<'a, str>575 fn pre_escaped_content(self) -> Cow<'a, str> {
576 match self {
577 EscStr(s) => s,
578 LabelStr(s) => if s.contains('\\') {
579 LabelText::escape_default(&*s).into()
580 } else {
581 s
582 },
583 HtmlStr(s) => s,
584 }
585 }
586
587 /// Puts `prefix` on a line above this label, with a blank line separator.
prefix_line(self, prefix: LabelText) -> LabelText<'static>588 pub fn prefix_line(self, prefix: LabelText) -> LabelText<'static> {
589 prefix.suffix_line(self)
590 }
591
592 /// Puts `suffix` on a line below this label, with a blank line separator.
suffix_line(self, suffix: LabelText) -> LabelText<'static>593 pub fn suffix_line(self, suffix: LabelText) -> LabelText<'static> {
594 let mut prefix = self.pre_escaped_content().into_owned();
595 let suffix = suffix.pre_escaped_content();
596 prefix.push_str(r"\n\n");
597 prefix.push_str(&suffix[..]);
598 EscStr(prefix.into())
599 }
600 }
601
602
603 /// This structure holds all information that can describe an arrow connected to
604 /// either start or end of an edge.
605 #[derive(Clone, Hash, PartialEq, Eq)]
606 pub struct Arrow {
607 pub arrows: Vec<ArrowShape>,
608 }
609
610 use self::ArrowShape::*;
611
612 impl Arrow {
613 /// Return `true` if this is a default arrow.
is_default(&self) -> bool614 fn is_default(&self) -> bool {
615 self.arrows.is_empty()
616 }
617
618 /// Arrow constructor which returns a default arrow
default() -> Arrow619 pub fn default() -> Arrow {
620 Arrow {
621 arrows: vec![],
622 }
623 }
624
625 /// Arrow constructor which returns an empty arrow
none() -> Arrow626 pub fn none() -> Arrow {
627 Arrow {
628 arrows: vec![NoArrow],
629 }
630 }
631
632 /// Arrow constructor which returns a regular triangle arrow, without modifiers
normal() -> Arrow633 pub fn normal() -> Arrow {
634 Arrow {
635 arrows: vec![ArrowShape::normal()]
636 }
637 }
638
639 /// Arrow constructor which returns an arrow created by a given ArrowShape.
from_arrow(arrow: ArrowShape) -> Arrow640 pub fn from_arrow(arrow: ArrowShape) -> Arrow {
641 Arrow {
642 arrows: vec![arrow],
643 }
644 }
645
646 /// Function which converts given arrow into a renderable form.
to_dot_string(&self) -> String647 pub fn to_dot_string(&self) -> String {
648 let mut cow = String::new();
649 for arrow in &self.arrows {
650 cow.push_str(&arrow.to_dot_string());
651 };
652 cow
653 }
654 }
655
656
657 impl Into<Arrow> for [ArrowShape; 2] {
into(self) -> Arrow658 fn into(self) -> Arrow {
659 Arrow {
660 arrows: vec![self[0], self[1]],
661 }
662 }
663 }
664 impl Into<Arrow> for [ArrowShape; 3] {
into(self) -> Arrow665 fn into(self) -> Arrow {
666 Arrow {
667 arrows: vec![self[0], self[1], self[2]],
668 }
669 }
670 }
671 impl Into<Arrow> for [ArrowShape; 4] {
into(self) -> Arrow672 fn into(self) -> Arrow {
673 Arrow {
674 arrows: vec![self[0], self[1], self[2], self[3]],
675 }
676 }
677 }
678
679 /// Arrow modifier that determines if the shape is empty or filled.
680 #[derive(Clone, Copy, Hash, PartialEq, Eq)]
681 pub enum Fill {
682 Open,
683 Filled,
684 }
685
686 impl Fill {
as_slice(self) -> &'static str687 pub fn as_slice(self) -> &'static str {
688 match self {
689 Fill::Open => "o",
690 Fill::Filled => "",
691 }
692 }
693 }
694
695 /// Arrow modifier that determines if the shape is clipped.
696 /// For example `Side::Left` means only left side is visible.
697 #[derive(Clone, Copy, Hash, PartialEq, Eq)]
698 pub enum Side {
699 Left,
700 Right,
701 Both,
702 }
703
704 impl Side {
as_slice(self) -> &'static str705 pub fn as_slice(self) -> &'static str {
706 match self {
707 Side::Left => "l",
708 Side::Right => "r",
709 Side::Both => "",
710 }
711 }
712 }
713
714
715 /// This enumeration represents all possible arrow edge
716 /// as defined in [grapviz documentation](http://www.graphviz.org/content/arrow-shapes).
717 #[derive(Clone, Copy, Hash, PartialEq, Eq)]
718 pub enum ArrowShape {
719 /// No arrow will be displayed
720 NoArrow,
721 /// Arrow that ends in a triangle. Basically a normal arrow.
722 /// NOTE: there is error in official documentation, this supports both fill and side clipping
723 Normal(Fill, Side),
724 /// Arrow ending in a small square box
725 Box(Fill, Side),
726 /// Arrow ending in a three branching lines also called crow's foot
727 Crow(Side),
728 /// Arrow ending in a curve
729 Curve(Side),
730 /// Arrow ending in an inverted curve
731 ICurve(Fill, Side),
732 /// Arrow ending in an diamond shaped rectangular shape.
733 Diamond(Fill, Side),
734 /// Arrow ending in a circle.
735 Dot(Fill),
736 /// Arrow ending in an inverted triangle.
737 Inv(Fill, Side),
738 /// Arrow ending with a T shaped arrow.
739 Tee(Side),
740 /// Arrow ending with a V shaped arrow.
741 Vee(Side),
742 }
743 impl ArrowShape {
744 /// Constructor which returns no arrow.
none() -> ArrowShape745 pub fn none() -> ArrowShape {
746 ArrowShape::NoArrow
747 }
748
749 /// Constructor which returns normal arrow.
normal() -> ArrowShape750 pub fn normal() -> ArrowShape {
751 ArrowShape::Normal(Fill::Filled, Side::Both)
752 }
753
754 /// Constructor which returns a regular box arrow.
boxed() -> ArrowShape755 pub fn boxed() -> ArrowShape {
756 ArrowShape::Box(Fill::Filled, Side::Both)
757 }
758
759 /// Constructor which returns a regular crow arrow.
crow() -> ArrowShape760 pub fn crow() -> ArrowShape {
761 ArrowShape::Crow(Side::Both)
762 }
763
764 /// Constructor which returns a regular curve arrow.
curve() -> ArrowShape765 pub fn curve() -> ArrowShape {
766 ArrowShape::Curve(Side::Both)
767 }
768
769 /// Constructor which returns an inverted curve arrow.
icurve() -> ArrowShape770 pub fn icurve() -> ArrowShape {
771 ArrowShape::ICurve(Fill::Filled, Side::Both)
772 }
773
774 /// Constructor which returns a diamond arrow.
diamond() -> ArrowShape775 pub fn diamond() -> ArrowShape {
776 ArrowShape::Diamond(Fill::Filled, Side::Both)
777 }
778
779 /// Constructor which returns a circle shaped arrow.
dot() -> ArrowShape780 pub fn dot() -> ArrowShape {
781 ArrowShape::Diamond(Fill::Filled, Side::Both)
782 }
783
784 /// Constructor which returns an inverted triangle arrow.
inv() -> ArrowShape785 pub fn inv() -> ArrowShape {
786 ArrowShape::Inv(Fill::Filled, Side::Both)
787 }
788
789 /// Constructor which returns a T shaped arrow.
tee() -> ArrowShape790 pub fn tee() -> ArrowShape {
791 ArrowShape::Tee(Side::Both)
792 }
793
794 /// Constructor which returns a V shaped arrow.
vee() -> ArrowShape795 pub fn vee() -> ArrowShape {
796 ArrowShape::Vee(Side::Both)
797 }
798
799 /// Function which renders given ArrowShape into a String for displaying.
to_dot_string(&self) -> String800 pub fn to_dot_string(&self) -> String {
801 let mut res = String::new();
802 match *self {
803 Box(fill, side) | ICurve(fill, side)| Diamond(fill, side) |
804 Inv(fill, side) | Normal(fill, side)=> {
805 res.push_str(fill.as_slice());
806 match side {
807 Side::Left | Side::Right => res.push_str(side.as_slice()),
808 Side::Both => {},
809 };
810 },
811 Dot(fill) => res.push_str(fill.as_slice()),
812 Crow(side) | Curve(side) | Tee(side)
813 | Vee(side) => {
814 match side {
815 Side::Left | Side::Right => res.push_str(side.as_slice()),
816 Side::Both => {},
817 }
818 }
819 NoArrow => {},
820 };
821 match *self {
822 NoArrow => res.push_str("none"),
823 Normal(_, _) => res.push_str("normal"),
824 Box(_, _) => res.push_str("box"),
825 Crow(_) => res.push_str("crow"),
826 Curve(_) => res.push_str("curve"),
827 ICurve(_, _) => res.push_str("icurve"),
828 Diamond(_, _) => res.push_str("diamond"),
829 Dot(_) => res.push_str("dot"),
830 Inv(_, _) => res.push_str("inv"),
831 Tee(_) => res.push_str("tee"),
832 Vee(_) => res.push_str("vee"),
833 };
834 res
835 }
836 }
837
838 pub type Nodes<'a,N> = Cow<'a,[N]>;
839 pub type Edges<'a,E> = Cow<'a,[E]>;
840
841 /// Graph kind determines if `digraph` or `graph` is used as keyword
842 /// for the graph.
843 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
844 pub enum Kind {
845 Digraph,
846 Graph,
847 }
848
849 impl Kind {
850 /// The keyword to use to introduce the graph.
851 /// Determines which edge syntax must be used, and default style.
keyword(&self) -> &'static str852 fn keyword(&self) -> &'static str {
853 match *self {
854 Kind::Digraph => "digraph",
855 Kind::Graph => "graph"
856 }
857 }
858
859 /// The edgeop syntax to use for this graph kind.
edgeop(&self) -> &'static str860 fn edgeop(&self) -> &'static str {
861 match *self {
862 Kind::Digraph => "->",
863 Kind::Graph => "--",
864 }
865 }
866 }
867
868 // (The type parameters in GraphWalk should be associated items,
869 // when/if Rust supports such.)
870
871 /// GraphWalk is an abstraction over a graph = (nodes,edges)
872 /// made up of node handles `N` and edge handles `E`, where each `E`
873 /// can be mapped to its source and target nodes.
874 ///
875 /// The lifetime parameter `'a` is exposed in this trait (rather than
876 /// introduced as a generic parameter on each method declaration) so
877 /// that a client impl can choose `N` and `E` that have substructure
878 /// that is bound by the self lifetime `'a`.
879 ///
880 /// The `nodes` and `edges` method each return instantiations of
881 /// `Cow<[T]>` to leave implementers the freedom to create
882 /// entirely new vectors or to pass back slices into internally owned
883 /// vectors.
884 pub trait GraphWalk<'a, N: Clone, E: Clone> {
885 /// Returns all the nodes in this graph.
nodes(&'a self) -> Nodes<'a, N>886 fn nodes(&'a self) -> Nodes<'a, N>;
887 /// Returns all of the edges in this graph.
edges(&'a self) -> Edges<'a, E>888 fn edges(&'a self) -> Edges<'a, E>;
889 /// The source node for `edge`.
source(&'a self, edge: &E) -> N890 fn source(&'a self, edge: &E) -> N;
891 /// The target node for `edge`.
target(&'a self, edge: &E) -> N892 fn target(&'a self, edge: &E) -> N;
893 }
894
895 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
896 pub enum RenderOption {
897 NoEdgeLabels,
898 NoNodeLabels,
899 NoEdgeStyles,
900 NoEdgeColors,
901 NoNodeStyles,
902 NoNodeColors,
903 NoArrows,
904 }
905
906 /// Returns vec holding all the default render options.
default_options() -> Vec<RenderOption>907 pub fn default_options() -> Vec<RenderOption> {
908 vec![]
909 }
910
911 /// Renders graph `g` into the writer `w` in DOT syntax.
912 /// (Simple wrapper around `render_opts` that passes a default set of options.)
render<'a, N: Clone + 'a, E: Clone + 'a, G: Labeller<'a, N, E> + GraphWalk<'a, N, E>, W: Write> (g: &'a G, w: &mut W) -> io::Result<()>913 pub fn render<'a,
914 N: Clone + 'a,
915 E: Clone + 'a,
916 G: Labeller<'a, N, E> + GraphWalk<'a, N, E>,
917 W: Write>
918 (g: &'a G,
919 w: &mut W)
920 -> io::Result<()> {
921 render_opts(g, w, &[])
922 }
923
924 /// Renders graph `g` into the writer `w` in DOT syntax.
925 /// (Main entry point for the library.)
render_opts<'a, N: Clone + 'a, E: Clone + 'a, G: Labeller<'a, N, E> + GraphWalk<'a, N, E>, W: Write> (g: &'a G, w: &mut W, options: &[RenderOption]) -> io::Result<()>926 pub fn render_opts<'a,
927 N: Clone + 'a,
928 E: Clone + 'a,
929 G: Labeller<'a, N, E> + GraphWalk<'a, N, E>,
930 W: Write>
931 (g: &'a G,
932 w: &mut W,
933 options: &[RenderOption])
934 -> io::Result<()> {
935 fn writeln<W: Write>(w: &mut W, arg: &[&str]) -> io::Result<()> {
936 for &s in arg {
937 try!(w.write_all(s.as_bytes()));
938 }
939 write!(w, "\n")
940 }
941
942 fn indent<W: Write>(w: &mut W) -> io::Result<()> {
943 w.write_all(b" ")
944 }
945
946 try!(writeln(w, &[g.kind().keyword(), " ", g.graph_id().as_slice(), " {"]));
947 for n in g.nodes().iter() {
948 let colorstring;
949
950 try!(indent(w));
951 let id = g.node_id(n);
952
953 let escaped = &g.node_label(n).to_dot_string();
954 let shape;
955
956 let mut text = vec![id.as_slice()];
957
958 if !options.contains(&RenderOption::NoNodeLabels) {
959 text.push("[label=");
960 text.push(escaped);
961 text.push("]");
962 }
963
964 let style = g.node_style(n);
965 if !options.contains(&RenderOption::NoNodeStyles) && style != Style::None {
966 text.push("[style=\"");
967 text.push(style.as_slice());
968 text.push("\"]");
969 }
970
971 let color = g.node_color(n);
972 if !options.contains(&RenderOption::NoNodeColors) {
973 if let Some(c) = color {
974 colorstring = c.to_dot_string();
975 text.push("[color=");
976 text.push(&colorstring);
977 text.push("]");
978 }
979 }
980
981 if let Some(s) = g.node_shape(n) {
982 shape = s.to_dot_string();
983 text.push("[shape=");
984 text.push(&shape);
985 text.push("]");
986 }
987
988 text.push(";");
989 try!(writeln(w, &text));
990 }
991
992 for e in g.edges().iter() {
993 let colorstring;
994 let escaped_label = &g.edge_label(e).to_dot_string();
995 let start_arrow = g.edge_start_arrow(e);
996 let end_arrow = g.edge_end_arrow(e);
997 let start_arrow_s = start_arrow.to_dot_string();
998 let end_arrow_s = end_arrow.to_dot_string();
999
1000 try!(indent(w));
1001 let source = g.source(e);
1002 let target = g.target(e);
1003 let source_id = g.node_id(&source);
1004 let target_id = g.node_id(&target);
1005
1006 let mut text = vec![source_id.as_slice(), " ",
1007 g.kind().edgeop(), " ",
1008 target_id.as_slice()];
1009
1010 if !options.contains(&RenderOption::NoEdgeLabels) {
1011 text.push("[label=");
1012 text.push(escaped_label);
1013 text.push("]");
1014 }
1015
1016 let style = g.edge_style(e);
1017 if !options.contains(&RenderOption::NoEdgeStyles) && style != Style::None {
1018 text.push("[style=\"");
1019 text.push(style.as_slice());
1020 text.push("\"]");
1021 }
1022
1023 let color = g.edge_color(e);
1024 if !options.contains(&RenderOption::NoEdgeColors) {
1025 if let Some(c) = color {
1026 colorstring = c.to_dot_string();
1027 text.push("[color=");
1028 text.push(&colorstring);
1029 text.push("]");
1030 }
1031 }
1032
1033 if !options.contains(&RenderOption::NoArrows) &&
1034 (!start_arrow.is_default() || !end_arrow.is_default()) {
1035 text.push("[");
1036 if !end_arrow.is_default() {
1037 text.push("arrowhead=\"");
1038 text.push(&end_arrow_s);
1039 text.push("\"");
1040 }
1041 if !start_arrow.is_default() {
1042 text.push(" dir=\"both\" arrowtail=\"");
1043 text.push(&start_arrow_s);
1044 text.push("\"");
1045 }
1046
1047 text.push("]");
1048 }
1049
1050 text.push(";");
1051 try!(writeln(w, &text));
1052 }
1053
1054 writeln(w, &["}"])
1055 }
1056
1057 #[cfg(test)]
1058 mod tests {
1059 use self::NodeLabels::*;
1060 use super::{Id, Labeller, Nodes, Edges, GraphWalk, render, Style, Kind};
1061 use super::LabelText::{self, LabelStr, EscStr, HtmlStr};
1062 use super::{Arrow, ArrowShape, Side};
1063 use std::io;
1064 use std::io::prelude::*;
1065
1066 /// each node is an index in a vector in the graph.
1067 type Node = usize;
1068 struct Edge {
1069 from: usize,
1070 to: usize,
1071 label: &'static str,
1072 style: Style,
1073 start_arrow: Arrow,
1074 end_arrow: Arrow,
1075 color: Option<&'static str>,
1076 }
1077
edge(from: usize, to: usize, label: &'static str, style: Style, color: Option<&'static str>) -> Edge1078 fn edge(from: usize, to: usize, label: &'static str, style: Style, color: Option<&'static str>) -> Edge {
1079 Edge {
1080 from: from,
1081 to: to,
1082 label: label,
1083 style: style,
1084 start_arrow: Arrow::default(),
1085 end_arrow: Arrow::default(),
1086 color: color,
1087
1088 }
1089 }
1090
edge_with_arrows(from: usize, to: usize, label: &'static str, style:Style, start_arrow: Arrow, end_arrow: Arrow, color: Option<&'static str>) -> Edge1091 fn edge_with_arrows(from: usize, to: usize, label: &'static str, style:Style,
1092 start_arrow: Arrow, end_arrow: Arrow, color: Option<&'static str>) -> Edge {
1093 Edge {
1094 from: from,
1095 to: to,
1096 label: label,
1097 style: style,
1098 start_arrow: start_arrow,
1099 end_arrow: end_arrow,
1100 color: color,
1101 }
1102 }
1103
1104
1105 struct LabelledGraph {
1106 /// The name for this graph. Used for labelling generated `digraph`.
1107 name: &'static str,
1108
1109 /// Each node is an index into `node_labels`; these labels are
1110 /// used as the label text for each node. (The node *names*,
1111 /// which are unique identifiers, are derived from their index
1112 /// in this array.)
1113 ///
1114 /// If a node maps to None here, then just use its name as its
1115 /// text.
1116 node_labels: Vec<Option<&'static str>>,
1117
1118 node_styles: Vec<Style>,
1119
1120 /// Each edge relates a from-index to a to-index along with a
1121 /// label; `edges` collects them.
1122 edges: Vec<Edge>,
1123 }
1124
1125 // A simple wrapper around LabelledGraph that forces the labels to
1126 // be emitted as EscStr.
1127 struct LabelledGraphWithEscStrs {
1128 graph: LabelledGraph,
1129 }
1130
1131 enum NodeLabels<L> {
1132 AllNodesLabelled(Vec<L>),
1133 UnlabelledNodes(usize),
1134 SomeNodesLabelled(Vec<Option<L>>),
1135 }
1136
1137 type Trivial = NodeLabels<&'static str>;
1138
1139 impl NodeLabels<&'static str> {
into_opt_strs(self) -> Vec<Option<&'static str>>1140 fn into_opt_strs(self) -> Vec<Option<&'static str>> {
1141 match self {
1142 UnlabelledNodes(len) => vec![None; len],
1143 AllNodesLabelled(lbls) => lbls.into_iter().map(|l| Some(l)).collect(),
1144 SomeNodesLabelled(lbls) => lbls.into_iter().collect(),
1145 }
1146 }
1147
len(&self) -> usize1148 fn len(&self) -> usize {
1149 match self {
1150 &UnlabelledNodes(len) => len,
1151 &AllNodesLabelled(ref lbls) => lbls.len(),
1152 &SomeNodesLabelled(ref lbls) => lbls.len(),
1153 }
1154 }
1155 }
1156
1157 impl LabelledGraph {
new(name: &'static str, node_labels: Trivial, edges: Vec<Edge>, node_styles: Option<Vec<Style>>) -> LabelledGraph1158 fn new(name: &'static str,
1159 node_labels: Trivial,
1160 edges: Vec<Edge>,
1161 node_styles: Option<Vec<Style>>)
1162 -> LabelledGraph {
1163 let count = node_labels.len();
1164 LabelledGraph {
1165 name: name,
1166 node_labels: node_labels.into_opt_strs(),
1167 edges: edges,
1168 node_styles: match node_styles {
1169 Some(nodes) => nodes,
1170 None => vec![Style::None; count],
1171 },
1172 }
1173 }
1174 }
1175
1176 impl LabelledGraphWithEscStrs {
new(name: &'static str, node_labels: Trivial, edges: Vec<Edge>) -> LabelledGraphWithEscStrs1177 fn new(name: &'static str,
1178 node_labels: Trivial,
1179 edges: Vec<Edge>)
1180 -> LabelledGraphWithEscStrs {
1181 LabelledGraphWithEscStrs { graph: LabelledGraph::new(name, node_labels, edges, None) }
1182 }
1183 }
1184
id_name<'a>(n: &Node) -> Id<'a>1185 fn id_name<'a>(n: &Node) -> Id<'a> {
1186 Id::new(format!("N{}", *n)).unwrap()
1187 }
1188
1189 impl<'a> Labeller<'a, Node, &'a Edge> for LabelledGraph {
graph_id(&'a self) -> Id<'a>1190 fn graph_id(&'a self) -> Id<'a> {
1191 Id::new(&self.name[..]).unwrap()
1192 }
node_id(&'a self, n: &Node) -> Id<'a>1193 fn node_id(&'a self, n: &Node) -> Id<'a> {
1194 id_name(n)
1195 }
node_label(&'a self, n: &Node) -> LabelText<'a>1196 fn node_label(&'a self, n: &Node) -> LabelText<'a> {
1197 match self.node_labels[*n] {
1198 Some(ref l) => LabelStr((*l).into()),
1199 None => LabelStr(id_name(n).name()),
1200 }
1201 }
edge_label(&'a self, e: &&'a Edge) -> LabelText<'a>1202 fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
1203 LabelStr(e.label.into())
1204 }
node_style(&'a self, n: &Node) -> Style1205 fn node_style(&'a self, n: &Node) -> Style {
1206 self.node_styles[*n]
1207 }
edge_style(&'a self, e: &&'a Edge) -> Style1208 fn edge_style(&'a self, e: &&'a Edge) -> Style {
1209 e.style
1210 }
edge_color(&'a self, e: &&'a Edge) -> Option<LabelText<'a>>1211 fn edge_color(&'a self, e: &&'a Edge) -> Option<LabelText<'a>>
1212 {
1213 match e.color {
1214 Some(l) => {
1215 Some(LabelStr((*l).into()))
1216 },
1217 None => None,
1218 }
1219 }
edge_end_arrow(&'a self, e: &&'a Edge) -> Arrow1220 fn edge_end_arrow(&'a self, e: &&'a Edge) -> Arrow {
1221 e.end_arrow.clone()
1222 }
1223
edge_start_arrow(&'a self, e: &&'a Edge) -> Arrow1224 fn edge_start_arrow(&'a self, e: &&'a Edge) -> Arrow {
1225 e.start_arrow.clone()
1226 }
1227 }
1228
1229 impl<'a> Labeller<'a, Node, &'a Edge> for LabelledGraphWithEscStrs {
graph_id(&'a self) -> Id<'a>1230 fn graph_id(&'a self) -> Id<'a> {
1231 self.graph.graph_id()
1232 }
node_id(&'a self, n: &Node) -> Id<'a>1233 fn node_id(&'a self, n: &Node) -> Id<'a> {
1234 self.graph.node_id(n)
1235 }
node_label(&'a self, n: &Node) -> LabelText<'a>1236 fn node_label(&'a self, n: &Node) -> LabelText<'a> {
1237 match self.graph.node_label(n) {
1238 LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
1239 }
1240 }
node_color(&'a self, n: &Node) -> Option<LabelText<'a>>1241 fn node_color(&'a self, n: &Node) -> Option<LabelText<'a>> {
1242 match self.graph.node_color(n) {
1243 Some(LabelStr(s)) | Some(EscStr(s)) | Some(HtmlStr(s)) => Some(EscStr(s)),
1244 None => None,
1245 }
1246 }
edge_label(&'a self, e: &&'a Edge) -> LabelText<'a>1247 fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
1248 match self.graph.edge_label(e) {
1249 LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
1250 }
1251 }
edge_color(&'a self, e: &&'a Edge) -> Option<LabelText<'a>>1252 fn edge_color(&'a self, e: &&'a Edge) -> Option<LabelText<'a>> {
1253 match self.graph.edge_color(e) {
1254 Some(LabelStr(s)) | Some(EscStr(s)) | Some(HtmlStr(s)) => Some(EscStr(s)),
1255 None => None,
1256 }
1257 }
1258 }
1259
1260 impl<'a> GraphWalk<'a, Node, &'a Edge> for LabelledGraph {
nodes(&'a self) -> Nodes<'a, Node>1261 fn nodes(&'a self) -> Nodes<'a, Node> {
1262 (0..self.node_labels.len()).collect()
1263 }
edges(&'a self) -> Edges<'a, &'a Edge>1264 fn edges(&'a self) -> Edges<'a, &'a Edge> {
1265 self.edges.iter().collect()
1266 }
source(&'a self, edge: &&'a Edge) -> Node1267 fn source(&'a self, edge: &&'a Edge) -> Node {
1268 edge.from
1269 }
target(&'a self, edge: &&'a Edge) -> Node1270 fn target(&'a self, edge: &&'a Edge) -> Node {
1271 edge.to
1272 }
1273 }
1274
1275 impl<'a> GraphWalk<'a, Node, &'a Edge> for LabelledGraphWithEscStrs {
nodes(&'a self) -> Nodes<'a, Node>1276 fn nodes(&'a self) -> Nodes<'a, Node> {
1277 self.graph.nodes()
1278 }
edges(&'a self) -> Edges<'a, &'a Edge>1279 fn edges(&'a self) -> Edges<'a, &'a Edge> {
1280 self.graph.edges()
1281 }
source(&'a self, edge: &&'a Edge) -> Node1282 fn source(&'a self, edge: &&'a Edge) -> Node {
1283 edge.from
1284 }
target(&'a self, edge: &&'a Edge) -> Node1285 fn target(&'a self, edge: &&'a Edge) -> Node {
1286 edge.to
1287 }
1288 }
1289
test_input(g: LabelledGraph) -> io::Result<String>1290 fn test_input(g: LabelledGraph) -> io::Result<String> {
1291 let mut writer = Vec::new();
1292 render(&g, &mut writer).unwrap();
1293 let mut s = String::new();
1294 try!(Read::read_to_string(&mut &*writer, &mut s));
1295 Ok(s)
1296 }
1297
1298 // All of the tests use raw-strings as the format for the expected outputs,
1299 // so that you can cut-and-paste the content into a .dot file yourself to
1300 // see what the graphviz visualizer would produce.
1301
1302 #[test]
empty_graph()1303 fn empty_graph() {
1304 let labels: Trivial = UnlabelledNodes(0);
1305 let r = test_input(LabelledGraph::new("empty_graph", labels, vec![], None));
1306 assert_eq!(r.unwrap(),
1307 r#"digraph empty_graph {
1308 }
1309 "#);
1310 }
1311
1312 #[test]
single_node()1313 fn single_node() {
1314 let labels: Trivial = UnlabelledNodes(1);
1315 let r = test_input(LabelledGraph::new("single_node", labels, vec![], None));
1316 assert_eq!(r.unwrap(),
1317 r#"digraph single_node {
1318 N0[label="N0"];
1319 }
1320 "#);
1321 }
1322
1323 #[test]
single_node_with_style()1324 fn single_node_with_style() {
1325 let labels: Trivial = UnlabelledNodes(1);
1326 let styles = Some(vec![Style::Dashed]);
1327 let r = test_input(LabelledGraph::new("single_node", labels, vec![], styles));
1328 assert_eq!(r.unwrap(),
1329 r#"digraph single_node {
1330 N0[label="N0"][style="dashed"];
1331 }
1332 "#);
1333 }
1334
1335 #[test]
single_edge()1336 fn single_edge() {
1337 let labels: Trivial = UnlabelledNodes(2);
1338 let result = test_input(LabelledGraph::new("single_edge",
1339 labels,
1340 vec![edge(0, 1, "E", Style::None, None)],
1341 None));
1342 assert_eq!(result.unwrap(),
1343 r#"digraph single_edge {
1344 N0[label="N0"];
1345 N1[label="N1"];
1346 N0 -> N1[label="E"];
1347 }
1348 "#);
1349 }
1350
1351 #[test]
single_edge_with_style()1352 fn single_edge_with_style() {
1353 let labels: Trivial = UnlabelledNodes(2);
1354 let result = test_input(LabelledGraph::new("single_edge",
1355 labels,
1356 vec![edge(0, 1, "E", Style::Bold, Some("red"))],
1357 None));
1358 assert_eq!(result.unwrap(),
1359 r#"digraph single_edge {
1360 N0[label="N0"];
1361 N1[label="N1"];
1362 N0 -> N1[label="E"][style="bold"][color="red"];
1363 }
1364 "#);
1365 }
1366
1367 #[test]
test_some_labelled()1368 fn test_some_labelled() {
1369 let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]);
1370 let styles = Some(vec![Style::None, Style::Dotted]);
1371 let result = test_input(LabelledGraph::new("test_some_labelled",
1372 labels,
1373 vec![edge(0, 1, "A-1", Style::None, None)],
1374 styles));
1375 assert_eq!(result.unwrap(),
1376 r#"digraph test_some_labelled {
1377 N0[label="A"];
1378 N1[label="N1"][style="dotted"];
1379 N0 -> N1[label="A-1"];
1380 }
1381 "#);
1382 }
1383
1384 #[test]
single_cyclic_node()1385 fn single_cyclic_node() {
1386 let labels: Trivial = UnlabelledNodes(1);
1387 let r = test_input(LabelledGraph::new("single_cyclic_node",
1388 labels,
1389 vec![edge(0, 0, "E", Style::None, None)],
1390 None));
1391 assert_eq!(r.unwrap(),
1392 r#"digraph single_cyclic_node {
1393 N0[label="N0"];
1394 N0 -> N0[label="E"];
1395 }
1396 "#);
1397 }
1398
1399 #[test]
hasse_diagram()1400 fn hasse_diagram() {
1401 let labels = AllNodesLabelled(vec!("{x,y}", "{x}", "{y}", "{}"));
1402 let r = test_input(LabelledGraph::new("hasse_diagram",
1403 labels,
1404 vec![edge(0, 1, "", Style::None, Some("green")),
1405 edge(0, 2, "", Style::None, Some("blue")),
1406 edge(1, 3, "", Style::None, Some("red")),
1407 edge(2, 3, "", Style::None, Some("black"))],
1408 None));
1409 assert_eq!(r.unwrap(),
1410 r#"digraph hasse_diagram {
1411 N0[label="{x,y}"];
1412 N1[label="{x}"];
1413 N2[label="{y}"];
1414 N3[label="{}"];
1415 N0 -> N1[label=""][color="green"];
1416 N0 -> N2[label=""][color="blue"];
1417 N1 -> N3[label=""][color="red"];
1418 N2 -> N3[label=""][color="black"];
1419 }
1420 "#);
1421 }
1422
1423 #[test]
left_aligned_text()1424 fn left_aligned_text() {
1425 let labels = AllNodesLabelled(vec!(
1426 "if test {\
1427 \\l branch1\
1428 \\l} else {\
1429 \\l branch2\
1430 \\l}\
1431 \\lafterward\
1432 \\l",
1433 "branch1",
1434 "branch2",
1435 "afterward"));
1436
1437 let mut writer = Vec::new();
1438
1439 let g = LabelledGraphWithEscStrs::new("syntax_tree",
1440 labels,
1441 vec![edge(0, 1, "then", Style::None, None),
1442 edge(0, 2, "else", Style::None, None),
1443 edge(1, 3, ";", Style::None, None),
1444 edge(2, 3, ";", Style::None, None)]);
1445
1446 render(&g, &mut writer).unwrap();
1447 let mut r = String::new();
1448 Read::read_to_string(&mut &*writer, &mut r).unwrap();
1449
1450 assert_eq!(r,
1451 r#"digraph syntax_tree {
1452 N0[label="if test {\l branch1\l} else {\l branch2\l}\lafterward\l"];
1453 N1[label="branch1"];
1454 N2[label="branch2"];
1455 N3[label="afterward"];
1456 N0 -> N1[label="then"];
1457 N0 -> N2[label="else"];
1458 N1 -> N3[label=";"];
1459 N2 -> N3[label=";"];
1460 }
1461 "#);
1462 }
1463
1464 #[test]
simple_id_construction()1465 fn simple_id_construction() {
1466 let id1 = Id::new("hello");
1467 match id1 {
1468 Ok(_) => {}
1469 Err(..) => panic!("'hello' is not a valid value for id anymore"),
1470 }
1471 }
1472
1473 #[test]
test_some_arrow()1474 fn test_some_arrow() {
1475 let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]);
1476 let styles = Some(vec![Style::None, Style::Dotted]);
1477 let start = Arrow::default();
1478 let end = Arrow::from_arrow(ArrowShape::crow());
1479 let result = test_input(LabelledGraph::new("test_some_labelled",
1480 labels,
1481 vec![edge_with_arrows(0, 1, "A-1", Style::None, start, end, None)],
1482 styles));
1483 assert_eq!(result.unwrap(),
1484 r#"digraph test_some_labelled {
1485 N0[label="A"];
1486 N1[label="N1"][style="dotted"];
1487 N0 -> N1[label="A-1"][arrowhead="crow"];
1488 }
1489 "#);
1490 }
1491
1492 #[test]
test_some_arrows()1493 fn test_some_arrows() {
1494 let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]);
1495 let styles = Some(vec![Style::None, Style::Dotted]);
1496 let start = Arrow::from_arrow(ArrowShape::tee());
1497 let end = Arrow::from_arrow(ArrowShape::Crow(Side::Left));
1498 let result = test_input(LabelledGraph::new("test_some_labelled",
1499 labels,
1500 vec![edge_with_arrows(0, 1, "A-1", Style::None, start, end, None)],
1501 styles));
1502 assert_eq!(result.unwrap(),
1503 r#"digraph test_some_labelled {
1504 N0[label="A"];
1505 N1[label="N1"][style="dotted"];
1506 N0 -> N1[label="A-1"][arrowhead="lcrow" dir="both" arrowtail="tee"];
1507 }
1508 "#);
1509 }
1510
1511 #[test]
invisible()1512 fn invisible() {
1513 let labels: Trivial = UnlabelledNodes(1);
1514 let r = test_input(LabelledGraph::new("single_cyclic_node",
1515 labels,
1516 vec![edge(0, 0, "E", Style::Invisible, None)],
1517 Some(vec![Style::Invisible])));
1518 assert_eq!(r.unwrap(),
1519 r#"digraph single_cyclic_node {
1520 N0[label="N0"][style="invis"];
1521 N0 -> N0[label="E"][style="invis"];
1522 }
1523 "#);
1524 }
1525
1526 #[test]
badly_formatted_id()1527 fn badly_formatted_id() {
1528 let id2 = Id::new("Weird { struct : ure } !!!");
1529 match id2 {
1530 Ok(_) => panic!("graphviz id suddenly allows spaces, brackets and stuff"),
1531 Err(..) => {}
1532 }
1533 }
1534
1535 type SimpleEdge = (Node, Node);
1536
1537 struct DefaultStyleGraph {
1538 /// The name for this graph. Used for labelling generated graph
1539 name: &'static str,
1540 nodes: usize,
1541 edges: Vec<SimpleEdge>,
1542 kind: Kind,
1543 }
1544
1545 impl DefaultStyleGraph {
new(name: &'static str, nodes: usize, edges: Vec<SimpleEdge>, kind: Kind) -> DefaultStyleGraph1546 fn new(name: &'static str,
1547 nodes: usize,
1548 edges: Vec<SimpleEdge>,
1549 kind: Kind)
1550 -> DefaultStyleGraph {
1551 assert!(!name.is_empty());
1552 DefaultStyleGraph {
1553 name: name,
1554 nodes: nodes,
1555 edges: edges,
1556 kind: kind,
1557 }
1558 }
1559 }
1560
1561 impl<'a> Labeller<'a, Node, &'a SimpleEdge> for DefaultStyleGraph {
graph_id(&'a self) -> Id<'a>1562 fn graph_id(&'a self) -> Id<'a> {
1563 Id::new(&self.name[..]).unwrap()
1564 }
node_id(&'a self, n: &Node) -> Id<'a>1565 fn node_id(&'a self, n: &Node) -> Id<'a> {
1566 id_name(n)
1567 }
kind(&self) -> Kind1568 fn kind(&self) -> Kind {
1569 self.kind
1570 }
1571 }
1572
1573 impl<'a> GraphWalk<'a, Node, &'a SimpleEdge> for DefaultStyleGraph {
nodes(&'a self) -> Nodes<'a, Node>1574 fn nodes(&'a self) -> Nodes<'a, Node> {
1575 (0..self.nodes).collect()
1576 }
edges(&'a self) -> Edges<'a, &'a SimpleEdge>1577 fn edges(&'a self) -> Edges<'a, &'a SimpleEdge> {
1578 self.edges.iter().collect()
1579 }
source(&'a self, edge: &&'a SimpleEdge) -> Node1580 fn source(&'a self, edge: &&'a SimpleEdge) -> Node {
1581 edge.0
1582 }
target(&'a self, edge: &&'a SimpleEdge) -> Node1583 fn target(&'a self, edge: &&'a SimpleEdge) -> Node {
1584 edge.1
1585 }
1586 }
1587
test_input_default(g: DefaultStyleGraph) -> io::Result<String>1588 fn test_input_default(g: DefaultStyleGraph) -> io::Result<String> {
1589 let mut writer = Vec::new();
1590 render(&g, &mut writer).unwrap();
1591 let mut s = String::new();
1592 try!(Read::read_to_string(&mut &*writer, &mut s));
1593 Ok(s)
1594 }
1595
1596 #[test]
default_style_graph()1597 fn default_style_graph() {
1598 let r = test_input_default(
1599 DefaultStyleGraph::new("g", 4,
1600 vec![(0, 1), (0, 2), (1, 3), (2, 3)],
1601 Kind::Graph));
1602 assert_eq!(r.unwrap(),
1603 r#"graph g {
1604 N0[label="N0"];
1605 N1[label="N1"];
1606 N2[label="N2"];
1607 N3[label="N3"];
1608 N0 -- N1[label=""];
1609 N0 -- N2[label=""];
1610 N1 -- N3[label=""];
1611 N2 -- N3[label=""];
1612 }
1613 "#);
1614 }
1615
1616 #[test]
default_style_digraph()1617 fn default_style_digraph() {
1618 let r = test_input_default(
1619 DefaultStyleGraph::new("di", 4,
1620 vec![(0, 1), (0, 2), (1, 3), (2, 3)],
1621 Kind::Digraph));
1622 assert_eq!(r.unwrap(),
1623 r#"digraph di {
1624 N0[label="N0"];
1625 N1[label="N1"];
1626 N2[label="N2"];
1627 N3[label="N3"];
1628 N0 -> N1[label=""];
1629 N0 -> N2[label=""];
1630 N1 -> N3[label=""];
1631 N2 -> N3[label=""];
1632 }
1633 "#);
1634 }
1635 }
1636