KiCad - the KiCad Bridge

//! Read-only electrical and graphical model of ONE schematic sheet, and its connectivity.
//!
//! `extract` turns a parsed `.kicad_sch` (the lossless `schematic::Schematic`) into flat
//! lists: wire segments, junctions, no-connect flags, labels, symbol pins in sheet
//! coordinates (with their electrical type from `lib_symbols`), sheet symbols with their
//! pins, symbol body extents and visible text. `Connectivity::build` then groups them into
//! nets with the rules eeschema's connection graph uses:
//!
//! * wire ends join other wire ends, and a wire end landing on another wire's interior
//!   joins it (a T);
//! * labels and junction dots join a wire anywhere along it;
//! * a symbol pin or a sheet pin joins a wire at the wire's END, or mid-wire only where a
//!   junction dot sits; pins stacked on one point join each other;
//! * same-named local labels on one sheet are one net, as are same-named global labels and
//!   power symbols (power symbols name their net by their Value), and hidden power-input
//!   pins of ordinary symbols join the global net of their pin name.
//!
//! Coordinates are sheet millimetres, origin top-left, y down. Two points are the same
//! point when they agree to 1 micrometre (eeschema's internal unit is 100 nm).

use std::collections::{BTreeMap, BTreeSet, HashMap};

use serde::Serialize;

use crate::schematic::{is_symbol_instance, symbol_property, Node, Schematic};

pub type Pt = (f64, f64);

/// Same-point tolerance in millimetres.
pub const EPS: f64 = 0.001;

pub fn same(a: Pt, b: Pt) -> bool {
    (a.0 - b.0).abs() <= EPS && (a.1 - b.1).abs() <= EPS
}

pub fn dist(a: Pt, b: Pt) -> f64 {
    ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt()
}

/// Round to the 0.1 micrometre grid and drop negative zero, for stable output.
pub fn r4(v: f64) -> f64 {
    (v * 1e4).round() / 1e4 + 0.0
}

/// Is `p` on the segment a-b (endpoints included), within EPS.
pub fn on_segment(p: Pt, a: Pt, b: Pt) -> bool {
    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
    let len2 = dx * dx + dy * dy;
    if len2 == 0.0 {
        return same(p, a);
    }
    let t = ((p.0 - a.0) * dx + (p.1 - a.1) * dy) / len2;
    if t < -1e-9 || t > 1.0 + 1e-9 {
        return same(p, a) || same(p, b);
    }
    let q = (a.0 + t * dx, a.1 + t * dy);
    dist(p, q) <= EPS
}

/// On the segment but not at either end.
pub fn on_interior(p: Pt, a: Pt, b: Pt) -> bool {
    on_segment(p, a, b) && !same(p, a) && !same(p, b)
}

/// An axis-aligned box: (min x, min y, max x, max y).
pub type BBox = (f64, f64, f64, f64);

pub fn bbox_union(a: Option<BBox>, p: Pt) -> Option<BBox> {
    Some(match a {
        None => (p.0, p.1, p.0, p.1),
        Some((x0, y0, x1, y1)) => (x0.min(p.0), y0.min(p.1), x1.max(p.0), y1.max(p.1)),
    })
}

/// Overlap area of two boxes after shrinking each by `inset` (so boxes that only touch,
/// like two symbols wired pin to pin, do not count).
pub fn overlap(a: BBox, b: BBox, inset: f64) -> Option<BBox> {
    let a = (a.0 + inset, a.1 + inset, a.2 - inset, a.3 - inset);
    let b = (b.0 + inset, b.1 + inset, b.2 - inset, b.3 - inset);
    let (x0, y0, x1, y1) = (a.0.max(b.0), a.1.max(b.1), a.2.min(b.2), a.3.min(b.3));
    if x1 > x0 && y1 > y0 {
        Some((x0, y0, x1, y1))
    } else {
        None
    }
}

#[derive(Clone, Debug, Serialize)]
pub struct Wire {
    pub uuid: String,
    pub a: Pt,
    pub b: Pt,
}

#[derive(Clone, Debug, Serialize)]
pub struct Marker {
    pub uuid: String,
    pub at: Pt,
}

#[derive(Clone, Debug, Serialize)]
pub struct Label {
    pub uuid: String,
    pub text: String,
    /// local | global | hierarchical
    pub kind: String,
    pub at: Pt,
    pub rotation: f64,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub shape: Option<String>,
    #[serde(skip)]
    pub size: f64,
}

