bat-cli 0.28.0

//! Deterministic graph layout for the automatic Miro deployment.
//!
//! This module is pure: it takes measured boxes plus a call graph and returns
//! coordinates. It never touches the network, the filesystem or the Miro API,
//! so the whole algorithm is unit-testable.
//!
//! Two independent pieces live here:
//!
//! - [`layout_graph`]: places the screenshots of one entry point inside its
//!   frame (Sugiyama-style layering, left → right).
//! - [`ShelfAllocator`]: places the frames themselves on the board, in O(1) per
//!   frame and without ever asking Miro where there is free space.

use std::collections::{HashMap, HashSet, VecDeque};

/// Tunables for [`layout_graph`]. All distances are in board units.
#[derive(Debug, Clone, Copy)]
pub struct LayoutConfig {
    /// Horizontal margin between the frame border and the first layer.
    pub padding_x: f64,
    /// Vertical margin between the frame border and the content.
    pub padding_y: f64,
    /// Extra vertical room reserved at the top for the frame title.
    pub title_band: f64,
    /// Horizontal gap between layers.
    pub gutter_x: f64,
    /// Vertical gap between nodes of the same layer.
    pub gutter_y: f64,
    /// A layer taller than this is split into side-by-side sub-columns.
    pub max_layer_height: f64,
}

impl Default for LayoutConfig {
    fn default() -> Self {
        Self {
            padding_x: 250.0,
            padding_y: 200.0,
            title_band: 150.0,
            // A modest horizontal corridor: enough that Miro's elbow turns in the
            // gutter (clear of the screenshots) now that forward connectors leave
            // horizontally, without wasting frame space. The crossing-minimisation
            // and exit-side changes do the rest at no space cost.
            gutter_x: 550.0,
            gutter_y: 120.0,
            max_layer_height: 12_000.0,
        }
    }
}

/// A measured screenshot waiting to be placed.
#[derive(Debug, Clone)]
pub struct LayoutNode {
    pub id: String,
    pub width: f64,
    pub height: f64,
}

/// A caller → callee edge, carrying where in the caller the call happens.
#[derive(Debug, Clone)]
pub struct LayoutEdge {
    pub from: String,
    pub to: String,
    /// Vertical position of the call inside the caller's screenshot, as a
    /// fraction in `[0, 1]`. Used to order callees so that a call made near the
    /// top of the caller draws above one made near the bottom.
    pub from_line_fraction: f64,
}

/// A node with its final position, in coordinates local to the frame
/// (origin at the frame's top-left corner, `x`/`y` = center of the item, which
/// is what the Miro API expects for a child of a frame).
#[derive(Debug, Clone, PartialEq)]
pub struct PlacedNode {
    pub id: String,
    pub layer: usize,
    pub x: f64,
    pub y: f64,
    pub width: f64,
    pub height: f64,
}

/// Result of laying out one entry point.
#[derive(Debug, Clone)]
pub struct GraphLayout {
    pub nodes: Vec<PlacedNode>,
    /// Where each edge has to bend, aligned with the input `edges`.
    ///
    /// Empty for an edge between adjacent layers, which already runs down the
    /// corridor between them. An edge that skips layers gets one point per
    /// layer it crosses, and the caller is expected to draw it as a chain
    /// through those points instead of as one long connector — see
    /// [`layout_graph`].
    pub routes: Vec<Vec<(f64, f64)>>,
    /// Edges that were classified as cycles and should be drawn dashed.
    pub back_edges: Vec<(String, String)>,
    pub bbox_width: f64,
    pub bbox_height: f64,
    pub frame_width: f64,
    pub frame_height: f64,
}

impl GraphLayout {
    pub fn node(&self, id: &str) -> Option<&PlacedNode> {
        self.nodes.iter().find(|n| n.id == id)
    }
}

/// Lay out the dependency graph of a single entry point.
///
/// Layers come from the **longest** path to the root, not the shortest: a helper
/// called from both layer 1 and layer 3 lands on layer 4, which guarantees every
/// edge points forward and no connector ever runs backwards.
pub fn layout_graph(
    root_id: &str,
    nodes: &[LayoutNode],
    edges: &[LayoutEdge],
    config: LayoutConfig,
) -> GraphLayout {
    // There used to be a shortcut here: a graph with no shared nodes went to a tidy-tree
    // layout, on the grounds that giving each subtree its own band draws a tree with no
    // crossings at all. It cost more than it bought, and the bill grew.
    //
    // A band is the whole subtree's height, so a light sibling placed after a heavy one
    // starts BELOW everything the heavy one reaches — on one real entry point, two
    // getters sat at y≈6,900 with their column empty from 1,300 down, and the frame
    // reserved 7,692px where its tallest column needed 4,883. The frame's height is the
    // SUM of the root's children's bands, not the tallest column, so the emptiness is
    // structural rather than a packing accident.
    //
    // It also became the common case rather than the exception: localization copies a
    // shared helper per caller and a crossing callee too big to copy is replaced by a
    // card, so the multi-parent nodes that made a graph "not a tree" are exactly what the
    // framing work removes. Diagrams that used to be laid out by layers started falling
    // into the tree path and growing a dead band.
    //
    // So: one layout for everything. Layers pack each column from the top, and every
    // recent improvement — call order, one lane per arrow, the honest crossing count —
    // lives there.
    let (forward_edges, back_edges) = split_back_edges(root_id, nodes, edges);
    let layers = assign_layers(root_id, nodes, &forward_edges);

    // Insert a placeholder in every layer an edge skips over.
    //
    // An edge between adjacent layers runs down the empty corridor between
    // them. One that skips a layer has to cross the column of screenshots
    // living there, which is what puts a line on top of a code block. Splitting
    // it into a chain of one-layer hops fixes that, and because the
    // placeholders take a slot in the ordering, the screenshots move aside to
    // leave the corridor — the space is reserved rather than hoped for.
    let (augmented_nodes, augmented_edges, routes_by_edge, layers) =
        insert_bend_points(nodes, edges, &forward_edges, layers);

    let by_id: HashMap<&str, &LayoutNode> = augmented_nodes
        .iter()
        .map(|n| (n.id.as_str(), n))
        .collect();
    let mut layer_members = group_by_layer(&augmented_nodes, &layers);
    order_layers(&mut layer_members, &augmented_edges);

    // Split any layer that would make the frame absurdly tall.
    let columns: Vec<Vec<Vec<String>>> = layer_members
        .iter()
        .map(|members| split_into_columns(members, &by_id, config))
        .collect();

    // Geometry per layer.
    let mut layer_widths = Vec::with_capacity(columns.len());
    let mut layer_heights = Vec::with_capacity(columns.len());
    for layer_columns in &columns {
        let sub_gutter = config.gutter_x / 2.0;
        let width: f64 = layer_columns
            .iter()
            .map(|column| {
                column_width(column, &by_id)
            })
            .sum::<f64>()
            + sub_gutter * (layer_columns.len().saturating_sub(1)) as f64;
        let height = layer_columns
            .iter()
            .map(|column| column_height(column, &by_id, config))
            .fold(0.0_f64, f64::max);
        layer_widths.push(width);
        layer_heights.push(height);
    }

    let bbox_width = layer_widths.iter().sum::<f64>()
        + config.gutter_x * (columns.len().saturating_sub(1)) as f64;
    let bbox_height = layer_heights.iter().cloned().fold(0.0_f64, f64::max);

    // Place every node.
    let mut placed = Vec::with_capacity(nodes.len());
    let mut layer_x = config.padding_x;
    for (layer_index, layer_columns) in columns.iter().enumerate() {
        let sub_gutter = config.gutter_x / 2.0;
        let mut column_x = layer_x;
        for column in layer_columns {
            let this_column_width = column_width(column, &by_id);
            let this_column_height = column_height(column, &by_id, config);
            // Every layer starts at the TOP, not centred. A caller (tall entry point)
            // sits at the top-left; centring its callees would push them to the middle
            // of the frame, so arrows from the caller's top AND bottom call sites both
            // converge inward and cross. Top-aligning keeps the fan-out monotonic —
            // the cascade flows down-and-right from the top — which is what removes
            // those crossings, and keeps deep chains from drifting far down.
            let mut y_cursor = config.padding_y + config.title_band;
            let _ = this_column_height;
            for (rank, id) in column.iter().enumerate() {
                let node = match by_id.get(id.as_str()) {
                    Some(node) => *node,
                    None => continue,
                };
                placed.push(PlacedNode {
                    id: id.clone(),
                    layer: layer_index,
                    x: column_x + node.width / 2.0,
                    y: y_cursor + node.height / 2.0,
                    width: node.width,
                    height: node.height,
                });
                y_cursor += node.height + config.gutter_y;
            }
            column_x += this_column_width + sub_gutter;
        }
        layer_x += layer_widths[layer_index] + config.gutter_x;
    }

    // Turn the placeholders into coordinates, then drop them: the caller draws
    // the bends, it does not need boxes for them.
    let position_of: HashMap<&str, (f64, f64)> = placed
        .iter()
        .map(|node| (node.id.as_str(), (node.x, node.y)))
        .collect();
    let routes: Vec<Vec<(f64, f64)>> = routes_by_edge
        .iter()
        .map(|bends| {
            bends
                .iter()
                .filter_map(|id| position_of.get(id.as_str()).copied())
                .collect()
        })
        .collect();
    placed.retain(|node| !is_bend_point(&node.id));

    GraphLayout {
        nodes: placed,
        routes,
        back_edges,
        bbox_width,
        bbox_height,
        frame_width: bbox_width + 2.0 * config.padding_x,
        frame_height: bbox_height + 2.0 * config.padding_y + config.title_band,
    }
}

