AI Flow

//! Placement helpers: courtyard boxes from the file, a legal spot for a part near where it should
//! be, moving footprints in the file, and the overlap check.
//!
//! The AI decides where parts go; these are the mechanics that keep a decision legal before it
//! reaches the live board (the bridge's `kicad_move_footprint` checks courtyards exactly when it lands).
pub mod intent;

use std::collections::BTreeMap;

use aiflow_board::{geom, num, Board, Pt};
use serde::{Deserialize, Serialize};
use serde_json::Value;

#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct Move {
    pub x: f64,
    pub y: f64,
    #[serde(default)]
    pub rotation: Option<f64>,
}

#[derive(Clone, Debug, Deserialize)]
pub struct Wish {
    pub x: f64,
    pub y: f64,
    #[serde(default = "default_rot")]
    pub rot: Vec<f64>,
    #[serde(default = "default_radius")]
    pub radius: f64,
    #[serde(default)]
    pub keepout: Vec<(f64, f64, f64, f64, f64)>,
    #[serde(default)]
    pub gap: Option<f64>,
}

fn default_rot() -> Vec<f64> { vec![0.0] }
fn default_radius() -> f64 { 4.0 }

type Box4 = (f64, f64, f64, f64);

/// Local (unrotated, anchor-relative) F.CrtYd or B.CrtYd points of a footprint, from the file text.
pub fn courtyard_local(board: &Board, reference: &str) -> Option<Vec<Pt>> {
    let fp = board.footprints.get(reference)?;
    let block = &board.text[fp.start..fp.end];
    let node = aiflow_board::sx::parse(block).ok()?;
    let mut pts = Vec::new();
    for n in node.nodes() {
        if !matches!(n.tag.as_str(), "fp_line" | "fp_rect" | "fp_poly" | "fp_circle" | "fp_arc") {
            continue;
        }
        let layer = n.find("layer").and_then(|l| l.value()).unwrap_or("");
        if layer != "F.CrtYd" && layer != "B.CrtYd" {
            continue;
        }
        for tag in ["start", "end", "mid", "center"] {
            if let Some(p) = n.find(tag) {
                if let (Some(x), Some(y)) = (p.number(1), p.number(2)) {
                    pts.push((x, y));
                }
            }
        }
        if let Some(p) = n.find("pts") {
            for xy in p.find_all("xy") {
                if let (Some(x), Some(y)) = (xy.number(1), xy.number(2)) {
                    pts.push((x, y));
                }
            }
        }
        if n.tag == "fp_circle" {
            if let (Some(c), Some(e)) = (n.find("center"), n.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);
                    pts.push((cx - r, cy - r));
                    pts.push((cx + r, cy + r));
                }
            }
        }
    }
    if pts.is_empty() { None } else { Some(pts) }
}

pub fn placed_box(pts: &[Pt], x: f64, y: f64, rot: f64) -> Box4 {
    let placed: Vec<Pt> = pts.iter().map(|&(dx, dy)| { let (a, b) = geom::rot_kicad(dx, dy, rot); (x + a, y + b) }).collect();
    geom::bbox(&placed)
}

/// The courtyard box (pad box grown by 0.25 mm when a part has no courtyard) of every footprint.
pub fn boxes(board: &Board) -> BTreeMap<String, Box4> {
    let mut out = BTreeMap::new();
    for (r, fp) in &board.footprints {
        if let Some(pts) = courtyard_local(board, r) {
            out.insert(r.clone(), placed_box(&pts, fp.x, fp.y, fp.rot));
        } else if let Some(b) = board.pad_box(r) {
            out.insert(r.clone(), (b.0 - 0.25, b.1 - 0.25, b.2 + 0.25, b.3 + 0.25));
        }
    }
    out
}

fn clear(b: &Box4, others: &[Box4], gap: f64) -> bool {
    !others.iter().any(|o| b.0 - gap < o.2 && o.0 - gap < b.2 && b.1 - gap < o.3 && o.1 - gap < b.3)
}

/// The sides a part occupies (issue #179): (top, bottom). An SMD part on F.Cu is top only, one on B.Cu
/// bottom only (KiCad checks F.CrtYd and B.CrtYd separately); a part with a drilled pad or hole is on both.
pub fn sides(board: &Board, reference: &str) -> (bool, bool) {
    let drilled = board.pads.iter().any(|p| p.reference == reference && (p.thru || p.drill.is_some())) || board.holes.iter().any(|h| h.reference == reference);
    if drilled { return (true, true); }
    let bottom = board.footprints.get(reference).is_some_and(|f| f.layer == "B.Cu");
    (!bottom, bottom)
}

fn share_side(a: (bool, bool), b: (bool, bool)) -> bool {
    (a.0 && b.0) || (a.1 && b.1)
}

/// The copper of every drilled pad and the outline of every bare hole, grown by 0.25 mm: on both sides,
/// and it can stick out past its part's courtyard (a USB-C shell tab). Parts in `skip` are left out.
fn drilled_boxes(board: &Board, skip: &[&str]) -> Vec<Box4> {
    let grow = |b: Box4| (b.0 - 0.25, b.1 - 0.25, b.2 + 0.25, b.3 + 0.25);
    let pads = board.pads.iter().filter(|p| (p.thru || p.drill.is_some()) && !p.polys.iter().all(|q| q.is_empty()) && !skip.contains(&p.reference.as_str())).map(|p| grow(geom::bbox(&p.polys.iter().flatten().copied().collect::<Vec<_>>())));
    let holes = board.holes.iter().filter(|h| !skip.contains(&h.reference.as_str()) && !h.poly.is_empty()).map(|h| grow(geom::bbox(&h.poly)));
    pads.chain(holes).collect()
}

