AI Flow

//! The search and the driver: A* per connection, a net as a spanning tree onto its own copper,
//! rip-up when a connection fails, plane stubs, Kelvin taps, passes, and the plan.
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};

use aiflow_board::{geom, B_CU, F_CU};
use aiflow_grid::RES;
use serde_json::{json, Value};

use crate::{slop, turn_cost, End, NetState, Route, Router, Snapshot, Term, COST_VIA, DIRS, HIST_COST, INF, JUMPER_COST, JUMPER_LAYER_MULT, LAYER_MULT, PAIR_OFF, SOFT_EXTRA, STEP, VIA_WALL, ZONE_COST};

pub type Win = (i64, i64, i64, i64);

pub struct Search<'a> {
    pub sources: Vec<(Term, i64)>,
    pub targets: Option<&'a HashSet<Term>>,
    pub heur: Vec<(i64, i64)>,
    pub win: Win,
    pub allow_via: bool,
    pub soft: bool,
    pub via_target: bool,
    pub max_nodes: Option<usize>,
    pub vip: Vec<Term>,
}

// Existing copper is in via_ok. Also check layer transitions in this unfinished path.
fn path_vias_clear(n: usize, parent: &[usize], layer_cells: usize, width: usize, gap_mm: f64) -> bool {
    let m = n % layer_cells;
    let mut cursor = n;
    while parent[cursor] != usize::MAX {
        let prev = parent[cursor];
        if cursor / layer_cells != prev / layer_cells {
            let via = cursor % layer_cells;
            let dx = (m % width) as f64 - (via % width) as f64;
            let dy = (m / width) as f64 - (via / width) as f64;
            if dx.hypot(dy) * RES < gap_mm { return false; }
        }
        cursor = prev;
    }
    true
}

impl Router {
    /// A* from sources to targets over the window. Returns (cells, blockers).
    pub fn search(&mut self, net: usize, width: f64, mut s: Search) -> (Option<Vec<Term>>, HashSet<usize>) {
        // the window inside the grid, whoever built it (issue #140)
        let (wx, hy) = (self.grid.w as i64 - 1, self.grid.h as i64 - 1);
        let (a, b) = (s.win.0.clamp(0, wx), s.win.1.clamp(0, hy));
        s.win = (a, b, s.win.2.clamp(a, wx), s.win.3.clamp(b, hy));
        let (i0, j0, i1, j1) = s.win;
        let ww = (i1 - i0 + 1) as usize;
        let hw = (j1 - j0 + 1) as usize;
        let nl = ww * hw;
        let (obs_o, obs_d, softm, via_ok) = self.obstacle_maps(net, width, s.win, s.soft);
        let guide = self.pair_guide(net, s.win);
        let g = self.grid.clone();
        // zone, wall, history windows
        let mut zone = vec![false; nl];
        let mut wall = vec![0i64; nl];
        let mut hist = [vec![0i64; nl], vec![0i64; nl]];
        for jj in 0..hw {
            for ii in 0..ww {
                let c = (j0 as usize + jj) * g.w + i0 as usize + ii;
                zone[jj * ww + ii] = self.ic_zone.bits[c];
                wall[jj * ww + ii] = self.chan_count[c] as i64;
                hist[0][jj * ww + ii] = (self.history[0][c] as i64).clamp(0, 40);
                hist[1][jj * ww + ii] = (self.history[1][c] as i64).clamp(0, 40);
            }
        }
        let nid = self.nets[net].idx;
        for ((n, _, _), cells) in &self.chan_lines {
            if *n == nid {
                for &c in cells {
                    let (cj, ci) = ((c / g.w) as i64, (c % g.w) as i64);
                    if cj >= j0 && cj <= j1 && ci >= i0 && ci <= i1 {
                        wall[(cj - j0) as usize * ww + (ci - i0) as usize] -= 1;
                    }
                }
            }
        }
        for w in wall.iter_mut() {
            *w = (*w).clamp(0, 60);
        }
        let mut tgt = vec![false; 2 * nl];
        let vipset: HashSet<usize> = s.vip.iter().filter(|t| t.i as i64 >= i0 && t.i as i64 <= i1 && t.j as i64 >= j0 && t.j as i64 <= j1).map(|t| (t.j as i64 - j0) as usize * ww + (t.i as i64 - i0) as usize).collect();
        if s.via_target {
            // a via site on the sources' layer: F.Cu, or B.Cu when every source is a bottom pad's (issue #139)
            let vl = if !s.sources.is_empty() && s.sources.iter().all(|(t, _)| t.layer() == B_CU) { B_CU } else { F_CU };
            for m in 0..nl {
                if via_ok.bits[m] && !obs_o[vl].bits[m] {
                    tgt[vl * nl + m] = true;
                }
            }
        }
        if let Some(targets) = s.targets {
            for t in targets {
                if t.i as i64 >= i0 && t.i as i64 <= i1 && t.j as i64 >= j0 && t.j as i64 <= j1 {
                    tgt[t.layer() * nl + (t.j as i64 - j0) as usize * ww + (t.i as i64 - i0) as usize] = true;
                }
            }
        }
        if !tgt.iter().any(|b| *b) {
            return (None, HashSet::new());
        }
        let mut gcost = vec![INF; 2 * nl];
        let mut parent = vec![usize::MAX; 2 * nl];
        let mut pdir = vec![-1i8; 2 * nl];
        let mut closed = vec![false; 2 * nl];
        let mut heap: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
        let hp: Vec<(i64, i64)> = s.heur.iter().map(|(i, j)| (i - i0, j - j0)).collect();
        let h = |il: i64, jl: i64| -> i64 {
            if hp.is_empty() {
                return 0;
            }
            hp.iter().map(|(hi, hj)| { let dx = (hi - il).abs(); let dy = (hj - jl).abs(); 10 * dx.max(dy) + 4 * dx.min(dy) }).min().unwrap()
        };
        // issue #183: with both layers and no vias, the jumper layer (F.Cu) is a wire on the component
        // side: entering it costs JUMPER_COST, so a connection takes a jumper only when the milled face
        // has no way through
        let jumper = self.rules.jumper_layer();
        let layer_mult: [f64; 2] = if jumper.is_some() { JUMPER_LAYER_MULT } else { LAYER_MULT };
        for (t, c0) in &s.sources {
            let c0 = &(c0 + if jumper == Some(t.layer()) { JUMPER_COST } else { 0 });
            let (i, j) = (t.i as i64, t.j as i64);
            if !(i >= i0 && i <= i1 && j >= j0 && j <= j1) {
                continue;
            }
            let m = (j - j0) as usize * ww + (i - i0) as usize;
            let n = t.layer() * nl + m;
            if obs_o[t.layer()].bits[m] {
                continue;
            }
            if *c0 < gcost[n] {
                gcost[n] = *c0;
                heap.push(Reverse((c0 + h(i - i0, j - j0), n)));
            }
        }
        let flat_turns = self.flat_turns;
        let mut expanded = 0usize;
        let mut found: Option<usize> = None;
        while let Some(Reverse((_, n))) = heap.pop() {
            if closed[n] {
                continue;
            }
            closed[n] = true;
            if tgt[n] {
                found = Some(n);
                break;
            }
            expanded += 1;
            if let Some(cap) = s.max_nodes {
                if expanded > cap {
                    break;
                }
            }
            let l = n / nl;
            let m = n - l * nl;
            let jl = (m / ww) as i64;
            let il = (m % ww) as i64;
            let gn = gcost[n];
            let pd = pdir[n];
            let mult = layer_mult[l];
            for d in 0..8 {
                let ni = il + DIRS[d].0 as i64;
                let nj = jl + DIRS[d].1 as i64;
                if ni < 0 || nj < 0 || ni >= ww as i64 || nj >= hw as i64 {
                    continue;
                }
                let nm = nj as usize * ww + ni as usize;
                if obs_o[l].bits[nm] {
                    continue;
                }
                if d >= 4 && obs_d[l].bits[nm] && obs_d[l].bits[m] {
                    continue;
                }
                let nn = l * nl + nm;
                if closed[nn] {
                    continue;
                }
                let mut c = (STEP[d] as f64 * mult) as i64;
                if pd != -1 {
                    c += turn_cost(pd as usize, d, flat_turns);
                }
                if let Some(sm) = &softm[l] {
                    if sm.bits[nm] {
                        c += SOFT_EXTRA;
                    }
                }
                if l == F_CU && zone[nm] {
                    c += ZONE_COST;
                }
                if hist[l][nm] > 0 {
                    c += HIST_COST * hist[l][nm];
                }
                if let Some((gl, gm)) = &guide {
                    if *gl == l && !gm[nm] {
                        c += PAIR_OFF;
                    }
                }
                let ng = gn + c;
                if ng < gcost[nn] {
                    gcost[nn] = ng;
                    parent[nn] = n;
                    pdir[nn] = d as i8;
                    heap.push(Reverse((ng + h(ni, nj), nn)));
                }
            }
            if s.allow_via && (via_ok.bits[m] || vipset.contains(&m))
                && path_vias_clear(n, &parent, nl, ww, self.nets[net].drill + self.rules.hole_to_hole + slop()) {

                let l2 = 1 - l;
                if !obs_o[l2].bits[m] {
                    let nn = l2 * nl + m;
                    if !closed[nn] {
                        let ng = gn + COST_VIA + VIA_WALL * wall[m] + if jumper == Some(l2) { JUMPER_COST } else { 0 };
                        if ng < gcost[nn] {
                            gcost[nn] = ng;
                            parent[nn] = n;
                            pdir[nn] = -1;
                            heap.push(Reverse((ng + h(il, jl), nn)));
                        }
                    }
                }
            }
        }
        self.stat("expanded", expanded as i64);
        let Some(mut n) = found else { return (None, HashSet::new()) };
        let mut cells = Vec::new();
        loop {
            let l = n / nl;
            let m = n - l * nl;
            cells.push(Term::new(l, (m % ww) as i64 + i0, (m / ww) as i64 + j0));
            if parent[n] == usize::MAX {
                break;
            }
            n = parent[n];
        }
        cells.reverse();
        let mut blockers = HashSet::new();
        if s.soft {
            let r = ((self.rules.clearance + width / 2.0 + slop()) / RES).ceil() as i64 + 1;
            for t in &cells {
                if let Some(sm) = &softm[t.layer()] {
                    let m = (t.j as i64 - j0) as usize * ww + (t.i as i64 - i0) as usize;
                    if sm.bits[m] {
                        for jj in (t.j as i64 - r).max(0)..=(t.j as i64 + r).min(g.h as i64 - 1) {
                            for ii in (t.i as i64 - r).max(0)..=(t.i as i64 + r).min(g.w as i64 - 1) {
                                let v = self.route_raw[t.layer()][jj as usize * g.w + ii as usize];
                                if v != -1 && v as usize != nid {
                                    blockers.insert(v as usize);
                                }
                            }
                        }
                    }
                }
            }
        }
        (Some(cells), blockers)
    }

