sv_sim_sim/netlist/

dedup.rs

//! Task 2 (NL-004, NL-011, NL-012, NL-013): `TemplateKey` hash-then-verify
//! `Template` dedup (Decision 2). `Design::compile()` forces
//! `DisableInstanceCaching` (ARCHITECTURE §7 item 7): `sv-lang` itself never
//! pointer-shares two instance bodies, even textually identical ones, so
//! this module reconstructs that sharing at the netlist layer instead.
//! `TemplateKey` (built by [`template_key_of`]) is a candidate-bucketing
//! filter ONLY — [`merge_groups_within_bucket`] never merges two bodies on
//! `TemplateKey` equality alone; every same-key pair is confirmed pairwise
//! via `Symbol::instance_body_has_same_type` (the ground truth) before
//! merging.

use crate::netlist::{ElabError, SymbolKey, TemplateKey};
use crate::symid::SymbolUid;
use std::collections::HashMap;
use std::hash::{Hash, Hasher};

/// Interns a definition `Symbol` (`instance_body_definition()`) to a stable
/// dense id, keyed by `SymbolUid::uid() -> crate::symid::SymbolId` — the
/// hierarchical-path-keyed, `Hash + Eq + Clone` stable key `sv-lang` itself
/// publishes for exactly this purpose (verified at pinned `sv-lang = "=0.1.9"`,
/// `ast.rs:5205-5226`).
#[derive(Default)]
pub(crate) struct DefinitionTable {
    by_id: HashMap<crate::symid::SymbolId, u32>,
}

impl DefinitionTable {
    pub(crate) fn intern(&mut self, def: sv_lang::Symbol<'_>) -> u32 {
        let next_id = self.by_id.len() as u32;
        *self.by_id.entry(def.uid()).or_insert(next_id)
    }
}

/// Builds a `TemplateKey` (Decision 2: hash-then-verify, not pointer
/// identity) from an instantiated body's `instance_body_definition()` (the
/// `Definition`-identity half) and the owning instance's elaborated
/// `parameters()` (the resolved-parameter half). `params_hash` is a
/// candidate-bucketing filter only — `elaborate()`'s dedup pass NEVER merges
/// two bodies on `TemplateKey` equality alone; every same-key pair is
/// confirmed pairwise via `Symbol::instance_body_has_same_type` before
/// merging (ground truth per Decision 2 — hash quality only affects
/// performance).
///
/// Deviation from the plan's illustrative signature
/// (`fn template_key_of(defs: &mut DefinitionTable, body: Symbol<'_>) ->
/// TemplateKey`, taking only the instance `body`): verified against pinned
/// `sv-lang = "=0.1.9"` that `Symbol::parameters()`'s own doc/SAFETY comment
/// ("count is 0 for non-instances") means it is populated only when called
/// on an `Instance`-kind symbol, never on that instance's `InstanceBody`
/// (`body`, `SymbolKind::InstanceBody`) — there is no way to read the
/// resolved parameter list starting from `body` alone. This function
/// therefore additionally takes the owning `instance` (`Instance`-kind)
/// symbol so it can call `instance.parameters()` directly; `body`
/// (`instance.instance_body()`) still supplies the `Definition` identity
/// half via `instance_body_definition()`, exactly as planned.
pub(crate) fn template_key_of(
    defs: &mut DefinitionTable,
    instance: sv_lang::Symbol<'_>,
    body: sv_lang::Symbol<'_>,
) -> TemplateKey {
    let definition = body
        .instance_body_definition()
        .map(|def| defs.intern(def))
        .unwrap_or(u32::MAX);

    // Deterministic (fixed-key) hasher: `DefaultHasher::new()` is NOT the
    // per-process-randomized `RandomState` `HashMap` uses — it hashes the
    // same input to the same output across runs within one Rust std build,
    // which is what NL-004's "stable across elaborate() runs" acceptance
    // requires.
    let mut hasher = std::collections::hash_map::DefaultHasher::new();
    for param in instance.parameters() {
        param.name().hash(&mut hasher);
        param.parameter_value().hash(&mut hasher);
    }
    let params_hash = hasher.finish();

    TemplateKey {
        definition,
        params_hash,
    }
}