/// Local outline points of a part for placement: its courtyard, else its pad box grown by 0.25.
fn local_pts(board: &Board, reference: &str) -> Vec<Pt> {
    if let Some(p) = courtyard_local(board, reference) {
        return p;
    }
    let fp = &board.footprints[reference];
    let pts: Vec<Pt> = board.pads.iter().filter(|p| p.reference == reference).flat_map(|p| p.polys.iter().flatten().copied()).map(|(x, y)| geom::rot_kicad(x - fp.x, y - fp.y, -(fp.rot))).collect();
    let (x0, y0, x1, y1) = geom::bbox(&pts);
    vec![(x0 - 0.25, y0 - 0.25), (x1 + 0.25, y1 + 0.25)]
}

/// Pads of a part in its own frame (unrotated, anchor-relative), with their nets.
fn local_pads(board: &Board, reference: &str) -> Vec<(String, String, Pt)> {
    let Some(fp) = board.footprints.get(reference) else { return Vec::new() };
    board.pads.iter().filter(|p| p.reference == reference).map(|p| (p.name.clone(), p.net.clone(), geom::rot_kicad(p.x - fp.x, p.y - fp.y, -fp.rot))).collect()
}

/// Where the pads of every part sit now: moved parts at their move, the rest where the board has
/// them (parts parked outside the outline are left out: their position means nothing yet).
struct PadMap {
    at: BTreeMap<String, Vec<(String, Pt)>>,
    small_nets: std::collections::BTreeSet<String>,
}

impl PadMap {
    fn new(board: &Board) -> PadMap {
        let (x0, y0, x1, y1) = board.bbox;
        let mut at: BTreeMap<String, Vec<(String, Pt)>> = BTreeMap::new();
        for p in &board.pads {
            if p.net.is_empty() || p.x < x0 || p.x > x1 || p.y < y0 || p.y > y1 {
                continue;
            }
            at.entry(p.reference.clone()).or_default().push((p.net.clone(), (p.x, p.y)));
        }
        // nets with a handful of pads: a ground or rail with dozens of pads says nothing about adjacency
        let small_nets = board.nets.iter().filter(|(_, v)| v.len() <= 8).map(|(k, _)| k.clone()).collect();
        PadMap { at, small_nets }
    }

    fn place(&mut self, board: &Board, reference: &str, x: f64, y: f64, rot: f64) {
        let pads = local_pads(board, reference).into_iter().filter(|(_, n, _)| !n.is_empty()).map(|(_, n, (lx, ly))| { let (a, b) = geom::rot_kicad(lx, ly, rot); (n, (x + a, y + b)) }).collect();
        self.at.insert(reference.to_string(), pads);
    }

    /// Sum over the part's pads on small nets of the distance to the nearest same-net pad of another part.
    fn adjacency(&self, board: &Board, reference: &str, x: f64, y: f64, rot: f64) -> f64 {
        let mut total = 0.0;
        for (_, net, (lx, ly)) in local_pads(board, reference) {
            if !self.small_nets.contains(&net) {
                continue;
            }
            let (a, b) = geom::rot_kicad(lx, ly, rot);
            let (px, py) = (x + a, y + b);
            let best = self.at.iter().filter(|(r, _)| r.as_str() != reference).flat_map(|(_, v)| v.iter()).filter(|(n, _)| *n == net).map(|(_, (qx, qy))| (qx - px).hypot(qy - py)).fold(f64::INFINITY, f64::min);
            if best.is_finite() {
                total += best;
            }
        }
        total
    }
}

/// For each wish, in order, the nearest legal spot: courtyard clears every other courtyard by
/// `gap`, stays `edge` inside the outline box, avoids the keepout rectangles (grown by their margin).
/// When a wish lists several rotations and more than one is legal at the nearest spot, the one that
/// puts the part's pads nearest their net partners wins (ties keep the list order).
pub fn pack(board: &Board, wishes: &[(String, Wish)], gap: f64, edge: f64) -> (BTreeMap<String, Move>, Vec<String>) {
    let mut boxes = boxes(board);
    let (x0, y0, x1, y1) = board.bbox;
    let mut out = BTreeMap::new();
    let mut lines = Vec::new();
    let mut pads = PadMap::new(board);
    // issue #179: a candidate meets only the courtyards on its own side, plus every drilled pad and hole
    let side: BTreeMap<String, (bool, bool)> = board.footprints.keys().map(|r| (r.clone(), sides(board, r))).collect();
    let wished: Vec<&str> = wishes.iter().map(|(r, _)| r.as_str()).collect();
    let drilled = drilled_boxes(board, &wished);
    for (reference, w) in wishes {
        if !board.footprints.contains_key(reference) {
            lines.push(format!("{reference}: not on the board"));
            continue;
        }
        let pts = local_pts(board, reference);
        let mine = side[reference];
        let others: Vec<Box4> = boxes.iter().filter(|(r, _)| *r != reference && side.get(*r).is_none_or(|s| share_side(*s, mine))).map(|(_, b)| *b).chain(drilled.iter().copied()).collect();
        let g = w.gap.unwrap_or(gap);
        let n = (w.radius / 0.1) as i64;
        let mut cands: Vec<(f64, f64, f64)> = Vec::new();
        for i in -n..=n {
            for j in -n..=n {
                let d = ((i * i + j * j) as f64).sqrt() * 0.1;
                if d <= w.radius {
                    cands.push((d, ((w.x + i as f64 * 0.1) * 100.0).round() / 100.0, ((w.y + j as f64 * 0.1) * 100.0).round() / 100.0));
                }
            }
        }
        cands.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
        let mut best: Option<(f64, f64, f64, Box4, f64)> = None;
        'outer: for (d, x, y) in cands {
            let mut legal: Vec<(f64, Box4)> = Vec::new();
            for &rot in &w.rot {
                let b = placed_box(&pts, x, y, rot);
                if b.0 < x0 + edge || b.1 < y0 + edge || b.2 > x1 - edge || b.3 > y1 - edge {
                    continue;
                }
                if !clear(&b, &others, g) {
                    continue;
                }
                if w.keepout.iter().any(|(kx0, ky0, kx1, ky1, m)| b.0 - m < *kx1 && kx0 - m < b.2 && b.1 - m < *ky1 && ky0 - m < b.3) {
                    continue;
                }
                legal.push((rot, b));
            }
            if legal.is_empty() {
                continue;
            }
            let mut pick = legal[0];
            if legal.len() > 1 {
                let mut score = pads.adjacency(board, reference, x, y, pick.0);
                for &(rot, b) in &legal[1..] {
                    let s = pads.adjacency(board, reference, x, y, rot);
                    if s < score - 0.05 {
                        score = s;
                        pick = (rot, b);
                    }
                }
            }
            best = Some((x, y, pick.0, pick.1, d));
            break 'outer;
        }
        match best {
            None => lines.push(format!("{reference}: NO SPOT within {:.1} mm of ({:.1}, {:.1})", w.radius, w.x, w.y)),
            Some((x, y, rot, b, d)) => {
                boxes.insert(reference.clone(), b);
                pads.place(board, reference, x, y, rot);
                out.insert(reference.clone(), Move { x, y, rotation: Some(rot) });
                lines.push(format!("{reference}: ({x:.2}, {y:.2}, {rot}) {d:.2} mm from the wish, box x {:.2}..{:.2} y {:.2}..{:.2}", b.0, b.2, b.1, b.3));
            }
        }
    }
    (out, lines)
}

