[PATCH/RFC] rev-list: add --authorship-order alternative ordering

[elliottcable <me@ell.io>]

--date-order is an excellent alternative to --topo-order if you want a feel for
the *actual history*, chronologically, of your project. I use it often, with
--graph as well; it's a great way to get an overview of a project's recent
development history.

However, in a project that rebases various in-development topic-branches often,
it gets hard to demonstrate a *chronological history* of changes to the
codebase, as this always “resets” the COMMITTER_DATE (which --date-order uses)
to the time the rebase happened; which often means ‘last time all of the
topic-branches were rebased on the latest fixes in master.’

Thus, I've added an --authorship-order version of --date-order, which relies
upon the AUTHOR_DATE instead of the COMMITTER_DATE; this means that old commits
will continue to show up chronologically in-order despite rebasing.
---
 builtin/log.c                          |  2 +-
 builtin/rev-list.c                     |  1 +
 builtin/rev-parse.c                    |  1 +
 builtin/show-branch.c                  | 12 ++++-
 commit.c                               | 83 ++++++++++++++++++++++++++++++----
 commit.h                               |  3 +-
 contrib/completion/git-completion.bash |  4 +-
 po/de.po                               |  4 +-
 po/git.pot                             |  2 +-
 po/sv.po                               |  4 +-
 po/vi.po                               |  4 +-
 po/zh_CN.po                            |  4 +-
 revision.c                             | 11 ++++-
 revision.h                             |  1 +
 14 files changed, 110 insertions(+), 26 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 9e21232..54d4d7f 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -237,7 +237,7 @@ static void log_show_early(struct rev_info *revs, struct commit_list *list)
 	int i = revs->early_output;
 	int show_header = 1;
 
-	sort_in_topological_order(&list, revs->lifo);
+	sort_in_topological_order(&list, revs->lifo, revs->use_author);
 	while (list && i) {
 		struct commit *commit = list->item;
 		switch (simplify_commit(revs, commit)) {
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 67701be..cfa5d1f 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -30,6 +30,7 @@ static const char rev_list_usage[] =
 "  ordering output:\n"
 "    --topo-order\n"
 "    --date-order\n"
+"    --authorship-order\n"
 "    --reverse\n"
 "  formatting output:\n"
 "    --parents\n"
diff --git a/builtin/rev-parse.c b/builtin/rev-parse.c
index f267a1d..d08aebd 100644
--- a/builtin/rev-parse.c
+++ b/builtin/rev-parse.c
@@ -65,6 +65,7 @@ static int is_rev_argument(const char *arg)
 		"--tags",
 		"--topo-order",
 		"--date-order",
+		"--authorship-order",
 		"--unpacked",
 		NULL
 	};
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index 90fc6b1..ac06ac3 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -6,7 +6,7 @@
 #include "parse-options.h"
 
 static const char* show_branch_usage[] = {
-    N_("git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | <glob>)...]"),
+    N_("git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | <glob>)...]"),
     N_("git show-branch (-g|--reflog)[=<n>[,<base>]] [--list] [<ref>]"),
     NULL
 };
@@ -631,6 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 	int all_heads = 0, all_remotes = 0;
 	int all_mask, all_revs;
 	int lifo = 1;
+	int use_author = 0;
 	char head[128];
 	const char *head_p;
 	int head_len;
@@ -667,6 +668,8 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 			    N_("show refs unreachable from any other ref")),
 		OPT_BOOLEAN(0, "topo-order", &lifo,
 			    N_("show commits in topological order")),
+		OPT_BOOLEAN(0, "authorship-order", &use_author,
+			    N_("like --date-order, but with the *author* date")),
 		OPT_BOOLEAN(0, "topics", &topics,
 			    N_("show only commits not on the first branch")),
 		OPT_SET_INT(0, "sparse", &dense,
@@ -694,6 +697,11 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 			   show_branch_usage, PARSE_OPT_STOP_AT_NON_OPTION);
 	if (all_heads)
 		all_remotes = 1;
+	/* I'm having trouble figuring out exactly what `lifo` stores. Why do both 'date-order' and
+	 * 'topo-order' set the same variable!? Aren't they mutually exclusive? Since *both* set it, for
+	 * the moment, I'm going to set it for '--authorship-order'; but that seems counterintuitive. */
+	if (use_author)
+		lifo = 1;
 
 	if (extra || reflog) {
 		/* "listing" mode is incompatible with
@@ -900,7 +908,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 		exit(0);
 
 	/* Sort topologically */
-	sort_in_topological_order(&seen, lifo);
+	sort_in_topological_order(&seen, lifo, use_author);
 
 	/* Give names to commits */
 	if (!sha1_name && !no_name)
diff --git a/commit.c b/commit.c
index 888e02a..b8a0f60 100644
--- a/commit.c
+++ b/commit.c
@@ -78,7 +78,34 @@ struct commit *lookup_commit_reference_by_name(const char *name)
 	return commit;
 }
 
