ttgraph/
typed_graph.rs

1//! Typed graph
2//! A container for a graph-like data structure, where nodes have distinct types.
3//! An edge in this graph is a data field in the node.
4
5use std::any::Any;
6// use std::collections::{BTreeMap, BTreeSet};
7use std::fmt::{Debug, Display};
8use std::hash::Hash;
9use std::iter::FusedIterator;
10
11use serde::{Deserialize, Serialize};
12
13use ordermap::{OrderMap, OrderSet};
14
15use uuid::Uuid;
16
17use crate::cate_arena::*;
18// use crate::arena::{self, Arena, ArenaIndex};
19use crate::id_distributer::IdDistributer;
20
21pub mod debug;
22pub mod display;
23pub mod serialize;
24// pub mod library;
25pub mod macro_traits;
26pub use macro_traits::*;
27// pub mod link;
28// pub use link::*;
29
30mod transaction;
31pub use transaction::Transaction;
32
33pub mod check;
34use check::*;
35
36pub mod macros;
37pub use ttgraph_macros::*;
38
39/// The index of a node, which implements [`Copy`].
40///
41/// Note: The index is very independent to the [`Graph`], which does not check if it is realy pointing to a node in the graph.
42#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
43pub struct NodeIndex(pub usize);
44
45impl NodeIndex {
46  /// Make an empty index
47  /// # Example
48  /// ```
49  /// use ttgraph::NodeIndex;
50  /// let a = NodeIndex::empty();
51  /// assert_eq!(a, NodeIndex::empty());
52  /// ````
53  pub fn empty() -> NodeIndex {
54    NodeIndex(0)
55  }
56
57  /// Check if the index is empty
58  ///  /// # Example
59  /// ```
60  /// use ttgraph::NodeIndex;
61  /// let a = NodeIndex::empty();
62  /// assert!(a.is_empty());
63  /// ````
64  pub fn is_empty(&self) -> bool {
65    self.0 == 0
66  }
67}
68
69impl Default for NodeIndex {
70  fn default() -> Self {
71    Self::empty()
72  }
73}
74
75// impl ArenaIndex for NodeIndex {
76//   fn new(id: usize) -> Self {
77//     NodeIndex(id)
78//   }
79// }
80
81impl Display for NodeIndex {
82  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83    if self.is_empty() {
84      write!(f, "empty")
85    } else {
86      write!(f, "{}", self.0)
87    }
88  }
89}
90
91/// A graph with typed nodes
92///
93/// The graph can only by modified by commiting a transaction, which avoids mutable borrow of the graph
94///
95/// # Example:
96///
97/// ```rust
98/// use ttgraph::*;
99/// # use std::collections::BTreeSet;
100///
101/// #[derive(TypedNode, Debug)]
102/// struct NodeA{
103///   link: NodeIndex,
104///   data: usize,
105/// }
106///
107/// #[derive(TypedNode, Debug)]
108/// struct NodeB{
109///   links: BTreeSet<NodeIndex>,
110///   another_data: String,
111/// }
112///
113/// node_enum!{
114///   #[derive(Debug)]
115///   enum Node{
116///     A(NodeA),
117///     B(NodeB)
118///   }
119/// }
120///
121/// # fn main() {
122/// let ctx = Context::new();
123/// let mut graph = Graph::<Node>::new(&ctx);
124/// let mut trans = Transaction::new(&ctx);
125/// // Does some operations on the transaction
126/// graph.commit(trans).unwrap();
127/// # }
128/// ```
129pub struct Graph<NodeT, Arena = <NodeT as NodeEnum>::GenArena>
130where
131  NodeT: NodeEnum,
132  Arena: CateArena<V = NodeT, D = NodeT::Discriminant>,
133{
134  ctx_id: Uuid,
135  nodes: Arena,
136  back_links: OrderMap<NodeIndex, OrderSet<(NodeIndex, NodeT::SourceEnum)>>,
137}
138
139impl<NodeT, Arena> Graph<NodeT, Arena>
140where
141  NodeT: NodeEnum,
142  Arena: CateArena<V = NodeT, D = NodeT::Discriminant>,
143{
144  /// Create an empty graph
145  pub fn new(context: &Context) -> Self {
146    Graph {
147      ctx_id: context.id,
148      nodes: Arena::new(context.node_dist.clone()),
149      back_links: OrderMap::new(),
150    }
151  }
152
153  /// Get the reference of a node. For convinience, if the type of the node is previously known, use [`get_node!()`](crate::get_node!) instead.
154  ///
155  /// # Example
156  /// ```
157  /// use ttgraph::*;
158  ///
159  /// #[derive(TypedNode, Debug)]
160  /// struct NodeA{
161  ///   data: usize,
162  /// }
163  ///
164  /// node_enum!{
165  ///   #[derive(Debug)]
166  ///   enum Node{
167  ///     A(NodeA)
168  ///   }
169  /// }
170  ///
171  /// # fn main() {
172  /// let ctx = Context::new();
173  /// let mut graph = Graph::<Node>::new(&ctx);
174  /// let mut trans = Transaction::new(&ctx);
175  /// let idx = trans.insert(Node::A(NodeA{
176  ///   data: 1
177  /// }));
178  /// graph.commit(trans).unwrap();
179  ///
180  /// // node: Option<&Node>
181  /// let node = graph.get(idx);
182  /// if let Some(Node::A(node)) = node {
183  ///   assert_eq!(node.data, 1);
184  /// } else {
185  ///   panic!();
186  /// }
187  ///
188  /// assert!(graph.get(NodeIndex::empty()).is_none());
189  /// # }
190  /// ````
191  pub fn get(&self, idx: NodeIndex) -> Option<&NodeT> {
192    self.nodes.get(idx)
193  }
194
195  /// Iterate all nodes in the graph following the order of NodeIndex.
196  ///
197  /// If only a type of node is wanted, use [`iter_nodes!`](`crate::iter_nodes!`) instead.
198  ///
199  /// # Example
200  /// ```
201  /// use ttgraph::*;
202  ///
203  /// #[derive(TypedNode, Debug)]
204  /// struct NodeA{
205  ///   a: usize
206  /// }
207  /// #[derive(TypedNode, Debug)]
208  /// struct NodeB{
209  ///   b: usize
210  /// }
211  ///
212  /// node_enum!{
213  ///   #[derive(Debug)]
214  ///   enum Node{
215  ///     A(NodeA),
216  ///     B(NodeB),
217  ///   }
218  /// }
219  ///
220  /// # fn main() {
221  /// let ctx = Context::new();
222  /// let mut graph = Graph::<Node>::new(&ctx);
223  /// let mut trans = Transaction::new(&ctx);
224  ///
225  /// trans.insert(Node::A(NodeA{ a: 1 }));
226  /// trans.insert(Node::A(NodeA{ a: 2 }));
227  /// trans.insert(Node::B(NodeB{ b: 0 }));
228  /// graph.commit(trans).unwrap();
229  ///
230  /// // iterator.next() returns Option<(NodeIndex, &Node)>
231  /// let iterator = graph.iter();
232  /// for (i, (_, node)) in (1..3).zip(iterator) {
233  ///   if let Node::A(a) = node {
234  ///     assert_eq!(i, a.a);
235  ///   } else {
236  ///     panic!();
237  ///   }
238  /// }
239  /// # }
240  /// ```
241  pub fn iter(&self) -> Arena::Iter<'_> {
242    self.nodes.iter()
243  }
244
245  /// Iterate a certain type of nodes denote by the discriminant.
246  /// Time complexity is only related to the number of nodes of that kind. It is backed by [`ordermap::OrderMap`] so it should be fast.
247  ///
248  /// # Example
249  /// ```
250  /// use ttgraph::*;
251  ///
252  /// #[derive(TypedNode, Debug)]
253  /// struct NodeA{
254  ///   a: usize
255  /// }
256  /// #[derive(TypedNode, Debug)]
257  /// struct NodeB{
258  ///   b: usize
259  /// }
260  ///
261  /// node_enum!{
262  ///   #[derive(Debug)]
263  ///   enum Node{
264  ///     A(NodeA),
265  ///     B(NodeB),
266  ///   }
267  /// }
268  ///
269  /// # fn main() {
270  /// let ctx = Context::new();
271  /// let mut graph = Graph::<Node>::new(&ctx);
272  /// let mut trans = Transaction::new(&ctx);
273  ///
274  /// trans.insert(Node::A(NodeA{ a: 1 }));
275  /// trans.insert(Node::A(NodeA{ a: 2 }));
276  /// trans.insert(Node::B(NodeB{ b: 0 }));
277  /// graph.commit(trans).unwrap();
278  ///
279  /// for (_, node) in graph.iter_type(discriminant!(Node::A)){
280  ///   if let Node::A(a) = node {
281  ///     // Ok
282  ///   } else {
283  ///     panic!();
284  ///   }
285  /// }
286  /// # }
287  /// ```
288  pub fn iter_type<'a>(
289    &'a self, d: NodeT::Discriminant,
290  ) -> NodeIterator<'a, NodeT, ordermap::map::Iter<'a, usize, NodeT>> {
291    NodeIterator { iter: self.nodes.get_container(d).iter() }
292  }
293
294  /// Iterate all nodes within the named group
295  ///
296  /// # Example
297  /// ```
298  /// use ttgraph::*;
299  /// #[derive(TypedNode, Debug)]
300  /// struct NodeA {
301  ///   a: usize,
302  /// }
303  /// #[derive(TypedNode, Debug)]
304  /// struct NodeB {
305  ///   b: usize,
306  /// }
307  /// #[derive(TypedNode, Debug)]
308  /// struct NodeC {
309  ///   c: usize,
310  /// }
311  /// #[derive(TypedNode, Debug)]
312  /// struct NodeD {
313  ///   d: usize,
314  /// }
315  ///
316  /// node_enum! {
317  ///   #[derive(Debug)]
318  ///   enum MultiNodes{
319  ///     A(NodeA),
320  ///     B(NodeB),
321  ///     C(NodeC),
322  ///     D(NodeD),
323  ///   }
324  ///   group!{
325  ///     first{A, B},
326  ///     second{C, D},
327  ///     third{A, D},
328  ///     one{B},
329  ///     all{A, B, C, D},
330  ///   }
331  /// }
332  ///
333  /// # fn main() {
334  ///  let ctx = Context::new();
335  ///  let mut graph = Graph::<MultiNodes>::new(&ctx);
336  ///  let mut trans = Transaction::new(&ctx);
337  ///  let a = trans.insert(MultiNodes::A(NodeA { a: 1 }));
338  ///  let b = trans.insert(MultiNodes::B(NodeB { b: 2 }));
339  ///  let c = trans.insert(MultiNodes::C(NodeC { c: 3 }));
340  ///  let d = trans.insert(MultiNodes::D(NodeD { d: 4 }));
341  ///  graph.commit(trans).unwrap();
342  ///
343  ///  assert_eq!(Vec::from_iter(graph.iter_group("first").map(|(x, _)| x)), vec![a, b]);
344  ///  assert_eq!(Vec::from_iter(graph.iter_group("second").map(|(x, _)| x)), vec![c, d]);
345  ///  assert_eq!(Vec::from_iter(graph.iter_group("third").map(|(x, _)| x)), vec![a, d]);
346  ///  assert_eq!(Vec::from_iter(graph.iter_group("one").map(|(x, _)| x)), vec![b]);
347  ///  assert_eq!(Vec::from_iter(graph.iter_group("all").map(|(x, _)| x)), vec![a, b, c, d]);
348  /// # }
349  /// ```
350  pub fn iter_group(&self, name: &'static str) -> impl Iterator<Item = (NodeIndex, &NodeT)> {
351    self.iter().filter(move |(_, n)| n.in_group(name))
352  }
353
354  /// Get the number of nodes in a graph
355  ///
356  /// # Example
357  /// ```
358  /// use ttgraph::*;
359  /// #[derive(TypedNode, Debug)]
360  /// struct NodeA{
361  ///   data: usize,
362  /// }
363  /// node_enum!{
364  ///   #[derive(Debug)]
365  ///   enum Node{
366  ///     A(NodeA)
367  ///   }
368  /// }
369  ///
370  /// # fn main() {
371  /// let ctx = Context::new();
372  /// let mut graph = Graph::<Node>::new(&ctx);
373  /// assert_eq!(graph.len(), 0);
374  /// let mut trans = Transaction::new(&ctx);
375  /// trans.insert(Node::A(NodeA{data: 1}));
376  /// trans.insert(Node::A(NodeA{data: 1}));
377  /// trans.insert(Node::A(NodeA{data: 1}));
378  /// graph.commit(trans).unwrap();
379  /// assert_eq!(graph.len(), 3);
380  /// # }
381  /// ```
382  pub fn len(&self) -> usize {
383    self.nodes.len()
384  }
385
386  /// Check if the graph has no node
387  pub fn is_empty(&self) -> bool {
388    self.len() == 0
389  }
390
391  /// Commit an [`Transaction`] to modify the graph
392  ///
393  /// Operation order:
394  /// + Redirect nodes
395  /// + Insert new nodes
396  /// + Modify nodes
397  /// + Update nodes
398  /// + Redirect all nodes
399  /// + Remove nodes
400  /// + Add/Remove links due to bidirectional declaration
401  /// + Check link types
402  ///
403  /// # Panics
404  ///
405  /// Panics if:
406  ///
407  /// + the transaction and the graph have different context
408  ///
409  /// # Errors
410  ///
411  /// + there are multiple choices to make a bidirectional link (i.e. a.x <-> {b.y, b.z}, found a.x, don't know if b.y=x or b.z=x)
412  /// + type check failed
413  ///
414  /// ** Note that in current version, the contents in the graph is always changed after commit, even with an error occurs. In this case, the graph will be in an unstable state. **
415  ///
416  /// # Example
417  /// ```
418  /// use ttgraph::*;
419  /// #[derive(TypedNode, Debug)]
420  /// struct NodeA{
421  ///   data: usize,
422  /// }
423  /// node_enum!{
424  ///   #[derive(Debug)]
425  ///   enum Node{
426  ///     A(NodeA)
427  ///   }
428  /// }
429  ///
430  /// # fn main() {
431  /// let ctx = Context::new();
432  /// let mut graph = Graph::<Node>::new(&ctx);
433  /// let mut trans = Transaction::new(&ctx);
434  /// trans.insert(Node::A(NodeA{data: 1}));
435  /// graph.commit(trans).unwrap();
436  /// # }
437  /// ```
438  pub fn commit(&mut self, t: Transaction<NodeT, Arena>) -> Result<(), CommitError<NodeT>> {
439    let (lcr, mut err) = self.do_commit(t);
440    self.check_link_type(&lcr, &mut err);
441    if err.is_empty() {
442      Ok(())
443    } else {
444      Err(err)
445    }
446  }
447
448  /// Similar to [`commit()`](Graph::commit), but with additional checks on the changed nodes and links.
449  ///
450  /// See [`GraphCheck`] for more information.
451  #[cfg(feature = "debug")]
452  pub fn commit_checked(
453    &mut self, t: Transaction<NodeT, Arena>, checks: &GraphCheck<NodeT>,
454  ) -> Result<(), CommitError<NodeT>> {
455    let (lcr, mut err) = self.do_commit(t);
456    self.check_link_type(&lcr, &mut err);
457    self.check_change(&lcr, checks, &mut err);
458    if err.is_empty() {
459      Ok(())
460    } else {
461      Err(err)
462    }
463  }
464
465  /// Switch the context and relabel the node ids.
466  ///
467  /// # Usecase:
468  /// + Useful when there are a lot of removed [`NodeIndex`], and after context switching the indexes will be more concise.
469  /// + Merge two graphs with different context. See [`merge`](Transaction::merge) for example.
470  ///
471  /// # Warning:
472  /// + Please ensure there is no uncommitted transactions!
473  /// + [`NodeIndex`] pointing to this graph is useless after context switching!
474  pub fn switch_context(self, new_ctx: &Context) -> Result<Self, CommitError<NodeT>> {
475    let mut new_nodes = Arena::new(new_ctx.node_dist.clone());
476    let mut id_map = OrderMap::new();
477
478    for (id, x) in self.nodes.into_iter() {
479      let new_idx = new_nodes.insert(x);
480      id_map.insert(id, new_idx);
481    }
482
483    for (id, new_id) in &id_map {
484      for (y, s) in &self.back_links[id] {
485        new_nodes.get_mut(id_map[y]).unwrap().modify_link(*s, *id, *new_id);
486      }
487    }
488
489    let mut result = Graph {
490      ctx_id: new_ctx.id,
491      nodes: Arena::new(new_ctx.node_dist.clone()),
492      back_links: OrderMap::new(),
493    };
494
495    let mut lcr = LinkChangeRecorder::default();
496    let mut err = CommitError::default();
497    result.merge_nodes(new_nodes, &mut lcr);
498    result.apply_bidirectional_links(&lcr, &mut err);
499    result.check_link_type(&lcr, &mut err);
500    if err.is_empty() {
501      Ok(result)
502    } else {
503      Err(err)
504    }
505  }
506
507  /// Check if all links are internal, just for debug
508  #[cfg(feature = "debug")]
509  pub fn check_integrity(&self) {
510    for (_, node) in self.nodes.iter() {
511      for (y, _) in node.iter_sources() {
512        debug_assert!(self.get(y).is_some(), "Found external link, integrity check failed!");
513      }
514    }
515  }
516
517  #[cfg(not(feature = "debug"))]
518  pub fn check_integrity(&self) {}
519
520  /// Check if the backlinks are connected correctly, just for debug
521  #[cfg(feature = "debug")]
522  #[doc(hidden)]
523  pub fn check_backlinks(&self) {
524    let mut back_links: OrderMap<NodeIndex, OrderSet<(NodeIndex, NodeT::SourceEnum)>> = OrderMap::new();
525    for (x, n) in self.nodes.iter() {
526      back_links.entry(x).or_default();
527      for (y, s) in n.iter_sources() {
528        back_links.entry(y).or_default().insert((x, s));
529        let links = self.back_links.get(&y).unwrap_or_else(|| panic!("Node {} have no backlink!", x.0));
530        debug_assert!(links.contains(&(x, s)));
531      }
532    }
533    for (k, v) in back_links.iter() {
534      let Some(v2) = self.back_links.get(k) else { panic!("Key {:?} not in back_links {:?}", k, self.back_links) };
535      if !v2.set_eq(v) {
536        panic!("Backlink not equal {:?} expect {:?}", v2, v);
537      }
538    }
539  }
540
541  #[cfg(not(feature = "debug"))]
542  pub fn check_backlinks(&self) {}
543
544  fn do_commit(&mut self, t: Transaction<NodeT, Arena>) -> (LinkChangeRecorder<NodeT>, CommitError<NodeT>) {
545    debug_assert!(t.ctx_id == self.ctx_id, "The transaction and the graph are from different context!");
546    debug_assert!(t.alloc_nodes.is_empty(), "There are unfilled allocated nodes");
547
548    let mut lcr = LinkChangeRecorder::default();
549    let mut err = CommitError::default();
550
551    self.redirect_links_vec(t.redirect_links_vec, &mut lcr);
552    self.merge_nodes(t.inc_nodes, &mut lcr);
553    for (i, f) in t.mut_nodes {
554      self.modify_node(i, f, &mut lcr);
555    }
556    for (i, f) in t.update_nodes {
557      self.update_node(i, f, &mut lcr);
558    }
559    self.redirect_links_vec(t.redirect_all_links_vec, &mut lcr);
560    for n in &t.dec_nodes {
561      self.remove_node(*n, &mut lcr);
562    }
563
564    self.apply_bidirectional_links(&lcr, &mut err);
565    (lcr, err)
566  }
567
568  fn merge_nodes(&mut self, nodes: Arena, lcr: &mut LinkChangeRecorder<NodeT>) {
569    for (x, n) in nodes.iter() {
570      self.add_back_links(x, n);
571      for (y, s) in n.iter_sources() {
572        lcr.add_link(x, y, NodeT::to_link_mirror_enum(s));
573      }
574    }
575
576    self.nodes.merge(nodes);
577  }
578
579  fn remove_node(&mut self, x: NodeIndex, lcr: &mut LinkChangeRecorder<NodeT>) {
580    let n = self.nodes.remove(x).expect("Remove a non-existing node!");
581    for (y, s) in n.iter_sources() {
582      lcr.remove_link(x, y, NodeT::to_link_mirror_enum(s));
583    }
584    self.remove_back_links(x, &n);
585    for (y, s) in self.back_links.swap_remove(&x).unwrap() {
586      self.nodes.get_mut(y).unwrap().modify_link(s, x, NodeIndex::empty());
587      lcr.remove_link(y, x, NodeT::to_link_mirror_enum(s));
588    }
589  }
590
591  fn modify_node<F>(&mut self, x: NodeIndex, f: F, lcr: &mut LinkChangeRecorder<NodeT>)
592  where
593    F: FnOnce(&mut NodeT),
594  {
595    for (y, s) in self.nodes.get(x).unwrap().iter_sources() {
596      self.back_links.get_mut(&y).unwrap().swap_remove(&(x, s));
597      lcr.remove_link(x, y, NodeT::to_link_mirror_enum(s));
598    }
599
600    f(self.nodes.get_mut(x).unwrap());
601
602    for (y, s) in self.nodes.get(x).unwrap().iter_sources() {
603      self.back_links.get_mut(&y).unwrap().insert((x, s));
604      lcr.add_link(x, y, NodeT::to_link_mirror_enum(s));
605    }
606  }
607
608  fn update_node<F>(&mut self, x: NodeIndex, f: F, lcr: &mut LinkChangeRecorder<NodeT>)
609  where
610    F: FnOnce(NodeT) -> NodeT,
611  {
612    for (y, s) in self.nodes.get(x).unwrap().iter_sources() {
613      self.back_links.get_mut(&y).unwrap().swap_remove(&(x, s));
614      lcr.remove_link(x, y, NodeT::to_link_mirror_enum(s));
615    }
616
617    self.nodes.update_with(x, f);
618
619    for (y, s) in self.nodes.get(x).unwrap().iter_sources() {
620      self.back_links.get_mut(&y).unwrap().insert((x, s));
621      lcr.add_link(x, y, NodeT::to_link_mirror_enum(s));
622    }
623  }
624
625  fn redirect_links(&mut self, old_node: NodeIndex, new_node: NodeIndex, lcr: &mut LinkChangeRecorder<NodeT>) {
626    let old_link = self.back_links.swap_remove(&old_node).unwrap();
627    self.back_links.insert(old_node, OrderSet::new());
628
629    let new_link = self.back_links.entry(new_node).or_default();
630    for (y, s) in old_link {
631      new_link.insert((y, s));
632      let result = self.nodes.get_mut(y).unwrap().modify_link(s, old_node, new_node);
633      // add: if (added) {new_idx} else {ttgraph::NodeIndex::empty()},
634      // remove: if (removed) {old_idx} else {ttgraph::NodeIndex::empty()},
635      if result.added {
636        lcr.add_link(y, new_node, NodeT::to_link_mirror_enum(s));
637      }
638      if result.removed {
639        lcr.remove_link(y, old_node, NodeT::to_link_mirror_enum(s));
640      }
641    }
642  }
643
644  fn redirect_links_vec(&mut self, replacements: Vec<(NodeIndex, NodeIndex)>, lcr: &mut LinkChangeRecorder<NodeT>) {
645    let mut fa = OrderMap::new();
646
647    for (old, new) in &replacements {
648      fa.entry(*old).or_insert(*old);
649      fa.entry(*new).or_insert(*new);
650    }
651
652    for (old, new) in &replacements {
653      let mut x = *new;
654      while fa[&x] != x {
655        x = fa[&x];
656      }
657      assert!(x != *old, "Loop redirection detected!");
658      *fa.get_mut(old).unwrap() = x;
659    }
660
661    for (old, new) in &replacements {
662      let mut x = *new;
663      let mut y = fa[&x];
664      while x != y {
665        x = y;
666        y = fa[&y];
667      }
668
669      self.redirect_links(*old, x, lcr);
670
671      x = *new;
672      while fa[&x] != y {
673        let z = fa[&x];
674        *fa.get_mut(&x).unwrap() = y;
675        x = z;
676      }
677    }
678  }
679
680  fn apply_bidirectional_links(&mut self, lcr: &LinkChangeRecorder<NodeT>, err: &mut CommitError<NodeT>) {
681    for &(x, y, l) in &lcr.removes {
682      if !self.nodes.contains(x) || !self.nodes.contains(y) {
683        continue;
684      }
685
686      let bds = self.nodes.get(x).unwrap().get_bidiretional_link_mirrors_of(l);
687      let bds = self.nodes.get(y).unwrap().match_bd_link_group(bds);
688      for link in bds {
689        if self.nodes.get_mut(y).unwrap().remove_link(link, x) {
690          self.remove_back_link(y, x, NodeT::to_source_enum(link));
691        }
692      }
693    }
694
695    for &(x, y, l) in &lcr.adds {
696      if !self.nodes.contains(x) || !self.nodes.contains(y) {
697        continue;
698      }
699
700      // x.l -> y, find y.l2 or y.group should -> x
701      let bds = self.nodes.get(x).unwrap().get_bidiretional_link_mirrors_of(l);
702      // expand y.group to y.l2
703      let bds = self.nodes.get(y).unwrap().match_bd_link_group(bds);
704      if bds.is_empty() {
705        continue;
706      }
707
708      let node = self.nodes.get(y).unwrap();
709      let found = bds.iter().any(|link| node.contains_link(*link, x));
710
711      if !found {
712        if bds.len() == 1 {
713          let link = *bds.first().unwrap();
714          match self.nodes.get_mut(y).unwrap().add_link(link, x) {
715            Ok(added) => {
716              if added {
717                self.add_back_link(y, x, NodeT::to_source_enum(link));
718              }
719            },
720            Err(old) => err.link_multiconnect.push(LinkMultiConnectError { x: y, link, old, new: x }),
721          }
722        } else {
723          err.bdlink_multichoices.push(BDLinkMultiChoiceError { x, link: l, y, choices: bds })
724        }
725      }
726    }
727  }
728
729  fn add_back_link(&mut self, x: NodeIndex, y: NodeIndex, src: NodeT::SourceEnum) {
730    self.back_links.entry(y).or_default().insert((x, src));
731  }
732
733  fn add_back_links(&mut self, x: NodeIndex, n: &NodeT) {
734    self.back_links.entry(x).or_default();
735    for (y, s) in n.iter_sources() {
736      self.back_links.entry(y).or_default().insert((x, s));
737    }
738  }
739
740  fn remove_back_link(&mut self, x: NodeIndex, y: NodeIndex, src: NodeT::SourceEnum) {
741    self.back_links.get_mut(&y).unwrap().swap_remove(&(x, src));
742  }
743
744  fn remove_back_links(&mut self, x: NodeIndex, n: &NodeT) {
745    for (y, s) in n.iter_sources() {
746      self.back_links.get_mut(&y).unwrap().swap_remove(&(x, s));
747    }
748  }
749
750  fn check_link_type(&self, lcr: &LinkChangeRecorder<NodeT>, err: &mut CommitError<NodeT>) {
751    for (_, y, l) in &lcr.adds {
752      if let Some(node) = self.nodes.get(*y) {
753        if let Result::Err(lerr) = NodeT::check_link_type(node.discriminant(), *l) {
754          err.link_type_errors.push(lerr);
755          // panic!("Link type check failed! Link {:?} expect {:?}, found {:?}", err.link, err.expect, err.found);
756        }
757      }
758    }
759  }
760
761  #[cfg(feature = "debug")]
762  fn check_change(&self, lcr: &LinkChangeRecorder<NodeT>, checks: &GraphCheck<NodeT>, err: &mut CommitError<NodeT>) {
763    let mut changed_nodes = OrderSet::new();
764    for (x, _, _) in lcr.adds.iter().chain(lcr.removes.iter()) {
765      changed_nodes.insert(*x);
766    }
767    for (name, check_func) in &checks.node_checks {
768      for x in &changed_nodes {
769        if check_func(*x, self.get(*x).unwrap()).is_err() {
770          err.custom_node_check.push((name.to_string(), *x));
771          // break;
772        }
773      }
774    }
775    for (name, check_func) in &checks.link_add_checks {
776      for (x, y, _) in &lcr.adds {
777        if check_func(*x, *y, self.get(*x).unwrap(), self.get(*y)).is_err() {
778          err.custom_link_add_check.push((name.to_string(), *x, *y));
779          // break;
780        }
781      }
782    }
783    for (name, check_func) in &checks.link_remove_checks {
784      for (x, y, _) in &lcr.adds {
785        if check_func(*x, *y, self.get(*x).unwrap(), self.get(*y)).is_err() {
786          err.custom_link_remove_check.push((name.to_string(), *x, *y));
787          // break;
788        }
789      }
790    }
791  }
792
793  pub(crate) fn do_deserialize(ctx: &Context, nodes: Vec<(NodeIndex, NodeT)>) -> Self {
794    let arena = Arena::new_from_iter(ctx.node_dist.clone(), nodes);
795    let mut lcr = LinkChangeRecorder::default();
796    let mut err = CommitError::default();
797    let mut graph = Self::new(ctx);
798    graph.merge_nodes(arena, &mut lcr);
799    graph.apply_bidirectional_links(&lcr, &mut err);
800    graph
801  }
802}
803
804struct LinkChangeRecorder<NodeT: NodeEnum> {
805  adds: OrderSet<(NodeIndex, NodeIndex, NodeT::LinkMirrorEnum)>,
806  removes: OrderSet<(NodeIndex, NodeIndex, NodeT::LinkMirrorEnum)>,
807}
808impl<NodeT: NodeEnum> LinkChangeRecorder<NodeT> {
809  #[cfg(feature = "debug")]
810  fn add_link(&mut self, x: NodeIndex, y: NodeIndex, l: NodeT::LinkMirrorEnum) {
811    if y.is_empty() {
812      return;
813    }
814    if self.removes.contains(&(x, y, l)) {
815      self.removes.swap_remove(&(x, y, l));
816    } else {
817      self.adds.insert((x, y, l));
818    }
819  }
820
821  #[cfg(not(feature = "debug"))]
822  fn add_link(&mut self, x: NodeIndex, y: NodeIndex, l: NodeT::LinkMirrorEnum) {}
823
824  #[cfg(feature = "debug")]
825  fn remove_link(&mut self, x: NodeIndex, y: NodeIndex, l: NodeT::LinkMirrorEnum) {
826    if y.is_empty() {
827      return;
828    }
829    if self.adds.contains(&(x, y, l)) {
830      self.adds.swap_remove(&(x, y, l));
831    } else {
832      self.removes.insert((x, y, l));
833    }
834  }
835
836  #[cfg(not(feature = "debug"))]
837  fn remove_link(&mut self, x: NodeIndex, y: NodeIndex, l: NodeT::LinkMirrorEnum) {}
838}
839impl<NodeT: NodeEnum> Default for LinkChangeRecorder<NodeT> {
840  fn default() -> Self {
841    LinkChangeRecorder {
842      adds: OrderSet::default(),
843      removes: OrderSet::default(),
844    }
845  }
846}
847
848impl<T: NodeEnum, A: CateArena<V = T, D = T::Discriminant>> IntoIterator for Graph<T, A> {
849  type IntoIter = A::IntoIter;
850  type Item = (NodeIndex, T);
851
852  fn into_iter(self) -> Self::IntoIter {
853    self.nodes.into_iter()
854  }
855}
856
857impl<'a, T: NodeEnum + 'static, A: CateArena<V = T, D = T::Discriminant>> IntoIterator for &'a Graph<T, A> {
858  type IntoIter = A::Iter<'a>;
859  type Item = (NodeIndex, &'a T);
860
861  fn into_iter(self) -> Self::IntoIter {
862    self.iter()
863  }
864}
865
866pub struct NodeIterator<'a, V, I>
867where
868  V: NodeEnum + 'static,
869  I: Iterator<Item = (&'a usize, &'a V)> + ExactSizeIterator + FusedIterator,
870{
871  iter: I,
872}
873impl<'a, V, I> Iterator for NodeIterator<'a, V, I>
874where
875  V: NodeEnum + 'static,
876  I: Iterator<Item = (&'a usize, &'a V)> + ExactSizeIterator + FusedIterator,
877{
878  type Item = (NodeIndex, &'a V);
879  fn next(&mut self) -> Option<Self::Item> {
880    self.iter.next().map(|(k, v)| (NodeIndex(*k), v))
881  }
882  fn size_hint(&self) -> (usize, Option<usize>) {
883    self.iter.size_hint()
884  }
885}
886impl<'a, V, I> ExactSizeIterator for NodeIterator<'a, V, I>
887where
888  V: NodeEnum + 'static,
889  I: Iterator<Item = (&'a usize, &'a V)> + ExactSizeIterator + FusedIterator,
890{
891}
892impl<'a, V, I> FusedIterator for NodeIterator<'a, V, I>
893where
894  V: NodeEnum + 'static,
895  I: Iterator<Item = (&'a usize, &'a V)> + ExactSizeIterator + FusedIterator,
896{
897}
898
899/// Type alias to be used in [`mutate`](Transaction::mutate), intented to be used in macros
900pub type MutFunc<'a, T> = Box<dyn FnOnce(&mut T) + 'a>;
901/// Type alias to be used in [`update`](Transaction::update), intented to be used in macros
902pub type UpdateFunc<'a, T> = Box<dyn FnOnce(T) -> T + 'a>;
903
904/// Context for typed graph
905/// Transactions and graph must have the same context to ensure the correctness of NodeIndex
906#[derive(Debug, Clone, Default)]
907pub struct Context {
908  id: Uuid,
909  node_dist: IdDistributer,
910}
911impl Context {
912  /// Create a new context
913  pub fn new() -> Context {
914    Context {
915      id: Uuid::new_v4(),
916      node_dist: IdDistributer::new(),
917    }
918  }
919
920  pub(crate) fn from_id(id: Uuid, cnt: usize) -> Self {
921    Context {
922      id,
923      node_dist: IdDistributer::from_count(cnt),
924    }
925  }
926}
927
928// /// A trait intended to be used in macros
929// pub trait SourceIterator<T: TypedNode + ?Sized>:
930//   Iterator<Item = (NodeIndex, Self::Source)>
931// {
932//   type Source: Copy + Clone + Eq + PartialEq + Debug + Hash + PartialOrd + Ord;
933//   fn new(node: &T) -> Self;
934// }
935
936/// A struct to hold errors found in link type check
937#[derive(Debug, Clone)]
938pub struct LinkTypeError<NodeT: NodeEnum + ?Sized> {
939  pub link: NodeT::LoGMirrorEnum,
940  pub expect: &'static [NodeT::Discriminant],
941  pub found: NodeT::Discriminant,
942}
943
944pub type LinkTypeCheckResult<NodeT> = Result<(), LinkTypeError<NodeT>>;
945
946/// Links that have multiple connects due to bidirecitonal link.
947/// Before commit `x.l = old`. After commit `x.l` will link to `new` while previous link is not cut.
948#[derive(Debug, Clone)]
949pub struct LinkMultiConnectError<NodeT: NodeEnum + ?Sized> {
950  pub x: NodeIndex,
951  pub link: NodeT::LinkMirrorEnum,
952  pub old: NodeIndex,
953  pub new: NodeIndex,
954}
955
956/// Bidirectional link that have multiple choices.
957/// Assume `y.l1 <-> x.l, y.l2 <-> x.l`, a commit added `x.l = y`, while leaving y unchanged.
958/// Then the error will be: `{x, link: l, y, choices: vec![l1, l2]}`
959#[derive(Debug, Clone)]
960pub struct BDLinkMultiChoiceError<NodeT: NodeEnum + ?Sized> {
961  pub x: NodeIndex,
962  pub link: NodeT::LinkMirrorEnum,
963  pub y: NodeIndex,
964  pub choices: Vec<NodeT::LinkMirrorEnum>,
965}
966
967#[derive(Debug, Clone)]
968pub struct CommitError<NodeT: NodeEnum + ?Sized> {
969  pub link_multiconnect: Vec<LinkMultiConnectError<NodeT>>,
970  pub link_type_errors: Vec<LinkTypeError<NodeT>>,
971  pub bdlink_multichoices: Vec<BDLinkMultiChoiceError<NodeT>>,
972  pub custom_node_check: Vec<(String, NodeIndex)>,
973  pub custom_link_add_check: Vec<(String, NodeIndex, NodeIndex)>,
974  pub custom_link_remove_check: Vec<(String, NodeIndex, NodeIndex)>,
975}
976
977impl<NodeT: NodeEnum + ?Sized> CommitError<NodeT> {
978  pub fn is_empty(&self) -> bool {
979    self.link_multiconnect.is_empty()
980      && self.link_type_errors.is_empty()
981      && self.bdlink_multichoices.is_empty()
982      && self.custom_node_check.is_empty()
983      && self.custom_link_add_check.is_empty()
984      && self.custom_link_remove_check.is_empty()
985  }
986}
987
988impl<NodeT: NodeEnum + ?Sized> Default for CommitError<NodeT> {
989  fn default() -> Self {
990    Self {
991      link_multiconnect: Vec::new(),
992      link_type_errors: Vec::new(),
993      bdlink_multichoices: Vec::new(),
994      custom_node_check: Vec::new(),
995      custom_link_add_check: Vec::new(),
996      custom_link_remove_check: Vec::new(),
997    }
998  }
999}
ttgraph/typed_graph.rs

ttgraph/
typed_graph.rs
