chartlet 0.23.0

//! Trees: a root and the nodes below it, such as an organization chart, an ownership structure
//! or a hierarchy of norms.
//!
//! Every level of the tree takes a row (a column in landscape); the children of a node sit side
//! by side below it and the node is centered over them. Subtrees are pushed together until they
//! are a gap apart at every level, so that a narrow subtree tucks in under a broad neighbour. The
//! description and the data table list every node with its parent, so that the picture is never
//! the only place the structure is said.

use std::{
    f64::consts::{FRAC_PI_2, TAU},
    fmt::Write as _,
};

use crate::{
    DataTable,
    diagram::{self, chip, pixels, rounded, warn_growth, warn_growth_advising, wrap},
    error::ChartWarning,
    flow::{Shape, focus_classes, shape},
    heat,
    layout::{NARROW, count, format_value, push_title, title_extra},
    metrics::TextMetrics,
    parts, roles,
    scene::{Element, Hotspot, Scene, Text, TextAnchor},
    spec::{
        ChartSpec, DiagramOrientation, DiagramRole, NumberStyle, PartSpec, TreeLayout,
        TreeNodeKind, TreeSpec,
    },
    text,
};

const MARGIN: f64 = 24.0;
const COMPACT_MARGIN: f64 = 12.0;
const BOTTOM: f64 = 16.0;
const LABEL_SIZE: f64 = 13.0;
const SUBLABEL_SIZE: f64 = 11.0;
/// Distance between the baselines of a node's label lines, and of its sublabel lines.
const NODE_LINE: f64 = 16.0;
const SUBLABEL_LINE: f64 = 14.0;
const PAD: f64 = 12.0;
const MIN_NODE: f64 = 96.0;
const MAX_NODE: f64 = 190.0;
/// The same in a diagram narrower than [`NARROW`], such as a mobile variant.
const COMPACT_MIN_NODE: f64 = 64.0;
const COMPACT_MAX_NODE: f64 = 120.0;
/// Space between two nodes next to each other, and between two subtrees.
const SIBLING_GAP: f64 = 20.0;
const COMPACT_SIBLING_GAP: f64 = 10.0;
/// Space between the two boxes of a couple.
const PARTNER_GAP: f64 = 28.0;
/// Space between two levels, and the same when a link between them carries a label.
const LEVEL_GAP: f64 = 36.0;
const LINKED_LEVEL_GAP: f64 = 58.0;
/// In landscape the label of a link sits on its last, horizontal stretch, which must be long
/// enough to hold it.
const LINKED_COLUMN_GAP: f64 = 112.0;

pub(crate) fn layout(
    spec: &ChartSpec,
    warnings: &mut Vec<ChartWarning>,
    metrics: &impl TextMetrics,
) -> Scene {
    if tree(spec).distances.is_some() {
        return crate::dendrogram::layout(spec, warnings, metrics);
    }
    let Some((view, kept)) = tree(spec).collapsed_view() else {
        return layout_all(spec, warnings, metrics);
    };
    // The drawing leaves out what hangs below a collapsed node: it is laid out as a smaller
    // tree, and its warnings are renamed to the nodes of the specification.
    let mut drawn = spec.clone();
    drawn.tree = Some(view);
    let before = warnings.len();
    let scene = layout_all(&drawn, warnings, metrics);
    for warning in &mut warnings[before..] {
        if let Some(rest) = warning.path.strip_prefix("/tree/nodes/")
            && let Some((index, tail)) = rest.split_once('/')
            && let Ok(index) = index.parse::<usize>()
        {
            warning.path = format!("/tree/nodes/{}/{tail}", kept[index]);
        }
    }
    scene
}

/// The tree as drawn, with the key of its node colors below when its nodes have values.
fn layout_all(
    spec: &ChartSpec,
    warnings: &mut Vec<ChartWarning>,
    metrics: &impl TextMetrics,
) -> Scene {
    let tree = tree(spec);
    let mut scene = draw_all(spec, warnings, metrics);
    let values: Vec<Option<f64>> = tree.nodes.iter().map(|node| node.value).collect();
    let margin = if spec.width < NARROW {
        COMPACT_MARGIN
    } else {
        MARGIN
    };
    heat::push_key(
        &mut scene,
        spec,
        (&heat::name(spec, tree.value_label.as_deref()), &values),
        margin,
        metrics,
    );
    let names = parts::names(tree.nodes.iter().map(|node| node.parts.as_slice()));
    parts::push_legend(&mut scene, &names, margin, metrics);
    let used = roles::used(tree.nodes.iter().map(|node| node.role), std::iter::empty());
    roles::push_legend(
        &mut scene,
        spec.locale,
        &used,
        (margin, roles::push_badge),
        metrics,
    );
    scene
}

fn draw_all(
    spec: &ChartSpec,
    warnings: &mut Vec<ChartWarning>,
    metrics: &impl TextMetrics,
) -> Scene {
    let tree = tree(spec);
    let compact = spec.width < NARROW;
    let margin = if compact { COMPACT_MARGIN } else { MARGIN };
    let width = f64::from(spec.width);
    let top = 56.0 + title_extra(spec, width - 2.0 * margin, metrics);
    let nodes = boxes(tree, compact, metrics, warnings);
    // Type tags belong to the editorial look and not to a narrow canvas.
    let tags = spec.look == crate::spec::Look::Editorial && spec.tags && !compact;
    if tree.layout == TreeLayout::Radial {
        let radial = Radial::new(spec, tree, &nodes, (top, margin, compact));
        let mut elements = Vec::new();
        push_title(
            &mut elements,
            spec,
            margin,
            width - 2.0 * margin,
            metrics,
            warnings,
        );
        warn_growth_advising(
            spec,
            (radial.width, radial.height),
            "use the layered layout",
            warnings,
        );
        radial.draw((tree, (spec.number_style(), tags)), &nodes, &mut elements);
        return Scene {
            width: pixels(radial.width),
            height: pixels(radial.height),
            elements,
        };
    }
    let landscape = match tree.orientation {
        DiagramOrientation::Portrait => false,
        DiagramOrientation::Landscape => true,
        DiagramOrientation::Auto => {
            let portrait = Plan::new(spec, tree, &nodes, false, (top, margin, compact));
            let landscape = Plan::new(spec, tree, &nodes, true, (top, margin, compact));
            diagram::prefers_landscape(
                spec,
                (portrait.width, portrait.height),
                (landscape.width, landscape.height),
            )
        }
    };
    let plan = Plan::new(spec, tree, &nodes, landscape, (top, margin, compact));
    let mut elements = Vec::new();
    push_title(
        &mut elements,
        spec,
        margin,
        width - 2.0 * margin,
        metrics,
        warnings,
    );
    warn_growth(spec, plan.width, plan.height, warnings);
    plan.draw(
        (tree, (spec.number_style(), tags)),
        &nodes,
        metrics,
        &mut elements,
    );
    Scene {
        width: pixels(plan.width),
        height: pixels(plan.height),
        elements,
    }
}

fn tree(spec: &ChartSpec) -> &TreeSpec {
    spec.tree
        .as_ref()
        .expect("validated trees carry a tree block")
}

/// A node as drawn: its label and sublabel lines and its box, width and height.
struct NodeBox {
    lines: Vec<String>,
    sublines: Vec<String>,
    width: f64,
    height: f64,
}

