replace: cleanup redirection style in tests

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: factor out compare and swap operations

When manipulating the priority queue's heap, we frequently
have to compare and swap heap entries. As we are storing
only void pointers right now, this is quite easy to do
inline in a few lines. However, when we start using a more
complicated heap entry in a future patch, that will get
longer. Factoring out these operations lets us make future
changes in one place. It also makes the code a little
shorter and more readable.

Note that we actually accept indices into the queue array
instead of pointers. This is slightly less flexible than
passing pointers-to-pointers (we could not swap items from
unrelated arrays, but we would not want to), but will make
further refactoring simpler (and lets us avoid repeating
"queue->array" at each callsite, which led to some long
lines).

And finally, note that we are cleaning up an accidental use
of a "struct commit" pointer to hold a temporary entry
during swap. Even though we currently only use this code for
commits, it is supposed to be type-agnostic. In practice
this didn't matter anyway because we never dereferenced the
commit pointer (and on most systems, the pointer values
themselves are interchangeable between types).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: make output stable with respect to insertion

If two items are added to a prio_queue and compare equal,
they currently come out in an apparently random order (this
order is deterministic for a particular sequence of
insertions and removals, but does not necessarily match the
insertion order). This makes it unlike using a date-ordered
commit_list, which is one of the main types we would like to
replace with it (because prio_queue does not suffer from
O(n) insertions).

We can make the priority queue stable by keeping an
insertion counter for each element, and using it to break
ties. This does increase the memory usage of the structure
(one int per element), but in practice it does not seem to
affect runtime. A best-of-five "git rev-list --topo-order"
on linux.git showed less than 1% difference (well within the
run-to-run noise).

In an ideal world, we would offer both stable and unstable
priority queues (the latter to try to maximize performance).
However, given the lack of a measurable performance
difference, it is not worth the extra code.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
paint_down_to_common: use prio_queue

When we are traversing to find merge bases, we keep our
usual commit_list of commits to process, sorted by their
commit timestamp. As we add each parent to the list, we have
to spend "O(width of history)" to do the insertion, where
the width of history is the number of simultaneous lines of
development.

If we instead use a heap-based priority queue, we can do
these insertions in "O(log width)" time. This provides minor
speedups to merge-base calculations (timings in linux.git,
warm cache, best-of-five):

  [before]
  $ git merge-base HEAD v2.6.12
  real    0m3.251s
  user    0m3.148s
  sys     0m0.104s

  [after]
  $ git merge-base HEAD v2.6.12
  real    0m3.234s
  user    0m3.108s
  sys     0m0.128s

That's only an 0.5% speedup, but it does help protect us
against pathological cases.

While we are munging the "interesting" function, we also
take the opportunity to give it a more descriptive name, and
convert the return value to an int (we returned the first
interesting commit, but nobody ever looked at it).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t5539: update a flaky test

The test creates some unrelated commits in two separate repositories,
and then fetches from one to the other. Since the commit creation
happens in a subshell, the first commit in each ends up with the
same test_tick value. When fetch-pack looks at the two root commits
"unrelated1" and "new-too", the exact sequence of ACKs is different
depending on which one it pulls out of the queue first.

With the current code, it happens to be "unrelated1" (though this is not
at all guaranteed by the prio_queue data structure, it is deterministic
for this particular sequence of input). We see the ready-ACK, and the
test succeeds.

With the stable queue, we reliably get "new-too" out (since it is our
local tip, it is added to the queue before we even talk to the remote).
We never see a ready-ACK, and the test fails due to the grep on the
TRACE_PACKET output at the end (the fetch itself succeeds as expected).

I'm really not quite clear on what's supposed to be going on in the
test. I can make it pass with this change.
rebase--am: use --cherry-pick instead of --ignore-if-in-upstream

When using `git format-patch --ignore-if-in-upstream` we are only
allowed to give a single revision range.  In the next commit we will
want to add an additional exclusion revision in order to handle fork
points correctly, so convert `git-rebase--am` to use a symmetric
difference with `--cherry-pick --right-only`.

This does not change the result of the format-patch invocation, just how
we spell the arguments.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase: omit patch-identical commits with --fork-point

