AI Flow: Routing

//! The power stage's plan: each rated rail worked out as a whole before any copper is laid.
//!
//! A rail's widths depend on the whole rail (where the source is, which loads hang off which
//! branch), so they cannot be found one connection at a time and patched after. Per rail:
//!
//! 1. A tree from the source. Loads join heaviest first, each to the nearest part already in the
//!    tree; parts that draw nothing (capacitors, test points, pull-ups) join last, each to the
//!    part nearest it, which is its own IC.
//! 2. Each branch's current: its part's draw and everything hanging off it, never over the rail's.
//! 3. Each branch's width: the larger of the chart's width for that current and its share of the
//!    drop limit. Along a load's path the limit is shared so the copper used is least, which is
//!    width in proportion to the square root of the current. A pad narrower than the branch costs
//!    a short neck, and that neck's drop comes out of the limit first.
//! 4. What each part's tap may land on: its own part's pads and the copper of the parts above it
//!    in the tree. That is what makes the planned currents true of the copper as laid.
//!
//! Rails fed by their pour are not planned: there every pad draws its own from the pour.

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

pub struct PadPlan {
    pub width: i64,
    pub amps: f64,
    /// Pads this pad's tap may land on (or on copper routed from them).
    pub allowed: HashSet<usize>,
    /// A part drawing under a hundredth of its rail (a pull-up, a capacitor, a test point) may land
    /// on any of the rail's copper: what it adds to a branch is nothing next to that branch's own.
    pub anywhere: bool,
}

#[derive(Default)]
pub struct PowerPlan {
    pub pads: HashMap<usize, PadPlan>,
    /// Per rail, the pads to tap, in the order to lay them: the tree from the source outward.
    pub order: Vec<(NetId, Vec<usize>)>,
    /// Per rail, its source parts' pads: a tap lands only on copper already joined to one of them,
    /// so the rail grows from its source and two unjoined parts never end up joined to each other.
    pub sources: HashMap<NetId, HashSet<usize>>,
    pub notes: Vec<String>,
}

/// The share of the drop limit the plan spends. The rest is for what the plan can't see: copper
/// runs longer than the straight distance it is planned on, and vias on the way add their own drop.
const PLAN_SHARE: f64 = 0.9;

fn oct(p: P, q: P) -> f64 {
    let (dx, dy) = ((p.0 - q.0).abs() as f64, (p.1 - q.1).abs() as f64);
    dx.max(dy) + (std::f64::consts::SQRT_2 - 1.0) * dx.min(dy)
}

