22054564584

Committed 16 Feb 2026 07:58AM UTC coverage: 78.266% (+0.2%) from 78.043%

Build # 22054564584

Build Type

Pull #418

github

Committed by

web-flow

Commit Message

Merge 1081fc4c7 into e3367509b

Pull Request Pull Request #418: Fix: Sometimes the storage garbage collector appears to collect new trees that are still needed

Run Details

737 of 845 new or added lines in 29 files covered. (87.22%)

57 existing lines in 6 files now uncovered.

7321 of 9354 relevant lines covered (78.27%)

26486.75 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.37

/fuzz/fuzz_functions/src/prolly_tree_editable_node_remove.rs

use arbitrary::{Arbitrary, Unstructured};
use astraea::{
    in_memory_storage::InMemoryTreeStorage,
    storage::{LoadTree, StrongReference},
    tree::BlobDigest,
};
use pretty_assertions::assert_eq;
use sorted_tree::prolly_tree_editable_node::EditableNode;
use std::collections::BTreeMap;

#[derive(Arbitrary, Debug)]
enum MapOperation {
    Insert(u32, i64),
    Remove(u32),
    Save,
}

#[derive(Arbitrary, Debug)]
struct TestCase {
    before: BTreeMap<u32, i64>,
    after: BTreeMap<u32, i64>,
    operations: Vec<MapOperation>,
}

fn find_operations_to_transform(
    before: &BTreeMap<u32, i64>,
    after: &BTreeMap<u32, i64>,
) -> Vec<MapOperation> {
    let mut operations = Vec::new();
    for (key, value) in after.iter() {
        match before.get(key) {
            Some(existing_value) => {
                if existing_value != value {
                    operations.push(MapOperation::Insert(*key, *value));
                }
            }
            None => {
                operations.push(MapOperation::Insert(*key, *value));
            }
        }
    }
    for key in before.keys() {
        if !after.contains_key(key) {
            operations.push(MapOperation::Remove(*key));
        }
    }
    operations
}

async fn execute_operations_on_prolly_tree(
    digest: &BlobDigest,
    operations: &[MapOperation],
    storage: &InMemoryTreeStorage,
) -> StrongReference {
    let mut editable_node: EditableNode<u32, i64> =
        EditableNode::load(digest, storage).await.unwrap();
    let mut oracle = BTreeMap::new();
    for operation in operations {
        match operation {
            MapOperation::Insert(key, value) => {
                editable_node.insert(*key, *value, storage).await.unwrap();
                oracle.insert(*key, *value);
            }
            MapOperation::Remove(key) => {
                editable_node.remove(key, storage).await.unwrap();
                oracle.remove(key);
            }
            MapOperation::Save => {
                let saved_reference = editable_node.save(storage).await.unwrap();
                let reloaded_node: EditableNode<u32, i64> =
                    EditableNode::Reference(saved_reference);
                editable_node = reloaded_node;
            }
        }
    }
    editable_node.save(storage).await.unwrap()
}

fn execute_operations_on_btree_map(map: &mut BTreeMap<u32, i64>, operations: &[MapOperation]) {
    for operation in operations {
        match operation {
            MapOperation::Insert(key, value) => {
                map.insert(*key, *value);
            }
            MapOperation::Remove(key) => {
                map.remove(key);
            }
            MapOperation::Save => {}
        }
    }
}

async fn verify_prolly_tree_equality_to_map(
    digest: &BlobDigest,
    map: &BTreeMap<u32, i64>,
    storage: &InMemoryTreeStorage,
) {
    let mut editable_node: EditableNode<u32, i64> =
        EditableNode::load(digest, storage).await.unwrap();
    for (key, value) in map.iter() {
        let found = editable_node.find(key, storage).await.unwrap();
        assert_eq!(Some(*value), found);
    }
    let count = editable_node.count(storage).await.unwrap();
    assert_eq!(map.len() as u64, count);
}

async fn count_tree_node_count(root: &BlobDigest, storage: &InMemoryTreeStorage) -> u64 {
    let loaded = storage.load_tree(root).await.unwrap();
    let hashed = loaded.hash().unwrap();
    let mut sum = 1;
    for child in hashed.hashed_tree().tree().children().references() {
        let child_count = Box::pin(count_tree_node_count(child.digest(), storage)).await;
        sum += child_count;
    }
    sum
}

