KiCad - the KiCad Bridge

//! Manufacturability pre-flight from the board file (kicad_validate_for_fab): the outline,
//! copper widths and gaps, drills and rings, copper near the edge, silkscreen on pads,
//! vias in pads, acid traps, footprints without 3D models and missing fiducials, checked
//! against a fab profile. KiCad's own DRC (run by the verb layer) is folded in as one more
//! finding; this module is pure geometry and is tested without KiCad.
//!
//! Every copper item is modelled as a stadium (a segment swept by a radius): a track is
//! exact, a via or round pad is exact, a rectangular pad is approximated by the stadium
//! along its long axis (corners slightly rounded off), so gaps near rectangle corners are
//! reported a little larger than they are. KiCad's DRC remains the authority on spacing.

use std::collections::{BTreeMap, HashMap};

use serde_json::{json, Value};

use crate::model_check::{parse_sexpr, Sx};
use crate::pcb::{arc_points, Point};

pub type P = (f64, f64);

#[derive(Clone, Debug)]
pub struct Stadium {
    pub a: P,
    pub b: P,
    pub r: f64,
    /// Copper (or silkscreen) layer names; empty means "every copper layer".
    pub layers: Vec<String>,
    pub net: String,
    /// "R1.2" for a pad, "track", "via", or the footprint reference for silkscreen.
    pub owner: String,
    /// Footprint reference for pads and footprint silkscreen.
    pub fp: String,
    pub smd: bool,
}

impl Stadium {
    fn bbox(&self) -> (f64, f64, f64, f64) {
        (self.a.0.min(self.b.0) - self.r, self.a.1.min(self.b.1) - self.r, self.a.0.max(self.b.0) + self.r, self.a.1.max(self.b.1) + self.r)
    }
    fn on(&self, layer: &str) -> bool {
        self.layers.is_empty() || self.layers.iter().any(|l| l == layer)
    }
    fn shares_layer(&self, o: &Stadium) -> bool {
        if self.layers.is_empty() || o.layers.is_empty() {
            return true;
        }
        self.layers.iter().any(|l| o.on(l))
    }
}

#[derive(Clone, Debug)]
pub struct Hole {
    pub at: P,
    pub drill: f64,
    /// Copper diameter around it (0 for a non-plated hole).
    pub ring_dia: f64,
    pub via: bool,
    pub plated: bool,
    pub owner: String,
}

#[derive(Clone, Debug, Default)]
pub struct FpInfo {
    pub reference: String,
    pub footprint: String,
    pub value: String,
    pub attrs: Vec<String>,
    pub has_model: bool,
}

#[derive(Clone, Debug, Default)]
pub struct Geometry {
    pub copper_layers: Vec<String>,
    pub thickness: f64,
    pub tracks: Vec<Stadium>,
    pub vias: Vec<Stadium>,
    pub pads: Vec<Stadium>,
    pub holes: Vec<Hole>,
    /// Edge.Cuts as straight pieces (arcs and circles as chords).
    pub edges: Vec<(P, P)>,
    /// Endpoints of the open Edge.Cuts primitives (lines, arcs), for the closure check.
    pub open_ends: Vec<P>,
    pub closed_shapes: usize,
    pub silk: Vec<Stadium>,
    pub footprints: Vec<FpInfo>,
}

fn f(sx: &Sx, i: usize) -> Option<f64> {
    sx.atom_at(i)?.parse().ok()
}

fn pt(n: Option<&Sx>) -> Option<P> {
    let n = n?;
    Some((f(n, 1)?, f(n, 2)?))
}

fn layer_of(n: &Sx) -> Option<&str> {
    n.find("layer").and_then(Sx::value)
}

fn stroke_width(n: &Sx) -> f64 {
    n.find("stroke").and_then(|s| s.find("width")).and_then(|w| f(w, 1)).or_else(|| n.find("width").and_then(|w| f(w, 1))).unwrap_or(0.0)
}

/// Footprint-local to board: KiCad's y-down rotation (see `pcb::pads`).
#[derive(Clone, Copy)]
struct Xf {
    x: f64,
    y: f64,
    sin: f64,
    cos: f64,
}

impl Xf {
    fn id() -> Xf {
        Xf { x: 0.0, y: 0.0, sin: 0.0, cos: 1.0 }
    }
    fn of(fp: &Sx) -> Xf {
        let at = fp.find("at");
        let rot = at.and_then(|a| f(a, 3)).unwrap_or(0.0).to_radians();
        Xf { x: at.and_then(|a| f(a, 1)).unwrap_or(0.0), y: at.and_then(|a| f(a, 2)).unwrap_or(0.0), sin: rot.sin(), cos: rot.cos() }
    }
    fn p(&self, q: P) -> P {
        (self.x + q.0 * self.cos + q.1 * self.sin, self.y - q.0 * self.sin + q.1 * self.cos)
    }
}

/// The straight pieces of one graphic (line, rect, poly, circle, arc), transformed, and
/// whether the shape closes on itself.
fn shape_pieces(n: &Sx, xf: Xf) -> Option<(Vec<(P, P)>, bool, Option<(P, P)>)> {
    let tag = n.tag()?;
    let kind = tag.trim_start_matches("gr_").trim_start_matches("fp_");
    let mut out = Vec::new();
    match kind {
        "line" => {
            let (a, b) = (pt(n.find("start"))?, pt(n.find("end"))?);
            out.push((xf.p(a), xf.p(b)));
            Some((out, false, Some((xf.p(a), xf.p(b)))))
        }
        "arc" => {
            let (a, m, b) = (pt(n.find("start"))?, pt(n.find("mid"))?, pt(n.find("end"))?);
            let pts = arc_points(&Point { x: a.0, y: a.1 }, &Point { x: m.0, y: m.1 }, &Point { x: b.0, y: b.1 });
            for w in pts.windows(2) {
                out.push((xf.p((w[0].x, w[0].y)), xf.p((w[1].x, w[1].y))));
            }
            Some((out, false, Some((xf.p(a), xf.p(b)))))
        }
        "rect" => {
            let (a, b) = (pt(n.find("start"))?, pt(n.find("end"))?);
            let c = [(a.0, a.1), (b.0, a.1), (b.0, b.1), (a.0, b.1)];
            for i in 0..4 {
                out.push((xf.p(c[i]), xf.p(c[(i + 1) % 4])));
            }
            Some((out, true, None))
        }
        "circle" => {
            let (c, e) = (pt(n.find("center"))?, pt(n.find("end"))?);
            let r = dist(c, e);
            let k = 72;
            let at = |i: usize| {
                let t = std::f64::consts::TAU * i as f64 / k as f64;
                xf.p((c.0 + r * t.cos(), c.1 + r * t.sin()))
            };
            for i in 0..k {
                out.push((at(i), at(i + 1)));
            }
            Some((out, true, None))
        }
        "poly" => {
            let v: Vec<P> = n.find("pts")?.find_all("xy").filter_map(|xy| Some(xf.p((f(xy, 1)?, f(xy, 2)?)))).collect();
            if v.len() < 2 {
                return None;
            }
            for i in 0..v.len() {
                out.push((v[i], v[(i + 1) % v.len()]));
            }
            Some((out, true, None))
        }
        _ => None,
    }
}