fn column_width(column: &[String], by_id: &HashMap<&str, &LayoutNode>) -> f64 {
    column
        .iter()
        .filter_map(|id| by_id.get(id.as_str()))
        .map(|n| n.width)
        .fold(0.0_f64, f64::max)
}

fn column_height(
    column: &[String],
    by_id: &HashMap<&str, &LayoutNode>,
    config: LayoutConfig,
) -> f64 {
    let sum: f64 = column
        .iter()
        .filter_map(|id| by_id.get(id.as_str()))
        .map(|n| n.height)
        .sum();
    sum + config.gutter_y * (column.len().saturating_sub(1)) as f64
}

/// Break a layer into side-by-side columns when stacking it in one column would
/// exceed `max_layer_height`.
fn split_into_columns(
    members: &[String],
    by_id: &HashMap<&str, &LayoutNode>,
    config: LayoutConfig,
) -> Vec<Vec<String>> {
    let total = column_height(members, by_id, config);
    if total <= config.max_layer_height || members.len() < 2 {
        return vec![members.to_vec()];
    }
    let column_count = (total / config.max_layer_height).ceil() as usize;
    let target = total / column_count as f64;

    let mut columns: Vec<Vec<String>> = Vec::new();
    let mut current: Vec<String> = Vec::new();
    let mut current_height = 0.0;
    for id in members {
        let height = by_id.get(id.as_str()).map(|n| n.height).unwrap_or(0.0);
        if !current.is_empty()
            && current_height + height > target
            && columns.len() + 1 < column_count
        {
            columns.push(std::mem::take(&mut current));
            current_height = 0.0;
        }
        current.push(id.clone());
        current_height += height + config.gutter_y;
    }
    if !current.is_empty() {
        columns.push(current);
    }
    columns
}

/// Classify edges into forward edges and back edges (cycles), using a DFS from
/// the root. Back edges are excluded from the layering so the graph is a DAG.
fn split_back_edges(
    root_id: &str,
    nodes: &[LayoutNode],
    edges: &[LayoutEdge],
) -> (Vec<LayoutEdge>, Vec<(String, String)>) {
    let mut adjacency: HashMap<&str, Vec<usize>> = HashMap::new();
    for (index, edge) in edges.iter().enumerate() {
        adjacency.entry(edge.from.as_str()).or_default().push(index);
    }

    let mut back: HashSet<usize> = HashSet::new();
    let mut state: HashMap<&str, u8> = HashMap::new(); // 0 unseen, 1 on stack, 2 done

    // Iterative DFS so a deep graph cannot blow the stack.
    let mut roots: Vec<&str> = vec![root_id];
    roots.extend(nodes.iter().map(|n| n.id.as_str()));
    for start in roots {
        if state.get(start).copied().unwrap_or(0) != 0 {
            continue;
        }
        let mut stack: Vec<(&str, usize)> = vec![(start, 0)];
        state.insert(start, 1);
        while let Some((node, cursor)) = stack.pop() {
            let outgoing = adjacency.get(node).cloned().unwrap_or_default();
            if cursor < outgoing.len() {
                stack.push((node, cursor + 1));
                let edge_index = outgoing[cursor];
                let target = edges[edge_index].to.as_str();
                match state.get(target).copied().unwrap_or(0) {
                    1 => {
                        back.insert(edge_index);
                    }
                    0 => {
                        state.insert(target, 1);
                        stack.push((target, 0));
                    }
                    _ => {}
                }
            } else {
                state.insert(node, 2);
            }
        }
    }

    let mut forward = Vec::new();
    let mut back_pairs = Vec::new();
    for (index, edge) in edges.iter().enumerate() {
        if back.contains(&index) {
            back_pairs.push((edge.from.clone(), edge.to.clone()));
        } else {
            forward.push(edge.clone());
        }
    }
    (forward, back_pairs)
}

/// Longest-path layering over the acyclic edge set.
fn assign_layers(
    root_id: &str,
    nodes: &[LayoutNode],
    edges: &[LayoutEdge],
) -> HashMap<String, usize> {
    let mut adjacency: HashMap<&str, Vec<&str>> = HashMap::new();
    let mut in_degree: HashMap<&str, usize> = HashMap::new();
    for node in nodes {
        in_degree.entry(node.id.as_str()).or_insert(0);
    }
    for edge in edges {
        adjacency
            .entry(edge.from.as_str())
            .or_default()
            .push(edge.to.as_str());
        *in_degree.entry(edge.to.as_str()).or_insert(0) += 1;
    }

    // Kahn topological order.
    let mut queue: VecDeque<&str> = VecDeque::new();
    if in_degree.get(root_id).copied().unwrap_or(0) == 0 {
        queue.push_back(root_id);
    }
    for node in nodes {
        if node.id != root_id && in_degree.get(node.id.as_str()).copied().unwrap_or(0) == 0 {
            queue.push_back(node.id.as_str());
        }
    }

    let mut layers: HashMap<String, usize> = HashMap::new();
    layers.insert(root_id.to_string(), 0);
    let mut remaining = in_degree.clone();
    let mut order: Vec<&str> = Vec::new();
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in adjacency.get(node).unwrap_or(&Vec::new()) {
            let entry = remaining.entry(next).or_insert(0);
            *entry = entry.saturating_sub(1);
            if *entry == 0 {
                queue.push_back(next);
            }
        }
    }

    for node in &order {
        let current = layers.get(*node).copied().unwrap_or(0);
        for &next in adjacency.get(*node).unwrap_or(&Vec::new()) {
            let candidate = current + 1;
            let entry = layers.entry(next.to_string()).or_insert(candidate);
            if *entry < candidate {
                *entry = candidate;
            }
        }
    }

    for node in nodes {
        layers.entry(node.id.clone()).or_insert(0);
    }
    layers
}

