AI Flow: Routing

//! The coarse view of the board: what a detailed search can't see from where it stands.
//!
//! Two jobs share one map. First, a backward search from the target over coarse cells on each
//! routing layer, with vias as edges (VTR's router lookahead, Navit's search from the destination),
//! resumed only as far as the detailed search asks (reverse resumable A*). That gives the detailed
//! A* the true way round obstacles, and a quick "no path" when the map is closed. Second, the global
//! stage further down, which uses the same boundaries as capacities.
//!
//! The map must stay optimistic: "closed" is only ever a proof. A boundary between two cells is cut
//! into short samples; a sample is closed only when one obstacle is closer to its middle than the
//! narrowest legal centreline allows, by more than half the sample's length, so no point of that
//! sample could carry a legal track. A fine-pitch lane therefore can't be closed by rounding: The designer's
//! rule that a router's "no path" at fine pitch is not evidence (Troubleshooting, "Routing practices")
//! is why the map has no slop. Copper of the query's own net never closes anything.

use crate::board::*;
use crate::geom::*;
use crate::index::*;
use crate::rules::Rules;
use crate::search::{Query, Terminal, World};
use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// A sample closed by copper of more than one net, or by something with no net.
const MANY: u16 = u16::MAX;
/// Samples per boundary. Must fit the u16 masks.
const K: usize = 5;
const FULL: u16 = (1u16 << K) - 1;
/// A track's keep-out at the neck is about 0.6 mm across, or 0.85 mm along an axis at 45 degrees,
/// so at this size no boundary line can slip through a wall of tracks at any angle.
const CELL: f64 = 0.25 * NM;
const VIA_SUB: usize = 2;
/// How much dearer the estimate makes a step off the planned corridor. Swept 0.3 and 1.0: the same
/// completion on all three boards within one connection, fewer bends at 0.3 (piprobe_v13 66 to 72).
const CORRIDOR_BIAS: f32 = 0.3;
/// What the coarse estimate charges a soft search per crossing of committed copper (the router's
/// cheapest price for taking a route's place).
const SOFT_CROSSING: f64 = 2.0 * NM;

#[inline]
fn net16(n: NetId) -> u16 {
    if n == NO_NET { MANY } else { n.min(MANY as u32 - 1) as u16 }
}

pub struct Coarse {
    pub x0: f64,
    pub y0: f64,
    pub cell: f64,
    s: f64,
    pub w: usize,
    pub h: usize,
    /// World layer of each coarse layer, and back.
    pub route: Vec<usize>,
    index: Vec<usize>,
    /// Narrowest legal centreline's distance to copper, and to the board edge.
    need: f64,
    need_edge: f64,
    /// Closed samples per boundary, as a bit mask: copper that stays, and committed routes.
    mask_s: Vec<u16>,
    mask_d: Vec<u16>,
    /// Who closes each sample: 0 nobody, otherwise one net, or MANY.
    blk_s: Vec<u16>,
    blk_d: Vec<u16>,
    /// Bumped when committed copper changes, and when anything else does.
    pub rev_d: u64,
    pub rev_s: u64,
}

impl Coarse {
    pub fn build(w: &World, r: &Rules) -> Coarse {
        let mut bb = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
        let mut grow = |b: (f64, f64, f64, f64)| {
            bb = (bb.0.min(b.0), bb.1.min(b.1), bb.2.max(b.2), bb.3.max(b.3));
        };
        for o in w.edge.iter() {
            grow(o.bb);
        }
        for g in &w.layers {
            for o in g.iter() {
                if matches!(o.owner, Owner::Pad(_)) {
                    grow(o.bb);
                }
            }
        }
        let cell = CELL;
        let s = cell / K as f64;
        let x0 = bb.0 - 2.0 * cell;
        let y0 = bb.1 - 2.0 * cell;
        let cw = ((bb.2 - bb.0) / cell).ceil() as usize + 4;
        let ch = ((bb.3 - bb.1) / cell).ceil() as usize + 4;
        let route = w.route_layers.clone();
        let mut index = vec![usize::MAX; w.layers.len()];
        for (i, &l) in route.iter().enumerate() {
            index[l] = i;
        }
        let n = route.len() * 2 * cw * ch;
        let mut c = Coarse {
            x0,
            y0,
            cell,
            s,
            w: cw,
            h: ch,
            route,
            index,
            need: r.neck as f64 / 2.0 + r.clearance as f64,
            need_edge: r.neck as f64 / 2.0 + r.edge as f64,
            mask_s: vec![0; n],
            mask_d: vec![0; n],
            blk_s: vec![0; n * K],
            blk_d: vec![0; n * K],
            rev_d: 1,
            rev_s: 1,
        };
        for l in 0..c.route.len() {
            let g = &w.layers[c.route[l]];
            g.drain_log();
            for o in g.iter() {
                // "Closed" is a proof, and a pour some nets may cross proves nothing about them.
                if let Owner::Zone(z) = o.owner {
                    if w.pour_open.get(z as usize).map(|v| !v.is_empty()).unwrap_or(false) {
                        continue;
                    }
                }
                c.mark(l, &o.shape, o.net, o.owner, c.need);
            }
            for o in w.edge.iter() {
                c.mark(l, &o.shape, NO_NET, Owner::Edge, c.need_edge);
            }
        }
        c
    }

    /// Bring the map up to date with what was committed and ripped since last time.
    pub fn sync(&mut self, w: &World) {
        for l in 0..self.route.len() {
            let log = w.layers[self.route[l]].drain_log();
            for (added, o) in log {
                if added {
                    self.mark(l, &o.shape, o.net, o.owner, self.need);
                } else {
                    self.unmark(w, l, &o.shape);
                }
                if matches!(o.owner, Owner::Conn(_)) {
                    self.rev_d += 1;
                } else {
                    self.rev_s += 1;
                    self.rev_d += 1;
                }
            }
        }
    }

    #[inline]
    fn boundary(&self, l: usize, d: usize, i: usize, j: usize) -> usize {
        ((l * 2 + d) * self.h + j) * self.w + i
    }

    /// Visit the samples any obstacle piece could close. `d` 0: the boundary from (i,j) to
    /// (i+1,j); 1: from (i,j) to (i,j+1).
    fn near_samples(&self, bb: (f64, f64, f64, f64), mut f: impl FnMut(usize, usize, usize, usize, V)) {
        let (w, h, cell, s, x0, y0) = (self.w as i64, self.h as i64, self.cell, self.s, self.x0, self.y0);
        let lo = |v: f64, o: f64, st: f64| ((v - o) / st).ceil() as i64;
        let hi = |v: f64, o: f64, st: f64| ((v - o) / st).floor() as i64;
        let k = K as i64;
        // Vertical boundary lines x = x0 + (i+1) cell, samples along y.
        for line in lo(bb.0, x0, cell)..=hi(bb.2, x0, cell) {
            let i = line - 1;
            if i < 0 || i >= w {
                continue;
            }
            for n in (hi(bb.1, y0, s)).max(0)..=(hi(bb.3, y0, s)).min(h * k - 1) {
                let m = V(x0 + line as f64 * cell, y0 + (n as f64 + 0.5) * s);
                f(0, i as usize, (n / k) as usize, (n % k) as usize, m);
            }
        }
        for line in lo(bb.1, y0, cell)..=hi(bb.3, y0, cell) {
            let j = line - 1;
            if j < 0 || j >= h {
                continue;
            }
            for n in (hi(bb.0, x0, s)).max(0)..=(hi(bb.2, x0, s)).min(w * k - 1) {
                let m = V(x0 + (n as f64 + 0.5) * s, y0 + line as f64 * cell);
                f(1, (n / k) as usize, j as usize, (n % k) as usize, m);
            }
        }
    }

