commit-graph: prepare for commit-graph chains

To prepare for a chain of commit-graph files, augment the
commit_graph struct to point to a base commit_graph. As we load
commits from the graph, we may actually want to read from a base
file according to the graph position.

The "graph position" of a commit is given by concatenating the
lexicographic commit orders from each of the commit-graph files in
the chain. This means that we must distinguish two values:

* lexicographic index : the position within the lexicographic
order in a single commit-graph file.

* graph position: the position within the concatenated order
of multiple commit-graph files

Given the lexicographic index of a commit in a graph, we can
compute the graph position by adding the number of commits in
the lower-level graphs. To find the lexicographic index of
a commit, we subtract the number of commits in lower-level graphs.

While here, change insert_parent_or_die() to take a uint32_t
position, as that is the type used by its only caller and that
makes more sense with the limits in the commit-graph format.

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

diff --git a/commit-graph.c b/commit-graph.c
index 76d189de45416165fea039e7be67375b30e7a230..8f5c09363c4a541906aa95df4a897feb7712fc68 100644 (file)
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -359,9 +359,18 @@ int generation_numbers_enabled(struct repository *r)
        return !!first_generation;
 }
 
+static void close_commit_graph_one(struct commit_graph *g)
+{
+       if (!g)
+               return;
+
+       close_commit_graph_one(g->base_graph);
+       free_commit_graph(g);
+}
+
 void close_commit_graph(struct raw_object_store *o)
 {
-       free_commit_graph(o->commit_graph);
+       close_commit_graph_one(o->commit_graph);
        o->commit_graph = NULL;
 }
 
@@ -371,18 +380,38 @@ static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t
                            g->chunk_oid_lookup, g->hash_len, pos);
 }
 
+static void load_oid_from_graph(struct commit_graph *g,
+                               uint32_t pos,
+                               struct object_id *oid)
+{
+       uint32_t lex_index;
+
+       while (g && pos < g->num_commits_in_base)
+               g = g->base_graph;
+
+       if (!g)
+               BUG("NULL commit-graph");
+
+       if (pos >= g->num_commits + g->num_commits_in_base)
+               die(_("invalid commit position. commit-graph is likely corrupt"));
+
+       lex_index = pos - g->num_commits_in_base;
+
+       hashcpy(oid->hash, g->chunk_oid_lookup + g->hash_len * lex_index);
+}
+
 static struct commit_list **insert_parent_or_die(struct repository *r,
                                                 struct commit_graph *g,
-                                                uint64_t pos,
+                                                uint32_t pos,
                                                 struct commit_list **pptr)
 {
        struct commit *c;
        struct object_id oid;
 
-       if (pos >= g->num_commits)
-               die("invalid parent position %"PRIu64, pos);
+       if (pos >= g->num_commits + g->num_commits_in_base)
+               die("invalid parent position %"PRIu32, pos);
 
-       hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
+       load_oid_from_graph(g, pos, &oid);
        c = lookup_commit(r, &oid);
        if (!c)
                die(_("could not find commit %s"), oid_to_hex(&oid));
@@ -392,7 +421,14 @@ static struct commit_list **insert_parent_or_die(struct repository *r,
 
 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;
+       const unsigned char *commit_data;
+       uint32_t lex_index;
+
+       while (pos < g->num_commits_in_base)
+               g = g->base_graph;
+
+       lex_index = pos - g->num_commits_in_base;
+       commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
        item->graph_pos = pos;
        item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 }
@@ -405,10 +441,25 @@ static int fill_commit_in_graph(struct repository *r,
        uint32_t *parent_data_ptr;
        uint64_t date_low, date_high;
        struct commit_list **pptr;
-       const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * pos;
+       const unsigned char *commit_data;
+       uint32_t lex_index;
 
-       item->object.parsed = 1;
+       while (pos < g->num_commits_in_base)
+               g = g->base_graph;
+
+       if (pos >= g->num_commits + g->num_commits_in_base)
+               die(_("invalid commit position. commit-graph is likely corrupt"));
+
+       /*
+        * Store the "full" position, but then use the
+        * "local" position for the rest of the calculation.
+        */
        item->graph_pos = pos;
+       lex_index = pos - g->num_commits_in_base;
+
+       commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
+
+       item->object.parsed = 1;
 
        item->maybe_tree = NULL;
 
@@ -452,7 +503,18 @@ static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uin
                *pos = item->graph_pos;
                return 1;
        } else {
-               return bsearch_graph(g, &(item->object.oid), pos);
+               struct commit_graph *cur_g = g;
+               uint32_t lex_index;
+
+               while (cur_g && !bsearch_graph(cur_g, &(item->object.oid), &lex_index))
+                       cur_g = cur_g->base_graph;
+
+               if (cur_g) {
+                       *pos = lex_index + cur_g->num_commits_in_base;
+                       return 1;
+               }
+
+               return 0;
        }
 }
 
@@ -492,8 +554,13 @@ static struct tree *load_tree_for_commit(struct repository *r,
                                         struct commit *c)
 {
        struct object_id oid;
-       const unsigned char *commit_data = g->chunk_commit_data +
-                                          GRAPH_DATA_WIDTH * (c->graph_pos);
+       const unsigned char *commit_data;
+
+       while (c->graph_pos < g->num_commits_in_base)
+               g = g->base_graph;
+
+       commit_data = g->chunk_commit_data +
+                       GRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);
 
        hashcpy(oid.hash, commit_data);
        c->maybe_tree = lookup_tree(r, &oid);

diff --git a/commit-graph.h b/commit-graph.h
index 390c7f696104fbe772151b91cb04889d0f682401..5819910a5b22d92877be516f8a19fa6b26911c0f 100644 (file)
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -48,6 +48,9 @@ struct commit_graph {
        uint32_t num_commits;
        struct object_id oid;
 
+       uint32_t num_commits_in_base;
+       struct commit_graph *base_graph;
+
        const uint32_t *chunk_oid_fanout;
        const unsigned char *chunk_oid_lookup;
        const unsigned char *chunk_commit_data;