dagre 0.1.1

//! Cross-validation tests: compare dagre-rs output against dagre.js reference data.
//!
//! Reference data is generated by `cross-validate/generate_reference.mjs` which runs
//! dagre.js on a set of test graphs and saves the results as JSON.

use dagre::graph::{Graph, GraphOptions};
use dagre::layout::layout;
use dagre::layout::types::*;
use serde::Deserialize;
use std::collections::HashMap;

// Mirror types for the reference JSON. Some fields exist in the JSON for
// schema completeness (so a baseline regen failure surfaces a parse error
// rather than a silent shape change) but are not yet asserted against — keep
// them under `#[allow(dead_code)]` so future tests can read them without
// reinstating the struct.

#[derive(Deserialize, Debug)]
#[allow(dead_code)]
struct TestCase {
    name: String,
    opts: serde_json::Value,
    nodes: HashMap<String, RefNode>,
    edges: Vec<RefEdge>,
    graph: RefGraph,
}

#[derive(Deserialize, Debug)]
#[allow(dead_code)]
struct RefNode {
    x: f64,
    y: f64,
    // Cluster nodes with no children are never sized by dagre, so the
    // baseline JSON omits these fields entirely. Optional matches that.
    #[serde(default)]
    width: Option<f64>,
    #[serde(default)]
    height: Option<f64>,
    rank: Option<i32>,
    order: Option<usize>,
}

#[derive(Deserialize, Debug)]
#[allow(dead_code)]
struct RefEdge {
    v: String,
    w: String,
    points: Vec<RefPoint>,
    x: Option<f64>,
    y: Option<f64>,
}

#[derive(Deserialize, Debug)]
#[allow(dead_code)]
struct RefPoint {
    x: f64,
    y: f64,
}

#[derive(Deserialize, Debug)]
struct RefGraph {
    width: f64,
    height: f64,
}

/// Return node insertion order matching the JS reference generator.
fn get_node_order(name: &str) -> Vec<String> {
    let strs: Vec<&str> = match name {
        "single_node" => vec!["a"],
        "two_nodes" => vec!["a", "b"],
        "diamond" => vec!["a", "b", "c", "d"],
        "chain_5" => vec!["a", "b", "c", "d", "e"],
        "edge_label" => vec!["a", "b"],
        "cycle" => vec!["a", "b", "c"],
        "disconnected" => vec!["a", "b", "c", "d"],
        "lr_direction" | "bt_direction" | "rl_direction" => vec!["a", "b"],
        "custom_sep" => vec!["a", "b", "c"],
        "self_loop" => vec!["a", "b"],
        "long_edge" => vec!["a", "b", "c"],
        "fan_out" => vec!["root", "n0", "n1", "n2", "n3", "n4"],
        "margins" => vec!["a", "b"],
        "varied_sizes" => vec!["small", "medium", "large"],
        "parallel_edges" => vec!["a", "b"],
        "complex" => vec!["a", "b", "c", "d", "e", "f", "g", "h"],
        "compound" => vec!["a", "b", "c", "group"],
        "minlen" => vec!["a", "b"],
        // Compound bbox matrix (cases 21-30).
        "compound_single_leaf_tb" | "compound_single_leaf_lr" => vec!["a", "g"],
        "compound_chain_tb" | "compound_chain_lr" => vec!["a", "b", "c", "g"],
        "compound_nested_tb" | "compound_nested_lr" => {
            vec!["a", "b", "c", "inner", "outer"]
        }
        "compound_cross_cluster_tb" | "compound_cross_cluster_lr" => {
            vec!["a", "b", "g1", "g2"]
        }
        "compound_empty_inner" => vec!["a", "inner_empty", "outer"],
        "compound_fork_join" => vec!["a", "l", "r", "z", "g"],
        other => panic!("Unknown test case: {}", other),
    };
    strs.into_iter().map(|s| s.to_string()).collect()
}

#[derive(Deserialize, Debug)]
struct ReferenceFile {
    #[serde(default)]
    _meta: Option<ReferenceMeta>,
    cases: Vec<TestCase>,
}

#[derive(Deserialize, Debug)]
#[allow(dead_code)]
struct ReferenceMeta {
    upstream: String,
    version: String,
    commit: String,
    generated_at: Option<String>,
    generator: Option<String>,
    note: Option<String>,
}

