tests/libgit2/graph/reachable_from_any.c

   1 #include "clar_libgit2.h"
   2
   3 #include <git2.h>
   4
   5 #include "commit_graph.h"
   6 #include "bitvec.h"
   7 #include "vector.h"
   8
   9 static git_repository *repo;
  10
  11 #define TEST_REPO_PATH "merge-recursive"
  12
  13 void test_graph_reachable_from_any__initialize(void)
  14 {
  15         git_oid oid;
  16         git_commit *commit;
  17
  18         repo = cl_git_sandbox_init(TEST_REPO_PATH);
  19
  20         git_oid_fromstr(&oid, "539bd011c4822c560c1d17cab095006b7a10f707");
  21         cl_git_pass(git_commit_lookup(&commit, repo, &oid));
  22         cl_git_pass(git_reset(repo, (git_object *)commit, GIT_RESET_HARD, NULL));
  23         git_commit_free(commit);
  24 }
  25
  26 void test_graph_reachable_from_any__cleanup(void)
  27 {
  28         cl_git_sandbox_cleanup();
  29 }
  30
  31 void test_graph_reachable_from_any__returns_correct_result(void)
  32 {
  33         git_object *branchA1, *branchA2, *branchB1, *branchB2, *branchC1, *branchC2, *branchH1,
  34                         *branchH2;
  35         git_oid descendants[7];
  36
  37         cl_git_pass(git_revparse_single(&branchA1, repo, "branchA-1"));
  38         cl_git_pass(git_revparse_single(&branchA2, repo, "branchA-2"));
  39         cl_git_pass(git_revparse_single(&branchB1, repo, "branchB-1"));
  40         cl_git_pass(git_revparse_single(&branchB2, repo, "branchB-2"));
  41         cl_git_pass(git_revparse_single(&branchC1, repo, "branchC-1"));
  42         cl_git_pass(git_revparse_single(&branchC2, repo, "branchC-2"));
  43         cl_git_pass(git_revparse_single(&branchH1, repo, "branchH-1"));
  44         cl_git_pass(git_revparse_single(&branchH2, repo, "branchH-2"));
  45
  46         cl_assert_equal_i(
  47                         git_graph_reachable_from_any(
  48                                         repo, git_object_id(branchH1), git_object_id(branchA1), 1),
  49                         0);
  50         cl_assert_equal_i(
  51                         git_graph_reachable_from_any(
  52                                         repo, git_object_id(branchH1), git_object_id(branchA2), 1),
  53                         0);
  54
  55         cl_git_pass(git_oid_cpy(&descendants[0], git_object_id(branchA1)));
  56         cl_git_pass(git_oid_cpy(&descendants[1], git_object_id(branchA2)));
  57         cl_git_pass(git_oid_cpy(&descendants[2], git_object_id(branchB1)));
  58         cl_git_pass(git_oid_cpy(&descendants[3], git_object_id(branchB2)));
  59         cl_git_pass(git_oid_cpy(&descendants[4], git_object_id(branchC1)));
  60         cl_git_pass(git_oid_cpy(&descendants[5], git_object_id(branchC2)));
  61         cl_git_pass(git_oid_cpy(&descendants[6], git_object_id(branchH2)));
  62         cl_assert_equal_i(
  63                         git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 6),
  64                         0);
  65         cl_assert_equal_i(
  66                         git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 7),
  67                         1);
  68
  69         git_object_free(branchA1);
  70         git_object_free(branchA2);
  71         git_object_free(branchB1);
  72         git_object_free(branchB2);
  73         git_object_free(branchC1);
  74         git_object_free(branchC2);
  75         git_object_free(branchH1);
  76         git_object_free(branchH2);
  77 }
  78
  79 struct exhaustive_state {
  80         git_odb *db;
  81         git_vector commits;
  82 };
  83
  84 /** Get all commits from the repository. */
  85 static int exhaustive_commits(const git_oid *id, void *payload)
  86 {
  87         struct exhaustive_state *mc = (struct exhaustive_state *)payload;
  88         size_t header_len;
  89         git_object_t header_type;
  90         int error = 0;
  91
  92         error = git_odb_read_header(&header_len, &header_type, mc->db, id);
  93         if (error < 0)
  94                 return error;
  95
  96         if (header_type == GIT_OBJECT_COMMIT) {
  97                 git_commit *commit = NULL;
  98
  99                 cl_git_pass(git_commit_lookup(&commit, repo, id));
 100                 cl_git_pass(git_vector_insert(&mc->commits, commit));
 101         }
 102
 103         return 0;
 104 }
 105
 106 /** Compare the `git_oid`s of two `git_commit` objects. */
 107 static int commit_id_cmp(const void *a, const void *b)
 108 {
 109         return git_oid_cmp(
 110                         git_commit_id((const git_commit *)a), git_commit_id((const git_commit *)b));
 111 }
 112
 113 /** Find a `git_commit` whose ID matches the provided `git_oid` key. */
 114 static int id_commit_id_cmp(const void *key, const void *commit)
 115 {
 116         return git_oid_cmp((const git_oid *)key, git_commit_id((const git_commit *)commit));
 117 }
 118
 119 void test_graph_reachable_from_any__exhaustive(void)
 120 {
 121         struct exhaustive_state mc = {
 122                         .db = NULL,
 123                         .commits = GIT_VECTOR_INIT,
 124         };
 125         size_t child_idx, commit_count;
 126         size_t n_descendants;
 127         git_commit *child_commit;
 128         git_bitvec reachable;
 129
 130         cl_git_pass(git_repository_odb(&mc.db, repo));
 131         cl_git_pass(git_odb_foreach(mc.db, &exhaustive_commits, &mc));
 132         git_vector_set_cmp(&mc.commits, commit_id_cmp);
 133         git_vector_sort(&mc.commits);
 134         cl_git_pass(git_bitvec_init(
 135                         &reachable,
 136                         git_vector_length(&mc.commits) * git_vector_length(&mc.commits)));
 137
 138         commit_count = git_vector_length(&mc.commits);
 139         git_vector_foreach (&mc.commits, child_idx, child_commit) {
 140                 unsigned int parent_i;
 141
 142                 /* We treat each commit as being able to reach itself. */
 143                 git_bitvec_set(&reachable, child_idx * commit_count + child_idx, true);
 144
 145                 for (parent_i = 0; parent_i < git_commit_parentcount(child_commit); ++parent_i) {
 146                         size_t parent_idx = -1;
 147                         cl_git_pass(git_vector_bsearch2(
 148                                         &parent_idx,
 149                                         &mc.commits,
 150                                         id_commit_id_cmp,
 151                                         git_commit_parent_id(child_commit, parent_i)));
 152
 153                         /* We have established that parent_idx is reachable from child_idx */
 154                         git_bitvec_set(&reachable, parent_idx * commit_count + child_idx, true);
 155                 }
 156         }
 157
 158         /* Floyd-Warshall */
 159         {
 160                 size_t i, j, k;
 161                 for (k = 0; k < commit_count; ++k) {
 162                         for (i = 0; i < commit_count; ++i) {
 163                                 if (!git_bitvec_get(&reachable, i * commit_count + k))
 164                                         continue;
 165                                 for (j = 0; j < commit_count; ++j) {
 166                                         if (!git_bitvec_get(&reachable, k * commit_count + j))
 167                                                 continue;
 168                                         git_bitvec_set(&reachable, i * commit_count + j, true);
 169                                 }
 170                         }
 171                 }
 172         }
 173
 174         /* Try 1000 subsets of 1 through 10 entries each. */
 175         srand(0x223ddc4b);
 176         for (n_descendants = 1; n_descendants < 10; ++n_descendants) {
 177                 size_t test_iteration;
 178                 git_oid descendants[10];
 179
 180                 for (test_iteration = 0; test_iteration < 1000; ++test_iteration) {
 181                         size_t descendant_i;
 182                         size_t child_idx, parent_idx;
 183                         int expected_reachable = false, actual_reachable;
 184                         git_commit *child_commit, *parent_commit;
 185
 186                         parent_idx = rand() % commit_count;
 187                         parent_commit = (git_commit *)git_vector_get(&mc.commits, parent_idx);
 188                         for (descendant_i = 0; descendant_i < n_descendants; ++descendant_i) {
 189                                 child_idx = rand() % commit_count;
 190                                 child_commit = (git_commit *)git_vector_get(&mc.commits, child_idx);
 191                                 expected_reachable |= git_bitvec_get(
 192                                                 &reachable, parent_idx * commit_count + child_idx);
 193                                 git_oid_cpy(&descendants[descendant_i],
 194                                             git_commit_id(child_commit));
 195                         }
 196
 197                         actual_reachable = git_graph_reachable_from_any(
 198                                         repo,
 199                                         git_commit_id(parent_commit),
 200                                         descendants,
 201                                         n_descendants);
 202                         if (actual_reachable != expected_reachable) {
 203                                 git_str error_message_buf = GIT_STR_INIT;
 204                                 char parent_oidbuf[9] = {0}, child_oidbuf[9] = {0};
 205
 206                                 cl_git_pass(git_oid_nfmt(
 207                                                 parent_oidbuf, 8, git_commit_id(parent_commit)));
 208                                 git_str_printf(&error_message_buf,
 209                                                "git_graph_reachable_from_any(\"%s\", %zu, "
 210                                                "{",
 211                                                parent_oidbuf,
 212                                                n_descendants);
 213                                 for (descendant_i = 0; descendant_i < n_descendants;
 214                                      ++descendant_i) {
 215                                         cl_git_pass(
 216                                                         git_oid_nfmt(child_oidbuf,
 217                                                                      8,
 218                                                                      &descendants[descendant_i]));
 219                                         git_str_printf(&error_message_buf, " \"%s\"", child_oidbuf);
 220                                 }
 221                                 git_str_printf(&error_message_buf,
 222                                                " }) = %d, expected = %d",
 223                                                actual_reachable,
 224                                                expected_reachable);
 225                                 cl_check_(actual_reachable == expected_reachable,
 226                                           git_str_cstr(&error_message_buf));
 227                         }
 228                 }
 229         }
 230
 231         git_vector_foreach (&mc.commits, child_idx, child_commit)
 232                 git_commit_free(child_commit);
 233         git_bitvec_free(&reachable);
 234         git_vector_free(&mc.commits);
 235         git_odb_free(mc.db);
 236 }