    // -- per net -----------------------------------------------------------------------
    pub fn window_for(&self, pts: &[(i64, i64)], margin_mm: f64) -> Win {
        let m = (margin_mm / RES).round() as i64;
        let xs: Vec<i64> = pts.iter().map(|p| p.0).collect();
        let ys: Vec<i64> = pts.iter().map(|p| p.1).collect();
        // every bound inside the grid (issue #140: a point off the grid, a part outside the outline, made a
        // window past the grid's end and obstacle_maps indexed out of bounds); search skips any source or
        // target outside the window
        let (wx, hy) = (self.grid.w as i64 - 1, self.grid.h as i64 - 1);
        ((xs.iter().min().unwrap() - m).clamp(0, wx), (ys.iter().min().unwrap() - m).clamp(0, hy), (xs.iter().max().unwrap() + m).clamp(0, wx), (ys.iter().max().unwrap() + m).clamp(0, hy))
    }

    pub fn copper_targets(&self, net: usize) -> HashSet<Term> {
        let mut t = HashSet::new();
        for c in &self.nets[net].clusters {
            if c.connected && !self.kelvin_clusters.contains(&(net, c.idx)) {
                t.extend(c.terminals.iter().copied());   // a sense pad is never a landing target either
            }
        }
        for r in &self.nets[net].routes {
            if r.kelvin {
                continue;   // a Kelvin tap is not copper the rest of its net may land on
            }
            if !self.pair_route_joined(net, r) {
                continue;   // a decoupling pair not yet joined to the tree is an island, not tree copper
            }
            t.extend(r.cells.iter().copied());
        }
        // the board's own copper of every group already joined to the tree
        if let Some(cells) = self.fixed_targets.get(&net) {
            let joined: HashSet<usize> = (0..self.nets[net].clusters.len()).filter(|&c| self.nets[net].clusters[c].connected).map(|c| self.comp_of(net, c)).collect();
            t.extend(cells.iter().filter(|(g, _)| joined.contains(g)).map(|(_, c)| *c));
        }
        t
    }

    fn vip_cells(&mut self, net: usize, clusters: &[usize]) -> Vec<Term> {
        let mut out = Vec::new();
        for &c in clusters {
            let cl = self.nets[net].clusters[c].clone();
            if self.board.pads[cl.primary].thru || !cl.escapes.is_empty() {
                continue;
            }
            for t in cl.terminals {
                if t.layer() == F_CU {
                    let (x, y) = self.grid.to_xy(t.i as i64, t.j as i64);
                    if self.via_clear_exact(net, x, y) {
                        out.push(t);
                    }
                }
            }
        }
        out
    }

    pub fn connect(&mut self, net: usize, cluster: usize, anchor: &[(i64, i64)], soft: bool, vip: bool) -> (Option<Route>, HashSet<usize>) {
        let mut targets = self.copper_targets(net);
        let cl = self.nets[net].clusters[cluster].clone();
        let mut sources: Vec<(Term, i64)> = cl.terminals.iter().map(|t| (*t, 0)).collect();
        // a cluster the board's own copper already reaches may leave from anywhere on that copper
        if let Some(cells) = self.fixed_targets.get(&net) {
            let group = self.comp_of(net, cluster);
            sources.extend(cells.iter().filter(|(g, t)| *g == group && !targets.contains(t)).map(|(_, t)| (*t, 0)));
        }
        let allow = cl.allow;
        let mut widths: Vec<f64> = self.nets[net].widths.iter().copied().filter(|w| *w <= allow).collect();
        if widths.is_empty() {
            widths = vec![self.nets[net].widths.iter().cloned().fold(f64::INFINITY, f64::min)];
        }
        let mut allpts: Vec<(i64, i64)> = cl.terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
        allpts.extend_from_slice(anchor);
        let mut vip_src = Vec::new();
        let vip = vip && self.rules.vias_allowed();   // issue #183: via-in-pad is a via
        if vip {
            vip_src = self.vip_cells(net, &[cluster]);
            let connected: Vec<usize> = self.nets[net].clusters.iter().filter(|c| c.connected).map(|c| c.idx).collect();
            for t in self.vip_cells(net, &connected) {
                targets.insert(Term::new(B_CU, t.i as i64, t.j as i64));
            }
        }
        let stages: Vec<(f64, Option<usize>)> = if soft || vip { vec![(12.0, Some(200_000))] } else { vec![(5.0, None), (12.0, None), (80.0, Some(250_000))] };
        for width in widths {
            for (margin, cap) in &stages {
                let win = self.window_for(&allpts, *margin);
                let (cells, blockers) = self.search(net, width, Search { sources: sources.clone(), targets: Some(&targets), heur: anchor.to_vec(), win, allow_via: true, soft, via_target: false, max_nodes: *cap, vip: vip_src.clone() });
                if let Some(cells) = cells {
                    let start_term = cells[0];
                    let end_cell = *cells.last().unwrap();
                    let from_pad = cl.terminals.contains(&start_term);
                    let start = if cl.escapes.contains_key(&start_term) { End::Escape(cluster, start_term) } else if from_pad { End::Pad(cluster, start_term) } else { End::Copper };
                    let mut end = End::Copper;
                    for c in &self.nets[net].clusters {
                        if c.connected && (c.terminals.contains(&end_cell) || (end_cell.layer() == B_CU && c.terminals.contains(&Term::new(F_CU, end_cell.i as i64, end_cell.j as i64)) && targets.contains(&end_cell))) {
                            end = if c.escapes.contains_key(&end_cell) { End::Escape(c.idx, end_cell) } else { End::Pad(c.idx, end_cell) };
                        }
                    }
                    let mut route = Route::new(cells.clone(), width, start, end.clone());
                    if let End::Pad(ec, _) = end {
                        // issue #139: a via only where the end pad has no copper on the arriving layer (a
                        // top pad reached on B.Cu through via-in-pad); a bottom part's pad reached on B.Cu
                        // is already joined, and a via there put the path's end on F.Cu, where it has none
                        let ep = &self.board.pads[self.nets[net].clusters[ec].primary];
                        if !ep.thru && !ep.on_layer(end_cell.layer()) && self.rules.vias_allowed() {
                            route.via_end = true;
                            route.via_end_layer = if ep.on_f { F_CU } else { B_CU };
                            self.stat("viaInPad", 1);
                            let key = self.nets[net].clusters[ec].key(&self.board).to_string();
                            self.nets[net].via_in_pad.push(key);
                        }
                    }
                    if from_pad && cells.len() > 1 && (cells[0].i, cells[0].j) == (cells[1].i, cells[1].j) && cells[0].layer() != cells[1].layer() && !self.board.pads[cl.primary].thru {
                        self.stat("viaInPad", 1);
                        let key = cl.key(&self.board).to_string();
                        self.nets[net].via_in_pad.push(key);
                    }
                    return (Some(route), blockers);
                }
            }
        }
        (None, HashSet::new())
    }

    /// Prim's order over clusters; each cluster to the existing copper. Returns blocker net ids on failure.
    pub fn route_net(&mut self, net: usize) -> HashSet<usize> {
        let n = self.nets[net].clusters.len();
        for c in 0..n {
            self.nets[net].clusters[c].connected = false;
        }
        self.nets[net].routes.retain(|r| r.pair.is_some());   // decoupling pairs stay (decoupling.rs)
        self.nets[net].failed.clear();
        self.nets[net].last_soft.clear();
        let start = (0..n).max_by(|&a, &b| {
            let ca = &self.nets[net].clusters[a];
            let cb = &self.nets[net].clusters[b];
            let pa = &self.board.pads[ca.primary];
            let pb = &self.board.pads[cb.primary];
            (ca.allow, pa.half_long * pa.half_short).partial_cmp(&(cb.allow, pb.half_long * pb.half_short)).unwrap()
        }).unwrap();
        // the start and every cluster the board's own copper already joins to it
        let mut connected = self.join_with_pairs(net, start);
        let mut remaining: Vec<usize> = (0..n).filter(|c| !connected.contains(c)).collect();
        let mut blockers_all = HashSet::new();
        // Kelvin taps first: sense pad to shunt pad as a dedicated trace
        let kelvin = self.rules.kelvin.clone();
        for c in remaining.clone() {
            let key = self.nets[net].clusters[c].key(&self.board).to_string();
            if self.joined_by_board(net, c) {
                continue;   // a sense pad the board's copper already reaches keeps that copper
            }
            if let Some(dst_key) = kelvin.get(&key) {
                let dst = self.nets[net].clusters.iter().position(|k| k.key(&self.board) == dst_key);
                let Some(dst) = dst else { continue };
                if self.route_kelvin(net, c, dst) {
                    // the sense pad is done; the shunt pad still joins the rest of the net through
                    // the wide path (the tap itself is never a landing target, see copper_targets)
                    remaining.retain(|&x| x != c);
                } else {
                    let dk = self.nets[net].clusters[dst].key(&self.board).to_string();
                    self.nets[net].failed.push((key, format!("kelvin tap to {dk} found no dedicated path")));
                    remaining.retain(|&x| x != c);
                }
            }
        }
        while !remaining.is_empty() {
            let mut best: Option<(f64, usize, usize)> = None;
            for &c in &remaining {
                for &k in &connected {
                    let a = self.nets[net].clusters[c].xy(&self.board);
                    let b = self.nets[net].clusters[k].xy(&self.board);
                    let d = (a.0 - b.0).hypot(a.1 - b.1);
                    if best.map(|x| d < x.0).unwrap_or(true) {
                        best = Some((d, c, k));
                    }
                }
            }
            let (_, c, k) = best.unwrap();
            remaining.retain(|&x| x != c);
            let anchor: Vec<(i64, i64)> = self.nets[net].clusters[k].terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
            let (mut route, _) = self.connect(net, c, &anchor, false, false);
            if route.is_none() && self.rules.vias_allowed() {
                route = self.connect(net, c, &anchor, false, true).0;
            }
            match route {
                None => {
                    let (soft_route, blockers) = self.connect(net, c, &anchor, true, false);
                    blockers_all.extend(blockers.iter().copied());
                    if let Some(sr) = soft_route {
                        self.nets[net].last_soft.extend(sr.cells.iter().copied());
                    }
                    let key = self.nets[net].clusters[c].key(&self.board).to_string();
                    let why = if let Some(w) = self.off_layer_reason(net, c).or_else(|| self.off_layer_reason(net, k)) { w } else if blockers.is_empty() { if self.rules.default_copper_mode() { "no path".to_string() } else { format!("no path {}", self.mode_words()) } } else {
                        let mut names: Vec<String> = blockers.iter().map(|&b| self.name_of(b)).collect();
                        names.sort();
                        format!("blocked by {names:?}")
                    };
                    self.nets[net].failed.push((key, why));
                    self.nets[net].clusters[c].connected = false;
                }
                Some(r) => {
                    self.commit(net, r);
                    for k in self.join_with_pairs(net, c) {
                        if !connected.contains(&k) {
                            connected.push(k);
                        }
                        remaining.retain(|&x| x != k);
                    }
                }
            }
        }
        blockers_all
    }