fn load_reference() -> Vec<TestCase> {
    let data = include_str!("../cross-validate/reference_data.json");
    let file: ReferenceFile = serde_json::from_str(data).expect("Failed to parse reference data");
    if let Some(meta) = &file._meta {
        // Surface the upstream baseline in test output so a CI log makes
        // baseline drift obvious without having to open the JSON.
        println!(
            "Cross-validation baseline: {}@{} ({})",
            meta.upstream,
            meta.version,
            meta.commit.get(..7).unwrap_or(&meta.commit),
        );
    }
    file.cases
}

fn build_graph(tc: &TestCase) -> (Graph<NodeLabel, EdgeLabel>, LayoutOptions) {
    // dagre.js reference data was generated with compound: true for ALL graphs.
    let mut g = Graph::with_options(GraphOptions {
        directed: true,
        multigraph: true,
        compound: true,
    });

    // Set up nodes in the same order as the JS reference generator.
    // This is critical because dagre.js preserves insertion order and
    // the ordering algorithm depends on g.nodes() order.
    let node_order = get_node_order(&tc.name);
    let cluster_ids = cluster_node_ids_for(&tc.name);
    for v in &node_order {
        // Cluster (compound) nodes are created in JS via `setNode("g", {})`
        // — default 0×0 dimensions. Reference data stores the FINAL
        // (computed) dimensions, so we must use Default here, not the
        // ref_node.
        if cluster_ids.contains(&v.as_str()) {
            g.set_node(v.clone(), Some(NodeLabel::default()));
            continue;
        }
        if let Some(ref_node) = tc.nodes.get(v.as_str()) {
            let label = NodeLabel {
                width: ref_node.width.unwrap_or(0.0),
                height: ref_node.height.unwrap_or(0.0),
                ..Default::default()
            };
            g.set_node(v.clone(), Some(label));
        }
    }

    // Set parent relationships for the compound matrix.
    setup_parents(&mut g, tc);

    // Set up edges based on the test case name
    setup_edges(&mut g, tc);

    // Parse options
    let mut opts = LayoutOptions::default();
    if let Some(rd) = tc.opts.get("rankdir").and_then(|v| v.as_str()) {
        opts.rankdir = match rd {
            "LR" => RankDir::LR,
            "RL" => RankDir::RL,
            "BT" => RankDir::BT,
            _ => RankDir::TB,
        };
    }
    if let Some(ns) = tc.opts.get("nodesep").and_then(|v| v.as_f64()) {
        opts.nodesep = ns;
    }
    if let Some(es) = tc.opts.get("edgesep").and_then(|v| v.as_f64()) {
        opts.edgesep = es;
    }
    if let Some(rs) = tc.opts.get("ranksep").and_then(|v| v.as_f64()) {
        opts.ranksep = rs;
    }
    if let Some(mx) = tc.opts.get("marginx").and_then(|v| v.as_f64()) {
        opts.marginx = mx;
    }
    if let Some(my) = tc.opts.get("marginy").and_then(|v| v.as_f64()) {
        opts.marginy = my;
    }

    (g, opts)
}

/// IDs that should be created with `NodeLabel::default()` (zero-sized;
/// dagre fills the size during layout). Mirrors `g.setNode("g", {})`
/// in the JS generator.
fn cluster_node_ids_for(name: &str) -> &'static [&'static str] {
    match name {
        "compound" => &["group"],
        "compound_single_leaf_tb" | "compound_single_leaf_lr" => &["g"],
        "compound_chain_tb" | "compound_chain_lr" => &["g"],
        "compound_nested_tb" | "compound_nested_lr" => &["inner", "outer"],
        "compound_cross_cluster_tb" | "compound_cross_cluster_lr" => &["g1", "g2"],
        "compound_empty_inner" => &["inner_empty", "outer"],
        "compound_fork_join" => &["g"],
        _ => &[],
    }
}

