//! Renames: files that moved between two trees, found by their content, as
//! git finds them. A removed path and an added one are the same file when
//! the content is identical, or (for text) when at least half the lines are
//! the same. Merges use them so an edit follows a file to its new name, and
//! history follows a file back through them.

use std::collections::{BTreeMap, HashMap};

use crate::object::{Kind, Object};
use crate::tree::{self, Change, Entry, EntryKind, TreeEntry};
use crate::{Id, Result, Source, chunk, diff};

/// How alike two files must be (shared lines over all lines) to be one file that moved.
const SIMILAR: f64 = 0.5;
/// Similar-content pairs compared at most; past this only identical content counts.
const MOST_PAIRS: usize = 2500;
/// Files bigger than this only count when identical.
const MOST_BYTES: u64 = 512 * 1024;

/// The renames in `changes` (from `tree::diff_trees`): (from, to) pairs.
pub fn renames(src: &dyn Source, changes: &BTreeMap<String, Change>) -> Result<Vec<(String, String)>> {
    let file = |e: &Entry| e.kind != EntryKind::Tree && e.kind != EntryKind::Gitlink;
    let removed: Vec<(&String, &Entry)> = changes.iter().filter_map(|(p, c)| if let Change::Removed(e) = c { file(e).then_some((p, e)) } else { None }).collect();
    let added: Vec<(&String, &Entry)> = changes.iter().filter_map(|(p, c)| if let Change::Added(e) = c { file(e).then_some((p, e)) } else { None }).collect();
    if removed.is_empty() || added.is_empty() {
        return Ok(Vec::new());
    }
    let mut out = Vec::new();
    let mut used_from = vec![false; removed.len()];
    let mut used_to = vec![false; added.len()];
    // Identical content first.
    let mut by_id: HashMap<Id, Vec<usize>> = HashMap::new();
    for (i, (_, e)) in removed.iter().enumerate() {
        by_id.entry(e.id).or_default().push(i);
    }
    for (j, (to, e)) in added.iter().enumerate() {
        if let Some(i) = by_id.get_mut(&e.id).and_then(|v| (!v.is_empty()).then(|| v.remove(0))) {
            used_from[i] = true;
            used_to[j] = true;
            out.push((removed[i].0.clone(), (*to).clone()));
        }
    }
    // Then similar text, best pairs first.
    let from_left: Vec<usize> = (0..removed.len()).filter(|i| !used_from[*i]).collect();
    let to_left: Vec<usize> = (0..added.len()).filter(|j| !used_to[*j]).collect();
    if from_left.is_empty() || to_left.is_empty() || from_left.len() * to_left.len() > MOST_PAIRS {
        return Ok(out);
    }
    let lines_of = |id: &Id| -> Result<Option<HashMap<Vec<u8>, usize>>> {
        let Some(o) = src.get(id)? else { return Ok(None) };
        if o.kind == Kind::Chunks && chunk::file_size(src, id)? > MOST_BYTES {
            return Ok(None);
        }
        let data = chunk::read_file(src, id)?;
        if data.len() as u64 > MOST_BYTES || diff::is_binary(&data) {
            return Ok(None);
        }
        let mut counts: HashMap<Vec<u8>, usize> = HashMap::new();
        for line in diff::lines(&data) {
            *counts.entry(line.to_vec()).or_default() += 1;
        }
        Ok(Some(counts))
    };
    let froms: Vec<Option<HashMap<Vec<u8>, usize>>> = from_left.iter().map(|i| lines_of(&removed[*i].1.id)).collect::<Result<_>>()?;
    let tos: Vec<Option<HashMap<Vec<u8>, usize>>> = to_left.iter().map(|j| lines_of(&added[*j].1.id)).collect::<Result<_>>()?;
    let mut scored: Vec<(f64, usize, usize)> = Vec::new();
    for (a, fa) in froms.iter().enumerate() {
        let Some(fa) = fa else { continue };
        let total_a: usize = fa.values().sum();
        for (b, tb) in tos.iter().enumerate() {
            let Some(tb) = tb else { continue };
            let total_b: usize = tb.values().sum();
            if total_a + total_b == 0 {
                continue;
            }
            let common: usize = fa.iter().map(|(line, n)| (*n).min(*tb.get(line).unwrap_or(&0))).sum();
            let score = 2.0 * common as f64 / (total_a + total_b) as f64;
            if score >= SIMILAR {
                scored.push((score, a, b));
            }
        }
    }
    scored.sort_by(|x, y| y.0.total_cmp(&x.0).then(x.1.cmp(&y.1)).then(x.2.cmp(&y.2)));
    let (mut taken_a, mut taken_b) = (vec![false; froms.len()], vec![false; tos.len()]);
    for (_, a, b) in scored {
        if taken_a[a] || taken_b[b] {
            continue;
        }
        taken_a[a] = true;
        taken_b[b] = true;
        out.push((removed[from_left[a]].0.clone(), added[to_left[b]].0.clone()));
    }
    out.sort();
    Ok(out)
}

