git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 1/4] toposort: rename "lifo" field

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 9, 2013, 23:24 UTC
Message-ID
<1370820277-30158-2-git-send-email-gitster@pobox.com>
In-Reply-To
<1370820277-30158-1-git-send-email-gitster@pobox.com>

The primary invariant of sort_in_topological_order() is that a parent commit is not emitted untile all children of it are. When traversing a forked history like this with "git log C E":

    A----B----C
     \
      D----E

we ensure that A is emitted after all of B, C, D, and E are done, B has to wait until C is done, and D has to wait until E is done.

In some applications, however, we would further want to control how these child commits B, C, D and E on two parallel ancestry chains are shown.

Most of the time, we would want to see C and B emitted together, and then E and D, and finally A (i.e. the --topo-order output). The "lifo" parameter of the sort_in_topological_order() function is used to control this behaviour. We start the traversal by knowing two commits, C and E. While keeping in mind that we also need to inspect E later, we pick C first to inspect, and we notice and record that B needs to be inspected. By structuring the "work to be done" set as a LIFO stack, we ensure that B is inspected next, before other in-flight commits we had known that we will need to inspect, e.g. E.

When showing in --date-order, we would want to see commits ordered by timestamps, i.e. show C, E, B and D in this order before showing A, possibly mixing commits from two parallel histories together. When "lifo" parameter is set to false, the function keeps the "work to be done" set sorted in the date order to realize this semantics. After inspecting C, we add B to the "work to be done" set, but the next commit we inspect from the set is E which is newer than B.

The name "lifo", however, is too strongly tied to the way how the function implements its behaviour, and does not describe what the behaviour _means_.

Replace this field with an enum rev_sort_order, with two possible values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and update the existing code. The mechanical replacement rule is:

  "lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
  "lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/log.c         |  2 +-
 builtin/show-branch.c | 14 ++++++++------
 commit.c              | 12 ++++++++----
 commit.h              | 14 +++++++++++---
 revision.c            | 10 +++++-----
 revision.h            |  6 +++++-
 6 files changed, 38 insertions(+), 20 deletions(-)
diff --git a/builtin/log.c b/builtin/log.c
index 8f0b2e8..8d26042 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -205,7 +205,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->sort_order);
 	while (list && i) {
 		struct commit *commit = list->item;
 		switch (simplify_commit(revs, commit)) {
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index d208fd6..7c57985 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -631,7 +631,7 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 	int num_rev, i, extra = 0;
 	int all_heads = 0, all_remotes = 0;
 	int all_mask, all_revs;
-	int lifo = 1;
+	enum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;
 	char head[128];
 	const char *head_p;
 	int head_len;
@@ -666,15 +666,17 @@ int cmd_show_branch(int ac, const char **av, const char *prefix)
 			    N_("show possible merge bases")),
 		OPT_BOOLEAN(0, "independent", &independent,
 			    N_("show refs unreachable from any other ref")),
-		OPT_BOOLEAN(0, "topo-order", &lifo,
-			    N_("show commits in topological order")),
+		OPT_SET_INT(0, "topo-order", &sort_order,
+			    N_("show commits in topological order"),
+			    REV_SORT_IN_GRAPH_ORDER),
 		OPT_BOOLEAN(0, "topics", &topics,
 			    N_("show only commits not on the first branch")),
 		OPT_SET_INT(0, "sparse", &dense,
 			    N_("show merges reachable from only one tip"), 0),
-		OPT_SET_INT(0, "date-order", &lifo,
+		OPT_SET_INT(0, "date-order", &sort_order,
 			    N_("show commits where no parent comes before its "
-			       "children"), 0),
+			       "children"),
+			    REV_SORT_BY_COMMIT_DATE),
 		{ OPTION_CALLBACK, 'g', "reflog", &reflog_base, N_("<n>[,<base>]"),
 			    N_("show <n> most recent ref-log entries starting at "
 			       "base"),
@@ -901,7 +903,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, sort_order);
 
 	/* Give names to commits */
 	if (!sha1_name && !no_name)
