//! A path's history over main: the versions that changed it, and the
//! version that last changed each line of a file (blame). Hosts work these
//! out where the versions are, so a workspace never needs old versions.

use std::collections::HashMap;

use crate::tree::{self, Entry, EntryKind};
use crate::{Id, Result, Source, diff};

/// What `entries` found: the path's entry in every tree, or the trees it
/// needs first (all of one level at once, so a host loads them together).
pub enum Found {
    All(Vec<Option<Entry>>),
    Need(Vec<Id>),
}

/// The entry at `path` in each of `trees` (None: not there), reading only
/// the folders on the path.
pub fn entries(src: &dyn Source, trees: &[Id], path: &str) -> Result<Found> {
    let mut at: Vec<Option<Entry>> = trees.iter().map(|t| Some(Entry { kind: EntryKind::Tree, id: *t })).collect();
    for part in path.split('/').filter(|p| !p.is_empty()) {
        let mut need: Vec<Id> = Vec::new();
        for e in at.iter().flatten() {
            if e.kind == EntryKind::Tree && src.get(&e.id)?.is_none() {
                need.push(e.id);
            }
        }
        if !need.is_empty() {
            need.sort();
            need.dedup();
            return Ok(Found::Need(need));
        }
        // Versions share most folders: each is read once.
        let mut seen: HashMap<Id, Option<Entry>> = HashMap::new();
        for slot in at.iter_mut() {
            let next = match *slot {
                Some(e) if e.kind == EntryKind::Tree => match seen.get(&e.id) {
                    Some(found) => *found,
                    None => {
                        let found = tree::read(src, &e.id)?.into_iter().find(|x| x.name == part).map(|x| Entry { kind: x.kind, id: x.id });
                        seen.insert(e.id, found);
                        found
                    }
                },
                _ => None,
            };
            *slot = next;
        }
    }
    Ok(Found::All(at))
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Kind {
    Added,
    Modified,
    Removed,
}

/// The versions that changed the path, newest first, from its entry in
/// each version (`versions` newest first). The oldest version given counts
/// as a change only when it's version 1 (`from_start`): otherwise what came
/// before it isn't known.
pub fn changes(versions: &[u64], entries: &[Option<Entry>], from_start: bool) -> Vec<(u64, Kind, Option<Entry>)> {
    let mut out = Vec::new();
    for (i, (n, after)) in versions.iter().zip(entries).enumerate() {
        let before = match entries.get(i + 1) {
            Some(b) => *b,
            None if from_start => None,
            None => break,
        };
        let kind = match (before, after) {
            (None, Some(_)) => Kind::Added,
            (Some(_), None) => Kind::Removed,
            (Some(b), Some(a)) if b != *a => Kind::Modified,
            _ => continue,
        };
        out.push((*n, kind, *after));
    }
    out
}

/// What `touched` found: for each pair, the paths it changes (None: more
/// than the most asked for), or the folders it needs first.
pub enum Touched {
    All(Vec<Option<Vec<String>>>),
    Need(Vec<Id>),
}

/// The paths each (before, after) pair of trees changes: files and links
/// that differ, and folders added or removed whole as just the folder.
/// Hosts keep this with each version, so a path's history reads only the
/// versions that touched it (git's changed-path filters do the same).
/// Works a level at a time across all pairs, naming every folder a level
/// needs at once.
pub fn touched(src: &dyn Source, pairs: &[(Option<Id>, Id)], most: usize) -> Result<Touched> {
    let mut out: Vec<Option<Vec<String>>> = vec![Some(Vec::new()); pairs.len()];
    let mut level: Vec<(usize, String, Option<Id>, Option<Id>)> =
        pairs.iter().enumerate().filter(|(_, (a, b))| a.as_ref() != Some(b)).map(|(i, (a, b))| (i, String::new(), *a, Some(*b))).collect();
    while !level.is_empty() {
        let mut need: Vec<Id> = Vec::new();
        for (_, _, a, b) in &level {
            for t in [a, b].into_iter().flatten() {
                if src.get(t)?.is_none() {
                    need.push(*t);
                }
            }
        }
        if !need.is_empty() {
            need.sort();
            need.dedup();
            return Ok(Touched::Need(need));
        }
        let mut next = Vec::new();
        for (i, prefix, a, b) in level {
            let Some(paths) = &mut out[i] else { continue };
            let read = |t: Option<Id>| -> Result<Vec<tree::TreeEntry>> { t.map(|t| tree::read(src, &t)).unwrap_or(Ok(Vec::new())) };
            let (ea, eb) = (read(a)?, read(b)?);
            let path = |name: &str| if prefix.is_empty() { name.to_string() } else { format!("{prefix}/{name}") };
            // Both are sorted by name.
            let (mut x, mut y) = (0, 0);
            while x < ea.len() || y < eb.len() {
                let order = match (ea.get(x), eb.get(y)) {
                    (Some(l), Some(r)) => l.name.as_bytes().cmp(r.name.as_bytes()),
                    (Some(_), None) => std::cmp::Ordering::Less,
                    _ => std::cmp::Ordering::Greater,
                };
                match order {
                    std::cmp::Ordering::Less => {
                        paths.push(path(&ea[x].name));
                        x += 1;
                    }
                    std::cmp::Ordering::Greater => {
                        paths.push(path(&eb[y].name));
                        y += 1;
                    }
                    std::cmp::Ordering::Equal => {
                        let (l, r) = (&ea[x], &eb[y]);
                        if l.kind == EntryKind::Tree && r.kind == EntryKind::Tree && l.id != r.id {
                            next.push((i, path(&l.name), Some(l.id), Some(r.id)));
                        } else if l.kind != r.kind || l.id != r.id {
                            paths.push(path(&l.name));
                        }
                        x += 1;
                        y += 1;
                    }
                }
            }
            if paths.len() > most {
                out[i] = None;
            }
        }
        level = next.into_iter().filter(|(i, ..)| out[*i].is_some()).collect();
    }
    Ok(Touched::All(out))
}

/// Whether a version whose changed paths are `touched` (from [`touched`])
/// may have changed `path`: a path it lists is the path, under it, or a
/// folder holding it.
pub fn may_touch(touched: &[String], path: &str) -> bool {
    let under = |p: &str, folder: &str| folder.is_empty() || p == folder || (p.starts_with(folder) && p.as_bytes().get(folder.len()) == Some(&b'/'));
    touched.iter().any(|t| under(t, path) || under(path, t))
}

/// Which version last changed each line of a file. `points` are the
/// versions that changed it, newest first, with the file's content after
/// each (empty where it was removed); the last is where it began (or the
/// oldest known). Answers a version per line of the newest content.
pub fn blame(points: &[(u64, &[u8])]) -> Vec<u64> {
    let Some((_, newest)) = points.first() else { return Vec::new() };
    let count = diff::lines(newest).len();
    let mut owner = vec![points.last().map(|p| p.0).unwrap_or(0); count];
    // Where each of the newest lines is in the version being looked at.
    let mut track: Vec<Option<u32>> = (0..count as u32).map(Some).collect();
    for (k, (n, cur)) in points.iter().enumerate() {
        let Some((_, prev)) = points.get(k + 1) else { break };
        // Lines the version didn't touch map to the version before it.
        let mut map: Vec<Option<u32>> = vec![None; diff::lines(cur).len()];
        let (mut old, mut new) = (0u32, 0u32);
        for h in diff::hunks(prev, cur) {
            while new < h.after.start {
                map[new as usize] = Some(old);
                new += 1;
                old += 1;
            }
            new = h.after.end;
            old = h.before.end;
        }
        while (new as usize) < map.len() {
            map[new as usize] = Some(old);
            new += 1;
            old += 1;
        }
        let mut left = false;
        for (line, t) in track.iter_mut().enumerate() {
            if let Some(at) = *t {
                match map.get(at as usize).copied().flatten() {
                    Some(before) => {
                        *t = Some(before);
                        left = true;
                    }
                    None => {
                        owner[line] = *n;
                        *t = None;
                    }
                }
            }
        }
        if !left {
            break;
        }
    }
    owner
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tree::Files;
    use crate::{MemSource, Object};

    fn version(src: &mut MemSource, files: &[(&str, &str)]) -> Id {
        let f: Files = files.iter().map(|(p, c)| (p.to_string(), Entry { kind: EntryKind::File, id: src.put(Object::blob(c.as_bytes().to_vec())) })).collect();
        let (root, objects) = tree::build(&f);
        for o in objects {
            src.put(o);
        }
        root
    }

    #[test]
    fn history_of_a_file_and_a_folder() {
        let mut src = MemSource::default();
        // Newest first: 4 removes it, 3 changes it, 2 leaves it, 1 adds it.
        let trees = [
            version(&mut src, &[("other.txt", "o2")]),
            version(&mut src, &[("src/a.txt", "a2"), ("other.txt", "o2")]),
            version(&mut src, &[("src/a.txt", "a1"), ("other.txt", "o2")]),
            version(&mut src, &[("src/a.txt", "a1"), ("other.txt", "o1")]),
        ];
        let Found::All(found) = entries(&src, &trees, "src/a.txt").unwrap() else { panic!("all here") };
        let got: Vec<(u64, Kind)> = changes(&[4, 3, 2, 1], &found, true).into_iter().map(|(n, k, _)| (n, k)).collect();
        assert_eq!(got, vec![(4, Kind::Removed), (3, Kind::Modified), (1, Kind::Added)]);
        // Without version 1, its start isn't known.
        assert_eq!(changes(&[4, 3, 2], &found[..3], false).len(), 2);
        let Found::All(dir) = entries(&src, &trees, "src").unwrap() else { panic!() };
        assert_eq!(changes(&[4, 3, 2, 1], &dir, true).len(), 3);

        // Missing folders are named a level at a time.
        let empty = MemSource::default();
        let Found::Need(need) = entries(&empty, &trees, "src/a.txt").unwrap() else { panic!("needs the roots") };
        assert_eq!(need.len(), 4);
    }

    #[test]
    fn touched_paths() {
        let mut src = MemSource::default();
        let v1 = version(&mut src, &[("README.md", "r"), ("src/a.txt", "a1"), ("src/deep/b.txt", "b")]);
        let v2 = version(&mut src, &[("README.md", "r"), ("src/a.txt", "a2"), ("src/deep/b.txt", "b"), ("docs/x.md", "x")]);
        let v3 = version(&mut src, &[("README.md", "r2"), ("src/a.txt", "a2"), ("docs/x.md", "x")]);
        let Touched::All(got) = touched(&src, &[(None, v1), (Some(v1), v2), (Some(v2), v3), (Some(v3), v3)], 100).unwrap() else { panic!("all here") };
        let sorted = |p: &Option<Vec<String>>| {
            let mut p = p.clone().unwrap();
            p.sort();
            p
        };
        // A new or removed folder is named, not what's in it.
        assert_eq!(sorted(&got[0]), vec!["README.md", "src"]);
        assert_eq!(sorted(&got[1]), vec!["docs", "src/a.txt"]);
        assert_eq!(sorted(&got[2]), vec!["README.md", "src/deep"]);
        assert!(sorted(&got[3]).is_empty());
        // Past the most asked for, it's not listed.
        let Touched::All(few) = touched(&src, &[(Some(v1), v2)], 1).unwrap() else { panic!() };
        assert!(few[0].is_none());

        let list = |p: &[&str]| p.iter().map(|s| s.to_string()).collect::<Vec<_>>();
        assert!(may_touch(&list(&["src"]), "src/deep/b.txt"));
        assert!(may_touch(&list(&["src/a.txt"]), "src"));
        assert!(may_touch(&list(&["src/a.txt"]), ""));
        assert!(!may_touch(&list(&["src/a.txt"]), "src/a"));
        assert!(!may_touch(&list(&["srcs/a.txt", "sr"]), "src"));

        let empty = MemSource::default();
        let Touched::Need(need) = touched(&empty, &[(Some(v1), v2)], 100).unwrap() else { panic!("needs the roots") };
        assert_eq!(need.len(), 2);
    }

    #[test]
    fn blame_follows_lines_back() {
        let v1 = "one\ntwo\nthree\n";
        let v2 = "one\nTWO\nthree\n";
        let v3 = "zero\none\nTWO\nthree\nfour\n";
        let owners = blame(&[(30, v3.as_bytes()), (20, v2.as_bytes()), (10, v1.as_bytes())]);
        assert_eq!(owners, vec![30, 10, 20, 10, 30]);
        assert_eq!(blame(&[(5, b"a\nb\n")]), vec![5, 5]);
        assert!(blame(&[]).is_empty());
    }
}