#[derive(Clone, Debug, Serialize)]
pub struct Pin {
    pub reference: String,
    #[serde(rename = "symbolUuid")]
    pub symbol_uuid: String,
    pub number: String,
    pub name: String,
    /// eeschema's pin electrical type: input, output, bidirectional, tri_state, passive,
    /// free, unspecified, power_in, power_out, open_collector, open_emitter, no_connect.
    pub electrical: String,
    pub at: Pt,
    #[serde(skip_serializing_if = "std::ops::Not::not")]
    pub hidden: bool,
    /// The pin of a power symbol (#PWR, a GND or +3V3 flag): it names a net, it is not a part.
    #[serde(rename = "powerSymbol", skip_serializing_if = "std::ops::Not::not")]
    pub power_symbol: bool,
    /// For a power symbol pin: the net it names (the symbol's Value).
    #[serde(skip)]
    pub power_net: Option<String>,
}

#[derive(Clone, Debug, Serialize)]
pub struct SheetPin {
    pub uuid: String,
    pub name: String,
    pub shape: String,
    pub at: Pt,
    pub rotation: f64,
    #[serde(rename = "sheetUuid")]
    pub sheet_uuid: String,
    #[serde(rename = "sheetName")]
    pub sheet_name: String,
}

#[derive(Clone, Debug, Serialize)]
pub struct SheetRef {
    pub uuid: String,
    pub name: String,
    pub file: String,
    pub at: Pt,
    pub size: Pt,
    pub pins: Vec<SheetPin>,
    /// (instance path of the file holding this sheet, page) pairs from its instances block.
    #[serde(skip)]
    pub pages: Vec<(String, String)>,
}

#[derive(Clone, Debug, Serialize)]
pub struct SymbolMeta {
    pub uuid: String,
    pub reference: String,
    #[serde(rename = "libId")]
    pub lib_id: String,
    pub value: String,
    pub footprint: String,
    pub description: String,
    pub unit: u32,
    pub at: Pt,
    #[serde(rename = "isPower")]
    pub is_power: bool,
    #[serde(rename = "inBom")]
    pub in_bom: bool,
    #[serde(rename = "onBoard")]
    pub on_board: bool,
    pub dnp: bool,
    /// Body and pin extents in sheet coordinates (None when the library symbol is missing).
    #[serde(skip)]
    pub bbox: Option<BBox>,
}

/// Visible text on the sheet: a free (text ..) item or a visible symbol field.
#[derive(Clone, Debug, Serialize)]
pub struct TextItem {
    pub uuid: String,
    pub text: String,
    pub at: Pt,
    /// text | field
    pub kind: String,
    /// For a field: the reference of its symbol.
    #[serde(skip_serializing_if = "Option::is_none")]
    pub owner: Option<String>,
    #[serde(skip)]
    pub bbox: BBox,
}

#[derive(Clone, Debug, Default)]
pub struct SheetModel {
    pub wires: Vec<Wire>,
    pub buses: Vec<Wire>,
    pub junctions: Vec<Marker>,
    pub no_connects: Vec<Marker>,
    pub labels: Vec<Label>,
    pub pins: Vec<Pin>,
    pub sheets: Vec<SheetRef>,
    pub symbols: Vec<SymbolMeta>,
    pub texts: Vec<TextItem>,
    /// Symbols whose library symbol is not in lib_symbols (their pins are unknown).
    pub missing_lib: Vec<String>,
}

impl SheetModel {
    pub fn sheet_pins(&self) -> impl Iterator<Item = &SheetPin> {
        self.sheets.iter().flat_map(|s| s.pins.iter())
    }
}

fn xy_of(n: &Node) -> Option<Pt> {
    Some((n.num(0)?, n.num(1)?))
}

fn at_of(n: &Node) -> (Pt, f64) {
    match n.child("at") {
        Some(a) => ((a.num(0).unwrap_or(0.0), a.num(1).unwrap_or(0.0)), a.num(2).unwrap_or(0.0)),
        None => ((0.0, 0.0), 0.0),
    }
}

fn is_hidden(n: &Node) -> bool {
    if let Some(h) = n.child("hide") {
        return h.arg(0).map_or(true, |v| v == "yes");
    }
    if n.children().iter().any(|c| c.raw() == Some("hide")) {
        return true;
    }
    n.child("effects").map_or(false, |e| {
        e.child("hide").map_or(false, |h| h.arg(0).map_or(true, |v| v == "yes")) || e.children().iter().any(|c| c.raw() == Some("hide"))
    })
}

fn font_size(n: &Node) -> f64 {
    n.child("effects").and_then(|e| e.child("font")).and_then(|f| f.child("size")).and_then(|s| s.num(0)).unwrap_or(1.27)
}

fn yes(n: &Node, name: &str, default: bool) -> bool {
    n.child(name).and_then(|c| c.arg(0)).map(|v| v == "yes").unwrap_or(default)
}

/// A placed symbol's placement: anchor, rotation and mirror, mapping library coordinates
/// (y up) to sheet coordinates (y down). Rotation turns counterclockwise as seen, then the
/// mirror flips: the same order `schematic::pin_points` uses.
#[derive(Clone, Copy, Debug)]
pub struct Placement {
    pub at: Pt,
    pub sin: f64,
    pub cos: f64,
    pub mirror: Option<char>,
}

