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