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>
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>
"git stash --staged" errors out when given binary files, after saving the
stash.
This behaviour dates back to the addition of the feature in 41a28eb6c1
(stash: implement '--staged' option for 'push' and 'save', 2021-10-18).
Adding the "--binary" option of "diff-tree" fixes this. The "diff-tree" call
in stash_patch() also omits "--binary", but that is fine since binary files
cannot be selected interactively.
Helped-By: Jeff King <peff@peff.net>
Helped-By: Randall S. Becker <randall.becker@nexbridge.ca>
Signed-off-by: Adam Johnson <me@adamj.eu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>
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>
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>
Fix a bug that allows the "--rfc" and "-k" options to be specified together
when "git format-patch" is executed, which was introduced in the commit
e0d7db7423 ("format-patch: --rfc honors what --subject-prefix sets").
Add a couple of additional tests to t4014, to cover additional cases of
the mutual exclusivity between different "git format-patch" options.
Signed-off-by: Dragan Simic <dsimic@manjaro.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
* maint-2.43: (40 commits)
Git 2.43.4
Git 2.42.2
Git 2.41.1
Git 2.40.2
Git 2.39.4
fsck: warn about symlink pointing inside a gitdir
core.hooksPath: add some protection while cloning
init.templateDir: consider this config setting protected
clone: prevent hooks from running during a clone
Add a helper function to compare file contents
init: refactor the template directory discovery into its own function
find_hook(): refactor the `STRIP_EXTENSION` logic
clone: when symbolic links collide with directories, keep the latter
entry: report more colliding paths
t5510: verify that D/F confusion cannot lead to an RCE
submodule: require the submodule path to contain directories only
clone_submodule: avoid using `access()` on directories
submodules: submodule paths must not contain symlinks
clone: prevent clashing git dirs when cloning submodule in parallel
t7423: add tests for symlinked submodule directories
...
* maint-2.42: (39 commits)
Git 2.42.2
Git 2.41.1
Git 2.40.2
Git 2.39.4
fsck: warn about symlink pointing inside a gitdir
core.hooksPath: add some protection while cloning
init.templateDir: consider this config setting protected
clone: prevent hooks from running during a clone
Add a helper function to compare file contents
init: refactor the template directory discovery into its own function
find_hook(): refactor the `STRIP_EXTENSION` logic
clone: when symbolic links collide with directories, keep the latter
entry: report more colliding paths
t5510: verify that D/F confusion cannot lead to an RCE
submodule: require the submodule path to contain directories only
clone_submodule: avoid using `access()` on directories
submodules: submodule paths must not contain symlinks
clone: prevent clashing git dirs when cloning submodule in parallel
t7423: add tests for symlinked submodule directories
has_dir_name(): do not get confused by characters < '/'
...
* maint-2.41: (38 commits)
Git 2.41.1
Git 2.40.2
Git 2.39.4
fsck: warn about symlink pointing inside a gitdir
core.hooksPath: add some protection while cloning
init.templateDir: consider this config setting protected
clone: prevent hooks from running during a clone
Add a helper function to compare file contents
init: refactor the template directory discovery into its own function
find_hook(): refactor the `STRIP_EXTENSION` logic
clone: when symbolic links collide with directories, keep the latter
entry: report more colliding paths
t5510: verify that D/F confusion cannot lead to an RCE
submodule: require the submodule path to contain directories only
clone_submodule: avoid using `access()` on directories
submodules: submodule paths must not contain symlinks
clone: prevent clashing git dirs when cloning submodule in parallel
t7423: add tests for symlinked submodule directories
has_dir_name(): do not get confused by characters < '/'
docs: document security issues around untrusted .git dirs
...
* maint-2.40: (39 commits)
Git 2.40.2
Git 2.39.4
fsck: warn about symlink pointing inside a gitdir
core.hooksPath: add some protection while cloning
init.templateDir: consider this config setting protected
clone: prevent hooks from running during a clone
Add a helper function to compare file contents
init: refactor the template directory discovery into its own function
find_hook(): refactor the `STRIP_EXTENSION` logic
clone: when symbolic links collide with directories, keep the latter
entry: report more colliding paths
t5510: verify that D/F confusion cannot lead to an RCE
submodule: require the submodule path to contain directories only
clone_submodule: avoid using `access()` on directories
submodules: submodule paths must not contain symlinks
clone: prevent clashing git dirs when cloning submodule in parallel
t7423: add tests for symlinked submodule directories
has_dir_name(): do not get confused by characters < '/'
docs: document security issues around untrusted .git dirs
upload-pack: disable lazy-fetching by default
...
* maint-2.39: (38 commits)
Git 2.39.4
fsck: warn about symlink pointing inside a gitdir
core.hooksPath: add some protection while cloning
init.templateDir: consider this config setting protected
clone: prevent hooks from running during a clone
Add a helper function to compare file contents
init: refactor the template directory discovery into its own function
find_hook(): refactor the `STRIP_EXTENSION` logic
clone: when symbolic links collide with directories, keep the latter
entry: report more colliding paths
t5510: verify that D/F confusion cannot lead to an RCE
submodule: require the submodule path to contain directories only
clone_submodule: avoid using `access()` on directories
submodules: submodule paths must not contain symlinks
clone: prevent clashing git dirs when cloning submodule in parallel
t7423: add tests for symlinked submodule directories
has_dir_name(): do not get confused by characters < '/'
docs: document security issues around untrusted .git dirs
upload-pack: disable lazy-fetching by default
fetch/clone: detect dubious ownership of local repositories
...
This topic addresses two CVEs:
- CVE-2024-32020:
Local clones may end up hardlinking files into the target repository's
object database when source and target repository reside on the same
disk. If the source repository is owned by a different user, then
those hardlinked files may be rewritten at any point in time by the
untrusted user.
- CVE-2024-32021:
When cloning a local source repository that contains symlinks via the
filesystem, Git may create hardlinks to arbitrary user-readable files
on the same filesystem as the target repository in the objects/
directory.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
This topic branch adds a couple of measures designed to make it much
harder to exploit any bugs in Git's recursive clone machinery that might
be found in the future.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
In the wake of fixing a vulnerability where `git clone` mistakenly
followed a symbolic link that it had just written while checking out
files, writing into a gitdir, let's add some defense-in-depth by
teaching `git fsck` to report symbolic links stored in its trees that
point inside `.git/`.
Even though the Git project never made any promises about the exact
shape of the `.git/` directory's contents, there are likely repositories
out there containing symbolic links that point inside the gitdir. For
that reason, let's only report these as warnings, not as errors.
Security-conscious users are encouraged to configure
`fsck.symlinkPointsToGitDir = error`.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Quite frequently, when vulnerabilities were found in Git's (quite
complex) clone machinery, a relatively common way to escalate the
severity was to trick Git into running a hook which is actually a script
that has just been laid on disk as part of that clone. This constitutes
a Remote Code Execution vulnerability, the highest severity observed in
Git's vulnerabilities so far.
Some previously-fixed vulnerabilities allowed malicious repositories to
be crafted such that Git would check out files not in the worktree, but
in, say, a submodule's `<git>/hooks/` directory.
A vulnerability that "merely" allows to modify the Git config would
allow a related attack vector, to manipulate Git into looking in the
worktree for hooks, e.g. redirecting the location where Git looks for
hooks, via setting `core.hooksPath` (which would be classified as
CWE-427: Uncontrolled Search Path Element and CWE-114: Process Control,
for more details see https://cwe.mitre.org/data/definitions/427.html and
https://cwe.mitre.org/data/definitions/114.html).
To prevent that attack vector, let's error out and complain loudly if an
active `core.hooksPath` configuration is seen in the repository-local
Git config during a `git clone`.
There is one caveat: This changes Git's behavior in a slightly
backwards-incompatible manner. While it is probably a rare scenario (if
it exists at all) to configure `core.hooksPath` via a config in the Git
templates, it _is_ conceivable that some valid setup requires this to
work. In the hopefully very unlikely case that a user runs into this,
there is an escape hatch: set the `GIT_CLONE_PROTECTION_ACTIVE=false`
environment variable. Obviously, this should be done only with utmost
caution.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
The ability to configuring the template directory is a delicate feature:
It allows defining hooks that will be run e.g. during a `git clone`
operation, such as the `post-checkout` hook.
As such, it is of utmost importance that Git would not allow that config
setting to be changed during a `git clone` by mistake, allowing an
attacker a chance for a Remote Code Execution, allowing attackers to run
arbitrary code on unsuspecting users' machines.
As a defense-in-depth measure, to prevent minor vulnerabilities in the
`git clone` code from ballooning into higher-serverity attack vectors,
let's make this a protected setting just like `safe.directory` and
friends, i.e. ignore any `init.templateDir` entries from any local
config.
Note: This does not change the behavior of any recursive clone (modulo
bugs), as the local repository config is not even supposed to be written
while cloning the superproject, except in one scenario: If a config
template is configured that sets the template directory. This might be
done because `git clone --recurse-submodules --template=<directory>`
does not pass that template directory on to the submodules'
initialization.
Another scenario where this commit changes behavior is where
repositories are _not_ cloned recursively, and then some (intentional,
benign) automation configures the template directory to be used before
initializing the submodules.
So the caveat is that this could theoretically break existing processes.
In both scenarios, there is a way out, though: configuring the template
directory via the environment variable `GIT_TEMPLATE_DIR`.
This change in behavior is a trade-off between security and
backwards-compatibility that is struck in favor of security.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Critical security issues typically combine relatively common
vulnerabilities such as case confusion in file paths with other
weaknesses in order to raise the severity of the attack.
One such weakness that has haunted the Git project in many a
submodule-related CVE is that any hooks that are found are executed
during a clone operation. Examples are the `post-checkout` and
`fsmonitor` hooks.
However, Git's design calls for hooks to be disabled by default, as only
disabled example hooks are copied over from the templates in
`<prefix>/share/git-core/templates/`.
As a defense-in-depth measure, let's prevent those hooks from running.
Obviously, administrators can choose to drop enabled hooks into the
template directory, though, _and_ it is also possible to override
`core.hooksPath`, in which case the new check needs to be disabled.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
In the next commit, Git will learn to disallow hooks during `git clone`
operations _except_ when those hooks come from the templates (which are
inherently supposed to be trusted). To that end, we add a function to
compare the contents of two files.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
When rebasing with "--signoff" the commit created by "rebase --continue"
after resolving conflicts or editing a commit fails to add the
"Signed-off-by:" trailer. This happens because the message from the
original commit is reused instead of the one that would have been used
if the sequencer had not stopped for the user interaction. The correct
message is stored in ctx->message and so with a couple of exceptions
this is written to rebase_path_message() when stopping for user
interaction instead. The exceptions are (i) "fixup" and "squash"
commands where the file is written by error_failed_squash() and (ii)
"edit" commands that are fast-forwarded where the original message is
still reused. The latter is safe because "--signoff" will never
fast-forward.
Note this introduces a change in behavior as the message file now
contains conflict comments. This is safe because commit_staged_changes()
passes an explicit cleanup flag when not editing the message and when
the message is being edited it will be cleaned up automatically. This
means user now sees the same message comments in editor with "rebase
--continue" as they would if they ran "git commit" themselves before
continuing the rebase. It also matches the behavior of "git
cherry-pick", "git merge" etc. which all list the files with merge
conflicts.
The tests are extended to check that all commits made after continuing a
rebase have a "Signed-off-by:" trailer. Sadly there are a couple of
leaks in apply.c which I've not been able to track down that mean this
test file is no-longer leak free when testing "git rebase --apply
--signoff" with conflicts.
Reported-by: David Bimmler <david.bimmler@isovalent.com>
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add an strbuf to "struct replay_ctx" to hold the current commit
message. This does not change the behavior but it will allow us to fix a
bug with "git rebase --signoff" in the next commit. A future patch
series will use the changes here to avoid writing the commit message to
disc unless there are conflicts or the commit is being reworded.
The changes in do_pick_commit() are a mechanical replacement of "msgbuf"
with "ctx->message". In do_merge() the code to write commit message to
disc is factored out of the conditional now that both branches store the
message in the same buffer.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The list of current fixups is an implementation detail of the sequencer
and so it should not be stored in the public options struct.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
"struct replay_opts" has a number of fields that are for internal
use. While they are marked as private having them in a public struct is
a distraction for callers and means that every time the internal details
are changed we have to recompile all the files that include sequencer.h
even though the public API is unchanged. This commit starts the process
of removing the private fields by adding an opaque pointer to a "struct
replay_ctx" to "struct replay_opts" and moving the "reflog_message"
member to the new private struct.
The sequencer currently updates the state files on disc each time it
processes a command in the todo list. This is an artifact of the
scripted implementation and makes the code hard to reason about as it is
not possible to get a complete view of the state in memory. In the
future we will add new members to "struct replay_ctx" to remedy this and
avoid writing state to disc unless the sequencer stops for user
interaction.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sequencer_post_commit_cleanup() initializes an instance of "struct
replay_opts" but does not call replay_opts_release(). Currently this
does not leak memory because the code paths called don't allocate any of
the struct members. That will change in the next commit so add call to
replay_opts_release() to prevent a memory leak in "git commit" that
breaks all of the leak free tests.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
This topic branch fixes two vulnerabilities:
- Recursive clones on case-insensitive filesystems that support symbolic
links are susceptible to case confusion that can be exploited to
execute just-cloned code during the clone operation.
- Repositories can be configured to execute arbitrary code during local
clones. To address this, the ownership checks introduced in v2.30.3
are now extended to cover cloning local repositories.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
We will need to call this function from `hook.c` to be able to prevent
hooks from running that were written as part of a `clone` but did not
originate from the template directory.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
When looking for a hook and not finding one, and when `STRIP_EXTENSION`
is available (read: if we're on Windows and `.exe` is the required
extension for executable programs), we want to look also for a hook with
that extension.
Previously, we added that handling into the conditional block that was
meant to handle when no hook was found (possibly providing some advice
for the user's benefit). If the hook with that file extension was found,
we'd return early from that function instead of writing out said advice,
of course.
However, we're about to introduce a safety valve to prevent hooks from
being run during a clone, to reduce the attack surface of bugs that
allow writing files to be written into arbitrary locations.
To prepare for that, refactor the logic to avoid the early return, by
separating the `STRIP_EXTENSION` handling from the conditional block
handling the case when no hook was found.
This commit is best viewed with `--patience`.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
When recursively cloning a repository with submodules, we must ensure
that the submodules paths do not suddenly contain symbolic links that
would let Git write into unintended locations. We just plugged that
vulnerability, but let's add some more defense-in-depth.
Since we can only keep one item on disk if multiple index entries' paths
collide, we may just as well avoid keeping a symbolic link (because that
would allow attack vectors where Git follows those links by mistake).
Technically, we handle more situations than cloning submodules into
paths that were (partially) replaced by symbolic links. This provides
defense-in-depth in case someone finds a case-folding confusion
vulnerability in the future that does not even involve submodules.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
In b878579ae7 (clone: report duplicate entries on case-insensitive
filesystems, 2018-08-17) code was added to warn about index entries that
resolve to the same file system entity (usually the cause is a
case-insensitive filesystem).
In Git for Windows, where inodes are not trusted (because of a
performance trade-off, inodes are equal to 0 by default), that check
does not compare inode numbers but the verbatim path.
This logic works well when index entries' paths differ only in case.
However, for file/directory conflicts only the file's path was reported,
leaving the user puzzled with what that path collides.
Let's try ot catch colliding paths even if one path is the prefix of the
other. We do this also in setups where the file system is case-sensitive
because the inode check would not be able to catch those collisions.
While not a complete solution (for example, on macOS, Unicode
normalization could also lead to file/directory conflicts but be missed
by this logic), it is at least another defensive layer on top of what
the previous commits added.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
The most critical vulnerabilities in Git lead to a Remote Code Execution
("RCE"), i.e. the ability for an attacker to have malicious code being
run as part of a Git operation that is not expected to run said code,
such has hooks delivered as part of a `git clone`.
A couple of parent commits ago, a bug was fixed that let Git be confused
by the presence of a path `a-` to mistakenly assume that a directory
`a/` can safely be created without removing an existing `a` that is a
symbolic link.
This bug did not represent an exploitable vulnerability on its
own; Let's make sure it stays that way.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Submodules are stored in subdirectories of their superproject. When
these subdirectories have been replaced with symlinks by a malicious
actor, all kinds of mayhem can be caused.
This _should_ not be possible, but many CVEs in the past showed that
_when_ possible, it allows attackers to slip in code that gets executed
during, say, a `git clone --recursive` operation.
Let's add some defense-in-depth to disallow submodule paths to have
anything except directories in them.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
In 0060fd1511 (clone --recurse-submodules: prevent name squatting on
Windows, 2019-09-12), I introduced code to verify that a git dir either
does not exist, or is at least empty, to fend off attacks where an
inadvertently (and likely maliciously) pre-populated git dir would be
used while cloning submodules recursively.
The logic used `access(<path>, X_OK)` to verify that a directory exists
before calling `is_empty_dir()` on it. That is a curious way to check
for a directory's existence and might well fail for unwanted reasons.
Even the original author (it was I ;-) ) struggles to explain why this
function was used rather than `stat()`.
This code was _almost_ copypastad in the previous commit, but that
`access()` call was caught during review.
Let's use `stat()` instead also in the code that was almost copied
verbatim. Let's not use `lstat()` because in the unlikely event that
somebody snuck a symbolic link in, pointing to a crafted directory, we
want to verify that that directory is empty.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
When creating a submodule path, we must be careful not to follow
symbolic links. Otherwise we may follow a symbolic link pointing to
a gitdir (which are valid symbolic links!) e.g. while cloning.
On case-insensitive filesystems, however, we blindly replace a directory
that has been created as part of the `clone` operation with a symlink
when the path to the latter differs only in case from the former's path.
Let's simply avoid this situation by expecting not ever having to
overwrite any existing file/directory/symlink upon cloning. That way, we
won't even replace a directory that we just created.
This addresses CVE-2024-32002.
Reported-by: Filip Hejsek <filip.hejsek@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
While it is expected to have several git dirs within the `.git/modules/`
tree, it is important that they do not interfere with each other. For
example, if one submodule was called "captain" and another submodule
"captain/hooks", their respective git dirs would clash, as they would be
located in `.git/modules/captain/` and `.git/modules/captain/hooks/`,
respectively, i.e. the latter's files could clash with the actual Git
hooks of the former.
To prevent these clashes, and in particular to prevent hooks from being
written and then executed as part of a recursive clone, we introduced
checks as part of the fix for CVE-2019-1387 in a8dee3ca61 (Disallow
dubiously-nested submodule git directories, 2019-10-01).
It is currently possible to bypass the check for clashing submodule
git dirs in two ways:
1. parallel cloning
2. checkout --recurse-submodules
Let's check not only before, but also after parallel cloning (and before
checking out the submodule), that the git dir is not clashing with
another one, otherwise fail. This addresses the parallel cloning issue.
As to the parallel checkout issue: It requires quite a few manual steps
to create clashing git dirs because Git itself would refuse to
initialize the inner one, as demonstrated by the test case.
Nevertheless, let's teach the recursive checkout (namely, the
`submodule_move_head()` function that is used by the recursive checkout)
to be careful to verify that it does not use a clashing git dir, and if
it does, disable it (by deleting the `HEAD` file so that subsequent Git
calls won't recognize it as a git dir anymore).
Note: The parallel cloning test case contains a `cat err` that proved to
be highly useful when analyzing the racy nature of the operation (the
operation can fail with three different error messages, depending on
timing), and was left on purpose to ease future debugging should the
need arise.
Signed-off-by: Filip Hejsek <filip.hejsek@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Submodule operations must not follow symlinks in working tree, because
otherwise files might be written to unintended places, leading to
vulnerabilities.
Signed-off-by: Filip Hejsek <filip.hejsek@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
There is a bug in directory/file ("D/F") conflict checking optimization:
It assumes that such a conflict cannot happen if a newly added entry's
path is lexicgraphically "greater than" the last already-existing index
entry _and_ contains a directory separator that comes strictly after the
common prefix (`len > len_eq_offset`).
This assumption is incorrect, though: `a-` sorts _between_ `a` and
`a/b`, their common prefix is `a`, the slash comes after the common
prefix, and there is still a file/directory conflict.
Let's re-design this logic, taking these facts into consideration:
- It is impossible for a file to sort after another file with whose
directory it conflicts because the trailing NUL byte is always smaller
than any other character.
- Since there are quite a number of ASCII characters that sort before
the slash (e.g. `-`, `.`, the space character), looking at the last
already-existing index entry is not enough to determine whether there
is a D/F conflict when the first character different from the
existing last index entry's path is a slash.
If it is not a slash, there cannot be a file/directory conflict.
And if the existing index entry's first different character is a
slash, it also cannot be a file/directory conflict because the
optimization requires the newly-added entry's path to sort _after_ the
existing entry's, and the conflicting file's path would not.
So let's fall back to the regular binary search whenever the newly-added
item's path differs in a slash character. If it does not, and it sorts
after the last index entry, there is no D/F conflict and the new index
entry can be safely appended.
This fix also nicely simplifies the logic and makes it much easier to
reason about, while the impact on performance should be negligible:
After this fix, the optimization will be skipped only when index
entry's paths differ in a slash and a space, `!`, `"`, `#`, `$`,
`%`, `&`, `'`, | ( `)`, `*`, `+`, `,`, `-`, or `.`, which should
be a rare situation.
Signed-off-by: Filip Hejsek <filip.hejsek@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Rubén Justo