]>
Commit | Line | Data |
---|---|---|
136023e0 | 1 | //! Generate files suitable for use with [Graphviz](https://www.graphviz.org/) |
1a4d82fc | 2 | //! |
0731742a | 3 | //! The `render` function generates output (e.g., an `output.dot` file) for |
136023e0 | 4 | //! use with [Graphviz](https://www.graphviz.org/) by walking a labeled |
1a4d82fc JJ |
5 | //! graph. (Graphviz can then automatically lay out the nodes and edges |
6 | //! of the graph, and also optionally render the graph as an image or | |
04454e1e | 7 | //! other [output formats](https://www.graphviz.org/docs/outputs), such as SVG.) |
1a4d82fc JJ |
8 | //! |
9 | //! Rather than impose some particular graph data structure on clients, | |
10 | //! this library exposes two traits that clients can implement on their | |
11 | //! own structs before handing them over to the rendering function. | |
12 | //! | |
13 | //! Note: This library does not yet provide access to the full | |
04454e1e FG |
14 | //! expressiveness of the [DOT language](https://www.graphviz.org/doc/info/lang.html). |
15 | //! For example, there are many [attributes](https://www.graphviz.org/doc/info/attrs.html) | |
16 | //! related to providing layout hints (e.g., left-to-right versus top-down, which | |
1a4d82fc JJ |
17 | //! algorithm to use, etc). The current intention of this library is to |
18 | //! emit a human-readable .dot file with very regular structure suitable | |
19 | //! for easy post-processing. | |
20 | //! | |
21 | //! # Examples | |
22 | //! | |
23 | //! The first example uses a very simple graph representation: a list of | |
24 | //! pairs of ints, representing the edges (the node set is implicit). | |
25 | //! Each node label is derived directly from the int representing the node, | |
26 | //! while the edge labels are all empty strings. | |
27 | //! | |
c34b1796 | 28 | //! This example also illustrates how to use `Cow<[T]>` to return |
1a4d82fc JJ |
29 | //! an owned vector or a borrowed slice as appropriate: we construct the |
30 | //! node vector from scratch, but borrow the edge list (rather than | |
31 | //! constructing a copy of all the edges from scratch). | |
32 | //! | |
33 | //! The output from this example renders five nodes, with the first four | |
34 | //! forming a diamond-shaped acyclic graph and then pointing to the fifth | |
35 | //! which is cyclic. | |
36 | //! | |
37 | //! ```rust | |
9cc50fc6 | 38 | //! #![feature(rustc_private)] |
c1a9b12d | 39 | //! |
c34b1796 | 40 | //! use std::io::Write; |
f035d41b | 41 | //! use rustc_graphviz as dot; |
1a4d82fc | 42 | //! |
c34b1796 AL |
43 | //! type Nd = isize; |
44 | //! type Ed = (isize,isize); | |
1a4d82fc JJ |
45 | //! struct Edges(Vec<Ed>); |
46 | //! | |
c34b1796 | 47 | //! pub fn render_to<W: Write>(output: &mut W) { |
c30ab7b3 | 48 | //! let edges = Edges(vec![(0,1), (0,2), (1,3), (2,3), (3,4), (4,4)]); |
1a4d82fc JJ |
49 | //! dot::render(&edges, output).unwrap() |
50 | //! } | |
51 | //! | |
54a0048b SL |
52 | //! impl<'a> dot::Labeller<'a> for Edges { |
53 | //! type Node = Nd; | |
54 | //! type Edge = Ed; | |
1a4d82fc JJ |
55 | //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example1").unwrap() } |
56 | //! | |
57 | //! fn node_id(&'a self, n: &Nd) -> dot::Id<'a> { | |
58 | //! dot::Id::new(format!("N{}", *n)).unwrap() | |
59 | //! } | |
60 | //! } | |
61 | //! | |
54a0048b SL |
62 | //! impl<'a> dot::GraphWalk<'a> for Edges { |
63 | //! type Node = Nd; | |
64 | //! type Edge = Ed; | |
1a4d82fc JJ |
65 | //! fn nodes(&self) -> dot::Nodes<'a,Nd> { |
66 | //! // (assumes that |N| \approxeq |E|) | |
67 | //! let &Edges(ref v) = self; | |
68 | //! let mut nodes = Vec::with_capacity(v.len()); | |
62682a34 | 69 | //! for &(s,t) in v { |
1a4d82fc JJ |
70 | //! nodes.push(s); nodes.push(t); |
71 | //! } | |
72 | //! nodes.sort(); | |
73 | //! nodes.dedup(); | |
0bf4aa26 | 74 | //! nodes.into() |
1a4d82fc JJ |
75 | //! } |
76 | //! | |
77 | //! fn edges(&'a self) -> dot::Edges<'a,Ed> { | |
78 | //! let &Edges(ref edges) = self; | |
0bf4aa26 | 79 | //! (&edges[..]).into() |
1a4d82fc JJ |
80 | //! } |
81 | //! | |
82 | //! fn source(&self, e: &Ed) -> Nd { let &(s,_) = e; s } | |
83 | //! | |
84 | //! fn target(&self, e: &Ed) -> Nd { let &(_,t) = e; t } | |
85 | //! } | |
86 | //! | |
87 | //! # pub fn main() { render_to(&mut Vec::new()) } | |
88 | //! ``` | |
89 | //! | |
90 | //! ```no_run | |
c34b1796 | 91 | //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() } |
1a4d82fc | 92 | //! pub fn main() { |
c34b1796 AL |
93 | //! use std::fs::File; |
94 | //! let mut f = File::create("example1.dot").unwrap(); | |
1a4d82fc JJ |
95 | //! render_to(&mut f) |
96 | //! } | |
97 | //! ``` | |
98 | //! | |
99 | //! Output from first example (in `example1.dot`): | |
100 | //! | |
041b39d2 | 101 | //! ```dot |
1a4d82fc JJ |
102 | //! digraph example1 { |
103 | //! N0[label="N0"]; | |
104 | //! N1[label="N1"]; | |
105 | //! N2[label="N2"]; | |
106 | //! N3[label="N3"]; | |
107 | //! N4[label="N4"]; | |
108 | //! N0 -> N1[label=""]; | |
109 | //! N0 -> N2[label=""]; | |
110 | //! N1 -> N3[label=""]; | |
111 | //! N2 -> N3[label=""]; | |
112 | //! N3 -> N4[label=""]; | |
113 | //! N4 -> N4[label=""]; | |
114 | //! } | |
115 | //! ``` | |
116 | //! | |
117 | //! The second example illustrates using `node_label` and `edge_label` to | |
118 | //! add labels to the nodes and edges in the rendered graph. The graph | |
119 | //! here carries both `nodes` (the label text to use for rendering a | |
120 | //! particular node), and `edges` (again a list of `(source,target)` | |
121 | //! indices). | |
122 | //! | |
123 | //! This example also illustrates how to use a type (in this case the edge | |
124 | //! type) that shares substructure with the graph: the edge type here is a | |
125 | //! direct reference to the `(source,target)` pair stored in the graph's | |
126 | //! internal vector (rather than passing around a copy of the pair | |
127 | //! itself). Note that this implies that `fn edges(&'a self)` must | |
c34b1796 | 128 | //! construct a fresh `Vec<&'a (usize,usize)>` from the `Vec<(usize,usize)>` |
1a4d82fc JJ |
129 | //! edges stored in `self`. |
130 | //! | |
131 | //! Since both the set of nodes and the set of edges are always | |
132 | //! constructed from scratch via iterators, we use the `collect()` method | |
133 | //! from the `Iterator` trait to collect the nodes and edges into freshly | |
0bf4aa26 XL |
134 | //! constructed growable `Vec` values (rather than using `Cow` as in the |
135 | //! first example above). | |
1a4d82fc JJ |
136 | //! |
137 | //! The output from this example renders four nodes that make up the | |
138 | //! Hasse-diagram for the subsets of the set `{x, y}`. Each edge is | |
3b2f2976 | 139 | //! labeled with the ⊆ character (specified using the HTML character |
1a4d82fc JJ |
140 | //! entity `&sube`). |
141 | //! | |
142 | //! ```rust | |
92a42be0 | 143 | //! #![feature(rustc_private)] |
c1a9b12d | 144 | //! |
c34b1796 | 145 | //! use std::io::Write; |
f035d41b | 146 | //! use rustc_graphviz as dot; |
1a4d82fc | 147 | //! |
c34b1796 AL |
148 | //! type Nd = usize; |
149 | //! type Ed<'a> = &'a (usize, usize); | |
150 | //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> } | |
1a4d82fc | 151 | //! |
c34b1796 | 152 | //! pub fn render_to<W: Write>(output: &mut W) { |
c30ab7b3 SL |
153 | //! let nodes = vec!["{x,y}","{x}","{y}","{}"]; |
154 | //! let edges = vec![(0,1), (0,2), (1,3), (2,3)]; | |
1a4d82fc JJ |
155 | //! let graph = Graph { nodes: nodes, edges: edges }; |
156 | //! | |
157 | //! dot::render(&graph, output).unwrap() | |
158 | //! } | |
159 | //! | |
54a0048b SL |
160 | //! impl<'a> dot::Labeller<'a> for Graph { |
161 | //! type Node = Nd; | |
162 | //! type Edge = Ed<'a>; | |
1a4d82fc JJ |
163 | //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example2").unwrap() } |
164 | //! fn node_id(&'a self, n: &Nd) -> dot::Id<'a> { | |
165 | //! dot::Id::new(format!("N{}", n)).unwrap() | |
166 | //! } | |
167 | //! fn node_label<'b>(&'b self, n: &Nd) -> dot::LabelText<'b> { | |
92a42be0 | 168 | //! dot::LabelText::LabelStr(self.nodes[*n].into()) |
1a4d82fc JJ |
169 | //! } |
170 | //! fn edge_label<'b>(&'b self, _: &Ed) -> dot::LabelText<'b> { | |
92a42be0 | 171 | //! dot::LabelText::LabelStr("⊆".into()) |
1a4d82fc JJ |
172 | //! } |
173 | //! } | |
174 | //! | |
54a0048b SL |
175 | //! impl<'a> dot::GraphWalk<'a> for Graph { |
176 | //! type Node = Nd; | |
177 | //! type Edge = Ed<'a>; | |
85aaf69f | 178 | //! fn nodes(&self) -> dot::Nodes<'a,Nd> { (0..self.nodes.len()).collect() } |
1a4d82fc JJ |
179 | //! fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { self.edges.iter().collect() } |
180 | //! fn source(&self, e: &Ed) -> Nd { let & &(s,_) = e; s } | |
181 | //! fn target(&self, e: &Ed) -> Nd { let & &(_,t) = e; t } | |
182 | //! } | |
183 | //! | |
184 | //! # pub fn main() { render_to(&mut Vec::new()) } | |
185 | //! ``` | |
186 | //! | |
187 | //! ```no_run | |
c34b1796 | 188 | //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() } |
1a4d82fc | 189 | //! pub fn main() { |
c34b1796 AL |
190 | //! use std::fs::File; |
191 | //! let mut f = File::create("example2.dot").unwrap(); | |
1a4d82fc JJ |
192 | //! render_to(&mut f) |
193 | //! } | |
194 | //! ``` | |
195 | //! | |
196 | //! The third example is similar to the second, except now each node and | |
197 | //! edge now carries a reference to the string label for each node as well | |
198 | //! as that node's index. (This is another illustration of how to share | |
199 | //! structure with the graph itself, and why one might want to do so.) | |
200 | //! | |
201 | //! The output from this example is the same as the second example: the | |
202 | //! Hasse-diagram for the subsets of the set `{x, y}`. | |
203 | //! | |
204 | //! ```rust | |
92a42be0 | 205 | //! #![feature(rustc_private)] |
c1a9b12d | 206 | //! |
c34b1796 | 207 | //! use std::io::Write; |
f035d41b | 208 | //! use rustc_graphviz as dot; |
1a4d82fc | 209 | //! |
c34b1796 | 210 | //! type Nd<'a> = (usize, &'a str); |
1a4d82fc | 211 | //! type Ed<'a> = (Nd<'a>, Nd<'a>); |
c34b1796 | 212 | //! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> } |
1a4d82fc | 213 | //! |
c34b1796 | 214 | //! pub fn render_to<W: Write>(output: &mut W) { |
c30ab7b3 SL |
215 | //! let nodes = vec!["{x,y}","{x}","{y}","{}"]; |
216 | //! let edges = vec![(0,1), (0,2), (1,3), (2,3)]; | |
1a4d82fc JJ |
217 | //! let graph = Graph { nodes: nodes, edges: edges }; |
218 | //! | |
219 | //! dot::render(&graph, output).unwrap() | |
220 | //! } | |
221 | //! | |
54a0048b SL |
222 | //! impl<'a> dot::Labeller<'a> for Graph { |
223 | //! type Node = Nd<'a>; | |
224 | //! type Edge = Ed<'a>; | |
1a4d82fc JJ |
225 | //! fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example3").unwrap() } |
226 | //! fn node_id(&'a self, n: &Nd<'a>) -> dot::Id<'a> { | |
227 | //! dot::Id::new(format!("N{}", n.0)).unwrap() | |
228 | //! } | |
229 | //! fn node_label<'b>(&'b self, n: &Nd<'b>) -> dot::LabelText<'b> { | |
230 | //! let &(i, _) = n; | |
92a42be0 | 231 | //! dot::LabelText::LabelStr(self.nodes[i].into()) |
1a4d82fc JJ |
232 | //! } |
233 | //! fn edge_label<'b>(&'b self, _: &Ed<'b>) -> dot::LabelText<'b> { | |
92a42be0 | 234 | //! dot::LabelText::LabelStr("⊆".into()) |
1a4d82fc JJ |
235 | //! } |
236 | //! } | |
237 | //! | |
54a0048b SL |
238 | //! impl<'a> dot::GraphWalk<'a> for Graph { |
239 | //! type Node = Nd<'a>; | |
240 | //! type Edge = Ed<'a>; | |
1a4d82fc | 241 | //! fn nodes(&'a self) -> dot::Nodes<'a,Nd<'a>> { |
c34b1796 | 242 | //! self.nodes.iter().map(|s| &s[..]).enumerate().collect() |
1a4d82fc JJ |
243 | //! } |
244 | //! fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { | |
245 | //! self.edges.iter() | |
c34b1796 AL |
246 | //! .map(|&(i,j)|((i, &self.nodes[i][..]), |
247 | //! (j, &self.nodes[j][..]))) | |
1a4d82fc JJ |
248 | //! .collect() |
249 | //! } | |
250 | //! fn source(&self, e: &Ed<'a>) -> Nd<'a> { let &(s,_) = e; s } | |
251 | //! fn target(&self, e: &Ed<'a>) -> Nd<'a> { let &(_,t) = e; t } | |
252 | //! } | |
253 | //! | |
254 | //! # pub fn main() { render_to(&mut Vec::new()) } | |
255 | //! ``` | |
256 | //! | |
257 | //! ```no_run | |
c34b1796 | 258 | //! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() } |
1a4d82fc | 259 | //! pub fn main() { |
c34b1796 AL |
260 | //! use std::fs::File; |
261 | //! let mut f = File::create("example3.dot").unwrap(); | |
1a4d82fc JJ |
262 | //! render_to(&mut f) |
263 | //! } | |
264 | //! ``` | |
265 | //! | |
266 | //! # References | |
267 | //! | |
136023e0 | 268 | //! * [Graphviz](https://www.graphviz.org/) |
1a4d82fc | 269 | //! |
136023e0 | 270 | //! * [DOT language](https://www.graphviz.org/doc/info/lang.html) |
1a4d82fc | 271 | |
dfeec247 | 272 | #![doc( |
1b1a35ee | 273 | html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/", |
dfeec247 XL |
274 | test(attr(allow(unused_variables), deny(warnings))) |
275 | )] | |
1a4d82fc | 276 | |
9fa01778 | 277 | use LabelText::*; |
1a4d82fc | 278 | |
0bf4aa26 | 279 | use std::borrow::Cow; |
c34b1796 | 280 | use std::io; |
dfeec247 | 281 | use std::io::prelude::*; |
1a4d82fc JJ |
282 | |
283 | /// The text for a graphviz label on a node or edge. | |
284 | pub enum LabelText<'a> { | |
285 | /// This kind of label preserves the text directly as is. | |
286 | /// | |
287 | /// Occurrences of backslashes (`\`) are escaped, and thus appear | |
288 | /// as backslashes in the rendered label. | |
85aaf69f | 289 | LabelStr(Cow<'a, str>), |
1a4d82fc JJ |
290 | |
291 | /// This kind of label uses the graphviz label escString type: | |
04454e1e | 292 | /// <https://www.graphviz.org/docs/attr-types/escString> |
1a4d82fc JJ |
293 | /// |
294 | /// Occurrences of backslashes (`\`) are not escaped; instead they | |
295 | /// are interpreted as initiating an escString escape sequence. | |
296 | /// | |
297 | /// Escape sequences of particular interest: in addition to `\n` | |
298 | /// to break a line (centering the line preceding the `\n`), there | |
299 | /// are also the escape sequences `\l` which left-justifies the | |
300 | /// preceding line and `\r` which right-justifies it. | |
85aaf69f | 301 | EscStr(Cow<'a, str>), |
e9174d1e SL |
302 | |
303 | /// This uses a graphviz [HTML string label][html]. The string is | |
304 | /// printed exactly as given, but between `<` and `>`. **No | |
305 | /// escaping is performed.** | |
306 | /// | |
04454e1e | 307 | /// [html]: https://www.graphviz.org/doc/info/shapes.html#html |
e9174d1e | 308 | HtmlStr(Cow<'a, str>), |
1a4d82fc JJ |
309 | } |
310 | ||
c1a9b12d | 311 | /// The style for a node or edge. |
04454e1e | 312 | /// See <https://www.graphviz.org/docs/attr-types/style/> for descriptions. |
c1a9b12d SL |
313 | /// Note that some of these are not valid for edges. |
314 | #[derive(Copy, Clone, PartialEq, Eq, Debug)] | |
315 | pub enum Style { | |
316 | None, | |
317 | Solid, | |
318 | Dashed, | |
319 | Dotted, | |
320 | Bold, | |
321 | Rounded, | |
322 | Diagonals, | |
323 | Filled, | |
324 | Striped, | |
325 | Wedged, | |
326 | } | |
327 | ||
328 | impl Style { | |
329 | pub fn as_slice(self) -> &'static str { | |
330 | match self { | |
331 | Style::None => "", | |
332 | Style::Solid => "solid", | |
333 | Style::Dashed => "dashed", | |
334 | Style::Dotted => "dotted", | |
335 | Style::Bold => "bold", | |
336 | Style::Rounded => "rounded", | |
337 | Style::Diagonals => "diagonals", | |
338 | Style::Filled => "filled", | |
339 | Style::Striped => "striped", | |
340 | Style::Wedged => "wedged", | |
341 | } | |
342 | } | |
343 | } | |
344 | ||
1a4d82fc JJ |
345 | // There is a tension in the design of the labelling API. |
346 | // | |
347 | // For example, I considered making a `Labeller<T>` trait that | |
348 | // provides labels for `T`, and then making the graph type `G` | |
349 | // implement `Labeller<Node>` and `Labeller<Edge>`. However, this is | |
350 | // not possible without functional dependencies. (One could work | |
351 | // around that, but I did not explore that avenue heavily.) | |
352 | // | |
353 | // Another approach that I actually used for a while was to make a | |
354 | // `Label<Context>` trait that is implemented by the client-specific | |
355 | // Node and Edge types (as well as an implementation on Graph itself | |
356 | // for the overall name for the graph). The main disadvantage of this | |
357 | // second approach (compared to having the `G` type parameter | |
358 | // implement a Labelling service) that I have encountered is that it | |
359 | // makes it impossible to use types outside of the current crate | |
360 | // directly as Nodes/Edges; you need to wrap them in newtype'd | |
0731742a | 361 | // structs. See e.g., the `No` and `Ed` structs in the examples. (In |
1a4d82fc JJ |
362 | // practice clients using a graph in some other crate would need to |
363 | // provide some sort of adapter shim over the graph anyway to | |
364 | // interface with this library). | |
365 | // | |
366 | // Another approach would be to make a single `Labeller<N,E>` trait | |
367 | // that provides three methods (graph_label, node_label, edge_label), | |
368 | // and then make `G` implement `Labeller<N,E>`. At first this did not | |
369 | // appeal to me, since I had thought I would need separate methods on | |
370 | // each data variant for dot-internal identifiers versus user-visible | |
371 | // labels. However, the identifier/label distinction only arises for | |
372 | // nodes; graphs themselves only have identifiers, and edges only have | |
373 | // labels. | |
374 | // | |
375 | // So in the end I decided to use the third approach described above. | |
376 | ||
377 | /// `Id` is a Graphviz `ID`. | |
378 | pub struct Id<'a> { | |
85aaf69f | 379 | name: Cow<'a, str>, |
1a4d82fc JJ |
380 | } |
381 | ||
382 | impl<'a> Id<'a> { | |
383 | /// Creates an `Id` named `name`. | |
384 | /// | |
385 | /// The caller must ensure that the input conforms to an | |
386 | /// identifier format: it must be a non-empty string made up of | |
387 | /// alphanumeric or underscore characters, not beginning with a | |
0731742a | 388 | /// digit (i.e., the regular expression `[a-zA-Z_][a-zA-Z_0-9]*`). |
1a4d82fc JJ |
389 | /// |
390 | /// (Note: this format is a strict subset of the `ID` format | |
9fa01778 | 391 | /// defined by the DOT language. This function may change in the |
1a4d82fc JJ |
392 | /// future to accept a broader subset, or the entirety, of DOT's |
393 | /// `ID` format.) | |
394 | /// | |
395 | /// Passing an invalid string (containing spaces, brackets, | |
396 | /// quotes, ...) will return an empty `Err` value. | |
0bf4aa26 XL |
397 | pub fn new<Name: Into<Cow<'a, str>>>(name: Name) -> Result<Id<'a>, ()> { |
398 | let name = name.into(); | |
ff7c6d11 XL |
399 | match name.chars().next() { |
400 | Some(c) if c.is_ascii_alphabetic() || c == '_' => {} | |
401 | _ => return Err(()), | |
1a4d82fc | 402 | } |
dfeec247 | 403 | if !name.chars().all(|c| c.is_ascii_alphanumeric() || c == '_') { |
ff7c6d11 | 404 | return Err(()); |
1a4d82fc | 405 | } |
b7449926 XL |
406 | |
407 | Ok(Id { name }) | |
1a4d82fc JJ |
408 | } |
409 | ||
410 | pub fn as_slice(&'a self) -> &'a str { | |
411 | &*self.name | |
412 | } | |
1a4d82fc JJ |
413 | } |
414 | ||
415 | /// Each instance of a type that implements `Label<C>` maps to a | |
416 | /// unique identifier with respect to `C`, which is used to identify | |
417 | /// it in the generated .dot file. They can also provide more | |
418 | /// elaborate (and non-unique) label text that is used in the graphviz | |
419 | /// rendered output. | |
420 | ||
421 | /// The graph instance is responsible for providing the DOT compatible | |
422 | /// identifiers for the nodes and (optionally) rendered labels for the nodes and | |
423 | /// edges, as well as an identifier for the graph itself. | |
54a0048b SL |
424 | pub trait Labeller<'a> { |
425 | type Node; | |
426 | type Edge; | |
427 | ||
1a4d82fc JJ |
428 | /// Must return a DOT compatible identifier naming the graph. |
429 | fn graph_id(&'a self) -> Id<'a>; | |
430 | ||
431 | /// Maps `n` to a unique identifier with respect to `self`. The | |
b039eaaf | 432 | /// implementor is responsible for ensuring that the returned name |
1a4d82fc | 433 | /// is a valid DOT identifier. |
54a0048b | 434 | fn node_id(&'a self, n: &Self::Node) -> Id<'a>; |
1a4d82fc | 435 | |
e9174d1e SL |
436 | /// Maps `n` to one of the [graphviz `shape` names][1]. If `None` |
437 | /// is returned, no `shape` attribute is specified. | |
438 | /// | |
04454e1e | 439 | /// [1]: https://www.graphviz.org/doc/info/shapes.html |
54a0048b | 440 | fn node_shape(&'a self, _node: &Self::Node) -> Option<LabelText<'a>> { |
e9174d1e SL |
441 | None |
442 | } | |
443 | ||
1a4d82fc JJ |
444 | /// Maps `n` to a label that will be used in the rendered output. |
445 | /// The label need not be unique, and may be the empty string; the | |
446 | /// default is just the output from `node_id`. | |
54a0048b | 447 | fn node_label(&'a self, n: &Self::Node) -> LabelText<'a> { |
1a4d82fc JJ |
448 | LabelStr(self.node_id(n).name) |
449 | } | |
450 | ||
451 | /// Maps `e` to a label that will be used in the rendered output. | |
452 | /// The label need not be unique, and may be the empty string; the | |
453 | /// default is in fact the empty string. | |
ff7c6d11 | 454 | fn edge_label(&'a self, _e: &Self::Edge) -> LabelText<'a> { |
0bf4aa26 | 455 | LabelStr("".into()) |
1a4d82fc | 456 | } |
c1a9b12d SL |
457 | |
458 | /// Maps `n` to a style that will be used in the rendered output. | |
54a0048b | 459 | fn node_style(&'a self, _n: &Self::Node) -> Style { |
c1a9b12d SL |
460 | Style::None |
461 | } | |
462 | ||
463 | /// Maps `e` to a style that will be used in the rendered output. | |
54a0048b | 464 | fn edge_style(&'a self, _e: &Self::Edge) -> Style { |
c1a9b12d SL |
465 | Style::None |
466 | } | |
1a4d82fc JJ |
467 | } |
468 | ||
e9174d1e SL |
469 | /// Escape tags in such a way that it is suitable for inclusion in a |
470 | /// Graphviz HTML label. | |
471 | pub fn escape_html(s: &str) -> String { | |
a2a8927a | 472 | s.replace('&', "&").replace('\"', """).replace('<', "<").replace('>', ">") |
e9174d1e SL |
473 | } |
474 | ||
1a4d82fc | 475 | impl<'a> LabelText<'a> { |
0bf4aa26 XL |
476 | pub fn label<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> { |
477 | LabelStr(s.into()) | |
1a4d82fc JJ |
478 | } |
479 | ||
0bf4aa26 XL |
480 | pub fn html<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> { |
481 | HtmlStr(s.into()) | |
e9174d1e SL |
482 | } |
483 | ||
484 | fn escape_char<F>(c: char, mut f: F) | |
dfeec247 XL |
485 | where |
486 | F: FnMut(char), | |
e9174d1e | 487 | { |
1a4d82fc JJ |
488 | match c { |
489 | // not escaping \\, since Graphviz escString needs to | |
490 | // interpret backslashes; see EscStr above. | |
491 | '\\' => f(c), | |
92a42be0 SL |
492 | _ => { |
493 | for c in c.escape_default() { | |
494 | f(c) | |
495 | } | |
496 | } | |
1a4d82fc JJ |
497 | } |
498 | } | |
499 | fn escape_str(s: &str) -> String { | |
500 | let mut out = String::with_capacity(s.len()); | |
501 | for c in s.chars() { | |
502 | LabelText::escape_char(c, |c| out.push(c)); | |
503 | } | |
504 | out | |
505 | } | |
506 | ||
507 | /// Renders text as string suitable for a label in a .dot file. | |
3b2f2976 | 508 | /// This includes quotes or suitable delimiters. |
e9174d1e | 509 | pub fn to_dot_string(&self) -> String { |
b7449926 XL |
510 | match *self { |
511 | LabelStr(ref s) => format!("\"{}\"", s.escape_default()), | |
3c0e092e | 512 | EscStr(ref s) => format!("\"{}\"", LabelText::escape_str(&s)), |
b7449926 | 513 | HtmlStr(ref s) => format!("<{}>", s), |
1a4d82fc JJ |
514 | } |
515 | } | |
516 | ||
517 | /// Decomposes content into string suitable for making EscStr that | |
9fa01778 | 518 | /// yields same content as self. The result obeys the law |
1a4d82fc JJ |
519 | /// render(`lt`) == render(`EscStr(lt.pre_escaped_content())`) for |
520 | /// all `lt: LabelText`. | |
85aaf69f | 521 | fn pre_escaped_content(self) -> Cow<'a, str> { |
1a4d82fc JJ |
522 | match self { |
523 | EscStr(s) => s, | |
92a42be0 SL |
524 | LabelStr(s) => { |
525 | if s.contains('\\') { | |
9fa01778 | 526 | (&*s).escape_default().to_string().into() |
92a42be0 SL |
527 | } else { |
528 | s | |
529 | } | |
530 | } | |
e9174d1e | 531 | HtmlStr(s) => s, |
1a4d82fc JJ |
532 | } |
533 | } | |
534 | ||
1a4d82fc | 535 | /// Puts `suffix` on a line below this label, with a blank line separator. |
9fa01778 | 536 | pub fn suffix_line(self, suffix: LabelText<'_>) -> LabelText<'static> { |
1a4d82fc JJ |
537 | let mut prefix = self.pre_escaped_content().into_owned(); |
538 | let suffix = suffix.pre_escaped_content(); | |
539 | prefix.push_str(r"\n\n"); | |
cc61c64b | 540 | prefix.push_str(&suffix); |
0bf4aa26 | 541 | EscStr(prefix.into()) |
1a4d82fc JJ |
542 | } |
543 | } | |
544 | ||
dfeec247 XL |
545 | pub type Nodes<'a, N> = Cow<'a, [N]>; |
546 | pub type Edges<'a, E> = Cow<'a, [E]>; | |
1a4d82fc JJ |
547 | |
548 | // (The type parameters in GraphWalk should be associated items, | |
549 | // when/if Rust supports such.) | |
550 | ||
551 | /// GraphWalk is an abstraction over a directed graph = (nodes,edges) | |
552 | /// made up of node handles `N` and edge handles `E`, where each `E` | |
553 | /// can be mapped to its source and target nodes. | |
554 | /// | |
555 | /// The lifetime parameter `'a` is exposed in this trait (rather than | |
556 | /// introduced as a generic parameter on each method declaration) so | |
557 | /// that a client impl can choose `N` and `E` that have substructure | |
558 | /// that is bound by the self lifetime `'a`. | |
559 | /// | |
560 | /// The `nodes` and `edges` method each return instantiations of | |
b039eaaf | 561 | /// `Cow<[T]>` to leave implementors the freedom to create |
1a4d82fc JJ |
562 | /// entirely new vectors or to pass back slices into internally owned |
563 | /// vectors. | |
54a0048b SL |
564 | pub trait GraphWalk<'a> { |
565 | type Node: Clone; | |
566 | type Edge: Clone; | |
567 | ||
1a4d82fc | 568 | /// Returns all the nodes in this graph. |
54a0048b | 569 | fn nodes(&'a self) -> Nodes<'a, Self::Node>; |
1a4d82fc | 570 | /// Returns all of the edges in this graph. |
54a0048b | 571 | fn edges(&'a self) -> Edges<'a, Self::Edge>; |
1a4d82fc | 572 | /// The source node for `edge`. |
54a0048b | 573 | fn source(&'a self, edge: &Self::Edge) -> Self::Node; |
1a4d82fc | 574 | /// The target node for `edge`. |
54a0048b | 575 | fn target(&'a self, edge: &Self::Edge) -> Self::Node; |
1a4d82fc JJ |
576 | } |
577 | ||
1b1a35ee | 578 | #[derive(Clone, PartialEq, Eq, Debug)] |
1a4d82fc JJ |
579 | pub enum RenderOption { |
580 | NoEdgeLabels, | |
581 | NoNodeLabels, | |
c1a9b12d SL |
582 | NoEdgeStyles, |
583 | NoNodeStyles, | |
74b04a01 | 584 | |
1b1a35ee XL |
585 | Fontname(String), |
586 | DarkTheme, | |
1a4d82fc JJ |
587 | } |
588 | ||
1a4d82fc JJ |
589 | /// Renders directed graph `g` into the writer `w` in DOT syntax. |
590 | /// (Simple wrapper around `render_opts` that passes a default set of options.) | |
dfeec247 XL |
591 | pub fn render<'a, N, E, G, W>(g: &'a G, w: &mut W) -> io::Result<()> |
592 | where | |
593 | N: Clone + 'a, | |
594 | E: Clone + 'a, | |
595 | G: Labeller<'a, Node = N, Edge = E> + GraphWalk<'a, Node = N, Edge = E>, | |
596 | W: Write, | |
54a0048b | 597 | { |
1a4d82fc JJ |
598 | render_opts(g, w, &[]) |
599 | } | |
600 | ||
601 | /// Renders directed graph `g` into the writer `w` in DOT syntax. | |
602 | /// (Main entry point for the library.) | |
dfeec247 XL |
603 | pub fn render_opts<'a, N, E, G, W>(g: &'a G, w: &mut W, options: &[RenderOption]) -> io::Result<()> |
604 | where | |
605 | N: Clone + 'a, | |
606 | E: Clone + 'a, | |
607 | G: Labeller<'a, Node = N, Edge = E> + GraphWalk<'a, Node = N, Edge = E>, | |
608 | W: Write, | |
54a0048b | 609 | { |
ff7c6d11 | 610 | writeln!(w, "digraph {} {{", g.graph_id().as_slice())?; |
74b04a01 XL |
611 | |
612 | // Global graph properties | |
1b1a35ee XL |
613 | let mut graph_attrs = Vec::new(); |
614 | let mut content_attrs = Vec::new(); | |
615 | let font; | |
616 | if let Some(fontname) = options.iter().find_map(|option| { | |
617 | if let RenderOption::Fontname(fontname) = option { Some(fontname) } else { None } | |
618 | }) { | |
619 | font = format!(r#"fontname="{}""#, fontname); | |
620 | graph_attrs.push(&font[..]); | |
621 | content_attrs.push(&font[..]); | |
622 | } | |
623 | if options.contains(&RenderOption::DarkTheme) { | |
624 | graph_attrs.push(r#"bgcolor="black""#); | |
29967ef6 | 625 | graph_attrs.push(r#"fontcolor="white""#); |
1b1a35ee XL |
626 | content_attrs.push(r#"color="white""#); |
627 | content_attrs.push(r#"fontcolor="white""#); | |
628 | } | |
629 | if !(graph_attrs.is_empty() && content_attrs.is_empty()) { | |
630 | writeln!(w, r#" graph[{}];"#, graph_attrs.join(" "))?; | |
631 | let content_attrs_str = content_attrs.join(" "); | |
632 | writeln!(w, r#" node[{}];"#, content_attrs_str)?; | |
633 | writeln!(w, r#" edge[{}];"#, content_attrs_str)?; | |
74b04a01 XL |
634 | } |
635 | ||
29967ef6 | 636 | let mut text = Vec::new(); |
62682a34 | 637 | for n in g.nodes().iter() { |
ff7c6d11 | 638 | write!(w, " ")?; |
1a4d82fc | 639 | let id = g.node_id(n); |
c1a9b12d | 640 | |
e9174d1e | 641 | let escaped = &g.node_label(n).to_dot_string(); |
c1a9b12d | 642 | |
ff7c6d11 | 643 | write!(text, "{}", id.as_slice()).unwrap(); |
c1a9b12d SL |
644 | |
645 | if !options.contains(&RenderOption::NoNodeLabels) { | |
ff7c6d11 | 646 | write!(text, "[label={}]", escaped).unwrap(); |
1a4d82fc | 647 | } |
c1a9b12d SL |
648 | |
649 | let style = g.node_style(n); | |
650 | if !options.contains(&RenderOption::NoNodeStyles) && style != Style::None { | |
ff7c6d11 | 651 | write!(text, "[style=\"{}\"]", style.as_slice()).unwrap(); |
c1a9b12d SL |
652 | } |
653 | ||
e9174d1e | 654 | if let Some(s) = g.node_shape(n) { |
ff7c6d11 | 655 | write!(text, "[shape={}]", &s.to_dot_string()).unwrap(); |
e9174d1e SL |
656 | } |
657 | ||
ff7c6d11 | 658 | writeln!(text, ";").unwrap(); |
a2a8927a | 659 | w.write_all(&text)?; |
29967ef6 XL |
660 | |
661 | text.clear(); | |
1a4d82fc JJ |
662 | } |
663 | ||
62682a34 | 664 | for e in g.edges().iter() { |
e9174d1e | 665 | let escaped_label = &g.edge_label(e).to_dot_string(); |
ff7c6d11 | 666 | write!(w, " ")?; |
1a4d82fc JJ |
667 | let source = g.source(e); |
668 | let target = g.target(e); | |
669 | let source_id = g.node_id(&source); | |
670 | let target_id = g.node_id(&target); | |
c1a9b12d | 671 | |
ff7c6d11 | 672 | write!(text, "{} -> {}", source_id.as_slice(), target_id.as_slice()).unwrap(); |
c1a9b12d SL |
673 | |
674 | if !options.contains(&RenderOption::NoEdgeLabels) { | |
ff7c6d11 | 675 | write!(text, "[label={}]", escaped_label).unwrap(); |
c1a9b12d SL |
676 | } |
677 | ||
678 | let style = g.edge_style(e); | |
679 | if !options.contains(&RenderOption::NoEdgeStyles) && style != Style::None { | |
ff7c6d11 | 680 | write!(text, "[style=\"{}\"]", style.as_slice()).unwrap(); |
1a4d82fc | 681 | } |
c1a9b12d | 682 | |
ff7c6d11 | 683 | writeln!(text, ";").unwrap(); |
a2a8927a | 684 | w.write_all(&text)?; |
29967ef6 XL |
685 | |
686 | text.clear(); | |
1a4d82fc JJ |
687 | } |
688 | ||
ff7c6d11 | 689 | writeln!(w, "}}") |
1a4d82fc JJ |
690 | } |
691 | ||
692 | #[cfg(test)] | |
dc9dc135 | 693 | mod tests; |