KiCad - the KiCad Bridge

//! Placement helpers on a parsed board: footprint-to-footprint clearance (courtyard or pad
//! copper), a 0-100 placement score with named deductions, a decoupling capacitor plan
//! beside an IC's power pins, and a BGA / QFN fanout plan whose calls `kicad_route_net`
//! takes as they are. Pure: nothing here talks to KiCad.
//!
//! Coordinates are millimetres in KiCad's board frame (+x right, +y DOWN); rotations are
//! degrees with KiCad's sign, as `crate::placement` uses them.

use serde_json::{json, Value};

use crate::pcb::{self, Board, Footprint, RoutingError};
use crate::placement::{self, Placement, Rect};

type R<T> = Result<T, RoutingError>;
type P = (f64, f64);

fn r3(v: f64) -> f64 {
    (v * 1000.0).round() / 1000.0
}

// ---------------------------------------------------------------------------
// Distance geometry
// ---------------------------------------------------------------------------

fn seg_point(p: P, a: P, b: P) -> f64 {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let l2 = dx * dx + dy * dy;
    let t = if l2 == 0.0 { 0.0 } else { (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / l2).clamp(0.0, 1.0) };
    pcb::dist(p, (a.0 + t * dx, a.1 + t * dy))
}

fn cross(o: P, a: P, b: P) -> f64 {
    (a.0 - o.0) * (b.1 - o.1) - (a.1 - o.1) * (b.0 - o.0)
}

fn segs_cross(a: P, b: P, c: P, d: P) -> bool {
    let (d1, d2, d3, d4) = (cross(c, d, a), cross(c, d, b), cross(a, b, c), cross(a, b, d));
    ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0)) && ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0))
}

fn seg_seg(a: P, b: P, c: P, d: P) -> f64 {
    if segs_cross(a, b, c, d) {
        return 0.0;
    }
    seg_point(a, c, d).min(seg_point(b, c, d)).min(seg_point(c, a, b)).min(seg_point(d, a, b))
}

/// Ray casting over a closed polygon given as edges.
fn inside_edges(p: P, edges: &[(P, P)]) -> bool {
    let mut c = false;
    for (a, b) in edges {
        if (a.1 > p.1) != (b.1 > p.1) && p.0 < (b.0 - a.0) * (p.1 - a.1) / (b.1 - a.1) + a.0 {
            c = !c;
        }
    }
    c
}

/// The gap between two outlines given as edges: 0 when they touch, cross or nest.
pub fn edges_distance(a: &[(P, P)], b: &[(P, P)]) -> f64 {
    let mut best = f64::INFINITY;
    for (p, q) in a {
        for (r, s) in b {
            best = best.min(seg_seg(*p, *q, *r, *s));
            if best == 0.0 {
                return 0.0;
            }
        }
    }
    if let (Some(pa), Some(pb)) = (a.first(), b.first()) {
        if inside_edges(pa.0, b) || inside_edges(pb.0, a) {
            return 0.0;
        }
    }
    best
}

pub fn rect_distance(a: &Rect, b: &Rect) -> f64 {
    let dx = (b.min_x - a.max_x).max(a.min_x - b.max_x).max(0.0);
    let dy = (b.min_y - a.max_y).max(a.min_y - b.max_y).max(0.0);
    (dx * dx + dy * dy).sqrt()
}

fn rect_edges(r: &Rect) -> Vec<(P, P)> {
    let c = [(r.min_x, r.min_y), (r.max_x, r.min_y), (r.max_x, r.max_y), (r.min_x, r.max_y)];
    (0..4).map(|i| (c[i], c[(i + 1) % 4])).collect()
}

fn outline_of(p: &Placement) -> Vec<(P, P)> {
    if p.outline.is_empty() {
        rect_edges(&p.courtyard)
    } else {
        p.outline.clone()
    }
}

// ---------------------------------------------------------------------------
// Pad copper in board coordinates
// ---------------------------------------------------------------------------

/// One pad's copper: a circle, or the polygon of its rectangle (round-rect and oval pads
/// use their full rectangle, which is conservative: the reported gap is never larger than
/// KiCad's).
#[derive(Clone, Debug)]
pub struct PadShape {
    pub reference: String,
    pub pad: String,
    pub net: String,
    pub center: P,
    pub circle: Option<f64>,
    pub edges: Vec<(P, P)>,
    pub bbox: Rect,
    pub layers: Vec<String>,
}

pub fn pad_shapes(board: &Board) -> Vec<PadShape> {
    let mut out = Vec::new();
    for fp in &board.footprints {
        let (fx, fy, rot) = fp.position.as_ref().map(|p| (p.x, p.y, p.rotation.unwrap_or(0.0))).unwrap_or((0.0, 0.0, 0.0));
        for pad in &fp.pads {
            let (Some(px), Some(py)) = (pad.x, pad.y) else { continue };
            let (w, h) = (pad.width.unwrap_or(0.0), pad.height.unwrap_or(0.0));
            let center = placement::to_board((fx, fy), rot, (px, py));
            let ang = pad.rotation.unwrap_or(0.0);
            let circle = (pad.shape == "circle").then_some(w.max(h) / 2.0);
            let corners: Vec<P> = [(-w / 2.0, -h / 2.0), (w / 2.0, -h / 2.0), (w / 2.0, h / 2.0), (-w / 2.0, h / 2.0)].iter().map(|c| placement::to_board(center, ang, *c)).collect();
            let edges: Vec<(P, P)> = (0..4).map(|i| (corners[i], corners[(i + 1) % 4])).collect();
            let bbox = match circle {
                Some(r) => Rect { min_x: center.0 - r, min_y: center.1 - r, max_x: center.0 + r, max_y: center.1 + r },
                None => Rect::from_points(corners.iter().copied()).unwrap(),
            };
            out.push(PadShape { reference: fp.reference.clone(), pad: pad.number.clone(), net: pad.net_name.clone().unwrap_or_default(), center, circle, edges, bbox, layers: pad.layers.clone().unwrap_or_default() });
        }
    }
    out
}

fn shape_distance(a: &PadShape, b: &PadShape) -> f64 {
    match (a.circle, b.circle) {
        (Some(ra), Some(rb)) => (pcb::dist(a.center, b.center) - ra - rb).max(0.0),
        (Some(ra), None) => point_to_poly(a.center, &b.edges, ra),
        (None, Some(rb)) => point_to_poly(b.center, &a.edges, rb),
        (None, None) => edges_distance(&a.edges, &b.edges),
    }
}

fn point_to_poly(p: P, edges: &[(P, P)], r: f64) -> f64 {
    if inside_edges(p, edges) {
        return 0.0;
    }
    (edges.iter().map(|(a, b)| seg_point(p, *a, *b)).fold(f64::INFINITY, f64::min) - r).max(0.0)
}

fn copper_sides(layers: &[String]) -> (bool, bool) {
    let any = layers.iter().any(|l| l == "*.Cu");
    (any || layers.iter().any(|l| l == "F.Cu"), any || layers.iter().any(|l| l == "B.Cu"))
}

// ---------------------------------------------------------------------------
// kicad_check_clearance
// ---------------------------------------------------------------------------

fn refs_arg(args: &Value) -> Option<Vec<String>> {
    args.get("refs").and_then(Value::as_array).map(|a| a.iter().filter_map(Value::as_str).map(|s| s.trim().to_uppercase()).collect())
}

