sv_sim_sim/

collections.rs

//! SV queues, dynamic arrays and associative arrays (LRM 1800-2023 §7.5,
//! §7.8, §7.10): variable-size collections held outside STATE.
//!
//! A collection is stored -- in STATE, a frame slot, or a register -- as a
//! 64-bit handle: an entry index in the low 32 bits and the entry's version
//! in the high 32. Handle 0 is an empty collection with no entry. Every
//! operation that changes a collection returns its new handle, which the
//! caller stores back: the version changes with each change, so the store
//! is a value change other processes see (`wait (q.size() != 0)`).
//!
//! An entry's contents are shared copy-on-write: [`clone`] (an
//! assignment `b = a`) makes a new entry sharing the data, and the first
//! change to either copies it. [`release`] frees an entry whose handle
//! is being overwritten.
//!
//! An element is the stored bits of its value -- codegen's packed
//! `(unk << W) | val` form, as `elem_words` little-endian words -- so the
//! store is independent of element types. Associative array keys are
//! integers of up to 127 bits (ordered as signed or unsigned numbers), wider
//! integers (unsigned), or strings (ordered lexicographically, §7.8.1).

use std::collections::{BTreeMap, VecDeque};
use std::ops::Bound;
use std::sync::{Arc, Mutex, OnceLock};

/// An associative array key.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Key {
    Int(i128),
    /// Wider than 127 bits: the value's words, most significant first.
    Big(Vec<u64>),
    Str(Vec<u8>),
}

#[derive(Clone, Debug)]
enum Data {
    /// A queue or dynamic array: `len * stride` words, element 0 first.
    Seq { stride: usize, words: VecDeque<u64> },
    /// An associative array, and the value a missing key reads when it has
    /// a `default:` (LRM 1800-2023 §7.9.11).
    Map(BTreeMap<Key, Box<[u64]>>, Option<Box<[u64]>>),
}

impl Data {
    fn len(&self) -> usize {
        match self {
            Data::Seq { stride, words } => words.len() / (*stride).max(1),
            Data::Map(m, _) => m.len(),
        }
    }
}

/// A collection's contents, and -- when its elements are class handles
/// (`objs`; the handle is word 0 of each element) -- the references it holds
/// on those objects (LRM 1800-2023 §8.29: an object lives while any handle
/// names it, and a collection element is a handle).
///
/// Every handle element owns one `objects` reference: cloning the contents
/// (copy-on-write's unshare, a frozen constant's first change) retains each
/// in the copy, and dropping them releases each. An operation that adds an
/// element TAKES the caller's reference (the caller passes an owned value);
/// one that removes an element releases it, except [`pop`], which hands it to
/// its caller.
///
/// An associative array indexed by a class handle ([`KeyKind::Obj`],
/// `key_objs`) owns a reference on each KEY object the same way: a key
/// inserted by [`store`] is retained (the caller keeps its own reference; the
/// key it passes is borrowed), and removing the key releases it.
struct Held {
    data: Data,
    objs: bool,
    key_objs: bool,
}

impl Held {
    /// Calls `f` with the handle word of every element, and (when
    /// `with_default`) a map's `default:` value.
    fn each_handle(&self, with_default: bool, mut f: impl FnMut(u64)) {
        if !self.objs {
            return;
        }
        match &self.data {
            Data::Seq { stride, words } => {
                words.iter().step_by((*stride).max(1)).for_each(|&w| f(w))
            }
            Data::Map(m, dflt) => {
                m.values()
                    .chain(dflt.iter().filter(|_| with_default))
                    .filter_map(|v| v.first().copied())
                    .for_each(f);
            }
        }
    }

    /// Calls `f` with every key of a class-handle-keyed map.
    fn each_key(&self, mut f: impl FnMut(u64)) {
        if !self.key_objs {
            return;
        }
        if let Data::Map(m, _) = &self.data {
            for k in m.keys() {
                if let Key::Int(v) = k {
                    f(*v as u64);
                }
            }
        }
    }

    /// Releases every element's reference (before the elements are removed
    /// wholesale; a map's `default:` stays, with its reference).
    fn release_elements(&self) {
        self.each_handle(false, crate::objects::release);
    }
}

impl Clone for Held {
    fn clone(&self) -> Held {
        self.each_handle(true, crate::objects::retain);
        self.each_key(crate::objects::retain);
        Held {
            data: self.data.clone(),
            objs: self.objs,
            key_objs: self.key_objs,
        }
    }
}

impl Drop for Held {
    fn drop(&mut self) {
        self.each_handle(true, crate::objects::release);
        self.each_key(crate::objects::release);
    }
}

struct Entry {
    version: u32,
    data: Arc<Held>,
    /// The key at `pos` of the last [`key_at`], for sequential walks.
    cursor: Option<(usize, Key)>,
    /// A constant (a declaration's initial value, shared by every instance
    /// of its module): never changed in place -- a change makes a new
    /// entry -- nor freed.
    frozen: bool,
}

#[derive(Default)]
struct Table {
    /// Index 0 is unused (handle 0 is the empty collection).
    entries: Vec<Option<Entry>>,
    /// Each slot's last version, so a reused slot never repeats a handle.
    versions: Vec<u32>,
    free: Vec<u32>,
    /// The element references open right now ([`ref_open`]); slot `k` is id
    /// `k + 1`. Empty (and every hook below a no-op) unless a design passes
    /// a queue or dynamic-array element by `ref`.
    refs: Vec<Option<ElemRef>>,
    free_refs: Vec<u32>,
    n_refs: usize,
}

/// An open `ref` to element `index` of the collection in entry `entry`
/// (LRM 1800-2023 13.5.2, 7.10.3). The structural operations keep `index`
/// naming the same element; an operation that removes the element or the
/// whole contents makes the reference outdated (`live == false`): the record
/// stays until [`ref_close`] so its id is never reused under the callee.
#[derive(Clone)]
struct ElemRef {
    entry: usize,
    index: i64,
    /// An associative array's element is named by its key (LRM 7.8); the
    /// element need not exist yet (a reference to an absent key reads the
    /// array's default and its first write creates the element).
    key: Option<Key>,
    live: bool,
}

fn table() -> &'static Mutex<Table> {
    static T: OnceLock<Mutex<Table>> = OnceLock::new();
    T.get_or_init(|| {
        Mutex::new(Table {
            entries: vec![None],
            versions: vec![0],
            free: Vec::new(),
            refs: Vec::new(),
            free_refs: Vec::new(),
            n_refs: 0,
        })
    })
}

fn index(h: u64) -> usize {
    (h & 0xffff_ffff) as usize
}

impl Table {
    fn held(&self, h: u64) -> Option<&Held> {
        self.entries.get(index(h))?.as_ref().map(|e| &*e.data)
    }

    fn data(&self, h: u64) -> Option<&Data> {
        self.held(h).map(|e| &e.data)
    }

    fn alloc(&mut self, data: Held) -> u64 {
        let i = match self.free.pop() {
            Some(i) => i as usize,
            None => {
                self.entries.push(None);
                self.versions.push(0);
                self.entries.len() - 1
            }
        };
        let version = self.versions[i].wrapping_add(1);
        self.versions[i] = version;
        self.entries[i] = Some(Entry {
            version,
            data: Arc::new(data),
            cursor: None,
            frozen: false,
        });
        (u64::from(version) << 32) | i as u64
    }

    /// Frees `h`'s entry -- only if `h` is that entry's *current* handle: a
    /// stale handle (the slot since freed and reused, or the entry changed
    /// in place) must not free the slot's new owner.
    fn release(&mut self, h: u64) {
        let i = index(h);
        if i != 0
            && self.entries.get(i).is_some_and(|e| {
                e.as_ref()
                    .is_some_and(|e| !e.frozen && u64::from(e.version) == h >> 32)
            })
        {
            self.refs_outdated(i, 0);
            self.entries[i] = None;
            self.free.push(i as u32);
        }
    }

    /// Every open reference into entry `entry` whose element is at or after
    /// `from` is outdated (the elements were removed or the entry freed).
    fn refs_outdated(&mut self, entry: usize, from: i64) {
        if self.n_refs == 0 {
            return;
        }
        for r in self.refs.iter_mut().flatten() {
            if r.live && r.entry == entry && r.index >= from {
                r.live = false;
            }
        }
    }

