cpd_core/

detect.rs

// detect.rs

use rayon::prelude::*;
use rustc_hash::{FxHashMap, FxHashSet};
use std::path::{Path, PathBuf};

use crate::{
    hash::{base_pow, hash_window, roll, token_hash},
    models::{CpdClone, DetectionToken, Fragment, Location, SourceFile, TokenKind},
};

// ---------------------------------------------------------------------------
// Internal store type — replaces the Store trait + MemoryStore
// ---------------------------------------------------------------------------

/// Window store: maps a window hash to the last seen occurrence.
/// Type alias — no trait indirection, no vtable, no dyn dispatch.
type WindowStore = FxHashMap<u64, Occurrence>;

/// Lightweight reference to a window position within a format-group detection call.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Occurrence {
    /// Index into the `prepared` array for this `detect_in_group` call.
    source_id: usize,
    token_start: usize,
}

// ---------------------------------------------------------------------------
// Deduplication key
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct CloneDedupKey {
    a_id: String,
    a_start_line: u32,
    b_id: String,
    b_start_line: u32,
}

impl CloneDedupKey {
    fn from_clone(c: &CpdClone) -> Self {
        // Normalize: smaller (id, line) first so (A,B) and (B,A) map to the same key.
        let a_key = (&c.fragment_a.source_id, c.fragment_a.start.line);
        let b_key = (&c.fragment_b.source_id, c.fragment_b.start.line);
        if a_key <= b_key {
            Self {
                a_id: c.fragment_a.source_id.clone(),
                a_start_line: c.fragment_a.start.line,
                b_id: c.fragment_b.source_id.clone(),
                b_start_line: c.fragment_b.start.line,
            }
        } else {
            Self {
                a_id: c.fragment_b.source_id.clone(),
                a_start_line: c.fragment_b.start.line,
                b_id: c.fragment_a.source_id.clone(),
                b_start_line: c.fragment_a.start.line,
            }
        }
    }
}

// ---------------------------------------------------------------------------
// Public API — SourceFile path (for backward compat with tests)
// ---------------------------------------------------------------------------

/// Detect duplicate code clones across `files` using a rolling-hash sliding window.
///
/// Files are grouped by format; each format group is processed independently.
/// Rayon is used for outer parallelism (one task per format group).
pub fn detect(files: &[SourceFile], min_tokens: usize) -> Vec<CpdClone> {
    detect_with_options(files, min_tokens, false, 0, &[])
}

/// Detect clones with extended options.
///
/// - `skip_local`: skip clone pairs where both fragments are under the same scan root.
/// - `min_lines`: reject clones whose fragment line span is shorter than this.
///   The line span is `end.line - start.line`; a clone is kept only if this value
///   is >= `min_lines`. This mirrors jscpd's `LinesLengthCloneValidator`.
/// - `scan_roots`: when `skip_local` is true, clone pairs where both fragments
///   are relative to the same scan root are skipped. Mirrors jscpd's
///   `SkipLocalValidator` which checks `path.some(dir => isRelative(fileA, dir) && isRelative(fileB, dir))`.
pub fn detect_with_options(
    files: &[SourceFile],
    min_tokens: usize,
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
) -> Vec<CpdClone> {
    if files.is_empty() || min_tokens == 0 {
        return vec![];
    }

    // Group files by format. Sort for deterministic order.
    let mut by_format: FxHashMap<&str, Vec<&SourceFile>> = FxHashMap::default();
    for file in files {
        by_format
            .entry(file.format.as_str())
            .or_default()
            .push(file);
    }
    let mut format_groups: Vec<(&str, Vec<&SourceFile>)> = by_format.into_iter().collect();
    format_groups.sort_unstable_by_key(|(fmt, _)| *fmt);
    for (_, group) in &mut format_groups {
        group.sort_unstable_by_key(|&file| file.id.as_str());
    }

    let mut clones: Vec<CpdClone> = format_groups
        .into_par_iter()
        .flat_map(|(_format, files)| {
            // Build per-group prepared data from SourceFile.tokens.
            // This is the backward-compat path; orchestrate.rs uses
            // detect_prepared() directly to avoid re-hashing.
            let prepared: Vec<PreparedSource> = files
                .into_iter()
                .map(|file| {
                    let mut hashes = Vec::with_capacity(file.tokens.len());
                    let mut spans: Vec<(Location, Location)> =
                        Vec::with_capacity(file.tokens.len());
                    for t in &file.tokens {
                        if t.kind == TokenKind::Ignore {
                            continue;
                        }
                        hashes.push(token_hash(t.kind.discriminant(), &t.value));
                        spans.push((t.start.clone(), t.end.clone()));
                    }
                    PreparedSource {
                        id: file.id.clone(),
                        format: file.format.clone(),
                        hashes,
                        spans,
                    }
                })
                .collect();
            detect_in_group(&prepared, min_tokens, skip_local, min_lines, scan_roots)
        })
        .collect();

    finalize_clones(&mut clones);
    clones
}

