AI Flow: Routing

//! Sort nets into the designer's routing hierarchy (4.2) and work out each net's topology: the order its
//! pads are joined in. Decoupling is cap first, crystals are daisy chains, data prefers a chain.

use crate::board::*;
use crate::geom::*;
use crate::rules::Rules;
use std::collections::{BTreeMap, HashMap, HashSet};

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Level {
    Kelvin = 0,
    Pair = 1,
    Crystal = 2,
    Data = 3,
    Power = 4,
    PlaneFanout = 5,
    Other = 6,
}

impl Level {
    pub fn name(self) -> &'static str {
        match self {
            Level::Kelvin => "kelvin",
            Level::Pair => "differential pair",
            Level::Crystal => "crystal",
            Level::Data => "data",
            Level::Power => "power",
            Level::PlaneFanout => "plane via",
            Level::Other => "non-priority",
        }
    }
}

pub struct NetInfo {
    pub net: NetId,
    pub level: Level,
    pub pads: Vec<usize>,
    /// Why this level, from the pins and parts on the net. Printed by `plan`, because a wrong class
    /// means wrong widths and the wrong turn in the hierarchy, and the designer has to be able to see it.
    pub why: String,
    /// A switch node (4.2 Switching loops): keep it compact, never pour it, MCU outside the loop.
    pub switching: bool,
    /// Kelvin taps on this net, each a chain of pads ending on the shunt (4.2): dedicated copper,
    /// routed apart from the rest of the net, which is planned without the amplifier's pins.
    pub taps: Vec<Vec<usize>>,
}

pub fn ref_prefix(r: &str) -> &str {
    let end = r.find(|c: char| c.is_ascii_digit()).unwrap_or(r.len());
    &r[..end]
}

/// A power rail by name: +3v3, +5V, VBUS, VCC, VDD... (never by width, 4.2).
pub fn looks_power(name: &str) -> bool {
    let n = name.trim_start_matches('/').to_ascii_uppercase();
    n.starts_with('+') || n.starts_with("VCC") || n.starts_with("VDD") || n.starts_with("VBUS") || n.starts_with("VIN") || n.starts_with("VSYS") || n.starts_with("PWR") || n == "VBAT"
}

pub fn looks_ground(name: &str) -> bool {
    let n = name.trim_start_matches('/').to_ascii_uppercase();
    n == "GND" || n.starts_with("GND") || n == "VSS" || n == "AGND" || n == "DGND" || n == "PGND"
}

/// Non-switching signals that can via often without a noticeable effect (4.2 item 4).
pub fn looks_low_priority(name: &str) -> bool {
    let n = name.trim_start_matches('/').to_ascii_uppercase();
    n.contains("LED") || n.contains("RST") || n.contains("RESET") || n == "RUN" || n.contains("BOOT") || n.contains("SW_") || n.contains("BTN")
}

/// The 90-ohm figures in PCB_Troubleshooting ("A USB pair fails"), measured for one JLC 4-layer stack.
/// Only a last resort when neither the spec nor the project sets a pair: every use is reported.
const TROUBLESHOOTING_PAIR: (f64, f64) = (0.2817, 0.15);

/// Pairs by name when the spec does not list them: ..D+/..D-, .._P/.._N, ..DP/..DN, then the width
/// and gap of every pair (4.2: specs are predetermined, not chosen here): the spec's, else the net
/// class's (`Rules::bind` must have run). Returns a note for each figure that came from neither.
pub fn find_pairs(board: &Board, rules: &mut Rules) -> Vec<String> {
    let names: HashSet<&str> = board.nets.iter().map(|s| s.as_str()).collect();
    let listed: HashSet<String> = rules.pairs.iter().flat_map(|p| [p.p.clone(), p.n.clone()]).collect();
    let mut found = Vec::new();
    for name in board.nets.iter() {
        for (a, b) in [("D+", "D-"), ("_P", "_N"), ("_DP", "_DN"), ("+", "-")] {
            if let Some(stem) = name.strip_suffix(a) {
                let other = format!("{stem}{b}");
                if names.contains(other.as_str()) && !listed.contains(name) && !(a == "+" && stem.is_empty()) {
                    if a == "+" && !stem.to_ascii_uppercase().ends_with("USB") && !stem.to_ascii_uppercase().ends_with('D') {
                        continue;
                    }
                    found.push((name.clone(), other));
                    break;
                }
            }
        }
    }
    found.sort();
    found.dedup();
    for (p, n) in found {
        rules.pairs.push(crate::rules::Pair { p, n, width: 0, gap: 0 });
    }
    let mut notes = Vec::new();
    let mut pairs = std::mem::take(&mut rules.pairs);
    for p in pairs.iter_mut() {
        let class = board.net_ids.get(&p.p).and_then(|&id| rules.pair_for(id));
        if p.width == 0 {
            p.width = class.map(|c| c.0).unwrap_or(0);
        }
        if p.gap == 0 {
            p.gap = class.map(|c| c.1).unwrap_or(0);
        }
        if p.width == 0 || p.gap == 0 {
            if p.width == 0 {
                p.width = mm(TROUBLESHOOTING_PAIR.0);
            }
            if p.gap == 0 {
                p.gap = mm(TROUBLESHOOTING_PAIR.1);
            }
            notes.push(format!("DEFAULT: pair {}/{} has no width or gap in the spec or a net class, so it takes {:.4}/{:.3} mm from PCB_Troubleshooting's JLC 4-layer table. Confirm it with the fab's calculator for this stack (2.2)", p.p, p.n, to_mm(p.width), to_mm(p.gap)));
        }
    }
    rules.pairs = pairs;
    notes
}

