AI Flow

//! Assigned-pin decoupling (spec "decoupling", issue #32).
//!
//! A decoupling capacitor serves one supply pin. A rail tree that is DRC-clean can still reach that
//! pin the long way round (cap to another pin, along the rail, back to the assigned pin). A spec entry
//!
//! ```json
//! {"cap": "C6", "pin": "U1.39", "capPad": "C6.1", "gndPad": "C6.2", "returnPins": ["U1.38"],
//!  "maxLengthMm": 3.0, "maxVias": 0, "severity": "warning"}
//! ```
//!
//! names the pair. Only `cap` and `pin` are required: the cap's supply pad is its pad on the pin's net,
//! its ground pad the pad on its other net. The router routes the direct connection (cap supply pad to
//! the pin) before any rail distribution, with the net's own widths, clearances and vias, and keeps it
//! through rip-up; the rest of the net then joins that copper. A pair it cannot route directly is said
//! in the router log and the report and falls back to normal routing. There is no default budget:
//! `maxLengthMm` and `maxVias` are this board's, and without them the length is reported only.
use std::collections::HashSet;

use aiflow_board::Board;
use aiflow_grid::RES;
use serde::{Deserialize, Serialize};
use serde_json::{json, Value};

use crate::drive::Search;
use crate::{End, Route, Router, Term};

/// One spec `decoupling` entry, as written.
#[derive(Clone, Debug, Default, Serialize, Deserialize)]
#[serde(default, rename_all = "camelCase")]
pub struct Pair {
    /// The capacitor's reference (`C6`), or its supply pad key (`C6.1`).
    pub cap: String,
    /// The supply pin the cap serves, as a pad key (`U1.39`).
    pub pin: String,
    /// The cap's supply pad; inferred as the cap pad on the pin's net when absent.
    pub cap_pad: Option<String>,
    /// The cap's ground pad; inferred as the cap pad on its other net when absent.
    pub gnd_pad: Option<String>,
    /// The IC's return pins for this pair (on the ground pad's net), reported by connectivity.
    pub return_pins: Vec<String>,
    /// This board's budget for the routed path, cap supply pad to pin. None: report only.
    pub max_length_mm: Option<f64>,
    /// This board's budget for layer changes on that path. None: report only; 0 also keeps the
    /// router's direct connection on one layer.
    pub max_vias: Option<usize>,
    /// "warning" (default) or "error" for a finding on this pair.
    pub severity: Option<String>,
    pub note: Option<String>,
}

impl Pair {
    /// Every `decoupling` entry of a spec (an array, or one object). An entry that does not parse,
    /// or has a bad severity or budget, is an error naming it.
    pub fn from_spec(spec: &Value) -> Result<Vec<Pair>, String> {
        let v = spec.get("decoupling").cloned().unwrap_or(Value::Null);
        let items = match v {
            Value::Array(a) => a,
            Value::Object(_) => vec![v],
            Value::Null => Vec::new(),
            _ => return Err("decoupling must be an array of {cap, pin, ...} entries".into()),
        };
        let mut out = Vec::new();
        for (k, e) in items.into_iter().enumerate() {
            let p: Pair = serde_json::from_value(e).map_err(|x| format!("decoupling[{k}]: {x}"))?;
            if p.cap.is_empty() || p.pin.is_empty() {
                return Err(format!("decoupling[{k}]: cap and pin are required"));
            }
            if let Some(s) = &p.severity {
                if s != "warning" && s != "error" {
                    return Err(format!("decoupling[{k}]: severity is \"warning\" or \"error\", not {s:?}"));
                }
            }
            if p.max_length_mm.map(|m| !(m > 0.0)).unwrap_or(false) {
                return Err(format!("decoupling[{k}]: maxLengthMm must be a positive length in mm"));
            }
            out.push(p);
        }
        Ok(out)
    }

    pub fn is_error(&self) -> bool {
        self.severity.as_deref() == Some("error")
    }
}

/// A pair resolved on a board: pad keys and nets.
#[derive(Clone, Debug)]
pub struct Resolved {
    pub label: String,
    pub net: String,
    pub cap_pad: String,
    pub pin: String,
    pub gnd_pad: Option<String>,
    pub gnd_net: Option<String>,
    pub return_pins: Vec<String>,
    pub spec: Pair,
}