    /// Key `key` of the associative array `entry` was deleted: references to
    /// that element are outdated (LRM 1800-2023 13.5.2); inserting other keys
    /// never outdates one.
    fn refs_key_removed(&mut self, entry: usize, key: &Key) {
        if self.n_refs == 0 {
            return;
        }
        for r in self.refs.iter_mut().flatten() {
            if r.live && r.entry == entry && r.key.as_ref() == Some(key) {
                r.live = false;
            }
        }
    }

    /// Element `i` of `entry` was removed: its references are outdated, those
    /// of later elements move down one (LRM 1800-2023 7.10.3).
    fn refs_removed(&mut self, entry: usize, i: i64) {
        if self.n_refs == 0 {
            return;
        }
        for rr in self.refs.iter_mut().flatten() {
            if !rr.live || rr.entry != entry || rr.index < i {
                continue;
            }
            if rr.index == i {
                rr.live = false;
            } else {
                rr.index -= 1;
            }
        }
    }

    /// An element was inserted before position `i` of `entry`: later
    /// elements' references follow them up one (an insert never outdates).
    fn refs_inserted(&mut self, entry: usize, i: i64) {
        if self.n_refs == 0 {
            return;
        }
        for r in self.refs.iter_mut().flatten() {
            if r.live && r.entry == entry && r.index >= i {
                r.index += 1;
            }
        }
    }

    /// The contents of entry `from` moved to entry `to` (a constant's first
    /// change makes a new entry): its references follow.
    fn refs_moved(&mut self, from: usize, to: usize) {
        if self.n_refs == 0 {
            return;
        }
        for r in self.refs.iter_mut().flatten() {
            if r.live && r.entry == from {
                r.entry = to;
            }
        }
    }

    /// Changes `h`'s data with `f` (allocating an entry for the empty
    /// handle, `empty` giving its initial data) and returns its new handle.
    fn modify(&mut self, h: u64, empty: impl FnOnce() -> Held, f: impl FnOnce(&mut Held)) -> u64 {
        let i = index(h);
        match self.entries.get_mut(i).and_then(|e| e.as_mut()) {
            Some(e) if e.frozen => {
                let mut d = (*e.data).clone();
                f(&mut d);
                let new = self.alloc(d);
                self.refs_moved(i, index(new));
                new
            }
            Some(e) if i != 0 => {
                f(Arc::make_mut(&mut e.data));
                e.version = e.version.wrapping_add(1);
                e.cursor = None;
                self.versions[i] = e.version;
                (u64::from(e.version) << 32) | i as u64
            }
            _ => {
                let mut d = empty();
                f(&mut d);
                self.alloc(d)
            }
        }
    }
}

/// What an operation works on: element size, and for an associative
/// array, its key type.
#[derive(Clone, Copy, Debug)]
pub struct Shape {
    pub elem_words: usize,
    pub assoc: bool,
    pub key: KeyKind,
    /// The elements are class handles (word 0 of each): the collection owns
    /// a reference on each object (see [`Held`]).
    pub obj: bool,
}

/// An associative array's key type.
#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub enum KeyKind {
    /// An integral key of `width` bits.
    Int {
        width: u32,
        signed: bool,
    },
    Str,
    /// A class handle (LRM 1800-2023 §7.8.3, §8.29): compared as a 64-bit
    /// unsigned number; the array owns a reference on each key's object.
    Obj,
}

impl Shape {
    fn empty(&self) -> Held {
        self.held(if self.assoc {
            Data::Map(BTreeMap::new(), None)
        } else {
            Data::Seq {
                stride: self.elem_words.max(1),
                words: VecDeque::new(),
            }
        })
    }

    fn held(&self, data: Data) -> Held {
        Held {
            data,
            objs: self.obj,
            key_objs: self.key == KeyKind::Obj,
        }
    }

    /// Gives up the reference an operation that did not store `val` was
    /// handed on its element (the operation was a no-op: an out-of-range
    /// write, an invalid key).
    pub fn discard(&self, val: &[u64]) {
        if self.obj
            && let Some(&w) = val.first()
        {
            crate::objects::release(w);
        }
    }

    /// The words of a packed key value (`(unk << width) | val`): `None` if
    /// any bit is unknown (such a key is invalid, §7.8.6).
    pub fn key_from_bits(&self, bits: &[u64]) -> Option<Key> {
        match self.key {
            KeyKind::Str => Some(Key::Str(crate::strings::bytes(bits[0]).to_vec())),
            KeyKind::Int { .. } | KeyKind::Obj => {
                let (width, signed) = if let KeyKind::Int { width, signed } = self.key {
                    (width, signed)
                } else {
                    // An object handle key: a 64-bit unsigned value.
                    (64, false)
                };
                let w = width as usize;
                let bit = |i: usize| (bits.get(i / 64).copied().unwrap_or(0) >> (i % 64)) & 1;
                if (w..2 * w).any(|i| bit(i) != 0) {
                    return None;
                }
                if w <= 127 {
                    let mut v: i128 = 0;
                    for i in 0..w {
                        v |= (bit(i) as i128) << i;
                    }
                    if signed && w > 0 && bit(w - 1) == 1 {
                        v -= 1i128 << w;
                    }
                    Some(Key::Int(v))
                } else {
                    let n = w.div_ceil(64);
                    let mut words = vec![0u64; n];
                    for i in 0..w {
                        words[i / 64] |= bit(i) << (i % 64);
                    }
                    words.reverse();
                    Some(Key::Big(words))
                }
            }
        }
    }

    /// `key` as packed bits into `out` (a string key as its interned id).
    pub fn key_to_bits(&self, key: &Key, out: &mut [u64]) {
        out.fill(0);
        match key {
            Key::Str(s) => out[0] = crate::strings::intern(s),
            Key::Int(v) => {
                let width = match self.key {
                    KeyKind::Int { width, .. } => width,
                    KeyKind::Obj => 64,
                    KeyKind::Str => return,
                };
                for i in 0..width as usize {
                    if (v >> i.min(127)) & 1 == 1 {
                        out[i / 64] |= 1 << (i % 64);
                    }
                }
            }
            Key::Big(words) => {
                for (i, w) in words.iter().rev().enumerate() {
                    if let Some(o) = out.get_mut(i) {
                        *o = *w;
                    }
                }
            }
        }
    }
}

/// The number of elements.
pub fn size(h: u64) -> usize {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.data(h).map_or(0, |d| d.len())
}

/// Element `i` of a queue or dynamic array into `out`: `false` (leaving
/// `out` alone) when out of range.
pub fn get(h: u64, i: i64, out: &mut [u64]) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(Data::Seq { stride, words }) = t.data(h) else {
        return false;
    };
    let n = words.len() / stride;
    if i < 0 || i as usize >= n {
        return false;
    }
    let base = i as usize * stride;
    for (k, o) in out.iter_mut().enumerate().take(*stride) {
        *o = words[base + k];
    }
    true
}

/// The value at `key` of an associative array into `out`: `false` when
/// absent.
pub fn lookup(h: u64, key: &Key, out: &mut [u64]) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(Data::Map(m, dflt)) = t.data(h) else {
        return false;
    };
    match m.get(key).or(dflt.as_ref()) {
        Some(v) => {
            let n = out.len().min(v.len());
            out[..n].copy_from_slice(&v[..n]);
            true
        }
        None => false,
    }
}

/// Whether an associative array has `key`.
pub fn exists(h: u64, key: &Key) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    matches!(t.data(h), Some(Data::Map(m, _)) if m.contains_key(key))
}

/// Writes element `i` of a queue or dynamic array; `i == size` of a queue
/// appends (`q[$+1] = v`, §7.10.1). Any other out-of-range write is
/// ignored and returns `h` unchanged.
///
/// Object elements: the collection takes `val`'s reference and releases the
/// element it overwrites; an ignored write releases `val`.
pub fn set(shape: &Shape, h: u64, i: i64, val: &[u64], queue: bool) -> u64 {
    let n = size(h) as i64;
    if i < 0 || i > n || (i == n && !queue) {
        shape.discard(val);
        return h;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held { data, objs, .. } = d;
            if let Data::Seq { stride, words } = data {
                let base = i as usize * *stride;
                if base == words.len() {
                    words.extend(val.iter().copied().take(*stride));
                    words.resize(base + *stride, 0);
                } else {
                    if *objs {
                        crate::objects::release(words[base]);
                    }
                    for k in 0..*stride {
                        words[base + k] = val.get(k).copied().unwrap_or(0);
                    }
                }
            }
        },
    )
}