impl Placement {
    pub fn of(inst: &Node) -> Placement {
        let (at, rot) = at_of(inst);
        let (sin, cos) = rot.to_radians().sin_cos();
        let mirror = inst.child_value("mirror").and_then(|m| m.chars().next());
        Placement { at, sin, cos, mirror }
    }
    pub fn apply(&self, p: Pt) -> Pt {
        let (mut qx, mut qy) = (p.0 * self.cos - p.1 * self.sin, p.0 * self.sin + p.1 * self.cos);
        match self.mirror {
            Some('x') => qy = -qy,
            Some('y') => qx = -qx,
            _ => {}
        }
        (r4(self.at.0 + qx), r4(self.at.1 - qy))
    }
}

/// `R_1_1` with base `R` -> (unit 1, body style 1).
fn sub_unit_style(name: &str, base: &str) -> Option<(u32, u32)> {
    let rest = name.strip_prefix(base)?.strip_prefix('_')?;
    let (u, s) = rest.split_once('_')?;
    Some((u.parse().ok()?, s.parse().ok()?))
}

/// The sub-symbols of a library symbol that a placed unit draws.
fn unit_subs<'a>(lib: &'a Node, lib_key: &str, unit: u32, style: u32) -> Vec<&'a Node> {
    let base = lib.arg(0).unwrap_or_else(|| lib_key.to_string());
    let base = base.rsplit(':').next().unwrap_or(&base).to_string();
    lib.children()
        .iter()
        .filter(|n| n.head() == Some("symbol"))
        .filter(|n| {
            let Some(name) = n.arg(0) else { return false };
            match sub_unit_style(&name, &base) {
                Some((u, s)) => (u == 0 || u == unit) && (s == 0 || s == style),
                None => false,
            }
        })
        .collect()
}

/// The reference a symbol carries under one sheet instance path, else its Reference field.
pub fn instance_reference(inst: &Node, path: Option<&str>) -> String {
    if let Some(path) = path {
        if let Some(insts) = inst.child("instances") {
            for proj in insts.children().iter().filter(|n| n.head() == Some("project")) {
                for p in proj.children().iter().filter(|n| n.head() == Some("path")) {
                    if p.arg(0).as_deref() == Some(path) {
                        if let Some(r) = p.child_value("reference") {
                            return r;
                        }
                    }
                }
            }
        }
    }
    symbol_property(inst, "Reference").unwrap_or_default()
}

/// Rough extent of a text run: KiCad's stroke font averages about 0.9 of the font height per
/// character including spacing; height is the font height. `rot` 0 runs right, 90 up, 180
/// left, 270 down from the anchor; `centered` puts the anchor mid-run (free text, fields).
pub fn text_bbox(at: Pt, text: &str, size: f64, rot: f64, centered: bool, pad: f64) -> BBox {
    let len = text.chars().count().max(1) as f64 * size * 0.9 + pad;
    let h = size;
    let r = ((rot % 360.0) + 360.0) % 360.0;
    let vertical = (r - 90.0).abs() < 1.0 || (r - 270.0).abs() < 1.0;
    let (w, hh) = if vertical { (h, len) } else { (len, h) };
    if centered {
        return (at.0 - w / 2.0, at.1 - hh / 2.0, at.0 + w / 2.0, at.1 + hh / 2.0);
    }
    if (r - 0.0).abs() < 1.0 {
        (at.0, at.1 - h, at.0 + len, at.1)
    } else if (r - 180.0).abs() < 1.0 {
        (at.0 - len, at.1 - h, at.0, at.1)
    } else if (r - 90.0).abs() < 1.0 {
        (at.0 - h, at.1 - len, at.0, at.1)
    } else {
        (at.0 - h, at.1, at.0, at.1 + len)
    }
}

