Last Diff Analyzer: Multi-language Automated Approver for Behavior-Preserving Code Revisions
Pages 1693 - 1704
Abstract
Code review is a crucial step in ensuring the quality and maintainability of software systems. However, this process can be time-consuming and resource-intensive, especially in large-scale projects where a significant number of code changes are submitted every day. Fortunately, not all code changes require human reviews, as some may only contain syntactic modifications that do not alter the behavior of the system, such as format changes, variable / function renamings, and constant extractions.
In this paper, we propose a multi-language automated code approver — Last Diff Analyzer for Go and Java, which is able to detect if a reviewable incremental unit of code change (diff) contains only changes that do not modify system behavior. It is built on top of a novel multi-language static analysis framework that unifies common features of multiple languages while keeping unique language constructs separate. This makes it easy to extend to other languages such as TypeScript, Kotlin, Swift, and others. Besides skipping unnecessary code reviews, Last Diff Analyzer could be further applied to skip certain resource-intensive end-to-end (E2E) tests for auto-approved diffs for significant reduction of resource usage. We have deployed the analyzer at scale within Uber, and data collected in production shows that approximately 15% of analyzed diffs are auto-approved weekly for code reviews. Furthermore, 13.5% reduction in server node usage dedicated to E2E tests (measured by number of executed E2E tests) is observed as a result of skipping E2E tests, compared to the node usage if Last Diff Analyzer were not enabled.
References
[1]
Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman. 2007. Compilers: principles, techniques, and tools. 2, Addison-wesley Reading.
[2]
Everton L. G. 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, (FSE-22), Hong Kong, China, November 16 - 22, 2014, Shing-Chi Cheung, Alessandro Orso, and Margaret-Anne D. Storey (Eds.). ACM, 751–754. https://doi.org/10.1145/2635868.2661674
[3]
Taweesup Apiwattanapong, Alessandro Orso, and Mary Jean Harrold. 2004. A Differencing Algorithm for Object-Oriented Programs. In 19th IEEE International Conference on Automated Software Engineering (ASE 2004), 20-25 September 2004, Linz, Austria. IEEE Computer Society, 2–13. https://doi.org/10.1109/ASE.2004.10015
[4]
John D. Backes, Suzette Person, Neha Rungta, and Oksana Tkachuk. 2013. Regression Verification Using Impact Summaries. In Model Checking Software - 20th International Symposium, SPIN 2013, Stony Brook, NY, USA, July 8-9, 2013. Proceedings, Ezio Bartocci and C. R. Ramakrishnan (Eds.) (Lecture Notes in Computer Science, Vol. 7976). Springer, 99–116. https://doi.org/10.1007/978-3-642-39176-7_7
[5]
Ira D. Baxter, Andrew Yahin, Leonardo Mendonça de Moura, Marcelo Sant’Anna, and Lorraine Bier. 1998. Clone Detection Using Abstract Syntax Trees. In 1998 International Conference on Software Maintenance, ICSM 1998, Bethesda, Maryland, USA, November 16-19, 1998. IEEE Computer Society, 368–377. https://doi.org/10.1109/ICSM.1998.738528
[6]
Oren Ben-Kiki, Clark Evans, and Brian Ingerson. 2009. Yaml ain’t markup language (yaml™ ) version 1.1. Working Draft 2008, 5 (2009), 11.
[7]
Zhiyuan Chen, Hai-Feng Guo, and Myoungkyu Song. 2018. Improving regression test efficiency with an awareness of refactoring changes. Inf. Softw. Technol., 103 (2018), 174–187. https://doi.org/10.1016/j.infsof.2018.07.003
[8]
Berkeley R. Churchill, Oded Padon, Rahul Sharma, and Alex Aiken. 2019. Semantic program alignment for equivalence checking. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix, AZ, USA, June 22-26, 2019, Kathryn S. McKinley and Kathleen Fisher (Eds.). ACM, 1027–1040. https://doi.org/10.1145/3314221.3314596
[9]
Danny Dig, Can Comertoglu, Darko Marinov, and Ralph E. Johnson. 2006. Automated Detection of Refactorings in Evolving Components. In ECOOP 2006 - Object-Oriented Programming, 20th European Conference, Nantes, France, July 3-7, 2006, Proceedings, Dave Thomas (Ed.) (Lecture Notes in Computer Science, Vol. 4067). Springer, 404–428. https://doi.org/10.1007/11785477_24
[10]
Apache Foundation. 2023. Thrift. https://thrift.apache.org/
[11]
Xi Ge, Saurabh Sarkar, and Emerson R. Murphy-Hill. 2014. Towards refactoring-aware code review. In Proceedings of the 7th International Workshop on Cooperative and Human Aspects of Software Engineering, CHASE 2014, Hyderabad, India, June 2-3, 2014, Helen Sharp, Rafael Prikladnicki, Andrew Begel, and Cleidson R. B. de Souza (Eds.). ACM, 99–102. https://doi.org/10.1145/2593702.2593706
[12]
Xi Ge, Saurabh Sarkar, Jim Witschey, and Emerson R. Murphy-Hill. 2017. Refactoring-aware code review. In 2017 IEEE Symposium on Visual Languages and Human-Centric Computing, VL/HCC 2017, Raleigh, NC, USA, October 11-14, 2017, Austin Z. Henley, Peter Rogers, and Anita Sarma (Eds.). IEEE Computer Society, 71–79. https://doi.org/10.1109/VLHCC.2017.8103453
[13]
GitHub. 2022. Semantic. https://github.com/github/semantic
[14]
GitHub. 2023. About Pull Request Reviews (Documentation). https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests
[15]
GitHub. 2023. GitHub. https://github.com/
[16]
GitLab. 2023. GitLab. https://gitlab.com/
[17]
Benny Godlin and Ofer Strichman. 2009. Regression verification. In Proceedings of the 46th Design Automation Conference, DAC 2009, San Francisco, CA, USA, July 26-31, 2009. ACM, 466–471. https://doi.org/10.1145/1629911.1630034
[18]
Google, Inc. 2023. Go Modules Reference. https://go.dev/ref/mod
[19]
Google, Inc. 2023. Protobuf. https://github.com/protocolbuffers/protobuf
[20]
Google, Inc. 2023. Starlark Language. https://github.com/bazelbuild/starlark
[21]
James Gosling, Bill Joy, Guy Steele, and Gilad Bracha. 2000. The Java language specification. Addison-Wesley Professional.
[22]
Google Inc. 2023. Bazel. https://github.com/bazelbuild/bazel
[23]
Google Inc. 2023. Bazel Gazelle. https://github.com/bazelbuild/bazel-gazelle
[24]
Uber Technologies Inc. 2023. Zap. https://github.com/uber-go/zap
[25]
ISO/IEC. 2016. ISO/IEC 9075-1: 2016,“SQL-Part 1: Framework”.
[26]
J. Howard Johnson. 1993. Identifying redundancy in source code using fingerprints. In Proceedings of the 1993 Conference of the Centre for Advanced Studies on Collaborative Research, October 24-28, 1993, Toronto, Ontario, Canada, 2 Volumes, Ann Gawman, Evelyn Kidd, and Per-Åke Larson (Eds.). IBM, 171–183. https://dl.acm.org/citation.cfm?id=962305
[27]
Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue. 2002. CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code. IEEE Trans. Software Eng., 28, 7 (2002), 654–670. https://doi.org/10.1109/TSE.2002.1019480
[28]
Moritz Kiefer, Vladimir Klebanov, and Mattias Ulbrich. 2016. Relational Program Reasoning Using Compiler IR. In Verified Software. Theories, Tools, and Experiments - 8th International Conference, VSTTE 2016, Toronto, ON, Canada, July 17-18, 2016, Revised Selected Papers, Sandrine Blazy and Marsha Chechik (Eds.) (Lecture Notes in Computer Science, Vol. 9971). 149–165. https://doi.org/10.1007/978-3-319-48869-1_12
[29]
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 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2010, Santa Fe, NM, USA, November 7-11, 2010, Gruia-Catalin Roman and André van der Hoek (Eds.). ACM, 371–372. https://doi.org/10.1145/1882291.1882353
[30]
Miryung Kim and David Notkin. 2009. Discovering and representing systematic code changes. In 31st International Conference on Software Engineering, ICSE 2009, May 16-24, 2009, Vancouver, Canada, Proceedings. IEEE, 309–319. https://doi.org/10.1109/ICSE.2009.5070531
[31]
Raghavan Komondoor and Susan Horwitz. 2001. Using Slicing to Identify Duplication in Source Code. In Static Analysis, 8th International Symposium, SAS 2001, Paris, France, July 16-18, 2001, Proceedings, Patrick Cousot (Ed.) (Lecture Notes in Computer Science, Vol. 2126). Springer, 40–56. https://doi.org/10.1007/3-540-47764-0_3
[32]
Shuvendu K. Lahiri, Chris Hawblitzel, Ming Kawaguchi, and Henrique Rebêlo. 2012. SYMDIFF: A Language-Agnostic Semantic Diff Tool for Imperative Programs. In Computer Aided Verification - 24th International Conference, CAV 2012, Berkeley, CA, USA, July 7-13, 2012 Proceedings, P. Madhusudan and Sanjit A. Seshia (Eds.) (Lecture Notes in Computer Science, Vol. 7358). Springer, 712–717. https://doi.org/10.1007/978-3-642-31424-7_54
[33]
Liuqing Li, He Feng, Wenjie Zhuang, Na Meng, and Barbara G. Ryder. 2017. CCLearner: A Deep Learning-Based Clone Detection Approach. In 2017 IEEE International Conference on Software Maintenance and Evolution, ICSME 2017, Shanghai, China, September 17-22, 2017. IEEE Computer Society, 249–260. https://doi.org/10.1109/ICSME.2017.46
[34]
Viktor Malík and Tomás Vojnar. 2021. Automatically Checking Semantic Equivalence between Versions of Large-Scale C Projects. In 14th IEEE Conference on Software Testing, Verification and Validation, ICST 2021, Porto de Galinhas, Brazil, April 12-16, 2021. IEEE, 329–339. https://doi.org/10.1109/ICST49551.2021.00045
[35]
Michael Kerrisk. 2010. The Linux programming interface: a Linux and UNIX system programming handbook. https://man7.org/linux/man-pages/man1/diff.1.html
[36]
Suzette Person, Matthew B. Dwyer, Sebastian G. Elbaum, and Corina S. Pasareanu. 2008. Differential symbolic execution. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2008, Atlanta, Georgia, USA, November 9-14, 2008, Mary Jean Harrold and Gail C. Murphy (Eds.). ACM, 226–237. https://doi.org/10.1145/1453101.1453131
[37]
Phacility, Inc. 2023. Phabricator. https://www.phacility.com/phabricator/
[38]
Kyle Prete, Napol Rachatasumrit, Nikita Sudan, and Miryung Kim. 2010. Template-based reconstruction of complex refactorings. In 26th IEEE International Conference on Software Maintenance (ICSM 2010), September 12-18, 2010, Timisoara, Romania, Radu Marinescu, Michele Lanza, and Andrian Marcus (Eds.). IEEE Computer Society, 1–10. https://doi.org/10.1109/ICSM.2010.5609577
[39]
David A. Ramos and Dawson R. Engler. 2011. Practical, Low-Effort Equivalence Verification of Real Code. In Computer Aided Verification - 23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings, Ganesh Gopalakrishnan and Shaz Qadeer (Eds.) (Lecture Notes in Computer Science, Vol. 6806). Springer, 669–685. https://doi.org/10.1007/978-3-642-22110-1_55
[40]
Vaibhav Saini, Farima Farmahinifarahani, Yadong Lu, Pierre Baldi, and Cristina V. Lopes. 2018. Oreo: detection of clones in the twilight zone. In Proceedings of the 2018 ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/SIGSOFT FSE 2018, Lake Buena Vista, FL, USA, November 04-09, 2018, Gary T. Leavens, Alessandro Garcia, and Corina S. Pasareanu (Eds.). ACM, 354–365. https://doi.org/10.1145/3236024.3236026
[41]
Gerard Salton and Michael McGill. 1984. Introduction to Modern Information Retrieval. McGraw-Hill Book Company. isbn:0-07-054484-0
[42]
Danilo Silva, João Paulo da Silva, Gustavo Jansen de Souza Santos, Ricardo Terra, and Marco Túlio Valente. 2021. RefDiff 2.0: A Multi-Language Refactoring Detection Tool. IEEE Trans. Software Eng., 47, 12 (2021), 2786–2802. https://doi.org/10.1109/TSE.2020.2968072
[43]
Danilo Silva and Marco Túlio Valente. 2017. RefDiff: detecting refactorings in version histories. In Proceedings of the 14th International Conference on Mining Software Repositories, MSR 2017, Buenos Aires, Argentina, May 20-28, 2017, Jesús M. González-Barahona, Abram Hindle, and Lin Tan (Eds.). IEEE Computer Society, 269–279. https://doi.org/10.1109/MSR.2017.14
[44]
The Free Software Foundation (FSF). 2021. GNU diffutils - Comparing and Merging Files. https://www.gnu.org/software/diffutils/manual/
[45]
Tree-sitter. 2023. Tree-sitter. https://github.com/tree-sitter/tree-sitter
[46]
Nikolaos Tsantalis, Ameya Ketkar, and Danny Dig. 2022. RefactoringMiner 2.0. IEEE Trans. Software Eng., 48, 3 (2022), 930–950. https://doi.org/10.1109/TSE.2020.3007722
[47]
Nikolaos Tsantalis, Matin Mansouri, Laleh Mousavi 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, ICSE 2018, Gothenburg, Sweden, May 27 - June 03, 2018, Michel Chaudron, Ivica Crnkovic, Marsha Chechik, and Mark Harman (Eds.). ACM, 483–494. https://doi.org/10.1145/3180155.3180206
[48]
Kaiyuan Wang, Chenguang Zhu, Ahmet Çelik, Jongwook Kim, Don S. Batory, and Milos Gligoric. 2018. Towards refactoring-aware regression test selection. In Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, Gothenburg, Sweden, May 27 - June 03, 2018, Michel Chaudron, Ivica Crnkovic, Marsha Chechik, and Mark Harman (Eds.). ACM, 233–244. https://doi.org/10.1145/3180155.3180254
[49]
Zhenchang Xing and Eleni Stroulia. 2005. UMLDiff: an algorithm for object-oriented design differencing. In 20th IEEE/ACM International Conference on Automated Software Engineering (ASE 2005), November 7-11, 2005, Long Beach, CA, USA, David F. Redmiles, Thomas Ellman, and Andrea Zisman (Eds.). ACM, 54–65. https://doi.org/10.1145/1101908.1101919
[50]
Zhenchang Xing and Eleni Stroulia. 2006. Refactoring Detection based on UMLDiff Change-Facts Queries. In 13th Working Conference on Reverse Engineering (WCRE 2006), 23-27 October 2006, Benevento, Italy. IEEE Computer Society, 263–274. https://doi.org/10.1109/WCRE.2006.48
[51]
Wuu Yang. 1991. Identifying Syntactic differences Between Two Programs. Softw. Pract. Exp., 21, 7 (1991), 739–755. https://doi.org/10.1002/spe.4380210706
Index Terms
- Last Diff Analyzer: Multi-language Automated Approver for Behavior-Preserving Code Revisions
Recommendations
Static program analysis of embedded executable assembly code
CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systemsWe consider the problem of automatically checking if coding standards have been followed in the development of embedded applications. The problem arises from practical considerations because DSP chip manufacturers (in our case Texas Instruments) want ...
Automated atomicity-violation fixing
PLDI '11Fixing software bugs has always been an important and time-consuming process in software development. Fixing concurrency bugs has become especially critical in the multicore era. However, fixing concurrency bugs is challenging, in part due to non-...
Automated atomicity-violation fixing
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and ImplementationFixing software bugs has always been an important and time-consuming process in software development. Fixing concurrency bugs has become especially critical in the multicore era. However, fixing concurrency bugs is challenging, in part due to non-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
2215 pages
ISBN:9798400703270
DOI:10.1145/3611643
- General Chair:
- Satish Chandra,
- Program Chairs:
- Kelly Blincoe,
- Paolo Tonella
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 November 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
Conference
ESEC/FSE '23
Sponsor:
ESEC/FSE '23: 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering
December 3 - 9, 2023
CA, San Francisco, USA
Acceptance Rates
Overall Acceptance Rate 112 of 543 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 272Total Downloads
- Downloads (Last 12 months)271
- Downloads (Last 6 weeks)17
Reflects downloads up to 16 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in