AI Flow: Routing

//! Breathing room (reference rule, 2026-11-09: "first routing everything completely then circling back and
//! optimizing spacing where it is possible"; he gives traces as much room as there is). Once every
//! connection is down, each middle piece of a track slides sideways, its two neighbours stretching
//! or shrinking along their own directions so every angle stays, to where its room to the nearest
//! other copper is largest. Repeated, lines packed at the routing pitch spread out evenly across
//! the channel they share. Nothing is re-routed: topology, layers and vias stay as routed.
//!
//! Widths are not touched here: a track's width comes from the current through it (current.rs), at
//! routing time, so a rail never necks from one arbitrary width to another.

use crate::board::*;
use crate::classify::*;
use crate::geom::*;
use crate::router::*;
use crate::search::*;
use crate::clock::Instant;

/// Room past which more is not worth moving copper for: his benchmark B bus has a median of 1.59 mm
/// centre to centre at 0.2 mm wide, about 1.4 mm of edge room.
const ROOM: f64 = 1.4 * NM;
/// Slide step and the farthest one piece goes in one pass.
const STEP: i64 = 25_000;
const MAX_SHIFT: i64 = 1_500_000;
/// Extra copper is worth this share of full room per unit length: 1 mm more track must buy at
/// least 0.05 mm of room along a millimetre.
const LEN_COST: f64 = 0.05;
/// A neighbour piece keeps at least this much of itself, or its own length if shorter.
const KEEP: i64 = 300_000;
const PASSES: usize = 8;

