name-rev: --algorithm option

Instead of naming a rev always after a tip that is topologically
closest, allow the command to use different algorithm when choosing
the tip to base the name on.  A new algorithm "weight" lets you use
the tip that has the smallest number of commits behind it.

The semantics "name-rev --algorithm=weight" would give us is closer
to what people expect from "describe --contains".

Note that this is fairly expensive to compute; a later change in the
series will cache the weight value using notes-cache.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-rev --algorithm=weight: trivial optimization

It often happens that immediately after traversing from v1.2.3 to
find out its weight, we are asked to see if another commit v1.2.0
is heavier than that.

Because the commits that are reachable from v1.2.3 are painted with
the SHOWN flag until the next "rev-list" traversal, we can notice
that the new commit v1.2.0 is reachable from v1.2.3 without doing
any traversal.  We cannot learn exactly how much it weighs, but we
can tell it must weigh less than v1.2.3, and that is all that the
caller wants to know.

In the kernel history, "git name-rev --tags 0136db586c" which
started this topic needs 26k calls to tip_weight_cmp().  13k of them
are comparisons between tips based on the same ref and answered
without computing any weight.  Among the remaining 13k, 1.8k
comparisons are answered with this trivial "fast-forward"
optimization.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-rev --algorithm=weight: cache the computed weight in notes

With the "weight" assigned to tip of each ref, we can give more
intuitive results from "name-rev" that is more suitable to answer
"what is the oldest tag that contains this commit?"  However, this
number is very expensive to compute.

Use the notes-cache mechanism to cache this value.  The result
becomes usable again.

    (priming the cache from scratch)
    $ rm .git/refs/notes/name-rev-weight
    $ /usr/bin/time git name-rev --algorithm=weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    6.06user 0.46system 0:06.54elapsed 99%CPU (0avgtext+0avgdata 1861456maxresident)k
    8inputs+16outputs (0major+128576minor)pagefaults 0swaps

    (with cache already primed)
    $ /usr/bin/time git name-rev --algorithm=weight --tags 0136db586c
    0136db586c tags/v3.5-rc1~83^2~81^2~76
    0.50user 0.22system 0:00.72elapsed 100%CPU (0avgtext+0avgdata 244224maxresident)k
    0inputs+0outputs (0major+16062minor)pagefaults 0swaps

    (the old "shortest path" version)
    $ /usr/bin/time git name-rev --tags 0136db586c
    0136db586c tags/v3.6-rc1~59^2~56^2~76
    0.31user 0.01system 0:00.32elapsed 100%CPU (0avgtext+0avgdata 243488maxresident)k
    0inputs+0outputs (0major+16000minor)pagefaults 0swaps

This version does not invalidate the cache in the presense of
modified grafts and object replacement, but in a later version we
can compute a hash of the grafts and replacement data and pass it as
the validity token to automatically invalidate the cache when these
data that affects the perceived topology change.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-rev --algorithm=weight: tests and documentation

We are almost there...

Signed-off-by: Junio C Hamano <gitster@pobox.com>
describe --contains: use "name-rev --algorithm=weight"

And this is the logical conclusion of the series, to
allow 0136db586c in the kernel history to be described
as v3.5-rc1~83^2~81^2~76, not as v3.6-rc1~59^2~56^2~76.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jc/maint-name-rev' into pu

* jc/maint-name-rev:
  describe --contains: use "name-rev --algorithm=weight"
  name-rev --algorithm=weight: tests and documentation
  name-rev --algorithm=weight: cache the computed weight in notes
  name-rev --algorithm=weight: trivial optimization
  name-rev: --algorithm option
  name_rev: clarify the logic to assign a new tip-name to a commit
  name-rev: lose unnecessary typedef

Conflicts:
	builtin/name-rev.c
Merge branch 'tx/relative-in-the-future' into pu

Not my itch; rewritten an earlier submission by Tom Xue into
somewhat more maintainable form, though it breaks existing i18n.

Waiting for a voluteer to fix it up.
Otherwise may discard.

* tx/relative-in-the-future:
  date: show relative dates in the future
  date: refactor the relative date logic from presentation
Merge branch 'jc/maint-push-refs-all' into pu

Allows pushing and fetching everything including refs/stash.
This is broken (see the log message there).

Not ready.

