AI Flow

//! Paths along one net's copper on a board: pads, track pieces, vias and filled zone islands as a
//! graph, and the shortest path between two pads on it. This is how the decoupling review measures
//! the routed path from a cap's supply pad to its assigned pin (the plan applied to the board, plus
//! the copper already there), never a straight line, and never across zone polygons that no fill
//! joins. Lengths are along track centrelines; a stretch through a filled island counts the straight
//! distance across it and is flagged, since that copper has no single path.
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

use aiflow_board::{geom, Board, Pt};
use serde_json::{json, Value};

use crate::decoupling::Resolved;

#[derive(Clone, Copy, PartialEq, Debug)]
enum Kind {
    Pad,
    Point,
    Via,
}

/// One net's copper as a graph.
pub struct NetGraph {
    pos: Vec<Pt>,
    /// None: both layers (a via, a through-hole pad).
    layer: Vec<Option<usize>>,
    kind: Vec<Kind>,
    label: Vec<String>,
    /// (to, mm, through a zone fill)
    adj: Vec<Vec<(usize, f64, bool)>>,
    pad_node: HashMap<String, usize>,
    /// The net has zones, and whether any is filled in this board.
    pub zones: usize,
    pub filled_islands: usize,
}

/// A path between two pads.
#[derive(Clone, Debug)]
pub struct Path {
    pub length_mm: f64,
    pub vias: usize,
    /// Other pads of the net the path passes through (the rail tree).
    pub through_pads: Vec<String>,
    pub through_fill: bool,
    /// Points on the path where other copper of the net leaves it (a T, a rail landing). A path
    /// with two or more is a stretch of the rail tree between two landings, not a local connection.
    pub branch_points: usize,
}

/// Shortest distances from one pad.
pub struct Dist {
    dist: Vec<f64>,
    prev: Vec<usize>,
    prev_fill: Vec<bool>,
    src: usize,
}

const TOL: f64 = 1e-3;

