order members by distance

4 files changed, 69 insertions, 41 deletions

diff --git a/docs/peers.md b/docs/peers.md
index 760412f..be77d5a 100644
--- a/docs/peers.md
+++ b/docs/peers.md
@@ -309,10 +309,12 @@ the default keepalive), and nothing goes into the document. `GET /peers` shows i
 A writer's changes pass on along its tree ([`swarm/tree.rs`](../src/swarm/tree.rs)), the same on every node:
 built on the graph the member list gives (as if every member reached every other) and
 on whom each member says it reaches. Members are ordered by their distance from the
-writer over that graph, then by key; a member's parent is the neighbour it reaches that
-comes before it, the closest to the writer first, then by pair score. Coming before
-rules out cycles; taking only one it reaches routes around links that don't work (one
-behind NAT that reaches a single member takes that one). A sync message that passes a
+writer over that graph, then whether they reach a member a hop closer, then by 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. Coming before rules out
+cycles; taking only one it reaches routes around links that don't work: where a writer
+behind NAT reaches a single member, that one comes first among those as far from it,
+and the others take it as their parent. A sync message that passes a
 writer's change on says whose; whoever applies one sends it at once to its children in
 that writer's tree, however it got it, and leaves them out of its announcement round.
 A member without a parent it reaches, or whose parent missed the change, gets it by
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());