AI Flow: Reverse Engineering

//! The router: closes the connections nobody can see, on every signal layer of the stackup.
//!
//! A through-hole via is the only layer change, because that is what the photos show. The board is a
//! 0.05 mm grid per copper layer. Every piece of copper stamps a keep-out for the centre line of a
//! narrowest track (its own width or shape, plus the clearance, plus half a track), so a cell is usable
//! by a net exactly when all copper near it belongs to that net. A wider track or a via tests a ring
//! around the cell. Stamps are counted, so ripping a net up removes exactly what it added.
//!
//! Only what cannot be moved blocks: pads, holes, vias seen on the board in copper of a known net (a hole through
//! every layer) and the board edge. Seen copper does not block, because a real via passes through a pour and the pour clears around
//! it, and the fill here is computed after routing, so it does the same. Crossing seen copper of another net
//! costs instead: six times the length for copper of unknown net, which may be the net being routed, twelve for
//! a known net. A net's own copper is free and counts as connected. The length that still crosses foreign copper
//! is reported for each stackup: it measures how far the route departs from the photo, and so how hard the board
//! is at that layer count.
//!
//! Inner layers are either planes (no routing, a via landing there is connected) or signal layers.
//! A connection that finds no path is searched again with routed copper made passable at a cost: the nets
//! it crossed are ripped up and queued again, and the congested tiles get dearer so the next try differs.
//! When a whole pass closes nothing new the search stops: the layer count is what limits it, and the
//! caller moves to the next stackup.
use crate::kicad_out::{Grid, Pad};
use crate::raster::Mask;
use serde_json::{json, Value};
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::time::Instant;

/// Stays clear of rounding in the stamps, so the DRC sees at least the rule.
const MARGIN: f64 = 0.012;
const STEP: u32 = 50;
const DIAG: u32 = 71;
const DIRS: [(i32, i32); 8] = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)];

#[derive(Clone, Debug)]
pub struct Rules { pub clr: f64, pub track: f64, pub power_track: f64, pub via: (f64, f64), pub power_via: (f64, f64), pub edge: f64, pub hole_clr: f64, pub hole_hole: f64 }

/// `cells`: the zone's copper on the grid.
pub struct ZoneIn { pub id: String, pub net: String, pub layer: usize, pub cells: Vec<usize> }
pub struct ViaIn { pub id: String, pub net: String, pub x: f64, pub y: f64, pub d: f64, pub h: f64 }
/// A piece of track seen on the photo.
pub struct TrackIn { pub id: String, pub net: String, pub layer: usize, pub path: Vec<(f64, f64)>, pub w: f64 }
/// Copper and pins the photo shows joined already, on one net.
pub struct GroupIn { pub net: String, pub pins: Vec<String>, pub zones: Vec<String>, pub traces: Vec<String>, pub vias: Vec<String> }

pub struct Input<'a> {
    pub pads: &'a [Pad],
    pub layers: Vec<String>,
    /// net name to its plane layer index
    pub planes: HashMap<String, usize>,
    pub inside: &'a Mask,
    pub grid: &'a Grid,
    pub zones: Vec<ZoneIn>,
    pub vias: Vec<ViaIn>,
    pub tracks: Vec<TrackIn>,
    pub groups: Vec<GroupIn>,
    pub rules: Rules,
    pub power: HashSet<String>,
    pub seconds: f64,
    /// passes without a better result before the layer count is called the limit
    pub stall: usize,
}

struct Field { cnt: Vec<u16>, sum: Vec<u32>, sq: Vec<u32> }
impl Field {
    fn new(n: usize) -> Field { Field { cnt: vec![0; n], sum: vec![0; n], sq: vec![0; n] } }
    /// All copper stamped here belongs to net `n`: count, sum and sum of squares only agree when every id equals n.
    #[inline] fn ok(&self, i: usize, n: u32) -> bool { let c = self.cnt[i] as u32; c == 0 || (self.sum[i] == c * n && self.sq[i] == c * n * n) }
    #[inline] fn add(&mut self, i: usize, n: u32, sign: i32) {
        if sign > 0 { self.cnt[i] += 1; self.sum[i] += n; self.sq[i] += n * n; } else { self.cnt[i] -= 1; self.sum[i] -= n; self.sq[i] -= n * n; }
    }
}

#[derive(Clone, Debug)] struct Seg { l: usize, a: (f64, f64), b: (f64, f64), w: f64 }
#[derive(Clone, Debug)] struct Via { x: f64, y: f64, d: f64, h: f64 }

struct Group { cells: Vec<u32>, center: (f64, f64), pins: Vec<String>, root: bool }

#[derive(Clone, Debug, PartialEq)] enum Parent { Group(usize), Conn(usize), Plane }
/// One closed connection: which group it brought in, what it landed on, and its copper. Ripping it up also takes
/// whatever landed on it, and nothing else.
#[derive(Clone, Debug)] struct Conn { gi: usize, parent: Parent, segs: Vec<Seg>, vias: Vec<Via>, alive: bool }

struct Net { id: u32, name: String, plane: Option<usize>, power: bool, groups: Vec<Group>, on: Vec<bool>, conns: Vec<Conn>, reason: HashMap<usize, String>, rips: u32, necked: u32 }
impl Net { fn segs(&self) -> impl Iterator<Item = &Seg> { self.conns.iter().filter(|c| c.alive).flat_map(|c| c.segs.iter()) } fn vias(&self) -> impl Iterator<Item = &Via> { self.conns.iter().filter(|c| c.alive).flat_map(|c| c.vias.iter()) } }

struct R {
    w: usize, h: usize, nl: usize, x0: f64, y0: f64, res: f64,
    fixed: Field, routed: Field,
    /// who owns the seen copper at a cell: 0 nobody, 1 unknown net, else the net's id
    seen: Vec<u16>, routable: Vec<bool>, hist: Vec<u16>,
    best: Vec<u32>, stamp: Vec<u16>, par: Vec<u8>, gen: u16,
    tgt: Vec<u16>, tgen: u16, dt: Vec<u32>,
    vstamp: Vec<u16>, vres: Vec<bool>,
    drills: HashMap<(i32, i32), Vec<(f64, f64, f64)>>,
    rules: Rules,
}

fn ring(r_mm: f64, res: f64) -> Vec<(i32, i32)> {
    if r_mm <= 1e-6 { return vec![]; }
    let r = r_mm * res;
    let n = ((std::f64::consts::TAU * r).ceil() as usize).max(8);
    let mut v: Vec<(i32, i32)> = (0..n).map(|k| { let t = k as f64 / n as f64 * std::f64::consts::TAU; ((r * t.cos()).round() as i32, (r * t.sin()).round() as i32) }).collect();
    v.sort(); v.dedup(); v
}

impl R {
    #[inline] fn idx(&self, l: usize, x: usize, y: usize) -> usize { l * self.w * self.h + y * self.w + x }
    #[inline] fn un(&self, s: usize) -> (usize, usize, usize) { let wh = self.w * self.h; let l = s / wh; let r = s - l * wh; (l, r % self.w, r / self.w) }
    #[inline] fn mm(&self, x: usize, y: usize) -> (f64, f64) { (self.x0 + x as f64 / self.res, self.y0 + y as f64 / self.res) }
    #[inline] fn cell(&self, p: (f64, f64)) -> (i64, i64) { (((p.0 - self.x0) * self.res).round() as i64, ((p.1 - self.y0) * self.res).round() as i64) }

