A graph-based algorithm for three-way merging of ordered collections in EMF models

• We present an algorithm for three-way merging of ordered collections.
• Our algorithm performs a topological sort on a combination of linearly ordered input graphs.
• Within the input sequences, arbitrary moves are allowed.
• The implementation of our algorithm targets EMF models.
• The user is involved only in the case of primary conflicts.

In EMF models, ordered collections appear as the values of multi-valued structural features. Traditional, text-based version control systems do not sufficiently support three-way merging of ordered collections inside EMF models since they cannot guarantee a consistent result. The operation three-way merging is defined as follows: based on a common base version b  , two alternative versions a1a1 and a2a2 were developed by copying and modifying the base version. To reconcile these changes, a merged version m   is to be created as a common successor of a1a1 and a2a2. In this paper, we present a graph algorithm to solve the problem of three-way merging of ordered collections in EMF models. Each version of a collection can be represented by means of a linearly ordered graph. To create the merged version, these graphs are combined to a merged collection graph using set formula. To create the merged collection, a generalized topological sort is performed on the merged collection graph. Conflicts occur in case the order of elements cannot be deduced automatically; these conflicts are resolved either interactively or by default rules. We have implemented the merge algorithm in our tool BTMerge, which performs a consistency-preserving three-way merge of versions of EMF models being instances of arbitrary Ecore models. Our implementation relies on an alternative form of representing multiple versions of a collection, namely a versioned collection graph which forms a superimposition of collection versions. The algorithm presented here is purely state-based. Matching and merging of collections are clearly separated sub-problems. Insertions and deletions performed on the elements of the collection are propagated into the merged version in a consistent way. Our algorithm makes only minimal assumptions with regard to the underlying product model and thus may be applied to ordered collections inside plain text or XML files. By taking arbitrary move operations into account, the algorithm considerably goes beyond the functionality of contemporary merge tools which cannot adequately handle move operations.