//! Bloom filter pre-filtering for fast search elimination.
//!
//! Provides per-file bloom filters that index function names, type names,
//! and import paths. Before a full vector or graph search, the bloom index
//! can quickly eliminate files that definitely don't contain the query tokens.

use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use std::sync::RwLock;

use tracing::debug;

/// Number of hash functions used by the bloom filter.
const NUM_HASHES: usize = 5;

/// Default bits per entry (controls false-positive rate).
/// At 10 bits/entry with 5 hashes, FP rate ≈ 0.8%.
const BITS_PER_ENTRY: usize = 10;

/// Minimum filter size in bits.
const MIN_FILTER_BITS: usize = 64;

/// A compact bloom filter backed by a bit vector.
#[derive(Debug, Clone)]
pub struct BloomFilter {
    bits: Vec<u64>,
    num_bits: usize,
    count: usize,
}

impl BloomFilter {
    /// Create a new bloom filter sized for the expected number of entries.
    pub fn with_capacity(expected_entries: usize) -> Self {
        let num_bits = (expected_entries * BITS_PER_ENTRY).max(MIN_FILTER_BITS);
        let num_words = (num_bits + 63) / 64;
        Self {
            bits: vec![0u64; num_words],
            num_bits: num_words * 64,
            count: 0,
        }
    }

    /// Insert a token (lowercased) into the filter.
    pub fn insert(&mut self, token: &str) {
        let lower = token.to_lowercase();
        for i in 0..NUM_HASHES {
            let bit = self.hash_index(&lower, i);
            let word = bit / 64;
            let offset = bit % 64;
            self.bits[word] |= 1u64 << offset;
        }
        self.count += 1;
    }

    /// Test whether a token might be in the filter.
    /// Returns `false` if the token is definitely NOT present.
    /// Returns `true` if it might be present (possible false positive).
    pub fn might_contain(&self, token: &str) -> bool {
        let lower = token.to_lowercase();
        for i in 0..NUM_HASHES {
            let bit = self.hash_index(&lower, i);
            let word = bit / 64;
            let offset = bit % 64;
            if self.bits[word] & (1u64 << offset) == 0 {
                return false;
            }
        }
        true
    }

    /// Number of items inserted.
    pub fn count(&self) -> usize {
        self.count
    }

    /// Estimated memory usage in bytes.
    pub fn size_bytes(&self) -> usize {
        self.bits.len() * 8
    }

    /// Compute the i-th hash of a token, mapped to a bit position.
    fn hash_index(&self, token: &str, i: usize) -> usize {
        let mut hasher = std::collections::hash_map::DefaultHasher::new();
        token.hash(&mut hasher);
        i.hash(&mut hasher);
        (hasher.finish() as usize) % self.num_bits
    }
}

/// Index of per-file bloom filters for fast entity pre-filtering.
///
/// Each file gets a bloom filter populated with its function names, type names,
/// and import paths. Query tokens are tested against all filters to quickly
/// eliminate files that can't match.
pub struct BloomFilterIndex {
    filters: RwLock<HashMap<String, BloomFilter>>,
}

impl BloomFilterIndex {
    pub fn new() -> Self {
        Self {
            filters: RwLock::new(HashMap::new()),
        }
    }

    /// Add or replace the bloom filter for a file.
    /// `tokens` should include function names, type names, import paths, etc.
    pub fn index_file(&self, file_path: &str, tokens: &[String]) {
        let mut filter = BloomFilter::with_capacity(tokens.len().max(1));
        for token in tokens {
            filter.insert(token);
        }
        if let Ok(mut filters) = self.filters.write() {
            filters.insert(file_path.to_string(), filter);
        }
    }

    /// Remove a file's bloom filter (e.g., on deletion).
    pub fn remove_file(&self, file_path: &str) {
        if let Ok(mut filters) = self.filters.write() {
            filters.remove(file_path);
        }
    }

    /// Pre-filter: return file paths whose bloom filter matches ANY of the query tokens.
    /// Files not in the index are included by default (no false negatives).
    pub fn candidate_files(&self, query_tokens: &[String], known_files: &[String]) -> Vec<String> {
        let filters = match self.filters.read() {
            Ok(f) => f,
            Err(_) => return known_files.to_vec(), // poisoned lock: pass through
        };

        known_files
            .iter()
            .filter(|path| {
                match filters.get(*path) {
                    Some(filter) => {
                        // File has a bloom filter — must match at least one token.
                        query_tokens.iter().any(|t| filter.might_contain(t))
                    }
                    None => {
                        // File not indexed in bloom — include it (no false negatives).
                        true
                    }
                }
            })
            .cloned()
            .collect()
    }

    /// Tokenize a query string into bloom-testable tokens.
    /// Splits on whitespace and punctuation, lowercases, filters short tokens.
    pub fn tokenize_query(query: &str) -> Vec<String> {
        query
            .to_lowercase()
            .split(|c: char| !c.is_alphanumeric() && c != '_')
            .filter(|t| t.len() >= 2)
            .map(|t| t.to_string())
            .collect()
    }

    /// Number of files indexed.
    pub fn file_count(&self) -> usize {
        self.filters.read().map(|f| f.len()).unwrap_or(0)
    }

