20003570228

Committed 07 Dec 2025 11:31AM UTC coverage: 80.214% (+0.5%) from 79.756%

Build # 20003570228

Build Type

push

github

Committed by

TyRoXx

Commit Message

Design a new prolly tree API that will make normalization easier to implement

Run Details

568 of 617 new or added lines in 4 files covered. (92.06%)

3 existing lines in 1 file now uncovered.

5400 of 6732 relevant lines covered (80.21%)

33555.09 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::{
    storage::{InMemoryTreeStorage, 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 size = editable_node.size(storage).await.unwrap();
    assert_eq!(map.len() as u64, size);
}

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().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 size1 = editable_node1.size(storage).await.unwrap();
    let size2 = editable_node2.size(storage).await.unwrap();
    assert_eq!(size1, size2);
    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 = astraea::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::{
3	storage::{InMemoryTreeStorage, LoadTree},
4	tree::BlobDigest,
5	};
6	use pretty_assertions::assert_eq;
7	use sorted_tree::{prolly_tree_editable_node::EditableNode, sorted_tree::TreeReference};
8	use std::collections::BTreeMap;
9	use tokio::sync::Mutex;
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	) -> BlobDigest {
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 {	66✔
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_digest = editable_node.save(storage).await.unwrap();	5✔
70	let reloaded_node: EditableNode<u32, i64> =	2✔
71	EditableNode::Reference(TreeReference::new(saved_digest));	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 {	66✔
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 size = editable_node.size(storage).await.unwrap();	120✔
105	assert_eq!(map.len() as u64, size);
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.tree().references() {	48✔
NEW 113	let child_count = Box::pin(count_tree_node_count(child, storage)).await;	×
NEW 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 size1 = editable_node1.size(storage).await.unwrap();	60✔
129	let size2 = editable_node2.size(storage).await.unwrap();	60✔
130	assert_eq!(size1, size2);
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	) -> BlobDigest {
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 digest = editable_node.save(storage).await.unwrap();	60✔
146	verify_prolly_tree_equality_to_map(&digest, map, storage).await;	48✔
147	digest	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 = astraea::storage::InMemoryTreeStorage::new(Mutex::new(BTreeMap::new()));	24✔
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, &test_case.operations, &storage).await;	24✔
167	if test_case.operations.is_empty() {	12✔
168	verify_prolly_trees_equal(&before_digest, &operations_executed, &storage).await;	12✔
169	}
170	verify_prolly_tree_equality_to_map(&operations_executed, &intermediary_map, &storage).await;	24✔
171	let additional_operations_executed =	6✔
172	execute_operations_on_prolly_tree(&operations_executed, &additional_operations, &storage)	24✔
173	.await;	6✔
174	if additional_operations.is_empty() {	12✔
175	verify_prolly_trees_equal(
176	&operations_executed,	6✔
177	&additional_operations_executed,	6✔
178	&storage,	3✔
179	)
180	.await;	3✔
181	}
182	let after_digest = btree_map_to_digest(&test_case.after, &storage).await;	24✔
183	verify_prolly_tree_equality_to_map(&after_digest, &final_map, &storage).await;	24✔
184	verify_prolly_trees_equal(&after_digest, &additional_operations_executed, &storage).await;	24✔
185	}
186
187	pub fn fuzz_function(data: &[u8]) -> bool {	1✔
188	let mut unstructured = Unstructured::new(data);	3✔
189	let test_case: TestCase = match unstructured.arbitrary() {	3✔
190	Ok(success) => success,	2✔
NEW 191	Err(_) => return false,	×
192	};
193	tokio::runtime::Builder::new_current_thread()	2✔
194	.build()
195	.unwrap()
196	.block_on(async {	2✔
197	run_test_case(&test_case).await;	2✔
198	});
199	true	1✔
200	}
201
202	#[cfg(test)]
203	#[test_log::test(tokio::test)]
204	async fn test_empty() {
205	run_test_case(&TestCase {
206	before: BTreeMap::new(),
207	after: BTreeMap::new(),
208	operations: vec![],
209	})
210	.await;
211	}
212
213	#[cfg(test)]
214	#[test_log::test(tokio::test)]
215	async fn test_no_operations() {
216	run_test_case(&TestCase {
217	before: BTreeMap::new(),
218	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
219	operations: vec![],
220	})
221	.await;
222	}
223
224	#[cfg(test)]
225	#[test_log::test(tokio::test)]
226	async fn test_matching_operations() {
227	run_test_case(&TestCase {
228	before: BTreeMap::new(),
229	after: BTreeMap::from([(10, 100), (20, 200), (30, 300)]),
230	operations: vec![
231	MapOperation::Insert(10, 100),
232	MapOperation::Insert(20, 200),
233	MapOperation::Insert(30, 300),
234	],
235	})
236	.await;
237	}
238
239	#[cfg(test)]
240	#[test_log::test(tokio::test)]
241	async fn test_mismatching_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(40, 200),
248	MapOperation::Insert(30, 400),
249	],
250	})
251	.await;
252	}
253
254	#[cfg(test)]
255	#[test_log::test(tokio::test)]
256	async fn test_save_operation() {
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(20, 200),
263	MapOperation::Save,
264	MapOperation::Insert(30, 300),
265	],
266	})
267	.await;
268	}
269
270	#[cfg(test)]
271	#[test_log::test]
272	fn test_crash_0() {
273	fuzz_function(&[
274	201, 255, 255, 219, 89, 89, 67, 75, 73, 89, 75, 240, 67, 243, 102, 0, 219, 170, 67, 75, 89,
275	32, 240, 89, 67, 75, 33, 89, 75, 240, 67, 243, 32, 191, 157, 40, 255, 0, 255, 1, 149, 25,
276	255, 255, 255, 0, 0, 255, 255, 58, 255, 43, 43, 154, 202, 0, 43, 43, 43, 43, 43, 43, 43,
277	43, 43, 43, 43, 43, 43, 43, 43, 43, 255, 255, 239, 32, 75, 219, 89, 89, 241, 241, 255, 255,
278	255, 255, 255, 255, 255, 255, 255, 255, 127, 255, 255, 255, 255, 225, 255, 255, 255, 255,
279	46, 255, 93, 255, 254, 59, 253, 88, 255, 255, 46, 255, 93, 241, 241, 241, 241, 241, 243,
280	241, 241, 219, 89, 89, 67, 75, 89, 0, 60, 255,
281	]);
282	}

TyRoXx / NonlocalityOS / 20003570228

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