//! Embedded path list for game-path discovery.
//!
//! Enabled by the `path-list` feature flag. [`PathList`] maintains a
//! bi-directional index of known game paths keyed by both their V1 (64-bit,
//! `.index`) and V2 (32-bit, `.index2`) hashes, allowing hash-keyed index
//! entries to be resolved back to a human-readable path when available.
//!
//! The [`SEED_PATHS`] constant provides a built-in starting set covering the
//! most commonly useful paths. Additional paths can be loaded via
//! [`PathList::extend_from_paths`] without recompilation.
//!
//! Paths are stored in their original surface form (case and separator
//! preserved), but lookups are hash-normalised so `"EXD\\Root.EXL"` and
//! `"exd/root.exl"` resolve to the same entry.

mod seed;

use std::collections::HashMap;
use std::sync::Arc;

use tracing::debug;

use crate::hash::{hash_index1_key, hash_index2};

pub use seed::SEED_PATHS;

/// Statistics returned by [`PathList::extend_from_paths`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[cfg_attr(docsrs, doc(cfg(feature = "path-list")))]
#[non_exhaustive]
pub struct ExtendOutcome {
    /// Paths successfully added (unique by both V1 and V2 hash).
    pub added: usize,
    /// Total paths in the list after this call.
    pub total: usize,
    /// Paths dropped because their hashes matched an already-stored path.
    pub dropped_duplicate: usize,
    /// Paths dropped due to a V1-hash collision with a different path.
    pub dropped_collision_v1: usize,
    /// Paths dropped due to a V2-hash collision with a different path.
    pub dropped_collision_v2: usize,
}

/// A set of known game paths indexed by their V1 and V2 hashes.
///
/// Use [`PathList::with_seed_list`] to start with the built-in set, or
/// [`PathList::new`] for an empty list and populate it with
/// [`PathList::extend_from_paths`].
///
/// Each path is stored once as an `Arc<str>` shared between the insertion-order
/// `Vec` and the two hash maps; cloning the whole list is cheap.
#[derive(Debug, Clone, Default)]
#[cfg_attr(docsrs, doc(cfg(feature = "path-list")))]
#[non_exhaustive]
pub struct PathList {
    paths: Vec<Arc<str>>,
    by_v1: HashMap<u64, Arc<str>>,
    by_v2: HashMap<u32, Arc<str>>,
}

impl PathList {
    /// Create an empty list.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Create a list pre-populated with [`SEED_PATHS`].
    #[must_use]
    pub fn with_seed_list() -> Self {
        let mut list = Self::new();
        list.extend_from_paths(SEED_PATHS.iter().copied());
        list
    }

    /// Create a list pre-populated with `paths`.
    #[must_use]
    pub fn with_paths<I, S>(paths: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let mut list = Self::new();
        let _ = list.extend_from_paths(paths);
        list
    }

    /// Alias of [`with_paths`](PathList::with_paths).
    #[must_use]
    pub fn from_paths<I, S>(paths: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        Self::with_paths(paths)
    }

    /// Add paths to the list, skipping duplicates and collisions.
    ///
    /// A path is considered a duplicate if both its V1 and V2 hashes already
    /// appear in the list (case/separator-normalised). A collision is when the
    /// V1 or V2 hash matches an existing entry that maps to a different path.
    ///
    /// Returns an [`ExtendOutcome`] counting each category.
    pub fn extend_from_paths<I, S>(&mut self, paths: I) -> ExtendOutcome
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let started_at = std::time::Instant::now();
        let mut outcome = ExtendOutcome::default();

