Towards AST-based Collaborative Editing

Handheld devices and cloud-connected applications are now commonplace. Even complex software development tasks are moving into the mobile arena, as exemplified by “on-thego” code-editing with applications like Visual Studio Online. Further still, there is a trend towards real-time components in collaborative software development, with platforms like Google Docs and MS Office Online enabling limited forms of real-time collaborative document development.

However, these platforms are unattractive for collaborative software development since they don’t recognize and maintain code structure. Additionally, these systems are built atop ad-hoc algorithms or incredibly complex/fragile techniques for ensuring eventual consistency of documents.

We address these problems by providing a clean framework for realtime collaborative editing of source code within an online structured editor. We first develop a conflict-free three-way merge algorithm for program ASTs, which behaves intuitively to developers, and preserves syntactic correctness. We then show how this merge functionality can be used in conjunction with the Cloud Types eventual consistency model to enable seamless realtime collaboration.

We have implemented our system in the TouchDevelop online programming environment. The UI now allows a user to select another user’s code, and merge it into their current application (patch merge). We have also implemented basic realtime collaborative editing, allowing users to edit the same piece of code on multiple devices simultaneously.