vj-sim 0.3.0

//! Task 31 (`abi` track's wave-A implementation plan, XC-045 **partial**
//! closure — see `docs/CONTRACTS.md`'s "Partial closures (wave A)" entry for
//! the real scoping): a generic, `sv-lang`-free hash-then-verify dedup
//! algorithm (ARCHITECTURE §7 item 7). `Design::compile()` forces
//! `DisableInstanceCaching`, so `sv-lang` never pointer-shares two instance
//! bodies, even textually identical ones — dedup must instead bucket
//! candidates by a cheap hash (the filter) and confirm every same-hash pair
//! pairwise via a ground-truth `same_type` check (the verify) before
//! merging, never trusting hash equality alone.
//!
//! This module implements that algorithm generically, over a caller-supplied
//! `T`/hash/verify triple, so it needs no `sv-lang` dependency at all and
//! stays available under `cargo check -p vj-sim --no-default-features`
//! (`docs/CONTRACTS.md` D4) — unlike [`super::dedup`], which is
//! `#[cfg(feature = "frontend")]`-only and concrete over real
//! `sv_lang::Symbol` instance bodies.
//!
//! **Deviation from the wave-A `abi` plan's literal file location**
//! (`netlist/dedup.rs`, described there as a "new — additive module"): by
//! the time this task ran, `netlist/dedup.rs` already held real,
//! `sv-lang`-specific production code the `netlist` track landed
//! independently and earlier (`netlist` Task 2/3 —
//! `TemplateKey`/`merge_groups_within_bucket`/`confirm_and_assign_symbol_keys`,
//! `#[cfg(feature = "frontend")]`-gated, `git log` shows commits `5115693`
//! "netlist task 2" and `f53bf9f` "netlist task 3" already on this branch).
//! That module is owned by the `netlist` track (`docs/CONTRACTS.md`:
//! "`vj-sim::netlist` (owner: **netlist**)"). Landing this task's
//! generic algorithm there would either silently overwrite the `netlist`
//! track's real, tested production code, or force this sv-lang-free
//! algorithm behind the `frontend` feature it explicitly does not need
//! (every item in that file is `#[cfg(feature = "frontend")]` via
//! `netlist/mod.rs`'s `mod dedup;`). Instead this task lands its algorithm
//! as its own unconditional sibling module, `netlist::dedup_algorithm`
//! (this file), added to `netlist/mod.rs` outside the `frontend` gate —
//! the exact "append an unconditional item to `netlist/mod.rs` for a
//! cross-cutting `abi`-track concern" pattern Task 30 already used for
//! XC-039's `#[cfg(test)] mod tests` block there. The `netlist` track's own
//! `merge_groups_within_bucket` (`dedup.rs`) already independently
//! implements this exact same algorithm shape, concretely, against real
//! `sv_lang::Symbol` bodies (and — per `netlist/dedup_verification.md` —
//! has already been verified live against several real parameterized SV
//! fixtures); this module is the generic, reusable building block the
//! ledger row asks for, kept as a separate, directly unit-testable surface
//! rather than duplicated into or grafted onto the `netlist` track's file.

use std::collections::HashMap;
use std::hash::Hash;

