Merge #1

1: Add Bors r=matthiasbeyer a=matthiasbeyer



Co-authored-by: Matthias Beyer <mail@beyermatthias.de>

12 files changed, 272 insertions, 100 deletions

diff --git a/.builds/debian.yml b/.builds/debian.yml
deleted file mode 100644
index 111f38d..0000000
--- a/.builds/debian.yml
+++ /dev/null
@@ -1,16 +0,0 @@
-image: debian/buster
-sources:
-  - https://git.sr.ht/~matthiasbeyer/daglib
-tasks:
-  - install: curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh -s -- -y --default-toolchain 1.50.0
-  - build: |
-      cd daglib
-      PATH="$HOME/.cargo/bin:$PATH" cargo build --all --all-features
-  - test: |
-      cd daglib
-      PATH="$HOME/.cargo/bin:$PATH" cargo test --all --all-features
-triggers:
-  - action: email
-    condition: always
-    to: mail@beyermatthias.de
-
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
new file mode 100644
index 0000000..f862d27
--- /dev/null
+++ b/.github/workflows/ci.yml
@@ -0,0 +1,111 @@
+name: CI
+
+on:
+  push:
+    branches: [master, staging, trying, release-*]
+  pull_request:
+    branches: [master, release-*]
+
+env:
+  CARGO_TERM_COLOR: always
+
+jobs:
+  check:
+    name: check
+    runs-on: ubuntu-latest
+    strategy:
+      matrix:
+        rust:
+          - 1.60.0
+          - stable
+          - beta
+          # - nightly
+
+    steps:
+      - name: Checkout sources
+        uses: actions/checkout@v3
+      - name: Install toolchain
+        uses: actions-rs/toolchain@v1
+        with:
+          toolchain: ${{ matrix.rust }}
+          override: true
+      - uses: swatinem/rust-cache@v1
+      - name: cargo-check
+        uses: actions-rs/cargo@v1
+        with:
+          command: check
+
+
+  fmt:
+    name: format
+    runs-on: ubuntu-latest
+
+    steps:
+      - uses: actions/checkout@v3
+      - uses: actions-rs/toolchain@v1
+        with:
+          toolchain: 1.60.0
+      - run: rustup component add rustfmt
+      - name: cargo-fmt
+        uses: actions-rs/cargo@v1
+        with:
+          command: fmt
+          args: -- --check
+
+
+  test:
+    name: test
+    runs-on: ubuntu-latest
+    strategy:
+      matrix:
+        rust:
+          - 1.60.0
+          - stable
+          - beta
+          # - nightly
+    steps:
+      - name: Checkout sources
+        uses: actions/checkout@v3
+      - name: Install toolchain
+        uses: actions-rs/toolchain@v1
+        with:
+          toolchain: ${{ matrix.rust }}
+          override: true
+      - uses: swatinem/rust-cache@v1
+      - name: cargo-test
+        uses: actions-rs/cargo@v1
+        with:
+          command: test
+          args: --all --all-features
+
+
+  clippy:
+    name: clippy
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v3
+      - uses: actions-rs/toolchain@v1
+        with:
+          toolchain: 1.60.0
+          override: true
+      - uses: swatinem/rust-cache@v1
+      - run: rustup component add clippy
+      - name: cargo-clippy
+        run: cargo clippy --all --all-targets --all-features -- -D warnings
+
+
+  # We need some "accummulation" job here because bors fails (timeouts) to
+  # listen on matrix builds.
+  # Hence, we have some kind of dummy here that bors can listen on
+  ci-success:
+    name: CI
+    if: ${{ success() }}
+    needs:
+      - check
+      - clippy
+      - fmt
+      - test
+    runs-on: ubuntu-latest
+    steps:
+      - name: CI succeeded
+        run: exit 0
diff --git a/.github/workflows/commit-lint.yml b/.github/workflows/commit-lint.yml
new file mode 100644
index 0000000..5e6e22d
--- /dev/null
+++ b/.github/workflows/commit-lint.yml
@@ -0,0 +1,25 @@
+on:
+  pull_request:
+
+name: Pull Request Checks
+
+jobs:
+  block-fixup:
+    runs-on: ubuntu-latest
+    steps:
+    - uses: actions/checkout@v3
+    - name: Block fixup commit merge
+      uses: 13rac1/block-fixup-merge-action@v2.0.0
+
+  commit-lint:
+    runs-on: ubuntu-latest
+    if: github.event_name == 'pull_request'
+    steps:
+      - uses: actions/checkout@v3
+        with:
+          fetch-depth: 0
+      - uses: actions/setup-python@v4
+        with:
+          python-version: '3.x'
+      - run: pip install gitlint
+      - run: gitlint --commits $(git merge-base origin/master HEAD)..HEAD
diff --git a/.github/workflows/flake-update.yml b/.github/workflows/flake-update.yml
new file mode 100644
index 0000000..bf9aff1
--- /dev/null
+++ b/.github/workflows/flake-update.yml
@@ -0,0 +1,28 @@
+name: "Update flakes"
+
+on:
+  repository_dispatch:
+  workflow_dispatch:
+  schedule:
+    # 01:15 every monday
+    - cron:  '15 1 * * 1'
+
+jobs:
+  lockfile:
+    runs-on: ubuntu-latest
+    steps:
+      - name: Checkout repository
+        uses: actions/checkout@v3
+      - name: Install Nix
+        uses: cachix/install-nix-action@v18
+        with:
+          extra_nix_config: |
+            access-tokens = github.com=${{ secrets.GITHUB_TOKEN }}
+      - name: Update flake.lock
+        uses: DeterminateSystems/update-flake-lock@v14
+        with:
+          pr-title: "Update flake.lock" # Title of PR to be created
+          # pr-labels: |                  # Labels to be set on the PR
+          #   dependencies
+          #   automated
+
diff --git a/bors.toml b/bors.toml
new file mode 100644
index 0000000..c50591c
--- /dev/null
+++ b/bors.toml
@@ -0,0 +1,9 @@
+# Must pass on the merge with the master branch
+status = [
+    "CI"
+]
+
+cut_body_after = "<details>"
+
+delete_merged_branches = true
+
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..36755d2
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1 @@
+# default
diff --git a/src/async_dag.rs b/src/async_dag.rs
index 57ecc16..8b4c595 100644
--- a/src/async_dag.rs
+++ b/src/async_dag.rs
@@ -6,20 +6,21 @@
 
 use std::pin::Pin;
 
