AI Flow

//! adom-aiflow's routing engine: a grid maze router for any KiCad 10 board.
//!
//! 0.1 mm grid over the outline, two signal layers (F.Cu, B.Cu), through vias between them
//! (0.6/0.3 mm for signals, 0.8/0.4 on the wide power nets), the board's rules plus every per-pad
//! clearance override. A* per connection (octilinear, +cost per via and per turn, F.Cu preferred),
//! obstacles per layer for the net being routed (every other net's copper dilated by clearance
//! plus half the track width), narrow pins entered on their axis through a reserved escape stub,
//! same-net overlapping pads clustered, each net routed as a minimum spanning tree onto its own
//! copper, shortest nets first, plane nets stubbed to a via, rip-up with history cost when a
//! connection fails, multi-pass with the failed nets first, and Kelvin sense taps routed first as
//! dedicated traces that the rest of their net treats as foreign copper.
//!
//!
//! Copper already on the board (an adopted or partly routed board) is fixed: its tracks and vias are
//! obstacles for every other net, and connections it already makes are not planned again. A spec's
//! planeUnder regions are keepouts for every net but their own on their layer.
//!
//! Output: a plan, a list of `kicad_route_net` calls ({net, width, viaSize, viaDrill, paths}).
pub mod board_copper;
pub mod copper_path;
pub mod decoupling;
pub mod signal_priority;
pub mod neckdown;
pub mod drive;
pub mod impedance;
pub mod plane_under;
pub mod rules;
pub mod simplify;
pub mod variants;

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

use aiflow_board::{geom, Board, Pad, Pt, B_CU, F_CU};
use aiflow_grid::{Grid, Mask, RES};

pub use rules::Rules;

pub const COST_ORTH: i64 = 10;
pub const COST_DIAG: i64 = 14;
pub const COST_VIA: i64 = 250;
pub const COST_TURN: i64 = 4;
/// What a change of direction adds to a step (issue #127). A 90 degree corner costs more than the two
/// 45 degree turns that replace it, and a sharper one more again, so the search rounds its corners.
/// With `flat` every turn costs the same, which gives up some corners to fit a crowded board.
/// `from` and `to` index DIRS.
pub fn turn_cost(from: usize, to: usize, flat: bool) -> i64 {
    let eighths = |d: usize| match DIRS[d] { (1, 0) => 0, (1, 1) => 1, (0, 1) => 2, (-1, 1) => 3, (-1, 0) => 4, (-1, -1) => 5, (0, -1) => 6, _ => 7 };
    let diff = (eighths(from) - eighths(to) as i32).rem_euclid(8);
    match diff.min(8 - diff) { 0 => 0, 1 => COST_TURN, _ if flat => COST_TURN, 2 => 3 * COST_TURN, 3 => 5 * COST_TURN, _ => 7 * COST_TURN }
}
pub const LAYER_MULT: [f64; 2] = [1.0, 1.1];
/// Issue #183, single-face boards with F.Cu jumpers: the milled face (B.Cu) is the cheaper layer, and
/// entering the jumper layer (a wire on the component side) costs as much as a 30 mm detour.
pub const JUMPER_LAYER_MULT: [f64; 2] = [1.2, 1.0];
pub const JUMPER_COST: i64 = 3000;
pub const SOFT_EXTRA: i64 = 80;
pub const ZONE_COST: i64 = 20;
pub const VIA_WALL: i64 = 300;
pub const HIST_COST: i64 = 12;
/// Extra cost per step for the second net of an impedance pair off its partner's coupling line.
pub const PAIR_OFF: i64 = 10;
pub const DIRS: [(i32, i32); 8] = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)];
pub const STEP: [i64; 8] = [10, 10, 10, 10, 14, 14, 14, 14];
pub const INF: i64 = 1 << 40;

/// Half a cell diagonal: pads and stubs are off-grid. (Adding a margin here crosses a cell
/// boundary in the dilation radius and chokes the 0.5 mm-pitch escapes; a net that lands a hair
/// under the rule gets a per-net clearance from the spec instead: netClearance.)
pub fn slop() -> f64 {
    0.05 * std::f64::consts::SQRT_2 + 1e-6
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Term {
    pub l: u8,
    pub i: i32,
    pub j: i32,
}

impl Term {
    pub fn new(l: usize, i: i64, j: i64) -> Term {
        Term { l: l as u8, i: i as i32, j: j as i32 }
    }
    pub fn layer(&self) -> usize {
        self.l as usize
    }
}

#[derive(Clone, Debug)]
pub struct Cluster {
    pub idx: usize,
    pub pads: Vec<usize>,
    pub primary: usize,
    pub terminals: Vec<Term>,
    pub escapes: HashMap<Term, Pt>,
    pub corridors: HashMap<Term, Pt>,
    pub connected: bool,
    pub allow: f64,
    pub released: HashSet<Term>,
}

impl Cluster {
    pub fn key<'a>(&self, board: &'a Board) -> &'a str {
        &board.pads[self.primary].key
    }
    pub fn xy(&self, board: &Board) -> Pt {
        (board.pads[self.primary].x, board.pads[self.primary].y)
    }
}

#[derive(Clone, Debug)]
pub enum End {
    Pad(usize, Term),
    Escape(usize, Term),
    Copper,
    Via,
}

impl End {
    pub fn cluster(&self) -> Option<usize> {
        match self {
            End::Pad(c, _) | End::Escape(c, _) => Some(*c),
            _ => None,
        }
    }
    pub fn term(&self) -> Option<Term> {
        match self {
            End::Pad(_, t) | End::Escape(_, t) => Some(*t),
            _ => None,
        }
    }
}

#[derive(Clone, Debug)]
pub struct Route {
    pub cells: Vec<Term>,
    pub width: f64,
    pub start: End,
    pub end: End,
    pub breaks: HashSet<usize>,
    pub via_end: bool,
    pub via_end_layer: usize,
    pub kelvin: bool,
    /// The spec decoupling pair (index into `Router::pairs`) this route is the direct connection of:
    /// routed before the rail and kept through rip-up (decoupling.rs).
    pub pair: Option<usize>,
}

impl Route {
    pub fn new(cells: Vec<Term>, width: f64, start: End, end: End) -> Route {
        Route { cells, width, start, end, breaks: HashSet::new(), via_end: false, via_end_layer: B_CU, kelvin: false, pair: None }
    }
}

