Solving Merge Conflicts in Drupal -GS0C16 - Week 11

Submitted by rakesh on Wed, 08/10/2016 - 20:45

Project Details: The task is to solve the conflicts which may occur when two users try to push the same content with modifications in same piece of content/entity on their respective end. So far, we've a way to detect conflicts but not any to solve them. 

Solution we're working on: When a node is updated, a revision is created. Multiple revisions forms a graph with actual entity as root node. The simplest way to detect a merge conflict is to compare entities with their parent entity and figure out if both users have modified the same content or not. In case both of them have modified same content from an entity, there'd be a merge conflict otherwise we can simply merge their updates which would result in a new entity. Now, to compare these entities, we need a base entity as well with which these two updated revisions can be compared. For this purpose, we find lowest common ancestor from the graph (Aka LCA). After finding LCA, we can compare both of them with their common parent revision one by one. This process is known as  3-way merge algorithm. According to this algorithm, we shall compare two entities/revisions with another entity/revision to detect the modifications. While comparing, we just make sure that the same content is not modified from an entity in both the new revisions. If this happens, there'd be a merge conflict. To solve this merge conflict, a 3-pane window would be shown to user and let him decide which code he wants to keep and the other code (from other developer) would be discarded. You can find more about the project and the approach in the 3rd week blog post at my blog.

Progress so far: We have created two php libraries. One to find LCA from a directed acyclic graph and other one to perform a recursive 3-way merge algorithm. We have also created a module named "Conflict" which would find LCA and perform the merge algorithm on drupal entities. This module doesn't use these libraries we've created. Now we are writing code in Multiversion module which would use these library. We'd be able to detect LCA from complex graphs and resolve merge conflicts using Multiversion module once we've integrated these APIs with the module. Of course these features would be available to sites using Multiversion module. At the moment, we have successfully integrated LCA Library with Multiversion module. The next task would be to integrate Merge Library with the multiversion module as well.

Work we did last week: We implemented the basic functionality for finding lowest common ancestor from a graph of revision last week in multiversion module. The first task was to implement a method which could return a graph of revision Id's from the tree containing all information of an entity and it's revisions. We implemented `getGraph()` in multiversion module for this purpose. It takes uuid as input and returns a graph containing nodes keyed with revision ids. Once we had the graph of revision ID, we were able to use the relaxedws/lca library to find nearest common parent of two revisions in this graph of revision ids. We also implemented basic tests for the ComplexLcaResolver class to ensure that it was returning the correct LCA.

Work we did this week: Some tests were failing last week because the graph multiple nodes were having same revision Ids in the graph returned by the code we wrote last week in the ComplexLcaResolver.php .  This week, we tested our code in ComplexLcaResolver.php for multiple graphs and made sure that all the tests were passing. Because of some issues with my debugger, I was not able to debug the programme and despite of everything working fine, tests were failing. I spent almost 4 days trying to solve the issue but in the end, I was unable to solve the issue on my own. A big thanks to my super awesome mentors Dick Olsson, Andrei Jechiu and Tim Millwood, they pointed me in the right direction and the issue was resolved in next hour. However, the issue this time was not caused because of a silly mistake in my code. The most important thing I learnt this week was the importance of a working debugger. I learnt how a debugger can make life of a software developer much easier. The other thing I learnt is to follow the standards, even in documentation. Although it is said that a good code should be able to explain itself but for other cases, we must add proper documentation. Documentation standards are different for Drupal modules than the ones we used in PHP Library. I got to know about this after we're done with the tests issue.

Aim for the next week: The next step is to implement code which can use relaxedws/merge library to detect merge conflicts or to merge updates from multiple revisions into one. We've started our work with it already. We would have to convert entity objects into array first and then the merge library would loop over them to detect merge conflicts. After we're sure that there are no merge conflicts, we'd update (merge) the entities and convert them back to object. We would be using Serialization API for this. We'd be implementing tests for this class as well this week to make sure it's working fine.