tree_graphviz/
lib.rs

1#![deny(missing_docs)]
2#![deny(unsafe_code)]
3#![deny(unstable_features)]
4
5//! A simple crate for generating GraphViz dot directed trees,
6//!     based on an arbitrary tree structure.
7//! A tree can be any struct that implements:
8//!     [`std::string::ToString`], [`std::hash::Hash`] and [`TreeVizNode`].
9//! Currently, this crate does not support recursive elements within a tree.
10//! An optional `"async"` feature is available and provides an async variant of
11//!     `draw_nodes` - `draw_nodes_async`, which will recurse through a
12//!     node's children concurrently.
13//! This introduces a dependency on the `futures` crate, but may be quicker,
14//!     especially if `futures` is already in your dependency tree.
15
16use std::{
17    collections::HashSet,
18    hash::{DefaultHasher, Hash, Hasher},
19    string::ToString,
20};
21
22/// A trait that represents a node in an arbitrary tree structure.
23/// To use this with [draw_nodes], you also need to implement [std::hash::Hash].
24pub trait TreeVizNode
25where
26    Self: ToString,
27{
28    /// Returns a vector containing the sub-nodes that are children of this node.
29    fn children(&self) -> Vec<Self>
30    where
31        Self: Sized;
32}
33
34/// Returns a visualisation of the tree with the root node `node` in the GraphViz DOT format, as a
35/// string.
36/// - `graph_name` is the name of the graph, which will have spaces and non-ascii characters
37///     removed to comply with DOT's format restrictions.
38pub fn draw_nodes<T: TreeVizNode + Hash>(graph_name: &str, node: T) -> String {
39    let graph_name: String = graph_name
40        .to_owned()
41        .chars()
42        .filter(|c| *c != ' ' && c.is_ascii())
43        .collect();
44    let mut out = format!("digraph {} {{", graph_name);
45    out = format!("{}\n{}", out, draw_node(None, node, &mut HashSet::new()));
46    out = out
47        .lines()
48        .map(|ln| ln.trim())
49        .filter(|ln| *ln != ";")
50        .collect();
51    out.push('}');
52    out
53}
54
55fn draw_node<T: TreeVizNode + Hash>(
56    parent_hash: Option<u64>,
57    node: T,
58    hashes: &mut HashSet<u64>,
59) -> String {
60    let mut hasher = DefaultHasher::new();
61    node.hash(&mut hasher);
62    let mut hash = hasher.finish();
63    while hashes.contains(&hash) {
64        hash += 1;
65    }
66    hashes.insert(hash);
67    let mut out = format!("{} [label=\"{}\"];\n", hash, sanitize(node.to_string()));
68    if let Some(parent) = parent_hash {
69        out = format!("{}{} -> {};\n", out, parent, hash);
70    }
71    for child in node.children() {
72        out = format!("{}{};\n", out, draw_node(Some(hash), child, hashes));
73    }
74    out
75}
76
77fn sanitize(s: String) -> String {
78    s.replace(|c: char| !c.is_ascii(), "")
79        .replace('"', "\\\"")
80        .chars()
81        .filter(|c| c.is_ascii())
82        .collect()
83}
84
85#[cfg(test)]
86mod tests;
87
88#[cfg(feature = "async")]
89use futures::future::join_all;
90#[cfg(feature = "async")]
91use std::sync::{Arc, Mutex};
92
93/// Returns a future promising the visualisation of the tree with the root node `node` in the GraphViz DOT format, as a
94/// string.
95/// - `graph_name` is the name of the graph, which will have spaces and non-ascii characters
96///     removed to comply with DOT's format restrictions.
97#[cfg(feature = "async")]
98pub async fn draw_nodes_async<T: TreeVizNode + Hash>(graph_name: &str, node: T) -> String {
99    let graph_name: String = graph_name
100        .to_owned()
101        .chars()
102        .filter(|c| *c != ' ' && c.is_ascii())
103        .collect();
104    let mut out = format!("digraph {} {{", graph_name);
105    out = format!(
106        "{}\n{}",
107        out,
108        draw_node_async(None, node, Arc::new(Mutex::new(HashSet::new()))).await
109    );
110    out = out
111        .lines()
112        .map(|ln| ln.trim())
113        .filter(|ln| *ln != ";")
114        .collect();
115    out.push('}');
116    out
117}
118
119#[cfg(feature = "async")]
120async fn draw_node_async<T: TreeVizNode + Hash>(
121    parent_hash: Option<u64>,
122    node: T,
123    hashes: Arc<Mutex<HashSet<u64>>>,
124) -> String {
125    let mut hasher = DefaultHasher::new();
126    node.hash(&mut hasher);
127    let mut hash = hasher.finish();
128    {
129        let mut _hashes = hashes.clone();
130        let mut hashesa = _hashes.lock().unwrap();
131        while hashesa.contains(&hash) {
132            hash += 1;
133        }
134        hashesa.insert(hash);
135    }
136    let mut out = format!("{} [label=\"{}\"];\n", hash, sanitize(node.to_string()));
137    if let Some(parent) = parent_hash {
138        out = format!("{}{} -> {};\n", out, parent, hash);
139    }
140    let promises = node
141        .children()
142        .into_iter()
143        .map(|child| draw_node_async(Some(hash), child, hashes.clone()));
144    out = format!(
145        "{}{}",
146        out,
147        join_all(promises)
148            .await
149            .into_iter()
150            .map(|s| format!("{};\n", s))
151            .collect::<String>()
152    );
153    out
154}
tree_graphviz/lib.rs

tree_graphviz/
lib.rs