-use anyhow::Result;
 use anyhow::anyhow;
+use anyhow::Result;
 use futures::stream::StreamExt;
 use futures::task::Poll;
 
+use crate::DagBackend;
 use crate::Node;
 use crate::NodeId;
-use crate::DagBackend;
 
 /// 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>
+where
+    Id: NodeId + Send,
+    N: Node<Id = Id>,
+    Backend: DagBackend<Id, N>,
 {
     head: Id,
     backend: Backend,
@@ -27,24 +28,20 @@ pub struct AsyncDag<Id, N, Backend>
 }
 
 impl<Id, N, Backend> AsyncDag<Id, N, Backend>
-    where Id: NodeId + Send,
-          N: Node<Id = Id>,
-          Backend: DagBackend<Id, N>
+where
+    Id: NodeId + Send,
+    N: Node<Id = Id>,
+    Backend: DagBackend<Id, N>,
 {
     /// 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> {
-        backend
-            .put(head)
-            .await
-            .map(|id| {
-                AsyncDag {
-                    head: id,
-                    backend: backend,
-                    _node: std::marker::PhantomData,
-                }
-            })
+        backend.put(head).await.map(|id| AsyncDag {
+            head: id,
+            backend,
+            _node: std::marker::PhantomData,
+        })
     }
 
     /// Load a AsyncDag object using `head` as HEAD node.
