radicle_cob/
history.rs

1// Copyright © 2021 The Radicle Link Contributors
2#![allow(clippy::too_many_arguments)]
3use std::{cmp::Ordering, collections::BTreeSet, ops::ControlFlow};
4
5use git_ext::Oid;
6use radicle_dag::Dag;
7
8pub use crate::change::{Contents, Entry, EntryId, Timestamp};
9
10/// The DAG of changes making up the history of a collaborative object.
11#[derive(Clone, Debug)]
12pub struct History {
13    graph: Dag<EntryId, Entry>,
14    root: EntryId,
15}
16
17impl PartialEq for History {
18    fn eq(&self, other: &Self) -> bool {
19        self.tips() == other.tips()
20    }
21}
22
23impl Eq for History {}
24
25impl History {
26    /// Create a new history from a DAG. Panics if the root is not part of the graph.
27    pub fn new(root: EntryId, graph: Dag<EntryId, Entry>) -> Self {
28        assert!(
29            graph.contains(&root),
30            "History::new: root must be present in graph"
31        );
32        Self { root, graph }
33    }
34
35    /// Create a new history from a root entry.
36    pub fn new_from_root(root: Entry) -> Self {
37        let id = *root.id();
38
39        Self::new(id, Dag::root(id, root))
40    }
41
42    /// Get all the tips of the graph.
43    pub fn tips(&self) -> BTreeSet<Oid> {
44        self.graph.tips().map(|(_, entry)| *entry.id()).collect()
45    }
46
47    /// A topological (parents before children) traversal of the dependency
48    /// graph of this history. This is analagous to
49    /// [`std::iter::Iterator::fold`] in that it folds every change into an
50    /// accumulator value of type `A`. However, unlike `fold` the function `f`
51    /// may prune branches from the dependency graph by returning
52    /// `ControlFlow::Break`.
53    pub fn traverse<F, A>(&self, init: A, roots: &[EntryId], mut f: F) -> A
54    where
55        F: for<'r> FnMut(A, &'r EntryId, &'r Entry) -> ControlFlow<A, A>,
56    {
57        self.graph.fold(roots, init, |acc, k, v| f(acc, k, v))
58    }
59
60    /// Return a topologically-sorted list of history entries.
61    pub fn sorted<F>(&self, compare: F) -> impl Iterator<Item = &Entry>
62    where
63        F: FnMut(&EntryId, &EntryId) -> Ordering,
64    {
65        self.graph
66            .sorted_by(compare)
67            .into_iter()
68            .filter_map(|k| self.graph.get(&k))
69            .map(|node| &node.value)
70    }
71
72    /// Extend this history with a new entry.
73    pub fn extend(&mut self, change: Entry) {
74        let tips = self.tips();
75        let id = *change.id();
76
77        self.graph.node(id, change);
78
79        for tip in tips {
80            self.graph.dependency(id, (*tip).into());
81        }
82    }
83
84    /// Merge two histories.
85    pub fn merge(&mut self, other: Self) {
86        self.graph.merge(other.graph);
87    }
88
89    /// Get the number of history entries.
90    pub fn len(&self) -> usize {
91        self.graph.len()
92    }
93
94    /// Check if the graph is empty.
95    pub fn is_empty(&self) -> bool {
96        self.graph.is_empty()
97    }
98
99    /// Get the underlying graph
100    pub fn graph(&self) -> &Dag<EntryId, Entry> {
101        &self.graph
102    }
103
104    /// Get the root entry.
105    pub fn root(&self) -> &Entry {
106        // SAFETY: We don't allow construction of histories without a root.
107        self.graph
108            .get(&self.root)
109            .expect("History::root: the root entry must be present in the graph")
110    }
111
112    /// Get the children of the given entry.
113    pub fn children_of(&self, id: &EntryId) -> Vec<EntryId> {
114        self.graph
115            .get(id)
116            .map(|n| n.dependents.iter().cloned().collect())
117            .unwrap_or_default()
118    }
119}
radicle_cob/history.rs

radicle_cob/
history.rs
