Use generation numbers for --topo-order

This patch series performs a decently-sized refactoring of the revision-walk machinery. Well, "refactoring" is probably the wrong word, as I don't actually remove the old code. Instead, when we see certain options in the 'rev_info' struct, we redirect the commit-walk logic to a new set of methods that distribute the workload differently. By using generation numbers in the commit-graph, we can significantly improve 'git log --graph' commands (and the underlying 'git rev-list --topo-order').

On the Linux repository, I got the following performance results when comparing to the previous version with or without a commit-graph:

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

If you want to read this series but are unfamiliar with the commit-graph and generation numbers, then I recommend reading Documentation/technical/commit-graph.txt or a blob post [1] I wrote on the subject. In particular, the three-part walk described in "revision.c:
refactor basic topo-order logic" is present (but underexplained) as an animated PNG [2].

Since revision.c is an incredibly important (and old) portion of the codebase -- and because there are so many orthogonal options in 'struct rev_info' -- I consider this submission to be "RFC quality". That is, I am not confident that I am not missing anything, or that my solution is the best it can be. I did merge this branch with ds/commit-graph-with-grafts and the "DO-NOT-MERGE: write and read commit-graph always" commit that computes a commit-graph with every 'git commit' command. The test suite passed with that change, available on GitHub [3]. To ensure that I cover at least the case I think are interesting, I added tests to t6600-test-reach.sh to verify the walks report the correct results for the three cases there (no commit-graph, full commit-graph, and a partial commit-graph so the walk starts at GENERATION_NUMBER_INFINITY).

One notable case that is not included in this series is the case of a history comparison such as 'git rev-list --topo-order A..B'. The existing code in limit_list() has ways to cut the walk short when all pending commits are UNINTERESTING. Since this code depends on commit_list instead of the prio_queue we are using here, I chose to leave it untouched for now. We can revisit it in a separate series later. Since handle_commit() turns on revs->limited when a commit is UNINTERESTING, we do not hit the new code in this case. Removing this 'revs->limited = 1;' line yields correct results, but the performance is worse.

This series is based on ds/reachable.

Thanks, -Stolee

[1]
https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/
Supercharging the Git Commit Graph III: Generations and Graph Algorithms

[2]
https://msdnshared.blob.core.windows.net/media/2018/06/commit-graph-topo-order-b-a.png
Animation showing three-part walk

[3] https://github.com/derrickstolee/git/tree/topo-order/testA branch containing this series along with commits to compute commit-graph in entire test suite.

Derrick Stolee (6):
prio-queue: add 'peek' operation
test-reach: add run_three_modes method
test-reach: add rev-list tests revision.c: begin refactoring --topo-order logic commit/revisions: bookkeeping before refactoring revision.c: refactor basic topo-order logic

 commit.c                   |  11 +-
 commit.h                   |   8 ++
 object.h                   |   4 +-
 prio-queue.c               |   9 ++
 prio-queue.h               |   6 +
 revision.c                 | 232 ++++++++++++++++++++++++++++++++++++-
 revision.h                 |   6 +
 t/helper/test-prio-queue.c |  10 +-
 t/t6600-test-reach.sh      |  98 +++++++++++++++-
 9 files changed, 361 insertions(+), 23 deletions(-)

base-commit: 6cc017431c1c48f80d1c6512fdcc9866cf4b7f55
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-25%2Fderrickstolee%2Ftopo-order%2Fprogress-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-25/derrickstolee/topo-order/progress-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/25

gitgitgadget

From: Derrick Stolee <[email protected]>

When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek().

Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh.

---
 prio-queue.c               |  9 +++++++++
 prio-queue.h               |  6 ++++++
 t/helper/test-prio-queue.c | 10 +++++++---
 3 files changed, 22 insertions(+), 3 deletions(-)

index a078451872..d3f488cb05 100644
@@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue)
 	}
 	return result;
 }
+
+void *prio_queue_peek(struct prio_queue *queue)
+{
+	if (!queue->nr)
+		return NULL;
+	if (!queue->compare)
+		return queue->array[queue->nr - 1].data;
+	return queue->array[0].data;
+}

index d030ec9dd6..682e51867a 100644
@@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing);
  */
 extern void *prio_queue_get(struct prio_queue *);
 
+/*
+ * Gain access to the "thing" that would be returned by
+ * prio_queue_get, but do not remove it from the queue.
+ */
+extern void *prio_queue_peek(struct prio_queue *);
+
 extern void clear_prio_queue(struct prio_queue *);
 
 /* Reverse the LIFO elements */