fn setup_parents(g: &mut Graph<NodeLabel, EdgeLabel>, tc: &TestCase) {
    match tc.name.as_str() {
        "compound" => {
            g.set_parent("a", Some("group"));
            g.set_parent("b", Some("group"));
        }
        "compound_single_leaf_tb" | "compound_single_leaf_lr" => {
            g.set_parent("a", Some("g"));
        }
        "compound_chain_tb" | "compound_chain_lr" => {
            g.set_parent("a", Some("g"));
            g.set_parent("b", Some("g"));
            g.set_parent("c", Some("g"));
        }
        "compound_nested_tb" | "compound_nested_lr" => {
            g.set_parent("a", Some("inner"));
            g.set_parent("b", Some("inner"));
            g.set_parent("inner", Some("outer"));
            g.set_parent("c", Some("outer"));
        }
        "compound_cross_cluster_tb" | "compound_cross_cluster_lr" => {
            g.set_parent("a", Some("g1"));
            g.set_parent("b", Some("g2"));
        }
        "compound_empty_inner" => {
            g.set_parent("a", Some("outer"));
            g.set_parent("inner_empty", Some("outer"));
        }
        "compound_fork_join" => {
            g.set_parent("l", Some("g"));
            g.set_parent("r", Some("g"));
        }
        _ => {}
    }
}

fn setup_edges(g: &mut Graph<NodeLabel, EdgeLabel>, tc: &TestCase) {
    match tc.name.as_str() {
        "single_node" => {}
        "two_nodes" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
        }
        "diamond" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("a", "c", Some(EdgeLabel::default()), None);
            g.set_edge("b", "d", Some(EdgeLabel::default()), None);
            g.set_edge("c", "d", Some(EdgeLabel::default()), None);
        }
        "chain_5" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("b", "c", Some(EdgeLabel::default()), None);
            g.set_edge("c", "d", Some(EdgeLabel::default()), None);
            g.set_edge("d", "e", Some(EdgeLabel::default()), None);
        }
        "edge_label" => {
            let el = EdgeLabel {
                width: 80.0,
                height: 20.0,
                labelpos: LabelPos::Center,
                ..Default::default()
            };
            g.set_edge("a", "b", Some(el), None);
        }
        "cycle" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("b", "c", Some(EdgeLabel::default()), None);
            g.set_edge("c", "a", Some(EdgeLabel::default()), None);
        }
        "disconnected" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("c", "d", Some(EdgeLabel::default()), None);
        }
        "lr_direction" | "bt_direction" | "rl_direction" | "margins" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
        }
        "custom_sep" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("a", "c", Some(EdgeLabel::default()), None);
        }
        "self_loop" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            let el = EdgeLabel {
                width: 40.0,
                height: 20.0,
                ..Default::default()
            };
            g.set_edge("a", "a", Some(el), None);
        }
        "long_edge" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("a", "c", Some(EdgeLabel::default()), None);
            g.set_edge("b", "c", Some(EdgeLabel::default()), None);
        }
        "fan_out" => {
            for i in 0..5 {
                g.set_edge("root", format!("n{}", i), Some(EdgeLabel::default()), None);
            }
        }
        "varied_sizes" => {
            g.set_edge("small", "medium", Some(EdgeLabel::default()), None);
            g.set_edge("small", "large", Some(EdgeLabel::default()), None);
            g.set_edge("medium", "large", Some(EdgeLabel::default()), None);
        }
        "parallel_edges" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), Some("edge1"));
            g.set_edge("a", "b", Some(EdgeLabel::default()), Some("edge2"));
        }
        "complex" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("a", "c", Some(EdgeLabel::default()), None);
            g.set_edge("b", "d", Some(EdgeLabel::default()), None);
            g.set_edge("b", "e", Some(EdgeLabel::default()), None);
            g.set_edge("c", "f", Some(EdgeLabel::default()), None);
            g.set_edge("c", "g", Some(EdgeLabel::default()), None);
            g.set_edge("d", "h", Some(EdgeLabel::default()), None);
            g.set_edge("e", "h", Some(EdgeLabel::default()), None);
            g.set_edge("f", "h", Some(EdgeLabel::default()), None);
            g.set_edge("g", "h", Some(EdgeLabel::default()), None);
        }
        "compound" => {
            g.set_edge("a", "c", Some(EdgeLabel::default()), None);
            g.set_edge("b", "c", Some(EdgeLabel::default()), None);
        }
        "minlen" => {
            let el = EdgeLabel {
                minlen: 3,
                ..Default::default()
            };
            g.set_edge("a", "b", Some(el), None);
        }
        // Compound bbox matrix.
        "compound_single_leaf_tb" | "compound_single_leaf_lr" => {}
        "compound_chain_tb" | "compound_chain_lr" | "compound_nested_tb" | "compound_nested_lr" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
            g.set_edge("b", "c", Some(EdgeLabel::default()), None);
        }
        "compound_cross_cluster_tb" | "compound_cross_cluster_lr" => {
            g.set_edge("a", "b", Some(EdgeLabel::default()), None);
        }
        "compound_empty_inner" => {}
        "compound_fork_join" => {
            g.set_edge("a", "l", Some(EdgeLabel::default()), None);
            g.set_edge("a", "r", Some(EdgeLabel::default()), None);
            g.set_edge("l", "z", Some(EdgeLabel::default()), None);
            g.set_edge("r", "z", Some(EdgeLabel::default()), None);
        }
        _ => panic!("Unknown test case: {}", tc.name),
    }
}

