//! Validated ordered relationship-type dictionary.

use crate::safety::{GraphError, GraphResult};
use crate::types::EdgeTypeId;
use std::collections::HashMap;

const REGISTRY_FINGERPRINT_SEED: u64 = 0xcbf2_9ce4_8422_2325;

fn fingerprint_append(mut fingerprint: u64, label: &str) -> u64 {
    for byte in (label.len() as u64)
        .to_le_bytes()
        .into_iter()
        .chain(label.bytes())
    {
        fingerprint ^= u64::from(byte);
        fingerprint = fingerprint.wrapping_mul(0x100_0000_01b3);
    }
    fingerprint
}

fn registry_fingerprint<'a>(labels: impl IntoIterator<Item = &'a str>) -> u64 {
    labels
        .into_iter()
        .fold(REGISTRY_FINGERPRINT_SEED, fingerprint_append)
}

/// Ordered labels plus an O(1) label-to-logical-ID lookup.
#[derive(Debug, Clone)]
pub(crate) struct EdgeTypeRegistry {
    labels: Vec<String>,
    ids_by_label: HashMap<String, EdgeTypeId>,
    label_bytes: usize,
    ordered_label_capacity_bytes: usize,
    lookup_label_capacity_bytes: usize,
    fingerprint: u64,
}

impl EdgeTypeRegistry {
    const HASH_ENTRY_OVERHEAD_BYTES: usize = 32;
    pub(crate) const MAX_USER_EDGE_TYPES: usize = 1_000_000;
    pub(crate) const MAX_EDGE_TYPE_LABEL_BYTES: usize = 1_024;
    pub(crate) const MAX_EDGE_TYPE_DICTIONARY_BYTES: usize = 256 * 1024 * 1024;
    pub(crate) const MAX_QUERY_EDGE_TYPE_FILTERS: usize = 4_096;
    pub(crate) const MAX_QUERY_EDGE_TYPE_FILTER_BYTES: usize = 4 * 1024 * 1024;
    pub(crate) const STATUS_EDGE_TYPE_PREVIEW: usize = 64;

    pub(crate) fn new() -> Self {
        Self {
            labels: vec![String::new()],
            ids_by_label: HashMap::new(),
            label_bytes: 0,
            ordered_label_capacity_bytes: 0,
            lookup_label_capacity_bytes: 0,
            fingerprint: registry_fingerprint(std::iter::once("")),
        }
    }

    #[cfg(test)]
    pub(crate) fn new_v6() -> Self {
        Self::new()
    }

