pseudo-merge: implement support for finding existing merges

This patch implements support for reusing existing pseudo-merge commits
when writing bitmaps when there is an existing pseudo-merge bitmap which
has exactly the same set of parents as one that we are about to write.

Note that unstable pseudo-merges are likely to change between
consecutive repacks, and so are generally poor candidates for reuse.
However, stable pseudo-merges (see the configuration option
'bitmapPseudoMerge.<name>.stableThreshold') are by definition unlikely
to change between runs (as they represent long-running branches).

Because there is no index from a *set* of pseudo-merge parents to a
matching pseudo-merge bitmap, we have to construct the bitmap
corresponding to the set of parents for each pending pseudo-merge commit
and see if a matching bitmap exists.

This is technically quadratic in the number of pseudo-merges, but is OK
in practice for a couple of reasons:

  - non-matching pseudo-merge bitmaps are rejected quickly as soon as
    they differ in a single bit

  - already-matched pseudo-merge bitmaps are discarded from subsequent
    rounds of search

  - the number of pseudo-merges is generally small, even for large
    repositories

In order to do this, implement (a) a function that finds a matching
pseudo-merge given some uncompressed bitset describing its parents, (b)
a function that computes the bitset of parents for a given pseudo-merge
commit, and (c) call that function before computing the set of reachable
objects for some pending pseudo-merge.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

ewah: `bitmap_equals_ewah()`

Prepare to reuse existing pseudo-merge bitmaps by implementing a
`bitmap_equals_ewah()` helper.

This helper will be used to see if a raw bitmap (containing the set of
parents for some pseudo-merge) is equal to any existing pseudo-merge's
commits bitmap (which are stored as EWAH-compressed bitmaps on disk).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: extra trace2 information

Add some extra trace2 lines to capture the number of bitmap lookups that
are hits versus misses, as well as the number of reachability roots that
have bitmap coverage (versus those that do not).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap.c: use pseudo-merges during traversal

Now that all of the groundwork has been laid to support reading and
using pseudo-merges, make use of that work in this commit by teaching
the pack-bitmap machinery to use pseudo-merge(s) when available during
traversal.

The basic operation is as follows:

  - When enumerating objects on either side of a reachability query,
    first see if any subset of the roots satisfies some pseudo-merge
    bitmap. If it does, apply that pseudo-merge bitmap.

  - If any pseudo-merge bitmap(s) were applied in the previous step, OR
    them into the result[^1]. Then repeat the process over all
    pseudo-merge bitmaps (we'll refer to this as "cascading"
    pseudo-merges). Once this is done, OR in the resulting bitmap.

  - If there is no fill-in traversal to be done, return the bitmap for
    that side of the reachability query. If there is fill-in traversal,
    then for each commit we encounter via show_commit(), check to see if
    any unsatisfied pseudo-merges containing that commit as one of its
    parents has been made satisfied by the presence of that commit.

    If so, OR in the object set from that pseudo-merge bitmap, and then
    cascade. If not, continue traversal.

A similar implementation is present in the boundary-based bitmap
traversal routines.

