test-sha1: add a binary output mode

The test-sha1 helper program will run our internal sha1
routines over its input and output the 40-byte hex sha1.
Sometimes, however, it is useful to have the binary 20-byte
sha1 (and it's a pain to convert back in the shell). Let's
add a "-b" option to output the binary version.

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

The sha1_entry_pos function tries to be smart about
selecting the middle of a range for its binary search by
looking at the value differences between the "lo" and "hi"
constraints. However, it is unable to cope with entries with
duplicate keys in the sorted list.

We may hit a point in the search where both our "lo" and
"hi" point to the same key. In this case, the range of
values between our endpoints is 0, and trying to scale the
difference between our key and the endpoints over that range
is undefined (i.e., divide by zero). The current code
catches this with an "assert(lov < hiv)".

Moreover, after seeing that the first 20 byte of the key are
the same, we will try to establish a value from the 21st
byte. Which is nonsensical.

Instead, we can detect the case that we are in a run of
duplicates, and simply do a final comparison against any one
of them (since they are all the same, it does not matter
which). If the keys match, we have found our entry (or one
of them, anyway).  If not, then we know that we do not need
to look further, as we must be in a run of the duplicate
key.

Furthermore, we know that one of our endpoints must be
the edge of the run of duplicates. For example, given this
sequence:

 idx 0 1 2 3 4 5
 key A C C C C D

If we are searching for "B", we might hit the duplicate run
at lo=1, hi=3 (e.g., by first mi=3, then mi=0). But we can
never have lo > 1, because B < C. That is, if our key is
less than the run, we know that "lo" is the edge, but we can
say nothing of "hi". Similarly, if our key is greater than
the run, we know that "hi" is the edge, but we can say
nothing of "lo". But that is enough for us to return not
only "not found", but show the position at which we would
insert the new item.

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for indexing packs with delta cycles

If we receive a broken or malicious pack from a remote, we
will feed it to index-pack. As index-pack processes the
objects as a stream, reconstructing and hashing each object
to get its name, it is not very susceptible to doing the
wrong with bad data (it simply notices that the data is
bogus and aborts).

However, one question raised on the list is whether it could
be susceptible to problems during the delta-resolution
phase. In particular, can a cycle in the packfile deltas
cause us to go into an infinite loop or cause any other
problem?

The answer is no.

We cannot have a cycle of delta-base offsets, because they
go only in one direction (the OFS_DELTA object mentions its
base by an offset towards the beginning of the file, and we
explicitly reject negative offsets).

We can have a cycle of REF_DELTA objects, which refer to
base objects by sha1 name. However, index-pack does not know
these sha1 names ahead of time; it has to reconstruct the
objects to get their names, and it cannot do so if there is
a delta cycle (in other words, it does not even realize
there is a cycle, but only that there are items that cannot
be resolved).

Even though we can reason out that index-pack should handle
this fine, let's add a few tests to make sure it behaves
correctly.

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test index-pack on packs with recoverable delta cycles

The previous commit added tests to show that index-pack
correctly bails in unrecoverable situations. There are some
situations where the data could be recovered, but it is not
currently:

  1. If we can break the cycle using an object from another
     pack via --fix-thin.

  2. If we can break the cycle using a duplicate of one of
     the objects found in the same pack.

Note that neither of these is particularly high priority; a
delta cycle within a pack should never occur, and we have no
record of even a buggy git implementation creating such a
pack.

However, it's worth adding these tests for two reasons. One,
to document that we do not currently handle the situation,
even though it is possible. And two, to exercise the code
that runs in this situation; even though it fails, by
running it we can confirm that index-pack detects the
situation and aborts, and does not misbehave (e.g., by
following the cycle in an infinite loop).

In both cases, we hit an assert that aborts index-pack.

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
index-pack: optionally reject packs with duplicate objects

Git should never generate packs with duplicate objects.
However, we may see such packs due to bugs in Git or other
implementations (e.g., JGit had such a bug a few years ago).

In theory, such packs should not be a problem for us (we
will simply find one of the instances of the object when
looking in the pack). However, the JGit bug report mentioned
possible infinite loops during repacking due to cycles in
the delta chain.  Though this problem hasn't specifically
been reproduced on modern git, there is no reason not to be
careful with incoming packs, given that only buggy
implementations should be producing such packs, anyway.

This patch introduces the pack.indexDuplicates option to
allow or reject such packs from index-pack. The default
remains to allow it.

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
default pack.indexDuplicates to false

We should never see duplicate objects in packs, and it is
unknown what kind of complications such packs could create
during the repacking process. The previous commit introduced
a safety valve for checking packs coming into the repository
and being indexed by index-pack.

Let's turn the safety valve on by default. This helps
protect sites receiving packfiles from potentially malicious
strangers, and shouldn't affect normal use (and if it does,
it will have helped us identify a buggy packfile writer).
In a pinch, users can recover by turning off the option, or
by resorting to unpack-objects to explode the pack.