fn finalize_clones(clones: &mut Vec<CpdClone>) {
    dedup_exact_clones(clones);
    clones.sort_by(|a, b| {
        (
            &a.fragment_a.source_id,
            a.fragment_a.start.line,
            &a.fragment_b.source_id,
            a.fragment_b.start.line,
        )
            .cmp(&(
                &b.fragment_a.source_id,
                b.fragment_a.start.line,
                &b.fragment_b.source_id,
                b.fragment_b.start.line,
            ))
    });
}

// ---------------------------------------------------------------------------
// Direct DetectionToken path (called by orchestrate.rs)
// ---------------------------------------------------------------------------

/// A file ready for detection: pre-hashed, pre-filtered.
///
/// Produced either from `SourceFile.tokens` (backward compat) or directly from
/// `tokenize_to_detection` output (fast path used by orchestrate.rs).
pub struct PreparedSource {
    pub id: String,
    pub format: String,
    pub hashes: Vec<u64>,
    pub spans: Vec<(Location, Location)>,
}

impl PreparedSource {
    /// Build from a `DetectionToken` slice — the fast path.
    pub fn from_detection_tokens(id: String, format: String, tokens: &[DetectionToken]) -> Self {
        let mut hashes = Vec::with_capacity(tokens.len());
        let mut spans = Vec::with_capacity(tokens.len());
        for t in tokens {
            hashes.push(t.hash);
            spans.push((t.start.clone(), t.end.clone()));
        }
        Self {
            id,
            format,
            hashes,
            spans,
        }
    }
}

/// Detect clones from pre-prepared sources grouped by format.
///
/// Called by orchestrate.rs after `tokenize_to_detection` — skips re-hashing.
/// - `scan_roots`: when `skip_local` is true, clone pairs where both fragments
///   are relative to the same scan root are skipped.
pub fn detect_prepared(
    format_groups: Vec<Vec<PreparedSource>>,
    min_tokens: usize,
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
) -> Vec<CpdClone> {
    if format_groups.is_empty() || min_tokens == 0 {
        return vec![];
    }

    let mut clones: Vec<CpdClone> = format_groups
        .into_par_iter()
        .flat_map(|group| detect_in_group(&group, min_tokens, skip_local, min_lines, scan_roots))
        .collect();

    finalize_clones(&mut clones);
    clones
}

// ---------------------------------------------------------------------------
// Core detection — per format group
// ---------------------------------------------------------------------------

