add mergesort() for linked lists

This adds a generic bottom-up mergesort implementation for singly linked
lists.  It was inspired by Simon Tatham's webpage on the topic[1], but
not so much by his implementation -- for no good reason, really, just a
case of NIH.

[1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit: use mergesort() in commit_list_sort_by_date()

Replace the insertion sort in commit_list_sort_by_date() with a
call to the generic mergesort function.  This sets the stage for
using commit_list_sort_by_date() for larger lists, as shown in
the next patch.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
revision: insert unsorted, then sort in prepare_revision_walk()

Speed up prepare_revision_walk() by adding commits without sorting
to the commit_list and at the end sort the list in one go.  Thanks
to mergesort() working behind the scenes, this is a lot faster for
large numbers of commits than the current insert sort.

Also introduce and use commit_list_reverse(), to keep the ordering
of commits sharing the same commit date unchanged.  That's because
commit_list_insert_by_date() sorts commits with descending date,
but adds later entries with the same date entries last, while
commit_list_insert() always inserts entries at the top.  The
following commit_list_sort_by_date() keeps the order of entries
sharing the same date.

Jeff's test case, in a repo with lots of refs, was to run:

  # make a new commit on top of HEAD, but not yet referenced
  sha1=`git commit-tree HEAD^{tree} -p HEAD </dev/null`

  # now do the same "connected" test that receive-pack would do
  git rev-list --objects $sha1 --not --all

With a git.git with a ref for each revision, master needs (best of
five):

	real	0m2.210s
	user	0m2.188s
	sys	0m0.016s

And with this patch:

	real	0m0.480s
	user	0m0.456s
	sys	0m0.020s

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'ph/rerere-doc' into maint-1.7.8

* ph/rerere-doc:
  rerere: Document 'rerere remaining'
Merge branch 'tr/maint-bundle-long-subject' into maint-1.7.8

* tr/maint-bundle-long-subject:
  t5704: match tests to modern style
  strbuf: improve strbuf_get*line documentation
  bundle: use a strbuf to scan the log for boundary commits
  bundle: put strbuf_readline_fd in strbuf.c with adjustments
Merge branch 'tr/maint-bundle-boundary' into maint-1.7.8

* tr/maint-bundle-boundary:
  bundle: keep around names passed to add_pending_object()
  t5510: ensure we stay in the toplevel test dir
  t5510: refactor bundle->pack conversion
Merge branch 'cn/maint-rev-list-doc' into maint-1.7.8

* cn/maint-rev-list-doc:
  Documentation: use {asterisk} in rev-list-options.txt when needed
Merge branch 'cb/maint-t5541-make-server-port-portable' into maint-1.7.8

* cb/maint-t5541-make-server-port-portable:
  t5541: check error message against the real port number used
  remote-curl: Fix push status report when all branches fail
Merge branch 'tr/cache-tree' into maint-1.7.8

* tr/cache-tree:
  t0090: be prepared that 'wc -l' writes leading blanks
  reset: update cache-tree data when appropriate
  commit: write cache-tree data when writing index anyway
  Refactor cache_tree_update idiom from commit
  Test the current state of the cache-tree optimization
  Add test-scrap-cache-tree
Merge branch 'dw/gitweb-doc-grammo' into maint-1.7.8

* dw/gitweb-doc-grammo:
  Documentation/gitweb: trivial English fixes
Merge branch 'jc/maint-verify-objects-remove-pessimism' into maint-1.7.8

* jc/maint-verify-objects-remove-pessimism:
  fetch/receive: remove over-pessimistic connectivity check
Avoid bug in Solaris xpg4/sed as used in submodule

The sed provided by Solaris in /usr/xpg4/bin has a bug whereby an
unanchored regex using * for zero or more repetitions sees two
separate matches fed to the substitution engine in some cases.

This is evidenced by:

$ for sed in /usr/xpg4/bin/sed /usr/bin/sed /opt/csw/gnu/sed; do \
echo 'ab' | $sed -e 's|[a]*|X|g'; \
done
XXbX
XbX
XbX

This bug was triggered during a git submodule clone operation as
exercised in the setup stage of t5526-fetch-submodules when using the
default SANE_TOOL_PATH for Solaris.  It led to paths such as
..../.. being used in the submodule .git gitdir reference.

Using the expression 's|\([^/]*\(/*\)\)|..\2|g' provides the desired
result with all three three tested sed implementations but is harder
to read.  As we do not need to handle fully qualified paths though,
the expression could actually be [^/]+ which isn't properly handled
either.  Instead, use [^/][^/]*, as suggested by Andreas Schwab, which
works on all three tested sed implementations.

The new expression is semantically different than the original one.
It will not place a leading '..' on a fully qualified path as the
original expression did.  All of the paths being passed through this
regex are relative and did not rely on this behaviour so it's a safe
change.

Signed-off-by: Ben Walton <bwalton@artsci.utoronto.ca>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-p4: move to toplevel

Move git-p4 out of contrib/fast-import into the main code base,
aside other foreign SCM tools.

Signed-off-by: Pete Wyckoff <pw@padd.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git p4: update name in script

In messages to the user and comments, change "git-p4" to "git p4".

Signed-off-by: Pete Wyckoff <pw@padd.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git p4: use "git p4" directly in tests

Drop the $GITP4 variable that was used to specify the script in
contrib/fast-import/.  The command is called "git p4" now, not
"git-p4".

Note that configuration variables will remain in a section called
"git-p4".

Signed-off-by: Pete Wyckoff <pw@padd.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fast-import: tighten parsing of datarefs

The syntax for the use of mark references in fast-import
demands either a SP (space) or LF (end-of-line) after
a mark reference.  Fast-import does not complain when garbage
appears after a mark reference in some cases.

Factor out parsing of mark references and complain if
errant characters are found.  Also be a little more careful
when parsing "inline" and SHA1s, complaining if extra
characters appear or if the form of the dataref is unrecognized.

Buggy input can cause fast-import to produce the wrong output,
silently, without error.  This makes it difficult to track
down buggy generators of fast-import streams.  An example is
seen in the last line of this commit command:

    commit refs/heads/S2
    committer Name <name@example.com> 1112912893 -0400
    data <<COMMIT
    commit message
    COMMIT
    from :1M 100644 :103 hello.c

It is missing a newline and should be:

    [...]
    from :1
    M 100644 :103 hello.c

What fast-import does is to produce a commit with the same
contents for hello.c as in refs/heads/S2^.  What the buggy
program was expecting was the contents of blob :103.  While
the resulting commit graph looked correct, the contents in
some commits were wrong.

Signed-off-by: Pete Wyckoff <pw@padd.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
remote: update builtin usage

Add missing options "--tags|--no-tags" and "--push".

Signed-off-by: Michael Schubert <mschub@elegosoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase -i continue: don't skip commits that only change submodules

When git-rebase--interactive stops due to a conflict and the only change
to be committed is in a submodule, the test for whether there is
anything to be committed ignores the staged submodule change.  This
leads rebase to skip creating the commit for the change.

While unstaged submodule changes should be ignored to avoid needing to
update submodules during a rebase, it is safe to remove the
--ignore-submodules option to diff-index because --cached ensures that
it is only checking the index.  This was discussed in [1] and a test is
included to ensure that unstaged changes are still ignored correctly.

[1] http://thread.gmane.org/gmane.comp.version-control.git/188713

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'da/difftool-test' into jch

Makes sure "difftool" options can be given in any order.

* da/difftool-test:
  t7800: Test difftool passing arguments to diff
Merge branch 'jn/diffstat-tests' into jch

Some tests checked the "diff --stat" output when they do not have to,
which unnecessarily made things harder to verify under GETTEXT_POISON.

Not urgent.

* jn/diffstat-tests:
  diffstat summary line varies by locale: miscellany
  test: use numstat instead of diffstat in binary-diff test
  test: use --numstat instead of --stat in "git stash show" tests
  test: test cherry-pick functionality and output separately
  test: modernize funny-names test style
  test: use numstat instead of diffstat in funny-names test
  test: use test_i18ncmp when checking --stat output