#[derive(Clone, Debug)]
pub struct NetState {
    pub idx: usize,
    pub name: String,
    pub pads: Vec<usize>,
    pub clusters: Vec<Cluster>,
    pub routes: Vec<Route>,
    pub widths: Vec<f64>,
    pub plane: Option<String>,
    pub mst_len: f64,
    pub used_escapes: HashSet<(usize, Term)>,
    pub failed: Vec<(String, String)>,
    pub rips: usize,
    pub routed_order: Option<usize>,
    pub via_in_pad: Vec<String>,
    pub last_soft: Vec<Term>,
    pub via: f64,
    pub drill: f64,
    /// Every cluster of the net is already joined by the board's own copper: nothing to route.
    pub done_by_board: bool,
    /// Issue #140: pads of this net the router cannot reach because they lie off the board (their part
    /// is outside the outline, or the pad is off the routing grid), with the reason; never routed,
    /// always reported as unrouted.
    pub outside: Vec<(String, String)>,
}

#[derive(Clone)]
pub struct Snapshot {
    pub nets: Vec<(Vec<Route>, HashSet<(usize, Term)>, Vec<(String, String)>, Vec<String>, Option<usize>)>,
}

pub struct Router {
    pub board: Board,
    pub grid: Grid,
    pub rules: Rules,
    pub verbose: bool,
    pub nets: Vec<NetState>,
    pub net_ids: HashMap<String, usize>,
    pub pad_raw: [Vec<i16>; 2],
    pub pad_owner: [Vec<i16>; 2],
    pub route_raw: [Vec<i16>; 2],
    pub big_clr: [Mask; 2],
    pub big_clr_val: f64,
    pub smd_pad_cells: HashMap<usize, Mask>,
    pub thru_cells: Mask,
    pub history: [Vec<i16>; 2],
    pub chan_count: Vec<i16>,
    pub chan_lines: HashMap<(usize, usize, Term), Vec<usize>>,
    pub vias: Vec<(i32, i32, usize, f64, f64)>,
    pub fp_index: HashMap<String, usize>,
    /// cells of each pad, by its index in board.pads (a key may name two pads: issue #93)
    pub pad_cells: HashMap<usize, Vec<usize>>,
    pub inside: Mask,
    pub edge_dist: Vec<f32>,
    pub inside_w: HashMap<i64, Mask>,
    pub rip_total: usize,
    /// Every turn costs the same in the search: the later passes of a board that will not close (issue #127).
    pub flat_turns: bool,
    pub stats: HashMap<String, i64>,
    pub kelvin_owner: HashMap<usize, usize>,
    pub kelvin_clusters: HashSet<(usize, usize)>,
    pub body_owner: Vec<i16>,
    pub ic_zone: Mask,
    pub ic_nets: HashMap<usize, HashSet<usize>>,
    pub log_lines: Vec<String>,
    /// The board's own tracks and vias, per layer: net id, -2 for copper on no known net, -1 empty.
    pub fixed_raw: [Vec<i16>; 2],
    pub fixed_tracks: Vec<aiflow_board::Track>,
    pub fixed_vias: Vec<aiflow_board::Via>,
    /// Per pad: the group of pads the board's own copper already joins (its own index when none).
    pub pad_comp: Vec<usize>,
    pub comp_copper: HashMap<usize, board_copper::CompCopper>,
    /// Per net: landing cells on its fixed copper, with the group each belongs to.
    pub fixed_targets: HashMap<usize, Vec<(usize, Term)>>,
    /// planeUnder regions and, per layer, the region index owning each cell (-1 none).
    pub keep: Vec<plane_under::Region>,
    pub keep_raw: [Vec<i16>; 2],
    /// Spec decoupling pairs resolved on this board (decoupling.rs).
    pub pairs: Vec<decoupling::PairState>,
    /// The signal-net order (`route --variants`, variants.rs); the default is shortest first.
    pub order: variants::NetOrder,
}

impl Router {
    pub fn log(&mut self, s: String) {
        if self.verbose {
            eprintln!("{s}");
        }
        self.log_lines.push(s);
    }

    pub fn stat(&mut self, k: &str, d: i64) {
        *self.stats.entry(k.to_string()).or_insert(0) += d;
    }

    pub fn new(board: Board, rules: Rules, verbose: bool) -> Router {
        let grid = Grid::new(board.bbox);
        let n = grid.w * grid.h;
        let mut names: Vec<&String> = board.nets.keys().collect();
        names.sort();
        let mut nets = Vec::new();
        let mut net_ids = HashMap::new();
        for (k, name) in names.iter().enumerate() {
            net_ids.insert((*name).clone(), k);
            nets.push(NetState {
                idx: k, name: (*name).clone(), pads: board.nets[*name].clone(), clusters: Vec::new(), routes: Vec::new(),
                widths: vec![rules.track], plane: rules.planes.get(*name).cloned(), 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: rules.via_small, drill: rules.drill_small, done_by_board: false, outside: Vec::new(),
            });
        }
        let mut refs: Vec<&String> = board.footprints.keys().collect();
        refs.sort();
        let fp_index: HashMap<String, usize> = refs.iter().enumerate().map(|(i, r)| ((*r).clone(), i)).collect();
        let (mut inside, mut edge_dist) = grid.outline_distance(&board.outline);
        // Edge.Cuts cutouts (a bore, a slot) are outside the board, and their edges keep the same
        // edge clearance as the outline (issue #77)
        for cut in &board.outline_cutouts {
            let (in_cut, d_cut) = grid.outline_distance(cut);
            for j in 0..grid.h {
                for i in 0..grid.w {
                    if in_cut.get(i, j) { inside.set(i, j, false); }
                    let k = j * grid.w + i;
                    if d_cut[k] < edge_dist[k] { edge_dist[k] = d_cut[k]; }
                }
            }
        }
        let mut r = Router {
            grid: grid.clone(), rules, verbose, nets, net_ids,
            pad_raw: [vec![-1; n], vec![-1; n]], pad_owner: [vec![-1; n], vec![-1; n]], route_raw: [vec![-1; n], vec![-1; n]],
            big_clr: [grid.mask(), grid.mask()], big_clr_val: 0.0, smd_pad_cells: HashMap::new(), thru_cells: grid.mask(),
            history: [vec![0; n], vec![0; n]], chan_count: vec![0; n], chan_lines: HashMap::new(), vias: Vec::new(), fp_index,
            pad_cells: HashMap::new(), inside, edge_dist, inside_w: HashMap::new(), rip_total: 0, flat_turns: false, stats: HashMap::new(), kelvin_owner: HashMap::new(), kelvin_clusters: HashSet::new(),
            body_owner: vec![-1; n], ic_zone: grid.mask(), ic_nets: HashMap::new(), log_lines: Vec::new(),
            fixed_raw: [vec![-1; n], vec![-1; n]], fixed_tracks: Vec::new(), fixed_vias: Vec::new(), pad_comp: Vec::new(), comp_copper: HashMap::new(), fixed_targets: HashMap::new(),
            keep: Vec::new(), keep_raw: [vec![-1; n], vec![-1; n]], pairs: Vec::new(), order: variants::NetOrder::default(), board,
        };
        r.big_clr_val = r.rules.clearance;
        // issue #183: a board with no vias has no plane to stitch down to; its plane nets are routed as
        // tracks like any other net (a pour can still be added after routing)
        if !r.rules.vias_allowed() {
            let planes: Vec<String> = r.nets.iter_mut().filter_map(|n| n.plane.take().map(|_| n.name.clone())).collect();
            let layers: Vec<&str> = (0..2).filter(|&l| r.rules.layer_allowed(l)).map(|l| aiflow_board::LAYER_NAMES[l]).collect();
            r.log(format!("router: single-face mode: layers {}, no vias (a layer change only at a through-hole pad of the same net){}", layers.join(" + "),
                if planes.is_empty() { String::new() } else { format!("; plane net(s) {} routed as tracks (no via can reach a plane)", planes.join(", ")) }));
        }
        let t0 = std::time::Instant::now();
        r.set_aside_outside_pads();
        r.stamp_pads();
        r.stamp_holes();
        r.stamp_board_copper();
        r.stamp_plane_under();
        r.build_clusters();
        r.build_ic_zones();
        r.init_decoupling();
        let count = r.nets.iter().filter(|n| (n.clusters.len() >= 2 || n.plane.is_some()) && !n.done_by_board).count();
        r.log(format!("router: {} x {} cells, {} pads stamped, {} nets to route, init {:.1}s", r.grid.w, r.grid.h, r.board.pads.len(), count, t0.elapsed().as_secs_f64()));
        r
    }