fn detect_in_group(
    prepared: &[PreparedSource],
    min_tokens: usize,
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
) -> Vec<CpdClone> {
    // Precompute window_power once for this format group.
    // If per-language min_tokens is introduced, recompute per group (it is already scoped here).
    let window_power = base_pow(min_tokens.saturating_sub(1));

    // Pre-allocate store capacity to avoid FxHashMap rehashing.
    let total_windows: usize = prepared
        .iter()
        .map(|p| p.hashes.len().saturating_sub(min_tokens))
        .sum();
    let mut store: WindowStore =
        FxHashMap::with_capacity_and_hasher(total_windows, Default::default());

    let mut clones: Vec<CpdClone> = Vec::new();
    // Cap repeated-window occurrences per hash. Higher values find more clone pairs
    // among 3+ similar files (e.g., file_1.js, file_1.mjs, file_1.cjs) but use more memory.
    // The TypeScript jscpd compares all file pairs, so we raise this to match its coverage.
    const SECONDARY_OCCURRENCE_CAP: usize = 2;
    let mut repeated_windows: FxHashMap<u64, Vec<Occurrence>> = FxHashMap::default();

    for (file_idx, source) in prepared.iter().enumerate() {
        let hashes = &source.hashes;
        if hashes.len() < min_tokens {
            continue;
        }
        let windows_len = hashes.len() - min_tokens + 1;

        // open_clone state machine: replaces emit-every-window + suppress_subclones.
        // A clone is opened when a matching window is found and enlarged as long as
        // subsequent windows also match. flush_clone is called when the match breaks
        // or the file scan ends — only one clone per contiguous matching region.
        let mut open_clone: Option<OpenClone> = None;

        let mut window_hash = hash_window(&hashes[..min_tokens]);

        for token_start in 0..windows_len {
            if token_start > 0 {
                window_hash = roll(
                    window_hash,
                    hashes[token_start - 1],
                    hashes[token_start + min_tokens - 1],
                    window_power,
                );
            }

            let current = Occurrence {
                source_id: file_idx,
                token_start,
            };

            match store.get(&window_hash).copied() {
                Some(stored) if windows_match(stored, current, prepared, min_tokens) => {
                    if open_clone.is_none() {
                        open_clone = Some(OpenClone {
                            stored_occurrence: stored,
                            current_start: token_start,
                            match_len: min_tokens,
                        });
                    } else if let Some(ref mut oc) = open_clone {
                        // Enlarge: the next window also matches — extend by one token.
                        oc.match_len += 1;
                    }
                    remember_repeated_window(
                        &mut repeated_windows,
                        window_hash,
                        stored,
                        SECONDARY_OCCURRENCE_CAP,
                    );
                    remember_repeated_window(
                        &mut repeated_windows,
                        window_hash,
                        current,
                        SECONDARY_OCCURRENCE_CAP,
                    );
                    // Do NOT update store — keep the first occurrence so the enlargement
                    // stays consistent across the contiguous match region.
                }
                _ => {
                    // Match broke (or no entry). Flush whatever was open.
                    flush_clone(
                        open_clone.take(),
                        file_idx,
                        prepared,
                        skip_local,
                        min_lines,
                        scan_roots,
                        &mut clones,
                    );
                    store.insert(window_hash, current);
                }
            }
        }

        // Flush any open clone at the end of the file scan.
        flush_clone(
            open_clone.take(),
            file_idx,
            prepared,
            skip_local,
            min_lines,
            scan_roots,
            &mut clones,
        );
    }

    add_secondary_clones(
        repeated_windows,
        prepared,
        min_tokens,
        skip_local,
        min_lines,
        scan_roots,
        &mut clones,
    );

    clones
}

// ---------------------------------------------------------------------------
// Open clone state machine helpers
// ---------------------------------------------------------------------------

/// Returns true if both files share a common scan root directory.
/// Mirrors jscpd's `SkipLocalValidator.shouldSkipClone`:
///   `path.some(dir => isRelative(fileA, dir) && isRelative(fileB, dir))`
fn should_skip_local(file_a: &str, file_b: &str, scan_roots: &[PathBuf]) -> bool {
    scan_roots
        .iter()
        .any(|root| is_relative_to(file_a, root) && is_relative_to(file_b, root))
}

/// Returns true if `file_path` is contained within `dir`.
/// Mirrors the TypeScript `SkipLocalValidator.isRelative`:
///   `const rel = relative(dir, file); return rel !== '' && !rel.startsWith('..') && !isAbsolute(rel);`
fn is_relative_to(file_path: &str, dir: &PathBuf) -> bool {
    let file = Path::new(file_path);
    // Fast path: file path starts with the dir prefix
    if let Ok(rel) = file.strip_prefix(dir) {
        return !rel.as_os_str().is_empty();
    }
    // Mixed absolute/relative can never match via simple prefix
    if file.is_absolute() != dir.is_absolute() {
        return false;
    }
    // Walk up from the file path checking if any ancestor starts with dir
    let mut ancestor = file;
    loop {
        if ancestor == dir.as_path() {
            return false;
        }
        if ancestor.starts_with(dir) {
            let rel = ancestor.strip_prefix(dir).unwrap_or(ancestor);
            return !rel.as_os_str().is_empty();
        }
        ancestor = match ancestor.parent() {
            Some(p) => p,
            None => return false,
        };
    }
}

