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
interesting(git_pqueue * list,git_commit_list * roots)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
mark_parents(git_revwalk * walk,git_commit_list_node * one,git_commit_list_node * two)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_time_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
ahead_behind(git_commit_list_node * one,git_commit_list_node * two,size_t * ahead,size_t * behind)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
git_graph_ahead_behind(size_t * ahead,size_t * behind,git_repository * repo,const git_oid * local,const git_oid * upstream)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
git_graph_descendant_of(git_repository * repo,const git_oid * commit,const git_oid * ancestor)177 int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor)
178 {
179 git_oid merge_base;
180 int error;
181
182 if (git_oid_equal(commit, ancestor))
183 return 0;
184
185 error = git_merge_base(&merge_base, repo, commit, ancestor);
186 /* No merge-base found, it's not a descendant */
187 if (error == GIT_ENOTFOUND)
188 return 0;
189
190 if (error < 0)
191 return error;
192
193 return git_oid_equal(&merge_base, ancestor);
194 }
195