merman_render/flowchart/

layout.rs

use crate::config::config_f64;
use crate::math::MathRenderer;
use crate::model::{
    FlowchartV2Layout, LayoutCluster, LayoutEdge, LayoutLabel, LayoutNode, LayoutPoint,
};
use crate::text::{TextMeasurer, TextStyle, WrapMode};
use crate::{Error, Result};
use dugong::graphlib::{Graph, GraphOptions};
use dugong::{EdgeLabel, GraphLabel, LabelPos, NodeLabel, RankDir};
use merman_core::MermaidConfig;
use serde_json::Value;
use std::collections::{HashMap, HashSet};

use super::label::compute_bounds;
use super::node::{NodeLayoutDimensionsRequest, node_layout_dimensions};
use super::{FlowEdge, FlowSubgraph, FlowchartV2Model};
use super::{
    FlowchartLabelMetricsRequest, flowchart_effective_html_labels,
    flowchart_effective_node_html_labels, flowchart_effective_text_style_for_classes,
    flowchart_effective_text_style_for_node_classes, flowchart_html_label_measurement_base_style,
    flowchart_label_metrics_for_layout, flowchart_node_has_span_css_height_parity,
};

fn config_string(cfg: &Value, path: &[&str]) -> Option<String> {
    let mut cur = cfg;
    for key in path {
        cur = cur.get(*key)?;
    }
    cur.as_str().map(|s| s.to_string())
}

fn flowchart_svg_plain_computed_width_px(
    measurer: &dyn TextMeasurer,
    plain: &str,
    style: &TextStyle,
    max_width_px: Option<f64>,
) -> f64 {
    let wrapped_lines =
        crate::text::wrap_svg_text_lines_by_measurement(measurer, plain, style, max_width_px, true);
    let mut width: f64 = 0.0;
    for line in wrapped_lines {
        width = width.max(measurer.measure_svg_text_computed_length_px(line.trim_end(), style));
    }
    crate::text::round_to_1_64_px(width)
}

fn rank_dir_from_flow(direction: &str) -> RankDir {
    match direction.trim().to_uppercase().as_str() {
        "TB" | "TD" => RankDir::TB,
        "BT" => RankDir::BT,
        "LR" => RankDir::LR,
        "RL" => RankDir::RL,
        _ => RankDir::TB,
    }
}

fn normalize_dir(s: &str) -> String {
    s.trim().to_uppercase()
}

fn toggled_dir(parent: &str) -> String {
    let parent = normalize_dir(parent);
    if parent == "TB" || parent == "TD" {
        "LR".to_string()
    } else {
        "TB".to_string()
    }
}

fn flow_dir_from_rankdir(rankdir: RankDir) -> &'static str {
    match rankdir {
        RankDir::TB => "TB",
        RankDir::BT => "BT",
        RankDir::LR => "LR",
        RankDir::RL => "RL",
    }
}

fn effective_cluster_dir(sg: &FlowSubgraph, parent_dir: &str, inherit_dir: bool) -> String {
    if let Some(dir) = sg.dir.as_deref().map(str::trim).filter(|s| !s.is_empty()) {
        return normalize_dir(dir);
    }
    if inherit_dir {
        return normalize_dir(parent_dir);
    }
    toggled_dir(parent_dir)
}

fn compute_effective_dir_by_id(
    subgraphs_by_id: &HashMap<String, FlowSubgraph>,
    g: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
    diagram_dir: &str,
    inherit_dir: bool,
) -> HashMap<String, String> {
    fn compute_one(
        id: &str,
        subgraphs_by_id: &HashMap<String, FlowSubgraph>,
        g: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
        diagram_dir: &str,
        inherit_dir: bool,
        visiting: &mut std::collections::HashSet<String>,
        memo: &mut HashMap<String, String>,
    ) -> String {
        if let Some(dir) = memo.get(id) {
            return dir.clone();
        }
        if !visiting.insert(id.to_string()) {
            let dir = toggled_dir(diagram_dir);
            memo.insert(id.to_string(), dir.clone());
            return dir;
        }

        let parent_dir = g
            .parent(id)
            .and_then(|p| subgraphs_by_id.contains_key(p).then_some(p.to_string()))
            .map(|p| {
                compute_one(
                    &p,
                    subgraphs_by_id,
                    g,
                    diagram_dir,
                    inherit_dir,
                    visiting,
                    memo,
                )
            })
            .unwrap_or_else(|| normalize_dir(diagram_dir));

        let dir = subgraphs_by_id
            .get(id)
            .map(|sg| effective_cluster_dir(sg, &parent_dir, inherit_dir))
            .unwrap_or_else(|| toggled_dir(&parent_dir));

        memo.insert(id.to_string(), dir.clone());
        let _ = visiting.remove(id);
        dir
    }

    let mut memo: HashMap<String, String> = HashMap::new();
    let mut visiting: std::collections::HashSet<String> = std::collections::HashSet::new();
    for id in subgraphs_by_id.keys() {
        let _ = compute_one(
            id,
            subgraphs_by_id,
            g,
            diagram_dir,
            inherit_dir,
            &mut visiting,
            &mut memo,
        );
    }
    memo
}

fn dir_to_rankdir(dir: &str) -> RankDir {
    match normalize_dir(dir).as_str() {
        "TB" | "TD" => RankDir::TB,
        "BT" => RankDir::BT,
        "LR" => RankDir::LR,
        "RL" => RankDir::RL,
        _ => RankDir::TB,
    }
}

fn edge_label_is_non_empty(edge: &FlowEdge) -> bool {
    edge.label
        .as_deref()
        .map(|s| !s.trim().is_empty())
        .unwrap_or(false)
}

fn lowest_common_parent(
    g: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
    a: &str,
    b: &str,
) -> Option<String> {
    if !g.options().compound {
        return None;
    }

    let mut ancestors: std::collections::HashSet<String> = std::collections::HashSet::new();
    let mut cur = g.parent(a);
    while let Some(p) = cur {
        ancestors.insert(p.to_string());
        cur = g.parent(p);
    }

    let mut cur = g.parent(b);
    while let Some(p) = cur {
        if ancestors.contains(p) {
            return Some(p.to_string());
        }
        cur = g.parent(p);
    }

    None
}

fn extract_descendants(id: &str, g: &Graph<NodeLabel, EdgeLabel, GraphLabel>) -> Vec<String> {
    let mut out: Vec<String> = Vec::new();
    let mut visited: HashSet<String> = HashSet::new();
    let mut stack: Vec<String> = g.children(id).iter().map(|s| s.to_string()).collect();
    while let Some(node) = stack.pop() {
        if !visited.insert(node.clone()) {
            continue;
        }
        for child in g.children(&node) {
            stack.push(child.to_string());
        }
        out.push(node);
    }
    out
}

fn edge_in_cluster(
    edge: &dugong::graphlib::EdgeKey,
    cluster_id: &str,
    descendants: &std::collections::HashMap<String, Vec<String>>,
) -> bool {
    if edge.v == cluster_id || edge.w == cluster_id {
        return false;
    }
    let Some(cluster_desc) = descendants.get(cluster_id) else {
        return false;
    };
    cluster_desc.contains(&edge.v) || cluster_desc.contains(&edge.w)
}

#[derive(Debug, Clone)]
struct FlowchartClusterDbEntry {
    anchor_id: String,
    external_connections: bool,
}

fn flowchart_find_common_edges(
    graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
    id1: &str,
    id2: &str,
) -> Vec<(String, String)> {
    let edges1: Vec<(String, String)> = graph
        .edge_keys()
        .into_iter()
        .filter(|edge| edge.v == id1 || edge.w == id1)
        .map(|edge| (edge.v, edge.w))
        .collect();
    let edges2: Vec<(String, String)> = graph
        .edge_keys()
        .into_iter()
        .filter(|edge| edge.v == id2 || edge.w == id2)
        .map(|edge| (edge.v, edge.w))
        .collect();

    let edges1_prim: Vec<(String, String)> = edges1
        .into_iter()
        .map(|(v, w)| {
            (
                if v == id1 { id2.to_string() } else { v },
                // Mermaid's `findCommonEdges(...)` has an asymmetry here: it maps the `w` side
                // back to `id1` rather than `id2` (Mermaid@11.12.2).
                if w == id1 { id1.to_string() } else { w },
            )
        })
        .collect();

    let mut out = Vec::new();
    for e1 in edges1_prim {
        if edges2.contains(&e1) {
            out.push(e1);
        }
    }
    out
}

fn flowchart_find_non_cluster_child(
    id: &str,
    graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
    cluster_id: &str,
) -> Option<String> {
    let children = graph.children(id);
    if children.is_empty() {
        return Some(id.to_string());
    }
    let mut reserve: Option<String> = None;
    let mut visited: HashSet<String> = HashSet::new();
    let mut stack: Vec<String> = children.iter().rev().map(|s| s.to_string()).collect();
    while let Some(node) = stack.pop() {
        if !visited.insert(node.clone()) {
            continue;
        }
        let children = graph.children(&node);
        if !children.is_empty() {
            for child in children.iter().rev() {
                stack.push(child.to_string());
            }
            continue;
        }
        let common_edges = flowchart_find_common_edges(graph, cluster_id, &node);
        if !common_edges.is_empty() {
            reserve = Some(node);
        } else {
            return Some(node);
        }
    }
    reserve
}

fn adjust_flowchart_clusters_and_edges(
    graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
) -> std::collections::HashMap<String, bool> {
    use serde_json::Value;

    fn is_descendant(
        node_id: &str,
        cluster_id: &str,
        descendants: &std::collections::HashMap<String, Vec<String>>,
    ) -> bool {
        descendants
            .get(cluster_id)
            .is_some_and(|ds| ds.iter().any(|n| n == node_id))
    }

    let mut descendants: std::collections::HashMap<String, Vec<String>> =
        std::collections::HashMap::new();
    let mut cluster_db: std::collections::HashMap<String, FlowchartClusterDbEntry> =
        std::collections::HashMap::new();

    for id in graph.node_ids() {
        if graph.children(&id).is_empty() {
            continue;
        }
        descendants.insert(id.clone(), extract_descendants(&id, graph));
        let anchor_id =
            flowchart_find_non_cluster_child(&id, graph, &id).unwrap_or_else(|| id.clone());
        cluster_db.insert(
            id,
            FlowchartClusterDbEntry {
                anchor_id,
                external_connections: false,
            },
        );
    }

    for id in cluster_db.keys().cloned().collect::<Vec<_>>() {
        if graph.children(&id).is_empty() {
            continue;
        }
        let mut has_external = false;
        for e in graph.edges() {
            let d1 = is_descendant(e.v.as_str(), id.as_str(), &descendants);
            let d2 = is_descendant(e.w.as_str(), id.as_str(), &descendants);
            if d1 ^ d2 {
                has_external = true;
                break;
            }
        }
        if let Some(entry) = cluster_db.get_mut(&id) {
            entry.external_connections = has_external;
        }
    }

    for id in cluster_db.keys().cloned().collect::<Vec<_>>() {
        let Some(non_cluster_child) = cluster_db.get(&id).map(|e| e.anchor_id.clone()) else {
            continue;
        };
        let parent = graph.parent(&non_cluster_child);
        if parent.is_some_and(|p| p != id.as_str())
            && parent.is_some_and(|p| cluster_db.contains_key(p))
            && parent.is_some_and(|p| !cluster_db.get(p).is_some_and(|e| e.external_connections))
        {
            if let Some(p) = parent {
                if let Some(entry) = cluster_db.get_mut(&id) {
                    entry.anchor_id = p.to_string();
                }
            }
        }
    }

    fn get_anchor_id(
        id: &str,
        cluster_db: &std::collections::HashMap<String, FlowchartClusterDbEntry>,
    ) -> String {
        let Some(entry) = cluster_db.get(id) else {
            return id.to_string();
        };
        if !entry.external_connections {
            return id.to_string();
        }
        entry.anchor_id.clone()
    }

    let edge_keys = graph.edge_keys();
    for ek in edge_keys {
        if !cluster_db.contains_key(&ek.v) && !cluster_db.contains_key(&ek.w) {
            continue;
        }

        let Some(mut edge_label) = graph.edge_by_key(&ek).cloned() else {
            continue;
        };

        let v = get_anchor_id(&ek.v, &cluster_db);
        let w = get_anchor_id(&ek.w, &cluster_db);

        // Match Mermaid `adjustClustersAndEdges`: edges that touch cluster nodes are removed and
        // re-inserted even when their endpoints do not change. This affects edge iteration order
        // and therefore cycle-breaking determinism in Dagre's acyclic pass.
        let _ = graph.remove_edge_key(&ek);

        if v != ek.v {
            if let Some(parent) = graph.parent(&v) {
                if let Some(entry) = cluster_db.get_mut(parent) {
                    entry.external_connections = true;
                }
            }
            edge_label
                .extras
                .insert("fromCluster".to_string(), Value::String(ek.v.clone()));
        }

        if w != ek.w {
            if let Some(parent) = graph.parent(&w) {
                if let Some(entry) = cluster_db.get_mut(parent) {
                    entry.external_connections = true;
                }
            }
            edge_label
                .extras
                .insert("toCluster".to_string(), Value::String(ek.w.clone()));
        }

        graph.set_edge_named(v, w, ek.name, Some(edge_label));
    }

    cluster_db
        .into_iter()
        .map(|(id, entry)| (id, entry.external_connections))
        .collect()
}

