dupe_core/

lib.rs

//! PolyDup Core - Cross-language duplicate code detection engine
//!
//! This library provides the core functionality for detecting duplicate code
//! across Node.js, Python, and Rust codebases using Tree-sitter parsing,
//! Rabin-Karp/MinHash algorithms, and parallel processing.

mod hashing;
mod parsing;
mod queries;

#[cfg(test)]
mod proptest_fuzzing;

#[cfg(test)]
mod snapshot_tests;

// Re-export public types
pub use hashing::{
    compute_rolling_hashes, compute_token_edit_distance, compute_token_similarity,
    detect_duplicates_with_extension, detect_type3_clones, normalize, CloneMatch, RollingHash,
    Token,
};
pub use parsing::{
    extract_functions, extract_javascript_functions, extract_python_functions,
    extract_rust_functions, FunctionNode,
};

use anyhow::{anyhow, Context, Result};
use ignore::WalkBuilder;
use rayon::prelude::*;
use serde::{Deserialize, Serialize};
use std::fs;
use std::path::{Path, PathBuf};
use std::sync::Arc;
use tree_sitter::Language;

/// Clone type classification
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
pub enum CloneType {
    /// Type-1: Exact copies (only whitespace/comments differ)
    #[serde(rename = "type-1")]
    Type1,
    /// Type-2: Structurally identical but renamed identifiers/literals
    #[serde(rename = "type-2")]
    Type2,
    /// Type-3: Near-miss clones with modifications (not yet implemented)
    #[serde(rename = "type-3")]
    Type3,
}

/// Helper function to check if two ranges overlap
fn ranges_overlap(start1: usize, end1: usize, start2: usize, end2: usize) -> bool {
    start1 < end2 && start2 < end1
}

// Stable key for deduplicating matches within the same file pair.
fn canonical_pair_key<'a>(
    func1: &'a FunctionHash,
    func2: &'a FunctionHash,
    source_start: usize,
    target_start: usize,
    length: usize,
) -> (&'a str, &'a str, usize, usize, usize, usize, usize) {
    if func1.file_path.as_ref() < func2.file_path.as_ref() {
        (
            func1.file_path.as_ref(),
            func2.file_path.as_ref(),
            func1.start_line,
            func2.start_line,
            source_start,
            target_start,
            length,
        )
    } else {
        (
            func2.file_path.as_ref(),
            func1.file_path.as_ref(),
            func2.start_line,
            func1.start_line,
            target_start,
            source_start,
            length,
        )
    }
}

/// Represents a detected duplicate code fragment
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
pub struct DuplicateMatch {
    pub file1: String,
    pub file2: String,
    pub start_line1: usize,
    pub start_line2: usize,
    pub length: usize,
    pub similarity: f64,
    pub hash: u64,
    pub clone_type: CloneType,
    /// Edit distance (Type-3 only). None for Type-1/2
    #[serde(skip_serializing_if = "Option::is_none")]
    pub edit_distance: Option<usize>,
}

/// Represents a function with its tokens for duplicate detection
#[derive(Debug, Clone)]
struct FunctionHash {
    file_path: Arc<str>, // Shared ownership, cheap to clone
    #[allow(dead_code)] // Kept for potential future reporting improvements
    function_name: Option<String>,
    #[allow(dead_code)] // Kept for byte-level analysis in future
    start_byte: usize,
    #[allow(dead_code)] // Kept for byte-level analysis in future
    end_byte: usize,
    start_line: usize,
    #[allow(dead_code)] // Kept for future detailed reporting
    end_line: usize,
    tokens: Vec<Token>, // Normalized token sequence
    raw_body: String,   // Original (unnormalized) function body for Type-1 detection
}

/// Baseline snapshot for comparing duplicate detection across runs
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Baseline {
    /// Version of the baseline format
    pub version: String,
    /// Timestamp when baseline was created
    pub created_at: String,
    /// Duplicates that existed at baseline time
    pub duplicates: Vec<DuplicateMatch>,
}

impl Baseline {
    /// Create a new baseline from scan results
    pub fn from_duplicates(duplicates: Vec<DuplicateMatch>) -> Self {
        Self {
            version: env!("CARGO_PKG_VERSION").to_string(),
            created_at: chrono::Utc::now().to_rfc3339(),
            duplicates,
        }
    }