    /// Issue #183: why a cluster cannot be reached in single-face mode: its pad has copper only on a
    /// layer the router may not use. None when the pad is reachable (or in the default mode).
    pub fn off_layer_reason(&self, net: usize, c: usize) -> Option<String> {
        if self.rules.default_copper_mode() { return None; }
        let p = &self.board.pads[self.nets[net].clusters[c].primary];
        if p.thru || (0..2).any(|l| p.on_layer(l) && self.rules.layer_allowed(l)) { return None; }
        let on = if p.on_f { "F.Cu" } else { "B.Cu" };
        Some(format!("pad {} has copper only on {on}, a layer this board does not route (routeLayers {}); allow {on}, or use a through-hole part there", p.key, self.mode_layers().join(" + ")))
    }

    /// The layers the router may use, by name.
    pub fn mode_layers(&self) -> Vec<&'static str> {
        (0..2).filter(|&l| self.rules.layer_allowed(l)).map(|l| aiflow_board::LAYER_NAMES[l]).collect()
    }

    /// "on B.Cu alone, no vias" or "on B.Cu with F.Cu jumpers, no vias".
    pub fn mode_words(&self) -> String {
        match self.rules.jumper_layer() {
            Some(j) => format!("on {} with {} jumpers, no vias", aiflow_board::LAYER_NAMES[1 - j], aiflow_board::LAYER_NAMES[j]),
            None if !self.rules.vias_allowed() => format!("on {} alone, no vias", self.mode_layers().join(" + ")),
            None => String::new(),
        }
    }

    pub fn name_of(&self, nid: usize) -> String {
        if let Some(&owner) = self.kelvin_owner.get(&nid) {
            return self.nets[owner].name.clone();
        }
        self.nets.iter().find(|n| n.idx == nid).map(|n| n.name.clone()).unwrap_or_else(|| "?".into())
    }

    pub fn commit(&mut self, net: usize, route: Route) {
        let end = *route.cells.last().unwrap();
        for r in self.nets[net].routes.iter_mut() {
            if let Some(pos) = r.cells.iter().position(|c| *c == end) {
                r.breaks.insert(pos);
            }
        }
        for e in [&route.start, &route.end] {
            if let End::Escape(c, t) = e {
                self.nets[net].used_escapes.insert((*c, *t));
            }
        }
        self.stamp_route(net, &route, 1);
        let ends = [route.start.clone(), route.end.clone()];
        self.nets[net].routes.push(route);
        for e in ends {
            match e {
                End::Escape(c, t) => {
                    self.release_escapes(net, c);
                    self.stamp_channel_pub(net, c, t, -1);
                }
                End::Pad(c, _) => self.release_escapes(net, c),
                _ => {}
            }
        }
    }

    pub fn stamp_channel_pub(&mut self, net: usize, c: usize, t: Term, sign: i32) {
        // the channel bookkeeping lives in lib.rs; re-expose through stamp_stub's helper
        let key = (self.nets[net].idx, c, t);
        if sign < 0 {
            if let Some(cells) = self.chan_lines.remove(&key) {
                for cell in cells {
                    self.chan_count[cell] -= 1;
                }
            }
        }
    }

    pub fn release_escapes(&mut self, net: usize, cluster: usize) {
        let escapes: Vec<Term> = self.nets[net].clusters[cluster].escapes.keys().copied().collect();
        for t in escapes {
            let used = self.nets[net].used_escapes.contains(&(cluster, t));
            let released = self.nets[net].clusters[cluster].released.contains(&t);
            if !used && !released {
                self.stamp_stub(net, cluster, t, -1);
                self.nets[net].clusters[cluster].released.insert(t);
            }
        }
    }

    /// Re-reserve a cluster's escapes after a rip-up; an escape crossed by another net's copper stays dead.
    pub fn reserve_escapes(&mut self, net: usize, cluster: usize) {
        let g = self.grid.clone();
        let escapes: Vec<Term> = self.nets[net].clusters[cluster].escapes.keys().copied().collect();
        let nid = self.nets[net].idx as i16;
        for t in escapes {
            if self.nets[net].clusters[cluster].released.contains(&t) {
                let l = t.layer();
                let a = self.board.pads[self.nets[net].clusters[cluster].primary].polys_centre;
                let b = g.to_xy(t.i as i64, t.j as i64);
                let mut checks = vec![(a, b, self.stub_for(net) / 2.0 + self.rules.clearance)];
                if let Some(k) = self.nets[net].clusters[cluster].corridors.get(&t) {
                    checks.push((b, *k, self.rules.track / 2.0 + self.rules.clearance));
                }
                let mut blocked = false;
                for (s0, s1, hw) in checks {
                    for c in g.segment_cells(s0, s1, hw, Some(1e-6)) {
                        let raw = self.route_raw[l][c];
                        if raw != -1 && raw != nid {
                            blocked = true;
                            break;
                        }
                    }
                    if blocked {
                        break;
                    }
                }
                if blocked {
                    let cl = &mut self.nets[net].clusters[cluster];
                    if cl.terminals.len() > 1 {
                        cl.terminals.retain(|x| *x != t);
                    }
                    self.stat("deadEscapes", 1);
                    continue;
                }
                self.stamp_stub(net, cluster, t, 1);
                self.nets[net].clusters[cluster].released.remove(&t);
                if !self.nets[net].clusters[cluster].terminals.contains(&t) {
                    self.nets[net].clusters[cluster].terminals.push(t);
                }
            } else {
                self.stamp_stub_channel(net, cluster, t);
            }
        }
    }

    fn stamp_stub_channel(&mut self, net: usize, cluster: usize, t: Term) {
        // (re)count the channel only: stamp_stub(+1) would re-stamp copper that is still there
        let key = (self.nets[net].idx, cluster, t);
        if self.chan_lines.contains_key(&key) {
            return;
        }
        // reuse stamp_stub's channel computation by a +1 stub stamp on already-stamped cells (idempotent copper)
        self.stamp_stub(net, cluster, t, 1);
    }

    pub fn rip_cluster(&mut self, net: usize, cluster: usize) {
        let routes = std::mem::take(&mut self.nets[net].routes);
        let mut keep = Vec::new();
        for r in routes {
            if r.start.cluster() == Some(cluster) && r.pair.is_none() {
                self.stamp_route(net, &r, -1);
                for c in &r.cells {
                    self.bump_history(c);
                }
            } else {
                keep.push(r);
            }
        }
        self.nets[net].routes = keep;
        self.nets[net].used_escapes.retain(|(ci, _)| *ci != cluster);
        self.nets[net].clusters[cluster].connected = false;
        self.reserve_escapes(net, cluster);
        let key = self.nets[net].clusters[cluster].key(&self.board).to_string();
        if !self.nets[net].failed.iter().any(|(k, _)| *k == key) {
            self.nets[net].failed.push((key, "ripped for a signal".into()));
        }
        self.stat("rips", 1);
        self.rip_total += 1;
    }

    fn bump_history(&mut self, c: &Term) {
        let g = &self.grid;
        for jj in (c.j as i64 - 2).max(0)..=(c.j as i64 + 2).min(g.h as i64 - 1) {
            for ii in (c.i as i64 - 2).max(0)..=(c.i as i64 + 2).min(g.w as i64 - 1) {
                let idx = jj as usize * g.w + ii as usize;
                self.history[c.layer()][idx] = self.history[c.layer()][idx].saturating_add(1);
            }
        }
    }

    /// Rip the net's routes, keeping its decoupling pair routes (decoupling.rs).
    pub fn rip(&mut self, net: usize) {
        self.rip_keeping(net, true);
    }

    pub fn rip_keeping(&mut self, net: usize, keep_pairs: bool) {
        let routes = std::mem::take(&mut self.nets[net].routes);
        let mut kept = Vec::new();
        for r in routes {
            if keep_pairs && r.pair.is_some() {
                kept.push(r);
                continue;
            }
            self.stamp_route(net, &r, -1);
            for c in &r.cells {
                self.bump_history(c);
            }
        }
        self.nets[net].routes = kept;
        self.nets[net].used_escapes.clear();
        let n = self.nets[net].clusters.len();
        for c in 0..n {
            self.nets[net].clusters[c].connected = false;
            self.reserve_escapes(net, c);
        }
        self.keep_pair_escapes(net);
        self.nets[net].rips += 1;
        self.rip_total += 1;
        self.stat("rips", 1);
    }

    // -- Kelvin taps -----------------------------------------------------------------------
    pub fn route_kelvin(&mut self, net: usize, src: usize, dst: usize) -> bool {
        let g = self.grid.clone();
        let mut kid = 30000 + (src % 1000);
        while self.nets.iter().any(|n| n.idx == kid) || self.kelvin_owner.contains_key(&kid) {
            kid += 1;
        }
        self.kelvin_owner.insert(kid, net);
        let nid = self.nets[net].idx as i16;
        let mut saved: Vec<(usize, Vec<usize>)> = Vec::new();
        for &cl in &[src, dst] {
            let p = self.board.pads[self.nets[net].clusters[cl].primary].clone();
            let cells = g.disk_cells((p.x, p.y), p.half_long + self.rules.escape + self.rules.corridor + 0.3, Some(1e-6));
            for l in 0..2 {
                let mine: Vec<usize> = cells.iter().copied().filter(|&c| self.pad_raw[l][c] == nid).collect();
                for &c in &mine {
                    self.pad_raw[l][c] = kid as i16;
                }
                saved.push((l, mine));
            }
        }
        // a synthetic net state just for the search
        let fake = NetState { idx: kid, name: self.nets[net].name.clone(), pads: Vec::new(), clusters: Vec::new(), routes: Vec::new(), widths: vec![self.rules.stub + 0.05], plane: None, mst_len: 0.0, used_escapes: HashSet::new(), failed: Vec::new(), rips: 0, routed_order: None, via_in_pad: Vec::new(), last_soft: Vec::new(), via: self.nets[net].via, drill: self.nets[net].drill, done_by_board: false, outside: Vec::new() };
        self.nets.push(fake);
        let fidx = self.nets.len() - 1;
        let sources: Vec<(Term, i64)> = self.nets[net].clusters[src].terminals.iter().map(|t| (*t, 0)).collect();
        let targets: HashSet<Term> = self.nets[net].clusters[dst].terminals.iter().copied().collect();
        let mut pts: Vec<(i64, i64)> = self.nets[net].clusters[src].terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
        let dpts: Vec<(i64, i64)> = self.nets[net].clusters[dst].terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
        pts.extend_from_slice(&dpts);
        let allow_via = self.nets[net].plane.is_none();
        let width = self.rules.stub + 0.05;
        let mut cells = None;
        for margin in [4.0, 10.0] {
            let win = self.window_for(&pts, margin);
            let (c, _) = self.search(fidx, width, Search { sources: sources.clone(), targets: Some(&targets), heur: dpts.clone(), win, allow_via, soft: false, via_target: false, max_nodes: None, vip: Vec::new() });
            if c.is_some() {
                cells = c;
                break;
            }
        }
        self.nets.pop();
        for (l, mine) in saved {
            for c in mine {
                self.pad_raw[l][c] = nid;
            }
        }
        let Some(cells) = cells else { self.kelvin_owner.remove(&kid); return false };
        let start = if self.nets[net].clusters[src].escapes.contains_key(&cells[0]) { End::Escape(src, cells[0]) } else { End::Pad(src, cells[0]) };
        let last = *cells.last().unwrap();
        let end = if self.nets[net].clusters[dst].escapes.contains_key(&last) { End::Escape(dst, last) } else { End::Pad(dst, last) };
        let mut r = Route::new(cells.clone(), width, start, end);
        r.kelvin = true;
        self.commit(net, r);
        // the tap is foreign copper to the rest of its net, except inside the pads it joins: the
        // pickup is the pad itself, and the wide path must still be able to land on that pad
        for c in &cells {
            let xy = g.to_xy(c.i as i64, c.j as i64);
            for cell in g.disk_cells(xy, width / 2.0, Some(1e-6)) {
                if self.pad_raw[c.layer()][cell] != nid {
                    self.route_raw[c.layer()][cell] = kid as i16;
                }
            }
        }
        self.nets[net].clusters[src].connected = true;
        self.kelvin_clusters.insert((net, src));
        self.stat("kelvin", 1);
        let (sk, dk) = (self.nets[net].clusters[src].key(&self.board).to_string(), self.nets[net].clusters[dst].key(&self.board).to_string());
        self.log(format!("    kelvin {sk} -> {dk}: {} cells, dedicated", cells.len()));
        true
    }

    // -- planes ------------------------------------------------------------------------------
    pub fn route_plane_net(&mut self, net: usize, retry: bool) {
        let g = self.grid.clone();
        let failed: HashSet<String> = if retry { self.nets[net].failed.iter().map(|(k, _)| k.clone()).collect() } else { HashSet::new() };
        if retry {
            self.nets[net].failed.clear();
        }
        let n = self.nets[net].clusters.len();
        let kelvin = self.rules.kelvin.clone();
        for c in 0..n {
            let cl = self.nets[net].clusters[c].clone();
            let key = cl.key(&self.board).to_string();
            if self.on_plane(net, c) || self.joined_by_board(net, c) {
                self.nets[net].clusters[c].connected = true;
                continue;
            }
            if kelvin.contains_key(&key) {
                continue;
            }
            if retry && (cl.connected || !failed.contains(&key)) {
                continue;
            }
            let sources: Vec<(Term, i64)> = cl.terminals.iter().map(|t| (*t, 0)).collect();
            let pts: Vec<(i64, i64)> = cl.terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
            let win = self.window_for(&pts, self.rules.via_search_mm);
            // the pad's own layer: a bottom part's pad (issue #139) reaches its via on B.Cu, and the via's
            // marker names the other layer so the plan carries a through via, not a point on the same layer
            let pl = { let p = &self.board.pads[cl.primary]; if p.thru || p.on_f { F_CU } else { B_CU } };
            let other = if pl == F_CU { B_CU } else { F_CU };
            let own: HashSet<Term> = self.copper_targets(net).into_iter().filter(|t| t.layer() == pl).collect();
            let track = self.rules.track;
            let (cells, _) = self.search(net, track, Search { sources, targets: Some(&own), heur: Vec::new(), win, allow_via: false, soft: false, via_target: true, max_nodes: None, vip: Vec::new() });
            match cells {
                None => {
                    let p = self.board.pads[cl.primary].clone();
                    let (i, j) = g.to_cell(p.x, p.y);
                    if self.via_clear_exact(net, p.x, p.y) {
                        let mut r = Route::new(vec![Term::new(pl, i, j)], track, End::Pad(c, Term::new(pl, i, j)), End::Via);
                        r.via_end = true;
                        r.via_end_layer = other;
                        self.commit(net, r);
                        self.nets[net].clusters[c].connected = true;
                        self.nets[net].via_in_pad.push(key.clone());
                        self.stat("viaInPad", 1);
                    } else {
                        self.nets[net].failed.push((key.clone(), format!("no via site within {:.0} mm", self.rules.via_search_mm)));
                    }
                }
                Some(cells) => {
                    let start = if cl.escapes.contains_key(&cells[0]) { End::Escape(c, cells[0]) } else { End::Pad(c, cells[0]) };
                    let joined = own.contains(cells.last().unwrap());
                    let mut r = Route::new(cells, track, start, if joined { End::Copper } else { End::Via });
                    r.via_end = !joined;
                    r.via_end_layer = other;
                    self.commit(net, r);
                    self.nets[net].clusters[c].connected = true;
                }
            }
        }
    }

    /// Exact geometry: may a via of this net sit at (x, y)?
    pub fn via_clear_exact(&mut self, net: usize, x: f64, y: f64) -> bool {
        let g = self.grid.clone();
        let (via, drill) = (self.nets[net].via, self.nets[net].drill);
        let rv = via / 2.0;
        let (i, j) = g.to_cell(x, y);
        if !g.in_bounds(i, j) || !self.inside_for(via).get(i as usize, j as usize) {
            return false;
        }
        let reach = rv + self.big_clr_val + 1.5;
        let name = self.nets[net].name.clone();
        for p in &self.board.pads {
            if (p.x - x).abs() > reach + p.half_long || (p.y - y).abs() > reach + p.half_long {
                continue;
            }
            if p.net == name && !p.thru {
                continue;
            }
            let mut need = if p.thru && p.net == name { drill / 2.0 + self.rules.hole_to_hole + p.drill.unwrap_or(0.0) / 2.0 + slop() } else { rv + self.rules.clearance.max(p.clearance) };
            if p.thru && p.net != name {
                need = need.max(drill / 2.0 + self.rules.hole_to_hole + p.drill.unwrap_or(0.0) / 2.0);
            }
            for poly in &p.polys {
                if geom::point_poly_distance(x, y, poly) < need {
                    return false;
                }
            }
        }
        // drilled holes with no copper: hole to hole for the drill, clearance for the via's copper
        for h in &self.board.holes {
            if (h.x - x).abs() > reach + h.diameter() || (h.y - y).abs() > reach + h.diameter() {
                continue;
            }
            let need = (drill / 2.0 + self.rules.hole_to_hole).max(rv + self.rules.clearance) + slop();
            if geom::point_poly_distance(x, y, &h.poly) < need {
                return false;
            }
        }
        if self.fixed_blocks(&name, None, x, y, rv + self.rules.clearance) {
            return false;
        }
        if g.in_bounds(i, j) && (0..2).any(|l| self.kept_from(&name, l, j as usize * g.w + i as usize)) {
            return false;
        }
        let nid = self.nets[net].idx;
        for (oi, other) in self.nets.iter().enumerate() {
            if other.idx == nid || oi == net {
                continue;
            }
            for r in &other.routes {
                let need = rv + self.rules.clearance + r.width / 2.0;
                for (ax, ay, bx, by) in route_segments(&g, &r.cells) {
                    if (ax - x).abs() > 3.0 && (bx - x).abs() > 3.0 {
                        continue;
                    }
                    if geom::seg_distance(x, y, ax, ay, bx, by) < need {
                        return false;
                    }
                }
            }
        }
        for &(vi, vj, vnid, dia, vdrill) in &self.vias {
            let (vx, vy) = g.to_xy(vi as i64, vj as i64);
            if (vx - x).hypot(vy - y) < self.via_gap(net, vnid, dia, vdrill) {
                return false;
            }
        }
        true
    }

    // -- driver --------------------------------------------------------------------------
    pub fn mst_length(&self, net: usize) -> f64 {
        let pts: Vec<(f64, f64)> = self.nets[net].clusters.iter().map(|c| c.xy(&self.board)).collect();
        if pts.len() < 2 {
            return 0.0;
        }
        let mut inn = vec![pts[0]];
        let mut rest: Vec<(f64, f64)> = pts[1..].to_vec();
        let mut total = 0.0;
        while !rest.is_empty() {
            let mut best = (f64::INFINITY, 0usize);
            for (ri, b) in rest.iter().enumerate() {
                for a in &inn {
                    let d = (a.0 - b.0).hypot(a.1 - b.1);
                    if d < best.0 {
                        best = (d, ri);
                    }
                }
            }
            total += best.0;
            inn.push(rest.remove(best.1));
        }
        total
    }

    pub fn run(&mut self, planes: bool, rip_per_net: usize, rip_global: usize, priority: &[String]) -> usize {
        let t0 = std::time::Instant::now();
        self.rip_total = 0;
        for n in self.nets.iter_mut() {
            n.rips = 0;
        }
        let plane_nets: Vec<usize> = self.nets.iter().filter(|n| n.plane.is_some()).map(|n| n.idx).collect();
        let kelvin = self.rules.kelvin.clone();
        // assigned-pin decoupling pairs go down before any rail distribution (spec "decoupling")
        self.route_decoupling();
        if planes {
            for &net in &plane_nets {
                if self.nets[net].done_by_board {
                    continue;
                }
                let t1 = std::time::Instant::now();
                let n = self.nets[net].clusters.len();
                for c in 0..n {
                    let key = self.nets[net].clusters[c].key(&self.board).to_string();
                    if self.joined_by_board(net, c) {
                        continue;
                    }
                    if let Some(dk) = kelvin.get(&key) {
                        let dst = self.nets[net].clusters.iter().position(|k| k.key(&self.board) == dk);
                        if dst.map(|d| !self.route_kelvin(net, c, d)).unwrap_or(true) {
                            self.nets[net].failed.push((key, "kelvin tap found no dedicated path".into()));
                        }
                    }
                }
                self.route_plane_net(net, false);
                let (name, plane, nr, nv, nf) = (self.nets[net].name.clone(), self.nets[net].plane.clone().unwrap(), self.nets[net].routes.len(), self.nets[net].via_in_pad.len(), self.nets[net].failed.len());
                self.log(format!("  {name:<28} plane {plane}: {} smd stubs, {nv} via-in-pad, {nf} failed, {:.1}s", nr - nv, t1.elapsed().as_secs_f64()));
            }
        }
        let mut signal: Vec<usize> = self.nets.iter().filter(|n| n.plane.is_none() && n.clusters.len() >= 2 && !n.done_by_board).map(|n| n.idx).collect();
        for &n in &signal {
            let l = self.mst_length(n);
            self.nets[n].mst_len = l;
        }
        signal.sort_by(|a, b| self.nets[*a].mst_len.partial_cmp(&self.nets[*b].mst_len).unwrap());
        // `route --variants`: another order of the same nets (the default keeps shortest first untouched)
        crate::variants::reorder(&mut signal, &self.nets, self.order);
        // issue #129: the AI's ranking goes first, class by class; within a class (and for the nets no class
        // names, which come last) the order above stands (the sort is stable)
        let ranked = !self.rules.signal_priority.is_empty();
        crate::signal_priority::sort_by_rank(&mut signal, &self.rules.signal_priority, |&n| self.nets[n].name.clone());
        let mut first: Vec<usize> = signal.iter().copied().filter(|n| priority.contains(&self.nets[*n].name)).collect();
        let mut rest: Vec<usize> = signal.iter().copied().filter(|n| !priority.contains(&self.nets[*n].name)).collect();
        let mut queue: Vec<usize> = Vec::new();
        queue.append(&mut first);
        queue.append(&mut rest);
        self.log(format!("routing {} signal nets, {}{}{}", queue.len(), if ranked { "by the spec's signalPriority classes, then " } else { "" }, self.order.describe(), if priority.is_empty() { String::new() } else { format!(", {} nets that failed last pass go first: {:?}", priority.len(), priority) }));
        let mut order_no = 0;
        let mut best_state: Option<(usize, Snapshot, Vec<usize>)> = None;
        while !queue.is_empty() {
            let net = queue.remove(0);
            if self.nets[net].routes.iter().any(|r| r.pair.is_none()) {
                self.rip(net);
            }
            let t1 = std::time::Instant::now();
            let blockers = self.route_net(net);
            order_no += 1;
            self.nets[net].routed_order = Some(order_no);
            {
                let n = &self.nets[net];
                let widths: Vec<String> = n.widths.iter().map(|w| format!("{w}")).collect();
                let line = format!("  {:<28} {:>2} clusters  {}  {} routes, {} failed, {:.1}s{}", n.name, n.clusters.len(), widths.join("/"), n.routes.len(), n.failed.len(), t1.elapsed().as_secs_f64(), if n.failed.is_empty() { String::new() } else { format!("  FAILED {:?}", n.failed) });
                self.log(line);
            }
            let score = self.nets.iter().filter(|n| !queue.contains(&n.idx)).map(|n| n.failed.len()).sum::<usize>() + queue.iter().map(|&q| self.nets[q].clusters.len().saturating_sub(1)).sum::<usize>();
            if best_state.as_ref().map(|b| score < b.0).unwrap_or(true) {
                // issue #167: the nets still queued here are not routed in this snapshot; keep them to finish after a restore
                best_state = Some((score, self.snapshot(), queue.clone()));
            }
            if !self.nets[net].failed.is_empty() && !blockers.is_empty() && self.nets[net].rips < rip_per_net && self.rip_total < rip_global {
                let mut cands: Vec<usize> = blockers.iter().copied().filter(|b| !self.kelvin_owner.contains_key(b)).filter_map(|b| self.nets.iter().position(|n| n.idx == b)).filter(|&n| self.nets[n].routes.iter().any(|r| r.pair.is_none()) && self.nets[n].plane.is_none()).collect();
                cands.sort_by_key(|&n| std::cmp::Reverse(self.nets[n].routed_order.unwrap_or(0)));
                cands.truncate(4);
                let mut stubs: Vec<(usize, usize)> = Vec::new();
                if cands.is_empty() {
                    let soft: HashSet<(i32, i32)> = self.nets[net].last_soft.iter().flat_map(|t| { let (i, j) = (t.i, t.j); (-6..=6).flat_map(move |di| (-6..=6).map(move |dj| (i + di, j + dj))) }).collect();
                    for &b in &blockers {
                        if let Some(pn) = self.nets.iter().position(|n| n.idx == b) {
                            if self.nets[pn].plane.is_none() {
                                continue;
                            }
                            for r in self.nets[pn].routes.clone() {
                                if r.cells.iter().any(|t| soft.contains(&(t.i, t.j))) {
                                    if let Some(cl) = r.start.cluster() {
                                        stubs.push((pn, cl));
                                    }
                                }
                            }
                        }
                    }
                }
                if !cands.is_empty() || !stubs.is_empty() {
                    let cn: Vec<String> = cands.iter().map(|&c| self.nets[c].name.clone()).collect();
                    let sn: Vec<String> = stubs.iter().map(|(pn, cl)| self.nets[*pn].clusters[*cl].key(&self.board).to_string()).collect();
                    let name = self.nets[net].name.clone();
                    self.log(format!("    rip-up {cn:?}{} and retry {name}", if sn.is_empty() { String::new() } else { format!(" + plane stubs {sn:?}") }));
                    for &c in &cands {
                        self.rip(c);
                        queue.retain(|&q| q != c);
                    }
                    for (pn, cl) in stubs {
                        self.rip_cluster(pn, cl);
                    }
                    self.nets[net].rips += 1;
                    queue.insert(0, net);
                    for (k, &c) in cands.iter().enumerate() {
                        queue.insert(1 + k, c);
                    }
                    continue;
                }
            }
            if planes {
                for &pn in &plane_nets {
                    if !self.nets[pn].failed.is_empty() {
                        self.route_plane_net(pn, true);
                    }
                }
            }
        }
        if planes {
            for &pn in &plane_nets {
                if self.nets[pn].failed.is_empty() {
                    continue;
                }
                let before = self.nets[pn].failed.len();
                self.route_plane_net(pn, true);
                let (name, after) = (self.nets[pn].name.clone(), self.nets[pn].failed.len());
                self.log(format!("  {name:<28} plane retry: {} of {before} stubs recovered", before - after));
            }
        }
        let mut final_failed: usize = self.nets.iter().map(|n| n.failed.len()).sum();
        if let Some((score, snap, pending)) = best_state {
            if score < final_failed {
                // issue #167: the best intermediate state still had nets in the queue (never routed, never
                // failed); route them now, without rip-up, and keep that state only when it really is better
                let end = self.snapshot();
                self.restore(&snap);
                for &net in &pending {
                    if self.nets[net].routes.iter().any(|r| r.pair.is_none()) {
                        self.rip(net);
                    }
                    self.route_net(net);
                    order_no += 1;
                    self.nets[net].routed_order = Some(order_no);
                }
                if planes {
                    for &pn in &plane_nets {
                        if !self.nets[pn].failed.is_empty() {
                            self.route_plane_net(pn, true);
                        }
                    }
                }
                let restored: usize = self.nets.iter().map(|n| n.failed.len()).sum();
                if restored < final_failed {
                    self.log(format!("  restoring the best intermediate state ({restored} failed connections instead of {final_failed}, {} queued net(s) routed after it)", pending.len()));
                    final_failed = restored;
                } else {
                    self.restore(&end);
                }
            }
        }
        final_failed += self.flag_never_routed();
        let (exp, rips) = (self.stats.get("expanded").copied().unwrap_or(0), self.stats.get("rips").copied().unwrap_or(0));
        self.log(format!("routing done in {:.1}s, {exp} node expansions, {rips} rip-ups, {final_failed} failed connections", t0.elapsed().as_secs_f64()));
        final_failed
    }

    /// Issue #167: a signal net that ends a run with open clusters, no routes, no failures and no
    /// route order was dropped, never tried. Each open cluster becomes a failed connection with
    /// its reason, so the report, the summary and the variant ranking count it. Returns how many.
    pub fn flag_never_routed(&mut self) -> usize {
        let mut added = 0;
        for n in 0..self.nets.len() {
            let net = &self.nets[n];
            if net.plane.is_some() || net.done_by_board || net.clusters.len() < 2 || !net.failed.is_empty() || !net.routes.is_empty() {
                continue;
            }
            let groups: HashSet<usize> = (0..net.clusters.len()).map(|c| self.comp_of(n, c)).collect();
            if groups.len() < 2 {
                continue;
            }
            let mut seen: HashSet<usize> = HashSet::from([self.comp_of(n, 0)]);
            let open: Vec<String> = (1..net.clusters.len()).filter(|&c| seen.insert(self.comp_of(n, c))).map(|c| net.clusters[c].key(&self.board).to_string()).collect();
            for key in open {
                self.nets[n].failed.push((key, "never routed: the router dropped this net (ripped up and not retried before the rip budget or the pass ended); route again with a higher --rip-global or more --passes".into()));
                added += 1;
            }
        }
        if added > 0 {
            self.log(format!("  {added} connection(s) of nets that were never routed, now reported as failed"));
        }
        added
    }

    pub fn reset(&mut self) {
        let n = self.nets.len();
        for net in 0..n {
            if !self.nets[net].routes.is_empty() {
                self.rip_keeping(net, false);
            }
            self.nets[net].failed.clear();
            self.nets[net].via_in_pad.clear();
            self.nets[net].routed_order = None;
            self.nets[net].used_escapes.clear();
            let done = self.nets[net].done_by_board;
            for c in self.nets[net].clusters.iter_mut() {
                c.connected = done;
            }
        }
        self.rip_total = 0;
    }

    pub fn snapshot(&self) -> Snapshot {
        Snapshot { nets: self.nets.iter().map(|n| (n.routes.clone(), n.used_escapes.clone(), n.failed.clone(), n.via_in_pad.clone(), n.routed_order)).collect() }
    }

    pub fn restore(&mut self, snap: &Snapshot) {
        self.reset();
        for (net, (routes, used, failed, vip, order)) in snap.nets.iter().enumerate() {
            self.nets[net].used_escapes = used.clone();
            self.nets[net].failed = failed.clone();
            self.nets[net].via_in_pad = vip.clone();
            self.nets[net].routed_order = *order;
            for r in routes {
                self.stamp_route(net, r, 1);
                if r.kelvin {
                    // the tap's own-net exclusion is rebuilt by the next kelvin routing; here it is copper of its net
                }
                self.nets[net].routes.push(r.clone());
            }
            let n = self.nets[net].clusters.len();
            for c in 0..n {
                let plane_thru = self.nets[net].plane.is_some() && self.on_plane(net, c);
                let touched = self.nets[net].routes.iter().any(|r| r.start.cluster() == Some(c) || (matches!(r.end, End::Pad(..) | End::Escape(..)) && r.end.cluster() == Some(c)));
                let done = self.nets[net].done_by_board || self.joined_by_board(net, c);
                self.nets[net].clusters[c].connected = touched || plane_thru || done;
            }
        }
    }

    // -- plan emission -----------------------------------------------------------------------
    /// A cluster's pad as a plan waypoint: its key, or its coordinates when the key names more than one
    /// pad on the board (issue #93: a connector's two `MP` pads; the bridge would take the first).
    fn pad_waypoint(&self, net: usize, cl: usize, layer: Option<&str>) -> Value {
        let p = &self.board.pads[self.nets[net].clusters[cl].primary];
        match (self.board.key_is_ambiguous(&p.key), layer) {
            (false, None) => json!(p.key),
            (false, Some(l)) => json!({"pad": p.key, "layer": l}),
            (true, None) => json!([p.x, p.y]),
            (true, Some(l)) => json!({"x": p.x, "y": p.y, "layer": l}),
        }
    }

    fn waypoints(&self, net: usize, route: &Route) -> Vec<Value> {
        let g = &self.grid;
        let cells = &route.cells;
        let xy = |c: &Term| { let p = g.to_xy(c.i as i64, c.j as i64); json!([p.0, p.1]) };
        let mut pts: Vec<Value> = Vec::new();
        match &route.start {
            End::Pad(cl, term) => pts.push(self.pad_waypoint(net, *cl, (term.layer() == B_CU).then_some("B.Cu"))),
            _ => {
                let first = &cells[0];
                let p = g.to_xy(first.i as i64, first.j as i64);
                pts.push(json!({"x": p.0, "y": p.1, "layer": aiflow_board::LAYER_NAMES[first.layer()]}));
            }
        }
        let n = cells.len();
        let mut k = 1;
        while k < n {
            let (l, i, j) = (cells[k].layer(), cells[k].i, cells[k].j);
            let (pl, pi, pj) = (cells[k - 1].layer(), cells[k - 1].i, cells[k - 1].j);
            if l != pl {
                let p = g.to_xy(i as i64, j as i64);
                pts.push(json!({"x": p.0, "y": p.1, "layer": aiflow_board::LAYER_NAMES[l]}));
                k += 1;
                continue;
            }
            let (di, dj) = (i - pi, j - pj);
            let mut m = k;
            while m + 1 < n && cells[m + 1].layer() == l && (cells[m + 1].i - cells[m].i, cells[m + 1].j - cells[m].j) == (di, dj) && !route.breaks.contains(&m) {
                m += 1;
            }
            if m == n - 1 {
                break;
            }
            pts.push(xy(&cells[m]));
            k = m + 1;
        }
        let last = cells[n - 1];
        if route.via_end {
            let mut p = g.to_xy(last.i as i64, last.j as i64);
            if n == 1 {
                if let End::Pad(cl, _) = &route.start {
                    let pad = &self.board.pads[self.nets[net].clusters[*cl].primary];
                    p = (pad.x, pad.y);
                }
            }
            pts.push(json!({"x": p.0, "y": p.1, "layer": aiflow_board::LAYER_NAMES[route.via_end_layer]}));
            if let End::Pad(cl, _) = &route.end {
                pts.push(self.pad_waypoint(net, *cl, None));
            }
        } else {
            match &route.end {
                End::Pad(cl, _) => pts.push(self.pad_waypoint(net, *cl, None)),
                _ => pts.push(xy(&last)),
            }
        }
        pts
    }

    /// Issue #183: a route that changes layer at through-hole pads of its net, cut into one route per
    /// face. Each cut ends and starts on the pad (the lead joins the faces), so no via is planned.
    pub fn split_at_pads(&self, net: usize, route: &Route) -> Vec<Route> {
        let cells = &route.cells;
        let cuts: Vec<usize> = (1..cells.len()).filter(|&k| cells[k].layer() != cells[k - 1].layer()).collect();
        if cuts.is_empty() {
            return vec![route.clone()];
        }
        let mut out = Vec::new();
        let mut start = route.start.clone();
        let mut from = 0usize;
        for &k in cuts.iter().chain(std::iter::once(&cells.len())) {
            let piece: Vec<Term> = cells[from..k].to_vec();
            let end = if k == cells.len() { route.end.clone() } else {
                let t = cells[k - 1];
                match self.pth_cluster_at(net, t.i, t.j) { Some(cl) => End::Pad(cl, t), None => End::Copper }
            };
            let next_start = if k < cells.len() {
                let t = cells[k];
                match self.pth_cluster_at(net, t.i, t.j) { Some(cl) => End::Pad(cl, t), None => End::Copper }
            } else { End::Copper };
            if piece.len() >= 2 {
                let mut r = Route::new(piece, route.width, start.clone(), end);
                r.kelvin = route.kelvin;
                r.pair = route.pair;
                r.breaks = route.breaks.iter().filter(|&&b| b >= from && b < k).map(|b| b - from).collect();
                if k == cells.len() { r.via_end = route.via_end; r.via_end_layer = route.via_end_layer; }
                out.push(r);
            }
            start = next_start;
            from = k;
        }
        out
    }

    pub fn plan(&self) -> Vec<Value> {
        let mut order: Vec<usize> = (0..self.nets.len()).collect();
        order.sort_by_key(|&n| (self.nets[n].routed_order.unwrap_or(1_000_000), self.nets[n].name.clone()));
        let mut entries = Vec::new();
        for n in order {
            let net = &self.nets[n];
            if net.routes.is_empty() {
                continue;
            }
            let mut by_width: Vec<(f64, Vec<Value>)> = Vec::new();
            for r in &net.routes {
                // issue #183: with vias off a route that changes layer at a through-hole pad is one path per face
                let split = if self.rules.vias_allowed() { Vec::new() } else { self.split_at_pads(n, r) };
                if split.len() > 1 {
                    let paths: Vec<Value> = split.iter().map(|sr| self.waypoints(n, sr)).filter(|p| p.len() >= 2).map(Value::Array).collect();
                    if r.kelvin || r.pair.is_some() {
                        let mut e = json!({"net": net.name, "width": r.width, "viaSize": net.via, "viaDrill": net.drill, "paths": paths});
                        if r.kelvin { e["kelvin"] = json!(true); } else { e["decoupling"] = json!(r.pair.and_then(|k| self.pairs.get(k)).map(|p| p.r.label.clone())); }
                        entries.push(e);
                    } else if let Some(e) = by_width.iter_mut().find(|(w, _)| (*w - r.width).abs() < 1e-9) {
                        e.1.extend(paths);
                    } else {
                        by_width.push((r.width, paths));
                    }
                    continue;
                }
                let pts = self.waypoints(n, r);
                if pts.len() < 2 {
                    continue;
                }
                if r.kelvin {
                    entries.push(json!({"net": net.name, "width": r.width, "viaSize": net.via, "viaDrill": net.drill, "paths": [pts], "kelvin": true}));
                    continue;
                }
                if let Some(k) = r.pair {
                    entries.push(json!({"net": net.name, "width": r.width, "viaSize": net.via, "viaDrill": net.drill, "paths": [pts], "decoupling": self.pairs.get(k).map(|p| p.r.label.clone())}));
                    continue;
                }
                if let Some(e) = by_width.iter_mut().find(|(w, _)| (*w - r.width).abs() < 1e-9) {
                    e.1.push(Value::Array(pts));
                } else {
                    by_width.push((r.width, vec![Value::Array(pts)]));
                }
            }
            let mut stubs: Vec<Value> = Vec::new();
            let mut used: Vec<(usize, Term)> = net.used_escapes.iter().copied().collect();
            used.sort();
            for (cidx, term) in used {
                let key = net.clusters[cidx].key(&self.board);
                let p = self.grid.to_xy(term.i as i64, term.j as i64);
                // the stub leaves along the pad's long axis: a pad centre is off the grid, and a stub
                // that slopes toward the escape cell from the first micrometre grazes the neighbouring
                // pin (0.1989 mm against a 0.2 rule on a 0.5 mm pitch); the jog to the cell happens at
                // the cell end, inside the stub's own width
                let pad = &self.board.pads[net.clusters[cidx].primary];
                let (ax, ay) = pad.long_axis;
                let norm = (ax * ax + ay * ay).sqrt();
                // issue #139: a bottom pad's stub is on B.Cu; a stub with no layer lands on F.Cu
                let mut pts = vec![if term.layer() == B_CU { self.pad_waypoint(n, cidx, Some("B.Cu")) } else { json!(key) }];
                if norm > 1e-9 {
                    let (ux, uy) = (ax / norm, ay / norm);
                    let t = (p.0 - pad.x) * ux + (p.1 - pad.y) * uy;
                    let mid = (((pad.x + ux * t) * 1000.0).round() / 1000.0, ((pad.y + uy * t) * 1000.0).round() / 1000.0);
                    let jog = (p.0 - mid.0).hypot(p.1 - mid.1);
                    if jog > 1e-6 && jog < self.stub_for(n) && t.abs() > 1e-6 {
                        pts.push(json!([mid.0, mid.1]));
                    }
                }
                pts.push(json!([p.0, p.1]));
                stubs.push(Value::Array(pts));
            }
            if !stubs.is_empty() {
                entries.push(json!({"net": net.name, "width": self.stub_for(n), "viaSize": net.via, "viaDrill": net.drill, "paths": stubs}));
            }
            by_width.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
            for (w, paths) in by_width {
                entries.push(json!({"net": net.name, "width": w, "viaSize": net.via, "viaDrill": net.drill, "paths": paths}));
            }
        }
        entries
    }

    pub fn report(&self) -> Value {
        let mut nets = serde_json::Map::new();
        let mut unrouted = Vec::new();
        for net in &self.nets {
            if net.clusters.len() < 2 && net.plane.is_none() && net.outside.is_empty() {
                continue;
            }
            let mut widths: Vec<f64> = net.routes.iter().map(|r| r.width).collect();
            widths.sort_by(|a, b| b.partial_cmp(a).unwrap());
            widths.dedup();
            nets.insert(net.name.clone(), json!({
                "clusters": net.clusters.len(), "pads": net.pads.len(), "routes": net.routes.len(), "widths": widths, "plane": net.plane,
                "failed": net.failed.iter().chain(&net.outside).collect::<Vec<_>>(), "viaInPad": net.via_in_pad, "ripUps": net.rips, "order": net.routed_order, "mstMm": (net.mst_len * 100.0).round() / 100.0,
                "doneByBoard": net.done_by_board,
            }));
            for (k, why) in net.failed.iter().chain(&net.outside) {
                unrouted.push(json!([net.name, [k, why]]));
            }
        }
        let mut rep = json!({"rules": serde_json::to_value(&self.rules).unwrap(), "nets": nets, "stats": self.stats, "unrouted": unrouted, "boardCopper": self.board_copper_summary(), "decoupling": self.decoupling_report(),
            "planeUnder": self.keep.iter().map(|k| json!({"label": k.label, "net": k.net, "layer": aiflow_board::LAYER_NAMES[k.layer], "polygon": k.poly})).collect::<Vec<_>>()});
        if !self.rules.default_copper_mode() {
            rep["singleFace"] = self.single_face_summary();
        }
        rep
    }

    /// Issue #183: what single-face routing made of the board: connections closed on the primary face
    /// alone, connections that needed the jumper layer, layer changes made on through-hole pads, and
    /// vias (always 0: the mode plans none).
    pub fn single_face_summary(&self) -> Value {
        let primary = self.rules.primary_layer();
        let (mut closed, mut single, mut jumpered, mut changes) = (0usize, 0usize, 0usize, 0usize);
        for net in &self.nets {
            for r in &net.routes {
                closed += 1;
                if r.cells.iter().all(|t| t.layer() == primary) { single += 1; } else { jumpered += 1; }
                changes += r.cells.windows(2).filter(|w| w[0].layer() != w[1].layer()).count();
            }
        }
        json!({"layers": self.mode_layers(), "vias": false, "primary": aiflow_board::LAYER_NAMES[primary],
               "jumperLayer": self.rules.jumper_layer().map(|l| aiflow_board::LAYER_NAMES[l]),
               "connections": closed, "singleLayer": single, "withJumper": jumpered, "layerChangesAtPads": changes, "viasPlanned": self.vias.len()})
    }

    /// What the board's own copper already did: its size, the nets it completes, the nets it
    /// only partly joins (the plan finishes those), and how many connections the router still had to plan.
    pub fn board_copper_summary(&self) -> Value {
        let mut complete = Vec::new();
        let mut partial = Vec::new();
        let mut open = 0usize;
        for (n, net) in self.nets.iter().enumerate() {
            if net.clusters.len() < 2 && net.plane.is_none() {
                continue;
            }
            if net.done_by_board {
                complete.push(net.name.clone());
                continue;
            }
            let groups: HashSet<usize> = (0..net.clusters.len()).map(|c| self.comp_of(n, c)).collect();
            let joined = (0..net.clusters.len()).any(|c| self.joined_by_board(n, c));
            if joined {
                partial.push(net.name.clone());
            }
            open += if net.plane.is_some() { (0..net.clusters.len()).filter(|&c| !self.joined_by_board(n, c) && !self.on_plane(n, c)).count() } else { groups.len() - 1 };
        }
        // a zone of a net the plan still tracks, with no fill in the board file: once refilled it
        // may join those pads itself, so say so instead of tracking across it in silence (issue #84)
        let zones = self.board.zones();
        let islands = self.board.copper_fills().len();
        let mut warnings: Vec<String> = Vec::new();
        for net in &self.nets {
            if net.done_by_board || net.routes.is_empty() { continue; }
            let unfilled: Vec<&aiflow_board::Zone> = zones.iter().filter(|z| z.net == net.name && z.fills.is_empty()).collect();
            if unfilled.is_empty() { continue; }
            let mut layers: Vec<&str> = unfilled.iter().flat_map(|z| z.layers.iter().map(|&l| aiflow_board::LAYER_NAMES[l])).collect();
            layers.sort();
            layers.dedup();
            warnings.push(format!("{} has a zone on {} with no fill in the board file, and the plan tracks {} connection(s) of it: refill the zones (KiCad: Edit > Fill All Zones, save) and route again instead of tracking across the pour", net.name, layers.join(" and "), net.routes.len()));
        }
        json!({"trackPieces": self.fixed_tracks.len(), "vias": self.fixed_vias.len(), "zoneIslands": islands, "netsComplete": complete, "netsPartial": partial, "openConnections": open, "warnings": warnings})
    }
}