impl Geometry {
    pub fn from_text(text: &str) -> Result<Geometry, String> {
        let tree = parse_sexpr(text).ok_or("empty board file")?;
        if tree.tag() != Some("kicad_pcb") {
            return Err("not a kicad_pcb file".into());
        }
        let mut g = Geometry {
            thickness: tree.find("general").and_then(|g| g.find("thickness")).and_then(|t| f(t, 1)).unwrap_or(1.6),
            ..Default::default()
        };
        if let Some(layers) = tree.find("layers").and_then(Sx::as_list) {
            for l in layers.iter().skip(1) {
                if let Some(name) = l.atom_at(1) {
                    if name.ends_with(".Cu") {
                        g.copper_layers.push(name.to_string());
                    }
                }
            }
        }
        let net_of = |n: &Sx| -> String {
            let Some(net) = n.find("net") else { return String::new() };
            // KiCad <= 9: (net 3 "GND"); KiCad 10: (net "GND").
            match (net.atom_at(1), net.atom_at(2)) {
                (Some(_), Some(name)) => name.to_string(),
                (Some(a), None) if a.parse::<i64>().is_err() => a.to_string(),
                (Some(a), None) => format!("#{a}"),
                _ => String::new(),
            }
        };
        let net_of = &net_of;
        for (tag, is_arc) in [("segment", false), ("arc", true)] {
            for t in tree.find_all(tag) {
                let w = t.find("width").and_then(|w| f(w, 1)).unwrap_or(0.0);
                let layer = layer_of(t).unwrap_or("F.Cu").to_string();
                let net = net_of(t);
                let pieces: Vec<(P, P)> = if is_arc {
                    match (pt(t.find("start")), pt(t.find("mid")), pt(t.find("end"))) {
                        (Some(a), Some(m), Some(b)) => arc_points(&Point { x: a.0, y: a.1 }, &Point { x: m.0, y: m.1 }, &Point { x: b.0, y: b.1 }).windows(2).map(|w| ((w[0].x, w[0].y), (w[1].x, w[1].y))).collect(),
                        _ => continue,
                    }
                } else {
                    match (pt(t.find("start")), pt(t.find("end"))) {
                        (Some(a), Some(b)) => vec![(a, b)],
                        _ => continue,
                    }
                };
                for (a, b) in pieces {
                    g.tracks.push(Stadium { a, b, r: w / 2.0, layers: vec![layer.clone()], net: net.clone(), owner: "track".into(), fp: String::new(), smd: false });
                }
            }
        }
        for v in tree.find_all("via") {
            let Some(at) = pt(v.find("at")) else { continue };
            let size = v.find("size").and_then(|s| f(s, 1)).unwrap_or(0.0);
            let drill = v.find("drill").and_then(|s| f(s, 1)).unwrap_or(0.0);
            g.vias.push(Stadium { a: at, b: at, r: size / 2.0, layers: Vec::new(), net: net_of(v), owner: "via".into(), fp: String::new(), smd: false });
            g.holes.push(Hole { at, drill, ring_dia: size, via: true, plated: true, owner: format!("via at ({}, {})", fmt(at.0), fmt(at.1)) });
        }
        for n in tree.as_list().unwrap_or(&[]) {
            let Some(tag) = n.tag() else { continue };
            if !tag.starts_with("gr_") {
                continue;
            }
            g.add_graphic(n, Xf::id(), "");
        }
        for fp in tree.find_all("footprint") {
            let xf = Xf::of(fp);
            let mut reference = String::new();
            let mut value = String::new();
            for p in fp.find_all("property") {
                match p.atom_at(1) {
                    Some("Reference") => reference = p.atom_at(2).unwrap_or("").to_string(),
                    Some("Value") => value = p.atom_at(2).unwrap_or("").to_string(),
                    _ => {}
                }
            }
            if reference.is_empty() {
                // KiCad 7 and older: (fp_text reference "R1")
                if let Some(t) = fp.find_all("fp_text").find(|t| t.atom_at(1) == Some("reference")) {
                    reference = t.atom_at(2).unwrap_or("").to_string();
                }
            }
            let attrs: Vec<String> = fp.find("attr").and_then(Sx::as_list).map(|l| l.iter().skip(1).filter_map(Sx::as_atom).map(str::to_string).collect()).unwrap_or_default();
            g.footprints.push(FpInfo { reference: reference.clone(), footprint: fp.atom_at(1).unwrap_or("").to_string(), value, attrs, has_model: fp.find("model").is_some() });
            for child in fp.as_list().unwrap_or(&[]) {
                if child.tag().map(|t| t.starts_with("fp_")).unwrap_or(false) {
                    g.add_graphic(child, xf, &reference);
                }
            }
            for pad in fp.find_all("pad") {
                let kind = pad.atom_at(2).unwrap_or("");
                let Some(local) = pt(pad.find("at")) else { continue };
                let ang = pad.find("at").and_then(|a| f(a, 3)).unwrap_or(0.0).to_radians();
                let c = xf.p(local);
                let (w, h) = pad.find("size").map(|s| (f(s, 1).unwrap_or(0.0), f(s, 2).unwrap_or(0.0))).unwrap_or((0.0, 0.0));
                let layers: Vec<String> = pad.find("layers").and_then(Sx::as_list).map(|l| l.iter().skip(1).filter_map(Sx::as_atom).map(str::to_string).collect()).unwrap_or_default();
                let copper: Vec<String> = if layers.iter().any(|l| l == "*.Cu") {
                    Vec::new()
                } else {
                    layers.iter().filter(|l| l.ends_with(".Cu")).cloned().collect()
                };
                let drill = pad.find("drill").and_then(|d| {
                    let nums: Vec<f64> = d.as_list().unwrap_or(&[]).iter().skip(1).filter_map(Sx::as_atom).filter_map(|a| a.parse().ok()).collect();
                    nums.iter().cloned().fold(None, |m: Option<f64>, x| Some(m.map_or(x, |m| m.min(x))))
                });
                let number = pad.atom_at(1).unwrap_or("").to_string();
                let owner = format!("{reference}.{number}");
                if kind == "np_thru_hole" {
                    if let Some(d) = drill {
                        g.holes.push(Hole { at: c, drill: d, ring_dia: 0.0, via: false, plated: false, owner: owner.clone() });
                    }
                    // A non-plated hole carries no copper unless its size exceeds the drill.
                    if w <= drill.unwrap_or(0.0) + 1e-6 {
                        continue;
                    }
                }
                if kind == "thru_hole" {
                    if let Some(d) = drill {
                        g.holes.push(Hole { at: c, drill: d, ring_dia: w.min(h), via: false, plated: true, owner: owner.clone() });
                    }
                }
                let has_copper = copper.is_empty() && layers.iter().any(|l| l == "*.Cu") || !copper.is_empty();
                if !has_copper {
                    continue;
                }
                let (long, short) = if w >= h { (w, h) } else { (h, w) };
                let half = (long - short) / 2.0;
                // the long axis in board coordinates: pad angle is absolute, y down
                let axis_ang = if w >= h { ang } else { ang + std::f64::consts::FRAC_PI_2 };
                let d = (axis_ang.cos() * half, -axis_ang.sin() * half);
                g.pads.push(Stadium {
                    a: (c.0 - d.0, c.1 - d.1),
                    b: (c.0 + d.0, c.1 + d.1),
                    r: short / 2.0,
                    layers: copper,
                    net: net_of(pad),
                    owner,
                    fp: reference.clone(),
                    smd: kind == "smd",
                });
            }
        }
        Ok(g)
    }