index 9807b649b1..e817bbf464 100644
@@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv)
 	struct prio_queue pq = { intcmp };
 
 	while (*++argv) {
-		if (!strcmp(*argv, "get"))
-			show(prio_queue_get(&pq));
-		else if (!strcmp(*argv, "dump")) {
+		if (!strcmp(*argv, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			show(get);
+		} else if (!strcmp(*argv, "dump")) {
 			int *v;
 			while ((v = prio_queue_get(&pq)))
 			       show(v);

gitgitgadget

From: Derrick Stolee <[email protected]>

The 'test_three_modes' method assumes we are using the 'test-tool reach' command for our test. However, we may want to use the data shape of our commit graph and the three modes (no commit-graph, full commit-graph, partial commit-graph) for other git commands.

Split test_three_modes to be a simple translation on a more general run_three_modes method that executes the given command and tests the actual output to the expected output.

While inspecting this code, I realized that the final test for 'commit_contains --tag' is silently dropping the '--tag' argument. It should be quoted to include both.

---
 t/t6600-test-reach.sh | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

index d139a00d1d..1b18e12a4e 100755
@@ -53,18 +53,22 @@ test_expect_success 'setup' '
 	git config core.commitGraph true
 '
 
-test_three_modes () {
+run_three_modes () {
 	test_when_finished rm -rf .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual
 }
 
+test_three_modes () {
+	run_three_modes "test-tool reach $1"
+}
+
 test_expect_success 'ref_newer:miss' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

@@ -219,7 +223,7 @@ test_expect_success 'commit_contains:hit' '
 	EOF
 	echo "commit_contains(_,A,X,_):1" >expect &&
 	test_three_modes commit_contains &&
-	test_three_modes commit_contains --tag
+	test_three_modes "commit_contains --tag"
 '
 
 test_expect_success 'commit_contains:miss' '

gitgitgadget

From: Derrick Stolee <[email protected]>

The rev-list command is critical to Git's functionality. Ensure it works in the three commit-graph environments constructed in t6600-test-reach.sh. Here are a few important types of rev-list operations:

* Basic: git rev-list --topo-order HEAD
* Range: git rev-list --topo-order compare..HEAD
* Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD
* Symmetric Difference: git rev-list --topo-order compare...HEAD

---
 t/t6600-test-reach.sh | 84 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)

index 1b18e12a4e..2fcaa39077 100755
@@ -243,4 +243,88 @@ test_expect_success 'commit_contains:miss' '
 	test_three_modes commit_contains --tag
 '
 
+test_expect_success 'rev-list: basic topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
+		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-6-6"
+'
+
+test_expect_success 'rev-list: first-parent topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes "git rev-list --first-parent --topo-order commit-6-6"
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-3..commit-6-6"
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-8..commit-6-6"
+'
+
+test_expect_success 'rev-list: first-parent range topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --first-parent --topo-order commit-3-8..commit-6-6"
+'
+
+test_expect_success 'rev-list: ancestry-path topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6"
+'
+
+test_expect_success 'rev-list: symmetric difference topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+		commit-3-8 commit-2-8 commit-1-8 \
+		commit-3-7 commit-2-7 commit-1-7 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-8...commit-6-6"
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

When running 'git rev-list --topo-order' and its kin, the topo_order setting in struct rev_info implies the limited setting. This means that the following things happen during prepare_revision_walk():

* revs->limited implies we run limit_list() to walk the entire reachable set. There are some short-cuts here, such as if we perform a range query like 'git rev-list COMPARE..HEAD' and we can stop limit_list() when all queued commits are uninteresting.

* revs->topo_order implies we run sort_in_topological_order(). See the implementation of that method in commit.c. It implies that the full set of commits to order is in the given commit_list.

These two methods imply that a 'git rev-list --topo-order HEAD' command must walk the entire reachable set of commits _twice_ before returning a single result.

If we have a commit-graph file with generation numbers computed, then there is a better way. This patch introduces some necessary logic redirection when we are in this situation.

In v2.18.0, the commit-graph file contains zero-valued bytes in the positions where the generation number is stored in v2.19.0 and later. Thus, we use generation_numbers_enabled() to check if the commit-graph is available and has non-zero generation numbers.

When setting revs->limited only because revs->topo_order is true, only do so if generation numbers are not available. There is no reason to use the new logic as it will behave similarly when all generation numbers are INFINITY or ZERO.

In prepare_revision_walk(), if we have revs->topo_order but not revs->limited, then we trigger the new logic. It breaks the logic into three pieces, to fit with the existing framework:

1. init_topo_walk() fills a new struct topo_walk_info in the rev_info struct. We use the presence of this struct as a signal to use the new methods during our walk. In this patch, this method simply calls limit_list() and sort_in_topological_order(). In the future, this method will set up a new data structure to perform that logic in-line.

2. next_topo_commit() provides get_revision_1() with the next topo- ordered commit in the list. Currently, this simply pops the commit from revs->commits.

3. expand_topo_walk() provides get_revision_1() with a way to signal walking beyond the latest commit. Currently, this calls add_parents_to_list() exactly like the old logic.

While this commit presents method redirection for performing the exact same logic as before, it allows the next commit to focus only on the new logic.

---
 revision.c | 42 ++++++++++++++++++++++++++++++++++++++----
 revision.h |  4 ++++
 2 files changed, 42 insertions(+), 4 deletions(-)

index 3205a3947a..1db70dc951 100644
@@ -25,6 +25,7 @@
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"
+#include "commit-graph.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -2451,7 +2452,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->diffopt.objfind)
 		revs->simplify_history = 0;
 
-	if (revs->topo_order)
+	if (revs->topo_order && !generation_numbers_enabled(the_repository))
 		revs->limited = 1;
 
 	if (revs->prune_data.nr) {

@@ -2889,6 +2890,33 @@ static int mark_uninteresting(const struct object_id *oid,
 	return 0;
 }
 
+struct topo_walk_info {};
+
+static void init_topo_walk(struct rev_info *revs)
+{
+	struct topo_walk_info *info;
+	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
+	info = revs->topo_walk_info;
+	memset(info, 0, sizeof(struct topo_walk_info));
+
+	limit_list(revs);
+	sort_in_topological_order(&revs->commits, revs->sort_order);
+}
+
+static struct commit *next_topo_commit(struct rev_info *revs)
+{
+	return pop_commit(&revs->commits);
+}
+
+static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
+{
+	if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+		if (!revs->ignore_missing_links)
+			die("Failed to traverse parents of commit %s",
+			    oid_to_hex(&commit->object.oid));
+	}
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int i;

@@ -2925,11 +2953,13 @@ int prepare_revision_walk(struct rev_info *revs)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;
-	if (revs->limited)
+	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;
-	if (revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->sort_order);
+		if (revs->topo_order)
+			sort_in_topological_order(&revs->commits, revs->sort_order);
+	} else if (revs->topo_order)
+		init_topo_walk(revs);
 	if (revs->line_level_traverse)
 		line_log_filter(revs);
 	if (revs->simplify_merges)

@@ -3254,6 +3284,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 		if (revs->reflog_info)
 			commit = next_reflog_entry(revs->reflog_info);
+		else if (revs->topo_walk_info)
+			commit = next_topo_commit(revs);
 		else
 			commit = pop_commit(&revs->commits);
 

@@ -3275,6 +3307,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 			if (revs->reflog_info)
 				try_to_simplify_commit(revs, commit);
+			else if (revs->topo_walk_info)
+				expand_topo_walk(revs, commit);
 			else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
 				if (!revs->ignore_missing_links)
 					die("Failed to traverse parents of commit %s",

index bf2239f876..e48181673d 100644
@@ -54,6 +54,8 @@ struct rev_cmdline_info {
 #define REVISION_WALK_NO_WALK_SORTED 1
 #define REVISION_WALK_NO_WALK_UNSORTED 2
 
+struct topo_walk_info;
+
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;

@@ -227,6 +229,8 @@ struct rev_info {
 	const char *break_bar;
 
 	struct revision_sources *sources;
+
+	struct topo_walk_info *topo_walk_info;
 };
 
 extern int ref_excluded(struct string_list *, const char *path);

gitgitgadget

From: Derrick Stolee <[email protected]>

There are a few things that need to move around a little before making a big refactoring in the topo-order logic:

1. We need access to record_author_date() and compare_commits_by_author_date() in revision.c. These are used currently by sort_in_topological_order() in commit.c.

2. Moving these methods to commit.h requires adding the author_slab definition to commit.h.

3. The add_parents_to_list() method in revision.c performs logic around the UNINTERESTING flag and other special cases depending on the struct rev_info. Allow this method to ignore a NULL 'list' parameter, as we will not be populating the list for our walk.

---
 commit.c   | 11 ++++-------
 commit.h   |  8 ++++++++
 revision.c |  6 ++++--
 3 files changed, 16 insertions(+), 9 deletions(-)

index 32d1234bd7..2dbe187b8c 100644
@@ -655,11 +655,8 @@ struct commit *pop_commit(struct commit_list **stack)
 /* count number of children that have not been emitted */
 define_commit_slab(indegree_slab, int);
 
-/* record author-date for each commit object */
-define_commit_slab(author_date_slab, unsigned long);
-
-static void record_author_date(struct author_date_slab *author_date,
-			       struct commit *commit)
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit)
 {
 	const char *buffer = get_commit_buffer(commit, NULL);
 	struct ident_split ident;

@@ -684,8 +681,8 @@ fail_exit:
 	unuse_commit_buffer(commit, buffer);
 }
 
-static int compare_commits_by_author_date(const void *a_, const void *b_,
-					  void *cb_data)
+int compare_commits_by_author_date(const void *a_, const void *b_,
+				   void *cb_data)
 {
 	const struct commit *a = a_, *b = b_;
 	struct author_date_slab *author_date = cb_data;

index e2c99d9b04..51de10e698 100644
@@ -8,6 +8,7 @@
 #include "gpg-interface.h"
 #include "string-list.h"
 #include "pretty.h"
+#include "commit-slab.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
 #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF

@@ -328,6 +329,13 @@ extern int remove_signature(struct strbuf *buf);
  */
 extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);
 
+/* record author-date for each commit object */
+define_commit_slab(author_date_slab, timestamp_t);
+
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit);
+
+int compare_commits_by_author_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused);
 

index 1db70dc951..565f903e46 100644
@@ -804,7 +804,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			if (p->object.flags & SEEN)
 				continue;
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		return 0;
 	}

@@ -843,7 +844,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		if (revs->first_parent_only)
 			break;

gitgitgadget

From: Derrick Stolee <[email protected]>

When running a command like 'git rev-list --topo-order HEAD', Git performed the following steps:

1. Run limit_list(), which parses all reachable commits, adds them to a linked list, and distributes UNINTERESTING flags. If all unprocessed commits are UNINTERESTING, then it may terminate without walking all reachable commits. This does not occur if we do not specify UNINTERESTING commits.

2. Run sort_in_topological_order(), which is an implementation of Kahn's algorithm. It first iterates through the entire set of important commits and computes the in-degree of each (plus one, as we use 'zero' as a special value here). Then, we walk the commits in priority order, adding them to the priority queue if and only if their in-degree is one. As we remove commits from this priority queue, we decrement the in-degree of their parents.

3. While we are peeling commits for output, get_revision_1() uses pop_commit on the full list of commits computed by sort_in_topological_order().

In the new algorithm, these three steps correspond to three different commit walks. We run these walks simultaneously, and advance each only as far as necessary to satisfy the requirements of the 'higher order' walk. We know when we can pause each walk by using generation numbers from the commit- graph feature.

Recall that the generation number of a commit satisfies:

* If the commit has at least one parent, then the generation number is one more than the maximum generation number among its parents.

* If the commit has no parent, then the generation number is one.

There are two special generation numbers:

* GENERATION_NUMBER_INFINITY: this value is 0xffffffff and indicates that the commit is not stored in the commit-graph and the generation number was not previously calculated.

* GENERATION_NUMBER_ZERO: this value (0) is a special indicator to say that the commit-graph was generated by a version of Git that does not compute generation numbers (such as v2.18.0).

Since we use generation_numbers_enabled() before using the new algorithm, we do not need to worry about GENERATION_NUMBER_ZERO. However, the existence of GENERATION_NUMBER_INFINITY implies the following weaker statement than the usual we expect from generation numbers:

If A and B are commits with generation numbers gen(A) and gen(B) and gen(A) < gen(B), then A cannot reach B.

Thus, we will walk in each of our stages until the "maximum unexpanded generation number" is strictly lower than the generation number of a commit we are about to use.

The walks are as follows:

1. EXPLORE: using the explore_queue priority queue (ordered by maximizing the generation number), parse each reachable commit until all commits in the queue have generation number strictly lower than needed. During this walk, update the UNINTERESTING flags as necessary.

2. INDEGREE: using the indegree_queue priority queue (ordered by maximizing the generation number), add one to the in- degree of each parent for each commit that is walked. Since we walk in order of decreasing generation number, we know that discovering an in-degree value of 0 means the value for that commit was not initialized, so should be initialized to two. (Recall that in-degree value "1" is what we use to say a commit is ready for output.) As we iterate the parents of a commit during this walk, ensure the EXPLORE walk has walked beyond their generation numbers.

3. TOPO: using the topo_queue priority queue (ordered based on the sort_order given, which could be commit-date, author- date, or typical topo-order which treats the queue as a LIFO stack), remove a commit from the queue and decrement the in-degree of each parent. If a parent has an in-degree of one, then we add it to the topo_queue. Before we decrement the in-degree, however, ensure the INDEGREE walk has walked beyond that generation number.

The implementations of these walks are in the following methods:

* explore_walk_step and explore_to_depth
* indegree_walk_step and compute_indegrees_to_depth
* next_topo_commit and expand_topo_walk

These methods have some patterns that may seem strange at first, but they are probably carry-overs from their equivalents in limit_list and sort_in_topological_order.

One thing that is missing from this implementation is a proper way to stop walking when the entire queue is UNINTERESTING, so this implementation is not enabled by comparisions, such as in 'git rev-list --topo-order A..B'. This can be updated in the future.

In my local testing, I used the following Git commands on the Linux repository in three modes: HEAD~1 with no commit-graph, HEAD~1 with a commit-graph, and HEAD with a commit-graph. This allows comparing the benefits we get from parsing commits from the commit-graph and then again the benefits we get by restricting the set of commits we walk.

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

This speedup is due to a few things. First, the new generation- number-enabled algorithm walks commits on order of the number of results output (subject to some branching structure expectations). Since we limit to 100 results, we are running a query similar to filling a single page of results. Second, when specifying a path, we must parse the root tree object for each commit we walk. The previous benefits from the commit-graph are entirely from reading the commit-graph instead of parsing commits. Since we need to parse trees for the same number of commits as before, we slow down significantly from the non-path-based query.

For the test above, I specifically selected a path that is changed frequently, including by merge commits. A less-frequently-changed path (such as 'README') has similar end-to-end time since we need to walk the same number of commits (before determining we do not have 100 hits). However, get get the benefit that the output is presented to the user as it is discovered, much the same as a normal 'git log' command (no '--topo-order'). This is an improved user experience, even if the command has the same runtime.

---
 object.h   |   4 +-
 revision.c | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 revision.h |   2 +
 3 files changed, 194 insertions(+), 8 deletions(-)

index b132944c51..a84eea61d2 100644
@@ -57,7 +57,7 @@ struct object_array {
 
 /*
  * object flag allocation:
- * revision.h:               0---------10                                26
+ * revision.h:               0---------10                                26--28
  * fetch-pack.c:             0----5
  * walker.c:                 0-2
  * upload-pack.c:                4       11-----14  16-----19

@@ -75,7 +75,7 @@ struct object_array {
  * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
-#define FLAG_BITS  27
+#define FLAG_BITS  29
 
 /*
  * The object type is stored in 3 bits.

index e48181673d..ca10392021 100644
@@ -21,6 +21,8 @@
 #define PATCHSAME	(1u<<9)
 #define BOTTOM		(1u<<10)
 #define TRACK_LINEAR	(1u<<26)
+#define TOPO_WALK_EXPLORED (1u<<27)
+#define TOPO_WALK_INDEGREE (1u<<28)
 #define ALL_REV_FLAGS	(((1u<<11)-1) | TRACK_LINEAR)
 
 #define DECORATE_SHORT_REFS	1

gitgitgadget

Finally ;-).

This patch series performs a decently-sized refactoring of the revision-walk machinery. Well, "refactoring" is probably the wrong word, as I don't actually remove the old code. Instead, when we see certain options in the 'rev_info' struct, we redirect the commit-walk logic to a new set of methods that distribute the workload differently. By using generation numbers in the commit-graph, we can significantly improve 'git log --graph' commands (and the underlying 'git rev-list --topo-order').

On the Linux repository, I got the following performance results when comparing to the previous version with or without a commit-graph:

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

If you want to read this series but are unfamiliar with the commit-graph and generation numbers, then I recommend reading Documentation/technical/commit-graph.txt or a blob post [1] I wrote on the subject. In particular, the three-part walk described in "revision.c:
refactor basic topo-order logic" is present (but underexplained) as an animated PNG [2].

Since revision.c is an incredibly important (and old) portion of the codebase -- and because there are so many orthogonal options in 'struct rev_info' -- I consider this submission to be "RFC quality". That is, I am not confident that I am not missing anything, or that my solution is the best it can be. I did merge this branch with ds/commit-graph-with-grafts and the "DO-NOT-MERGE: write and read commit-graph always" commit that computes a commit-graph with every 'git commit' command. The test suite passed with that change, available on GitHub [3]. To ensure that I cover at least the case I think are interesting, I added tests to t6600-test-reach.sh to verify the walks report the correct results for the three cases there (no commit-graph, full commit-graph, and a partial commit-graph so the walk starts at GENERATION_NUMBER_INFINITY).

One notable case that is not included in this series is the case of a history comparison such as 'git rev-list --topo-order A..B'. The existing code in limit_list() has ways to cut the walk short when all pending commits are UNINTERESTING. Since this code depends on commit_list instead of the prio_queue we are using here, I chose to leave it untouched for now. We can revisit it in a separate series later. Since handle_commit() turns on revs->limited when a commit is UNINTERESTING, we do not hit the new code in this case. Removing this 'revs->limited = 1;' line yields correct results, but the performance is worse.

This series was based on ds/reachable, but is now based on 'master' to not conflict with 182070 "commit: use timestamp_t for author_date_slab". There is a small conflict with md/filter-trees, because it renamed a flag in revisions.h in the line before I add new flags. Hopefully this conflict is not too difficult to resolve.

Thanks, -Stolee

[1]
https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/
Supercharging the Git Commit Graph III: Generations and Graph Algorithms

[2]
https://msdnshared.blob.core.windows.net/media/2018/06/commit-graph-topo-order-b-a.png
Animation showing three-part walk

[3] https://github.com/derrickstolee/git/tree/topo-order/testA branch containing this series along with commits to compute commit-graph in entire test suite.

Derrick Stolee (6):
prio-queue: add 'peek' operation
test-reach: add run_three_modes method
test-reach: add rev-list tests revision.c: begin refactoring --topo-order logic commit/revisions: bookkeeping before refactoring revision.c: refactor basic topo-order logic

 commit.c                   |  11 +-
 commit.h                   |   8 ++
 object.h                   |   4 +-
 prio-queue.c               |   9 ++
 prio-queue.h               |   6 +
 revision.c                 | 232 ++++++++++++++++++++++++++++++++++++-
 revision.h                 |   6 +
 t/helper/test-prio-queue.c |  10 +-
 t/t6600-test-reach.sh      |  98 +++++++++++++++-
 9 files changed, 361 insertions(+), 23 deletions(-)

base-commit: 2d3b1c576c85b7f5db1f418907af00ab88e0c303
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-25%2Fderrickstolee%2Ftopo-order%2Fprogress-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-25/derrickstolee/topo-order/progress-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/25

Range-diff vs v1:

 1:  5e55669f4d = 1:  cc1ec4c270 prio-queue: add 'peek' operation
 2:  9628396af1 = 2:  404c918608 test-reach: add run_three_modes method
 3:  708b4550a1 = 3:  30dee58c61 test-reach: add rev-list tests
 4:  908442417d ! 4:  a74ae13d4e revision.c: begin refactoring --topo-order logic
     @@ -168,4 +168,4 @@
      +	struct topo_walk_info *topo_walk_info;
       };
       
     - extern int ref_excluded(struct string_list *, const char *path);
     + int ref_excluded(struct string_list *, const char *path);
 5:  a7272f2799 ! 5:  0e64fc144c commit/revisions: bookkeeping before refactoring
     @@ -27,7 +27,7 @@
       define_commit_slab(indegree_slab, int);
       
      -/* record author-date for each commit object */
     --define_commit_slab(author_date_slab, unsigned long);
     +-define_commit_slab(author_date_slab, timestamp_t);
      -
      -static void record_author_date(struct author_date_slab *author_date,
      -			       struct commit *commit)

6: 73713bcbee ! 6: 3b185ac3b1 revision.c: refactor basic topo-order logic
@@ -153,11 +153,11 @@

/*
* object flag allocation:
-- * revision.h: 0---------10 26
-+ * revision.h: 0---------10 26--28
- * fetch-pack.c: 0----5
+- * revision.h: 0---------10 2526
++ * revision.h: 0---------10 25----28
+ * fetch-pack.c: 01
+ * negotiator/default.c: 2--5
* walker.c: 0-2
- * upload-pack.c: 4 11-----14 16-----19
@@
* builtin/show-branch.c: 0-------------------------------------------26
* builtin/unpack-objects.c: 2021
@@ -404,11 +404,11 @@
--- a/revision.h
+++ b/revision.h
@@
- #define PATCHSAME (1u<<9)
- #define BOTTOM (1u<<10)
+ #define USER_GIVEN (1u<<25) /* given directly by the user */
#define TRACK_LINEAR (1u<<26)
+ #define ALL_REV_FLAGS (((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
+#define TOPO_WALK_EXPLORED (1u<<27)
+#define TOPO_WALK_INDEGREE (1u<<28)
- #define ALL_REV_FLAGS (((1u<<11)-1) | TRACK_LINEAR)

#define DECORATE_SHORT_REFS 1
+ #define DECORATE_FULL_REFS 2

gitgitgadget

From: Derrick Stolee <[email protected]>

When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek().

Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh.

---
 prio-queue.c               |  9 +++++++++
 prio-queue.h               |  6 ++++++
 t/helper/test-prio-queue.c | 10 +++++++---
 3 files changed, 22 insertions(+), 3 deletions(-)

index a078451872..d3f488cb05 100644
@@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue)
 	}
 	return result;
 }
+
+void *prio_queue_peek(struct prio_queue *queue)
+{
+	if (!queue->nr)
+		return NULL;
+	if (!queue->compare)
+		return queue->array[queue->nr - 1].data;
+	return queue->array[0].data;
+}

index d030ec9dd6..682e51867a 100644
@@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing);
  */
 extern void *prio_queue_get(struct prio_queue *);
 
+/*
+ * Gain access to the "thing" that would be returned by
+ * prio_queue_get, but do not remove it from the queue.
+ */
+extern void *prio_queue_peek(struct prio_queue *);
+
 extern void clear_prio_queue(struct prio_queue *);
 
 /* Reverse the LIFO elements */

