Search-Based Merge Conflict Resolution

• Heleno de Souza Campos Junior UFF
• Leonardo Gresta Paulino Murta UFF

DOI: https://doi.org/10.5753/cbsoft_estendido.2026.29848

Resumo

Merge conflicts are a pervasive bottleneck in collaborative software development. Automated approaches fall into two categories: merge approaches, which use language syntax to reduce the number of conflicts produced during the merge operation, and conflict resolution approaches, which receive an existing textual conflict as input and generate a valid resolution. Conflict resolution remains a challenging open problem; existing learning-based tools achieve strong results but require substantial training data and computational infrastructure. This paper presents a doctoral dissertation that applies search-based software engineering to conflict resolution. Targeting the 87% of resolutions that are formed by using lines already present in the conflicting versions [17], the dissertation delivers four integrated contributions: (i) MESTRE, a machine-learning classifier that predicts conflict resolution strategies with 80.8% accuracy and correctly resolves 70.5% of conflicts automatically; (ii) an empirical feasibility study revealing that structural properties of real resolutions reduce the search space by 89.2% while preserving 98.6% coverage; (iii) a lightweight evaluation function based on textual similarity to the conflicting parents, achieving Spearman correlation 𝜌 = 0.791 with resolution quality; and (iv) SBCR, a search-based resolution tool achieving median resolution similarity of 86.5% and exact matches in 25.2% of cases [5]; its empirical evaluation across more than 50,000 conflict chunks [11] further shows that SBCR is complementary to MergeGen [15], the current state-of-the-art learning-based approach, motivating hybrid resolution strategies.

Palavras-chave: Software merge, Conflict resolution, Search-based software engineering, Machine learning, Empirical software engineering

Referências

Paola Accioly, Paulo Borba, and Guilherme Cavalcanti. 2018. Understanding Semi-Structured Merge Conflict Characteristics in Open-Source Java Projects. Empirical Software Engineering 23, 4 (2018), 2051–2085. DOI: 10.1007/s10664-017-9586-1

Sven Apel, Olaf Leßenich, and Christian Lengauer. 2012. Structured Merge with Auto-Tuning: Balancing Precision and Performance. In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering (ASE ’12). Association for Computing Machinery, New York, NY, USA, 120–129.

Sven Apel, Jörg Liebig, Benjamin Brandl, Christian Lengauer, and Christian Kästner. 2011. Semistructured Merge: Rethinking Merge in Revision Control Systems. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE ’11). ACM, Szeged, Hungary, 190–200. DOI: 10.1145/2025113.2025141

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2024. How Code Composition Strategies Affect Merge Conflict Resolution? Journal of Software Engineering Research and Development 12, 1 (2024), 13:1–13:24. DOI: 10.5753/jserd.2024.3638

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2026. Towards a Feasible Evaluation Function for Search-Based Merge Conflict Resolution. ACM Transactions on Software Engineering and Methodology 35, 5, Article 131 (April 2026), 35 pages. DOI: 10.1145/3748256

Heleno de S. Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2022. Towards Merge Conflict Resolution by Combining Existing Lines of Code. In Proceedings of the 36th Brazilian Symposium on Software Engineering (SBES ’22). ACM, Maringá, Brazil, 425–434. DOI: 10.1145/3555228.3555229 Distinguished Paper Award.

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2022. Artifacts for the SBES 2022 Submission on the Analysis of Merge Conflicts Resolved with Combination of the Conflicting Lines. DOI: 10.6084/m9.figshare.19705600

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2023. Artifacts for the JSERD Submission: How Code Composition Strategies Affect Merge Conflict Resolution? DOI: 10.6084/m9.figshare.24012579

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2024. Merge Conflicts Dataset Used in SBES 2022 Paper. DOI: 10.6084/m9.figshare.26831818

Heleno de Souza Campos Junior, Gleiph Ghiotto L. de Menezes, Márcio de Oliveira Barros, André van der Hoek, and Leonardo Gresta Paulino Murta. 2025. SBCR: Search-Based Conflict Resolution – Source Code and Supplementary Material. [link].

Heleno de Souza Campos Junior and Leonardo Gresta Paulino Murta. 2026. LLM-based vs. Search-based Merge Conflict Resolution: An Empirical Study of Competing Paradigms. [link]. arXiv:2605.16646 [cs.SE]