    fn add_graphic(&mut self, n: &Sx, xf: Xf, fp: &str) {
        let Some(layer) = layer_of(n) else { return };
        let silk = matches!(layer, "F.SilkS" | "B.SilkS" | "F.Silkscreen" | "B.Silkscreen");
        if layer != "Edge.Cuts" && !silk {
            return;
        }
        let Some((pieces, closed, ends)) = shape_pieces(n, xf) else { return };
        if layer == "Edge.Cuts" {
            if closed {
                self.closed_shapes += 1;
            } else if let Some((a, b)) = ends {
                self.open_ends.push(a);
                self.open_ends.push(b);
            }
            self.edges.extend(pieces);
        } else {
            let side = if layer.starts_with('F') { "F.Cu" } else { "B.Cu" };
            let r = stroke_width(n) / 2.0;
            for (a, b) in pieces {
                self.silk.push(Stadium { a, b, r, layers: vec![side.into()], net: String::new(), owner: fp.to_string(), fp: fp.to_string(), smd: false });
            }
        }
    }

    /// (closed, dangling endpoints). Open pieces must meet end to end within 10 um.
    pub fn outline_closed(&self) -> (bool, Vec<P>) {
        if self.edges.is_empty() {
            return (false, Vec::new());
        }
        let key = |p: P| ((p.0 * 100.0).round() as i64, (p.1 * 100.0).round() as i64);
        let mut deg: HashMap<(i64, i64), (usize, P)> = HashMap::new();
        for &p in &self.open_ends {
            let e = deg.entry(key(p)).or_insert((0, p));
            e.0 += 1;
        }
        let mut dangling: Vec<P> = deg.values().filter(|(d, _)| d % 2 == 1).map(|(_, p)| *p).collect();
        dangling.sort_by(|a, b| a.partial_cmp(b).unwrap());
        (dangling.is_empty(), dangling)
    }

    pub fn outline_size(&self) -> Option<(f64, f64)> {
        if self.edges.is_empty() {
            return None;
        }
        let (mut x0, mut y0, mut x1, mut y1) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
        for (a, b) in &self.edges {
            for p in [a, b] {
                x0 = x0.min(p.0);
                y0 = y0.min(p.1);
                x1 = x1.max(p.0);
                y1 = y1.max(p.1);
            }
        }
        Some((x1 - x0, y1 - y0))
    }

    pub fn min_track(&self) -> Option<f64> {
        self.tracks.iter().map(|t| t.r * 2.0).filter(|w| *w > 0.0).fold(None, |m, w| Some(m.map_or(w, |m: f64| m.min(w))))
    }

    fn copper(&self) -> Vec<&Stadium> {
        self.tracks.iter().chain(self.vias.iter()).chain(self.pads.iter()).collect()
    }

    /// Every copper gap between items of different nets on a shared layer, smallest first
    /// (gap, item, item, where). Pads of one footprint are not paired (the land pattern's
    /// own pitch is the part maker's call). Items with no net are skipped.
    pub fn gaps(&self, below: f64) -> Vec<(f64, String, String, P)> {
        let items = self.copper();
        let boxes: Vec<_> = items.iter().map(|s| s.bbox()).collect();
        let mut out = Vec::new();
        for (i, j) in near_pairs(&boxes, &boxes, below, true) {
            let (a, b) = (items[i], items[j]);
            if a.net.is_empty() || b.net.is_empty() || a.net == b.net || !a.shares_layer(b) {
                continue;
            }
            if !a.fp.is_empty() && a.fp == b.fp {
                continue;
            }
            let (d, at) = seg_seg(a.a, a.b, b.a, b.b);
            let gap = d - a.r - b.r;
            if gap < below {
                out.push((gap, label(a), label(b), at));
            }
        }
        out.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
        out
    }

