vj-sim 0.3.0

//! Window aliases: a ref port (IEEE 1800-2023 23.3.3.2) bound to a *select*
//! of a variable -- a member of an unpacked struct, an element of an unpacked
//! array, or a nesting of the two (13.5.2 allows nothing else to be passed by
//! reference) -- names a sub-range of the target's storage, not a whole
//! slot.
//!
//! A windowed alias owns no storage. Its *view cell* is a [`StateCellId`]
//! whose value is always derived from the target's cell (the *root*): a read
//! extracts the window out of the root's value, a write splices the new bits
//! into the root and commits the root. Processes wait on a view cell exactly
//! as on any other cell, so an `@(r)` in the child wakes on a change of the
//! window and never on a change of the rest of the root.
//!
//! Every write that changes a root (whichever name it was written through)
//! reports, besides its own notification, one [`AliasChange`] per overlapping
//! window plus -- when the write was made through a view -- one for the root
//! itself; the scheduler drains those after each commit
//! (`SignalAccess::take_alias_changes`) and notifies the cells through its
//! ordinary notification path.

use std::cell::{Cell, RefCell};
use std::collections::HashMap;

use super::write::{ChangeResult, four_state_changed};
use super::{FourStateValue, StateCellId};

/// A sub-range of a root cell: `width` bits from bit `lo`, of memory row
/// `row` when the root is a memory (an unpacked array's element).
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct AliasWindow {
    pub row: Option<u64>,
    pub lo: u32,
    pub width: u32,
}

/// What a view cell stands for.
#[derive(Clone, Copy, Debug)]
pub(crate) struct ViewInfo {
    pub root: StateCellId,
    pub window: AliasWindow,
}

/// A change of a cell the scheduler has to announce because the write that
/// caused it was made through a *different* name for the same storage.
#[derive(Clone, Debug)]
pub struct AliasChange {
    pub cell: StateCellId,
    pub old: FourStateValue,
    pub new: FourStateValue,
    /// The cell is a whole memory (no meaningful edge).
    pub no_edge: bool,
}

/// All view cells of one engine.
#[derive(Default)]
pub(crate) struct ViewTable {
    by_view: HashMap<StateCellId, ViewInfo>,
    by_key: HashMap<(StateCellId, AliasWindow), StateCellId>,
    of_root: HashMap<StateCellId, Vec<StateCellId>>,
    pending: Vec<AliasChange>,
    /// The view a write in flight was made through.
    writing: Option<StateCellId>,
}

impl ViewTable {
    pub(crate) fn existing(&self, root: StateCellId, window: AliasWindow) -> Option<StateCellId> {
        self.by_key.get(&(root, window)).copied()
    }

    pub(crate) fn register(&mut self, view: StateCellId, root: StateCellId, window: AliasWindow) {
        self.by_view.insert(view, ViewInfo { root, window });
        self.by_key.insert((root, window), view);
        self.of_root.entry(root).or_default().push(view);
    }

    pub(crate) fn info(&self, cell: StateCellId) -> Option<ViewInfo> {
        self.by_view.get(&cell).copied()
    }

    pub(crate) fn begin_write(&mut self, view: StateCellId) {
        self.writing = Some(view);
    }

    pub(crate) fn end_write(&mut self) {
        self.writing = None;
    }

    pub(crate) fn take_pending(&mut self) -> Vec<AliasChange> {
        std::mem::take(&mut self.pending)
    }