async fn verify_prolly_trees_equal(
    digest1: &BlobDigest,
    digest2: &BlobDigest,
    storage: &InMemoryTreeStorage,
) {
    let mut editable_node1: EditableNode<u32, i64> =
        EditableNode::load(digest1, storage).await.unwrap();
    let mut editable_node2: EditableNode<u32, i64> =
        EditableNode::load(digest2, storage).await.unwrap();
    let element_count1 = editable_node1.count(storage).await.unwrap();
    let element_count2 = editable_node2.count(storage).await.unwrap();
    assert_eq!(element_count1, element_count2);
    let node_count1 = count_tree_node_count(digest1, storage).await;
    let node_count2 = count_tree_node_count(digest2, storage).await;
    assert_eq!(node_count1, node_count2);
    assert_eq!(digest1, digest2);
}

async fn btree_map_to_digest(
    map: &BTreeMap<u32, i64>,
    storage: &InMemoryTreeStorage,
) -> StrongReference {
    let mut editable_node: EditableNode<u32, i64> = EditableNode::new();
    for (key, value) in map.iter() {
        editable_node.insert(*key, *value, storage).await.unwrap();
    }
    let reference = editable_node.save(storage).await.unwrap();
    verify_prolly_tree_equality_to_map(reference.digest(), map, storage).await;
    reference
}

async fn run_test_case(test_case: &TestCase) {
    let intermediary_map = {
        let mut map = test_case.before.clone();
        execute_operations_on_btree_map(&mut map, &test_case.operations);
        map
    };
    let additional_operations = find_operations_to_transform(&intermediary_map, &test_case.after);
    let final_map = {
        let mut map = intermediary_map.clone();
        execute_operations_on_btree_map(&mut map, &additional_operations);
        map
    };
    assert_eq!(final_map, test_case.after);
    let storage = InMemoryTreeStorage::empty();
    let before_digest = btree_map_to_digest(&test_case.before, &storage).await;
    let operations_executed =
        execute_operations_on_prolly_tree(before_digest.digest(), &test_case.operations, &storage)
            .await;
    if test_case.operations.is_empty() {
        verify_prolly_trees_equal(
            before_digest.digest(),
            operations_executed.digest(),
            &storage,
        )
        .await;
    }
    verify_prolly_tree_equality_to_map(operations_executed.digest(), &intermediary_map, &storage)
        .await;
    let additional_operations_executed = execute_operations_on_prolly_tree(
        operations_executed.digest(),
        &additional_operations,
        &storage,
    )
    .await;
    if additional_operations.is_empty() {
        verify_prolly_trees_equal(
            operations_executed.digest(),
            additional_operations_executed.digest(),
            &storage,
        )
        .await;
    }
    let after_digest = btree_map_to_digest(&test_case.after, &storage).await;
    verify_prolly_tree_equality_to_map(after_digest.digest(), &final_map, &storage).await;
    verify_prolly_trees_equal(
        after_digest.digest(),
        additional_operations_executed.digest(),
        &storage,
    )
    .await;
}

