refs: change do_for_each_*() functions to take ref_cache arguments

Change the callers convert submodule names into ref_cache pointers.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: handle the main ref_cache specially

Hold the ref_cache instance for the main repository in a dedicated,
statically-allocated instance to avoid the need for a function call
and a linked-list traversal when it is needed.

Suggested by: Heiko Voigt <hvoigt@hvoigt.net>

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
lookup_object: prioritize recently found objects

The lookup_object function is backed by a hash table of all
objects we have seen in the program. We manage collisions
with a linear walk over the colliding entries, checking each
with hashcmp(). The main cost of lookup is in these
hashcmp() calls; finding our item in the first slot is
cheaper than finding it in the second slot, which is cheaper
than the third, and so on.

If we assume that there is some locality to the object
lookups (e.g., if X and Y collide, and we have just looked
up X, the next lookup is more likely to be for X than for
Y), then we can improve our average lookup speed by checking
X before Y.

This patch does so by swapping a found item to the front of
the collision chain. The p0001 perf test reveals that this
does indeed exploit locality in the case of "rev-list --all
--objects":

Test                               origin          this tree
-------------------------------------------------------------------------
0001.1: rev-list --all             0.40(0.38+0.02) 0.40(0.36+0.03) +0.0%
0001.2: rev-list --all --objects   2.24(2.17+0.05) 1.86(1.79+0.05) -17.0%

This is not surprising, as the full object traversal will
hit the same tree entries over and over (e.g., for every
commit that doesn't change "Documentation/", we will have to
look up the same sha1 just to find out that we already
processed it).

The reason why this technique works (and does not violate
any properties of the hash table) is subtle and bears some
explanation. Let's imagine we get a lookup for sha1 `X`, and
it hashes to bucket `i` in our table. That stretch of the
table may look like:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  B  |  C  |  X  | ...
       -----------------------------------

We start our probe at i, see that B does not match, nor does
C, and finally find X. There may be multiple C's in the
middle, but we know that there are no empty slots (or else
we would not find X at all).

We do not know the original index of B; it may be `i`, or it
may be less than i (e.g., if it were `i-1`, it would collide
with A and spill over into the `i` bucket). So it is
acceptable for us to move it to the right of a contiguous
stretch of entries (because we will find it from a linear
walk starting anywhere at `i` or before), but never to the
left (if we moved it to `i-1`, we would miss it when
starting our walk at `i`).

We do know the original index of X; it is `i`, so it is safe
to place it anywhere in the contiguous stretch between `i`
and where we found it (`i+2` in the this case).

This patch does a pure swap; after finding X in the
situation above, we would end with:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  X  |  C  |  B  | ...
       -----------------------------------

We could instead bump X into the `i` slot, and then shift
the whole contiguous chain down by one, resulting in:

index       | i-1 |  i  | i+1 | i+2 |
       -----------------------------------
entry   ... |  A  |  X  |  B  |  C  | ...
       -----------------------------------

That puts our chain in true most-recently-used order.
However, experiments show that it is not any faster (and in
fact, is slightly slower due to the extra manipulation).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/Makefile: don't define TEST_RESULTS_DIRECTORY recursively

Commit 54bb901 (t/Makefile: fix result handling with
TEST_OUTPUT_DIRECTORY - 2013-04-26) incorrectly defined
TEST_RESULTS_DIRECTORY relative to itself, when it should be relative to
TEST_OUTPUT_DIRECTORY.  Fix this.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fast-export: do not parse non-commit objects while reading marks file

We read from the marks file and keep only marked commits, but in
order to find the type of object, we are parsing the whole thing,
which is slow, specially in big repositories with lots of big files.

There's no need for that, we can query the object information with
sha1_object_info().

Before this, loading the objects of a fresh emacs import, with 260598
blobs took 14 minutes, after this patch, it takes 3 seconds.

This is the way fast-import does it. Also die if the object is not
found (like fast-import).

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fast-export: don't parse commits while reading marks file

We don't need the parsed objects at this point, merely the
information that they have marks.

Seems to be three times faster in my setup with lots of objects.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
clone: allow cloning local paths with colons in them

Usually "foo:bar" is interpreted as an ssh url. This patch allows to
clone from such paths by putting at least one slash before the colon
(i.e. /path/to/foo:bar or just ./foo:bar).

file://foo:bar should also work, but local optimizations are off in
that case, which may be unwanted. While at there, warn the users about
--local being ignored in this case.

Reported-by: William Giokas <1007380@gmail.com>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fast-{import,export}: use get_sha1_hex() to read from marks file

It's wrong to call get_sha1() if they should be SHA-1s, plus
inefficient.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: at-combinations: simplify setup

The test is setting up an upstream branch, but there's a much simpler
way of doing that: git branch -u.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: at-combinations: check ref names directly

Some committishes might point to the same commit, but through a
different ref, that's why it's better to check directly for the ref,
rather than the commit message.

We can do that by calling rev-parse --symbolic-full-name, and to
differentiate the old from the new behavior we add an extra argument to
the check() helper.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: at-combinations: improve nonsense()

In some circumstances 'git log' might fail, but not because the @
parsing failed. For example: 'git rev-parse' might succeed and return a
bad object, and then 'git log' would fail.

The layer we want to test is revision parsing, so let's test that
directly.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: at-combinations: increase coverage

Add more tests exercising documented functionality.

[fc: commit message and extra tests]

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: at-combinations: @{N} versus HEAD@{N}

All the tests so far check that @{N} is the same as HEAD@{N} (for
positive N). However, this is not always the case; write a couple of
tests for this.

[fc: simplify some wording]

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_name: remove no-op

'at' is always 0, since we can reach this point only if
!len && reflog_len, and len=at when reflog is assigned.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_name: remove unnecessary braces

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_name: don't waste cycles in the @-parsing loop

The @-parsing loop unnecessarily checks for the sequence "@{" from
(len - 2) unnecessarily.  We can safely check from (len - 4).

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
completion: cleanup zsh wrapper

There's no need for a separate function; we can call
'emulate -k ksh func'.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
completion: synchronize zsh wrapper

So it's closer to the full zsh wrapper.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_name: reorganize get_sha1_basic()

Through the years the functionality to handle @{-N} and @{u} has moved
around the code, and as a result, code that once made sense, doesn't any
more.

There is no need to call this function recursively with the branch of
@{-N} substituted because dwim_{ref,log} already replaces it.

However, there's one corner-case where @{-N} resolves to a detached
HEAD, in which case we wouldn't get any ref back.

So we parse the nth-prior manually, and deal with it depending on
whether it's a SHA-1, or a ref.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_name: check @{-N} errors sooner

It's trivial to check for them in the @{N} parsing loop.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>