brep_kernel/feature_pipeline/features/sketch/

loop_ids.rs

//! Stable per-LOOP identity for a sketch's closed loops.
//!
//! # Why
//!
//! A profile-swept feature (extrude/sweep/revolve/loft/path-sweep) builds one
//! prism per profile REGION and stamps names on the result. Sidewalls are safe:
//! they are named from the source geometry's persistent `{sketchId}:G{gid}`. The
//! CAPS were not — every region stamped the SAME `{cap_base}_START/_END`, so the
//! post-union `ensure_unique_face_names` pass disambiguated them POSITIONALLY
//! (`X[0]`, `X[1]`, …) in shell/face encounter order. Editing the sketch to add
//! or remove a loop shifted those indices, and a fillet that referenced `X[1]`
//! silently jumped to a different island on replay.
//!
//! The fix is to give every loop an identity of its own that the cap names embed.
//! That identity must survive editing the loop itself, so it is PERSISTED: each
//! sketch geometry carries a `loopId` in `persistentData.sketch`, written back by
//! the editor on commit (`assign_sketch_loop_ids`).
//!
//! # The rule
//!
//! For each assembled closed loop:
//! - if ANY member edge carries a stored `loopId`, the loop claims the LOWEST of
//!   them ("lowest number wins") and that value is written back onto every other
//!   member edge, so the loop keeps its identity as edges come and go;
//! - otherwise the loop is new and SEEDS its id from the lowest geometry id
//!   among its edges.
//!
//! Both halves are computed the same way whether or not the document has ever
//! been committed, so a sketch that has never been through the editor derives
//! exactly the id it would have been assigned — reading and writing never
//! disagree, and no document renames faces merely by being opened.
//!
//! # Resilience
//!
//! - ADDING an edge to a loop: the new edge carries no id and inherits the
//!   loop's — unchanged. (Minting also hands out ids above the current maximum,
//!   so a seed can only move down, never up.)
//! - REMOVING a non-anchor edge: the id lives on the survivors — unchanged.
//! - REMOVING the anchor edge (the one the id was seeded from): still unchanged,
//!   because the id was persisted onto the whole loop, not recomputed from the
//!   anchor. This is the case a derive-only scheme cannot handle, and the reason
//!   the id is stored at all.
//! - Editing a DIFFERENT loop: never observed here — a loop's claim reads only
//!   its own edges. That is the reported bug, fixed.
//!
//! # Collisions
//!
//! Two loops can claim the same id: a loop that SPLIT in two (both halves carry
//! the same stored id), or — because the editor mints `max(existing gid) + 1` and
//! therefore REUSES the ids of deleted geometry — a freshly drawn loop whose
//! seed collides with an older loop's stored id. Ties break in this order:
//! 1. a loop that INHERITED the id (stored on its edges) beats one that merely
//!    seeded it from a gid, so a new loop can never steal a live loop's identity;
//! 2. between two inheritors (the split case), the one holding the lower minimum
//!    gid keeps it — deterministic, and independent of loop order.
//! The loser re-seeds from its own lowest gid, or, if that is taken too, from one
//! above the highest id in play. A split therefore keeps the original id on one
//! half and mints a fresh one for the other; if the halves are later rejoined,
//! the survivor's id wins again.

use super::geometry::Loop;

/// Resolve every loop's [`Loop::loop_id`], in place.
///
/// `loops` is the fully assembled set (chained loops plus whole circles and
/// ellipses) BEFORE region classification, so ids are decided over the sketch as
/// a whole and never depend on how the loops later group into regions.
pub(super) fn resolve(loops: &mut [Loop]) {
    let claims: Vec<Claim> = loops.iter().map(Claim::of).collect();
    for (loop_data, id) in loops.iter_mut().zip(settle(&claims)) {
        loop_data.loop_id = id;
    }
}

/// One loop's claim: the id it wants, whether it INHERITED that id from stored
/// geometry (as opposed to seeding it from a gid), and its lowest gid — the
/// tie-break and the re-seed source.
struct Claim {
    id: Option<u64>,
    inherited: bool,
    min_gid: Option<u64>,
}

impl Claim {
    fn of(loop_data: &Loop) -> Self {
        let stored = loop_data
            .entries
            .iter()
            .filter_map(|(segment, _)| segment.ids.loop_id)
            .min();
        let min_gid = loop_data
            .entries
            .iter()
            .filter_map(|(segment, _)| segment.ids.gid)
            .min();
        Self {
            id: stored.or(min_gid),
            inherited: stored.is_some(),
            min_gid,
        }
    }
}