    pub(crate) fn try_from_v6_labels(labels: Vec<String>) -> GraphResult<Self> {
        if labels.len() > EdgeTypeId::V6_MAX_USER_ID as usize + 1 {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry count exceeds v6 limits".into(),
            });
        }
        Self::try_from_labels(labels)
    }

    pub(crate) fn try_from_labels(labels: Vec<String>) -> GraphResult<Self> {
        if labels.first().is_none_or(|label| !label.is_empty())
            || labels.len() > u32::MAX as usize
            || labels.iter().skip(1).any(String::is_empty)
        {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry contains invalid labels".into(),
            });
        }
        let label_bytes = labels.iter().try_fold(0_usize, |total, label| {
            total
                .checked_add(label.len())
                .ok_or_else(|| GraphError::CorruptFile {
                    reason: "edge type registry payload overflows".into(),
                })
        })?;
        validate_policy(labels.len(), label_bytes, labels.iter().map(String::as_str))?;
        let mut ids_by_label = HashMap::new();
        ids_by_label
            .try_reserve(labels.len().saturating_sub(1))
            .map_err(|error| {
                GraphError::Internal(format!(
                    "edge type registry lookup allocation failed: {error}"
                ))
            })?;
        for (index, label) in labels.iter().enumerate().skip(1) {
            let logical = EdgeTypeId::try_from(u32::try_from(index).map_err(|_| {
                GraphError::Internal("edge type registry index exceeds u32".into())
            })?)
            .map_err(|_| GraphError::CorruptFile {
                reason: "edge type registry uses the logical sentinel".into(),
            })?;
            let lookup_label = try_clone_label(label)?;
            if ids_by_label.insert(lookup_label, logical).is_some() {
                return Err(GraphError::CorruptFile {
                    reason: "edge type registry contains duplicate labels".into(),
                });
            }
        }
        let ordered_label_capacity_bytes = labels.iter().map(String::capacity).sum();
        let lookup_label_capacity_bytes = ids_by_label.keys().map(String::capacity).sum();
        Ok(Self {
            fingerprint: registry_fingerprint(labels.iter().map(String::as_str)),
            labels,
            ids_by_label,
            label_bytes,
            ordered_label_capacity_bytes,
            lookup_label_capacity_bytes,
        })
    }

    #[cfg(test)]
    pub(crate) fn register_v6(&mut self, label: &str) -> GraphResult<EdgeTypeId> {
        if let Some(id) = self.id(label) {
            return Ok(id);
        }
        if label.is_empty() || self.labels.len() > EdgeTypeId::V6_MAX_USER_ID as usize {
            return Err(GraphError::EdgeTypeLimit);
        }
        self.register(label)
    }

    pub(crate) fn register(&mut self, label: &str) -> GraphResult<EdgeTypeId> {
        if let Some(id) = self.id(label) {
            return Ok(id);
        }
        let next_user_labels = self.labels.len();
        let next_bytes = self
            .label_bytes
            .checked_add(label.len())
            .ok_or(GraphError::EdgeTypeLimit)?;
        if label.is_empty()
            || label.len() > Self::MAX_EDGE_TYPE_LABEL_BYTES
            || next_user_labels > Self::MAX_USER_EDGE_TYPES
            || next_bytes > Self::MAX_EDGE_TYPE_DICTIONARY_BYTES
        {
            return Err(GraphError::EdgeTypeLimit);
        }
        self.register_inner(label)
    }

    fn register_inner(&mut self, label: &str) -> GraphResult<EdgeTypeId> {
        let id =
            EdgeTypeId::try_from(u32::try_from(self.labels.len()).map_err(|_| {
                GraphError::Internal("edge type registry index exceeds u32".into())
            })?)
            .map_err(|_| GraphError::EdgeTypeLimit)?;
        self.labels.try_reserve(1).map_err(|error| {
            GraphError::Internal(format!("edge type registry allocation failed: {error}"))
        })?;
        self.ids_by_label.try_reserve(1).map_err(|error| {
            GraphError::Internal(format!("edge type lookup allocation failed: {error}"))
        })?;
        let ordered_label = try_clone_label(label)?;
        let lookup_label = try_clone_label(label)?;
        self.label_bytes = self
            .label_bytes
            .checked_add(label.len())
            .ok_or(GraphError::EdgeTypeLimit)?;
        self.ordered_label_capacity_bytes = self
            .ordered_label_capacity_bytes
            .checked_add(ordered_label.capacity())
            .ok_or(GraphError::EdgeTypeLimit)?;
        self.lookup_label_capacity_bytes = self
            .lookup_label_capacity_bytes
            .checked_add(lookup_label.capacity())
            .ok_or(GraphError::EdgeTypeLimit)?;
        self.labels.push(ordered_label);
        self.ids_by_label.insert(lookup_label, id);
        self.fingerprint = fingerprint_append(self.fingerprint, label);
        Ok(id)
    }

    pub(crate) fn id(&self, label: &str) -> Option<EdgeTypeId> {
        if label.is_empty() {
            return Some(EdgeTypeId::UNTYPED);
        }
        self.ids_by_label.get(label).copied()
    }

    pub(crate) fn as_slice(&self) -> &[String] {
        &self.labels
    }

    pub(crate) fn validate_query_filter(labels: &[String]) -> GraphResult<()> {
        if labels.len() > Self::MAX_QUERY_EDGE_TYPE_FILTERS {
            return Err(GraphError::InvalidFilter {
                reason: format!(
                    "edge type filter has {} entries; maximum is {}",
                    labels.len(),
                    Self::MAX_QUERY_EDGE_TYPE_FILTERS
                ),
            });
        }
        let bytes = labels.iter().try_fold(0usize, |total, label| {
            total
                .checked_add(label.len())
                .ok_or_else(|| GraphError::InvalidFilter {
                    reason: "edge type filter byte count overflows".into(),
                })
        })?;
        if bytes > Self::MAX_QUERY_EDGE_TYPE_FILTER_BYTES {
            return Err(GraphError::InvalidFilter {
                reason: format!(
                    "edge type filter uses {bytes} UTF-8 bytes; maximum is {}",
                    Self::MAX_QUERY_EDGE_TYPE_FILTER_BYTES
                ),
            });
        }
        Ok(())
    }

    /// Stable identity of the exact ordered registry contents.
    pub(crate) fn fingerprint(&self) -> u64 {
        self.fingerprint
    }

    /// Total UTF-8 payload bytes in the ordered registry.
    pub(crate) fn label_bytes(&self) -> usize {
        self.label_bytes
    }

    pub(crate) fn into_labels(self) -> Vec<String> {
        self.labels
    }

    pub(crate) fn ordered_heap_bytes(&self) -> usize {
        self.labels.capacity() * std::mem::size_of::<String>() + self.ordered_label_capacity_bytes
    }

    pub(crate) fn registration_heap_upper_bound(&self, label: &str) -> GraphResult<usize> {
        if self.id(label).is_some() {
            return Ok(0);
        }
        let next_bytes = self
            .label_bytes
            .checked_add(label.len())
            .ok_or(GraphError::EdgeTypeLimit)?;
        if label.is_empty()
            || label.len() > Self::MAX_EDGE_TYPE_LABEL_BYTES
            || self.labels.len() > Self::MAX_USER_EDGE_TYPES
            || next_bytes > Self::MAX_EDGE_TYPE_DICTIONARY_BYTES
        {
            return Err(GraphError::EdgeTypeLimit);
        }
        let next_labels =
            self.labels.len().checked_add(1).ok_or_else(|| {
                GraphError::Internal("edge type registry length overflowed".into())
            })?;
        let next_lookup = self
            .ids_by_label
            .len()
            .checked_add(1)
            .ok_or_else(|| GraphError::Internal("edge type lookup length overflowed".into()))?;
        let label_slots = collection_capacity_upper_bound(self.labels.capacity(), next_labels)?;
        let lookup_slots =
            collection_capacity_upper_bound(self.ids_by_label.capacity(), next_lookup)?;
        let target = label_slots
            .checked_mul(std::mem::size_of::<String>())
            .and_then(|bytes| bytes.checked_add(self.ordered_label_capacity_bytes))
            .and_then(|bytes| bytes.checked_add(label.len()))
            .and_then(|bytes| {
                bytes.checked_add(lookup_slots.checked_mul(
                    std::mem::size_of::<(String, EdgeTypeId)>() + Self::HASH_ENTRY_OVERHEAD_BYTES,
                )?)
            })
            .and_then(|bytes| bytes.checked_add(self.lookup_label_capacity_bytes))
            .and_then(|bytes| bytes.checked_add(label.len()))
            .ok_or_else(|| GraphError::Internal("edge type registry growth overflowed".into()))?;
        Ok(target.saturating_sub(self.heap_bytes()))
    }

    pub(crate) fn heap_bytes(&self) -> usize {
        self.ordered_heap_bytes()
            + self.ids_by_label.capacity()
                * (std::mem::size_of::<(String, EdgeTypeId)>() + Self::HASH_ENTRY_OVERHEAD_BYTES)
            + self.lookup_label_capacity_bytes
    }

    /// Conservative heap bound for decoding one validated v6 registry section.
    pub(crate) fn v6_load_metadata_upper_bound(encoded: &[u8]) -> GraphResult<usize> {
        let count = registry_encoded_count(encoded)?;
        if count > EdgeTypeId::V6_MAX_USER_ID as usize + 1 {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry count exceeds v6 limits".into(),
            });
        }
        Self::load_metadata_upper_bound(encoded)
    }

    pub(crate) fn load_metadata_upper_bound(encoded: &[u8]) -> GraphResult<usize> {
        let count = registry_encoded_count(encoded)?;
        if count > Self::MAX_USER_EDGE_TYPES + 1 {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry count exceeds logical limits".into(),
            });
        }
        let header_bytes = count
            .checked_add(1)
            .and_then(|offsets| offsets.checked_mul(8))
            .and_then(|offsets| offsets.checked_add(4))
            .ok_or_else(|| GraphError::CorruptFile {
                reason: "edge type registry header overflows".into(),
            })?;
        let payload_bytes =
            encoded
                .len()
                .checked_sub(header_bytes)
                .ok_or_else(|| GraphError::CorruptFile {
                    reason: "edge type registry offset table exceeds its section".into(),
                })?;
        if payload_bytes > Self::MAX_EDGE_TYPE_DICTIONARY_BYTES {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry payload exceeds configured policy".into(),
            });
        }
        let mut previous = 0_usize;
        for index in 0..count {
            let offset = 4 + (index + 1) * 8;
            let end = usize::try_from(u64::from_le_bytes(
                encoded
                    .get(offset..offset + 8)
                    .ok_or_else(|| GraphError::CorruptFile {
                        reason: "edge type registry offset table is truncated".into(),
                    })?
                    .try_into()
                    .map_err(|_| GraphError::CorruptFile {
                        reason: "edge type registry offset is malformed".into(),
                    })?,
            ))
            .map_err(|_| GraphError::CorruptFile {
                reason: "edge type registry offset exceeds usize".into(),
            })?;
            if end < previous
                || end > payload_bytes
                || (index > 0 && end - previous > Self::MAX_EDGE_TYPE_LABEL_BYTES)
            {
                return Err(GraphError::CorruptFile {
                    reason: "edge type registry label exceeds configured policy".into(),
                });
            }
            previous = end;
        }
        let lookup_count = count.saturating_sub(1);
        // `HashMap` keeps spare buckets and one control byte per bucket. Two
        // times the next power of two is deliberately above its maximum load
        // factor for this v6-bounded dictionary.
        let lookup_slots = lookup_count
            .max(1)
            .checked_next_power_of_two()
            .and_then(|slots| slots.checked_mul(2))
            .ok_or_else(|| GraphError::Internal("edge type lookup bound overflowed".into()))?;
        count
            .checked_mul(std::mem::size_of::<String>())
            .and_then(|bytes| bytes.checked_add(payload_bytes.checked_mul(2)?))
            .and_then(|bytes| {
                bytes.checked_add(lookup_slots.checked_mul(
                    std::mem::size_of::<(String, EdgeTypeId)>() + Self::HASH_ENTRY_OVERHEAD_BYTES,
                )?)
            })
            .ok_or_else(|| GraphError::Internal("edge type metadata bound overflowed".into()))
    }

    /// Conservative retained registry heap bound from validated count/payload metadata.
    pub(crate) fn decoded_heap_upper_bound(
        count: usize,
        payload_bytes: usize,
    ) -> GraphResult<usize> {
        if count == 0
            || count > Self::MAX_USER_EDGE_TYPES + 1
            || payload_bytes > Self::MAX_EDGE_TYPE_DICTIONARY_BYTES
        {
            return Err(GraphError::CorruptFile {
                reason: "edge type registry metadata exceeds configured policy".into(),
            });
        }
        let lookup_slots = count
            .saturating_sub(1)
            .max(1)
            .checked_next_power_of_two()
            .and_then(|slots| slots.checked_mul(2))
            .ok_or_else(|| GraphError::Internal("edge type lookup bound overflowed".into()))?;
        count
            .checked_mul(std::mem::size_of::<String>())
            .and_then(|bytes| bytes.checked_add(payload_bytes.checked_mul(2)?))
            .and_then(|bytes| {
                bytes.checked_add(lookup_slots.checked_mul(
                    std::mem::size_of::<(String, EdgeTypeId)>() + Self::HASH_ENTRY_OVERHEAD_BYTES,
                )?)
            })
            .ok_or_else(|| GraphError::Internal("edge type metadata bound overflowed".into()))
    }
}