struct OpenClone {
    stored_occurrence: Occurrence,
    current_start: usize,
    match_len: usize,
}

/// Returns true if the window at `current` actually matches the window at `stored`
/// (hash match is necessary but not sufficient — verify token equality).
fn windows_match(
    stored: Occurrence,
    current: Occurrence,
    prepared: &[PreparedSource],
    min_tokens: usize,
) -> bool {
    if stored.source_id == current.source_id && stored.token_start == current.token_start {
        return false;
    }
    let stored_hashes = &prepared[stored.source_id].hashes;
    let current_hashes = &prepared[current.source_id].hashes;
    if stored.token_start + min_tokens > stored_hashes.len()
        || current.token_start + min_tokens > current_hashes.len()
    {
        return false;
    }
    stored_hashes[stored.token_start..stored.token_start + min_tokens]
        == current_hashes[current.token_start..current.token_start + min_tokens]
}

/// Flush an open clone to the clones list.
///
/// A clone is rejected if its line span is shorter than `min_lines`.
/// The line span is measured as `end.line - start.line` (which equals
/// `number_of_lines - 1`). Mirrors jscpd's `LinesLengthCloneValidator`.
fn flush_clone(
    open: Option<OpenClone>,
    current_file_idx: usize,
    prepared: &[PreparedSource],
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
    clones: &mut Vec<CpdClone>,
) {
    let oc = match open {
        Some(o) => o,
        None => return,
    };

    let existing = &oc.stored_occurrence;
    let cur_start = oc.current_start;
    let match_len = oc.match_len;

    let existing_file = &prepared[existing.source_id];
    let current_file = &prepared[current_file_idx];

    let ex_start = existing.token_start;
    let ex_end = ex_start + match_len - 1;
    let cur_end = cur_start + match_len - 1;

    // skip_local: drop clone pairs where both fragments are under the same scan root.
    // Mirrors jscpd's SkipLocalValidator which checks
    //   path.some(dir => isRelative(fileA, dir) && isRelative(fileB, dir))
    if skip_local && should_skip_local(&existing_file.id, &current_file.id, scan_roots) {
        return;
    }

    let fragment_a = match make_fragment(&existing_file.id, &existing_file.spans, ex_start, ex_end)
    {
        Some(f) => f,
        None => return,
    };
    let fragment_b = match make_fragment(&current_file.id, &current_file.spans, cur_start, cur_end)
    {
        Some(f) => f,
        None => return,
    };

    // min_lines filter: reject clones whose fragment A line span is shorter than min_lines.
    // Mirrors jscpd's LinesLengthCloneValidator which checks only duplicationA:
    //   duplicationA.end.line - duplicationA.start.line >= minLines
    if min_lines > 0 {
        let lines = fragment_a.end.line as usize - fragment_a.start.line as usize;
        if lines < min_lines {
            return;
        }
    }

    clones.push(CpdClone {
        format: current_file.format.clone(),
        fragment_a,
        fragment_b,
        token_count: match_len as u32,
    });
}

fn make_fragment(
    source_id: &str,
    spans: &[(Location, Location)],
    start_idx: usize,
    end_idx: usize,
) -> Option<Fragment> {
    let (first_start, _) = spans.get(start_idx)?;
    let (_, last_end) = spans.get(end_idx)?;
    Some(Fragment {
        source_id: source_id.to_string(),
        source_root: None,
        start: first_start.clone(),
        end: last_end.clone(),
        range: [start_idx as u32, end_idx as u32],
        blame: None,
    })
}

// ---------------------------------------------------------------------------
// Deduplication — O(n) FxHashSet + sub-clone suppression
// ---------------------------------------------------------------------------