fn group_by_layer(nodes: &[LayoutNode], layers: &HashMap<String, usize>) -> Vec<Vec<String>> {
    let depth = layers.values().copied().max().unwrap_or(0);
    let mut grouped: Vec<Vec<String>> = vec![Vec::new(); depth + 1];
    for node in nodes {
        let layer = layers.get(&node.id).copied().unwrap_or(0);
        grouped[layer].push(node.id.clone());
    }
    grouped
}

/// Barycenter ordering, weighted by where the call sits inside the caller.
///
/// A callee invoked on the third line of its caller is pulled above one invoked
/// on the twelfth, so connectors stay close to horizontal and rarely cross.
fn order_layers(layers: &mut [Vec<String>], edges: &[LayoutEdge]) {
    // An odd number so the **last** sweep is the downward one: the downward pass
    // is the one that honours the call-line order, and an upward pass would
    // undo it by re-sorting on the successors' positions.
    const SWEEPS: usize = 5;

    let mut incoming: HashMap<&str, Vec<&LayoutEdge>> = HashMap::new();
    let mut outgoing: HashMap<&str, Vec<&LayoutEdge>> = HashMap::new();
    for edge in edges {
        incoming.entry(edge.to.as_str()).or_default().push(edge);
        outgoing.entry(edge.from.as_str()).or_default().push(edge);
    }

    // Keep the fewest-crossings ordering seen across the sweeps, so a sweep can
    // never leave the layout worse than it started. Ties keep the current one (a
    // downward sweep, which honours the call-line order).
    let mut best = layers.to_vec();
    let mut best_crossings = count_crossings(layers, edges);

    for sweep in 0..SWEEPS {
        let downward = sweep % 2 == 0;
        if downward {
            for index in 1..layers.len() {
                let previous: HashMap<String, usize> = layers[index - 1]
                    .iter()
                    .enumerate()
                    .map(|(position, id)| (id.clone(), position))
                    .collect();
                sort_layer(&mut layers[index], |id| {
                    let sources = incoming.get(id)?;
                    let keys: Vec<f64> = sources
                        .iter()
                        .filter_map(|edge| {
                            previous
                                .get(&edge.from)
                                .map(|position| *position as f64 + edge.from_line_fraction)
                        })
                        .collect();
                    mean(&keys)
                });
            }
        } else {
            for index in (0..layers.len().saturating_sub(1)).rev() {
                let next: HashMap<String, usize> = layers[index + 1]
                    .iter()
                    .enumerate()
                    .map(|(position, id)| (id.clone(), position))
                    .collect();
                sort_layer(&mut layers[index], |id| {
                    let targets = outgoing.get(id)?;
                    let keys: Vec<f64> = targets
                        .iter()
                        .filter_map(|edge| {
                            next.get(&edge.to).map(|position| *position as f64)
                        })
                        .collect();
                    mean(&keys)
                });
            }
        }
        // A downward sweep is the one that honours the call-line order; prefer it on
        // ties by only replacing the best when this ordering is strictly better,
        // except accept an equal downward sweep so the final order stays call-ordered.
        let crossings = count_crossings(layers, edges);
        if crossings < best_crossings || (crossings == best_crossings && downward) {
            best_crossings = crossings;
            best = layers.to_vec();
        }
    }

    layers.clone_from_slice(&best);
}

/// Total edge crossings between all adjacent layer pairs, given the current order
/// within each layer. Standard layered-graph count: two edges cross when their
/// endpoints are in opposite order on the two layers.
fn count_crossings(layers: &[Vec<String>], edges: &[LayoutEdge]) -> usize {
    let mut pos: HashMap<&str, (usize, usize)> = HashMap::new();
    for (layer_index, layer) in layers.iter().enumerate() {
        for (order, id) in layer.iter().enumerate() {
            pos.insert(id.as_str(), (layer_index, order));
        }
    }
    // Group edges by the (upper) layer they leave, keeping (from_order, to_order).
    // The from key carries the CALL LINE: an edge leaves its caller at the height of
    // the call, not at a point, so two edges out of one caller cross whenever call
    // order and callee order disagree. Keying on the integer slot alone made those
    // pairs equal and therefore never counted — the metric was blind to the one
    // defect a reader notices first, and the call-line order survived only as a
    // tie-break that any gain elsewhere overrode.
    let mut per_gap: HashMap<usize, Vec<(f64, f64)>> = HashMap::new();
    for edge in edges {
        let (Some(&(fl, fo)), Some(&(tl, to))) =
            (pos.get(edge.from.as_str()), pos.get(edge.to.as_str()))
        else {
            continue;
        };
        // Only count strictly adjacent forward edges; bend points make long edges
        // adjacent, so this covers the whole routed graph.
        if tl == fl + 1 {
            per_gap
                .entry(fl)
                .or_default()
                .push((fo as f64 + edge.from_line_fraction, to as f64));
        }
    }
    let mut total = 0usize;
    for pairs in per_gap.values() {
        for i in 0..pairs.len() {
            for j in (i + 1)..pairs.len() {
                let (a1, a2) = pairs[i];
                let (b1, b2) = pairs[j];
                if (a1 < b1 && a2 > b2) || (a1 > b1 && a2 < b2) {
                    total += 1;
                }
            }
        }
    }
    total
}

fn mean(values: &[f64]) -> Option<f64> {
    if values.is_empty() {
        return None;
    }
    Some(values.iter().sum::<f64>() / values.len() as f64)
}

/// Stable sort by an optional key, leaving the nodes that have NO key exactly where
/// they are: only the keyed ones are re-ordered, among the slots they already hold.
///
/// A node with no neighbour on the side being swept has no opinion about where it
/// belongs, and the previous version read that silence as "put it last". In a
/// downward sweep every leaf is keyless, so a whole layer came out as "the callees
/// that call something, then every leaf" — the order of the calls in the source was
/// lost for exactly the nodes that were easiest to place.
fn sort_layer<F>(layer: &mut [String], key_of: F)
where
    F: Fn(&str) -> Option<f64>,
{
    let keys: Vec<Option<f64>> = layer.iter().map(|id| key_of(id.as_str())).collect();
    let slots: Vec<usize> = (0..layer.len()).filter(|index| keys[*index].is_some()).collect();
    let mut keyed: Vec<(f64, String)> = slots
        .iter()
        .map(|&index| (keys[index].unwrap_or_default(), layer[index].clone()))
        .collect();
    keyed.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
    for (&slot, (_, id)) in slots.iter().zip(keyed.into_iter()) {
        layer[slot] = id;
    }
}

// ---------------------------------------------------------------------------
// Board-level placement
// ---------------------------------------------------------------------------