* jc/maint-push-refs-all:
  get_fetch_map(): tighten checks on dest refs
  [BROKEN] fetch/push: allow refs/*:refs/*
Merge branch 'jx/test-real-path' into pu

Running tests with the "trash" directory elsewhere with the "--root"
option did not work well if the directory was specified by a symbolic
link pointing at it.

Seems broken as it makes $(pwd) and TRASH_DIRECTORY inconsistent.
Needs rerolling.

* jx/test-real-path:
  test: set the realpath of CWD as TRASH_DIRECTORY
Merge branch 'ms/contrib-thunderbird-updates' into pu

Update helper to send out format-patch output using Thunderbird.
Seems to have design regression for silent users.

* ms/contrib-thunderbird-updates:
  [SQUASH] minimum fixup
  Thunderbird: fix appp.sh format problems
Merge branch 'mb/remote-default-nn-origin' into pu

When the user does not specify what remote to interact with, we
often attempt to use 'origin'.  This can now be customized via a
configuration variable.

Expecting a reroll.

"The first remote becomes the default" bit is better done as a
separate step.

* mb/remote-default-nn-origin:
  Teach get_default_remote to respect remote.default.
  Test that plain "git fetch" uses remote.default when on a detached HEAD.
  Teach clone to set remote.default.
  Teach "git remote" about remote.default.
  Teach remote.c about the remote.default configuration setting.
  Rename remote.c's default_remote_name static variables.

Conflicts:
	builtin/remote.c
	t/t5505-remote.sh
Merge branch 'jc/split-blob' into pu

Not ready.

I finished the streaming checkout codepath, but as explained in
127b177 (bulk-checkin: support chunked-object encoding, 2011-11-30),
these are still early steps of a long and painful journey. At least
pack-objects and fsck need to learn the new encoding for the series
to be usable locally, and then index-pack/unpack-objects needs to
learn it to be used remotely.

Given that I heard a lot of noise that people want large files, and
that I was asked by somebody at GitTogether'11 privately for an
advice on how to pay developers (not me) to help adding necessary
support, I am somewhat dissapointed that the original patch series
that was sent long time ago still remains here without much comments
and updates from the developer community. I even made the interface
to the logic that decides where to split chunks easily replaceable,
and I deliberately made the logic in the original patch extremely
stupid to entice others, especially the "bup" fanbois, to come up
with a better logic, thinking that giving people an easy target to
shoot for, they may be encouraged to help out. The plan is not
working :-<.

* jc/split-blob:
  chunked-object: streaming checkout
  chunked-object: fallback checkout codepaths
  bulk-checkin: support chunked-object encoding
  bulk-checkin: allow the same data to be multiply hashed
  new representation types in the packstream
  packfile: use varint functions

Conflicts:
	builtin/pack-objects.c
	streaming.c
	t/t1050-large.sh
Merge branch 'ph/credential-refactor' into pu

Attempts to refactor to share code among OSX keychain, Gnome keyring
and Win32 credential helpers.

* ph/credential-refactor:
  wincred: port to generic credential helper
  osxkeychain: port to generic credential helper implementation
  gnome-keyring: port to generic helper implementation
  contrib: add generic credential helper
Merge branch 'jl/submodule-rm' into pu

"git rm submodule" cannot blindly remove a submodule directory as
its working tree may have local changes, and worse yet, it may even
have its repository embedded in it.  Teach it some special cases
where it is safe to remove a submodule, specifically, when there is
no local changes in the submodule working tree, and its repository
is not embedded in its working tree but is elsewhere and uses the
gitfile mechanism to point at it.

Replacement sent but was still iffy around conflicted merge cases.

* jl/submodule-rm:
  Teach rm to remove submodules unless they contain a git directory
Merge branch 'jc/xprm-generation' into pu

A toy to analyze how bad the clock skews are in histories of real
world projects.

* jc/xprm-generation:
  test-generation: compute generation numbers and clock skews
Merge branch 'jc/maint-mailinfo-mime-attr' into pu

* jc/maint-mailinfo-mime-attr:
  mailinfo: do not concatenate charset= attribute values from mime headers
Merge branch 'nd/wildmatch' into pu

* nd/wildmatch:
  Support "**" in .gitignore and .gitattributes patterns using wildmatch()
  Integrate wildmatch to git
  compat/wildmatch: fix case-insensitive matching
  compat/wildmatch: remove static variable force_lower_case
  Import wildmatch from rsync
Merge branch 'js/poll-emu' into pu

* js/poll-emu:
  make poll() work on platforms that can't recv() on a non-socket
  poll() exits too early with EFAULT if 1st arg is NULL
  fix some win32 specific dependencies in poll.c
  make poll available for other platforms lacking it