/// Straight runs of a cell path as exact segments, vias skipped.
pub fn route_segments(g: &aiflow_grid::Grid, cells: &[Term]) -> Vec<(f64, f64, f64, f64)> {
    let mut out = Vec::new();
    let n = cells.len();
    let mut k = 0;
    while k + 1 < n {
        let l = cells[k].layer();
        let mut m = k + 1;
        if cells[m].layer() != l {
            k = m;
            continue;
        }
        let (di, dj) = (cells[m].i - cells[k].i, cells[m].j - cells[k].j);
        while m + 1 < n && cells[m + 1].layer() == l && (cells[m + 1].i - cells[m].i, cells[m + 1].j - cells[m].j) == (di, dj) {
            m += 1;
        }
        let a = g.to_xy(cells[k].i as i64, cells[k].j as i64);
        let b = g.to_xy(cells[m].i as i64, cells[m].j as i64);
        out.push((a.0, a.1, b.0, b.1));
        k = m;
    }
    out
}

/// Route a board: passes with the failed nets first; keeps the best pass. Returns (plan entries, report, failed).
pub fn route_board(router: &mut Router, passes: usize, rip_per_net: usize, rip_global: usize) -> (Vec<Value>, Value, usize) {
    let mut best: Option<(usize, Snapshot, usize)> = None;
    let mut priority: Vec<String> = Vec::new();
    for k in 1..=passes {
        if k > 1 {
            router.reset();
        }
        // rounded corners first; a board still open after half its passes needs the room more than the corners
        router.flat_turns = k > passes.div_ceil(2);
        router.log(format!("=== pass {k} of {passes}{} ===", if router.flat_turns { ", turns at one cost" } else { "" }));
        let failed = router.run(true, rip_per_net, rip_global, &priority);
        let mut names: Vec<String> = router.nets.iter().filter(|n| !n.failed.is_empty()).map(|n| n.name.clone()).collect();
        names.sort();
        names.dedup();
        router.log(format!("=== pass {k}: {failed} failed connections in {names:?}"));
        if best.as_ref().map(|b| failed < b.0).unwrap_or(true) {
            best = Some((failed, router.snapshot(), k));
        }
        if failed == 0 {
            break;
        }
        priority = names;
    }
    let (failed, snap, k) = best.unwrap();
    router.restore(&snap);
    router.log(format!("keeping pass {k} ({failed} failed connections)"));
    // issue #140: pads off the board were never routed; each is an unrouted connection with its reason
    let outside: usize = router.nets.iter().map(|n| n.outside.len()).sum();
    if outside > 0 {
        let why: Vec<String> = router.nets.iter().flat_map(|n| n.outside.iter().map(|(_, w)| w.clone())).collect::<std::collections::BTreeSet<_>>().into_iter().collect();
        router.log(format!("{outside} more connection(s) not routed, off the board: {}", why.join("; ")));
    }
    let failed = failed + outside;
    let plan = router.plan();
    let report = router.report();
    (plan, report, failed)
}