pub fn is_crystal(board: &Board, fp: usize) -> bool {
    let f = &board.footprints[fp];
    let r = ref_prefix(&f.reference);
    (r == "Y" || r == "X" || f.lib.to_ascii_lowercase().contains("crystal")) && f.pads.len() >= 2 && f.pads.len() <= 6
}

/// An LED by its part, not its net name: the reference says LED, or the library part does.
pub fn is_led(board: &Board, fp: usize) -> bool {
    let f = &board.footprints[fp];
    let r = ref_prefix(&f.reference);
    r == "LED" || (r == "D" && f.lib.to_ascii_lowercase().contains("led"))
}

/// A net that drives an LED, directly or through a series resistor: non-switching, may via often
/// (4.2 item 4). A diode that isn't an LED doesn't count: an ESD array on a terminal line is on the
/// line for a reason, and benchmark C's TI/TO lines were going last because of one.
pub fn drives_led(board: &Board, pads: &[usize]) -> bool {
    pads.iter().any(|&p| {
        let fp = board.pads[p].fp;
        if is_led(board, fp) {
            return true;
        }
        let f = &board.footprints[fp];
        if ref_prefix(&f.reference) != "R" || f.pads.len() != 2 {
            return false;
        }
        let other = f.pads.iter().copied().find(|&o| o != p);
        let Some(other) = other else { return false };
        let net = board.pads[other].net;
        // A resistor to GND or a rail also reaches some LED: that's a pull or a set resistor.
        let name = board.net_name(net);
        net != NO_NET && !looks_ground(name) && (!looks_power(name) || name.to_ascii_uppercase().contains("LED")) && board.pads.iter().any(|q| q.net == net && is_led(board, q.fp))
    })
}

/// A part value as ohms: R068, 0R1, 10m, 100mR, 4k7, 22, 0.05. None when it isn't a plain resistance.
pub fn ohms(value: &str) -> Option<f64> {
    let v = value.trim().to_ascii_lowercase().replace("ohms", "").replace("ohm", "").replace('\u{3a9}', "");
    let v = v.split_whitespace().next()?.to_string();
    for (mark, scale) in [('m', 1e-3), ('k', 1e3), ('r', 1.0)] {
        if let Some(i) = v.find(mark) {
            let (head, tail) = (&v[..i], &v[i + 1..]);
            // "100mr" is 100 milliohms: the trailing r only repeats the unit.
            let tail = tail.strip_suffix('r').unwrap_or(tail);
            let head = if head.is_empty() { "0" } else { head };
            let text = if tail.is_empty() { head.to_string() } else { format!("{head}.{tail}") };
            return text.parse::<f64>().ok().map(|x| x * scale);
        }
    }
    v.parse().ok()
}

/// A current-sense shunt: a low-value two-pad resistor. His standard parts read R068 and the like.
fn is_shunt(board: &Board, fp: usize) -> bool {
    let f = &board.footprints[fp];
    ref_prefix(&f.reference).starts_with('R') && f.pads.iter().filter(|&&p| !board.pads[p].layers.is_empty()).count() == 2 && ohms(&f.value).map(|x| x > 0.0 && x < 1.0).unwrap_or(false)
}

/// Each shunt with an amplifier's sense pins across it: (footprint of the shunt, then for each side
/// its pad and the amplifier pins on that side). The nets are rails, so the name says nothing: what
/// makes these Kelvin taps is the amplifier's input pins on both sides of a milliohm resistor.
pub fn kelvin_taps(board: &Board) -> Vec<Vec<usize>> {
    let mut out = Vec::new();
    for (fi, f) in board.footprints.iter().enumerate() {
        if !is_shunt(board, fi) || f.dnp {
            continue;
        }
        let pads: Vec<usize> = f.pads.iter().copied().filter(|&p| !board.pads[p].layers.is_empty()).collect();
        let (a, b) = (pads[0], pads[1]);
        let (na, nb) = (board.pads[a].net, board.pads[b].net);
        if na == NO_NET || nb == NO_NET || na == nb {
            continue;
        }
        for (gi, g) in board.footprints.iter().enumerate() {
            if gi == fi || g.pads.len() < 5 || !matches!(ref_prefix(&g.reference), "U" | "IC") {
                continue;
            }
            // A power pin on the rail is just the part being fed; sense pins are inputs.
            let sense = |net: NetId| -> Vec<usize> { g.pads.iter().copied().filter(|&p| board.pads[p].net == net && !board.pads[p].layers.is_empty() && matches!(board.pads[p].pintype.as_str(), "input" | "passive")).collect() };
            let (sa, sb) = (sense(na), sense(nb));
            if sa.is_empty() || sb.is_empty() {
                continue;
            }
            for (shunt_pad, mut pins) in [(a, sa), (b, sb)] {
                pins.push(shunt_pad);
                out.push(pins);
            }
        }
    }
    out
}