    /// Long diagonal tracks have huge boxes, so a capsule is walked in short pieces.
    fn pieces(&self, shape: &Shape, reach: f64) -> Vec<(f64, f64, f64, f64)> {
        if let Shape::Capsule { a, b, r } = shape {
            let len = hypot(sub(*a, *b));
            let n = (len / (2.0 * self.cell)).ceil().max(1.0) as usize;
            let rr = r + reach;
            return (0..n)
                .map(|i| {
                    let (t0, t1) = (i as f64 / n as f64, (i + 1) as f64 / n as f64);
                    let p = V(a.0 + (b.0 - a.0) * t0, a.1 + (b.1 - a.1) * t0);
                    let q = V(a.0 + (b.0 - a.0) * t1, a.1 + (b.1 - a.1) * t1);
                    (p.0.min(q.0) - rr, p.1.min(q.1) - rr, p.0.max(q.0) + rr, p.1.max(q.1) + rr)
                })
                .collect();
        }
        let b = shape.bbox();
        vec![(b.0 - reach, b.1 - reach, b.2 + reach, b.3 + reach)]
    }

    fn mark(&mut self, l: usize, shape: &Shape, net: NetId, owner: Owner, need: f64) {
        let half = self.s / 2.0;
        let who = net16(net);
        let dynamic = matches!(owner, Owner::Conn(_));
        let mut hits: Vec<(usize, usize)> = Vec::new();
        if let Shape::Poly { pts, r } = shape {
            // A pour can have thousands of points, and testing every sample in its box against all
            // of them took 10 s on benchmark B. Its inside comes from scanlines, its rim from its
            // edges as thin capsules.
            self.poly_inside(l, pts, &mut hits);
            let n = pts.len();
            for i in 0..n {
                let seg = Shape::Capsule { a: pts[i], b: pts[(i + 1) % n], r: *r };
                for bb in self.pieces(&seg, need) {
                    self.near_samples(bb, |d, a, b, bit, m| {
                        if seg.dist_pt(m) + half < need {
                            hits.push((self.boundary(l, d, a, b), bit));
                        }
                    });
                }
            }
        } else {
            for bb in self.pieces(shape, need) {
                self.near_samples(bb, |d, i, j, bit, m| {
                    if shape.dist_pt(m) + half < need {
                        hits.push((self.boundary(l, d, i, j), bit));
                    }
                });
            }
        }
        for (b, bit) in hits {
            let (blk, mask) = if dynamic { (&mut self.blk_d, &mut self.mask_d) } else { (&mut self.blk_s, &mut self.mask_s) };
            let v = &mut blk[b * K + bit];
            *v = if *v == 0 || *v == who { who } else { MANY };
            mask[b] |= 1 << bit;
        }
    }

    /// Samples strictly inside a polygon, boundary line by boundary line.
    fn poly_inside(&self, l: usize, pts: &[V], hits: &mut Vec<(usize, usize)>) {
        let n = pts.len();
        let k = K as i64;
        let mut xs: Vec<f64> = Vec::new();
        let mut bb = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
        for p in pts {
            bb = (bb.0.min(p.0), bb.1.min(p.1), bb.2.max(p.0), bb.3.max(p.1));
        }
        // d 0: lines of constant x, walking y; d 1: the other way round.
        for d in 0..2usize {
            let (lo, hi, o, t_o, t_n, l_n) = if d == 0 { (bb.0, bb.2, self.x0, self.y0, self.h as i64, self.w as i64) } else { (bb.1, bb.3, self.y0, self.x0, self.w as i64, self.h as i64) };
            let first = ((lo - o) / self.cell).ceil() as i64;
            let last = ((hi - o) / self.cell).floor() as i64;
            for line in first..=last {
                let idx = line - 1;
                if idx < 0 || idx >= l_n {
                    continue;
                }
                let at = o + line as f64 * self.cell;
                xs.clear();
                for i in 0..n {
                    let (a, b) = (pts[i], pts[(i + 1) % n]);
                    let (ax, ay, bx, by) = if d == 0 { (a.0, a.1, b.0, b.1) } else { (a.1, a.0, b.1, b.0) };
                    if (ax > at) != (bx > at) {
                        xs.push(ay + (at - ax) / (bx - ax) * (by - ay));
                    }
                }
                xs.sort_by(f64::total_cmp);
                for w in xs.chunks_exact(2) {
                    let from = (((w[0] - t_o) / self.s).ceil() as i64).max(0);
                    let to = (((w[1] - t_o) / self.s).floor() as i64 - 1).min(t_n * k - 1);
                    for m in from..=to {
                        let (a, b) = if d == 0 { (idx as usize, (m / k) as usize) } else { ((m / k) as usize, idx as usize) };
                        hits.push((self.boundary(l, d, a, b), (m % k) as usize));
                    }
                }
            }
        }
    }

    /// Something went away: work out again who closes each sample it could have closed.
    fn unmark(&mut self, w: &World, l: usize, shape: &Shape) {
        let (half, need) = (self.s / 2.0, self.need);
        let mut todo: Vec<(usize, usize, V)> = Vec::new();
        for bb in self.pieces(shape, need) {
            self.near_samples(bb, |d, i, j, bit, m| {
                if shape.dist_pt(m) + half < need {
                    todo.push((self.boundary(l, d, i, j), bit, m));
                }
            });
        }
        let g = &w.layers[self.route[l]];
        for (b, bit, m) in todo {
            let (mut sv, mut dv) = (0u16, 0u16);
            let box_ = (m.0 - need, m.1 - need, m.0 + need, m.1 + need);
            g.visit(box_, |o| {
                if o.shape.dist_pt(m) + half < need {
                    let who = net16(o.net);
                    let v = if matches!(o.owner, Owner::Conn(_)) { &mut dv } else { &mut sv };
                    *v = if *v == 0 || *v == who { who } else { MANY };
                }
                true
            });
            let e = self.need_edge;
            w.edge.visit((m.0 - e, m.1 - e, m.0 + e, m.1 + e), |o| {
                if o.shape.dist_pt(m) + half < e {
                    sv = MANY;
                }
                true
            });
            self.blk_s[b * K + bit] = sv;
            self.blk_d[b * K + bit] = dv;
            let set = |mask: &mut u16, on: bool| {
                if on { *mask |= 1 << bit } else { *mask &= !(1 << bit) }
            };
            set(&mut self.mask_s[b], sv != 0);
            set(&mut self.mask_d[b], dv != 0);
        }
    }

    /// Can a centreline of this net cross this boundary at all?
    #[inline]
    pub fn open(&self, b: usize, who: u16, soft: bool) -> bool {
        let m = if soft { self.mask_s[b] } else { self.mask_s[b] | self.mask_d[b] };
        if m != FULL {
            return true;
        }
        for i in 0..K {
            let (s, d) = (self.blk_s[b * K + i], self.blk_d[b * K + i]);
            if (s == 0 || s == who) && (soft || d == 0 || d == who) {
                return true;
            }
        }
        false
    }

    #[inline]
    pub fn cell_of(&self, p: V) -> (i64, i64) {
        (((p.0 - self.x0) / self.cell).floor() as i64, ((p.1 - self.y0) / self.cell).floor() as i64)
    }
    #[inline]
    pub fn layer_index(&self, l: usize) -> usize {
        self.index[l]
    }

    /// Can a via stand anywhere in this cell? Same logic as the samples: only a proof counts.
    fn via_open(&self, w: &World, r: &Rules, net: NetId, soft: bool, i: usize, j: usize) -> bool {
        let sub = self.cell / VIA_SUB as f64;
        let hd = sub * 0.7072;
        let need = r.via as f64 / 2.0 + r.clearance as f64;
        let edge = r.via as f64 / 2.0 + r.edge as f64;
        for a in 0..VIA_SUB {
            'sq: for b in 0..VIA_SUB {
                let c = V(self.x0 + (i as f64 + (a as f64 + 0.5) / VIA_SUB as f64) * self.cell, self.y0 + (j as f64 + (b as f64 + 0.5) / VIA_SUB as f64) * self.cell);
                let bb = (c.0 - need, c.1 - need, c.0 + need, c.1 + need);
                for g in &w.layers {
                    let mut closed = false;
                    g.visit(bb, |o| {
                        if (o.net == net && net != NO_NET) || (soft && matches!(o.owner, Owner::Conn(_))) {
                            return true;
                        }
                        if o.shape.dist_pt(c) + hd < need {
                            closed = true;
                            return false;
                        }
                        true
                    });
                    if closed {
                        continue 'sq;
                    }
                }
                let mut closed = false;
                w.edge.visit((c.0 - edge, c.1 - edge, c.0 + edge, c.1 + edge), |o| {
                    if o.shape.dist_pt(c) + hd < edge {
                        closed = true;
                        return false;
                    }
                    true
                });
                if closed {
                    continue 'sq;
                }
                return true;
            }
        }
        false
    }
}

