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

83.61

/fuzz/fuzz_functions/src/prolly_tree_editable_node_insert.rs

use arbitrary::{Arbitrary, Unstructured};
use astraea::tree::BlobDigest;
use pretty_assertions::assert_eq;
use rand::{rngs::SmallRng, seq::SliceRandom, SeedableRng};
use sorted_tree::{
    prolly_tree_editable_node::{EditableNode, IntegrityCheckResult},
    sorted_tree::TreeReference,
};
use std::collections::BTreeMap;
use tokio::sync::Mutex;

type UniqueInsertions = BTreeMap<u32, i64>;
type InsertionBatches = Vec<UniqueInsertions>;

fn randomize_insertion_order(seed: u8, insertion_batches: &InsertionBatches) -> Vec<(u32, i64)> {
    let mut random = SmallRng::seed_from_u64(seed as u64);
    let mut all_insertions = Vec::new();
    for batch in insertion_batches.iter() {
        let mut batch_randomized: Vec<(u32, i64)> = batch.iter().map(|(k, v)| (*k, *v)).collect();
        batch_randomized.shuffle(&mut random);
        all_insertions.extend(batch_randomized);
    }
    all_insertions
}

async fn insert_one_at_a_time(insertions: &[(u32, i64)]) -> BlobDigest {
    let storage = astraea::storage::InMemoryTreeStorage::new(Mutex::new(BTreeMap::new()));
    let mut editable_node: EditableNode<u32, i64> = EditableNode::new();
    let mut oracle = BTreeMap::new();
    for (key, _value) in insertions.iter() {
        let found = editable_node.find(key, &storage).await.unwrap();
        assert_eq!(None, found);
    }
    for (key, value) in insertions.iter() {
        {
            let existing_entry = editable_node.find(key, &storage).await.unwrap();
            let expected_entry = oracle.get(key);
            assert_eq!(expected_entry.copied(), existing_entry);
        }
        {
            let number_of_trees_before = storage.number_of_trees().await;
            editable_node
                .insert(*key, *value, &storage)
                .await
                .expect("inserting key should succeed");
            let number_of_trees_after = storage.number_of_trees().await;
            assert!(number_of_trees_after >= number_of_trees_before);
            let difference = number_of_trees_after - number_of_trees_before;
            // TODO: find out why so many trees are created in some cases
            assert!(difference <= 100);
        }
        let found = editable_node.find(key, &storage).await.unwrap();
        assert_eq!(Some(*value), found);
        oracle.insert(*key, *value);
        let size = editable_node.size(&storage).await.unwrap();
        assert_eq!(oracle.len() as u64, size);
        match editable_node
            .verify_integrity(oracle.keys().last(), &storage)
            .await
            .unwrap()
        {
            IntegrityCheckResult::Valid { depth } => {
                assert!(depth < 10);
            }
            IntegrityCheckResult::Corrupted(reason) => {
                panic!("Tree integrity check failed: {}", reason);
            }
        }
    }
    for (key, value) in oracle.iter() {
        let found = editable_node.find(key, &storage).await.unwrap();
        assert_eq!(Some(*value), found);
    }
    let final_size = editable_node.size(&storage).await.unwrap();
    assert_eq!(oracle.len() as u64, final_size);
    assert_eq!(0, storage.number_of_trees().await);
    let digest = editable_node.save(&storage).await.unwrap();
    let number_of_trees = storage.number_of_trees().await;
    assert!(number_of_trees >= 1);
    // TODO: find a better upper bound
    assert!(number_of_trees <= 1000);

    // test loading from storage
    editable_node = EditableNode::Reference(TreeReference::new(digest));
    for (key, value) in oracle.iter() {
        let found = editable_node.find(key, &storage).await.unwrap();
        assert_eq!(Some(*value), found);
    }
    assert_eq!(
        oracle.len() as u64,
        editable_node.size(&storage).await.unwrap()
    );
    let saved_again = editable_node.save(&storage).await.unwrap();
    assert_eq!(saved_again, digest);

    digest
}

#[derive(Arbitrary, Debug)]
struct TestCase {
    seed_a: u8,
    seed_b: u8,
    insertion_batches: InsertionBatches,
}