    /// Total memory estimate across all filters.
    pub fn total_size_bytes(&self) -> usize {
        self.filters
            .read()
            .map(|f| f.values().map(|bf| bf.size_bytes()).sum())
            .unwrap_or(0)
    }

    /// Get hit statistics: how many files matched vs total.
    pub fn filter_stats(&self, query_tokens: &[String], known_files: &[String]) -> BloomFilterStats {
        let candidates = self.candidate_files(query_tokens, known_files);
        let total = known_files.len();
        let passed = candidates.len();
        let eliminated = total.saturating_sub(passed);
        let elimination_rate = if total > 0 {
            eliminated as f64 / total as f64
        } else {
            0.0
        };
        debug!(
            total,
            passed,
            eliminated,
            elimination_rate = format!("{:.1}%", elimination_rate * 100.0),
            "Bloom filter pre-filtering"
        );
        BloomFilterStats {
            total_files: total,
            candidate_files: passed,
            eliminated_files: eliminated,
            elimination_rate,
        }
    }
}

/// Statistics from a bloom filter pre-filtering pass.
#[derive(Debug, Clone)]
pub struct BloomFilterStats {
    pub total_files: usize,
    pub candidate_files: usize,
    pub eliminated_files: usize,
    pub elimination_rate: f64,
}

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

    #[test]
    fn test_bloom_filter_basic() {
        let mut bf = BloomFilter::with_capacity(10);
        bf.insert("hello");
        bf.insert("world");
        assert!(bf.might_contain("hello"));
        assert!(bf.might_contain("world"));
        assert_eq!(bf.count(), 2);
    }

    #[test]
    fn test_bloom_filter_probably_absent() {
        let mut bf = BloomFilter::with_capacity(10);
        bf.insert("present_token");
        // With 10 bits/entry and 5 hashes, false positive for a single
        // random token is very unlikely.
        assert!(!bf.might_contain("definitely_not_here_xyz_12345"));
    }

    #[test]
    fn test_bloom_filter_case_insensitive() {
        let mut bf = BloomFilter::with_capacity(10);
        bf.insert("HelloWorld");
        assert!(bf.might_contain("helloworld"));
        assert!(bf.might_contain("HELLOWORLD"));
    }

    #[test]
    fn test_bloom_index_candidate_files() {
        let index = BloomFilterIndex::new();
        index.index_file("src/auth.rs", &["authenticate".into(), "login".into(), "session".into()]);
        index.index_file("src/db.rs", &["query".into(), "insert".into(), "connection".into()]);
        index.index_file("src/api.rs", &["handler".into(), "route".into(), "login".into()]);

        let all_files = vec![
            "src/auth.rs".into(),
            "src/db.rs".into(),
            "src/api.rs".into(),
        ];

        let candidates = index.candidate_files(&["login".into()], &all_files);
        assert!(candidates.contains(&"src/auth.rs".to_string()));
        assert!(candidates.contains(&"src/api.rs".to_string()));
        assert!(!candidates.contains(&"src/db.rs".to_string()));
    }

    #[test]
    fn test_bloom_index_unindexed_files_included() {
        let index = BloomFilterIndex::new();
        index.index_file("src/auth.rs", &["authenticate".into()]);

        let all_files = vec![
            "src/auth.rs".into(),
            "src/unknown.rs".into(), // not in bloom index
        ];

        let candidates = index.candidate_files(&["something".into()], &all_files);
        // unknown.rs should pass through (not indexed = no false negatives)
        assert!(candidates.contains(&"src/unknown.rs".to_string()));
    }

    #[test]
    fn test_bloom_index_remove_file() {
        let index = BloomFilterIndex::new();
        index.index_file("src/old.rs", &["deprecated".into()]);
        assert_eq!(index.file_count(), 1);
        index.remove_file("src/old.rs");
        assert_eq!(index.file_count(), 0);
    }

    #[test]
    fn test_tokenize_query() {
        let tokens = BloomFilterIndex::tokenize_query("find the login_handler function");
        assert!(tokens.contains(&"find".to_string()));
        assert!(tokens.contains(&"the".to_string()));
        assert!(tokens.contains(&"login_handler".to_string()));
        assert!(tokens.contains(&"function".to_string()));
    }

    #[test]
    fn test_bloom_filter_stats() {
        let index = BloomFilterIndex::new();
        index.index_file("a.rs", &["foo".into()]);
        index.index_file("b.rs", &["bar".into()]);
        index.index_file("c.rs", &["baz".into()]);

        let all = vec!["a.rs".into(), "b.rs".into(), "c.rs".into()];
        let stats = index.filter_stats(&["foo".into()], &all);
        assert_eq!(stats.total_files, 3);
        assert_eq!(stats.candidate_files, 1);
        assert_eq!(stats.eliminated_files, 2);
    }

    #[test]
    fn test_bloom_filter_size_bytes() {
        let bf = BloomFilter::with_capacity(100);
        assert!(bf.size_bytes() > 0);
        // 100 entries * 10 bits/entry = 1000 bits ≈ 128 bytes (rounded to 64-bit words)
        assert!(bf.size_bytes() >= 125);
    }
}