/// One backward search, resumed as the detailed search asks. Keyed on everything that changes its
/// answer, so a later attempt for the same target with the same window and via rule reuses it.
pub struct Back {
    key: (NetId, u64, bool, bool, (i64, i64, i64, i64), u64),
    corridor: Option<Rc<Corridor>>,
    rev: u64,
    i0: i64,
    j0: i64,
    cw: usize,
    ch: usize,
    nl: usize,
    g: Vec<f32>,
    closed: Vec<bool>,
    via: Vec<u8>,
    heap: BinaryHeap<Reverse<(u32, u32)>>,
    src: (i64, i64),
    net: NetId,
    soft: bool,
    no_vias: bool,
    pub pops: u64,
}

/// Terminals by where they are, whichever layers a search allows them on: a bus member's first
/// tries are held to its layer, and it should still find its corridor.
fn ends_hash(ts: &[Terminal]) -> u64 {
    let mut h = 0xcbf2_9ce4_8422_2325u64;
    for t in ts {
        if let Terminal::Point { p, .. } = t {
            h = (h ^ p.0 as u64).wrapping_mul(0x0000_0100_0000_01b3);
            h = (h ^ p.1 as u64).wrapping_mul(0x0000_0100_0000_01b3);
        }
    }
    h
}

fn terminal_hash(ts: &[Terminal]) -> u64 {
    let mut h = 0xcbf2_9ce4_8422_2325u64;
    let mut mix = |v: u64| h = (h ^ v).wrapping_mul(0x0000_0100_0000_01b3);
    for t in ts {
        match t {
            Terminal::Point { p, layers } => {
                mix(p.0 as u64);
                mix(p.1 as u64);
                for &l in layers {
                    mix(l as u64 + 1);
                }
            }
            Terminal::Zone { layer, poly } => {
                mix(*layer as u64 + 100);
                mix(poly.len() as u64);
                if let Some(p) = poly.first() {
                    mix(p.0.to_bits());
                    mix(p.1.to_bits());
                }
            }
            Terminal::Track { a, b, layer, .. } => {
                mix(*layer as u64 + 200);
                mix(a.0 as u64);
                mix(a.1 as u64);
                mix(b.0 as u64);
                mix(b.1 as u64);
            }
        }
    }
    h
}

impl Back {
    fn state(&self, i: i64, j: i64, l: usize) -> Option<usize> {
        let (a, b) = (i - self.i0, j - self.j0);
        if a < 0 || b < 0 || a >= self.cw as i64 || b >= self.ch as i64 {
            return None;
        }
        Some((l * self.ch + b as usize) * self.cw + a as usize)
    }

    #[inline]
    fn est(&self, i: i64, j: i64, cell: f64) -> f32 {
        let (dx, dy) = ((i - self.src.0).abs() as f64, (j - self.src.1).abs() as f64);
        let (hi, lo) = if dx > dy { (dx, dy) } else { (dy, dx) };
        (((hi - lo) + lo * SQRT2) * cell) as f32
    }

    fn relax(&mut self, cell: f64, s: usize, i: i64, j: i64, g: f32) {
        if g < self.g[s] {
            self.g[s] = g;
            let f = g + self.est(i, j, cell);
            // Micrometres: enough to order cells of half a millimetre.
            self.heap.push(Reverse(((f / 1000.0) as u32, s as u32)));
        }
    }

    /// Settle states until this one is settled, or nothing is left.
    fn lookup(&mut self, c: &Coarse, w: &World, r: &Rules, i: i64, j: i64, l: usize) -> f32 {
        let Some(want) = self.state(i, j, l) else { return f32::INFINITY };
        if self.closed[want] {
            return self.g[want];
        }
        let who = net16(self.net);
        let soft = self.soft;
        while let Some(Reverse((_, s))) = self.heap.pop() {
            let s = s as usize;
            if self.closed[s] {
                continue;
            }
            self.closed[s] = true;
            self.pops += 1;
            let (ci, cj, cl) = (s % self.cw, (s / self.cw) % self.ch, s / (self.cw * self.ch));
            let (ai, aj) = (ci as i64 + self.i0, cj as i64 + self.j0);
            let g = self.g[s];
            let mut unit = c.cell as f32 * if c.route[cl] == 0 { 1.0 } else { r.cost_bottom as f32 };
            // Off the planned corridor costs more in the estimate only: a preference, not a wall.
            if let Some(cr) = &self.corridor {
                if !cr.contains(ai, aj, cl) {
                    unit *= 1.0 + CORRIDOR_BIAS;
                }
            }
            // What crossing a boundary adds, or infinity when it is closed. A soft search may cross
            // committed routes at a price, and an estimate that knows this heads straight for the
            // crossing instead of flooding everything cheaper first.
            let cross = |d: usize, a: i64, b: i64| -> f32 {
                if a < 0 || b < 0 || a as usize >= c.w || b as usize >= c.h {
                    return f32::INFINITY;
                }
                let e = c.boundary(cl, d, a as usize, b as usize);
                if c.open(e, who, false) {
                    0.0
                } else if soft && c.open(e, who, true) {
                    SOFT_CROSSING as f32
                } else {
                    f32::INFINITY
                }
            };
            let e = cross(0, ai, aj);
            let wst = cross(0, ai - 1, aj);
            let so = cross(1, ai, aj);
            let n = cross(1, ai, aj - 1);
            for (x, dx, dy) in [(e, 1i64, 0i64), (wst, -1, 0), (so, 0, 1), (n, 0, -1)] {
                if x.is_finite() {
                    if let Some(t) = self.state(ai + dx, aj + dy, cl) {
                        self.relax(c.cell, t, ai + dx, aj + dy, g + unit + x);
                    }
                }
            }
            // A diagonal step needs one of its two L-shaped ways open: any 45-degree line passes
            // through one of them.
            for (dx, dy, a, b) in [(1i64, 1i64, e, so), (1, -1, e, n), (-1, 1, wst, so), (-1, -1, wst, n)] {
                let via_x = a + if dy > 0 { cross(1, ai + dx, aj) } else { cross(1, ai + dx, aj - 1) };
                let via_y = b + if dx > 0 { cross(0, ai, aj + dy) } else { cross(0, ai - 1, aj + dy) };
                let x = via_x.min(via_y);
                if x.is_finite() {
                    if let Some(t) = self.state(ai + dx, aj + dy, cl) {
                        self.relax(c.cell, t, ai + dx, aj + dy, g + unit * SQRT2 as f32 + x);
                    }
                }
            }
            if !self.no_vias && self.nl > 1 {
                let v = ci + cj * self.cw;
                if self.via[v] == 0 {
                    self.via[v] = if c.via_open(w, r, self.net, soft, ai as usize, aj as usize) { 1 } else { 2 };
                }
                if self.via[v] == 1 {
                    for o in 0..self.nl {
                        if o != cl {
                            let t = (o * self.ch + cj) * self.cw + ci;
                            self.relax(c.cell, t, ai, aj, g + r.cost_via as f32);
                        }
                    }
                }
            }
            if s == want {
                return g;
            }
        }
        f32::INFINITY
    }
}

/// What the search keeps between calls: the map and its recent backward searches.
#[derive(Default)]
pub struct Guide {
    pub coarse: Option<Coarse>,
    tables: Vec<Back>,
    pub back_pops: u64,
    pub closed_early: u64,
    pub pockets_closed: u64,
    pub searches: u64,
    pub nodes_ok: u64,
    pub nodes_failed: u64,
    /// The last query that failed, so a retry can afford a closer look.
    failed: Option<(NetId, u64, u64)>,
    pockets: Vec<((u64, NetId, bool, bool), u64, bool)>,
    /// When the first search of the run began, for the hard stop inside a long search (4.6).
    pub start: Option<crate::clock::Instant>,
    pub plan: Option<GlobalPlan>,
    /// What the connection being routed should look like, if it belongs to a bus.
    pub hint: Option<Hint>,
}

