AI Flow: Routing

//! The board as this router sees it: copper layers, nets, footprints and pads with their exact
//! outlines, tracks, vias, zones, the edge and every hole. Read straight from a `.kicad_pcb`.

use crate::geom::*;
use crate::sx::{self, Node};
use std::collections::{BTreeMap, HashMap};

pub type NetId = u32;
pub const NO_NET: NetId = 0;

#[derive(Clone, Debug)]
pub struct Layer {
    pub name: String,
    pub signal: bool,
}

#[derive(Clone, Debug)]
pub struct Pad {
    pub fp: usize,
    pub number: String,
    pub net: NetId,
    pub center: P,
    pub shape: Shape,
    /// Copper layers the pad exists on (indices into `Board::layers`).
    pub layers: Vec<usize>,
    pub drill: Option<f64>,
    pub npth: bool,
    /// The pad's own clearance override, else its footprint's, in nm (0 when it has none). KiCad's
    /// DRC holds other copper to it even where the net class allows less.
    pub local_clearance: f64,
    /// The pad's own way of joining a pour (`zone_connect`: 0 none, 1 thermal relief, 2 solid, 3
    /// thermal for through-hole only), its footprint's if it has none, else the zone decides.
    pub zone_connect: Option<u8>,
    pub size: (f64, f64),
    pub angle: f64,
    /// Mask opening beyond the copper, resolved the way KiCad does: the pad's own margin, else the
    /// footprint's, else the board's pad_to_mask_clearance.
    pub mask_margin: f64,
    /// Opening in F.Mask and in B.Mask. A pad listing no mask layer has no opening at all.
    pub mask: (bool, bool),
    pub paste: bool,
    /// The schematic's electrical type (power_in, input, ...), empty when the file has none.
    pub pintype: String,
    /// The schematic's pin name (VCC_5, IOVDD_1, ...), empty when the file has none.
    pub pinfunction: String,
}

#[derive(Clone, Debug)]
pub struct Footprint {
    pub reference: String,
    pub value: String,
    pub lib: String,
    pub at: P,
    pub bottom: bool,
    pub pads: Vec<usize>,
    /// Smallest centre-to-centre distance between two of its copper pads, nm.
    pub min_pitch: f64,
    pub dnp: bool,
}

#[derive(Clone, Debug)]
pub struct Track {
    pub net: NetId,
    pub layer: usize,
    pub a: P,
    pub b: P,
    pub width: i64,
    pub span: (usize, usize),
}

#[derive(Clone, Debug)]
pub struct Via {
    pub net: NetId,
    pub at: P,
    pub size: i64,
    pub drill: i64,
    pub span: (usize, usize),
    /// Mask over the via on the front and back (4.4: every via tented on both sides).
    pub tent: (bool, bool),
}

/// A teardrop's filled copper, as KiCad wrote it. It is not an obstacle to routing but it does
/// count for solder mask, so the mask check reads it.
#[derive(Clone, Debug)]
pub struct Teardrop {
    pub net: NetId,
    pub layer: usize,
    pub pts: Vec<V>,
}

/// Board-wide mask settings from `(setup ...)`.
#[derive(Clone, Debug)]
pub struct MaskSetup {
    pub pad_to_mask: f64,
    /// Smallest web of mask between two openings.
    pub web: f64,
    pub allow_bridges_in_footprints: bool,
    pub tent: (bool, bool),
}

#[derive(Clone, Debug)]
pub struct Zone {
    pub net: NetId,
    pub layers: Vec<usize>,
    pub outline: Vec<V>,
    /// Filled copper per layer, as read from the file (empty when the zone is not filled).
    pub fills: Vec<(usize, Vec<V>)>,
    pub keepout_tracks: bool,
    pub keepout_vias: bool,
    pub priority: i64,
    pub name: String,
    /// `(keepout (copperpour not_allowed))`: no zone fills here.
    pub keepout_pour: bool,
    /// The zone's own clearance, nm (`connect_pads (clearance x)`), 0 when it sets none.
    pub clearance: f64,
    /// `min_thickness`, nm: copper narrower than this does not survive a refill.
    pub min_thickness: f64,
    /// `connect_pads no`: the fill keeps clear of pads of its own net.
    pub joins_pads: bool,
    /// Thermal reliefs (the default `connect_pads`): the gap round a pad and the width of the spokes
    /// across it, nm. None: pads join the fill solid (`connect_pads yes`) or not at all.
    pub thermal: Option<(f64, f64)>,
    /// `connect_pads thru_hole_only`: reliefs for through-hole pads, solid for the rest.
    pub thermal_tht_only: bool,
}