fn boxes(
    tree: &TreeSpec,
    compact: bool,
    metrics: &impl TextMetrics,
    warnings: &mut Vec<ChartWarning>,
) -> Vec<NodeBox> {
    let (min, max) = if compact {
        (COMPACT_MIN_NODE, COMPACT_MAX_NODE)
    } else {
        (MIN_NODE, MAX_NODE)
    };
    tree.nodes
        .iter()
        .enumerate()
        .map(|(index, node)| {
            // Never narrower than the longest word, which cannot wrap.
            let word = node
                .label
                .split(' ')
                .map(|word| metrics.width(word, LABEL_SIZE))
                .fold(0.0, f64::max);
            let room = (max - 2.0 * PAD).max(word);
            let lines = wrap(
                &node.label,
                room,
                LABEL_SIZE,
                metrics,
                warnings,
                &format!("/tree/nodes/{index}/label"),
            );
            let sublines = node.sublabel.as_ref().map_or_else(Vec::new, |sublabel| {
                wrap(
                    sublabel,
                    room,
                    SUBLABEL_SIZE,
                    metrics,
                    warnings,
                    &format!("/tree/nodes/{index}/sublabel"),
                )
            });
            let text = lines
                .iter()
                .map(|line| metrics.width(line, LABEL_SIZE))
                .chain(
                    sublines
                        .iter()
                        .map(|line| metrics.width(line, SUBLABEL_SIZE)),
                )
                .fold(0.0, f64::max);
            // A person's head takes room on top of the box.
            let head = if node.kind == TreeNodeKind::Person {
                18.0
            } else {
                0.0
            };
            let stripe = if node.parts.is_empty() {
                0.0
            } else {
                parts::ROOM
            };
            let height = 20.0
                + NODE_LINE * count(lines.len())
                + SUBLABEL_LINE * count(sublines.len())
                + head
                + stripe;
            NodeBox {
                width: (text + 2.0 * PAD)
                    .clamp(min, max.max(room + 2.0 * PAD))
                    .ceil(),
                height,
                lines,
                sublines,
            }
        })
        .collect()
}

/// One orientation of the layout. Positions are centers, on the page.
struct Plan {
    landscape: bool,
    center: Vec<(f64, f64)>,
    /// Each level's row on the main axis, on the page: where it begins and ends.
    rows: Vec<(f64, f64)>,
    /// The level of every node.
    levels: Vec<usize>,
    width: f64,
    height: f64,
}

/// The cross position of every node, the root at 0.
///
/// Subtrees go from the leaves up: each node's offset to its parent, and the reach of its subtree
/// on either side at every level, measured from the node's own center. The next child of a node
/// is pushed as far as it must so that it keeps `gap` from everything placed before it at every
/// level, and the node then stands over the middle of its first and last child.
///
/// A couple counts as one node whose reach on the two sides is `extent`, from the middle of the
/// line between its partners; a partner takes no position of its own here.
fn cross_positions(
    tree: &TreeSpec,
    count_of_nodes: usize,
    extent: impl Fn(usize) -> (f64, f64),
    gap: f64,
) -> Vec<f64> {
    let order = tree.reading_order();
    let mut offset = vec![0.0; count_of_nodes];
    let mut reach: Vec<Vec<(f64, f64)>> = vec![Vec::new(); count_of_nodes];
    for &node in order
        .iter()
        .rev()
        .filter(|node| tree.head_of(**node).is_none())
    {
        let own = extent(node);
        let children = tree.children(node);
        let mut placed: Vec<(f64, f64)> = Vec::new();
        let mut at = Vec::with_capacity(children.len());
        for &child in &children {
            let shift = reach[child]
                .iter()
                .zip(&placed)
                .map(|(new, old)| old.1 + gap - new.0)
                .fold(f64::NEG_INFINITY, f64::max);
            let shift = if placed.is_empty() { 0.0 } else { shift };
            for (level, extent) in reach[child].iter().enumerate() {
                let moved = (extent.0 + shift, extent.1 + shift);
                match placed.get_mut(level) {
                    Some(old) => *old = (old.0.min(moved.0), old.1.max(moved.1)),
                    None => placed.push(moved),
                }
            }
            at.push(shift);
        }
        // The node stands over the middle of its first and last child.
        let middle = match (at.first(), at.last()) {
            (Some(first), Some(last)) => f64::midpoint(*first, *last),
            _ => 0.0,
        };
        for (&child, shift) in children.iter().zip(&at) {
            offset[child] = shift - middle;
        }
        let mut extents = vec![own];
        extents.extend(
            placed
                .iter()
                .map(|(low, high)| (low - middle, high - middle)),
        );
        reach[node] = extents;
    }
    // Positions across: the root at 0, every other node from its parent.
    let mut cross = vec![0.0; count_of_nodes];
    for &node in &order {
        if let Some(parent) = tree.parent_of(node) {
            cross[node] = cross[parent] + offset[node];
        }
    }
    cross
}

/// The level of every node, where each level's row begins along the flow and how deep it is: as
/// deep as its deepest node, with more room before a level whose links carry labels.
fn level_rows(
    tree: &TreeSpec,
    count_of_nodes: usize,
    along: impl Fn(usize) -> f64,
    landscape: bool,
) -> (Vec<usize>, Vec<f64>, Vec<f64>) {
    let depths: Vec<usize> = (0..count_of_nodes).map(|node| tree.depth(node)).collect();
    let levels = depths.iter().copied().max().unwrap_or(0) + 1;
    let mut thickness = vec![0.0_f64; levels];
    let mut linked = vec![false; levels];
    for node in 0..count_of_nodes {
        thickness[depths[node]] = thickness[depths[node]].max(along(node));
        linked[depths[node]] |= tree.nodes[node].link.is_some();
    }
    let mut level_start = vec![0.0; levels];
    for level in 1..levels {
        let space = if linked[level] && landscape {
            LINKED_COLUMN_GAP
        } else if linked[level] {
            LINKED_LEVEL_GAP
        } else {
            LEVEL_GAP
        };
        level_start[level] = level_start[level - 1] + thickness[level - 1] + space;
    }
    (depths, level_start, thickness)
}

impl Plan {
    fn new(
        spec: &ChartSpec,
        tree: &TreeSpec,
        nodes: &[NodeBox],
        landscape: bool,
        (top, margin, compact): (f64, f64, bool),
    ) -> Self {
        let gap = if compact {
            COMPACT_SIBLING_GAP
        } else {
            SIBLING_GAP
        };
        // Across the levels (the cross axis) and along them (the main axis).
        let across = |node: usize| {
            if landscape {
                nodes[node].height
            } else {
                nodes[node].width
            }
        };
        let along = |node: usize| {
            if landscape {
                nodes[node].width
            } else {
                nodes[node].height
            }
        };
        // A couple is as wide as its two boxes and the room between them, and the middle of that
        // room is where its children's lines start.
        let extent = |node: usize| match tree.partner_of(node) {
            Some(partner) => (
                -(across(node) + PARTNER_GAP / 2.0),
                across(partner) + PARTNER_GAP / 2.0,
            ),
            None => (-across(node) / 2.0, across(node) / 2.0),
        };
        let mut cross = cross_positions(tree, nodes.len(), extent, gap);
        for node in 0..nodes.len() {
            if let Some(partner) = tree.partner_of(node) {
                let middle = cross[node];
                cross[node] = middle - PARTNER_GAP / 2.0 - across(node) / 2.0;
                cross[partner] = middle + PARTNER_GAP / 2.0 + across(partner) / 2.0;
            }
        }
        let (depths, level_start, thickness) = level_rows(tree, nodes.len(), along, landscape);
        let levels = thickness.len();
        let length = level_start[levels - 1] + thickness[levels - 1];
        let (low, high) = cross.iter().enumerate().fold(
            (f64::INFINITY, f64::NEG_INFINITY),
            |(low, high), (node, at)| {
                (
                    low.min(at - across(node) / 2.0),
                    high.max(at + across(node) / 2.0),
                )
            },
        );
        let breadth = high - low;
        let (width, height) = (f64::from(spec.width), f64::from(spec.height));
        let (page_width, page_height) = if landscape {
            (
                width.max(2.0 * margin + length),
                height.max(top + breadth + BOTTOM),
            )
        } else {
            (
                width.max(2.0 * margin + breadth),
                height.max(top + length + BOTTOM),
            )
        };
        // The tree stands in the middle of the room the canvas leaves across, and begins at the
        // top (at the left in landscape).
        let center = (0..nodes.len())
            .map(|node| {
                // Nodes of a level start where the level starts.
                let along_at = level_start[depths[node]] + along(node) / 2.0;
                if landscape {
                    let room = page_height - top - BOTTOM;
                    (
                        margin + along_at,
                        top + (room - breadth) / 2.0 + cross[node] - low,
                    )
                } else {
                    let room = page_width - 2.0 * margin;
                    (
                        margin + (room - breadth) / 2.0 + cross[node] - low,
                        top + along_at,
                    )
                }
            })
            .collect();
        let origin = if landscape { margin } else { top };
        let rows = (0..levels)
            .map(|level| {
                (
                    origin + level_start[level],
                    origin + level_start[level] + thickness[level],
                )
            })
            .collect();
        Self {
            landscape,
            center,
            rows,
            levels: depths,
            width: page_width,
            height: page_height,
        }
    }

