rad:z3gqcJUoA1n9HaHKufZs5FCSGazv5 heartwoodb4f2614d6c2fefa2b8721e815d63323697a9846d
{
"request": "trigger",
"version": 1,
"event_type": "patch",
"repository": {
"id": "rad:z3gqcJUoA1n9HaHKufZs5FCSGazv5",
"name": "heartwood",
"description": "Radicle Heartwood Protocol & Stack",
"private": false,
"default_branch": "master",
"delegates": [
"did:key:z6MksFqXN3Yhqk8pTJdUGLwATkRfQvwZXPqR2qMEhbS9wzpT",
"did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"did:key:z6MkkPvBfjP4bQmco5Dm7UGsX2ruDBieEHi8n9DVJWX5sTEz"
]
},
"action": "Created",
"patch": {
"id": "8c740a45593d8b2495277def5caf1896a22b4695",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"title": "cob: provide stable ordering of concurrent values",
"state": {
"status": "merged",
"conflicts": []
},
"before": "de1958fab04a95f73b7d7dcc62d66775d0854fc1",
"after": "b4f2614d6c2fefa2b8721e815d63323697a9846d",
"commits": [
"b4f2614d6c2fefa2b8721e815d63323697a9846d"
],
"target": "3fc92f83fe089263c470b328414d923227cf0e4a",
"labels": [],
"assignees": [],
"revisions": [
{
"id": "8c740a45593d8b2495277def5caf1896a22b4695",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"description": "The underlying `Dag` for a COB will use the `Ord` implementation of\nwhatever is provided as the key. This means that the lexicographical\nordering of the `Oid` SHA will be used, which in turn means that if\nthe SHAs change in our tests, then the ordering will be broken for\nconcurrent updates.\n\nTo prevent this from happening, a new key is used `EntryKey`, which is\nthe combination of an `Oid` and a `Timestamp` -- the commit\ntimestamp. The key is used in place of `EntryId` as the `Dag` key.\n\nThis introduction meant that in some places it was necessary to have a\nway of getting the timestamp of an `EntryId`. The `TimestampOf` trait\nis used in these cases, which means that some infallible functions\nbecame fallible.",
"base": "855327d303566aac1d3e065d4ba7e16d9ccd18e6",
"oid": "00e670eb3262f38bfffad711d8642875e1170434",
"timestamp": 1729087831
},
{
"id": "af29ca7e8977ee42aa4017e765d2cf0bbc56e517",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"description": "Changes:\n- rebased\n- changed commit message to use the terminology \"chronlogical\n ordering\" rather than \"stable ordering\"",
"base": "f83c11674287d4f56c43daac74d7461abfc0ddde",
"oid": "e2fd86a77d154b29249ab8fbb6314fc1b68d6d4a",
"timestamp": 1729584404
},
{
"id": "c378998c99d4356714c55fe86111c822b658f866",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"description": "Changes:\n- Approach the problem from the `Dag` API, introducing a `prune_by`\n method which is used in place of `prune`, and allows us to dictate\n the ordering based on the key and value pairs.",
"base": "de1958fab04a95f73b7d7dcc62d66775d0854fc1",
"oid": "c83b9bf326bf9c4a09d8b872e41d90ce50e8b24c",
"timestamp": 1729678044
},
{
"id": "f6b2c5110741b776655eca8228ec66de40b7243d",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"description": "Changes:\n- Reverting some erroneuous changes",
"base": "de1958fab04a95f73b7d7dcc62d66775d0854fc1",
"oid": "7ff426a2d477b3545ad19b29394ce43bb23cf356",
"timestamp": 1729678179
},
{
"id": "244fb1f61b0b0dc00962b0af181e30fa972ed8a6",
"author": {
"id": "did:key:z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM",
"alias": null
},
"description": "Changes:\n- Add test for `prune_by`\n- Do not take `ordering` by reference in `prune_by`",
"base": "de1958fab04a95f73b7d7dcc62d66775d0854fc1",
"oid": "b4f2614d6c2fefa2b8721e815d63323697a9846d",
"timestamp": 1729685077
}
]
}
}
{
"response": "triggered",
"run_id": {
"id": "ad1ad3b1-abf7-4863-b74a-129e00b79a28"
},
"info_url": "https://cci.rad.levitte.org//ad1ad3b1-abf7-4863-b74a-129e00b79a28.html"
}
Started at: 2026-09-08 00:21:58.047259+02:00
Commands:
$ rad clone rad:z3gqcJUoA1n9HaHKufZs5FCSGazv5 .
✓ Creating checkout in ./...
✓ Remote cloudhead@z6MksFqXN3Yhqk8pTJdUGLwATkRfQvwZXPqR2qMEhbS9wzpT added
✓ Remote-tracking branch cloudhead@z6MksFqXN3Yhqk8pTJdUGLwATkRfQvwZXPqR2qMEhbS9wzpT/master created for z6MksFqXN3Yhqk8pTJdUGLwATkRfQvwZXPqR2qMEhbS9wzpT
✓ Remote fintohaps@z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM added
✓ Remote-tracking branch fintohaps@z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM/master created for z6MkireRatUThvd3qzfKht1S44wpm4FEWSSa4PRMTSQZ3voM
✓ Remote lorenz@z6MkkPvBfjP4bQmco5Dm7UGsX2ruDBieEHi8n9DVJWX5sTEz added
✓ Remote-tracking branch lorenz@z6MkkPvBfjP4bQmco5Dm7UGsX2ruDBieEHi8n9DVJWX5sTEz/master created for z6MkkPvBfjP4bQmco5Dm7UGsX2ruDBieEHi8n9DVJWX5sTEz
✓ Repository successfully cloned under /opt/radcis/ci.rad.levitte.org/cci/state/ad1ad3b1-abf7-4863-b74a-129e00b79a28/w/
╭────────────────────────────────────╮
│ heartwood │
│ Radicle Heartwood Protocol & Stack │
│ 189 issues · 38 patches │
╰────────────────────────────────────╯
Run `cd ./.` to go to the repository directory.
Exit code: 0
$ rad patch checkout 8c740a45593d8b2495277def5caf1896a22b4695
✓ Switched to branch patch/8c740a4 at revision 244fb1f
✓ Branch patch/8c740a4 setup to track rad/patches/8c740a45593d8b2495277def5caf1896a22b4695
Exit code: 0
$ git config advice.detachedHead false
Exit code: 0
$ git checkout b4f2614d6c2fefa2b8721e815d63323697a9846d
HEAD is now at b4f2614d cob: chronological ordering of concurrent values
Exit code: 0
$ rad patch show 8c740a45593d8b2495277def5caf1896a22b4695 -p
╭───────────────────────────────────────────────────────────────────────────────╮
│ Title cob: provide stable ordering of concurrent values │
│ Patch 8c740a45593d8b2495277def5caf1896a22b4695 │
│ Author fintohaps z6Mkire…SQZ3voM │
│ Head b4f2614d6c2fefa2b8721e815d63323697a9846d │
│ Base de1958fab04a95f73b7d7dcc62d66775d0854fc1 │
│ Target master │
│ Branches patch/8c740a4 │
│ Commits ahead 0, behind 1179 │
│ Status merged │
│ │
│ The underlying `Dag` for a COB will use the `Ord` implementation of │
│ whatever is provided as the key. This means that the lexicographical │
│ ordering of the `Oid` SHA will be used, which in turn means that if │
│ the SHAs change in our tests, then the ordering will be broken for │
│ concurrent updates. │
│ │
│ To prevent this from happening, a new key is used `EntryKey`, which is │
│ the combination of an `Oid` and a `Timestamp` -- the commit │
│ timestamp. The key is used in place of `EntryId` as the `Dag` key. │
│ │
│ This introduction meant that in some places it was necessary to have a │
│ way of getting the timestamp of an `EntryId`. The `TimestampOf` trait │
│ is used in these cases, which means that some infallible functions │
│ became fallible. │
├───────────────────────────────────────────────────────────────────────────────┤
│ b4f2614 cob: chronological ordering of concurrent values │
├───────────────────────────────────────────────────────────────────────────────┤
│ ● Revision 8c740a4 @ 855327d..00e670e by fintohaps z6Mkire…SQZ3voM 1 year ago │
│ ↑ Revision af29ca7 @ f83c116..e2fd86a by fintohaps z6Mkire…SQZ3voM 1 year ago │
│ ↑ Revision c378998 @ de1958f..c83b9bf by fintohaps z6Mkire…SQZ3voM 1 year ago │
│ ↑ Revision f6b2c51 @ de1958f..7ff426a by fintohaps z6Mkire…SQZ3voM 1 year ago │
│ ↑ Revision 244fb1f @ de1958f..b4f2614 by fintohaps z6Mkire…SQZ3voM 1 year ago │
│ └─ ✓ merged @ a838c3e by cloudhead z6MksFq…bS9wzpT 1 year ago │
╰───────────────────────────────────────────────────────────────────────────────╯
commit b4f2614d6c2fefa2b8721e815d63323697a9846d
Author: Fintan Halpenny <fintan.halpenny@gmail.com>
Date: Wed Oct 23 10:25:34 2024 +0100
cob: chronological ordering of concurrent values
The underlying `Dag` for a COB will use the `Ord` implementation of
whatever is provided as the key. This means that the lexicographical
ordering of the `Oid` SHA will be used, which in turn means that if
the SHAs change in our tests, then the ordering will be broken for
concurrent updates.
To prevent this from happening, a variant of the `prune` method is
introduced that takes an ordering of the keys and values – this method
being called `prune_by`.
This allows `prune` to be replaced with `prune_by` in the
`ChangeGraph::evaluate` method. The ordering used is first comparing
the `Entry::timestamp` and then the `EntryId` (`Oid`).
diff --git a/radicle-cob/src/change_graph.rs b/radicle-cob/src/change_graph.rs
index a1fd62afa..8cfcd2b12 100644
--- a/radicle-cob/src/change_graph.rs
+++ b/radicle-cob/src/change_graph.rs
@@ -1,7 +1,7 @@
// Copyright © 2021 The Radicle Link Contributors
-use std::collections::BTreeSet;
use std::ops::ControlFlow;
+use std::{cmp::Ordering, collections::BTreeSet};
use git_ext::Oid;
use radicle_dag::Dag;
@@ -113,20 +113,24 @@ impl ChangeGraph {
let manifest = root.manifest.clone();
let root = root.id;
- self.graph.prune(&children, |_, entry, siblings| {
- // Check the entry signatures are valid.
- if !entry.valid_signatures() {
- return ControlFlow::Break(());
- }
- // Apply the entry to the state, and if there's an error, prune that branch.
- if object
- .apply(entry, siblings.map(|(k, n)| (k, &n.value)), store)
- .is_err()
- {
- return ControlFlow::Break(());
- }
- ControlFlow::Continue(())
- });
+ self.graph.prune_by(
+ &children,
+ |_, entry, siblings| {
+ // Check the entry signatures are valid.
+ if !entry.valid_signatures() {
+ return ControlFlow::Break(());
+ }
+ // Apply the entry to the state, and if there's an error, prune that branch.
+ if object
+ .apply(entry, siblings.map(|(k, n)| (k, &n.value)), store)
+ .is_err()
+ {
+ return ControlFlow::Break(());
+ }
+ ControlFlow::Continue(())
+ },
+ Self::chronological,
+ );
Ok(CollaborativeObject {
manifest,
@@ -144,6 +148,10 @@ impl ChangeGraph {
pub(crate) fn number_of_nodes(&self) -> usize {
self.graph.len()
}
+
+ fn chronological(x: (&Oid, &Entry), y: (&Oid, &Entry)) -> Ordering {
+ x.1.timestamp.cmp(&y.1.timestamp).then(x.0.cmp(y.0))
+ }
}
struct GraphBuilder {
diff --git a/radicle-dag/src/lib.rs b/radicle-dag/src/lib.rs
index 8c590bffd..923e7274a 100644
--- a/radicle-dag/src/lib.rs
+++ b/radicle-dag/src/lib.rs
@@ -201,19 +201,38 @@ impl<K: Ord + Copy, V> Dag<K, V> {
/// To continue traversing a branch, return [`ControlFlow::Continue`] from the
/// filter function. To stop traversal of a branch and prune it,
/// return [`ControlFlow::Break`].
- pub fn prune<F>(&mut self, roots: &[K], mut filter: F)
+ pub fn prune<F>(&mut self, roots: &[K], filter: F)
where
F: for<'r> FnMut(
&'r K,
&'r Node<K, V>,
Box<dyn Iterator<Item = (&'r K, &'r Node<K, V>)> + 'r>,
) -> ControlFlow<()>,
+ {
+ self.prune_by(roots, filter, |(k1, _), (k2, _)| k1.cmp(k2))
+ }
+
+ /// Fold over the graph in the order provided by `order`, pruning branches
+ /// along the way.
+ /// This is a depth-first traversal.
+ ///
+ /// To continue traversing a branch, return [`ControlFlow::Continue`] from the
+ /// filter function. To stop traversal of a branch and prune it,
+ /// return [`ControlFlow::Break`].
+ pub fn prune_by<F, P>(&mut self, roots: &[K], mut filter: F, ordering: P)
+ where
+ F: for<'r> FnMut(
+ &'r K,
+ &'r Node<K, V>,
+ Box<dyn Iterator<Item = (&'r K, &'r Node<K, V>)> + 'r>,
+ ) -> ControlFlow<()>,
+ P: Fn((&K, &V), (&K, &V)) -> Ordering,
{
let mut visited = BTreeSet::new();
let mut result = VecDeque::new();
for root in roots {
- self.visit(root, &mut visited, &mut result);
+ self.visit_by(root, &mut visited, &mut result, &ordering);
}
for next in result {
@@ -369,6 +388,32 @@ impl<K: Ord + Copy, V> Dag<K, V> {
order.push_front(*key);
}
}
+
+ /// Add nodes recursively to the provided ordering, starting from the given node.
+ fn visit_by(
+ &self,
+ key: &K,
+ visited: &mut BTreeSet<K>,
+ order: &mut VecDeque<K>,
+ ordering: &impl Fn((&K, &V), (&K, &V)) -> Ordering,
+ ) {
+ if visited.insert(*key) {
+ // Recursively visit all of the node's dependents.
+ if let Some(node) = self.graph.get(key) {
+ let mut dependents: Vec<&Node<K, V>> = node
+ .dependents
+ .iter()
+ .filter_map(|k| self.get(k))
+ .collect::<Vec<_>>();
+ dependents.sort_by(|x, y| ordering((&x.key, &x.value), (&y.key, &y.value)));
+ for dependent in dependents.iter().rev() {
+ self.visit_by(&dependent.key, visited, order, ordering);
+ }
+ }
+ // Add the node to the topological order.
+ order.push_front(*key);
+ }
+ }
}
impl<K: Ord + Copy + fmt::Display, V> Dag<K, V> {
@@ -915,4 +960,64 @@ mod tests {
});
assert_eq!(order, dag.sorted());
}
+
+ #[test]
+ fn test_prune_by_sorting() {
+ let mut dag = Dag::new();
+
+ dag.node("R", 0);
+ dag.node("A1", 1);
+ dag.node("A2", 2);
+ dag.node("A3", 3);
+ dag.node("B1", 1);
+ dag.node("B2", 2);
+ dag.node("B3", 3);
+ dag.node("C1", 1);
+
+ dag.dependency("A1", "R");
+ dag.dependency("A2", "R");
+ dag.dependency("A3", "R");
+
+ dag.dependency("B1", "A1");
+ dag.dependency("B2", "A1");
+ dag.dependency("B3", "A2");
+ dag.dependency("B3", "A3");
+
+ dag.dependency("C1", "B1");
+ dag.dependency("C1", "B2");
+ dag.dependency("C1", "B3");
+
+ let mut order = Vec::new();
+ dag.prune_by(
+ &["R"],
+ |key, _, _| {
+ order.push(*key);
+ ControlFlow::Continue(())
+ },
+ |(a, _), (b, _)| a.cmp(b),
+ );
+ assert_eq!(order, vec!["R", "A1", "B1", "B2", "A2", "A3", "B3", "C1"]);
+
+ let mut order = Vec::new();
+ dag.prune_by(
+ &["R"],
+ |key, _, _| {
+ order.push(*key);
+ ControlFlow::Continue(())
+ },
+ |(a, _), (b, _)| a.cmp(b).reverse(),
+ );
+ assert_eq!(order, vec!["R", "A3", "A2", "B3", "A1", "B2", "B1", "C1"]);
+
+ let mut order = Vec::new();
+ dag.prune_by(
+ &["R"],
+ |key, _, _| {
+ order.push(*key);
+ ControlFlow::Continue(())
+ },
+ |(_, a), (_, b)| a.cmp(b).reverse(),
+ );
+ assert_eq!(order, vec!["R", "A3", "A2", "B3", "A1", "B2", "B1", "C1"]);
+ }
}
Exit code: 0
shell: 'cargo --version rustc --version cargo fmt --check cargo clippy --all-targets --workspace -- --deny clippy::all cargo build --all-targets --workspace cargo doc --workspace cargo test --workspace --no-fail-fast '
Commands:
$ podman run --name ad1ad3b1-abf7-4863-b74a-129e00b79a28 -v /opt/radcis/ci.rad.levitte.org/cci/state/ad1ad3b1-abf7-4863-b74a-129e00b79a28/s:/ad1ad3b1-abf7-4863-b74a-129e00b79a28/s:ro -v /opt/radcis/ci.rad.levitte.org/cci/state/ad1ad3b1-abf7-4863-b74a-129e00b79a28/w:/ad1ad3b1-abf7-4863-b74a-129e00b79a28/w -w /ad1ad3b1-abf7-4863-b74a-129e00b79a28/w -v /opt/radcis/ci.rad.levitte.org/.radicle:/${id}/.radicle:ro -e RAD_HOME=/${id}/.radicle rust:trixie bash /ad1ad3b1-abf7-4863-b74a-129e00b79a28/s/script.sh
+ cargo --version
info: syncing channel updates for '1.80-x86_64-unknown-linux-gnu'
info: latest update on 2024-08-08, rust version 1.80.1 (3f5fd8dd4 2024-08-06)
info: downloading component 'cargo'
info: downloading component 'clippy'
info: downloading component 'rust-docs'
info: downloading component 'rust-src'
info: downloading component 'rust-std'
info: downloading component 'rustc'
info: downloading component 'rustfmt'
info: installing component 'cargo'
info: installing component 'clippy'
info: installing component 'rust-docs'
info: installing component 'rust-src'
info: installing component 'rust-std'
info: installing component 'rustc'
info: installing component 'rustfmt'
cargo 1.80.1 (376290515 2024-07-16)
+ rustc --version
rustc 1.80.1 (3f5fd8dd4 2024-08-06)
+ cargo fmt --check
Diff in /ad1ad3b1-abf7-4863-b74a-129e00b79a28/w/radicle-cli/src/commands/clone.rs at line 236:
node: &mut Node,
signer: &G,
storage: &Storage,
-) -> Result<
- (
- raw::Repository,
- storage::git::Repository,
- Doc,
- Project,
- ),
- CloneError,
-> {
+) -> Result<(raw::Repository, storage::git::Repository, Doc, Project), CloneError> {
let me = *signer.public_key();
// Seed repository.
Diff in /ad1ad3b1-abf7-4863-b74a-129e00b79a28/w/radicle-cli/src/commands/init.rs at line 14:
use radicle::explorer::ExplorerUrl;
use radicle::git::RefString;
use radicle::identity::project::ProjectName;
-use radicle::identity::{RepoId, Doc, Visibility};
+use radicle::identity::{Doc, RepoId, Visibility};
use radicle::node::events::UploadPack;
use radicle::node::policy::Scope;
use radicle::node::{Event, Handle, NodeId, DEFAULT_SUBSCRIBE_TIMEOUT};
Diff in /ad1ad3b1-abf7-4863-b74a-129e00b79a28/w/radicle-fetch/src/handle.rs at line 4:
use bstr::BString;
use radicle::crypto::PublicKey;
use radicle::git::Oid;
-use radicle::identity::{DocError, Doc};
+use radicle::identity::{Doc, DocError};
use radicle::storage::git::Repository;
use radicle::storage::ReadRepository;
Diff in /ad1ad3b1-abf7-4863-b74a-129e00b79a28/w/radicle-fetch/src/state.rs at line 4:
use gix_protocol::handshake;
use radicle::crypto::PublicKey;
use radicle::git::{Oid, Qualified};
-use radicle::identity::{Did, DocError, Doc};
+use radicle::identity::{Did, Doc, DocError};
use radicle::prelude::Verified;
use radicle::storage;
Exit code: 1
{
"response": "finished",
"result": "failure"
}