[^1]: Importantly, we cannot OR in the entire set of roots along with
  the objects reachable from whatever pseudo-merge bitmaps were
  satisfied.  This may leave some dangling bits corresponding to any
  unsatisfied root(s) getting OR'd into the resulting bitmap, tricking
  other parts of the traversal into thinking we already have a
  reachability closure over those commit(s) when we do not.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()`

One of the tests we'll want to add for pseudo-merge bitmaps needs to be
able to generate a large number of commits at a specific date.

Support the `--notick` option (with identical semantics to the
`--notick` option for `test_commit()`) within `test_commit_bulk` as a
prerequisite for that. Callers can then set the various _DATE variables
themselves.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: implement test helpers for pseudo-merge

Implement three new sub-commands for the "bitmap" test-helper:

  - t/helper test-tool bitmap dump-pseudo-merges
  - t/helper test-tool bitmap dump-pseudo-merge-commits <n>
  - t/helper test-tool bitmap dump-pseudo-merge-objects <n>

These three helpers dump the list of pseudo merges, the "parents" of the
nth pseudo-merges, and the set of objects reachable from those parents,
respectively.

These helpers will be useful in subsequent patches when we add test
coverage for pseudo-merge bitmaps.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

ewah: implement `ewah_bitmap_popcount()`

Some of the pseudo-merge test helpers (which will be introduced in the
following commit) will want to indicate the total number of commits in
or objects reachable from a pseudo-merge.

Implement a popcount() function that operates on EWAH bitmaps to quickly
determine how many bits are set in each of the respective bitmaps.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pseudo-merge: implement support for reading pseudo-merge commits

Implement the basic API for reading pseudo-merge bitmaps, which consists
of four basic functions:

  - pseudo_merge_bitmap()
  - use_pseudo_merge()
  - apply_pseudo_merges_for_commit()
  - cascade_pseudo_merges()

These functions are all documented in pseudo-merge.h, but their rough
descriptions are as follows:

  - pseudo_merge_bitmap() reads and inflates the objects EWAH bitmap for
    a given pseudo-merge

  - use_pseudo_merge() does the same as pseudo_merge_bitmap(), but on
    the commits EWAH bitmap, not the objects bitmap

  - apply_pseudo_merges_for_commit() applies all satisfied pseudo-merge
    commits for a given result set, and cascades any yet-unsatisfied
    pseudo-merges if any were applied in the previous step

  - cascade_pseudo_merges() applies all pseudo-merges which are
    satisfied but have not been previously applied, repeating this
    process until no more pseudo-merges can be applied

The core of the API is the latter two functions, which are responsible
for applying pseudo-merges during the object traversal implemented in
the pack-bitmap machinery.

The other two functions (pseudo_merge_bitmap(), and use_pseudo_merge())
are low-level ways to interact with the pseudo-merge machinery, which
will be useful in future commits.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap.c: read pseudo-merge extension

Now that the scaffolding for reading the pseudo-merge extension has been
laid, teach the pack-bitmap machinery to read the pseudo-merge extension
when present.

Note that pseudo-merges themselves are not yet used during traversal,
this step will be taken by a future commit.

In the meantime, read the table and initialize the pseudo_merge_map
structure introduced by a previous commit. When the pseudo-merge
extension is present, `load_bitmap_header()` performs basic sanity
checks to make sure that the table is well-formed.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pseudo-merge: scaffolding for reads

Implement scaffolding within the new pseudo-merge compilation unit
necessary to use the pseudo-merge API from within the pack-bitmap.c
machinery.

The core of this scaffolding is two-fold:

  - The `pseudo_merge` structure itself, which represents an individual
    pseudo-merge bitmap. It has fields for both bitmaps, as well as
    metadata about its position within the memory-mapped region, and
    a few extra bits indicating whether or not it is satisfied, and
    which bitmaps(s, if any) have been read, since they are initialized
    lazily.

  - The `pseudo_merge_map` structure, which holds an array of
    pseudo_merges, as well as a pointer to the memory-mapped region
    containing the pseudo-merge serialization from within a .bitmap
    file.

Note that the `bitmap_index` structure is defined statically within the
pack-bitmap.o compilation unit, so we can't take in a `struct
bitmap_index *`. Instead, wrap the primary components necessary to read
the pseudo-merges in this new structure to avoid exposing the
implementation details of the `bitmap_index` structure.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: extract `read_bitmap()` function

The pack-bitmap machinery uses the `read_bitmap_1()` function to read a
bitmap from within the mmap'd region corresponding to the .bitmap file.
As as side-effect of calling this function, `read_bitmap_1()` increments
the `index->map_pos` variable to reflect the number of bytes read.

Extract the core of this routine to a separate function (that operates
over a `const unsigned char *`, a `size_t` and a `size_t *` pointer)
instead of a `struct bitmap_index *` pointer.

This function (called `read_bitmap()`) is part of the pack-bitmap.h API
so that it can be used within the upcoming portion of the implementation
in pseduo-merge.ch.

Rewrite the existing function, `read_bitmap_1()`, in terms of its more
generic counterpart.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap-write.c: write pseudo-merge table

Now that the pack-bitmap writer machinery understands how to select and
store pseudo-merge commits, teach it how to write the new optional
pseudo-merge .bitmap extension.

No readers yet exist for this new extension to the .bitmap format. The
following commits will take any preparatory step(s) necessary before
then implementing the routines necessary to read this new table.

In the meantime, the new `write_pseudo_merges()` function implements
writing this new format as described by a previous commit in
Documentation/technical/bitmap-format.txt.

Writing this table is fairly straightforward and consists of a few
sub-components:

  - a pair of bitmaps for each pseudo-merge (one for the pseudo-merge
    "parents", and another for the objects reachable from those parents)

  - for each commit, the offset of either (a) the pseudo-merge it
    belongs to, or (b) an extended lookup table if it belongs to >1
    pseudo-merge groups

  - if there are any commits belonging to >1 pseudo-merge group, the
    extended lookup tables (which each consist of the number of
    pseudo-merge groups a commit appears in, and then that many 4-byte
    unsigned )

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pseudo-merge: implement support for selecting pseudo-merge commits

Teach the new pseudo-merge machinery how to select non-bitmapped commits
for inclusion in different pseudo-merge group(s) based on a handful of
criteria.

Note that the selected pseudo-merge commits aren't actually used or
written anywhere yet. This will be done in the following commit.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

config: introduce `git_config_double()`

Future commits will want to parse a double-precision floating point
value from configuration, but we have no way to parse such a value prior
to this patch.

The core of the routine is implemented in git_parse_double(). Unlike
git_parse_unsigned() and git_parse_signed(), however, the function
implemented here only works on type "double", and not related types like
"float", or "long double".

This is because "float" and "long double" use different functions to
convert from ASCII strings to floating point values (strtof() and
strtold(), respectively). Likewise, there is no pointer type that can
assign to any of these values (except for "void *"), so the only way to
define this trio of functions would be with a macro expansion that is
parameterized over the floating point type and conversion function.

That is all doable, but likely to be overkill given our current needs,
which is only to parse double-precision floats.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public

The pseudo-merge selection code will be added in a subsequent commit,
and will need a way to push the allocated commit structures into the
bitmap writer from a separate compilation unit.

Make the `bitmap_writer_push_bitmapped_commit()` function part of the
pack-bitmap.h header in order to make this possible.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()`

