AI Flow

//! The board model every stage reads: a KiCad 10 `.kicad_pcb` as footprints, copper pads with
//! their real outlines in board coordinates, nets, the Edge.Cuts outline and the copper layers.
//! Nothing here writes a file; the writers splice into `text` using the spans the reader keeps.
pub mod altium;
pub mod eagle;
pub mod geom;
pub mod netname;
pub mod silk;
pub mod sx;

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

pub use geom::Pt;
pub use sx::{num, quote, Node};

pub const F_CU: usize = 0;
pub const B_CU: usize = 1;
pub const LAYER_NAMES: [&str; 2] = ["F.Cu", "B.Cu"];

/// A copper layer by name for connectivity reads that see every layer: F.Cu 0, B.Cu 1, InN.Cu 1 + N.
/// Outer layers keep F_CU and B_CU, so outer-layer items read the same as before.
pub fn copper_layer(name: &str) -> Option<usize> {
    match name {
        "F.Cu" => Some(F_CU),
        "B.Cu" => Some(B_CU),
        _ => name.strip_prefix("In").and_then(|r| r.strip_suffix(".Cu")).and_then(|n| n.parse::<usize>().ok()).filter(|&n| n >= 1).map(|n| 1 + n),
    }
}

/// How deep a `copper_layer` index sits in the stack, from 0 at F.Cu down to COPPER_BOTTOM at B.Cu.
pub fn copper_depth(layer: usize) -> usize {
    match layer { F_CU => 0, B_CU => COPPER_BOTTOM, k => k - 1 }
}

/// The depth of B.Cu in `copper_depth`.
pub const COPPER_BOTTOM: usize = 1000;

#[derive(Debug, Clone)]
pub struct Pad {
    pub reference: String,
    pub name: String,
    pub key: String,
    pub net: String,
    pub x: f64,
    pub y: f64,
    pub angle: f64,
    pub shape: String,
    pub size: (f64, f64),
    pub drill: Option<f64>,
    pub thru: bool,
    pub on_f: bool,
    pub on_b: bool,
    pub polys: Vec<Vec<Pt>>,
    pub fp_x: f64,
    pub fp_y: f64,
    pub long_axis: Pt,
    pub half_long: f64,
    pub half_short: f64,
    pub uuid: String,
    pub polys_centre: Pt,
    pub clearance: f64,
}

impl Pad {
    pub fn min_dim(&self) -> f64 {
        2.0 * self.half_short
    }
    pub fn on_layer(&self, layer: usize) -> bool {
        if layer == F_CU { self.on_f } else { self.on_b }
    }
    /// Whether the pad has copper on a `copper_layer` index: outer layers as `on_layer`, inner
    /// layers only for a plated through-hole pad.
    pub fn on_copper(&self, layer: usize) -> bool {
        if layer <= B_CU { self.on_layer(layer) } else { self.thru }
    }
}

#[derive(Debug, Clone)]
pub struct Footprint {
    pub reference: String,
    pub x: f64,
    pub y: f64,
    pub rot: f64,
    pub layer: String,
    pub lib: String,
    pub start: usize,
    pub end: usize,
}

/// One straight piece of an existing track (a `segment`, or a piece of an `arc`).
#[derive(Debug, Clone)]
pub struct Track {
    pub net: String,
    pub layer: usize,
    pub a: Pt,
    pub b: Pt,
    pub width: f64,
}

#[derive(Debug, Clone)]
pub struct Via {
    pub net: String,
    pub x: f64,
    pub y: f64,
    pub size: f64,
    pub drill: f64,
    /// The copper depths it spans (`copper_depth`): 0..=COPPER_BOTTOM for a through via, less for
    /// a blind or buried one.
    pub span: (usize, usize),
}

impl Via {
    /// Whether the via has copper on a `copper_layer` index.
    pub fn on_copper(&self, layer: usize) -> bool {
        let d = copper_depth(layer);
        self.span.0 <= d && d <= self.span.1
    }
}

/// A copper zone: its outline and its filled islands per layer (empty when never filled).
#[derive(Debug, Clone)]
pub struct Zone {
    pub net: String,
    pub layers: Vec<usize>,
    pub outline: Vec<Pt>,
    pub fills: Vec<(usize, Vec<Pt>)>,
}

