AI Flow: Routing

//! Net by net against a reference board: length, vias, layers, widths, bends and spacing. The designer's
//! finished boards are the grade (4.6), so this is how cost weights are calibrated: change a weight,
//! route, compare, and keep it only if the board moves toward the reference copper. Reads only the two files.

use crate::board::*;
use crate::classify::*;
use crate::conn;
use crate::geom::*;
use crate::index::*;
use crate::router::build_world;
use crate::rules::Rules;
use serde_json::{json, Value};
use std::collections::{BTreeMap, HashMap};

#[derive(Default, Clone, Debug)]
pub struct NetStat {
    pub level: String,
    pub len: f64,
    pub top: f64,
    pub bottom: f64,
    pub vias: usize,
    pub bends45: usize,
    pub bends90: usize,
    /// Copper length per width in mm, keyed by the width in microns.
    pub widths: BTreeMap<i64, f64>,
    /// The shortest octilinear tree over the net's pads (lower bound for its copper).
    pub tree: f64,
    pub open: usize,
    /// Places where the width changes along a run.
    pub steps: usize,
    /// Same-net tracks running side by side: within 0.4 mm centre to centre, for 0.3 mm or more.
    pub doubled: usize,
}

/// Length-weighted spacing, over copper outside fine-pitch escapes and inside them.
#[derive(Default, Clone, Debug)]
pub struct Spacing {
    pub open_total: f64,
    pub open_3w: f64,
    pub open_2w: f64,
    pub open_min: f64,
    pub esc_total: f64,
    pub data_open_total: f64,
    pub data_open_in_band: f64,
    pub data_open_neck: f64,
}

fn octile(a: V, b: V) -> f64 {
    let (dx, dy) = ((a.0 - b.0).abs(), (a.1 - b.1).abs());
    let (hi, lo) = if dx > dy { (dx, dy) } else { (dy, dx) };
    (hi - lo) + lo * SQRT2
}

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

/// Prim over the net's pads, octile metric: the length a straight daisy chain could not beat by much.
fn tree_len(board: &Board, pads: &[usize]) -> f64 {
    if pads.len() < 2 {
        return 0.0;
    }
    let c: Vec<V> = pads.iter().map(|&p| board.pads[p].center.into()).collect();
    let mut best: Vec<f64> = c.iter().map(|&x| octile(x, c[0])).collect();
    let mut done = vec![false; c.len()];
    done[0] = true;
    let mut total = 0.0;
    for _ in 1..c.len() {
        let (i, d) = best.iter().enumerate().filter(|(i, _)| !done[*i]).map(|(i, d)| (i, *d)).min_by(|a, b| a.1.total_cmp(&b.1)).unwrap();
        total += d;
        done[i] = true;
        for j in 0..c.len() {
            best[j] = best[j].min(octile(c[i], c[j]));
        }
    }
    total
}

