]>
Commit | Line | Data |
---|---|---|
0984c876 | 1 | /* |
359fc2d2 | 2 | * Copyright (C) the libgit2 contributors. All rights reserved. |
0984c876 SG |
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 | ||
eae0bfdc PP |
8 | #include "common.h" |
9 | ||
0984c876 | 10 | #include "revwalk.h" |
0984c876 | 11 | #include "merge.h" |
0984c876 SG |
12 | #include "git2/graph.h" |
13 | ||
e51c8b99 | 14 | static int interesting(git_pqueue *list, git_commit_list *roots) |
a3a81ae5 SG |
15 | { |
16 | unsigned int i; | |
4075e060 RB |
17 | |
18 | for (i = 0; i < git_pqueue_size(list); i++) { | |
19 | git_commit_list_node *commit = git_pqueue_get(list, i); | |
a3a81ae5 SG |
20 | if ((commit->flags & STALE) == 0) |
21 | return 1; | |
22 | } | |
23 | ||
e51c8b99 SG |
24 | while(roots) { |
25 | if ((roots->item->flags & STALE) == 0) | |
26 | return 1; | |
27 | roots = roots->next; | |
28 | } | |
29 | ||
a3a81ae5 SG |
30 | return 0; |
31 | } | |
32 | ||
9c2a4e8c SG |
33 | static int mark_parents(git_revwalk *walk, git_commit_list_node *one, |
34 | git_commit_list_node *two) | |
a3a81ae5 | 35 | { |
a3a81ae5 | 36 | unsigned int i; |
e51c8b99 | 37 | git_commit_list *roots = NULL; |
a3a81ae5 SG |
38 | git_pqueue list; |
39 | ||
40 | /* if the commit is repeated, we have a our merge base already */ | |
9c2a4e8c SG |
41 | if (one == two) { |
42 | one->flags |= PARENT1 | PARENT2 | RESULT; | |
43 | return 0; | |
a3a81ae5 SG |
44 | } |
45 | ||
c25aa7cd | 46 | if (git_pqueue_init(&list, 0, 2, git_commit_list_generation_cmp) < 0) |
a3a81ae5 SG |
47 | return -1; |
48 | ||
49 | if (git_commit_list_parse(walk, one) < 0) | |
7d26c410 | 50 | goto on_error; |
a3a81ae5 SG |
51 | one->flags |= PARENT1; |
52 | if (git_pqueue_insert(&list, one) < 0) | |
7d26c410 | 53 | goto on_error; |
a3a81ae5 | 54 | |
9c2a4e8c | 55 | if (git_commit_list_parse(walk, two) < 0) |
7d26c410 | 56 | goto on_error; |
9c2a4e8c SG |
57 | two->flags |= PARENT2; |
58 | if (git_pqueue_insert(&list, two) < 0) | |
7d26c410 | 59 | goto on_error; |
a3a81ae5 SG |
60 | |
61 | /* as long as there are non-STALE commits */ | |
e51c8b99 | 62 | while (interesting(&list, roots)) { |
4075e060 | 63 | git_commit_list_node *commit = git_pqueue_pop(&list); |
e781a0c5 | 64 | unsigned int flags; |
a3a81ae5 | 65 | |
e51c8b99 SG |
66 | if (commit == NULL) |
67 | break; | |
a3a81ae5 SG |
68 | |
69 | flags = commit->flags & (PARENT1 | PARENT2 | STALE); | |
70 | if (flags == (PARENT1 | PARENT2)) { | |
9c2a4e8c | 71 | if (!(commit->flags & RESULT)) |
a3a81ae5 | 72 | commit->flags |= RESULT; |
a3a81ae5 SG |
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 | ||
7d26c410 SG |
82 | if (git_commit_list_parse(walk, p) < 0) |
83 | goto on_error; | |
a3a81ae5 SG |
84 | |
85 | p->flags |= flags; | |
86 | if (git_pqueue_insert(&list, p) < 0) | |
7d26c410 | 87 | goto on_error; |
a3a81ae5 | 88 | } |
e51c8b99 | 89 | |
7d26c410 | 90 | /* Keep track of root commits, to make sure the path gets marked */ |
e51c8b99 SG |
91 | if (commit->out_degree == 0) { |
92 | if (git_commit_list_insert(commit, &roots) == NULL) | |
7d26c410 | 93 | goto on_error; |
e51c8b99 | 94 | } |
a3a81ae5 SG |
95 | } |
96 | ||
7d26c410 | 97 | git_commit_list_free(&roots); |
a3a81ae5 | 98 | git_pqueue_free(&list); |
a3a81ae5 | 99 | return 0; |
7d26c410 SG |
100 | |
101 | on_error: | |
102 | git_commit_list_free(&roots); | |
103 | git_pqueue_free(&list); | |
104 | return -1; | |
a3a81ae5 SG |
105 | } |
106 | ||
9c2a4e8c | 107 | |
0984c876 SG |
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; | |
4075e060 | 113 | int error = 0, i; |
0984c876 SG |
114 | *ahead = 0; |
115 | *behind = 0; | |
116 | ||
4075e060 | 117 | if (git_pqueue_init(&pq, 0, 2, git_commit_list_time_cmp) < 0) |
0984c876 | 118 | return -1; |
4075e060 RB |
119 | |
120 | if ((error = git_pqueue_insert(&pq, one)) < 0 || | |
121 | (error = git_pqueue_insert(&pq, two)) < 0) | |
122 | goto done; | |
0984c876 SG |
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) | |
0984c876 | 129 | (*ahead)++; |
05f0d0c1 CMN |
130 | else if (commit->flags & PARENT2) |
131 | (*behind)++; | |
0984c876 SG |
132 | |
133 | for (i = 0; i < commit->out_degree; i++) { | |
134 | git_commit_list_node *p = commit->parents[i]; | |
4075e060 RB |
135 | if ((error = git_pqueue_insert(&pq, p)) < 0) |
136 | goto done; | |
0984c876 SG |
137 | } |
138 | commit->flags |= RESULT; | |
139 | } | |
140 | ||
4075e060 | 141 | done: |
da820437 | 142 | git_pqueue_free(&pq); |
4075e060 | 143 | return error; |
0984c876 SG |
144 | } |
145 | ||
146 | int git_graph_ahead_behind(size_t *ahead, size_t *behind, git_repository *repo, | |
33a59401 | 147 | const git_oid *local, const git_oid *upstream) |
0984c876 SG |
148 | { |
149 | git_revwalk *walk; | |
33a59401 | 150 | git_commit_list_node *commit_u, *commit_l; |
0984c876 SG |
151 | |
152 | if (git_revwalk_new(&walk, repo) < 0) | |
153 | return -1; | |
154 | ||
33a59401 CMN |
155 | commit_u = git_revwalk__commit_lookup(walk, upstream); |
156 | if (commit_u == NULL) | |
0984c876 SG |
157 | goto on_error; |
158 | ||
33a59401 CMN |
159 | commit_l = git_revwalk__commit_lookup(walk, local); |
160 | if (commit_l == NULL) | |
0984c876 SG |
161 | goto on_error; |
162 | ||
33a59401 | 163 | if (mark_parents(walk, commit_l, commit_u) < 0) |
0984c876 | 164 | goto on_error; |
33a59401 | 165 | if (ahead_behind(commit_l, commit_u, ahead, behind) < 0) |
0984c876 SG |
166 | goto on_error; |
167 | ||
0984c876 SG |
168 | git_revwalk_free(walk); |
169 | ||
170 | return 0; | |
171 | ||
172 | on_error: | |
173 | git_revwalk_free(walk); | |
174 | return -1; | |
175 | } | |
e7c16943 AS |
176 | |
177 | int git_graph_descendant_of(git_repository *repo, const git_oid *commit, const git_oid *ancestor) | |
178 | { | |
e7c16943 AS |
179 | if (git_oid_equal(commit, ancestor)) |
180 | return 0; | |
181 | ||
c25aa7cd PP |
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) | |
ce2e8269 CMN |
200 | return 0; |
201 | ||
c25aa7cd PP |
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) | |
e7c16943 AS |
208 | return error; |
209 | ||
c25aa7cd PP |
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; | |
e7c16943 | 249 | } |