tola_caps/trie/

insert.rs

//! Insert and Remove operations for the 16-ary trie
//!
//! Provides traits for inserting capabilities into and removing them from the trie.

use crate::primitives::Peano;
use crate::primitives::{GetTail, Nibble, Present, Absent};
use crate::primitives::stream::{S, D0, StreamEq, DefaultMaxDepth};
use crate::primitives::nibble::{NibbleEq, *};


use super::node::{Empty, Leaf, Node16, EmptyNode16, Bucket};
use super::capability::Capability;
use super::evaluate::{EvalAt, Has};

// =============================================================================
// InsertAt - Main insertion trait
// =============================================================================

/// Insert a capability into a trie node at a given depth
pub trait InsertAt<Cap, Depth> {
    type Out;
}

impl<Cap, Depth> InsertAt<Cap, Depth> for Empty {
    type Out = Leaf<Cap>;
}

#[macros::node16]
impl<Cap, Depth, _Slots_> InsertAt<Cap, Depth> for _Node16_
where
    Cap: Capability,
    Depth: Peano,
    Cap::Stream: GetTail<Depth>,
    Self: NodeInsert<Cap, Depth, Cap::At<Depth>>,
{
    type Out = <Self as NodeInsert<Cap, Depth, Cap::At<Depth>>>::Out;
}

// =============================================================================
// NodeInsert - 16-ary node insertion
// =============================================================================

/// Insert capability into Node16 at specific nibble position
pub trait NodeInsert<Cap, Depth, Nib: Nibble> {
    type Out;
}


#[macros::node16(for_nibble_split)]
impl<Cap, Depth, _Slots_> NodeInsert<Cap, Depth, _Nibble_> for _Node16_
where
    Cap: Capability,
    Depth: Peano,
    _SlotN_: InsertAt<Cap, S<Depth>>,
{
    type Out = Node16<_Before_, <_SlotN_ as InsertAt<Cap, S<Depth>>>::Out, _After_>;
}

// =============================================================================
// LeafInsert - Insertion into Leaf nodes
// =============================================================================

impl<NewCap, StoredCap, Depth> InsertAt<NewCap, Depth> for Leaf<StoredCap>
where
    NewCap: Capability,
    StoredCap: Capability,
    Depth: Peano,
    NewCap::Stream: GetTail<Depth>,
    StoredCap::Stream: GetTail<Depth>,
    Self: LeafInsert<NewCap, StoredCap, Depth, NewCap::At<Depth>, StoredCap::At<Depth>>,
{
    type Out = <Self as LeafInsert<NewCap, StoredCap, Depth, NewCap::At<Depth>, StoredCap::At<Depth>>>::Out;
}

/// Insert into a Leaf node - handles collision vs diverge cases
pub trait LeafInsert<NewCap, StoredCap, Depth, NewNib: Nibble, StoredNib: Nibble> {
    type Out;
}

// =============================================================================
// MakeNode16WithLeaf - Helper traits
// =============================================================================

/// Helper trait to create a Node16 with a single leaf at position Xi
pub trait MakeNode16WithLeaf<Cap, Nib: Nibble> {
    type Out;
}

/// Helper trait to create a Node16 with two leaves at positions
pub trait MakeNode16WithTwoLeaves<NewCap, StoredCap, NewNib: Nibble, StoredNib: Nibble> {
    type Out;
}


#[macros::node16(for_nibble_split)]
impl<Cap> MakeNode16WithLeaf<Cap, _Nibble_> for () {
    type Out = Node16<_EmptyBefore_, Leaf<Cap>, _EmptyAfter_>;
}

// =============================================================================
// LeafInsert - Same nibble collision (16 impls)
// =============================================================================

// Same nibble collision: both caps go into same slot at NEXT depth
// Helper trait to dispatch based on Hash Stream Equality (Collision vs Diverge)
// We include Nibble to ensure uniqueness of impls generated by #[node16(for_nibble_split)]
pub trait LeafCollisionBranch<NewCap, StoredCap, IsCollision, Depth, Nib: Nibble> {
    type Out;
}

