tests: fix negated test_i18ngrep calls

The helper function test_i18ngrep pretends that it found the expected
results when it is running under GETTEXT_POISON. For this reason, it must
not be used negated like so

   ! test_i18ngrep foo bar

because the test case would fail under GETTEXT_POISON. The function offers
a special syntax to test that a pattern is *not* found:

   test_i18ngrep ! foo bar

Convert incorrect uses to this syntax.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Git 2.1

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.
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.
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.
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.
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).
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.99(1.97+0.01)   0.25(0.24+0.00) -87.4%    0.27(0.26+0.00) -86.4%
    7000.4: contains recent/v2.0.1    0.03(0.03+0.00)   0.00(0.00+0.00) -100.0%   0.03(0.02+0.00) +0.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.24+0.00)   0.03(0.03+0.00) -88.0%    0.25(0.24+0.00) +0.0%
    7000.7: contains ancient/all      0.82(0.80+0.01)   0.13(0.12+0.00) -84.1%    0.27(0.26+0.01) -67.1%
    7000.8: contains ancient/v2.0.1   0.26(0.26+0.00)   0.09(0.08+0.00) -65.4%    0.25(0.24+0.00) -3.8%

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.