src/libgit2/commit_graph.h

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #ifndef INCLUDE_commit_graph_h__
   9 #define INCLUDE_commit_graph_h__
  10
  11 #include "common.h"
  12
  13 #include "git2/types.h"
  14 #include "git2/sys/commit_graph.h"
  15
  16 #include "map.h"
  17 #include "vector.h"
  18 #include "oid.h"
  19 #include "hash.h"
  20
  21 /**
  22  * A commit-graph file.
  23  *
  24  * This file contains metadata about commits, particularly the generation
  25  * number for each one. This can help speed up graph operations without
  26  * requiring a full graph traversal.
  27  *
  28  * Support for this feature was added in git 2.19.
  29  */
  30 typedef struct git_commit_graph_file {
  31         git_map graph_map;
  32
  33         /* The OID Fanout table. */
  34         const uint32_t *oid_fanout;
  35         /* The total number of commits in the graph. */
  36         uint32_t num_commits;
  37
  38         /* The OID Lookup table. */
  39         unsigned char *oid_lookup;
  40
  41         /*
  42          * The Commit Data table. Each entry contains the OID of the commit followed
  43          * by two 8-byte fields in network byte order:
  44          * - The indices of the first two parents (32 bits each).
  45          * - The generation number (first 30 bits) and commit time in seconds since
  46          *   UNIX epoch (34 bits).
  47          */
  48         const unsigned char *commit_data;
  49
  50         /*
  51          * The Extra Edge List table. Each 4-byte entry is a network byte order index
  52          * of one of the i-th (i > 0) parents of commits in the `commit_data` table,
  53          * when the commit has more than 2 parents.
  54          */
  55         const unsigned char *extra_edge_list;
  56         /* The number of entries in the Extra Edge List table. Each entry is 4 bytes wide. */
  57         size_t num_extra_edge_list;
  58
  59         /* The trailer of the file. Contains the SHA1-checksum of the whole file. */
  60         unsigned char checksum[GIT_HASH_SHA1_SIZE];
  61 } git_commit_graph_file;
  62
  63 /**
  64  * An entry in the commit-graph file. Provides a subset of the information that
  65  * can be obtained from the commit header.
  66  */
  67 typedef struct git_commit_graph_entry {
  68         /* The generation number of the commit within the graph */
  69         size_t generation;
  70
  71         /* Time in seconds from UNIX epoch. */
  72         git_time_t commit_time;
  73
  74         /* The number of parents of the commit. */
  75         size_t parent_count;
  76
  77         /*
  78          * The indices of the parent commits within the Commit Data table. The value
  79          * of `GIT_COMMIT_GRAPH_MISSING_PARENT` indicates that no parent is in that
  80          * position.
  81          */
  82         size_t parent_indices[2];
  83
  84         /* The index within the Extra Edge List of any parent after the first two. */
  85         size_t extra_parents_index;
  86
  87         /* The SHA-1 hash of the root tree of the commit. */
  88         git_oid tree_oid;
  89
  90         /* The SHA-1 hash of the requested commit. */
  91         git_oid sha1;
  92 } git_commit_graph_entry;
  93
  94 /* A wrapper for git_commit_graph_file to enable lazy loading in the ODB. */
  95 struct git_commit_graph {
  96         /* The path to the commit-graph file. Something like ".git/objects/info/commit-graph". */
  97         git_str filename;
  98
  99         /* The underlying commit-graph file. */
 100         git_commit_graph_file *file;
 101
 102         /* Whether the commit-graph file was already checked for validity. */
 103         bool checked;
 104 };
 105
 106 /** Create a new commit-graph, optionally opening the underlying file. */
 107 int git_commit_graph_new(git_commit_graph **cgraph_out, const char *objects_dir, bool open_file);
 108
 109 /** Open and validate a commit-graph file. */
 110 int git_commit_graph_file_open(git_commit_graph_file **file_out, const char *path);
 111
 112 /*
 113  * Attempt to get the git_commit_graph's commit-graph file. This object is
 114  * still owned by the git_commit_graph. If the repository does not contain a commit graph,
 115  * it will return GIT_ENOTFOUND.
 116  *
 117  * This function is not thread-safe.
 118  */
 119 int git_commit_graph_get_file(git_commit_graph_file **file_out, git_commit_graph *cgraph);
 120
 121 /* Marks the commit-graph file as needing a refresh. */
 122 void git_commit_graph_refresh(git_commit_graph *cgraph);
 123
 124 /*
 125  * A writer for `commit-graph` files.
 126  */
 127 struct git_commit_graph_writer {
 128         /*
 129          * The path of the `objects/info` directory where the `commit-graph` will be
 130          * stored.
 131          */
 132         git_str objects_info_dir;
 133
 134         /* The list of packed commits. */
 135         git_vector commits;
 136 };
 137
 138 int git_commit_graph__writer_dump(
 139         git_str *cgraph,
 140         git_commit_graph_writer *w,
 141         git_commit_graph_writer_options *opts);
 142
 143 /*
 144  * Returns whether the git_commit_graph_file needs to be reloaded since the
 145  * contents of the commit-graph file have changed on disk.
 146  */
 147 bool git_commit_graph_file_needs_refresh(
 148                 const git_commit_graph_file *file, const char *path);
 149
 150 int git_commit_graph_entry_find(
 151                 git_commit_graph_entry *e,
 152                 const git_commit_graph_file *file,
 153                 const git_oid *short_oid,
 154                 size_t len);
 155 int git_commit_graph_entry_parent(
 156                 git_commit_graph_entry *parent,
 157                 const git_commit_graph_file *file,
 158                 const git_commit_graph_entry *entry,
 159                 size_t n);
 160 int git_commit_graph_file_close(git_commit_graph_file *cgraph);
 161 void git_commit_graph_file_free(git_commit_graph_file *cgraph);
 162
 163 /* This is exposed for use in the fuzzers. */
 164 int git_commit_graph_file_parse(
 165                 git_commit_graph_file *file,
 166                 const unsigned char *data,
 167                 size_t size);
 168
 169 #endif