0bbfa2ab31917e2a7584b0267c04f3324fad28d9
[git.git] / commit.c
1 #include <ctype.h>
2 #include "tag.h"
3 #include "commit.h"
4 #include "cache.h"
5
6 struct sort_node
7 {
8         /*
9          * the number of children of the associated commit
10          * that also occur in the list being sorted.
11          */
12         unsigned int indegree;
13
14         /*
15          * reference to original list item that we will re-use
16          * on output.
17          */
18         struct commit_list * list_item;
19
20 };
21
22 const char *commit_type = "commit";
23
24 enum cmit_fmt get_commit_format(const char *arg)
25 {
26         if (!*arg)
27                 return CMIT_FMT_DEFAULT;
28         if (!strcmp(arg, "=raw"))
29                 return CMIT_FMT_RAW;
30         if (!strcmp(arg, "=medium"))
31                 return CMIT_FMT_MEDIUM;
32         if (!strcmp(arg, "=short"))
33                 return CMIT_FMT_SHORT;
34         if (!strcmp(arg, "=full"))
35                 return CMIT_FMT_FULL;
36         die("invalid --pretty format");
37 }
38
39 static struct commit *check_commit(struct object *obj, const unsigned char *sha1)
40 {
41         if (obj->type != commit_type) {
42                 error("Object %s is a %s, not a commit", 
43                       sha1_to_hex(sha1), obj->type);
44                 return NULL;
45         }
46         return (struct commit *) obj;
47 }
48
49 struct commit *lookup_commit_reference(const unsigned char *sha1)
50 {
51         struct object *obj = parse_object(sha1);
52
53         if (!obj)
54                 return NULL;
55         if (obj->type == tag_type)
56                 obj = ((struct tag *)obj)->tagged;
57         return check_commit(obj, sha1);
58 }
59
60 struct commit *lookup_commit(const unsigned char *sha1)
61 {
62         struct object *obj = lookup_object(sha1);
63         if (!obj) {
64                 struct commit *ret = xmalloc(sizeof(struct commit));
65                 memset(ret, 0, sizeof(struct commit));
66                 created_object(sha1, &ret->object);
67                 ret->object.type = commit_type;
68                 return ret;
69         }
70         if (!obj->type)
71                 obj->type = commit_type;
72         return check_commit(obj, sha1);
73 }
74
75 static unsigned long parse_commit_date(const char *buf)
76 {
77         unsigned long date;
78
79         if (memcmp(buf, "author", 6))
80                 return 0;
81         while (*buf++ != '\n')
82                 /* nada */;
83         if (memcmp(buf, "committer", 9))
84                 return 0;
85         while (*buf++ != '>')
86                 /* nada */;
87         date = strtoul(buf, NULL, 10);
88         if (date == ULONG_MAX)
89                 date = 0;
90         return date;
91 }
92
93 int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
94 {
95         void *bufptr = buffer;
96         unsigned char parent[20];
97         struct commit_list **pptr;
98
99         if (item->object.parsed)
100                 return 0;
101         item->object.parsed = 1;
102         get_sha1_hex(bufptr + 5, parent);
103         item->tree = lookup_tree(parent);
104         if (item->tree)
105                 add_ref(&item->object, &item->tree->object);
106         bufptr += 46; /* "tree " + "hex sha1" + "\n" */
107         pptr = &item->parents;
108         while (!memcmp(bufptr, "parent ", 7) &&
109                !get_sha1_hex(bufptr + 7, parent)) {
110                 struct commit *new_parent = lookup_commit(parent);
111                 if (new_parent) {
112                         pptr = &commit_list_insert(new_parent, pptr)->next;
113                         add_ref(&item->object, &new_parent->object);
114                 }
115                 bufptr += 48;
116         }
117         item->date = parse_commit_date(bufptr);
118         return 0;
119 }
120
121 int parse_commit(struct commit *item)
122 {
123         char type[20];
124         void *buffer;
125         unsigned long size;
126         int ret;
127
128         if (item->object.parsed)
129                 return 0;
130         buffer = read_sha1_file(item->object.sha1, type, &size);
131         if (!buffer)
132                 return error("Could not read %s",
133                              sha1_to_hex(item->object.sha1));
134         if (strcmp(type, commit_type)) {
135                 free(buffer);
136                 return error("Object %s not a commit",
137                              sha1_to_hex(item->object.sha1));
138         }
139         ret = parse_commit_buffer(item, buffer, size);
140         if (!ret) {
141                 item->buffer = buffer;
142                 return 0;
143         }
144         free(buffer);
145         return ret;
146 }
147
148 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
149 {
150         struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
151         new_list->item = item;
152         new_list->next = *list_p;
153         *list_p = new_list;
154         return new_list;
155 }
156
157 void free_commit_list(struct commit_list *list)
158 {
159         while (list) {
160                 struct commit_list *temp = list;
161                 list = temp->next;
162                 free(temp);
163         }
164 }
165
166 struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
167 {
168         struct commit_list **pp = list;
169         struct commit_list *p;
170         while ((p = *pp) != NULL) {
171                 if (p->item->date < item->date) {
172                         break;
173                 }
174                 pp = &p->next;
175         }
176         return commit_list_insert(item, pp);
177 }
178
179         
180 void sort_by_date(struct commit_list **list)
181 {
182         struct commit_list *ret = NULL;
183         while (*list) {
184                 insert_by_date((*list)->item, &ret);
185                 *list = (*list)->next;
186         }
187         *list = ret;
188 }
189
190 struct commit *pop_most_recent_commit(struct commit_list **list,
191                                       unsigned int mark)
192 {
193         struct commit *ret = (*list)->item;
194         struct commit_list *parents = ret->parents;
195         struct commit_list *old = *list;
196
197         *list = (*list)->next;
198         free(old);
199
200         while (parents) {
201                 struct commit *commit = parents->item;
202                 parse_commit(commit);
203                 if (!(commit->object.flags & mark)) {
204                         commit->object.flags |= mark;
205                         insert_by_date(commit, list);
206                 }
207                 parents = parents->next;
208         }
209         return ret;
210 }
211
212 /*
213  * Generic support for pretty-printing the header
214  */
215 static int get_one_line(const char *msg, unsigned long len)
216 {
217         int ret = 0;
218
219         while (len--) {
220                 char c = *msg++;
221                 ret++;
222                 if (c == '\n')
223                         break;
224                 if (!c)
225                         return 0;
226         }
227         return ret;
228 }
229
230 static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line)
231 {
232         char *date;
233         unsigned int namelen;
234         unsigned long time;
235         int tz, ret;
236
237         date = strchr(line, '>');
238         if (!date)
239                 return 0;
240         namelen = ++date - line;
241         time = strtoul(date, &date, 10);
242         tz = strtol(date, NULL, 10);
243
244         ret = sprintf(buf, "%s: %.*s\n", what, namelen, line);
245         if (fmt == CMIT_FMT_MEDIUM)
246                 ret += sprintf(buf + ret, "Date:   %s\n", show_date(time, tz));
247         return ret;
248 }
249
250 static int is_empty_line(const char *line, int len)
251 {
252         while (len && isspace(line[len-1]))
253                 len--;
254         return !len;
255 }
256
257 static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents)
258 {
259         int offset = 0;
260         switch (parents) {
261         case 1:
262                 break;
263         case 2:
264                 /* Go back to the previous line: 40 characters of previous parent, and one '\n' */
265                 offset = sprintf(buf, "Merge: %.40s\n", line-41);
266                 /* Fallthrough */
267         default:
268                 /* Replace the previous '\n' with a space */
269                 buf[offset-1] = ' ';
270                 offset += sprintf(buf + offset, "%.40s\n", line+7);
271         }
272         return offset;
273 }
274
275 unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space)
276 {
277         int hdr = 1, body = 0;
278         unsigned long offset = 0;
279         int parents = 0;
280
281         for (;;) {
282                 const char *line = msg;
283                 int linelen = get_one_line(msg, len);
284
285                 if (!linelen)
286                         break;
287
288                 /*
289                  * We want some slop for indentation and a possible
290                  * final "...". Thus the "+ 20".
291                  */
292                 if (offset + linelen + 20 > space) {
293                         memcpy(buf + offset, "    ...\n", 8);
294                         offset += 8;
295                         break;
296                 }
297
298                 msg += linelen;
299                 len -= linelen;
300                 if (hdr) {
301                         if (linelen == 1) {
302                                 hdr = 0;
303                                 buf[offset++] = '\n';
304                                 continue;
305                         }
306                         if (fmt == CMIT_FMT_RAW) {
307                                 memcpy(buf + offset, line, linelen);
308                                 offset += linelen;
309                                 continue;
310                         }
311                         if (!memcmp(line, "parent ", 7)) {
312                                 if (linelen != 48)
313                                         die("bad parent line in commit");
314                                 offset += add_parent_info(fmt, buf + offset, line, ++parents);
315                         }
316                         if (!memcmp(line, "author ", 7))
317                                 offset += add_user_info("Author", fmt, buf + offset, line + 7);
318                         if (fmt == CMIT_FMT_FULL) {
319                                 if (!memcmp(line, "committer ", 10))
320                                         offset += add_user_info("Commit", fmt, buf + offset, line + 10);
321                         }
322                         continue;
323                 }
324
325                 if (is_empty_line(line, linelen)) {
326                         if (!body)
327                                 continue;
328                         if (fmt == CMIT_FMT_SHORT)
329                                 break;
330                 } else {
331                         body = 1;
332                 }
333                 memset(buf + offset, ' ', 4);
334                 memcpy(buf + offset + 4, line, linelen);
335                 offset += linelen + 4;
336         }
337         /* Make sure there is an EOLN */
338         if (buf[offset - 1] != '\n')
339                 buf[offset++] = '\n';
340         buf[offset] = '\0';
341         return offset;
342 }
343
344 struct commit *pop_commit(struct commit_list **stack)
345 {
346         struct commit_list *top = *stack;
347         struct commit *item = top ? top->item : NULL;
348
349         if (top) {
350                 *stack = top->next;
351                 free(top);
352         }
353         return item;
354 }
355
356 int count_parents(struct commit * commit)
357 {
358         int count = 0;
359         struct commit_list * parents = commit->parents;
360         for (count=0;parents; parents=parents->next,count++)
361           ;
362         return count;
363 }
364
365 /*
366  * Performs an in-place topological sort on the list supplied.
367  */
368 void sort_in_topological_order(struct commit_list ** list)
369 {
370         struct commit_list * next = *list;
371         struct commit_list * work = NULL;
372         struct commit_list ** pptr = list;
373         struct sort_node * nodes;
374         struct sort_node * next_nodes;
375         int count = 0;
376
377         /* determine the size of the list */
378         while (next) {
379                 next = next->next;
380                 count++;
381         }
382         /* allocate an array to help sort the list */
383         nodes = xcalloc(count, sizeof(*nodes));
384         /* link the list to the array */
385         next_nodes = nodes;
386         next=*list;
387         while (next) {
388                 next_nodes->list_item = next;
389                 next->item->object.util = next_nodes;
390                 next_nodes++;
391                 next = next->next;
392         }
393         /* update the indegree */
394         next=*list;
395         while (next) {
396                 struct commit_list * parents = next->item->parents;
397                 while (parents) {
398                         struct commit * parent=parents->item;
399                         struct sort_node * pn = (struct sort_node *)parent->object.util;
400                         
401                         if (pn)
402                                 pn->indegree++;
403                         parents=parents->next;
404                 }
405                 next=next->next;
406         }
407         /* 
408          * find the tips
409          *
410          * tips are nodes not reachable from any other node in the list 
411          * 
412          * the tips serve as a starting set for the work queue.
413          */
414         next=*list;
415         while (next) {
416                 struct sort_node * node = (struct sort_node *)next->item->object.util;
417
418                 if (node->indegree == 0) {
419                         commit_list_insert(next->item, &work);
420                 }
421                 next=next->next;
422         }
423         /* process the list in topological order */
424         while (work) {
425                 struct commit * work_item = pop_commit(&work);
426                 struct sort_node * work_node = (struct sort_node *)work_item->object.util;
427                 struct commit_list * parents = work_item->parents;
428
429                 while (parents) {
430                         struct commit * parent=parents->item;
431                         struct sort_node * pn = (struct sort_node *)parent->object.util;
432                         
433                         if (pn) {
434                                 /* 
435                                  * parents are only enqueued for emission 
436                                  * when all their children have been emitted thereby
437                                  * guaranteeing topological order.
438                                  */
439                                 pn->indegree--;
440                                 if (!pn->indegree) 
441                                         commit_list_insert(parent, &work);
442                         }
443                         parents=parents->next;
444                 }
445                 /*
446                  * work_item is a commit all of whose children
447                  * have already been emitted. we can emit it now.
448                  */
449                 *pptr = work_node->list_item;
450                 pptr = &(*pptr)->next;
451                 *pptr = NULL;
452                 work_item->object.util = NULL;
453         }
454         free(nodes);
455 }