Prepare to implement pseudo-merge bitmap selection by implementing a
necessary new function, `bitmap_writer_has_bitmapped_object_id()`.

This function returns whether or not the bitmap_writer selected the
given object ID for bitmapping. This will allow the pseudo-merge
machinery to reject candidates for pseudo-merges if they have already
been selected as an ordinary bitmap tip.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap-write: support storing pseudo-merge commits

Prepare to write pseudo-merge bitmaps by annotating individual bitmapped
commits (which are represented by the `bitmapped_commit` structure) with
an extra bit indicating whether or not they are a pseudo-merge.

In subsequent commits, pseudo-merge bitmaps will be generated by
allocating a fake commit node with parents covering the full set of
commits represented by the pseudo-merge bitmap. These commits will be
added to the set of "selected" commits as usual, but will be written
specially instead of being included with the rest of the selected
commits.

Mechanically speaking, there are two parts of this change:

  - The bitmapped_commit struct gets a new bit indicating whether it is
    a pseudo-merge, or an ordinary commit selected for bitmaps.

  - A handful of changes to only write out the non-pseudo-merge commits
    when enumerating through the selected array (see the new
    `bitmap_writer_selected_nr()` function). Pseudo-merge commits appear
    after all non-pseudo-merge commits, so it is safe to enumerate
    through the selected array like so:

        for (i = 0; i < bitmap_writer_selected_nr(); i++)
          if (writer.selected[i].pseudo_merge)
            BUG("unexpected pseudo-merge");

    without encountering the BUG().

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pseudo-merge.ch: initial commit

Add a new (empty) header file to contain the implementation for
selecting, reading, and applying pseudo-merge bitmaps.

For now this header and its corresponding implementation are left
empty, but they will evolve over the course of subsequent commit(s).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: move some initialization to `bitmap_writer_init()`

The pack-bitmap-writer machinery uses a oidmap (backed by khash.h) to
map from commits selected for bitmaps (by OID) to a bitmapped_commit
structure (containing the bitmap itself, among other things like its XOR
offset, etc.)

This map was initialized at the end of `bitmap_writer_build()`. New
entries are added in `pack-bitmap-write.c::store_selected()`, which is
called by the bitmap_builder machinery (which is responsible for
traversing history and generating the actual bitmaps).

Reorganize when this field is initialized and when entries are added to
it so that we can quickly determine whether a commit is a candidate for
pseudo-merge selection, or not (since it was already selected to receive
a bitmap, and thus storing it in a pseudo-merge would be redundant).

The changes are as follows:

  - Introduce a new `bitmap_writer_init()` function which initializes
    the `writer.bitmaps` field (instead of waiting until the end of
    `bitmap_writer_build()`).

  - Add map entries in `push_bitmapped_commit()` (which is called via
    `bitmap_writer_select_commits()`) with OID keys and NULL values to
    track whether or not we *expect* to write a bitmap for some given
    commit.

  - Validate that a NULL entry is found matching the given key when we
    store a selected bitmap.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

ewah: implement `ewah_bitmap_is_subset()`

In order to know whether a given pseudo-merge (comprised of a "parents"
and "objects" bitmaps) is "satisfied" and can be OR'd into the bitmap
result, we need to be able to quickly determine whether the "parents"
bitmap is a subset of the current set of objects reachable on either
side of a traversal.

Implement a helper function to prepare for that, which determines
whether an EWAH bitmap (the parents bitmap from the pseudo-merge) is a
subset of a non-EWAH bitmap (in this case, the results bitmap from
either side of the traversal).

This function makes use of the EWAH iterator to avoid inflating any part
of the EWAH bitmap after we determine it is not a subset of the non-EWAH
bitmap. This "fail-fast" allows us to avoid a potentially large amount
of wasted effort.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Documentation/technical: describe pseudo-merge bitmaps format

Prepare to implement pseudo-merge bitmaps over the next several commits
by first describing the serialization format which will store the new
pseudo-merge bitmaps themselves.

This format is implemented as an optional extension within the bitmap v1
format, making it compatible with previous versions of Git, as well as
the original .bitmap implementation within JGit.

The format is described in detail in the patch contents below, but the
high-level description is as follows:

  - An array of pseudo-merge bitmaps, each containing a pair of EWAH
    bitmaps: one describing the set of pseudo-merge "parents", and
    another describing the set of object(s) reachable from those
    parents.

  - A lookup table to determine which pseudo-merge(s) a given commit
    appears in. An optional extended lookup table follows when there is
    at least one commit which appears in multiple pseudo-merge groups.

  - Trailing metadata, including the number of pseudo-merge(s), number
    of unique parents, the offset within the .bitmap file for the
    pseudo-merge commit lookup table, and the size of the optional
    extension itself.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Documentation/gitpacking.txt: describe pseudo-merge bitmaps

Add some details to the gitpacking(7) manual page which motivate and
describe pseudo-merge bitmaps.

The exact on-disk format and many of the configuration knobs will be
described in subsequent commits.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Documentation/gitpacking.txt: initial commit

Introduce a new manual page, gitpacking(7) to collect useful information
about advanced packing concepts in Git.

