AI Flow

//! Issue #52 (a real board: StickHub, eight USB pairs, 2 layers, 1.6 mm): an impedance target can solve to a
//! width far wider than the pins it has to reach (90 ohm diff over 1.51 mm FR4: 1.38 mm, against 0.3 mm hub
//! pins), and a net searched only at that width never leaves its pins. The router now also tries such a net at
//! the rule width (a pair still at its solved centre pitch), and this pass widens the routed copper back to the
//! target width wherever the router's own clearance check allows: the copper stays narrow only where it must
//! (near the pins, past an obstacle), and `analyze impedance` counts that as the net's uncontrolled length
//! against `maxUncontrolledMm`. Each widened run is its own plan path at the target width, joined end to end.
use crate::{Router, F_CU, B_CU};
use serde_json::{json, Value};
use std::collections::BTreeMap;

type Pt = (f64, f64);
/// The length of each piece the widening is judged on (mm).
const STEP: f64 = 0.1;

fn layer_index(name: &str) -> Option<usize> { match name { "F.Cu" => Some(F_CU), "B.Cu" => Some(B_CU), _ => None } }

fn point(board: &aiflow_board::Board, v: &Value) -> Option<Pt> {
    if let Some(k) = v.as_str() { let p = board.pad_by_key(k)?; return Some((p.x, p.y)); }
    if let Some(a) = v.as_array() { return Some((a.first()?.as_f64()?, a.get(1)?.as_f64()?)); }
    let o = v.as_object()?;
    if let Some(k) = o.get("pad").and_then(|p| p.as_str()) { let p = board.pad_by_key(k)?; return Some((p.x, p.y)); }
    Some((o.get("x")?.as_f64()?, o.get("y")?.as_f64()?))
}

fn dist(a: Pt, b: Pt) -> f64 { ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt() }
fn lerp(a: Pt, b: Pt, t: f64) -> Pt { (a.0 + (b.0 - a.0) * t, a.1 + (b.1 - a.1) * t) }
fn r6(v: f64) -> f64 { (v * 1e6).round() / 1e6 }

/// A polyline cut into pieces of at most STEP, keeping its own vertices.
fn pieces(pts: &[Pt]) -> Vec<(Pt, Pt)> {
    let mut out = Vec::new();
    for w in pts.windows(2) {
        let (a, b) = (w[0], w[1]);
        let n = (dist(a, b) / STEP).ceil().max(1.0) as usize;
        for k in 0..n { out.push((lerp(a, b, k as f64 / n as f64), lerp(a, b, (k + 1) as f64 / n as f64))); }
    }
    out
}

/// Runs of consecutive pieces with the same verdict, as polylines (collinear points dropped).
fn runs(ps: &[(Pt, Pt)], ok: &[bool]) -> Vec<(bool, Vec<Pt>)> {
    let mut out: Vec<(bool, Vec<Pt>)> = Vec::new();
    for (k, (a, b)) in ps.iter().enumerate() {
        match out.last_mut() {
            Some((v, line)) if *v == ok[k] => line.push(*b),
            _ => out.push((ok[k], vec![*a, *b])),
        }
    }
    for (_, line) in out.iter_mut() {
        let mut keep: Vec<Pt> = Vec::new();
        for p in line.iter() {
            if keep.len() >= 2 {
                let (a, b) = (keep[keep.len() - 2], keep[keep.len() - 1]);
                let cross = (b.0 - a.0) * (p.1 - a.1) - (b.1 - a.1) * (p.0 - a.0);
                if cross.abs() < 1e-6 { keep.pop(); }
            }
            keep.push(*p);
        }
        *line = keep;
    }
    out
}