Note that this also turns the option on for packs we write
ourselves (e.g., via pack-objects, fast-import, or streaming
large blobs). We do not expect maliciously constructed
packfiles in these code paths, of course, but it can serve
as an extra check that we have no accidentally created a
buggy pack (and the check itself is cheap to perform).

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation/fast-import: clarify summary for `feature` command

In most cases, "feature <foo>" does not just require that the feature
exists, but also changes the behavior by enabling it.

Cases where the feature is only requested like cat-blob, notes or ls are
clearly documented below.

Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'km/svn-1.8-serf-only' into jch

Subversion 1.8.0 that was recently released breaks older subversion
clients coming over http/https in various ways.

* km/svn-1.8-serf-only:
  Git.pm: revert _temp_cache use of temp_is_locked
  git-svn: allow git-svn fetching to work using serf
  Git.pm: add new temp_is_locked function
Merge branch 'jc/check-x-z' into jch

"git check-ignore -z" applied the NUL termination to both its input
(with --stdin) and its output, but "git check-attr -z" ignored the
option on the output side.

This is potentially a backward incompatible fix.  I am tempted to
merge this to and keep it in 'next' for a while to see if anybody
screams before deciding if we want to do anything to help existing
users (there may be none).

* jc/check-x-z:
  check-attr -z: a single -z should apply to both input and output
  check-ignore -z: a single -z should apply to both input and output
  check-attr: the name of the character is NUL, not NULL
  check-ignore: the name of the character is NUL, not NULL

# Conflicts:
# 	builtin/check-ignore.c
Merge branch 'ms/fetch-prune-configuration' into jch

Allow fetch.prune and remote.*.prune configuration variables to be set,
and "git fetch" to behave as if "--prune" is given.

"git fetch" that honors remote.*.prune is fine, but I wonder if we
should somehow make "git push" aware of it as well.  Perhaps
remote.*.prune should not be just a boolean, but a 4-way "none",
"push", "fetch", "both"?

* ms/fetch-prune-configuration:
  fetch: make --prune configurable
Merge branch 'rj/doc-rev-parse' into jch

* rj/doc-rev-parse:
  rev-parse(1): logically group options
  rev-parse: remove restrictions on some options
Merge branch 'jc/pull-training-wheel' into jch

Make "git pull" (without arguments that say what branch to
integrate from where) refuse with "it does not fast forward; choose
between 'pull --merge' and 'pull --rebase'".

See

http://thread.gmane.org/gmane.comp.version-control.git/225146/focus=225326
http://thread.gmane.org/gmane.comp.version-control.git/225146/focus=229221

for full discussion.

* jc/pull-training-wheel:
  pull: require choice between rebase/merge on non-fast-forward pull
Merge branch 'jc/diff-filter-negation' into jch

Teach "git diff --diff-filter" to express "I do not want to see
these classes of changes" more directly by listing only the
unwanted ones in lowercase (e.g. "--diff-filter=d" will show
everything but deletion) and deprecate "diff-files -q" which did
the same thing as "--diff-filter=d".

