[PATCH 5/13] Introduce --topo-order switch to git-rev-list

[Jon Seymour <jon.seymour@gmail.com>]

This patch introduces a --topo-order switch to git-rev-list.

When this --switch is specified, a minimal topological sort
weaker than the --merge-order sort is applied to the output
list.

The invariant of the resulting list is:
	a is reachable from b => ord(b) < ord(a)

Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---

 Documentation/git-rev-list.txt |    9 +++++++--
 rev-list.c                     |   27 +++++++++++++++++++++++++--
 2 files changed, 32 insertions(+), 4 deletions(-)

99d3a2318171f611f1c186a7ed4881b2f34b6b49
diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt
@@ -9,13 +9,15 @@ git-rev-list - Lists commit objects in r
 
 SYNOPSIS
 --------
-'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>
+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* ] [ *--show-breaks* ] [ *--topo-order* ] <commit>... ^<prune>...
 
 DESCRIPTION
 -----------
 Lists commit objects in reverse chronological order starting at the
 given commit, taking ancestry relationship into account.  This is
-useful to produce human-readable log output.
+useful to produce human-readable log output. If prune points are specified
+with ^<prune>... arguments, the output will not include any commits reachable
+from (and including) the prune points.
 
 If *--merge-order* is specified, the commit history is decomposed into a
 unique sequence of minimal, non-linear epochs and maximal, linear epochs.
@@ -59,6 +61,9 @@ represent an arbtirary DAG in a linear f
 
 *--show-breaks* implies **-merge-order*.
 
+If *--topo-order* is specified, the commit history is sorted in a topological
+order that is weaker than the topological order generated by *--merge-order*.
+
 Author
 ------
 Written by Linus Torvalds <torvalds@osdl.org>
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -20,6 +20,7 @@ static const char rev_list_usage[] =
 		      "  --unpacked\n"
 		      "  --header\n"
 		      "  --pretty\n"
+		      "  --topo-order\n"
 		      "  --merge-order [ --show-breaks ]";
 
 static int unpacked = 0;
@@ -38,10 +39,12 @@ static enum cmit_fmt commit_format = CMI
 static int merge_order = 0;
 static int show_breaks = 0;
 static int stop_traversal = 0;
+static int topo_order = 0;
 
 struct rev_list_fns {
 	struct commit_list * (*insert)(struct commit *, struct commit_list **);
 	struct commit_list * (*limit)(struct commit_list *);
+	void (*sort)(struct commit_list **);
 	void (*process)(struct commit_list *);
 };
 
@@ -425,12 +428,21 @@ static void merge_order_sort(struct comm
 struct rev_list_fns default_fns = {
 	&insert_by_date,
 	&limit_list,
-        &show_commit_list
+	NULL,
+	&show_commit_list
+};
+
+struct rev_list_fns topo_order_fns = {
+	&insert_by_date,
+	&limit_list,
+	&sort_in_topological_order,
+	&show_commit_list
 };
 
 struct rev_list_fns merge_order_fns = {
 	&commit_list_insert,
 	NULL,
+	NULL,
 	&merge_order_sort
 };
 
@@ -439,7 +451,7 @@ int main(int argc, char **argv)
 	struct commit_list *list = NULL;
 	struct commit_list *sorted = NULL;
 	struct commit_list **list_tail = &list;
-	struct rev_list_fns * fns = &default_fns;
+	struct rev_list_fns * fns = NULL;
 	int i, limited = 0;
 
 	for (i = 1 ; i < argc; i++) {
@@ -498,6 +510,11 @@ int main(int argc, char **argv)
 			merge_order = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--topo-order")) {
+		        topo_order = 1;
+			limited=1;
+			continue;
+		}
 
 		flags = 0;
 		if (*arg == '^') {
@@ -512,11 +529,17 @@ int main(int argc, char **argv)
 	}
 	if (merge_order)
 		fns=&merge_order_fns;
+	else if (topo_order)
+		fns=&topo_order_fns;
+	else
+		fns=&default_fns;
 	while (list)
 		fns->insert(pop_commit(&list), &sorted);
 	list=sorted;
 	if (limited && fns->limit)
 		list = fns->limit(list);
+	if (fns->sort)
+		fns->sort(&list);
 	fns->process(list);
 	return 0;
 }
------------