git-commit.txt: clarify -t requires editing message

Make it clear that, when using commit --template, the message *must* be
changed or the commit will be aborted.

Helped-by: Junio C Hamano <gitster@pobox.com>
Helped-by: Ivan Heffner <iheffner@gmail.com>
Signed-off-by: Adam Monsen <haircut@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>
fetch-pack: new --stdin option to read refs from stdin

If a remote repo has too many tags (or branches), cloning it over the
smart HTTP transport can fail because remote-curl.c puts all the refs
from the remote repo on the fetch-pack command line. This can make the
command line longer than the global OS command line limit, causing
fetch-pack to fail.

This is especially a problem on Windows where the command line limit is
orders of magnitude shorter than Linux. There are already real repos out
there that msysGit cannot clone over smart HTTP due to this problem.

Here is an easy way to trigger this problem:

	git init too-many-refs
	cd too-many-refs
	echo bla > bla.txt
	git add .
	git commit -m test
	sha=$(git rev-parse HEAD)
	tag=$(perl -e 'print "bla" x 30')
	for i in `seq 50000`; do
		echo $sha refs/tags/$tag-$i >> .git/packed-refs
	done

Then share this repo over the smart HTTP protocol and try cloning it:

	$ git clone http://localhost/.../too-many-refs/.git
	Cloning into 'too-many-refs'...
	fatal: cannot exec 'fetch-pack': Argument list too long

50k tags is obviously an absurd number, but it is required to
demonstrate the problem on Linux because it has a much more generous
command line limit. On Windows the clone fails with as little as 500
tags in the above loop, which is getting uncomfortably close to the
number of tags you might see in real long lived repos.

This is not just theoretical, msysGit is already failing to clone our
company repo due to this. It's a large repo converted from CVS, nearly
10 years of history.

Four possible solutions were discussed on the Git mailing list (in no
particular order):

1) Call fetch-pack multiple times with smaller batches of refs.

This was dismissed as inefficient and inelegant.

2) Add option --refs-fd=$n to pass a an fd from where to read the refs.

This was rejected because inheriting descriptors other than
stdin/stdout/stderr through exec() is apparently problematic on Windows,
plus it would require changes to the run-command API to open extra
pipes.

3) Add option --refs-from=$tmpfile to pass the refs using a temp file.

This was not favored because of the temp file requirement.

4) Add option --stdin to pass the refs on stdin, one per line.

In the end this option was chosen as the most efficient and most
desirable from scripting perspective.

There was however a small complication when using stdin to pass refs to
fetch-pack. The --stateless-rpc option to fetch-pack also uses stdin for
communication with the remote server.

If we are going to sneak refs on stdin line by line, it would have to be
done very carefully in the presence of --stateless-rpc, because when
reading refs line by line we might read ahead too much data into our
buffer and eat some of the remote protocol data which is also coming on
stdin.

One way to solve this would be to refactor get_remote_heads() in
fetch-pack.c to accept a residual buffer from our stdin line parsing
above, but this function is used in several places so other callers
would be burdened by this residual buffer interface even when most of
them don't need it.

In the end we settled on the following solution:

If --stdin is specified without --stateless-rpc, fetch-pack would read
the refs from stdin one per line, in a script friendly format.

However if --stdin is specified together with --stateless-rpc,
fetch-pack would read the refs from stdin in packetized format
(pkt-line) with a flush packet terminating the list of refs. This way we
can read the exact number of bytes that we need from stdin, and then
get_remote_heads() can continue reading from the same fd without losing
a single byte of remote protocol data.

This way the --stdin option only loses generality and scriptability when
used together with --stateless-rpc, which is not easily scriptable
anyway because it also uses pkt-line when talking to the remote server.

Signed-off-by: Ivan Todoroski <grnch@gmx.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
remote-curl: send the refs to fetch-pack on stdin

Now that we can throw an arbitrary number of refs at fetch-pack using
its --stdin option, we use it in the remote-curl helper to bypass the
OS command line length limit.

Signed-off-by: Ivan Todoroski <grnch@gmx.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fixup? no longer need flex argv[]

Signed-off-by: Junio C Hamano <gitster@pobox.com>
fetch-pack: test cases for the new --stdin option

These test cases focus only on testing the parsing of refs on stdin,
without bothering with the rest of the fetch-pack machinery. We pass in
the refs using different combinations of command line and stdin and then
we watch fetch-pack's stdout to see whether it prints all the refs we
specified (but we ignore their order).

Signed-off-by: Ivan Todoroski <grnch@gmx.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
remote-curl: main test case for the OS command line overflow

This is main test case for the original problem that triggered this
patch series. We create a repo with 50k tags and then test whether
git-clone over the smart HTTP protocol succeeds.