impl NetGraph {
    pub fn build(board: &Board, net: &str) -> NetGraph {
        let mut g = NetGraph { pos: Vec::new(), layer: Vec::new(), kind: Vec::new(), label: Vec::new(), adj: Vec::new(), pad_node: HashMap::new(), zones: 0, filled_islands: 0 };
        let add = |g: &mut NetGraph, p: Pt, l: Option<usize>, k: Kind, s: String| -> usize {
            g.pos.push(p);
            g.layer.push(l);
            g.kind.push(k);
            g.label.push(s);
            g.adj.push(Vec::new());
            g.pos.len() - 1
        };
        let pads: Vec<&aiflow_board::Pad> = board.pads.iter().filter(|p| p.net == net).collect();
        let mut pad_ids = Vec::new();
        for p in &pads {
            let l = if p.thru || (p.on_f && p.on_b) { None } else if p.on_f { Some(aiflow_board::F_CU) } else { Some(aiflow_board::B_CU) };
            let id = add(&mut g, (p.x, p.y), l, Kind::Pad, p.key.clone());
            g.pad_node.insert(p.key.clone(), id);
            pad_ids.push(id);
        }
        let tracks: Vec<aiflow_board::Track> = board.tracks().into_iter().filter(|t| t.net == net).collect();
        let mut ends = Vec::new(); // (node a, node b, half width)
        let mut point_hw: HashMap<usize, f64> = HashMap::new();
        // track ends at one spot on one layer are one node (a corner, a joint)
        let mut at: HashMap<(i64, i64, usize), usize> = HashMap::new();
        for t in &tracks {
            let mut node = |g: &mut NetGraph, p: Pt| -> usize {
                let key = ((p.0 * 1e4).round() as i64, (p.1 * 1e4).round() as i64, t.layer);
                let id = *at.entry(key).or_insert_with(|| add(g, p, Some(t.layer), Kind::Point, String::new()));
                let hw = point_hw.entry(id).or_insert(0.0);
                *hw = hw.max(t.width / 2.0);
                id
            };
            let a = node(&mut g, t.a);
            let b = node(&mut g, t.b);
            ends.push((a, b, t.width / 2.0));
        }
        let vias: Vec<aiflow_board::Via> = board.vias().into_iter().filter(|v| v.net == net).collect();
        let mut via_ids = Vec::new();
        for v in &vias {
            let id = add(&mut g, (v.x, v.y), None, Kind::Via, format!("via ({:.2}, {:.2})", v.x, v.y));
            point_hw.insert(id, v.size / 2.0);
            via_ids.push(id);
        }
        // each track piece: its own ends plus every point or via that touches it, chained along it
        let feature_nodes: Vec<usize> = point_hw.keys().copied().collect();
        for (ti, t) in tracks.iter().enumerate() {
            let (a, b, hw) = ends[ti];
            let len = (t.b.0 - t.a.0).hypot(t.b.1 - t.a.1);
            let (ux, uy) = if len > 1e-9 { ((t.b.0 - t.a.0) / len, (t.b.1 - t.a.1) / len) } else { (0.0, 0.0) };
            let mut on: Vec<(f64, usize)> = vec![(0.0, a), (len, b)];
            let (x0, x1) = (t.a.0.min(t.b.0) - hw - 1.0, t.a.0.max(t.b.0) + hw + 1.0);
            let (y0, y1) = (t.a.1.min(t.b.1) - hw - 1.0, t.a.1.max(t.b.1) + hw + 1.0);
            for &n in &feature_nodes {
                if n == a || n == b {
                    continue;
                }
                if let Some(l) = g.layer[n] {
                    if l != t.layer {
                        continue;
                    }
                }
                let (x, y) = g.pos[n];
                if x < x0 || x > x1 || y < y0 || y > y1 {
                    continue;
                }
                let reach = hw + point_hw[&n] + TOL;
                if geom::seg_distance(x, y, t.a.0, t.a.1, t.b.0, t.b.1) <= reach {
                    let s = ((x - t.a.0) * ux + (y - t.a.1) * uy).clamp(0.0, len);
                    on.push((s, n));
                }
            }
            on.sort_by(|p, q| p.0.partial_cmp(&q.0).unwrap());
            for w in on.windows(2) {
                g.link(w[0].1, w[1].1, w[1].0 - w[0].0, false);
            }
        }
        // pads: a track end or a via on the pad's copper joins it at its centre
        for (pi, p) in pads.iter().enumerate() {
            let pn = pad_ids[pi];
            for &n in &feature_nodes {
                let on_layer = match g.layer[n] { Some(l) => p.thru || p.on_layer(l), None => true };
                if !on_layer {
                    continue;
                }
                let (x, y) = g.pos[n];
                if (x - p.x).abs() > p.half_long + 2.0 || (y - p.y).abs() > p.half_long + 2.0 {
                    continue;
                }
                let r = if g.kind[n] == Kind::Via { TOL } else { point_hw[&n] + TOL };
                if p.polys.iter().any(|poly| geom::point_poly_distance(x, y, poly) <= r) {
                    let d = (x - p.x).hypot(y - p.y);
                    g.link(pn, n, d, false);
                }
            }
        }
        // filled zone islands: everything on one island is joined, straight across it
        for z in board.zones().iter().filter(|z| z.net == net) {
            g.zones += 1;
            for (l, poly) in &z.fills {
                g.filled_islands += 1;
                let mut members = Vec::new();
                for n in 0..g.pos.len() {
                    let on_layer = match g.layer[n] { Some(x) => x == *l, None => true };
                    if !on_layer {
                        continue;
                    }
                    let (x, y) = g.pos[n];
                    let inside = if g.kind[n] == Kind::Pad {
                        let p = pads[pad_ids.iter().position(|&q| q == n).unwrap()];
                        geom::point_in_poly(x, y, poly) || p.polys.iter().flatten().any(|v| geom::point_in_poly(v.0, v.1, poly))
                    } else {
                        geom::point_poly_distance(x, y, poly) <= point_hw.get(&n).copied().unwrap_or(0.0) + TOL
                    };
                    if inside {
                        members.push(n);
                    }
                }
                for i in 0..members.len() {
                    for j in i + 1..members.len() {
                        let (a, b) = (members[i], members[j]);
                        let d = (g.pos[a].0 - g.pos[b].0).hypot(g.pos[a].1 - g.pos[b].1);
                        g.link(a, b, d, true);
                    }
                }
            }
        }
        g
    }

