#include "revision.h"
#include "notes.h"
#include "gpg-interface.h"
+#include "mergesort.h"
+#include "commit-slab.h"
+
+static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
int save_commit_buffer = 1;
const char *commit_type = "commit";
+static int commit_count;
static struct commit *check_commit(struct object *obj,
const unsigned char *sha1,
struct commit *lookup_commit(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj)
- return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
+ if (!obj) {
+ struct commit *c = alloc_commit_node();
+ c->index = commit_count++;
+ return create_object(sha1, OBJ_COMMIT, c);
+ }
if (!obj->type)
obj->type = OBJ_COMMIT;
return check_commit(obj, sha1, 0);
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 item;
}
+/*
+ * Topological sort support
+ */
+
+/* count number of children that have not been emitted */
+define_commit_slab(indegree_slab, int);
+
/*
* Performs an in-place topological sort on the list supplied.
*/
-void sort_in_topological_order(struct commit_list ** list, int lifo)
+void sort_in_topological_order(struct commit_list ** list, enum rev_sort_order sort_order)
{
struct commit_list *next, *orig = *list;
struct commit_list *work, **insert;
struct commit_list **pptr;
+ struct indegree_slab indegree;
if (!orig)
return;
*list = NULL;
+ init_indegree_slab(&indegree);
+
/* Mark them and clear the indegree */
for (next = orig; next; next = next->next) {
struct commit *commit = next->item;
- commit->indegree = 1;
+ *(indegree_slab_at(&indegree, commit)) = 1;
}
/* update the indegree */
struct commit_list * parents = next->item->parents;
while (parents) {
struct commit *parent = parents->item;
+ int *pi = indegree_slab_at(&indegree, parent);
- if (parent->indegree)
- parent->indegree++;
+ if (*pi)
+ (*pi)++;
parents = parents->next;
}
}
for (next = orig; next; next = next->next) {
struct commit *commit = next->item;
- if (commit->indegree == 1)
+ if (*(indegree_slab_at(&indegree, commit)) == 1)
insert = &commit_list_insert(commit, insert)->next;
}
/* process the list in topological order */
- if (!lifo)
+ if (sort_order != REV_SORT_IN_GRAPH_ORDER)
commit_list_sort_by_date(&work);
pptr = list;
commit = work_item->item;
for (parents = commit->parents; parents ; parents = parents->next) {
struct commit *parent = parents->item;
+ int *pi = indegree_slab_at(&indegree, parent);
- if (!parent->indegree)
+ if (!*pi)
continue;
/*
* when all their children have been emitted thereby
* guaranteeing topological order.
*/
- if (--parent->indegree == 1) {
- if (!lifo)
+ if (--(*pi) == 1) {
+ switch (sort_order) {
+ case REV_SORT_BY_COMMIT_DATE:
commit_list_insert_by_date(parent, &work);
- else
+ break;
+ default: /* REV_SORT_IN_GRAPH_ORDER */
commit_list_insert(parent, &work);
+ break;
+ }
}
}
/*
* work_item is a commit all of whose children
* have already been emitted. we can emit it now.
*/
- commit->indegree = 0;
+ *(indegree_slab_at(&indegree, commit)) = 0;
*pptr = work_item;
pptr = &work_item->next;
}
+
+ clear_indegree_slab(&indegree);
}
/* merge-base stuff */
}
/*
- * Is "commit" a decendant of one of the elements on the "with_commit" list?
+ * Is "commit" a descendant of one of the elements on the "with_commit" list?
*/
int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
{
return 0;
}
-struct commit_extra_header *read_commit_extra_header_lines(const char *buffer, size_t size,
- const char **exclude)
+static 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;
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;
+
+ /*
+ * Count how many more high bits set: that's how
+ * many more bytes this sequence should have.
+ */
+ 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;
+ }
+}
+
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";
/* 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);
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 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;
+}
+
+void print_commit_list(struct commit_list *list,
+ const char *format_cur,
+ const char *format_last)
+{
+ for ( ; list; list = list->next) {
+ const char *format = list->next ? format_cur : format_last;
+ printf(format, sha1_to_hex(list->item->object.sha1));
+ }
+}