/// A bus member's preference: its neighbour's shape carried over to its own pins, and a layer. Only
/// ever a small cost: the search still finds its own way where the neighbour's shape doesn't fit.
#[derive(Clone, Default)]
pub struct Hint {
    pub net: NetId,
    /// Runs to follow, and the layer each is on.
    pub lanes: Vec<(V, V, usize)>,
    pub layer: Option<usize>,
}

/// How much dearer a step away from the lanes is. All octilinear routes between two points of one
/// length tie, so this only has to break ties, and more than the search's own 20% inflation would
/// flood. At 0, 0.1 and 0.25 the boards' results vary with no trend (benchmark C 269, 287, 259 of 300);
/// 0.1 is what benchmark B's picture was judged at.
const OFF_LANE: f64 = 0.1;

impl Hint {
    #[inline]
    pub fn extra(&self, a: V, b: V, layer: usize) -> f64 {
        let mut k = 0.0;
        if let Some(l) = self.layer {
            if l != layer {
                k += OFF_LANE;
            }
        }
        if !self.lanes.is_empty() && !self.lanes.iter().any(|(p, q, l)| *l == layer && pt_seg(a, *p, *q) <= 2000.0 && pt_seg(b, *p, *q) <= 2000.0) {
            k += OFF_LANE;
        }
        k
    }
}

/// The pocket check looks this far around a terminal, in squares of this size.
const POCKET_R: f64 = 2.0 * NM;
const POCKET_S: f64 = 0.05 * NM;

/// Is this terminal walled in? A flood at the fine scale from the pad, over squares that a single
/// obstacle doesn't provably cover, looking for the edge of the area, the other terminal, or a place
/// a via could stand. Measured on benchmark C: most failing searches come within two cells of a pin
/// they can't get into and then spend their whole node budget circling it. Same rule as the map:
/// walled in means proven, never rounded, and a lane that exactly fits stays open.
fn walled_in(c: &Coarse, w: &World, q: &Query, p: P, layers: &[usize], other: &[Terminal]) -> bool {
    let n = (2.0 * POCKET_R / POCKET_S) as i64;
    let (ox, oy) = (p.0 as f64 - POCKET_R, p.1 as f64 - POCKET_R);
    let hd = POCKET_S * 0.7072;
    let nl = c.route.len();
    let soft = q.soft.is_some();
    let un = n as usize;
    let mut closed = vec![false; un * un * nl];
    let centre = |i: i64, j: i64| V(ox + (i as f64 + 0.5) * POCKET_S, oy + (j as f64 + 0.5) * POCKET_S);
    let region = (ox, oy, ox + 2.0 * POCKET_R, oy + 2.0 * POCKET_R);
    let mut paint = |l: usize, shape: &Shape, bb: (f64, f64, f64, f64), need: f64| {
        let lo = |v: f64, o: f64| (((v - need - o) / POCKET_S).floor() as i64).clamp(0, n);
        let hi = |v: f64, o: f64| (((v + need - o) / POCKET_S).ceil() as i64).clamp(0, n);
        for j in lo(bb.1, oy)..hi(bb.3, oy) {
            for i in lo(bb.0, ox)..hi(bb.2, ox) {
                let at = (l * un + j as usize) * un + i as usize;
                if !closed[at] && shape.dist_pt(centre(i, j)) + hd < need {
                    closed[at] = true;
                }
            }
        }
    };
    for l in 0..nl {
        let need = c.need;
        let r = (region.0 - need, region.1 - need, region.2 + need, region.3 + need);
        w.layers[c.route[l]].visit(r, |o| {
            if (o.net == q.net && q.net != NO_NET) || (soft && matches!(o.owner, Owner::Conn(_))) || w.crosses_pour(o, q.net) {
                return true;
            }
            paint(l, &o.shape, o.bb, need);
            true
        });
        let e = c.need_edge;
        w.edge.visit((region.0 - e, region.1 - e, region.2 + e, region.3 + e), |o| {
            paint(l, &o.shape, o.bb, e);
            true
        });
    }
    let goal: Vec<(i64, i64, usize)> = other
        .iter()
        .filter_map(|t| if let Terminal::Point { p: g, layers } = t { Some((*g, layers)) } else { None })
        .flat_map(|(g, ls)| {
            let (i, j) = (((g.0 as f64 - ox) / POCKET_S).floor() as i64, ((g.1 as f64 - oy) / POCKET_S).floor() as i64);
            ls.iter().filter(|&&l| c.index[l] != usize::MAX).map(move |&l| (i, j, l)).collect::<Vec<_>>()
        })
        .map(|(i, j, l)| (i, j, c.index[l]))
        .collect();
    let mut seen = vec![false; un * un * nl];
    let mut via_tried = vec![false; un * un / 4 + un + 1];
    let mut stack: Vec<(i64, i64, usize)> = Vec::new();
    let (si, sj) = (n / 2, n / 2);
    for &l in layers {
        if c.index[l] != usize::MAX {
            let cl = c.index[l];
            seen[(cl * un + sj as usize) * un + si as usize] = true;
            stack.push((si, sj, cl));
        }
    }
    let via_need = q.rules.via as f64 / 2.0 + q.rules.clearance as f64;
    let via_edge = q.rules.via as f64 / 2.0 + q.rules.edge as f64;
    let via_hd = 2.0 * POCKET_S * 0.7072;
    let can_via = q.profile.max_vias > 0 && nl > 1;
    while let Some((i, j, l)) = stack.pop() {
        if i == 0 || j == 0 || i == n - 1 || j == n - 1 || goal.contains(&(i, j, l)) {
            return false;
        }
        if can_via {
            // Tested on squares twice the size, so each proof covers four flood squares.
            let (vi, vj) = (i / 2, j / 2);
            let tag = (vj * n / 2 + vi) as usize;
            if !via_tried[tag] {
                via_tried[tag] = true;
                let m = V(ox + (vi as f64 + 0.5) * 2.0 * POCKET_S, oy + (vj as f64 + 0.5) * 2.0 * POCKET_S);
                let bb = (m.0 - via_need, m.1 - via_need, m.0 + via_need, m.1 + via_need);
                let mut stands = true;
                for g in &w.layers {
                    g.visit(bb, |o| {
                        if (o.net == q.net && q.net != NO_NET) || (soft && matches!(o.owner, Owner::Conn(_))) {
                            return true;
                        }
                        if o.shape.dist_pt(m) + via_hd < via_need {
                            stands = false;
                            return false;
                        }
                        true
                    });
                    if !stands {
                        break;
                    }
                }
                if stands {
                    w.edge.visit((m.0 - via_edge, m.1 - via_edge, m.0 + via_edge, m.1 + via_edge), |o| {
                        if o.shape.dist_pt(m) + via_hd < via_edge {
                            stands = false;
                            return false;
                        }
                        true
                    });
                }
                if stands {
                    for o in 0..nl {
                        let at = (o * un + j as usize) * un + i as usize;
                        if !seen[at] && !closed[at] {
                            seen[at] = true;
                            stack.push((i, j, o));
                        }
                    }
                }
            }
        }
        for dj in -1..=1i64 {
            for di in -1..=1i64 {
                let (a, b) = (i + di, j + dj);
                let at = (l * un + b as usize) * un + a as usize;
                if !seen[at] && !closed[at] {
                    seen[at] = true;
                    stack.push((a, b, l));
                }
            }
        }
    }
    true
}