    /// Save baseline to a JSON file
    pub fn save_to_file(&self, path: &Path) -> Result<()> {
        let json =
            serde_json::to_string_pretty(self).context("Failed to serialize baseline to JSON")?;
        fs::write(path, json).context("Failed to write baseline file")?;
        Ok(())
    }

    /// Load baseline from a JSON file
    pub fn load_from_file(path: &Path) -> Result<Self> {
        let content = fs::read_to_string(path)
            .with_context(|| format!("Failed to read baseline file: {}", path.display()))?;
        let baseline: Baseline =
            serde_json::from_str(&content).context("Failed to parse baseline JSON")?;
        Ok(baseline)
    }

    /// Compare current duplicates against baseline and return only new ones
    pub fn find_new_duplicates(&self, current: &[DuplicateMatch]) -> Vec<DuplicateMatch> {
        let baseline_set: std::collections::HashSet<_> =
            self.duplicates.iter().map(duplicate_key).collect();

        current
            .iter()
            .filter(|dup| !baseline_set.contains(&duplicate_key(dup)))
            .cloned()
            .collect()
    }
}

/// Create a unique key for a duplicate match for comparison
fn duplicate_key(dup: &DuplicateMatch) -> (String, String, usize, usize, usize) {
    // Normalize file order for consistent comparison
    let (file1, file2, line1, line2) = if dup.file1 < dup.file2 {
        (
            dup.file1.clone(),
            dup.file2.clone(),
            dup.start_line1,
            dup.start_line2,
        )
    } else {
        (
            dup.file2.clone(),
            dup.file1.clone(),
            dup.start_line2,
            dup.start_line1,
        )
    };
    (file1, file2, line1, line2, dup.length)
}

/// Report containing scan results
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Report {
    /// PolyDup version
    #[serde(skip_serializing_if = "Option::is_none")]
    pub version: Option<String>,
    /// Scan start time (ISO 8601)
    #[serde(skip_serializing_if = "Option::is_none")]
    pub scan_time: Option<String>,
    /// Configuration used for the scan
    #[serde(skip_serializing_if = "Option::is_none")]
    pub config: Option<ScanConfig>,
    /// Total number of files scanned
    pub files_scanned: usize,
    /// Total number of functions analyzed
    pub functions_analyzed: usize,
    /// Detected duplicate matches
    pub duplicates: Vec<DuplicateMatch>,
    /// Scan statistics
    pub stats: ScanStats,
}

/// Configuration used for scanning
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ScanConfig {
    /// Minimum block size in tokens
    pub threshold: usize,
    /// Similarity threshold (0.0 - 1.0)
    pub similarity: f64,
    /// Type-3 detection enabled
    pub type3_enabled: bool,
    /// Paths scanned
    #[serde(skip_serializing_if = "Option::is_none")]
    pub paths: Option<Vec<String>>,
}

/// Statistics from the scanning process
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ScanStats {
    /// Total lines of code scanned
    pub total_lines: usize,
    /// Total tokens processed
    pub total_tokens: usize,
    /// Number of unique hashes computed
    pub unique_hashes: usize,
    /// Scan duration in milliseconds
    pub duration_ms: u64,
}

/// Main scanner for detecting duplicates
#[allow(dead_code)] // similarity_threshold reserved for future use
pub struct Scanner {
    /// Minimum code block size to consider (in tokens)
    min_block_size: usize,
    /// Similarity threshold (0.0 - 1.0)
    similarity_threshold: f64,
    /// Glob patterns to exclude from scanning
    exclude_patterns: Vec<String>,
    /// Enable Type-3 (gap-tolerant) clone detection
    enable_type3: bool,
    /// Type-3 similarity tolerance (0.0 - 1.0)
    type3_tolerance: f64,
}