index 9807b649b1..e817bbf464 100644
@@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv)
 	struct prio_queue pq = { intcmp };
 
 	while (*++argv) {
-		if (!strcmp(*argv, "get"))
-			show(prio_queue_get(&pq));
-		else if (!strcmp(*argv, "dump")) {
+		if (!strcmp(*argv, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			show(get);
+		} else if (!strcmp(*argv, "dump")) {
 			int *v;
 			while ((v = prio_queue_get(&pq)))
 			       show(v);

gitgitgadget

From: Derrick Stolee <[email protected]>

The 'test_three_modes' method assumes we are using the 'test-tool reach' command for our test. However, we may want to use the data shape of our commit graph and the three modes (no commit-graph, full commit-graph, partial commit-graph) for other git commands.

Split test_three_modes to be a simple translation on a more general run_three_modes method that executes the given command and tests the actual output to the expected output.

While inspecting this code, I realized that the final test for 'commit_contains --tag' is silently dropping the '--tag' argument. It should be quoted to include both.

---
 t/t6600-test-reach.sh | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

index d139a00d1d..1b18e12a4e 100755
@@ -53,18 +53,22 @@ test_expect_success 'setup' '
 	git config core.commitGraph true
 '
 
-test_three_modes () {
+run_three_modes () {
 	test_when_finished rm -rf .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	$1 <input >actual &&
 	test_cmp expect actual
 }
 
+test_three_modes () {
+	run_three_modes "test-tool reach $1"
+}
+
 test_expect_success 'ref_newer:miss' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

@@ -219,7 +223,7 @@ test_expect_success 'commit_contains:hit' '
 	EOF
 	echo "commit_contains(_,A,X,_):1" >expect &&
 	test_three_modes commit_contains &&
-	test_three_modes commit_contains --tag
+	test_three_modes "commit_contains --tag"
 '
 
 test_expect_success 'commit_contains:miss' '

gitgitgadget

Nit: while quoting the function's arguments does fix the issue, it leaves the tests prone to the same issue in the future. Wouldn't it be better to use $@ inside the function to refer to all its arguments?

IOW, do it more like this?

	"$@" <input >actual

i.e. treat each parameter as separate things without further getting split at $IFS and ...

run_three_modes test-tool reach "$1"

... make sure there three things are sent as separate, by quoting "$1" inside dq.

I think that makes sense.

I also noticed that 2/6 made "commti_contains --tag" enclosed in dq pair for one test, but the next test after it has the identical one.

Here is what I queued in the meantime.

index 1b18e12a4e..1377849bf8 100755
@@ -55,18 +55,18 @@ test_expect_success 'setup' '
 
 run_three_modes () {
 	test_when_finished rm -rf .git/objects/info/commit-graph &&
-	$1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	$1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
-	$1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual
 }
 
 test_three_modes () {
-	run_three_modes "test-tool reach $1"
+	run_three_modes test-tool reach "$1"
 }
 
 test_expect_success 'ref_newer:miss' '

@@ -223,7 +223,7 @@ test_expect_success 'commit_contains:hit' '
 	EOF
 	echo "commit_contains(_,A,X,_):1" >expect &&
 	test_three_modes commit_contains &&
-	test_three_modes "commit_contains --tag"
+	test_three_modes commit_contains --tag
 '
 
 test_expect_success 'commit_contains:miss' '

2.19.0-216-g2d3b1c576c

And of course, I find out that 3/6 needs a matching update after I've almost finished day's integration cycle, and need to redo the whole thing X-<.

Here is a squashable update for 3/6 to match the proposed change.

-- >8 --
Subject: fixup! test-reach: add rev-list tests

 t/t6600-test-reach.sh | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

index 990ab56e7a..cf9179bdb8 100755
@@ -252,7 +252,7 @@ test_expect_success 'rev-list: basic topo-order' '
 		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
 		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
 	>expect &&
-	run_three_modes "git rev-list --topo-order commit-6-6"
+	run_three_modes git rev-list --topo-order commit-6-6
 '
 
 test_expect_success 'rev-list: first-parent topo-order' '

@@ -264,7 +264,7 @@ test_expect_success 'rev-list: first-parent topo-order' '
 		commit-6-2 \
 		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
 	>expect &&
-	run_three_modes "git rev-list --first-parent --topo-order commit-6-6"
+	run_three_modes git rev-list --first-parent --topo-order commit-6-6
 '
 
 test_expect_success 'rev-list: range topo-order' '

@@ -276,7 +276,7 @@ test_expect_success 'rev-list: range topo-order' '
 		commit-6-2 commit-5-2 commit-4-2 \
 		commit-6-1 commit-5-1 commit-4-1 \
 	>expect &&
-	run_three_modes "git rev-list --topo-order commit-3-3..commit-6-6"
+	run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
 '
 
 test_expect_success 'rev-list: range topo-order' '

@@ -288,7 +288,7 @@ test_expect_success 'rev-list: range topo-order' '
 		commit-6-2 commit-5-2 commit-4-2 \
 		commit-6-1 commit-5-1 commit-4-1 \
 	>expect &&
-	run_three_modes "git rev-list --topo-order commit-3-8..commit-6-6"
+	run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
 '
 
 test_expect_success 'rev-list: first-parent range topo-order' '

@@ -300,7 +300,7 @@ test_expect_success 'rev-list: first-parent range topo-order' '
 		commit-6-2 \
 		commit-6-1 commit-5-1 commit-4-1 \
 	>expect &&
-	run_three_modes "git rev-list --first-parent --topo-order commit-3-8..commit-6-6"
+	run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
 '
 
 test_expect_success 'rev-list: ancestry-path topo-order' '

@@ -310,7 +310,7 @@ test_expect_success 'rev-list: ancestry-path topo-order' '
 		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
 		commit-6-3 commit-5-3 commit-4-3 \
 	>expect &&
-	run_three_modes "git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6"
+	run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
 '
 
 test_expect_success 'rev-list: symmetric difference topo-order' '

@@ -324,7 +324,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '
 		commit-3-8 commit-2-8 commit-1-8 \
 		commit-3-7 commit-2-7 commit-1-7 \
 	>expect &&
-	run_three_modes "git rev-list --topo-order commit-3-8...commit-6-6"
+	run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
 '
 
 test_done

From: Derrick Stolee <[email protected]>

The rev-list command is critical to Git's functionality. Ensure it works in the three commit-graph environments constructed in t6600-test-reach.sh. Here are a few important types of rev-list operations:

* Basic: git rev-list --topo-order HEAD
* Range: git rev-list --topo-order compare..HEAD
* Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD
* Symmetric Difference: git rev-list --topo-order compare...HEAD

---
 t/t6600-test-reach.sh | 84 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)

index 1b18e12a4e..2fcaa39077 100755
@@ -243,4 +243,88 @@ test_expect_success 'commit_contains:miss' '
 	test_three_modes commit_contains --tag
 '
 
+test_expect_success 'rev-list: basic topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
+		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-6-6"
+'
+
+test_expect_success 'rev-list: first-parent topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes "git rev-list --first-parent --topo-order commit-6-6"
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-3..commit-6-6"
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-8..commit-6-6"
+'
+
+test_expect_success 'rev-list: first-parent range topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes "git rev-list --first-parent --topo-order commit-3-8..commit-6-6"
+'
+
+test_expect_success 'rev-list: ancestry-path topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6"
+'
+
+test_expect_success 'rev-list: symmetric difference topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+		commit-3-8 commit-2-8 commit-1-8 \
+		commit-3-7 commit-2-7 commit-1-7 \
+	>expect &&
+	run_three_modes "git rev-list --topo-order commit-3-8...commit-6-6"
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

When running 'git rev-list --topo-order' and its kin, the topo_order setting in struct rev_info implies the limited setting. This means that the following things happen during prepare_revision_walk():

* revs->limited implies we run limit_list() to walk the entire reachable set. There are some short-cuts here, such as if we perform a range query like 'git rev-list COMPARE..HEAD' and we can stop limit_list() when all queued commits are uninteresting.

* revs->topo_order implies we run sort_in_topological_order(). See the implementation of that method in commit.c. It implies that the full set of commits to order is in the given commit_list.

These two methods imply that a 'git rev-list --topo-order HEAD' command must walk the entire reachable set of commits _twice_ before returning a single result.

If we have a commit-graph file with generation numbers computed, then there is a better way. This patch introduces some necessary logic redirection when we are in this situation.

In v2.18.0, the commit-graph file contains zero-valued bytes in the positions where the generation number is stored in v2.19.0 and later. Thus, we use generation_numbers_enabled() to check if the commit-graph is available and has non-zero generation numbers.

When setting revs->limited only because revs->topo_order is true, only do so if generation numbers are not available. There is no reason to use the new logic as it will behave similarly when all generation numbers are INFINITY or ZERO.

In prepare_revision_walk(), if we have revs->topo_order but not revs->limited, then we trigger the new logic. It breaks the logic into three pieces, to fit with the existing framework:

1. init_topo_walk() fills a new struct topo_walk_info in the rev_info struct. We use the presence of this struct as a signal to use the new methods during our walk. In this patch, this method simply calls limit_list() and sort_in_topological_order(). In the future, this method will set up a new data structure to perform that logic in-line.

2. next_topo_commit() provides get_revision_1() with the next topo- ordered commit in the list. Currently, this simply pops the commit from revs->commits.

3. expand_topo_walk() provides get_revision_1() with a way to signal walking beyond the latest commit. Currently, this calls add_parents_to_list() exactly like the old logic.

While this commit presents method redirection for performing the exact same logic as before, it allows the next commit to focus only on the new logic.

---
 revision.c | 42 ++++++++++++++++++++++++++++++++++++++----
 revision.h |  4 ++++
 2 files changed, 42 insertions(+), 4 deletions(-)

index e18bd530e4..2dcde8a8ac 100644
@@ -25,6 +25,7 @@
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"
+#include "commit-graph.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -2454,7 +2455,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->diffopt.objfind)
 		revs->simplify_history = 0;
 
-	if (revs->topo_order)
+	if (revs->topo_order && !generation_numbers_enabled(the_repository))
 		revs->limited = 1;
 
 	if (revs->prune_data.nr) {

@@ -2892,6 +2893,33 @@ static int mark_uninteresting(const struct object_id *oid,
 	return 0;
 }
 
+struct topo_walk_info {};
+
+static void init_topo_walk(struct rev_info *revs)
+{
+	struct topo_walk_info *info;
+	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
+	info = revs->topo_walk_info;
+	memset(info, 0, sizeof(struct topo_walk_info));
+
+	limit_list(revs);
+	sort_in_topological_order(&revs->commits, revs->sort_order);
+}
+
+static struct commit *next_topo_commit(struct rev_info *revs)
+{
+	return pop_commit(&revs->commits);
+}
+
+static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
+{
+	if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+		if (!revs->ignore_missing_links)
+			die("Failed to traverse parents of commit %s",
+			    oid_to_hex(&commit->object.oid));
+	}
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int i;

@@ -2928,11 +2956,13 @@ int prepare_revision_walk(struct rev_info *revs)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;
-	if (revs->limited)
+	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;
-	if (revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->sort_order);
+		if (revs->topo_order)
+			sort_in_topological_order(&revs->commits, revs->sort_order);
+	} else if (revs->topo_order)
+		init_topo_walk(revs);
 	if (revs->line_level_traverse)
 		line_log_filter(revs);
 	if (revs->simplify_merges)

@@ -3257,6 +3287,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 		if (revs->reflog_info)
 			commit = next_reflog_entry(revs->reflog_info);
+		else if (revs->topo_walk_info)
+			commit = next_topo_commit(revs);
 		else
 			commit = pop_commit(&revs->commits);
 

@@ -3278,6 +3310,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 			if (revs->reflog_info)
 				try_to_simplify_commit(revs, commit);
+			else if (revs->topo_walk_info)
+				expand_topo_walk(revs, commit);
 			else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
 				if (!revs->ignore_missing_links)
 					die("Failed to traverse parents of commit %s",

index 2b30ac270d..fd4154ff75 100644
@@ -56,6 +56,8 @@ struct rev_cmdline_info {
 #define REVISION_WALK_NO_WALK_SORTED 1
 #define REVISION_WALK_NO_WALK_UNSORTED 2
 
+struct topo_walk_info;
+
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;

@@ -245,6 +247,8 @@ struct rev_info {
 	const char *break_bar;
 
 	struct revision_sources *sources;
+
+	struct topo_walk_info *topo_walk_info;
 };
 
 int ref_excluded(struct string_list *, const char *path);

gitgitgadget

From: Derrick Stolee <[email protected]>

There are a few things that need to move around a little before making a big refactoring in the topo-order logic:

1. We need access to record_author_date() and compare_commits_by_author_date() in revision.c. These are used currently by sort_in_topological_order() in commit.c.

2. Moving these methods to commit.h requires adding the author_slab definition to commit.h.

3. The add_parents_to_list() method in revision.c performs logic around the UNINTERESTING flag and other special cases depending on the struct rev_info. Allow this method to ignore a NULL 'list' parameter, as we will not be populating the list for our walk.

---
 commit.c   | 11 ++++-------
 commit.h   |  8 ++++++++
 revision.c |  6 ++++--
 3 files changed, 16 insertions(+), 9 deletions(-)

index d0f199e122..f68e04b2f1 100644
@@ -655,11 +655,8 @@ struct commit *pop_commit(struct commit_list **stack)
 /* count number of children that have not been emitted */
 define_commit_slab(indegree_slab, int);
 
-/* record author-date for each commit object */
-define_commit_slab(author_date_slab, timestamp_t);
-
-static void record_author_date(struct author_date_slab *author_date,
-			       struct commit *commit)
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit)
 {
 	const char *buffer = get_commit_buffer(commit, NULL);
 	struct ident_split ident;

@@ -684,8 +681,8 @@ fail_exit:
 	unuse_commit_buffer(commit, buffer);
 }
 
-static int compare_commits_by_author_date(const void *a_, const void *b_,
-					  void *cb_data)
+int compare_commits_by_author_date(const void *a_, const void *b_,
+				   void *cb_data)
 {
 	const struct commit *a = a_, *b = b_;
 	struct author_date_slab *author_date = cb_data;

index 2b1a734388..ff0eb5f8ef 100644
@@ -8,6 +8,7 @@
 #include "gpg-interface.h"
 #include "string-list.h"
 #include "pretty.h"
+#include "commit-slab.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
 #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF

@@ -328,6 +329,13 @@ extern int remove_signature(struct strbuf *buf);
  */
 extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);
 
+/* record author-date for each commit object */
+define_commit_slab(author_date_slab, timestamp_t);
+
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit);
+
+int compare_commits_by_author_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused);
 

index 2dcde8a8ac..92012d5f45 100644
@@ -808,7 +808,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			if (p->object.flags & SEEN)
 				continue;
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		return 0;
 	}

@@ -847,7 +848,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		if (revs->first_parent_only)
 			break;

gitgitgadget

From: Derrick Stolee <[email protected]>

When running a command like 'git rev-list --topo-order HEAD', Git performed the following steps:

1. Run limit_list(), which parses all reachable commits, adds them to a linked list, and distributes UNINTERESTING flags. If all unprocessed commits are UNINTERESTING, then it may terminate without walking all reachable commits. This does not occur if we do not specify UNINTERESTING commits.

2. Run sort_in_topological_order(), which is an implementation of Kahn's algorithm. It first iterates through the entire set of important commits and computes the in-degree of each (plus one, as we use 'zero' as a special value here). Then, we walk the commits in priority order, adding them to the priority queue if and only if their in-degree is one. As we remove commits from this priority queue, we decrement the in-degree of their parents.

3. While we are peeling commits for output, get_revision_1() uses pop_commit on the full list of commits computed by sort_in_topological_order().

In the new algorithm, these three steps correspond to three different commit walks. We run these walks simultaneously, and advance each only as far as necessary to satisfy the requirements of the 'higher order' walk. We know when we can pause each walk by using generation numbers from the commit- graph feature.

Recall that the generation number of a commit satisfies:

* If the commit has at least one parent, then the generation number is one more than the maximum generation number among its parents.

* If the commit has no parent, then the generation number is one.

There are two special generation numbers:

* GENERATION_NUMBER_INFINITY: this value is 0xffffffff and indicates that the commit is not stored in the commit-graph and the generation number was not previously calculated.

* GENERATION_NUMBER_ZERO: this value (0) is a special indicator to say that the commit-graph was generated by a version of Git that does not compute generation numbers (such as v2.18.0).

Since we use generation_numbers_enabled() before using the new algorithm, we do not need to worry about GENERATION_NUMBER_ZERO. However, the existence of GENERATION_NUMBER_INFINITY implies the following weaker statement than the usual we expect from generation numbers:

If A and B are commits with generation numbers gen(A) and gen(B) and gen(A) < gen(B), then A cannot reach B.

Thus, we will walk in each of our stages until the "maximum unexpanded generation number" is strictly lower than the generation number of a commit we are about to use.

The walks are as follows:

1. EXPLORE: using the explore_queue priority queue (ordered by maximizing the generation number), parse each reachable commit until all commits in the queue have generation number strictly lower than needed. During this walk, update the UNINTERESTING flags as necessary.

2. INDEGREE: using the indegree_queue priority queue (ordered by maximizing the generation number), add one to the in- degree of each parent for each commit that is walked. Since we walk in order of decreasing generation number, we know that discovering an in-degree value of 0 means the value for that commit was not initialized, so should be initialized to two. (Recall that in-degree value "1" is what we use to say a commit is ready for output.) As we iterate the parents of a commit during this walk, ensure the EXPLORE walk has walked beyond their generation numbers.

3. TOPO: using the topo_queue priority queue (ordered based on the sort_order given, which could be commit-date, author- date, or typical topo-order which treats the queue as a LIFO stack), remove a commit from the queue and decrement the in-degree of each parent. If a parent has an in-degree of one, then we add it to the topo_queue. Before we decrement the in-degree, however, ensure the INDEGREE walk has walked beyond that generation number.

The implementations of these walks are in the following methods:

* explore_walk_step and explore_to_depth
* indegree_walk_step and compute_indegrees_to_depth
* next_topo_commit and expand_topo_walk

These methods have some patterns that may seem strange at first, but they are probably carry-overs from their equivalents in limit_list and sort_in_topological_order.

One thing that is missing from this implementation is a proper way to stop walking when the entire queue is UNINTERESTING, so this implementation is not enabled by comparisions, such as in 'git rev-list --topo-order A..B'. This can be updated in the future.

In my local testing, I used the following Git commands on the Linux repository in three modes: HEAD~1 with no commit-graph, HEAD~1 with a commit-graph, and HEAD with a commit-graph. This allows comparing the benefits we get from parsing commits from the commit-graph and then again the benefits we get by restricting the set of commits we walk.

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

This speedup is due to a few things. First, the new generation- number-enabled algorithm walks commits on order of the number of results output (subject to some branching structure expectations). Since we limit to 100 results, we are running a query similar to filling a single page of results. Second, when specifying a path, we must parse the root tree object for each commit we walk. The previous benefits from the commit-graph are entirely from reading the commit-graph instead of parsing commits. Since we need to parse trees for the same number of commits as before, we slow down significantly from the non-path-based query.

For the test above, I specifically selected a path that is changed frequently, including by merge commits. A less-frequently-changed path (such as 'README') has similar end-to-end time since we need to walk the same number of commits (before determining we do not have 100 hits). However, get get the benefit that the output is presented to the user as it is discovered, much the same as a normal 'git log' command (no '--topo-order'). This is an improved user experience, even if the command has the same runtime.

---
 object.h   |   4 +-
 revision.c | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 revision.h |   2 +
 3 files changed, 194 insertions(+), 8 deletions(-)

index 0feb90ae61..796792cb32 100644
@@ -59,7 +59,7 @@ struct object_array {
 
 /*
  * object flag allocation:
- * revision.h:               0---------10                              2526
+ * revision.h:               0---------10                              25----28
  * fetch-pack.c:             01
  * negotiator/default.c:       2--5
  * walker.c:                 0-2

@@ -78,7 +78,7 @@ struct object_array {
  * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
-#define FLAG_BITS  27
+#define FLAG_BITS  29
 
 /*
  * The object type is stored in 3 bits.

index fd4154ff75..b20c16c0e0 100644
@@ -24,6 +24,8 @@
 #define USER_GIVEN	(1u<<25) /* given directly by the user */
 #define TRACK_LINEAR	(1u<<26)
 #define ALL_REV_FLAGS	(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
+#define TOPO_WALK_EXPLORED (1u<<27)
+#define TOPO_WALK_INDEGREE (1u<<28)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2

gitgitgadget

On Tue, Sep 18 2018, Derrick Stolee via GitGitGadget wrote:

Thanks. Good to see the commit graph used for more stuff.

It would be great if this were made into a t/perf/ test shipped with this series, that would be later quoted in a commit, as in e.g. 3b41fb0cb2 ("fsck: use oidset instead of oid_array for skipList", 2018-09-03).

Although generalizing that "-- tools" part (i.e. finding a candidate dir) will require some heuristic, but would make it useful when running this against other erpos.

We discussed some of this in private E-Mail, and this isn't really feedback on *this* series in particular, just on the general commit-graph work.

Right now git-config(1) just matter-of-factly says how to enable it, and points to git-commit-graph(1) for further info, which just shows how to run the tool. But nothing's describing what stuff is sped up, and those sorts of docs aren't being updated as new optimizations (e.g. this --topo-order walk) are added.

For that you need to scour a combination of your blogpost & commits in git.git (with quoted perf numbers).

t/perf/p4211-line-log.sh has the following test:

    test_perf 'git log --oneline --raw --parents -1000' ' git log --oneline --raw --parents -1000 >/dev/null '

We could add the following to the end of that script to get similar values, since it already selects a file randomly at the top of the script:

    test_perf 'git log --oneline --raw --parents -1000 -- <file>' ' git log --oneline --raw --parents -1000 -- $file >/dev/null '

Thanks for reminding me. I have this on my list of TODOs.

-Stolee

This patch series performs a decently-sized refactoring of the revision-walk machinery. Well, "refactoring" is probably the wrong word, as I don't actually remove the old code. Instead, when we see certain options in the 'rev_info' struct, we redirect the commit-walk logic to a new set of methods that distribute the workload differently. By using generation numbers in the commit-graph, we can significantly improve 'git log --graph' commands (and the underlying 'git rev-list --topo-order').

On the Linux repository, I got the following performance results when comparing to the previous version with or without a commit-graph:

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

If you want to read this series but are unfamiliar with the commit-graph and generation numbers, then I recommend reading Documentation/technical/commit-graph.txt or a blob post [1] I wrote on the subject. In particular, the three-part walk described in "revision.c:
refactor basic topo-order logic" is present (but underexplained) as an animated PNG [2].

Since revision.c is an incredibly important (and old) portion of the codebase -- and because there are so many orthogonal options in 'struct rev_info' -- I consider this submission to be "RFC quality". That is, I am not confident that I am not missing anything, or that my solution is the best it can be. I did merge this branch with ds/commit-graph-with-grafts and the "DO-NOT-MERGE: write and read commit-graph always" commit that computes a commit-graph with every 'git commit' command. The test suite passed with that change, available on GitHub [3]. To ensure that I cover at least the case I think are interesting, I added tests to t6600-test-reach.sh to verify the walks report the correct results for the three cases there (no commit-graph, full commit-graph, and a partial commit-graph so the walk starts at GENERATION_NUMBER_INFINITY).

One notable case that is not included in this series is the case of a history comparison such as 'git rev-list --topo-order A..B'. The existing code in limit_list() has ways to cut the walk short when all pending commits are UNINTERESTING. Since this code depends on commit_list instead of the prio_queue we are using here, I chose to leave it untouched for now. We can revisit it in a separate series later. Since handle_commit() turns on revs->limited when a commit is UNINTERESTING, we do not hit the new code in this case. Removing this 'revs->limited = 1;' line yields correct results, but the performance is worse.

This series was based on ds/reachable, but is now based on 'master' to not conflict with 182070 "commit: use timestamp_t for author_date_slab". There is a small conflict with md/filter-trees, because it renamed a flag in revisions.h in the line before I add new flags. Hopefully this conflict is not too difficult to resolve.

Changes in V3: I added a new patch that updates the tab-alignment for flags in revision.h before adding new ones (Thanks, Ævar!). Also, I squashed the recommended changes to run_three_modes and test_three_modes from Szeder and Junio. Thanks!

Thanks, -Stolee

[1]
https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/
Supercharging the Git Commit Graph III: Generations and Graph Algorithms

[2]
https://msdnshared.blob.core.windows.net/media/2018/06/commit-graph-topo-order-b-a.png
Animation showing three-part walk

[3] https://github.com/derrickstolee/git/tree/topo-order/testA branch containing this series along with commits to compute commit-graph in entire test suite.

Derrick Stolee (7):
prio-queue: add 'peek' operation
test-reach: add run_three_modes method
test-reach: add rev-list tests revision.c: begin refactoring --topo-order logic commit/revisions: bookkeeping before refactoring revision.h: add whitespace in flag definitions revision.c: refactor basic topo-order logic

 commit.c                   |  11 +-
 commit.h                   |   8 ++
 object.h                   |   4 +-
 prio-queue.c               |   9 ++
 prio-queue.h               |   6 +
 revision.c                 | 232 ++++++++++++++++++++++++++++++++++++-
 revision.h                 |  34 +++---
 t/helper/test-prio-queue.c |  10 +-
 t/t6600-test-reach.sh      |  96 ++++++++++++++-
 9 files changed, 374 insertions(+), 36 deletions(-)

base-commit: 2d3b1c576c85b7f5db1f418907af00ab88e0c303
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-25%2Fderrickstolee%2Ftopo-order%2Fprogress-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-25/derrickstolee/topo-order/progress-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/25

Range-diff vs v2:

 1:  cc1ec4c270 = 1:  cc1ec4c270 prio-queue: add 'peek' operation
 2:  404c918608 ! 2:  b2a1ade148 test-reach: add run_three_modes method
     @@ -11,10 +11,6 @@
          run_three_modes method that executes the given command and tests
          the actual output to the expected output.
      
     -    While inspecting this code, I realized that the final test for
     -    'commit_contains --tag' is silently dropping the '--tag' argument.
     -    It should be quoted to include both.
     -
          Signed-off-by: Derrick Stolee <[email protected]>
      
      diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
     @@ -28,31 +24,22 @@
      +run_three_modes () {
       	test_when_finished rm -rf .git/objects/info/commit-graph &&
      -	test-tool reach $1 <input >actual &&
     -+	$1 <input >actual &&
     ++	"$@" <input >actual &&
       	test_cmp expect actual &&
       	cp commit-graph-full .git/objects/info/commit-graph &&
      -	test-tool reach $1 <input >actual &&
     -+	$1 <input >actual &&
     ++	"$@" <input >actual &&
       	test_cmp expect actual &&
       	cp commit-graph-half .git/objects/info/commit-graph &&
      -	test-tool reach $1 <input >actual &&
     -+	$1 <input >actual &&
     ++	"$@" <input >actual &&
       	test_cmp expect actual
       }
       
      +test_three_modes () {
     -+	run_three_modes "test-tool reach $1"
     ++	run_three_modes test-tool reach "$@"
      +}
      +
       test_expect_success 'ref_newer:miss' '
       	cat >input <<-\EOF &&
       	A:commit-5-7
     -@@
     - 	EOF
     - 	echo "commit_contains(_,A,X,_):1" >expect &&
     - 	test_three_modes commit_contains &&
     --	test_three_modes commit_contains --tag
     -+	test_three_modes "commit_contains --tag"
     - '
     - 
     - test_expect_success 'commit_contains:miss' '
 3:  30dee58c61 ! 3:  b0ceb96076 test-reach: add rev-list tests
     @@ -30,7 +30,7 @@
      +		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
      +		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
      +	>expect &&
     -+	run_three_modes "git rev-list --topo-order commit-6-6"
     ++	run_three_modes git rev-list --topo-order commit-6-6
      +'
      +
      +test_expect_success 'rev-list: first-parent topo-order' '
     @@ -42,7 +42,7 @@
      +		commit-6-2 \
      +		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
      +	>expect &&
     -+	run_three_modes "git rev-list --first-parent --topo-order commit-6-6"
     ++	run_three_modes git rev-list --first-parent --topo-order commit-6-6
      +'
      +
      +test_expect_success 'rev-list: range topo-order' '
     @@ -54,7 +54,7 @@
      +		commit-6-2 commit-5-2 commit-4-2 \
      +		commit-6-1 commit-5-1 commit-4-1 \
      +	>expect &&
     -+	run_three_modes "git rev-list --topo-order commit-3-3..commit-6-6"
     ++	run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
      +'
      +
      +test_expect_success 'rev-list: range topo-order' '
     @@ -66,7 +66,7 @@
      +		commit-6-2 commit-5-2 commit-4-2 \
      +		commit-6-1 commit-5-1 commit-4-1 \
      +	>expect &&
     -+	run_three_modes "git rev-list --topo-order commit-3-8..commit-6-6"
     ++	run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
      +'
      +
      +test_expect_success 'rev-list: first-parent range topo-order' '
     @@ -78,7 +78,7 @@
      +		commit-6-2 \
      +		commit-6-1 commit-5-1 commit-4-1 \
      +	>expect &&
     -+	run_three_modes "git rev-list --first-parent --topo-order commit-3-8..commit-6-6"
     ++	run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
      +'
      +
      +test_expect_success 'rev-list: ancestry-path topo-order' '
     @@ -88,7 +88,7 @@
      +		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
      +		commit-6-3 commit-5-3 commit-4-3 \
      +	>expect &&
     -+	run_three_modes "git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6"
     ++	run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
      +'
      +
      +test_expect_success 'rev-list: symmetric difference topo-order' '
     @@ -102,7 +102,7 @@
      +		commit-3-8 commit-2-8 commit-1-8 \
      +		commit-3-7 commit-2-7 commit-1-7 \
      +	>expect &&
     -+	run_three_modes "git rev-list --topo-order commit-3-8...commit-6-6"
     ++	run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
      +'
      +
       test_done
 4:  a74ae13d4e = 4:  fd1a0ab7cd revision.c: begin refactoring --topo-order logic
 5:  0e64fc144c = 5:  e86f304082 commit/revisions: bookkeeping before refactoring
 -:  ---------- > 6:  fa6d5ef152 revision.h: add whitespace in flag definitions
 6:  3b185ac3b1 ! 7:  020b2f50c5 revision.c: refactor basic topo-order logic
     @@ -404,11 +404,11 @@
      --- a/revision.h
      +++ b/revision.h
      @@
     - #define USER_GIVEN	(1u<<25) /* given directly by the user */
     - #define TRACK_LINEAR	(1u<<26)
     - #define ALL_REV_FLAGS	(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
     -+#define TOPO_WALK_EXPLORED (1u<<27)
     -+#define TOPO_WALK_INDEGREE (1u<<28)
     + #define USER_GIVEN		(1u<<25) /* given directly by the user */
     + #define TRACK_LINEAR		(1u<<26)
     + #define ALL_REV_FLAGS		(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
     ++#define TOPO_WALK_EXPLORED	(1u<<27)
     ++#define TOPO_WALK_INDEGREE	(1u<<28)
       
       #define DECORATE_SHORT_REFS	1
       #define DECORATE_FULL_REFS	2

gitgitgadget

From: Derrick Stolee <[email protected]>

When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek().

Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh.

---
 prio-queue.c               |  9 +++++++++
 prio-queue.h               |  6 ++++++
 t/helper/test-prio-queue.c | 10 +++++++---
 3 files changed, 22 insertions(+), 3 deletions(-)

index a078451872..d3f488cb05 100644
@@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue)
 	}
 	return result;
 }
