//! The two trees `wai breaking` compares, read through `git`: the base (a commit) and the
//! working tree (what is on disk, committed or not, untracked files included).

use super::super::envelope::{EXIT_INTERNAL, EXIT_NOT_FOUND, OpError};
use std::collections::BTreeMap;
use std::io::{Read, Write};
use std::path::{Path, PathBuf};
use std::process::{Command, Stdio};

/// A checkout: its top-level directory.
pub struct Repo {
    pub root: PathBuf,
}

/// How a path differs between the base and the working tree.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Status {
    Added,
    Modified,
    Removed,
}

fn internal(e: impl std::fmt::Display) -> OpError {
    OpError::new(EXIT_INTERNAL, "git-failed", e.to_string(), "run it in a git checkout with git on PATH")
}

impl Repo {
    /// The checkout holding `dir`.
    pub fn open(dir: &Path) -> Result<Repo, OpError> {
        let out = Command::new("git").arg("-C").arg(dir).args(["rev-parse", "--show-toplevel"]).output().map_err(|e| {
            OpError::new(EXIT_NOT_FOUND, "git-not-found", format!("git: {e}"), "install git; `wai breaking` reads both trees through it")
        })?;
        if !out.status.success() {
            return Err(OpError::new(
                EXIT_NOT_FOUND,
                "not-a-checkout",
                format!("{}: not in a git checkout", dir.display()),
                "run it inside the repository, or pass --root <checkout>",
            ));
        }
        let root = String::from_utf8_lossy(&out.stdout).trim().to_string();
        Ok(Repo { root: PathBuf::from(root) })
    }

    fn git(&self, args: &[&str]) -> Result<Vec<u8>, OpError> {
        let out = Command::new("git").arg("-C").arg(&self.root).args(args).output().map_err(internal)?;
        if !out.status.success() {
            return Err(internal(format!("git {}: {}", args.join(" "), String::from_utf8_lossy(&out.stderr).trim())));
        }
        Ok(out.stdout)
    }

    /// The commit `rev` names, or `None` when it names none.
    pub fn commit(&self, rev: &str) -> Option<String> {
        let out = Command::new("git").arg("-C").arg(&self.root).args(["rev-parse", "--verify", "--quiet", &format!("{rev}^{{commit}}")]).output().ok()?;
        out.status.success().then(|| String::from_utf8_lossy(&out.stdout).trim().to_string())
    }

    /// The best common ancestor of two commits.
    pub fn merge_base(&self, a: &str, b: &str) -> Option<String> {
        let out = Command::new("git").arg("-C").arg(&self.root).args(["merge-base", a, b]).output().ok()?;
        out.status.success().then(|| String::from_utf8_lossy(&out.stdout).trim().to_string())
    }

    /// Every path under `pathspecs` that differs between `base` and the working tree.
    pub fn changed(&self, base: &str, pathspecs: &[&str]) -> Result<Vec<(Status, String)>, OpError> {
        let mut args = vec!["diff", "--name-status", "--no-renames", "-z", base, "--"];
        args.extend_from_slice(pathspecs);
        let out = self.git(&args)?;
        let mut v = Vec::new();
        let mut it = out.split(|b| *b == 0).filter(|s| !s.is_empty());
        while let (Some(st), Some(p)) = (it.next(), it.next()) {
            let s = match st.first() {
                Some(b'A') => Status::Added,
                Some(b'D') => Status::Removed,
                _ => Status::Modified,
            };
            v.push((s, String::from_utf8_lossy(p).into_owned()));
        }
        let mut args = vec!["ls-files", "--others", "--exclude-standard", "-z", "--"];
        args.extend_from_slice(pathspecs);
        for p in self.git(&args)?.split(|b| *b == 0).filter(|s| !s.is_empty()) {
            v.push((Status::Added, String::from_utf8_lossy(p).into_owned()));
        }
        v.sort_by(|a, b| a.1.cmp(&b.1));
        v.dedup_by(|a, b| a.1 == b.1);
        Ok(v)
    }

