AI Flow: Reverse Engineering

//! The KiCad copy. Footprints come from KiCad's own library (service-kicad, cached under lib/), lugs
//! measured on the photo get a generated footprint, pads carry their nets, zones take the fitted
//! outlines and their settings, and every zone is filled here by a raster fill (zone minus other-net
//! copper grown by the clearance, islands without same-net copper removed, holes bridged into one
//! outline as KiCad stores fills), so the board shows its pours the moment it opens.
use crate::raster::{self, Mask};
use crate::sexp::{self, a, f, l, q, N};
use serde_json::Value;
use std::collections::HashMap;
use std::path::{Path, PathBuf};

pub fn uuid(seed: &str) -> String {
    let mut h1: u64 = 0xcbf29ce484222325; let mut h2: u64 = 0x84222325cbf29ce4;
    for b in seed.bytes() { h1 = (h1 ^ b as u64).wrapping_mul(0x100000001b3); h2 = (h2 ^ b as u64).wrapping_mul(0x1000193).rotate_left(7); }
    let s = format!("{h1:016x}{h2:016x}");
    format!("{}-{}-4{}-a{}-{}", &s[0..8], &s[8..12], &s[13..16], &s[17..20], &s[20..32])
}

fn fv(v: &Value, k: &str) -> f64 { v[k].as_f64().unwrap_or(0.0) }
fn pt(v: &Value) -> (f64, f64) { (v[0].as_f64().unwrap_or(0.0), v[1].as_f64().unwrap_or(0.0)) }

/// A lug footprint from measured sizes: one square plated pad with its hole.
pub fn lug_footprint(pad: f64, drill: f64) -> String {
    format!("(footprint \"Lug_{pad:.1}mm_Drill{drill:.2}mm\" (layer \"F.Cu\") (attr through_hole)\n (property \"Reference\" \"REF**\" (at 0 {:.2}) (layer \"F.SilkS\") (effects (font (size 1 1) (thickness 0.15))))\n (property \"Value\" \"Lug\" (at 0 {:.2}) (layer \"F.Fab\") (effects (font (size 1 1) (thickness 0.15))))\n (fp_rect (start {:.3} {:.3}) (end {:.3} {:.3}) (stroke (width 0.05) (type solid)) (fill no) (layer \"F.CrtYd\"))\n (pad \"1\" thru_hole roundrect (at 0 0) (size {pad:.3} {pad:.3}) (drill {drill:.3}) (layers \"*.Cu\" \"*.Mask\") (roundrect_rratio 0.15)))\n",
        -pad / 2.0 - 1.2, pad / 2.0 + 1.2, -pad / 2.0 - 0.25, -pad / 2.0 - 0.25, pad / 2.0 + 0.25, pad / 2.0 + 0.25)
}

/// Fetch a library footprint (cached). `id` is "Library:Name".
pub fn footprint_text(cache: &Path, id: &str, part: &Value) -> Result<String, String> {
    if id == "generated:lug" { return Ok(lug_footprint(fv(&part["lug"], "pad_mm").max(1.0), fv(&part["lug"], "drill_mm").max(0.3))); }
    if id == "generated:hole" {
        let (pad, drill) = (fv(&part["hole"], "pad_mm"), fv(&part["hole"], "drill_mm").max(0.3));
        if pad <= drill { return Ok(format!("(footprint \"Hole_NPTH_{drill:.2}mm\" (layer \"F.Cu\") (attr exclude_from_pos_files exclude_from_bom)\n (property \"Reference\" \"REF**\" (at 0 {:.2}) (layer \"F.SilkS\") (effects (font (size 1 1) (thickness 0.15))))\n (property \"Value\" \"Hole\" (at 0 {:.2}) (layer \"F.Fab\") (effects (font (size 1 1) (thickness 0.15))))\n (pad \"\" np_thru_hole circle (at 0 0) (size {drill:.3} {drill:.3}) (drill {drill:.3}) (layers \"*.Cu\" \"*.Mask\")))\n", -drill - 1.0, drill + 1.0)); }
        return Ok(format!("(footprint \"Hole_Plated_{pad:.2}mm_Drill{drill:.2}mm\" (layer \"F.Cu\") (attr through_hole)\n (property \"Reference\" \"REF**\" (at 0 {:.2}) (layer \"F.SilkS\") (effects (font (size 1 1) (thickness 0.15))))\n (property \"Value\" \"Hole\" (at 0 {:.2}) (layer \"F.Fab\") (effects (font (size 1 1) (thickness 0.15))))\n (pad \"1\" thru_hole circle (at 0 0) (size {pad:.3} {pad:.3}) (drill {drill:.3}) (layers \"*.Cu\" \"*.Mask\")))\n", -pad - 1.0, pad + 1.0));
    }
    let (lib, name) = id.split_once(':').ok_or(format!("footprint {id:?} is not Library:Name"))?;
    let p = cache.join(lib).join(format!("{name}.kicad_mod"));
    if !p.is_file() {
        std::fs::create_dir_all(p.parent().unwrap()).ok();
        let o = std::process::Command::new("service-kicad").args(["fp", "fetch", lib, name, "--out"]).arg(&p).output().map_err(|e| format!("service-kicad not runnable: {e}"))?;
        if !p.is_file() || std::fs::metadata(&p).map(|m| m.len() < 50).unwrap_or(true) {
            let _ = std::fs::remove_file(&p);
            return Err(format!("footprint {id} not in KiCad's library ({})", String::from_utf8_lossy(&o.stderr).trim().chars().take(160).collect::<String>()));
        }
    }
    std::fs::read_to_string(&p).map_err(|e| e.to_string())
}

#[derive(Clone, Debug)]
pub struct Pad { pub part: String, pub num: String, pub x: f64, pub y: f64, pub w: f64, pub h: f64, pub rot: f64, pub round: bool, pub drill: f64, pub layers: Vec<String>, pub net: String }

impl Pad {
    pub fn on(&self, layer: &str) -> bool { self.layers.iter().any(|l| l == layer || l == "*.Cu" || (l == "F&B.Cu" && (layer == "F.Cu" || layer == "B.Cu"))) || (self.drill > 0.0 && self.layers.iter().any(|l| l == "*.Cu")) }
}

/// KiCad places a footprint child at fp + R(rot) * local, rotation counter-clockwise on screen.
pub fn place(x: f64, y: f64, rot: f64, lx: f64, ly: f64) -> (f64, f64) {
    let (c, s) = (rot.to_radians().cos(), rot.to_radians().sin());
    (x + lx * c + ly * s, y - lx * s + ly * c)
}

/// Turn a library footprint over onto the bottom face, as KiCad's flip does: mirrored in local y with its angles negated, and every front layer swapped for the back one.
pub fn flip_footprint(n: &mut N) {
    fn swap(s: &str) -> Option<String> { let q = s.trim_matches('"'); if let Some(r) = q.strip_prefix("F.") { Some(format!("\"B.{r}\"")) } else { q.strip_prefix("B.").map(|r| format!("\"F.{r}\"")) } }
    fn walk(n: &mut N) {
        let head = n.head().to_string();
        if let N::L(v) = n {
            if matches!(head.as_str(), "layer" | "layers") { for c in v.iter_mut().skip(1) { if let N::A(s) = c { if let Some(t) = swap(s) { *s = t; } } } return; }
            if matches!(head.as_str(), "at" | "start" | "end" | "mid" | "center" | "xy") && v.len() >= 3 {
                if let N::A(s) = &mut v[2] { if let Ok(y) = s.parse::<f64>() { *s = format!("{}", -y); } }
                if head == "at" && v.len() >= 4 { if let N::A(s) = &mut v[3] { if let Ok(a) = s.parse::<f64>() { *s = format!("{}", -a); } } }
                return;
            }
            for c in v.iter_mut() { walk(c); }
        }
    }
    walk(n);
}