/// Resolve the pairs on the board. Returns the pairs that resolve and one problem per pair that does not.
pub fn resolve(board: &Board, pairs: &[Pair]) -> (Vec<Resolved>, Vec<String>) {
    let mut ok = Vec::new();
    let mut problems = Vec::new();
    for p in pairs {
        match resolve_one(board, p) {
            Ok(r) => ok.push(r),
            Err(e) => problems.push(format!("decoupling {} -> {}: {e}", p.cap, p.pin)),
        }
    }
    (ok, problems)
}

fn resolve_one(board: &Board, p: &Pair) -> Result<Resolved, String> {
    let pin = board.pad_by_key(&p.pin).ok_or_else(|| format!("pin {} is not a pad on this board (use REF.PAD, e.g. U1.39)", p.pin))?;
    let net = pin.net.clone();
    if net.is_empty() {
        return Err(format!("pin {} has no net", p.pin));
    }
    // the cap: a reference, or a pad key standing for its supply pad
    let (cap_ref, given_pad) = match board.pad_by_key(&p.cap) {
        Some(cp) if board.footprints.get(&p.cap).is_none() => (cp.reference.clone(), Some(p.cap.clone())),
        _ => (p.cap.clone(), p.cap_pad.clone()),
    };
    let pads = board.pads_of(&cap_ref);
    if pads.is_empty() {
        return Err(format!("no part {cap_ref} on this board"));
    }
    let cap_pad = match given_pad {
        Some(k) => {
            let cp = board.pad_by_key(&k).ok_or_else(|| format!("capPad {k} is not a pad on this board"))?;
            if cp.reference != cap_ref {
                return Err(format!("capPad {k} is not a pad of {cap_ref}"));
            }
            if cp.net != net {
                return Err(format!("capPad {k} is on {:?}, the pin {} is on {net:?}", cp.net, p.pin));
            }
            k
        }
        None => {
            let on: Vec<&&aiflow_board::Pad> = pads.iter().filter(|q| q.net == net).collect();
            match on.len() {
                0 => return Err(format!("{cap_ref} has no pad on {net:?} (the net of {})", p.pin)),
                1 => on[0].key.clone(),
                _ => return Err(format!("{cap_ref} has {} pads on {net:?}; name the supply pad with capPad", on.len())),
            }
        }
    };
    if cap_pad == p.pin {
        return Err("the cap pad and the pin are the same pad".into());
    }
    let gnd_pad = match &p.gnd_pad {
        Some(k) => {
            let g = board.pad_by_key(k).ok_or_else(|| format!("gndPad {k} is not a pad on this board"))?;
            if g.reference != cap_ref {
                return Err(format!("gndPad {k} is not a pad of {cap_ref}"));
            }
            if g.net.is_empty() || g.net == net {
                return Err(format!("gndPad {k} is on {:?}; it must be the cap's other net", g.net));
            }
            Some(k.clone())
        }
        None => {
            let others: Vec<&&aiflow_board::Pad> = pads.iter().filter(|q| !q.net.is_empty() && q.net != net).collect();
            let nets: HashSet<&str> = others.iter().map(|q| q.net.as_str()).collect();
            if nets.len() == 1 { Some(others[0].key.clone()) } else { None }
        }
    };
    let gnd_net = gnd_pad.as_ref().and_then(|k| board.pad_by_key(k)).map(|g| g.net.clone());
    for rp in &p.return_pins {
        let Some(q) = board.pad_by_key(rp) else { return Err(format!("return pin {rp} is not a pad on this board")) };
        match &gnd_net {
            None => return Err(format!("returnPins given but {cap_ref} has no single ground pad; name it with gndPad")),
            Some(g) if &q.net != g => return Err(format!("return pin {rp} is on {:?}, the cap's ground pad is on {g:?}", q.net)),
            _ => {}
        }
    }
    Ok(Resolved { label: format!("{cap_pad}->{}", p.pin), net, cap_pad, pin: p.pin.clone(), gnd_pad, gnd_net, return_pins: p.return_pins.clone(), spec: p.clone() })
}

/// A pair in the router: its net and clusters, and what the last attempt said.
#[derive(Clone, Debug)]
pub struct PairState {
    pub r: Resolved,
    pub net: Option<usize>,
    pub cap_cluster: Option<usize>,
    pub pin_cluster: Option<usize>,
    pub note: String,
}

