AI Flow: Routing

//! Buses: what makes hand routing look hand-routed, and what road navigation has no reason to do.
//! Connections between the same two parts are planned as a group: the ones that don't cross share a
//! layer and run side by side in pin order, and the ones that would cross them take the other layer
//! on purpose instead of finding that out one at a time.
//!
//! Adapted from KiCadRoutingTools (MIT, Copyright (c) 2026 drandyhaas), docs/bus-routing.md and
//! docs/net-ordering.md: its maximum-planar-subset greedy (fewest active conflicts first, then shorter),
//! routing a bus's members middle-out, and each member following its routed neighbour. Two things
//! differ. Its crossings come from unrolling each chip's boundary, which assumes copper can't pass
//! through a part; benchmark B's runs eighteen lines through the pins of a module, so chords
//! are compared directly. And its attraction is a discount around the neighbour's path, where here a
//! member is drawn to the neighbour's shape carried over to its own pins: "each line leaves its
//! pin straight out, parallel to its neighbours at the pin pitch" (4.7, QSPI on PiProbe).
//!
//! The hierarchy isn't touched: this only orders connections inside one level (4.2), and the layer
//! and the neighbour's shape are preferences the search can overrule.

use crate::board::*;
use crate::classify::*;
use crate::geom::*;
use crate::global::chords_cross;
use crate::router::{dir_of, Plan, Router};
use crate::rules::Rules;
use crate::search::{Profile, Query, World};
use std::collections::{BTreeMap, HashMap};

/// Contacts and two-pad parts this close count as one row, the way a connector's pins do. KRT's
/// default detection radius.
const ROW_REACH: f64 = 5.0 * NM;
const ROW_BAND: f64 = 0.5 * NM;
/// Fewest connections that make a bus (KRT's strict filter).
const MIN_MEMBERS: usize = 3;

#[derive(Clone, Debug)]
pub struct Member {
    /// Which bus, and this member's turn inside it; buses go first within their level.
    pub group: usize,
    pub seq: usize,
    /// Preferred layer (index into Board::layers), by crossing count.
    pub layer: usize,
    /// Both pads reach that layer, so it costs no via to use.
    pub free: bool,
    /// The routed neighbour to follow, and whether its ends are swapped relative to this one's.
    pub follow: Option<((usize, usize), bool)>,
}

#[derive(Default)]
pub struct BusPlan {
    pub members: HashMap<(usize, usize), Member>,
    /// Each bus's lines that don't cross, in their order across the bus, and their layer: what can
    /// be laid as one band.
    pub bands: Vec<(usize, Vec<(usize, usize)>)>,
    pub notes: Vec<String>,
}

impl BusPlan {
    /// Sort key inside a level: buses first, biggest first, each member in its turn.
    pub fn order_of(&self, t: &crate::classify::Task) -> (usize, usize) {
        self.members.get(&(t.a, t.b)).map(|m| (m.group, m.seq)).unwrap_or((usize::MAX, 0))
    }
}

/// One end of a bus: a part with a row of pins, or a row of separate contacts or passives.
fn clusters(board: &Board) -> Vec<usize> {
    let n = board.footprints.len();
    let mut uf = crate::conn::Uf::new(n);
    let small: Vec<bool> = board.footprints.iter().map(|f| f.pads.iter().filter(|&&p| !board.pads[p].layers.is_empty()).count() <= 2).collect();
    for i in 0..n {
        if !small[i] {
            continue;
        }
        for j in i + 1..n {
            if small[j] && ref_prefix(&board.footprints[i].reference) == ref_prefix(&board.footprints[j].reference) {
                let (pi, pj): (V, V) = (board.footprints[i].at.into(), board.footprints[j].at.into());
                // In line with each other: a row. Parts merely near each other aren't one end of a bus.
                let aligned = (pi.0 - pj.0).abs() < ROW_BAND || (pi.1 - pj.1).abs() < ROW_BAND;
                if aligned && hypot(sub(pi, pj)) <= ROW_REACH {
                    uf.union(i as u32, j as u32);
                }
            }
        }
    }
    (0..n).map(|i| uf.find(i as u32) as usize).collect()
}

