//! FST-based symbol index: maps symbol name/sub-tokens → posting list of symbol indices.
//!
//! This replaces the in-memory InvertedIndex with a persistent, zero-copy FST.
//! CamelCase sub-tokens are indexed: "PaymentService" → ["paymentservice", "payment", "service"].

use anyhow::{Context, Result};

/// Build symbol FST + posting lists from symbol records.
/// Each symbol name and its CamelCase sub-tokens are inserted.
/// Returns (fst_bytes, posting_bytes).
///
/// v1.13 P7: `Vec<(String, u32)>` + final sort beats the previous
/// `BTreeMap<String, Vec<u32>>` — no per-insert tree node, contiguous
/// sort, and the duplicate-key path no longer clones the key on each
/// hit. CamelCase sub-tokens still emit one `to_lowercase` allocation
/// each but no longer pay the `entry().clone()` tax on dup names.
pub fn build_symbol_fst(
    symbols: &[(String, u32)], // (name, symbol_index)
) -> Result<(Vec<u8>, Vec<u8>)> {
    // Worst case: one primary key + a handful of CamelCase tokens per
    // symbol. Reserve 3× as a heuristic — most identifiers split into
    // 1–3 tokens.
    let mut entries: Vec<(String, u32)> = Vec::with_capacity(symbols.len() * 3);

    for (name, idx) in symbols {
        let lower = name.to_lowercase();
        // Push the primary lowercased name, then any CamelCase
        // sub-tokens that differ from it.
        for token in split_camel_case(name) {
            let token_lower = token.to_lowercase();
            if token_lower != lower {
                entries.push((token_lower, *idx));
            }
        }
        entries.push((lower, *idx));
    }

    entries.sort_unstable_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)));

    let mut posting_data: Vec<u8> = Vec::with_capacity(entries.len() * 4 + entries.len());
    let mut fst_builder = fst::MapBuilder::memory();

    let mut i = 0;
    while i < entries.len() {
        let mut j = i + 1;
        while j < entries.len() && entries[j].0 == entries[i].0 {
            j += 1;
        }
        // Dedup ascending edge indices in-place over the contiguous group.
        let group = &mut entries[i..j];
        let mut write = 0;
        for read in 0..group.len() {
            if write == 0 || group[read].1 != group[write - 1].1 {
                group.swap(read, write);
                write += 1;
            }
        }
        let offset = posting_data.len() as u64;
        let count = write as u32;
        posting_data.extend_from_slice(&count.to_le_bytes());
        for slot in group.iter().take(write) {
            posting_data.extend_from_slice(&slot.1.to_le_bytes());
        }
        fst_builder
            .insert(entries[i].0.as_bytes(), offset)
            .context("fst insert")?;
        i = j;
    }

    let fst_bytes = fst_builder.into_inner().context("finalize fst")?;
    Ok((fst_bytes, posting_data))
}

/// Read symbol indices from persistent FST. Zero-copy from mmap.
pub struct SymbolFstReader<'a> {
    fst_map: fst::Map<&'a [u8]>,
    posting_data: &'a [u8],
}

impl<'a> SymbolFstReader<'a> {
    pub fn new(fst_bytes: &'a [u8], posting_bytes: &'a [u8]) -> Result<Self> {
        let fst_map = fst::Map::new(fst_bytes).map_err(|e| anyhow::anyhow!("fst load: {e}"))?;
        Ok(Self {
            fst_map,
            posting_data: posting_bytes,
        })
    }

    /// Exact lookup: find all symbol indices for a name (lowercased).
    pub fn find(&self, name: &str) -> Vec<u32> {
        let key = name.to_lowercase();
        match self.fst_map.get(key.as_bytes()) {
            Some(offset) => self.read_posting_list(offset),
            None => Vec::new(),
        }
    }

    /// Prefix search: find all matching names and their symbol indices.
    pub fn find_by_prefix(&self, prefix: &str) -> Vec<(String, Vec<u32>)> {
        use fst::automaton::{Automaton, Str};
        use fst::{IntoStreamer, Streamer};

        let key = prefix.to_lowercase();
        let automaton = Str::new(&key).starts_with();
        let mut stream = self.fst_map.search(automaton).into_stream();
        let mut results = Vec::new();

        while let Some((k, offset)) = stream.next() {
            let name = std::str::from_utf8(k).unwrap_or("").to_owned();
            let indices = self.read_posting_list(offset);
            results.push((name, indices));
        }

        results
    }