/// Grid length (mm) and layer changes of a cell path.
pub fn cells_length(cells: &[Term]) -> (f64, usize) {
    let mut mm = 0.0;
    let mut vias = 0;
    for w in cells.windows(2) {
        if w[0].layer() != w[1].layer() {
            vias += 1;
        } else {
            mm += ((w[1].i - w[0].i) as f64).hypot((w[1].j - w[0].j) as f64) * RES;
        }
    }
    (mm, vias)
}

impl Router {
    /// Resolve the rules' decoupling pairs on this board and find their clusters.
    pub(crate) fn init_decoupling(&mut self) {
        let (resolved, problems) = resolve(&self.board, &self.rules.decoupling);
        for p in problems {
            self.log(format!("  {p}; pair skipped"));
        }
        for r in resolved {
            let net = self.net_ids.get(&r.net).copied();
            let find = |me: &Router, key: &str| -> Option<usize> {
                let pi = me.board.pad_idx(key)?;
                me.nets[net?].clusters.iter().position(|c| c.pads.contains(&pi))
            };
            let (a, b) = (find(self, &r.cap_pad), find(self, &r.pin));
            self.pairs.push(PairState { r, net, cap_cluster: a, pin_cluster: b, note: String::new() });
        }
    }

    /// Is this route tree copper? A decoupling pair route is, once its clusters joined the tree.
    pub fn pair_route_joined(&self, net: usize, r: &Route) -> bool {
        if r.pair.is_none() {
            return true;
        }
        r.start.cluster().map(|c| self.nets[net].clusters[c].connected).unwrap_or(true)
    }

    /// `connect_group` plus every cluster a kept decoupling pair route joins to them (transitively).
    pub fn join_with_pairs(&mut self, net: usize, c: usize) -> Vec<usize> {
        let mut out = self.connect_group(net, c);
        let mut k = 0;
        while k < out.len() {
            let me = out[k];
            let partners: Vec<usize> = self.nets[net].routes.iter().filter(|r| r.pair.is_some()).filter_map(|r| {
                let (s, e) = (r.start.cluster(), r.end.cluster());
                if s == Some(me) { e } else if e == Some(me) { s } else { None }
            }).collect();
            for p in partners {
                if !out.contains(&p) {
                    for q in self.connect_group(net, p) {
                        if !out.contains(&q) {
                            out.push(q);
                        }
                    }
                }
            }
            k += 1;
        }
        out
    }

    /// After a rip that kept the pair routes: their escapes stay used, the pins' other escapes released.
    pub(crate) fn keep_pair_escapes(&mut self, net: usize) {
        let ends: Vec<End> = self.nets[net].routes.iter().filter(|r| r.pair.is_some()).flat_map(|r| [r.start.clone(), r.end.clone()]).collect();
        for e in ends {
            match e {
                End::Escape(c, t) => {
                    self.nets[net].used_escapes.insert((c, t));
                    self.stamp_channel_pub(net, c, t, -1);
                    self.release_escapes(net, c);
                }
                End::Pad(c, _) => self.release_escapes(net, c),
                _ => {}
            }
        }
    }

    /// Route every decoupling pair's direct connection that is not already down. Called at the start
    /// of each pass, before plane stubs and signal nets.
    pub fn route_decoupling(&mut self) {
        for k in 0..self.pairs.len() {
            let ps = self.pairs[k].clone();
            let Some(net) = ps.net else { continue };
            if self.nets[net].routes.iter().any(|r| r.pair == Some(k)) {
                continue;
            }
            let label = format!("decoupling {} ({})", ps.r.label, ps.r.net);
            let (Some(a), Some(b)) = (ps.cap_cluster, ps.pin_cluster) else {
                self.pairs[k].note = "the pads are not routing terminals of their net".into();
                self.log(format!("  {label}: {}; normal routing", self.pairs[k].note));
                continue;
            };
            if a == b {
                self.pairs[k].note = "the cap pad and the pin overlap: joined by their pads".into();
                continue;
            }
            if self.nets[net].done_by_board || (self.comp_of(net, a) == self.comp_of(net, b) && self.joined_by_board(net, a)) {
                self.pairs[k].note = "already joined by the board's own copper".into();
                self.log(format!("  {label}: {}", self.pairs[k].note));
                continue;
            }
            if self.kelvin_clusters.contains(&(net, a)) || self.kelvin_clusters.contains(&(net, b)) || self.rules.kelvin.contains_key(&ps.r.cap_pad) || self.rules.kelvin.contains_key(&ps.r.pin) {
                self.pairs[k].note = "a Kelvin tap owns one of the pads; not routed as a pair".into();
                self.log(format!("  {label}: {}", self.pairs[k].note));
                continue;
            }
            match self.route_pair(k, net, a, b) {
                Ok((mm, vias, w)) => {
                    self.pairs[k].note = String::new();
                    self.stat("decouplingDirect", 1);
                    self.log(format!("  {label}: direct, {mm:.2} mm on the grid, {vias} via(s), {w} mm wide, routed before the rail and kept through rip-up"));
                }
                Err(why) => {
                    self.pairs[k].note = why.clone();
                    self.stat("decouplingFallback", 1);
                    self.log(format!("  {label}: no direct connection ({why}); falls back to normal routing of {}", ps.r.net));
                }
            }
        }
    }

