sequoia-git 0.5.0

use std::{
    collections::{
        BTreeSet
    },
};

use anyhow::Result;
use git2::{
    Repository,
    Oid,
};

use crate::{
    Error,
};

const TRACE: bool = false;

/// Returns whether `ancestor` is an ancestor of `target`.
///
/// A commit is considered to be an ancestor of another commit if
/// there is a path from the first commit to the target commit.  Note:
/// this does not authenticate the path, or even check whether the
/// commits are signed.  Commits are considered their own ancestors.
///
/// Returns `Ok(())` if there is a path.  If there is no path, returns
/// `Err(Error::NoPathConnecting)`.
pub fn git_is_ancestor(git: &Repository, ancestor: Oid, target: Oid) -> Result<()> {
    tracer!(TRACE, "is_ancestor");
    t!("Looking for {}..{}", ancestor, target);

    if ancestor.is_zero() {
        return Err(Error::NoPathConnecting(ancestor, target).into());
    }

    if ancestor == target {
        return Ok(());
    }

    // Whether we've already processed a commit.
    let mut processed: BTreeSet<Oid> = Default::default();

    // Commits that we still need to process.
    let mut pending: BTreeSet<Oid> = Default::default();
    pending.insert(target.clone());

    while let Some(commit_id) = pending.pop_first() {
        t!("Visiting commit {:?}", commit_id);
        processed.insert(commit_id.clone());

        let commit = git.find_commit(commit_id)?;

        for parent in commit.parents() {
            let parent_id = parent.id();
            if processed.contains(&parent_id) || pending.contains(&parent_id) {
                // There is a valid path from PARENT to TARGET, which
                // is not via COMMIT.  There is no need to find a
                // second path.
                continue;
            }

            if parent_id == ancestor {
                t!("Reached ancestor!");
                return Ok(());
            }

            pending.insert(parent_id.clone());
        }
    }

    Err(Error::NoPathConnecting(ancestor, target).into())
}

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

    use std::path::Path;

    use tempfile::TempDir;

    use git2::Commit;
    use git2::Repository;

    fn commit_file<'repo, P>(repo: &'repo Repository,
                             filename: P, content: &[u8],
                             commit_message: &str,
                             parents: &[&Commit<'repo>]) -> Commit<'repo>
        where P: AsRef<Path>
    {
        let filename = filename.as_ref();

        let filename_abs = repo.workdir().unwrap().join(&filename);
        std::fs::write(&filename_abs, content).unwrap();

        let mut index = repo.index().unwrap();
        index.add_path(&filename).unwrap();

        let oid = index.write_tree().unwrap();
        let tree = repo.find_tree(oid).unwrap();

        let sig = repo.signature().unwrap();

        let commit_oid = repo.commit(
            None, &sig, &sig, commit_message, &tree, parents)
            .unwrap();

        let commit = repo.find_commit(commit_oid).unwrap();

        commit
    }

    #[test]
    fn ancestor() -> Result<()> {
        let dir = TempDir::new()?;

        let repo = Repository::init(&dir)
            .expect("Initialize git repository");

        let mut config = repo.config().unwrap();
        config.set_str("user.name", "name").unwrap();
        config.set_str("user.email", "email").unwrap();

        //   root
        //   /  \
        // l.0  r.0
        //  |    |
        // l.1  r.1
        //   \  /
        //  merge
        //    |
        //   c.0
        //    |
        //   c.1

        let root = commit_file(
            &repo, "root", b"root", "root", &[]);

        let l_0 = commit_file(
            &repo, "l", b"0", "commit l.0", &[ &root ]);
        let l_1 = commit_file(
            &repo, "l", b"1", "commit l.1", &[ &l_0 ]);

        let r_0 = commit_file(
            &repo, "r", b"0", "commit r.0", &[ &root ]);
        let r_1 = commit_file(
            &repo, "r", b"1", "commit r.1", &[ &r_0 ]);

        let m = commit_file(
            &repo, "m", b"merge!", "commit merge", &[ &l_1, &r_1 ]);

        let c_0 = commit_file(
            &repo, "c", b"0", "commit c.0", &[ &m ]);

        let c_1 = commit_file(
            &repo, "c", b"1", "commit c.1", &[ &c_0 ]);

        let all_commits = &[&root, &l_0, &l_1, &r_0, &r_1, &m, &c_0, &c_1 ];

        // All the commits in a topological order.
        let paths = &[
            // Via l.
            &[&root, &l_0, &l_1, &m, &c_0, &c_1 ],
            // Via r.
            &[&root, &r_0, &r_1, &m, &c_0, &c_1 ],
        ];

        let t = |ancestor: &Commit, commit: &Commit, expect: bool| {
            match (expect,
                   git_is_ancestor(&repo, ancestor.id(), commit.id()).is_ok())
            {
                (true, true) => (),
                (false, false) => (),
                (true, false) => {
                    panic!("Expected {} ({}) to be an ancestor of {} ({})",
                           ancestor.summary().unwrap_or("<unknown>"),
                           ancestor.id(),
                           commit.summary().unwrap_or("<unknown>"),
                           commit.id());
                }
                (false, true) => {
                    panic!("Expected {} ({}) to NOT be an ancestor of {} ({})",
                           ancestor.summary().unwrap_or("<unknown>"),
                           ancestor.id(),
                           commit.summary().unwrap_or("<unknown>"),
                           commit.id());
                }
            }
        };

        // Commits are their own ancestors.
        for c in all_commits.iter() {
            t(c, c, true);
        }

        for path in paths.iter() {
            for i in 0..(path.len() - 1) {
                for j in (i + 1)..path.len() {
                    t(&path[i], &path[j], true);
                    t(&path[j], &path[i], false);
                }
            }
        }

        t(&l_0, &r_0, false);
        t(&l_0, &r_1, false);
        t(&l_1, &r_0, false);
        t(&l_1, &r_1, false);

        t(&r_0, &l_0, false);
        t(&r_0, &l_1, false);
        t(&r_1, &l_0, false);
        t(&r_1, &l_1, false);

        Ok(())
    }
}