    /// Fuzzy search: find keys within Levenshtein edit distance of the query.
    /// Uses the FST's built-in Levenshtein automaton for efficient traversal.
    pub fn find_fuzzy(
        &self,
        query: &str,
        max_distance: u32,
        limit: usize,
    ) -> Vec<(String, Vec<u32>)> {
        use fst::automaton::Levenshtein;
        use fst::{IntoStreamer, Streamer};

        let key = query.to_lowercase();
        let lev = match Levenshtein::new(&key, max_distance) {
            Ok(l) => l,
            Err(_) => return Vec::new(), // query too long for this distance
        };

        let mut stream = self.fst_map.search(lev).into_stream();
        let mut results = Vec::new();
        let mut total = 0usize;

        while let Some((k, offset)) = stream.next() {
            let name = std::str::from_utf8(k).unwrap_or("").to_owned();
            let indices = self.read_posting_list(offset);
            total += indices.len();
            results.push((name, indices));
            if total >= limit {
                break;
            }
        }

        results
    }

    /// Search with fuzzy fallback: exact → prefix → Levenshtein.
    /// Returns (indices, was_fuzzy).
    pub fn search_with_fallback(&self, query: &str, limit: usize) -> (Vec<u32>, bool) {
        // Exact match
        let exact = self.find(query);
        if !exact.is_empty() {
            return (exact.into_iter().take(limit).collect(), false);
        }

        // Prefix match
        let prefix_results = self.find_by_prefix(query);
        let mut all: Vec<u32> = Vec::new();
        let mut seen = std::collections::HashSet::new();
        for (_name, indices) in prefix_results {
            for idx in indices {
                if seen.insert(idx) {
                    all.push(idx);
                    if all.len() >= limit {
                        return (all, false);
                    }
                }
            }
        }
        if !all.is_empty() {
            return (all, false);
        }

        // Fuzzy fallback (adaptive distance)
        let distance = fuzzy_distance(query);
        let fuzzy_results = self.find_fuzzy(query, distance, limit);
        let mut fuzzy_all: Vec<u32> = Vec::new();
        seen.clear();
        for (_name, indices) in fuzzy_results {
            for idx in indices {
                if seen.insert(idx) {
                    fuzzy_all.push(idx);
                    if fuzzy_all.len() >= limit {
                        break;
                    }
                }
            }
        }
        let was_fuzzy = !fuzzy_all.is_empty();
        (fuzzy_all, was_fuzzy)
    }

    fn read_posting_list(&self, offset: u64) -> Vec<u32> {
        let offset = offset as usize;
        if offset + 4 > self.posting_data.len() {
            tracing::warn!(offset, "symbol posting list offset out of bounds");
            return Vec::new();
        }

        let count = u32::from_le_bytes(
            self.posting_data[offset..offset + 4]
                .try_into()
                .unwrap_or([0; 4]),
        ) as usize;

        let entry_size = 4; // u32 symbol_idx
        let data_start = offset + 4;

        let data_end = match count
            .checked_mul(entry_size)
            .and_then(|n| data_start.checked_add(n))
        {
            Some(end) => end,
            None => {
                tracing::warn!(count, "symbol posting list count overflow");
                return Vec::new();
            }
        };

        if data_end > self.posting_data.len() {
            tracing::warn!(count, "symbol posting list truncated");
            return Vec::new();
        }

        let mut indices = Vec::with_capacity(count);
        for i in 0..count {
            let base = data_start + i * entry_size;
            let idx = u32::from_le_bytes(
                self.posting_data[base..base + 4]
                    .try_into()
                    .unwrap_or([0; 4]),
            );
            indices.push(idx);
        }

        indices
    }
}

/// Adaptive Levenshtein distance: short queries get distance 1, longer get 2.
fn fuzzy_distance(query: &str) -> u32 {
    if query.chars().count() <= 4 {
        1
    } else {
        2
    }
}

