AI Flow: Routing

//! The search. Not a grid: an implicit lattice of exact 0/45/90 degree lines through every pad
//! centre and along every obstacle at exact clearance, so a route hugs copper at the clearance it
//! asked for, leaves a pin straight along the pin's own line, and has few bends by construction.
//!
//! What is borrowed from road navigation:
//! - Direction is part of the search state (OSRM's edge-based graph), so a turn's cost is exact
//!   instead of depending on which path reached a cell first.
//! - The search runs in rounds by layer changes (RAPTOR's rounds by transfers): first with no via
//!   at all, then with vias, so "don't hop to the bottom layer where the top works" is structural.
//!
//! What is borrowed from routers: a legality check against real copper at every step, a slightly
//! inflated A* heuristic (VTR, nextpnr), soft search for finding who is in the way (Freerouting's
//! rip-in-search, KiCadRoutingTools' blocker analysis).
//!
//! What the search can't see from where it stands comes from global.rs: a coarse map that gives the
//! estimate its true way round obstacles, proves "no path" early, and carries the board-wide plan.

use crate::board::*;
use crate::geom::*;
use crate::index::*;
use crate::rules::Rules;
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};

/// A fast multiplicative hash for the search's state table. SipHash took 18 of 61 s on benchmark C
/// (measured with timers round every call), and these keys aren't attacker-controlled.
#[derive(Default, Clone, Copy)]
pub struct Fx(u64);
impl std::hash::Hasher for Fx {
    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }
    #[inline]
    fn write(&mut self, b: &[u8]) {
        for &x in b {
            self.write_u64(x as u64);
        }
    }
    #[inline]
    fn write_u8(&mut self, v: u8) {
        self.write_u64(v as u64);
    }
    #[inline]
    fn write_i64(&mut self, v: i64) {
        self.write_u64(v as u64);
    }
    #[inline]
    fn write_u64(&mut self, v: u64) {
        self.0 = (self.0.rotate_left(5) ^ v).wrapping_mul(0x517c_c1b7_2722_0a95);
    }
}
pub type FxBuild = std::hash::BuildHasherDefault<Fx>;

pub const DIRS: [(i64, i64); 8] = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)];
const NO_DIR: u8 = 8;

/// Guide lines, by family: x = a, y = b, x - y = c, x + y = e. All constants are even nanometres,
/// so every crossing is a whole nanometre.
#[derive(Default, Clone)]
pub struct Lines {
    pub v: Vec<i64>,
    pub h: Vec<i64>,
    pub dp: Vec<i64>,
    pub dm: Vec<i64>,
}

#[inline]
fn even_up(v: f64) -> i64 {
    let x = v.ceil() as i64;
    x + (x & 1)
}
#[inline]
fn even_down(v: f64) -> i64 {
    let x = v.floor() as i64;
    x - (x & 1)
}
pub fn snap(p: P) -> P {
    (p.0 & !1, p.1 & !1)
}

impl Lines {
    pub fn add_point(&mut self, p: P) {
        let p = snap(p);
        self.v.push(p.0);
        self.h.push(p.1);
        self.dp.push(p.0 - p.1);
        self.dm.push(p.0 + p.1);
    }
    /// The eight tangents of an outline at distance `r`, rounded outward so clearance is kept.
    pub fn add_tangents(&mut self, s: &Shape, r: f64) {
        let rd = r * SQRT2;
        self.v.push(even_up(s.support(1.0, 0.0) + r));
        self.v.push(even_down(-s.support(-1.0, 0.0) - r));
        self.h.push(even_up(s.support(0.0, 1.0) + r));
        self.h.push(even_down(-s.support(0.0, -1.0) - r));
        self.dp.push(even_up(s.support(1.0, -1.0) + rd));
        self.dp.push(even_down(-s.support(-1.0, 1.0) - rd));
        self.dm.push(even_up(s.support(1.0, 1.0) + rd));
        self.dm.push(even_down(-s.support(-1.0, -1.0) - rd));
    }
    pub fn finish(&mut self) {
        for v in [&mut self.v, &mut self.h, &mut self.dp, &mut self.dm] {
            v.sort_unstable();
            v.dedup();
        }
    }
    #[inline]
    fn on_family(&self, p: P, d: u8) -> bool {
        match d % 4 {
            0 => self.h.binary_search(&p.1).is_ok(),
            1 => self.dp.binary_search(&(p.0 - p.1)).is_ok(),
            2 => self.v.binary_search(&p.0).is_ok(),
            _ => self.dm.binary_search(&(p.0 + p.1)).is_ok(),
        }
    }
    /// Distance along direction `d`, in axis steps, to the next crossing line.
    #[inline]
    fn next_stop(&self, p: P, d: u8) -> Option<i64> {
        let (dx, dy) = DIRS[d as usize];
        let mut t = i64::MAX;
        let next = |a: &[i64], val: i64, up: bool| -> Option<i64> {
            if up {
                let i = a.partition_point(|&x| x <= val);
                a.get(i).map(|&x| x - val)
            } else {
                let i = a.partition_point(|&x| x < val);
                if i > 0 { Some(val - a[i - 1]) } else { None }
            }
        };
        if dx != 0 {
            if let Some(s) = next(&self.v, p.0, dx > 0) {
                t = t.min(s);
            }
        }
        if dy != 0 {
            if let Some(s) = next(&self.h, p.1, dy > 0) {
                t = t.min(s);
            }
        }
        let sp = dx - dy;
        if sp != 0 {
            if let Some(s) = next(&self.dp, p.0 - p.1, sp > 0) {
                t = t.min((s + sp.abs() - 1) / sp.abs());
            }
        }
        let sm = dx + dy;
        if sm != 0 {
            if let Some(s) = next(&self.dm, p.0 + p.1, sm > 0) {
                t = t.min((s + sm.abs() - 1) / sm.abs());
            }
        }
        if t == i64::MAX { None } else { Some(t) }
    }
}

/// Everything already on the board that a route must respect.
/// How much dearer a millimetre inside a pour to leave is than one anywhere else.
const POUR_AVOID_COST: f64 = 8.0;
/// What straying from the bus line before costs per unit length, at two pitches or more away.
const FOLLOW_COST: f64 = 3.0;
/// What a millimetre costs on top of the pair partner's track on another layer. Two tracks stacked
/// through the board are a wall on both layers: on adom/carrier-fc-rp2350a-mini a split USB pair ran
/// stacked for the module's whole height and sealed nine pads behind it.
const STACK_COST: f64 = 6.0;
/// What a millimetre costs inside the thermal-relief gap of another net's pad. KiCad wants two
/// spokes from each such pad into its pour (starved_thermal otherwise); a track through the gap
/// takes the spokes on that side. A cost, not a wall: one side lost is allowed, and where there is
/// no other way the track still goes. a flight controller board came back with 9 starved pads.
const RELIEF_COST: f64 = 2.5;
/// How near the partner's centre line counts as on top of it.
const STACK_BAND: f64 = 0.6 * NM;