When the `--fork-point` argument was added to `git rebase`, we changed
the value of $upstream to be the fork point instead of the point from
which we want to rebase.  When $orig_head..$upstream is empty this does
not change the behaviour, but when there are new changes in the upstream
we are no longer checking if any of them are patch-identical with
changes in $upstream..$orig_head.

Fix this by introducing a new variable to hold the fork point and using
this to restrict the range as an extra (negative) revision argument so
that the set of desired revisions becomes (in fork-point mode):

	git rev-list --cherry-pick --right-only \
		$upstream...$orig_head ^$fork_point

This allows us to correctly handle the scenario where we have the
following topology:

	    C --- D --- E  <- dev
	   /
	  B  <- master@{1}
	 /
	o --- B' --- C* --- D*  <- master

where:
- B' is a fixed-up version of B that is not patch-identical with B;
- C* and D* are patch-identical to C and D respectively and conflict
  textually if applied in the wrong order;
- E depends textually on D.

The correct result of `git rebase master dev` is that B is identified as
the fork-point of dev and master, so that C, D, E are the commits that
need to be replayed onto master; but C and D are patch-identical with C*
and D* and so can be dropped, so that the end result is:

	o --- B' --- C* --- D* --- E  <- dev

If the fork-point is not identified, then picking B onto a branch
containing B' results in a conflict and if the patch-identical commits
are not correctly identified then picking C onto a branch containing D
(or equivalently D*) results in a conflict.

This change allows us to handle both of these cases, where previously we
either identified the fork-point (with `--fork-point`) but not the
patch-identical commits *or* (with `--no-fork-point`) identified the
patch-identical commits but not the fact that master had been rewritten.

Reported-by: Ted Felix <ted@tedfelix.com>
Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
unix-socket: remove stale socket before calling chdir()

unix_stream_listen() is given a path.  It calls unix_sockaddr_init(),
which in turn can call chdir().  After that a relative path doesn't
mean the same as before.  Any use of the original path should thus
happen before that call.  For that reason, unlink the given path
(to get rid of a possibly existing stale socket) right at the
beginning of the function.

Noticed-by: Karsten Blees <karsten.blees@gmail.com>
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add --graft option

The usage string for this option is:

git replace [-f] --graft <commit> [<parent>...]

First we create a new commit that is the same as <commit>
except that its parents are [<parents>...]

Then we create a replace ref that replace <commit> with
the commit we just created.

With this new option, it should be straightforward to
convert grafts to replace refs.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: replace: add --graft option

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib: add convert-grafts-to-replace-refs.sh

This patch adds into contrib/ an example script to convert
grafts from an existing grafts file into replace refs using
the new --graft option of "git replace".

While at it let's mention this new script in the
"git replace" documentation for the --graft option.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: remove signature when using --graft

It could be misleading to keep a signature in a
replacement commit, so let's remove it.

Note that there should probably be a way to sign
the replacement commit created when using --graft,
but this can be dealt with in another commit or
patch series.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft with signed commit

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: check mergetags when using --graft

When using --graft, with a mergetag in the original
commit, we should check that the commit pointed to by
the mergetag is still a parent of then new commit we
create, otherwise the mergetag could be misleading.

If the commit pointed to by the mergetag is no more
a parent of the new commit, we could remove the
mergetag, but in this case there is a good chance
that the title or other elements of the commit might
also be misleading. So let's just error out and
suggest to use --edit instead on the commit.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft with a mergetag

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: fix missing text for rev-parse --verify

The caret (^) is used as a markup symbol in AsciiDoc.  Due to the
inability of AsciiDoc to parse a line containing an unmatched caret, it
omitted the line from the output, resulting in the man page missing the
end of a sentence.  Escape this caret so that the man page ends up with
the complete text.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'maint-1.8.5' into maint-1.9

* maint-1.8.5:
  Documentation: fix missing text for rev-parse --verify
Merge branch 'maint-1.9' into maint

* maint-1.9:
  Documentation: fix missing text for rev-parse --verify
Merge branch 'ep/shell-assign-and-export-vars' into maint

* ep/shell-assign-and-export-vars:
  scripts: more "export VAR=VALUE" fixes
  scripts: "export VAR=VALUE" construct is not portable