fn validate_policy<'a>(
    count: usize,
    label_bytes: usize,
    labels: impl Iterator<Item = &'a str>,
) -> GraphResult<()> {
    if count > EdgeTypeRegistry::MAX_USER_EDGE_TYPES + 1
        || label_bytes > EdgeTypeRegistry::MAX_EDGE_TYPE_DICTIONARY_BYTES
        || labels
            .skip(1)
            .any(|label| label.len() > EdgeTypeRegistry::MAX_EDGE_TYPE_LABEL_BYTES)
    {
        return Err(GraphError::CorruptFile {
            reason: "edge type registry exceeds configured policy limits".into(),
        });
    }
    Ok(())
}

fn registry_encoded_count(encoded: &[u8]) -> GraphResult<usize> {
    let count_bytes: [u8; 4] = encoded
        .get(..4)
        .ok_or_else(|| GraphError::CorruptFile {
            reason: "edge type registry is too short".into(),
        })?
        .try_into()
        .map_err(|_| GraphError::CorruptFile {
            reason: "edge type registry count is malformed".into(),
        })?;
    let count = u32::from_le_bytes(count_bytes) as usize;
    if count == 0 {
        return Err(GraphError::CorruptFile {
            reason: "edge type registry must contain the untyped entry".into(),
        });
    }
    Ok(count)
}

