Re: The new Codeville merge algorithm

Bram Cohen wrote:

> The criteria for a full ordering are (1) if two lines appear in any file
> at the same time, they must appear in that order in the full ordering,
> and (2) For each line, give it an ordering identifier, which is a tuple
> used to do 'tiebreak' between lines. To compare two ordering
> identifiers, first the first element is compared, and if those are the
> same then the second one is compared, and if those are the same the
> third ones are compared. The tuple elements are, first, the longest
> number of steps between the new revision and the history root, second
> the new revision identifier, and third the line number within that
> revision. When new text is inserted, it's put between the lines before
> and after it in the full ordering. When comparing merging two versions
> together, we combine their full orderings first by separating out lines
> based on what flanks them, so that if line X appears on both sides then
> a section which appears before X doesn't have to be compared to a
> section after X. For sections which are flanked the same way on either
> side we first determine their tiebreak ordering, and then mix. Mixing is
> done by successively taking the smallest number which appears anywhere
> in either section, then pulling everything up until that line to the
> beginning, and iterating on the result. For example if we're mixing 513
> and 42, then first the 51 gets pulled out, then the 42, then the 3, so
> the full ordering is 51423.
>
> We aren't especially fond of this full ordering technique, but it does
> work. We'd really like one which 'clumps' better - that is, if you have
> two different branches, and merge them together, all lines from one side
> should come after all lines from the other in the full ordering. Finding a
> better ordering technique is an interesting problem, but we have one which
> is perfictly serviceable for now.

I've given a bit more thought to this, and it seems that that the
technique of 'pull out the lowest thing and iterate' is a good one, the
problem is that our definition of 'lowest thing' is suboptimal. What we
need is a comparison function between graph elements where each element
has an arbitrary known identifier which has the following properties:

(1) a descendant must always have a greater value than any of its
ancestors

(2) the comparison between two nodes should not be changed by adding any
additional nodes

Length of longest path to root works for this, but we wish to add another
criterion:

(3) If there is a fork, then all nodes on one side of the fork should come
after all nodes on the other side of the fork.

A very good algorithm for doing this is to use the 'greatest' path from
the root. The between two paths, the 'greater' one is the one whose first
element (the one right off the root) is larger. If the first elements are
the same (which is most of the time) then the second element decides, then
the third, etc. If one path is identical to the other one but has more
stuff at the end, the longer one wins.

When comparing two elements, the one whose greatest path to root is
smaller comes first. If there's a fork, the value of the first element
after the fork will determine which side comes first, and that element
will be the same for each entire side, so this technique satisfies our
criterion (3) quite nicely.

Note that because the entire path is being walked, it makes a lot of sense
to only use graph elements which modify the particular file being weaved,
rather than all of history. It also makes sense to canonicalize clean
merges, so the same clean merge doesn't appear as multiple graph nodes,
especially since we went through all the trouble of making them really
canonical.

-Bram