#[allow(dead_code)]
fn _unused(_: HashMap<u8, u8>) {}

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

    #[test]
    fn existing_copper_start_preserves_its_layer_in_export() {
        let b = crate::board_copper::tests::board(&[("J1", "A", 2.0, 5.0, true)], "");
        let r = Router::new(b, crate::Rules::default(), false);
        let net = r.net_ids["A"];
        let (i, j) = r.grid.to_cell(10.0, 5.0);
        for layer in [F_CU, B_CU] {
            let cells = vec![Term::new(layer, i, j), Term::new(layer, i + 1, j)];
            let route = Route::new(cells, 0.25, End::Copper, End::Copper);
            let points = r.waypoints(net, &route);
            assert_eq!(points[0]["layer"], aiflow_board::LAYER_NAMES[layer]);
            let expected = r.grid.to_xy(i, j);
            assert_eq!(points[0]["x"], expected.0);
            assert_eq!(points[0]["y"], expected.1);
        }
    }
    const BOTTOM: &str = include_str!("../../../tests/fixtures/bottom-side.kicad_pcb");

    /// Every pad a plan path reaches, with the layer the path is on there (as plan_to_copper reads it):
    /// the pads with no copper on that layer.
    fn pads_off_their_layer(b: &aiflow_board::Board, plan: &[Value]) -> Vec<String> {
        let mut bad = Vec::new();
        for e in plan {
            for path in e["paths"].as_array().unwrap() {
                let pts = path.as_array().unwrap();
                let wp = |v: &Value| -> (Option<&aiflow_board::Pad>, Option<String>) {
                    let key = v.as_str().or_else(|| v.get("pad").and_then(|p| p.as_str()));
                    (key.and_then(|k| b.pad_by_key(k)), v.get("layer").and_then(|l| l.as_str()).map(str::to_string))
                };
                let mut layer = e["layer"].as_str().map(str::to_string).or_else(|| wp(&pts[0]).1)
                    .unwrap_or_else(|| aiflow_board::Board::path_start_layer(pts.iter().map(|v| { let (p, l) = wp(v); (p, l.is_some()) })).to_string());
                for v in pts {
                    let (pad, l) = wp(v);
                    if let Some(l) = l { layer = l; }
                    if let Some(p) = pad {
                        let on = p.thru || (layer == "F.Cu" && p.on_f) || (layer == "B.Cu" && p.on_b);
                        if !on { bad.push(format!("{} on {layer} ({} {})", p.key, e["net"], path)); }
                    }
                }
            }
        }
        bad
    }

    /// Issue #139: parts on the bottom (B.Cu-only SMD pads, one with narrow pads and escapes) route,
    /// and every path reaches each bottom pad on B.Cu (a via where it comes from F.Cu).
    #[test]
    fn bottom_side_pads_are_routed_and_reached_on_b_cu() {
        let b = aiflow_board::Board::from_text("bottom.kicad_pcb", BOTTOM.to_string()).unwrap();
        let u1 = b.pad_by_key("U1.1").unwrap();
        assert!(u1.on_b && !u1.on_f && !u1.thru);
        let mut r = Router::new(aiflow_board::Board::from_text("bottom.kicad_pcb", BOTTOM.to_string()).unwrap(), crate::Rules::default(), false);
        let (plan, report, failed) = route_board(&mut r, 3, 4, 40);
        assert_eq!(failed, 0, "{}", report["unrouted"]);
        assert!(!plan.is_empty());
        let bad = pads_off_their_layer(&b, &plan);
        assert!(bad.is_empty(), "paths reach pads on a layer they have no copper on: {bad:?}");
        // B (U1.2 to R2.1) is bottom to bottom: no via needed, so B.Cu all the way
        let text = serde_json::to_string(&plan).unwrap();
        assert!(text.contains("B.Cu"), "{text}");
    }

    /// Issue #167: a net left with open clusters, no routes and no failure (dropped from the queue by a
    /// best-state restore) is reported unrouted with its reason and counted, never left silent.
    #[test]
    fn a_dropped_net_is_reported_unrouted_and_counted() {
        let mut r = Router::new(aiflow_board::Board::from_text("bottom.kicad_pcb", BOTTOM.to_string()).unwrap(), crate::Rules::default(), false);
        let (_, _, failed) = route_board(&mut r, 2, 4, 40);
        assert_eq!(failed, 0);
        assert_eq!(r.flag_never_routed(), 0, "a fully routed board flags nothing");
        let net = r.nets.iter().position(|n| n.plane.is_none() && n.clusters.len() >= 2 && !n.done_by_board && !n.routes.is_empty()).unwrap();
        r.rip_keeping(net, false);
        r.nets[net].failed.clear();
        r.nets[net].routed_order = None;
        let report = r.report();
        assert_eq!(report["nets"][&r.nets[net].name]["routes"], 0);
        assert!(report["unrouted"].as_array().unwrap().is_empty(), "the silent state the issue saw");
        let added = r.flag_never_routed();
        assert_eq!(added, r.nets[net].clusters.len() - 1);
        let un = r.report()["unrouted"].as_array().unwrap().clone();
        assert_eq!(un.len(), added);
        assert!(un[0][1][1].as_str().unwrap().starts_with("never routed"), "{un:?}");
    }

    /// Issue #140: a part parked outside the outline (pads off the routing grid) no longer panics in
    /// obstacle_maps; its connections are reported unrouted with the part named, the rest route.
    #[test]
    fn a_part_off_the_board_is_reported_not_a_panic() {
        let text = BOTTOM.replace("(footprint \"T:R2\"\n\t\t(layer \"B.Cu\")\n\t\t(at 21 6)", "(footprint \"T:R2\"\n\t\t(layer \"B.Cu\")\n\t\t(at 61 46)");
        assert_ne!(text, BOTTOM);
        let b = aiflow_board::Board::from_text("off.kicad_pcb", text).unwrap();
        assert_eq!(b.parts_outside(), ["R2"]);
        let mut r = Router::new(b, crate::Rules::default(), false);
        let (_, report, failed) = route_board(&mut r, 2, 4, 40);
        let un = report["unrouted"].as_array().unwrap();
        let named: Vec<&Value> = un.iter().filter(|u| u[1][1].as_str().unwrap_or("").starts_with("R2 is outside the board outline")).collect();
        assert_eq!(named.len(), 2, "{un:?}");   // R2.1 on B, R2.2 on D
        assert!(failed >= 2);
        assert!(report["nets"]["D"]["failed"].as_array().unwrap().iter().any(|f| f[0] == "R2.2"), "{}", report["nets"]["D"]);
        // a window built from a point off the grid stays inside the grid, and maps from it are window-sized
        let w = r.window_for(&[(r.grid.w as i64 + 300, r.grid.h as i64 + 900)], 5.0);
        assert!(w.0 <= w.2 && w.1 <= w.3 && w.2 < r.grid.w as i64 && w.3 < r.grid.h as i64, "{w:?}");
        let (o, _, _, via) = r.obstacle_maps(0, 0.25, (r.grid.w as i64 + 10, -40, r.grid.w as i64 + 400, 3), false);
        assert_eq!(o[0].bits.len(), via.bits.len());
    }

    #[test]
    fn nearby_transitions_in_one_path_are_rejected() {
        let mut parent=vec![usize::MAX;200];
        parent[122]=22; parent[123]=122; parent[128]=123;
        assert!(!path_vias_clear(123,&parent,100,10,2.0*RES));
        assert!(path_vias_clear(128,&parent,100,10,2.0*RES));
        assert!(path_vias_clear(22,&parent,100,10,2.0*RES));
    }
}