/// Is this a switch node? Topology first: an inductor meeting a diode, a transistor or an IC pin at
/// one net (4.2 Switching loops). A converter module hides its inductor, so a net that is only pins of
/// one IC that also has power pins, and is named for a switch node, counts too (benchmark C's U5 SW).
fn is_switch_node(board: &Board, name: &str, pads: &[usize]) -> Option<String> {
    let prefix = |p: usize| ref_prefix(&board.footprints[board.pads[p].fp].reference).to_string();
    let inductor = pads.iter().find(|&&p| prefix(p) == "L");
    let active = pads.iter().find(|&&p| match prefix(p).as_str() {
        "D" => !is_led(board, board.pads[p].fp),
        "Q" | "U" | "IC" => board.pads[p].pintype != "input",
        _ => false,
    });
    if let (Some(&l), Some(&x)) = (inductor, active) {
        return Some(format!("inductor {} meets {}", board.pad_name(l), board.pad_name(x)));
    }
    let tail = name.rsplit('/').next().unwrap_or(name).to_ascii_uppercase();
    let named = matches!(tail.as_str(), "SW" | "LX" | "PHASE") || tail.starts_with("SW_NODE");
    let first = board.pads[*pads.first()?].fp;
    let one_part = pads.iter().all(|&p| board.pads[p].fp == first);
    let powered = board.footprints[first].pads.iter().any(|&p| matches!(board.pads[p].pintype.as_str(), "power_in" | "power_out"));
    if named && one_part && powered {
        return Some(format!("only pins of {}, a part with power pins, named {tail}", board.footprints[first].reference));
    }
    None
}

/// Which nets carry power, and why, from the pins and parts rather than from names or widths (4.2:
/// never judge current from a net name or a trace width alone). A name counts only where nothing on
/// the net contradicts it: /VBUS_G is named like a rail and is two FET gates.
fn power_nets(board: &Board, rules: &Rules, by_net: &BTreeMap<NetId, Vec<usize>>) -> HashMap<NetId, String> {
    let mut power: HashMap<NetId, String> = HashMap::new();
    let ground = |n: NetId| looks_ground(board.net_name(n));
    let prefix = |p: usize| ref_prefix(&board.footprints[board.pads[p].fp].reference).to_string();
    let is_gate = |p: usize| prefix(p) == "Q" && board.pads[p].pintype == "input";
    let is_power_pin = |p: usize| matches!(board.pads[p].pintype.as_str(), "power_in" | "power_out");
    for (&net, pads) in by_net {
        let name = board.net_name(net);
        if ground(net) {
            continue;
        }
        if rules.wide.contains_key(name) {
            power.insert(net, "listed in the spec's wideNets".to_string());
        } else if let Some(&p) = pads.iter().find(|&&p| is_power_pin(p)) {
            power.insert(net, format!("power pin {} ({})", board.pad_name(p), board.pads[p].pintype));
        } else if looks_power(name) && !pads.iter().any(|&p| is_gate(p)) && !drives_led(board, pads) {
            power.insert(net, "named as a rail, and no gate or LED on it says otherwise".to_string());
        } else {
            // An output pin with only bypass capacitors on it is a regulator's own supply, not a
            // signal: nothing receives it (benchmark C's U5 VCC).
            let outputs = pads.iter().filter(|&&p| board.pads[p].pintype == "output").count();
            let caps_to_ground = pads.iter().all(|&p| {
                board.pads[p].pintype == "output" || (prefix(p) == "C" && board.footprints[board.pads[p].fp].pads.iter().any(|&o| o != p && ground(board.pads[o].net)))
            });
            if outputs > 0 && pads.len() > outputs && caps_to_ground {
                power.insert(net, "an output pin with only bypass capacitors on it".to_string());
            }
        }
    }
    // Power carries through what is in series with it: fuses, ferrites, inductors, shunts, and the
    // channel of a power FET (several pins tied on each side, the gate typed input).
    let mut links: Vec<(NetId, NetId, String)> = Vec::new();
    for (fi, f) in board.footprints.iter().enumerate() {
        let copper: Vec<usize> = f.pads.iter().copied().filter(|&p| !board.pads[p].layers.is_empty() && board.pads[p].net != NO_NET).collect();
        let r = ref_prefix(&f.reference);
        if copper.len() == 2 && (matches!(r, "F" | "FB" | "L") || is_shunt(board, fi)) {
            links.push((board.pads[copper[0]].net, board.pads[copper[1]].net, f.reference.clone()));
        }
        if r == "Q" {
            let mut sides: BTreeMap<NetId, usize> = BTreeMap::new();
            for &p in &copper {
                if !is_gate(p) {
                    *sides.entry(board.pads[p].net).or_insert(0) += 1;
                }
            }
            let tied: Vec<NetId> = sides.iter().filter(|(_, &c)| c >= 2).map(|(&n, _)| n).collect();
            for w in tied.iter().enumerate().flat_map(|(i, a)| tied[i + 1..].iter().map(move |b| (*a, *b))) {
                links.push((w.0, w.1, format!("{} channel", f.reference)));
            }
        }
    }
    loop {
        let mut changed = false;
        for (a, b, via) in &links {
            for (from, to) in [(*a, *b), (*b, *a)] {
                if power.contains_key(&from) && !power.contains_key(&to) && !ground(to) && by_net.contains_key(&to) {
                    power.insert(to, format!("in series with {} through {via}", board.net_name(from)));
                    changed = true;
                }
            }
        }
        if !changed {
            return power;
        }
    }
}