    fn stamp_pad(f: &mut Field, wid: usize, hei: usize, x0: f64, y0: f64, res: f64, l: usize, p: &Pad, rad: f64, n: u32) {
        let (hw, hh) = (p.w / 2.0, p.h / 2.0);
        let (c, s) = (p.rot.to_radians().cos(), p.rot.to_radians().sin());
        let ext = hw.max(hh) * std::f64::consts::SQRT_2 + rad;
        let (u0, u1) = (((p.x - ext - x0) * res).floor().max(0.0) as usize, (((p.x + ext - x0) * res).ceil() as usize).min(wid - 1));
        let (v0, v1) = (((p.y - ext - y0) * res).floor().max(0.0) as usize, (((p.y + ext - y0) * res).ceil() as usize).min(hei - 1));
        for v in v0..=v1 { for u in u0..=u1 {
            let (dx, dy) = (x0 + u as f64 / res - p.x, y0 + v as f64 / res - p.y);
            let (lx, ly) = (dx * c - dy * s, dx * s + dy * c);
            let d = if p.round { (lx * lx + ly * ly).sqrt() - hw } else { let (ax, ay) = ((lx.abs() - hw).max(0.0), (ly.abs() - hh).max(0.0)); (ax * ax + ay * ay).sqrt() };
            if d <= rad { f.add(l * wid * hei + v * wid + u, n, 1); }
        } }
    }

    fn stamp_capsule(&mut self, routed: bool, l: usize, a: (f64, f64), b: (f64, f64), rad: f64, n: u32, sign: i32) {
        let (w, h, x0, y0, res) = (self.w, self.h, self.x0, self.y0, self.res);
        let (u0, u1) = (((a.0.min(b.0) - rad - x0) * res).floor().max(0.0) as usize, (((a.0.max(b.0) + rad - x0) * res).ceil() as usize).min(w - 1));
        let (v0, v1) = (((a.1.min(b.1) - rad - y0) * res).floor().max(0.0) as usize, (((a.1.max(b.1) + rad - y0) * res).ceil() as usize).min(h - 1));
        let (dx, dy) = (b.0 - a.0, b.1 - a.1); let len2 = dx * dx + dy * dy;
        let f = if routed { &mut self.routed } else { &mut self.fixed };
        for v in v0..=v1 { for u in u0..=u1 {
            let (px, py) = (x0 + u as f64 / res - a.0, y0 + v as f64 / res - a.1);
            let t = if len2 > 0.0 { ((px * dx + py * dy) / len2).clamp(0.0, 1.0) } else { 0.0 };
            let (qx, qy) = (px - t * dx, py - t * dy);
            if qx * qx + qy * qy <= rad * rad { f.add(l * w * h + v * w + u, n, sign); }
        } }
    }

    fn keepout_seg(&self, w: f64) -> f64 { w / 2.0 + self.rules.clr + self.rules.track / 2.0 + MARGIN }

    fn add_seg(&mut self, net: u32, s: &Seg, sign: i32) { let r = self.keepout_seg(s.w); self.stamp_capsule(true, s.l, s.a, s.b, r, net, sign); }
    fn add_via(&mut self, net: u32, v: &Via, sign: i32) {
        let r = self.keepout_seg(v.d);
        for l in 0..self.nl { self.stamp_capsule(true, l, (v.x, v.y), (v.x, v.y), r, net, sign); }
        let key = ((v.x).floor() as i32, (v.y).floor() as i32);
        if sign > 0 { self.drills.entry(key).or_default().push((v.x, v.y, v.h / 2.0)); }
        else if let Some(b) = self.drills.get_mut(&key) { if let Some(i) = b.iter().position(|d| (d.0 - v.x).abs() < 1e-6 && (d.1 - v.y).abs() < 1e-6) { b.swap_remove(i); } }
    }

    fn hole_ok(&self, x: f64, y: f64, h: f64) -> bool {
        let (cx, cy) = (x.floor() as i32, y.floor() as i32);
        for j in -3..=3 { for i in -3..=3 { if let Some(b) = self.drills.get(&(cx + i, cy + j)) { for d in b {
            let e = ((d.0 - x).powi(2) + (d.1 - y).powi(2)).sqrt() - d.2 - h / 2.0;
            if e < self.rules.hole_hole + MARGIN { return false; }
        } } } }
        true
    }

    #[inline] fn seen_factor(&self, i: usize, n: u32) -> u32 { match self.seen[i] as u32 { 0 => 1, 1 => 6, o if o == n => 1, _ => 12 } }