impl Scanner {
    /// Creates a new Scanner with default settings
    ///
    /// This is now infallible as there are no I/O or allocation failures.
    pub fn new() -> Self {
        Self {
            min_block_size: 50,
            similarity_threshold: 0.85,
            exclude_patterns: vec![
                "**/*.test.ts".to_string(),
                "**/*.test.js".to_string(),
                "**/*.test.tsx".to_string(),
                "**/*.test.jsx".to_string(),
                "**/*.spec.ts".to_string(),
                "**/*.spec.js".to_string(),
                "**/*.spec.tsx".to_string(),
                "**/*.spec.jsx".to_string(),
                "**/__tests__/**".to_string(),
                "**/*.test.py".to_string(),
            ],
            enable_type3: false,
            type3_tolerance: 0.85,
        }
    }

    /// Creates a new Scanner with custom settings
    pub fn with_config(min_block_size: usize, similarity_threshold: f64) -> Result<Self> {
        Ok(Self {
            min_block_size,
            similarity_threshold,
            exclude_patterns: vec![
                "**/*.test.ts".to_string(),
                "**/*.test.js".to_string(),
                "**/*.test.tsx".to_string(),
                "**/*.test.jsx".to_string(),
                "**/*.spec.ts".to_string(),
                "**/*.spec.js".to_string(),
                "**/*.spec.tsx".to_string(),
                "**/*.spec.jsx".to_string(),
                "**/__tests__/**".to_string(),
                "**/*.test.py".to_string(),
            ],
            enable_type3: false,
            type3_tolerance: 0.85,
        })
    }

    /// Sets custom exclude patterns, replacing the defaults
    pub fn with_exclude_patterns(mut self, patterns: Vec<String>) -> Self {
        self.exclude_patterns = patterns;
        self
    }

    /// Enables Type-3 clone detection with the specified tolerance
    pub fn with_type3_detection(mut self, tolerance: f64) -> Result<Self> {
        if !(0.0..=1.0).contains(&tolerance) {
            return Err(anyhow!("Type-3 tolerance must be between 0.0 and 1.0"));
        }
        self.enable_type3 = true;
        self.type3_tolerance = tolerance;
        Ok(self)
    }

    /// Scans the given paths and returns a Report with detected duplicates
    ///
    /// Uses Rayon for parallel file processing:
    /// 1. Read and parse files
    /// 2. Extract functions
    /// 3. Normalize and hash function bodies
    /// 4. Compare hashes to find duplicates
    pub fn scan(&self, paths: Vec<PathBuf>) -> Result<Report> {
        use std::time::Instant;
        let start_time = Instant::now();

        // Collect all source files
        let source_files = self.collect_source_files(paths)?;

        // Process files in parallel using Rayon
        let function_hashes: Vec<FunctionHash> = source_files
            .par_iter()
            .filter_map(|path| self.process_file(path).ok())
            .flatten()
            .collect();

        // Find duplicates by comparing hashes
        let duplicates = self.find_duplicate_hashes(&function_hashes);

        // Calculate statistics
        let total_tokens: usize = function_hashes.iter().map(|fh| fh.tokens.len()).sum();

        let unique_hashes: usize = {
            let mut hash_set = std::collections::HashSet::new();
            for fh in &function_hashes {
                // Compute rolling hashes just for statistics
                let hashes = compute_rolling_hashes(&fh.tokens, self.min_block_size);
                for (hash, _) in hashes {
                    hash_set.insert(hash);
                }
            }
            hash_set.len()
        };

        let duration_ms = start_time.elapsed().as_millis() as u64;

        // Count total lines across all source files
        let total_lines: usize = source_files
            .iter()
            .filter_map(|path| std::fs::read_to_string(path).ok())
            .map(|content| content.lines().count())
            .sum();

        Ok(Report {
            version: None,   // Will be set by CLI
            scan_time: None, // Will be set by CLI
            config: None,    // Will be set by CLI
            files_scanned: source_files.len(),
            functions_analyzed: function_hashes.len(),
            duplicates,
            stats: ScanStats {
                total_lines,
                total_tokens,
                unique_hashes,
                duration_ms,
            },
        })
    }