/// A series chain from the spec (`"chains": [["R1", "R2", "C9"]]`, or an entry
/// `{"refs": [...], "direction": "down", "gap": 0.25}`): parts in electrical order, each sharing a
/// net with the next. `place pack` lays them on one line in that order, on one axis, each turned
/// so the pads on the shared net face each other.
#[derive(Clone, Debug)]
pub struct Chain {
    pub refs: Vec<String>,
    pub direction: Option<String>,
    pub gap: Option<f64>,
}

/// `spec.chains` or `spec.placement.chains`.
pub fn chains_from_spec(spec: &Value) -> Result<Vec<Chain>, String> {
    let v = spec.get("chains").or_else(|| spec.get("placement").and_then(|p| p.get("chains")));
    let Some(a) = v.and_then(|v| v.as_array()) else { return Ok(Vec::new()) };
    let refs_of = |x: &Value| -> Option<Vec<String>> { x.as_array().map(|a| a.iter().filter_map(|r| r.as_str().map(str::to_string)).collect()) };
    let mut out = Vec::new();
    for (k, e) in a.iter().enumerate() {
        let chain = if let Some(refs) = refs_of(e) {
            Chain { refs, direction: None, gap: None }
        } else if let Some(refs) = e.get("refs").and_then(refs_of) {
            Chain { refs, direction: e.get("direction").and_then(|d| d.as_str()).map(str::to_string), gap: e.get("gap").and_then(|g| g.as_f64()) }
        } else {
            return Err(format!("chains[{k}]: use [\"R1\", \"R2\", ...] or {{\"refs\": [...], \"direction\": \"down\"}}"));
        };
        if chain.refs.len() < 2 {
            return Err(format!("chains[{k}]: a chain needs two or more parts"));
        }
        if let Some(d) = &chain.direction {
            if !matches!(d.as_str(), "down" | "up" | "left" | "right") {
                return Err(format!("chains[{k}]: direction {d:?} is not down, up, left or right"));
            }
        }
        out.push(chain);
    }
    Ok(out)
}

fn shared_net(board: &Board, a: &str, b: &str) -> Option<String> {
    let na: std::collections::BTreeSet<String> = board.pads.iter().filter(|p| p.reference == a && !p.net.is_empty()).map(|p| p.net.clone()).collect();
    board.pads.iter().filter(|p| p.reference == b).map(|p| p.net.clone()).find(|n| na.contains(n))
}

fn centroid(pts: &[Pt]) -> Option<Pt> {
    if pts.is_empty() { None } else { Some((pts.iter().map(|p| p.0).sum::<f64>() / pts.len() as f64, pts.iter().map(|p| p.1).sum::<f64>() / pts.len() as f64)) }
}

/// A chain as laid out for the packer: its members' rotations and the shared nets between them.
#[derive(Clone, Debug)]
pub struct ChainPlan {
    pub refs: Vec<String>,
    pub rots: Vec<f64>,
    pub nets: Vec<String>,
    pub direction: String,
}