/// Writes (or creates) `key` of an associative array (object values: the
/// collection takes `val`'s reference and releases the value it replaces).
pub fn store(shape: &Shape, h: u64, key: Key, val: &[u64]) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let v: Box<[u64]> = val[..shape.elem_words.min(val.len())].into();
    t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held {
                data,
                objs,
                key_objs,
            } = d;
            if let Data::Map(m, _) = data {
                // A new key of a handle-keyed map takes its own reference.
                if *key_objs
                    && !m.contains_key(&key)
                    && let Key::Int(k) = &key
                {
                    crate::objects::retain(*k as u64);
                }
                if let Some(old) = m.insert(key, v)
                    && *objs
                    && let Some(&w) = old.first()
                {
                    crate::objects::release(w);
                }
            }
        },
    )
}

/// Inserts `val` before element `i` (`i == size` appends); out-of-range
/// positions are ignored (§7.10.2.2; object elements: the collection takes
/// `val`'s reference, or releases it when ignored).
pub fn insert(shape: &Shape, h: u64, i: i64, val: &[u64]) -> u64 {
    let n = size(h) as i64;
    if i < 0 || i > n {
        shape.discard(val);
        return h;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            if let Data::Seq { stride, words } = &mut d.data {
                let at = i as usize * *stride;
                for k in (0..*stride).rev() {
                    words.insert(at, val.get(k).copied().unwrap_or(0));
                }
            }
        },
    );
    t.refs_inserted(index(new), i);
    new
}

/// `push_front` / `push_back`.
pub fn push(shape: &Shape, h: u64, val: &[u64], front: bool) -> u64 {
    if front {
        insert(shape, h, 0, val)
    } else {
        insert(shape, h, size(h) as i64, val)
    }
}

/// `pop_front` / `pop_back`: the element into `out` (untouched when empty)
/// and the new handle. An object element's reference moves to the caller
/// (in `out`) rather than being released.
pub fn pop(shape: &Shape, h: u64, out: &mut [u64], front: bool) -> (u64, bool) {
    let n = size(h);
    if n == 0 {
        return (h, false);
    }
    let i = if front { 0 } else { n - 1 };
    get(h, i as i64, out);
    (remove_at(shape, h, i as i64, false), true)
}

/// Drops the elements of a queue beyond its first `keep` (a bounded queue's
/// out-of-bounds elements, LRM 1800-2023 §7.10.5), warning when any go; an
/// object element is released.
pub fn truncate(shape: &Shape, h: u64, keep: usize) -> u64 {
    if size(h) <= keep {
        return h;
    }
    eprintln!(
        "Warning: bounded queue exceeded its bound; elements beyond index {} discarded",
        keep - 1
    );
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held { data, objs, .. } = d;
            if let Data::Seq { stride, words } = data {
                let at = keep * *stride;
                if *objs {
                    for w in words.iter().skip(at).step_by(*stride) {
                        crate::objects::release(*w);
                    }
                }
                words.truncate(at);
            }
        },
    );
    t.refs_outdated(index(new), keep as i64);
    new
}

/// Removes element `i` of a queue (out of range: ignored); an object element
/// is released.
pub fn delete_at(shape: &Shape, h: u64, i: i64) -> u64 {
    remove_at(shape, h, i, true)
}

/// [`delete_at`], releasing the element's object reference only when
/// `release` (a pop hands it to its caller instead).
fn remove_at(shape: &Shape, h: u64, i: i64, release: bool) -> u64 {
    let n = size(h) as i64;
    if i < 0 || i >= n {
        return h;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held { data, objs, .. } = d;
            if let Data::Seq { stride, words } = data {
                let at = i as usize * *stride;
                if release && *objs {
                    crate::objects::release(words[at]);
                }
                words.drain(at..at + *stride);
            }
        },
    );
    t.refs_removed(index(new), i);
    new
}

/// Removes `key` of an associative array (an object value is released).
pub fn delete_key(shape: &Shape, h: u64, key: &Key) -> u64 {
    if !exists(h, key) {
        return h;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held {
                data,
                objs,
                key_objs,
            } = d;
            if let Data::Map(m, _) = data
                && let Some(old) = m.remove(key)
            {
                if *key_objs && let Key::Int(k) = key {
                    crate::objects::release(*k as u64);
                }
                if *objs && let Some(&w) = old.first() {
                    crate::objects::release(w);
                }
            }
        },
    );
    t.refs_key_removed(index(new), key);
    new
}

/// Gives an associative array the value a missing key reads (`'{default:
/// v}`); an object value is owned like any element, and replaces (releasing)
/// an earlier default.
pub fn set_default(shape: &Shape, h: u64, val: &[u64]) -> u64 {
    let v: Box<[u64]> = val[..shape.elem_words.min(val.len())].into();
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.modify(
        h,
        || shape.empty(),
        |d| {
            let Held { data, objs, .. } = d;
            if let Data::Map(_, dflt) = data
                && let Some(old) = dflt.replace(v)
                && *objs
                && let Some(&w) = old.first()
            {
                crate::objects::release(w);
            }
        },
    )
}

/// Removes every element (releasing the objects they name).
pub fn clear(shape: &Shape, h: u64) -> u64 {
    if h == 0 {
        return 0;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            d.release_elements();
            d.each_key(crate::objects::release);
            match &mut d.data {
                Data::Map(m, _) => m.clear(),
                Data::Seq { words, .. } => words.clear(),
            }
        },
    );
    t.refs_outdated(index(new), 0);
    new
}

/// A new handle sharing `h`'s contents (an assignment's copy). The shared
/// contents keep their one reference per object; the first change to either
/// holder unshares them (and the copy takes its own references).
pub fn clone(h: u64) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    if t.entries
        .get(index(h))
        .and_then(|e| e.as_ref())
        .is_some_and(|e| e.frozen)
    {
        return h;
    }
    match t.entries.get(index(h)).and_then(|e| e.as_ref()) {
        Some(e) => {
            let data = Arc::clone(&e.data);
            let fresh = t.alloc(Held {
                data: Data::Map(BTreeMap::new(), None),
                objs: false,
                key_objs: false,
            });
            if let Some(e) = t.entries[index(fresh)].as_mut() {
                e.data = data;
            }
            fresh
        }
        None => 0,
    }
}

/// Where the collection handles sit inside one element of a collection whose
/// elements hold collections themselves (`int q[$][$]`, a struct with a queue
/// field, ...): the bit offset of each handle within the element's value bits
/// and the layout of the collection it names. Empty: no element holds one.
#[derive(Clone, Debug, Default, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Nest {
    pub slots: Vec<(u32, Nest)>,
}

/// The 64 bits at bit `at` of an element's words (a handle may straddle two).
fn bits64(words: &[u64], at: usize) -> u64 {
    let (w, s) = (at / 64, at % 64);
    let lo = words.get(w).copied().unwrap_or(0) >> s;
    if s == 0 {
        lo
    } else {
        lo | (words.get(w + 1).copied().unwrap_or(0) << (64 - s))
    }
}

fn set_bits64(words: &mut [u64], at: usize, v: u64) {
    let (w, s) = (at / 64, at % 64);
    if s == 0 {
        if let Some(x) = words.get_mut(w) {
            *x = v;
        }
        return;
    }
    if let Some(x) = words.get_mut(w) {
        *x = (*x & (u64::MAX >> (64 - s))) | (v << s);
    }
    if let Some(x) = words.get_mut(w + 1) {
        *x = (*x & (u64::MAX << s)) | (v >> (64 - s));
    }
}

/// Every element of `h` as owned words, with the key of an associative
/// array's (`None` for a queue's), in order; `default:` values excluded.
fn elem_list(h: u64) -> Vec<(Option<Key>, Vec<u64>)> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    match t.data(h) {
        None => Vec::new(),
        Some(Data::Seq { stride, words }) => words
            .iter()
            .copied()
            .collect::<Vec<_>>()
            .chunks((*stride).max(1))
            .map(|c| (None, c.to_vec()))
            .collect(),
        Some(Data::Map(m, _)) => m
            .iter()
            .map(|(k, v)| (Some(k.clone()), v.to_vec()))
            .collect(),
    }
}