/// Award each claim a UNIQUE id, applying the tie-break rules in the module doc.
/// Returns one id per claim, in input order.
fn settle(claims: &[Claim]) -> Vec<Option<u64>> {
    // Award order: inheritors first (they cannot be displaced by a seeder), then
    // by ascending minimum gid, then by input position — a total order, so the
    // outcome never depends on the order the loops happened to be assembled in.
    let mut order: Vec<usize> = (0..claims.len()).collect();
    order.sort_by_key(|&index| {
        let claim = &claims[index];
        (!claim.inherited, claim.min_gid.unwrap_or(u64::MAX), index)
    });

    let mut taken: Vec<u64> = Vec::with_capacity(claims.len());
    let mut resolved = vec![None; claims.len()];
    for index in order {
        let claim = &claims[index];
        let Some(wanted) = claim.id else { continue };
        let id = if taken.contains(&wanted) {
            // Displaced: fall back to this loop's own lowest gid, else to one
            // above everything in play (ids are just numbers — a re-seed is free
            // to leave the gid space).
            let own = claim.min_gid.filter(|gid| !taken.contains(gid));
            own.unwrap_or_else(|| next_free(claims, &taken))
        } else {
            wanted
        };
        taken.push(id);
        resolved[index] = Some(id);
    }
    resolved
}

/// One above the highest id anywhere in play (awarded, claimed, or a gid) — the
/// last-resort id for a loop displaced off both its stored id and its own gid.
fn next_free(claims: &[Claim], taken: &[u64]) -> u64 {
    let highest = taken
        .iter()
        .copied()
        .chain(claims.iter().flat_map(|claim| claim.id.into_iter()))
        .chain(claims.iter().flat_map(|claim| claim.min_gid.into_iter()))
        .max()
        .unwrap_or(0);
    highest.saturating_add(1)
}

#[cfg(test)]
mod tests {
    use super::super::geometry::{SegKind, Segment, SegmentIds};
    use super::*;

    /// A loop of `(gid, stored loop id)` edges — geometry only matters to the
    /// containment pass, so the segments here are placeholders.
    fn loop_of(edges: &[(u64, Option<u64>)]) -> Loop {
        Loop {
            entries: edges
                .iter()
                .map(|&(gid, loop_id)| {
                    (
                        Segment {
                            a: [0.0, 0.0],
                            b: [1.0, 0.0],
                            kind: SegKind::Line,
                            name: Some(format!("S1:G{gid}")),
                            ids: SegmentIds {
                                gid: Some(gid),
                                loop_id,
                            },
                        },
                        false,
                    )
                })
                .collect(),
            polygon: Vec::new(),
            loop_id: None,
        }
    }

    fn ids(loops: &[Loop]) -> Vec<Option<u64>> {
        loops.iter().map(|l| l.loop_id).collect()
    }

    /// A never-committed sketch seeds each loop from its own lowest gid.
    #[test]
    fn fresh_loops_seed_from_their_lowest_gid() {
        let mut loops = vec![
            loop_of(&[(4, None), (9, None), (12, None)]),
            loop_of(&[(2, None), (7, None)]),
        ];
        resolve(&mut loops);
        assert_eq!(ids(&loops), vec![Some(4), Some(2)]);
    }

    /// The reported bug: removing a WHOLE loop leaves the others' ids alone.
    #[test]
    fn deleting_another_loop_does_not_move_an_ids() {
        let three = vec![
            loop_of(&[(4, Some(4)), (5, Some(4))]),
            loop_of(&[(9, Some(9)), (10, Some(9))]),
            loop_of(&[(12, Some(12)), (13, Some(12))]),
        ];
        let mut before = three;
        resolve(&mut before);
        // The middle loop is deleted; the survivors keep their exact ids.
        let mut after = vec![
            loop_of(&[(4, Some(4)), (5, Some(4))]),
            loop_of(&[(12, Some(12)), (13, Some(12))]),
        ];
        resolve(&mut after);
        assert_eq!(ids(&before), vec![Some(4), Some(9), Some(12)]);
        assert_eq!(ids(&after), vec![Some(4), Some(12)]);
    }