/// Find the buses among this pass's connections, and give each member its layer, turn and neighbour.
/// A row this long or longer goes down as one band (lines back to back, each beside the last, kept
/// out of optimise). Benchmark B's 15- and 11-line rows look like the designer's that way; on benchmark C the
/// same treatment of its 4-line rows cost 11 joins (290 against 301 of 302, four runs each way,
/// 2026-11-09), so short rows route as before.
const BAND_MIN: usize = 6;

pub fn plan(board: &Board, world: &World, _rules: &Rules, plan: &Plan) -> BusPlan {
    let mut out = BusPlan::default();
    let cluster = clusters(board);
    let mut by: BTreeMap<(Level, usize, usize), Vec<usize>> = BTreeMap::new();
    let tasks = &plan.tasks;
    for (i, t) in tasks.iter().enumerate() {
        // Data only: non-priority lines may via often without a noticeable effect (4.2 item 4), and
        // holding them to a plan shut GPIO2's pin on piprobe_v13 for no gain in the board's looks.
        if t.a == t.b || t.zone.is_some() || t.level != Level::Data {
            continue;
        }
        let (x, y) = (cluster[board.pads[t.a].fp], cluster[board.pads[t.b].fp]);
        if x == y {
            continue;
        }
        by.entry((t.level, x.min(y), x.max(y))).or_default().push(i);
    }
    let mut groups: Vec<((Level, usize, usize), Vec<usize>)> = by.into_iter().filter(|(_, v)| v.len() >= MIN_MEMBERS).collect();
    // Biggest first: within a level the largest bus has the least room to move. Stable, so the
    // order is the same on every run.
    groups.sort_by_key(|(k, v)| (k.0, std::cmp::Reverse(v.len())));
    let chord = |i: usize| -> (V, V) { (board.pads[tasks[i].a].center.into(), board.pads[tasks[i].b].center.into()) };
    let free_on = |i: usize, l: usize| board.pads[tasks[i].a].layers.contains(&l) && board.pads[tasks[i].b].layers.contains(&l);
    let layers = &world.route_layers;
    // What each layer already holds, for counting crossings between buses.
    let mut placed: HashMap<usize, Vec<(V, V)>> = HashMap::new();
    for (gi, (key, members)) in groups.iter().enumerate() {
        let m = members.len();
        let conflict: Vec<Vec<bool>> = (0..m).map(|a| (0..m).map(|b| a != b && { let (p, q) = (chord(members[a]), chord(members[b])); chords_cross(p.0, p.1, q.0, q.1) }).collect()).collect();
        // The largest set that doesn't cross: fewest active conflicts first, shorter on a tie (KRT).
        let mut left: Vec<usize> = (0..m).collect();
        let mut planar: Vec<usize> = Vec::new();
        let len = |a: usize| { let c = chord(members[a]); hypot(sub(c.0, c.1)) };
        while !left.is_empty() {
            let &pick = left.iter().min_by(|&&a, &&b| {
                let count = |x: usize| left.iter().filter(|&&o| conflict[x][o]).count();
                count(a).cmp(&count(b)).then(len(a).total_cmp(&len(b)))
            }).unwrap();
            planar.push(pick);
            left.retain(|&o| o != pick && !conflict[pick][o]);
        }
        let others: Vec<usize> = (0..m).filter(|a| !planar.contains(a)).collect();
        // Which layer for the planar set? A via is dearest, then crossing other buses, then the
        // bottom: "don't hop to the bottom layer where the top works" (4.2).
        let score = |a_layer: usize, b_layer: usize| -> f64 {
            let mut s = 0.0;
            for (set, l) in [(&planar, a_layer), (&others, b_layer)] {
                for &a in set.iter() {
                    let c = chord(members[a]);
                    if !free_on(members[a], l) {
                        s += 100.0;
                    }
                    if let Some(v) = placed.get(&l) {
                        s += v.iter().filter(|q| chords_cross(c.0, c.1, q.0, q.1)).count() as f64;
                    }
                    if l != 0 {
                        s += 0.01 * (1.0 + hypot(sub(c.0, c.1)) / NM);
                    }
                }
            }
            s
        };
        let mut best: Option<(f64, usize, usize)> = None;
        for &la in layers {
            for &lb in layers {
                if layers.len() > 1 && la == lb {
                    continue;
                }
                let s = score(la, lb);
                if best.map(|b| s < b.0).unwrap_or(true) {
                    best = Some((s, la, lb));
                }
            }
        }
        let Some((_, la, lb)) = best else { continue };
        // Physical order across the bus, so each member's neighbour really is beside it.
        let (dx, dy) = planar.iter().fold((0.0, 0.0), |acc, &a| {
            let c = chord(members[a]);
            let (mut x, mut y) = (c.1 .0 - c.0 .0, c.1 .1 - c.0 .1);
            // Chords can be listed either way round; add them all facing the same way.
            if x * (acc.0 as f64) + y * (acc.1 as f64) < 0.0 {
                x = -x;
                y = -y;
            }
            (acc.0 + x, acc.1 + y)
        });
        let norm = (dx * dx + dy * dy).sqrt().max(1.0);
        let across = |a: usize| {
            let c = chord(members[a]);
            ((c.0 .0 + c.1 .0) / 2.0 * -dy + (c.0 .1 + c.1 .1) / 2.0 * dx) / norm
        };
        let mut row = planar.clone();
        row.sort_by(|&a, &b| across(a).total_cmp(&across(b)));
        if row.len() >= BAND_MIN {
    out.bands.push((la, row.iter().map(|&a| (tasks[members[a]].a, tasks[members[a]].b)).collect()));
        }
        // Middle out: each member's neighbour is the one before it, toward the middle, and no
        // member is ever walled off from its pins by the order.
        let mid = row.len() / 2;
        let mut turns: Vec<(usize, Option<usize>)> = vec![(row[mid], None)];
        for k in 1..=row.len() {
            if mid + k < row.len() {
                turns.push((row[mid + k], Some(row[mid + k - 1])));
            }
            if k <= mid {
                turns.push((row[mid - k], Some(row[mid - k + 1])));
            }
        }
        // The rest go shortest first: a line that must wrap round another's pin goes after it, so
        // they nest, as the bottom row of benchmark B's bus does.
        let mut rest = others.clone();
        rest.sort_by(|&a, &b| len(a).total_cmp(&len(b)));
        // They nest, so they run beside each other too: the next one out follows the one inside it.
        if rest.len() >= BAND_MIN {
            out.bands.push((lb, rest.iter().map(|&a| (tasks[members[a]].a, tasks[members[a]].b)).collect()));
        }
        for a in rest {
            turns.push((a, None));
        }
        let same_way = |a: usize, b: usize| {
            let (ta, tb) = (&tasks[members[a]], &tasks[members[b]]);
            cluster[board.pads[ta.a].fp] == cluster[board.pads[tb.a].fp]
        };
        for (seq, (a, near)) in turns.iter().enumerate() {
            let t = &tasks[members[*a]];
            let layer = if planar.contains(a) { la } else { lb };
            let follow = near.map(|n| {
                let o = &tasks[members[n]];
                ((o.a, o.b), !same_way(*a, n))
            });
            out.members.insert((t.a, t.b), Member { group: gi, seq, layer, free: free_on(members[*a], layer), follow });
            placed.entry(layer).or_default().push(chord(members[*a]));
        }
        let name = |c: usize| {
            let f = board.footprints.iter().enumerate().find(|(i, _)| cluster[*i] == c).map(|(_, f)| f.reference.clone()).unwrap_or_default();
            if board.footprints.iter().enumerate().filter(|(i, _)| cluster[*i] == c).count() > 1 { format!("{}..", f) } else { f }
        };
        out.notes.push(format!("bus {} to {}: {} lines, {} level, {} side by side on {}, {} on {}", name(key.1), name(key.2), m, key.0.name(), planar.len(), board.layers[la].name, others.len(), board.layers[lb].name));
    }
    out
}