In future commits in this series, this manual page will expand to
describe the new pseudo-merge bitmaps feature, as well as include
examples, relevant configuration bits, use-cases, and so on.

Outside of this series, this manual page may absorb similar pieces from
other parts of Git's documentation about packing.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'tb/pack-bitmap-write-cleanups' into tb/pseudo-merge-reachability-bitmap

* tb/pack-bitmap-write-cleanups:
  pack-bitmap: introduce `bitmap_writer_free()`
  pack-bitmap-write.c: avoid uninitialized 'write_as' field
  pack-bitmap: drop unused `max_bitmaps` parameter
  pack-bitmap: avoid use of static `bitmap_writer`
  pack-bitmap-write.c: move commit_positions into commit_pos fields
  object.h: add flags allocated by pack-bitmap.h

pack-bitmap: introduce `bitmap_writer_free()`

Now that there is clearer memory ownership around the bitmap_writer
structure, introduce a bitmap_writer_free() function that callers may
use to free any memory associated with their instance of the
bitmap_writer structure.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap-write.c: avoid uninitialized 'write_as' field

Prepare to free() memory associated with bitmapped_commit structs by
zero'ing the 'write_as' field.

In ideal cases, it is fine to do something like:

    for (i = 0; i < writer->selected_nr; i++) {
        struct bitmapped_commit *bc = &writer->selected[i];
        if (bc->write_as != bc->bitmap)
            ewah_free(bc->write_as);
        ewah_free(bc->bitmap);
    }

but if not all of the 'write_as' fields were populated (e.g., because
the packing_data given does not form a reachability closure), then we
may attempt to free uninitialized memory.

Guard against this by preemptively zero'ing this field just in case.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: drop unused `max_bitmaps` parameter

The `max_bitmaps` parameter in `bitmap_writer_select_commits()` was
introduced back in 7cc8f97108 (pack-objects: implement bitmap writing,
2013-12-21), making it original to the bitmap implementation in Git
itself.

When that patch was merged via 0f9e62e084 (Merge branch
'jk/pack-bitmap', 2014-02-27), its sole caller in builtin/pack-objects.c
passed a value of "-1" for `max_bitmaps`, indicating no limit.

Since then, the only other caller (in midx.c, added via c528e17966
(pack-bitmap: write multi-pack bitmaps, 2021-08-31)) also uses a value
of "-1" for `max_bitmaps`.

Since no callers have needed a finite limit for the `max_bitmaps`
parameter in the nearly decade that has passed since 0f9e62e084, let's
remove the parameter and any dead pieces of code connected to it.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap: avoid use of static `bitmap_writer`

The pack-bitmap machinery uses a structure called 'bitmap_writer' to
collect the data necessary to write out .bitmap files. Since its
introduction in 7cc8f971085 (pack-objects: implement bitmap writing,
2013-12-21), there has been a single static bitmap_writer structure,
which is responsible for all bitmap writing-related operations.

In practice, this is OK, since we are only ever writing a single .bitmap
file in a single process (e.g., `git multi-pack-index write --bitmap`,
`git pack-objects --write-bitmap-index`, `git repack -b`, etc.).

However, having a single static variable makes issues like data
ownership unclear, when to free variables, what has/hasn't been
initialized unclear.

Refactor this code to be written in terms of a given bitmap_writer
structure instead of relying on a static global.

Note that this exposes the structure definition of the bitmap_writer at
the pack-bitmap.h level. We could work around this by, e.g., forcing
callers to declare their writers as:

    struct bitmap_writer *writer;
    bitmap_writer_init(&bitmap_writer);

and then declaring `bitmap_writer_init()` as taking in a double-pointer
like so:

    void bitmap_writer_init(struct bitmap_writer **writer);

which would avoid us having to expose the definition of the structure
itself. This patch takes a different approach, since future patches
(like for the ongoing pseudo-merge bitmaps work) will want to modify the
innards of this structure (in the previous example, via pseudo-merge.c).

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

pack-bitmap-write.c: move commit_positions into commit_pos fields

In 7cc8f971085 (pack-objects: implement bitmap writing, 2013-12-21), the
bitmapped_commit struct was introduced, including the 'commit_pos'
field, which has been unused ever since its introduction more than a
decade ago.

Instead, we have used the nearby `commit_positions` array leaving the
bitmapped_commit struct with an unused 4-byte field.

We could drop the `commit_pos` field as unused, and continue to store
the values in the auxiliary array. But we could also drop the array and
store the data for each bitmapped_commit struct inside of the structure
itself, which is what this patch does.

In any spot that we previously read `commit_positions[i]`, we can now
instead read `writer.selected[i].commit_pos`. There are a few spots that
need changing as a result:

  - write_selected_commits_v1() is a simple transformation, since we're
    just reading the field. As a result, the function no longer needs an
    explicit argument to pass the commit_positions array.

  - write_lookup_table() also no longer needs the explicit
    commit_positions array passed in as an argument. But it still needs
    to sort an array of indices into the writer.selected array to read
    them in commit_pos order, so table_cmp() is adjusted accordingly.

  - bitmap_writer_finish() no longer needs to allocate, populate, and
    free the commit_positions table. Instead, we can just write the data
    directly into each struct bitmapped_commit.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