fn copy_cluster(
    cluster_id: &str,
    graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
    new_graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
    root_id: &str,
    descendants: &std::collections::HashMap<String, Vec<String>>,
) {
    let mut nodes: Vec<String> = graph
        .children(cluster_id)
        .iter()
        .map(|s| s.to_string())
        .collect();
    if cluster_id != root_id {
        nodes.push(cluster_id.to_string());
    }

    for node in nodes {
        if !graph.has_node(&node) {
            continue;
        }

        if !graph.children(&node).is_empty() {
            copy_cluster(&node, graph, new_graph, root_id, descendants);
        } else {
            let data = graph.node(&node).cloned().unwrap_or_default();
            new_graph.set_node(node.clone(), data);

            if let Some(parent) = graph.parent(&node) {
                if parent != root_id {
                    new_graph.set_parent(node.clone(), parent.to_string());
                }
            }
            if cluster_id != root_id && node != cluster_id {
                new_graph.set_parent(node.clone(), cluster_id.to_string());
            }

            // Copy edges for this extracted cluster.
            //
            // Mermaid's implementation calls `graph.edges(node)` (note: on dagre-d3-es Graphlib,
            // `edges()` ignores the argument and returns *all* edges). Because the source graph is
            // mutated as nodes are removed, this makes edge insertion order sensitive to the leaf
            // traversal order, which in turn can affect deterministic tie-breaking in Dagre's
            // acyclic/ranking steps.
            //
            // Reference:
            // - `packages/mermaid/src/rendering-util/layout-algorithms/dagre/mermaid-graphlib.js`
            for ek in graph.edge_keys() {
                if !edge_in_cluster(&ek, root_id, descendants) {
                    continue;
                }
                if new_graph.has_edge(&ek.v, &ek.w, ek.name.as_deref()) {
                    continue;
                }
                let Some(lbl) = graph.edge_by_key(&ek).cloned() else {
                    continue;
                };
                new_graph.set_edge_named(ek.v, ek.w, ek.name, Some(lbl));
            }
        }

        let _ = graph.remove_node(&node);
    }
}

fn extract_clusters_recursively(
    graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
    subgraphs_by_id: &std::collections::HashMap<String, FlowSubgraph>,
    external_connections_by_id: &std::collections::HashMap<String, bool>,
    extracted: &mut std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
    _depth: usize,
) {
    struct ExtractFrame {
        id: String,
        graph: Graph<NodeLabel, EdgeLabel, GraphLabel>,
        expanded: bool,
    }

    fn extract_one_level(
        graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
        subgraphs_by_id: &std::collections::HashMap<String, FlowSubgraph>,
        external_connections_by_id: &std::collections::HashMap<String, bool>,
    ) -> Vec<(String, Graph<NodeLabel, EdgeLabel, GraphLabel>)> {
        let node_ids = graph.node_ids();
        let mut descendants: std::collections::HashMap<String, Vec<String>> =
            std::collections::HashMap::new();
        for id in &node_ids {
            if graph.children(id).is_empty() {
                continue;
            }
            descendants.insert(id.clone(), extract_descendants(id, graph));
        }

        let mut extracted_here: Vec<(String, Graph<NodeLabel, EdgeLabel, GraphLabel>)> = Vec::new();

        let candidates: Vec<String> = node_ids
            .into_iter()
            .filter(|id| graph.has_node(id))
            .filter(|id| !graph.children(id).is_empty())
            // Mermaid's extractor does not recompute external connections after
            // `adjustClustersAndEdges` rewrites cluster endpoints to anchor children. It uses the
            // global `clusterDb.externalConnections` flag computed before those rewrites, then
            // recurses into extracted graphs with the same `clusterDb`.
            //
            // Reference:
            // - `packages/mermaid/src/rendering-util/layout-algorithms/dagre/mermaid-graphlib.js`
            .filter(|id| {
                external_connections_by_id
                    .get(id.as_str())
                    .is_some_and(|external| !external)
            })
            .collect();

        for id in candidates {
            if !graph.has_node(&id) {
                continue;
            }
            if graph.children(&id).is_empty() {
                continue;
            }

            let mut cluster_graph: Graph<NodeLabel, EdgeLabel, GraphLabel> =
                Graph::new(GraphOptions {
                    multigraph: true,
                    compound: true,
                    directed: true,
                });

            // Mermaid's `extractor(...)` uses:
            // - `clusterData.dir` when explicitly set for the subgraph
            // - otherwise: toggle relative to the current graph's rankdir (TB<->LR)
            let dir = subgraphs_by_id
                .get(&id)
                .and_then(|sg| sg.dir.as_deref())
                .map(str::trim)
                .filter(|s| !s.is_empty())
                .map(normalize_dir)
                .unwrap_or_else(|| toggled_dir(flow_dir_from_rankdir(graph.graph().rankdir)));

            cluster_graph.set_graph(GraphLabel {
                rankdir: dir_to_rankdir(&dir),
                // Mermaid's cluster extractor initializes subgraphs with a fixed dagre config
                // (nodesep/ranksep=50, marginx/marginy=8). Before each recursive render Mermaid then
                // overrides `nodesep` to the parent graph value and `ranksep` to `parent.ranksep + 25`.
                //
                // We model that in headless mode by keeping the extractor defaults here, then applying
                // the per-depth override inside `layout_graph_with_recursive_clusters(...)` right
                // before laying out each extracted graph.
                //
                // Reference:
                // - `packages/mermaid/src/rendering-util/layout-algorithms/dagre/mermaid-graphlib.js`
                // - `packages/mermaid/src/rendering-util/layout-algorithms/dagre/index.js`
                nodesep: 50.0,
                ranksep: 50.0,
                marginx: 8.0,
                marginy: 8.0,
                acyclicer: None,
                ..Default::default()
            });

            copy_cluster(&id, graph, &mut cluster_graph, &id, &descendants);
            extracted_here.push((id, cluster_graph));
        }

        extracted_here
    }

    let extracted_here = extract_one_level(graph, subgraphs_by_id, external_connections_by_id);
    let mut stack: Vec<ExtractFrame> = extracted_here
        .into_iter()
        .rev()
        .map(|(id, graph)| ExtractFrame {
            id,
            graph,
            expanded: false,
        })
        .collect();

    while let Some(mut frame) = stack.pop() {
        if frame.expanded {
            extracted.insert(frame.id, frame.graph);
            continue;
        }

        let children = extract_one_level(
            &mut frame.graph,
            subgraphs_by_id,
            external_connections_by_id,
        );
        frame.expanded = true;
        stack.push(frame);
        stack.extend(children.into_iter().rev().map(|(id, graph)| ExtractFrame {
            id,
            graph,
            expanded: false,
        }));
    }
}

pub fn layout_flowchart_v2(
    semantic: &Value,
    effective_config: &MermaidConfig,
    measurer: &dyn TextMeasurer,
    math_renderer: Option<&(dyn MathRenderer + Send + Sync)>,
) -> Result<FlowchartV2Layout> {
    let timing_enabled = std::env::var("MERMAN_FLOWCHART_LAYOUT_TIMING")
        .map(|v| v == "1" || v.eq_ignore_ascii_case("true"))
        .unwrap_or(false);
    let total_start = timing_enabled.then(std::time::Instant::now);

    let deserialize_start = timing_enabled.then(std::time::Instant::now);
    let model: FlowchartV2Model = crate::json::from_value_ref(semantic)?;
    let deserialize = deserialize_start.map(|s| s.elapsed()).unwrap_or_default();

    layout_flowchart_v2_with_model(
        &model,
        effective_config,
        measurer,
        math_renderer,
        timing_enabled,
        total_start,
        deserialize,
    )
}

pub fn layout_flowchart_v2_typed(
    model: &FlowchartV2Model,
    effective_config: &MermaidConfig,
    measurer: &dyn TextMeasurer,
    math_renderer: Option<&(dyn MathRenderer + Send + Sync)>,
) -> Result<FlowchartV2Layout> {
    let timing_enabled = std::env::var("MERMAN_FLOWCHART_LAYOUT_TIMING")
        .map(|v| v == "1" || v.eq_ignore_ascii_case("true"))
        .unwrap_or(false);
    let total_start = timing_enabled.then(std::time::Instant::now);

    layout_flowchart_v2_with_model(
        model,
        effective_config,
        measurer,
        math_renderer,
        timing_enabled,
        total_start,
        std::time::Duration::default(),
    )
}

