hibana 0.9.2

//! Mutable frontier-state owner for endpoint kernel runtime bookkeeping.
//!
//! # Unsafe Owner Contract
//!
//! This module owns mutable frontier-state buffers for one endpoint runtime
//! image. Unsafe blocks here may expose table entries only within the initialized
//! capacity recorded on the same frontier state object.

use core::ops::{Index, IndexMut};

use super::frontier::{
    ActiveEntrySet, ActiveEntrySlot, EntryBuffer, LaneOfferState, RootFrontierState,
};
use super::frontier::{OfferEntrySlot, OfferEntryState, OfferEntryTable};
use crate::global::const_dsl::ScopeId;

pub(super) struct RootFrontierTable {
    ptr: *mut RootFrontierState,
    active_entries: *mut ActiveEntrySlot,
    capacity: u16,
    pool_capacity: u8,
}

pub(super) struct RootFrontierStorage {
    pub(super) rows: *mut RootFrontierState,
    pub(super) active_entries: *mut ActiveEntrySlot,
}

pub(super) struct RootFrontierCapacity {
    pub(super) row_count: usize,
    pub(super) pool_capacity: usize,
}

pub(super) struct FrontierStateStorage {
    pub(super) root: RootFrontierStorage,
    pub(super) offer_entry_slots: *mut OfferEntrySlot,
}

pub(super) struct FrontierStateCapacity {
    pub(super) root: RootFrontierCapacity,
    pub(super) max_offer_entries: usize,
}

impl RootFrontierTable {
    unsafe fn init_from_parts(
        dst: *mut Self,
        storage: RootFrontierStorage,
        capacity: RootFrontierCapacity,
    ) {
        if capacity.row_count > u16::MAX as usize {
            crate::invariant();
        }
        if capacity.pool_capacity > u8::MAX as usize {
            crate::invariant();
        }
        /* SAFETY: `FrontierState::init_empty` passes an unpublished root table; row and active-entry columns are installed before borrow. */
        unsafe {
            core::ptr::addr_of_mut!((*dst).ptr).write(storage.rows);
            core::ptr::addr_of_mut!((*dst).active_entries).write(storage.active_entries);
            core::ptr::addr_of_mut!((*dst).capacity).write(capacity.row_count as u16);
            core::ptr::addr_of_mut!((*dst).pool_capacity).write(capacity.pool_capacity as u8);
        }
        let mut slot_idx = 0usize;
        while slot_idx < capacity.row_count {
            /* SAFETY: `slot_idx < row_count` selects one unpublished root row; every row starts EMPTY before exposure. */
            unsafe {
                storage.rows.add(slot_idx).write(RootFrontierState::EMPTY);
            }
            slot_idx += 1;
        }
        let mut entry_idx = 0usize;
        while entry_idx < capacity.pool_capacity {
            /* SAFETY: `entry_idx < pool_capacity` selects one active-entry pool slot initialized before publication. */
            unsafe {
                storage
                    .active_entries
                    .add(entry_idx)
                    .write(ActiveEntrySlot::EMPTY);
            }
            entry_idx += 1;
        }
    }

    #[inline]
    fn capacity(&self) -> usize {
        self.capacity as usize
    }

    #[inline]
    fn pool_capacity(&self) -> usize {
        self.pool_capacity as usize
    }

    #[inline]
    fn len(&self) -> usize {
        let mut len = 0usize;
        while len < self.capacity() {
            if self[len].root.is_none() {
                break;
            }
            len += 1;
        }
        len
    }

    #[inline]
    fn active_pool_used(&self) -> usize {
        let len = self.len();
        if len == 0 {
            return 0;
        }
        let tail = self[len - 1];
        tail.active_start as usize + tail.active_len as usize
    }

