delta-islands: convert island_marks khash to use oids

All of the users of this map have an actual "struct object_id" rather
than a bare sha1. Let's use the more descriptive type (and get one step
closer to dropping khash_sha1 entirely).

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

khash: rename kh_oid_t to kh_oid_set

khash lets us define a hash as either a map or a set (i.e., with no
"value" type). For the oid maps we define, "oid" is the set and
"oid_map" is the map. As the bug in the previous commit shows, it's easy
to pick the wrong one.

So let's make the names more distinct: "oid_set" and "oid_map".

An alternative naming scheme would be to actually name the type after
the key/value types. So e.g., "oid" _would_ be the set, since it has no
value type. And "oid_map" would become "oid_void" or similar (and
"oid_pos" becomes "oid_int"). That's better in some ways: it's more
regular, and a given map type can be more reasily reused in multiple
contexts (e.g., something storing an "int" that isn't a "pos"). But it's
also slightly less descriptive.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

khash: drop broken oid_map typedef

Commit 5a8643eff1 (khash: move oid hash table definition, 2019-02-19)
added a khash "oid_map" type to match the existing "oid" type, which is
a simple set (i.e., just keys, no values). But in setting up the
khash_oid_map typedef, it accidentally referred to "kh_oid_t", which is
the set type.

Nobody noticed the breakage because there are not yet any callers; the
type was added just as a match to the existing sha1 types (whose map
type confusingly _is_ called khash_sha1, and it has no matching set
type).

We could easily fix this with s/oid/oid_map/ in the typedef. But let's
take this a step further, and just drop the typedef entirely.  These
typedefs were added by 5a8643eff1 to match the khash_sha1 typedefs. But
the actual khash-derived type names are descriptive enough; this is just
adding an extra layer of indirection. The khash names do not quite
follow our usual style (e.g., they end in "_t"), but since we end up
using other khash names (e.g., khiter_t, kh_get_oid()) anyway, just
typedef-ing the struct name is not really helping much.

And there are already many cases where we use the raw khash type names
anyway (e.g., the "set" variant defined just above us does not have such
a typedef!).

So let's drop this typedef, and the matching oid_pos one (which actually
_does_ have a user, but we can easily convert it).

We'll leave the khash_sha1 typedef around. The ultimate fate of its
callers should be conversion to kh_oid_map_t, so there's no point in
going through the noise of changing the names now.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

object: convert create_object() to use object_id

There are no callers left of create_object() that aren't just passing us
the "hash" member of a "struct object_id". Let's take the whole struct,
which gets us closer to removing all raw sha1 variables.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

object: convert internal hash_obj() to object_id

Now that lookup_object() has an object_id, we can consistently pass that
around instead of a raw sha1. We still convert to a hash to pass to
sha1hash(), but the goal is for that to go away shortly.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

object: convert lookup_object() to use object_id

There are no callers left of lookup_object() that aren't just passing us
the "hash" member of a "struct object_id". Let's take the whole struct,
which gets us closer to removing all raw sha1 variables.  It also
matches the existing conversions of lookup_blob(), etc.

The conversions of callers were done by hand, but they're all mechanical
one-liners.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

object: convert lookup_unknown_object() to use object_id

There are no callers left of lookup_unknown_object() that aren't just
passing us the "hash" member of a "struct object_id". Let's take the
whole struct, which gets us closer to removing all raw sha1 variables.
It also matches the existing conversions of lookup_blob(), etc.

The conversions of callers were done by hand, but they're all mechanical
one-liners.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

pack-objects: convert locate_object_entry_hash() to object_id

There are no callers of locate_object_entry_hash() that aren't just
passing us the "hash" member of a "struct object_id". Let's take the
whole struct, which gets us closer to removing all raw sha1 variables.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

pack-objects: convert packlist_find() to use object_id

We take a raw hash pointer, but most of our callers have a "struct
object_id" already. Let's switch to taking the full struct, which will
let us continue removing uses of raw sha1 buffers.

There are two callers that do need special attention:

  - in rebuild_existing_bitmaps(), we need to switch to
    nth_packed_object_oid(). This incurs an extra hash copy over
    pointing straight to the mmap'd sha1, but it shouldn't be measurable
    compared to the rest of the operation.

  - in can_reuse_delta() we already spent the effort to copy the sha1
    into a "struct object_id", but now we just have to do so a little
    earlier in the function (we can't easily convert that function's
    callers because they may be pointing at mmap'd REF_DELTA blocks).

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

pack-bitmap-write: convert some helpers to use object_id

A few functions take raw hash pointers, but all of their callers
actually have a "struct object_id". Let's retain that extra type as long
as possible (which will let future patches extend that further, and so
on).

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

upload-pack: rename a "sha1" variable to "oid"

This variable is a "struct object_id", but uses the old-style name
"sha1". Let's call it oid to match more modern code (and make it clear
that it can handle any algorithm, since it uses parse_oid_hex()
properly).

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

describe: fix accidental oid/hash type-punning

The find_commit_name() function passes an object_id.hash as the key of a
hashmap. That ends up in commit_name_neq(), which then feeds it to
oideq(). Which means we should actually be the whole "struct object_id".

It works anyway because pointers to the two are interchangeable. And
because we're going through a layer of void pointers, the compiler
doesn't notice the type mismatch.

