Adom Fields

//! Reflections and TDR (0.9.6): a net's copper walked from its driver pad to its receiver pad, each segment a lossless
//! transmission line with the cross-section solve's own Z0 and delay (crate::xsec), each via on the path its pad
//! capacitance (Johnson & Graham: C ≈ 1.41·εr·T·D1/(D2 − D1) pF, inches), the receiver a capacitance. Two ngspice runs:
//!   TDR      a 50 Ω step source (35 ps edge) into the path, the far end at the receiver: Z(t) = 50·(1+ρ)/(1−ρ), ρ = 2·V − 1
//!   in use   the net's real driver (its output resistance and edge) into the same path: overshoot, undershoot, ringing
//! A net shorter than a sixth of its edge (round trip under a third) is electrically short and only says so.
//! Branches off the path are counted, not modelled. The nets: spec impedance targets, clocks, length groups, spec tdr.
use crate::board::Board;
use crate::fields::{Issue, Spec};
use serde::Deserialize;
use serde_json::{json, Value};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap};
use std::cmp::Reverse;

#[allow(non_snake_case)]
#[derive(Deserialize, Clone, Debug, Default)]
pub struct TdrCfg { #[serde(default)] pub driverOhm: Option<f64>, #[serde(default)] pub riseNs: Option<f64>, #[serde(default)] pub loadPf: Option<f64>, #[serde(default)] pub from: Option<String>, #[serde(default)] pub to: Option<String> }

fn r1(v: f64) -> f64 { (v * 10.0).round() / 10.0 }
type P = (i64, i64);
fn key(x: f64, y: f64) -> P { ((x * 20.0).round() as i64, (y * 20.0).round() as i64) } // 0.05 mm

enum El { Line { z0: f64, td: f64, len: f64, layer: String, w: f64 }, Via { c: f64 } }

/// the path from one pad to another over the net's segments and vias: Dijkstra on length
fn path(b: &Board, net: &str, from: (f64, f64), to: (f64, f64)) -> Option<(Vec<(usize, bool)>, Vec<P>, usize)> {
    let ts: Vec<(usize, &crate::board::Track)> = b.tracks.iter().enumerate().filter(|(_, t)| t.net == net).collect();
    // nodes: (layer index, point); a via joins its point on every layer
    let mut id: BTreeMap<(String, P), usize> = BTreeMap::new(); let mut pts: Vec<(String, P)> = Vec::new();
    let mut node = |l: &str, p: P, id: &mut BTreeMap<(String, P), usize>| -> usize { let k = (l.to_string(), p); if let Some(i) = id.get(&k) { return *i; } let i = pts.len(); pts.push(k.clone()); id.insert(k, i); i };
    let mut adj: Vec<Vec<(usize, f64, Option<(usize, bool)>)>> = Vec::new();
    let mut edge = |a: usize, c: usize, w: f64, e: Option<(usize, bool)>, adj: &mut Vec<Vec<(usize, f64, Option<(usize, bool)>)>>| { while adj.len() <= a.max(c) { adj.push(Vec::new()); } adj[a].push((c, w, e)); adj[c].push((a, w, e.map(|(i, f)| (i, !f)))); };
    for (i, t) in &ts { let a = node(&t.layer, key(t.a.0, t.a.1), &mut id); let c = node(&t.layer, key(t.b.0, t.b.1), &mut id); edge(a, c, (t.a.0 - t.b.0).hypot(t.a.1 - t.b.1), Some((*i, true)), &mut adj); }
    let mut vias = Vec::new();
    for v in b.vias.iter().filter(|v| v.net == net) { let k = key(v.x, v.y); let ls: Vec<usize> = (0..pts.len()).filter(|i| pts[*i].1 == k).collect(); for w in ls.windows(2) { edge(w[0], w[1], 0.0, None, &mut adj); } if ls.len() > 1 { vias.push(k); } }
    // a pad: every segment end within 0.6 mm on any layer
    let near = |p: (f64, f64)| -> Vec<usize> { (0..pts.len()).filter(|i| { let q = pts[*i].1; ((q.0 as f64 / 20.0 - p.0).hypot(q.1 as f64 / 20.0 - p.1)) < 0.6 }).collect() };
    let (s, g) = (near(from), near(to)); if s.is_empty() || g.is_empty() { return None; }
    let n = pts.len(); while adj.len() < n { adj.push(Vec::new()); }
    let mut dist = vec![f64::MAX; n]; let mut prev: Vec<Option<(usize, Option<(usize, bool)>)>> = vec![None; n];
    let mut h = BinaryHeap::new(); for &i in &s { dist[i] = 0.0; h.push(Reverse(((0.0f64 * 1000.0) as i64, i))); }
    let mut done = vec![false; n];
    while let Some(Reverse((_, u))) = h.pop() { if done[u] { continue; } done[u] = true; for &(v, w, e) in &adj[u] { let nd = dist[u] + w; if nd < dist[v] - 1e-9 { dist[v] = nd; prev[v] = Some((u, e)); h.push(Reverse(((nd * 1e6) as i64, v))); } } }
    let end = *g.iter().min_by(|a, z| dist[**a].partial_cmp(&dist[**z]).unwrap())?; if dist[end] == f64::MAX { return None; }
    let mut segs = Vec::new(); let mut via_hits = Vec::new(); let mut cur = end; let mut seen_nodes = BTreeSet::new();
    while let Some((p, e)) = prev[cur] { if !seen_nodes.insert(cur) || seen_nodes.len() > n { break; } match e { Some(x) => segs.push(x), None => via_hits.push(pts[cur].1) } cur = p; }
    seen_nodes.insert(cur); segs.reverse(); via_hits.reverse(); via_hits.dedup();
    // branches: segment ends on the path with more edges than the path uses
    let branches = seen_nodes.iter().filter(|i| adj[**i].iter().filter(|x| x.2.is_some() && !seen_nodes.contains(&x.0)).count() > 0).count();
    Some((segs, via_hits, branches))
}

fn pad_of(b: &Board, net: &str, name: Option<&str>, prefer_ic: bool) -> Option<(String, (f64, f64))> {
    let ps: Vec<_> = b.pads.iter().filter(|p| p.net == net).collect();
    if let Some(n) = name { let (r, pd) = n.split_once('.').unwrap_or((n, "")); return ps.iter().find(|p| p.reference == r && (pd.is_empty() || p.pad == pd)).map(|p| (format!("{}.{}", p.reference, p.pad), (p.x, p.y))); }
    let pick = if prefer_ic { ps.iter().find(|p| p.reference.starts_with('U')).or(ps.first()) } else { ps.first() };
    pick.map(|p| (format!("{}.{}", p.reference, p.pad), (p.x, p.y)))
}

fn spice(deck: &str, dir: &std::path::Path, tag: &str) -> Option<Vec<(f64, f64, f64)>> {
    let cir = dir.join(format!("tdr-{tag}.cir")); let out = dir.join(format!("tdr-{tag}.txt"));
    std::fs::write(&cir, deck.replace("@OUT@", &out.display().to_string())).ok()?;
    let r = std::process::Command::new("timeout").args(["30", "ngspice", "-b"]).arg(&cir).output().ok()?; if !r.status.success() { return None; }
    let t = std::fs::read_to_string(&out).ok()?; let _ = std::fs::remove_file(&out); let _ = std::fs::remove_file(&cir);
    Some(t.lines().filter_map(|l| { let v: Vec<f64> = l.split_whitespace().filter_map(|x| x.parse().ok()).collect(); if v.len() >= 4 { Some((v[0], v[1], v[3])) } else { None } }).collect())
}
fn deck(els: &[El], rs: f64, tr: f64, cl: f64, tstop: f64) -> String {
    let mut d = format!("tdr\nV1 in 0 PULSE(0 1 0 {tr:e} {tr:e} 1 2)\nRs in n0 {rs}\n"); let mut k = 0;
    for (i, e) in els.iter().enumerate() { match e { El::Line { z0, td, .. } => { d += &format!("T{i} n{k} 0 n{} 0 Z0={z0} TD={td:e}\n", k + 1); k += 1; } El::Via { c } => { d += &format!("C{i} n{k} 0 {c:e}\n"); } } }
    d += &format!("Cl n{k} 0 {cl:e}\nRl n{k} 0 1e7\n.tran {:e} {tstop:e}\n.control\nrun\nwrdata @OUT@ v(n0) v(n{k})\n.endc\n.end\n", (tr / 20.0).min(2e-12).max(2e-13)); d
}

pub fn review(b: &Board, spec: &Spec, xs: &Value, out: &std::path::Path, issues: &mut Vec<Issue>) -> Value {
    let mut nets: BTreeSet<String> = spec.tdr.keys().cloned().collect();
    for k in spec.impedance.keys() { for n in k.split('/') { nets.insert(n.to_string()); } }
    for k in spec.clocks.keys() { nets.insert(k.clone()); }
    for g in spec.lengthGroups.values() { for n in &g.nets { nets.insert(n.clone()); } }
    if nets.is_empty() { return json!({"ran": false, "why": "no net to check: give spec impedance targets, clocks, lengthGroups or tdr {net: {driverOhm, riseNs, loadPf, from, to}}"}); }
    let has_spice = std::process::Command::new("ngspice").arg("-v").output().map(|o| o.status.success()).unwrap_or(false);
    let rows_of = |net: &str| xs["nets"].as_array().and_then(|a| a.iter().find(|x| x["net"] == net)).and_then(|x| x["segments"].as_array().cloned()).unwrap_or_default();
    let thick: f64 = if spec.real_gaps.is_empty() { 1.6 } else { spec.real_gaps.iter().sum::<f64>() };
    let er = spec.epsilonR.unwrap_or(4.3);
    let mut res = Vec::new();
    for net in nets.iter().take(24) {
        let cfg = spec.tdr.get(net).cloned().unwrap_or_default();
        let Some((dn, dp)) = pad_of(b, net, cfg.from.as_deref(), true) else { res.push(json!({"net": net, "ran": false, "why": "no pads on this net"})); continue };
        let to = match cfg.to.as_deref() { Some(t) => pad_of(b, net, Some(t), false), None => b.pads.iter().filter(|p| p.net == *net && format!("{}.{}", p.reference, p.pad) != dn).max_by(|a, z| (a.x - dp.0).hypot(a.y - dp.1).partial_cmp(&(z.x - dp.0).hypot(z.y - dp.1)).unwrap()).map(|p| (format!("{}.{}", p.reference, p.pad), (p.x, p.y))) };
        let Some((rn, rp)) = to else { res.push(json!({"net": net, "ran": false, "why": "one pad only"})); continue };
        let Some((segs, vias, branches)) = path(b, net, dp, rp) else { res.push(json!({"net": net, "ran": false, "why": format!("no copper path from {dn} to {rn} over segments and vias (a pour or an unrouted net)")})); continue };
        let rows = rows_of(net);
        let mut els: Vec<El> = Vec::new(); let mut vi = 0; let mut last_layer = String::new(); let mut assumed = 0.0f64;
        for (si, _) in &segs {
            let t = &b.tracks[*si];
            if !last_layer.is_empty() && last_layer != t.layer && vi < vias.len() {
                let v = b.vias.iter().filter(|v| v.net == *net).min_by(|a, z| (key(a.x, a.y).0 - vias[vi].0).abs().cmp(&(key(z.x, z.y).0 - vias[vi].0).abs())).map(|v| (v.size, v.drill)).unwrap_or((0.6, 0.3));
                let (d1, d2, ti) = (v.0 / 25.4, (v.0 + 0.5) / 25.4, thick / 25.4); els.push(El::Via { c: 1.41 * er * ti * d1 / (d2 - d1) * 1e-12 }); vi += 1;
            }
            last_layer = t.layer.clone();
            let len = (t.a.0 - t.b.0).hypot(t.a.1 - t.b.1); if len < 1e-6 { continue; }
            // the solved impedance for this layer and width; a stretch with no reference under it has none, and is taken as
            // 50 Ω with the length counted in `assumedMm`
            let row = rows.iter().find(|r| r["layer"] == t.layer.as_str() && (r["widthMm"].as_f64().unwrap_or(0.0) - t.w).abs() < 1e-3 && r["z0"].is_number());
            if row.is_none() { assumed += (t.a.0 - t.b.0).hypot(t.a.1 - t.b.1); }
            let (z0, ps) = row.map(|r| (r["z0"].as_f64().unwrap_or(50.0), r["psPerMm"].as_f64().unwrap_or(6.7))).unwrap_or((50.0, 6.7));
            // adjacent segments of one width and layer are one line
            if let Some(El::Line { z0: z, td, len: l, layer, w }) = els.last_mut() { if *layer == t.layer && (*w - t.w).abs() < 1e-6 && (*z - z0).abs() < 1e-9 { *td += len * ps * 1e-12; *l += len; continue; } }
            els.push(El::Line { z0, td: len * ps * 1e-12, len, layer: t.layer.clone(), w: t.w });
        }
        let td: f64 = els.iter().map(|e| if let El::Line { td, .. } = e { *td } else { 0.0 }).sum();
        let len: f64 = els.iter().map(|e| if let El::Line { len, .. } = e { *len } else { 0.0 }).sum();
        let clock_tr = spec.clocks.get(net).map(|c| 0.07 / c.top_hz().max(1.0)); // a clock's edge: about 7 % of its period
        let tr = cfg.riseNs.map(|x| x * 1e-9).or(clock_tr).unwrap_or(1e-9).max(2e-11);
        let (rs, cl) = (cfg.driverOhm.unwrap_or(25.0), cfg.loadPf.unwrap_or(3.0) * 1e-12);
        let zs: Vec<f64> = els.iter().filter_map(|e| if let El::Line { z0, .. } = e { Some(*z0) } else { None }).collect();
        let zline = if zs.is_empty() { 50.0 } else { els.iter().filter_map(|e| if let El::Line { z0, len, .. } = e { Some(z0 * len) } else { None }).sum::<f64>() / len.max(1e-9) };
        let target = spec.impedance.get(net).copied();
        let short = td < tr / 6.0;
        let mut row = json!({"net": net, "ran": true, "driver": dn, "receiver": rn, "lengthMm": r1(len), "delayPs": r1(td * 1e12), "segments": els.iter().filter(|e| matches!(e, El::Line { .. })).count(), "vias": els.iter().filter(|e| matches!(e, El::Via { .. })).count(), "branches": branches, "edgeNs": (tr * 1e12).round() / 1e3, "driverOhm": rs, "loadPf": cl * 1e12, "zMin": zs.iter().cloned().fold(f64::MAX, f64::min), "zMax": zs.iter().cloned().fold(0.0, f64::max), "targetOhm": target, "electricallyShort": short});
        if assumed > 0.0 { row["assumedMm"] = json!(r1(assumed)); row["assumedNote"] = json!("stretches with no solved impedance (no reference plane under them, see review.impedance) are taken as 50 Ω"); }
        if short { row["note"] = json!(format!("{:.0} ps of line against a {:.0} ps edge: shorter than a sixth of it, so reflections stay inside the edge", td * 1e12, tr * 1e12)); }
        if has_spice && !els.is_empty() {
            // TDR: 50 Ω, a 35 ps step, long enough to see the far end
            if let Some(w) = spice(&deck(&els, 50.0, 35e-12, cl, (2.0 * td + 400e-12).max(1e-9)), out, &format!("z-{}", res.len())) {
                let prof: Vec<Value> = w.iter().step_by((w.len() / 160).max(1)).filter(|p| p.0 >= 35e-12 && p.0 <= 2.0 * td + 100e-12).map(|p| { let rho = (2.0 * p.1 - 1.0).clamp(-0.99, 0.99); json!([r1(p.0 * 1e12), r1(50.0 * (1.0 + rho) / (1.0 - rho))]) }).collect();
                row["tdr"] = json!({"columns": ["ps", "ohm"], "points": prof, "source": "50 Ω, 35 ps step, ngspice lossless lines"});
            }
            // in use: the driver's edge into the receiver
            if let Some(w) = spice(&deck(&els, rs, tr, cl, (6.0 * td + 4.0 * tr).max(2e-9)), out, &format!("u-{}", res.len())) {
                let vmax = w.iter().map(|p| p.2).fold(0.0, f64::max); let after: Vec<f64> = w.iter().filter(|p| p.0 > tr).map(|p| p.2).collect();
                let vmin = after.iter().cloned().skip_while(|v| *v < 0.9).fold(1.0, f64::min);
                let over = (vmax - 1.0).max(0.0) * 100.0; let under = (1.0 - vmin).max(0.0) * 100.0;
                let settle = w.iter().rev().find(|p| (p.2 - 1.0).abs() > 0.05).map(|p| p.0).unwrap_or(0.0);
                let r_series = (zline - rs).max(0.0);
                row["receiver"] = json!(rn); row["inUse"] = json!({"overshootPct": r1(over), "undershootPct": r1(under), "settleNs": (settle * 1e12).round() / 1e3, "seriesTerminationOhm": r_series.round()});
                if over > 15.0 && !short {
                    issues.push(Issue { severity: if over > 30.0 { "medium".into() } else { "low".into() }, kind: "reflection".into(), what: format!("{net}: {:.0} % overshoot and {:.0} % ringing back at {rn} ({:.0} mm, {:.0} ps of {:.0} Ω line driven by {rs:.0} Ω with a {:.2} ns edge)", over, under, len, td * 1e12, zline, tr * 1e9), at: Some([dp.0, dp.1]), layer: None, net: Some(net.clone()), reference: Some(dn.split('.').next().unwrap_or("").into()), fix: format!("Add a {:.0} Ω series resistor at {dn} (the line's {:.0} Ω less the driver's {rs:.0} Ω), or slow the edge; set spec tdr.{net}.driverOhm and riseNs from the driver's datasheet first.", r_series.max(10.0), zline), action: Some(json!({"type": "add-part", "what": "series termination resistor", "net": net, "nearPin": dn, "valueOhm": r_series.max(10.0).round(), "why": "reflection"})) });
                }
            }
        }
        if let Some(tz) = target { let dev = zs.iter().map(|z| (z - tz).abs() / tz).fold(0.0, f64::max); if dev > 0.1 { row["worstDeviationPct"] = json!(r1(dev * 100.0)); } }
        res.push(row);
    }
    json!({"ran": true, "ngspice": has_spice, "model": "each path segment a lossless line with the cross-section solve's Z0 and delay, vias as pad capacitance, receiver as a capacitance; 50 Ω TDR and the real driver in ngspice", "defaults": "driver 25 Ω, edge 1 ns (a clock: 7 % of its period), receiver 3 pF: set spec tdr.<net> {driverOhm, riseNs, loadPf, from, to}", "nets": res})
}

#[cfg(test)] mod tests {
    use super::*;
    #[test] fn matched_line_is_clean() {
        // a 50 Ω line from a 50 Ω source into a tiny load: the TDR reads 50 Ω along the line
        if std::process::Command::new("ngspice").arg("-v").output().is_err() { return; }
        let dir = std::env::temp_dir();
        let els = vec![El::Line { z0: 50.0, td: 200e-12, len: 30.0, layer: "F.Cu".into(), w: 0.3 }];
        let w = spice(&deck(&els, 50.0, 35e-12, 1e-15, 1e-9), &dir, "test").unwrap();
        let mid: Vec<f64> = w.iter().filter(|p| p.0 > 100e-12 && p.0 < 350e-12).map(|p| p.1).collect();
        assert!(mid.iter().all(|v| (v - 0.5).abs() < 0.02), "{:?}", &mid[..3]);
        // the open far end doubles: 1 V at the receiver after the delay
        assert!(w.iter().any(|p| p.0 > 300e-12 && (p.2 - 1.0).abs() < 0.05));
    }
}