    /// Issue #140: a part left outside the outline (pack found it no spot) has pads off the routing grid,
    /// and a window built from them indexed past the grid (a panic in obstacle_maps). Such pads never
    /// join a cluster: each is recorded on its net's `outside` list, with the part named, and reported
    /// as an unrouted connection. A part that only overhangs the edge keeps its on-grid pads.
    fn set_aside_outside_pads(&mut self) {
        let off_board = self.board.parts_outside();
        for net in 0..self.nets.len() {
            let routable = self.nets[net].pads.len() >= 2 || self.nets[net].plane.is_some();
            let pads = std::mem::take(&mut self.nets[net].pads);
            let mut keep = Vec::with_capacity(pads.len());
            for pi in pads {
                let p = &self.board.pads[pi];
                let (i, j) = self.grid.to_cell(p.x, p.y);
                let why = if off_board.contains(&p.reference) {
                    Some(format!("{} is outside the board outline; move it inside (did `place pack` place one part fewer than asked?), then route again", p.reference))
                } else if !self.grid.in_bounds(i, j) {
                    Some(format!("pad {} of {} lies outside the board outline (off the routing grid); move {} inside, then route again", p.key, p.reference, p.reference))
                } else { None };
                match why {
                    Some(w) => if routable { self.nets[net].outside.push((p.key.clone(), w)); },
                    None => keep.push(pi),
                }
            }
            self.nets[net].pads = keep;
        }
        let n: usize = self.nets.iter().map(|n| n.outside.len()).sum();
        if n > 0 {
            let parts: Vec<String> = off_board.clone();
            self.log(format!("router: {n} pad(s) set aside off the board{}", if parts.is_empty() { String::new() } else { format!(" (outside the outline: {})", parts.join(", ")) }));
        }
    }

    // -- stamping --------------------------------------------------------------------
    fn stamp_pads(&mut self) {
        let g = self.grid.clone();
        let pads: Vec<Pad> = self.board.pads.clone();
        for (pi, p) in pads.iter().enumerate() {
            let nid = self.net_ids.get(&p.net).map(|&k| k as i16).unwrap_or(-2); // -1 is empty; -2 is physical, unassigned copper.
            let mut m = g.mask();
            for poly in &p.polys {
                g.poly_mask(poly, &mut m);
            }
            if let Some(d) = p.drill {
                for c in g.disk_cells((p.x, p.y), d / 2.0, None) {
                    m.bits[c] = true;
                }
            }
            let cells: Vec<usize> = m.bits.iter().enumerate().filter(|(_, b)| **b).map(|(i, _)| i).collect();
            self.pad_cells.insert(pi, cells.clone());
            let layers: Vec<usize> = if p.thru { vec![F_CU, B_CU] } else if p.on_f { vec![F_CU] } else { vec![B_CU] };
            let fpi = self.fp_index[&p.reference] as i16;
            for &l in &layers {
                for &c in &cells {
                    self.pad_raw[l][c] = nid;
                    self.pad_owner[l][c] = fpi;
                    if p.clearance > self.rules.clearance {
                        self.big_clr[l].bits[c] = true;
                    }
                }
                if p.clearance > self.rules.clearance {
                    self.big_clr_val = self.big_clr_val.max(p.clearance);
                }
            }
            if !p.thru && nid >= 0 {
                let sm = self.smd_pad_cells.entry(nid as usize).or_insert_with(|| g.mask());
                for &c in &cells {
                    sm.bits[c] = true;
                }
            }
            if p.thru {
                for &c in &cells {
                    self.thru_cells.bits[c] = true;
                }
            }
        }
    }

    /// Drilled holes with no copper (mask-only NPTH): physical obstacles on both layers, like an
    /// unnumbered copper hole, so tracks keep clearance and vias keep hole clearance. They are not
    /// pads, so they never join a net or a cluster.
    fn stamp_holes(&mut self) {
        let g = self.grid.clone();
        let holes = self.board.holes.clone();
        for h in &holes {
            let mut m = g.mask();
            g.poly_mask(&h.poly, &mut m);
            for c in g.disk_cells((h.x, h.y), h.size.0.min(h.size.1) / 2.0, None) {
                m.bits[c] = true;
            }
            let fpi = self.fp_index.get(&h.reference).map(|&k| k as i16).unwrap_or(-1);
            for c in m.bits.iter().enumerate().filter(|(_, b)| **b).map(|(i, _)| i) {
                for l in [F_CU, B_CU] {
                    if self.pad_raw[l][c] == -1 {
                        self.pad_raw[l][c] = -2;
                        self.pad_owner[l][c] = fpi;
                    }
                }
                self.thru_cells.bits[c] = true;
            }
        }
    }

    /// Resolve the planeUnder regions and mark their cells. A region the board cannot resolve is
    /// logged and skipped here; `route` refuses such a spec before it builds a router.
    fn stamp_plane_under(&mut self) {
        let regions = match plane_under::regions(&self.board, &self.rules.plane_under) {
            Ok(r) => r,
            Err(e) => {
                self.log(format!("planeUnder: {e}; no region applied"));
                return;
            }
        };
        let g = self.grid.clone();
        for (k, reg) in regions.iter().enumerate() {
            let mut m = g.mask();
            g.poly_mask(&reg.poly, &mut m);
            let mut cells = 0;
            for (c, b) in m.bits.iter().enumerate() {
                if *b {
                    self.keep_raw[reg.layer][c] = k as i16;
                    cells += 1;
                }
            }
            self.log(format!("  planeUnder {}: {:.1} mm2 of {} kept for {} (a keepout for every other net)", reg.label, cells as f64 * RES * RES, aiflow_board::LAYER_NAMES[reg.layer], reg.net));
        }
        self.keep = regions;
    }