-static unsigned long parse_commit_date(const char *buf, const char *tail)
+static unsigned long parse_commit_author_date(const char *buf, const char *tail)
+{
+	const char *dateptr;
+
+	if (buf + 6 >= tail)
+		return 0;
+	if (memcmp(buf, "author", 6))
+		return 0;
+	while (buf < tail && *buf++ != '>')
+		/* nada */;
+	if (buf >= tail)
+		return 0;
+	dateptr = buf;
+	while (buf < tail && *buf++ != '\n')
+		/* nada */;
+	if (buf + 9 >= tail)
+		return 0;
+	if (memcmp(buf, "committer", 9))
+		return 0;
+	while (buf < tail && *buf++ != '\n')
+		/* nada */;
+	if (buf >= tail)
+		return 0;
+	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
+	return strtoul(dateptr, NULL, 10);
+}
+
+static unsigned long parse_commit_committer_date(const char *buf, const char *tail)
 {
 	const char *dateptr;
 
@@ -301,7 +328,8 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 			pptr = &commit_list_insert(new_parent, pptr)->next;
 		}
 	}
-	item->date = parse_commit_date(bufptr, tail);
+	item->date = parse_commit_committer_date(bufptr, tail);
+	item->author_date = parse_commit_author_date(bufptr, tail);
 
 	return 0;
 }
@@ -380,6 +408,19 @@ void free_commit_list(struct commit_list *list)
 	}
 }
 
+struct commit_list * commit_list_insert_by_author_date(struct commit *item, struct commit_list **list)
+{
+	struct commit_list **pp = list;
+	struct commit_list *p;
+	while ((p = *pp) != NULL) {
+		if (p->item->author_date < item->author_date) {
+			break;
+		}
+		pp = &p->next;
+	}
+	return commit_list_insert(item, pp);
+}
+
 struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list)
 {
 	struct commit_list **pp = list;
@@ -393,6 +434,17 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm
 	return commit_list_insert(item, pp);
 }
 
+static int commit_list_compare_by_author_date(const void *a, const void *b)
+{
+	unsigned long a_date = ((const struct commit_list *)a)->item->author_date;
+	unsigned long b_date = ((const struct commit_list *)b)->item->author_date;
+	if (a_date < b_date)
+		return 1;
+	if (a_date > b_date)
+		return -1;
+	return 0;
+}
+
 static int commit_list_compare_by_date(const void *a, const void *b)
 {
 	unsigned long a_date = ((const struct commit_list *)a)->item->date;
@@ -414,6 +466,12 @@ static void commit_list_set_next(void *a, void *next)
 	((struct commit_list *)a)->next = next;
 }
 
+void commit_list_sort_by_author_date(struct commit_list **list)
+{
+	*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
+				commit_list_compare_by_author_date);
+}
+
 void commit_list_sort_by_date(struct commit_list **list)
 {
 	*list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
@@ -509,7 +567,7 @@ struct commit *pop_commit(struct commit_list **stack)
 /*
  * 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, int lifo, int use_author)
 {
 	struct commit_list *next, *orig = *list;
 	struct commit_list *work, **insert;
@@ -554,8 +612,12 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	}
 
 	/* process the list in topological order */
-	if (!lifo)
-		commit_list_sort_by_date(&work);
+	if (!lifo) {
+		if (use_author)
+			commit_list_sort_by_author_date(&work);
+		else
+			commit_list_sort_by_date(&work);
+	}
 
 	pptr = list;
 	*list = NULL;
@@ -580,10 +642,13 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * guaranteeing topological order.
 			 */
 			if (--parent->indegree == 1) {
-				if (!lifo)
-					commit_list_insert_by_date(parent, &work);
-				else
-					commit_list_insert(parent, &work);
+				if (!lifo) {
+					if (use_author)
+						commit_list_insert_by_author_date(parent, &work);
+					else
+						commit_list_insert_by_date(parent, &work);
+				} else {
+					commit_list_insert(parent, &work); }
 			}
 		}
 		/*
diff --git a/commit.h b/commit.h
index 67bd509..de07525 100644
--- a/commit.h
+++ b/commit.h
@@ -17,6 +17,7 @@ struct commit {
 	void *util;
 	unsigned int indegree;
 	unsigned long date;
+	unsigned long author_date;
 	struct commit_list *parents;
 	struct tree *tree;
 	char *buffer;
@@ -150,7 +151,7 @@ void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);
  *   in addition, when lifo == 0, commits on parallel tracks are
  *   sorted in the dates order.
  */
-void sort_in_topological_order(struct commit_list ** list, int lifo);
+void sort_in_topological_order(struct commit_list ** list, int lifo, int use_author);
 
 struct commit_graft {
 	unsigned char sha1[20];
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 91234d4..f051e53 100644
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -1445,7 +1445,7 @@ _git_log ()
 			$__git_log_common_options
 			$__git_log_shortlog_options
 			$__git_log_gitk_options
-			--root --topo-order --date-order --reverse
+			--root --topo-order --date-order --authorship-order --reverse
 			--follow --full-diff
 			--abbrev-commit --abbrev=
 			--relative-date --date=
@@ -2291,7 +2291,7 @@ _git_show_branch ()
 	case "$cur" in
 	--*)
 		__gitcomp "