    /// The paths under `pathspecs` in `base`. (`git ls-tree` takes no pathspec magic, so
    /// the listing is filtered here, by [`matches`].)
    pub fn ls_base(&self, base: &str, pathspecs: &[&str]) -> Result<Vec<String>, OpError> {
        let all = split0(&self.git(&["ls-tree", "-r", "--name-only", "-z", base])?);
        Ok(all.into_iter().filter(|p| matches(pathspecs, p)).collect())
    }

    /// The paths under `pathspecs` in the working tree: tracked files still on disk, and
    /// untracked files that are not ignored.
    pub fn ls_head(&self, pathspecs: &[&str]) -> Result<Vec<String>, OpError> {
        let mut args = vec!["ls-files", "--cached", "--others", "--exclude-standard", "-z", "--"];
        args.extend_from_slice(pathspecs);
        let mut v: Vec<String> = split0(&self.git(&args)?).into_iter().filter(|p| self.root.join(p).is_file()).collect();
        v.sort();
        v.dedup();
        Ok(v)
    }

    /// The files under `pathspecs` with a line matching the extended regular expression
    /// `re`: in `base` when it is given, else in the working tree (untracked files too).
    pub fn grep_files(&self, base: Option<&str>, re: &str, pathspecs: &[&str]) -> Result<Vec<String>, OpError> {
        let mut args = vec!["grep", "-l", "-I", "-z", "-E", "-e", re];
        match base {
            Some(b) => args.push(b),
            None => args.push("--untracked"),
        }
        args.push("--");
        args.extend_from_slice(pathspecs);
        let out = Command::new("git").arg("-C").arg(&self.root).args(&args).output().map_err(internal)?;
        // git grep exits 1 when nothing matched.
        if !out.status.success() && out.status.code() != Some(1) {
            return Err(internal(format!("git grep: {}", String::from_utf8_lossy(&out.stderr).trim())));
        }
        let prefix = base.map(|b| format!("{b}:")).unwrap_or_default();
        Ok(split0(&out.stdout).into_iter().map(|p| p.strip_prefix(&prefix).map(String::from).unwrap_or(p)).collect())
    }

    /// A file of the working tree, or `None` when it is not there.
    pub fn head_file(&self, path: &str) -> Option<Vec<u8>> {
        std::fs::read(self.root.join(path)).ok()
    }

    /// Files of `base`, read in one `git cat-file --batch`: each path's bytes, or no entry
    /// when `base` does not hold it.
    pub fn base_files(&self, base: &str, paths: &[String]) -> Result<BTreeMap<String, Vec<u8>>, OpError> {
        let mut out = BTreeMap::new();
        if paths.is_empty() {
            return Ok(out);
        }
        let mut child = Command::new("git")
            .arg("-C")
            .arg(&self.root)
            .args(["cat-file", "--batch"])
            .stdin(Stdio::piped())
            .stdout(Stdio::piped())
            .stderr(Stdio::null())
            .spawn()
            .map_err(internal)?;
        let mut stdin = child.stdin.take().ok_or_else(|| internal("git cat-file: no stdin"))?;
        let req: String = paths.iter().map(|p| format!("{base}:{p}\n")).collect();
        let writer = std::thread::spawn(move || {
            let _ = stdin.write_all(req.as_bytes());
        });
        let mut all = Vec::new();
        child.stdout.take().ok_or_else(|| internal("git cat-file: no stdout"))?.read_to_end(&mut all).map_err(internal)?;
        let _ = writer.join();
        let _ = child.wait();
        let mut rest: &[u8] = &all;
        for p in paths {
            let nl = rest.iter().position(|b| *b == b'\n').ok_or_else(|| internal("git cat-file: short answer"))?;
            let header = String::from_utf8_lossy(&rest[..nl]).into_owned();
            rest = &rest[nl + 1..];
            if header.ends_with(" missing") || header.ends_with(" ambiguous") {
                continue;
            }
            let size: usize = header.rsplit(' ').next().and_then(|s| s.parse().ok()).ok_or_else(|| internal(format!("git cat-file: {header}")))?;
            if rest.len() < size + 1 {
                return Err(internal("git cat-file: short object"));
            }
            if header.split(' ').nth(1) == Some("blob") {
                out.insert(p.clone(), rest[..size].to_vec());
            }
            rest = &rest[size + 1..];
        }
        Ok(out)
    }