/// Footprint pairs (`mode: "courtyard"`, the default) or pad pairs of different footprints
/// (`mode: "pads"`) closer than `threshold` mm (default 0.25 courtyard, 0.2 pads). `refs`
/// limits the check to pairs that involve at least one of them. Pads on the same net are
/// skipped unless `includeSameNet`. Courtyards on different sides never conflict.
pub fn check_clearance(board: &Board, args: &Value) -> R<Value> {
    let mode = args.get("mode").and_then(Value::as_str).unwrap_or("courtyard");
    let threshold = match args.get("threshold") {
        Some(v) => pcb::number(Some(v), "threshold", false)?.max(0.0),
        None => if mode == "pads" { 0.2 } else { 0.25 },
    };
    let limit = args.get("maxPairs").and_then(Value::as_u64).unwrap_or(200) as usize;
    let refs = refs_arg(args);
    if let Some(rs) = &refs {
        let known: Vec<String> = board.footprints.iter().map(|f| f.reference.to_uppercase()).collect();
        let unknown: Vec<&String> = rs.iter().filter(|r| !known.contains(r)).collect();
        if !unknown.is_empty() {
            return Err(RoutingError::new("unknown_footprint", format!("not on this board: {unknown:?}")));
        }
    }
    let wanted = |r: &str| refs.as_ref().map(|rs| rs.iter().any(|x| x == &r.to_uppercase())).unwrap_or(true);
    let mut pairs: Vec<Value> = Vec::new();
    let mut checked = 0usize;
    match mode {
        "courtyard" => {
            let places = placement::placements(board);
            for i in 0..places.len() {
                for j in (i + 1)..places.len() {
                    let (a, b) = (&places[i], &places[j]);
                    if a.side != b.side || !(wanted(&a.reference) || wanted(&b.reference)) {
                        continue;
                    }
                    checked += 1;
                    if rect_distance(&a.courtyard, &b.courtyard) > threshold {
                        continue;
                    }
                    let d = edges_distance(&outline_of(a), &outline_of(b));
                    if d < threshold {
                        let (x, y) = if placement::ref_key(&a.reference) <= placement::ref_key(&b.reference) { (a, b) } else { (b, a) };
                        pairs.push(json!({"a": x.reference, "b": y.reference, "side": a.side, "distanceMm": r3(d), "overlapping": d == 0.0,
                            "measuredOn": if a.outline.is_empty() || b.outline.is_empty() { "courtyard box" } else { "courtyard outline" }}));
                    }
                }
            }
        }
        "pads" => {
            let same_net = args.get("includeSameNet") == Some(&json!(true));
            let shapes = pad_shapes(board);
            for i in 0..shapes.len() {
                for j in (i + 1)..shapes.len() {
                    let (a, b) = (&shapes[i], &shapes[j]);
                    if a.reference == b.reference || !(wanted(&a.reference) || wanted(&b.reference)) {
                        continue;
                    }
                    if !same_net && !a.net.is_empty() && a.net == b.net {
                        continue;
                    }
                    let (af, ab) = copper_sides(&a.layers);
                    let (bf, bb) = copper_sides(&b.layers);
                    if !((af && bf) || (ab && bb)) {
                        continue;
                    }
                    checked += 1;
                    if rect_distance(&a.bbox, &b.bbox) > threshold {
                        continue;
                    }
                    let d = shape_distance(a, b);
                    if d < threshold {
                        pairs.push(json!({"a": format!("{}.{}", a.reference, a.pad), "b": format!("{}.{}", b.reference, b.pad), "netA": a.net, "netB": b.net, "distanceMm": r3(d), "touching": d == 0.0}));
                    }
                }
            }
        }
        other => return Err(RoutingError::new("invalid_mode", format!("mode is courtyard or pads, not {other}"))),
    }
    pairs.sort_by(|x, y| x["distanceMm"].as_f64().partial_cmp(&y["distanceMm"].as_f64()).unwrap_or(std::cmp::Ordering::Equal));
    let total = pairs.len();
    pairs.truncate(limit);
    Ok(json!({
        "mode": mode, "thresholdMm": threshold, "pairsChecked": checked, "violationCount": total, "pairs": pairs, "truncated": total > limit,
        "clean": total == 0,
        "method": if mode == "pads" { "pad copper: circles exact, rectangles, round-rects and ovals as their full rectangle (conservative)" } else { "courtyard outline when both footprints have one, else the courtyard box; same side only" },
    }))
}

// ---------------------------------------------------------------------------
// Part classification
// ---------------------------------------------------------------------------

fn prefix(r: &str) -> String {
    r.chars().take_while(|c| c.is_ascii_alphabetic()).collect::<String>().to_uppercase()
}

pub fn is_ground(net: &str) -> bool {
    let n = net.trim_start_matches('/').to_uppercase();
    n.contains("GND") || n.starts_with("VSS") || n == "0V" || n.ends_with("_VSS")
}

/// A net named like a supply rail: +3V3, 5V, VCC, VDD_IO, VBAT, VIN, VBUS, AVDD, VREF, ...
pub fn is_supply(net: &str) -> bool {
    let n = net.trim_start_matches('/').to_uppercase();
    if n.starts_with('+') || n.starts_with("-") {
        return true;
    }
    if ["VCC", "VDD", "VBAT", "VIN", "VBUS", "VOUT", "VREF", "VSYS", "VMOT", "VM", "PWR", "POWER", "VSUP"].iter().any(|k| n.starts_with(k) || n.contains(&format!("_{k}")) || n.ends_with(k)) {
        return true;
    }
    // 3V3, 5V, 1V8, 12V, 3.3V, V3P3 ...
    let b = n.as_bytes();
    (0..b.len()).any(|i| b[i] == b'V' && i > 0 && b[i - 1].is_ascii_digit()) || n.starts_with("V3P") || n.starts_with("V1P")
}

pub fn is_connector(fp: &Footprint) -> bool {
    let p = prefix(&fp.reference);
    let lib = fp.footprint.to_lowercase();
    matches!(p.as_str(), "J" | "P" | "CN" | "X" | "USB" | "CON") || ["connector", "usb", "pinheader", "pin_header", "terminalblock", "jst", "molex", "barrel"].iter().any(|k| lib.contains(k))
}

pub fn is_ic(fp: &Footprint) -> bool {
    matches!(prefix(&fp.reference).as_str(), "U" | "IC") && fp.pads.len() >= 3
}

pub fn is_cap(fp: &Footprint) -> bool {
    prefix(&fp.reference) == "C" && fp.pads.len() == 2
}

/// A capacitor across a ground net and a power net that an IC also has: (power pad
/// number, power net).
pub fn decoupling_role(cap: &Footprint) -> Option<(String, String)> {
    if !is_cap(cap) {
        return None;
    }
    let nets: Vec<(String, String)> = cap.pads.iter().map(|p| (p.number.clone(), p.net_name.clone().unwrap_or_default())).collect();
    let g = nets.iter().filter(|(_, n)| is_ground(n)).count();
    if g != 1 {
        return None;
    }
    nets.into_iter().find(|(_, n)| !n.is_empty() && !is_ground(n))
}

// ---------------------------------------------------------------------------
// kicad_score_placement
// ---------------------------------------------------------------------------