/// Build the model of one sheet. `path` is the sheet instance path (`/<root uuid>/...`) used
/// to pick each symbol's reference for that instance; None takes the Reference field.
pub fn extract(sch: &Schematic, path: Option<&str>) -> SheetModel {
    let mut m = SheetModel::default();
    let lib_symbols = sch.doc.root.child("lib_symbols");
    for n in sch.doc.root.children() {
        match n.head() {
            Some("wire") | Some("bus") => {
                let pts: Vec<Pt> = n.child("pts").map(|p| p.children().iter().filter(|c| c.head() == Some("xy")).filter_map(xy_of).collect()).unwrap_or_default();
                let uuid = n.child_value("uuid").unwrap_or_default();
                for seg in pts.windows(2) {
                    let w = Wire { uuid: uuid.clone(), a: seg[0], b: seg[1] };
                    if n.head() == Some("wire") {
                        m.wires.push(w);
                    } else {
                        m.buses.push(w);
                    }
                }
            }
            Some("junction") => m.junctions.push(Marker { uuid: n.child_value("uuid").unwrap_or_default(), at: at_of(n).0 }),
            Some("no_connect") => m.no_connects.push(Marker { uuid: n.child_value("uuid").unwrap_or_default(), at: at_of(n).0 }),
            Some(h @ ("label" | "global_label" | "hierarchical_label")) => {
                let (at, rotation) = at_of(n);
                let kind = match h {
                    "label" => "local",
                    "global_label" => "global",
                    _ => "hierarchical",
                };
                m.labels.push(Label {
                    uuid: n.child_value("uuid").unwrap_or_default(),
                    text: unescape_name(&n.arg(0).unwrap_or_default()),
                    kind: kind.into(),
                    at,
                    rotation,
                    shape: n.child_value("shape"),
                    size: font_size(n),
                });
            }
            Some("text") => {
                let (at, rot) = at_of(n);
                let text = n.arg(0).unwrap_or_default();
                let size = font_size(n);
                let lines: Vec<&str> = text.split('\n').collect();
                let longest = lines.iter().max_by_key(|l| l.chars().count()).copied().unwrap_or("");
                let mut bb = text_bbox(at, longest, size, rot, false, 0.0);
                bb.3 += (lines.len().saturating_sub(1)) as f64 * size * 1.6;
                m.texts.push(TextItem { uuid: n.child_value("uuid").unwrap_or_default(), text, at, kind: "text".into(), owner: None, bbox: bb });
            }
            Some("sheet") => m.sheets.push(sheet_ref(n)),
            Some("symbol") if is_symbol_instance(n) => symbol_items(&mut m, n, lib_symbols, path),
            _ => {}
        }
    }
    m
}

/// The standard's sheetDrawing entry for one sheet (#29: schematic_review's drawing checks): wires, buses, junctions,
/// no-connects, labels (power symbols as labels of kind power, a sheet symbol's pins as hierarchical labels), the parts'
/// pins and their boxes, in mm, origin top-left, y down.
pub fn drawing(m: &SheetModel, sheet: &str) -> serde_json::Value {
    use serde_json::json;
    let p = |q: Pt| json!([r4(q.0), r4(q.1)]);
    let seg = |w: &Wire| json!({"a": p(w.a), "b": p(w.b)});
    let mut labels: Vec<serde_json::Value> = m.labels.iter().map(|l| json!({"text": l.text, "kind": l.kind, "at": p(l.at)})).collect();
    labels.extend(m.pins.iter().filter(|q| q.power_symbol && q.power_net.is_some()).map(|q| json!({"text": q.power_net.clone().unwrap_or_default(), "kind": "power", "at": p(q.at)})));
    labels.extend(m.sheets.iter().flat_map(|s| s.pins.iter()).map(|q| json!({"text": q.name, "kind": "hierarchical", "at": p(q.at)})));
    json!({
        "sheet": sheet, "units": "mm", "frame": "sheet: origin top-left, y down",
        "wires": m.wires.iter().map(seg).collect::<Vec<_>>(),
        "buses": m.buses.iter().map(seg).collect::<Vec<_>>(),
        "junctions": m.junctions.iter().map(|j| p(j.at)).collect::<Vec<_>>(),
        "noConnects": m.no_connects.iter().map(|j| p(j.at)).collect::<Vec<_>>(),
        "labels": labels,
        // a PWR_FLAG names no net: its pin is a connection point like any part's
        "pins": m.pins.iter().filter(|q| (!q.power_symbol || q.power_net.is_none()) && !q.hidden).map(|q| json!({"ref": q.reference, "number": q.number, "at": p(q.at)})).collect::<Vec<_>>(),
        "symbols": m.symbols.iter().filter(|s| !s.is_power).filter_map(|s| s.bbox.map(|b| json!({"ref": s.reference, "box": [r4(b.0), r4(b.1), r4(b.2), r4(b.3)]}))).collect::<Vec<_>>(),
    })
}

/// A net name as KiCad compares it: its file escapes ({slash}, {backslash}, ...) read back, so "VPP{slash}MCLR" and
/// "VPP/MCLR" are one label name, as they are one net in KiCad's netlist.
pub fn unescape_name(s: &str) -> String {
    if !s.contains('{') {
        return s.to_string();
    }
    [("{slash}", "/"), ("{backslash}", "\\"), ("{colon}", ":"), ("{dblquote}", "\""), ("{lt}", "<"), ("{gt}", ">"), ("{space}", " "), ("{tab}", "\t"), ("{return}", "\n"), ("{brace}", "{")]
        .iter().fold(s.to_string(), |t, (k, v)| t.replace(k, v))
}

