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 }