        for raw in paths {
            let raw_str = raw.as_ref();
            let v1 = hash_index1_key(raw_str);
            let v2 = hash_index2(raw_str);

            if let Some(prev) = self.by_v1.get(&v1) {
                let prev_v1 = hash_index1_key(prev.as_ref());
                let prev_v2 = hash_index2(prev.as_ref());
                if prev_v1 == v1 && prev_v2 == v2 {
                    outcome.dropped_duplicate += 1;
                } else {
                    debug!(
                        new = %raw_str,
                        prev = %prev,
                        v1 = format_args!("{v1:#018x}"),
                        "path_list.collision_v1",
                    );
                    outcome.dropped_collision_v1 += 1;
                }
                continue;
            }
            if let Some(prev) = self.by_v2.get(&v2) {
                let prev_v1 = hash_index1_key(prev.as_ref());
                let prev_v2 = hash_index2(prev.as_ref());
                if prev_v1 == v1 && prev_v2 == v2 {
                    outcome.dropped_duplicate += 1;
                } else {
                    debug!(
                        new = %raw_str,
                        prev = %prev,
                        v2 = format_args!("{v2:#010x}"),
                        "path_list.collision_v2",
                    );
                    outcome.dropped_collision_v2 += 1;
                }
                continue;
            }

            let stored: Arc<str> = Arc::from(raw_str);
            self.paths.push(Arc::clone(&stored));
            self.by_v1.insert(v1, Arc::clone(&stored));
            self.by_v2.insert(v2, stored);
            outcome.added += 1;
        }