pub fn sheet_ref(n: &Node) -> SheetRef {
    let (at, _) = at_of(n);
    let size = n.child("size").and_then(xy_of).unwrap_or((0.0, 0.0));
    let uuid = n.child_value("uuid").unwrap_or_default();
    let name = symbol_property(n, "Sheetname").or_else(|| symbol_property(n, "Sheet name")).unwrap_or_default();
    let file = symbol_property(n, "Sheetfile").or_else(|| symbol_property(n, "Sheet file")).unwrap_or_default();
    let pins = n
        .children()
        .iter()
        .filter(|c| c.head() == Some("pin"))
        .map(|p| {
            let (pat, rot) = at_of(p);
            SheetPin {
                uuid: p.child_value("uuid").unwrap_or_default(),
                name: p.arg(0).unwrap_or_default(),
                shape: p.arg(1).unwrap_or_else(|| "input".into()),
                at: pat,
                rotation: rot,
                sheet_uuid: uuid.clone(),
                sheet_name: name.clone(),
            }
        })
        .collect();
    let mut pages = Vec::new();
    if let Some(insts) = n.child("instances") {
        for proj in insts.children().iter().filter(|c| c.head() == Some("project")) {
            for p in proj.children().iter().filter(|c| c.head() == Some("path")) {
                pages.push((p.arg(0).unwrap_or_default(), p.child_value("page").unwrap_or_default()));
            }
        }
    }
    SheetRef { uuid, name, file, at, size, pins, pages }
}

fn symbol_items(m: &mut SheetModel, inst: &Node, lib_symbols: Option<&Node>, path: Option<&str>) {
    let reference = instance_reference(inst, path);
    let lib_key = inst.child_value("lib_name").or_else(|| inst.child_value("lib_id")).unwrap_or_default();
    let lib = lib_symbols.and_then(|ls| ls.children().iter().find(|n| n.head() == Some("symbol") && n.arg(0).as_deref() == Some(lib_key.as_str())));
    let unit = inst.child("unit").and_then(|u| u.num(0)).unwrap_or(1.0) as u32;
    let style = inst.child("body_style").or_else(|| inst.child("convert")).and_then(|u| u.num(0)).unwrap_or(1.0) as u32;
    let uuid = inst.child_value("uuid").unwrap_or_default();
    let value = symbol_property(inst, "Value").unwrap_or_default();
    let is_power = lib.map_or(false, |l| l.child("power").is_some()) || reference.starts_with("#PWR") || reference.starts_with("#FLG");
    let xf = Placement::of(inst);
    let mut bbox: Option<BBox> = None;
    if let Some(lib) = lib {
        for sub in unit_subs(lib, &lib_key, unit, style) {
            for g in sub.children() {
                match g.head() {
                    Some("rectangle") => {
                        for k in ["start", "end"] {
                            if let Some(p) = g.child(k).and_then(xy_of) {
                                bbox = bbox_union(bbox, xf.apply(p));
                            }
                        }
                    }
                    Some("polyline") | Some("bezier") => {
                        if let Some(pts) = g.child("pts") {
                            for p in pts.children().iter().filter(|c| c.head() == Some("xy")).filter_map(xy_of) {
                                bbox = bbox_union(bbox, xf.apply(p));
                            }
                        }
                    }
                    Some("circle") => {
                        if let (Some(c), Some(r)) = (g.child("center").and_then(xy_of), g.child("radius").and_then(|r| r.num(0))) {
                            for p in [(c.0 - r, c.1 - r), (c.0 + r, c.1 + r), (c.0 - r, c.1 + r), (c.0 + r, c.1 - r)] {
                                bbox = bbox_union(bbox, xf.apply(p));
                            }
                        }
                    }
                    Some("arc") => {
                        for k in ["start", "mid", "end"] {
                            if let Some(p) = g.child(k).and_then(xy_of) {
                                bbox = bbox_union(bbox, xf.apply(p));
                            }
                        }
                    }
                    Some("pin") => {
                        let (pat, ang) = at_of(g);
                        let len = g.child("length").and_then(|l| l.num(0)).unwrap_or(0.0);
                        let (s, c) = ang.to_radians().sin_cos();
                        let end = (pat.0 + len * c, pat.1 + len * s);
                        let at = xf.apply(pat);
                        bbox = bbox_union(bbox, at);
                        bbox = bbox_union(bbox, xf.apply(end));
                        let number = g.child_value("number").unwrap_or_default();
                        if m.pins.iter().any(|p| p.symbol_uuid == uuid && p.number == number && same(p.at, at)) {
                            continue;
                        }
                        let electrical = g.arg(0).unwrap_or_else(|| "unspecified".into());
                        // a power symbol names its net through its power_in pin (GND, +3V3); PWR_FLAG's pin is
                        // power_out and names nothing, so flags on different nets are not one net
                        let names_net = is_power && electrical == "power_in";
                        m.pins.push(Pin {
                            reference: reference.clone(),
                            symbol_uuid: uuid.clone(),
                            number,
                            name: g.child_value("name").unwrap_or_default(),
                            electrical,
                            at,
                            hidden: is_hidden(g),
                            power_symbol: is_power,
                            power_net: if names_net { Some(value.clone()) } else { None },
                        });
                    }
                    _ => {}
                }
            }
        }
    } else {
        m.missing_lib.push(reference.clone());
    }
    // Visible fields as text items (overlap checks).
    for prop in inst.children().iter().filter(|c| c.head() == Some("property")) {
        if is_hidden(prop) {
            continue;
        }
        let text = prop.arg(1).unwrap_or_default();
        if text.is_empty() || text == "~" {
            continue;
        }
        let (at, rot) = at_of(prop);
        let size = font_size(prop);
        let justify = prop.child("effects").and_then(|e| e.child("justify"));
        let left = justify.map_or(false, |j| j.children().iter().any(|c| c.raw() == Some("left")));
        let right = justify.map_or(false, |j| j.children().iter().any(|c| c.raw() == Some("right")));
        let bb = if left {
            text_bbox(at, &text, size, rot, false, 0.0)
        } else if right {
            text_bbox(at, &text, size, rot + 180.0, false, 0.0)
        } else {
            text_bbox(at, &text, size, rot, true, 0.0)
        };
        let bb = if left || right { (bb.0, bb.1 + size / 2.0, bb.2, bb.3 + size / 2.0) } else { bb };
        m.texts.push(TextItem { uuid: uuid.clone(), text, at, kind: "field".into(), owner: Some(reference.clone()), bbox: bb });
    }
    m.symbols.push(SymbolMeta {
        uuid,
        reference,
        lib_id: inst.child_value("lib_id").unwrap_or_default(),
        value,
        footprint: symbol_property(inst, "Footprint").unwrap_or_default(),
        description: symbol_property(inst, "Description").unwrap_or_default(),
        unit,
        at: xf.at,
        is_power,
        in_bom: yes(inst, "in_bom", true),
        on_board: yes(inst, "on_board", true),
        dnp: yes(inst, "dnp", false),
        bbox,
    });
}