    /// The smallest copper gap found (within 1 mm), if any.
    pub fn min_space(&self) -> Option<(f64, String, String, P)> {
        self.gaps(1.0).into_iter().next()
    }

    /// Copper closer than `limit` to the board edge, smallest first.
    pub fn edge_gaps(&self, limit: f64) -> Vec<(f64, String, P)> {
        let items = self.copper();
        let boxes: Vec<_> = items.iter().map(|s| s.bbox()).collect();
        let eboxes: Vec<_> = self.edges.iter().map(|(a, b)| (a.0.min(b.0), a.1.min(b.1), a.0.max(b.0), a.1.max(b.1))).collect();
        let mut best: BTreeMap<usize, (f64, P)> = BTreeMap::new();
        for (i, j) in near_pairs(&boxes, &eboxes, limit, false) {
            let s = items[i];
            let (a, b) = self.edges[j];
            let (d, at) = seg_seg(s.a, s.b, a, b);
            let gap = d - s.r;
            if gap < limit {
                let e = best.entry(i).or_insert((gap, at));
                if gap < e.0 {
                    *e = (gap, at);
                }
            }
        }
        let mut out: Vec<(f64, String, P)> = best.into_iter().map(|(i, (g, at))| (g, label(items[i]), at)).collect();
        out.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
        out
    }

    /// Silkscreen strokes that land on a pad of the same side: (footprint ref or "board", pad).
    pub fn silk_on_pads(&self) -> Vec<(String, String, P)> {
        let sb: Vec<_> = self.silk.iter().map(|s| s.bbox()).collect();
        let pb: Vec<_> = self.pads.iter().map(|s| s.bbox()).collect();
        let mut seen = std::collections::BTreeSet::new();
        let mut out = Vec::new();
        for (i, j) in near_pairs(&sb, &pb, 0.0, false) {
            let (s, p) = (&self.silk[i], &self.pads[j]);
            if !p.on(&s.layers[0]) {
                continue;
            }
            let (d, at) = seg_seg(s.a, s.b, p.a, p.b);
            if d < s.r + p.r - 1e-6 && seen.insert((s.owner.clone(), p.owner.clone())) {
                out.push((if s.owner.is_empty() { "board".into() } else { s.owner.clone() }, p.owner.clone(), at));
            }
        }
        out.sort_by(|a, b| a.1.cmp(&b.1));
        out.dedup_by(|a, b| a.0 == b.0 && a.1 == b.1);
        out
    }

    /// Vias whose centre lies inside an SMD pad: (via, pad).
    pub fn vias_in_pads(&self) -> Vec<(String, String, P)> {
        let vb: Vec<_> = self.vias.iter().map(|s| s.bbox()).collect();
        let pb: Vec<_> = self.pads.iter().map(|s| s.bbox()).collect();
        let mut out = Vec::new();
        for (i, j) in near_pairs(&vb, &pb, 0.0, false) {
            let (v, p) = (&self.vias[i], &self.pads[j]);
            if !p.smd {
                continue;
            }
            let (d, _) = seg_seg(v.a, v.a, p.a, p.b);
            if d < p.r {
                out.push((format!("via at ({}, {})", fmt(v.a.0), fmt(v.a.1)), p.owner.clone(), v.a));
            }
        }
        out
    }

    /// Track joints where two tracks of one net meet at an acute angle (under 90 degrees),
    /// away from pads and vias that would fill the wedge: (angle, layer, net, where).
    pub fn acid_traps(&self) -> Vec<(f64, String, String, P)> {
        let key = |p: P| ((p.0 * 1000.0).round() as i64, (p.1 * 1000.0).round() as i64);
        let mut joints: HashMap<(String, String, (i64, i64)), Vec<P>> = HashMap::new();
        for t in &self.tracks {
            if dist(t.a, t.b) < 1e-6 {
                continue;
            }
            let layer = t.layers.first().cloned().unwrap_or_default();
            joints.entry((layer.clone(), t.net.clone(), key(t.a))).or_default().push((t.b.0 - t.a.0, t.b.1 - t.a.1));
            joints.entry((layer, t.net.clone(), key(t.b))).or_default().push((t.a.0 - t.b.0, t.a.1 - t.b.1));
        }
        let mut out = Vec::new();
        for ((layer, net, k), dirs) in joints {
            if dirs.len() < 2 {
                continue;
            }
            let at = (k.0 as f64 / 1000.0, k.1 as f64 / 1000.0);
            let covered = self.pads.iter().chain(self.vias.iter()).any(|p| p.on(&layer) && seg_seg(at, at, p.a, p.b).0 <= p.r + 1e-6);
            if covered {
                continue;
            }
            let mut worst: Option<f64> = None;
            for i in 0..dirs.len() {
                for j in i + 1..dirs.len() {
                    let ang = angle_between(dirs[i], dirs[j]);
                    if ang > 1.0 && ang < 89.5 {
                        worst = Some(worst.map_or(ang, |w: f64| w.min(ang)));
                    }
                }
            }
            if let Some(a) = worst {
                out.push(((a * 10.0).round() / 10.0, layer, net, at));
            }
        }
        out.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap().then(a.3.partial_cmp(&b.3).unwrap()));
        out
    }
}

fn label(s: &Stadium) -> String {
    match s.owner.as_str() {
        "track" => format!("track on {} ({})", s.layers.first().map(String::as_str).unwrap_or("?"), s.net),
        "via" => format!("via ({})", s.net),
        o => format!("pad {o} ({})", s.net),
    }
}

pub fn fmt(v: f64) -> String {
    crate::schematic::fmt_num(v)
}

pub fn dist(a: P, b: P) -> f64 {
    ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt()
}

