prio_queue_reverse: don't swap elements with themselves
Our array-reverse algorithm does the usual "walk from both
ends, swapping elements". We can quit when the two indices
are equal, since:
1. Swapping an element with itself is a noop.
2. If i and j are equal, then in the next iteration i is
guaranteed to be bigge than j, and we will exit the
loop.
So exiting the loop on equality is slightly more efficient.
And more importantly, the new SWAP() macro does not expect
to handle noop swaps; it will call memcpy() with the same src
and dst pointers in this case. It's unclear whether that
causes a problem on any platforms by violating the
"overlapping memory" constraint of memcpy, but it does cause
valgrind to complain.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The test creates some unrelated commits in two separate repositories,
and then fetches from one to the other. Since the commit creation
happens in a subshell, the first commit in each ends up with the
same test_tick value. When fetch-pack looks at the two root commits
"unrelated1" and "new-too", the exact sequence of ACKs is different
depending on which one it pulls out of the queue first.
With the current code, it happens to be "unrelated1" (though this is not
at all guaranteed by the prio_queue data structure, it is deterministic
for this particular sequence of input). We see the ready-ACK, and the
test succeeds.
With the stable queue, we reliably get "new-too" out (since it is our
local tip, it is added to the queue before we even talk to the remote).
We never see a ready-ACK, and the test fails due to the grep on the
TRACE_PACKET output at the end (the fetch itself succeeds as expected).
I'm really not quite clear on what's supposed to be going on in the
test. I can make it pass with this change.
When we are traversing to find merge bases, we keep our
usual commit_list of commits to process, sorted by their
commit timestamp. As we add each parent to the list, we have
to spend "O(width of history)" to do the insertion, where
the width of history is the number of simultaneous lines of
development.
If we instead use a heap-based priority queue, we can do
these insertions in "O(log width)" time. This provides minor
speedups to merge-base calculations (timings in linux.git,
warm cache, best-of-five):
[before]
$ git merge-base HEAD v2.6.12
real 0m3.251s
user 0m3.148s
sys 0m0.104s
[after]
$ git merge-base HEAD v2.6.12
real 0m3.234s
user 0m3.108s
sys 0m0.128s
That's only an 0.5% speedup, but it does help protect us
against pathological cases.
While we are munging the "interesting" function, we also
take the opportunity to give it a more descriptive name, and
convert the return value to an int (we returned the first
interesting commit, but nobody ever looked at it).
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: make output stable with respect to insertion
If two items are added to a prio_queue and compare equal,
they currently come out in an apparently random order (this
order is deterministic for a particular sequence of
insertions and removals, but does not necessarily match the
insertion order). This makes it unlike using a date-ordered
commit_list, which is one of the main types we would like to
replace with it (because prio_queue does not suffer from
O(n) insertions).
We can make the priority queue stable by keeping an
insertion counter for each element, and using it to break
ties. This does increase the memory usage of the structure
(one int per element), but in practice it does not seem to
affect runtime. A best-of-five "git rev-list --topo-order"
on linux.git showed less than 1% difference (well within the
run-to-run noise).
In an ideal world, we would offer both stable and unstable
priority queues (the latter to try to maximize performance).
However, given the lack of a measurable performance
difference, it is not worth the extra code.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: factor out compare and swap operations
When manipulating the priority queue's heap, we frequently
have to compare and swap heap entries. As we are storing
only void pointers right now, this is quite easy to do
inline in a few lines. However, when we start using a more
complicated heap entry in a future patch, that will get
longer. Factoring out these operations lets us make future
changes in one place. It also makes the code a little
shorter and more readable.
Note that we actually accept indices into the queue array
instead of pointers. This is slightly less flexible than
passing pointers-to-pointers (we could not swap items from
unrelated arrays, but we would not want to), but will make
further refactoring simpler (and lets us avoid repeating
"queue->array" at each callsite, which led to some long
lines).
And finally, note that we are cleaning up an accidental use
of a "struct commit" pointer to hold a temporary entry
during swap. Even though we currently only use this code for
commits, it is supposed to be type-agnostic. In practice
this didn't matter anyway because we never dereferenced the
commit pointer (and on most systems, the pointer values
themselves are interchangeable between types).
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add 'verify-commit' to be used in a way similar to 'verify-tag' is
used. Further work on verifying the mergetags might be needed.
* mg/verify-commit:
t7510: test verify-commit
t7510: exit for loop with test result
verify-commit: scriptable commit signature verification
gpg-interface: provide access to the payload
gpg-interface: provide clear helper for struct signature_check
"git clone -b brefs/tags/bar" would have mistakenly thought we were
following a single tag, even though it was a name of the branch,
because it incorrectly used strstr().
* jc/fix-clone-single-starting-at-a-tag:
builtin/clone.c: detect a clone starting at a tag correctly
Merge branch 'jk/repack-pack-keep-objects' into maint
* jk/repack-pack-keep-objects:
repack: s/write_bitmap/&s/ in code
repack: respect pack.writebitmaps
repack: do not accidentally pack kept objects by default
* jk/pretty-G-format-fixes:
move "%G" format test from t7510 to t6006
pretty: avoid reading past end-of-string with "%G"
t7510: check %G* pretty-format output
t7510: test a commit signed by an unknown key
t7510: use consistent &&-chains in loop
t7510: stop referring to master in later tests
* jk/xstrfmt:
setup_git_env(): introduce git_path_from_env() helper
unique_path: fix unlikely heap overflow
walker_fetch: fix minor memory leak
merge: use argv_array when spawning merge strategy
sequencer: use argv_array_pushf
setup_git_env: use git_pathdup instead of xmalloc + sprintf
use xstrfmt to replace xmalloc + strcpy/strcat
use xstrfmt to replace xmalloc + sprintf
use xstrdup instead of xmalloc + strcpy
use xstrfmt in favor of manual size calculations
strbuf: add xstrfmt helper
* jk/skip-prefix:
http-push: refactor parsing of remote object names
imap-send: use skip_prefix instead of using magic numbers
use skip_prefix to avoid repeated calculations
git: avoid magic number with skip_prefix
fetch-pack: refactor parsing in get_ack
fast-import: refactor parsing of spaces
stat_opt: check extra strlen call
daemon: use skip_prefix to avoid magic numbers
fast-import: use skip_prefix for parsing input
use skip_prefix to avoid repeating strings
use skip_prefix to avoid magic numbers
transport-helper: avoid reading past end-of-string
fast-import: fix read of uninitialized argv memory
apply: use skip_prefix instead of raw addition
refactor skip_prefix to return a boolean
avoid using skip_prefix as a boolean
daemon: mark some strings as const
parse_diff_color_slot: drop ofs parameter
Add all of the ways in which check_refname_format violates valgrind's
expectations to the valgrind suppression file; remove an assumption about
the call chain of check_refname_format from same.
Signed-off-by: David Turner <dturner@twitter.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add the whole directory of test files at once using git add instead of
calling git update-index on each of them and use git commit instead of
the plumbing commands write-tree, update-ref and commit-tree to build
the commit. This simplifies the code considerably.
Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
'git checkout' fails if a directory is longer than PATH_MAX, because the
lstat_cache in symlinks.c checks if the leading directory exists using
PATH_MAX-bounded string operations.
Remove the limitation by using strbuf instead.
Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs.c: handle REFNAME_REFSPEC_PATTERN at end of page
When a ref crosses a memory page boundary, we restart the parsing
at the beginning with the bytewise code. Pass the original flags
to that code, rather than the current flags.
Reported-By: Øyvind A. Holm <sunny@sunbase.org> Signed-off-by: David Turner <dturner@twitter.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Move "commit->buffer" out of the in-core commit object and keep
track of their lengths. Use this to optimize the code paths to
validate GPG signatures in commit objects.
* jk/commit-buffer-length:
reuse cached commit buffer when parsing signatures
commit: record buffer length in cache
commit: convert commit->buffer to a slab
commit-slab: provide a static initializer
use get_commit_buffer everywhere
convert logmsg_reencode to get_commit_buffer
use get_commit_buffer to avoid duplicate code
use get_cached_commit_buffer where appropriate
provide helpers to access the commit buffer
provide a helper to set the commit buffer
provide a helper to free commit buffer
sequencer: use logmsg_reencode in get_message
logmsg_reencode: return const buffer
do not create "struct commit" with xcalloc
commit: push commit_index update into alloc_commit_node
alloc: include any-object allocations in alloc_report
replace dangerous uses of strbuf_attach
commit_tree: take a pointer/len pair rather than a const strbuf
If the middle step fails but leaves the directory (e.g., the
bug is that clean does not notice the failure), this
pollutes the test repo with an unremovable directory. Not
only does this cause further tests to fail, but it means
that "rm -rf" fails on the whole trash directory, and the
user has to intervene manually to even re-run the test script.
We can bump the "chmod 755" recovery to a test_when_finished
block to be sure that it always runs.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_file: avoid overrunning alternate object base string
While checking if a new alternate object database is a duplicate make
sure that old and new base paths have the same length before comparing
them with memcmp. This avoids overrunning the buffer of the existing
entry if the new one is longer and it stops rejecting foobar/ after
foo/ was already added.
Signed-off-by: Rene Scharfe <ls.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Instead of using a PATH_MAX buffer, use argv_array for constructing the
environment for git submodule summary. This simplifies the code a bit
and removes the arbitrary length limit.
Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
gitk: Add visiblerefs option, which lists always-shown branches
When many branches contain a commit, the branches used to be shown in
the form "A, B and many more", where A, B can be master of current
HEAD. But there are more which might be interesting to always know about.
For example, "origin/master".
The new option, visiblerefs, is stored in ~/.gitk. It contains a list
of references which are always shown before "and many more" if they
contain the commit. By default it is `{"master"}', which is compatible
with previous behavior.
Signed-off-by: Max Kirillov <max@max630.net> Signed-off-by: Paul Mackerras <paulus@samba.org>
105b5d3f ("gitk: Use mktemp -d to avoid predictable temporary
directories") introduced a dependency on mkdtemp, which is not
available on Windows.
Use the original temporary directory behavior when mkdtemp fails.
This makes the code use mkdtemp when available and gracefully
fallback to the existing behavior when it is not available.
Helped-by: Junio C Hamano <gitster@pobox.com> Helped-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: David Aguilar <davvid@gmail.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
Merge early parts from git://ozlabs.org/~paulus/gitk.git
* master~2:
gitk: Show staged submodules regardless of ignore config
gitk: Allow displaying time zones from author and commit dates timestamps
gitk: Switch to patch mode when searching for line origin
gitk: Replace SHA1 entry field on keyboard paste
l10n: Init Vietnamese translation
* git://repo.or.cz/git-gui:
git-gui: tolerate major version changes when comparing the git version
git-gui: show staged submodules regardless of ignore config
The final test in t7510 checks that "--format" placeholders
that look similar to GPG placeholders (but that we don't
actually understand) are passed through. That test was
placed in t7510, since the other GPG placeholder tests are
there. However, it does not have a GPG prerequisite, because
it is not actually checking any signed commits.
This causes the test to erroneously fail when gpg is not
installed on a system, however. Not because we need signed
commits, but because we need _any_ commit to run "git log".
If we don't have gpg installed, t7510 doesn't create any
commits at all.
We can fix this by moving the test into t6006. This is
arguably a better place anyway, because it is where we test
most of the other placeholders (we do not test GPG
placeholders there because of the infrastructure needed to
make signed commits).
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Some subcommands do not want to be aliased because of the side
effects that happens while the definitions of the aliases are looked
up from configuration system.
* nd/init-restore-env:
git potty: restore environments after alias expansion
Recent updates to "git repack" started to duplicate objects that
are in packfiles marked with .keep flag into the new packfile by
mistake.
* jk/repack-pack-keep-objects:
repack: s/write_bitmap/&s/ in code
repack: respect pack.writebitmaps
repack: do not accidentally pack kept objects by default
Merge branch 'jl/status-added-submodule-is-never-ignored' into maint
"git status" (and "git commit") behaved as if changes in a modified
submodule are not there if submodule.*.ignore configuration is set,
which was misleading. The configuration is only to unclutter diff
output during the course of development, and should not to hide
changes in the "status" output to cause the users forget to commit
them.
* jl/status-added-submodule-is-never-ignored:
commit -m: commit staged submodules regardless of ignore config
status/commit: show staged submodules regardless of ignore config
Merge branch 'ym/fix-opportunistic-index-update-race' into maint
"git status", even though it is a read-only operation, tries to
update the index with refreshed lstat(2) info to optimize future
accesses to the working tree opportunistically, but this could
race with a "read-write" operation that modify the index while it
is running. Detect such a race and avoid overwriting the index.
* ym/fix-opportunistic-index-update-race:
read-cache.c: verify index file before we opportunistically update it
wrapper.c: add xpread() similar to xread()
The autostash mode of "git rebase -i" did not restore the dirty
working tree state if the user aborted the interactive rebase by
emptying the insn sheet.
* rr/rebase-autostash-fix:
rebase -i: test "Nothing to do" case with autostash
rebase -i: handle "Nothing to do" case with autostash
"git log --exclude=<glob> --all | git shortlog" worked as expected,
but "git shortlog --exclude=<glob> --all", which is supposed to be
identical to the above pipeline, was not accepted at the command
line argument parser level.
* jc/shortlog-ref-exclude:
shortlog: allow --exclude=<glob> to be passed
"git remote rm" and "git remote prune" can involve removing many
refs at once, which is not a very efficient thing to do when very
many refs exist in the packed-refs file.
* jl/remote-rm-prune:
remote prune: optimize "dangling symref" check/warning
remote: repack packed-refs once when deleting multiple refs
remote rm: delete remote configuration as the last
Merge branch 'rs/pack-objects-no-unnecessary-realloc' into maint
"git pack-objects" unnecessarily copied the previous contents when
extending the hashtable, even though it will populate the table
from scratch anyway.
* rs/pack-objects-no-unnecessary-realloc:
pack-objects: use free()+xcalloc() instead of xrealloc()+memset()
Merge branch 'dt/merge-recursive-case-insensitive' into maint
On a case insensitive filesystem, merge-recursive incorrectly
deleted the file that is to be renamed to a name that is the same
except for case differences.
* dt/merge-recursive-case-insensitive:
mv: allow renaming to fix case on case insensitive filesystems
merge-recursive.c: fix case-changing merge bug
Merge branch 'nd/index-pack-one-fd-per-thread' into maint
We used to disable threaded "git index-pack" on platforms without
thread-safe pread(); use a different workaround for such
platforms to allow threaded "git index-pack".
* nd/index-pack-one-fd-per-thread:
index-pack: work around thread-unsafe pread()
Merge branch 'sk/spawn-less-case-insensitively-from-grep-O-i' into maint
"git grep -O" to show the lines that hit in the pager did not work
well with case insensitive search. We now spawn "less" with its
"-I" option when it is used as the pager (which is the default).
* sk/spawn-less-case-insensitively-from-grep-O-i:
git grep -O -i: if the pager is 'less', pass the '-I' option
"git gc --auto" was recently changed to run in the background to
give control back early to the end-user sitting in front of the
terminal, but it forgot that housekeeping involving reflogs should
be done without other processes competing for accesses to the refs.
* nd/daemonize-gc:
gc --auto: do not lock refs in the background
Merge branch 'jx/blame-align-relative-time' into maint
"git blame" miscounted number of columns needed to show localized
timestamps, resulting in jaggy left-side-edge of the source code
lines in its output.
* jx/blame-align-relative-time:
blame: dynamic blame_date_width for different locales
blame: fix broken time_buf paddings in relative timestamp
Merge branch 'jc/apply-ignore-whitespace' into maint
"--ignore-space-change" option of "git apply" ignored the spaces
at the beginning of line too aggressively, which is inconsistent
with the option of the same name "diff" and "git diff" have.
* jc/apply-ignore-whitespace:
apply --ignore-space-change: lines with and without leading whitespaces do not match
The completion scripts (in contrib/) did not know about quite a few
options that are common between "git merge" and "git pull", and a
couple of options unique to "git merge".
* jk/complete-merge-pull:
completion: add missing options for git-merge
completion: add a note that merge options are shared
The "%<(10,trunc)%s" pretty format specifier in the log family of
commands is used to truncate the string to a given length (e.g. 10
in the example) with padding to column-align the output, but did
not take into account that number of bytes and number of display
columns are different.
* as/pretty-truncate:
pretty.c: format string with truncate respects logOutputEncoding
t4205, t6006: add tests that fail with i18n.logOutputEncoding set
t4205 (log-pretty-format): use `tformat` rather than `format`
t4041, t4205, t6006, t7102: don't hardcode tested encoding value
t4205 (log-pretty-formats): don't hardcode SHA-1 in expected outputs
Merge branch 'jc/revision-dash-count-parsing' into maint
"git log -2master" is a common typo that shows two commits starting
from whichever random branch that is not 'master' that happens to
be checked out currently.
* jc/revision-dash-count-parsing:
revision: parse "git log -<count>" more carefully
Merge branch 'jk/report-fail-to-read-objects-better' into maint
Reworded the error message given upon a failure to open an existing
loose object file due to e.g. permission issues; it was reported as
the object being corrupt, but that is not quite true.
Tools that read diagnostic output in our standard error stream do
not want to see terminal control sequence (e.g. erase-to-eol).
Detect them by checking if the standard error stream is connected
to a tty.
* mn/sideband-no-ansi:
sideband.c: do not use ANSI control sequence on non-terminal
We used to unconditionally disable the pager in the pager process
we spawn to feed out output, but that prevented people who want to
run "less" within "less" from doing so.
* je/pager-do-not-recurse:
pager: do allow spawning pager recursively
"Check the value of an environment and fall back to a known path
inside $GIT_DIR" is repeated a few times to determine the location
of the data store, the index and the graft file, but the return
value of getenv is not guaranteed to survive across further
invocations of setenv or even getenv.
Make sure to xstrdup() the value we receive from getenv(3), and
encapsulate the pattern into a helper function.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
This mixes the "git verify-commit" tests in with the "git show
--show-signature" tests, to keep the tests more readable.
The tests already mix in the "call show" tests with the "verify" tests.
So in case of a test beakage, a '-v' run would be needed to reveal the
exact point of breakage anyway.
Additionally, test the actual output of "git verify-commit" and "git
show --show-signature" and compare to "git cat-file".
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Commit signatures can be verified using "git show -s --show-signature"
or the "%G?" pretty format and parsing the output, which is well suited
for user inspection, but not for scripting.
Provide a command "verify-commit" which is analogous to "verify-tag": It
returns 0 for good signatures and non-zero otherwise, has the gpg output
on stderr and (optionally) the commit object on stdout, sans the
signature, just like "verify-tag" does.
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
In contrast to tag signatures, commit signatures are put into the
header, that is between the other header parts and commit messages.
Provide access to the commit content sans the signature, which is the
payload that is actually signed. Commit signature verification does the
parsing anyways, and callers may wish to act on or display the commit
object sans the signature.
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
gpg-interface: provide clear helper for struct signature_check
The struct has been growing members whose malloced memory needs to be
freed. Do this with one helper function so that no malloced memory shall
be left unfreed.
Signed-off-by: Michael J Gruber <git@drmicha.warpmail.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>