/// The actual bucket -> merge-group decision, factored out of `elaborate()`'s
/// dedup pass into its own `pub` function specifically so it is directly
/// unit-testable against a FORCED hash collision (NL-013 clause (b)). Every
/// element of `tagged` carries its own `TemplateKey` — normal callers
/// (`elaborate()`) always pass the real `template_key_of(..)` result for each
/// body, but a test may pass two DIFFERENT bodies tagged with the SAME
/// (possibly fabricated) `TemplateKey` to prove the key alone never causes a
/// merge. Two entries land in the same output group iff (a) their supplied
/// `TemplateKey`s are `==` (the filter — decides which pairs are even
/// compared) AND (b) `Symbol::instance_body_has_same_type` returns `true` for
/// their bodies (the ground truth — decides whether same-keyed pairs
/// actually merge). Returns groups as index-sets into `tagged`, in
/// first-seen order within each group; outer groups are emitted in
/// first-seen `TemplateKey` order.
pub fn merge_groups_within_bucket<'d>(
    tagged: &[(TemplateKey, sv_lang::Symbol<'d>)],
) -> Vec<Vec<usize>> {
    // Bucket by TemplateKey (the filter), preserving first-seen order both
    // for buckets and for entries within a bucket.
    let mut bucket_order: Vec<TemplateKey> = Vec::new();
    let mut buckets: HashMap<TemplateKey, Vec<usize>> = HashMap::new();
    for (index, (key, _symbol)) in tagged.iter().enumerate() {
        if !buckets.contains_key(key) {
            bucket_order.push(*key);
        }
        buckets.entry(*key).or_default().push(index);
    }

    let mut groups: Vec<Vec<usize>> = Vec::new();
    for key in bucket_order {
        let indices = &buckets[&key];
        // Within one same-key bucket: greedily grow groups, confirming
        // every addition pairwise against the group's own canonical
        // (first) member via `instance_body_has_same_type` — the ground
        // truth (NL-013 clause (b)). A same-key pair that fails this check
        // never merges, however the hash landed them in the same bucket.
        let mut assigned = vec![false; indices.len()];
        for a in 0..indices.len() {
            if assigned[a] {
                continue;
            }
            let canonical = &tagged[indices[a]].1;
            let mut group = vec![indices[a]];
            assigned[a] = true;
            for b in (a + 1)..indices.len() {
                if assigned[b] {
                    continue;
                }
                let candidate = &tagged[indices[b]].1;
                if canonical.instance_body_has_same_type(candidate) {
                    group.push(indices[b]);
                    assigned[b] = true;
                }
            }
            groups.push(group);
        }
    }
    groups
}

/// Task 3 (NL-015, NL-016): a minimal per-member descriptor used ONLY to
/// defensively re-verify member-for-member equality when confirming a merge
/// (Decision 4) — not the full `SignalDecl` (that's Task 5); just (kind,
/// name) pairs read from `members()`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct MemberShape {
    pub kind: sv_lang_kinds::SymbolKind,
    pub name: String,
}

/// (Revision, resolving a blocking review finding — Deviation #18.) The
/// return payload of [`confirm_and_assign_symbol_keys`], split into:
/// `shapes`, `(SymbolKey, MemberShape)` pairs read off `canonical`'s own
/// members, in `SymbolKey` order; and `per_body_symbols`, the same lockstep
/// walk's real `sv_lang::Symbol<'d>` handles, one `Vec` per body in
/// `[canonical, others[0], others[1], ..]` order, each `Vec` `SymbolKey`-
/// ordered identically to `shapes` (member `i` of every body's `Vec` is "the
/// same" logical member, by construction of the lockstep walk).
pub struct ConfirmedMembers<'d> {
    pub shapes: Vec<(SymbolKey, MemberShape)>,
    pub per_body_symbols: Vec<Vec<sv_lang::Symbol<'d>>>,
}