    /// Records the consequences of `result`, a committed change of `root`
    /// (row `row` of it, for a memory).
    fn note(&mut self, root: StateCellId, row: Option<u64>, result: &ChangeResult) {
        let ViewTable {
            by_view,
            of_root,
            pending,
            writing,
            ..
        } = self;
        if writing.is_some() {
            pending.push(AliasChange {
                cell: root,
                old: result.old.clone(),
                new: result.new.clone(),
                no_edge: row.is_some(),
            });
        }
        let Some(views) = of_root.get(&root) else {
            return;
        };
        for &view in views {
            if Some(view) == *writing {
                continue;
            }
            let info = &by_view[&view];
            if info.window.row != row {
                continue;
            }
            let old = window_value(&result.old, info.window);
            let new = window_value(&result.new, info.window);
            if four_state_changed(&old, &new) {
                pending.push(AliasChange {
                    cell: view,
                    old,
                    new,
                    no_edge: false,
                });
            }
        }
    }
}

/// The engine-wide handle on the table, with a one-load fast path for the
/// (usual) design that has no window alias at all.
#[derive(Default)]
pub(crate) struct Views {
    any: Cell<bool>,
    table: RefCell<ViewTable>,
}

impl Views {
    pub(crate) fn table(&self) -> std::cell::RefMut<'_, ViewTable> {
        self.table.borrow_mut()
    }

    pub(crate) fn mark_any(&self) {
        self.any.set(true);
    }

    pub(crate) fn info(&self, cell: StateCellId) -> Option<ViewInfo> {
        if !self.any.get() {
            return None;
        }
        self.table.borrow().info(cell)
    }

    #[inline]
    pub(crate) fn note_change(&self, root: StateCellId, row: Option<u64>, result: &ChangeResult) {
        if self.any.get() && result.changed {
            self.table.borrow_mut().note(root, row, result);
        }
    }

    pub(crate) fn take_pending(&self) -> Vec<AliasChange> {
        if !self.any.get() {
            return Vec::new();
        }
        self.table.borrow_mut().take_pending()
    }
}

/// `(value plane, unknown plane)` of `v`: `val` is the value bit, `unk` the
/// unknown bit (x is `val=0, unk=1`; z is `val=1, unk=1`).
fn planes(v: &FourStateValue) -> (Vec<u64>, Vec<u64>) {
    match v {
        FourStateValue::Narrow(n) => (vec![*n as u64], vec![(*n >> 64) as u64]),
        FourStateValue::Wide { aval, bval } => (
            aval.iter().zip(bval).map(|(a, b)| a ^ b).collect(),
            bval.clone(),
        ),
    }
}

fn extract_bits(src: &[u64], lo: u32, width: u32) -> Vec<u64> {
    let n = width.div_ceil(64) as usize;
    let mut out = Vec::with_capacity(n);
    for i in 0..n {
        let bit = lo as usize + 64 * i;
        let (wi, sh) = (bit / 64, (bit % 64) as u32);
        let mut w = src.get(wi).copied().unwrap_or(0) >> sh;
        if sh != 0 {
            w |= src.get(wi + 1).copied().unwrap_or(0) << (64 - sh);
        }
        out.push(w);
    }
    if !width.is_multiple_of(64)
        && let Some(last) = out.last_mut()
    {
        *last &= (1u64 << (width % 64)) - 1;
    }
    out
}

fn insert_bits(dst: &mut [u64], lo: u32, width: u32, src: &[u64]) {
    let n = width.div_ceil(64) as usize;
    for i in 0..n {
        let chunk = (width as usize - 64 * i).min(64) as u32;
        let m = if chunk == 64 {
            u64::MAX
        } else {
            (1u64 << chunk) - 1
        };
        let v = src.get(i).copied().unwrap_or(0) & m;
        let bit = lo as usize + 64 * i;
        let (wi, sh) = (bit / 64, (bit % 64) as u32);
        dst[wi] = (dst[wi] & !(m << sh)) | (v << sh);
        if sh != 0 && sh + chunk > 64 {
            dst[wi + 1] = (dst[wi + 1] & !(m >> (64 - sh))) | (v >> (64 - sh));
        }
    }
}

