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

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;
        }