ewah: compressed bitmap implementation

EWAH is a word-aligned compressed variant of a bitset (i.e. a data
structure that acts as a 0-indexed boolean array for many entries).

It uses a 64-bit run-length encoding (RLE) compression scheme,
trading some compression for better processing speed.

The goal of this word-aligned implementation is not to achieve
the best compression, but rather to improve query processing time.
As it stands right now, this EWAH implementation will always be more
efficient storage-wise than its uncompressed alternative.

EWAH arrays will be used as the on-disk format to store reachability
bitmaps for all objects in a repository while keeping reasonable sizes,
in the same way that JGit does.

This EWAH implementation is a mostly straightforward port of the
original `javaewah` library that JGit currently uses. The library is
self-contained and has been embedded whole (4 files) inside the `ewah`
folder to ease redistribution.

The library is re-licensed under the GPLv2 with the permission of Daniel
Lemire, the original author. The source code for the C version can
be found on GitHub:

	https://github.com/vmg/libewok

The original Java implementation can also be found on GitHub:

	https://github.com/lemire/javaewah

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
documentation: add documentation for the bitmap format

This is the technical documentation for the JGit-compatible Bitmap v1
on-disk format.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add-interactive: handle unborn branch in patch mode

The list_modified function already knows how to handle an
unborn branch by diffing against the empty tree. However,
the diff we perform to get the actual hunks does not. Let's
use the same logic for both diffs.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
reset: pass real rev name to add--interactive

The add--interactive --patch mode adjusts the UI based on
whether we are pulling changes from HEAD or elsewhere (in
the former case it asks to unstage the reverse hunk, rather
than apply the forward hunk).

Commit 166ec2e taught reset to work on an unborn branch, but
in doing so, switched to always providing add--interactive
with the sha1 rather than the symbolic name. This meant we
always used the "apply" interface, even for "git reset -p
HEAD".

We can fix this by passing the symbolic name to
add--interactive.  Since it understands unborn branches
these days, we do not even have to cover this special case
ourselves; we can simply pass HEAD.