pub struct World {
    pub layers: Vec<Grid>,
    pub holes: Grid,
    pub edge: Grid,
    pub route_layers: Vec<usize>,
    pub escapes: Vec<(f64, f64, f64, f64)>,
    pub zones: Vec<(NetId, usize, Vec<V>)>,
    /// The coarse map, its backward searches and the board-wide plan; see global.rs.
    pub guide: std::cell::RefCell<crate::global::Guide>,
    /// The bus line routed just before this one, on its layer: (layer, its segments, the pitch to
    /// keep from it). Running farther than the pitch costs extra, so a bus comes out as parallel
    /// lines, each passing a pad row's gaps on its own, as his benchmark B bus does.
    pub follow: std::cell::RefCell<Option<(usize, Vec<(V, V)>, f64)>>,
    /// Nets with an approved current (the spec's `rails`). Their tracks keep their width on every
    /// layer and neck only for the last stretch into a terminal: the width is what carries the
    /// current, so a stub layer at neck width (4.2's habit for unrated rails) is not allowed them.
    pub rail_nets: std::collections::HashSet<NetId>,
    /// Pads' solder mask openings: foreign copper may not bridge one (KiCad's solder_mask_bridge).
    pub mask: crate::mask::MaskMap,
    /// Each pad's own clearance override, nm (0 when it has none).
    pub pad_clearance: Vec<f64>,
    pub max_local: f64,
    /// Per zone: the other nets with a pad inside its outline. Such a pour can't be a wall to them:
    /// they have to get out, and KiCad refills around them. On benchmark B the USB connector
    /// sits inside the VBUS pour, and his own D+, D-, CC and GND copper crosses it.
    pub pour_open: Vec<Vec<NetId>>,
    /// Big pours each net with a pad inside them should leave at once: layer and outline. Copper in
    /// one costs extra in the search itself, so the way round is found rather than rejected after.
    pub pour_avoid: HashMap<NetId, Vec<(usize, Vec<V>)>>,
    /// Pads that join their own net's pour through thermal spokes, per layer, and each one's relief
    /// gap (by pad index; 0 where there is none). Copper of another net inside that gap cuts spokes:
    /// see RELIEF_COST.
    pub relief: Vec<Grid>,
    pub relief_gap: Vec<f64>,
    pub relief_reach: f64,
    /// Each net of a differential pair and its partner. A pair that could not be coupled is routed
    /// as two tracks; the second must not run on top of the first on another layer (see STACK_COST).
    pub partner: HashMap<NetId, NetId>,
    /// The tracks now on the board for each pair net: (route id, layer, ends). Kept by place/unplace.
    pub pair_segs: std::cell::RefCell<HashMap<NetId, Vec<(u32, usize, V, V)>>>,
}

#[derive(Clone, Copy, Debug)]
pub struct Profile {
    /// Track width on open runs, and inside a fine-pitch escape.
    pub width: i64,
    pub neck: i64,
    /// Hard minimum gap to other nets.
    pub clearance: i64,
    /// Preferred gap (3W target); less costs extra, never below `clearance`.
    pub target_gap: i64,
    pub max_vias: u32,
    pub margin: f64,
    /// A rail's bus layer. `width` then applies on this layer only, everywhere on it; on the other
    /// layers the route is a stub at `neck` and each mm costs more.
    pub layer_bias: Option<usize>,
}

#[derive(Clone, Debug)]
pub enum Terminal {
    /// A pad centre, on any of these layers.
    Point { p: P, layers: Vec<usize> },
    /// Anywhere inside this net's zone copper on a layer.
    Zone { layer: usize, poly: Vec<V> },
    /// Anywhere along a routed track of this net: a tap onto a rail (4.2). `wide` rails take a stub
    /// at 45 or 90 degrees, others only a Y. `stand_off` is how far a via must stay off the track,
    /// measured along the stub (4.4: no via inside a trace, branch 0.6-0.85 mm to the side).
    Track { a: P, b: P, layer: usize, wide: bool, stand_off: f64 },
}

/// A rail's cost per mm off its bus layer (`Profile::layer_bias`): stubs go to the bus and stop.
pub const OFF_BUS: f64 = 3.0;
const RAIL_WEIGHT: f64 = 2.0;

#[derive(Clone, Debug, Default)]
pub struct Path {
    /// Points with their layer; a layer change between neighbours is a via.
    pub pts: Vec<(P, usize)>,
    pub vias: u32,
    pub cost: f64,
    /// Other routes' connection ids this path crosses (only in a soft search).
    pub blockers: Vec<u32>,
    pub nodes: usize,
}

pub struct Query<'a> {
    pub net: NetId,
    /// Nets treated as own copper (a pair searches for both its nets together).
    pub also: Option<NetId>,
    pub sources: &'a [Terminal],
    pub targets: &'a [Terminal],
    pub profile: Profile,
    pub rules: &'a Rules,
    /// May cross routed copper in this set, at a price (who is in the way?).
    pub soft: Option<&'a dyn Fn(u32) -> f64>,
    /// Via stand-off from these pads is waived (own exposed pad).
    pub via_in: Option<usize>,
    pub history: Option<&'a History>,
    /// Circles where clearance isn't checked: a pair's centreline inside its own fan-in. The two
    /// real tracks and their stubs are checked exactly afterwards.
    pub free: &'a [(P, f64)],
    /// The direction the route continues in after the target, so it doesn't arrive at an acute
    /// angle (a stub joining a pair's coupled run).
    pub arrive: Option<u8>,
}

/// How contested each part of the board has been: raised where nets fought, decayed each pass
/// (FastRoute's 0.9 per pass, CUGR's fade). Only contested places are raised, not whole routes.
pub struct History {
    pub x0: f64,
    pub y0: f64,
    pub cell: f64,
    pub w: usize,
    pub h: usize,
    pub v: Vec<f32>,
}

impl History {
    pub fn new(bb: (f64, f64, f64, f64)) -> History {
        let cell = 0.5 * NM;
        let w = ((bb.2 - bb.0) / cell).ceil() as usize + 2;
        let h = ((bb.3 - bb.1) / cell).ceil() as usize + 2;
        History { x0: bb.0, y0: bb.1, cell, w, h, v: vec![0.0; w * h] }
    }
    #[inline]
    pub fn at(&self, p: V) -> f32 {
        let i = ((p.0 - self.x0) / self.cell).max(0.0) as usize;
        let j = ((p.1 - self.y0) / self.cell).max(0.0) as usize;
        if i < self.w && j < self.h { self.v[j * self.w + i] } else { 0.0 }
    }
    pub fn bump(&mut self, p: V) {
        let i = ((p.0 - self.x0) / self.cell).max(0.0) as usize;
        let j = ((p.1 - self.y0) / self.cell).max(0.0) as usize;
        if i < self.w && j < self.h {
            self.v[j * self.w + i] += 1.0;
        }
    }
    pub fn decay(&mut self) {
        for x in &mut self.v {
            *x *= 0.9;
        }
    }
}

impl World {
    /// Whether this copper is a pour this net may cross.
    pub fn crosses_pour(&self, o: &Obs, net: NetId) -> bool {
        match o.owner {
            Owner::Zone(z) => self.pour_open.get(z as usize).map(|v| v.binary_search(&net).is_ok()).unwrap_or(false),
            _ => false,
        }
    }

    pub fn in_escape(&self, p: V) -> bool {
        self.escapes.iter().any(|b| p.0 >= b.0 && p.0 <= b.2 && p.1 >= b.1 && p.1 <= b.3)
    }