/// Groups `items` into merge-groups via ARCHITECTURE §7 item 7's
/// hash-then-verify algorithm: bucket by `hash_of` (the candidate filter —
/// decides which pairs are even compared), then within each bucket, greedily
/// grow groups by confirming every candidate pairwise, against the group's
/// own first ("canonical") member, via `same_type` (the ground truth —
/// decides whether a same-hash pair actually merges). A hash collision
/// without a matching `same_type` result never merges two items, however
/// the hash landed them in the same bucket — the exact property XC-045's
/// acceptance names.
///
/// Returns groups of item-indices into `items`, each group dedup-able into
/// one compiled `Template`; both outer groups (by first-seen bucket order)
/// and indices within a group (first-seen order) are deterministic given a
/// deterministic `hash_of`/`same_type`.
///
/// Complexity is **not** a universal `O(total items)` bound — that claim
/// was checked in an earlier revision of this doc comment and was false; see
/// below for the verified bound.
///
/// Calls `same_type` at most `items.len() - 1` times in total **only in the
/// best case**, where every same-hash item within a bucket ultimately merges
/// into a single group: each successful merge immediately marks the
/// compared item `assigned`, removing it from every later comparison, so the
/// whole bucket costs one call per non-first item, i.e. `O(total items)`.
///
/// That bound does **not** hold when same-hash items fail to merge. A failed
/// `same_type` call leaves both items unassigned, so a candidate that never
/// matches any earlier canonical becomes a new canonical itself and is then
/// compared against by every later item in the bucket. In the fully
/// adversarial case — a bucket of `k` items whose `same_type` always returns
/// `false` (a hash collision between `k` genuinely different types, exactly
/// the case hash-then-verify dedup exists to reject) — every one of the
/// `k*(k-1)/2` pairs within the bucket gets exactly one `same_type` call,
/// i.e. `O(bucket_size^2)`, not `O(bucket_size)`. See
/// `worst_case_all_distinct_same_hash_is_quadratic_in_same_type_calls` below,
/// which pins this real behavior with a call counter (N=100 => 4950 calls).
///
/// So: this function calls `same_type` `O(total items)` times only when most
/// same-hash items in a bucket end up merging into few groups; when hash
/// collisions occur between items that mostly do *not* match each other, it
/// degrades to `O(bucket_size^2)` `same_type` calls per such bucket.
/// ARCHITECTURE §7 item 7's `O(total instances)` bound is about
/// *elaboration* walking every instance before dedup runs at all — it does
/// not by itself imply, and this function does not provide, a worst-case
/// linear bound on `same_type` calls when same-hash buckets contain many
/// mutually non-matching items.
pub fn hash_then_verify_dedup<T, H: Eq + Hash + Clone>(
    items: &[T],
    hash_of: impl Fn(&T) -> H,
    same_type: impl Fn(&T, &T) -> bool,
) -> Vec<Vec<usize>> {
    // Bucket by hash (the filter), preserving first-seen order both for
    // buckets and for entries within a bucket.
    let mut bucket_order: Vec<H> = Vec::new();
    let mut buckets: HashMap<H, Vec<usize>> = HashMap::new();
    for (index, item) in items.iter().enumerate() {
        let key = hash_of(item);
        if !buckets.contains_key(&key) {
            bucket_order.push(key.clone());
        }
        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-hash bucket: greedily grow groups, confirming
        // every addition pairwise against the group's own canonical (first)
        // member via `same_type` (the ground truth). A same-hash 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 = &items[indices[a]];
            let mut group = vec![indices[a]];
            assigned[a] = true;
            for b in (a + 1)..indices.len() {
                if assigned[b] {
                    continue;
                }
                let candidate = &items[indices[b]];
                if same_type(canonical, candidate) {
                    group.push(indices[b]);
                    assigned[b] = true;
                }
            }
            groups.push(group);
        }
    }
    groups
}

#[cfg(test)]
mod tests {
    use super::hash_then_verify_dedup;
    use std::cell::Cell;

    /// Hash bucketing alone determines the candidate set — verify only
    /// narrows within a bucket, never merges across one. Three items with
    /// three distinct hashes, `same_type` always `true`: since no two items
    /// ever share a bucket, `same_type` is never even called, and the
    /// result must be 3 singleton groups regardless of what `same_type`
    /// would have said.
    #[test]
    fn distinct_hashes_never_merge() {
        let items = [10u32, 20, 30];
        let groups = hash_then_verify_dedup(&items, |x| *x, |_, _| true);

        assert_eq!(groups.len(), 3, "three distinct hashes => three groups");
        for group in &groups {
            assert_eq!(group.len(), 1, "no two items should ever be merged");
        }
    }