#[derive(Clone, Debug)]
pub struct Board {
    pub text: String,
    pub layers: Vec<Layer>,
    pub nets: Vec<String>,
    pub net_ids: HashMap<String, NetId>,
    pub footprints: Vec<Footprint>,
    pub pads: Vec<Pad>,
    pub tracks: Vec<Track>,
    pub vias: Vec<Via>,
    pub zones: Vec<Zone>,
    pub edges: Vec<(V, V)>,
    pub bbox: (f64, f64, f64, f64),
    /// Teardrops are stored as small zones. They are copper KiCad regenerates from the routing,
    /// so they are not obstacles, and they go when the routing goes.
    pub teardrop_spans: Vec<(usize, usize)>,
    pub teardrops: Vec<Teardrop>,
    pub mask: MaskSetup,
}

fn xy(n: &Node) -> Option<V> {
    Some(V(n.num(1)? * NM, n.num(2)? * NM))
}

impl Board {
    pub fn read(path: &str) -> Result<Board, String> {
        let text = std::fs::read_to_string(path).map_err(|e| format!("{path}: {e}"))?;
        Board::parse(text)
    }

    pub fn parse(text: String) -> Result<Board, String> {
        let root = sx::parse(&text)?;
        if root.head() != "kicad_pcb" {
            return Err("not a kicad_pcb file".into());
        }
        let mut b = Board {
            text: String::new(),
            layers: Vec::new(),
            nets: vec![String::new()],
            net_ids: HashMap::new(),
            footprints: Vec::new(),
            pads: Vec::new(),
            tracks: Vec::new(),
            vias: Vec::new(),
            zones: Vec::new(),
            edges: Vec::new(),
            bbox: (f64::MAX, f64::MAX, f64::MIN, f64::MIN),
            teardrop_spans: Vec::new(),
            teardrops: Vec::new(),
            mask: MaskSetup { pad_to_mask: 0.0, web: 0.0, allow_bridges_in_footprints: false, tent: (true, true) },
        };
        if let Some(s) = root.child("setup") {
            let num = |k: &str| s.child(k).and_then(|x| x.num(1)).unwrap_or(0.0) * NM;
            b.mask.pad_to_mask = num("pad_to_mask_clearance");
            b.mask.web = num("solder_mask_min_width");
            b.mask.allow_bridges_in_footprints = s.child("allow_soldermask_bridges_in_footprints").and_then(|x| x.atom(1)) == Some("yes");
            b.mask.tent = tent_of(s, (true, true));
        }
        b.net_ids.insert(String::new(), NO_NET);

        // Copper layers in stack order: F.Cu, inner layers by number, B.Cu.
        let mut inner: BTreeMap<u32, Layer> = BTreeMap::new();
        let (mut top, mut bot) = (None, None);
        if let Some(ls) = root.child("layers") {
            for l in ls.items() {
                let (Some(name), Some(kind)) = (l.atom(1), l.atom(2)) else { continue };
                if !name.ends_with(".Cu") {
                    continue;
                }
                let layer = Layer { name: name.to_string(), signal: kind == "signal" || kind == "mixed" };
                if name == "F.Cu" {
                    top = Some(layer);
                } else if name == "B.Cu" {
                    bot = Some(layer);
                } else if let Some(n) = name.strip_prefix("In").and_then(|s| s.strip_suffix(".Cu")).and_then(|s| s.parse().ok()) {
                    inner.insert(n, layer);
                }
            }
        }
        b.layers.extend(top);
        b.layers.extend(inner.into_values());
        b.layers.extend(bot);
        if b.layers.len() < 2 {
            return Err("board has fewer than two copper layers".into());
        }

        // Older files carry a net table; KiCad 10 writes the net by name on each item.
        let mut table: HashMap<i64, String> = HashMap::new();
        for n in root.children("net") {
            if let (Some(id), Some(name)) = (n.num(1), n.atom(2)) {
                table.insert(id as i64, name.to_string());
            }
        }
        let net_of = |b: &mut Board, node: &Node| -> NetId {
            let Some(n) = node.child("net") else { return NO_NET };
            let name = match (n.atom(1), n.atom(2)) {
                (_, Some(name)) => name.to_string(),
                (Some(a), None) => {
                    if let Some(name) = a.parse::<i64>().ok().and_then(|id| table.get(&id)) {
                        name.clone()
                    } else {
                        a.to_string()
                    }
                }
                _ => String::new(),
            };
            b.intern(&name)
        };

        for n in root.items() {
            match n.head() {
                "footprint" | "module" => b.read_footprint(n, &net_of)?,
                "segment" => {
                    let (Some(s), Some(e)) = (n.child("start").and_then(xy), n.child("end").and_then(xy)) else { continue };
                    let Some(layer) = n.child("layer").and_then(|l| l.atom(1)).and_then(|l| b.layer_index(l)) else { continue };
                    let width = mm(n.child("width").and_then(|w| w.num(1)).unwrap_or(0.0));
                    let net = net_of(&mut b, n);
                    b.tracks.push(Track { net, layer, a: to_p(s), b: to_p(e), width, span: n.span() });
                }
                "arc" => {
                    let (Some(s), Some(m), Some(e)) = (n.child("start").and_then(xy), n.child("mid").and_then(xy), n.child("end").and_then(xy)) else { continue };
                    let Some(layer) = n.child("layer").and_then(|l| l.atom(1)).and_then(|l| b.layer_index(l)) else { continue };
                    let width = mm(n.child("width").and_then(|w| w.num(1)).unwrap_or(0.0));
                    let net = net_of(&mut b, n);
                    let pts = arc_points(s, m, e, 50_000.0);
                    for w in pts.windows(2) {
                        b.tracks.push(Track { net, layer, a: to_p(w[0]), b: to_p(w[1]), width, span: n.span() });
                    }
                }
                "via" => {
                    let Some(at) = n.child("at").and_then(xy) else { continue };
                    let size = mm(n.child("size").and_then(|w| w.num(1)).unwrap_or(0.0));
                    let drill = mm(n.child("drill").and_then(|w| w.num(1)).unwrap_or(0.0));
                    let net = net_of(&mut b, n);
                    let tent = tent_of(n, b.mask.tent);
                    b.vias.push(Via { net, at: to_p(at), size, drill, span: n.span(), tent });
                }
                "zone" => b.read_zone(n, &net_of),
                "gr_line" | "gr_arc" | "gr_rect" | "gr_circle" | "gr_poly" => b.read_edge(n, &|v| v),
                _ => {}
            }
        }
        for e in b.edges.clone() {
            b.bbox = (b.bbox.0.min(e.0 .0).min(e.1 .0), b.bbox.1.min(e.0 .1).min(e.1 .1), b.bbox.2.max(e.0 .0).max(e.1 .0), b.bbox.3.max(e.0 .1).max(e.1 .1));
        }
        b.text = text;
        Ok(b)
    }