const TOLERANCE: f64 = 1.0; // Allow 1px tolerance

fn approx_eq(a: f64, b: f64, tol: f64) -> bool {
    (a - b).abs() <= tol
}

#[test]
fn cross_validate_all_cases() {
    let cases = load_reference();
    let mut total_pass = 0;
    let mut total_fail = 0;
    let mut failures: Vec<String> = Vec::new();

    for tc in &cases {
        let (mut g, opts) = build_graph(tc);
        layout(&mut g, Some(opts));

        let mut case_ok = true;

        // Compare node positions
        for (v, ref_node) in &tc.nodes {
            let node = match g.node(v) {
                Some(n) => n,
                None => {
                    failures.push(format!("[{}] node '{}' missing in output", tc.name, v));
                    case_ok = false;
                    continue;
                }
            };

            let (x, y) = (node.x.unwrap_or(f64::NAN), node.y.unwrap_or(f64::NAN));

            if !approx_eq(x, ref_node.x, TOLERANCE) {
                failures.push(format!(
                    "[{}] node '{}' x: dagre-rs={:.3}, dagre.js={:.3}, diff={:.3}",
                    tc.name,
                    v,
                    x,
                    ref_node.x,
                    (x - ref_node.x).abs()
                ));
                case_ok = false;
            }
            if !approx_eq(y, ref_node.y, TOLERANCE) {
                failures.push(format!(
                    "[{}] node '{}' y: dagre-rs={:.3}, dagre.js={:.3}, diff={:.3}",
                    tc.name,
                    v,
                    y,
                    ref_node.y,
                    (y - ref_node.y).abs()
                ));
                case_ok = false;
            }

            // Compare rank
            if let Some(ref_rank) = ref_node.rank
                && node.rank != Some(ref_rank)
            {
                failures.push(format!(
                    "[{}] node '{}' rank: dagre-rs={:?}, dagre.js={}",
                    tc.name, v, node.rank, ref_rank
                ));
                case_ok = false;
            }
        }

        // Compare graph dimensions
        if let Some(gl) = g.graph_label::<GraphLabel>() {
            if !approx_eq(gl.width, tc.graph.width, TOLERANCE) {
                failures.push(format!(
                    "[{}] graph width: dagre-rs={:.3}, dagre.js={:.3}",
                    tc.name, gl.width, tc.graph.width
                ));
                case_ok = false;
            }
            if !approx_eq(gl.height, tc.graph.height, TOLERANCE) {
                failures.push(format!(
                    "[{}] graph height: dagre-rs={:.3}, dagre.js={:.3}",
                    tc.name, gl.height, tc.graph.height
                ));
                case_ok = false;
            }
        }

        if case_ok {
            total_pass += 1;
        } else {
            total_fail += 1;
        }
    }

    println!("\n=== Cross-validation results ===");
    println!("Passed: {}/{}", total_pass, cases.len());
    println!("Failed: {}/{}", total_fail, cases.len());

    if !failures.is_empty() {
        println!("\nDivergences:");
        for f in &failures {
            println!("  {}", f);
        }
    }

    // For now, don't assert — just report. We'll tighten this as we fix divergences.
    if total_fail > 0 {
        panic!(
            "{} of {} cross-validation cases diverged from dagre.js. See divergences above.",
            total_fail,
            cases.len()
        );
    }
}