24925290370

Committed 25 Apr 2026 07:03AM UTC coverage: 73.622% (-0.07%) from 73.693%

Build # 24925290370

Build Type

push

github

Committed by

TyRoXx

Commit Message

Handle deserialization errors in sorted_tree

Coverage Stats

20 of 33 new or added lines in 1 file covered. (60.61%)

3 existing lines in 2 files now uncovered.

7469 of 10145 relevant lines covered (73.62%)

24464.01 hits per line

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

81.2

/sorted_tree/src/sorted_tree.rs

use astraea::{
    storage::{load_children, LoadError, LoadTree, StoreError, StoreTree, StrongReference},
    tree::{BlobDigest, HashedTree, Tree, TreeBlob, TreeChildren, TreeSerializationError},
};
use serde::{de::DeserializeOwned, Deserialize, Serialize};

pub trait NodeValue {
    type Content: Serialize + DeserializeOwned;

    fn has_child(content: &Self::Content) -> bool;
    // TODO: change to Option<&StrongReference>
    fn from_content(content: Self::Content, child: &Option<StrongReference>) -> Self;
    fn to_content(&self) -> Self::Content;
    fn get_reference(&self) -> Option<StrongReference>;
}

impl<T> NodeValue for T
where
    T: Serialize + DeserializeOwned + Clone,
{
    type Content = T;

    fn has_child(_content: &Self::Content) -> bool {
        false
    }

    fn from_content(content: Self::Content, child: &Option<StrongReference>) -> Self {
        assert!(child.is_none());
        content
    }

    fn to_content(&self) -> Self::Content {
        self.clone()
    }

    fn get_reference(&self) -> Option<StrongReference> {
        None
    }
}

#[derive(Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub struct TreeReference {
    reference: StrongReference,
}

impl TreeReference {
    pub fn new(reference: StrongReference) -> Self {
        Self { reference }
    }

    pub fn reference(&self) -> &StrongReference {
        &self.reference
    }
}

impl NodeValue for TreeReference {
    type Content = ();

    fn has_child(_content: &Self::Content) -> bool {
        true
    }

    fn from_content(_content: Self::Content, child: &Option<StrongReference>) -> Self {
        match child {
            Some(reference) => TreeReference {
                reference: reference.clone(),
            },
            None => todo!("node claims to have a child, but no reference is available"),
        }
    }

    fn to_content(&self) -> Self::Content {}

    fn get_reference(&self) -> Option<StrongReference> {
        Some(self.reference.clone())
    }
}

#[derive(Serialize, Deserialize, Clone, Hash, PartialEq, Debug)]
pub struct Node<Key: Serialize + Ord, Value: NodeValue> {
    /// sorted by Key
    pub entries: Vec<(Key, Value)>,
}

impl<Key: Serialize + Ord + Clone, Value: NodeValue + Clone> Default for Node<Key, Value> {
    fn default() -> Self {
        Self::new()
    }
}

impl<Key: Serialize + Ord + Clone, Value: NodeValue + Clone> Node<Key, Value> {
    pub fn new() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    pub fn entries(&self) -> &Vec<(Key, Value)> {
        &self.entries
    }

    pub fn insert(&mut self, key: Key, value: Value) {
        let partition_point = self.entries.partition_point(|element| element.0 < key);
        if partition_point < self.entries.len() && self.entries[partition_point].0 == key {
            self.entries[partition_point].1 = value;
        } else {
            self.entries.insert(partition_point, (key, value));
        }
    }

    pub fn replace_chunk(&mut self, index: usize, new_chunks: &[(Key, Value)]) {
        self.entries
            .splice(index..=index, new_chunks.iter().cloned());
    }

    pub fn find(&self, key: &Key) -> Option<Value> {
        match self
            .entries
            .binary_search_by_key(&key, |element| &element.0)
        {
            Ok(index) => Some(self.entries[index].1.clone()),
            Err(_) => None,
        }
    }
}

#[derive(Serialize, Deserialize, Clone, Hash)]
pub struct SerializableNodeContent<Key: Serialize + Ord, Value: Serialize> {
    /// sorted by Key
    entries: Vec<(Key, Value)>,
}

