refactor: `tests` is now `tests/libgit2`

Like we want to separate libgit2 and utility source code, we want to
separate libgit2 and utility tests.  Start by moving all the tests into
libgit2.

4 files changed, 475 insertions, 0 deletions

diff --git a/tests/libgit2/graph/ahead_behind.c b/tests/libgit2/graph/ahead_behind.c
new file mode 100644
index 000000000..77d7768af
--- /dev/null
+++ b/tests/libgit2/graph/ahead_behind.c
@@ -0,0 +1,58 @@
+#include "clar_libgit2.h"
+
+static git_repository *_repo;
+static git_commit *commit;
+static size_t ahead;
+static size_t behind;
+
+void test_graph_ahead_behind__initialize(void)
+{
+	git_oid oid;
+	cl_git_pass(git_repository_open(&_repo, cl_fixture("testrepo.git")));
+
+	cl_git_pass(git_oid_fromstr(&oid, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644"));
+	cl_git_pass(git_commit_lookup(&commit, _repo, &oid));
+}
+
+void test_graph_ahead_behind__cleanup(void)
+{
+	git_commit_free(commit);
+	commit = NULL;
+
+	git_repository_free(_repo);
+	_repo = NULL;
+}
+
+void test_graph_ahead_behind__returns_correct_result(void)
+{	
+	git_oid oid;
+	git_oid oid2;
+	git_commit *other;
+
+	cl_git_pass(git_oid_fromstr(&oid, "e90810b8df3e80c413d903f631643c716887138d"));
+	cl_git_pass(git_oid_fromstr(&oid2, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644"));
+	
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, &oid, &oid2));
+	cl_assert_equal_sz(2, ahead);
+	cl_assert_equal_sz(6, behind);
+
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, git_commit_id(commit), git_commit_id(commit)));
+	cl_assert_equal_sz(ahead, behind);
+	cl_git_pass(git_commit_nth_gen_ancestor(&other, commit, 1));
+
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, git_commit_id(commit), git_commit_id(other)));
+	cl_assert_equal_sz(ahead, behind + 2);
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, git_commit_id(other), git_commit_id(commit)));
+	cl_assert_equal_sz(ahead + 2, behind);
+
+	git_commit_free(other);
+
+	cl_git_pass(git_commit_nth_gen_ancestor(&other, commit, 3));
+
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, git_commit_id(commit), git_commit_id(other)));
+	cl_assert_equal_sz(ahead, behind + 4);
+	cl_git_pass(git_graph_ahead_behind(&ahead, &behind, _repo, git_commit_id(other), git_commit_id(commit)));
+	cl_assert_equal_sz(ahead + 4, behind);
+
+	git_commit_free(other);
+}
diff --git a/tests/libgit2/graph/commitgraph.c b/tests/libgit2/graph/commitgraph.c
new file mode 100644
index 000000000..7607c35a3
--- /dev/null
+++ b/tests/libgit2/graph/commitgraph.c
@@ -0,0 +1,126 @@
+#include "clar_libgit2.h"
+
+#include <git2.h>
+#include <git2/sys/commit_graph.h>
+
+#include "commit_graph.h"
+#include "futils.h"
+
+void test_graph_commitgraph__parse(void)
+{
+	git_repository *repo;
+	struct git_commit_graph_file *file;
+	struct git_commit_graph_entry e, parent;
+	git_oid id;
+	git_str commit_graph_path = GIT_STR_INIT;
+
+	cl_git_pass(git_repository_open(&repo, cl_fixture("testrepo.git")));
+	cl_git_pass(git_str_joinpath(&commit_graph_path, git_repository_path(repo), "objects/info/commit-graph"));
+	cl_git_pass(git_commit_graph_file_open(&file, git_str_cstr(&commit_graph_path)));
+	cl_assert_equal_i(git_commit_graph_file_needs_refresh(file, git_str_cstr(&commit_graph_path)), 0);
+
+	cl_git_pass(git_oid_fromstr(&id, "5001298e0c09ad9c34e4249bc5801c75e9754fa5"));
+	cl_git_pass(git_commit_graph_entry_find(&e, file, &id, GIT_OID_HEXSZ));
+	cl_assert_equal_oid(&e.sha1, &id);
+	cl_git_pass(git_oid_fromstr(&id, "418382dff1ffb8bdfba833f4d8bbcde58b1e7f47"));
+	cl_assert_equal_oid(&e.tree_oid, &id);
+	cl_assert_equal_i(e.generation, 1);
+	cl_assert_equal_i(e.commit_time, UINT64_C(1273610423));
+	cl_assert_equal_i(e.parent_count, 0);
+
+	cl_git_pass(git_oid_fromstr(&id, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644"));
+	cl_git_pass(git_commit_graph_entry_find(&e, file, &id, GIT_OID_HEXSZ));
+	cl_assert_equal_oid(&e.sha1, &id);
+	cl_assert_equal_i(e.generation, 5);
+	cl_assert_equal_i(e.commit_time, UINT64_C(1274813907));
+	cl_assert_equal_i(e.parent_count, 2);
+
+	cl_git_pass(git_oid_fromstr(&id, "9fd738e8f7967c078dceed8190330fc8648ee56a"));
+	cl_git_pass(git_commit_graph_entry_parent(&parent, file, &e, 0));
+	cl_assert_equal_oid(&parent.sha1, &id);
+	cl_assert_equal_i(parent.generation, 4);
+
+	cl_git_pass(git_oid_fromstr(&id, "c47800c7266a2be04c571c04d5a6614691ea99bd"));
+	cl_git_pass(git_commit_graph_entry_parent(&parent, file, &e, 1));
+	cl_assert_equal_oid(&parent.sha1, &id);
+	cl_assert_equal_i(parent.generation, 3);
+
+	git_commit_graph_file_free(file);
+	git_repository_free(repo);
+	git_str_dispose(&commit_graph_path);
+}
+
+void test_graph_commitgraph__parse_octopus_merge(void)
+{
+	git_repository *repo;
+	struct git_commit_graph_file *file;
+	struct git_commit_graph_entry e, parent;
+	git_oid id;
+	git_str commit_graph_path = GIT_STR_INIT;
+
+	cl_git_pass(git_repository_open(&repo, cl_fixture("merge-recursive/.gitted")));
+	cl_git_pass(git_str_joinpath(&commit_graph_path, git_repository_path(repo), "objects/info/commit-graph"));
+	cl_git_pass(git_commit_graph_file_open(&file, git_str_cstr(&commit_graph_path)));
+
+	cl_git_pass(git_oid_fromstr(&id, "d71c24b3b113fd1d1909998c5bfe33b86a65ee03"));
+	cl_git_pass(git_commit_graph_entry_find(&e, file, &id, GIT_OID_HEXSZ));
+	cl_assert_equal_oid(&e.sha1, &id);
+	cl_git_pass(git_oid_fromstr(&id, "348f16ffaeb73f319a75cec5b16a0a47d2d5e27c"));
+	cl_assert_equal_oid(&e.tree_oid, &id);
+	cl_assert_equal_i(e.generation, 7);
+	cl_assert_equal_i(e.commit_time, UINT64_C(1447083009));
+	cl_assert_equal_i(e.parent_count, 3);
+
+	cl_git_pass(git_oid_fromstr(&id, "ad2ace9e15f66b3d1138922e6ffdc3ea3f967fa6"));
+	cl_git_pass(git_commit_graph_entry_parent(&parent, file, &e, 0));
+	cl_assert_equal_oid(&parent.sha1, &id);
+	cl_assert_equal_i(parent.generation, 6);
+
+	cl_git_pass(git_oid_fromstr(&id, "483065df53c0f4a02cdc6b2910b05d388fc17ffb"));
+	cl_git_pass(git_commit_graph_entry_parent(&parent, file, &e, 1));
+	cl_assert_equal_oid(&parent.sha1, &id);
+	cl_assert_equal_i(parent.generation, 2);
+
+	cl_git_pass(git_oid_fromstr(&id, "815b5a1c80ca749d705c7aa0cb294a00cbedd340"));
+	cl_git_pass(git_commit_graph_entry_parent(&parent, file, &e, 2));
+	cl_assert_equal_oid(&parent.sha1, &id);
+	cl_assert_equal_i(parent.generation, 6);
+
+	git_commit_graph_file_free(file);
+	git_repository_free(repo);
+	git_str_dispose(&commit_graph_path);
+}
+
+void test_graph_commitgraph__writer(void)
+{
+	git_repository *repo;
+	git_commit_graph_writer *w = NULL;
+	git_revwalk *walk;
+	git_commit_graph_writer_options opts = GIT_COMMIT_GRAPH_WRITER_OPTIONS_INIT;
+	git_buf cgraph = GIT_BUF_INIT;
+	git_str expected_cgraph = GIT_STR_INIT, path = GIT_STR_INIT;
+
+	cl_git_pass(git_repository_open(&repo, cl_fixture("testrepo.git")));
+
+	cl_git_pass(git_str_joinpath(&path, git_repository_path(repo), "objects/info"));
+	cl_git_pass(git_commit_graph_writer_new(&w, git_str_cstr(&path)));
+
+	/* This is equivalent to `git commit-graph write --reachable`. */
+	cl_git_pass(git_revwalk_new(&walk, repo));
+	cl_git_pass(git_revwalk_push_glob(walk, "refs/*"));
+	cl_git_pass(git_commit_graph_writer_add_revwalk(w, walk));
+	git_revwalk_free(walk);
+
+	cl_git_pass(git_commit_graph_writer_dump(&cgraph, w, &opts));
+	cl_git_pass(git_str_joinpath(&path, git_repository_path(repo), "objects/info/commit-graph"));
+	cl_git_pass(git_futils_readbuffer(&expected_cgraph, git_str_cstr(&path)));
+
+	cl_assert_equal_i(cgraph.size, git_str_len(&expected_cgraph));
+	cl_assert_equal_i(memcmp(cgraph.ptr, git_str_cstr(&expected_cgraph), cgraph.size), 0);
+
+	git_buf_dispose(&cgraph);
+	git_str_dispose(&expected_cgraph);
+	git_str_dispose(&path);
+	git_commit_graph_writer_free(w);
+	git_repository_free(repo);
+}
diff --git a/tests/libgit2/graph/descendant_of.c b/tests/libgit2/graph/descendant_of.c
new file mode 100644
index 000000000..8e9952a09
--- /dev/null
+++ b/tests/libgit2/graph/descendant_of.c
@@ -0,0 +1,55 @@
+#include "clar_libgit2.h"
+
+static git_repository *_repo;
+static git_commit *commit;
+
+void test_graph_descendant_of__initialize(void)
+{
+	git_oid oid;
+
+	cl_git_pass(git_repository_open(&_repo, cl_fixture("testrepo.git")));
+
+	git_oid_fromstr(&oid, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644");
+	cl_git_pass(git_commit_lookup(&commit, _repo, &oid));
+}
+
+void test_graph_descendant_of__cleanup(void)
+{
+	git_commit_free(commit);
+	commit = NULL;
+
+	git_repository_free(_repo);
+	_repo = NULL;
+}
+
+void test_graph_descendant_of__returns_correct_result(void)
+{
+	git_commit *other;
+
+	cl_assert_equal_i(0, git_graph_descendant_of(_repo, git_commit_id(commit), git_commit_id(commit)));
+
+
+	cl_git_pass(git_commit_nth_gen_ancestor(&other, commit, 1));
+
+	cl_assert_equal_i(1, git_graph_descendant_of(_repo, git_commit_id(commit), git_commit_id(other)));
+	cl_assert_equal_i(0, git_graph_descendant_of(_repo, git_commit_id(other), git_commit_id(commit)));
+
+	git_commit_free(other);
+
+
+	cl_git_pass(git_commit_nth_gen_ancestor(&other, commit, 3));
+
+	cl_assert_equal_i(1, git_graph_descendant_of(_repo, git_commit_id(commit), git_commit_id(other)));
+	cl_assert_equal_i(0, git_graph_descendant_of(_repo, git_commit_id(other), git_commit_id(commit)));
+
+	git_commit_free(other);
+
+}
+
+void test_graph_descendant_of__nopath(void)
+{
+	git_oid oid;
+
+	git_oid_fromstr(&oid, "e90810b8df3e80c413d903f631643c716887138d");
+	cl_assert_equal_i(0, git_graph_descendant_of(_repo, git_commit_id(commit), &oid));
+}
diff --git a/tests/libgit2/graph/reachable_from_any.c b/tests/libgit2/graph/reachable_from_any.c
new file mode 100644
index 000000000..9693d7d67
--- /dev/null
+++ b/tests/libgit2/graph/reachable_from_any.c
@@ -0,0 +1,236 @@
+#include "clar_libgit2.h"
+
+#include <git2.h>
+
+#include "commit_graph.h"
+#include "bitvec.h"
+#include "vector.h"
+
+static git_repository *repo;
+
+#define TEST_REPO_PATH "merge-recursive"
+
+void test_graph_reachable_from_any__initialize(void)
+{
+	git_oid oid;
+	git_commit *commit;
+
+	repo = cl_git_sandbox_init(TEST_REPO_PATH);
+
+	git_oid_fromstr(&oid, "539bd011c4822c560c1d17cab095006b7a10f707");
+	cl_git_pass(git_commit_lookup(&commit, repo, &oid));
+	cl_git_pass(git_reset(repo, (git_object *)commit, GIT_RESET_HARD, NULL));
+	git_commit_free(commit);
+}
+
+void test_graph_reachable_from_any__cleanup(void)
+{
+	cl_git_sandbox_cleanup();
+}
+
+void test_graph_reachable_from_any__returns_correct_result(void)
+{
+	git_object *branchA1, *branchA2, *branchB1, *branchB2, *branchC1, *branchC2, *branchH1,
+			*branchH2;
+	git_oid descendants[7];
+
+	cl_git_pass(git_revparse_single(&branchA1, repo, "branchA-1"));
+	cl_git_pass(git_revparse_single(&branchA2, repo, "branchA-2"));
+	cl_git_pass(git_revparse_single(&branchB1, repo, "branchB-1"));
+	cl_git_pass(git_revparse_single(&branchB2, repo, "branchB-2"));
+	cl_git_pass(git_revparse_single(&branchC1, repo, "branchC-1"));
+	cl_git_pass(git_revparse_single(&branchC2, repo, "branchC-2"));
+	cl_git_pass(git_revparse_single(&branchH1, repo, "branchH-1"));
+	cl_git_pass(git_revparse_single(&branchH2, repo, "branchH-2"));
+
+	cl_assert_equal_i(
+			git_graph_reachable_from_any(
+					repo, git_object_id(branchH1), git_object_id(branchA1), 1),
+			0);
+	cl_assert_equal_i(
+			git_graph_reachable_from_any(
+					repo, git_object_id(branchH1), git_object_id(branchA2), 1),
+			0);
+
+	cl_git_pass(git_oid_cpy(&descendants[0], git_object_id(branchA1)));
+	cl_git_pass(git_oid_cpy(&descendants[1], git_object_id(branchA2)));
+	cl_git_pass(git_oid_cpy(&descendants[2], git_object_id(branchB1)));
+	cl_git_pass(git_oid_cpy(&descendants[3], git_object_id(branchB2)));
+	cl_git_pass(git_oid_cpy(&descendants[4], git_object_id(branchC1)));
+	cl_git_pass(git_oid_cpy(&descendants[5], git_object_id(branchC2)));
+	cl_git_pass(git_oid_cpy(&descendants[6], git_object_id(branchH2)));
+	cl_assert_equal_i(
+			git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 6),
+			0);
+	cl_assert_equal_i(
+			git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 7),
+			1);
+
+	git_object_free(branchA1);
+	git_object_free(branchA2);
+	git_object_free(branchB1);
+	git_object_free(branchB2);
+	git_object_free(branchC1);
+	git_object_free(branchC2);
+	git_object_free(branchH1);
+	git_object_free(branchH2);
+}
+
+struct exhaustive_state {
+	git_odb *db;
+	git_vector commits;
+};
+
+/** Get all commits from the repository. */
+static int exhaustive_commits(const git_oid *id, void *payload)
+{
+	struct exhaustive_state *mc = (struct exhaustive_state *)payload;
+	size_t header_len;
+	git_object_t header_type;
+	int error = 0;
+
+	error = git_odb_read_header(&header_len, &header_type, mc->db, id);
+	if (error < 0)
+		return error;
+
+	if (header_type == GIT_OBJECT_COMMIT) {
+		git_commit *commit = NULL;
+
+		cl_git_pass(git_commit_lookup(&commit, repo, id));
+		cl_git_pass(git_vector_insert(&mc->commits, commit));
+	}
+
+	return 0;
+}
+
+/** Compare the `git_oid`s of two `git_commit` objects. */
+static int commit_id_cmp(const void *a, const void *b)
+{
+	return git_oid_cmp(
+			git_commit_id((const git_commit *)a), git_commit_id((const git_commit *)b));
+}
+
+/** Find a `git_commit` whose ID matches the provided `git_oid` key. */
+static int id_commit_id_cmp(const void *key, const void *commit)
+{
+	return git_oid_cmp((const git_oid *)key, git_commit_id((const git_commit *)commit));
+}
+
+void test_graph_reachable_from_any__exhaustive(void)
+{
+	struct exhaustive_state mc = {
+			.db = NULL,
+			.commits = GIT_VECTOR_INIT,
+	};
+	size_t child_idx, commit_count;
+	size_t n_descendants;
+	git_commit *child_commit;
+	git_bitvec reachable;
+
+	cl_git_pass(git_repository_odb(&mc.db, repo));
+	cl_git_pass(git_odb_foreach(mc.db, &exhaustive_commits, &mc));
+	git_vector_set_cmp(&mc.commits, commit_id_cmp);
+	git_vector_sort(&mc.commits);
+	cl_git_pass(git_bitvec_init(
+			&reachable,
+			git_vector_length(&mc.commits) * git_vector_length(&mc.commits)));
+
+	commit_count = git_vector_length(&mc.commits);
+	git_vector_foreach (&mc.commits, child_idx, child_commit) {
+		unsigned int parent_i;
+
+		/* We treat each commit as being able to reach itself. */
+		git_bitvec_set(&reachable, child_idx * commit_count + child_idx, true);
+
+		for (parent_i = 0; parent_i < git_commit_parentcount(child_commit); ++parent_i) {
+			size_t parent_idx = -1;
+			cl_git_pass(git_vector_bsearch2(
+					&parent_idx,
+					&mc.commits,
+					id_commit_id_cmp,
+					git_commit_parent_id(child_commit, parent_i)));
+
+			/* We have established that parent_idx is reachable from child_idx */
+			git_bitvec_set(&reachable, parent_idx * commit_count + child_idx, true);
+		}
+	}
+
+	/* Floyd-Warshall */
+	{
+		size_t i, j, k;
+		for (k = 0; k < commit_count; ++k) {
+			for (i = 0; i < commit_count; ++i) {
+				if (!git_bitvec_get(&reachable, i * commit_count + k))
+					continue;
+				for (j = 0; j < commit_count; ++j) {
+					if (!git_bitvec_get(&reachable, k * commit_count + j))
+						continue;
+					git_bitvec_set(&reachable, i * commit_count + j, true);
+				}
+			}
+		}
+	}
+
+	/* Try 1000 subsets of 1 through 10 entries each. */
+	srand(0x223ddc4b);
+	for (n_descendants = 1; n_descendants < 10; ++n_descendants) {
+		size_t test_iteration;
+		git_oid descendants[10];
+
+		for (test_iteration = 0; test_iteration < 1000; ++test_iteration) {
+			size_t descendant_i;
+			size_t child_idx, parent_idx;
+			int expected_reachable = false, actual_reachable;
+			git_commit *child_commit, *parent_commit;
+
+			parent_idx = rand() % commit_count;
+			parent_commit = (git_commit *)git_vector_get(&mc.commits, parent_idx);
+			for (descendant_i = 0; descendant_i < n_descendants; ++descendant_i) {
+				child_idx = rand() % commit_count;
+				child_commit = (git_commit *)git_vector_get(&mc.commits, child_idx);
+				expected_reachable |= git_bitvec_get(
+						&reachable, parent_idx * commit_count + child_idx);
+				git_oid_cpy(&descendants[descendant_i],
+					    git_commit_id(child_commit));
+			}
+
+			actual_reachable = git_graph_reachable_from_any(
+					repo,
+					git_commit_id(parent_commit),
+					descendants,
+					n_descendants);
+			if (actual_reachable != expected_reachable) {
+				git_str error_message_buf = GIT_STR_INIT;
+				char parent_oidbuf[9] = {0}, child_oidbuf[9] = {0};
+
+				cl_git_pass(git_oid_nfmt(
+						parent_oidbuf, 8, git_commit_id(parent_commit)));
+				git_str_printf(&error_message_buf,
+					       "git_graph_reachable_from_any(\"%s\", %zu, "
+					       "{",
+					       parent_oidbuf,
+					       n_descendants);
+				for (descendant_i = 0; descendant_i < n_descendants;
+				     ++descendant_i) {
+					cl_git_pass(
+							git_oid_nfmt(child_oidbuf,
+								     8,
+								     &descendants[descendant_i]));
+					git_str_printf(&error_message_buf, " \"%s\"", child_oidbuf);
+				}
+				git_str_printf(&error_message_buf,
+					       " }) = %d, expected = %d",
+					       actual_reachable,
+					       expected_reachable);
+				cl_check_(actual_reachable == expected_reachable,
+					  git_str_cstr(&error_message_buf));
+			}
+		}
+	}
+
+	git_vector_foreach (&mc.commits, child_idx, child_commit)
+		git_commit_free(child_commit);
+	git_bitvec_free(&reachable);
+	git_vector_free(&mc.commits);
+	git_odb_free(mc.db);
+}