async fn insert_entries(parameters: &TestCase) {
    let digest_a = insert_one_at_a_time(&randomize_insertion_order(
        parameters.seed_a,
        &parameters.insertion_batches,
    ))
    .await;
    let digest_b = insert_one_at_a_time(&randomize_insertion_order(
        parameters.seed_b,
        &parameters.insertion_batches,
    ))
    .await;
    assert_eq!(digest_a, digest_b);
}

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

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_insert_many_entries_zero() {
    insert_entries(&TestCase {
        seed_a: 0,
        seed_b: 1,
        insertion_batches: vec![],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_insert_many_entries_same_entry() {
    insert_entries(&TestCase {
        seed_a: 0,
        seed_b: 1,
        insertion_batches: vec![[(10, 100), (10, 100), (10, 100), (10, 100), (10, 100)].into()],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_insert_many_entries_few() {
    insert_entries(&TestCase {
        seed_a: 0,
        seed_b: 1,
        insertion_batches: vec![
            [
                (10, 100),
                (20, 200),
                (15, 150),
                (25, 250),
                (5, 50),
                (30, 300),
                (12, 120),
            ]
            .into(),
            [(10, 200), (15, 250), (12, 220), (18, 180), (22, 220)].into(),
        ],
    })
    .await;
}

#[cfg(test)]
#[test_log::test(tokio::test)]
async fn test_insert_many_entries_lots() {
    insert_entries(&TestCase {
        seed_a: 0,
        seed_b: 1,
        insertion_batches: vec![(0..200).map(|i| (i, (i as i64) * 10)).collect()],
    })
    .await;
}

1	use arbitrary::{Arbitrary, Unstructured};
2	use astraea::tree::BlobDigest;
3	use pretty_assertions::assert_eq;
4	use rand::{rngs::SmallRng, seq::SliceRandom, SeedableRng};
5	use sorted_tree::{
6	prolly_tree_editable_node::{EditableNode, IntegrityCheckResult},
7	sorted_tree::TreeReference,
8	};
9	use std::collections::BTreeMap;
10	use tokio::sync::Mutex;
11
12	type UniqueInsertions = BTreeMap<u32, i64>;
13	type InsertionBatches = Vec<UniqueInsertions>;
14
15	fn randomize_insertion_order(seed: u8, insertion_batches: &InsertionBatches) -> Vec<(u32, i64)> {	8✔
16	let mut random = SmallRng::seed_from_u64(seed as u64);	24✔
17	let mut all_insertions = Vec::new();	16✔
18	for batch in insertion_batches.iter() {	24✔
19	let mut batch_randomized: Vec<(u32, i64)> = batch.iter().map(\|(k, v)\| (k, v)).collect();	900✔
20	batch_randomized.shuffle(&mut random);	16✔
21	all_insertions.extend(batch_randomized);	24✔
22	}
23	all_insertions	8✔
24	}
25
26	async fn insert_one_at_a_time(insertions: &[(u32, i64)]) -> BlobDigest {	16✔
27	let storage = astraea::storage::InMemoryTreeStorage::new(Mutex::new(BTreeMap::new()));	32✔
28	let mut editable_node: EditableNode<u32, i64> = EditableNode::new();	24✔
29	let mut oracle = BTreeMap::new();	16✔
30	for (key, _value) in insertions.iter() {	868✔
31	let found = editable_node.find(key, &storage).await.unwrap();	2,556✔
32	assert_eq!(None, found);
33	}
34	for (key, value) in insertions.iter() {	868✔
35	{
36	let existing_entry = editable_node.find(key, &storage).await.unwrap();	2,556✔
37	let expected_entry = oracle.get(key);	1,704✔
38	assert_eq!(expected_entry.copied(), existing_entry);
39	}
40	{
41	let number_of_trees_before = storage.number_of_trees().await;	1,278✔
42	editable_node	852✔
43	.insert(key, value, &storage)	1,704✔
44	.await	426✔
45	.expect("inserting key should succeed");
46	let number_of_trees_after = storage.number_of_trees().await;	1,278✔
47	assert!(number_of_trees_after >= number_of_trees_before);
48	let difference = number_of_trees_after - number_of_trees_before;	852✔
49	// TODO: find out why so many trees are created in some cases
50	assert!(difference <= 100);
51	}
52	let found = editable_node.find(key, &storage).await.unwrap();	2,556✔
53	assert_eq!(Some(*value), found);
54	oracle.insert(key, value);	1,704✔
55	let size = editable_node.size(&storage).await.unwrap();	2,130✔
56	assert_eq!(oracle.len() as u64, size);
57	match editable_node	852✔
58	.verify_integrity(oracle.keys().last(), &storage)	2,130✔
59	.await	426✔
60	.unwrap()	426✔
61	{
62	IntegrityCheckResult::Valid { depth } => {	426✔
63	assert!(depth < 10);
64	}
NEW 65	IntegrityCheckResult::Corrupted(reason) => {	×
66	panic!("Tree integrity check failed: {}", reason);
67	}
68	}
69	}
70	for (key, value) in oracle.iter() {	856✔
71	let found = editable_node.find(key, &storage).await.unwrap();	2,520✔
72	assert_eq!(Some(*value), found);
73	}
74	let final_size = editable_node.size(&storage).await.unwrap();	40✔
75	assert_eq!(oracle.len() as u64, final_size);
76	assert_eq!(0, storage.number_of_trees().await);
77	let digest = editable_node.save(&storage).await.unwrap();	40✔
78	let number_of_trees = storage.number_of_trees().await;	24✔
79	assert!(number_of_trees >= 1);
80	// TODO: find a better upper bound
81	assert!(number_of_trees <= 1000);
82
83	// test loading from storage
84	editable_node = EditableNode::Reference(TreeReference::new(digest));	16✔
85	for (key, value) in oracle.iter() {	856✔
86	let found = editable_node.find(key, &storage).await.unwrap();	2,520✔
87	assert_eq!(Some(*value), found);
88	}
89	assert_eq!(
90	oracle.len() as u64,
91	editable_node.size(&storage).await.unwrap()
92	);
93	let saved_again = editable_node.save(&storage).await.unwrap();	40✔
94	assert_eq!(saved_again, digest);
95
96	digest	8✔
97	}
98
99	#[derive(Arbitrary, Debug)]
100	struct TestCase {
101	seed_a: u8,
102	seed_b: u8,
103	insertion_batches: InsertionBatches,
104	}
105
106	async fn insert_entries(parameters: &TestCase) {	8✔
107	let digest_a = insert_one_at_a_time(&randomize_insertion_order(	16✔
108	parameters.seed_a,	4✔
109	&parameters.insertion_batches,	4✔
110	))
111	.await;	4✔
112	let digest_b = insert_one_at_a_time(&randomize_insertion_order(	16✔
113	parameters.seed_b,	4✔
114	&parameters.insertion_batches,	4✔
115	))
116	.await;	4✔
117	assert_eq!(digest_a, digest_b);
118	}
119
NEW 120	pub fn fuzz_function(data: &[u8]) -> bool {	×
NEW 121	let mut unstructured = Unstructured::new(data);	×
NEW 122	let parameters: TestCase = match unstructured.arbitrary() {	×
NEW 123	Ok(success) => success,	×
NEW 124	Err(_) => return false,	×
125	};
NEW 126	tokio::runtime::Builder::new_current_thread()	×
127	.build()
128	.unwrap()
NEW 129	.block_on(async {	×
NEW 130	insert_entries(&parameters).await;	×
131	});
NEW 132	true	×
133	}
134
135	#[cfg(test)]
136	#[test_log::test(tokio::test)]
137	async fn test_insert_many_entries_zero() {
138	insert_entries(&TestCase {
139	seed_a: 0,
140	seed_b: 1,
141	insertion_batches: vec![],
142	})
143	.await;
144	}
145
146	#[cfg(test)]
147	#[test_log::test(tokio::test)]
148	async fn test_insert_many_entries_same_entry() {
149	insert_entries(&TestCase {
150	seed_a: 0,
151	seed_b: 1,
152	insertion_batches: vec![[(10, 100), (10, 100), (10, 100), (10, 100), (10, 100)].into()],
153	})
154	.await;
155	}
156
157	#[cfg(test)]
158	#[test_log::test(tokio::test)]
159	async fn test_insert_many_entries_few() {
160	insert_entries(&TestCase {
161	seed_a: 0,
162	seed_b: 1,
163	insertion_batches: vec![
164	[
165	(10, 100),
166	(20, 200),
167	(15, 150),
168	(25, 250),
169	(5, 50),
170	(30, 300),
171	(12, 120),
172	]
173	.into(),
174	[(10, 200), (15, 250), (12, 220), (18, 180), (22, 220)].into(),
175	],
176	})
177	.await;
178	}
179
180	#[cfg(test)]
181	#[test_log::test(tokio::test)]
182	async fn test_insert_many_entries_lots() {
183	insert_entries(&TestCase {
184	seed_a: 0,
185	seed_b: 1,
186	insertion_batches: vec![(0..200).map(\|i\| (i, (i as i64) * 10)).collect()],	400✔
187	})
188	.await;
189	}

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