tree views measured

1 files changed, 95 insertions, 0 deletions

diff --git a/src/simtest/bench.rs b/src/simtest/bench.rs
index 30a43c7..6729c7d 100644
--- a/src/simtest/bench.rs
+++ b/src/simtest/bench.rs
@@ -260,6 +260,16 @@ const SCENARIOS: &[Scenario] = &[
         joining: 0,
         reply_timeout: Some(Duration::from_secs(5)),
     },
+    Scenario {
+        name: "writer behind NAT (one link), partial mesh, 50 nodes",
+        nodes: 50,
+        on: sim_only,
+        net: writer_behind_nat,
+        writer: 1,
+        away: None,
+        joining: 0,
+        reply_timeout: None,
+    },
 ];
 
 #[tokio::test(flavor = "multi_thread", worker_threads = 16)]
@@ -618,6 +628,7 @@ async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim
         _ => f64::NAN,
     };
     let mut latencies = Vec::new();
+    let mut views = Views::default();
     for node in nodes {
         // Each member's parent in this node's tree, as the member chose it.
         let mut parents = std::collections::HashMap::new();
@@ -627,8 +638,10 @@ async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim
                 parents.insert(member.local_id().to_owned(), chosen);
             }
         }
+        views.add(nodes, node, &parents).await;
         latencies.extend(crate::swarm::tree::own_latencies(node, &parents, &latency).await);
     }
+    views.report(out);
     let members: usize = latencies.iter().map(|l| l.members).sum();
     if members == 0 {
         return;
@@ -649,6 +662,88 @@ async fn trees(out: &mut String, nodes: &[AppState], net: &crate::transport::sim
     );
 }
 
+/// Whether the nodes' views of the writers' trees agree: each member's parent as the
+/// member chose it (`swarm::tree::own_parent`) against what that parent and the
+/// others plan (`swarm::tree::plan`: their children, the neighbours they count as
+/// covered). Summed over every node's tree.
+#[derive(Default)]
+struct Views {
+    /// Child links planned (a node sends to its children).
+    planned: usize,
+    /// Of those, the child's own choice of parent.
+    confirmed: usize,
+    /// Members whose chosen parent doesn't plan them as a child, so that nothing comes
+    /// along the tree: the parent counts them as covered (as having the changes from
+    /// another), or neither (it doesn't reach them, or ranks them before itself).
+    orphans_covered: usize,
+    orphans_neither: usize,
+    /// Members two nodes or more plan as a child (all but one send in vain).
+    doubled: usize,
+    /// Members (not writers) that chose no parent: announcements bring them all.
+    parentless: usize,
+}
+
+impl Views {
+    async fn add(
+        &mut self,
+        nodes: &[AppState],
+        writer: &AppState,
+        parents: &HashMap<String, Option<String>>,
+    ) {
+        let key = crate::swarm::topology::pair_key(writer.local_id());
+        let mut plans = HashMap::new();
+        for node in nodes {
+            if let Some(plan) = crate::swarm::tree::plan(node, key).await {
+                plans.insert(node.local_id().to_owned(), plan);
+            }
+        }
+        let mut planned_by: HashMap<&str, usize> = HashMap::new();
+        for (node, plan) in &plans {
+            for child in &plan.children {
+                self.planned += 1;
+                *planned_by.entry(child.as_str()).or_default() += 1;
+                if parents
+                    .get(child)
+                    .is_some_and(|parent| parent.as_ref() == Some(node))
+                {
+                    self.confirmed += 1;
+                }
+            }
+        }
+        self.doubled += planned_by.values().filter(|count| **count > 1).count();
+        for (member, parent) in parents {
+            let Some(parent) = parent else {
+                self.parentless += 1;
+                continue;
+            };
+            let Some(plan) = plans.get(parent) else {
+                continue;
+            };
+            if plan.children.contains(member) {
+                continue;
+            }
+            if plan.covered.contains(member) {
+                self.orphans_covered += 1;
+            } else {
+                self.orphans_neither += 1;
+            }
+        }
+    }
+
+    fn report(&self, out: &mut String) {
+        let _ = writeln!(
+            out,
+            "    views of the trees: {} of {} child links the child's own choice; orphans (the parent it chose doesn't send): {} counted covered, {} neither; {} planned as a child twice or more; {} members without a parent",
+            self.confirmed,
+            self.planned,
+            self.orphans_covered,
+            self.orphans_neither,
+            self.doubled,
+            self.parentless,
+        );
+    }
+}
+
 /// The members `writer`'s changes take longest to reach along its tree, by the links'
 /// latencies alone (the parents as each member chose them, `swarm::tree::own_place`),
 /// those later than `LATE_MS`: how far each is from the writer, its parent and the