    /// Collects all source files from the given paths
    ///
    /// Uses the `ignore` crate to respect .gitignore, .ignore files,
    /// and common ignore patterns (node_modules, target, etc.)
    fn collect_source_files(&self, paths: Vec<PathBuf>) -> Result<Vec<PathBuf>> {
        let mut files = Vec::new();

        for path in paths {
            if path.is_file() {
                if self.is_supported_file(&path) && !self.is_excluded(&path) {
                    files.push(path);
                }
            } else if path.is_dir() {
                // Use ignore crate's WalkBuilder to respect .gitignore
                let walker = WalkBuilder::new(&path)
                    .git_ignore(true) // Respect .gitignore
                    .git_global(true) // Respect global gitignore
                    .git_exclude(true) // Respect .git/info/exclude
                    .ignore(true) // Respect .ignore files
                    .hidden(false) // Don't skip hidden files (e.g., .config/)
                    .parents(true) // Respect parent .gitignore files
                    .build();

                for entry in walker {
                    match entry {
                        Ok(entry) => {
                            let path = entry.path();
                            if path.is_file()
                                && self.is_supported_file(path)
                                && !self.is_excluded(path)
                            {
                                files.push(path.to_path_buf());
                            }
                        }
                        Err(err) => {
                            // Log but don't fail on individual entry errors
                            eprintln!("Warning: Failed to access path: {}", err);
                        }
                    }
                }
            }
        }

        Ok(files)
    }

    /// Checks if a file is a supported source file
    fn is_supported_file(&self, path: &Path) -> bool {
        if let Some(ext) = path.extension().and_then(|e| e.to_str()) {
            matches!(ext, "rs" | "py" | "js" | "ts" | "jsx" | "tsx")
        } else {
            false
        }
    }

    /// Checks if a file matches any exclude patterns
    fn is_excluded(&self, path: &Path) -> bool {
        use globset::{Glob, GlobSetBuilder};

        // Build glob set from exclude patterns
        let mut builder = GlobSetBuilder::new();
        for pattern in &self.exclude_patterns {
            if let Ok(glob) = Glob::new(pattern) {
                builder.add(glob);
            }
        }

        if let Ok(glob_set) = builder.build() {
            glob_set.is_match(path)
        } else {
            false
        }
    }

    /// Processes a single file and returns function hashes
    fn process_file(&self, path: &Path) -> Result<Vec<FunctionHash>> {
        let code = fs::read_to_string(path).context(format!("Failed to read file: {:?}", path))?;

        let lang = self.detect_language(path)?;
        let functions = extract_functions(&code, lang)?;

        // Use Arc<str> for efficient sharing across all functions in this file
        let file_path: Arc<str> = path.to_string_lossy().to_string().into();
        let mut function_hashes = Vec::new();

        for func in functions {
            // Store both raw body (for Type-1) and normalized tokens (for Type-2)
            let raw_body = func.body.clone();
            let tokens = normalize(&func.body);

            // Skip if too small
            if tokens.len() < self.min_block_size {
                continue;
            }

            // Store the full token sequence for extension-based detection
            function_hashes.push(FunctionHash {
                file_path: Arc::clone(&file_path), // Cheap pointer clone
                function_name: func.name.clone(),
                start_byte: func.start_byte,
                end_byte: func.end_byte,
                start_line: func.start_line,
                end_line: func.end_line,
                tokens,
                raw_body,
            });
        }

        Ok(function_hashes)
    }

    /// Detects the Tree-sitter Language from file extension
    fn detect_language(&self, path: &Path) -> Result<Language> {
        let ext = path
            .extension()
            .and_then(|e| e.to_str())
            .ok_or_else(|| anyhow!("No file extension"))?;

        match ext {
            "rs" => Ok(tree_sitter_rust::language()),
            "py" => Ok(tree_sitter_python::language()),
            "js" | "jsx" | "ts" | "tsx" => Ok(tree_sitter_javascript::language()),
            _ => Err(anyhow!("Unsupported file extension: {}", ext)),
        }
    }

