AI Flow: Routing

//! Completion: what happens to a connection the first pass couldn't make, and the lanes that keep
//! fine-pitch pins from getting stuck in the first place. Three ideas, all transactional, so a
//! repair that doesn't close leaves the board exactly as it found it:
//! - Copper is the truth. What is open is read from the routed copper the way the checker reads it,
//!   so a join a fill already made isn't routed again and a join the plan forgot isn't lost.
//! - Displace, don't rip and hope. A soft search names who is in the way; those routes come up,
//!   this task goes down, and each victim must find a new place before the move is accepted.
//!   A victim keeps the parts of its route that are still legal (the splice below, from Organic
//!   Maps' AdjustRoute: search from the break to the old route and keep the old tail; VTR and
//!   nextpnr keep a route's legal part the same way). Only if that fails does it route afresh.
//! - Memory and backoff. A victim that couldn't move is banned for the next try (Freerouting's
//!   rip-up memory), and a task that fails the same way again is given up on and handed to the
//!   designer with its reason (Part 3 step 6).

use super::*;

/// Price of moving a route, nm of track: sets how far a soft search detours before it would rather
/// ask someone to move. Measured on piprobe_v13: 0.5, 1 and 2 mm land within one join of each other.
const SOFT_PRICE: f64 = 1.0 * NM;
/// Budget of a soft search and of a repair's own searches; see `pf_limit` for the small windows.
const SOFT_NODES: usize = 160_000;
const SOFT_WEIGHT: f64 = 1.5;
/// Blocker sets tried per task per round before it is left for the next round.
const REPAIR_TRIES: u32 = 4;
/// Rounds of swap moves once plain repair has stalled.
const SWAP_ROUNDS: u32 = 2;

/// One repair in progress, and how to undo it.
#[derive(Default)]
pub(super) struct Txn {
    removed: Vec<Route>,
    added: Vec<u32>,
    /// Routes laid in this repair: nothing in the same repair may take them back.
    locked: HashSet<u32>,
    /// Tasks that lost their place to a higher priority task in a swap move.
    dropped: Vec<Task>,
    banned: HashSet<(usize, usize)>,
    /// How many tasks this repair may touch, so one bad spot can't eat the whole time budget.
    fuel: i32,
    /// Each net a victim belongs to and how many pieces it was in before: a rail's tap may hang off
    /// the piece that moved, so a move is only good if no net ends up in more pieces.
    apart: HashMap<NetId, usize>,
}

#[derive(Clone, Copy)]
pub(super) struct Mode {
    /// May move higher priority data too (never pairs or Kelvin taps, 4.2).
    pub escalate: bool,
    /// May leave one lower priority victim unrouted: a sideways move that a later repair can use.
    pub swap: bool,
}

pub(super) enum Repair {
    Fixed,
    Swapped(Task),
    Failed,
}

pub(super) struct Best {
    pub score: (usize, usize, i64),
    pub routes: HashMap<u32, Route>,
    pub failed: Vec<Task>,
    pub notes: Vec<String>,
}

fn route_tie(level: Level) -> usize {
    // A hole in a higher level of the hierarchy is worse than one lower down.
    match level {
        Level::Kelvin | Level::Pair => 4,
        Level::Crystal | Level::Data => 3,
        Level::Power => 2,
        Level::PlaneFanout | Level::Other => 1,
    }
}