    /// A node's box on the page: left, top, width and height.
    fn node_box(&self, nodes: &[NodeBox], node: usize) -> (f64, f64, f64, f64) {
        let (x, y) = self.center[node];
        let (width, height) = (nodes[node].width, nodes[node].height);
        (x - width / 2.0, y - height / 2.0, width, height)
    }

    fn draw(
        &self,
        (tree, style): (&TreeSpec, (NumberStyle, bool)),
        nodes: &[NodeBox],
        metrics: &impl TextMetrics,
        elements: &mut Vec<Element>,
    ) {
        for node in 0..nodes.len() {
            let Some(partner) = tree.partner_of(node) else {
                continue;
            };
            elements.push(Element::Group(focus_classes(
                None,
                &[node.min(partner), node.max(partner)],
            )));
            let (from, to) = self.couple_line(nodes, node, partner);
            elements.push(Element::Polyline(diagram::polyline(
                vec![from, to],
                "chartlet-flow-edge",
                Some(format!(
                    "{} + {}",
                    tree.nodes[node].label, tree.nodes[partner].label
                )),
            )));
            elements.push(Element::GroupEnd);
        }
        let mut labels = Vec::new();
        for node in tree.reading_order() {
            let Some(parent) = tree.parent_of(node) else {
                continue;
            };
            elements.push(Element::Group(focus_classes(
                None,
                &[parent.min(node), parent.max(node)],
            )));
            self.draw_link(tree, nodes, parent, node, elements, &mut labels);
            elements.push(Element::GroupEnd);
        }
        for (lines, at, classes) in labels {
            elements.push(Element::Group(classes));
            chip(&lines, at, TextAnchor::Middle, metrics, elements);
            elements.push(Element::GroupEnd);
        }
        draw_nodes(
            (tree, style),
            nodes,
            |node| self.node_box(nodes, node),
            elements,
        );
    }

    /// The short line between the two boxes of a couple: from the head to its partner.
    fn couple_line(
        &self,
        nodes: &[NodeBox],
        head: usize,
        partner: usize,
    ) -> ((f64, f64), (f64, f64)) {
        let (ax, ay, aw, ah) = self.node_box(nodes, head);
        let (bx, by, bw, bh) = self.node_box(nodes, partner);
        if self.landscape {
            // Stacked: the line runs down where the two boxes overlap across.
            let x = f64::midpoint(ax.max(bx), (ax + aw).min(bx + bw));
            ((x, ay + ah), (x, by))
        } else {
            let y = f64::midpoint(ay.max(by), (ay + ah).min(by + bh));
            ((ax + aw, y), (bx, y))
        }
    }

    /// Where the lines to the children of `parent` start: on its bottom edge, or, for a couple,
    /// in the middle of the line between the partners.
    fn start_of(&self, nodes: &[NodeBox], parent: usize, partner: Option<usize>) -> (f64, f64) {
        if let Some(partner) = partner {
            let (from, to) = self.couple_line(nodes, parent, partner);
            return (f64::midpoint(from.0, to.0), f64::midpoint(from.1, to.1));
        }
        let (x, y, width, height) = self.node_box(nodes, parent);
        if self.landscape {
            (x + width, y + height / 2.0)
        } else {
            (x + width / 2.0, y + height)
        }
    }

    /// The line from a parent to a child: down from the parent, across, and down into the child
    /// (right, across and right in landscape), with the child's link on its last stretch.
    fn draw_link(
        &self,
        tree: &TreeSpec,
        nodes: &[NodeBox],
        parent: usize,
        child: usize,
        elements: &mut Vec<Element>,
        labels: &mut Vec<(Vec<String>, (f64, f64), String)>,
    ) {
        let (cx, cy, cw, ch) = self.node_box(nodes, child);
        // The line turns halfway between the row of the parent and the row of the child, the
        // same for all children of a level.
        let (_, parent_end) = self.rows[self.levels[parent]];
        let (child_start, _) = self.rows[self.levels[child]];
        let middle = f64::midpoint(parent_end, child_start);
        let from = self.start_of(nodes, parent, tree.partner_of(parent));
        let points = if self.landscape {
            let end = cy + ch / 2.0;
            vec![from, (middle, from.1), (middle, end), (cx, end)]
        } else {
            let end = cx + cw / 2.0;
            vec![from, (from.0, middle), (end, middle), (end, cy)]
        };
        let link = tree.nodes[child].link.as_deref();
        let tooltip = match link {
            Some(link) => format!(
                "{} → {}: {link}",
                tree.nodes[parent].label, tree.nodes[child].label
            ),
            None => format!("{} → {}", tree.nodes[parent].label, tree.nodes[child].label),
        };
        elements.push(Element::Polyline(diagram::polyline(
            rounded(&points),
            "chartlet-flow-edge",
            Some(tooltip),
        )));
        if let Some(link) = link {
            let last = points[points.len() - 1];
            // Between the turn and the row of the child, on the line.
            let at = if self.landscape {
                (f64::midpoint(middle, child_start), last.1 + 4.5)
            } else {
                (last.0, f64::midpoint(middle, child_start) + 4.5)
            };
            labels.push((
                vec![link.to_owned()],
                at,
                focus_classes(None, &[parent.min(child), parent.max(child)]),
            ));
        }
    }
}

/// The radial layout of a mind map: the root in the middle, every level on a ring around it and
/// every subtree in a sector of its own. Positions are centers, on the page.
struct Radial {
    center: Vec<(f64, f64)>,
    width: f64,
    height: f64,
}

impl Radial {
    /// Sectors follow the leaves: every node gets the share of its parent's sector that its
    /// leaves are of its parent's, the first child from twelve o'clock clockwise, and stands in
    /// the middle of its sector. The rings are ellipses: of the proportions tried, the one that
    /// grows the canvas least, and among those that fit, the one closest to the room on the page.
    fn new(
        spec: &ChartSpec,
        tree: &TreeSpec,
        nodes: &[NodeBox],
        (top, margin, compact): (f64, f64, bool),
    ) -> Self {
        let gap = if compact {
            COMPACT_SIBLING_GAP
        } else {
            SIBLING_GAP
        };
        let angle = sector_angles(tree, nodes.len());
        let (width, height) = (f64::from(spec.width), f64::from(spec.height));
        let room = (width - 2.0 * margin) / (height - top - BOTTOM);
        let mut best: Option<Proportion> = None;
        for step in 0..=STRETCH_STEPS {
            let stretch = MIN_STRETCH + f64::from(step) * 0.1;
            let centers = rings(tree, nodes, &angle, stretch, gap);
            let bounds = (0..nodes.len()).fold(
                (
                    f64::INFINITY,
                    f64::INFINITY,
                    f64::NEG_INFINITY,
                    f64::NEG_INFINITY,
                ),
                |(low_x, low_y, high_x, high_y), node| {
                    let (x, y, w, h) = box_around(centers[node], &nodes[node]);
                    (
                        low_x.min(x),
                        low_y.min(y),
                        high_x.max(x + w),
                        high_y.max(y + h),
                    )
                },
            );
            let growth = ((2.0 * margin + bounds.2 - bounds.0) / width)
                .max((top + bounds.3 - bounds.1 + BOTTOM) / height)
                .max(1.0);
            let off = (stretch - room).abs();
            let better = best.as_ref().is_none_or(|best| {
                growth < best.growth - 1e-9 || (growth <= best.growth + 1e-9 && off < best.off)
            });
            if better {
                best = Some(Proportion {
                    growth,
                    off,
                    centers,
                    bounds,
                });
            }
        }
        let Proportion {
            centers: offsets,
            bounds: (low_x, low_y, high_x, high_y),
            ..
        } = best.expect("at least one proportion is tried");
        let page_width = width.max(2.0 * margin + high_x - low_x);
        let page_height = height.max(top + high_y - low_y + BOTTOM);
        // The drawing stands in the middle of the room the canvas leaves below the title.
        let shift = (
            margin + (page_width - 2.0 * margin - (high_x - low_x)) / 2.0 - low_x,
            top + (page_height - top - BOTTOM - (high_y - low_y)) / 2.0 - low_y,
        );
        Self {
            center: offsets
                .iter()
                .map(|(x, y)| (x + shift.0, y + shift.1))
                .collect(),
            width: page_width,
            height: page_height,
        }
    }

