vj-codegen 0.1.0

//! Task 23 (CG-014, CG-065): dedup cache -- hash-then-verify, never pointer
//! identity.
//!
//! ARCHITECTURE.md §7 item 7: `Design::compile()` forces
//! `DisableInstanceCaching` (the precondition for `Design: Send + Sync`), so
//! slang never pointer-shares two structurally identical `InstanceBody`s --
//! elaboration always walks every instance (`O(total instances)`, not
//! `O(distinct templates)`). Codegen recovers the sharing it needs itself:
//! bucket by `(Definition, resolved-params)` hash, then confirm every
//! bucket hit pairwise via `Symbol::instance_body_has_same_type` (mirrors
//! `slang::ast::InstanceBodySymbol::hasSameType`) before two `InstanceBody`s
//! are collapsed into one compiled kernel. Trusting the hash alone is
//! exactly the bug this cache exists to prevent (CG-065); see
//! `hash_collision_structurally_different_bodies_yield_two_kernels` in
//! `tests/dedup.rs`.
//!
//! The plan text that introduced this module (Task 23 of
//! `docs/superpowers/plans/2026-09-23-wave-A-codegen.md`) names the key
//! type `sv_lang::DefinitionId`; no such type exists in the real `sv_lang`
//! API. `Symbol::instance_body_definition()` returns the elaborated
//! `Definition` `Symbol`, and `SymbolUid::uid() -> SymbolId` (a stable,
//! hashable hierarchical-path key) is compilation-wide for a `Definition`
//! symbol -- exactly the per-module-type granularity this cache's key
//! needs -- so `SymbolId` is used in `DefinitionId`'s place (adaptation
//! noted in the task's deviations).

use std::collections::HashMap;

use sv_lang::Symbol;
use sv_sim_sim::symid::SymbolId;

use crate::mangle::{EntityTag, mangle_kernel};

/// The stable internal name assigned to one deduplicated compiled kernel
/// body (Task 21's `mangle.rs` `_SV$...` scheme). A plain `String` -- there
/// is no distinct `MangledName` newtype anywhere else in this crate
/// (`mangle::mangle_kernel` itself returns `String`), so this is a type
/// alias rather than a second wrapper around the same data.
pub type MangledName = String;

/// The outcome of [`DedupCache::get_or_insert`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DedupResult {
    /// No structurally-equal `InstanceBody` was cached yet under this
    /// `(definition, param_hash)` bucket -- a fresh kernel entry was
    /// recorded under the returned name and must actually be lowered.
    New(MangledName),
    /// A structurally-equal `InstanceBody` (confirmed via
    /// `Symbol::instance_body_has_same_type`, never via the hash bucket
    /// alone) is already cached under the returned name -- reuse it, never
    /// lower again.
    Existing(MangledName),
}

/// CG-014/CG-065's dedup cache: keys compiled kernels by `(definition,
/// param-binding hash)` and confirms every bucket hit pairwise via
/// `Symbol::instance_body_has_same_type` before treating two
/// `InstanceBody`s as the same compiled kernel. Never keys or compares by
/// `Symbol` pointer identity (`Design::compile()`'s forced
/// `DisableInstanceCaching` means two value-equal instances are guaranteed
/// to be distinct handles -- see `dedup_cache_is_not_pointer_identity`).
///
/// Branded with the `Design`'s lifetime `'d` because a bucket keeps one
/// representative `Symbol<'d>` per (rare) hash collision, to compare
/// future arrivals against.
pub struct DedupCache<'d> {
    // One entry per `(definition, param_hash)` bucket that has been seen so
    // far. Almost always length 1 by the time a bucket stabilizes: a
    // second (or later) entry only appears when `instance_body_has_same_
    // type` disagrees with the hash -- a genuine `DefaultHasher` collision
    // in real use, or a test deliberately forcing one. Each entry pairs the
    // representative `InstanceBody` handle (used only for the pairwise
    // structural check, never as a map key) with the `MangledName` already
    // assigned to it.
    buckets: HashMap<(SymbolId, u64), Vec<(Symbol<'d>, MangledName)>>,
}

impl<'d> Default for DedupCache<'d> {
    fn default() -> Self {
        Self::new()
    }
}

impl<'d> DedupCache<'d> {
    pub fn new() -> Self {
        Self {
            buckets: HashMap::new(),
        }
    }

    /// `def_id` identifies the `InstanceBody`'s elaborated `Definition`
    /// (typically `body.instance_body_definition().unwrap().uid()`).
    /// `param_hash` is the caller-supplied hash half of the dedup key
    /// (typically `mangle::param_binding_hash(&instance)`); it is an
    /// explicit argument, never derived internally, so callers (and tests)
    /// control it exactly -- including deliberately forcing a collision.
    /// `body` is the `InstanceBody` symbol itself, consulted ONLY for the
    /// pairwise `instance_body_has_same_type` verification, never used as
    /// part of the map key (CG-065's "never pointer identity").
    pub fn get_or_insert(
        &mut self,
        def_id: SymbolId,
        param_hash: u64,
        body: Symbol<'d>,
    ) -> DedupResult {
        let def_name = def_id.path().to_string();
        let entries = self.buckets.entry((def_id, param_hash)).or_default();

        for (existing, name) in entries.iter() {
            if existing.instance_body_has_same_type(&body) {
                return DedupResult::Existing(name.clone());
            }
        }

        // No cached representative in this bucket is structurally equal to
        // `body` (bucket was empty, or every representative present is a
        // genuine/forced hash collision with a DIFFERENT real type) -- this
        // is a new kernel. Disambiguate the mangled name by the entry's
        // index within the bucket so two structurally distinct bodies that
        // happen to share one `(def_id, param_hash)` key never also share
        // a `MangledName` (they would otherwise silently collide at the
        // LLVM symbol-name level).
        let local = format!("k{}", entries.len());
        let name = mangle_kernel(&def_name, param_hash, EntityTag::Kernel, &local);
        entries.push((body, name.clone()));
        DedupResult::New(name)
    }
}