impl Guide {
    /// Prepare the backward search for a query, or say the query isn't guided. Pair centrelines
    /// and fan-ins skip checks the map can't know about, so they stay out of it.
    pub fn prepare(&mut self, w: &World, q: &Query, window: (f64, f64, f64, f64)) -> Option<usize> {
        if q.also.is_some() || !q.free.is_empty() || q.targets.is_empty() || q.profile.neck < q.rules.neck || q.profile.clearance < q.rules.clearance {
            return None;
        }
        if self.coarse.is_none() {
            self.coarse = Some(Coarse::build(w, q.rules));
        }
        let c = self.coarse.as_mut().unwrap();
        c.sync(w);
        let c = self.coarse.as_ref().unwrap();
        let soft = q.soft.is_some();
        let no_vias = q.profile.max_vias == 0;
        let (a, b) = (c.cell_of(V(window.0, window.1)), c.cell_of(V(window.2, window.3)));
        let (i0, j0) = (a.0.max(0), a.1.max(0));
        let (i1, j1) = (b.0.min(c.w as i64 - 1), b.1.min(c.h as i64 - 1));
        if i0 > i1 || j0 > j1 {
            return None;
        }
        let corridor = if soft || q.profile.margin >= 8.0 * NM { None } else { self.corridor_of(q) };
        let key = (q.net, terminal_hash(q.targets), soft, no_vias, (i0, j0, i1, j1), terminal_hash(q.sources) * corridor.is_some() as u64);
        let c = self.coarse.as_ref().unwrap();
        let rev = if soft { c.rev_s } else { c.rev_d };
        self.tables.retain(|t| t.rev == rev);
        if let Some(i) = self.tables.iter().position(|t| t.key == key) {
            return Some(i);
        }
        if self.tables.len() >= 8 {
            self.tables.remove(0);
        }
        let (cw, ch, nl) = ((i1 - i0 + 1) as usize, (j1 - j0 + 1) as usize, c.route.len());
        let n = cw * ch * nl;
        let mut src = (0, 0);
        for t in q.sources {
            if let Terminal::Point { p, .. } = t {
                src = c.cell_of((*p).into());
                break;
            }
        }
        let mut t = Back { key, corridor, rev, i0, j0, cw, ch, nl, g: vec![f32::INFINITY; n], closed: vec![false; n], via: vec![0; cw * ch], heap: BinaryHeap::new(), src, net: q.net, soft, no_vias, pops: 0 };
        for term in q.targets {
            match term {
                // A tap onto a rail: every cell along the track is a goal.
                Terminal::Track { a, b, layer, .. } => {
                    if c.index[*layer] == usize::MAX {
                        continue;
                    }
                    let l = c.index[*layer];
                    let (va, vb): (V, V) = ((*a).into(), (*b).into());
                    let steps = (hypot(sub(va, vb)) / (c.cell * 0.5)).ceil().max(1.0) as usize;
                    for k in 0..=steps {
                        let f = k as f64 / steps as f64;
                        let (i, j) = c.cell_of(V(va.0 + (vb.0 - va.0) * f, va.1 + (vb.1 - va.1) * f));
                        if let Some(s) = t.state(i, j, l) {
                            t.relax(c.cell, s, i, j, 0.0);
                        }
                    }
                }
                Terminal::Point { p, layers } => {
                    let (i, j) = c.cell_of((*p).into());
                    for &l in layers {
                        if c.index[l] != usize::MAX {
                            if let Some(s) = t.state(i, j, c.index[l]) {
                                t.relax(c.cell, s, i, j, 0.0);
                            }
                        }
                    }
                }
                Terminal::Zone { layer, poly } => {
                    if c.index[*layer] == usize::MAX {
                        continue;
                    }
                    let l = c.index[*layer];
                    let b = Shape::Poly { pts: poly.clone(), r: 0.0 }.bbox();
                    let (u, v) = (c.cell_of(V(b.0, b.1)), c.cell_of(V(b.2, b.3)));
                    let reach = c.cell * 0.7072;
                    let edge = Shape::Poly { pts: poly.clone(), r: 0.0 };
                    for j in u.1.max(j0)..=v.1.min(j1) {
                        for i in u.0.max(i0)..=v.0.min(i1) {
                            let m = V(c.x0 + (i as f64 + 0.5) * c.cell, c.y0 + (j as f64 + 0.5) * c.cell);
                            // dist_pt is zero inside the outline.
                            if edge.dist_pt(m) <= reach {
                                if let Some(s) = t.state(i, j, l) {
                                    t.relax(c.cell, s, i, j, 0.0);
                                }
                            }
                        }
                    }
                }
            }
        }
        self.tables.push(t);
        Some(self.tables.len() - 1)
    }

    /// One line for the run's report: what the search spent, and what the map saved it.
    pub fn summary(&self) -> String {
        format!("search: {} searches, {} nodes in those that succeeded, {} in those that failed; {} closed by the coarse map, {} by a walled-in terminal; {} coarse states", self.searches, self.nodes_ok, self.nodes_failed, self.closed_early, self.pockets_closed, self.back_pops)
    }

    /// Could a via stand in this point's cell? False is a proof, as everywhere on the map.
    pub fn via_possible(&mut self, table: usize, w: &World, r: &Rules, p: V) -> bool {
        let c = self.coarse.as_ref().unwrap();
        let (i, j) = c.cell_of(p);
        let t = &mut self.tables[table];
        let (a, b) = (i - t.i0, j - t.j0);
        if a < 0 || b < 0 || a >= t.cw as i64 || b >= t.ch as i64 {
            return true;
        }
        let v = b as usize * t.cw + a as usize;
        if t.via[v] == 0 {
            t.via[v] = if c.via_open(w, r, t.net, t.soft, i as usize, j as usize) { 1 } else { 2 };
        }
        t.via[v] == 1
    }

    pub fn corridor_of(&self, q: &Query) -> Option<Rc<Corridor>> {
        let plan = self.plan.as_ref()?;
        plan.corridors.get(&(q.net, ends_hash(q.sources), ends_hash(q.targets))).cloned()
    }

    pub fn note_failed(&mut self, q: &Query) {
        if let Some(c) = &self.coarse {
            self.failed = Some((q.net, terminal_hash(q.targets), if q.soft.is_some() { c.rev_s } else { c.rev_d }));
        }
    }

    /// Retrying after a failure: is either end walled in? Only then is the closer look worth it,
    /// and the answer carries over to every later attempt for the same pins.
    pub fn hopeless(&mut self, w: &World, q: &Query) -> bool {
        let Some(c) = self.coarse.as_ref() else { return false };
        let soft = q.soft.is_some();
        let rev = if soft { c.rev_s } else { c.rev_d };
        if self.failed != Some((q.net, terminal_hash(q.targets), rev)) {
            return false;
        }
        let no_vias = q.profile.max_vias == 0;
        self.pockets.retain(|x| x.1 == rev);
        let mut closed = false;
        for (ours, others) in [(q.sources, q.targets), (q.targets, q.sources)] {
            for t in ours {
                let Terminal::Point { p, layers } = t else { continue };
                if others.iter().any(|o| matches!(o, Terminal::Zone { .. })) {
                    continue;
                }
                let key = (terminal_hash(std::slice::from_ref(t)) ^ terminal_hash(others), q.net, soft, no_vias);
                let v = match self.pockets.iter().find(|x| x.0 == key) {
                    Some(x) => x.2,
                    None => {
                        let v = walled_in(c, w, q, *p, layers, others);
                        self.pockets.push((key, rev, v));
                        v
                    }
                };
                closed |= v;
            }
        }
        if closed {
            self.pockets_closed += 1;
        }
        closed
    }

    /// The coarse cost from a point on a layer to the target; infinity is a proof of no way there.
    #[inline]
    pub fn cost(&mut self, table: usize, w: &World, r: &Rules, p: V, layer: usize) -> f64 {
        let c = self.coarse.as_ref().unwrap();
        let (i, j) = c.cell_of(p);
        let t = &mut self.tables[table];
        let before = t.pops;
        let g = t.lookup(c, w, r, i, j, c.index[layer]);
        self.back_pops += t.pops - before;
        if g.is_finite() {
            // Each end of a real route can be up to a cell closer than the cell centres say.
            (g as f64 - 2.0 * c.cell).max(0.0)
        } else {
            f64::INFINITY
        }
    }
}