    fn node_box(&self, nodes: &[NodeBox], node: usize) -> (f64, f64, f64, f64) {
        box_around(self.center[node], &nodes[node])
    }

    /// A straight spoke from every parent to each of its children, from edge to edge of the
    /// boxes, under the boxes.
    fn draw(
        &self,
        (tree, style): (&TreeSpec, (NumberStyle, bool)),
        nodes: &[NodeBox],
        elements: &mut Vec<Element>,
    ) {
        for node in tree.reading_order() {
            let Some(parent) = tree.parent_of(node) else {
                continue;
            };
            let (from, to) = (self.center[parent], self.center[node]);
            elements.push(Element::Group(focus_classes(
                None,
                &[parent.min(node), parent.max(node)],
            )));
            elements.push(Element::Polyline(diagram::polyline(
                vec![
                    edge_toward(from, to, &nodes[parent]),
                    edge_toward(to, from, &nodes[node]),
                ],
                "chartlet-flow-edge",
                Some(format!(
                    "{} → {}",
                    tree.nodes[parent].label, tree.nodes[node].label
                )),
            )));
            elements.push(Element::GroupEnd);
        }
        draw_nodes(
            (tree, style),
            nodes,
            |node| self.node_box(nodes, node),
            elements,
        );
    }
}

/// How much wider than high the rings of a radial tree may be drawn: from 0.6 in steps of 0.1.
const MIN_STRETCH: f64 = 0.6;
const STRETCH_STEPS: u8 = 18;

/// The angle of every node of a radial tree, the root's 0: the middle of its sector.
fn sector_angles(tree: &TreeSpec, count_of_nodes: usize) -> Vec<f64> {
    let order = tree.reading_order();
    let mut leaves = vec![1_usize; count_of_nodes];
    for &node in order.iter().rev() {
        let children = tree.children(node);
        if !children.is_empty() {
            leaves[node] = children.iter().map(|child| leaves[*child]).sum();
        }
    }
    let mut angle = vec![0.0_f64; count_of_nodes];
    let mut sector = vec![(0.0_f64, 0.0_f64); count_of_nodes];
    sector[tree.root()] = (-FRAC_PI_2, -FRAC_PI_2 + TAU);
    for &node in &order {
        let (start, end) = sector[node];
        let mut at = start;
        for child in tree.children(node) {
            #[allow(clippy::cast_precision_loss)]
            let share = (end - start) * leaves[child] as f64 / leaves[node] as f64;
            sector[child] = (at, at + share);
            angle[child] = at + share / 2.0;
            at += share;
        }
    }
    angle
}

/// The center of every node from the root, on rings that are `stretch` times wider than high.
///
/// The rings are worked out where boxes are `stretch` times narrower, so that they are circles
/// there. A ring lies so far out that every box on it clears, by the level gap, the farthest
/// corner of any box on the ring inside it, and then further out until no two of its boxes come
/// closer than `gap`.
fn rings(
    tree: &TreeSpec,
    nodes: &[NodeBox],
    angle: &[f64],
    stretch: f64,
    gap: f64,
) -> Vec<(f64, f64)> {
    let half = |node: usize| (nodes[node].width / 2.0 / stretch, nodes[node].height / 2.0);
    // How far a box reaches out along its spoke, and across it.
    let radial = |node: usize| {
        let (w, h) = half(node);
        w * angle[node].cos().abs() + h * angle[node].sin().abs()
    };
    let tangential = |node: usize| {
        let (w, h) = half(node);
        w * angle[node].sin().abs() + h * angle[node].cos().abs()
    };
    let at_radius = |node: usize, radius: f64| {
        (
            stretch * radius * angle[node].cos(),
            radius * angle[node].sin(),
        )
    };
    let order = tree.reading_order();
    let depths: Vec<usize> = (0..nodes.len()).map(|node| tree.depth(node)).collect();
    let levels = depths.iter().copied().max().unwrap_or(0) + 1;
    let mut radius = vec![0.0_f64; nodes.len()];
    let (root_w, root_h) = half(tree.root());
    let mut outer = root_w.hypot(root_h);
    for level in 1..levels {
        let ring: Vec<usize> = order
            .iter()
            .copied()
            .filter(|node| depths[*node] == level)
            .collect();
        let mut at = outer + LEVEL_GAP + ring.iter().map(|node| radial(*node)).fold(0.0, f64::max);
        let place = |node: usize, at: f64| box_around(at_radius(node, at), &nodes[node]);
        while ring.iter().enumerate().any(|(index, a)| {
            ring[index + 1..]
                .iter()
                .any(|b| !apart(place(*a, at), place(*b, at), gap))
        }) {
            at += (at * 0.03).max(2.0);
        }
        for &node in &ring {
            radius[node] = at;
        }
        outer = ring
            .iter()
            .map(|node| (at + radial(*node)).hypot(tangential(*node)))
            .fold(0.0, f64::max);
    }
    (0..nodes.len())
        .map(|node| at_radius(node, radius[node]))
        .collect()
}

/// One proportion of the rings of a radial tree: how much it grows the canvas, how far it is
/// from the proportion of the room, the centers of the nodes from the root, and their bounds:
/// left, top, right and bottom.
struct Proportion {
    growth: f64,
    off: f64,
    centers: Vec<(f64, f64)>,
    bounds: (f64, f64, f64, f64),
}

/// The box of a node whose center is at `(x, y)`: left, top, width and height.
fn box_around((x, y): (f64, f64), node: &NodeBox) -> (f64, f64, f64, f64) {
    (
        x - node.width / 2.0,
        y - node.height / 2.0,
        node.width,
        node.height,
    )
}

/// Whether two boxes keep at least `gap` between them, across or along.
fn apart(a: (f64, f64, f64, f64), b: (f64, f64, f64, f64), gap: f64) -> bool {
    a.0 + a.2 + gap <= b.0
        || b.0 + b.2 + gap <= a.0
        || a.1 + a.3 + gap <= b.1
        || b.1 + b.3 + gap <= a.1
}

/// Where the line from the center `from` of a box toward `to` leaves the box.
fn edge_toward(from: (f64, f64), to: (f64, f64), node: &NodeBox) -> (f64, f64) {
    let (dx, dy) = (to.0 - from.0, to.1 - from.1);
    let reach = (node.width / 2.0 / dx.abs()).min(node.height / 2.0 / dy.abs());
    (from.0 + dx * reach, from.1 + dy * reach)
}