    /// Is this cell of the layer inside a planeUnder region that belongs to another net?
    pub fn kept_from(&self, net_name: &str, l: usize, c: usize) -> bool {
        let k = self.keep_raw[l][c];
        k >= 0 && self.keep[k as usize].net != net_name
    }

    pub fn inside_for(&mut self, w: f64) -> &Mask {
        let key = (w * 1000.0).round() as i64;
        if !self.inside_w.contains_key(&key) {
            let mut m = self.inside.clone();
            let need = (self.rules.edge + w / 2.0 + slop()) as f32;
            for (b, d) in m.bits.iter_mut().zip(&self.edge_dist) {
                *b = *b && *d >= need;
            }
            self.inside_w.insert(key, m);
        }
        &self.inside_w[&key]
    }

    pub fn stamp_route(&mut self, net: usize, route: &Route, sign: i32) {
        let g = self.grid.clone();
        let nid = if sign > 0 { self.nets[net].idx as i16 } else { -1 };
        let cells = &route.cells;
        let mut k = 0;
        while k + 1 < cells.len() {
            let (l, i0, j0) = (cells[k].layer(), cells[k].i, cells[k].j);
            let mut m = k + 1;
            let (di, dj) = (cells[m].i - i0, cells[m].j - j0);
            while m + 1 < cells.len() && cells[m + 1].layer() == l && cells[m].layer() == l && (cells[m + 1].i - cells[m].i, cells[m + 1].j - cells[m].j) == (di, dj) {
                m += 1;
            }
            if cells[m].layer() == l {
                let a = g.to_xy(i0 as i64, j0 as i64);
                let b = g.to_xy(cells[m].i as i64, cells[m].j as i64);
                for c in g.segment_cells(a, b, route.width / 2.0, Some(1e-6)) {
                    self.route_raw[l][c] = nid;
                }
            }
            k = m;
        }
        // issue #183: with vias off a layer change is a through-hole pad of the net, never a via
        let vias = self.rules.vias_allowed();
        for k in 1..cells.len() {
            if vias && cells[k].layer() != cells[k - 1].layer() && (cells[k].i, cells[k].j) == (cells[k - 1].i, cells[k - 1].j) {
                self.stamp_via(cells[k].i, cells[k].j, net, sign);
            }
        }
        if route.via_end {
            let t = *cells.last().unwrap();
            self.stamp_via(t.i, t.j, net, sign);
        }
    }

    fn stamp_via(&mut self, i: i32, j: i32, net: usize, sign: i32) {
        let g = self.grid.clone();
        let (via, drill, nid) = (self.nets[net].via, self.nets[net].drill, self.nets[net].idx);
        let xy = g.to_xy(i as i64, j as i64);
        for c in g.disk_cells(xy, via / 2.0, Some(1e-6)) {
            for l in 0..2 {
                self.route_raw[l][c] = if sign > 0 { nid as i16 } else { -1 };
            }
        }
        if sign > 0 {
            self.vias.push((i, j, nid, via, drill));
        } else {
            self.vias.retain(|v| !(v.0 == i && v.1 == j && v.2 == nid));
        }
    }

    /// Centre-to-centre distance this net's via must keep from a via of (nid, dia, drill).
    pub fn via_gap(&self, net: usize, nid: usize, dia: f64, drill: f64) -> f64 {
        let n = &self.nets[net];
        if nid == n.idx {
            (n.drill + drill) / 2.0 + self.rules.hole_to_hole + slop()
        } else {
            n.via / 2.0 + dia / 2.0 + self.rules.clearance + slop()
        }
    }

    pub fn stamp_stub(&mut self, net: usize, cluster: usize, term: Term, sign: i32) {
        let g = self.grid.clone();
        let l = term.layer();
        let cl = self.nets[net].clusters[cluster].clone();
        let p = self.board.pads[cl.primary].clone();
        let a = p.polys_centre;
        let b = g.to_xy(term.i as i64, term.j as i64);
        let nid = if sign > 0 { self.nets[net].idx as i16 } else { -1 };
        let fpi = self.fp_index[&p.reference] as i16;
        for c in g.segment_cells(a, b, self.stub_for(net) / 2.0, Some(1e-6)) {
            self.pad_raw[l][c] = nid;
            if sign > 0 {
                self.pad_owner[l][c] = fpi;
            }
        }
        if let Some(kend) = cl.corridors.get(&term) {
            for c in g.segment_cells(b, *kend, self.rules.track / 2.0, Some(1e-6)) {
                self.pad_raw[l][c] = nid;
                if sign > 0 {
                    self.pad_owner[l][c] = fpi;
                }
            }
        }
        self.stamp_channel(net, cluster, term, sign);
        if sign < 0 {
            let cells = self.pad_cells[&cl.primary].clone();
            let real = self.nets[net].idx as i16;
            for c in cells {
                self.pad_raw[l][c] = real;
                self.pad_owner[l][c] = fpi;
            }
        }
    }

    fn stamp_channel(&mut self, net: usize, cluster: usize, term: Term, sign: i32) {
        let key = (self.nets[net].idx, cluster, term);
        if sign > 0 && self.chan_lines.contains_key(&key) {
            return;
        }
        if sign < 0 {
            if let Some(cells) = self.chan_lines.remove(&key) {
                for c in cells {
                    self.chan_count[c] -= 1;
                }
            }
            return;
        }
        let g = self.grid.clone();
        let cl = &self.nets[net].clusters[cluster];
        let p = &self.board.pads[cl.primary];
        let b = g.to_xy(term.i as i64, term.j as i64);
        let (ax, ay) = p.long_axis;
        let (cx, cy) = p.polys_centre;
        let sgn = if (b.0 - cx) * ax + (b.1 - cy) * ay > 0.0 { 1.0 } else { -1.0 };
        let rax = (ax * 1e6).round() / 1e6;
        let ray = (ay * 1e6).round() / 1e6;
        let cend = (b.0 + sgn * rax * self.rules.channel, b.1 + sgn * ray * self.rules.channel);
        let r = self.nets[net].via / 2.0 + self.rules.clearance + self.rules.track / 2.0 + slop();
        let via = self.nets[net].via;
        let cells: Vec<usize> = g.segment_cells(b, cend, r, Some(0.0));
        let inside = self.inside_for(via).clone();
        let cells: Vec<usize> = cells.into_iter().filter(|&c| inside.bits[c]).collect();
        for &c in &cells {
            self.chan_count[c] += 1;
        }
        self.chan_lines.insert(key, cells);
    }