    fn link(&mut self, a: usize, b: usize, d: f64, fill: bool) {
        if a == b {
            return;
        }
        self.adj[a].push((b, d, fill));
        self.adj[b].push((a, d, fill));
    }

    pub fn has_pad(&self, key: &str) -> bool {
        self.pad_node.contains_key(key)
    }

    /// Shortest copper distances from a pad of the net.
    pub fn from_pad(&self, key: &str) -> Option<Dist> {
        let src = *self.pad_node.get(key)?;
        let n = self.pos.len();
        let mut dist = vec![f64::INFINITY; n];
        let mut prev = vec![usize::MAX; n];
        let mut prev_fill = vec![false; n];
        let mut heap = BinaryHeap::new();
        dist[src] = 0.0;
        heap.push(Reverse((0i64, src)));
        while let Some(Reverse((dk, u))) = heap.pop() {
            if dk > (dist[u] * 1e6) as i64 {
                continue;
            }
            for &(v, w, fill) in &self.adj[u] {
                let nd = dist[u] + w;
                if nd + 1e-9 < dist[v] {
                    dist[v] = nd;
                    prev[v] = u;
                    prev_fill[v] = fill;
                    heap.push(Reverse(((nd * 1e6) as i64, v)));
                }
            }
        }
        Some(Dist { dist, prev, prev_fill, src })
    }

    /// The path from the Dist's source pad to this pad, if copper joins them.
    pub fn path_to(&self, d: &Dist, key: &str) -> Option<Path> {
        let t = *self.pad_node.get(key)?;
        if !d.dist[t].is_finite() {
            return None;
        }
        let mut nodes = vec![t];
        let mut fill = false;
        let mut c = t;
        while c != d.src {
            fill |= d.prev_fill[c];
            c = d.prev[c];
            nodes.push(c);
        }
        nodes.reverse();
        let mut vias = 0;
        let mut branches = 0;
        let mut through = Vec::new();
        for k in 1..nodes.len().saturating_sub(1) {
            let n = nodes[k];
            match self.kind[n] {
                Kind::Via => {
                    // a layer change: the copper before and after the via is on different layers
                    let before = (0..k).rev().find_map(|q| self.layer[nodes[q]]);
                    let after = (k + 1..nodes.len()).find_map(|q| self.layer[nodes[q]]);
                    if let (Some(a), Some(b)) = (before, after) {
                        if a != b && self.layer[nodes[k - 1]].is_some() && self.layer[nodes[k + 1]].is_some() {
                            vias += 1;
                        }
                    }
                }
                Kind::Pad => through.push(self.label[n].clone()),
                Kind::Point => {}
            }
            // a landing on the end pads themselves is not a rail branch; other pads' links are not copper runs
            let at_end = self.adj[n].iter().any(|e| !e.2 && (e.0 == t || e.0 == d.src));
            if self.kind[n] != Kind::Pad && !at_end {
                let mut nb: Vec<usize> = self.adj[n].iter().filter(|e| !e.2 && e.0 != n && self.kind[e.0] != Kind::Pad).map(|e| e.0).collect();
                nb.sort_unstable();
                nb.dedup();
                if nb.len() >= 3 {
                    branches += 1;
                }
            }
        }
        Some(Path { length_mm: d.dist[t], vias, through_pads: through, through_fill: fill, branch_points: branches })
    }

