boa_engine/vm/flowgraph/
graph.rs

1use crate::vm::flowgraph::{Color, Edge, EdgeStyle, EdgeType, Node, NodeShape};
2use std::{collections::hash_map::RandomState, fmt::Write as _, hash::BuildHasher};
3
4/// This represents the direction of flow in the flowgraph.
5#[derive(Debug, Clone, Copy)]
6pub enum Direction {
7    /// Represents a top to bottom direction.
8    TopToBottom,
9
10    /// Represents a bottom to top direction.
11    BottomToTop,
12
13    /// Represents a left to right direction.
14    LeftToRight,
15
16    /// Represents a right to left direction.
17    RightToLeft,
18}
19
20/// Represents a sub-graph in the graph.
21///
22/// Sub-graphs can be nested.
23#[derive(Debug, Clone)]
24pub struct SubGraph {
25    /// The label on the sub-graph.
26    label: String,
27    /// The nodes it contains.
28    nodes: Vec<Node>,
29    /// The edges/connections in contains.
30    edges: Vec<Edge>,
31    /// The direction of flow in the sub-graph.
32    direction: Direction,
33
34    /// The sub-graphs this graph contains.
35    subgraphs: Vec<SubGraph>,
36}
37
38impl SubGraph {
39    /// Construct a new subgraph.
40    #[inline]
41    fn new(label: String) -> Self {
42        Self {
43            label,
44            nodes: Vec::default(),
45            edges: Vec::default(),
46            direction: Direction::TopToBottom,
47            subgraphs: Vec::default(),
48        }
49    }
50
51    /// Set the label of the subgraph.
52    #[inline]
53    pub fn set_label(&mut self, label: String) {
54        self.label = label;
55    }
56
57    /// Set the direction of the subgraph.
58    #[inline]
59    pub fn set_direction(&mut self, direction: Direction) {
60        self.direction = direction;
61    }
62
63    /// Add a node to the subgraph.
64    #[inline]
65    pub fn add_node(&mut self, location: usize, shape: NodeShape, label: Box<str>, color: Color) {
66        let node = Node::new(location, shape, label, color);
67        self.nodes.push(node);
68    }
69
70    /// Add an edge to the subgraph.
71    #[inline]
72    pub fn add_edge(
73        &mut self,
74        from: usize,
75        to: usize,
76        label: Option<Box<str>>,
77        color: Color,
78        style: EdgeStyle,
79    ) -> &mut Edge {
80        let edge = Edge::new(from, to, label, color, style);
81        self.edges.push(edge);
82        self.edges.last_mut().expect("Already pushed edge")
83    }
84
85    /// Create a subgraph in this subgraph.
86    #[inline]
87    pub fn subgraph(&mut self, label: String) -> &mut Self {
88        self.subgraphs.push(Self::new(label));
89        let result = self
90            .subgraphs
91            .last_mut()
92            .expect("We just pushed a subgraph");
93        result.set_direction(self.direction);
94        result
95    }
96
97    /// Format into the graphviz format.
98    fn graphviz_format(&self, result: &mut String, prefix: &str) {
99        let label = format!("{}", RandomState::new().hash_one(&self.label));
100        let _ = writeln!(result, "\tsubgraph cluster_{prefix}_{label} {{");
101        result.push_str("\t\tstyle = filled;\n");
102        let _ = writeln!(
103            result,
104            "\t\tlabel = \"{}\";",
105            if self.label.is_empty() {
106                "Anonymous Function"
107            } else {
108                self.label.as_ref()
109            }
110        );
111
112        let _ = writeln!(
113            result,
114            "\t\t{prefix}_{label}_start [label=\"Start\",shape=Mdiamond,style=filled,color=green]"
115        );
116        if !self.nodes.is_empty() {
117            let _ = writeln!(result, "\t\t{prefix}_{label}_start -> {prefix}_{label}_i_0");
118        }
119
120        for node in &self.nodes {
121            let shape = match node.shape {
122                NodeShape::None => "",
123                NodeShape::Record => ", shape=record",
124                NodeShape::Diamond => ", shape=diamond",
125            };
126            let color = format!(",style=filled,color=\"{}\"", node.color);
127            let _ = writeln!(
128                result,
129                "\t\t{prefix}_{}_i_{}[label=\"{:04}: {}\"{shape}{color}];",
130                label, node.location, node.location, node.label
131            );
132        }
133
134        for edge in &self.edges {
135            let color = format!(",color=\"{}\"", edge.color);
136            let style = match (edge.style, edge.type_) {
137                (EdgeStyle::Line, EdgeType::None) => ",dir=none",
138                (EdgeStyle::Line, EdgeType::Arrow) => "",
139                (EdgeStyle::Dotted, EdgeType::None) => ",style=dotted,dir=none",
140                (EdgeStyle::Dotted, EdgeType::Arrow) => ",style=dotted",
141                (EdgeStyle::Dashed, EdgeType::None) => ",style=dashed,dir=none",
142                (EdgeStyle::Dashed, EdgeType::Arrow) => ",style=dashed,",
143            };
144            let _ = writeln!(
145                result,
146                "\t\t{prefix}_{}_i_{} -> {prefix}_{}_i_{} [label=\"{}\", len=f{style}{color}];",
147                label,
148                edge.from,
149                label,
150                edge.to,
151                edge.label.as_deref().unwrap_or("")
152            );
153        }
154        for (index, subgraph) in self.subgraphs.iter().enumerate() {
155            let prefix = format!("{prefix}_F{index}");
156            subgraph.graphviz_format(result, &prefix);
157        }
158        result.push_str("\t}\n");
159    }
160
161    /// Format into the mermaid format.
162    fn mermaid_format(&self, result: &mut String, prefix: &str) {
163        let label = format!("{}", RandomState::new().hash_one(&self.label));
164        let rankdir = match self.direction {
165            Direction::TopToBottom => "TB",
166            Direction::BottomToTop => "BT",
167            Direction::LeftToRight => "LR",
168            Direction::RightToLeft => "RL",
169        };
170        let _ = writeln!(
171            result,
172            "  subgraph {prefix}_{}[\"{}\"]",
173            label,
174            if self.label.is_empty() {
175                "Anonymous Function"
176            } else {
177                self.label.as_ref()
178            }
179        );
180        let _ = writeln!(result, "  direction {rankdir}");
181        let _ = writeln!(result, "  {prefix}_{label}_start{{Start}}");
182        let _ = writeln!(result, "  style {prefix}_{label}_start fill:green");
183        if !self.nodes.is_empty() {
184            let _ = writeln!(result, "  {prefix}_{label}_start --> {prefix}_{label}_i_0");
185        }
186
187        for node in &self.nodes {
188            let (shape_begin, shape_end) = match node.shape {
189                NodeShape::None | NodeShape::Record => ('[', ']'),
190                NodeShape::Diamond => ('{', '}'),
191            };
192            let _ = writeln!(
193                result,
194                "  {prefix}_{}_i_{}{shape_begin}\"{:04}: {}\"{shape_end}",
195                label, node.location, node.location, node.label
196            );
197            if !node.color.is_none() {
198                let _ = writeln!(
199                    result,
200                    "  style {prefix}_{}_i_{} fill:{}",
201                    label, node.location, node.color
202                );
203            }
204        }
205
206        for (index, edge) in self.edges.iter().enumerate() {
207            let style = match (edge.style, edge.type_) {
208                (EdgeStyle::Line, EdgeType::None) => "---",
209                (EdgeStyle::Line, EdgeType::Arrow) => "-->",
210                (EdgeStyle::Dotted | EdgeStyle::Dashed, EdgeType::None) => "-.-",
211                (EdgeStyle::Dotted | EdgeStyle::Dashed, EdgeType::Arrow) => "-.->",
212            };
213            let _ = writeln!(
214                result,
215                "  {prefix}_{}_i_{} {style}| {}| {prefix}_{}_i_{}",
216                label,
217                edge.from,
218                edge.label.as_deref().unwrap_or(""),
219                label,
220                edge.to,
221            );
222
223            if !edge.color.is_none() {
224                let _ = writeln!(
225                    result,
226                    "  linkStyle {} stroke:{}, stroke-width: 4px",
227                    index + 1,
228                    edge.color
229                );
230            }
231        }
232        for (index, subgraph) in self.subgraphs.iter().enumerate() {
233            let prefix = format!("{prefix}_F{index}");
234            subgraph.mermaid_format(result, &prefix);
235        }
236        result.push_str("  end\n");
237    }
238}
239
240/// This represents the main graph that other [`SubGraph`]s can be nested in.
241#[derive(Debug)]
242pub struct Graph {
243    subgraphs: Vec<SubGraph>,
244    direction: Direction,
245}
246
247impl Graph {
248    /// Construct a [`Graph`]
249    #[inline]
250    #[must_use]
251    pub fn new(direction: Direction) -> Self {
252        Self {
253            subgraphs: Vec::default(),
254            direction,
255        }
256    }
257
258    /// Create a [`SubGraph`] in this [`Graph`].
259    #[inline]
260    pub fn subgraph(&mut self, label: String) -> &mut SubGraph {
261        self.subgraphs.push(SubGraph::new(label));
262        let result = self
263            .subgraphs
264            .last_mut()
265            .expect("We just pushed a subgraph");
266        result.set_direction(self.direction);
267        result
268    }
269
270    /// Output the graph into the graphviz format.
271    #[must_use]
272    pub fn to_graphviz_format(&self) -> String {
273        let mut result = String::new();
274        result += "digraph {\n";
275        result += "\tnode [shape=record];\n";
276
277        let rankdir = match self.direction {
278            Direction::TopToBottom => "TB",
279            Direction::BottomToTop => "BT",
280            Direction::LeftToRight => "LR",
281            Direction::RightToLeft => "RL",
282        };
283        let _ = writeln!(result, "\trankdir={rankdir};");
284
285        for subgraph in &self.subgraphs {
286            subgraph.graphviz_format(&mut result, "");
287        }
288        result += "}\n";
289        result
290    }
291
292    /// Output the graph into the mermaid format.
293    #[must_use]
294    pub fn to_mermaid_format(&self) -> String {
295        let mut result = String::new();
296        let rankdir = match self.direction {
297            Direction::TopToBottom => "TD",
298            Direction::BottomToTop => "DT",
299            Direction::LeftToRight => "LR",
300            Direction::RightToLeft => "RL",
301        };
302        let _ = writeln!(result, "graph {rankdir}");
303
304        for subgraph in &self.subgraphs {
305            subgraph.mermaid_format(&mut result, "");
306        }
307        result += "\n";
308        result
309    }
310}
boa_engine/vm/flowgraph/graph.rs

boa_engine/vm/flowgraph/
graph.rs
