AI Flow

//! Post-route clean-up of a plan (issue #39, reply 1): staircase traces become clean 45 degree runs.
//!
//! A grid search, or an AI writing a path point by point, can leave a diagonal run as a staircase
//! of tiny alternating horizontal and vertical segments. They are electrically fine but add
//! vertices and acid traps and look machine-made. For every path of a plan:
//! 1. collinear consecutive segments are merged into one;
//! 2. a staircase (three or more consecutive axis-aligned segments, each no longer than
//!    STAIR_FACTOR x the track width, alternating between horizontal and vertical) is replaced by
//!    one 45 degree segment plus at most one orthogonal leg between the same end points, only when
//!    the replacement keeps clearance by the router's own obstacle data (other nets' pads, routes,
//!    fixed copper, planeUnder regions and the board edge, dilated exactly as the search dilates
//!    them); otherwise the staircase is left as it is;
//! 3. collinear segments are merged again.
//! Pads, layer changes and the path's ends are never moved. The gate's DRC then runs on the
//! changed copper as on any plan.
//!
//! `staircases` and `board_staircases` find what is left (a warning in the gate).

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

use aiflow_board::{Board, Pt, B_CU, F_CU};
use serde_json::{json, Value};

use crate::{slop, Router};

/// A staircase step is at most this many track widths long.
pub const STAIR_FACTOR: f64 = 2.0;
/// A staircase has at least this many steps.
pub const STAIR_MIN_STEPS: usize = 3;

const EPS: f64 = 1e-6;

fn axis(a: Pt, b: Pt) -> Option<bool> {
    let (dx, dy) = ((b.0 - a.0).abs(), (b.1 - a.1).abs());
    if dx < EPS && dy < EPS { None } else if dy < EPS { Some(true) } else if dx < EPS { Some(false) } else { None }
}

fn len(a: Pt, b: Pt) -> f64 { (b.0 - a.0).hypot(b.1 - a.1) }

/// Staircase runs in a polyline: (first segment index, number of segments).
pub fn staircases(pts: &[Pt], width: f64) -> Vec<(usize, usize)> {
    let max = STAIR_FACTOR * width + EPS;
    let mut out = Vec::new();
    let n = pts.len();
    let mut j = 0;
    while j + 1 < n {
        let mut m = j;
        let mut last: Option<bool> = None;
        while m + 1 < n {
            let Some(h) = axis(pts[m], pts[m + 1]) else { break };
            if len(pts[m], pts[m + 1]) > max || last == Some(h) { break; }
            last = Some(h);
            m += 1;
        }
        let steps = m - j;
        if steps >= STAIR_MIN_STEPS { out.push((j, steps)); j = m; } else { j += 1; }
    }
    out
}

/// Drop free interior points that sit on a straight run (same direction in and out).
fn merge_collinear(pts: &mut Vec<Pt>, free: &mut Vec<bool>) -> usize {
    let mut removed = 0;
    let mut i = 1;
    while i + 1 < pts.len() {
        let (a, b, c) = (pts[i - 1], pts[i], pts[i + 1]);
        let (ux, uy, vx, vy) = (b.0 - a.0, b.1 - a.1, c.0 - b.0, c.1 - b.1);
        let cross = ux * vy - uy * vx;
        let dot = ux * vx + uy * vy;
        let scale = (ux.hypot(uy) * vx.hypot(vy)).max(1e-12);
        if free[i] && (cross / scale).abs() < 1e-6 && dot > 0.0 {
            pts.remove(i); free.remove(i); removed += 1;
        } else { i += 1; }
    }
    removed
}

/// The two 45 degree candidates between a and b: diagonal first, or leg first. A pure diagonal or
/// a straight line has one.
pub fn replacements(a: Pt, b: Pt) -> Vec<Vec<Pt>> {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let d = dx.abs().min(dy.abs());
    if d < EPS || (dx.abs() - dy.abs()).abs() < EPS { return vec![vec![a, b]]; }
    let (sx, sy) = (dx.signum() * d, dy.signum() * d);
    vec![vec![a, (a.0 + sx, a.1 + sy), b], vec![a, (b.0 - sx, b.1 - sy), b]]
}

#[derive(Debug, Default, Clone, Copy)]
pub struct Counts { pub merged: usize, pub replaced: usize, pub kept: usize }

/// Simplify one chain (its first and last points and every non-free point stay where they are).
/// `clear(a, b)` says whether a new segment keeps clearance.
pub fn simplify_chain(pts: &[Pt], free: &[bool], width: f64, clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, Counts) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let mut c = Counts { merged: merge_collinear(&mut p, &mut f), ..Default::default() };
    let mut j = 0;
    loop {
        let runs = staircases(&p, width);
        let Some(&(s, k)) = runs.iter().find(|(s, _)| *s >= j) else { break };
        let (a, b) = (p[s], p[s + k]);
        // only free points inside the run may go
        if !(s + 1..s + k).all(|i| f[i]) { c.kept += 1; j = s + 1; continue; }
        match replacements(a, b).into_iter().find(|cand| cand.windows(2).all(|w| clear(w[0], w[1]))) {
            Some(cand) => {
                let mid: Vec<Pt> = cand[1..cand.len() - 1].to_vec();
                let nm = mid.len();
                p.splice(s + 1..s + k, mid);
                f.splice(s + 1..s + k, std::iter::repeat(true).take(nm));
                c.replaced += 1;
                j = s + 1;
            }
            None => { c.kept += 1; j = s + k; }
        }
    }
    c.merged += merge_collinear(&mut p, &mut f);
    (p, f, c)
}

/// A chamfer leg is at most this many track widths (and half of either leg it cuts).
pub const CHAMFER_FACTOR: f64 = 3.0;
/// A wiggle is a sideways step no longer than this (issue #127's route_fig.py definition).
pub const JOG_MM: f64 = 1.0;

fn unit(a: Pt, b: Pt) -> Pt { let l = len(a, b).max(1e-12); ((b.0 - a.0) / l, (b.1 - a.1) / l) }
fn turn_deg(a: Pt, b: Pt, c: Pt) -> f64 { let (u, v) = (unit(a, b), unit(b, c)); (u.0 * v.1 - u.1 * v.0).atan2(u.0 * v.0 + u.1 * v.1).to_degrees() }
fn on45(a: Pt, b: Pt) -> bool { let ang = (b.1 - a.1).atan2(b.0 - a.0).to_degrees().rem_euclid(45.0); ang.min(45.0 - ang) < 0.5 }
fn right(t: f64) -> bool { (t.abs() - 90.0).abs() < 0.5 }

#[derive(Debug, Default, Clone, Copy)]
pub struct Smooth { pub chamfered: usize, pub jogs: usize, pub kept: usize, pub squared: usize, pub tightened: usize }

/// How many corners of 90 degrees or sharper a run of points makes, with the points before and after it.
fn hard_corners(before: Option<Pt>, run: &[Pt], after: Option<Pt>) -> usize {
    let mut all: Vec<Pt> = before.into_iter().collect();
    all.extend_from_slice(run);
    all.extend(after);
    all.windows(3).filter(|w| turn_deg(w[0], w[1], w[2]).abs() > 60.0).count()
}

/// Issue #127: a segment off every multiple of 45 degrees comes from a pad that is not on the grid.
/// It becomes one straight leg and one 45 degree leg with a new corner between them, the straight leg
/// at the pad where that end is one, wherever `clear` passes both legs.
pub fn square_segments(pts: &[Pt], free: &[bool], clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, usize) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let mut done = 0;
    let mut i = 0;
    while i + 1 < p.len() {
        let (a, b) = (p[i], p[i + 1]);
        if on45(a, b) || len(a, b) < EPS { i += 1; continue; }
        let mut cands = replacements(a, b);
        // replacements gives the diagonal first: that leaves the straight leg at b, the wrong way round for a pad at a
        if !f[i] && f[i + 1] { cands.reverse(); }
        // the shape with the fewer hard corners against its neighbours wins; the order above breaks a tie
        let hard = |c: &Vec<Pt>| hard_corners(if i > 0 { Some(p[i - 1]) } else { None }, c, p.get(i + 2).copied());
        cands.sort_by_key(hard);
        match cands.into_iter().find(|c| c.windows(2).all(|w| clear(w[0], w[1]))) {
            Some(c) if c.len() == 3 => { p.insert(i + 1, c[1]); f.insert(i + 1, true); done += 1; i += 2; }
            _ => { i += 1; }
        }
    }
    (p, f, done)
}