But it's worth cleaning up (especially since once we switch away from
sha1hash() on the same line, accessing the hash member will look doubly
out of place).

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

fetch: only run 'gc' once when fetching multiple remotes

In multiple remotes mode, git-fetch is launched for n-1 remotes and the
last remote is handled by the current process. Each of these processes
will in turn run 'gc' at the end.

This is not really a problem because even if multiple 'gc --auto' is run
at the same time we still handle it correctly. It does show multiple
"auto packing in the background" messages though. And we may waste some
resources when gc actually runs because we still do some stuff before
checking the lock and moving it to background.

So let's try to avoid that. We should only need one 'gc' run after all
objects and references are added anyway. Add a new option --no-auto-gc
that will be used by those n-1 processes. 'gc --auto' will always run on
the main fetch process (*).

(*) even if we fetch remotes in parallel at some point in future, this
    should still be fine because we should "join" all those processes
    before this step.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
Acked-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: test verify across alternates

The 'git commit-graph verify' subcommand loads a commit-graph from
a given object directory instead of using the standard method
prepare_commit_graph(). During development of load_commit_graph_chain(),
a version did not include prepare_alt_odb() as it was previously
run by prepare_commit_graph() in most cases.

Add a test that prevents that mistake from happening again.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: normalize commit-graph filenames

When writing commit-graph files, we append path data to an
object directory, which may be specified by the user via the
'--object-dir' option. If the user supplies a trailing slash,
or some other alternative path format, the resulting path may
be usable for writing to the correct location. However, when
expiring graph files from the <obj-dir>/info/commit-graphs
directory during a write, we need to compare paths with exact
string matches.

Normalize the commit-graph filenames to avoid ambiguity. This
creates extra allocations, but this is a constant multiple of
the number of commit-graph files, which should be a number in
the single digits.

Further normalize the object directory in the context. Due to
a comparison between g->obj_dir and ctx->obj_dir in
split_graph_merge_strategy(), a trailing slash would prevent
any merging of layers within the same object directory. The
check is there to ensure we do not merge across alternates.
Update the tests to include a case with this trailing slash
problem.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: merge commit-graph chains

When searching for a commit in a commit-graph chain of G graphs with N
commits, the search takes O(G log N) time. If we always add a new tip
graph with every write, the linear G term will start to dominate and
slow the lookup process.

To keep lookups fast, but also keep most incremental writes fast, create
a strategy for merging levels of the commit-graph chain. The strategy is
detailed in the commit-graph design document, but is summarized by these
two conditions:

  1. If the number of commits we are adding is more than half the number
     of commits in the graph below, then merge with that graph.

  2. If we are writing more than 64,000 commits into a single graph,
     then merge with all lower graphs.

The numeric values in the conditions above are currently constant, but
can become config options in a future update.

As we merge levels of the commit-graph chain, check that the commits
still exist in the repository. A garbage-collection operation may have
removed those commits from the object store and we do not want to
persist them in the commit-graph chain. This is a non-issue if the
'git gc' process wrote a new, single-level commit-graph file.

After we merge levels, the old graph-{hash}.graph files are no longer
referenced by the commit-graph-chain file. We will expire these files in
a future change.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: test --split across alternate without --split

We allow sharing commit-graph files across alternates. When we are
writing a split commit-graph, we allow adding tip graph files that
are not in the alternate, but include commits from our local repo.

However, if our alternate is not using the split commit-graph format,
its file is at .git/objects/info/commit-graph and we are trying to
write files in .git/objects/info/commit-graphs/graph-{hash}.graph.

We already have logic to ensure we do not merge across alternate
boundaries, but we also cannot have a commit-graph chain to our
alternate if uses the old filename structure.

Create a test that verifies we create a new split commit-graph
with only one level and we do not modify the existing commit-graph
in the alternate.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: add --split option to builtin

Add a new "--split" option to the 'git commit-graph write' subcommand. This
option allows the optional behavior of writing a commit-graph chain.

The current behavior will add a tip commit-graph containing any commits that
are not in the existing commit-graph or commit-graph chain. Later changes
will allow merging the chain and expiring out-dated files.

Add a new test script (t5324-split-commit-graph.sh) that demonstrates this
behavior.

Helped-by: Johannes Schindelin <redacted>
Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: test octopus merges with --split

Octopus merges require an extra chunk of data in the commit-graph
file format. Create a test that ensures the new --split option
continues to work with an octopus merge. Specifically, ensure
that the octopus merge has parents across layers to truly check
that our graph position logic holds up correctly.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: write commit-graph chains

Extend write_commit_graph() to write a commit-graph chain when given the
COMMIT_GRAPH_SPLIT flag.

This implementation is purposefully simplistic in how it creates a new
chain. The commits not already in the chain are added to a new tip
commit-graph file.

Much of the logic around writing a graph-{hash}.graph file and updating
the commit-graph-chain file is the same as the commit-graph file case.
However, there are several places where we need to do some extra logic
in the split case.

Track the list of graph filenames before and after the planned write.
This will be more important when we start merging graph files, but it
also allows us to upgrade our commit-graph file to the appropriate
graph-{hash}.graph file when we upgrade to a chain of commit-graphs.