/// One placed footprint node and its pads in board coordinates.
pub fn placed(text: &str, id: &str, part: &Value, nets: &HashMap<String, String>, net_idx: &HashMap<String, usize>) -> Result<(N, Vec<Pad>), String> {
    let mut n = sexp::parse(text)?;
    let r = part["ref"].as_str().unwrap_or("?").to_string();
    let (x, y) = pt(&part["pos_mm"]); let rot = fv(part, "rot");
    let side = part["side"].as_str().unwrap_or("top");
    if side == "bottom" { flip_footprint(&mut n); }
    let items = n.items_mut();
    items[1] = q(id);
    items.retain(|c| !matches!(c.head(), "version" | "generator" | "generator_version" | "embedded_fonts" | "uuid" | "at" | "tedit"));
    let li = items.iter().position(|c| c.head() == "layer").map(|i| i + 1).unwrap_or(2);
    items.insert(li, l(vec![a("at"), f(x), f(y), f(rot)]));
    items.insert(li + 1, l(vec![a("uuid"), q(&uuid(&format!("fp/{r}")))]));
    let mut pads = vec![];
    for c in items.iter_mut() {
        match c.head() {
            "property" => {
                let key = c.arg(0).unwrap_or_default();
                if key == "Reference" { c.items_mut()[2] = q(&r); }
                if key == "Value" { c.items_mut()[2] = q(part["value"].as_str().unwrap_or("")); }
                if let Some(at) = c.child_mut("at") { let ang = at.num(2).unwrap_or(0.0) + rot; let v = at.items_mut(); v.truncate(3); v.push(f(ang)); }
            }
            "fp_text" => { if let Some(at) = c.child_mut("at") { let ang = at.num(2).unwrap_or(0.0) + rot; let v = at.items_mut(); v.truncate(3); v.push(f(ang)); } }
            "pad" => {
                let num = c.arg(0).unwrap_or_default();
                let shape = c.arg(2).unwrap_or_default();
                let at = c.child("at").cloned().unwrap_or(l(vec![a("at"), a("0"), a("0")]));
                let (lx, ly, lr) = (at.num(0).unwrap_or(0.0), at.num(1).unwrap_or(0.0), at.num(2).unwrap_or(0.0));
                if let Some(atn) = c.child_mut("at") { let v = atn.items_mut(); v.truncate(3); v.push(f(lr + rot)); }
                let size = c.child("size"); let (w, h) = (size.and_then(|s| s.num(0)).unwrap_or(0.0), size.and_then(|s| s.num(1)).unwrap_or(0.0));
                let drill = c.child("drill").and_then(|d| d.num(0).or_else(|| d.num(1))).unwrap_or(0.0);
                let layers: Vec<String> = c.child("layers").map(|ls| ls.items()[1..].iter().map(|x| sexp::unq(&match x { N::A(s) => s.clone(), _ => String::new() })).collect()).unwrap_or_default();
                let net = nets.get(&format!("{r}.{num}")).cloned().unwrap_or_default();
                c.items_mut().retain(|k| k.head() != "net" && k.head() != "uuid");
                if !net.is_empty() { c.items_mut().push(l(vec![a("net"), a(net_idx[&net]), q(&net)])); }
                c.items_mut().push(l(vec![a("uuid"), q(&uuid(&format!("pad/{r}/{num}/{lx}/{ly}")))]));
                let (px, py) = place(x, y, rot, lx, ly);
                if !num.is_empty() || shape != "" { pads.push(Pad { part: r.clone(), num, x: px, y: py, w, h, rot: lr + rot, round: shape == "circle" || (shape == "oval" && (w - h).abs() < 1e-6), drill, layers, net }); }
            }
            _ => {}
        }
    }
    Ok((n, pads))
}

/// Only the placed pads of the parts whose footprints are already cached or generated. Never fetches:
/// a score must not depend on the KiCad service being up.
pub fn pads_of(cache: &Path, parts: &[Value]) -> Vec<Pad> {
    let (none, idx): (HashMap<String, String>, HashMap<String, usize>) = (HashMap::new(), HashMap::new());
    let mut out = vec![];
    for p in parts {
        let id = p["footprint"].as_str().unwrap_or("");
        let local = id.starts_with("generated:") || id.split_once(':').map(|(lib, name)| cache.join(lib).join(format!("{name}.kicad_mod")).is_file()).unwrap_or(false);
        if !local { continue; }
        if let Ok((_, ps)) = footprint_text(cache, id, p).and_then(|t| placed(&t, id, p, &none, &idx)) { out.extend(ps); }
    }
    out
}

