From 412d3e81d757038bd5d8bb15e4f4ceba9f5acd6e Mon Sep 17 00:00:00 2001 From: Matthias Beyer Date: Sun, 4 Apr 2021 16:30:23 +0200 Subject: Remove Node::id() requirement A `Node` instance should not need to know about its id, because this would restrict us in case of IPFS, where we know the ID only _after_ adding the data to the storage. This commit thus removes the requirement `Node::id()`. The interface `DagBackend::get()` now returns the `NodeId` for the `Node` as well. This is mostly because it makes the implementation of `AsyncDag` less complicated. Signed-off-by: Matthias Beyer Tested-by: Matthias Beyer --- src/async_dag.rs | 79 +++++++++++++++++++++++------------------------------- src/dag_backend.rs | 29 ++++++++------------ src/node.rs | 2 -- src/test_impl.rs | 16 +++++------ 4 files changed, 51 insertions(+), 75 deletions(-) diff --git a/src/async_dag.rs b/src/async_dag.rs index 66d79fc..651b91d 100644 --- a/src/async_dag.rs +++ b/src/async_dag.rs @@ -32,25 +32,26 @@ impl AsyncDag Backend: DagBackend { /// Create a new DAG with a backend and a HEAD node - pub async fn new(backend: Backend, head: N) -> Result { + /// + /// 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 { backend - .get(head.id().clone()) - .await? - .map(|node| { + .put(head) + .await + .map(|id| { AsyncDag { - head: node.id().clone(), + head: id, backend: backend, _node: std::marker::PhantomData, } }) - .ok_or_else(|| anyhow!("Head not found in backend")) } /// Check whether an `id` is in the DAG. pub async fn has_id(&self, id: &Id) -> Result { self.stream() .map(|r| -> Result { - r.map(|node| node.id() == id) + r.map(|(ref node_id, _)| node_id == id) }) .collect::>>() .await @@ -68,6 +69,7 @@ impl AsyncDag self.backend .get(id) .await? + .map(|tpl| tpl.1) .ok_or_else(|| anyhow!("ID Not found"))? .parent_ids() .into_iter() @@ -82,6 +84,7 @@ impl AsyncDag .await .into_iter() .filter_map(|o| o) + .map(|r| r.map(|tpl| tpl.1)) .collect() } @@ -170,7 +173,7 @@ pub struct Stream<'a, Id, N, Backend> Backend: DagBackend { dag: &'a AsyncDag, - backlog: Vec>> + std::marker::Send + 'a)>>>, + backlog: Vec>> + std::marker::Send + 'a)>>>, } impl<'a, Id, N, Backend> futures::stream::Stream for Stream<'a, Id, N, Backend> @@ -178,18 +181,18 @@ impl<'a, Id, N, Backend> futures::stream::Stream for Stream<'a, Id, N, Backend> N: Node, Backend: DagBackend { - type Item = Result; + type Item = Result<(Id, N)>; fn poll_next(mut self: std::pin::Pin<&mut Self>, cx: &mut futures::task::Context<'_>) -> futures::task::Poll> { 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))) => { + Poll::Ready(Ok(Some((node_id, node)))) => { for parent in node.parent_ids().into_iter() { - let fut = self.dag.backend.get(parent); + let fut = self.dag.backend.get(parent.clone()); self.as_mut().backlog.push(fut); } - Poll::Ready(Some(Ok(node))) + Poll::Ready(Some(Ok((node_id, node)))) }, Poll::Ready(Ok(None)) => { // backend.get() returned Ok(None), so the referenced node seems not to exist @@ -227,17 +230,15 @@ mod tests { #[test] fn test_dag_two_nodes() { let head = test::Node { - id: test::Id(1), parents: vec![test::Id(0)], - data: 43, + data: 1, }; let b = test::Backend::new(vec![ { Some(test::Node { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, }) }, { @@ -247,9 +248,8 @@ mod tests { { let node = tokio_test::block_on(b.get(test::Id(1))).unwrap().unwrap(); - assert_eq!(node.data, 43); - assert_eq!(node.id, test::Id(1)); - assert!(!node.parents.is_empty()); // to check whether the parent is set + 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)); @@ -277,8 +277,7 @@ mod tests { let node = next.pop(); assert!(node.is_some()); let node = node.unwrap(); - assert_eq!(node.id, test::Id(0)); - assert_eq!(node.data, 42); + assert_eq!(node.data, 0); assert!(node.parents.is_empty()); } } @@ -286,17 +285,15 @@ mod tests { #[test] fn test_dag_two_nodes_stream() { let head = test::Node { - id: test::Id(1), parents: vec![test::Id(0)], - data: 43, + data: 1, }; let b = test::Backend::new(vec![ { Some(test::Node { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, }) }, { @@ -311,16 +308,15 @@ mod tests { let v = tokio_test::block_on(dag.stream().collect::>()); assert_eq!(v.len(), 2, "Expected two nodes: {:?}", v); - assert_eq!(v[0].as_ref().unwrap().id, test::Id(1)); - assert_eq!(v[1].as_ref().unwrap().id, test::Id(0)); + 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 { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, }; let b = test::Backend::new(vec![Some(head.clone())]); @@ -329,9 +325,8 @@ mod tests { let mut dag = dag.unwrap(); let new_head = test::Node { - id: test::Id(1), parents: vec![test::Id(0)], - data: 43, + data: 1, }; assert_eq!(dag.backend.0.read().unwrap().len(), 1); @@ -344,10 +339,10 @@ mod tests { 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().id, test::Id(0)); + 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().id, test::Id(1)); + 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)); } @@ -356,9 +351,8 @@ mod tests { fn test_branch() { let mut dag = { let head = test::Node { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, }; let b = test::Backend::new(vec![Some(head.clone())]); let dag = tokio_test::block_on(AsyncDag::new(b, head)); @@ -372,9 +366,8 @@ mod tests { assert_eq!(dag.backend.0.read().unwrap().len(), 1); assert_eq!(dag.head, test::Id(0)); let new_head = test::Node { - id: test::Id(1), parents: vec![test::Id(0)], - data: 43, + data: 1, }; let id = tokio_test::block_on(dag.update_head(new_head)); @@ -393,9 +386,8 @@ mod tests { fn test_merging() { let mut dag = { let head = test::Node { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, }; let b = test::Backend::new(vec![Some(head.clone())]); let dag = tokio_test::block_on(AsyncDag::new(b, head)); @@ -409,9 +401,8 @@ mod tests { assert_eq!(dag.backend.0.read().unwrap().len(), 1); assert_eq!(dag.head, test::Id(0)); let new_head = test::Node { - id: test::Id(1), parents: vec![test::Id(0)], - data: 43, + data: 1, }; let id = tokio_test::block_on(dag.update_head(new_head)); @@ -426,9 +417,8 @@ mod tests { assert_eq!(branched.backend.0.read().unwrap().len(), 2); assert_eq!(branched.head, test::Id(0)); let new_head = test::Node { - id: test::Id(2), parents: vec![test::Id(0)], - data: 44, + data: 2, }; let id = tokio_test::block_on(branched.update_head(new_head)); @@ -443,9 +433,8 @@ mod tests { impl super::Merger for M { fn create_merge_node(&self, left_id: &test::Id, right_id: &test::Id) -> Result { Ok(test::Node { - id: test::Id(3), parents: vec![left_id.clone(), right_id.clone()], - data: 45, + data: 3, }) } } diff --git a/src/dag_backend.rs b/src/dag_backend.rs index 62b2cef..bfc75f8 100644 --- a/src/dag_backend.rs +++ b/src/dag_backend.rs @@ -26,9 +26,8 @@ pub trait DagBackend /// /// * Should return Err(_) if the operation failed. /// * Should return Ok(None) if there is no node that is identified by `id` - /// - /// Otherwise Ok(Some(node)). - async fn get(&self, id: Id) -> Result>; + /// * Otherwise return the Id along with the node identified by it + async fn get(&self, id: Id) -> Result>; /// Store a `node` in the backend, returning its `Id` /// @@ -51,9 +50,8 @@ mod tests { #[test] fn test_backend_get() { let b = test::Backend::new(vec![Some(test::Node { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, })]); let node = tokio_test::block_on(b.get(test::Id(0))); @@ -63,24 +61,21 @@ mod tests { assert!(node.is_some()); let node = node.unwrap(); - assert_eq!(node.data, 42); - assert_eq!(node.id, test::Id(0)); - assert!(node.parents.is_empty()); + 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 { - id: test::Id(0), parents: vec![], - data: 42, + data: 0, })]); let id = tokio_test::block_on(b.put({ test::Node { - id: test::Id(1), parents: vec![], - data: 43, + data: 1, } })); @@ -92,9 +87,8 @@ mod tests { assert!(node.is_some()); let node = node.unwrap(); - assert_eq!(node.data, 42); - assert_eq!(node.id, test::Id(0)); - assert!(node.parents.is_empty()); + assert_eq!(node.0, test::Id(0)); + assert!(node.1.parents.is_empty()); } { let node = tokio_test::block_on(b.get(test::Id(1))); @@ -104,9 +98,8 @@ mod tests { assert!(node.is_some()); let node = node.unwrap(); - assert_eq!(node.data, 43); - assert_eq!(node.id, test::Id(1)); - assert!(node.parents.is_empty()); + assert_eq!(node.0, test::Id(1)); + assert!(node.1.parents.is_empty()); } { let node = tokio_test::block_on(b.get(test::Id(2))); diff --git a/src/node.rs b/src/node.rs index da57fb8..794c4af 100644 --- a/src/node.rs +++ b/src/node.rs @@ -9,8 +9,6 @@ use crate::NodeId; /// A Node in the DAG, holding the data. pub trait Node { type Id: NodeId; - - fn id(&self) -> &Self::Id; fn parent_ids(&self) -> Vec; } diff --git a/src/test_impl.rs b/src/test_impl.rs index cd6dd26..672c3fc 100644 --- a/src/test_impl.rs +++ b/src/test_impl.rs @@ -17,18 +17,14 @@ impl crate::NodeId for Id {} #[derive(Clone, Debug)] pub struct Node { - pub(crate) id: Id, pub(crate) parents: Vec, - pub(crate) data: u8, + // 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 id(&self) -> &Self::Id { - &self.id - } - fn parent_ids(&self) -> Vec { self.parents.clone() } @@ -50,20 +46,20 @@ impl Backend { #[async_trait] impl crate::DagBackend for Backend { - async fn get(&self, id: Id) -> Result> { + async fn get(&self, id: Id) -> Result> { if self.0.read().unwrap().len() < id.0 + 1 { Ok(None) } else { - Ok(self.0.read().unwrap()[id.0].clone()) + Ok(self.0.read().unwrap()[id.0].clone().map(|node| (id, node))) } } async fn put(&mut self, node: Node) -> Result { - while self.0.read().unwrap().len() < node.id.0 + 1 { + while self.0.read().unwrap().len() < node.data + 1 { self.0.write().unwrap().push(None) } - let idx = node.id.0; + let idx = node.data; self.0.write().unwrap()[idx] = Some(node); Ok(Id(idx)) } -- cgit v1.2.3