/// Rewrite the wishes of every chain: members on one line from the first member's wish, in chain
/// order, each with the one rotation (0/90/180/270) that points its pad on the previous link's net
/// back up the chain and its pad on the next link's net down it. A chain that cannot be laid out
/// (a member without a wish or not on the board, two neighbours with no common net) is left alone
/// and says why.
pub fn apply_chains(board: &Board, wishes: &[(String, Wish)], chains: &[Chain], gap: f64) -> (Vec<(String, Wish)>, Vec<ChainPlan>, Vec<String>) {
    let mut out: Vec<(String, Wish)> = wishes.to_vec();
    let mut plans = Vec::new();
    let mut lines = Vec::new();
    'chain: for ch in chains {
        let name = ch.refs.join("-");
        for r in &ch.refs {
            if !board.footprints.contains_key(r) {
                lines.push(format!("chain {name}: not applied, {r} is not on the board"));
                continue 'chain;
            }
            if !out.iter().any(|(k, _)| k == r) {
                lines.push(format!("chain {name}: not applied, {r} has no wish (list every member in the wishes)"));
                continue 'chain;
            }
        }
        let mut nets = Vec::new();
        for w in ch.refs.windows(2) {
            match shared_net(board, &w[0], &w[1]) {
                Some(n) => nets.push(n),
                None => {
                    lines.push(format!("chain {name}: not applied, {} and {} share no net", w[0], w[1]));
                    continue 'chain;
                }
            }
        }
        let wish_of = |r: &str| out.iter().find(|(k, _)| k == r).map(|(_, w)| w.clone()).unwrap();
        let first = wish_of(&ch.refs[0]);
        let last = wish_of(ch.refs.last().unwrap());
        let direction = ch.direction.clone().unwrap_or_else(|| {
            let (dx, dy) = (last.x - first.x, last.y - first.y);
            if dx.abs() > dy.abs() { if dx > 0.0 { "right" } else { "left" } } else if dy < 0.0 { "up" } else { "down" }.to_string()
        });
        let d: Pt = match direction.as_str() { "up" => (0.0, -1.0), "left" => (-1.0, 0.0), "right" => (1.0, 0.0), _ => (0.0, 1.0) };
        let n = ch.refs.len();
        let mut rots = Vec::new();
        for (k, r) in ch.refs.iter().enumerate() {
            let pads = local_pads(board, r);
            let prev = if k > 0 { Some(&nets[k - 1]) } else { None };
            let next = if k + 1 < n { Some(&nets[k]) } else { None };
            let on = |net: Option<&String>| -> Vec<Pt> { pads.iter().filter(|(_, pn, _)| Some(pn) == net).map(|(_, _, p)| *p).collect() };
            let off = |net: Option<&String>| -> Vec<Pt> { pads.iter().filter(|(_, pn, _)| Some(pn) != net).map(|(_, _, p)| *p).collect() };
            let pin = centroid(&if prev.is_some() { on(prev) } else { off(next) }).unwrap_or((0.0, 0.0));
            let pout = centroid(&if next.is_some() { on(next) } else { off(prev) }).unwrap_or((0.0, 0.0));
            let v = (pout.0 - pin.0, pout.1 - pin.1);
            let rot = [0.0, 90.0, 180.0, 270.0].into_iter().max_by(|a, b| {
                let da = { let (x, y) = geom::rot_kicad(v.0, v.1, *a); x * d.0 + y * d.1 };
                let db = { let (x, y) = geom::rot_kicad(v.0, v.1, *b); x * d.0 + y * d.1 };
                da.partial_cmp(&db).unwrap().then(b.partial_cmp(a).unwrap())
            }).unwrap();
            rots.push(rot);
        }
        // centres along the line: each part's courtyard extent forward, the gap, the next part's extent back
        let g = ch.gap.unwrap_or(gap.max(0.25));
        let (mut cx, mut cy) = (first.x, first.y);
        for (k, r) in ch.refs.iter().enumerate() {
            let pts = local_pts(board, r);
            let b = placed_box(&pts, 0.0, 0.0, rots[k]);
            let (back, fwd) = match direction.as_str() { "up" => (b.3, -b.1), "left" => (b.2, -b.0), "right" => (-b.0, b.2), _ => (-b.1, b.3) };
            if k > 0 {
                cx += d.0 * (back + g);
                cy += d.1 * (back + g);
            }
            let e = out.iter_mut().find(|(key, _)| key == r).unwrap();
            e.1.x = (cx * 100.0).round() / 100.0;
            e.1.y = (cy * 100.0).round() / 100.0;
            e.1.rot = vec![rots[k]];
            cx += d.0 * fwd;
            cy += d.1 * fwd;
        }
        let same = rots.iter().all(|r| *r == rots[0]);
        lines.push(format!("chain {name}: laid out {direction} from ({:.2}, {:.2}), rotation{} {}", first.x, first.y, if same { "" } else { "s" }, if same { format!("{} for every member", rots[0]) } else { format!("{} (pad numbering differs, so a member turns 180 to face its neighbour)", rots.iter().map(|r| r.to_string()).collect::<Vec<_>>().join("/")) }));
        plans.push(ChainPlan { refs: ch.refs.clone(), rots, nets, direction });
    }
    (out, plans, lines)
}

/// After packing: was each chain honoured? Every member got its chain rotation, and for each link
/// the closest pair of pads between the two parts is a pair on their shared net.
pub fn chain_report(board: &Board, moves: &BTreeMap<String, Move>, plans: &[ChainPlan]) -> Vec<(String, bool, String)> {
    let mut out = Vec::new();
    for p in plans {
        let name = p.refs.join("-");
        let world = |r: &str| -> Option<Vec<(String, String, Pt)>> {
            let m = moves.get(r)?;
            let rot = m.rotation.unwrap_or(0.0);
            Some(local_pads(board, r).into_iter().map(|(pn, net, (lx, ly))| { let (a, b) = geom::rot_kicad(lx, ly, rot); (pn, net, (m.x + a, m.y + b)) }).collect())
        };
        let mut why = Vec::new();
        let mut links = Vec::new();
        for (k, r) in p.refs.iter().enumerate() {
            match moves.get(r) {
                None => why.push(format!("{r} found no spot")),
                Some(m) if m.rotation != Some(p.rots[k]) => why.push(format!("{r} at rotation {:?}, not {}", m.rotation, p.rots[k])),
                _ => {}
            }
        }
        if why.is_empty() {
            for (k, w) in p.refs.windows(2).enumerate() {
                let (Some(a), Some(b)) = (world(&w[0]), world(&w[1])) else { continue };
                let mut best: Option<(f64, &(String, String, Pt), &(String, String, Pt))> = None;
                for pa in &a {
                    for pb in &b {
                        let dd = (pa.2 .0 - pb.2 .0).hypot(pa.2 .1 - pb.2 .1);
                        if best.map(|x| dd < x.0 - 1e-6).unwrap_or(true) {
                            best = Some((dd, pa, pb));
                        }
                    }
                }
                if let Some((dd, pa, pb)) = best {
                    if pa.1 == p.nets[k] && pb.1 == p.nets[k] {
                        links.push(format!("{}.{}-{}.{} {} {:.2} mm", w[0], pa.0, w[1], pb.0, p.nets[k], dd));
                    } else {
                        why.push(format!("{} and {} face each other on {}.{}/{}.{}, not on {}", w[0], w[1], w[0], pa.0, w[1], pb.0, p.nets[k]));
                    }
                }
            }
        }
        if why.is_empty() {
            out.push((name, true, format!("honoured: {}", links.join(", "))));
        } else {
            out.push((name, false, format!("not honoured: {}", why.join("; "))));
        }
    }
    out
}