    #[inline] fn pass_at(&self, l: usize, x: i64, y: i64, n: u32, soft: bool) -> bool {
        if x < 0 || y < 0 || x >= self.w as i64 || y >= self.h as i64 { return false; }
        let i = self.idx(l, x as usize, y as usize);
        self.fixed.ok(i, n) && (soft || self.routed.ok(i, n))
    }
    #[inline] fn pass_ring(&self, l: usize, x: i64, y: i64, n: u32, soft: bool, rg: &[(i32, i32)]) -> bool {
        if !self.pass_at(l, x, y, n, soft) { return false; }
        rg.iter().all(|o| self.pass_at(l, x + o.0 as i64, y + o.1 as i64, n, soft))
    }

    fn via_ok(&mut self, x: usize, y: usize, n: u32, vring: &[(i32, i32)], vh: f64, soft: bool) -> bool {
        let k = y * self.w + x;
        if self.vstamp[k] == self.gen { return self.vres[k]; }
        let (mx, my) = self.mm(x, y);
        let ok = self.hole_ok(mx, my, vh) && (0..self.nl).all(|l| self.pass_ring(l, x as i64, y as i64, n, soft, vring));
        self.vstamp[k] = self.gen; self.vres[k] = ok; ok
    }

    /// Chamfer distance from the marked target cells, ignoring layers: a heuristic that knows where the targets are.
    fn distance_field(&mut self) {
        let (w, h) = (self.w, self.h);
        self.dt.iter_mut().for_each(|v| *v = u32::MAX / 2);
        for l in 0..self.nl { for k in 0..w * h { if self.tgt[l * w * h + k] == self.tgen { self.dt[k] = 0; } } }
        for y in 0..h { for x in 0..w { let k = y * w + x; let mut d = self.dt[k];
            if x > 0 { d = d.min(self.dt[k - 1] + STEP); }
            if y > 0 { d = d.min(self.dt[k - w] + STEP); if x > 0 { d = d.min(self.dt[k - w - 1] + DIAG); } if x + 1 < w { d = d.min(self.dt[k - w + 1] + DIAG); } }
            self.dt[k] = d; } }
        for y in (0..h).rev() { for x in (0..w).rev() { let k = y * w + x; let mut d = self.dt[k];
            if x + 1 < w { d = d.min(self.dt[k + 1] + STEP); }
            if y + 1 < h { d = d.min(self.dt[k + w] + STEP); if x + 1 < w { d = d.min(self.dt[k + w + 1] + DIAG); } if x > 0 { d = d.min(self.dt[k + w - 1] + DIAG); } }
            self.dt[k] = d; } }
    }

    fn tile(&self, x: usize, y: usize, l: usize) -> usize { let (tw, th) = (self.w / 8 + 1, self.h / 8 + 1); l * tw * th + (y / 8) * tw + x / 8 }

    /// A* from the source cells to a marked target, or to `plane` by a via. Returns the states from source to goal.
    #[allow(clippy::too_many_arguments)]
    fn search(&mut self, n: u32, plane: Option<usize>, power: bool, srcs: &[u32], trk: &[(i32, i32)], vring: &[(i32, i32)], vh: f64, soft: bool, limit: usize) -> Option<Vec<u32>> {
        self.gen = self.gen.wrapping_add(1);
        if self.gen == 0 { self.stamp.iter_mut().for_each(|v| *v = 0); self.vstamp.iter_mut().for_each(|v| *v = 0); self.gen = 1; }
        let (w, h, nl) = (self.w, self.h, self.nl);
        let wh = w * h;
        let use_h = plane.is_none();
        let mut heap: BinaryHeap<Reverse<(u32, u32, u32)>> = BinaryHeap::new();
        for &s in srcs {
            let (l, x, y) = self.un(s as usize);
            if !self.pass_ring(l, x as i64, y as i64, n, soft, trk) { continue; }
            let i = s as usize;
            if self.stamp[i] == self.gen { continue; }
            self.stamp[i] = self.gen; self.best[i] = 0; self.par[i] = 255;
            let hh = if use_h { self.dt[y * w + x] } else { 0 };
            heap.push(Reverse((hh, 0, s)));
        }
        let via_cost: u32 = if power { 1200 } else { 1600 };
        let mut pops = 0usize;
        while let Some(Reverse((_, g, s))) = heap.pop() {
            let si = s as usize;
            if self.best[si] < g { continue; }
            pops += 1; if pops > limit { return None; }
            let (l, x, y) = self.un(si);
            if self.tgt[si] == self.tgen || plane == Some(l) {
                let mut path = vec![s]; let mut c = si;
                loop { let p = self.par[c]; if p == 255 { break; }
                    let (cl, cx, cy) = self.un(c);
                    c = if p < 8 { let d = DIRS[p as usize]; self.idx(cl, (cx as i32 - d.0) as usize, (cy as i32 - d.1) as usize) } else { self.idx(p as usize - 8, cx, cy) };
                    path.push(c as u32); }
                path.reverse();
                return Some(path);
            }
            if self.routable[l] {
                // the inner layers lean to alternate directions, so tracks on one do not fill the channels of the next
                let inner = l > 0 && l + 1 < nl;
                for (di, d) in DIRS.iter().enumerate() {
                    let (nx, ny) = (x as i64 + d.0 as i64, y as i64 + d.1 as i64);
                    if !self.pass_ring(l, nx, ny, n, soft, trk) { continue; }
                    let (nxu, nyu) = (nx as usize, ny as usize);
                    let ni = l * wh + nyu * w + nxu;
                    let mut c = if d.0 != 0 && d.1 != 0 { DIAG } else { STEP };
                    if inner && d.0 != 0 && d.1 != 0 { c += c / 8; } else if inner && ((l % 2 == 1) == (d.0 != 0)) { c += c / 4; }
                    c *= self.seen_factor(ni, n);
                    c += self.hist[self.tile(nxu, nyu, l)] as u32 * 8;
                    if soft && !self.routed.ok(ni, n) { c += 600; }
                    let ng = g + c;
                    if self.stamp[ni] != self.gen || ng < self.best[ni] {
                        self.stamp[ni] = self.gen; self.best[ni] = ng; self.par[ni] = di as u8;
                        let hh = if use_h { self.dt[nyu * w + nxu] + self.dt[nyu * w + nxu] / 4 } else { 0 };
                        heap.push(Reverse((ng + hh, ng, ni as u32)));
                    }
                }
            }
            if x % 2 == 0 && y % 2 == 0 && self.via_ok(x, y, n, vring, vh, soft) {
                let mut c = via_cost;
                if soft && !(0..nl).all(|q| self.pass_ring(q, x as i64, y as i64, n, false, vring)) { c += 3000; }
                for l2 in 0..nl {
                    if l2 == l || (!self.routable[l2] && plane != Some(l2)) { continue; }
                    let ni = l2 * wh + y * w + x;
                    let ng = g + c;
                    if self.stamp[ni] != self.gen || ng < self.best[ni] {
                        self.stamp[ni] = self.gen; self.best[ni] = ng; self.par[ni] = 8 + l as u8;
                        let hh = if use_h { self.dt[y * w + x] + self.dt[y * w + x] / 4 } else { 0 };
                        heap.push(Reverse((ng + hh, ng, ni as u32)));
                    }
                }
            }
        }
        None
    }

    /// Cells of a straight octile run, end included, start excluded. None if a and b are not on one octile line.
    fn walk(a: (i64, i64), b: (i64, i64)) -> Option<Vec<(i64, i64)>> {
        let (dx, dy) = (b.0 - a.0, b.1 - a.1);
        if dx != 0 && dy != 0 && dx.abs() != dy.abs() { return None; }
        let n = dx.abs().max(dy.abs());
        Some((1..=n).map(|i| (a.0 + dx.signum() * i, a.1 + dy.signum() * i)).collect())
    }

    /// Cost of a run on layer l, or None if it hits copper.
    fn run_cost(&self, l: usize, cells: &[(i64, i64)], prev: (i64, i64), n: u32, trk: &[(i32, i32)]) -> Option<u64> {
        let mut c = 0u64; let mut p = prev;
        for q in cells {
            if !self.pass_ring(l, q.0, q.1, n, false, trk) { return None; }
            let st = if q.0 != p.0 && q.1 != p.1 { DIAG } else { STEP } as u64;
            c += st * self.seen_factor(self.idx(l, q.0 as usize, q.1 as usize), n) as u64;
            p = *q;
        }
        Some(c)
    }

    /// Straighten a run of grid cells into few octile segments, never costlier than the path found.
    fn straighten(&self, l: usize, cells: &[(i64, i64)], n: u32, trk: &[(i32, i32)]) -> Vec<(i64, i64)> {
        if cells.len() < 3 { return cells.to_vec(); }
        let mut pre = vec![0u64; cells.len()];
        for i in 1..cells.len() {
            let (a, b) = (cells[i - 1], cells[i]);
            let st = if a.0 != b.0 && a.1 != b.1 { DIAG } else { STEP } as u64;
            pre[i] = pre[i - 1] + st * self.seen_factor(self.idx(l, b.0 as usize, b.1 as usize), n) as u64;
        }
        let mut out = vec![cells[0]]; let mut i = 0;
        while i + 1 < cells.len() {
            let mut span = (cells.len() - 1 - i).max(1); let mut done = false;
            while span >= 1 {
                let j = i + span; let (a, b) = (cells[i], cells[j]); let old = pre[j] - pre[i];
                let (dx, dy) = (b.0 - a.0, b.1 - a.1);
                let d = dx.abs().min(dy.abs());
                let k1 = (a.0 + dx.signum() * d, a.1 + dy.signum() * d);
                let k2 = (b.0 - dx.signum() * d, b.1 - dy.signum() * d);
                let mut best: Option<(u64, (i64, i64))> = None;
                for k in [k1, k2] {
                    let (Some(r1), Some(r2)) = (Self::walk(a, k), Self::walk(k, b)) else { continue };
                    let (Some(c1), Some(c2)) = (self.run_cost(l, &r1, a, n, trk), self.run_cost(l, &r2, k, n, trk)) else { continue };
                    if c1 + c2 <= old + STEP as u64 && best.map(|x| c1 + c2 < x.0).unwrap_or(true) { best = Some((c1 + c2, k)); }
                }
                if let Some((_, k)) = best { if k != a && k != b { out.push(k); } out.push(b); i = j; done = true; break; }
                if span == 1 { break; }
                span = (span * 2) / 3;
            }
            if !done { out.push(cells[i + 1]); i += 1; }
        }
        // merge collinear
        let mut m: Vec<(i64, i64)> = vec![];
        for p in out {
            if m.last() == Some(&p) { continue; }
            if m.len() >= 2 { let (a, b) = (m[m.len() - 2], m[m.len() - 1]);
                if (b.0 - a.0) * (p.1 - b.1) == (b.1 - a.1) * (p.0 - b.0) && (b.0 - a.0) * (p.0 - b.0) + (b.1 - a.1) * (p.1 - b.1) > 0 { *m.last_mut().unwrap() = p; continue; } }
            m.push(p);
        }
        m
    }
}

fn point_seg(p: (f64, f64), a: (f64, f64), b: (f64, f64)) -> f64 {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1); let len2 = dx * dx + dy * dy;
    let t = if len2 > 0.0 { (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / len2).clamp(0.0, 1.0) } else { 0.0 };
    ((p.0 - a.0 - t * dx).powi(2) + (p.1 - a.1 - t * dy).powi(2)).sqrt()
}

