research-article

Open access

IntelliMerge: a refactoring-aware software merging technique

Authors:

Guangtai Liang,

Qianxiang WangAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 3, Issue OOPSLA

Article No.: 170, Pages 1 - 28

https://doi.org/10.1145/3360596

Published: 10 October 2019 Publication History

Abstract

In modern software development, developers rely on version control systems like Git to collaborate in the branch-based development workflow. One downside of this workflow is the conflicts occurred when merging contributions from different developers: these conflicts are tedious and error-prone to be correctly resolved, reducing the efficiency of collaboration and introducing potential bugs. The situation becomes even worse, with the popularity of refactorings in software development and evolution, because current merging tools (usually based on the text or tree structures of source code) are unaware of refactorings. In this paper, we present IntelliMerge, a graph-based refactoring-aware merging algorithm for Java programs. We explicitly enhance this algorithm's ability in detecting and resolving refactoring-related conflicts. Through the evaluation on 1,070 merge scenarios from 10 popular open-source Java projects, we show that IntelliMerge reduces the number of merge conflicts by 58.90% comparing with GitMerge (the prevalent unstructured merging tool) and 11.84% comparing with jFSTMerge (the state-of-the-art semi-structured merging tool) without sacrificing the auto-merging precision (88.48%) and recall (90.22%). Besides, the evaluation of performance shows that IntelliMerge takes 539 milliseconds to process one merge scenario on the median, which indicates its feasibility in real-world applications.

References

[1]

Iftekhar Ahmed, Caius Brindescu, Umme Ayda Mannan, Carlos Jensen, and Anita Sarma. 2017. An empirical examination of the relationship between code smells and merge conflicts. In 2017 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM). IEEE, 58–67.

Digital Library

[2]

Everton LG Alves, Myoungkyu Song, and Miryung Kim. 2014. RefDistiller: a refactoring aware code review tool for inspecting manual refactoring edits. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 751–754.

Digital Library

[3]

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. ACM, 120–129.

Digital Library

[4]

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. ACM, 190–200.

Digital Library

[5]

Christian Bartelt. 2008. Consistence preserving model merge in collaborative development processes. In Proceedings of the 2008 international workshop on Comparison and versioning of software models. ACM, 13–18.

Digital Library

[6]

David Binkley, Susan Horwitz, and Thomas Reps. 1995. Program integration for languages with procedure calls. ACM Transactions on Software Engineering and Methodology (TOSEM) 4, 1 (1995), 3–35.

Digital Library

[7]

Christian Bird and Thomas Zimmermann. 2012. Assessing the value of branches with what-if analysis. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering. ACM, 45.

Digital Library

[8]

Caius Brindescu. 2018. How do developers resolve merge conflicts? an investigation into the processes, tools, and improvements. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM, 952–955.

Digital Library

[9]

Yuriy Brun, Reid Holmes, Michael D Ernst, and David Notkin. 2011. Proactive detection of collaboration conflicts. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering. ACM, 168–178.

Digital Library

[10]

Jim Buckley, Tom Mens, Matthias Zenger, Awais Rashid, and Günter Kniesel. 2005. Towards a taxonomy of software change. Journal of Software Maintenance and Evolution: Research and Practice 17, 5 (2005), 309–332.

Digital Library

[11]

Jim Buffenbarger. 1993. Syntactic software merging. In Software Configuration Management. Springer, 153–172.

[12]

Guilherme Cavalcanti, Paulo Borba, and Paola Accioly. 2017. Evaluating and improving semistructured merge. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 59.

Digital Library

[13]

Eunjong Choi, Kenji Fujiwara, Norihiro Yoshida, and Shinpei Hayashi. 2018. A survey of refactoring detection techniques based on change history analysis. arXiv preprint arXiv:1808.02320 (2018).

[14]

Danny Dig, Kashif, Tien N Nguyen, and Ralph Johnson. 2006a. Refactoring-aware software merging and configuration management. Acm Sigsoft Software Engineering Notes 31, 6 (2006), 1–2.

Digital Library

[15]