/// [`clone`] for a collection whose elements hold collections (`nest`): the
/// copy gets a copy of every inner collection too (recursively), so later
/// changes to the original's inner collections leave it alone -- a value copy
/// (LRM 7.6), where [`clone`] alone would share the inner handles. Every
/// handle made is pushed onto `minted`, for the caller to [`release`].
pub fn clone_deep(h: u64, nest: &Nest, minted: &mut Vec<u64>) -> u64 {
    let fresh = clone(h);
    if fresh != 0 {
        minted.push(fresh);
    }
    if fresh == 0 || nest.slots.is_empty() {
        return fresh;
    }
    let mut inner: Vec<(usize, u64)> = Vec::new();
    {
        let t = table().lock().unwrap_or_else(|e| e.into_inner());
        let Some(e) = t.entries.get(index(fresh)).and_then(|e| e.as_ref()) else {
            return fresh;
        };
        if e.frozen {
            return fresh;
        }
        let mut visit = |el: &[u64]| {
            for (k, (off, _)) in nest.slots.iter().enumerate() {
                let x = bits64(el, *off as usize);
                if x != 0 {
                    inner.push((k, x));
                }
            }
        };
        match &e.data.data {
            Data::Seq { stride, words } => words
                .iter()
                .copied()
                .collect::<Vec<_>>()
                .chunks((*stride).max(1))
                .for_each(&mut visit),
            Data::Map(m, d) => m.values().chain(d.iter()).for_each(|v| visit(v)),
        }
    }
    let mut copies: std::collections::HashMap<(usize, u64), u64> = std::collections::HashMap::new();
    for (k, x) in inner {
        copies
            .entry((k, x))
            .or_insert_with(|| clone_deep(x, &nest.slots[k].1, minted));
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(e) = t.entries.get_mut(index(fresh)).and_then(|e| e.as_mut()) else {
        return fresh;
    };
    let held = Arc::make_mut(&mut e.data);
    let mut rewrite = |el: &mut [u64]| {
        for (k, (off, _)) in nest.slots.iter().enumerate() {
            let x = bits64(el, *off as usize);
            if let Some(&n) = copies.get(&(k, x)) {
                set_bits64(el, *off as usize, n);
            }
        }
    };
    match &mut held.data {
        Data::Seq { stride, words } => words
            .make_contiguous()
            .chunks_mut((*stride).max(1))
            .for_each(&mut rewrite),
        Data::Map(m, d) => m
            .values_mut()
            .map(|v| &mut v[..])
            .chain(d.iter_mut().map(|v| &mut v[..]))
            .for_each(rewrite),
    }
    fresh
}

/// [`equal`] by contents all the way down: the inner collections two
/// elements name compare by their elements, not by handle (`nest` as for
/// [`clone_deep`]).
pub fn equal_nest(a: u64, b: u64, nest: &Nest) -> bool {
    if nest.slots.is_empty() {
        return equal(a, b);
    }
    let (x, y) = (elem_list(a), elem_list(b));
    x.len() == y.len()
        && x.iter().zip(&y).all(|((ka, ea), (kb, eb))| {
            if ka != kb || ea.len() != eb.len() {
                return false;
            }
            let (mut ea, mut eb) = (ea.clone(), eb.clone());
            let mut same = true;
            for (off, sub) in &nest.slots {
                let at = *off as usize;
                same &= equal_nest(bits64(&ea, at), bits64(&eb, at), sub);
                set_bits64(&mut ea, at, 0);
                set_bits64(&mut eb, at, 0);
            }
            same && ea == eb
        })
}

/// How many collections are alive right now (a leak check for tests: the
/// count is process-global, so measure a before/after delta).
pub fn live_count() -> usize {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.entries.iter().filter(|e| e.is_some()).count()
}

/// Frees `h`'s entry (its variable is being overwritten).
pub fn release(h: u64) {
    table().lock().unwrap_or_else(|e| e.into_inner()).release(h);
}

/// Opens a reference to element `i` of the queue or dynamic array `h` (a `ref`
/// argument bound to `h[i]`, LRM 1800-2023 13.5.2) and returns its id, 0 when
/// there is no such element. The caller first makes `h` its own entry
/// ([`ref_own`]). Until [`ref_close`] the structural operations track the
/// element: a delete / pop of it, a `clear`, a resize, an assignment to the
/// whole collection outdate the reference (7.10.3, 7.5.1, 13.5.2); other
/// elements being removed or inserted move the index it names.
pub fn ref_open(h: u64, i: i64) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let e = index(h);
    let n = t.data(h).filter(|_| e != 0).map_or(0, |d| d.len() as i64);
    if i < 0 || i >= n {
        return 0;
    }
    t.ref_push(ElemRef {
        entry: e,
        index: i,
        key: None,
        live: true,
    })
}

/// [`ref_open`] for key `key` of the associative array `h` (a `ref` argument
/// bound to `h[key]`, LRM 1800-2023 13.5.2, 7.8): the element is named by
/// its key, so inserting other keys never outdates the reference and deleting
/// this key does. The key need not exist: the reference then reads the
/// array's default and its first write creates the element (7.8.6). `h` must
/// be an entry ([`ref_own`] makes the empty handle one); 0 when it is not.
pub fn ref_open_key(h: u64, key: Key) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let e = index(h);
    if e == 0 || !matches!(t.data(h), Some(Data::Map(..))) {
        return 0;
    }
    t.ref_push(ElemRef {
        entry: e,
        index: 0,
        key: Some(key),
        live: true,
    })
}

impl Table {
    fn ref_push(&mut self, rec: ElemRef) -> u64 {
        let rec = Some(rec);
        self.n_refs += 1;
        match self.free_refs.pop() {
            Some(k) => {
                self.refs[k as usize] = rec;
                u64::from(k) + 1
            }
            None => {
                self.refs.push(rec);
                self.refs.len() as u64
            }
        }
    }
}

/// Makes the collection `h` an entry of its own (a frozen constant's first
/// change would otherwise move it under an open reference); returns its
/// handle.
pub fn ref_own(shape: &Shape, h: u64) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    if h == 0 {
        // The empty associative array gets an entry a key reference can name.
        return if shape.assoc {
            t.modify(h, || shape.empty(), |_| {})
        } else {
            0
        };
    }
    if t.entries
        .get(index(h))
        .and_then(|e| e.as_ref())
        .is_some_and(|e| e.frozen)
    {
        t.modify(h, || shape.empty(), |_| {})
    } else {
        h
    }
}

fn ref_rec(t: &Table, id: u64) -> Option<ElemRef> {
    t.refs.get(id.wrapping_sub(1) as usize).cloned().flatten()
}

/// Element the open reference `id` names into `out`; `false` when `id` is 0,
/// outdated or closed (the caller keeps its own copy, which is what an
/// outdated reference's holder goes on using, 13.5.2).
pub fn ref_get(id: u64, out: &mut [u64]) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(r) = ref_rec(&t, id).filter(|r| r.live) else {
        return false;
    };
    match (&r.key, t.data(r.entry as u64)) {
        (Some(key), Some(Data::Map(m, dflt))) => match m.get(key).or(dflt.as_ref()) {
            Some(v) => {
                let n = out.len().min(v.len());
                out[..n].copy_from_slice(&v[..n]);
                true
            }
            None => false,
        },
        (None, _) => {
            drop(t);
            get(r.entry as u64, r.index, out)
        }
        _ => false,
    }
}

/// Writes `val` to the element reference `id` names, in place (the
/// collection's handle is unchanged; a key reference to an absent key creates
/// the element, LRM 7.8.6). An outdated reference writes nothing: its changes
/// are not visible outside the subroutine (LRM 13.5.2).
pub fn ref_put(id: u64, val: &[u64]) {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(r) = ref_rec(&t, id).filter(|r| r.live) else {
        return;
    };
    let Some(e) = t.entries.get_mut(r.entry).and_then(|e| e.as_mut()) else {
        return;
    };
    let held = Arc::make_mut(&mut e.data);
    let key_objs = held.key_objs;
    match (&mut held.data, r.key) {
        (Data::Seq { stride, words }, None) => {
            let base = r.index as usize * *stride;
            if base + *stride <= words.len() {
                for k in 0..*stride {
                    words[base + k] = val.get(k).copied().unwrap_or(0);
                }
                e.cursor = None;
            }
        }
        (Data::Map(m, _), Some(key)) => {
            match m.get_mut(&key) {
                Some(slot) => {
                    let n = slot.len().min(val.len());
                    slot[..n].copy_from_slice(&val[..n]);
                }
                None => {
                    if key_objs && let Key::Int(k) = &key {
                        crate::objects::retain(*k as u64);
                    }
                    m.insert(key, val.into());
                }
            }
            e.cursor = None;
        }
        _ => {}
    }
}

fn bit_at(w: &[u64], i: usize) -> bool {
    w.get(i / 64).is_some_and(|x| (x >> (i % 64)) & 1 != 0)
}