struct Uf(Vec<usize>);
impl Uf { fn find(&mut self, x: usize) -> usize { let mut r = x; while self.0[r] != r { r = self.0[r]; } let mut y = x; while self.0[y] != r { let n = self.0[y]; self.0[y] = r; y = n; } r }
          fn join(&mut self, a: usize, b: usize) { let (a, b) = (self.find(a), self.find(b)); if a != b { self.0[a] = b; } } }

fn pad_cells(r: &R, p: &Pad, l: usize) -> Vec<u32> {
    let (hw, hh) = (p.w / 2.0, p.h / 2.0);
    let (c, s) = (p.rot.to_radians().cos(), p.rot.to_radians().sin());
    let ext = hw.max(hh) * std::f64::consts::SQRT_2;
    let (u0, u1) = (((p.x - ext - r.x0) * r.res).floor().max(0.0) as usize, (((p.x + ext - r.x0) * r.res).ceil() as usize).min(r.w - 1));
    let (v0, v1) = (((p.y - ext - r.y0) * r.res).floor().max(0.0) as usize, (((p.y + ext - r.y0) * r.res).ceil() as usize).min(r.h - 1));
    let mut out = vec![];
    for v in v0..=v1 { for u in u0..=u1 {
        let (dx, dy) = (r.x0 + u as f64 / r.res - p.x, r.y0 + v as f64 / r.res - p.y);
        let (lx, ly) = (dx * c - dy * s, dx * s + dy * c);
        let hit = if p.round { lx * lx + ly * ly <= hw * hw } else { lx.abs() <= hw && ly.abs() <= hh };
        if hit { out.push(r.idx(l, u, v) as u32); }
    } }
    out
}

struct Snapshot { open: usize, conns: Vec<Vec<Conn>>, on: Vec<Vec<bool>>, reason: Vec<HashMap<usize, String>> }

