weir/

resident_cache_identity.rs

use crate::fixed_point_graph::FixedPointAnalysisKind;
use std::cmp::Ordering;

/// Resident graph cache domain participating in shared cache identity.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum ResidentGraphCacheDomain {
    /// Prepared IFDS exploded-supergraph CSR buffers.
    IfdsCsr,
    /// Fixed-point forward graph buffers for one analysis family.
    FixedPoint(FixedPointAnalysisKind),
}

impl ResidentGraphCacheDomain {
    /// Stable numeric code used by deterministic evidence ordering and digests.
    #[must_use]
    pub const fn code(self) -> u8 {
        match self {
            Self::IfdsCsr => 1,
            Self::FixedPoint(FixedPointAnalysisKind::Generic) => 16,
            Self::FixedPoint(FixedPointAnalysisKind::Reaching) => 17,
            Self::FixedPoint(FixedPointAnalysisKind::Live) => 18,
            Self::FixedPoint(FixedPointAnalysisKind::PointsToSubset) => 19,
            Self::FixedPoint(FixedPointAnalysisKind::Slice) => 20,
        }
    }
}

/// Backend-neutral resident graph cache identity shared by IFDS and
/// fixed-point resident caches.
///
/// The tuple is intentionally not just `layout_hash`: resident handles are
/// backend-owned, backend-version-sensitive resources, and solver scratch
/// compatibility depends on the shape carried beside the layout hash.
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct ResidentGraphCacheIdentity {
    /// Resident cache domain and analysis family.
    pub domain: ResidentGraphCacheDomain,
    /// Stable backend/device family id.
    pub backend_id: &'static str,
    /// Stable backend implementation version.
    pub backend_version: &'static str,
    /// Deterministic graph layout/content hash.
    pub layout_hash: u64,
    /// Graph node count used by resident solver scratch.
    pub node_count: u32,
    /// Graph edge count used by resident uploads and diagnostics.
    pub edge_count: u32,
    /// Frontier bitset word count required by the resident solve.
    pub frontier_words: u32,
}

impl ResidentGraphCacheIdentity {
    /// Identity for a prepared IFDS resident CSR.
    #[must_use]
    pub const fn ifds_csr(
        backend_id: &'static str,
        backend_version: &'static str,
        layout_hash: u64,
        node_count: u32,
        edge_count: u32,
        frontier_words: u32,
    ) -> Self {
        Self {
            domain: ResidentGraphCacheDomain::IfdsCsr,
            backend_id,
            backend_version,
            layout_hash,
            node_count,
            edge_count,
            frontier_words,
        }
    }

    /// Identity for a fixed-point resident graph.
    #[must_use]
    pub const fn fixed_point(
        backend_id: &'static str,
        backend_version: &'static str,
        analysis_kind: FixedPointAnalysisKind,
        layout_hash: u64,
        node_count: u32,
        edge_count: u32,
        frontier_words: u32,
    ) -> Self {
        Self {
            domain: ResidentGraphCacheDomain::FixedPoint(analysis_kind),
            backend_id,
            backend_version,
            layout_hash,
            node_count,
            edge_count,
            frontier_words,
        }
    }

    /// Tuple-boundary-preserving 64-bit digest for compact release evidence.
    #[must_use]
    pub fn stable_digest64(&self) -> u64 {
        const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
        const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

        fn mix(mut hash: u64, bytes: &[u8]) -> u64 {
            for byte in bytes {
                hash ^= u64::from(*byte);
                hash = hash.wrapping_mul(FNV_PRIME);
            }
            hash
        }

        let mut hash = FNV_OFFSET;
        hash = mix(hash, b"weir-resident-graph-cache-identity-v1\0domain\0");
        hash = mix(hash, &[self.domain.code()]);
        hash = mix(hash, b"\0backend-id\0");
        hash = mix(hash, self.backend_id.as_bytes());
        hash = mix(hash, b"\0backend-version\0");
        hash = mix(hash, self.backend_version.as_bytes());
        hash = mix(hash, b"\0layout\0");
        hash = mix(hash, &self.layout_hash.to_le_bytes());
        hash = mix(hash, b"\0nodes\0");
        hash = mix(hash, &self.node_count.to_le_bytes());
        hash = mix(hash, b"\0edges\0");
        hash = mix(hash, &self.edge_count.to_le_bytes());
        hash = mix(hash, b"\0frontier-words\0");
        mix(hash, &self.frontier_words.to_le_bytes())
    }

    /// Deterministic ordering for cache snapshots and release evidence.
    #[must_use]
    pub fn cmp_stable(&self, other: &Self) -> Ordering {
        (
            self.domain.code(),
            self.backend_id,
            self.backend_version,
            self.layout_hash,
            self.node_count,
            self.edge_count,
            self.frontier_words,
        )
            .cmp(&(
                other.domain.code(),
                other.backend_id,
                other.backend_version,
                other.layout_hash,
                other.node_count,
                other.edge_count,
                other.frontier_words,
            ))
    }
}

/// Adjacent cache identity evidence used to explain resident graph misses.
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct ResidentGraphCacheMissEvidence {
    /// Total resident graph cache entries inspected.
    pub total_entries: usize,
    /// Entries in the same resident graph domain.
    pub same_domain_entries: usize,
    /// Entries with the same domain, backend id, and backend version.
    pub same_backend_entries: usize,
    /// Entries with the same domain, backend identity, and layout hash.
    pub same_layout_entries: usize,
    /// Entries with matching domain, backend, layout, node, edge, and frontier
    /// word counts.
    pub same_shape_entries: usize,
}