Note that we construct the repo in a slightly different way than the
original script used to reproduce the problem. This is because the
original script just created 50k tags all pointing to the same commit,
so if there was a bug where remote-curl.c was not passing all the refs
to fetch-pack we wouldn't know. The clone would succeed even if only one
tag was passed, because all the other tags were pointing at the same SHA
and would be considered present.

Instead we create a repo with 50k independent (dangling) commits and
then tag each of those commits with a unique tag. This way if one of the
tags is not given to fetch-pack, later stages of the clone would
complain about it.

This allows us to test both that the command line overflow was fixed, as
well as that it was fixed in a way that doesn't leave out any of the
refs.

Signed-off-by: Ivan Todoroski <grnch@gmx.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
difftool: teach difftool to handle directory diffs

When 'difftool' is called to compare a range of commits that modify
more than one file, it opens a separate instance of the diff tool for
each file that changed.

The new '--dir-diff' option copies all the modified files to a temporary
location and runs a directory diff on them in a single instance of the
diff tool.

Signed-off-by: Tim Henigan <tim.henigan@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
difftool: print list of valid tools with '--tool-help'

Since bc7a96a (mergetool--lib: Refactor tools into separate files,
2011-08-18), it is possible to add a new diff tool by creating a simple
script in the '$(git --exec-path)/mergetools' directory.  Updating the
difftool help text is still a manual process, and the documentation can
easily go out of sync.

This commit teaches difftool the '--tool-help' option, which:
  - Reads the list of valid tools from 'mergetools/*'
  - Determines which of them are actually installed
  - Determines which are capable of diffing (i.e. not just a merge tool)
  - Prints the resulting list for the user

Signed-off-by: Tim Henigan <tim.henigan@gmail.com>
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
Merge branch 'jc/commit-hook-authorship' into jch

"git commit --author=$name" did not tell the name that was being
recorded in the resulting commit to hooks, even though it does do so
when the end user overrode the authorship via the "GIT_AUTHOR_NAME"
environment variable.  This is a simpler of the two approaches.

Will defer til 1.7.10.

* jc/commit-hook-authorship:
  commit: pass author/committer info to hooks
  t7503: does pre-commit-hook learn authorship?
  ident.c: add split_ident_line() to parse formatted ident line
Merge branch 'tr/maint-word-diff-regex-sticky' into jch

The regexp configured with wordregex was incorrectly reused across
files.
Not urgent.

* tr/maint-word-diff-regex-sticky:
  diff: tweak a _copy_ of diff_options with word-diff
  diff: refactor the word-diff setup from builtin_diff_cmd
  t4034: diff.*.wordregex should not be "sticky" in --word-diff
Merge branch 'jh/notes-merge-in-git-dir-worktree' into jch

Running "notes merge --commit" failed to perform correctly when run
from any directory inside $GIT_DIR/.  When "notes merge" stops with
conflicts, $GIT_DIR/NOTES_MERGE_WORKTREE is the place a user edits
to resolve it.

Not urgent.

* jh/notes-merge-in-git-dir-worktree:
  notes-merge: Don't remove .git/NOTES_MERGE_WORKTREE; it may be the user's cwd
  notes-merge: use opendir/readdir instead of using read_directory()
  t3310: illustrate failure to "notes merge --commit" inside $GIT_DIR/
  remove_dir_recursively(): Add flag for skipping removal of toplevel dir
Merge branch 'jc/maint-clean-nested-worktree-in-subdir' into jch

"git clean -d -f" (not "-d -f -f") is supposed to protect nested working
trees of independent git repositories that exist in the current project
working tree from getting removed, but the protection applied only to such
working trees that are at the top-level of the current project by mistake.

Not urgent.

* jc/maint-clean-nested-worktree-in-subdir:
  clean: preserve nested git worktree in subdirectories
Merge branch 'rs/unpack-trees-leakfix' into jch

Will defer til 1.7.10.

* rs/unpack-trees-leakfix:
  unpack-trees: plug minor memory leak
Merge branch 'jc/diff-algo-cleanup' into jch

Resurrects the preparatory clean-up patches from another topic that was
discarded, as this would give a saner foundation to build on diff.algo
configuration option series.

Not urgent.

* jc/diff-algo-cleanup:
  xdiff: PATIENCE/HISTOGRAM are not independent option bits
  xdiff: remove XDL_PATCH_* macros
Merge branch 'nd/stream-more' into jch

Use API to read blob data in smaller chunks in more places to
reduce the memory footprint.  In general, looked fairly good.

Will defer til 1.7.10.

* nd/stream-more:
  update-server-info: respect core.bigfilethreshold
  fsck: use streaming API for writing lost-found blobs
  show: use streaming API for showing blobs
  parse_object: avoid putting whole blob in core
  cat-file: use streaming API to print blobs
  Add more large blob test cases
  streaming: make streaming-write-entry to be more reusable