In anticipation of making trees load lazily, create a Coccinelle
script (contrib/coccinelle/commit.cocci) to ensure that all
references to the 'maybe_tree' member of struct commit are either
mutations or accesses through get_commit_tree() or
get_commit_tree_oid().

Apply the Coccinelle script to create the rest of the patch.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

While walking the commit graph, we load struct commit objects into
the object cache. During this process, we also load struct tree
objects for the root tree of each of these commits. We load these
objects even if we are only computing commit reachability information,
such as a merge base or ahead/behind information.

Create get_commit_tree() as a first step to removing direct
references to the 'maybe_tree' member of struct commit.

Create get_commit_tree_oid() as a shortcut for several references
to "&commit->maybe_tree->object.oid" in the codebase.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Using the commit-graph file to walk commit history removes the large
cost of parsing commits during the walk. This exposes a performance
issue: lookup_tree() takes a large portion of the computation time,
even when Git never uses those trees.

In anticipation of lazy-loading these trees, rename the 'tree' member
of struct commit to 'maybe_tree'. This serves two purposes: it hints
at the future role of possibly being NULL even if the commit has a
valid tree, and it allows for unambiguous transformation from simple
member access (i.e. commit->maybe_tree) to method access.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

* bw/c-plus-plus: (37 commits)
  replace: rename 'new' variables
  trailer: rename 'template' variables
  tempfile: rename 'template' variables
  wrapper: rename 'template' variables
  environment: rename 'namespace' variables
  diff: rename 'template' variables
  environment: rename 'template' variables
  init-db: rename 'template' variables
  unpack-trees: rename 'new' variables
  trailer: rename 'new' variables
  submodule: rename 'new' variables
  split-index: rename 'new' variables
  remote: rename 'new' variables
  ref-filter: rename 'new' variables
  read-cache: rename 'new' variables
  line-log: rename 'new' variables
  imap-send: rename 'new' variables
  http: rename 'new' variables
  entry: rename 'new' variables
  diffcore-delta: rename 'new' variables
  ...

Teach git-commit-graph to add all commits from the existing
commit-graph file to the file about to be written. This should be
used when adding new commits without performing garbage collection.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach git-commit-graph to read commits from stdin when the
--stdin-commits flag is specified. Commits reachable from these
commits are added to the graph. This is a much faster way to construct
the graph than inspecting all packed objects, but is restricted to
known tips.

For the Linux repository, 700,000+ commits were added to the graph
file starting from 'master' in 7-9 seconds, depending on the number
of packfiles in the repo (1, 24, or 120).
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach git-commit-graph to inspect the objects only in a certain list
of pack-indexes within the given pack directory. This allows updating
the commit graph iteratively.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach Git to inspect a commit graph file to supply the contents of a
struct commit when calling parse_commit_gently(). This implementation
satisfies all post-conditions on the struct commit, including loading
parents, the root tree, and the commit date.

If core.commitGraph is false, then do not check graph files.

In test script t5318-commit-graph.sh, add output-matching conditions on
read-only graph operations.

By loading commits from the graph instead of parsing commit buffers, we
save a lot of time on long commit walks. Here are some performance
results for a copy of the Linux repository where 'master' has 678,653
reachable commits and is behind 'origin/master' by 59,929 commits.

| Command                          | Before | After  | Rel % |
|----------------------------------|--------|--------|-------|
| log --oneline --topo-order -1000 |  8.31s |  0.94s | -88%  |
| branch -vv                       |  1.02s |  0.14s | -86%  |
| rev-list --all                   |  5.89s |  1.07s | -81%  |
| rev-list --all --objects         | 66.15s | 58.45s | -11%  |
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach write_commit_graph() to walk all parents from the commits
discovered in packfiles. This prevents gaps given by loose objects or
previously-missed packfiles.

Also automatically add commits from the existing graph file, if it
exists.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The commit graph feature is controlled by the new core.commitGraph config
setting. This defaults to 0, so the feature is opt-in.

The intention of core.commitGraph is that a user can always stop checking
for or parsing commit graph files if core.commitGraph=0.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach git-commit-graph to read commit graph files and summarize their contents.