@@ -53,14 +50,13 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
     ///
     /// This fails if backend.get(head) fails.
     pub async fn load(backend: Backend, head: Id) -> Result<Self> {
-        backend.get(head)
+        backend
+            .get(head)
             .await?
-            .map(|(id, _)| {
-                AsyncDag {
-                    head: id,
-                    backend: backend,
-                    _node: std::marker::PhantomData,
-                }
+            .map(|(id, _)| AsyncDag {
+                head: id,
+                backend,
+                _node: std::marker::PhantomData,
             })
             .ok_or_else(|| anyhow!("Node not found"))
     }
@@ -80,18 +76,14 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
     /// Check whether an `id` is in the DAG.
     pub async fn has_id(&self, id: &Id) -> Result<bool> {
         self.stream()
-            .map(|r| -> Result<bool> {
-                r.map(|(ref node_id, _)| node_id == id)
-            })
+            .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),
-                }
+            .fold(Ok(false), |acc, e| match (acc, e) {
+                (Err(e), _) => Err(e),
+                (Ok(_), Err(e)) => Err(e),
+                (Ok(a), Ok(b)) => Ok(a || b),
             })
     }
 
@@ -102,14 +94,14 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
     /// # Warning
     ///
     /// The order of the nodes is not (yet) guaranteed.
-    pub fn stream(&self) -> Stream<Id, N, Backend>  {
+    pub fn stream(&self) -> Stream<Id, N, Backend> {
         Stream {
             dag: self,
             backlog: {
                 let mut v = Vec::with_capacity(2);
                 v.push(self.backend.get(self.head.clone()));
                 v
-            }
+            },
         }
     }
 
@@ -143,7 +135,8 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
     /// 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
+    where
+        Backend: Clone,
     {
         AsyncDag {
             head: self.head.clone(),
@@ -157,7 +150,8 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
     /// 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>
-        where M: Merger<Id, N>
+    where
+        M: Merger<Id, N>,
     {
         let node = merger.create_merge_node(&self.head, &other.head)?;
         let id = self.backend.put(node).await?;
@@ -167,16 +161,18 @@ impl<Id, N, Backend> AsyncDag<Id, N, Backend>
 }
 
 pub trait Merger<Id, N>
-    where Id: NodeId,
-          N: Node<Id = Id>
+where
+    Id: NodeId,
+    N: Node<Id = Id>,
 {
     fn create_merge_node(&self, left_id: &Id, right_id: &Id) -> Result<N>;
 }
 
 impl<Id, N, F> Merger<Id, N> for F
-    where Id: NodeId,
-          N: Node<Id = Id>,
-          F: Fn(&Id, &Id) -> Result<N>,
+where
+    Id: NodeId,
+    N: Node<Id = Id>,
+    F: Fn(&Id, &Id) -> Result<N>,
 {
     fn create_merge_node(&self, left_id: &Id, right_id: &Id) -> Result<N> {
         (self)(left_id, right_id)
@@ -185,22 +181,30 @@ impl<Id, N, F> Merger<Id, N> for F
 
 /// Stream adapter for streaming all nodes in a DAG
 pub struct Stream<'a, Id, N, Backend>
-    where Id: NodeId + Send,
-          N: Node<Id = Id>,
-          Backend: DagBackend<Id, N>
+where
+    Id: NodeId + Send,
+    N: Node<Id = Id>,
+    Backend: DagBackend<Id, N>,
 {
     dag: &'a AsyncDag<Id, N, Backend>,
-    backlog: Vec<Pin<Box<(dyn futures::future::Future<Output = Result<Option<(Id, N)>>> + std::marker::Send + 'a)>>>,
+    backlog: Vec<Pin<Backlog<'a, Id, N>>>,
 }
 
+pub type Backlog<'a, Id, N> =
+    Box<(dyn futures::future::Future<Output = Result<Option<(Id, N)>>> + std::marker::Send + 'a)>;
+
 impl<'a, Id, N, Backend> futures::stream::Stream for Stream<'a, Id, N, Backend>
-    where Id: NodeId + Send,
-          N: Node<Id = Id>,
-          Backend: DagBackend<Id, N>
+where
+    Id: NodeId + Send,
+    N: Node<Id = Id>,
+    Backend: DagBackend<Id, N>,
 {
     type Item = Result<(Id, N)>;
 
-    fn poll_next(mut self: std::pin::Pin<&mut Self>, cx: &mut futures::task::Context<'_>) -> futures::task::Poll<Option<Self::Item>> {
+    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))),
@@ -210,14 +214,14 @@ impl<'a, Id, N, Backend> futures::stream::Stream for Stream<'a, Id, N, Backend>
                         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
@@ -229,16 +233,15 @@ impl<'a, Id, N, Backend> futures::stream::Stream for Stream<'a, Id, N, Backend>
     }
 }
 
-
 #[cfg(test)]
 mod tests {
 
     use anyhow::Result;
     use futures::StreamExt;
 
-    use crate::DagBackend;
-    use crate::AsyncDag;
     use crate::test_impl as test;
+    use crate::AsyncDag;
+    use crate::DagBackend;
 
     #[test]
     fn test_dag_two_nodes() {
@@ -254,9 +257,7 @@ mod tests {
                     data: 0,
                 })
             },
-            {
-                Some(head.clone())
-            },
+            { Some(head.clone()) },
         ]);
 
         {
@@ -297,9 +298,7 @@ mod tests {
                     data: 0,
                 })
             },
