ogeom_core/

id.rs

//! Stable entity identity and provenance.
//!
//! See `docs/DATA_MODEL.md` §8. A deliberate divergence from identifying
//! topology by pointer, and the reason this lives in the foundation crate
//! rather than being added later.
//!
//! Where topology is identified by pointer, every modeling operation allocates
//! new nodes, so every reference into a previous result dies: the topological
//! naming problem, which identity reconstructed afterwards from history maps
//! only patches.
//!
//! Here an entity's identity is *what produced it, and from what*. A rebuild
//! with different parameters runs the same operations over the same inputs and
//! therefore produces entities with the same provenance, so a reference like
//! "the fillet on this edge" survives a change to an unrelated dimension.
//!
//! Provenance does not replace operation history: history is what a binding
//! layer consumes, and it is the honest answer where provenance cannot resolve
//! a reference. It is the primary mechanism, not the only one.

use core::num::NonZeroU64;

use smallvec::SmallVec;

/// A stable identity for a topological entity, valid for the lifetime of a
/// document.
///
/// Distinct from an arena [`Key`](crate::Key): a key says *where the data is*
/// and dies when the entity is rebuilt. An `EntityId` says *what the entity is*
/// and survives.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct EntityId(NonZeroU64);

impl EntityId {
    /// The identity's raw value. Non-zero.
    #[must_use]
    pub const fn get(self) -> u64 {
        self.0.get()
    }

    /// An identity from a raw value, or `None` if it is zero.
    ///
    /// For reading a document back from a file, which has to reproduce the
    /// identities it was written with: a reference recorded against
    /// `EntityId(7)` has to still find entity seven. Nothing else should mint
    /// one of these: within a document,
    /// [`ProvenanceTable::record`](ProvenanceTable::record) is what issues an
    /// identity, and it issues one that has something behind it.
    #[must_use]
    pub const fn from_raw(raw: u64) -> Option<Self> {
        match NonZeroU64::new(raw) {
            Some(value) => Some(Self(value)),
            None => None,
        }
    }
}

/// Identifies one invocation of a modeling operation.
///
/// Stable across rebuilds: the third extrusion in a document's recompute is
/// `OpId(3)` every time, which is what lets provenance survive a parameter
/// change.
///
/// The default, `OpId(0)`, is the implicit operation a document starts in:
/// whatever was there before anything was deliberately begun.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct OpId(pub u32);

/// What an entity *is*, relative to the operation that made it.
///
/// The low values are shared vocabulary. Everything from [`Role::OP_DEFINED`]
/// up is interpreted by the producing operation alone. Keeping it a newtype
/// rather than an enum avoids fixing a taxonomy of every role in a CAD
/// kernel before the operations that need one exist.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Role(pub u32);

impl Role {
    /// No distinguishing role: the operation produced exactly one entity of
    /// this kind, so it needs no further discriminator.
    pub const SOLE: Self = Self(0);
    /// The result's outer boundary: the outer wire of a face, the outer shell of
    /// a solid.
    pub const OUTER: Self = Self(1);
    /// An inner boundary: a hole.
    pub const INNER: Self = Self(2);
    /// The start of a swept or extruded result.
    pub const START_CAP: Self = Self(3);
    /// The end of a swept or extruded result.
    pub const END_CAP: Self = Self(4);
    /// The swept side wall between the caps.
    pub const LATERAL: Self = Self(5);
    /// A seam on a closed surface.
    pub const SEAM: Self = Self(6);
    /// The first value an operation may assign meaning to itself.
    pub const OP_DEFINED: u32 = 1024;

    /// An operation-defined role. `index` is offset above [`Role::OP_DEFINED`].
    #[must_use]
    pub const fn op_defined(index: u32) -> Self {
        Self(Self::OP_DEFINED + index)
    }
}