// ---------------------------------------------------------------------------
// Connectivity
// ---------------------------------------------------------------------------

/// What a connectivity node stands for: an index into the model's list of that kind.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Item {
    Wire(usize),
    Pin(usize),
    Label(usize),
    SheetPin(usize),
    Junction(usize),
    NoConnect(usize),
}

pub struct Dsu {
    parent: Vec<usize>,
}

impl Dsu {
    pub fn new(n: usize) -> Dsu {
        Dsu { parent: (0..n).collect() }
    }
    pub fn find(&mut self, x: usize) -> usize {
        let mut r = x;
        while self.parent[r] != r {
            r = self.parent[r];
        }
        let mut c = x;
        while self.parent[c] != r {
            let n = self.parent[c];
            self.parent[c] = r;
            c = n;
        }
        r
    }
    pub fn union(&mut self, a: usize, b: usize) {
        let (ra, rb) = (self.find(a), self.find(b));
        if ra != rb {
            self.parent[ra.max(rb)] = ra.min(rb);
        }
    }
    pub fn grow(&mut self) -> usize {
        let n = self.parent.len();
        self.parent.push(n);
        n
    }
}

/// One net on one sheet.
#[derive(Clone, Debug, Default)]
pub struct Group {
    pub items: Vec<Item>,
    /// (kind, text) of every name on the net: kind is local, global, hierarchical, power,
    /// or sheet_pin. Sorted, de-duplicated.
    pub names: Vec<(String, String)>,
}

impl Group {
    pub fn pins<'a>(&'a self, m: &'a SheetModel) -> impl Iterator<Item = &'a Pin> + 'a {
        self.items.iter().filter_map(move |i| if let Item::Pin(k) = i { Some(&m.pins[*k]) } else { None })
    }
    /// Pins of real parts (not power symbols).
    pub fn part_pins<'a>(&'a self, m: &'a SheetModel) -> impl Iterator<Item = &'a Pin> + 'a {
        self.pins(m).filter(|p| !p.power_symbol)
    }
    pub fn has(&self, f: impl Fn(&Item) -> bool) -> bool {
        self.items.iter().any(f)
    }
    /// Can this net continue on another sheet (global label, hierarchical label, sheet pin,
    /// power symbol)?
    pub fn leaves_sheet(&self) -> bool {
        self.names.iter().any(|(k, _)| k != "local")
    }
    /// The name eeschema would pick: power or global first, then hierarchical, then local;
    /// alphabetical within a kind. None for an unnamed net.
    pub fn best_name(&self) -> Option<String> {
        for want in ["power", "global", "hierarchical", "sheet_pin", "local"] {
            if let Some((_, t)) = self.names.iter().find(|(k, _)| k == want) {
                return Some(t.clone());
            }
        }
        None
    }
}

