AI Flow

//! `route --variants N` (issue #55): the levers one variant pulls, chosen in a fixed order so the
//! same board, spec and N always give the same variants. The levers are the ones the
//! kicad-place-route-loop skill lists: the signal-net order, the via size (within the spec's own
//! sizes), the pass count and a seed for a shuffled order. Variant 1 is always a plain `route`.
use serde_json::{json, Value};

use crate::{NetState, Rules};

/// The most variants one `route --variants` runs.
pub const MAX_VARIANTS: usize = 8;

/// The order the signal nets are routed in (planes and stubs always go first).
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum NetOrder {
    /// Shortest spanning length first: the router's own order and a plain `route`.
    #[default]
    Shortest,
    /// Longest first: the long nets take the open corridors before the short ones box them in.
    Longest,
    /// Most pads (clusters) first, shortest first among equals.
    Fanout,
    /// A fixed shuffle keyed by the seed and the net name.
    Seeded(u64),
}

impl NetOrder {
    pub fn describe(&self) -> String {
        match self {
            NetOrder::Shortest => "shortest first".into(),
            NetOrder::Longest => "longest first".into(),
            NetOrder::Fanout => "most pads first".into(),
            NetOrder::Seeded(s) => format!("seeded order (seed {s})"),
        }
    }
    pub fn name(&self) -> &'static str {
        match self {
            NetOrder::Shortest => "shortest-first",
            NetOrder::Longest => "longest-first",
            NetOrder::Fanout => "fanout-first",
            NetOrder::Seeded(_) => "seeded",
        }
    }
}

/// The via the signal nets take.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ViaChoice {
    /// The spec's sizes: signal nets the signal via, power and wide nets the power via.
    Spec,
    /// Signal nets take the spec's power via too (a larger hole, still a size the spec allows).
    PowerSize,
}

/// One variant's levers.
#[derive(Clone, Debug, PartialEq)]
pub struct Levers {
    pub order: NetOrder,
    pub via: ViaChoice,
    pub passes: usize,
}

impl Levers {
    /// A plain `route --passes P`.
    pub fn baseline(passes: usize) -> Levers {
        Levers { order: NetOrder::Shortest, via: ViaChoice::Spec, passes }
    }
    /// The rules this variant routes to: the spec's, with the via lever applied.
    pub fn apply(&self, rules: &Rules) -> Rules {
        let mut r = rules.clone();
        if self.via == ViaChoice::PowerSize {
            r.via_small = r.via;
            r.drill_small = r.drill;
        }
        r
    }
    pub fn to_json(&self, rules: &Rules) -> Value {
        let r = self.apply(rules);
        json!({
            "order": self.order.name(),
            "seed": match self.order { NetOrder::Seeded(s) => json!(s), _ => Value::Null },
            "via": match self.via { ViaChoice::Spec => "spec", ViaChoice::PowerSize => "power-size" },
            "signalVia": [r.via_small, r.drill_small],
            "powerVia": [r.via, r.drill],
            "passes": self.passes,
        })
    }
    /// One short line for the table.
    pub fn label(&self) -> String {
        let via = match self.via { ViaChoice::Spec => "spec vias", ViaChoice::PowerSize => "power-size vias" };
        format!("{}, {via}, {} passes", self.order.describe(), self.passes)
    }
}

/// The first `n` variants (at most MAX_VARIANTS) for a run whose plain route takes `passes`.
/// The order is fixed; a via variant is left out when the spec's signal and power vias are the
/// same size (it would route the same copper), and seeded orders fill the list up to `n`.
pub fn plan(n: usize, passes: usize, rules: &Rules) -> Vec<Levers> {
    let n = n.clamp(1, MAX_VARIANTS);
    let same_via = (rules.via - rules.via_small).abs() < 1e-9 && (rules.drill - rules.drill_small).abs() < 1e-9;
    let l = |order, via, passes| Levers { order, via, passes };
    let mut out: Vec<Levers> = [
        l(NetOrder::Shortest, ViaChoice::Spec, passes),
        l(NetOrder::Longest, ViaChoice::Spec, passes),
        l(NetOrder::Shortest, ViaChoice::PowerSize, passes),
        l(NetOrder::Fanout, ViaChoice::Spec, passes),
        l(NetOrder::Seeded(1), ViaChoice::Spec, passes),
        l(NetOrder::Seeded(2), ViaChoice::Spec, passes),
        l(NetOrder::Shortest, ViaChoice::Spec, passes + 4),
        l(NetOrder::Longest, ViaChoice::PowerSize, passes + 4),
    ]
    .into_iter()
    .filter(|v| !(same_via && v.via == ViaChoice::PowerSize))
    .collect();
    let mut seed = 3;
    while out.len() < n {
        out.push(l(NetOrder::Seeded(seed), ViaChoice::Spec, passes));
        seed += 1;
    }
    out.truncate(n);
    out
}