Use the read subcommand to verify the contents of a commit graph file in the
tests.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach git-commit-graph to write graph files. Create new test script to verify
this command succeeds without failure.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach Git to write a commit graph file by checking all packed objects
to see if they are commits, then store the file in the given object
directory.
Helped-by: NJeff King <peff@peff.net>
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Teach git the 'commit-graph' builtin that will be used for writing and
reading packed graph files. The current implementation is mostly
empty, except for an '--object-dir' option.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add Documentation/technical/commit-graph.txt with details of the planned
commit graph feature, including future plans.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add document specifying the binary format for commit graphs. This
format allows for:

* New versions.
* New hash functions and hash lengths.
* Optional extensions.

Basic header information is followed by a binary table of contents
into "chunks" that include:

* An ordered list of commit object IDs.
* A 256-entry fanout into that list of OIDs.
* A list of metadata for the commits.
* A list of "large edges" to enable octopus merges.

The format automatically includes two parent positions for every
commit. This favors speed over space, since using only one position
per commit would cause an extra level of indirection for every merge
commit. (Octopus merges suffer from this indirection, but they are
very rare.)
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

If we want to use a hashfile on the temporary file for a lockfile, then
we need finalize_hashfile() to fully write the trailing hash but also keep
the file descriptor open.

Do this by adding a new CSUM_HASH_IN_STREAM flag along with a functional
change that checks this flag before writing the checksum to the stream.
This differs from previous behavior since it would be written if either
CSUM_CLOSE or CSUM_FSYNC is provided.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The hashclose() method behaves very differently depending on the flags
parameter. In particular, the file descriptor is not always closed.

Perform a simple rename of "hashclose()" to "finalize_hashfile()" in
preparation for functional changes.
Signed-off-by: NDerrick Stolee <dstolee@microsoft.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

* jk/cached-commit-buffer:
  revision: drop --show-all option
  commit: drop uses of get_cached_commit_buffer()
  Git 2.16.2

* jt/binsearch-with-fanout:
  packfile: refactor hash search with fanout table
  packfile: remove GIT_DEBUG_LOOKUP log statements

This was an undocumented debugging aid that does not seem to
have come in handy in the past decade, judging from its lack
of mentions on the mailing list.

Let's drop it in the name of simplicity. This is morally a
revert of 3131b713 (Add "--show-all" revision walker flag
for debugging, 2008-02-09), but note that I did leave in the
mapping of UNINTERESTING to "^" in get_revision_mark(). I
don't think this would be possible to trigger with the
current code, but it's the only sensible marker.

We'll skip the usual deprecation period because this was
explicitly a debugging aid that was never documented.
Signed-off-by: NJeff King <peff@peff.net>
Acked-by: NLinus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The "--show-all" revision option shows UNINTERESTING
commits. Some of these commits may be unparsed when we try
to show them (since we may or may not need to walk their
parents to fulfill the request).

Commit 3131b713 (Add "--show-all" revision walker flag for
debugging, 2008-02-09) resolved this by just skipping
pretty-printing for commits without their object contents
cached, saying:

  Because we now end up listing commits we may not even have been parsed
  at all "show_log" and "show_commit" need to protect against commits
  that don't have a commit buffer entry.

That was the easy fix to avoid the pretty-printer segfaulting,
but:

  1. It doesn't work for all formats. E.g., --oneline
     prints the oid for each such commit but not a trailing
     newline, leading to jumbled output.

  2. It only affects some commits, depending on whether we
     happened to parse them or not (so if they were at the
     tip of an UNINTERESTING starting point, or if we
     happened to traverse over them, you'd see more data).

  3. It unncessarily ties the decision to show the verbose
     header to whether the commit buffer was cached. That
     makes it harder to change the logic around caching
     (e.g., if we could traverse without actually loading
     the full commit objects).

These days it's safe to feed such a commit to the
pretty-print code. Since be5c9fb9 (logmsg_reencode: lazily
load missing commit buffers, 2013-01-26), we'll load it on
demand in such a case. So let's just always show the verbose
headers.

This does change the behavior of plumbing, but:

  a. The --show-all option was explicitly introduced as a
     debugging aid, and was never documented (and has rarely
     even been mentioned on the list by git devs).

  b. Avoiding the commits was already not deterministic due
     to (2) above. So the caller might have seen full
     headers for these commits anyway, and would need to be
     prepared for it.
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Rename C++ keyword in order to bring the codebase closer to being able
to be compiled with a C++ compiler.
Signed-off-by: NBrandon Williams <bmwill@google.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>