object.h: add flags allocated by pack-bitmap.h

In commit 7cc8f971085 (pack-objects: implement bitmap writing,
2013-12-21) the NEEDS_BITMAP flag was introduced into pack-bitmap.h, but
no object flags allocation table existed at the time.

In 208acbfb82f (object.h: centralize object flag allocation, 2014-03-25)
when that table was first introduced, we never added the flags from
7cc8f971085, which has remained the case since.

Rectify this by including the flag bit used by pack-bitmap.h into the
centralized table in object.h.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Git 2.45

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge tag 'l10n-2.45.0-rnd1' of https://github.com/git-l10n/git-po

l10n-2.45.0-rnd1

* tag 'l10n-2.45.0-rnd1' of https://github.com/git-l10n/git-po:
  l10n: tr: Update Turkish translations
  l10n: zh_CN: for git 2.45 rounds
  l10n: zh-TW: Git 2.45
  l10n: vi: Updated translation for 2.45
  l10n: TEAMS: retire l10n teams no update in 1 year
  l10n: uk: v2.45 update
  l10n: sv.po: Update Swedish translation
  l10n: Update German translation
  l10n: po-id for 2.45
  l10n: bg.po: Updated Bulgarian translation (5652t)
  l10n: fr: v2.45.0
  l10n: Update Vietnamese team contact

Merge branch 'master' of github.com:alshopov/git-po

* 'master' of github.com:alshopov/git-po:
  l10n: bg.po: Updated Bulgarian translation (5652t)

Merge branch 'fr_v2.45.0' of github.com:jnavila/git

* 'fr_v2.45.0' of github.com:jnavila/git:
  l10n: fr: v2.45.0

l10n: tr: Update Turkish translations

Signed-off-by: Emir SARI <emir_sari@icloud.com>

Merge branch 'l10n/zh-TW/240428' of github.com:l10n-tw/git-po

* 'l10n/zh-TW/240428' of github.com:l10n-tw/git-po:
  l10n: zh-TW: Git 2.45

Merge branch 'tl/zh_CN_2.45.0_rnd' of github.com:dyrone/git

* 'tl/zh_CN_2.45.0_rnd' of github.com:dyrone/git:
  l10n: zh_CN: for git 2.45 rounds

l10n: zh_CN: for git 2.45 rounds

Signed-off-by: Teng Long <dyroneteng@gmail.com>

l10n: zh-TW: Git 2.45

Co-Authored-By: Lumynous <lumynou5.tw@gmail.com>
Co-Authored-By: Kisaragi Hiu <mail@kisaragi-hiu.com>
Signed-off-by: Yi-Jyun Pan <pan93412@gmail.com>

Merge branch 'update-teams' of https://github.com/Nekosha/git-po

* 'update-teams' of https://github.com/Nekosha/git-po:
  l10n: Update Vietnamese team contact

l10n: vi: Updated translation for 2.45

Signed-off-by: Vũ Tiến Hưng <newcomerminecraft@gmail.com>

l10n: TEAMS: retire l10n teams no update in 1 year

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>

Merge branch 'l10n/uk/2.45-uk-update'

* '2.45-uk-update' of github.com:arkid15r/git-ukrainian-l10n:
  l10n: uk: v2.45 update

Merge branch 'l10n-de-2.45' of github.com:ralfth/git

* 'l10n-de-2.45' of github.com:ralfth/git:
  l10n: Update German translation

Merge branch 'po-id' of github.com:bagasme/git-po

* 'po-id' of github.com:bagasme/git-po:
  l10n: po-id for 2.45

l10n: uk: v2.45 update

Co-authored-by: Kate Golovanova <kate@kgthreads.com>
Signed-off-by: Arkadii Yakovets <ark@cho.red>
Signed-off-by: Kate Golovanova <kate@kgthreads.com>

l10n: sv.po: Update Swedish translation

Also fix some inconsistencies, and fix issue reported by
Anders Jonsson <anders.jonsson@norsjovallen.se>.

Signed-off-by: Peter Krefting <peter@softwolves.pp.se>

l10n: Update German translation

Reviewed-by: Matthias Rüster <matthias.ruester@gmail.com>
Signed-off-by: Ralf Thielow <ralf.thielow@gmail.com>

l10n: po-id for 2.45

Translate following new components:

  * refs/reftable-backend.c

Update following components:

  * branch.c
  * builtin/column.c
  * builtin/config.c
  * builtin/for-each-ref.c
  * builtin/pack-refs.c
  * revision.c

Signed-off-by: Bagas Sanjaya <bagasdotme@gmail.com>

Merge branch 'rj/add-i-leak-fix'

Leakfix.

* rj/add-i-leak-fix:
  add: plug a leak on interactive_add
  add-patch: plug a leak handling the '/' command
  add-interactive: plug a leak in get_untracked_files
  apply: plug a leak in apply_data

Merge branch 'rs/vsnprintf-failure-is-not-a-bug'

Demote a BUG() to an die() when the failure from vsnprintf() may
not be due to a programmer error.

* rs/vsnprintf-failure-is-not-a-bug:
  don't report vsnprintf(3) error as bug