    pub fn intern(&mut self, name: &str) -> NetId {
        if let Some(&i) = self.net_ids.get(name) {
            return i;
        }
        let i = self.nets.len() as NetId;
        self.nets.push(name.to_string());
        self.net_ids.insert(name.to_string(), i);
        i
    }

    pub fn layer_index(&self, name: &str) -> Option<usize> {
        self.layers.iter().position(|l| l.name == name)
    }

    pub fn net_name(&self, n: NetId) -> &str {
        &self.nets[n as usize]
    }

    pub fn pad_name(&self, i: usize) -> String {
        let p = &self.pads[i];
        format!("{}.{}", self.footprints[p.fp].reference, p.number)
    }

    /// Layer indices named by a `(layers ...)` list, wildcards expanded.
    fn expand_layers(&self, names: &[&str]) -> Vec<usize> {
        let mut out = Vec::new();
        for n in names {
            match *n {
                "*.Cu" => out.extend(0..self.layers.len()),
                "F&B.Cu" => {
                    out.push(0);
                    out.push(self.layers.len() - 1);
                }
                other => out.extend(self.layer_index(other)),
            }
        }
        out.sort_unstable();
        out.dedup();
        out
    }

    fn read_footprint(&mut self, n: &Node, net_of: &dyn Fn(&mut Board, &Node) -> NetId) -> Result<(), String> {
        let at = n.child("at").ok_or("footprint without (at)")?;
        let (fx, fy) = (at.num(1).unwrap_or(0.0) * NM, at.num(2).unwrap_or(0.0) * NM);
        let frot = at.num(3).unwrap_or(0.0);
        let bottom = n.child("layer").and_then(|l| l.atom(1)) == Some("B.Cu");
        let mut reference = String::new();
        let mut value = String::new();
        for p in n.children("property") {
            match p.atom(1) {
                Some("Reference") => reference = p.atom(2).unwrap_or("").to_string(),
                Some("Value") => value = p.atom(2).unwrap_or("").to_string(),
                _ => {}
            }
        }
        for t in n.children("fp_text") {
            match t.atom(1) {
                Some("reference") if reference.is_empty() => reference = t.atom(2).unwrap_or("").to_string(),
                Some("value") if value.is_empty() => value = t.atom(2).unwrap_or("").to_string(),
                _ => {}
            }
        }
        let dnp = n.child("attr").map(|a| a.atoms().contains(&"dnp")).unwrap_or(false);
        let fp_idx = self.footprints.len();
        let lib = n.atom(1).unwrap_or("").to_string();
        let fp_margin = n.child("solder_mask_margin").and_then(|m| m.num(1));
        let mut fp = Footprint { reference, value, lib, at: (fx as i64, fy as i64), bottom, pads: Vec::new(), min_pitch: f64::INFINITY, dnp };
        for p in n.children("pad") {
            let kind = p.atom(2).unwrap_or("smd");
            let shape_name = p.atom(3).unwrap_or("rect");
            let pat = p.child("at").ok_or("pad without (at)")?;
            let (lx, ly) = (pat.num(1).unwrap_or(0.0) * NM, pat.num(2).unwrap_or(0.0) * NM);
            let pang = pat.num(3).unwrap_or(0.0);
            let (rx, ry) = rot(lx, ly, frot);
            let (cx, cy) = (fx + rx, fy + ry);
            let size = p.child("size").map(|s| (s.num(1).unwrap_or(0.0) * NM, s.num(2).unwrap_or(0.0) * NM)).unwrap_or((0.0, 0.0));
            let names = p.child("layers").map(|l| l.atoms().into_iter().skip(1).collect::<Vec<_>>()).unwrap_or_default();
            let layers = self.expand_layers(&names);
            let drill_node = p.child("drill");
            let drill = drill_node.and_then(|d| d.atoms().iter().skip(1).find_map(|a| a.parse::<f64>().ok())).map(|d| d * NM);
            let off = drill_node.and_then(|d| d.child("offset")).map(|o| (o.num(1).unwrap_or(0.0) * NM, o.num(2).unwrap_or(0.0) * NM)).unwrap_or((0.0, 0.0));
            let (ox, oy) = rot(off.0, off.1, pang);
            let center = V(cx + ox, cy + oy);
            let rr = p.child("roundrect_rratio").and_then(|r| r.num(1)).unwrap_or(0.0);
            let delta = p.child("rect_delta").map(|d| (d.num(1).unwrap_or(0.0) * NM, d.num(2).unwrap_or(0.0) * NM));
            let shape = pad_shape(shape_name, center, size, pang, rr, delta, p, kind);
            let net = net_of(self, p);
            let npth = kind == "np_thru_hole";
            let pi = self.pads.len();
            let mask_margin = p.child("solder_mask_margin").and_then(|m| m.num(1)).or(fp_margin).map(|m| m * NM).unwrap_or(self.mask.pad_to_mask);
            let has = |l: &str| names.iter().any(|n| *n == l || *n == "*.Mask" && l.ends_with(".Mask") || *n == "F&B.Mask" && l.ends_with(".Mask"));
            let mask = (has("F.Mask"), has("B.Mask"));
            let paste = names.iter().any(|n| n.ends_with(".Paste"));
            self.pads.push(Pad { fp: fp_idx, number: p.atom(1).unwrap_or("").to_string(), net, center: to_p(V(cx, cy)), shape, layers: if npth { Vec::new() } else { layers }, drill, npth, local_clearance: p.child("clearance").or(n.child("clearance")).and_then(|c| c.num(1)).unwrap_or(0.0) * NM, zone_connect: p.child("zone_connect").or(n.child("zone_connect")).and_then(|c| c.num(1)).map(|v| v as u8), size, angle: pang, mask_margin, mask, paste, pintype: p.child("pintype").and_then(|t| t.atom(1)).unwrap_or("").to_string(), pinfunction: p.child("pinfunction").and_then(|t| t.atom(1)).unwrap_or("").to_string() });
            fp.pads.push(pi);
        }
        for i in 0..fp.pads.len() {
            for j in i + 1..fp.pads.len() {
                let (a, b) = (&self.pads[fp.pads[i]], &self.pads[fp.pads[j]]);
                if a.layers.is_empty() || b.layers.is_empty() {
                    continue;
                }
                let d = hypot(sub(a.center.into(), b.center.into()));
                if d > 1.0 {
                    fp.min_pitch = fp.min_pitch.min(d);
                }
            }
        }
        self.footprints.push(fp);
        for z in n.children("zone") {
            self.read_zone(z, net_of);
        }
        let xf = |v: V| {
            let (x, y) = rot(v.0, v.1, frot);
            V(fx + x, fy + y)
        };
        for k in ["fp_line", "fp_arc", "fp_rect", "fp_circle", "fp_poly"] {
            for g in n.children(k) {
                self.read_edge(g, &xf);
            }
        }
        Ok(())
    }