// ---------------------------------------------------------------------------------------------
// The global stage: before any copper is drawn, give every connection a corridor of coarse cells.
//
// Negotiation lives here and only here. PathFinder at lattice level scored poorly on ordinary boards
// (OrthoRoute's README cites 0.02 clean pass), while as an iterated assignment over a coarse network
// it converges (SUMO's duaIterate, VTR's rounds): route everything, price what is overused, repeat,
// with present and accumulated cost as in VTR's get_rr_cong_cost. A corridor can never make a route
// illegal: the detailed search still checks every step against real copper, and it only reads the
// corridor as a preference in its estimate, dropped when the search has to widen.
// ---------------------------------------------------------------------------------------------

use crate::board::Board;
use crate::classify::{Level, Task};
use std::collections::HashMap;
use std::rc::Rc;

const ROUNDS: usize = 16;
/// VTR's defaults, roughly: first present-cost factor, its growth per round, and the history step.
const PRES_INIT: f32 = 0.5;
const PRES_MULT: f32 = 1.5;
const ACC_FAC: f32 = 0.5;

/// A corridor: which global cells this connection plans to use, per layer.
pub struct Corridor {
    pub bbox: (f64, f64, f64, f64),
    on: Vec<bool>,
    i0: i64,
    j0: i64,
    gw: usize,
    gh: usize,
    f: i64,
    nl: usize,
}

impl Corridor {
    #[inline]
    fn contains(&self, ci: i64, cj: i64, l: usize) -> bool {
        let (i, j) = (ci.div_euclid(self.f) - self.i0, cj.div_euclid(self.f) - self.j0);
        i >= 0 && j >= 0 && (i as usize) < self.gw && (j as usize) < self.gh && l < self.nl && self.on[(l * self.gh + j as usize) * self.gw + i as usize]
    }
}

/// What the global stage hands back to the router: a preference per connection and an order hint.
#[derive(Default, Clone)]
pub struct GlobalPlan {
    corridors: HashMap<(NetId, u64, u64), Rc<Corridor>>,
    pub note: String,
}

struct Conn {
    a: (i64, i64, Vec<usize>),
    b: (i64, i64, Vec<usize>),
    demand: f32,
    path: Vec<(i64, i64, usize)>,
    key: (NetId, u64, u64),
}

fn env_on(name: &str) -> bool {
    std::env::var_os(name).is_some()
}

fn pad_term(board: &Board, w: &World, i: usize) -> Terminal {
    let p = &board.pads[i];
    Terminal::Point { p: p.center, layers: p.layers.iter().copied().filter(|l| w.route_layers.contains(l)).collect() }
}