pub fn run(inp: &Input, log: &mut dyn FnMut(String)) -> Value {
    let t0 = Instant::now();
    let g = inp.grid;
    let (w, h, nl) = (g.w, g.h, inp.layers.len());
    let total = w * h * nl;
    let rules = inp.rules.clone();
    let tr = rules.track / 2.0 + rules.clr + MARGIN;
    let mut r = R { w, h, nl, x0: g.x0, y0: g.y0, res: g.res, fixed: Field::new(total), routed: Field::new(total), seen: vec![0; total],
        routable: (0..nl).map(|l| !inp.planes.values().any(|v| *v == l)).collect(), hist: vec![0; nl * (w / 8 + 1) * (h / 8 + 1)],
        best: vec![0; total], stamp: vec![0; total], par: vec![0; total], gen: 0, tgt: vec![0; total], tgen: 0, dt: vec![0; w * h], vstamp: vec![0; w * h], vres: vec![false; w * h], drills: HashMap::new(), rules: rules.clone() };
    // net ids: 1 is foreign copper nobody may touch
    let mut ids: HashMap<String, u32> = HashMap::new();
    for p in inp.pads { if !p.net.is_empty() { let k = ids.len() as u32 + 2; ids.entry(p.net.clone()).or_insert(k); } }
    for z in &inp.zones { if !z.net.is_empty() && !z.net.starts_with("UNK") { let k = ids.len() as u32 + 2; ids.entry(z.net.clone()).or_insert(k); } }
    for v in &inp.vias { if !v.net.is_empty() && !v.net.starts_with("UNK") { let k = ids.len() as u32 + 2; ids.entry(v.net.clone()).or_insert(k); } }
    for t in &inp.tracks { if !t.net.is_empty() && !t.net.starts_with("UNK") { let k = ids.len() as u32 + 2; ids.entry(t.net.clone()).or_insert(k); } }
    let idn = |n: &str| ids.get(n).copied().unwrap_or(1);
    // board edge
    let keep = inp.inside.erode(((rules.edge + rules.track / 2.0 + MARGIN) * g.res) as f32);
    for k in 0..w * h { if !keep.d[k] { for l in 0..nl { r.fixed.add(l * w * h + k, 1, 1); } } }
    // pads and holes
    for p in inp.pads {
        let n = if p.net.is_empty() { 1 } else { idn(&p.net) };
        for (l, name) in inp.layers.iter().enumerate() { if p.on(name) { R::stamp_pad(&mut r.fixed, w, h, g.x0, g.y0, g.res, l, p, tr, n); } }
        if p.drill > 0.0 {
            let plated = p.layers.iter().any(|l| l == "*.Cu") && p.w > p.drill;
            let hn = if plated { n } else { 1 };
            for l in 0..nl { r.stamp_capsule(false, l, (p.x, p.y), (p.x, p.y), p.drill / 2.0 + rules.hole_clr + rules.track / 2.0 + MARGIN, hn, 1); }
            r.drills.entry((p.x.floor() as i32, p.y.floor() as i32)).or_default().push((p.x, p.y, p.drill / 2.0));
        }
    }
    // seen vias: a hole through every layer. One of unknown net is the weakest thing on the board (a dome no copper
    // explains may be a dimple), so it does not block: routed copper may displace it, and the count is reported.
    for v in &inp.vias {
        if v.net.starts_with("UNK") || v.net.is_empty() { continue; }
        let n = idn(&v.net);
        for l in 0..nl { r.stamp_capsule(false, l, (v.x, v.y), (v.x, v.y), v.d / 2.0 + tr, n, 1); }
        r.drills.entry((v.x.floor() as i32, v.y.floor() as i32)).or_default().push((v.x, v.y, v.h / 2.0));
    }
    // seen copper: who owns each cell
    for z in &inp.zones {
        let o: u16 = if z.net.starts_with("UNK") || z.net.is_empty() { 1 } else { idn(&z.net) as u16 };
        for k in &z.cells { r.seen[z.layer * w * h + *k] = o; }
    }
    for t in &inp.tracks {
        let o: u16 = if t.net.starts_with("UNK") || t.net.is_empty() { 1 } else { idn(&t.net) as u16 };
        for q in t.path.windows(2) {
            let (a, b) = (r.cell(q[0]), r.cell(q[1])); let n3 = (b.0 - a.0).abs().max((b.1 - a.1).abs()).max(1); let rad = ((t.w / 2.0) * g.res).ceil() as i64;
            for i in 0..=n3 { let (x, y) = (a.0 + (b.0 - a.0) * i / n3, a.1 + (b.1 - a.1) * i / n3);
                for dy in -rad..=rad { for dx in -rad..=rad { let (u, v) = (x + dx, y + dy); if u >= 0 && v >= 0 && (u as usize) < w && (v as usize) < h { r.seen[t.layer * w * h + v as usize * w + u as usize] = o; } } } }
        }
    }
    // nets and their groups of already joined copper
    let mut names: Vec<String> = vec![];
    for p in inp.pads { if !p.net.is_empty() && !names.contains(&p.net) { names.push(p.net.clone()); } }
    let mut nets: Vec<Net> = vec![];
    for name in &names {
        let plane = inp.planes.get(name).copied();
        let pads: Vec<&Pad> = inp.pads.iter().filter(|p| &p.net == name).collect();
        let zones: Vec<&ZoneIn> = inp.zones.iter().filter(|z| &z.net == name).collect();
        let vias: Vec<&ViaIn> = inp.vias.iter().filter(|v| &v.net == name).collect();
        let tracks: Vec<&TrackIn> = inp.tracks.iter().filter(|t| &t.net == name).collect();
        let (np, nz, nv) = (pads.len(), zones.len(), vias.len());
        let nt = tracks.len();
        let root_item = np + nz + nv + nt;
        let mut uf = Uf((0..=root_item).collect());
        let mut pins: HashMap<String, usize> = HashMap::new();
        for (i, p) in pads.iter().enumerate() { let k = format!("{}.{}", p.part, p.num); if let Some(j) = pins.get(&k) { uf.join(i, *j); } else { pins.insert(k, i); } }
        // a pad or via inside a pour of its own net is in that pour's copper
        for (zi, z) in zones.iter().enumerate() {
            let set: HashSet<usize> = z.cells.iter().copied().collect();
            let hit = |x: f64, y: f64| { let (u, v) = (((x - g.x0) * g.res) as i64, ((y - g.y0) * g.res) as i64); u >= 0 && v >= 0 && (u as usize) < w && (v as usize) < h && set.contains(&(v as usize * w + u as usize)) };
            for (i, p) in pads.iter().enumerate() { if p.on(&inp.layers[z.layer]) && hit(p.x, p.y) { uf.join(i, np + zi); } }
            for (vi, v) in vias.iter().enumerate() { if hit(v.x, v.y) { uf.join(np + nz + vi, np + zi); } }
        }
        // what the photo measured as joined
        for grp in inp.groups.iter().filter(|q| &q.net == name) {
            let mut items: Vec<usize> = vec![];
            for q in &grp.pins { if let Some(i) = pins.get(q) { items.push(*i); } }
            for q in &grp.zones { if let Some(i) = zones.iter().position(|z| &z.id == q) { items.push(np + i); } }
            for q in &grp.vias { if let Some(i) = vias.iter().position(|v| &v.id == q) { items.push(np + nz + i); } }
            for q in &grp.traces { if let Some(i) = tracks.iter().position(|t| &t.id == q) { items.push(np + nz + nv + i); } }
            for x in items.windows(2) { uf.join(x[0], x[1]); }
        }
        if plane.is_some() {
            for (i, p) in pads.iter().enumerate() { if p.drill > 0.0 && p.layers.iter().any(|l| l == "*.Cu") { uf.join(i, root_item); } }
            for vi in 0..nv { uf.join(np + nz + vi, root_item); }
        }
        // a through-hole pad and a via join their pieces on every layer
        let mut buckets: HashMap<usize, Vec<usize>> = HashMap::new();
        for i in 0..=root_item { let q = uf.find(i); buckets.entry(q).or_default().push(i); }
        let root_key = uf.find(root_item);
        let mut groups = vec![];
        let mut keys: Vec<usize> = buckets.keys().copied().collect(); keys.sort();
        for key in keys {
            let items = &buckets[&key];
            let is_root = plane.is_some() && key == root_key;
            if items.len() == 1 && items[0] == root_item && !is_root { continue; }
            let mut cells: Vec<u32> = vec![]; let mut pinl = vec![]; let (mut sx, mut sy, mut c) = (0.0, 0.0, 0.0);
            for &it in items {
                if it < np { let p = pads[it]; sx += p.x; sy += p.y; c += 1.0; pinl.push(format!("{}.{}", p.part, p.num));
                    for (l, nm) in inp.layers.iter().enumerate() { if r.routable[l] && p.on(nm) { cells.extend(pad_cells(&r, p, l)); } } }
                else if it < np + nz { let z = zones[it - np]; let mut m = g.empty(); for k in &z.cells { m.d[*k] = true; } let e = m.erode((0.2 * g.res) as f32);
                    let mut any = false; for k in (0..w * h).filter(|k| e.d[*k] && (k % 3 == 0)) { cells.push((z.layer * w * h + k) as u32); any = true; }
                    if any { let (mut ax, mut ay, mut n2) = (0.0, 0.0, 0.0); for k in z.cells.iter().step_by(17) { ax += g.x0 + (*k % w) as f64 / g.res; ay += g.y0 + (*k / w) as f64 / g.res; n2 += 1.0; } if n2 > 0.0 { sx += ax / n2; sy += ay / n2; c += 1.0; } } }
                else if it >= np + nz + nv && it < root_item { let t = tracks[it - np - nz - nv]; for q in t.path.windows(2) { let (a, b) = (r.cell(q[0]), r.cell(q[1])); let n3 = (b.0 - a.0).abs().max((b.1 - a.1).abs()).max(1); for i in 0..=n3 { let (x, y) = (a.0 + (b.0 - a.0) * i / n3, a.1 + (b.1 - a.1) * i / n3); if x >= 0 && y >= 0 && (x as usize) < w && (y as usize) < h { cells.push(r.idx(t.layer, x as usize, y as usize) as u32); } } sx += q[0].0; sy += q[0].1; c += 1.0; } }
                else if it < root_item { let v = vias[it - np - nz]; let (ux, uy) = r.cell((v.x, v.y)); sx += v.x; sy += v.y; c += 1.0;
                    if ux >= 0 && uy >= 0 && (ux as usize) < w && (uy as usize) < h { for l in (0..nl).filter(|l| r.routable[*l]) { cells.push(r.idx(l, ux as usize, uy as usize) as u32); } } }
            }
            pinl.sort(); pinl.dedup();
            groups.push(Group { cells, center: if c > 0.0 { (sx / c, sy / c) } else { (0.0, 0.0) }, pins: pinl, root: is_root });
        }
        // the first root: the plane, or the group of most copper
        let root_i = groups.iter().position(|q| q.root).unwrap_or_else(|| { let mut b = 0; for (i, q) in groups.iter().enumerate() { if q.cells.len() > groups[b].cells.len() { b = i; } } b });
        let mut on = vec![false; groups.len()]; if !on.is_empty() { on[root_i] = true; }
        nets.push(Net { id: idn(name), name: name.clone(), plane, power: inp.power.contains(name), groups, on, conns: vec![], reason: HashMap::new(), rips: 0, necked: 0 });
    }
    let opens = |nets: &[Net]| -> usize { nets.iter().map(|n| n.on.iter().filter(|o| !**o).count()).sum() };
    let total_conn = opens(&nets);
    log(format!("{} layers: {} nets, {} connections to close ({} planes: {:?})", nl, nets.len(), total_conn, inp.planes.len(), inp.planes));
    // order: plane fan-out early (short, and they must find a via near the pad), then power, then signals shortest first
    let hpwl = |n: &Net| { let (mut a, mut b, mut c, mut d) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN); for q in &n.groups { a = a.min(q.center.0); b = b.min(q.center.1); c = c.max(q.center.0); d = d.max(q.center.1); } (c - a) + (d - b) };
    let mut order: Vec<usize> = (0..nets.len()).filter(|i| nets[*i].on.iter().any(|o| !*o)).collect();
    // pins of fine-pitch parts go first of all: they have one way out, and anything nearby can close it
    let fine: HashSet<String> = inp.pads.iter().filter(|p| !p.net.is_empty() && p.w.min(p.h) <= 0.3).map(|p| p.net.clone()).collect();
    order.sort_by(|a, b| { let k = |i: usize| (if fine.contains(&nets[i].name) && nets[i].plane.is_none() && !nets[i].power { 0 } else if nets[i].plane.is_some() { 1 } else if nets[i].power { 2 } else { 3 }, hpwl(&nets[i]) as i64); k(*a).cmp(&k(*b)) });
    let mut best: Option<Snapshot> = None;
    let mut stalled = 0usize; let mut pass = 0usize; let mut stop = String::new();
    let mut queue: VecDeque<usize> = order.iter().copied().collect();
    let mut total_rips = 0u64;
    while pass < 40 {
        pass += 1;
        for n in nets.iter_mut() { n.rips = 0; }
        let budget = nets.len() * 4; let mut worked = 0;
        while let Some(ni) = queue.pop_front() {
            worked += 1; if worked > budget { queue.push_front(ni); break; }
            if t0.elapsed().as_secs_f64() > inp.seconds { queue.push_front(ni); break; }
            let mut attempt = 0;
            loop {
                attempt += 1;
                let closed = route_net(&mut r, &mut nets[ni]);
                if closed { break; }
                // rip up what stands in the way, once or twice per visit, a limited number of times per net
                if attempt > 3 || nets[ni].rips > 6 || std::env::var("ROUTE_NO_RIP").is_ok() { break; }
                nets[ni].rips += 1;
                let blockers = find_blockers(&mut r, &mut nets, ni);
                if blockers.is_empty() { break; }
                for (b, c) in blockers {
                    if b == ni { continue; }
                    total_rips += 1;
                    rip_conn(&mut r, &mut nets[b], c);
                    if !queue.contains(&b) { queue.push_back(b); }
                }
            }
        }
        let open_now = opens(&nets);
        let better = best.as_ref().map(|s| open_now < s.open).unwrap_or(true);
        log(format!("{} layers: pass {pass}, {open_now} open of {total_conn}, {total_rips} rip-ups, {:.0} s", nl, t0.elapsed().as_secs_f64()));
        if better {
            best = Some(Snapshot { open: open_now, conns: nets.iter().map(|n| n.conns.clone()).collect(), on: nets.iter().map(|n| n.on.clone()).collect(), reason: nets.iter().map(|n| n.reason.clone()).collect() });
            stalled = 0;
        } else { stalled += 1; }
        if open_now == 0 && queue.is_empty() { stop = "every connection closed".into(); break; }
        if t0.elapsed().as_secs_f64() > inp.seconds { stop = format!("time limit of {:.0} s", inp.seconds); break; }
        if stalled >= inp.stall { stop = format!("{stalled} passes closed nothing new: this stackup is the limit"); break; }
        // next pass: what is still open goes first
        let mut failed: Vec<usize> = (0..nets.len()).filter(|i| nets[*i].on.iter().any(|o| !*o)).collect();
        failed.retain(|i| !queue.contains(i));
        for i in failed.into_iter().rev() { queue.push_front(i); }
    }
    if stop.is_empty() { stop = "pass limit".into(); }
    let s = best.unwrap_or(Snapshot { open: opens(&nets), conns: vec![], on: vec![], reason: vec![] });
    // the result
    let mut traces = vec![]; let mut vias_out = vec![]; let mut failed = vec![];
    let mut per_layer = vec![0f64; nl]; let mut seen_mm = 0f64;
    for (i, n) in nets.iter().enumerate() {
        let live: Vec<Conn> = s.conns.get(i).cloned().unwrap_or_default().into_iter().filter(|c| c.alive).collect();
        let segs: Vec<Seg> = live.iter().flat_map(|c| c.segs.iter().cloned()).collect(); let vs: Vec<Via> = live.iter().flat_map(|c| c.vias.iter().cloned()).collect();
        let (on, why) = (s.on.get(i).cloned().unwrap_or_default(), s.reason.get(i).cloned().unwrap_or_default());
        for (k, q) in segs.iter().enumerate() {
            let len = crate::geom::dist(q.a, q.b); per_layer[q.l] += len;
            let steps = (len * g.res).ceil().max(1.0) as usize; let mut hit = 0;
            for t in 0..=steps { let f = t as f64 / steps as f64; let (cx, cy) = r.cell((q.a.0 + (q.b.0 - q.a.0) * f, q.a.1 + (q.b.1 - q.a.1) * f));
                if cx >= 0 && cy >= 0 && (cx as usize) < w && (cy as usize) < h && r.seen_factor(r.idx(q.l, cx as usize, cy as usize), n.id) > 1 { hit += 1; } }
            seen_mm += len * hit as f64 / (steps + 1) as f64;
            traces.push(json!({"id": format!("r-{}-{k}", n.name), "net": n.name, "layer": inp.layers[q.l], "width_mm": q.w, "path_mm": [[round3(q.a.0), round3(q.a.1)], [round3(q.b.0), round3(q.b.1)]], "tag": "INFERRED", "source": "router"}));
        }
        for (k, v) in vs.iter().enumerate() { vias_out.push(json!({"id": format!("rv-{}-{k}", n.name), "net": n.name, "kind": "router", "pos_mm": [round3(v.x), round3(v.y)], "diameter_mm": v.d, "drill_mm": v.h, "tag": "INFERRED", "source": "router"})); }
        for (gi, q) in n.groups.iter().enumerate() { if !on.get(gi).copied().unwrap_or(true) {
            // what fixed copper alone allows from here: no legal start, a pocket, or plenty of room
            let starts: Vec<usize> = q.cells.iter().map(|c| *c as usize).filter(|c| r.fixed.ok(*c, n.id)).collect();
            let mut seen_cells: HashSet<usize> = starts.iter().copied().collect(); let mut stack = starts.clone();
            while let Some(c) = stack.pop() { if seen_cells.len() > 40000 { break; } let (l, x, y) = r.un(c);
                for d in DIRS { let (nx, ny) = (x as i64 + d.0 as i64, y as i64 + d.1 as i64); if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 { continue; } let j = r.idx(l, nx as usize, ny as usize); if r.fixed.ok(j, n.id) && seen_cells.insert(j) { stack.push(j); } } }
            let room = seen_cells.len();
            let mut sites = 0usize; let vr = ring((rules.via.0 - rules.track) / 2.0, g.res);
            for c in seen_cells.iter().step_by(3) { let (_, x, y) = r.un(*c); if x % 2 == 0 && y % 2 == 0 && r.hole_ok(g.x0 + x as f64 / g.res, g.y0 + y as f64 / g.res, rules.via.1) && (0..nl).all(|l2| { let i = r.idx(l2, x, y); r.fixed.ok(i, n.id) && vr.iter().all(|o| { let (a, b) = (x as i64 + o.0 as i64, y as i64 + o.1 as i64); a >= 0 && b >= 0 && a < w as i64 && b < h as i64 && r.fixed.ok(r.idx(l2, a as usize, b as usize), n.id) }) }) { sites += 1; if sites > 50 { break; } } }
            failed.push(json!({"net": n.name, "pins": q.pins, "at_mm": [round3(q.center.0), round3(q.center.1)], "why": why.get(&gi).cloned().unwrap_or_default(), "legalStarts": starts.len(), "roomCells": room, "viaSites": sites}));
        } }
    }
    let layers_used: Vec<Value> = inp.layers.iter().enumerate().map(|(l, nm)| json!({"layer": nm, "plane": inp.planes.iter().find(|(_, v)| **v == l).map(|(k, _)| k.clone()), "trackMm": (per_layer[l] * 10.0).round() / 10.0})).collect();
    let necked: Vec<String> = nets.iter().filter(|n| n.necked > 0).map(|n| n.name.clone()).collect();
    json!({"layers": nl, "open": s.open, "connections": total_conn, "passes": pass, "ripups": total_rips, "stop": stop, "seconds": (t0.elapsed().as_secs_f64() * 10.0).round() / 10.0,
           "trackMm": (per_layer.iter().sum::<f64>() * 10.0).round() / 10.0, "vias": vias_out.len(), "seenCrossingMm": (seen_mm * 10.0).round() / 10.0, "layerUse": layers_used, "narrowedPower": necked,
           "failed": failed, "traces": traces, "routedVias": vias_out})
}

