AI Flow: Routing

//! What a pour becomes when KiCad refills it. The router and the rest of the checker read a zone as
//! the shape saved in the file, one piece of copper; a refill cuts it around every track of another
//! net, and an island with something on it stays as a separate piece (benchmark B: KiCad's DRC
//! reported /USB2_VBUS unconnected to itself while every join here read closed).
//!
//! The model: per net and layer, rasterise the zones and close each cell within clearance plus half
//! `min_thickness` of foreign copper. What stays open is where the centre of a `min_thickness` brush
//! can reach, so a neck too thin to survive the fill's own erosion reads as cut. Copper of the net
//! joins whatever open cells lie within reach, and islands nothing touches are dropped, as KiCad's
//! island removal drops them. KiCad's DRC stays the judge; this exists to see splits while routing.

use crate::board::*;
use crate::conn::{touches, Piece, Uf};
use crate::geom::*;
use crate::index::Owner;
use crate::rules::Rules;
use crate::search::World;
use std::collections::{BTreeMap, BTreeSet};

/// Grid pitch. Half a cell of slack on the clearance, so a lane exactly one brush wide stays open.
const STEP: f64 = 0.05 * NM;
const SLACK: f64 = STEP * 0.75;

pub struct Split {
    pub net: NetId,
    pub layer: usize,
    pub at: V,
    /// Pieces beyond what plain connectivity already counts as open.
    pub extra: usize,
    /// Nets whose copper, gone, would rejoin the pieces.
    pub cutters: Vec<NetId>,
}

struct Raster {
    layer: usize,
    x0: f64,
    y0: f64,
    w: usize,
    h: usize,
    inside: Vec<bool>,
    blocked: Vec<u16>,
    /// The cells each foreign net closes, once per obstacle.
    by_net: BTreeMap<NetId, Vec<u32>>,
    /// Item index and the cells it reaches.
    reach: Vec<(usize, Vec<u32>)>,
}

impl Raster {
    fn at(&self, i: usize) -> V {
        V(self.x0 + (i % self.w) as f64 * STEP, self.y0 + (i / self.w) as f64 * STEP)
    }

    /// The cell nearest a point, if the point lies on the raster.
    fn index(&self, p: V) -> Option<usize> {
        let (cx, cy) = (((p.0 - self.x0) / STEP).round(), ((p.1 - self.y0) / STEP).round());
        (cx >= 0.0 && cy >= 0.0 && (cx as usize) < self.w && (cy as usize) < self.h).then(|| cy as usize * self.w + cx as usize)
    }

    fn fill_poly(&mut self, pts: &[V]) {
        let n = pts.len();
        for row in 0..self.h {
            let y = self.y0 + row as f64 * STEP;
            let mut xs: Vec<f64> = Vec::new();
            for k in 0..n {
                let (a, b) = (pts[k], pts[(k + 1) % n]);
                if (a.1 <= y) != (b.1 <= y) {
                    xs.push(a.0 + (y - a.1) / (b.1 - a.1) * (b.0 - a.0));
                }
            }
            xs.sort_by(|p, q| p.total_cmp(q));
            for c in xs.chunks(2) {
                if c.len() < 2 {
                    continue;
                }
                let first = ((c[0] - self.x0) / STEP).ceil().max(0.0) as usize;
                let last = ((c[1] - self.x0) / STEP).floor().min(self.w as f64 - 1.0);
                if last < 0.0 {
                    continue;
                }
                for col in first..=last as usize {
                    self.inside[row * self.w + col] = true;
                }
            }
        }
    }

    /// Cells of the bounding box `bb` grown by `need`, in order.
    fn cells(&self, bb: (f64, f64, f64, f64), need: f64) -> Vec<usize> {
        let span = |lo: f64, hi: f64, o: f64, n: usize| -> Option<(usize, usize)> {
            let a = ((lo - need - o) / STEP).floor().max(0.0) as usize;
            let b = ((hi + need - o) / STEP).ceil();
            if b < 0.0 || a >= n {
                return None;
            }
            Some((a, (b as usize).min(n - 1)))
        };
        let (Some((c0, c1)), Some((r0, r1))) = (span(bb.0, bb.2, self.x0, self.w), span(bb.1, bb.3, self.y0, self.h)) else { return Vec::new() };
        let mut out = Vec::with_capacity((c1 - c0 + 1) * (r1 - r0 + 1));
        for r in r0..=r1 {
            for c in c0..=c1 {
                out.push(r * self.w + c);
            }
        }
        out
    }