impl<Key: Serialize + Ord, Value: Serialize> SerializableNodeContent<Key, Value> {
    pub fn new(entries: Vec<(Key, Value)>) -> Self {
        Self { entries }
    }

    pub fn entries(&self) -> &Vec<(Key, Value)> {
        &self.entries
    }
}

pub fn node_to_tree<Key: Serialize + Ord, Value: NodeValue>(
    node: &Node<Key, Value>,
    metadata: &bytes::Bytes,
) -> Result<Tree, TreeSerializationError> {
    let serializable_node_content = SerializableNodeContent {
        entries: node
            .entries
            .iter()
            .map(|(key, value)| (key, value.to_content()))
            .collect(),
    };
    let references: Vec<_> = node
        .entries
        .iter()
        .filter_map(|(_key, value)| value.get_reference())
        .collect();
    let children = match TreeChildren::try_from(references) {
        Some(children) => children,
        None => return Err(TreeSerializationError::TooManyChildren),
    };
    let mut buffer = Vec::from_iter(metadata.iter().cloned());
    postcard::to_io(&serializable_node_content, &mut buffer)
        .expect("serializing a node should always work");
    let blob = TreeBlob::try_from(bytes::Bytes::from(buffer))?;
    Ok(Tree::new(blob, children))
}

pub async fn store_node<Key: Serialize + Ord, Value: NodeValue>(
    store_tree: &(dyn StoreTree + Send + Sync),
    node: &Node<Key, Value>,
    metadata: &bytes::Bytes,
) -> Result<StrongReference, StoreError> {
    let tree = match node_to_tree(node, metadata) {
        Ok(tree) => tree,
        Err(error) => return Err(StoreError::TreeSerializationError(error)),
    };
    store_tree
        .store_tree(&HashedTree::from(std::sync::Arc::new(tree)))
        .await
}

#[derive(Debug, Clone, PartialEq)]
pub enum NodeDeserializationError {
    PostcardError(postcard::Error),
    EntriesNotSorted,
    TooManyChildren,
    NotEnoughChildren,
    DuplicateKeys,
}

impl std::fmt::Display for NodeDeserializationError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            NodeDeserializationError::PostcardError(e) => write!(f, "postcard error: {}", e),
            NodeDeserializationError::EntriesNotSorted => {
                write!(f, "node entries are not sorted by key")
            }
            NodeDeserializationError::TooManyChildren => {
                write!(
                    f,
                    "node has more children than expected based on its content"
                )
            }
            NodeDeserializationError::NotEnoughChildren => {
                write!(
                    f,
                    "node has fewer children than expected based on its content"
                )
            }
            NodeDeserializationError::DuplicateKeys => {
                write!(f, "node contains duplicate keys")
            }
        }
    }
}

impl std::error::Error for NodeDeserializationError {}

pub fn node_from_tree<Key: Serialize + DeserializeOwned + Ord, Value: NodeValue>(
    tree_blob: &TreeBlob,
    children: &[StrongReference],
    metadata_to_skip: usize,
) -> Result<Node<Key, Value>, NodeDeserializationError> {
    let node = postcard::from_bytes::<SerializableNodeContent<Key, Value::Content>>(
        tree_blob.as_slice().split_at(metadata_to_skip).1,
    )
    .map_err(NodeDeserializationError::PostcardError)?;
    let mut reference_iter = children.iter();
    let mut entries: Vec<(Key, Value)> = Vec::new();
    for (key, content) in node.entries.into_iter() {
        if let Some(last) = entries.last() {
            match last.0.cmp(&key) {
                std::cmp::Ordering::Less => {}
                std::cmp::Ordering::Equal => return Err(NodeDeserializationError::DuplicateKeys),
                std::cmp::Ordering::Greater => {
                    return Err(NodeDeserializationError::EntriesNotSorted)
                }
            }
        }
        if Value::has_child(&content) {
            let reference = match reference_iter.next() {
                Some(reference) => Some(reference.clone()),
                None => return Err(NodeDeserializationError::NotEnoughChildren),
            };
            entries.push((key, Value::from_content(content, &reference)));
        } else {
            entries.push((key, Value::from_content(content, &None)));
        }
    }
    if reference_iter.next().is_some() {
        return Err(NodeDeserializationError::TooManyChildren);
    }
    Ok(Node { entries })
}