fn dedup_exact_clones(clones: &mut Vec<CpdClone>) {
    // Normalize each clone so fragment_a <= fragment_b (by id then start line).
    for clone in clones.iter_mut() {
        let a_key = (&clone.fragment_a.source_id, clone.fragment_a.start.line);
        let b_key = (&clone.fragment_b.source_id, clone.fragment_b.start.line);
        if a_key > b_key {
            std::mem::swap(&mut clone.fragment_a, &mut clone.fragment_b);
        }
    }

    let mut seen: FxHashSet<CloneDedupKey> = FxHashSet::default();
    clones.retain(|c| seen.insert(CloneDedupKey::from_clone(c)));
}

// ---------------------------------------------------------------------------
// Secondary clone pass
// ---------------------------------------------------------------------------

fn remember_repeated_window(
    repeated_windows: &mut FxHashMap<u64, Vec<Occurrence>>,
    hash: u64,
    occurrence: Occurrence,
    cap: usize,
) {
    let bucket = repeated_windows.entry(hash).or_default();
    if bucket
        .iter()
        .any(|s| s.source_id == occurrence.source_id && s.token_start == occurrence.token_start)
    {
        return;
    }
    if bucket.len() < cap {
        bucket.push(occurrence);
    }
}

struct SecondaryOpen {
    clone: CpdClone,
    source_a: usize,
    source_b: usize,
    last_token_start_a: usize,
    last_token_start_b: usize,
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Candidate {
    source_a: usize,
    source_b: usize,
    token_a: usize,
    token_b: usize,
}

impl SecondaryOpen {
    /// True when `candidate` extends this open clone by exactly one token on
    /// both sides.
    fn is_continuation(&self, candidate: &Candidate) -> bool {
        self.source_a == candidate.source_a
            && self.source_b == candidate.source_b
            && self.last_token_start_a + 1 == candidate.token_a
            && self.last_token_start_b + 1 == candidate.token_b
    }