    /// One file of `base`.
    pub fn base_file(&self, base: &str, path: &str) -> Result<Option<Vec<u8>>, OpError> {
        Ok(self.base_files(base, &[path.to_string()])?.remove(path))
    }

    /// `base`'s tree under `path`, written below `dest` at the same relative paths.
    pub fn extract(&self, base: &str, path: &str, dest: &Path) -> Result<(), OpError> {
        std::fs::create_dir_all(dest).map_err(internal)?;
        let mut archive = Command::new("git")
            .arg("-C")
            .arg(&self.root)
            .args(["archive", "--format=tar", base, "--", path])
            .stdout(Stdio::piped())
            .stderr(Stdio::piped())
            .spawn()
            .map_err(internal)?;
        let tar_in = archive.stdout.take().ok_or_else(|| internal("git archive: no stdout"))?;
        let tar = Command::new("tar").arg("-x").arg("-C").arg(dest).stdin(tar_in).output().map_err(internal)?;
        let a = archive.wait_with_output().map_err(internal)?;
        if !a.status.success() || !tar.status.success() {
            return Err(internal(format!(
                "extracting {path} of {base}: {}{}",
                String::from_utf8_lossy(&a.stderr).trim(),
                String::from_utf8_lossy(&tar.stderr).trim()
            )));
        }
        Ok(())
    }

    /// The lines `base`'s CHANGELOG at `path` does not have and the working tree's has.
    pub fn added_lines(&self, base: &str, path: &str) -> Result<Vec<String>, OpError> {
        let old = self.base_file(base, path)?.unwrap_or_default();
        let new = self.head_file(path).unwrap_or_default();
        Ok(added_lines(&String::from_utf8_lossy(&old), &String::from_utf8_lossy(&new)))
    }
}

/// Whether `path` is under `pathspecs`, as git reads the forms used here: a plain path (the
/// file, or everything below the directory), `:(glob)<pattern>` and `:(exclude,glob)<pattern>`,
/// where `*` matches within one path segment and `**` matches any number of segments.
pub fn matches(pathspecs: &[&str], path: &str) -> bool {
    let mut included = false;
    for spec in pathspecs {
        let (exclude, pattern, glob) = if let Some(p) = spec.strip_prefix(":(exclude,glob)") {
            (true, p, true)
        } else if let Some(p) = spec.strip_prefix(":(glob)") {
            (false, p, true)
        } else {
            (false, *spec, false)
        };
        let hit = if glob { glob_match(&pattern.split('/').collect::<Vec<_>>(), &path.split('/').collect::<Vec<_>>()) } else { path == pattern || path.starts_with(&format!("{}/", pattern.trim_end_matches('/'))) };
        if hit && exclude {
            return false;
        }
        included |= hit;
    }
    included
}

fn glob_match(pat: &[&str], path: &[&str]) -> bool {
    match (pat.first(), path.first()) {
        (None, None) => true,
        (Some(&"**"), _) => glob_match(&pat[1..], path) || (!path.is_empty() && glob_match(pat, &path[1..])),
        (Some(p), Some(s)) => segment_match(p.as_bytes(), s.as_bytes()) && glob_match(&pat[1..], &path[1..]),
        _ => false,
    }
}

fn segment_match(p: &[u8], s: &[u8]) -> bool {
    match (p.first(), s.first()) {
        (None, None) => true,
        (Some(b'*'), _) => segment_match(&p[1..], s) || (!s.is_empty() && segment_match(p, &s[1..])),
        (Some(b'?'), Some(_)) => segment_match(&p[1..], &s[1..]),
        (Some(a), Some(b)) if a == b => segment_match(&p[1..], &s[1..]),
        _ => false,
    }
}