        outcome.total = self.paths.len();
        #[allow(clippy::cast_possible_truncation)]
        let elapsed_ms = started_at.elapsed().as_millis() as u64;
        debug!(
            added = outcome.added,
            total = outcome.total,
            dropped_duplicate = outcome.dropped_duplicate,
            dropped_collision_v1 = outcome.dropped_collision_v1,
            dropped_collision_v2 = outcome.dropped_collision_v2,
            elapsed_ms,
            "path_list.extend_from_paths",
        );
        outcome
    }

    /// Number of paths in the list.
    #[must_use]
    pub fn len(&self) -> usize {
        self.paths.len()
    }

    /// `true` if the list is empty.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.paths.is_empty()
    }

    /// Iterate over all paths in insertion order.
    pub fn paths(&self) -> impl ExactSizeIterator<Item = &str> {
        self.paths.iter().map(AsRef::as_ref)
    }

    /// Iterate over all paths in insertion order, yielding cloned `Arc<str>` handles.
    ///
    /// The returned `Arc`s share storage with the internal list — no new allocations.
    #[must_use = "iterator is lazy and does nothing unless consumed"]
    pub fn arc_paths(&self) -> impl ExactSizeIterator<Item = Arc<str>> + '_ {
        self.paths.iter().cloned()
    }

    #[must_use]
    pub(crate) fn arc_at(&self, idx: usize) -> Option<Arc<str>> {
        self.paths.get(idx).cloned()
    }

    /// Resolve a V1 (64-bit) hash to the stored path string, or `None` if unknown.
    #[must_use]
    pub fn lookup_v1(&self, hash: u64) -> Option<&str> {
        self.by_v1.get(&hash).map(AsRef::as_ref)
    }

    /// Resolve a V2 (32-bit) hash to the stored path string, or `None` if unknown.
    #[must_use]
    pub fn lookup_v2(&self, hash: u32) -> Option<&str> {
        self.by_v2.get(&hash).map(AsRef::as_ref)
    }

    /// Returns `true` if `path` (or any case/separator-normalised equivalent) is in the list.
    #[must_use]
    pub fn contains(&self, path: &str) -> bool {
        let v1 = hash_index1_key(path);
        self.by_v1.contains_key(&v1)
    }
}

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

    fn assert_send_sync<T: Send + Sync>() {}

    #[test]
    fn path_list_is_send_sync() {
        assert_send_sync::<PathList>();
    }

    #[test]
    fn new_is_empty() {
        let pl = PathList::new();
        assert!(pl.is_empty());
        assert_eq!(pl.len(), 0);
        assert!(pl.lookup_v1(0).is_none());
        assert!(pl.lookup_v2(0).is_none());
    }

    #[test]
    fn with_seed_list_populates_known_paths() {
        let pl = PathList::with_seed_list();
        assert!(!pl.is_empty());
        for &p in SEED_PATHS {
            let v1 = hash_index1_key(p);
            let v2 = hash_index2(p);
            assert_eq!(pl.lookup_v1(v1), Some(p), "v1 round-trip for {p}");
            assert_eq!(pl.lookup_v2(v2), Some(p), "v2 round-trip for {p}");
        }
    }

    #[test]
    fn with_paths_accepts_owned_and_borrowed() {
        let _a = PathList::with_paths(["exd/root.exl"]);
        let _b = PathList::with_paths(vec![String::from("exd/root.exl")]);
        let owned = String::from("exd/root.exl");
        let _c = PathList::with_paths([&owned]);
        let boxed: Box<str> = Box::from("exd/root.exl");
        let _d = PathList::with_paths([boxed]);
    }

    #[test]
    fn from_paths_is_alias_of_with_paths() {
        let a = PathList::from_paths(["exd/root.exl"]);
        let b = PathList::with_paths(["exd/root.exl"]);
        assert_eq!(a.len(), b.len());
        assert_eq!(
            a.lookup_v2(hash_index2("exd/root.exl")),
            b.lookup_v2(hash_index2("exd/root.exl")),
        );
    }

    #[test]
    fn duplicate_paths_drop_silently() {
        let mut pl = PathList::new();
        let outcome = pl.extend_from_paths(["exd/root.exl", "exd/root.exl", "exd/root.exl"]);
        assert_eq!(outcome.added, 1);
        assert_eq!(outcome.dropped_duplicate, 2);
        assert_eq!(outcome.dropped_collision_v1, 0);
        assert_eq!(outcome.dropped_collision_v2, 0);
        assert_eq!(pl.len(), 1);
    }

    #[test]
    fn case_and_slash_normalised_for_hash_keys() {
        let mut pl = PathList::new();
        let outcome = pl.extend_from_paths(["EXD\\Root.EXL", "exd/root.exl"]);
        assert_eq!(outcome.added, 1, "second insertion is a duplicate-by-hash");
        assert_eq!(pl.len(), 1);
        let stored: Vec<&str> = pl.paths().collect();
        assert_eq!(stored, vec!["EXD\\Root.EXL"]);
        assert_eq!(
            pl.lookup_v1(hash_index1_key("exd/root.exl")),
            Some("EXD\\Root.EXL"),
        );
    }

    #[test]
    fn normalised_duplicate_counts_as_duplicate_not_collision() {
        let mut pl = PathList::new();
        let outcome = pl.extend_from_paths(["EXD\\Root.EXL", "exd/root.exl"]);
        assert_eq!(outcome.added, 1);
        assert_eq!(
            outcome.dropped_duplicate, 1,
            "second surface form must be classified as duplicate, not collision",
        );
        assert_eq!(outcome.dropped_collision_v1, 0);
        assert_eq!(outcome.dropped_collision_v2, 0);
        assert_eq!(outcome.total, 1);

        let mut pl = PathList::new();
        let outcome = pl.extend_from_paths([
            "common/font/axis_12.fdt",
            "Common/Font/Axis_12.fdt",
            "COMMON\\FONT\\AXIS_12.FDT",
        ]);
        assert_eq!(outcome.added, 1);
        assert_eq!(outcome.dropped_duplicate, 2);
        assert_eq!(outcome.dropped_collision_v1, 0);
        assert_eq!(outcome.dropped_collision_v2, 0);
    }

    #[test]
    fn contains_uses_hash_lookup() {
        let pl = PathList::with_paths(["exd/root.exl", "common/font/axis_12.fdt"]);
        assert!(pl.contains("exd/root.exl"));
        assert!(pl.contains("EXD\\Root.EXL"));
        assert!(pl.contains("common/font/axis_12.fdt"));
        assert!(!pl.contains("chara/monster/m9999/obj/body/b0001/material/mt_x.mtrl"));
    }

    #[test]
    fn paths_iteration_is_insertion_order() {
        let inputs = ["b.bin", "a.bin", "c.bin"];
        let pl = PathList::with_paths(inputs);
        let observed: Vec<&str> = pl.paths().collect();
        assert_eq!(observed, inputs.to_vec());
    }

    #[test]
    fn extend_returns_added_count() {
        let mut pl = PathList::with_paths(["exd/root.exl"]);
        let outcome = pl.extend_from_paths(["exd/root.exl", "exd/item.exh"]);
        assert_eq!(outcome.added, 1, "only item.exh is new");
        assert_eq!(outcome.dropped_duplicate, 1);
        assert_eq!(outcome.total, 2);
        assert_eq!(pl.len(), 2);
    }

    #[test]
    fn seed_list_is_non_trivial() {
        assert!(
            SEED_PATHS.len() >= 20,
            "seed list shrank unexpectedly to {}",
            SEED_PATHS.len(),
        );
        assert!(SEED_PATHS.contains(&"exd/root.exl"));
    }

    #[test]
    fn arc_sharing_keeps_storage_minimal() {
        let n = 1024;
        let paths: Vec<String> = (0..n)
            .map(|i| format!("common/synthetic/path_{i}.bin"))
            .collect();
        let pl = PathList::with_paths(&paths);
        assert_eq!(pl.len(), n);
        let first: &Arc<str> = &pl.paths[0];
        assert!(
            Arc::strong_count(first) >= 3,
            "refcount on stored path must be ≥ 3 (vec + by_v1 + by_v2 + possibly more), got {}",
            Arc::strong_count(first),
        );
    }

    #[test]
    fn extend_from_paths_empty_iterator_returns_zero_outcome() {
        let mut pl = PathList::with_paths(["exd/root.exl"]);
        let outcome = pl.extend_from_paths(std::iter::empty::<&str>());
        assert_eq!(outcome.added, 0);
        assert_eq!(outcome.dropped_duplicate, 0);
        assert_eq!(outcome.dropped_collision_v1, 0);
        assert_eq!(outcome.dropped_collision_v2, 0);
        assert_eq!(
            outcome.total, 1,
            "total must reflect current list len, not zero"
        );
        assert_eq!(pl.len(), 1, "list must not shrink on empty extend");
    }

    #[test]
    fn extend_from_paths_repeated_calls_accumulate_correctly() {
        let mut pl = PathList::new();

        let first = pl.extend_from_paths(["exd/root.exl"]);
        assert_eq!(first.added, 1);
        assert_eq!(first.total, 1);

        let second = pl.extend_from_paths(["exd/root.exl", "exd/item.exh"]);
        assert_eq!(second.added, 1, "only item.exh is new in the second call");
        assert_eq!(
            second.dropped_duplicate, 1,
            "root.exl inserted in first call must be counted as duplicate in second call",
        );
        assert_eq!(second.dropped_collision_v1, 0);
        assert_eq!(second.dropped_collision_v2, 0);
        assert_eq!(second.total, 2);
        assert_eq!(pl.len(), 2);
    }

    #[test]
    fn extend_from_paths_outcome_arithmetic_invariant() {
        let mut pl = PathList::new();
        let inputs = [
            "exd/root.exl",
            "exd/item.exh",
            "exd/root.exl",
            "EXD\\Root.EXL",
            "exd/action.exh",
        ];
        let input_count = inputs.len();
        let outcome = pl.extend_from_paths(inputs);
        assert_eq!(
            outcome.added
                + outcome.dropped_duplicate
                + outcome.dropped_collision_v1
                + outcome.dropped_collision_v2,
            input_count,
            "counter arithmetic invariant violated: added({}) + dup({}) + col_v1({}) + col_v2({}) != input_count({})",
            outcome.added,
            outcome.dropped_duplicate,
            outcome.dropped_collision_v1,
            outcome.dropped_collision_v2,
            input_count,
        );
        assert_eq!(outcome.total, pl.len());
    }

    #[test]
    fn lookup_v1_hit_returns_original_string() {
        let pl = PathList::with_paths(["EXD\\Root.EXL"]);
        let v1 = hash_index1_key("EXD\\Root.EXL");
        assert_eq!(
            pl.lookup_v1(v1),
            Some("EXD\\Root.EXL"),
            "lookup_v1 must return the original surface form, not the normalised form",
        );
    }

    #[test]
    fn lookup_v1_miss_returns_none() {
        let pl = PathList::with_paths(["exd/root.exl"]);
        assert_eq!(pl.lookup_v1(0xdead_beef_dead_beef_u64), None);
    }

    #[test]
    fn lookup_v2_hit_returns_original_string() {
        let pl = PathList::with_paths(["EXD\\Root.EXL"]);
        let v2 = hash_index2("EXD\\Root.EXL");
        assert_eq!(
            pl.lookup_v2(v2),
            Some("EXD\\Root.EXL"),
            "lookup_v2 must return the original surface form",
        );
    }

    #[test]
    fn lookup_v2_miss_returns_none() {
        let pl = PathList::with_paths(["exd/root.exl"]);
        assert_eq!(pl.lookup_v2(0xdead_beefu32), None);
    }

    #[test]
    fn lookup_v1_normalisation_invariance() {
        let pl = PathList::with_paths(["EXD\\Root.EXL"]);
        let canonical_v1 = hash_index1_key("exd/root.exl");
        assert_eq!(
            pl.lookup_v1(canonical_v1),
            Some("EXD\\Root.EXL"),
            "normalised key must resolve to the originally-stored surface form",
        );
    }

    #[test]
    fn contains_is_normalisation_invariant() {
        let pl = PathList::with_paths(["exd/root.exl"]);
        assert!(pl.contains("EXD\\Root.EXL"), "non-canonical query must hit");
        assert!(!pl.contains("exd/item.exh"), "absent path must miss");
    }

    #[test]
    fn is_empty_tracks_len() {
        let mut pl = PathList::new();
        assert!(pl.is_empty());
        assert_eq!(pl.len(), 0);
        pl.extend_from_paths(["exd/root.exl"]);
        assert!(!pl.is_empty());
        assert_eq!(pl.len(), 1);
    }

    #[test]
    fn paths_and_arc_paths_yield_same_content() {
        let inputs = ["exd/root.exl", "exd/item.exh", "common/font/axis_12.fdt"];
        let pl = PathList::with_paths(inputs);

        let via_paths: Vec<&str> = pl.paths().collect();
        let via_arc: Vec<Arc<str>> = pl.arc_paths().collect();

        assert_eq!(via_paths.len(), via_arc.len());
        for (a, b) in via_paths.iter().zip(via_arc.iter()) {
            assert_eq!(*a, b.as_ref());
        }
    }

    #[test]
    fn arc_paths_yields_shared_arcs_not_fresh_copies() {
        let pl = PathList::with_paths(["exd/root.exl"]);
        let internal: Arc<str> = pl.paths[0].clone();
        let from_iter: Arc<str> = pl.arc_paths().next().expect("one entry");
        assert_eq!(
            Arc::as_ptr(&internal),
            Arc::as_ptr(&from_iter),
            "arc_paths() must yield the same Arc allocation as the internal vec, not a copy",
        );
    }

    #[test]
    fn arc_at_in_bounds_matches_paths_output() {
        let pl = PathList::with_paths(["exd/root.exl", "exd/item.exh"]);
        assert_eq!(pl.arc_at(0).as_deref(), Some("exd/root.exl"));
        assert_eq!(pl.arc_at(1).as_deref(), Some("exd/item.exh"));
    }

    #[test]
    fn arc_at_out_of_bounds_returns_none() {
        let pl = PathList::with_paths(["exd/root.exl"]);
        assert!(
            pl.arc_at(1).is_none(),
            "out-of-bounds arc_at must return None, not panic"
        );
    }

    #[test]
    fn seed_paths_are_already_canonical() {
        for &p in SEED_PATHS {
            assert!(
                !p.contains('\\'),
                "seed path {p:?} contains backslash; must use forward slashes",
            );
            assert_eq!(
                p,
                p.to_ascii_lowercase(),
                "seed path {p:?} is not lowercase",
            );
        }
    }

    #[test]
    fn seed_paths_have_no_duplicates() {
        let mut pl = PathList::new();
        let outcome = pl.extend_from_paths(SEED_PATHS.iter().copied());
        assert_eq!(
            outcome.dropped_duplicate, 0,
            "SEED_PATHS must have no duplicates; {} found",
            outcome.dropped_duplicate,
        );
        assert_eq!(
            outcome.dropped_collision_v1, 0,
            "SEED_PATHS must have no v1 collisions; {} found",
            outcome.dropped_collision_v1,
        );
        assert_eq!(
            outcome.dropped_collision_v2, 0,
            "SEED_PATHS must have no v2 collisions; {} found",
            outcome.dropped_collision_v2,
        );
        assert_eq!(
            outcome.added,
            SEED_PATHS.len(),
            "every seed path must be unique and added",
        );
    }

    #[test]
    fn extend_outcome_fields_are_readable_and_default_to_zero() {
        let outcome = ExtendOutcome::default();
        assert_eq!(outcome.added, 0);
        assert_eq!(outcome.total, 0);
        assert_eq!(outcome.dropped_duplicate, 0);
        assert_eq!(outcome.dropped_collision_v1, 0);
        assert_eq!(outcome.dropped_collision_v2, 0);
    }
}