/// Where an entity came from.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Provenance {
    /// Created outright by an operation, from no prior entity: the `+Z` face of
    /// a box, the lateral surface of a cylinder.
    Primitive {
        /// The operation that created it.
        op: OpId,
        /// Which part of that operation's result this is.
        role: Role,
    },
    /// Derived from one or more existing entities. A face split by a boolean
    /// names the face it came from. An intersection edge names both faces.
    Derived {
        /// The operation that derived it.
        op: OpId,
        /// The inputs it came from, in the operation's canonical order.
        from: SmallVec<[EntityId; 2]>,
        /// Which part of that operation's result this is.
        role: Role,
    },
    /// Read from a file. `external` is the source's own identifier (a STEP
    /// entity number, say) so that a re-import matches entities up.
    Imported {
        /// Which imported document it came from.
        source: SourceId,
        /// The identifier the source file gave it.
        external: u64,
    },
}

impl Provenance {
    /// The operation that produced this entity, if any.
    #[must_use]
    pub const fn op(&self) -> Option<OpId> {
        match self {
            Self::Primitive { op, .. } | Self::Derived { op, .. } => Some(*op),
            Self::Imported { .. } => None,
        }
    }

    /// Which part of its operation's result this entity is, if the operation
    /// named one.
    ///
    /// The question provenance exists to answer: "the top face of that box",
    /// asked of a model that has been rebuilt since. An imported entity has no
    /// role, because the file said where it came from and not what it is for.
    #[must_use]
    pub const fn role(&self) -> Option<Role> {
        match self {
            Self::Primitive { role, .. } | Self::Derived { role, .. } => Some(*role),
            Self::Imported { .. } => None,
        }
    }

    /// The entities this one was derived from.
    #[must_use]
    pub fn inputs(&self) -> &[EntityId] {
        match self {
            Self::Derived { from, .. } => from,
            Self::Primitive { .. } | Self::Imported { .. } => &[],
        }
    }
}

/// Identifies an imported document.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SourceId(pub u32);

/// Assigns [`EntityId`]s and remembers what each one came from.
///
/// One per document. Cloning it clones the whole history, which is what a
/// rebuild-with-rollback needs.
///
/// An entry can be forgotten ([`ProvenanceTable::forget`],
/// [`ProvenanceTable::retain`]): its id stays issued, so no later entity
/// takes it, and asking for it answers `None` as for an id from another
/// document.
#[derive(Debug, Clone, Default)]
pub struct ProvenanceTable {
    /// The entries, ascending by id. From `tail_at` on the ids run without
    /// a gap up to the last one issued, so they are found by arithmetic;
    /// the ones before are found by search. An entry forgotten one at a
    /// time stays as `None` until [`ProvenanceTable::retain`] packs it out.
    entries: Vec<(EntityId, Option<Provenance>)>,
    /// Where the gapless run of ids starts in `entries`.
    tail_at: usize,
    /// How many ids have been issued.
    issued: u64,
}