fn layout_flowchart_v2_with_model(
    model: &FlowchartV2Model,
    effective_config: &MermaidConfig,
    measurer: &dyn TextMeasurer,
    math_renderer: Option<&(dyn MathRenderer + Send + Sync)>,
    timing_enabled: bool,
    total_start: Option<std::time::Instant>,
    deserialize: std::time::Duration,
) -> Result<FlowchartV2Layout> {
    #[derive(Debug, Default, Clone)]
    struct FlowchartLayoutTimings {
        total: std::time::Duration,
        deserialize: std::time::Duration,
        expand_self_loops: std::time::Duration,
        build_graph: std::time::Duration,
        extract_clusters: std::time::Duration,
        dom_order: std::time::Duration,
        layout_recursive: std::time::Duration,
        dagre_calls: u32,
        dagre_total: std::time::Duration,
        place_graph: std::time::Duration,
        build_output: std::time::Duration,
    }

    let mut timings = FlowchartLayoutTimings {
        deserialize,
        ..Default::default()
    };

    let effective_config_value = effective_config.as_value();

    // Mermaid's dagre adapter expands self-loop edges into a chain of two special label nodes plus
    // three edges. This avoids `v == w` edges in Dagre and is required for SVG parity (Mermaid
    // uses `*-cyclic-special-*` ids when rendering self-loops).
    let expand_self_loops_start = timing_enabled.then(std::time::Instant::now);
    let self_loop_count = model.edges.iter().filter(|e| e.from == e.to).count();
    let mut render_edges: Vec<std::borrow::Cow<'_, FlowEdge>> =
        Vec::with_capacity(model.edges.len() + self_loop_count * 3);
    let mut self_loop_label_node_ids: Vec<String> = Vec::new();
    let mut self_loop_label_node_id_set: std::collections::HashSet<String> =
        std::collections::HashSet::new();
    for e in &model.edges {
        if e.from != e.to {
            render_edges.push(std::borrow::Cow::Borrowed(e));
            continue;
        }

        let helper_edges = super::flowchart_self_loop_helper_edges(
            e,
            super::FlowchartSelfLoopEdgeOptions::layout(),
        );
        if self_loop_label_node_id_set.insert(helper_edges.special_id_1.clone()) {
            self_loop_label_node_ids.push(helper_edges.special_id_1.clone());
        }
        if self_loop_label_node_id_set.insert(helper_edges.special_id_2.clone()) {
            self_loop_label_node_ids.push(helper_edges.special_id_2.clone());
        }

        // Mermaid clears the label text on the end segments, but keeps the label (if any) on the
        // mid edge (`edgeMid` is a structuredClone of the original edge without label changes).
        render_edges.push(std::borrow::Cow::Owned(helper_edges.edge1));
        render_edges.push(std::borrow::Cow::Owned(helper_edges.edge_mid));
        render_edges.push(std::borrow::Cow::Owned(helper_edges.edge2));
    }
    if let Some(s) = expand_self_loops_start {
        timings.expand_self_loops = s.elapsed();
    }

    let build_graph_start = timing_enabled.then(std::time::Instant::now);

    let nodesep = config_f64(effective_config_value, &["flowchart", "nodeSpacing"]).unwrap_or(50.0);
    let ranksep = config_f64(effective_config_value, &["flowchart", "rankSpacing"]).unwrap_or(50.0);
    // Mermaid's default config sets `flowchart.padding` to 15.
    let node_padding =
        config_f64(effective_config_value, &["flowchart", "padding"]).unwrap_or(15.0);
    // Used by a few flowchart-v2 shapes (notably `forkJoin.ts`) to inflate Dagre node dimensions.
    // Mermaid default config sets `state.padding` to 8.
    let state_padding = config_f64(effective_config_value, &["state", "padding"]).unwrap_or(8.0);
    let wrapping_width =
        config_f64(effective_config_value, &["flowchart", "wrappingWidth"]).unwrap_or(200.0);
    // Mermaid measures edge labels via `createText(...)` without overriding the default
    // wrapping width (200px), independent of `flowchart.wrappingWidth`.
    let edge_label_wrapping_width = 200.0;
    // Mermaid@11.12.2 renders subgraph titles via the `createText(...)` path and applies a default
    // wrapping width of 200px (even when `labelType=text` and `htmlLabels=false`), which results
    // in `<tspan>`-wrapped titles for long words. Match that behavior in headless metrics.
    let cluster_title_wrapping_width = 200.0;
    // Mermaid flowchart-v2 has split htmlLabels semantics: node labels follow the root
    // `htmlLabels` toggle, while edge labels, subgraph titles, CSS selectors, and browser-style
    // styled-label height quirks follow `flowchart.htmlLabels` and fall back to the root toggle.
    let node_html_labels = flowchart_effective_node_html_labels(effective_config_value);
    let flowchart_html_labels = flowchart_effective_html_labels(effective_config_value);
    let edge_html_labels = flowchart_html_labels;
    let cluster_html_labels = edge_html_labels;
    let node_html_label_css_parity = node_html_labels && flowchart_html_labels;
    let node_wrap_mode = if node_html_labels {
        WrapMode::HtmlLike
    } else {
        WrapMode::SvgLike
    };
    let cluster_wrap_mode = if cluster_html_labels {
        WrapMode::HtmlLike
    } else {
        WrapMode::SvgLike
    };
    let edge_wrap_mode = if edge_html_labels {
        WrapMode::HtmlLike
    } else {
        WrapMode::SvgLike
    };
    // Mermaid FlowDB encodes subgraph nodes with a fixed `padding: 8` in `data4Layout.nodes`.
    // That value is separate from `flowchart.padding` (node padding) and `nodeSpacing`/`rankSpacing`.
    let cluster_padding = 8.0;
    let title_margin_top = config_f64(
        effective_config_value,
        &["flowchart", "subGraphTitleMargin", "top"],
    )
    .unwrap_or(0.0);
    let title_margin_bottom = config_f64(
        effective_config_value,
        &["flowchart", "subGraphTitleMargin", "bottom"],
    )
    .unwrap_or(0.0);
    let title_total_margin = title_margin_top + title_margin_bottom;
    let y_shift = title_total_margin / 2.0;
    let inherit_dir = effective_config_value
        .get("flowchart")
        .and_then(|v| v.get("inheritDir"))
        .and_then(Value::as_bool)
        .unwrap_or(false);

    fn normalize_css_font_family(font_family: &str) -> String {
        let s = font_family.trim().trim_end_matches(';').trim();
        if s.is_empty() {
            return String::new();
        }

        let mut parts: Vec<String> = Vec::new();
        let mut cur = String::new();
        let mut in_single = false;
        let mut in_double = false;

        for ch in s.chars() {
            match ch {
                '\'' if !in_double => {
                    in_single = !in_single;
                    cur.push(ch);
                }
                '"' if !in_single => {
                    in_double = !in_double;
                    cur.push(ch);
                }
                ',' if !in_single && !in_double => {
                    let p = cur.trim();
                    if !p.is_empty() {
                        parts.push(p.to_string());
                    }
                    cur.clear();
                }
                _ => cur.push(ch),
            }
        }

        let p = cur.trim();
        if !p.is_empty() {
            parts.push(p.to_string());
        }
        parts.join(",")
    }

    fn parse_font_size_px(v: &serde_json::Value) -> Option<f64> {
        if let Some(n) = v.as_f64() {
            return Some(n);
        }
        if let Some(n) = v.as_i64() {
            return Some(n as f64);
        }
        if let Some(n) = v.as_u64() {
            return Some(n as f64);
        }
        let s = v.as_str()?.trim();
        if s.is_empty() {
            return None;
        }
        let mut num = String::new();
        for (idx, ch) in s.chars().enumerate() {
            if ch.is_ascii_digit() {
                num.push(ch);
                continue;
            }
            if idx == 0 && (ch == '-' || ch == '+') {
                num.push(ch);
                continue;
            }
            break;
        }
        if num.trim().is_empty() {
            return None;
        }
        num.parse::<f64>().ok()
    }

    let default_theme_font_family = "\"trebuchet ms\",verdana,arial,sans-serif".to_string();
    let theme_font_family =
        config_string(effective_config_value, &["themeVariables", "fontFamily"])
            .map(|s| normalize_css_font_family(&s));
    let top_font_family = config_string(effective_config_value, &["fontFamily"])
        .map(|s| normalize_css_font_family(&s));
    let font_family = Some(match (top_font_family, theme_font_family) {
        (Some(top), Some(theme)) if theme == default_theme_font_family => top,
        (_, Some(theme)) => theme,
        (Some(top), None) => top,
        (None, None) => default_theme_font_family,
    });
    let font_size = effective_config_value
        .get("themeVariables")
        .and_then(|tv| tv.get("fontSize"))
        .and_then(parse_font_size_px)
        .unwrap_or(16.0);
    let font_weight = config_string(effective_config_value, &["fontWeight"]);
    let text_style = TextStyle {
        font_family,
        font_size,
        font_weight,
    };
    let html_label_text_style =
        flowchart_html_label_measurement_base_style(&text_style, effective_config_value);
    let node_label_base_style = if node_wrap_mode == WrapMode::HtmlLike {
        &html_label_text_style
    } else {
        &text_style
    };
    let cluster_label_base_style = if cluster_wrap_mode == WrapMode::HtmlLike {
        &html_label_text_style
    } else {
        &text_style
    };
    let edge_label_base_style = if edge_wrap_mode == WrapMode::HtmlLike {
        &html_label_text_style
    } else {
        &text_style
    };

    let diagram_direction = normalize_dir(model.direction.as_deref().unwrap_or("TB"));
    let has_subgraphs = !model.subgraphs.is_empty();
    let mut subgraphs_by_id: std::collections::HashMap<String, FlowSubgraph> =
        std::collections::HashMap::new();
    for sg in &model.subgraphs {
        subgraphs_by_id.insert(sg.id.clone(), sg.clone());
    }
    let subgraph_ids: std::collections::HashSet<&str> =
        model.subgraphs.iter().map(|sg| sg.id.as_str()).collect();
    let subgraph_id_set: std::collections::HashSet<String> =
        model.subgraphs.iter().map(|sg| sg.id.clone()).collect();
    let mut g: Graph<NodeLabel, EdgeLabel, GraphLabel> = Graph::new(GraphOptions {
        multigraph: true,
        // Mermaid's Dagre adapter always enables `compound: true`, even if there are no explicit
        // subgraphs. This also allows `nestingGraph.run` to connect components during ranking.
        compound: true,
        directed: true,
    });
    g.set_graph(GraphLabel {
        rankdir: rank_dir_from_flow(&diagram_direction),
        nodesep,
        ranksep,
        marginx: 8.0,
        marginy: 8.0,
        acyclicer: None,
        ..Default::default()
    });

    let mut empty_subgraph_ids: Vec<String> = Vec::new();
    let mut cluster_node_labels: std::collections::HashMap<String, NodeLabel> =
        std::collections::HashMap::new();
    for sg in &model.subgraphs {
        if sg.nodes.is_empty() {
            // Mermaid renders empty subgraphs as regular nodes. Keep the semantic `subgraph`
            // definition around for styling/title, but size + lay it out as a leaf node.
            empty_subgraph_ids.push(sg.id.clone());
            continue;
        }
        // Mermaid does not pre-size compound (subgraph) nodes based on title metrics for Dagre
        // layout. Their dimensions are computed from children (border nodes) and then adjusted at
        // render time for title width and configured margins.
        cluster_node_labels.insert(sg.id.clone(), NodeLabel::default());
    }

    let mut leaf_node_labels: std::collections::HashMap<String, NodeLabel> =
        std::collections::HashMap::new();
    let mut leaf_label_metrics_by_id: HashMap<String, (f64, f64)> = HashMap::new();
    leaf_label_metrics_by_id.reserve(model.nodes.len() + empty_subgraph_ids.len());
    for n in &model.nodes {
        // Mermaid treats the subgraph id as the "group node" id (a cluster can be referenced in
        // edges). Avoid introducing a separate leaf node that would collide with the cluster node
        // of the same id.
        if subgraph_ids.contains(n.id.as_str()) {
            continue;
        }
        let raw_label = n.label.as_deref().unwrap_or(&n.id);
        let label_type = n.label_type.as_deref().unwrap_or("text");
        let node_text_style = flowchart_effective_text_style_for_node_classes(
            node_label_base_style,
            &model.class_defs,
            &n.classes,
            &n.styles,
        );
        let mut metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer,
            raw_label,
            label_type,
            style: node_text_style.as_ref(),
            max_width_px: Some(wrapping_width),
            wrap_mode: node_wrap_mode,
            config: effective_config,
            math_renderer,
            preserve_string_whitespace_height: node_html_label_css_parity,
        });
        let span_css_height_parity =
            flowchart_node_has_span_css_height_parity(&model.class_defs, &n.classes);
        if node_html_label_css_parity && span_css_height_parity {
            crate::text::flowchart_apply_mermaid_styled_node_height_parity(
                &mut metrics,
                node_text_style.as_ref(),
            );
        }
        if node_wrap_mode == WrapMode::SvgLike
            && label_type != "markdown"
            && !raw_label.contains('<')
            && !raw_label.contains('>')
            && matches!(
                n.layout_shape.as_deref().unwrap_or("squareRect"),
                "squareRect"
            )
        {
            let plain = crate::flowchart::flowchart_label_plain_text_for_layout(
                raw_label, label_type, false,
            );
            metrics.width = flowchart_svg_plain_computed_width_px(
                measurer,
                &plain,
                node_text_style.as_ref(),
                Some(wrapping_width),
            );
        }
        leaf_label_metrics_by_id.insert(n.id.clone(), (metrics.width, metrics.height));
        let (width, height) = node_layout_dimensions(NodeLayoutDimensionsRequest {
            layout_shape: n.layout_shape.as_deref(),
            layout_direction: &diagram_direction,
            metrics,
            padding: node_padding,
            state_padding,
            wrap_mode: node_wrap_mode,
            node_icon: n.icon.as_deref(),
            node_img: n.img.as_deref(),
            node_pos: n.pos.as_deref(),
            node_asset_width: n.asset_width,
            node_asset_height: n.asset_height,
        });
        leaf_node_labels.insert(
            n.id.clone(),
            NodeLabel {
                width,
                height,
                ..Default::default()
            },
        );
    }
    for sg in &model.subgraphs {
        if !sg.nodes.is_empty() {
            continue;
        }
        let label_type = sg.label_type.as_deref().unwrap_or("text");
        let sg_text_style = flowchart_effective_text_style_for_classes(
            cluster_label_base_style,
            &model.class_defs,
            &sg.classes,
            &[],
        );
        let metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer,
            raw_label: &sg.title,
            label_type,
            style: sg_text_style.as_ref(),
            max_width_px: Some(cluster_title_wrapping_width),
            wrap_mode: node_wrap_mode,
            config: effective_config,
            math_renderer,
            preserve_string_whitespace_height: node_html_label_css_parity,
        });
        leaf_label_metrics_by_id.insert(sg.id.clone(), (metrics.width, metrics.height));
        let (width, height) = node_layout_dimensions(NodeLayoutDimensionsRequest {
            layout_shape: Some("squareRect"),
            layout_direction: &diagram_direction,
            metrics,
            padding: cluster_padding,
            state_padding,
            wrap_mode: node_wrap_mode,
            node_icon: None,
            node_img: None,
            node_pos: None,
            node_asset_width: None,
            node_asset_height: None,
        });
        leaf_node_labels.insert(
            sg.id.clone(),
            NodeLabel {
                width,
                height,
                ..Default::default()
            },
        );
    }

    // Mermaid constructs the Dagre graph by:
    // 1) inserting subgraph (cluster) nodes first (in reverse `subgraphs[]` order), then
    // 2) inserting vertex nodes (in FlowDB `Map` insertion order),
    // and setting `parentId` as each node is inserted.
    //
    // Matching this order matters because Graphlib insertion order can affect compound-graph
    // child ordering, anchor selection and deterministic tie-breaking in layout.
    let mut inserted: std::collections::HashSet<String> = std::collections::HashSet::new();
    let mut parent_assigned: std::collections::HashSet<String> = std::collections::HashSet::new();
    let insert_one = |id: &str,
                      g: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
                      inserted: &mut std::collections::HashSet<String>| {
        if inserted.contains(id) {
            return;
        }
        if let Some(lbl) = cluster_node_labels.get(id).cloned() {
            g.set_node(id.to_string(), lbl);
            inserted.insert(id.to_string());
            return;
        }
        if let Some(lbl) = leaf_node_labels.get(id).cloned() {
            g.set_node(id.to_string(), lbl);
            inserted.insert(id.to_string());
        }
    };

    if has_subgraphs {
        // Match Mermaid's `FlowDB.getData()` parent assignment: build `parentId` by iterating
        // subgraphs in reverse order and recording each membership.
        let mut parent_by_id: std::collections::HashMap<String, String> =
            std::collections::HashMap::new();
        for sg in model.subgraphs.iter().rev() {
            for child in &sg.nodes {
                parent_by_id.insert(child.clone(), sg.id.clone());
            }
        }

        let insert_with_parent =
            |id: &str,
             g: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
             inserted: &mut std::collections::HashSet<String>,
             parent_assigned: &mut std::collections::HashSet<String>| {
                insert_one(id, g, inserted);
                if !parent_assigned.insert(id.to_string()) {
                    return;
                }
                if let Some(p) = parent_by_id.get(id).cloned() {
                    g.set_parent(id.to_string(), p);
                }
            };

        for sg in model.subgraphs.iter().rev() {
            insert_with_parent(sg.id.as_str(), &mut g, &mut inserted, &mut parent_assigned);
        }
        for n in &model.nodes {
            insert_with_parent(n.id.as_str(), &mut g, &mut inserted, &mut parent_assigned);
        }
        for id in &model.vertex_calls {
            insert_with_parent(id.as_str(), &mut g, &mut inserted, &mut parent_assigned);
        }
    } else {
        // No subgraphs: insertion order still matters for deterministic Dagre tie-breaking.
        for n in &model.nodes {
            insert_one(n.id.as_str(), &mut g, &mut inserted);
        }
        for id in &model.vertex_calls {
            insert_one(id.as_str(), &mut g, &mut inserted);
        }
    }

    // Materialize self-loop helper label nodes and place them in the same parent cluster as the
    // base node (if any), matching Mermaid `@11.12.2` dagre layout adapter behavior.
    for id in &self_loop_label_node_ids {
        if !g.has_node(id) {
            g.set_node(
                id.clone(),
                NodeLabel {
                    // Mermaid initializes these labelRect nodes at 10x10, but then immediately
                    // runs `insertNode(...)` + `updateNodeBounds(...)` before Dagre layout. For an
                    // empty `labelRect`, the measured bbox collapses to ~0.1x0.1 and that is what
                    // Dagre actually sees for spacing. Match that here for layout parity.
                    width: 0.1_f32 as f64,
                    height: 0.1_f32 as f64,
                    ..Default::default()
                },
            );
        }
        let Some((base, _)) = id.split_once("---") else {
            continue;
        };
        if let Some(p) = g.parent(base) {
            g.set_parent(id.clone(), p.to_string());
        }
    }

    let effective_dir_by_id = if has_subgraphs {
        compute_effective_dir_by_id(&subgraphs_by_id, &g, &diagram_direction, inherit_dir)
    } else {
        HashMap::new()
    };

    // Map SVG edge ids to the multigraph key used by the Dagre layout graph. Most edges use their
    // `id` as the key, but Mermaid uses distinct keys for the self-loop special edges and we also
    // want deterministic ordering under our BTree-backed graph storage.
    let mut edge_key_by_id: HashMap<String, String> = HashMap::new();
    let mut edge_id_by_key: HashMap<String, String> = HashMap::new();

    for e in &render_edges {
        // Mermaid uses distinct graphlib multigraph keys for self-loop helper edges.
        // Reference: `packages/mermaid/src/rendering-util/layout-algorithms/dagre/index.js`
        let edge_key = if let Some(prefix) = e.id.strip_suffix("-cyclic-special-1") {
            format!("{prefix}-cyclic-special-0")
        } else if let Some(prefix) = e.id.strip_suffix("-cyclic-special-mid") {
            format!("{prefix}-cyclic-special-1")
        } else if let Some(prefix) = e.id.strip_suffix("-cyclic-special-2") {
            // Mermaid contains this typo in the edge key (note the `<`):
            // `nodeId + '-cyc<lic-special-2'`
            format!("{prefix}-cyc<lic-special-2")
        } else {
            e.id.clone()
        };
        edge_key_by_id.insert(e.id.clone(), edge_key.clone());
        edge_id_by_key.insert(edge_key.clone(), e.id.clone());

        let from = e.from.clone();
        let to = e.to.clone();

        if edge_label_is_non_empty(e) {
            let label_text = e.label.as_deref().unwrap_or_default();
            let label_type = e.label_type.as_deref().unwrap_or("text");
            let edge_text_style = flowchart_effective_text_style_for_classes(
                edge_label_base_style,
                &model.class_defs,
                &e.classes,
                &e.style,
            );
            let metrics = if label_type == "markdown" && edge_wrap_mode != WrapMode::HtmlLike {
                crate::text::measure_wrapped_markdown_with_flowchart_bold_deltas(
                    measurer,
                    label_text,
                    edge_text_style.as_ref(),
                    Some(edge_label_wrapping_width),
                    edge_wrap_mode,
                )
            } else {
                flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
                    measurer,
                    raw_label: label_text,
                    label_type,
                    style: edge_text_style.as_ref(),
                    max_width_px: Some(edge_label_wrapping_width),
                    wrap_mode: edge_wrap_mode,
                    config: effective_config,
                    math_renderer,
                    preserve_string_whitespace_height: false,
                })
            };
            let (label_width, label_height) = if edge_html_labels {
                (metrics.width.max(1.0), metrics.height.max(1.0))
            } else {
                // Mermaid's SVG edge-labels include a padded background rect (+2px left/right and
                // +2px top/bottom).
                (
                    (metrics.width + 4.0).max(1.0),
                    (metrics.height + 4.0).max(1.0),
                )
            };

            let minlen = e.length.max(1);
            let el = EdgeLabel {
                width: label_width,
                height: label_height,
                labelpos: LabelPos::C,
                // Dagre layout defaults `labeloffset` to 10 when unspecified.
                labeloffset: 10.0,
                minlen,
                weight: 1.0,
                ..Default::default()
            };

            g.set_edge_named(from, to, Some(edge_key), Some(el));
        } else {
            let el = EdgeLabel {
                width: 0.0,
                height: 0.0,
                labelpos: LabelPos::C,
                // Dagre layout defaults `labeloffset` to 10 when unspecified.
                labeloffset: 10.0,
                minlen: e.length.max(1),
                weight: 1.0,
                ..Default::default()
            };
            g.set_edge_named(from, to, Some(edge_key), Some(el));
        }
    }

    let external_connections_by_id = if has_subgraphs {
        adjust_flowchart_clusters_and_edges(&mut g)
    } else {
        std::collections::HashMap::new()
    };

    let mut edge_endpoints_by_id: HashMap<String, (String, String)> = HashMap::new();
    for ek in g.edge_keys() {
        let Some(edge_key) = ek.name.as_deref() else {
            continue;
        };
        let edge_id = edge_id_by_key
            .get(edge_key)
            .cloned()
            .unwrap_or_else(|| edge_key.to_string());
        edge_endpoints_by_id.insert(edge_id, (ek.v.clone(), ek.w.clone()));
    }

    if let Some(s) = build_graph_start {
        timings.build_graph = s.elapsed();
    }

    let mut extracted_graphs: std::collections::HashMap<
        String,
        Graph<NodeLabel, EdgeLabel, GraphLabel>,
    > = std::collections::HashMap::new();
    if has_subgraphs {
        let extract_start = timing_enabled.then(std::time::Instant::now);
        extract_clusters_recursively(
            &mut g,
            &subgraphs_by_id,
            &external_connections_by_id,
            &mut extracted_graphs,
            0,
        );
        if let Some(s) = extract_start {
            timings.extract_clusters = s.elapsed();
        }
    }

    // Mermaid's flowchart-v2 renderer inserts node DOM elements in `graph.nodes()` order before
    // running Dagre layout, including for recursively extracted cluster graphs. Capture that
    // insertion order per root so the headless SVG matches strict DOM expectations.
    let mut dom_node_order_by_root: std::collections::HashMap<String, Vec<String>> =
        std::collections::HashMap::new();
    let dom_order_start = timing_enabled.then(std::time::Instant::now);
    dom_node_order_by_root.insert(String::new(), g.node_ids());
    for (id, cg) in &extracted_graphs {
        dom_node_order_by_root.insert(id.clone(), cg.node_ids());
    }
    if let Some(s) = dom_order_start {
        timings.dom_order = s.elapsed();
    }

    type Rect = merman_core::geom::Box2;

    struct ClusterTitleMetricsContext<'a> {
        subgraphs_by_id: &'a std::collections::HashMap<String, FlowSubgraph>,
        measurer: &'a dyn TextMeasurer,
        text_style: &'a TextStyle,
        html_label_text_style: &'a TextStyle,
        title_wrapping_width: f64,
        wrap_mode: WrapMode,
        config: &'a MermaidConfig,
        math_renderer: Option<&'a (dyn MathRenderer + Send + Sync)>,
    }

    fn cluster_title_metrics_for_layout(
        id: &str,
        ctx: &ClusterTitleMetricsContext<'_>,
    ) -> Option<(f64, f64)> {
        let sg = ctx.subgraphs_by_id.get(id)?;
        let label_type = sg.label_type.as_deref().unwrap_or("text");
        let metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer: ctx.measurer,
            raw_label: &sg.title,
            label_type,
            style: if ctx.wrap_mode == WrapMode::HtmlLike {
                ctx.html_label_text_style
            } else {
                ctx.text_style
            },
            max_width_px: Some(ctx.title_wrapping_width),
            wrap_mode: ctx.wrap_mode,
            config: ctx.config,
            math_renderer: ctx.math_renderer,
            preserve_string_whitespace_height: false,
        });
        Some((metrics.width.max(1.0), metrics.height.max(1.0)))
    }

    fn extracted_graph_bbox_rect(
        g: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
        title_total_margin: f64,
        extracted: &std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
        subgraph_id_set: &std::collections::HashSet<String>,
        title_metrics_ctx: &ClusterTitleMetricsContext<'_>,
        cluster_padding: f64,
    ) -> Option<Rect> {
        fn graph_content_rect(
            g: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
            extracted: &std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
            subgraph_id_set: &std::collections::HashSet<String>,
            title_total_margin: f64,
            title_metrics_ctx: &ClusterTitleMetricsContext<'_>,
            cluster_padding: f64,
        ) -> Option<Rect> {
            let mut out: Option<Rect> = None;
            for id in g.node_ids() {
                let Some(n) = g.node(&id) else { continue };
                let (Some(x), Some(y)) = (n.x, n.y) else {
                    continue;
                };
                let mut width = n.width;
                let mut height = n.height;
                let is_cluster_node = extracted.contains_key(&id) && g.children(&id).is_empty();
                let is_non_recursive_cluster =
                    subgraph_id_set.contains(&id) && !g.children(&id).is_empty();

                // Mermaid increases cluster node height by `subGraphTitleTotalMargin` *after* Dagre
                // layout (just before rendering), and `updateNodeBounds(...)` measures the DOM
                // bbox after that expansion. Mirror that here for non-recursive clusters.
                //
                // For leaf clusterNodes (recursively rendered clusters), the node's width/height
                // comes directly from `updateNodeBounds(...)`, so do not add margins again.
                if !is_cluster_node && is_non_recursive_cluster {
                    if title_total_margin > 0.0 {
                        height = (height + title_total_margin).max(1.0);
                    }
                    if let Some((title_w, title_h)) =
                        cluster_title_metrics_for_layout(&id, title_metrics_ctx)
                    {
                        width = width.max(title_w + cluster_padding);
                        height = height.max(title_h + title_total_margin);
                    }
                }

                let r = Rect::from_center(x, y, width, height);
                if let Some(ref mut cur) = out {
                    cur.union(r);
                } else {
                    out = Some(r);
                }
            }
            for ek in g.edge_keys() {
                let Some(e) = g.edge_by_key(&ek) else {
                    continue;
                };
                let (Some(x), Some(y)) = (e.x, e.y) else {
                    continue;
                };
                if e.width <= 0.0 && e.height <= 0.0 {
                    continue;
                }
                let r = Rect::from_center(x, y, e.width, e.height);
                if let Some(ref mut cur) = out {
                    cur.union(r);
                } else {
                    out = Some(r);
                }
            }
            out
        }

        graph_content_rect(
            g,
            extracted,
            subgraph_id_set,
            title_total_margin,
            title_metrics_ctx,
            cluster_padding,
        )
    }

    fn apply_mermaid_subgraph_title_shifts(
        graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
        extracted: &std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
        subgraph_id_set: &std::collections::HashSet<String>,
        y_shift: f64,
    ) {
        if y_shift.abs() < 1e-9 {
            return;
        }

        // Mermaid v11.12.2 adjusts Y positions after Dagre layout:
        // - regular nodes: +subGraphTitleTotalMargin/2
        // - clusterNode nodes (recursively rendered clusters): +subGraphTitleTotalMargin
        // - pure cluster nodes (non-recursive clusters): no y-shift (but height grows elsewhere)
        for id in graph.node_ids() {
            // A cluster is only a Mermaid "clusterNode" placeholder if it is a leaf in the
            // current graph. Extracted graphs contain an injected parent cluster node with the
            // same id (and children), which must follow the pure-cluster path.
            let is_cluster_node = extracted.contains_key(&id) && graph.children(&id).is_empty();
            let delta_y = if is_cluster_node {
                y_shift * 2.0
            } else if subgraph_id_set.contains(&id) && !graph.children(&id).is_empty() {
                0.0
            } else {
                y_shift
            };
            if delta_y.abs() > 1e-9 {
                let Some(y) = graph.node(&id).and_then(|n| n.y) else {
                    continue;
                };
                if let Some(n) = graph.node_mut(&id) {
                    n.y = Some(y + delta_y);
                }
            }
        }

        // Mermaid shifts all edge points and the edge label position by +subGraphTitleTotalMargin/2.
        for ek in graph.edge_keys() {
            let Some(e) = graph.edge_mut_by_key(&ek) else {
                continue;
            };
            if let Some(y) = e.y {
                e.y = Some(y + y_shift);
            }
            for p in &mut e.points {
                p.y += y_shift;
            }
        }
    }

    struct RecursiveLayoutContext<'a> {
        extracted:
            &'a mut std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
        subgraph_id_set: &'a std::collections::HashSet<String>,
        y_shift: f64,
        cluster_node_labels: &'a std::collections::HashMap<String, NodeLabel>,
        title_total_margin: f64,
        title_metrics_ctx: &'a ClusterTitleMetricsContext<'a>,
        cluster_padding: f64,
        timings: &'a mut FlowchartLayoutTimings,
        timing_enabled: bool,
    }

    fn layout_graph_with_recursive_clusters(
        graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
        graph_cluster_id: Option<&str>,
        _depth: usize,
        ctx: &mut RecursiveLayoutContext<'_>,
    ) {
        #[derive(Clone)]
        struct LayoutFrame {
            cluster_id: Option<String>,
            expanded: bool,
        }

        fn recursive_child_ids(
            graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
            extracted: &std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
        ) -> Vec<String> {
            graph
                .node_ids()
                .into_iter()
                // Only recurse into extracted graphs for leaf cluster nodes ("clusterNode" in
                // Mermaid). Child graphs also get their parent cluster node injected, with
                // children, and must not recurse back into themselves.
                .filter(|id| graph.children(id).is_empty() && extracted.contains_key(id))
                .collect()
        }

        fn inject_parent_cluster(
            graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
            cluster_id: &str,
            ctx: &RecursiveLayoutContext<'_>,
        ) {
            if !graph.has_node(cluster_id) {
                let lbl = ctx
                    .cluster_node_labels
                    .get(cluster_id)
                    .cloned()
                    .unwrap_or_default();
                graph.set_node(cluster_id.to_string(), lbl);
            }
            let node_ids = graph.node_ids();
            for node_id in node_ids {
                if node_id == cluster_id {
                    continue;
                }
                if graph.parent(&node_id).is_none() {
                    graph.set_parent(node_id, cluster_id.to_string());
                }
            }
        }

        fn update_child_cluster_bounds(
            graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
            ctx: &RecursiveLayoutContext<'_>,
        ) {
            let ids = recursive_child_ids(graph, ctx.extracted);
            for id in ids {
                let Some(child) = ctx.extracted.get(&id) else {
                    continue;
                };

                // In Mermaid, `updateNodeBounds(...)` measures the recursively rendered `<g
                // class="root">` group. In that render path, the child graph contains a node
                // matching the cluster id (inserted via `graph.setNode(parentCluster.id, ...)`),
                // whose computed compound bounds correspond to the cluster box measured in the DOM.
                if let Some(r) = extracted_graph_bbox_rect(
                    child,
                    ctx.title_total_margin,
                    ctx.extracted,
                    ctx.subgraph_id_set,
                    ctx.title_metrics_ctx,
                    ctx.cluster_padding,
                ) {
                    if let Some(n) = graph.node_mut(&id) {
                        n.width = r.width().max(1.0);
                        n.height = r.height().max(1.0);
                    }
                } else if let Some(n_child) = child.node(&id) {
                    if let Some(n) = graph.node_mut(&id) {
                        n.width = n_child.width.max(1.0);
                        n.height = n_child.height.max(1.0);
                    }
                }
            }
        }

        fn layout_one_graph(
            graph: &mut Graph<NodeLabel, EdgeLabel, GraphLabel>,
            ctx: &mut RecursiveLayoutContext<'_>,
        ) {
            if ctx.timing_enabled {
                ctx.timings.dagre_calls += 1;
                let start = std::time::Instant::now();
                dugong::layout_dagreish(graph);
                ctx.timings.dagre_total += start.elapsed();
            } else {
                dugong::layout_dagreish(graph);
            }
            apply_mermaid_subgraph_title_shifts(
                graph,
                ctx.extracted,
                ctx.subgraph_id_set,
                ctx.y_shift,
            );
        }

        let mut stack = vec![LayoutFrame {
            cluster_id: graph_cluster_id.map(str::to_string),
            expanded: false,
        }];

        while let Some(frame) = stack.pop() {
            if !frame.expanded {
                let Some((child_ids, parent_nodesep, parent_ranksep)) = (match &frame.cluster_id {
                    Some(id) => ctx.extracted.get(id).map(|g| {
                        (
                            recursive_child_ids(g, ctx.extracted),
                            g.graph().nodesep,
                            g.graph().ranksep,
                        )
                    }),
                    None => Some((
                        recursive_child_ids(graph, ctx.extracted),
                        graph.graph().nodesep,
                        graph.graph().ranksep,
                    )),
                }) else {
                    continue;
                };

                stack.push(LayoutFrame {
                    cluster_id: frame.cluster_id,
                    expanded: true,
                });

                for child_id in child_ids.iter().rev() {
                    // Match Mermaid `recursiveRender` behavior: before laying out a recursively
                    // rendered cluster graph, override `nodesep` to the parent graph spacing and
                    // `ranksep` to `parent.ranksep + 25`. This compounds for nested recursive
                    // clusters.
                    if let Some(child) = ctx.extracted.get_mut(child_id) {
                        child.graph_mut().nodesep = parent_nodesep;
                        child.graph_mut().ranksep = parent_ranksep + 25.0;
                    }
                    stack.push(LayoutFrame {
                        cluster_id: Some(child_id.clone()),
                        expanded: false,
                    });
                }
                continue;
            }

            if let Some(cluster_id) = frame.cluster_id {
                let Some(mut current) = ctx.extracted.remove(&cluster_id) else {
                    continue;
                };
                update_child_cluster_bounds(&mut current, ctx);
                inject_parent_cluster(&mut current, &cluster_id, ctx);
                layout_one_graph(&mut current, ctx);
                ctx.extracted.insert(cluster_id, current);
            } else {
                update_child_cluster_bounds(graph, ctx);
                layout_one_graph(graph, ctx);
            }
        }
    }

    let layout_start = timing_enabled.then(std::time::Instant::now);
    {
        let title_metrics_ctx = ClusterTitleMetricsContext {
            subgraphs_by_id: &subgraphs_by_id,
            measurer,
            text_style: &text_style,
            html_label_text_style: &html_label_text_style,
            title_wrapping_width: cluster_title_wrapping_width,
            wrap_mode: cluster_wrap_mode,
            config: effective_config,
            math_renderer,
        };
        let mut recursive_layout_ctx = RecursiveLayoutContext {
            extracted: &mut extracted_graphs,
            subgraph_id_set: &subgraph_id_set,
            y_shift,
            cluster_node_labels: &cluster_node_labels,
            title_total_margin,
            title_metrics_ctx: &title_metrics_ctx,
            cluster_padding,
            timings: &mut timings,
            timing_enabled,
        };
        layout_graph_with_recursive_clusters(&mut g, None, 0, &mut recursive_layout_ctx);
    }
    if let Some(s) = layout_start {
        timings.layout_recursive = s.elapsed();
    }

    let mut leaf_rects: std::collections::HashMap<String, Rect> = std::collections::HashMap::new();
    let mut base_pos: std::collections::HashMap<String, (f64, f64)> =
        std::collections::HashMap::new();
    let mut edge_override_points: std::collections::HashMap<String, Vec<LayoutPoint>> =
        std::collections::HashMap::new();
    let mut edge_override_label: std::collections::HashMap<String, Option<LayoutLabel>> =
        std::collections::HashMap::new();
    let mut edge_override_from_cluster: std::collections::HashMap<String, Option<String>> =
        std::collections::HashMap::new();
    let mut edge_override_to_cluster: std::collections::HashMap<String, Option<String>> =
        std::collections::HashMap::new();
    let mut leaf_node_ids: std::collections::HashSet<String> = model
        .nodes
        .iter()
        .filter(|n| !subgraph_ids.contains(n.id.as_str()))
        .map(|n| n.id.clone())
        .collect();
    for id in &self_loop_label_node_ids {
        leaf_node_ids.insert(id.clone());
    }
    for id in &empty_subgraph_ids {
        leaf_node_ids.insert(id.clone());
    }

    struct PlaceGraphInputs<'a> {
        edge_id_by_key: &'a std::collections::HashMap<String, String>,
        extracted_graphs:
            &'a std::collections::HashMap<String, Graph<NodeLabel, EdgeLabel, GraphLabel>>,
        subgraph_ids: &'a std::collections::HashSet<&'a str>,
        leaf_node_ids: &'a std::collections::HashSet<String>,
    }

    struct PlaceGraphOutputs<'a> {
        base_pos: &'a mut std::collections::HashMap<String, (f64, f64)>,
        leaf_rects: &'a mut std::collections::HashMap<String, Rect>,
        cluster_rects_from_graph: &'a mut std::collections::HashMap<String, Rect>,
        extracted_cluster_rects: &'a mut std::collections::HashMap<String, Rect>,
        extracted_cluster_base_widths: &'a mut std::collections::HashMap<String, f64>,
        edge_override_points: &'a mut std::collections::HashMap<String, Vec<LayoutPoint>>,
        edge_override_label: &'a mut std::collections::HashMap<String, Option<LayoutLabel>>,
        edge_override_from_cluster: &'a mut std::collections::HashMap<String, Option<String>>,
        edge_override_to_cluster: &'a mut std::collections::HashMap<String, Option<String>>,
    }

    fn place_graph(
        graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
        offset: (f64, f64),
        is_root: bool,
        inputs: &PlaceGraphInputs<'_>,
        out: &mut PlaceGraphOutputs<'_>,
    ) {
        for id in graph.node_ids() {
            let Some(n) = graph.node(&id) else { continue };
            let x = n.x.unwrap_or(0.0) + offset.0;
            let y = n.y.unwrap_or(0.0) + offset.1;
            if inputs.leaf_node_ids.contains(&id) {
                out.base_pos.insert(id.clone(), (x, y));
                out.leaf_rects
                    .insert(id.clone(), Rect::from_center(x, y, n.width, n.height));
                continue;
            }
        }

        fn subtree_rect(
            graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
            id: &str,
            visiting: &mut std::collections::HashSet<String>,
        ) -> Option<Rect> {
            if !visiting.insert(id.to_string()) {
                return None;
            }
            let mut out: Option<Rect> = None;
            for child in graph.children(id) {
                if let Some(n) = graph.node(child) {
                    if let (Some(x), Some(y)) = (n.x, n.y) {
                        let r = Rect::from_center(x, y, n.width, n.height);
                        if let Some(ref mut cur) = out {
                            cur.union(r);
                        } else {
                            out = Some(r);
                        }
                    }
                }
                if !graph.children(child).is_empty() {
                    if let Some(r) = subtree_rect(graph, child, visiting) {
                        if let Some(ref mut cur) = out {
                            cur.union(r);
                        } else {
                            out = Some(r);
                        }
                    }
                }
            }
            visiting.remove(id);
            out
        }

        // Capture the layout-computed compound bounds for non-extracted clusters.
        //
        // Upstream Dagre computes compound-node geometry from border nodes and then removes the
        // border dummy nodes (`removeBorderNodes`). Our dugong parity pipeline mirrors that, so
        // prefer the compound node's own x/y/width/height when available.
        for id in graph.node_ids() {
            if !inputs.subgraph_ids.contains(id.as_str()) {
                continue;
            }
            if inputs.extracted_graphs.contains_key(&id) {
                continue;
            }
            if out.cluster_rects_from_graph.contains_key(&id) {
                continue;
            }
            if let Some(n) = graph.node(&id) {
                if let (Some(x), Some(y)) = (n.x, n.y) {
                    if n.width > 0.0 && n.height > 0.0 {
                        let mut r = Rect::from_center(x, y, n.width, n.height);
                        r.translate(offset.0, offset.1);
                        out.cluster_rects_from_graph.insert(id, r);
                        continue;
                    }
                }
            }

            let mut visiting: std::collections::HashSet<String> = std::collections::HashSet::new();
            let Some(mut r) = subtree_rect(graph, &id, &mut visiting) else {
                continue;
            };
            r.translate(offset.0, offset.1);
            out.cluster_rects_from_graph.insert(id, r);
        }

        for ek in graph.edge_keys() {
            let Some(edge_key) = ek.name.as_deref() else {
                continue;
            };
            let edge_id = inputs
                .edge_id_by_key
                .get(edge_key)
                .map(String::as_str)
                .unwrap_or(edge_key);
            let Some(lbl) = graph.edge_by_key(&ek) else {
                continue;
            };

            if let (Some(x), Some(y)) = (lbl.x, lbl.y) {
                if lbl.width > 0.0 || lbl.height > 0.0 {
                    let lx = x + offset.0;
                    let ly = y + offset.1;
                    let leaf_id = format!("edge-label::{edge_id}");
                    out.base_pos.insert(leaf_id.clone(), (lx, ly));
                    out.leaf_rects
                        .insert(leaf_id, Rect::from_center(lx, ly, lbl.width, lbl.height));
                }
            }

            if !is_root {
                let points = lbl
                    .points
                    .iter()
                    .map(|p| LayoutPoint {
                        x: p.x + offset.0,
                        y: p.y + offset.1,
                    })
                    .collect::<Vec<_>>();
                let label_pos = match (lbl.x, lbl.y) {
                    (Some(x), Some(y)) if lbl.width > 0.0 || lbl.height > 0.0 => {
                        Some(LayoutLabel {
                            x: x + offset.0,
                            y: y + offset.1,
                            width: lbl.width,
                            height: lbl.height,
                        })
                    }
                    _ => None,
                };
                out.edge_override_points.insert(edge_id.to_string(), points);
                out.edge_override_label
                    .insert(edge_id.to_string(), label_pos);
                let from_cluster = lbl
                    .extras
                    .get("fromCluster")
                    .and_then(|v| v.as_str().map(|s| s.to_string()));
                let to_cluster = lbl
                    .extras
                    .get("toCluster")
                    .and_then(|v| v.as_str().map(|s| s.to_string()));
                out.edge_override_from_cluster
                    .insert(edge_id.to_string(), from_cluster);
                out.edge_override_to_cluster
                    .insert(edge_id.to_string(), to_cluster);
            }
        }

        for id in graph.node_ids() {
            // Only recurse into extracted graphs for leaf cluster nodes ("clusterNode" in Mermaid).
            // The recursively rendered graph itself also contains a node with the same id (the
            // parent cluster node injected before layout), which has children and must not recurse.
            if !graph.children(&id).is_empty() {
                continue;
            }
            let Some(child) = inputs.extracted_graphs.get(&id) else {
                continue;
            };
            let Some(n) = graph.node(&id) else {
                continue;
            };
            let (Some(px), Some(py)) = (n.x, n.y) else {
                continue;
            };
            let parent_x = px + offset.0;
            let parent_y = py + offset.1;
            let Some(cnode) = child.node(&id) else {
                continue;
            };
            let (Some(cx), Some(cy)) = (cnode.x, cnode.y) else {
                continue;
            };
            let child_offset = (parent_x - cx, parent_y - cy);
            // The extracted cluster's footprint in the parent graph is the clusterNode itself.
            // Our recursive layout step updates the parent graph's node `width/height` to match
            // Mermaid's `updateNodeBounds(...)` behavior (including any title margin). Avoid
            // adding `title_total_margin` again here.
            let r = Rect::from_center(parent_x, parent_y, n.width, n.height);
            out.extracted_cluster_rects.insert(id.clone(), r);
            out.extracted_cluster_base_widths
                .insert(id.clone(), cnode.width.max(1.0));
            place_graph(child, child_offset, false, inputs, out);
        }
    }

    let mut cluster_rects_from_graph: std::collections::HashMap<String, Rect> =
        std::collections::HashMap::new();
    let mut extracted_cluster_rects: std::collections::HashMap<String, Rect> =
        std::collections::HashMap::new();
    let mut extracted_cluster_base_widths: std::collections::HashMap<String, f64> =
        std::collections::HashMap::new();
    let place_start = timing_enabled.then(std::time::Instant::now);
    {
        let place_graph_inputs = PlaceGraphInputs {
            edge_id_by_key: &edge_id_by_key,
            extracted_graphs: &extracted_graphs,
            subgraph_ids: &subgraph_ids,
            leaf_node_ids: &leaf_node_ids,
        };
        let mut place_graph_outputs = PlaceGraphOutputs {
            base_pos: &mut base_pos,
            leaf_rects: &mut leaf_rects,
            cluster_rects_from_graph: &mut cluster_rects_from_graph,
            extracted_cluster_rects: &mut extracted_cluster_rects,
            extracted_cluster_base_widths: &mut extracted_cluster_base_widths,
            edge_override_points: &mut edge_override_points,
            edge_override_label: &mut edge_override_label,
            edge_override_from_cluster: &mut edge_override_from_cluster,
            edge_override_to_cluster: &mut edge_override_to_cluster,
        };
        place_graph(
            &g,
            (0.0, 0.0),
            true,
            &place_graph_inputs,
            &mut place_graph_outputs,
        );
    }
    if let Some(s) = place_start {
        timings.place_graph = s.elapsed();
    }

    let build_output_start = timing_enabled.then(std::time::Instant::now);

    let mut extra_children: std::collections::HashMap<String, Vec<String>> =
        std::collections::HashMap::new();
    let labeled_edges: std::collections::HashSet<&str> = render_edges
        .iter()
        .filter(|e| edge_label_is_non_empty(e))
        .map(|e| e.id.as_str())
        .collect();

    fn collect_extra_children(
        graph: &Graph<NodeLabel, EdgeLabel, GraphLabel>,
        edge_id_by_key: &std::collections::HashMap<String, String>,
        labeled_edges: &std::collections::HashSet<&str>,
        implicit_root: Option<&str>,
        out: &mut std::collections::HashMap<String, Vec<String>>,
    ) {
        for ek in graph.edge_keys() {
            let Some(edge_key) = ek.name.as_deref() else {
                continue;
            };
            let edge_id = edge_id_by_key
                .get(edge_key)
                .map(String::as_str)
                .unwrap_or(edge_key);
            if !labeled_edges.contains(edge_id) {
                continue;
            }
            // Mermaid's recursive cluster extractor removes the root cluster node from the
            // extracted graph. In that case, the "lowest common parent" of edges whose endpoints
            // belong to the extracted cluster becomes `None`, even though the label should still
            // participate in the extracted cluster's bounding box. Use `implicit_root` to map
            // those labels back to the extracted cluster id.
            let parent = lowest_common_parent(graph, &ek.v, &ek.w)
                .or_else(|| implicit_root.map(|s| s.to_string()));
            let Some(parent) = parent else {
                continue;
            };
            out.entry(parent)
                .or_default()
                .push(format!("edge-label::{edge_id}"));
        }
    }

    collect_extra_children(
        &g,
        &edge_id_by_key,
        &labeled_edges,
        None,
        &mut extra_children,
    );
    for (cluster_id, cg) in &extracted_graphs {
        collect_extra_children(
            cg,
            &edge_id_by_key,
            &labeled_edges,
            Some(cluster_id.as_str()),
            &mut extra_children,
        );
    }

    // Ensure Mermaid-style self-loop helper nodes participate in cluster bounding/packing.
    // These nodes are not part of the semantic `subgraph ... end` membership list, but are
    // parented into the same clusters as their base node.
    for id in &self_loop_label_node_ids {
        if let Some(p) = g.parent(id) {
            extra_children
                .entry(p.to_string())
                .or_default()
                .push(id.clone());
        }
    }

    let mut out_nodes: Vec<LayoutNode> = Vec::new();
    for n in &model.nodes {
        if subgraph_ids.contains(n.id.as_str()) {
            continue;
        }
        let (x, y) = base_pos
            .get(&n.id)
            .copied()
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing positioned node {}", n.id),
            })?;
        let (width, height) = leaf_rects
            .get(&n.id)
            .map(|r| (r.width(), r.height()))
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing sized node {}", n.id),
            })?;
        out_nodes.push(LayoutNode {
            id: n.id.clone(),
            x,
            y,
            width,
            height,
            is_cluster: false,
            label_width: leaf_label_metrics_by_id.get(&n.id).map(|v| v.0),
            label_height: leaf_label_metrics_by_id.get(&n.id).map(|v| v.1),
        });
    }
    for id in &empty_subgraph_ids {
        let (x, y) = base_pos
            .get(id)
            .copied()
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing positioned node {id}"),
            })?;
        let (width, height) = leaf_rects
            .get(id)
            .map(|r| (r.width(), r.height()))
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing sized node {id}"),
            })?;
        out_nodes.push(LayoutNode {
            id: id.clone(),
            x,
            y,
            width,
            height,
            is_cluster: false,
            label_width: leaf_label_metrics_by_id.get(id).map(|v| v.0),
            label_height: leaf_label_metrics_by_id.get(id).map(|v| v.1),
        });
    }
    for id in &self_loop_label_node_ids {
        let (x, y) = base_pos
            .get(id)
            .copied()
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing positioned node {id}"),
            })?;
        let (width, height) = leaf_rects
            .get(id)
            .map(|r| (r.width(), r.height()))
            .ok_or_else(|| Error::InvalidModel {
                message: format!("missing sized node {id}"),
            })?;
        out_nodes.push(LayoutNode {
            id: id.clone(),
            x,
            y,
            width,
            height,
            is_cluster: false,
            label_width: None,
            label_height: None,
        });
    }

    let mut clusters: Vec<LayoutCluster> = Vec::new();

    let mut cluster_rects: std::collections::HashMap<String, Rect> =
        std::collections::HashMap::new();
    let mut cluster_base_widths: std::collections::HashMap<String, f64> =
        std::collections::HashMap::new();
    let mut visiting: std::collections::HashSet<String> = std::collections::HashSet::new();

    struct ClusterRectContext<'a> {
        subgraphs_by_id: &'a std::collections::HashMap<String, FlowSubgraph>,
        leaf_rects: &'a std::collections::HashMap<String, Rect>,
        extra_children: &'a std::collections::HashMap<String, Vec<String>>,
        measurer: &'a dyn TextMeasurer,
        text_style: &'a TextStyle,
        html_label_text_style: &'a TextStyle,
        title_wrapping_width: f64,
        wrap_mode: WrapMode,
        config: &'a MermaidConfig,
        math_renderer: Option<&'a (dyn MathRenderer + Send + Sync)>,
        cluster_padding: f64,
        title_total_margin: f64,
    }

    struct ClusterRectState<'a> {
        cluster_rects: &'a mut std::collections::HashMap<String, Rect>,
        cluster_base_widths: &'a mut std::collections::HashMap<String, f64>,
        visiting: &'a mut std::collections::HashSet<String>,
    }

    fn compute_cluster_rect(
        id: &str,
        ctx: &ClusterRectContext<'_>,
        state: &mut ClusterRectState<'_>,
    ) -> Result<(Rect, f64)> {
        if let Some(r) = state.cluster_rects.get(id).copied() {
            let base_width = state
                .cluster_base_widths
                .get(id)
                .copied()
                .unwrap_or_else(|| r.width());
            return Ok((r, base_width));
        }
        if !state.visiting.insert(id.to_string()) {
            return Err(Error::InvalidModel {
                message: format!("cycle in subgraph membership involving {id}"),
            });
        }

        let Some(sg) = ctx.subgraphs_by_id.get(id) else {
            return Err(Error::InvalidModel {
                message: format!("missing subgraph definition for {id}"),
            });
        };

        let mut content: Option<Rect> = None;
        for member in &sg.nodes {
            let member_rect = if let Some(r) = ctx.leaf_rects.get(member).copied() {
                Some(r)
            } else if ctx.subgraphs_by_id.contains_key(member) {
                Some(compute_cluster_rect(member, ctx, state)?.0)
            } else {
                None
            };

            if let Some(r) = member_rect {
                if let Some(ref mut cur) = content {
                    cur.union(r);
                } else {
                    content = Some(r);
                }
            }
        }

        if let Some(extra) = ctx.extra_children.get(id) {
            for child in extra {
                if let Some(r) = ctx.leaf_rects.get(child).copied() {
                    if let Some(ref mut cur) = content {
                        cur.union(r);
                    } else {
                        content = Some(r);
                    }
                }
            }
        }

        let label_type = sg.label_type.as_deref().unwrap_or("text");
        let title_width_limit = Some(ctx.title_wrapping_width);
        let title_metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer: ctx.measurer,
            raw_label: &sg.title,
            label_type,
            style: if ctx.wrap_mode == WrapMode::HtmlLike {
                ctx.html_label_text_style
            } else {
                ctx.text_style
            },
            max_width_px: title_width_limit,
            wrap_mode: ctx.wrap_mode,
            config: ctx.config,
            math_renderer: ctx.math_renderer,
            preserve_string_whitespace_height: false,
        });
        let mut rect = if let Some(r) = content {
            r
        } else {
            Rect::from_center(
                0.0,
                0.0,
                title_metrics.width.max(1.0),
                title_metrics.height.max(1.0),
            )
        };

        // Expand to provide the cluster's internal padding.
        rect.pad(ctx.cluster_padding);

        // Mermaid computes `node.diff` using the pre-widened layout node width, then may widen the
        // rect to fit the label bbox during rendering.
        let base_width = rect.width();

        // Mermaid cluster "rect" rendering widens to fit the raw title bbox, plus a small
        // horizontal inset. Empirically (Mermaid@11.12.2 fixtures), this behaves like
        // `title_width + cluster_padding` when the title is wider than the content.
        let min_width = title_metrics.width.max(1.0) + ctx.cluster_padding;
        if rect.width() < min_width {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, min_width, rect.height());
        }

        // Extend height to reserve space for subgraph title margins (Mermaid does this after layout).
        if ctx.title_total_margin > 0.0 {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, rect.width(), rect.height() + ctx.title_total_margin);
        }

        // Keep the cluster tall enough to accommodate the title bbox if needed.
        let min_height = title_metrics.height.max(1.0) + ctx.title_total_margin;
        if rect.height() < min_height {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, rect.width(), min_height);
        }

        state.visiting.remove(id);
        state.cluster_rects.insert(id.to_string(), rect);
        state.cluster_base_widths.insert(id.to_string(), base_width);
        Ok((rect, base_width))
    }

    struct ClusterTitleAdjustContext<'a> {
        measurer: &'a dyn TextMeasurer,
        text_style: &'a TextStyle,
        html_label_text_style: &'a TextStyle,
        title_wrapping_width: f64,
        wrap_mode: WrapMode,
        config: &'a MermaidConfig,
        math_renderer: Option<&'a (dyn MathRenderer + Send + Sync)>,
        title_total_margin: f64,
        cluster_padding: f64,
    }

    fn adjust_cluster_rect_for_title(
        mut rect: Rect,
        title: &str,
        label_type: &str,
        add_title_total_margin: bool,
        ctx: &ClusterTitleAdjustContext<'_>,
    ) -> Rect {
        let title_width_limit = Some(ctx.title_wrapping_width);
        let title_metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer: ctx.measurer,
            raw_label: title,
            label_type,
            style: if ctx.wrap_mode == WrapMode::HtmlLike {
                ctx.html_label_text_style
            } else {
                ctx.text_style
            },
            max_width_px: title_width_limit,
            wrap_mode: ctx.wrap_mode,
            config: ctx.config,
            math_renderer: ctx.math_renderer,
            preserve_string_whitespace_height: false,
        });
        let title_w = title_metrics.width.max(1.0);
        let title_h = title_metrics.height.max(1.0);

        // Mermaid cluster "rect" widens to fit the raw title bbox (no added padding),
        // even when the cluster bounds come from Dagre border nodes.
        let min_w = title_w + ctx.cluster_padding;
        if rect.width() < min_w {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, min_w, rect.height());
        }

        // Mermaid adds `subGraphTitleTotalMargin` to cluster height after layout.
        if add_title_total_margin && ctx.title_total_margin > 0.0 {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, rect.width(), rect.height() + ctx.title_total_margin);
        }

        // Keep the cluster tall enough for the title bbox (including title margins).
        let min_h = title_h + ctx.title_total_margin;
        if rect.height() < min_h {
            let (cx, cy) = rect.center();
            rect = Rect::from_center(cx, cy, rect.width(), min_h);
        }

        rect
    }

    let cluster_rect_ctx = ClusterRectContext {
        subgraphs_by_id: &subgraphs_by_id,
        leaf_rects: &leaf_rects,
        extra_children: &extra_children,
        measurer,
        text_style: &text_style,
        html_label_text_style: &html_label_text_style,
        title_wrapping_width: cluster_title_wrapping_width,
        wrap_mode: cluster_wrap_mode,
        config: effective_config,
        math_renderer,
        cluster_padding,
        title_total_margin,
    };
    let mut cluster_rect_state = ClusterRectState {
        cluster_rects: &mut cluster_rects,
        cluster_base_widths: &mut cluster_base_widths,
        visiting: &mut visiting,
    };
    let title_adjust_ctx = ClusterTitleAdjustContext {
        measurer,
        text_style: &text_style,
        html_label_text_style: &html_label_text_style,
        title_wrapping_width: cluster_title_wrapping_width,
        wrap_mode: cluster_wrap_mode,
        config: effective_config,
        math_renderer,
        title_total_margin,
        cluster_padding,
    };

    for sg in &model.subgraphs {
        if sg.nodes.is_empty() {
            continue;
        }

        let (rect, base_width) = if extracted_graphs.contains_key(&sg.id) {
            // For extracted (recursive) clusters, match Mermaid's `updateNodeBounds(...)` intent by
            // taking the rendered child-graph content bbox (including border nodes) as the cluster
            // node's bounds.
            let rect = extracted_cluster_rects
                .get(&sg.id)
                .copied()
                .unwrap_or_else(|| {
                    compute_cluster_rect(&sg.id, &cluster_rect_ctx, &mut cluster_rect_state)
                        .map(|v| v.0)
                        .unwrap_or_else(|_| Rect::from_center(0.0, 0.0, 1.0, 1.0))
                });
            let base_width = extracted_cluster_base_widths
                .get(&sg.id)
                .copied()
                .unwrap_or_else(|| rect.width());
            let rect = adjust_cluster_rect_for_title(
                rect,
                &sg.title,
                sg.label_type.as_deref().unwrap_or("text"),
                false,
                &title_adjust_ctx,
            );
            (rect, base_width)
        } else if let Some(r) = cluster_rects_from_graph.get(&sg.id).copied() {
            let base_width = r.width();
            let rect = adjust_cluster_rect_for_title(
                r,
                &sg.title,
                sg.label_type.as_deref().unwrap_or("text"),
                true,
                &title_adjust_ctx,
            );
            (rect, base_width)
        } else {
            compute_cluster_rect(&sg.id, &cluster_rect_ctx, &mut cluster_rect_state)?
        };
        let (cx, cy) = rect.center();

        let label_type = sg.label_type.as_deref().unwrap_or("text");
        let title_width_limit = Some(cluster_title_wrapping_width);
        let mut title_metrics = flowchart_label_metrics_for_layout(FlowchartLabelMetricsRequest {
            measurer,
            raw_label: &sg.title,
            label_type,
            style: if cluster_wrap_mode == WrapMode::HtmlLike {
                &html_label_text_style
            } else {
                &text_style
            },
            max_width_px: title_width_limit,
            wrap_mode: cluster_wrap_mode,
            config: effective_config,
            math_renderer,
            preserve_string_whitespace_height: false,
        });
        if cluster_wrap_mode == crate::text::WrapMode::SvgLike && label_type != "markdown" {
            // Mermaid's flowchart cluster titles rendered as plain SVG `<text>` are measured via
            // `getComputedTextLength()` on the emitted wrapped lines rather than the raw title.
            // Using the raw unwrapped line makes long-word SVG-like subgraph titles pull root
            // bounds far to the left even though Mermaid emits a wrapped `<tspan>` stack.
            let plain = crate::flowchart::flowchart_label_plain_text_for_layout(
                &sg.title, label_type, false,
            );
            title_metrics.width = flowchart_svg_plain_computed_width_px(
                measurer,
                &plain,
                &text_style,
                title_width_limit,
            );
        } else if cluster_wrap_mode == crate::text::WrapMode::SvgLike && label_type == "markdown" {
            // Cluster titles with markdown emphasis are rendered as SVG `<text>/<tspan>` runs and
            // measured via browser `getBBox()` in upstream Mermaid. For italic `<em>` titles, the
            // 1/64px-snapped markdown width can be just enough to shift the left-aligned label
            // transform across a strict-XML rounding boundary; use a tighter lattice width probe.
            let has_emphasis = crate::text::mermaid_markdown_to_wrapped_word_lines(
                measurer,
                &sg.title,
                &text_style,
                title_width_limit,
                cluster_wrap_mode,
            )
            .iter()
            .any(|line| {
                line.iter()
                    .any(|(_, ty)| *ty == crate::text::MermaidMarkdownWordType::Em)
            });
            if has_emphasis {
                title_metrics.width = crate::text::measure_markdown_svg_like_precise_width_px(
                    measurer,
                    &sg.title,
                    &text_style,
                    title_width_limit,
                );
            }
        }
        let title_label = LayoutLabel {
            x: cx,
            y: cy - rect.height() / 2.0 + title_margin_top + title_metrics.height / 2.0,
            width: title_metrics.width,
            height: title_metrics.height,
        };

        // `dagre-wrapper/clusters.js` (shape `rect`) sets `padding = 0 * node.padding`.
        // The cluster label is positioned at `node.x - bbox.width/2`, and `node.diff` is:
        // - `(bbox.width - node.width)/2 - node.padding/2` when the box widens to fit the title
        // - otherwise `-node.padding/2`.
        let title_w = title_metrics.width.max(1.0);
        let diff = if base_width <= title_w {
            (title_w - base_width) / 2.0 - cluster_padding / 2.0
        } else {
            -cluster_padding / 2.0
        };
        let offset_y = title_metrics.height - cluster_padding / 2.0;

        let effective_dir = effective_dir_by_id
            .get(&sg.id)
            .cloned()
            .unwrap_or_else(|| effective_cluster_dir(sg, &diagram_direction, inherit_dir));

        clusters.push(LayoutCluster {
            id: sg.id.clone(),
            x: cx,
            y: cy,
            width: rect.width(),
            height: rect.height(),
            diff,
            offset_y,
            title: sg.title.clone(),
            title_label,
            requested_dir: sg.dir.as_ref().map(|s| normalize_dir(s)),
            effective_dir,
            padding: cluster_padding,
            title_margin_top,
            title_margin_bottom,
        });

        out_nodes.push(LayoutNode {
            id: sg.id.clone(),
            x: cx,
            // Mermaid does not shift pure cluster nodes by `subGraphTitleTotalMargin / 2`.
            y: cy,
            width: rect.width(),
            height: rect.height(),
            is_cluster: true,
            label_width: None,
            label_height: None,
        });
    }
    clusters.sort_by(|a, b| a.id.cmp(&b.id));

    let mut out_edges: Vec<LayoutEdge> = Vec::new();
    for e in &render_edges {
        let (points, label_pos, mut from_cluster, mut to_cluster) =
            if let Some(points) = edge_override_points.get(&e.id) {
                let from_cluster = edge_override_from_cluster
                    .get(&e.id)
                    .cloned()
                    .unwrap_or(None);
                let to_cluster = edge_override_to_cluster.get(&e.id).cloned().unwrap_or(None);
                (
                    points.clone(),
                    edge_override_label.get(&e.id).cloned().unwrap_or(None),
                    from_cluster,
                    to_cluster,
                )
            } else {
                let (v, w) = edge_endpoints_by_id
                    .get(&e.id)
                    .cloned()
                    .unwrap_or_else(|| (e.from.clone(), e.to.clone()));
                let edge_key = edge_key_by_id
                    .get(&e.id)
                    .map(String::as_str)
                    .unwrap_or(e.id.as_str());
                let Some(label) = g.edge(&v, &w, Some(edge_key)) else {
                    return Err(Error::InvalidModel {
                        message: format!("missing layout edge {}", e.id),
                    });
                };
                let from_cluster = label
                    .extras
                    .get("fromCluster")
                    .and_then(|v| v.as_str().map(|s| s.to_string()));
                let to_cluster = label
                    .extras
                    .get("toCluster")
                    .and_then(|v| v.as_str().map(|s| s.to_string()));
                let points = label
                    .points
                    .iter()
                    .map(|p| LayoutPoint { x: p.x, y: p.y })
                    .collect::<Vec<_>>();
                let label_pos = match (label.x, label.y) {
                    (Some(x), Some(y)) if label.width > 0.0 || label.height > 0.0 => {
                        Some(LayoutLabel {
                            x,
                            y,
                            width: label.width,
                            height: label.height,
                        })
                    }
                    _ => None,
                };
                (points, label_pos, from_cluster, to_cluster)
            };

        // Match Mermaid's dagre adapter: self-loop special edges on group nodes are annotated with
        // `fromCluster` / `toCluster` so downstream renderers can clip routes to the cluster
        // boundary.
        if subgraph_ids.contains(e.from.as_str()) && e.id.ends_with("-cyclic-special-1") {
            from_cluster = Some(e.from.clone());
        }
        if subgraph_ids.contains(e.to.as_str()) && e.id.ends_with("-cyclic-special-2") {
            to_cluster = Some(e.to.clone());
        }

        out_edges.push(LayoutEdge {
            id: e.id.clone(),
            from: e.from.clone(),
            to: e.to.clone(),
            from_cluster,
            to_cluster,
            points,
            label: label_pos,
            start_label_left: None,
            start_label_right: None,
            end_label_left: None,
            end_label_right: None,
            start_marker: None,
            end_marker: None,
            stroke_dasharray: None,
        });
    }

    // Mermaid's flowchart renderer uses shape-specific intersection functions for edge endpoints
    // (e.g. diamond nodes). Our Dagre-ish layout currently treats all nodes as rectangles, so the
    // first/last points can land on the bounding box rather than the actual polygon boundary.
    //
    // Adjust the first/last edge points to match Mermaid's shape intersection behavior for the
    // shapes that materially differ from rectangles.
    let mut node_shape_by_id: HashMap<&str, &str> = HashMap::new();
    for n in &model.nodes {
        if let Some(s) = n.layout_shape.as_deref() {
            node_shape_by_id.insert(n.id.as_str(), s);
        }
    }
    let mut layout_node_by_id: HashMap<&str, &LayoutNode> = HashMap::new();
    for n in &out_nodes {
        layout_node_by_id.insert(n.id.as_str(), n);
    }

    fn diamond_intersection(node: &LayoutNode, toward: &LayoutPoint) -> Option<LayoutPoint> {
        let vx = toward.x - node.x;
        let vy = toward.y - node.y;
        if !(vx.is_finite() && vy.is_finite()) {
            return None;
        }
        if vx.abs() <= 1e-12 && vy.abs() <= 1e-12 {
            return None;
        }
        let hw = (node.width / 2.0).max(1e-9);
        let hh = (node.height / 2.0).max(1e-9);
        let denom = vx.abs() / hw + vy.abs() / hh;
        if !(denom.is_finite() && denom > 0.0) {
            return None;
        }
        let t = 1.0 / denom;
        Some(LayoutPoint {
            x: node.x + vx * t,
            y: node.y + vy * t,
        })
    }

    for e in &mut out_edges {
        if e.points.len() < 2 {
            continue;
        }

        if let Some(node) = layout_node_by_id.get(e.from.as_str()) {
            if !node.is_cluster {
                let shape = node_shape_by_id
                    .get(e.from.as_str())
                    .copied()
                    .unwrap_or("squareRect");
                if matches!(shape, "diamond" | "question" | "diam") {
                    if let Some(p) = diamond_intersection(node, &e.points[1]) {
                        e.points[0] = p;
                    }
                }
            }
        }
        if let Some(node) = layout_node_by_id.get(e.to.as_str()) {
            if !node.is_cluster {
                let shape = node_shape_by_id
                    .get(e.to.as_str())
                    .copied()
                    .unwrap_or("squareRect");
                if matches!(shape, "diamond" | "question" | "diam") {
                    let n = e.points.len();
                    if let Some(p) = diamond_intersection(node, &e.points[n - 2]) {
                        e.points[n - 1] = p;
                    }
                }
            }
        }
    }

    let bounds = compute_bounds(&out_nodes, &out_edges);

    if let Some(s) = build_output_start {
        timings.build_output = s.elapsed();
    }
    if let Some(s) = total_start {
        timings.total = s.elapsed();
        let dagre_overhead = timings
            .layout_recursive
            .checked_sub(timings.dagre_total)
            .unwrap_or_default();
        eprintln!(
            "[layout-timing] diagram=flowchart-v2 total={:?} deserialize={:?} expand_self_loops={:?} build_graph={:?} extract_clusters={:?} dom_order={:?} layout_recursive={:?} dagre_calls={} dagre_total={:?} dagre_overhead={:?} place_graph={:?} build_output={:?}",
            timings.total,
            timings.deserialize,
            timings.expand_self_loops,
            timings.build_graph,
            timings.extract_clusters,
            timings.dom_order,
            timings.layout_recursive,
            timings.dagre_calls,
            timings.dagre_total,
            dagre_overhead,
            timings.place_graph,
            timings.build_output,
        );
    }

    Ok(FlowchartV2Layout {
        nodes: out_nodes,
        edges: out_edges,
        clusters,
        bounds,
        dom_node_order_by_root,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::mpsc;
    use std::time::Duration;

    #[test]
    fn extract_descendants_handles_deeply_nested_subgraphs() {
        const DEPTH: usize = 100_000;
        let (tx, rx) = mpsc::channel();
        std::thread::Builder::new()
            .stack_size(512 * 1024)
            .spawn(move || {
                let mut g = Graph::new(GraphOptions {
                    compound: true,
                    ..Default::default()
                });
                for i in (0..DEPTH).rev() {
                    g.set_parent(format!("n{}", i + 1), format!("n{i}"));
                }
                let _ = tx.send(extract_descendants("n0", &g));
            })
            .unwrap();
        let descendants = rx
            .recv_timeout(Duration::from_secs(2))
            .expect("extract_descendants overflowed the stack on deep nesting");
        assert_eq!(descendants.len(), DEPTH);
    }
}