revision.c: begin refactoring --topo-order logic

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.

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

diff --git a/revision.c b/revision.c
index e18bd530e4c50d0f5a1887714b074a6c2c63875b..2dcde8a8ac7926991faf23b650c2f6ada17d7e5a 100644 (file)
--- a/revision.c
+++ b/revision.c
@@ -25,6 +25,7 @@
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"
 #include "worktree.h"
 #include "argv-array.h"
 #include "commit-reach.h"

+#include "commit-graph.h"

 
 volatile show_early_output_fn_t show_early_output;
 
 
 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->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) {
                revs->limited = 1;
 
        if (revs->prune_data.nr) {


@@ -2892,6 +2893,33 @@ static int mark_uninteresting(const struct object_id *oid,
        return 0;
 }
 
        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;
 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;
                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 (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)
        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);
 
                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);
 
                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);
 
                        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",
                        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",

diff --git a/revision.h b/revision.h
index 2b30ac270d9295e00641b08483fe07cd44dc51f6..fd4154ff7584635af5ef17922c1f8a3dbdab14f0 100644 (file)
--- a/revision.h
+++ b/revision.h
@@ -56,6 +56,8 @@ struct rev_cmdline_info {
 #define REVISION_WALK_NO_WALK_SORTED 1
 #define REVISION_WALK_NO_WALK_UNSORTED 2
 
 #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;
 struct rev_info {
        /* Starting list */
        struct commit_list *commits;


@@ -245,6 +247,8 @@ struct rev_info {
        const char *break_bar;
 
        struct revision_sources *sources;
        const char *break_bar;
 
        struct revision_sources *sources;

+
+       struct topo_walk_info *topo_walk_info;

 };
 
 int ref_excluded(struct string_list *, const char *path);
 };
 
 int ref_excluded(struct string_list *, const char *path);