Documentation/RelNotes/2.45.0.txt: fix typo

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Git 2.45-rc1

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'ps/run-auto-maintenance-in-receive-pack'

The "receive-pack" program (which responds to "git push") was not
converted to run "git maintenance --auto" when other codepaths that
used to run "git gc --auto" were updated, which has been corrected.

* ps/run-auto-maintenance-in-receive-pack:
  builtin/receive-pack: convert to use git-maintenance(1)
  run-command: introduce function to prepare auto-maintenance process

Merge branch 'pk/bisect-use-show'

When "git bisect" reports the commit it determined to be the
culprit, we used to show it in a format that does not honor common
UI tweaks, like log.date and log.decorate.  The code has been
taught to use "git show" to follow more customizations.

* pk/bisect-use-show:
  bisect: report the found commit with "show"

A bit more topics before -rc1

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'rs/apply-reject-long-name'

The filename used for rejected hunks "git apply --reject" creates
was limited to PATH_MAX, which has been lifted.

* rs/apply-reject-long-name:
  apply: avoid using fixed-size buffer in write_out_one_reject()

Merge branch 'mr/rerere-crash-fix'

When .git/rr-cache/ rerere database gets corrupted or rerere is fed to
work on a file with conflicted hunks resolved incompletely, the rerere
machinery got confused and segfaulted, which has been corrected.

* mr/rerere-crash-fix:
  rerere: fix crashes due to unmatched opening conflict markers

Merge branch 'rs/imap-send-simplify-cmd-issuing-codepath'

Code simplification.

* rs/imap-send-simplify-cmd-issuing-codepath:
  imap-send: increase command size limit

Merge branch 'xx/rfc2822-date-format-in-doc'

Docfix.

* xx/rfc2822-date-format-in-doc:
  Documentation: fix typos describing date format

Merge branch 'ps/missing-btmp-fix'

GIt 2.44 introduced a regression that makes the updated code to
barf in repositories with multi-pack index written by older
versions of Git, which has been corrected.

* ps/missing-btmp-fix:
  pack-bitmap: gracefully handle missing BTMP chunks

Merge branch 'la/format-trailer-info'

The code to format trailers have been cleaned up.

* la/format-trailer-info:
  trailer: finish formatting unification
  trailer: begin formatting unification
  format_trailer_info(): append newline for non-trailer lines
  format_trailer_info(): drop redundant unfold_value()
  format_trailer_info(): use trailer_item objects

Merge branch 'dd/t9604-use-posix-timezones'

The cvsimport tests required that the platform understands
traditional timezone notations like CST6CDT, which has been
updated to work on those systems as long as they understand
POSIX notation with explicit tz transition dates.

* dd/t9604-use-posix-timezones:
  t9604: Fix test for musl libc and new Debian

Merge branch 'rj/launch-editor-error-message'

Git writes a "waiting for your editor" message on an incomplete
line after launching an editor, and then append another error
message on the same line if the editor errors out.  It now clears
the "waiting for..." line before giving the error message.

* rj/launch-editor-error-message:
  launch_editor: waiting message on error

Merge branch 'yb/replay-doc-linkfix'

Docfix.

* yb/replay-doc-linkfix:
  Documentation: fix linkgit reference

Merge branch 'rs/no-openssl-compilation-fix-on-macos'

Build fix.

* rs/no-openssl-compilation-fix-on-macos:
  git-compat-util: fix NO_OPENSSL on current macOS

Merge branch 'ta/fast-import-parse-path-fix'

The way "git fast-import" handles paths described in its input has
been tightened up and more clearly documented.

* ta/fast-import-parse-path-fix:
  fast-import: make comments more precise
  fast-import: forbid escaped NUL in paths
  fast-import: document C-style escapes for paths
  fast-import: improve documentation for path quoting
  fast-import: remove dead strbuf
  fast-import: allow unquoted empty path for root
  fast-import: directly use strbufs for paths
  fast-import: tighten path unquoting

Merge branch 'ps/reftable-block-iteration-optim'

The code to iterate over reftable blocks has seen some optimization
to reduce memory allocation and deallocation.

* ps/reftable-block-iteration-optim:
  reftable/block: avoid copying block iterators on seek
  reftable/block: reuse `zstream` state on inflation
  reftable/block: open-code call to `uncompress2()`
  reftable/block: reuse uncompressed blocks
  reftable/reader: iterate to next block in place
  reftable/block: move ownership of block reader into `struct table_iter`
  reftable/block: introduce `block_reader_release()`
  reftable/block: better grouping of functions
  reftable/block: merge `block_iter_seek()` and `block_reader_seek()`
  reftable/block: rename `block_reader_start()`

add: plug a leak on interactive_add

Plug a leak we have since 5a76aff1a6 (add: convert to use
parse_pathspec, 2013-07-14).

This leak can be triggered with:
    $ git add -p anything

Fixing this leak allows us to mark as leak-free the following tests:

    + t3701-add-interactive.sh
    + t7514-commit-patch.sh

Mark them with "TEST_PASSES_SANITIZE_LEAK=true" to notice and fix
promply any new leak that may be introduced and triggered by them in the
future.