diff --git a/commit.c b/commit.c
index f97456d..11b9635 100644
--- a/commit.c
+++ b/commit.c
@@ -512,7 +512,7 @@ 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;
@@ -561,7 +561,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	}
 
 	/* process the list in topological order */
-	if (!lifo)
+	if (sort_order != REV_SORT_IN_GRAPH_ORDER)
 		commit_list_sort_by_date(&work);
 
 	pptr = list;
@@ -588,10 +588,14 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * guaranteeing topological order.
 			 */
 			if (--(*pi) == 1) {
-				if (!lifo)
+				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;
+				}
 			}
 		}
 		/*
diff --git a/commit.h b/commit.h
index 70e749d..247e474 100644
--- a/commit.h
+++ b/commit.h
@@ -139,15 +139,23 @@ struct commit *pop_commit(struct commit_list **stack);
 void clear_commit_marks(struct commit *commit, unsigned int mark);
 void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark);
 
+
+enum rev_sort_order {
+	REV_SORT_IN_GRAPH_ORDER = 0,
+	REV_SORT_BY_COMMIT_DATE
+};
+
 /*
  * Performs an in-place topological sort of list supplied.
  *
  *   invariant of resulting list is:
  *      a reachable from b => ord(b) < ord(a)
- *   in addition, when lifo == 0, commits on parallel tracks are
- *   sorted in the dates order.
+ *   sort_order further specifies:
+ *   REV_SORT_IN_GRAPH_ORDER: try to show a commit on a single-parent
+ *                            chain together.
+ *   REV_SORT_BY_COMMIT_DATE: show eligible commits in committer-date order.
  */
-void sort_in_topological_order(struct commit_list ** list, int lifo);
+void sort_in_topological_order(struct commit_list **, enum rev_sort_order);
 
 struct commit_graft {
 	unsigned char sha1[20];
diff --git a/revision.c b/revision.c
index cf620c6..966ebbc 100644
--- a/revision.c
+++ b/revision.c
@@ -1038,7 +1038,7 @@ void init_revisions(struct rev_info *revs, const char *prefix)
 	DIFF_OPT_SET(&revs->pruning, QUICK);
 	revs->pruning.add_remove = file_add_remove;
 	revs->pruning.change = file_change;
-	revs->lifo = 1;
+	revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
 	revs->dense = 1;
 	revs->prefix = prefix;
 	revs->max_age = -1;
@@ -1373,7 +1373,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--merge")) {
 		revs->show_merge = 1;
 	} else if (!strcmp(arg, "--topo-order")) {
-		revs->lifo = 1;
+		revs->sort_order = REV_SORT_IN_GRAPH_ORDER;
 		revs->topo_order = 1;
 	} else if (!strcmp(arg, "--simplify-merges")) {
 		revs->simplify_merges = 1;
@@ -1391,7 +1391,7 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->prune = 1;
 		load_ref_decorations(DECORATE_SHORT_REFS);
 	} else if (!strcmp(arg, "--date-order")) {
-		revs->lifo = 0;
+		revs->sort_order = REV_SORT_BY_COMMIT_DATE;
 		revs->topo_order = 1;
 	} else if (!prefixcmp(arg, "--early-output")) {
 		int count = 100;
@@ -2165,7 +2165,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->sort_order);
 	if (revs->simplify_merges)
 		simplify_merges(revs);
 	if (revs->children.name)
@@ -2480,7 +2480,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->sort_order);
 }
 
 static struct commit *get_revision_internal(struct rev_info *revs)
diff --git a/revision.h b/revision.h
index 5da09ee..2a5e325 100644
--- a/revision.h
+++ b/revision.h
@@ -4,6 +4,7 @@
 #include "parse-options.h"
 #include "grep.h"
 #include "notes.h"
+#include "commit.h"
 
 #define SEEN		(1u<<0)
 #define UNINTERESTING   (1u<<1)