fn round3(v: f64) -> f64 { (v * 1000.0).round() / 1000.0 }

/// Mark everything of this net that is already connected as targets.
fn mark_targets(r: &mut R, net: &Net) -> usize {
    r.tgen = r.tgen.wrapping_add(1);
    if r.tgen == 0 { r.tgt.iter_mut().for_each(|v| *v = 0); r.tgen = 1; }
    let tg = r.tgen; let mut c = 0;
    for (gi, q) in net.groups.iter().enumerate() { if net.on[gi] { for &s in &q.cells { r.tgt[s as usize] = tg; c += 1; } } }
    let segs: Vec<Seg> = net.segs().cloned().collect(); let vias: Vec<Via> = net.vias().cloned().collect();
    for q in &segs {
        let (a, b) = (r.cell(q.a), r.cell(q.b));
        if a.0 < 0 || a.1 < 0 || b.0 < 0 || b.1 < 0 { continue; }
        let i0 = r.idx(q.l, a.0 as usize, a.1 as usize); r.tgt[i0] = tg; c += 1;
        if let Some(cells) = R::walk(a, b) { for p in cells { let i = r.idx(q.l, p.0 as usize, p.1 as usize); r.tgt[i] = tg; c += 1; } }
    }
    for v in &vias { let (x, y) = r.cell((v.x, v.y)); for l in 0..r.nl { if r.routable[l] { let i = r.idx(l, x as usize, y as usize); r.tgt[i] = tg; c += 1; } } }
    c
}