/// Shelf packing allocator for frames.
///
/// Miro's REST API has no "find me free space" endpoint (`findEmptySpace` only
/// exists in the Web SDK), and testing a new frame for collisions against every
/// frame on the board does not scale to hundreds of entry points. Instead we
/// reserve a region of the board and hand out positions from a running cursor:
/// O(1) per frame, no API calls, and overlaps are impossible by construction.
///
/// The state is meant to be persisted in the project metadata so incremental
/// runs keep appending instead of rescanning the board.
#[derive(Debug, Clone, PartialEq)]
pub struct ShelfAllocator {
    /// Top-left corner of the reserved region, in board coordinates.
    pub origin_x: f64,
    pub origin_y: f64,
    /// Cursor inside the region.
    pub cursor_x: f64,
    pub cursor_y: f64,
    /// Height of the tallest frame in the row being filled.
    pub row_height: f64,
    /// A row wraps once it would grow past this width.
    pub row_max_width: f64,
    /// Gap left between frames, horizontally and between rows.
    pub gutter: f64,
    /// Horizontal step per level of the cluster, so a frame's depth is visible from the
    /// board: a child starts further right than its parent, like an outline.
    pub indent: f64,
    /// The depth the open row belongs to, and whether it is closed to further frames.
    pub row_depth: usize,
    pub row_closed: bool,
    /// Whether anything has been placed on the open row, which `cursor_x` can no longer
    /// say on its own now that a row starts at an indent.
    pub row_used: bool,
}

impl ShelfAllocator {
    /// Default row width: the spiritual successor of the old fixed
    /// `MIRO_BOARD_COLUMNS = 5` grid — five wide frames per row, but frames of
    /// any size are handled without wasting space.
    pub const DEFAULT_ROW_MAX_WIDTH: f64 = 60_000.0;
    pub const DEFAULT_GUTTER: f64 = 1_000.0;
    /// Enough to read as a step at the zoom where a whole cluster fits on screen, against
    /// frames 7k–20k wide, and small enough that five levels add ~10k of width.
    pub const DEFAULT_INDENT: f64 = 2_000.0;


    pub fn new(origin_x: f64, origin_y: f64) -> Self {
        Self {
            origin_x,
            origin_y,
            cursor_x: 0.0,
            cursor_y: 0.0,
            row_height: 0.0,
            row_max_width: Self::DEFAULT_ROW_MAX_WIDTH,
            gutter: Self::DEFAULT_GUTTER,
            indent: Self::DEFAULT_INDENT,
            row_depth: 0,
            row_closed: false,
            row_used: false,
        }
    }

    /// Reserve room for a frame and return its **center** in board coordinates,
    /// which is what the Miro API expects.
    pub fn place(&mut self, width: f64, height: f64) -> (f64, f64) {
        self.place_in_outline(width, height, 0, false)
    }

    /// Place a frame as a line of an outline: indented by its depth in the cluster, under
    /// the frame that leads to it.
    ///
    /// A cluster is deployed in reading order (depth-first, calls in source order), so
    /// laying it out in that same order down the board makes the two agree: the parent is
    /// the nearest frame above with a smaller indent, the next sibling is below at the
    /// same indent, and what a frame leads to is below it and further right. Reading the
    /// cluster becomes scrolling down instead of hunting across a wall of shelves.
    ///
    /// A frame WITH children takes a row to itself, because its subtree follows underneath
    /// and a neighbour on the same row would be read as part of it. Leaf siblings share a
    /// row left to right, which is what keeps "one parent, six small helpers" compact.
    ///
    /// Rows remain exclusive horizontal bands, so frames still cannot overlap by
    /// construction — the one thing Miro refuses outright.
    pub fn place_in_outline(
        &mut self,
        width: f64,
        height: f64,
        depth: usize,
        has_children: bool,
    ) -> (f64, f64) {
        let left = depth as f64 * self.indent;
        let wraps = self.row_used && self.cursor_x + width > self.row_max_width;
        if self.row_closed || depth != self.row_depth || wraps {
            if self.row_used {
                self.cursor_y += self.row_height + self.gutter;
                self.row_height = 0.0;
            }
            self.cursor_x = left;
            self.row_depth = depth;
            self.row_closed = false;
            self.row_used = false;
        }
        let x = self.origin_x + self.cursor_x + width / 2.0;
        let y = self.origin_y + self.cursor_y + height / 2.0;
        self.cursor_x += width + self.gutter;
        self.row_height = self.row_height.max(height);
        self.row_used = true;
        // Its subtree goes underneath, so nothing else joins this row.
        self.row_closed = has_children;
        (x, y)
    }
}

/// Breathing room around content of this size: a fraction of it, between a floor and a
/// ceiling.
///
/// A fixed margin is wrong at both ends. 400 units around a thirty-line capture is a hairline;
/// around a four-line one it is half the frame, which is what made a small deployment look
/// like three mostly-empty boxes. Tying it to the content keeps the proportion while the floor
/// stops a tiny capture from being drawn edge to edge.
pub fn breathing_room(content: f64, floor: f64, ceiling: f64) -> f64 {
    (content * 0.06).clamp(floor, ceiling)
}

/// A rectangle on the board: a frame as the placement arithmetic sees it, with no id and no
/// title. `x`/`y` are the CENTRE, as Miro reports them.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Rect {
    pub x: f64,
    pub y: f64,
    pub width: f64,
    pub height: f64,
}

impl Rect {
    pub fn left(&self) -> f64 {
        self.x - self.width / 2.0
    }
    pub fn right(&self) -> f64 {
        self.x + self.width / 2.0
    }
    pub fn top(&self) -> f64 {
        self.y - self.height / 2.0
    }
    pub fn bottom(&self) -> f64 {
        self.y + self.height / 2.0
    }

    /// Do the two overlap, with `gap` of clearance demanded on every side?
    ///
    /// Miro refuses overlapping frames outright, with a 500, so this is the whole reason the
    /// arithmetic exists rather than a cursor that trusts its own bookkeeping.
    pub fn clashes(&self, other: &Rect, gap: f64) -> bool {
        self.left() - gap < other.right()
            && other.left() - gap < self.right()
            && self.top() - gap < other.bottom()
            && other.top() - gap < self.bottom()
    }
}

/// Where one contract's column of deployments lives, and where the next cluster joins it.
///
/// A column is not stored anywhere: it is DERIVED from the board every run, from the frames the
/// registry says belong to this contract. The auditor drags frames, deletes them, and adds their
/// own, and a cursor that remembers where it left off is a cursor that is wrong by the second
/// deploy. The board is the truth; the registry only says which frames are whose.
pub struct ColumnLayout {
    /// Clearance demanded between any two frames, on every side.
    pub gap: f64,
    /// The gap a NEW column leaves to the right of everything already on the board.
    ///
    /// Modest on purpose. It was 60k, on the theory that a column should reserve room for the
    /// widest cluster it might ever hold — but a cluster that does not fit is pushed DOWN,
    /// never sideways, so the reserve buys nothing and costs a screen of empty board between
    /// every two groups. What the gap has to do is read as a separation at the zoom where
    /// several columns fit on screen, and a few thousand units does that against frames that
    /// are themselves thousands wide.
    pub pitch: f64,
}

impl ColumnLayout {
    pub const DEFAULT_GAP: f64 = 1_500.0;
    pub const DEFAULT_PITCH: f64 = 8_000.0;