Danny Dig, Kashif Manzoor, Ralph Johnson, and Tien N. Nguyen. 2007. Refactoring-Aware Configuration Management for Object-Oriented Programs. In International Conference on Software Engineering.

[16]

Danny Dig, Kashif Manzoor, Ralph E Johnson, and Tien N Nguyen. 2008. Effective software merging in the presence of object-oriented refactorings. IEEE Transactions on Software Engineering 34, 3 (2008), 321–335.

Digital Library

[17]

Danny Dig, Tien N Nguyen, Kashif Manzoor, and Ralph Johnson. 2006b. MolhadoRef: a refactoring-aware software configuration management tool. In Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications. ACM, 732–733.

[18]

Hongfei Fan, Jiayao Gao, Hongming Zhu, Qin Liu, Yang Shi, and Chengzheng Sun. 2017a. Balancing Conflict Prevention and Concurrent Work in Real-Time Collaborative Programming. In Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing. ACM, 217–220.

Digital Library

[19]

Hongfei Fan and Chengzheng Sun. 2012. Dependency-based automatic locking for semantic conflict prevention in real-time collaborative programming. In Proceedings of the 27th Annual ACM Symposium on Applied Computing. ACM, 737–742.

Digital Library

[20]

Hongfei Fan, Hongming Zhu, Qin Liu, Yang Shi, and Chengzheng Sun. 2017b. Shared-locking for semantic conflict prevention in real-time collaborative programming. In 2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD). IEEE, 174–179.

[21]

Martin Fowler. 2002. Refactoring: Improving the Design of Existing Code. In Xp Universe First Agile Universe Conference on Extreme Programming Agile Methods-xp/agile Universe.

[22]

Judith E Grass. 1992. Cdiff: A syntax directed differencer for C++ programs. In C++ Conference, Portland, Oregon, 1992. 181–193.

[23]

Mário Luís Guimarães and António Rito Silva. 2012. Improving early detection of software merge conflicts. In Proceedings of the 34th International Conference on Software Engineering. IEEE Press, 342–352.

Digital Library

[24]

Daniel Jackson, David A Ladd, et al. 1994. Semantic Diff: A Tool for Summarizing the Effects of Modifications. In ICSM, Vol. 94. 243–252.

Digital Library

[25]

Bakhtiar Khan Kasi and Anita Sarma. 2013. Cassandra: Proactive conflict minimization through optimized task scheduling. In Proceedings of the 2013 International Conference on Software Engineering. IEEE Press, 732–741.

Digital Library

[26]

Miryung Kim, Matthew Gee, Alex Loh, and Napol Rachatasumrit. 2010. Ref-Finder: a refactoring reconstruction tool based on logic query templates. In Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering. ACM, 371–372.

Digital Library

[27]

Dimitrios S Kolovos, Richard F Paige, and Fiona AC Polack. 2006. Merging models with the epsilon merging language (EML). In International Conference on Model Driven Engineering Languages and Systems. Springer, 215–229.

Digital Library

[28]

Hoai Le Nguyen and Claudia-Lavinia Ignat. 2018. An Analysis of Merge Conflicts and Resolutions in Git-based Open Source Projects. Computer Supported Cooperative Work (CSCW) 27, 3-6 (2018), 741–765.

Digital Library

[29]

Olaf Leßenich, Sven Apel, and Christian Lengauer. 2015. Balancing precision and performance in structured merge. Automated Software Engineering 22, 3 (2015), 367–397.

Digital Library

[30]

Tancred Lindholm. 2004. A three-way merge for XML documents. In Proceedings of the 2004 ACM symposium on Document engineering. ACM, 1–10.

Digital Library

[31]

Ernst Lippe and Norbert Van Oosterom. 1992. Operation-based merging. In ACM SIGSOFT Software Engineering Notes, Vol. 17. ACM, 78–87.

Digital Library

[32]

Mehran Mahmoudi, Sarah Nadi, and Nikolaos Tsantalis. 2019. Are Refactorings to Blame? An Empirical Study of Refactorings in Merge Conflicts. In 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 151–162.

