iota_types/
accumulator.rs

1// Copyright (c) Mysten Labs, Inc.
2// Modifications Copyright (c) 2024 IOTA Stiftung
3// SPDX-License-Identifier: Apache-2.0
4
5pub type Accumulator = fastcrypto::hash::EllipticCurveMultisetHash;
6
7#[cfg(test)]
8mod tests {
9    use fastcrypto::hash::MultisetHash;
10    use rand::seq::SliceRandom;
11
12    use crate::{accumulator::Accumulator, base_types::ObjectDigest};
13
14    #[test]
15    fn test_accumulator() {
16        let ref1 = ObjectDigest::random();
17        let ref2 = ObjectDigest::random();
18        let ref3 = ObjectDigest::random();
19        let ref4 = ObjectDigest::random();
20
21        let mut a1 = Accumulator::default();
22        a1.insert(ref1);
23        a1.insert(ref2);
24        a1.insert(ref3);
25
26        // Insertion out of order should arrive at the same result.
27        let mut a2 = Accumulator::default();
28        a2.insert(ref3);
29        assert_ne!(a1, a2);
30        a2.insert(ref2);
31        assert_ne!(a1, a2);
32        a2.insert(ref1);
33        assert_eq!(a1, a2);
34
35        // Accumulator is not a set, and inserting the same element twice will change
36        // the result.
37        a2.insert(ref3);
38        assert_ne!(a1, a2);
39        a2.remove(ref3);
40
41        a2.insert(ref4);
42        assert_ne!(a1, a2);
43
44        // Supports removal.
45        a2.remove(ref4);
46        assert_eq!(a1, a2);
47
48        // Removing elements out of order should arrive at the same result.
49        a2.remove(ref3);
50        a2.remove(ref1);
51
52        a1.remove(ref1);
53        a1.remove(ref3);
54
55        assert_eq!(a1, a2);
56
57        // After removing all elements, it should be the same as an empty one.
58        a1.remove(ref2);
59        assert_eq!(a1, Accumulator::default());
60    }
61
62    #[test]
63    fn test_accumulator_commutativity() {
64        let ref1 = ObjectDigest::random();
65        let ref2 = ObjectDigest::random();
66        let ref3 = ObjectDigest::random();
67
68        let mut a1 = Accumulator::default();
69        a1.remove(ref1);
70        a1.remove(ref2);
71        a1.insert(ref1);
72        a1.insert(ref2);
73
74        // Removal before insertion should yield the same result
75        assert_eq!(a1, Accumulator::default());
76
77        a1.insert(ref1);
78        a1.insert(ref2);
79
80        // Insertion out of order should arrive at the same result.
81        let mut a2 = Accumulator::default();
82        a2.remove(ref1);
83        a2.remove(ref2);
84
85        // Unioning where all objects from a are removed in b should
86        // result in empty accumulator
87        a1.union(&a2);
88        assert_eq!(a1, Accumulator::default());
89
90        a1.insert(ref1);
91        a1.insert(ref2);
92        a1.insert(ref3);
93
94        let mut a3 = Accumulator::default();
95        a3.insert(ref3);
96
97        // a1: (+ref1, +ref2, +ref3)
98        // a2: (-ref1, -ref2)
99        // a3: (+ref3)
100        // a1 + a2 = a3
101
102        a1.union(&a2);
103        assert_eq!(a1, a3);
104    }
105
106    #[test]
107    fn test_accumulator_insert_stress() {
108        let mut refs: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
109        let mut accumulator = Accumulator::default();
110        accumulator.insert_all(&refs);
111        let mut rng = rand::thread_rng();
112        (0..10).for_each(|_| {
113            refs.shuffle(&mut rng);
114            let mut a = Accumulator::default();
115            a.insert_all(&refs);
116            assert_eq!(accumulator, a);
117        })
118    }
119
120    #[test]
121    fn test_accumulator_remove_stress() {
122        let mut refs1: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
123        let mut refs2: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
124        let mut accumulator = Accumulator::default();
125        accumulator.insert_all(&refs1);
126
127        let mut rng = rand::thread_rng();
128        (0..10).for_each(|_| {
129            refs1.shuffle(&mut rng);
130            let mut a = Accumulator::default();
131            a.insert_all(&refs1);
132            a.insert_all(&refs2);
133            refs2.shuffle(&mut rng);
134            a.remove_all(&refs2);
135            assert_eq!(accumulator, a);
136        })
137    }
138}
iota_types/accumulator.rs

iota_types/
accumulator.rs