/// Widen every impedance-controlled path the router laid at less than its target width. Returns the report:
/// per net the length widened to the target and the length left narrow.
pub fn widen_plan(router: &mut Router, plan: &mut Vec<Value>) -> Value {
    let rules: BTreeMap<String, (f64, String)> = router.rules.impedance.iter().map(|(n, ir)| (n.clone(), (ir.width, ir.layer.clone()))).collect();
    let mut report: BTreeMap<String, Value> = BTreeMap::new();
    let mut added: Vec<Value> = Vec::new();
    for e in plan.iter_mut() {
        let net = e["net"].as_str().unwrap_or("").to_string();
        let Some((target, layer_name)) = rules.get(&net).cloned() else { continue };
        let Some(layer) = layer_index(&layer_name) else { continue };
        let w = e["width"].as_f64().unwrap_or(target);
        if w + 1e-6 >= target || e.get("kelvin").is_some() || e.get("decoupling").is_some() { continue; }
        let paths: Vec<Value> = e["paths"].as_array().cloned().unwrap_or_default();
        let (mut keep_narrow, mut wide_paths) = (Vec::new(), Vec::new());
        let (mut wide_mm, mut narrow_mm) = (0.0, 0.0);
        for path in paths {
            let raw = path.as_array().cloned().unwrap_or_default();
            let pts: Vec<Pt> = raw.iter().filter_map(|v| point(&router.board, v)).collect();
            // a path that changes layer is not an impedance path the router laid (it holds them to one layer)
            if pts.len() < 2 || pts.len() != raw.len() || raw.iter().any(|v| v.get("layer").and_then(|l| l.as_str()).is_some_and(|l| l != layer_name)) { keep_narrow.push(path); continue; }
            let ps = pieces(&pts);
            let ok: Vec<bool> = ps.iter().map(|(a, b)| router.segment_clear(&net, layer, *a, *b, target)).collect();
            let rs = runs(&ps, &ok);
            // a wide run too short to matter stays narrow (no short bulges)
            let rs: Vec<(bool, Vec<Pt>)> = rs.into_iter().map(|(v, line)| { let l: f64 = line.windows(2).map(|x| dist(x[0], x[1])).sum(); (v && l >= 2.0 * target, line) }).collect();
            if !rs.iter().any(|r| r.0) { narrow_mm += ps.iter().map(|(a, b)| dist(*a, *b)).sum::<f64>(); keep_narrow.push(path); continue; }
            let at = |p: Pt| json!({"x": r6(p.0), "y": r6(p.1), "layer": layer_name});
            let n = rs.len();
            for (k, (wide, line)) in rs.into_iter().enumerate() {
                let len: f64 = line.windows(2).map(|x| dist(x[0], x[1])).sum();
                // the run's ends: the path's own first and last waypoints (pads keep their key), else points
                let mut wp: Vec<Value> = line.iter().map(|p| at(*p)).collect();
                if k == 0 { wp[0] = raw[0].clone(); }
                if k + 1 == n { *wp.last_mut().unwrap() = raw[raw.len() - 1].clone(); }
                if wide {
                    wide_mm += len;
                    for x in line.windows(2) { router.stamp_wide(&net, layer, x[0], x[1], target); }
                    wide_paths.push(Value::Array(wp));
                } else { narrow_mm += len; keep_narrow.push(Value::Array(wp)); }
            }
        }
        if wide_paths.is_empty() { continue; }
        e["paths"] = Value::Array(keep_narrow);
        added.push(json!({"net": net, "width": target, "paths": wide_paths, "impedance": "widened to the target width (issue #52)"}));
        let r = report.entry(net).or_insert(json!({"wideMm": 0.0, "narrowMm": 0.0}));
        r["wideMm"] = json!(((r["wideMm"].as_f64().unwrap_or(0.0) + wide_mm) * 100.0).round() / 100.0);
        r["narrowMm"] = json!(((r["narrowMm"].as_f64().unwrap_or(0.0) + narrow_mm) * 100.0).round() / 100.0);
    }
    plan.retain(|e| e["paths"].as_array().is_none_or(|a| !a.is_empty()));
    plan.extend(added);
    json!({"nets": report, "rule": "an impedance net the router could only lay at the rule width is widened to its target width wherever its own clearance check passes; what stays narrow (near the pins, past an obstacle) is uncontrolled length, judged against maxUncontrolledMm"})
}

