Implementing real-time collaboration in TouchDevelop using AST merges

Collaborating on a piece of code is notoriously difficult when the number of people involved goes above 1. In particular, every computer programmer dreads the “merge conflict”, a brutal, unforgiving experience, where they must reconcile their changes with someone else’s. If offline collaboration is already so painful, real-time collaboration seems even less of an option. It turns out, though, that by reasoning on changes at the level of the program AST, rather than the program text, we can devise a new conflict-free merge algorithm. The algorithm is particularly well-suited to real-time collaboration: we implemented it in the TouchDevelop web programming environment and dub the algorithm diffTree.