A Graph-based Algorithm for Three-way Merging of Ordered Collections in EMF Models

Felix Schwägerl, Sabrina Uhrig, Bernhard Westfechtel

2014

Abstract

Version control for models is not yet supported in an adequate way. In this paper, we address three-way merging of model versions. Based on a common base version b, two alternative versions a1 and a2 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 a1 and a2. We present a graph algorithm to solve an important subproblem which occurs in three-way model merging: merging of (linearly) ordered collections. To create the merged version, a generalized topological sort is performed. Conflicts occur if 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 merge of versions of EMF models being instances of arbitrary Ecore models. By taking arbitrary move operations into account, the algorithm considerably goes beyond the functionality of contemporary merge tools which are based on common subsequences and thus cannot adequately handle move operations.

Paper Citation

in Harvard Style

Schwägerl F., Uhrig S. and Westfechtel B. (2014). A Graph-based Algorithm for Three-way Merging of Ordered Collections in EMF Models . In Proceedings of the 2nd International Conference on Model-Driven Engineering and Software Development - Volume 1: MODELSWARD, ISBN 978-989-758-007-9, pages 41-54. DOI: 10.5220/0004702100410054

in Bibtex Style

@conference{modelsward14,
author={Felix Schwägerl and Sabrina Uhrig and Bernhard Westfechtel},
title={A Graph-based Algorithm for Three-way Merging of Ordered Collections in EMF Models},
booktitle={Proceedings of the 2nd International Conference on Model-Driven Engineering and Software Development - Volume 1: MODELSWARD,},
year={2014},
pages={41-54},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004702100410054},
isbn={978-989-758-007-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 2nd International Conference on Model-Driven Engineering and Software Development - Volume 1: MODELSWARD,
TI - A Graph-based Algorithm for Three-way Merging of Ordered Collections in EMF Models
SN - 978-989-758-007-9
AU - Schwägerl F.
AU - Uhrig S.
AU - Westfechtel B.
PY - 2014
SP - 41
EP - 54
DO - 10.5220/0004702100410054