// Case 1a: Stream collision AND same type (NewCap == StoredCap) - Deduplicate
impl<Cap, Depth, Nib> LeafCollisionBranch<Cap, Cap, Present, Depth, Nib> for Leaf<Cap>
where
    Cap: Capability,
    Nib: Nibble,
{
    type Out = Leaf<Cap>; // Already present, deduplicate
}

// Note: Case 1b (Stream collision but different types) would create a Bucket.
// However, in our current design, we rely on the hash being unique enough
// that true collisions (different types with same hash) are effectively impossible
// with 64-bit FNV-1a hash + full module path.
// If a collision does occur, compilation will fail with "conflicting implementations"
// which is SAFE (fail-closed) rather than silently wrong behavior.

// Case 2: Diverge -> Deepen
#[macros::node16(for_nibble_split)]
impl<NewCap, StoredCap, Depth> LeafCollisionBranch<NewCap, StoredCap, Absent, Depth, _Nibble_> for Leaf<StoredCap>
where
    StoredCap: Capability,
    NewCap: Capability,
    Empty: InsertAt<StoredCap, S<Depth>>,
    <Empty as InsertAt<StoredCap, S<Depth>>>::Out: InsertAt<NewCap, S<Depth>>,
{
    type Out = Node16<
        _EmptyBefore_,
        <<Empty as InsertAt<StoredCap, S<Depth>>>::Out as InsertAt<NewCap, S<Depth>>>::Out,
        _EmptyAfter_
    >;
}

// Same nibble collision: Check for Full Stream Collision first
#[macros::node16(for_nibble_split)]
impl<NewCap, StoredCap, Depth> LeafInsert<NewCap, StoredCap, Depth, _Nibble_, _Nibble_> for Leaf<StoredCap>
where
    NewCap: Capability,
    StoredCap: Capability,
    NewCap::Stream: StreamEq<StoredCap::Stream, DefaultMaxDepth>, // Check for collision
    Self: LeafCollisionBranch<
        NewCap,
        StoredCap,
        <NewCap::Stream as StreamEq<StoredCap::Stream, DefaultMaxDepth>>::Out,
        Depth,
        _Nibble_
    >,
{
    type Out = <Self as LeafCollisionBranch<
        NewCap,
        StoredCap,
        <NewCap::Stream as StreamEq<StoredCap::Stream, DefaultMaxDepth>>::Out,
        Depth,
        _Nibble_
    >>::Out;
}

// =============================================================================
// LeafInsert - Different nibbles (single generic impl via NibbleEq)
// =============================================================================

/// Different nibbles: insert both leaves into EmptyNode16 at current depth.
/// Uses NibbleEq<Out = Absent> constraint to ensure NewNib != StoredNib.
impl<NewCap, StoredCap, Depth, NewNib, StoredNib>
    LeafInsert<NewCap, StoredCap, Depth, NewNib, StoredNib> for Leaf<StoredCap>
where
    NewCap: Capability,
    StoredCap: Capability,
    NewNib: Nibble + NibbleEq<StoredNib, Out = Absent>,
    StoredNib: Nibble,
    EmptyNode16: NodeInsert<StoredCap, Depth, StoredNib>,
    <EmptyNode16 as NodeInsert<StoredCap, Depth, StoredNib>>::Out:
        NodeInsert<NewCap, Depth, NewNib>,
{
    type Out = <<EmptyNode16 as NodeInsert<StoredCap, Depth, StoredNib>>::Out
        as NodeInsert<NewCap, Depth, NewNib>>::Out;
}

// =============================================================================
// RemoveAt - Main removal trait
// =============================================================================

/// Remove a capability from a trie node at a given depth
pub trait RemoveAt<Cap, Depth> {
    type Out;
}

impl<Cap, Depth> RemoveAt<Cap, Depth> for Empty {
    type Out = Empty;
}

// =============================================================================
// LeafRemove - Removal from Leaf nodes
// =============================================================================

