dir.c: use the cache_* macro to access the current index

These codepaths always start from the_index and use index_*
functions, but there is no reason to do so.  Use the compatibility
cache_* macro to access the current in-core index like everybody
else.

While at it, fix typo in the comment for a function to check if a
path within a directory appears in the index.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
ls-files -k: a directory only can be killed if the index has a non-directory

"ls-files -o" and "ls-files -k" both traverse the working tree down
to find either all untracked paths or those that will be "killed"
(removed from the working tree to make room) when the paths recorded
in the index are checked out.  It is necessary to traverse the
working tree fully when enumerating all the "other" paths, but when
we are only interested in "killed" paths, we can take advantage of
the fact that paths that do not overlap with entries in the index
can never be killed.

The treat_one_path() helper function, which is called during the
recursive traversal, is the ideal place to implement an
optimization.

When we are looking at a directory P in the working tree, there are
three cases:

 (1) P exists in the index.  Everything inside the directory P in
     the working tree needs to go when P is checked out from the
     index.

 (2) P does not exist in the index, but there is P/Q in the index.
     We know P will stay a directory when we check out the contents
     of the index, but we do not know yet if there is a directory
     P/Q in the working tree to be killed, so we need to recurse.

 (3) P does not exist in the index, and there is no P/Q in the index
     to require P to be a directory, either.  Only in this case, we
     know that everything inside P will not be killed without
     recursing.

Note that this helper is called by treat_leading_path() that decides
if we need to traverse only subdirectories of a single common
leading directory, which is essential for this optimization to be
correct.  This caller checks each level of the leading path
component from shallower directory to deeper ones, and that is what
allows us to only check if the path appears in the index.  If the
call to treat_one_path() weren't there, given a path P/Q/R, the real
traversal may start from directory P/Q/R, even when the index
records P as a regular file, and we would end up having to check if
any leading subpath in P/Q/R, e.g. P, appears in the index.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3010: update to demonstrate "ls-files -k" optimization pitfalls

An earlier draft of the previous step used cache_name_exists() to
check the directory we were looking at, which missed the second case
described in its log message.  Demonstrate why it is not sufficient.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
move setup_alternate_shallow and write_shallow_commits to shallow.c

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
dir.c::test_one_path(): work around directory_exists_in_index_icase() breakage

directory_exists_in_index() takes pathname and its length, but its
helper function directory_exists_in_index_icase() reads one byte
beyond the end of the pathname and expects there to be a '/'.

This needs to be fixed, as that one-byte-beyond-the-end location may
not even be readable, possibly by not registering directories to
name hashes with trailing slashes.  In the meantime, update the new
caller added recently to treat_one_path() to make sure that the path
buffer it gives the function is one byte longer than the path it is
asking the function about by appending a slash to it.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
shallow: only add shallow graft points to new shallow file

for_each_commit_graft() goes through all graft points, and shallow
boundaries are just one special kind of grafting.

If $GIT_DIR/shallow and $GIT_DIR/info/grafts are both present,
write_shallow_commits() may catch both sets, accidentally turning
some graft points to shallow boundaries.  Don't do that.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
shallow: add setup_temporary_shallow()

This function is like setup_alternate_shallow() except that it does
not lock $GIT_DIR/shallow.  It is supposed to be used when a program
generates temporary shallow for use by another program, then throw
the shallow file away.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
upload-pack: delegate rev walking in shallow fetch to pack-objects

upload-pack has a special revision walking code for shallow
recipients. It works almost like the similar code in pack-objects
except:

1. in upload-pack, graft points could be added for deepening;

2. also when the repository is deepened, the shallow point will be
   moved further away from the tip, but the old shallow point will be
   marked as edge to produce more efficient packs. See 6523078 (make
   shallow repository deepening more network efficient - 2009-09-03).

Pass the file to pack-objects via --shallow-file. This will override
$GIT_DIR/shallow and give pack-objects the exact repository shape
that upload-pack has.

mark edge commits by revision command arguments. Even if old shallow
points are passed as "--not" revisions as in this patch, they will not
be picked up by mark_edges_uninteresting() because this function looks
up to parents for edges, while in this case the edge is the children,
in the opposite direction. This will be fixed in an later patch when
all given uninteresting commits are marked as edges.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
list-objects: reduce one argument in mark_edges_uninteresting

mark_edges_uninteresting() is always called with this form

  mark_edges_uninteresting(revs->commits, revs, ...);

Remove the first argument and let mark_edges_uninteresting figure that
out by itself. It helps answer the question "are this commit list and
revs related in any way?" when looking at mark_edges_uninteresting
implementation.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
list-objects: mark more commits as edges in mark_edges_uninteresting

