git.oblomov.eu Git - git/blob - commit.c

   1 #include "cache.h"
   2 #include "tag.h"
   3 #include "commit.h"
   4 #include "repository.h"
   5 #include "object-store.h"
   6 #include "pkt-line.h"
   7 #include "utf8.h"
   8 #include "diff.h"
   9 #include "revision.h"
  10 #include "notes.h"
  11 #include "alloc.h"
  12 #include "gpg-interface.h"
  13 #include "mergesort.h"
  14 #include "commit-slab.h"
  15 #include "prio-queue.h"
  16 #include "sha1-lookup.h"
  17 #include "wt-status.h"
  18
  19 static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
  20
  21 int save_commit_buffer = 1;
  22
  23 const char *commit_type = "commit";
  24
  25 struct commit *lookup_commit_reference_gently(const struct object_id *oid,
  26                                               int quiet)
  27 {
  28         struct object *obj = deref_tag(parse_object(oid), NULL, 0);
  29
  30         if (!obj)
  31                 return NULL;
  32         return object_as_type(obj, OBJ_COMMIT, quiet);
  33 }
  34
  35 struct commit *lookup_commit_reference(const struct object_id *oid)
  36 {
  37         return lookup_commit_reference_gently(oid, 0);
  38 }
  39
  40 struct commit *lookup_commit_or_die(const struct object_id *oid, const char *ref_name)
  41 {
  42         struct commit *c = lookup_commit_reference(oid);
  43         if (!c)
  44                 die(_("could not parse %s"), ref_name);
  45         if (oidcmp(oid, &c->object.oid)) {
  46                 warning(_("%s %s is not a commit!"),
  47                         ref_name, oid_to_hex(oid));
  48         }
  49         return c;
  50 }
  51
  52 struct commit *lookup_commit(const struct object_id *oid)
  53 {
  54         struct object *obj = lookup_object(oid->hash);
  55         if (!obj)
  56                 return create_object(the_repository, oid->hash,
  57                                      alloc_commit_node(the_repository));
  58         return object_as_type(obj, OBJ_COMMIT, 0);
  59 }
  60
  61 struct commit *lookup_commit_reference_by_name(const char *name)
  62 {
  63         struct object_id oid;
  64         struct commit *commit;
  65
  66         if (get_oid_committish(name, &oid))
  67                 return NULL;
  68         commit = lookup_commit_reference(&oid);
  69         if (parse_commit(commit))
  70                 return NULL;
  71         return commit;
  72 }
  73
  74 static timestamp_t parse_commit_date(const char *buf, const char *tail)
  75 {
  76         const char *dateptr;
  77
  78         if (buf + 6 >= tail)
  79                 return 0;
  80         if (memcmp(buf, "author", 6))
  81                 return 0;
  82         while (buf < tail && *buf++ != '\n')
  83                 /* nada */;
  84         if (buf + 9 >= tail)
  85                 return 0;
  86         if (memcmp(buf, "committer", 9))
  87                 return 0;
  88         while (buf < tail && *buf++ != '>')
  89                 /* nada */;
  90         if (buf >= tail)
  91                 return 0;
  92         dateptr = buf;
  93         while (buf < tail && *buf++ != '\n')
  94                 /* nada */;
  95         if (buf >= tail)
  96                 return 0;
  97         /* dateptr < buf && buf[-1] == '\n', so parsing will stop at buf-1 */
  98         return parse_timestamp(dateptr, NULL, 10);
  99 }
 100
 101 static const unsigned char *commit_graft_sha1_access(size_t index, void *table)
 102 {
 103         struct commit_graft **commit_graft_table = table;
 104         return commit_graft_table[index]->oid.hash;
 105 }
 106
 107 static int commit_graft_pos(struct repository *r, const unsigned char *sha1)
 108 {
 109         return sha1_pos(sha1, r->parsed_objects->grafts,
 110                         r->parsed_objects->grafts_nr,
 111                         commit_graft_sha1_access);
 112 }
 113
 114 int register_commit_graft(struct repository *r, struct commit_graft *graft,
 115                           int ignore_dups)
 116 {
 117         int pos = commit_graft_pos(r, graft->oid.hash);
 118
 119         if (0 <= pos) {
 120                 if (ignore_dups)
 121                         free(graft);
 122                 else {
 123                         free(r->parsed_objects->grafts[pos]);
 124                         r->parsed_objects->grafts[pos] = graft;
 125                 }
 126                 return 1;
 127         }
 128         pos = -pos - 1;
 129         ALLOC_GROW(r->parsed_objects->grafts,
 130                    r->parsed_objects->grafts_nr + 1,
 131                    r->parsed_objects->grafts_alloc);
 132         r->parsed_objects->grafts_nr++;
 133         if (pos < r->parsed_objects->grafts_nr)
 134                 memmove(r->parsed_objects->grafts + pos + 1,
 135                         r->parsed_objects->grafts + pos,
 136                         (r->parsed_objects->grafts_nr - pos - 1) *
 137                         sizeof(*r->parsed_objects->grafts));
 138         r->parsed_objects->grafts[pos] = graft;
 139         return 0;
 140 }
 141
 142 struct commit_graft *read_graft_line(struct strbuf *line)
 143 {
 144         /* The format is just "Commit Parent1 Parent2 ...\n" */
 145         int i, phase;
 146         const char *tail = NULL;
 147         struct commit_graft *graft = NULL;
 148         struct object_id dummy_oid, *oid;
 149
 150         strbuf_rtrim(line);
 151         if (!line->len || line->buf[0] == '#')
 152                 return NULL;
 153         /*
 154          * phase 0 verifies line, counts hashes in line and allocates graft
 155          * phase 1 fills graft
 156          */
 157         for (phase = 0; phase < 2; phase++) {
 158                 oid = graft ? &graft->oid : &dummy_oid;
 159                 if (parse_oid_hex(line->buf, oid, &tail))
 160                         goto bad_graft_data;
 161                 for (i = 0; *tail != '\0'; i++) {
 162                         oid = graft ? &graft->parent[i] : &dummy_oid;
 163                         if (!isspace(*tail++) || parse_oid_hex(tail, oid, &tail))
 164                                 goto bad_graft_data;
 165                 }
 166                 if (!graft) {
 167                         graft = xmalloc(st_add(sizeof(*graft),
 168                                                st_mult(sizeof(struct object_id), i)));
 169                         graft->nr_parent = i;
 170                 }
 171         }
 172         return graft;
 173
 174 bad_graft_data:
 175         error("bad graft data: %s", line->buf);
 176         assert(!graft);
 177         return NULL;
 178 }
 179
 180 static int read_graft_file(struct repository *r, const char *graft_file)
 181 {
 182         FILE *fp = fopen_or_warn(graft_file, "r");
 183         struct strbuf buf = STRBUF_INIT;
 184         if (!fp)
 185                 return -1;
 186         while (!strbuf_getwholeline(&buf, fp, '\n')) {
 187                 /* The format is just "Commit Parent1 Parent2 ...\n" */
 188                 struct commit_graft *graft = read_graft_line(&buf);
 189                 if (!graft)
 190                         continue;
 191                 if (register_commit_graft(r, graft, 1))
 192                         error("duplicate graft data: %s", buf.buf);
 193         }
 194         fclose(fp);
 195         strbuf_release(&buf);
 196         return 0;
 197 }
 198
 199 #define prepare_commit_graft(r) prepare_commit_graft_##r()
 200 static void prepare_commit_graft_the_repository(void)
 201 {
 202         static int commit_graft_prepared;
 203         char *graft_file;
 204
 205         if (commit_graft_prepared)
 206                 return;
 207         graft_file = get_graft_file();
 208         read_graft_file(the_repository, graft_file);
 209         /* make sure shallows are read */
 210         is_repository_shallow(the_repository);
 211         commit_graft_prepared = 1;
 212 }
 213
 214 struct commit_graft *lookup_commit_graft_the_repository(const struct object_id *oid)
 215 {
 216         int pos;
 217         prepare_commit_graft(the_repository);
 218         pos = commit_graft_pos(the_repository, oid->hash);
 219         if (pos < 0)
 220                 return NULL;
 221         return the_repository->parsed_objects->grafts[pos];
 222 }
 223
 224 int for_each_commit_graft(each_commit_graft_fn fn, void *cb_data)
 225 {
 226         int i, ret;
 227         for (i = ret = 0; i < the_repository->parsed_objects->grafts_nr && !ret; i++)
 228                 ret = fn(the_repository->parsed_objects->grafts[i], cb_data);
 229         return ret;
 230 }
 231
 232 int unregister_shallow(const struct object_id *oid)
 233 {
 234         int pos = commit_graft_pos(the_repository, oid->hash);
 235         if (pos < 0)
 236                 return -1;
 237         if (pos + 1 < the_repository->parsed_objects->grafts_nr)
 238                 MOVE_ARRAY(the_repository->parsed_objects->grafts + pos,
 239                            the_repository->parsed_objects->grafts + pos + 1,
 240                            the_repository->parsed_objects->grafts_nr - pos - 1);
 241         the_repository->parsed_objects->grafts_nr--;
 242         return 0;
 243 }
 244
 245 struct commit_buffer {
 246         void *buffer;
 247         unsigned long size;
 248 };
 249 define_commit_slab(buffer_slab, struct commit_buffer);
 250 static struct buffer_slab buffer_slab = COMMIT_SLAB_INIT(1, buffer_slab);
 251
 252 void set_commit_buffer(struct commit *commit, void *buffer, unsigned long size)
 253 {
 254         struct commit_buffer *v = buffer_slab_at(&buffer_slab, commit);
 255         v->buffer = buffer;
 256         v->size = size;
 257 }
 258
 259 const void *get_cached_commit_buffer(const struct commit *commit, unsigned long *sizep)
 260 {
 261         struct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);
 262         if (!v) {
 263                 if (sizep)
 264                         *sizep = 0;
 265                 return NULL;
 266         }
 267         if (sizep)
 268                 *sizep = v->size;
 269         return v->buffer;
 270 }
 271
 272 const void *get_commit_buffer(const struct commit *commit, unsigned long *sizep)
 273 {
 274         const void *ret = get_cached_commit_buffer(commit, sizep);
 275         if (!ret) {
 276                 enum object_type type;
 277                 unsigned long size;
 278                 ret = read_object_file(&commit->object.oid, &type, &size);
 279                 if (!ret)
 280                         die("cannot read commit object %s",
 281                             oid_to_hex(&commit->object.oid));
 282                 if (type != OBJ_COMMIT)
 283                         die("expected commit for %s, got %s",
 284                             oid_to_hex(&commit->object.oid), type_name(type));
 285                 if (sizep)
 286                         *sizep = size;
 287         }
 288         return ret;
 289 }
 290
 291 void unuse_commit_buffer(const struct commit *commit, const void *buffer)
 292 {
 293         struct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);
 294         if (!(v && v->buffer == buffer))
 295                 free((void *)buffer);
 296 }
 297
 298 void free_commit_buffer(struct commit *commit)
 299 {
 300         struct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);
 301         if (v) {
 302                 FREE_AND_NULL(v->buffer);
 303                 v->size = 0;
 304         }
 305 }
 306
 307 void release_commit_memory(struct commit *c)
 308 {
 309         c->tree = NULL;
 310         c->index = 0;
 311         free_commit_buffer(c);
 312         free_commit_list(c->parents);
 313         /* TODO: what about commit->util? */
 314
 315         c->object.parsed = 0;
 316 }
 317
 318 const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep)
 319 {
 320         struct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);
 321         void *ret;
 322
 323         if (!v) {
 324                 if (sizep)
 325                         *sizep = 0;
 326                 return NULL;
 327         }
 328         ret = v->buffer;
 329         if (sizep)
 330                 *sizep = v->size;
 331
 332         v->buffer = NULL;
 333         v->size = 0;
 334         return ret;
 335 }
 336
 337 int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size)
 338 {
 339         const char *tail = buffer;
 340         const char *bufptr = buffer;
 341         struct object_id parent;
 342         struct commit_list **pptr;
 343         struct commit_graft *graft;
 344         const int tree_entry_len = GIT_SHA1_HEXSZ + 5;
 345         const int parent_entry_len = GIT_SHA1_HEXSZ + 7;
 346
 347         if (item->object.parsed)
 348                 return 0;
 349         item->object.parsed = 1;
 350         tail += size;
 351         if (tail <= bufptr + tree_entry_len + 1 || memcmp(bufptr, "tree ", 5) ||
 352                         bufptr[tree_entry_len] != '\n')
 353                 return error("bogus commit object %s", oid_to_hex(&item->object.oid));
 354         if (get_sha1_hex(bufptr + 5, parent.hash) < 0)
 355                 return error("bad tree pointer in commit %s",
 356                              oid_to_hex(&item->object.oid));
 357         item->tree = lookup_tree(&parent);
 358         bufptr += tree_entry_len + 1; /* "tree " + "hex sha1" + "\n" */
 359         pptr = &item->parents;
 360
 361         graft = lookup_commit_graft(the_repository, &item->object.oid);
 362         while (bufptr + parent_entry_len < tail && !memcmp(bufptr, "parent ", 7)) {
 363                 struct commit *new_parent;
 364
 365                 if (tail <= bufptr + parent_entry_len + 1 ||
 366                     get_sha1_hex(bufptr + 7, parent.hash) ||
 367                     bufptr[parent_entry_len] != '\n')
 368                         return error("bad parents in commit %s", oid_to_hex(&item->object.oid));
 369                 bufptr += parent_entry_len + 1;
 370                 /*
 371                  * The clone is shallow if nr_parent < 0, and we must
 372                  * not traverse its real parents even when we unhide them.
 373                  */
 374                 if (graft && (graft->nr_parent < 0 || grafts_replace_parents))
 375                         continue;
 376                 new_parent = lookup_commit(&parent);
 377                 if (new_parent)
 378                         pptr = &commit_list_insert(new_parent, pptr)->next;
 379         }
 380         if (graft) {
 381                 int i;
 382                 struct commit *new_parent;
 383                 for (i = 0; i < graft->nr_parent; i++) {
 384                         new_parent = lookup_commit(&graft->parent[i]);
 385                         if (!new_parent)
 386                                 continue;
 387                         pptr = &commit_list_insert(new_parent, pptr)->next;
 388                 }
 389         }
 390         item->date = parse_commit_date(bufptr, tail);
 391
 392         return 0;
 393 }
 394
 395 int parse_commit_gently(struct commit *item, int quiet_on_missing)
 396 {
 397         enum object_type type;
 398         void *buffer;
 399         unsigned long size;
 400         int ret;
 401
 402         if (!item)
 403                 return -1;
 404         if (item->object.parsed)
 405                 return 0;
 406         buffer = read_object_file(&item->object.oid, &type, &size);
 407         if (!buffer)
 408                 return quiet_on_missing ? -1 :
 409                         error("Could not read %s",
 410                              oid_to_hex(&item->object.oid));
 411         if (type != OBJ_COMMIT) {
 412                 free(buffer);
 413                 return error("Object %s not a commit",
 414                              oid_to_hex(&item->object.oid));
 415         }
 416         ret = parse_commit_buffer(item, buffer, size);
 417         if (save_commit_buffer && !ret) {
 418                 set_commit_buffer(item, buffer, size);
 419                 return 0;
 420         }
 421         free(buffer);
 422         return ret;
 423 }
 424
 425 void parse_commit_or_die(struct commit *item)
 426 {
 427         if (parse_commit(item))
 428                 die("unable to parse commit %s",
 429                     item ? oid_to_hex(&item->object.oid) : "(null)");
 430 }
 431
 432 int find_commit_subject(const char *commit_buffer, const char **subject)
 433 {
 434         const char *eol;
 435         const char *p = commit_buffer;
 436
 437         while (*p && (*p != '\n' || p[1] != '\n'))
 438                 p++;
 439         if (*p) {
 440                 p = skip_blank_lines(p + 2);
 441                 eol = strchrnul(p, '\n');
 442         } else
 443                 eol = p;
 444
 445         *subject = p;
 446
 447         return eol - p;
 448 }
 449
 450 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 451 {
 452         struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
 453         new_list->item = item;
 454         new_list->next = *list_p;
 455         *list_p = new_list;
 456         return new_list;
 457 }
 458
 459 unsigned commit_list_count(const struct commit_list *l)
 460 {
 461         unsigned c = 0;
 462         for (; l; l = l->next )
 463                 c++;
 464         return c;
 465 }
 466
 467 struct commit_list *copy_commit_list(struct commit_list *list)
 468 {
 469         struct commit_list *head = NULL;
 470         struct commit_list **pp = &head;
 471         while (list) {
 472                 pp = commit_list_append(list->item, pp);
 473                 list = list->next;
 474         }
 475         return head;
 476 }
 477
 478 void free_commit_list(struct commit_list *list)
 479 {
 480         while (list)
 481                 pop_commit(&list);
 482 }
 483
 484 struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list)
 485 {
 486         struct commit_list **pp = list;
 487         struct commit_list *p;
 488         while ((p = *pp) != NULL) {
 489                 if (p->item->date < item->date) {
 490                         break;
 491                 }
 492                 pp = &p->next;
 493         }
 494         return commit_list_insert(item, pp);
 495 }
 496
 497 static int commit_list_compare_by_date(const void *a, const void *b)
 498 {
 499         timestamp_t a_date = ((const struct commit_list *)a)->item->date;
 500         timestamp_t b_date = ((const struct commit_list *)b)->item->date;
 501         if (a_date < b_date)
 502                 return 1;
 503         if (a_date > b_date)
 504                 return -1;
 505         return 0;
 506 }
 507
 508 static void *commit_list_get_next(const void *a)
 509 {
 510         return ((const struct commit_list *)a)->next;
 511 }
 512
 513 static void commit_list_set_next(void *a, void *next)
 514 {
 515         ((struct commit_list *)a)->next = next;
 516 }
 517
 518 void commit_list_sort_by_date(struct commit_list **list)
 519 {
 520         *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
 521                                 commit_list_compare_by_date);
 522 }
 523
 524 struct commit *pop_most_recent_commit(struct commit_list **list,
 525                                       unsigned int mark)
 526 {
 527         struct commit *ret = pop_commit(list);
 528         struct commit_list *parents = ret->parents;
 529
 530         while (parents) {
 531                 struct commit *commit = parents->item;
 532                 if (!parse_commit(commit) && !(commit->object.flags & mark)) {
 533                         commit->object.flags |= mark;
 534                         commit_list_insert_by_date(commit, list);
 535                 }
 536                 parents = parents->next;
 537         }
 538         return ret;
 539 }
 540
 541 static void clear_commit_marks_1(struct commit_list **plist,
 542                                  struct commit *commit, unsigned int mark)
 543 {
 544         while (commit) {
 545                 struct commit_list *parents;
 546
 547                 if (!(mark & commit->object.flags))
 548                         return;
 549
 550                 commit->object.flags &= ~mark;
 551
 552                 parents = commit->parents;
 553                 if (!parents)
 554                         return;
 555
 556                 while ((parents = parents->next))
 557                         commit_list_insert(parents->item, plist);
 558
 559                 commit = commit->parents->item;
 560         }
 561 }
 562
 563 void clear_commit_marks_many(int nr, struct commit **commit, unsigned int mark)
 564 {
 565         struct commit_list *list = NULL;
 566
 567         while (nr--) {
 568                 clear_commit_marks_1(&list, *commit, mark);
 569                 commit++;
 570         }
 571         while (list)
 572                 clear_commit_marks_1(&list, pop_commit(&list), mark);
 573 }
 574
 575 void clear_commit_marks(struct commit *commit, unsigned int mark)
 576 {
 577         clear_commit_marks_many(1, &commit, mark);
 578 }
 579
 580 struct commit *pop_commit(struct commit_list **stack)
 581 {
 582         struct commit_list *top = *stack;
 583         struct commit *item = top ? top->item : NULL;
 584
 585         if (top) {
 586                 *stack = top->next;
 587                 free(top);
 588         }
 589         return item;
 590 }
 591
 592 /*
 593  * Topological sort support
 594  */
 595
 596 /* count number of children that have not been emitted */
 597 define_commit_slab(indegree_slab, int);
 598
 599 /* record author-date for each commit object */
 600 define_commit_slab(author_date_slab, unsigned long);
 601
 602 static void record_author_date(struct author_date_slab *author_date,
 603                                struct commit *commit)
 604 {
 605         const char *buffer = get_commit_buffer(commit, NULL);
 606         struct ident_split ident;
 607         const char *ident_line;
 608         size_t ident_len;
 609         char *date_end;
 610         timestamp_t date;
 611
 612         ident_line = find_commit_header(buffer, "author", &ident_len);
 613         if (!ident_line)
 614                 goto fail_exit; /* no author line */
 615         if (split_ident_line(&ident, ident_line, ident_len) ||
 616             !ident.date_begin || !ident.date_end)
 617                 goto fail_exit; /* malformed "author" line */
 618
 619         date = parse_timestamp(ident.date_begin, &date_end, 10);
 620         if (date_end != ident.date_end)
 621                 goto fail_exit; /* malformed date */
 622         *(author_date_slab_at(author_date, commit)) = date;
 623
 624 fail_exit:
 625         unuse_commit_buffer(commit, buffer);
 626 }
 627
 628 static int compare_commits_by_author_date(const void *a_, const void *b_,
 629                                           void *cb_data)
 630 {
 631         const struct commit *a = a_, *b = b_;
 632         struct author_date_slab *author_date = cb_data;
 633         timestamp_t a_date = *(author_date_slab_at(author_date, a));
 634         timestamp_t b_date = *(author_date_slab_at(author_date, b));
 635
 636         /* newer commits with larger date first */
 637         if (a_date < b_date)
 638                 return 1;
 639         else if (a_date > b_date)
 640                 return -1;
 641         return 0;
 642 }
 643
 644 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)
 645 {
 646         const struct commit *a = a_, *b = b_;
 647         /* newer commits with larger date first */
 648         if (a->date < b->date)
 649                 return 1;
 650         else if (a->date > b->date)
 651                 return -1;
 652         return 0;
 653 }
 654
 655 /*
 656  * Performs an in-place topological sort on the list supplied.
 657  */
 658 void sort_in_topological_order(struct commit_list **list, enum rev_sort_order sort_order)
 659 {
 660         struct commit_list *next, *orig = *list;
 661         struct commit_list **pptr;
 662         struct indegree_slab indegree;
 663         struct prio_queue queue;
 664         struct commit *commit;
 665         struct author_date_slab author_date;
 666
 667         if (!orig)
 668                 return;
 669         *list = NULL;
 670
 671         init_indegree_slab(&indegree);
 672         memset(&queue, '\0', sizeof(queue));
 673
 674         switch (sort_order) {
 675         default: /* REV_SORT_IN_GRAPH_ORDER */
 676                 queue.compare = NULL;
 677                 break;
 678         case REV_SORT_BY_COMMIT_DATE:
 679                 queue.compare = compare_commits_by_commit_date;
 680                 break;
 681         case REV_SORT_BY_AUTHOR_DATE:
 682                 init_author_date_slab(&author_date);
 683                 queue.compare = compare_commits_by_author_date;
 684                 queue.cb_data = &author_date;
 685                 break;
 686         }
 687
 688         /* Mark them and clear the indegree */
 689         for (next = orig; next; next = next->next) {
 690                 struct commit *commit = next->item;
 691                 *(indegree_slab_at(&indegree, commit)) = 1;
 692                 /* also record the author dates, if needed */
 693                 if (sort_order == REV_SORT_BY_AUTHOR_DATE)
 694                         record_author_date(&author_date, commit);
 695         }
 696
 697         /* update the indegree */
 698         for (next = orig; next; next = next->next) {
 699                 struct commit_list *parents = next->item->parents;
 700                 while (parents) {
 701                         struct commit *parent = parents->item;
 702                         int *pi = indegree_slab_at(&indegree, parent);
 703
 704                         if (*pi)
 705                                 (*pi)++;
 706                         parents = parents->next;
 707                 }
 708         }
 709
 710         /*
 711          * find the tips
 712          *
 713          * tips are nodes not reachable from any other node in the list
 714          *
 715          * the tips serve as a starting set for the work queue.
 716          */
 717         for (next = orig; next; next = next->next) {
 718                 struct commit *commit = next->item;
 719
 720                 if (*(indegree_slab_at(&indegree, commit)) == 1)
 721                         prio_queue_put(&queue, commit);
 722         }
 723
 724         /*
 725          * This is unfortunate; the initial tips need to be shown
 726          * in the order given from the revision traversal machinery.
 727          */
 728         if (sort_order == REV_SORT_IN_GRAPH_ORDER)
 729                 prio_queue_reverse(&queue);
 730
 731         /* We no longer need the commit list */
 732         free_commit_list(orig);
 733
 734         pptr = list;
 735         *list = NULL;
 736         while ((commit = prio_queue_get(&queue)) != NULL) {
 737                 struct commit_list *parents;
 738
 739                 for (parents = commit->parents; parents ; parents = parents->next) {
 740                         struct commit *parent = parents->item;
 741                         int *pi = indegree_slab_at(&indegree, parent);
 742
 743                         if (!*pi)
 744                                 continue;
 745
 746                         /*
 747                          * parents are only enqueued for emission
 748                          * when all their children have been emitted thereby
 749                          * guaranteeing topological order.
 750                          */
 751                         if (--(*pi) == 1)
 752                                 prio_queue_put(&queue, parent);
 753                 }
 754                 /*
 755                  * all children of commit have already been
 756                  * emitted. we can emit it now.
 757                  */
 758                 *(indegree_slab_at(&indegree, commit)) = 0;
 759
 760                 pptr = &commit_list_insert(commit, pptr)->next;
 761         }
 762
 763         clear_indegree_slab(&indegree);
 764         clear_prio_queue(&queue);
 765         if (sort_order == REV_SORT_BY_AUTHOR_DATE)
 766                 clear_author_date_slab(&author_date);
 767 }
 768
 769 /* merge-base stuff */
 770
 771 /* Remember to update object flag allocation in object.h */
 772 #define PARENT1         (1u<<16)
 773 #define PARENT2         (1u<<17)
 774 #define STALE           (1u<<18)
 775 #define RESULT          (1u<<19)
 776
 777 static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
 778
 779 static int queue_has_nonstale(struct prio_queue *queue)
 780 {
 781         int i;
 782         for (i = 0; i < queue->nr; i++) {
 783                 struct commit *commit = queue->array[i].data;
 784                 if (!(commit->object.flags & STALE))
 785                         return 1;
 786         }
 787         return 0;
 788 }
 789
 790 /* all input commits in one and twos[] must have been parsed! */
 791 static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
 792 {
 793         struct prio_queue queue = { compare_commits_by_commit_date };
 794         struct commit_list *result = NULL;
 795         int i;
 796
 797         one->object.flags |= PARENT1;
 798         if (!n) {
 799                 commit_list_append(one, &result);
 800                 return result;
 801         }
 802         prio_queue_put(&queue, one);
 803
 804         for (i = 0; i < n; i++) {
 805                 twos[i]->object.flags |= PARENT2;
 806                 prio_queue_put(&queue, twos[i]);
 807         }
 808
 809         while (queue_has_nonstale(&queue)) {
 810                 struct commit *commit = prio_queue_get(&queue);
 811                 struct commit_list *parents;
 812                 int flags;
 813
 814                 flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 815                 if (flags == (PARENT1 | PARENT2)) {
 816                         if (!(commit->object.flags & RESULT)) {
 817                                 commit->object.flags |= RESULT;
 818                                 commit_list_insert_by_date(commit, &result);
 819                         }
 820                         /* Mark parents of a found merge stale */
 821                         flags |= STALE;
 822                 }
 823                 parents = commit->parents;
 824                 while (parents) {
 825                         struct commit *p = parents->item;
 826                         parents = parents->next;
 827                         if ((p->object.flags & flags) == flags)
 828                                 continue;
 829                         if (parse_commit(p))
 830                                 return NULL;
 831                         p->object.flags |= flags;
 832                         prio_queue_put(&queue, p);
 833                 }
 834         }
 835
 836         clear_prio_queue(&queue);
 837         return result;
 838 }
 839
 840 static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
 841 {
 842         struct commit_list *list = NULL;
 843         struct commit_list *result = NULL;
 844         int i;
 845
 846         for (i = 0; i < n; i++) {
 847                 if (one == twos[i])
 848                         /*
 849                          * We do not mark this even with RESULT so we do not
 850                          * have to clean it up.
 851                          */
 852                         return commit_list_insert(one, &result);
 853         }
 854
 855         if (parse_commit(one))
 856                 return NULL;
 857         for (i = 0; i < n; i++) {
 858                 if (parse_commit(twos[i]))
 859                         return NULL;
 860         }
 861
 862         list = paint_down_to_common(one, n, twos);
 863
 864         while (list) {
 865                 struct commit *commit = pop_commit(&list);
 866                 if (!(commit->object.flags & STALE))
 867                         commit_list_insert_by_date(commit, &result);
 868         }
 869         return result;
 870 }
 871
 872 struct commit_list *get_octopus_merge_bases(struct commit_list *in)
 873 {
 874         struct commit_list *i, *j, *k, *ret = NULL;
 875
 876         if (!in)
 877                 return ret;
 878
 879         commit_list_insert(in->item, &ret);
 880
 881         for (i = in->next; i; i = i->next) {
 882                 struct commit_list *new_commits = NULL, *end = NULL;
 883
 884                 for (j = ret; j; j = j->next) {
 885                         struct commit_list *bases;
 886                         bases = get_merge_bases(i->item, j->item);
 887                         if (!new_commits)
 888                                 new_commits = bases;
 889                         else
 890                                 end->next = bases;
 891                         for (k = bases; k; k = k->next)
 892                                 end = k;
 893                 }
 894                 ret = new_commits;
 895         }
 896         return ret;
 897 }
 898
 899 static int remove_redundant(struct commit **array, int cnt)
 900 {
 901         /*
 902          * Some commit in the array may be an ancestor of
 903          * another commit.  Move such commit to the end of
 904          * the array, and return the number of commits that
 905          * are independent from each other.
 906          */
 907         struct commit **work;
 908         unsigned char *redundant;
 909         int *filled_index;
 910         int i, j, filled;
 911
 912         work = xcalloc(cnt, sizeof(*work));
 913         redundant = xcalloc(cnt, 1);
 914         ALLOC_ARRAY(filled_index, cnt - 1);
 915
 916         for (i = 0; i < cnt; i++)
 917                 parse_commit(array[i]);
 918         for (i = 0; i < cnt; i++) {
 919                 struct commit_list *common;
 920
 921                 if (redundant[i])
 922                         continue;
 923                 for (j = filled = 0; j < cnt; j++) {
 924                         if (i == j || redundant[j])
 925                                 continue;
 926                         filled_index[filled] = j;
 927                         work[filled++] = array[j];
 928                 }
 929                 common = paint_down_to_common(array[i], filled, work);
 930                 if (array[i]->object.flags & PARENT2)
 931                         redundant[i] = 1;
 932                 for (j = 0; j < filled; j++)
 933                         if (work[j]->object.flags & PARENT1)
 934                                 redundant[filled_index[j]] = 1;
 935                 clear_commit_marks(array[i], all_flags);
 936                 clear_commit_marks_many(filled, work, all_flags);
 937                 free_commit_list(common);
 938         }
 939
 940         /* Now collect the result */
 941         COPY_ARRAY(work, array, cnt);
 942         for (i = filled = 0; i < cnt; i++)
 943                 if (!redundant[i])
 944                         array[filled++] = work[i];
 945         for (j = filled, i = 0; i < cnt; i++)
 946                 if (redundant[i])
 947                         array[j++] = work[i];
 948         free(work);
 949         free(redundant);
 950         free(filled_index);
 951         return filled;
 952 }
 953
 954 static struct commit_list *get_merge_bases_many_0(struct commit *one,
 955                                                   int n,
 956                                                   struct commit **twos,
 957                                                   int cleanup)
 958 {
 959         struct commit_list *list;
 960         struct commit **rslt;
 961         struct commit_list *result;
 962         int cnt, i;
 963
 964         result = merge_bases_many(one, n, twos);
 965         for (i = 0; i < n; i++) {
 966                 if (one == twos[i])
 967                         return result;
 968         }
 969         if (!result || !result->next) {
 970                 if (cleanup) {
 971                         clear_commit_marks(one, all_flags);
 972                         clear_commit_marks_many(n, twos, all_flags);
 973                 }
 974                 return result;
 975         }
 976
 977         /* There are more than one */
 978         cnt = commit_list_count(result);
 979         rslt = xcalloc(cnt, sizeof(*rslt));
 980         for (list = result, i = 0; list; list = list->next)
 981                 rslt[i++] = list->item;
 982         free_commit_list(result);
 983
 984         clear_commit_marks(one, all_flags);
 985         clear_commit_marks_many(n, twos, all_flags);
 986
 987         cnt = remove_redundant(rslt, cnt);
 988         result = NULL;
 989         for (i = 0; i < cnt; i++)
 990                 commit_list_insert_by_date(rslt[i], &result);
 991         free(rslt);
 992         return result;
 993 }
 994
 995 struct commit_list *get_merge_bases_many(struct commit *one,
 996                                          int n,
 997                                          struct commit **twos)
 998 {
 999         return get_merge_bases_many_0(one, n, twos, 1);
1000 }
1001
1002 struct commit_list *get_merge_bases_many_dirty(struct commit *one,
1003                                                int n,
1004                                                struct commit **twos)
1005 {
1006         return get_merge_bases_many_0(one, n, twos, 0);
1007 }
1008
1009 struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
1010 {
1011         return get_merge_bases_many_0(one, 1, &two, 1);
1012 }
1013
1014 /*
1015  * Is "commit" a descendant of one of the elements on the "with_commit" list?
1016  */
1017 int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
1018 {
1019         if (!with_commit)
1020                 return 1;
1021         while (with_commit) {
1022                 struct commit *other;
1023
1024                 other = with_commit->item;
1025                 with_commit = with_commit->next;
1026                 if (in_merge_bases(other, commit))
1027                         return 1;
1028         }
1029         return 0;
1030 }
1031
1032 /*
1033  * Is "commit" an ancestor of one of the "references"?
1034  */
1035 int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
1036 {
1037         struct commit_list *bases;
1038         int ret = 0, i;
1039
1040         if (parse_commit(commit))
1041                 return ret;
1042         for (i = 0; i < nr_reference; i++)
1043                 if (parse_commit(reference[i]))
1044                         return ret;
1045
1046         bases = paint_down_to_common(commit, nr_reference, reference);
1047         if (commit->object.flags & PARENT2)
1048                 ret = 1;
1049         clear_commit_marks(commit, all_flags);
1050         clear_commit_marks_many(nr_reference, reference, all_flags);
1051         free_commit_list(bases);
1052         return ret;
1053 }
1054
1055 /*
1056  * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
1057  */
1058 int in_merge_bases(struct commit *commit, struct commit *reference)
1059 {
1060         return in_merge_bases_many(commit, 1, &reference);
1061 }
1062
1063 struct commit_list *reduce_heads(struct commit_list *heads)
1064 {
1065         struct commit_list *p;
1066         struct commit_list *result = NULL, **tail = &result;
1067         struct commit **array;
1068         int num_head, i;
1069
1070         if (!heads)
1071                 return NULL;
1072
1073         /* Uniquify */
1074         for (p = heads; p; p = p->next)
1075                 p->item->object.flags &= ~STALE;
1076         for (p = heads, num_head = 0; p; p = p->next) {
1077                 if (p->item->object.flags & STALE)
1078                         continue;
1079                 p->item->object.flags |= STALE;
1080                 num_head++;
1081         }
1082         array = xcalloc(num_head, sizeof(*array));
1083         for (p = heads, i = 0; p; p = p->next) {
1084                 if (p->item->object.flags & STALE) {
1085                         array[i++] = p->item;
1086                         p->item->object.flags &= ~STALE;
1087                 }
1088         }
1089         num_head = remove_redundant(array, num_head);
1090         for (i = 0; i < num_head; i++)
1091                 tail = &commit_list_insert(array[i], tail)->next;
1092         free(array);
1093         return result;
1094 }
1095
1096 void reduce_heads_replace(struct commit_list **heads)
1097 {
1098         struct commit_list *result = reduce_heads(*heads);
1099         free_commit_list(*heads);
1100         *heads = result;
1101 }
1102
1103 static const char gpg_sig_header[] = "gpgsig";
1104 static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;
1105
1106 static int do_sign_commit(struct strbuf *buf, const char *keyid)
1107 {
1108         struct strbuf sig = STRBUF_INIT;
1109         int inspos, copypos;
1110         const char *eoh;
1111
1112         /* find the end of the header */
1113         eoh = strstr(buf->buf, "\n\n");
1114         if (!eoh)
1115                 inspos = buf->len;
1116         else
1117                 inspos = eoh - buf->buf + 1;
1118
1119         if (!keyid || !*keyid)
1120                 keyid = get_signing_key();
1121         if (sign_buffer(buf, &sig, keyid)) {
1122                 strbuf_release(&sig);
1123                 return -1;
1124         }
1125
1126         for (copypos = 0; sig.buf[copypos]; ) {
1127                 const char *bol = sig.buf + copypos;
1128                 const char *eol = strchrnul(bol, '\n');
1129                 int len = (eol - bol) + !!*eol;
1130
1131                 if (!copypos) {
1132                         strbuf_insert(buf, inspos, gpg_sig_header, gpg_sig_header_len);
1133                         inspos += gpg_sig_header_len;
1134                 }
1135                 strbuf_insert(buf, inspos++, " ", 1);
1136                 strbuf_insert(buf, inspos, bol, len);
1137                 inspos += len;
1138                 copypos += len;
1139         }
1140         strbuf_release(&sig);
1141         return 0;
1142 }
1143
1144 int parse_signed_commit(const struct commit *commit,
1145                         struct strbuf *payload, struct strbuf *signature)
1146 {
1147
1148         unsigned long size;
1149         const char *buffer = get_commit_buffer(commit, &size);
1150         int in_signature, saw_signature = -1;
1151         const char *line, *tail;
1152
1153         line = buffer;
1154         tail = buffer + size;
1155         in_signature = 0;
1156         saw_signature = 0;
1157         while (line < tail) {
1158                 const char *sig = NULL;
1159                 const char *next = memchr(line, '\n', tail - line);
1160
1161                 next = next ? next + 1 : tail;
1162                 if (in_signature && line[0] == ' ')
1163                         sig = line + 1;
1164                 else if (starts_with(line, gpg_sig_header) &&
1165                          line[gpg_sig_header_len] == ' ')
1166                         sig = line + gpg_sig_header_len + 1;
1167                 if (sig) {
1168                         strbuf_add(signature, sig, next - sig);
1169                         saw_signature = 1;
1170                         in_signature = 1;
1171                 } else {
1172                         if (*line == '\n')
1173                                 /* dump the whole remainder of the buffer */
1174                                 next = tail;
1175                         strbuf_add(payload, line, next - line);
1176                         in_signature = 0;
1177                 }
1178                 line = next;
1179         }
1180         unuse_commit_buffer(commit, buffer);
1181         return saw_signature;
1182 }
1183
1184 int remove_signature(struct strbuf *buf)
1185 {
1186         const char *line = buf->buf;
1187         const char *tail = buf->buf + buf->len;
1188         int in_signature = 0;
1189         const char *sig_start = NULL;
1190         const char *sig_end = NULL;
1191
1192         while (line < tail) {
1193                 const char *next = memchr(line, '\n', tail - line);
1194                 next = next ? next + 1 : tail;
1195
1196                 if (in_signature && line[0] == ' ')
1197                         sig_end = next;
1198                 else if (starts_with(line, gpg_sig_header) &&
1199                          line[gpg_sig_header_len] == ' ') {
1200                         sig_start = line;
1201                         sig_end = next;
1202                         in_signature = 1;
1203                 } else {
1204                         if (*line == '\n')
1205                                 /* dump the whole remainder of the buffer */
1206                                 next = tail;
1207                         in_signature = 0;
1208                 }
1209                 line = next;
1210         }
1211
1212         if (sig_start)
1213                 strbuf_remove(buf, sig_start - buf->buf, sig_end - sig_start);
1214
1215         return sig_start != NULL;
1216 }
1217
1218 static void handle_signed_tag(struct commit *parent, struct commit_extra_header ***tail)
1219 {
1220         struct merge_remote_desc *desc;
1221         struct commit_extra_header *mergetag;
1222         char *buf;
1223         unsigned long size, len;
1224         enum object_type type;
1225
1226         desc = merge_remote_util(parent);
1227         if (!desc || !desc->obj)
1228                 return;
1229         buf = read_object_file(&desc->obj->oid, &type, &size);
1230         if (!buf || type != OBJ_TAG)
1231                 goto free_return;
1232         len = parse_signature(buf, size);
1233         if (size == len)
1234                 goto free_return;
1235         /*
1236          * We could verify this signature and either omit the tag when
1237          * it does not validate, but the integrator may not have the
1238          * public key of the signer of the tag he is merging, while a
1239          * later auditor may have it while auditing, so let's not run
1240          * verify-signed-buffer here for now...
1241          *
1242          * if (verify_signed_buffer(buf, len, buf + len, size - len, ...))
1243          *      warn("warning: signed tag unverified.");
1244          */
1245         mergetag = xcalloc(1, sizeof(*mergetag));
1246         mergetag->key = xstrdup("mergetag");
1247         mergetag->value = buf;
1248         mergetag->len = size;
1249
1250         **tail = mergetag;
1251         *tail = &mergetag->next;
1252         return;
1253
1254 free_return:
1255         free(buf);
1256 }
1257
1258 int check_commit_signature(const struct commit *commit, struct signature_check *sigc)
1259 {
1260         struct strbuf payload = STRBUF_INIT;
1261         struct strbuf signature = STRBUF_INIT;
1262         int ret = 1;
1263
1264         sigc->result = 'N';
1265
1266         if (parse_signed_commit(commit, &payload, &signature) <= 0)
1267                 goto out;
1268         ret = check_signature(payload.buf, payload.len, signature.buf,
1269                 signature.len, sigc);
1270
1271  out:
1272         strbuf_release(&payload);
1273         strbuf_release(&signature);
1274
1275         return ret;
1276 }
1277
1278
1279
1280 void append_merge_tag_headers(struct commit_list *parents,
1281                               struct commit_extra_header ***tail)
1282 {
1283         while (parents) {
1284                 struct commit *parent = parents->item;
1285                 handle_signed_tag(parent, tail);
1286                 parents = parents->next;
1287         }
1288 }
1289
1290 static void add_extra_header(struct strbuf *buffer,
1291                              struct commit_extra_header *extra)
1292 {
1293         strbuf_addstr(buffer, extra->key);
1294         if (extra->len)
1295                 strbuf_add_lines(buffer, " ", extra->value, extra->len);
1296         else
1297                 strbuf_addch(buffer, '\n');
1298 }
1299
1300 struct commit_extra_header *read_commit_extra_headers(struct commit *commit,
1301                                                       const char **exclude)
1302 {
1303         struct commit_extra_header *extra = NULL;
1304         unsigned long size;
1305         const char *buffer = get_commit_buffer(commit, &size);
1306         extra = read_commit_extra_header_lines(buffer, size, exclude);
1307         unuse_commit_buffer(commit, buffer);
1308         return extra;
1309 }
1310
1311 void for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data)
1312 {
1313         struct commit_extra_header *extra, *to_free;
1314
1315         to_free = read_commit_extra_headers(commit, NULL);
1316         for (extra = to_free; extra; extra = extra->next) {
1317                 if (strcmp(extra->key, "mergetag"))
1318                         continue; /* not a merge tag */
1319                 fn(commit, extra, data);
1320         }
1321         free_commit_extra_headers(to_free);
1322 }
1323
1324 static inline int standard_header_field(const char *field, size_t len)
1325 {
1326         return ((len == 4 && !memcmp(field, "tree", 4)) ||
1327                 (len == 6 && !memcmp(field, "parent", 6)) ||
1328                 (len == 6 && !memcmp(field, "author", 6)) ||
1329                 (len == 9 && !memcmp(field, "committer", 9)) ||
1330                 (len == 8 && !memcmp(field, "encoding", 8)));
1331 }
1332
1333 static int excluded_header_field(const char *field, size_t len, const char **exclude)
1334 {
1335         if (!exclude)
1336                 return 0;
1337
1338         while (*exclude) {
1339                 size_t xlen = strlen(*exclude);
1340                 if (len == xlen && !memcmp(field, *exclude, xlen))
1341                         return 1;
1342                 exclude++;
1343         }
1344         return 0;
1345 }
1346
1347 static struct commit_extra_header *read_commit_extra_header_lines(
1348         const char *buffer, size_t size,
1349         const char **exclude)
1350 {
1351         struct commit_extra_header *extra = NULL, **tail = &extra, *it = NULL;
1352         const char *line, *next, *eof, *eob;
1353         struct strbuf buf = STRBUF_INIT;
1354
1355         for (line = buffer, eob = line + size;
1356              line < eob && *line != '\n';
1357              line = next) {
1358                 next = memchr(line, '\n', eob - line);
1359                 next = next ? next + 1 : eob;
1360                 if (*line == ' ') {
1361                         /* continuation */
1362                         if (it)
1363                                 strbuf_add(&buf, line + 1, next - (line + 1));
1364                         continue;
1365                 }
1366                 if (it)
1367                         it->value = strbuf_detach(&buf, &it->len);
1368                 strbuf_reset(&buf);
1369                 it = NULL;
1370
1371                 eof = memchr(line, ' ', next - line);
1372                 if (!eof)
1373                         eof = next;
1374                 else if (standard_header_field(line, eof - line) ||
1375                          excluded_header_field(line, eof - line, exclude))
1376                         continue;
1377
1378                 it = xcalloc(1, sizeof(*it));
1379                 it->key = xmemdupz(line, eof-line);
1380                 *tail = it;
1381                 tail = &it->next;
1382                 if (eof + 1 < next)
1383                         strbuf_add(&buf, eof + 1, next - (eof + 1));
1384         }
1385         if (it)
1386                 it->value = strbuf_detach(&buf, &it->len);
1387         return extra;
1388 }
1389
1390 void free_commit_extra_headers(struct commit_extra_header *extra)
1391 {
1392         while (extra) {
1393                 struct commit_extra_header *next = extra->next;
1394                 free(extra->key);
1395                 free(extra->value);
1396                 free(extra);
1397                 extra = next;
1398         }
1399 }
1400
1401 int commit_tree(const char *msg, size_t msg_len, const struct object_id *tree,
1402                 struct commit_list *parents, struct object_id *ret,
1403                 const char *author, const char *sign_commit)
1404 {
1405         struct commit_extra_header *extra = NULL, **tail = &extra;
1406         int result;
1407
1408         append_merge_tag_headers(parents, &tail);
1409         result = commit_tree_extended(msg, msg_len, tree, parents, ret,
1410                                       author, sign_commit, extra);
1411         free_commit_extra_headers(extra);
1412         return result;
1413 }
1414
1415 static int find_invalid_utf8(const char *buf, int len)
1416 {
1417         int offset = 0;
1418         static const unsigned int max_codepoint[] = {
1419                 0x7f, 0x7ff, 0xffff, 0x10ffff
1420         };
1421
1422         while (len) {
1423                 unsigned char c = *buf++;
1424                 int bytes, bad_offset;
1425                 unsigned int codepoint;
1426                 unsigned int min_val, max_val;
1427
1428                 len--;
1429                 offset++;
1430
1431                 /* Simple US-ASCII? No worries. */
1432                 if (c < 0x80)
1433                         continue;
1434
1435                 bad_offset = offset-1;
1436
1437                 /*
1438                  * Count how many more high bits set: that's how
1439                  * many more bytes this sequence should have.
1440                  */
1441                 bytes = 0;
1442                 while (c & 0x40) {
1443                         c <<= 1;
1444                         bytes++;
1445                 }
1446
1447                 /*
1448                  * Must be between 1 and 3 more bytes.  Longer sequences result in
1449                  * codepoints beyond U+10FFFF, which are guaranteed never to exist.
1450                  */
1451                 if (bytes < 1 || 3 < bytes)
1452                         return bad_offset;
1453
1454                 /* Do we *have* that many bytes? */
1455                 if (len < bytes)
1456                         return bad_offset;
1457
1458                 /*
1459                  * Place the encoded bits at the bottom of the value and compute the
1460                  * valid range.
1461                  */
1462                 codepoint = (c & 0x7f) >> bytes;
1463                 min_val = max_codepoint[bytes-1] + 1;
1464                 max_val = max_codepoint[bytes];
1465
1466                 offset += bytes;
1467                 len -= bytes;
1468
1469                 /* And verify that they are good continuation bytes */
1470                 do {
1471                         codepoint <<= 6;
1472                         codepoint |= *buf & 0x3f;
1473                         if ((*buf++ & 0xc0) != 0x80)
1474                                 return bad_offset;
1475                 } while (--bytes);
1476
1477                 /* Reject codepoints that are out of range for the sequence length. */
1478                 if (codepoint < min_val || codepoint > max_val)
1479                         return bad_offset;
1480                 /* Surrogates are only for UTF-16 and cannot be encoded in UTF-8. */
1481                 if ((codepoint & 0x1ff800) == 0xd800)
1482                         return bad_offset;
1483                 /* U+xxFFFE and U+xxFFFF are guaranteed non-characters. */
1484                 if ((codepoint & 0xfffe) == 0xfffe)
1485                         return bad_offset;
1486                 /* So are anything in the range U+FDD0..U+FDEF. */
1487                 if (codepoint >= 0xfdd0 && codepoint <= 0xfdef)
1488                         return bad_offset;
1489         }
1490         return -1;
1491 }
1492
1493 /*
1494  * This verifies that the buffer is in proper utf8 format.
1495  *
1496  * If it isn't, it assumes any non-utf8 characters are Latin1,
1497  * and does the conversion.
1498  */
1499 static int verify_utf8(struct strbuf *buf)
1500 {
1501         int ok = 1;
1502         long pos = 0;
1503
1504         for (;;) {
1505                 int bad;
1506                 unsigned char c;
1507                 unsigned char replace[2];
1508
1509                 bad = find_invalid_utf8(buf->buf + pos, buf->len - pos);
1510                 if (bad < 0)
1511                         return ok;
1512                 pos += bad;
1513                 ok = 0;
1514                 c = buf->buf[pos];
1515                 strbuf_remove(buf, pos, 1);
1516
1517                 /* We know 'c' must be in the range 128-255 */
1518                 replace[0] = 0xc0 + (c >> 6);
1519                 replace[1] = 0x80 + (c & 0x3f);
1520                 strbuf_insert(buf, pos, replace, 2);
1521                 pos += 2;
1522         }
1523 }
1524
1525 static const char commit_utf8_warn[] =
1526 N_("Warning: commit message did not conform to UTF-8.\n"
1527    "You may want to amend it after fixing the message, or set the config\n"
1528    "variable i18n.commitencoding to the encoding your project uses.\n");
1529
1530 int commit_tree_extended(const char *msg, size_t msg_len,
1531                          const struct object_id *tree,
1532                          struct commit_list *parents, struct object_id *ret,
1533                          const char *author, const char *sign_commit,
1534                          struct commit_extra_header *extra)
1535 {
1536         int result;
1537         int encoding_is_utf8;
1538         struct strbuf buffer;
1539
1540         assert_oid_type(tree, OBJ_TREE);
1541
1542         if (memchr(msg, '\0', msg_len))
1543                 return error("a NUL byte in commit log message not allowed.");
1544
1545         /* Not having i18n.commitencoding is the same as having utf-8 */
1546         encoding_is_utf8 = is_encoding_utf8(git_commit_encoding);
1547
1548         strbuf_init(&buffer, 8192); /* should avoid reallocs for the headers */
1549         strbuf_addf(&buffer, "tree %s\n", oid_to_hex(tree));
1550
1551         /*
1552          * NOTE! This ordering means that the same exact tree merged with a
1553          * different order of parents will be a _different_ changeset even
1554          * if everything else stays the same.
1555          */
1556         while (parents) {
1557                 struct commit *parent = pop_commit(&parents);
1558                 strbuf_addf(&buffer, "parent %s\n",
1559                             oid_to_hex(&parent->object.oid));
1560         }
1561
1562         /* Person/date information */
1563         if (!author)
1564                 author = git_author_info(IDENT_STRICT);
1565         strbuf_addf(&buffer, "author %s\n", author);
1566         strbuf_addf(&buffer, "committer %s\n", git_committer_info(IDENT_STRICT));
1567         if (!encoding_is_utf8)
1568                 strbuf_addf(&buffer, "encoding %s\n", git_commit_encoding);
1569
1570         while (extra) {
1571                 add_extra_header(&buffer, extra);
1572                 extra = extra->next;
1573         }
1574         strbuf_addch(&buffer, '\n');
1575
1576         /* And add the comment */
1577         strbuf_add(&buffer, msg, msg_len);
1578
1579         /* And check the encoding */
1580         if (encoding_is_utf8 && !verify_utf8(&buffer))
1581                 fprintf(stderr, _(commit_utf8_warn));
1582
1583         if (sign_commit && do_sign_commit(&buffer, sign_commit)) {
1584                 result = -1;
1585                 goto out;
1586         }
1587
1588         result = write_object_file(buffer.buf, buffer.len, commit_type, ret);
1589 out:
1590         strbuf_release(&buffer);
1591         return result;
1592 }
1593
1594 void set_merge_remote_desc(struct commit *commit,
1595                            const char *name, struct object *obj)
1596 {
1597         struct merge_remote_desc *desc;
1598         FLEX_ALLOC_STR(desc, name, name);
1599         desc->obj = obj;
1600         commit->util = desc;
1601 }
1602
1603 struct commit *get_merge_parent(const char *name)
1604 {
1605         struct object *obj;
1606         struct commit *commit;
1607         struct object_id oid;
1608         if (get_oid(name, &oid))
1609                 return NULL;
1610         obj = parse_object(&oid);
1611         commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
1612         if (commit && !commit->util)
1613                 set_merge_remote_desc(commit, name, obj);
1614         return commit;
1615 }
1616
1617 /*
1618  * Append a commit to the end of the commit_list.
1619  *
1620  * next starts by pointing to the variable that holds the head of an
1621  * empty commit_list, and is updated to point to the "next" field of
1622  * the last item on the list as new commits are appended.
1623  *
1624  * Usage example:
1625  *
1626  *     struct commit_list *list;
1627  *     struct commit_list **next = &list;
1628  *
1629  *     next = commit_list_append(c1, next);
1630  *     next = commit_list_append(c2, next);
1631  *     assert(commit_list_count(list) == 2);
1632  *     return list;
1633  */
1634 struct commit_list **commit_list_append(struct commit *commit,
1635                                         struct commit_list **next)
1636 {
1637         struct commit_list *new_commit = xmalloc(sizeof(struct commit_list));
1638         new_commit->item = commit;
1639         *next = new_commit;
1640         new_commit->next = NULL;
1641         return &new_commit->next;
1642 }
1643
1644 const char *find_commit_header(const char *msg, const char *key, size_t *out_len)
1645 {
1646         int key_len = strlen(key);
1647         const char *line = msg;
1648
1649         while (line) {
1650                 const char *eol = strchrnul(line, '\n');
1651
1652                 if (line == eol)
1653                         return NULL;
1654
1655                 if (eol - line > key_len &&
1656                     !strncmp(line, key, key_len) &&
1657                     line[key_len] == ' ') {
1658                         *out_len = eol - line - key_len - 1;
1659                         return line + key_len + 1;
1660                 }
1661                 line = *eol ? eol + 1 : NULL;
1662         }
1663         return NULL;
1664 }
1665
1666 /*
1667  * Inspect the given string and determine the true "end" of the log message, in
1668  * order to find where to put a new Signed-off-by: line.  Ignored are
1669  * trailing comment lines and blank lines.  To support "git commit -s
1670  * --amend" on an existing commit, we also ignore "Conflicts:".  To
1671  * support "git commit -v", we truncate at cut lines.
1672  *
1673  * Returns the number of bytes from the tail to ignore, to be fed as
1674  * the second parameter to append_signoff().
1675  */
1676 int ignore_non_trailer(const char *buf, size_t len)
1677 {
1678         int boc = 0;
1679         int bol = 0;
1680         int in_old_conflicts_block = 0;
1681         size_t cutoff = wt_status_locate_end(buf, len);
1682
1683         while (bol < cutoff) {
1684                 const char *next_line = memchr(buf + bol, '\n', len - bol);
1685
1686                 if (!next_line)
1687                         next_line = buf + len;
1688                 else
1689                         next_line++;
1690
1691                 if (buf[bol] == comment_line_char || buf[bol] == '\n') {
1692                         /* is this the first of the run of comments? */
1693                         if (!boc)
1694                                 boc = bol;
1695                         /* otherwise, it is just continuing */
1696                 } else if (starts_with(buf + bol, "Conflicts:\n")) {
1697                         in_old_conflicts_block = 1;
1698                         if (!boc)
1699                                 boc = bol;
1700                 } else if (in_old_conflicts_block && buf[bol] == '\t') {
1701                         ; /* a pathname in the conflicts block */
1702                 } else if (boc) {
1703                         /* the previous was not trailing comment */
1704                         boc = 0;
1705                         in_old_conflicts_block = 0;
1706                 }
1707                 bol = next_line - buf;
1708         }
1709         return boc ? len - boc : len - cutoff;
1710 }