fn angle_between(u: P, v: P) -> f64 {
    let d = (u.0 * v.0 + u.1 * v.1) / ((u.0.hypot(u.1)) * (v.0.hypot(v.1)));
    d.clamp(-1.0, 1.0).acos().to_degrees()
}

/// Closest point on segment ab to p.
fn closest(p: P, a: P, b: P) -> P {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let l2 = dx * dx + dy * dy;
    if l2 < 1e-18 {
        return a;
    }
    let t = (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / l2).clamp(0.0, 1.0);
    (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)
}

/// Distance between segments ab and cd, and a point between them where it is reached.
pub fn seg_seg(a: P, b: P, c: P, d: P) -> (f64, P) {
    let d1 = cross(c, d, a);
    let d2 = cross(c, d, b);
    let d3 = cross(a, b, c);
    let d4 = cross(a, b, d);
    if ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0)) && ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0)) {
        let t = d1 / (d1 - d2);
        return (0.0, (a.0 + t * (b.0 - a.0), a.1 + t * (b.1 - a.1)));
    }
    let cands = [(a, closest(a, c, d)), (b, closest(b, c, d)), (closest(c, a, b), c), (closest(d, a, b), d)];
    let mut best = (f64::MAX, a);
    for (p, q) in cands {
        let dd = dist(p, q);
        if dd < best.0 {
            best = (dd, ((p.0 + q.0) / 2.0, (p.1 + q.1) / 2.0));
        }
    }
    best
}

type BBox = (f64, f64, f64, f64);

/// Index pairs (i in a, j in b) whose boxes come within `margin`, through a uniform grid.
/// With `same` (a and b are one list) each unordered pair is returned once, i < j.
fn near_pairs(a: &[BBox], b: &[BBox], margin: f64, same: bool) -> Vec<(usize, usize)> {
    let cell = 2.0f64.max(margin * 2.0);
    let ci = |v: f64| (v / cell).floor() as i64;
    let mut grid: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
    for (j, bb) in b.iter().enumerate() {
        for gx in ci(bb.0)..=ci(bb.2) {
            for gy in ci(bb.1)..=ci(bb.3) {
                grid.entry((gx, gy)).or_default().push(j);
            }
        }
    }
    let mut seen = std::collections::HashSet::new();
    let mut out = Vec::new();
    for (i, ab) in a.iter().enumerate() {
        let e = (ab.0 - margin, ab.1 - margin, ab.2 + margin, ab.3 + margin);
        for gx in ci(e.0)..=ci(e.2) {
            for gy in ci(e.1)..=ci(e.3) {
                let Some(list) = grid.get(&(gx, gy)) else { continue };
                for &j in list {
                    if same && j <= i {
                        continue;
                    }
                    let bb = b[j];
                    if bb.0 > e.2 || bb.2 < e.0 || bb.1 > e.3 || bb.3 < e.1 {
                        continue;
                    }
                    if seen.insert((i, j)) {
                        out.push((i, j));
                    }
                }
            }
        }
    }
    out
}

// ---------------------------------------------------------------------------
// Fab profiles
// ---------------------------------------------------------------------------

#[derive(Clone, Debug, PartialEq)]
pub struct Profile {
    pub name: String,
    pub min_track: f64,
    pub min_space: f64,
    pub min_drill: f64,
    pub min_annular: f64,
    pub min_edge: f64,
    pub layer_counts: Vec<u32>,
    pub source: Vec<String>,
}

pub const PROFILES: &[&str] = &["generic", "jlcpcb"];

/// The bridge's built-in approximations. A staged `<stem>.kicad_dru` and explicit args win.
pub fn builtin_profile(name: &str) -> Option<Profile> {
    match name {
        "generic" => Some(Profile {
            name: "generic".into(),
            min_track: 0.15,
            min_space: 0.15,
            min_drill: 0.3,
            min_annular: 0.13,
            min_edge: 0.3,
            layer_counts: (1..=32).collect(),
            source: vec!["built-in generic profile (6 mil track and space, 0.3 mm drill, 0.13 mm ring, 0.3 mm copper to edge)".into()],
        }),
        "jlcpcb" => Some(Profile {
            name: "jlcpcb".into(),
            min_track: 0.127,
            min_space: 0.127,
            min_drill: 0.3,
            min_annular: 0.075,
            min_edge: 0.3,
            layer_counts: vec![1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20],
            source: vec!["built-in JLCPCB standard-process approximation (5 mil track and space, 0.3 mm drill, 0.075 mm via ring, 0.3 mm copper to edge)".into()],
        }),
        _ => None,
    }
}

/// A KiCad length: "0.127mm", "5mil", "0.005in", or a bare number in mm.
pub fn dru_length(s: &str) -> Option<f64> {
    let t = s.trim();
    let (num, mul) = if let Some(n) = t.strip_suffix("mm") {
        (n, 1.0)
    } else if let Some(n) = t.strip_suffix("mil") {
        (n, 0.0254)
    } else if let Some(n) = t.strip_suffix("in") {
        (n, 25.4)
    } else if let Some(n) = t.strip_suffix("um") {
        (n, 0.001)
    } else {
        (t, 1.0)
    };
    num.trim().parse::<f64>().ok().map(|v| v * mul)
}

/// The most permissive `min` of each constraint in a .kicad_dru (KiCad custom rules):
/// track_width, clearance, hole_size, annular_width, edge_clearance.
pub fn dru_minimums(text: &str) -> BTreeMap<String, f64> {
    let cleaned: String = text.lines().filter(|l| !l.trim_start().starts_with('#')).collect::<Vec<_>>().join("\n");
    let mut out: BTreeMap<String, f64> = BTreeMap::new();
    let Some(root) = parse_sexpr(&format!("(dru {cleaned})")) else { return out };
    for rule in root.find_all("rule") {
        for c in rule.find_all("constraint") {
            let Some(kind) = c.atom_at(1) else { continue };
            let Some(min) = c.find("min").and_then(|m| m.atom_at(1)).and_then(dru_length) else { continue };
            let e = out.entry(kind.to_string()).or_insert(min);
            if min < *e {
                *e = min;
            }
        }
    }
    out
}