impl<'a> Router<'a> {
    /// A track starting at a pad's centre can break a class clearance the pads themselves are set
    /// tighter than: on benchmark B U3.1's centre line is 0.231 mm from U3.12, class 0.25 (his
    /// project excludes that DRC finding). Shifting the start across the pad, inside its copper,
    /// keeps the rule instead of bending it. Only pads whose centre fails get one.
    pub(super) fn find_pad_entries(&mut self, plan: &Plan) {
        let n = self.rules.neck;
        let half = n as f64 / 2.0;
        let pads: HashSet<usize> = plan.tasks.iter().flat_map(|t| [t.a, t.b]).collect();
        let mut found = Vec::new();
        let mut boxed = Vec::new();
        for i in pads {
            let p = &self.board.pads[i];
            let Some(layer) = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l)) else { continue };
            let c = snap(p.center);
            if self.seg_clear(c, c, layer, n, p.net, NO_NET) {
                continue;
            }
            let b = p.shape.bbox();
            let (rx, ry) = (((b.2 - b.0) / 2.0 - half).max(0.0) as i64, ((b.3 - b.1) / 2.0 - half).max(0.0) as i64);
            let mut best: Option<(i64, P)> = None;
            // Steps of 0.01 mm, plus the flush offsets where the track's edge meets the pad's edge:
            // on benchmark B U3.12 (pad 0.2, neck 0.15) only the flush 0.025 mm meets the class's
            // 0.25 mm to U3.11, and it falls between two steps.
            let mut steps: Vec<i64> = (1..=50i64).map(|k| k * 10_000).chain([rx, ry]).filter(|&d| d > 0).collect();
            steps.sort_unstable();
            steps.dedup();
            for d in steps {
                for (dx, dy) in [(d, 0), (-d, 0), (0, d), (0, -d)] {
                    if dx.abs() > rx || dy.abs() > ry {
                        continue;
                    }
                    let q = snap((c.0 + dx, c.1 + dy));
                    if p.shape.dist_pt(q.into()) <= 0.0 && self.seg_clear(q, q, layer, n, p.net, NO_NET) && best.is_none() {
                        best = Some((d, q));
                    }
                }
                if best.is_some() {
                    break;
                }
            }
            match best {
                Some((_, q)) => found.push((i, q)),
                None => boxed.push(i),
            }
        }
        // No start on these pads meets the class. Where the footprint's own pads are what box one in,
        // a local rule at the pad settles it for review; otherwise only the designer can.
        let boxed: Vec<usize> = boxed.into_iter().filter(|&i| !self.propose_pad_rule(i)).collect();
        for i in boxed {
            for t in plan.tasks.iter().filter(|t| t.a == i || t.b == i) {
                self.boxed_pads.insert((t.a, t.b), i);
            }
        }
        for (i, q) in found {
            self.log.push(format!("{}: track starts {:.3} mm off the pad centre, which is closer to a neighbour than the class clearance", self.board.pad_name(i), hypot(sub(q.into(), self.board.pads[i].center.into())) / NM));
            self.pad_entry.insert(i, q);
        }
    }

    /// Length of a path that runs inside pours of other nets (those it may cross, see World).
    pub(crate) fn pour_run(&self, net: NetId, pts: &[(P, usize)]) -> f64 {
        let mut polys: Vec<(usize, &Vec<V>)> = Vec::new();
        for (z, nets) in self.world.pour_open.iter().enumerate() {
            if nets.binary_search(&net).is_ok() {
                let zone = &self.board.zones[z];
                polys.extend(zone.layers.iter().map(|&l| (l, &zone.outline)));
            }
        }
        if polys.is_empty() {
            return 0.0;
        }
        let mut run = 0.0;
        for w in pts.windows(2).filter(|w| w[0].1 == w[1].1) {
            let (a, b): (V, V) = (w[0].0.into(), w[1].0.into());
            let m = V((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0);
            if polys.iter().any(|(l, p)| *l == w[0].1 && in_poly(m, p)) {
                run += hypot(sub(a, b));
            }
        }
        run
    }

    /// The start on pad `i` that leaves the most room to its footprint's other pads, and a local
    /// rule lowering the clearance to those pads to exactly that room, never under the standing
    /// minimum. True if a track can then start there.
    fn propose_pad_rule(&mut self, i: usize) -> bool {
        let p = self.board.pads[i].clone();
        let n = self.rules.neck;
        let half = n as f64 / 2.0;
        let Some(layer) = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l)) else { return false };
        let reference = self.board.footprints[p.fp].reference.clone();
        let near: Vec<usize> = self.board.footprints[p.fp].pads.iter().copied().filter(|&q| q != i && self.board.pads[q].net != p.net && self.board.pads[q].layers.contains(&layer)).collect();
        let c = snap(p.center);
        let b = p.shape.bbox();
        let (rx, ry) = (((b.2 - b.0) / 2.0 - half).max(0.0) as i64, ((b.3 - b.1) / 2.0 - half).max(0.0) as i64);
        let room = |s: P| near.iter().map(|&q| self.board.pads[q].shape.dist_pt(s.into()) - half).fold(f64::INFINITY, f64::min);
        let mut best = (room(c), c);
        for s in [(rx, 0), (-rx, 0), (0, ry), (0, -ry)].map(|d| snap((c.0 + d.0, c.1 + d.1))) {
            if p.shape.dist_pt(s.into()) <= 0.0 && room(s) > best.0 {
                best = (room(s), s);
            }
        }
        // To the micron below, so the rule's number is one a person can read and DRC agrees with.
        let min = (best.0 / 1000.0).floor() as i64 * 1000;
        if min < self.rules.floor.max(self.rules.min.clearance) {
            return false;
        }
        let needed: Vec<usize> = near.iter().copied().filter(|&q| {
            let o = &self.board.pads[q];
            o.shape.dist_pt(best.1.into()) - half < self.rules.clearance_for(p.net, o.net) as f64 && o.local_clearance <= min as f64
        }).collect();
        if needed.is_empty() {
            return false;
        }
        let net = self.board.net_name(p.net).to_string();
        let kept = self.rules.pad_rules.len();
        for q in needed {
            self.rules.pad_rules.push(PadRule { net: net.clone(), reference: reference.clone(), pad: self.board.pads[q].number.clone(), min });
        }
        self.rules.bind(self.board);
        if !self.seg_clear(best.1, best.1, layer, n, p.net, NO_NET) {
            self.rules.pad_rules.truncate(kept);
            self.rules.bind(self.board);
            return false;
        }
        self.log.push(format!("{}: no start on the pad meets the class, so a local rule at {:.3} mm is proposed", self.board.pad_name(i), to_mm(min)));
        self.pad_entry.insert(i, best.1);
        true
    }

    /// A way off a big pour for pad `i`: the via site within a short stub that leaves the most room to
    /// its footprint's other pads, and local rules lowering the clearance to just that room, never
    /// under the standing minimum. True if it added a rule to try. His own exit at J1 on benchmark B
    /// sits inside USB's 0.4 mm class in the same way, with those DRC findings excluded by hand.
    pub(super) fn propose_exit_rule(&mut self, i: usize) -> bool {
        if !self.pour_exit_pads.contains(&i) {
            return false;
        }
        let p = self.board.pads[i].clone();
        let net = p.net;
        let layer = p.layers[0];
        let (via_d, _) = self.rules.via_for(net);
        let vr = via_d as f64 / 2.0;
        let half = self.rules.neck as f64 / 2.0;
        let own = vr + self.rules.pad_via_gap as f64;
        let reference = self.board.footprints[p.fp].reference.clone();
        let near: Vec<usize> = self.board.footprints[p.fp].pads.iter().copied().filter(|&q| q != i && self.board.pads[q].net != net && self.board.pads[q].layers.contains(&layer)).collect();
        let c = snap(p.center);
        let room_at = |s: P| -> f64 {
            near.iter().map(|&q| {
                let o = &self.board.pads[q].shape;
                (o.dist_pt(s.into()) - vr).min(o.dist_seg(c.into(), s.into()) - half)
            }).fold(f64::INFINITY, f64::min)
        };
        let mut best: Option<(f64, P)> = None;
        for dir in 0..8usize {
            let (dx, dy) = DIRS[dir];
            for k in 1..=(self.pour_limit / 50_000.0) as i64 {
                let d = k * 50_000;
                let t = if dx != 0 && dy != 0 { (d as f64 / SQRT2) as i64 } else { d };
                let s = snap((c.0 + dx * t, c.1 + dy * t));
                if p.shape.dist_pt(s.into()) < own || self.world.mask.via_hit(net, s.into(), vr).is_some() {
                    continue;
                }
                let room = room_at(s);
                if best.map(|b| room > b.0).unwrap_or(true) {
                    best = Some((room, s));
                }
            }
        }
        let Some((room, _)) = best else { return false };
        let min = (room / 1000.0).floor() as i64 * 1000;
        if min < self.rules.floor.max(self.rules.min.clearance) {
            return false;
        }
        let name = self.board.net_name(net).to_string();
        let mut added = false;
        for &q in &near {
            let o = &self.board.pads[q];
            let number = o.number.clone();
            if (min as f64) >= self.rules.clearance_for(net, o.net) as f64 || o.local_clearance > min as f64 {
                continue;
            }
            if self.rules.pad_rules.iter().any(|r| r.net == name && r.reference == reference && r.pad == number && r.min <= min) {
                continue;
            }
            self.rules.pad_rules.retain(|r| !(r.net == name && r.reference == reference && r.pad == number));
            self.rules.pad_rules.push(PadRule { net: name.clone(), reference: reference.clone(), pad: number, min });
            added = true;
        }
        if added {
            self.rules.bind(self.board);
            self.log.push(format!("{}: no way off the pour under the class, so local rules at {:.3} mm are proposed", self.board.pad_name(i), to_mm(min)));
        }
        added
    }

    /// A proposal stands only where a track really uses it, and then the designer hears about it.
    pub(super) fn settle_pad_rules(&mut self) {
        let mut used = Vec::new();
        for rule in std::mem::take(&mut self.rules.pad_rules) {
            let Some(net) = self.board.net_ids.get(&rule.net).copied() else { continue };
            // A number can name several pads: a connector's shell pads are all SH.
            let vr = self.rules.via_for(net).0 as f64 / 2.0;
            let mut tightest: Option<(f64, f64)> = None;
            for q in self.board.pads.iter().filter(|q| q.number == rule.pad && self.board.footprints[q.fp].reference == rule.reference) {
                let class = self.rules.clearance_for(net, q.net) as f64;
                let track = self.routes.values().filter(|r| r.task.net == net).flat_map(|r| r.segs.iter()).filter(|s| q.layers.contains(&s.layer)).map(|s| q.shape.dist_seg(s.a.into(), s.b.into()) - s.width as f64 / 2.0).fold(f64::INFINITY, f64::min);
                let closest = self.routes.values().filter(|r| r.task.net == net).flat_map(|r| r.vias.iter()).map(|v| q.shape.dist_pt((*v).into()) - vr).fold(track, f64::min);
                if closest < class - DRC_TOL && tightest.map(|t| closest < t.0).unwrap_or(true) {
                    tightest = Some((closest, class));
                }
            }
            if let Some((closest, class)) = tightest {
                self.notes.push(format!("for the designer: {} passes {} {} at {:.3} mm under a proposed local rule (class {:.3} mm): no track fits its pad otherwise; review the rule in the output's .kicad_dru", rule.net, rule.reference, rule.pad, closest / NM, class / NM));
                used.push(rule);
            }
        }
        self.rules.pad_rules = used;
        self.rules.bind(self.board);
    }

    /// `pour_run` of a laid route, segment by segment: a route's segments need not join end to end.
    pub(crate) fn seg_pour_run(&self, r: &Route) -> f64 {
        r.segs.iter().map(|s| self.pour_run(r.task.net, &[(s.a, s.layer), (s.b, s.layer)])).sum()
    }

    /// The pours this board's copper would split on a refill, by net name: (net, extra pieces,
    /// cutting nets). Judged from the written board, the same way the checker judges it.
    fn pour_splits(&self) -> Vec<(String, usize, Vec<NetId>)> {
        // In id order: a hash map's order changes on every start of the program (clock.rs).
        let mut routes: Vec<&Route> = self.routes.values().collect();
        routes.sort_by_key(|r| r.id);
        let text = crate::write::render(self.board, &routes, &self.rules);
        let Ok(written) = Board::parse(text) else { return Vec::new() };
        let mut rules = self.rules.clone();
        rules.bind(&written);
        let world = build_world(&written, &rules);
        crate::pour::splits(&written, &rules, &world)
            .into_iter()
            .map(|s| (written.net_name(s.net).to_string(), s.extra, s.cutters.iter().filter_map(|&c| self.board.net_ids.get(written.net_name(c)).copied()).collect()))
            .collect()
    }

    /// Ground stitching, and the same for any poured net: where a refill would leave a piece of a
    /// pour apart from the rest of its net, a via ties it to the net's copper on another layer.
    /// The boards on the wiki do this everywhere (the designer's and another designer's have 100 to 300 vias where the
    /// router laid 20 to 60), and without it KiCad reports the pieces unconnected: on four of the
    /// first eight wiki boards the router called every join made while KiCad found 10 to 16 open
    /// (2026-11-10). Judged from the written board; a via stays only where one is legal and the
    /// net has a pour or plane on another layer there.
    pub(super) fn stitch_pours(&mut self) {
        let t0 = Instant::now();
        let (mut added, mut left) = (0usize, 0usize);
        let mut tried: HashSet<P> = HashSet::new();
        let mut tried_pairs: HashSet<(usize, usize)> = HashSet::new();
        let mut failed_pieces: HashSet<usize> = HashSet::new();
        let mut tracks = 0usize;
        let octile_p = |a: P, b: P| -> f64 {
            let (dx, dy) = ((a.0 - b.0).abs() as f64, (a.1 - b.1).abs() as f64);
            dx.max(dy) + (SQRT2 - 1.0) * dx.min(dy)
        };
        for _round in 0..60 {
            if self.over_time() {
                break;
            }
            let mut routes: Vec<&Route> = self.routes.values().collect();
            routes.sort_by_key(|r| r.id);
            let text = crate::write::render(self.board, &routes, &self.rules);
            let Ok(written) = Board::parse(text) else { return };
            let mut rules = self.rules.clone();
            rules.bind(&written);
            let world = build_world(&written, &rules);
            let nets: std::collections::BTreeSet<NetId> = written.zones.iter().filter(|z| z.net != NO_NET && !z.keepout_tracks && z.outline.len() >= 3).map(|z| z.net).collect();
            let (mut placed, mut loose) = (0usize, 0usize);
            for wnet in nets {
                let Some(&net) = self.board.net_ids.get(written.net_name(wnet)) else { continue };
                // A run asked for a few nets (a fixture) mends only those.
                if self.only.as_ref().map_or(false, |o| !o.contains(&net)) {
                    continue;
                }
                let Some(pad) = self.board.pads.iter().position(|p| p.net == net && !p.layers.is_empty()) else { continue };
                for (layer, cells, island_pads) in crate::pour::loose_islands(&written, &rules, &world, wnet) {
                    loose += 1;
                    let mut done = false;
                    // Somewhere to go: the net's pour or plane on another layer over this point.
                    let other = |c: V| self.board.zones.iter().any(|z| z.net == net && !z.keepout_tracks && z.layers.iter().any(|&l| l != layer) && in_poly(c, &z.outline));
                    let profile = Profile { width: 0, neck: 0, clearance: self.rules.clearance_for(net, net), target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None };
                    let q = Query { net, also: None, sources: &[], targets: &[], profile, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
                    for c in cells {
                        let at = crate::search::snap(to_p(c));
                        if !tried.insert(at) || !other(c) {
                            continue;
                        }
                        let (mut b, mut sc) = (Vec::new(), 0.0);
                        if self.world.via_ok(at, &q, None, &mut b, &mut sc) {
                            let id = self.fresh_id();
                            let task = Task { net, level: Level::PlaneFanout, a: pad, b: pad, main: false, zone: None };
                            self.place(id, task, Vec::new(), vec![at]);
                            placed += 1;
                            done = true;
                            break;
                        }
                    }
                    // No room on the piece itself, but the net's other layer lies under one of its pads:
                    // a via beside that pad, on a short stub, as a plane pad gets (4.2). Cheaper than a
                    // track and the way he ties such a pad (a motor-controller board, Q302.2 over the B.Cu plane).
                    if !done {
                        for &ip in &island_pads {
                            let at = self.board.pads[ip].center;
                            if !other(at.into()) || !tried.insert(at) {
                                continue;
                            }
                            let task = Task { net, level: Level::PlaneFanout, a: ip, b: ip, main: false, zone: None };
                            if self.fan_out_pad(ip, &task) {
                                placed += 1;
                                done = true;
                                break;
                            }
                        }
                    }
                    // No copper of the net on another layer to drop to, or no room for the via: a track
                    // from a pad on this piece to the nearest pad of the net off it.
                    // One try per piece: the join already aims at every piece off this one, so a second
                    // try from another of its pads fails the same way (it used up stitching's time).
                    let piece_key = island_pads.iter().copied().min();
                    if !done && !island_pads.is_empty() && !piece_key.map_or(false, |k| failed_pieces.contains(&k)) {
                        let c = |i: usize| self.board.pads[i].center;
                        let mut best: Option<(f64, usize, usize)> = None;
                        for &ip in &island_pads {
                            for (o, p) in self.board.pads.iter().enumerate() {
                                if p.net != net || p.layers.is_empty() || island_pads.contains(&o) {
                                    continue;
                                }
                                let d = octile_p(c(ip), c(o));
                                if best.map_or(true, |b| d < b.0) && !tried_pairs.contains(&(ip, o)) {
                                    best = Some((d, ip, o));
                                }
                            }
                        }
                        if let Some((_, ip, o)) = best {
                            tried_pairs.insert((ip, o));
                            let off: Vec<usize> = self.board.pads.iter().enumerate().filter(|(i, p)| p.net == net && !p.layers.is_empty() && !island_pads.contains(i)).map(|(i, _)| i).collect();
                            if self.join_by_track(net, ip, o, &off) {
                                placed += 1;
                                tracks += 1;
                                done = true;
                            } else if let Some(k) = piece_key {
                                failed_pieces.insert(k);
                            }
                        }
                    }
                    // Still loose: a via beside a pad on it, on a short stub, as a plane pad gets (4.2).
                    if !done {
                        for ip in island_pads {
                            if !tried.insert(self.board.pads[ip].center) {
                                continue;
                            }
                            let task = Task { net, level: Level::PlaneFanout, a: ip, b: ip, main: false, zone: None };
                            if self.fan_out_pad(ip, &task) {
                                placed += 1;
                                break;
                            }
                        }
                    }
                }
            }
            added += placed;
            left = loose - placed.min(loose);
            if placed == 0 {
                break;
            }
        }
        if added > 0 || left > 0 {
            self.log.push(format!("stitching: {} vias tie pour pieces to their net on another layer, {tracks} tracks join pads a pour leaves apart; {left} pieces had no place for either, {:.1} s", added - tracks, t0.elapsed().as_secs_f64()));
        }
    }

    /// A track from the copper of pad `a`'s piece to the nearest copper of the pads `to`, searched
    /// without the net's pour as a target, since the pour is what failed to join them. Both ends are
    /// whole pieces (pads and their tracks), so the new track never runs along one already there.
    fn join_by_track(&mut self, net: NetId, a: usize, b: usize, to: &[usize]) -> bool {
        let task = Task { net, level: Level::Other, a, b, main: false, zone: None };
        let (width, neck) = self.widths_for(&task);
        let clearance = self.rules.clearance_for(net, net);
        let comps = self.components_with(net, false);
        let (mut sources, mut targets) = (Vec::new(), Vec::new());
        for c in &comps {
            if c.pads.contains(&a) {
                self.comp_terminals(c, 0.0, &mut sources);
            } else if c.pads.iter().any(|p| to.contains(p)) {
                self.comp_terminals(c, 0.0, &mut targets);
            }
        }
        if sources.is_empty() || targets.is_empty() {
            return false;
        }
        // A mend, not a first route: a join that is not found quickly is left for the designer's note.
        // At the full node limit a few hopeless joins used all of stitching's time on a motor-controller board.
        let mut rules = self.rules.clone();
        rules.node_limit = rules.node_limit.min(60_000);
        // A search leaves from pads and may land on a track, never the reverse. So both ways are
        // tried and the shorter kept: the side that already has a track toward the other is then
        // the one landed on, and nothing is laid twice.
        let len = |pts: &[(P, usize)]| -> f64 { pts.windows(2).map(|w| hypot(sub(w[0].0.into(), w[1].0.into()))).sum() };
        for (max_vias, margin) in [(0u32, 3.0), (2, 6.0), (2, 15.0)] {
            let pf = Profile { width, neck, clearance, target_gap: clearance, max_vias, margin: margin * NM, layer_bias: None };
            let mut best: Option<(f64, Vec<(P, usize)>)> = None;
            for (from, to) in [(&sources, &targets), (&targets, &sources)] {
                let q = Query { net, also: None, sources: from, targets: to, profile: pf, rules: &rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
                self.searches += 1;
                let Some(path) = search(&self.world, &q) else { continue };
                self.nodes += path.nodes as u64;
                let pts = self.finish_path(&path, net, NO_NET, neck);
                let l = len(&pts);
                if best.as_ref().map_or(true, |b| l < b.0) {
                    best = Some((l, pts));
                }
            }
            if let Some((_, pts)) = best {
                self.commit(&task, &pts, width, neck, NO_NET);
                return true;
            }
        }
        false
    }

    /// Takes the nets that cut a pour off it. His way (benchmark B USB connector): a short stub off
    /// the pad and straight to the other layer. One net at a time first, then all of them together,
    /// since two neighbours can each block the other's way down. A move stands only if the refill
    /// model says the pour is better for it and no join opened; otherwise the old copper goes back.
    pub(super) fn heal_pours(&mut self) {
        self.grant_time(60.0);
        for _ in 0..8 {
            let splits = self.pour_splits();
            let total: usize = splits.iter().map(|s| s.1).sum();
            if total == 0 {
                break;
            }
            let cutters: Vec<NetId> = splits.iter().flat_map(|s| s.2.iter().copied()).collect();
            let mut sets: Vec<Vec<NetId>> = cutters.iter().map(|&c| vec![c]).collect();
            if cutters.len() > 1 {
                sets.push(cutters.clone());
            }
            // A net alone may not be the cut: a pour can be blocked on both sides of a connector by
            // different nets, and only moving them together opens it. So every net leaving a big pour.
            let mut leaving: Vec<NetId> = self.pour_exit.iter().copied().filter(|&n| !looks_ground(self.board.net_name(n))).collect();
            leaving.sort_unstable();
            if leaving.len() > 1 {
                sets.push(leaving);
            }
            if !sets.iter().any(|set| self.move_off_pour(set, total)) {
                break;
            }
        }
        for (net, extra, cutters) in self.pour_splits() {
            let names: Vec<&str> = cutters.iter().map(|&c| self.board.net_name(c)).collect();
            self.notes.push(format!("for the designer: the {net} pour refills into {extra} extra separate pieces, cut by {}: move them or bridge the pieces", names.join(", ")));
        }
    }

    fn move_off_pour(&mut self, nets: &[NetId], total: usize) -> bool {
        let names = nets.iter().map(|&c| self.board.net_name(c).to_string()).collect::<Vec<_>>().join(", ");
        // Even a short link can cut a pour: D+ tying a USB-C receptacle's two rows together across the
        // gap between them. So anything more than a stub off a pad is up for moving, and may not come
        // back longer than one (reference J1: each pad drops to the run by its own via).
        let ids: Vec<u32> = self.routes.values().filter(|r| nets.contains(&r.task.net) && self.seg_pour_run(r) > STUB_RUN).map(|r| r.id).collect();
        if ids.is_empty() {
            self.log.push(format!("pours: {names}: nothing more than a stub in the pour to move"));
            return false;
        }
        self.pour_limit = STUB_RUN;
        let open: usize = nets.iter().map(|&c| self.open_pieces(c)).sum();
        let saved: Vec<Route> = ids.iter().filter_map(|&i| self.unplace(i)).collect();
        let others: HashSet<u32> = self.routes.keys().copied().collect();
        self.pour_strict.extend(nets.iter().copied());
        let mut failed = 0;
        for r in &saved {
            if !self.try_route(&r.task) {
                failed += 1;
            }
        }
        for c in nets {
            self.pour_strict.remove(c);
        }
        self.pour_limit = POUR_RUN;
        let now_open: usize = nets.iter().map(|&c| self.open_pieces(c)).sum();
        let after: usize = if failed == 0 && now_open <= open { self.pour_splits().iter().map(|s| s.1).sum() } else { total };
        if after < total {
            self.log.push(format!("pours: moved {names} off the pour, extra pieces {total} to {after}"));
            return true;
        }
        let new: Vec<u32> = self.routes.keys().copied().filter(|i| !others.contains(i)).collect();
        for i in new {
            self.unplace(i);
        }
        for r in saved {
            self.place(r.id, r.task, r.segs, r.vias);
        }
        self.log.push(format!("pours: {names}: put back ({} of {} routes found no way off the pour, joins open {open} to {now_open}, extra pieces {total} to {after})", failed, ids.len()));
        false
    }

    /// Hold a pin's way out, straight off the pad, until its route is laid, on any part whose pitch
    /// makes the straight line that pin's only way out. That is decided from geometry, not from the
    /// part: a track on a neighbour's line can't get past a via on this one when the pitch is under
    /// the via's radius + clearance + half the track. RP-family parts qualify at 0.4 mm, and so does
    /// anything else that tight; the fine-pitch rule in the Troubleshooting doc ("parallel at pin
    /// pitch before calling it blocked") applies to them all, while 4.7's supply rings don't and
    /// aren't here. An earlier route then can't cut across the row and a GND via can't stand in the
    /// lane, and bus lines stagger their turns by themselves. Pins that stub inward to their own fill
    /// have no lane.
    pub(super) fn lay_lanes(&mut self, plan: &Plan) {
        // A new order of battle on a restart: lanes from the last run come off first.
        let old: Vec<usize> = self.lanes.keys().copied().collect();
        for pad in old {
            self.lane_off(pad);
        }
        self.lanes.clear();
        if self.lane_len <= 0.0 {
            return;
        }
        let inward: HashSet<usize> = plan.tasks.iter().filter(|t| t.zone.is_some_and(|z| z != RAIL_TAP)).map(|t| t.a).collect();
        // Where each pin's route is headed, for which way its lane's neighbours should stair.
        let mut goes_to: HashMap<usize, V> = HashMap::new();
        for t in plan.tasks.iter().filter(|t| t.a != t.b) {
            goes_to.entry(t.a).or_insert(self.board.pads[t.b].center.into());
            goes_to.entry(t.b).or_insert(self.board.pads[t.a].center.into());
        }
        let working: HashSet<usize> = plan.tasks.iter().flat_map(|t| [t.a, t.b]).collect();
        let r = self.rules.neck as f64 / 2.0;
        let stair = 0.06 * NM;
        let mut lanes = Vec::new();
        for f in &self.board.footprints {
            if f.min_pitch >= (self.rules.via as f64 / 2.0) + self.rules.clearance as f64 + self.rules.neck as f64 / 2.0 {
                continue;
            }
            let n = f.pads.len().max(1) as f64;
            let cx: f64 = f.pads.iter().map(|&p| self.board.pads[p].center.0 as f64).sum::<f64>() / n;
            let cy: f64 = f.pads.iter().map(|&p| self.board.pads[p].center.1 as f64).sum::<f64>() / n;
            // One row per side: (runs along y, outward sign) -> (position along the row, pad, tip).
            let mut rows: HashMap<(bool, bool), Vec<(f64, usize, V, usize)>> = HashMap::new();
            for &i in &f.pads {
                let p = &self.board.pads[i];
                if !working.contains(&i) || inward.contains(&i) {
                    continue;
                }
                let Some(layer) = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l)) else { continue };
                let b = p.shape.bbox();
                let (w, h) = (b.2 - b.0, b.3 - b.1);
                let c: V = p.center.into();
                // The pad's long axis points the way out; a square pad has no such way.
                if w > h * 1.5 {
                    let out = c.0 >= cx;
                    rows.entry((true, out)).or_default().push((c.1, i, V(if out { b.2 } else { b.0 }, c.1), layer));
                } else if h > w * 1.5 {
                    let out = c.1 >= cy;
                    rows.entry((false, out)).or_default().push((c.0, i, V(c.0, if out { b.3 } else { b.1 }), layer));
                }
            }
            for ((along_y, out), mut row) in rows {
                row.sort_by(|a, b| a.0.total_cmp(&b.0));
                let turn = |i: usize, at: f64| -> i32 {
                    let Some(t) = goes_to.get(&i) else { return 0 };
                    let d = if along_y { t.1 } else { t.0 } - at;
                    if d.abs() < f.min_pitch { 0 } else if d > 0.0 { 1 } else { -1 }
                };
                // Neighbours turning the same way at 45 degrees need more than the pin pitch between
                // them, so their turns stair by a little each (reference QSPI bus: "each bends further
                // out"). The pin on the inside of the turn gets the shortest lane, or the bus closes.
                let mut k = 0;
                while k < row.len() {
                    let s = turn(row[k].1, row[k].0);
                    let mut e = k + 1;
                    while e < row.len() && s != 0 && turn(row[e].1, row[e].0) == s && row[e].0 - row[e - 1].0 < f.min_pitch * 1.5 {
                        e += 1;
                    }
                    for j in k..e {
                        let (_, i, tip, layer) = row[j];
                        let steps = if s > 0 { e - 1 - j } else { j - k } as f64;
                        let len = if e - k == 1 { self.lane_len } else { (self.lane_len * 0.5 + stair * steps).min(self.lane_len * 2.0) };
                        let sign = if out { 1.0 } else { -1.0 };
                        // A lane stops short of fixed copper in its way: a part placed right off
                        // the pin must stay reachable, its own pad most of all.
                        let net = self.board.pads[i].net;
                        let mut len = len;
                        let mut to = tip;
                        while len >= 0.1 * NM {
                            to = if along_y { V(tip.0 + sign * len, tip.1) } else { V(tip.0, tip.1 + sign * len) };
                            if self.seg_clear(to_p(tip), to_p(to), layer, self.rules.neck, net, NO_NET) {
                                break;
                            }
                            len -= 0.05 * NM;
                        }
                        if len >= 0.1 * NM {
                            lanes.push((i, layer, Shape::Capsule { a: tip, b: to, r }));
                        }
                    }
                    k = e;
                }
            }
        }
        lanes.sort_by_key(|l| l.0);
        for (i, layer, shape) in lanes {
            self.lanes.insert(i, (layer, shape, None));
            self.lane_on(i);
        }
    }

    pub(super) fn lane_off(&mut self, pad: usize) {
        if let Some((layer, _, h)) = self.lanes.get_mut(&pad) {
            if let Some(id) = h.take() {
                self.world.layers[*layer].remove(id);
            }
        }
    }

    pub(super) fn lane_on(&mut self, pad: usize) {
        if !self.lanes.contains_key(&pad) || self.routes.values().any(|r| r.task.a == pad || r.task.b == pad) {
            return;
        }
        let net = self.board.pads[pad].net;
        let (layer, shape, h) = self.lanes.get_mut(&pad).unwrap();
        if h.is_none() {
            *h = Some(self.world.layers[*layer].add(shape.clone(), net, Owner::Lane(pad as u32)));
        }
    }

    fn pieces_of(&self, net: NetId) -> Vec<(NetId, conn::Piece)> {
        let mut extra = Vec::new();
        for r in self.routes.values().filter(|r| r.task.net == net) {
            for s in &r.segs {
                extra.push((net, conn::Piece::Seg { layer: s.layer, a: s.a.into(), b: s.b.into(), r: s.width as f64 / 2.0 }));
            }
            for v in &r.vias {
                extra.push((net, conn::Piece::Via { at: (*v).into(), r: self.rules.via as f64 / 2.0 }));
            }
        }
        extra
    }

    /// A net's islands as the checker sees them: pads, routed copper and fills.
    pub(crate) fn islands(&self, net: NetId) -> Vec<Vec<usize>> {
        let Some((_, pads)) = self.net_info.get(&net) else { return Vec::new() };
        conn::net_groups(self.board, net, &self.pieces_of(net))
            .into_iter()
            .map(|g| g.into_iter().filter(|p| pads.contains(p)).collect::<Vec<_>>())
            .filter(|g: &Vec<usize>| !g.is_empty())
            .collect()
    }

    /// Does the copper already join this task's two pads? Nets of two pads can't be joined by
    /// anything but their own route, so they skip the work.
    pub(super) fn joined(&self, task: &Task) -> bool {
        if task.a == task.b || task.zone.is_some_and(|z| z != RAIL_TAP) {
            return false;
        }
        let Some((_, pads)) = self.net_info.get(&task.net) else { return false };
        if pads.len() < 3 {
            return false;
        }
        self.islands(task.net).iter().any(|g| g.contains(&task.a) && g.contains(&task.b))
    }

    /// What is really open: the failed tasks that still join two islands, plus the joins nothing
    /// asked for. Plane fan-outs keep their own record, a pad either has its via or it hasn't.
    pub(super) fn open_work(&self, failed: Vec<Task>) -> Vec<Task> {
        let mut out: Vec<Task> = failed.iter().filter(|t| t.a == t.b && t.zone.is_none() && t.level == Level::PlaneFanout).cloned().collect();
        let planes = self.board.plane_nets();
        let mut nets: Vec<NetId> = self.net_info.keys().copied().collect();
        nets.sort();
        for net in nets {
            if self.only.as_ref().map(|o| !o.contains(&net)).unwrap_or(false) {
                continue;
            }
            let (level, _) = self.net_info[&net];
            if level == Level::PlaneFanout && planes.contains_key(&net) {
                continue;
            }
            // A rail joins as a rail: whatever is apart taps the rest, by the bus and its stubs,
            // and a fill nothing feeds counts too, since an island is never acceptable (4.3).
            if level == Level::Power {
                out.extend(self.rail_work(net));
                continue;
            }
            let live = self.islands(net);
            if live.len() < 2 {
                continue;
            }
            let mut uf = conn::Uf::new(live.len());
            let at = |p: usize| live.iter().position(|g| g.contains(&p));
            for t in failed.iter().filter(|t| t.net == net && t.a != t.b && t.zone.is_none()) {
                if let (Some(x), Some(y)) = (at(t.a), at(t.b)) {
                    if uf.find(x as u32) != uf.find(y as u32) {
                        uf.union(x as u32, y as u32);
                        out.push(t.clone());
                    }
                }
            }
            // Whatever is still apart joins at its nearest pads (Prim over the islands).
            loop {
                let mut best: Option<(f64, usize, usize, usize, usize)> = None;
                for i in 0..live.len() {
                    for j in i + 1..live.len() {
                        if uf.find(i as u32) == uf.find(j as u32) {
                            continue;
                        }
                        for &a in &live[i] {
                            for &b in &live[j] {
                                let d = hypot(sub(self.board.pads[a].center.into(), self.board.pads[b].center.into()));
                                if best.map(|x| d < x.0).unwrap_or(true) {
                                    best = Some((d, i, j, a, b));
                                }
                            }
                        }
                    }
                }
                let Some((_, i, j, a, b)) = best else { break };
                uf.union(i as u32, j as u32);
                out.push(Task { net, level, a, b, main: false, zone: None });
            }
        }
        // A fill nothing feeds is open too, though no pad says so (4.3: islands, never).
        out.extend(self.unfed_fills());
        out.sort_by_key(|t| t.level);
        out
    }

    /// One tap per piece of a rail still apart: from the pad of each smaller piece nearest the
    /// biggest, then from the nearest pad to each fill with no feed.
    fn rail_work(&self, net: NetId) -> Vec<Task> {
        let comps = self.components(net);
        let mk = |p: usize| Task { net, level: Level::Power, a: p, b: p, main: false, zone: Some(RAIL_TAP) };
        let with_pads: Vec<&crate::post::Comp> = comps.iter().filter(|c| !c.pads.is_empty()).collect();
        let Some(big) = with_pads.iter().max_by_key(|c| c.pads.len() + c.segs.len()) else { return Vec::new() };
        let dist = |a: usize, b: usize| hypot(sub(self.board.pads[a].center.into(), self.board.pads[b].center.into()));
        let mut out = Vec::new();
        for c in with_pads.iter().filter(|c| !std::ptr::eq(**c, *big)) {
            let near = |p: usize| big.pads.iter().map(|&q| dist(p, q)).fold(f64::INFINITY, f64::min);
            if let Some(&p) = c.pads.iter().min_by(|&&x, &&y| near(x).total_cmp(&near(y))) {
                out.push(mk(p));
            }
        }
        for c in comps.iter().filter(|c| c.pads.is_empty() && c.zones.iter().any(|&z| self.world.route_layers.contains(&self.world.zones[z].1))) {
            let z = c.zones[0];
            let poly = &self.world.zones[z].2;
            if poly.is_empty() {
                continue;
            }
            let m = V(poly.iter().map(|p| p.0).sum::<f64>() / poly.len() as f64, poly.iter().map(|p| p.1).sum::<f64>() / poly.len() as f64);
            if let Some(&p) = big.pads.iter().min_by(|&&x, &&y| hypot(sub(self.board.pads[x].center.into(), m)).total_cmp(&hypot(sub(self.board.pads[y].center.into(), m)))) {
                out.push(mk(p));
            }
        }
        out
    }

    /// How many pieces a net is in, for telling whether a move took it apart.
    fn pieces_apart(&self, net: NetId) -> usize {
        match self.net_info.get(&net) {
            Some((Level::Power, _)) => self.rail_work(net).len() + 1,
            Some((Level::PlaneFanout, _)) => 1,
            _ => self.islands(net).len(),
        }
    }

    /// Fullest first, then the fewest holes high in the hierarchy, then the cleanest copper.
    pub(super) fn score(&self, failed: &[Task]) -> (usize, usize, i64) {
        let holes: usize = failed.iter().map(|t| route_tie(t.level)).sum();
        let mut cost = 0.0;
        for r in self.routes.values() {
            for s in &r.segs {
                cost += hypot(sub(s.a.into(), s.b.into()));
            }
            cost += r.vias.len() as f64 * self.rules.cost_via;
        }
        // Of two boards equally full, the one with the bus plan: its copper may be longer, but the plain
        // go exists to close holes, not to win on length (4.2 weighs order against distance by hand).
        let plain = if self.plain_go { i64::MAX / 4 } else { 0 };
        (failed.len(), holes, cost as i64 + plain)
    }

    pub(super) fn keep_if_best(&self, failed: &[Task], best: &mut Option<Best>) {
        let score = self.score(failed);
        if best.as_ref().map(|b| score < b.score).unwrap_or(true) {
            *best = Some(Best { score, routes: self.routes.clone(), failed: failed.to_vec(), notes: self.notes.clone() });
        }
    }

    fn undo(&mut self, txn: Txn) {
        for id in txn.added {
            self.rip(id);
        }
        for r in txn.removed.into_iter().rev() {
            self.place(r.id, r.task, r.segs, r.vias);
        }
    }

    /// Who may be moved for this task, at what price. GND vias may always move, they are the
    /// lowest priority copper (4.4). Pairs and Kelvin never move for anything lower (4.2).
    fn prices_for(&self, task: &Task, mode: Mode, txn: &Txn) -> HashMap<u32, f64> {
        let me = (task.a, task.b);
        self.routes
            .values()
            .map(|r| {
                let them = (r.task.a, r.task.b);
                let protected = matches!(r.task.level, Level::Kelvin | Level::Pair) || (r.segs.is_empty() && r.task.a == r.task.b);
                let via = r.task.level == Level::PlaneFanout;
                let lower = r.task.level >= task.level || via;
                let times = self.memory.get(&(me, them)).copied().unwrap_or(0);
                let rc = self.rip_count.get(&them).copied().unwrap_or(0) as f64;
                let closed = protected || (!lower && !mode.escalate) || times >= 6 || txn.locked.contains(&r.id) || txn.banned.contains(&them);
                let base = if via { 0.3 * NM } else { SOFT_PRICE };
                (r.id, if closed { f64::INFINITY } else { base * (1.0 + 0.25 * rc) })
            })
            .collect()
    }

    /// A soft search with a tight budget, a coarser lattice and a greedier heuristic. Free copper
    /// is flooded first at the usual weights, so an unbudgeted exact one spends everything before
    /// paying to cross anyone: measured on piprobe_v13 as 800k expansions, 8 s and no answer for a
    /// pin 0.4 mm from its way out.
    fn soft_path(&mut self, task: &Task, mode: Mode, txn: &Txn) -> Option<(Path, Profile)> {
        let prices = self.prices_for(task, mode, txn);
        let price = |c: u32| prices.get(&c).copied().unwrap_or(f64::INFINITY);
        let sources = [self.pad_terminal(task.a)];
        let targets = self.targets_of(task);
        let (_, n) = self.widths_for(task);
        let mut rules = self.rules.clone();
        rules.node_limit = SOFT_NODES * if self.deep { 6 } else { 1 };
        rules.search_weight = SOFT_WEIGHT;
        // Non-priority nets and rails go for the via first: a rail's way is along its bus.
        let bias = self.bus_of(task);
        let ladder: &[(u32, f64)] = if task.level == Level::Other || bias.is_some() { &[(2, 3.0), (2, 10.0), (4, 40.0)] } else { &[(0, 3.0), (2, 3.0), (2, 10.0), (4, 40.0)] };
        for &(vias, margin) in ladder {
            let pf = Profile { width: n, neck: n, clearance: self.rules.clearance, target_gap: self.rules.clearance, max_vias: vias, margin: margin * NM, layer_bias: bias };
            let q = Query { net: task.net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &rules, soft: Some(&price), via_in: None, history: Some(&self.history), free: &[], arrive: None };
            self.searches += 1;
            if let Some(path) = search(&self.world, &q) {
                self.nodes += path.nodes as u64;
                return Some((path, pf));
            }
            if self.trace {
                eprintln!("    soft {} {} -> {} vias {} margin {}: {}", self.board.net_name(task.net), self.board.pad_name(task.a), self.board.pad_name(task.b), vias, margin, if RAN_OUT.with(|c| c.get()) { "ran out" } else { "walled in" });
            }
        }
        None
    }

    /// A legal route for this task with a budget fit for a repair, not a first attempt. Power goes to
    /// the bus first, like any other rail task (4.2): a repair is no reason to wrap a chip on the pad
    /// layer. It may then join anywhere on the other island, a pad, a via or a bend (a branch, not a
    /// new run).
    pub(super) fn route_hard(&mut self, task: &Task) -> Option<u32> {
        if task.level == Level::Power && task.zone.map(|z| z == RAIL_TAP).unwrap_or(true) {
            let rail = Task { zone: Some(RAIL_TAP), main: true, ..task.clone() };
            // A rail the power stage planned (it has a current) is searched as often as repair asks:
            // capped here, an benchmark C +5V feed came out thin and failed its fixture (0.26% drop against
            // 0.25%). The cap is for rails with no spec, where the ladder is all there is.
            // (2026-11-10: the memo and the cap of post.rs `rail_route_guarded` were also tried here for
            // rails without a spec. They saved nothing on the board they were meant for, esc-g431, and
            // cost joins on two others whose repair needs the repeats: benchmark C without its
            // spec 300 -> 297, a current-monitor board 521 -> 520. Repair searches unguarded.)
            let made = self.rail_route(&rail);
            if let Some(id) = made {
                return Some(id);
            }
        }
        let mut rules = self.rules.clone();
        rules.node_limit = SOFT_NODES * if self.deep { 6 } else { 1 };
        let (sources, targets) = if task.level == Level::Power && task.a != task.b { self.island_terminals(task) } else { (vec![self.pad_terminal(task.a)], self.targets_of(task)) };
        // At the neck: this is about finding room. A no-via way round is weighed against a via.
        let (w, n) = self.widths_for(task);
        let c = self.rules.clearance_for(task.net, task.net);
        let ladder: &[(u32, f64)] = if task.level == Level::Other { &[(2, 3.0), (2, 8.0), (4, 40.0)] } else { &[(0, 3.0), (2, 3.0), (0, 8.0), (2, 8.0), (4, 40.0)] };
        let profiles: Vec<Profile> = ladder.iter().map(|&(vias, margin)| Profile { width: n, neck: n, clearance: c, target_gap: c, max_vias: vias, margin: margin * NM, layer_bias: None }).collect();
        let (path, _) = self.weigh(task, &sources, &targets, &profiles, &rules)?;
        let pts = self.finish_path(&path, task.net, NO_NET, n);
        let id = self.commit(task, &pts, w, n, NO_NET);
        // A join onto an island's copper is only worth keeping if it really joined.
        if task.level == Level::Power && task.a != task.b && (!self.joined(task) || !self.joints_ok(id)) {
            self.rip(id);
            return None;
        }
        Some(id)
    }

    /// Does this route meet its net's other copper at an obtuse angle? A branch joins as a "Y",
    /// never square or acute (4.2).
    fn joints_ok(&self, id: u32) -> bool {
        let Some(r) = self.routes.get(&id) else { return true };
        for s in &r.segs {
            for (p, far) in [(s.a, s.b), (s.b, s.a)] {
                for o in self.routes.values().filter(|o| o.id != id && o.task.net == r.task.net) {
                    for t in o.segs.iter().filter(|t| t.layer == s.layer) {
                        let other = if t.a == p { Some(t.b) } else if t.b == p { Some(t.a) } else { None };
                        if let Some(q) = other {
                            if turn_of(q, p, far).map(|x| x > 1).unwrap_or(false) {
                                return false;
                            }
                        }
                    }
                }
            }
        }
        true
    }

    fn island_terminals(&self, task: &Task) -> (Vec<Terminal>, Vec<Terminal>) {
        let live = self.islands(task.net);
        let side = |pad: usize| -> (Vec<Terminal>, Vec<Terminal>) {
            let Some(g) = live.iter().find(|g| g.contains(&pad)) else { return (vec![self.pad_terminal(pad)], Vec::new()) };
            let mut points: Vec<Terminal> = g.iter().map(|&p| self.pad_terminal(p)).collect();
            let mut fills: Vec<Terminal> = Vec::new();
            for r in self.routes.values().filter(|r| r.task.net == task.net && (g.contains(&r.task.a) || g.contains(&r.task.b))) {
                for s in &r.segs {
                    points.push(Terminal::Point { p: s.b, layers: vec![s.layer] });
                }
                for v in &r.vias {
                    points.push(Terminal::Point { p: *v, layers: self.world.route_layers.clone() });
                }
                // The fill this island stubs into is part of it: a via down into the ring is how
                // his caps get their +1V1 (4.7).
                if let Some(z) = r.task.zone.filter(|&z| z != RAIL_TAP) {
                    let (_, layer, poly) = &self.world.zones[z];
                    fills.push(Terminal::Zone { layer: *layer, poly: poly.clone() });
                }
            }
            (points, fills)
        };
        let (a, fa) = side(task.a);
        let (mut b, fb) = side(task.b);
        // A fill can only be a target (a source has no one point to start from).
        if fb.is_empty() && !fa.is_empty() {
            b.extend(fa);
            return (b, a);
        }
        b.extend(fb);
        (a, b)
    }

    /// Move a route only as much as the new copper needs: keep what is still legal and search from
    /// the break to the old route. Often what comes out is a shove, since the detour hugs the
    /// copper that displaced it.
    fn splice(&mut self, old: &Route, txn: &mut Txn) -> bool {
        // A tap has no fixed far end to keep: its target is whatever of the rail is nearest now.
        if old.task.a == old.task.b || old.segs.is_empty() {
            return false;
        }
        let task = &old.task;
        let mut pts: Vec<(P, usize)> = Vec::new();
        for s in &old.segs {
            if let Some(&(q, _)) = pts.last() {
                // Tidy-up can drop a piece hidden in the net's own fill: no chain to keep.
                if q != s.a {
                    return false;
                }
            }
            if pts.last() != Some(&(s.a, s.layer)) {
                pts.push((s.a, s.layer));
            }
            pts.push((s.b, s.layer));
        }
        // A route that joined an island elsewhere has no pad to keep.
        if pts[0].0 != snap(self.board.pads[task.a].center) {
            return false;
        }
        let (w, n) = self.widths_for(task);
        let via_q = |net| Query { net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: self.rules.clearance, target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
        let mut first = None;
        let mut last = 0;
        for (i, x) in pts.windows(2).enumerate() {
            let bad = if x[0].1 == x[1].1 {
                !self.seg_clear(x[0].0, x[1].0, x[0].1, n, task.net, NO_NET)
            } else {
                let (mut b, mut c) = (Vec::new(), 0.0);
                !self.world.via_ok(x[0].0, &via_q(task.net), None, &mut b, &mut c)
            };
            if bad {
                first.get_or_insert(i);
                last = i;
            }
        }
        let Some(first) = first else {
            // The path it was ripped for bent away in tidy-up: nothing to change.
            let id = self.commit(task, &pts, w, n, NO_NET);
            txn.added.push(id);
            return true;
        };
        let mut rules = self.rules.clone();
        rules.node_limit = SOFT_NODES / 2;
        for grow in [0usize, 1, 3] {
            let i = first.saturating_sub(grow);
            let j = (last + 1 + grow).min(pts.len() - 1);
            let term = |k: usize| -> Terminal {
                if k == 0 {
                    self.pad_terminal(task.a)
                } else if k == pts.len() - 1 && task.zone.is_none() {
                    self.pad_terminal(task.b)
                } else {
                    Terminal::Point { p: pts[k].0, layers: vec![pts[k].1] }
                }
            };
            let sources = [term(i)];
            let targets = [term(j)];
            let arrive = if j + 1 < pts.len() && pts[j].1 == pts[j + 1].1 { dir_of(pts[j].0, pts[j + 1].0) } else { None };
            for (vias, margin) in [(0u32, 1.5), (2, 3.0)] {
                let pf = Profile { width: n, neck: n, clearance: self.rules.clearance, target_gap: self.rules.clearance, max_vias: vias, margin: margin * NM, layer_bias: None };
                let q = Query { net: task.net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &rules, soft: None, via_in: None, history: Some(&self.history), free: &[], arrive };
                self.searches += 1;
                let Some(path) = search(&self.world, &q) else { continue };
                self.nodes += path.nodes as u64;
                let mut new: Vec<(P, usize)> = pts[..i].to_vec();
                new.extend(path.pts.iter().copied());
                new.extend(pts[j + 1..].iter().copied());
                simplify(&mut new);
                // The old part and the detour must meet at an obtuse or square angle: a square one
                // gets its chamfer below, an acute one isn't worth keeping.
                let acute = new.windows(3).any(|x| x[0].1 == x[1].1 && x[1].1 == x[2].1 && turn_of(x[0].0, x[1].0, x[2].0).map(|t| t > 2).unwrap_or(false));
                // The kept part's vias are off the board while the detour is found, so the search
                // can't keep clear of them: benchmark C got two holes of one net 0.002 mm apart this way.
                let holes: Vec<P> = new.windows(2).filter(|x| x[0].1 != x[1].1).map(|x| x[0].0).collect();
                let min = (self.rules.drill + self.rules.hole_hole) as f64;
                let crowded = holes.iter().enumerate().any(|(k, a)| holes[k + 1..].iter().any(|b| hypot(sub((*a).into(), (*b).into())) < min));
                if acute || crowded {
                    continue;
                }
                let whole = Path { pts: new, ..Default::default() };
                let tidy = self.finish_path(&whole, task.net, NO_NET, n);
                let id = self.commit(task, &tidy, w, n, NO_NET);
                txn.added.push(id);
                self.splices += 1;
                return true;
            }
        }
        false
    }

    /// Lay this task again, moving what is in the way. True only if it holds, every net it touched
    /// stays whole and nothing was given up; otherwise the board is as it was.
    pub(crate) fn move_for_width(&mut self, task: &Task, open: usize) -> bool {
        let mode = Mode { escalate: true, swap: false };
        let mut txn = Txn { fuel: 14, ..Default::default() };
        let ok = self.displace(task, mode, 3, &mut txn) && self.still_whole(&mut txn, task) && txn.dropped.is_empty() && self.open_pieces(task.net) <= open;
        if !ok {
            self.undo(txn);
        }
        ok
    }

    /// Find this task a place, moving whoever is in the way, who then do the same, `depth` deep.
    fn displace(&mut self, task: &Task, mode: Mode, depth: u32, txn: &mut Txn) -> bool {
        if self.over_time() || txn.fuel <= 0 {
            return false;
        }
        txn.fuel -= 1;
        if task.a == task.b && task.zone.is_none() {
            return self.displace_fanout(task, mode, depth, txn);
        }
        if self.joined(task) || (task.zone == Some(RAIL_TAP) && self.rail_targets(task, 0.0).is_empty()) {
            return true;
        }
        if let Some(id) = self.route_hard(task) {
            txn.added.push(id);
            txn.locked.insert(id);
            return true;
        }
        if depth == 0 {
            return false;
        }
        let Some((path, pf)) = self.soft_path(task, mode, txn) else {
            let why = if RAN_OUT.with(|c| c.get()) { "the search ran out of budget before reaching it, even allowed to move routes" } else { "no path even through the routes it may move: pads, fills or protected copper wall it in" };
            self.why.insert((task.a, task.b), why.to_string());
            return false;
        };
        let victims = self.take_victims(task, &path.blockers, txn);
        if self.trace {
            eprintln!("    move for {} {} -> {}: {:?}", self.board.net_name(task.net), self.board.pad_name(task.a), self.board.pad_name(task.b), victims.iter().map(|r| self.board.net_name(r.task.net).to_string()).collect::<Vec<_>>());
        }
        let (w, _) = self.widths_for(task);
        // The soft lattice has no lines along movable copper, so its path grazes more routes than
        // it must. With them up, the exact lattice finds the hugging path, and any victim it no
        // longer touches goes straight back (splice sees nothing wrong with it).
        let exact = self.route_hard(task);
        let id = match exact {
            Some(id) => id,
            None => {
                let pts = self.finish_path(&path, task.net, NO_NET, pf.neck);
                // A victim's lane came back when it came up, and the soft path couldn't see it:
                // laying that path would box the victim's own pin in.
                let legal = pts.windows(2).all(|x| x[0].1 != x[1].1 || self.seg_clear(x[0].0, x[1].0, x[0].1, pf.neck, task.net, NO_NET));
                if !legal {
                    if let Some(v) = victims.first() {
                        txn.banned.insert((v.task.a, v.task.b));
                    }
                    self.why.insert((task.a, task.b), "the way through crosses another pin's way out".to_string());
                    return false;
                }
                self.commit(task, &pts, w, pf.neck, NO_NET)
            }
        };
        txn.added.push(id);
        txn.locked.insert(id);
        self.relocate(task, victims, mode, depth, txn)
    }

    fn take_victims(&mut self, task: &Task, ids: &[u32], txn: &mut Txn) -> Vec<Route> {
        let me = (task.a, task.b);
        let mut out = Vec::new();
        for b in ids {
            let Some(r) = self.routes.get(b).cloned() else { continue };
            *self.memory.entry((me, (r.task.a, r.task.b))).or_insert(0) += 1;
            if !txn.apart.contains_key(&r.task.net) {
                let n = self.pieces_apart(r.task.net);
                txn.apart.insert(r.task.net, n);
            }
            self.rip(*b);
            self.rips += 1;
            txn.removed.push(r.clone());
            out.push(r);
        }
        out.sort_by_key(|r| r.task.level);
        out
    }

    fn relocate(&mut self, task: &Task, victims: Vec<Route>, mode: Mode, depth: u32, txn: &mut Txn) -> bool {
        for r in victims {
            let before = txn.added.len();
            if self.splice(&r, txn) {
                let added: Vec<u32> = txn.added[before..].to_vec();
                txn.locked.extend(added);
                continue;
            }
            if self.displace(&r.task, mode, depth - 1, txn) {
                continue;
            }
            if mode.swap && r.task.level >= task.level && txn.dropped.is_empty() {
                txn.dropped.push(r.task.clone());
                continue;
            }
            self.why.insert((task.a, task.b), format!("its way is held by {} ({} to {}), which found no other place", self.board.net_name(r.task.net), self.board.pad_name(r.task.a), self.board.pad_name(r.task.b)));
            txn.banned.insert((r.task.a, r.task.b));
            return false;
        }
        true
    }

    /// A pad with no via site in a straight line: a bent stub to the nearest site that has one, and
    /// failing that, a stub to the net's own copper that already reaches the plane, such as a USB
    /// connector's shield pad (reference benchmark B joins J1's GND pins to the shield this way).
    fn fan_out_search(&mut self, task: &Task) -> Option<u32> {
        let p = &self.board.pads[task.a];
        let (center, net) = (p.center, p.net);
        let layer = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l))?;
        let (n, c) = (self.rules.neck, self.rules.clearance);
        let vr = self.rules.via as f64 / 2.0;
        let pad_gap = self.rules.pad_via_gap as f64;
        let shape = p.shape.clone();
        let mut sites: Vec<(f64, P)> = Vec::new();
        let step = 0.1 * NM;
        let reach = (2.5 * NM / step) as i64;
        for j in -reach..=reach {
            for i in -reach..=reach {
                let v = snap((center.0 + (i as f64 * step) as i64, center.1 + (j as f64 * step) as i64));
                let d = hypot(sub(v.into(), center.into()));
                if d > 2.5 * NM || shape.dist_pt(v.into()) < vr + pad_gap {
                    continue;
                }
                let q = Query { net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: c, target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
                let (mut b, mut sc) = (Vec::new(), 0.0);
                if self.world.via_ok(v, &q, None, &mut b, &mut sc) {
                    sites.push((d, v));
                }
            }
        }
        sites.sort_by(|a, b| a.0.total_cmp(&b.0));
        let mut rules = self.rules.clone();
        rules.node_limit = SOFT_NODES / 4;
        let pf = Profile { width: n, neck: n, clearance: c, target_gap: c, max_vias: 0, margin: 2.0 * NM, layer_bias: None };
        let sources = [self.pad_terminal(task.a)];
        // Sites close together fail together: try a spread of them.
        let mut tried: Vec<P> = Vec::new();
        for (_, v) in sites {
            if tried.len() >= 8 {
                break;
            }
            if tried.iter().any(|t| hypot(sub((*t).into(), v.into())) < 0.3 * NM) {
                continue;
            }
            tried.push(v);
            let targets = [Terminal::Point { p: v, layers: vec![layer] }];
            let q = Query { net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
            self.searches += 1;
            let Some(path) = search(&self.world, &q) else { continue };
            self.nodes += path.nodes as u64;
            let pts = self.finish_path(&path, net, NO_NET, n);
            let id = self.fresh_id();
            let segs: Vec<Seg> = pts.windows(2).filter(|w| w[0].1 == w[1].1 && w[0].0 != w[1].0).map(|w| Seg { a: w[0].0, b: w[1].0, layer: w[0].1, width: n }).collect();
            self.place(id, task.clone(), segs, vec![v]);
            return Some(id);
        }
        // Own copper already on the plane: through-hole pads and vias of this net.
        let mut targets: Vec<Terminal> = Vec::new();
        let planes = self.board.plane_nets();
        let inner = planes.get(&net).cloned().unwrap_or_default();
        let own_fp = self.board.pads[task.a].fp;
        for (i, q) in self.board.pads.iter().enumerate() {
            // Through-hole pads reach the plane; a pin beside its own part's exposed pad joins that
            // (benchmark C's U6.5 and U8.5: no via site in the row, and the pad is right there).
            let exposed = q.fp == own_fp && q.size.0 >= 1.0 * NM && q.size.1 >= 1.0 * NM;
            if i != task.a && q.net == net && (exposed || q.layers.iter().any(|l| inner.contains(l))) && q.layers.contains(&layer) && hypot(sub(q.center.into(), center.into())) < 6.0 * NM {
                targets.push(self.pad_terminal(i));
            }
        }
        for r in self.routes.values().filter(|r| r.task.net == net) {
            for v in r.vias.iter().filter(|v| hypot(sub((**v).into(), center.into())) < 6.0 * NM) {
                targets.push(Terminal::Point { p: *v, layers: vec![layer] });
            }
        }
        if targets.is_empty() {
            return None;
        }
        let pf = Profile { margin: 3.0 * NM, ..pf };
        let q = Query { net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
        self.searches += 1;
        let path = search(&self.world, &q)?;
        let pts = self.finish_path(&path, net, NO_NET, n);
        let id = self.fresh_id();
        let segs: Vec<Seg> = pts.windows(2).filter(|w| w[0].1 == w[1].1 && w[0].0 != w[1].0).map(|w| Seg { a: w[0].0, b: w[1].0, layer: w[0].1, width: n }).collect();
        self.notes.push(format!("{}: joined to the net's own plane copper, no via site of its own (4.4)", self.board.pad_name(task.a)));
        self.place(id, task.clone(), segs, Vec::new());
        Some(id)
    }

    fn displace_fanout(&mut self, task: &Task, mode: Mode, depth: u32, txn: &mut Txn) -> bool {
        let before = self.next_id;
        if self.fan_out_pad(task.a, task) {
            for id in before..self.next_id {
                txn.added.push(id);
                txn.locked.insert(id);
            }
            return true;
        }
        if let Some(id) = self.fan_out_search(task) {
            txn.added.push(id);
            txn.locked.insert(id);
            return true;
        }
        if depth == 0 {
            return false;
        }
        let prices = self.prices_for(task, mode, txn);
        let Some((v, layer, blockers)) = self.fan_out_site(task.a, &prices) else {
            self.why.insert((task.a, task.b), "no via site within 2 mm, even moving the routes it may move".to_string());
            return false;
        };
        let victims = self.take_victims(task, &blockers, txn);
        let id = self.next_id;
        self.next_id += 1;
        self.place(id, task.clone(), vec![Seg { a: snap(self.board.pads[task.a].center), b: v, layer, width: self.rules.neck }], vec![v]);
        txn.added.push(id);
        txn.locked.insert(id);
        self.relocate(task, victims, mode, depth, txn)
    }

    /// No net a repair touched may end up in more pieces than it was in, bar a swap's one hole.
    fn still_whole(&mut self, txn: &mut Txn, task: &Task) -> bool {
        if self.loose {
            return true;
        }
        let mut ok = true;
        for (net, was) in txn.apart.clone() {
            let spare = txn.dropped.iter().filter(|t| t.net == net).count();
            if self.pieces_apart(net) > was + spare {
                ok = false;
                let hit: Vec<(usize, usize)> = txn.removed.iter().filter(|r| r.task.net == net).map(|r| (r.task.a, r.task.b)).collect();
                txn.banned.extend(hit);
                self.why.insert((task.a, task.b), format!("moving {} for it would take that net apart", self.board.net_name(net)));
            }
        }
        ok
    }

    /// One task's repair, whole or not at all. A victim that couldn't move is banned for the next
    /// try, which so has to find another way; the same failure twice ends it.
    pub(super) fn repair_one(&mut self, task: &Task, mode: Mode) -> Repair {
        let mut banned = HashSet::new();
        for _ in 0..REPAIR_TRIES {
            let mut txn = Txn { banned: banned.clone(), fuel: 14, ..Default::default() };
            let ok = self.displace(task, mode, 3, &mut txn) && self.still_whole(&mut txn, task);
            if ok {
                return match txn.dropped.pop() {
                    Some(t) => Repair::Swapped(t),
                    None => Repair::Fixed,
                };
            }
            let learned = txn.banned.len() > banned.len();
            banned = std::mem::take(&mut txn.banned);
            self.undo(txn);
            if !learned || self.over_time() {
                break;
            }
        }
        Repair::Failed
    }

    /// Part 3 step 8, the move a plain re-search can't make: this connection has a good way but someone
    /// sits on it. Take it, then let them find another place. Kept only if the board's cost falls and
    /// no net comes apart. The caller has already lifted the route; on failure it goes back.
    /// `own_pieces`: how apart the route's own net was before it was lifted.
    pub(crate) fn swap_for(&mut self, old: &Route, old_cost: f64, own_pieces: usize) -> bool {
        let task = old.task.clone();
        let mode = Mode { escalate: false, swap: false };
        let mut txn = Txn { fuel: 8, ..Default::default() };
        let Some((path, _)) = self.soft_path(&task, mode, &txn) else { return false };
        if path.blockers.is_empty() || path.blockers.len() > 3 {
            return false;
        }
        if path.blockers.iter().any(|b| self.routes.get(b).map(|r| self.in_bus_row(&r.task)).unwrap_or(false)) {
            return false;
        }
        let nets: Vec<NetId> = {
            let mut v: Vec<NetId> = path.blockers.iter().filter_map(|b| self.routes.get(b).map(|r| r.task.net)).collect();
            v.push(task.net);
            v.sort_unstable();
            v.dedup();
            v
        };
        let pieces: usize = nets.iter().map(|&n| if n == task.net { own_pieces } else { self.open_pieces(n) }).sum();
        let before: f64 = path.blockers.iter().filter_map(|b| self.routes.get(b)).map(|r| self.route_cost(r)).sum::<f64>() + old_cost;
        let victims = self.take_victims(&task, &path.blockers, &mut txn);
        let done = match self.route_hard(&task) {
            Some(id) => {
                txn.added.push(id);
                txn.locked.insert(id);
                self.relocate(&task, victims, mode, 1, &mut txn)
            }
            None => false,
        };
        let after: f64 = txn.added.iter().filter_map(|id| self.routes.get(id)).map(|r| self.route_cost(r)).sum();
        let whole = nets.iter().map(|&n| self.open_pieces(n)).sum::<usize>() <= pieces;
        if self.trace {
            eprintln!("    swap {} {}: blockers {:?} placed {done} whole {whole} cost {:.1} -> {:.1}", self.board.net_name(task.net), self.board.pad_name(task.a), nets.iter().map(|&n| self.board.net_name(n)).collect::<Vec<_>>(), before / NM, after / NM);
        }
        if done && whole && after + 0.05 * NM < before {
            return true;
        }
        self.undo(txn);
        false
    }

    /// A 90-degree corner that tidy-up couldn't chamfer for lack of room breaks 4.2 outright: go
    /// around again, with square corners priced out of the search. Stays as it was if that fails.
    pub(super) fn fix_square_corners(&mut self) {
        let square = |r: &Route| -> bool {
            r.segs.windows(2).any(|s| s[0].layer == s[1].layer && s[0].b == s[1].a && turn_of(s[0].a, s[0].b, s[1].b) == Some(2))
        };
        // A fan-out stub has no second pad to route to: searching would lay nothing and lose its via.
        let ids: Vec<u32> = self.routes.values().filter(|r| square(r) && !matches!(r.task.level, Level::Pair | Level::Kelvin) && !(r.task.a == r.task.b && r.task.zone.is_none())).map(|r| r.id).collect();
        let mut rules = self.rules.clone();
        rules.cost_bend90 = 30.0 * NM;
        rules.node_limit = SOFT_NODES * if self.deep { 6 } else { 1 };
        for id in ids {
            let Some(old) = self.routes.get(&id).cloned() else { continue };
            self.rip(id);
            let sources = [self.pad_terminal(old.task.a)];
            let targets = self.targets_of(&old.task);
            let (w, n) = self.widths_for(&old.task);
            let mut placed = false;
            for (vias, margin) in [(old.vias.len() as u32, 3.0), (old.vias.len() as u32 + 2, 8.0)] {
                let pf = Profile { width: n, neck: n, clearance: self.rules.clearance, target_gap: self.rules.clearance, max_vias: vias, margin: margin * NM, layer_bias: None };
                let q = Query { net: old.task.net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
                let Some(path) = search(&self.world, &q) else { continue };
                let pts = self.finish_path(&path, old.task.net, NO_NET, n);
                let new = self.commit(&old.task, &pts, w, n, NO_NET);
                if self.routes.get(&new).map(square).unwrap_or(true) {
                    self.rip(new);
                    continue;
                }
                placed = true;
                break;
            }
            if !placed {
                self.place(old.id, old.task, old.segs, old.vias);
            }
        }
    }

    /// The teardrop KiCad will draw where this route leaves a pad, as a polygon: from the pad's edge
    /// to a point half the pad's size along the track (at most 1 mm), and as wide as the pad where it
    /// meets it. Read from the project's teardrop settings as the reference boards carry them, and checked
    /// against the one KiCad reported on piprobe_v13 (its side point, 173.26 by 67.75, is this
    /// polygon's). Follows the track round one bend, as KiCad's two-track teardrops do.
    fn teardrop_at(&self, pad: usize, chain: &[(P, i64)]) -> Option<(usize, Vec<V>)> {
        let p = &self.board.pads[pad];
        let b = p.shape.bbox();
        let size = (b.2 - b.0).min(b.3 - b.1);
        let (first, w) = chain.first().copied()?;
        if w as f64 >= 0.9 * size || chain.len() < 2 {
            return None;
        }
        let _ = first;
        // Walk out of the pad.
        let mut exit = None;
        for k in 0..chain.len() - 1 {
            let (u, v): (V, V) = (chain[k].0.into(), chain[k + 1].0.into());
            if p.shape.dist_pt(v) > 0.0 {
                let l = hypot(sub(v, u)).max(1.0);
                let mut t = 0.0;
                while t < l {
                    let q = V(u.0 + (v.0 - u.0) * t / l, u.1 + (v.1 - u.1) * t / l);
                    if p.shape.dist_pt(q) > 0.0 {
                        break;
                    }
                    t += 0.01 * NM;
                }
                exit = Some((k, V(u.0 + (v.0 - u.0) * t / l, u.1 + (v.1 - u.1) * t / l), V((v.0 - u.0) / l, (v.1 - u.1) / l)));
                break;
            }
        }
        let (k, out, dir) = exit?;
        let mut left = (0.5 * size).min(1.0 * NM);
        let mut at = out;
        let mut along = dir;
        for j in k..chain.len() - 1 {
            let v: V = chain[j + 1].0.into();
            let l = hypot(sub(v, at));
            if l >= left {
                at = V(at.0 + along.0 * left, at.1 + along.1 * left);
                break;
            }
            left -= l;
            at = v;
            if j + 2 < chain.len() {
                let n: V = chain[j + 2].0.into();
                let m = hypot(sub(n, v)).max(1.0);
                along = V((n.0 - v.0) / m, (n.1 - v.1) / m);
            }
        }
        let half = w as f64 / 2.0;
        let h = (size / 2.0).min(1.0 * NM);
        let (na, nd) = (V(-along.1, along.0), V(-dir.1, dir.0));
        let clamp = |q: V| V(q.0.clamp(b.0, b.2), q.1.clamp(b.1, b.3));
        Some((0, vec![
            V(at.0 + na.0 * half, at.1 + na.1 * half),
            V(at.0 - na.0 * half, at.1 - na.1 * half),
            clamp(V(out.0 - nd.0 * h, out.1 - nd.1 * h)),
            clamp(V(out.0 + nd.0 * h, out.1 + nd.1 * h)),
        ]))
    }

    /// Who a route's future teardrops would bridge: (pad on the route, foreign pad, layer).
    fn teardrop_hits(&self, r: &Route) -> Vec<(usize, usize, usize)> {
        let mut out = Vec::new();
        let by_layer: Vec<usize> = { let mut v: Vec<usize> = r.segs.iter().map(|s| s.layer).collect(); v.dedup(); v };
        for layer in by_layer {
            let run: Vec<&Seg> = r.segs.iter().filter(|s| s.layer == layer).collect();
            if run.is_empty() {
                continue;
            }
            let mut fwd: Vec<(P, i64)> = vec![(run[0].a, run[0].width)];
            fwd.extend(run.iter().map(|s| (s.b, s.width)));
            let back: Vec<(P, i64)> = fwd.iter().rev().copied().collect();
            for chain in [fwd, back] {
                let start: V = chain[0].0.into();
                let pad = self.board.pads.iter().position(|p| p.net == r.task.net && p.layers.contains(&layer) && p.shape.dist_pt(start) <= 1.0);
                let Some(pad) = pad else { continue };
                if let Some((_, poly)) = self.teardrop_at(pad, &chain) {
                    if let Some((who, _)) = self.world.mask.poly_near(r.task.net, layer, &poly, 0.03 * NM) {
                        out.push((pad, who, layer));
                    }
                }
            }
        }
        out
    }

    /// KiCad draws teardrops at refill and its DRC then judges them, so a track that clears a pad's
    /// mask opening can still have a teardrop that bridges it. Find those now and route them again
    /// wide of that opening; a route that can't go wide stays and KiCad will say so.
    pub(super) fn fix_teardrops(&mut self) {
        // Benchmark B's project ignores mask bridges, so this would chase what nobody judges.
        if self.rules.severity("solder_mask_bridge") != "error" {
            return;
        }
        // Not a fan-out stub: it has no second pad to route to, and "routing" one would lay nothing.
        let ids: Vec<u32> = self.routes.values().filter(|r| !r.segs.is_empty() && !matches!(r.task.level, Level::Pair | Level::Kelvin) && !(r.task.a == r.task.b && r.task.zone.is_none())).map(|r| r.id).collect();
        for id in ids {
            let Some(old) = self.routes.get(&id).cloned() else { continue };
            let hits = self.teardrop_hits(&old);
            if hits.is_empty() {
                continue;
            }
            self.unplace(id);
            let mut done = false;
            for wide in [0.4, 0.25, 0.15] {
                let mut held = Vec::new();
                for &(_, who, layer) in &hits {
                    let b = self.board.pads[who].shape.bbox();
                    let m = wide * NM;
                    let s = Shape::Poly { pts: vec![V(b.0 - m, b.1 - m), V(b.2 + m, b.1 - m), V(b.2 + m, b.3 + m), V(b.0 - m, b.3 + m)], r: 0.0 };
                    held.push((layer, self.world.layers[layer].add(s, NO_NET, Owner::Keepout)));
                }
                let before = self.next_id;
                let placed = if old.task.zone == Some(RAIL_TAP) { self.try_rail(&old.task) } else { self.try_route_inner(&old.task) };
                for (l, h) in held {
                    self.world.layers[l].remove(h);
                }
                if placed && self.next_id > before {
                    let new = self.next_id - 1;
                    let ok = self.routes.get(&new).map(|r| self.teardrop_hits(r).is_empty()).unwrap_or(false) && self.pieces_apart(old.task.net) <= 1;
                    if ok {
                        done = true;
                        break;
                    }
                    self.unplace(new);
                }
            }
            if done {
                self.log.push(format!("teardrop: {} moved clear of a pad's mask opening", self.board.net_name(old.task.net)));
            } else {
                let task = old.task.clone();
                self.place(old.id, task, old.segs.clone(), old.vias.clone());
                self.notes.push(format!("{}: KiCad's teardrop at {} may bridge {}'s mask opening; no other way in was found", self.board.net_name(old.task.net), self.board.pad_name(hits[0].0), self.board.pad_name(hits[0].1)));
            }
        }
    }

    /// Plane-net pads that the plan left to an outer-layer fill: that fill is the old board's, and
    /// KiCad's refill around the new tracks can cut a pad off it (benchmark C U6.5, U8.5; benchmark B
    /// U3.10). Each gets its own via where one stands (4.2: individual vias for each passive). No
    /// site is no failure here: the fill may well hold, and KiCad's DRC is the judge of that.
    pub(super) fn stitch_fill_pads(&mut self) {
        let planes = self.board.plane_nets();
        let mut count = 0;
        let mut pads: Vec<usize> = self.net_info.iter().filter(|(n, (l, _))| *l == Level::PlaneFanout && planes.contains_key(n)).flat_map(|(_, (_, p))| p.iter().copied()).collect();
        pads.sort_unstable();
        for pad in pads {
            let net = self.board.pads[pad].net;
            let inner = &planes[&net];
            // An exposed pad has its thermal vias already: piprobe_v13's U1 EP got a stub across the
            // +1V1 ring from here before this test.
            let size = self.board.pads[pad].size;
            if (size.0 >= 1.0 * NM && size.1 >= 1.0 * NM) || self.board.pads[pad].layers.iter().any(|l| inner.contains(l)) || self.routes.values().any(|r| r.task.a == pad || r.task.b == pad) {
                continue;
            }
            let task = Task { net, level: Level::PlaneFanout, a: pad, b: pad, main: false, zone: None };
            if self.fan_out_pad(pad, &task) || self.fan_out_search(&task).is_some() {
                count += 1;
            }
        }
        if count > 0 {
            self.log.push(format!("{count} plane-net pads that relied on an old fill got their own via"));
        }
    }

    /// A stuck connection usually isn't stuck by the board, only by the few routes laid around its
    /// pin before it had a turn. Lift everything near its ends, lay it first, and lay them back. Much
    /// cheaper than a restart, and it can't lose ground: the board stays as it was unless every
    /// route lifted finds a place again.
    fn local_restart(&mut self, task: &Task, radius: f64) -> bool {
        let ends: Vec<V> = vec![self.board.pads[task.a].center.into(), self.board.pads[task.b].center.into()];
        let near = |r: &Route| -> bool {
            ends.iter().any(|&e| r.segs.iter().any(|s| pt_seg(e, s.a.into(), s.b.into()) <= radius) || r.vias.iter().any(|v| hypot(sub(e, (*v).into())) <= radius))
        };
        let mut ids: Vec<u32> = self.routes.values().filter(|r| near(r) && !matches!(r.task.level, Level::Pair | Level::Kelvin) && !(r.segs.is_empty() && r.task.a == r.task.b)).map(|r| r.id).collect();
        ids.sort_unstable();
        if ids.is_empty() {
            return false;
        }
        let mut txn = Txn { fuel: ids.len() as i32 * 2 + 4, ..Default::default() };
        let victims = self.take_victims(task, &ids, &mut txn);
        let mode = Mode { escalate: true, swap: false };
        let mut ok = self.displace(task, mode, 0, &mut txn);
        if ok {
            for r in victims {
                let before = txn.added.len();
                if self.splice(&r, &mut txn) {
                    let added: Vec<u32> = txn.added[before..].to_vec();
                    txn.locked.extend(added);
                } else if !self.displace(&r.task, mode, 1, &mut txn) {
                    ok = false;
                    break;
                }
            }
        }
        if ok && self.still_whole(&mut txn, task) {
            return true;
        }
        self.undo(txn);
        false
    }

    /// Rounds over everything still open until a round closes nothing. Then one round of swap
    /// moves, which can walk a hole to a place where it closes; the best state seen is what counts.
    pub(super) fn repair(&mut self, failed: Vec<Task>, best: &mut Option<Best>) -> Vec<Task> {
        let mut open = self.open_work(failed);
        self.keep_if_best(&open, best);
        let mut swaps_left = SWAP_ROUNDS;
        let mut swapped: HashSet<(usize, usize)> = HashSet::new();
        while !open.is_empty() && !self.over_time() {
            let swap = swaps_left > 0 && self.stalled;
            let mut still = Vec::new();
            let before = open.len();
            let mut work: std::collections::VecDeque<Task> = open.into();
            while let Some(task) = work.pop_front() {
                if self.over_time() {
                    still.push(task);
                    continue;
                }
                let t0 = Instant::now();
                let mode = Mode { escalate: true, swap: swap && !swapped.contains(&(task.a, task.b)) };
                // One stuck spot may not eat the run: benchmark B spent 73 s on two tasks.
                let deadline = self.rules.deadline;
                let turn = Instant::now() + std::time::Duration::from_secs_f64(self.rules.time_limit / 10.0);
                self.rules.deadline = deadline.map(|d| d.min(turn));
                let mut r = self.repair_one(&task, mode);
                if matches!(r, Repair::Failed) && task.a != task.b {
                    for radius in [0.8, 1.5, 3.0] {
                        if self.local_restart(&task, radius * NM) {
                            r = Repair::Fixed;
                            self.log.push(format!("{} {}: stuck pin freed by lifting what's within {radius} mm", self.board.net_name(task.net), self.board.pad_name(task.a)));
                            break;
                        }
                    }
                }
                self.rules.deadline = deadline;
                if self.trace {
                    eprintln!("  {:<7.2}s repair {} {} {} -> {} {}", t0.elapsed().as_secs_f64(), match r { Repair::Fixed => "fixed", Repair::Swapped(_) => "swap ", Repair::Failed => "FAIL " }, task.level.name(), self.board.pad_name(task.a), self.board.pad_name(task.b), self.board.net_name(task.net));
                }
                match r {
                    Repair::Fixed => {}
                    Repair::Swapped(t) => {
                        swapped.insert((task.a, task.b));
                        still.push(t);
                    }
                    Repair::Failed => still.push(task),
                }
            }
            open = self.open_work(still);
            self.keep_if_best(&open, best);
            // Only fewer holes counts as progress. The same holes again means the next round
            // would repeat this one exactly, unless a swap changes the board.
            if open.len() < before {
                self.stalled = false;
                continue;
            }
            if self.stalled {
                swaps_left = swaps_left.saturating_sub(1);
                if swaps_left == 0 {
                    break;
                }
            }
            self.stalled = true;
        }
        self.stalled = false;
        self.fix_square_corners();
        self.keep_if_best(&open, best);
        open
    }
}

/// One net's way out of a connector: its stubs on the pads' layer, vias, and any short jog onto a
/// run already on the far layer.
#[derive(Clone)]
struct ExitPlan {
    net: NetId,
    pads: Vec<usize>,
    vias: Vec<P>,
    top: Vec<(P, P)>,
    bottom: Vec<(P, P)>,
    /// Pads of the part that the plan passes inside their class clearance: each needs a local rule.
    close: Vec<(usize, f64)>,
    cost: f64,
}

/// Search reach and how many ways per net go into the combined search.
/// The most of a net that may lie in a big pour once its way out is settled: a stub off a pad.
pub(super) const STUB_RUN: f64 = 1.2 * NM;
const EXIT_STEP: i64 = 50_000;
const EXIT_KEEP: usize = 24;
/// A jog from a via onto its own run, longest and shortest: he stands 0.2 mm off (4.4 "where there is room").
const JOG_MAX: f64 = 0.9 * NM;
const JOG_MIN: f64 = 0.15 * NM;

impl<'a> Router<'a> {
    /// Copper of `net` on `layer` from a to b: clear of everything by class, except this part's own
    /// pads, which may come as close as the standing minimum and are noted for a local rule.
    fn exit_clear(&self, a: P, b: P, half: f64, layer: usize, net: NetId, fp: usize, close: &mut Vec<(usize, f64)>) -> bool {
        let (va, vb): (V, V) = (a.into(), b.into());
        let floor = self.rules.floor.max(self.rules.min.clearance) as f64;
        let reach = half + self.rules.max_clearance() as f64 + self.world.max_local + 1.0;
        let bb = (va.0.min(vb.0) - reach, va.1.min(vb.1) - reach, va.0.max(vb.0) + reach, va.1.max(vb.1) + reach);
        let mut ok = true;
        self.world.layers[layer].visit(bb, |o| {
            if o.net == net || self.world.crosses_pour(o, net) {
                return true;
            }
            let (mine, local) = match o.owner {
                Owner::Pad(i) => (self.board.pads[i as usize].fp == fp, self.world.pad_clearance[i as usize]),
                _ => (false, 0.0),
            };
            let class = (self.rules.clearance_for(net, o.net) as f64).max(local);
            let need = half + if mine { floor.max(local) } else { class };
            let d = o.dist_within(va, vb, (half + class) * 1.01);
            if d < need - DRC_TOL {
                ok = false;
                return false;
            }
            if let (true, Owner::Pad(i)) = (mine && d < half + class - DRC_TOL, o.owner) {
                close.push((i as usize, d - half));
            }
            true
        });
        ok && self.world.mask.seg_hit(net, layer, va, vb, half).is_none() && self.world.holes_clear(&self.rules, va, vb, half, net)
    }

    fn exit_via_ok(&self, s: P, net: NetId, fp: usize, close: &mut Vec<(usize, f64)>) -> bool {
        let (dia, drill) = self.rules.via_for(net);
        let vr = dia as f64 / 2.0;
        let own = vr + self.rules.pad_via_gap as f64;
        let v: V = s.into();
        if self.board.pads.iter().any(|p| p.net == net && !p.layers.is_empty() && hypot(sub(p.center.into(), v)) < 3.0 * NM && p.shape.dist_pt(v) < own) {
            return false;
        }
        if self.world.mask.via_hit(net, v, vr).is_some() || !self.world.holes_clear(&self.rules, v, v, vr, net) {
            return false;
        }
        let hole = drill as f64 / 2.0 + self.rules.hole_to_hole() as f64;
        let mut clear = true;
        self.world.holes.visit((v.0 - hole, v.1 - hole, v.0 + hole, v.1 + hole), |o| {
            if o.shape.dist_pt(v) < hole {
                clear = false;
                return false;
            }
            true
        });
        if !clear {
            return false;
        }
        (0..self.board.layers.len()).filter(|&l| self.board.layers[l].signal).all(|l| self.exit_clear(s, s, vr, l, net, fp, close))
    }

    /// Pad centre to a via: straight if it can be, else one 45-degree bend either way round.
    fn exit_stub(&self, c: P, s: P, layer: usize, net: NetId, fp: usize, close: &mut Vec<(usize, f64)>) -> Option<Vec<(P, P)>> {
        self.exit_stub_at(c, s, layer, net, fp, self.rules.neck, close)
    }

    fn exit_stub_at(&self, c: P, s: P, layer: usize, net: NetId, fp: usize, width: i64, close: &mut Vec<(usize, f64)>) -> Option<Vec<(P, P)>> {
        let half = width as f64 / 2.0;
        let (dx, dy) = (s.0 - c.0, s.1 - c.1);
        let (ax, ay) = (dx.abs(), dy.abs());
        let m = ax.min(ay);
        let (sx, sy) = (dx.signum(), dy.signum());
        let diag = (sx * m, sy * m);
        let straight = if ax > ay { (sx * (ax - ay), 0) } else { (0, sy * (ay - ax)) };
        let mut ways: Vec<Vec<(P, P)>> = Vec::new();
        if m == 0 || ax == ay {
            ways.push(vec![(c, s)]);
        } else {
            // Straight off the pad first (reference exits), then the 45.
            let e1 = snap((c.0 + straight.0, c.1 + straight.1));
            let e2 = snap((c.0 + diag.0, c.1 + diag.1));
            ways.push(vec![(c, e1), (e1, s)]);
            ways.push(vec![(c, e2), (e2, s)]);
        }
        for w in ways {
            let mut got = Vec::new();
            if w.iter().all(|(a, b)| self.exit_clear(*a, *b, half, layer, net, fp, &mut got)) {
                close.extend(got);
                return Some(w);
            }
        }
        None
    }

    /// From a via, the shortest straight jog onto the net's run on `layer`, standing off it (4.4).
    fn exit_jog(&self, v: P, layer: usize, net: NetId, fp: usize, close: &mut Vec<(usize, f64)>) -> Option<(P, P, f64)> {
        let segs: Vec<Seg> = self.routes.values().filter(|r| r.task.net == net).flat_map(|r| r.segs.iter().cloned()).filter(|s| s.layer == layer).collect();
        let at: V = v.into();
        let mut best: Option<(P, P, f64)> = None;
        for s in &segs {
            if pt_seg(at, s.a.into(), s.b.into()) < JOG_MIN {
                return None;
            }
            let (sa, sb): (V, V) = (s.a.into(), s.b.into());
            for (dx, dy) in DIRS {
                let (ux, uy) = (dx as f64, dy as f64);
                let (ex, ey) = (sb.0 - sa.0, sb.1 - sa.1);
                let denom = ux * ey - uy * ex;
                if denom.abs() < 1e-6 {
                    continue;
                }
                // A branch joins as a Y, never square (4.2).
                if (ux * ex + uy * ey).abs() < 1e-6 * hypot(V(ex, ey)) {
                    continue;
                }
                let (wx, wy) = (sa.0 - at.0, sa.1 - at.1);
                let t = (wx * ey - wy * ex) / denom;
                let u = (wx * uy - wy * ux) / denom;
                let len = t * hypot(V(ux, uy));
                if t <= 0.0 || !(0.0..=1.0).contains(&u) || len > JOG_MAX {
                    continue;
                }
                let hit = (at.0 + ux * t, at.1 + uy * t);
                let q = (hit.0.round() as i64, hit.1.round() as i64);
                if best.map(|b| len < b.2).unwrap_or(true) {
                    let half = s.width as f64 / 2.0;
                    let mut got = Vec::new();
                    if self.exit_clear(v, q, half, layer, net, fp, &mut got) {
                        close.extend(got);
                        best = Some((v, q, len));
                    }
                }
            }
        }
        best
    }

    /// Every way worth trying for one net's pads on this part, cheapest first.
    fn exit_ways(&self, net: NetId, pads: &[usize], fp: usize, far: usize, on_run: bool) -> Vec<ExitPlan> {
        let top = self.board.pads[pads[0]].layers[0];
        let reach = (POUR_RUN as i64) / EXIT_STEP;
        let centers: Vec<P> = pads.iter().map(|&p| snap(self.board.pads[p].center)).collect();
        let mid = (centers.iter().map(|c| c.0).sum::<i64>() / centers.len() as i64, centers.iter().map(|c| c.1).sum::<i64>() / centers.len() as i64);
        let mut out: Vec<ExitPlan> = Vec::new();
        for ix in -reach..=reach {
            for iy in -reach..=reach {
                let s = snap((mid.0 + ix * EXIT_STEP, mid.1 + iy * EXIT_STEP));
                let v: V = s.into();
                if centers.iter().any(|c| {
                    let (ax, ay) = ((c.0 - s.0).abs() as f64, (c.1 - s.1).abs() as f64);
                    ax.max(ay) + (SQRT2 - 1.0) * ax.min(ay) > POUR_RUN
                }) {
                    continue;
                }
                let mut close = Vec::new();
                if !self.exit_via_ok(s, net, fp, &mut close) {
                    continue;
                }
                let mut topway = Vec::new();
                if !centers.iter().all(|c| match self.exit_stub(*c, s, top, net, fp, &mut close) {
                    Some(w) => {
                        topway.extend(w);
                        true
                    }
                    None => false,
                }) {
                    continue;
                }
                let mut bottom = Vec::new();
                if on_run {
                    match self.exit_jog(s, far, net, fp, &mut close) {
                        Some((a, b, _)) => bottom.push((a, b)),
                        None => continue,
                    }
                }
                let len = |w: &[(P, P)]| w.iter().map(|(a, b)| hypot(sub((*a).into(), (*b).into()))).sum::<f64>();
                let mut rule_pads: Vec<usize> = close.iter().map(|c| c.0).collect();
                rule_pads.sort_unstable();
                rule_pads.dedup();
                // Each exception weighs what 0.5 mm of stub does: fewest first, but not at any price.
                let cost = len(&topway) + 0.5 * len(&bottom) + 0.5 * NM * rule_pads.len() as f64;
                let _ = v;
                out.push(ExitPlan { net, pads: pads.to_vec(), vias: vec![s], top: topway, bottom, close, cost });
            }
        }
        out.sort_by(|a, b| a.cost.total_cmp(&b.cost));
        // Spread out, or the search only sees one spot many times over.
        let mut kept: Vec<ExitPlan> = Vec::new();
        for w in out {
            if kept.iter().all(|k| hypot(sub(k.vias[0].into(), w.vias[0].into())) >= 0.1 * NM) {
                kept.push(w);
                if kept.len() >= EXIT_KEEP {
                    break;
                }
            }
        }
        kept
    }

    fn exits_fit(&self, a: &ExitPlan, b: &ExitPlan) -> bool {
        let clr = self.rules.clearance_for(a.net, b.net) as f64 - DRC_TOL;
        let half = self.rules.neck as f64 / 2.0;
        let vr = |p: &ExitPlan| self.rules.via_for(p.net).0 as f64 / 2.0;
        let (ra, rb) = (vr(a), vr(b));
        let hole = (self.rules.via_for(a.net).1 + self.rules.via_for(b.net).1) as f64 / 2.0 + self.rules.hole_to_hole() as f64;
        for &x in &a.vias {
            for &y in &b.vias {
                let d = hypot(sub(x.into(), y.into()));
                if d < ra + rb + clr || d < hole {
                    return false;
                }
            }
            for (p, q) in b.top.iter().chain(&b.bottom) {
                if pt_seg(x.into(), (*p).into(), (*q).into()) < ra + half + clr {
                    return false;
                }
            }
        }
        for &y in &b.vias {
            for (p, q) in a.top.iter().chain(&a.bottom) {
                if pt_seg(y.into(), (*p).into(), (*q).into()) < rb + half + clr {
                    return false;
                }
            }
        }
        for (list_a, list_b) in [(&a.top, &b.top), (&a.bottom, &b.bottom)] {
            for (p, q) in list_a {
                for (r, s) in list_b {
                    if seg_seg((*p).into(), (*q).into(), (*r).into(), (*s).into()) < 2.0 * half + clr {
                        return false;
                    }
                }
            }
        }
        true
    }

    /// Lay every exit of this connector as one plan: the cheapest combination in which all of its nets
    /// fit together. The nets of the run through it join it by a jog; the others keep a via their own
    /// routes start from. False leaves the board untouched.
    pub(super) fn plan_exits(&mut self, fp: usize, run: [NetId; 2], far: usize) -> bool {
        let mut by_net: Vec<(NetId, Vec<usize>)> = Vec::new();
        for &i in &self.board.footprints[fp].pads {
            if !self.pour_exit_pads.contains(&i) || looks_ground(self.board.net_name(self.board.pads[i].net)) {
                continue;
            }
            let net = self.board.pads[i].net;
            match by_net.iter_mut().find(|x| x.0 == net) {
                Some(x) => x.1.push(i),
                None => by_net.push((net, vec![i])),
            }
        }
        if by_net.is_empty() {
            return false;
        }
        // A net's pads share a via if that works; otherwise each has its own, as his A7 and B7 do.
        let mut options: Vec<Vec<Vec<ExitPlan>>> = Vec::new();
        for (net, pads) in &by_net {
            let on_run = run.contains(net);
            let mut ways: Vec<Vec<ExitPlan>> = self.exit_ways(*net, pads, fp, far, on_run).into_iter().map(|w| vec![w]).collect();
            if pads.len() == 2 {
                let (a, b) = (self.exit_ways(*net, &pads[..1], fp, far, on_run), self.exit_ways(*net, &pads[1..], fp, far, on_run));
                for x in a.iter().take(10) {
                    for y in b.iter().take(10) {
                        if hypot(sub(x.vias[0].into(), y.vias[0].into())) >= self.rules.via_for(*net).0 as f64 + 0.15 * NM {
                            ways.push(vec![x.clone(), y.clone()]);
                        }
                    }
                }
            }
            if ways.is_empty() {
                self.log.push(format!("exits: {} has no legal way off {}", self.board.net_name(*net), self.board.footprints[fp].reference));
                return false;
            }
            let cost = |w: &Vec<ExitPlan>| w.iter().map(|p| p.cost).sum::<f64>();
            ways.sort_by(|a, b| cost(a).total_cmp(&cost(b)));
            ways.truncate(EXIT_KEEP * 2);
            options.push(ways);
        }
        // The tightest net first, so a dead end shows early.
        options.sort_by_key(|w| w.len());
        let mut best: Option<(f64, Vec<usize>)> = None;
        let mut pick = vec![0usize; options.len()];
        self.exit_search(&options, 0, 0.0, &mut pick, &mut best);
        let Some((_, chosen)) = best else {
            self.log.push(format!("exits: no combination fits at {}", self.board.footprints[fp].reference));
            return false;
        };
        let name = self.board.footprints[fp].reference.clone();
        let far_layer = far;
        for (k, &c) in chosen.iter().enumerate() {
            for plan in options[k][c].clone() {
                let top = self.board.pads[plan.pads[0]].layers[0];
                let neck = self.rules.neck;
                let run_w = self.routes.values().filter(|r| r.task.net == plan.net).flat_map(|r| r.segs.iter()).find(|s| s.layer == far_layer).map(|s| s.width).unwrap_or(neck);
                let mut segs: Vec<Seg> = plan.top.iter().filter(|(a, b)| a != b).map(|(a, b)| Seg { a: *a, b: *b, layer: top, width: neck }).collect();
                segs.extend(plan.bottom.iter().filter(|(a, b)| a != b).map(|(a, b)| Seg { a: *a, b: *b, layer: far_layer, width: run_w }));
                let (a, b) = (plan.pads[0], *plan.pads.last().unwrap());
                let task = Task { net: plan.net, level: Level::Pair, a, b, main: false, zone: None };
                let id = self.fresh_id();
                self.place(id, task, segs, plan.vias.clone());
                self.exit_tasks.insert((a, b));
                if !run.contains(&plan.net) {
                    for &p in &plan.pads {
                        self.exit_via.insert(p, plan.vias[0]);
                    }
                }
                // Exceptions, each at what the plan really leaves.
                let net_name = self.board.net_name(plan.net).to_string();
                let mut seen: HashMap<usize, f64> = HashMap::new();
                for (pad, room) in &plan.close {
                    let e = seen.entry(*pad).or_insert(*room);
                    *e = e.min(*room);
                }
                for (pad, room) in seen {
                    let number = self.board.pads[pad].number.clone();
                    let min = ((room / 1000.0).floor() as i64 * 1000).max(self.rules.floor.max(self.rules.min.clearance));
                    if !self.rules.pad_rules.iter().any(|r| r.net == net_name && r.reference == name && r.pad == number && r.min <= min) {
                        self.rules.pad_rules.retain(|r| !(r.net == net_name && r.reference == name && r.pad == number));
                        self.rules.pad_rules.push(PadRule { net: net_name.clone(), reference: name.clone(), pad: number, min });
                    }
                }
            }
        }
        self.rules.bind(self.board);
        self.log.push(format!("exits: planned {} nets off {} as one group", chosen.len(), name));
        true
    }

    fn exit_search(&self, options: &[Vec<Vec<ExitPlan>>], k: usize, cost: f64, pick: &mut Vec<usize>, best: &mut Option<(f64, Vec<usize>)>) {
        if best.as_ref().map(|b| cost >= b.0).unwrap_or(false) {
            return;
        }
        if k == options.len() {
            *best = Some((cost, pick.clone()));
            return;
        }
        for (c, way) in options[k].iter().enumerate() {
            let fits = (0..k).all(|j| options[j][pick[j]].iter().all(|a| way.iter().all(|b| self.exits_fit(a, b))));
            if !fits {
                continue;
            }
            pick[k] = c;
            self.exit_search(options, k + 1, cost + way.iter().map(|p| p.cost).sum::<f64>(), pick, best);
        }
    }

    /// A stub from a pad to the nearest through-hole pad of its net on the same part, if one is close.
    pub(super) fn tie_to_sibling(&mut self, pad: usize, task: &Task) -> bool {
        const TIE_MAX: f64 = 2.5 * NM;
        let p = self.board.pads[pad].clone();
        let Some(&layer) = p.layers.first() else { return false };
        let c = snap(p.center);
        let net = p.net;
        let fp = p.fp;
        let mut near: Vec<(f64, P)> = self.board.footprints[fp].pads.iter().copied().filter(|&q| q != pad).map(|q| &self.board.pads[q]).filter(|q| q.net == net && q.layers.len() > 1 && q.layers.contains(&layer)).map(|q| (hypot(sub(q.center.into(), p.center.into())), snap(q.center))).filter(|x| x.0 <= TIE_MAX + 2.0 * NM).collect();
        near.sort_by(|a, b| a.0.total_cmp(&b.0));
        for (_, to) in near {
            for width in [mm(0.4), self.rules.track, self.rules.neck] {
                let mut close = Vec::new();
                if let Some(way) = self.exit_stub_at(c, to, layer, net, fp, width, &mut close) {
                    if !close.is_empty() {
                        continue;
                    }
                    let segs: Vec<Seg> = way.iter().filter(|(a, b)| a != b).map(|(a, b)| Seg { a: *a, b: *b, layer, width }).collect();
                    let id = self.fresh_id();
                    self.place(id, Task { level: Level::Pair, zone: None, main: false, ..task.clone() }, segs, Vec::new());
                    return true;
                }
            }
        }
        false
    }

    /// After the best board is put back: which pads start from a planned via.
    pub(super) fn rebuild_exit_vias(&mut self) {
        self.exit_via.clear();
        let run_nets: Vec<(usize, usize, P)> = self.routes.values().filter(|r| self.exit_tasks.contains(&(r.task.a, r.task.b)) && !r.vias.is_empty() && !r.segs.iter().any(|s| s.layer != self.board.pads[r.task.a].layers[0])).map(|r| (r.task.a, r.task.b, r.vias[0])).collect();
        for (a, b, v) in run_nets {
            self.exit_via.insert(a, v);
            self.exit_via.insert(b, v);
        }
    }
}