/// Issue #183: single-face / no-via routing on an all through-hole strip where nets A and B must cross
/// (tests/fixtures/single-layer.kicad_pcb: J1 and J2 against the board's edges, A on J1.1, R1, J2.2 and
/// B on J1.2, J2.1, so one face alone cannot close both).
#[cfg(test)]
mod single_face_tests {
    use super::*;
    use serde_json::json;

    const STRIP: &str = include_str!("../../../tests/fixtures/single-layer.kicad_pcb");
    const BOTTOM: &str = include_str!("../../../tests/fixtures/bottom-side.kicad_pcb");

    fn strip() -> aiflow_board::Board {
        aiflow_board::Board::from_text("strip.kicad_pcb", STRIP.to_string()).unwrap()
    }

    /// Every waypoint after a path's first that names a layer: a layer change inside the path (a via).
    fn in_path_layer_changes(plan: &[Value]) -> Vec<String> {
        let mut out = Vec::new();
        for e in plan {
            for p in e["paths"].as_array().unwrap() {
                for w in p.as_array().unwrap().iter().skip(1) {
                    if w.get("layer").is_some() { out.push(format!("{} {}", e["net"], p)); }
                }
            }
        }
        out
    }

    /// The layer each path is on (paths are single-layer in this mode): its first waypoint's layer, else F.Cu.
    fn path_layers(plan: &[Value]) -> Vec<String> {
        plan.iter().flat_map(|e| e["paths"].as_array().unwrap().iter().map(|p| p[0].get("layer").and_then(|l| l.as_str()).unwrap_or("F.Cu").to_string())).collect()
    }