    fn read_edge(&mut self, n: &Node, xf: &dyn Fn(V) -> V) {
        if n.child("layer").and_then(|l| l.atom(1)) != Some("Edge.Cuts") {
            return;
        }
        let head = n.head();
        if head.ends_with("_line") {
            if let (Some(a), Some(b)) = (n.child("start").and_then(xy), n.child("end").and_then(xy)) {
                self.edges.push((xf(a), xf(b)));
            }
        } else if head.ends_with("_arc") {
            if let (Some(a), Some(m), Some(b)) = (n.child("start").and_then(xy), n.child("mid").and_then(xy), n.child("end").and_then(xy)) {
                let pts = arc_points(xf(a), xf(m), xf(b), 100_000.0);
                for w in pts.windows(2) {
                    self.edges.push((w[0], w[1]));
                }
            }
        } else if head.ends_with("_rect") {
            if let (Some(a), Some(b)) = (n.child("start").and_then(xy), n.child("end").and_then(xy)) {
                let c = [a, V(b.0, a.1), b, V(a.0, b.1)];
                for i in 0..4 {
                    self.edges.push((xf(c[i]), xf(c[(i + 1) % 4])));
                }
            }
        } else if head.ends_with("_circle") {
            if let (Some(c), Some(e)) = (n.child("center").and_then(xy), n.child("end").and_then(xy)) {
                let r = hypot(sub(e, c));
                let pts: Vec<V> = (0..=48).map(|i| {
                    let a = i as f64 / 48.0 * std::f64::consts::TAU;
                    xf(V(c.0 + r * a.cos(), c.1 + r * a.sin()))
                }).collect();
                for w in pts.windows(2) {
                    self.edges.push((w[0], w[1]));
                }
            }
        } else if head.ends_with("_poly") {
            if let Some(pts) = n.child("pts") {
                let v: Vec<V> = pts.children("xy").filter_map(xy).map(xf).collect();
                for i in 0..v.len() {
                    self.edges.push((v[i], v[(i + 1) % v.len()]));
                }
            }
        }
    }