/// Move footprints in the file text: the anchor's `(at x y rot)`, and every child's own angle by
/// the rotation change (pads, properties, graphics carry the footprint rotation in the file).
pub fn move_in_text(board: &Board, moves: &BTreeMap<String, Move>) -> Result<(String, Vec<String>), String> {
    let mut edits: Vec<(usize, usize, String)> = Vec::new();
    let mut lines = Vec::new();
    for (reference, m) in moves {
        let fp = board.footprints.get(reference).ok_or_else(|| format!("{reference} is not on the board"))?;
        let block = &board.text[fp.start..fp.end];
        let node = aiflow_board::sx::parse(block).map_err(|e| format!("{reference}: {e}"))?;
        let at = node.find("at").ok_or_else(|| format!("{reference}: no (at ...)"))?;
        let orot = at.number(3).unwrap_or(0.0);
        let nrot = m.rotation.unwrap_or(orot);
        let drot = nrot - orot;
        let new_at = format!("(at {} {}{})", num(m.x), num(m.y), if nrot == 0.0 { String::new() } else { format!(" {}", num(nrot)) });
        edits.push((fp.start + at.start, fp.start + at.end, new_at));
        if drot.abs() > 1e-9 {
            // every nested (at ...) except the footprint's own
            fn walk(n: &aiflow_board::Node, base: usize, drot: f64, edits: &mut Vec<(usize, usize, String)>, top: bool) {
                for c in n.nodes() {
                    if c.tag == "at" && !top {
                        let a = c.number(3).unwrap_or(0.0) + drot;
                        let a = ((a + 180.0).rem_euclid(360.0)) - 180.0;
                        let (x, y) = (c.atom(1).unwrap_or("0"), c.atom(2).unwrap_or("0"));
                        edits.push((base + c.start, base + c.end, format!("(at {} {}{})", x, y, if a.abs() < 1e-9 { String::new() } else { format!(" {}", num(a)) })));
                    } else if c.tag != "at" {
                        walk(c, base, drot, edits, false);
                    }
                }
            }
            for c in node.nodes() {
                if c.tag != "at" {
                    walk(c, fp.start, drot, &mut edits, false);
                }
            }
        }
        lines.push(format!("moved {reference:<6} ({:.2}, {:.2}, {}) -> ({:.2}, {:.2}, {})", fp.x, fp.y, num(orot), m.x, m.y, num(nrot)));
    }
    edits.sort_by_key(|e| e.0);
    let mut out = String::with_capacity(board.text.len());
    let mut pos = 0;
    for (a, b, ins) in edits {
        if a < pos {
            return Err("overlapping edits".into());
        }
        out.push_str(&board.text[pos..a]);
        out.push_str(&ins);
        pos = b;
    }
    out.push_str(&board.text[pos..]);
    Ok((out, lines))
}

/// The parts whose body may overhang the outline on purpose (issue #95: a USB-C mouth proud of the
/// edge): spec `placement.edgeOverhang: [{ref, why}]`, each with a reason. Pads and copper of these
/// parts must still lie inside the outline (`copper_outside`); edge clearance stays a DRC matter.
pub fn edge_overhang(spec: &Value) -> Result<Vec<(String, String)>, String> {
    let Some(v) = spec.get("placement").and_then(|p| p.get("edgeOverhang")) else { return Ok(Vec::new()) };
    let a = v.as_array().ok_or("placement.edgeOverhang must be a list: [{\"ref\": \"J13\", \"why\": \"USB-C mouth proud of the edge\"}]")?;
    let mut out = Vec::new();
    for e in a {
        let r = e.get("ref").and_then(|r| r.as_str()).filter(|r| !r.trim().is_empty()).ok_or("each placement.edgeOverhang entry needs a ref")?;
        let why = e.get("why").and_then(|w| w.as_str()).filter(|w| !w.trim().is_empty()).ok_or_else(|| format!("placement.edgeOverhang {r} needs a why (what the overhang is for)"))?;
        out.push((r.to_string(), why.to_string()));
    }
    Ok(out)
}

/// Pads and footprint copper of `refs` that lie outside the board outline (or inside a cutout): an
/// allowed overhang lets the body cross the edge, never copper. One line per offending item.
pub fn copper_outside(board: &Board, refs: &[String]) -> Vec<String> {
    let outside = |p: (f64, f64)| (board.outline.len() >= 3 && !geom::point_in_poly(p.0, p.1, &board.outline)) || board.outline_cutouts.iter().any(|c| geom::point_in_poly(p.0, p.1, c));
    let mut out = Vec::new();
    for r in refs {
        if !board.footprints.contains_key(r) { out.push(format!("{r} is not on the board")); continue; }
        for p in board.pads.iter().filter(|p| &p.reference == r) {
            if let Some(q) = p.polys.iter().flatten().find(|q| outside(**q)) { out.push(format!("pad {} reaches outside the outline at ({:.2}, {:.2})", p.key, q.0, q.1)); }
        }
    }
    let copper: Vec<_> = aiflow_board::silk::shapes(board, &|l| l.ends_with(".Cu")).into_iter().filter(|s| refs.iter().any(|r| s.what().starts_with(&format!("{r} ")))).collect();
    for s in copper {
        let pts: Vec<(f64, f64)> = match &s { aiflow_board::silk::Shape::Stroke { a, b, .. } => vec![*a, *b], aiflow_board::silk::Shape::Poly { pts, .. } => pts.clone(), aiflow_board::silk::Shape::Box { x0, y0, x1, y1, .. } => vec![(*x0, *y0), (*x1, *y1)] };
        if let Some(q) = pts.iter().find(|q| outside(**q)) { out.push(format!("{} copper ({}) reaches outside the outline at ({:.2}, {:.2})", s.what(), s.layer(), q.0, q.1)); }
    }
    out
}