    #[test]
    fn single_layer_only_uses_one_face_and_reports_the_crossing() {
        let rules = crate::Rules::from_spec(&json!({"routeLayers": ["B.Cu"]}));
        assert!(!rules.default_copper_mode() && !rules.vias_allowed() && rules.jumper_layer().is_none());
        let mut r = Router::new(strip(), rules, false);
        let (plan, report, failed) = route_board(&mut r, 3, 4, 40);
        assert!(failed >= 1, "A and B must cross: one face cannot close both: {}", report["unrouted"]);
        assert!(r.vias.is_empty());
        assert!(r.nets.iter().all(|n| n.routes.iter().all(|rt| rt.cells.iter().all(|t| t.layer() == B_CU))), "copper only on B.Cu");
        assert!(path_layers(&plan).iter().all(|l| l == "B.Cu"), "{plan:?}");
        assert!(in_path_layer_changes(&plan).is_empty());
        let sf = &report["singleFace"];
        assert_eq!(sf["layers"], json!(["B.Cu"]));
        assert_eq!(sf["viasPlanned"], 0);
        assert_eq!(sf["withJumper"], 0);
        assert!(sf["singleLayer"].as_u64().unwrap() >= 1, "{sf}");
        // the open connection is A or B, with its reason (the other net in the way)
        assert!(report["unrouted"].as_array().unwrap().iter().all(|u| (u[0] == "A" || u[0] == "B") && !u[1][1].as_str().unwrap().is_empty()), "{}", report["unrouted"]);
    }