    fn read_zone(&mut self, n: &Node, net_of: &dyn Fn(&mut Board, &Node) -> NetId) {
        if n.child("attr").and_then(|a| a.child("teardrop")).is_some() {
            self.teardrop_spans.push(n.span());
            let net = net_of(self, n);
            for f in n.children("filled_polygon") {
                let Some(layer) = f.child("layer").and_then(|l| l.atom(1)).and_then(|l| self.layer_index(l)) else { continue };
                if let Some(p) = f.child("pts") {
                    self.teardrops.push(Teardrop { net, layer, pts: pts_of(p) });
                }
            }
            return;
        }
        let net = net_of(self, n);
        let mut names: Vec<&str> = Vec::new();
        if let Some(l) = n.child("layer") {
            names.extend(l.atoms().into_iter().skip(1));
        }
        if let Some(l) = n.child("layers") {
            names.extend(l.atoms().into_iter().skip(1));
        }
        let layers = self.expand_layers(&names);
        let outline: Vec<V> = n.child("polygon").and_then(|p| p.child("pts")).map(pts_of).unwrap_or_default();
        let mut fills = Vec::new();
        for f in n.children("filled_polygon") {
            let Some(l) = f.child("layer").and_then(|l| l.atom(1)).and_then(|l| self.layer_index(l)) else { continue };
            if let Some(p) = f.child("pts") {
                fills.push((l, pts_of(p)));
            }
        }
        let ko = n.child("keepout");
        let na = |k: &str| ko.and_then(|o| o.child(k)).and_then(|c| c.atom(1)) == Some("not_allowed");
        let priority = n.child("priority").and_then(|p| p.num(1)).unwrap_or(0.0) as i64;
        let name = n.child("name").and_then(|p| p.atom(1)).unwrap_or("").to_string();
        let pads = n.child("connect_pads");
        let clearance = pads.and_then(|c| c.child("clearance")).and_then(|c| c.num(1)).unwrap_or(0.0) * NM;
        let min_thickness = n.child("min_thickness").and_then(|c| c.num(1)).unwrap_or(0.25) * NM;
        let joins_pads = pads.and_then(|c| c.atom(1)) != Some("no");
        let mode = pads.and_then(|c| c.atom(1));
        let fill = n.child("fill");
        let relief = (fill.and_then(|f| f.child("thermal_gap")).and_then(|c| c.num(1)).unwrap_or(0.5) * NM, fill.and_then(|f| f.child("thermal_bridge_width")).and_then(|c| c.num(1)).unwrap_or(0.5) * NM);
        let thermal = if mode.is_none() || mode == Some("thru_hole_only") { Some(relief) } else { None };
        let thermal_tht_only = mode == Some("thru_hole_only");
        self.zones.push(Zone { net, layers, outline, fills, keepout_tracks: na("tracks"), keepout_vias: na("vias"), priority, name, keepout_pour: na("copperpour"), clearance, min_thickness, joins_pads, thermal, thermal_tht_only });
    }