+
+void *prio_queue_peek(struct prio_queue *queue)
+{
+	if (!queue->nr)
+		return NULL;
+	if (!queue->compare)
+		return queue->array[queue->nr - 1].data;
+	return queue->array[0].data;
+}

index d030ec9dd6..682e51867a 100644
@@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing);
  */
 extern void *prio_queue_get(struct prio_queue *);
 
+/*
+ * Gain access to the "thing" that would be returned by
+ * prio_queue_get, but do not remove it from the queue.
+ */
+extern void *prio_queue_peek(struct prio_queue *);
+
 extern void clear_prio_queue(struct prio_queue *);
 
 /* Reverse the LIFO elements */

index 9807b649b1..e817bbf464 100644
@@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv)
 	struct prio_queue pq = { intcmp };
 
 	while (*++argv) {
-		if (!strcmp(*argv, "get"))
-			show(prio_queue_get(&pq));
-		else if (!strcmp(*argv, "dump")) {
+		if (!strcmp(*argv, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			show(get);
+		} else if (!strcmp(*argv, "dump")) {
 			int *v;
 			while ((v = prio_queue_get(&pq)))
 			       show(v);

gitgitgadget

Makes sense.

From: Derrick Stolee <[email protected]>

The 'test_three_modes' method assumes we are using the 'test-tool reach' command for our test. However, we may want to use the data shape of our commit graph and the three modes (no commit-graph, full commit-graph, partial commit-graph) for other git commands.

Split test_three_modes to be a simple translation on a more general run_three_modes method that executes the given command and tests the actual output to the expected output.

---
 t/t6600-test-reach.sh | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

index d139a00d1d..9d65b8b946 100755
@@ -53,18 +53,22 @@ test_expect_success 'setup' '
 	git config core.commitGraph true
 '
 
-test_three_modes () {
+run_three_modes () {
 	test_when_finished rm -rf .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual
 }
 
+test_three_modes () {
+	run_three_modes test-tool reach "$@"
+}
+
 test_expect_success 'ref_newer:miss' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

gitgitgadget

From: Derrick Stolee <[email protected]>

The rev-list command is critical to Git's functionality. Ensure it works in the three commit-graph environments constructed in t6600-test-reach.sh. Here are a few important types of rev-list operations:

* Basic: git rev-list --topo-order HEAD
* Range: git rev-list --topo-order compare..HEAD
* Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD
* Symmetric Difference: git rev-list --topo-order compare...HEAD

---
 t/t6600-test-reach.sh | 84 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)

index 9d65b8b946..288f703b7b 100755
@@ -243,4 +243,88 @@ test_expect_success 'commit_contains:miss' '
 	test_three_modes commit_contains --tag
 '
 
+test_expect_success 'rev-list: basic topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
+		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-6-6
+'
+
+test_expect_success 'rev-list: first-parent topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes git rev-list --first-parent --topo-order commit-6-6
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
+'
+
+test_expect_success 'rev-list: first-parent range topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
+'
+
+test_expect_success 'rev-list: ancestry-path topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+	>expect &&
+	run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
+'
+
+test_expect_success 'rev-list: symmetric difference topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+		commit-3-8 commit-2-8 commit-1-8 \
+		commit-3-7 commit-2-7 commit-1-7 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
+'
+
 test_done

gitgitgadget

Makes sense. I'll assume you filled out all those "expect" blocks correctly. ;)

-Peff

Well, otherwise three-modes test would barf at least when it is running in its "no graph" mode, so I'd assume we are covered.

From: Derrick Stolee <[email protected]>

When running 'git rev-list --topo-order' and its kin, the topo_order setting in struct rev_info implies the limited setting. This means that the following things happen during prepare_revision_walk():

* revs->limited implies we run limit_list() to walk the entire reachable set. There are some short-cuts here, such as if we perform a range query like 'git rev-list COMPARE..HEAD' and we can stop limit_list() when all queued commits are uninteresting.

* revs->topo_order implies we run sort_in_topological_order(). See the implementation of that method in commit.c. It implies that the full set of commits to order is in the given commit_list.

These two methods imply that a 'git rev-list --topo-order HEAD' command must walk the entire reachable set of commits _twice_ before returning a single result.

If we have a commit-graph file with generation numbers computed, then there is a better way. This patch introduces some necessary logic redirection when we are in this situation.

In v2.18.0, the commit-graph file contains zero-valued bytes in the positions where the generation number is stored in v2.19.0 and later. Thus, we use generation_numbers_enabled() to check if the commit-graph is available and has non-zero generation numbers.

When setting revs->limited only because revs->topo_order is true, only do so if generation numbers are not available. There is no reason to use the new logic as it will behave similarly when all generation numbers are INFINITY or ZERO.

In prepare_revision_walk(), if we have revs->topo_order but not revs->limited, then we trigger the new logic. It breaks the logic into three pieces, to fit with the existing framework:

1. init_topo_walk() fills a new struct topo_walk_info in the rev_info struct. We use the presence of this struct as a signal to use the new methods during our walk. In this patch, this method simply calls limit_list() and sort_in_topological_order(). In the future, this method will set up a new data structure to perform that logic in-line.

2. next_topo_commit() provides get_revision_1() with the next topo- ordered commit in the list. Currently, this simply pops the commit from revs->commits.

3. expand_topo_walk() provides get_revision_1() with a way to signal walking beyond the latest commit. Currently, this calls add_parents_to_list() exactly like the old logic.

While this commit presents method redirection for performing the exact same logic as before, it allows the next commit to focus only on the new logic.

---
 revision.c | 42 ++++++++++++++++++++++++++++++++++++++----
 revision.h |  4 ++++
 2 files changed, 42 insertions(+), 4 deletions(-)

index e18bd530e4..2dcde8a8ac 100644
@@ -25,6 +25,7 @@
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"
+#include "commit-graph.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -2454,7 +2455,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->diffopt.objfind)
 		revs->simplify_history = 0;
 
-	if (revs->topo_order)
+	if (revs->topo_order && !generation_numbers_enabled(the_repository))
 		revs->limited = 1;
 
 	if (revs->prune_data.nr) {

@@ -2892,6 +2893,33 @@ static int mark_uninteresting(const struct object_id *oid,
 	return 0;
 }
 
+struct topo_walk_info {};
+
+static void init_topo_walk(struct rev_info *revs)
+{
+	struct topo_walk_info *info;
+	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
+	info = revs->topo_walk_info;
+	memset(info, 0, sizeof(struct topo_walk_info));
+
+	limit_list(revs);
+	sort_in_topological_order(&revs->commits, revs->sort_order);
+}
+
+static struct commit *next_topo_commit(struct rev_info *revs)
+{
+	return pop_commit(&revs->commits);
+}
+
+static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
+{
+	if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+		if (!revs->ignore_missing_links)
+			die("Failed to traverse parents of commit %s",
+			    oid_to_hex(&commit->object.oid));
+	}
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int i;

@@ -2928,11 +2956,13 @@ int prepare_revision_walk(struct rev_info *revs)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;
-	if (revs->limited)
+	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;
-	if (revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->sort_order);
+		if (revs->topo_order)
+			sort_in_topological_order(&revs->commits, revs->sort_order);
+	} else if (revs->topo_order)
+		init_topo_walk(revs);
 	if (revs->line_level_traverse)
 		line_log_filter(revs);
 	if (revs->simplify_merges)

@@ -3257,6 +3287,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 		if (revs->reflog_info)
 			commit = next_reflog_entry(revs->reflog_info);
+		else if (revs->topo_walk_info)
+			commit = next_topo_commit(revs);
 		else
 			commit = pop_commit(&revs->commits);
 

@@ -3278,6 +3310,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 			if (revs->reflog_info)
 				try_to_simplify_commit(revs, commit);
+			else if (revs->topo_walk_info)
+				expand_topo_walk(revs, commit);
 			else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
 				if (!revs->ignore_missing_links)
 					die("Failed to traverse parents of commit %s",

index 2b30ac270d..fd4154ff75 100644
@@ -56,6 +56,8 @@ struct rev_cmdline_info {
 #define REVISION_WALK_NO_WALK_SORTED 1
 #define REVISION_WALK_NO_WALK_UNSORTED 2
 
+struct topo_walk_info;
+
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;

@@ -245,6 +247,8 @@ struct rev_info {
 	const char *break_bar;
 
 	struct revision_sources *sources;
+
+	struct topo_walk_info *topo_walk_info;
 };
 
 int ref_excluded(struct string_list *, const char *path);

gitgitgadget

Nicely explained. Your abstracted init/next/expand API seems sane, but of course the real test will be reading the later patches that make use of it. :)

The patch matches my understanding of your explanation.

-Peff

With or without "--topo-order", running rev-list without any negative commit means we must dig down to the roots that can be reached from the positive commits we have.

I am to sure if having to run the "sort" of order N counts as "walk the entire reachable set once" (in addition to the enumeration that must be done to prepare that N commits, performed in limit_list()).

... because everything is already done in #1 above. Which makes sense.

"latest"? We dig down the history from newer to older, so at some point we hit an old commit and need to find the parents to keep walking towards even older parts of the history. Did you mean "earliest" instead?

OK.

If we use default order in 'git log', we don't walk all the way to the root commits, and instead trust the commit-date. (This is different than --date-order, which does guarantee parents after children.) In this case, revs->limited is false.

sort_in_topological_order() does actually _two_ walks (the in-degree computation plus the walk that peels commits of in-degree zero), but those walks are cheaper because we've already parsed the commits in limit_list().

I mean "latest" in terms of the algorithm, so "the commit that was returned by get_revision_1() most recently". This could use some rewriting for clarity.

For this algorithm to work, we only care that _some_ commits have generation numbers. We expect that if a commit-graph file exists with generation numbers, then the majority of commits have generation numbers. The commits that were added or fetched since the commit-graph was written will have generation number INFINITY, but the topo-order algorithm will still work and be efficient in those cases. (This is also why we have the "half graph" case in test_three_modes.)

This is a good question. It seems to work for me when I check out your version of this commit (6c04ff30 "revision.c: begin refactoring --topo-order logic") and run all tests.

And specifically, when the conditions for our new topo-walk algorithm are in effect. If the commit-graph doesn't exist, the old logic will still go through for "git log --topo-order".

Thanks for the careful look!
-Stolee

Am 12.10.18 um 08:33 schrieb Junio C Hamano:

sizeof cannot return 0. sizeof(struct topo_walk_info) will be 1 here.

-- Hannes

Thanks.

From: Derrick Stolee <[email protected]>

There are a few things that need to move around a little before making a big refactoring in the topo-order logic:

1. We need access to record_author_date() and compare_commits_by_author_date() in revision.c. These are used currently by sort_in_topological_order() in commit.c.

2. Moving these methods to commit.h requires adding the author_slab definition to commit.h.

3. The add_parents_to_list() method in revision.c performs logic around the UNINTERESTING flag and other special cases depending on the struct rev_info. Allow this method to ignore a NULL 'list' parameter, as we will not be populating the list for our walk.

---
 commit.c   | 11 ++++-------
 commit.h   |  8 ++++++++
 revision.c |  6 ++++--
 3 files changed, 16 insertions(+), 9 deletions(-)

index d0f199e122..f68e04b2f1 100644
@@ -655,11 +655,8 @@ struct commit *pop_commit(struct commit_list **stack)
 /* count number of children that have not been emitted */
 define_commit_slab(indegree_slab, int);
 
-/* record author-date for each commit object */
-define_commit_slab(author_date_slab, timestamp_t);
-
-static void record_author_date(struct author_date_slab *author_date,
-			       struct commit *commit)
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit)
 {
 	const char *buffer = get_commit_buffer(commit, NULL);
 	struct ident_split ident;

@@ -684,8 +681,8 @@ fail_exit:
 	unuse_commit_buffer(commit, buffer);
 }
 
-static int compare_commits_by_author_date(const void *a_, const void *b_,
-					  void *cb_data)
+int compare_commits_by_author_date(const void *a_, const void *b_,
+				   void *cb_data)
 {
 	const struct commit *a = a_, *b = b_;
 	struct author_date_slab *author_date = cb_data;

index 2b1a734388..ff0eb5f8ef 100644
@@ -8,6 +8,7 @@
 #include "gpg-interface.h"
 #include "string-list.h"
 #include "pretty.h"
+#include "commit-slab.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
 #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF

@@ -328,6 +329,13 @@ extern int remove_signature(struct strbuf *buf);
  */
 extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);
 
+/* record author-date for each commit object */
+define_commit_slab(author_date_slab, timestamp_t);
+
+void record_author_date(struct author_date_slab *author_date,
+			struct commit *commit);
+
+int compare_commits_by_author_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);
 int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused);
 

index 2dcde8a8ac..92012d5f45 100644
@@ -808,7 +808,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			if (p->object.flags & SEEN)
 				continue;
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		return 0;
 	}

@@ -847,7 +848,8 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 		p->object.flags |= left_flag;
 		if (!(p->object.flags & SEEN)) {
 			p->object.flags |= SEEN;
-			commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
+			if (list)
+				commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
 		if (revs->first_parent_only)
 			break;

gitgitgadget

The overall goal makes sense. Do we really need to define the whole slab in the header file? We're going to end up with multiple copies of the functions, since they're declared static in each file that includes commit.h.

From what's here, I think you could get away with just:

struct author_date_slab;
void record_author_date(struct author_date_slab *author_date,

                          struct commit *commit);

in the header file. But presumably callers would eventually want to allocate their own author dates. If that's all we need, then these days you can do:

  declare_commit_slab(author_date, timestamp_t);

to get the type declaration.

If they really do need the functions accessible outside of commit.c, then perhaps:

  define_shared_commit_slab(author_date, timestamp_t);

in commit.h, and:

  implement_shared_commit_slab(author_date, timestamp_t);

in commit.c (the type repetition is not too bad, as the compiler would catch any mistakes).

The only downside of this approach is that we're less likely to be able to inline element access (though "peek" is big enough that I'm not sure it ends up inlined anyway).

So now you can add_parents_to_list() without a list? That sounds confusing. :)