/// Issue #140: every footprint on the board (moved or not) whose pads or courtyard lie outside the
/// Edge.Cuts outline, as (ref, what is outside). A part `place pack` found no spot for stays where it
/// was parked, often off the board; `place check`, `place land` and `route` report these as findings
/// with a suggestion, never as a refusal. Parts in `overhang` (an edge connector allowed past the edge)
/// are left to `copper_outside`.
pub fn parts_outside(board: &Board, overhang: &[String]) -> Vec<(String, String)> {
    if board.outline.len() < 3 { return Vec::new(); }
    let whole = board.parts_outside();
    let boxes = boxes(board);
    let (x0, y0, x1, y1) = board.bbox;
    let mut out = Vec::new();
    for (r, fp) in &board.footprints {
        if overhang.contains(r) { continue; }
        if whole.contains(r) {
            out.push((r.clone(), format!("{r} is outside the board outline (at {:.2}, {:.2}; the outline spans x {:.2}..{:.2}, y {:.2}..{:.2})", fp.x, fp.y, x0, x1, y0, y1)));
            continue;
        }
        let pad_out = board.pads.iter().filter(|p| &p.reference == r).find_map(|p| p.polys.iter().flatten().find(|q| board.point_outside(q.0, q.1)).map(|q| (p.key.clone(), *q)));
        if let Some((k, q)) = pad_out {
            out.push((r.clone(), format!("{r} reaches past the board outline: pad {k} at ({:.2}, {:.2})", q.0, q.1)));
            continue;
        }
        if let Some(b) = boxes.get(r) {
            if b.0 < x0 - 1e-6 || b.1 < y0 - 1e-6 || b.2 > x1 + 1e-6 || b.3 > y1 + 1e-6 {
                out.push((r.clone(), format!("{r}'s courtyard reaches past the board outline (x {:.2}..{:.2}, y {:.2}..{:.2}; the outline spans x {:.2}..{:.2}, y {:.2}..{:.2})", b.0, b.2, b.1, b.3, x0, x1, y0, y1)));
            }
        }
    }
    out
}

/// The suggestion that goes with `parts_outside` findings.
pub const OUTSIDE_HINT: &str = "Move each part named above inside the outline: give it a wish in the wishes file (or a wider radius) and run `place pack` again (a pack that reports N-1 of N parts placed left the missing part where it was), then `place check` and `place land`. An edge connector meant to overhang: name it in spec placement.edgeOverhang [{\"ref\", \"why\"}].";

/// Courtyard overlaps and outside-the-outline parts among the moved refs on a board.
pub fn check(board: &Board, moved: &[String], gap: f64) -> Vec<String> {
    check_allowing(board, moved, gap, &[])
}

/// `check`, with the parts in `overhang` allowed past the outline (their pads are checked by
/// `copper_outside` instead).
pub fn check_allowing(board: &Board, moved: &[String], gap: f64, overhang: &[String]) -> Vec<String> {
    let boxes = boxes(board);
    let mut problems = Vec::new();
    let refs: Vec<&String> = boxes.keys().collect();
    for (i, a) in refs.iter().enumerate() {
        for b in &refs[i + 1..] {
            if !moved.contains(a) && !moved.contains(b) {
                continue;
            }
            // issue #179: a top part and a bottom part never share a courtyard layer
            if !share_side(sides(board, a), sides(board, b)) {
                continue;
            }
            let (ba, bb) = (boxes[*a], boxes[*b]);
            if ba.0 - gap < bb.2 && bb.0 - gap < ba.2 && ba.1 - gap < bb.3 && bb.1 - gap < ba.3 {
                problems.push(format!("courtyards overlap: {a} {b}"));
            }
        }
    }
    let (x0, y0, x1, y1) = board.bbox;
    for r in moved {
        if overhang.contains(r) { continue; }
        if let Some(b) = boxes.get(r) {
            if b.0 < x0 + 0.5 || b.1 < y0 + 0.5 || b.2 > x1 - 0.5 || b.3 > y1 - 0.5 {
                problems.push(format!("outside the outline: {r}"));
            }
        }
    }
    problems
}

/// Wishes are packed in the order given. An array `[{"ref": "U5", "x": .., "y": ..}, ...]` keeps
/// that order; an object `{REF: {...}}` is packed alphabetically (JSON objects carry no order),
/// which is rarely what a placement wants: put the big parts first as an array.
pub fn wishes_from_json(v: &Value) -> Result<Vec<(String, Wish)>, String> {
    let mut out = Vec::new();
    if let Some(a) = v.as_array() {
        for e in a {
            let k = e.get("ref").and_then(|r| r.as_str()).ok_or("each wish in the array needs a ref")?.to_string();
            out.push((k.clone(), serde_json::from_value(e.clone()).map_err(|e| format!("{k}: {e}"))?));
        }
        return Ok(out);
    }
    let o = v.as_object().ok_or("wishes must be an array [{ref, x, y, ...}] (packed in order) or an object {REF: {...}}")?;
    for (k, w) in o {
        out.push((k.clone(), serde_json::from_value(w.clone()).map_err(|e| format!("{k}: {e}"))?));
    }
    Ok(out)
}