impl<'a> Router<'a> {
    pub(crate) fn spread(&mut self) {
        let t0 = Instant::now();
        let (mut moves, mut passes, mut undone) = (0usize, 0usize, 0usize);
        let mut gained = 0.0;
        for _ in 0..PASSES {
            passes += 1;
            let mut moved = 0usize;
            let mut ids: Vec<u32> = self.routes.values().filter(|r| !matches!(r.task.level, Level::Pair | Level::Kelvin | Level::PlaneFanout) && r.segs.len() >= 3).map(|r| r.id).collect();
            ids.sort_unstable();
            for id in ids {
                if self.over_time() {
                    break;
                }
                let (net, vias, mut cur) = {
                    let r = &self.routes[&id];
                    (r.task.net, r.vias.clone(), r.segs.clone())
                };
                // What else of the net lands on this track: other connections' ends, taps, vias,
                // the net's pads. A piece any of it touches stays, or the net comes apart.
                let mut held: Vec<V> = Vec::new();
                for r in self.routes.values().filter(|r| r.task.net == net && r.id != id) {
                    for sg in &r.segs {
                        held.push(sg.a.into());
                        held.push(sg.b.into());
                    }
                    held.extend(r.vias.iter().map(|&v| V::from(v)));
                }
                held.extend(self.board.pads.iter().filter(|pd| pd.net == net).map(|pd| V::from(pd.center)));
                let mut changed = false;
                for k in 1..cur.len() - 1 {
                    let own_other = |j: usize| j + 1 < k || j > k + 1;
                    let touched = |sg: &Seg| {
                        let (a, b): (V, V) = (sg.a.into(), sg.b.into());
                        held.iter().any(|h| pt_seg(*h, a, b) < 2_000.0) || cur.iter().enumerate().filter(|(j, _)| own_other(*j)).any(|(_, o)| pt_seg(o.a.into(), a, b) < 2_000.0 || pt_seg(o.b.into(), a, b) < 2_000.0)
                    };
                    // The pad a stub starts on is its own end and stays: only the far piece ends count.
                    let p_mid = { let sg = &cur[k - 1]; let (a, b): (V, V) = (sg.a.into(), sg.b.into()); held.iter().any(|h| pt_seg(*h, a, b) < 2_000.0 && hypot(sub(*h, a)) > 2_000.0) || cur.iter().enumerate().filter(|(j, _)| own_other(*j) && *j + 2 != k).any(|(_, o)| { let (oa, ob): (V, V) = (o.a.into(), o.b.into()); pt_seg(oa, a, b) < 2_000.0 || pt_seg(ob, a, b) < 2_000.0 }) };
                    let q_mid = { let sg = &cur[k + 1]; let (a, b): (V, V) = (sg.a.into(), sg.b.into()); held.iter().any(|h| pt_seg(*h, a, b) < 2_000.0 && hypot(sub(*h, b)) > 2_000.0) || cur.iter().enumerate().filter(|(j, _)| own_other(*j) && *j != k + 2).any(|(_, o)| { let (oa, ob): (V, V) = (o.a.into(), o.b.into()); pt_seg(oa, a, b) < 2_000.0 || pt_seg(ob, a, b) < 2_000.0 }) };
                    if touched(&cur[k]) || p_mid || q_mid {
                        continue;
                    }
                    if let Some((a2, b2, g)) = self.slide(&cur, k, net, &vias) {
                        cur[k - 1].b = a2;
                        cur[k].a = a2;
                        cur[k].b = b2;
                        cur[k + 1].a = b2;
                        changed = true;
                        moved += 1;
                        gained += g;
                    }
                }
                if changed {
                    // Whole or not at all: a track can touch its net's copper anywhere along its
                    // width (a pad it crosses off-centre, a track it overlaps), which the held points
                    // above don't see. If the net has more pieces after the move, the move is undone.
                    let before = self.open_pieces(net);
                    let doubled = |me: &Self| -> f64 { let r = &me.routes[&id]; (0..r.segs.len()).map(|i| me.doubled_along(r, i)).sum() };
                    let doubled_before = doubled(self);
                    let saved = self.unplace(id).unwrap();
                    let (sid, task, old, vias) = (saved.id, saved.task.clone(), saved.segs.clone(), saved.vias.clone());
                    self.place(sid, task.clone(), cur, vias.clone());
                    // Nor may it end up running beside its own net's copper (4.2's doubled runs).
                    if self.open_pieces(net) > before || doubled(self) > doubled_before + 1.0 {
                        self.unplace(sid);
                        self.place(sid, task, old, vias);
                        undone += 1;
                    }
                }
            }
            moves += moved;
            if moved == 0 || self.over_time() {
                break;
            }
        }
        self.log.push(format!("spacing: {moves} track pieces moved for room in {passes} passes, {:.1} mm2 of room gained (room x length, up to {:.1} mm), {:.1} s; {undone} moves undone to keep a net whole", gained / NM / NM, ROOM / NM, t0.elapsed().as_secs_f64()));
    }