Is it possible to split the function into two? Some handle_uninteresting_parents() logic, and then an add_parents_to_list() that calls that, but also adds to the list?

A cursory look at the function suggests it's actually kind of tricky. Perhaps as an alternative, add_parents_to_list() could just get a more descriptive name?

The patch itself seems straight-forward based on those explanations.

-Peff

From: Derrick Stolee <[email protected]>

In anticipation of adding longer flag names in the next change, add an extra tab to each flag definition in revision.h.

---
 revision.h | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

index fd4154ff75..e7bd059d80 100644
@@ -10,20 +10,20 @@
 #include "commit-slab-decl.h"
 
 /* Remember to update object flag allocation in object.h */
-#define SEEN		(1u<<0)
-#define UNINTERESTING   (1u<<1)
-#define TREESAME	(1u<<2)
-#define SHOWN		(1u<<3)
-#define TMP_MARK	(1u<<4) /* for isolated cases; clean after use */
-#define BOUNDARY	(1u<<5)
-#define CHILD_SHOWN	(1u<<6)
-#define ADDED		(1u<<7)	/* Parents already parsed and added? */
-#define SYMMETRIC_LEFT	(1u<<8)
-#define PATCHSAME	(1u<<9)
-#define BOTTOM		(1u<<10)
-#define USER_GIVEN	(1u<<25) /* given directly by the user */
-#define TRACK_LINEAR	(1u<<26)
-#define ALL_REV_FLAGS	(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
+#define SEEN			(1u<<0)
+#define UNINTERESTING		(1u<<1)
+#define TREESAME		(1u<<2)
+#define SHOWN			(1u<<3)
+#define TMP_MARK		(1u<<4) /* for isolated cases; clean after use */
+#define BOUNDARY		(1u<<5)
+#define CHILD_SHOWN		(1u<<6)
+#define ADDED			(1u<<7)	/* Parents already parsed and added? */
+#define SYMMETRIC_LEFT		(1u<<8)
+#define PATCHSAME		(1u<<9)
+#define BOTTOM			(1u<<10)
+#define USER_GIVEN		(1u<<25) /* given directly by the user */
+#define TRACK_LINEAR		(1u<<26)
+#define ALL_REV_FLAGS		(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2

