order members by distance

1 files changed, 45 insertions, 20 deletions

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());