@@ -60,6 +61,10 @@ struct rev_info {
 	const char *prefix;
 	const char *def;
 	struct pathspec prune_data;
+
+	/* topo-sort */
+	enum rev_sort_order sort_order;
+
 	unsigned int	early_output:1,
 			ignore_missing:1;
 
@@ -70,7 +75,6 @@ struct rev_info {
 			show_all:1,
 			remove_empty_trees:1,
 			simplify_history:1,
-			lifo:1,
 			topo_order:1,
 			simplify_merges:1,
 			simplify_by_decoration:1,

-- 
1.8.3-451-gb703ddf
Previous: Junio C HamanoNext: Eric Sunshine
Message 20 of 51 in “add --authorship-order flag to git log / rev-list”
  1. add --authorship-order flag to git log / rev-listelliottcable, Jun 4, 2013
  2. rev-list: add --authorship-order alternative orderingelliottcable, Jun 4, 2013
  3. Junio C HamanoJun 4, 2013
  4. Junio C HamanoJun 4, 2013
  5. Elliott CableJun 6, 2013
  6. Junio C HamanoJun 6, 2013
  7. Elliott CableJun 6, 2013
  8. Junio C HamanoJun 6, 2013
  9. Junio C HamanoJun 6, 2013
  10. toposort: rename "lifo" fieldJunio C Hamano, Jun 6, 2013
  11. Junio C HamanoJun 7, 2013
  12. 0/3 Preparing for --date-order=authorJunio C Hamano, Jun 7, 2013
  13. 1/3 toposort: rename "lifo" fieldJunio C Hamano, Jun 7, 2013
  14. Eric SunshineJun 7, 2013
  15. Junio C HamanoJun 7, 2013
  16. 2/3 commit-queue: LIFO or priority queue of commitsJunio C Hamano, Jun 7, 2013
  17. Eric SunshineJun 7, 2013
  18. 3/3 sort-in-topological-order: use commit-queueJunio C Hamano, Jun 7, 2013
  19. 0/4 log --author-date-orderJunio C Hamano, Jun 9, 2013
  20. 1/4 toposort: rename "lifo" fieldJunio C Hamano, Jun 9, 2013
  21. Eric SunshineJun 10, 2013
  22. Jeff KingJun 10, 2013
  23. 2/4 commit-queue: LIFO or priority queue of commitsJunio C Hamano, Jun 9, 2013
  24. Jeff KingJun 10, 2013
  25. Junio C HamanoJun 10, 2013
  26. Jeff KingJun 10, 2013
  27. Junio C HamanoJun 10, 2013
  28. Jeff KingJun 10, 2013
  29. Junio C HamanoJun 10, 2013
  30. Jeff KingJun 11, 2013
  31. Junio C HamanoJun 11, 2013
  32. 0/4 log --author-date-orderJunio C Hamano, Jun 11, 2013
  33. 1/4 toposort: rename "lifo" fieldJunio C Hamano, Jun 11, 2013
  34. 2/4 prio-queue: priority queue of pointers to structsJunio C Hamano, Jun 11, 2013
  35. 3/4 sort-in-topological-order: use prio-queueJunio C Hamano, Jun 11, 2013
  36. 4/4 log: --author-date-orderJunio C Hamano, Jun 11, 2013
  37. 3/4 sort-in-topological-order: use commit-queueJunio C Hamano, Jun 9, 2013
  38. Junio C HamanoJun 9, 2013
  39. Jeff KingJun 10, 2013
  40. Junio C HamanoJun 10, 2013
  41. Jeff KingJun 10, 2013
  42. 4/4 log: --author-date-orderJunio C Hamano, Jun 9, 2013
  43. Jeff KingJun 10, 2013
  44. Junio C HamanoJun 10, 2013
  45. Jeff KingJun 10, 2013
  46. Junio C HamanoJun 20, 2013
  47. Jeff KingJun 20, 2013
  48. Eric SunshineJun 7, 2013
  49. Jeff KingJun 4, 2013
  50. Junio C HamanoJun 4, 2013
  51. Elliott CableJun 6, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.