pub struct Connectivity {
    pub groups: Vec<Group>,
    /// Item to group index.
    pub of: HashMap<Item, usize>,
}

impl Connectivity {
    pub fn build(m: &SheetModel) -> Connectivity {
        let mut items: Vec<Item> = Vec::new();
        items.extend((0..m.wires.len()).map(Item::Wire));
        items.extend((0..m.pins.len()).map(Item::Pin));
        items.extend((0..m.labels.len()).map(Item::Label));
        let sheet_pins: Vec<&SheetPin> = m.sheet_pins().collect();
        items.extend((0..sheet_pins.len()).map(Item::SheetPin));
        items.extend((0..m.junctions.len()).map(Item::Junction));
        items.extend((0..m.no_connects.len()).map(Item::NoConnect));
        let idx: HashMap<Item, usize> = items.iter().enumerate().map(|(i, it)| (*it, i)).collect();
        let mut d = Dsu::new(items.len());
        let w = |i: usize| idx[&Item::Wire(i)];

        // wire to wire: shared ends, and an end on another wire's interior (a T)
        for i in 0..m.wires.len() {
            for j in (i + 1)..m.wires.len() {
                let (a, b) = (&m.wires[i], &m.wires[j]);
                let joined = same(a.a, b.a) || same(a.a, b.b) || same(a.b, b.a) || same(a.b, b.b) || on_interior(a.a, b.a, b.b) || on_interior(a.b, b.a, b.b) || on_interior(b.a, a.a, a.b) || on_interior(b.b, a.a, a.b);
                if joined {
                    d.union(w(i), w(j));
                }
            }
        }
        let junction_at = |p: Pt| m.junctions.iter().any(|j| same(j.at, p));
        // a point item joins wires: `anywhere` for labels and junctions, ends (or a dot) for pins
        let attach = |d: &mut Dsu, node: usize, p: Pt, anywhere: bool| {
            for (i, wire) in m.wires.iter().enumerate() {
                let at_end = same(p, wire.a) || same(p, wire.b);
                if at_end || ((anywhere || junction_at(p)) && on_segment(p, wire.a, wire.b)) {
                    d.union(node, w(i));
                }
            }
        };
        for (i, l) in m.labels.iter().enumerate() {
            attach(&mut d, idx[&Item::Label(i)], l.at, true);
        }
        for (i, j) in m.junctions.iter().enumerate() {
            attach(&mut d, idx[&Item::Junction(i)], j.at, true);
        }
        for (i, p) in m.pins.iter().enumerate() {
            attach(&mut d, idx[&Item::Pin(i)], p.at, false);
        }
        for (i, sp) in sheet_pins.iter().enumerate() {
            attach(&mut d, idx[&Item::SheetPin(i)], sp.at, false);
        }
        for (i, nc) in m.no_connects.iter().enumerate() {
            attach(&mut d, idx[&Item::NoConnect(i)], nc.at, false);
        }
        // coincident points: pins, labels, sheet pins and flags sitting on one another
        let mut points: Vec<(Pt, usize)> = Vec::new();
        points.extend(m.pins.iter().enumerate().map(|(i, p)| (p.at, idx[&Item::Pin(i)])));
        points.extend(m.labels.iter().enumerate().map(|(i, l)| (l.at, idx[&Item::Label(i)])));
        points.extend(sheet_pins.iter().enumerate().map(|(i, s)| (s.at, idx[&Item::SheetPin(i)])));
        points.extend(m.no_connects.iter().enumerate().map(|(i, s)| (s.at, idx[&Item::NoConnect(i)])));
        points.extend(m.junctions.iter().enumerate().map(|(i, s)| (s.at, idx[&Item::Junction(i)])));
        let mut by_key: BTreeMap<(i64, i64), Vec<usize>> = BTreeMap::new();
        for (p, n) in &points {
            by_key.entry(((p.0 * 1e3).round() as i64, (p.1 * 1e3).round() as i64)).or_default().push(*n);
        }
        for v in by_key.values() {
            for k in 1..v.len() {
                d.union(v[0], v[k]);
            }
        }
        // names: same-named local labels on the sheet; globals, hierarchical labels and power
        // symbols by name; hidden power-input pins of parts join the global net of their name
        let mut by_name: BTreeMap<(String, String), usize> = BTreeMap::new();
        let mut name_join = |d: &mut Dsu, scope: &str, text: &str, node: usize| {
            let k = (scope.to_string(), text.to_string());
            match by_name.get(&k) {
                Some(&first) => d.union(first, node),
                None => {
                    by_name.insert(k, node);
                }
            }
        };
        for (i, l) in m.labels.iter().enumerate() {
            let scope = if l.kind == "global" { "global" } else { l.kind.as_str() };
            name_join(&mut d, scope, &l.text, idx[&Item::Label(i)]);
        }
        for (i, p) in m.pins.iter().enumerate() {
            if let Some(n) = &p.power_net {
                name_join(&mut d, "global", n, idx[&Item::Pin(i)]);
            } else if p.hidden && p.electrical == "power_in" && !p.name.is_empty() {
                name_join(&mut d, "global", &p.name, idx[&Item::Pin(i)]);
            }
        }

        let mut root_to_group: HashMap<usize, usize> = HashMap::new();
        let mut groups: Vec<Group> = Vec::new();
        let mut of = HashMap::new();
        for (n, it) in items.iter().enumerate() {
            let r = d.find(n);
            let g = *root_to_group.entry(r).or_insert_with(|| {
                groups.push(Group::default());
                groups.len() - 1
            });
            groups[g].items.push(*it);
            of.insert(*it, g);
        }
        for g in groups.iter_mut() {
            let mut names: BTreeSet<(String, String)> = BTreeSet::new();
            for it in &g.items {
                match it {
                    Item::Label(i) => {
                        names.insert((m.labels[*i].kind.clone(), m.labels[*i].text.clone()));
                    }
                    Item::Pin(i) => {
                        if let Some(n) = &m.pins[*i].power_net {
                            names.insert(("power".into(), n.clone()));
                        } else if m.pins[*i].hidden && m.pins[*i].electrical == "power_in" && !m.pins[*i].name.is_empty() {
                            names.insert(("power".into(), m.pins[*i].name.clone()));
                        }
                    }
                    Item::SheetPin(i) => {
                        names.insert(("sheet_pin".into(), sheet_pins[*i].name.clone()));
                    }
                    _ => {}
                }
            }
            g.names = names.into_iter().collect();
        }
        Connectivity { groups, of }
    }