fn split0(b: &[u8]) -> Vec<String> {
    b.split(|x| *x == 0).filter(|s| !s.is_empty()).map(|s| String::from_utf8_lossy(s).into_owned()).collect()
}

/// The lines of `new` that a longest common subsequence with `old` leaves over: what an
/// edit added, in order. A line moved within the file counts as added where it now is.
pub fn added_lines(old: &str, new: &str) -> Vec<String> {
    let a: Vec<&str> = old.lines().collect();
    let b: Vec<&str> = new.lines().collect();
    // Trim the common head and tail first: a changelog edit is a few lines near the top of a
    // long file, and what is left between is small.
    let mut lo = 0;
    while lo < a.len() && lo < b.len() && a[lo] == b[lo] {
        lo += 1;
    }
    let (mut ea, mut eb) = (a.len(), b.len());
    while ea > lo && eb > lo && a[ea - 1] == b[eb - 1] {
        ea -= 1;
        eb -= 1;
    }
    let (a, b) = (&a[lo..ea], &b[lo..eb]);
    if a.is_empty() {
        return b.iter().map(|s| s.to_string()).collect();
    }
    if (a.len() as u64) * (b.len() as u64) > 40_000_000 {
        // Too far apart for the table: every line not in the old file counts as added.
        let old: std::collections::HashSet<&str> = a.iter().copied().collect();
        return b.iter().filter(|l| !old.contains(*l)).map(|s| s.to_string()).collect();
    }
    let (n, m) = (a.len(), b.len());
    let mut t = vec![0u32; (n + 1) * (m + 1)];
    for i in (0..n).rev() {
        for j in (0..m).rev() {
            t[i * (m + 1) + j] = if a[i] == b[j] { t[(i + 1) * (m + 1) + j + 1] + 1 } else { t[(i + 1) * (m + 1) + j].max(t[i * (m + 1) + j + 1]) };
        }
    }
    let (mut i, mut j) = (0, 0);
    let mut out = Vec::new();
    while j < m {
        if i < n && a[i] == b[j] {
            i += 1;
            j += 1;
        } else if i < n && t[(i + 1) * (m + 1) + j] >= t[i * (m + 1) + j + 1] {
            i += 1;
        } else {
            out.push(b[j].to_string());
            j += 1;
        }
    }
    out
}

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

    #[test]
    fn pathspecs_match_as_git_reads_them() {
        use super::matches;
        let specs = [":(glob)wai/*/src/**/*.rs", ":(exclude,glob)wai/*/src/bin/**"];
        assert!(matches(&specs, "wai/wai-rs/src/live_events.rs"));
        assert!(matches(&specs, "wai/wai-rs/src/a/b/c.rs"));
        assert!(!matches(&specs, "wai/wai-rs/src/bin/wai.rs"));
        assert!(!matches(&specs, "wai/wai-rs/tests/x.rs"));
        assert!(matches(&[":(glob)wai/**/openapi*.json"], "wai/openapi.json"));
        assert!(matches(&["joule-code/x/openapi.json"], "joule-code/x/openapi.json"));
        assert!(matches(&[":(glob)wai/*-conformance/**"], "wai/claim-conformance/vectors.json"));
        assert!(!matches(&[":(glob)wai/*-conformance/**"], "wai/wai-rs/x"));
    }

    #[test]
    fn added_lines_are_the_new_ones() {
        assert_eq!(added_lines("a\nb\nc\n", "a\nx\nb\nc\ny\n"), vec!["x", "y"]);
        assert_eq!(added_lines("", "a\n"), vec!["a"]);
        assert!(added_lines("a\nb\n", "a\n").is_empty());
        assert_eq!(added_lines("a\nb\n", "b\na\n"), vec!["a"]);
    }
}
