Function find_unique_matches

atomic-core/src/diff/patience.rs:165–218

Find lines that appear exactly once in both sequences and match. Returns a list of matches sorted by position in the old sequence.

(old: &[Line<'a>], new: &[Line<'a>])

///
/// Returns a list of matches sorted by position in the old sequence.
fn find_unique_matches<'a>(old: &[Line<'a>], new: &[Line<'a>]) -> Vec<UniqueMatch> {
    // Count occurrences in old sequence
    let mut old_counts: HashMap<u64, (usize, usize)> = HashMap::new(); // hash -> (count, index)
    for (idx, line) in old.iter().enumerate() {
        let hash = line.hash_value();
        old_counts
            .entry(hash)
            .and_modify(|(count, _)| *count += 1)
            .or_insert((1, idx));
    }

    // Count occurrences in new sequence and find matches
    let mut new_counts: HashMap<u64, (usize, usize)> = HashMap::new();
    for (idx, line) in new.iter().enumerate() {
        let hash = line.hash_value();
        new_counts
            .entry(hash)
            .and_modify(|(count, _)| *count += 1)
            .or_insert((1, idx));
    }

    // Find lines that are unique in both and actually match
    let mut matches = Vec::new();
    for (idx, line) in old.iter().enumerate() {
        let hash = line.hash_value();

        // Check if unique in old
        if let Some(&(old_count, _)) = old_counts.get(&hash) {
            if old_count != 1 {
                continue;
            }
        }

        // Check if unique in new and find the index
        if let Some(&(new_count, new_idx)) = new_counts.get(&hash) {
            if new_count != 1 {
                continue;
            }

            // Verify actual equality (not just hash match)
            if old[idx] == new[new_idx] {
                matches.push(UniqueMatch {
                    old_idx: idx,
                    new_idx,
                });
            }
        }
    }

    // Sort by old_idx (should already be sorted, but ensure it)
    matches.sort_by_key(|m| m.old_idx);

    matches
}

/// Find the Longest Increasing Subsequence of matches by new_idx.
///