order members by distance

3 files changed, 63 insertions, 37 deletions

diff --git a/src/simtest/reach.rs b/src/simtest/reach.rs
index 2c188cf..20f770c 100644
--- a/src/simtest/reach.rs
+++ b/src/simtest/reach.rs
@@ -53,9 +53,8 @@ async fn neighbours_tell_whom_they_reach() {
 }
 
 /// The same three: in x's tree (`swarm::tree`), c can't take x as its parent (it
-/// doesn't reach it), so it takes b, which comes before it if c comes later by pair
-/// key; else c has no parent and gets x's changes from announcements. Either way x's
-/// only child is b, and nobody but b passes x's changes to c.
+/// doesn't reach it), so it takes b, which comes before it: as far from x, but it
+/// reaches x. So x's only child is b, and b's is c.
 #[tokio::test(flavor = "multi_thread", worker_threads = 4)]
 async fn writer_trees_go_around_links_down() {
     let sim = Sim::with_identity(67);
@@ -71,21 +70,15 @@ async fn writer_trees_go_around_links_down() {
     sim.wait_ready(&[&b, &c, &x], SOON).await;
     let (b, c, x) = (&b, &c, &x);
     let writer = topology::pair_key(x.local_id());
-    let c_after_b = topology::pair_key(c.local_id()) > topology::pair_key(b.local_id());
     sim.wait_until(
-        "x's tree: b under x, and c under b if c comes after it",
+        "x's tree: b under x, and c under b",
         SOON,
         move || async move {
             let of_x = tree::children(x, writer).await;
             let of_b = tree::children(b, writer).await;
             heard(c, b, x).await
                 && of_x == [b.local_id().to_owned()]
-                && of_b
-                    == if c_after_b {
-                        vec![c.local_id().to_owned()]
-                    } else {
-                        Vec::new()
-                    }
+                && of_b == [c.local_id().to_owned()]
         },
     )
     .await;
diff --git a/src/swarm/topology/tests.rs b/src/swarm/topology/tests.rs
index 807ea63..4069c0e 100644
--- a/src/swarm/topology/tests.rs
+++ b/src/swarm/topology/tests.rs
@@ -317,10 +317,11 @@ fn hub_degree_is_bounded_in_large_swarms() {
 /// their members' keys): as now (every node that gets it tells all its neighbours but
 /// the one it came from, over the links that work), and along the writer's tree.
 ///
-/// The tree: every member's distance from the writer over the member list's graph (as
-/// every node computes it alike), and each member's parent the neighbour it reaches
-/// (as it tells its neighbours, `swarm::reach`) that comes first by distance, then pair
-/// score, of those before it (by distance, then pair key: no cycles). Whoever has a
+/// The tree (`swarm::tree`): every member's distance from the writer over the member
+/// list's graph (as every node computes it alike), and each member's parent the
+/// neighbour it reaches (as it tells its neighbours, `swarm::reach`) that comes first by
+/// distance, then whether it reaches a member a hop closer, then pair score, of those
+/// before it (by the same, then pair key: no cycles). Whoever has a
 /// change of the writer's passes it on to its children in the writer's tree, however
 /// it got it. A member with no parent it reaches waits for an announcement from a
 /// neighbour that has it (a pull), then passes it on to its own children.
@@ -399,14 +400,21 @@ fn bench_writer_trees() {
                 }
                 depth_max = depth_max.max(depth.values().copied().max().unwrap_or(0));
                 // Each member's parent: one it reaches, before it.
-                let rank = |m: &str| (depth[m], key[m]);
+                // Whether a member reaches one a hop closer (the writer: yes).
+                let closer = |m: &str| {
+                    depth[m] == 0
+                        || g[m]
+                            .iter()
+                            .any(|o| depth[o.as_str()] + 1 == depth[m] && works(m, o))
+                };
+                let rank = |m: &str| (depth[m], !closer(m), key[m]);
                 let mut children: HashMap<&str, Vec<&str>> = HashMap::new();
                 for &m in &order[1..] {
                     let parent = g[m]
                         .iter()
                         .map(String::as_str)
                         .filter(|p| rank(p) < rank(m) && works(m, p))
-                        .min_by_key(|p| (depth[p], pair_score(p, m)));
+                        .min_by_key(|p| (depth[p], !closer(p), pair_score(p, m)));
                     if let Some(parent) = parent {
                         children.entry(parent).or_default().push(m);
                     }
diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index 1dff92e..d362f74 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -5,11 +5,12 @@
 //! member list gives (`topology::member_list_graph`: every member's neighbours, as if
 //! all reached all) and what each member tells its neighbours it reaches
 //! (`swarm::reach`). Every member's distance from the writer over that graph orders the
-//! members, by distance and then pair key; a member's parent is the neighbour it reaches
-//! that comes before it, the closest to the writer first, then by pair score
+//! members: by distance, then whether it reaches a member a hop closer, then pair key;
+//! a member's parent is the neighbour it reaches that comes before it, the closest to
+//! the writer first, then one that reaches closer, then by pair score
 //! (`topology::pair_score`). Coming before rules out cycles, and taking only a neighbour
-//! it reaches routes around links that don't work: one behind NAT that reaches a single
-//! member takes that one, at whatever distance.
+//! it reaches routes around links that don't work: where a writer behind NAT reaches a
+//! single member, that one comes first and the others take it.
 //!
 //! A sync message that passes a writer's change on says whose (`SyncEnvelope::writer`).
 //! Whoever applies one passes it on to its own children in that writer's tree
@@ -85,16 +86,51 @@ fn distances(state: &AppState, writer: u64) -> Option<(Arc<Graph>, Arc<HashMap<S
 
 /// Our children in `writer`'s tree: our neighbours in the graph whose parent we are,
 /// and whom we reach.
+///
+/// Members are ordered by distance from the writer, then whether they reach a member a
+/// hop closer (as they say: else, while it hasn't the change from its own side, it is
+/// as good as farther), then pair key; a member's parent is the neighbour it reaches
+/// that comes before it, by the same, then pair score. So where the writer reaches few
+/// (behind NAT), those it reaches come first among the members as far from it, and the
+/// others take them as parents. What a member reaches we know of ourselves and our
+/// neighbours, as they said; of others, the graph is taken as right (if we're wrong,
+/// a change goes twice or by announcement).
 pub(crate) async fn children(state: &AppState, writer: u64) -> Vec<String> {
     let Some((graph, distance)) = distances(state, writer) else {
         return Vec::new();
     };
+    let me = state.local_id();
+    if !distance.contains_key(me) {
+        return Vec::new();
+    }
+    // Whom we and our neighbours reach, by pair key.
+    let mut reaches: HashMap<&str, Vec<u64>> = HashMap::new();
+    reaches.insert(me, reach::published(state));
+    for member in graph.get(me).into_iter().flatten() {
+        if let Some(peer_state) = state.get_peer_state(member).await
+            && let Some(keys) = reach::of(state, peer_state.lock().await.reaches.as_ref())
+        {
+            reaches.insert(member.as_str(), keys);
+        }
+    }
+    let reached = |by: &str, member: &str| {
+        reaches
+            .get(by)
+            .is_none_or(|keys| keys.contains(&topology::pair_key(member)))
+    };
+    // Whether a member reaches one a hop closer to the writer (the writer: yes).
+    let closer = |member: &str| {
+        let d = distance[member];
+        d == 0
+            || graph.get(member).into_iter().flatten().any(|other| {
+                distance.get(other.as_str()) == Some(&(d - 1)) && reached(member, other)
+            })
+    };
     let rank = |member: &str| {
         distance
             .get(member)
-            .map(|d| (*d, topology::pair_key(member)))
+            .map(|d| (*d, !closer(member), topology::pair_key(member)))
     };
-    let me = state.local_id();
     let Some(my_rank) = rank(me) else {
         return Vec::new();
     };
@@ -106,26 +142,15 @@ pub(crate) async fn children(state: &AppState, writer: u64) -> Vec<String> {
         if its_rank <= my_rank {
             continue;
         }
-        // Whom it reaches, as it told us; not knowing, as the graph says.
-        let reaches = match state.get_peer_state(member).await {
-            Some(peer_state) => reach::of(state, peer_state.lock().await.reaches.as_ref()),
-            None => None,
-        };
         let parent = graph
             .get(member)
             .into_iter()
             .flatten()
             .filter(|candidate| rank(candidate).is_some_and(|r| r < its_rank))
-            .filter(|candidate| {
-                reaches
-                    .as_ref()
-                    .is_none_or(|keys| keys.contains(&topology::pair_key(candidate)))
-            })
+            .filter(|candidate| reached(member, candidate))
             .min_by_key(|candidate| {
-                (
-                    distance[*candidate],
-                    topology::pair_score(candidate, member),
-                )
+                let (d, far, _) = rank(candidate).expect("ranked");
+                (d, far, topology::pair_score(candidate, member))
             });
         if parent.is_some_and(|parent| parent == me) && topology::reaches(state, member).await {
             children.push(member.clone());