    // -- clusters and terminals ----------------------------------------------------
    fn build_clusters(&mut self) {
        let nnets = self.nets.len();
        for net in 0..nnets {
            if self.nets[net].pads.len() < 2 && self.nets[net].plane.is_none() {
                continue;
            }
            let mut by_fp: Vec<(String, Vec<usize>)> = Vec::new();
            for &pi in &self.nets[net].pads.clone() {
                let r = self.board.pads[pi].reference.clone();
                if let Some(e) = by_fp.iter_mut().find(|(k, _)| *k == r) {
                    e.1.push(pi);
                } else {
                    by_fp.push((r, vec![pi]));
                }
            }
            let mut clusters: Vec<Cluster> = Vec::new();
            for (_, pads) in by_fp {
                let mut groups: Vec<(Vec<usize>, HashSet<usize>)> = Vec::new();
                for pi in pads {
                    let mask: HashSet<usize> = self.pad_cells[&pi].iter().copied().collect();
                    let mut merged: Option<usize> = None;
                    let mut gi = 0;
                    while gi < groups.len() {
                        if !groups[gi].1.is_disjoint(&mask) {
                            if let Some(m) = merged {
                                let (gp, gc) = groups.remove(gi);
                                groups[m].0.extend(gp);
                                groups[m].1.extend(gc);
                                continue;
                            } else {
                                groups[gi].0.push(pi);
                                groups[gi].1.extend(mask.iter().copied());
                                merged = Some(gi);
                            }
                        }
                        gi += 1;
                    }
                    if merged.is_none() {
                        groups.push((vec![pi], mask));
                    }
                }
                for (gpads, _) in groups {
                    let primary = *gpads.iter().max_by(|&&a, &&b| {
                        let pa = &self.board.pads[a];
                        let pb = &self.board.pads[b];
                        (pa.half_long * pa.half_short).partial_cmp(&(pb.half_long * pb.half_short)).unwrap()
                    }).unwrap();
                    clusters.push(Cluster { idx: clusters.len(), pads: gpads, primary, terminals: Vec::new(), escapes: HashMap::new(), corridors: HashMap::new(), connected: false, allow: 0.25, released: HashSet::new() });
                }
            }
            self.nets[net].clusters = clusters;
            let name = self.nets[net].name.clone();
            if let Some(w) = self.rules.wide.get(&name) {
                self.nets[net].widths = w.clone();
                self.nets[net].via = self.rules.via;
                self.nets[net].drill = self.rules.drill;
            } else if let Some(w) = self.rules.mid.get(&name) {
                self.nets[net].widths = w.clone();
            }
            if let Some(ir) = self.rules.impedance.get(&name) {
                self.nets[net].widths = vec![ir.width];
                // issue #52: pins narrower than the target width: also try the rule width (a pair keeps its
                // solved pitch); neckdown::widen_plan widens it back wherever it clears
                let narrowest = self.nets[net].pads.iter().map(|&p| 2.0 * self.board.pads[p].half_short).fold(f64::INFINITY, f64::min);
                if narrowest + 0.1 < ir.width && self.rules.track < ir.width { self.nets[net].widths.push(self.rules.track); }
            }
            let count = self.nets[net].clusters.len();
            if !self.comp_copper.is_empty() {
                let plane = self.nets[net].plane.is_some();
                let first = self.comp_of(net, 0);
                let done = if plane { (0..count).all(|c| self.joined_by_board(net, c) || self.on_plane(net, c)) } else { count >= 2 && (0..count).all(|c| self.comp_of(net, c) == first) };
                if done {
                    self.nets[net].done_by_board = true;
                    for c in 0..count {
                        self.nets[net].clusters[c].connected = true;
                    }
                    continue;
                }
            }
            for c in 0..count {
                self.terminals_for(net, c);
            }
        }
        // MOSFET drain and source nets get the wide treatment too
        for p in self.board.pads.clone() {
            if p.reference.starts_with('Q') && matches!(p.name.as_str(), "1" | "2" | "3" | "5") {
                if let Some(&n) = self.net_ids.get(&p.net) {
                    if self.nets[n].plane.is_none() && !self.rules.wide.contains_key(&p.net) {
                        self.nets[n].widths = vec![1.0, 0.5, 0.25];
                        self.nets[n].via = self.rules.via;
                        self.nets[n].drill = self.rules.drill;
                    }
                }
            }
        }
    }

    fn build_ic_zones(&mut self) {
        let g = self.grid.clone();
        let mut by_fp: HashMap<String, Vec<(usize, usize)>> = HashMap::new();
        for (n, net) in self.nets.iter().enumerate() {
            for (c, cl) in net.clusters.iter().enumerate() {
                if !cl.escapes.is_empty() {
                    by_fp.entry(self.board.pads[cl.primary].reference.clone()).or_default().push((n, c));
                }
            }
        }
        let mut refs: Vec<String> = by_fp.keys().cloned().collect();
        refs.sort();
        for r in refs {
            let clusters = &by_fp[&r];
            if clusters.len() < 2 {
                continue;
            }
            let fp = &self.board.footprints[&r];
            let mut inner = Vec::new();
            for &(n, c) in clusters {
                let p = &self.board.pads[self.nets[n].clusters[c].primary];
                let (ax, ay) = p.long_axis;
                let (cx, cy) = p.polys_centre;
                let sgn = if (fp.x - cx) * ax + (fp.y - cy) * ay > 0.0 { 1.0 } else { -1.0 };
                inner.push((cx + sgn * ax * p.half_long, cy + sgn * ay * p.half_long));
            }
            let (x0, y0, x1, y1) = geom::bbox(&inner);
            if x1 - x0 < 1.0 || y1 - y0 < 1.0 {
                continue;
            }
            let (i0, j0) = g.to_cell(x0, y0);
            let (i1, j1) = g.to_cell(x1, y1);
            let idx = self.fp_index[&r] as i16;
            for j in j0.max(0)..=j1.min(g.h as i64 - 1) {
                for i in i0.max(0)..=i1.min(g.w as i64 - 1) {
                    self.body_owner[j as usize * g.w + i as usize] = idx;
                }
            }
            let pads: Vec<&Pad> = self.board.pads.iter().filter(|q| q.reference == r).collect();
            let nets: HashSet<usize> = pads.iter().filter_map(|q| self.net_ids.get(&q.net).copied()).collect();
            let m = (self.rules.ic_zone / RES).round() as i64;
            let (px0, py0, px1, py1) = geom::bbox(&pads.iter().map(|q| (q.x, q.y)).collect::<Vec<_>>());
            let (a0, b0) = g.to_cell(px0, py0);
            let (a1, b1) = g.to_cell(px1, py1);
            for j in (b0 - m).max(0)..=(b1 + m).min(g.h as i64 - 1) {
                for i in (a0 - m).max(0)..=(a1 + m).min(g.w as i64 - 1) {
                    self.ic_zone.bits[j as usize * g.w + i as usize] = true;
                }
            }
            let foreign = self.nets.len() - nets.len();
            self.ic_nets.insert(idx as usize, nets);
            self.log(format!("  ic {}: body keepout {:.1} x {:.1} mm for {} foreign nets, escape band +{}/cell", r, (i1 - i0) as f64 * RES, (j1 - j0) as f64 * RES, foreign, ZONE_COST));
        }
    }