    /// Whether a point lies inside the board outline (holes in the outline count as outside).
    pub fn inside(&self, p: V) -> bool {
        let mut inside = false;
        for (a, b) in &self.edges {
            if (a.1 > p.1) != (b.1 > p.1) && p.0 < (b.0 - a.0) * (p.1 - a.1) / (b.1 - a.1) + a.0 {
                inside = !inside;
            }
        }
        inside
    }

    /// Inner layers given over to a reference plane: a zone of one net covers most of the board.
    /// KiCad's layer type doesn't tell: his benchmark C and benchmark B mark GND planes "signal". Routing
    /// through a plane cuts the return path (2.2, 4.2), so these never take a track.
    pub fn plane_layers(&self) -> Vec<usize> {
        let last = self.layers.len() - 1;
        let board_area = (self.bbox.2 - self.bbox.0).max(0.0) * (self.bbox.3 - self.bbox.1).max(0.0);
        let mut out = Vec::new();
        for l in 1..last {
            // Added up per net: benchmark B's GND plane is two zones, 48% and 13% of the board.
            let mut per_net: HashMap<NetId, f64> = HashMap::new();
            for z in self.zones.iter().filter(|z| z.net != NO_NET && !z.keepout_tracks && z.layers.contains(&l)) {
                let n = z.outline.len();
                let mut a = 0.0;
                for i in 0..n {
                    let (p, q) = (z.outline[i], z.outline[(i + 1) % n]);
                    a += p.0 * q.1 - q.0 * p.1;
                }
                *per_net.entry(z.net).or_insert(0.0) += (a / 2.0).abs();
            }
            let covered = per_net.values().copied().fold(0.0, f64::max);
            if board_area > 0.0 && covered >= 0.5 * board_area {
                out.push(l);
            }
        }
        out
    }

    /// Nets with a copper plane on an inner layer: zone net to its plane layers.
    pub fn plane_nets(&self) -> HashMap<NetId, Vec<usize>> {
        let mut out: HashMap<NetId, Vec<usize>> = HashMap::new();
        let last = self.layers.len() - 1;
        for z in &self.zones {
            if z.net == NO_NET || z.keepout_tracks {
                continue;
            }
            for &l in &z.layers {
                if l != 0 && l != last {
                    out.entry(z.net).or_default().push(l);
                }
            }
        }
        out
    }
}

