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

// Copyright © 2021 The Radicle Link Contributors
#![allow(clippy::too_many_arguments)]
use std::{cmp::Ordering, collections::BTreeSet, ops::ControlFlow};

use git_ext::Oid;
use radicle_dag::Dag;

pub use crate::change::{Contents, Entry, EntryId, Timestamp};

/// The DAG of changes making up the history of a collaborative object.
#[derive(Clone, Debug)]
pub struct History {
    graph: Dag<EntryId, Entry>,
    root: EntryId,
}

impl PartialEq for History {
    fn eq(&self, other: &Self) -> bool {
        self.tips() == other.tips()
    }
}

impl Eq for History {}

impl History {
    /// Create a new history from a DAG. Panics if the root is not part of the graph.
    pub fn new(root: EntryId, graph: Dag<EntryId, Entry>) -> Self {
        assert!(
            graph.contains(&root),
            "History::new: root must be present in graph"
        );
        Self { root, graph }
    }

    /// Create a new history from a root entry.
    pub fn new_from_root(root: Entry) -> Self {
        let id = *root.id();

        Self::new(id, Dag::root(id, root))
    }

    /// Get all the tips of the graph.
    pub fn tips(&self) -> BTreeSet<Oid> {
        self.graph.tips().map(|(_, entry)| *entry.id()).collect()
    }

    /// A topological (parents before children) traversal of the dependency
    /// graph of this history. This is analagous to
    /// [`std::iter::Iterator::fold`] in that it folds every change into an
    /// accumulator value of type `A`. However, unlike `fold` the function `f`
    /// may prune branches from the dependency graph by returning
    /// `ControlFlow::Break`.
    pub fn traverse<F, A>(&self, init: A, roots: &[EntryId], mut f: F) -> A
    where
        F: for<'r> FnMut(A, &'r EntryId, &'r Entry) -> ControlFlow<A, A>,
    {
        self.graph.fold(roots, init, |acc, k, v| f(acc, k, v))
    }

    /// Return a topologically-sorted list of history entries.
    pub fn sorted<F>(&self, compare: F) -> impl Iterator<Item = &Entry>
    where
        F: FnMut(&EntryId, &EntryId) -> Ordering,
    {
        self.graph
            .sorted_by(compare)
            .into_iter()
            .filter_map(|k| self.graph.get(&k))
            .map(|node| &node.value)
    }

    /// Extend this history with a new entry.
    pub fn extend(&mut self, change: Entry) {
        let tips = self.tips();
        let id = *change.id();

        self.graph.node(id, change);

        for tip in tips {
            self.graph.dependency(id, (*tip).into());
        }
    }

    /// Merge two histories.
    pub fn merge(&mut self, other: Self) {
        self.graph.merge(other.graph);
    }

    /// Get the number of history entries.
    pub fn len(&self) -> usize {
        self.graph.len()
    }

    /// Check if the graph is empty.
    pub fn is_empty(&self) -> bool {
        self.graph.is_empty()
    }

    /// Get the underlying graph
    pub fn graph(&self) -> &Dag<EntryId, Entry> {
        &self.graph
    }

    /// Get the root entry.
    pub fn root(&self) -> &Entry {
        // SAFETY: We don't allow construction of histories without a root.
        self.graph
            .get(&self.root)
            .expect("History::root: the root entry must be present in the graph")
    }

    /// Get the children of the given entry.
    pub fn children_of(&self, id: &EntryId) -> Vec<EntryId> {
        self.graph
            .get(id)
            .map(|n| n.dependents.iter().cloned().collect())
            .unwrap_or_default()
    }
}