    /// Lowest stored id wins, and adding an edge (no stored id) changes nothing.
    #[test]
    fn lowest_stored_id_wins_and_new_edges_inherit() {
        let mut loops = vec![loop_of(&[(9, Some(4)), (10, Some(7)), (11, None)])];
        resolve(&mut loops);
        assert_eq!(ids(&loops), vec![Some(4)]);
    }

    /// Deleting the anchor edge keeps the id: it lives on the survivors.
    #[test]
    fn deleting_the_anchor_edge_keeps_the_id() {
        let mut loops = vec![loop_of(&[(9, Some(4)), (10, Some(4))])];
        resolve(&mut loops);
        assert_eq!(ids(&loops), vec![Some(4)]);
    }

    /// Gid reuse: a newly drawn loop whose seed collides with a live loop's
    /// STORED id must not steal it — the inheritor keeps it, the seeder re-seeds.
    #[test]
    fn a_new_loop_cannot_steal_a_stored_id() {
        let mut loops = vec![
            // Older loop: its anchor (gid 4) was deleted, id 4 lives on gids 7/8.
            loop_of(&[(7, Some(4)), (8, Some(4))]),
            // Freshly drawn over the recycled ids 4..6 — seeds 4, which is taken.
            loop_of(&[(4, None), (5, None), (6, None)]),
        ];
        resolve(&mut loops);
        // The inheritor keeps 4; the new loop cannot fall back to its own lowest
        // gid either (also 4, also taken), so it re-seeds above everything in
        // play. What matters is that it did NOT take 4.
        assert_eq!(ids(&loops), vec![Some(4), Some(8)]);
    }

    /// A split loop: one half keeps the id, the other re-seeds from its own gid.
    #[test]
    fn a_split_loop_keeps_one_id_and_mints_the_other() {
        let mut loops = vec![
            loop_of(&[(4, Some(4)), (5, Some(4))]),
            loop_of(&[(6, Some(4)), (7, Some(4))]),
        ];
        resolve(&mut loops);
        assert_eq!(ids(&loops), vec![Some(4), Some(6)]);
    }

    /// Awarding is independent of the order the loops arrive in.
    #[test]
    fn award_order_is_independent_of_loop_order() {
        let mut forward = vec![
            loop_of(&[(6, Some(4)), (7, Some(4))]),
            loop_of(&[(4, Some(4)), (5, Some(4))]),
        ];
        resolve(&mut forward);
        assert_eq!(ids(&forward), vec![Some(6), Some(4)]);
    }
}

// ===========================================================================
// Write-back — the editor side
// ===========================================================================

/// Assign every closed loop's id onto the geometries of a SOLVED sketch document,
/// in place, and report whether anything changed.
///
/// This is the persistence half of the scheme: the kernel DERIVES ids the same
/// way every run (so a document that has never been through here still names its
/// faces correctly), and this writes the derived ids down so they survive the one
/// edit deriving cannot: deleting the edge an id was seeded from. The editor calls
/// it when a sketch is committed.
///
/// `doc` is the `persistentData.sketch` object. Geometry that is construction-only
/// or not part of a closed loop is left untouched — only a loop has an identity.
pub fn assign_sketch_loop_ids(doc: &mut serde_json::Value) -> bool {
    let Some(loops) = closed_loops(doc) else {
        return false;
    };
    let mut changed = false;
    let Some(geometries) = doc
        .get_mut("geometries")
        .and_then(serde_json::Value::as_array_mut)
    else {
        return false;
    };
    for geometry in geometries.iter_mut() {
        let Some(gid) = geometry.get("id").and_then(numeric) else {
            continue;
        };
        let Some(loop_id) = loops.get(&gid) else {
            continue;
        };
        let already = geometry.get("loopId").and_then(numeric);
        if already == Some(*loop_id) {
            continue;
        }
        if let Some(object) = geometry.as_object_mut() {
            object.insert("loopId".into(), serde_json::json!(loop_id));
            changed = true;
        }
    }
    changed
}

