1use std::collections::HashSet;
4use std::fmt::{Debug, Display};
5
6use petgraph::algo::toposort;
7use petgraph::dot::{Config, Dot};
8use petgraph::graph::{DiGraph, NodeIndex};
9use petgraph::visit::IntoNodeReferences;
10
11use crate::group::crdt::StateChangeResult;
12use crate::group::{GroupAction, GroupControlMessage, GroupCrdt, GroupCrdtState, GroupMember};
13use crate::traits::{GroupStore, IdentityHandle, Operation, OperationId, Orderer, Resolver};
14
15const OP_FILTER_NODE: &str = "#E63C3F";
16const OP_OK_NODE: &str = "#BFC6C77F";
17const OP_NOOP_NODE: &str = "#FFA142";
18const OP_ROOT_NODE: &str = "#EDD7B17F";
19const INDIVIDUAL_NODE: &str = "#EDD7B17F";
20const ADD_MEMBER_EDGE: &str = "#0091187F";
21const PREVIOUS_EDGE: &str = "#000000";
22const DEPENDENCIES_EDGE: &str = "#B748E37F";
23
24impl<ID, OP, C, RS, ORD, GS> GroupCrdtState<ID, OP, C, RS, ORD, GS>
25where
26 ID: IdentityHandle + Ord + Display,
27 OP: OperationId + Ord + Display,
28 C: Clone + Debug + PartialEq + PartialOrd,
29 RS: Resolver<ID, OP, C, ORD, GS> + Clone + Debug,
30 ORD: Orderer<ID, OP, GroupControlMessage<ID, C>> + Clone + Debug,
31 ORD::State: Clone,
32 ORD::Operation: Clone,
33 GS: GroupStore<ID, OP, C, RS, ORD> + Clone + Debug,
34{
35 pub fn display(&self) -> String {
37 let mut graph = DiGraph::new();
38 graph = self.add_nodes_and_previous_edges(self.clone(), graph);
39
40 graph.add_node((None, self.format_final_members()));
41
42 let dag_graphviz = Dot::with_attr_getters(
43 &graph,
44 &[Config::NodeNoLabel, Config::EdgeNoLabel],
45 &|_, edge| {
46 let weight = edge.weight();
47 if weight == "previous" {
48 return format!("color=\"{PREVIOUS_EDGE}\", penwidth = 2.0");
49 }
50
51 if weight == "member" || weight == "sub group" {
52 return format!("color=\"{ADD_MEMBER_EDGE}\", penwidth = 2.0");
53 }
54
55 format!("constraint = false, color=\"{DEPENDENCIES_EDGE}\", penwidth = 2.0")
56 },
57 &|_, (_, (_, s))| format!("label = {}", s),
58 );
59
60 let mut s = format!("{:?}", dag_graphviz);
61 s = s.replace("digraph {", "digraph {\n splines=polyline\n");
62 s
63 }
64
65 fn add_nodes_and_previous_edges(
66 &self,
67 root: Self,
68 mut graph: DiGraph<(Option<OP>, String), String>,
69 ) -> DiGraph<(Option<OP>, String), String> {
70 for operation in self.operations.values() {
71 graph.add_node((Some(operation.id()), self.format_operation(operation)));
72
73 let (operation_idx, _) = graph
74 .node_references()
75 .find(|(_, (op, _))| {
76 if let Some(op) = op {
77 *op == operation.id()
78 } else {
79 false
80 }
81 })
82 .unwrap();
83
84 if let GroupControlMessage {
85 action: GroupAction::Add { member, .. },
86 ..
87 } = operation.payload()
88 {
89 graph = self.add_member_to_graph(operation_idx, member, root.clone(), graph);
90 }
91
92 if let GroupControlMessage {
93 action:
94 GroupAction::Create {
95 initial_members, ..
96 },
97 ..
98 } = operation.payload()
99 {
100 for (member, _access) in initial_members {
101 graph = self.add_member_to_graph(operation_idx, member, root.clone(), graph);
102 }
103 }
104
105 let mut dependencies = operation.dependencies().clone();
106 let previous = operation.previous();
107 dependencies.retain(|id| !previous.contains(id));
108
109 for dependency in dependencies {
110 let (idx, _) = graph
111 .node_references()
112 .find(|(_, (op, _))| {
113 if let Some(op) = op {
114 *op == dependency
115 } else {
116 false
117 }
118 })
119 .unwrap();
120 graph.add_edge(operation_idx, idx, "dependency".to_string());
121 }
122
123 for previous in previous {
124 let (idx, _) = graph
125 .node_references()
126 .find(|(_, (op, _))| {
127 if let Some(op) = op {
128 *op == previous
129 } else {
130 false
131 }
132 })
133 .unwrap();
134 graph.add_edge(operation_idx, idx, "previous".to_string());
135 }
136 }
137
138 graph
139 }
140
141 fn format_operation(&self, operation: &ORD::Operation) -> String {
142 let control_message = operation.payload();
143
144 let mut s = String::new();
145
146 let color = if control_message.is_create() {
147 OP_ROOT_NODE
148 } else {
149 match GroupCrdt::apply_action(
150 self.clone(),
151 operation.id(),
152 operation.author(),
153 &HashSet::from_iter(operation.dependencies()),
154 &control_message.action,
155 )
156 .expect("critical error when applying state change")
157 {
158 StateChangeResult::Ok { .. } => OP_OK_NODE,
159 StateChangeResult::Noop { .. } => OP_NOOP_NODE,
160 StateChangeResult::Filtered { .. } => OP_FILTER_NODE,
161 }
162 };
163
164 s += &format!(
165 "<<TABLE BGCOLOR=\"{color}\" BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">"
166 );
167 s += &format!("<TR><TD>group</TD><TD>{}</TD></TR>", self.id());
168 s += &format!("<TR><TD>operation id</TD><TD>{}</TD></TR>", operation.id());
169 s += &format!("<TR><TD>actor</TD><TD>{}</TD></TR>", operation.author());
170 let previous = operation.previous();
171 if !previous.is_empty() {
172 s += &format!(
173 "<TR><TD>previous</TD><TD>{}</TD></TR>",
174 self.format_dependencies(&previous)
175 );
176 }
177 let dependencies = operation.dependencies().clone();
178 if !dependencies.is_empty() {
179 s += &format!(
180 "<TR><TD>dependencies</TD><TD>{}</TD></TR>",
181 self.format_dependencies(&dependencies)
182 );
183 }
184 s += &format!(
185 "<TR><TD COLSPAN=\"2\">{}</TD></TR>",
186 self.format_control_message(&control_message)
187 );
188 s += &format!(
189 "<TR><TD COLSPAN=\"2\">{}</TD></TR>",
190 self.format_members(operation)
191 );
192 s += "</TABLE>>";
193 s
194 }
195
196 fn format_final_members(&self) -> String {
197 let mut s = String::new();
198 s += "<<TABLE BGCOLOR=\"#00E30F7F\" BORDER=\"1\" CELLBORDER=\"1\" CELLSPACING=\"2\">";
199
200 let members = self.transitive_members().unwrap();
201 s += "<TR><TD>GROUP MEMBERS</TD></TR>";
202 for (id, access) in members {
203 s += &format!("<TR><TD> {} : {} </TD></TR>", id, access);
204 }
205 s += "</TABLE>>";
206 s
207 }
208
209 fn format_control_message(&self, message: &GroupControlMessage<ID, C>) -> String {
210 let mut s = String::new();
211 s += "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">";
212
213 match &message.action {
214 GroupAction::Create { initial_members } => {
215 s += "<TR><TD>CREATE</TD></TR>";
216 s += "<TR><TD>initial members</TD></TR>";
217 for (member, access) in initial_members {
218 match member {
219 GroupMember::Individual(id) => {
220 s += &format!("<TR><TD>individual : {} : {}</TD></TR>", id, access)
221 }
222 GroupMember::Group(id) => {
223 s += &format!("<TR><TD>group : {} : {}</TD></TR>", id, access)
224 }
225 }
226 }
227 }
228 GroupAction::Add { member, access } => {
229 s += "<TR><TD>ADD</TD></TR>";
230 match member {
231 GroupMember::Individual(id) => {
232 s += &format!("<TR><TD>individual : {} : {}</TD></TR>", id, access)
233 }
234 GroupMember::Group(id) => {
235 s += &format!("<TR><TD>group : {} : {}</TD></TR>", id, access)
236 }
237 }
238 }
239 GroupAction::Remove { member } => {
240 s += "<TR><TD>REMOVE</TD></TR>";
241 match member {
242 GroupMember::Individual(id) => {
243 s += &format!("<TR><TD>individual : {}</TD></TR>", id)
244 }
245 GroupMember::Group(id) => s += &format!("<TR><TD>group : {}</TD></TR>", id),
246 }
247 }
248 GroupAction::Promote { member, access } => {
249 s += "<TR><TD>PROMOTE</TD></TR>";
250 match member {
251 GroupMember::Individual(id) => {
252 s += &format!("<TR><TD>individual : {} : {}</TD></TR>", id, access)
253 }
254 GroupMember::Group(id) => {
255 s += &format!("<TR><TD>group : {} : {}</TD></TR>", id, access)
256 }
257 }
258 }
259 GroupAction::Demote { member, access } => {
260 s += "<TR><TD>DEMOTE</TD></TR>";
261 match member {
262 GroupMember::Individual(id) => {
263 s += &format!("<TR><TD>individual : {} : {}</TD></TR>", id, access)
264 }
265 GroupMember::Group(id) => {
266 s += &format!("<TR><TD>group : {} : {}</TD></TR>", id, access)
267 }
268 }
269 }
270 }
271 s += "</TABLE>";
272 s
273 }
274
275 fn format_members(&self, operation: &ORD::Operation) -> String {
276 let mut dependencies = HashSet::from_iter(operation.dependencies().clone());
277 dependencies.insert(operation.id());
278 let mut members = self
279 .transitive_members_at(&dependencies)
280 .expect("state exists");
281 members.sort_by(|(id_a, _), (id_b, _)| id_a.cmp(id_b));
282
283 let mut s = String::new();
284 s += "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">";
285 s += "<TR><TD>MEMBERS</TD></TR>";
286
287 for (member, access) in members {
288 s += &format!("<TR><TD>{member} : {access}</TD></TR>")
289 }
290
291 s += "</TABLE>";
292 s
293 }
294
295 fn format_dependencies(&self, dependencies: &Vec<OP>) -> String {
296 let mut s = String::new();
297 s += "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">";
298
299 for id in dependencies {
300 s += &format!("<TR><TD>{id}</TD></TR>")
301 }
302
303 s += "</TABLE>";
304 s
305 }
306
307 fn add_member_to_graph(
308 &self,
309 operation_idx: NodeIndex,
310 member: GroupMember<ID>,
311 root: Self,
312 mut graph: DiGraph<(Option<OP>, String), String>,
313 ) -> DiGraph<(Option<OP>, String), String> {
314 match member {
315 GroupMember::Individual(id) => {
316 let table = format!(
317 "<<TABLE BGCOLOR=\"{INDIVIDUAL_NODE}\" BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\"><TR><TD>individual</TD><TD>{id}</TD></TR></TABLE>>"
318 );
319 let idx = match graph.node_references().find(|(_, (_, t))| t == &table) {
320 Some((idx, _)) => idx,
321 None => graph.add_node((None, table)),
322 };
323 graph.add_edge(operation_idx, idx, "member".to_string());
324 }
325 GroupMember::Group(id) => {
326 let sub_group = self.get_sub_group(id).unwrap();
327
328 let topo_sort = toposort(&sub_group.graph, None)
329 .expect("group operation sets can be ordered topologically");
330 let create_op_id = topo_sort
331 .first()
332 .expect("at least one operation exists in graph");
333
334 let create_node = graph.node_references().find(|(_, (op, _))| {
335 if let Some(op) = op {
336 op == create_op_id
337 } else {
338 false
339 }
340 });
341
342 let create_operation_idx = match create_node {
343 Some((idx, _)) => idx,
344 None => {
345 graph = sub_group.add_nodes_and_previous_edges(root.clone(), graph);
346 let (idx, _) = graph
347 .node_references()
348 .find(|(_, (op, _))| {
349 if let Some(op) = op {
350 op == create_op_id
351 } else {
352 false
353 }
354 })
355 .unwrap();
356 idx
357 }
358 };
359
360 graph.add_edge(operation_idx, create_operation_idx, "sub group".to_string());
361 }
362 }
363 graph
364 }
365}