    pub fn new() -> Self {
        Self {
            gap: Self::DEFAULT_GAP,
            pitch: Self::DEFAULT_PITCH,
        }
    }

    /// The top-left a cluster of `width`×`height` takes in a column whose left edge is
    /// `column_left`, below everything that column already holds, pushed down until it clears
    /// every obstacle on the board.
    ///
    /// Pushing DOWN and never sideways is the whole point of a column: an entry point of this
    /// contract belongs under the previous one whatever its width, and the alternative —
    /// starting a second column when a cluster does not fit — scatters one contract across the
    /// board, which is what this feature exists to stop.
    pub fn place_in_column(
        &self,
        column_left: f64,
        column_bottom: Option<f64>,
        width: f64,
        height: f64,
        obstacles: &[Rect],
        top: f64,
    ) -> (f64, f64) {
        let mut y = match column_bottom {
            Some(bottom) => bottom + self.gap,
            None => top,
        };
        // Bounded, because an unbounded walk down a crowded board is a silent hang and a
        // deploy that lands far below everything is still a deploy you can read.
        for _ in 0..200 {
            let candidate = Rect {
                x: column_left + width / 2.0,
                y: y + height / 2.0,
                width,
                height,
            };
            let Some(hit) = obstacles.iter().find(|other| candidate.clashes(other, self.gap)) else {
                return (column_left, y);
            };
            // Straight to below the thing in the way, rather than a fixed step: a step small
            // enough for two frames is hundreds of iterations against one tall one.
            y = hit.bottom() + self.gap;
        }
        (column_left, y)
    }

    /// Where something that is NOT a column goes: clear to the LEFT of everything, aligned
    /// with the top of what is already there.
    ///
    /// Deployments march rightwards, so anything that is not a deployment — a map of the whole
    /// system, say — put on that side ends up between two groups it has nothing to do with,
    /// and stays there as the board grows. The left edge is the one side nothing else claims.
    pub fn open_left(&self, obstacles: &[Rect], width: f64) -> (f64, f64) {
        let Some(left) = obstacles.iter().map(|rect| rect.left()).reduce(f64::min) else {
            return (0.0, 0.0);
        };
        let top = obstacles
            .iter()
            .map(|rect| rect.top())
            .reduce(f64::min)
            .unwrap_or(0.0);
        (left - self.pitch.max(self.gap) - width, top)
    }

    /// Where a NEW column opens: clear to the right of everything on the board, aligned with
    /// the top of what is already there.
    ///
    /// Right of EVERYTHING, not of the last column: the board holds frames this tool did not
    /// draw, and a column that opens on top of one of them is a 500 from Miro rather than a
    /// cosmetic problem.
    pub fn open_column(&self, obstacles: &[Rect]) -> (f64, f64) {
        let Some(right) = obstacles
            .iter()
            .map(|rect| rect.right())
            .reduce(f64::max)
        else {
            return (0.0, 0.0);
        };
        let top = obstacles
            .iter()
            .map(|rect| rect.top())
            .reduce(f64::min)
            .unwrap_or(0.0);
        (right + self.pitch.max(self.gap), top)
    }
}

impl Default for ColumnLayout {
    fn default() -> Self {
        Self::new()
    }
}

/// The box a planned cluster occupies, from the frames it already decided on.
pub fn bounding_box(frames: &[Rect]) -> Option<Rect> {
    let left = frames.iter().map(|f| f.left()).reduce(f64::min)?;
    let right = frames.iter().map(|f| f.right()).reduce(f64::max)?;
    let top = frames.iter().map(|f| f.top()).reduce(f64::min)?;
    let bottom = frames.iter().map(|f| f.bottom()).reduce(f64::max)?;
    Some(Rect {
        x: (left + right) / 2.0,
        y: (top + bottom) / 2.0,
        width: right - left,
        height: bottom - top,
    })
}

#[cfg(test)]
mod layout_test {
    use super::*;

    fn node(id: &str, width: f64, height: f64) -> LayoutNode {
        LayoutNode {
            id: id.to_string(),
            width,
            height,
        }
    }

    fn edge(from: &str, to: &str, fraction: f64) -> LayoutEdge {
        LayoutEdge {
            from: from.to_string(),
            to: to.to_string(),
            from_line_fraction: fraction,
        }
    }

    fn layer_of(layout: &GraphLayout, id: &str) -> usize {
        layout.node(id).expect("node missing").layer
    }

    /// A helper reachable at depth 1 and at depth 2 must land on the deeper
    /// layer, otherwise a connector would point backwards.
    #[test]
    fn test_diamond_uses_longest_path() {
        let nodes = vec![
            node("root", 1000.0, 400.0),
            node("a", 1000.0, 400.0),
            node("b", 1000.0, 400.0),
            node("shared", 1000.0, 400.0),
        ];
        let edges = vec![
            edge("root", "a", 0.2),
            edge("root", "shared", 0.5),
            edge("a", "b", 0.3),
            edge("b", "shared", 0.4),
        ];
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        assert_eq!(layer_of(&layout, "root"), 0);
        assert_eq!(layer_of(&layout, "a"), 1);
        assert_eq!(layer_of(&layout, "b"), 2);
        assert_eq!(
            layer_of(&layout, "shared"),
            3,
            "shared must sink to the deepest caller"
        );

        for e in &edges {
            assert!(
                layer_of(&layout, &e.to) > layer_of(&layout, &e.from),
                "edge {} -> {} points backwards",
                e.from,
                e.to
            );
        }
    }

    #[test]
    fn test_cycle_is_reported_as_back_edge_and_does_not_hang() {
        let nodes = vec![
            node("root", 800.0, 300.0),
            node("a", 800.0, 300.0),
            node("b", 800.0, 300.0),
        ];
        let edges = vec![
            edge("root", "a", 0.1),
            edge("a", "b", 0.2),
            edge("b", "a", 0.9),
        ];
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        assert_eq!(layout.back_edges, vec![("b".to_string(), "a".to_string())]);
        assert_eq!(layer_of(&layout, "a"), 1);
        assert_eq!(layer_of(&layout, "b"), 2);
    }

    #[test]
    fn test_no_two_nodes_overlap() {
        let mut nodes = vec![node("root", 1800.0, 900.0)];
        let mut edges = Vec::new();
        for i in 0..7 {
            let id = format!("dep{i}");
            nodes.push(node(&id, 1200.0, 300.0 + 90.0 * i as f64));
            edges.push(edge("root", &id, i as f64 / 7.0));
        }
        for i in 0..4 {
            let id = format!("leaf{i}");
            nodes.push(node(&id, 1000.0, 260.0));
            edges.push(edge("dep0", &id, i as f64 / 4.0));
        }
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        for (i, a) in layout.nodes.iter().enumerate() {
            for b in layout.nodes.iter().skip(i + 1) {
                let overlap_x = (a.x - b.x).abs() < (a.width + b.width) / 2.0;
                let overlap_y = (a.y - b.y).abs() < (a.height + b.height) / 2.0;
                assert!(
                    !(overlap_x && overlap_y),
                    "{} and {} overlap",
                    a.id,
                    b.id
                );
            }
        }
    }