/// Is this footprint fine pitch? 4.2 only says "fine-pitch MCU", so this asks what that means for
/// routing: between two neighbouring pads of different nets, does a straight lane at the neck fit
/// with more than the minimum spacing either side? If it doesn't, spacing inside the escape has to
/// tighten to the minimum, which is what 4.2 allows a fine-pitch escape to do. Two-pad parts have no
/// pin row to escape from.
pub fn is_fine_pitch(board: &Board, rules: &Rules, fp: usize) -> bool {
    let f = &board.footprints[fp];
    let copper: Vec<usize> = f.pads.iter().copied().filter(|&p| !board.pads[p].layers.is_empty()).collect();
    if copper.len() < 3 {
        return false;
    }
    let lane = (rules.neck + 2 * rules.clearance_for(NO_NET, NO_NET).max(rules.floor)) as f64;
    for (i, &a) in copper.iter().enumerate() {
        for &b in &copper[i + 1..] {
            let (pa, pb) = (&board.pads[a], &board.pads[b]);
            if pa.net != pb.net && pa.shape.dist_shape(&pb.shape) < lane {
                return true;
            }
        }
    }
    false
}

pub fn is_passive2(board: &Board, fp: usize) -> bool {
    let f = &board.footprints[fp];
    f.pads.iter().filter(|&&p| !board.pads[p].layers.is_empty()).count() == 2 && matches!(ref_prefix(&f.reference), "C" | "R" | "L" | "FB" | "D")
}

pub fn classify(board: &Board, rules: &Rules) -> Vec<NetInfo> {
    let planes = board.plane_nets();
    let plane_names: HashSet<&str> = rules.plane_nets.iter().map(|s| s.as_str()).collect();
    let pair_nets: HashSet<&str> = rules.pairs.iter().flat_map(|p| [p.p.as_str(), p.n.as_str()]).collect();
    let kelvin: HashSet<&str> = rules.kelvin.iter().map(|s| s.as_str()).collect();
    let skip: HashSet<&str> = rules.skip_refs.iter().map(|s| s.as_str()).collect();
    let mut by_net: BTreeMap<NetId, Vec<usize>> = BTreeMap::new();
    for (i, p) in board.pads.iter().enumerate() {
        if p.net == NO_NET || p.layers.is_empty() {
            continue;
        }
        let f = &board.footprints[p.fp];
        // A part marked do-not-populate is still copper on the board: an option resistor has to be
        // wired or it is no option, and KiCad counts its pads as open (on a current-monitor board, three
        // unpopulated address resistors left five joins open while the router reported all made).
        // Only the spec's skipRefs leave a part out.
        if skip.contains(f.reference.as_str()) {
            continue;
        }
        by_net.entry(p.net).or_default().push(i);
    }
    let power = power_nets(board, rules, &by_net);
    let mut taps: HashMap<NetId, Vec<Vec<usize>>> = HashMap::new();
    for t in kelvin_taps(board) {
        taps.entry(board.pads[t[0]].net).or_default().push(t);
    }
    let mut out = Vec::new();
    for (net, pads) in by_net {
        let name = board.net_name(net);
        // KiCad names a net "unconnected-" when no schematic wire reaches it, but two pads on one
        // such net are one pin brought out twice, and its DRC wants them joined (benchmark C's U2).
        if name.is_empty() || (name.starts_with("unconnected-") && pads.len() < 2) {
            continue;
        }
        let switch = is_switch_node(board, name, &pads);
        let (level, why) = if kelvin.contains(name) {
            (Level::Kelvin, "listed as Kelvin in the spec".to_string())
        } else if pair_nets.contains(name) {
            (Level::Pair, "a differential pair".to_string())
        } else if planes.contains_key(&net) || plane_names.contains(name) || looks_ground(name) && !planes.is_empty() {
            (Level::PlaneFanout, "has a plane".to_string())
        } else if let Some(s) = &switch {
            (Level::Power, format!("switch node: {s}"))
        } else if let Some(p) = power.get(&net) {
            (Level::Power, p.clone())
        } else if drives_led(board, &pads) {
            (Level::Other, "drives an LED".to_string())
        } else if looks_low_priority(name) {
            (Level::Other, "reset, boot or button line by name".to_string())
        } else if pads.iter().any(|&p| is_crystal(board, board.pads[p].fp)) {
            (Level::Crystal, "on a crystal".to_string())
        } else {
            (Level::Data, "signal pins only".to_string())
        };
        let taps = taps.remove(&net).unwrap_or_default();
        out.push(NetInfo { net, level, pads, why, switching: switch.is_some(), taps });
    }
    out
}

