[PATCH v5 00/11] Compute and consume generation numbers

[Derrick Stolee <dstolee@microsoft.com>]

Most of the changes from v4 are cosmetic, but there is one new commit:

	commit: use generation number in remove_redundant()

Other changes are non-functional, but do clarify things.

Inter-diff from v4:

diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt
index d9f2713efa..e1a883eb46 100644
--- a/Documentation/technical/commit-graph.txt
+++ b/Documentation/technical/commit-graph.txt
@@ -125,9 +125,10 @@ Future Work
   walks aware of generation numbers to gain the performance benefits they
   enable. This will mostly be accomplished by swapping a commit-date-ordered
   priority queue with one ordered by generation number. The following
-  operation is an important candidate:
+  operations are important candidates:

     - 'log --topo-order'
+    - 'tag --merged'

 - Currently, parse_commit_gently() requires filling in the root tree
   object for a commit. This passes through lookup_tree() and consequently
diff --git a/commit-graph.c b/commit-graph.c
index aebd242def..a8c337dd77 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -248,6 +248,7 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,
 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
 {
        const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
+       item->graph_pos = pos;
        item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 }

@@ -454,8 +455,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
                else
                        packedDate[0] = 0;

-               if ((*list)->generation != GENERATION_NUMBER_INFINITY)
-                       packedDate[0] |= htonl((*list)->generation << 2);
+               packedDate[0] |= htonl((*list)->generation << 2);

                packedDate[1] = htonl((*list)->date);
                hashwrite(f, packedDate, 8);
@@ -589,18 +589,17 @@ static void close_reachable(struct packed_oid_list *oids)
        }
 }

-static void compute_generation_numbers(struct commit** commits,
-                                      int nr_commits)
+static void compute_generation_numbers(struct packed_commit_list* commits)
 {
        int i;
        struct commit_list *list = NULL;

-       for (i = 0; i < nr_commits; i++) {
-               if (commits[i]->generation != GENERATION_NUMBER_INFINITY &&
-                   commits[i]->generation != GENERATION_NUMBER_ZERO)
+       for (i = 0; i < commits->nr; i++) {
+               if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
+                   commits->list[i]->generation != GENERATION_NUMBER_ZERO)
                        continue;

-               commit_list_insert(commits[i], &list);
+               commit_list_insert(commits->list[i], &list);
                while (list) {
                        struct commit *current = list->item;
                        struct commit_list *parent;
@@ -621,10 +620,10 @@ static void compute_generation_numbers(struct commit** commits,
                        if (all_parents_computed) {
                                current->generation = max_generation + 1;
                                pop_commit(&list);
-                       }

-                       if (current->generation > GENERATION_NUMBER_MAX)
-                               current->generation = GENERATION_NUMBER_MAX;
+                               if (current->generation > GENERATION_NUMBER_MAX)
+                                       current->generation = GENERATION_NUMBER_MAX;
+                       }
                }
        }
 }
@@ -752,7 +751,7 @@ void write_commit_graph(const char *obj_dir,
        if (commits.nr >= GRAPH_PARENT_MISSING)
                die(_("too many commits to write graph"));

-       compute_generation_numbers(commits.list, commits.nr);
+       compute_generation_numbers(&commits);

        graph_name = get_commit_graph_filename(obj_dir);
        fd = hold_lock_file_for_update(&lk, graph_name, 0);
diff --git a/commit.c b/commit.c
index e2e16ea1a7..5064db4e61 100644
--- a/commit.c
+++ b/commit.c
@@ -835,7 +835,9 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n,
                int flags;

                if (commit->generation > last_gen)
-                       BUG("bad generation skip");
+                       BUG("bad generation skip %8x > %8x at %s",
+                           commit->generation, last_gen,
+                           oid_to_hex(&commit->object.oid));
                last_gen = commit->generation;

                if (commit->generation < min_generation)
@@ -947,6 +949,7 @@ static int remove_redundant(struct commit **array, int cnt)
                parse_commit(array[i]);
        for (i = 0; i < cnt; i++) {
                struct commit_list *common;
+               uint32_t min_generation = GENERATION_NUMBER_INFINITY;

                if (redundant[i])
                        continue;
@@ -955,8 +958,12 @@ static int remove_redundant(struct commit **array, int cnt)
                                continue;
                        filled_index[filled] = j;
                        work[filled++] = array[j];
+
+                       if (array[j]->generation < min_generation)
+                               min_generation = array[j]->generation;
                }
-               common = paint_down_to_common(array[i], filled, work, 0);
+               common = paint_down_to_common(array[i], filled, work,
+                                             min_generation);
                if (array[i]->object.flags & PARENT2)
                        redundant[i] = 1;
                for (j = 0; j < filled; j++)
@@ -1073,7 +1080,7 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
        for (i = 0; i < nr_reference; i++) {
                if (parse_commit(reference[i]))
                        return ret;
-               if (min_generation > reference[i]->generation)
+               if (reference[i]->generation < min_generation)
                        min_generation = reference[i]->generation;
        }


-- >8 --

Derrick Stolee (11):
  ref-filter: fix outdated comment on in_commit_list
  commit: add generation number to struct commmit
  commit-graph: compute generation numbers
  commit: use generations in paint_down_to_common()
  commit-graph: always load commit-graph information
  ref-filter: use generation number for --contains
  commit: use generation numbers for in_merge_bases()
  commit: add short-circuit to paint_down_to_common()
  commit: use generation number in remove_redundant()
  merge: check config before loading commits
  commit-graph.txt: update design document

 Documentation/technical/commit-graph.txt | 30 ++++++--
 alloc.c                                  |  1 +
 builtin/merge.c                          |  7 +-
 commit-graph.c                           | 91 ++++++++++++++++++++----
 commit-graph.h                           |  8 +++
 commit.c                                 | 61 +++++++++++++---
 commit.h                                 |  7 +-
 object.c                                 |  2 +-
 ref-filter.c                             | 26 +++++--
 sha1_file.c                              |  2 +-
 t/t5318-commit-graph.sh                  |  9 +++
 11 files changed, 204 insertions(+), 40 deletions(-)


base-commit: 7b8a21dba1bce44d64bd86427d3d92437adc4707
-- 
2.17.0.39.g685157f7fb