/// FNV-1a of the name, mixed with the seed (splitmix64): the same key on every machine.
fn key(name: &str, seed: u64) -> u64 {
    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
    for b in name.bytes() {
        h ^= b as u64;
        h = h.wrapping_mul(0x0100_0000_01b3);
    }
    let mut z = h ^ seed.wrapping_mul(0x9e37_79b9_7f4a_7c15);
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    z ^ (z >> 31)
}

/// Reorder the signal nets (already sorted shortest first) for `order`; Shortest leaves them as they are.
pub fn reorder(signal: &mut [usize], nets: &[NetState], order: NetOrder) {
    match order {
        NetOrder::Shortest => {}
        NetOrder::Longest => signal.sort_by(|a, b| nets[*b].mst_len.partial_cmp(&nets[*a].mst_len).unwrap_or(std::cmp::Ordering::Equal)),
        NetOrder::Fanout => signal.sort_by_key(|&n| std::cmp::Reverse(nets[n].clusters.len())),
        NetOrder::Seeded(s) => signal.sort_by_key(|&n| (key(&nets[n].name, s), nets[n].name.clone())),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn plan_is_fixed_capped_and_starts_with_a_plain_route() {
        let r = Rules::default();
        let a = plan(3, 5, &r);
        assert_eq!(a, plan(3, 5, &r));
        assert_eq!(a[0], Levers::baseline(5));
        assert_eq!(a[1].order, NetOrder::Longest);
        assert_eq!(a[2].via, ViaChoice::PowerSize);
        assert_eq!(plan(50, 5, &r).len(), MAX_VARIANTS);
        assert_eq!(plan(0, 5, &r).len(), 1);
    }

    #[test]
    fn same_vias_drop_the_via_variant_and_seeds_fill_in() {
        let mut r = Rules::default();
        r.via_small = r.via;
        r.drill_small = r.drill;
        let a = plan(8, 5, &r);
        assert_eq!(a.len(), 8);
        assert!(a.iter().all(|v| v.via == ViaChoice::Spec));
        assert_eq!((a[6].order, a[7].order), (NetOrder::Seeded(3), NetOrder::Seeded(4)));
    }

    #[test]
    fn power_size_via_applies_to_signal_nets_only_in_the_rules() {
        let r = Rules::default();
        let v = Levers { order: NetOrder::Shortest, via: ViaChoice::PowerSize, passes: 5 }.apply(&r);
        assert_eq!((v.via_small, v.drill_small), (r.via, r.drill));
        assert_eq!(Levers::baseline(5).apply(&r).via_small, r.via_small);
    }

    #[test]
    fn seeded_keys_are_stable_and_differ_by_seed() {
        assert_eq!(key("GND", 1), key("GND", 1));
        assert_ne!(key("GND", 1), key("GND", 2));
        let names = ["A", "B", "C", "D", "E", "F"];
        let o1: Vec<u64> = names.iter().map(|n| key(n, 1)).collect();
        let o2: Vec<u64> = names.iter().map(|n| key(n, 2)).collect();
        let rank = |o: &Vec<u64>| { let mut i: Vec<usize> = (0..o.len()).collect(); i.sort_by_key(|&k| o[k]); i };
        assert_ne!(rank(&o1), rank(&o2));
    }

    #[test]
    fn the_order_lever_changes_which_net_goes_first_and_default_is_unchanged() {
        let pads = [("J1", "A", 2.0, 2.0, true), ("J2", "A", 5.0, 2.0, true), ("J3", "B", 2.0, 8.0, true), ("J4", "B", 18.0, 8.0, true)];
        let first = |order: NetOrder| {
            let b = crate::board_copper::tests::board(&pads, "");
            let mut r = crate::Router::new(b, Rules::default(), false);
            r.order = order;
            let (_, _, failed) = crate::drive::route_board(&mut r, 2, 8, 400);
            assert_eq!(failed, 0);
            r.nets.iter().find(|n| n.routed_order == Some(1)).map(|n| n.name.clone()).unwrap()
        };
        assert_eq!(first(NetOrder::default()), "A");
        assert_eq!(first(NetOrder::Shortest), "A");
        assert_eq!(first(NetOrder::Longest), "B");
    }
}