pub fn measure(board: &Board, rules: &Rules) -> (BTreeMap<String, NetStat>, Spacing) {
    let infos = classify(board, rules);
    let groups = conn::pad_groups(board, &[]);
    let world = build_world(board, rules);
    let mut out: BTreeMap<String, NetStat> = BTreeMap::new();
    let mut level_of: HashMap<NetId, Level> = HashMap::new();
    for i in &infos {
        let live = groups.get(&i.net).map(|g| g.iter().filter(|grp| grp.iter().any(|p| i.pads.contains(p))).count()).unwrap_or(0);
        level_of.insert(i.net, i.level);
        out.insert(board.net_name(i.net).to_string(), NetStat { level: i.level.name().to_string(), tree: tree_len(board, &i.pads) / NM, open: live.saturating_sub(1), ..Default::default() });
    }
    let last = board.layers.len() - 1;
    for t in &board.tracks {
        let e = out.entry(board.net_name(t.net).to_string()).or_default();
        let l = hypot(sub(t.a.into(), t.b.into())) / NM;
        e.len += l;
        if t.layer == 0 {
            e.top += l;
        } else if t.layer == last {
            e.bottom += l;
        }
        *e.widths.entry(t.width / 1000).or_insert(0.0) += l;
    }
    for v in &board.vias {
        out.entry(board.net_name(v.net).to_string()).or_default().vias += 1;
    }
    // Bends: a node on one layer with exactly two tracks, not hidden in a pad or its own fill.
    let mut nodes: HashMap<(NetId, usize, P), Vec<(P, P)>> = HashMap::new();
    let mut widths: HashMap<(NetId, usize, P), Vec<i64>> = HashMap::new();
    for t in &board.tracks {
        if t.a != t.b {
            nodes.entry((t.net, t.layer, key(t.a))).or_default().push((t.a, t.b));
            nodes.entry((t.net, t.layer, key(t.b))).or_default().push((t.b, t.a));
            widths.entry((t.net, t.layer, key(t.a))).or_default().push(t.width);
            widths.entry((t.net, t.layer, key(t.b))).or_default().push(t.width);
        }
    }
    for (k, w) in &widths {
        if w.len() == 2 && w[0] != w[1] {
            out.entry(board.net_name(k.0).to_string()).or_default().steps += 1;
        }
    }
    for (i, t) in board.tracks.iter().enumerate() {
        for o in board.tracks[i + 1..].iter().filter(|o| o.net == t.net && o.layer == t.layer) {
            if side_by_side(t, o) {
                out.entry(board.net_name(t.net).to_string()).or_default().doubled += 1;
            }
        }
    }
    for ((net, layer, _), list) in &nodes {
        if list.len() != 2 {
            continue;
        }
        let at: V = list[0].0.into();
        let hidden = board.pads.iter().any(|q| q.net == *net && q.layers.contains(layer) && q.shape.dist_pt(at) <= 0.25 * NM) || world.zones.iter().any(|(zn, zl, poly)| zn == net && zl == layer && in_poly(at, poly));
        if hidden {
            continue;
        }
        let ang = |x: (P, P)| ((x.1 .1 - x.0 .1) as f64).atan2((x.1 .0 - x.0 .0) as f64).to_degrees();
        let d = (ang(list[0]) - ang(list[1])).rem_euclid(360.0);
        let turn = 180.0 - d.min(360.0 - d);
        let e = out.entry(board.net_name(*net).to_string()).or_default();
        if (turn - 45.0).abs() < 3.0 {
            e.bends45 += 1;
        } else if (turn - 90.0).abs() < 3.0 {
            e.bends90 += 1;
        }
    }
    (out, spacing(board, rules, &world, &level_of))
}

/// Of the signal vias, how many have a via of a plane net within `reach` (4.4: any signal via benefits
/// from a GND via close by). Returns (with one close by, all signal vias).
pub fn vias_near_ground(board: &Board, reach: f64) -> (usize, usize) {
    let planes = board.plane_nets();
    let ground: Vec<V> = board.vias.iter().filter(|v| planes.contains_key(&v.net)).map(|v| v.at.into()).collect();
    let power: Vec<&Via> = board.vias.iter().filter(|v| !planes.contains_key(&v.net) && !looks_power(board.net_name(v.net))).collect();
    let near = power.iter().filter(|v| ground.iter().any(|g| hypot(sub(*g, v.at.into())) <= reach)).count();
    (near, power.len())
}

fn side_by_side(t: &Track, o: &Track) -> bool {
    let (a, b): (V, V) = (t.a.into(), t.b.into());
    let (c, d): (V, V) = (o.a.into(), o.b.into());
    let (l, m) = (hypot(sub(b, a)), hypot(sub(d, c)));
    if l < 1.0 || m < 1.0 {
        return false;
    }
    let u = V((b.0 - a.0) / l, (b.1 - a.1) / l);
    if ((d.1 - c.1) / m * u.0 - (d.0 - c.0) / m * u.1).abs() > 0.02 {
        return false;
    }
    let off = ((c.0 - a.0) * -u.1 + (c.1 - a.1) * u.0).abs();
    let t0 = (c.0 - a.0) * u.0 + (c.1 - a.1) * u.1;
    let t1 = (d.0 - a.0) * u.0 + (d.1 - a.1) * u.1;
    off <= 0.4 * NM && l.min(t0.max(t1)) - t0.min(t1).max(0.0) >= 0.3 * NM
}