    fn terminals_for(&mut self, net: usize, c: usize) {
        let g = self.grid.clone();
        let primary = self.nets[net].clusters[c].primary;
        let p = self.board.pads[primary].clone();
        let md = p.min_dim();
        self.nets[net].clusters[c].allow = if md >= 1.0 { 1.0 } else if md >= 0.5 { 0.5 } else { 0.25 };
        if p.thru {
            let (i, j) = g.to_cell(p.x, p.y);
            self.nets[net].clusters[c].terminals = vec![Term::new(F_CU, i, j), Term::new(B_CU, i, j)];
            return;
        }
        let l = if p.on_f { F_CU } else { B_CU };
        let narrow = md < self.rules.narrow && p.half_long > p.half_short * 1.4;
        // a pad the board's own copper already reaches is joined where it is: no escape stub of its own
        if !narrow || self.joined_by_board(net, c) {
            let (i, j) = g.to_cell(p.x, p.y);
            self.nets[net].clusters[c].terminals = vec![Term::new(l, i, j)];
            return;
        }
        self.nets[net].clusters[c].allow = 0.25;
        let (cx, cy) = p.polys_centre;
        let (ax, ay) = p.long_axis;
        let rax = (ax * 1e6).round() / 1e6;
        let ray = (ay * 1e6).round() / 1e6;
        let mut found: Vec<(Term, Option<Pt>)> = Vec::new();
        for sgn in [1.0f64, -1.0] {
            let mut hit: Option<(Term, Option<Pt>)> = None;
            for corridor in [self.rules.corridor, self.rules.corridor / 2.0, 0.0] {
                let mut d = self.rules.escape;
                while d <= 1.6 && hit.is_none() {
                    let ex = cx + sgn * ax * (p.half_long + d);
                    let ey = cy + sgn * ay * (p.half_long + d);
                    let (i, j) = g.to_cell(ex, ey);
                    let (bx, by) = g.to_xy(i, j);
                    let kend = (bx + sgn * rax * corridor, by + sgn * ray * corridor);
                    if g.in_bounds(i, j) && self.escape_ok(net, &p, l, i, j, kend) {
                        hit = Some((Term::new(l, i, j), if corridor > 0.0 { Some(kend) } else { None }));
                    }
                    d += 0.1;
                }
                if hit.is_some() {
                    break;
                }
            }
            if let Some(h) = hit {
                found.push(h);
            }
        }
        if found.is_empty() {
            let (i, j) = g.to_cell(p.x, p.y);
            self.nets[net].clusters[c].terminals = vec![Term::new(l, i, j)];
            return;
        }
        self.nets[net].clusters[c].terminals = found.iter().map(|(t, _)| *t).collect();
        for (t, kend) in found {
            let xy = g.to_xy(t.i as i64, t.j as i64);
            self.nets[net].clusters[c].escapes.insert(t, xy);
            if let Some(k) = kend {
                self.nets[net].clusters[c].corridors.insert(t, k);
            }
            self.stamp_stub(net, c, t, 1);
        }
    }

    fn escape_ok(&mut self, net: usize, p: &Pad, l: usize, i: i64, j: i64, corridor_end: Pt) -> bool {
        let g = self.grid.clone();
        let track = self.rules.track;
        if !self.inside_for(track).get(i as usize, j as usize) {
            return false;
        }
        let b = g.to_xy(i, j);
        let a = p.polys_centre;
        let mut checks = vec![(a, b, self.stub_for(net) / 2.0)];
        if (b.0 - corridor_end.0).hypot(b.1 - corridor_end.1) > 1e-6 {
            let (ki, kj) = g.to_cell(corridor_end.0, corridor_end.1);
            if !g.in_bounds(ki, kj) || !self.inside_for(track).get(ki as usize, kj as usize) {
                return false;
            }
            checks.push((b, corridor_end, track / 2.0));
        }
        let mut samples: Vec<(f64, f64, f64)> = Vec::new();
        for (s0, s1, hw) in checks {
            let n = (((s1.0 - s0.0).hypot(s1.1 - s0.1)) / 0.05).ceil().max(1.0) as usize;
            for k in 0..=n {
                let t = k as f64 / n as f64;
                samples.push((s0.0 + (s1.0 - s0.0) * t, s0.1 + (s1.1 - s0.1) * t, hw));
            }
        }
        samples.push((b.0, b.1, track / 2.0));
        let reach = 2.5;
        let net_name = self.nets[net].name.clone();
        if !self.fixed_tracks.is_empty() || !self.fixed_vias.is_empty() || !self.keep.is_empty() {
            for &(x, y, hw) in &samples {
                if self.fixed_blocks(&net_name, Some(l), x, y, hw + self.rules.clearance) {
                    return false;
                }
                let (ci, cj) = g.to_cell(x, y);
                if g.in_bounds(ci, cj) && self.kept_from(&net_name, l, cj as usize * g.w + ci as usize) {
                    return false;
                }
            }
        }
        for q in &self.board.pads {
            if q.reference == p.reference || q.net == net_name {
                continue;
            }
            if (q.x - b.0).abs() > reach + q.half_long || (q.y - b.1).abs() > reach + q.half_long {
                continue;
            }
            // only copper on the escape's own layer is in its way (a bottom pad's escape passes over top pads)
            if !q.thru && !q.on_layer(l) {
                continue;
            }
            let clr = self.rules.clearance.max(q.clearance);
            for poly in &q.polys {
                for &(x, y, hw) in &samples {
                    if geom::point_poly_distance(x, y, poly) < hw + clr {
                        return false;
                    }
                }
            }
        }
        // a drilled hole with no copper blocks escapes of its own footprint too (a USB-C shell peg)
        for h in &self.board.holes {
            if (h.x - b.0).abs() > reach + h.diameter() || (h.y - b.1).abs() > reach + h.diameter() {
                continue;
            }
            for &(x, y, hw) in &samples {
                if geom::point_poly_distance(x, y, &h.poly) < hw + self.rules.clearance {
                    return false;
                }
            }
        }
        true
    }