/// Assign every connection a corridor by negotiated congestion. Called once per routing pass, with
/// the pairs already placed so their room is gone.
///
/// The plan doesn't change the routing order. Tried at 60 s: most contested first lost connections
/// against shortest first (benchmark C 265 against 268), least contested first won on benchmark C (271)
/// and lost on piprobe_v13 (86 against 87). That is within the run-to-run spread, so the order stays
/// as the router sets it.
pub fn plan(w: &World, r: &Rules, board: &Board, tasks: &[Task], held_to: &dyn Fn(&Task) -> Option<usize>) -> GlobalPlan {
    let t0 = std::time::Instant::now();
    let mut out = GlobalPlan::default();
    if env_on("ADOM_ROUTE_NO_GLOBAL") {
        w.guide.borrow_mut().plan = None;
        return out;
    }
    let mut guide = w.guide.borrow_mut();
    if guide.coarse.is_none() {
        guide.coarse = Some(Coarse::build(w, r));
    }
    let c = guide.coarse.as_mut().unwrap();
    c.sync(w);
    let c = guide.coarse.as_ref().unwrap();
    // Global cells of 1 mm on a molecule, 2 mm on a large board, so a round stays in milliseconds.
    let big = c.w as f64 * c.cell > 60.0 * NM || c.h as f64 * c.cell > 60.0 * NM;
    let f: usize = if big { 8 } else { 4 };
    let g = c.cell * f as f64;
    let (gw, gh, nl) = (c.w / f, c.h / f, c.route.len());
    if gw < 2 || gh < 2 {
        return out;
    }
    let pitch = (r.track + r.clearance) as f64;
    // Capacity of each global boundary: tracks that fit in each free run of real centreline room.
    // Layer l, direction d, (i, j): from global cell (i, j) to the next in x (d 0) or y (d 1).
    let ne = nl * 2 * gw * gh;
    let mut cap = vec![0f32; ne];
    let edge = |l: usize, d: usize, i: usize, j: usize| ((l * 2 + d) * gh + j) * gw + i;
    for l in 0..nl {
        for d in 0..2 {
            for j in 0..gh {
                for i in 0..gw {
                    let mut tracks = 0.0f32;
                    let mut run = 0usize;
                    let mut flush = |run: &mut usize| {
                        if *run > 0 {
                            tracks += (*run as f64 * c.s / pitch).floor() as f32 + 1.0;
                            *run = 0;
                        }
                    };
                    for t in 0..f {
                        let (bi, bj) = if d == 0 { ((i + 1) * f - 1, j * f + t) } else { (i * f + t, (j + 1) * f - 1) };
                        if bi >= c.w || bj >= c.h {
                            continue;
                        }
                        let b = c.boundary(l, d, bi, bj);
                        let m = c.mask_s[b] | c.mask_d[b];
                        for bit in 0..K {
                            if m & (1 << bit) == 0 {
                                run += 1;
                            } else {
                                flush(&mut run);
                            }
                        }
                    }
                    flush(&mut run);
                    cap[edge(l, d, i, j)] = tracks;
                }
            }
        }
    }
    let mut conns: Vec<Conn> = Vec::new();
    let gcell = |p: P| -> (i64, i64) {
        let (i, j) = c.cell_of(p.into());
        (i.div_euclid(f as i64), j.div_euclid(f as i64))
    };
    for t in tasks {
        if t.zone.is_some() || t.a == t.b {
            continue;
        }
        let (ta, tb) = (pad_term(board, w, t.a), pad_term(board, w, t.b));
        let (Terminal::Point { p: pa, layers: la }, Terminal::Point { p: pb, layers: lb }) = (&ta, &tb) else { continue };
        if la.is_empty() || lb.is_empty() {
            continue;
        }
        let (ca, cb) = (gcell(*pa), gcell(*pb));
        let demand = if t.level == Level::Power && t.main {
            let main = r.wide.get(board.net_name(t.net)).and_then(|v| v.first().copied()).unwrap_or(r.power_floor);
            (((main + r.clearance) as f64) / pitch).max(1.0) as f32
        } else {
            1.0
        };
        let key = (t.net, ends_hash(std::slice::from_ref(&ta)), ends_hash(std::slice::from_ref(&tb)));
        // A bus member with a layer chosen plans on that layer.
        let on = |ls: &Vec<usize>| -> Vec<usize> {
            match held_to(t) {
                Some(l) if ls.contains(&l) => vec![c.index[l]],
                _ => ls.iter().map(|&l| c.index[l]).collect(),
            }
        };
        conns.push(Conn { a: (ca.0, ca.1, on(la)), b: (cb.0, cb.1, on(lb)), demand, path: Vec::new(), key });
    }
    // Long ones first in the first round, so short ones see where the long ones want to be.
    let mut order: Vec<usize> = (0..conns.len()).collect();
    let span = |x: &Conn| (x.a.0 - x.b.0).abs() + (x.a.1 - x.b.1).abs();
    order.sort_by_key(|&i| -span(&conns[i]));

    let mut occ = vec![0f32; ne];
    let mut hist = vec![1f32; ne];
    let mut pres = PRES_INIT;
    let ng = gw * gh * nl;
    let mut best = vec![f32::INFINITY; ng];
    let mut prev = vec![u32::MAX; ng];
    let mut stamp = vec![0u32; ng];
    let mut tick = 0u32;
    let mut heap: BinaryHeap<Reverse<(u32, u32)>> = BinaryHeap::new();
    let base = (g * 0.75) as f32;
    let via_cost = r.cost_via as f32;
    let (mut first_over, mut last_over, mut rounds) = (0.0f32, 0.0f32, 0usize);
    for round in 0..ROUNDS {
        rounds = round + 1;
        let mut changed = 0;
        for &ci in &order {
            let conn = &mut conns[ci];
            // Only connections through something overused need a new corridor (incremental
            // PathFinder); the rest keep theirs, as SUMO keeps most drivers on their routes.
            let (mut over, mut has) = (false, false);
            for s in conn.path.windows(2) {
                has = true;
                if let Some(e) = charged(conn, s[0], s[1], &cap, gw, gh) {
                    if occ[e] > cap[e] {
                        over = true;
                        break;
                    }
                }
            }
            if has && !over {
                continue;
            }
            changed += 1;
            for s in conn.path.windows(2) {
                if let Some(e) = charged(conn, s[0], s[1], &cap, gw, gh) {
                    occ[e] -= conn.demand;
                }
            }
            // A* over global cells. Crossing a boundary costs its length, times history, times the
            // present cost of being over capacity.
            tick += 1;
            heap.clear();
            let idx = |i: i64, j: i64, l: usize| (l * gh + j as usize) * gw + i as usize;
            let inb = |i: i64, j: i64| i >= 0 && j >= 0 && (i as usize) < gw && (j as usize) < gh;
            let (ta, tb) = (conn.b.0, conn.b.1);
            let est = |i: i64, j: i64| ((i - ta).abs() + (j - tb).abs()) as f32 * base;
            for &l in &conn.a.2 {
                if inb(conn.a.0, conn.a.1) {
                    let s = idx(conn.a.0, conn.a.1, l);
                    best[s] = 0.0;
                    stamp[s] = tick;
                    prev[s] = u32::MAX;
                    heap.push(Reverse(((est(conn.a.0, conn.a.1) / 100.0) as u32, s as u32)));
                }
            }
            let mut goal = None;
            while let Some(Reverse((_, s))) = heap.pop() {
                let s = s as usize;
                let (i, j, l) = ((s % gw) as i64, ((s / gw) % gh) as i64, s / (gw * gh));
                if i == ta && j == tb && conn.b.2.contains(&l) {
                    goal = Some(s);
                    break;
                }
                let gs = best[s];
                let mult = if c.route[l] == 0 { 1.0 } else { r.cost_bottom as f32 };
                for (di, dj) in [(1i64, 0i64), (-1, 0), (0, 1), (0, -1)] {
                    let (a, b) = (i + di, j + dj);
                    if !inb(a, b) {
                        continue;
                    }
                    let e = step_edge((i, j, l), (a, b, l), gw, gh).unwrap();
                    let over_by = (occ[e] + conn.demand - cap[e]).max(0.0);
                    // A pin's own cell boundary reads closed to everyone (its pads block the map),
                    // so it costs no penalty for the connection that starts or ends there.
                    let at_end = (i == conn.a.0 && j == conn.a.1) || (i == ta && j == tb) || (a == conn.a.0 && b == conn.a.1) || (a == ta && b == tb);
                    let cong = if at_end && cap[e] < conn.demand { 1.0 } else { hist[e] * (1.0 + pres * over_by) };
                    let n = gs + base * mult * cong;
                    let t = idx(a, b, l);
                    if stamp[t] != tick || n < best[t] {
                        stamp[t] = tick;
                        best[t] = n;
                        prev[t] = s as u32;
                        heap.push(Reverse((((n + est(a, b)) / 100.0) as u32, t as u32)));
                    }
                }
                for o in 0..nl {
                    if o != l {
                        let t = idx(i, j, o);
                        let n = gs + via_cost;
                        if stamp[t] != tick || n < best[t] {
                            stamp[t] = tick;
                            best[t] = n;
                            prev[t] = s as u32;
                            heap.push(Reverse(((n + est(i, j)) as u32 / 100, t as u32)));
                        }
                    }
                }
            }
            conn.path.clear();
            if let Some(mut s) = goal {
                loop {
                    conn.path.push(((s % gw) as i64, ((s / gw) % gh) as i64, s / (gw * gh)));
                    if prev[s] == u32::MAX {
                        break;
                    }
                    s = prev[s] as usize;
                }
                conn.path.reverse();
            }
            for s in conn.path.windows(2) {
                if let Some(e) = charged(conn, s[0], s[1], &cap, gw, gh) {
                    occ[e] += conn.demand;
                }
            }
        }
        let mut over_total = 0.0;
        for e in 0..ne {
            let o = (occ[e] - cap[e]).max(0.0);
            over_total += o;
            hist[e] += ACC_FAC * o;
        }
        if round == 0 {
            first_over = over_total;
        }
        last_over = over_total;
        pres *= PRES_MULT;
        // No wall-clock cut-off (clock.rs): the rounds are bounded by ROUNDS, the same on every run.
        if changed == 0 {
            break;
        }
    }
    // Corridors: the planned cells, a cell wider each way, so the search has room to choose.
    for conn in &conns {
        if conn.path.is_empty() {
            continue;
        }
        let (mut i0, mut j0, mut i1, mut j1) = (i64::MAX, i64::MAX, i64::MIN, i64::MIN);
        for s in &conn.path {
            i0 = i0.min(s.0 - 1);
            j0 = j0.min(s.1 - 1);
            i1 = i1.max(s.0 + 1);
            j1 = j1.max(s.1 + 1);
        }
        let (cw, ch) = ((i1 - i0 + 1) as usize, (j1 - j0 + 1) as usize);
        let mut on = vec![false; cw * ch * nl];
        for s in &conn.path {
            for dj in -1..=1i64 {
                for di in -1..=1i64 {
                    on[(s.2 * ch + (s.1 + dj - j0) as usize) * cw + (s.0 + di - i0) as usize] = true;
                }
            }
        }
        let bbox = (c.x0 + i0 as f64 * g, c.y0 + j0 as f64 * g, c.x0 + (i1 + 1) as f64 * g, c.y0 + (j1 + 1) as f64 * g);
        out.corridors.insert(conn.key, Rc::new(Corridor { bbox, on, i0, j0, gw: cw, gh: ch, f: f as i64, nl }));
    }
    out.note = format!("global: {} connections, {} rounds, overuse {:.0} -> {:.0}, {:.0} ms", conns.len(), rounds, first_over, last_over, t0.elapsed().as_secs_f64() * 1000.0);
    guide.plan = Some(out.clone());
    out
}

/// The boundary a step uses up. A pin's own cell boundary reads closed to everyone, since its pads
/// block the map, so a step off a terminal over such a boundary uses nothing up.
#[inline]
fn charged(conn: &Conn, a: (i64, i64, usize), b: (i64, i64, usize), cap: &[f32], gw: usize, gh: usize) -> Option<usize> {
    let e = step_edge(a, b, gw, gh)?;
    let end = |p: (i64, i64, usize)| (p.0 == conn.a.0 && p.1 == conn.a.1) || (p.0 == conn.b.0 && p.1 == conn.b.1);
    if cap[e] < conn.demand && (end(a) || end(b)) {
        return None;
    }
    Some(e)
}

/// Would these two connections cross if each ran straight? The estimate buses use. Coarse on purpose:
/// which of two lines must give way depends on the ends, not on the detail of the route between.
pub fn chords_cross(a: V, b: V, c: V, d: V) -> bool {
    seg_cross(a, b, c, d)
}