/// Where `path` in `new` came from, when it's a file that moved there from `old`.
pub fn renamed_from(src: &dyn Source, old: &Id, new: &Id, path: &str) -> Result<Option<String>> {
    let changes = tree::diff_trees(src, old, new)?;
    if !matches!(changes.get(path), Some(Change::Added(_))) {
        return Ok(None);
    }
    Ok(renames(src, &changes)?.into_iter().find(|(_, to)| to == path).map(|(from, _)| from))
}

/// `tree` with `from` gone and `entry` at `to` (a file moved), and the new trees.
pub fn moved(src: &dyn Source, tree: &Id, from: &str, to: &str, entry: Entry) -> Result<(Id, Vec<Object>)> {
    let mut objects = Vec::new();
    let without = set(src, Some(tree), from, None, &mut objects)?.unwrap_or_else(tree::empty_id);
    let id = set(src, Some(&without), to, Some(entry), &mut objects)?.unwrap_or_else(tree::empty_id);
    Ok((id, objects))
}

/// `tree` with `path` set to `entry` (None: removed); None when that leaves it empty.
fn set(src: &dyn Source, tree: Option<&Id>, path: &str, entry: Option<Entry>, objects: &mut Vec<Object>) -> Result<Option<Id>> {
    let read = |id: &Id, objects: &[Object]| -> Result<Vec<TreeEntry>> {
        match objects.iter().find(|o| o.id() == *id) {
            Some(o) => tree::decode(&o.data),
            None => tree::read(src, id),
        }
    };
    let mut entries = match tree {
        Some(t) => read(t, objects)?,
        None => Vec::new(),
    };
    let (head, rest) = match path.split_once('/') {
        Some((h, r)) => (h, Some(r)),
        None => (path, None),
    };
    let at = entries.iter().position(|e| e.name == head);
    let next = match rest {
        None => entry,
        Some(rest) => {
            let inner = at.and_then(|i| (entries[i].kind == EntryKind::Tree).then_some(entries[i].id));
            set(src, inner.as_ref(), rest, entry, objects)?.map(|id| Entry { kind: EntryKind::Tree, id })
        }
    };
    match (at, next) {
        (Some(i), Some(e)) => entries[i] = TreeEntry { name: head.to_string(), kind: e.kind, id: e.id },
        (Some(i), None) => {
            entries.remove(i);
        }
        (None, Some(e)) => entries.push(TreeEntry { name: head.to_string(), kind: e.kind, id: e.id }),
        (None, None) => {}
    }
    if entries.is_empty() {
        return Ok(None);
    }
    entries.sort_by(|a, b| a.name.cmp(&b.name));
    let object = Object::new(Kind::Tree, tree::encode(&entries));
    let id = object.id();
    objects.push(object);
    Ok(Some(id))
}

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

    fn files(src: &mut MemSource, list: &[(&str, &str)]) -> Id {
        let mut map = tree::Files::new();
        for (path, content) in list {
            let objects = chunk::file_objects(content.as_bytes());
            let id = objects[0].id();
            for o in objects {
                src.put(o);
            }
            map.insert(path.to_string(), Entry { kind: EntryKind::File, id });
        }
        let (id, objects) = tree::build(&map);
        for o in objects {
            src.put(o);
        }
        id
    }

    #[test]
    fn finds_moves() {
        let mut src = MemSource::default();
        let text: String = (0..40).map(|i| format!("line {i}\n")).collect();
        let edited = text.replace("line 3\n", "line three\n");
        let a = files(&mut src, &[("src/old.rs", &text), ("same.txt", "same\n"), ("gone.txt", "bye\n")]);
        let b = files(&mut src, &[("src/new.rs", &edited), ("lib/same.txt", "same\n"), ("other.txt", "unrelated\nstuff\n")]);
        let changes = tree::diff_trees(&src, &a, &b).unwrap();
        let found = renames(&src, &changes).unwrap();
        assert_eq!(found, vec![("same.txt".to_string(), "lib/same.txt".to_string()), ("src/old.rs".to_string(), "src/new.rs".to_string())]);
        assert_eq!(renamed_from(&src, &a, &b, "src/new.rs").unwrap().as_deref(), Some("src/old.rs"));
        assert_eq!(renamed_from(&src, &a, &b, "other.txt").unwrap(), None);
    }

    #[test]
    fn moves_entries() {
        let mut src = MemSource::default();
        let a = files(&mut src, &[("a/x.txt", "x\n"), ("b.txt", "b\n")]);
        let x = tree::lookup(&src, &a, "a/x.txt").unwrap().unwrap();
        let (moved_tree, objects) = moved(&src, &a, "a/x.txt", "c/d/x.txt", x).unwrap();
        for o in objects {
            src.put(o);
        }
        let flat = tree::flatten(&src, &moved_tree).unwrap();
        assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["b.txt".to_string(), "c/d/x.txt".to_string()]);
    }
}