/// Every node: its shape, its text, and the hotspot the HTML profile focuses; `node_box` says
/// where each one stands.
fn draw_nodes(
    (tree, style): (&TreeSpec, (NumberStyle, bool)),
    nodes: &[NodeBox],
    node_box: impl Fn(usize) -> (f64, f64, f64, f64),
    elements: &mut Vec<Element>,
) {
    let related = |node: usize| {
        let mut related: Vec<usize> = tree
            .children(node)
            .into_iter()
            .chain(tree.parent_of(node))
            .chain(std::iter::once(node))
            .collect();
        related.sort_unstable();
        related
    };
    let (style, tags) = style;
    let heat = heat::steps(&tree.nodes.iter().map(|node| node.value).collect::<Vec<_>>());
    let names = parts::names(tree.nodes.iter().map(|node| node.parts.as_slice()));
    for (node, drawn) in nodes.iter().enumerate() {
        let spec = &tree.nodes[node];
        let mut classes = focus_classes(Some(node), &related(node));
        if let Some(step) = heat[node] {
            classes.push_str(&heat::class(step));
        }
        if let Some(role) = spec.role {
            classes.push_str(roles::class(role));
        }
        elements.push(Element::NodeGroup(classes, spec.id.clone()));
        let (x, y, width, height) = node_box(node);
        let tooltip = Some(match &spec.sublabel {
            Some(sublabel) => format!("{} – {sublabel}", spec.label),
            None => spec.label.clone(),
        });
        let kind = match spec.kind {
            TreeNodeKind::Unit => Shape::Process,
            TreeNodeKind::Person => Shape::Person,
            TreeNodeKind::External => Shape::External,
        };
        shape(kind, (x, y, width, height), tooltip, elements);
        if tags
            && let Some(tag) = match spec.kind {
                TreeNodeKind::Unit => None,
                TreeNodeKind::Person => Some("USER"),
                TreeNodeKind::External => Some("EXT"),
            }
        {
            crate::flow::push_tag(tag, (x, y), elements);
        }
        let stripe = if spec.parts.is_empty() {
            0.0
        } else {
            parts::ROOM
        };
        // The text stands in the middle of the room the stripe leaves.
        node_text(
            drawn,
            spec.kind == TreeNodeKind::Person,
            (x, y, width, height - stripe),
            elements,
        );
        if !spec.parts.is_empty() {
            parts::push_stripe(
                style,
                (&spec.parts, &names),
                (x, y, width, height),
                0.0,
                elements,
            );
        }
        if let Some(role) = spec.role {
            roles::push_badge(role, (x, y), elements);
        }
        elements.push(Element::GroupEnd);
        elements.push(Element::Hotspot(Hotspot {
            node,
            label: spec.label.clone(),
            x,
            y,
            width,
            height,
        }));
    }
}

/// A node's label, centered on one or two lines, and its sublabel below.
fn node_text(
    node: &NodeBox,
    person: bool,
    (x, y, width, height): (f64, f64, f64, f64),
    elements: &mut Vec<Element>,
) {
    let (middle_x, middle_y) = (x + width / 2.0, y + height / 2.0);
    let block =
        NODE_LINE * count(node.lines.len() - 1) + SUBLABEL_LINE * count(node.sublines.len());
    // The text clears the head of a person.
    let first = middle_y - block / 2.0 + 4.5 + if person { 8.0 } else { 0.0 };
    for (index, line) in node.lines.iter().enumerate() {
        elements.push(Element::Text(Text {
            x: middle_x,
            y: first + NODE_LINE * count(index),
            class: "chartlet-flow-label",
            anchor: TextAnchor::Middle,
            content: line.clone(),
        }));
    }
    for (index, line) in node.sublines.iter().enumerate() {
        elements.push(Element::Text(Text {
            x: middle_x,
            y: first + NODE_LINE * count(node.lines.len() - 1) + SUBLABEL_LINE * count(index + 1),
            class: "chartlet-flow-sublabel",
            anchor: TextAnchor::Middle,
            content: line.clone(),
        }));
    }
}

/// A node named with its sublabel and link in a parenthesis: `Holding GmbH (holding, 60 %)`; a
/// couple names both of its partners.
fn mention(tree: &TreeSpec, node: usize) -> String {
    let named = |node: usize, with_link: bool| {
        let spec = &tree.nodes[node];
        let notes: Vec<&str> = [
            spec.sublabel.as_deref(),
            spec.link.as_deref().filter(|_| with_link),
        ]
        .into_iter()
        .flatten()
        .collect();
        if notes.is_empty() {
            spec.label.clone()
        } else {
            format!("{} ({})", spec.label, notes.join(", "))
        }
    };
    match tree.partner_of(node) {
        Some(partner) => format!("{} + {}", named(node, true), named(partner, false)),
        None => named(node, true),
    }
}

/// The tree in sentences: its size, its root, and what hangs below every node that has anything
/// below it, in reading order.
pub(crate) fn description(spec: &ChartSpec) -> String {
    if tree(spec).distances.is_some() {
        return crate::dendrogram::description(spec);
    }
    let tree = tree(spec);
    let locale = spec.locale;
    let levels = (0..tree.nodes.len())
        .map(|node| tree.depth(node))
        .max()
        .unwrap_or(0)
        + 1;
    let radial = tree.layout == TreeLayout::Radial;
    let mut description = text::tree_opening(locale, tree.nodes.len(), levels, radial);
    description.push(' ');
    description.push_str(&text::tree_root(
        locale,
        &mention(tree, tree.root()),
        radial,
    ));
    for node in tree.reading_order() {
        let children: Vec<String> = tree
            .children(node)
            .into_iter()
            .map(|child| mention(tree, child))
            .collect();
        if !children.is_empty() {
            let name = tree.partner_of(node).map_or_else(
                || tree.nodes[node].label.clone(),
                |partner| format!("{} + {}", tree.nodes[node].label, tree.nodes[partner].label),
            );
            write!(description, " {name}: {}.", children.join(", "))
                .expect("writing to String cannot fail");
        }
    }
    let valued: Vec<(&str, f64)> = tree
        .reading_order()
        .into_iter()
        .filter_map(|node| {
            let spec_node = &tree.nodes[node];
            spec_node
                .value
                .map(|value| (spec_node.label.as_str(), value))
        })
        .collect();
    if !valued.is_empty() {
        description.push(' ');
        description.push_str(&heat::sentence(
            spec,
            &heat::name(spec, tree.value_label.as_deref()),
            &valued,
        ));
    }
    let with_parts: Vec<(&str, &[PartSpec])> = tree
        .reading_order()
        .into_iter()
        .map(|node| &tree.nodes[node])
        .filter(|node| !node.parts.is_empty())
        .map(|node| (node.label.as_str(), node.parts.as_slice()))
        .collect();
    if !with_parts.is_empty() {
        description.push(' ');
        description.push_str(&parts::sentence(spec, &with_parts));
    }
    let collapsed: Vec<&str> = (0..tree.nodes.len())
        .filter(|node| tree.hidden_below(*node) > 0)
        .map(|node| tree.nodes[node].label.as_str())
        .collect();
    if !collapsed.is_empty() {
        description.push(' ');
        description.push_str(&text::tree_collapsed(locale, &collapsed));
    }
    let with_roles: Vec<(DiagramRole, String)> = tree
        .reading_order()
        .into_iter()
        .filter_map(|node| {
            let spec_node = &tree.nodes[node];
            spec_node.role.map(|role| (role, spec_node.label.clone()))
        })
        .collect();
    if let Some(sentence) = roles::sentence(locale, &with_roles) {
        description.push(' ');
        description.push_str(&sentence);
    }
    description
}