Note that we use the eighth byte of the commit-graph header to store the
number of base graph files. This determines the length of the base
graphs chunk.

A subtle change of behavior with the new logic is that we do not write a
commit-graph if we our commit list is empty. This extends to the typical
case, which is reflected in t5318-commit-graph.sh.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: clean up chains after flattened write

If we write a commit-graph file without the split option, then
we write to $OBJDIR/info/commit-graph and start to ignore
the chains in $OBJDIR/info/commit-graphs/.

Unlink the commit-graph-chain file and expire the graph-{hash}.graph
files in $OBJDIR/info/commit-graphs/ during every write.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: rearrange chunk count logic

The number of chunks in a commit-graph file can change depending on
whether we need the Extra Edges Chunk. We are going to add more optional
chunks, and it will be helpful to rearrange this logic around the chunk
count before doing so.

Specifically, we need to finalize the number of chunks before writing
the commit-graph header. Further, we also need to fill out the chunk
lookup table dynamically and using "num_chunks" as we add optional
chunks is useful for adding optional chunks in the future.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: verify chains with --shallow mode

If we wrote a commit-graph chain, we only modified the tip file in
the chain. It is valuable to verify what we wrote, but not waste
time checking files we did not write.

Add a '--shallow' option to the 'git commit-graph verify' subcommand
and check that it does not read the base graph in a two-file chain.

Making the verify subcommand read from a chain of commit-graphs takes
some rearranging of the builtin code.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: add base graphs chunk

To quickly verify a commit-graph chain is valid on load, we will
read from the new "Base Graphs Chunk" of each file in the chain.
This will prevent accidentally loading incorrect data from manually
editing the commit-graph-chain file or renaming graph-{hash}.graph
files.

The commit_graph struct already had an object_id struct "oid", but
it was never initialized or used. Add a line to read the hash from
the end of the commit-graph file and into the oid member.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: create options for split files

The split commit-graph feature is now fully implemented, but needs
some more run-time configurability. Allow direct callers to 'git
commit-graph write --split' to specify the values used in the
merge strategy and the expire time.

Update the documentation to specify these values.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: load commit-graph chains

Prepare the logic for reading a chain of commit-graphs.

First, look for a file at $OBJDIR/info/commit-graph. If it exists,
then use that file and stop.

Next, look for the chain file at $OBJDIR/info/commit-graphs/commit-graph-chain.
If this file exists, then load the hash values as line-separated values in that
file and load $OBJDIR/info/commit-graphs/graph-{hash[i]}.graph for each hash[i]
in that file. The file is given in order, so the first hash corresponds to the
"base" file and the final hash corresponds to the "tip" file.

This implementation assumes that all of the graph-{hash}.graph files are in
the same object directory as the commit-graph-chain file. This will be updated
in a future change. This change is purposefully simple so we can isolate the
different concerns.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: expire commit-graph files

As we merge commit-graph files in a commit-graph chain, we should clean
up the files that are no longer used.

This change introduces an 'expiry_window' value to the context, which is
always zero (for now). We then check the modified time of each
graph-{hash}.graph file in the $OBJDIR/info/commit-graphs folder and
unlink the files that are older than the expiry_window.

Since this is always zero, this immediately clears all unused graph
files. We will update the value to match a config setting in a future
change.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: rename commit_compare to oid_compare

The helper function commit_compare() actually compares object_id
structs, not commits. A future change to commit-graph.c will need
to sort commit structs, so rename this function in advance.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: allow cross-alternate chains

In an environment like a fork network, it is helpful to have a
commit-graph chain that spans both the base repo and the fork repo. The
fork is usually a small set of data on top of the large repo, but
sometimes the fork is much larger. For example, git-for-windows/git has
almost double the number of commits as git/git because it rebases its
commits on every major version update.

To allow cross-alternate commit-graph chains, we need a few pieces:

1. When looking for a graph-{hash}.graph file, check all alternates.

2. When merging commit-graph chains, do not merge across alternates.

3. When writing a new commit-graph chain based on a commit-graph file
   in another object directory, do not allow success if the base file
   has of the name "commit-graph" instead of
   "commit-graphs/graph-{hash}.graph".

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

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 <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: document commit-graph chains

Add a basic description of commit-graph chains. More details about the
feature will be added as we add functionality. This introduction gives a
high-level overview to the goals of the feature and the basic layout of
commit-graph chains.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

stash: fix show referencing stash index

In the conversion of 'stash show' to C in dc7bd382b1 ("stash: convert
show to builtin", 2019-02-25), 'git stash show <n>', where n is the
index of a stash got broken, if n is not a file or a valid revision by
itself.

'stash show' accepts any flag 'git diff' accepts for changing the
output format.  Internally we use 'setup_revisions()' to parse these
command line flags.  Currently we pass the whole argv through to
'setup_revisions()', which includes the stash index.

As the stash index is not a valid revision or a file in the working
tree in most cases however, this 'setup_revisions()' call (and thus
the whole command) ends up failing if we use this form of 'git stash
show'.

Instead of passing the whole argv to 'setup_revisions()', only pass
the flags (and the command name) through, while excluding the stash
reference.  The stash reference is parsed (and validated) in
'get_stash_info()' already.

This separate parsing also means that we currently do produce the
correct output if the command succeeds.

Reported-by: Mike Hommey <redacted>
Signed-off-by: Thomas Gummerer <redacted>
Signed-off-by: Junio C Hamano <redacted>

ref-filter: sort detached HEAD lines firstly

Before this patch, "git branch" would put "(HEAD detached...)" and "(no
branch, rebasing...)" lines before all the other branches *in most
cases* except for when using Chinese-language messages. zh_CN generally
uses a full-width "(" symbol (codepoint FF08) to match the full-width
proportions of Chinese characters, and the translated strings we had did
use them. This meant that the detached HEAD line would appear after all
local refs and even after the remote refs if there were any.

