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