/// A connection the router must make: pad to pad, inside one net.
#[derive(Clone, Debug)]
pub struct Task {
    pub net: NetId,
    pub level: Level,
    pub a: usize,
    pub b: usize,
    /// Main rail run rather than a stub to a pin.
    pub main: bool,
    /// Join this pad to its net's copper fill (index into World::zones) instead of another pad.
    pub zone: Option<usize>,
}

/// `Task::zone` value meaning: join pad `a` to the net's rail copper, or, when `a != b`, to pad `b`
/// and whatever copper it already has. The targets are worked out from the copper at route time.
pub const RAIL_TAP: usize = usize::MAX;

fn dist(board: &Board, a: usize, b: usize) -> f64 {
    hypot(sub(board.pads[a].center.into(), board.pads[b].center.into()))
}

/// Daisy chain through `pads`, starting from the end that makes the chain shortest (4.2).
fn chain(board: &Board, pads: &[usize]) -> Vec<usize> {
    if pads.len() <= 2 {
        return pads.to_vec();
    }
    let mut best: Option<(f64, Vec<usize>)> = None;
    for &start in pads {
        let mut left: Vec<usize> = pads.iter().copied().filter(|&p| p != start).collect();
        let mut seq = vec![start];
        let mut total = 0.0;
        while !left.is_empty() {
            let cur = *seq.last().unwrap();
            let (i, d) = left.iter().enumerate().map(|(i, &p)| (i, dist(board, cur, p))).min_by(|a, b| a.1.total_cmp(&b.1)).unwrap();
            total += d;
            seq.push(left.swap_remove(i));
        }
        if best.as_ref().map(|b| total < b.0).unwrap_or(true) {
            best = Some((total, seq));
        }
    }
    best.unwrap().1
}

/// Minimum spanning tree edges between groups, nearest pads first (Prim).
fn tree(board: &Board, groups: &[Vec<usize>]) -> Vec<(usize, usize)> {
    let mut joined = vec![0usize];
    let mut out = Vec::new();
    while joined.len() < groups.len() {
        let mut best: Option<(f64, usize, usize, usize)> = None;
        for &g in &joined {
            for h in 0..groups.len() {
                if joined.contains(&h) {
                    continue;
                }
                for &a in &groups[g] {
                    for &b in &groups[h] {
                        let d = dist(board, a, b);
                        if best.map(|x| d < x.0).unwrap_or(true) {
                            best = Some((d, a, b, h));
                        }
                    }
                }
            }
        }
        let (_, a, b, h) = best.unwrap();
        out.push((a, b));
        joined.push(h);
    }
    out
}

/// Plan the pad-to-pad connections for one signal or power net, given which pads the board's
/// copper already joins.
pub fn plan_net(board: &Board, info: &NetInfo, groups: &[Vec<usize>]) -> Vec<Task> {
    let mk = |a, b, main| Task { net: info.net, level: info.level, a, b, main, zone: None };
    let live: Vec<Vec<usize>> = groups
        .iter()
        .map(|g| g.iter().copied().filter(|p| info.pads.contains(p)).collect::<Vec<_>>())
        .filter(|g: &Vec<usize>| !g.is_empty())
        .collect();
    if live.len() < 2 {
        return Vec::new();
    }
    let singles = live.iter().all(|g| g.len() == 1);
    match info.level {
        Level::Crystal if singles => {
            // IC pin -> load-cap pad -> crystal pad (4.2 crystal routing).
            let pads: Vec<usize> = live.iter().map(|g| g[0]).collect();
            let mut xtal: Vec<usize> = pads.iter().copied().filter(|&p| is_crystal(board, board.pads[p].fp)).collect();
            let mut caps: Vec<usize> = pads.iter().copied().filter(|&p| ref_prefix(&board.footprints[board.pads[p].fp].reference) == "C").collect();
            let mut rest: Vec<usize> = pads.iter().copied().filter(|p| !xtal.contains(p) && !caps.contains(p)).collect();
            let far = xtal.first().copied();
            if let Some(f) = far {
                caps.sort_by(|a, b| dist(board, *b, f).total_cmp(&dist(board, *a, f)));
                rest.sort_by(|a, b| dist(board, *b, f).total_cmp(&dist(board, *a, f)));
            }
            let mut seq = Vec::new();
            seq.append(&mut rest);
            seq.append(&mut caps);
            seq.append(&mut xtal);
            seq.windows(2).map(|w| mk(w[0], w[1], false)).collect()
        }
        Level::Power => plan_rail(board, info, &live, &[], &|_, _| false, f64::INFINITY),
        _ if singles => {
            let pads: Vec<usize> = live.iter().map(|g| g[0]).collect();
            // Each new pad joins what is already laid, so it starts as one pad and a route has no
            // copper of its own behind it to double back along. `targets_of` lets it land on any of
            // that copper, weighed against reaching the previous pad (4.2: a daisy chain preferred).
            chain(board, &pads).windows(2).map(|w| mk(w[1], w[0], false)).collect()
        }
        _ => tree(board, &live).into_iter().map(|(a, b)| mk(a, b, false)).collect(),
    }
}

