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