The purpose of edge commits is to let pack-objects know what objects
it can use as base, but does not need to include in the thin pack
because the other side is supposed to already have them. So far we
mark uninteresting parents of interesting commits as edges. But even
an unrelated uninteresting commit (that the other side has) may
become a good base for pack-objects and help produce more efficient
packs.

This is especially true for shallow clone, when the client issues a
fetch with a depth smaller or equal to the number of commits the
server is ahead of the client. For example, in this commit history
the client has up to "A" and the server has up to "B":

    -------A---B
     have--^   ^
              /
       want--+

If depth 1 is requested, the commit list to send to the client
includes only B. The way m_e_u is working, it checks if parent
commits of B are uninteresting, if so mark them as edges.  Due to
shallow effect, commit B is grafted to have no parents and the
revision walker never sees A as the parent of B. In fact it marks no
edges at all in this simple case and sends everything B has to the
client even if it could have excluded what A and also the client
already have.

In a slightly different case where A is not a direct parent of B
(iow there are commits in between A and B), marking A as an edge can
still save some because B may still have stuff from the far ancestor
A.

There is another case from the earlier patch, when we deepen a ref
from C->E to A->E:

    ---A---B   C---D---E
     want--^   ^       ^
       shallow-+      /
          have-------+

In this case we need to send A and B to the client, and C (i.e. the
current shallow point that the client informs the server) is a very
good base because it's closet to A and B. Normal m_e_u won't recognize
C as an edge because it only looks back to parents (i.e. A<-B) not the
opposite way B->C even if C is already marked as uninteresting commit
by the previous patch.

This patch includes all uninteresting commits from command line as
edges and lets pack-objects decide what's best to do. The upside is we
have better chance of producing better packs in certain cases. The
downside is we may need to process some extra objects on the server
side.

For the shallow case on git.git, when the client is 5 commits behind
and does "fetch --depth=3", the result pack is 99.26 KiB instead of
4.92 MiB.

Reported-and-analyzed-by: Matthijs Kooijman <matthijs@stdin.nl>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add testcase for needless objects during a shallow fetch

This is a testcase that checks for a problem where, during a specific
shallow fetch where the client does not have any commits that are a
successor of the new shallow root (i.e., the fetch creates a new
detached piece of history), the server would simply send over _all_
objects, instead of taking into account the objects already present in
the client.

The actual problem was fixed by a recent patch series by Nguyễn Thái
Ngọc Duy already.

Signed-off-by: Matthijs Kooijman <matthijs@stdin.nl>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t2024: Fix &&-chaining and a couple of typos

Improved-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3200: Minor fix when preparing for tracking failure

