shears.sh: support fixup! and squash!

One of the most powerful feature added to the already powerful
interactive rebase was to allow workflows where you *add* commits with
the intention to amend ("fix up") other commits in the topic branch at
a later stage, through "git rebase -i --autosquash". Such commits are
added by crafting special-format commit messages, or by using the
convenient --fixup or --squash options of "git commit".

However, with the garden shears, we side-step the original interactive
rebase, therefore we have to re-implement that very convenient
fixup/squash handling.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: simplify marking rewritten commits

It is nicer to read

	mark deadbeef

than

	exec git update-ref refs/rewritten/deadbeef HEAD

not to mention easier to write when modifying the edit script.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: provide hints as to branch names

It is quite convenient to know what branch is started by a

	exec git reset --hard refs/rewritten/onto

so let's try hard to find a branch name for each of them.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: introduce the 'rewind' shortcut

It is much nicer to read

	rewind onto

than

	exec git reset --hard refs/rewritten/onto

in the rebase script... ;-)

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: make merge nicer to use

When modifying edit scripts, it is quite convenient to be able to
split branches by inserting

	mark my-new-branch
	rewind onto

and later just adding the line

	merge my-new-branch

to make new merge commits from scratch, instead of calling a clunky

	exec git merge --no-ff -m "Merge 'my-new-branch'" refs/rewritten/my-new-branch

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: introduce 'bud' and 'finish' commands

The most common operations during splitting a bunch of commits into
neatly-packaged topic branches are:

1) 'finish': name a branch & mark it for merging at the end, and

2) 'bud': start a new branch from the 'onto' commit

Since multiple branches most often want to branch off from a common base
commit, the 'finish' command implies a 'bud' after marking the HEAD for
later merging.

For example, when given an edit script as this:

	pick abcdef Adds an initial README.md file
	pick 012345 Adds a FAQ section to the README
	pick 987654 Fix an off-by-one bug

you might want to put the first two commits into the 'readme' branch
while the third commit wants to live in the 'fixes' branch. This can be
accomplished by inserting two 'finish' lines:

	pick abcdef Adds an initial README.md file
	pick 012345 Adds a FAQ section to the README
	finish readme

	pick 987654 Fix an off-by-one bug
	finish fixes

Since 'finish' implies a 'bud', this will result in a rewritten
history like this:

	* 3141592 Merge 'fixes' into HEAD
	|\
	| * cafebabe Fix an off-by-one bug
	* |  badf00d Merge 'readme' into HEAD
	|\ \
	| * | c0eddad Adds a FAQ section to the README
	| * | d1bad00 Adds an initial README.md file
	|/ /
	o-' fa7d00d Start the merging-rebase

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: introduce --recrate=<merge-commit> option

This option will try to recreate the branch that was merged by the
specified commit.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: delete existing rewritten refs with --force

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: use branch names instead of short commit names whenever possible

It is nicer to read

	merge refs/rewritten/hide-dotgit -C bdb8cb3

than

	merge refs/rewritten/90116a7 -C bdb8cb3

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: quit early on dirty work tree

... not only after generating the script, when rebase -i complains...

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
shears.sh: report progress...

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Use the garden shears in merging-rebase.sh

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Add a script to determine the commit order implied by their changes

The idea comes from darcs: a (non-merge) commit can be easily exchanged
with its parent commit if -- and only if -- their respective diffs touch
different parts of the files they modify.

With merge commits thrown into the fray, it gets slightly more unwieldy,
and what we are really interested in is not so much to actually exchange
the commits, but to know their relationship.

Therefore, this tool only determines the commit topology implied by
their respective changes, and then shows the topology via gitk or `git
log --graph`.

Note that we let renaming commits be implied parents of subsequent
changes. This is somewhat unintuitive because commits can be
cherry-picked sometimes when the modified files in question have been
renamed. However, this is not really reliable due to the rename
detection failing when too many changes happened in the meantime, so
we'll err on the safe side.

Also, while it would have been nice to use `git log -p -m` to read the
original commit history at the same time as the diffs -- without having
to launch new processes, so as to avoid challenging Windows and other
operating systems whose filesystem and process management technology
fell a little behind -- but we need to use custom commit message
formatting to obtain both short and long commit names at the same time
(to accomodate command-line length limitations imposed by Windows), and
there is simply no support in Git to retrieve the *current* parent in
custom commit messages when using '-m' (showing diffs relative to *all*
parents in case of merge commits).

In contrast to darcs, we do not use Haskell (which would essentially
lock out the 99% of programmers who do not speak that language) and we
do not try to explain the concept by employing oh-so-intuitive quantum
physics theory.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Teach implied-commit-order to support the --gitk option

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
implied-commit-order: simplify the history by default

Imagine a commit history like this:

	* README: modify heading and fix a typo
	* README: modify heading
	* Add a README

where the first commit touches some parts that are touched by the second
commit, but also some others. In this case, the implied commit order
dictates that the third commit is both a direct implied parent as well
as an implied *grand* parent.

While this is technically correct, it is also confusing, and also
unnecessary when all we want to know is what commits are tied by their
changes and which ones are not: transitively-implied ancestors are just
as implied as directly-implied ones.

There is an additional problem with being "too correct" about implied
parents: our trick to re-use Git's history visualization tools is to
make temporary grafts to imply a different order than the one stored
inside the commit objects.

Now, the graft handling in Git predates the strbuf support, and
therefore it still has a rather serious line length limitation of 1023
bytes per line. Given that the graft lines *must* list non-abbreviated
commit names -- the only reason why we have to bother with long names at
all -- that leaves space for only (int)(1023 + 1) / (40 + 1) parents,
i.e. just one byte shy of allowing 24 parent commits to be listed.

While it is rare to see commit histories coming even close to merging 23
branches at once, in the implied commit order that limitation is reached
very quickly. Already Git for Windows' fork -- currently only puny 113
non-merge commits on top of upstream's 1.8.5.1 tag (a situation that is
unlikely going to change if one trusts history's lessons) -- lists
fourty-six implied parents for the final merge!

Unfortunately, simplifying the implied order isn't enough: it brings
down the (insane) number of 46 parents only to 29, still larger than
upstream Git's limit of 23 parents. But it's something!!!

While it is conceivable that there are more efficient methods to simplify
the implied commit order than to traverse the implied ancestry and
throwing out unnecessarily-implied parents, the current method is good
enough for now, and in the interest of following the YAGNI principle we'll
cross that bridge when -- and if -- we have to.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>