    // -- obstacle maps ---------------------------------------------------------------
    /// (obs_o, obs_d, soft, via_ok) for the window (i0, j0, i1, j1 inclusive), each a Mask of window size.
    pub fn obstacle_maps(&mut self, net: usize, width: f64, win: (i64, i64, i64, i64), soft: bool) -> ([Mask; 2], [Mask; 2], [Option<Mask>; 2], Mask) {
        let g = self.grid.clone();
        // a window always lies inside the grid (window_for clamps it); a hand-made one is clamped here too
        let (wx, hy) = (g.w as i64 - 1, g.h as i64 - 1);
        let (i0, j0) = (win.0.clamp(0, wx), win.1.clamp(0, hy));
        let (i1, j1) = (win.2.clamp(i0, wx), win.3.clamp(j0, hy));
        let clr = self.rules.clearance.max(self.rules.net_clearance.get(&self.nets[net].name).copied().unwrap_or(0.0));
        let r_o = (clr + width / 2.0 + slop()) / RES;
        let r_d = r_o + 0.0707 / RES;
        let r_big = (self.big_clr_val + width / 2.0 + slop()) / RES;
        let pad_r = (r_d.max(r_big)).ceil() as i64 + 1;
        let (pi0, pj0) = ((i0 - pad_r).max(0), (j0 - pad_r).max(0));
        let (pi1, pj1) = ((i1 + pad_r).min(g.w as i64 - 1), (j1 + pad_r).min(g.h as i64 - 1));
        let ww = (pi1 - pi0 + 1) as usize;
        let hh = (pj1 - pj0 + 1) as usize;
        let sub = Grid { res: g.res, x0: 0.0, y0: 0.0, w: ww, h: hh };
        let nid = self.nets[net].idx as i16;
        let via = self.nets[net].via;
        let mut via_block = Mask::new(ww, hh);
        let mut obs_o: [Mask; 2] = [Mask::new(1, 1), Mask::new(1, 1)];
        let mut obs_d: [Mask; 2] = [Mask::new(1, 1), Mask::new(1, 1)];
        let mut softm: [Option<Mask>; 2] = [None, None];
        let inside_w = self.inside_for(width).clone();
        let inside_via = self.inside_for(via).clone();
        let net_name = self.nets[net].name.clone();
        let keep_foreign: Vec<bool> = self.keep.iter().map(|k| k.net != net_name).collect();
        for l in 0..2 {
            let mut other_pads = Mask::new(ww, hh);
            let mut other_routes = Mask::new(ww, hh);
            let mut big = Mask::new(ww, hh);
            for jj in 0..hh {
                let base = (pj0 as usize + jj) * g.w + pi0 as usize;
                for ii in 0..ww {
                    let c = base + ii;
                    let pr = self.pad_raw[l][c];
                    let rr = self.route_raw[l][c];
                    let fr = self.fixed_raw[l][c];
                    let kr = self.keep_raw[l][c];
                    let op = (pr != -1 && pr != nid) || (fr != -1 && fr != nid) || (kr >= 0 && keep_foreign[kr as usize]);
                    let orr = rr != -1 && rr != nid;
                    other_pads.bits[jj * ww + ii] = op;
                    other_routes.bits[jj * ww + ii] = orr;
                    big.bits[jj * ww + ii] = self.big_clr[l].bits[c] && op;
                }
            }
            let mut hard = other_pads.clone();
            if !soft {
                hard.or_with(&other_routes);
            }
            let mut o = sub.dilate(&hard, r_o);
            o.or_with(&sub.dilate(&big, r_big));
            let mut d = sub.dilate(&hard, r_d);
            d.or_with(&sub.dilate(&big, r_big + 0.0707 / RES));
            for jj in 0..hh {
                for ii in 0..ww {
                    let c = (pj0 as usize + jj) * g.w + pi0 as usize + ii;
                    if !inside_w.bits[c] {
                        o.bits[jj * ww + ii] = true;
                    }
                }
            }
            if l == F_CU && !self.ic_nets.is_empty() {
                let foreign: Vec<i16> = self.ic_nets.iter().filter(|(_, nets)| !nets.contains(&net)).map(|(k, _)| *k as i16).collect();
                if !foreign.is_empty() {
                    for jj in 0..hh {
                        for ii in 0..ww {
                            let c = (pj0 as usize + jj) * g.w + pi0 as usize + ii;
                            let bo = self.body_owner[c];
                            if bo != -1 && foreign.contains(&bo) {
                                o.bits[jj * ww + ii] = true;
                                d.bits[jj * ww + ii] = true;
                            }
                        }
                    }
                }
            }
            let s = if soft { Some(sub.dilate(&other_routes, r_d)) } else { None };
            obs_o[l] = crop(&o, ww, i0 - pi0, j0 - pj0, i1 - pi0, j1 - pj0);
            obs_d[l] = crop(&d, ww, i0 - pi0, j0 - pj0, i1 - pi0, j1 - pj0);
            softm[l] = s.map(|m| crop(&m, ww, i0 - pi0, j0 - pj0, i1 - pi0, j1 - pj0));
            let mut hr = other_pads.clone();
            hr.or_with(&other_routes);
            // the net's own clearance (spec netClearance, which the gate's hint tells the AI to raise) and
            // the same diagonal grid margin as tracks: with the rule clearance alone a via landed 0.186 mm
            // from another net's track under a 0.2 mm rule, and raising netClearance could not move it
            via_block.or_with(&sub.dilate(&hr, (clr + via / 2.0 + slop() + 0.0707) / RES));
            via_block.or_with(&sub.dilate(&big, (self.big_clr_val + via / 2.0 + slop()) / RES));
        }
        if let Some(own) = self.smd_pad_cells.get(&(nid as usize)) {
            let mut m = Mask::new(ww, hh);
            for jj in 0..hh {
                for ii in 0..ww {
                    m.bits[jj * ww + ii] = own.bits[(pj0 as usize + jj) * g.w + pi0 as usize + ii];
                }
            }
            via_block.or_with(&sub.dilate(&m, (via / 2.0 + slop()) / RES));
        }
        {
            let mut m = Mask::new(ww, hh);
            for jj in 0..hh {
                for ii in 0..ww {
                    m.bits[jj * ww + ii] = self.thru_cells.bits[(pj0 as usize + jj) * g.w + pi0 as usize + ii];
                }
            }
            via_block.or_with(&sub.dilate(&m, (via / 2.0 + slop()) / RES));
        }
        // other vias: annular ring plus clearance for another net, hole to hole for this net
        let mut groups: HashMap<i64, Vec<(usize, usize)>> = HashMap::new();
        for &(vi, vj, vnid, dia, drill) in &self.vias {
            if vi as i64 >= pi0 && vi as i64 <= pi1 && vj as i64 >= pj0 && vj as i64 <= pj1 {
                let gap = self.via_gap(net, vnid, dia, drill);
                groups.entry((gap * 10000.0).round() as i64).or_default().push(((vj as i64 - pj0) as usize, (vi as i64 - pi0) as usize));
            }
        }
        for (gapk, cells) in groups {
            let mut vm = Mask::new(ww, hh);
            for (a, b) in cells {
                vm.bits[a * ww + b] = true;
            }
            via_block.or_with(&sub.dilate(&vm, gapk as f64 / 10000.0 / RES - 1e-6));
        }
        for jj in 0..hh {
            for ii in 0..ww {
                let c = (pj0 as usize + jj) * g.w + pi0 as usize + ii;
                if !inside_via.bits[c] {
                    via_block.bits[jj * ww + ii] = true;
                }
            }
        }
        let mut via_ok = crop(&via_block, ww, i0 - pi0, j0 - pj0, i1 - pi0, j1 - pj0);
        for b in via_ok.bits.iter_mut() {
            *b = !*b;
        }
        // an impedance-controlled net stays on the one layer its width was solved for: no vias
        if let Some(l) = self.impedance_layer(net) {
            for b in obs_o[1 - l].bits.iter_mut() {
                *b = true;
            }
            for b in via_ok.bits.iter_mut() {
                *b = false;
            }
        }
        // issue #183: a layer the spec (or the project's .kicad_dru) leaves out is a wall, and with vias
        // off the only layer change is on a through-hole pad of this net (the lead joins both faces)
        if !self.rules.default_copper_mode() {
            for l in 0..2 {
                if !self.rules.layer_allowed(l) {
                    for b in obs_o[l].bits.iter_mut() { *b = true; }
                }
            }
            if !self.rules.vias_allowed() {
                let (ww, hw) = ((i1 - i0 + 1) as usize, (j1 - j0 + 1) as usize);
                for jj in 0..hw {
                    for ii in 0..ww {
                        let c = (j0 as usize + jj) * g.w + i0 as usize + ii;
                        via_ok.bits[jj * ww + ii] = self.own_pth_cell(nid, c);
                    }
                }
            }
        }
        (obs_o, obs_d, softm, via_ok)
    }