/// Walks all copper in small steps and buckets each step by its distance to other nets. 3W and 2W
/// are measured on the track's own width, as 4.2 states them. Fills are skipped: they refill around
/// tracks, so a gap to one says nothing about the routing.
fn spacing(board: &Board, rules: &Rules, world: &crate::search::World, level_of: &HashMap<NetId, Level>) -> Spacing {
    let mut s = Spacing::default();
    let step = 0.2 * NM;
    for t in &board.tracks {
        let (a, b): (V, V) = (t.a.into(), t.b.into());
        let len = hypot(sub(a, b));
        let n = (len / step).ceil().max(1.0) as usize;
        let half = t.width as f64 / 2.0;
        for i in 0..n {
            let (u, v) = (i as f64 / n as f64, (i + 1) as f64 / n as f64);
            let p = V(a.0 + (b.0 - a.0) * u, a.1 + (b.1 - a.1) * u);
            let q = V(a.0 + (b.0 - a.0) * v, a.1 + (b.1 - a.1) * v);
            let piece = len / n as f64 / NM;
            let m = V((p.0 + q.0) / 2.0, (p.1 + q.1) / 2.0);
            if world.in_escape(m) {
                s.esc_total += piece;
                continue;
            }
            let reach = half + t.width as f64 * 3.0 + 1000.0;
            let bb = (p.0.min(q.0) - reach, p.1.min(q.1) - reach, p.0.max(q.0) + reach, p.1.max(q.1) + reach);
            let mut gap = f64::INFINITY;
            world.layers[t.layer].visit(bb, |o| {
                if o.net != t.net && !matches!(o.owner, Owner::Zone(_)) {
                    gap = gap.min(o.shape.dist_seg(p, q) - half);
                }
                true
            });
            s.open_total += piece;
            let w = t.width as f64;
            // 3W and 2W are centre to centre: 3W leaves a gap of 2W, 2W a gap of 1W (4.2).
            if gap >= w * 2.0 - 1000.0 {
                s.open_3w += piece;
            } else if gap >= w - 1000.0 {
                s.open_2w += piece;
            } else {
                s.open_min += piece;
            }
            if matches!(level_of.get(&t.net), Some(Level::Data) | Some(Level::Other)) {
                s.data_open_total += piece;
                if t.width >= rules.track - 1000 && t.width <= mm(0.3) + 1000 {
                    s.data_open_in_band += piece;
                } else if t.width <= rules.neck + 1000 {
                    s.data_open_neck += piece;
                }
            }
        }
    }
    s
}

/// Per pair: length each side, skew, and how much of the positive net runs coupled to the negative
/// one (edge to edge within 0.35 mm on the same layer; 4.2 wants the spec held but at pad and via).
pub fn pairs(board: &Board, rules: &Rules) -> Vec<(String, f64, f64, f64, f64)> {
    let mut out = Vec::new();
    for pr in &rules.pairs {
        let (Some(&p), Some(&n)) = (board.net_ids.get(&pr.p), board.net_ids.get(&pr.n)) else { continue };
        let len = |net: NetId| -> f64 { board.tracks.iter().filter(|t| t.net == net).map(|t| hypot(sub(t.a.into(), t.b.into()))).sum::<f64>() / NM };
        let mut coupled = 0.0;
        let mut gap_sum = 0.0;
        for t in board.tracks.iter().filter(|t| t.net == p) {
            let (a, b): (V, V) = (t.a.into(), t.b.into());
            let l = hypot(sub(a, b));
            let steps = (l / (0.05 * NM)).ceil().max(1.0) as usize;
            for i in 0..steps {
                let u = (i as f64 + 0.5) / steps as f64;
                let c = V(a.0 + (b.0 - a.0) * u, a.1 + (b.1 - a.1) * u);
                let mut near = f64::INFINITY;
                for o in board.tracks.iter().filter(|o| o.net == n && o.layer == t.layer) {
                    near = near.min(pt_seg(c, o.a.into(), o.b.into()) - (t.width + o.width) as f64 / 2.0);
                }
                if near <= 0.35 * NM {
                    coupled += l / steps as f64 / NM;
                    gap_sum += near * (l / steps as f64) / NM / NM;
                }
            }
        }
        out.push((format!("{}/{}", pr.p, pr.n), len(p), len(n), coupled, if coupled > 0.0 { gap_sum / coupled } else { 0.0 }));
    }
    out
}