impl ProvenanceTable {
    /// An empty table.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            entries: Vec::new(),
            tail_at: 0,
            issued: 0,
        }
    }

    /// Number of identities issued, forgotten ones included: the next
    /// recorded entity is this plus one.
    #[must_use]
    #[allow(
        clippy::cast_possible_truncation,
        reason = "every issued id has had an entry in memory"
    )]
    pub const fn len(&self) -> usize {
        self.issued as usize
    }

    /// Whether no identity has been issued.
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.issued == 0
    }

    /// Record an entity's provenance and return its identity.
    ///
    /// # Panics
    ///
    /// If more than `u64::MAX - 1` entities are recorded. Not reachable.
    #[allow(clippy::expect_used, reason = "documented panic; see # Panics")]
    pub fn record(&mut self, provenance: Provenance) -> EntityId {
        // Ids start at 1 so that EntityId can be NonZeroU64 and Option<EntityId>
        // costs nothing.
        self.issued = self
            .issued
            .checked_add(1)
            .expect("entity count exceeded u64");
        let id = EntityId(NonZeroU64::new(self.issued).expect("at least 1 after an increment"));
        self.entries.push((id, Some(provenance)));
        id
    }

    /// Convenience for [`Provenance::Primitive`].
    pub fn primitive(&mut self, op: OpId, role: Role) -> EntityId {
        self.record(Provenance::Primitive { op, role })
    }

    /// Convenience for [`Provenance::Derived`].
    pub fn derived(
        &mut self,
        op: OpId,
        from: impl IntoIterator<Item = EntityId>,
        role: Role,
    ) -> EntityId {
        self.record(Provenance::Derived {
            op,
            from: from.into_iter().collect(),
            role,
        })
    }

    /// Where `id`'s entry sits in `entries`, if it has one.
    fn position(&self, id: EntityId) -> Option<usize> {
        let tail_len = (self.entries.len() - self.tail_at) as u64;
        let tail_first = self.issued - tail_len + 1;
        if id.get() >= tail_first {
            let at = self.tail_at + usize::try_from(id.get() - tail_first).ok()?;
            return (at < self.entries.len()).then_some(at);
        }
        self.entries[..self.tail_at]
            .binary_search_by_key(&id, |(id, _)| *id)
            .ok()
    }

    /// The provenance of `id`, or `None` if it belongs to another document
    /// or its entry was forgotten.
    #[must_use]
    pub fn get(&self, id: EntityId) -> Option<&Provenance> {
        self.entries.get(self.position(id)?)?.1.as_ref()
    }

    /// Drop `id`'s entry and keep its id issued.
    ///
    /// For a document that keeps only what its shapes can still reach: an
    /// entity no shape carries and no kept entry derives from answers
    /// nothing a reference could ask. Returns whether there was an entry
    /// to drop.
    pub fn forget(&mut self, id: EntityId) -> bool {
        let Some(at) = self.position(id) else {
            return false;
        };
        self.entries
            .get_mut(at)
            .and_then(|(_, entry)| entry.take())
            .is_some()
    }

    /// Keep the entries `keep` answers `true` for and forget the rest, as
    /// [`ProvenanceTable::forget`] does each one. What is forgotten stops
    /// costing memory.
    pub fn retain(&mut self, mut keep: impl FnMut(EntityId, &Provenance) -> bool) {
        self.entries
            .retain(|(id, entry)| entry.as_ref().is_some_and(|entry| keep(*id, entry)));
        let mut tail_len = 0_usize;
        while tail_len < self.entries.len() {
            let (id, _) = self.entries[self.entries.len() - 1 - tail_len];
            if id.get() + tail_len as u64 != self.issued {
                break;
            }
            tail_len += 1;
        }
        self.tail_at = self.entries.len() - tail_len;
        self.entries.shrink_to_fit();
    }

    /// Walk `id`'s derivation back to the entities it ultimately came from.
    ///
    /// Returns the roots: entities that are `Primitive` or `Imported`. This is
    /// how a stale reference is resolved after a rebuild: find what the user
    /// originally picked, then find what that became.
    ///
    /// Cycles cannot occur, because an entity can only be derived from ids that
    /// already existed when it was recorded. The visited set guards against a
    /// table assembled by hand or deserialized from a corrupt file.
    #[must_use]
    pub fn roots(&self, id: EntityId) -> Vec<EntityId> {
        let mut out = Vec::new();
        let mut seen = crate::collections::FastSet::default();
        let mut stack = vec![id];
        while let Some(current) = stack.pop() {
            if !seen.insert(current) {
                continue;
            }
            match self.get(current) {
                Some(Provenance::Derived { from, .. }) if !from.is_empty() => {
                    stack.extend(from.iter().copied());
                }
                Some(_) => out.push(current),
                None => {}
            }
        }
        out.sort_unstable();
        out
    }

    /// Every entity with an entry, in the order its identity was issued;
    /// forgotten entries are skipped.
    ///
    /// For writing a document out: the table *is* the record of what every
    /// entity is, and a file that dropped it would come back as a model whose
    /// every reference had to be rebuilt from scratch.
    pub fn iter(&self) -> impl Iterator<Item = (EntityId, &Provenance)> {
        self.entries
            .iter()
            .filter_map(|(id, entry)| Some((*id, entry.as_ref()?)))
    }
}

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

    #[test]
    fn ids_are_non_zero_and_distinct() {
        let mut t = ProvenanceTable::new();
        let a = t.primitive(OpId(0), Role::SOLE);
        let b = t.primitive(OpId(0), Role::OUTER);
        assert_ne!(a, b);
        assert!(a.get() > 0 && b.get() > 0);
        assert_eq!(
            core::mem::size_of::<Option<EntityId>>(),
            core::mem::size_of::<EntityId>()
        );
    }

    #[test]
    fn derived_entities_remember_their_inputs() {
        let mut t = ProvenanceTable::new();
        let face_a = t.primitive(OpId(1), Role::LATERAL);
        let face_b = t.primitive(OpId(2), Role::LATERAL);
        let section = t.derived(OpId(3), [face_a, face_b], Role::SOLE);

        let p = t.get(section).unwrap();
        assert_eq!(p.op(), Some(OpId(3)));
        assert_eq!(p.inputs(), &[face_a, face_b]);
    }

    #[test]
    fn roots_walk_back_through_a_derivation_chain() {
        let mut t = ProvenanceTable::new();
        let original = t.primitive(OpId(1), Role::END_CAP);
        // A boolean splits the face, then a fillet modifies one fragment.
        let split = t.derived(OpId(2), [original], Role::op_defined(0));
        let filleted = t.derived(OpId(3), [split], Role::SOLE);

        assert_eq!(t.roots(filleted), vec![original]);
        assert_eq!(t.roots(original), vec![original], "a root is its own root");
    }

    #[test]
    fn roots_of_a_multi_parent_entity_include_every_branch() {
        let mut t = ProvenanceTable::new();
        let a = t.primitive(OpId(1), Role::SOLE);
        let b = t.primitive(OpId(2), Role::SOLE);
        let mid = t.derived(OpId(3), [a], Role::SOLE);
        let joined = t.derived(OpId(4), [mid, b], Role::SOLE);

        let mut expected = vec![a, b];
        expected.sort_unstable();
        assert_eq!(t.roots(joined), expected);
    }

    #[test]
    fn ids_from_another_document_do_not_resolve() {
        let mut t = ProvenanceTable::new();
        let mine = t.primitive(OpId(0), Role::SOLE);
        let mut other = ProvenanceTable::new();
        for _ in 0..10 {
            other.primitive(OpId(0), Role::SOLE);
        }
        let theirs = other.primitive(OpId(0), Role::SEAM);

        assert!(t.get(mine).is_some());
        assert!(t.get(theirs).is_none(), "foreign id must not resolve");
    }

    #[test]
    fn a_forgotten_entry_keeps_its_id_issued() {
        let mut t = ProvenanceTable::new();
        let a = t.primitive(OpId(1), Role::SOLE);
        let b = t.primitive(OpId(2), Role::SOLE);
        assert!(t.forget(a));
        assert!(!t.forget(a), "already forgotten");
        assert!(t.get(a).is_none());
        assert_eq!(t.len(), 2);
        assert_eq!(t.iter().map(|(id, _)| id).collect::<Vec<_>>(), vec![b]);
        let c = t.primitive(OpId(3), Role::SOLE);
        assert_eq!(c.get(), 3, "the next id follows every id issued");
    }

    #[test]
    fn retained_entries_answer_under_their_ids_and_new_ones_follow() {
        let mut t = ProvenanceTable::new();
        let ids: Vec<_> = (0..8).map(|i| t.primitive(OpId(i), Role::SOLE)).collect();
        let kept = [ids[1], ids[4], ids[6], ids[7]];
        t.retain(|id, _| kept.contains(&id));
        for (i, id) in ids.iter().enumerate() {
            let want = kept.contains(id).then_some(OpId(u32::try_from(i).unwrap()));
            assert_eq!(t.get(*id).and_then(Provenance::op), want);
        }
        assert_eq!(t.len(), 8);
        let next = t.derived(OpId(9), [ids[4]], Role::SOLE);
        assert_eq!(next.get(), 9);
        assert_eq!(t.roots(next), vec![ids[4]]);
        assert_eq!(
            t.iter().map(|(id, _)| id.get()).collect::<Vec<_>>(),
            vec![2, 5, 7, 8, 9]
        );
    }

    #[test]
    fn op_defined_roles_do_not_collide_with_shared_ones() {
        assert!(Role::op_defined(0).0 > Role::SEAM.0);
        assert_ne!(Role::op_defined(0), Role::op_defined(1));
    }
}