    /// Smallest edge distance from a centreline to copper of other nets on a layer, stopping once
    /// it is certainly below `floor` (then a blocker that is not soft-crossable has been met).
    #[inline]
    #[allow(clippy::too_many_arguments)]
    fn gap(&self, rules: &Rules, base: i64, layer: usize, a: V, b: V, net: NetId, also: NetId, reach: f64, floor: f64, soft: Option<&dyn Fn(u32) -> f64>, blockers: &mut Vec<u32>, soft_cost: &mut f64) -> f64 {
        // Clearance is per pair of nets, as KiCad judges it: a 0.5 mm class pushes only what's beside
        // it. The returned gap is normalised to `base`, so callers compare it against one number.
        let reach = reach + (rules.max_clearance() - base).max(0) as f64 + self.max_pad_clearance();
        let bb = (a.0.min(b.0) - reach, a.1.min(b.1) - reach, a.0.max(b.0) + reach, a.1.max(b.1) + reach);
        let mut best = f64::INFINITY;
        self.layers[layer].visit(bb, |o| {
            if o.net == net && net != NO_NET {
                return true;
            }
            if o.net == also && also != NO_NET {
                return true;
            }
            if self.crosses_pour(o, net) {
                return true;
            }
            let local = if let Owner::Pad(i) = o.owner { self.pad_clearance[i as usize] } else { 0.0 };
            let pad = if let Owner::Pad(i) = o.owner { Some(i) } else { None };
            let d = o.dist_within(a, b, reach) - ((rules.clearance_at(net, o.net, pad) as f64).max(local) - base as f64);
            if d < floor {
                if let (Some(f), Owner::Conn(c)) = (soft, o.owner) {
                    let price = f(c);
                    if price.is_finite() {
                        if !blockers.contains(&c) {
                            blockers.push(c);
                            *soft_cost += price;
                        }
                        return true;
                    }
                }
                best = d;
                return false;
            }
            best = best.min(d);
            true
        });
        best
    }

    /// Edge distance from a centreline to the nearest copper of another net within `reach`, less
    /// any extra clearance that net pair needs over the board's: the room a track has.
    pub fn room(&self, rules: &Rules, layer: usize, a: V, b: V, net: NetId, reach: f64) -> f64 {
        let (mut blockers, mut cost) = (Vec::new(), 0.0);
        self.gap(rules, rules.clearance, layer, a, b, net, NO_NET, reach, f64::NEG_INFINITY, None, &mut blockers, &mut cost).min(reach)
    }

    #[inline]
    pub fn max_pad_clearance(&self) -> f64 {
        self.max_local
    }

    /// Whether a track stays clear of every through hole of another net, plated or not: every
    /// layer sees every hole (KiCad's hole_clearance).
    pub fn holes_clear(&self, rules: &Rules, a: V, b: V, half: f64, net: NetId) -> bool {
        self.holes_clear_also(rules, a, b, half, net, NO_NET)
    }

    /// `holes_clear` for copper shared by a pair: the partner's holes are not another net's.
    pub fn holes_clear_also(&self, rules: &Rules, a: V, b: V, half: f64, net: NetId, also: NetId) -> bool {
        let need = half + rules.hole_clearance() as f64;
        let far = need + self.max_pad_clearance();
        let bb = (a.0.min(b.0) - far, a.1.min(b.1) - far, a.0.max(b.0) + far, a.1.max(b.1) + far);
        let mut ok = true;
        self.holes.visit(bb, |o| {
            if (o.net == net && net != NO_NET) || (o.net == also && also != NO_NET) || matches!(o.shape, Shape::Poly { .. }) {
                return true;
            }
            let local = if let Owner::Pad(i) = o.owner { self.pad_clearance[i as usize] + half } else { 0.0 };
            if o.shape.dist_seg(a, b) < need.max(local) {
                ok = false;
                return false;
            }
            true
        });
        ok
    }

    fn edge_gap(&self, a: V, b: V, reach: f64) -> f64 {
        let bb = (a.0.min(b.0) - reach, a.1.min(b.1) - reach, a.0.max(b.0) + reach, a.1.max(b.1) + reach);
        let mut best = f64::INFINITY;
        self.edge.visit(bb, |o| {
            best = best.min(o.shape.dist_seg(a, b));
            true
        });
        best
    }

    /// Whether a through via can stand here: copper clear on every layer, holes apart, on the
    /// board, and off every pad (via-in-pad needs a decision, 4.4).
    pub fn via_ok(&self, p: P, q: &Query, soft: Option<&dyn Fn(u32) -> f64>, blockers: &mut Vec<u32>, soft_cost: &mut f64) -> bool {
        let r = q.rules;
        let c: V = p.into();
        // The net class's via, not the board's: the size 2.2 says the class may set.
        let (via_dia, via_drill) = r.via_for(q.net);
        let vr = via_dia as f64 / 2.0;
        let also = q.also.unwrap_or(NO_NET);
        let base = r.clearance_for(q.net, q.net);
        for l in 0..self.layers.len() {
            // A micron over: a pad corner here is a polygon inside KiCad's arc (benchmark C: 0.1994 against 0.2).
            let need = vr + base as f64 + 1000.0;
            let d = self.gap(r, base, l, c, c, q.net, also, need, need, soft, blockers, soft_cost);
            if d < need {
                return false;
            }
        }
        // Own-net pads: the via sits just clear of the pad, not in it.
        let own = vr + r.pad_via_gap as f64;
        let bb = (c.0 - own, c.1 - own, c.0 + own, c.1 + own);
        let mut clear = true;
        for l in [0, self.layers.len() - 1] {
            self.layers[l].visit(bb, |o| {
                if let Owner::Pad(i) = o.owner {
                    if (o.net == q.net || (also != NO_NET && o.net == also)) && Some(i as usize) != q.via_in && o.shape.dist_pt(c) < own {
                        clear = false;
                        return false;
                    }
                }
                true
            });
        }
        if !clear {
            return false;
        }
        if self.mask.via_hit(q.net, c, vr).is_some() || !self.holes_clear(r, c, c, vr, q.net) {
            return false;
        }
        let hole = via_drill as f64 / 2.0 + r.hole_to_hole() as f64;
        let bb = (c.0 - hole, c.1 - hole, c.0 + hole, c.1 + hole);
        self.holes.visit(bb, |o| {
            if o.shape.dist_pt(c) < hole {
                clear = false;
                return false;
            }
            true
        });
        if !clear {
            return false;
        }
        let e = vr + r.edge as f64;
        self.edge_gap(c, c, e) >= e
    }
}

fn octile(a: P, b: P) -> f64 {
    let (dx, dy) = ((a.0 - b.0).abs() as f64, (a.1 - b.1).abs() as f64);
    let (hi, lo) = if dx > dy { (dx, dy) } else { (dy, dx) };
    (hi - lo) + lo * SQRT2
}

fn near_poly(p: P, poly: &[V]) -> P {
    let c: V = p.into();
    if in_poly(c, poly) {
        return p;
    }
    let mut best = (f64::INFINITY, c);
    let n = poly.len();
    for i in 0..n {
        let (a, b) = (poly[i], poly[(i + 1) % n]);
        let ab = sub(b, a);
        let l2 = dot(ab, ab).max(1.0);
        let t = (dot(sub(c, a), ab) / l2).clamp(0.0, 1.0);
        let q = V(a.0 + ab.0 * t, a.1 + ab.1 * t);
        let d = hypot(sub(c, q));
        if d < best.0 {
            best = (d, q);
        }
    }
    to_p(best.1)
}

struct Node {
    p: P,
    layer: u8,
    dir: u8,
    vias: u8,
    parent: u32,
    g: f64,
    /// Not yet checked against copper. Moves are validated only when the search picks them
    /// (lazy A*), which is most of the speed: most candidate moves are never looked at.
    pending: Pending,
}

#[derive(Clone, Copy, PartialEq)]
enum Pending {
    None,
    Move { from: P },
    Via,
}