fn commit(r: &mut R, net: &mut Net, gi: usize, path: &[u32], w: f64, trk: &[(i32, i32)], via: (f64, f64)) {
    // split the path at layer changes
    let mut runs: Vec<(usize, Vec<(i64, i64)>)> = vec![];
    for &s in path { let (l, x, y) = r.un(s as usize); let c = (x as i64, y as i64);
        match runs.last_mut() { Some((rl, cells)) if *rl == l => cells.push(c), _ => runs.push((l, vec![c])) } }
    let mut new_segs = vec![]; let mut new_vias = vec![];
    for i in 0..runs.len() {
        let (l, cells) = (&runs[i].0, &runs[i].1);
        if i + 1 < runs.len() { let c = runs[i + 1].1[0]; let (x, y) = r.mm(c.0 as usize, c.1 as usize); new_vias.push(Via { x, y, d: via.0, h: via.1 }); }
        if r.routable[*l] && cells.len() >= 2 {
            let st = r.straighten(*l, cells, net.id, trk);
            for pair in st.windows(2) { let (a, b) = (r.mm(pair[0].0 as usize, pair[0].1 as usize), r.mm(pair[1].0 as usize, pair[1].1 as usize)); new_segs.push(Seg { l: *l, a, b, w }); }
        }
    }
    // what it landed on: a plane, a connection's copper, or a group
    let (gl, gx, gy) = r.un(*path.last().unwrap() as usize);
    let at = r.mm(gx, gy);
    let parent = if net.plane == Some(gl) { Parent::Plane } else {
        let hit = net.conns.iter().position(|c| c.alive && (c.segs.iter().any(|q| q.l == gl && point_seg(at, q.a, q.b) < 0.04) || c.vias.iter().any(|v| crate::geom::dist(at, (v.x, v.y)) < 0.04)));
        match hit { Some(c) => Parent::Conn(c), None => {
            let goal = *path.last().unwrap();
            let g = (0..net.groups.len()).find(|i| net.on[*i] && net.groups[*i].cells.contains(&goal)).unwrap_or(0);
            Parent::Group(g) } }
    };
    for q in &new_segs { r.add_seg(net.id, q, 1); }
    for v in &new_vias { r.add_via(net.id, v, 1); }
    net.conns.push(Conn { gi, parent, segs: new_segs, vias: new_vias, alive: true });
}

/// Close the open groups of a net. true when none is left open.
fn route_net(r: &mut R, net: &mut Net) -> bool {
    let rules = r.rules.clone();
    let (wide, via) = if net.power && net.plane.is_none() { (rules.power_track, rules.power_via) } else { (rules.track, rules.via) };
    let res = r.res;
    let narrow_via = rules.via;
    // a group that finds no path must not stop the rest of the net: each still gets its try
    let mut stuck: HashSet<usize> = HashSet::new();
    loop {
        let open: Vec<usize> = (0..net.groups.len()).filter(|i| !net.on[*i] && !stuck.contains(i)).collect();
        if open.is_empty() { return stuck.is_empty(); }
        // nearest open group to what is connected
        let anchors: Vec<(f64, f64)> = net.groups.iter().enumerate().filter(|(i, _)| net.on[*i]).map(|(_, q)| q.center).chain(net.vias().map(|v| (v.x, v.y))).collect();
        let dist = |gi: usize| anchors.iter().map(|a| crate::geom::dist(*a, net.groups[gi].center)).fold(f64::MAX, f64::min);
        let gi = open.iter().copied().min_by(|a, b| dist(*a).partial_cmp(&dist(*b)).unwrap()).unwrap();
        mark_targets(r, net);
        if net.plane.is_none() { r.distance_field(); }
        let srcs = net.groups[gi].cells.clone();
        let mut found = None;
        // a wide track first on a power net, then the narrow one where a pad's neighbours leave no room
        let tries: Vec<(f64, (f64, f64))> = if wide > rules.track + 1e-6 { vec![(wide, via), (rules.track, narrow_via)] } else { vec![(rules.track, via)] };
        for (ti, (tw, tv)) in tries.iter().enumerate() {
            let trk = ring((tw - rules.track) / 2.0, res);
            let vr = ring((tv.0 - rules.track) / 2.0, res);
            let limit = if net.plane.is_some() { 800_000 } else if ti + 1 < tries.len() { 200_000 } else { 1_200_000 };
            if let Some(p) = r.search(net.id, net.plane, net.power, &srcs, &trk, &vr, tv.1, false, limit) { found = Some((p, *tw, trk, *tv, ti)); break; }
        }
        match found {
            Some((p, tw, trk, tv, ti)) => {
                if ti > 0 { net.necked += 1; }
                commit(r, net, gi, &p, tw, &trk, tv);
                net.on[gi] = true; net.reason.remove(&gi);
            }
            None => { net.reason.insert(gi, "no path among copper already placed".into()); stuck.insert(gi); }
        }
    }
}

/// Take one connection up, and whatever landed on it or on the group it brought in.
fn rip_conn(r: &mut R, net: &mut Net, c: usize) {
    if !net.conns[c].alive { return; }
    let mut stack = vec![c];
    while let Some(k) = stack.pop() {
        if !net.conns[k].alive { continue; }
        net.conns[k].alive = false;
        let segs = net.conns[k].segs.clone(); let vias = net.conns[k].vias.clone(); let gi = net.conns[k].gi;
        for q in &segs { r.add_seg(net.id, q, -1); }
        for v in &vias { r.add_via(net.id, v, -1); }
        net.on[gi] = false;
        for j in 0..net.conns.len() { if net.conns[j].alive && (net.conns[j].parent == Parent::Conn(k) || net.conns[j].parent == Parent::Group(gi)) { stack.push(j); } }
    }
}