fn set_bit(w: &mut [u64], i: usize, v: bool) {
    if let Some(x) = w.get_mut(i / 64) {
        let m = 1u64 << (i % 64);
        *x = if v { *x | m } else { *x & !m };
    }
}

/// Part `[lo, lo + w)` of the `big_w`-bit element reference `id` names, into
/// `out` as a `w`-bit packed `(unk << w) | val` value (an element is
/// `(unk << big_w) | val`): a `ref` argument bound to a member / select of a
/// queue or dynamic-array element (`f(q[i].m)`, LRM 1800-2023 13.5.2).
/// `big_w == 0` names the whole element ([`ref_get`]). `false` when the
/// reference is 0, outdated or closed (`out` is then left alone).
pub fn ref_get_part(id: u64, lo: u64, w: u32, big_w: u32, out: &mut [u64]) -> bool {
    if crate::winref::is_window(id) {
        return crate::winref::get_part(id, lo, w, big_w, out);
    }
    if big_w == 0 {
        return ref_get(id, out);
    }
    let mut elem = vec![0u64; (2 * big_w as usize).div_ceil(64)];
    if !ref_get(id, &mut elem) {
        return false;
    }
    out.fill(0);
    for k in 0..w as usize {
        // A bit past the element (a select the caller flagged out of range)
        // reads as 0.
        let i = lo as usize + k;
        if i < big_w as usize {
            set_bit(out, k, bit_at(&elem, i));
            set_bit(out, w as usize + k, bit_at(&elem, big_w as usize + i));
        }
    }
    true
}

/// Writes the `w`-bit packed `val` into part `[lo, lo + w)` of the element
/// reference `id` names, keeping the element's other bits as they are now
/// (the element may have changed through another path since this reference
/// was read). Nothing once the reference is outdated (13.5.2); `big_w == 0`
/// is [`ref_put`].
pub fn ref_put_part(id: u64, lo: u64, w: u32, big_w: u32, val: &[u64]) {
    if crate::winref::is_window(id) {
        return crate::winref::put_part(id, lo, w, big_w, val);
    }
    if big_w == 0 {
        return ref_put(id, val);
    }
    let mut elem = vec![0u64; (2 * big_w as usize).div_ceil(64)];
    if !ref_get(id, &mut elem) {
        return;
    }
    for k in 0..w as usize {
        let i = lo as usize + k;
        if i < big_w as usize {
            set_bit(&mut elem, i, bit_at(val, k));
            set_bit(&mut elem, big_w as usize + i, bit_at(val, w as usize + k));
        }
    }
    ref_put(id, &elem);
}

/// Closes reference `id`, live or outdated.
pub fn ref_close(id: u64) {
    if crate::winref::is_window(id) {
        return crate::winref::close(id);
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let k = id.wrapping_sub(1) as usize;
    if t.refs.get_mut(k).and_then(Option::take).is_some() {
        t.free_refs.push(k as u32);
        t.n_refs -= 1;
    }
}

/// Whether `h` still names a live entry: its slot is occupied *at `h`'s
/// version*. Unlike [`size`] (which reads the slot by index alone), a freed
/// slot another thread has since reused does not count -- the table is
/// process-global, so a test asserting "freed" must not be fooled by a
/// parallel test's allocation taking the slot.
#[cfg(test)]
pub(crate) fn is_live(h: u64) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.entries
        .get(index(h))
        .and_then(|e| e.as_ref())
        .is_some_and(|e| u64::from(e.version) == h >> 32)
}

/// A new sequence of `n` elements: element `i` is `src`'s element `i` if
/// it has one, else `dflt` (`new[n](src)`, §7.5.1). Object elements: the new
/// sequence takes its own reference on each (`dflt`'s included).
pub fn resized(shape: &Shape, src: u64, n: usize, dflt: &[u64]) -> u64 {
    let stride = shape.elem_words.max(1);
    let mut words = VecDeque::with_capacity(n * stride);
    {
        let t = table().lock().unwrap_or_else(|e| e.into_inner());
        if let Some(Data::Seq { words: w, .. }) = t.data(src) {
            words.extend(w.iter().copied().take(n * stride));
        }
    }
    while words.len() < n * stride {
        for k in 0..stride {
            words.push_back(dflt.get(k).copied().unwrap_or(0));
        }
    }
    retain_elems(shape, words.iter().copied());
    table()
        .lock()
        .unwrap_or_else(|e| e.into_inner())
        .alloc(shape.held(Data::Seq { stride, words }))
}

/// Takes a reference on the object of each element of `words` (a copy of
/// elements some other holder keeps).
fn retain_elems(shape: &Shape, words: impl Iterator<Item = u64>) {
    if shape.obj {
        words
            .step_by(shape.elem_words.max(1))
            .for_each(crate::objects::retain);
    }
}

/// A new sequence of the given elements (`n * elem_words` words). Object
/// elements: the sequence TAKES the caller's reference on each.
pub fn from_words(shape: &Shape, elems: &[u64]) -> u64 {
    let stride = shape.elem_words.max(1);
    table()
        .lock()
        .unwrap_or_else(|e| e.into_inner())
        .alloc(shape.held(Data::Seq {
            stride,
            words: elems.iter().copied().collect(),
        }))
}

/// [`from_words`] for elements some other holder still names: the new
/// sequence takes its own reference on each object.
pub fn from_copies(shape: &Shape, elems: &[u64]) -> u64 {
    retain_elems(shape, elems.iter().copied());
    from_words(shape, elems)
}

/// A constant sequence of the given elements (`elem_words` words each):
/// a declaration's initial value (see `Entry::frozen`).
pub fn frozen_from_words(elem_words: usize, elems: &[u64]) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let h = t.alloc(Held {
        data: Data::Seq {
            stride: elem_words.max(1),
            words: elems.iter().copied().collect(),
        },
        objs: false,
        key_objs: false,
    });
    if let Some(e) = t.entries[index(h)].as_mut() {
        e.frozen = true;
    }
    h
}

/// A constant associative array of the given entries (see
/// [`frozen_from_words`]).
pub fn frozen_map(entries: Vec<(Key, Vec<u64>)>, default: Option<Vec<u64>>) -> u64 {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let h = t.alloc(Held {
        data: Data::Map(
            entries.into_iter().map(|(k, v)| (k, v.into())).collect(),
            default.map(Into::into),
        ),
        objs: false,
        key_objs: false,
    });
    if let Some(e) = t.entries[index(h)].as_mut() {
        e.frozen = true;
    }
    h
}

/// One constant collection (see [`Entry::frozen`]), as plain data.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum FrozenData {
    Seq {
        stride: usize,
        words: Vec<u64>,
    },
    Map {
        entries: Vec<(Key, Vec<u64>)>,
        default: Option<Vec<u64>>,
    },
}

/// Every collection of this process, as the constants a declaration's initial
/// value names: entry 1 first, so entry `i` is handle `(1 << 32) | i`. The
/// handles are baked into a built design's cells, which is why it carries
/// these ([`frozen_preload`]). `Err` if the table holds anything else (a live
/// non-constant collection, or a freed slot), since its handles could not be
/// reproduced.
pub fn frozen_snapshot() -> Result<Vec<FrozenData>, String> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.entries[1..]
        .iter()
        .enumerate()
        .map(|(i, e)| {
            let Some(e) = e.as_ref().filter(|e| e.frozen && e.version == 1) else {
                return Err(format!(
                    "collection {} is not a constant of a declaration's initial value",
                    i + 1
                ));
            };
            Ok(plain(e))
        })
        .collect()
}

fn plain(e: &Entry) -> FrozenData {
    match &e.data.data {
        Data::Seq { stride, words } => FrozenData::Seq {
            stride: *stride,
            words: words.iter().copied().collect(),
        },
        Data::Map(m, dflt) => FrozenData::Map {
            entries: m.iter().map(|(k, v)| (k.clone(), v.to_vec())).collect(),
            default: dflt.as_ref().map(|d| d.to_vec()),
        },
    }
}

