merge: a random object may not necssarily be a commit

The user could have said "git merge $(git rev-parse v1.0.0)"; we
shouldn't mark it as "Merge commit '15999998fb...'" as the merge
name, even though such an invocation might be crazy.

We could even read the "tag " header from the tag object and replace
the object name the user gave us, but let's not lose the information
by doing so, at least not yet.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: coalesce lost lines optimally

This replaces the greedy implementation to coalesce lost lines by using
dynamic programming to find the Longest Common Subsequence.

The O(n²) time complexity is obviously bigger than previous
implementation but it can produce shorter diff results (and most likely
easier to read).

List of lost lines is now doubly-linked because we reverse-read it when
reading the direction matrix.

Signed-off-by: Antoine Pelisse <apelisse@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Make core.sharedRepository work under cygwin 1.7

When core.sharedRepository is used, set_shared_perm() in path.c
needs lstat() to return the correct POSIX permissions.

The default for cygwin is core.ignoreCygwinFSTricks = false, which
means that the fast implementation in do_stat() is used instead of
lstat().

lstat() under cygwin uses the Windows security model to implement
POSIX-like permissions.  The user, group or everyone bits can be set
individually.

do_stat() simplifes the file permission bits, and may return a wrong
value.  The read-only attribute of a file is used to calculate the
permissions, resulting in either rw-r--r-- or r--r--r--

One effect of the simplified do_stat() is that t1301 fails.

Add a function cygwin_get_st_mode_bits() which returns the POSIX
permissions.  When not compiling for cygwin, true_mode_bits() in
path.c is used.

Side note:

t1301 passes under cygwin 1.5.

The "user write" bit is synchronized with the "read only" attribute
of a file:

    $ chmod 444 x
    $ attrib x
    A    R     C:\temp\pt\x

    cygwin 1.7 would show
    A          C:\temp\pt\x

Signed-off-by: Torsten Bögershausen <tboegi@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_file: remove recursion in packed_object_info

packed_object_info() and packed_delta_info() were mutually recursive.
The former would handle ordinary types and defer deltas to the latter;
the latter would use the former to resolve the delta base.

This arrangement, however, leads to trouble with threaded index-pack
and long delta chains on platforms where thread stacks are small, as
happened on OS X (512kB thread stacks by default) with the chromium
repo.

The task of the two functions is not all that hard to describe without
any recursion, however.  It proceeds in three steps:

- determine the representation type and size, based on the outermost
  object (delta or not)

- follow through the delta chain, if any

- determine the object type from what is found at the end of the delta
  chain

The only complication stems from the error recovery.  If parsing fails
at any step, we want to mark that object (within the pack) as bad and
try getting the corresponding SHA1 from elsewhere.  If that also
fails, we want to repeat this process back up the delta chain until we
find a reasonable solution or conclude that there is no way to
reconstruct the object.  (This is conveniently checked by t5303.)

To achieve that within the pack, we keep track of the entire delta
chain in a stack.  When things go sour, we process that stack from the
top, marking entries as bad and attempting to re-resolve by sha1.  To
avoid excessive malloc(), the stack starts out with a small
stack-allocated array.  The choice of 64 is based on the default of
pack.depth, which is 50, in the hope that it covers "most" delta
chains without any need for malloc().

It's much harder to make the actual re-resolving by sha1 nonrecursive,
so we skip that.  If you can't afford *that* recursion, your
corruption problems are more serious than your stack size problems.

Reported-by: Stefan Zager <szager@google.com>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
attr.c::path_matches(): the basename is part of the pathname

The function takes two strings (pathname and basename) as if they
are independent strings, but in reality, the latter is always
pointing into a substring in the former.

Clarify this relationship by expressing the latter as an offset into
the former.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
checkout: avoid unnecessary match_pathspec calls