/// A placed part's package as its footprint draws it on the fabrication layer: the box round those lines in the footprint's own
/// frame (turned over for a part on the bottom), with the part's place and rotation. `pads`: how many pad numbers the footprint has.
#[derive(Clone, Debug)]
pub struct Body { pub part: String, pub layer: &'static str, pub x: f64, pub y: f64, pub rot: f64, pub bx: (f64, f64, f64, f64), pub pads: usize }

impl Body {
    /// Whether a board point lies in the body drawn in by `inset` mm on every side: the inverse of `place`.
    pub fn holds(&self, x: f64, y: f64, inset: f64) -> bool {
        let (dx, dy) = (x - self.x, y - self.y); let (c, s) = (self.rot.to_radians().cos(), self.rot.to_radians().sin());
        let (lx, ly) = (dx * c - dy * s, dx * s + dy * c);
        lx >= self.bx.0 + inset && lx <= self.bx.2 - inset && ly >= self.bx.1 + inset && ly <= self.bx.3 - inset
    }
    pub fn corners(&self) -> [(f64, f64); 4] { let b = self.bx; [(b.0, b.1), (b.2, b.1), (b.2, b.3), (b.0, b.3)].map(|q| place(self.x, self.y, self.rot, q.0, q.1)) }
}

/// The box of what a placed footprint draws on its fabrication layer, in its own frame. None when it draws nothing there.
fn fab_box(n: &N) -> Option<(f64, f64, f64, f64)> {
    let mut pts: Vec<(f64, f64)> = vec![];
    let at = |c: &N, k: &str| c.child(k).and_then(|a| Some((a.num(0)?, a.num(1)?)));
    for c in n.items() {
        if !matches!(c.head(), "fp_rect" | "fp_line" | "fp_poly" | "fp_circle" | "fp_arc") || !c.child("layer").and_then(|l| l.arg(0)).map(|l| l.ends_with(".Fab")).unwrap_or(false) { continue; }
        if c.head() == "fp_circle" { if let (Some(m), Some(e)) = (at(c, "center"), at(c, "end")) { let r = crate::geom::dist(m, e); pts.push((m.0 - r, m.1 - r)); pts.push((m.0 + r, m.1 + r)); } continue; }
        for k in ["start", "mid", "end"] { if let Some(q) = at(c, k) { pts.push(q); } }
        if let Some(ps) = c.child("pts") { for q in ps.children("xy") { if let (Some(x), Some(y)) = (q.num(0), q.num(1)) { pts.push((x, y)); } } }
    }
    if pts.is_empty() { return None; }
    Some(pts.iter().fold((f64::MAX, f64::MAX, f64::MIN, f64::MIN), |b, q| (b.0.min(q.0), b.1.min(q.1), b.2.max(q.0), b.3.max(q.1))))
}

/// The bodies of the placed parts whose footprints are cached or generated, as `pads_of` reads their pads. Never fetches.
pub fn bodies_of(cache: &Path, parts: &[Value]) -> Vec<Body> {
    let (none, idx): (HashMap<String, String>, HashMap<String, usize>) = (HashMap::new(), HashMap::new());
    let mut out = vec![];
    for p in parts {
        let id = p["footprint"].as_str().unwrap_or("");
        let local = id.starts_with("generated:") || id.split_once(':').map(|(lib, name)| cache.join(lib).join(format!("{name}.kicad_mod")).is_file()).unwrap_or(false);
        if !local { continue; }
        let Ok((n, ps)) = footprint_text(cache, id, p).and_then(|t| placed(&t, id, p, &none, &idx)) else { continue };
        let Some(bx) = fab_box(&n) else { continue };
        let nums: std::collections::BTreeSet<&str> = ps.iter().map(|q| q.num.as_str()).filter(|s| !s.is_empty()).collect();
        let (x, y) = pt(&p["pos_mm"]);
        out.push(Body { part: p["ref"].as_str().unwrap_or("?").to_string(), layer: if p["side"].as_str() == Some("bottom") { "B.Cu" } else { "F.Cu" }, x, y, rot: fv(p, "rot"), bx, pads: nums.len() });
    }
    out
}

/// Raster of board copper at `res` px/mm over the board box.
pub struct Grid { pub x0: f64, pub y0: f64, pub res: f64, pub w: usize, pub h: usize }
impl Grid {
    pub fn px(&self, x: f64, y: f64) -> (f64, f64) { ((x - self.x0) * self.res, (y - self.y0) * self.res) }
    pub fn mm(&self, u: f64, v: f64) -> (f64, f64) { (self.x0 + u / self.res, self.y0 + v / self.res) }
    pub fn empty(&self) -> Mask { Mask::new(self.w, self.h) }
    pub fn poly(&self, m: &mut Mask, poly: &[(f64, f64)]) {
        let p: Vec<(f64, f64)> = poly.iter().map(|q| self.px(q.0, q.1)).collect();
        for v in 0..self.h { let yc = v as f64 + 0.5; let mut xs = vec![];
            for i in 0..p.len() { let (a, b) = (p[i], p[(i + 1) % p.len()]); if (a.1 <= yc && b.1 > yc) || (b.1 <= yc && a.1 > yc) { xs.push(a.0 + (yc - a.1) / (b.1 - a.1) * (b.0 - a.0)); } }
            xs.sort_by(|a, b| a.partial_cmp(b).unwrap());
            for c in xs.chunks(2) { if c.len() == 2 { for u in (c[0].max(0.0).round() as usize)..(c[1].min(self.w as f64).round() as usize) { m.set(u, v, true); } } } }
    }
    pub fn pad(&self, m: &mut Mask, p: &Pad, grow: f64) {
        let (cx, cy) = self.px(p.x, p.y);
        let (hw, hh) = ((p.w / 2.0 + grow) * self.res, (p.h / 2.0 + grow) * self.res);
        let (c, s) = (p.rot.to_radians().cos(), p.rot.to_radians().sin());
        let r = hw.max(hh).ceil() as i64 + 1;
        for dv in -r..=r { for du in -r..=r {
            let (u, v) = (cx as i64 + du, cy as i64 + dv); if u < 0 || v < 0 || u >= self.w as i64 || v >= self.h as i64 { continue; }
            let (dx, dy) = (du as f64 + 0.5 - (cx - cx.floor()), dv as f64 + 0.5 - (cy - cy.floor()));
            let (lx, ly) = (dx * c - dy * s, dx * s + dy * c);
            let inside = if p.round { (lx / hw).powi(2) + (ly / hh).powi(2) <= 1.0 } else { lx.abs() <= hw && ly.abs() <= hh };
            if inside { m.set(u as usize, v as usize, true); }
        } }
    }
    pub fn disk(&self, m: &mut Mask, x: f64, y: f64, rad: f64) {
        let (cx, cy) = self.px(x, y); let r = rad * self.res; let ri = r.ceil() as i64;
        for dv in -ri..=ri { for du in -ri..=ri { if (du * du + dv * dv) as f64 > r * r { continue; }
            let (u, v) = (cx as i64 + du, cy as i64 + dv); if u >= 0 && v >= 0 && u < self.w as i64 && v < self.h as i64 { m.set(u as usize, v as usize, true); } } }
    }
    pub fn seg(&self, m: &mut Mask, a: (f64, f64), b: (f64, f64), wd: f64) {
        let n = ((crate::geom::dist(a, b) * self.res) as usize).max(1);
        for i in 0..=n { let t = i as f64 / n as f64; self.disk(m, a.0 + (b.0 - a.0) * t, a.1 + (b.1 - a.1) * t, wd / 2.0); }
    }
}

/// Join holes into the outer ring with slits that never cross: each hole, left to right, joins from its leftmost
/// vertex straight left to the first edge of what has been built so far. Done in any other order, or to the nearest
/// vertex, slits cross on a pour with hundreds of holes and KiCad drops the polygon.
pub fn keyhole(outer: Vec<(f64, f64)>, mut holes: Vec<Vec<(f64, f64)>>) -> Vec<(f64, f64)> {
    // a hole winds against its outline: KiCad's triangulation reads a hole wound the same way as copper
    let area = |r: &[(f64, f64)]| (0..r.len()).map(|i| { let (a, b) = (r[i], r[(i + 1) % r.len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>();
    let outer_sign = area(&outer).signum();
    for h in holes.iter_mut() { if area(h).signum() == outer_sign { h.reverse(); } }
    let left = |h: &Vec<(f64, f64)>| (0..h.len()).min_by(|a, b| h[*a].0.partial_cmp(&h[*b].0).unwrap().then(h[*a].1.partial_cmp(&h[*b].1).unwrap())).unwrap();
    holes.sort_by(|a, b| a[left(a)].0.partial_cmp(&b[left(b)].0).unwrap());
    let mut ring = outer;
    for h in holes {
        let k = left(&h); let p = h[k];
        // the first edge straight left of p
        let mut best: Option<(f64, usize)> = None;
        for i in 0..ring.len() {
            let (a, b) = (ring[i], ring[(i + 1) % ring.len()]);
            if (a.1 <= p.1) == (b.1 <= p.1) { continue; }
            let x = a.0 + (p.1 - a.1) / (b.1 - a.1) * (b.0 - a.0);
            if x <= p.0 && best.map(|q| x > q.0).unwrap_or(true) { best = Some((x, i)); }
        }
        let Some((x, i)) = best else { continue };
        let at = (x, p.1);
        let mut ins = vec![at];
        for j in 0..=h.len() { ins.push(h[(k + j) % h.len()]); }
        ins.push(at);
        ring.splice(i + 1..i + 1, ins);
    }
    ring
}

/// The filled region of a zone as KiCad polygon rings in mm (each a fractured ring: holes bridged in).
pub fn vectorize(g: &Grid, fill: &Mask) -> Vec<Vec<(f64, f64)>> {
    let (lab, cs) = raster::components(fill);
    let mut rings = vec![];
    for c in &cs {
        if c.area < 6 { continue; }
        let outer: Vec<(f64, f64)> = crate::geom::simplify(&raster::trace_boundary(&lab, fill.w, fill.h, c), 0.8);
        if outer.len() < 3 { continue; }
        // holes: background components enclosed by this component
        let (x0, y0, x1, y1) = (c.x0, c.y0, c.x1, c.y1);
        let mut sub = Mask::new(x1 - x0 + 3, y1 - y0 + 3);
        for y in y0..=y1 { for x in x0..=x1 { if lab[y * fill.w + x] == c.label { sub.set(x - x0 + 1, y - y0 + 1, true); } } }
        let holes = sub.fill_holes().andnot(&sub);
        let (hl, hc) = raster::components(&holes);
        let mut holes_px: Vec<Vec<(f64, f64)>> = vec![];
        for hcomp in hc.iter().filter(|h| h.area >= 4) {
            let hr: Vec<(f64, f64)> = crate::geom::simplify(&raster::trace_boundary(&hl, sub.w, sub.h, hcomp), 0.8).iter().map(|p| (p.0 + x0 as f64 - 1.0, p.1 + y0 as f64 - 1.0)).collect();
            if hr.len() >= 3 { holes_px.push(hr); }
        }
        let ring = keyhole(outer, holes_px);
        rings.push(ring.iter().map(|p| { let m = g.mm(p.0, p.1); ((m.0 * 1000.0).round() / 1000.0, (m.1 * 1000.0).round() / 1000.0) }).collect());
    }
    rings
}

/// A segment's width: measured along a track read from the photo, otherwise the track's one width.
pub fn seg_width(t: &Value, j: usize) -> f64 {
    if let Some(w) = t["widths_mm"].as_array() { if j + 1 < w.len() { return ((w[j].as_f64().unwrap_or(0.0) + w[j + 1].as_f64().unwrap_or(0.0)) / 2.0).max(0.025); } }
    fv(t, "width_mm").max(0.1)
}

/// A pour read from the photo as a mask on the photo's own pixels (image pixel centres at integer pixels, 40 px/mm): (mask, x of its pixel 0, y of its pixel 0).
fn photo_mask(z: &Value) -> Option<(Mask, i64, i64)> {
    let rows = z["rle_px"].as_array()?;
    let (mut x0, mut y0, mut x1, mut y1) = (i64::MAX, i64::MAX, i64::MIN, i64::MIN);
    for r in rows { let Some(a) = r.as_array() else { continue }; let y = a[0].as_i64().unwrap_or(0); y0 = y0.min(y); y1 = y1.max(y); for c in a[1..].chunks(2) { if c.len() == 2 { x0 = x0.min(c[0].as_i64().unwrap_or(0)); x1 = x1.max(c[1].as_i64().unwrap_or(0)); } } }
    if x0 > x1 { return None; }
    let (ox, oy) = (x0 - 1, y0 - 1);
    let mut m = Mask::new((x1 - x0 + 3) as usize, (y1 - y0 + 3) as usize);
    for r in rows { let Some(a) = r.as_array() else { continue }; let y = a[0].as_i64().unwrap_or(0); for c in a[1..].chunks(2) { if c.len() != 2 { continue; } for x in c[0].as_i64().unwrap_or(0)..c[1].as_i64().unwrap_or(0) { m.set((x - ox) as usize, (y - oy) as usize, true); } } }
    Some((m, ox, oy))
}

/// The closed loops along the pixel edges of one 4-connected piece: pixel (x, y) occupies [x, x + 1] by [y, y + 1], which is how `gerber::rasterize` draws it back, so a loop fills exactly the
/// piece's pixels. Tracing through pixel centres, as `raster::trace_boundary` does, leaves half a pixel off every outer edge and adds it round every hole: the drawn copper then sat 1 to 1.5 px inside
/// the steepest fall of brightness on the photo. Each loop keeps the copper on its right (y down), so an outline has positive area and a hole negative.
fn crack_loops(inside: &dyn Fn(i64, i64) -> bool, x0: i64, y0: i64, x1: i64, y1: i64) -> Vec<Vec<(f64, f64)>> {
    const DIRS: [(i64, i64); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    let mut out: HashMap<(i64, i64), Vec<(usize, bool)>> = HashMap::new();
    for y in y0..=y1 { for x in x0..=x1 { if !inside(x, y) { continue; }
        if !inside(x, y - 1) { out.entry((x, y)).or_default().push((0, false)); }
        if !inside(x + 1, y) { out.entry((x + 1, y)).or_default().push((1, false)); }
        if !inside(x, y + 1) { out.entry((x + 1, y + 1)).or_default().push((2, false)); }
        if !inside(x - 1, y) { out.entry((x, y + 1)).or_default().push((3, false)); } } }
    let mut starts: Vec<(i64, i64)> = out.keys().copied().collect(); starts.sort();
    let mut loops = vec![];
    for s in starts { loop {
        let Some(first) = out.get_mut(&s).and_then(|v| v.iter_mut().find(|e| !e.1).map(|e| { e.1 = true; e.0 })) else { break };
        let mut ring = vec![(s.0 as f64, s.1 as f64)]; let (mut p, mut d) = (s, first);
        loop {
            p = (p.0 + DIRS[d].0, p.1 + DIRS[d].1);
            if p == s { break; }
            // at a corner shared by two diagonal pixels the right turn stays on this pixel: right, straight, left
            let Some(v) = out.get_mut(&p) else { break };
            let next = [(d + 1) % 4, d, (d + 3) % 4].iter().copied().find(|t| v.iter().any(|e| e.0 == *t && !e.1));
            let Some(n) = next else { break };
            for e in v.iter_mut() { if e.0 == n { e.1 = true; } }
            if n != d { ring.push((p.0 as f64, p.1 as f64)); }
            d = n;
        }
        if ring.len() >= 3 { loops.push(ring); }
    } }
    loops
}

/// The outline of one connected piece of a mask, and its holes, in mm. Within 0.75 px (0.019 mm) of the pixel edges: a tighter fit keeps each pixel's stair and adds nothing the photo can tell.
fn piece_contours(lab: &[u32], w: usize, h: usize, c: &raster::Component, ox: i64, oy: i64) -> Option<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)> {
    const TOL: f64 = 0.75;
    let inside = |x: i64, y: i64| x >= 0 && y >= 0 && x < w as i64 && y < h as i64 && lab[y as usize * w + x as usize] == c.label;
    let area = |r: &[(f64, f64)]| (0..r.len()).map(|i| { let (a, b) = (r[i], r[(i + 1) % r.len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>() / 2.0;
    let to_mm = |p: &(f64, f64)| { let q = crate::board::to_mm(p.0 + ox as f64, p.1 + oy as f64); ((q.0 * 1000.0).round() / 1000.0, (q.1 * 1000.0).round() / 1000.0) };
    let (mut outer, mut holes): (Option<Vec<(f64, f64)>>, Vec<Vec<(f64, f64)>>) = (None, vec![]);
    for ring in crack_loops(&inside, c.x0 as i64, c.y0 as i64, c.x1 as i64, c.y1 as i64) {
        let a = area(&ring);
        if a > 0.0 { if outer.as_ref().map(|o| area(o) < a).unwrap_or(true) { outer = Some(ring); } }
        else if a <= -2.0 { let r = crate::geom::simplify(&ring, TOL); if r.len() >= 3 { holes.push(r.iter().map(to_mm).collect()); } }
    }
    let outer = crate::geom::simplify(&outer?, TOL);
    if outer.len() < 3 { return None; }
    Some((outer.iter().map(to_mm).collect(), holes))
}

/// Each connected piece of a pour as read: its outline and holes as read, and its fill, which is the same copper less what another net's pad, via or routed
/// track occupies on the coarse grid. A fill ring has its holes joined in by slits, as KiCad stores fills. An outline keeps them apart.
fn photo_pieces(g: &Grid, z: &Value, other: &Mask) -> Vec<PhotoPiece> {
    let Some((m, ox, oy)) = photo_mask(z) else { return vec![] };
    let (sw, sh) = (m.w, m.h);
    let (lab, cs) = raster::components(&m);
    let mut out = vec![];
    for c in cs.iter().filter(|c| c.area >= 2) {
        let Some((outer, holes)) = piece_contours(&lab, sw, sh, c, ox, oy) else { continue };
        let mut cut = Mask::new(sw, sh);
        for y in c.y0..=c.y1 { for x in c.x0..=c.x1 { if lab[y * sw + x] != c.label { continue; }
            let (mx, my) = crate::board::to_mm(x as f64 + ox as f64, y as f64 + oy as f64); let (gu, gv) = g.px(mx, my);
            if gu >= 0.0 && gv >= 0.0 && (gu as usize) < g.w && (gv as usize) < g.h && other.d[gv as usize * g.w + gu as usize] { continue; }
            cut.set(x, y, true); } }
        let (fl, fc) = raster::components(&cut);
        let mut rings = vec![];
        for f_ in fc.iter().filter(|f_| f_.area >= 2) { if let Some((o, hs)) = piece_contours(&fl, sw, sh, f_, ox, oy) { rings.push(keyhole(o, hs)); } }
        out.push(PhotoPiece { outer, holes, rings });
    }
    out
}
struct PhotoPiece { outer: Vec<(f64, f64)>, holes: Vec<Vec<(f64, f64)>>, rings: Vec<Vec<(f64, f64)>> }

/// A mask as the runs of pixels it sets: small pours subtract in the time their size takes, not the board's.
struct Sparse(Vec<usize>);
impl Sparse {
    fn of(m: &Mask) -> Sparse { Sparse((0..m.d.len()).filter(|i| m.d[*i]).collect()) }
    fn subtract_from(&self, m: &mut Mask) { for i in &self.0 { m.d[*i] = false; } }
}

/// A via of another net in a read pour: the photo shows no gap (a gap would have split the pour), so its net or its place is in doubt. This keeps the two copper apart without redrawing the pour. 2 photo pixels: 0.1 mm rings round the 130 such vias per face took 47 mm2 of seen copper off the plot. Most of these vias are named wrongly, not placed wrongly, and clear when attribution joins them.
const VIA_GAP: f64 = 0.05;
/// Copper of another net stays this far from a pad: as far as the photo cannot show (fidelity::BESIDE_PX, 6 px).
const PAD_GAP: f64 = 0.15;
/// A read pour keeps necks this narrow on a refill; KiCad deflates and inflates a zone by half of this. 2 photo pixels.
const PHOTO_MIN_THICKNESS: f64 = 0.05;

/// For each read pour, the narrowest gap between it and copper of another net, in mm, rounded down to 0.01 mm and at least 0.01: seen pours, seen tracks, pads and vias on its layer, at photo resolution, up to 0.25 mm.
fn photo_gaps(copper: &Value, pads: &[Pad], shaped: &HashMap<usize, Vec<(f64, f64)>>, w: usize, h: usize) -> HashMap<String, f64> {
    let mut out: HashMap<String, f64> = HashMap::new();
    const REACH: i64 = 10;
    let offs: Vec<(i64, i64, f64)> = (-REACH..=REACH).flat_map(|dy| (-REACH..=REACH).map(move |dx| (dx, dy))).filter(|(dx, dy)| { let d = dx * dx + dy * dy; d > 0 && d <= REACH * REACH && (*dy > 0 || (*dy == 0 && *dx > 0)) }).map(|(dx, dy)| (dx, dy, ((dx * dx + dy * dy) as f64).sqrt())).collect();
    let fr = crate::gerber::Frame { w, h, res: crate::board::RES, ox: crate::board::ORIGIN, oy: crate::board::ORIGIN };
    for layer in ["F.Cu", "B.Cu"] {
        // owner of each pixel: a net index, and the zone it belongs to (0: not a pour)
        let mut nets: HashMap<String, u32> = HashMap::new();
        let mut idx = |n: &str| -> u32 { let k = nets.len() as u32 + 1; *nets.entry(n.to_string()).or_insert(k) };
        let (mut net_at, mut zone_at) = (vec![0u32; w * h], vec![0u32; w * h]);
        let zs: Vec<&Value> = copper["zones"].as_array().into_iter().flatten().filter(|z| z["layer"].as_str() == Some(layer) && z["rle_px"].is_array()).collect();
        for t in copper["traces"].as_array().into_iter().flatten().filter(|t| t["layer"].as_str() == Some(layer)) {
            let path: Vec<(f64, f64)> = t["path_mm"].as_array().map(|a| a.iter().map(pt).collect()).unwrap_or_default(); let n = idx(t["net"].as_str().unwrap_or(""));
            let mut m = Mask::new(0, 0); let _ = &mut m;
            for (j, s) in path.windows(2).enumerate() { let wd = seg_width(t, j); let d = crate::geom::dist(s[0], s[1]); let steps = ((d * crate::board::RES) as usize).max(1); for k in 0..=steps { let a_ = k as f64 / steps as f64; let (u, v) = crate::board::to_px(s[0].0 + (s[1].0 - s[0].0) * a_, s[0].1 + (s[1].1 - s[0].1) * a_); let r = (wd / 2.0 * crate::board::RES) as i64; for dv in -r..=r { for du in -r..=r { if du * du + dv * dv > r * r { continue; } let (x, y) = (u as i64 + du, v as i64 + dv); if x >= 0 && y >= 0 && x < w as i64 && y < h as i64 { net_at[y as usize * w + x as usize] = n; } } } } }
        }
        for (i, p) in pads.iter().enumerate().filter(|(_, p)| p.on(layer)) { let n = idx(&p.net); let mut m = Mask::new(w, h);
            if let Some(poly) = shaped.get(&i) { crate::gerber::fill_poly(&mut m, &fr, poly); } else if p.round { crate::gerber::fill_disk(&mut m, &fr, p.x, p.y, p.w.max(p.h) / 2.0); } else { let (c, s) = (p.rot.to_radians().cos(), p.rot.to_radians().sin()); let (hw, hh) = (p.w / 2.0, p.h / 2.0); let pts: Vec<(f64, f64)> = [(-hw, -hh), (hw, -hh), (hw, hh), (-hw, hh)].iter().map(|q| (p.x + q.0 * c + q.1 * s, p.y - q.0 * s + q.1 * c)).collect(); crate::gerber::fill_poly(&mut m, &fr, &pts); }
            for (k, on) in m.d.iter().enumerate() { if *on { net_at[k] = n; } } }
        for v in copper["vias"].as_array().into_iter().flatten().filter(|v| !v["net"].as_str().unwrap_or("").is_empty()) { let (x, y) = pt(&v["pos_mm"]); let n = idx(v["net"].as_str().unwrap_or("")); let (u, u2) = crate::board::to_px(x, y); let r = (v["diameter_mm"].as_f64().unwrap_or(0.5) / 2.0 * crate::board::RES) as i64; for dv in -r..=r { for du in -r..=r { if du * du + dv * dv > r * r { continue; } let (x, y) = (u as i64 + du, u2 as i64 + dv); if x >= 0 && y >= 0 && x < w as i64 && y < h as i64 { net_at[y as usize * w + x as usize] = n; } } } }
        for (zi, z) in zs.iter().enumerate() { let n = idx(z["net"].as_str().unwrap_or("")); for r in z["rle_px"].as_array().into_iter().flatten() { let Some(a_) = r.as_array() else { continue }; let y = a_[0].as_i64().unwrap_or(0); if y < 0 || y >= h as i64 { continue; } for c in a_[1..].chunks(2) { if c.len() != 2 { continue; } for x in c[0].as_i64().unwrap_or(0).max(0)..c[1].as_i64().unwrap_or(0).min(w as i64) { let k = y as usize * w + x as usize; if net_at[k] == 0 || zone_at[k] != 0 { net_at[k] = n; zone_at[k] = zi as u32 + 1; } } } } }
        let mut best = vec![f64::MAX; zs.len() + 1];
        for y in 0..h as i64 { for x in 0..w as i64 { let k = (y * w as i64 + x) as usize; let a_ = net_at[k]; if a_ == 0 { continue; }
            // a pixel with copper of its own on every side has no gap to measure
            if x > 0 && y > 0 && x + 1 < w as i64 && y + 1 < h as i64 && net_at[k - 1] != 0 && net_at[k + 1] != 0 && net_at[k - w] != 0 && net_at[k + w] != 0 { let same = net_at[k - 1] == a_ && net_at[k + 1] == a_ && net_at[k - w] == a_ && net_at[k + w] == a_; if same { continue; } }
            for (dx, dy, d) in &offs { let (px, py) = (x + dx, y + dy); if px < 0 || py < 0 || px >= w as i64 || py >= h as i64 { continue; } let j = (py * w as i64 + px) as usize; let b = net_at[j]; if b == 0 || b == a_ { continue; }
                for zz in [zone_at[k], zone_at[j]] { if zz != 0 && *d < best[zz as usize] { best[zz as usize] = *d; } } } } }
        for (zi, z) in zs.iter().enumerate() { let px = best[zi + 1]; let g = if px == f64::MAX { 0.25 } else { ((px - 1.0).max(0.0) / crate::board::RES * 100.0).floor() / 100.0 }; out.insert(z["id"].as_str().unwrap_or("").to_string(), g.max(0.01)); }
    }
    out
}

/// `fills` holds one mask per copper layer: everything filled on it (the net is empty). Until 2026-11-11 it held one whole-board mask
/// per zone, which on a board with 1201 read islands (test board 11, 72 x 175 mm) was 6 GB and killed `build`. `zones_filled` counts the zones.
/// `no_fill`: read pours drawn with an outline and no fill, each with its area and what covers it (`{"id", "layer", "net", "areaMm2", "why"}`).
pub struct Board { pub text: String, pub pads: Vec<Pad>, pub fills: Vec<(String, String, Mask)>, pub zones_filled: usize, pub no_fill: Vec<Value>, pub grid: Grid, pub warnings: Vec<String> }

/// A patch of exposed metal that no footprint explains, drawn from the photo into PHOTO1 as a custom pad: no net, no drill, and a `Pad` that is only its box.
pub fn is_photo_metal(p: &Pad) -> bool { p.part == "PHOTO1" && p.num.starts_with('M') && p.drill <= 0.0 && p.net.is_empty() }

/// Write the board. `layers` is the copper layer count (2, 4, 6).
pub fn board(cache: &Path, parts: &[Value], copper: &Value, nets_doc: &Value, layers: usize, title: &str) -> Result<Board, String> { board_opt(cache, parts, copper, nets_doc, layers, title, true) }

/// `filled`: write each zone's computed fill. A board for the router goes unfilled, so the router's gate
/// fills around the copper it adds instead of checking it against a fill drawn before it existed.
pub fn board_opt(cache: &Path, parts: &[Value], copper: &Value, nets_doc: &Value, layers: usize, title: &str, filled: bool) -> Result<Board, String> {
    let mut warnings = vec![];
    // nets: from nets.json pins, plus every zone, trace and via net
    let mut pin_net: HashMap<String, String> = HashMap::new();
    let mut names: Vec<String> = vec![];
    let mut add = |n: &str, names: &mut Vec<String>| { if !n.is_empty() && !names.iter().any(|x| x == n) { names.push(n.to_string()); } };
    for n in nets_doc["nets"].as_array().into_iter().flatten() {
        let name = n["name"].as_str().unwrap_or(""); add(name, &mut names);
        for p in n["pins"].as_array().into_iter().flatten().filter_map(|p| p.as_str()) { pin_net.insert(p.to_string(), name.to_string()); }
    }
    for k in ["zones", "traces", "vias"] { for z in copper[k].as_array().into_iter().flatten() { add(z["net"].as_str().unwrap_or(""), &mut names); } }
    let net_idx: HashMap<String, usize> = names.iter().enumerate().map(|(i, n)| (n.clone(), i + 1)).collect();
    // footprints; a run that has traced the photos draws its silk, pads, holes and outline from that
    let photo = cache.parent().and_then(|l| l.parent()).and_then(crate::photolayers::load);
    let mut photo_polys: HashMap<String, Vec<(f64, f64)>> = HashMap::new();
    let mut fps = vec![]; let mut pads = vec![];
    for p in parts {
        if p["onBoard"] == Value::Bool(false) { continue; }
        let id = p["footprint"].as_str().unwrap_or("");
        if id.is_empty() { warnings.push(format!("{}: no footprint", p["ref"].as_str().unwrap_or("?"))); continue; }
        match footprint_text(cache, id, p).and_then(|t| placed(&t, match id { "generated:lug" => "Generated:Lug", "generated:hole" => "Generated:Hole", _ => id }, p, &pin_net, &net_idx)) {
            Ok((mut n, mut ps)) => {
                if let Some(doc) = &photo { crate::photolayers::strip_silk(&mut n); crate::photolayers::apply_pads(doc, &mut n, &mut ps, p, &mut photo_polys); }
                fps.push(n); pads.extend(ps);
            }
            // said with the part's name, so `build` and `auto` can name the footprint that is wanted (main.rs writes LEFT_OUT from these)
            Err(e) => warnings.push(format!("{}{}: {e}", LEFT_OUT_MARK, p["ref"].as_str().unwrap_or("?"))),
        }
    }
    let extras = photo.as_ref().and_then(crate::photolayers::extras_footprint);
    if let Some((_, ps)) = &extras { pads.extend(ps.iter().cloned()); }
    // which pads carry a photographed outline
    let mut seen_k: HashMap<String, usize> = HashMap::new();
    let shaped: HashMap<usize, Vec<(f64, f64)>> = pads.iter().enumerate().filter_map(|(i, p)| { let key = format!("{}.{}", p.part, p.num); let e = seen_k.entry(key.clone()).or_default(); let k = *e; *e += 1; photo_polys.get(&format!("{key}#{k}")).map(|poly| (i, poly.clone())) }).collect();
    // outline
    let outline: Vec<(f64, f64)> = copper["outline"]["points_mm"].as_array().ok_or("copper.json has no outline.points_mm")?.iter().map(pt).collect();
    let (bx0, by0) = outline.iter().fold((f64::MAX, f64::MAX), |a, p| (a.0.min(p.0), a.1.min(p.1)));
    let (bx1, by1) = outline.iter().fold((f64::MIN, f64::MIN), |a, p| (a.0.max(p.0), a.1.max(p.1)));
    let radius = copper["outline"]["corner_mm"].as_f64().unwrap_or(0.0);
    let grid = Grid { x0: bx0, y0: by0, res: 20.0, w: ((bx1 - bx0) * 20.0).ceil() as usize + 1, h: ((by1 - by0) * 20.0).ceil() as usize + 1 };
    let cu_layers: Vec<String> = { let mut v = vec!["F.Cu".to_string()]; for i in 1..layers.saturating_sub(1) { v.push(format!("In{i}.Cu")); } v.push("B.Cu".into()); v };
    // board area inset by the edge clearance
    let inside = board_inside(&grid, &outline, radius);
    // zones stay the edge clearance inside the board, plus one raster cell
    let edge_ok = inside.erode(((copper["edge_clearance_mm"].as_f64().unwrap_or(0.5) + 1.0 / 20.0) * grid.res) as f32);
    // fills, highest priority first
    let mut zones: Vec<Value> = copper["zones"].as_array().cloned().unwrap_or_default();
    zones.sort_by(|a, b| fv(b, "priority").partial_cmp(&fv(a, "priority")).unwrap());
    let photo_clearance = if std::env::var("ZONE_RULE_CLEARANCE").is_ok() { HashMap::new() } else { photo_gaps(copper, &pads, &shaped, ((bx1 - crate::board::ORIGIN) * crate::board::RES).ceil() as usize + 2, ((by1 - crate::board::ORIGIN) * crate::board::RES).ceil() as usize + 2) };
    let mut fills: Vec<(String, String, Mask)> = vec![]; let mut zones_filled = 0usize; let mut no_fill: Vec<Value> = vec![];
    let mut dilated: Vec<(String, String, Sparse)> = vec![];
    let mut zone_nodes = vec![];
    for z in &zones {
        let layer = z["layer"].as_str().unwrap_or("F.Cu").to_string();
        if !cu_layers.contains(&layer) { warnings.push(format!("zone {} on {layer}: not a layer of a {layers}-layer board", z["id"])); continue; }
        let net = z["net"].as_str().unwrap_or("").to_string();
        let poly: Vec<(f64, f64)> = z["polygon_mm"].as_array().map(|a| a.iter().map(pt).collect()).unwrap_or_else(|| outline.clone());
        // one raster cell of margin, so a fill drawn at 20 px/mm never comes closer than the clearance
        let clr_rule = z["clearance_mm"].as_f64().unwrap_or(0.2);
        let clr = clr_rule + 2.0 / 20.0;
        let minw = z["min_width_mm"].as_f64().unwrap_or(0.2);
        let zm = zone_mask(&grid, z, &poly);
        let mut fill = zm.and(&edge_ok);
        let mut other = grid.empty(); let mut same = grid.empty();
        // a pour read from the photo is what the photo shows: rule clearance around other seen copper would redraw it
        let photo = z["rle_px"].is_array();
        let clr = if photo { 0.0 } else { clr };
        // only what is near this zone matters
        let zb = { let (mut a, mut b, mut c, mut d) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN); for q in &poly { a = a.min(q.0); b = b.min(q.1); c = c.max(q.0); d = d.max(q.1); } (a - 2.0, b - 2.0, c + 2.0, d + 2.0) };
        let nearby = |x: f64, y: f64| x >= zb.0 && x <= zb.2 && y >= zb.1 && y <= zb.3;
        let mut near_other: Vec<String> = vec![];
        for (i, p) in pads.iter().enumerate().filter(|(_, p)| nearby(p.x, p.y)) { if p.on(&layer) {
            // Exposed metal no footprint explains (PHOTO1.M<n>, `photolayers::extras_footprint`) is known here only by the box round its
            // outline, which can be many times its area: on test board 4 an 11.4 x 9.4 mm box round one such patch wiped the whole of
            // isl-top-765 (8 mm2, a terminal's land and its track arm) out of its own fill, and `check mimic` then stopped the run on
            // "zones with no fill". It carries no net and is the same metal the photo shows, so a pour read from the photo is not cut by it.
            if photo && is_photo_metal(p) { continue; }
            if !(p.net == net && !net.is_empty()) { near_other.push(format!("{}.{}", p.part, p.num)); }
            if p.net == net && !net.is_empty() { grid.pad(&mut same, p, 0.0); }
            else if let Some(poly) = shaped.get(&i) { grid.poly(&mut other, poly); for s in 0..poly.len() { grid.seg(&mut other, poly[s], poly[(s + 1) % poly.len()], 2.0 * clr); } } // a photographed pad clears by its own shape
            else { grid.pad(&mut other, p, clr); }
            // the photo cannot show a gap beside a pad: the mask's edge, glare and the part hide it (fidelity::BESIDE_PX). Copper of another net keeps that far away, or the two would short
            if photo && p.net != net { let c = PAD_GAP.min(clr_rule); if let Some(poly) = shaped.get(&i) { grid.poly(&mut other, poly); for s in 0..poly.len() { grid.seg(&mut other, poly[s], poly[(s + 1) % poly.len()], 2.0 * c); } } else { grid.pad(&mut other, p, c); } }
        } }
        for t in copper["traces"].as_array().into_iter().flatten().filter(|t| t["layer"] == Value::String(layer.clone())) {
            let path: Vec<(f64, f64)> = t["path_mm"].as_array().map(|a| a.iter().map(pt).collect()).unwrap_or_default();
            let w = fv(t, "width_mm").max(0.1);
            let seen = t["from"].as_str() == Some("islands");
            let t_clr = if photo && !seen { clr_rule + 2.0 / 20.0 } else { clr };
            for s in path.windows(2) { if !nearby(s[0].0, s[0].1) && !nearby(s[1].0, s[1].1) && crate::geom::dist(s[0], s[1]) < 4.0 { continue; } if t["net"].as_str() == Some(&net) { grid.seg(&mut same, s[0], s[1], w); } else if !(photo && seen) { grid.seg(&mut other, s[0], s[1], w + 2.0 * t_clr); } }
        }
        for v in copper["vias"].as_array().into_iter().flatten().filter(|v| !v["net"].as_str().unwrap_or("").is_empty()) {
            let (x, y) = pt(&v["pos_mm"]); let d = v["diameter_mm"].as_f64().unwrap_or(0.6);
            if !nearby(x, y) { continue; }
            if v["net"].as_str() == Some(&net) { grid.disk(&mut same, x, y, d / 2.0); } else { grid.disk(&mut other, x, y, d / 2.0 + if photo { VIA_GAP } else { clr }); }
        }
        if !photo { for (_, fl, fm) in dilated.iter().filter(|(fl2, _, _)| *fl2 == layer) { if *fl != net { fm.subtract_from(&mut fill); } } }
        fill = fill.andnot(&other);
        if !photo { fill = fill.open((minw / 2.0 * grid.res) as f32); }
        // islands: keep the pieces that touch same-net copper (all, if the layer has none of that net)
        let (lab, cs) = raster::components(&fill);
        let touch: std::collections::HashSet<u32> = (0..lab.len()).filter(|i| same.d[*i] && lab[*i] != 0).map(|i| lab[i]).collect();
        if photo { }
        else if !touch.is_empty() { for i in 0..lab.len() { if lab[i] != 0 && !touch.contains(&lab[i]) { fill.d[i] = false; } } }
        else if cs.len() > 1 { warnings.push(format!("zone {} ({net} on {layer}): no {net} copper inside it on this layer, so every island is kept", z["id"])); }
        // one zone per connected piece: KiCad reads the first polygon of a zone as its outline and every later one as a hole in it
        let pieces: Vec<(Vec<Vec<(f64, f64)>>, Vec<Vec<(f64, f64)>>)> = if photo { photo_pieces(&grid, z, &other).into_iter().map(|p| { let mut o = vec![p.outer]; o.extend(p.holes); (o, p.rings) }).collect() } else { vec![(vec![poly.clone()], vectorize(&grid, &fill))] };
        // a read pour that other-net copper and its clearance cover whole is drawn with its outline and no fill: said, with what covers it, not left for `check mimic` to find
        if photo && filled && !pieces.is_empty() && pieces.iter().all(|p| p.1.is_empty()) {
            near_other.sort(); near_other.dedup();
            no_fill.push(serde_json::json!({"id": z["id"], "layer": layer, "net": net, "areaMm2": z["areaMm2"], "why": if near_other.is_empty() { "every part of it lies inside copper of another net, or its clearance, on this layer".to_string() } else { format!("every part of it lies inside pads of another net, or of no net, and their clearance: {}{}", near_other.iter().take(6).cloned().collect::<Vec<_>>().join(", "), if near_other.len() > 6 { format!(" and {} more", near_other.len() - 6) } else { String::new() }) }}));
        }
        for (k, (outline, rings)) in pieces.into_iter().enumerate() {
            let id = z["id"].as_str().unwrap_or("").to_string(); let id = if k == 0 { id } else { format!("{id}#{k}") };
            let mut zn = vec![a("zone"), l(vec![a("net"), a(net_idx.get(&net).copied().unwrap_or(0))]), l(vec![a("net_name"), q(&net)]), l(vec![a("layer"), q(&layer)]),
                l(vec![a("uuid"), q(&uuid(&format!("zone/{id}")))]), l(vec![a("name"), q(&id)]), l(vec![a("hatch"), a("edge"), a("0.5")])];
            if let Some(p) = z["priority"].as_u64() { zn.push(l(vec![a("priority"), a(p)])); }
            let connect = z["connect"].as_str().unwrap_or("thermal");
            // a pour read from the photo: its clearance is the gap the photo shows, or a refill would cut it back to the rule
            let zc = if photo { photo_clearance.get(z["id"].as_str().unwrap_or("")).copied().unwrap_or(clr_rule).min(clr_rule) } else { clr_rule };
            let mut cp = vec![a("connect_pads")]; if connect == "solid" { cp.push(a("yes")); } cp.push(l(vec![a("clearance"), f(zc)])); zn.push(l(cp));
            zn.push(l(vec![a("min_thickness"), f(if photo { PHOTO_MIN_THICKNESS } else { minw })])); zn.push(l(vec![a("filled_areas_thickness"), a("no")]));
            // a read pour with no pad of its net on this layer is still what the photo shows: mode 1 keeps islands on a refill
            zn.push(l(vec![a("fill"), a("yes"), l(vec![a("thermal_gap"), f(z["thermal_gap_mm"].as_f64().unwrap_or(0.3))]), l(vec![a("thermal_bridge_width"), f(z["spoke_mm"].as_f64().unwrap_or(0.3))]), l(vec![a("island_removal_mode"), a(if photo { "1" } else { "0" })])]));
            for o in &outline { zn.push(l(vec![a("polygon"), l(std::iter::once(a("pts")).chain(o.iter().map(|p| l(vec![a("xy"), f(p.0), f(p.1)]))).collect())])); }
            for r in rings.into_iter().filter(|_| filled) { zn.push(l(vec![a("filled_polygon"), l(vec![a("layer"), q(&layer)]), l(std::iter::once(a("pts")).chain(r.iter().map(|p| l(vec![a("xy"), f(p.0), f(p.1)]))).collect())])); }
            zone_nodes.push(l(zn));
        }
        dilated.push((layer.clone(), net.clone(), Sparse::of(&fill.dilate((clr * grid.res) as f32))));
        zones_filled += 1;
        match fills.iter_mut().find(|x| x.0 == layer) { Some(x) => { for (a_, b_) in x.2.d.iter_mut().zip(fill.d.iter()) { *a_ |= *b_; } } None => fills.push((layer, String::new(), fill)) }
    }
    // the file
    let mut out = String::from("(kicad_pcb\n\t(version 20241229)\n\t(generator \"adom-aiflow-reverse\")\n\t(generator_version \"9.0\")\n\t(general (thickness 1.6) (legacy_teardrops no))\n\t(paper \"A4\")\n");
    out += &format!("\t(title_block (title \"{}\") (comment 1 \"Generated by adom-aiflow-reverse from photos: see reverse-flow/ for the evidence of every item\"))\n", title.replace('"', "'"));
    out += "\t(layers\n\t\t(0 \"F.Cu\" signal)\n";
    for i in 1..layers.saturating_sub(1) { out += &format!("\t\t({} \"In{i}.Cu\" signal)\n", 2 + 2 * i); }
    out += "\t\t(2 \"B.Cu\" signal)\n\t\t(9 \"F.Adhes\" user \"F.Adhesive\")\n\t\t(11 \"B.Adhes\" user \"B.Adhesive\")\n\t\t(13 \"F.Paste\" user)\n\t\t(15 \"B.Paste\" user)\n\t\t(5 \"F.SilkS\" user \"F.Silkscreen\")\n\t\t(7 \"B.SilkS\" user \"B.Silkscreen\")\n\t\t(1 \"F.Mask\" user)\n\t\t(3 \"B.Mask\" user)\n\t\t(17 \"Dwgs.User\" user \"User.Drawings\")\n\t\t(19 \"Cmts.User\" user \"User.Comments\")\n\t\t(25 \"Edge.Cuts\" user)\n\t\t(27 \"Margin\" user)\n\t\t(31 \"F.CrtYd\" user \"F.Courtyard\")\n\t\t(29 \"B.CrtYd\" user \"B.Courtyard\")\n\t\t(35 \"F.Fab\" user)\n\t\t(33 \"B.Fab\" user))\n";
    out += "\t(setup (pad_to_mask_clearance 0) (allow_soldermask_bridges_in_footprints no))\n\t(net 0 \"\")\n";
    for (i, n) in names.iter().enumerate() { out += &format!("\t(net {} \"{}\")\n", i + 1, n.replace('"', "'")); }
    for n in &fps { out += "\t"; out += &n.to_string(); out += "\n"; }
    if let Some((t, _)) = &extras { out += "\t"; out += t; }
    if let Some(doc) = &photo { out += &crate::photolayers::graphics(doc); }
    let photo_edge = photo.as_ref().and_then(crate::photolayers::edge_cuts);
    if let Some(e) = &photo_edge { out += e; }
    // Edge.Cuts: the outline, with arcs where a corner radius was measured
    let edge = |s: (f64, f64), e: (f64, f64), k: usize| format!("\t(gr_line (start {:.4} {:.4}) (end {:.4} {:.4}) (stroke (width 0.1) (type default)) (layer \"Edge.Cuts\") (uuid \"{}\"))\n", s.0, s.1, e.0, e.1, uuid(&format!("edge/{k}")));
    if photo_edge.is_some() { } else if radius > 0.0 && outline.len() == 4 {
        let r = radius; let (x0, y0, x1, y1) = (bx0, by0, bx1, by1); let c45 = r * (1.0 - std::f64::consts::FRAC_1_SQRT_2);
        out += &edge((x0 + r, y0), (x1 - r, y0), 0); out += &edge((x1, y0 + r), (x1, y1 - r), 1); out += &edge((x1 - r, y1), (x0 + r, y1), 2); out += &edge((x0, y1 - r), (x0, y0 + r), 3);
        for (k, (s, m, e)) in [((x0, y0 + r), (x0 + c45, y0 + c45), (x0 + r, y0)), ((x1 - r, y0), (x1 - c45, y0 + c45), (x1, y0 + r)), ((x1, y1 - r), (x1 - c45, y1 - c45), (x1 - r, y1)), ((x0 + r, y1), (x0 + c45, y1 - c45), (x0, y1 - r))].iter().enumerate() {
            out += &format!("\t(gr_arc (start {:.4} {:.4}) (mid {:.4} {:.4}) (end {:.4} {:.4}) (stroke (width 0.1) (type default)) (layer \"Edge.Cuts\") (uuid \"{}\"))\n", s.0, s.1, m.0, m.1, e.0, e.1, uuid(&format!("arc/{k}")));
        }
    } else { for i in 0..outline.len() { out += &edge(outline[i], outline[(i + 1) % outline.len()], i); } }
    for (k, t) in copper["traces"].as_array().into_iter().flatten().enumerate() {
        let path: Vec<(f64, f64)> = t["path_mm"].as_array().map(|a| a.iter().map(pt).collect()).unwrap_or_default();
        let net = net_idx.get(t["net"].as_str().unwrap_or("")).copied().unwrap_or(0);
        for (j, s) in path.windows(2).enumerate() {
            out += &format!("\t(segment (start {:.4} {:.4}) (end {:.4} {:.4}) (width {:.3}) (layer \"{}\") (net {net}) (uuid \"{}\"))\n", s[0].0, s[0].1, s[1].0, s[1].1, seg_width(t, j), t["layer"].as_str().unwrap_or("F.Cu"), uuid(&format!("seg/{k}/{j}")));
        }
    }
    for (k, v) in copper["vias"].as_array().into_iter().flatten().enumerate() {
        // a via whose net is not known yet is evidence only: it is not written into the board
        if v["net"].as_str().unwrap_or("").is_empty() { continue; }
        let (x, y) = pt(&v["pos_mm"]); let net = net_idx.get(v["net"].as_str().unwrap_or("")).copied().unwrap_or(0);
        out += &format!("\t(via (at {x:.4} {y:.4}) (size {:.3}) (drill {:.3}) (layers \"F.Cu\" \"B.Cu\") (net {net}) (uuid \"{}\"))\n", v["diameter_mm"].as_f64().unwrap_or(0.6), v["drill_mm"].as_f64().unwrap_or(0.3), uuid(&format!("via/{k}")));
    }
    for z in &zone_nodes { out += "\t"; out += &z.to_string(); out += "\n"; }
    out += ")\n";
    Ok(Board { text: out, pads, fills, zones_filled, no_fill, grid, warnings })
}

/// A zone's copper: its exact runs when it was traced from a photo, otherwise everything inside its outline.
pub fn zone_mask(g: &Grid, z: &Value, poly: &[(f64, f64)]) -> Mask {
    let mut m = g.empty();
    if let Some(rows) = z["rle"].as_array() {
        for r in rows { let Some(a) = r.as_array() else { continue }; let v = a[0].as_u64().unwrap_or(0) as usize; if v >= g.h { continue; }
            for c in a[1..].chunks(2) { if c.len() < 2 { continue; } let (u0, u1) = (c[0].as_u64().unwrap_or(0) as usize, (c[1].as_u64().unwrap_or(0) as usize).min(g.w)); for u in u0..u1 { m.d[v * g.w + u] = true; } } }
    } else { g.poly(&mut m, poly); }
    m
}

/// The board's area as a mask, rounded corners included.
pub fn board_inside(g: &Grid, outline: &[(f64, f64)], radius: f64) -> Mask {
    let mut m = g.empty();
    if radius > 0.0 && outline.len() == 4 {
        let (x0, y0) = outline.iter().fold((f64::MAX, f64::MAX), |a, p| (a.0.min(p.0), a.1.min(p.1)));
        let (x1, y1) = outline.iter().fold((f64::MIN, f64::MIN), |a, p| (a.0.max(p.0), a.1.max(p.1)));
        let mut poly = vec![];
        for (cx, cy, a0) in [(x1 - radius, y0 + radius, -90.0f64), (x1 - radius, y1 - radius, 0.0), (x0 + radius, y1 - radius, 90.0), (x0 + radius, y0 + radius, 180.0)] {
            for k in 0..=12 { let t = (a0 + k as f64 * 7.5).to_radians(); poly.push((cx + radius * t.cos(), cy + radius * t.sin())); }
        }
        g.poly(&mut m, &poly);
    } else { g.poly(&mut m, outline); }
    m
}

pub fn cache_dir(flow: &Path) -> PathBuf { flow.join("lib").join("fp") }

/// A build warning that starts with this is a part the board does not carry, because its footprint did not load.
pub const LEFT_OUT_MARK: &str = "LEFT OUT of the board, ";
/// What the last build left out, written by `build` on every run (empty when nothing was): `{"leftOut": [{"ref", "footprint", "why"}]}`.
pub const LEFT_OUT: &str = "build-left-out.json";

/// The parts a build's warnings say it left out, as rows for `LEFT_OUT`.
pub fn left_out_rows(warnings: &[String], parts: &[Value]) -> Vec<Value> {
    warnings.iter().filter_map(|w| w.strip_prefix(LEFT_OUT_MARK)).filter_map(|w| w.split_once(": ")).map(|(r, why)| {
        let fp = parts.iter().find(|p| p["ref"].as_str() == Some(r)).and_then(|p| p["footprint"].as_str()).unwrap_or("");
        let file = fp.split_once(':').map(|(lib, name)| format!("; a file of your own goes at reverse-flow/lib/fp/{lib}/{name}.kicad_mod")).unwrap_or_default();
        serde_json::json!({"ref": r, "footprint": fp, "why": format!("its footprint {fp} did not load ({why}){file}")})
    }).collect()
}

#[cfg(test)]
mod flip_tests {
    use super::*;
    use serde_json::json;
    #[test]
    fn a_body_is_the_fab_drawing_at_the_parts_place_on_either_face() {
        let dir = std::env::temp_dir().join(format!("bodies-{}", std::process::id())); std::fs::create_dir_all(dir.join("Read")).unwrap();
        std::fs::write(dir.join("Read/Body_3x2.kicad_mod"), r#"(footprint "Body_3x2" (layer "F.Cu") (attr smd)
 (property "Reference" "REF**" (at 0 -2) (layer "F.SilkS"))
 (fp_rect (start -1 -0.5) (end 2 1.5) (stroke (width 0.1) (type solid)) (fill none) (layer "F.Fab"))
 (fp_rect (start -1.5 -1) (end 2.5 2) (stroke (width 0.05) (type solid)) (fill none) (layer "F.CrtYd")))"#).unwrap();
        let parts = [json!({"ref": "U1", "footprint": "Read:Body_3x2", "pos_mm": [110.0, 110.0], "rot": 0, "side": "top"}), json!({"ref": "U2", "footprint": "Read:Body_3x2", "pos_mm": [120.0, 110.0], "rot": 0, "side": "bottom"}), json!({"ref": "U3", "footprint": "Read:Not_cached", "pos_mm": [0.0, 0.0], "rot": 0, "side": "top"})];
        let b = bodies_of(&dir, &parts);
        let _ = std::fs::remove_dir_all(&dir);
        assert_eq!(b.len(), 2, "a footprint that is not cached has no body to read");
        assert_eq!((b[0].layer, b[0].pads, b[0].bx), ("F.Cu", 0, (-1.0, -0.5, 2.0, 1.5)), "the courtyard is not the body");
        assert!(b[0].holds(111.9, 111.4, 0.0) && !b[0].holds(111.9, 109.4, 0.0));
        // turned over, the drawing is mirrored top to bottom
        assert_eq!(b[1].layer, "B.Cu");
        assert!(b[1].holds(121.9, 108.6, 0.0) && !b[1].holds(121.9, 111.4, 0.0));
    }
    #[test]
    fn a_bottom_part_lands_mirrored_on_the_back_layers() {
        let text = r#"(footprint "X" (layer "F.Cu") (fp_line (start 1 2) (end 3 4) (layer "F.SilkS")) (pad "1" smd rect (at -0.5 0.25 90) (size 0.6 0.5) (layers "F.Cu" "F.Mask" "F.Paste")))"#;
        let part = json!({"ref": "C1", "side": "bottom", "pos_mm": [110.0, 120.0], "rot": 0.0});
        let (n, pads) = placed(text, "L:X", &part, &HashMap::new(), &HashMap::new()).unwrap();
        assert_eq!(pads.len(), 1);
        assert!(pads[0].on("B.Cu") && !pads[0].on("F.Cu"), "{:?}", pads[0].layers);
        assert!((pads[0].x - 109.5).abs() < 1e-9 && (pads[0].y - 119.75).abs() < 1e-9, "{:?}", pads[0]);
        let body = format!("{n:?}");
        assert!(body.contains("B.SilkS") && !body.contains("F.SilkS"));
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn placement_matches_kicad() {
        // a pad at local (1, 0) of a footprint at (10, 10) turned 90 degrees lands above it (y smaller)
        let p = place(10.0, 10.0, 90.0, 1.0, 0.0);
        assert!((p.0 - 10.0).abs() < 1e-9 && (p.1 - 9.0).abs() < 1e-9, "{p:?}");
        assert_eq!(uuid("a").len(), 36);
    }
}

#[cfg(test)]
mod photo_zone_tests {
    use super::*;
    #[test]
    fn loops_along_pixel_edges_fill_exactly_the_pixels() {
        // an L of 3 pixels with one pixel touching it only at a corner: 4-connected, so that pixel is not in this piece
        let on = [(1i64, 1i64), (2, 1), (1, 2)];
        let inside = |x: i64, y: i64| on.contains(&(x, y));
        let l = crack_loops(&inside, 0, 0, 4, 4);
        assert_eq!(l.len(), 1);
        let area = (0..l[0].len()).map(|i| { let (a, b) = (l[0][i], l[0][(i + 1) % l[0].len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>() / 2.0;
        assert!((area - 3.0).abs() < 1e-9, "{area}");
        // a ring has an outline and a hole, wound opposite ways
        let inside2 = |x: i64, y: i64| (0..3).contains(&x) && (0..3).contains(&y) && (x, y) != (1, 1);
        let r = crack_loops(&inside2, 0, 0, 3, 3);
        let areas: Vec<f64> = r.iter().map(|q| (0..q.len()).map(|i| { let (a, b) = (q[i], q[(i + 1) % q.len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>() / 2.0).collect();
        assert_eq!(r.len(), 2); assert!(areas.contains(&9.0) && areas.contains(&-1.0), "{areas:?}");
        // two pixels touching at a corner stay two loops
        let inside3 = |x: i64, y: i64| (x, y) == (0, 0) || (x, y) == (1, 1);
        assert_eq!(crack_loops(&inside3, 0, 0, 2, 2).len(), 2);
    }
    #[test]
    fn a_read_pour_keeps_its_hole_in_the_outline_and_the_fill_and_another_nets_via_cuts_only_the_fill() {
        // a 2 x 2 mm pour with a 0.5 mm hole, at the image's own pixels
        let rows: Vec<Value> = (0..80).map(|y| if (30..50).contains(&y) { serde_json::json!([y, 0, 30, 50, 80]) } else { serde_json::json!([y, 0, 80]) }).collect();
        let z = serde_json::json!({"rle_px": rows});
        let g = Grid { x0: 100.0, y0: 100.0, res: 20.0, w: 60, h: 60 };
        let none = g.empty();
        let p = photo_pieces(&g, &z, &none);
        assert_eq!(p.len(), 1); assert_eq!(p[0].holes.len(), 1, "the hole goes in the outline"); assert_eq!(p[0].rings.len(), 1);
        let area = |r: &[(f64, f64)]| (0..r.len()).map(|i| { let (a, b) = (r[i], r[(i + 1) % r.len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>().abs() / 2.0;
        assert!((area(&p[0].rings[0]) - (4.0 - 0.25)).abs() < 0.2, "{}", area(&p[0].rings[0]));
        let mut other = g.empty(); g.disk(&mut other, 100.4, 100.4, 0.2);
        let q = photo_pieces(&g, &z, &other);
        assert_eq!(q[0].holes.len(), 1, "the outline is what was read"); assert!(area(&q[0].rings[0]) < area(&p[0].rings[0]) - 0.05, "the fill clears the via");
    }
}

#[cfg(test)]
mod keyhole_tests {
    use super::*;
    fn crosses(r: &[(f64, f64)]) -> bool {
        let n = r.len();
        let side = |a: (f64, f64), b: (f64, f64), c: (f64, f64)| (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0);
        for i in 0..n { for j in i + 2..n { if i == 0 && j == n - 1 { continue; }
            let (a, b, c, d) = (r[i], r[(i + 1) % n], r[j], r[(j + 1) % n]);
            let (s1, s2, s3, s4) = (side(a, b, c), side(a, b, d), side(c, d, a), side(c, d, b));
            if s1 * s2 < -1e-9 && s3 * s4 < -1e-9 { return true; }
        } }
        false
    }
    #[test]
    fn many_holes_never_cross_their_slits() {
        let outer = vec![(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)];
        let mut holes = vec![];
        for j in 0..7 { for i in 0..7 { let (x, y) = (8.0 + i as f64 * 13.0 + (j % 2) as f64 * 3.0, 8.0 + j as f64 * 13.0 + (i % 3) as f64); holes.push(vec![(x, y), (x + 3.0, y), (x + 3.0, y + 3.0), (x, y + 3.0)]); } }
        let r = keyhole(outer.clone(), holes);
        assert_eq!(r.len(), 4 + 49 * 7);
        assert!(!crosses(&r));
        // holes wind against the outline: the total area is the outline minus the holes
        let area = |r: &[(f64, f64)]| (0..r.len()).map(|i| { let (a, b) = (r[i], r[(i + 1) % r.len()]); a.0 * b.1 - b.0 * a.1 }).sum::<f64>().abs() / 2.0;
        assert!((area(&r) - (area(&outer) - 49.0 * 9.0)).abs() < 1e-6, "{}", area(&r));
    }
}