    /// Issue #183: is grid cell `c` a through-hole pad of net id `nid` (copper of that net on both layers)?
    pub fn own_pth_cell(&self, nid: i16, c: usize) -> bool {
        self.thru_cells.bits[c] && self.pad_raw[F_CU][c] == nid && self.pad_raw[B_CU][c] == nid
    }

    /// Issue #183: the cluster of this net whose through-hole pad covers cell (i, j), if any.
    pub fn pth_cluster_at(&self, net: usize, i: i32, j: i32) -> Option<usize> {
        let c = j as usize * self.grid.w + i as usize;
        self.nets[net].clusters.iter().position(|cl| cl.pads.iter().any(|p| self.board.pads[*p].thru && self.pad_cells.get(p).is_some_and(|cells| cells.contains(&c))))
    }

    /// The width of a net's escape stubs: the rule stub, or an impedance-controlled net's own width
    /// when every one of its pads is at least that wide (so a pair leaves its pads already at the
    /// solved width and gap; a narrower pad keeps the rule stub and its breakout stays uncontrolled).
    pub fn stub_for(&self, net: usize) -> f64 {
        match self.rules.impedance.get(&self.nets[net].name) {
            Some(ir) if ir.width > self.rules.stub && self.nets[net].pads.iter().all(|&p| 2.0 * self.board.pads[p].half_short + 1e-9 >= ir.width) => ir.width,
            _ => self.rules.stub,
        }
    }

    /// The layer an impedance-controlled net is held to (impedance::table chose it).
    pub fn impedance_layer(&self, net: usize) -> Option<usize> {
        self.rules.impedance.get(&self.nets[net].name).and_then(|ir| match ir.layer.as_str() { "F.Cu" => Some(F_CU), "B.Cu" => Some(B_CU), _ => None })
    }

    /// For the second net of an impedance pair: the cells of the search window whose distance from
    /// the partner's routed centre line is the pair's centre pitch (within 0.045 mm, so one 45 degree offset line qualifies).
    /// The search charges PAIR_OFF for every step off this line, so the net follows its partner at
    /// the solved gap wherever the obstacles allow. Returns (layer, window mask).
    pub fn pair_guide(&self, net: usize, win: (i64, i64, i64, i64)) -> Option<(usize, Vec<bool>)> {
        let ir = self.rules.impedance.get(&self.nets[net].name)?;
        let (partner, pitch) = (ir.partner.as_ref()?, ir.pitch?);
        let layer = self.impedance_layer(net)?;
        let &pid = self.net_ids.get(partner)?;
        let cells: Vec<Term> = self.nets[pid].routes.iter().flat_map(|r| r.cells.iter().copied()).filter(|t| t.layer() == layer).collect();
        if cells.is_empty() {
            return None;
        }
        let (i0, j0, i1, j1) = win;
        let ww = (i1 - i0 + 1) as usize;
        let hw = (j1 - j0 + 1) as usize;
        let band = 0.045;
        let reach = ((pitch + band) / RES).ceil() as i64;
        let mut mind = vec![f64::INFINITY; ww * hw];
        for t in &cells {
            let (ci, cj) = (t.i as i64, t.j as i64);
            if ci < i0 - reach || ci > i1 + reach || cj < j0 - reach || cj > j1 + reach {
                continue;
            }
            for dj in -reach..=reach {
                let j = cj + dj;
                if j < j0 || j > j1 {
                    continue;
                }
                for di in -reach..=reach {
                    let i = ci + di;
                    if i < i0 || i > i1 {
                        continue;
                    }
                    let d = ((di * di + dj * dj) as f64).sqrt() * RES;
                    let k = (j - j0) as usize * ww + (i - i0) as usize;
                    if d < mind[k] {
                        mind[k] = d;
                    }
                }
            }
        }
        Some((layer, mind.iter().map(|d| (d - pitch).abs() <= band).collect()))
    }
}

/// Crop a window-sized mask (row stride ww) to the inclusive sub-window.
fn crop(m: &Mask, ww: usize, a: i64, b: i64, c: i64, d: i64) -> Mask {
    let w = (c - a + 1) as usize;
    let h = (d - b + 1) as usize;
    let mut out = Mask::new(w, h);
    for jj in 0..h {
        for ii in 0..w {
            out.bits[jj * w + ii] = m.bits[(b as usize + jj) * ww + a as usize + ii];
        }
    }
    out
}