/// 0-100 with named deductions. Each rule's points per offence and cap:
/// courtyard overlap 10 (40), outside the outline 10 (30), connector farther than
/// `connectorEdgeMm` (3) from the edge 5 (15), decoupling cap farther than
/// `decouplingMm` (3) from its IC's nearest pin on the cap's power net 3 (15), and the
/// ratsnest: the mean MST edge as a fraction of the board diagonal, 0 points at 10 %
/// rising to 20 at 40 %.
pub fn score(board: &Board, args: &Value) -> Value {
    let places = placement::placements(board);
    let outline = placement::outline(board);
    let edge_mm = args.get("connectorEdgeMm").and_then(Value::as_f64).unwrap_or(3.0);
    let decap_mm = args.get("decouplingMm").and_then(Value::as_f64).unwrap_or(3.0);
    let mut deductions = Vec::new();
    let mut push = |rule: &str, per: f64, cap: f64, items: Vec<Value>, detail: &str| {
        let pts = (per * items.len() as f64).min(cap);
        deductions.push(json!({"rule": rule, "count": items.len(), "points": pts, "perItem": per, "cap": cap, "items": items, "detail": detail}));
        pts
    };
    let mut total = 0.0;
    let overlaps = placement::overlaps(&places);
    total += push("courtyard_overlap", 10.0, 40.0, overlaps.iter().map(|o| json!({"a": o.a, "b": o.b, "side": o.side})).collect(), "same-side courtyards that overlap");
    let outside: Vec<Value> = places.iter().filter(|p| p.inside_outline == Some(false)).map(|p| json!(p.reference)).collect();
    total += push("outside_board", 10.0, 30.0, outside, "courtyard not inside the Edge.Cuts box");
    let mut far_conn = Vec::new();
    if let Some(o) = &outline {
        for (fp, p) in board.footprints.iter().zip(places.iter()) {
            if !is_connector(fp) || p.inside_outline == Some(false) {
                continue;
            }
            let c = &p.courtyard;
            let d = (c.min_x - o.min_x).min(o.max_x - c.max_x).min(c.min_y - o.min_y).min(o.max_y - c.max_y).max(0.0);
            if d > edge_mm {
                far_conn.push(json!({"ref": fp.reference, "edgeDistanceMm": r3(d)}));
            }
        }
    }
    total += push("connector_off_edge", 5.0, 15.0, far_conn, "connectors whose courtyard is farther than connectorEdgeMm from the board edge");
    let pads = pcb::pads(board);
    let mut far_caps = Vec::new();
    for fp in &board.footprints {
        let Some((pad_no, net)) = decoupling_role(fp) else { continue };
        let Some(cp) = pads.iter().find(|p| p.reference == fp.reference && p.pad == pad_no) else { continue };
        let ic_pins: Vec<&pcb::Pad> = pads.iter().filter(|p| p.net_name == net && p.reference != fp.reference && board.footprints.iter().any(|f| f.reference == p.reference && is_ic(f))).collect();
        let Some(best) = ic_pins.iter().min_by(|a, b| pcb::dist((a.x, a.y), (cp.x, cp.y)).partial_cmp(&pcb::dist((b.x, b.y), (cp.x, cp.y))).unwrap()) else { continue };
        let d = pcb::dist((best.x, best.y), (cp.x, cp.y));
        if d > decap_mm {
            far_caps.push(json!({"ref": fp.reference, "net": net, "nearestPin": best.name, "distanceMm": r3(d)}));
        }
    }
    total += push("decoupling_far", 3.0, 15.0, far_caps, "decoupling caps farther than decouplingMm from their IC's nearest pin on the same power net");
    let (nets, mst) = placement::nets(board);
    let edges: usize = nets.iter().map(|n| n.pad_count.saturating_sub(1)).sum();
    let diag = outline.map(|o| (o.width().powi(2) + o.height().powi(2)).sqrt()).unwrap_or(0.0);
    let frac = if edges > 0 && diag > 0.0 { mst / edges as f64 / diag } else { 0.0 };
    let rpts = (((frac - 0.1) / 0.3).clamp(0.0, 1.0) * 20.0 * 10.0).round() / 10.0;
    deductions.push(json!({"rule": "ratsnest_length", "count": edges, "points": rpts, "cap": 20.0, "items": [],
        "detail": format!("mean ratsnest edge {:.2} mm is {:.1} % of the {:.1} mm board diagonal (0 points at 10 %, 20 at 40 %)", if edges > 0 { mst / edges as f64 } else { 0.0 }, frac * 100.0, diag)}));
    total += rpts;
    let score = (100.0 - total).max(0.0).round();
    let grade = match score as i64 {
        90..=100 => "A",
        80..=89 => "B",
        70..=79 => "C",
        50..=69 => "D",
        _ => "F",
    };
    deductions.sort_by(|a, b| b["points"].as_f64().partial_cmp(&a["points"].as_f64()).unwrap_or(std::cmp::Ordering::Equal));
    json!({
        "score": score, "grade": grade, "deductions": deductions,
        "metrics": {"footprints": places.len(), "ratsnestTotalMm": mst, "ratsnestEdges": edges, "boardDiagonalMm": r3(diag), "outlineFound": outline.is_some()},
        "thresholds": {"connectorEdgeMm": edge_mm, "decouplingMm": decap_mm},
    })
}

// ---------------------------------------------------------------------------
// kicad_place_decoupling
// ---------------------------------------------------------------------------

fn side_normal(c: &Rect, pin: P) -> ((f64, f64), &'static str) {
    let d = [(pin.0 - c.min_x, (-1.0, 0.0), "left"), (c.max_x - pin.0, (1.0, 0.0), "right"), (pin.1 - c.min_y, (0.0, -1.0), "top"), (c.max_y - pin.1, (0.0, 1.0), "bottom")];
    let best = d.iter().min_by(|a, b| a.0.partial_cmp(&b.0).unwrap()).unwrap();
    (best.1, best.2)
}