In checkout_paths() we do this

 - for all updated items, call match_pathspec
 - for all items, call match_pathspec (inside unmerge_cache)
 - for all items, call match_pathspec (for showing "path .. is unmerged)
 - for updated items, call match_pathspec and update paths

That's a lot of duplicate match_pathspec(s) and the function is not
exactly cheap to be called so many times, especially on large indexes.
This patch makes it call match_pathspec once per updated index entry,
save the result in ce_flags and reuse the results in the following
loops.

The changes in 0a1283b (checkout $tree $path: do not clobber local
changes in $path not in $tree - 2011-09-30) limit the affected paths
to ones we read from $tree. We do not do anything to other modified
entries in this case, so the "for all items" above could be modified
to "for all updated items". But..

The command's behavior now is modified slightly: unmerged entries that
match $path, but not updated by $tree, are now NOT touched.  Although
this should be considered a bug fix, not a regression. A new test is
added for this change.

And while at there, free ps_matched after use.

The following command is tested on webkit, 215k entries. The pattern
is chosen mainly to make match_pathspec sweat:

git checkout -- "*[a-zA-Z]*[a-zA-Z]*[a-zA-Z]*"

        before      after
real    0m3.493s    0m2.737s
user    0m2.239s    0m1.586s
sys     0m1.252s    0m1.151s

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Refactor parts of in_delta_base_cache/cache_or_unpack_entry

The delta base cache lookup and test were shared.  Refactor them;
we'll need both parts again.  Also, we'll use the clearing routine
later.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1_file: remove recursion in unpack_entry

Similar to the recursion in packed_object_info(), this leads to
problems on stack-space-constrained systems in the presence of long
delta chains.

We proceed in three phases:

1. Dig through the delta chain, saving each delta object's offsets and
   size on an ad-hoc stack.

2. Unpack the base object at the bottom.

3. Unpack and apply the deltas from the stack.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
stream_blob_to_fd: detect errors reading from stream

We call read_istream, but never check its return value for
errors. This can lead to us looping infinitely, as we just
keep trying to write "-1" bytes (and we do not notice the
error, as we simply check that write_in_full reports the
same number of bytes we fed it, which of course is also -1).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
check_sha1_signature: check return value from read_istream

It's possible for read_istream to return an error, in which
case we just end up in an infinite loop (aside from EOF, we
do not even look at the result, but just feed it straight
into our running hash).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
read_istream_filtered: propagate read error from upstream

The filter istream pulls data from an "upstream" stream,
running it through a filter function. However, we did not
properly notice when the upstream filter yielded an error,
and just returned what we had read. Instead, we should
propagate the error.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
avoid infinite loop in read_istream_loose

The read_istream_loose function loops on inflating a chunk of data
from an mmap'd loose object. We end the loop when we run out
of space in our output buffer, or if we see a zlib error.

We need to treat Z_BUF_ERROR specially, though, as it is not
fatal; it is just zlib's way of telling us that we need to
either feed it more input or give it more output space. It
is perfectly normal for us to hit this when we are at the
end of our buffer.

However, we may also get Z_BUF_ERROR because we have run out
of input. In a well-formed object, this should not happen,
because we have fed the whole mmap'd contents to zlib. But
if the object is truncated or corrupt, we will loop forever,
never giving zlib any more data, but continuing to ask it to
inflate.

We can fix this by considering it an error when zlib returns
Z_BUF_ERROR but we still have output space left (which means
it must want more input, which we know is a truncation
error). It would not be sufficient to just check whether
zlib had consumed all the input at the start of the loop, as
it might still want to generate output from what is in its
internal state.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add test for streaming corrupt blobs

We do not have many tests for handling corrupt objects. This
new test at least checks that we detect a byte error in a
corrupt blob object while streaming it out with cat-file.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
streaming_write_entry: propagate streaming errors

When we are streaming an index blob to disk, we store the
error from stream_blob_to_fd in the "result" variable, and
then immediately overwrite that with the return value of
"close". That means we catch errors on close (e.g., problems
committing the file to disk), but miss anything which
happened before then.

We can fix this by using bitwise-OR to accumulate errors in
our result variable.

While we're here, we can also simplify the error handling
with an early return, which makes it easier to see under
which circumstances we need to clean up.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for cloning corrupted repositories

We try not to let corruption pass unnoticed over fetches and
clones. For the most part, this works, but there are some
broken corner cases, including:

  1. We do not detect missing objects over git-aware
     transports. This is a little hard to test, because the
     sending side will actually complain about the missing
     object.

     To fool it, we corrupt a repository such that we have a
     "misnamed" object: it claims to be sha1 X, but is
     really Y. This lets the sender blindly transmit it, but
     it is the receiver's responsibility to verify that what
     it got is sane (and it does not).

  2. We do not detect missing or misnamed blobs during the
     checkout phase of clone.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
clone: die on errors from unpack_trees

When clone is populating the working tree, it ignores the
return status from unpack_trees; this means we may report a
successful clone, even when the checkout fails.

When checkout fails, we may want to leave the $GIT_DIR in
place, as it might be possible to recover the data through
further use of "git checkout" (e.g., if the checkout failed
due to a transient error, disk full, etc). However, we
already die on a number of other checkout-related errors, so
this patch follows that pattern.

In addition to marking a now-passing test, we need to adjust
t5710, which blindly assumed it could make bogus clones of
very deep alternates hierarchies. By using "--bare", we can
avoid it actually touching any objects.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
clone: run check_everything_connected

When we fetch from a remote, we do a revision walk to make
sure that what we received is connected to our existing
history. We do not do the same check for clone, which should
be able to check that we received an intact history graph.

The upside of this patch is that it will make clone more
resilient against propagating repository corruption. The
downside is that we will now traverse "rev-list --objects
--all" down to the roots, which may take some time (it is
especially noticeable for a "--local --bare" clone).