We're testing that trying to --track a ref that is not covered by any remote
refspec should fail. For that, we want to have refs/remotes/local/master
present, but we also want the remote.local.fetch refspec to NOT match
refs/remotes/local/master (so that the tracking setup will fail, as intended).
However, when doing "git fetch local" to ensure the existence of
refs/remotes/local/master, we must not already have changed remote.local.fetch
so as to cause refs/remotes/local/master not to be fetched. Therefore, set
remote.local.fetch to refs/heads/*:refs/remotes/local/* BEFORE we fetch, and
then reset it to refs/heads/s:refs/remotes/local/s AFTER we have fetched
(but before we test --track).

Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Refer to branch.<name>.remote/merge when documenting --track

Make it easier for readers to find the actual config variables that
implement the "upstream" relationship.

Suggested-by: Per Cederqvist <cederp@opera.com>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3200: Add test demonstrating minor regression in 41c21f2

In 41c21f2 (branch.c: Validate tracking branches with refspecs instead of
refs/remotes/*), we changed the rules for what is considered a valid tracking
branch (a.k.a. upstream branch). We now use the configured remotes and their
refspecs to determine whether a proposed tracking branch is in fact within
the domain of a remote, and we then use that information to deduce the
upstream configuration (branch.<name>.remote and branch.<name>.merge).

However, with that change, we also check that - in addition to a matching
refspec - the result of mapping the tracking branch through that refspec
(i.e. the corresponding ref name in the remote repo) happens to start with
"refs/heads/". In other words, we require that a tracking branch refers to
a _branch_ in the remote repo.

Now, consider that you are e.g. setting up an automated building/testing
infrastructure for a group of similar "source" repositories. The build/test
infrastructure consists of a central scheduler, and a number of build/test
"slave" machines that perform the actual build/test work. The scheduler
monitors the group of similar repos for changes (e.g. with a periodic
"git fetch"), and triggers builds/tests to be run on one or more slaves.
Graphically the changes flow between the repos like this:

  Source #1 -------v          ----> Slave #1
                             /
  Source #2 -----> Scheduler -----> Slave #2
                             \
  Source #3 -------^          ----> Slave #3

        ...                           ...

The scheduler maintains a single Git repo with each of the source repos set
up as distinct remotes. The slaves also need access to all the changes from
all of the source repos, so they pull from the scheduler repo, but using the
following custom refspec:

  remote.origin.fetch = "+refs/remotes/*:refs/remotes/*"

This makes all of the scheduler's remote-tracking branches automatically
available as identical remote-tracking branches in each of the slaves.

Now, consider what happens if a slave tries to create a local branch with
one of the remote-tracking branches as upstream:

  git branch local_branch --track refs/remotes/source-1/some_branch

Git now looks at the configured remotes (in this case there is only "origin",
pointing to the scheduler's repo) and sees refs/remotes/source-1/some_branch
matching origin's refspec. Mapping through that refspec we find that the
corresponding remote ref name is "refs/remotes/source-1/some_branch".
However, since this remote ref name does not start with "refs/heads/", we
discard it as a suitable upstream, and the whole command fails.

This patch adds a testcase demonstrating this failure by creating two
source repos ("a" and "b") that are forwarded through a scheduler ("c")
to a slave repo ("d"), that then tries create a local branch with an
upstream. See the next patch in this series for the exciting conclusion
to this story...

Reported-by: Per Cederqvist <cederp@opera.com>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
branch.c: Relax unnecessary requirement on upstream's remote ref name

When creating an upstream relationship, we use the configured remotes and
their refspecs to determine the upstream configuration settings
branch.<name>.remote and branch.<name>.merge. However, if the matching
refspec does not have refs/heads/<something> on the remote side, we end
up rejecting the match, and failing the upstream configuration.

It could be argued that when we set up an branch's upstream, we want that
upstream to also be a proper branch in the remote repo. Although this is
typically the common case, there are cases (as demonstrated by the previous
patch in this series) where this requirement prevents a useful upstream
relationship from being formed. Furthermore:

 - We have fundamentally no say in how the remote repo have organized its
   branches. The remote repo may put branches (or branch-like constructs
   that are insteresting for downstreams to track) outside refs/heads/*.

 - The user may intentionally want to track a non-branch from a remote
   repo, by using a branch and configured upstream in the local repo.

Relaxing the checking to only require a matching remote/refspec allows the
testcase introduced in the previous patch to succeed, and has no negative
effect on the rest of the test suite.

This patch fixes a behavior (arguably a regression) first introduced in
41c21f2 (branch.c: Validate tracking branches with refspecs instead of
refs/remotes/*) on 2013-04-21 (released in >= v1.8.3.2).

Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3200: fix failure on case-insensitive filesystems

62d94a3a (t3200: Add test demonstrating minor regression in 41c21f2;
2013-09-08) introduced a test which creates a directory named 'a',
however, on case-insensitive filesystems, this action fails with a
"fatal: cannot mkdir a: File exists" error due to a file named 'A' left
over from earlier tests. Resolve this problem.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'nd/fetch-into-shallow' into maint

When there is no sufficient overlap between old and new history
during a "git fetch" into a shallow repository, objects that the
sending side knows the receiving end has were unnecessarily sent.

* nd/fetch-into-shallow:
  Add testcase for needless objects during a shallow fetch
  list-objects: mark more commits as edges in mark_edges_uninteresting
  list-objects: reduce one argument in mark_edges_uninteresting
  upload-pack: delegate rev walking in shallow fetch to pack-objects
  shallow: add setup_temporary_shallow()
  shallow: only add shallow graft points to new shallow file
  move setup_alternate_shallow and write_shallow_commits to shallow.c
Merge branch 'jh/checkout-auto-tracking' into maint

"git branch --track" had a minor regression in v1.8.3.2 and later
that made it impossible to base your local work on anything but a
local branch of the upstream repository you are tracking from.

* jh/checkout-auto-tracking:
  t3200: fix failure on case-insensitive filesystems
  branch.c: Relax unnecessary requirement on upstream's remote ref name
  t3200: Add test demonstrating minor regression in 41c21f2
  Refer to branch.<name>.remote/merge when documenting --track
  t3200: Minor fix when preparing for tracking failure
  t2024: Fix &&-chaining and a couple of typos
Merge branch 'jc/ls-files-killed-optim' into maint

"git ls-files -k" needs to crawl only the part of the working tree
that may overlap the paths in the index to find killed files, but
shared code with the logic to find all the untracked files, which
made it unnecessarily inefficient.

* jc/ls-files-killed-optim:
  dir.c::test_one_path(): work around directory_exists_in_index_icase() breakage
  t3010: update to demonstrate "ls-files -k" optimization pitfalls
  ls-files -k: a directory only can be killed if the index has a non-directory
  dir.c: use the cache_* macro to access the current index