    #[test]
    fn test_every_node_fits_inside_the_frame() {
        let nodes = vec![
            node("root", 1800.0, 900.0),
            node("a", 1500.0, 1200.0),
            node("b", 1200.0, 400.0),
        ];
        let edges = vec![edge("root", "a", 0.3), edge("a", "b", 0.6)];
        let config = LayoutConfig::default();
        let layout = layout_graph("root", &nodes, &edges, config);

        for placed in &layout.nodes {
            assert!(
                placed.x - placed.width / 2.0 >= 0.0
                    && placed.x + placed.width / 2.0 <= layout.frame_width,
                "{} sticks out horizontally",
                placed.id
            );
            assert!(
                placed.y - placed.height / 2.0 >= 0.0
                    && placed.y + placed.height / 2.0 <= layout.frame_height,
                "{} sticks out vertically",
                placed.id
            );
        }
        // Nothing may intrude into the title band.
        for placed in &layout.nodes {
            assert!(placed.y - placed.height / 2.0 >= config.title_band);
        }
    }

    #[test]
    fn test_call_line_order_drives_vertical_order() {
        let nodes = vec![
            node("root", 1400.0, 900.0),
            node("called_last", 1000.0, 300.0),
            node("called_first", 1000.0, 300.0),
        ];
        // Declared in the wrong order on purpose: the fractions must win.
        let edges = vec![
            edge("root", "called_last", 0.90),
            edge("root", "called_first", 0.05),
        ];
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        let first = layout.node("called_first").unwrap();
        let last = layout.node("called_last").unwrap();
        assert!(
            first.y < last.y,
            "the callee invoked earlier in the body must be drawn above"
        );
    }

    /// Column splitting belongs to the layered algorithm, which only runs for
    /// graphs that are not trees — a tree is laid out as a tree, where one tall
    /// band is the honest shape and splitting it would create crossings. The
    /// extra shared node here is what makes this a DAG.
    #[test]
    fn test_tall_layer_is_split_into_columns() {
        let mut nodes = vec![node("root", 1200.0, 400.0), node("shared", 900.0, 200.0)];
        let mut edges = Vec::new();
        for i in 0..20 {
            let id = format!("dep{i}");
            nodes.push(node(&id, 1000.0, 1500.0));
            edges.push(edge("root", &id, i as f64 / 20.0));
            edges.push(edge(&id, "shared", 0.5));
        }
        let config = LayoutConfig {
            max_layer_height: 12_000.0,
            ..LayoutConfig::default()
        };
        let layout = layout_graph("root", &nodes, &edges, config);

        // 20 * 1500 + gutters ≈ 32k, so it must be broken up rather than
        // producing a 32k-tall frame.
        assert!(
            layout.frame_height < 20_000.0,
            "frame height {} was not reduced by column splitting",
            layout.frame_height
        );
        for (i, a) in layout.nodes.iter().enumerate() {
            for b in layout.nodes.iter().skip(i + 1) {
                let overlap_x = (a.x - b.x).abs() < (a.width + b.width) / 2.0;
                let overlap_y = (a.y - b.y).abs() < (a.height + b.height) / 2.0;
                assert!(!(overlap_x && overlap_y), "{} and {} overlap", a.id, b.id);
            }
        }
    }

    #[test]
    fn test_layout_is_deterministic() {
        let nodes = vec![
            node("root", 1800.0, 900.0),
            node("a", 1200.0, 500.0),
            node("b", 1200.0, 700.0),
            node("c", 1200.0, 300.0),
        ];
        let edges = vec![
            edge("root", "a", 0.1),
            edge("root", "b", 0.5),
            edge("a", "c", 0.4),
        ];
        let first = layout_graph("root", &nodes, &edges, LayoutConfig::default());
        let second = layout_graph("root", &nodes, &edges, LayoutConfig::default());
        assert_eq!(first.nodes, second.nodes);
    }

    #[test]
    fn test_shelf_allocator_never_overlaps_and_wraps_rows() {
        let mut allocator = ShelfAllocator::new(0.0, 100_000.0);
        allocator.row_max_width = 20_000.0;

        // Deliberately uneven sizes, the case a uniform grid handles badly.
        let sizes: Vec<(f64, f64)> = (0..40)
            .map(|i| {
                let width = 3_000.0 + (i % 7) as f64 * 2_500.0;
                let height = 1_500.0 + (i % 5) as f64 * 1_200.0;
                (width, height)
            })
            .collect();

        let mut rects = Vec::new();
        for (width, height) in &sizes {
            let (x, y) = allocator.place(*width, *height);
            rects.push((x, y, *width, *height));
        }

        for (i, a) in rects.iter().enumerate() {
            for b in rects.iter().skip(i + 1) {
                let overlap_x = (a.0 - b.0).abs() < (a.2 + b.2) / 2.0;
                let overlap_y = (a.1 - b.1).abs() < (a.3 + b.3) / 2.0;
                assert!(!(overlap_x && overlap_y), "frames {i} overlap");
            }
        }

        // Everything stays inside the reserved region.
        for (x, _y, width, _height) in &rects {
            assert!(x - width / 2.0 >= 0.0);
        }
    }

    /// A cluster placed in the order it is deployed — root, then its cards depth-first —
    /// must read as an outline: each frame indented by its depth, each one below the
    /// frame that leads to it, and nothing overlapping.
    #[test]
    fn test_outline_indents_by_depth_and_never_overlaps() {
        // (depth, has_children), exactly the order `deploy_one` recurses in:
        // root → a (→ a1, a2) → b (leaf) → c (leaf).
        let plan = [
            (0, true),
            (1, true),
            (2, false),
            (2, false),
            (1, false),
            (1, false),
        ];
        let mut allocator = ShelfAllocator::new(0.0, 0.0);
        let mut rects = Vec::new();
        for (i, (depth, has_children)) in plan.iter().enumerate() {
            let width = 6_000.0 + (i % 3) as f64 * 1_000.0;
            let height = 3_000.0;
            let (x, y) = allocator.place_in_outline(width, height, *depth, *has_children);
            rects.push((*depth, x, y, width, height));
        }

        for (i, a) in rects.iter().enumerate() {
            for b in rects.iter().skip(i + 1) {
                let overlap_x = (a.1 - b.1).abs() < (a.3 + b.3) / 2.0;
                let overlap_y = (a.2 - b.2).abs() < (a.4 + b.4) / 2.0;
                assert!(!(overlap_x && overlap_y), "frame {i} overlaps a later one");
            }
        }

        // The indent IS the depth: a row STARTS at depth * indent, and a frame sharing
        // that row sits further right still.
        for (i, (depth, x, y, width, _height)) in rects.iter().enumerate() {
            let left = x - width / 2.0;
            let indent = *depth as f64 * allocator.indent;
            let opens_row = !rects[..i].iter().any(|other| other.2 == *y);
            if opens_row {
                assert_eq!(left, indent, "row opened by frame {i} is not at its indent");
            } else {
                assert!(left > indent, "frame {i} is left of its indent");
            }
        }

        // Reading order is top to bottom: nothing is placed above a frame that came
        // before it, and a frame with a subtree gets its own band.
        for pair in rects.windows(2) {
            let (_, _, prev_y, _, prev_height) = pair[0];
            let (_, _, y, _, _) = pair[1];
            assert!(y >= prev_y, "a later frame was placed above an earlier one");
            let shares_row = y < prev_y + prev_height;
            assert!(
                !shares_row || pair[0].0 == pair[1].0,
                "frames at different depths shared a row"
            );
        }

        // `a1` and `a2` are leaf siblings, so they DO share their row — that is what
        // keeps "one parent, several small helpers" from becoming a column of air.
        assert_eq!(rects[2].2, rects[3].2);
        // `a` has children, so `b` could not join its row.
        assert!(rects[4].2 > rects[1].2);
    }