/// `geometry id -> loop id` for every geometry that belongs to a closed loop,
/// derived exactly as the sketch feature derives it: chain the segments, settle
/// the claims, then hand each loop's awarded id to ALL of its members ("lowest
/// number wins and updates the rest of the edges in that loop to match").
fn closed_loops(doc: &serde_json::Value) -> Option<std::collections::HashMap<u64, u64>> {
    let members = loop_members(doc)?;
    let claims: Vec<Claim> = members
        .iter()
        .map(|edges| {
            let stored = edges.iter().filter_map(|(_, stored)| *stored).min();
            let min_gid = edges.iter().map(|(gid, _)| *gid).min();
            Claim {
                id: stored.or(min_gid),
                inherited: stored.is_some(),
                min_gid,
            }
        })
        .collect();
    let mut assignment = std::collections::HashMap::new();
    for (edges, id) in members.iter().zip(settle(&claims)) {
        let Some(id) = id else { continue };
        for (gid, _) in edges {
            assignment.insert(*gid, id);
        }
    }
    Some(assignment)
}

/// Group the document's model geometry into closed loops, as
/// `(geometry id, stored loop id)` per member.
///
/// Whole circles and ellipses are loops on their own. The rest chain end-to-end
/// through shared POINT ids — the same adjacency the profile chainer walks, read
/// off the document's point references rather than solved coordinates, which is
/// exact and needs no tolerance. A chain is closed when it returns to its start.
///
/// At a BRANCHING junction (three or more segments meeting at one point — not a
/// well-formed profile) this walk takes the first candidate, which may group the
/// edges differently than the profile chainer does. That degrades safely rather
/// than corrupting anything: the kernel resolves each loop's id from the ids
/// stored on ITS OWN edges, so a mis-grouped stamp at worst makes two loops claim
/// the same id, which [`settle`] then breaks apart deterministically.
fn loop_members(doc: &serde_json::Value) -> Option<Vec<Vec<(u64, Option<u64>)>>> {
    let geometries = doc.get("geometries")?.as_array()?;
    let mut loops: Vec<Vec<(u64, Option<u64>)>> = Vec::new();
    // (gid, stored, endpoint a, endpoint b) for the chainable segments.
    let mut segments: Vec<(u64, Option<u64>, u64, u64)> = Vec::new();
    for geometry in geometries {
        if geometry.get("construction").and_then(serde_json::Value::as_bool) == Some(true) {
            continue;
        }
        let Some(gid) = geometry.get("id").and_then(numeric) else {
            continue;
        };
        let stored = geometry.get("loopId").and_then(numeric);
        let geom_type = geometry
            .get("type")
            .and_then(serde_json::Value::as_str)
            .unwrap_or("");
        let points: Vec<u64> = geometry
            .get("points")
            .and_then(serde_json::Value::as_array)
            .map(|ids| ids.iter().filter_map(numeric).collect())
            .unwrap_or_default();
        match geom_type {
            // Self-contained loops.
            "circle" | "ellipse" => loops.push(vec![(gid, stored)]),
            // `[start, end]`.
            "line" if points.len() == 2 => segments.push((gid, stored, points[0], points[1])),
            // `[center, start, end]`.
            "arc" if points.len() == 3 => segments.push((gid, stored, points[1], points[2])),
            // `[p0, …, pn]` — the spline's endpoints are its first and last.
            "bezier" if points.len() >= 2 => {
                segments.push((gid, stored, points[0], points[points.len() - 1]))
            }
            _ => {}
        }
    }

    // Walk each connected component; keep it only if it closes.
    let mut visited = vec![false; segments.len()];
    for start in 0..segments.len() {
        if visited[start] {
            continue;
        }
        let (_, _, first_point, _) = segments[start];
        let mut chain = vec![start];
        visited[start] = true;
        let mut tail = segments[start].3;
        loop {
            if tail == first_point {
                // Closed: a chain of one segment closes only if it is a loop on
                // its own (a full-circle arc), which the endpoints already say.
                loops.push(
                    chain
                        .iter()
                        .map(|&index| (segments[index].0, segments[index].1))
                        .collect(),
                );
                break;
            }
            let next = (0..segments.len()).find(|&index| {
                !visited[index] && (segments[index].2 == tail || segments[index].3 == tail)
            });
            let Some(next) = next else { break };
            visited[next] = true;
            chain.push(next);
            tail = if segments[next].2 == tail {
                segments[next].3
            } else {
                segments[next].2
            };
        }
    }
    Some(loops)
}

/// A JSON id as a number (a numeric string counts) — the write-back's copy of the
/// sketch pipeline's `numeric_id`, so both halves read ids identically.
fn numeric(value: &serde_json::Value) -> Option<u64> {
    match value {
        serde_json::Value::Number(number) => number.as_u64(),
        serde_json::Value::String(text) => text.parse().ok(),
        _ => None,
    }
}

