The current rebase implementation finds commits in our tree but
not in the upstream tree using git-cherry, and tries to apply
them using git-cherry-pick (i.e. always use 3-way) one by one.

Which is fine, but when some of the changes do not apply
cleanly, it punts, and punts badly.

Suppose you have commits A-B-C-D-E since you forked from the
upstream and submitted the changes for inclusion.  You fetch
from upstream head U and find that B has been picked up.  You
run git-rebase to update your branch, which tries to apply
changes contained in A-C-D-E, in this order, but replaying of C
fails, because the upstream got changes that touch the same area
from elsewhere.

Now what?

It notes that fact, and goes ahead to apply D and E, and at the
very end tells you to deal with C by hand.  Even if you somehow
managed to replay C on top of the result, you would now end up
with ...-B-...-U-A-D-E-C.

Breaking the order between B and others was the conscious
decision made by the upstream, so we would not worry about it,
and even if it were worrisome, it is too late for us to fix now.
What D and E do may well depend on having C applied before them,
which is a problem for us.

This rewrites rebase to use git-format-patch piped to git-am,
and when the patch does not apply, have git-am fall back on
3-way merge.  The updated diff/patch pair knows how to apply
trivial binary patches as long as the pre- and post-images are
locally available, so this should work on a repository with
binary files as well.

The primary benefit of this change is that it makes rebase
easier to use when some of the changes do not replay cleanly.
In the "unapplicable patch in the middle" case, this "rebase"
works like this:

 - A series of patches in e-mail form is created that records
   what A-C-D-E do, and is fed to git-am.  This is stored in
   .dotest/ directory, just like the case you tried to apply
   them from your mailbox.  Your branch is rewound to the tip of
   upstream U, and the original head is kept in .git/ORIG_HEAD,
   so you could "git reset --hard ORIG_HEAD" in case the end
   result is really messy.

 - Patch A applies cleanly.  This could either be a clean patch
   application on top of rewound head (i.e. same as upstream
   head), or git-am might have internally fell back on 3-way
   (i.e.  it would have done the same thing as git-cherry-pick).
   In either case, a rebased commit A is made on top of U.

 - Patch C does not apply.  git-am stops here, with conflicts to
   be resolved in the working tree.  Yet-to-be-applied D and E
   are still kept in .dotest/ directory at this point.  What the
   user does is exactly the same as fixing up unapplicable patch
   when running git-am:

   - Resolve conflict just like any merge conflicts.
   - "git am --resolved --3way" to continue applying the patches.

 - This applies the fixed-up patch so by definition it had
   better apply.  "git am" knows the patch after the fixed-up
   one is D and then E; it applies them, and you will get the
   changes from A-C-D-E commits on top of U, in this order.

I've been using this without noticing any problem, and as people
may know I do a lot of rebases.
Signed-off-by: NJunio C Hamano <junkio@cox.net>