    #[inline]
    fn active_entry_set(&self, slot_idx: usize) -> ActiveEntrySet {
        let row = self[slot_idx];
        if row.active_len == 0 {
            return ActiveEntrySet::EMPTY;
        }
        ActiveEntrySet {
            slots: EntryBuffer::from_parts(
                /* SAFETY: row active span is allocated from this table's active-entry pool and stays below `active_pool_used()`. */
                unsafe { self.active_entries.add(row.active_start as usize) },
                row.active_len as usize,
            ),
        }
    }

    #[inline]
    fn clear_row(&mut self, slot_idx: usize) {
        self[slot_idx] = RootFrontierState::EMPTY;
    }

    #[inline]
    fn prepare_row(&mut self, slot_idx: usize, root: ScopeId) {
        let active_start = self.active_pool_used();
        let row = &mut self[slot_idx];
        row.root = root;
        row.active_start = active_start as u8;
        row.active_len = 0;
    }

    fn insert_root_active_entry(
        &mut self,
        slot_idx: usize,
        entry_idx: usize,
        lane_idx: u8,
    ) -> bool {
        if slot_idx >= self.len() {
            crate::invariant();
        }
        let Some(entry) = super::frontier::checked_state_index(entry_idx) else {
            return false;
        };
        let row = self[slot_idx];
        let start = row.active_start as usize;
        let len = row.active_len as usize;
        let mut insert_rel = 0usize;
        while insert_rel < len {
            let existing = /* SAFETY: `insert_rel < row.active_len` bounds a shared read inside the root row active-entry span. */ unsafe { *self.active_entries.add(start + insert_rel) };
            if existing.entry == entry {
                return false;
            }
            if existing.lane_idx > lane_idx
                || (existing.lane_idx == lane_idx && existing.entry.raw() > entry.raw())
            {
                break;
            }
            insert_rel += 1;
        }
        let used = self.active_pool_used();
        if used >= self.pool_capacity() {
            return false;
        }
        let insert_idx = start + insert_rel;
        let mut idx = used;
        while idx > insert_idx {
            /* SAFETY: `idx` and `idx - 1` are inside initialized active-entry pool; `&mut self` owns this insert shift. */
            unsafe {
                self.active_entries
                    .add(idx)
                    .write(*self.active_entries.add(idx - 1));
            }
            idx -= 1;
        }
        /* SAFETY: `insert_idx < pool_capacity`; active entry is written before row lengths change. */
        unsafe {
            self.active_entries
                .add(insert_idx)
                .write(ActiveEntrySlot { entry, lane_idx });
        }
        if self[slot_idx].active_len == u8::MAX {
            crate::invariant();
        }
        self[slot_idx].active_len += 1;
        let row_len = self.len();
        let mut idx = slot_idx + 1;
        while idx < row_len {
            if self[idx].active_start == u8::MAX {
                crate::invariant();
            }
            self[idx].active_start += 1;
            idx += 1;
        }
        true
    }

    fn remove_root_active_entry(&mut self, slot_idx: usize, entry_idx: usize) -> bool {
        if slot_idx >= self.len() {
            crate::invariant();
        }
        let row = self[slot_idx];
        let start = row.active_start as usize;
        let len = row.active_len as usize;
        let mut remove_rel = 0usize;
        let entry = crate::invariant_some(super::frontier::checked_state_index(entry_idx));
        while remove_rel < len {
            if
            /* SAFETY: `remove_rel < row.active_len` bounds this shared read inside the root row active-entry span. */
            unsafe { (*self.active_entries.add(start + remove_rel)).entry } == entry {
                break;
            }
            remove_rel += 1;
        }
        if remove_rel >= len {
            return false;
        }
        let used = self.active_pool_used();
        let remove_idx = start + remove_rel;
        let mut idx = remove_idx;
        while idx + 1 < used {
            /* SAFETY: `idx` and `idx + 1` are inside used active-entry pool; `&mut self` owns removal compaction. */
            unsafe {
                self.active_entries
                    .add(idx)
                    .write(*self.active_entries.add(idx + 1));
            }
            idx += 1;
        }
        if used != 0 {
            /* SAFETY: `used - 1` is the old tail slot after compaction; clearing removes stale cells. */
            unsafe {
                self.active_entries
                    .add(used - 1)
                    .write(ActiveEntrySlot::EMPTY);
            }
        }
        if self[slot_idx].active_len == 0 {
            crate::invariant();
        }
        self[slot_idx].active_len -= 1;
        let row_len = self.len();
        let mut idx = slot_idx + 1;
        while idx < row_len {
            if self[idx].active_start == 0 {
                crate::invariant();
            }
            self[idx].active_start -= 1;
            idx += 1;
        }
        true
    }

