#include "diff.h"
#include "revision.h"
#include "notes.h"
+#include "gpg-interface.h"
+#include "mergesort.h"
int save_commit_buffer = 1;
unsigned char sha1[20];
struct commit *commit;
- if (get_sha1(name, sha1))
+ if (get_sha1_committish(name, sha1))
return NULL;
commit = lookup_commit_reference(sha1);
if (!commit || parse_commit(commit))
return commit_list_insert(item, pp);
}
+static int commit_list_compare_by_date(const void *a, const void *b)
+{
+ unsigned long a_date = ((const struct commit_list *)a)->item->date;
+ unsigned long b_date = ((const struct commit_list *)b)->item->date;
+ if (a_date < b_date)
+ return 1;
+ if (a_date > b_date)
+ return -1;
+ return 0;
+}
+
+static void *commit_list_get_next(const void *a)
+{
+ return ((const struct commit_list *)a)->next;
+}
+
+static void commit_list_set_next(void *a, void *next)
+{
+ ((struct commit_list *)a)->next = next;
+}
void commit_list_sort_by_date(struct commit_list **list)
{
- struct commit_list *ret = NULL;
- while (*list) {
- commit_list_insert_by_date((*list)->item, &ret);
- *list = (*list)->next;
- }
- *list = ret;
+ *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
+ commit_list_compare_by_date);
}
struct commit *pop_most_recent_commit(struct commit_list **list,
return ret;
}
-void clear_commit_marks(struct commit *commit, unsigned int mark)
+static void clear_commit_marks_1(struct commit_list **plist,
+ struct commit *commit, unsigned int mark)
{
while (commit) {
struct commit_list *parents;
return;
while ((parents = parents->next))
- clear_commit_marks(parents->item, mark);
+ commit_list_insert(parents->item, plist);
commit = commit->parents->item;
}
}
+void clear_commit_marks(struct commit *commit, unsigned int mark)
+{
+ struct commit_list *list = NULL;
+ commit_list_insert(commit, &list);
+ while (list)
+ clear_commit_marks_1(&list, pop_commit(&list), mark);
+}
+
void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
{
struct object *object;
return NULL;
}
-static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
{
struct commit_list *list = NULL;
struct commit_list *result = NULL;
int i;
- for (i = 0; i < n; i++) {
- if (one == twos[i])
- /*
- * We do not mark this even with RESULT so we do not
- * have to clean it up.
- */
- return commit_list_insert(one, &result);
- }
-
- if (parse_commit(one))
- return NULL;
- for (i = 0; i < n; i++) {
- if (parse_commit(twos[i]))
- return NULL;
- }
-
one->object.flags |= PARENT1;
commit_list_insert_by_date(one, &list);
for (i = 0; i < n; i++) {
}
}
- /* Clean up the result to remove stale ones */
free_commit_list(list);
- list = result; result = NULL;
+ return result;
+}
+
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
+{
+ struct commit_list *list = NULL;
+ struct commit_list *result = NULL;
+ int i;
+
+ for (i = 0; i < n; i++) {
+ if (one == twos[i])
+ /*
+ * We do not mark this even with RESULT so we do not
+ * have to clean it up.
+ */
+ return commit_list_insert(one, &result);
+ }
+
+ if (parse_commit(one))
+ return NULL;
+ for (i = 0; i < n; i++) {
+ if (parse_commit(twos[i]))
+ return NULL;
+ }
+
+ list = paint_down_to_common(one, n, twos);
+
while (list) {
struct commit_list *next = list->next;
if (!(list->item->object.flags & STALE))
return ret;
}
+static int remove_redundant(struct commit **array, int cnt)
+{
+ /*
+ * Some commit in the array may be an ancestor of
+ * another commit. Move such commit to the end of
+ * the array, and return the number of commits that
+ * are independent from each other.
+ */
+ struct commit **work;
+ unsigned char *redundant;
+ int *filled_index;
+ int i, j, filled;
+
+ work = xcalloc(cnt, sizeof(*work));
+ redundant = xcalloc(cnt, 1);
+ filled_index = xmalloc(sizeof(*filled_index) * (cnt - 1));
+
+ for (i = 0; i < cnt; i++) {
+ struct commit_list *common;
+
+ if (redundant[i])
+ continue;
+ for (j = filled = 0; j < cnt; j++) {
+ if (i == j || redundant[j])
+ continue;
+ filled_index[filled] = j;
+ work[filled++] = array[j];
+ }
+ common = paint_down_to_common(array[i], filled, work);
+ if (array[i]->object.flags & PARENT2)
+ redundant[i] = 1;
+ for (j = 0; j < filled; j++)
+ if (work[j]->object.flags & PARENT1)
+ redundant[filled_index[j]] = 1;
+ clear_commit_marks(array[i], all_flags);
+ for (j = 0; j < filled; j++)
+ clear_commit_marks(work[j], all_flags);
+ free_commit_list(common);
+ }
+
+ /* Now collect the result */
+ memcpy(work, array, sizeof(*array) * cnt);
+ for (i = filled = 0; i < cnt; i++)
+ if (!redundant[i])
+ array[filled++] = work[i];
+ for (j = filled, i = 0; i < cnt; i++)
+ if (redundant[i])
+ array[j++] = work[i];
+ free(work);
+ free(redundant);
+ free(filled_index);
+ return filled;
+}
+
struct commit_list *get_merge_bases_many(struct commit *one,
int n,
struct commit **twos,
struct commit_list *list;
struct commit **rslt;
struct commit_list *result;
- int cnt, i, j;
+ int cnt, i;
result = merge_bases_many(one, n, twos);
for (i = 0; i < n; i++) {
clear_commit_marks(one, all_flags);
for (i = 0; i < n; i++)
clear_commit_marks(twos[i], all_flags);
- for (i = 0; i < cnt - 1; i++) {
- for (j = i+1; j < cnt; j++) {
- if (!rslt[i] || !rslt[j])
- continue;
- result = merge_bases_many(rslt[i], 1, &rslt[j]);
- clear_commit_marks(rslt[i], all_flags);
- clear_commit_marks(rslt[j], all_flags);
- for (list = result; list; list = list->next) {
- if (rslt[i] == list->item)
- rslt[i] = NULL;
- if (rslt[j] == list->item)
- rslt[j] = NULL;
- }
- }
- }
- /* Surviving ones in rslt[] are the independent results */
+ cnt = remove_redundant(rslt, cnt);
result = NULL;
- for (i = 0; i < cnt; i++) {
- if (rslt[i])
- commit_list_insert_by_date(rslt[i], &result);
- }
+ for (i = 0; i < cnt; i++)
+ commit_list_insert_by_date(rslt[i], &result);
free(rslt);
return result;
}
return get_merge_bases_many(one, 1, &two, cleanup);
}
+/*
+ * Is "commit" a decendant of one of the elements on the "with_commit" list?
+ */
int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
{
if (!with_commit)
other = with_commit->item;
with_commit = with_commit->next;
- if (in_merge_bases(other, &commit, 1))
+ if (in_merge_bases(other, commit))
return 1;
}
return 0;
}
-int in_merge_bases(struct commit *commit, struct commit **reference, int num)
+/*
+ * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
+ */
+int in_merge_bases(struct commit *commit, struct commit *reference)
{
- struct commit_list *bases, *b;
+ struct commit_list *bases;
int ret = 0;
- if (num == 1)
- bases = get_merge_bases(commit, *reference, 1);
- else
- die("not yet");
- for (b = bases; b; b = b->next) {
- if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {
- ret = 1;
- break;
- }
- }
+ if (parse_commit(commit) || parse_commit(reference))
+ return ret;
+ bases = paint_down_to_common(commit, 1, &reference);
+ if (commit->object.flags & PARENT2)
+ ret = 1;
+ clear_commit_marks(commit, all_flags);
+ clear_commit_marks(reference, all_flags);
free_commit_list(bases);
return ret;
}
{
struct commit_list *p;
struct commit_list *result = NULL, **tail = &result;
- struct commit **other;
- size_t num_head, num_other;
+ struct commit **array;
+ int num_head, i;
if (!heads)
return NULL;
- /* Avoid unnecessary reallocations */
- for (p = heads, num_head = 0; p; p = p->next)
+ /* Uniquify */
+ for (p = heads; p; p = p->next)
+ p->item->object.flags &= ~STALE;
+ for (p = heads, num_head = 0; p; p = p->next) {
+ if (p->item->object.flags & STALE)
+ continue;
+ p->item->object.flags |= STALE;
num_head++;
- other = xcalloc(sizeof(*other), num_head);
+ }
+ array = xcalloc(sizeof(*array), num_head);
+ for (p = heads, i = 0; p; p = p->next) {
+ if (p->item->object.flags & STALE) {
+ array[i++] = p->item;
+ p->item->object.flags &= ~STALE;
+ }
+ }
+ num_head = remove_redundant(array, num_head);
+ for (i = 0; i < num_head; i++)
+ tail = &commit_list_insert(array[i], tail)->next;
+ return result;
+}
- /* For each commit, see if it can be reached by others */
- for (p = heads; p; p = p->next) {
- struct commit_list *q, *base;
+static const char gpg_sig_header[] = "gpgsig";
+static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;
- /* Do we already have this in the result? */
- for (q = result; q; q = q->next)
- if (p->item == q->item)
- break;
- if (q)
- continue;
+static int do_sign_commit(struct strbuf *buf, const char *keyid)
+{
+ struct strbuf sig = STRBUF_INIT;
+ int inspos, copypos;
- num_other = 0;
- for (q = heads; q; q = q->next) {
- if (p->item == q->item)
- continue;
- other[num_other++] = q->item;
+ /* find the end of the header */
+ inspos = strstr(buf->buf, "\n\n") - buf->buf + 1;
+
+ if (!keyid || !*keyid)
+ keyid = get_signing_key();
+ if (sign_buffer(buf, &sig, keyid)) {
+ strbuf_release(&sig);
+ return -1;
+ }
+
+ for (copypos = 0; sig.buf[copypos]; ) {
+ const char *bol = sig.buf + copypos;
+ const char *eol = strchrnul(bol, '\n');
+ int len = (eol - bol) + !!*eol;
+
+ if (!copypos) {
+ strbuf_insert(buf, inspos, gpg_sig_header, gpg_sig_header_len);
+ inspos += gpg_sig_header_len;
}
- if (num_other)
- base = get_merge_bases_many(p->item, num_other, other, 1);
- else
- base = NULL;
+ strbuf_insert(buf, inspos++, " ", 1);
+ strbuf_insert(buf, inspos, bol, len);
+ inspos += len;
+ copypos += len;
+ }
+ strbuf_release(&sig);
+ return 0;
+}
+
+int parse_signed_commit(const unsigned char *sha1,
+ struct strbuf *payload, struct strbuf *signature)
+{
+ unsigned long size;
+ enum object_type type;
+ char *buffer = read_sha1_file(sha1, &type, &size);
+ int in_signature, saw_signature = -1;
+ char *line, *tail;
+
+ if (!buffer || type != OBJ_COMMIT)
+ goto cleanup;
+
+ line = buffer;
+ tail = buffer + size;
+ in_signature = 0;
+ saw_signature = 0;
+ while (line < tail) {
+ const char *sig = NULL;
+ char *next = memchr(line, '\n', tail - line);
+
+ next = next ? next + 1 : tail;
+ if (in_signature && line[0] == ' ')
+ sig = line + 1;
+ else if (!prefixcmp(line, gpg_sig_header) &&
+ line[gpg_sig_header_len] == ' ')
+ sig = line + gpg_sig_header_len + 1;
+ if (sig) {
+ strbuf_add(signature, sig, next - sig);
+ saw_signature = 1;
+ in_signature = 1;
+ } else {
+ if (*line == '\n')
+ /* dump the whole remainder of the buffer */
+ next = tail;
+ strbuf_add(payload, line, next - line);
+ in_signature = 0;
+ }
+ line = next;
+ }
+ cleanup:
+ free(buffer);
+ return saw_signature;
+}
+
+static void handle_signed_tag(struct commit *parent, struct commit_extra_header ***tail)
+{
+ struct merge_remote_desc *desc;
+ struct commit_extra_header *mergetag;
+ char *buf;
+ unsigned long size, len;
+ enum object_type type;
+
+ desc = merge_remote_util(parent);
+ if (!desc || !desc->obj)
+ return;
+ buf = read_sha1_file(desc->obj->sha1, &type, &size);
+ if (!buf || type != OBJ_TAG)
+ goto free_return;
+ len = parse_signature(buf, size);
+ if (size == len)
+ goto free_return;
+ /*
+ * We could verify this signature and either omit the tag when
+ * it does not validate, but the integrator may not have the
+ * public key of the signer of the tag he is merging, while a
+ * later auditor may have it while auditing, so let's not run
+ * verify-signed-buffer here for now...
+ *
+ * if (verify_signed_buffer(buf, len, buf + len, size - len, ...))
+ * warn("warning: signed tag unverified.");
+ */
+ mergetag = xcalloc(1, sizeof(*mergetag));
+ mergetag->key = xstrdup("mergetag");
+ mergetag->value = buf;
+ mergetag->len = size;
+
+ **tail = mergetag;
+ *tail = &mergetag->next;
+ return;
+
+free_return:
+ free(buf);
+}
+
+void append_merge_tag_headers(struct commit_list *parents,
+ struct commit_extra_header ***tail)
+{
+ while (parents) {
+ struct commit *parent = parents->item;
+ handle_signed_tag(parent, tail);
+ parents = parents->next;
+ }
+}
+
+static void add_extra_header(struct strbuf *buffer,
+ struct commit_extra_header *extra)
+{
+ strbuf_addstr(buffer, extra->key);
+ if (extra->len)
+ strbuf_add_lines(buffer, " ", extra->value, extra->len);
+ else
+ strbuf_addch(buffer, '\n');
+}
+
+struct commit_extra_header *read_commit_extra_headers(struct commit *commit,
+ const char **exclude)
+{
+ struct commit_extra_header *extra = NULL;
+ unsigned long size;
+ enum object_type type;
+ char *buffer = read_sha1_file(commit->object.sha1, &type, &size);
+ if (buffer && type == OBJ_COMMIT)
+ extra = read_commit_extra_header_lines(buffer, size, exclude);
+ free(buffer);
+ return extra;
+}
+
+static inline int standard_header_field(const char *field, size_t len)
+{
+ return ((len == 4 && !memcmp(field, "tree ", 5)) ||
+ (len == 6 && !memcmp(field, "parent ", 7)) ||
+ (len == 6 && !memcmp(field, "author ", 7)) ||
+ (len == 9 && !memcmp(field, "committer ", 10)) ||
+ (len == 8 && !memcmp(field, "encoding ", 9)));
+}
+
+static int excluded_header_field(const char *field, size_t len, const char **exclude)
+{
+ if (!exclude)
+ return 0;
+
+ while (*exclude) {
+ size_t xlen = strlen(*exclude);
+ if (len == xlen &&
+ !memcmp(field, *exclude, xlen) && field[xlen] == ' ')
+ return 1;
+ exclude++;
+ }
+ return 0;
+}
+
+struct commit_extra_header *read_commit_extra_header_lines(const char *buffer, size_t size,
+ const char **exclude)
+{
+ struct commit_extra_header *extra = NULL, **tail = &extra, *it = NULL;
+ const char *line, *next, *eof, *eob;
+ struct strbuf buf = STRBUF_INIT;
+
+ for (line = buffer, eob = line + size;
+ line < eob && *line != '\n';
+ line = next) {
+ next = memchr(line, '\n', eob - line);
+ next = next ? next + 1 : eob;
+ if (*line == ' ') {
+ /* continuation */
+ if (it)
+ strbuf_add(&buf, line + 1, next - (line + 1));
+ continue;
+ }
+ if (it)
+ it->value = strbuf_detach(&buf, &it->len);
+ strbuf_reset(&buf);
+ it = NULL;
+
+ eof = strchr(line, ' ');
+ if (next <= eof)
+ eof = next;
+
+ if (standard_header_field(line, eof - line) ||
+ excluded_header_field(line, eof - line, exclude))
+ continue;
+
+ it = xcalloc(1, sizeof(*it));
+ it->key = xmemdupz(line, eof-line);
+ *tail = it;
+ tail = &it->next;
+ if (eof + 1 < next)
+ strbuf_add(&buf, eof + 1, next - (eof + 1));
+ }
+ if (it)
+ it->value = strbuf_detach(&buf, &it->len);
+ return extra;
+}
+
+void free_commit_extra_headers(struct commit_extra_header *extra)
+{
+ while (extra) {
+ struct commit_extra_header *next = extra->next;
+ free(extra->key);
+ free(extra->value);
+ free(extra);
+ extra = next;
+ }
+}
+
+int commit_tree(const struct strbuf *msg, unsigned char *tree,
+ struct commit_list *parents, unsigned char *ret,
+ const char *author, const char *sign_commit)
+{
+ struct commit_extra_header *extra = NULL, **tail = &extra;
+ int result;
+
+ append_merge_tag_headers(parents, &tail);
+ result = commit_tree_extended(msg, tree, parents, ret,
+ author, sign_commit, extra);
+ free_commit_extra_headers(extra);
+ return result;
+}
+
+static int find_invalid_utf8(const char *buf, int len)
+{
+ int offset = 0;
+
+ while (len) {
+ unsigned char c = *buf++;
+ int bytes, bad_offset;
+
+ len--;
+ offset++;
+
+ /* Simple US-ASCII? No worries. */
+ if (c < 0x80)
+ continue;
+
+ bad_offset = offset-1;
+
/*
- * If p->item does not have anything common with other
- * commits, there won't be any merge base. If it is
- * reachable from some of the others, p->item will be
- * the merge base. If its history is connected with
- * others, but p->item is not reachable by others, we
- * will get something other than p->item back.
+ * Count how many more high bits set: that's how
+ * many more bytes this sequence should have.
*/
- if (!base || (base->item != p->item))
- tail = &(commit_list_insert(p->item, tail)->next);
- free_commit_list(base);
+ bytes = 0;
+ while (c & 0x40) {
+ c <<= 1;
+ bytes++;
+ }
+
+ /* Must be between 1 and 5 more bytes */
+ if (bytes < 1 || bytes > 5)
+ return bad_offset;
+
+ /* Do we *have* that many bytes? */
+ if (len < bytes)
+ return bad_offset;
+
+ offset += bytes;
+ len -= bytes;
+
+ /* And verify that they are good continuation bytes */
+ do {
+ if ((*buf++ & 0xc0) != 0x80)
+ return bad_offset;
+ } while (--bytes);
+
+ /* We could/should check the value and length here too */
+ }
+ return -1;
+}
+
+/*
+ * This verifies that the buffer is in proper utf8 format.
+ *
+ * If it isn't, it assumes any non-utf8 characters are Latin1,
+ * and does the conversion.
+ *
+ * Fixme: we should probably also disallow overlong forms and
+ * invalid characters. But we don't do that currently.
+ */
+static int verify_utf8(struct strbuf *buf)
+{
+ int ok = 1;
+ long pos = 0;
+
+ for (;;) {
+ int bad;
+ unsigned char c;
+ unsigned char replace[2];
+
+ bad = find_invalid_utf8(buf->buf + pos, buf->len - pos);
+ if (bad < 0)
+ return ok;
+ pos += bad;
+ ok = 0;
+ c = buf->buf[pos];
+ strbuf_remove(buf, pos, 1);
+
+ /* We know 'c' must be in the range 128-255 */
+ replace[0] = 0xc0 + (c >> 6);
+ replace[1] = 0x80 + (c & 0x3f);
+ strbuf_insert(buf, pos, replace, 2);
+ pos += 2;
}
- free(other);
- return result;
}
static const char commit_utf8_warn[] =
-"Warning: commit message does not conform to UTF-8.\n"
+"Warning: commit message did not conform to UTF-8.\n"
"You may want to amend it after fixing the message, or set the config\n"
"variable i18n.commitencoding to the encoding your project uses.\n";
-int commit_tree(const char *msg, unsigned char *tree,
- struct commit_list *parents, unsigned char *ret,
- const char *author)
+int commit_tree_extended(const struct strbuf *msg, unsigned char *tree,
+ struct commit_list *parents, unsigned char *ret,
+ const char *author, const char *sign_commit,
+ struct commit_extra_header *extra)
{
int result;
int encoding_is_utf8;
assert_sha1_type(tree, OBJ_TREE);
+ if (memchr(msg->buf, '\0', msg->len))
+ return error("a NUL byte in commit log message not allowed.");
+
/* Not having i18n.commitencoding is the same as having utf-8 */
encoding_is_utf8 = is_encoding_utf8(git_commit_encoding);
*/
while (parents) {
struct commit_list *next = parents->next;
+ struct commit *parent = parents->item;
+
strbuf_addf(&buffer, "parent %s\n",
- sha1_to_hex(parents->item->object.sha1));
+ sha1_to_hex(parent->object.sha1));
free(parents);
parents = next;
}
/* Person/date information */
if (!author)
- author = git_author_info(IDENT_ERROR_ON_NO_NAME);
+ author = git_author_info(IDENT_STRICT);
strbuf_addf(&buffer, "author %s\n", author);
- strbuf_addf(&buffer, "committer %s\n", git_committer_info(IDENT_ERROR_ON_NO_NAME));
+ strbuf_addf(&buffer, "committer %s\n", git_committer_info(IDENT_STRICT));
if (!encoding_is_utf8)
strbuf_addf(&buffer, "encoding %s\n", git_commit_encoding);
+
+ while (extra) {
+ add_extra_header(&buffer, extra);
+ extra = extra->next;
+ }
strbuf_addch(&buffer, '\n');
/* And add the comment */
- strbuf_addstr(&buffer, msg);
+ strbuf_addbuf(&buffer, msg);
/* And check the encoding */
- if (encoding_is_utf8 && !is_utf8(buffer.buf))
+ if (encoding_is_utf8 && !verify_utf8(&buffer))
fprintf(stderr, commit_utf8_warn);
+ if (sign_commit && do_sign_commit(&buffer, sign_commit))
+ return -1;
+
result = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);
strbuf_release(&buffer);
return result;
}
+
+struct commit *get_merge_parent(const char *name)
+{
+ struct object *obj;
+ struct commit *commit;
+ unsigned char sha1[20];
+ if (get_sha1(name, sha1))
+ return NULL;
+ obj = parse_object(sha1);
+ commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+ if (commit && !commit->util) {
+ struct merge_remote_desc *desc;
+ desc = xmalloc(sizeof(*desc));
+ desc->obj = obj;
+ desc->name = strdup(name);
+ commit->util = desc;
+ }
+ return commit;
+}
+
+/*
+ * Append a commit to the end of the commit_list.
+ *
+ * next starts by pointing to the variable that holds the head of an
+ * empty commit_list, and is updated to point to the "next" field of
+ * the last item on the list as new commits are appended.
+ *
+ * Usage example:
+ *
+ * struct commit_list *list;
+ * struct commit_list **next = &list;
+ *
+ * next = commit_list_append(c1, next);
+ * next = commit_list_append(c2, next);
+ * assert(commit_list_count(list) == 2);
+ * return list;
+ */
+struct commit_list **commit_list_append(struct commit *commit,
+ struct commit_list **next)
+{
+ struct commit_list *new = xmalloc(sizeof(struct commit_list));
+ new->item = commit;
+ *next = new;
+ new->next = NULL;
+ return &new->next;
+}