    fn close(&mut self, shape: &Shape, need: f64, net: NetId) {
        let mut hit = Vec::new();
        for i in self.cells(shape.bbox(), need) {
            if self.inside[i] && shape.dist_pt(self.at(i)) < need {
                hit.push(i as u32);
            }
        }
        for &i in &hit {
            self.blocked[i as usize] = self.blocked[i as usize].saturating_add(1);
        }
        self.by_net.entry(net).or_default().extend(hit);
    }

    /// Labels the open cells, ignoring what `without` closes. 0: closed.
    fn label(&self, without: Option<NetId>) -> (Vec<u32>, u32) {
        let mut blocked = self.blocked.clone();
        if let Some(cells) = without.and_then(|n| self.by_net.get(&n)) {
            for &i in cells {
                blocked[i as usize] -= 1;
            }
        }
        let mut lab = vec![0u32; self.inside.len()];
        let mut next = 0;
        let mut stack = Vec::new();
        for s in 0..lab.len() {
            if lab[s] != 0 || !self.inside[s] || blocked[s] != 0 {
                continue;
            }
            next += 1;
            lab[s] = next;
            stack.push(s);
            while let Some(i) = stack.pop() {
                let (c, r) = (i % self.w, i / self.w);
                let mut go = |j: usize, stack: &mut Vec<usize>| {
                    if lab[j] == 0 && self.inside[j] && blocked[j] == 0 {
                        lab[j] = next;
                        stack.push(j);
                    }
                };
                if c > 0 { go(i - 1, &mut stack); }
                if c + 1 < self.w { go(i + 1, &mut stack); }
                if r > 0 { go(i - self.w, &mut stack); }
                if r + 1 < self.h { go(i + self.w, &mut stack); }
            }
        }
        (lab, next)
    }
}

/// How many pieces the net is in after a refill: anything holding a pad or a kept island.
/// Returns the count and, for the most pieces' smallest kept island, where it lies.
fn pieces(rasters: &[Raster], base: &Uf, is_pad: &[bool], without: Option<NetId>) -> (usize, Option<(usize, V)>) {
    let n = is_pad.len();
    let labelled: Vec<(Vec<u32>, u32)> = rasters.iter().map(|r| r.label(without)).collect();
    let total: u32 = labelled.iter().map(|l| l.1).sum();
    // Items first, then every island of every layer.
    let mut uf = Uf::new(n + total as usize);
    for i in 0..n {
        let root = base.clone().find(i as u32);
        uf.union(i as u32, root);
    }
    let mut kept: BTreeSet<u32> = BTreeSet::new();
    let mut offset = n as u32;
    let mut where_is: Vec<(usize, usize)> = Vec::new();
    for (ri, (r, (lab, count))) in rasters.iter().zip(&labelled).enumerate() {
        for (item, cells) in &r.reach {
            for &c in cells {
                let l = lab[c as usize];
                if l != 0 {
                    let id = offset + l - 1;
                    uf.union(*item as u32, id);
                    kept.insert(id);
                }
            }
        }
        for _ in 0..*count {
            where_is.push((ri, 0));
        }
        offset += count;
    }
    let mut roots: BTreeSet<u32> = BTreeSet::new();
    for (i, pad) in is_pad.iter().enumerate() {
        if *pad {
            roots.insert(uf.find(i as u32));
        }
    }
    for &id in &kept {
        roots.insert(uf.find(id));
    }
    // A cell of the smallest kept island, for the report.
    let mut smallest: Option<(usize, usize, usize)> = None;
    let mut offset = n as u32;
    for (ri, (lab, count)) in labelled.iter().enumerate() {
        let mut sizes = vec![0usize; *count as usize];
        let mut first = vec![0usize; *count as usize];
        for (i, &l) in lab.iter().enumerate() {
            if l != 0 {
                if sizes[l as usize - 1] == 0 {
                    first[l as usize - 1] = i;
                }
                sizes[l as usize - 1] += 1;
            }
        }
        for k in 0..*count as usize {
            if kept.contains(&(offset + k as u32)) && smallest.map(|s| sizes[k] < s.0).unwrap_or(true) {
                smallest = Some((sizes[k], ri, first[k]));
            }
        }
        offset += count;
    }
    (roots.len(), smallest.map(|(_, ri, i)| (rasters[ri].layer, rasters[ri].at(i))))
}