/// Positions for capacitors beside an IC's power pins: each cap goes just outside the IC
/// courtyard (`gap` mm, default 0.3) on the side of the pin it serves, turned so its power
/// pad faces the pin and lined up with it; a spot taken by another courtyard slides along
/// the edge. `caps` defaults to every capacitor across ground and one of the IC's power
/// nets. The result carries `moveArgs`, the exact `kicad_move_footprint` batch, and
/// `validation` from the same checks that verb runs.
pub fn plan_decoupling(board: &Board, args: &Value) -> R<Value> {
    let ic_ref = args.get("ic").or_else(|| args.get("ref")).and_then(Value::as_str).map(str::trim).filter(|s| !s.is_empty()).ok_or_else(|| RoutingError::new("missing_ref", "Pass ic: the IC reference (e.g. \"U1\")"))?;
    let places = placement::placements(board);
    let idx = board.footprints.iter().position(|f| f.reference.eq_ignore_ascii_case(ic_ref)).ok_or_else(|| RoutingError::new("unknown_footprint", format!("No footprint {ic_ref}")))?;
    let ic = &board.footprints[idx];
    let icp = &places[idx];
    let gap = args.get("gap").and_then(Value::as_f64).unwrap_or(0.3).max(0.0);
    let pads = pcb::pads(board);
    let ic_pads: Vec<&pcb::Pad> = pads.iter().filter(|p| p.reference == ic.reference).collect();
    let power_nets: Vec<String> = {
        let mut v: Vec<String> = ic_pads.iter().map(|p| p.net_name.clone()).filter(|n| !n.is_empty() && !is_ground(n)).collect();
        v.sort();
        v.dedup();
        v
    };
    // By default the caps across ground and one of the IC's power nets, less (std #22): a net not named like a
    // supply with only one cap to ground (a crystal's load cap is a signal, not decoupling), and a cap nearer
    // another IC's pin on the same net (12 VBAT caps belong to U1, U3 and U4, not all round one of them).
    let mut left_out: Vec<Value> = Vec::new();
    let cap_refs: Vec<String> = match args.get("caps").and_then(Value::as_array) {
        Some(a) => a.iter().filter_map(Value::as_str).map(str::to_string).collect(),
        None => {
            let roles: Vec<(&Footprint, String)> = board.footprints.iter().filter_map(|f| decoupling_role(f).map(|(_, n)| (f, n))).collect();
            let ics: Vec<&Footprint> = board.footprints.iter().filter(|f| is_ic(f)).collect();
            let near = |f: &Footprint, p: &pcb::Pad| {
                let (x, y) = f.position.as_ref().map(|q| (q.x, q.y)).unwrap_or((0.0, 0.0));
                pcb::dist((x, y), (p.x, p.y))
            };
            let mut v: Vec<String> = Vec::new();
            for (f, net) in roles.iter().filter(|(_, n)| power_nets.contains(n)) {
                let caps_on_net = roles.iter().filter(|(_, n)| n == net).count();
                if !is_supply(net) && caps_on_net == 1 {
                    left_out.push(json!({"ref": f.reference, "reason": "signal_net", "net": net, "detail": format!("{net} is not named like a supply and has only this cap to ground: a signal (a crystal's load, a filter), not decoupling. Pass caps:[\"{}\"] to place it anyway.", f.reference)}));
                    continue;
                }
                let mine = ic_pads.iter().filter(|p| &p.net_name == net).map(|p| near(f, p)).fold(f64::INFINITY, f64::min);
                let other = ics.iter().filter(|o| o.reference != ic.reference).filter_map(|o| {
                    pads.iter().filter(|p| p.reference == o.reference && &p.net_name == net).map(|p| near(f, p)).reduce(f64::min).map(|d| (o.reference.clone(), d))
                }).min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
                if let Some((o, d)) = other.filter(|(_, d)| *d < mine) {
                    left_out.push(json!({"ref": f.reference, "reason": "nearer_another_ic", "net": net, "ic": o, "detail": format!("{} is {:.1} mm from {o}'s {net} pin and {:.1} mm from {}'s: it decouples {o}. Pass caps:[...] to move it anyway.", f.reference, d, mine, ic.reference)}));
                    continue;
                }
                v.push(f.reference.clone());
            }
            v.sort_by_key(|r| placement::ref_key(r));
            v
        }
    };
    if cap_refs.is_empty() {
        return Err(RoutingError::new("no_caps", format!("no capacitor across ground and a power net of {}; pass caps:[...]", ic.reference)).with("icPowerNets", json!(power_nets)).with("leftOut", json!(left_out)));
    }
    let moving: Vec<String> = cap_refs.iter().map(|r| r.to_uppercase()).collect();
    // Obstacles: every same-side courtyard that is not one of the caps being placed.
    let mut taken: Vec<Rect> = places.iter().filter(|p| p.side == icp.side && !moving.contains(&p.reference.to_uppercase())).map(|p| p.courtyard).collect();
    // a through-hole pad of a part on the other side comes through to this side too
    let other_side: Vec<String> = places.iter().filter(|p| p.side != icp.side).map(|p| p.reference.clone()).collect();
    taken.extend(pad_shapes(board).into_iter().filter(|s| other_side.contains(&s.reference) && (s.layers.iter().any(|l| l == "*.Cu") || (s.layers.iter().any(|l| l == "F.Cu") && s.layers.iter().any(|l| l == "B.Cu")))).map(|s| s.bbox));
    // a cap that will not move keeps its spot (std #22: a skipped cap was left out of the taken spots): the ones
    // on another side are on another side's courtyards already; one on no shared power net stays put here
    for (i, f) in board.footprints.iter().enumerate() {
        if moving.contains(&f.reference.to_uppercase()) && places[i].side == icp.side
            && !f.pads.iter().any(|p| p.net_name.as_deref().map(|n| power_nets.iter().any(|x| x == n)).unwrap_or(false)) {
            taken.push(places[i].courtyard);
        }
    }
    // std #22 leaveFanout (default true): a cap's pads keep clear of the stubs and vias plan_fanout would give the IC's
    // other nets' pins, so placing caps first does not block the escape (Altium put 5 caps on U4's stubs)
    let leave_fanout = args.get("leaveFanout").and_then(Value::as_bool).unwrap_or(true);
    let (fan, fan_clear) = if leave_fanout { fanout_pieces(board, &ic.reference, &icp.side) } else { (Vec::new(), 0.0) };
    let outline = placement::outline(board);
    let mut used_pins: Vec<String> = Vec::new();
    let mut moves = Vec::new();
    let mut rows = Vec::new();
    let mut skipped = Vec::new();
    for cr in &cap_refs {
        let Some(ci) = board.footprints.iter().position(|f| f.reference.eq_ignore_ascii_case(cr)) else {
            skipped.push(json!({"ref": cr, "reason": "unknown_footprint"}));
            continue;
        };
        let cap = &board.footprints[ci];
        if places[ci].side != icp.side {
            skipped.push(json!({"ref": cap.reference, "reason": "other_side", "detail": format!("{} is on {}, the IC on {}; flip it first (side changes are not moved by kicad_move_footprint)", cap.reference, places[ci].side, icp.side)}));
            continue;
        }
        let Some(pp) = cap.pads.iter().find(|p| p.net_name.as_deref().map(|n| power_nets.iter().any(|x| x == n)).unwrap_or(false)) else {
            skipped.push(json!({"ref": cap.reference, "reason": "no_shared_power_net"}));
            continue;
        };
        let net = pp.net_name.clone().unwrap_or_default();
        let mut pins: Vec<&&pcb::Pad> = ic_pads.iter().filter(|p| p.net_name == net).collect();
        pins.sort_by_key(|p| (used_pins.contains(&p.name), placement::ref_key(&p.pad)));
        let pin = pins[0];
        used_pins.push(pin.name.clone());
        let (n, side) = side_normal(&icp.courtyard, (pin.x, pin.y));
        let v = (pp.x.unwrap_or(0.0), pp.y.unwrap_or(0.0));
        let rot = [0.0, 90.0, 180.0, 270.0]
            .into_iter()
            .max_by(|a, b| {
                let ra = placement::to_board((0.0, 0.0), *a, v);
                let rb = placement::to_board((0.0, 0.0), *b, v);
                (-(ra.0 * n.0 + ra.1 * n.1)).partial_cmp(&(-(rb.0 * n.0 + rb.1 * n.1))).unwrap()
            })
            .unwrap();
        let rot = if rot == 270.0 { -90.0 } else { rot };
        let (cy, _) = placement::courtyard_at(cap, (0.0, 0.0), rot);
        let rv = placement::to_board((0.0, 0.0), rot, v);
        let c = &icp.courtyard;
        let base = match side {
            "left" => (c.min_x - gap - cy.max_x, pin.y - rv.1),
            "right" => (c.max_x + gap - cy.min_x, pin.y - rv.1),
            "top" => (pin.x - rv.0, c.min_y - gap - cy.max_y),
            _ => (pin.x - rv.0, c.max_y + gap - cy.min_y),
        };
        let along = if n.0 != 0.0 { (0.0, 1.0) } else { (1.0, 0.0) };
        let step = if n.0 != 0.0 { cy.height() } else { cy.width() } + gap;
        let mut chosen = None;
        for k in 0..13 {
            let s = if k == 0 { 0.0 } else if k % 2 == 1 { ((k + 1) / 2) as f64 * step } else { -((k / 2) as f64) * step };
            let at = (pcb::round6(base.0 + along.0 * s), pcb::round6(base.1 + along.1 * s));
            let r = placement::courtyard_at(cap, at, rot).0;
            let off_fanout = fan.is_empty() || cap.pads.iter().all(|pd| {
                let c = placement::to_board(at, rot, (pd.x.unwrap_or(0.0), pd.y.unwrap_or(0.0)));
                let rad = pd.width.unwrap_or(0.0).max(pd.height.unwrap_or(0.0)) / 2.0;
                let pnet = pd.net_name.as_deref().unwrap_or("");
                fan.iter().filter(|(n, ..)| n != pnet || pnet.is_empty()).all(|(_, a, b, hw)| seg_point(c, *a, *b) - rad - hw >= fan_clear - 1e-9)
            });
            let clear = off_fanout && taken.iter().all(|t| !t.overlaps(&r)) && outline.map(|o| o.contains(&r)).unwrap_or(true);
            if clear {
                chosen = Some((at, r, s));
                break;
            }
        }
        let Some((at, r, slid)) = chosen else {
            skipped.push(json!({"ref": cap.reference, "reason": "no_free_spot", "pin": pin.name, "side": side}));
            taken.push(places[ci].courtyard); // it stays where it is (std #22)
            continue;
        };
        taken.push(r);
        let pad_at = placement::to_board(at, rot, v);
        rows.push(json!({"ref": cap.reference, "net": net, "pin": pin.name, "side": side, "x": at.0, "y": at.1, "rotation": rot,
            "powerPad": format!("{}.{}", cap.reference, pp.number), "padToPinMm": r3(pcb::dist(pad_at, (pin.x, pin.y))), "slidMm": r3(slid),
            "from": {"x": places[ci].x, "y": places[ci].y, "rotation": places[ci].rotation}}));
        moves.push(json!({"ref": cap.reference, "x": at.0, "y": at.1, "rotation": rot}));
    }
    let validation = if moves.is_empty() {
        json!({"ok": false, "reason": "nothing to place"})
    } else {
        match placement::plan_moves(board, &json!({"refs": moves})) {
            Ok(p) => json!({"ok": true, "checks": p.checks}),
            Err(e) => {
                let mut v = json!({"ok": false, "errorCode": e.code, "error": e.message});
                for (k, val) in e.detail {
                    v[k] = val;
                }
                v
            }
        }
    };
    Ok(json!({"ic": ic.reference, "icPowerNets": power_nets, "placements": rows, "skipped": skipped, "leftOut": left_out,
        "leaveFanout": leave_fanout, "fanoutPieces": fan.len(), "moveArgs": {"refs": moves}, "validation": validation, "gapMm": gap}))
}

