commit-reach: move ref_newer from remote.c
[git/git.git] / commit-reach.c
CommitLineData
5227c385 1#include "cache.h"
5227c385 2#include "commit.h"
1d614d41
DS
3#include "decorate.h"
4#include "prio-queue.h"
5#include "tree.h"
6#include "revision.h"
7#include "tag.h"
5227c385
DS
8#include "commit-reach.h"
9
10/* Remember to update object flag allocation in object.h */
11#define PARENT1 (1u<<16)
12#define PARENT2 (1u<<17)
13#define STALE (1u<<18)
14#define RESULT (1u<<19)
15
16static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
17
18static int queue_has_nonstale(struct prio_queue *queue)
19{
20 int i;
21 for (i = 0; i < queue->nr; i++) {
22 struct commit *commit = queue->array[i].data;
23 if (!(commit->object.flags & STALE))
24 return 1;
25 }
26 return 0;
27}
28
29/* all input commits in one and twos[] must have been parsed! */
30static struct commit_list *paint_down_to_common(struct commit *one, int n,
31 struct commit **twos,
32 int min_generation)
33{
34 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
35 struct commit_list *result = NULL;
36 int i;
37 uint32_t last_gen = GENERATION_NUMBER_INFINITY;
38
39 one->object.flags |= PARENT1;
40 if (!n) {
41 commit_list_append(one, &result);
42 return result;
43 }
44 prio_queue_put(&queue, one);
45
46 for (i = 0; i < n; i++) {
47 twos[i]->object.flags |= PARENT2;
48 prio_queue_put(&queue, twos[i]);
49 }
50
51 while (queue_has_nonstale(&queue)) {
52 struct commit *commit = prio_queue_get(&queue);
53 struct commit_list *parents;
54 int flags;
55
56 if (commit->generation > last_gen)
57 BUG("bad generation skip %8x > %8x at %s",
58 commit->generation, last_gen,
59 oid_to_hex(&commit->object.oid));
60 last_gen = commit->generation;
61
62 if (commit->generation < min_generation)
63 break;
64
65 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
66 if (flags == (PARENT1 | PARENT2)) {
67 if (!(commit->object.flags & RESULT)) {
68 commit->object.flags |= RESULT;
69 commit_list_insert_by_date(commit, &result);
70 }
71 /* Mark parents of a found merge stale */
72 flags |= STALE;
73 }
74 parents = commit->parents;
75 while (parents) {
76 struct commit *p = parents->item;
77 parents = parents->next;
78 if ((p->object.flags & flags) == flags)
79 continue;
80 if (parse_commit(p))
81 return NULL;
82 p->object.flags |= flags;
83 prio_queue_put(&queue, p);
84 }
85 }
86
87 clear_prio_queue(&queue);
88 return result;
89}
90
91static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
92{
93 struct commit_list *list = NULL;
94 struct commit_list *result = NULL;
95 int i;
96
97 for (i = 0; i < n; i++) {
98 if (one == twos[i])
99 /*
100 * We do not mark this even with RESULT so we do not
101 * have to clean it up.
102 */
103 return commit_list_insert(one, &result);
104 }
105
106 if (parse_commit(one))
107 return NULL;
108 for (i = 0; i < n; i++) {
109 if (parse_commit(twos[i]))
110 return NULL;
111 }
112
113 list = paint_down_to_common(one, n, twos, 0);
114
115 while (list) {
116 struct commit *commit = pop_commit(&list);
117 if (!(commit->object.flags & STALE))
118 commit_list_insert_by_date(commit, &result);
119 }
120 return result;
121}
122
123struct commit_list *get_octopus_merge_bases(struct commit_list *in)
124{
125 struct commit_list *i, *j, *k, *ret = NULL;
126
127 if (!in)
128 return ret;
129
130 commit_list_insert(in->item, &ret);
131
132 for (i = in->next; i; i = i->next) {
133 struct commit_list *new_commits = NULL, *end = NULL;
134
135 for (j = ret; j; j = j->next) {
136 struct commit_list *bases;
137 bases = get_merge_bases(i->item, j->item);
138 if (!new_commits)
139 new_commits = bases;
140 else
141 end->next = bases;
142 for (k = bases; k; k = k->next)
143 end = k;
144 }
145 ret = new_commits;
146 }
147 return ret;
148}
149
150static int remove_redundant(struct commit **array, int cnt)
151{
152 /*
153 * Some commit in the array may be an ancestor of
154 * another commit. Move such commit to the end of
155 * the array, and return the number of commits that
156 * are independent from each other.
157 */
158 struct commit **work;
159 unsigned char *redundant;
160 int *filled_index;
161 int i, j, filled;
162
163 work = xcalloc(cnt, sizeof(*work));
164 redundant = xcalloc(cnt, 1);
165 ALLOC_ARRAY(filled_index, cnt - 1);
166
167 for (i = 0; i < cnt; i++)
168 parse_commit(array[i]);
169 for (i = 0; i < cnt; i++) {
170 struct commit_list *common;
171 uint32_t min_generation = array[i]->generation;
172
173 if (redundant[i])
174 continue;
175 for (j = filled = 0; j < cnt; j++) {
176 if (i == j || redundant[j])
177 continue;
178 filled_index[filled] = j;
179 work[filled++] = array[j];
180
181 if (array[j]->generation < min_generation)
182 min_generation = array[j]->generation;
183 }
184 common = paint_down_to_common(array[i], filled, work,
185 min_generation);
186 if (array[i]->object.flags & PARENT2)
187 redundant[i] = 1;
188 for (j = 0; j < filled; j++)
189 if (work[j]->object.flags & PARENT1)
190 redundant[filled_index[j]] = 1;
191 clear_commit_marks(array[i], all_flags);
192 clear_commit_marks_many(filled, work, all_flags);
193 free_commit_list(common);
194 }
195
196 /* Now collect the result */
197 COPY_ARRAY(work, array, cnt);
198 for (i = filled = 0; i < cnt; i++)
199 if (!redundant[i])
200 array[filled++] = work[i];
201 for (j = filled, i = 0; i < cnt; i++)
202 if (redundant[i])
203 array[j++] = work[i];
204 free(work);
205 free(redundant);
206 free(filled_index);
207 return filled;
208}
209
210static struct commit_list *get_merge_bases_many_0(struct commit *one,
211 int n,
212 struct commit **twos,
213 int cleanup)
214{
215 struct commit_list *list;
216 struct commit **rslt;
217 struct commit_list *result;
218 int cnt, i;
219
220 result = merge_bases_many(one, n, twos);
221 for (i = 0; i < n; i++) {
222 if (one == twos[i])
223 return result;
224 }
225 if (!result || !result->next) {
226 if (cleanup) {
227 clear_commit_marks(one, all_flags);
228 clear_commit_marks_many(n, twos, all_flags);
229 }
230 return result;
231 }
232
233 /* There are more than one */
234 cnt = commit_list_count(result);
235 rslt = xcalloc(cnt, sizeof(*rslt));
236 for (list = result, i = 0; list; list = list->next)
237 rslt[i++] = list->item;
238 free_commit_list(result);
239
240 clear_commit_marks(one, all_flags);
241 clear_commit_marks_many(n, twos, all_flags);
242
243 cnt = remove_redundant(rslt, cnt);
244 result = NULL;
245 for (i = 0; i < cnt; i++)
246 commit_list_insert_by_date(rslt[i], &result);
247 free(rslt);
248 return result;
249}
250
251struct commit_list *get_merge_bases_many(struct commit *one,
252 int n,
253 struct commit **twos)
254{
255 return get_merge_bases_many_0(one, n, twos, 1);
256}
257
258struct commit_list *get_merge_bases_many_dirty(struct commit *one,
259 int n,
260 struct commit **twos)
261{
262 return get_merge_bases_many_0(one, n, twos, 0);
263}
264
265struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
266{
267 return get_merge_bases_many_0(one, 1, &two, 1);
268}
269
270/*
271 * Is "commit" a descendant of one of the elements on the "with_commit" list?
272 */
273int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
274{
275 if (!with_commit)
276 return 1;
277 while (with_commit) {
278 struct commit *other;
279
280 other = with_commit->item;
281 with_commit = with_commit->next;
282 if (in_merge_bases(other, commit))
283 return 1;
284 }
285 return 0;
286}
287
288/*
289 * Is "commit" an ancestor of one of the "references"?
290 */
291int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
292{
293 struct commit_list *bases;
294 int ret = 0, i;
295 uint32_t min_generation = GENERATION_NUMBER_INFINITY;
296
297 if (parse_commit(commit))
298 return ret;
299 for (i = 0; i < nr_reference; i++) {
300 if (parse_commit(reference[i]))
301 return ret;
302 if (reference[i]->generation < min_generation)
303 min_generation = reference[i]->generation;
304 }
305
306 if (commit->generation > min_generation)
307 return ret;
308
309 bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
310 if (commit->object.flags & PARENT2)
311 ret = 1;
312 clear_commit_marks(commit, all_flags);
313 clear_commit_marks_many(nr_reference, reference, all_flags);
314 free_commit_list(bases);
315 return ret;
316}
317
318/*
319 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
320 */
321int in_merge_bases(struct commit *commit, struct commit *reference)
322{
323 return in_merge_bases_many(commit, 1, &reference);
324}
325
326struct commit_list *reduce_heads(struct commit_list *heads)
327{
328 struct commit_list *p;
329 struct commit_list *result = NULL, **tail = &result;
330 struct commit **array;
331 int num_head, i;
332
333 if (!heads)
334 return NULL;
335
336 /* Uniquify */
337 for (p = heads; p; p = p->next)
338 p->item->object.flags &= ~STALE;
339 for (p = heads, num_head = 0; p; p = p->next) {
340 if (p->item->object.flags & STALE)
341 continue;
342 p->item->object.flags |= STALE;
343 num_head++;
344 }
345 array = xcalloc(num_head, sizeof(*array));
346 for (p = heads, i = 0; p; p = p->next) {
347 if (p->item->object.flags & STALE) {
348 array[i++] = p->item;
349 p->item->object.flags &= ~STALE;
350 }
351 }
352 num_head = remove_redundant(array, num_head);
353 for (i = 0; i < num_head; i++)
354 tail = &commit_list_insert(array[i], tail)->next;
355 free(array);
356 return result;
357}
358
359void reduce_heads_replace(struct commit_list **heads)
360{
361 struct commit_list *result = reduce_heads(*heads);
362 free_commit_list(*heads);
363 *heads = result;
364}
1d614d41
DS
365
366static void unmark_and_free(struct commit_list *list, unsigned int mark)
367{
368 while (list) {
369 struct commit *commit = pop_commit(&list);
370 commit->object.flags &= ~mark;
371 }
372}
373
374int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
375{
376 struct object *o;
377 struct commit *old_commit, *new_commit;
378 struct commit_list *list, *used;
379 int found = 0;
380
381 /*
382 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
383 * old_commit. Otherwise we require --force.
384 */
385 o = deref_tag(the_repository, parse_object(the_repository, old_oid),
386 NULL, 0);
387 if (!o || o->type != OBJ_COMMIT)
388 return 0;
389 old_commit = (struct commit *) o;
390
391 o = deref_tag(the_repository, parse_object(the_repository, new_oid),
392 NULL, 0);
393 if (!o || o->type != OBJ_COMMIT)
394 return 0;
395 new_commit = (struct commit *) o;
396
397 if (parse_commit(new_commit) < 0)
398 return 0;
399
400 used = list = NULL;
401 commit_list_insert(new_commit, &list);
402 while (list) {
403 new_commit = pop_most_recent_commit(&list, TMP_MARK);
404 commit_list_insert(new_commit, &used);
405 if (new_commit == old_commit) {
406 found = 1;
407 break;
408 }
409 }
410 unmark_and_free(list, TMP_MARK);
411 unmark_and_free(used, TMP_MARK);
412 return found;
413}