* jc/diff-filter-negation:
  diff: deprecate -q option to diff-files
  diff: allow lowercase letter to specify what change class to exclude
  diff: reject unknown change class given to --diff-filter
  diff: preparse --diff-filter string argument
  diff: factor out match_filter()
  diff: pass the whole diff_options to diffcore_apply_filter()

# Conflicts:
# 	diff.c
Merge branch 'jk/fast-import-empty-ls' into jch

* jk/fast-import-empty-ls:
  fast-import: allow moving the root tree
  fast-import: allow ls or filecopy of the root tree
  fast-import: set valid mode on root tree in "ls"
  t9300: document fast-import empty path issues
Merge branch 'nd/magic-pathspec' into jch

Use "struct pathspec" interface in more places, instead of array of
characters, the latter of which cannot express magic pathspecs
(e.g. ":(icase)makefile" that matches both Makefile and makefile).

* nd/magic-pathspec: (48 commits)
  rm: do not set a variable twice without intermediate reading.
  t6131 - skip tests if on case-insensitive file system
  parse_pathspec: accept :(icase)path syntax
  pathspec: support :(glob) syntax
  pathspec: make --literal-pathspecs disable pathspec magic
  pathspec: support :(literal) syntax for noglob pathspec
  kill limit_pathspec_to_literal() as it's only used by parse_pathspec()
  parse_pathspec: preserve prefix length via PATHSPEC_PREFIX_ORIGIN
  parse_pathspec: make sure the prefix part is wildcard-free
  rename field "raw" to "_raw" in struct pathspec
  tree-diff: remove the use of pathspec's raw[] in follow-rename codepath
  remove match_pathspec() in favor of match_pathspec_depth()
  remove init_pathspec() in favor of parse_pathspec()
  remove diff_tree_{setup,release}_paths
  convert common_prefix() to use struct pathspec
  convert add_files_to_cache to take struct pathspec
  convert {read,fill}_directory to take struct pathspec
  convert refresh_index to take struct pathspec
  convert report_path_error to take struct pathspec
  checkout: convert read_tree_some to take struct pathspec
  ...
Merge branch 'jc/push-cas' into jch

Allow a safer "rewind of the remote tip" push than blind "--force",
by requiring that the overwritten remote ref to be unchanged since
the new history to replace it was prepared.

The machinery is more or less ready.  The "--force" option is again
the big red button to override any safety, thanks to J6t's sanity
(the original round allowed --lockref to defeat --force).

The logic to choose the default implemented here is fragile
(e.g. "git fetch" after seeing a failure will update the
remote-tracking branch and will make the next "push" pass,
defeating the safety pretty easily).  It is suitable only for the
simplest workflows, and it may hurt users more than it helps them.

* jc/push-cas:
  push: teach --force-with-lease to smart-http transport
  send-pack: fix parsing of --force-with-lease option
  t5540/5541: smart-http does not support "--force-with-lease"
  t5533: test "push --force-with-lease"
  push --force-with-lease: tie it all together
  push --force-with-lease: implement logic to populate old_sha1_expect[]
  remote.c: add command line option parser for "--force-with-lease"
  builtin/push.c: use OPT_BOOL, not OPT_BOOLEAN
  cache.h: move remote/connect API out of it

# Conflicts:
# 	remote-curl.c
# 	remote.c
Merge branch 'nd/clone-connectivity-shortcut' into jch

* nd/clone-connectivity-shortcut:
  smart http: use the same connectivity check on cloning

# Conflicts:
# 	remote-curl.c
Merge branch 'rr/feed-real-path-to-editor' into jch

* rr/feed-real-path-to-editor:
  editor: use canonicalized absolute path
Merge branch 'db/http-savecookies' into jch

* db/http-savecookies:
  t5551: Remove header from curl cookie file
  http: add http.savecookies option to write out HTTP cookies
Merge branch 'nd/sq-quote-buf' into jch

Code simplification as a preparatory step to something larger.

* nd/sq-quote-buf:
  quote: remove sq_quote_print()
  tar-tree: remove dependency on sq_quote_print()
  for-each-ref, quote: convert *_quote_print -> *_quote_buf