gitgitgadget

From: Derrick Stolee <[email protected]>

When running a command like 'git rev-list --topo-order HEAD', Git performed the following steps:

1. Run limit_list(), which parses all reachable commits, adds them to a linked list, and distributes UNINTERESTING flags. If all unprocessed commits are UNINTERESTING, then it may terminate without walking all reachable commits. This does not occur if we do not specify UNINTERESTING commits.

2. Run sort_in_topological_order(), which is an implementation of Kahn's algorithm. It first iterates through the entire set of important commits and computes the in-degree of each (plus one, as we use 'zero' as a special value here). Then, we walk the commits in priority order, adding them to the priority queue if and only if their in-degree is one. As we remove commits from this priority queue, we decrement the in-degree of their parents.

3. While we are peeling commits for output, get_revision_1() uses pop_commit on the full list of commits computed by sort_in_topological_order().

In the new algorithm, these three steps correspond to three different commit walks. We run these walks simultaneously, and advance each only as far as necessary to satisfy the requirements of the 'higher order' walk. We know when we can pause each walk by using generation numbers from the commit- graph feature.

Recall that the generation number of a commit satisfies:

* If the commit has at least one parent, then the generation number is one more than the maximum generation number among its parents.

* If the commit has no parent, then the generation number is one.

There are two special generation numbers:

* GENERATION_NUMBER_INFINITY: this value is 0xffffffff and indicates that the commit is not stored in the commit-graph and the generation number was not previously calculated.

* GENERATION_NUMBER_ZERO: this value (0) is a special indicator to say that the commit-graph was generated by a version of Git that does not compute generation numbers (such as v2.18.0).

Since we use generation_numbers_enabled() before using the new algorithm, we do not need to worry about GENERATION_NUMBER_ZERO. However, the existence of GENERATION_NUMBER_INFINITY implies the following weaker statement than the usual we expect from generation numbers:

If A and B are commits with generation numbers gen(A) and gen(B) and gen(A) < gen(B), then A cannot reach B.

Thus, we will walk in each of our stages until the "maximum unexpanded generation number" is strictly lower than the generation number of a commit we are about to use.

The walks are as follows:

1. EXPLORE: using the explore_queue priority queue (ordered by maximizing the generation number), parse each reachable commit until all commits in the queue have generation number strictly lower than needed. During this walk, update the UNINTERESTING flags as necessary.

2. INDEGREE: using the indegree_queue priority queue (ordered by maximizing the generation number), add one to the in- degree of each parent for each commit that is walked. Since we walk in order of decreasing generation number, we know that discovering an in-degree value of 0 means the value for that commit was not initialized, so should be initialized to two. (Recall that in-degree value "1" is what we use to say a commit is ready for output.) As we iterate the parents of a commit during this walk, ensure the EXPLORE walk has walked beyond their generation numbers.

3. TOPO: using the topo_queue priority queue (ordered based on the sort_order given, which could be commit-date, author- date, or typical topo-order which treats the queue as a LIFO stack), remove a commit from the queue and decrement the in-degree of each parent. If a parent has an in-degree of one, then we add it to the topo_queue. Before we decrement the in-degree, however, ensure the INDEGREE walk has walked beyond that generation number.

The implementations of these walks are in the following methods:

* explore_walk_step and explore_to_depth
* indegree_walk_step and compute_indegrees_to_depth
* next_topo_commit and expand_topo_walk

These methods have some patterns that may seem strange at first, but they are probably carry-overs from their equivalents in limit_list and sort_in_topological_order.

One thing that is missing from this implementation is a proper way to stop walking when the entire queue is UNINTERESTING, so this implementation is not enabled by comparisions, such as in 'git rev-list --topo-order A..B'. This can be updated in the future.

In my local testing, I used the following Git commands on the Linux repository in three modes: HEAD~1 with no commit-graph, HEAD~1 with a commit-graph, and HEAD with a commit-graph. This allows comparing the benefits we get from parsing commits from the commit-graph and then again the benefits we get by restricting the set of commits we walk.

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

This speedup is due to a few things. First, the new generation- number-enabled algorithm walks commits on order of the number of results output (subject to some branching structure expectations). Since we limit to 100 results, we are running a query similar to filling a single page of results. Second, when specifying a path, we must parse the root tree object for each commit we walk. The previous benefits from the commit-graph are entirely from reading the commit-graph instead of parsing commits. Since we need to parse trees for the same number of commits as before, we slow down significantly from the non-path-based query.

For the test above, I specifically selected a path that is changed frequently, including by merge commits. A less-frequently-changed path (such as 'README') has similar end-to-end time since we need to walk the same number of commits (before determining we do not have 100 hits). However, get get the benefit that the output is presented to the user as it is discovered, much the same as a normal 'git log' command (no '--topo-order'). This is an improved user experience, even if the command has the same runtime.

---
 object.h   |   4 +-
 revision.c | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 revision.h |   2 +
 3 files changed, 194 insertions(+), 8 deletions(-)

index 0feb90ae61..796792cb32 100644
@@ -59,7 +59,7 @@ struct object_array {
 
 /*
  * object flag allocation:
- * revision.h:               0---------10                              2526
+ * revision.h:               0---------10                              25----28
  * fetch-pack.c:             01
  * negotiator/default.c:       2--5
  * walker.c:                 0-2

@@ -78,7 +78,7 @@ struct object_array {
  * builtin/show-branch.c:    0-------------------------------------------26
  * builtin/unpack-objects.c:                                 2021
  */
-#define FLAG_BITS  27
+#define FLAG_BITS  29
 
 /*
  * The object type is stored in 3 bits.

index e7bd059d80..7cc3bf5fc0 100644
@@ -24,6 +24,8 @@
 #define USER_GIVEN		(1u<<25) /* given directly by the user */
 #define TRACK_LINEAR		(1u<<26)
 #define ALL_REV_FLAGS		(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
+#define TOPO_WALK_EXPLORED	(1u<<27)
+#define TOPO_WALK_INDEGREE	(1u<<28)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2

gitgitgadget

Hello, Git contributors.

I understand that this commit message and patch are pretty daunting. There is a lot to read and digest. I would like to see if anyone is willing to put the work in to review this patch, as I quite like what it does, and the performance numbers below.

If there is something I can do to make this easier to review, then please let me know.

Thanks,
-Stolee

I'll try to find time to review v3 of this patch series this week.

A minor nit, but this commit message doesn't mention the most basic thing up front: that its main purpose is to introduce a new algorithm for topo-order. ;)

It's obvious in the context of reviewing the series, but somebody reading "git log" later may want a bit more. Perhaps:

revision.c: implement generation-based topo-order algorithm

as a subject, and/or an introductory paragraph like:

The current --topo-order algorithm requires walking all commits we are going to output up front, topo-sorting them, all before outputting the first value. This patch introduces a new algorithm which uses stored generation numbers to incrementally walk in topo-order, outputting commits as we go.

Other than that, I find this to be a wonderfully explanatory commit message. :)

OK, this makes sense. If we know that everybody else in our queue is at generation X, then it is safe to output a commit at generation greater than X.

I think this by itself would allow us to implement "show no parents before all of its children are shown", right? But --topo-order promises a bit more: "avoid showing commits no multiple lines of history intermixed".

I guess also INFINITY generation numbers need more. For a real generation number, we know that "gen(A) == gen(B)" implies that there is no ancestry relationship between the two. But not so for INFINITY.

I wondered how this would work for INFINITY. We can't know the order of a bunch of INFINITY nodes at all, so we never know when their in-degree values are "done". But if I understand the EXPLORE walk, we'd basically walk all of INFINITY down to something with a real generation number. Is that right?

But after that, I'm not totally clear on why we need this INDEGREE walk.

OK, this makes sense to make --author-date-order, etc, work. Potentially those numbers might have no relationship at all with the graph structure, but we promise "no parent before its children are shown", so this is really just a tie-breaker after the topo-sort anyway. As long as steps 1 and 2 are correct and produce a complete set of commits for one "layer", this should be OK.

I guess I'm not 100% convinced that we don't have a case where we haven't yet parsed or considered some commit that we know cannot have an ancestry relationship with commits we are outputting. But it may have an author-date-order relationship.

(I'm not at all convinced that this _is_ a problem, and I suspect it isn't; I'm only suggesting I haven't fully grokked the proof).

I'll pause here on evaluating the actual code. It looks sane from a cursory read, but there's no point in digging further until I'm sure I fully understand the algorithm. I think that needs a little more brain power from me, and hopefully discussion around my comments above will help trigger that.

-Peff

Good idea. I'll make that change.