Signed-off-by: Rubén Justo <rjusto@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

add-patch: plug a leak handling the '/' command

Plug a leak we have since d6cf873340 (built-in add -p: implement the '/'
("search regex") command, 2019-12-13).

This leak can be triggered with:

    $ printf "A\n\nB\n" >file
    $ git add file && git commit -m file
    $ printf "AA\n\nBB\n" >file
    $ printf "s\n/ .\n" >lines
    $ git add -p <lines

Signed-off-by: Rubén Justo <rjusto@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

add-interactive: plug a leak in get_untracked_files

Plug a leak we have since ab1e1cccaf (built-in add -i: re-implement
`add-untracked` in C, 2019-11-29).

This leak can be triggered with:

$ echo a | git add -i

As a curiosity, we have a somewhat similar function in builtin/stash.c,
which correctly frees the memory.

Signed-off-by: Rubén Justo <rjusto@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

apply: plug a leak in apply_data

We have an execution path in apply_data that leaks the local struct
image.  Plug it.

This leak can be triggered with:

    $ echo foo >file
    $ git add file && git commit -m file
    $ echo bar >file
    $ git diff file >diff
    $ sed s/foo/frotz/ <diff >baddiff
    $ git apply --cached <baddiff

Fixing this leak allows us to mark as leak-free the following tests:

    + t2016-checkout-patch.sh
    + t4103-apply-binary.sh
    + t4104-apply-boundary.sh
    + t4113-apply-ending.sh
    + t4117-apply-reject.sh
    + t4123-apply-shrink.sh
    + t4252-am-options.sh
    + t4258-am-quoted-cr.sh

Mark them with "TEST_PASSES_SANITIZE_LEAK=true" to notice and fix
promply any new leak that may be introduced and triggered by them in the
future.

Signed-off-by: Rubén Justo <rjusto@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

docs: address typos in Git v2.45 changelog

Address some typos in the Git v2.45 changelog.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

docs: improve changelog entry for `git pack-refs --auto`

The changelog entry for the new `git pack-refs --auto` mode only says
that the new flag is useful, but doesn't really say what it does. Add
some more information.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

docs: remove duplicate entry and fix typo in 2.45 changelog

Signed-off-by: Orgad Shaneh <orgads@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

don't report vsnprintf(3) error as bug

strbuf_addf() has been reporting a negative return value of vsnprintf(3)
as a bug since f141bd804d (Handle broken vsnprintf implementations in
strbuf, 2007-11-13).  Other functions copied that behavior:

7b03c89ebd (add xsnprintf helper function, 2015-09-24)
5ef264dbdb (strbuf.c: add `strbuf_insertf()` and `strbuf_vinsertf()`, 2019-02-25)
8d25663d70 (mem-pool: add mem_pool_strfmt(), 2024-02-25)

However, vsnprintf(3) can legitimately return a negative value if the
formatted output would be longer than INT_MAX.  Stop accusing it of
being broken and just report the fact that formatting failed.

Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

l10n: bg.po: Updated Bulgarian translation (5652t)

Signed-off-by: Alexander Shopov <ash@kambanaria.org>

l10n: fr: v2.45.0

Signed-off-by: Jean-Noël Avila <jn.avila@free.fr>

l10n: Update Vietnamese team contact

The previous team has not maintained the translation since 2.37. Leader
has agreed to transfer leadership to me.

Signed-off-by: Vũ Tiến Hưng <newcomerminecraft@gmail.com>

Git 2.45-rc0

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'la/mailmap-entry'

Update contact address for Linus Arver.

* la/mailmap-entry:
  mailmap: change primary address for Linus Arver

Merge branch 'pf/commitish-committish'

Spellfix.

* pf/commitish-committish:
  typo: replace 'commitish' with 'committish'

builtin/receive-pack: convert to use git-maintenance(1)

In 850b6edefa (auto-gc: extract a reusable helper from "git fetch",
2020-05-06), we have introduced a helper function `run_auto_gc()` that
kicks off `git gc --auto`. The intent of this function was to pass down
the "--quiet" flag to git-gc(1) as required without duplicating this at
all callsites. In 7c3e9e8cfb (auto-gc: pass --quiet down from am,
commit, merge and rebase, 2020-05-06) we then converted callsites that
need to pass down this flag to use the new helper function. This has the
notable omission of git-receive-pack(1), which is the only remaining
user of `git gc --auto` that sets up the proccess manually. This is
probably because it unconditionally passes down the `--quiet` flag and
thus didn't benefit much from the new helper function.

In a95ce12430 (maintenance: replace run_auto_gc(), 2020-09-17) we then
replaced `run_auto_gc()` with `run_auto_maintenance()` which invokes
git-maintenance(1) instead of git-gc(1). This command is the modern
replacement for git-gc(1) and is both more thorough and also more
flexible because administrators can configure which tasks exactly to run
during maintenance.

But due to git-receive-pack(1) not using `run_auto_gc()` in the first
place it did not get converted to use git-maintenance(1) like we do
everywhere else now. Address this oversight and start to use the newly
introduced function `prepare_auto_maintenance()`. This will also make it
easier for us to adapt this code together with all the other callsites
that invoke auto-maintenance in the future.