/// Split CamelCase identifiers into sub-tokens.
/// Handles lowercase→Uppercase and Uppercase→Uppercase+Lowercase transitions.
/// "PaymentService" → ["Payment", "Service"]
/// "HTTPSClient" → ["HTTPS", "Client"]
/// "getHTTPResponse" → ["get", "HTTP", "Response"]
fn split_camel_case(s: &str) -> Vec<&str> {
    let mut tokens = Vec::new();
    let bytes = s.as_bytes();
    let mut start = 0;

    for i in 1..bytes.len() {
        let prev_lower = bytes[i - 1].is_ascii_lowercase();
        let curr_upper = bytes[i].is_ascii_uppercase();

        // lowercase → Uppercase: "payment|Service"
        if prev_lower && curr_upper {
            tokens.push(&s[start..i]);
            start = i;
        }

        // Uppercase → Uppercase + Lowercase: "HTTPS|Client" (split before the last uppercase)
        if i + 1 < bytes.len()
            && bytes[i - 1].is_ascii_uppercase()
            && bytes[i].is_ascii_uppercase()
            && bytes[i + 1].is_ascii_lowercase()
        {
            tokens.push(&s[start..i]);
            start = i;
        }
    }
    if start < s.len() {
        tokens.push(&s[start..]);
    }
    tokens
}

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

    #[test]
    fn exact_search() {
        let symbols = vec![
            ("PaymentService".to_string(), 0),
            ("PaymentGateway".to_string(), 1),
            ("UserService".to_string(), 2),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        assert_eq!(reader.find("paymentservice"), vec![0]);
        assert_eq!(reader.find("userservice"), vec![2]);
        assert!(reader.find("nonexistent").is_empty());
    }

    #[test]
    fn camel_case_sub_token_search() {
        let symbols = vec![
            ("PaymentService".to_string(), 0),
            ("PaymentGateway".to_string(), 1),
            ("UserService".to_string(), 2),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // "payment" sub-token matches both Payment* symbols
        let results = reader.find("payment");
        assert!(results.contains(&0));
        assert!(results.contains(&1));
        assert!(!results.contains(&2));

        // "service" sub-token matches all *Service symbols
        let results = reader.find("service");
        assert!(results.contains(&0));
        assert!(results.contains(&2));
    }

    #[test]
    fn prefix_search() {
        let symbols = vec![
            ("PaymentService".to_string(), 0),
            ("PaymentGateway".to_string(), 1),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        let results = reader.find_by_prefix("payment");
        assert!(results.len() >= 2); // "payment", "paymentgateway", "paymentservice"
    }

    #[test]
    fn acronym_split() {
        let symbols = vec![
            ("HTTPSClient".to_string(), 0),
            ("getHTTPResponse".to_string(), 1),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // "https" sub-token from HTTPSClient
        let results = reader.find("https");
        assert!(results.contains(&0), "should find HTTPSClient via 'https'");

        // "http" sub-token from getHTTPResponse
        let results = reader.find("http");
        assert!(
            results.contains(&1),
            "should find getHTTPResponse via 'http'"
        );

        // "client" sub-token
        let results = reader.find("client");
        assert!(results.contains(&0), "should find HTTPSClient via 'client'");
    }

    #[test]
    fn fuzzy_single_typo() {
        let symbols = vec![
            ("PaymentService".to_string(), 0),
            ("UserService".to_string(), 1),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // "paymentservce" (missing 'i') → finds "paymentservice" at distance 1
        let results = reader.find_fuzzy("paymentservce", 1, 10);
        let names: Vec<&str> = results.iter().map(|(n, _)| n.as_str()).collect();
        assert!(
            names.contains(&"paymentservice"),
            "should fuzzy-find PaymentService"
        );
    }

    #[test]
    fn fuzzy_no_match_on_exact() {
        let symbols = vec![("FooBar".to_string(), 0)];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // Exact match → search_with_fallback returns (indices, false)
        let (indices, was_fuzzy) = reader.search_with_fallback("foobar", 10);
        assert!(!indices.is_empty());
        assert!(!was_fuzzy);
    }

    #[test]
    fn fuzzy_fallback_triggers() {
        let symbols = vec![
            ("PaymentService".to_string(), 0),
            ("UserService".to_string(), 1),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // "pymntservice" doesn't match exact or prefix, triggers fuzzy
        let (indices, was_fuzzy) = reader.search_with_fallback("paymentservce", 10);
        assert!(!indices.is_empty(), "fuzzy should find results");
        assert!(was_fuzzy);
    }

    #[test]
    fn search_exact_then_prefix() {
        let symbols = vec![
            ("FooBar".to_string(), 0),
            ("FooBaz".to_string(), 1),
            ("Qux".to_string(), 2),
        ];
        let (fst, postings) = build_symbol_fst(&symbols).unwrap();
        let reader = SymbolFstReader::new(&fst, &postings).unwrap();

        // Exact match
        let (indices, was_fuzzy) = reader.search_with_fallback("foobar", 10);
        assert_eq!(indices, vec![0]);
        assert!(!was_fuzzy);

        // Prefix — "foo" matches sub-token
        let (results, was_fuzzy) = reader.search_with_fallback("foo", 10);
        assert!(results.contains(&0));
        assert!(results.contains(&1));
        assert!(!was_fuzzy);
    }
}