/// Apply a .kicad_dru's minimums onto a profile.
pub fn apply_dru(p: &mut Profile, text: &str, source: &str) -> usize {
    let m = dru_minimums(text);
    let mut n = 0;
    for (k, slot) in [("track_width", &mut p.min_track), ("clearance", &mut p.min_space), ("hole_size", &mut p.min_drill), ("annular_width", &mut p.min_annular), ("edge_clearance", &mut p.min_edge)] {
        if let Some(v) = m.get(k) {
            *slot = *v;
            n += 1;
        }
    }
    if n > 0 {
        p.source.push(format!("{n} minimum(s) from {source}"));
    }
    n
}

// ---------------------------------------------------------------------------
// The pre-flight
// ---------------------------------------------------------------------------

pub struct Options {
    pub assembly: bool,
    pub max_items: usize,
}

fn finding(check: &str, severity: &str, message: String, items: Vec<Value>, max: usize) -> Value {
    let count = items.len();
    json!({"check": check, "severity": severity, "message": message, "count": count, "items": items.into_iter().take(max).collect::<Vec<_>>()})
}

fn at(p: P) -> Value {
    json!({"x": (p.0 * 1000.0).round() / 1000.0, "y": (p.1 * 1000.0).round() / 1000.0})
}

/// Run every board-file check. `drc` is kicad-cli's raw DRC report when it ran, or a
/// reason it did not. Returns {pass, errors, warnings, findings, checked, profile}.
pub fn validate(g: &Geometry, p: &Profile, opts: &Options, drc: Result<&Value, &str>) -> Value {
    let max = opts.max_items.max(1);
    let mut findings: Vec<Value> = Vec::new();
    let mut checked: Vec<&str> = Vec::new();

    checked.push("outline");
    let (closed, dangling) = g.outline_closed();
    if g.edges.is_empty() {
        findings.push(finding("outline", "error", "No board outline: nothing on Edge.Cuts.".into(), vec![], max));
    } else if !closed {
        findings.push(finding("outline", "error", format!("The Edge.Cuts outline is not closed: {} loose end(s).", dangling.len()), dangling.iter().map(|d| at(*d)).collect(), max));
    }

    checked.push("layer_count");
    let n = g.copper_layers.len() as u32;
    if !p.layer_counts.contains(&n) {
        findings.push(finding("layer_count", "error", format!("{n} copper layers; the {} profile builds {:?}.", p.name, p.layer_counts), vec![], max));
    }

    checked.push("min_track");
    let thin: Vec<&Stadium> = g.tracks.iter().filter(|t| t.r * 2.0 < p.min_track - 1e-6).collect();
    if !thin.is_empty() {
        let w = thin.iter().map(|t| t.r * 2.0).fold(f64::MAX, f64::min);
        findings.push(finding("min_track", "error", format!("{} track piece(s) narrower than {} mm (narrowest {} mm).", thin.len(), fmt(p.min_track), fmt(w)), thin.iter().map(|t| json!({"width": t.r * 2.0, "layer": t.layers.first(), "net": t.net, "at": at(t.a)})).collect(), max));
    }

    checked.push("min_space");
    let gaps = g.gaps(p.min_space - 1e-6);
    if !gaps.is_empty() {
        findings.push(finding("min_space", "error", format!("{} copper gap(s) under {} mm (smallest {} mm).", gaps.len(), fmt(p.min_space), fmt(gaps[0].0.max(0.0))), gaps.iter().map(|(gap, a, b, w)| json!({"gap": (gap.max(0.0) * 1000.0).round() / 1000.0, "between": [a, b], "at": at(*w)})).collect(), max));
    }

    checked.push("min_drill");
    let small: Vec<&Hole> = g.holes.iter().filter(|h| h.drill > 0.0 && h.drill < p.min_drill - 1e-6).collect();
    if !small.is_empty() {
        findings.push(finding("min_drill", "error", format!("{} hole(s) smaller than {} mm.", small.len(), fmt(p.min_drill)), small.iter().map(|h| json!({"drill": h.drill, "owner": h.owner, "at": at(h.at)})).collect(), max));
    }

    checked.push("annular_ring");
    let rings: Vec<&Hole> = g.holes.iter().filter(|h| h.plated && h.ring_dia > 0.0 && (h.ring_dia - h.drill) / 2.0 < p.min_annular - 1e-6).collect();
    if !rings.is_empty() {
        findings.push(finding("annular_ring", "error", format!("{} plated hole(s) with a copper ring under {} mm.", rings.len(), fmt(p.min_annular)), rings.iter().map(|h| json!({"ring": ((h.ring_dia - h.drill) / 2.0 * 1000.0).round() / 1000.0, "owner": h.owner, "at": at(h.at)})).collect(), max));
    }

    checked.push("edge_clearance");
    if !g.edges.is_empty() {
        let near = g.edge_gaps(p.min_edge - 1e-6);
        let crossing = near.iter().filter(|x| x.0 < 0.0).count();
        if !near.is_empty() {
            findings.push(finding(
                "edge_clearance",
                if crossing > 0 { "error" } else { "warning" },
                format!("{} copper item(s) closer than {} mm to the board edge{}.", near.len(), fmt(p.min_edge), if crossing > 0 { format!(", {crossing} over it") } else { String::new() }),
                near.iter().map(|(gap, who, w)| json!({"gap": (gap * 1000.0).round() / 1000.0, "item": who, "at": at(*w)})).collect(),
                max,
            ));
        }
    }

    checked.push("silk_over_pads");
    let silk = g.silk_on_pads();
    if !silk.is_empty() {
        findings.push(finding("silk_over_pads", "warning", format!("{} silkscreen stroke(s) on exposed pads (the fab clips them, or they stop solder wetting).", silk.len()), silk.iter().map(|(who, pad, w)| json!({"silk": who, "pad": pad, "at": at(*w)})).collect(), max));
    }

    checked.push("via_in_pad");
    let vip = g.vias_in_pads();
    if !vip.is_empty() {
        findings.push(finding("via_in_pad", "warning", format!("{} via(s) inside SMD pads: order filled and capped vias, or solder wicks down the hole.", vip.len()), vip.iter().map(|(v, pad, w)| json!({"via": v, "pad": pad, "at": at(*w)})).collect(), max));
    }

    checked.push("acid_traps");
    let traps = g.acid_traps();
    if !traps.is_empty() {
        findings.push(finding("acid_traps", "warning", format!("{} track joint(s) at an acute angle (acid traps).", traps.len()), traps.iter().map(|(a, l, n, w)| json!({"angle": a, "layer": l, "net": n, "at": at(*w)})).collect(), max));
    }

    checked.push("3d_models");
    let no_model: Vec<&FpInfo> = g.footprints.iter().filter(|f| !f.has_model && !f.attrs.iter().any(|a| a == "board_only" || a == "exclude_from_pos_files") && !f.reference.starts_with('#')).collect();
    if !no_model.is_empty() {
        findings.push(finding("3d_models", "info", format!("{} footprint(s) without a 3D model (the STEP export and the 3D check will miss them).", no_model.len()), no_model.iter().map(|f| json!({"ref": f.reference, "footprint": f.footprint})).collect(), max));
    }

    checked.push("fiducials");
    if opts.assembly {
        let fids = g.footprints.iter().filter(|f| f.reference.to_uppercase().starts_with("FID") || f.footprint.to_lowercase().contains("fiducial")).count();
        if fids == 0 {
            findings.push(finding("fiducials", "warning", "Assembly requested but the board has no fiducials. Most assembly lines want three (or panel fiducials on the rails).".into(), vec![], max));
        }
    }

    checked.push("drc");
    match drc {
        Ok(report) => {
            let summary = crate::cli::summarize_report(report);
            let errors = summary["errors"].as_u64().unwrap_or(0);
            let unconnected = summary["unconnected"].as_u64().unwrap_or(0);
            let viol_errors = errors.saturating_sub(unconnected);
            if viol_errors > 0 {
                findings.push(finding("drc", "error", format!("KiCad DRC: {viol_errors} error(s)."), summary["first"].as_array().cloned().unwrap_or_default().into_iter().filter(|v| v["type"] != "unconnected_items").collect(), max));
            }
            if unconnected > 0 {
                findings.push(finding("unconnected", "error", format!("KiCad DRC: {unconnected} unconnected item(s): the board is not fully routed."), vec![], max));
            }
        }
        Err(why) => findings.push(finding("drc", "warning", format!("KiCad DRC did not run ({why}); DRC errors and unconnected items are not checked, so a pass is provisional."), vec![], max)),
    }

    let errors = findings.iter().filter(|f| f["severity"] == "error").count();
    let warnings = findings.iter().filter(|f| f["severity"] == "warning").count();
    json!({
        "pass": errors == 0,
        "errors": errors,
        "warnings": warnings,
        "findings": findings,
        "checked": checked,
        "profile": {"name": p.name, "minTrackMm": p.min_track, "minSpaceMm": p.min_space, "minDrillMm": p.min_drill, "minAnnularMm": p.min_annular, "minEdgeClearanceMm": p.min_edge, "layerCounts": p.layer_counts, "source": p.source},
        "board": {"copperLayers": g.copper_layers.len(), "thicknessMm": g.thickness, "size": g.outline_size().map(|(w, h)| json!({"widthMm": (w * 1000.0).round() / 1000.0, "heightMm": (h * 1000.0).round() / 1000.0})), "footprints": g.footprints.len(), "tracks": g.tracks.len(), "vias": g.vias.len(), "holes": g.holes.len()},
    })
}

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

    fn board(body: &str) -> String {
        format!("(kicad_pcb (version 20260206) (generator \"t\") (general (thickness 1.6)) (layers (0 \"F.Cu\" signal) (2 \"B.Cu\" signal) (25 \"Edge.Cuts\" user) (5 \"F.SilkS\" user \"F.Silkscreen\"))\n{body}\n)")
    }

    const OUTLINE: &str = "(gr_line (start 0 0) (end 40 0) (layer \"Edge.Cuts\")) (gr_line (start 40 0) (end 40 30) (layer \"Edge.Cuts\")) (gr_line (start 40 30) (end 0 30) (layer \"Edge.Cuts\")) (gr_line (start 0 30) (end 0 0) (layer \"Edge.Cuts\"))";

    #[test]
    fn outline_closure_and_size() {
        let g = Geometry::from_text(&board(OUTLINE)).unwrap();
        assert_eq!(g.outline_closed(), (true, vec![]));
        assert_eq!(g.outline_size(), Some((40.0, 30.0)));
        let open = OUTLINE.replace("(gr_line (start 0 30) (end 0 0) (layer \"Edge.Cuts\"))", "(gr_line (start 0 30) (end 0 1) (layer \"Edge.Cuts\"))");
        let g = Geometry::from_text(&board(&open)).unwrap();
        let (closed, dangling) = g.outline_closed();
        assert!(!closed);
        assert_eq!(dangling, vec![(0.0, 0.0), (0.0, 1.0)]);
        let g = Geometry::from_text(&board("(gr_circle (center 5 5) (end 10 5) (layer \"Edge.Cuts\"))")).unwrap();
        assert!(g.outline_closed().0);
        assert!(!Geometry::from_text(&board("")).unwrap().outline_closed().0);
    }

    #[test]
    fn spacing_tracks_drills_and_rings() {
        let body = format!(
            "{OUTLINE}
            (segment (start 5 10) (end 30 10) (width 0.2) (layer \"F.Cu\") (net \"A\"))
            (segment (start 5 10.3) (end 30 10.3) (width 0.1) (layer \"F.Cu\") (net \"B\"))
            (segment (start 5 20) (end 30 20) (width 0.2) (layer \"B.Cu\") (net \"C\"))
            (via (at 20 25) (size 0.45) (drill 0.2) (layers \"F.Cu\" \"B.Cu\") (net \"A\"))"
        );
        let g = Geometry::from_text(&board(&body)).unwrap();
        assert_eq!(g.min_track(), Some(0.1));
        let (gap, a, b, _) = g.min_space().unwrap();
        assert!((gap - 0.15).abs() < 1e-9, "0.3 apart minus half widths 0.1 and 0.05: {gap}");
        assert!(a.contains("net") || a.contains("(A)") || b.contains("(A)"));
        let p = builtin_profile("jlcpcb").unwrap();
        let r = validate(&g, &p, &Options { assembly: false, max_items: 5 }, Err("kicad-cli not installed"));
        let checks: Vec<&str> = r["findings"].as_array().unwrap().iter().map(|f| f["check"].as_str().unwrap()).collect();
        assert!(checks.contains(&"min_track"), "{checks:?}");
        assert!(!checks.contains(&"min_space"), "0.15 >= 0.127");
        assert!(checks.contains(&"min_drill"), "0.2 < 0.3");
        assert!(!checks.contains(&"annular_ring"), "ring 0.125 >= 0.075");
        assert!(checks.contains(&"drc"));
        assert_eq!(r["pass"], false);
        let mut strict = p.clone();
        strict.min_space = 0.2;
        strict.min_annular = 0.13;
        let r = validate(&g, &strict, &Options { assembly: false, max_items: 5 }, Err("x"));
        let checks: Vec<&str> = r["findings"].as_array().unwrap().iter().map(|f| f["check"].as_str().unwrap()).collect();
        assert!(checks.contains(&"min_space") && checks.contains(&"annular_ring"), "{checks:?}");
    }

    #[test]
    fn edge_silk_via_in_pad_acid_trap_models_fiducials() {
        let body = format!(
            "{OUTLINE}
            (footprint \"R:R_0603\" (layer \"F.Cu\") (at 10 15 90)
              (property \"Reference\" \"R1\") (attr smd)
              (fp_line (start -1 0) (end 1 0) (stroke (width 0.12) (type solid)) (layer \"F.SilkS\"))
              (pad \"1\" smd rect (at -0.8 0 90) (size 0.8 0.9) (layers \"F.Cu\" \"F.Mask\") (net \"A\"))
              (pad \"2\" smd rect (at 0.8 0 90) (size 0.8 0.9) (layers \"F.Cu\" \"F.Mask\") (net \"B\")))
            (via (at 10 15.8) (size 0.4) (drill 0.2) (layers \"F.Cu\" \"B.Cu\") (net \"A\"))
            (segment (start 0.1 5) (end 10 5) (width 0.2) (layer \"F.Cu\") (net \"E\"))
            (segment (start 20 20) (end 30 20) (width 0.2) (layer \"F.Cu\") (net \"T\"))
            (segment (start 20 20) (end 25 22) (width 0.2) (layer \"F.Cu\") (net \"T\"))"
        );
        let g = Geometry::from_text(&board(&body)).unwrap();
        // rotated 90: pad 1 local (-0.8, 0) lands at (10, 15.8)
        assert!(g.pads.iter().any(|p| dist(p.a, (10.0, 15.8)) < 0.1 || dist(p.b, (10.0, 15.8)) < 0.1 || dist(((p.a.0 + p.b.0) / 2.0, (p.a.1 + p.b.1) / 2.0), (10.0, 15.8)) < 1e-6));
        assert_eq!(g.vias_in_pads().len(), 1);
        assert_eq!(g.silk_on_pads().len(), 2, "the silk line crosses both pads");
        let traps = g.acid_traps();
        assert_eq!(traps.len(), 1);
        assert!((traps[0].0 - 21.8).abs() < 0.2, "{traps:?}");
        let near = g.edge_gaps(0.3);
        assert!(near.iter().any(|(gap, who, _)| who.contains("(E)") && *gap < 0.1));
        let r = validate(&g, &builtin_profile("generic").unwrap(), &Options { assembly: true, max_items: 3 }, Err("x"));
        let checks: Vec<&str> = r["findings"].as_array().unwrap().iter().map(|f| f["check"].as_str().unwrap()).collect();
        for c in ["edge_clearance", "silk_over_pads", "via_in_pad", "acid_traps", "3d_models", "fiducials"] {
            assert!(checks.contains(&c), "{c} missing from {checks:?}");
        }
    }

    #[test]
    fn drc_report_is_folded_in() {
        let path = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/fixtures/rp2040-drc.json");
        let rep: Value = serde_json::from_str(&std::fs::read_to_string(path).unwrap()).unwrap();
        let g = Geometry::from_text(&board(OUTLINE)).unwrap();
        let r = validate(&g, &builtin_profile("generic").unwrap(), &Options { assembly: false, max_items: 3 }, Ok(&rep));
        let summary = crate::cli::summarize_report(&rep);
        let has_drc = r["findings"].as_array().unwrap().iter().any(|f| f["check"] == "drc");
        assert_eq!(has_drc, summary["errors"].as_u64().unwrap() > 0);
        assert!(!r["findings"].as_array().unwrap().iter().any(|f| f["check"] == "drc" && f["severity"] == "warning"));
    }

    #[test]
    fn dru_minimums_override_the_profile() {
        let dru = "(version 1)\n# comment\n(rule \"track\" (constraint track_width (min 5mil)))\n(rule \"inner\" (layer inner) (constraint track_width (min 0.09mm)))\n(rule \"gap\" (constraint clearance (min 0.1mm)))\n(rule \"edge\" (constraint edge_clearance (min 0.2mm)))\n(rule \"hole\" (constraint hole_size (min 0.25mm)))";
        let m = dru_minimums(dru);
        assert!((m["track_width"] - 0.09).abs() < 1e-9);
        let mut p = builtin_profile("generic").unwrap();
        assert_eq!(apply_dru(&mut p, dru, "x.kicad_dru"), 4);
        assert!((p.min_space - 0.1).abs() < 1e-9 && (p.min_edge - 0.2).abs() < 1e-9 && (p.min_drill - 0.25).abs() < 1e-9);
        assert!((dru_length("0.005in").unwrap() - 0.127).abs() < 1e-9);
    }
}