src/libgit2/graph.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "common.h"
   9
  10 #include "revwalk.h"
  11 #include "merge.h"
  12 #include "git2/graph.h"
  13
  14 static int interesting(git_pqueue *list, git_commit_list *roots)
  15 {
  16         unsigned int i;
  17
  18         for (i = 0; i < git_pqueue_size(list); i++) {
  19                 git_commit_list_node *commit = git_pqueue_get(list, i);
  20                 if ((commit->flags & STALE) == 0)
  21                         return 1;
  22         }
  23
  24         while(roots) {
  25                 if ((roots->item->flags & STALE) == 0)
  26                         return 1;
  27                 roots = roots->next;
  28         }
  29
  30         return 0;
  31 }
  32
  33 static int mark_parents(git_revwalk *walk, git_commit_list_node *one,
  34         git_commit_list_node *two)
  35 {
  36         unsigned int i;
  37         git_commit_list *roots = NULL;
  38         git_pqueue list;
  39
  40         /* if the commit is repeated, we have a our merge base already */
  41         if (one == two) {
  42                 one->flags |= PARENT1 | PARENT2 | RESULT;
  43                 return 0;
  44         }
  45
  46         if (git_pqueue_init(&list, 0, 2, git_commit_list_generation_cmp) < 0)
  47                 return -1;
  48
  49         if (git_commit_list_parse(walk, one) < 0)
  50                 goto on_error;
  51         one->flags |= PARENT1;
  52         if (git_pqueue_insert(&list, one) < 0)
  53                 goto on_error;
  54
  55         if (git_commit_list_parse(walk, two) < 0)
  56                 goto on_error;
  57         two->flags |= PARENT2;
  58         if (git_pqueue_insert(&list, two) < 0)
  59                 goto on_error;
  60
  61         /* as long as there are non-STALE commits */
  62         while (interesting(&list, roots)) {
  63                 git_commit_list_node *commit = git_pqueue_pop(&list);
  64                 unsigned int flags;
  65
  66                 if (commit == NULL)
  67                         break;
  68
  69                 flags = commit->flags & (PARENT1 | PARENT2 | STALE);
  70                 if (flags == (PARENT1 | PARENT2)) {
  71                         if (!(commit->flags & RESULT))
  72                                 commit->flags |= RESULT;
  73                         /* we mark the parents of a merge stale */
  74                         flags |= STALE;
  75                 }
  76
  77                 for (i = 0; i < commit->out_degree; i++) {
  78                         git_commit_list_node *p = commit->parents[i];
  79                         if ((p->flags & flags) == flags)
  80                                 continue;
  81
  82                         if (git_commit_list_parse(walk, p) < 0)
  83                                 goto on_error;
  84
  85                         p->flags |= flags;
  86                         if (git_pqueue_insert(&list, p) < 0)
  87                                 goto on_error;
  88                 }
  89
  90                 /* Keep track of root commits, to make sure the path gets marked */
  91                 if (commit->out_degree == 0) {
  92                         if (git_commit_list_insert(commit, &roots) == NULL)
  93                                 goto on_error;
  94                 }
  95         }
  96
  97         git_commit_list_free(&roots);
  98         git_pqueue_free(&list);
  99         return 0;
 100
 101 on_error:
 102         git_commit_list_free(&roots);
 103         git_pqueue_free(&list);
 104         return -1;
 105 }
 106
 107
 108 static int ahead_behind(git_commit_list_node *one, git_commit_list_node *two,
 109         size_t *ahead, size_t *behind)
 110 {
 111         git_commit_list_node *commit;
 112         git_pqueue pq;
 113         int error = 0, i;
 114         *ahead = 0;
 115         *behind = 0;
 116
 117         if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0)
 118                 return -1;
 119
 120         if ((error = git_pqueue_insert(&pq, one)) < 0 ||
 121                 (error = git_pqueue_insert(&pq, two)) < 0)
 122                 goto done;
 123
 124         while ((commit = git_pqueue_pop(&pq)) != NULL) {
 125                 if (commit->flags & RESULT ||
 126                         (commit->flags & (PARENT1 | PARENT2)) == (PARENT1 | PARENT2))
 127                         continue;
 128                 else if (commit->flags & PARENT1)
 129                         (*ahead)++;
 130                 else if (commit->flags & PARENT2)
 131                         (*behind)++;
 132
 133                 for (i = 0; i < commit->out_degree; i++) {
 134                         git_commit_list_node *p = commit->parents[i];
 135                         if ((error = git_pqueue_insert(&pq, p)) < 0)
 136                                 goto done;
 137                 }
 138                 commit->flags |= RESULT;
 139         }
 140
 141 done:
 142         git_pqueue_free(&pq);
 143         return error;
 144 }
 145
 146 int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo,
 147         const git_oid *local, const git_oid *upstream)
 148 {
 149         git_revwalk *walk;
 150         git_commit_list_node *commit_u, *commit_l;
 151
 152         if (git_revwalk_new(&walk, repo) < 0)
 153                 return -1;
 154
 155         commit_u = git_revwalk__commit_lookup(walk, upstream);
 156         if (commit_u == NULL)
 157                 goto on_error;
 158
 159         commit_l = git_revwalk__commit_lookup(walk, local);
 160         if (commit_l == NULL)
 161                 goto on_error;
 162
 163         if (mark_parents(walk, commit_l, commit_u) < 0)
 164                 goto on_error;
 165         if (ahead_behind(commit_l, commit_u, ahead, behind) < 0)
 166                 goto on_error;
 167
 168         git_revwalk_free(walk);
 169
 170         return 0;
 171
 172 on_error:
 173         git_revwalk_free(walk);
 174         return -1;
 175 }
 176
 177 int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor)
 178 {
 179         if (git_oid_equal(commit, ancestor))
 180                 return 0;
 181
 182         return git_graph_reachable_from_any(repo, ancestor, commit, 1);
 183 }
 184
 185 int git_graph_reachable_from_any(
 186                 git_repository *repo,
 187                 const git_oid *commit_id,
 188                 const git_oid descendant_array[],
 189                 size_t length)
 190 {
 191         git_revwalk *walk = NULL;
 192         git_vector list;
 193         git_commit_list *result = NULL;
 194         git_commit_list_node *commit;
 195         size_t i;
 196         uint32_t minimum_generation = 0xffffffff;
 197         int error = 0;
 198
 199         if (!length)
 200                 return 0;
 201
 202         for (i = 0; i < length; ++i) {
 203                 if (git_oid_equal(commit_id, &descendant_array[i]))
 204                         return 1;
 205         }
 206
 207         if ((error = git_vector_init(&list, length + 1, NULL)) < 0)
 208                 return error;
 209
 210         if ((error = git_revwalk_new(&walk, repo)) < 0)
 211                 goto done;
 212
 213         for (i = 0; i < length; i++) {
 214                 commit = git_revwalk__commit_lookup(walk, &descendant_array[i]);
 215                 if (commit == NULL) {
 216                         error = -1;
 217                         goto done;
 218                 }
 219
 220                 git_vector_insert(&list, commit);
 221                 if (minimum_generation > commit->generation)
 222                         minimum_generation = commit->generation;
 223         }
 224
 225         commit = git_revwalk__commit_lookup(walk, commit_id);
 226         if (commit == NULL) {
 227                 error = -1;
 228                 goto done;
 229         }
 230
 231         if (minimum_generation > commit->generation)
 232                 minimum_generation = commit->generation;
 233
 234         if ((error = git_merge__bases_many(&result, walk, commit, &list, minimum_generation)) < 0)
 235                 goto done;
 236
 237         if (result) {
 238                 error = git_oid_equal(commit_id, &result->item->oid);
 239         } else {
 240                 /* No merge-base found, it's not a descendant */
 241                 error = 0;
 242         }
 243
 244 done:
 245         git_commit_list_free(&result);
 246         git_vector_free(&list);
 247         git_revwalk_free(walk);
 248         return error;
 249 }