    /// Finds duplicate code using greedy extension algorithm
    fn find_duplicate_hashes(&self, function_hashes: &[FunctionHash]) -> Vec<DuplicateMatch> {
        let mut duplicates = Vec::new();
        let mut seen_pairs: std::collections::HashSet<(
            &str,
            &str,
            usize,
            usize,
            usize,
            usize,
            usize,
        )> = std::collections::HashSet::new();

        // Compare each pair of functions
        for i in 0..function_hashes.len() {
            for j in (i + 1)..function_hashes.len() {
                let func1 = &function_hashes[i];
                let func2 = &function_hashes[j];

                // Use extension-based detection on each function's tokens
                let matches = self.find_clones_between_functions(func1, func2);

                for clone_match in matches {
                    // Create pair key for deduplication using string slices (no cloning)
                    let pair_key = canonical_pair_key(
                        func1,
                        func2,
                        clone_match.source_start,
                        clone_match.target_start,
                        clone_match.length,
                    );

                    if seen_pairs.contains(&pair_key) {
                        continue;
                    }
                    seen_pairs.insert(pair_key);

                    // Compute a hash for this match for reporting
                    use std::collections::hash_map::DefaultHasher;
                    use std::hash::{Hash, Hasher};
                    let mut hasher = DefaultHasher::new();
                    func1.tokens
                        [clone_match.source_start..clone_match.source_start + clone_match.length]
                        .hash(&mut hasher);
                    let match_hash = hasher.finish();

                    // Determine clone type by comparing raw function bodies
                    // (simplified: compares entire bodies, not just the clone region)
                    let clone_type = self.classify_clone_type(&func1.raw_body, &func2.raw_body);

                    // Calculate actual line numbers within the code
                    let actual_start1 = func1.start_line + clone_match.source_start;
                    let actual_start2 = func2.start_line + clone_match.target_start;

                    // Skip if this is the exact same location (same file, same line)
                    // This can happen with overlapping function boundaries
                    if func1.file_path == func2.file_path && actual_start1 == actual_start2 {
                        continue;
                    }

                    duplicates.push(DuplicateMatch {
                        file1: func1.file_path.to_string(),
                        file2: func2.file_path.to_string(),
                        start_line1: actual_start1,
                        start_line2: actual_start2,
                        length: clone_match.length,
                        similarity: clone_match.similarity,
                        hash: match_hash,
                        clone_type,
                        edit_distance: None, // Type-1/2 don't have edit distance
                    });
                }
            }
        }

        // Type-3 detection (gap-tolerant) if enabled
        if self.enable_type3 {
            // Collect all Type-3 matches first
            let mut type3_candidates = Vec::new();

            for i in 0..function_hashes.len() {
                for j in (i + 1)..function_hashes.len() {
                    let func1 = &function_hashes[i];
                    let func2 = &function_hashes[j];

                    // Type-3 detection works for both same-file and cross-file clones
                    // (Type-1/2 already handled same-file detection)

                    // Detect Type-3 clones
                    let type3_matches = detect_type3_clones(
                        &func1.tokens,
                        &func2.tokens,
                        self.min_block_size,
                        self.type3_tolerance,
                    );

                    for clone_match in type3_matches {
                        // Check if this overlaps with existing Type-1/2 matches
                        let pair_key = canonical_pair_key(
                            func1,
                            func2,
                            clone_match.source_start,
                            clone_match.target_start,
                            clone_match.length,
                        );

                        if seen_pairs.contains(&pair_key) {
                            continue;
                        }

                        type3_candidates.push((func1, func2, clone_match));
                    }
                }
            }

            // Deduplicate overlapping Type-3 matches
            let deduplicated = self.deduplicate_overlapping_matches(type3_candidates);

            // Convert deduplicated matches to DuplicateMatch
            for (func1, func2, clone_match) in deduplicated {
                // Calculate edit distance for Type-3 using our custom implementation
                let window1 = &func1.tokens
                    [clone_match.source_start..clone_match.source_start + clone_match.length];
                let window2 = &func2.tokens[clone_match.target_start
                    ..clone_match.target_start + clone_match.target_length];
                let edit_dist = hashing::compute_token_edit_distance(window1, window2);

                // Compute hash for Type-3 match
                use std::collections::hash_map::DefaultHasher;
                use std::hash::{Hash, Hasher};
                let mut hasher = DefaultHasher::new();
                window1.hash(&mut hasher);
                let match_hash = hasher.finish();

                duplicates.push(DuplicateMatch {
                    file1: func1.file_path.to_string(),
                    file2: func2.file_path.to_string(),
                    start_line1: func1.start_line,
                    start_line2: func2.start_line,
                    length: clone_match.length,
                    similarity: clone_match.similarity,
                    hash: match_hash,
                    clone_type: CloneType::Type3,
                    edit_distance: Some(edit_dist),
                });
            }
        }

        duplicates
    }