/// Search again for the first open group, walking through routed copper at a cost: the nets on that path stand in the way.
fn find_blockers(r: &mut R, nets: &mut [Net], ni: usize) -> Vec<(usize, usize)> {
    let rules = r.rules.clone();
    let open: Vec<usize> = (0..nets[ni].groups.len()).filter(|i| !nets[ni].on[*i]).collect();
    if open.is_empty() { return vec![]; }
    // each visit tries a different stuck group
    let gi = open[nets[ni].rips as usize % open.len()];
    mark_targets(r, &nets[ni]);
    if nets[ni].plane.is_none() { r.distance_field(); }
    let srcs = nets[ni].groups[gi].cells.clone();
    let vr = ring((rules.via.0 - rules.track) / 2.0, r.res);
    let Some(p) = r.search(nets[ni].id, nets[ni].plane, nets[ni].power, &srcs, &[], &vr, rules.via.1, true, 1_500_000) else {
        nets[ni].reason.insert(gi, "walled in by copper seen on the photos (pads, known pours, vias)".into());
        return vec![];
    };
    // tiles on the path get dearer
    for &s in &p { let (l, x, y) = r.un(s as usize); let t = r.tile(x, y, l); r.hist[t] = r.hist[t].saturating_add(1); }
    let mut who: HashSet<(usize, usize)> = HashSet::new();
    let mut prev: Option<usize> = None;
    for &s in &p {
        let (l, x, y) = r.un(s as usize);
        let i = s as usize;
        let changed = prev.map(|pl| pl != l).unwrap_or(false); prev = Some(l);
        if r.routed.ok(i, nets[ni].id) && !changed { continue; }
        let at = r.mm(x, y);
        let extra = if changed { rules.via.0 / 2.0 } else { rules.track / 2.0 };
        for (oi, o) in nets.iter().enumerate() {
            if oi == ni { continue; }
            for (ci, c) in o.conns.iter().enumerate() {
                if !c.alive || who.contains(&(oi, ci)) { continue; }
                let hit = c.segs.iter().any(|q| (q.l == l || changed) && point_seg(at, q.a, q.b) <= q.w / 2.0 + rules.clr + extra + MARGIN)
                    || c.vias.iter().any(|v| crate::geom::dist(at, (v.x, v.y)) <= v.d / 2.0 + rules.clr + extra + MARGIN);
                if hit { who.insert((oi, ci)); }
            }
        }
    }
    let mut v: Vec<(usize, usize)> = who.into_iter().collect(); v.sort(); v
}

#[cfg(test)]
mod tests {
    use super::*;
    fn pad(part: &str, x: f64, y: f64, net: &str) -> Pad { Pad { part: part.into(), num: "1".into(), x, y, w: 1.0, h: 1.0, rot: 0.0, round: false, drill: 0.0, layers: vec!["F.Cu".into()], net: net.into() } }
    fn rules() -> Rules { Rules { clr: 0.2, track: 0.2, power_track: 0.5, via: (0.6, 0.3), power_via: (0.8, 0.4), edge: 0.5, hole_clr: 0.25, hole_hole: 0.25 } }
    fn board(w: f64, h: f64) -> (Grid, Mask) { let g = Grid { x0: 0.0, y0: 0.0, res: 20.0, w: (w * 20.0) as usize + 1, h: (h * 20.0) as usize + 1 }; let mut m = g.empty(); g.poly(&mut m, &[(0.0, 0.0), (w, 0.0), (w, h), (0.0, h)]); (g, m) }
    fn wall(g: &Grid, net: &str, layer: usize, x0: f64, x1: f64) -> ZoneIn { let mut cells = vec![]; for v in 0..g.h { for u in 0..g.w { let x = u as f64 / g.res; if x >= x0 && x <= x1 { cells.push(v * g.w + u); } } } ZoneIn { id: format!("z{layer}"), net: net.into(), layer, cells } }
    fn go(pads: &[Pad], layers: &[&str], planes: &[(&str, usize)], zones: Vec<ZoneIn>, g: &Grid, m: &Mask) -> Value {
        let inp = Input { pads, layers: layers.iter().map(|s| s.to_string()).collect(), planes: planes.iter().map(|(a, b)| (a.to_string(), *b)).collect(), inside: m, grid: g, zones, vias: vec![], tracks: vec![], groups: vec![], rules: rules(), power: HashSet::new(), seconds: 30.0, stall: 2 };
        run(&inp, &mut |_| {})
    }
    #[test]
    fn straight_connection_on_one_layer() {
        let (g, m) = board(10.0, 6.0);
        let o = go(&[pad("A", 2.0, 3.0, "S"), pad("B", 8.0, 3.0, "S")], &["F.Cu", "B.Cu"], &[], vec![], &g, &m);
        assert_eq!(o["open"], json!(0));
        assert_eq!(o["vias"], json!(0));
        assert!(o["trackMm"].as_f64().unwrap() < 6.5, "{o}");
    }
    #[test]
    fn a_track_changes_layer_rather_than_cross_a_wide_pour_of_another_net() {
        // a wide pour of another net: going under it through two vias is cheaper than twelve times its width
        let (g, m) = board(14.0, 6.0);
        let z = vec![wall(&g, "OTHER", 0, 4.0, 10.0)];
        let o = go(&[pad("A", 2.0, 3.0, "S"), pad("B", 12.0, 3.0, "S")], &["F.Cu", "B.Cu"], &[], z, &g, &m);
        assert_eq!(o["open"], json!(0));
        assert_eq!(o["vias"], json!(2), "{o}");
        assert!(o["seenCrossingMm"].as_f64().unwrap() < 0.5, "{o}");
    }
    #[test]
    fn a_plane_net_needs_only_a_via_per_pin() {
        let (g, m) = board(10.0, 6.0);
        let o = go(&[pad("A", 2.0, 3.0, "GND"), pad("B", 8.0, 3.0, "GND")], &["F.Cu", "In1.Cu", "In2.Cu", "B.Cu"], &[("GND", 1)], vec![], &g, &m);
        assert_eq!(o["open"], json!(0));
        assert_eq!(o["vias"], json!(2), "{o}");
        assert!(o["trackMm"].as_f64().unwrap() < 1.0, "the plane carries the current, not a track: {o}");
    }
    #[test]
    fn inner_layers_carry_signals_when_the_outer_are_covered() {
        // wide pours of other nets on both outer layers: two layers must cross one; four go under on an inner layer
        let (g, m) = board(16.0, 6.0);
        let w2 = |l| wall(&g, "OTHER", l, 4.0, 12.0);
        let two = go(&[pad("A", 2.0, 3.0, "S"), pad("B", 14.0, 3.0, "S")], &["F.Cu", "B.Cu"], &[], vec![w2(0), w2(1)], &g, &m);
        assert_eq!(two["open"], json!(0));
        assert!(two["seenCrossingMm"].as_f64().unwrap() > 7.0, "two layers have to cross: {two}");
        let four = go(&[pad("A", 2.0, 3.0, "S"), pad("B", 14.0, 3.0, "S")], &["F.Cu", "In1.Cu", "In2.Cu", "B.Cu"], &[], vec![w2(0), w2(3)], &g, &m);
        assert_eq!(four["open"], json!(0), "{four}");
        assert!(four["seenCrossingMm"].as_f64().unwrap() < 0.5, "{four}");
        let inner: f64 = four["layerUse"].as_array().unwrap().iter().filter(|u| u["layer"].as_str().unwrap().starts_with("In")).map(|u| u["trackMm"].as_f64().unwrap()).sum();
        assert!(inner > 5.0, "{four}");
    }
    #[test]
    fn a_narrow_gap_between_fine_pads_is_found() {
        // 0.5 mm pitch pads, 0.25 wide: only the column straight below the pad clears both neighbours at 0.2 + 0.2
        let (g, m) = board(8.0, 6.0);
        let fine = |n: &str, x: f64, net: &str| Pad { part: "U".into(), num: n.into(), x, y: 2.0, w: 0.25, h: 0.8, rot: 0.0, round: false, drill: 0.0, layers: vec!["F.Cu".into()], net: net.into() };
        let pads = vec![fine("1", 3.5, "A"), fine("2", 4.0, "S"), fine("3", 4.5, "B"), pad("X", 4.0, 5.0, "S")];
        let o = go(&pads, &["F.Cu", "B.Cu"], &[], vec![], &g, &m);
        assert_eq!(o["open"], json!(0), "{o}");
    }
    #[test]
    fn rip_up_restores_the_keep_out_exactly() {
        let (g, m) = board(10.0, 6.0);
        let mut f = Field::new(g.w * g.h);
        f.add(10, 5, 1); f.add(10, 7, 1); assert!(!f.ok(10, 5)); assert!(!f.ok(10, 6), "two nets never read as a third");
        f.add(10, 7, -1); assert!(f.ok(10, 5)); assert!(!f.ok(10, 7));
        f.add(10, 5, -1); assert!(f.ok(10, 7));
        let _ = m;
    }
}