fn collection_capacity_upper_bound(current: usize, required: usize) -> GraphResult<usize> {
    if current >= required {
        return Ok(current);
    }
    required
        .max(1)
        .checked_next_power_of_two()
        .and_then(|capacity| capacity.checked_mul(4))
        .ok_or_else(|| GraphError::Internal("edge type collection capacity overflowed".into()))
}

fn try_clone_label(label: &str) -> GraphResult<String> {
    let mut owned = String::new();
    owned.try_reserve_exact(label.len()).map_err(|error| {
        GraphError::Internal(format!("edge type label allocation failed: {error}"))
    })?;
    owned.push_str(label);
    Ok(owned)
}

impl std::ops::Deref for EdgeTypeRegistry {
    type Target = [String];

    fn deref(&self) -> &Self::Target {
        self.as_slice()
    }
}

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

    #[test]
    fn registry_preserves_order_and_reuses_o1_ids() {
        let mut registry = EdgeTypeRegistry::new_v6();
        let before = registry.heap_bytes();
        let growth_bound = registry.registration_heap_upper_bound("friend").unwrap();
        let friend = registry.register_v6("friend").unwrap();
        assert!(registry.heap_bytes() <= before + growth_bound);
        assert_eq!(registry.registration_heap_upper_bound("friend").unwrap(), 0);
        assert_eq!(registry.register_v6("friend").unwrap(), friend);
        assert_eq!(registry.register_v6("works_at").unwrap().get(), 2);
        assert_eq!(registry.id("friend"), Some(friend));
        assert_eq!(registry.as_slice(), ["", "friend", "works_at"]);
    }

    #[test]
    fn registration_bound_covers_every_v6_capacity_transition() {
        let mut registry = EdgeTypeRegistry::new_v6();
        for index in 1..=EdgeTypeId::V6_MAX_USER_ID {
            let label = format!("type_{index}");
            let before = registry.heap_bytes();
            let growth = registry.registration_heap_upper_bound(&label).unwrap();
            registry.register_v6(&label).unwrap();
            assert!(
                registry.heap_bytes() <= before + growth,
                "registration {index} exceeded its preflight"
            );
        }
    }

    #[test]
    fn registry_rejects_invalid_loaded_labels_and_v6_overflow() {
        assert!(EdgeTypeRegistry::try_from_v6_labels(vec!["bad".into()]).is_err());
        assert!(
            EdgeTypeRegistry::try_from_v6_labels(vec!["".into(), "x".into(), "x".into()]).is_err()
        );
        let mut registry = EdgeTypeRegistry::new_v6();
        for index in 1..=EdgeTypeId::V6_MAX_USER_ID {
            assert_eq!(
                registry
                    .register_v6(&format!("type_{index}"))
                    .unwrap()
                    .get(),
                index
            );
        }
        assert!(matches!(
            registry.register_v6("overflow"),
            Err(GraphError::EdgeTypeLimit)
        ));
    }

    #[test]
    fn v6_load_bound_covers_short_label_lookup_storage() {
        let count = EdgeTypeId::V6_MAX_USER_ID as usize + 1;
        let labels = std::iter::once(String::new())
            .chain((1..count).map(|index| format!("t{index}")))
            .collect::<Vec<_>>();
        let payload_bytes = labels.iter().map(String::len).sum::<usize>();
        let encoded_len = 4 + (count + 1) * 8 + payload_bytes;
        let mut encoded = vec![0; encoded_len];
        encoded[..4].copy_from_slice(&(count as u32).to_le_bytes());
        let mut offset = 0u64;
        for (index, label) in labels.iter().enumerate() {
            encoded[4 + index * 8..12 + index * 8].copy_from_slice(&offset.to_le_bytes());
            offset += label.len() as u64;
        }
        encoded[4 + count * 8..12 + count * 8].copy_from_slice(&offset.to_le_bytes());
        let registry = EdgeTypeRegistry::try_from_v6_labels(labels).unwrap();
        let bound = EdgeTypeRegistry::v6_load_metadata_upper_bound(&encoded).unwrap();
        assert!(bound >= registry.heap_bytes());
    }

    #[test]
    fn edge_type_policy_rejects_count_label_and_dictionary_limits() {
        let mut registry = EdgeTypeRegistry::new();
        let oversized = "x".repeat(EdgeTypeRegistry::MAX_EDGE_TYPE_LABEL_BYTES + 1);
        assert!(matches!(
            registry.register(&oversized),
            Err(GraphError::EdgeTypeLimit)
        ));
        assert!(matches!(
            EdgeTypeRegistry::try_from_labels(vec![String::new(), oversized]),
            Err(GraphError::CorruptFile { .. })
        ));
        assert_eq!(EdgeTypeRegistry::MAX_USER_EDGE_TYPES, 1_000_000);
        assert_eq!(
            EdgeTypeRegistry::MAX_EDGE_TYPE_DICTIONARY_BYTES,
            256 * 1024 * 1024
        );
        assert!(validate_policy(
            EdgeTypeRegistry::MAX_USER_EDGE_TYPES + 2,
            0,
            std::iter::empty()
        )
        .is_err());
        assert!(validate_policy(
            1,
            EdgeTypeRegistry::MAX_EDGE_TYPE_DICTIONARY_BYTES + 1,
            std::iter::once("")
        )
        .is_err());
    }

    #[test]
    fn query_filter_policy_enforces_count_and_cumulative_utf8_boundaries() {
        let at_count = vec![String::new(); EdgeTypeRegistry::MAX_QUERY_EDGE_TYPE_FILTERS];
        assert!(EdgeTypeRegistry::validate_query_filter(&at_count).is_ok());
        let over_count = vec![String::new(); EdgeTypeRegistry::MAX_QUERY_EDGE_TYPE_FILTERS + 1];
        assert!(matches!(
            EdgeTypeRegistry::validate_query_filter(&over_count),
            Err(GraphError::InvalidFilter { .. })
        ));
        let at_bytes = vec!["x".repeat(EdgeTypeRegistry::MAX_QUERY_EDGE_TYPE_FILTER_BYTES)];
        assert!(EdgeTypeRegistry::validate_query_filter(&at_bytes).is_ok());
        let over_bytes = vec!["x".repeat(EdgeTypeRegistry::MAX_QUERY_EDGE_TYPE_FILTER_BYTES + 1)];
        assert!(matches!(
            EdgeTypeRegistry::validate_query_filter(&over_bytes),
            Err(GraphError::InvalidFilter { .. })
        ));
    }

    proptest! {
        #[test]
        fn open_type_registry_property_preserves_order_spelling_and_lookup(
            generated in proptest::collection::hash_set("[A-Za-z][A-Za-z0-9_]{0,31}", 0..128)
        ) {
            let ordered = generated.into_iter().collect::<Vec<_>>();
            let labels = std::iter::once(String::new())
                .chain(ordered.iter().cloned())
                .collect::<Vec<_>>();
            let registry = EdgeTypeRegistry::try_from_labels(labels.clone())?;

            prop_assert_eq!(registry.as_slice(), labels.as_slice());
            prop_assert_eq!(registry.id(""), Some(EdgeTypeId::UNTYPED));
            for (index, label) in ordered.iter().enumerate() {
                let expected = EdgeTypeId::try_from((index + 1) as u32)
                    .expect("generated registry stays below the logical sentinel");
                prop_assert_eq!(registry.id(label), Some(expected));
                prop_assert_eq!(&registry.as_slice()[index + 1], label);
            }
            prop_assert_eq!(registry.id("__definitely_absent_open_type__"), None);
        }
    }
}
