]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | use super::LabelText::{self, EscStr, HtmlStr, LabelStr}; |
2 | use super::{render, Edges, GraphWalk, Id, Labeller, Nodes, Style}; | |
dc9dc135 XL |
3 | use std::io; |
4 | use std::io::prelude::*; | |
dfeec247 | 5 | use NodeLabels::*; |
dc9dc135 XL |
6 | |
7 | /// each node is an index in a vector in the graph. | |
8 | type Node = usize; | |
9 | struct Edge { | |
10 | from: usize, | |
11 | to: usize, | |
12 | label: &'static str, | |
13 | style: Style, | |
14 | } | |
15 | ||
16 | fn edge(from: usize, to: usize, label: &'static str, style: Style) -> Edge { | |
dfeec247 | 17 | Edge { from, to, label, style } |
dc9dc135 XL |
18 | } |
19 | ||
20 | struct LabelledGraph { | |
21 | /// The name for this graph. Used for labeling generated `digraph`. | |
22 | name: &'static str, | |
23 | ||
24 | /// Each node is an index into `node_labels`; these labels are | |
25 | /// used as the label text for each node. (The node *names*, | |
26 | /// which are unique identifiers, are derived from their index | |
27 | /// in this array.) | |
28 | /// | |
29 | /// If a node maps to None here, then just use its name as its | |
30 | /// text. | |
31 | node_labels: Vec<Option<&'static str>>, | |
32 | ||
33 | node_styles: Vec<Style>, | |
34 | ||
35 | /// Each edge relates a from-index to a to-index along with a | |
36 | /// label; `edges` collects them. | |
37 | edges: Vec<Edge>, | |
38 | } | |
39 | ||
40 | // A simple wrapper around LabelledGraph that forces the labels to | |
41 | // be emitted as EscStr. | |
42 | struct LabelledGraphWithEscStrs { | |
43 | graph: LabelledGraph, | |
44 | } | |
45 | ||
46 | enum NodeLabels<L> { | |
47 | AllNodesLabelled(Vec<L>), | |
48 | UnlabelledNodes(usize), | |
49 | SomeNodesLabelled(Vec<Option<L>>), | |
50 | } | |
51 | ||
52 | type Trivial = NodeLabels<&'static str>; | |
53 | ||
54 | impl NodeLabels<&'static str> { | |
55 | fn to_opt_strs(self) -> Vec<Option<&'static str>> { | |
56 | match self { | |
57 | UnlabelledNodes(len) => vec![None; len], | |
58 | AllNodesLabelled(lbls) => lbls.into_iter().map(|l| Some(l)).collect(), | |
59 | SomeNodesLabelled(lbls) => lbls.into_iter().collect(), | |
60 | } | |
61 | } | |
62 | ||
63 | fn len(&self) -> usize { | |
64 | match self { | |
65 | &UnlabelledNodes(len) => len, | |
66 | &AllNodesLabelled(ref lbls) => lbls.len(), | |
67 | &SomeNodesLabelled(ref lbls) => lbls.len(), | |
68 | } | |
69 | } | |
70 | } | |
71 | ||
72 | impl LabelledGraph { | |
dfeec247 XL |
73 | fn new( |
74 | name: &'static str, | |
75 | node_labels: Trivial, | |
76 | edges: Vec<Edge>, | |
77 | node_styles: Option<Vec<Style>>, | |
78 | ) -> LabelledGraph { | |
dc9dc135 XL |
79 | let count = node_labels.len(); |
80 | LabelledGraph { | |
81 | name, | |
82 | node_labels: node_labels.to_opt_strs(), | |
83 | edges, | |
84 | node_styles: match node_styles { | |
85 | Some(nodes) => nodes, | |
86 | None => vec![Style::None; count], | |
87 | }, | |
88 | } | |
89 | } | |
90 | } | |
91 | ||
92 | impl LabelledGraphWithEscStrs { | |
dfeec247 | 93 | fn new(name: &'static str, node_labels: Trivial, edges: Vec<Edge>) -> LabelledGraphWithEscStrs { |
dc9dc135 XL |
94 | LabelledGraphWithEscStrs { graph: LabelledGraph::new(name, node_labels, edges, None) } |
95 | } | |
96 | } | |
97 | ||
98 | fn id_name<'a>(n: &Node) -> Id<'a> { | |
99 | Id::new(format!("N{}", *n)).unwrap() | |
100 | } | |
101 | ||
102 | impl<'a> Labeller<'a> for LabelledGraph { | |
103 | type Node = Node; | |
104 | type Edge = &'a Edge; | |
105 | fn graph_id(&'a self) -> Id<'a> { | |
106 | Id::new(self.name).unwrap() | |
107 | } | |
108 | fn node_id(&'a self, n: &Node) -> Id<'a> { | |
109 | id_name(n) | |
110 | } | |
111 | fn node_label(&'a self, n: &Node) -> LabelText<'a> { | |
112 | match self.node_labels[*n] { | |
113 | Some(l) => LabelStr(l.into()), | |
114 | None => LabelStr(id_name(n).name()), | |
115 | } | |
116 | } | |
117 | fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> { | |
118 | LabelStr(e.label.into()) | |
119 | } | |
120 | fn node_style(&'a self, n: &Node) -> Style { | |
121 | self.node_styles[*n] | |
122 | } | |
123 | fn edge_style(&'a self, e: &&'a Edge) -> Style { | |
124 | e.style | |
125 | } | |
126 | } | |
127 | ||
128 | impl<'a> Labeller<'a> for LabelledGraphWithEscStrs { | |
129 | type Node = Node; | |
130 | type Edge = &'a Edge; | |
131 | fn graph_id(&'a self) -> Id<'a> { | |
132 | self.graph.graph_id() | |
133 | } | |
134 | fn node_id(&'a self, n: &Node) -> Id<'a> { | |
135 | self.graph.node_id(n) | |
136 | } | |
137 | fn node_label(&'a self, n: &Node) -> LabelText<'a> { | |
138 | match self.graph.node_label(n) { | |
139 | LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s), | |
140 | } | |
141 | } | |
142 | fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> { | |
143 | match self.graph.edge_label(e) { | |
144 | LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s), | |
145 | } | |
146 | } | |
147 | } | |
148 | ||
149 | impl<'a> GraphWalk<'a> for LabelledGraph { | |
150 | type Node = Node; | |
151 | type Edge = &'a Edge; | |
152 | fn nodes(&'a self) -> Nodes<'a, Node> { | |
153 | (0..self.node_labels.len()).collect() | |
154 | } | |
155 | fn edges(&'a self) -> Edges<'a, &'a Edge> { | |
156 | self.edges.iter().collect() | |
157 | } | |
158 | fn source(&'a self, edge: &&'a Edge) -> Node { | |
159 | edge.from | |
160 | } | |
161 | fn target(&'a self, edge: &&'a Edge) -> Node { | |
162 | edge.to | |
163 | } | |
164 | } | |
165 | ||
166 | impl<'a> GraphWalk<'a> for LabelledGraphWithEscStrs { | |
167 | type Node = Node; | |
168 | type Edge = &'a Edge; | |
169 | fn nodes(&'a self) -> Nodes<'a, Node> { | |
170 | self.graph.nodes() | |
171 | } | |
172 | fn edges(&'a self) -> Edges<'a, &'a Edge> { | |
173 | self.graph.edges() | |
174 | } | |
175 | fn source(&'a self, edge: &&'a Edge) -> Node { | |
176 | edge.from | |
177 | } | |
178 | fn target(&'a self, edge: &&'a Edge) -> Node { | |
179 | edge.to | |
180 | } | |
181 | } | |
182 | ||
183 | fn test_input(g: LabelledGraph) -> io::Result<String> { | |
184 | let mut writer = Vec::new(); | |
185 | render(&g, &mut writer).unwrap(); | |
186 | let mut s = String::new(); | |
187 | Read::read_to_string(&mut &*writer, &mut s)?; | |
188 | Ok(s) | |
189 | } | |
190 | ||
191 | // All of the tests use raw-strings as the format for the expected outputs, | |
192 | // so that you can cut-and-paste the content into a .dot file yourself to | |
193 | // see what the graphviz visualizer would produce. | |
194 | ||
195 | #[test] | |
196 | fn empty_graph() { | |
197 | let labels: Trivial = UnlabelledNodes(0); | |
198 | let r = test_input(LabelledGraph::new("empty_graph", labels, vec![], None)); | |
dfeec247 XL |
199 | assert_eq!( |
200 | r.unwrap(), | |
201 | r#"digraph empty_graph { | |
dc9dc135 | 202 | } |
dfeec247 XL |
203 | "# |
204 | ); | |
dc9dc135 XL |
205 | } |
206 | ||
207 | #[test] | |
208 | fn single_node() { | |
209 | let labels: Trivial = UnlabelledNodes(1); | |
210 | let r = test_input(LabelledGraph::new("single_node", labels, vec![], None)); | |
dfeec247 XL |
211 | assert_eq!( |
212 | r.unwrap(), | |
213 | r#"digraph single_node { | |
dc9dc135 XL |
214 | N0[label="N0"]; |
215 | } | |
dfeec247 XL |
216 | "# |
217 | ); | |
dc9dc135 XL |
218 | } |
219 | ||
220 | #[test] | |
221 | fn single_node_with_style() { | |
222 | let labels: Trivial = UnlabelledNodes(1); | |
223 | let styles = Some(vec![Style::Dashed]); | |
224 | let r = test_input(LabelledGraph::new("single_node", labels, vec![], styles)); | |
dfeec247 XL |
225 | assert_eq!( |
226 | r.unwrap(), | |
227 | r#"digraph single_node { | |
dc9dc135 XL |
228 | N0[label="N0"][style="dashed"]; |
229 | } | |
dfeec247 XL |
230 | "# |
231 | ); | |
dc9dc135 XL |
232 | } |
233 | ||
234 | #[test] | |
235 | fn single_edge() { | |
236 | let labels: Trivial = UnlabelledNodes(2); | |
dfeec247 XL |
237 | let result = test_input(LabelledGraph::new( |
238 | "single_edge", | |
239 | labels, | |
240 | vec![edge(0, 1, "E", Style::None)], | |
241 | None, | |
242 | )); | |
243 | assert_eq!( | |
244 | result.unwrap(), | |
245 | r#"digraph single_edge { | |
dc9dc135 XL |
246 | N0[label="N0"]; |
247 | N1[label="N1"]; | |
248 | N0 -> N1[label="E"]; | |
249 | } | |
dfeec247 XL |
250 | "# |
251 | ); | |
dc9dc135 XL |
252 | } |
253 | ||
254 | #[test] | |
255 | fn single_edge_with_style() { | |
256 | let labels: Trivial = UnlabelledNodes(2); | |
dfeec247 XL |
257 | let result = test_input(LabelledGraph::new( |
258 | "single_edge", | |
259 | labels, | |
260 | vec![edge(0, 1, "E", Style::Bold)], | |
261 | None, | |
262 | )); | |
263 | assert_eq!( | |
264 | result.unwrap(), | |
265 | r#"digraph single_edge { | |
dc9dc135 XL |
266 | N0[label="N0"]; |
267 | N1[label="N1"]; | |
268 | N0 -> N1[label="E"][style="bold"]; | |
269 | } | |
dfeec247 XL |
270 | "# |
271 | ); | |
dc9dc135 XL |
272 | } |
273 | ||
274 | #[test] | |
275 | fn test_some_labelled() { | |
276 | let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]); | |
277 | let styles = Some(vec![Style::None, Style::Dotted]); | |
dfeec247 XL |
278 | let result = test_input(LabelledGraph::new( |
279 | "test_some_labelled", | |
280 | labels, | |
281 | vec![edge(0, 1, "A-1", Style::None)], | |
282 | styles, | |
283 | )); | |
284 | assert_eq!( | |
285 | result.unwrap(), | |
286 | r#"digraph test_some_labelled { | |
dc9dc135 XL |
287 | N0[label="A"]; |
288 | N1[label="N1"][style="dotted"]; | |
289 | N0 -> N1[label="A-1"]; | |
290 | } | |
dfeec247 XL |
291 | "# |
292 | ); | |
dc9dc135 XL |
293 | } |
294 | ||
295 | #[test] | |
296 | fn single_cyclic_node() { | |
297 | let labels: Trivial = UnlabelledNodes(1); | |
dfeec247 XL |
298 | let r = test_input(LabelledGraph::new( |
299 | "single_cyclic_node", | |
300 | labels, | |
301 | vec![edge(0, 0, "E", Style::None)], | |
302 | None, | |
303 | )); | |
304 | assert_eq!( | |
305 | r.unwrap(), | |
306 | r#"digraph single_cyclic_node { | |
dc9dc135 XL |
307 | N0[label="N0"]; |
308 | N0 -> N0[label="E"]; | |
309 | } | |
dfeec247 XL |
310 | "# |
311 | ); | |
dc9dc135 XL |
312 | } |
313 | ||
314 | #[test] | |
315 | fn hasse_diagram() { | |
316 | let labels = AllNodesLabelled(vec!["{x,y}", "{x}", "{y}", "{}"]); | |
dfeec247 XL |
317 | let r = test_input(LabelledGraph::new( |
318 | "hasse_diagram", | |
319 | labels, | |
320 | vec![ | |
321 | edge(0, 1, "", Style::None), | |
322 | edge(0, 2, "", Style::None), | |
323 | edge(1, 3, "", Style::None), | |
324 | edge(2, 3, "", Style::None), | |
325 | ], | |
326 | None, | |
327 | )); | |
328 | assert_eq!( | |
329 | r.unwrap(), | |
330 | r#"digraph hasse_diagram { | |
dc9dc135 XL |
331 | N0[label="{x,y}"]; |
332 | N1[label="{x}"]; | |
333 | N2[label="{y}"]; | |
334 | N3[label="{}"]; | |
335 | N0 -> N1[label=""]; | |
336 | N0 -> N2[label=""]; | |
337 | N1 -> N3[label=""]; | |
338 | N2 -> N3[label=""]; | |
339 | } | |
dfeec247 XL |
340 | "# |
341 | ); | |
dc9dc135 XL |
342 | } |
343 | ||
344 | #[test] | |
345 | fn left_aligned_text() { | |
346 | let labels = AllNodesLabelled(vec![ | |
347 | "if test {\ | |
348 | \\l branch1\ | |
349 | \\l} else {\ | |
350 | \\l branch2\ | |
351 | \\l}\ | |
352 | \\lafterward\ | |
353 | \\l", | |
354 | "branch1", | |
355 | "branch2", | |
dfeec247 XL |
356 | "afterward", |
357 | ]); | |
dc9dc135 XL |
358 | |
359 | let mut writer = Vec::new(); | |
360 | ||
dfeec247 XL |
361 | let g = LabelledGraphWithEscStrs::new( |
362 | "syntax_tree", | |
363 | labels, | |
364 | vec![ | |
365 | edge(0, 1, "then", Style::None), | |
366 | edge(0, 2, "else", Style::None), | |
367 | edge(1, 3, ";", Style::None), | |
368 | edge(2, 3, ";", Style::None), | |
369 | ], | |
370 | ); | |
dc9dc135 XL |
371 | |
372 | render(&g, &mut writer).unwrap(); | |
373 | let mut r = String::new(); | |
374 | Read::read_to_string(&mut &*writer, &mut r).unwrap(); | |
375 | ||
dfeec247 XL |
376 | assert_eq!( |
377 | r, | |
378 | r#"digraph syntax_tree { | |
dc9dc135 XL |
379 | N0[label="if test {\l branch1\l} else {\l branch2\l}\lafterward\l"]; |
380 | N1[label="branch1"]; | |
381 | N2[label="branch2"]; | |
382 | N3[label="afterward"]; | |
383 | N0 -> N1[label="then"]; | |
384 | N0 -> N2[label="else"]; | |
385 | N1 -> N3[label=";"]; | |
386 | N2 -> N3[label=";"]; | |
387 | } | |
dfeec247 XL |
388 | "# |
389 | ); | |
dc9dc135 XL |
390 | } |
391 | ||
392 | #[test] | |
393 | fn simple_id_construction() { | |
394 | let id1 = Id::new("hello"); | |
395 | match id1 { | |
396 | Ok(_) => {} | |
397 | Err(..) => panic!("'hello' is not a valid value for id anymore"), | |
398 | } | |
399 | } | |
400 | ||
401 | #[test] | |
402 | fn badly_formatted_id() { | |
403 | let id2 = Id::new("Weird { struct : ure } !!!"); | |
404 | match id2 { | |
405 | Ok(_) => panic!("graphviz id suddenly allows spaces, brackets and stuff"), | |
406 | Err(..) => {} | |
407 | } | |
408 | } |