fn widths_text(w: &BTreeMap<i64, f64>) -> String {
    let mut v: Vec<(&i64, &f64)> = w.iter().collect();
    v.sort_by(|a, b| b.1.total_cmp(a.1));
    v.iter().take(3).map(|(k, l)| format!("{:.2}:{:.1}", **k as f64 / 1000.0, l)).collect::<Vec<_>>().join(" ")
}

fn pct(a: f64, t: f64) -> f64 {
    if t > 0.0 { 100.0 * a / t } else { 0.0 }
}

fn spacing_json(s: &Spacing) -> Value {
    json!({
        "openMm": s.open_total, "escapeMm": s.esc_total,
        "at3wPct": pct(s.open_3w, s.open_total), "at2wPct": pct(s.open_2w, s.open_total), "tighterPct": pct(s.open_min, s.open_total),
        "dataOpenMm": s.data_open_total, "dataInBandPct": pct(s.data_open_in_band, s.data_open_total), "dataAtNeckPct": pct(s.data_open_neck, s.data_open_total),
    })
}

/// Prints the comparison, biggest length difference first. The summary line carries the one number
/// to minimise when calibrating: the sum over nets of |ours - his| length, plus 3 mm per via off.
pub fn report(ours: &Board, reference: &Board, rules: &Rules, as_json: bool) -> Value {
    let (a, sa) = measure(ours, rules);
    let (b, sb) = measure(reference, rules);
    let (bus_n, bus_ours, bus_mm) = crate::bus::coherence(ours, rules);
    let (_, bus_his, bus_his_mm) = crate::bus::coherence(reference, rules);
    if !as_json {
        println!("  buses: {bus_n} bus lines; {:.0}% of their length runs beside the next line in the bus (reference {:.0}%), over {:.0} mm (reference {:.0} mm).", bus_ours * 100.0, bus_his * 100.0, bus_mm, bus_his_mm);
    }
    let mut rows: Vec<(String, NetStat, NetStat)> = Vec::new();
    for (n, x) in &b {
        if x.len > 0.0 || x.vias > 0 || a.get(n).map(|y| y.len > 0.0).unwrap_or(false) {
            rows.push((n.clone(), a.get(n).cloned().unwrap_or_default(), x.clone()));
        }
    }
    rows.sort_by(|p, q| (q.1.len - q.2.len).abs().total_cmp(&(p.1.len - p.2.len).abs()));
    let mut score = 0.0;
    let (mut la, mut lb, mut va, mut vb, mut ba, mut bb, mut open) = (0.0, 0.0, 0, 0, 0, 0, 0);
    let mut per_net = Vec::new();
    // The same distance over only the nets we closed, bends included, so a calibration run isn't
    // judged by how far the clock let it get.
    let (mut closed, mut closed_nets) = (0.0, 0);
    for (n, x, y) in &rows {
        score += (x.len - y.len).abs() + 3.0 * (x.vias as f64 - y.vias as f64).abs();
        if x.open == 0 {
            closed += (x.len - y.len).abs() + 3.0 * (x.vias as f64 - y.vias as f64).abs() + 0.3 * ((x.bends45 + x.bends90) as f64 - (y.bends45 + y.bends90) as f64).abs();
            closed_nets += 1;
        }
        la += x.len;
        lb += y.len;
        va += x.vias;
        vb += y.vias;
        ba += x.bends45 + x.bends90;
        bb += y.bends45 + y.bends90;
        open += x.open;
        per_net.push(json!({"net": n, "level": y.level, "treeMm": y.tree, "open": x.open,
            "ours": {"mm": x.len, "top": x.top, "bottom": x.bottom, "vias": x.vias, "bends45": x.bends45, "bends90": x.bends90, "widths": widths_text(&x.widths)},
            "his": {"mm": y.len, "top": y.top, "bottom": y.bottom, "vias": y.vias, "bends45": y.bends45, "bends90": y.bends90, "widths": widths_text(&y.widths)}}));
    }
    let tally = |m: &BTreeMap<String, NetStat>| (m.values().map(|n| n.steps).sum::<usize>(), m.values().map(|n| n.doubled).sum::<usize>());
    let (ta, tb) = (tally(&a), tally(&b));
    let v = json!({"widthSteps": [ta.0, tb.0], "doubledRuns": [ta.1, tb.1], "score": score, "closedScore": closed, "closedNets": closed_nets, "lengthMm": [la, lb], "vias": [va, vb], "bends": [ba, bb], "open": open, "spacing": {"ours": spacing_json(&sa), "his": spacing_json(&sb)}, "nets": per_net});
    if !as_json {
        println!("OK: distance from the reference copper {:.1} (sum of |length diff| + 3 per via off); {:.1} mm against the reference's {:.1}, {} vias against {}, {} bends against {}, {} joins open. On the {} nets closed: {:.1} with bends at 0.3 each.", score, la, lb, va, vb, ba, bb, open, closed_nets, closed);
        println!("  width steps {} against the reference's {}; same-net doubled runs {} against the reference's {}.", ta.0, tb.0, ta.1, tb.1);
        for (who, s) in [("ours", &sa), ("ref ", &sb)] {
            println!("  spacing {who}: outside escapes {:.1} mm: {:.0}% at 3W, {:.0}% at 2W, {:.0}% tighter; in escapes {:.1} mm. Data outside escapes {:.1} mm: {:.0}% at 0.2-0.3 wide, {:.0}% at the neck.", s.open_total, pct(s.open_3w, s.open_total), pct(s.open_2w, s.open_total), pct(s.open_min, s.open_total), s.esc_total, s.data_open_total, pct(s.data_open_in_band, s.data_open_total), pct(s.data_open_neck, s.data_open_total));
        }
        let long = |pick: &dyn Fn(&(String, NetStat, NetStat)) -> f64| rows.iter().filter(|r| r.2.tree > 1.0 * NM / NM && r.2.level != "plane via" && pick(r) > r.2.tree * 1.4 + 2.5).map(|r| r.0.as_str()).collect::<Vec<_>>().join(" ");
        println!("  over 1.4 x tree + 2.5 mm, ours: [{}]; reference: [{}].", long(&|r| r.1.len), long(&|r| r.2.len));
        for (who, b) in [("ours", ours), ("ref ", reference)] {
            let (n, t) = vias_near_ground(b, 1.5 * NM);
            println!("  signal vias {who}: {n} of {t} have a plane via within 1.5 mm.");
        }
        for (who, list) in [("ours", pairs(ours, rules)), ("ref ", pairs(reference, rules))] {
            for (name, lp, ln, c, g) in list {
                println!("  pair {who} {name}: {lp:.2} / {ln:.2} mm, skew {:.3} mm, coupled {c:.2} mm ({:.0}% of the positive net), mean gap {g:.3} mm.", (lp - ln).abs(), if lp > 0.0 { 100.0 * c / lp } else { 0.0 });
            }
        }
        println!("  {:<16} {:<10} {:>6} | {:>7} {:>7} {:>6} {:>6} {:>4} {:>5} {:<22} | {:>7} {:>7} {:>6} {:>6} {:>4} {:>5} {}", "net", "level", "tree", "mm", "ratio", "top", "bot", "via", "bends", "widths mm:len", "ref mm", "ratio", "top", "bot", "via", "bends", "widths");
        for (n, x, y) in &rows {
            let r = |l: f64| if y.tree > 0.0 { l / y.tree } else { 0.0 };
            println!(
                "  {:<16} {:<10} {:>6.1} | {:>7.1} {:>7.2} {:>6.1} {:>6.1} {:>4} {:>2}/{:<2} {:<22} | {:>7.1} {:>7.2} {:>6.1} {:>6.1} {:>4} {:>2}/{:<2} {}{}",
                n.chars().take(16).collect::<String>(),
                y.level.chars().take(10).collect::<String>(),
                y.tree,
                x.len,
                r(x.len),
                x.top,
                x.bottom,
                x.vias,
                x.bends45,
                x.bends90,
                widths_text(&x.widths),
                y.len,
                r(y.len),
                y.top,
                y.bottom,
                y.vias,
                y.bends45,
                y.bends90,
                widths_text(&y.widths),
                if x.open > 0 { format!("  OPEN {}", x.open) } else { String::new() }
            );
        }
    }
    v
}