21313200008

Committed 24 Jan 2026 09:48AM UTC coverage: 78.882% (+0.04%) from 78.838%

Build # 21313200008

Build Type

push

github

Committed by

TyRoXx

Commit Message

Improve error handling for too many child trees in the database

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

70 existing lines in 6 files now uncovered.

6959 of 8822 relevant lines covered (78.88%)

27915.88 hits per line

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

97.14

/fuzz/fuzz_functions/src/prolly_tree_editable_node_remove.rs

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

#[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,
) -> BlobDigest {
    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_digest = editable_node.save(storage).await.unwrap();
                let reloaded_node: EditableNode<u32, i64> =
                    EditableNode::Reference(TreeReference::new(saved_digest));
                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.tree().children().references() {
        let child_count = Box::pin(count_tree_node_count(child, 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,
) -> BlobDigest {
    let mut editable_node: EditableNode<u32, i64> = EditableNode::new();
    for (key, value) in map.iter() {
        editable_node.insert(*key, *value, storage).await.unwrap();
    }
    let digest = editable_node.save(storage).await.unwrap();
    verify_prolly_tree_equality_to_map(&digest, map, storage).await;
    digest
}

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

TyRoXx / NonlocalityOS / 21313200008

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