/// The extra length one 45-degree trapezoid bump of height h adds: two legs of h*sqrt2 replace 2h of line.
fn bump_gain(h: f64) -> f64 { 2.0 * h * (std::f64::consts::SQRT_2 - 1.0) }

/// A net's copper length in the plan, every path of every entry.
fn net_length(board: &aiflow_board::Board, plan: &[Value], net: &str) -> f64 {
    plan.iter().filter(|e| e["net"] == net).flat_map(|e| e["paths"].as_array().cloned().unwrap_or_default()).map(|p| {
        let pts: Vec<Pt> = p.as_array().into_iter().flatten().filter_map(|v| point(board, v)).collect();
        pts.windows(2).map(|w| dist(w[0], w[1])).sum::<f64>()
    }).sum()
}

/// Issue #52: length tuning. For each pair longer on one side than its maxSkewMm, add 45-degree trapezoid bumps
/// to the shorter net until the two match: on its narrow necks first (uncontrolled already), then on its coupled
/// run, on the side away from its partner, only where the router's own clearance check passes. A bump on the
/// coupled run is uncoupled length there, so it is the last resort; what cannot be tuned is reported.
pub fn tune_pairs(router: &mut Router, plan: &mut Vec<Value>) -> Value {
    let pairs: Vec<(String, String, f64, String)> = router.rules.impedance.iter().filter_map(|(n, ir)| {
        let p = ir.partner.clone()?;
        (n < &p).then(|| (n.clone(), p, if ir.max_skew > 0.0 { ir.max_skew } else { 0.5 }, ir.layer.clone()))
    }).collect();
    let mut report: BTreeMap<String, Value> = BTreeMap::new();
    for (a, b, max_skew, layer_name) in pairs {
        let Some(layer) = layer_index(&layer_name) else { continue };
        let skew_now = |plan: &[Value], board: &aiflow_board::Board| net_length(board, plan, &a) - net_length(board, plan, &b);
        let before = skew_now(plan, &router.board).abs();
        if before <= max_skew { continue; }
        let mut added = 0usize;
        let mut tuned: Vec<String> = Vec::new();
        for _round in 0..12 {
            let sk = skew_now(plan, &router.board);
            if sk.abs() <= max_skew { break; }
            let (short, partner) = if sk < 0.0 { (a.clone(), b.clone()) } else { (b.clone(), a.clone()) };
            let partner_pts: Vec<Pt> = plan.iter().filter(|e| e["net"] == partner.as_str()).flat_map(|e| e["paths"].as_array().cloned().unwrap_or_default()).flat_map(|p| p.as_array().cloned().unwrap_or_default()).filter_map(|v| point(&router.board, &v)).collect();
            let near_partner = |p: Pt| partner_pts.windows(2).map(|w| seg_dist(p, w[0], w[1])).fold(f64::INFINITY, f64::min);
            // candidate segments of the shorter net: (entry, path, segment, width, length), narrow first, longest first
            let mut cands: Vec<(usize, usize, usize, f64, f64)> = Vec::new();
            for (ei, e) in plan.iter().enumerate() {
                if e["net"] != short.as_str() || e.get("kelvin").is_some() || e.get("decoupling").is_some() { continue; }
                let w = e["width"].as_f64().unwrap_or(0.2);
                for (pi, p) in e["paths"].as_array().into_iter().flatten().enumerate() {
                    let pts: Vec<Pt> = p.as_array().into_iter().flatten().filter_map(|v| point(&router.board, v)).collect();
                    for (si, sg) in pts.windows(2).enumerate() { cands.push((ei, pi, si, w, dist(sg[0], sg[1]))); }
                }
            }
            let narrowest = cands.iter().map(|c| c.3).fold(f64::INFINITY, f64::min);
            cands.sort_by(|x, y| ((x.3 - narrowest).abs() > 1e-6).cmp(&((y.3 - narrowest).abs() > 1e-6)).then(y.4.total_cmp(&x.4)));
            let need = sk.abs();
            let mut done = false;
            'cand: for (ei, pi, si, w_seg, seglen) in cands {
                // a bump on a wide (coupled) run is drawn at the net's narrowest width, the wide copper split
                // around it: a short uncoupled stretch instead of a wide detour that uncouples both nets
                let w = narrowest.min(w_seg);
                let split = w_seg > w + 1e-6;
                // the bump's height: what the skew needs, at least the trace's own width; kept only if it helps
                let h_need = need / (2.0 * (std::f64::consts::SQRT_2 - 1.0));
                for h in [h_need, h_need / 2.0, h_need / 3.0].map(|h| h.max(w)) {
                    if (need - bump_gain(h)).abs() >= need - 1e-6 { continue; }
                    let base = 2.0 * h + 2.0 * w;
                    if seglen < base + 2.0 * w { continue; }
                    let path = plan[ei]["paths"][pi].as_array().cloned().unwrap_or_default();
                    let pts: Vec<Pt> = path.iter().filter_map(|v| point(&router.board, v)).collect();
                    if pts.len() != path.len() { continue 'cand; }
                    let (p0, p1) = (pts[si], pts[si + 1]);
                    let l = dist(p0, p1);
                    let d = ((p1.0 - p0.0) / l, (p1.1 - p0.1) / l);
                    let mid = lerp(p0, p1, 0.5);
                    let s0 = (mid.0 - d.0 * base / 2.0, mid.1 - d.1 * base / 2.0);
                    let n1 = (-d.1, d.0);
                    let side = if near_partner((mid.0 + n1.0 * h, mid.1 + n1.1 * h)) >= near_partner((mid.0 - n1.0 * h, mid.1 - n1.1 * h)) { n1 } else { (d.1, -d.0) };
                    let q1 = (s0.0 + d.0 * h + side.0 * h, s0.1 + d.1 * h + side.1 * h);
                    let q2 = (q1.0 + d.0 * 2.0 * w, q1.1 + d.1 * 2.0 * w);
                    let s1 = (q2.0 + d.0 * h - side.0 * h, q2.1 + d.1 * h - side.1 * h);
                    if ![(s0, q1), (q1, q2), (q2, s1)].iter().all(|(x, y)| router.segment_clear(&short, layer, *x, *y, w)) { continue; }
                    let at = |p: Pt| json!({"x": r6(p.0), "y": r6(p.1), "layer": layer_name});
                    if split {
                        // wide up to s0, the narrow bump s0..s1, wide again from s1
                        let mut before: Vec<Value> = path[..=si].to_vec();
                        before.push(at(s0));
                        let mut after: Vec<Value> = vec![at(s1)];
                        after.extend_from_slice(&path[si + 1..]);
                        let mut paths = plan[ei]["paths"].as_array().cloned().unwrap_or_default();
                        paths[pi] = Value::Array(before);
                        paths.insert(pi + 1, Value::Array(after));
                        plan[ei]["paths"] = Value::Array(paths);
                        let bump = Value::Array(vec![at(s0), at(q1), at(q2), at(s1)]);
                        match plan.iter().position(|e| e["net"] == short.as_str() && (e["width"].as_f64().unwrap_or(0.0) - w).abs() < 1e-6 && e.get("kelvin").is_none() && e.get("decoupling").is_none()) {
                            Some(k) => { if let Some(a) = plan[k]["paths"].as_array_mut() { a.push(bump); } }
                            None => plan.push(json!({"net": short, "width": w, "paths": [bump]})),
                        }
                    } else {
                        let mut np = path.clone();
                        np.splice(si + 1..si + 1, [at(s0), at(q1), at(q2), at(s1)]);
                        plan[ei]["paths"][pi] = Value::Array(np);
                    }
                    for (x, y) in [(s0, q1), (q1, q2), (q2, s1)] { router.stamp_wide(&short, layer, x, y, w); }
                    added += 1;
                    if !tuned.contains(&short) { tuned.push(short.clone()); }
                    done = true;
                    break 'cand;
                }
            }
            if !done { break; }
        }
        let after = skew_now(plan, &router.board).abs();
        report.insert(format!("{a}/{b}"), json!({"skewBeforeMm": (before * 1000.0).round() / 1000.0, "skewAfterMm": (after * 1000.0).round() / 1000.0, "maxSkewMm": max_skew, "bumps": added, "tunedNets": tuned, "within": after <= max_skew + 1e-9}));
    }
    json!({"pairs": report, "rule": "the shorter net of a pair gets 45-degree trapezoid bumps until the skew is within maxSkewMm: on its narrow necks first, then its coupled run, away from its partner, where the router's clearance check passes"})
}