    /// The net name: the best label or power name, else `Net-(<ref>-Pad<n>)` from the first
    /// part pin in reference order, else `unconnected`.
    pub fn net_name(&self, m: &SheetModel, g: usize) -> String {
        let grp = &self.groups[g];
        if let Some(n) = grp.best_name() {
            return n;
        }
        let mut pins: Vec<&Pin> = grp.part_pins(m).collect();
        pins.sort_by(|a, b| crate::sch_model::ref_order(&a.reference).cmp(&ref_order(&b.reference)).then(a.number.cmp(&b.number)));
        match pins.first() {
            Some(p) => format!("Net-({}-Pad{})", p.reference, p.number),
            None => "unconnected".into(),
        }
    }
}

/// Sort key for references: prefix, then number (R2 before R10).
pub fn ref_order(r: &str) -> (String, u64, String) {
    let head: String = r.chars().take_while(|c| !c.is_ascii_digit()).collect();
    let digits: String = r[head.len()..].chars().take_while(|c| c.is_ascii_digit()).collect();
    let rest = r[head.len() + digits.len()..].to_string();
    (head, digits.parse().unwrap_or(0), rest)
}

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

    #[test]
    fn segment_tests() {
        assert!(on_segment((5.0, 0.0), (0.0, 0.0), (10.0, 0.0)));
        assert!(on_interior((5.0, 0.0), (0.0, 0.0), (10.0, 0.0)));
        assert!(!on_interior((10.0, 0.0), (0.0, 0.0), (10.0, 0.0)));
        assert!(!on_segment((11.0, 0.0), (0.0, 0.0), (10.0, 0.0)));
        assert!(on_segment((5.0, 5.0), (0.0, 0.0), (10.0, 10.0)));
        assert!(!on_segment((5.0, 5.1), (0.0, 0.0), (10.0, 10.0)));
    }

    #[test]
    fn overlap_needs_area() {
        assert!(overlap((0.0, 0.0, 10.0, 10.0), (10.0, 0.0, 20.0, 10.0), 0.1).is_none());
        assert!(overlap((0.0, 0.0, 10.0, 10.0), (5.0, 5.0, 20.0, 20.0), 0.1).is_some());
    }

    #[test]
    fn ref_order_is_natural() {
        let mut v = vec!["R10", "R2", "C1", "R1"];
        v.sort_by_key(|r| ref_order(r));
        assert_eq!(v, vec!["C1", "R1", "R2", "R10"]);
    }

    #[test]
    fn escaped_label_names_are_the_names_kicad_compares() {
        assert_eq!(super::unescape_name("VPP{slash}MCLR"), "VPP/MCLR");
        assert_eq!(super::unescape_name("A{colon}B{space}C"), "A:B C");
        assert_eq!(super::unescape_name("PLAIN"), "PLAIN");
    }
}