/// Wiggles in a polyline, as the route-quality report counts them: a segment of at most JOG_MM whose
/// two end turns go opposite ways.
fn wiggles_in(p: &[Pt]) -> usize {
    (1..p.len().saturating_sub(2)).filter(|&i| {
        let d = len(p[i], p[i + 1]);
        if d < EPS || d > JOG_MM + EPS { return false; }
        let (t1, t2) = (turn_deg(p[i - 1], p[i], p[i + 1]), turn_deg(p[i], p[i + 1], p[i + 2]));
        t1.abs() >= 1.0 && t2.abs() >= 1.0 && t1.signum() != t2.signum()
    }).count()
}

fn path_len(p: &[Pt]) -> f64 { p.windows(2).map(|w| len(w[0], w[1])).sum() }

/// A direction snapped to the nearest multiple of 45 degrees, when it is within half a degree of one.
fn snap45(u: Pt) -> Option<Pt> {
    let ang = u.1.atan2(u.0).to_degrees();
    let k = (ang / 45.0).round();
    if (ang - k * 45.0).abs() > 0.5 { return None; }
    let r = (k * 45.0).to_radians();
    let c = |v: f64| if v.abs() < 1e-9 { 0.0 } else { v };
    Some((c(r.cos()), c(r.sin())))
}

/// Issue #127: a pad at the end of a chain, with the directions a trace may leave it along and how far
/// the pad's copper reaches along each (its edge). A long pad has its long axis; a square pad both of its
/// axes; a round pad every multiple of 45 degrees. Only directions at a multiple of 45 degrees, and none
/// pointing back into its own part (an IC pin is entered from outside the package).
#[derive(Debug, Clone)]
pub struct PadEnd { pub at: Pt, pub axes: Vec<(Pt, f64)>, pub long: Pt, pub half: (f64, f64), pub round: bool }

impl PadEnd {
    /// Whether a point lies inside the pad's copper (its own rectangle or circle); its edge is outside.
    pub fn inside(&self, q: Pt) -> bool {
        let d = (q.0 - self.at.0, q.1 - self.at.1);
        if self.round { return d.0.hypot(d.1) < self.half.0 - 1e-6; }
        dot(d, self.long).abs() < self.half.0 - 1e-6 && (d.0 * self.long.1 - d.1 * self.long.0).abs() < self.half.1 - 1e-6
    }
}

/// A long pad is this much longer than wide; anything squarer may be entered along either axis.
pub const SQUARE_PAD: f64 = 1.15;

pub fn pad_end(p: &aiflow_board::Pad) -> PadEnd {
    let n = p.long_axis.0.hypot(p.long_axis.1);
    let (ax, ay) = if n > 1e-9 { (p.long_axis.0 / n, p.long_axis.1 / n) } else { (1.0, 0.0) };
    let round = p.shape == "circle";
    let mut dirs: Vec<Pt> = vec![(ax, ay), (-ax, -ay)];
    if round || p.half_long <= p.half_short * SQUARE_PAD { dirs.extend([(-ay, ax), (ay, -ax)]); }
    if round {
        let h = std::f64::consts::FRAC_1_SQRT_2;
        dirs.extend([(h, h), (h, -h), (-h, h), (-h, -h)]);
    }
    let out = (p.x - p.fp_x, p.y - p.fp_y);
    let axes = dirs.into_iter().filter_map(snap45).filter(|u| out.0 * u.0 + out.1 * u.1 >= -0.05).map(|u| {
        let along_long = (u.0 * ax + u.1 * ay).abs() > 0.5;
        let edge = p.polys.iter().flatten().map(|q| (q.0 - p.x) * u.0 + (q.1 - p.y) * u.1).fold(f64::NEG_INFINITY, f64::max);
        (u, if edge.is_finite() { edge.max(0.0) } else if along_long { p.half_long } else { p.half_short })
    }).collect();
    PadEnd { at: (p.x, p.y), axes, long: (ax, ay), half: (p.half_long, p.half_short), round }
}

/// How far along the chain a pad entry may reach to join the route again.
const ENTRY_REACH_MM: f64 = 6.0;
/// How much longer than the copper it replaces a pad entry may be.
const ENTRY_SLACK_MM: f64 = 0.5;

const DIR8: [Pt; 8] = [(1.0, 0.0), (-1.0, 0.0), (0.0, 1.0), (0.0, -1.0),
    (std::f64::consts::FRAC_1_SQRT_2, std::f64::consts::FRAC_1_SQRT_2), (std::f64::consts::FRAC_1_SQRT_2, -std::f64::consts::FRAC_1_SQRT_2),
    (-std::f64::consts::FRAC_1_SQRT_2, std::f64::consts::FRAC_1_SQRT_2), (-std::f64::consts::FRAC_1_SQRT_2, -std::f64::consts::FRAC_1_SQRT_2)];

fn dot(a: Pt, b: Pt) -> f64 { a.0 * b.0 + a.1 * b.1 }
fn add(a: Pt, b: Pt, k: f64) -> Pt { (a.0 + b.0 * k, a.1 + b.1 * k) }

/// Whether a chain that starts on a pad already leaves the pad's copper along one of its axes (or never
/// leaves it: a via or a join inside the pad).
pub fn enters_on_axis(pts: &[Pt], pad: &PadEnd) -> bool {
    let Some(e) = (0..pts.len().saturating_sub(1)).find(|&i| !pad.inside(pts[i + 1])) else { return true };
    if len(pts[e], pts[e + 1]) < EPS { return false; }
    let d = unit(pts[e], pts[e + 1]);
    pad.axes.iter().any(|&(u, _)| dot(d, u) > (0.5f64).to_radians().cos())
}

/// Issue #127: the last leg into a pad runs along the pad's own axis. The chain's first point is the pad;
/// its start is rebuilt as a straight stub from the pad out past its edge along an axis, then one leg at a
/// multiple of 45 degrees back onto the route: to a vertex of the chain, or onto one of its segments,
/// which it then follows. Candidates turn at most 45 degrees inside the new legs, have no more hard corners
/// or wiggles than the copper they replace (up to two vertices past the join) and are at most
/// ENTRY_SLACK_MM longer; they are tried shortest first; the first one `clear` passes wins. The stub's end is
/// returned fixed, so later passes keep the entry. None when the entry is already on an axis or nothing fits.
pub fn enter_on_axis(pts: &[Pt], free: &[bool], pad: &PadEnd, width: f64, clear: &mut dyn FnMut(Pt, Pt) -> bool) -> Option<(Vec<Pt>, Vec<bool>)> {
    let n = pts.len();
    if n < 2 || pad.axes.is_empty() || enters_on_axis(pts, pad) { return None; }
    let p0 = pts[0];
    // the vertices a new leg may land on: up to the first fixed one, within reach
    let mut last = 1;
    let mut reach = 0.0;
    for j in 1..n {
        reach += len(pts[j - 1], pts[j]);
        last = j;
        if !free[j] || reach > ENTRY_REACH_MM { break; }
    }
    // (new prefix from the pad, index of the chain vertex it continues from)
    let mut cands: Vec<(Vec<Pt>, usize)> = Vec::new();
    for &(u, edge) in &pad.axes {
        let t0 = edge + width / 2.0;
        // one stub and one 45: onto a vertex
        for j in 1..=last {
            let d = (pts[j].0 - p0.0, pts[j].1 - p0.1);
            let cross = u.0 * d.1 - u.1 * d.0;
            if cross.abs() < 1e-7 && dot(d, u) + EPS >= edge { cands.push((vec![p0, pts[j]], j)); continue; }
            for &v in &DIR8 {
                let det = u.0 * v.1 - u.1 * v.0;
                if det.abs() < 1e-9 { continue; }
                let (t, s) = ((d.0 * v.1 - d.1 * v.0) / det, (u.0 * d.1 - u.1 * d.0) / det);
                if t + EPS >= edge && s > EPS { cands.push((vec![p0, add(p0, u, t), pts[j]], j)); }
            }
        }
        // one stub and one 45 onto a segment k (pts[k] to pts[k + 1]), then along it; or the stub straight onto it
        for k in 1..last {
            let (a, b) = (pts[k], pts[k + 1]);
            let lk = len(a, b);
            if lk < EPS { continue; }
            let w = unit(a, b);
            let nn = (-w.1, w.0);
            let pa = (p0.0 - a.0, p0.1 - a.1);
            if dot(nn, u).abs() > 1e-9 {
                let t = -dot(nn, pa) / dot(nn, u);
                let e = add(p0, u, t);
                if t + EPS >= t0 && dot(w, (e.0 - a.0, e.1 - a.1)) < lk - EPS { cands.push((vec![p0, e, b], k + 1)); }
            }
            for &v in &DIR8 {
                let nv = dot(nn, v);
                if nv.abs() < 1e-9 || (u.0 * v.1 - u.1 * v.0).abs() < 1e-9 { continue; }
                // s(t) = s0 + s1 t puts the leg's end on the segment's line; l(t) = l0 + l1 t is where along it
                let (s0, s1) = (-dot(nn, pa) / nv, -dot(nn, u) / nv);
                let (l0, l1) = (dot(w, pa) + s0 * dot(w, v), dot(w, u) + s1 * dot(w, v));
                let (mut lo, mut hi) = (t0, f64::INFINITY);
                let mut ok = true;
                for (c, m) in [(s0, s1), (lk - EPS - l0, -l1)] {
                    if m.abs() < 1e-12 { if c < 0.0 { ok = false; } } else if m > 0.0 { lo = lo.max(-c / m); } else { hi = hi.min(-c / m); }
                }
                if !ok || lo > hi + 1e-12 { continue; }
                let s = s0 + s1 * lo;
                let e = add(p0, u, lo);
                let f = add(e, v, s);
                cands.push((if s < EPS { vec![p0, e, b] } else { vec![p0, e, f, b] }, k + 1));
            }
        }
    }
    // the comparison runs two vertices past the join, so a wiggle made just beyond it counts
    let window = |pre: &[Pt], keep: usize| -> Vec<Pt> { let mut w = pre.to_vec(); w.extend(pts.iter().skip(keep + 1).take(2).copied()); w };
    let mut scored: Vec<((usize, usize, f64), Vec<Pt>, usize)> = cands.into_iter().filter_map(|(mut pre, keep)| {
        pre.dedup_by(|a, b| len(*a, *b) < EPS);
        if pre.len() < 2 || pre.windows(2).any(|w| !on45(w[0], w[1]) && w[1] != pts[keep]) { return None; }
        // the stub's end is fixed from here on, so nothing would cut a hard corner there later: none at all inside the new legs
        if pre.windows(3).any(|w| turn_deg(w[0], w[1], w[2]).abs() > 46.0) { return None; }
        let (old, new) = (window(&pts[..=keep], keep), window(&pre, keep));
        let (ho, hn) = (hard_corners(None, &old, None), hard_corners(None, &new, None));
        let (wo, wn) = (wiggles_in(&old), wiggles_in(&new));
        let (lo, ln) = (path_len(&pts[..=keep]), path_len(&pre));
        (hn <= ho && wn <= wo && ln <= lo + ENTRY_SLACK_MM).then_some(((hn, wn, ln), pre, keep))
    }).collect();
    scored.sort_by(|a, b| a.0.0.cmp(&b.0.0).then(a.0.1.cmp(&b.0.1)).then(a.0.2.total_cmp(&b.0.2)));
    for (_, pre, keep) in scored {
        if !pre.windows(2).all(|w| clear(w[0], w[1])) { continue; }
        let mut p = pre.clone();
        let mut f: Vec<bool> = (0..pre.len()).map(|q| q >= 2).collect();
        // the continuing vertex keeps its own state (the prefix's last point is pts[keep])
        p.pop(); f.pop();
        p.extend_from_slice(&pts[keep..]);
        f.extend_from_slice(&free[keep..]);
        if p.len() >= 2 && f.len() == p.len() { f[1] = false; }
        return Some((p, f));
    }
    None
}

/// Issue #127: both pad ends of a chain entered on their axes where they can be (see enter_on_axis).
pub fn enter_pads(pts: &[Pt], free: &[bool], start: Option<&PadEnd>, end: Option<&PadEnd>, width: f64, clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, usize) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let mut done = 0;
    if let Some(pad) = start {
        if let Some((np, nf)) = enter_on_axis(&p, &f, pad, width, clear) { p = np; f = nf; done += 1; }
    }
    if let Some(pad) = end {
        p.reverse(); f.reverse();
        if let Some((np, nf)) = enter_on_axis(&p, &f, pad, width, clear) { p = np; f = nf; done += 1; }
        p.reverse(); f.reverse();
    }
    (p, f, done)
}

/// Issue #127: the wiggles the pull and the step leave are mostly short legs between two parallel runs (a
/// 45 degree lane change, or a zigzag of straight and diagonal legs). A free corner is flipped across the
/// parallelogram of its two legs (the same two legs in the other order, the same length): the short leg
/// slides along until its neighbour runs on in the same direction and the two merge. A flip is kept only
/// when `clear` passes both new legs, it adds no wiggle and no hard corner, and it removes a wiggle or a
/// corner. Only chains with a wiggle are touched; fixed points stay. `keep_ends` (start, end) keeps the
/// direction of the chain's first or last leg: a pad entered on its axis, or an end another path meets
/// (their turn there is a corner this chain cannot see).
pub fn slide_jogs(pts: &[Pt], free: &[bool], keep_ends: (bool, bool), clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, usize) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let score = |p: &[Pt]| (wiggles_in(p), hard_corners(None, p, None), p.len());
    let mut done = 0;
    let mut guard = 0;
    'outer: while guard < 4 * pts.len() + 8 {
        guard += 1;
        let s0 = score(&p);
        if s0.0 == 0 { break; }
        for i in 1..p.len().saturating_sub(1) {
            if !f[i] || (keep_ends.0 && i == 1) || (keep_ends.1 && i + 2 == p.len()) { continue; }
            let q = (p[i - 1].0 + p[i + 1].0 - p[i].0, p[i - 1].1 + p[i + 1].1 - p[i].1);
            if len(q, p[i]) < EPS { continue; }
            let (mut np, mut nf) = (p.clone(), f.clone());
            np[i] = q;
            merge_collinear(&mut np, &mut nf);
            let s1 = score(&np);
            if s1.0 > s0.0 || s1.1 > s0.1 || (s1.0 == s0.0 && s1.2 >= s0.2) { continue; }
            if !(clear(p[i - 1], q) && clear(q, p[i + 1])) { continue; }
            p = np;
            f = nf;
            done += 1;
            continue 'outer;
        }
        break;
    }
    (p, f, done)
}

/// A net is a tree: another path of the net can end anywhere along this one, and a pad of the net can
/// sit under it. Those joins hold the net together, so they are made fixed points before anything moves:
/// a vertex at the join is fixed, a join along a segment gets a fixed vertex of its own on that line.
pub fn pin_joins(pts: &[Pt], free: &[bool], joins: &[(Pt, f64)]) -> (Vec<Pt>, Vec<bool>) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    for &(j, reach) in joins {
        if let Some(i) = p.iter().position(|q| len(*q, j) <= reach) { f[i] = false; continue; }
        let hit = p.windows(2).enumerate().find_map(|(i, w)| {
            let (dx, dy) = (w[1].0 - w[0].0, w[1].1 - w[0].1);
            let l2 = dx * dx + dy * dy;
            if l2 < EPS { return None; }
            let t = ((j.0 - w[0].0) * dx + (j.1 - w[0].1) * dy) / l2;
            let q = (w[0].0 + t * dx, w[0].1 + t * dy);
            ((0.0..=1.0).contains(&t) && len(q, j) <= reach).then_some((i, q))
        });
        if let Some((i, q)) = hit { p.insert(i + 1, q); f.insert(i + 1, false); }
    }
    (p, f)
}

/// How far a pull may look: up to this many segments replaced at once.
const TIGHTEN_SPAN: usize = 6;

/// Issue #127: the search stops at the first path that joins, so it leaves short sideways steps and
/// detours. A run of free points is replaced by one 45 degree leg and one straight leg between the same
/// ends when that is no longer, has fewer corners, adds no corner of 90 degrees or sharper and `clear`
/// passes it. Fixed points stay; repeats until nothing moves.
pub fn tighten_chain(pts: &[Pt], free: &[bool], clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, usize) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let mut done = 0;
    let mut moved = true;
    while moved {
        moved = false;
        let mut i = 0;
        while i + 2 < p.len() {
            let top = (i + TIGHTEN_SPAN).min(p.len() - 1);
            for k in (i + 2..=top).rev() {
                if !(i + 1..k).all(|q| f[q]) { continue; }
                let was: f64 = p[i..=k].windows(2).map(|w| len(w[0], w[1])).sum();
                let hit = replacements(p[i], p[k]).into_iter().find(|c| {
                    let long: f64 = c.windows(2).map(|w| len(w[0], w[1])).sum();
                    if long > was + EPS || c.len() >= k - i + 1 { return false; }
                    // never trades a short step for a hard corner
                    let (before, after) = (i.checked_sub(1).map(|q| p[q]), p.get(k + 1).copied());
                    if hard_corners(before, c, after) > hard_corners(before, &p[i..=k], after) { return false; }
                    // nor makes a hard corner at a fixed point (a pad's entry stub), where nothing can cut it later
                    if let Some(b) = before.filter(|_| !f[i]) { if turn_deg(b, c[0], c[1]).abs() > 60.0 && turn_deg(b, p[i], p[i + 1]).abs() <= 60.0 { return false; } }
                    if let Some(a) = after.filter(|_| !f[k]) { let m = c.len(); if turn_deg(c[m - 2], c[m - 1], a).abs() > 60.0 && turn_deg(p[k - 1], p[k], a).abs() <= 60.0 { return false; } }
                    c.windows(2).all(|w| clear(w[0], w[1]))
                });
                if let Some(c) = hit {
                    let mid: Vec<Pt> = c[1..c.len() - 1].to_vec();
                    let n = mid.len();
                    p.splice(i + 1..k, mid);
                    f.splice(i + 1..k, std::iter::repeat(true).take(n));
                    done += 1;
                    moved = true;
                    break;
                }
            }
            i += 1;
        }
    }
    (p, f, done)
}

/// Issue #127: on a chain whose legs already run at multiples of 45 degrees, a short sideways step
/// (two opposite right angles around a segment of at most JOG_MM) becomes one 45 degree step, and
/// every other right-angle corner at a free point is cut into two 45 degree turns, each only where
/// `clear` passes the new diagonal (the shortened legs lie on the old copper). Fixed points stay.
pub fn smooth_chain(pts: &[Pt], free: &[bool], width: f64, clear: &mut dyn FnMut(Pt, Pt) -> bool) -> (Vec<Pt>, Vec<bool>, Smooth) {
    let (mut p, mut f) = (pts.to_vec(), free.to_vec());
    let mut c = Smooth::default();
    let mut i = 1;
    while i + 2 < p.len() {
        let d = len(p[i], p[i + 1]);
        let (t1, t2) = (turn_deg(p[i - 1], p[i], p[i + 1]), turn_deg(p[i], p[i + 1], p[i + 2]));
        if f[i] && f[i + 1] && d > EPS && d <= JOG_MM + EPS && right(t1) && right(t2) && t1.signum() != t2.signum() && on45(p[i - 1], p[i]) && on45(p[i + 1], p[i + 2]) {
            let (ui, uo) = (unit(p[i - 1], p[i]), unit(p[i + 1], p[i + 2]));
            let back = (p[i].0 - ui.0 * d, p[i].1 - ui.1 * d);
            let fwd = (p[i + 1].0 + uo.0 * d, p[i + 1].1 + uo.1 * d);
            if len(p[i - 1], p[i]) > d + EPS && clear(back, p[i + 1]) { p[i] = back; c.jogs += 1; i += 2; continue; }
            if len(p[i + 1], p[i + 2]) > d + EPS && clear(p[i], fwd) { p[i + 1] = fwd; c.jogs += 1; i += 2; continue; }
            c.kept += 1;
        }
        i += 1;
    }
    let mut i = 1;
    while i + 1 < p.len() {
        let (a, b, n) = (p[i - 1], p[i], p[i + 1]);
        if !(f[i] && right(turn_deg(a, b, n)) && on45(a, b) && on45(b, n)) { i += 1; continue; }
        let cmax = (CHAMFER_FACTOR * width).min(len(a, b) / 2.0).min(len(b, n) / 2.0);
        let (ui, uo) = (unit(a, b), unit(b, n));
        let done = [cmax, cmax / 2.0].into_iter().filter(|&k| k >= width / 2.0 - EPS).find_map(|k| {
            let (q1, q2) = ((b.0 - ui.0 * k, b.1 - ui.1 * k), (b.0 + uo.0 * k, b.1 + uo.1 * k));
            clear(q1, q2).then_some((q1, q2))
        });
        match done {
            Some((q1, q2)) => { p.splice(i..=i, [q1, q2]); f.splice(i..=i, [true, true]); c.chamfered += 1; i += 2; }
            None => { c.kept += 1; i += 1; }
        }
    }
    merge_collinear(&mut p, &mut f);
    (p, f, c)
}

impl Router {
    /// The router's own obstacle check for a straight copper segment of `width` on layer `l`:
    /// every other net's pad, stub, route, via and fixed copper, a foreign planeUnder region, and
    /// the board edge, dilated by the clearance plus half the width plus the grid slop.
    pub fn segment_clear(&mut self, net_name: &str, l: usize, a: Pt, b: Pt, width: f64) -> bool {
        let g = self.grid.clone();
        let nid = self.net_ids.get(net_name).map(|&k| k as i16).unwrap_or(-3);
        let clr = self.rules.clearance.max(self.rules.net_clearance.get(net_name).copied().unwrap_or(0.0));
        let r = clr + width / 2.0 + slop();
        let r_big = self.big_clr_val + width / 2.0 + slop();
        let inside = self.inside_for(width).clone();
        for c in g.segment_cells(a, b, 0.0, Some(1e-6)) {
            if !inside.bits[c] { return false; }
        }
        for c in g.segment_cells(a, b, r, Some(0.0)) {
            let other = |v: i16| v != -1 && v != nid;
            if other(self.pad_raw[l][c]) || other(self.route_raw[l][c]) || other(self.fixed_raw[l][c]) || self.kept_from(net_name, l, c) { return false; }
        }
        if r_big > r {
            for c in g.segment_cells(a, b, r_big, Some(0.0)) {
                let p = self.pad_raw[l][c];
                if self.big_clr[l].bits[c] && p != -1 && p != nid { return false; }
            }
        }
        true
    }

    fn stamp_segment(&mut self, net_name: &str, l: usize, a: Pt, b: Pt, width: f64) {
        let Some(&k) = self.net_ids.get(net_name) else { return };
        let g = self.grid.clone();
        for c in g.segment_cells(a, b, width / 2.0, Some(1e-6)) { self.route_raw[l][c] = k as i16; }
    }
}

/// A plan waypoint resolved: where it is, the layer it sets, and whether it may be removed.
struct Wp { xy: Pt, layer: Option<String>, free: bool }

fn resolve(board: &Board, v: &Value) -> Option<Wp> {
    if let Some(k) = v.as_str() { let p = board.pad_by_key(k)?; return Some(Wp { xy: (p.x, p.y), layer: None, free: false }); }
    if let Some(a) = v.as_array() { return Some(Wp { xy: (a.first()?.as_f64()?, a.get(1)?.as_f64()?), layer: None, free: true }); }
    let o = v.as_object()?;
    let layer = o.get("layer").and_then(|l| l.as_str()).map(str::to_string);
    if let Some(k) = o.get("pad").and_then(|p| p.as_str()) { let p = board.pad_by_key(k)?; return Some(Wp { xy: (p.x, p.y), layer, free: false }); }
    Some(Wp { xy: (o.get("x")?.as_f64()?, o.get("y")?.as_f64()?), free: layer.is_none(), layer })
}

fn round(v: f64) -> f64 { (v * 1e6).round() / 1e6 }

/// Simplify every path of a plan in place; returns the report (vertex count per net before and
/// after, staircases replaced and kept, collinear points merged).
pub fn simplify_plan(router: &mut Router, plan: &mut [Value]) -> Value {
    let mut per_net: BTreeMap<String, (usize, usize)> = BTreeMap::new();
    let mut total = Counts::default();
    let mut smooth = Smooth::default();
    // every point another path of a net can join at, per net: each path's ends and layer changes
    let mut path_joins: HashMap<String, Vec<Vec<Pt>>> = HashMap::new();
    for e in plan.iter() {
        let net = e["net"].as_str().unwrap_or("").to_string();
        let paths: Vec<Value> = if e["paths"].is_array() { e["paths"].as_array().cloned().unwrap_or_default() } else if e["points"].is_array() { vec![e["points"].clone()] } else { continue };
        for path in paths {
            let raw = path.as_array().cloned().unwrap_or_default();
            let n = raw.len();
            let ends: Vec<Pt> = raw.iter().enumerate().filter_map(|(q, v)| {
                let w = resolve(&router.board, v)?;
                (q == 0 || q + 1 == n || w.layer.is_some()).then_some(w.xy)
            }).collect();
            path_joins.entry(net.clone()).or_default().push(ends);
        }
    }
    let pad_joins: HashMap<String, Vec<(Pt, f64)>> = router.board.pads.iter().fold(HashMap::new(), |mut m, p| {
        m.entry(p.net.clone()).or_insert_with(Vec::new).push(((p.x, p.y), p.size.0.min(p.size.1) / 2.0));
        m
    });
    // issue #127: the pads of each net, to find a chain that ends on one
    let net_pads: HashMap<String, Vec<usize>> = router.board.pads.iter().enumerate().fold(HashMap::new(), |mut m, (k, p)| {
        m.entry(p.net.clone()).or_insert_with(Vec::new).push(k);
        m
    });
    let mut entered = 0usize;
    let mut slid = 0usize;
    let mut path_no: HashMap<String, usize> = HashMap::new();
    for e in plan.iter_mut() {
        let net = e["net"].as_str().unwrap_or("").to_string();
        // a coupled impedance pair keeps its shape: both halves would have to move together
        let pair = router.rules.impedance.contains_key(&net);
        let width = e["width"].as_f64().unwrap_or(0.25);
        let entry_layer = e["layer"].as_str().map(str::to_string);
        let key = if e["paths"].is_array() { "paths" } else if e["points"].is_array() { "points" } else { continue };
        let paths: Vec<Value> = if key == "paths" { e["paths"].as_array().cloned().unwrap_or_default() } else { vec![e["points"].clone()] };
        let mut out_paths = Vec::new();
        for path in paths {
            let this_path = { let n = path_no.entry(net.clone()).or_insert(0); *n += 1; *n - 1 };
            let Some(raw) = path.as_array().cloned() else { out_paths.push(path); continue };
            // the joins this path must keep: where the net's other paths meet it, and the net's pads under it
            let mut joins: Vec<(Pt, f64)> = path_joins.get(&net).into_iter().flatten().enumerate().filter(|(q, _)| *q != this_path).flat_map(|(_, ends)| ends.iter().map(|&j| (j, width / 2.0))).collect();
            joins.extend(pad_joins.get(&net).into_iter().flatten().map(|&(j, r)| (j, r + width / 2.0)));
            let rs: Vec<Option<Wp>> = raw.iter().map(|v| resolve(&router.board, v)).collect();
            let entry = per_net.entry(net.clone()).or_insert((0, 0));
            entry.0 += raw.len();
            if rs.iter().any(|w| w.is_none()) || raw.len() < 3 { entry.1 += raw.len(); out_paths.push(Value::Array(raw)); continue; }
            let rs: Vec<Wp> = rs.into_iter().map(Option::unwrap).collect();
            // the layer of the segment leaving each waypoint, as plan_to_copper reads it
            let mut layer = entry_layer.clone().or_else(|| rs[0].layer.clone()).unwrap_or_else(|| {
                // issue #139: no layer named, a bottom part's pad first: B.Cu, as plan_to_copper reads it
                let pad_of = |v: &Value| v.as_str().or_else(|| v.get("pad").and_then(|p| p.as_str())).and_then(|k| router.board.pad_by_key(k));
                Board::path_start_layer(raw.iter().zip(&rs).map(|(v, w)| (pad_of(v), w.layer.is_some()))).into()
            });
            let mut seg_layer = Vec::with_capacity(rs.len());
            let mut anchor = vec![false; rs.len()];
            for (i, w) in rs.iter().enumerate() {
                let nxt = w.layer.clone().unwrap_or_else(|| layer.clone());
                if nxt != layer { anchor[i] = true; layer = nxt; }
                seg_layer.push(layer.clone());
            }
            let mut new_path: Vec<Value> = vec![raw[0].clone()];
            let mut i = 0;
            while i + 1 < rs.len() {
                // a chain: from i to the next anchor or layer change (exclusive of what follows it)
                let mut k = i + 1;
                while k + 1 < rs.len() && rs[k].free && !anchor[k] && seg_layer[k] == seg_layer[i] { k += 1; }
                let l = match seg_layer[i].as_str() { "F.Cu" => Some(F_CU), "B.Cu" => Some(B_CU), _ => None };
                let pts: Vec<Pt> = rs[i..=k].iter().map(|w| w.xy).collect();
                let free: Vec<bool> = (i..=k).map(|q| q != i && q != k).collect();
                // issue #127: a chain end on a pad of the net, on this layer. Where exactly one other path
                // ends on the same pad, the two meet there as a corner: its turn is not this chain's to change.
                let others_at = |at: Pt| path_joins.get(&net).into_iter().flatten().enumerate().filter(|(q, _)| *q != this_path).flat_map(|(_, ends)| ends.iter()).filter(|j| len(**j, at) < 1e-4).count();
                let pad_at = |at: Pt| -> Option<PadEnd> {
                    let l = l?;
                    net_pads.get(&net).into_iter().flatten().map(|&q| &router.board.pads[q]).find(|p| len((p.x, p.y), at) < 1e-4 && (p.thru || p.on_layer(l))).map(pad_end)
                };
                // only an end the plan names as a pad (not a via or a join that happens to sit on one)
                let names_pad = |v: &Value| v.is_string() || v.get("pad").is_some();
                let (start_pad, end_pad) = if pair { (None, None) } else { (pad_at(pts[0]).filter(|_| names_pad(&raw[i])), pad_at(pts[pts.len() - 1]).filter(|_| names_pad(&raw[k]))) };
                // a pad end met there by exactly one other path is not rebuilt (their turn at the pad is a corner)
                let shared = (others_at(pts[0]) == 1, others_at(pts[pts.len() - 1]) == 1);
                let (start_any, end_any) = (start_pad.clone(), end_pad.clone());
                let (start_pad, end_pad) = (start_pad.filter(|_| !shared.0), end_pad.filter(|_| !shared.1));
                if let (Some(l), true) = (l, k - i >= 2 || start_pad.is_some() || end_pad.is_some()) {
                    let mut accepted: Vec<(Pt, Pt)> = Vec::new();
                    let (np, c) = {
                        let r = &mut *router;
                        let net_s = net.clone();
                        let mut chk = |a: Pt, b: Pt| { let ok = r.segment_clear(&net_s, l, a, b, width); if ok { accepted.push((a, b)); } ok };
                        let (pts, free) = pin_joins(&pts, &free, &joins);
                        let (np, nf, c) = simplify_chain(&pts, &free, width, &mut chk);
                        if pair { (np, c) } else {
                            let (ep, ef, en) = enter_pads(&np, &nf, start_pad.as_ref(), end_pad.as_ref(), width, &mut chk);
                            let (qp, qf, squared) = square_segments(&ep, &ef, &mut chk);
                            let (tp, tf, tightened) = tighten_chain(&qp, &qf, &mut chk);
                            // a sliding jog keeps an end's leg where it meets exactly one other path's (their turn is a corner
                            // this chain cannot see) or where it enters a pad on the pad's axis
                            let rev: Vec<Pt> = tp.iter().rev().copied().collect();
                            let keep_ends = (shared.0 || start_any.as_ref().is_some_and(|p| enters_on_axis(&tp, p)), shared.1 || end_any.as_ref().is_some_and(|p| enters_on_axis(&rev, p)));
                            let (lp, lf, sl) = slide_jogs(&tp, &tf, keep_ends, &mut chk);
                            let (sp, _, sc) = smooth_chain(&lp, &lf, width, &mut chk);
                            smooth.chamfered += sc.chamfered; smooth.jogs += sc.jogs; smooth.kept += sc.kept; smooth.squared += squared; smooth.tightened += tightened;
                            entered += en; slid += sl;
                            (sp, c)
                        }
                    };
                    for (a, b) in accepted { router.stamp_segment(&net, l, a, b, width); }
                    total.merged += c.merged; total.replaced += c.replaced; total.kept += c.kept;
                    // keep original values where a point survived unchanged, new points as [x, y]
                    let orig: HashMap<(i64, i64), Value> = (i..=k).map(|q| (((rs[q].xy.0 * 1e6).round() as i64, (rs[q].xy.1 * 1e6).round() as i64), raw[q].clone())).collect();
                    for p in &np[1..] {
                        let key = ((p.0 * 1e6).round() as i64, (p.1 * 1e6).round() as i64);
                        new_path.push(orig.get(&key).cloned().unwrap_or_else(|| json!([round(p.0), round(p.1)])));
                    }
                } else {
                    new_path.extend(raw[i + 1..=k].iter().cloned());
                }
                i = k;
            }
            entry.1 += new_path.len();
            out_paths.push(Value::Array(new_path));
        }
        if key == "paths" { e["paths"] = Value::Array(out_paths); } else if let Some(p) = out_paths.into_iter().next() { e["points"] = p; }
    }
    let nets: serde_json::Map<String, Value> = per_net.iter().map(|(n, (b, a))| (n.clone(), json!({"before": b, "after": a}))).collect();
    let (b, a): (usize, usize) = per_net.values().fold((0, 0), |s, v| (s.0 + v.0, s.1 + v.1));
    json!({"verticesBefore": b, "verticesAfter": a, "staircasesReplaced": total.replaced, "staircasesKept": total.kept, "collinearMerged": total.merged, "cornersChamfered": smooth.chamfered, "segmentsSquared": smooth.squared, "runsTightened": smooth.tightened, "wigglesStepped": smooth.jogs, "smoothKept": smooth.kept, "padsEnteredOnAxis": entered, "jogsSlid": slid, "nets": nets,
        "rule": format!("staircase = {STAIR_MIN_STEPS}+ alternating 0/90 degree segments each <= {STAIR_FACTOR} x track width; replaced by a 45 degree segment plus at most one orthogonal leg only where the router's obstacle check keeps clearance. Then (not on impedance pairs) a sideways step <= {JOG_MM} mm between two opposite right angles becomes one 45 degree step, and a right-angle corner at a free point is cut into two 45 degree turns (leg <= {CHAMFER_FACTOR} x width and half of either leg), each only where the same check keeps clearance. A trace into a pad is rebuilt as a straight stub along the pad's own axis out past its edge and one 45 degree leg back onto the route (no new hard corner or wiggle, at most {ENTRY_SLACK_MM} mm longer), and a short leg between two parallel runs is slid along them (the same two legs in the other order) until it merges, both only where the same check keeps clearance")})
}

/// Staircases left in a board's copper: track chains per net and layer joined end to end through
/// points where exactly two tracks meet. One line per staircase.
pub fn board_staircases(b: &Board) -> Vec<String> {
    let tracks = b.tracks();
    let key = |p: Pt| ((p.0 * 1e4).round() as i64, (p.1 * 1e4).round() as i64);
    let mut groups: BTreeMap<(String, usize), Vec<usize>> = BTreeMap::new();
    for (i, t) in tracks.iter().enumerate() { groups.entry((t.net.clone(), t.layer)).or_default().push(i); }
    let mut out = Vec::new();
    for ((net, layer), ids) in groups {
        let mut at: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
        for &i in &ids { at.entry(key(tracks[i].a)).or_default().push(i); at.entry(key(tracks[i].b)).or_default().push(i); }
        let mut used = std::collections::HashSet::new();
        for &start in &ids {
            if used.contains(&start) { continue; }
            // walk to one end of the chain, then collect forward
            let (mut cur, mut from) = (start, key(tracks[start].a));
            let mut guard = 0;
            loop {
                let next = at.get(&from).filter(|v| v.len() == 2).and_then(|v| v.iter().find(|&&t| t != cur).copied());
                match next { Some(n) if n != start && guard < ids.len() => { let t = &tracks[n]; from = if key(t.a) == from { key(t.b) } else { key(t.a) }; cur = n; guard += 1; } _ => break }
            }
            // cur is an end track, `from` its outer end; walk the other way
            let mut pts: Vec<Pt> = Vec::new();
            let mut width = f64::INFINITY;
            let (mut t_id, mut end) = (cur, from);
            loop {
                if !used.insert(t_id) { break; }
                let t = &tracks[t_id];
                let (p, q) = if key(t.a) == end { (t.a, t.b) } else { (t.b, t.a) };
                if pts.is_empty() { pts.push(p); }
                pts.push(q);
                width = width.min(t.width);
                end = key(q);
                match at.get(&end).filter(|v| v.len() == 2).and_then(|v| v.iter().find(|&&x| x != t_id).copied()) { Some(n) => t_id = n, None => break }
            }
            for (s, k) in staircases(&pts, width) {
                out.push(format!("{net} on {}: a {k}-step staircase from ({:.3}, {:.3}) to ({:.3}, {:.3})", aiflow_board::LAYER_NAMES[layer], pts[s].0, pts[s].1, pts[s + k].0, pts[s + k].1));
            }
        }
    }
    out
}

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

    fn stair(n: usize, step: f64, from: Pt) -> Vec<Pt> {
        let mut p = vec![from];
        for k in 0..n { let l = *p.last().unwrap(); p.push(if k % 2 == 0 { (l.0 + step, l.1) } else { (l.0, l.1 + step) }); }
        p
    }

    #[test]
    fn tightening_adds_no_hard_corner() {
        // the shortcut from (0,0) to (2,1) would meet the next leg, which runs back up, at a hard corner
        let pts = [(0.0, 0.0), (1.0, 0.0), (1.0, 0.5), (2.0, 0.5), (2.0, 1.0), (2.0, 4.0)];
        let free = [false, true, true, true, true, false];
        let (p, _, _) = tighten_chain(&pts, &free, &mut |_, _| true);
        let n = |v: &[Pt]| hard_corners(None, v, None);
        assert!(n(&p) <= n(&pts), "{p:?}");
    }
    #[test]
    fn a_join_stays_where_the_other_path_meets_it() {
        let pts = [(0.0, 0.0), (2.0, 0.0), (2.0, 0.5), (3.0, 0.5), (3.0, 0.0), (6.0, 0.0)];
        let free = [false, true, true, true, true, false];
        // on a vertex
        let (p, f) = pin_joins(&pts, &free, &[((2.0, 0.5), 0.1)]);
        assert_eq!((p.len(), f[2]), (6, false));
        let (t, _, _) = tighten_chain(&p, &f, &mut |_, _| true);
        assert!(t.contains(&(2.0, 0.5)), "{t:?}");
        // along a segment: a fixed vertex of its own, on the line, that smoothing and pulling both keep
        let (p, f) = pin_joins(&pts, &free, &[((5.0, 0.05), 0.1)]);
        assert_eq!(p.len(), 7);
        assert!(p.contains(&(5.0, 0.0)) && !f[p.iter().position(|q| *q == (5.0, 0.0)).unwrap()]);
        let (t, _, _) = tighten_chain(&p, &f, &mut |_, _| true);
        assert!(t.contains(&(5.0, 0.0)), "{t:?}");
        // too far away to touch: nothing changes
        assert_eq!(pin_joins(&pts, &free, &[((5.0, 1.0), 0.1)]).0.len(), 6);
    }
    #[test]
    fn an_off_angle_entry_gets_a_straight_leg_at_the_pad() {
        let free = [false, true, true];
        let (p, _, n) = square_segments(&[(0.03, 0.17), (1.0, 0.0), (3.0, 0.0)], &free, &mut |_, _| true);
        assert_eq!(n, 1);
        assert!(p.windows(2).all(|w| on45(w[0], w[1])), "{p:?}");
        assert!(axis(p[0], p[1]).is_some(), "the leg at the pad is the straight one: {p:?}");
        // nothing clear: the segment stays as it was
        let (p, _, n) = square_segments(&[(0.03, 0.17), (1.0, 0.0), (3.0, 0.0)], &free, &mut |_, _| false);
        assert_eq!((n, p.len()), (0, 3));
    }
    #[test]
    fn a_sideways_detour_is_pulled_tight_and_fixed_points_stay() {
        let pts = [(0.0, 0.0), (2.0, 0.0), (2.0, 0.5), (3.0, 0.5), (3.0, 0.0), (6.0, 0.0)];
        let free = [false, true, true, true, true, false];
        let (p, _, n) = tighten_chain(&pts, &free, &mut |_, _| true);
        assert!(n >= 1);
        assert_eq!(p, vec![(0.0, 0.0), (6.0, 0.0)]);
        // the way is blocked: it stays
        let (p, _, n) = tighten_chain(&pts, &free, &mut |_, _| false);
        assert_eq!((n, p.len()), (0, 6));
        // a fixed point in the middle stays on the path
        let fixed = [false, true, false, true, true, false];
        let (p, _, _) = tighten_chain(&pts, &fixed, &mut |_, _| true);
        assert!(p.contains(&(2.0, 0.5)), "{p:?}");
    }
    #[test]
    fn tightening_never_lengthens_a_path() {
        let pts = [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (2.0, 1.0), (2.0, 2.0), (3.0, 2.0)];
        let free = [false, true, true, true, true, false];
        let l = |v: &[Pt]| v.windows(2).map(|w| len(w[0], w[1])).sum::<f64>();
        let (p, _, _) = tighten_chain(&pts, &free, &mut |_, _| true);
        assert!(l(&p) <= l(&pts) + 1e-9 && p.len() < pts.len(), "{p:?}");
    }
    #[test]
    fn detects_staircases_and_not_long_jogs() {
        let s = stair(6, 0.3, (0.0, 0.0));
        assert_eq!(staircases(&s, 0.25), vec![(0, 6)]);
        // steps longer than 2 x width are a real jog, not a staircase
        assert!(staircases(&stair(6, 0.6, (0.0, 0.0)), 0.25).is_empty());
        // two alternating steps are a corner pair, not a staircase
        assert!(staircases(&stair(2, 0.3, (0.0, 0.0)), 0.25).is_empty());
    }

    #[test]
    fn a_staircase_becomes_a_diagonal_and_a_leg_and_collinear_points_merge() {
        // 6 steps of 0.3 after a straight lead-in with a redundant point: the first step merges
        // into the lead-in, the 5 left span dx 0.6, dy 0.9
        let mut pts = vec![(-2.0, 0.0), (-1.0, 0.0)];
        pts.extend(stair(6, 0.3, (0.0, 0.0)));
        let free: Vec<bool> = (0..pts.len()).map(|i| i != 0 && i != pts.len() - 1).collect();
        let (p, _, c) = simplify_chain(&pts, &free, 0.25, &mut |_, _| true);
        assert_eq!(c.replaced, 1);
        assert!(c.merged >= 1);
        // lead-in, a 45 degree segment, one orthogonal leg: 4 points
        assert_eq!(p.len(), 4, "{p:?}");
        assert!(staircases(&p, 0.25).is_empty());
        let diag = |a: Pt, b: Pt| ((b.0 - a.0).abs() - (b.1 - a.1).abs()).abs() < 1e-9;
        assert!((diag(p[1], p[2]) && axis(p[2], p[3]).is_some()) || (axis(p[1], p[2]).is_some() && diag(p[2], p[3])), "{p:?}");
        assert_eq!(*p.last().unwrap(), *pts.last().unwrap());
    }

    #[test]
    fn the_leg_first_candidate_is_used_when_the_diagonal_first_one_is_blocked() {
        let pts = stair(5, 0.3, (0.0, 0.0)); // ends at (0.9, 0.6)
        let free: Vec<bool> = (0..pts.len()).map(|i| i != 0 && i != pts.len() - 1).collect();
        // diagonal first would turn at (0.6, 0.6); refuse any segment that ends there
        let (p, _, c) = simplify_chain(&pts, &free, 0.25, &mut |a, b| (a.0 - 0.6).abs() + (a.1 - 0.6).abs() > 1e-9 && (b.0 - 0.6).abs() + (b.1 - 0.6).abs() > 1e-9);
        assert_eq!(c.replaced, 1);
        let want = [(0.0, 0.0), (0.3, 0.0), (0.9, 0.6)];
        assert!(p.len() == 3 && p.iter().zip(want).all(|(a, b)| len(*a, b) < 1e-9), "{p:?}");
    }

    fn mid_free(n: usize) -> Vec<bool> { (0..n).map(|i| i != 0 && i != n - 1).collect() }
    fn close(p: &[Pt], q: &[Pt]) -> bool { p.len() == q.len() && p.iter().zip(q).all(|(a, b)| len(*a, *b) < 1e-9) }

    #[test]
    fn a_right_angle_is_chamfered_into_two_45s_where_it_clears() {
        let pts = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 3.0)];
        let (p, _, c) = smooth_chain(&pts, &mid_free(3), 0.25, &mut |_, _| true);
        assert_eq!(c.chamfered, 1);
        assert!(close(&p, &[(0.0, 0.0), (2.25, 0.0), (3.0, 0.75), (3.0, 3.0)]), "{p:?}");
        assert!(right(turn_deg(pts[0], pts[1], pts[2])) && (turn_deg(p[0], p[1], p[2]).abs() - 45.0).abs() < 1e-6);
        // the full chamfer blocked, the half one clears
        let (p, _, c) = smooth_chain(&pts, &mid_free(3), 0.25, &mut |a, _| len(a, (2.25, 0.0)) > 1e-9);
        assert_eq!(c.chamfered, 1);
        assert!(close(&p, &[(0.0, 0.0), (2.625, 0.0), (3.0, 0.375), (3.0, 3.0)]), "{p:?}");
        // nothing clears: kept; a fixed corner (a pad) is never moved; a 45 degree bend is left alone
        let (p, _, c) = smooth_chain(&pts, &mid_free(3), 0.25, &mut |_, _| false);
        assert_eq!((c.chamfered, c.kept), (0, 1));
        assert_eq!(p, pts);
        assert_eq!(smooth_chain(&pts, &[false, false, false], 0.25, &mut |_, _| true).0, pts);
        let bend = vec![(0.0, 0.0), (3.0, 0.0), (5.0, 2.0)];
        assert_eq!(smooth_chain(&bend, &mid_free(3), 0.25, &mut |_, _| true).2.chamfered, 0);
    }

    #[test]
    fn a_short_sideways_step_becomes_one_45_degree_step() {
        let pts = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 0.4), (6.0, 0.4)];
        let (p, _, c) = smooth_chain(&pts, &mid_free(4), 0.25, &mut |_, _| true);
        assert_eq!((c.jogs, c.chamfered), (1, 0));
        assert!(close(&p, &[(0.0, 0.0), (2.6, 0.0), (3.0, 0.4), (6.0, 0.4)]), "{p:?}");
        // the step back is blocked: the step forward
        let (p, _, c) = smooth_chain(&pts, &mid_free(4), 0.25, &mut |a, _| len(a, (2.6, 0.0)) > 1e-9);
        assert_eq!(c.jogs, 1);
        assert!(close(&p, &[(0.0, 0.0), (3.0, 0.0), (3.4, 0.4), (6.0, 0.4)]), "{p:?}");
        // a long step is a lane change: its two corners are chamfered instead
        let lane = vec![(0.0, 0.0), (3.0, 0.0), (3.0, 2.0), (6.0, 2.0)];
        let (p, _, c) = smooth_chain(&lane, &mid_free(4), 0.25, &mut |_, _| true);
        assert_eq!((c.jogs, c.chamfered), (0, 2));
        assert!(p.windows(3).all(|w| !right(turn_deg(w[0], w[1], w[2]))), "{p:?}");
    }

    /// A pad at the origin, 1.0 mm long along y: entered along -y or +y, edge 0.5 mm.
    fn tall_pad() -> PadEnd { PadEnd { at: (0.0, 0.0), axes: vec![((0.0, -1.0), 0.5), ((0.0, 1.0), 0.5)], long: (0.0, 1.0), half: (0.5, 0.3), round: false } }

    #[test]
    fn a_pad_is_entered_along_its_own_axis() {
        // the route comes in at 45 degrees straight to the pad centre, across the pad's long side
        let pts = vec![(0.0, 0.0), (1.5, -1.5), (5.0, -1.5)];
        let (p, f, n) = enter_pads(&pts, &mid_free(3), Some(&tall_pad()), None, 0.25, &mut |_, _| true);
        assert_eq!(n, 1);
        // a straight stub up the pad's axis out past its edge (0.5 + half the width), one 45 back onto the run
        assert!(close(&p, &[(0.0, 0.0), (0.0, -0.625), (0.875, -1.5), (5.0, -1.5)]), "{p:?}");
        assert!(enters_on_axis(&p, &tall_pad()));
        assert!(p.windows(2).all(|w| on45(w[0], w[1])) && hard_corners(None, &p, None) == 0, "{p:?}");
        assert!(!f[1], "the stub's end is fixed so later passes keep the entry");
        assert_eq!(*p.last().unwrap(), (5.0, -1.5));
        // an off-grid pad centre entered at an odd angle gets the same: the stub, then a 45
        let pts = vec![(0.03, 0.02), (0.6, -1.9), (4.0, -1.9)];
        let pad = PadEnd { at: (0.03, 0.02), ..tall_pad() };
        let (p, _, n) = enter_pads(&pts, &mid_free(3), Some(&pad), None, 0.25, &mut |_, _| true);
        assert_eq!(n, 1);
        assert!(enters_on_axis(&p, &pad) && p.windows(2).all(|w| on45(w[0], w[1])), "{p:?}");
        // the end of a chain too
        let rev: Vec<Pt> = vec![(5.0, -1.5), (1.5, -1.5), (0.0, 0.0)];
        let (p, _, n) = enter_pads(&rev, &mid_free(3), None, Some(&tall_pad()), 0.25, &mut |_, _| true);
        assert_eq!(n, 1);
        assert!(close(&p, &[(5.0, -1.5), (0.875, -1.5), (0.0, -0.625), (0.0, 0.0)]), "{p:?}");
    }

    #[test]
    fn a_pad_entry_stays_when_nothing_clears_or_it_is_already_on_axis() {
        let pts = vec![(0.0, 0.0), (1.5, -1.5), (5.0, -1.5)];
        let (p, _, n) = enter_pads(&pts, &mid_free(3), Some(&tall_pad()), None, 0.25, &mut |_, _| false);
        assert_eq!((n, p.clone()), (0, pts.clone()));
        // already leaving along the axis past the edge: untouched
        let on = vec![(0.0, 0.0), (0.0, -1.0), (2.0, -3.0)];
        assert_eq!(enter_pads(&on, &mid_free(3), Some(&tall_pad()), None, 0.25, &mut |_, _| true).2, 0);
        // a fixed point (another path joins there) is never skipped over
        let fixed = [false, false, true];
        let (p, _, _) = enter_pads(&pts, &fixed, Some(&tall_pad()), None, 0.25, &mut |_, _| true);
        assert!(p.contains(&(1.5, -1.5)), "{p:?}");
        // a chain that never leaves the pad (a via in it) is left alone
        let via_in_pad = vec![(0.0, 0.0), (0.2, 0.1)];
        assert!(enters_on_axis(&via_in_pad, &tall_pad()));
        assert_eq!(enter_pads(&via_in_pad, &[false, false], Some(&tall_pad()), None, 0.25, &mut |_, _| true).2, 0);
        // a short jog inside the pad, then out along the axis, is already on axis
        let jog_in = vec![(0.0, 0.0), (0.05, -0.05), (0.05, -2.0), (3.0, -4.95)];
        assert!(enters_on_axis(&jog_in, &tall_pad()));
        // no shape without a hard corner (the route runs on along the pad's centre line): untouched
        let side = vec![(0.0, 0.0), (3.0, 0.0), (6.0, 0.0)];
        assert_eq!(enter_pads(&side, &mid_free(3), Some(&tall_pad()), None, 0.25, &mut |_, _| true).0, side);
    }

    #[test]
    fn pad_axes_follow_the_pad_and_never_point_into_its_part() {
        let b = crate::board_copper::tests::board(&[("J1", "A", 2.0, 5.0, true), ("K1", "B", 15.0, 2.0, false)], "");
        // a round through-hole pad: all eight directions; a square one: its four axes
        assert_eq!(pad_end(b.pad_by_key("J1.1").unwrap()).axes.len(), 8);
        let k = pad_end(b.pad_by_key("K1.1").unwrap());
        assert_eq!(k.axes.len(), 4);
        assert!(k.axes.iter().all(|(_, e)| (e - 0.5).abs() < 1e-6), "{k:?}");
        // a long pin at the left of its part, long axis along x: only outward (-x)
        let mut p = b.pad_by_key("K1.1").unwrap().clone();
        p.half_long = 0.6;
        p.half_short = 0.15;
        p.long_axis = (1.0, 0.0);
        p.fp_x = p.x + 3.0;
        let e = pad_end(&p);
        assert_eq!(e.axes.len(), 1);
        assert!(close(&[e.axes[0].0], &[(-1.0, 0.0)]), "{e:?}");
        // a rotated pad off every multiple of 45 degrees has no axis to enter along
        p.long_axis = (30f64.to_radians().cos(), 30f64.to_radians().sin());
        assert!(pad_end(&p).axes.is_empty());
    }

    #[test]
    fn a_short_leg_between_parallel_runs_slides_until_it_merges() {
        // east, a 0.42 mm diagonal lane change, east, then a long diagonal: the lane change is a wiggle
        let pts = vec![(0.0, 0.0), (3.0, 0.0), (3.3, 0.3), (6.0, 0.3), (8.0, 2.3)];
        assert_eq!(wiggles_in(&pts), 1);
        let (p, _, n) = slide_jogs(&pts, &mid_free(5), (true, true), &mut |_, _| true);
        assert!(n >= 1);
        assert_eq!(wiggles_in(&p), 0, "{p:?}");
        assert!(close(&p, &[(0.0, 0.0), (5.7, 0.0), (8.0, 2.3)]), "{p:?}");
        assert!((path_len(&p) - path_len(&pts)).abs() < 1e-9, "a slide keeps the length");
        // a zigzag of straight and diagonal legs becomes one straight and one diagonal
        let zig = vec![(0.0, 0.0), (0.0, 2.5), (-0.6, 3.1), (-0.6, 3.9), (-1.2, 4.5), (-1.2, 6.0)];
        assert!(wiggles_in(&zig) >= 2);
        let (p, _, _) = slide_jogs(&zig, &mid_free(6), (true, true), &mut |_, _| true);
        assert_eq!(wiggles_in(&p), 0, "{p:?}");
        assert!(p.len() < zig.len() && hard_corners(None, &p, None) == 0, "{p:?}");
        // blocked: it stays; fixed points never move
        assert_eq!(slide_jogs(&pts, &mid_free(5), (true, true), &mut |_, _| false).0, pts);
        assert_eq!(slide_jogs(&pts, &[false; 5], (true, true), &mut |_, _| true).0, pts);
        // no wiggle, nothing to do: a plain corner is left alone
        let l = vec![(0.0, 0.0), (3.0, 0.0), (5.0, 2.0)];
        assert_eq!(slide_jogs(&l, &mid_free(3), (true, true), &mut |_, _| true).2, 0);
    }

    #[test]
    fn plan_simplifier_enters_a_pad_on_its_axis_and_keeps_both_ends() {
        // net A from J1 (a round pad at 2, 5) to K1 (a square pad at 8, 3.03); the route meets K1 on a diagonal
        let b = crate::board_copper::tests::board(&[("J1", "A", 2.0, 5.0, true), ("K1", "A", 8.0, 3.03, false), ("Z1", "B", 15.0, 8.0, true)], "");
        let mut r = Router::new(b, Rules::default(), false);
        let mut plan = vec![json!({"net": "A", "width": 0.25, "paths": [["J1.1", [6.0, 5.0], [7.4, 3.6], "K1.1"]]})];
        let rep = simplify_plan(&mut r, &mut plan);
        assert!(rep["padsEnteredOnAxis"].as_u64().unwrap() >= 1, "{rep}");
        let path = plan[0]["paths"][0].as_array().unwrap();
        assert_eq!(path[0], "J1.1");
        assert_eq!(path[path.len() - 1], "K1.1");
        let pts: Vec<Pt> = path.iter().map(|v| resolve(&r.board, v).unwrap().xy).collect();
        assert!(pts.windows(2).all(|w| on45(w[0], w[1])), "{pts:?}");
        let n = pts.len();
        let last = unit(pts[n - 2], pts[n - 1]);
        assert!(last.0.abs() < 1e-6 || last.1.abs() < 1e-6, "the last leg runs along one of the square pad's axes: {pts:?}");
    }

    #[test]
    fn a_staircase_is_kept_when_no_replacement_clears() {
        let pts = stair(4, 0.3, (0.0, 0.0));
        let free: Vec<bool> = (0..pts.len()).map(|i| i != 0 && i != pts.len() - 1).collect();
        let (p, _, c) = simplify_chain(&pts, &free, 0.25, &mut |_, _| false);
        assert_eq!((c.replaced, c.kept), (0, 1));
        assert_eq!(p, pts);
    }

    #[test]
    fn plan_simplifier_respects_other_nets_by_the_router_obstacle_data() {
        // net A from J1 (2, 5) to J2 (8, 7.4) with a staircase between, net B's pad elsewhere
        let b = crate::board_copper::tests::board(&[("J1", "A", 2.0, 5.0, true), ("J2", "A", 8.0, 7.4, true), ("K1", "B", 15.0, 2.0, true)], "");
        let mut r = Router::new(b, Rules::default(), false);
        let mut path = vec![json!("J1.1"), json!([4.0, 5.0])];
        for p in stair(8, 0.3, (4.0, 5.0)).into_iter().skip(1) { path.push(json!([p.0, p.1])); }
        path.push(json!([6.0, 6.2]));
        path.push(json!("J2.1"));
        let mut plan = vec![json!({"net": "A", "width": 0.25, "paths": [path.clone()]})];
        let rep = simplify_plan(&mut r, &mut plan);
        assert_eq!(rep["staircasesReplaced"], 1, "{rep}");
        let after = plan[0]["paths"][0].as_array().unwrap().len();
        assert!(after < path.len(), "{rep}");
        assert_eq!(rep["nets"]["A"]["before"], path.len());
        assert_eq!(rep["nets"]["A"]["after"], after);
        assert_eq!(plan[0]["paths"][0][0], "J1.1");
        assert_eq!(plan[0]["paths"][0][after - 1], "J2.1");
        // the router's check refuses copper over another net's pad and off the board
        let k = (15.0, 2.0);
        assert!(!r.segment_clear("A", F_CU, (14.0, 2.0), (16.0, 2.0), 0.25));
        assert!(!r.segment_clear("A", F_CU, (0.1, 1.0), (0.1, 3.0), 0.25));
        assert!(r.segment_clear("B", F_CU, (k.0 - 1.0, k.1), (k.0 + 1.0, k.1), 0.25));
    }

    #[test]
    fn board_staircases_are_found_in_track_chains() {
        let mut extra = String::new();
        let p = stair(5, 0.3, (4.0, 5.0));
        for w in p.windows(2) { extra.push_str(&crate::board_copper::tests::seg("A", "F.Cu", w[0], w[1])); }
        let b = crate::board_copper::tests::board(&[("J1", "A", 2.0, 5.0, true)], &extra);
        let found = board_staircases(&b);
        assert_eq!(found.len(), 1, "{found:?}");
        assert!(found[0].contains("5-step staircase"), "{found:?}");
    }
}