    /// Where piece `k` of a track does best, if better than where it is: its new ends and the room
    /// it gained.
    fn slide(&self, segs: &[Seg], k: usize, net: NetId, vias: &[P]) -> Option<(P, P, f64)> {
        let (p, s, q) = (&segs[k - 1], &segs[k], &segs[k + 1]);
        if p.b != s.a || s.b != q.a || p.layer != s.layer || q.layer != s.layer || vias.contains(&s.a) || vias.contains(&s.b) {
            return None;
        }
        let (ds, dp, dq) = (dir_of(s.a, s.b)?, dir_of(p.a, p.b)?, dir_of(q.a, q.b)?);
        let (sx, sy) = DIRS[ds as usize];
        let l = ((sx * sx + sy * sy) as f64).sqrt();
        let n = (-(sy as f64) / l, sx as f64 / l);
        let (px, py) = DIRS[dp as usize];
        let (qx, qy) = DIRS[dq as usize];
        let dot_p = px as f64 * n.0 + py as f64 * n.1;
        let dot_q = qx as f64 * n.0 + qy as f64 * n.1;
        if dot_p.abs() < 1e-6 || dot_q.abs() < 1e-6 {
            return None;
        }
        let layer = s.layer;
        let half = s.width as f64 / 2.0;
        let reach = ROOM + half + 1.0;
        let len = |a: P, b: P| hypot(sub(a.into(), b.into()));
        // How far short of full room a piece is along its length (mm of room times mm of track):
        // a long line pinched only by the pad at its end still has its whole middle to gain.
        let short = |a: P, b: P, w: i64| -> (f64, f64) {
            let (va, vb): (V, V) = (a.into(), b.into());
            let l = hypot(sub(va, vb));
            let k = ((l / (0.4 * NM)).ceil() as usize).max(1);
            let (mut sum, mut least) = (0.0, f64::INFINITY);
            for i in 0..k {
                let (t0, t1) = (i as f64 / k as f64, (i + 1) as f64 / k as f64);
                let pa = V(va.0 + (vb.0 - va.0) * t0, va.1 + (vb.1 - va.1) * t0);
                let pb = V(va.0 + (vb.0 - va.0) * t1, va.1 + (vb.1 - va.1) * t1);
                let r = (self.world.room(&self.rules, layer, pa, pb, net, reach) - w as f64 / 2.0).min(ROOM);
                least = least.min(r);
                sum += (ROOM - r) * l / k as f64;
            }
            (sum, least)
        };
        let ((sp, mp), (ss, ms), (sq, mq)) = (short(p.a, p.b, p.width), short(s.a, s.b, s.width), short(q.a, q.b, q.width));
        let before = sp + ss + sq;
        if ss <= 1.0 {
            return None;
        }
        let total0 = len(p.a, p.b) + len(s.a, s.b) + len(q.a, q.b);
        let keep = |a: P, b: P| (len(a, b) as i64).min(KEEP);
        let (keep_p, keep_q, keep_s) = (keep(p.a, p.b), keep(q.a, q.b), keep(s.a, s.b));
        let mut best: Option<(f64, P, P, f64)> = None;
        for sign in [1i64, -1] {
            let mut off = STEP;
            while off <= MAX_SHIFT {
                let o = (sign * off) as f64;
                let (ka, kb) = ((o / dot_p).round() as i64, (o / dot_q).round() as i64);
                let a2 = (s.a.0 + ka * px, s.a.1 + ka * py);
                let b2 = (s.b.0 + kb * qx, s.b.1 + kb * qy);
                // Every angle stays: each piece keeps its direction, and none shrinks away (a chamfer slid
                // into its corner turns back into a 90-degree bend).
                let ok_shape = dir_of(a2, b2) == Some(ds) && dir_of(p.a, a2) == Some(dp) && dir_of(b2, q.b) == Some(dq) && len(p.a, a2) as i64 >= keep_p && len(b2, q.b) as i64 >= keep_q && len(a2, b2) as i64 >= keep_s;
                if !ok_shape {
                    break;
                }
                if !self.seg_clear(p.a, a2, layer, p.width, net, NO_NET) || !self.seg_clear(a2, b2, layer, s.width, net, NO_NET) || !self.seg_clear(b2, q.b, layer, q.width, net, NO_NET) {
                    break;
                }
                let ((sp2, mp2), (ss2, ms2), (sq2, mq2)) = (short(p.a, a2, p.width), short(a2, b2, s.width), short(b2, q.b, q.width));
                // No piece's tightest point gets tighter: room is gained, never traded.
                if mp2 + 1.0 >= mp.min(ROOM) && ms2 + 1.0 >= ms.min(ROOM) && mq2 + 1.0 >= mq.min(ROOM) {
                    let extra = len(p.a, a2) + len(a2, b2) + len(b2, q.b) - total0;
                    let cost = sp2 + ss2 + sq2 + LEN_COST * ROOM * extra.max(0.0);
                    if best.map(|b| cost < b.0).unwrap_or(true) {
                        best = Some((cost, a2, b2, before - (sp2 + ss2 + sq2)));
                    }
                }
                off += STEP;
            }
        }
        let (cost, a2, b2, gain) = best?;
        // Worth moving only for a real gain: 0.01 mm of room over a millimetre of track is noise.
        (cost + 0.01 * NM * NM < before).then_some((a2, b2, gain))
    }
}