    fn remove_root_row(&mut self, slot_idx: usize) {
        let len = self.len();
        if slot_idx >= len {
            crate::invariant();
        }

        let active_span = self[slot_idx].active_len as usize;
        if active_span != 0 {
            let start = self[slot_idx].active_start as usize;
            let used = self.active_pool_used();
            let mut idx = start;
            while idx + active_span < used {
                /* SAFETY: `idx` and `idx + active_span` are inside used active-entry pool; `&mut self` owns the root-row removal shift. */
                unsafe {
                    self.active_entries
                        .add(idx)
                        .write(*self.active_entries.add(idx + active_span));
                }
                idx += 1;
            }
            let mut clear_idx = used - active_span;
            while clear_idx < used {
                /* SAFETY: `clear_idx` walks the old tail span after compaction; clearing removes stale cells. */
                unsafe {
                    self.active_entries
                        .add(clear_idx)
                        .write(ActiveEntrySlot::EMPTY);
                }
                clear_idx += 1;
            }
        }

        let mut idx = slot_idx + 1;
        while idx < len {
            let mut shifted = self[idx];
            if active_span != 0 {
                if active_span > shifted.active_start as usize {
                    crate::invariant();
                }
                shifted.active_start -= active_span as u8;
            }
            self[idx - 1] = shifted;
            idx += 1;
        }
        self.clear_row(len - 1);
    }
}

impl Index<usize> for RootFrontierTable {
    type Output = RootFrontierState;

    #[inline]
    fn index(&self, index: usize) -> &Self::Output {
        if index >= self.capacity() {
            crate::invariant();
        }
        /* SAFETY: `index < capacity` bounds the initialized root row column; `&self` creates only a shared row borrow. */
        unsafe { &*self.ptr.add(index) }
    }
}

impl IndexMut<usize> for RootFrontierTable {
    #[inline]
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        if index >= self.capacity() {
            crate::invariant();
        }
        /* SAFETY: `index < capacity` bounds the initialized root row column, and `&mut self` is the row mutation token. */
        unsafe { &mut *self.ptr.add(index) }
    }
}

pub(super) struct FrontierState {
    pub(super) root_frontier_state: RootFrontierTable,
    pub(super) offer_entry_state: OfferEntryTable,
    pub(super) global_frontier_scratch_state: FrontierScratchState,
}

#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum FrontierScratchState {
    Uninitialized = 0,
    Initialized = 1,
}

impl FrontierScratchState {
    #[inline]
    pub(super) const fn is_initialized(self) -> bool {
        matches!(self, Self::Initialized)
    }
}

impl FrontierState {
    pub(super) unsafe fn init_empty(
        dst: *mut Self,
        storage: FrontierStateStorage,
        capacity: FrontierStateCapacity,
    ) {
        unsafe {
            // SAFETY: `FrontierState` is initialized in one caller-owned endpoint
            // arena. The root and offer-entry sub-tables receive disjoint backing
            // buffers with capacities recorded on their respective owners before
            // safe frontier methods can observe them.
            RootFrontierTable::init_from_parts(
                core::ptr::addr_of_mut!((*dst).root_frontier_state),
                storage.root,
                capacity.root,
            );
            OfferEntryTable::init_from_parts(
                core::ptr::addr_of_mut!((*dst).offer_entry_state),
                storage.offer_entry_slots,
                capacity.max_offer_entries,
            );
            core::ptr::addr_of_mut!((*dst).global_frontier_scratch_state)
                .write(FrontierScratchState::Uninitialized);
        }
    }

