oxilean_kernel/name/

types.rs

//! Auto-generated module
//!
//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)

use std::collections::{HashMap, HashSet, VecDeque};
use std::rc::Rc;

/// A clock that measures elapsed time in a loop.
#[allow(dead_code)]
pub struct LoopClock {
    start: crate::wall_clock::Instant,
    iters: u64,
}
#[allow(dead_code)]
impl LoopClock {
    /// Starts the clock.
    pub fn start() -> Self {
        Self {
            start: crate::wall_clock::Instant::now(),
            iters: 0,
        }
    }
    /// Records one iteration.
    pub fn tick(&mut self) {
        self.iters += 1;
    }
    /// Returns the elapsed time in microseconds.
    pub fn elapsed_us(&self) -> f64 {
        self.start.elapsed().as_secs_f64() * 1e6
    }
    /// Returns the average microseconds per iteration.
    pub fn avg_us_per_iter(&self) -> f64 {
        if self.iters == 0 {
            return 0.0;
        }
        self.elapsed_us() / self.iters as f64
    }
    /// Returns the number of iterations.
    pub fn iters(&self) -> u64 {
        self.iters
    }
}
/// A monotonic timestamp in microseconds.
#[allow(dead_code)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Timestamp(u64);
#[allow(dead_code)]
impl Timestamp {
    /// Creates a timestamp from microseconds.
    pub const fn from_us(us: u64) -> Self {
        Self(us)
    }
    /// Returns the timestamp in microseconds.
    pub fn as_us(self) -> u64 {
        self.0
    }
    /// Returns the duration between two timestamps.
    pub fn elapsed_since(self, earlier: Timestamp) -> u64 {
        self.0.saturating_sub(earlier.0)
    }
}
/// A fresh-name generator.
///
/// Generates unique names by appending an incrementing counter suffix.
#[derive(Debug, Clone)]
pub struct NameGenerator {
    base: Name,
    counter: u64,
}
impl NameGenerator {
    /// Create a generator with the given base name.
    pub fn new(base: Name) -> Self {
        Self { base, counter: 0 }
    }
    /// Create a generator with a string base.
    pub fn with_base(s: impl Into<String>) -> Self {
        Self::new(Name::str(s))
    }
    /// Generate the next fresh name.
    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> Name {
        let n = self.base.clone().append_num(self.counter);
        self.counter += 1;
        n
    }
    /// Peek at the next name without advancing.
    pub fn peek(&self) -> Name {
        self.base.clone().append_num(self.counter)
    }
    /// Reset the counter to 0.
    pub fn reset(&mut self) {
        self.counter = 0;
    }
    /// Current counter value.
    pub fn count(&self) -> u64 {
        self.counter
    }
}
/// A type-safe wrapper around a `u32` identifier.
#[allow(dead_code)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct TypedId<T> {
    pub(super) id: u32,
    _phantom: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<T> TypedId<T> {
    /// Creates a new typed ID.
    pub const fn new(id: u32) -> Self {
        Self {
            id,
            _phantom: std::marker::PhantomData,
        }
    }
    /// Returns the raw `u32` ID.
    pub fn raw(&self) -> u32 {
        self.id
    }
}
/// Interns strings to save memory (each unique string stored once).
#[allow(dead_code)]
pub struct StringInterner {
    strings: Vec<String>,
    map: std::collections::HashMap<String, u32>,
}
#[allow(dead_code)]
impl StringInterner {
    /// Creates a new string interner.
    pub fn new() -> Self {
        Self {
            strings: Vec::new(),
            map: std::collections::HashMap::new(),
        }
    }
    /// Interns `s` and returns its ID.
    pub fn intern(&mut self, s: &str) -> u32 {
        if let Some(&id) = self.map.get(s) {
            return id;
        }
        let id = self.strings.len() as u32;
        self.strings.push(s.to_string());
        self.map.insert(s.to_string(), id);
        id
    }
    /// Returns the string for `id`.
    pub fn get(&self, id: u32) -> Option<&str> {
        self.strings.get(id as usize).map(|s| s.as_str())
    }
    /// Returns the total number of interned strings.
    pub fn len(&self) -> usize {
        self.strings.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.strings.is_empty()
    }
}
/// A trie (prefix tree) for efficient name lookups.
///
/// Each node in the trie corresponds to one component of a hierarchical name.
/// Useful for namespace browsing and completion in the LSP server.
#[derive(Debug, Clone)]
pub struct NameTrie<V> {
    /// Value stored at this node (if any).
    pub(super) value: Option<V>,
    /// Children indexed by string component.
    pub(super) string_children: Vec<(String, NameTrie<V>)>,
    /// Children indexed by numeric component.
    pub(super) num_children: Vec<(u64, NameTrie<V>)>,
}
impl<V: Clone> NameTrie<V> {
    /// Create an empty trie.
    pub fn new() -> Self {
        Self::default()
    }
    /// Insert a name-value pair into the trie.
    pub fn insert(&mut self, name: &Name, value: V) {
        match name.view() {
            NameView::Anonymous => {
                self.value = Some(value);
            }
            NameView::Str(parent, s) => {
                let child = if let Some(idx) = self
                    .string_children
                    .iter()
                    .position(|(k, _)| k.as_str() == s)
                {
                    &mut self.string_children[idx].1
                } else {
                    self.string_children.push((s.to_string(), NameTrie::new()));
                    let last = self.string_children.len() - 1;
                    &mut self.string_children[last].1
                };
                child.insert(parent, value);
            }
            NameView::Num(parent, n) => {
                let child = if let Some(idx) = self.num_children.iter().position(|(k, _)| *k == n) {
                    &mut self.num_children[idx].1
                } else {
                    self.num_children.push((n, NameTrie::new()));
                    let last = self.num_children.len() - 1;
                    &mut self.num_children[last].1
                };
                child.insert(parent, value);
            }
        }
    }
    /// Look up a name in the trie.
    pub fn lookup(&self, name: &Name) -> Option<&V> {
        match name.view() {
            NameView::Anonymous => self.value.as_ref(),
            NameView::Str(parent, s) => {
                let child = self
                    .string_children
                    .iter()
                    .find(|(k, _)| k.as_str() == s)
                    .map(|(_, v)| v)?;
                child.lookup(parent)
            }
            NameView::Num(parent, n) => {
                let child = self
                    .num_children
                    .iter()
                    .find(|(k, _)| *k == n)
                    .map(|(_, v)| v)?;
                child.lookup(parent)
            }
        }
    }
    /// Check whether the trie contains the given name.
    pub fn contains(&self, name: &Name) -> bool {
        self.lookup(name).is_some()
    }
    /// Count all values stored in the trie.
    pub fn count(&self) -> usize {
        let self_count = if self.value.is_some() { 1 } else { 0 };
        let str_count: usize = self.string_children.iter().map(|(_, c)| c.count()).sum();
        let num_count: usize = self.num_children.iter().map(|(_, c)| c.count()).sum();
        self_count + str_count + num_count
    }
    /// Collect all (name, value) pairs in the trie.
    pub fn to_vec(&self) -> Vec<(Name, V)> {
        let mut result = Vec::new();
        self.collect_all(Name::anonymous(), &mut result);
        result
    }
    fn collect_all(&self, prefix: Name, result: &mut Vec<(Name, V)>) {
        if let Some(v) = &self.value {
            result.push((prefix.clone(), v.clone()));
        }
        for (s, child) in &self.string_children {
            let name = prefix.clone().append_str(s.as_str());
            child.collect_all(name, result);
        }
        for (n, child) in &self.num_children {
            let name = prefix.clone().append_num(*n);
            child.collect_all(name, result);
        }
    }
}
/// A FIFO work queue.
#[allow(dead_code)]
pub struct WorkQueue<T> {
    items: std::collections::VecDeque<T>,
}
#[allow(dead_code)]
impl<T> WorkQueue<T> {
    /// Creates a new empty queue.
    pub fn new() -> Self {
        Self {
            items: std::collections::VecDeque::new(),
        }
    }
    /// Enqueues a work item.
    pub fn enqueue(&mut self, item: T) {
        self.items.push_back(item);
    }
    /// Dequeues the next work item.
    pub fn dequeue(&mut self) -> Option<T> {
        self.items.pop_front()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
    /// Returns the number of pending items.
    pub fn len(&self) -> usize {
        self.items.len()
    }
}
/// A sequence number that can be compared for ordering.
#[allow(dead_code)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SeqNum(u64);
#[allow(dead_code)]
impl SeqNum {
    /// Creates sequence number zero.
    pub const ZERO: SeqNum = SeqNum(0);
    /// Advances the sequence number by one.
    pub fn next(self) -> SeqNum {
        SeqNum(self.0 + 1)
    }
    /// Returns the raw value.
    pub fn value(self) -> u64 {
        self.0
    }
}
/// A set of non-overlapping integer intervals.
#[allow(dead_code)]
pub struct IntervalSet {
    intervals: Vec<(i64, i64)>,
}
#[allow(dead_code)]
impl IntervalSet {
    /// Creates an empty interval set.
    pub fn new() -> Self {
        Self {
            intervals: Vec::new(),
        }
    }
    /// Adds the interval `[lo, hi]` to the set.
    pub fn add(&mut self, lo: i64, hi: i64) {
        if lo > hi {
            return;
        }
        let mut new_lo = lo;
        let mut new_hi = hi;
        let mut i = 0;
        while i < self.intervals.len() {
            let (il, ih) = self.intervals[i];
            if ih < new_lo - 1 {
                i += 1;
                continue;
            }
            if il > new_hi + 1 {
                break;
            }
            new_lo = new_lo.min(il);
            new_hi = new_hi.max(ih);
            self.intervals.remove(i);
        }
        self.intervals.insert(i, (new_lo, new_hi));
    }
    /// Returns `true` if `x` is in the set.
    pub fn contains(&self, x: i64) -> bool {
        self.intervals.iter().any(|&(lo, hi)| x >= lo && x <= hi)
    }
    /// Returns the number of intervals.
    pub fn num_intervals(&self) -> usize {
        self.intervals.len()
    }
    /// Returns the total count of integers covered.
    pub fn cardinality(&self) -> i64 {
        self.intervals.iter().map(|&(lo, hi)| hi - lo + 1).sum()
    }
}
/// A mapping from `Name` to `V`.
///
/// Wraps `HashMap<Name, V>` for convenient use in the elaborator and kernel.
#[derive(Debug, Clone, Default)]
pub struct NameMap<V> {
    pub(super) inner: HashMap<Name, V>,
}
impl<V> NameMap<V> {
    /// Create an empty `NameMap`.
    pub fn new() -> Self {
        Self {
            inner: HashMap::new(),
        }
    }
    /// Create a `NameMap` with the given capacity.
    pub fn with_capacity(cap: usize) -> Self {
        Self {
            inner: HashMap::with_capacity(cap),
        }
    }
    /// Insert or overwrite a mapping.
    pub fn insert(&mut self, name: Name, value: V) -> Option<V> {
        self.inner.insert(name, value)
    }
    /// Get a reference to the value for `name`.
    pub fn get(&self, name: &Name) -> Option<&V> {
        self.inner.get(name)
    }
    /// Get a mutable reference to the value for `name`.
    pub fn get_mut(&mut self, name: &Name) -> Option<&mut V> {
        self.inner.get_mut(name)
    }
    /// Remove and return the value for `name`.
    pub fn remove(&mut self, name: &Name) -> Option<V> {
        self.inner.remove(name)
    }
    /// Check whether `name` has a mapping.
    pub fn contains_key(&self, name: &Name) -> bool {
        self.inner.contains_key(name)
    }
    /// Number of mappings.
    pub fn len(&self) -> usize {
        self.inner.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
    /// Iterate over key-value pairs.
    pub fn iter(&self) -> impl Iterator<Item = (&Name, &V)> {
        self.inner.iter()
    }
    /// Iterate over keys.
    pub fn keys(&self) -> impl Iterator<Item = &Name> {
        self.inner.keys()
    }
    /// Iterate over values.
    pub fn values(&self) -> impl Iterator<Item = &V> {
        self.inner.values()
    }
    /// Filter entries by a predicate on the name.
    pub fn filter_by_namespace(&self, ns: &Name) -> Vec<(&Name, &V)> {
        self.inner
            .iter()
            .filter(|(n, _)| n.has_prefix(ns))
            .collect()
    }
    /// Collect all names in sorted order.
    pub fn sorted_names(&self) -> Vec<Name> {
        let mut names: Vec<Name> = self.inner.keys().cloned().collect();
        names.sort();
        names
    }
    /// Get or insert a default value.
    pub fn entry_or_insert(&mut self, name: Name, value: V) -> &mut V {
        self.inner.entry(name).or_insert(value)
    }
}
/// A pair of values useful for before/after comparisons.
#[allow(dead_code)]
#[allow(missing_docs)]
pub struct BeforeAfter<T> {
    /// Value before the transformation.
    pub before: T,
    /// Value after the transformation.
    pub after: T,
}
#[allow(dead_code)]
impl<T: PartialEq> BeforeAfter<T> {
    /// Creates a new before/after pair.
    pub fn new(before: T, after: T) -> Self {
        Self { before, after }
    }
    /// Returns `true` if before equals after (no change).
    pub fn unchanged(&self) -> bool {
        self.before == self.after
    }
}
/// A simple LIFO work queue.
#[allow(dead_code)]
pub struct WorkStack<T> {
    items: Vec<T>,
}
#[allow(dead_code)]
impl<T> WorkStack<T> {
    /// Creates a new empty stack.
    pub fn new() -> Self {
        Self { items: Vec::new() }
    }
    /// Pushes a work item.
    pub fn push(&mut self, item: T) {
        self.items.push(item);
    }
    /// Pops the next work item.
    pub fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
    /// Returns the number of pending work items.
    pub fn len(&self) -> usize {
        self.items.len()
    }
}
/// A generation counter for validity tracking.
#[allow(dead_code)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Generation(u32);
#[allow(dead_code)]
impl Generation {
    /// The initial generation.
    pub const INITIAL: Generation = Generation(0);
    /// Advances to the next generation.
    pub fn advance(self) -> Generation {
        Generation(self.0 + 1)
    }
    /// Returns the raw generation number.
    pub fn number(self) -> u32 {
        self.0
    }
}
/// A name with an optional namespace alias.
///
/// Used for name resolution when the user writes `open Nat` and then `add`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct QualifiedName {
    /// The full canonical name.
    pub canonical: Name,
    /// An optional shorter alias (e.g. after `open`).
    pub alias: Option<Name>,
}
impl QualifiedName {
    /// Create a new `QualifiedName` with no alias.
    pub fn new(canonical: Name) -> Self {
        Self {
            canonical,
            alias: None,
        }
    }
    /// Create a `QualifiedName` with an alias.
    pub fn with_alias(canonical: Name, alias: Name) -> Self {
        Self {
            canonical,
            alias: Some(alias),
        }
    }
    /// The preferred display name (alias if present, otherwise canonical).
    pub fn preferred(&self) -> &Name {
        self.alias.as_ref().unwrap_or(&self.canonical)
    }
}
/// An interning pool for `Name` strings.
#[allow(dead_code)]
pub struct NamePool {
    names: Vec<String>,
    index: std::collections::HashMap<String, usize>,
}
#[allow(dead_code)]
impl NamePool {
    /// Creates an empty name pool.
    pub fn new() -> Self {
        Self {
            names: Vec::new(),
            index: std::collections::HashMap::new(),
        }
    }
    /// Interns `name` and returns its ID.
    pub fn intern(&mut self, name: &str) -> usize {
        if let Some(&id) = self.index.get(name) {
            return id;
        }
        let id = self.names.len();
        self.names.push(name.to_string());
        self.index.insert(name.to_string(), id);
        id
    }
    /// Returns the name for `id`, or `None`.
    pub fn get(&self, id: usize) -> Option<&str> {
        self.names.get(id).map(|s| s.as_str())
    }
    /// Returns the number of interned names.
    pub fn len(&self) -> usize {
        self.names.len()
    }
    /// Returns `true` if the pool is empty.
    pub fn is_empty(&self) -> bool {
        self.names.is_empty()
    }
}
/// Resolves unqualified names to fully-qualified names given a namespace.
#[allow(dead_code)]
pub struct NameResolver {
    namespace: Vec<String>,
    registered: std::collections::HashSet<String>,
}
#[allow(dead_code)]
impl NameResolver {
    /// Creates a new resolver in the root namespace.
    pub fn new() -> Self {
        Self {
            namespace: Vec::new(),
            registered: std::collections::HashSet::new(),
        }
    }
    /// Registers a fully-qualified name.
    pub fn register(&mut self, fqn: impl Into<String>) {
        self.registered.insert(fqn.into());
    }
    /// Enters a sub-namespace.
    pub fn enter(&mut self, ns: impl Into<String>) {
        self.namespace.push(ns.into());
    }
    /// Exits the current sub-namespace.
    pub fn exit(&mut self) {
        self.namespace.pop();
    }
    /// Returns the current namespace as a dot-separated string.
    pub fn current_ns(&self) -> String {
        self.namespace.join(".")
    }
    /// Resolves `name` to a fully-qualified name.
    pub fn resolve(&self, name: &str) -> String {
        if self.namespace.is_empty() {
            return name.to_string();
        }
        let fqn = format!("{}.{}", self.namespace.join("."), name);
        if self.registered.contains(&fqn) {
            fqn
        } else {
            name.to_string()
        }
    }
}
/// A growable ring buffer with fixed maximum capacity.
#[allow(dead_code)]
pub struct RingBuffer<T> {
    data: Vec<Option<T>>,
    head: usize,
    tail: usize,
    count: usize,
    capacity: usize,
}
#[allow(dead_code)]
impl<T> RingBuffer<T> {
    /// Creates a new ring buffer with the given capacity.
    pub fn new(capacity: usize) -> Self {
        let mut data = Vec::with_capacity(capacity);
        for _ in 0..capacity {
            data.push(None);
        }
        Self {
            data,
            head: 0,
            tail: 0,
            count: 0,
            capacity,
        }
    }
    /// Pushes a value, overwriting the oldest if full.
    pub fn push(&mut self, val: T) {
        if self.count == self.capacity {
            self.data[self.head] = Some(val);
            self.head = (self.head + 1) % self.capacity;
            self.tail = (self.tail + 1) % self.capacity;
        } else {
            self.data[self.tail] = Some(val);
            self.tail = (self.tail + 1) % self.capacity;
            self.count += 1;
        }
    }
    /// Pops the oldest value.
    pub fn pop(&mut self) -> Option<T> {
        if self.count == 0 {
            return None;
        }
        let val = self.data[self.head].take();
        self.head = (self.head + 1) % self.capacity;
        self.count -= 1;
        val
    }
    /// Returns the number of elements.
    pub fn len(&self) -> usize {
        self.count
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }
    /// Returns `true` if at capacity.
    pub fn is_full(&self) -> bool {
        self.count == self.capacity
    }
}
/// A bidirectional map between two types.
#[allow(dead_code)]
pub struct BiMap<A: std::hash::Hash + Eq + Clone, B: std::hash::Hash + Eq + Clone> {
    forward: std::collections::HashMap<A, B>,
    backward: std::collections::HashMap<B, A>,
}
#[allow(dead_code)]
impl<A: std::hash::Hash + Eq + Clone, B: std::hash::Hash + Eq + Clone> BiMap<A, B> {
    /// Creates an empty bidirectional map.
    pub fn new() -> Self {
        Self {
            forward: std::collections::HashMap::new(),
            backward: std::collections::HashMap::new(),
        }
    }
    /// Inserts a pair `(a, b)`.
    pub fn insert(&mut self, a: A, b: B) {
        self.forward.insert(a.clone(), b.clone());
        self.backward.insert(b, a);
    }
    /// Looks up `b` for a given `a`.
    pub fn get_b(&self, a: &A) -> Option<&B> {
        self.forward.get(a)
    }
    /// Looks up `a` for a given `b`.
    pub fn get_a(&self, b: &B) -> Option<&A> {
        self.backward.get(b)
    }
    /// Returns the number of pairs.
    pub fn len(&self) -> usize {
        self.forward.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.forward.is_empty()
    }
}
/// A hierarchical name.
///
/// Names identify constants, inductives, and other declarations. They form a
/// tree: `Nat.add.comm` is `Str(Str(Str(Anonymous, "Nat"), "add"), "comm")`.
///
/// Structural sharing (wave5 Stage F): `Name` is a newtype over a
/// reference-counted cell holding its outermost component (`NameKind`), so
/// cloning a whole name — e.g. the name held by every `Const` referencing a
/// constant — is an O(1) refcount bump, not a deep copy of the component chain.
/// The parent link inside `NameKind` is itself a `Name`, so a name shares its
/// entire prefix with any longer name built on it: at Mathlib scale (millions of
/// recurring names and prefixes) residency is proportional to the number of
/// *distinct* names, not to how many times each is referenced.
///
/// Each name also stores a hash of its own structure, computed when it is
/// built from its parent's stored hash and its last component (see the
/// kernel-private `structural_hash` module) — so an `Expr` that mentions a
/// name (a `Const`, a binder, a projection) folds it into its own hash in O(1), without
/// walking the component chain.
///
/// Equality is exactly structural: the same allocation is equal, different
/// stored hashes are different (equal names always hash equal), and otherwise
/// the components are compared. `Hash` writes the components as it always did
/// (not the stored hash), so a `HashMap<Name, _>` behaves as before.
///
/// Match on the outermost component through [`Name::view`]: a
/// `match name.view() { NameView::Str(parent, s) => .. }` reads like the former
/// `match name { Name::Str(parent, s) => .. }`.
#[derive(Clone)]
pub struct Name(Rc<NameCell>);

/// The shared allocation behind a [`Name`]: its component kind, and the hash
/// of its structure.
///
/// Invariant: `hash` is the structural hash of `kind`, set where the cell is
/// built ([`Name::anonymous`], [`Name::mk_str`], [`Name::mk_num`]) and never
/// changed — a `Name` gives no mutable access to its cell.
struct NameCell {
    hash: u64,
    kind: NameKind,
}

impl PartialEq for Name {
    #[inline]
    fn eq(&self, other: &Name) -> bool {
        Rc::ptr_eq(&self.0, &other.0)
            || (self.0.hash == other.0.hash && self.0.kind == other.0.kind)
    }
}
impl Eq for Name {}
impl std::hash::Hash for Name {
    /// Writes the component chain, exactly as the derived implementation did
    /// when `Name` wrapped the component kind directly.
    #[inline]
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.0.kind.hash(state);
    }
}
impl std::fmt::Debug for Name {
    /// Formats as `Name(<kind>)` — the output of the derived implementation
    /// when `Name` wrapped the component kind directly. Code that hashes or
    /// orders terms by their `Debug` text depends on this spelling.
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_tuple("Name").field(&self.0.kind).finish()
    }
}
impl Default for Name {
    /// The anonymous name.
    fn default() -> Self {
        Name::anonymous()
    }
}