fn seg_dist(p: Pt, a: Pt, b: Pt) -> f64 {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let l2 = dx * dx + dy * dy;
    let t = if l2 < 1e-12 { 0.0 } else { (((p.0 - a.0) * dx + (p.1 - a.1) * dy) / l2).clamp(0.0, 1.0) };
    dist(p, (a.0 + t * dx, a.1 + t * dy))
}

impl Router {
    /// Mark a widened segment as this net's copper, so its partner and later nets see it.
    pub fn stamp_wide(&mut self, net_name: &str, l: usize, a: Pt, b: Pt, width: f64) {
        let Some(&k) = self.net_ids.get(net_name) else { return };
        let g = self.grid.clone();
        for c in g.segment_cells(a, b, width / 2.0, Some(1e-6)) { self.route_raw[l][c] = k as i16; }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::impedance::{targets, stackup, solve_row, plan_tracks, check_target, Fab, GridPair};
    use crate::Rules;
    use aiflow_board::Board;

    /// A 2-layer 1.6 mm board: a pair from a fine-pitch part (0.3 mm pins at 0.5 mm) to another 30 mm away.
    fn fine_pitch_pair() -> Board {
        let fp = |r: &str, x: f64| format!("(footprint \"T:{r}\" (layer \"F.Cu\") (at {x} 10) (property \"Reference\" \"{r}\") (pad \"1\" smd rect (at 0 -0.25) (size 1.0 0.3) (layers \"F.Cu\") (net \"DP\")) (pad \"2\" smd rect (at 0 0.25) (size 1.0 0.3) (layers \"F.Cu\") (net \"DN\")))");
        let t = format!("(kicad_pcb (version 20260206) (generator \"test\") (general (thickness 1.6)) (layers (0 \"F.Cu\" signal) (2 \"B.Cu\" signal) (25 \"Edge.Cuts\" user)) {} {} (gr_rect (start 0 0) (end 40 20) (layer \"Edge.Cuts\")))", fp("U1", 4.0), fp("J1", 36.0));
        Board::from_text("np.kicad_pcb", t).unwrap()
    }

    /// Issue #52: 90 ohm on 1.6 mm FR4 is 1.38 mm wide against 0.3 mm pins. The pair is routed at the rule
    /// width and widened to the target between the pins: it routes at all, and the copper between is controlled.
    #[test]
    fn a_pair_too_wide_for_its_pins_is_routed_narrow_and_widened_between() {
        let b = fine_pitch_pair();
        let spec = serde_json::json!({"stackupMm": [1.51], "epsilonR": 4.5, "impedanceTargets": {"USB": {"pair": ["DP", "DN"], "targetDiffOhms": 90, "maxUncontrolledMm": 8}}});
        let ts = targets(&spec).unwrap();
        let st = stackup(&b, &spec).unwrap();
        let fab = Fab { min_width: 0.127, min_space: 0.127, source: "test".into() };
        let grid = GridPair { res: aiflow_grid::RES, clearance: 0.2, slop: crate::slop() };
        let row = solve_row(&ts[0], &st.layers[0], &fab, Some(&grid));
        let w = row["widthMm"].as_f64().unwrap();
        assert!(w > 1.2, "the wide target this is about: {row}");
        let mut rules = Rules { clearance: 0.2, ..Rules::default() };
        rules.track = 0.2;
        rules.stub = 0.2;
        for (k, n) in ts[0].nets.iter().enumerate() {
            rules.impedance.insert(n.clone(), crate::rules::ImpedanceRoute { max_skew: 0.5, target: "USB".into(), width: w, layer: "F.Cu".into(), partner: Some(ts[0].nets[1 - k].clone()), pitch: row["pitchMm"].as_f64() });
        }
        let mut r = Router::new(b, rules, false);
        let (mut plan, _report, failed) = crate::drive::route_board(&mut r, 3, 8, 400);
        assert_eq!(failed, 0, "the pair routes at all (at the rule width)");
        crate::simplify::simplify_plan(&mut r, &mut plan);
        let rep = widen_plan(&mut r, &mut plan);
        let wide: f64 = ["DP", "DN"].iter().map(|n| rep["nets"][*n]["wideMm"].as_f64().unwrap_or(0.0)).sum();
        assert!(wide > 30.0, "most of the 30 mm run is at the target width: {rep}");
        assert!(plan.iter().any(|e| (e["width"].as_f64().unwrap_or(0.0) - w).abs() < 1e-9), "a plan entry at the target width");
        let (tracks, vias) = plan_tracks(&serde_json::json!({"nets": plan}), &r.board);
        let c = check_target(&ts[0], &st, &tracks, &vias, &r.board.pads, &crate::impedance::GroundCopper::default());
        eprintln!("{rep}\n{c}");
        assert!(c["uncontrolledMm"][0].as_f64().unwrap() < 8.0, "only the necks are uncontrolled: {c}");
        // the skew left by the fan-out is tuned out on the shorter net
        let before = c["skewMm"].as_f64().unwrap();
        let tune = tune_pairs(&mut r, &mut plan);
        let (tracks, vias) = plan_tracks(&serde_json::json!({"nets": plan}), &r.board);
        let c2 = check_target(&ts[0], &st, &tracks, &vias, &r.board.pads, &crate::impedance::GroundCopper::default());
        eprintln!("{tune}\n{c2}");
        assert!(before > 0.5, "the case needs tuning: {c}");
        assert!(c2["skewMm"].as_f64().unwrap() <= 0.5, "tuned within maxSkewMm: {tune} {c2}");
        assert!(c2["coupledPercent"][0].as_f64().unwrap() > 70.0 && c2["coupledPercent"][1].as_f64().unwrap() > 70.0, "still mostly coupled: {c2}");
        assert_eq!(c2["status"], "pass", "{c2}");
    }

    #[test]
    fn a_bump_adds_the_length_it_should() {
        assert!((bump_gain(1.0) - 0.8284).abs() < 1e-3);
    }

    #[test]
    fn runs_split_where_the_verdict_changes_and_drop_collinear_points() {
        let ps = pieces(&[(0.0, 0.0), (1.0, 0.0)]);
        assert_eq!(ps.len(), 10);
        let ok: Vec<bool> = (0..10).map(|k| (2..8).contains(&k)).collect();
        let r = runs(&ps, &ok);
        assert_eq!(r.len(), 3);
        assert_eq!((r[0].0, r[1].0, r[2].0), (false, true, false));
        assert_eq!(r[1].1.len(), 2, "a straight run is two points: {:?}", r[1].1);
        assert!((r[1].1[0].0 - 0.2).abs() < 1e-9 && (r[1].1[1].0 - 0.8).abs() < 1e-9);
    }
}