/// The value of `window` within `root`: `Narrow` up to 64 bits, `Wide`
/// beyond, as the storage class of a slot of that width is.
pub fn window_value(root: &FourStateValue, window: AliasWindow) -> FourStateValue {
    let (val, unk) = planes(root);
    let val = extract_bits(&val, window.lo, window.width);
    let unk = extract_bits(&unk, window.lo, window.width);
    if window.width <= 64 {
        FourStateValue::Narrow(u128::from(val[0]) | (u128::from(unk[0]) << 64))
    } else {
        FourStateValue::Wide {
            aval: val.iter().zip(&unk).map(|(v, u)| v ^ u).collect(),
            bval: unk,
        }
    }
}

/// `root` with `window` replaced by `new` (in `root`'s own representation).
pub fn splice_window(
    root: &FourStateValue,
    window: AliasWindow,
    new: &FourStateValue,
) -> FourStateValue {
    let (mut val, mut unk) = planes(root);
    let (nv, nu) = planes(new);
    insert_bits(&mut val, window.lo, window.width, &nv);
    insert_bits(&mut unk, window.lo, window.width, &nu);
    match root {
        FourStateValue::Narrow(_) => {
            FourStateValue::Narrow(u128::from(val[0]) | (u128::from(unk[0]) << 64))
        }
        FourStateValue::Wide { .. } => FourStateValue::Wide {
            aval: val.iter().zip(&unk).map(|(v, u)| v ^ u).collect(),
            bval: unk,
        },
    }
}

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

    fn w(row: Option<u64>, lo: u32, width: u32) -> AliasWindow {
        AliasWindow { row, lo, width }
    }

    #[test]
    fn narrow_window_round_trips() {
        let root = FourStateValue::Narrow(0x00AB_CDEF);
        let win = w(None, 8, 8);
        match window_value(&root, win) {
            FourStateValue::Narrow(v) => assert_eq!(v, 0xCD),
            other => panic!("{other:?}"),
        }
        match splice_window(&root, win, &FourStateValue::Narrow(0x12)) {
            FourStateValue::Narrow(v) => assert_eq!(v, 0x00AB_12EF),
            other => panic!("{other:?}"),
        }
    }

    #[test]
    fn unknown_bits_travel_with_the_window() {
        // bits 4..8 are x (val=0, unk=1)
        let root = FourStateValue::Narrow(0x0000_0000_0000_0005 | (0xF0u128 << 64));
        let win = w(None, 4, 4);
        match window_value(&root, win) {
            FourStateValue::Narrow(v) => assert_eq!(v, 0xF_u128 << 64),
            other => panic!("{other:?}"),
        }
    }

    #[test]
    fn wide_window_straddling_a_word_boundary() {
        // 128-bit root, aval/bval planes, all value bits 1 (no unknowns).
        let root = FourStateValue::Wide {
            aval: vec![u64::MAX, u64::MAX],
            bval: vec![0, 0],
        };
        let win = w(None, 60, 8);
        match window_value(&root, win) {
            FourStateValue::Narrow(v) => assert_eq!(v, 0xFF),
            other => panic!("{other:?}"),
        }
        let cleared = splice_window(&root, win, &FourStateValue::Narrow(0));
        match cleared {
            FourStateValue::Wide { aval, bval } => {
                assert_eq!(aval, vec![0x0FFF_FFFF_FFFF_FFFF, 0xFFFF_FFFF_FFFF_FFF0]);
                assert_eq!(bval, vec![0, 0]);
            }
            other => panic!("{other:?}"),
        }
    }

    #[test]
    fn window_wider_than_a_word_is_wide() {
        let root = FourStateValue::Wide {
            aval: vec![0x1111, 0x2222, 0x3333],
            bval: vec![0, 0, 0],
        };
        match window_value(&root, w(None, 64, 100)) {
            FourStateValue::Wide { aval, bval } => {
                assert_eq!(aval, vec![0x2222, 0x3333 & 0xF_FFFF_FFFF]);
                assert_eq!(bval, vec![0, 0]);
            }
            other => panic!("{other:?}"),
        }
    }
}