    #[test]
    fn test_shelf_allocator_state_round_trips() {
        let mut allocator = ShelfAllocator::new(0.0, 0.0);
        allocator.place(5_000.0, 2_000.0);
        let saved = allocator.clone();

        // Resuming from persisted state must continue where it left off.
        let mut resumed = saved.clone();
        let (x_a, y_a) = allocator.place(4_000.0, 1_000.0);
        let (x_b, y_b) = resumed.place(4_000.0, 1_000.0);
        assert_eq!((x_a, y_a), (x_b, y_b));
    }
}

#[cfg(test)]
mod tree_shaped_graph_test {
    use super::*;

    fn node(id: &str, width: f64, height: f64) -> LayoutNode {
        LayoutNode {
            id: id.to_string(),
            width,
            height,
        }
    }

    fn edge(from: &str, to: &str) -> LayoutEdge {
        LayoutEdge {
            from: from.to_string(),
            to: to.to_string(),
            from_line_fraction: 0.5,
        }
    }

    /// Two edges cross when one starts above the other and ends below it.
    fn crossings(layout: &GraphLayout, edges: &[LayoutEdge]) -> usize {
        let segment = |edge: &LayoutEdge| {
            let from = layout.node(&edge.from)?;
            let to = layout.node(&edge.to)?;
            Some((from.y, to.y, from.layer))
        };
        let segments: Vec<_> = edges.iter().filter_map(segment).collect();
        let mut count = 0;
        for (index, a) in segments.iter().enumerate() {
            for b in segments.iter().skip(index + 1) {
                if a.2 != b.2 {
                    continue; // only siblings' edges share a corridor
                }
                if (a.0 - b.0) * (a.1 - b.1) < 0.0 {
                    count += 1;
                }
            }
        }
        count
    }

    /// The shape a deployment actually produces: the same helper appears once
    /// per caller instead of being shared.
    #[test]
    fn test_tree_layout_has_no_crossings() {
        let mut nodes = vec![node("root", 1600.0, 700.0)];
        let mut edges = Vec::new();
        for branch in 0..4 {
            let parent = format!("dep{branch}");
            nodes.push(node(&parent, 1200.0, 400.0));
            edges.push(edge("root", &parent));
            for leaf in 0..3 {
                let child = format!("leaf{branch}_{leaf}");
                nodes.push(node(&child, 1000.0, 250.0));
                edges.push(edge(&parent, &child));
            }
        }
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        assert_eq!(crossings(&layout, &edges), 0);
        for (i, a) in layout.nodes.iter().enumerate() {
            for b in layout.nodes.iter().skip(i + 1) {
                let overlap_x = (a.x - b.x).abs() < (a.width + b.width) / 2.0;
                let overlap_y = (a.y - b.y).abs() < (a.height + b.height) / 2.0;
                assert!(!(overlap_x && overlap_y), "{} and {} overlap", a.id, b.id);
            }
        }
    }

    /// The entry point sits at the TOP of the band its children occupy, not its middle.
    ///
    /// Centring it is the textbook tidy-tree and it leaves empty space above the one box
    /// a reader starts from, while everything done to a frame afterwards — reading it,
    /// adding a declaration underneath — wants that box near the top-left and the room
    /// below it. The layered path already top-aligns every layer.
    #[test]
    fn test_root_sits_at_the_top_not_the_middle() {
        let nodes = vec![
            node("root", 1200.0, 300.0),
            node("a", 1000.0, 200.0),
            node("b", 1000.0, 600.0),
            node("c", 1000.0, 200.0),
        ];
        let edges = vec![edge("root", "a"), edge("root", "b"), edge("root", "c")];
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        // Compared by their TOP edges: boxes of different heights share a top, not a centre.
        let root = layout.node("root").unwrap();
        let first = layout.node("a").unwrap();
        let top_of = |node: &PlacedNode| node.y - node.height / 2.0;
        assert!(
            (top_of(root) - top_of(first)).abs() < 1.0,
            "root's top at {} but the first child's is at {}",
            top_of(root),
            top_of(first)
        );
        let last = layout.node("c").unwrap();
        assert!(
            root.y < last.y,
            "root at {} should sit above the last child at {}",
            root.y,
            last.y
        );
    }

    /// A light sibling is NOT pushed below a heavy sibling's whole subtree.
    ///
    /// The tidy-tree layout gave each subtree a band of its own height, so a getter drawn
    /// after a deep branch started below everything that branch reached: on a real frame,
    /// two of them sat 5,500px down with their column empty above them, and the frame
    /// reserved the SUM of the bands instead of its tallest column. Columns pack from the
    /// top, so the frame is as tall as what is in it.
    #[test]
    fn a_light_sibling_is_not_pushed_below_a_heavy_one() {
        let mut nodes = vec![
            node("root", 1000.0, 300.0),
            node("heavy", 1000.0, 300.0),
            node("light", 1000.0, 300.0),
        ];
        let mut edges = vec![edge("root", "heavy"), edge("root", "light")];
        // A deep chain under `heavy`, which is what used to reserve the band.
        for depth in 0..8 {
            let id = format!("deep{depth}");
            nodes.push(node(&id, 1000.0, 600.0));
            let parent = if depth == 0 { "heavy".to_string() } else { format!("deep{}", depth - 1) };
            edges.push(edge(&parent, &id));
        }
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        let heavy = layout.node("heavy").unwrap();
        let light = layout.node("light").unwrap();
        let gap = (light.y - light.height / 2.0) - (heavy.y + heavy.height / 2.0);
        assert!(
            gap < LayoutConfig::default().gutter_y + 1.0,
            "light sits {gap} below heavy; they share a column and should be one gutter apart"
        );
        // And the frame is as tall as its tallest column, not the sum of the subtrees.
        assert!(
            layout.frame_height < 3_000.0,
            "frame is {} tall for a column holding 600px of boxes",
            layout.frame_height
        );
    }

    /// Repeating a shared helper is the whole point: each copy is its own node.
    #[test]
    fn test_repeated_helper_gets_its_own_box() {
        let nodes = vec![
            node("root", 1200.0, 300.0),
            node("a", 1000.0, 200.0),
            node("b", 1000.0, 200.0),
            node("helper#1", 900.0, 150.0),
            node("helper#2", 900.0, 150.0),
        ];
        let edges = vec![
            edge("root", "a"),
            edge("root", "b"),
            edge("a", "helper#1"),
            edge("b", "helper#2"),
        ];
        let layout = layout_graph("root", &nodes, &edges, LayoutConfig::default());

        let first = layout.node("helper#1").unwrap();
        let second = layout.node("helper#2").unwrap();
        assert_ne!(first.y, second.y, "the two copies must not sit on top of each other");
        assert_eq!(first.layer, second.layer);
        assert_eq!(crossings(&layout, &edges), 0);
    }
}

/// Prefix marking a node that exists only to bend an edge.
const BEND_PREFIX: &str = "\u{0}bend";

fn is_bend_point(id: &str) -> bool {
    id.starts_with(BEND_PREFIX)
}

