A Delta-Oracle for Fast Model Merge Conflict Estimation using Sketch-Based Critical Pair Analysis

Reviewed Paper In Proceedings

Author(s):Karl Kegel, Andreas Domanowski, Kevin Feichtinger, Romain Pascual, and Uwe Aßmann
In:Proceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems
Publisher:Association for Computing Machinery
Series:MODELS Companion '24
Year:2024
Pages:1046-1055
DOI:10.1145/3652620.3688341
Keywords: merge conflict estimation critical pair analysis oracle algorithm

Abstract

Conflicting changes are a major challenge in branch-based development and modeling. State-of-the-art research proposes continuous analysis via attempted three-way merges to find potential merge conflicts early on. These approaches are computation-heavy due to the necessity of comparing all variant combinations, ideally for each change. This work proposes a conflict approximation algorithm (oracle) for quick feedback. The oracle approximates conflicts using critical pair analysis on tracked delta sequences, providing a quick feedback loop. The oracle is paired with a classical slow-but-precise full model comparison algorithm, which is run occasionally to validate the oracle's results. This work contributes the Sketch-based Critical Pair Analysis (SCPA) approach for fast merge conflict estimation. SCPA's runtime depends only on the number of changes and not the model size. We evaluate SCPA against EMFCompare in different simulated model evolution scenarios. We found that for the investigated model sizes, SCPA is faster by a magnitude while the number of found conflicts strongly correlates with EMFCompare.

BibTeX

@InProceedings{ME2024,
  author       = {Karl Kegel and 
                  Andreas Domanowski and 
                  Kevin Feichtinger and 
                  Romain Pascual and
                  Uwe A\ss{}mann},
  title        = {A Delta-Oracle for Fast Model Merge Conflict Estimation
                  using Sketch-Based Critical Pair Analysis},
  year         = {2024},
  isbn         = {9798400706226},
  publisher    = {Association for Computing Machinery},
  address      = {New York, NY, USA},
  doi          = {10.1145/3652620.3688341},
  abstract     = {Conflicting changes are a major challenge in
                  branch-based development and modeling. State-of-the-art
                  research proposes continuous analysis via attempted
                  three-way merges to find potential merge conflicts early
                  on. These approaches are computation-heavy due to the
                  necessity of comparing all variant combinations, ideally
                  for each change. This work proposes a conflict
                  approximation algorithm (oracle) for quick feedback. The
                  oracle approximates conflicts using critical pair
                  analysis on tracked delta sequences, providing a quick
                  feedback loop. The oracle is paired with a classical
                  slow-but-precise full model comparison algorithm, which
                  is run occasionally to validate the oracle's results.
                  This work contributes the Sketch-based Critical Pair
                  Analysis (SCPA) approach for fast merge conflict
                  estimation. SCPA's runtime depends only on the number of
                  changes and not the model size. We evaluate SCPA against
                  EMFCompare in different simulated model evolution
                  scenarios. We found that for the investigated model
                  sizes, SCPA is faster by a magnitude while the number of
                  found conflicts strongly correlates with EMFCompare.},
  booktitle    = {Proceedings of the ACM/IEEE 27th International
                  Conference on Model Driven Engineering Languages and
                  Systems},
  pages        = {1046--1055},
  numpages     = {10},
  keywords     = {merge conflict estimation, critical pair analysis,
                  oracle algorithm},
  venue        = {Linz, Austria},
  eventdate    = {2024-09-22/2024-09-27},
  series       = {MODELS Companion '24}
}