AFAIK, it is sometimes not jarring to see the half-width parenthesis in
"full-width" text as in the CJK languages, for instance when there are
no characters preceding or following the parenthesized text fragment. By
removing the parenthesis from the localizable text, we can share strings
with wt-status.c and remove a cautionary comment to translators.

Remove the ( from the localizable portion of messages so the sorting
happens properly regardless of locale.

Helped-by: Johannes Schindelin <redacted>
Helped-by: Jonathan Nieder <redacted>
Signed-off-by: Matthew DeVore <redacted>
Signed-off-by: Junio C Hamano <redacted>

wt-status.h: drop stdio.h include

We started including stdio.h to pick up the declaration of "FILE" in
f26a001226 (Enable wt-status output to a given FILE pointer.,
2007-09-17). But there's no need, since headers can assume that
git-compat-util.h has been included, which covers stdio.

This should just be redundant, and not hurting anything (like pulling in
includes out of order) because C files are supposed to always include
git-compat-util.h first. But it's worth cleaning up to model good
behavior.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

verify-tag: drop signal.h include

There's no reason verify-tag.c needs to include signal.h. It's already
in git-compat-util.h, which we properly include as the first header.
And there doesn't seem to be a particular reason for this include; it's
just an artifact from the file creation in 2ae68fcb78 (Make verify-tag a
builtin., 2007-07-27).

Likewise verify-commit.c has the same issue, probably because it was
created using verify-tag as a template in d07b00b7f3 (verify-commit:
scriptable commit signature verification, 2014-06-23).

These includes are probably just redundant, and not hurting anything by
circumventing the order that git-compat-util.h tries to impose, since
we'll always have loaded git-compat-util by the time we get to these. So
this is just a cleanup, and shouldn't fix or break any platforms.

Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

wrapper: avoid undefined behaviour in macOS

0620b39b3b ("compat: add a mkstemps() compatibility function", 2009-05-31)
included a function based on code from libiberty which would result in
undefined behaviour in platforms where timeval's tv_usec is a 32-bit signed
type as shown by:

wrapper.c:505:31: runtime error: left shift of 594546 by 16 places cannot be represented in type '__darwin_suseconds_t' (aka 'int')

interestingly the version of this code from gcc never had this bug and the
code had a cast that would had prevented the issue (at least in 64-bit
platforms) but was misapplied.

change the cast to uint64_t so it also works in 32-bit platforms.

Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
Signed-off-by: Junio C Hamano <redacted>

interpret-trailers: load default config

The interpret-trailers program does not do the usual loading of config
via git_default_config(), and thus does not respect many of the usual
options. In particular, we will not load core.commentChar, even though
the underlying trailer code uses its value.

This can be seen in the accompanying test, where setting
core.commentChar to anything besides "#" results in a failure to treat
the comments correctly.

Reported-by: Masahiro Yamada <redacted>
Signed-off-by: Jeff King <redacted>
Signed-off-by: Junio C Hamano <redacted>

show --continue/skip etc. consistently in synopsis

Command mode options that the user can choose one among many are
listed like this in the documentation:

    git am (--continue | --skip | --abort | --quit)

They are listed on a single line and in parenthesis, because they
are not optional.

But documentation pages for some commands deviate from this norm.
Fix the merge and rebase docs to match this style.

Signed-off-by: Phillip Wood <redacted>
Signed-off-by: Junio C Hamano <redacted>

use COPY_ARRAY for copying arrays

Convert calls of memcpy(3) to use COPY_ARRAY, which shortens and
simplifies the code a bit.

Patch generated by Coccinelle and contrib/coccinelle/array.cocci.

Signed-off-by: Rene Scharfe <redacted>
Signed-off-by: Junio C Hamano <redacted>

coccinelle: use COPY_ARRAY for copying arrays

The current semantic patch for COPY_ARRAY transforms memcpy(3) calls on
pointers, but Coccinelle distinguishes them from arrays.  It already
contains three rules to handle the options for sizeof (i.e. source,
destination and type), and handling arrays as source and destination
would require four times as many rules if we enumerated all cases.

We also don't handle array subscripts, and supporting that would
increase the number of rules by another factor of four.  (An isomorphism
telling Coccinelle that "sizeof x[...]" is equivalent to "sizeof *x"
would be nice..)

Support arrays and array subscripts, but keep the number of rules down
by adding normalization steps: First turn array subscripts into
derefences, then determine the types of expressions used with sizeof and
replace them with these types, and then convert the different possible
combinations of arrays and pointers with memcpy(3) to COPY_ARRAY.

Signed-off-by: Rene Scharfe <redacted>
Signed-off-by: Junio C Hamano <redacted>

fsmonitor: avoid signed integer overflow / infinite loop

883e248b8a ("fsmonitor: teach git to optionally utilize a file system
monitor to speed up detecting new or changed files.", 2017-09-22) uses
an int in a loop that would wrap if index_state->cache_nr (unsigned)
is bigger than INT_MAX

Signed-off-by: Carlo Marcelo Arenas Belón <redacted>
Signed-off-by: Junio C Hamano <redacted>

test-hashmap: remove 'hash' command

If hashes like strhash() are updated, for example to use a different
hash algorithm, we should not have to be updating t0011 to change out
the hashes.

As long as hashmap can store and retrieve values, and that it performs
well, we should not care what are the values of the hashes. Let's just
focus on the externally visible behavior instead.

Suggested-by: Jeff King <redacted>
Signed-off-by: Christian Couder <redacted>
Signed-off-by: Junio C Hamano <redacted>

oidmap: use sha1hash() instead of static hash() function

Get rid of the static hash() function in oidmap.c which is redundant
with sha1hash(). Use sha1hash() directly instead.

Let's be more consistent and not use several hash functions doing
nearly exactly the same thing.

Signed-off-by: Christian Couder <redacted>
Signed-off-by: Junio C Hamano <redacted>

t: add t0016-oidmap.sh

Add actual tests for operations using `struct oidmap` from oidmap.{c,h}.

Helped-by: SZEDER Gábor <redacted>
Helped-by: Jeff King <redacted>
Signed-off-by: Christian Couder <redacted>
Signed-off-by: Junio C Hamano <redacted>

t/helper: add test-oidmap.c

This new helper is very similar to "test-hashmap.c" and will help
test how `struct oidmap` from oidmap.{c,h} can be used.

Helped-by: SZEDER Gábor <redacted>
Helped-by: Jeff King <redacted>
Signed-off-by: Christian Couder <redacted>
Signed-off-by: Junio C Hamano <redacted>

The second batch

Signed-off-by: Junio C Hamano <redacted>

Merge branch 'xl/record-partial-clone-origin'

When creating a partial clone, the object filtering criteria is
recorded for the origin of the clone, but this incorrectly used a
hardcoded name "origin" to name that remote; it has been corrected
to honor the "--origin <name>" option.

* xl/record-partial-clone-origin:
  clone: respect user supplied origin name when setting up partial clone

Merge branch 'pb/request-pull-verify-remote-ref'

"git request-pull" learned to warn when the ref we ask them to pull
from in the local repository and in the published repository are
different.

* pb/request-pull-verify-remote-ref:
  request-pull: warn if the remote object is not the same as the local one
  request-pull: quote regex metacharacters in local ref

Merge branch 'mm/p4-unshelve-windows-fix'

The command line to invoke a "git cat-file" command from inside
"git p4" was not properly quoted to protect a caret and running a
broken command on Windows, which has been corrected.

* mm/p4-unshelve-windows-fix:
  p4 unshelve: fix "Not a valid object name HEAD0" on Windows

Merge branch 'po/git-help-on-git-itself'

"git help git" was hard to discover (well, at least for some
people).

* po/git-help-on-git-itself:
  Doc: git.txt: remove backticks from link and add git-scm.com/docs
  git.c: show usage for accessing the git(1) help page

Merge branch 'es/first-contrib-tutorial'

A new tutorial targetting specifically aspiring git-core
developers.

* es/first-contrib-tutorial:
  doc: add some nit fixes to MyFirstContribution
  documentation: add anchors to MyFirstContribution
  documentation: add tutorial for first contribution

Merge branch 'bb/unicode-12.1-reiwa'

Update to Unicode 12.1 width table.

* bb/unicode-12.1-reiwa:
  unicode: update the width tables to Unicode 12.1

Merge branch 'sw/git-p4-unshelve-branched-files'

"git p4" update.

* sw/git-p4-unshelve-branched-files:
  git-p4: allow unshelving of branched files

Merge branch 'js/fsmonitor-unflake'

The data collected by fsmonitor was not properly written back to
the on-disk index file, breaking t7519 tests occasionally, which
has been corrected.

* js/fsmonitor-unflake:
  mark_fsmonitor_valid(): mark the index as changed if needed
  fill_stat_cache_info(): prepare for an fsmonitor fix

Merge branch 'ds/topo-traversal-using-commit-graph'

Prepare use of reachability index in topological walker that works
on a range (A..B).

* ds/topo-traversal-using-commit-graph:
  revision: keep topo-walk free of unintersting commits
  revision: use generation for A..B --topo-order queries

Merge branch 'bl/userdiff-octave'

The pattern "git diff/grep" use to extract funcname and words
boundary for Matlab has been extend to cover Octave, which is more
or less equivalent.

* bl/userdiff-octave:
  userdiff: fix grammar and style issues
  userdiff: add Octave

Merge branch 'ba/clone-remote-submodules'

"git clone --recurse-submodules" learned to set up the submodules
to ignore commit object names recorded in the superproject gitlink
and instead use the commits that happen to be at the tip of the
remote-tracking branches from the get-go, by passing the new
"--remote-submodules" option.

* ba/clone-remote-submodules:
  clone: add `--remote-submodules` flag

Merge branch 'vv/merge-squash-with-explicit-commit'

"git merge --squash" is designed to update the working tree and the
index without creating the commit, and this cannot be countermanded
by adding the "--commit" option; the command now refuses to work
when both options are given.

* vv/merge-squash-with-explicit-commit:
  merge: refuse --commit with --squash

Merge branch 'js/bundle-verify-require-object-store'

"git bundle verify" needs to see if prerequisite objects exist in
the receiving repository, but the command did not check if we are
in a repository upfront, which has been corrected.

* js/bundle-verify-require-object-store:
  bundle verify: error out if called without an object database

Merge branch 'js/bisect-helper-check-get-oid-return-value'

Code cleanup.

* js/bisect-helper-check-get-oid-return-value:
  bisect--helper: verify HEAD could be parsed before continuing

Merge branch 'jk/am-i-resolved-fix'

"git am -i --resolved" segfaulted after trying to see a commit as
if it were a tree, which has been corrected.

* jk/am-i-resolved-fix:
  am: fix --interactive HEAD tree resolution
  am: drop tty requirement for --interactive
  am: read interactive input from stdin
  am: simplify prompt response handling

Merge branch 'jk/HEAD-symref-in-xfer-namespaces'

The server side support for "git fetch" used to show incorrect
value for the HEAD symbolic ref when the namespace feature is in
use, which has been corrected.

* jk/HEAD-symref-in-xfer-namespaces:
  upload-pack: strip namespace from symref data

Merge branch 'ew/server-info-remove-crufts'

"git update-server-info" used to leave stale packfiles in its
output, which has been corrected.

* ew/server-info-remove-crufts:
  server-info: do not list unlinked packs

Merge branch 'es/grep-require-name-when-needed'

More parameter validation.

* es/grep-require-name-when-needed:
  grep: fail if call could output and name is null

Merge branch 'es/git-debugger-doc'

Doc update.

* es/git-debugger-doc:
  doc: hint about GIT_DEBUGGER in CodingGuidelines

Merge branch 'ds/object-info-for-prefetch-fix'

Code cleanup and futureproof.

* ds/object-info-for-prefetch-fix:
  sha1-file: split OBJECT_INFO_FOR_PREFETCH

t3404: fix a typo

This one slipped through the review of a9279c678588 (sequencer: do not
squash 'reword' commits when we hit conflicts, 2018-06-19).

Signed-off-by: Johannes Schindelin <redacted>
Signed-off-by: Junio C Hamano <redacted>

The first batch after 2.22

Signed-off-by: Junio C Hamano <redacted>

Merge branch 'pw/rebase-edit-message-for-replayed-merge'

A "merge -c" instruction during "git rebase --rebase-merges" should
give the user a chance to edit the log message, even when there is
otherwise no need to create a new merge and replace the existing
one (i.e. fast-forward instead), but did not.  Which has been
corrected.

* pw/rebase-edit-message-for-replayed-merge:
  rebase -r: always reword merge -c

Merge branch 'ab/deprecate-R-for-dynpath'

The way of specifying the path to find dynamic libraries at runtime
has been simplified.  The old default to pass -R/path/to/dir has been
replaced with the new default to pass -Wl,-rpath,/path/to/dir,
which is the more recent GCC uses.  Those who need to build with an
old GCC can still use "CC_LD_DYNPATH=-R"

* ab/deprecate-R-for-dynpath:
  Makefile: remove the NO_R_TO_GCC_LINKER flag

Merge branch 'mh/import-transport-fd-fix'

The ownership rule for the file descriptor to fast-import remote
backend was mixed up, leading to unrelated file descriptor getting
closed, which has been fixed.

* mh/import-transport-fd-fix:
  Use xmmap_gently instead of xmmap in use_pack
  dup() the input fd for fast-import used for remote helpers

Merge branch 'ew/update-server-info'

"git update-server-info" learned not to rewrite the file with the
same contents.

* ew/update-server-info:
  update-server-info: avoid needless overwrites

Merge branch 'jk/help-unknown-ref-fix'

Improve the code to show args with potential typo that cannot be
interpreted as a commit-ish.

* jk/help-unknown-ref-fix:
  help_unknown_ref(): check for refname ambiguity
  help_unknown_ref(): duplicate collected refnames

Merge branch 'dl/format-patch-notes-config'

"git format-patch" learns a configuration to set the default for
its --notes=<ref> option.

* dl/format-patch-notes-config:
  format-patch: teach format.notes config option
  git-format-patch.txt: document --no-notes option

Merge branch 'nd/merge-quit'

"git merge" learned "--quit" option that cleans up the in-progress
merge while leaving the working tree and the index still in a mess.

* nd/merge-quit:
  merge: add --quit
  merge: remove drop_save() in favor of remove_merge_branch_state()

Merge branch 'ab/fail-prereqs-in-test'

Developer support to emulate unsatisfied prerequisites in tests to
ensure that the remainer of the tests still succeeds when tests
with prerequisites are skipped.

* ab/fail-prereqs-in-test:
  tests: add a special setup where prerequisites fail

Merge branch 'nd/corrupt-worktrees'

"git worktree add" used to fail when another worktree connected to
the same repository was corrupt, which has been corrected.

* nd/corrupt-worktrees:
  worktree add: be tolerant of corrupt worktrees

Merge branch 'js/rebase-cleanup'

Update supporting parts of "git rebase" to remove code that should
no longer be used.

* js/rebase-cleanup:
  rebase: fold git-rebase--common into the -p backend
  sequencer: the `am` and `rebase--interactive` scripts are gone
  .gitignore: there is no longer a built-in `git-rebase--interactive`
  t3400: stop referring to the scripted rebase
  Drop unused git-rebase--am.sh

Merge branch 'nd/worktree-name-sanitization'

In recent versions of Git, per-worktree refs are exposed in
refs/worktrees/<wtname>/ hierarchy, which means that worktree names
must be a valid refname component.  The code now sanitizes the names
given to worktrees, to make sure these refs are well-formed.

* nd/worktree-name-sanitization:
  worktree add: sanitize worktree names

Merge branch 'en/fast-export-encoding'

The "git fast-export/import" pair has been taught to handle commits
with log messages in encoding other than UTF-8 better.

* en/fast-export-encoding:
  fast-export: do automatic reencoding of commit messages only if requested
  fast-export: differentiate between explicitly UTF-8 and implicitly UTF-8
  fast-export: avoid stripping encoding header if we cannot reencode
  fast-import: support 'encoding' commit header
  t9350: fix encoding test to actually test reencoding

Merge branch 'jk/unused-params-final-batch'

* jk/unused-params-final-batch:
  verify-commit: simplify parameters to run_gpg_verify()
  show-branch: drop unused parameter from show_independent()
  rev-list: drop unused void pointer from finish_commit()
  remove_all_fetch_refspecs(): drop unused "remote" parameter
  receive-pack: drop unused "commands" from prepare_shallow_update()
  pack-objects: drop unused rev_info parameters
  name-rev: drop unused parameters from is_better_name()
  mktree: drop unused length parameter
  wt-status: drop unused status parameter
  read-cache: drop unused parameter from threaded load
  clone: drop dest parameter from copy_alternates()
  submodule: drop unused prefix parameter from some functions
  builtin: consistently pass cmd_* prefix to parse_options
  cmd_{read,write}_tree: rename "unused" variable that is used

Merge branch 'sb/format-patch-base-patch-id-fix'

The "--base" option of "format-patch" computed the patch-ids for
prerequisite patches in an unstable way, which has been updated to
compute in a way that is compatible with "git patch-id --stable".

* sb/format-patch-base-patch-id-fix:
  format-patch: make --base patch-id output stable
  format-patch: inform user that patch-id generation is unstable

Merge branch 'nd/init-relative-template-fix'

A relative pathname given to "git init --template=<path> <repo>"
ought to be relative to the directory "git init" gets invoked in,
but it instead was made relative to the repository, which has been
corrected.

* nd/init-relative-template-fix:
  init: make --template path relative to $CWD

Merge branch 'ab/send-email-transferencoding-fix'

Since "git send-email" learned to take 'auto' as the value for the
transfer-encoding, it by mistake stopped honoring the values given
to the configuration variables sendemail.transferencoding and/or
sendemail.<ident>.transferencoding.  This has been corrected to
(finally) redoing the order of setting the default, reading the
configuration and command line options.

* ab/send-email-transferencoding-fix:
  send-email: fix regression in sendemail.identity parsing
  send-email: document --no-[to|cc|bcc]
  send-email: fix broken transferEncoding tests
  send-email: remove cargo-culted multi-patch pattern in tests
  send-email: do defaults -> config -> getopt in that order
  send-email: rename the @bcclist variable for consistency
  send-email: move the read_config() function above getopts

cleanup: fix possible overflow errors in binary search, part 2

Calculating the sum of two array indexes to find the midpoint between
them can overflow, i.e. code like this is unsafe for big arrays:

mid = (first + last) >> 1;

Make sure the intermediate value stays within the boundaries instead,
like this:

mid = first + ((last - first) >> 1);

The loop condition of the binary search makes sure that 'last' is
always greater than 'first', so this is safe as long as 'first' is
not negative.  And that can be verified easily using the pre-context
of each change, except for name-hash.c, so add an assertion to that
effect there.

The unsafe calculations were found with:

git grep '(.*+.*) *>> *1'

This is a continuation of 19716b21a4 (cleanup: fix possible overflow
errors in binary search, 2017-10-08).

Signed-off-by: Rene Scharfe <redacted>
Signed-off-by: Junio C Hamano <redacted>

add -p: fix checkout -p with pathological context

Commit fecc6f3a68 ("add -p: adjust offsets of subsequent hunks when one is
skipped", 2018-03-01) fixed adding hunks in the correct place when a
previous hunk has been skipped. However it did not address patches that
are applied in reverse. In that case we need to adjust the pre-image
offset so that when apply reverses the patch the post-image offset is
adjusted correctly. We subtract rather than add the delta as the patch
is reversed (the easiest way to think about it is to consider a hunk of
deletions that is skipped - in that case we want to reduce offset so we
need to subtract).

Signed-off-by: Phillip Wood <redacted>
Signed-off-by: Junio C Hamano <redacted>

config: avoid calling `labs()` on too-large data type

The `labs()` function operates, as the initial `l` suggests, on `long`
parameters. However, in `config.c` we tried to use it on values of type
`intmax_t`.

This problem was found by GCC v9.x.

To fix it, let's just "unroll" the function (i.e. negate the value if it
is negative).

Signed-off-by: Johannes Schindelin <redacted>
Signed-off-by: Junio C Hamano <redacted>

winansi: simplify loading the GetCurrentConsoleFontEx() function

We introduced helper macros to simplify loading functions dynamically.
Might just as well use them.

This also side-steps a compiler warning when building with GCC v8.x: it
would complain about casting between incompatible function pointers.

Signed-off-by: Johannes Schindelin <redacted>
Signed-off-by: Junio C Hamano <redacted>

kwset: allow building with GCC 8

The kwset functionality makes use of the obstack code, which expects to
be handed a function that can allocate large chunks of data. It expects
that function to accept a `size` parameter of type `long`.

This upsets GCC 8 on Windows, because `long` does not have the same
bit size as `size_t` there.

Now, the proper thing to do would be to switch to `size_t`. But this
would make us deviate from the "upstream" code even further, making it
hard to synchronize with newer versions, and also it would be quite
involved because that `long` type is so invasive in that code.

Let's punt, and instead provide a super small wrapper around
`xmalloc()`.

Signed-off-by: Johannes Schindelin <redacted>
Signed-off-by: Junio C Hamano <redacted>

poll (mingw): allow compiling with GCC 8 and DEVELOPER=1

The return type of the `GetProcAddress()` function is `FARPROC` which
evaluates to `long long int (*)()`, i.e. it cannot be cast to the
correct function signature by GCC 8.

To work around that, we first cast to `void *` and go on with our merry
lives.

Signed-off-by: Johannes Schindelin <redacted>
Signed-off-by: Junio C Hamano <redacted>

mergetool: use shell variable magic instead of `awk`

git-mergetool spawns an enormous amount of processes. For this reason,
the test script, t7610, is exceptionally slow, in particular, on
Windows. Most of the processes are invocations of git. There are
also some that can be replaced with shell builtins. Avoid repeated
calls of `git ls-files` and `awk`.

Signed-off-by: Johannes Sixt <redacted>
Signed-off-by: Junio C Hamano <redacted>

mergetool: dissect strings with shell variable magic instead of `expr`

git-mergetool spawns an enormous amount of processes. For this reason,
the test script, t7610, is exceptionally slow, in particular, on
Windows. Most of the processes are invocations of git. There are
also some that can be replaced with shell builtins. Do so with `expr`.

Signed-off-by: Johannes Sixt <redacted>
Signed-off-by: Junio C Hamano <redacted>

t7610-mergetool: use test_cmp instead of test $(cat file) = $txt

Fix that anti-pattern by a sequence of echo and test_cmp.

The patch was generated with this command:

   sed -i -e '/test.*(cat/s/^\(\t*\)test "..cat \(.*\))" = \(".*"\)\(.*\)/\1echo \3 >expect \&\&\n\1test_cmp expect \2\4/' t7610-mergetool.sh

This helps on Windows, where test_cmp avoids spawning a process when
there is no difference.

Signed-off-by: Johannes Sixt <redacted>
Signed-off-by: Junio C Hamano <redacted>

packfile: rename close_all_packs to close_object_store

The close_all_packs() method is now responsible for more than just pack-files.
It also closes the commit-graph and the multi-pack-index. Rename the function
to be more descriptive of its larger role. The name also fits because the
input parameter is a raw_object_store.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

packfile: close commit-graph in close_all_packs

The close_all_packs() method is used to close all read handles to
pack-files and the multi-pack-index before running 'git gc --auto'.
This is particularly important on the Windows platform, where read
handles block any writes to those files. Replacing one of these
files with a rename() will fail in this situation.

The commit-graph also performs a rename, so is susceptable to this
problem. We are careful to close the commit-graph before writing,
but that doesn't work when a 'git fetch' (or similar) process runs
'git gc --auto' which may write a commit-graph.

Here, close the commit-graph as part of close_all_packs().

Reported-by: Johannes Schindelin <redacted>
Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: use raw_object_store when closing

The close_commit_graph() method took a repository struct, but then
only uses the raw_object_store within. Change the function prototype
to make the method more flexible.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: extract write_commit_graph_file()

The write_commit_graph() method is too complex, so we are
extracting helper functions one by one.

Extract write_commit_graph_file() that takes all of the information
in the context struct and writes the data to a commit-graph file.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: extract copy_oids_to_commits()

The write_commit_graph() method is too complex, so we are
extracting helper functions one by one.

Extract copy_oids_to_commits(), which fills the commits list
with the distinct commits from the oids list. During this loop,
it also counts the number of "extra" edges from octopus merges.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: extract count_distinct_commits()

The write_commit_graph() method is too complex, so we are
extracting helper functions one by one.

Extract count_distinct_commits(), which sorts the oids list, then
iterates through to find duplicates.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>

commit-graph: extract fill_oids_from_all_packs()

The write_commit_graph() method is too complex, so we are
extracting helper functions one by one.

Extract fill_oids_from_all_packs() that reads all pack-files
for commits and fills the oid list in the context.

Signed-off-by: Derrick Stolee <redacted>
Signed-off-by: Junio C Hamano <redacted>