commit-queue: LIFO or priority queue of commits

Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history.  The most typical use
of the list is to add commits that are newly discovered to it, keep
the list sorted by commit timestamp, pick up the newest one from the
list, and keep digging.  The cost of keeping the singly linked list
sorted is nontrivial, and this typical use pattern better matches a
priority queue.

Introduce a commit-queue structure, that can be used either as a
LIFO stack, or a priority queue.  This will be used in the next
patch to hold in-flight commits during sort-in-topological-order.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
sort-in-topological-order: use prio-queue

Use the prio-queue data structure to implement a priority queue of
commits sorted by committer date, when handling --date-order.  The
structure can also be used as a simple LIFO stack, which is a good
match for --topo-order processing.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
log: --author-date-order

Sometimes people would want to view the commits in parallel
histories in the order of author dates, not committer dates.

Teach "topo-order" sort machinery to do so, using a commit-info slab
to record the author dates of each commit, and prio-queue to sort
them.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jc/topo-author-date-sort' into jch

"git log" learned the "--author-date-order" option, with which the
output is topologically sorted and commits in parallel histories
are shown intermixed together based on the author timestamp.

* jc/topo-author-date-sort:
  log: --author-date-order
  sort-in-topological-order: use prio-queue
  commit-queue: LIFO or priority queue of commits
  toposort: rename "lifo" field

# Conflicts:
# 	revision.c
Merge branch 'fc/show-non-empty-errors-in-test' into jch

* fc/show-non-empty-errors-in-test:
  test: test_must_be_empty helper
Merge branch 'nd/traces' into jch

* nd/traces:
  git.txt: document GIT_TRACE_PACKET
  core: use env variable instead of config var to turn on logging pack access
Merge branch 'rs/discard-index-discard-array' into jch

* rs/discard-index-discard-array:
  read-cache: free cache in discard_index
  read-cache: add simple performance test

# Conflicts:
# 	.gitignore
# 	Makefile
### 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
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 'mg/more-textconv' into pu

Make "git grep" and "git show" pay attention to --textconv when
dealing with blob objects.

I thought this was pretty well designed and executed, but it seems
there are some doubts on the list; kicking back to 'pu'.

* mg/more-textconv:
  grep: honor --textconv for the case rev:path
  grep: allow to use textconv filters
  t7008: demonstrate behavior of grep with textconv
  cat-file: do not die on --textconv without textconv filters
  show: honor --textconv for blobs
  diff_opt: track whether flags have been set explicitly
  t4030: demonstrate behavior of show with textconv

# Conflicts:
# 	object.c
# 	object.h
Merge branch 'jl/submodule-mv' into pu

"git mv A B" when moving a submodule A does "the right thing",
inclusing relocating its working tree and adjusting the paths in
the .gitmodules file.

* jl/submodule-mv:
  submodule.c: duplicate real_path's return value
  rm: delete .gitmodules entry of submodules removed from the work tree
  Teach mv to update the path entry in .gitmodules for moved submodules
  Teach mv to move submodules using a gitfile
  Teach mv to move submodules together with their work trees
Merge branch 'jk/submodule-subdirectory-ok' into pu

Allow various subcommands of "git submodule" to be run not from the
top of the working tree of the superproject.

* jk/submodule-subdirectory-ok:
  submodule: fix quoting in relative_path()
  submodule: drop the top-level requirement
  rev-parse: add --prefix option
Merge branch 'fc/remote-helpers-use-specified-python' into pu

I do not particularly think the second from the bottom is a good
change, but it takes the remainder of the series hostage.

* fc/remote-helpers-use-specified-python:
  remote-helpers: add exec-path links
  remote-helpers: allow direct test execution
  remote-helpers: rename tests
  remote-helpers: generate scripts
Merge branch 'mm/color-auto-default' into pu

Flip the default for color.ui to 'auto', which is what many
tutorials recommend new users to do.

* mm/color-auto-default:
  make color.ui default to 'auto'
  config: refactor management of color.ui's default value
Merge branch 'fc/sequencer-skip-quiet' into pu

The bottom three looked more or less reasonable.  Execution of
post-rewrite hook could use a better refactoring from the original
code copied from builtin/commit.c, though.

* fc/sequencer-skip-quiet:
  sequencer: run post-rewrite hook
  cherry-pick: store rewritten commits
  cherry-pick: add --skip-empty option
  sequencer: avoid leaking message buffer when refusing to create an empty commit
  sequencer: remove useless indentation
Merge branch 'js/test-ln-s-add' into pu

Many tests that check the behaviour of symbolic links stored in the
index or the tree objects do not have to be skipped on a filesystem
that lack symbolic link support.

* js/test-ln-s-add:
  t4011: remove SYMLINKS prerequisite
  t6035: use test_ln_s_add to remove SYMLINKS prerequisite
  t3509, t4023, t4114: use test_ln_s_add to remove SYMLINKS prerequisite
  t3100: use test_ln_s_add to remove SYMLINKS prerequisite
  t3030: use test_ln_s_add to remove SYMLINKS prerequisite
  t0000: use test_ln_s_add to remove SYMLINKS prerequisite
  tests: use test_ln_s_add to remove SYMLINKS prerequisite (trivial cases)
  tests: introduce test_ln_s_add
  t3010: modernize style
  test-chmtime: Fix exit code on Windows

# Conflicts:
# 	t/t8007-cat-file-textconv.sh
Merge branch 'ap/diff-ignore-blank-lines' into pu

"git diff" learned a mode that ignores hunks whose change consists
only of additions and removals of blank lines, which is the same as
"diff -B" (ignore blank lines) of GNU diff.

* ap/diff-ignore-blank-lines:
  diff: add --ignore-blank-lines option