/// How much of a bus's line length runs beside its neighbour in the bus: same layer, parallel, within
/// `BESIDE` of another line of the same bus. His buses move as one band of lines at 3W; lines routed one at a time fan out and cross,
/// which bends and vias don't show (benchmark B: ours had fewer bends than his and looked worse).
/// Returns (lines measured, share beside, mm measured).
pub fn coherence(board: &Board, rules: &Rules) -> (usize, f64, f64) {
    const BESIDE: f64 = 1.5 * NM;
    const STEP: f64 = 0.2 * NM;
    let mut bare = board.clone();
    bare.tracks.clear();
    bare.vias.clear();
    let mut r = rules.clone();
    r.bind(&bare);
    let p = crate::router::make_plan(&bare, &r);
    let w = crate::router::build_world(&bare, &r);
    let bp = plan(&bare, &w, &r, &p);
    let net_of = |a: usize| board.pads[a].net;
    let (mut lines, mut beside, mut total) = (0usize, 0.0, 0.0);
    for ((a, _), m) in &bp.members {
        let mine = net_of(*a);
        // Any other line of the same bus counts: the order he routes them in is his, not the plan's.
        let others: Vec<NetId> = bp.members.iter().filter(|((x, _), o)| o.group == m.group && net_of(*x) != mine).map(|((x, _), _)| net_of(*x)).collect();
        let segs_of = |n: NetId| board.tracks.iter().filter(move |t| t.net == n);
        let theirs: Vec<&Track> = board.tracks.iter().filter(|t| others.contains(&t.net)).collect();
        lines += 1;
        for s in segs_of(mine) {
            let (sa, sb): (V, V) = (s.a.into(), s.b.into());
            let len = hypot(sub(sa, sb));
            if len < 1.0 {
                continue;
            }
            let d = dir_of(s.a, s.b);
            let k = (len / STEP).ceil().max(1.0) as usize;
            for i in 0..k {
                let t = (i as f64 + 0.5) / k as f64;
                let pt = V(sa.0 + (sb.0 - sa.0) * t, sa.1 + (sb.1 - sa.1) * t);
                total += len / k as f64;
                let near = theirs.iter().any(|o| {
                    o.layer == s.layer && pt_seg(pt, o.a.into(), o.b.into()) <= BESIDE && match (d, dir_of(o.a, o.b)) {
                        (Some(x), Some(y)) => x % 4 == y % 4,
                        _ => false,
                    }
                });
                if near {
                    beside += len / k as f64;
                }
            }
        }
    }
    (lines, if total > 0.0 { beside / total } else { 0.0 }, total / NM)
}