/// The component kind behind a [`Name`]. Private: construct through [`Name`]'s
/// constructors and inspect through [`Name::view`] and the accessor methods.
#[derive(PartialEq, Eq, Hash, Debug, Default)]
enum NameKind {
    /// The anonymous (root) name.
    #[default]
    Anonymous,
    /// A string component: parent name + string.
    Str(Name, String),
    /// A numeric component: parent name + number.
    Num(Name, u64),
}

/// A borrowed view of a [`Name`]'s outermost component, for pattern matching.
///
/// Obtained from [`Name::view`]; mirrors the former public `Name` enum shape.
pub enum NameView<'a> {
    /// The anonymous (root) name.
    Anonymous,
    /// A string component: parent name + string.
    Str(&'a Name, &'a str),
    /// A numeric component: parent name + number.
    Num(&'a Name, u64),
}

impl Name {
    /// Borrow this name's outermost component for matching. O(1).
    #[inline]
    pub fn view(&self) -> NameView<'_> {
        match &self.0.kind {
            NameKind::Anonymous => NameView::Anonymous,
            NameKind::Str(parent, s) => NameView::Str(parent, s.as_str()),
            NameKind::Num(parent, n) => NameView::Num(parent, *n),
        }
    }
    /// The hash of this name's structure, stored when the name was built.
    /// O(1). Equal names have equal hashes; see [`crate::structural_hash`].
    #[inline]
    #[must_use]
    pub(crate) fn structural_hash(&self) -> u64 {
        self.0.hash
    }
    /// The anonymous (root) name.
    #[inline]
    pub fn anonymous() -> Name {
        Name(Rc::new(NameCell {
            hash: crate::structural_hash::NAME_ANONYMOUS,
            kind: NameKind::Anonymous,
        }))
    }
    /// Construct `parent.s` (string component). O(1) in the length of the
    /// name — shares `parent` and reads its stored hash.
    #[inline]
    pub fn mk_str(parent: Name, s: impl Into<String>) -> Name {
        use crate::structural_hash::{mix, mix_bytes, NAME_STR};
        let s: String = s.into();
        let hash = mix_bytes(mix(NAME_STR, parent.0.hash), s.as_bytes());
        Name(Rc::new(NameCell {
            hash,
            kind: NameKind::Str(parent, s),
        }))
    }
    /// Construct `parent.n` (numeric component). O(1) — shares `parent` and
    /// reads its stored hash.
    #[inline]
    pub fn mk_num(parent: Name, n: u64) -> Name {
        use crate::structural_hash::{mix, NAME_NUM};
        let hash = mix(mix(NAME_NUM, parent.0.hash), n);
        Name(Rc::new(NameCell {
            hash,
            kind: NameKind::Num(parent, n),
        }))
    }
    /// Create a simple string name (no parent).
    pub fn str(s: impl Into<String>) -> Self {
        Name::mk_str(Name::anonymous(), s)
    }
    /// Append a string component to this name.
    pub fn append_str(self, s: impl Into<String>) -> Self {
        Name::mk_str(self, s)
    }
    /// Append a numeric component to this name.
    pub fn append_num(self, n: u64) -> Self {
        Name::mk_num(self, n)
    }
    /// Check if this is the anonymous name.
    pub fn is_anonymous(&self) -> bool {
        matches!(&self.0.kind, NameKind::Anonymous)
    }
    /// Create a `Name` from a dot-separated string.
    ///
    /// `Name::from_str("Nat.add.comm")` produces the same as
    /// `Name::str("Nat").append_str("add").append_str("comm")`.
    #[allow(clippy::should_implement_trait)]
    pub fn from_str(s: &str) -> Self {
        let mut parts = s.split('.');
        let first = match parts.next() {
            None | Some("") => return Name::anonymous(),
            Some(f) => f,
        };
        let mut name = Name::str(first);
        for part in parts {
            if part.is_empty() {
                continue;
            }
            if let Ok(n) = part.parse::<u64>() {
                name = name.append_num(n);
            } else {
                name = name.append_str(part);
            }
        }
        name
    }
    /// Returns the depth (number of components) of this name.
    ///
    /// `Anonymous` has depth 0, `Name::str("Nat")` has depth 1,
    /// `Name::str("Nat").append_str("add")` has depth 2.
    pub fn depth(&self) -> usize {
        match &self.0.kind {
            NameKind::Anonymous => 0,
            NameKind::Str(parent, _) | NameKind::Num(parent, _) => 1 + parent.depth(),
        }
    }
    /// Return the last string component of this name, if any.
    ///
    /// For `Nat.add`, returns `Some("add")`.
    pub fn last_str(&self) -> Option<&str> {
        match &self.0.kind {
            NameKind::Anonymous => None,
            NameKind::Str(_, s) => Some(s.as_str()),
            NameKind::Num(parent, _) => parent.last_str(),
        }
    }
    /// Return the last numeric component, if any.
    pub fn last_num(&self) -> Option<u64> {
        match &self.0.kind {
            NameKind::Num(_, n) => Some(*n),
            NameKind::Str(parent, _) => parent.last_num(),
            NameKind::Anonymous => None,
        }
    }
    /// Return the root (top-level) component as a string.
    ///
    /// For `Nat.add.comm`, returns `"Nat"`.
    pub fn root(&self) -> Option<&str> {
        match &self.0.kind {
            NameKind::Anonymous => None,
            NameKind::Str(parent, s) => {
                if parent.is_anonymous() {
                    Some(s.as_str())
                } else {
                    parent.root()
                }
            }
            NameKind::Num(parent, _) => parent.root(),
        }
    }
    /// Return the parent name (prefix with last component removed).
    pub fn prefix(&self) -> Name {
        match &self.0.kind {
            NameKind::Anonymous => Name::anonymous(),
            NameKind::Str(parent, _) | NameKind::Num(parent, _) => parent.clone(),
        }
    }
    /// Check whether this name has `prefix` as a (strict) prefix.
    ///
    /// `Nat.add.comm.has_prefix(Nat)` is `true`.
    pub fn has_prefix(&self, prefix: &Name) -> bool {
        if self == prefix {
            return false;
        }
        let mut current = self.clone();
        loop {
            let parent = match &current.0.kind {
                NameKind::Anonymous => return false,
                NameKind::Str(parent, _) | NameKind::Num(parent, _) => parent.clone(),
            };
            if &parent == prefix {
                return true;
            }
            current = parent;
        }
    }
    /// Collect all components from root to leaf.
    ///
    /// Returns a vector of `(is_num, string_or_num)` pairs.
    pub fn components(&self) -> Vec<String> {
        let mut comps = Vec::new();
        let mut current = self.clone();
        loop {
            let parent = match &current.0.kind {
                NameKind::Anonymous => break,
                NameKind::Str(parent, s) => {
                    comps.push(s.clone());
                    parent.clone()
                }
                NameKind::Num(parent, n) => {
                    comps.push(n.to_string());
                    parent.clone()
                }
            };
            current = parent;
        }
        comps.reverse();
        comps
    }
    /// Reconstruct a `Name` from a list of string components.
    ///
    /// Numeric strings are converted to `Num` components.
    pub fn from_components(comps: &[String]) -> Self {
        let mut name = Name::anonymous();
        for comp in comps {
            if let Ok(n) = comp.parse::<u64>() {
                name = name.append_num(n);
            } else {
                name = name.append_str(comp.as_str());
            }
        }
        name
    }
    /// Replace the last string component with `new_last`.
    ///
    /// If the name ends in a numeric component, appends `new_last` instead.
    pub fn replace_last(self, new_last: impl Into<String>) -> Self {
        match &self.0.kind {
            NameKind::Anonymous => Name::str(new_last),
            NameKind::Str(parent, _) | NameKind::Num(parent, _) => {
                Name::mk_str(parent.clone(), new_last)
            }
        }
    }
    /// Produce a "fresh" version of this name by appending a suffix number.
    ///
    /// Used to avoid name collisions during elaboration.
    pub fn freshen(self, suffix: u64) -> Self {
        self.append_num(suffix)
    }
    /// Check whether this name is in the given namespace.
    ///
    /// A name is in namespace `ns` if it has `ns` as a strict prefix.
    pub fn in_namespace(&self, ns: &Name) -> bool {
        self.has_prefix(ns)
    }
    /// Append a suffix string to this name.
    pub fn with_suffix(self, suffix: impl Into<String>) -> Self {
        self.append_str(suffix)
    }
    /// Convert to a string suitable for use as a Rust identifier.
    ///
    /// Dots and special characters are replaced with underscores.
    pub fn to_ident_string(&self) -> String {
        self.to_string()
            .chars()
            .map(|c| {
                if c.is_alphanumeric() || c == '_' {
                    c
                } else {
                    '_'
                }
            })
            .collect()
    }
    /// Return a new name with the given prefix prepended.
    pub fn prepend(self, prefix: Name) -> Self {
        let comps = self.components();
        let mut name = prefix;
        for comp in comps {
            if let Ok(n) = comp.parse::<u64>() {
                name = name.append_num(n);
            } else {
                name = name.append_str(comp);
            }
        }
        name
    }
    /// Check whether this name is a string name (last component is a string).
    pub fn is_str_name(&self) -> bool {
        matches!(&self.0.kind, NameKind::Str(_, _))
    }
    /// Check whether this name is a numeric name (last component is a number).
    pub fn is_num_name(&self) -> bool {
        matches!(&self.0.kind, NameKind::Num(_, _))
    }
}
/// A bidirectional mapping between names and numeric IDs.
#[allow(dead_code)]
pub struct NameMapping {
    name_to_id: std::collections::HashMap<String, u32>,
    id_to_name: std::collections::HashMap<u32, String>,
    next_id: u32,
}
#[allow(dead_code)]
impl NameMapping {
    /// Creates an empty name mapping.
    pub fn new() -> Self {
        Self {
            name_to_id: std::collections::HashMap::new(),
            id_to_name: std::collections::HashMap::new(),
            next_id: 0,
        }
    }
    /// Registers `name` and returns its ID (or the existing ID).
    pub fn register(&mut self, name: impl Into<String>) -> u32 {
        let name = name.into();
        if let Some(&id) = self.name_to_id.get(&name) {
            return id;
        }
        let id = self.next_id;
        self.next_id += 1;
        self.name_to_id.insert(name.clone(), id);
        self.id_to_name.insert(id, name);
        id
    }
    /// Returns the ID for `name`, or `None`.
    pub fn id_of(&self, name: &str) -> Option<u32> {
        self.name_to_id.get(name).copied()
    }
    /// Returns the name for `id`, or `None`.
    pub fn name_of(&self, id: u32) -> Option<&str> {
        self.id_to_name.get(&id).map(|s| s.as_str())
    }
    /// Returns the total number of registered names.
    pub fn len(&self) -> usize {
        self.name_to_id.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.name_to_id.is_empty()
    }
}
/// A key-value store for diagnostic metadata.
#[allow(dead_code)]
pub struct DiagMeta {
    pub(super) entries: Vec<(String, String)>,
}
#[allow(dead_code)]
impl DiagMeta {
    /// Creates an empty metadata store.
    pub fn new() -> Self {
        Self {
            entries: Vec::new(),
        }
    }
    /// Adds a key-value pair.
    pub fn add(&mut self, key: impl Into<String>, val: impl Into<String>) {
        self.entries.push((key.into(), val.into()));
    }
    /// Returns the value for `key`, or `None`.
    pub fn get(&self, key: &str) -> Option<&str> {
        self.entries
            .iter()
            .find(|(k, _)| k == key)
            .map(|(_, v)| v.as_str())
    }
    /// Returns the number of entries.
    pub fn len(&self) -> usize {
        self.entries.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}
/// A simple sparse bit set.
#[allow(dead_code)]
pub struct SparseBitSet {
    words: Vec<u64>,
}
#[allow(dead_code)]
impl SparseBitSet {
    /// Creates a new bit set that can hold at least `capacity` bits.
    pub fn new(capacity: usize) -> Self {
        let words = capacity.div_ceil(64);
        Self {
            words: vec![0u64; words],
        }
    }
    /// Sets bit `i`.
    pub fn set(&mut self, i: usize) {
        let word = i / 64;
        let bit = i % 64;
        if word < self.words.len() {
            self.words[word] |= 1u64 << bit;
        }
    }
    /// Clears bit `i`.
    pub fn clear(&mut self, i: usize) {
        let word = i / 64;
        let bit = i % 64;
        if word < self.words.len() {
            self.words[word] &= !(1u64 << bit);
        }
    }
    /// Returns `true` if bit `i` is set.
    pub fn get(&self, i: usize) -> bool {
        let word = i / 64;
        let bit = i % 64;
        self.words.get(word).is_some_and(|w| w & (1u64 << bit) != 0)
    }
    /// Returns the number of set bits.
    pub fn count_ones(&self) -> u32 {
        self.words.iter().map(|w| w.count_ones()).sum()
    }
    /// Returns the union with another bit set.
    pub fn union(&self, other: &SparseBitSet) -> SparseBitSet {
        let len = self.words.len().max(other.words.len());
        let mut result = SparseBitSet {
            words: vec![0u64; len],
        };
        for i in 0..self.words.len() {
            result.words[i] |= self.words[i];
        }
        for i in 0..other.words.len() {
            result.words[i] |= other.words[i];
        }
        result
    }
}
/// A set of names with fast membership testing.
#[allow(dead_code)]
pub struct NameSetExt {
    inner: std::collections::HashSet<String>,
}
#[allow(dead_code)]
impl NameSetExt {
    /// Creates an empty name set.
    pub fn new() -> Self {
        Self {
            inner: std::collections::HashSet::new(),
        }
    }
    /// Inserts `name`.
    pub fn insert(&mut self, name: impl Into<String>) {
        self.inner.insert(name.into());
    }
    /// Returns `true` if `name` is in the set.
    pub fn contains(&self, name: &str) -> bool {
        self.inner.contains(name)
    }
    /// Removes `name`.
    pub fn remove(&mut self, name: &str) {
        self.inner.remove(name);
    }
    /// Returns the number of names.
    pub fn len(&self) -> usize {
        self.inner.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
    /// Returns the union with another set.
    pub fn union(&self, other: &NameSetExt) -> NameSetExt {
        let mut result = NameSetExt::new();
        for n in &self.inner {
            result.insert(n.as_str());
        }
        for n in &other.inner {
            result.insert(n.as_str());
        }
        result
    }
    /// Returns the intersection with another set.
    pub fn intersect(&self, other: &NameSetExt) -> NameSetExt {
        let mut result = NameSetExt::new();
        for n in &self.inner {
            if other.contains(n) {
                result.insert(n.as_str());
            }
        }
        result
    }
}
/// A simple stack-based scope tracker.
#[allow(dead_code)]
pub struct ScopeStack {
    names: Vec<String>,
}
#[allow(dead_code)]
impl ScopeStack {
    /// Creates a new empty scope stack.
    pub fn new() -> Self {
        Self { names: Vec::new() }
    }
    /// Pushes a scope name.
    pub fn push(&mut self, name: impl Into<String>) {
        self.names.push(name.into());
    }
    /// Pops the current scope.
    pub fn pop(&mut self) -> Option<String> {
        self.names.pop()
    }
    /// Returns the current (innermost) scope name, or `None`.
    pub fn current(&self) -> Option<&str> {
        self.names.last().map(|s| s.as_str())
    }
    /// Returns the depth of the scope stack.
    pub fn depth(&self) -> usize {
        self.names.len()
    }
    /// Returns `true` if the stack is empty.
    pub fn is_empty(&self) -> bool {
        self.names.is_empty()
    }
    /// Returns the full path as a dot-separated string.
    pub fn path(&self) -> String {
        self.names.join(".")
    }
}
/// A trie (prefix tree) for efficient prefix search over names.
#[allow(dead_code)]
pub struct NameTrieExt {
    children: std::collections::HashMap<char, NameTrieExt>,
    terminal: bool,
    name: Option<String>,
}
#[allow(dead_code)]
impl NameTrieExt {
    /// Creates an empty trie.
    pub fn new() -> Self {
        Self {
            children: std::collections::HashMap::new(),
            terminal: false,
            name: None,
        }
    }
    /// Inserts a name into the trie.
    pub fn insert(&mut self, name: &str) {
        let mut node = self;
        for c in name.chars() {
            node = node.children.entry(c).or_default();
        }
        node.terminal = true;
        node.name = Some(name.to_string());
    }
    /// Returns `true` if `name` is in the trie.
    pub fn contains(&self, name: &str) -> bool {
        let mut node = self;
        for c in name.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return false,
            }
        }
        node.terminal
    }
    /// Collects all names with the given prefix.
    pub fn with_prefix(&self, prefix: &str) -> Vec<String> {
        let mut node = self;
        for c in prefix.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return Vec::new(),
            }
        }
        let mut results = Vec::new();
        node.collect_all(&mut results);
        results
    }
    fn collect_all(&self, out: &mut Vec<String>) {
        if let Some(ref n) = self.name {
            out.push(n.clone());
        }
        for child in self.children.values() {
            let c: &NameTrieExt = child;
            c.collect_all(out);
        }
    }
}
/// A simple event counter with named events.
#[allow(dead_code)]
pub struct EventCounter {
    counts: std::collections::HashMap<String, u64>,
}
#[allow(dead_code)]
impl EventCounter {
    /// Creates a new empty counter.
    pub fn new() -> Self {
        Self {
            counts: std::collections::HashMap::new(),
        }
    }
    /// Increments the counter for `event`.
    pub fn inc(&mut self, event: &str) {
        *self.counts.entry(event.to_string()).or_insert(0) += 1;
    }
    /// Adds `n` to the counter for `event`.
    pub fn add(&mut self, event: &str, n: u64) {
        *self.counts.entry(event.to_string()).or_insert(0) += n;
    }
    /// Returns the count for `event`.
    pub fn get(&self, event: &str) -> u64 {
        self.counts.get(event).copied().unwrap_or(0)
    }
    /// Returns the total count across all events.
    pub fn total(&self) -> u64 {
        self.counts.values().sum()
    }
    /// Resets all counters.
    pub fn reset(&mut self) {
        self.counts.clear();
    }
    /// Returns all event names.
    pub fn event_names(&self) -> Vec<&str> {
        self.counts.keys().map(|s| s.as_str()).collect()
    }
}
/// A set of `Name` values.
///
/// Wraps `HashSet<Name>` for convenient use in the elaborator.
#[derive(Debug, Clone, Default)]
pub struct NameSet {
    pub(super) inner: HashSet<Name>,
}
impl NameSet {
    /// Create an empty `NameSet`.
    pub fn new() -> Self {
        Self {
            inner: HashSet::new(),
        }
    }
    /// Insert a name. Returns `true` if it was newly inserted.
    pub fn insert(&mut self, name: Name) -> bool {
        self.inner.insert(name)
    }
    /// Remove a name. Returns `true` if it was present.
    pub fn remove(&mut self, name: &Name) -> bool {
        self.inner.remove(name)
    }
    /// Check whether the set contains `name`.
    pub fn contains(&self, name: &Name) -> bool {
        self.inner.contains(name)
    }
    /// Number of names in the set.
    pub fn len(&self) -> usize {
        self.inner.len()
    }
    /// Returns `true` if the set is empty.
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
    /// Iterate over all names.
    pub fn iter(&self) -> impl Iterator<Item = &Name> {
        self.inner.iter()
    }
    /// Compute the union with another `NameSet`.
    pub fn union(&self, other: &NameSet) -> NameSet {
        NameSet {
            inner: self.inner.union(&other.inner).cloned().collect(),
        }
    }
    /// Compute the intersection with another `NameSet`.
    pub fn intersection(&self, other: &NameSet) -> NameSet {
        NameSet {
            inner: self.inner.intersection(&other.inner).cloned().collect(),
        }
    }
    /// Compute the difference `self \ other`.
    pub fn difference(&self, other: &NameSet) -> NameSet {
        NameSet {
            inner: self.inner.difference(&other.inner).cloned().collect(),
        }
    }
    /// Filter to names in a given namespace.
    pub fn in_namespace(&self, ns: &Name) -> NameSet {
        NameSet {
            inner: self
                .inner
                .iter()
                .filter(|n| n.has_prefix(ns))
                .cloned()
                .collect(),
        }
    }
    /// Convert to a sorted vector.
    pub fn to_sorted_vec(&self) -> Vec<Name> {
        let mut v: Vec<Name> = self.inner.iter().cloned().collect();
        v.sort();
        v
    }
}
/// A key-value annotation table for arbitrary metadata.
#[allow(dead_code)]
pub struct AnnotationTable {
    map: std::collections::HashMap<String, Vec<String>>,
}
#[allow(dead_code)]
impl AnnotationTable {
    /// Creates an empty annotation table.
    pub fn new() -> Self {
        Self {
            map: std::collections::HashMap::new(),
        }
    }
    /// Adds an annotation value for the given key.
    pub fn annotate(&mut self, key: impl Into<String>, val: impl Into<String>) {
        self.map.entry(key.into()).or_default().push(val.into());
    }
    /// Returns all annotations for `key`.
    pub fn get_all(&self, key: &str) -> &[String] {
        self.map.get(key).map(|v| v.as_slice()).unwrap_or(&[])
    }
    /// Returns the number of distinct annotation keys.
    pub fn num_keys(&self) -> usize {
        self.map.len()
    }
    /// Returns `true` if the table has any annotations for `key`.
    pub fn has(&self, key: &str) -> bool {
        self.map.contains_key(key)
    }
}
/// A simple LRU cache backed by a linked list + hash map.
#[allow(dead_code)]
pub struct SimpleLruCache<K: std::hash::Hash + Eq + Clone, V: Clone> {
    capacity: usize,
    map: std::collections::HashMap<K, usize>,
    keys: Vec<K>,
    vals: Vec<V>,
    order: Vec<usize>,
}
#[allow(dead_code)]
impl<K: std::hash::Hash + Eq + Clone, V: Clone> SimpleLruCache<K, V> {
    /// Creates a new LRU cache with the given capacity.
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        Self {
            capacity,
            map: std::collections::HashMap::new(),
            keys: Vec::new(),
            vals: Vec::new(),
            order: Vec::new(),
        }
    }
    /// Inserts or updates a key-value pair.
    pub fn put(&mut self, key: K, val: V) {
        // `keys`, `vals` and `order` keep one length, with `order` holding
        // each slot index once (most recently used first) and the length at
        // most `capacity`, also when a call unwinds out of user code (`Clone`,
        // `Hash` or `Eq` of `K`, the drop of a `K` or a `V`): `new` starts
        // them empty, and every change below to a length or to `order` is a
        // step that runs no user code and cannot fail, with its branch's user
        // code (and the `reserve`s, which may panic) before the first such
        // step or after the last. Every index in `map` is a slot index.
        if let Some(&idx) = self.map.get(&key) {
            // `map.get` ran `Hash` / `Eq` before any change. The old value's
            // drop runs in this assignment and changes no length.
            self.vals[idx] = val;
            // `idx` is in `order` once, so `retain` removes one index and
            // `insert` puts it back without growing the buffer.
            self.order.retain(|&x| x != idx);
            self.order.insert(0, idx);
            return;
        }
        match self.order.last() {
            // A full cache has `order.len() == keys.len() >= capacity > 0`
            // (`new` asserts `capacity > 0`), so its least recently used slot
            // is `order.last()`.
            Some(&evict_idx) if self.keys.len() >= self.capacity => {
                // The user code that comes before any change: the clone that
                // goes into the map, and `Hash` / `Eq` in removing the evicted
                // key from the map (a panic there leaves the map as it was).
                // The removed key is held and dropped at the end.
                let map_key = key.clone();
                let removed = self.map.remove_entry(&self.keys[evict_idx]);
                // Moves that run no user code: the slot takes the new key and
                // value, and `rotate_right` takes the evicted index from the
                // back of `order` to the front. No length changes.
                let old_key = std::mem::replace(&mut self.keys[evict_idx], key);
                let old_val = std::mem::replace(&mut self.vals[evict_idx], val);
                self.order.rotate_right(1);
                // The user code that comes after: `Hash` / `Eq` in the map's
                // insertion, then the drops of the evicted key and value.
                self.map.insert(map_key, evict_idx);
                drop((removed, old_key, old_val));
            }
            // Not full: a new slot. (With the lengths equal, `order` is never
            // empty while `keys.len() >= capacity`.)
            _ => {
                let map_key = key.clone();
                let idx = self.keys.len();
                // Reserving first, the three appends below allocate nothing
                // and cannot fail, so the lists grow together; `Hash` / `Eq`
                // in the map's insertion run after them.
                self.keys.reserve(1);
                self.vals.reserve(1);
                self.order.reserve(1);
                self.keys.push(key);
                self.vals.push(val);
                self.order.insert(0, idx);
                self.map.insert(map_key, idx);
            }
        }
    }
    /// Returns a reference to the value for `key`, promoting it.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        // `map.get` runs `Hash` / `Eq` before any change; `idx` is in `order`
        // once (see `put`), so `retain` and `insert` change no length.
        let idx = *self.map.get(key)?;
        self.order.retain(|&x| x != idx);
        self.order.insert(0, idx);
        Some(&self.vals[idx])
    }
    /// Returns the number of entries.
    pub fn len(&self) -> usize {
        self.keys.len()
    }
    /// Returns `true` if empty.
    pub fn is_empty(&self) -> bool {
        self.keys.is_empty()
    }
}
/// A slot that can hold a value, with lazy initialization.
#[allow(dead_code)]
pub struct Slot<T> {
    inner: Option<T>,
}
#[allow(dead_code)]
impl<T> Slot<T> {
    /// Creates an empty slot.
    pub fn empty() -> Self {
        Self { inner: None }
    }
    /// Fills the slot with `val`.  Panics if already filled.
    pub fn fill(&mut self, val: T) {
        assert!(self.inner.is_none(), "Slot: already filled");
        self.inner = Some(val);
    }
    /// Returns the slot's value, or `None`.
    pub fn get(&self) -> Option<&T> {
        self.inner.as_ref()
    }
    /// Returns `true` if the slot is filled.
    pub fn is_filled(&self) -> bool {
        self.inner.is_some()
    }
    /// Takes the value out of the slot.
    pub fn take(&mut self) -> Option<T> {
        self.inner.take()
    }
    /// Fills the slot if empty, returning a reference to the value.
    pub fn get_or_fill_with(&mut self, f: impl FnOnce() -> T) -> &T {
        self.inner.get_or_insert_with(f)
    }
}
/// Generates fresh unique names.
#[allow(dead_code)]
pub struct NameGeneratorExt {
    prefix: String,
    counter: u64,
}
#[allow(dead_code)]
impl NameGeneratorExt {
    /// Creates a generator using the given prefix.
    pub fn new(prefix: impl Into<String>) -> Self {
        Self {
            prefix: prefix.into(),
            counter: 0,
        }
    }
    /// Returns the next fresh name.
    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> String {
        let n = self.counter;
        self.counter += 1;
        format!("{}{}", self.prefix, n)
    }
    /// Returns the number of names generated.
    pub fn count(&self) -> u64 {
        self.counter
    }
    /// Resets the counter to zero.
    pub fn reset(&mut self) {
        self.counter = 0;
    }
}
/// A counted-access cache that tracks hit and miss statistics.
#[allow(dead_code)]
#[allow(missing_docs)]
pub struct StatCache<K: std::hash::Hash + Eq + Clone, V: Clone> {
    /// The inner LRU cache.
    pub inner: SimpleLruCache<K, V>,
    /// Number of cache hits.
    pub hits: u64,
    /// Number of cache misses.
    pub misses: u64,
}
#[allow(dead_code)]
impl<K: std::hash::Hash + Eq + Clone, V: Clone> StatCache<K, V> {
    /// Creates a new stat cache with the given capacity.
    pub fn new(capacity: usize) -> Self {
        Self {
            inner: SimpleLruCache::new(capacity),
            hits: 0,
            misses: 0,
        }
    }
    /// Performs a lookup, tracking hit/miss.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let result = self.inner.get(key);
        if result.is_some() {
            self.hits += 1;
        } else {
            self.misses += 1;
        }
        None
    }
    /// Inserts a key-value pair.
    pub fn put(&mut self, key: K, val: V) {
        self.inner.put(key, val);
    }
    /// Returns the hit rate.
    pub fn hit_rate(&self) -> f64 {
        let total = self.hits + self.misses;
        if total == 0 {
            return 0.0;
        }
        self.hits as f64 / total as f64
    }
}
/// Tracks the frequency of items.
#[allow(dead_code)]
pub struct FrequencyTable<T: std::hash::Hash + Eq + Clone> {
    counts: std::collections::HashMap<T, u64>,
}
#[allow(dead_code)]
impl<T: std::hash::Hash + Eq + Clone> FrequencyTable<T> {
    /// Creates a new empty frequency table.
    pub fn new() -> Self {
        Self {
            counts: std::collections::HashMap::new(),
        }
    }
    /// Records one occurrence of `item`.
    pub fn record(&mut self, item: T) {
        *self.counts.entry(item).or_insert(0) += 1;
    }
    /// Returns the frequency of `item`.
    pub fn freq(&self, item: &T) -> u64 {
        self.counts.get(item).copied().unwrap_or(0)
    }
    /// Returns the item with the highest frequency.
    pub fn most_frequent(&self) -> Option<(&T, u64)> {
        self.counts
            .iter()
            .max_by_key(|(_, &v)| v)
            .map(|(k, &v)| (k, v))
    }
    /// Returns the total number of recordings.
    pub fn total(&self) -> u64 {
        self.counts.values().sum()
    }
    /// Returns the number of distinct items.
    pub fn distinct(&self) -> usize {
        self.counts.len()
    }
}
/// A counter that dispenses monotonically increasing `TypedId` values.
#[allow(dead_code)]
pub struct IdDispenser<T> {
    next: u32,
    _phantom: std::marker::PhantomData<T>,
}
#[allow(dead_code)]
impl<T> IdDispenser<T> {
    /// Creates a new dispenser starting from zero.
    pub fn new() -> Self {
        Self {
            next: 0,
            _phantom: std::marker::PhantomData,
        }
    }
    /// Dispenses the next ID.
    #[allow(clippy::should_implement_trait)]
    pub fn next(&mut self) -> TypedId<T> {
        let id = TypedId::new(self.next);
        self.next += 1;
        id
    }
    /// Returns the number of IDs dispensed.
    pub fn count(&self) -> u32 {
        self.next
    }
}
/// A dot-separated qualified name (e.g. `Nat.succ`).
#[allow(dead_code)]
#[allow(missing_docs)]
pub struct QualifiedNameExt {
    /// Component parts of the name.
    pub parts: Vec<String>,
}
#[allow(dead_code)]
impl QualifiedNameExt {
    /// Creates a qualified name from a dot-separated string.
    pub fn from_dot_str(s: &str) -> Self {
        s.parse().unwrap_or_else(|_| unreachable!())
    }
    /// Creates a single-component name.
    pub fn simple(name: impl Into<String>) -> Self {
        Self {
            parts: vec![name.into()],
        }
    }
    /// Returns the last component (unqualified name).
    pub fn unqualified(&self) -> &str {
        self.parts.last().map(|s| s.as_str()).unwrap_or("")
    }
    /// Returns the namespace (all but the last component), or `None`.
    pub fn namespace(&self) -> Option<QualifiedNameExt> {
        if self.parts.len() <= 1 {
            return None;
        }
        let parts = self.parts[..self.parts.len() - 1].to_vec();
        Some(QualifiedNameExt { parts })
    }
    /// Returns `true` if this name is a sub-name of `other`.
    pub fn is_sub_of(&self, other: &QualifiedNameExt) -> bool {
        self.parts.starts_with(&other.parts)
    }
    /// Returns the number of components.
    pub fn depth(&self) -> usize {
        self.parts.len()
    }
}
/// A memoized computation slot that stores a cached value.
#[allow(dead_code)]
pub struct MemoSlot<T: Clone> {
    cached: Option<T>,
}
#[allow(dead_code)]
impl<T: Clone> MemoSlot<T> {
    /// Creates an uncomputed memo slot.
    pub fn new() -> Self {
        Self { cached: None }
    }
    /// Returns the cached value, computing it with `f` if absent.
    pub fn get_or_compute(&mut self, f: impl FnOnce() -> T) -> &T {
        self.cached.get_or_insert_with(f)
    }
    /// Invalidates the cached value.
    pub fn invalidate(&mut self) {
        self.cached = None;
    }
    /// Returns `true` if the value has been computed.
    pub fn is_cached(&self) -> bool {
        self.cached.is_some()
    }
}