    /// Every pad of the net with its copper distance from the Dist's source.
    pub fn pad_distances(&self, d: &Dist) -> Vec<(String, f64)> {
        let mut v: Vec<(String, f64)> = self.pad_node.iter().filter(|(_, &n)| n != d.src && d.dist[n].is_finite()).map(|(k, &n)| (k.clone(), d.dist[n])).collect();
        v.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap().then(a.0.cmp(&b.0)));
        v
    }
}

impl Path {
    /// Through other pads, or along a stretch of the rail between two landings.
    pub fn detour(&self) -> bool {
        !self.through_pads.is_empty() || self.branch_points >= 2
    }
}

/// Where the zone fills in the measured board came from, and whether they are current.
#[derive(Clone, Debug, Default)]
pub struct FillContext {
    /// The fills were refilled natively after the last copper change: a path through them is verified.
    pub fills_current: bool,
    /// Words for where the fills came from (the saved board file, an approximate raster fill, ...).
    pub fill_source: String,
    /// Nets with pours planned but not on the board (plan-pours.json not landed and refilled yet).
    pub planned_pour_nets: Vec<String>,
}

fn r2(x: f64) -> f64 {
    (x * 100.0).round() / 100.0
}

fn pad_gap(a: &aiflow_board::Pad, b: &aiflow_board::Pad) -> f64 {
    let mut best = f64::INFINITY;
    for pa in &a.polys {
        for pb in &b.polys {
            for v in pa {
                best = best.min(geom::point_poly_distance(v.0, v.1, pb));
            }
            for v in pb {
                best = best.min(geom::point_poly_distance(v.0, v.1, pa));
            }
        }
    }
    if best.is_finite() { best } else { 0.0 }
}