/// Plan one rail (4.2 power): supply pins join their own fill or their cap first (never pin ->
/// junction -> cap), then each resulting cluster joins the rail on the bus layer, tapping onto
/// whatever rail copper is nearest when its turn comes. `zones`: this net's fills, as (index in World::zones,
/// layer, outline). `stub_clear`: can this pad reach this fill straight, on its own layer? A fill
/// behind another net's copper is reached from the bus instead (4.7: DVDD pins go out to their caps).
/// `cap_reach`: how far a pin's stub to its cap may run. Past where a stub on the pad layer costs more
/// than going down to the bus and back up, the pin and the cap each join the rail on their own.
pub fn plan_rail(board: &Board, info: &NetInfo, live: &[Vec<usize>], zones: &[(usize, usize, &Vec<V>)], stub_clear: &dyn Fn(usize, usize) -> bool, cap_reach: f64) -> Vec<Task> {
    let mut tasks = Vec::new();
    let is_ic_pin = |p: usize| {
        let f = &board.footprints[board.pads[p].fp];
        f.pads.len() > 4 && matches!(ref_prefix(&f.reference), "U" | "IC" | "Q")
    };
    let is_cap = |p: usize| is_passive2(board, board.pads[p].fp) && ref_prefix(&board.footprints[board.pads[p].fp].reference) == "C";
    let (ng, nz) = (live.len(), zones.len());
    let mut uf = crate::conn::Uf::new(ng + nz);
    let mut group_of: HashMap<usize, usize> = HashMap::new();
    for (i, g) in live.iter().enumerate() {
        for &p in g {
            group_of.insert(p, i);
        }
    }
    let edge_dist = |p: usize, poly: &Vec<V>| -> f64 {
        let n = poly.len();
        if in_poly(board.pads[p].center.into(), poly) {
            return 0.0;
        }
        (0..n).map(|i| board.pads[p].shape.dist_seg(poly[i], poly[(i + 1) % n])).fold(f64::INFINITY, f64::min)
    };
    for &p in &info.pads {
        let Some(&g) = group_of.get(&p) else { continue };
        for (zi, (_, layer, poly)) in zones.iter().enumerate() {
            if board.pads[p].layers.contains(layer) && edge_dist(p, poly) <= 1.0 {
                uf.union(g as u32, (ng + zi) as u32);
            }
        }
    }
    // A pin next to its net's fill stubs into it (4.7's method, where the designer drew the fill).
    for &p in &info.pads {
        let Some(&g) = group_of.get(&p) else { continue };
        if !is_ic_pin(p) {
            continue;
        }
        for (zi, (z, layer, poly)) in zones.iter().enumerate() {
            let same = uf.find(g as u32) == uf.find((ng + zi) as u32);
            if !same && board.pads[p].layers.contains(layer) && edge_dist(p, poly) <= 1.0 * NM && stub_clear(p, *z) {
                tasks.push(Task { net: info.net, level: info.level, a: p, b: p, main: false, zone: Some(*z) });
                uf.union(g as u32, (ng + zi) as u32);
                break;
            }
        }
    }
    let caps: Vec<usize> = info.pads.iter().copied().filter(|&p| is_cap(p)).collect();
    let mut pins: Vec<usize> = info.pads.iter().copied().filter(|&p| is_ic_pin(p)).collect();
    pins.sort_by(|&a, &b| {
        let da = caps.iter().map(|&c| dist(board, a, c)).fold(f64::INFINITY, f64::min);
        let db = caps.iter().map(|&c| dist(board, b, c)).fold(f64::INFINITY, f64::min);
        da.total_cmp(&db)
    });
    for pin in pins {
        let Some(&cap) = caps.iter().min_by(|&&a, &&b| dist(board, pin, a).total_cmp(&dist(board, pin, b))) else { continue };
        if dist(board, pin, cap) > cap_reach {
            continue;
        }
        let (Some(&ga), Some(&gb)) = (group_of.get(&pin), group_of.get(&cap)) else { continue };
        if uf.find(ga as u32) != uf.find(gb as u32) {
            uf.union(ga as u32, gb as u32);
            // Rail-routed, so the search itself weighs a long stub against the bus. `main: false`
            // holds it to the cap's own pad: cap first, never a junction on the way (4.2).
            tasks.push(Task { net: info.net, level: info.level, a: pin, b: cap, main: false, zone: Some(RAIL_TAP) });
        }
    }
    // Clusters, and the pads each one is fed from: a cap if it has one (cap first), else a passive
    // or connector pad, else the pin.
    let mut clusters: BTreeMap<u32, Vec<usize>> = BTreeMap::new();
    for (i, g) in live.iter().enumerate() {
        clusters.entry(uf.find(i as u32)).or_default().extend(g.iter().copied());
    }
    let feeds: Vec<Vec<usize>> = clusters
        .values()
        .map(|pads| {
            let c: Vec<usize> = pads.iter().copied().filter(|&p| is_cap(p)).collect();
            if !c.is_empty() {
                return c;
            }
            let o: Vec<usize> = pads.iter().copied().filter(|&p| !is_ic_pin(p)).collect();
            if !o.is_empty() { o } else { pads.clone() }
        })
        .collect();
    // With a fill on the net, the fill is the hub and every cluster taps toward it at the main width.
    // Without one, the two clusters farthest apart make the trunk and the rest tap onto it. Nearest
    // to what is already joined goes next either way, so each tap finds rail close by.
    let mut joined: Vec<usize> = Vec::new();
    let mut left: Vec<usize> = (0..feeds.len()).collect();
    if zones.is_empty() && feeds.len() >= 2 {
        let mut far: Option<(f64, usize, usize, usize, usize)> = None;
        for i in 0..feeds.len() {
            for j in i + 1..feeds.len() {
                for &a in &feeds[i] {
                    for &b in &feeds[j] {
                        let d = dist(board, a, b);
                        if far.map(|x| d > x.0).unwrap_or(true) {
                            far = Some((d, i, j, a, b));
                        }
                    }
                }
            }
        }
        let (_, i, j, a, b) = far.unwrap();
        tasks.push(Task { net: info.net, level: info.level, a, b, main: true, zone: Some(RAIL_TAP) });
        joined = vec![a, b];
        left.retain(|&k| k != i && k != j);
    }
    let hub = !zones.is_empty();
    while !left.is_empty() {
        let near = |p: usize| -> f64 {
            let to_pads = joined.iter().map(|&q| dist(board, p, q)).fold(f64::INFINITY, f64::min);
            zones.iter().map(|(_, _, poly)| edge_dist(p, poly)).fold(to_pads, f64::min)
        };
        let (pos, pad) = left
            .iter()
            .enumerate()
            .flat_map(|(pos, &k)| feeds[k].iter().map(move |&p| (pos, p)))
            .min_by(|x, y| near(x.1).total_cmp(&near(y.1)))
            .unwrap();
        left.swap_remove(pos);
        joined.push(pad);
        tasks.push(Task { net: info.net, level: info.level, a: pad, b: pad, main: hub, zone: Some(RAIL_TAP) });
    }
    // A fill with no pad of its own still has to be fed: an island is never acceptable (4.3). These
    // go last: by then the pads are one piece, so the tap's only target is the fill itself.
    let reps: Vec<usize> = feeds.iter().flatten().copied().collect();
    for (zi, (_, _, poly)) in zones.iter().enumerate() {
        let root = uf.find((ng + zi) as u32);
        let has_pad = (0..ng).any(|g| uf.find(g as u32) == root);
        if !has_pad && !poly.is_empty() {
            let c = V(poly.iter().map(|p| p.0).sum::<f64>() / poly.len() as f64, poly.iter().map(|p| p.1).sum::<f64>() / poly.len() as f64);
            if let Some(&near) = reps.iter().min_by(|&&x, &&y| hypot(sub(board.pads[x].center.into(), c)).total_cmp(&hypot(sub(board.pads[y].center.into(), c)))) {
                tasks.push(Task { net: info.net, level: info.level, a: near, b: near, main: false, zone: Some(RAIL_TAP) });
            }
        }
    }
    tasks
}

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

    /// A reference board, or None where the reference boards are not present (they do not ship with
    /// the source): the test that asked is then skipped.
    fn load(name: &str) -> Option<(Board, Rules)> {
        let path = format!("{}/bench/boards/{name}.ref.kicad_pcb", env!("CARGO_MANIFEST_DIR"));
        if !std::path::Path::new(&path).exists() {
            eprintln!("skipped: {path} is not here");
            return None;
        }
        let b = Board::read(&path).unwrap();
        let mut r = Rules::default();
        crate::project::apply(&path, &mut r);
        Some((b, r))
    }

    fn level_of(b: &Board, infos: &[NetInfo], name: &str) -> Level {
        infos.iter().find(|i| b.net_name(i.net) == name).unwrap_or_else(|| panic!("{name} not classified")).level
    }

    #[test]
    fn values_read_as_ohms() {
        for (text, ohm) in [("R068", 0.068), ("0R1", 0.1), ("10m", 0.01), ("100mR", 0.1), ("4k7", 4700.0), ("22", 22.0), ("0.05", 0.05), ("100mOhm", 0.1), ("1k", 1000.0)] {
            assert!((ohms(text).unwrap() - ohm).abs() < 1e-9, "{text}");
        }
        assert_eq!(ohms("BLU"), None);
    }

    /// The reviewer's list on benchmark C, and what the parts on those nets say.
    #[test]
    fn benchmark_c_classes_come_from_its_parts() {
        let Some((b, r)) = load("benchc_v10") else { return };
        let infos = classify(&b, &r);
        assert_eq!(level_of(&b, &infos, "/MCU_Upstream/5V_VCC"), Level::Power);
        assert_eq!(level_of(&b, &infos, "/MCU_Upstream/SW"), Level::Power);
        assert!(infos.iter().find(|i| b.net_name(i.net) == "/MCU_Upstream/SW").unwrap().switching);
        assert_eq!(level_of(&b, &infos, "Net-(D3-K)"), Level::Power);
        assert_eq!(level_of(&b, &infos, "Net-(D3-A)"), Level::Power);
        // An ESD array on a terminal line isn't an LED; a real LED's anode net is low priority.
        assert_eq!(level_of(&b, &infos, "/TI_0_J"), Level::Data);
        assert_eq!(level_of(&b, &infos, "/MCU_Upstream/+3V3_AN"), Level::Other);
        // A set resistor to GND doesn't drive an LED just because GND reaches one.
        assert_eq!(level_of(&b, &infos, "/MCU_Downstream/ILIM"), Level::Data);
        // RS1 is the shunt, U11 the amplifier, and its two tied pins on the far side share one tap.
        let tap = |name: &str| infos.iter().find(|i| b.net_name(i.net) == name).unwrap().taps.iter().map(|t| t.iter().map(|&p| b.pad_name(p)).collect::<Vec<_>>()).collect::<Vec<_>>();
        assert_eq!(tap("+3V3_EXT"), vec![vec!["U11.10".to_string(), "RS1.1".to_string()]]);
        assert_eq!(tap("+3V3_EXT_SENS"), vec![vec!["U11.8".to_string(), "U11.9".to_string(), "RS1.2".to_string()]]);
    }

    #[test]
    fn benchmark_b_classes_come_from_its_parts() {
        let Some((b, r)) = load("benchb_v210") else { return };
        let infos = classify(&b, &r);
        assert_eq!(level_of(&b, &infos, "-PS1"), Level::Power);
        assert_eq!(level_of(&b, &infos, "/USB2_RLY"), Level::Power);
        // Named like a rail, and is two FET gates.
        assert_eq!(level_of(&b, &infos, "/VBUS_G"), Level::Data);
        // Through the FET's channel from a power pin; the name says nothing.
        assert_eq!(level_of(&b, &infos, "/USB2_VBUS"), Level::Power);
        assert_eq!(level_of(&b, &infos, "/VBUS_CS"), Level::Power);
        assert_eq!(level_of(&b, &infos, "/USER_IO.0"), Level::Data);
    }

    #[test]
    fn piprobe_classes_come_from_its_parts() {
        let Some((b, r)) = load("piprobe_v13") else { return };
        let infos = classify(&b, &r);
        assert_eq!(level_of(&b, &infos, "+1V1"), Level::Power);
        assert_eq!(level_of(&b, &infos, "QSPI_SD0"), Level::Data);
        // Through R4 to /PWR_LED: the name of that net starts like a rail, and it's an LED.
        assert_eq!(level_of(&b, &infos, "GPIO2"), Level::Other);
        assert_eq!(level_of(&b, &infos, "XIN"), Level::Crystal);
    }

    /// Fine pitch from the pads, against the reference's parts: 0.4 and 0.5 mm QFNs are, a 2 mm module and a
    /// 1.27 mm SOIC aren't.
    #[test]
    fn fine_pitch_comes_from_the_pad_gap() {
        let fine = |b: &Board, r: &Rules, name: &str| is_fine_pitch(b, r, b.footprints.iter().position(|f| f.reference == name).unwrap());
        let Some((b, r)) = load("piprobe_v13") else { return };
        assert!(fine(&b, &r, "U1"));
        assert!(fine(&b, &r, "U2"));
        assert!(!fine(&b, &r, "C4"));
        let Some((b, r)) = load("benchb_v210") else { return };
        assert!(fine(&b, &r, "U3"));
        assert!(!fine(&b, &r, "U2"));
        assert!(!fine(&b, &r, "Q1"));
        let Some((b, r)) = load("benchc_v10") else { return };
        assert!(fine(&b, &r, "U6"));
        assert!(fine(&b, &r, "U11"));
    }
}