Note that we need to adjust t5710, which tries to make such
a bogus clone. Rather than checking after the fact that our
clone is bogus, we can simplify it to just make sure "git
clone" reports failure.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
log: read gpg settings for signed commit verification

"show --show-signature" and "log --show-signature" do not read the
gpg.program setting from git config, even though, commit signing,
tag signing, and tag verification honor it.

Signed-off-by: Jacob Sarvis <jsarvis@openspan.com>
Signed-off-by: Hans Brigman <hbrigman@openspan.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Avoid loading commits twice in log with diffs

If you run a log with diffs (such as -p, --raw, --stat etc.) the
current code ends up loading many objects twice.  For example, for
'log -3000 -p' my instrumentation said the objects loaded more than
once are distributed as follows:

  2008 blob
  2103 commit
  2678 tree

Fixing blobs and trees will be harder, because those are really used
within the diff engine and need some form of caching.

However, fixing the commits is easy at least at the band-aid level.
They are triggered by log_tree_diff() invoking diff_tree_sha1() on
commits, which duly loads the specified object to dereference it to a
tree.  Since log_tree_diff() knows that it works with commits and they
must have trees, we can simply pass through the trees.

We add some parse_commit() calls.  The ones for the parents are
required; we do not know at this stage if they have been looked at.
The one for the commit itself is pure paranoia, but has about the same
cost as an assertion on commit->object.parsed.

This has a quite dramatic effect on log --raw, though only a
negligible impact on log -p:

Test                      this tree         HEAD
--------------------------------------------------------------------
4000.2: log --raw -3000   0.50(0.43+0.06)   0.54(0.46+0.06) +7.0%***
4000.3: log -p -3000      2.34(2.20+0.13)   2.37(2.22+0.13) +1.2%
--------------------------------------------------------------------
Significance hints:  '.' 0.1  '*' 0.05  '**' 0.01  '***' 0.001

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
attr.c::path_matches(): special case paths that end with a slash

The function is given a string that ends with a slash to signal that
the path is a directory to make sure that a pattern that ends with a
slash (i.e. MUSTBEDIR) can tell directories and non-directories
apart.  However, the pattern itself (pat->pattern and
pat->patternlen) that came from such a MUSTBEDIR pattern is
represented as a string that ends with a slash, but patternlen does
not count that trailing slash. A MUSTBEDIR pattern "element/" is
represented as a counted string <"element/", 7> and this must match
match pathname "element/".

Because match_basename() and match_pathname() want to see pathname
"element" to match against the pattern <"element/", 7>, reduce the
length of the path to exclude the trailing slash when calling
these functions.

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