pub async fn load_node<Key: Serialize + DeserializeOwned + Ord, Value: NodeValue>(
    load_tree: &(dyn LoadTree + Send + Sync),
    root: &BlobDigest,
) -> Result<Node<Key, Value>, Box<dyn std::error::Error>> {
    let delayed_hashed_tree = match load_tree.load_tree(root).await {
        Ok(tree) => tree,
        Err(error) => return Err(error.into()),
    };
    let hashed_tree = match delayed_hashed_tree.hash() {
        Some(tree) => tree,
        None => {
            return Err(
                LoadError::Inconsistency(*root, "tree hash does not match".to_string()).into(),
            )
        }
    };
    let children = load_children(load_tree, hashed_tree.hashed_tree().tree())
        .await?
        .into_iter()
        .map(|child| child.reference().clone())
        .collect::<Vec<_>>();
    node_from_tree::<Key, Value>(hashed_tree.hashed_tree().tree().blob(), &children, 0)
        .map_err(|e| e.into())
}

pub async fn new_tree<Key: Serialize + Ord, Value: NodeValue>(
    store_tree: &(dyn StoreTree + Send + Sync),
) -> Result<StrongReference, StoreError> {
    let root = Node::<Key, Value> {
        entries: Vec::new(),
    };
    store_node(store_tree, &root,  /*this function is only used by sorted_tree_tests, so we don't need the prolly_tree metadata*/ &bytes::Bytes::new()).await
}

pub async fn insert<Key: Serialize + DeserializeOwned + Ord + Clone, Value: NodeValue + Clone>(
    load_tree: &(dyn LoadTree + Send + Sync),
    store_tree: &(dyn StoreTree + Send + Sync),
    root: &BlobDigest,
    key: Key,
    value: Value,
) -> Result<StrongReference, StoreError> {
    let mut node = match load_node::<Key, Value>(load_tree, root).await {
        Ok(loaded) => loaded,
        Err(_) => todo!(),
    };
    node.insert(key, value);
    store_node(store_tree, &node, /*this function is only used by sorted_tree_tests, so we don't need the prolly_tree metadata*/ &bytes::Bytes::new()).await
}

pub async fn find<
    Key: Serialize + DeserializeOwned + PartialEq + Ord + Clone,
    Value: NodeValue + Clone,
>(
    load_tree: &(dyn LoadTree + Send + Sync),
    root: &BlobDigest,
    key: &Key,
) -> Option<Value> {
    let node = match load_node::<Key, Value>(load_tree, root).await {
        Ok(loaded) => loaded,
        Err(_) => todo!(),
    };
    node.find(key)
}