    fn route_pair(&mut self, k: usize, net: usize, a: usize, b: usize) -> Result<(f64, usize, f64), String> {
        let spec = self.pairs[k].r.spec.clone();
        let (ca, cb) = (self.nets[net].clusters[a].clone(), self.nets[net].clusters[b].clone());
        let allow = ca.allow.min(cb.allow);
        let mut widths: Vec<f64> = self.nets[net].widths.iter().copied().filter(|w| *w <= allow).collect();
        if widths.is_empty() {
            widths = vec![self.nets[net].widths.iter().cloned().fold(f64::INFINITY, f64::min)];
        }
        widths.sort_by(|x, y| y.partial_cmp(x).unwrap());
        let sources: Vec<(Term, i64)> = ca.terminals.iter().map(|t| (*t, 0)).collect();
        let targets: HashSet<Term> = cb.terminals.iter().copied().collect();
        let mut pts: Vec<(i64, i64)> = ca.terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
        let tpts: Vec<(i64, i64)> = cb.terminals.iter().map(|t| (t.i as i64, t.j as i64)).collect();
        pts.extend_from_slice(&tpts);
        let allow_via = spec.max_vias != Some(0);
        let mut why = "no path clear of other nets within 4 mm of the pads".to_string();
        for width in widths {
            for margin in [2.0, 4.0] {
                let win = self.window_for(&pts, margin);
                let (cells, _) = self.search(net, width, Search { sources: sources.clone(), targets: Some(&targets), heur: tpts.clone(), win, allow_via, soft: false, via_target: false, max_nodes: Some(200_000), vip: Vec::new() });
                let Some(cells) = cells else { continue };
                let (mm, vias) = cells_length(&cells);
                if let Some(mv) = spec.max_vias {
                    if vias > mv {
                        why = format!("the shortest clear path needs {vias} via(s), maxVias {mv}");
                        continue;
                    }
                }
                if let Some(ml) = spec.max_length_mm {
                    if mm > ml {
                        why = format!("the shortest clear path is {mm:.2} mm, maxLengthMm {ml}");
                        continue;
                    }
                }
                let start = if ca.escapes.contains_key(&cells[0]) { End::Escape(a, cells[0]) } else { End::Pad(a, cells[0]) };
                let last = *cells.last().unwrap();
                let end = if cb.escapes.contains_key(&last) { End::Escape(b, last) } else { End::Pad(b, last) };
                let mut r = Route::new(cells, width, start, end);
                r.pair = Some(k);
                self.commit(net, r);
                return Ok((mm, vias, width));
            }
        }
        Err(why)
    }

    /// Per pair: routed directly or not, the grid length and vias of the direct route, and why not.
    pub fn decoupling_report(&self) -> Value {
        let mut out = Vec::new();
        for (k, p) in self.pairs.iter().enumerate() {
            let route = p.net.and_then(|n| self.nets[n].routes.iter().find(|r| r.pair == Some(k)));
            let (mm, vias) = route.map(|r| cells_length(&r.cells)).unwrap_or((0.0, 0));
            out.push(json!({
                "pair": p.r.label, "net": p.r.net, "capPad": p.r.cap_pad, "pin": p.r.pin, "direct": route.is_some(),
                "gridMm": route.map(|_| (mm * 100.0).round() / 100.0), "vias": route.map(|_| vias), "widthMm": route.map(|r| r.width),
                "note": if route.is_some() { Value::Null } else { json!(if p.note.is_empty() { "not routed as a pair" } else { p.note.as_str() }) },
            }));
        }
        Value::Array(out)
    }
}