This removes the last internal user of `git gc --auto`.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

run-command: introduce function to prepare auto-maintenance process

The `run_auto_maintenance()` function is responsible for spawning a new
`git maintenance run --auto` process. To do so, it sets up the `sturct
child_process` and then runs it by executing `run_command()` directly.
This is rather inflexible in case callers want to modify the child
process somewhat, e.g. to redirect stderr or stdout.

Introduce a new `prepare_auto_maintenance()` function to plug this gap.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

mailmap: change primary address for Linus Arver

Linus will lose access to his work email soon.

Signed-off-by: Linus Arver <linusa@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

The twentieth batch

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'pw/t3428-cleanup'

Test cleanup.

* pw/t3428-cleanup:
  t3428: restore coverage for "apply" backend
  t3428: use test_commit_message
  t3428: modernize test setup

Merge branch 'ba/osxkeychain-updates'

Update osxkeychain backend with features required for the recent
credential subsystem.

* ba/osxkeychain-updates:
  osxkeychain: store new attributes
  osxkeychain: erase matching passwords only
  osxkeychain: erase all matching credentials
  osxkeychain: replace deprecated SecKeychain API

Merge branch 'jt/reftable-geometric-compaction'

The strategy to compact multiple tables of reftables after many
operations accumulate many entries has been improved to avoid
accumulating too many tables uncollected.

* jt/reftable-geometric-compaction:
  reftable/stack: use geometric table compaction
  reftable/stack: add env to disable autocompaction
  reftable/stack: expose option to disable auto-compaction

Merge branch 'tb/make-indent-conditional-with-non-spaces'

Adjust to an upcoming changes to GNU make that breaks our Makefiles.

* tb/make-indent-conditional-with-non-spaces:
  Makefile(s): do not enforce "all indents must be done with tab"
  Makefile(s): avoid recipe prefix in conditional statements

Merge branch 'rs/usage-fallback-to-show-message-format'

vreportf(), which is usede by error() and friends, has been taught
to give the error message printf-format string when its vsnprintf()
call fails, instead of showing nothing useful to identify the
nature of the error.

* rs/usage-fallback-to-show-message-format:
  usage: report vsnprintf(3) failure

Merge branch 'rs/date-mode-pass-by-value'

The codepaths that reach date_mode_from_type() have been updated to
pass "struct date_mode" by value to make them thread safe.

* rs/date-mode-pass-by-value:
  date: make DATE_MODE thread-safe

Merge branch 'sj/userdiff-c-sharp'

The userdiff patterns for C# has been updated.

Acked-by: Johannes Sixt <j6t@kdbg.org>
cf. <c2154457-3f2f-496e-9b8b-c8ea7257027b@kdbg.org>

* sj/userdiff-c-sharp:
  userdiff: better method/property matching for C#

Merge branch 'tb/t7700-fixup'

Test fix.

* tb/t7700-fixup:
  t/t7700-repack.sh: fix test breakages with `GIT_TEST_MULTI_PACK_INDEX=1 `

Merge branch 'jc/local-extern-shell-rules'

Document and apply workaround for a buggy version of dash that
mishandles "local var=val" construct.

* jc/local-extern-shell-rules:
  t1016: local VAR="VAL" fix
  t0610: local VAR="VAL" fix
  t: teach lint that RHS of 'local VAR=VAL' needs to be quoted
  t: local VAR="VAL" (quote ${magic-reference})
  t: local VAR="VAL" (quote command substitution)
  t: local VAR="VAL" (quote positional parameters)
  CodingGuidelines: quote assigned value in 'local var=$val'
  CodingGuidelines: describe "export VAR=VAL" rule

apply: avoid using fixed-size buffer in write_out_one_reject()

On some systems PATH_MAX is not a hard limit.  Support longer paths by
building them on the heap instead of using static buffers.

Take care to work around (arguably buggy) implementations of free(3)
that change errno by calling it only after using the errno value.

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

rerere: fix crashes due to unmatched opening conflict markers

When rerere handles a conflict with an unmatched opening conflict marker
in a file with other conflicts, it will fail create a preimage and also
fail allocate the status member of struct rerere_dir. Currently the
status member is allocated after the error handling. This will lead to a
SEGFAULT when the status member is accessed during cleanup of the failed
parse.

Additionally, in subsequent executions of rerere, after removing the
MERGE_RR.lock manually, rerere crashes for a similar reason. MERGE_RR
points to a conflict id that has no preimage, therefore the status
member is not allocated and a SEGFAULT happens when trying to check if a
preimage exists.

Solve this by making sure the status field is allocated correctly and add
tests to prevent the bug from reoccurring.

This does not fix the root cause, failing to parse stray conflict
markers, but I don't think we can do much better than recognizing it,
printing an error, and moving on gracefully.

Signed-off-by: Marcel Röthke <marcel@roethke.info>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

The ninteenth batch

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'jc/t2104-style-fixes'

Test style fixes.

* jc/t2104-style-fixes:
  t2104: style fixes

Merge branch 'jc/unleak-core-excludesfile'

The variable that holds the value read from the core.excludefile
configuration variable used to leak, which has been corrected.

* jc/unleak-core-excludesfile:
  config: do not leak excludes_file