chore(3p/git): Unvendor git and track patches instead r/2903

This was vendored a long time ago under the expectation that keeping
it in sync with cgit would be easier this way, but it has proven not
to be a big issue.

On the other hand, a vendored copy of git is an annoying maintenance
burden. It is much easier to rebase the single (dottime) patch that we
have.

This removes the vendored copy of git and instead passes the git
source code to cgit via `pkgs.srcOnly`, which includes the applied
patch so that cgit can continue rendering dottime.

Change-Id: If31f62dea7ce688fd1b9050204e9378019775f2b

1 files changed, 0 insertions, 350 deletions

diff --git a/third_party/git/Documentation/technical/commit-graph.txt b/third_party/git/Documentation/technical/commit-graph.txt
deleted file mode 100644
index f14a7659aa87..000000000000
--- a/third_party/git/Documentation/technical/commit-graph.txt
+++ /dev/null
@@ -1,350 +0,0 @@
-Git Commit Graph Design Notes
-=============================
-
-Git walks the commit graph for many reasons, including:
-
-1. Listing and filtering commit history.
-2. Computing merge bases.
-
-These operations can become slow as the commit count grows. The merge
-base calculation shows up in many user-facing commands, such as 'merge-base'
-or 'status' and can take minutes to compute depending on history shape.
-
-There are two main costs here:
-
-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
-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
-extra metadata to speed up graph walks. By listing commit OIDs in
-lexicographic order, we can identify an integer position for each commit
-and refer to the parents of a commit using those integer positions. We
-use binary search to find initial commits and then use the integer
-positions for fast lookups during the walk.
-
-A consumer may load the following info for a commit from the graph:
-
-1. The commit OID.
-2. The list of parents, along with their integer position.
-3. The commit date.
-4. The root tree OID.
-5. The generation number (see definition below).
-
-Values 1-4 satisfy the requirements of parse_commit_gently().
-
-Define the "generation number" of a commit recursively as follows:
-
- * A commit with no parents (a root commit) has generation number one.
-
- * A commit with at least one parent has generation number one more than
-   the largest generation number among its parents.
-
-Equivalently, the generation number of a commit A is one more than the
-length of a longest path from A to a root commit. The recursive definition
-is easier to use for computation and observing the following property:
-
-    If A and B are commits with generation numbers N and M, respectively,
-    and N <= M, then A cannot reach B. That is, we know without searching
-    that B is not an ancestor of A because it is further from a root commit
-    than A.
-
-    Conversely, when checking if A is an ancestor of B, then we only need
-    to walk commits until all commits on the walk boundary have generation
-    number at most N. If we walk commits using a priority queue seeded by
-    generation numbers, then we always expand the boundary commit with highest
-    generation number and can easily detect the stopping condition.
-
-This property can be used to significantly reduce the time it takes to
-walk commits and determine topological relationships. Without generation
-numbers, the general heuristic is the following:
-
-    If A and B are commits with commit time X and Y, respectively, and
-    X < Y, then A _probably_ cannot reach B.
-
-This heuristic is currently used whenever the computation is allowed to
-violate topological relationships due to clock skew (such as "git log"
-with default order), but is not used when the topological order is
-required (such as merge base calculations, "git log --graph").
-
-In practice, we expect some commits to be created recently and not stored
-in the commit graph. We can treat these commits as having "infinite"
-generation number and walk until reaching commits with known generation
-number.
-
-We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not
-in the commit-graph file. If a commit-graph file was written by a version
-of Git that did not compute generation numbers, then those commits will
-have generation number represented by the macro GENERATION_NUMBER_ZERO = 0.
-
-Since the commit-graph file is closed under reachability, we can guarantee
-the following weaker condition on all commits:
-
-    If A and B are commits with generation numbers N and M, respectively,
-    and N < M, then A cannot reach B.
-
-Note how the strict inequality differs from the inequality when we have
-fully-computed generation numbers. Using strict inequality may result in
-walking a few extra commits, but the simplicity in dealing with commits
-with generation number *_INFINITY or *_ZERO is valuable.
-
-We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose
-generation numbers are computed to be at least this value. We limit at
-this value since it is the largest value that can be stored in the
-commit-graph file using the 30 bits available to generation numbers. This
-presents another case where a commit can have generation number equal to
-that of a parent.
-
-Design Details
---------------
-
-- 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 core.commitGraph config setting must be on to consume graph files.
-
-- 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.
-
-- 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).
-
-Each commit-graph file (except the base, `graph-{hash0}.graph`) contains data
-specifying the hashes of all files in the lower layers. In the above example,
-`graph-{hash1}.graph` contains `{hash0}` while `graph-{hash2}.graph` contains
-`{hash0}` and `{hash1}`.
-
-## Merging commit-graph files
-
-If we only added a new commit-graph file on every write, we would run into a
-linear search problem through many commit-graph files.  Instead, we use a merge
-strategy to decide when the stack should collapse some number of levels.
-
-The diagram below shows such a collapse. As a set of new commits are added, it
-is determined by the merge strategy that the files should collapse to
-`graph-{hash1}`. Thus, the new commits, the commits in `graph-{hash2}` and
-the commits in `graph-{hash1}` should be combined into a new `graph-{hash3}`
-file.
-
-			    +---------------------+
-			    |                     |
-			    |    (new commits)    |
-			    |                     |
-			    +---------------------+
-			    |                     |
- +-----------------------+  +---------------------+
- |  graph-{hash2}        |->|                     |
- +-----------------------+  +---------------------+
-	  |                 |                     |
- +-----------------------+  +---------------------+
- |                       |  |                     |
- |  graph-{hash1}        |->|                     |
- |                       |  |                     |
- +-----------------------+  +---------------------+
-	  |                  tmp_graphXXX
- +-----------------------+
- |                       |
- |                       |
- |                       |
- |  graph-{hash0}        |
- |                       |
- |                       |
- |                       |
- +-----------------------+
-
-During this process, the commits to write are combined, sorted and we write the
-contents to a temporary file, all while holding a `commit-graph-chain.lock`
-lock-file.  When the file is flushed, we rename it to `graph-{hash3}`
-according to the computed `{hash3}`. Finally, we write the new chain data to
-`commit-graph-chain.lock`:
-
-```
-	{hash3}
-	{hash0}
-```
-
-We then close the lock-file.
-
-## Merge Strategy
-
-When writing a set of commits that do not exist in the commit-graph stack of
-height N, we default to creating a new file at level N + 1. We then decide to
-merge with the Nth level if one of two conditions hold:
-
-  1. `--size-multiple=<X>` is specified or X = 2, and the number of commits in
-     level N is less than X times the number of commits in level N + 1.
-
-  2. `--max-commits=<C>` is specified with non-zero C and the number of commits
-     in level N + 1 is more than C commits.
-
-This decision cascades down the levels: when we merge a level we create a new
-set of commits that then compares to the next level.
-
-The first condition bounds the number of levels to be logarithmic in the total
-number of commits.  The second condition bounds the total number of commits in
-a `graph-{hashN}` file and not in the `commit-graph` file, preventing
-significant performance issues when the stack merges and another process only
-partially reads the previous stack.
-
-The merge strategy values (2 for the size multiple, 64,000 for the maximum
-number of commits) could be extracted into config settings for full
-flexibility.
-
-## Deleting graph-{hash} files
-
-After a new tip file is written, some `graph-{hash}` files may no longer
-be part of a chain. It is important to remove these files from disk, eventually.
-The main reason to delay removal is that another process could read the
-`commit-graph-chain` file before it is rewritten, but then look for the
-`graph-{hash}` files after they are deleted.
-
-To allow holding old split commit-graphs for a while after they are unreferenced,
-we update the modified times of the files when they become unreferenced. Then,
-we scan the `$OBJDIR/info/commit-graphs/` directory for `graph-{hash}`
-files whose modified times are older than a given expiry window. This window
-defaults to zero, but can be changed using command-line arguments or a config
-setting.
-
-## Chains across multiple object directories
-
-In a repo with alternates, we look for the `commit-graph-chain` file starting
-in the local object directory and then in each alternate. The first file that
-exists defines our chain. As we look for the `graph-{hash}` files for
-each `{hash}` in the chain file, we follow the same pattern for the host
-directories.
-
-This allows commit-graphs to be split across multiple forks in a fork network.
-The typical case is a large "base" repo with many smaller forks.
-
-As the base repo advances, it will likely update and merge its commit-graph
-chain more frequently than the forks. If a fork updates their commit-graph after
-the base repo, then it should "reparent" the commit-graph chain onto the new
-chain in the base repo. When reading each `graph-{hash}` file, we track
-the object directory containing it. During a write of a new commit-graph file,
-we check for any changes in the source object directory and read the
-`commit-graph-chain` file for that source and create a new file based on those
-files. During this "reparent" operation, we necessarily need to collapse all
-levels in the fork, as all of the files are invalid against the new base file.
-
-It is crucial to be careful when cleaning up "unreferenced" `graph-{hash}.graph`
-files in this scenario. It falls to the user to define the proper settings for
-their custom environment:
-
- 1. When merging levels in the base repo, the unreferenced files may still be
-    referenced by chains from fork repos.
-
- 2. The expiry time should be set to a length of time such that every fork has
-    time to recompute their commit-graph chain to "reparent" onto the new base
-    file(s).
-
- 3. If the commit-graph chain is updated in the base, the fork will not have
-    access to the new chain until its chain is updated to reference those files.
-    (This may change in the future [5].)
-
-Related Links
--------------
-[0] https://bugs.chromium.org/p/git/issues/detail?id=8
-    Chromium work item for: Serialized Commit Graph
-
-[1] https://lore.kernel.org/git/20110713070517.GC18566@sigill.intra.peff.net/
-    An abandoned patch that introduced generation numbers.
-
-[2] https://lore.kernel.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
-    Discussion about generation numbers on commits and how they interact
-    with fsck.
-
-[3] https://lore.kernel.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/
-    More discussion about generation numbers and not storing them inside
-    commit objects. A valuable quote:
-
-    "I think we should be moving more in the direction of keeping
-     repo-local caches for optimizations. Reachability bitmaps have been
-     a big performance win. I think we should be doing the same with our
-     properties of commits. Not just generation numbers, but making it
-     cheap to access the graph structure without zlib-inflating whole
-     commit objects (i.e., packv4 or something like the "metapacks" I
-     proposed a few years ago)."
-
-[4] https://lore.kernel.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
-    A patch to remove the ahead-behind calculation from 'status'.
-
-[5] https://lore.kernel.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/
-    A discussion of a "two-dimensional graph position" that can allow reading
-    multiple commit-graph chains at the same time.