February 6, 2013
For a class called 6.033 (Computer Systems Engineering) at MIT, I was required to design a collaborative, distributed text editor. It’s supposed to work like Git—if two users make concurrent changes to the document, the editor should try to automatically merge the two changes (or report a merge conflict).
However, the merge algorithm had to be more intelligent than Git’s line-by-line diff merger—if one user moved a paragraph of text (for example) to a different location in the document, and another user concurrently edited the wording of that paragraph, then the merger should be able to detect that the paragraph was both edited and moved, automatically.
I wanted the merge algorithm to be even more general. It shouldn’t have any notion of “paragraph” or “sentence.” Rather, if any piece of text is moved and edited concurrently, this should be resolved automatically. Furthermore, it should work even if two (or more) users edit the text and another user user moves it. Moreover, I wanted it to even work recursively—for example, if one user moves a chapter in a book, while another user moves a paragraph within that chapter, and yet another user moves a sentence within that paragraph, and still another user changes the wording of that sentence, the merge algorithm should be able to handle all of that without any user intervention, and without any notion of “chapter,” “paragraph,” “sentence,” etc. It should just “do the right thing,” whether you’re working on code, a novel, a scientific paper, or any other text-based document.
While I wasn’t required to actually implement the algorithm, I ended up doing it in Python anyway. I later discovered that I had independently invented the operational transformation.