1. Decompressing and parsing commits.
2. Walking the entire graph to satisfy topological order constraints.
-The commit graph file is a supplemental data structure that accelerates
+The commit-graph file is a supplemental data structure that accelerates
commit graph walks. If a user downgrades or disables the 'core.commitGraph'
config setting, then the existing ODB is sufficient. The file is stored
as "commit-graph" either in the .git/objects/info directory or in the info
directory of an alternate.
-The commit graph file stores the commit graph structure along with some
+The commit-graph file stores the commit graph structure along with some
extra metadata to speed up graph walks. By listing commit OIDs in lexi-
cographic order, we can identify an integer position for each commit and
refer to the parents of a commit using those integer positions. We use
Design Details
--------------
-- The commit graph file is stored in a file named 'commit-graph' in the
+- The commit-graph file is stored in a file named 'commit-graph' in the
.git/objects/info directory. This could be stored in the info directory
of an alternate.
- The file format includes parameters for the object ID hash function,
so a future change of hash algorithm does not require a change in format.
-Future Work
------------
-
-- The commit graph feature currently does not honor commit grafts. This can
- be remedied by duplicating or refactoring the current graft logic.
-
-- After computing and storing generation numbers, we must make graph
- 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
- operations are important candidates:
-
- - 'log --topo-order'
- - 'tag --merged'
-
-- A server could provide a commit graph file as part of the network protocol
- to avoid extra calculations by clients. This feature is only of benefit if
- the user is willing to trust the file, because verifying the file is correct
- is as hard as computing it from scratch.
+- Commit grafts and replace objects can change the shape of the commit
+ history. The latter can also be enabled/disabled on the fly using
+ `--no-replace-objects`. This leads to difficultly storing both possible
+ interpretations of a commit id, especially when computing generation
+ numbers. The commit-graph will not be read or written when
+ replace-objects or grafts are present.
+
+- Shallow clones create grafts of commits by dropping their parents. This
+ leads the commit-graph to think those commits have generation number 1.
+ If and when those commits are made unshallow, those generation numbers
+ become invalid. Since shallow clones are intended to restrict the commit
+ history to a very small set of commits, the commit-graph feature is less
+ helpful for these clones, anyway. The commit-graph will not be read or
+ written when shallow commits are present.
+
+Commit Graphs Chains
+--------------------
+
+Typically, repos grow with near-constant velocity (commits per day). Over time,
+the number of commits added by a fetch operation is much smaller than the
+number of commits in the full history. By creating a "chain" of commit-graphs,
+we enable fast writes of new commit data without rewriting the entire commit
+history -- at least, most of the time.
+
+## File Layout
+
+A commit-graph chain uses multiple files, and we use a fixed naming convention
+to organize these files. Each commit-graph file has a name
+`$OBJDIR/info/commit-graphs/graph-{hash}.graph` where `{hash}` is the hex-
+valued hash stored in the footer of that file (which is a hash of the file's
+contents before that hash). For a chain of commit-graph files, a plain-text
+file at `$OBJDIR/info/commit-graphs/commit-graph-chain` contains the
+hashes for the files in order from "lowest" to "highest".
+
+For example, if the `commit-graph-chain` file contains the lines
+
+```
+ {hash0}
+ {hash1}
+ {hash2}
+```
+
+then the commit-graph chain looks like the following diagram:
+
+ +-----------------------+
+ | graph-{hash2}.graph |
+ +-----------------------+
+ |
+ +-----------------------+
+ | |
+ | graph-{hash1}.graph |
+ | |
+ +-----------------------+
+ |
+ +-----------------------+
+ | |
+ | |
+ | |
+ | graph-{hash0}.graph |
+ | |
+ | |
+ | |
+ +-----------------------+
+
+Let X0 be the number of commits in `graph-{hash0}.graph`, X1 be the number of
+commits in `graph-{hash1}.graph`, and X2 be the number of commits in
+`graph-{hash2}.graph`. If a commit appears in position i in `graph-{hash2}.graph`,
+then we interpret this as being the commit in position (X0 + X1 + i), and that
+will be used as its "graph position". The commits in `graph-{hash2}.graph` use these
+positions to refer to their parents, which may be in `graph-{hash1}.graph` or
+`graph-{hash0}.graph`. We can navigate to an arbitrary commit in position j by checking
+its containment in the intervals [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1 +
+X2).
Related Links
-------------