/// Makes `frozen` (a [`frozen_snapshot`]) entries `1..` of this process's
/// table, each at the handle it had when built. Fails if the table already
/// holds something else.
pub fn frozen_preload(frozen: &[FrozenData]) -> Result<(), String> {
    for (i, f) in frozen.iter().enumerate() {
        let want = (1u64 << 32) | (i as u64 + 1);
        let have = frozen_snapshot_entry(i + 1);
        if let Some(have) = have {
            if &have != f {
                return Err(format!(
                    "collection {} of the design cannot take its handle: this process \
                     already made a different one",
                    i + 1
                ));
            }
            continue;
        }
        let got = match f {
            FrozenData::Seq { stride, words } => frozen_from_words(*stride, words),
            FrozenData::Map { entries, default } => frozen_map(entries.clone(), default.clone()),
        };
        if got != want {
            return Err(format!(
                "collection {} of the design got handle {got:#x}, not {want:#x}",
                i + 1
            ));
        }
    }
    Ok(())
}

/// Entry `i` as plain data, if it is a constant.
fn frozen_snapshot_entry(i: usize) -> Option<FrozenData> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.entries.get(i)?.as_ref().filter(|e| e.frozen).map(plain)
}

/// A new associative array with `h`'s keys and `default:` value but the
/// values `flat` (`elem_words` words per key, in key order): what
/// `randomize()` writes back to a `rand` associative array, whose keys it
/// never changes (LRM 18.4). `None` when `h` is not an associative array or
/// `flat` does not have exactly one value per key. Integral elements only
/// (no object references are moved).
pub fn map_with_values(h: u64, elem_words: usize, flat: &[u64]) -> Option<u64> {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(Data::Map(m, dflt)) = t.data(h) else {
        return None;
    };
    if flat.len() != m.len() * elem_words {
        return None;
    }
    let keys: Vec<Key> = m.keys().cloned().collect();
    let dflt = dflt.clone();
    let map: BTreeMap<Key, Box<[u64]>> = keys
        .into_iter()
        .zip(flat.chunks(elem_words.max(1)))
        .map(|(k, v)| (k, v.into()))
        .collect();
    Some(t.alloc(Held {
        data: Data::Map(map, dflt),
        objs: false,
        key_objs: false,
    }))
}

/// `h` with every element of `other` appended (a concatenation's queue
/// operand); object elements: `h` takes its own reference on each.
pub fn append(shape: &Shape, h: u64, other: u64) -> u64 {
    let extra: Vec<u64> = {
        let t = table().lock().unwrap_or_else(|e| e.into_inner());
        match t.data(other) {
            Some(Data::Seq { words, .. }) => words.iter().copied().collect(),
            _ => Vec::new(),
        }
    };
    retain_elems(shape, extra.iter().copied());
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    t.modify(
        h,
        || shape.empty(),
        |d| {
            if let Data::Seq { words, .. } = &mut d.data {
                words.extend(extra);
            }
        },
    )
}

/// Elements `a..=b` as a new sequence, clamped to the sequence (an empty
/// result when `a > b`, §7.10.1).
pub fn slice(shape: &Shape, h: u64, a: i64, b: i64) -> u64 {
    let n = size(h) as i64;
    let a = a.max(0);
    let b = b.min(n - 1);
    let stride = shape.elem_words.max(1);
    let mut out = VecDeque::new();
    if a <= b {
        let t = table().lock().unwrap_or_else(|e| e.into_inner());
        if let Some(Data::Seq { words, .. }) = t.data(h) {
            out.extend(
                words
                    .range(a as usize * stride..(b as usize + 1) * stride)
                    .copied(),
            );
        }
    }
    retain_elems(shape, out.iter().copied());
    table()
        .lock()
        .unwrap_or_else(|e| e.into_inner())
        .alloc(shape.held(Data::Seq { stride, words: out }))
}

/// Whether two collections hold the same elements (and keys).
pub fn equal(a: u64, b: u64) -> bool {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    match (t.data(a), t.data(b)) {
        (None, None) => true,
        (Some(d), None) | (None, Some(d)) => d.len() == 0,
        (Some(Data::Seq { words: x, .. }), Some(Data::Seq { words: y, .. })) => x == y,
        (Some(Data::Map(x, _)), Some(Data::Map(y, _))) => x == y,
        _ => false,
    }
}

/// The first / last key (`first`, `last`), or the key after / before `key`
/// (`next`, `prev`), of an associative array (§7.9.4-7.9.7).
pub fn neighbor(h: u64, key: Option<&Key>, forward: bool) -> Option<Key> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    let Some(Data::Map(m, _)) = t.data(h) else {
        return None;
    };
    let found = match (key, forward) {
        (None, true) => m.keys().next(),
        (None, false) => m.keys().next_back(),
        (Some(k), true) => m
            .range((Bound::Excluded(k.clone()), Bound::Unbounded))
            .next()
            .map(|(k, _)| k),
        (Some(k), false) => m
            .range((Bound::Unbounded, Bound::Excluded(k.clone())))
            .next_back()
            .map(|(k, _)| k),
    };
    found.cloned()
}

/// The key at position `pos` of an associative array (a `foreach`
/// visits keys in order); sequential positions are O(log n) each.
pub fn key_at(h: u64, pos: usize) -> Option<Key> {
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let i = index(h);
    let e = t.entries.get_mut(i)?.as_mut()?;
    let Data::Map(m, _) = &e.data.data else {
        return None;
    };
    let key = match &e.cursor {
        Some((p, k)) if *p == pos => Some(k.clone()),
        Some((p, k)) if *p + 1 == pos => m
            .range((Bound::Excluded(k.clone()), Bound::Unbounded))
            .next()
            .map(|(k, _)| k.clone()),
        _ => m.keys().nth(pos).cloned(),
    };
    if let Some(k) = &key {
        e.cursor = Some((pos, k.clone()));
    }
    key
}

/// The key at position `pos` of an associative array and its value into
/// `out` (an array method walking the entries in key order).
pub fn entry_at(h: u64, pos: usize, out: &mut [u64]) -> Option<Key> {
    let key = key_at(h, pos)?;
    lookup(h, &key, out);
    Some(key)
}

/// `h` with its elements reordered: element `k` becomes the old element
/// `order[k]` (`order` a permutation of the positions).
pub fn permute(shape: &Shape, h: u64, order: &[usize]) -> u64 {
    let old = elements(h);
    if old.len() != order.len() || old.is_empty() {
        return h;
    }
    let mut t = table().lock().unwrap_or_else(|e| e.into_inner());
    let new = t.modify(
        h,
        || shape.empty(),
        |d| {
            // The same elements in a new order: the references stay put.
            if let Data::Seq { words, .. } = &mut d.data {
                words.clear();
                for &k in order {
                    words.extend(old[k].iter().copied());
                }
            }
        },
    );
    // The LRM names no ordering method among the operations that keep or
    // outdate references (7.10.3): an open element reference would address
    // a different element afterwards, so it is outdated (its write is
    // dropped rather than landing on the wrong element).
    t.refs_outdated(index(new), 0);
    new
}

/// Every element of `h` as words, element 0 (or the first key's value)
/// first -- for `%p`.
pub fn elements(h: u64) -> Vec<Vec<u64>> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    match t.data(h) {
        Some(Data::Seq { stride, words }) => words
            .iter()
            .copied()
            .collect::<Vec<_>>()
            .chunks(*stride)
            .map(<[u64]>::to_vec)
            .collect(),
        Some(Data::Map(m, _)) => m.values().map(|v| v.to_vec()).collect(),
        None => Vec::new(),
    }
}