pub fn plan(board: &Board, rules: &Rules, pour_fed: &HashSet<NetId>) -> PowerPlan {
    let mut out = PowerPlan::default();
    for (name, rail) in &rules.rails {
        let Some(net) = board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v) else { continue };
        if pour_fed.contains(&net) {
            continue;
        }
        // Parts on the rail, in footprint order (the same on every run).
        let mut parts: Vec<(usize, Vec<usize>)> = Vec::new();
        for (i, p) in board.pads.iter().enumerate().filter(|(_, p)| p.net == net && !p.layers.is_empty()) {
            match parts.iter_mut().find(|(fp, _)| *fp == p.fp) {
                Some((_, pads)) => pads.push(i),
                None => parts.push((p.fp, vec![i])),
            }
        }
        let n = parts.len();
        let refname = |k: usize| board.footprints[parts[k].0].reference.as_str();
        let is_source = |k: usize| rail.sources.iter().any(|s| s == refname(k));
        if !(0..n).any(is_source) {
            continue;
        }
        let load = |k: usize| if is_source(k) { 0.0 } else { rail.loads.get(refname(k)).copied().unwrap_or(0.0) };
        let nearest = |a: usize, b: usize| -> (f64, usize, usize) {
            let mut best = (f64::INFINITY, parts[a].1[0], parts[b].1[0]);
            for &x in &parts[a].1 {
                for &y in &parts[b].1 {
                    let d = oct(board.pads[x].center, board.pads[y].center);
                    if d < best.0 {
                        best = (d, x, y);
                    }
                }
            }
            best
        };
        let mut joined: Vec<usize> = (0..n).filter(|&k| is_source(k)).collect();
        let mut parent: Vec<Option<usize>> = vec![None; n];
        let mut edge: Vec<(f64, usize)> = vec![(0.0, 0); n]; // (length, the part's pad nearest its parent)
        let mut order: Vec<usize> = Vec::new();
        let mut join = |k: usize, joined: &mut Vec<usize>, parent: &mut Vec<Option<usize>>, edge: &mut Vec<(f64, usize)>, order: &mut Vec<usize>| {
            let (d, mine, par) = joined.iter().map(|&j| { let (d, x, _) = nearest(k, j); (d, x, j) }).min_by(|a, b| a.0.total_cmp(&b.0).then(a.2.cmp(&b.2))).unwrap();
            parent[k] = Some(par);
            edge[k] = (d, mine);
            joined.push(k);
            order.push(k);
        };
        let mut loads: Vec<usize> = (0..n).filter(|&k| !is_source(k) && load(k) > 0.0).collect();
        loads.sort_by(|&a, &b| load(b).total_cmp(&load(a)).then(refname(a).cmp(refname(b))));
        for k in loads.clone() {
            join(k, &mut joined, &mut parent, &mut edge, &mut order);
        }
        let mut idle: Vec<usize> = (0..n).filter(|&k| !is_source(k) && load(k) <= 0.0).collect();
        while !idle.is_empty() {
            let (pos, _) = idle.iter().enumerate().map(|(pos, &k)| (pos, joined.iter().map(|&j| nearest(k, j).0).fold(f64::INFINITY, f64::min))).min_by(|a, b| a.1.total_cmp(&b.1).then(a.0.cmp(&b.0))).unwrap();
            let k = idle.remove(pos);
            join(k, &mut joined, &mut parent, &mut edge, &mut order);
        }
        let mut amps: Vec<f64> = (0..n).map(load).collect();
        for &k in order.iter().rev() {
            if let Some(p) = parent[k] {
                amps[p] += amps[k];
            }
        }
        for a in amps.iter_mut() {
            *a = a.min(rail.amps);
        }
        let class = rules.track_for(net);
        let plain = if class > mm(0.3) { rules.track } else { class };
        let mut width: Vec<i64> = (0..n).map(|k| rules.rail_width(amps[k], false).max(plain)).collect();
        // The drop limit, shared along each load's path.
        if let Some(volts) = rail.volts {
            let t_cu = rules.copper_um * 1e-6;
            let clearance = rules.clearance_for(net, net) as f64;
            for &l in &loads {
                let mut path: Vec<usize> = Vec::new();
                let mut k = l;
                while let Some(p) = parent[k] {
                    path.push(k);
                    k = p;
                }
                let share: f64 = path.iter().map(|&k| edge[k].0 * 1e-9 * amps[k].sqrt()).sum();
                let budget = volts * DROP_LIMIT * PLAN_SHARE;
                let need = |b: f64, k: usize| amps[k].sqrt() * share * RHO_CU / (t_cu * b);
                // The last stretch into a pad narrower than the branch runs at the pad's width.
                let pad = &board.pads[edge[l].1];
                let pad_w = pad.size.0.min(pad.size.1) * 1e-9;
                let first = need(budget, l);
                // A pad inside its own rail's pour needs no neck: the pour carries the current to
                // the pin, and the branch ends on the pour (reference benchmark C does this at U10).
                let c: V = pad.center.into();
                let in_pour = board.zones.iter().any(|z| z.net == net && !z.keepout_tracks && (in_poly(c, &z.outline) || z.fills.iter().any(|(_, f)| in_poly(c, f))));
                let neck = if in_pour { 0.0 } else if first > pad_w && pad_w > 0.0 { amps[l] * RHO_CU * (first / 2.0 + clearance * 1e-9 + 0.3e-3) / (pad_w * t_cu) } else { 0.0 };
                let left = (budget - neck).max(0.3 * budget);
                for &k in &path {
                    let w = mm((need(left, k) * 1000.0 * 100.0).ceil() / 100.0);
                    width[k] = width[k].max(w);
                }
            }
        }
        // What each part may land on: its own pads and those of every part above it.
        let mut taps: Vec<usize> = Vec::new();
        let mut line: Vec<String> = Vec::new();
        for &k in &order {
            let mut allowed: HashSet<usize> = parts[k].1.iter().copied().collect();
            let mut up = parent[k];
            while let Some(p) = up {
                allowed.extend(parts[p].1.iter().copied());
                up = parent[p];
            }
            for &pad in &parts[k].1 {
                out.pads.insert(pad, PadPlan { width: width[k], amps: amps[k], allowed: allowed.clone(), anywhere: amps[k] < 0.01 * rail.amps });
            }
            taps.push(edge[k].1);
            taps.extend(parts[k].1.iter().copied().filter(|&p| p != edge[k].1));
            if amps[k] > 0.0 {
                line.push(format!("{} {:.3} A over {:.1} mm from {} at {:.2} mm", refname(k), amps[k], edge[k].0 / NM, refname(parent[k].unwrap()), to_mm(width[k])));
            }
        }
        out.notes.push(format!("power plan {name}: {}; {} parts with no load of their own at {:.2} mm", line.join("; "), order.iter().filter(|&&k| amps[k] <= 0.0).count(), to_mm(plain)));
        out.sources.insert(net, (0..n).filter(|&k| is_source(k)).flat_map(|k| parts[k].1.iter().copied()).collect());
        out.order.push((net, taps));
    }
    out
}