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

作者：Schwaegerl Felix; Uhrig Sabrina; Westfechtel Bernhard

来源：Science of Computer Programming, 2015, 113: 51-81.

DOI：10.1016/j.scico.2015.02.008

• Model-driven software engineering
• EMF models
• Version control
• Three-way merging
• Graph algorithm

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 a(1) and a(2) 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 a(1) and a(2). 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.

• 出版日期2015-12-1