    #[test]
    fn jumpers_close_the_crossing_with_layer_changes_only_on_pth_pads() {
        let rules = crate::Rules::from_spec(&json!({"vias": false}));
        assert_eq!(rules.jumper_layer(), Some(F_CU));
        let mut r = Router::new(strip(), rules, false);
        let (plan, report, failed) = route_board(&mut r, 3, 4, 40);
        assert_eq!(failed, 0, "{}", report["unrouted"]);
        assert!(r.vias.is_empty(), "no via is ever stamped: {:?}", r.vias);
        // every layer change inside a route sits on a through-hole pad of its own net
        for (n, net) in r.nets.iter().enumerate() {
            for rt in &net.routes {
                for w in rt.cells.windows(2).filter(|w| w[0].layer() != w[1].layer()) {
                    let c = w[1].j as usize * r.grid.w + w[1].i as usize;
                    assert!(r.own_pth_cell(net.idx as i16, c) && r.pth_cluster_at(n, w[1].i, w[1].j).is_some(), "layer change off a pad in {}", net.name);
                }
            }
        }
        // the plan has no layer change inside a path: one path per face
        assert!(in_path_layer_changes(&plan).is_empty(), "{:?}", in_path_layer_changes(&plan));
        let layers = path_layers(&plan);
        assert!(layers.iter().any(|l| l == "B.Cu") && layers.iter().any(|l| l == "F.Cu"), "B.Cu milled, F.Cu jumper: {layers:?}");
        let sf = &report["singleFace"];
        assert_eq!(sf["jumperLayer"], "F.Cu");
        assert!(sf["withJumper"].as_u64().unwrap() >= 1 && sf["singleLayer"].as_u64().unwrap() >= 1, "{sf}");
        // the jumper is the exception: most connections stay on the milled face
        assert!(sf["withJumper"].as_u64().unwrap() <= sf["singleLayer"].as_u64().unwrap(), "{sf}");
    }

    #[test]
    fn with_vias_off_a_via_is_never_possible_except_on_an_own_pth_pad() {
        let mut r = Router::new(strip(), crate::Rules::from_spec(&json!({"vias": false})), false);
        let a = r.net_ids["A"];
        let win = (0, 0, r.grid.w as i64 - 1, r.grid.h as i64 - 1);
        let (_, _, _, via_ok) = r.obstacle_maps(a, 0.25, win, false);
        let nid = r.nets[a].idx as i16;
        let mut on_pads = 0;
        for (c, ok) in via_ok.bits.iter().enumerate() {
            if *ok { assert!(r.own_pth_cell(nid, c), "via allowed off A's own pads at cell {c}"); on_pads += 1; }
        }
        assert!(on_pads > 0, "A's own through-hole pads are where it may change face");
        // and B.Cu only: nowhere, and F.Cu is a wall
        let mut r = Router::new(strip(), crate::Rules::from_spec(&json!({"routeLayers": ["B.Cu"]})), false);
        let (o, _, _, via_ok) = r.obstacle_maps(a, 0.25, win, false);
        assert!(o[F_CU].bits.iter().all(|b| *b));
        let nid = r.nets[a].idx as i16;
        assert!(via_ok.bits.iter().enumerate().all(|(c, ok)| !*ok || r.own_pth_cell(nid, c)));
    }

    #[test]
    fn a_default_spec_routes_exactly_as_before() {
        let d = crate::Rules::default();
        assert!(d.default_copper_mode() && d.vias_allowed() && d.jumper_layer().is_none());
        let both = crate::Rules::from_spec(&json!({"routeLayers": ["F.Cu", "B.Cu"], "vias": true}));
        assert!(both.default_copper_mode());
        // the rules record is unchanged for a default spec (no new keys in plan-route-report.json)
        let v = serde_json::to_value(crate::Rules::from_spec(&json!({}))).unwrap();
        assert!(v.get("route_layers").is_none() && v.get("vias").is_none(), "{v}");
        assert!(serde_json::to_value(crate::Rules::from_spec(&json!({"vias": false}))).unwrap()["vias"] == json!(false));
        for text in [BOTTOM, STRIP] {
            let mut a = Router::new(aiflow_board::Board::from_text("a.kicad_pcb", text.to_string()).unwrap(), crate::Rules::default(), false);
            let mut b = Router::new(aiflow_board::Board::from_text("a.kicad_pcb", text.to_string()).unwrap(), both.clone(), false);
            let (pa, ra, fa) = route_board(&mut a, 3, 4, 40);
            let (pb, rb, fb) = route_board(&mut b, 3, 4, 40);
            assert_eq!(serde_json::to_string(&pa).unwrap(), serde_json::to_string(&pb).unwrap());
            assert_eq!(fa, fb);
            assert!(ra.get("singleFace").is_none() && rb.get("singleFace").is_none());
        }
    }
}