revision: use generation for A..B --topo-order queries

If a commit-graph exists with computed generation numbers, then a
'git rev-list --topo-order -n <N> <rev>' query will use those generation
numbers to reduce the number of commits walked before writing N commits.

One caveat put in b454241 (revision.c: generation-based topo-order
algorithm, 2018-11-01) was to not enable the new algorithm for queries
with a revision range "A..B". The logic was placed to walk from "A" and
mark those commits as uninteresting, but the performance was actually
worse than the existing logic in some cases.

The root cause of this performance degradation is that generation
numbers _increase_ the number of commits we walk relative to the
existing heuristic of walking by commit date. While generation numbers
actually guarantee that the algorithm is correct, the existing logic
is very rarely wrong and that added requirement is not worth the cost.

This motivates the planned "corrected commit date" to replace
generation numbers in a future version of Git.

The current change enables the logic to use whatever reachability
index is currently in the commit-graph (generation numbers or
corrected commit date).

The limited flag in struct rev_info forces a full walk of the
commit history (after discovering the A..B range). Previosuly, it
is enabled whenever we see an uninteresting commit. We prevent
enabling the parameter when we are planning to use the reachability
index for a topo-order.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 3 insertions, 1 deletions

diff --git a/revision.c b/revision.c
index d4aaf0ef25..be6ccf5786 100644
--- a/revision.c
+++ b/revision.c
@@ -436,7 +436,9 @@ static struct commit *handle_commit(struct rev_info *revs,
 			die("unable to parse commit %s", name);
 		if (flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
-			revs->limited = 1;
+
+			if (!revs->topo_order || !generation_numbers_enabled(the_repository))
+				revs->limited = 1;
 		}
 		if (revs->sources) {
 			char **slot = revision_sources_at(revs->sources, commit);