/// The kept islands of a net's pours that a refill leaves apart from the net's largest piece, each
/// with cell centres to try a stitching via at (spread over the island, the most central first).
/// A kept island is one the net's own copper touches: KiCad keeps it, and reports it unconnected.
pub fn loose_islands(board: &Board, rules: &Rules, world: &World, net: NetId) -> Vec<(usize, Vec<V>, Vec<usize>)> {
    let (rasters, base, is_pad, _) = model(board, rules, world, net);
    let n = is_pad.len();
    let labelled: Vec<(Vec<u32>, u32)> = rasters.iter().map(|r| r.label(None)).collect();
    let total: u32 = labelled.iter().map(|l| l.1).sum();
    let mut uf = Uf::new(n + total as usize);
    for i in 0..n {
        let root = base.clone().find(i as u32);
        uf.union(i as u32, root);
    }
    let mut kept: BTreeSet<u32> = BTreeSet::new();
    let mut offset = n as u32;
    let mut starts: Vec<u32> = Vec::new();
    // The net's pads, in the order the model lists its items (pads first), and the pads on each island.
    let pad_ids: Vec<usize> = board.pads.iter().enumerate().filter(|(_, p)| p.net == net && !p.layers.is_empty()).map(|(i, _)| i).collect();
    let mut pads_on: BTreeMap<u32, BTreeSet<usize>> = BTreeMap::new();
    for (r, (lab, count)) in rasters.iter().zip(&labelled) {
        starts.push(offset);
        for (item, cells) in &r.reach {
            for &c in cells {
                let l = lab[c as usize];
                if l != 0 {
                    uf.union(*item as u32, offset + l - 1);
                    kept.insert(offset + l - 1);
                    if let Some(&p) = pad_ids.get(*item) {
                        pads_on.entry(offset + l - 1).or_default().insert(p);
                    }
                }
            }
        }
        offset += count;
    }
    // Cells per connected piece of the net; the largest is the net's body.
    let mut size: BTreeMap<u32, usize> = BTreeMap::new();
    let mut cells_of: BTreeMap<u32, Vec<(usize, usize)>> = BTreeMap::new();
    for (ri, (lab, _)) in labelled.iter().enumerate() {
        for (i, &l) in lab.iter().enumerate() {
            if l != 0 && kept.contains(&(starts[ri] + l - 1)) {
                *size.entry(uf.find(starts[ri] + l - 1)).or_insert(0) += 1;
                cells_of.entry(starts[ri] + l - 1).or_default().push((ri, i));
            }
        }
    }
    let Some((&body, _)) = size.iter().max_by_key(|(k, v)| (**v, std::cmp::Reverse(**k))) else {
        // No pad reaches any piece of the pour (every thermal spoke is starved, or the fill is cut away
        // round each pad): the pour joins nothing, so every group of pads that copper does not join
        // to the largest group is loose. On an I/O carrier board: small pours over pin-header pads
        // left 16 joins open in KiCad, and this returned nothing to mend.
        let mut groups: BTreeMap<u32, Vec<usize>> = BTreeMap::new();
        for (k, &pad) in pad_ids.iter().enumerate() {
            groups.entry(uf.find(k as u32)).or_default().push(pad);
        }
        let big = groups.iter().max_by_key(|(k, v)| (v.len(), std::cmp::Reverse(**k))).map(|(k, _)| *k);
        return groups.into_iter().filter(|(k, _)| Some(*k) != big).map(|(_, pads)| (board.pads[pads[0]].layers.first().copied().unwrap_or(0), Vec::new(), pads)).collect();
    };
    let mut out = Vec::new();
    // Pads of the net that no spoke or copper joins to the body and that sit on no island of their
    // own: each is a piece by itself (cells empty), to be given a via beside it.
    let on_island: BTreeSet<usize> = pads_on.values().flat_map(|s| s.iter().copied()).collect();
    for (k, &pad) in pad_ids.iter().enumerate() {
        if uf.find(k as u32) != body && !on_island.contains(&pad) {
            let layer = board.pads[pad].layers.first().copied().unwrap_or(0);
            out.push((layer, Vec::new(), vec![pad]));
        }
    }
    for (id, cells) in cells_of {
        if uf.find(id) == body || cells.is_empty() {
            continue;
        }
        let r = &rasters[cells[0].0];
        let pts: Vec<V> = cells.iter().map(|&(_, i)| r.at(i)).collect();
        let c = V(pts.iter().map(|p| p.0).sum::<f64>() / pts.len() as f64, pts.iter().map(|p| p.1).sum::<f64>() / pts.len() as f64);
        let mut pts = pts;
        pts.sort_by(|a, b| hypot(sub(*a, c)).total_cmp(&hypot(sub(*b, c))));
        let step = (pts.len() / 60).max(1);
        out.push((r.layer, pts.into_iter().step_by(step).collect(), pads_on.get(&id).map(|p| p.iter().copied().collect()).unwrap_or_default()));
    }
    out
}