/// One row per node in reading order: its label, level, parent, link and children.
pub(crate) fn data_table(spec: &ChartSpec) -> DataTable {
    if tree(spec).distances.is_some() {
        return crate::dendrogram::data_table(spec);
    }
    let tree = tree(spec);
    let words = spec.locale.words();
    let linked = tree.nodes.iter().any(|node| node.link.is_some());
    let coupled = tree.nodes.iter().any(|node| node.partner.is_some());
    let mut columns = vec![
        words.node.to_owned(),
        words.level.to_owned(),
        words.parent.to_owned(),
    ];
    if coupled {
        columns.push(words.partner.to_owned());
    }
    if linked {
        columns.push(words.link.to_owned());
    }
    let values = tree.nodes.iter().any(|node| node.value.is_some());
    if values {
        columns.push(heat::name(spec, tree.value_label.as_deref()));
    }
    let with_parts = tree.nodes.iter().any(|node| !node.parts.is_empty());
    if with_parts {
        columns.push(words.parts.to_owned());
    }
    let with_roles = tree.nodes.iter().any(|node| node.role.is_some());
    if with_roles {
        columns.push(words.role.to_owned());
    }
    columns.push(words.children.to_owned());
    let folded = tree.nodes.iter().any(|node| node.collapsed);
    if folded {
        columns.push(words.collapsed.to_owned());
    }
    let rows = tree
        .reading_order()
        .into_iter()
        .map(|node| {
            let mut row = vec![
                tree.nodes[node].label.clone(),
                (tree.depth(node) + 1).to_string(),
                tree.parent_of(node)
                    .map_or_else(String::new, |parent| tree.nodes[parent].label.clone()),
            ];
            if coupled {
                row.push(
                    tree.partner_of(node)
                        .or_else(|| tree.head_of(node))
                        .map_or_else(String::new, |other| tree.nodes[other].label.clone()),
                );
            }
            if linked {
                row.push(tree.nodes[node].link.clone().unwrap_or_default());
            }
            if values {
                row.push(tree.nodes[node].value.map_or_else(String::new, |value| {
                    format_value(value, spec.number_style())
                }));
            }
            if with_parts {
                row.push(parts::listed(spec.number_style(), &tree.nodes[node].parts));
            }
            if with_roles {
                row.push(
                    tree.nodes[node]
                        .role
                        .map_or_else(String::new, |role| text::role(spec.locale, role).to_owned()),
                );
            }
            row.push(
                tree.children(node)
                    .into_iter()
                    .map(|child| tree.nodes[child].label.as_str())
                    .collect::<Vec<_>>()
                    .join(", "),
            );
            if folded {
                let hidden = tree.hidden_below(node);
                row.push(if hidden > 0 {
                    format!("+{hidden}")
                } else {
                    String::new()
                });
            }
            row
        })
        .collect();
    DataTable {
        caption: format!("{} {}", words.data_for, spec.title),
        columns,
        rows,
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        BuiltinMetrics, ChartSpec, RenderFormat, RenderOptions, render_json, text_alternative,
    };

    use super::{Plan, Radial, apart, boxes, tree};

    const SPEC: &str = r#"{
        "schemaVersion": 1,
        "type": "tree",
        "title": "Company",
        "width": 900,
        "height": 500,
        "tree": {
            "nodes": [
                {"id": "ceo", "label": "Chief executive", "sublabel": "board"},
                {"id": "tech", "label": "Technology", "parent": "ceo", "link": "reports"},
                {"id": "ops", "label": "Operations", "parent": "ceo"},
                {"id": "platform", "label": "Platform", "parent": "tech"},
                {"id": "apps", "label": "Applications", "parent": "tech"},
                {"id": "web", "label": "Web", "parent": "apps"},
                {"id": "mobile", "label": "Mobile", "parent": "apps"},
                {"id": "support", "label": "Support", "parent": "ops"}
            ]
        }
    }"#;

    fn svg(json: &str) -> crate::RenderOutput {
        render_json(json, RenderFormat::Svg, &RenderOptions::default())
            .expect("the test specification renders")
    }

    fn error(json: &str) -> (&'static str, String) {
        let error = render_json(json, RenderFormat::Svg, &RenderOptions::default())
            .expect_err("the test specification is invalid");
        (error.code, error.path)
    }

    fn plan(json: &str, landscape: bool) -> (Plan, Vec<(f64, f64, f64, f64)>) {
        let spec: ChartSpec = serde_json::from_str(json).expect("a specification");
        let tree = tree(&spec);
        let nodes = boxes(tree, false, &BuiltinMetrics, &mut Vec::new());
        let plan = Plan::new(&spec, tree, &nodes, landscape, (56.0, 24.0, false));
        let rectangles = (0..nodes.len())
            .map(|node| plan.node_box(&nodes, node))
            .collect();
        (plan, rectangles)
    }

    #[test]
    fn no_two_nodes_overlap_in_either_orientation() {
        for landscape in [false, true] {
            let (_, boxes) = plan(SPEC, landscape);
            for (index, a) in boxes.iter().enumerate() {
                for b in &boxes[index + 1..] {
                    let apart = a.0 + a.2 <= b.0
                        || b.0 + b.2 <= a.0
                        || a.1 + a.3 <= b.1
                        || b.1 + b.3 <= a.1;
                    assert!(apart, "{a:?} overlaps {b:?} (landscape: {landscape})");
                }
            }
        }
    }

    #[test]
    fn a_parent_stands_over_the_middle_of_its_children() {
        let (plan, _) = plan(SPEC, false);
        // ids by position: tech (1) has platform (3) and apps (4); apps has web (5) and mobile (6).
        for (parent, first, last) in [(1, 3, 4), (4, 5, 6)] {
            let middle = f64::midpoint(plan.center[first].0, plan.center[last].0);
            assert!((plan.center[parent].0 - middle).abs() < 0.01, "{parent}");
        }
    }

    #[test]
    fn a_narrow_subtree_tucks_in_under_a_broad_neighbour() {
        // `ops` has one child; its subtree may stand closer than the width of the whole of
        // `tech`'s subtree.
        let (plan, _) = plan(SPEC, false);
        assert!(plan.center[2].0 - plan.center[1].0 < 4.0 * 190.0);
        assert!(plan.center[7].1 > plan.center[2].1);
    }

    #[test]
    fn a_tree_renders_without_warnings_and_twice_to_the_same_bytes() {
        let first = svg(SPEC);
        assert!(first.warnings.is_empty(), "{:?}", first.warnings);
        assert_eq!(first.content, svg(SPEC).content);
        assert!(first.content.contains(">Chief executive</text>"));
        assert!(first.content.contains(">reports</text>"));
    }

    #[test]
    fn the_text_alternative_names_the_root_and_what_hangs_below_every_node() {
        let alternative =
            text_alternative(&ChartSpec::from_json(SPEC).expect("parses")).expect("valid");
        let description = alternative.description;
        assert!(
            description
                .starts_with("Tree with 8 nodes in 4 levels. Root: Chief executive (board).")
        );
        assert!(description.contains("Chief executive: Technology (reports), Operations."));
        assert!(description.contains("Applications: Web, Mobile."));
    }

    #[test]
    fn the_html_table_lists_every_node_with_level_and_parent() {
        let html = render_json(SPEC, RenderFormat::Html, &RenderOptions::default())
            .expect("renders")
            .content;
        for needle in [">Level<", ">Parent<", ">Link<", "Platform"] {
            assert!(html.contains(needle), "{needle}");
        }
    }

    #[test]
    fn german_writes_the_description_and_the_table_in_german() {
        let json = SPEC.replace(
            "\"title\": \"Company\",",
            "\"title\": \"Firma\", \"locale\": \"de\",",
        );
        let alternative =
            text_alternative(&ChartSpec::from_json(&json).expect("parses")).expect("valid");
        assert!(
            alternative
                .description
                .starts_with("Baum mit 8 Knoten in 4 Ebenen. Wurzel:")
        );
        let html = render_json(&json, RenderFormat::Html, &RenderOptions::default())
            .expect("renders")
            .content;
        assert!(html.contains(">Knoten<") && html.contains(">Übergeordnet<"));
    }

    #[test]
    fn invalid_trees_name_the_field() {
        for (from, to, code, path) in [
            (
                r#""id": "ops", "label": "Operations", "parent": "ceo""#,
                r#""id": "ops", "label": "Operations""#,
                "invalid_root",
                "/tree/nodes/2",
            ),
            (
                r#""id": "web", "label": "Web", "parent": "apps""#,
                r#""id": "web", "label": "Web", "parent": "nowhere""#,
                "unknown_node",
                "/tree/nodes/5/parent",
            ),
            (
                r#""id": "ops""#,
                r#""id": "tech""#,
                "duplicate_id",
                "/tree/nodes/2/id",
            ),
            (
                r#""id": "ceo", "label": "Chief executive", "sublabel": "board""#,
                r#""id": "ceo", "label": "Chief executive", "link": "100 %""#,
                "option_not_supported",
                "/tree/nodes/0/link",
            ),
            (
                r#""id": "ceo", "label": "Chief executive", "sublabel": "board""#,
                r#""id": "ceo", "label": "Chief executive", "parent": "web""#,
                "invalid_root",
                "/tree/nodes",
            ),
        ] {
            let (got_code, got_path) = error(&SPEC.replace(from, to));
            assert_eq!((got_code, got_path.as_str()), (code, path), "{from}");
        }
    }

    #[test]
    fn a_circle_of_parents_and_a_missing_block_are_refused() {
        let circle = r#"{"schemaVersion": 1, "type": "tree", "title": "Loop", "width": 600, "height": 300,
            "tree": {"nodes": [
                {"id": "a", "label": "A"},
                {"id": "b", "label": "B", "parent": "c"},
                {"id": "c", "label": "C", "parent": "b"}
            ]}}"#;
        assert_eq!(
            error(circle),
            ("circular_parent", "/tree/nodes/1/parent".to_owned())
        );
        let missing =
            r#"{"schemaVersion": 1, "type": "tree", "title": "None", "width": 600, "height": 300}"#;
        assert_eq!(error(missing), ("missing_tree", "/tree".to_owned()));
    }

    const COUPLES: &str = r#"{
        "schemaVersion": 1,
        "type": "tree",
        "title": "Family",
        "width": 900,
        "height": 500,
        "tree": {
            "nodes": [
                {"id": "a", "label": "Ana", "kind": "person"},
                {"id": "t", "label": "Tomas", "kind": "person", "partner": "a"},
                {"id": "l", "label": "Lena", "kind": "person", "parent": "a"},
                {"id": "m", "label": "Marc", "kind": "person", "partner": "l"},
                {"id": "p", "label": "Paul", "kind": "person", "parent": "t"},
                {"id": "s", "label": "Sofia", "parent": "l"},
                {"id": "f", "label": "Foundation", "kind": "external", "parent": "p"}
            ]
        }
    }"#;

    #[test]
    fn a_couple_stands_side_by_side_and_its_children_hang_from_the_middle() {
        for landscape in [false, true] {
            let (plan, boxes) = plan(COUPLES, landscape);
            // ids by position: a 0, t 1, l 2, m 3, p 4, s 5, f 6. Ana and Tomas share a row.
            let (a, t) = (boxes[0], boxes[1]);
            if landscape {
                assert!((a.0 - t.0).abs() < 0.01 && t.1 > a.1 + a.3);
            } else {
                assert!((a.1 - t.1).abs() < 0.01 && t.0 > a.0 + a.2);
            }
            // Lena (a child of Ana) and Paul (a child of Tomas) are both below the couple, and
            // Sofia is below Lena and Marc.
            let level = |node: usize| {
                if landscape {
                    plan.center[node].0
                } else {
                    plan.center[node].1
                }
            };
            assert!(level(2) > level(0) && (level(2) - level(4)).abs() < 0.01);
            assert!(level(5) > level(2) && (level(3) - level(2)).abs() < 0.01);
        }
    }

    #[test]
    fn couples_and_kinds_are_drawn_and_described() {
        let output = svg(COUPLES);
        assert!(output.warnings.is_empty(), "{:?}", output.warnings);
        assert!(output.content.contains("chartlet-arch-head"));
        assert!(output.content.contains("chartlet-flow-external"));
        let alternative =
            text_alternative(&ChartSpec::from_json(COUPLES).expect("parses")).expect("valid");
        assert!(alternative.description.contains("Root: Ana + Tomas."));
        assert!(
            alternative
                .description
                .contains("Ana + Tomas: Lena + Marc, Paul.")
        );
        assert_eq!(alternative.table.columns[3], "Partner");
    }

    #[test]
    fn invalid_partners_name_the_field() {
        for (from, to, code, path) in [
            (
                r#""partner": "a""#,
                r#""partner": "nobody""#,
                "unknown_node",
                "/tree/nodes/1/partner",
            ),
            (
                r#""partner": "a""#,
                r#""partner": "t""#,
                "invalid_partner",
                "/tree/nodes/1/partner",
            ),
            (
                r#""partner": "l""#,
                r#""partner": "t""#,
                "invalid_partner",
                "/tree/nodes/3/partner",
            ),
            (
                r#""kind": "person", "partner": "a""#,
                r#""kind": "person", "parent": "a", "partner": "a""#,
                "invalid_partner",
                "/tree/nodes/1/partner",
            ),
        ] {
            let (got_code, got_path) = error(&COUPLES.replace(from, to));
            assert_eq!((got_code, got_path.as_str()), (code, path), "{from}");
        }
    }

    #[test]
    fn a_broad_tree_of_long_names_keeps_its_nodes_apart_and_its_text() {
        let mut nodes =
            vec![r#"{"id": "root", "label": "Root of the whole organization"}"#.to_owned()];
        for branch in 0..9 {
            nodes.push(format!(
                r#"{{"id": "b{branch}", "label": "Branch number {branch} of the organization", "parent": "root"}}"#
            ));
            for leaf in 0..14 {
                nodes.push(format!(
                    r#"{{"id": "l{branch}x{leaf}", "label": "Team {leaf} of branch {branch}", "sublabel": "responsible for something long", "parent": "b{branch}"}}"#
                ));
            }
        }
        let json = format!(
            r#"{{"schemaVersion": 1, "type": "tree", "title": "Big", "width": 800, "height": 400, "tree": {{"nodes": [{}]}}}}"#,
            nodes.join(",")
        );
        assert_eq!(nodes.len(), 136);
        for landscape in [false, true] {
            let (_, boxes) = plan(&json, landscape);
            for (index, a) in boxes.iter().enumerate() {
                for b in &boxes[index + 1..] {
                    let apart = a.0 + a.2 <= b.0
                        || b.0 + b.2 <= a.0
                        || a.1 + a.3 <= b.1
                        || b.1 + b.3 <= a.1;
                    assert!(apart, "{a:?} overlaps {b:?}");
                }
            }
        }
        let output = svg(&json);
        assert!(
            output
                .warnings
                .iter()
                .all(|warning| warning.code != "text_truncated"),
            "{:?}",
            output.warnings
        );
    }

    const MIND_MAP: &str = r#"{
        "schemaVersion": 1,
        "type": "tree",
        "title": "Strategy",
        "width": 940,
        "height": 560,
        "tree": {
            "layout": "radial",
            "nodes": [
                {"id": "core", "label": "Platform", "sublabel": "2026"},
                {"id": "ux", "label": "Experience", "parent": "core"},
                {"id": "data", "label": "Data", "parent": "core"},
                {"id": "ops", "label": "Operations", "parent": "core"},
                {"id": "ds", "label": "Design system", "parent": "ux"},
                {"id": "mobile", "label": "Mobile first", "parent": "ux"},
                {"id": "a11y", "label": "Accessibility", "parent": "ux"},
                {"id": "tracking", "label": "Tracking", "parent": "data"},
                {"id": "deploy", "label": "Deployment", "parent": "ops", "kind": "external"},
                {"id": "canary", "label": "Canary releases", "parent": "deploy"}
            ]
        }
    }"#;

    fn radial(json: &str) -> (Radial, Vec<(f64, f64, f64, f64)>) {
        let spec: ChartSpec = serde_json::from_str(json).expect("a specification");
        let tree = tree(&spec);
        let nodes = boxes(tree, false, &BuiltinMetrics, &mut Vec::new());
        let radial = Radial::new(&spec, tree, &nodes, (56.0, 24.0, false));
        let rectangles = (0..nodes.len())
            .map(|node| radial.node_box(&nodes, node))
            .collect();
        (radial, rectangles)
    }

    #[test]
    fn a_radial_tree_keeps_its_boxes_apart_and_runs_clockwise_from_twelve() {
        let (plan, boxes) = radial(MIND_MAP);
        for (index, a) in boxes.iter().enumerate() {
            for b in &boxes[index + 1..] {
                assert!(apart(*a, *b, 0.0), "{a:?} overlaps {b:?}");
            }
        }
        let root = plan.center[0];
        // The branches run clockwise from twelve o'clock, each in the middle of a sector as wide
        // as its share of the leaves: Experience (three of five) to the right, Data and
        // Operations (one each) after it.
        let clock = |node: usize| {
            let (dx, dy) = (plan.center[node].0 - root.0, plan.center[node].1 - root.1);
            (dy.atan2(dx) + std::f64::consts::FRAC_PI_2).rem_euclid(std::f64::consts::TAU)
        };
        assert!(
            (clock(1).to_degrees() - 108.0).abs() < 25.0,
            "{}",
            clock(1).to_degrees()
        );
        assert!(clock(1) < clock(2) && clock(2) < clock(3));
    }

    #[test]
    fn a_broad_radial_tree_keeps_its_boxes_apart_and_fits_the_size_it_asks_for() {
        let mut nodes = vec![r#"{"id": "root", "label": "Root of it all"}"#.to_owned()];
        for branch in 0..6 {
            nodes.push(format!(
                r#"{{"id": "b{branch}", "label": "Branch {branch}", "parent": "root"}}"#
            ));
            for leaf in 0..branch + 2 {
                nodes.push(format!(
                    r#"{{"id": "l{branch}x{leaf}", "label": "Leaf {leaf}.{branch}", "parent": "b{branch}"}}"#
                ));
            }
        }
        let json = format!(
            r#"{{"schemaVersion": 1, "type": "tree", "title": "Big", "width": 800, "height": 450, "tree": {{"layout": "radial", "nodes": [{}]}}}}"#,
            nodes.join(",")
        );
        let (_, boxes) = radial(&json);
        for (index, a) in boxes.iter().enumerate() {
            for b in &boxes[index + 1..] {
                assert!(apart(*a, *b, 0.0), "{a:?} overlaps {b:?}");
            }
        }
        // The canvas grows and says by how much; at that size the tree fits without a warning.
        let output = svg(&json);
        let needed = |path: &str| {
            output
                .warnings
                .iter()
                .find(|warning| warning.code == "canvas_too_small" && warning.path == path)
                .map(|warning| {
                    assert!(warning.message.ends_with("or use the layered layout"));
                    warning
                        .message
                        .split(' ')
                        .nth(3)
                        .expect("a size")
                        .to_owned()
                })
        };
        let (width, height) = (needed("/width"), needed("/height"));
        assert!(width.is_some() || height.is_some(), "{:?}", output.warnings);
        let mut resized = json.clone();
        if let Some(width) = width {
            resized = resized.replace(r#""width": 800"#, &format!(r#""width": {width}"#));
        }
        if let Some(height) = height {
            resized = resized.replace(r#""height": 450"#, &format!(r#""height": {height}"#));
        }
        let output = svg(&resized);
        assert!(output.warnings.is_empty(), "{:?}", output.warnings);
    }

    #[test]
    fn a_radial_tree_says_it_is_a_mind_map_in_both_languages() {
        let output = svg(MIND_MAP);
        assert!(output.warnings.is_empty(), "{:?}", output.warnings);
        assert_eq!(output.content, svg(MIND_MAP).content);
        assert!(output.content.contains(">Canary releases</text>"));
        let alternative =
            text_alternative(&ChartSpec::from_json(MIND_MAP).expect("parses")).expect("valid");
        assert!(
            alternative.description.starts_with(
                "Mind map (radial tree) with 10 nodes in 4 levels. Centre: Platform (2026). Platform: Experience, Data, Operations."
            ),
            "{}",
            alternative.description
        );
        let german = MIND_MAP.replace(
            r#""title": "Strategy","#,
            r#""title": "Strategie", "locale": "de","#,
        );
        let alternative =
            text_alternative(&ChartSpec::from_json(&german).expect("parses")).expect("valid");
        assert!(
            alternative.description.starts_with(
                "Mindmap (radialer Baum) mit 10 Knoten in 4 Ebenen. Mitte: Platform (2026)."
            ),
            "{}",
            alternative.description
        );
    }

    #[test]
    fn a_radial_tree_draws_a_collapsed_node_without_what_hangs_below() {
        let json = MIND_MAP.replace(
            r#""label": "Experience", "parent": "core""#,
            r#""label": "Experience", "parent": "core", "collapsed": true"#,
        );
        let output = svg(&json);
        assert!(output.warnings.is_empty(), "{:?}", output.warnings);
        assert!(output.content.contains(">+3</text>"));
        assert!(!output.content.contains(">Mobile first</text>"));
    }

    #[test]
    fn a_radial_tree_refuses_what_it_cannot_draw() {
        for (from, to, path) in [
            (
                r#""layout": "radial","#,
                r#""layout": "radial", "orientation": "landscape","#,
                "/tree/orientation",
            ),
            (
                r#""label": "Tracking", "parent": "data""#,
                r#""label": "Tracking", "parent": "data", "link": "weekly""#,
                "/tree/nodes/7/link",
            ),
            (
                r#""label": "Tracking", "parent": "data""#,
                r#""label": "Tracking", "partner": "data""#,
                "/tree/nodes/7/partner",
            ),
        ] {
            let json = MIND_MAP.replace(from, to);
            assert_eq!(
                error(&json),
                ("option_not_supported", path.to_owned()),
                "{to}"
            );
        }
    }

    #[test]
    fn nodes_take_roles_with_a_badge_a_legend_and_a_column() {
        let json = SPEC
            .replace(
                r#"{"id": "ops", "label": "Operations", "parent": "ceo"}"#,
                r#"{"id": "ops", "label": "Operations", "parent": "ceo", "role": "deprecated"}"#,
            )
            .replace(
                r#"{"id": "mobile", "label": "Mobile", "parent": "apps"}"#,
                r#"{"id": "mobile", "label": "Mobile", "parent": "apps", "role": "planned"}"#,
            );
        let output = svg(&json);
        assert!(output.warnings.is_empty(), "{:?}", output.warnings);
        assert!(output.content.contains(" chartlet-flow-role-deprecated\">"));
        assert!(output.content.contains(">+</text>"));
        assert!(output.content.contains(">−</text>"));
        assert!(output.content.contains(">Planned</text>"));
        assert!(output.content.contains(">Deprecated</text>"));
        let alternative =
            text_alternative(&ChartSpec::from_json(&json).expect("parses")).expect("valid");
        assert!(
            alternative
                .description
                .ends_with("Roles: planned: Mobile; deprecated: Operations."),
            "{}",
            alternative.description
        );
        let role = alternative
            .table
            .columns
            .iter()
            .position(|column| column == "Role")
            .expect("a role column");
        let ops = alternative
            .table
            .rows
            .iter()
            .find(|row| row[0] == "Operations")
            .expect("a row");
        assert_eq!(ops[role], "deprecated");
        let german = json.replace(
            "\"schemaVersion\": 1,",
            "\"schemaVersion\": 1, \"locale\": \"de\",",
        );
        let alternative =
            text_alternative(&ChartSpec::from_json(&german).expect("parses")).expect("valid");
        assert!(
            alternative
                .description
                .ends_with("Rollen: geplant: Mobile; veraltet: Operations."),
            "{}",
            alternative.description
        );
        assert!(alternative.table.columns.contains(&"Rolle".to_owned()));
    }
}