diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/async_dag.rs | 542 | ||||
| -rw-r--r-- | src/dag_backend.rs | 106 | ||||
| -rw-r--r-- | src/error.rs | 11 | ||||
| -rw-r--r-- | src/id.rs | 18 | ||||
| -rw-r--r-- | src/lib.rs | 20 | ||||
| -rw-r--r-- | src/node.rs | 36 | ||||
| -rw-r--r-- | src/node_id.rs | 10 | ||||
| -rw-r--r-- | src/repository.rs | 26 | ||||
| -rw-r--r-- | src/test_impl.rs | 79 |
9 files changed, 770 insertions, 78 deletions
diff --git a/src/async_dag.rs b/src/async_dag.rs new file mode 100644 index 0000000..7abc6c5 --- /dev/null +++ b/src/async_dag.rs @@ -0,0 +1,542 @@ +// +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. +// + +use std::pin::Pin; + +use futures::stream::StreamExt; +use futures::task::Poll; + +use crate::DagBackend; +use crate::Node; +use crate::NodeId; + +/// An async DAG, generic over Node, Node identifier and Backend implementation +pub struct AsyncDag<Id, N, Backend> +where + Id: NodeId + Send, + N: Node<Id = Id>, + Backend: DagBackend<Id, N>, +{ + head: Id, + backend: Backend, + _node: std::marker::PhantomData<N>, +} + +impl<Id, N, Backend, Error> AsyncDag<Id, N, Backend> +where + Id: NodeId + Send, + N: Node<Id = Id>, + Backend: DagBackend<Id, N, Error = Error>, + Error: From<crate::Error<Id>>, +{ + /// Create a new DAG with a backend and a HEAD node + /// + /// The head node is `DagBackend::put` into the backend before the AsyncDag object is created. + pub async fn new(mut backend: Backend, head: N) -> Result<Self, Error> { + backend.put(head).await.map(|id| AsyncDag { + head: id, + backend, + _node: std::marker::PhantomData, + }) + } + + /// Load a AsyncDag object using `head` as HEAD node. + /// + /// # Warning + /// + /// This fails if backend.get(head) fails. + pub async fn load(backend: Backend, head: Id) -> Result<Self, Error> { + backend + .get(head.clone()) + .await? + .map(|(id, _)| AsyncDag { + head: id, + backend, + _node: std::marker::PhantomData, + }) + .ok_or_else(|| crate::Error::NodeNotFound(head).into()) + } + + pub fn head(&self) -> &Id { + &self.head + } + + pub fn backend(&self) -> &Backend { + &self.backend + } + + pub fn backend_mut(&mut self) -> &mut Backend { + &mut self.backend + } + + /// Check whether an `id` is in the DAG. + pub async fn has_id(&self, id: &Id) -> Result<bool, Error> { + self.stream() + .map(|r| -> Result<bool, _> { r.map(|(ref node_id, _)| node_id == id) }) + .collect::<Vec<Result<bool, _>>>() + .await + .into_iter() + .fold(Ok(false), |acc, e| match (acc, e) { + (Err(e), _) => Err(e), + (Ok(_), Err(e)) => Err(e), + (Ok(a), Ok(b)) => Ok(a || b), + }) + } + + /// Iterate over the DAG + /// + /// This function returns a Stream over all nodes in the DAG. + /// + /// # Warning + /// + /// The order of the nodes is not (yet) guaranteed. + pub fn stream(&self) -> Stream<Id, N, Backend, Error> { + Stream { + dag: self, + backlog: { + let mut v = Vec::with_capacity(2); + v.push(self.backend.get(self.head.clone())); + v + }, + } + } + + /// Update the HEAD pointer of the DAG + /// + /// # Warning + /// + /// fails if the passed node does not point to the current HEAD in its parents. + pub async fn update_head(&mut self, node: N) -> Result<Id, Error> { + if node.parent_ids().iter().any(|id| id == &self.head) { + self.update_head_unchecked(node).await + } else { + Err(Error::from(crate::Error::HeadNotAParent)) + } + } + + /// Update the HEAD pointer of the DAG, unchecked + /// + /// # Warning + /// + /// Does not check whether the passed `node` does point to the current (then old) HEAD in its + /// parents. Be careful to not lose nodes from the DAG with this. + pub async fn update_head_unchecked(&mut self, node: N) -> Result<Id, Error> { + let id = self.backend.put(node).await?; + self.head = id.clone(); + Ok(id) + } + + /// Branch from the current head. + /// + /// This function creates a new AsyncDag object with the same backend (thus the backend must be + /// `Clone` in this case). + pub fn branch(&self) -> AsyncDag<Id, N, Backend> + where + Backend: Clone, + { + AsyncDag { + head: self.head.clone(), + backend: self.backend.clone(), + _node: std::marker::PhantomData, + } + } + + /// Merge another AsyncDag into this one + /// + /// Use the `merger` function to merge the two head IDs and generate a new Node instance for + /// the new HEAD of `self`. + pub async fn merge<M>( + &mut self, + other: &AsyncDag<Id, N, Backend>, + merger: M, + ) -> Result<Id, Error> + where + M: Merger<Id, N, Error = Error>, + { + let node = merger.create_merge_node(&self.head, &other.head)?; + let id = self.backend.put(node).await?; + self.head = id.clone(); + Ok(id) + } +} + +pub trait Merger<Id, N> +where + Id: NodeId, + N: Node<Id = Id>, +{ + type Error; + + fn create_merge_node(&self, left_id: &Id, right_id: &Id) -> Result<N, Self::Error>; +} + +impl<Id, N, F, Error> Merger<Id, N> for F +where + Id: NodeId, + N: Node<Id = Id>, + F: Fn(&Id, &Id) -> Result<N, Error>, + Error: From<crate::Error<Id>>, +{ + type Error = Error; + + fn create_merge_node(&self, left_id: &Id, right_id: &Id) -> Result<N, Self::Error> { + (self)(left_id, right_id) + } +} + +/// Stream adapter for streaming all nodes in a DAG +pub struct Stream<'a, Id, N, Backend, Error> +where + Id: NodeId + Send, + N: Node<Id = Id>, + Backend: DagBackend<Id, N>, + Error: From<crate::Error<Id>>, +{ + dag: &'a AsyncDag<Id, N, Backend>, + backlog: Vec<Pin<Backlog<'a, Id, N, Error>>>, +} + +pub type Backlog<'a, Id, N, Error> = Box< + (dyn futures::future::Future<Output = Result<Option<(Id, N)>, Error>> + std::marker::Send + 'a), +>; + +impl<'a, Id, N, Backend, Error> futures::stream::Stream for Stream<'a, Id, N, Backend, Error> +where + Id: NodeId + Send, + N: Node<Id = Id>, + Backend: DagBackend<Id, N, Error = Error>, + Error: From<crate::Error<Id>>, +{ + type Item = Result<(Id, N), Error>; + + fn poll_next( + mut self: std::pin::Pin<&mut Self>, + cx: &mut futures::task::Context<'_>, + ) -> futures::task::Poll<Option<Self::Item>> { + if let Some(mut fut) = self.as_mut().backlog.pop() { + match fut.as_mut().poll(cx) { + Poll::Ready(Err(e)) => Poll::Ready(Some(Err(e))), + Poll::Ready(Ok(Some((node_id, node)))) => { + for parent in node.parent_ids().into_iter() { + let fut = self.dag.backend.get(parent.clone()); + self.as_mut().backlog.push(fut); + } + Poll::Ready(Some(Ok((node_id, node)))) + } + Poll::Ready(Ok(None)) => { + // backend.get() returned Ok(None), so the referenced node seems not to exist + // + // TODO: Decide whether we should return an error here. + cx.waker().wake_by_ref(); + Poll::Pending + } + Poll::Pending => { + cx.waker().wake_by_ref(); + Poll::Pending + } + } + } else { + Poll::Ready(None) + } + } +} + +#[cfg(test)] +mod tests { + use futures::StreamExt; + + use crate::test_impl as test; + use crate::test_impl::TestError; + use crate::AsyncDag; + use crate::DagBackend; + + #[test] + fn test_dag_two_nodes() { + let head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + let b = test::Backend::new(vec![ + { + Some(test::Node { + parents: vec![], + data: 0, + }) + }, + { Some(head.clone()) }, + ]); + + { + let node = tokio_test::block_on(b.get(test::Id(1))).unwrap().unwrap(); + assert_eq!(node.1.data, 1); + assert!(!node.1.parents.is_empty()); // to check whether the parent is set + } + + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + let dag = dag.unwrap(); + + { + let has_id = tokio_test::block_on(dag.has_id(&test::Id(0))); + assert!(has_id.is_ok()); + let has_id = has_id.unwrap(); + assert!(has_id); + } + { + let has_id = tokio_test::block_on(dag.has_id(&test::Id(1))); + assert!(has_id.is_ok()); + let has_id = has_id.unwrap(); + assert!(has_id); + } + } + + #[test] + fn test_dag_two_nodes_stream() { + let head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + let b = test::Backend::new(vec![ + { + Some(test::Node { + parents: vec![], + data: 0, + }) + }, + { Some(head.clone()) }, + ]); + + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + let dag = dag.unwrap(); + + let v = tokio_test::block_on(dag.stream().collect::<Vec<_>>()); + + assert_eq!(v.len(), 2, "Expected two nodes: {:?}", v); + assert_eq!(v[0].as_ref().unwrap().0, test::Id(1)); + assert_eq!(v[1].as_ref().unwrap().0, test::Id(0)); + } + + #[test] + fn test_adding_head() { + let head = test::Node { + parents: vec![], + data: 0, + }; + let b = test::Backend::new(vec![Some(head.clone())]); + + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + let mut dag = dag.unwrap(); + + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + assert_eq!(dag.backend.0.read().unwrap().len(), 1); + assert_eq!(dag.head, test::Id(0)); + + let id = tokio_test::block_on(dag.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 2); + assert_eq!(dag.head, test::Id(1)); + + assert_eq!(dag.backend.0.read().unwrap()[0].as_ref().unwrap().data, 0); + assert!(dag.backend.0.read().unwrap()[0] + .as_ref() + .unwrap() + .parents + .is_empty()); + + assert_eq!(dag.backend.0.read().unwrap()[1].as_ref().unwrap().data, 1); + assert_eq!( + dag.backend.0.read().unwrap()[1] + .as_ref() + .unwrap() + .parents + .len(), + 1 + ); + assert_eq!( + dag.backend.0.read().unwrap()[1].as_ref().unwrap().parents[0], + test::Id(0) + ); + } + + #[test] + fn test_branch() { + let mut dag = { + let head = test::Node { + parents: vec![], + data: 0, + }; + let b = test::Backend::new(vec![Some(head.clone())]); + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + dag.unwrap() + }; + + let branched = dag.branch(); + + { + assert_eq!(dag.backend.0.read().unwrap().len(), 1); + assert_eq!(dag.head, test::Id(0)); + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + let id = tokio_test::block_on(dag.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 2); + assert_eq!(dag.head, test::Id(1)); + } + + assert_eq!(branched.backend.0.read().unwrap().len(), 2); + assert_eq!(branched.head, test::Id(0)); + } + + #[test] + fn test_merging() { + let mut dag = { + let head = test::Node { + parents: vec![], + data: 0, + }; + let b = test::Backend::new(vec![Some(head.clone())]); + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + dag.unwrap() + }; + + let mut branched = dag.branch(); + + { + assert_eq!(dag.backend.0.read().unwrap().len(), 1); + assert_eq!(dag.head, test::Id(0)); + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + let id = tokio_test::block_on(dag.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 2); + assert_eq!(dag.head, test::Id(1)); + } + + { + assert_eq!(branched.backend.0.read().unwrap().len(), 2); + assert_eq!(branched.head, test::Id(0)); + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 2, + }; + + let id = tokio_test::block_on(branched.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(branched.backend.0.read().unwrap().len(), 3); + assert_eq!(branched.head, test::Id(2)); + } + + struct M; + impl super::Merger<test::Id, test::Node> for M { + type Error = TestError; + + fn create_merge_node( + &self, + left_id: &test::Id, + right_id: &test::Id, + ) -> Result<test::Node, Self::Error> { + Ok(test::Node { + parents: vec![*left_id, *right_id], + data: 3, + }) + } + } + + let merge = tokio_test::block_on(dag.merge(&branched, M)); + assert!(merge.is_ok()); + let _ = merge.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 4); + assert_eq!(dag.head, test::Id(3)); + } + + #[test] + fn test_merging_merge_fn() { + let mut dag = { + let head = test::Node { + parents: vec![], + data: 0, + }; + let b = test::Backend::new(vec![Some(head.clone())]); + let dag = tokio_test::block_on(AsyncDag::new(b, head)); + assert!(dag.is_ok()); + dag.unwrap() + }; + + let mut branched = dag.branch(); + + { + assert_eq!(dag.backend.0.read().unwrap().len(), 1); + assert_eq!(dag.head, test::Id(0)); + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 1, + }; + + let id = tokio_test::block_on(dag.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 2); + assert_eq!(dag.head, test::Id(1)); + } + + { + assert_eq!(branched.backend.0.read().unwrap().len(), 2); + assert_eq!(branched.head, test::Id(0)); + let new_head = test::Node { + parents: vec![test::Id(0)], + data: 2, + }; + + let id = tokio_test::block_on(branched.update_head(new_head)); + assert!(id.is_ok()); + let _ = id.unwrap(); + + assert_eq!(branched.backend.0.read().unwrap().len(), 3); + assert_eq!(branched.head, test::Id(2)); + } + + let merge = tokio_test::block_on(dag.merge( + &branched, + |left_id: &test::Id, right_id: &test::Id| { + Ok(test::Node { + parents: vec![*left_id, *right_id], + data: 3, + }) + }, + )); + assert!(merge.is_ok()); + let _ = merge.unwrap(); + + assert_eq!(dag.backend.0.read().unwrap().len(), 4); + assert_eq!(dag.head, test::Id(3)); + } +} diff --git a/src/dag_backend.rs b/src/dag_backend.rs new file mode 100644 index 0000000..09dc428 --- /dev/null +++ b/src/dag_backend.rs @@ -0,0 +1,106 @@ +// +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. +// + +use async_trait::async_trait; + +use crate::Node; +use crate::NodeId; + +/// An interface to a DAG backend storage +/// +/// A DAG backend storage is nothing more than a thing that can store (`DagBackend::put`) and load +/// (`DagBackend::get`) nodes. +#[async_trait] +pub trait DagBackend<Id, N> +where + N: Node, + Id: NodeId + Send, +{ + type Error; + + /// Get a `Node` from the backend that is identified by `id` + /// + /// # Returns + /// + /// * Should return Err(_) if the operation failed. + /// * Should return Ok(None) if there is no node that is identified by `id` + /// * Otherwise return the Id along with the node identified by it + async fn get(&self, id: Id) -> Result<Option<(Id, N)>, Self::Error>; + + /// Store a `node` in the backend, returning its `Id` + /// + /// This function should store the `node` in the backend and return the `id` the node has. + async fn put(&mut self, node: N) -> Result<Id, Self::Error>; +} + +#[cfg(test)] +mod tests { + use crate::test_impl as test; + use crate::*; + + #[test] + fn test_backend_get() { + let b = test::Backend::new(vec![Some(test::Node { + parents: vec![], + data: 0, + })]); + + let node = tokio_test::block_on(b.get(test::Id(0))); + assert!(node.is_ok()); + let node = node.unwrap(); + + assert!(node.is_some()); + let node = node.unwrap(); + + assert_eq!(node.0, test::Id(0)); + assert!(node.1.parents.is_empty()); + } + + #[test] + fn test_backend_put() { + let mut b = test::Backend::new(vec![Some(test::Node { + parents: vec![], + data: 0, + })]); + + let _ = tokio_test::block_on(b.put({ + test::Node { + parents: vec![], + data: 1, + } + })); + + { + let node = tokio_test::block_on(b.get(test::Id(0))); + assert!(node.is_ok()); + let node = node.unwrap(); + + assert!(node.is_some()); + let node = node.unwrap(); + + assert_eq!(node.0, test::Id(0)); + assert!(node.1.parents.is_empty()); + } + { + let node = tokio_test::block_on(b.get(test::Id(1))); + assert!(node.is_ok()); + let node = node.unwrap(); + + assert!(node.is_some()); + let node = node.unwrap(); + + assert_eq!(node.0, test::Id(1)); + assert!(node.1.parents.is_empty()); + } + { + let node = tokio_test::block_on(b.get(test::Id(2))); + assert!(node.is_ok()); + let node = node.unwrap(); + + assert!(node.is_none()); + } + } +} diff --git a/src/error.rs b/src/error.rs new file mode 100644 index 0000000..fd91045 --- /dev/null +++ b/src/error.rs @@ -0,0 +1,11 @@ +#[derive(Debug, thiserror::Error)] +pub enum Error<Id> +where + Id: crate::NodeId, +{ + #[error("Node not found: {:?}", .0)] + NodeNotFound(Id), + + #[error("Node does not have HEAD as parent")] + HeadNotAParent, +} diff --git a/src/id.rs b/src/id.rs deleted file mode 100644 index 018ae60..0000000 --- a/src/id.rs +++ /dev/null @@ -1,18 +0,0 @@ -// -// This Source Code Form is subject to the terms of the Mozilla Public -// License, v. 2.0. If a copy of the MPL was not distributed with this -// file, You can obtain one at http://mozilla.org/MPL/2.0/. -// - -use std::fmt::Debug; - -/// An "ID" is an object that can be used to uniquely identify a node in the DAG. -/// -/// In git-speak, this would be a SHA1 hash. -/// -pub trait Id : Clone + Debug + PartialEq + Eq { - - /* empty */ - -} - @@ -4,6 +4,20 @@ // file, You can obtain one at http://mozilla.org/MPL/2.0/. // -pub mod id; -pub mod node; -pub mod repository; +mod async_dag; +pub use async_dag::*; + +mod dag_backend; +pub use dag_backend::*; + +mod node; +pub use node::*; + +mod node_id; +pub use node_id::*; + +mod error; +pub use error::*; + +#[cfg(test)] +mod test_impl; diff --git a/src/node.rs b/src/node.rs index b6a088b..58515a8 100644 --- a/src/node.rs +++ b/src/node.rs @@ -4,36 +4,10 @@ // file, You can obtain one at http://mozilla.org/MPL/2.0/. // -use std::fmt::Debug; +use crate::NodeId; -use crate::id::Id; - -use futures::future::Future; -use futures::stream::Stream; - -/// A "Node" is an object of the (DA)Graph -/// -/// In git-speak, this would be an "Object". -/// -/// -/// # Equality -/// -/// A node might be compared to another node. In git, for example, equality would be the equality -/// of the nodes ids, because objects are non-mutable. -/// -pub trait Node: Debug + PartialEq + Eq { - type Id: Id; - type NodePayload: Debug; - type Error: Debug; - type Payload: Future<Item = Self::NodePayload, Error = Self::Error>; - - /// It should be trivial to get the Id of a Node. - fn id(&self) -> Self::Id; - - /// Fetch the payload of the node. - fn payload(&self) -> Self::Payload; - - /// Fetch the Ids of the parents of this node - fn parent_ids(&self) -> Stream<Item = Self::Id, Error = Self::Error>; +/// A Node in the DAG, holding the data. +pub trait Node { + type Id: NodeId; + fn parent_ids(&self) -> Vec<Self::Id>; } - diff --git a/src/node_id.rs b/src/node_id.rs new file mode 100644 index 0000000..5d0663a --- /dev/null +++ b/src/node_id.rs @@ -0,0 +1,10 @@ +// +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. +// + +/// A unique identifier for a `Node` +/// +/// The `NodeId` should be cheap to clone (for example a UUID or some form of a hash value). +pub trait NodeId: Clone + Eq + PartialEq + std::fmt::Debug {} diff --git a/src/repository.rs b/src/repository.rs deleted file mode 100644 index 57f2d63..0000000 --- a/src/repository.rs +++ /dev/null @@ -1,26 +0,0 @@ -// -// This Source Code Form is subject to the terms of the Mozilla Public -// License, v. 2.0. If a copy of the MPL was not distributed with this -// file, You can obtain one at http://mozilla.org/MPL/2.0/. -// - -use std::fmt::Debug; - -use crate::node; -use crate::id; - -use futures::future::Future; - -/// -pub trait Repository: Debug { - type Id: id::Id; - type Error: Debug; - type Node: node::Node<Id = Self::Id, Error = Self::Error>; - - type Get: Future<Item = Self::Node, Error = Self::Error>; - - /// It should be trivial to get the Id of a Node. - fn get<ID>(id: ID) -> Result<Self::Get, Self::Error> - where ID: id::Id; -} - diff --git a/src/test_impl.rs b/src/test_impl.rs new file mode 100644 index 0000000..c8f2b51 --- /dev/null +++ b/src/test_impl.rs @@ -0,0 +1,79 @@ +// +// This Source Code Form is subject to the terms of the Mozilla Public +// License, v. 2.0. If a copy of the MPL was not distributed with this +// file, You can obtain one at http://mozilla.org/MPL/2.0/. +// + +use std::sync::Arc; +use std::sync::RwLock; + +use async_trait::async_trait; + +#[derive(Debug)] +pub struct TestError; + +impl<Id> From<crate::Error<Id>> for TestError +where + Id: crate::NodeId, +{ + fn from(_ce: crate::Error<Id>) -> Self { + TestError + } +} + +#[derive(Copy, Clone, Eq, PartialEq, std::hash::Hash, Debug)] +pub struct Id(pub(crate) usize); + +impl crate::NodeId for Id {} + +#[derive(Clone, Debug)] +pub struct Node { + pub(crate) parents: Vec<Id>, + // data the node holds, used to create the ID in tests as "hashing" for unique id + pub(crate) data: usize, +} + +impl crate::Node for Node { + type Id = Id; + + fn parent_ids(&self) -> Vec<Self::Id> { + self.parents.clone() + } +} + +/// The backend for the tests +/// +/// This is `Clone` because we can test branching only with a clonable backend. +/// A real backend would not implement the storage itself, but rather a way to retrieve the data +/// from some storage mechansim (think IPFS), and thus `Clone`ing a backend is nothing esotheric. +#[derive(Clone, Debug)] +pub struct Backend(pub(crate) Arc<RwLock<Vec<Option<Node>>>>); + +impl Backend { + pub fn new(v: Vec<Option<Node>>) -> Self { + Backend(Arc::new(RwLock::new(v))) + } +} + +#[async_trait] +impl crate::DagBackend<Id, Node> for Backend { + type Error = TestError; + + async fn get(&self, id: Id) -> Result<Option<(Id, Node)>, Self::Error> { + if self.0.read().unwrap().len() < id.0 + 1 { + Ok(None) + } else { + Ok(self.0.read().unwrap()[id.0].clone().map(|node| (id, node))) + } + } + + async fn put(&mut self, node: Node) -> Result<Id, Self::Error> { + while self.0.read().unwrap().len() < node.data + 1 { + self.0.write().unwrap().push(None) + } + + let idx = node.data; + self.0.write().unwrap()[idx] = Some(node); + Ok(Id(idx)) + } +} |