replace: replace spaces with tabs in indentation

This matches our usual style and the surrounding code.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
avoid double close of descriptors handed to run_command

When a file descriptor is given to run_command via the
"in", "out", or "err" parameters, run_command takes
ownership. The descriptor will be closed in the parent
process whether the process is spawned successfully or not,
and closing it again is wrong.

In practice this has not caused problems, because we usually
close() right after start_command returns, meaning no other
code has opened a descriptor in the meantime. So we just get
EBADF and ignore it (rather than accidentally closing
somebody else's descriptor!).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: use argv_array in export_object

This is a little more verbose, but will make it easier to
make parts of our command-line conditional (without
resorting to magic numbers or lots of NULLs to get an
appropriately sized argv array).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add a --raw mode for --edit

One of the purposes of "git replace --edit" is to help a
user repair objects which are malformed or corrupted.
Usually we pretty-print trees with "ls-tree", which is much
easier to work with than the raw binary data.  However, some
forms of corruption break the tree-walker, in which case our
pretty-printing fails, rendering "--edit" useless for the
user.

This patch introduces a "--raw" option, which lets you edit
the binary data in these instances.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
wt-status: use argv_array for environment

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>
wt-status: simplify building of summary limit argument

Use argv_array_pushf for building the number string for the option
--summary-limit directly instead of using an intermediate buffer.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tag: allow --sort with -n

When we are listing tags, we print each one as it is
processed by for_each_ref. We can't do that with --sort, of
course, as we need to see the whole list to sort. For the
--sort code path, we store each tag in a string_list, and
then print them all at the end.

This interacts badly with "-n", which needs not only the
name of the tag, but also the object itself. We simply
punted on handling this, and disallowed the combination.

This patch remedies that by storing the sha1 of each object
in the "util" field of the string list. We can then factor
out the printing to a helper function and call that function
either when we first see each tag, or after we have sorted.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tag: factor out decision to stream tags

Right now we stream tags if we are not sorting. If we are
sorting, we save them in a list and print them at the end.
Let's abstract this decision into a function to make it
easier to add more cases where we use the list.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
paint_down_to_common: use prio_queue

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.

The downside is that our priority queue is not stable, which
means that commits with the same timestamp may not come out
in the order we put them in. You can see this in the test
update in t6024. That test does a recursive merge across a
set of commits that all have the same timestamp. For the
virtual ancestor, the test currently ends up with blob like
this:

    <<<<<<< Temporary merge branch 1
    <<<<<<< Temporary merge branch 1
    C
    =======
    B
    >>>>>>> Temporary merge branch 2
    =======
    A
    >>>>>>> Temporary merge branch 2

but with this patch, the positions of B and A are swapped.
This is probably fine, as the order is an internal
implementation detail anyway (it would _not_ be fine if we
were using a priority queue for "git log" traversal, which
should show commits in parent order).

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>
add functions for memory-efficient bitmaps

We already have a nice-to-use bitmap implementation in
ewah/bitmap.c. It pretends to be infinitely long when asking
for a bit (and just returns 0 for bits that haven't been
allocated or set), and dynamically resizes as appropriate
when you set bits.

The cost to this is that each bitmap must store its own
pointer and length, using up to 16 bytes per bitmap on top
of the actual bit storage. This is a lot of storage (not to
mention an extra level of pointer indirection) if you are
going to store one bitmap per commit in a traversal.

These functions provide an alternative bitmap implementation
that can be used when you have a large number of fixed-size
bitmaps. See the documentation in the header file for
details and examples.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
string-list: add pos to iterator callback

When we are running a string-list foreach or filter, the
callback function sees only the string_list_item, along with
a void* data pointer provided by the caller. This is
sufficient for most purposes.

However, it can also be useful to know the position of the
item within the string (for example, if the data pointer
points to a secondary array in which each element
corresponds to part of the string list). We can help this
use case by providing the position to each callback.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit: provide a fast multi-tip contains function

When commands like "git branch --contains" want to know
which branches contain a particular commit, they run a
series of merge-base calculations, one per branch. This can
be very slow if you have a large number of branches.

We made "tag --contains" faster in ffc4b80 (tag: speed up
--contains calculation, 2011-06-11) by switching to a
different algorithm that caches intermediate "contains"
information from each tag we check. The downside of the new
algorithm is that it moves depth-first through the graph. So
it tends to go all the way to the roots, even if the
contained commit is near the top of history. That works OK
for tags, because repositories tend to have tags near the
roots anyway (e.g., a v0.1 or similar). The number of
commits we look at increased a little bit, but since we
avoid traversing over the same parts of history repeatedly,
it was a huge net win.

For "branch --contains", it is less clear that this is a
win. Most branches stay up to date, so we can bound a search
for a recent commit when we hit the merge base between the
commit and the branches.

The ideal would be to use the merge-base-style breadth-first
traversal, but to perform a single traversal for all tips.
The problem is that we need one bit of storage per tip in
each commit, and "struct commit" has only a fixed number of
bits. We can solve that by using a process similar to
paint_down_to_common, but instead of storing PARENT1 and
PARENT2 flags, using a commit slab to store one bit per tip.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tag: use commit_contains

The newly added commit_contains function should do a better
job than our custom depth-first traversal. It should be the
same speed when going close to the roots, but much faster
when all tags are close to the searched-for commit (this
usually isn't the case, but could be if you limit the tags
with a pattern).

It also cleans up some of the more egregious pitfalls of the
original implementation, including an abuse of the
UNINTERESTING and TMP_MARK flags, an utterly confusing
calling convention (it silently caches the bits between
calls, with no checks that our "with_commit" was the same
for each call), and a failure to clean up after itself
(tainting any further traversals).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
perf: add tests for tag --contains

These tests can demonstrate the changes in "tag --contains"
speed over time. The interesting points in history are:

  - pre-ffc4b80, where we used a series of N merge-base
    traversals

  - ffc4b80 up to the current master, where we moved to a
    single depth-first traversal

  - the previous commit, where we moved from depth-first to
    a multi-tip merge-base

The interesting cases to measure are:

  - checking which tags contain a recent commit (we use
    HEAD~100 here)

  - checking which tags contain a very ancient commit (we
    use the last commit output by rev-list)

  - checking which tags contain a commit in the middle (we
    use HEAD~5000, which goes back 5 years in git.git)

  - all of the above, but instead of looking at all commits,
    considering only recent ones (we pick the most recent
    tag by its tagger date)

Here are the timings for git.git:

    Test                              ffc4b80^          origin/master             HEAD
    ----------------------------------------------------------------------------------------------------
    7000.3: contains recent/all       1.97(1.96+0.01)   0.26(0.25+0.00) -86.8%    0.27(0.26+0.00) -86.3%
    7000.4: contains recent/v2.0.1    0.08(0.08+0.00)   0.25(0.24+0.01) +212.5%   0.02(0.02+0.00) -75.0%
    7000.5: contains old/all          0.90(0.89+0.00)   0.18(0.17+0.00) -80.0%    0.27(0.26+0.00) -70.0%
    7000.6: contains old/v2.0.1       0.25(0.23+0.02)   0.03(0.03+0.00) -88.0%    0.25(0.24+0.00) +0.0%
    7000.7: contains ancient/all      1.98(1.97+0.01)   0.26(0.24+0.01) -86.9%    0.28(0.25+0.02) -85.9%
    7000.8: contains ancient/v2.0.1   1.95(1.94+0.00)   0.26(0.24+0.01) -86.7%    0.27(0.26+0.00) -86.2%

You can see that ffc4b80 vastly improved the normal case of
checking all tags. This is because we avoid walking over the
same parts of history over and over. However, when looking
only for a recent tag (v2.0.1 in these tests), it sometimes
performs much worse than the original. This is not
surprising. For a merge-base solution, we can quit when we
hit history shared between the contained commit and the tag.
For ffc4b80's depth-first approach, we typically go all the
way to the roots before backtracking. For the ancient/v2.0.1
case, that's not a big deal, because the merge base requires
us doing that anyway. But for recent/v2.0.1, the merge-base
answer should involve only recent history.

The new traversal code performs about as well as the
depth-first code in the normal case, but fixes the
regression in the recent/v2.0.1 case.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
submodule.c: use the ARRAY_SIZE macro

Use the ARRAY_SIZE macro to get the number
of elements in an array.

Signed-off-by: Elia Pinto <gitter.spiros@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
implement submodule config cache for lookup of submodule names

This submodule configuration cache allows us to lazily read .gitmodules
configurations by commit into a runtime cache which can then be used to
easily lookup values from it. Currently only the values for path or name
are stored but it can be extended for any value needed.

It is expected that .gitmodules files do not change often between
commits. Thats why we lookup the .gitmodules sha1 from a commit and then
either lookup an already parsed configuration or parse and cache an
unknown one for each sha1. The cache is lazily build on demand for each
requested commit.

This cache can be used for all purposes which need knowledge about
submodule configurations. Example use cases are:

 * Recursive submodule checkout needs lookup a submodule name from its
   path when a submodule first appears. This needs be done before this
   configuration exists in the worktree.

 * The implementation of submodule support for 'git archive' needs to
   lookup the submodule name to generate the archive when given a
   revision that is not checked out.

 * 'git fetch' when given the --recurse-submodules=on-demand option (or
   configuration) needs to lookup submodule names by path from the
   database rather than reading from the worktree. For new submodule it
   needs to lookup the name from its path to allow cloning new
   submodules into the .git folder so they can be checked out without
   any network interaction when the user does a checkout of that
   revision.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
extract functions for submodule config set and lookup

This is one step towards using the new configuration API. We just
extract these functions to make replacing the actual code easier.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
use new config API for worktree configurations of submodules

We remove the extracted functions and directly parse into and read out
of the cache. This allows us to have one unified way of accessing
submodule configuration values specific to single submodules. Regardless
whether we need to access a configuration from history or from the
worktree.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
do not die on error of parsing fetchrecursesubmodules option

We should not die when reading the submodule config cache since the user
might not be able to get out of that situation when the configuration is
part of the history.

We should handle this condition later when the value is about to be
used.

Signed-off-by: Heiko Voigt <hvoigt@hvoigt.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_file: replace PATH_MAX buffer with strbuf in prepare_packed_git_one()

Instead of using strbuf to create a message string in case a path is
too long for our fixed-size buffer, replace that buffer with a strbuf
and thus get rid of the limitation.

Helped-by: Duy Nguyen <pclouds@gmail.com>
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>