fn pts_of(p: &Node) -> Vec<V> {
    let mut out = Vec::new();
    for c in p.items() {
        match c.head() {
            "xy" => out.extend(xy(c)),
            "arc" => {
                if let (Some(a), Some(m), Some(b)) = (c.child("start").and_then(xy), c.child("mid").and_then(xy), c.child("end").and_then(xy)) {
                    out.extend(arc_points(a, m, b, 100_000.0));
                }
            }
            _ => {}
        }
    }
    out
}

/// A `(tenting ...)` block on a via or in the setup, or the default when it has none.
fn tent_of(n: &Node, default: (bool, bool)) -> (bool, bool) {
    let Some(t) = n.child("tenting") else { return default };
    let side = |k: &str, d: bool| match t.child(k).and_then(|x| x.atom(1)) {
        Some("yes") => true,
        Some("no") => false,
        _ => d,
    };
    (side("front", default.0), side("back", default.1))
}

pub fn to_p(v: V) -> P {
    (v.0.round() as i64, v.1.round() as i64)
}

fn rect_pts(center: V, w: f64, h: f64, ang: f64, rr: f64) -> Vec<V> {
    let (hw, hh) = (w / 2.0, h / 2.0);
    let mut local: Vec<(f64, f64)> = Vec::new();
    if rr <= 0.0 {
        local.extend([(-hw, -hh), (hw, -hh), (hw, hh), (-hw, hh)]);
    } else {
        // Corner arcs with enough facets that the polygon stays within a micron of the true outline.
        let n = 12;
        for (cx, cy, a0) in [(hw - rr, -hh + rr, -90.0f64), (hw - rr, hh - rr, 0.0), (-hw + rr, hh - rr, 90.0), (-hw + rr, -hh + rr, 180.0)] {
            for i in 0..=n {
                let a = (a0 + 90.0 * i as f64 / n as f64).to_radians();
                local.push((cx + rr * a.cos(), cy + rr * a.sin()));
            }
        }
    }
    local
        .into_iter()
        .map(|(x, y)| {
            let (rx, ry) = rot(x, y, ang);
            V(center.0 + rx, center.1 + ry)
        })
        .collect()
}