-            {
-                Some(head.clone())
-            },
+            { Some(head.clone()) },
         ]);
 
         let dag = tokio_test::block_on(AsyncDag::new(b, head));
@@ -341,11 +340,25 @@ mod tests {
         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!(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));
+        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]
@@ -432,9 +445,13 @@ mod tests {
 
         struct M;
         impl super::Merger<test::Id, test::Node> for M {
-            fn create_merge_node(&self, left_id: &test::Id, right_id: &test::Id) -> Result<test::Node> {
+            fn create_merge_node(
+                &self,
+                left_id: &test::Id,
+                right_id: &test::Id,
+            ) -> Result<test::Node> {
                 Ok(test::Node {
-                    parents: vec![left_id.clone(), right_id.clone()],
+                    parents: vec![*left_id, *right_id],
                     data: 3,
                 })
             }
@@ -495,12 +512,15 @@ mod tests {
             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.clone(), right_id.clone()],
-                data: 3,
-            })
-        }));
+        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();
 
@@ -508,4 +528,3 @@ mod tests {
         assert_eq!(dag.head, test::Id(3));
     }
 }
-
diff --git a/src/dag_backend.rs b/src/dag_backend.rs
index b3077c4..2be9736 100644
--- a/src/dag_backend.rs
+++ b/src/dag_backend.rs
@@ -7,8 +7,8 @@
 use anyhow::Result;
 use async_trait::async_trait;
 
-use crate::NodeId;
 use crate::Node;
+use crate::NodeId;
 
 /// An interface to a DAG backend storage
 ///
@@ -16,10 +16,10 @@ use crate::Node;
 /// (`DagBackend::get`) nodes.
 #[async_trait]
 pub trait DagBackend<Id, N>
-    where N: Node,
-          Id: NodeId + Send
+where
+    N: Node,
+    Id: NodeId + Send,
 {
-
     /// Get a `Node` from the backend that is identified by `id`
     ///
     /// # Returns
@@ -102,5 +102,4 @@ mod tests {
             assert!(node.is_none());
         }
     }
-
 }
diff --git a/src/lib.rs b/src/lib.rs
index 655cef1..bcb6ae0 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -18,4 +18,3 @@ pub use node_id::*;
 
 #[cfg(test)]
 mod test_impl;
-
diff --git a/src/node.rs b/src/node.rs
index 794c4af..58515a8 100644
--- a/src/node.rs
+++ b/src/node.rs
@@ -11,4 +11,3 @@ 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
index 6211e19..df1e4d4 100644
--- a/src/node_id.rs
+++ b/src/node_id.rs
@@ -7,5 +7,4 @@
 /// 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 {
-}
+pub trait NodeId: Clone + Eq + PartialEq {}
diff --git a/src/test_impl.rs b/src/test_impl.rs
index 672c3fc..a95c4c6 100644
--- a/src/test_impl.rs
+++ b/src/test_impl.rs
@@ -64,4 +64,3 @@ impl crate::DagBackend<Id, Node> for Backend {
         Ok(Id(idx))
     }
 }
-