merge.ChangeLog, specialized ChangeLog merger

I have a specialized ChangeLog merger at

https://netfiles.uiuc.edu/brownawe/www/merge.ChangeLog/

. It makes some assumptions (mostly, that entries are unique and don't
change very much), but seems to work ok.

Those of you getting this through monotone-devel may be interested in
merge.ChangeLog.monotonerc, which calls this merger instead of whatever
it would have used when monotone needs help merging a file named
"ChangeLog".


General reasoning and how it works are below, and also in the readme
file:


ChangeLog s in general are annoying to merge, because they change with
*every* commit, and always in the form of adding lines to the top.
Occasionally other parts will change (spelling fixes, utf8 mangling by
bad editors), but not often and not by very much.

A ChangeLog has a specific format, as an ordered collection of entries.
Individual entries don't depend on eachother the way lines in source
code do, and entries are ~always unique. This makes it possible to
resolve some merge conflicts automatically, that a general text merger
can't.

Specifically it allows for better resolution of what matches what, for
"edit" changes in addition to add and delete, and for add changes at the
same place to be handled automatically (keep both and sort by date,
which the format means is a string comparison of the entries).

----------

This merger divides the ChangeLog s (left, right, anc) into entries, and
then matches entries in anc against left and right starting from the
tail of the files. (Starting from the head would mean that for each new
entry, it would have to search the entire other file looking for a
match.)

Entries are considered to be the same if they are identical, or if a
character-based diff of the entries is sufficiently smaller than the
combined sizes of the entries. ("sufficiently smaller" is 10% in this
code)

Entries in left and right which are the only match for an entry in anc
are dropped, and left and right are combined as with "sort -m", except
that entries wich are "the same" (match the same entry in ancestor, or
would end up next to eachother and match eachother) are merged and
printed as a single entry. If entries in left and right match the same
entry in anc, but would end up in different places in the output,
they're only printed in the first location.

"merged" here is, if they match the same thing in ancestor, determine
changed/not changed and have the user pick if both sides changed in
different ways. If they don't match the same thing in ancestor, have the
user pick one.

----------

Note than if an entry is changed too much (more than 10%), this will see
it as a delete+add instead of an edit. So if it's changed too much in
both sides, it will be duplicated, and if it's changed too much in one
side, any small changes in the other side are lost.

Also note that if an entry gets edited on both sides, the available
conflict resolution is "pick one". I haven't implemented text merging
for entries, and haven't implemented any sort of editing.