/// Remove from a Leaf node based on match result
pub trait LeafRemove<IsMatch> {
    type Out;
}

impl<S> LeafRemove<Present> for Leaf<S> {
    type Out = Empty;
}

impl<S> LeafRemove<Absent> for Leaf<S> {
    type Out = Leaf<S>;
}

impl<StoredCap, QCap, Depth> RemoveAt<QCap, Depth> for Leaf<StoredCap>
where
    QCap: Capability,
    StoredCap: Capability,
    Leaf<StoredCap>: EvalAt<Has<QCap>, Depth>,
    Leaf<StoredCap>: LeafRemove<<Leaf<StoredCap> as EvalAt<Has<QCap>, Depth>>::Out>,
{
    type Out = <Leaf<StoredCap> as LeafRemove<<Leaf<StoredCap> as EvalAt<Has<QCap>, Depth>>::Out>>::Out;
}

// =============================================================================
// NodeRemove - 16-ary node removal
// =============================================================================

/// Remove capability from Node16 at specific nibble position
pub trait NodeRemove<Cap, Depth, Nib: Nibble> {
    type Out;
}


#[macros::node16(for_nibble_split)]
impl<Cap, Depth, _Slots_> NodeRemove<Cap, Depth, _Nibble_> for _Node16_
where
    Cap: Capability,
    _SlotN_: RemoveAt<Cap, S<Depth>>,
{
    type Out = Node16<_Before_, <_SlotN_ as RemoveAt<Cap, S<Depth>>>::Out, _After_>;
}

#[macros::node16]
impl<Cap, Depth, _Slots_> RemoveAt<Cap, Depth> for _Node16_
where
    Cap: Capability,
    Depth: Peano,
    Cap::Stream: GetTail<Depth>,
    Self: NodeRemove<Cap, Depth, Cap::At<Depth>>,
{
    type Out = <Self as NodeRemove<Cap, Depth, Cap::At<Depth>>>::Out;
}

// =============================================================================
// Bucket Operations (Linear Scan)
// =============================================================================

// InsertAt for Bucket - same type at head means already present
impl<Cap, Tail, Depth> InsertAt<Cap, Depth> for Bucket<Cap, Tail>
where
    Cap: Capability,
{
    type Out = Self; // Already present
}

// RemoveAt for Bucket - same type at head means remove head
impl<Cap, Tail, Depth> RemoveAt<Cap, Depth> for Bucket<Cap, Tail>
where
    Cap: Capability,
{
    type Out = Tail; // Remove head
}

// =============================================================================
// With / Without - User-facing API for adding/removing capabilities
// =============================================================================

/// Add a capability to a set (user-facing API)
///
/// This trait wraps `InsertAt` with depth=D0 for a cleaner API.
/// ```ignore
/// type MySet = <Empty as With<CloneCap>>::Out;
/// ```
#[diagnostic::on_unimplemented(
    message = "Cannot add capability {Cap} to set {Self}",
    label = "Failed to add {Cap} to {Self}",
    note = "Ensure {Self} is a valid capability set (Empty/Leaf/Node) and {Cap} is a Capability."
)]
pub trait With<Cap>: Sized {
    type Out;
}

impl<Ctx, Cap> With<Cap> for Ctx
where
    Cap: Capability,
    Ctx: InsertAt<Cap, D0>,
{
    type Out = <Ctx as InsertAt<Cap, D0>>::Out;
}

/// Remove a capability from a set (user-facing API)
///
/// This trait wraps `RemoveAt` with depth=D0 for a cleaner API.
/// ```ignore
/// type Reduced = <MySet as Without<CloneCap>>::Out;
/// ```
pub trait Without<Cap>: Sized {
    type Out;
}

impl<Ctx, Cap> Without<Cap> for Ctx
where
    Cap: Capability,
    Ctx: RemoveAt<Cap, D0>,
{
    type Out = <Ctx as RemoveAt<Cap, D0>>::Out;
}