impl ResidentGraphCacheMissEvidence {
    /// Build miss evidence from cache identities adjacent to a requested key.
    #[must_use]
    pub fn from_identities<'a>(
        cached: impl Iterator<Item = &'a ResidentGraphCacheIdentity>,
        requested: &ResidentGraphCacheIdentity,
    ) -> Self {
        let mut evidence = Self::default();
        for identity in cached {
            evidence.total_entries += 1;
            if identity.domain == requested.domain {
                evidence.same_domain_entries += 1;
                if identity.backend_id == requested.backend_id
                    && identity.backend_version == requested.backend_version
                {
                    evidence.same_backend_entries += 1;
                    if identity.layout_hash == requested.layout_hash {
                        evidence.same_layout_entries += 1;
                        if identity.node_count == requested.node_count
                            && identity.edge_count == requested.edge_count
                            && identity.frontier_words == requested.frontier_words
                        {
                            evidence.same_shape_entries += 1;
                        }
                    }
                }
            }
        }
        evidence
    }
}

/// Backend-neutral resident cache-miss reason for diagnostics and release
/// evidence.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum ResidentGraphCacheMissReason {
    /// The resident graph cache has no entries.
    EmptyCache,
    /// Entries exist but for a different resident graph domain.
    DomainChanged,
    /// The same domain exists but backend id or backend version changed.
    BackendChanged,
    /// Domain and backend match, but the graph layout/content hash changed.
    LayoutChanged,
    /// Domain, backend, and layout hash matched, but shape fields differ.
    ShapeChanged,
    /// Adjacent identity says the entry should exist, but the final key missed.
    KeyAbsent,
}

impl ResidentGraphCacheMissReason {
    /// Classify a resident graph cache miss from adjacent identity evidence.
    #[must_use]
    pub const fn classify(evidence: ResidentGraphCacheMissEvidence) -> Self {
        if evidence.total_entries == 0 {
            Self::EmptyCache
        } else if evidence.same_domain_entries == 0 {
            Self::DomainChanged
        } else if evidence.same_backend_entries == 0 {
            Self::BackendChanged
        } else if evidence.same_layout_entries == 0 {
            Self::LayoutChanged
        } else if evidence.same_shape_entries == 0 {
            Self::ShapeChanged
        } else {
            Self::KeyAbsent
        }
    }

    /// Stable metric suffix for cache telemetry.
    #[must_use]
    pub const fn metric_suffix(self) -> &'static str {
        match self {
            Self::EmptyCache => "empty_cache",
            Self::DomainChanged => "domain_changed",
            Self::BackendChanged => "backend_changed",
            Self::LayoutChanged => "layout_changed",
            Self::ShapeChanged => "shape_changed",
            Self::KeyAbsent => "key_absent",
        }
    }
}

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

    fn ifds_identity() -> ResidentGraphCacheIdentity {
        ResidentGraphCacheIdentity::ifds_csr("backend-a", "v1", 0x1111, 64, 8, 2)
    }

    #[test]
    fn resident_graph_identity_digest_separates_cache_compatibility_fields() {
        let base = ifds_identity();

        assert_ne!(
            base.stable_digest64(),
            ResidentGraphCacheIdentity::ifds_csr("backend-b", "v1", 0x1111, 64, 8, 2)
                .stable_digest64()
        );
        assert_ne!(
            base.stable_digest64(),
            ResidentGraphCacheIdentity::ifds_csr("backend-a", "v2", 0x1111, 64, 8, 2)
                .stable_digest64()
        );
        assert_ne!(
            base.stable_digest64(),
            ResidentGraphCacheIdentity::ifds_csr("backend-a", "v1", 0x2222, 64, 8, 2)
                .stable_digest64()
        );
        assert_ne!(
            base.stable_digest64(),
            ResidentGraphCacheIdentity::ifds_csr("backend-a", "v1", 0x1111, 64, 8, 3)
                .stable_digest64()
        );
        assert_ne!(
            base.stable_digest64(),
            ResidentGraphCacheIdentity::fixed_point(
                "backend-a",
                "v1",
                FixedPointAnalysisKind::Reaching,
                0x1111,
                64,
                8,
                2,
            )
            .stable_digest64()
        );
    }

    #[test]
    fn resident_graph_miss_reason_classifies_adjacent_identity() {
        let requested = ifds_identity();
        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities([].iter(), &requested)
            ),
            ResidentGraphCacheMissReason::EmptyCache
        );

        let different_domain = ResidentGraphCacheIdentity::fixed_point(
            "backend-a",
            "v1",
            FixedPointAnalysisKind::Reaching,
            0x1111,
            64,
            8,
            2,
        );
        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities(
                    std::iter::once(&different_domain),
                    &requested,
                )
            ),
            ResidentGraphCacheMissReason::DomainChanged
        );

        let different_backend =
            ResidentGraphCacheIdentity::ifds_csr("backend-b", "v1", 0x1111, 64, 8, 2);
        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities(
                    std::iter::once(&different_backend),
                    &requested,
                )
            ),
            ResidentGraphCacheMissReason::BackendChanged
        );

        let different_layout =
            ResidentGraphCacheIdentity::ifds_csr("backend-a", "v1", 0x2222, 64, 8, 2);
        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities(
                    std::iter::once(&different_layout),
                    &requested,
                )
            ),
            ResidentGraphCacheMissReason::LayoutChanged
        );

        let different_shape =
            ResidentGraphCacheIdentity::ifds_csr("backend-a", "v1", 0x1111, 64, 8, 3);
        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities(
                    std::iter::once(&different_shape),
                    &requested,
                )
            ),
            ResidentGraphCacheMissReason::ShapeChanged
        );

        assert_eq!(
            ResidentGraphCacheMissReason::classify(
                ResidentGraphCacheMissEvidence::from_identities(std::iter::once(&requested), &requested)
            ),
            ResidentGraphCacheMissReason::KeyAbsent
        );
    }
}