/// The acceptance review of every pair on a board (the plan applied plus the copper already there).
/// Per pair: the routed copper path from the cap supply pad to the assigned pin (length, vias, the
/// other pads it passes), the nearest same-net pin of the same part by copper, the straight pad
/// distance, the ground return by connectivity, and findings against the pair's own budget.
pub fn review(board: &Board, pairs: &[Resolved], ctx: &FillContext) -> Value {
    let mut entries = Vec::new();
    let (mut warnings, mut errors) = (0usize, 0usize);
    let mut graphs: HashMap<String, NetGraph> = HashMap::new();
    for p in pairs {
        let sev = if p.spec.is_error() { "error" } else { "warning" };
        let mut findings: Vec<Value> = Vec::new();
        let cap = board.pad_by_key(&p.cap_pad).unwrap();
        let pin = board.pad_by_key(&p.pin).unwrap();
        let straight = (cap.x - pin.x).hypot(cap.y - pin.y);
        let g = graphs.entry(p.net.clone()).or_insert_with(|| NetGraph::build(board, &p.net));
        let d = g.from_pad(&p.cap_pad).unwrap();
        let path = g.path_to(&d, &p.pin);
        let nearest = g.pad_distances(&d).into_iter().find(|(k, _)| board.pad_by_key(k).map(|q| q.reference == pin.reference).unwrap_or(false));
        let assigned = match &path {
            Some(x) => json!({"connected": true, "pathMm": r2(x.length_mm), "vias": x.vias, "throughPads": x.through_pads, "branchPoints": x.branch_points, "detour": x.detour(), "throughFill": x.through_fill}),
            None => json!({"connected": false, "pathMm": Value::Null, "vias": Value::Null, "throughPads": [], "branchPoints": Value::Null, "detour": Value::Null, "throughFill": false}),
        };
        match &path {
            None => findings.push(json!({"severity": sev, "text": format!("{}: no copper joins {} to {} yet", p.label, p.cap_pad, p.pin)})),
            Some(x) => {
                if !x.through_pads.is_empty() {
                    findings.push(json!({"severity": sev, "text": format!("{}: the copper path detours through the rail ({}), {:.2} mm against {:.2} mm straight; the cap reaches its pin through other pads", p.label, x.through_pads.join(", "), x.length_mm, straight)}));
                } else if x.branch_points >= 2 {
                    findings.push(json!({"severity": sev, "text": format!("{}: the copper path runs along the rail tree ({} rail branch points on it), {:.2} mm against {:.2} mm straight; the cap and the pin each land on the rail instead of on each other", p.label, x.branch_points, x.length_mm, straight)}));
                }
                if let Some(ml) = p.spec.max_length_mm {
                    if x.length_mm > ml + 1e-6 {
                        findings.push(json!({"severity": sev, "text": format!("{}: copper path {:.2} mm, over maxLengthMm {ml}", p.label, x.length_mm)}));
                    }
                }
                if let Some(mv) = p.spec.max_vias {
                    if x.vias > mv {
                        findings.push(json!({"severity": sev, "text": format!("{}: {} via(s) on the path, over maxVias {mv}", p.label, x.vias)}));
                    }
                }
            }
        }
        // ground return, by connectivity only
        let ground = match (&p.gnd_pad, &p.gnd_net) {
            (Some(gp), Some(gn)) => {
                let gg = graphs.entry(gn.clone()).or_insert_with(|| NetGraph::build(board, gn));
                let gd = gg.from_pad(gp);
                let planned = ctx.planned_pour_nets.iter().any(|n| n == gn);
                let mut returns = Vec::new();
                for rp in &p.return_pins {
                    let q = board.pad_by_key(rp).unwrap();
                    let s = r2((q.x - board.pad_by_key(gp).unwrap().x).hypot(q.y - board.pad_by_key(gp).unwrap().y));
                    let found = gd.as_ref().and_then(|d| gg.path_to(d, rp));
                    let v = match found {
                        Some(x) if !x.through_fill => json!({"pin": rp, "status": "copper", "verified": true, "pathMm": r2(x.length_mm), "vias": x.vias, "throughPads": x.through_pads, "straightMm": s}),
                        Some(x) if ctx.fills_current => json!({"pin": rp, "status": "fill", "verified": true, "pathMm": r2(x.length_mm), "vias": x.vias, "throughPads": x.through_pads, "straightMm": s, "note": format!("through filled zone islands ({}); the length is straight across the fill", ctx.fill_source)}),
                        Some(x) => json!({"pin": rp, "status": "fill-unverified", "verified": false, "pathMm": r2(x.length_mm), "vias": x.vias, "straightMm": s, "note": format!("joined only through zone fills that are not a native refill of this copper ({}); refill natively (land pours, measure) and review again", ctx.fill_source)}),
                        None if gg.zones > 0 || planned => json!({"pin": rp, "status": "unverified", "verified": false, "pathMm": Value::Null, "straightMm": s, "note": "only planned or unfilled pours could join these pads; no refilled native fill data, so the return is unverified (the straight distance is not a path)"}),
                        None => json!({"pin": rp, "status": "open", "verified": false, "pathMm": Value::Null, "straightMm": s, "note": "no copper joins these pads"}),
                    };
                    returns.push(v);
                }
                json!({"gndPad": gp, "net": gn, "returns": returns})
            }
            _ => Value::Null,
        };
        for f in &findings {
            if f["severity"] == "error" { errors += 1 } else { warnings += 1 }
        }
        entries.push(json!({
            "pair": p.label, "net": p.net, "capPad": p.cap_pad, "pin": p.pin, "severity": sev,
            "budget": {"maxLengthMm": p.spec.max_length_mm, "maxVias": p.spec.max_vias},
            "assignedPin": assigned,
            "nearestSameNetPin": nearest.map(|(k, mm)| json!({"pin": k, "pathMm": r2(mm)})),
            "straightMm": r2(straight), "padGapMm": r2(pad_gap(cap, pin)),
            "groundReturn": ground, "findings": findings,
        }));
    }
    json!({"pairs": entries.len(), "warnings": warnings, "errors": errors, "entries": entries,
        "method": "shortest path along this net's copper (tracks, vias, pads, and filled zone islands straight across) from the cap supply pad to the pin; budgets are the spec's own"})
}