    #[inline]
    pub(super) fn root_frontier_len(&self) -> usize {
        self.root_frontier_state.len()
    }

    #[inline]
    pub(super) fn root_frontier_slot(&self, root: ScopeId) -> Option<usize> {
        let len = self.root_frontier_len();
        let mut slot_idx = 0usize;
        while slot_idx < len {
            let slot = self.root_frontier_state[slot_idx];
            if slot.root == root {
                return Some(slot_idx);
            }
            slot_idx += 1;
        }
        None
    }

    #[inline]
    pub(super) fn root_frontier_active_mask(&self, root: ScopeId) -> u8 {
        match self.root_frontier_slot(root) {
            Some(slot) => self
                .root_frontier_state
                .active_entry_set(slot)
                .occupancy_mask(),
            None => 0,
        }
    }

    #[inline]
    pub(super) fn root_frontier_active_entries(&self, root: ScopeId) -> ActiveEntrySet {
        match self.root_frontier_slot(root) {
            Some(slot) => self.root_frontier_state.active_entry_set(slot),
            None => ActiveEntrySet::EMPTY,
        }
    }

    #[inline]
    pub(super) fn offer_entry_state_mut(
        &mut self,
        entry_idx: usize,
    ) -> Option<&mut OfferEntryState> {
        if !self.offer_entry_state.has_storage() {
            return None;
        }
        self.offer_entry_state.get_mut(entry_idx)
    }

    #[inline]
    pub(super) fn set_offer_entry_state(&mut self, entry_idx: usize, state: OfferEntryState) {
        self.offer_entry_state.set(entry_idx, state);
    }

    #[inline]
    pub(super) fn clear_offer_entry_state(&mut self, entry_idx: usize) {
        self.set_offer_entry_state(entry_idx, OfferEntryState::EMPTY);
    }

    pub(super) fn remove_root_frontier_slot(&mut self, slot_idx: usize) {
        self.root_frontier_state.remove_root_row(slot_idx);
    }

    #[inline]
    pub(super) fn attach_offer_entry_to_root_frontier(
        &mut self,
        entry_idx: usize,
        root: ScopeId,
        lane_idx: u8,
    ) {
        if root.is_none() {
            return;
        }
        let Some(slot_idx) = self.root_frontier_slot(root) else {
            crate::invariant();
        };
        if !self
            .root_frontier_state
            .insert_root_active_entry(slot_idx, entry_idx, lane_idx)
        {
            crate::invariant();
        }
    }

    #[inline]
    pub(super) fn detach_offer_entry_from_root_frontier(
        &mut self,
        entry_idx: usize,
        root: ScopeId,
    ) {
        if root.is_none() {
            return;
        }
        let Some(slot_idx) = self.root_frontier_slot(root) else {
            crate::invariant();
        };
        if !self
            .root_frontier_state
            .remove_root_active_entry(slot_idx, entry_idx)
        {
            crate::invariant();
        }
    }

    pub(super) fn detach_lane_from_root_frontier(&mut self, info: LaneOfferState) {
        let root = info.parallel_root;
        if root.is_none() {
            return;
        }
        let Some(slot_idx) = self.root_frontier_slot(root) else {
            return;
        };
        if self.root_frontier_state.active_entry_set(slot_idx).len() == 0 {
            self.remove_root_frontier_slot(slot_idx);
        }
    }

    pub(super) fn attach_lane_to_root_frontier(&mut self, info: LaneOfferState) {
        let root = info.parallel_root;
        if root.is_none() {
            return;
        }
        if self.root_frontier_slot(root).is_none() {
            let slot_idx = self.root_frontier_len();
            if slot_idx >= self.root_frontier_state.capacity() {
                crate::invariant();
            }
            self.root_frontier_state.prepare_row(slot_idx, root);
        }
    }
}

#[cfg(all(test, hibana_repo_tests))]
#[path = "frontier_state/tests.rs"]
mod tests;