pub fn moves_from_json(v: &Value) -> Result<BTreeMap<String, Move>, String> {
    serde_json::from_value(v.clone()).map_err(|e| e.to_string())
}

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

    /// A 30 x 20 mm board with two-pad parts: (reference, pad 1 net, pad 2 net, x, y); pads 1 mm apart on x.
    fn board(parts: &[(&str, &str, &str, f64, f64)]) -> Board {
        let mut t = String::from("(kicad_pcb\n\t(version 20260206)\n\t(generator \"test\")\n\t(layers\n\t\t(0 \"F.Cu\" signal)\n\t\t(2 \"B.Cu\" signal)\n\t\t(25 \"Edge.Cuts\" user)\n\t)\n");
        for (r, n1, n2, x, y) in parts {
            let pad = |name: &str, dx: f64, net: &str| format!("\t\t(pad \"{name}\" smd rect\n\t\t\t(at {dx} 0)\n\t\t\t(size 0.6 0.6)\n\t\t\t(layers \"F.Cu\")\n\t\t\t(net \"{net}\")\n\t\t)\n");
            t.push_str(&format!("\t(footprint \"T:R\"\n\t\t(layer \"F.Cu\")\n\t\t(at {x} {y})\n\t\t(property \"Reference\" \"{r}\")\n{}{}\t)\n", pad("1", -0.5, n1), pad("2", 0.5, n2)));
        }
        t.push_str("\t(gr_rect\n\t\t(start 0 0)\n\t\t(end 30 20)\n\t\t(layer \"Edge.Cuts\")\n\t)\n)\n");
        Board::from_text("test.kicad_pcb", t).unwrap()
    }

    fn wish(x: f64, y: f64, rot: &[f64]) -> Wish {
        Wish { x, y, rot: rot.to_vec(), radius: 3.0, keepout: Vec::new(), gap: None }
    }

    /// Issue #179: a QFN on F.Cu at (10, 10), a 0402 on B.Cu and a 0402 on F.Cu parked aside, and a
    /// through-hole header at (20, 10).
    fn two_sided() -> Board {
        let crt = |layer: &str, h: f64, w: f64| format!("\t\t(fp_rect (start {} {}) (end {w} {h}) (layer \"{layer}\"))\n", -w, -h);
        let smd = |r: &str, layer: &str, x: f64, y: f64, h: f64, w: f64| format!("\t(footprint \"T:{r}\"\n\t\t(layer \"{layer}\")\n\t\t(at {x} {y})\n\t\t(property \"Reference\" \"{r}\")\n{}\t\t(pad \"1\" smd rect (at 0 0) (size 0.5 0.5) (layers \"{}\") (net \"N{r}\"))\n\t)\n", crt(&layer.replace(".Cu", ".CrtYd"), h, w), layer);
        let mut t = String::from("(kicad_pcb\n\t(version 20260206)\n\t(generator \"test\")\n\t(layers\n\t\t(0 \"F.Cu\" signal)\n\t\t(2 \"B.Cu\" signal)\n\t\t(25 \"Edge.Cuts\" user)\n\t)\n");
        t.push_str(&smd("U1", "F.Cu", 10.0, 10.0, 2.0, 2.0));
        t.push_str(&smd("C1", "B.Cu", 3.0, 3.0, 0.5, 0.9));
        t.push_str(&smd("C2", "F.Cu", 3.0, 17.0, 0.5, 0.9));
        t.push_str(&format!("\t(footprint \"T:J1\"\n\t\t(layer \"F.Cu\")\n\t\t(at 20 10)\n\t\t(property \"Reference\" \"J1\")\n{}\t\t(pad \"1\" thru_hole circle (at 0 0) (size 1.7 1.7) (drill 1) (layers \"*.Cu\") (net \"NJ\"))\n\t)\n", crt("F.CrtYd", 1.0, 1.0)));
        t.push_str("\t(gr_rect\n\t\t(start 0 0)\n\t\t(end 30 20)\n\t\t(layer \"Edge.Cuts\")\n\t)\n)\n");
        Board::from_text("two.kicad_pcb", t).unwrap()
    }

    #[test]
    fn pack_puts_a_bottom_part_under_a_top_part_and_keeps_sides_apart() {
        let b = two_sided();
        assert_eq!((sides(&b, "U1"), sides(&b, "C1"), sides(&b, "J1")), ((true, false), (false, true), (true, true)));
        // the bottom 0402 wished at the QFN's centre gets its spot 0.00 mm from the wish
        let (m, lines) = pack(&b, &[("C1".into(), wish(10.0, 10.0, &[0.0]))], 0.05, 0.3);
        assert_eq!((m["C1"].x, m["C1"].y), (10.0, 10.0), "{lines:?}");
        assert!(lines[0].contains("0.00 mm from the wish"), "{lines:?}");
        // a top 0402 wished there has to leave the QFN's courtyard
        let (m, _) = pack(&b, &[("C2".into(), wish(10.0, 10.0, &[0.0]))], 0.05, 0.3);
        assert!((m["C2"].x - 10.0).abs() > 1.0 || (m["C2"].y - 10.0).abs() > 1.0, "{:?}", m["C2"]);
        // a through-hole part is on both sides: the bottom 0402 cannot sit on the header
        let (m, _) = pack(&b, &[("C1".into(), wish(20.0, 10.0, &[0.0]))], 0.05, 0.3);
        assert!((m["C1"].x - 20.0).abs() >= 1.0 || (m["C1"].y - 10.0).abs() >= 1.0, "{:?}", m["C1"]);
        // the overlap advisory is per side too: C1 under U1 is fine, C2 on U1 is not
        let (text, _) = move_in_text(&b, &BTreeMap::from([("C1".to_string(), Move { x: 10.0, y: 10.0, rotation: None }), ("C2".to_string(), Move { x: 10.0, y: 10.5, rotation: None })])).unwrap();
        let moved = Board::from_text("moved.kicad_pcb", text).unwrap();
        let problems = check(&moved, &["C1".into(), "C2".into()], 0.05);
        assert!(problems.iter().any(|p| p.contains("C2 U1")), "{problems:?}");
        assert!(!problems.iter().any(|p| p.contains("C1") && p.contains("U1")), "{problems:?}");
    }

    /// Issue #140: a part parked off the board is a finding that names it; one straddling the edge
    /// names its pad; parts inside, and an allowed overhang, are not listed.
    #[test]
    fn parts_outside_the_outline_are_named() {
        let b = board(&[("R1", "A", "B", 10.0, 10.0), ("U7", "A", "B", 45.0, 10.0), ("R2", "A", "B", 29.8, 5.0), ("J1", "A", "B", 29.8, 15.0)]);
        let f = parts_outside(&b, &["J1".to_string()]);
        let refs: Vec<&str> = f.iter().map(|(r, _)| r.as_str()).collect();
        assert_eq!(refs, ["R2", "U7"], "{f:?}");
        assert!(f[1].1.starts_with("U7 is outside the board outline"), "{f:?}");
        assert!(f[0].1.contains("pad R2.2"), "{f:?}");
        assert_eq!(b.parts_outside(), ["U7"]);
        // the pack never moved U7 (no wish): its line is the finding, not the moved parts' advisory
        assert!(check(&b, &["R1".to_string()], 0.05).is_empty());
    }

    #[test]
    fn chains_parse_from_the_spec() {
        let c = chains_from_spec(&json!({"chains": [["R1", "R2"], {"refs": ["R3", "R4", "R5"], "direction": "left", "gap": 0.3}]})).unwrap();
        assert_eq!(c.len(), 2);
        assert_eq!(c[1].direction.as_deref(), Some("left"));
        assert_eq!(chains_from_spec(&json!({"placement": {"chains": [["A", "B"]]}})).unwrap().len(), 1);
        assert!(chains_from_spec(&json!({"chains": [["R1"]]})).is_err());
        assert!(chains_from_spec(&json!({"chains": [{"refs": ["R1", "R2"], "direction": "sideways"}]})).is_err());
        assert!(chains_from_spec(&json!({})).unwrap().is_empty());
    }

    #[test]
    fn a_chain_is_laid_on_one_line_with_shared_pads_facing() {
        // R1: A-B; R2 numbered the other way round: C-B; parked outside the outline
        let b = board(&[("R1", "A", "B", 40.0, 5.0), ("R2", "C", "B", 44.0, 5.0)]);
        let wishes = vec![("R1".to_string(), wish(10.0, 8.0, &[0.0, 90.0, 180.0, 270.0])), ("R2".to_string(), wish(10.0, 12.0, &[0.0, 90.0, 180.0, 270.0]))];
        let chains = chains_from_spec(&json!({"chains": [["R1", "R2"]]})).unwrap();
        let (w, plans, lines) = apply_chains(&b, &wishes, &chains, 0.05);
        assert_eq!(plans.len(), 1, "{lines:?}");
        assert_eq!(plans[0].direction, "down");
        // R1's B pad (pad 2, local +x) points down at 270; R2's B pad (pad 2) must point up: 90
        assert_eq!(plans[0].rots, vec![270.0, 90.0]);
        assert_eq!(w[0].1.x, w[1].1.x, "one line");
        assert!(w[1].1.y > w[0].1.y);
        let (mv, _) = pack(&b, &w, 0.05, 0.0);
        let verdict = chain_report(&b, &mv, &plans);
        assert!(verdict[0].1, "{verdict:?}");
        assert!(verdict[0].2.contains("R1.2-R2.2 B"), "{verdict:?}");
    }

    #[test]
    fn a_chain_with_a_missing_member_or_no_common_net_is_left_alone() {
        let b = board(&[("R1", "A", "B", 40.0, 5.0), ("R2", "C", "D", 44.0, 5.0)]);
        let wishes = vec![("R1".to_string(), wish(10.0, 8.0, &[0.0])), ("R2".to_string(), wish(10.0, 12.0, &[0.0]))];
        let (w, plans, lines) = apply_chains(&b, &wishes, &chains_from_spec(&json!({"chains": [["R1", "R2"]]})).unwrap(), 0.05);
        assert!(plans.is_empty() && lines[0].contains("share no net"), "{lines:?}");
        assert_eq!(w[1].1.y, 12.0);
        let (_, plans, lines) = apply_chains(&b, &wishes[..1], &chains_from_spec(&json!({"chains": [["R1", "R2"]]})).unwrap(), 0.05);
        assert!(plans.is_empty() && lines[0].contains("R2 has no wish"), "{lines:?}");
    }

    #[test]
    fn pack_turns_a_part_so_its_pad_faces_its_net_partner() {
        // P is already placed at the left; R1's pad 2 is on P's net, so R1 turns 180 to face it
        let b = board(&[("P", "X", "Y", 5.0, 10.0), ("R1", "Z", "Y", 40.0, 5.0)]);
        let (mv, _) = pack(&b, &[("R1".to_string(), wish(9.0, 10.0, &[0.0, 180.0]))], 0.05, 0.0);
        assert_eq!(mv["R1"].rotation, Some(180.0));
        // with the partner on the right, the list order (0) already faces it and stays
        let b = board(&[("P", "X", "Y", 13.0, 10.0), ("R1", "Z", "Y", 40.0, 5.0)]);
        let (mv, _) = pack(&b, &[("R1".to_string(), wish(9.0, 10.0, &[0.0, 180.0]))], 0.05, 0.0);
        assert_eq!(mv["R1"].rotation, Some(0.0));
    }

    /// The buck run's own placement: the VOUT-R1-FBM-R2-FB-R3-GND divider as a chain.
    #[test]
    fn the_buck_divider_chain_is_honoured_on_the_real_board() {
        let src = "/home/adom/project/buck-12v5v-molecule/aiflow";
        if !std::path::Path::new(&format!("{src}/run/board-0.kicad_pcb")).is_file() {
            return;
        }
        let tmp = std::env::temp_dir().join(format!("aiflow-place-chain-{}", std::process::id()));
        std::fs::create_dir_all(&tmp).unwrap();
        let bp = tmp.join("board-0.kicad_pcb");
        std::fs::copy(format!("{src}/run/board-0.kicad_pcb"), &bp).unwrap();
        let b = Board::load(bp.to_str().unwrap()).unwrap();
        let wishes = wishes_from_json(&serde_json::from_str(&std::fs::read_to_string(format!("{src}/wishes.json")).unwrap()).unwrap()).unwrap();
        let chains = chains_from_spec(&json!({"chains": [{"refs": ["R1", "R2", "R3"], "direction": "down"}]})).unwrap();
        let (w, plans, lines) = apply_chains(&b, &wishes, &chains, 0.05);
        assert_eq!(plans.len(), 1, "{lines:?}");
        assert!(plans[0].rots.iter().all(|r| *r == plans[0].rots[0]), "{:?}", plans[0].rots);
        let (mv, _) = pack(&b, &w, 0.05, 0.0);
        let verdict = chain_report(&b, &mv, &plans);
        std::fs::remove_dir_all(&tmp).ok();
        assert!(verdict[0].1, "{verdict:?}");
    }
}