/// Every key of an associative array, in order -- for `%p`.
pub fn keys(h: u64) -> Vec<Key> {
    let t = table().lock().unwrap_or_else(|e| e.into_inner());
    match t.data(h) {
        Some(Data::Map(m, _)) => m.keys().cloned().collect(),
        _ => Vec::new(),
    }
}

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

    const Q: Shape = Shape {
        elem_words: 1,
        assoc: false,
        key: KeyKind::Str,
        obj: false,
    };

    #[test]
    fn a_queue_pushes_pops_and_changes_handle_on_every_change() {
        let h = push(&Q, 0, &[3], false);
        let h2 = push(&Q, h, &[4], false);
        assert_ne!(h, h2, "each change is a new handle value");
        let h3 = push(&Q, h2, &[1], true);
        assert_eq!(size(h3), 3);
        let mut out = [0];
        assert!(get(h3, 2, &mut out));
        assert_eq!(out, [4]);
        let (h4, ok) = pop(&Q, h3, &mut out, true);
        assert!(ok);
        assert_eq!(out, [1]);
        assert_eq!(size(h4), 2);
    }

    #[test]
    fn clone_deep_copies_inner_collections_and_equal_nest_compares_contents() {
        const OUTER: Shape = Shape {
            elem_words: 2,
            assoc: false,
            key: KeyKind::Str,
            obj: false,
        };
        let nest = Nest {
            slots: vec![(0, Nest::default())],
        };
        let inner = push(&Q, push(&Q, 0, &[1], false), &[2], false);
        let outer = push(&OUTER, 0, &[inner, 0], false);
        let mut minted = Vec::new();
        let copy = clone_deep(outer, &nest, &mut minted);
        // The inner queue changes in place (same entry, new handle) and the
        // outer element is re-pointed at it, as the design's store does.
        let grown = push(&Q, inner, &[3], false);
        let outer = set(&OUTER, outer, 0, &[grown, 0], true);
        let mut got = [0, 0];
        assert!(get(copy, 0, &mut got));
        assert_eq!(size(got[0]), 2, "the copy keeps the old inner contents");
        assert!(!equal_nest(outer, copy, &nest), "contents differ");
        let again = clone_deep(outer, &nest, &mut minted);
        assert!(equal_nest(outer, again, &nest));
        minted.iter().for_each(|&h| release(h));
    }

    fn queue_of(vals: &[u64]) -> u64 {
        vals.iter().fold(0, |h, v| push(&Q, h, &[*v], false))
    }

    fn words(h: u64) -> Vec<u64> {
        (0..size(h) as i64)
            .map(|i| {
                let mut o = [0];
                get(h, i, &mut o);
                o[0]
            })
            .collect()
    }

    #[test]
    fn an_element_reference_follows_other_elements_and_writes_through() {
        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 1);
        assert_ne!(id, 0);
        let mut out = [0];
        assert!(ref_get(id, &mut out));
        assert_eq!(out, [2]);
        let h = push(&Q, h, &[9], true); // 9 1 2 3: the element moves to 2
        let h = insert(&Q, h, 0, &[8]); // 8 9 1 2 3: and to 3
        let h = delete_at(&Q, h, 1); // 8 1 2 3: and back to 2
        assert!(ref_get(id, &mut out));
        assert_eq!(out, [2]);
        ref_put(id, &[10]);
        assert_eq!(words(h), [8, 1, 10, 3]);
        // A direct write is seen through the reference.
        let h = set(&Q, h, 2, &[11], true);
        assert!(ref_get(id, &mut out));
        assert_eq!(out, [11]);
        ref_close(id);
        assert!(!ref_get(id, &mut out), "a closed reference is gone");
        assert_eq!(words(h), [8, 1, 11, 3]);
    }

    #[test]
    fn a_part_reference_reads_and_writes_only_its_bits() {
        // A 32-bit element is `(unk << 32) | val`; the part is bits [8, 16).
        let h = queue_of(&[0x0000_0F00_AABB_CCDD, 7]);
        let id = ref_open(h, 0);
        let mut out = [u64::MAX];
        assert!(ref_get_part(id, 8, 8, 32, &mut out));
        // val 0xCC, unk 0x0F: packed as (unk << 8) | val.
        assert_eq!(out, [0x0FCC]);
        ref_put_part(id, 8, 8, 32, &[0x01_55]);
        assert_eq!(words(h), [0x0000_0100_AABB_55DD, 7]);
        // `big_w == 0` is the whole element.
        assert!(ref_get_part(id, 0, 32, 0, &mut out));
        assert_eq!(out, [0x0000_0100_AABB_55DD]);
        ref_close(id);
        assert!(!ref_get_part(id, 8, 8, 32, &mut out));
    }

    #[test]
    fn an_outdated_element_reference_drops_its_write_and_keeps_its_id() {
        // Deleting the element, popping it, truncating it away, clearing and
        // releasing the collection all outdate (LRM 7.10.3, 7.5.1).
        let mut out = [0];
        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 1);
        let h = delete_at(&Q, h, 1);
        assert!(!ref_get(id, &mut out));
        // The id is not reused while the callee holds it.
        let other = ref_open(h, 0);
        assert_ne!(other, id);
        ref_put(id, &[10]);
        assert_eq!(words(h), [1, 3]);
        ref_close(id);
        ref_close(other);

        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 2);
        let (h, _) = pop(&Q, h, &mut out, false);
        ref_put(id, &[10]);
        assert_eq!(words(h), [1, 2]);
        ref_close(id);

        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 2);
        let h = truncate(&Q, h, 2);
        ref_put(id, &[10]);
        assert_eq!(words(h), [1, 2]);
        ref_close(id);

        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 0);
        let h = clear(&Q, h);
        let h = push(&Q, h, &[5], false);
        ref_put(id, &[10]);
        assert_eq!(words(h), [5]);
        ref_close(id);

        // The collection is released (its variable was assigned).
        let h = queue_of(&[1, 2, 3]);
        let id = ref_open(h, 0);
        release(h);
        let other = queue_of(&[7, 8, 9]);
        ref_put(id, &[10]);
        assert_eq!(words(other), [7, 8, 9]);
        assert!(!ref_get(id, &mut out));
        ref_close(id);
    }

    #[test]
    fn a_reference_outside_the_collection_is_never_open() {
        let h = queue_of(&[1]);
        assert_eq!(ref_open(h, 1), 0);
        assert_eq!(ref_open(h, -1), 0);
        assert_eq!(ref_open(0, 0), 0);
        ref_put(0, &[5]);
        assert_eq!(words(h), [1]);
    }

    #[test]
    fn a_reference_survives_a_frozen_values_first_write() {
        let f = frozen_from_words(1, &[1, 2]);
        let f = ref_own(&Q, f);
        let id = ref_open(f, 1);
        let g = insert(&Q, f, 0, &[0]);
        ref_put(id, &[5]);
        assert_eq!(words(g), [0, 1, 5]);
        ref_close(id);
    }

    #[test]
    fn a_clone_is_a_copy_on_write_value() {
        let a = push(&Q, 0, &[7], false);
        let b = clone(a);
        let b2 = set(&Q, b, 0, &[9], true);
        let mut out = [0];
        get(a, 0, &mut out);
        assert_eq!(out, [7], "changing the copy leaves the original");
        get(b2, 0, &mut out);
        assert_eq!(out, [9]);
    }

    #[test]
    fn a_frozen_value_is_shared_and_never_changed_in_place() {
        let f = frozen_from_words(1, &[1, 2]);
        assert_eq!(clone(f), f, "a constant needs no copy");
        let a = push(&Q, f, &[3], false);
        assert_ne!(index(a), index(f), "a change makes a new entry");
        assert_eq!(size(f), 2);
        assert_eq!(size(a), 3);
        release(f);
        assert_eq!(size(f), 2, "a constant is never freed");
    }

    #[test]
    fn associative_keys_are_ordered_and_walkable() {
        let s = Shape {
            elem_words: 1,
            assoc: true,
            key: KeyKind::Int {
                width: 8,
                signed: true,
            },
            obj: false,
        };
        let mut h = 0;
        for k in [5i128, -3, 2] {
            h = store(&s, h, Key::Int(k), &[k as u64]);
        }
        assert_eq!(neighbor(h, None, true), Some(Key::Int(-3)));
        assert_eq!(neighbor(h, Some(&Key::Int(2)), true), Some(Key::Int(5)));
        assert_eq!(neighbor(h, Some(&Key::Int(5)), true), None);
        assert_eq!(key_at(h, 0), Some(Key::Int(-3)));
        assert_eq!(key_at(h, 1), Some(Key::Int(2)));
        assert_eq!(key_at(h, 2), Some(Key::Int(5)));
        assert_eq!(s.key_from_bits(&[0xfd]), Some(Key::Int(-3)));
        assert_eq!(s.key_from_bits(&[0x1fd]), None, "an unknown bit");
    }

    // Classes plan Task 10: collections of class handles own one object
    // reference per element. Every test below reads only per-handle
    // `objects::refcount` (the heap's `live_count` is process-global and the
    // tests run concurrently) and allocates objects of its own template id.

    /// A queue / dynamic array of class handles: 64-bit element, two words.
    const OQ: Shape = Shape {
        elem_words: 2,
        assoc: false,
        key: KeyKind::Str,
        obj: true,
    };

    fn oa() -> Shape {
        Shape {
            elem_words: 2,
            assoc: true,
            key: KeyKind::Int {
                width: 8,
                signed: true,
            },
            obj: true,
        }
    }

    /// A fresh object (refcount 1, the caller's reference).
    fn obj(template: u32) -> u64 {
        crate::objects::alloc(crate::netlist::ClassTemplateId(template), 1)
    }

    fn rc(h: u64) -> Option<u32> {
        crate::objects::refcount(h)
    }

    #[test]
    fn a_pushed_object_element_takes_the_callers_reference() {
        let a = obj(1013);
        let q = push(&OQ, 0, &[a, 0], false);
        assert_eq!(rc(a), Some(1), "the queue owns the one reference");
        release(q);
        assert_eq!(rc(a), None, "releasing the queue frees what it alone held");
    }

    #[test]
    fn overwriting_deleting_and_clearing_release_the_old_element() {
        let (a, b, c) = (obj(1014), obj(1014), obj(1014));
        crate::objects::retain(a);
        crate::objects::retain(b);
        crate::objects::retain(c);
        // Each object now has two references: ours and the queue's.
        let mut q = push(&OQ, 0, &[a, 0], false);
        q = push(&OQ, q, &[b, 0], false);
        q = push(&OQ, q, &[c, 0], false);
        assert_eq!((rc(a), rc(b), rc(c)), (Some(2), Some(2), Some(2)));
        // Overwrite element 0 with `b` (the queue takes another reference we
        // acquire for it): `a` loses the queue's reference.
        crate::objects::retain(b);
        q = set(&OQ, q, 0, &[b, 0], true);
        assert_eq!(rc(a), Some(1), "an overwritten element is released");
        assert_eq!(rc(b), Some(3));
        q = delete_at(&OQ, q, 0);
        assert_eq!(rc(b), Some(2), "a deleted element is released");
        q = clear(&OQ, q);
        assert_eq!(rc(b), Some(1));
        assert_eq!(rc(c), Some(1), "clear releases every element");
        assert_eq!(size(q), 0);
        for h in [a, b, c] {
            crate::objects::release(h);
            assert_eq!(rc(h), None);
        }
        release(q);
    }

    #[test]
    fn a_pop_hands_its_reference_to_the_caller() {
        let a = obj(1015);
        let q = push(&OQ, 0, &[a, 0], false);
        let mut out = [0, 0];
        let (q, ok) = pop(&OQ, q, &mut out, true);
        assert!(ok);
        assert_eq!(out[0], a);
        assert_eq!(rc(a), Some(1), "the reference moved, it was not dropped");
        crate::objects::release(out[0]);
        assert_eq!(rc(a), None);
        release(q);
    }

    #[test]
    fn an_ignored_write_gives_back_the_reference_it_was_handed() {
        let (a, b, c) = (obj(1016), obj(1016), obj(1016));
        let q = push(&OQ, 0, &[c, 0], false);
        let q = set(&OQ, q, 5, &[a, 0], true);
        assert_eq!(rc(a), None, "an out-of-range set releases the value");
        let q = insert(&OQ, q, -1, &[b, 0]);
        assert_eq!(rc(b), None, "an out-of-range insert releases the value");
        assert_eq!(rc(c), Some(1), "the element already there is untouched");
        release(q);
        assert_eq!(rc(c), None);
    }

    #[test]
    fn a_copy_on_write_clone_takes_its_own_reference_per_element() {
        let a = obj(1017);
        let q = push(&OQ, 0, &[a, 0], false);
        let copy = clone(q);
        assert_eq!(rc(a), Some(1), "an unchanged clone shares the references");
        let b = obj(1017);
        let copy = push(&OQ, copy, &[b, 0], false);
        assert_eq!(rc(a), Some(2), "unsharing the copy retains each element");
        release(q);
        assert_eq!(rc(a), Some(1), "the original's holder let go of its own");
        release(copy);
        assert_eq!(rc(a), None);
        assert_eq!(rc(b), None);
    }

    #[test]
    fn resized_append_slice_and_from_copies_retain_what_they_copy() {
        let (a, b) = (obj(1018), obj(1018));
        let q = push(&OQ, push(&OQ, 0, &[a, 0], false), &[b, 0], false);
        assert_eq!((rc(a), rc(b)), (Some(1), Some(1)));
        let grown = resized(&OQ, q, 3, &[a, 0]);
        // `a` once from the copied element 0 and once for the default that
        // fills element 2; `b` once for the copied element 1.
        assert_eq!((rc(a), rc(b)), (Some(3), Some(2)));
        let sl = slice(&OQ, q, 1, 1);
        assert_eq!(rc(b), Some(3));
        let ap = append(&OQ, 0, q);
        assert_eq!((rc(a), rc(b)), (Some(4), Some(4)));
        let fc = from_copies(&OQ, &[a, 0, b, 0]);
        assert_eq!((rc(a), rc(b)), (Some(5), Some(5)));
        for h in [q, grown, sl, ap, fc] {
            release(h);
        }
        assert_eq!(
            (rc(a), rc(b)),
            (None, None),
            "no holder left, nothing leaks"
        );
    }

    #[test]
    fn an_associative_array_owns_values_and_its_default() {
        let (a, b, d) = (obj(1019), obj(1019), obj(1019));
        let s = oa();
        let mut h = store(&s, 0, Key::Int(1), &[a, 0]);
        crate::objects::retain(a);
        h = store(&s, h, Key::Int(2), &[a, 0]);
        assert_eq!(rc(a), Some(2), "two keys, two references");
        h = store(&s, h, Key::Int(1), &[b, 0]);
        assert_eq!(rc(a), Some(1), "replacing a value releases the old one");
        h = delete_key(&s, h, &Key::Int(2));
        assert_eq!(rc(a), None, "deleting a key releases its value");
        h = delete_key(&s, h, &Key::Int(99));
        assert_eq!(rc(b), Some(1), "deleting an absent key changes nothing");
        h = set_default(&s, h, &[d, 0]);
        assert_eq!(rc(d), Some(1));
        h = clear(&s, h);
        assert_eq!(rc(b), None);
        assert_eq!(rc(d), Some(1), "clear keeps the default's reference");
        release(h);
        assert_eq!(rc(d), None, "freeing the array frees its default");
    }

    /// A class-handle-keyed map (LRM 7.8.3) owns one reference per key:
    /// a new key retains, a re-store of the key does not, delete/clear/free
    /// and a copy-on-write unshare release/retain.
    #[test]
    fn a_handle_keyed_map_owns_its_keys() {
        let (k1, k2) = (obj(1021), obj(1021));
        let s = Shape {
            elem_words: 1,
            assoc: true,
            key: KeyKind::Obj,
            obj: false,
        };
        let key = |k: u64| Key::Int(i128::from(k));
        let mut h = store(&s, 0, key(k1), &[1]);
        assert_eq!(rc(k1), Some(2), "a new key takes its own reference");
        h = store(&s, h, key(k1), &[2]);
        assert_eq!(rc(k1), Some(2), "re-storing an existing key adds none");
        h = store(&s, h, key(k2), &[3]);
        let c = clone(h);
        let c = store(&s, c, key(k2), &[4]);
        assert_eq!(rc(k1), Some(3), "an unshared copy retains each key");
        h = delete_key(&s, h, &key(k1));
        assert_eq!(rc(k1), Some(2), "deleting a key releases it");
        h = clear(&s, h);
        assert_eq!(rc(k2), Some(2), "clear releases every key");
        release(h);
        release(c);
        assert_eq!(rc(k1), Some(1), "freeing the copy releases its keys");
        assert_eq!(rc(k2), Some(1));
        crate::objects::release(k1);
        crate::objects::release(k2);
    }

    #[test]
    fn a_permutation_moves_references_without_changing_counts() {
        let (a, b) = (obj(1020), obj(1020));
        let q = push(&OQ, push(&OQ, 0, &[a, 0], false), &[b, 0], false);
        let q = permute(&OQ, q, &[1, 0]);
        let mut out = [0, 0];
        assert!(get(q, 0, &mut out));
        assert_eq!(out[0], b);
        assert_eq!((rc(a), rc(b)), (Some(1), Some(1)));
        release(q);
        assert_eq!((rc(a), rc(b)), (None, None));
    }

    /// `build-aot` refuses, naming the feature `collection`, a design whose process
    /// holds a collection that is not a declaration's constant: no `.sv`
    /// source reaches that state (every build-time collection is made by
    /// `frozen_from_words`/`frozen_map`), so this is the refusal sweep's
    /// exercise of that guard (`aot_refusal_sweep.rs` names this test).
    #[test]
    fn frozen_snapshot_refuses_a_live_collection() {
        let live = from_words(&Q, &[1, 2]);
        let why = frozen_snapshot().expect_err("a live collection cannot be frozen into an image");
        assert!(why.contains("not a constant"), "{why}");
        release(live);
    }
}