/// Split every edge that skips a layer into a chain of one-layer hops.
///
/// Returns the augmented node and edge sets, the bend points belonging to each
/// input edge (aligned with `edges`), and the layer of every node including the
/// new ones.
///
/// The bend points have no size: they claim a slot in their layer's ordering,
/// which pushes the screenshots apart by one gutter, and that gutter is the
/// corridor the edge travels down.
#[allow(clippy::type_complexity)]
fn insert_bend_points(
    nodes: &[LayoutNode],
    edges: &[LayoutEdge],
    forward_edges: &[LayoutEdge],
    mut layers: HashMap<String, usize>,
) -> (
    Vec<LayoutNode>,
    Vec<LayoutEdge>,
    Vec<Vec<String>>,
    HashMap<String, usize>,
) {
    let is_forward = |edge: &LayoutEdge| {
        forward_edges
            .iter()
            .any(|kept| kept.from == edge.from && kept.to == edge.to)
    };

    let mut augmented_nodes = nodes.to_vec();
    let mut augmented_edges: Vec<LayoutEdge> = Vec::new();
    let mut routes: Vec<Vec<String>> = vec![Vec::new(); edges.len()];

    for (index, edge) in edges.iter().enumerate() {
        let (Some(&from_layer), Some(&to_layer)) =
            (layers.get(&edge.from), layers.get(&edge.to))
        else {
            continue;
        };

        // A cycle runs backwards by definition and is drawn dashed; bending it
        // would only add points to a line that is already an exception.
        if !is_forward(edge) || to_layer <= from_layer + 1 {
            augmented_edges.push(edge.clone());
            continue;
        }

        let mut previous = edge.from.clone();
        for layer in (from_layer + 1)..to_layer {
            let id = format!("{BEND_PREFIX}{index}_{layer}");
            augmented_nodes.push(LayoutNode {
                id: id.clone(),
                width: 0.0,
                height: 0.0,
            });
            layers.insert(id.clone(), layer);
            augmented_edges.push(LayoutEdge {
                from: previous,
                to: id.clone(),
                // Inherit the caller's fraction so the chain keeps the vertical
                // order of the calls it came from.
                from_line_fraction: edge.from_line_fraction,
            });
            routes[index].push(id.clone());
            previous = id;
        }
        augmented_edges.push(LayoutEdge {
            from: previous,
            to: edge.to.clone(),
            from_line_fraction: edge.from_line_fraction,
        });
    }

    (augmented_nodes, augmented_edges, routes, layers)
}

#[cfg(test)]
mod column_test {
    use super::{bounding_box, ColumnLayout, Rect};

    fn rect(left: f64, top: f64, width: f64, height: f64) -> Rect {
        Rect {
            x: left + width / 2.0,
            y: top + height / 2.0,
            width,
            height,
        }
    }

    /// An empty board puts the first column at the origin.
    #[test]
    fn the_first_column_opens_at_the_origin() {
        assert_eq!(ColumnLayout::new().open_column(&[]), (0.0, 0.0));
    }

    /// A new column opens clear of EVERYTHING, not of the last column — the board holds
    /// frames this tool did not draw.
    #[test]
    fn a_new_column_opens_right_of_everything() {
        let layout = ColumnLayout::new();
        let board = [rect(0.0, 0.0, 10_000.0, 5_000.0), rect(90_000.0, 40_000.0, 3_000.0, 1_000.0)];
        let (left, top) = layout.open_column(&board);
        assert!(left >= 93_000.0, "opened at {left}, which is over the far frame");
        assert_eq!(top, 0.0, "aligned with the top of what is already there");
    }

    /// The second cluster of a contract lands under the first, in the same column.
    #[test]
    fn the_next_cluster_lands_under_the_previous_one() {
        let layout = ColumnLayout::new();
        let first = rect(0.0, 0.0, 10_000.0, 4_000.0);
        let (x, y) = layout.place_in_column(0.0, Some(first.bottom()), 8_000.0, 2_000.0, &[first], 0.0);
        assert_eq!(x, 0.0, "same column");
        assert!(y >= first.bottom(), "below the previous cluster");
    }

    /// A cluster WIDER than its column is pushed down past whatever is beside it, never
    /// sideways: a contract's deployments stay in one column.
    #[test]
    fn a_wide_cluster_is_pushed_down_not_sideways() {
        let layout = ColumnLayout::new();
        let mine = rect(0.0, 0.0, 10_000.0, 4_000.0);
        // The neighbouring column, which a 70k-wide cluster would run straight into.
        let neighbour = rect(60_000.0, 0.0, 20_000.0, 30_000.0);
        let (x, y) = layout.place_in_column(
            0.0,
            Some(mine.bottom()),
            70_000.0,
            5_000.0,
            &[mine, neighbour],
            0.0,
        );
        assert_eq!(x, 0.0, "still its own column");
        assert!(y >= neighbour.bottom(), "cleared the neighbour by going under it");
        let placed = rect(x, y, 70_000.0, 5_000.0);
        for other in [mine, neighbour] {
            assert!(!placed.clashes(&other, 0.0), "overlaps {other:?}");
        }
    }

    /// Nothing is placed on top of anything, which is not a nicety: Miro refuses an
    /// overlapping frame with a 500.
    #[test]
    fn a_placement_never_overlaps_an_obstacle() {
        let layout = ColumnLayout::new();
        let board: Vec<Rect> = (0..12)
            .map(|index| rect(index as f64 * 3_000.0, index as f64 * 1_500.0, 5_000.0, 4_000.0))
            .collect();
        let (x, y) = layout.place_in_column(0.0, Some(0.0), 9_000.0, 3_000.0, &board, 0.0);
        let placed = rect(x, y, 9_000.0, 3_000.0);
        for other in &board {
            assert!(!placed.clashes(other, 0.0), "overlaps {other:?}");
        }
    }

    /// An empty column starts at the top the caller gives it, not below the board.
    #[test]
    fn an_empty_column_starts_at_its_top() {
        let layout = ColumnLayout::new();
        let (_, y) = layout.place_in_column(50_000.0, None, 4_000.0, 2_000.0, &[], 1_234.0);
        assert_eq!(y, 1_234.0);
    }

    /// The box a cluster occupies is the union of its frames.
    #[test]
    fn a_bounding_box_covers_every_frame() {
        let frames = [rect(0.0, 0.0, 1_000.0, 500.0), rect(2_000.0, 300.0, 500.0, 900.0)];
        let box_ = bounding_box(&frames).expect("two frames");
        assert_eq!(box_.left(), 0.0);
        assert_eq!(box_.right(), 2_500.0);
        assert_eq!(box_.top(), 0.0);
        assert_eq!(box_.bottom(), 1_200.0);
    }

    /// No frames, no box — the caller decides what that means.
    #[test]
    fn no_frames_is_no_box() {
        assert!(bounding_box(&[]).is_none());
    }
}

#[cfg(test)]
mod breathing_room_test {
    use super::breathing_room;

    /// A small capture gets the floor, not a margin half its own size.
    #[test]
    fn a_small_capture_gets_the_floor() {
        assert_eq!(breathing_room(600.0, 120.0, 400.0), 120.0);
    }

    /// A large one is capped, so a thirty-line frame does not grow a border nobody asked for.
    #[test]
    fn a_large_capture_is_capped() {
        assert_eq!(breathing_room(20_000.0, 120.0, 400.0), 400.0);
    }

    /// In between it follows the content, which is the whole point.
    #[test]
    fn in_between_it_follows_the_content() {
        assert_eq!(breathing_room(4_000.0, 120.0, 400.0), 240.0);
    }
}