/// The boundary between two neighbouring global cells on one layer; None for a via.
#[inline]
fn step_edge(a: (i64, i64, usize), b: (i64, i64, usize), gw: usize, gh: usize) -> Option<usize> {
    if a.2 != b.2 {
        return None;
    }
    let (d, i, j) = if a.1 == b.1 { (0, a.0.min(b.0), a.1) } else { (1, a.0, a.1.min(b.1)) };
    Some(((a.2 * 2 + d) * gh + j as usize) * gw + i as usize)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::router::build_world;
    use crate::search::{search, Profile};

    fn board_text(extra: &str) -> String {
        format!(
            r#"(kicad_pcb (version 20240108) (generator test)
  (layers (0 "F.Cu" signal) (31 "B.Cu" signal) (44 "Edge.Cuts" user))
  (net 0 "") (net 1 "A") (net 2 "B")
  (gr_rect (start 0 0) (end 20 10) (layer "Edge.Cuts") (width 0.1))
  {extra}
)"#
        )
    }

    fn term(x: f64, y: f64) -> [Terminal; 1] {
        [Terminal::Point { p: (mm(x), mm(y)), layers: vec![0] }]
    }

    fn profile(r: &Rules, vias: u32) -> Profile {
        Profile { width: r.neck, neck: r.neck, clearance: r.clearance, target_gap: r.clearance, max_vias: vias, margin: 40.0 * NM, layer_bias: None }
    }

    fn query<'a>(r: &'a Rules, s: &'a [Terminal], t: &'a [Terminal], vias: u32) -> Query<'a> {
        Query { net: 99, also: None, sources: s, targets: t, profile: profile(r, vias), rules: r, soft: None, via_in: None, history: None, free: &[], arrive: None }
    }

    /// A wall of two tracks with a gap that a neck-width track fits exactly. Rounding of any kind
    /// would close this lane; the map must not. A tenth of a millimetre less must close it.
    #[test]
    fn a_lane_that_exactly_fits_stays_open() {
        let r = Rules::default();
        let gap = (r.neck + 2 * r.clearance) as f64 / NM;
        let half = r.track as f64 / NM / 2.0;
        let (a, b) = (5.0 - gap / 2.0 - half, 5.0 + gap / 2.0 + half);
        let extra = format!(
            r#"(segment (start 10 0.5) (end 10 {a}) (width 0.2) (layer "F.Cu") (net 2))
               (segment (start 10 {b}) (end 10 9.5) (width 0.2) (layer "F.Cu") (net 2))"#
        );
        let board = Board::parse(board_text(&extra)).unwrap();
        let w = build_world(&board, &r);
        let (s, t) = (term(5.0, 5.0), term(15.0, 5.0));
        let q = query(&r, &s, &t, 0);
        let mut guide = w.guide.borrow_mut();
        let tb = guide.prepare(&w, &q, (0.0, 0.0, 20.0 * NM, 10.0 * NM)).unwrap();
        assert!(guide.cost(tb, &w, &r, V(5.0 * NM, 5.0 * NM), 0).is_finite());
        drop(guide);
        assert!(search(&w, &q).is_some(), "the detailed search should use the lane too");

        let (a, b) = (a + 0.05, b - 0.05);
        let extra = format!(
            r#"(segment (start 10 0.5) (end 10 {a}) (width 0.2) (layer "F.Cu") (net 2))
               (segment (start 10 {b}) (end 10 9.5) (width 0.2) (layer "F.Cu") (net 2))"#
        );
        let board = Board::parse(board_text(&extra)).unwrap();
        let w = build_world(&board, &r);
        let q = query(&r, &s, &t, 0);
        assert!(search(&w, &q).is_none(), "the lane is 0.1 mm too narrow");
    }

    /// The same wall with no lane at all is a proof: no nodes spent.
    #[test]
    fn a_closed_wall_is_proved_without_searching() {
        let r = Rules::default();
        let extra = r#"(segment (start 10 0) (end 10 10) (width 0.2) (layer "F.Cu") (net 2))"#;
        let board = Board::parse(board_text(extra)).unwrap();
        let w = build_world(&board, &r);
        let (s, t) = (term(5.0, 5.0), term(15.0, 5.0));
        let q = query(&r, &s, &t, 0);
        assert!(search(&w, &q).is_none());
        let g = w.guide.borrow();
        assert_eq!(g.closed_early, 1);
        assert_eq!(g.nodes_failed, 0);
    }

    /// A committed route closes the map and taking it away opens it again.
    #[test]
    fn the_map_follows_commits_and_rips() {
        let r = Rules::default();
        let board = Board::parse(board_text("")).unwrap();
        let mut w = build_world(&board, &r);
        let (s, t) = (term(5.0, 5.0), term(15.0, 5.0));
        assert!(search(&w, &query(&r, &s, &t, 0)).is_some());
        let id = w.layers[0].add(Shape::Capsule { a: V(10.0 * NM, 0.0), b: V(10.0 * NM, 10.0 * NM), r: 0.1 * NM }, 2, Owner::Conn(7));
        assert!(search(&w, &query(&r, &s, &t, 0)).is_none());
        assert_eq!(w.guide.borrow().closed_early, 1);
        w.layers[0].remove(id);
        assert!(search(&w, &query(&r, &s, &t, 0)).is_some());
    }

    /// The hard case the map must not get wrong: every pin of the 0.4 mm QFN on PiProbe with its
    /// copper stripped. The designer routes all of these; "no path" here would be the map's mistake.
    #[test]
    fn piprobe_u1_escapes_are_open() {
        let path = concat!(env!("CARGO_MANIFEST_DIR"), "/bench/boards/piprobe_v13.ref.kicad_pcb");
        if !std::path::Path::new(&path).exists() {
            eprintln!("skipped: {path} is not here (the reference boards do not ship with the source)");
            return;
        }
        let mut board = Board::read(path).unwrap();
        board.tracks.clear();
        board.vias.clear();
        let mut r = Rules::default();
        crate::project::apply(path, &mut r);
        let w = build_world(&board, &r);
        let u1 = board.footprints.iter().find(|f| f.pads.iter().any(|&p| board.pad_name(p).starts_with("U1.")));
        let u1 = u1.expect("U1 on the board");
        let mut guide = w.guide.borrow_mut();
        guide.coarse = Some(Coarse::build(&w, &r));
        let c = guide.coarse.as_ref().unwrap();
        let mut checked = 0;
        for &i in &u1.pads {
            let pad = &board.pads[i];
            if pad.net == NO_NET || pad.layers.is_empty() {
                continue;
            }
            let Some(&other) = (0..board.pads.len()).collect::<Vec<_>>().iter().find(|&&o| o != i && board.pads[o].net == pad.net && !u1.pads.contains(&o)) else { continue };
            let layers: Vec<usize> = pad.layers.iter().copied().filter(|l| w.route_layers.contains(l)).collect();
            let s = [Terminal::Point { p: pad.center, layers: layers.clone() }];
            let t = [Terminal::Point { p: board.pads[other].center, layers: board.pads[other].layers.iter().copied().filter(|l| w.route_layers.contains(l)).collect() }];
            let q = Query { net: pad.net, also: None, sources: &s, targets: &t, profile: profile(&r, 2), rules: &r, soft: None, via_in: None, history: None, free: &[], arrive: None };
            assert!(!walled_in(c, &w, &q, pad.center, &layers, &t), "{} called walled in", board.pad_name(i));
            checked += 1;
        }
        assert!(checked >= 20, "only {checked} U1 pins checked");
        drop(guide);
        for &i in &u1.pads {
            let pad = &board.pads[i];
            let Some(&other) = (0..board.pads.len()).collect::<Vec<_>>().iter().find(|&&o| o != i && pad.net != NO_NET && board.pads[o].net == pad.net && !u1.pads.contains(&o)) else { continue };
            let layers: Vec<usize> = pad.layers.iter().copied().filter(|l| w.route_layers.contains(l)).collect();
            if layers.is_empty() {
                continue;
            }
            let s = [Terminal::Point { p: pad.center, layers }];
            let t = [Terminal::Point { p: board.pads[other].center, layers: board.pads[other].layers.iter().copied().filter(|l| w.route_layers.contains(l)).collect() }];
            let q = Query { net: pad.net, also: None, sources: &s, targets: &t, profile: profile(&r, 2), rules: &r, soft: None, via_in: None, history: None, free: &[], arrive: None };
            let mut g = w.guide.borrow_mut();
            let tb = g.prepare(&w, &q, (-1e12, -1e12, 1e12, 1e12)).unwrap();
            assert!(g.cost(tb, &w, &r, pad.center.into(), pad.layers[0]).is_finite(), "{} closed on the coarse map", board.pad_name(i));
        }
    }
}