thread_local! {
    /// Whether the last failed search stopped on its budget rather than exhausting its window:
    /// the difference between "ran out" and "walled in" when a task goes to the designer.
    pub static RAN_OUT: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}

#[inline]
fn soft_ignores(q: &Query, o: &Obs) -> bool {
    match (q.soft, o.owner) {
        (Some(f), Owner::Conn(c)) => f(c).is_finite(),
        _ => false,
    }
}

/// Build the guide lines for a search window.
pub fn build_lines(w: &World, q: &Query, window: (f64, f64, f64, f64)) -> Lines {
    build_lines_on(w, q, window, &w.route_layers)
}

/// The same, from the copper on the given layers only. A rail's bus layer is mostly empty: it has no
/// use for a line along every pad on the other side of the board, and each one multiplies the states.
pub fn build_lines_on(w: &World, q: &Query, window: (f64, f64, f64, f64), layers: &[usize]) -> Lines {
    let mut lines = Lines::default();
    let r = q.rules;
    let p = q.profile;
    let also = q.also.unwrap_or(NO_NET);
    let mut terminal = |t: &Terminal, lines: &mut Lines| match t {
        Terminal::Point { p, .. } => lines.add_point(*p),
        Terminal::Zone { poly, .. } => {
            let b = Shape::Poly { pts: poly.clone(), r: 0.0 }.bbox();
            lines.add_point(((b.0 + b.2) as i64 / 2, (b.1 + b.3) as i64 / 2));
        }
        Terminal::Track { a, b, .. } => {
            add_track_lines(lines, *a, *b);
            lines.add_point(*a);
            lines.add_point(*b);
        }
    };
    for t in q.sources.iter().chain(q.targets.iter()) {
        terminal(t, &mut lines);
    }
    let wide = p.width as f64 / 2.0;
    let neck = p.neck as f64 / 2.0;
    let tgt = p.target_gap as f64 + 1000.0;
    for &l in layers {
        w.layers[l].visit(window, |o| {
            let own = o.net == q.net || (also != NO_NET && o.net == also);
            // A soft search crosses movable copper, so it has no use for lines around it, and
            // those lines are most of the lattice on a dense board (see Router::soft_path).
            if soft_ignores(q, o) {
                return true;
            }
            if !own {
                let at_pad = if let Owner::Pad(i) = o.owner { Some(i) } else { None };
                let clr = r.clearance_at(q.net, o.net, at_pad);
                let c = clr as f64 + 1000.0;
                let via_r = r.via_for(q.net).0 as f64 / 2.0 + clr as f64 + 1000.0;
                // Hug at the neck's clearance; at the run's own width if that is meaningfully wider.
                lines.add_tangents(&o.shape, neck + c);
                if wide > neck + 40_000.0 {
                    lines.add_tangents(&o.shape, wide + c);
                }
                // The preferred spacing, along routed tracks only: that is what makes a bus.
                if tgt > c && matches!(o.owner, Owner::Conn(_) | Owner::Fixed) {
                    lines.add_tangents(&o.shape, wide + tgt);
                }
                if q.profile.max_vias > 0 && !matches!(o.owner, Owner::Keepout | Owner::Zone(_)) {
                    let (b, _) = (o.bb, 0);
                    lines.v.push(even_up(b.2 + via_r));
                    lines.v.push(even_down(b.0 - via_r));
                    lines.h.push(even_up(b.3 + via_r));
                    lines.h.push(even_down(b.1 - via_r));
                }
            }
            if let Owner::Pad(i) = o.owner {
                // Hug a pad's solder mask opening too, where it reaches past the clearance.
                let limit = w.mask.limit_of(i as usize);
                if !own && limit > r.clearance_for(q.net, o.net) as f64 {
                    lines.add_tangents(&o.shape, neck + limit + 1000.0);
                    // And a second set clear of the laying guard: the first serves runs along a
                    // straight side, this one a diagonal past a rounded corner (mask.rs `curved_near`).
                    if w.mask.guard() > 0.0 {
                        lines.add_tangents(&o.shape, neck + limit + w.mask.guard() + 1000.0);
                    }
                }
                let b = o.bb;
                let cx = ((b.0 + b.2) / 2.0) as i64;
                let cy = ((b.1 + b.3) / 2.0) as i64;
                // A neighbouring pin's own line: parallel runs at pin pitch (4.7).
                lines.v.push(cx & !1);
                lines.h.push(cy & !1);
            }
            true
        });
    }
    w.edge.visit(window, |o| {
        lines.add_tangents(&o.shape, wide + r.edge as f64 + 1000.0);
        true
    });
    w.holes.visit(window, |o| {
        if o.net != q.net && !matches!(o.shape, Shape::Poly { .. }) {
            let local = if let Owner::Pad(i) = o.owner { w.pad_clearance[i as usize] } else { 0.0 };
            lines.add_tangents(&o.shape, neck + local.max(r.hole_clearance() as f64) + 1000.0);
        }
        true
    });
    lines.finish();
    lines
}

/// The line a track lies on, so a search stops exactly where it crosses that track.
fn add_track_lines(lines: &mut Lines, a: P, b: P) {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    if dy == 0 {
        lines.h.push(a.1);
    } else if dx == 0 {
        lines.v.push(a.0);
    } else if dx == dy {
        lines.dp.push(a.0 - a.1);
    } else if dx == -dy {
        lines.dm.push(a.0 + a.1);
    }
}

/// Whether a route arriving at `p` on `layer` heading `dir` may end on this track. A square T only
/// off a wide rail, never parallel, and any via at the required distance from the track.
#[allow(clippy::too_many_arguments)]
fn track_accepts(t: &Terminal, p: P, layer: usize, dir: u8, last_via: Option<P>) -> bool {
    let Terminal::Track { a, b, layer: tl, wide, stand_off } = t else { return false };
    if *tl != layer || pt_seg(p.into(), (*a).into(), (*b).into()) > 2.0 {
        return false;
    }
    if let Some(v) = last_via {
        if pt_seg(v.into(), (*a).into(), (*b).into()) < *stand_off {
            return false;
        }
    }
    // Straight off a via onto the track: a via inside a trace (4.4), only as a marked last resort.
    if dir == NO_DIR {
        return *stand_off < 0.0;
    }
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let Some(axis) = DIRS.iter().position(|d| d.0 == dx.signum() && d.1 == dy.signum() && (dx.abs() == dy.abs() || dx == 0 || dy == 0)) else { return true };
    // Landing on the track's very end is a corner, not a junction: it must not fold back acutely.
    for (end, onward) in [(*a, axis as i32), (*b, axis as i32 + 4)] {
        if octile(p, end) <= 2.0 {
            let t = (onward - dir as i32).rem_euclid(8);
            if t.min(8 - t) > if *wide { 2 } else { 1 } {
                return false;
            }
        }
    }
    let turn = (axis as i32 - dir as i32).rem_euclid(4);
    let turn = turn.min(4 - turn);
    match turn {
        0 => false,
        1 => true,
        _ => *wide,
    }
}

/// A* over the lattice from any source to any target. Returns None when no legal path exists in
/// the window within the node budget.
pub fn search(w: &World, q: &Query) -> Option<Path> {
    RAN_OUT.with(|c| c.set(false));
    crate::clock::tick(crate::clock::SEARCH_START);
    let t0 = std::time::Instant::now();
    let mut nodes = 0usize;
    let found = search_inner(w, q, &mut nodes);
    {
        let mut g = w.guide.borrow_mut();
        g.searches += 1;
        if found.is_some() {
            g.nodes_ok += nodes as u64;
        } else {
            g.nodes_failed += nodes as u64;
            g.note_failed(q);
        }
    }
    if trace() {
        eprintln!("    search vias={} margin={:.1} w={:.2} gap={:.2} soft={} -> {} nodes={} {:.1} ms", q.profile.max_vias, q.profile.margin / NM, q.profile.width as f64 / NM, q.profile.target_gap as f64 / NM, q.soft.is_some(), found.is_some(), nodes, t0.elapsed().as_secs_f64() * 1000.0);
    }
    found
}