/// How close a GND via counts as close by. His benchmark C has one within this of 48 of its 61 signal vias.
const RETURN_REACH: f64 = 1.5 * NM;

impl<'a> Router<'a> {
    /// "Any signal via benefits from a GND via close by, when possible" (4.4): once every route is
    /// done, so nothing moved for it (lowest priority, like stitching), a GND via next to each signal
    /// via that lacks one, wherever one fits. It reaches the plane by itself.
    pub(crate) fn return_vias(&mut self) {
        let planes = self.board.plane_nets();
        let Some(&gnd) = planes.keys().find(|&&n| looks_ground(self.board.net_name(n))) else { return };
        let Some(pad) = self.board.pads.iter().position(|p| p.net == gnd && !p.layers.is_empty()) else { return };
        let plane_at = |p: V, world: &World| world.zones.iter().any(|(n, _, poly)| *n == gnd && in_poly(p, poly));
        let task = Task { net: gnd, level: Level::PlaneFanout, a: pad, b: pad, main: false, zone: None };
        // A through pin on the plane is a return path as good as a via.
        let mut returns: Vec<V> = self.board.pads.iter().filter(|p| p.net == gnd && p.drill.is_some() && !p.npth).map(|p| p.center.into()).collect();
        let mut gnd_vias: Vec<V> = self.board.vias.iter().filter(|v| v.net == gnd).map(|v| v.at.into()).collect();
        let mut signal: Vec<(u32, P)> = Vec::new();
        for r in self.routes.values() {
            if r.task.net == gnd {
                gnd_vias.extend(r.vias.iter().map(|&v| V::from(v)));
            } else if !matches!(r.task.level, Level::Power) {
                signal.extend(r.vias.iter().map(|&v| (r.id, v)));
            }
        }
        signal.sort();
        returns.extend(gnd_vias.iter().copied());
        let close = |set: &[V], v: P| set.iter().any(|g| hypot(sub(*g, v.into())) <= RETURN_REACH);
        let total = signal.len();
        let before = signal.iter().filter(|(_, v)| close(&gnd_vias, *v)).count();
        let vr = self.rules.via as f64 / 2.0;
        let mut added = 0;
        let mut boxed = 0;
        for (_, v) in &signal {
            if close(&returns, *v) {
                continue;
            }
            let c: V = (*v).into();
            let profile = Profile { width: 0, neck: 0, clearance: self.rules.clearance_for(gnd, gnd), target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None };
            let q = Query { net: gnd, also: None, sources: &[], targets: &[], profile, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
            let mut site = None;
            let mut radius = 2.0 * vr + self.rules.hole_hole as f64;
            'look: while radius <= RETURN_REACH {
                for k in 0..16 {
                    let a = k as f64 / 16.0 * std::f64::consts::TAU;
                    let at = crate::search::snap(to_p(V(c.0 + radius * a.cos(), c.1 + radius * a.sin())));
                    let (mut b, mut sc) = (Vec::new(), 0.0);
                    if plane_at(at.into(), &self.world) && self.world.via_ok(at, &q, None, &mut b, &mut sc) {
                        site = Some(at);
                        break 'look;
                    }
                }
                radius += 0.05 * NM;
            }
            let Some(at) = site else {
                boxed += 1;
                continue;
            };
            let id = self.fresh_id();
            self.place(id, task.clone(), Vec::new(), vec![at]);
            returns.push(at.into());
            gnd_vias.push(at.into());
            added += 1;
        }
        let after = signal.iter().filter(|(_, v)| close(&gnd_vias, *v)).count();
        self.log.push(format!("return vias: {after} of {total} signal vias have a GND via within {:.1} mm ({before} before; {added} added, {boxed} with no room)", RETURN_REACH / NM));
    }
}

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

    /// His benchmark B: 26 lines from the module to the contact row. The lines that keep their order run
    /// together; the bottom row, which is reversed against the contacts, goes on the other layer, as
    /// he routed it.
    #[test]
    fn benchmark_b_splits_its_bus_the_way_the_designer_did() {
        let path = format!("{}/bench/boards/benchb_v210.ref.kicad_pcb", env!("CARGO_MANIFEST_DIR"));
        if !std::path::Path::new(&path).exists() {
            eprintln!("skipped: {path} is not here (the reference boards do not ship with the source)");
            return;
        }
        let mut b = Board::read(&path).unwrap();
        b.tracks.clear();
        b.vias.clear();
        let mut r = Rules::default();
        crate::project::apply(&path, &mut r);
        let p = crate::router::make_plan(&b, &r);
        let w = crate::router::build_world(&b, &r);
        let bus = plan(&b, &w, &r, &p);
        let layer_of = |net: &str| {
            let id = b.net_ids[net];
            let t = p.tasks.iter().find(|t| t.net == id).unwrap();
            bus.members[&(t.a, t.b)].layer
        };
        for n in ["/USER_IO.13", "/USER_IO.16", "/USER_IO.22", "/USER_IO.27"] {
            assert_eq!(layer_of(n), 0, "{n} should be with the bus on F.Cu");
        }
        // Everything with its pins in the reversed order is not on the bus's layer, bar the one it
        // can keep. Pairwise reversal means at most one stays.
        let top = ["/USER_IO.0", "/USER_IO.1", "/USER_IO.2", "/USER_IO.3", "/USER_IO.4", "/USER_IO.5"].iter().filter(|n| layer_of(n) == 0).count();
        assert!(top <= 1, "{top} of the reversed lines stayed on the top");
    }

    #[test]
    fn piprobe_finds_the_qspi_bus() {
        let path = format!("{}/bench/boards/piprobe_v13.ref.kicad_pcb", env!("CARGO_MANIFEST_DIR"));
        if !std::path::Path::new(&path).exists() {
            eprintln!("skipped: {path} is not here (the reference boards do not ship with the source)");
            return;
        }
        let mut b = Board::read(&path).unwrap();
        b.tracks.clear();
        b.vias.clear();
        let mut r = Rules::default();
        crate::project::apply(&path, &mut r);
        let p = crate::router::make_plan(&b, &r);
        let w = crate::router::build_world(&b, &r);
        let bus = plan(&b, &w, &r, &p);
        let qspi: Vec<_> = p.tasks.iter().filter(|t| b.net_name(t.net).starts_with("QSPI_") && bus.members.contains_key(&(t.a, t.b))).collect();
        assert!(qspi.len() >= 6, "{} QSPI lines in a bus", qspi.len());
        // SMD on one side: no line may be pushed to the other layer without a via, so none is held.
        assert!(qspi.iter().all(|t| bus.members[&(t.a, t.b)].layer == 0 || !bus.members[&(t.a, t.b)].free));
    }
}