/// Re-asserts member-for-member (kind, name) equality across every body
/// already confirmed by `instance_body_has_same_type`, walking `members()`
/// of both bodies in lockstep, and assigns the SAME dense `SymbolKey`
/// (`canonical`'s own `members()` position) to matching members across every
/// body in the group (Decision 4: "the code re-asserts defensively as a
/// fuzz-testable invariant... a merge that silently drops a mismatch is a
/// correctness bug, not a warning"). Returns
/// `Err(ElabError::MergeInvariantViolated)` — never a panic, never a silent
/// skip of the mismatching member — on any disagreement, even though
/// `instance_body_has_same_type` already said `true` (defense in depth
/// against NL-019's still-open verification gap): this function never itself
/// calls `instance_body_has_same_type` and is fully independent of it, which
/// is exactly what lets a test simulate "the oracle said yes but our own
/// re-check disagrees" by calling this function directly with two bodies
/// that were never actually confirmed by the oracle.
///
/// A member-count mismatch (one body has more/fewer members than
/// `canonical`) is also a `MergeInvariantViolated`, reported at the index one
/// past the shorter body's last member.
pub fn confirm_and_assign_symbol_keys<'d>(
    canonical: sv_lang::Symbol<'d>,
    others: &[sv_lang::Symbol<'d>],
) -> Result<ConfirmedMembers<'d>, ElabError> {
    let canonical_members: Vec<sv_lang::Symbol<'d>> = canonical.members().collect();

    let shapes: Vec<(SymbolKey, MemberShape)> = canonical_members
        .iter()
        .enumerate()
        .map(|(i, m)| {
            (
                SymbolKey(i as u32),
                MemberShape {
                    kind: m.kind(),
                    name: m.name().to_string(),
                },
            )
        })
        .collect();

    let mut per_body_symbols: Vec<Vec<sv_lang::Symbol<'d>>> = Vec::with_capacity(others.len() + 1);
    per_body_symbols.push(canonical_members.clone());

    for other in others {
        let other_members: Vec<sv_lang::Symbol<'d>> = other.members().collect();

        for (i, canonical_member) in canonical_members.iter().enumerate() {
            let Some(other_member) = other_members.get(i) else {
                return Err(ElabError::MergeInvariantViolated {
                    canonical_hier_path: canonical.hierarchical_path(),
                    other_hier_path: other.hierarchical_path(),
                    member_index: i,
                    detail: format!(
                        "other body has only {} member(s), canonical has member {} (`{}`, {:?})",
                        other_members.len(),
                        i,
                        canonical_member.name(),
                        canonical_member.kind(),
                    ),
                });
            };
            if other_member.kind() != canonical_member.kind()
                || other_member.name() != canonical_member.name()
            {
                return Err(ElabError::MergeInvariantViolated {
                    canonical_hier_path: canonical.hierarchical_path(),
                    other_hier_path: other.hierarchical_path(),
                    member_index: i,
                    detail: format!(
                        "member {i} mismatch: canonical `{}` ({:?}) vs other `{}` ({:?})",
                        canonical_member.name(),
                        canonical_member.kind(),
                        other_member.name(),
                        other_member.kind(),
                    ),
                });
            }
        }

        if other_members.len() != canonical_members.len() {
            return Err(ElabError::MergeInvariantViolated {
                canonical_hier_path: canonical.hierarchical_path(),
                other_hier_path: other.hierarchical_path(),
                member_index: canonical_members.len(),
                detail: format!(
                    "other body has {} member(s), canonical has only {}",
                    other_members.len(),
                    canonical_members.len(),
                ),
            });
        }

        per_body_symbols.push(other_members);
    }

    Ok(ConfirmedMembers {
        shapes,
        per_body_symbols,
    })
}