graphviz_pure_parser/
lib.rs

1//! Re-entrant DOT and HTML-label parser and canonical serializer (`graphviz-pure-parser`).
2//! Fixes GV-BUG-001 (global mutable lexer state) and GV-BUG-005 (memory leaks on syntax errors).
3
4pub mod canon;
5pub mod lexer;
6pub mod parser;
7
8pub use canon::{
9    canon_str, canon_str_with, canon_value, is_html_string, write_canon, write_canon_forced,
10};
11pub use lexer::{Lexer, Token, TokenKind};
12pub use parser::{GlobalAttrs, Parser};
13
14use graphviz_pure_core::{Graph, Result};
15
16/// Parses a DOT graph specification into an arena-backed [`Graph`].
17pub fn parse_dot(input: &str) -> Result<Graph> {
18    Parser::parse_str(input)
19}
20
21/// Parses every graph in a DOT stream (`digraph G {..} digraph H {..}`), applying `globals`
22/// (`-G`/`-N`/`-E` command line attributes) as if declared at the top of each graph.
23pub fn parse_dot_all(input: &str, globals: &GlobalAttrs) -> Result<Vec<Graph>> {
24    Parser::parse_all(input, globals)
25}
26
27/// [`parse_dot_all`] keeping the graphs read before a syntax error, with the error.
28pub fn parse_dot_all_partial(
29    input: &str,
30    globals: &GlobalAttrs,
31) -> (Vec<Graph>, Option<graphviz_pure_core::GraphvizError>) {
32    Parser::parse_all_partial(input, globals)
33}
34
35#[cfg(test)]
36mod tests {
37    use super::*;
38    use graphviz_pure_core::GraphKind;
39    use std::path::PathBuf;
40
41    fn fixture_path(name: &str) -> PathBuf {
42        PathBuf::from(env!("CARGO_MANIFEST_DIR"))
43            .join("../../tests/fixtures")
44            .join(name)
45    }
46
47    fn read_fixture(name: &str) -> String {
48        let path = fixture_path(name);
49        std::fs::read_to_string(&path)
50            .unwrap_or_else(|e| panic!("failed to read fixture {}: {}", path.display(), e))
51    }
52
53    #[test]
54    fn parse_all_20_fixtures_and_roundtrip_canon() {
55        let fixtures = [
56            "ER.gv",
57            "Heawood.gv",
58            "NaN.gv",
59            "Petersen.gv",
60            "abstract.gv",
61            "alf.gv",
62            "arrows.gv",
63            "clust.gv",
64            "clust1.gv",
65            "clust2.gv",
66            "clust3.gv",
67            "clust4.gv",
68            "fsm.gv",
69            "html.gv",
70            "html2.gv",
71            "pack.gv",
72            "record.gv",
73            "shapes.gv",
74            "unix.gv",
75            "world.gv",
76        ];
77
78        for name in fixtures {
79            let src = read_fixture(name);
80            let graph =
81                parse_dot(&src).unwrap_or_else(|e| panic!("failed to parse fixture {name}: {e}"));
82            assert!(
83                !graph.nodes.is_empty(),
84                "fixture {name} should have at least 1 node"
85            );
86
87            let canon = write_canon(&graph);
88            let reparsed = parse_dot(&canon).unwrap_or_else(|e| {
89                panic!("failed to re-parse canonical output for {name}: {e}\nCanon:\n{canon}")
90            });
91            assert_eq!(
92                graph.kind, reparsed.kind,
93                "kind mismatch after canon roundtrip for {name}"
94            );
95            assert_eq!(
96                graph.nodes.len(),
97                reparsed.nodes.len(),
98                "node count mismatch after canon roundtrip for {name}"
99            );
100            assert_eq!(
101                graph.edges.len(),
102                reparsed.edges.len(),
103                "edge count mismatch after canon roundtrip for {name}"
104            );
105        }
106    }
107
108    #[test]
109    fn verify_fsm_fixture() {
110        let g = parse_dot(&read_fixture("fsm.gv")).unwrap();
111        assert_eq!(g.name, "finite_state_machine");
112        assert_eq!(g.kind, GraphKind::Directed);
113        assert!(!g.strict);
114        assert_eq!(g.nodes.len(), 9);
115        assert_eq!(g.edges.len(), 14);
116        assert_eq!(g.graph_attrs.get("rankdir").map(String::as_str), Some("LR"));
117
118        let lr0 = g.node_lookup["LR_0"];
119        let lr1 = g.node_lookup["LR_1"];
120        assert_eq!(
121            g.nodes[lr0.0 as usize]
122                .attrs
123                .get("shape")
124                .map(String::as_str),
125            Some("doublecircle")
126        );
127        assert_eq!(
128            g.nodes[lr1.0 as usize]
129                .attrs
130                .get("shape")
131                .map(String::as_str),
132            Some("circle")
133        );
134    }
135
136    #[test]
137    fn verify_clusters_and_attribute_scoping() {
138        let clust = parse_dot(&read_fixture("clust.gv")).unwrap();
139        assert_eq!(clust.nodes.len(), 8);
140        assert_eq!(clust.edges.len(), 9);
141        assert_eq!(clust.subgraphs.len(), 2);
142        assert!(clust.subgraphs[0].is_cluster);
143        assert_eq!(clust.subgraphs[0].name, "cluster_0");
144        assert_eq!(
145            clust.subgraphs[0]
146                .graph_attrs
147                .get("label")
148                .map(String::as_str),
149            Some("hello world")
150        );
151        assert_eq!(clust.subgraphs[0].nodes.len(), 3);
152        assert_eq!(clust.subgraphs[0].edges.len(), 2);
153
154        let clust4 = parse_dot(&read_fixture("clust4.gv")).unwrap();
155        assert_eq!(clust4.nodes.len(), 10);
156        assert_eq!(clust4.edges.len(), 13);
157        assert_eq!(clust4.subgraphs.len(), 2);
158        let a0 = clust4.node_lookup["a0"];
159        let b0 = clust4.node_lookup["b0"];
160        let start = clust4.node_lookup["start"];
161        assert_eq!(
162            clust4.nodes[a0.0 as usize]
163                .attrs
164                .get("color")
165                .map(String::as_str),
166            Some("white")
167        );
168        assert_eq!(
169            clust4.nodes[b0.0 as usize].attrs.get("color"),
170            None,
171            "color=white in cluster_0 must not leak into cluster_1"
172        );
173        assert_eq!(
174            clust4.nodes[start.0 as usize]
175                .attrs
176                .get("shape")
177                .map(String::as_str),
178            Some("Mdiamond")
179        );
180    }
181
182    #[test]
183    fn canon_distinguishes_quoted_and_html_labels() {
184        let g = parse_dot(
185            "digraph { a [label=\"<x>\"]; b [label=<<b>x</b>>]; a -> b [label=\"<e>\"]; }",
186        )
187        .unwrap();
188        let canon = write_canon(&g);
189        assert!(canon.contains("a\t[label=\"<x>\"];"), "{canon}");
190        assert!(canon.contains("b\t[label=<<b>x</b>>];"), "{canon}");
191        assert!(canon.contains("a -> b\t[label=\"<e>\"];"), "{canon}");
192        assert!(canon.contains("node [label=\"\\N\"];"), "{canon}");
193    }
194
195    #[test]
196    fn command_line_attrs_are_fixed_at_root() {
197        // `global_def` marks the symbols `fixed`: root attribute statements keep
198        // the command-line value, subgraphs and individual objects may change it.
199        let mut globals = GlobalAttrs::default();
200        globals.graph.insert("rankdir".into(), "LR".into());
201        globals.node.insert("shape".into(), "box".into());
202        let src = "digraph G { rankdir=TB; graph [rankdir=BT]; node [shape=circle]; a; \
203                   b [shape=point]; subgraph s { rankdir=RL; node [shape=egg]; c } }";
204        let g = &parse_dot_all(src, &globals).unwrap()[0];
205        assert_eq!(g.graph_attrs.get("rankdir").map(String::as_str), Some("LR"));
206        let shape = |n: usize| g.nodes[n].attrs.get("shape").map(String::as_str);
207        assert_eq!(shape(0), Some("box"));
208        assert_eq!(shape(1), Some("point"));
209        assert_eq!(shape(2), Some("egg"));
210        assert_eq!(
211            g.subgraphs[0]
212                .graph_attrs
213                .get("rankdir")
214                .map(String::as_str),
215            Some("RL")
216        );
217    }
218
219    #[test]
220    fn parse_dot_all_drops_the_rest_of_a_graphs_last_line() {
221        // cgraph reads line by line and starts a new scanner per graph.
222        let graphs = parse_dot_all(
223            "digraph G { a -> b } graph H { c -- d }",
224            &GlobalAttrs::default(),
225        )
226        .unwrap();
227        assert_eq!(graphs.len(), 1);
228    }
229
230    #[test]
231    fn parse_dot_all_returns_every_graph_with_globals() {
232        let mut globals = GlobalAttrs::default();
233        globals.graph.insert("rankdir".into(), "LR".into());
234        globals.node.insert("shape".into(), "box".into());
235        globals.edge.insert("color".into(), "red".into());
236        let graphs = parse_dot_all("digraph G { a -> b }\ngraph H { c -- d }", &globals).unwrap();
237        assert_eq!(graphs.len(), 2);
238        assert_eq!(graphs[0].name, "G");
239        assert_eq!(graphs[1].name, "H");
240        assert_eq!(graphs[1].kind, GraphKind::Undirected);
241        for g in &graphs {
242            assert_eq!(g.graph_attrs.get("rankdir").map(String::as_str), Some("LR"));
243            assert_eq!(
244                g.nodes[0].attrs.get("shape").map(String::as_str),
245                Some("box")
246            );
247            assert_eq!(
248                g.edges[0].attrs.get("color").map(String::as_str),
249                Some("red")
250            );
251        }
252        assert_eq!(
253            parse_dot("digraph G { a } digraph H { b }").unwrap().name,
254            "G"
255        );
256        assert!(
257            parse_dot_all("", &GlobalAttrs::default())
258                .unwrap()
259                .is_empty()
260        );
261    }
262
263    #[test]
264    fn canon_orders_out_edges_by_head_sequence() {
265        let g = parse_dot("digraph { b; c; a -> c; a -> b; }").unwrap();
266        let canon = write_canon(&g);
267        assert!(canon.find("a -> b").unwrap() < canon.find("a -> c").unwrap());
268    }
269
270    #[test]
271    fn verify_html_labels_and_ports() {
272        let html = parse_dot(&read_fixture("html.gv")).unwrap();
273        assert_eq!(html.nodes.len(), 3);
274        assert_eq!(html.edges.len(), 2);
275        for node in &html.nodes {
276            let label = node.attrs.get("label").expect("missing label");
277            assert!(is_html_string(label), "expected HTML label, got {label}");
278            assert!(label.contains("<TABLE"));
279        }
280        assert_eq!(html.edges[0].tail_port.name.as_deref(), Some("f1"));
281        assert_eq!(html.edges[0].head_port.name.as_deref(), Some("f0"));
282        assert_eq!(html.edges[1].tail_port.name.as_deref(), Some("f2"));
283        assert_eq!(html.edges[1].head_port.name.as_deref(), Some("here"));
284
285        let html2 = parse_dot(&read_fixture("html2.gv")).unwrap();
286        assert_eq!(html2.nodes.len(), 4);
287        assert_eq!(html2.edges.len(), 3);
288        assert_eq!(html2.subgraphs.len(), 1);
289        assert_eq!(html2.edges[0].tail_port.name.as_deref(), Some("here"));
290        assert_eq!(html2.edges[0].head_port.name.as_deref(), Some("there"));
291        let edge_label = html2.edges[2]
292            .attrs
293            .get("label")
294            .expect("missing edge label");
295        assert!(is_html_string(edge_label));
296    }
297
298    #[test]
299    fn verify_er_heawood_petersen_pack_world() {
300        let er = parse_dot(&read_fixture("ER.gv")).unwrap();
301        assert_eq!(er.kind, GraphKind::Undirected);
302        assert_eq!(er.nodes.len(), 12);
303        assert_eq!(er.edges.len(), 12);
304        let name0 = er.node_lookup["name0"];
305        let code = er.node_lookup["code"];
306        assert_eq!(
307            er.nodes[name0.0 as usize]
308                .attrs
309                .get("label")
310                .map(String::as_str),
311            Some("name")
312        );
313        assert_eq!(
314            er.nodes[code.0 as usize]
315                .attrs
316                .get("label")
317                .map(String::as_str),
318            Some("\\N")
319        );
320
321        let heawood = parse_dot(&read_fixture("Heawood.gv")).unwrap();
322        assert_eq!(heawood.name, "Heawood");
323        assert_eq!(heawood.nodes.len(), 14);
324        assert_eq!(heawood.edges.len(), 21);
325
326        let petersen = parse_dot(&read_fixture("Petersen.gv")).unwrap();
327        assert_eq!(petersen.name, "Petersen");
328        assert_eq!(petersen.nodes.len(), 10);
329        assert_eq!(petersen.edges.len(), 15);
330        assert_eq!(
331            petersen.edges[0].attrs.get("color").map(String::as_str),
332            Some("blue")
333        );
334
335        let pack = parse_dot(&read_fixture("pack.gv")).unwrap();
336        assert_eq!(pack.nodes.len(), 24);
337        assert_eq!(pack.edges.len(), 20);
338
339        let world = parse_dot(&read_fixture("world.gv")).unwrap();
340        assert_eq!(world.subgraphs.len(), 14);
341        assert!(world.edges.len() > 50);
342    }
343
344    #[test]
345    fn verify_strict_concat_compass_and_syntax_errors() {
346        let dot = r#"
347            # Preprocessor comment
348            strict digraph "My" + "Graph" {
349                a:p1:ne -> b:p2:sw [label="hello " + "world"][color=red];
350                a:p1:ne -> b:p2:sw [weight=2];
351                { x, y } -> { z };
352            }
353        "#;
354        let g = parse_dot(dot).unwrap();
355        assert!(g.strict);
356        assert_eq!(g.name, "MyGraph");
357        assert_eq!(g.edges.len(), 3); // strict merges duplicate a->b, plus x->z and y->z
358        assert_eq!(g.edges[0].tail_port.name.as_deref(), Some("p1"));
359        assert_eq!(g.edges[0].tail_port.compass.as_deref(), Some("ne"));
360        assert_eq!(g.edges[0].head_port.name.as_deref(), Some("p2"));
361        assert_eq!(g.edges[0].head_port.compass.as_deref(), Some("sw"));
362        assert_eq!(
363            g.edges[0].attrs.get("label").map(String::as_str),
364            Some("hello world")
365        );
366        assert_eq!(
367            g.edges[0].attrs.get("weight").map(String::as_str),
368            Some("2")
369        );
370
371        // Directed edge in undirected graph must fail
372        assert!(parse_dot("graph G { a -> b }").is_err());
373        // Undirected edge in directed graph must fail
374        assert!(parse_dot("digraph G { a -- b }").is_err());
375        // Unclosed HTML string must fail
376        assert!(parse_dot("digraph G { a [label=<<table>] }").is_err());
377    }
378
379    /// Issue #29. scan.l returns `T_node`, `T_edge`, `T_graph`, `T_digraph`,
380    /// `T_subgraph` and `T_strict` for the keywords (flex `--case-insensitive`),
381    /// and grammar.y's `atom : T_atom | qatom` accepts none of them, so an
382    /// unquoted keyword is a syntax error as an attribute name or value, a
383    /// port or a compass point. C 16.1.0 exits 1 on every input below.
384    #[test]
385    fn unquoted_keywords_are_not_atoms() {
386        for src in [
387            "digraph G { packmode=node; }",
388            "digraph G { x=strict }",
389            "digraph G { x=digraph }",
390            "digraph G { a [label=edge] }",
391            "digraph G { a [label=NODE] }",
392            "digraph G { a [label=Edge] }",
393            "digraph G { a [node=1] }",
394            "digraph G { a [NODE=1] }",
395            "digraph G { a [label=node, b=c] }",
396            "graph G { graph [x=subgraph] }",
397            "digraph G { a:graph -> b }",
398            "digraph G { a -> b:strict }",
399            "digraph G { a:b:node }",
400            "digraph G { a -> edge }",
401        ] {
402            assert!(parse_dot(src).is_err(), "{src} should be a syntax error");
403        }
404    }
405
406    /// Issue #29: quoted keywords are `T_qatom` in C, so they stay valid.
407    #[test]
408    fn quoted_keywords_are_atoms() {
409        let g = parse_dot(
410            r#"digraph G {
411                packmode="node";
412                "node"="edge";
413                a [label="edge", "node"="1", x="a" + "graph"];
414                a:"graph":"n" -> b;
415                nodes; edged; graphx;
416            }"#,
417        )
418        .unwrap();
419        assert_eq!(
420            g.graph_attrs.get("packmode").map(String::as_str),
421            Some("node")
422        );
423        assert_eq!(g.graph_attrs.get("node").map(String::as_str), Some("edge"));
424        let a = &g.nodes[g.node_lookup["a"].0 as usize].attrs;
425        assert_eq!(a.get("label").map(String::as_str), Some("edge"));
426        assert_eq!(a.get("node").map(String::as_str), Some("1"));
427        assert_eq!(a.get("x").map(String::as_str), Some("agraph"));
428        assert_eq!(g.edges[0].tail_port.name.as_deref(), Some("graph"));
429        assert_eq!(g.edges[0].tail_port.compass.as_deref(), Some("n"));
430        for name in ["nodes", "edged", "graphx"] {
431            assert!(g.node_lookup.contains_key(name), "{name}");
432        }
433    }
434}
graphviz_pure_parser/lib.rs

graphviz_pure_parser/
lib.rs
