diamond_types/list/
check.rs

1use jumprope::JumpRope;
2use crate::list::{Branch, ListCRDT, OpLog};
3use smallvec::smallvec;
4use crate::frontier::{advance_frontier_by_known_run, clone_smallvec, debug_assert_frontier_sorted};
5use crate::history::History;
6use crate::LocalVersion;
7
8/// This file contains debugging assertions to validate the document's internal state.
9///
10/// This is used during fuzzing to make sure everything is working properly, and if not, find bugs
11/// as early as possible.
12
13impl Branch {
14    #[allow(unused)]
15    pub fn dbg_assert_content_eq_rope(&self, expected_content: &JumpRope) {
16        assert_eq!(&self.content, expected_content);
17    }
18
19
20}
21
22impl OpLog {
23    fn get_frontier_inefficiently(&self) -> LocalVersion {
24        // Could improve this by just looking at the last txn, and following shadows down.
25
26        let mut b = smallvec![];
27        for txn in self.history.entries.iter() {
28            advance_frontier_by_known_run(&mut b, txn.parents.as_slice(), txn.span);
29        }
30        b
31    }
32
33    /// Check the internal state of the diamond types list. This is only exported for integration
34    /// testing.
35    ///
36    /// You shouldn't have any reason to call this method.
37    ///
38    /// This method is public, but do not depend on it as part of the DT API. It could be removed at
39    /// any time.
40    #[allow(unused)]
41    pub fn dbg_check(&self, deep: bool) {
42        let actual_frontier = self.get_frontier_inefficiently();
43        assert_eq!(self.version, actual_frontier);
44
45        if deep {
46            self.history.check();
47        }
48    }
49
50    #[allow(unused)]
51    pub(crate) fn check_all_changes_rle_merged(&self) {
52        assert_eq!(self.client_data[0].item_times.num_entries(), 1);
53        // .. And operation log.
54        assert_eq!(self.history.entries.num_entries(), 1);
55    }
56}
57
58impl ListCRDT {
59    /// Check the internal state of the diamond types document. This is only exported for
60    /// integration testing.
61    ///
62    /// You shouldn't have any reason to call this method.
63    ///
64    /// This method is public, but do not depend on it as part of the DT API. It could be removed at
65    /// any time.
66    #[allow(unused)]
67    pub fn dbg_check(&self, deep: bool) {
68        self.oplog.dbg_check(deep);
69    }
70}
71
72impl History {
73    fn check(&self) {
74        self.entries.check_packed();
75
76        let expect_root_children = self.entries
77        .iter()
78        .enumerate()
79        .filter_map(|(i, entry)| {
80            if entry.parents.is_empty() {
81                Some(i)
82            } else { None }
83        });
84        assert!(expect_root_children.eq(self.root_child_indexes.iter().copied()));
85
86        // The shadow entries in txns name the smallest order for which all txns from
87        // [shadow..txn.order] are transitive parents of the current txn.
88
89        // I'm testing here sort of by induction. Iterating the txns in order allows us to assume
90        // all previous txns have valid shadows while we advance.
91
92        for (idx, hist) in self.entries.iter().enumerate() {
93            assert!(hist.span.end > hist.span.start);
94
95            debug_assert_frontier_sorted(&hist.parents);
96
97            // We contain prev_txn_order *and more*! See if we can extend the shadow by
98            // looking at the other entries of parents.
99            let mut parents = clone_smallvec(&hist.parents);
100            let mut expect_shadow = hist.span.start;
101
102            // The first txn *must* have ROOT as a parent, so 0 should never show up in shadow.
103            assert_ne!(hist.shadow, 0);
104
105            // Check our child_indexes all contain this item in their parents list.
106            for child_idx in &hist.child_indexes {
107                let child = &self.entries.0[*child_idx];
108                assert!(child.parents.iter().any(|p| hist.contains(*p)));
109            }
110
111            if parents.is_empty() {
112                if hist.span.start == 0 { expect_shadow = usize::MAX; }
113                // assert!(hist.parent_indexes.is_empty());
114            } else {
115                // We'll resort parents into descending order.
116                parents.sort_unstable_by(|a, b| b.cmp(a)); // descending order
117
118                // By induction, we can assume the previous shadows are correct.
119                for parent_order in parents {
120                    // Note parent_order could point in the middle of a txn run.
121                    let parent_idx = self.entries.find_index(parent_order).unwrap();
122                    let parent_txn = &self.entries.0[parent_idx];
123                    let offs = parent_order - parent_txn.span.start;
124
125                    // Check the parent txn names this txn in its child_indexes
126                    assert!(parent_txn.child_indexes.contains(&idx));
127
128                    // dbg!(parent_txn.order + offs, expect_shadow);
129                    // Shift it if the expected shadow points to the last item in the txn run.
130                    if parent_txn.span.start + offs + 1 == expect_shadow {
131                        expect_shadow = parent_txn.shadow;
132                    }
133                }
134            }
135
136            assert_eq!(hist.shadow, expect_shadow);
137        }
138    }
139}
diamond_types/list/check.rs

diamond_types/list/
check.rs