#[cfg(test)]
mod write_back_tests {
    use super::*;
    use serde_json::json;

    fn line(id: u64, a: u64, b: u64) -> serde_json::Value {
        json!({ "id": id, "type": "line", "points": [a, b] })
    }

    /// The loop id each geometry ended up with.
    fn stamped(doc: &serde_json::Value) -> Vec<(u64, Option<u64>)> {
        doc["geometries"]
            .as_array()
            .unwrap()
            .iter()
            .map(|geometry| {
                (
                    numeric(&geometry["id"]).unwrap(),
                    geometry.get("loopId").and_then(numeric),
                )
            })
            .collect()
    }

    /// A closed loop's id lands on EVERY one of its edges, not just the anchor —
    /// that is what lets the loop keep its identity when the anchor is deleted.
    #[test]
    fn a_closed_loop_stamps_all_of_its_edges() {
        let mut doc = json!({
            "points": [],
            "geometries": [line(4, 1, 2), line(5, 2, 3), line(6, 3, 1)],
            "constraints": [],
        });
        assert!(assign_sketch_loop_ids(&mut doc));
        assert_eq!(stamped(&doc), vec![(4, Some(4)), (5, Some(4)), (6, Some(4))]);
        // Idempotent: a second commit changes nothing.
        assert!(!assign_sketch_loop_ids(&mut doc));
    }

    /// Two disjoint loops get their own ids, and deleting the FIRST loop's anchor
    /// edge leaves both loops' ids exactly where they were.
    #[test]
    fn deleting_an_anchor_edge_preserves_both_loop_ids() {
        let mut doc = json!({
            "points": [],
            "geometries": [
                line(4, 1, 2), line(5, 2, 3), line(6, 3, 1),
                line(7, 10, 11), line(8, 11, 12), line(9, 12, 10),
            ],
            "constraints": [],
        });
        assign_sketch_loop_ids(&mut doc);
        assert_eq!(
            stamped(&doc),
            vec![
                (4, Some(4)), (5, Some(4)), (6, Some(4)),
                (7, Some(7)), (8, Some(7)), (9, Some(7)),
            ],
        );

        // Delete edge 4 (loop A's anchor) and re-close the loop with a new edge
        // 12 — the editor's own "delete and redraw" shape.
        let mut edited = json!({
            "points": [],
            "geometries": [
                { "id": 5, "type": "line", "points": [2, 3], "loopId": 4 },
                { "id": 6, "type": "line", "points": [3, 1], "loopId": 4 },
                line(12, 1, 2),
                { "id": 7, "type": "line", "points": [10, 11], "loopId": 7 },
                { "id": 8, "type": "line", "points": [11, 12], "loopId": 7 },
                { "id": 9, "type": "line", "points": [12, 10], "loopId": 7 },
            ],
            "constraints": [],
        });
        assign_sketch_loop_ids(&mut edited);
        assert_eq!(
            stamped(&edited),
            vec![
                (5, Some(4)), (6, Some(4)), (12, Some(4)),
                (7, Some(7)), (8, Some(7)), (9, Some(7)),
            ],
            "both loops kept their ids; the new edge inherited loop A's",
        );
    }

    /// A whole circle is a loop on its own; an OPEN chain is not a loop and is
    /// left alone.
    #[test]
    fn circles_are_loops_and_open_chains_are_not() {
        let mut doc = json!({
            "points": [],
            "geometries": [
                { "id": 3, "type": "circle", "points": [1, 2] },
                line(7, 10, 11),
                line(8, 11, 12),
            ],
            "constraints": [],
        });
        assign_sketch_loop_ids(&mut doc);
        assert_eq!(stamped(&doc), vec![(3, Some(3)), (7, None), (8, None)]);
    }

    /// Construction geometry constrains but never models a loop.
    #[test]
    fn construction_geometry_is_never_stamped() {
        let mut doc = json!({
            "points": [],
            "geometries": [
                line(4, 1, 2), line(5, 2, 3), line(6, 3, 1),
                { "id": 2, "type": "line", "points": [1, 3], "construction": true },
            ],
            "constraints": [],
        });
        assign_sketch_loop_ids(&mut doc);
        assert_eq!(
            stamped(&doc),
            vec![(4, Some(4)), (5, Some(4)), (6, Some(4)), (2, None)],
        );
    }
}