[33]

Akhil Mehra, John Grundy, and John Hosking. 2005. A generic approach to supporting diagram differencing and merging for collaborative design. In Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering. ACM, 204–213.

Digital Library

[34]

Gleiph Ghiotto Lima Menezes, Leonardo Gresta Paulino Murta, Marcio Oliveira Barros, and Andre Van Der Hoek. 2018. On the Nature of Merge Conflicts: a Study of 2,731 Open Source Java Projects Hosted by GitHub. IEEE Transactions on Software Engineering (2018).

[35]

Tom Mens. 1999. Conditional graph rewriting as a domain-independent formalism for software evolution. In International Workshop on Applications of Graph Transformations with Industrial Relevance. Springer, 127–143.

Digital Library

[36]

T. Mens. 2002. A state-of-the-art survey on software merging. IEEE Transactions on Software Engineering 28, 5 (2002), 449–462.

Digital Library

[37]

Tom Mens and Tom Tourwé. 2004. A survey of software refactoring. IEEE Transactions on software engineering 30, 2 (2004), 126–139.

Digital Library

[38]

Stas Negara, Nicholas Chen, Mohsen Vakilian, Ralph E Johnson, and Danny Dig. 2013. A comparative study of manual and automated refactorings. In European Conference on Object-Oriented Programming. Springer, 552–576.

Digital Library

[39]

Nan Niu, Steve Easterbrook, and Mehrdad Sabetzadeh. 2005. A category-theoretic approach to syntactic software merging. In 21st IEEE International Conference on Software Maintenance (ICSM’05). IEEE, 197–206.

Digital Library

[40]

Felix Schwägerl, Sabrina Uhrig, and Bernhard Westfechtel. 2015. A graph-based algorithm for three-way merging of ordered collections in EMF models. Science of Computer Programming 113 (2015), 51–81.

Digital Library

[41]

Sergio Segura, David Benavides, Antonio Ruiz-Cortés, and Pablo Trinidad. 2007. Automated merging of feature models using graph transformations. In International Summer School on Generative and Transformational Techniques in Software Engineering. Springer, 489–505.

[42]

Danilo Silva, Nikolaos Tsantalis, and Marco Tulio Valente. 2016. Why we refactor? confessions of github contributors. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 858–870.

Digital Library

[43]

Danilo Silva and Marco Tulio Valente. 2017. RefDiff: detecting refactorings in version histories. In Proceedings of the 14th International Conference on Mining Software Repositories. IEEE Press, 269–279.

Digital Library

[44]

Friedrich Steimann and Nils Kurowsky. 2019. Transactional Editing: Giving ACID to Programmers. In Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering. ACM.

Digital Library

[45]

Nikolaos Tsantalis, Matin Mansouri, Laleh M Eshkevari, Davood Mazinanian, and Danny Dig. 2018. Accurate and efficient refactoring detection in commit history. In Proceedings of the 40th International Conference on Software Engineering. ACM, 483–494.

Digital Library

[46]

Chuck Walrad and Darrel Strom. 2002. The importance of branching models in SCM. Computer 35, 9 (2002), 31–38.

Digital Library

[47]

Bernhard Westfechtel. 1991. Structure-oriented merging of revisions of software documents. In Software Configuration Management Workshop: Proceedings of the 3 rd international workshop on Software configuration management, Vol. 12. 68–79.

Digital Library

[48]

Fengmin Zhu and Fei He. 2018. Conflict resolution for structured merge via version space algebra. Proceedings of the ACM on Programming Languages 2, OOPSLA (2018), 166.

Digital Library

Cited By

Liu JZhang YLi YMa TDong W(2025)CIPAC: A framework of automated software construction based on collective intelligenceJournal of Systems and Software10.1016/j.jss.2025.112335222(112335)Online publication date: Apr-2025
https://doi.org/10.1016/j.jss.2025.112335
Liu WZhang WZhao HJin Z(2024)GABoost: Graph Alignment Boosting via Local Optimum EscapeProceedings of the ACM on Management of Data10.1145/36771352:4(1-26)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677135
Aldndni WServant FMeng NBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Understanding the Impact of Branch Edit Features for the Automatic Prediction of Merge Conflict ResolutionsProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644433(149-160)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644433
Show More Cited By