// ---------------------------------------------------------------------------
// kicad_plan_fanout
// ---------------------------------------------------------------------------

fn median(mut v: Vec<f64>) -> Option<f64> {
    if v.is_empty() {
        return None;
    }
    v.sort_by(|a, b| a.partial_cmp(b).unwrap());
    Some(v[v.len() / 2])
}

/// A fanout plan for one BGA or perimeter (QFN, QFP, SOIC) package. Detects the pad pitch
/// (median nearest-neighbour spacing) and the package kind (pads inside the grid make a
/// BGA). BGA: the outer ring escapes on the surface; every inner ball gets a dogbone via
/// on the diagonal away from the package centre, or a via in the pad when the dogbone does
/// not fit (`style: auto|dogbone|via-in-pad`). Perimeter: each pad gets an outward surface
/// stub (with a via at its end when `viaPerimeter` or the net is ground), and an exposed
/// pad a via grid. `calls` is one `kicad_route_net` argument object per net.
pub fn plan_fanout(board: &Board, args: &Value) -> R<Value> {
    let r = args.get("ref").and_then(Value::as_str).map(str::trim).filter(|s| !s.is_empty()).ok_or_else(|| RoutingError::new("missing_ref", "Pass ref: the BGA or QFN reference"))?;
    let fp = board.footprints.iter().find(|f| f.reference.eq_ignore_ascii_case(r)).ok_or_else(|| RoutingError::new("unknown_footprint", format!("No footprint {r}")))?;
    let side = if fp.layer.as_deref() == Some("B.Cu") { "B.Cu" } else { "F.Cu" };
    let copper = pcb::copper_layers(board);
    let escape = match args.get("escapeLayer").and_then(Value::as_str) {
        Some(l) if copper.iter().any(|c| c == l) => l.to_string(),
        Some(l) => return Err(RoutingError::new("unknown_layer", format!("Unknown copper layer: {l}")).with("copperLayers", json!(copper))),
        None => copper.iter().find(|l| l.starts_with("In")).cloned().unwrap_or_else(|| if side == "F.Cu" { "B.Cu".into() } else { "F.Cu".into() }),
    };
    let all = pcb::pads(board);
    let pads: Vec<&pcb::Pad> = all.iter().filter(|p| p.reference == fp.reference && !p.pad.is_empty() && p.kind == "smd").collect();
    if pads.len() < 4 {
        return Err(RoutingError::new("not_a_package", format!("{} has {} SMD pads; fanout is for BGA and QFN/QFP packages", fp.reference, pads.len())));
    }
    let sizes: Vec<(f64, f64)> = pads.iter().map(|p| fp.pads.iter().find(|q| q.number == p.pad).map(|q| (q.width.unwrap_or(0.0), q.height.unwrap_or(0.0))).unwrap_or((0.0, 0.0))).collect();
    let areas: Vec<f64> = sizes.iter().map(|s| s.0 * s.1).collect();
    let med_area = median(areas.clone()).unwrap_or(0.0);
    let thermal: Vec<usize> = (0..pads.len()).filter(|i| areas[*i] > 4.0 * med_area).collect();
    let signal: Vec<usize> = (0..pads.len()).filter(|i| !thermal.contains(i)).collect();
    let nn: Vec<f64> = signal.iter().map(|&i| signal.iter().filter(|&&j| j != i).map(|&j| pcb::dist((pads[i].x, pads[i].y), (pads[j].x, pads[j].y))).fold(f64::INFINITY, f64::min)).collect();
    let pitch = match args.get("pitch") {
        Some(v) => pcb::number(Some(v), "pitch", true)?,
        None => r3(median(nn).ok_or_else(|| RoutingError::new("not_a_package", "no pad pitch"))?),
    };
    let fx = fp.position.as_ref().map(|p| (p.x, p.y)).unwrap_or((0.0, 0.0));
    let cx = signal.iter().map(|&i| pads[i].x).sum::<f64>() / signal.len() as f64;
    let cy = signal.iter().map(|&i| pads[i].y).sum::<f64>() / signal.len() as f64;
    let (minx, maxx) = signal.iter().map(|&i| pads[i].x).fold((f64::INFINITY, f64::NEG_INFINITY), |a, x| (a.0.min(x), a.1.max(x)));
    let (miny, maxy) = signal.iter().map(|&i| pads[i].y).fold((f64::INFINITY, f64::NEG_INFINITY), |a, y| (a.0.min(y), a.1.max(y)));
    let interior = signal.iter().filter(|&&i| {
        let p = pads[i];
        (p.x - minx).min(maxx - p.x).min(p.y - miny).min(maxy - p.y) > pitch * 0.5
    }).count();
    let kind = if interior > 0 { "bga" } else { "perimeter" };
    let fine = pitch < 0.8 - 1e-9;
    let via_size = args.get("viaSize").and_then(Value::as_f64).unwrap_or(if fine { 0.4 } else if pitch < 1.0 - 1e-9 { 0.45 } else { 0.6 });
    let via_drill = args.get("viaDrill").and_then(Value::as_f64).unwrap_or(if via_size <= 0.45 { 0.2 } else { 0.3 });
    if via_drill >= via_size {
        return Err(RoutingError::new("invalid_geometry", "viaDrill must be smaller than viaSize"));
    }
    let width = args.get("width").and_then(Value::as_f64).unwrap_or(if fine { 0.1 } else { 0.15 });
    let clearance = args.get("clearance").and_then(Value::as_f64).unwrap_or(0.1);
    let pad_d = median(signal.iter().map(|&i| sizes[i].0.max(sizes[i].1)).collect()).unwrap_or(0.0);
    let dogbone_room = r3(pitch / 2f64.sqrt() - pad_d / 2.0 - via_size / 2.0);
    let dogbone_fits = dogbone_room + 1e-9 >= clearance;
    let want = args.get("style").and_then(Value::as_str).unwrap_or("auto");
    let style = match want {
        "auto" => if dogbone_fits { "dogbone" } else { "via-in-pad" },
        "dogbone" | "via-in-pad" => want,
        o => return Err(RoutingError::new("invalid_style", format!("style is auto, dogbone or via-in-pad, not {o}"))),
    };
    let mut warnings = Vec::new();
    if style == "dogbone" && !dogbone_fits {
        warnings.push(format!("a {via_size} mm dogbone via leaves {dogbone_room} mm to the balls at {pitch} mm pitch, under the {clearance} mm clearance; use via-in-pad or a smaller via"));
    }
    let via_perimeter = args.get("viaPerimeter") == Some(&json!(true));
    let stub = args.get("stubMm").and_then(Value::as_f64).unwrap_or(0.4);
    let mut rows = Vec::new();
    let mut calls: std::collections::BTreeMap<String, Vec<Value>> = std::collections::BTreeMap::new();
    let mut add = |net: &str, path: Value| calls.entry(net.to_string()).or_default().push(path);
    let pt = |x: f64, y: f64| json!([pcb::round6(x), pcb::round6(y)]);
    let pt_l = |x: f64, y: f64, l: &str| json!({"x": pcb::round6(x), "y": pcb::round6(y), "layer": l});
    let mut vias: Vec<P> = Vec::new();
    let sign = |v: f64| if v < -1e-9 { -1.0 } else { 1.0 };
    for &i in &signal {
        let p = pads[i];
        if p.net_name.is_empty() {
            rows.push(json!({"pad": p.name, "net": "", "style": "skip", "reason": "no net"}));
            continue;
        }
        if kind == "bga" {
            let ring = ((p.x - minx) / pitch).round().min(((maxx - p.x) / pitch).round()).min(((p.y - miny) / pitch).round()).min(((maxy - p.y) / pitch).round()) as i64;
            if ring == 0 && args.get("surfaceOuterRing") != Some(&json!(false)) {
                let (n, _) = side_normal(&Rect { min_x: minx, min_y: miny, max_x: maxx, max_y: maxy }, (p.x, p.y));
                let end = (p.x + n.0 * pitch, p.y + n.1 * pitch);
                rows.push(json!({"pad": p.name, "net": p.net_name, "ring": ring, "style": "surface", "escapeLayer": side, "stubEnd": pt(end.0, end.1)}));
                add(&p.net_name, json!([p.name, pt(end.0, end.1)]));
                continue;
            }
            if style == "dogbone" {
                let v = (p.x + sign(p.x - cx) * pitch / 2.0, p.y + sign(p.y - cy) * pitch / 2.0);
                vias.push(v);
                rows.push(json!({"pad": p.name, "net": p.net_name, "ring": ring, "style": "dogbone", "escapeLayer": escape, "via": {"at": pt(v.0, v.1), "size": via_size, "drill": via_drill}}));
                add(&p.net_name, json!([p.name, pt_l(v.0, v.1, &escape)]));
            } else {
                vias.push((p.x, p.y));
                rows.push(json!({"pad": p.name, "net": p.net_name, "ring": ring, "style": "via-in-pad", "escapeLayer": escape, "via": {"at": pt(p.x, p.y), "size": via_size, "drill": via_drill}, "note": "via-in-pad needs filled and capped vias (IPC-4761 type VII) from the fab"}));
                add(&p.net_name, json!([pt_l(p.x, p.y, side), pt_l(p.x, p.y, &escape)]));
            }
        } else {
            let (n, edge) = side_normal(&Rect { min_x: minx, min_y: miny, max_x: maxx, max_y: maxy }, (p.x, p.y));
            let (w, h) = sizes[i];
            let len_along = {
                let a = placement::to_board((0.0, 0.0), fp.pads.iter().find(|q| q.number == p.pad).and_then(|q| q.rotation).unwrap_or(0.0), (w, h));
                if n.0 != 0.0 { a.0.abs() } else { a.1.abs() }
            };
            let reach = len_along / 2.0 + stub + if via_perimeter || is_ground(&p.net_name) { via_size / 2.0 } else { 0.0 };
            let end = (p.x + n.0 * reach, p.y + n.1 * reach);
            if via_perimeter || is_ground(&p.net_name) {
                vias.push(end);
                rows.push(json!({"pad": p.name, "net": p.net_name, "edge": edge, "style": "stub+via", "escapeLayer": escape, "via": {"at": pt(end.0, end.1), "size": via_size, "drill": via_drill}}));
                add(&p.net_name, json!([p.name, pt_l(end.0, end.1, &escape)]));
            } else {
                rows.push(json!({"pad": p.name, "net": p.net_name, "edge": edge, "style": "surface", "escapeLayer": side, "stubEnd": pt(end.0, end.1)}));
                add(&p.net_name, json!([p.name, pt(end.0, end.1)]));
            }
        }
    }
    for &i in &thermal {
        let p = pads[i];
        if p.net_name.is_empty() {
            continue;
        }
        let (w, h) = sizes[i];
        let vp = (via_size + 0.5).max(1.0);
        let nx = (((w - via_size) / vp).floor() as i64 + 1).max(1);
        let ny = (((h - via_size) / vp).floor() as i64 + 1).max(1);
        let mut at = Vec::new();
        for a in 0..nx {
            for b in 0..ny {
                let v = (p.x + (a as f64 - (nx - 1) as f64 / 2.0) * vp, p.y + (b as f64 - (ny - 1) as f64 / 2.0) * vp);
                vias.push(v);
                at.push(pt(v.0, v.1));
                add(&p.net_name, json!([pt_l(v.0, v.1, side), pt_l(v.0, v.1, &escape)]));
            }
        }
        rows.push(json!({"pad": p.name, "net": p.net_name, "style": "thermal-via-grid", "escapeLayer": escape, "vias": at, "viaPitchMm": vp}));
    }
    // via to foreign copper: the nearest pad of another net, centre to edge (circles exact, rectangles by their circumcircle)
    let mut worst = f64::INFINITY;
    for v in &vias {
        for p in &pads {
            let (w, h) = fp.pads.iter().find(|q| q.number == p.pad).map(|q| (q.width.unwrap_or(0.0), q.height.unwrap_or(0.0))).unwrap_or((0.0, 0.0));
            let d = pcb::dist(*v, (p.x, p.y));
            if d < 1e-6 {
                continue;
            }
            worst = worst.min(d - w.max(h) / 2.0 - via_size / 2.0);
        }
    }
    let conflicts = fanout_conflicts(board, &calls, side, width, via_size, clearance);
    if !conflicts.is_empty() {
        warnings.push(format!("{} via(s) or stub(s) come closer than {clearance} mm to another net's pad: see conflicts, and drop or shorten them before routing", conflicts.len()));
    }
    let calls: Vec<Value> = calls.into_iter().map(|(net, paths)| json!({"net": net, "paths": paths, "width": width, "viaSize": via_size, "viaDrill": via_drill})).collect();
    let _ = fx;
    Ok(json!({
        "ref": fp.reference, "package": kind, "padCount": pads.len(), "pitchMm": pitch, "side": side, "escapeLayer": escape,
        "style": style, "requestedStyle": want, "dogboneRoomMm": dogbone_room, "dogboneFits": dogbone_fits,
        "via": {"size": via_size, "drill": via_drill}, "width": width, "clearanceMm": clearance,
        "pads": rows, "calls": calls, "callCount": calls.len(), "viaCount": vias.len(),
        "minViaToPadMm": if worst.is_finite() { json!(r3(worst)) } else { Value::Null }, "conflicts": conflicts,
        "warnings": warnings,
    }))
}

