Merge branch 'maint'
[git] / commit.c
1 #include "cache.h"
2 #include "tag.h"
3 #include "commit.h"
4 #include "pkt-line.h"
5 #include "utf8.h"
6 #include "diff.h"
7 #include "revision.h"
8
9 int save_commit_buffer = 1;
10
11 struct sort_node
12 {
13         /*
14          * the number of children of the associated commit
15          * that also occur in the list being sorted.
16          */
17         unsigned int indegree;
18
19         /*
20          * reference to original list item that we will re-use
21          * on output.
22          */
23         struct commit_list * list_item;
24
25 };
26
27 const char *commit_type = "commit";
28
29 static struct commit *check_commit(struct object *obj,
30                                    const unsigned char *sha1,
31                                    int quiet)
32 {
33         if (obj->type != OBJ_COMMIT) {
34                 if (!quiet)
35                         error("Object %s is a %s, not a commit",
36                               sha1_to_hex(sha1), typename(obj->type));
37                 return NULL;
38         }
39         return (struct commit *) obj;
40 }
41
42 struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
43                                               int quiet)
44 {
45         struct object *obj = deref_tag(parse_object(sha1), NULL, 0);
46
47         if (!obj)
48                 return NULL;
49         return check_commit(obj, sha1, quiet);
50 }
51
52 struct commit *lookup_commit_reference(const unsigned char *sha1)
53 {
54         return lookup_commit_reference_gently(sha1, 0);
55 }
56
57 struct commit *lookup_commit(const unsigned char *sha1)
58 {
59         struct object *obj = lookup_object(sha1);
60         if (!obj)
61                 return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
62         if (!obj->type)
63                 obj->type = OBJ_COMMIT;
64         return check_commit(obj, sha1, 0);
65 }
66
67 static unsigned long parse_commit_date(const char *buf)
68 {
69         unsigned long date;
70
71         if (memcmp(buf, "author", 6))
72                 return 0;
73         while (*buf++ != '\n')
74                 /* nada */;
75         if (memcmp(buf, "committer", 9))
76                 return 0;
77         while (*buf++ != '>')
78                 /* nada */;
79         date = strtoul(buf, NULL, 10);
80         if (date == ULONG_MAX)
81                 date = 0;
82         return date;
83 }
84
85 static struct commit_graft **commit_graft;
86 static int commit_graft_alloc, commit_graft_nr;
87
88 static int commit_graft_pos(const unsigned char *sha1)
89 {
90         int lo, hi;
91         lo = 0;
92         hi = commit_graft_nr;
93         while (lo < hi) {
94                 int mi = (lo + hi) / 2;
95                 struct commit_graft *graft = commit_graft[mi];
96                 int cmp = hashcmp(sha1, graft->sha1);
97                 if (!cmp)
98                         return mi;
99                 if (cmp < 0)
100                         hi = mi;
101                 else
102                         lo = mi + 1;
103         }
104         return -lo - 1;
105 }
106
107 int register_commit_graft(struct commit_graft *graft, int ignore_dups)
108 {
109         int pos = commit_graft_pos(graft->sha1);
110
111         if (0 <= pos) {
112                 if (ignore_dups)
113                         free(graft);
114                 else {
115                         free(commit_graft[pos]);
116                         commit_graft[pos] = graft;
117                 }
118                 return 1;
119         }
120         pos = -pos - 1;
121         if (commit_graft_alloc <= ++commit_graft_nr) {
122                 commit_graft_alloc = alloc_nr(commit_graft_alloc);
123                 commit_graft = xrealloc(commit_graft,
124                                         sizeof(*commit_graft) *
125                                         commit_graft_alloc);
126         }
127         if (pos < commit_graft_nr)
128                 memmove(commit_graft + pos + 1,
129                         commit_graft + pos,
130                         (commit_graft_nr - pos - 1) *
131                         sizeof(*commit_graft));
132         commit_graft[pos] = graft;
133         return 0;
134 }
135
136 struct commit_graft *read_graft_line(char *buf, int len)
137 {
138         /* The format is just "Commit Parent1 Parent2 ...\n" */
139         int i;
140         struct commit_graft *graft = NULL;
141
142         if (buf[len-1] == '\n')
143                 buf[--len] = 0;
144         if (buf[0] == '#' || buf[0] == '\0')
145                 return NULL;
146         if ((len + 1) % 41) {
147         bad_graft_data:
148                 error("bad graft data: %s", buf);
149                 free(graft);
150                 return NULL;
151         }
152         i = (len + 1) / 41 - 1;
153         graft = xmalloc(sizeof(*graft) + 20 * i);
154         graft->nr_parent = i;
155         if (get_sha1_hex(buf, graft->sha1))
156                 goto bad_graft_data;
157         for (i = 40; i < len; i += 41) {
158                 if (buf[i] != ' ')
159                         goto bad_graft_data;
160                 if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
161                         goto bad_graft_data;
162         }
163         return graft;
164 }
165
166 int read_graft_file(const char *graft_file)
167 {
168         FILE *fp = fopen(graft_file, "r");
169         char buf[1024];
170         if (!fp)
171                 return -1;
172         while (fgets(buf, sizeof(buf), fp)) {
173                 /* The format is just "Commit Parent1 Parent2 ...\n" */
174                 int len = strlen(buf);
175                 struct commit_graft *graft = read_graft_line(buf, len);
176                 if (!graft)
177                         continue;
178                 if (register_commit_graft(graft, 1))
179                         error("duplicate graft data: %s", buf);
180         }
181         fclose(fp);
182         return 0;
183 }
184
185 static void prepare_commit_graft(void)
186 {
187         static int commit_graft_prepared;
188         char *graft_file;
189
190         if (commit_graft_prepared)
191                 return;
192         graft_file = get_graft_file();
193         read_graft_file(graft_file);
194         /* make sure shallows are read */
195         is_repository_shallow();
196         commit_graft_prepared = 1;
197 }
198
199 static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
200 {
201         int pos;
202         prepare_commit_graft();
203         pos = commit_graft_pos(sha1);
204         if (pos < 0)
205                 return NULL;
206         return commit_graft[pos];
207 }
208
209 int write_shallow_commits(int fd, int use_pack_protocol)
210 {
211         int i, count = 0;
212         for (i = 0; i < commit_graft_nr; i++)
213                 if (commit_graft[i]->nr_parent < 0) {
214                         const char *hex =
215                                 sha1_to_hex(commit_graft[i]->sha1);
216                         count++;
217                         if (use_pack_protocol)
218                                 packet_write(fd, "shallow %s", hex);
219                         else {
220                                 if (write_in_full(fd, hex,  40) != 40)
221                                         break;
222                                 if (write_in_full(fd, "\n", 1) != 1)
223                                         break;
224                         }
225                 }
226         return count;
227 }
228
229 int unregister_shallow(const unsigned char *sha1)
230 {
231         int pos = commit_graft_pos(sha1);
232         if (pos < 0)
233                 return -1;
234         if (pos + 1 < commit_graft_nr)
235                 memcpy(commit_graft + pos, commit_graft + pos + 1,
236                                 sizeof(struct commit_graft *)
237                                 * (commit_graft_nr - pos - 1));
238         commit_graft_nr--;
239         return 0;
240 }
241
242 int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
243 {
244         char *tail = buffer;
245         char *bufptr = buffer;
246         unsigned char parent[20];
247         struct commit_list **pptr;
248         struct commit_graft *graft;
249         unsigned n_refs = 0;
250
251         if (item->object.parsed)
252                 return 0;
253         item->object.parsed = 1;
254         tail += size;
255         if (tail <= bufptr + 5 || memcmp(bufptr, "tree ", 5))
256                 return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
257         if (tail <= bufptr + 45 || get_sha1_hex(bufptr + 5, parent) < 0)
258                 return error("bad tree pointer in commit %s",
259                              sha1_to_hex(item->object.sha1));
260         item->tree = lookup_tree(parent);
261         if (item->tree)
262                 n_refs++;
263         bufptr += 46; /* "tree " + "hex sha1" + "\n" */
264         pptr = &item->parents;
265
266         graft = lookup_commit_graft(item->object.sha1);
267         while (bufptr + 48 < tail && !memcmp(bufptr, "parent ", 7)) {
268                 struct commit *new_parent;
269
270                 if (tail <= bufptr + 48 ||
271                     get_sha1_hex(bufptr + 7, parent) ||
272                     bufptr[47] != '\n')
273                         return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
274                 bufptr += 48;
275                 if (graft)
276                         continue;
277                 new_parent = lookup_commit(parent);
278                 if (new_parent) {
279                         pptr = &commit_list_insert(new_parent, pptr)->next;
280                         n_refs++;
281                 }
282         }
283         if (graft) {
284                 int i;
285                 struct commit *new_parent;
286                 for (i = 0; i < graft->nr_parent; i++) {
287                         new_parent = lookup_commit(graft->parent[i]);
288                         if (!new_parent)
289                                 continue;
290                         pptr = &commit_list_insert(new_parent, pptr)->next;
291                         n_refs++;
292                 }
293         }
294         item->date = parse_commit_date(bufptr);
295
296         if (track_object_refs) {
297                 unsigned i = 0;
298                 struct commit_list *p;
299                 struct object_refs *refs = alloc_object_refs(n_refs);
300                 if (item->tree)
301                         refs->ref[i++] = &item->tree->object;
302                 for (p = item->parents; p; p = p->next)
303                         refs->ref[i++] = &p->item->object;
304                 set_object_refs(&item->object, refs);
305         }
306
307         return 0;
308 }
309
310 int parse_commit(struct commit *item)
311 {
312         enum object_type type;
313         void *buffer;
314         unsigned long size;
315         int ret;
316
317         if (item->object.parsed)
318                 return 0;
319         buffer = read_sha1_file(item->object.sha1, &type, &size);
320         if (!buffer)
321                 return error("Could not read %s",
322                              sha1_to_hex(item->object.sha1));
323         if (type != OBJ_COMMIT) {
324                 free(buffer);
325                 return error("Object %s not a commit",
326                              sha1_to_hex(item->object.sha1));
327         }
328         ret = parse_commit_buffer(item, buffer, size);
329         if (save_commit_buffer && !ret) {
330                 item->buffer = buffer;
331                 return 0;
332         }
333         free(buffer);
334         return ret;
335 }
336
337 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
338 {
339         struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
340         new_list->item = item;
341         new_list->next = *list_p;
342         *list_p = new_list;
343         return new_list;
344 }
345
346 void free_commit_list(struct commit_list *list)
347 {
348         while (list) {
349                 struct commit_list *temp = list;
350                 list = temp->next;
351                 free(temp);
352         }
353 }
354
355 struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
356 {
357         struct commit_list **pp = list;
358         struct commit_list *p;
359         while ((p = *pp) != NULL) {
360                 if (p->item->date < item->date) {
361                         break;
362                 }
363                 pp = &p->next;
364         }
365         return commit_list_insert(item, pp);
366 }
367
368
369 void sort_by_date(struct commit_list **list)
370 {
371         struct commit_list *ret = NULL;
372         while (*list) {
373                 insert_by_date((*list)->item, &ret);
374                 *list = (*list)->next;
375         }
376         *list = ret;
377 }
378
379 struct commit *pop_most_recent_commit(struct commit_list **list,
380                                       unsigned int mark)
381 {
382         struct commit *ret = (*list)->item;
383         struct commit_list *parents = ret->parents;
384         struct commit_list *old = *list;
385
386         *list = (*list)->next;
387         free(old);
388
389         while (parents) {
390                 struct commit *commit = parents->item;
391                 parse_commit(commit);
392                 if (!(commit->object.flags & mark)) {
393                         commit->object.flags |= mark;
394                         insert_by_date(commit, list);
395                 }
396                 parents = parents->next;
397         }
398         return ret;
399 }
400
401 void clear_commit_marks(struct commit *commit, unsigned int mark)
402 {
403         while (commit) {
404                 struct commit_list *parents;
405
406                 if (!(mark & commit->object.flags))
407                         return;
408
409                 commit->object.flags &= ~mark;
410
411                 parents = commit->parents;
412                 if (!parents)
413                         return;
414
415                 while ((parents = parents->next))
416                         clear_commit_marks(parents->item, mark);
417
418                 commit = commit->parents->item;
419         }
420 }
421
422 struct commit *pop_commit(struct commit_list **stack)
423 {
424         struct commit_list *top = *stack;
425         struct commit *item = top ? top->item : NULL;
426
427         if (top) {
428                 *stack = top->next;
429                 free(top);
430         }
431         return item;
432 }
433
434 void topo_sort_default_setter(struct commit *c, void *data)
435 {
436         c->util = data;
437 }
438
439 void *topo_sort_default_getter(struct commit *c)
440 {
441         return c->util;
442 }
443
444 /*
445  * Performs an in-place topological sort on the list supplied.
446  */
447 void sort_in_topological_order(struct commit_list ** list, int lifo)
448 {
449         sort_in_topological_order_fn(list, lifo, topo_sort_default_setter,
450                                      topo_sort_default_getter);
451 }
452
453 void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
454                                   topo_sort_set_fn_t setter,
455                                   topo_sort_get_fn_t getter)
456 {
457         struct commit_list * next = *list;
458         struct commit_list * work = NULL, **insert;
459         struct commit_list ** pptr = list;
460         struct sort_node * nodes;
461         struct sort_node * next_nodes;
462         int count = 0;
463
464         /* determine the size of the list */
465         while (next) {
466                 next = next->next;
467                 count++;
468         }
469
470         if (!count)
471                 return;
472         /* allocate an array to help sort the list */
473         nodes = xcalloc(count, sizeof(*nodes));
474         /* link the list to the array */
475         next_nodes = nodes;
476         next=*list;
477         while (next) {
478                 next_nodes->list_item = next;
479                 setter(next->item, next_nodes);
480                 next_nodes++;
481                 next = next->next;
482         }
483         /* update the indegree */
484         next=*list;
485         while (next) {
486                 struct commit_list * parents = next->item->parents;
487                 while (parents) {
488                         struct commit * parent=parents->item;
489                         struct sort_node * pn = (struct sort_node *) getter(parent);
490
491                         if (pn)
492                                 pn->indegree++;
493                         parents=parents->next;
494                 }
495                 next=next->next;
496         }
497         /*
498          * find the tips
499          *
500          * tips are nodes not reachable from any other node in the list
501          *
502          * the tips serve as a starting set for the work queue.
503          */
504         next=*list;
505         insert = &work;
506         while (next) {
507                 struct sort_node * node = (struct sort_node *) getter(next->item);
508
509                 if (node->indegree == 0) {
510                         insert = &commit_list_insert(next->item, insert)->next;
511                 }
512                 next=next->next;
513         }
514
515         /* process the list in topological order */
516         if (!lifo)
517                 sort_by_date(&work);
518         while (work) {
519                 struct commit * work_item = pop_commit(&work);
520                 struct sort_node * work_node = (struct sort_node *) getter(work_item);
521                 struct commit_list * parents = work_item->parents;
522
523                 while (parents) {
524                         struct commit * parent=parents->item;
525                         struct sort_node * pn = (struct sort_node *) getter(parent);
526
527                         if (pn) {
528                                 /*
529                                  * parents are only enqueued for emission
530                                  * when all their children have been emitted thereby
531                                  * guaranteeing topological order.
532                                  */
533                                 pn->indegree--;
534                                 if (!pn->indegree) {
535                                         if (!lifo)
536                                                 insert_by_date(parent, &work);
537                                         else
538                                                 commit_list_insert(parent, &work);
539                                 }
540                         }
541                         parents=parents->next;
542                 }
543                 /*
544                  * work_item is a commit all of whose children
545                  * have already been emitted. we can emit it now.
546                  */
547                 *pptr = work_node->list_item;
548                 pptr = &(*pptr)->next;
549                 *pptr = NULL;
550                 setter(work_item, NULL);
551         }
552         free(nodes);
553 }
554
555 /* merge-base stuff */
556
557 /* bits #0..15 in revision.h */
558 #define PARENT1         (1u<<16)
559 #define PARENT2         (1u<<17)
560 #define STALE           (1u<<18)
561 #define RESULT          (1u<<19)
562
563 static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
564
565 static struct commit *interesting(struct commit_list *list)
566 {
567         while (list) {
568                 struct commit *commit = list->item;
569                 list = list->next;
570                 if (commit->object.flags & STALE)
571                         continue;
572                 return commit;
573         }
574         return NULL;
575 }
576
577 static struct commit_list *merge_bases(struct commit *one, struct commit *two)
578 {
579         struct commit_list *list = NULL;
580         struct commit_list *result = NULL;
581
582         if (one == two)
583                 /* We do not mark this even with RESULT so we do not
584                  * have to clean it up.
585                  */
586                 return commit_list_insert(one, &result);
587
588         parse_commit(one);
589         parse_commit(two);
590
591         one->object.flags |= PARENT1;
592         two->object.flags |= PARENT2;
593         insert_by_date(one, &list);
594         insert_by_date(two, &list);
595
596         while (interesting(list)) {
597                 struct commit *commit;
598                 struct commit_list *parents;
599                 struct commit_list *n;
600                 int flags;
601
602                 commit = list->item;
603                 n = list->next;
604                 free(list);
605                 list = n;
606
607                 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
608                 if (flags == (PARENT1 | PARENT2)) {
609                         if (!(commit->object.flags & RESULT)) {
610                                 commit->object.flags |= RESULT;
611                                 insert_by_date(commit, &result);
612                         }
613                         /* Mark parents of a found merge stale */
614                         flags |= STALE;
615                 }
616                 parents = commit->parents;
617                 while (parents) {
618                         struct commit *p = parents->item;
619                         parents = parents->next;
620                         if ((p->object.flags & flags) == flags)
621                                 continue;
622                         parse_commit(p);
623                         p->object.flags |= flags;
624                         insert_by_date(p, &list);
625                 }
626         }
627
628         /* Clean up the result to remove stale ones */
629         free_commit_list(list);
630         list = result; result = NULL;
631         while (list) {
632                 struct commit_list *n = list->next;
633                 if (!(list->item->object.flags & STALE))
634                         insert_by_date(list->item, &result);
635                 free(list);
636                 list = n;
637         }
638         return result;
639 }
640
641 struct commit_list *get_merge_bases(struct commit *one,
642                                         struct commit *two, int cleanup)
643 {
644         struct commit_list *list;
645         struct commit **rslt;
646         struct commit_list *result;
647         int cnt, i, j;
648
649         result = merge_bases(one, two);
650         if (one == two)
651                 return result;
652         if (!result || !result->next) {
653                 if (cleanup) {
654                         clear_commit_marks(one, all_flags);
655                         clear_commit_marks(two, all_flags);
656                 }
657                 return result;
658         }
659
660         /* There are more than one */
661         cnt = 0;
662         list = result;
663         while (list) {
664                 list = list->next;
665                 cnt++;
666         }
667         rslt = xcalloc(cnt, sizeof(*rslt));
668         for (list = result, i = 0; list; list = list->next)
669                 rslt[i++] = list->item;
670         free_commit_list(result);
671
672         clear_commit_marks(one, all_flags);
673         clear_commit_marks(two, all_flags);
674         for (i = 0; i < cnt - 1; i++) {
675                 for (j = i+1; j < cnt; j++) {
676                         if (!rslt[i] || !rslt[j])
677                                 continue;
678                         result = merge_bases(rslt[i], rslt[j]);
679                         clear_commit_marks(rslt[i], all_flags);
680                         clear_commit_marks(rslt[j], all_flags);
681                         for (list = result; list; list = list->next) {
682                                 if (rslt[i] == list->item)
683                                         rslt[i] = NULL;
684                                 if (rslt[j] == list->item)
685                                         rslt[j] = NULL;
686                         }
687                 }
688         }
689
690         /* Surviving ones in rslt[] are the independent results */
691         result = NULL;
692         for (i = 0; i < cnt; i++) {
693                 if (rslt[i])
694                         insert_by_date(rslt[i], &result);
695         }
696         free(rslt);
697         return result;
698 }
699
700 int in_merge_bases(struct commit *commit, struct commit **reference, int num)
701 {
702         struct commit_list *bases, *b;
703         int ret = 0;
704
705         if (num == 1)
706                 bases = get_merge_bases(commit, *reference, 1);
707         else
708                 die("not yet");
709         for (b = bases; b; b = b->next) {
710                 if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
711                         ret = 1;
712                         break;
713                 }
714         }
715
716         free_commit_list(bases);
717         return ret;
718 }