#[allow(clippy::too_many_arguments)]
fn pad_shape(name: &str, center: V, size: (f64, f64), ang: f64, rr: f64, delta: Option<(f64, f64)>, p: &Node, kind: &str) -> Shape {
    let (w, h) = size;
    match name {
        "circle" => Shape::Circle { c: center, r: w / 2.0 },
        "oval" => {
            if (w - h).abs() < 1.0 {
                Shape::Circle { c: center, r: w / 2.0 }
            } else if w > h {
                let d = (w - h) / 2.0;
                let (x, y) = rot(d, 0.0, ang);
                Shape::Capsule { a: V(center.0 - x, center.1 - y), b: V(center.0 + x, center.1 + y), r: h / 2.0 }
            } else {
                let d = (h - w) / 2.0;
                let (x, y) = rot(0.0, d, ang);
                Shape::Capsule { a: V(center.0 - x, center.1 - y), b: V(center.0 + x, center.1 + y), r: w / 2.0 }
            }
        }
        "roundrect" => Shape::Poly { pts: rect_pts(center, w, h, ang, rr * w.min(h)), r: 0.0 },
        "trapezoid" => {
            let (dx, dy) = delta.unwrap_or((0.0, 0.0));
            let (hw, hh) = (w / 2.0, h / 2.0);
            let local = [(-hw - dy / 2.0, -hh + dx / 2.0), (hw + dy / 2.0, -hh - dx / 2.0), (hw - dy / 2.0, hh + dx / 2.0), (-hw + dy / 2.0, hh - dx / 2.0)];
            let pts = local.iter().map(|&(x, y)| {
                let (rx, ry) = rot(x, y, ang);
                V(center.0 + rx, center.1 + ry)
            }).collect();
            Shape::Poly { pts, r: 0.0 }
        }
        "custom" => {
            // A custom pad is its anchor plus every primitive, all one piece of copper. KiCad's DRC
            // and connectivity see the union, so all of it is kept, not only the largest piece.
            let anchor_circle = p.child("options").and_then(|o| o.child("anchor")).and_then(|a| a.atom(1)) == Some("circle");
            let mut parts = vec![if anchor_circle { Shape::Circle { c: center, r: w / 2.0 } } else { Shape::Poly { pts: rect_pts(center, w, h, ang, 0.0), r: 0.0 } }];
            let xf = |v: V| {
                let (rx, ry) = rot(v.0, v.1, ang);
                V(center.0 + rx, center.1 + ry)
            };
            if let Some(prims) = p.child("primitives") {
                for g in prims.items() {
                    let half = g.child("width").and_then(|w| w.num(1)).unwrap_or(0.0) * NM / 2.0;
                    let filled = g.child("fill").and_then(|f| f.atom(1)).map(|f| f != "no" && f != "none").unwrap_or(true);
                    match g.head() {
                        "gr_poly" => {
                            if let Some(pp) = g.child("pts") {
                                parts.push(Shape::Poly { pts: pts_of(pp).into_iter().map(xf).collect(), r: half });
                            }
                        }
                        "gr_line" => {
                            if let (Some(a), Some(e)) = (g.child("start").and_then(xy), g.child("end").and_then(xy)) {
                                parts.push(Shape::Capsule { a: xf(a), b: xf(e), r: half });
                            }
                        }
                        "gr_arc" => {
                            if let (Some(a), Some(m), Some(e)) = (g.child("start").and_then(xy), g.child("mid").and_then(xy), g.child("end").and_then(xy)) {
                                for s in arc_points(a, m, e, 50_000.0).windows(2) {
                                    parts.push(Shape::Capsule { a: xf(s[0]), b: xf(s[1]), r: half });
                                }
                            }
                        }
                        "gr_rect" => {
                            if let (Some(a), Some(e)) = (g.child("start").and_then(xy), g.child("end").and_then(xy)) {
                                let pts: Vec<V> = [a, V(e.0, a.1), e, V(a.0, e.1)].into_iter().map(xf).collect();
                                parts.push(Shape::Poly { pts, r: half });
                            }
                        }
                        "gr_circle" => {
                            if let (Some(c), Some(e)) = (g.child("center").and_then(xy), g.child("end").and_then(xy)) {
                                let r = hypot(sub(e, c));
                                if filled {
                                    parts.push(Shape::Circle { c: xf(c), r: r + half });
                                } else {
                                    let ring: Vec<V> = (0..=48).map(|i| {
                                        let a = i as f64 / 48.0 * std::f64::consts::TAU;
                                        V(c.0 + r * a.cos(), c.1 + r * a.sin())
                                    }).collect();
                                    for s in ring.windows(2) {
                                        parts.push(Shape::Capsule { a: xf(s[0]), b: xf(s[1]), r: half });
                                    }
                                }
                            }
                        }
                        _ => {}
                    }
                }
            }
            if parts.len() == 1 { parts.pop().unwrap() } else { Shape::Multi(parts) }
        }
        _ => {
            let _ = kind;
            Shape::Poly { pts: rect_pts(center, w, h, ang, 0.0), r: 0.0 }
        }
    }
}

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

    /// A 100 x 100 board with rectangles on In1.Cu: (net, width, height) of each zone.
    fn with_zones(zones: &[(&str, f64, f64)]) -> Board {
        let mut t = String::from(r#"(kicad_pcb (layers (0 "F.Cu" signal) (4 "In1.Cu" signal) (6 "In2.Cu" signal) (2 "B.Cu" signal)) (gr_rect (start 0 0) (end 100 100) (layer "Edge.Cuts"))"#);
        let mut y0 = 0.0;
        for (net, w, h) in zones {
            t.push_str(&format!(r#"(zone (net "{net}") (layer "In1.Cu") (polygon (pts (xy 0 {y0}) (xy {w} {y0}) (xy {w} {}) (xy 0 {}))))"#, y0 + h, y0 + h));
            y0 += h;
        }
        t.push(')');
        Board::parse(t).unwrap()
    }

    #[test]
    fn a_plane_split_into_two_zones_counts() {
        // Benchmark B's shape: neither zone is half the board, together they are 61%.
        assert_eq!(with_zones(&[("GND", 100.0, 48.0), ("GND", 100.0, 13.0)]).plane_layers(), vec![1]);
        assert_eq!(with_zones(&[("GND", 100.0, 60.0)]).plane_layers(), vec![1]);
    }

    #[test]
    fn zones_of_two_nets_do_not_add_up_to_a_plane() {
        assert!(with_zones(&[("GND", 100.0, 30.0), ("+3V3", 100.0, 30.0)]).plane_layers().is_empty());
        assert!(with_zones(&[("GND", 100.0, 40.0)]).plane_layers().is_empty());
    }
}