    /// Deduplicates overlapping Type-3 matches by keeping only the longest match per region
    ///
    /// Groups matches by (file1, file2, func1_line, func2_line) to handle same-file clones properly.
    /// Merges overlapping regions, keeping the longest match with the highest similarity score.
    /// Overlap requires BOTH source AND target ranges to overlap.
    fn deduplicate_overlapping_matches<'a>(
        &self,
        candidates: Vec<(&'a FunctionHash, &'a FunctionHash, CloneMatch)>,
    ) -> Vec<(&'a FunctionHash, &'a FunctionHash, CloneMatch)> {
        if candidates.is_empty() {
            return Vec::new();
        }

        // Track which matches have been merged
        let mut used = vec![false; candidates.len()];
        let mut deduplicated = Vec::new();

        for i in 0..candidates.len() {
            if used[i] {
                continue;
            }

            let (func1, func2, current) = &candidates[i];
            let mut best_match = (*func1, *func2, current.clone());
            used[i] = true;

            // Find all overlapping matches (iterate until no more overlaps found)
            // This handles transitive overlaps: A overlaps B, B overlaps C
            let mut found_overlap = true;
            while found_overlap {
                found_overlap = false;

                for j in (i + 1)..candidates.len() {
                    if used[j] {
                        continue;
                    }

                    let (f1, f2, candidate) = &candidates[j];

                    // Only merge if same function pair (by file path and line number)
                    let same_pair = (func1.file_path == f1.file_path
                        && func2.file_path == f2.file_path
                        && func1.start_line == f1.start_line
                        && func2.start_line == f2.start_line)
                        || (func1.file_path == f2.file_path
                            && func2.file_path == f1.file_path
                            && func1.start_line == f2.start_line
                            && func2.start_line == f1.start_line);

                    if !same_pair {
                        continue;
                    }

                    // Check if overlapping with CURRENT best_match (not original)
                    // This ensures transitive overlaps are handled correctly
                    let source_overlap = ranges_overlap(
                        best_match.2.source_start,
                        best_match.2.source_start + best_match.2.length,
                        candidate.source_start,
                        candidate.source_start + candidate.length,
                    );
                    let target_overlap = ranges_overlap(
                        best_match.2.target_start,
                        best_match.2.target_start + best_match.2.target_length,
                        candidate.target_start,
                        candidate.target_start + candidate.target_length,
                    );

                    if source_overlap && target_overlap {
                        let best_span = best_match.2.length.max(best_match.2.target_length);
                        let candidate_span = candidate.length.max(candidate.target_length);

                        // Keep the match that covers more tokens overall, breaking ties by similarity
                        if candidate_span > best_span
                            || (candidate_span == best_span
                                && candidate.similarity > best_match.2.similarity)
                        {
                            best_match = (*f1, *f2, candidate.clone());
                            found_overlap = true; // Need another pass to check against new best
                        }
                        used[j] = true;
                    }
                }
            }

            deduplicated.push(best_match);
        }

        deduplicated
    }

    /// Classifies a clone as Type-1 (exact) or Type-2 (renamed)
    fn classify_clone_type(&self, raw1: &str, raw2: &str) -> CloneType {
        // Normalize whitespace for comparison (avoid intermediate Vec allocation)
        let normalized1 = raw1.split_whitespace().collect::<String>();
        let normalized2 = raw2.split_whitespace().collect::<String>();

        // If raw code is identical (ignoring whitespace), it's Type-1 (exact copy)
        if normalized1 == normalized2 {
            CloneType::Type1
        } else {
            // Otherwise, it's Type-2 (renamed identifiers/literals)
            CloneType::Type2
        }
    }

    /// Finds clone matches between two functions using extension algorithm
    fn find_clones_between_functions(
        &self,
        func1: &FunctionHash,
        func2: &FunctionHash,
    ) -> Vec<CloneMatch> {
        use std::collections::HashMap;

        let mut matches = Vec::new();
        let mut hash_map: HashMap<u64, Vec<usize>> = HashMap::new();

        // Index all windows in func1
        let mut i = 0;
        while i <= func1.tokens.len().saturating_sub(self.min_block_size) {
            let hash = self.compute_window_hash(&func1.tokens[i..i + self.min_block_size]);
            hash_map.entry(hash).or_default().push(i);
            i += 1;
        }

        // Search for matches in func2
        let mut j = 0;
        while j <= func2.tokens.len().saturating_sub(self.min_block_size) {
            let hash = self.compute_window_hash(&func2.tokens[j..j + self.min_block_size]);

            if let Some(func1_positions) = hash_map.get(&hash) {
                for &func1_pos in func1_positions {
                    // Verify exact match
                    if self.verify_window_match(
                        &func1.tokens,
                        &func2.tokens,
                        func1_pos,
                        j,
                        self.min_block_size,
                    ) {
                        // Greedy extension
                        let mut extension = 0;
                        while (func1_pos + self.min_block_size + extension < func1.tokens.len())
                            && (j + self.min_block_size + extension < func2.tokens.len())
                            && (func1.tokens[func1_pos + self.min_block_size + extension]
                                == func2.tokens[j + self.min_block_size + extension])
                        {
                            extension += 1;
                        }

                        let total_length = self.min_block_size + extension;

                        matches.push(CloneMatch {
                            source_start: func1_pos,
                            target_start: j,
                            length: total_length,
                            target_length: total_length,
                            similarity: 1.0, // Exact match
                        });

                        // Skip ahead
                        j += extension.max(1);
                        break;
                    }
                }
            }

            j += 1;
        }

        matches
    }

    /// Computes hash for a token window
    ///
    /// Uses Rabin-Karp polynomial rolling hash with:
    /// - BASE = 257 (prime > 256 to minimize collisions)
    /// - MODULUS = 1e9+7 (large prime for hash space)
    fn compute_window_hash(&self, window: &[Token]) -> u64 {
        /// Prime base for polynomial rolling hash
        const BASE: u64 = 257;
        /// Large prime modulus to reduce hash collisions
        const MODULUS: u64 = 1_000_000_007;

        let mut hash: u64 = 0;
        for token in window {
            use std::collections::hash_map::DefaultHasher;
            use std::hash::{Hash, Hasher};
            let mut hasher = DefaultHasher::new();
            token.as_hash_string().hash(&mut hasher);
            let token_hash = hasher.finish();
            // Use u128 to prevent overflow before modulo operation
            let wide_hash = (hash as u128 * BASE as u128 + token_hash as u128) % MODULUS as u128;
            hash = wide_hash as u64;
        }
        hash
    }

    /// Verifies that two token windows are exactly identical
    fn verify_window_match(
        &self,
        tokens1: &[Token],
        tokens2: &[Token],
        idx1: usize,
        idx2: usize,
        len: usize,
    ) -> bool {
        if idx1 + len > tokens1.len() || idx2 + len > tokens2.len() {
            return false;
        }
        tokens1[idx1..idx1 + len] == tokens2[idx2..idx2 + len]
    }
}