1	use astraea::{
2	storage::{load_children, LoadError, LoadTree, StoreError, StoreTree, StrongReference},
3	tree::{BlobDigest, HashedTree, Tree, TreeBlob, TreeChildren, TreeSerializationError},
4	};
5	use serde::{de::DeserializeOwned, Deserialize, Serialize};
6
7	pub trait NodeValue {
8	type Content: Serialize + DeserializeOwned;
9
10	fn has_child(content: &Self::Content) -> bool;
11	// TODO: change to Option<&StrongReference>
12	fn from_content(content: Self::Content, child: &Option<StrongReference>) -> Self;
13	fn to_content(&self) -> Self::Content;
14	fn get_reference(&self) -> Option<StrongReference>;
15	}
16
17	impl<T> NodeValue for T
18	where
19	T: Serialize + DeserializeOwned + Clone,
20	{
21	type Content = T;
22
23	fn has_child(_content: &Self::Content) -> bool {	28,527✔
24	false	28,527✔
25	}
26
27	fn from_content(content: Self::Content, child: &Option<StrongReference>) -> Self {	28,527✔
28	assert!(child.is_none());
29	content	28,527✔
30	}
31
32	fn to_content(&self) -> Self::Content {	3,199,464✔
33	self.clone()	6,398,928✔
34	}
35
36	fn get_reference(&self) -> Option<StrongReference> {	13,255✔
37	None	13,255✔
38	}
39	}
40
41	#[derive(Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
42	pub struct TreeReference {
43	reference: StrongReference,
44	}
45
46	impl TreeReference {
47	pub fn new(reference: StrongReference) -> Self {	19,666✔
48	Self { reference }
49	}
50
51	pub fn reference(&self) -> &StrongReference {	2,312✔
52	&self.reference	2,312✔
53	}
54	}
55
56	impl NodeValue for TreeReference {
57	type Content = ();
58
59	fn has_child(_content: &Self::Content) -> bool {	17✔
60	true	17✔
61	}
62
63	fn from_content(_content: Self::Content, child: &Option<StrongReference>) -> Self {	16✔
64	match child {	16✔
65	Some(reference) => TreeReference {
66	reference: reference.clone(),	16✔
67	},
68	None => todo!("node claims to have a child, but no reference is available"),
69	}
70	}
71
72	fn to_content(&self) -> Self::Content {}	34,716✔
73
74	fn get_reference(&self) -> Option<StrongReference> {	79✔
75	Some(self.reference.clone())	79✔
76	}
77	}
78
79	#[derive(Serialize, Deserialize, Clone, Hash, PartialEq, Debug)]
80	pub struct Node<Key: Serialize + Ord, Value: NodeValue> {
81	/// sorted by Key
82	pub entries: Vec<(Key, Value)>,
83	}
84
85	impl<Key: Serialize + Ord + Clone, Value: NodeValue + Clone> Default for Node<Key, Value> {
86	fn default() -> Self {	×
87	Self::new()	×
88	}
89	}
90
91	impl<Key: Serialize + Ord + Clone, Value: NodeValue + Clone> Node<Key, Value> {
92	pub fn new() -> Self {	2✔
93	Self {
94	entries: Vec::new(),	2✔
95	}
96	}
97
98	pub fn entries(&self) -> &Vec<(Key, Value)> {	211✔
99	&self.entries	211✔
100	}
101
102	pub fn insert(&mut self, key: Key, value: Value) {	217✔
103	let partition_point = self.entries.partition_point(\|element\| element.0 < key);	2,937✔
104	if partition_point < self.entries.len() && self.entries[partition_point].0 == key {	727✔
105	self.entries[partition_point].1 = value;	94✔
106	} else {
107	self.entries.insert(partition_point, (key, value));	492✔
108	}
109	}
110
111	pub fn replace_chunk(&mut self, index: usize, new_chunks: &[(Key, Value)]) {	×
112	self.entries	×
113	.splice(index..=index, new_chunks.iter().cloned());	×
114	}
115
116	pub fn find(&self, key: &Key) -> Option<Value> {	343✔
117	match self	343✔
118	.entries	343✔
119	.binary_search_by_key(&key, \|element\| &element.0)	686✔
120	{
121	Ok(index) => Some(self.entries[index].1.clone()),	654✔
122	Err(_) => None,	16✔
123	}
124	}
125	}
126
127	#[derive(Serialize, Deserialize, Clone, Hash)]
128	pub struct SerializableNodeContent<Key: Serialize + Ord, Value: Serialize> {
129	/// sorted by Key
130	entries: Vec<(Key, Value)>,
131	}
132
133	impl<Key: Serialize + Ord, Value: Serialize> SerializableNodeContent<Key, Value> {
134	pub fn new(entries: Vec<(Key, Value)>) -> Self {	7✔
135	Self { entries }
136	}
137
138	pub fn entries(&self) -> &Vec<(Key, Value)> {	×
139	&self.entries	×
140	}
141	}
142
143	pub fn node_to_tree<Key: Serialize + Ord, Value: NodeValue>(	643✔
144	node: &Node<Key, Value>,
145	metadata: &bytes::Bytes,
146	) -> Result<Tree, TreeSerializationError> {
147	let serializable_node_content = SerializableNodeContent {
148	entries: node	643✔
149	.entries
150	.iter()
151	.map(\|(key, value)\| (key, value.to_content()))
152	.collect(),
153	};
154	let references: Vec<_> = node	1,929✔
155	.entries	643✔
156	.iter()
157	.filter_map(\|(_key, value)\| value.get_reference())	29,753✔
158	.collect();
159	let children = match TreeChildren::try_from(references) {	1,286✔
160	Some(children) => children,	1,286✔
161	None => return Err(TreeSerializationError::TooManyChildren),	×
162	};
163	let mut buffer = Vec::from_iter(metadata.iter().cloned());	2,572✔
164	postcard::to_io(&serializable_node_content, &mut buffer)	1,929✔
165	.expect("serializing a node should always work");
166	let blob = TreeBlob::try_from(bytes::Bytes::from(buffer))?;	2,572✔
167	Ok(Tree::new(blob, children))	1,286✔
168	}
169
170	pub async fn store_node<Key: Serialize + Ord, Value: NodeValue>(	641✔
171	store_tree: &(dyn StoreTree + Send + Sync),
172	node: &Node<Key, Value>,
173	metadata: &bytes::Bytes,
174	) -> Result<StrongReference, StoreError> {
175	let tree = match node_to_tree(node, metadata) {	1,923✔
176	Ok(tree) => tree,	1,282✔
177	Err(error) => return Err(StoreError::TreeSerializationError(error)),	×
178	};
179	store_tree	1,282✔
180	.store_tree(&HashedTree::from(std::sync::Arc::new(tree)))	1,923✔
181	.await	641✔
182	}
183
184	#[derive(Debug, Clone, PartialEq)]
185	pub enum NodeDeserializationError {
186	PostcardError(postcard::Error),
187	EntriesNotSorted,
188	TooManyChildren,
189	NotEnoughChildren,
190	DuplicateKeys,
191	}
192
193	impl std::fmt::Display for NodeDeserializationError {
NEW 194	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {	×
NEW 195	match self {	×
NEW 196	NodeDeserializationError::PostcardError(e) => write!(f, "postcard error: {}", e),	×
197	NodeDeserializationError::EntriesNotSorted => {
NEW 198	write!(f, "node entries are not sorted by key")	×
199	}
200	NodeDeserializationError::TooManyChildren => {
NEW 201	write!(	×
NEW 202	f,	×
203	"node has more children than expected based on its content"
204	)
205	}
206	NodeDeserializationError::NotEnoughChildren => {
NEW 207	write!(	×
NEW 208	f,	×
209	"node has fewer children than expected based on its content"
210	)
211	}
212	NodeDeserializationError::DuplicateKeys => {
NEW 213	write!(f, "node contains duplicate keys")	×
214	}
215	}
216	}
217	}
218
219	impl std::error::Error for NodeDeserializationError {}
220
221	pub fn node_from_tree<Key: Serialize + DeserializeOwned + Ord, Value: NodeValue>(	960✔
222	tree_blob: &TreeBlob,
223	children: &[StrongReference],
224	metadata_to_skip: usize,
225	) -> Result<Node<Key, Value>, NodeDeserializationError> {
226	let node = postcard::from_bytes::<SerializableNodeContent<Key, Value::Content>>(
227	tree_blob.as_slice().split_at(metadata_to_skip).1,	1,920✔
228	)
229	.map_err(NodeDeserializationError::PostcardError)?;	960✔
230	let mut reference_iter = children.iter();	2,880✔
231	let mut entries: Vec<(Key, Value)> = Vec::new();	2,880✔
232	for (key, content) in node.entries.into_iter() {	61,188✔
233	if let Some(last) = entries.last() {	58,402✔
234	match last.0.cmp(&key) {	57,536✔
235	std::cmp::Ordering::Less => {}	28,766✔
236	std::cmp::Ordering::Equal => return Err(NodeDeserializationError::DuplicateKeys),	1✔
NEW 237	std::cmp::Ordering::Greater => {	×
238	return Err(NodeDeserializationError::EntriesNotSorted)	1✔
239	}
240	}
241	}
242	if Value::has_child(&content) {	59,264✔
243	let reference = match reference_iter.next() {	2,209✔
244	Some(reference) => Some(reference.clone()),	2,208✔
245	None => return Err(NodeDeserializationError::NotEnoughChildren),	1✔
246	};
247	entries.push((key, Value::from_content(content, &reference)));	5,520✔
248	} else {
249	entries.push((key, Value::from_content(content, &None)));	142,635✔
250	}
251	}
252	if reference_iter.next().is_some() {	1,914✔
253	return Err(NodeDeserializationError::TooManyChildren);	1✔
254	}
255	Ok(Node { entries })	956✔
256	}
257
258	pub async fn load_node<Key: Serialize + DeserializeOwned + Ord, Value: NodeValue>(	765✔
259	load_tree: &(dyn LoadTree + Send + Sync),
260	root: &BlobDigest,
261	) -> Result<Node<Key, Value>, Box<dyn std::error::Error>> {
262	let delayed_hashed_tree = match load_tree.load_tree(root).await {	3,824✔
263	Ok(tree) => tree,	1,528✔
264	Err(error) => return Err(error.into()),	2✔
265	};
266	let hashed_tree = match delayed_hashed_tree.hash() {	1,528✔
267	Some(tree) => tree,	1,528✔
NEW 268	None => {	×
NEW 269	return Err(	×
NEW 270	LoadError::Inconsistency(*root, "tree hash does not match".to_string()).into(),	×
271	)
272	}
273	};
274	let children = load_children(load_tree, hashed_tree.hashed_tree().tree())	3,056✔
275	.await?	764✔
276	.into_iter()
277	.map(\|child\| child.reference().clone())	770✔
278	.collect::<Vec<_>>();
279	node_from_tree::<Key, Value>(hashed_tree.hashed_tree().tree().blob(), &children, 0)	2,292✔
280	.map_err(\|e\| e.into())	764✔
281	}
282
283	pub async fn new_tree<Key: Serialize + Ord, Value: NodeValue>(	9✔
284	store_tree: &(dyn StoreTree + Send + Sync),
285	) -> Result<StrongReference, StoreError> {
286	let root = Node::<Key, Value> {
287	entries: Vec::new(),	9✔
288	};
289	store_node(store_tree, &root, /this function is only used by sorted_tree_tests, so we don't need the prolly_tree metadata/ &bytes::Bytes::new()).await	36✔
290	}
291
292	pub async fn insert<Key: Serialize + DeserializeOwned + Ord + Clone, Value: NodeValue + Clone>(	213✔
293	load_tree: &(dyn LoadTree + Send + Sync),
294	store_tree: &(dyn StoreTree + Send + Sync),
295	root: &BlobDigest,
296	key: Key,
297	value: Value,
298	) -> Result<StrongReference, StoreError> {
299	let mut node = match load_node::<Key, Value>(load_tree, root).await {	1,065✔
300	Ok(loaded) => loaded,	426✔
301	Err(_) => todo!(),
302	};
303	node.insert(key, value);	852✔
304	store_node(store_tree, &node, /this function is only used by sorted_tree_tests, so we don't need the prolly_tree metadata/ &bytes::Bytes::new()).await	852✔
305	}
306
307	pub async fn find<	343✔
308	Key: Serialize + DeserializeOwned + PartialEq + Ord + Clone,
309	Value: NodeValue + Clone,
310	>(
311	load_tree: &(dyn LoadTree + Send + Sync),
312	root: &BlobDigest,
313	key: &Key,
314	) -> Option<Value> {
315	let node = match load_node::<Key, Value>(load_tree, root).await {	1,715✔
316	Ok(loaded) => loaded,	686✔
317	Err(_) => todo!(),
318	};
319	node.find(key)	1,029✔
320	}

TyRoXx / NonlocalityOS / 24925290370

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