Guilherme Cavalcanti, Paulo Borba, and Paola Accioly. 2017. Evaluating and Improving Semistructured Merge. Proceedings of the ACM on Programming Languages (OOPSLA) 1 (2017), 59:1–59:27.

Guilherme Cavalcanti, Paulo Borba, Leonardo dos Anjos, and Jonatas Clementino. 2024. Semistructured Merge with Language-Specific Syntactic Separators. In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering (ASE ’24). IEEE, 1032–1043.

Elizabeth Dinella, Todd Mytkowicz, Alexey Svyatkovskiy, Christian Bird, Mayur Naik, and Shuvendu Lahiri. 2023. DeepMerge: Learning to Merge Programs. IEEE Transactions on Software Engineering 49, 4 (2023), 1599–1614. DOI: 10.1109/TSE.2022.3183955

Jinhao Dong, Qihao Zhu, Zeyu Sun, Yiling Lou, and Dan Hao. 2023. Merge Conflict Resolution: Classification or Generation?. In Proceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering (ASE ’23). IEEE, Luxembourg, Luxembourg, 1652–1664. DOI: 10.1109/ASE56229.2023.00155

Paulo Elias, Heleno de S. Campos Junior, Eduardo Ogasawara, and Leonardo Gresta Paulino Murta. 2023. Towards Accurate Recommendations of Merge Conflicts Resolution Strategies. Information and Software Technology 164 (2023), 107332. DOI: 10.1016/j.infsof.2023.107332

Gleiph Ghiotto, Leonardo Murta, Márcio Barros, and André van der Hoek. 2020. On the Nature of Merge Conflicts: A Study of 2,731 Open Source Java Projects Hosted by GitHub. IEEE Transactions on Software Engineering 46, 8 (2020), 892–915. DOI: 10.1109/TSE.2018.2871083

Mark Harman and Bryan F. Jones. 2001. Search-Based Software Engineering. Information and Software Technology 43, 14 (2001), 833–839. DOI: 10.1016/S0950-5849(01)00189-6

Bakhtiar Khan Kasi and Anita Sarma. 2013. Cassandra: Proactive Conflict Minimization through Optimized Task Scheduling. In Proceedings of the 35th International Conference on Software Engineering (ICSE ’13). IEEE, San Francisco, CA, USA, 732–741. DOI: 10.1109/ICSE.2013.6606619

Tom Mens. 2002. A State-of-the-Art Survey on Software Merging. IEEE Transactions on Software Engineering 28, 5 (2002), 449–462. DOI: 10.1109/TSE.2002.1000449

Nicholas Nelson, Caius Brindescu, Shane McKee, Anita Sarma, and Danny Dig. 2019. The Life-Cycle of Merge Conflicts: Processes, Barriers, and Strategies. Empirical Software Engineering 24, 5 (2019), 2863–2906. DOI: 10.1007/s10664-018-9674-x

Shaun Phillips, Jonathan Sillito, and Rob Walker. 2011. Branching and Merging: An Investigation into Current Version Control Practices. In Proceedings of the 4th InternationalWorkshop on Cooperative and Human Aspects of Software Engineering (CHASE ’11). Association for Computing Machinery, New York, NY, USA, 9–15.

John W Ratcliff, David E Metzener, et al. 1988. Pattern matching: The gestalt approach. Dr. Dobb’s Journal 13, 7 (1988), 46.

Stuart Russell and Peter Norvig. 2020. Artificial Intelligence: A Modern Approach (4 ed.). Pearson.

Alexey Svyatkovskiy, Sarah Fakhoury, Negar Ghorbani, Todd Mytkowicz, Elizabeth Dinella, Christian Bird, Jinu Jang, Neel Sundaresan, and Shuvendu K. Lahiri. 2022. Program Merge Conflict Resolution via Neural Transformers. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’22). ACM, Singapore, Singapore, 822–833. DOI: 10.1145/3540250.3549163

Jialu Zhang, Todd Mytkowicz, Mike Kaufman, Ruzica Piskac, and Shuvendu K. Lahiri. 2022. Using Pre-trained Language Models to Resolve Textual and Semantic Merge Conflicts. In Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’22). Association for Computing Machinery, New York, NY, USA, 77–88.