    /// The core ARCHITECTURE §7 item 7 property, and XC-045's literal
    /// acceptance: two items with the SAME hash, but `same_type` returns
    /// `false` for that pair, must never merge. A hash collision without a
    /// matching pairwise verify does not merge, however tempting the hash
    /// equality looks.
    #[test]
    fn same_hash_but_same_type_false_never_merges() {
        let items = ["left".to_string(), "right".to_string()];
        // Constant hash: both items land in the same bucket regardless of
        // content, forcing the pairwise verify to run.
        let groups = hash_then_verify_dedup(&items, |_| 0u32, |_, _| false);

        assert_eq!(
            groups.len(),
            2,
            "a hash collision without a matching same_type verify must not merge"
        );
        assert_eq!(groups[0].len(), 1);
        assert_eq!(groups[1].len(), 1);
    }

    /// Two items, same hash, `same_type` returns `true`: they collapse into
    /// one merge-group of size 2.
    #[test]
    fn same_hash_and_same_type_true_merges() {
        let items = ["left".to_string(), "right".to_string()];
        let groups = hash_then_verify_dedup(&items, |_| 0u32, |_, _| true);

        assert_eq!(groups.len(), 1, "same hash + same_type true => one group");
        assert_eq!(groups[0], vec![0, 1]);
    }

    /// Property/perf-shape test: with N=100 items all hashing identically
    /// (the worst case for bucketing — every item lands in one bucket) and
    /// `same_type` always `true`, `same_type` must be called exactly N-1
    /// times, not O(N^2) — each new item is compared against one
    /// representative of its bucket/group, never against every previously
    /// seen item pairwise. This is the O(total items) complexity bound
    /// ARCHITECTURE §7 item 7 requires, made concrete and regression-tested
    /// via a call counter, not merely asserted in prose.
    #[test]
    fn o_of_total_items_not_o_of_templates() {
        let items: Vec<u32> = (0..100).collect();
        let call_count = Cell::new(0usize);

        let groups = hash_then_verify_dedup(
            &items,
            |_| 0u32, // one bucket for all 100 items: the worst case
            |_, _| {
                call_count.set(call_count.get() + 1);
                true
            },
        );

        assert_eq!(groups.len(), 1, "same_type always true => one merged group");
        assert_eq!(groups[0].len(), 100);
        assert_eq!(
            call_count.get(),
            99,
            "same_type must be called exactly N-1 times (each of the 99 \
             non-first items compared once against its group's canonical \
             member), never O(N^2) pairwise comparisons"
        );
    }

    /// The real worst case, which `o_of_total_items_not_o_of_templates`
    /// above does *not* exercise: N=100 items, all sharing one hash bucket
    /// (a hash collision), but `same_type` always returns `false` — i.e. the
    /// bucket actually holds 100 genuinely distinct types that merely
    /// collided on hash, the exact scenario hash-then-verify dedup exists to
    /// handle correctly. Because no comparison ever succeeds, no item is
    /// ever removed from consideration by a merge; every one of the
    /// `100 * 99 / 2 = 4950` pairs within the bucket is compared exactly
    /// once. This pins the true `O(bucket_size^2)` behavior documented on
    /// `hash_then_verify_dedup`: it would fail (at 4950 calls, not some
    /// smaller number) if a future change accidentally re-compared already
    /// non-matching pairs, and it fails today against any claim that this
    /// function is worst-case `O(total items)`.
    #[test]
    fn worst_case_all_distinct_same_hash_is_quadratic_in_same_type_calls() {
        let items: Vec<u32> = (0..100).collect();
        let call_count = Cell::new(0usize);

        let groups = hash_then_verify_dedup(
            &items,
            |_| 0u32, // one bucket for all 100 items: a hash collision
            |_, _| {
                call_count.set(call_count.get() + 1);
                false // every pair is genuinely a different type
            },
        );

        assert_eq!(
            groups.len(),
            100,
            "same_type always false => every item is its own singleton group"
        );
        for group in &groups {
            assert_eq!(group.len(), 1);
        }
        assert_eq!(
            call_count.get(),
            100 * 99 / 2,
            "a same-hash bucket of N mutually-non-matching items costs \
             N*(N-1)/2 same_type calls (O(N^2)), not O(N): this is the real, \
             documented worst case, not a bug to be 'fixed' by changing this \
             assertion — see the complexity discussion on \
             hash_then_verify_dedup's doc comment"
        );
    }
}