fn search_inner(w: &World, q: &Query, node_count: &mut usize) -> Option<Path> {
    let r = q.rules;
    let pf = q.profile;
    // Window: the bounding box of the terminals plus a margin.
    let (mut x0, mut y0, mut x1, mut y1) = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
    for t in q.sources.iter().chain(q.targets.iter()) {
        let b = match t {
            Terminal::Point { p, .. } => (p.0 as f64, p.1 as f64, p.0 as f64, p.1 as f64),
            Terminal::Zone { poly, .. } => Shape::Poly { pts: poly.clone(), r: 0.0 }.bbox(),
            Terminal::Track { a, b, .. } => ((a.0.min(b.0)) as f64, (a.1.min(b.1)) as f64, (a.0.max(b.0)) as f64, (a.1.max(b.1)) as f64),
        };
        x0 = x0.min(b.0);
        y0 = y0.min(b.1);
        x1 = x1.max(b.2);
        y1 = y1.max(b.3);
    }
    let mut window = (x0 - pf.margin, y0 - pf.margin, x1 + pf.margin, y1 + pf.margin);
    // A planned detour may leave the terminals' box: the first attempt can already follow it.
    if q.soft.is_none() {
        if let Some(cr) = w.guide.borrow().corridor_of(q) {
            let b = cr.bbox;
            window = (window.0.min(b.0), window.1.min(b.1), window.2.max(b.2), window.3.max(b.3));
        }
    }
    let table = w.guide.borrow_mut().prepare(w, q, window);
    let audit = audit_guide();
    let walled = table.is_some() && w.guide.borrow_mut().hopeless(w, q);
    if walled && !audit {
        return None;
    }
    let started = *w.guide.borrow_mut().start.get_or_insert_with(crate::clock::Instant::now);
    let hint = if q.soft.is_none() { w.guide.borrow().hint.as_ref().filter(|h| h.net == q.net).cloned() } else { None };
    let mut lines = build_lines(w, q, window);
    if let Some(h) = &hint {
        for (a, b, _) in &h.lanes {
            lines.add_point(to_p(*a));
            lines.add_point(to_p(*b));
        }
        lines.finish();
    }
    let bus_lines = pf.layer_bias.map(|l| build_lines_on(w, q, window, &[l]));
    let also = q.also.unwrap_or(NO_NET);
    // The targets' own lines: a route may turn onto one of these anywhere.
    let mut term = Lines::default();
    for t in q.targets {
        match t {
            Terminal::Point { p, .. } => term.add_point(*p),
            Terminal::Zone { poly, .. } => {
                let b = Shape::Poly { pts: poly.clone(), r: 0.0 }.bbox();
                term.add_point(((b.0 + b.2) as i64 / 2, (b.1 + b.3) as i64 / 2));
            }
            // A route turns toward a track where it meets a line through the track's ends: empty
            // bus layers have no copper to bend at otherwise.
            Terminal::Track { a, b, .. } => {
                term.add_point(*a);
                term.add_point(*b);
            }
        }
    }
    // A bus member may also turn onto its neighbour's shape anywhere.
    if let Some(h) = &hint {
        for (a, b, _) in &h.lanes {
            term.add_point(to_p(*a));
            term.add_point(to_p(*b));
        }
    }
    term.finish();
    // A shortest route only bends where it wraps something: next to copper, or onto a target's
    // line. Everywhere else it goes straight. This is what keeps the lattice small.
    let bend_reach = ((pf.width.max(pf.neck) as f64 / 2.0 + pf.target_gap.max(pf.clearance) as f64) * 1.2 + 40_000.0).max(r.via as f64 / 2.0 + r.clearance as f64 + 60_000.0);
    // The hugging lines lie at each neighbour's own class clearance, so the turn must be allowed out
    // there: at a USB class's 0.4 mm they lay outside this reach, every legal bend read as open
    // copper, and a net of a wide class had nowhere to turn (benchmark B's pair, "no room").
    let bend_half = pf.width.max(pf.neck) as f64 / 2.0;
    let bend_far = bend_reach.max(bend_half + r.max_clearance() as f64 * 1.2 + 40_000.0);
    let near_copper = |p: P, layer: usize| -> bool {
        let c: V = p.into();
        let bb = (c.0 - bend_far, c.1 - bend_far, c.0 + bend_far, c.1 + bend_far);
        let mut hit = false;
        w.layers[layer].visit(bb, |o| {
            if (o.net == q.net && q.net != NO_NET) || (also != NO_NET && o.net == also) || soft_ignores(q, o) {
                return true;
            }
            let reach = bend_reach.max(bend_half + r.clearance_for(q.net, o.net) as f64 * 1.2 + 40_000.0);
            if o.dist_within(c, c, reach * 1.01) <= reach {
                hit = true;
                return false;
            }
            true
        });
        if !hit {
            w.edge.visit(bb, |o| {
                if o.dist_within(c, c, bend_reach * 1.01) <= bend_reach {
                    hit = true;
                    return false;
                }
                true
            });
        }
        hit
    };

    // Target positions for the heuristic and the arrival test.
    let mut point_targets: HashSet<(P, usize)> = HashSet::new();
    let mut h_points: Vec<(P, Vec<usize>)> = Vec::new();
    let mut zone_targets: Vec<(usize, &Vec<V>)> = Vec::new();
    let mut track_targets: Vec<(P, P, usize)> = Vec::new();
    for t in q.targets {
        match t {
            Terminal::Point { p, layers } => {
                let s = snap(*p);
                for &l in layers {
                    point_targets.insert((s, l));
                }
                h_points.push((s, layers.clone()));
            }
            Terminal::Zone { layer, poly } => zone_targets.push((*layer, poly)),
            Terminal::Track { a, b, layer, .. } => track_targets.push((*a, *b, *layer)),
        }
    }
    // Remaining cost of covering `d` to a target that is on `on_layer(l)`. For a rail, staying off the
    // bus costs OFF_BUS per mm, so the bound has to know a via is usually the cheap way: without this
    // the search crawls the crowded stub layer for millimetres before it tries going down.
    let rest = |d: f64, layer: usize, on_layer: &dyn Fn(usize) -> bool| -> f64 {
        match pf.layer_bias {
            None => d + if on_layer(layer) { 0.0 } else { r.cost_via },
            Some(bus) => {
                let via_end = if on_layer(bus) { 0.0 } else { r.cost_via };
                if layer == bus {
                    d + via_end
                } else {
                    let down = r.cost_via + d + via_end;
                    if on_layer(layer) { down.min(OFF_BUS * d) } else { down }
                }
            }
        }
    };
    // A rail's targets are every piece of its copper, pours of hundreds of points included, and working
    // that out per state was most of a rail search's time on benchmark C. With many targets the estimate
    // is kept per 0.1 mm square, less the most it can change across a square, so it's still a bound.
    let many = h_points.len() + track_targets.len() + zone_targets.len() * 8 > 8;
    let near_cache: std::cell::RefCell<HashMap<(i64, i64, u8), f64, FxBuild>> = Default::default();
    const CACHE_CELL: i64 = 100_000;
    let target_bound = |p: P, layer: usize| -> f64 {
        let mut best = f64::INFINITY;
        for (t, ls) in &h_points {
            best = best.min(rest(octile(p, *t), layer, &|l| ls.contains(&l)));
        }
        for (l, poly) in &zone_targets {
            best = best.min(rest(octile(p, near_poly(p, poly)), layer, &|x| x == *l));
        }
        for (a, b, l) in &track_targets {
            // Straight-line distance never exceeds the octile path, so this stays a lower bound.
            best = best.min(rest(pt_seg(p.into(), (*a).into(), (*b).into()), layer, &|x| x == *l));
        }
        best
    };
    let h = |p: P, layer: usize| -> f64 {
        let mut best = if many {
            let key = (p.0.div_euclid(CACHE_CELL), p.1.div_euclid(CACHE_CELL), layer as u8);
            let mut cache = near_cache.borrow_mut();
            *cache.entry(key).or_insert_with(|| {
                let c = (key.0 * CACHE_CELL + CACHE_CELL / 2, key.1 * CACHE_CELL + CACHE_CELL / 2);
                // OFF_BUS can steepen the bound by its factor, so the square's slack is scaled by it.
                (target_bound(c, layer) - OFF_BUS.max(1.0) * SQRT2 * CACHE_CELL as f64).max(0.0)
            })
        } else {
            target_bound(p, layer)
        };
        // Raised to the coarse map's true way round obstacles. Infinity is the map's proof that this
        // place can't reach the target.
        if let Some(tb) = table {
            let g = w.guide.borrow_mut().cost(tb, w, r, p.into(), layer);
            if g.is_finite() {
                best = best.max(g);
            } else if !audit {
                return g;
            }
        }
        best
    };

    // The pair partner's tracks, if this net has one on the board (STACK_COST).
    let stack: Vec<(usize, V, V)> = w.partner.get(&q.net).and_then(|p| w.pair_segs.borrow().get(p).map(|v| v.iter().map(|(_, l, a, b)| (*l, *a, *b)).collect())).unwrap_or_default();
    let mut nodes: Vec<Node> = Vec::new();
    let mut best: HashMap<(P, u8, u8), f64, FxBuild> = HashMap::with_capacity_and_hasher(4096, FxBuild::default());
    let mut heap: BinaryHeap<Reverse<(i64, u32)>> = BinaryHeap::new();
    // A rail is pulled tight afterwards and its bus layer is mostly empty, so its search may run
    // greedier: the answer barely changes and the node count drops by an order of magnitude.
    let weight = if pf.layer_bias.is_some() { RAIL_WEIGHT } else { r.search_weight };
    let mut push = |nodes: &mut Vec<Node>, best: &mut HashMap<(P, u8, u8), f64, FxBuild>, heap: &mut BinaryHeap<Reverse<(i64, u32)>>, n: Node| {
        let key = (n.p, n.layer, n.dir);
        let est = h(n.p, n.layer as usize);
        if est.is_infinite() {
            return;
        }
        if let Some(&g) = best.get(&key) {
            if g <= n.g {
                return;
            }
        }
        best.insert(key, n.g);
        let f = n.g + weight * est;
        nodes.push(n);
        heap.push(Reverse((f as i64, (nodes.len() - 1) as u32)));
    };
    for s in q.sources {
        match s {
            Terminal::Point { p, layers } => {
                for &l in layers {
                    if w.route_layers.contains(&l) {
                        push(&mut nodes, &mut best, &mut heap, Node { p: snap(*p), layer: l as u8, dir: NO_DIR, vias: 0, parent: u32::MAX, g: 0.0, pending: Pending::None });
                    }
                }
            }
            Terminal::Zone { layer, poly } => {
                let b = Shape::Poly { pts: poly.to_vec(), r: 0.0 }.bbox();
                let c = snap(((b.0 + b.2) as i64 / 2, (b.1 + b.3) as i64 / 2));
                if w.route_layers.contains(layer) {
                    push(&mut nodes, &mut best, &mut heap, Node { p: c, layer: *layer as u8, dir: NO_DIR, vias: 0, parent: u32::MAX, g: 0.0, pending: Pending::None });
                }
            }
            // Routes leave a pad or a fill; a track is only ever something to join.
            Terminal::Track { .. } => {}
        }
    }

    // Every source closed off on the coarse map: a proof that no route exists in this window.
    if table.is_some() && heap.is_empty() {
        w.guide.borrow_mut().closed_early += 1;
        return None;
    }

    let source_points: Vec<P> = q.sources.iter().filter_map(|s| if let Terminal::Point { p, .. } = s { Some(snap(*p)) } else { None }).collect();
    let target_points: Vec<P> = h_points.iter().map(|x| x.0).collect();
    // How far from a terminal a track may run at its neck. A wide rail's body can't come as close to
    // a small pad as a signal's can: it necks from where its own edge would meet the pad's neighbours.
    let rated = w.rail_nets.contains(&q.net) && pf.width > pf.neck;
    let neck_reach = if rated { (pf.width as f64 / 2.0 + pf.clearance as f64 + 0.3 * NM).max(0.4 * NM) } else { 0.4 * NM };
    let near_term = |x: P| source_points.iter().chain(target_points.iter()).any(|&s| octile(x, s) <= neck_reach);
    let mut expanded = 0usize;
    while let Some(Reverse((_, id))) = heap.pop() {
        let (p, layer, dir, vias, g, pending) = {
            let n = &nodes[id as usize];
            (n.p, n.layer as usize, n.dir, n.vias, n.g, n.pending)
        };
        let key = (p, layer as u8, dir);
        if best.get(&key).map(|&b| g > b).unwrap_or(false) {
            continue;
        }
        // Lazy check: is the move that reached this state legal, and what does it really cost?
        match pending {
            Pending::Move { from } => {
                expanded += 1;
                crate::clock::tick(1);
                *node_count = expanded;
                // The whole-run limit holds inside a long search too (4.6).
                if expanded & 4095 == 0 && started.elapsed().as_secs_f64() > r.time_limit {
                    // Cut short, not closed: nothing was proved about the way.
                    RAN_OUT.with(|c| c.set(true));
                    return None;
                }
                if expanded > pf_limit(q) {
                    RAN_OUT.with(|c| c.set(true));
                    return None;
                }
                if expanded % 1024 == 0 && r.deadline.map(|d| crate::clock::Instant::now() > d).unwrap_or(false) {
                    RAN_OUT.with(|c| c.set(true));
                    return None;
                }
                let (a, b): (V, V) = (from.into(), p.into());
                // On its bus layer a rail keeps its width under a fine-pitch part: the escape is on
                // the other side. Off the bus layer it is a stub.
                let on_bus = pf.layer_bias == Some(layer);
                let in_esc = if pf.layer_bias.is_some() && !rated { !on_bus } else { (w.in_escape(a) && w.in_escape(b)) || near_term(from) || near_term(p) };
                let half = if in_esc { pf.neck } else { pf.width } as f64 / 2.0;
                let hard = half + pf.clearance as f64 - DRC_TOL;
                let soft_reach = half + pf.target_gap as f64;
                let reach = hard.max(soft_reach);
                let is_free = q.free.iter().any(|(c, rad)| octile(from, *c) <= *rad && octile(p, *c) <= *rad);
                let mut blockers = Vec::new();
                let mut soft_cost = 0.0;
                let gap = if is_free { f64::INFINITY } else { w.gap(r, pf.clearance, layer, a, b, q.net, also, reach, hard, q.soft, &mut blockers, &mut soft_cost) };
                if gap < hard {
                    best.remove(&key);
                    continue;
                }
                let e = half + r.edge as f64;
                if !is_free && (w.edge_gap(a, b, e) < e || w.mask.seg_hit_also(q.net, also, layer, a, b, half).is_some() || !w.holes_clear_also(r, a, b, half, q.net, also)) {
                    best.remove(&key);
                    continue;
                }
                let len = hypot(sub(a, b));
                // A crossing costs its price once however finely the lattice cuts it: the band of a
                // track and its clearance is about 0.5 mm wide, and lattice steps are far smaller.
                let mut extra = soft_cost * (len / (0.5 * NM)).min(1.0);
                if !in_esc && gap < soft_reach {
                    extra += len * r.cost_tight * (1.0 - (gap - hard) / (soft_reach - hard).max(1.0));
                }
                // His J1: CC2 stays on B.Cu past the VBUS pour's edge, then hops to F.Cu.
                if let Some(polys) = w.pour_avoid.get(&q.net) {
                    let m = V((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0);
                    if polys.iter().any(|(l, p)| *l == layer && in_poly(m, p)) {
                        extra += len * POUR_AVOID_COST;
                    }
                }
                if let Some(hist) = q.history {
                    let m = V((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0);
                    extra += hist.at(m) as f64 * len * 0.5;
                }
                if w.relief_reach > 0.0 {
                    let reach = w.relief_reach + half;
                    let bb = (a.0.min(b.0) - reach, a.1.min(b.1) - reach, a.0.max(b.0) + reach, a.1.max(b.1) + reach);
                    let mut hit = false;
                    w.relief[layer].visit(bb, |o| {
                        if o.net != q.net {
                            if let Owner::Pad(i) = o.owner {
                                if o.shape.dist_seg(a, b) - half < w.relief_gap[i as usize] {
                                    hit = true;
                                    return false;
                                }
                            }
                        }
                        true
                    });
                    if hit {
                        extra += len * RELIEF_COST;
                    }
                }
                if !stack.is_empty() {
                    let m = V((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0);
                    if stack.iter().any(|(l, s0, s1)| *l != layer && pt_seg(m, *s0, *s1) < STACK_BAND) {
                        extra += len * STACK_COST;
                    }
                }
                if let Some((fl, segs, pitch)) = w.follow.borrow().as_ref() {
                    if *fl == layer && !segs.is_empty() {
                        let m = V((a.0 + b.0) / 2.0, (a.1 + b.1) / 2.0);
                        let d = segs.iter().map(|(s0, s1)| pt_seg(m, *s0, *s1)).fold(f64::INFINITY, f64::min);
                        extra += len * FOLLOW_COST * ((d - pitch) / pitch).clamp(0.0, 1.0);
                    }
                }
                nodes[id as usize].pending = Pending::None;
                if extra > 0.0 {
                    let ng = g + extra;
                    nodes[id as usize].g = ng;
                    best.insert(key, ng);
                    let f = ng + weight * h(p, layer);
                    heap.push(Reverse((f as i64, id)));
                    continue;
                }
            }
            Pending::Via => {
                expanded += 1;
                crate::clock::tick(1);
                // Two vias of one path are holes too (2.2), and neither is on the board yet to see.
                let mut up = nodes[id as usize].parent;
                let min_hole = r.drill as f64 + r.hole_hole as f64;
                let mut close = false;
                while up != u32::MAX && nodes[id as usize].vias > 1 {
                    let n = &nodes[up as usize];
                    if n.pending == Pending::None && n.dir == NO_DIR && n.parent != u32::MAX && n.p != p && hypot(sub(n.p.into(), p.into())) < min_hole {
                        close = true;
                        break;
                    }
                    up = n.parent;
                }
                if close {
                    best.remove(&key);
                    continue;
                }
                let mut blockers = Vec::new();
                let mut soft_cost = 0.0;
                if !w.via_ok(p, q, q.soft, &mut blockers, &mut soft_cost) {
                    best.remove(&key);
                    continue;
                }
                nodes[id as usize].pending = Pending::None;
                if soft_cost > 0.0 {
                    let ng = g + soft_cost;
                    nodes[id as usize].g = ng;
                    best.insert(key, ng);
                    let f = ng + weight * h(p, layer);
                    heap.push(Reverse((f as i64, id)));
                    continue;
                }
            }
            Pending::None => {}
        }
        let mut arrived = point_targets.contains(&(p, layer)) || zone_targets.iter().any(|(l, poly)| *l == layer && in_poly(p.into(), poly));
        if !arrived && !track_targets.is_empty() {
            let last_via = last_via_of(&nodes, id);
            arrived = q.targets.iter().any(|t| track_accepts(t, p, layer, dir, last_via));
        }
        let arrive_ok = match (q.arrive, dir) {
            (Some(next), d) if d != NO_DIR => ((next as i32 - d as i32).rem_euclid(8)).min((d as i32 - next as i32).rem_euclid(8)) <= 1,
            _ => true,
        };
        if arrived && arrive_ok {
            if let (true, Some(tb)) = (audit, table) {
                audit_path(&nodes, id, w, q, tb, walled);
            }
            return Some(rebuild(&nodes, id, q, w, expanded));
        }

        // Straight on and 45-degree turns; 90 degrees only at a price (chamfered afterwards).
        // Asked at most once per node, and only if a turn is on a line: near_copper took about 10%.
        let mut may_bend = if dir == NO_DIR { Some(true) } else { None };
        let lines = match (&bus_lines, pf.layer_bias) {
            (Some(b), Some(l)) if l == layer => b,
            _ => &lines,
        };
        for d in 0..8u8 {
            let turn = if dir == NO_DIR { 0 } else { ((d as i32 - dir as i32).rem_euclid(8)).min((dir as i32 - d as i32).rem_euclid(8)) };
            if turn >= 3 {
                continue;
            }
            // Straight off a via onto a bus layer's sparser lines, from wherever the via stands.
            if dir != NO_DIR && !lines.on_family(p, d) {
                continue;
            }
            if dir == NO_DIR && pf.layer_bias.is_none() && !lines.on_family(p, d) {
                continue;
            }
            if turn != 0 && !term.on_family(p, d) && !*may_bend.get_or_insert_with(|| near_copper(p, layer)) {
                continue;
            }
            let Some(mut t) = lines.next_stop(p, d) else { continue };
            let (dx, dy) = DIRS[d as usize];
            let mut np = (p.0 + dx * t, p.1 + dy * t);
            // In open copper a stop can only go straight on, so skip it: on a dense board's lattice
            // a straight run across an empty layer otherwise stops thousands of times per mm, each
            // a node and a clearance check, and floods the budget (piprobe_v13: 362k states on
            // an almost empty B.Cu, then "no path" 10 mm short). Stops where a bend or an arrival
            // is possible are all kept, so no route shape is lost.
            let open_stop = |x: P| !near_copper(x, layer) && !(0..8u8).any(|k| k != d && term.on_family(x, k)) && !point_targets.contains(&(x, layer)) && zone_targets.is_empty();
            let mut hops = 0;
            while hops < 512 && open_stop(np) {
                let Some(more) = lines.next_stop(np, d) else { break };
                let further = (np.0 + dx * more, np.1 + dy * more);
                if (further.0 as f64) < window.0 || (further.0 as f64) > window.2 || (further.1 as f64) < window.1 || (further.1 as f64) > window.3 {
                    break;
                }
                t += more;
                np = further;
                hops += 1;
            }
            if (np.0 as f64) < window.0 || (np.0 as f64) > window.2 || (np.1 as f64) < window.1 || (np.1 as f64) > window.3 {
                continue;
            }
            let len = t as f64 * if dx != 0 && dy != 0 { SQRT2 } else { 1.0 };
            let per_mm = match pf.layer_bias {
                Some(l) if l == layer => 1.0,
                Some(_) => OFF_BUS,
                None if layer == 0 => 1.0,
                None => r.cost_bottom,
            };
            let mut cost = len * per_mm;
            if let Some(h) = &hint {
                cost += len * h.extra(p.into(), np.into(), layer);
            }
            cost += match turn {
                0 => 0.0,
                1 => r.cost_bend45,
                _ => r.cost_bend90,
            };
            push(&mut nodes, &mut best, &mut heap, Node { p: np, layer: layer as u8, dir: d, vias, parent: id, g: g + cost, pending: Pending::Move { from: p } });
        }

        // Change layer, in rounds by via count.
        // Most via candidates fail (9 in 10 on the benchmark boards), so the map's proof that none
        // can stand in this cell saves each one a trip through the heap and a full check.
        if (vias as u32) < pf.max_vias && (audit || table.map_or(true, |tb| w.guide.borrow_mut().via_possible(tb, w, r, p.into()))) {
            for &l in &w.route_layers {
                if l != layer {
                    push(&mut nodes, &mut best, &mut heap, Node { p, layer: l as u8, dir: NO_DIR, vias: vias + 1, parent: id, g: g + r.cost_via, pending: Pending::Via });
                }
            }
        }
    }
    None
}

fn trace() -> bool {
    static V: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
    *V.get_or_init(|| std::env::var_os("ADOM_ROUTE_TRACE").is_some())
}

/// Audit mode: the coarse map's proofs aren't acted on, and any finished route through a place the
/// map called closed is reported. This is how the map's optimism is measured.
fn audit_guide() -> bool {
    static V: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
    *V.get_or_init(|| std::env::var_os("ADOM_ROUTE_AUDIT_GUIDE").is_some())
}

fn audit_path(nodes: &[Node], mut id: u32, w: &World, q: &Query, table: usize, walled: bool) {
    if walled {
        eprintln!("GUIDE VIOLATION net {}: routed although a terminal was called walled in", q.net);
    }
    loop {
        let n = &nodes[id as usize];
        let g = w.guide.borrow_mut().cost(table, w, q.rules, n.p.into(), n.layer as usize);
        if g.is_infinite() {
            eprintln!("GUIDE VIOLATION net {} vias {} at ({:.3},{:.3}) layer {}", q.net, q.profile.max_vias, n.p.0 as f64 / NM, n.p.1 as f64 / NM, n.layer);
        }
        if n.parent != u32::MAX && nodes[n.parent as usize].layer != n.layer && !w.guide.borrow_mut().via_possible(table, w, q.rules, n.p.into()) {
            eprintln!("GUIDE VIOLATION net {}: via at ({:.3},{:.3}) in a cell the map called closed", q.net, n.p.0 as f64 / NM, n.p.1 as f64 / NM);
        }
        if n.parent == u32::MAX {
            break;
        }
        id = n.parent;
    }
}

/// Where this node's copper last came through a via, if it did on the way here.
fn last_via_of(nodes: &[Node], mut id: u32) -> Option<P> {
    loop {
        let n = &nodes[id as usize];
        if n.parent == u32::MAX {
            return None;
        }
        let parent = &nodes[n.parent as usize];
        if parent.layer != n.layer {
            return Some(n.p);
        }
        id = n.parent;
    }
}

fn pf_limit(q: &Query) -> usize {
    // Small windows get a small budget; the wide last-resort searches get the full one.
    let m = q.profile.margin;
    // A soft search that finds its way does so early: the longest that succeeded across the three
    // benchmark boards took 182k nodes, while every wider one spent its full budget and failed.
    if q.soft.is_some() {
        return q.rules.node_limit / 4;
    }
    if m < 2.0 * NM { q.rules.node_limit / 16 } else if m < 6.0 * NM { q.rules.node_limit / 4 } else { q.rules.node_limit }
}

fn rebuild(nodes: &[Node], mut id: u32, q: &Query, w: &World, expanded: usize) -> Path {
    let mut pts = Vec::new();
    let cost = nodes[id as usize].g;
    let vias = nodes[id as usize].vias as u32;
    loop {
        let n = &nodes[id as usize];
        pts.push((n.p, n.layer as usize));
        if n.parent == u32::MAX {
            break;
        }
        id = n.parent;
    }
    pts.reverse();
    let mut blockers = Vec::new();
    if let Some(f) = q.soft {
        // Find exactly who the finished path crosses.
        let half = q.profile.neck as f64 / 2.0 + q.profile.clearance as f64;
        let also = q.also.unwrap_or(NO_NET);
        for s in pts.windows(2) {
            let ((a, la), (b, lb)) = (s[0], s[1]);
            let (va, vb): (V, V) = (a.into(), b.into());
            if la == lb {
                let mut c = 0.0;
                w.gap(q.rules, q.profile.clearance, la, va, vb, q.net, also, half, half, Some(f), &mut blockers, &mut c);
            } else {
                let need = q.rules.via_for(q.net).0 as f64 / 2.0 + q.profile.clearance as f64;
                for l in 0..w.layers.len() {
                    let mut c = 0.0;
                    w.gap(q.rules, q.profile.clearance, l, va, va, q.net, also, need, need, Some(f), &mut blockers, &mut c);
                }
            }
        }
    }
    Path { pts, vias, cost, blockers, nodes: expanded }
}

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

    fn rail(wide: bool, stand_off: f64) -> Terminal {
        Terminal::Track { a: (0, 0), b: (1_000_000, 0), layer: 3, wide, stand_off }
    }

    #[test]
    fn a_tap_joins_a_wide_rail_at_45_or_90_and_a_thin_one_only_as_a_y() {
        let mid = (500_000, 0);
        assert!(track_accepts(&rail(true, 0.0), mid, 3, 2, None));
        assert!(track_accepts(&rail(true, 0.0), mid, 3, 1, None));
        assert!(!track_accepts(&rail(false, 0.0), mid, 3, 2, None));
        assert!(track_accepts(&rail(false, 0.0), mid, 3, 1, None));
        // Never along the rail, never on the wrong layer.
        assert!(!track_accepts(&rail(true, 0.0), mid, 3, 0, None));
        assert!(!track_accepts(&rail(true, 0.0), mid, 0, 2, None));
    }

    #[test]
    fn a_tap_keeps_its_via_off_the_rail_and_never_folds_back_at_its_end() {
        let mid = (500_000, 0);
        // A via on the rail, or one too close to it, is refused while a stand-off is asked for (4.4).
        assert!(!track_accepts(&rail(true, 600_000.0), mid, 3, NO_DIR, Some(mid)));
        assert!(!track_accepts(&rail(true, 600_000.0), mid, 3, 2, Some((500_000, -300_000))));
        assert!(track_accepts(&rail(true, 600_000.0), mid, 3, 2, Some((500_000, -700_000))));
        // Arriving heading -x at the rail's start would turn back along +x: an acute corner.
        assert!(!track_accepts(&rail(true, 0.0), (0, 0), 3, 3, None));
        assert!(track_accepts(&rail(true, 0.0), (0, 0), 3, 1, None));
    }
}