The tests in t7105 now check that the right interface is
used in each circumstance (and notice the regression from
166ec2e we are fixing). The test in t7106 checks that we
get this right for the unborn case, too (not a regression,
since it didn't work at all before, but a nice improvement).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
howto: add article on recovering a corrupted object

This is an asciidoc-ified version of a corruption post-mortem sent to
the git list. It complements the existing howto article, since it covers
a case where the object couldn't be easily recreated or copied from
elsewhere.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
graph.c: mark root commit differently

For projects with separate history lines and, thus, multiple
root-commits, the linear arrangement of `git log --graph --oneline`
does not allow the user to spot where the sequence ends, giving the
impression that it's a contiguous history. E.g.

History sequence A: a1 -- a2 -- a3 (root-commit)
History sequence B: b1 -- b2 -- b3 (root-commit)

    git log --graph --oneline
    * a1
    * a2
    * a3
    * b1
    * b2
    * b3

In a GUI tool, the root-commit of each series would stand out on the graph.

This modification changes the commit char to a different symbol ('x'), so users
of the command-line graph tool can easily identify root-commits and make sense
of where each series is limited to.

    git log --graph --oneline
    * a1
    * a2
    x a3
    * b1
    * b2
    x b3

Signed-off-by: Milton Soares Filho <milton.soares.filho@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rev-parse --parseopt: add the --sticked-long mode

Add the --sticked-long option to output the options in their long form
if available, and with their arguments sticked.

Contrary to the default form (non sticked arguments and short options),
this can be parsed unambiguously when using options with optional
arguments :

 - in the non sticked form, when an option is taking an optional argument
   you cannot know if the next argument is its optional argument, or the
   next option.

 - the long options form allows to differenciate between an empty argument
   '--option=' and an unset argument '--option', which is not possible
   with short options.

Signed-off-by: Nicolas Vigier <boklm@mars-attacks.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
merge-base: teach "--fork-point" mode

The "git pull --rebase" command computes the fork point of the
branch being rebased using the reflog entries of the "base" branch
(typically a remote-tracking branch) the branch's work was based on,
in order to cope with the case in which the "base" branch has been
rewound and rebuilt.  For example, if the history looked like this:

                     o---B1
                    /
    ---o---o---B2--o---o---o---Base
            \
             B3
              \
               Derived

where the current tip of the "base" branch is at Base, but earlier
fetch observed that its tip used to be B3 and then B2 and then B1
before getting to the current commit, and the branch being rebased
on top of the latest "base" is based on commit B3, it tries to find
B3 by going through the output of "git rev-list --reflog base" (i.e.
Base, B1, B2, B3) until it finds a commit that is an ancestor of the
current tip "Derived".

Internally, we have get_merge_bases_many() that can compute this
with one-go.  We would want a merge-base between Derived and a
fictitious merge commit that would result by merging all the
historical tips of "base".  When such a commit exist, we should get
a single result, which exactly match one of the reflog entries of
"base".

Teach "git merge-base" a new mode, "--fork-point", to compute
exactly that.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jc/merge-base-reflog' into jch

Code the logic in "pull --rebase" that figures out a fork point
from reflog entries in C.

* jc/merge-base-reflog:
  merge-base: teach "--fork-point" mode
  merge-base: use OPT_CMDMODE and clarify the command line parsing
Merge branch 'bc/http-100-continue' into jch

Conditionally allow "100 Continue" responses to help use of
GSS-Negotiate authentication scheme over HTTP transport.

* bc/http-100-continue:
  http: add option to enable 100 Continue responses

# Conflicts:
# 	http.h
Merge branch 'jk/pack-corruption-post-mortem' into jch

* jk/pack-corruption-post-mortem:
  howto: add article on recovering a corrupted object
Merge branch 'jk/reset-p-current-head-fix' into jch

* jk/reset-p-current-head-fix:
  reset: pass real rev name to add--interactive
  add-interactive: handle unborn branch in patch mode
Merge branch 'nv/parseopt-opt-arg' into jch

* nv/parseopt-opt-arg:
  rev-parse --parseopt: add the --sticked-long mode
### 2.0
Merge branch 'jc/push-2.0-default-to-simple' into jch

* jc/push-2.0-default-to-simple:
  push: switch default from "matching" to "simple"

# Conflicts:
# 	Documentation/config.txt
# 	Documentation/git-push.txt
# 	builtin/push.c
Merge branch 'jn/add-2.0-u-A-sans-pathspec' into jch

* jn/add-2.0-u-A-sans-pathspec:
  git add: -u/-A now affects the entire working tree

# Conflicts:
# 	builtin/add.c
Merge branch 'jc/add-2.0-ignore-removal' into jch

Updated endgame for "git add <pathspec>" that defaults to "--all"
aka "--no-ignore-removal".

* jc/add-2.0-ignore-removal:
  git add <pathspec>... defaults to "-A"

# Conflicts:
# 	builtin/add.c
Merge branch 'jc/core-checkstat-2.0' into jch

* jc/core-checkstat-2.0:
  core.statinfo: remove as promised in Git 2.0
Merge branch 'jc/hold-diff-remove-q-synonym-for-no-deletion' into jch

* jc/hold-diff-remove-q-synonym-for-no-deletion:
  diff: remove "diff-files -q" in a version of Git in a distant future

# Conflicts:
# 	diff.c
Merge branch 'mh/fetch-tags-in-addition-to-normal-refs' into pu

Some questionable paragraphs in the doc updates, but other than
that looks reasonably solid.

* mh/fetch-tags-in-addition-to-normal-refs:
  fetch, remote: properly convey --no-prune options to subprocesses
  builtin/remote.c:update(): use struct argv_array
  builtin/remote.c: reorder function definitions
  query_refspecs(): move some constants out of the loop
  fetch --prune: prune only based on explicit refspecs
  SQUASH??? --tags is no longer a short-hand
  fetch --tags: fetch tags *in addition to* other stuff
  builtin/fetch.c: reorder function definitions
  ref_remove_duplicates(): improve documentation comment
  ref_remove_duplicates(): simplify function
  ref_remove_duplicates(): avoid redundant bisection
  get_ref_map(): rename local variables
  api-remote.txt: correct section "struct refspec"
  t5510: check that "git fetch --prune --tags" does not prune branches
  t5510: prepare test refs more straightforwardly
  t5510: use the correct tag name in test