sva-engine 0.8.0

// Concern: a graph's values, each in a slot while held, with its memory place, holds and where its moves end | Non-concern: what a value holds (value.rs), when one goes (mod.rs) | IO: (Value) -> slot
use std::collections::{BTreeMap, HashMap, HashSet};
use std::ops::{Index, IndexMut};

use super::store::Place;
use super::value::{Key, Value};

/// A value keeps its slot until let go; one made later comes later.
#[derive(Default)]
pub(crate) struct Values {
    slots: Vec<Option<Slot>>,
    free: Vec<usize>,
    order: BTreeMap<u64, usize>,
    next: u64,
    index: HashMap<Key, usize>,
}

struct Slot {
    seq: u64,
    value: Option<Value>,
    place: Place,
    held: u32,
}

impl Values {
    pub(crate) fn span(&self) -> usize {
        self.slots.len()
    }

    pub(crate) fn of(&self, key: &Key) -> Option<usize> {
        self.index.get(key).copied()
    }

    /// `value` in a slot of its own, holding what it reads, held by nothing yet.
    pub(crate) fn push(&mut self, value: Value, place: Place) -> usize {
        for at in value.reads.clone() {
            self.slot_mut(at).held += 1;
        }
        let seq = self.next;
        self.next += 1;
        let key = value.key;
        let slot = Some(Slot {
            seq,
            value: Some(value),
            place,
            held: 0,
        });
        let at = match self.free.pop() {
            Some(at) => {
                self.slots[at] = slot;
                at
            }
            None => {
                self.slots.push(slot);
                self.slots.len() - 1
            }
        };
        self.order.insert(seq, at);
        self.index.insert(key, at);
        at
    }

    /// The value at `at` let go, once nothing holds it.
    pub(crate) fn remove(&mut self, at: usize) -> Value {
        let slot = self.slots[at].take().expect("a held value");
        self.order.remove(&slot.seq);
        self.free.push(at);
        let value = slot.value.expect("a value in its slot");
        if self.index.get(&value.key) == Some(&at) {
            self.index.remove(&value.key);
        }
        value
    }

    pub(crate) fn holds(&self, at: usize) -> bool {
        self.slots.get(at).is_some_and(Option::is_some)
    }

    pub(crate) fn hold(&mut self, at: usize) {
        self.slot_mut(at).held += 1;
    }

    /// `at` held once less; whether nothing holds it now.
    pub(crate) fn release(&mut self, at: usize) -> bool {
        let slot = self.slot_mut(at);
        slot.held -= 1;
        slot.held == 0
    }

    pub(crate) fn held(&self, at: usize) -> bool {
        self.slot(at).held > 0
    }

    /// Each value that only moves another, mapped to the value at the end of what it moves
    /// and the shift to it: one fold in order, readers after what they read.
    pub(crate) fn feet(&self) -> HashMap<usize, (usize, i64)> {
        let mut feet: HashMap<usize, (usize, i64)> = HashMap::new();
        for at in self.ordered() {
            if let Some((read, by)) = self[at].moves() {
                let foot = feet
                    .get(&read)
                    .map_or((read, by), |(foot, more)| (*foot, by + more));
                feet.insert(at, foot);
            }
        }
        feet
    }

    /// `at` and each value reading it, in their order, after every value made so far.
    pub(crate) fn behind(&mut self, at: usize) {
        let from = self.slot(at).seq;
        let later: Vec<usize> = self.order.range(from..).map(|(_, a)| *a).collect();
        let mut moved = HashSet::new();
        for a in later {
            if a != at && !self[a].reads.iter().any(|r| moved.contains(r)) {
                continue;
            }
            moved.insert(a);
            let slot = self.slots[a].as_mut().expect("a held value");
            self.order.remove(&slot.seq);
            slot.seq = self.next;
            self.order.insert(self.next, a);
            self.next += 1;
        }
    }

    pub(crate) fn seq(&self, at: usize) -> u64 {
        self.slot(at).seq
    }

    pub(crate) fn ordered(&self) -> impl DoubleEndedIterator<Item = usize> + '_ {
        self.order.values().copied()
    }

    pub(crate) fn iter(&self) -> impl Iterator<Item = (usize, &Value)> {
        self.ordered().map(|at| (at, &self[at]))
    }

    pub(crate) fn place(&self, at: usize) -> &Place {
        &self.slot(at).place
    }

    pub(crate) fn place_mut(&mut self, at: usize) -> &mut Place {
        &mut self.slot_mut(at).place
    }

    pub(crate) fn placed(&mut self, at: usize) -> (&mut Value, &mut Place) {
        let slot = self.slot_mut(at);
        let value = slot.value.as_mut().expect("a value in its slot");
        (value, &mut slot.place)
    }

    /// The value at `at`, out until `put` back.
    pub(crate) fn lift(&mut self, at: usize) -> Value {
        self.slot_mut(at).value.take().expect("a value in its slot")
    }

    pub(crate) fn put(&mut self, at: usize, value: Value) {
        self.slot_mut(at).value = Some(value);
    }

    fn slot(&self, at: usize) -> &Slot {
        self.slots[at].as_ref().expect("a held value")
    }

    fn slot_mut(&mut self, at: usize) -> &mut Slot {
        self.slots[at].as_mut().expect("a held value")
    }
}

impl Index<usize> for Values {
    type Output = Value;

    fn index(&self, at: usize) -> &Value {
        self.slot(at).value.as_ref().expect("a value in its slot")
    }
}

impl IndexMut<usize> for Values {
    fn index_mut(&mut self, at: usize) -> &mut Value {
        self.slot_mut(at)
            .value
            .as_mut()
            .expect("a value in its slot")
    }
}