]>
Commit | Line | Data |
---|---|---|
8f1d2e6f | 1 | #include "cache.h" |
961784ee | 2 | #include "tag.h" |
175785e5 | 3 | #include "commit.h" |
ed09aef0 | 4 | #include "pkt-line.h" |
52883fbd | 5 | #include "utf8.h" |
199c45bf JH |
6 | #include "diff.h" |
7 | #include "revision.h" | |
175785e5 | 8 | |
60ab26de LT |
9 | int save_commit_buffer = 1; |
10 | ||
175785e5 DB |
11 | const char *commit_type = "commit"; |
12 | ||
f76412ed JH |
13 | static struct commit *check_commit(struct object *obj, |
14 | const unsigned char *sha1, | |
15 | int quiet) | |
961784ee | 16 | { |
1974632c | 17 | if (obj->type != OBJ_COMMIT) { |
f76412ed JH |
18 | if (!quiet) |
19 | error("Object %s is a %s, not a commit", | |
885a86ab | 20 | sha1_to_hex(sha1), typename(obj->type)); |
961784ee LT |
21 | return NULL; |
22 | } | |
23 | return (struct commit *) obj; | |
24 | } | |
25 | ||
f76412ed JH |
26 | struct commit *lookup_commit_reference_gently(const unsigned char *sha1, |
27 | int quiet) | |
961784ee | 28 | { |
9534f40b | 29 | struct object *obj = deref_tag(parse_object(sha1), NULL, 0); |
961784ee LT |
30 | |
31 | if (!obj) | |
32 | return NULL; | |
f76412ed JH |
33 | return check_commit(obj, sha1, quiet); |
34 | } | |
35 | ||
36 | struct commit *lookup_commit_reference(const unsigned char *sha1) | |
37 | { | |
38 | return lookup_commit_reference_gently(sha1, 0); | |
961784ee LT |
39 | } |
40 | ||
5d6ccf5c | 41 | struct commit *lookup_commit(const unsigned char *sha1) |
175785e5 DB |
42 | { |
43 | struct object *obj = lookup_object(sha1); | |
100c5f3b LT |
44 | if (!obj) |
45 | return create_object(sha1, OBJ_COMMIT, alloc_commit_node()); | |
d1af002d | 46 | if (!obj->type) |
1974632c | 47 | obj->type = OBJ_COMMIT; |
f76412ed | 48 | return check_commit(obj, sha1, 0); |
175785e5 DB |
49 | } |
50 | ||
0a617799 | 51 | static unsigned long parse_commit_date(const char *buf, const char *tail) |
175785e5 | 52 | { |
0a617799 | 53 | const char *dateptr; |
175785e5 | 54 | |
0a617799 MK |
55 | if (buf + 6 >= tail) |
56 | return 0; | |
175785e5 DB |
57 | if (memcmp(buf, "author", 6)) |
58 | return 0; | |
0a617799 | 59 | while (buf < tail && *buf++ != '\n') |
175785e5 | 60 | /* nada */; |
0a617799 MK |
61 | if (buf + 9 >= tail) |
62 | return 0; | |
175785e5 DB |
63 | if (memcmp(buf, "committer", 9)) |
64 | return 0; | |
0a617799 | 65 | while (buf < tail && *buf++ != '>') |
175785e5 | 66 | /* nada */; |
0a617799 MK |
67 | if (buf >= tail) |
68 | return 0; | |
69 | dateptr = buf; | |
70 | while (buf < tail && *buf++ != '\n') | |
71 | /* nada */; | |
72 | if (buf >= tail) | |
73 | return 0; | |
74 | /* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */ | |
f2909743 | 75 | return strtoul(dateptr, NULL, 10); |
175785e5 DB |
76 | } |
77 | ||
5040f17e | 78 | static struct commit_graft **commit_graft; |
5da5c8f4 JH |
79 | static int commit_graft_alloc, commit_graft_nr; |
80 | ||
81 | static int commit_graft_pos(const unsigned char *sha1) | |
82 | { | |
83 | int lo, hi; | |
84 | lo = 0; | |
85 | hi = commit_graft_nr; | |
86 | while (lo < hi) { | |
87 | int mi = (lo + hi) / 2; | |
88 | struct commit_graft *graft = commit_graft[mi]; | |
a89fccd2 | 89 | int cmp = hashcmp(sha1, graft->sha1); |
5da5c8f4 JH |
90 | if (!cmp) |
91 | return mi; | |
92 | if (cmp < 0) | |
93 | hi = mi; | |
94 | else | |
95 | lo = mi + 1; | |
96 | } | |
97 | return -lo - 1; | |
98 | } | |
99 | ||
5040f17e JH |
100 | int register_commit_graft(struct commit_graft *graft, int ignore_dups) |
101 | { | |
102 | int pos = commit_graft_pos(graft->sha1); | |
a6080a0a | 103 | |
5040f17e JH |
104 | if (0 <= pos) { |
105 | if (ignore_dups) | |
106 | free(graft); | |
107 | else { | |
108 | free(commit_graft[pos]); | |
109 | commit_graft[pos] = graft; | |
110 | } | |
111 | return 1; | |
112 | } | |
113 | pos = -pos - 1; | |
114 | if (commit_graft_alloc <= ++commit_graft_nr) { | |
115 | commit_graft_alloc = alloc_nr(commit_graft_alloc); | |
116 | commit_graft = xrealloc(commit_graft, | |
117 | sizeof(*commit_graft) * | |
118 | commit_graft_alloc); | |
119 | } | |
120 | if (pos < commit_graft_nr) | |
121 | memmove(commit_graft + pos + 1, | |
122 | commit_graft + pos, | |
123 | (commit_graft_nr - pos - 1) * | |
124 | sizeof(*commit_graft)); | |
125 | commit_graft[pos] = graft; | |
126 | return 0; | |
127 | } | |
128 | ||
129 | struct commit_graft *read_graft_line(char *buf, int len) | |
130 | { | |
131 | /* The format is just "Commit Parent1 Parent2 ...\n" */ | |
132 | int i; | |
133 | struct commit_graft *graft = NULL; | |
134 | ||
135 | if (buf[len-1] == '\n') | |
136 | buf[--len] = 0; | |
360204c3 | 137 | if (buf[0] == '#' || buf[0] == '\0') |
5bc4ce58 | 138 | return NULL; |
5040f17e JH |
139 | if ((len + 1) % 41) { |
140 | bad_graft_data: | |
141 | error("bad graft data: %s", buf); | |
142 | free(graft); | |
143 | return NULL; | |
144 | } | |
145 | i = (len + 1) / 41 - 1; | |
146 | graft = xmalloc(sizeof(*graft) + 20 * i); | |
147 | graft->nr_parent = i; | |
148 | if (get_sha1_hex(buf, graft->sha1)) | |
149 | goto bad_graft_data; | |
150 | for (i = 40; i < len; i += 41) { | |
151 | if (buf[i] != ' ') | |
152 | goto bad_graft_data; | |
153 | if (get_sha1_hex(buf + i + 1, graft->parent[i/41])) | |
154 | goto bad_graft_data; | |
155 | } | |
156 | return graft; | |
157 | } | |
158 | ||
c5ae6439 | 159 | static int read_graft_file(const char *graft_file) |
5da5c8f4 | 160 | { |
5da5c8f4 JH |
161 | FILE *fp = fopen(graft_file, "r"); |
162 | char buf[1024]; | |
5040f17e JH |
163 | if (!fp) |
164 | return -1; | |
5da5c8f4 JH |
165 | while (fgets(buf, sizeof(buf), fp)) { |
166 | /* The format is just "Commit Parent1 Parent2 ...\n" */ | |
167 | int len = strlen(buf); | |
5040f17e | 168 | struct commit_graft *graft = read_graft_line(buf, len); |
5bc4ce58 JH |
169 | if (!graft) |
170 | continue; | |
5040f17e | 171 | if (register_commit_graft(graft, 1)) |
5da5c8f4 | 172 | error("duplicate graft data: %s", buf); |
5da5c8f4 JH |
173 | } |
174 | fclose(fp); | |
5040f17e JH |
175 | return 0; |
176 | } | |
177 | ||
178 | static void prepare_commit_graft(void) | |
179 | { | |
180 | static int commit_graft_prepared; | |
181 | char *graft_file; | |
182 | ||
183 | if (commit_graft_prepared) | |
184 | return; | |
185 | graft_file = get_graft_file(); | |
186 | read_graft_file(graft_file); | |
ed09aef0 JS |
187 | /* make sure shallows are read */ |
188 | is_repository_shallow(); | |
5040f17e | 189 | commit_graft_prepared = 1; |
5da5c8f4 JH |
190 | } |
191 | ||
45163382 | 192 | struct commit_graft *lookup_commit_graft(const unsigned char *sha1) |
5da5c8f4 JH |
193 | { |
194 | int pos; | |
5040f17e | 195 | prepare_commit_graft(); |
5da5c8f4 JH |
196 | pos = commit_graft_pos(sha1); |
197 | if (pos < 0) | |
198 | return NULL; | |
199 | return commit_graft[pos]; | |
200 | } | |
201 | ||
ed09aef0 JS |
202 | int write_shallow_commits(int fd, int use_pack_protocol) |
203 | { | |
204 | int i, count = 0; | |
205 | for (i = 0; i < commit_graft_nr; i++) | |
206 | if (commit_graft[i]->nr_parent < 0) { | |
207 | const char *hex = | |
208 | sha1_to_hex(commit_graft[i]->sha1); | |
209 | count++; | |
210 | if (use_pack_protocol) | |
211 | packet_write(fd, "shallow %s", hex); | |
212 | else { | |
93822c22 AW |
213 | if (write_in_full(fd, hex, 40) != 40) |
214 | break; | |
215 | if (write_in_full(fd, "\n", 1) != 1) | |
216 | break; | |
ed09aef0 JS |
217 | } |
218 | } | |
219 | return count; | |
220 | } | |
221 | ||
f53514bc JS |
222 | int unregister_shallow(const unsigned char *sha1) |
223 | { | |
224 | int pos = commit_graft_pos(sha1); | |
225 | if (pos < 0) | |
226 | return -1; | |
227 | if (pos + 1 < commit_graft_nr) | |
228 | memcpy(commit_graft + pos, commit_graft + pos + 1, | |
229 | sizeof(struct commit_graft *) | |
230 | * (commit_graft_nr - pos - 1)); | |
231 | commit_graft_nr--; | |
232 | return 0; | |
233 | } | |
234 | ||
bd2c39f5 | 235 | int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size) |
175785e5 | 236 | { |
3b44f15a | 237 | char *tail = buffer; |
f7cc77d7 | 238 | char *bufptr = buffer; |
175785e5 | 239 | unsigned char parent[20]; |
6c88be16 | 240 | struct commit_list **pptr; |
5da5c8f4 | 241 | struct commit_graft *graft; |
bd2c39f5 | 242 | |
175785e5 DB |
243 | if (item->object.parsed) |
244 | return 0; | |
245 | item->object.parsed = 1; | |
3b44f15a | 246 | tail += size; |
0a617799 | 247 | if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n') |
f7cc77d7 | 248 | return error("bogus commit object %s", sha1_to_hex(item->object.sha1)); |
0a617799 | 249 | if (get_sha1_hex(bufptr + 5, parent) < 0) |
bd2afde8 JH |
250 | return error("bad tree pointer in commit %s", |
251 | sha1_to_hex(item->object.sha1)); | |
175785e5 | 252 | item->tree = lookup_tree(parent); |
175785e5 | 253 | bufptr += 46; /* "tree " + "hex sha1" + "\n" */ |
6c88be16 | 254 | pptr = &item->parents; |
5da5c8f4 JH |
255 | |
256 | graft = lookup_commit_graft(item->object.sha1); | |
3b44f15a | 257 | while (bufptr + 48 < tail && !memcmp(bufptr, "parent ", 7)) { |
f7cc77d7 LT |
258 | struct commit *new_parent; |
259 | ||
3b44f15a JH |
260 | if (tail <= bufptr + 48 || |
261 | get_sha1_hex(bufptr + 7, parent) || | |
262 | bufptr[47] != '\n') | |
f7cc77d7 | 263 | return error("bad parents in commit %s", sha1_to_hex(item->object.sha1)); |
5da5c8f4 JH |
264 | bufptr += 48; |
265 | if (graft) | |
266 | continue; | |
f7cc77d7 | 267 | new_parent = lookup_commit(parent); |
39468def | 268 | if (new_parent) |
6c88be16 | 269 | pptr = &commit_list_insert(new_parent, pptr)->next; |
5da5c8f4 JH |
270 | } |
271 | if (graft) { | |
272 | int i; | |
273 | struct commit *new_parent; | |
274 | for (i = 0; i < graft->nr_parent; i++) { | |
275 | new_parent = lookup_commit(graft->parent[i]); | |
276 | if (!new_parent) | |
277 | continue; | |
278 | pptr = &commit_list_insert(new_parent, pptr)->next; | |
5da5c8f4 | 279 | } |
175785e5 | 280 | } |
0a617799 | 281 | item->date = parse_commit_date(bufptr, tail); |
27dedf0c | 282 | |
175785e5 DB |
283 | return 0; |
284 | } | |
285 | ||
bd2c39f5 NP |
286 | int parse_commit(struct commit *item) |
287 | { | |
21666f1a | 288 | enum object_type type; |
bd2c39f5 NP |
289 | void *buffer; |
290 | unsigned long size; | |
291 | int ret; | |
292 | ||
9786f68b MK |
293 | if (!item) |
294 | return -1; | |
bd2c39f5 NP |
295 | if (item->object.parsed) |
296 | return 0; | |
21666f1a | 297 | buffer = read_sha1_file(item->object.sha1, &type, &size); |
bd2c39f5 NP |
298 | if (!buffer) |
299 | return error("Could not read %s", | |
300 | sha1_to_hex(item->object.sha1)); | |
21666f1a | 301 | if (type != OBJ_COMMIT) { |
bd2c39f5 NP |
302 | free(buffer); |
303 | return error("Object %s not a commit", | |
304 | sha1_to_hex(item->object.sha1)); | |
305 | } | |
306 | ret = parse_commit_buffer(item, buffer, size); | |
60ab26de | 307 | if (save_commit_buffer && !ret) { |
3ff1fbbb LT |
308 | item->buffer = buffer; |
309 | return 0; | |
310 | } | |
bd2c39f5 NP |
311 | free(buffer); |
312 | return ret; | |
313 | } | |
314 | ||
ac5155ef | 315 | struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p) |
dd97f850 | 316 | { |
812666c8 | 317 | struct commit_list *new_list = xmalloc(sizeof(struct commit_list)); |
dd97f850 DB |
318 | new_list->item = item; |
319 | new_list->next = *list_p; | |
320 | *list_p = new_list; | |
ac5155ef | 321 | return new_list; |
dd97f850 DB |
322 | } |
323 | ||
65319475 MV |
324 | unsigned commit_list_count(const struct commit_list *l) |
325 | { | |
326 | unsigned c = 0; | |
327 | for (; l; l = l->next ) | |
328 | c++; | |
329 | return c; | |
330 | } | |
331 | ||
175785e5 DB |
332 | void free_commit_list(struct commit_list *list) |
333 | { | |
334 | while (list) { | |
335 | struct commit_list *temp = list; | |
336 | list = temp->next; | |
337 | free(temp); | |
338 | } | |
339 | } | |
dd97f850 | 340 | |
f755494c | 341 | struct commit_list * insert_by_date(struct commit *item, struct commit_list **list) |
dd97f850 DB |
342 | { |
343 | struct commit_list **pp = list; | |
344 | struct commit_list *p; | |
345 | while ((p = *pp) != NULL) { | |
346 | if (p->item->date < item->date) { | |
347 | break; | |
348 | } | |
349 | pp = &p->next; | |
350 | } | |
f755494c | 351 | return commit_list_insert(item, pp); |
dd97f850 DB |
352 | } |
353 | ||
a6080a0a | 354 | |
dd97f850 DB |
355 | void sort_by_date(struct commit_list **list) |
356 | { | |
357 | struct commit_list *ret = NULL; | |
358 | while (*list) { | |
f755494c | 359 | insert_by_date((*list)->item, &ret); |
dd97f850 DB |
360 | *list = (*list)->next; |
361 | } | |
362 | *list = ret; | |
363 | } | |
364 | ||
58e28af6 DB |
365 | struct commit *pop_most_recent_commit(struct commit_list **list, |
366 | unsigned int mark) | |
dd97f850 DB |
367 | { |
368 | struct commit *ret = (*list)->item; | |
369 | struct commit_list *parents = ret->parents; | |
370 | struct commit_list *old = *list; | |
371 | ||
372 | *list = (*list)->next; | |
373 | free(old); | |
374 | ||
375 | while (parents) { | |
4056c091 | 376 | struct commit *commit = parents->item; |
dec38c81 | 377 | if (!parse_commit(commit) && !(commit->object.flags & mark)) { |
58e28af6 | 378 | commit->object.flags |= mark; |
f755494c | 379 | insert_by_date(commit, list); |
4056c091 | 380 | } |
dd97f850 DB |
381 | parents = parents->next; |
382 | } | |
383 | return ret; | |
384 | } | |
e3bc7a3b | 385 | |
f8f9c73c JH |
386 | void clear_commit_marks(struct commit *commit, unsigned int mark) |
387 | { | |
60fcc2e6 JS |
388 | while (commit) { |
389 | struct commit_list *parents; | |
f8f9c73c | 390 | |
60fcc2e6 JS |
391 | if (!(mark & commit->object.flags)) |
392 | return; | |
58ecf5c1 | 393 | |
60fcc2e6 JS |
394 | commit->object.flags &= ~mark; |
395 | ||
396 | parents = commit->parents; | |
397 | if (!parents) | |
398 | return; | |
399 | ||
400 | while ((parents = parents->next)) | |
401 | clear_commit_marks(parents->item, mark); | |
402 | ||
403 | commit = commit->parents->item; | |
f8f9c73c JH |
404 | } |
405 | } | |
406 | ||
a3437b8c JS |
407 | struct commit *pop_commit(struct commit_list **stack) |
408 | { | |
409 | struct commit_list *top = *stack; | |
410 | struct commit *item = top ? top->item : NULL; | |
411 | ||
412 | if (top) { | |
413 | *stack = top->next; | |
414 | free(top); | |
415 | } | |
416 | return item; | |
417 | } | |
418 | ||
ab580ace JS |
419 | /* |
420 | * Performs an in-place topological sort on the list supplied. | |
421 | */ | |
4c8725f1 | 422 | void sort_in_topological_order(struct commit_list ** list, int lifo) |
6b6dcfc2 | 423 | { |
23c17d4a LT |
424 | struct commit_list *next, *orig = *list; |
425 | struct commit_list *work, **insert; | |
426 | struct commit_list **pptr; | |
a6080a0a | 427 | |
23c17d4a | 428 | if (!orig) |
7d6fb370 | 429 | return; |
23c17d4a LT |
430 | *list = NULL; |
431 | ||
432 | /* Mark them and clear the indegree */ | |
433 | for (next = orig; next; next = next->next) { | |
434 | struct commit *commit = next->item; | |
e358f3c3 | 435 | commit->indegree = 1; |
ab580ace | 436 | } |
23c17d4a | 437 | |
ab580ace | 438 | /* update the indegree */ |
23c17d4a | 439 | for (next = orig; next; next = next->next) { |
ab580ace JS |
440 | struct commit_list * parents = next->item->parents; |
441 | while (parents) { | |
23c17d4a | 442 | struct commit *parent = parents->item; |
6b6dcfc2 | 443 | |
e358f3c3 | 444 | if (parent->indegree) |
23c17d4a LT |
445 | parent->indegree++; |
446 | parents = parents->next; | |
ab580ace | 447 | } |
ab580ace | 448 | } |
23c17d4a | 449 | |
a6080a0a | 450 | /* |
674d1727 PH |
451 | * find the tips |
452 | * | |
453 | * tips are nodes not reachable from any other node in the list | |
454 | * | |
455 | * the tips serve as a starting set for the work queue. | |
456 | */ | |
23c17d4a | 457 | work = NULL; |
2ed02887 | 458 | insert = &work; |
23c17d4a LT |
459 | for (next = orig; next; next = next->next) { |
460 | struct commit *commit = next->item; | |
ab580ace | 461 | |
e358f3c3 | 462 | if (commit->indegree == 1) |
23c17d4a | 463 | insert = &commit_list_insert(commit, insert)->next; |
ab580ace | 464 | } |
4c8725f1 | 465 | |
ab580ace | 466 | /* process the list in topological order */ |
4c8725f1 JH |
467 | if (!lifo) |
468 | sort_by_date(&work); | |
23c17d4a LT |
469 | |
470 | pptr = list; | |
471 | *list = NULL; | |
ab580ace | 472 | while (work) { |
23c17d4a LT |
473 | struct commit *commit; |
474 | struct commit_list *parents, *work_item; | |
ab580ace | 475 | |
23c17d4a LT |
476 | work_item = work; |
477 | work = work_item->next; | |
478 | work_item->next = NULL; | |
479 | ||
480 | commit = work_item->item; | |
481 | for (parents = commit->parents; parents ; parents = parents->next) { | |
482 | struct commit *parent=parents->item; | |
483 | ||
e358f3c3 | 484 | if (!parent->indegree) |
23c17d4a LT |
485 | continue; |
486 | ||
487 | /* | |
488 | * parents are only enqueued for emission | |
489 | * when all their children have been emitted thereby | |
490 | * guaranteeing topological order. | |
491 | */ | |
e358f3c3 | 492 | if (--parent->indegree == 1) { |
23c17d4a LT |
493 | if (!lifo) |
494 | insert_by_date(parent, &work); | |
495 | else | |
496 | commit_list_insert(parent, &work); | |
ab580ace | 497 | } |
ab580ace JS |
498 | } |
499 | /* | |
674d1727 PH |
500 | * work_item is a commit all of whose children |
501 | * have already been emitted. we can emit it now. | |
502 | */ | |
e358f3c3 | 503 | commit->indegree = 0; |
23c17d4a LT |
504 | *pptr = work_item; |
505 | pptr = &work_item->next; | |
ab580ace | 506 | } |
ab580ace | 507 | } |
7c6f8aaf | 508 | |
1295228d | 509 | /* merge-base stuff */ |
7c6f8aaf | 510 | |
577ed5c2 JH |
511 | /* bits #0..15 in revision.h */ |
512 | #define PARENT1 (1u<<16) | |
513 | #define PARENT2 (1u<<17) | |
514 | #define STALE (1u<<18) | |
515 | #define RESULT (1u<<19) | |
7c6f8aaf | 516 | |
1295228d JH |
517 | static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT); |
518 | ||
7c6f8aaf JS |
519 | static struct commit *interesting(struct commit_list *list) |
520 | { | |
521 | while (list) { | |
522 | struct commit *commit = list->item; | |
523 | list = list->next; | |
542ccefe | 524 | if (commit->object.flags & STALE) |
7c6f8aaf JS |
525 | continue; |
526 | return commit; | |
527 | } | |
528 | return NULL; | |
529 | } | |
530 | ||
6a938648 | 531 | static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos) |
7c6f8aaf JS |
532 | { |
533 | struct commit_list *list = NULL; | |
534 | struct commit_list *result = NULL; | |
6a938648 | 535 | int i; |
7c6f8aaf | 536 | |
6a938648 JH |
537 | for (i = 0; i < n; i++) { |
538 | if (one == twos[i]) | |
539 | /* | |
540 | * We do not mark this even with RESULT so we do not | |
541 | * have to clean it up. | |
542 | */ | |
543 | return commit_list_insert(one, &result); | |
544 | } | |
7c6f8aaf | 545 | |
172947e6 MK |
546 | if (parse_commit(one)) |
547 | return NULL; | |
6a938648 JH |
548 | for (i = 0; i < n; i++) { |
549 | if (parse_commit(twos[i])) | |
550 | return NULL; | |
551 | } | |
7c6f8aaf | 552 | |
f3249438 | 553 | one->object.flags |= PARENT1; |
f3249438 | 554 | insert_by_date(one, &list); |
6a938648 JH |
555 | for (i = 0; i < n; i++) { |
556 | twos[i]->object.flags |= PARENT2; | |
557 | insert_by_date(twos[i], &list); | |
558 | } | |
7c6f8aaf JS |
559 | |
560 | while (interesting(list)) { | |
f3249438 | 561 | struct commit *commit; |
7c6f8aaf | 562 | struct commit_list *parents; |
f3249438 JH |
563 | struct commit_list *n; |
564 | int flags; | |
7c6f8aaf | 565 | |
f3249438 JH |
566 | commit = list->item; |
567 | n = list->next; | |
568 | free(list); | |
569 | list = n; | |
7c6f8aaf | 570 | |
f3249438 JH |
571 | flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); |
572 | if (flags == (PARENT1 | PARENT2)) { | |
573 | if (!(commit->object.flags & RESULT)) { | |
574 | commit->object.flags |= RESULT; | |
575 | insert_by_date(commit, &result); | |
576 | } | |
542ccefe JH |
577 | /* Mark parents of a found merge stale */ |
578 | flags |= STALE; | |
7c6f8aaf JS |
579 | } |
580 | parents = commit->parents; | |
581 | while (parents) { | |
582 | struct commit *p = parents->item; | |
583 | parents = parents->next; | |
584 | if ((p->object.flags & flags) == flags) | |
585 | continue; | |
172947e6 MK |
586 | if (parse_commit(p)) |
587 | return NULL; | |
7c6f8aaf JS |
588 | p->object.flags |= flags; |
589 | insert_by_date(p, &list); | |
590 | } | |
591 | } | |
592 | ||
f3249438 | 593 | /* Clean up the result to remove stale ones */ |
1295228d | 594 | free_commit_list(list); |
f3249438 JH |
595 | list = result; result = NULL; |
596 | while (list) { | |
597 | struct commit_list *n = list->next; | |
598 | if (!(list->item->object.flags & STALE)) | |
599 | insert_by_date(list->item, &result); | |
600 | free(list); | |
601 | list = n; | |
602 | } | |
603 | return result; | |
604 | } | |
7c6f8aaf | 605 | |
5240c9d7 MV |
606 | struct commit_list *get_octopus_merge_bases(struct commit_list *in) |
607 | { | |
608 | struct commit_list *i, *j, *k, *ret = NULL; | |
609 | struct commit_list **pptr = &ret; | |
610 | ||
611 | for (i = in; i; i = i->next) { | |
612 | if (!ret) | |
613 | pptr = &commit_list_insert(i->item, pptr)->next; | |
614 | else { | |
615 | struct commit_list *new = NULL, *end = NULL; | |
616 | ||
617 | for (j = ret; j; j = j->next) { | |
618 | struct commit_list *bases; | |
619 | bases = get_merge_bases(i->item, j->item, 1); | |
620 | if (!new) | |
621 | new = bases; | |
622 | else | |
623 | end->next = bases; | |
624 | for (k = bases; k; k = k->next) | |
625 | end = k; | |
626 | } | |
627 | ret = new; | |
628 | } | |
629 | } | |
630 | return ret; | |
631 | } | |
632 | ||
6a938648 JH |
633 | struct commit_list *get_merge_bases_many(struct commit *one, |
634 | int n, | |
635 | struct commit **twos, | |
636 | int cleanup) | |
f3249438 | 637 | { |
f3249438 JH |
638 | struct commit_list *list; |
639 | struct commit **rslt; | |
640 | struct commit_list *result; | |
641 | int cnt, i, j; | |
642 | ||
6a938648 JH |
643 | result = merge_bases_many(one, n, twos); |
644 | for (i = 0; i < n; i++) { | |
645 | if (one == twos[i]) | |
646 | return result; | |
647 | } | |
f3249438 JH |
648 | if (!result || !result->next) { |
649 | if (cleanup) { | |
650 | clear_commit_marks(one, all_flags); | |
6a938648 JH |
651 | for (i = 0; i < n; i++) |
652 | clear_commit_marks(twos[i], all_flags); | |
7c6f8aaf | 653 | } |
f3249438 | 654 | return result; |
7c6f8aaf JS |
655 | } |
656 | ||
f3249438 JH |
657 | /* There are more than one */ |
658 | cnt = 0; | |
659 | list = result; | |
660 | while (list) { | |
661 | list = list->next; | |
662 | cnt++; | |
663 | } | |
664 | rslt = xcalloc(cnt, sizeof(*rslt)); | |
665 | for (list = result, i = 0; list; list = list->next) | |
666 | rslt[i++] = list->item; | |
667 | free_commit_list(result); | |
668 | ||
669 | clear_commit_marks(one, all_flags); | |
6a938648 JH |
670 | for (i = 0; i < n; i++) |
671 | clear_commit_marks(twos[i], all_flags); | |
f3249438 JH |
672 | for (i = 0; i < cnt - 1; i++) { |
673 | for (j = i+1; j < cnt; j++) { | |
674 | if (!rslt[i] || !rslt[j]) | |
675 | continue; | |
6a938648 | 676 | result = merge_bases_many(rslt[i], 1, &rslt[j]); |
f3249438 JH |
677 | clear_commit_marks(rslt[i], all_flags); |
678 | clear_commit_marks(rslt[j], all_flags); | |
679 | for (list = result; list; list = list->next) { | |
680 | if (rslt[i] == list->item) | |
681 | rslt[i] = NULL; | |
682 | if (rslt[j] == list->item) | |
683 | rslt[j] = NULL; | |
684 | } | |
685 | } | |
58ecf5c1 | 686 | } |
7c6f8aaf | 687 | |
f3249438 JH |
688 | /* Surviving ones in rslt[] are the independent results */ |
689 | result = NULL; | |
690 | for (i = 0; i < cnt; i++) { | |
691 | if (rslt[i]) | |
692 | insert_by_date(rslt[i], &result); | |
693 | } | |
694 | free(rslt); | |
7c6f8aaf JS |
695 | return result; |
696 | } | |
2ecd2bbc | 697 | |
6a938648 JH |
698 | struct commit_list *get_merge_bases(struct commit *one, struct commit *two, |
699 | int cleanup) | |
700 | { | |
701 | return get_merge_bases_many(one, 1, &two, cleanup); | |
702 | } | |
703 | ||
7fcdb36e JG |
704 | int is_descendant_of(struct commit *commit, struct commit_list *with_commit) |
705 | { | |
706 | if (!with_commit) | |
707 | return 1; | |
708 | while (with_commit) { | |
709 | struct commit *other; | |
710 | ||
711 | other = with_commit->item; | |
712 | with_commit = with_commit->next; | |
713 | if (in_merge_bases(other, &commit, 1)) | |
714 | return 1; | |
715 | } | |
716 | return 0; | |
717 | } | |
718 | ||
03840fc3 | 719 | int in_merge_bases(struct commit *commit, struct commit **reference, int num) |
2ecd2bbc JH |
720 | { |
721 | struct commit_list *bases, *b; | |
722 | int ret = 0; | |
723 | ||
03840fc3 JH |
724 | if (num == 1) |
725 | bases = get_merge_bases(commit, *reference, 1); | |
726 | else | |
727 | die("not yet"); | |
2ecd2bbc | 728 | for (b = bases; b; b = b->next) { |
03840fc3 | 729 | if (!hashcmp(commit->object.sha1, b->item->object.sha1)) { |
2ecd2bbc JH |
730 | ret = 1; |
731 | break; | |
732 | } | |
733 | } | |
734 | ||
735 | free_commit_list(bases); | |
736 | return ret; | |
737 | } | |
98cf9c3b JH |
738 | |
739 | struct commit_list *reduce_heads(struct commit_list *heads) | |
740 | { | |
741 | struct commit_list *p; | |
742 | struct commit_list *result = NULL, **tail = &result; | |
743 | struct commit **other; | |
744 | size_t num_head, num_other; | |
745 | ||
746 | if (!heads) | |
747 | return NULL; | |
748 | ||
749 | /* Avoid unnecessary reallocations */ | |
750 | for (p = heads, num_head = 0; p; p = p->next) | |
751 | num_head++; | |
752 | other = xcalloc(sizeof(*other), num_head); | |
753 | ||
754 | /* For each commit, see if it can be reached by others */ | |
755 | for (p = heads; p; p = p->next) { | |
756 | struct commit_list *q, *base; | |
757 | ||
711f6b29 JH |
758 | /* Do we already have this in the result? */ |
759 | for (q = result; q; q = q->next) | |
760 | if (p->item == q->item) | |
761 | break; | |
762 | if (q) | |
763 | continue; | |
764 | ||
98cf9c3b JH |
765 | num_other = 0; |
766 | for (q = heads; q; q = q->next) { | |
3d1dd472 | 767 | if (p->item == q->item) |
98cf9c3b JH |
768 | continue; |
769 | other[num_other++] = q->item; | |
770 | } | |
711f6b29 | 771 | if (num_other) |
98cf9c3b | 772 | base = get_merge_bases_many(p->item, num_other, other, 1); |
711f6b29 | 773 | else |
98cf9c3b JH |
774 | base = NULL; |
775 | /* | |
776 | * If p->item does not have anything common with other | |
777 | * commits, there won't be any merge base. If it is | |
778 | * reachable from some of the others, p->item will be | |
779 | * the merge base. If its history is connected with | |
780 | * others, but p->item is not reachable by others, we | |
781 | * will get something other than p->item back. | |
782 | */ | |
783 | if (!base || (base->item != p->item)) | |
784 | tail = &(commit_list_insert(p->item, tail)->next); | |
785 | free_commit_list(base); | |
786 | } | |
787 | free(other); | |
788 | return result; | |
789 | } |