pub fn splits(board: &Board, rules: &Rules, world: &World) -> Vec<Split> {
    let nets: BTreeSet<NetId> = board.zones.iter().filter(|z| z.net != NO_NET && !z.keepout_tracks && z.outline.len() >= 3).map(|z| z.net).collect();
    let mut out = Vec::new();
    for net in nets {
        if let Some(s) = split_of(board, rules, world, net) {
            out.push(s);
        }
    }
    out
}

/// The refill model of one net: its pours rasterised per layer and cut by foreign copper, the net's
/// own items joined without any fill, and how many pieces the net is in without its pours.
fn model(board: &Board, rules: &Rules, world: &World, net: NetId) -> (Vec<Raster>, Uf, Vec<bool>, usize) {
    // Items of this net, and what joins them without any fill.
    let mut items: Vec<Piece> = Vec::new();
    let mut shapes: Vec<(Option<usize>, Shape, bool)> = Vec::new();
    for (i, p) in board.pads.iter().enumerate().filter(|(_, p)| p.net == net && !p.layers.is_empty()) {
        items.push(Piece::Pad(i));
        shapes.push((None, p.shape.clone(), true));
    }
    for t in board.tracks.iter().filter(|t| t.net == net) {
        items.push(Piece::Seg { layer: t.layer, a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 });
        shapes.push((Some(t.layer), Shape::Capsule { a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 }, false));
    }
    for v in board.vias.iter().filter(|v| v.net == net) {
        items.push(Piece::Via { at: v.at.into(), r: v.size as f64 / 2.0 });
        shapes.push((None, Shape::Circle { c: v.at.into(), r: v.size as f64 / 2.0 }, false));
    }
    let is_pad: Vec<bool> = items.iter().map(|p| matches!(p, Piece::Pad(_))).collect();
    let mut base = Uf::new(items.len());
    for i in 0..items.len() {
        for j in i + 1..items.len() {
            if base.find(i as u32) != base.find(j as u32) && touches(&items[i], &items[j], board) {
                base.union(i as u32, j as u32);
            }
        }
    }
    // Without any fill the net is in this many pieces; plain open joins are counted elsewhere,
    // so compare with what the saved shapes join.
    let plain = crate::conn::net_groups(board, net, &[]).len().max(1);

    let layers: BTreeSet<usize> = board.zones.iter().filter(|z| z.net == net && !z.keepout_tracks).flat_map(|z| z.layers.iter().copied()).collect();
    let mut rasters = Vec::new();
    for layer in layers {
        let own: Vec<&Zone> = board.zones.iter().filter(|z| z.net == net && !z.keepout_tracks && z.outline.len() >= 3 && z.layers.contains(&layer)).collect();
        if own.is_empty() {
            continue;
        }
        let bb = own.iter().flat_map(|z| z.outline.iter()).fold((f64::MAX, f64::MAX, f64::MIN, f64::MIN), |m, v| (m.0.min(v.0), m.1.min(v.1), m.2.max(v.0), m.3.max(v.1)));
        let (x0, y0) = ((bb.0 / STEP).floor() * STEP, (bb.1 / STEP).floor() * STEP);
        let (w, h) = (((bb.2 - x0) / STEP).ceil() as usize + 1, ((bb.3 - y0) / STEP).ceil() as usize + 1);
        let mut r = Raster { layer, x0, y0, w, h, inside: vec![false; w * h], blocked: vec![0; w * h], by_net: BTreeMap::new(), reach: Vec::new() };
        for z in &own {
            r.fill_poly(&z.outline);
        }
        let thick = own.iter().map(|z| z.min_thickness).fold(0.0, f64::max);
        let brush = thick / 2.0 - SLACK;
        let zone_clr = own.iter().map(|z| z.clearance).fold(0.0, f64::max);
        let top = own.iter().map(|z| z.priority).max().unwrap_or(0);
        let window = (bb.0, bb.1, bb.2, bb.3);
        let mut found: Vec<(Shape, f64, NetId)> = Vec::new();
        world.layers[layer].visit(window, |o| {
            if o.net != net && matches!(o.owner, Owner::Pad(_) | Owner::Conn(_) | Owner::Fixed) {
                let local = if let Owner::Pad(i) = o.owner { world.pad_clearance[i as usize] } else { 0.0 };
                found.push((o.shape.clone(), zone_clr.max(rules.clearance_for(net, o.net) as f64).max(local) + brush, o.net));
            }
            true
        });
        world.holes.visit(window, |o| {
            if o.net != net && !matches!(o.shape, Shape::Poly { .. }) {
                found.push((o.shape.clone(), rules.hole_clearance() as f64 + brush, o.net));
            }
            true
        });
        world.edge.visit(window, |o| {
            found.push((o.shape.clone(), rules.edge as f64 + brush, NO_NET));
            true
        });
        for (s, need, n) in &found {
            r.close(s, *need, *n);
        }
        // Keep-outs, and zones of other nets that fill first. Their outlines stand in for their
        // fills: fills of higher priority sit inside them.
        for z in board.zones.iter().filter(|z| z.layers.contains(&layer) && z.outline.len() >= 3) {
            let above = z.net != net && z.net != NO_NET && !z.keepout_tracks && z.priority > top;
            if !(above || z.keepout_pour) {
                continue;
            }
            let extra = if z.keepout_pour { brush } else { zone_clr.max(rules.clearance_for(net, z.net) as f64) + brush };
            r.close(&Shape::Poly { pts: z.outline.clone(), r: 0.0 }, extra, z.net);
        }
        // What of the net's own copper reaches which cells.
        let joins = own.iter().any(|z| z.joins_pads);
        let touch = thick / 2.0 + SLACK;
        let mut reach = Vec::new();
        for (k, (only, shape, pad)) in shapes.iter().enumerate() {
            if only.map(|l| l != layer).unwrap_or(false) || (*pad && !joins) {
                continue;
            }
            if let Piece::Pad(i) = items[k] {
                if !board.pads[i].layers.contains(&layer) {
                    continue;
                }
            }
            // A pad joins a pour with thermal reliefs only through its spokes: four of them along the
            // pad's axes, each across the relief gap. A spoke stands where its far end is open copper
            // and nothing closes the way to it. KiCad wants two (min_resolved_spokes); with one the
            // pad is joined but DRC reports it starved, with none it is not joined at all. Read as
            // touching, pads that tracks had boxed in counted as joined: a motor-controller board had
            // five such ground pads open in KiCad while every join read closed here (2026-11-10).
            if let Piece::Pad(i) = items[k] {
                let pd = &board.pads[i];
                let relief = own.iter().find_map(|z| z.thermal.filter(|_| !z.thermal_tht_only || pd.drill.is_some()));
                let relief = match pd.zone_connect {
                    Some(2) => None,
                    Some(0) => { continue; }
                    Some(3) if pd.drill.is_none() => None,
                    _ => relief,
                };
                if let Some((gap, _width)) = relief {
                    let c: V = pd.center.into();
                    let mut cells: Vec<u32> = Vec::new();
                    for q in 0..4 {
                        let a = (pd.angle + 90.0 * q as f64).to_radians();
                        let u = V(a.cos(), -a.sin());
                        let half = if q % 2 == 0 { pd.size.0 } else { pd.size.1 } / 2.0;
                        let far = half + gap + thick / 2.0 + 2.0 * STEP;
                        let steps = ((far - half) / STEP).ceil() as usize;
                        let open = |d: f64| -> Option<usize> { r.index(V(c.0 + u.0 * d, c.1 + u.1 * d)).filter(|&i| r.inside[i] && r.blocked[i] == 0) };
                        if (0..=steps).all(|s| open(half + (far - half) * s as f64 / steps.max(1) as f64).is_some()) {
                            if let Some(i) = open(far) {
                                cells.push(i as u32);
                            }
                        }
                    }
                    reach.push((k, cells));
                    continue;
                }
            }
            let cells: Vec<u32> = r.cells(shape.bbox(), touch).into_iter().filter(|&i| r.inside[i] && shape.dist_pt(r.at(i)) <= touch).map(|i| i as u32).collect();
            reach.push((k, cells));
        }
        r.reach = reach;
        rasters.push(r);
    }
    (rasters, base, is_pad, plain)
}

fn split_of(board: &Board, rules: &Rules, world: &World, net: NetId) -> Option<Split> {
    let (rasters, base, is_pad, plain) = model(board, rules, world, net);
    let (now, smallest) = pieces(&rasters, &base, &is_pad, None);
    if now <= plain {
        return None;
    }
    let (layer, at) = smallest.unwrap_or((0, V(0.0, 0.0)));
    let foreign: BTreeSet<NetId> = rasters.iter().flat_map(|r| r.by_net.keys().copied()).filter(|&n| n != NO_NET).collect();
    let mut cutters = Vec::new();
    for f in foreign {
        if pieces(&rasters, &base, &is_pad, Some(f)).0 < now {
            cutters.push(f);
        }
    }
    Some(Split { net, layer, at, extra: now - plain, cutters })
}