1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

use std::{
    collections::{hash_map::DefaultHasher, BTreeMap, BTreeSet, HashSet},
    hash::BuildHasher,
};

use crate::core::{Identifiable, Visitor};

#[derive(Debug)]
struct Node {
    id: usize,
    name: &'static str,
    edges: BTreeSet<usize>,
}

/// A [Visitor] which builds a `Graphviz` representation of a given graph.
///
/// ```
/// # use std::{collections::HashSet, hash::Hash, rc::Rc};
/// #
/// # use depends::{
/// #     core::{
/// #         Depends, Dependency, HashValue, Resolve, UpdateDependee, UpdateLeaf,
/// #         NodeHash, LeafNode
/// #     },
/// #     derives::{Dependee, dependencies, Leaf},
/// # };
/// #
/// # // A `Leaf` is a node which takes new values from outside the graph.
/// # #[derive(Leaf, Default, Hash)]
/// # pub struct NumberInput {
/// #     value: i32,
/// # }
/// #
/// # // `Leaf` types must provide a way for code outside to update their internal state.
/// # // This is just a simple replace for now.
/// # impl UpdateLeaf for NumberInput {
/// #     type Input = i32;
/// #
/// #     fn update_mut(&mut self, input: Self::Input) {
/// #         self.value = input;
/// #     }
/// # }
/// #
/// # // `dependencies` are derived to state what references `Dependee` nodes need to
/// # // calculate their state on-demand. These could be any number of other `Dependee`s
/// # // or `Leaf`s.
/// # #[dependencies]
/// # pub struct Components {
/// #     left: LeafNode<NumberInput>,
/// #     right: LeafNode<NumberInput>,
/// # }
/// #
/// # // A `Dependee` i.e. its state is a pure transformation of other nodes
/// # #[derive(Dependee, Default, Hash)]
/// # #[depends(dependencies = Components)]
/// # pub struct Sum {
/// #     value: i32,
/// # }
/// #
/// # // This trait specifies how a `Dependee` updates its internal state given its dependencies.
/// # impl UpdateDependee for Sum {
/// #     fn update_mut(&mut self, input: <Self as Depends>::Input<'_>) {
/// #         // `ComponentsRef` is auto-generated by `dependencies`. It's a read-reference
/// #         // to each field of `Components`
/// #         let ComponentsRef { left, right } = input;
/// #         self.value = left.value + right.value;
/// #     }
/// # }
/// #
/// # struct MyGraph {
/// #     left: Rc<LeafNode<NumberInput>>,
/// #     right: Rc<LeafNode<NumberInput>>,
/// #     // `SumNode` is auto-generated by `Dependee`.
/// #     sum: Rc<SumNode>,
/// # }
/// #
/// use depends::graphviz::GraphvizVisitor;
///
/// // Compose a graph.
/// let left = NumberInput::default().into_leaf();
/// let right = NumberInput::default().into_leaf();
/// let sum = Sum::default().into_node(Components::new(Rc::clone(&left), Rc::clone(&right)));
///
/// let graph = MyGraph { left, right, sum };
///
/// let mut visitor = GraphvizVisitor::new();
///
/// // Resolve the graph with this visitor.
/// // Be sure NOT to use `resolve_root`, as this will clear the visitor's state.
/// graph.sum.resolve(&mut visitor);
///
/// // A Graphviz representation is now available on the visitor!
/// assert_eq!(visitor.render().unwrap(), r#"
/// digraph G {
///   0[label="NumberInput"];
///   1[label="NumberInput"];
///   2[label="Sum"];
///   0 -> 2;
///   1 -> 2;
/// }
/// "#.trim());
/// ```
#[derive(Debug, Default)]
pub struct GraphvizVisitor {
    visitor: HashSet<usize>,
    nodes: BTreeMap<usize, Node>,
    stack: Vec<usize>,
}

impl GraphvizVisitor {
    pub fn new() -> Self {
        Self::default()
    }

    /// Render the visited graph to Graphviz DOT format. Returns [Option::None]
    /// if no graph has been visited.
    pub fn render(&self) -> Option<String> {
        if self.nodes.is_empty() {
            None
        } else {
            let mut lines = Vec::new();
            lines.push(String::from("digraph G {"));
            self.nodes.values().for_each(|n| {
                lines.push(format!("  {}[label=\"{}\"];", n.id, n.name));
                n.edges.iter().for_each(|c| {
                    lines.push(format!("  {} -> {};", c, n.id));
                });
            });
            lines.push(String::from("}"));
            Some(lines.join("\n"))
        }
    }
}

impl Visitor for GraphvizVisitor {
    type Hasher = DefaultHasher;

    fn visit<N>(&mut self, node: &N) -> bool
    where
        N: Identifiable,
    {
        self.visitor.visit(node)
    }

    fn clear(&mut self) {
        self.visitor.clear();
        self.nodes.clear();
    }

    fn touch<N>(&mut self, node: &N)
    where
        N: Identifiable,
    {
        self.stack.push(node.id());
        self.nodes.entry(node.id()).or_insert_with(|| {
            Node {
                id: node.id(),
                name: N::name(),
                edges: BTreeSet::default(),
            }
        });
    }

    fn leave<N>(&mut self, node: &N)
    where
        N: Identifiable,
    {
        let last = self.stack.pop().unwrap();
        assert_eq!(last, node.id());
        if let Some(parent) = self.stack.last() {
            self.nodes.get_mut(parent).map(|n| n.edges.insert(last));
        }
    }

    fn hasher(&self) -> Self::Hasher {
        self.visitor.hasher().build_hasher()
    }
}