{"id":765556,"date":"2021-08-11T09:14:49","date_gmt":"2021-08-11T16:14:49","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=765556"},"modified":"2021-08-11T09:14:51","modified_gmt":"2021-08-11T16:14:51","slug":"safe-program-merges-at-scale-a-grand-challenge-for-program-repair-research","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/safe-program-merges-at-scale-a-grand-challenge-for-program-repair-research\/","title":{"rendered":"Safe program merges at scale: A grand challenge for program repair research"},"content":{"rendered":"\n<figure class=\"wp-block-image alignwide size-large\"><img decoding=\"async\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-scaled.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<p>Since the computing world began embracing an open-source approach to programming, building software has become increasingly collaborative. Members of development teams with as few as two developers and as many as thousands are simultaneously editing different components in creating software systems and keeping them functioning optimally, and <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Merge_(version_control)\">a three-way merge<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> is <em>the<\/em> mechanism for integrating changes from these individual contributors. But with so many people independently altering code, it\u2019s unsurprising that updates don\u2019t always synchronize, resulting in <em>bad merges<\/em>.<\/p>\n\n\n\n<p>Bad merges can take a range of forms. For example, textual merge conflicts occur when the changes from two branches can\u2019t be integrated by the default text-based merge algorithms used by version control systems such as Git, Concurrent Versions System (CVS), and Subversion. Most such conflicts are spurious from the perspective of their effect on program execution and often originate from the use of a <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/Diff3\">40-year-old diff3 algorithm<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> for merging text that is unaware of the syntax and semantics of programming languages. Such instances prevent developers from checking in their code, requiring them to manually fix the conflict or, if the solution is ambiguous, to consult with other developers. In other cases, bad program merges can be more subtle and costly, introducing semantic merge conflicts that may either fail the compiler, break a test, or\u2014worse\u2014introduce a regression. Bad merges <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/ieeexplore.ieee.org\/document\/8468085\">constitute between 10 percent and 20 percent of all merges for large projects<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> and collectively result in stalled pull requests, failed continuous integration runs, or bugs in deployment, including exploitable <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/dwheeler.com\/essays\/apple-goto-fail.html\">security vulnerabilities<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>. Coping with bad merges, which could delay development anywhere from hours to days or impact customer trust in a product, is one of the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/dl.acm.org\/doi\/10.1145\/2884781.2884826\">well-known pain points<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> in collaborative software development and, additionally, often discourages less experienced developers from making meaningful contributions to large open-source projects.<\/p>\n\n\n\n<p>Over the past few years, we at Microsoft Research\u2014in collaboration with our academic colleagues and informed by <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/ieeexplore.ieee.org\/document\/8468085\">recent large-scale studies of merge conflicts<\/a>\u2014have been revisiting the challenge, focusing on properties of safe program merges that allow harnessing the powers of program verification, program synthesis, and machine learning. First, the safety, or correctness, of a merge can be characterized by crisp formal specifications, making merges suited for verification with mathematical guarantees. Secondly, open-source software is a natural resource for merge conflict and resolution data, which can be leveraged by deep learning approaches. And third, there are project-specific patterns in how developers resolve bad merges that can be capitalized on by program synthesis. Our work in these spaces has produced several new techniques: <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/verified-three-way-program-merge\/\">an automatic, precise differential program verifier for ensuring a correct merge<\/a>; <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/deepmerge-learning-to-merge-programs\/\">a deep learning\u2013based sequence-to-sequence model for synthesizing merge conflict resolutions<\/a>; and <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/can-program-synthesis-be-used-to-learn-merge-conflict-resolutions-an-empirical-analysis\/\">a domain-specific language that can learn repeated resolution patterns for textual merge conflicts<\/a>. Extending our work and finding ways to combine the strengths of these approaches with prior merge work holds the promise of real results\u2014improvements for developer productivity around collaboration at scale.<\/p>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-1 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<div class=\"annotations \" data-bi-aN=\"citation\">\n\t<ul class=\"annotations__list card depth-16 bg-body p-4 \">\n\t\t<li class=\"annotations__list-item\">\n\t\t\t\t\t\t<span class=\"annotations__type d-block text-uppercase font-weight-semibold text-neutral-300 small\">Publication<\/span>\n\t\t\t<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/verified-three-way-program-merge\/\" target=\"_self\" class=\"annotations__link font-weight-semibold text-decoration-none\" data-bi-type=\"annotated-link\" aria-label=\"Verified Three-Way Program Merge\" data-bi-aN=\"citation\" data-bi-cN=\"Verified Three-Way Program Merge\">\n\t\t\t\tVerified Three-Way Program Merge&nbsp;<span class=\"glyph-append glyph-append-chevron-right glyph-append-xsmall\"><\/span>\n\t\t\t<\/a>\n\t\t\t\t\t<\/li>\n\t<\/ul>\n<\/div>\n\n\n\n<div class=\"annotations \" data-bi-aN=\"citation\">\n\t<ul class=\"annotations__list card depth-16 bg-body p-4 \">\n\t\t<li class=\"annotations__list-item\">\n\t\t\t\t\t\t<span class=\"annotations__type d-block text-uppercase font-weight-semibold text-neutral-300 small\">Publication<\/span>\n\t\t\t<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/can-program-synthesis-be-used-to-learn-merge-conflict-resolutions-an-empirical-analysis\/\" target=\"_self\" class=\"annotations__link font-weight-semibold text-decoration-none\" data-bi-type=\"annotated-link\" aria-label=\"Can Program Synthesis be Used to Learn Merge Conflict Resolutions? An Empirical Analysis\" data-bi-aN=\"citation\" data-bi-cN=\"Can Program Synthesis be Used to Learn Merge Conflict Resolutions? An Empirical Analysis\">\n\t\t\t\tCan Program Synthesis be Used to Learn Merge Conflict Resolutions? An Empirical Analysis&nbsp;<span class=\"glyph-append glyph-append-chevron-right glyph-append-xsmall\"><\/span>\n\t\t\t<\/a>\n\t\t\t\t\t<\/li>\n\t<\/ul>\n<\/div>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<div class=\"annotations \" data-bi-aN=\"citation\">\n\t<ul class=\"annotations__list card depth-16 bg-body p-4 \">\n\t\t<li class=\"annotations__list-item\">\n\t\t\t\t\t\t<span class=\"annotations__type d-block text-uppercase font-weight-semibold text-neutral-300 small\">Publication<\/span>\n\t\t\t<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/deepmerge-learning-to-merge-programs\/\" target=\"_self\" class=\"annotations__link font-weight-semibold text-decoration-none\" data-bi-type=\"annotated-link\" aria-label=\"DeepMerge: Learning to Merge Programs\" data-bi-aN=\"citation\" data-bi-cN=\"DeepMerge: Learning to Merge Programs\">\n\t\t\t\tDeepMerge: Learning to Merge Programs&nbsp;<span class=\"glyph-append glyph-append-chevron-right glyph-append-xsmall\"><\/span>\n\t\t\t<\/a>\n\t\t\t\t\t<\/li>\n\t<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<h2 id=\"safe-program-merges-a-long-standing-research-problem\">Safe program merges\u2014a long-standing research problem<\/h2>\n\n\n\n<p>The problem of ensuring safe program merges has been long studied and remains an open challenge in programming languages and software engineering research. Foundational work was done in the late \u201980s using <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/dl.acm.org\/doi\/10.1145\/65979.65980\">program dependence graphs<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> to formalize the problem; however, it didn\u2019t produce practical tools because of the complexity of real-world programs. Work in the last two decades has been around using variants of <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/dl.acm.org\/doi\/10.1145\/2351676.2351694\">structured merge<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, which lift the merge from a line-structured view of code to a tree-structured view of code (provided by abstract syntax trees). Such approaches, though, suffer from scalability issues inherent in tree matching algorithms and unfortunately can\u2019t soundly resolve conflicts that involve program statements with side effects. Thus, a practical solution that can deal with the complexities of real-world merges has been elusive.<\/p>\n\n\n\n<p>The below example illustrates the complexities of dealing with program semantics. The base program has redundant code, a duplicate test for null on the return value of an allocation function malloc. Removal of the test from either of the two locations in which it exists\u2014as performed by Variant A and Variant B, respectively\u2014leads to faster performance. However, the removal of <em>both<\/em> the checks exposes a null-dereference bug; interestingly, the default merge algorithm in Git creates such a program as a result of the merge! Such a regression may not always be caught by a test since the call to malloc may return a null value only when subjected to an extreme stress test.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"624\" height=\"177\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/SafeProgramMerges_Fig1.png\" alt=\"\" class=\"wp-image-765970\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/SafeProgramMerges_Fig1.png 624w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/SafeProgramMerges_Fig1-300x85.png 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/SafeProgramMerges_Fig1-240x68.png 240w\" sizes=\"(max-width: 624px) 100vw, 624px\" \/><figcaption>An example of a semantic merge conflict produced by running the default merge algorithm in Git. The crossed-out text denotes deletion with respect to the base program. The merge exposes a null-dereference bug not present in the base program or either of the two variants.<\/figcaption><\/figure><\/div>\n\n\n\n<h2 id=\"leveraging-differential-program-verification\">Leveraging differential program verification<\/h2>\n\n\n\n<p>Program merge is one of the few widespread software engineering tasks where specifying the lack of regressions can be performed in a generic fashion in the form of a notion called semantic conflict-freedom. Intuitively, semantic conflict-freedom ensures that the merge incorporates precisely the behavioral changes introduced by the two branches over their most common ancestor.<\/p>\n\n\n\n<p>A few years back, we developed a <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/verified-three-way-program-merge\/\">technique for formally verifying semantic conflict-freedom<\/a>; the technique ensures that a merge doesn\u2019t introduce a new regression. Although program verification offers mathematical guarantees, its applicability at scale is limited by a combination of several problems, including the need for formal specifications and complex program-specific invariants; it also scales poorly with the size of a program. Promisingly, we demonstrate that the combination of the generic semantic conflict-freedom specification and automatic inference of relatively simple classes of relational invariants\u2014along with a compositional approach based on <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/project\/symdiff-differential-program-verifier\/\">differential program verification<\/a>\u2014makes merge verification scale with the size of the edits instead of the absolute size of programs. This allowed for certifying many real-world merges as correct and finding bugs in merges.<\/p>\n\n\n\n<p>While the approach showed the potential to prevent bad merges, it didn\u2019t immediately solve the problem of synthesizing a safe merge\u2014that is, not only detecting a bad merge but also fixing it. To that end, we started exploring <em>data-driven <\/em>approaches for the construction of good merges that can be potentially certified by merge verification tools. This naturally led to us exploring deep learning and program synthesis for merges.<\/p>\n\n\n\n<h2 id=\"leveraging-deep-learning\">Leveraging deep learning<\/h2>\n\n\n\n<p>We exploited the fact that millions of merge conflicts and their resolutions can be mined by replaying the version history of thousands of open-source code repositories on GitHub. With the key observation that most merge resolutions consist of rearranging lines and tokens from the conflicted regions, we developed a <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/deepmerge-learning-to-merge-programs\/\">deep learning\u2013based sequence-to-sequence model for synthesizing merge conflict resolutions<\/a>. In the process, we shed light on the challenges of building such solutions based on machine learning, including the automatic creation of high-quality ground truth for a supervised machine learning problem and effective encoding of the merge problem for a deep learning algorithm. For example, we found it crucial to localize the changes the user made while resolving a conflict and to select merges that appeared to be semantically conflict-free. Similarly, we required an edit-aware encoding of the conflict, as well as restrictions on the output sequence with a pointer mechanism, to develop an effective deep learning model.<\/p>\n\n\n\n<p>The technique has demonstrated the feasibility of developing practical merge resolution tools for a dynamic language such as JavaScript, for which structured merge algorithms are known to perform poorly. This paves the path for exploiting the recent advances in deep learning for code to the problem of merge conflict resolution at scale.<\/p>\n\n\n\n<h2 id=\"leveraging-program-synthesis\">Leveraging program synthesis<\/h2>\n\n\n\n<p>Finally, it has been previously observed that projects with a sufficiently large number of conflicts often have many project-specific repeated resolution patterns. In a <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/can-program-synthesis-be-used-to-learn-merge-conflict-resolutions-an-empirical-analysis\/\">recent paper<\/a>, we\u2019ve demonstrated that one can design succinct domain-specific languages (DSLs) to encode such resolution patterns and leverage advances in program synthesis to learn such patterns from a small number of examples. We show the feasibility of the approach for learning merge resolution patterns for the Microsoft Edge browser code base using the <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/group\/prose\/\">PROSE program synthesis framework<\/a>.<\/p>\n\n\n\n<p>As a divergent fork of the upstream Chromium repository, Microsoft Edge nicely embodies many of the challenges of modern distributed software development that creates value-added differentiated services on top of open-source software. <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/towards-understanding-and-fixing-upstream-merge-induced-conflicts-in-divergent-forks-an-industrial-case-study\/\">Engineers deal with several thousand bad merges, ranging from textual conflicts to compiler breaks to test failures, each month<\/a> while absorbing changes from the upstream repository. The ability to synthesize safe merges will have a considerable impact on the engineering cost to develop and maintain Microsoft Edge and similar projects. &nbsp;<\/p>\n\n\n\n<h2 id=\"a-promising-trifecta-and-a-grand-challenge\">A promising trifecta and a grand challenge<\/h2>\n\n\n\n<p>Each of the above three techniques comes with its own strengths and challenges. For example, the use of program verification can help verify the absence of regressions but is challenging to implement for dynamic languages such as JavaScript and Python. Deep learning\u2013based approaches can be applied at scale with high automation but don\u2019t provide any guarantees about lack of regressions. And, finally, program synthesis can learn project-specific repeated patterns for large projects but requires investment in designing DSLs for different patterns and can\u2019t ensure semantic conflict-freedom. We hope to find synergies between these complementary approaches, in addition to leveraging prior works on structured merge, so that we may develop practical tools for helping developers deal with bad merges at scale. We also hope the wide applicability yet well-defined nature of program merge can serve as an important problem domain for the research community to drive advances in program verification, synthesis, and deep learning. We leave the research community with a <em>grand challenge<\/em> for program repair: automate the resolution of a<em> million<\/em> instances of merge conflicts such that the respective merges are safe enough to successfully compile and pass all the quality gates, including tests.<\/p>\n\n\n\n<h3 id=\"acknowledgments\">Acknowledgments<\/h3>\n\n\n\n<p><em>This research represents the work of researchers and developers at Microsoft, including <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/cbird\/\"><em>Christian Bird<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.linkedin.com\/in\/pallavi-choudhury-81638a14\"><em>Pallavi Choudhury<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/sumitg\/\"><em>Sumit Gulwani<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.linkedin.com\/in\/mike-kaufman-439622\/\"><em>Mike Kaufman<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/levu\/\"><em>Vu Le<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/toddm\/\"><em>Todd Mytkowicz<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, former Microsoft researcher <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/nachinagappan.github.io\/\"><em>Nachi Nagappan<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/gsoares\/\"><em>Gustavo Soares<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.linkedin.com\/in\/asvyatko\/\"><em>Alexey Svyatkovskiy<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, and <\/em><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/jwolk\/\"><em>Jessica Wolk<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>; interns <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/chunghasung.org\/\"><em>Chungha Sung,<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/rangeetpan.github.io\/\"><em>Rangeet Pan<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, and <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.seas.upenn.edu\/~edinella\/\"><em>Elizabeth Dinella<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>; and external collaborators <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.cs.ox.ac.uk\/people\/marcelo.sousa\/\"><em>Marcelo Sousa<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.cis.upenn.edu\/~mhnaik\/\"><em>Mayur Naik<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>, and <\/em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.cs.utexas.edu\/~isil\/\"><em>I\u015fil Dillig<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a><em>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Since the computing world began embracing an open-source approach to programming, building software has become increasingly collaborative. Members of development teams with as few as two developers and as many as thousands are simultaneously editing different components in creating software systems and keeping them functioning optimally, and a three-way merge (opens in new tab) is [&hellip;]<\/p>\n","protected":false},"author":40519,"featured_media":765967,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"categories":[1],"tags":[],"research-area":[13560],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-765556","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research-blog","msr-research-area-programming-languages-software-engineering","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[199565],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[144812,663303],"related-projects":[890049,879960],"related-events":[],"related-researchers":[{"type":"user_nicename","value":"Shuvendu Lahiri","user_id":33640,"display_name":"Shuvendu Lahiri","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/shuvendu\/\" aria-label=\"Visit the profile page for Shuvendu Lahiri\">Shuvendu Lahiri<\/a>","is_active":false,"last_first":"Lahiri, Shuvendu","people_section":0,"alias":"shuvendu"}],"msr_type":"Post","featured_image_thumbnail":"<img width=\"960\" height=\"540\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-960x540.jpg\" class=\"img-object-cover\" alt=\"An illustration of\u202fresolving\u202fa bad merge\u202finto a safe merge.\u202fMoving from left to right,\u202fcircles\u202fon a continuous line\u202frepresent code commits\u202fin a version control system. A circle labeled \u201cBase\u201d\u202fis the most common ancestor of\u202fthe\u202fcommits marked A and B,\u202frespectively.\u202fAll three commits\u202fpass\u202fthe project\u2019s\u202fquality gates,\u202fdenoted by green check marks\u202falongside each of these commits. The subsequent merge results in a\u202ffailure of\u202fsome quality gate, denoted by a\u202fblue circle labeled \u201cBad merge\u201d with a\u202fred\u202fx above it. The repair uses machine learning,\u202fdenoted by\u202fan\u202fabstract\u202fimage of a\u202fneural network,\u202fand program verification\u202fand synthesis, denoted by a\u202fformal inference rule containing math symbols,\u202fto construct a safe merge that passes the quality gate,\u202fdenoted by a circle outlined\u202fin green\u202fwith\u202fa green check mark\u202fabove it.\u202f\u202f\u202f\" decoding=\"async\" loading=\"lazy\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-960x540.jpg 960w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-300x169.jpg 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-1024x577.jpg 1024w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-768x432.jpg 768w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-1536x865.jpg 1536w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-2048x1153.jpg 2048w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-1066x600.jpg 1066w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-655x368.jpg 655w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-343x193.jpg 343w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-240x135.jpg 240w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-640x360.jpg 640w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-1280x720.jpg 1280w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2021\/08\/1400x788_Safe_Merges_at_scale_No_logo_still-1920x1080.jpg 1920w\" sizes=\"(max-width: 960px) 100vw, 960px\" \/>","byline":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/shuvendu\/\" title=\"Go to researcher profile for Shuvendu Lahiri\" aria-label=\"Go to researcher profile for Shuvendu Lahiri\" data-bi-type=\"byline author\" data-bi-cN=\"Shuvendu Lahiri\">Shuvendu Lahiri<\/a>","formattedDate":"August 11, 2021","formattedExcerpt":"Since the computing world began embracing an open-source approach to programming, building software has become increasingly collaborative. Members of development teams with as few as two developers and as many as thousands are simultaneously editing different components in creating software systems and keeping them functioning&hellip;","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/765556"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/40519"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=765556"}],"version-history":[{"count":6,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/765556\/revisions"}],"predecessor-version":[{"id":766465,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/765556\/revisions\/766465"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/765967"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=765556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=765556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=765556"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=765556"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=765556"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=765556"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=765556"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=765556"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=765556"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=765556"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=765556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}