Index Terms

IntelliMerge: a refactoring-aware software merging technique
1. Software and its engineering
  1. Software notations and tools
    1. Software configuration management and version control systems

Recommendations

Anchored Text for Software Weaving and Merging
SSIRI '09: Proceedings of the 2009 Third IEEE International Conference on Secure Software Integration and Reliability Improvement

Text-based software merge/refactoring systems are predominantly used. Anchored text, a datatype with first-class location anchors and greater commutativity of software merge operations has been proposed recently. In this paper we develop anchored text ...
The impact of structure on software merging: semistructured versus structured merge
ASE '19: Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering

Merge conflicts often occur when developers concurrently change the same code artifacts. While state of practice unstructured merge tools (e.g. Git merge) try to automatically resolve merge conflicts based on textual similarity, semistructured and ...
Refactoring-aware versioning in Eclipse

To fully support refactorings in a team development environment we have implemented a refactoring-aware repository provider as an extension plug-in to the Java Development Tools in Eclipse. The versioning system treats refactorings as first-class ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 3, Issue OOPSLA

October 2019

2077 pages

EISSN:2475-1421

DOI:10.1145/3366395

Issue’s Table of Contents

Copyright © 2019 Owner/Author.

This work is licensed under a Creative Commons Attribution-NoDerivs International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2019

Published in PACMPL Volume 3, Issue OOPSLA

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
National Basic Research Program of China (973 Program)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
1,517
Total Downloads

Downloads (Last 12 months)273
Downloads (Last 6 weeks)31

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu JZhang YLi YMa TDong W(2025)CIPAC: A framework of automated software construction based on collective intelligenceJournal of Systems and Software10.1016/j.jss.2025.112335222(112335)Online publication date: Apr-2025
https://doi.org/10.1016/j.jss.2025.112335
Liu WZhang WZhao HJin Z(2024)GABoost: Graph Alignment Boosting via Local Optimum EscapeProceedings of the ACM on Management of Data10.1145/36771352:4(1-26)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3677135
Aldndni WServant FMeng NBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Understanding the Impact of Branch Edit Features for the Automatic Prediction of Merge Conflict ResolutionsProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644433(149-160)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644433
Hasan MTsantalis NAlikhanifard P(2024)Refactoring-aware Block Tracking in Commit HistoryIEEE Transactions on Software Engineering10.1109/TSE.2024.3484586(1-20)Online publication date: 2024
https://doi.org/10.1109/TSE.2024.3484586
Shen BMeng N(2024)ConflictBenchJournal of Systems and Software10.1016/j.jss.2024.112084214:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112084
Teles ASantos AStorm THirschfeld R(2023)Code Merging using Transformations and Member IdentityProceedings of the 2023 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3622758.3622891(71-88)Online publication date: 18-Oct-2023
https://dl.acm.org/doi/10.1145/3622758.3622891
Shen BGulzar MHe FMeng N(2023)A Characterization Study of Merge Conflicts in Java ProjectsACM Transactions on Software Engineering and Methodology10.1145/354694432:2(1-28)Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1145/3546944
Ellis MNadi SDig D(2023)Operation-Based Refactoring-Aware Merging: An Empirical EvaluationIEEE Transactions on Software Engineering10.1109/TSE.2022.322885149:4(2698-2721)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TSE.2022.3228851
Gonzalez SFraternali P(2023)Almost Rerere: Learning to Resolve Conflicts in Distributed ProjectsIEEE Transactions on Software Engineering10.1109/TSE.2022.321528949:4(2255-2271)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TSE.2022.3215289
Larsen SFalleri JBaudry BMonperrus M(2023)Spork: Structured Merge for Java With Formatting PreservationIEEE Transactions on Software Engineering10.1109/TSE.2022.314376649:1(64-83)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TSE.2022.3143766
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents