AI Flow: Routing

//! What the designer rejects on sight and DRC never sees: copper that doubles back on itself, runs beside
//! itself, changes width every few millimetres, vias a short net needs no vias for, routes far longer
//! than their pads are apart, fills nothing feeds, rails thinner than 4.2's floor. Each one is graded
//! on the reference boards (bench/grade.json); where a threshold is a number he never wrote, the comment says
//! what it was read off.

use crate::board::*;
use crate::check::{Finding, NetStat, RailStat, Score};
use crate::classify::*;
use crate::geom::*;
use crate::rules::Rules;
use std::collections::{BTreeMap, HashMap, HashSet};

/// Shorter than this a segment is a width step or a stray join, not a direction change.
const JOG: f64 = 20_000.0;
/// Centre to centre, and overlap along the run, that make two same-net tracks one doubled run.
const DOUBLED_D: f64 = 0.4 * NM;
const DOUBLED_RUN: f64 = 0.3 * NM;
/// A retrace shorter than this past the pad or via it starts in is a join, not a fold. His boards'
/// longest such join is under his pads; our DIO retrace is 1.23 mm.
const FOLD_RUN: f64 = 0.1 * NM;

fn key(p: P) -> P {
    ((p.0 + 1000).div_euclid(2000), (p.1 + 1000).div_euclid(2000))
}

fn at_mm(p: P) -> (f64, f64) {
    (to_mm(p.0), to_mm(p.1))
}

fn len_of(t: &Track) -> f64 {
    hypot(sub(t.a.into(), t.b.into()))
}

/// Endpoints per net and layer, with micro-jogs merged so a 4 micron step is one node.
pub struct Nodes {
    link: HashMap<(NetId, usize, P), P>,
    pub at: HashMap<(NetId, usize, P), Vec<usize>>,
}

impl Nodes {
    pub fn new(board: &Board) -> Nodes {
        let mut n = Nodes { link: HashMap::new(), at: HashMap::new() };
        for t in &board.tracks {
            if len_of(t) <= JOG {
                let (x, y) = (n.rep(t.net, t.layer, t.a), n.rep(t.net, t.layer, t.b));
                if x != y {
                    n.link.insert((t.net, t.layer, x), y);
                }
            }
        }
        for (i, t) in board.tracks.iter().enumerate() {
            if len_of(t) > JOG {
                let (x, y) = (n.rep(t.net, t.layer, t.a), n.rep(t.net, t.layer, t.b));
                n.at.entry((t.net, t.layer, x)).or_default().push(i);
                n.at.entry((t.net, t.layer, y)).or_default().push(i);
            }
        }
        n
    }
    pub fn rep(&self, net: NetId, layer: usize, p: P) -> P {
        let mut k = key(p);
        while let Some(&n) = self.link.get(&(net, layer, k)) {
            k = n;
        }
        k
    }
    /// A track's ends as seen from node `n`: (the end at n, the far end).
    fn from(&self, t: &Track, n: P) -> (P, P) {
        if self.rep(t.net, t.layer, t.a) == n { (t.a, t.b) } else { (t.b, t.a) }
    }
}

fn angle(from: P, to: P) -> f64 {
    ((to.1 - from.1) as f64).atan2((to.0 - from.0) as f64).to_degrees()
}

fn diff(a: f64, b: f64) -> f64 {
    let d = (a - b).rem_euclid(360.0);
    d.min(360.0 - d)
}

fn own_pad_at(board: &Board, net: NetId, layer: usize, v: V) -> Option<usize> {
    board.pads.iter().position(|q| q.net == net && q.layers.contains(&layer) && q.shape.dist_pt(v) <= 1.0)
}

/// How much of a to b lies outside the net's own pads and via lands: copper inside them can't be seen,
/// so a 0.3 mm overlap wholly inside U1.33 on his v1.3 is nothing, and a retrace out of a pad is.
fn visible(board: &Board, net: NetId, layer: usize, a: V, b: V) -> f64 {
    let l = hypot(sub(b, a));
    if l <= 0.0 {
        return 0.0;
    }
    let steps = ((l / 20_000.0).ceil() as usize).max(1);
    let mut out = 0.0;
    for i in 0..steps {
        let u = (i as f64 + 0.5) / steps as f64;
        let p = V(a.0 + (b.0 - a.0) * u, a.1 + (b.1 - a.1) * u);
        let hid = board.pads.iter().any(|q| q.net == net && q.layers.contains(&layer) && q.shape.dist_pt(p) <= 0.0)
            || board.vias.iter().any(|v| v.net == net && hypot(sub(v.at.into(), p)) <= v.size as f64 / 2.0);
        if !hid {
            out += l / steps as f64;
        }
    }
    out
}

/// Fold-back (a track retracing its neighbour from a shared node) and doubled runs (two same-net
/// tracks side by side). 4.2: "route as straight as possible, with the fewest segments". A pad or a
/// via hides a corner, not a retrace: DIO at R15.2 on the routed PiProbe goes to the pad's centre and
/// comes back along itself.
pub fn shape_rules(board: &Board, nodes: &Nodes, f: &mut Vec<Finding>) {
    for ((net, layer, n), list) in &nodes.at {
        for (x, &i) in list.iter().enumerate() {
            for &j in &list[x + 1..] {
                if i == j {
                    continue;
                }
                let (ti, tj) = (&board.tracks[i], &board.tracks[j]);
                let (a, b) = nodes.from(ti, *n);
                let (c, d) = nodes.from(tj, *n);
                if diff(angle(a, b), angle(c, d)) <= 3.0 {
                    let short = if len_of(ti) <= len_of(tj) { b } else { d };
                    let run = visible(board, *net, *layer, a.into(), short.into());
                    if run < FOLD_RUN {
                        continue;
                    }
                    let v: V = a.into();
                    let place = match own_pad_at(board, *net, *layer, v) {
                        Some(p) => format!(" at its pad {}", board.pad_name(p)),
                        None => String::new(),
                    };
                    f.push(Finding { rule: "fold-back", severity: "error", at: at_mm(a), text: format!("{}: retraces itself for {:.2} mm on {}{place} (4.2)", board.net_name(*net), run / NM, board.layers[*layer].name) });
                }
            }
        }
    }
    let mut by: BTreeMap<(NetId, usize), Vec<usize>> = BTreeMap::new();
    for (i, t) in board.tracks.iter().enumerate() {
        if len_of(t) > JOG && t.net != NO_NET {
            by.entry((t.net, t.layer)).or_default().push(i);
        }
    }
    for ((net, layer), list) in by {
        for (x, &i) in list.iter().enumerate() {
            for &j in &list[x + 1..] {
                let (s, o) = (&board.tracks[i], &board.tracks[j]);
                let (a, b): (V, V) = (s.a.into(), s.b.into());
                let (c, e): (V, V) = (o.a.into(), o.b.into());
                let (ls, lo) = (hypot(sub(b, a)), hypot(sub(e, c)));
                let u = V((b.0 - a.0) / ls, (b.1 - a.1) / ls);
                let w = sub(e, c);
                if (u.0 * w.1 - u.1 * w.0).abs() / lo > 0.02 {
                    continue;
                }
                let d = ((c.0 - a.0) * -u.1 + (c.1 - a.1) * u.0).abs();
                if d > DOUBLED_D {
                    continue;
                }
                let (t0, t1) = (dot(sub(c, a), u), dot(sub(e, a), u));
                let (from, to) = (t0.min(t1).max(0.0), ls.min(t0.max(t1)));
                if to - from < DOUBLED_RUN {
                    continue;
                }
                let on_a = |u: f64| V(a.0 + (b.0 - a.0) * u / ls, a.1 + (b.1 - a.1) * u / ls);
                let run = visible(board, net, layer, on_a(from), on_a(to));
                if run < DOUBLED_RUN {
                    continue;
                }
                // Two tracks sharing a node and leaving it the same way are the fold-back above.
                let share = [s.a, s.b].iter().any(|p| {
                    let k = nodes.rep(net, layer, *p);
                    k == nodes.rep(net, layer, o.a) || k == nodes.rep(net, layer, o.b)
                });
                if share && d < 2000.0 {
                    continue;
                }
                f.push(Finding { rule: "same-net-parallel", severity: "error", at: at_mm(s.a), text: format!("{}: runs beside itself on {} for {:.2} mm, {:.3} mm centre to centre (4.2)", board.net_name(net), board.layers[layer].name, run / NM, d / NM) });
            }
        }
    }
}

/// Width steps on a net: a node of exactly two tracks of different widths, outside the net's pads,
/// where the step does not show. The reviewer's total on the reference boards: 5, 53, 45.
fn width_steps(board: &Board, nodes: &Nodes) -> HashMap<NetId, Vec<P>> {
    let mut out: HashMap<NetId, Vec<P>> = HashMap::new();
    for ((net, layer, n), list) in &nodes.at {
        if list.len() != 2 || board.tracks[list[0]].width == board.tracks[list[1]].width {
            continue;
        }
        let (a, _) = nodes.from(&board.tracks[list[0]], *n);
        if own_pad_at(board, *net, *layer, a.into()).is_some() {
            continue;
        }
        out.entry(*net).or_default().push(a);
    }
    out
}

/// Straight-line length of the shortest tree over a net's pads (Prim).
fn tree_length(board: &Board, pads: &[usize]) -> f64 {
    if pads.len() < 2 {
        return 0.0;
    }
    let c: Vec<V> = pads.iter().map(|&p| board.pads[p].shape.center()).collect();
    let mut best: Vec<f64> = c.iter().map(|q| hypot(sub(*q, c[0]))).collect();
    let mut used = vec![false; c.len()];
    used[0] = true;
    let mut total = 0.0;
    for _ in 1..c.len() {
        let (i, d) = best.iter().enumerate().filter(|(i, _)| !used[*i]).map(|(i, d)| (i, *d)).min_by(|x, y| x.1.total_cmp(&y.1)).unwrap();
        used[i] = true;
        total += d;
        for k in 0..c.len() {
            if !used[k] {
                best[k] = best[k].min(hypot(sub(c[k], c[i])));
            }
        }
    }
    total
}

/// A net's copper as a graph: pads, via lands and fills are single nodes, tracks are edges, split
/// wherever another track or a via lands on them. Everything the checker asks about topology (is
/// the cap first, where is the main run) is asked of this, so a via or a mid-track tap can't hide it.
pub struct Graph {
    pub adj: Vec<Vec<(usize, f64, i64, P)>>,
    pub pads_of: Vec<Vec<usize>>,
    pub fill: Vec<bool>,
    pub pad_node: HashMap<usize, usize>,
}

impl Graph {
    pub fn build(board: &Board, net: NetId) -> Graph {
        let tracks: Vec<&Track> = board.tracks.iter().filter(|t| t.net == net).collect();
        let vias: Vec<&Via> = board.vias.iter().filter(|v| v.net == net).collect();
        let mut ids: HashMap<(usize, P), usize> = HashMap::new();
        let mut pos: Vec<(usize, V)> = Vec::new();
        let mut node = |layer: usize, p: V, pos: &mut Vec<(usize, V)>| -> usize {
            *ids.entry((layer, key(to_p(p)))).or_insert_with(|| {
                pos.push((layer, p));
                pos.len() - 1
            })
        };
        let mut edges: Vec<(usize, usize, f64, i64, P)> = Vec::new();
        for t in &tracks {
            let (a, b): (V, V) = (t.a.into(), t.b.into());
            let l = hypot(sub(b, a)).max(1.0);
            let mut cuts: Vec<(f64, V)> = vec![(0.0, a), (l, b)];
            let mut try_cut = |p: V| {
                if pt_seg(p, a, b) <= 2000.0 {
                    let u = dot(sub(p, a), V((b.0 - a.0) / l, (b.1 - a.1) / l));
                    if u > 2000.0 && u < l - 2000.0 {
                        cuts.push((u, p));
                    }
                }
            };
            for o in &tracks {
                if o.layer == t.layer {
                    try_cut(o.a.into());
                    try_cut(o.b.into());
                }
            }
            for v in &vias {
                try_cut(v.at.into());
            }
            cuts.sort_by(|x, y| x.0.total_cmp(&y.0));
            for w in cuts.windows(2) {
                let (p, q) = (node(t.layer, w[0].1, &mut pos), node(t.layer, w[1].1, &mut pos));
                edges.push((p, q, w[1].0 - w[0].0, t.width, t.a));
            }
        }
        let n0 = pos.len();
        let pads: Vec<usize> = (0..board.pads.len()).filter(|&i| board.pads[i].net == net && !board.pads[i].layers.is_empty()).collect();
        let fills: Vec<(usize, Vec<V>)> = board.zones.iter().filter(|z| z.net == net && !z.keepout_tracks).flat_map(|z| {
            if z.fills.is_empty() { z.layers.iter().map(|l| (*l, z.outline.clone())).collect::<Vec<_>>() } else { z.fills.clone() }
        }).collect();
        // Node ids after the track nodes: pads, then vias, then fills.
        let (first_via, first_fill) = (n0 + pads.len(), n0 + pads.len() + vias.len());
        let total = first_fill + fills.len();
        let mut uf = crate::conn::Uf::new(total);
        for (k, &i) in pads.iter().enumerate() {
            let p = &board.pads[i];
            for (m, (l, v)) in pos.iter().enumerate() {
                if p.layers.contains(l) && p.shape.dist_pt(*v) <= 1.0 {
                    uf.union(m as u32, (n0 + k) as u32);
                }
            }
            for (vi, v) in vias.iter().enumerate() {
                if p.shape.dist_pt(v.at.into()) <= v.size as f64 / 2.0 {
                    uf.union((first_via + vi) as u32, (n0 + k) as u32);
                }
            }
            for (fi, (l, poly)) in fills.iter().enumerate() {
                if p.layers.contains(l) && crate::conn::shape_meets_poly(&p.shape, poly) {
                    uf.union((first_fill + fi) as u32, (n0 + k) as u32);
                }
            }
            for (k2, &j) in pads.iter().enumerate().skip(k + 1) {
                let q = &board.pads[j];
                if p.layers.iter().any(|l| q.layers.contains(l)) && p.shape.dist_shape(&q.shape) <= 1.0 {
                    uf.union((n0 + k) as u32, (n0 + k2) as u32);
                }
            }
        }
        for (vi, v) in vias.iter().enumerate() {
            let c: V = v.at.into();
            for (m, (_, q)) in pos.iter().enumerate() {
                if hypot(sub(*q, c)) <= v.size as f64 / 2.0 {
                    uf.union(m as u32, (first_via + vi) as u32);
                }
            }
            for (fi, (_, poly)) in fills.iter().enumerate() {
                if in_poly(c, poly) {
                    uf.union((first_fill + fi) as u32, (first_via + vi) as u32);
                }
            }
        }
        for (fi, (l, poly)) in fills.iter().enumerate() {
            for (m, (ml, q)) in pos.iter().enumerate() {
                if ml == l && in_poly(*q, poly) {
                    uf.union(m as u32, (first_fill + fi) as u32);
                }
            }
        }
        let mut g = Graph { adj: vec![Vec::new(); total], pads_of: vec![Vec::new(); total], fill: vec![false; total], pad_node: HashMap::new() };
        for (k, &i) in pads.iter().enumerate() {
            let r = uf.find((n0 + k) as u32) as usize;
            g.pads_of[r].push(i);
            g.pad_node.insert(i, r);
        }
        for fi in 0..fills.len() {
            let r = uf.find((first_fill + fi) as u32) as usize;
            g.fill[r] = true;
        }
        for (p, q, l, w, at) in edges {
            let (a, b) = (uf.find(p as u32) as usize, uf.find(q as u32) as usize);
            if a != b {
                g.adj[a].push((b, l, w, at));
                g.adj[b].push((a, l, w, at));
            }
        }
        g
    }

    /// The longest of the shortest paths between two pads, as its edges (length, width). The main
    /// run: it carries the net end to end, whatever is drawn widest somewhere else.
    pub fn main_run(&self) -> Vec<(f64, i64)> {
        let dijkstra = |s: usize| -> (Vec<f64>, Vec<Option<(usize, f64, i64)>>) {
            let mut d = vec![f64::INFINITY; self.adj.len()];
            let mut from = vec![None; self.adj.len()];
            let mut done = vec![false; self.adj.len()];
            d[s] = 0.0;
            loop {
                let Some(u) = (0..d.len()).filter(|&i| !done[i] && d[i].is_finite()).min_by(|a, b| d[*a].total_cmp(&d[*b])) else { break };
                done[u] = true;
                for &(v, l, w, _) in &self.adj[u] {
                    if d[u] + l < d[v] {
                        d[v] = d[u] + l;
                        from[v] = Some((u, l, w));
                    }
                }
            }
            (d, from)
        };
        let ends: Vec<usize> = (0..self.adj.len()).filter(|&i| !self.pads_of[i].is_empty() && !self.adj[i].is_empty()).collect();
        let mut best: Vec<(f64, i64)> = Vec::new();
        let mut best_len = 0.0;
        for &s in &ends {
            let (d, from) = dijkstra(s);
            for &e in &ends {
                if d[e].is_finite() && d[e] > best_len {
                    best_len = d[e];
                    best.clear();
                    let mut c = e;
                    while let Some((p, l, w)) = from[c] {
                        best.push((l, w));
                        c = p;
                    }
                }
            }
        }
        best
    }
}

/// Where a walk from a supply pin first stops (4.2: "each supply pin routes to its cap's pad first").
#[derive(Debug, PartialEq, Clone, Copy)]
enum Stop {
    Cap,
    Fill,
    Pad(usize),
    Junction(P),
    End,
}

fn walk(g: &Graph, board: &Board, start: usize, first: usize, at: P, is_cap: &dyn Fn(usize) -> bool) -> Stop {
    let (mut prev, mut cur, mut last) = (start, first, at);
    for _ in 0..200 {
        // A fill merges everything it touches into one node, so it is judged first: reaching it is
        // reaching the rail, whatever else it also touches.
        if g.fill[cur] {
            return Stop::Fill;
        }
        if g.pads_of[cur].iter().any(|&p| is_cap(p)) {
            return Stop::Cap;
        }
        if let Some(&p) = g.pads_of[cur].first() {
            return Stop::Pad(p);
        }
        // Distinct neighbours: a track and a stub laid over it are one way on.
        let mut on: Vec<(usize, P)> = Vec::new();
        for &(v, _, _, a) in &g.adj[cur] {
            if v != prev && !on.iter().any(|o| o.0 == v) {
                on.push((v, a));
            }
        }
        match on.len() {
            0 => return Stop::End,
            1 => {
                prev = cur;
                last = on[0].1;
                cur = on[0].0;
            }
            _ => return Stop::Junction(last),
        }
    }
    let _ = board;
    Stop::End
}

/// Cap first, walked on the real copper, through vias and mid-track taps.
fn cap_first(board: &Board, net: NetId, g: &Graph, f: &mut Vec<Finding>, s: &mut Score) {
    let is_cap = |p: usize| ref_prefix(&board.footprints[board.pads[p].fp].reference) == "C";
    let caps = g.pads_of.iter().flatten().filter(|&&p| is_cap(p)).count();
    if caps == 0 {
        return;
    }
    let mut pins: Vec<usize> = g.pads_of.iter().flatten().copied().filter(|&p| crate::placement::is_supply_pin(board, p)).collect();
    pins.sort();
    for pin in pins {
        let Some(&start) = g.pad_node.get(&pin) else { continue };
        s.cap_first.pins += 1;
        if g.fill[start] {
            s.cap_first.on_fill += 1;
            continue;
        }
        if g.pads_of[start].iter().any(|&p| is_cap(p)) {
            s.cap_first.direct += 1;
            continue;
        }
        // Pins tied side by side count as one pin (4.1): carry on from the neighbour.
        let mut stops: Vec<Stop> = Vec::new();
        let mut seen = vec![start];
        let mut work = vec![start];
        while let Some(n) = work.pop() {
            for &(v, _, _, a) in &g.adj[n] {
                let st = walk(g, board, n, v, a, &is_cap);
                if let Stop::Pad(p) = st {
                    if board.pads[p].fp == board.pads[pin].fp {
                        if let Some(&m) = g.pad_node.get(&p) {
                            if !seen.contains(&m) {
                                seen.push(m);
                                work.push(m);
                                continue;
                            }
                        }
                        continue;
                    }
                }
                stops.push(st);
            }
        }
        if stops.iter().any(|x| *x == Stop::Cap) {
            s.cap_first.cap += 1;
        } else if stops.iter().any(|x| *x == Stop::Fill) {
            s.cap_first.on_fill += 1;
        } else {
            // A pin with no copper yet is unrouted, which is `unconnected`'s to report, not this.
            let (at, what) = match stops.iter().find(|x| matches!(x, Stop::Junction(_))) {
                Some(Stop::Junction(p)) => (*p, "a junction".to_string()),
                _ => match stops.iter().find_map(|x| if let Stop::Pad(p) = x { Some(*p) } else { None }) {
                    Some(p) => (board.pads[pin].center, format!("pad {}", board.pad_name(p))),
                    None => continue,
                },
            };
            s.cap_first.junction += 1;
            f.push(Finding { rule: "cap-first", severity: "warn", at: at_mm(at), text: format!("{} ({}): reaches {what} before a cap; route pin to cap first (4.2)", board.pad_name(pin), board.net_name(net)) });
        }
    }
}

/// Boards under 3 x 3 in carry 4.2's floor on the main run; larger ones record the margin.
fn is_small(board: &Board) -> bool {
    let (w, h) = (board.bbox.2 - board.bbox.0, board.bbox.3 - board.bbox.1);
    w < 76.2 * NM && h < 76.2 * NM && w > 0.0
}

/// Rails, from the copper graph (4.2, and his decision of 2026-10-27: "Main runs only. Perform
/// analysis on branches"). The main run is the path that carries the net end to end; its width is
/// what most of that length is drawn at, so short necks at pins don't count against it and a short
/// wide patch doesn't excuse it. Everything else is a branch, recorded with its width and length.
fn rail_rules(board: &Board, rules: &Rules, net: NetId, g: &Graph, f: &mut Vec<Finding>, s: &mut Score) {
    let name = board.net_name(net);
    let main = g.main_run();
    if main.is_empty() {
        return;
    }
    let len: f64 = main.iter().map(|e| e.0).sum();
    let mut by: Vec<(i64, f64)> = Vec::new();
    for (l, w) in &main {
        match by.iter_mut().find(|x| x.0 == *w) {
            Some(x) => x.1 += l,
            None => by.push((*w, *l)),
        }
    }
    by.sort_by_key(|x| x.0);
    let mut acc = 0.0;
    let mut width = by[0].0;
    for (w, l) in &by {
        acc += l;
        if acc >= len / 2.0 {
            width = *w;
            break;
        }
    }
    let mut widths: BTreeMap<i64, f64> = BTreeMap::new();
    for t in board.tracks.iter().filter(|t| t.net == net && t.width != width) {
        *widths.entry(t.width).or_insert(0.0) += len_of(t);
    }
    s.rails.push(RailStat { name: name.to_string(), main_width_mm: to_mm(width), main_len_mm: len / NM, fed_by_fill: g.fill.iter().any(|x| *x), branches: widths.iter().map(|(w, l)| (to_mm(*w), (l / NM * 100.0).round() / 100.0)).collect() });
    let first = board.tracks.iter().find(|t| t.net == net && t.width == width).map(|t| t.a).unwrap_or((0, 0));
    if is_small(board) && width < rules.power_floor - 1000 && len >= RAIL_MIN_RUN {
        f.push(Finding { rule: "rail-floor", severity: "error", at: at_mm(first), text: format!("{name}: main run {:.2} mm long is {:.3} mm wide; 4.2's floor on a board under 3 x 3 in is {:.3} mm", len / NM, to_mm(width), to_mm(rules.power_floor)) });
    }
}

/// Under this the "main run" is a pin to its cap, which 4.2 calls a branch.
const RAIL_MIN_RUN: f64 = 3.0 * NM;
/// Fewest millimetres of straight line per via. His boards' lowest: 2.98 (benchmark C /MCU2_TO_1, a
/// non-priority net), so this reads off his practice; it warns, it does not gate. /RX_A: 0.93.
const VIA_SPACING: f64 = 2.9;
/// Copper over straight line on a net, read off the reference boards: worst 1.87 (v1.3 GPIO2). Warns only.
const EFFICIENCY: f64 = 1.9;
/// More width steps than this on one net. His boards' most on any net: 3 (benchmark C).
const NET_STEPS: usize = 3;

pub fn net_rules(board: &Board, rules: &Rules, infos: &[NetInfo], nodes: &Nodes, f: &mut Vec<Finding>, s: &mut Score) {
    let steps = width_steps(board, nodes);
    let mut with_fill: HashSet<NetId> = HashSet::new();
    for z in &board.zones {
        if z.net != NO_NET && !z.keepout_tracks {
            with_fill.insert(z.net);
        }
    }
    for info in infos {
        let name = board.net_name(info.net);
        let tracks: Vec<&Track> = board.tracks.iter().filter(|t| t.net == info.net).collect();
        if !looks_ground(name) && (looks_power(name) || info.level == Level::Power) {
            let g = Graph::build(board, info.net);
            cap_first(board, info.net, &g, f, s);
            rail_rules(board, rules, info.net, &g, f, s);
        }
        if tracks.is_empty() {
            continue;
        }
        let len: f64 = tracks.iter().map(|t| len_of(t)).sum();
        let mst = tree_length(board, &info.pads);
        let vias = board.vias.iter().filter(|v| v.net == info.net).count();
        let st = steps.get(&info.net).cloned().unwrap_or_default();
        let fill = with_fill.contains(&info.net);
        s.nets.push(NetStat { name: name.to_string(), level: info.level.name(), pads: info.pads.len(), len_mm: len / NM, tree_mm: mst / NM, vias, width_steps: st.len(), fill });
        let at = at_mm(tracks[0].a);
        if st.len() > NET_STEPS {
            f.push(Finding { rule: "width-steps", severity: "warn", at: at_mm(st[0]), text: format!("{name}: {} width changes; the reference boards' most on a net is {NET_STEPS} (4.2: one technique, fewest segments)", st.len()) });
        }
        // A rail may via often (4.2 item 3), and a fill gives no straight-line measure.
        let rail = looks_power(name) || looks_ground(name) || info.level == Level::PlaneFanout || fill;
        if !rail && vias > 0 && mst / NM / (vias as f64) < VIA_SPACING {
            f.push(Finding { rule: "via-count", severity: "warn", at, text: format!("{name}: {vias} vias on a net {:.2} mm across; the reference boards' tightest is {:.2} mm per via (4.2: don't hop where the top works)", mst / NM, 2.98) });
        }
        if !rail && mst >= 1.0 * NM && len / mst > EFFICIENCY {
            f.push(Finding { rule: "route-efficiency", severity: "warn", at, text: format!("{name}: {:.2} mm of copper for {:.2} mm of straight line, {:.2} x; the reference boards' worst is 1.87 x (4.2: as straight as possible)", len / NM, mst / NM, len / mst) });
        }
    }
    s.nets.sort_by(|a, b| a.name.cmp(&b.name));
    s.width_steps = steps.values().map(|v| v.len()).sum();
}

/// Copper a net has lying apart from any pad (4.3: "islands: in practice, never"). A fill nothing
/// feeds is an error: connectivity counted only pads, so an unfed ring passed. Tracks and vias with
/// no pad are reported as a warning, since a stitching via in a plane is one too.
pub fn island_rules(board: &Board, f: &mut Vec<Finding>) {
    for isl in crate::conn::islands(board) {
        if isl.has_pad {
            continue;
        }
        let name = board.net_name(isl.net);
        if isl.fill_pieces > 0 {
            f.push(Finding { rule: "fill-unfed", severity: "error", at: (isl.at.0 / NM, isl.at.1 / NM), text: format!("{name}: a fill on {} of about {:.2} sq mm reaches no pad of the net (4.3)", board.layers[isl.layer].name, isl.area / NM / NM) });
        } else {
            f.push(Finding { rule: "orphan-copper", severity: "warn", at: (isl.at.0 / NM, isl.at.1 / NM), text: format!("{name}: {} tracks and {} vias reach no pad of the net", isl.tracks, isl.vias) });
        }
    }
}

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

    fn board(extra: &str) -> Board {
        let head = r#"(kicad_pcb (layers (0 "F.Cu" signal) (2 "B.Cu" signal)) (setup (pad_to_mask_clearance 0.05))
            (gr_rect (start 0 0) (end 30 30) (layer "Edge.Cuts"))
            (footprint "x" (layer "F.Cu") (at 10 10) (property "Reference" "R1")
              (pad "1" smd rect (at 0 0) (size 1 1) (layers "F.Cu" "F.Mask") (net "A"))
              (pad "2" smd rect (at 8 0) (size 1 1) (layers "F.Cu" "F.Mask") (net "A")))"#;
        Board::parse(format!("{head}{extra})")).unwrap()
    }

    fn seg(a: (f64, f64), b: (f64, f64)) -> String {
        format!(r#"(segment (start {} {}) (end {} {}) (width 0.2) (layer "F.Cu") (net "A"))"#, a.0, a.1, b.0, b.1)
    }

    fn count(extra: &str, rule: &str) -> usize {
        check(&board(extra), &Rules::default()).0.iter().filter(|x| x.rule == rule).count()
    }

    #[test]
    fn a_retrace_out_of_a_pad_is_a_fold_back_and_one_inside_it_is_not() {
        // Up to the pad's centre and back out along itself, as DIO did at R15.2.
        let out = format!("{}{}", seg((14.0, 14.0), (10.0, 10.0)), seg((10.0, 10.0), (13.0, 13.0)));
        assert_eq!(count(&out, "fold-back"), 1);
        assert_eq!(count(&out, "corner-acute"), 0);
        // The same retrace, wholly under the pad's copper.
        let hid = format!("{}{}", seg((14.0, 14.0), (10.0, 10.0)), seg((10.0, 10.0), (10.2, 10.2)));
        assert_eq!(count(&hid, "fold-back"), 0);
    }

    #[test]
    fn a_doubled_run_counts_only_what_shows() {
        let side = format!("{}{}", seg((12.0, 5.0), (16.0, 5.0)), seg((12.0, 5.3), (16.0, 5.3)));
        assert_eq!(count(&side, "same-net-parallel"), 1);
        let far = format!("{}{}", seg((12.0, 5.0), (16.0, 5.0)), seg((12.0, 5.6), (16.0, 5.6)));
        assert_eq!(count(&far, "same-net-parallel"), 0);
    }

    #[test]
    fn a_fill_with_no_pad_is_unfed() {
        let z = r#"(zone (net "A") (layer "F.Cu") (polygon (pts (xy 20 20) (xy 22 20) (xy 22 22) (xy 20 22))) (filled_polygon (layer "F.Cu") (pts (xy 20 20) (xy 22 20) (xy 22 22) (xy 20 22))))"#;
        assert_eq!(count(z, "fill-unfed"), 1);
        let fed = format!("{z}{}", seg((18.0, 10.0), (21.0, 21.0)));
        assert_eq!(count(&fed, "fill-unfed"), 0);
    }

    /// An IC with one supply pin at (10, 20), a cap's supply pad at (14, 20), one more pad on the rail.
    fn supply(extra: &str) -> Board {
        let head = r#"(kicad_pcb (layers (0 "F.Cu" signal) (2 "B.Cu" signal))
            (gr_rect (start 0 0) (end 30 30) (layer "Edge.Cuts"))
            (footprint "ic" (layer "F.Cu") (at 8 20) (property "Reference" "U1")
              (pad "1" smd rect (at 2 0) (size 0.5 0.5) (layers "F.Cu") (net "+3V3") (pintype "power_in"))
              (pad "2" smd rect (at 2 2) (size 0.5 0.5) (layers "F.Cu"))
              (pad "3" smd rect (at -2 0) (size 0.5 0.5) (layers "F.Cu"))
              (pad "4" smd rect (at -2 2) (size 0.5 0.5) (layers "F.Cu"))
              (pad "5" smd rect (at 0 3) (size 0.5 0.5) (layers "F.Cu")))
            (footprint "c" (layer "F.Cu") (at 14 20) (property "Reference" "C1")
              (pad "1" smd rect (at 0 0) (size 0.5 0.5) (layers "F.Cu") (net "+3V3"))
              (pad "2" smd rect (at 1 0) (size 0.5 0.5) (layers "F.Cu") (net "GND")))
            (footprint "r" (layer "F.Cu") (at 25 20) (property "Reference" "R1")
              (pad "1" smd rect (at 0 0) (size 0.5 0.5) (layers "F.Cu") (net "+3V3"))
              (pad "2" smd rect (at 1 0) (size 0.5 0.5) (layers "F.Cu") (net "X")))"#;
        Board::parse(format!("{head}{extra})")).unwrap()
    }

    fn t(a: (f64, f64), b: (f64, f64), layer: &str) -> String {
        format!(r#"(segment (start {} {}) (end {} {}) (width 0.5) (layer "{layer}") (net "+3V3"))"#, a.0, a.1, b.0, b.1)
    }

    fn caps(b: &Board) -> usize {
        check(b, &Rules::default()).0.iter().filter(|x| x.rule == "cap-first").count()
    }

    #[test]
    fn cap_first_sees_past_vias_and_taps() {
        // Pin, cap, then rail: fine.
        let good = format!("{}{}", t((10.0, 20.0), (14.0, 20.0), "F.Cu"), t((14.0, 20.0), (25.0, 20.0), "F.Cu"));
        assert_eq!(caps(&supply(&good)), 0);
        // A tap landing mid-track between the pin and the cap: the old walk saw only endpoints.
        let tap = format!("{good}{}", t((12.0, 20.0), (12.0, 24.0), "F.Cu"));
        assert_eq!(caps(&supply(&tap)), 1);
        // The pin goes down a via with the rail on the far side, and only then to the cap.
        let via = format!(
            "{}{}{}{}{}",
            t((10.0, 20.0), (11.0, 20.0), "F.Cu"),
            r#"(via (at 11 20) (size 0.6) (drill 0.3) (layers "F.Cu" "B.Cu") (net "+3V3"))"#,
            t((11.0, 20.0), (25.0, 20.0), "B.Cu"),
            t((11.0, 20.0), (14.0, 20.0), "F.Cu"),
            r#"(via (at 25 20) (size 0.6) (drill 0.3) (layers "F.Cu" "B.Cu") (net "+3V3"))"#,
        );
        assert_eq!(caps(&supply(&via)), 1);
    }

    #[test]
    fn the_floor_reads_the_main_run_not_the_widest_scrap() {
        // 20 mm drawn at 0.2 with 1 mm at 0.8 is a 0.2 mm rail, on a small board.
        let small = |s: &str| Board::parse(format!(r#"(kicad_pcb (layers (0 "F.Cu" signal) (2 "B.Cu" signal)) (gr_rect (start 0 0) (end 30 30) (layer "Edge.Cuts")) (footprint "r" (layer "F.Cu") (at 2 5) (property "Reference" "R1") (pad "1" smd rect (at 0 0) (size 0.5 0.5) (layers "F.Cu") (net "+3V3"))) (footprint "q" (layer "F.Cu") (at 23 5) (property "Reference" "R2") (pad "1" smd rect (at 0 0) (size 0.5 0.5) (layers "F.Cu") (net "+3V3"))){s})"#)).unwrap();
        let tr = |a: f64, b: f64, w: f64| format!(r#"(segment (start {a} 5) (end {b} 5) (width {w}) (layer "F.Cu") (net "+3V3"))"#);
        let thin = format!("{}{}", tr(2.0, 22.0, 0.2), tr(22.0, 23.0, 0.8));
        let rails = |b: &Board| check(b, &Rules::default()).0.iter().filter(|x| x.rule == "rail-floor").count();
        assert_eq!(rails(&small(&thin)), 1);
        // Mostly 0.5 with short necks at the pins passes: 4.2 lets a branch be narrower.
        let good = format!("{}{}{}", tr(2.0, 3.0, 0.2), tr(3.0, 22.0, 0.5), tr(22.0, 23.0, 0.2));
        assert_eq!(rails(&small(&good)), 0);
    }
}