    /// Grow the open clone by one token on each side, using `prepared` to
    /// resolve the new endpoint spans.
    fn grow(&mut self, candidate: &Candidate, prepared: &[PreparedSource], min_tokens: usize) {
        self.clone.token_count += 1;
        let end_a = candidate.token_a + min_tokens;
        let end_b = candidate.token_b + min_tokens;
        if let Some(span) = prepared[self.source_a].spans.get(end_a) {
            self.clone.fragment_a.end = span.1.clone();
            self.clone.fragment_a.range[1] = end_a as u32;
        }
        if let Some(span) = prepared[self.source_b].spans.get(end_b) {
            self.clone.fragment_b.end = span.1.clone();
            self.clone.fragment_b.range[1] = end_b as u32;
        }
        self.last_token_start_a = candidate.token_a;
        self.last_token_start_b = candidate.token_b;
    }
}

fn add_secondary_clones(
    repeated_windows: FxHashMap<u64, Vec<Occurrence>>,
    prepared: &[PreparedSource],
    min_tokens: usize,
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
    clones: &mut Vec<CpdClone>,
) {
    if repeated_windows.is_empty() {
        return;
    }

    let mut candidates: Vec<Candidate> = Vec::new();
    for occurrences in repeated_windows.values() {
        if occurrences.len() < 2 {
            continue;
        }
        for li in 0..occurrences.len() {
            for ri in li + 1..occurrences.len() {
                let left = &occurrences[li];
                let right = &occurrences[ri];
                if left.source_id == right.source_id && left.token_start == right.token_start {
                    continue;
                }
                let lh = &prepared[left.source_id].hashes;
                let rh = &prepared[right.source_id].hashes;
                let la = left.token_start;
                let ra = right.token_start;
                if la + min_tokens > lh.len() || ra + min_tokens > rh.len() {
                    continue;
                }
                if lh[la..la + min_tokens] != rh[ra..ra + min_tokens] {
                    continue;
                }
                let (sa, ta, sb, tb) =
                    if (left.source_id, left.token_start) <= (right.source_id, right.token_start) {
                        (
                            left.source_id,
                            left.token_start,
                            right.source_id,
                            right.token_start,
                        )
                    } else {
                        (
                            right.source_id,
                            right.token_start,
                            left.source_id,
                            left.token_start,
                        )
                    };
                candidates.push(Candidate {
                    source_a: sa,
                    source_b: sb,
                    token_a: ta,
                    token_b: tb,
                });
            }
        }
    }
    if candidates.is_empty() {
        return;
    }
    candidates.sort_unstable();
    candidates.dedup();

    // Build line-coverage from already-found primary clones.
    let mut coverage = LineCoverage::from_clones(prepared, clones);
    let mut open: Option<SecondaryOpen> = None;

    for candidate in candidates {
        if let Some(current) = open.as_mut()
            && current.is_continuation(&candidate)
        {
            current.grow(&candidate, prepared, min_tokens);
            continue;
        }

        flush_secondary_clone(
            open.take(),
            prepared,
            skip_local,
            min_lines,
            scan_roots,
            clones,
            &mut coverage,
        );

        // Create a new secondary clone candidate.
        let start_a = candidate.token_a;
        let end_a = start_a + min_tokens - 1;
        let start_b = candidate.token_b;
        let end_b = start_b + min_tokens - 1;

        let frag_a = match make_fragment(
            &prepared[candidate.source_a].id,
            &prepared[candidate.source_a].spans,
            start_a,
            end_a,
        ) {
            Some(f) => f,
            None => continue,
        };
        let frag_b = match make_fragment(
            &prepared[candidate.source_b].id,
            &prepared[candidate.source_b].spans,
            start_b,
            end_b,
        ) {
            Some(f) => f,
            None => continue,
        };

        open = Some(SecondaryOpen {
            clone: CpdClone {
                format: prepared[candidate.source_a].format.clone(),
                fragment_a: frag_a,
                fragment_b: frag_b,
                token_count: min_tokens as u32,
            },
            source_a: candidate.source_a,
            source_b: candidate.source_b,
            last_token_start_a: candidate.token_a,
            last_token_start_b: candidate.token_b,
        });
    }

    flush_secondary_clone(
        open.take(),
        prepared,
        skip_local,
        min_lines,
        scan_roots,
        clones,
        &mut coverage,
    );
}

fn flush_secondary_clone(
    open: Option<SecondaryOpen>,
    prepared: &[PreparedSource],
    skip_local: bool,
    min_lines: usize,
    scan_roots: &[PathBuf],
    clones: &mut Vec<CpdClone>,
    coverage: &mut LineCoverage,
) {
    let Some(oc) = open else {
        return;
    };

    let range_a = fragment_line_range(&oc.clone.fragment_a);
    let range_b = fragment_line_range(&oc.clone.fragment_b);

    // skip_local: drop clone pairs where both fragments are under the same scan root.
    if skip_local
        && should_skip_local(
            &prepared[oc.source_a].id,
            &prepared[oc.source_b].id,
            scan_roots,
        )
    {
        return;
    }

    // min_lines filter: only check fragment A, mirroring jscpd's LinesLengthCloneValidator.
    if min_lines > 0 {
        let lines = oc.clone.fragment_a.end.line as usize - oc.clone.fragment_a.start.line as usize;
        if lines < min_lines {
            return;
        }
    }

    // Line-coverage filter: skip secondary clones that don't extend existing coverage
    // on either side.  This prevents the report from filling up with dozens of
    // overlapping sub-clones of the same region.
    if !coverage.extends(oc.source_a, range_a) || !coverage.extends(oc.source_b, range_b) {
        return;
    }

    let before = clones.len();
    clones.push(oc.clone);

    // Insert coverage for newly added clone.
    if clones.len() > before {
        coverage.insert(oc.source_a, range_a);
        coverage.insert(oc.source_b, range_b);
    }
}

fn fragment_line_range(fragment: &Fragment) -> (usize, usize) {
    let start = fragment.start.line as usize;
    let end = fragment.end.line as usize;
    (start.min(end), start.max(end))
}

// ---------------------------------------------------------------------------
// Line coverage tracking for secondary clones
// ---------------------------------------------------------------------------

struct LineCoverage {
    ranges_by_source: Vec<Vec<(usize, usize)>>,
}

impl LineCoverage {
    fn from_clones(prepared: &[PreparedSource], clones: &[CpdClone]) -> Self {
        let mut source_lookup: FxHashMap<&str, usize> = FxHashMap::default();
        for (idx, source) in prepared.iter().enumerate() {
            source_lookup.insert(source.id.as_str(), idx);
        }
        let mut coverage = Self {
            ranges_by_source: vec![Vec::new(); prepared.len()],
        };
        for clone in clones {
            if let Some(idx) = source_lookup.get(clone.fragment_a.source_id.as_str()) {
                coverage.insert(*idx, fragment_line_range(&clone.fragment_a));
            }
            if let Some(idx) = source_lookup.get(clone.fragment_b.source_id.as_str()) {
                coverage.insert(*idx, fragment_line_range(&clone.fragment_b));
            }
        }
        coverage
    }