-			--all --remotes --topo-order --current --more=
+			--all --remotes --topo-order --authorship-order --current --more=
 			--list --independent --merge-base --no-name
 			--color --no-color
 			--sha1-name --sparse --topics --reflog
diff --git a/po/de.po b/po/de.po
index 4901488..0dc184f 100644
--- a/po/de.po
+++ b/po/de.po
@@ -8716,12 +8716,12 @@ msgstr "Ausgabe mit Zeilenumbrüchen"
 
 #: builtin/show-branch.c:9
 msgid ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
 msgstr ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<Wann>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] "
 "[(<Revision> | <glob>)...]"
diff --git a/po/git.pot b/po/git.pot
index 4a9d4ef..325348d 100644
--- a/po/git.pot
+++ b/po/git.pot
@@ -8123,7 +8123,7 @@ msgstr ""
 
 #: builtin/show-branch.c:9
 msgid ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
diff --git a/po/sv.po b/po/sv.po
index a5c88c9..5091224 100644
--- a/po/sv.po
+++ b/po/sv.po
@@ -8478,12 +8478,12 @@ msgstr "Radbryt utdata"
 
 #: builtin/show-branch.c:9
 msgid ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
 msgstr ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<när>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<mönster>)...]"
diff --git a/po/vi.po b/po/vi.po
index c6af8d5..ec41ff8 100644
--- a/po/vi.po
+++ b/po/vi.po
@@ -8622,12 +8622,12 @@ msgstr "Ngắt dòng khi quá dài"
 
 #: builtin/show-branch.c:9
 msgid ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
 msgstr ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<khi>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
diff --git a/po/zh_CN.po b/po/zh_CN.po
index ba757d9..a666aed 100644
--- a/po/zh_CN.po
+++ b/po/zh_CN.po
@@ -8446,12 +8446,12 @@ msgstr "折行输出"
 
 #: builtin/show-branch.c:9
 msgid ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
 msgstr ""
-"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order] [--"
+"git show-branch [-a|--all] [-r|--remotes] [--topo-order | --date-order | --authorship-order] [--"
 "current] [--color[=<when>] | --no-color] [--sparse] [--more=<n> | --list | --"
 "independent | --merge-base] [--no-name | --sha1-name] [--topics] [(<rev> | "
 "<glob>)...]"
diff --git a/revision.c b/revision.c
index 518cd08..2d077ce 100644
--- a/revision.c
+++ b/revision.c
@@ -1053,6 +1053,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)
 	revs->pruning.add_remove = file_add_remove;
 	revs->pruning.change = file_change;
 	revs->lifo = 1;
+	revs->use_author = 0;
 	revs->dense = 1;
 	revs->prefix = prefix;
 	revs->max_age = -1;
@@ -1394,6 +1395,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--topo-order")) {
 		revs->lifo = 1;
 		revs->topo_order = 1;
+		revs->use_author = 0;
 	} else if (!strcmp(arg, "--simplify-merges")) {
 		revs->simplify_merges = 1;
 		revs->topo_order = 1;
@@ -1412,6 +1414,11 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--date-order")) {
 		revs->lifo = 0;
 		revs->topo_order = 1;
+		revs->use_author = 0;
+	} else if (!strcmp(arg, "--authorship-order")) {
+		revs->lifo = 0;
+		revs->topo_order = 1;
+		revs->use_author = 1;
 	} else if (!prefixcmp(arg, "--early-output")) {
 		int count = 100;
 		switch (arg[14]) {
@@ -2191,7 +2198,7 @@ int prepare_revision_walk(struct rev_info *revs)
 		if (limit_list(revs) < 0)
 			return -1;
 	if (revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->lifo);
+		sort_in_topological_order(&revs->commits, revs->lifo, revs->use_author);
 	if (revs->line_level_traverse)
 		line_log_filter(revs);
 	if (revs->simplify_merges)
@@ -2503,7 +2510,7 @@ static void create_boundary_commit_list(struct rev_info *revs)
 	 * If revs->topo_order is set, sort the boundary commits
 	 * in topological order
 	 */
-	sort_in_topological_order(&revs->commits, revs->lifo);
+	sort_in_topological_order(&revs->commits, revs->lifo, revs->use_author);
 }
 
 static struct commit *get_revision_internal(struct rev_info *revs)
diff --git a/revision.h b/revision.h
index a313a13..09effab 100644
--- a/revision.h
+++ b/revision.h
@@ -73,6 +73,7 @@ struct rev_info {
 			simplify_history:1,
 			lifo:1,
 			topo_order:1,
+			use_author:1,
 			simplify_merges:1,
 			simplify_by_decoration:1,
 			tag_objects:1,
-- 
1.8.1.3