/// A drilled hole with no copper layer at all (an NPTH whose pad lists only `*.Mask`, such as a
/// USB-C shell peg). It is not a pad: it has no net and no copper, so pad, net, BOM and netlist
/// consumers never see it. Copper consumers (router, pours, via placement) keep clearance from it.
#[derive(Debug, Clone)]
pub struct DrillHole {
    pub reference: String,
    pub name: String,
    pub x: f64,
    pub y: f64,
    /// the hole's extent (width, height) before rotation; equal for a round hole
    pub size: (f64, f64),
    pub angle: f64,
    pub plated: bool,
    /// the hole's outline in board coordinates
    pub poly: Vec<Pt>,
    pub uuid: String,
}

impl DrillHole {
    /// The largest dimension: a round hole's diameter, an oval's length (conservative for clearance).
    pub fn diameter(&self) -> f64 {
        self.size.0.max(self.size.1)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NetFormat {
    Number,
    Name,
}

pub struct Board {
    pub path: String,
    pub text: String,
    pub root: Node,
    pub net_table: BTreeMap<i64, String>,
    pub net_format: NetFormat,
    pub pads: Vec<Pad>,
    pub footprints: BTreeMap<String, Footprint>,
    /// The board outline: the outermost closed Edge.Cuts loop.
    pub outline: Vec<Pt>,
    /// Closed Edge.Cuts loops inside the outline (a bore, a slot, a cutout): holes in the board.
    pub outline_cutouts: Vec<Vec<Pt>>,
    pub bbox: (f64, f64, f64, f64),
    pub nets: BTreeMap<String, Vec<usize>>,
    pub copper_layers: Vec<String>,
    /// drilled holes with no copper (see `DrillHole`); never in `pads` or `nets`
    pub holes: Vec<DrillHole>,
    pad_index: HashMap<String, usize>,
}

fn pad_local_polys(pn: &Node, shape: &str, sx: f64, sy: f64) -> Vec<Vec<Pt>> {
    let rectp = |sx: f64, sy: f64| vec![(-sx / 2.0, -sy / 2.0), (sx / 2.0, -sy / 2.0), (sx / 2.0, sy / 2.0), (-sx / 2.0, sy / 2.0)];
    let mut polys = Vec::new();
    match shape {
        "rect" | "roundrect" | "trapezoid" | "chamfer" => polys.push(rectp(sx, sy)),
        "oval" => polys.push(geom::stadium_poly(sx, sy, 10)),
        "circle" => polys.push(geom::circle_poly(0.0, 0.0, sx / 2.0, 32)),
        "custom" => {
            let anchor = pn.find("options").and_then(|o| o.find("anchor")).and_then(|a| a.value()).unwrap_or("rect");
            if anchor == "circle" {
                polys.push(geom::circle_poly(0.0, 0.0, sx / 2.0, 32));
            } else {
                polys.push(rectp(sx, sy));
            }
            if let Some(prims) = pn.find("primitives") {
                for prim in prims.nodes() {
                    match prim.tag.as_str() {
                        "gr_poly" => {
                            if let Some(pts) = prim.find("pts") {
                                let mut poly: Vec<Pt> = pts.find_all("xy").filter_map(|xy| Some((xy.number(1)?, xy.number(2)?))).collect();
                                let w = prim.find("width").and_then(|w| w.number(1)).unwrap_or(0.0);
                                if w > 0.0 {
                                    poly = geom::grow_poly(&poly, w / 2.0);
                                }
                                if poly.len() >= 3 {
                                    polys.push(poly);
                                }
                            }
                        }
                        "gr_rect" => {
                            if let (Some(s), Some(e)) = (prim.find("start"), prim.find("end")) {
                                if let (Some(x0), Some(y0), Some(x1), Some(y1)) = (s.number(1), s.number(2), e.number(1), e.number(2)) {
                                    polys.push(vec![(x0, y0), (x1, y0), (x1, y1), (x0, y1)]);
                                }
                            }
                        }
                        "gr_circle" => {
                            if let (Some(c), Some(e)) = (prim.find("center"), prim.find("end")) {
                                if let (Some(cx), Some(cy), Some(ex), Some(ey)) = (c.number(1), c.number(2), e.number(1), e.number(2)) {
                                    let r = (ex - cx).hypot(ey - cy) + prim.find("width").and_then(|w| w.number(1)).unwrap_or(0.0) / 2.0;
                                    polys.push(geom::circle_poly(cx, cy, r, 32));
                                }
                            }
                        }
                        "gr_line" => {
                            if let (Some(s), Some(e)) = (prim.find("start"), prim.find("end")) {
                                let hw = prim.find("width").and_then(|w| w.number(1)).unwrap_or(0.1) / 2.0;
                                if let (Some(x0), Some(y0), Some(x1), Some(y1)) = (s.number(1), s.number(2), e.number(1), e.number(2)) {
                                    polys.push(geom::thick_line_poly((x0, y0), (x1, y1), hw));
                                }
                            }
                        }
                        _ => {}
                    }
                }
            }
        }
        _ => polys.push(rectp(sx, sy)),
    }
    polys
}

/// The hole of a pad with no copper layer, when it has a drill (`(drill d)` or `(drill oval w h)`,
/// optionally with an `(offset x y)`), in board coordinates.
fn drill_hole(pn: &Node, reference: &str, name: &str, ptype: &str, fx: f64, fy: f64, rot: f64) -> Option<DrillHole> {
    if ptype != "np_thru_hole" && ptype != "thru_hole" {
        return None;
    }
    let d = pn.find("drill")?;
    let (w, h) = if d.atom(1) == Some("oval") {
        let w = d.number(2)?;
        (w, d.number(3).unwrap_or(w))
    } else {
        let w = d.number(1)?;
        (w, d.number(2).unwrap_or(w))
    };
    if !(w > 0.0 && h > 0.0 && w.is_finite() && h.is_finite()) {
        return None;
    }
    let (ox, oy) = d.find("offset").map(|o| (o.number(1).unwrap_or(0.0), o.number(2).unwrap_or(0.0))).unwrap_or((0.0, 0.0));
    let pat = pn.find("at");
    let px = pat.and_then(|a| a.number(1)).unwrap_or(0.0);
    let py = pat.and_then(|a| a.number(2)).unwrap_or(0.0);
    // a pad's angle in a .kicad_pcb is absolute (it already holds the footprint's rotation); KiCad
    // leaves it out when that absolute angle is 0, even in a rotated footprint (issue #103)
    let pang = pat.and_then(|a| a.number(3)).unwrap_or(0.0);
    let (rx, ry) = geom::rot_kicad(px, py, rot);
    let (x, y) = (fx + rx, fy + ry);
    let local = if (w - h).abs() < 1e-9 { geom::circle_poly(ox, oy, w / 2.0, 32) } else { geom::stadium_poly(w, h, 10).into_iter().map(|(a, b)| (a + ox, b + oy)).collect() };
    let poly: Vec<Pt> = local.iter().map(|&(a, b)| { let (qx, qy) = geom::rot_kicad(a, b, pang); (x + qx, y + qy) }).collect();
    let (ux, uy) = geom::rot_kicad(ox, oy, pang);
    Some(DrillHole {
        reference: reference.to_string(), name: name.to_string(), x: x + ux, y: y + uy, size: (w, h), angle: pang,
        plated: ptype == "thru_hole", poly, uuid: pn.find("uuid").and_then(|u| u.value()).unwrap_or("").to_string(),
    })
}

pub fn reference_of(fp: &Node) -> Option<String> {
    for p in fp.find_all("property") {
        if p.atom(1) == Some("Reference") {
            return p.atom(2).map(str::to_string);
        }
    }
    fp.find("fp_text").filter(|t| t.atom(1) == Some("reference")).and_then(|t| t.atom(2)).map(str::to_string)
}

impl Board {
    pub fn load(path: &str) -> Result<Board, String> {
        let text = std::fs::read_to_string(path).map_err(|e| format!("{path}: {e}"))?;
        // a Fusion board (EAGLE source): plan on its .kicad_pcb rendering (see eagle.rs)
        if eagle::is_eagle(&text) { return Board::from_text(path, eagle::to_kicad(&text)?); }
        // an Altium board read (the Altium bridge's JSON): plan on its .kicad_pcb rendering (see altium.rs)
        if altium::is_altium(&text) { return Board::from_text(path, altium::render_plan_board(&text)?); }
        Board::from_text(path, text)
    }

    pub fn from_text(path: &str, text: String) -> Result<Board, String> {
        let root = sx::parse(&text)?;
        if root.tag != "kicad_pcb" {
            return Err(format!("{path} is not a kicad_pcb"));
        }
        let mut net_table = BTreeMap::new();
        for n in root.find_all("net") {
            if let (Some(k), Some(name)) = (n.atom(1).and_then(|a| a.parse::<i64>().ok()), n.atom(2)) {
                net_table.insert(k, name.to_string());
            }
        }
        let net_format = if net_table.is_empty() { NetFormat::Name } else { NetFormat::Number };
        let mut b = Board { path: path.to_string(), text: String::new(), root, net_table, net_format, pads: Vec::new(), footprints: BTreeMap::new(), outline: Vec::new(), outline_cutouts: Vec::new(), bbox: (0.0, 0.0, 0.0, 0.0), nets: BTreeMap::new(), copper_layers: Vec::new(), holes: Vec::new(), pad_index: HashMap::new() };
        b.read_footprints();
        (b.outline, b.outline_cutouts) = b.read_outline()?;
        b.bbox = geom::bbox(&b.outline);
        for (i, p) in b.pads.iter().enumerate() {
            if !p.net.is_empty() {
                b.nets.entry(p.net.clone()).or_default().push(i);
            }
            b.pad_index.insert(p.key.clone(), i);
        }
        if let Some(layers) = b.root.find("layers") {
            for l in layers.nodes() {
                let kind = l.atom(2).unwrap_or("");
                if matches!(kind, "signal" | "power" | "mixed") {
                    if let Some(name) = l.atom(1) {
                        b.copper_layers.push(name.to_string());
                    }
                }
            }
        }
        b.text = text;
        Ok(b)
    }

    fn read_footprints(&mut self) {
        let root = self.root.clone();
        for fp in root.find_all("footprint") {
            let Some(reference) = reference_of(fp) else { continue };
            let at = fp.find("at");
            let fx = at.and_then(|a| a.number(1)).unwrap_or(0.0);
            let fy = at.and_then(|a| a.number(2)).unwrap_or(0.0);
            let rot = at.and_then(|a| a.number(3)).unwrap_or(0.0);
            let layer = fp.find("layer").and_then(|l| l.value()).unwrap_or("F.Cu").to_string();
            let fp_clearance = fp.find("clearance").and_then(|c| c.number(1)).unwrap_or(0.0);
            self.footprints.insert(reference.clone(), Footprint { reference: reference.clone(), x: fx, y: fy, rot, layer, lib: fp.value().unwrap_or("").to_string(), start: fp.start, end: fp.end });
            for pn in fp.find_all("pad") {
                let name = pn.value().unwrap_or("").to_string();
                let ptype = pn.atom(2).unwrap_or("");
                let shape = pn.atom(3).unwrap_or("rect").to_string();
                let mut on_f = false;
                let mut on_b = false;
                let mut copper = false;
                if let Some(ln) = pn.find("layers") {
                    for l in ln.items.iter().filter_map(|it| if let sx::Item::Atom { text, .. } = it { Some(text.as_str()) } else { None }) {
                        if l == "*.Cu" {
                            on_f = true; on_b = true; copper = true;
                        } else if l.ends_with(".Cu") {
                            copper = true;
                            if l == "F.Cu" { on_f = true; }
                            if l == "B.Cu" { on_b = true; }
                        }
                    }
                }
                if !copper {
                    // a drilled hole with no copper (an NPTH with only mask layers): an obstacle, not a pad
                    if let Some(h) = drill_hole(pn, &reference, &name, ptype, fx, fy, rot) {
                        self.holes.push(h);
                    }
                    continue;
                }
                let pat = pn.find("at");
                let px = pat.and_then(|a| a.number(1)).unwrap_or(0.0);
                let py = pat.and_then(|a| a.number(2)).unwrap_or(0.0);
                // absolute, and 0 when left out (see drill_hole; issue #103)
                let pang = pat.and_then(|a| a.number(3)).unwrap_or(0.0);
                let size = pn.find("size");
                let sx_ = size.and_then(|s| s.number(1)).unwrap_or(0.0);
                let sy_ = size.and_then(|s| s.number(2)).unwrap_or(0.0);
                let drill = pn.find("drill").and_then(|d| d.number(1));
                let mut net = pn.find("net").and_then(|n| n.value()).unwrap_or("").to_string();
                if self.net_format == NetFormat::Number {
                    if let Some(k) = pn.find("net").and_then(|n| n.atom(1)).and_then(|a| a.parse::<i64>().ok()) {
                        if let Some(nm) = self.net_table.get(&k) {
                            net = nm.clone();
                        }
                    }
                }
                let (ox, oy) = geom::rot_kicad(px, py, rot);
                let (x, y) = (fx + ox, fy + oy);
                let thru = ptype == "thru_hole" || ptype == "np_thru_hole";
                let pclr = pn.find("clearance").and_then(|c| c.number(1)).unwrap_or(0.0);
                let local = pad_local_polys(pn, &shape, sx_, sy_);
                let (x0, y0, x1, y1) = geom::bbox(&local.iter().flatten().copied().collect::<Vec<_>>());
                let (lx, ly) = ((x1 - x0) / 2.0, (y1 - y0) / 2.0);
                let (lcx, lcy) = ((x0 + x1) / 2.0, (y0 + y1) / 2.0);
                let (half_long, half_short, axis) = if lx >= ly { (lx, ly, geom::rot_kicad(1.0, 0.0, pang)) } else { (ly, lx, geom::rot_kicad(0.0, 1.0, pang)) };
                let polys: Vec<Vec<Pt>> = local.iter().map(|poly| poly.iter().map(|&(a, b)| { let (rx, ry) = geom::rot_kicad(a, b, pang); (x + rx, y + ry) }).collect()).collect();
                let (ccx, ccy) = geom::rot_kicad(lcx, lcy, pang);
                // Unnumbered copper-layer pads, including NPTH mounting holes,
                // are physical obstacles rather than electrical terminals.
                let key = if name.is_empty() {
                    format!("{reference}.__physical_{}", self.pads.len())
                } else {
                    format!("{reference}.{name}")
                };
                self.pads.push(Pad {
                    key, reference: reference.clone(), name, net, x, y, angle: pang, shape, size: (sx_, sy_), drill, thru,
                    on_f: on_f && (thru || true) && on_f, on_b: on_b || thru, polys, fp_x: fx, fp_y: fy, long_axis: axis, half_long, half_short,
                    uuid: pn.find("uuid").and_then(|u| u.value()).unwrap_or("").to_string(), polys_centre: (x + ccx, y + ccy), clearance: fp_clearance.max(pclr),
                });
            }
        }
    }

    /// The outermost closed Edge.Cuts loop and the closed loops inside it (issue #77: a bore drawn as a
    /// gr_circle used to be taken as the whole outline).
    fn read_outline(&self) -> Result<(Vec<Pt>, Vec<Vec<Pt>>), String> {
        let mut pieces: Vec<Vec<Pt>> = Vec::new();
        let mut loops: Vec<Vec<Pt>> = Vec::new();
        for node in self.root.nodes() {
            if !node.tag.starts_with("gr_") {
                continue;
            }
            if node.find("layer").and_then(|l| l.value()) != Some("Edge.Cuts") {
                continue;
            }
            let p2 = |n: Option<&Node>| -> Option<Pt> { let n = n?; Some((n.number(1)?, n.number(2)?)) };
            match node.tag.as_str() {
                "gr_line" => {
                    if let (Some(s), Some(e)) = (p2(node.find("start")), p2(node.find("end"))) {
                        pieces.push(vec![s, e]);
                    }
                }
                "gr_arc" => {
                    if let (Some(s), Some(m), Some(e)) = (p2(node.find("start")), p2(node.find("mid")), p2(node.find("end"))) {
                        pieces.push(geom::arc_points(s, m, e, 0.35));
                    }
                }
                "gr_rect" => {
                    if let (Some(s), Some(e)) = (p2(node.find("start")), p2(node.find("end"))) {
                        loops.push(vec![s, (e.0, s.1), e, (s.0, e.1)]);
                    }
                }
                "gr_circle" => {
                    if let (Some(c), Some(e)) = (p2(node.find("center")), p2(node.find("end"))) {
                        loops.push(geom::circle_poly(c.0, c.1, (e.0 - c.0).hypot(e.1 - c.1), 64));
                    }
                }
                "gr_poly" => {
                    if let Some(pts) = node.find("pts") {
                        let poly: Vec<Pt> = pts.find_all("xy").filter_map(|xy| Some((xy.number(1)?, xy.number(2)?))).collect();
                        if poly.len() >= 3 { loops.push(poly); }
                    }
                }
                _ => {}
            }
        }
        loops.extend(geom::chain_loops(pieces, 0.01)?);
        if loops.is_empty() {
            return Err("no Edge.Cuts outline".into());
        }
        // the outline is the loop with the largest area; every other closed loop is a cutout
        let outer = (0..loops.len()).max_by(|&a, &b| geom::polygon_area(&loops[a]).abs().total_cmp(&geom::polygon_area(&loops[b]).abs())).unwrap();
        let outline = loops.remove(outer);
        Ok((outline, loops))
    }

    /// The `(net ...)` line for copper on this board (matches the bridge's net_sexpr).
    pub fn net_ref_sexpr(&self, net: &str) -> Result<String, String> {
        match self.net_format {
            NetFormat::Number => {
                let n = self.net_table.iter().find(|(_, v)| v.as_str() == net).map(|(k, _)| *k).ok_or_else(|| format!("net {net:?} is not in the net table"))?;
                Ok(format!("\t\t(net {n})\n"))
            }
            NetFormat::Name => Ok(format!("\t\t(net {})\n", quote(net))),
        }
    }

    pub fn pad_by_key(&self, key: &str) -> Option<&Pad> {
        self.pad_index.get(key).map(|&i| &self.pads[i])
    }

    pub fn pad_idx(&self, key: &str) -> Option<usize> {
        self.pad_index.get(key).copied()
    }

    /// Every pad a key names. A footprint may number two pads alike (a connector's two `MP` mounting
    /// pads): such a key is ambiguous, and `pad_by_key` gives only one of them (issue #93).
    pub fn pads_with_key(&self, key: &str) -> Vec<&Pad> {
        self.pads.iter().filter(|p| p.key == key).collect()
    }

    /// Whether more than one pad answers to `key`.
    pub fn key_is_ambiguous(&self, key: &str) -> bool {
        self.pads.iter().filter(|p| p.key == key).nth(1).is_some()
    }

    pub fn pads_of(&self, reference: &str) -> Vec<&Pad> {
        self.pads.iter().filter(|p| p.reference == reference).collect()
    }

    /// The net name of a board item's `(net ...)`: a number through the net table, or the name itself.
    pub fn item_net(&self, n: &Node) -> String {
        let Some(x) = n.find("net") else { return String::new() };
        if self.net_format == NetFormat::Number {
            if let Some(k) = x.atom(1).and_then(|a| a.parse::<i64>().ok()) {
                return self.net_table.get(&k).cloned().unwrap_or_default();
            }
        }
        x.atom(1).unwrap_or("").to_string()
    }

    /// The copper tracks already on the board: every `segment`, and every `arc` as short straight
    /// pieces, on F.Cu or B.Cu.
    pub fn tracks(&self) -> Vec<Track> {
        self.tracks_on(false)
    }

    /// Every copper track on every copper layer, for connectivity: `layer` is a `copper_layer`
    /// index (F.Cu 0, B.Cu 1, InN.Cu 1 + N).
    pub fn copper_tracks(&self) -> Vec<Track> {
        self.tracks_on(true)
    }

    fn tracks_on(&self, inner: bool) -> Vec<Track> {
        let mut out = Vec::new();
        let p2 = |n: Option<&Node>| -> Option<Pt> { let n = n?; Some((n.number(1)?, n.number(2)?)) };
        for node in self.root.nodes() {
            if node.tag != "segment" && node.tag != "arc" {
                continue;
            }
            let Some(layer) = node.find("layer").and_then(|l| l.value()).and_then(copper_layer).filter(|&l| inner || l <= B_CU) else { continue };
            let width = node.find("width").and_then(|w| w.number(1)).unwrap_or(0.0);
            let net = self.item_net(node);
            let (Some(s), Some(e)) = (p2(node.find("start")), p2(node.find("end"))) else { continue };
            let pts = match (node.tag.as_str(), p2(node.find("mid"))) { ("arc", Some(m)) => geom::arc_points(s, m, e, 0.1), _ => vec![s, e] };
            for w in pts.windows(2) {
                out.push(Track { net: net.clone(), layer, a: w[0], b: w[1], width });
            }
        }
        out
    }

    /// The vias already on the board (through vias: both outer layers).
    pub fn vias(&self) -> Vec<Via> {
        let mut out = Vec::new();
        for v in self.root.find_all("via") {
            let at = v.find("at");
            let (Some(x), Some(y)) = (at.and_then(|a| a.number(1)), at.and_then(|a| a.number(2))) else { continue };
            let size = v.find("size").and_then(|s| s.number(1)).unwrap_or(0.6);
            let drill = v.find("drill").and_then(|d| d.number(1)).unwrap_or(0.3);
            // a blind or buried via names its two end layers; a through via spans the whole stack
            let ends: Vec<usize> = v.find("layers").map(|ls| ls.items.iter().filter_map(|it| if let sx::Item::Atom { text, .. } = it { copper_layer(text) } else { None }).map(copper_depth).collect()).unwrap_or_default();
            let span = match (ends.iter().min(), ends.iter().max()) { (Some(&a), Some(&b)) if a < b => (a, b), _ => (0, COPPER_BOTTOM) };
            out.push(Via { net: self.item_net(v), x, y, size, drill, span });
        }
        out
    }

    /// Copper zones with their net, layers, outline and filled islands (one polygon per island).
    pub fn zones(&self) -> Vec<Zone> {
        self.zones_on(false)
    }

    /// Every filled zone island on every copper layer, for connectivity: (net, `copper_layer`
    /// index, island polygon).
    pub fn copper_fills(&self) -> Vec<(String, usize, Vec<Pt>)> {
        self.zones_on(true).into_iter().flat_map(|z| { let net = z.net; z.fills.into_iter().map(move |(l, p)| (net.clone(), l, p)) }).collect()
    }

    fn zones_on(&self, inner: bool) -> Vec<Zone> {
        let mut out = Vec::new();
        let pts_of = |n: &Node| -> Vec<Pt> { n.find("pts").map(|p| p.find_all("xy").filter_map(|xy| Some((xy.number(1)?, xy.number(2)?))).collect()).unwrap_or_default() };
        for z in self.root.find_all("zone") {
            if z.find("keepout").is_some() {
                continue;
            }
            let mut layers = Vec::new();
            let mut names: Vec<String> = Vec::new();
            if let Some(l) = z.find("layer").and_then(|l| l.value()) { names.push(l.to_string()); }
            if let Some(ls) = z.find("layers") {
                names.extend(ls.items.iter().filter_map(|it| if let sx::Item::Atom { text, .. } = it { Some(text.clone()) } else { None }).filter(|t| t != "layers"));
            }
            for n in &names {
                for (k, l) in LAYER_NAMES.iter().enumerate() {
                    if (n == l || n == "*.Cu" || n == "F&B.Cu") && !layers.contains(&k) { layers.push(k); }
                }
            }
            let outline = z.find("polygon").map(pts_of).unwrap_or_default();
            let mut fills = Vec::new();
            for f in z.find_all("filled_polygon") {
                let Some(layer) = f.find("layer").and_then(|l| l.value()).and_then(copper_layer).filter(|&l| inner || l <= B_CU) else { continue };
                let poly = pts_of(f);
                if poly.len() >= 3 { fills.push((layer, poly)); }
            }
            out.push(Zone { net: self.item_net(z), layers, outline, fills });
        }
        out
    }

    /// Pad-box (copper extent) of every pad of a footprint: (x0, y0, x1, y1).
    pub fn pad_box(&self, reference: &str) -> Option<(f64, f64, f64, f64)> {
        let pts: Vec<Pt> = self.pads.iter().filter(|p| p.reference == reference).flat_map(|p| p.polys.iter().flatten().copied()).collect();
        if pts.is_empty() { None } else { Some(geom::bbox(&pts)) }
    }

    /// Issue #139: the layer a plan path with no layer of its own starts on. A path's first layer is the
    /// entry's `layer` or its first waypoint's; when it names neither, the pads before its first layer
    /// marker say it: the first single-sided pad among them decides (a bottom part's pad is on B.Cu only),
    /// else F.Cu. `wps` is each waypoint's pad (None for a point) and whether it carries a layer.
    pub fn path_start_layer<'a>(wps: impl IntoIterator<Item = (Option<&'a Pad>, bool)>) -> &'static str {
        for (pad, explicit) in wps {
            if explicit { break; }
            if let Some(p) = pad {
                if p.thru || (p.on_f && p.on_b) { continue; }
                return if p.on_f { "F.Cu" } else if p.on_b { "B.Cu" } else { continue };
            }
        }
        "F.Cu"
    }

    /// A point outside the board: outside the Edge.Cuts outline (when there is one) or inside a cutout.
    pub fn point_outside(&self, x: f64, y: f64) -> bool {
        (self.outline.len() >= 3 && !geom::point_in_poly(x, y, &self.outline)) || self.outline_cutouts.iter().any(|c| geom::point_in_poly(x, y, c))
    }

    /// Issue #140: the footprints with copper pads that are wholly off the board, every pad centre outside
    /// the outline (a part `place pack` found no spot for and left where it was parked). A part that only
    /// overhangs the edge (an edge connector) keeps a pad inside and is not listed.
    pub fn parts_outside(&self) -> Vec<String> {
        if self.outline.len() < 3 { return Vec::new(); }
        self.footprints.keys().filter(|r| {
            let mut pads = self.pads.iter().filter(|p| &p.reference == *r).peekable();
            pads.peek().is_some() && pads.all(|p| self.point_outside(p.x, p.y))
        }).cloned().collect()
    }
}

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

    #[test]
    fn a_pad_angle_is_absolute_and_zero_when_left_out() {
        // KiCad writes a pad's absolute angle and omits it at 0, even in a footprint turned 90 degrees
        // (issue #103): pad 1 lies along x on the board, pad 2 (written at 90) along y
        let t = r#"(kicad_pcb (layers (0 "F.Cu" signal) (2 "B.Cu" signal) (25 "Edge.Cuts" user))
  (footprint "X" (layer "F.Cu") (at 10 10 90) (property "Reference" "X1")
    (pad "1" smd rect (at 0 0) (size 2 0.4) (layers "F.Cu") (net "A"))
    (pad "2" smd rect (at 0 3 90) (size 2 0.4) (layers "F.Cu") (net "A")))
  (gr_rect (start 0 0) (end 20 20) (layer "Edge.Cuts")))"#;
        let b = Board::from_text("t.kicad_pcb", t.to_string()).unwrap();
        let ext = |k: &str| { let bb = geom::bbox(&b.pad_by_key(k).unwrap().polys[0]); ((bb.2 - bb.0).abs(), (bb.3 - bb.1).abs()) };
        let (w1, h1) = ext("X1.1");
        assert!((w1 - 2.0).abs() < 1e-6 && (h1 - 0.4).abs() < 1e-6, "{w1} x {h1}");
        let (w2, h2) = ext("X1.2");
        assert!((w2 - 0.4).abs() < 1e-6 && (h2 - 2.0).abs() < 1e-6, "{w2} x {h2}");
    }

    #[test]
    fn copper_layers_read_inner_tracks_fills_and_via_spans() {
        assert_eq!((copper_layer("F.Cu"), copper_layer("B.Cu"), copper_layer("In1.Cu"), copper_layer("In30.Cu"), copper_layer("F.SilkS")), (Some(0), Some(1), Some(2), Some(31), None));
        let t = r#"(kicad_pcb (layers (0 "F.Cu" signal) (4 "In1.Cu" signal) (6 "In2.Cu" signal) (2 "B.Cu" signal) (25 "Edge.Cuts" user))
  (segment (start 0 0) (end 1 0) (width 0.2) (layer "In2.Cu") (net "A"))
  (segment (start 0 0) (end 1 0) (width 0.2) (layer "F.Cu") (net "A"))
  (via (at 1 1) (size 0.6) (drill 0.3) (layers "F.Cu" "B.Cu") (net "A"))
  (via blind (at 2 2) (size 0.6) (drill 0.3) (layers "F.Cu" "In1.Cu") (net "A"))
  (gr_rect (start 0 0) (end 20 20) (layer "Edge.Cuts")))"#;
        let b = Board::from_text("t.kicad_pcb", t.to_string()).unwrap();
        assert_eq!(b.tracks().len(), 1, "the router's two layers only");
        assert_eq!(b.copper_tracks().iter().map(|t| t.layer).collect::<Vec<_>>(), vec![3, 0]);
        let v = b.vias();
        assert!(v[0].on_copper(3) && v[0].on_copper(B_CU));
        assert!(v[1].on_copper(F_CU) && v[1].on_copper(2) && !v[1].on_copper(3) && !v[1].on_copper(B_CU));
    }
}