The Version Merging Algorithm: Release 0.9

[Marc Stiegler <marcs>]

In my writeup of the Top Ten Trauma several months ago, 
which listed the scariest issues we had uncovered in the 
Capabilities Review, one of the issues was the need for an 
algorithm that would transform low-level Xanadu version 
comparison information into high-level information that 
could sustain our Version Compare/Merge display. Our 
version compare/merge is based on standard proofreading 
marks (insert, delete, and move), but no one had ever 
thought about how to transform raw Xanadu version 
information into such a description until I thought about 
it in preparing for the Review. The particularly scary part 
of the process, I discovered, is deriving a reasonable 
description of character movement operations. The 
rearrangement and movement of blocks of characters is a 
surprisingly difficult concept to derive from the backend's 
description of the overlap of two documents.

Well, I have thought about it a great deal since then. 
The bad news is that this problem is even harder than I 
realized at Capabilities Review time; the good news is that 
it is soluble. In the upcoming series of messages I have 
enclosed 

- a more detailed description of the problem,  
- an algorithm that works well for most common text 
editing activities, 
- some samples of the algorithm in operation (the 
algorithm is implemented in Scheme, and will soon be 
available in my "current work" folder on Tops),
- deficiencies in the algorithm, which deficiencies I 
believe are important, and how to correct them, and
- ideas for later, for other kinds of version 
comparisons.

It will still require significant effort to build the 
software that displays version compare/merge. However, I 
now consider the scary aspects resolved. This issue is 
therefore removed from the Top Ten Trauma list and is 
downgraded to just another implementation chore.

Everyone is invited to read the algorithm except Mark 
Miller. Markm claims that Scheme is easy to read. 
Therefore, markm is not allowed to read the algorithm as I 
have expressed it in english until after he has read it in 
Scheme :-)

--marcs