/// A fanout waypoint as a point and its layer: [x, y] (on `side`), {x, y, layer?}, or a pad as "U1.3" / {pad}
/// (its centre, on `side`).
fn waypoint(v: &Value, side: &str, pads: &[pcb::Pad]) -> Option<(P, String)> {
    let pad_at = |name: &str| pads.iter().find(|p| p.name.eq_ignore_ascii_case(name)).map(|p| ((p.x, p.y), side.to_string()));
    match v {
        Value::Array(a) => Some(((a.first()?.as_f64()?, a.get(1)?.as_f64()?), side.to_string())),
        Value::String(n) => pad_at(n),
        Value::Object(o) => match o.get("pad").and_then(Value::as_str) {
            Some(n) => pad_at(n),
            None => Some(((o.get("x")?.as_f64()?, o.get("y")?.as_f64()?), o.get("layer").and_then(Value::as_str).unwrap_or(side).to_string())),
        },
        _ => None,
    }
}

/// The copper plan_fanout would give an IC's pins on its own side, by net: (net, a, b, half-width), a via
/// being a = b; and the clearance that plan keeps. Nothing when the IC is no package plan_fanout plans.
fn fanout_pieces(board: &Board, ic: &str, side: &str) -> (Vec<(String, P, P, f64)>, f64) {
    let Ok(v) = plan_fanout(board, &json!({"ref": ic})) else { return (Vec::new(), 0.0) };
    let pads = pcb::pads(board);
    let mut out = Vec::new();
    for c in v["calls"].as_array().into_iter().flatten() {
        let net = c["net"].as_str().unwrap_or("").to_string();
        let (w, vs) = (c["width"].as_f64().unwrap_or(0.15), c["viaSize"].as_f64().unwrap_or(0.6));
        for path in c["paths"].as_array().into_iter().flatten() {
            let pts: Vec<(P, String)> = path.as_array().into_iter().flatten().filter_map(|q| waypoint(q, side, &pads)).collect();
            for wnd in pts.windows(2) {
                let ((a, la), (b, lb)) = (&wnd[0], &wnd[1]);
                if pcb::dist(*a, *b) < 1e-6 {
                    if la != lb {
                        out.push((net.clone(), *a, *a, vs / 2.0));
                    }
                } else if la == side {
                    out.push((net.clone(), *a, *b, w / 2.0));
                }
            }
        }
    }
    (out, v["clearanceMm"].as_f64().unwrap_or(0.1))
}