pub fn fuzz_function(data: &[u8]) -> bool {
    let mut unstructured = Unstructured::new(data);
    let test_case: TestCase = match unstructured.arbitrary() {
        Ok(success) => success,
        Err(_) => return false,
    };
    tokio::runtime::Builder::new_current_thread()
        .build()
        .unwrap()
        .block_on(async {
            run_test_case(&test_case).await;
        });
    true
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_empty() {
    run_test_case(&TestCase {
        before: BTreeMap::new(),
        after: BTreeMap::new(),
        operations: vec![],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_no_operations() {
    run_test_case(&TestCase {
        before: BTreeMap::new(),
        after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
        operations: vec![],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_matching_operations() {
    run_test_case(&TestCase {
        before: BTreeMap::new(),
        after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
        operations: vec![
            MapOperation::Insert(10, 100),
            MapOperation::Insert(20, 200),
            MapOperation::Insert(30, 300),
        ],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_mismatching_operations() {
    run_test_case(&TestCase {
        before: BTreeMap::new(),
        after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
        operations: vec![
            MapOperation::Insert(10, 100),
            MapOperation::Insert(40, 200),
            MapOperation::Insert(30, 400),
        ],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_save_operation() {
    run_test_case(&TestCase {
        before: BTreeMap::new(),
        after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
        operations: vec![
            MapOperation::Insert(10, 100),
            MapOperation::Insert(20, 200),
            MapOperation::Save,
            MapOperation::Insert(30, 300),
        ],
    })
    .await;
}

#[cfg(test)]
#[test_log::test]
fn test_crash_0() {
    fuzz_function(&[
        201, 255, 255, 219, 89, 89, 67, 75, 73, 89, 75, 240, 67, 243, 102, 0, 219, 170, 67, 75, 89,
        32, 240, 89, 67, 75, 33, 89, 75, 240, 67, 243, 32, 191, 157, 40, 255, 0, 255, 1, 149, 25,
        255, 255, 255, 0, 0, 255, 255, 58, 255, 43, 43, 154, 202, 0, 43, 43, 43, 43, 43, 43, 43,
        43, 43, 43, 43, 43, 43, 43, 43, 43, 255, 255, 239, 32, 75, 219, 89, 89, 241, 241, 255, 255,
        255, 255, 255, 255, 255, 255, 255, 255, 127, 255, 255, 255, 255, 225, 255, 255, 255, 255,
        46, 255, 93, 255, 254, 59, 253, 88, 255, 255, 46, 255, 93, 241, 241, 241, 241, 241, 243,
        241, 241, 219, 89, 89, 67, 75, 89, 0, 60, 255,
    ]);
}

1	use arbitrary::{Arbitrary, Unstructured};
2	use astraea::{
3	in_memory_storage::InMemoryTreeStorage,
4	storage::{LoadTree, StrongReference},
5	tree::BlobDigest,
6	};
7	use pretty_assertions::assert_eq;
8	use sorted_tree::prolly_tree_editable_node::EditableNode;
9	use std::collections::BTreeMap;
10
11	#[derive(Arbitrary, Debug)]
12	enum MapOperation {
13	Insert(u32, i64),
14	Remove(u32),
15	Save,
16	}
17
18	#[derive(Arbitrary, Debug)]
19	struct TestCase {
20	before: BTreeMap<u32, i64>,
21	after: BTreeMap<u32, i64>,
22	operations: Vec<MapOperation>,
23	}
24
25	fn find_operations_to_transform(	6✔
26	before: &BTreeMap<u32, i64>,
27	after: &BTreeMap<u32, i64>,
28	) -> Vec<MapOperation> {
29	let mut operations = Vec::new();	12✔
30	for (key, value) in after.iter() {	38✔
31	match before.get(key) {	26✔
32	Some(existing_value) => {	8✔
33	if existing_value != value {	9✔
34	operations.push(MapOperation::Insert(key, value));	3✔
35	}
36	}
37	None => {	5✔
38	operations.push(MapOperation::Insert(key, value));	15✔
39	}
40	}
41	}
42	for key in before.keys() {	31✔
43	if !after.contains_key(key) {	49✔
44	operations.push(MapOperation::Remove(*key));	22✔
45	}
46	}
47	operations	6✔
48	}
49
50	async fn execute_operations_on_prolly_tree(	12✔
51	digest: &BlobDigest,
52	operations: &[MapOperation],
53	storage: &InMemoryTreeStorage,
54	) -> StrongReference {
55	let mut editable_node: EditableNode<u32, i64> =	24✔
56	EditableNode::load(digest, storage).await.unwrap();	48✔
57	let mut oracle = BTreeMap::new();	24✔
58	for operation in operations {	39✔
59	match operation {	27✔
60	MapOperation::Insert(key, value) => {	30✔
61	editable_node.insert(key, value, storage).await.unwrap();	90✔
62	oracle.insert(key, value);	60✔
63	}
64	MapOperation::Remove(key) => {	11✔
65	editable_node.remove(key, storage).await.unwrap();	55✔
66	oracle.remove(key);	33✔
67	}
68	MapOperation::Save => {
69	let saved_reference = editable_node.save(storage).await.unwrap();	5✔
70	let reloaded_node: EditableNode<u32, i64> =	2✔
71	EditableNode::Reference(saved_reference);	1✔
72	editable_node = reloaded_node;	2✔
73	}
74	}
75	}
76	editable_node.save(storage).await.unwrap()	48✔
77	}
78
79	fn execute_operations_on_btree_map(map: &mut BTreeMap<u32, i64>, operations: &[MapOperation]) {	12✔
80	for operation in operations {	39✔
81	match operation {	27✔
82	MapOperation::Insert(key, value) => {	45✔
83	map.insert(key, value);	45✔
84	}
85	MapOperation::Remove(key) => {	22✔
86	map.remove(key);	22✔
87	}
88	MapOperation::Save => {}	1✔
89	}
90	}
91	}
92
93	async fn verify_prolly_tree_equality_to_map(	24✔
94	digest: &BlobDigest,
95	map: &BTreeMap<u32, i64>,
96	storage: &InMemoryTreeStorage,
97	) {
98	let mut editable_node: EditableNode<u32, i64> =	48✔
99	EditableNode::load(digest, storage).await.unwrap();	96✔
100	for (key, value) in map.iter() {	158✔
101	let found = editable_node.find(key, storage).await.unwrap();	330✔
102	assert_eq!(Some(*value), found);
103	}
104	let count = editable_node.count(storage).await.unwrap();	120✔
105	assert_eq!(map.len() as u64, count);
106	}
107
108	async fn count_tree_node_count(root: &BlobDigest, storage: &InMemoryTreeStorage) -> u64 {	48✔
109	let loaded = storage.load_tree(root).await.unwrap();	120✔
110	let hashed = loaded.hash().unwrap();	96✔
111	let mut sum = 1;	48✔
112	for child in hashed.hashed_tree().tree().children().references() {	48✔
NEW 113	let child_count = Box::pin(count_tree_node_count(child.digest(), storage)).await;	×
UNCOV 114	sum += child_count;	×
115	}
116	sum	24✔
117	}
118
119	async fn verify_prolly_trees_equal(	12✔
120	digest1: &BlobDigest,
121	digest2: &BlobDigest,
122	storage: &InMemoryTreeStorage,
123	) {
124	let mut editable_node1: EditableNode<u32, i64> =	24✔
125	EditableNode::load(digest1, storage).await.unwrap();	48✔
126	let mut editable_node2: EditableNode<u32, i64> =	24✔
127	EditableNode::load(digest2, storage).await.unwrap();	48✔
128	let element_count1 = editable_node1.count(storage).await.unwrap();	60✔
129	let element_count2 = editable_node2.count(storage).await.unwrap();	60✔
130	assert_eq!(element_count1, element_count2);
131	let node_count1 = count_tree_node_count(digest1, storage).await;	48✔
132	let node_count2 = count_tree_node_count(digest2, storage).await;	48✔
133	assert_eq!(node_count1, node_count2);
134	assert_eq!(digest1, digest2);
135	}
136
137	async fn btree_map_to_digest(	12✔
138	map: &BTreeMap<u32, i64>,
139	storage: &InMemoryTreeStorage,
140	) -> StrongReference {
141	let mut editable_node: EditableNode<u32, i64> = EditableNode::new();	36✔
142	for (key, value) in map.iter() {	70✔
143	editable_node.insert(key, value, storage).await.unwrap();	138✔
144	}
145	let reference = editable_node.save(storage).await.unwrap();	60✔
146	verify_prolly_tree_equality_to_map(reference.digest(), map, storage).await;	48✔
147	reference	12✔
148	}
149
150	async fn run_test_case(test_case: &TestCase) {	12✔
151	let intermediary_map = {	6✔
152	let mut map = test_case.before.clone();	18✔
153	execute_operations_on_btree_map(&mut map, &test_case.operations);	18✔
154	map	6✔
155	};
156	let additional_operations = find_operations_to_transform(&intermediary_map, &test_case.after);	24✔
157	let final_map = {	6✔
158	let mut map = intermediary_map.clone();	18✔
159	execute_operations_on_btree_map(&mut map, &additional_operations);	18✔
160	map	6✔
161	};
162	assert_eq!(final_map, test_case.after);
163	let storage = InMemoryTreeStorage::empty();	12✔
164	let before_digest = btree_map_to_digest(&test_case.before, &storage).await;	24✔
165	let operations_executed =	6✔
166	execute_operations_on_prolly_tree(before_digest.digest(), &test_case.operations, &storage)	24✔
167	.await;	6✔
168	if test_case.operations.is_empty() {	12✔
169	verify_prolly_trees_equal(
170	before_digest.digest(),	6✔
171	operations_executed.digest(),	6✔
172	&storage,	3✔
173	)
174	.await;	3✔
175	}
176	verify_prolly_tree_equality_to_map(operations_executed.digest(), &intermediary_map, &storage)	24✔
177	.await;	6✔
178	let additional_operations_executed = execute_operations_on_prolly_tree(
179	operations_executed.digest(),	12✔
180	&additional_operations,	12✔
181	&storage,	6✔
182	)
183	.await;	6✔
184	if additional_operations.is_empty() {	12✔
185	verify_prolly_trees_equal(
186	operations_executed.digest(),	6✔
187	additional_operations_executed.digest(),	6✔
188	&storage,	3✔
189	)
190	.await;	3✔
191	}
192	let after_digest = btree_map_to_digest(&test_case.after, &storage).await;	24✔
193	verify_prolly_tree_equality_to_map(after_digest.digest(), &final_map, &storage).await;	24✔
194	verify_prolly_trees_equal(
195	after_digest.digest(),	12✔
196	additional_operations_executed.digest(),	12✔
197	&storage,	6✔
198	)
199	.await;	6✔
200	}
201
202	pub fn fuzz_function(data: &[u8]) -> bool {	1✔
203	let mut unstructured = Unstructured::new(data);	3✔
204	let test_case: TestCase = match unstructured.arbitrary() {	3✔
205	Ok(success) => success,	2✔
206	Err(_) => return false,	×
207	};
208	tokio::runtime::Builder::new_current_thread()	2✔
209	.build()
210	.unwrap()
211	.block_on(async {	2✔
212	run_test_case(&test_case).await;	2✔
213	});
214	true	1✔
215	}
216
217	#[cfg(test)]
218	#[test_log::test(tokio::test)]
219	async fn test_empty() {
220	run_test_case(&TestCase {
221	before: BTreeMap::new(),
222	after: BTreeMap::new(),
223	operations: vec![],
224	})
225	.await;
226	}
227
228	#[cfg(test)]
229	#[test_log::test(tokio::test)]
230	async fn test_no_operations() {
231	run_test_case(&TestCase {
232	before: BTreeMap::new(),
233	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
234	operations: vec![],
235	})
236	.await;
237	}
238
239	#[cfg(test)]
240	#[test_log::test(tokio::test)]
241	async fn test_matching_operations() {
242	run_test_case(&TestCase {
243	before: BTreeMap::new(),
244	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
245	operations: vec![
246	MapOperation::Insert(10, 100),
247	MapOperation::Insert(20, 200),
248	MapOperation::Insert(30, 300),
249	],
250	})
251	.await;
252	}
253
254	#[cfg(test)]
255	#[test_log::test(tokio::test)]
256	async fn test_mismatching_operations() {
257	run_test_case(&TestCase {
258	before: BTreeMap::new(),
259	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
260	operations: vec![
261	MapOperation::Insert(10, 100),
262	MapOperation::Insert(40, 200),
263	MapOperation::Insert(30, 400),
264	],
265	})
266	.await;
267	}
268
269	#[cfg(test)]
270	#[test_log::test(tokio::test)]
271	async fn test_save_operation() {
272	run_test_case(&TestCase {
273	before: BTreeMap::new(),
274	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
275	operations: vec![
276	MapOperation::Insert(10, 100),
277	MapOperation::Insert(20, 200),
278	MapOperation::Save,
279	MapOperation::Insert(30, 300),
280	],
281	})
282	.await;
283	}
284
285	#[cfg(test)]
286	#[test_log::test]
287	fn test_crash_0() {
288	fuzz_function(&[
289	201, 255, 255, 219, 89, 89, 67, 75, 73, 89, 75, 240, 67, 243, 102, 0, 219, 170, 67, 75, 89,
290	32, 240, 89, 67, 75, 33, 89, 75, 240, 67, 243, 32, 191, 157, 40, 255, 0, 255, 1, 149, 25,
291	255, 255, 255, 0, 0, 255, 255, 58, 255, 43, 43, 154, 202, 0, 43, 43, 43, 43, 43, 43, 43,
292	43, 43, 43, 43, 43, 43, 43, 43, 43, 255, 255, 239, 32, 75, 219, 89, 89, 241, 241, 255, 255,
293	255, 255, 255, 255, 255, 255, 255, 255, 127, 255, 255, 255, 255, 225, 255, 255, 255, 255,
294	46, 255, 93, 255, 254, 59, 253, 88, 255, 255, 46, 255, 93, 241, 241, 241, 241, 241, 243,
295	241, 241, 219, 89, 89, 67, 75, 89, 0, 60, 255,
296	]);
297	}

TyRoXx / NonlocalityOS / 22054564584

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous