dashboard: show writer trees

3 files changed, 189 insertions, 26 deletions

diff --git a/src/api/dashboard/dashboard.html b/src/api/dashboard/dashboard.html
index 9132275..b1aa821 100644
--- a/src/api/dashboard/dashboard.html
+++ b/src/api/dashboard/dashboard.html
@@ -161,6 +161,9 @@
   .legend .dormant::before { border-top-width: 1.5px; --colour: var(--muted);
     box-shadow: 0 0 0 2.5px color-mix(in srgb, var(--bad) 50%, transparent); }
   .legend .silent::before { border-top-style: dotted; --colour: var(--muted); }
+  /* A chevron on a link, as on the map: a writer's tree, the way its changes go. */
+  .legend .writer-tree::before { content: "\203A"; width: auto; height: auto; border: none;
+    font-weight: bold; font-size: 15px; line-height: 0; color: var(--muted); }
   .legend .hint::before { display: none; }
   /* A kind of message: a dot in its colour, as on the map. */
   .legend .message::before { width: 8px; height: 8px; border: none; border-radius: 50%;
@@ -263,6 +266,7 @@
     <div class="map-controls">
       <button id="links-toggle" class="toggle">links: live</button>
       <button id="rtt-toggle" class="toggle">layout: static</button>
+      <button id="tree-toggle" class="toggle">tree: off</button>
       <button id="legend-toggle" class="toggle">hide legend</button>
     </div>
     <div id="legends">
@@ -417,6 +421,7 @@ function focus(id) {
   } catch { /* not where history works */ }
   render();
   markPeerMessages();
+  loadTree();
 }
 
 // --- Peers ---
@@ -608,6 +613,10 @@ function renderLegend(measured) {
     el("span", { class: "relayed" }, "relayed"),
     el("span", { class: "dormant" }, "dormant or down"),
     el("span", { class: "silent" }, "an end reports no links"));
+  if (treeShown) {
+    items.push(el("span", { class: "writer-tree" }, name(treeWriter()) +
+      "'s tree: the way its changes go (of the node in focus)"));
+  }
   document.getElementById("legend").replaceChildren(...items);
 }
 
@@ -711,6 +720,27 @@ function relax(nodes, pairs, width, height, gain, most, only) {
 // the median one's, within bounds. Then, when the lengths change, the map moves to
 // them a little every frame (`settle`), not at once.
 let byRtt = false;
+// A writer's tree on the map (`swarm::tree`, `GET /admin/dashboard/tree`): of the node in
+// focus, else of this node; asked for anew when the writer changes and every 10 s.
+let treeShown = false;
+try { treeShown = localStorage.getItem("continuum-tree") === "1"; } catch (_) {}
+let writerTree = null;
+const treeWriter = () => focused !== null && !isPair(focused) ? focused
+  : state ? state.node.id : null;
+function loadTree() {
+  const writer = treeWriter();
+  if (!treeShown || writer === null) { writerTree = null; return; }
+  fetch("dashboard/tree?writer=" + encodeURIComponent(writer))
+    .then(response => response.ok ? response.json() : null)
+    .then(loaded => {
+      if (loaded && loaded.writer === treeWriter()) {
+        writerTree = loaded;
+        if (state) renderGraph();
+      }
+    })
+    .catch(() => {});
+}
+setInterval(() => { if (treeShown) loadTree(); }, 10000);
 try { byRtt = localStorage.getItem("continuum-by-rtt") === "1"; } catch (_) {}
 // One spring per pair of nodes, intended or measured or both: [a, b, length, loose].
 // Measured links shape the map; a link only intended (nothing measured backs it) is
@@ -1030,6 +1060,30 @@ function renderGraph() {
     tooltip(covering, descriptions.join("\n"));
   }
   // Above every line, so none crosses them.
+  // The tree of the writer in focus (`treeShown`): a chevron on each link from parent to
+  // child, at its middle, pointing the way changes go, in the colour of the link.
+  if (treeShown && writerTree && writerTree.writer === treeWriter()) {
+    for (const [child, parent] of Object.entries(writerTree.parents)) {
+      const p = parent && positions.get(parent), q = positions.get(child);
+      if (!p || !q) continue;
+      const length = Math.max(Math.hypot(q.x - p.x, q.y - p.y), 1);
+      const ux = (q.x - p.x) / length, uy = (q.y - p.y) / length;
+      const mx = (p.x + q.x) / 2, my = (p.y + q.y) / 2;
+      const d = "M " + (mx - ux * 5 - uy * 5) + " " + (my - uy * 5 + ux * 5) + " L " +
+        (mx + ux * 5) + " " + (my + uy * 5) + " L " + (mx - ux * 5 + uy * 5) + " " +
+        (my - uy * 5 - ux * 5);
+      const shape = { d, fill: "none", "stroke-linecap": "round", "stroke-linejoin": "round" };
+      // The colour of the link's line in use (its transport's), as the line it is on.
+      const edge = measured.get(pairKey(parent, child));
+      const colour = edge ? colourOf(edge.link.transport) : "var(--intended)";
+      labels.push(drawing("tree under " + child, "path",
+        { ...shape, stroke: "var(--panel)", "stroke-width": 6 }));
+      const chevron = drawing("tree " + child, "path",
+        { ...shape, stroke: colour, "stroke-width": 2.5 });
+      tooltip(chevron, "in " + name(writerTree.writer) + "'s tree: " + name(parent) + " → " + name(child));
+      labels.push(chevron);
+    }
+  }
   children.push(...labels);
   // Above the lines and their labels, below the nodes.
   children.push(...hits);
@@ -1549,6 +1603,23 @@ linksToggle.addEventListener("click", () => {
   const live = !state || state.graph.live !== false;
   fetch("dashboard/links?live=" + !live, { method: "POST" }).catch(() => {});
 });
+// A writer's tree, shown and hidden (`treeShown`).
+const treeToggle = document.getElementById("tree-toggle");
+function showTreeToggle() {
+  treeToggle.textContent = treeShown ? "tree: on" : "tree: off";
+  treeToggle.title = treeShown
+    ? "The tree of the node in focus (or this node) as a writer: the way its changes go. Click to hide it"
+    : "Click to show the tree of the node in focus (or this node) as a writer: the way its changes go";
+}
+showTreeToggle();
+treeToggle.addEventListener("click", () => {
+  treeShown = !treeShown;
+  try { localStorage.setItem("continuum-tree", treeShown ? "1" : "0"); } catch (_) {}
+  showTreeToggle();
+  writerTree = null;
+  loadTree();
+  if (state) renderGraph();
+});
 // Links as long as their round trips, and back.
 const rttToggle = document.getElementById("rtt-toggle");
 function showRttToggle() {
@@ -2289,6 +2360,7 @@ function connect() {
     if (state !== null) documentChanged({ all: true });
     state = snapshot; stateAt = Date.now(); live = true;
     status("live", true); pulse(); render(); trafficArrived();
+    if (treeShown && writerTree === null) loadTree();
     handOverLinks();
   });
   events.addEventListener("patch", event => {
diff --git a/src/api/dashboard/mod.rs b/src/api/dashboard/mod.rs
index 8d954c0..6682cbd 100644
--- a/src/api/dashboard/mod.rs
+++ b/src/api/dashboard/mod.rs
@@ -490,6 +490,7 @@ pub(crate) fn router(state: AppState) -> Router<AppState> {
         .route("/admin/dashboard/events", get(events))
         .route("/admin/dashboard/refresh", post(refresh))
         .route("/admin/dashboard/links", post(set_links))
+        .route("/admin/dashboard/tree", get(writer_tree))
         .layer(Extension(Hub::new(state, closing)))
 }
 
@@ -551,6 +552,52 @@ async fn set_links(
     StatusCode::NO_CONTENT
 }
 
+#[derive(serde::Deserialize)]
+struct TreeQuery {
+    writer: String,
+}
+
+/// `GET /admin/dashboard/tree?writer=…`: the writer's tree (`swarm::tree`), as this node
+/// computes it from the member list and the links members report (whom each reaches;
+/// one that reports none counts as reaching its neighbours by the member list): every
+/// member's parent, `null` for one without. `404` if the writer isn't a member.
+async fn writer_tree(
+    Extension(hub): Extension<Arc<Hub>>,
+    Query(query): Query<TreeQuery>,
+) -> Response {
+    let state = &hub.state;
+    let mut reaches: BTreeMap<String, BTreeSet<String>> = state
+        .links
+        .replies()
+        .into_iter()
+        .map(|(member, _, links)| (member, reached_by(&links)))
+        .collect();
+    reaches.insert(
+        state.local_id().to_owned(),
+        reached_by(&links::own_links(state).await),
+    );
+    let reached = |by: &str, member: &str| {
+        reaches
+            .get(by)
+            .is_none_or(|reached| reached.contains(member))
+    };
+    match crate::swarm::tree::whole(state, &query.writer, &reached) {
+        Some(parents) => {
+            axum::Json(json!({ "writer": query.writer, "parents": parents })).into_response()
+        }
+        None => StatusCode::NOT_FOUND.into_response(),
+    }
+}
+
+/// Whom a member reaches, by its links: those neither dormant nor down.
+fn reached_by(links: &[Link]) -> BTreeSet<String> {
+    links
+        .iter()
+        .filter(|link| !link.dormant && !link.down)
+        .map(|link| link.peer.clone())
+        .collect()
+}
+
 /// `GET /admin/dashboard/state`: the latest snapshot, for a client that wants it whole.
 async fn current_state(Extension(hub): Extension<Arc<Hub>>) -> Response {
     hub.want();
diff --git a/src/swarm/tree.rs b/src/swarm/tree.rs
index 8093c91..b21908e 100644
--- a/src/swarm/tree.rs
+++ b/src/swarm/tree.rs
@@ -105,6 +105,73 @@ pub(crate) async fn children(state: &AppState, writer: u64) -> Vec<String> {
         .unwrap_or_default()
 }
 
+/// Where `member` comes in the writer's tree (by `distance` from it over `graph`):
+/// its distance, then whether it reaches a member a hop closer (`reached(by, other)`:
+/// whether `by` reaches `other`, as known; the writer does), then its pair key. None if
+/// the graph doesn't have it.
+fn rank(
+    graph: &Graph,
+    distance: &HashMap<String, u32>,
+    reached: &dyn Fn(&str, &str) -> bool,
+    member: &str,
+) -> Option<(u32, bool, u64)> {
+    let d = *distance.get(member)?;
+    let closer =
+        d == 0
+            || graph.get(member).into_iter().flatten().any(|other| {
+                distance.get(other.as_str()) == Some(&(d - 1)) && reached(member, other)
+            });
+    Some((d, !closer, topology::pair_key(member)))
+}
+
+/// `member`'s parent in the writer's tree (`rank`): the neighbour it reaches that comes
+/// before it, the closest to the writer first, then one that reaches closer, then by
+/// pair score; None if none does (or it is the writer).
+fn parent<'g>(
+    graph: &'g Graph,
+    distance: &HashMap<String, u32>,
+    reached: &dyn Fn(&str, &str) -> bool,
+    member: &str,
+) -> Option<&'g str> {
+    let its_rank = rank(graph, distance, reached, member)?;
+    graph
+        .get(member)
+        .into_iter()
+        .flatten()
+        .map(String::as_str)
+        .filter(|candidate| {
+            rank(graph, distance, reached, candidate).is_some_and(|r| r < its_rank)
+                && reached(member, candidate)
+        })
+        .min_by_key(|candidate| {
+            let (d, far, _) = rank(graph, distance, reached, candidate).expect("ranked");
+            (d, far, topology::pair_score(candidate, member))
+        })
+}
+
+/// `writer`'s whole tree, as far as `reached` knows whom each member reaches (the
+/// dashboard's map, from the links members report): every member's parent, None for
+/// those without one (they get the writer's changes by announcement). None while the
+/// member list isn't known, or the writer isn't in it.
+#[cfg_attr(not(feature = "dashboard"), allow(dead_code))]
+pub(crate) fn whole(
+    state: &AppState,
+    writer: &str,
+    reached: &dyn Fn(&str, &str) -> bool,
+) -> Option<BTreeMap<String, Option<String>>> {
+    let (graph, distance) = distances(state, topology::pair_key(writer))?;
+    Some(
+        graph
+            .keys()
+            .filter(|member| distance.get(member.as_str()).is_some_and(|d| *d > 0))
+            .map(|member| {
+                let parent = parent(&graph, &distance, reached, member).map(str::to_owned);
+                (member.clone(), parent)
+            })
+            .collect(),
+    )
+}
+
 /// What `writer`'s tree means for us: our children in it, and our neighbours it leaves
 /// out (`uncovered`).
 pub(crate) struct Plan {
@@ -137,40 +204,17 @@ pub(crate) async fn plan(state: &AppState, writer: u64) -> Option<Plan> {
             .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, !closer(member), topology::pair_key(member)))
-    };
-    let my_rank = rank(me)?;
+    let my_rank = rank(&graph, &distance, &reached, me)?;
     let mut children = Vec::new();
     let mut uncovered = Vec::new();
     for member in graph.get(me).into_iter().flatten() {
-        let Some(its_rank) = rank(member) else {
+        let Some(its_rank) = rank(&graph, &distance, &reached, member) else {
             continue;
         };
         if distance[member.as_str()] == 0 {
             continue;
         }
-        let parent = graph
-            .get(member)
-            .into_iter()
-            .flatten()
-            .filter(|candidate| rank(candidate).is_some_and(|r| r < its_rank))
-            .filter(|candidate| reached(member, candidate))
-            .min_by_key(|candidate| {
-                let (d, far, _) = rank(candidate).expect("ranked");
-                (d, far, topology::pair_score(candidate, member))
-            });
-        match parent {
+        match parent(&graph, &distance, &reached, member) {
             None => uncovered.push(member.clone()),
             Some(parent)
                 if parent == me && its_rank > my_rank && topology::reaches(state, member).await =>