Yeah, to deal with INFINITY (and ZERO, but that won't happen if generation_numbers_enabled() returns true), we treat gen(A) == gen(B) as a "no information" state. So, to output a commit at generation X, we need to have our maximum generation number in the unexplored area to be at most X - 1. You'll see strict inequality when checking generations.

The INDEGREE walk is an important element for Kahn's algorithm. The final output order is dictated by peeling commits of "indegree zero" to ensure all children are output before their parents. (Note: since we use literal 0 to mean "uninitialized", we peel commits when the indegree slab has value 1.)

This walk replaces the indegree logic from sort_in_topological_order(). That method performs one walk that fills the indegree slab, then another walk that peels the commits with indegree 0 and inserts them into a list.

The INDEGREE walk should not stop until it has explored at least to the point that all indegree 0 commits are exposed (relative to the current state of the walk).

At initialization, we walk from all starting positions until the maximum generation number in our queue is less than the minimum generation of a starting commit. The starting positions that have indegree 0 are then added to the topo_queue, and the sort order dictates which is the best. From this point on, we can only create a new "indegree 0" commit by removing a commit from the topo_queue and decrementing the indegree of its parents. Those parents with indegree 0 are inserted into topo_queue and compared to all other indegree 0 commits. Thus, we will always explore enough to make the right choice relative our sort order.

Thanks for reading! I understand that reading the code is useless without understanding the high-level concepts. I'm happy to iterate on this. If I can find a better way to explain the algorithm in the commit message to avoid the "huh?" moments above, then I will.

Thanks,
-Stolee

I guess my big question here was: if we have generation numbers, do we need Kahn's algorithm? That is, in a fully populated set of generation numbers (i.e., no INFINITY), we could always just pick a commit with the highest generation number to show.

So if we EXPLORE down to a real generation number in phase 1, why do we need to care about INDEGREE anymore? Or am I wrong that we always have a real generation number (i.e., not INFINITY) after EXPLORE? (And if so, why is exploring to a real generation number a bad idea; presumably it's due to a worst-case that goes deeper than we'd otherwise need to here).

Everything else you said here made perfect sense.

-Peff

The issue is that we our final order (used by level 3) is unrelated to generation number. Yes, if we prioritized by generation number then we could output the commits in _some_ order that doesn't violate topological constraints. However, we are asking for a different priority, which is different than the generation number priority.

In the case of "--topo-order", we want to output the commits reachable from the second parent of a merge before the commits reachable from the first parent. However, in most cases the generation number of the first parent is higher than the second parent (there are more things in the merge chain than in a small topic that got merged). The INDEGREE is what allows us to know when we can peel these commits while still respecting the priority we want at the end.

Thanks,
-Stolee

[...]

"get get"

This is most unwelcome while other topics are in flight that caused unnecessary conflict. It would have been very welcomed if the codebase was dormant, though.

I'll live, and there is no need to resend, but this change may not appear in today's pushout (I'll have to push out the result of integration before I saw this new reroll with all the other topics).

This patch series performs a decently-sized refactoring of the revision-walk machinery. Well, "refactoring" is probably the wrong word, as I don't actually remove the old code. Instead, when we see certain options in the 'rev_info' struct, we redirect the commit-walk logic to a new set of methods that distribute the workload differently. By using generation numbers in the commit-graph, we can significantly improve 'git log --graph' commands (and the underlying 'git rev-list --topo-order').

On the Linux repository, I got the following performance results when comparing to the previous version with or without a commit-graph:

Test: git rev-list --topo-order -100 HEAD
HEAD~1, no commit-graph: 6.80 s
HEAD~1, w/ commit-graph: 0.77 s
HEAD, w/ commit-graph: 0.02 s

Test: git rev-list --topo-order -100 HEAD -- tools HEAD~1, no commit-graph: 9.63 s
HEAD~1, w/ commit-graph: 6.06 s
HEAD, w/ commit-graph: 0.06 s

If you want to read this series but are unfamiliar with the commit-graph and generation numbers, then I recommend reading Documentation/technical/commit-graph.txt or a blob post [1] I wrote on the subject. In particular, the three-part walk described in "revision.c:
refactor basic topo-order logic" is present (but underexplained) as an animated PNG [2].

Since revision.c is an incredibly important (and old) portion of the codebase -- and because there are so many orthogonal options in 'struct rev_info' -- I consider this submission to be "RFC quality". That is, I am not confident that I am not missing anything, or that my solution is the best it can be. I did merge this branch with ds/commit-graph-with-grafts and the "DO-NOT-MERGE: write and read commit-graph always" commit that computes a commit-graph with every 'git commit' command. The test suite passed with that change, available on GitHub [3]. To ensure that I cover at least the case I think are interesting, I added tests to t6600-test-reach.sh to verify the walks report the correct results for the three cases there (no commit-graph, full commit-graph, and a partial commit-graph so the walk starts at GENERATION_NUMBER_INFINITY).

One notable case that is not included in this series is the case of a history comparison such as 'git rev-list --topo-order A..B'. The existing code in limit_list() has ways to cut the walk short when all pending commits are UNINTERESTING. Since this code depends on commit_list instead of the prio_queue we are using here, I chose to leave it untouched for now. We can revisit it in a separate series later. Since handle_commit() turns on revs->limited when a commit is UNINTERESTING, we do not hit the new code in this case. Removing this 'revs->limited = 1;' line yields correct results, but the performance is worse.

This series was based on ds/reachable, but is now based on 'master' to not conflict with 182070 "commit: use timestamp_t for author_date_slab". There is a small conflict with md/filter-trees, because it renamed a flag in revisions.h in the line before I add new flags. Hopefully this conflict is not too difficult to resolve.

Changes in V3: I added a new patch that updates the tab-alignment for flags in revision.h before adding new ones (Thanks, Ævar!). Also, I squashed the recommended changes to run_three_modes and test_three_modes from Szeder and Junio. Thanks!

Changes in V4: I'm sending a V4 to respond to the feedback so far. Still looking forward to more on the really big commit!

* Removed the whitespace changes to the flags in revision.c that caused merge pain.

* The prio-queue peek function is now covered by tests when in "stack" mode.

* The "add_parents_to_list()" function is now renamed to "process_parents()"

* Added a new commit that expands test coverage with alternate orders and file history (use GIT_TEST_COMMIT_GRAPH to have t6012-rev-list-simplify.sh cover the new logic). These tests found a problem with author dates (I forgot to record them during the explore walk).

* Commit message edits.

Thanks, -Stolee

[1]
https://blogs.msdn.microsoft.com/devops/2018/07/09/supercharging-the-git-commit-graph-iii-generations/
Supercharging the Git Commit Graph III: Generations and Graph Algorithms

[2]
https://msdnshared.blob.core.windows.net/media/2018/06/commit-graph-topo-order-b-a.png
Animation showing three-part walk

[3] https://github.com/derrickstolee/git/tree/topo-order/testA branch containing this series along with commits to compute commit-graph in entire test suite.

Derrick Stolee (7):
prio-queue: add 'peek' operation
test-reach: add run_three_modes method
test-reach: add rev-list tests revision.c: begin refactoring --topo-order logic commit/revisions: bookkeeping before refactoring revision.c: generation-based topo-order algorithm
t6012: make rev-list tests more interesting

 commit.c                     |  11 +-
 commit.h                     |   8 ++
 object.h                     |   4 +-
 prio-queue.c                 |   9 ++
 prio-queue.h                 |   6 +
 revision.c                   | 245 +++++++++++++++++++++++++++++++++--
 revision.h                   |   6 +
 t/helper/test-prio-queue.c   |  26 ++--
 t/t0009-prio-queue.sh        |  14 ++
 t/t6012-rev-list-simplify.sh |  45 +++++--
 t/t6600-test-reach.sh        |  96 +++++++++++++-
 11 files changed, 430 insertions(+), 40 deletions(-)

base-commit: 2d3b1c576c85b7f5db1f418907af00ab88e0c303
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-25%2Fderrickstolee%2Ftopo-order%2Fprogress-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-25/derrickstolee/topo-order/progress-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/25

Range-diff vs v3:

1: cc1ec4c270 ! 1: 2358cfd5ed prio-queue: add 'peek' operation

     @@ -8,7 +8,9 @@
          add it as prio_queue_peek().
      
          Add a reference-level comparison in t/helper/test-prio-queue.c
     -    so this method is exercised by t0009-prio-queue.sh.
     +    so this method is exercised by t0009-prio-queue.sh. Further, add
     +    a test that checks the behavior when the compare function is NULL
     +    (i.e. the queue becomes a stack).
      
          Signed-off-by: Derrick Stolee <[email protected]>
      
     @@ -56,6 +58,11 @@
      -		if (!strcmp(*argv, "get"))
      -			show(prio_queue_get(&pq));
      -		else if (!strcmp(*argv, "dump")) {
     +-			int *v;
     +-			while ((v = prio_queue_get(&pq)))
     +-			       show(v);
     +-		}
     +-		else {
      +		if (!strcmp(*argv, "get")) {
      +			void *peek = prio_queue_peek(&pq);
      +			void *get = prio_queue_get(&pq);
     @@ -63,6 +70,40 @@
      +				BUG("peek and get results do not match");
      +			show(get);
      +		} else if (!strcmp(*argv, "dump")) {
     - 			int *v;
     - 			while ((v = prio_queue_get(&pq)))
     - 			       show(v);
     ++			void *peek;
     ++			void *get;
     ++			while ((peek = prio_queue_peek(&pq))) {
     ++				get = prio_queue_get(&pq);
     ++				if (peek != get)
     ++					BUG("peek and get results do not match");
     ++				show(get);
     ++			}
     ++		} else if (!strcmp(*argv, "stack")) {
     ++			pq.compare = NULL;
     ++		} else {
     + 			int *v = malloc(sizeof(*v));
     + 			*v = atoi(*argv);
     + 			prio_queue_put(&pq, v);
     +
     +diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh
     +--- a/t/t0009-prio-queue.sh
     ++++ b/t/t0009-prio-queue.sh
     +@@
     + 	test_cmp expect actual
     + '
     + 
     ++cat >expect <<'EOF'
     ++3
     ++2
     ++6
     ++4
     ++5
     ++1
     ++8
     ++EOF
     ++test_expect_success 'stack order' '
     ++	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
     ++	test_cmp expect actual
     ++'
     ++
     + test_done
 2:  b2a1ade148 = 2:  3a4b68e479 test-reach: add run_three_modes method
 3:  b0ceb96076 = 3:  12a3f6d367 test-reach: add rev-list tests
 4:  fd1a0ab7cd = 4:  cd9eef9688 revision.c: begin refactoring --topo-order logic
 5:  e86f304082 ! 5:  f3e291665d commit/revisions: bookkeeping before refactoring

@@ -16,7 +16,11 @@
around the UNINTERESTING flag and other special cases depending on the struct rev_info. Allow this method to ignore a NULL 'list' parameter, as we will not be populating the list for our walk.
+ Also rename the method to the slightly more generic name
+ process_parents() to make clear that this method does more than
+ add to a list (and no list is required anymore).

+ Helped-by: Jeff King <[email protected]>

diff --git a/commit.c b/commit.c
@@ -28,7 +32,8 @@

-/* record author-date for each commit object */ -define_commit_slab(author_date_slab, timestamp_t);
--
++implement_shared_commit_slab(author_date_slab, timestamp_t);
+
-static void record_author_date(struct author_date_slab *author_date,
- struct commit *commit)
+void record_author_date(struct author_date_slab *author_date,
@@ -64,7 +69,7 @@
extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);

+/* record author-date for each commit object */
-+define_commit_slab(author_date_slab, timestamp_t); ++define_shared_commit_slab(author_date_slab, timestamp_t);
+
+void record_author_date(struct author_date_slab *author_date,
+ struct commit *commit);
@@ -77,6 +82,17 @@
diff --git a/revision.c b/revision.c
--- a/revision.c
+++ b/revision.c
+@@
+ *cache = new_entry;
+ }
+
+-static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
+- struct commit_list **list, struct commit_list **cache_ptr)
++static int process_parents(struct rev_info *revs, struct commit *commit,
++ struct commit_list **list, struct commit_list **cache_ptr)
+ {
+ struct commit_list *parent = commit->parents;
+ unsigned left_flag;
@@
if (p->object.flags & SEEN)
continue;
@@ -97,3 +113,39 @@
}
if (revs->first_parent_only)
break;
+@@
+
+ if (revs->max_age != -1 && (commit->date < revs->max_age))
+ obj->flags |= UNINTERESTING;
+- if (add_parents_to_list(revs, commit, &list, NULL) < 0)
++ if (process_parents(revs, commit, &list, NULL) < 0)
+ return -1;
+ if (obj->flags & UNINTERESTING) {
+ mark_parents_uninteresting(commit);
+@@
+
+ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
+ {
+- if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
++ if (process_parents(revs, commit, &revs->commits, NULL) < 0) {
+ if (!revs->ignore_missing_links)
+ die("Failed to traverse parents of commit %s",
+ oid_to_hex(&commit->object.oid));
+@@
+ for (;;) {
+ struct commit *p = *pp;
+ if (!revs->limited)
+- if (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)
++ if (process_parents(revs, p, &revs->commits, &cache) < 0)
+ return rewrite_one_error;
+ if (p->object.flags & UNINTERESTING)
+ return rewrite_one_ok;
+@@
+ try_to_simplify_commit(revs, commit);
+ else if (revs->topo_walk_info)
+ expand_topo_walk(revs, commit);
+- else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
++ else if (process_parents(revs, commit, &revs->commits, NULL) < 0) {
+ if (!revs->ignore_missing_links)
+ die("Failed to traverse parents of commit %s",
+ oid_to_hex(&commit->object.oid));

 6:  fa6d5ef152 < -:  ---------- revision.h: add whitespace in flag definitions
 7:  020b2f50c5 ! 6:  aa0bb2221d revision.c: refactor basic topo-order logic
     @@ -1,6 +1,15 @@
      Author: Derrick Stolee <[email protected]>
      
     -    revision.c: refactor basic topo-order logic
     +    revision.c: generation-based topo-order algorithm
     +
     +    The current --topo-order algorithm requires walking all
     +    reachable commits up front, topo-sorting them, all before
     +    outputting the first value. This patch introduces a new
     +    algorithm which uses stored generation numbers to
     +    incrementally walk in topo-order, outputting commits as
     +    we go. This can dramatically reduce the computation time
     +    to write a fixed number of commits, such as when limiting
     +    with "-n <N>" or filling the first page of a pager.
      
          When running a command like 'git rev-list --topo-order HEAD',
          Git performed the following steps:
     @@ -139,11 +148,12 @@
          frequently, including by merge commits. A less-frequently-changed
          path (such as 'README') has similar end-to-end time since we need
          to walk the same number of commits (before determining we do not
     -    have 100 hits). However, get get the benefit that the output is
     +    have 100 hits). However, get the benefit that the output is
          presented to the user as it is discovered, much the same as a
          normal 'git log' command (no '--topo-order'). This is an improved
          user experience, even if the command has the same runtime.
      
     +    Helped-by: Jeff King <[email protected]>
          Signed-off-by: Derrick Stolee <[email protected]>
      
      diff --git a/object.h b/object.h
     @@ -216,10 +226,13 @@
      +	if (parse_commit_gently(c, 1) < 0)
      +		return;
      +
     ++	if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE)
     ++		record_author_date(&info->author_date, c);
     ++
      +	if (revs->max_age != -1 && (c->date < revs->max_age))
      +		c->object.flags |= UNINTERESTING;
      +
     -+	if (add_parents_to_list(revs, c, NULL, NULL) < 0)
     ++	if (process_parents(revs, c, NULL, NULL) < 0)
      +		return;
      +
      +	if (c->object.flags & UNINTERESTING)
     @@ -366,10 +379,10 @@
       
       static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
       {
     --	if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
     +-	if (process_parents(revs, commit, &revs->commits, NULL) < 0) {
      +	struct commit_list *p;
      +	struct topo_walk_info *info = revs->topo_walk_info;
     -+	if (add_parents_to_list(revs, commit, NULL, NULL) < 0) {
     ++	if (process_parents(revs, commit, NULL, NULL) < 0) {
       		if (!revs->ignore_missing_links)
       			die("Failed to traverse parents of commit %s",
      -			    oid_to_hex(&commit->object.oid));
     @@ -404,9 +417,9 @@
      --- a/revision.h
      +++ b/revision.h
      @@
     - #define USER_GIVEN		(1u<<25) /* given directly by the user */
     - #define TRACK_LINEAR		(1u<<26)
     - #define ALL_REV_FLAGS		(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
     + #define USER_GIVEN	(1u<<25) /* given directly by the user */
     + #define TRACK_LINEAR	(1u<<26)
     + #define ALL_REV_FLAGS	(((1u<<11)-1) | USER_GIVEN | TRACK_LINEAR)
      +#define TOPO_WALK_EXPLORED	(1u<<27)
      +#define TOPO_WALK_INDEGREE	(1u<<28)

-: ---------- > 7: a21febe112 t6012: make rev-list tests more interesting

gitgitgadget

From: Derrick Stolee <[email protected]>

When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek().

Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh. Further, add a test that checks the behavior when the compare function is NULL (i.e. the queue becomes a stack).

---
 prio-queue.c               |  9 +++++++++
 prio-queue.h               |  6 ++++++
 t/helper/test-prio-queue.c | 26 ++++++++++++++++++--------
 t/t0009-prio-queue.sh      | 14 ++++++++++++++
 4 files changed, 47 insertions(+), 8 deletions(-)

index a078451872..d3f488cb05 100644
@@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue)
 	}
 	return result;
 }
+
+void *prio_queue_peek(struct prio_queue *queue)
+{
+	if (!queue->nr)
+		return NULL;
+	if (!queue->compare)
+		return queue->array[queue->nr - 1].data;
+	return queue->array[0].data;
+}

index d030ec9dd6..682e51867a 100644
@@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing);
  */
 extern void *prio_queue_get(struct prio_queue *);
 
+/*
+ * Gain access to the "thing" that would be returned by
+ * prio_queue_get, but do not remove it from the queue.
+ */
+extern void *prio_queue_peek(struct prio_queue *);
+
 extern void clear_prio_queue(struct prio_queue *);
 
 /* Reverse the LIFO elements */

index 9807b649b1..5bc9c46ea5 100644
@@ -22,14 +22,24 @@ int cmd__prio_queue(int argc, const char **argv)
 	struct prio_queue pq = { intcmp };
 
 	while (*++argv) {
-		if (!strcmp(*argv, "get"))
-			show(prio_queue_get(&pq));
-		else if (!strcmp(*argv, "dump")) {
-			int *v;
-			while ((v = prio_queue_get(&pq)))
-			       show(v);
-		}
-		else {
+		if (!strcmp(*argv, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			show(get);
+		} else if (!strcmp(*argv, "dump")) {
+			void *peek;
+			void *get;
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results do not match");
+				show(get);
+			}
+		} else if (!strcmp(*argv, "stack")) {
+			pq.compare = NULL;
+		} else {
 			int *v = malloc(sizeof(*v));
 			*v = atoi(*argv);
 			prio_queue_put(&pq, v);

index e56dfce668..3941ad2528 100755
@@ -47,4 +47,18 @@ test_expect_success 'notice empty queue' '
 	test_cmp expect actual
 '
 
+cat >expect <<'EOF'
+3
+2
+6
+4
+5
+1
+8
+EOF
+test_expect_success 'stack order' '
+	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
+	test_cmp expect actual
+'
+
 test_done

gitgitgadget

From: Derrick Stolee <[email protected]>

The 'test_three_modes' method assumes we are using the 'test-tool reach' command for our test. However, we may want to use the data shape of our commit graph and the three modes (no commit-graph, full commit-graph, partial commit-graph) for other git commands.

Split test_three_modes to be a simple translation on a more general run_three_modes method that executes the given command and tests the actual output to the expected output.

---
 t/t6600-test-reach.sh | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

index d139a00d1d..9d65b8b946 100755
@@ -53,18 +53,22 @@ test_expect_success 'setup' '
 	git config core.commitGraph true
 '
 
-test_three_modes () {
+run_three_modes () {
 	test_when_finished rm -rf .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-full .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual &&
 	cp commit-graph-half .git/objects/info/commit-graph &&
-	test-tool reach $1 <input >actual &&
+	"$@" <input >actual &&
 	test_cmp expect actual
 }
 
+test_three_modes () {
+	run_three_modes test-tool reach "$@"
+}
+
 test_expect_success 'ref_newer:miss' '
 	cat >input <<-\EOF &&
 	A:commit-5-7

gitgitgadget

From: Derrick Stolee <[email protected]>

The rev-list command is critical to Git's functionality. Ensure it works in the three commit-graph environments constructed in t6600-test-reach.sh. Here are a few important types of rev-list operations:

* Basic: git rev-list --topo-order HEAD
* Range: git rev-list --topo-order compare..HEAD
* Ancestry: git rev-list --topo-order --ancestry-path compare..HEAD
* Symmetric Difference: git rev-list --topo-order compare...HEAD

---
 t/t6600-test-reach.sh | 84 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)

index 9d65b8b946..288f703b7b 100755
@@ -243,4 +243,88 @@ test_expect_success 'commit_contains:miss' '
 	test_three_modes commit_contains --tag
 '
 
+test_expect_success 'rev-list: basic topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
+		commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-6-6
+'
+
+test_expect_success 'rev-list: first-parent topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
+	>expect &&
+	run_three_modes git rev-list --first-parent --topo-order commit-6-6
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
+'
+
+test_expect_success 'rev-list: range topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
+'
+
+test_expect_success 'rev-list: first-parent range topo-order' '
+	git rev-parse \
+		commit-6-6 \
+		commit-6-5 \
+		commit-6-4 \
+		commit-6-3 \
+		commit-6-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+	>expect &&
+	run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
+'
+
+test_expect_success 'rev-list: ancestry-path topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
+		commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
+		commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+	>expect &&
+	run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
+'
+
+test_expect_success 'rev-list: symmetric difference topo-order' '
+	git rev-parse \
+		commit-6-6 commit-5-6 commit-4-6 \
+		commit-6-5 commit-5-5 commit-4-5 \
+		commit-6-4 commit-5-4 commit-4-4 \
+		commit-6-3 commit-5-3 commit-4-3 \
+		commit-6-2 commit-5-2 commit-4-2 \
+		commit-6-1 commit-5-1 commit-4-1 \
+		commit-3-8 commit-2-8 commit-1-8 \
+		commit-3-7 commit-2-7 commit-1-7 \
+	>expect &&
+	run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
+'
+
 test_done

gitgitgadget

Could you remind us here which of those operations will be using generation numbers after this patch series?

For this series, we are focused only on the --topo-order with a single start position. The versions that use a compare branch still use the old logic. In the future, I would like to use the new logic for these other modes.

I did lay out the branch names in a grid layout similar to the commit-graph layout. It's easier to see the purposeful layout in the comparison sections where some commits don't appear in the output.

Thanks,

-Stolee

From: Derrick Stolee <[email protected]>

When running 'git rev-list --topo-order' and its kin, the topo_order setting in struct rev_info implies the limited setting. This means that the following things happen during prepare_revision_walk():

* revs->limited implies we run limit_list() to walk the entire reachable set. There are some short-cuts here, such as if we perform a range query like 'git rev-list COMPARE..HEAD' and we can stop limit_list() when all queued commits are uninteresting.

* revs->topo_order implies we run sort_in_topological_order(). See the implementation of that method in commit.c. It implies that the full set of commits to order is in the given commit_list.

These two methods imply that a 'git rev-list --topo-order HEAD' command must walk the entire reachable set of commits _twice_ before returning a single result.

If we have a commit-graph file with generation numbers computed, then there is a better way. This patch introduces some necessary logic redirection when we are in this situation.

In v2.18.0, the commit-graph file contains zero-valued bytes in the positions where the generation number is stored in v2.19.0 and later. Thus, we use generation_numbers_enabled() to check if the commit-graph is available and has non-zero generation numbers.

When setting revs->limited only because revs->topo_order is true, only do so if generation numbers are not available. There is no reason to use the new logic as it will behave similarly when all generation numbers are INFINITY or ZERO.

In prepare_revision_walk(), if we have revs->topo_order but not revs->limited, then we trigger the new logic. It breaks the logic into three pieces, to fit with the existing framework:

1. init_topo_walk() fills a new struct topo_walk_info in the rev_info struct. We use the presence of this struct as a signal to use the new methods during our walk. In this patch, this method simply calls limit_list() and sort_in_topological_order(). In the future, this method will set up a new data structure to perform that logic in-line.

2. next_topo_commit() provides get_revision_1() with the next topo- ordered commit in the list. Currently, this simply pops the commit from revs->commits.

3. expand_topo_walk() provides get_revision_1() with a way to signal walking beyond the latest commit. Currently, this calls add_parents_to_list() exactly like the old logic.

While this commit presents method redirection for performing the exact same logic as before, it allows the next commit to focus only on the new logic.

---
 revision.c | 42 ++++++++++++++++++++++++++++++++++++++----
 revision.h |  4 ++++
 2 files changed, 42 insertions(+), 4 deletions(-)

index e18bd530e4..2dcde8a8ac 100644
@@ -25,6 +25,7 @@
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"
+#include "commit-graph.h"
 
 volatile show_early_output_fn_t show_early_output;
 

@@ -2454,7 +2455,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->diffopt.objfind)
 		revs->simplify_history = 0;
 
-	if (revs->topo_order)
+	if (revs->topo_order && !generation_numbers_enabled(the_repository))
 		revs->limited = 1;
 
 	if (revs->prune_data.nr) {

@@ -2892,6 +2893,33 @@ static int mark_uninteresting(const struct object_id *oid,
 	return 0;
 }
 
+struct topo_walk_info {};
+
+static void init_topo_walk(struct rev_info *revs)
+{
+	struct topo_walk_info *info;
+	revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info));
+	info = revs->topo_walk_info;
+	memset(info, 0, sizeof(struct topo_walk_info));
+
+	limit_list(revs);
+	sort_in_topological_order(&revs->commits, revs->sort_order);
+}
+
+static struct commit *next_topo_commit(struct rev_info *revs)
+{
+	return pop_commit(&revs->commits);
+}
+
+static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
+{
+	if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+		if (!revs->ignore_missing_links)
+			die("Failed to traverse parents of commit %s",
+			    oid_to_hex(&commit->object.oid));
+	}
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int i;

@@ -2928,11 +2956,13 @@ int prepare_revision_walk(struct rev_info *revs)
 		commit_list_sort_by_date(&revs->commits);
 	if (revs->no_walk)
 		return 0;
-	if (revs->limited)
+	if (revs->limited) {
 		if (limit_list(revs) < 0)
 			return -1;
-	if (revs->topo_order)
-		sort_in_topological_order(&revs->commits, revs->sort_order);
+		if (revs->topo_order)
+			sort_in_topological_order(&revs->commits, revs->sort_order);
+	} else if (revs->topo_order)
+		init_topo_walk(revs);
 	if (revs->line_level_traverse)
 		line_log_filter(revs);
 	if (revs->simplify_merges)

@@ -3257,6 +3287,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 		if (revs->reflog_info)
 			commit = next_reflog_entry(revs->reflog_info);
+		else if (revs->topo_walk_info)
+			commit = next_topo_commit(revs);
 		else
 			commit = pop_commit(&revs->commits);
 

@@ -3278,6 +3310,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 			if (revs->reflog_info)
 				try_to_simplify_commit(revs, commit);
+			else if (revs->topo_walk_info)
+				expand_topo_walk(revs, commit);
 			else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
 				if (!revs->ignore_missing_links)
 					die("Failed to traverse parents of commit %s",

index 2b30ac270d..fd4154ff75 100644
@@ -56,6 +56,8 @@ struct rev_cmdline_info {
 #define REVISION_WALK_NO_WALK_SORTED 1
 #define REVISION_WALK_NO_WALK_UNSORTED 2
 
+struct topo_walk_info;
+
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;

@@ -245,6 +247,8 @@ struct rev_info {
 	const char *break_bar;
 
 	struct revision_sources *sources;
+
+	struct topo_walk_info *topo_walk_info;
 };
 
 int ref_excluded(struct string_list *, const char *path);

gitgitgadget

And if revs->topo_order is set, then (with current implementation) we need limit_list() to run to generate commit_list with commits to be topologically sorted, which is done by setting revs->limited.

In short, with current code revs->topo_order implies revs->limited.

So the current code uses "generate list of commits, then sort it" approach...

...instead of generating commits in topological order as you go.

O.K., this should make main commit smaller. All right.

O.K. we will be using new algorithm only when there actually are some generation numbers.

So if revs->limited is set (but not because revs->topo_order is set), which means A..B queries, we will be still using the old algorithm. All right, though I wonder if it could be improved in the future (perhaps with the help of other graph labelling / indices than generation numbers, maybe a positive-cut index).

Do you have an idea why there is no improvement with the new code in this case?

So all three new functions should perform exactly like the old logic, isn't it?

All right, it's logical.

  +	memset(revs->topo_walk_info, 0, sizeof(struct topo_walk_info));

	if (limit_list(revs) < 0)
		return -1;
	if (revs->topo_order)
		sort_in_topological_order(&revs->commits, revs->sort_order);

I didn't get the impression that it would not be possible to improve the "--topo A..B" case by using generation numbers from this series. Isn't it just because the necessary code has not been written yet? In addition to what is needed for "--topo P1 P2 P3..." (all positive), limited walk needs to notice the bottom boundary and stop traversal. Having generation numbers would make it slightly easier than without, as you know that a positive commit you have will not be marked UNINTERESTING due to a negative commit whose ancestors have not been explored, as long as that negative commit has a higher generation number. But you still need to adjust the traversal logic to properly terminate upon hitting UNINTERESTING one, and also propagate the bit down the history, which is not needed at all if you only want to support the "positive only" case.

Actually, the code has been written, but the problem is the same as the performance issue when I made paint_down_to_common() use generation numbers: the algorithm for deciding what is in the set "reachable from A but not reachable from B" uses commit-date order as a heuristic to avoid walking the entire graph. Yes, the revision parameters specify "limited" in order to call "limit_list()", but it uses the same algorithm to determine the reachable set difference.

You can test this yourself! Run the following two commands in the Git repository using v2.19.1:

    time git log --topo-order -10 master >/dev/null

    time git log --topo-order -10 maint..master >/dev/null

I get 0.39s for the first call and 0.01s for the second. (Note: I specified "-10" to ensure we are only writing 10 commits and the output size does not factor into the time.) This is because the first walks the entire history, while the second uses the heuristic walk to identify a much smaller subgraph that the topo-order algorithm uses.

Just as before, by using this algorithm for the B..A case, we are adding an extra restriction on the algorithm: always be correct. This results in us walking a larger set (everything reachable from B or A with generation number at least the smallest generation of a commit reachable from only one).

I believe this can be handled by using a smarter generation number (one that relies on commit date as a heuristic, but still have enough information to guarantee topological relationships), and I've already started testing a few of these directions. It is possible now that we have concrete graph algorithms to use on real repositories. I hope to share a report on my findings in a couple weeks. I'll include how using this algorithm compares to the old algorithm in the B..A case.

Thanks,

-Stolee

---

I just wanted to mention that in order to use the new logic for 'git log --topo-order A..B', we just need the following patch. It is an extra time that sets 'revs->limited' to 1, triggering the old logic.