    fn extends(&self, source_idx: usize, range: (usize, usize)) -> bool {
        // ponytail: walk existing intervals in order, advancing the low watermark
        // past anything already covered. We extend unless the candidate is
        // already fully covered by an existing interval chain.
        let Some(intervals) = self.ranges_by_source.get(source_idx) else {
            return true;
        };
        let mut cursor = range.0;
        for &(start, end) in intervals {
            if end < cursor {
                continue;
            }
            if start > cursor {
                return true;
            }
            cursor = cursor.max(end.saturating_add(1));
            if cursor > range.1 {
                return false;
            }
        }
        cursor <= range.1
    }

    fn insert(&mut self, source_idx: usize, range: (usize, usize)) {
        // ponytail: merge-into-sorted approach. Keep the per-source vector
        // sorted and merged so `extends` can scan it in one pass; we rebuild
        // it by folding the new range into the existing merged intervals
        // rather than re-sorting the whole list every insert.
        let Some(intervals) = self.ranges_by_source.get_mut(source_idx) else {
            return;
        };
        let mut folded = Vec::with_capacity(intervals.len() + 1);
        let mut pending = Some(range);
        for &(start, end) in intervals.iter() {
            let p = match pending.take() {
                None => {
                    folded.push((start, end));
                    continue;
                }
                Some(p) => p,
            };
            // p is fully before this interval — emit p, then this interval.
            if p.1.saturating_add(1) < start {
                folded.push(p);
                folded.push((start, end));
            }
            // this interval is fully before p — emit it, keep p pending.
            else if end.saturating_add(1) < p.0 {
                folded.push((start, end));
                pending = Some(p);
            }
            // overlapping or adjacent — merge into p, keep pending.
            else {
                pending = Some((p.0.min(start), p.1.max(end)));
            }
        }
        if let Some(p) = pending {
            folded.push(p);
        }
        *intervals = folded;
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::models::{Location, Token, TokenKind};

    fn loc(line: u32, col: u32, offset: u32) -> Location {
        Location {
            line,
            column: col,
            offset,
        }
    }

    fn make_token(kind: TokenKind, value: &str, line: u32, col: u32, offset: u32) -> Token {
        let end_col = col + value.len() as u32;
        let end_off = offset + value.len() as u32;
        Token {
            kind,
            value: value.to_string(),
            start: loc(line, col, offset),
            end: loc(line, end_col, end_off),
        }
    }

    fn make_file(id: &str, format: &str, tokens: Vec<Token>) -> SourceFile {
        SourceFile {
            id: id.to_string(),
            format: format.to_string(),
            tokens,
        }
    }

    fn js_tokens_ab() -> Vec<Token> {
        vec![
            make_token(TokenKind::Keyword, "function", 1, 0, 0),
            make_token(TokenKind::Other, "hello", 1, 9, 9),
            make_token(TokenKind::Operator, "(", 1, 14, 14),
            make_token(TokenKind::Operator, ")", 1, 15, 15),
            make_token(TokenKind::Operator, "{", 1, 16, 16),
            make_token(TokenKind::Keyword, "return", 2, 0, 18),
            make_token(TokenKind::Literal, "42", 2, 7, 25),
            make_token(TokenKind::Operator, ";", 2, 9, 27),
            make_token(TokenKind::Operator, "}", 3, 0, 29),
        ]
    }

    #[test]
    fn empty_input_returns_empty() {
        let result = detect(&[], 10);
        assert!(result.is_empty());
    }

    fn pair_with_js_tokens(min_tokens: usize) -> Vec<CpdClone> {
        let tokens = js_tokens_ab();
        let file_a = make_file("a.js", "javascript", tokens.clone());
        let file_b = make_file("b.js", "javascript", tokens);
        detect(&[file_a, file_b], min_tokens)
    }

    #[test]
    fn identical_files_detected_as_clone() {
        assert!(
            !pair_with_js_tokens(5).is_empty(),
            "identical files must produce at least one clone"
        );
    }

    #[test]
    fn min_tokens_threshold_respected() {
        assert!(
            pair_with_js_tokens(100).is_empty(),
            "no clones when min_tokens exceeds file length"
        );
    }

    #[test]
    fn deduplication_ab_ba_collapse() {
        assert_eq!(
            pair_with_js_tokens(5).len(),
            1,
            "symmetric pairs must collapse to 1"
        );
    }

    #[test]
    fn different_formats_not_cross_detected() {
        let tokens = js_tokens_ab();
        let file_js = make_file("a.js", "javascript", tokens.clone());
        let file_py = make_file("a.py", "python", tokens);
        let clones = detect(&[file_js, file_py], 5);
        assert!(
            clones.is_empty(),
            "tokens from different formats must not match"
        );
    }

    #[test]
    fn cross_format_group_detected() {
        // Inverse of different_formats_not_cross_detected: when two formats
        // are pooled into ONE prepared group (--cross-formats), identical
        // token streams match across formats.
        let to_prepared = |id: &str, format: &str| {
            let tokens = js_tokens_ab();
            let mut hashes = Vec::new();
            let mut spans = Vec::new();
            for t in &tokens {
                hashes.push(token_hash(t.kind.discriminant(), &t.value));
                spans.push((t.start.clone(), t.end.clone()));
            }
            PreparedSource {
                id: id.to_string(),
                format: format.to_string(),
                hashes,
                spans,
            }
        };
        let group = vec![
            to_prepared("a.js", "javascript"),
            to_prepared("a.ts", "typescript"),
        ];
        let clones = detect_prepared(vec![group], 5, false, 0, &[]);
        assert_eq!(
            clones.len(),
            1,
            "identical token streams in one pool must match across formats"
        );
    }

    #[test]
    fn identical_files_maximal_clone() {
        // With the open_clone state machine, a single maximal clone is emitted
        // instead of multiple sliding-window sub-clones.
        let tokens = js_tokens_ab();
        let file_a = make_file("a.js", "javascript", tokens.clone());
        let file_b = make_file("b.js", "javascript", tokens);
        let clones = detect(&[file_a, file_b], 5);
        assert_eq!(
            clones.len(),
            1,
            "open_clone SM must produce one maximal clone"
        );
        assert_eq!(
            clones[0].token_count, 9,
            "maximal clone must cover all 9 tokens"
        );
    }

    #[test]
    fn three_identical_files_secondary_pass_adds_missing_pair() {
        let tokens = js_tokens_ab();
        let file_a = make_file("a.js", "javascript", tokens.clone());
        let file_b = make_file("b.js", "javascript", tokens.clone());
        let file_c = make_file("c.js", "javascript", tokens);
        let clones = detect(&[file_a, file_b, file_c], 5);
        assert!(
            clones.len() >= 2,
            "three identical files must yield at least 2 clone pairs, got {}",
            clones.len()
        );
    }

    #[test]
    fn clones_sorted_by_source_and_line() {
        let tokens = js_tokens_ab();
        let file_a = make_file("a.js", "javascript", tokens.clone());
        let file_b = make_file("b.js", "javascript", tokens);
        let clones = detect(&[file_a, file_b], 5);
        for i in 1..clones.len() {
            let prev = &clones[i - 1];
            let curr = &clones[i];
            assert!(
                (
                    &prev.fragment_a.source_id,
                    prev.fragment_a.start.line,
                    &prev.fragment_b.source_id,
                    prev.fragment_b.start.line,
                ) <= (
                    &curr.fragment_a.source_id,
                    curr.fragment_a.start.line,
                    &curr.fragment_b.source_id,
                    curr.fragment_b.start.line,
                ),
                "clones must be sorted"
            );
        }
    }
}