/// Every via and stub of a fanout plan against every other net's pad on the board, by the pad's real
/// outline (std #22, the engine's plan_fanout does the same): a via against pads on any layer, a stub
/// against pads on its own layer (and through-hole pads). A path of waypoints is a stub between two
/// points, or a via where two waypoints share a point on different layers. Closer than `clearance`
/// is a conflict.
fn fanout_conflicts(board: &Board, calls: &std::collections::BTreeMap<String, Vec<Value>>, side: &str, width: f64, via_size: f64, clearance: f64) -> Vec<Value> {
    let shapes = pad_shapes(board);
    let pads = pcb::pads(board);
    let wp = |v: &Value| waypoint(v, side, &pads);
    let on_layer = |s: &PadShape, l: &str| s.layers.iter().any(|x| x == l || x == "*.Cu");
    let mut out = Vec::new();
    for (net, paths) in calls {
        for path in paths {
            let pts: Vec<(P, String)> = path.as_array().into_iter().flatten().filter_map(wp).collect();
            for w in pts.windows(2) {
                let ((a, la), (b, lb)) = (&w[0], &w[1]);
                let via = pcb::dist(*a, *b) < 1e-6;
                if via && la == lb {
                    continue;
                }
                for s in shapes.iter().filter(|s| s.net != *net || net.is_empty()) {
                    if !via && !on_layer(s, la) {
                        continue;
                    }
                    let d = if via {
                        match s.circle {
                            Some(r) => (pcb::dist(*a, s.center) - r - via_size / 2.0).max(0.0),
                            None => point_to_poly(*a, &s.edges, via_size / 2.0),
                        }
                    } else {
                        let core = match s.circle {
                            Some(r) => seg_point(s.center, *a, *b) - r,
                            None if inside_edges(*a, &s.edges) || inside_edges(*b, &s.edges) => 0.0,
                            // a stub is one segment, not a closed outline: edges_distance would test a pad corner
                            // as inside it
                            None => s.edges.iter().map(|(c, d)| seg_seg(*a, *b, *c, *d)).fold(f64::INFINITY, f64::min),
                        };
                        (core - width / 2.0).max(0.0)
                    };
                    if d < clearance - 1e-9 {
                        out.push(json!({"net": net, "what": if via { "via" } else { "stub" }, "at": [pcb::round6(a.0), pcb::round6(a.1)], "layer": if via { Value::Null } else { json!(la) },
                            "pad": format!("{}.{}", s.reference, s.pad), "padNet": s.net, "gapMm": r3(d)}));
                    }
                }
            }
        }
    }
    out
}

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

    #[test]
    fn distances_between_outlines() {
        let a = rect_edges(&Rect { min_x: 0.0, min_y: 0.0, max_x: 1.0, max_y: 1.0 });
        let b = rect_edges(&Rect { min_x: 1.5, min_y: 0.0, max_x: 2.0, max_y: 1.0 });
        assert!((edges_distance(&a, &b) - 0.5).abs() < 1e-9);
        let c = rect_edges(&Rect { min_x: 0.2, min_y: 0.2, max_x: 0.4, max_y: 0.4 });
        assert_eq!(edges_distance(&a, &c), 0.0, "nested");
        assert!(is_ground("/GND") && is_ground("VSSA") && !is_ground("+3V3"));
    }

    #[test]
    fn supply_names() {
        for n in ["+3V3", "/5V_VCC", "VDD_IO", "/VBAT", "VIN", "1V8", "AVDD", "/VBUS", "-12V"] {
            assert!(is_supply(n), "{n}");
        }
        for n in ["/XTAL_IN", "/OSC32_OUT", "/SW", "/DRV_BSTA", "Net-(C1-Pad1)", "/NRST", "/ADC_IN"] {
            assert!(!is_supply(n), "{n}");
        }
    }

    #[test]
    fn decoupling_caps_go_to_their_nearest_ic() {
        // std #22: on the ESC board U1 took every +VBAT cap, including those beside U2
        let p = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../../../demo/routing/esc/esc-g431-fable-placed-planes.kicad_pcb");
        let b = pcb::parse_pcb_text(&std::fs::read_to_string(p).unwrap(), "esc.kicad_pcb").unwrap();
        let placed = |ic: &str| -> (Vec<String>, Vec<Value>) {
            let v = plan_decoupling(&b, &json!({"ic": ic})).unwrap();
            (v["placements"].as_array().unwrap().iter().map(|r| r["ref"].as_str().unwrap().to_string()).collect(), v["leftOut"].as_array().unwrap().clone())
        };
        let (u1, u1_out) = placed("U1");
        let (u2, _) = placed("U2");
        let (u3, _) = placed("U3");
        assert!(u1.contains(&"C5".to_string()), "C5 sits 4 mm from U1: {u1:?}");
        assert!(u1_out.iter().any(|o| o["ref"] == "C14" && o["reason"] == "nearer_another_ic" && o["ic"] == "U2"), "{u1_out:?}");
        for (a, b, an, bn) in [(&u1, &u2, "U1", "U2"), (&u1, &u3, "U1", "U3"), (&u2, &u3, "U2", "U3")] {
            assert!(a.iter().all(|c| !b.contains(c)), "a cap claimed by both {an} and {bn}: {a:?} {b:?}");
        }
        // caps named explicitly are placed as asked
        let v = plan_decoupling(&b, &json!({"ic": "U1", "caps": ["C14"]})).unwrap();
        assert_eq!(v["leftOut"], json!([]));
    }

    #[test]
    fn fanout_conflicts_measure_other_nets_pads() {
        let p = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../../../demo/routing/esc/esc-g431-fable-placed-planes.kicad_pcb");
        let b = pcb::parse_pcb_text(&std::fs::read_to_string(p).unwrap(), "esc.kicad_pcb").unwrap();
        let r12 = pcb::pads(&b).into_iter().find(|q| q.reference == "R12" && q.pad == "1").unwrap();
        let (x, y) = (r12.x, r12.y);
        let mut calls = std::collections::BTreeMap::new();
        // a stub of another net straight across R12.1, and a via of another net on it
        calls.insert("OTHER".to_string(), vec![json!([[x - 2.0, y], [x + 2.0, y]]), json!([{"x": x, "y": y, "layer": "F.Cu"}, {"x": x, "y": y, "layer": "B.Cu"}])]);
        // R12.1's own net touching it is fine
        calls.insert(r12.net_name.clone(), vec![json!([[x, y], [x + 0.01, y]])]);
        let c = fanout_conflicts(&b, &calls, "F.Cu", 0.15, 0.6, 0.1);
        assert!(c.iter().any(|k| k["what"] == "stub" && k["pad"] == "R12.1" && k["gapMm"] == 0.0), "{c:?}");
        assert!(c.iter().any(|k| k["what"] == "via" && k["pad"] == "R12.1"), "{c:?}");
        assert!(c.iter().all(|k| k["net"] == "OTHER"), "the pad's own net never conflicts: {c:?}");
        // a stub 5 mm away is clear: a single segment is not an outline a pad corner can sit "inside" (it was, and a
        // +12V stub at U4 conflicted with U5.1 across the board)
        let mut far = std::collections::BTreeMap::new();
        far.insert("OTHER".to_string(), vec![json!([[x - 2.0, y + 5.0], [x + 2.0, y + 5.0]])]);
        assert!(fanout_conflicts(&b, &far, "F.Cu", 0.15, 0.6, 0.1).iter().all(|k| k["pad"] != "R12.1"));
        // a fanout's waypoints start at a pad given by name: the stub from it is measured too
        let mut named = std::collections::BTreeMap::new();
        named.insert("OTHER".to_string(), vec![json!(["R12.2", [x, y]])]);
        assert!(fanout_conflicts(&b, &named, "F.Cu", 0.15, 0.6, 0.1).iter().any(|k| k["pad"] == "R12.1"));
        // a stub on B.Cu misses an SMD pad on F.Cu
        let mut back = std::collections::BTreeMap::new();
        back.insert("OTHER".to_string(), vec![json!([{"x": x - 2.0, "y": y, "layer": "B.Cu"}, {"x": x + 2.0, "y": y, "layer": "B.Cu"}])]);
        assert!(fanout_conflicts(&b, &back, "F.Cu", 0.15, 0.6, 0.1).iter().all(|k| k["pad"] != "R12.1"));
    }

    #[test]
    fn decoupling_leaves_room_for_the_fanout() {
        // std #22 leaveFanout: U5 (LQFP-48) on the unrouted ESC board; no placed cap pad may sit on another net's
        // escape stub or via
        let p = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../../../demo/placement/esc-g431-unrouted.kicad_pcb");
        let b = pcb::parse_pcb_text(&std::fs::read_to_string(p).unwrap(), "esc.kicad_pcb").unwrap();
        let v = plan_decoupling(&b, &json!({"ic": "U5"})).unwrap();
        assert_eq!(v["leaveFanout"], true);
        let (fan, clear) = fanout_pieces(&b, "U5", "F.Cu");
        assert!(fan.len() > 40 && v["fanoutPieces"].as_u64().unwrap() as usize == fan.len(), "{}", fan.len());
        for row in v["placements"].as_array().unwrap() {
            let cap = b.footprints.iter().find(|f| f.reference == row["ref"].as_str().unwrap()).unwrap();
            let at = (row["x"].as_f64().unwrap(), row["y"].as_f64().unwrap());
            for pd in &cap.pads {
                let c = placement::to_board(at, row["rotation"].as_f64().unwrap(), (pd.x.unwrap_or(0.0), pd.y.unwrap_or(0.0)));
                let rad = pd.width.unwrap_or(0.0).max(pd.height.unwrap_or(0.0)) / 2.0;
                let pnet = pd.net_name.clone().unwrap_or_default();
                for (n, a, bb, hw) in fan.iter().filter(|(n, ..)| *n != pnet) {
                    assert!(seg_point(c, *a, *bb) - rad - hw >= clear - 1e-9, "{} pad {} sits on {n}'s fanout", cap.reference, pd.number);
                }
            }
        }
        let off = plan_decoupling(&b, &json!({"ic": "U5", "leaveFanout": false})).unwrap();
        assert_eq!(off["fanoutPieces"], 0);
    }
}