impl Default for Scanner {
    fn default() -> Self {
        Self::new() // Infallible now, no panic possible
    }
}

/// Public API: Find duplicates in the given file paths
///
/// # Arguments
/// * `paths` - Vector of file paths to scan
///
/// # Returns
/// * `Result<Report>` - Scan report with detected duplicates
pub fn find_duplicates(paths: Vec<String>) -> Result<Report> {
    let scanner = Scanner::new();
    let path_bufs: Vec<PathBuf> = paths.into_iter().map(PathBuf::from).collect();
    scanner.scan(path_bufs)
}

/// Public API with custom configuration
pub fn find_duplicates_with_config(
    paths: Vec<String>,
    min_block_size: usize,
    similarity_threshold: f64,
) -> Result<Report> {
    let scanner = Scanner::with_config(min_block_size, similarity_threshold)?;
    let path_bufs: Vec<PathBuf> = paths.into_iter().map(PathBuf::from).collect();
    scanner.scan(path_bufs)
}

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

    #[test]
    fn test_scanner_creation() {
        let _scanner = Scanner::new(); // Infallible
    }

    #[test]
    fn test_scanner_with_config() {
        let scanner = Scanner::with_config(30, 0.9);
        assert!(scanner.is_ok());
        let s = scanner.unwrap();
        assert_eq!(s.min_block_size, 30);
        assert_eq!(s.similarity_threshold, 0.9);
    }

    #[test]
    fn test_type3_tolerance_validation() {
        assert!(Scanner::new().with_type3_detection(0.9).is_ok());
        assert!(Scanner::new().with_type3_detection(1.2).is_err());
        assert!(Scanner::new().with_type3_detection(-0.1).is_err());
    }

    #[test]
    fn test_type3_not_dropped_when_functions_share_offsets() {
        fn make_function(
            file: &str,
            start_line: usize,
            tokens: Vec<Token>,
            raw_body: &str,
        ) -> FunctionHash {
            FunctionHash {
                file_path: Arc::<str>::from(file),
                function_name: None,
                start_byte: 0,
                end_byte: 0,
                start_line,
                end_line: start_line + tokens.len(),
                tokens,
                raw_body: raw_body.to_string(),
            }
        }

        let scanner = Scanner::with_config(3, 0.85)
            .unwrap()
            .with_type3_detection(0.6)
            .unwrap();

        let type1_tokens = vec![
            Token::Keyword("return".into()),
            Token::NumberLiteral,
            Token::Punctuation(";".into()),
        ];
        let near_tokens_a = vec![
            Token::Keyword("compute".into()),
            Token::Identifier,
            Token::Identifier,
        ];
        let near_tokens_b = vec![
            Token::Keyword("compute".into()),
            Token::Identifier,
            Token::NumberLiteral,
        ];

        let functions = vec![
            make_function("file_a.rs", 10, type1_tokens.clone(), "return 1;"),
            make_function("file_b.rs", 20, type1_tokens, "return 1;"),
            make_function("file_a.rs", 200, near_tokens_a, "compute(x, y)"),
            make_function("file_b.rs", 300, near_tokens_b, "compute(x, 1)"),
        ];

        let duplicates = scanner.find_duplicate_hashes(&functions);

        let type1_present = duplicates.iter().any(|d| {
            matches!(d.clone_type, CloneType::Type1 | CloneType::Type2)
                && d.start_line1 == 10
                && d.start_line2 == 20
        });
        assert!(
            type1_present,
            "expected Type-1/2 match for the first function pair"
        );

        let type3_present = duplicates.iter().any(|d| {
            matches!(d.clone_type, CloneType::Type3) && d.start_line1 == 200 && d.start_line2 == 300
        });
        assert!(
            type3_present,
            "Type-3 match between later functions should not be deduped"
        );

        assert_eq!(
            duplicates.len(),
            2,
            "should keep both the Type-1/2 and Type-3 matches"
        );
    }

    #[test]
    fn test_find_duplicates_empty() {
        let result = find_duplicates(vec![]);
        assert!(result.is_ok());
        let report = result.unwrap();
        assert_eq!(report.duplicates.len(), 0);
    }

    #[test]
    fn test_is_supported_file() {
        let scanner = Scanner::new();

        assert!(scanner.is_supported_file(Path::new("test.rs")));
        assert!(scanner.is_supported_file(Path::new("test.py")));
        assert!(scanner.is_supported_file(Path::new("test.js")));
        assert!(scanner.is_supported_file(Path::new("test.ts")));
        assert!(!scanner.is_supported_file(Path::new("test.txt")));
        assert!(!scanner.is_supported_file(Path::new("test.md")));
    }

    #[test]
    fn test_detect_language() {
        let scanner = Scanner::new();

        assert!(scanner.detect_language(Path::new("test.rs")).is_ok());
        assert!(scanner.detect_language(Path::new("test.py")).is_ok());
        assert!(scanner.detect_language(Path::new("test.js")).is_ok());
        assert!(scanner.detect_language(Path::new("test.txt")).is_err());
    }
}