WizardMerge - Save Us From Merging Without Any Clues

Abstract.

Modern software development necessitates efficient version-oriented collaboration among developers. While Git is the most popular version control system, it generates unsatisfactory version merging results due to textual-based workflow, leading to potentially unexpected results in the merged version of the project. Although numerous merging tools have been proposed for improving merge results, developers remain struggling to resolve the conflicts and fix incorrectly modified code without clues. We present WizardMerge, an auxiliary tool that leverages merging results from Git to retrieve code block dependency on text and LLVM-IR level and provide suggestions for developers to resolve errors introduced by textual merging. Through the evaluation, we subjected WizardMerge to testing on 227 conflicts within five large-scale projects. The outcomes demonstrate that WizardMerge diminishes conflict merging time costs, achieving a 23.85% reduction. Beyond addressing conflicts, WizardMerge provides merging suggestions for over 70% of the code blocks potentially affected by the conflicts. Notably, WizardMerge exhibits the capability to identify conflict-unrelated code blocks that require manual intervention yet are harmfully applied by Git during the merging.

1. Introduction

As the most globally renowned version control system, Git (Git, 2023a) has been helping with the development and maintenance of millions of projects. To automatically merge the codes from two different versions, Git utilizes a Three-way Merge Algorithm (Vinkler, 2023) as the default strategy on the text level. The textual-based merging is general and suitable for various types of text files and the merging tempo is proved to be the fastest. However, it simply considers lines of code, neglecting all syntax and semantic information, which leads to potential bugs in the merged version of the project (Khurana, 2014; Spealman, 2018).

To mitigate the shortcomings of traditional textual-based merging, multiple merging approaches (Zhu and He, 2018; Zhu et al., 2022; Apel et al., 2011; Larsén et al., 2022; Shen et al., 2019; Sousa et al., 2018; Apel et al., 2012) are proposed for enhancing the correctness of merging results. These tools can be classified as Structured Merging and Semi-structured Merging. Structured merging tools (Larsén et al., 2022; Zhu et al., 2022; Sousa et al., 2018; Zhu and He, 2018) transform the code intended for merging into an Abstract Syntax Tree (AST), thereby converting the code merging into the merging of edges and nodes on the AST (Accioly et al., 2018). Semi-structured merging (Apel et al., 2012, 2011; Shen et al., 2019), akin to structured merging, designates certain semantically insensitive AST nodes (e.g., strings) as text, allowing them to be directly processed by the text-based merging strategy during the merging process (Cavalcanti et al., 2017).

Despite structured and semi-structured merging tools facilitating code merging, challenges arise when it is unclear which version of the code should take precedence. This uncertainty leads to merging conflicts. In the context of large-scale software projects, conflicts can become a source of frustration for developers, as they must dedicate significant effort to resolve the issues that arise from merging before they can release the final merged version (Ahmed et al., 2017; Nishimura and Maruyama, 2016). Addressing these conflict resolutions has given rise to merging assistance systems. These systems are designed with objectives such as selecting the most suitable developers to resolve conflicts (Costa et al., 2016), prioritizing the resolution order for conflicts (Shen et al., 2021), and even automatically generating alternative conflict resolutions (Zhu and He, 2018). With the rapid advancements in machine learning technologies in recent years, researchers have turned to machine learning approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023). These systems are trained using extensive datasets containing merge conflict scenarios and can provide predictions on the most suitable resolution strategy for each conflicting portion of code.

While these researches have made noteworthy contributions to code merging, they still exhibit the following limitations. Firstly, structured (Apel et al., 2012; Larsén et al., 2022; Zhu et al., 2022; Sousa et al., 2018; Zhu and He, 2018) and semi-structured (Apel et al., 2011; Shen et al., 2019) still generate conflicts when the direct merging between two AST noes failed, and cannot assist developers in resolving them. Secondly, conflict resolution assistance systems (Shen et al., 2021; Zhu and He, 2018; Costa et al., 2016) focus solely on resolving conflicts, overlooking potential errors introduced by incorrectly applied but conflict-free code. Though machine learning approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022) can automate conflict merging, the functionality of the resulting code may not ensure alignment with developers’ expectations. Additionally, machine learning methods necessitate specific code datasets for pre-training, which raises universality issues when applied to more diverse code projects. Moreover, the developers often have unpredictable operations on resolving conflicts, where the auto-generated conflict resolution may fail to meet the expectations of them.

To address these limitations, we introduce a novel approach aiming to aid developers in handling complex code-merging scenarios. Recognizing that developers have unpredictable ultimate needs, our approach focuses on grouping conflicts by relevance and providing prioritized suggestions for resolving conflicts rather than resolving them directly. Our approach also detects the incorrectly applied codes as they can be easily neglected but cumbersome to handle for developers. To realize these design goals, our approach requires a thorough understanding of the dependency relations in the two merging candidate versions. Firstly, we perform definition dependency graph construction on LLVM Intermediate Representation (IR) (LLVM, 2024) and utilize definition indicators extracted from Clang (Lattner, 2008) to indicate the definition name and ranges in the source file. Following graph construction, our approach analyzes the Git merge outcomes that present all the conflicts and modified code blocks. Then, we align the definitions in the source file with code snippets in Git’s outcomes to map from LLVM-IR to the Git merge results. Given the dependency graph analysis and aligned Git merge results, we further conduct an edge-sensitive algorithm to detect incorrectly applied codes, which we deem as conflicts since they require developers’ attention as well. Finally, we assign priorities to these conflicted nodes and produce merging suggestions.

We implement a prototype WizardMerge for C/C++ projects as most large-scale projects are written in C/C++ (Handy, 2023). We evaluate WizardMerge on 227 conflicts from five popular large projects. The outcomes demonstrate that WizardMerge diminishes conflict merging time costs. Beyond addressing conflicts, WizardMerge provides merging suggestions for most of the code blocks affected by the conflicts. Moreover, WizardMerge exhibits the capability to identify conflict-unrelated code blocks which should require manual intervention yet automatically applied by Git.

In summary, we make the following contributions:

• We proposed a novel approach to infer the dependency between text-level code blocks with modification.

• We proposed a remarkable methodology, which aims to pinpoint code blocks that have been automatically applied by Git but introduce unexpected results.

• We implemented a code merging auxiliary prototype named WizardMerge based on the approaches and evaluated the system on projects with large-scale code bases. We will open source WizardMerge and evaluation datasets at https://github.com/aa/bb.

2. Background

2.1. Git Merging

Figure 1. Three-way merging workflow of Git.

Git is a free and open-source distributed version control system designed for efficient handling of projects of all sizes (Git, 2023a). Git merge, as a key operation, facilitates the integration of changes between versions and is often used to consolidate code changes, bug fixes, or new features (Git, 2023b). Git supports multiple textual-based merging algorithms (Atlassian, 2022). Take the default and most commonly employed algorithm, Three-way Merging Algorithm (Vinkler, 2023) as an example, the workflow is shown in  Figure 1. When the developer tries to merge two commits (i.e., $C_{3}$ Variant A (VA) and $C_{5}$ Vairant B (VB) in  Figure 1), Git first traverses the commit-graph back until it reaches the nearest common ancestor commit (i.e., $C_{2}$, named Base). Then, all source code blocks of each newer version are mapped to the corresponding code blocks in base versions, and the modified code blocks of either VA or VB are regarded as Diff Code Blocks (DCBs). A DCB in a variant may contain zero or multiple lines of code, indicating the removal of an existing line or modification/addition of multiple continuous lines. After the code matching stage, Git will iterate each code block tuple, and determine which commit should be applied according to the following rules:

• If code blocks of VA and VB remain the same as the code block of Base, or both of them are changed in the same way, inherit the code block from VA. In Figure 1, both VA and VB remove the definition of v4 (i.e., deleting line 4 of Base). Due to identical modifications at the same locations, Git applies these changes. It is noteworthy that even for code removal, VA and VB maintain a pair of empty DCBs, symbolizing the deletion of lines.

• If only one code block of either VA or VB is changed, Git applies this code block, and marks this code block and the corresponding code block in the other variant as DCBs. In Figure 1, VA alters lines 1-2 and introduces a new line at 3. Git’s code-matching algorithm identifies these modifications, designating lines 1-3 of VA as DCB 1 and lines 1-2 of VB as DCB 2. Since only DCB 1 changes, Git applies it to generate the code for the Merged Commit at lines 1-3.

• If both code blocks from VA and VB are changed, and the modifications are different, Git marks both code blocks as DCBs. As Git cannot decide which one should be applied, it emits a conflict containing the two DCBs. In Figure 1, VA and VB independently modify the definition of v7. Git detects these alterations, marking line 7 of VA as DCB 3 and line 6 of VB as DCB 4. Since these two modifications differ, Git cannot determine which one to apply. Consequently, Git signals the inconsistency between DCB 3 and DCB 4, prompting developers to resolve this conflict.

Figure 2. An example of a clean but incorrect Git merge with the three-way merging algorithm

2.2. Limitations of Existing Approaches

Despite being the most widely used code merging tool currently, Git merge faces the following two challenges: (Challenge 1) It cannot ascertain developers’ expectations for code functionality. Consequently, when both versions modify the same code, Git treats this discrepancy as a conflict, necessitating manual intervention for resolution. We discussed how the conflicts are generated in §2.1. (Challenge 2) It cannot ensure the correctness of successfully applied and conflict-free code blocks. Even when Git successfully merges two versions without conflicts, the merged code may be generated with new bugs.  Figure 2 shows an incorrect merging scenario. Only the first line of VA and the third line of VB are changed. Using Git merge, the two versions of code can be easily merged without any conflict (i.e., the first line applied from VA and the second line applied from VB). Unfortunately, in the merged version, the definition of variable a has been removed, which causes a compilation error at the third line. These DCBs enforced by Git without conflict, yet resulting in unexpected results, are termed Violated DCBs. Given that these violated DCBs are not flagged as conflicts and are automatically incorporated by Git merge, they tend to introduce concealed programming errors into the merged code. In the most severe scenarios, these error-prone code segments might seemingly execute successfully but could potentially give rise to security issues post-deployment (Khurana, 2014; Spealman, 2018).

Over the years, researchers have concentrated on enhancing the quality of merged code and conflict resolution. However, these two basic limitations have not yet been fully resolved. On the one hand, structured (Zhu et al., 2022; Larsén et al., 2022; Sousa et al., 2018; Zhu and He, 2018) and semi-structured (Apel et al., 2012, 2011; Shen et al., 2019) merging still report conflicts when the same AST node is modified simultaneously by two merging candidate branches. On the other hand, the conflict resolution assistance system (Shen et al., 2021; Zhu and He, 2018) and machine learning approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) only consider conflicts reported by the merge tool, ignoring all code snippets that have been applied. Additionally, automatic software merging tools (Zhu et al., 2022; Larsén et al., 2022; Sousa et al., 2018; Zhu and He, 2018; Apel et al., 2012, 2011; Shen et al., 2019; Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) neglect an essential observation: developers have unpredictable ultimate needs, therefore cannot fully overcome Challenge 1. To better illustrate this, we provide an example of implementing the Fibonacci sequence in Figure 3. Two versions, A and B, calculate the Fibonacci sequence using recursion and iteration, respectively. When attempting to merge these versions, a conflict arises, and two developers resolve it. Although both developers decide to use the iterative approach from version B to avoid stack overflow for large values of $n$, they implement different strategies for handling negative values of $n$. Developer A, inspired by version A, uses an unsigned definition for $n$ to eliminate negative values (line 1 in resolution A). In contrast, Developer B opts to return zero when $n$ is less than zero (line 3 in resolution B). Since developers’ decisions on conflict resolution are unpredictable, automatic software merging tools often fail to produce an acceptable resolution in such cases.

Figure 3. An example of different resolutions to the same conflict

Furthermore, machine learning systems (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) are limited in their ability to resolve conflicts in large codebases due to input and output sequence constraints. However, these conflicts typically do not significantly impact developers’ time. For example, even MergeGen (Dong et al., 2023), the most advanced system available, failed to achieve satisfactory results when applied to the large-scale targets evaluated in §4. Upon completing MergeGen’s pre-training, we discovered that it produced no correct outputs, achieving an accuracy of 0%. This failure can be attributed to MergeGen’s default input and output sequence length limitations of 500 and 200 BPE, respectively (Dong et al., 2023). These limitations are excessively stringent for large-scale project source code, leading to truncation of code beyond the prescribed lengths. However, the end of the truncated code is usually far away from where conflict occurs and MergeGen cannot master the ability to resolve the conflicts given the trimmed training and testing sets. Attempts to relax these length limitations are impractical due to increased GPU memory consumption during training. Moreover, while machine learning techniques excel in generating merge results, they may not always align perfectly with developers’ expectations. Although MergeGen’s evaluation results demonstrate superior conflict code matching precision and accuracy on a line of code basis compared to previous works (Dong et al., 2023), it still falls short of expectations in some cases, with average precision and accuracy rates of 71.83% and 69.93%, respectively.

3. Design

Given the challenges outlined in the preceding section, we have identified two key insights. Addressing Challenge 1, we recognize that the expected outcomes of merges are subjective and open-ended. Consequently, our approach emphasizes guiding developers in resolving conflicts rather than prescribing resolutions. To tackle Challenge 2, it is imperative to analyze all modified code. To this end, we present WizardMerge, a novel conflict resolution assistance system, which provides developers with clues and aids in conflict resolution. Moreover, WizardMerge emphasizes all modified code snippets, not just conflicts, enabling it to uncover hidden discrepancies and preempt potential errors. A detailed design of WizardMerge will be presented in the subsequent subsections.

3.1. Overview

Figure 4. System overview of WizardMerge.

Figure 4 depicts the system overview of WizardMerge. WizardMerge first consumes compilation metadata from the two merge candidates through LLVM(LLVM, 2024). WizardMerge employs LLVM based on two insights: i) For large projects, code is compiled before a new version release to ensure compilation success, allowing WizardMerge to collect metadata without introducing additional merging steps; ii) LLVM Intermediate Representation (IR) provides a robust static analysis framework and comprehensive debug information, facilitating WizardMerge in performing definition dependency reasoning. To bridge LLVM IR analysis with merge results from Git, the compilation metadata also encompasses definition indicators. A definition indicator serves as the representation of a named definition section at the source code level, indicating the range and name of a definition. For example, a definition indicator of a function records its function name, along with its start and end line numbers in the source code file. Subsequently, To identify relationships between all modified codes, WizardMerge advances to the Dependency Graph Generation stage. Instead of focusing only on conflicts, dependencies for all definitions are analyzed. WizardMerge creates vertices for the definitions and establishes edges between vertices according to the dependency relationships of definitions analyzed from LLVM IRs. Following this, the Overall Dependency Graph (ODG) is generated to represent the dependencies among all the definitions in both candidate versions of the target project. To attach Git’s textual results with IR-level dependency information, WizardMerge aligns Git merge’s results and ODG to match DCBs with vertices in ODG through Graph-Text Alignment. This stage is capable of mapping DCBs to the corresponding definition nodes in each ODG, refining definition nodes into DCB nodes, and transforming definition dependencies into DCB dependencies. To rectify errors introduced by Git merge, WizardMerge employs an edge-sensitive algorithm in the Violated DCB Detection stage, detecting both conflict-related and conflict-unrelated violated DCBs. These violated DCBs and conflicts are categorized, prioritized based on the dependency graph, and presented as suggestions to developers to assist in resolution.

3.2. Dependency Graph Generation

WizardMerge first constructs ODG based on the LLVM IR and definition indicator. WizardMerge currently supports the following types of nodes and edges:

Graph node. Subsequently, WizardMerge generates nodes for each named definition with the corresponding indicator. Considering the types of definitions, WizardMerge creates three types of nodes based on the indicator information: Type Node (TN) represents composite types, e.g. structure, class, type alias, and enumeration; Global Variable Node (GN) represents global variable; Function Node (FN) represents function.

Graph edge. Each named definition may depend on other definitions within the project. For instance, a function might utilize a global variable or return a pointer with a specific structure type. In the ODG, these usage dependencies among definitions are deduced from LLVM IRs and represented by the edges linking one node to another. The types of edges are defined by the types of their two connected nodes. An edge of type A-B represents a dependency from node A to node B. In WizardMerge, five classifications of edges are supported: TN-TN, GN-TN, FN-TN, FN-GN and FN-FN.

Note that WizardMerge will never generate an edge from TN to FN, even though member functions may be defined within a composite type. Instead, WizardMerge creates TN for all functions, irrespective of whether the function is standalone or nested within another scope. If an FN represents a nested function defined inside a composite type, an FN-TN edge is built to represent the dependency from the function to the specific type.

3.3. Resolving Suggestion Generation

In this stage, WizardMerge extracts DCB information from Git merge to aid in the analysis. Then, merging suggestions can be generated based on the analysis results.

3.3.1. Graph-Text Alignment

The merge results cannot be directly linked to the corresponding node in ODG. This is primarily because these results are raw texts that provide no additional clues for program analysis. In the raw results, a single large DCB may cover multiple nodes and a single node may encompass several DCBs. This N-to-N relationship complicates the analysis of the graph.

Figure 5. Example alignment between node and DCB text.

WizardMerge initially associates each DCB with its corresponding definition indicators. To identify all nodes contained in the file where the DCB is situated, WizardMerge extracts the nodes whose range intersects with the DCB range. If no matched node is found, it indicates that the DCB is not in a definition (e.g., newlines or comments) and will not be further analyzed by WizardMerge. Treating each DCB as a ”line segment”, its start and end line numbers represent the coordinates of the line segment’s two endpoints on the coordinate axis. Similarly, each definition indicator of a node is considered as a unique ”color”. The range of each node signifies a specific coordinate interval that is colored with the definition represented by the node. Thus, retrieving the node during each DCB traversal can be seen as a color query for the interval $[start\_line,end\_line]$, and interval modification and information maintenance can be efficiently managed using line segment trees. For a target project containing $N$ lines of code, each ”coloring” and ”color query” operation can be achieved with a time complexity of $O(log_{2}N)$ (Cp-Algorithms, 2023). WizardMerge subsequently logs all DCBs corresponding to each node, organizing them in ascending order of line numbers. The node is then subdivided into finer-grained nodes. The ranges of these finer-grained nodes are updated concurrently based on the original node and their corresponding unique DCBs. Fine-grained nodes belonging to the same definition will be connected sequentially in range order, which implicitly expresses the dependency between code blocks. This mechanism ensures that each node in ODG aligns with at most one DCB, effectively preventing any matching confusion within the ODG.

Taking  Figure 5 as an instance, there are two definitions: Named Def 1, Named Def 2. Before alignment, the nodes are created with their range information. Let’s consider two DCBs associated with these definitions ($[L2,L5]$ and $[L6,L7]$). To establish a one-to-one mapping between DCBs and nodes, each node can be divided into multiple ones, while unaffected lines are excluded as they do not influence the merging. For DCB $[L2,L5]$, WizardMerge detects that $[L2,L3]$ belongs to Named Def 1 and $[L5,L5]$ belongs to Named Def 2. Consequently, a new node starting from $L2$ to $L3$ will replace the original node for Named Def 1. As $[L1,L1]$ remains unchanged, it will be discarded. Furthermore, a new node from $L5$ to $L5$ is also formed since $[L6,L7]$, representing another portion of Named Def 2, corresponds to the DCB $[L6,L7]$. To indicate the code dependency from lines to previous lines within the same definition, an additional edge from node $[L6,L7]$ to node $[L5,L5]$ is established.

As WizardMerge is tasked with managing two code versions (VA and VB), some nodes in the ODG of VA must possess a corresponding mirror node in the ODG of VB. WizardMerge also constructs a mapping of each node to its matched node in the other version’s ODG by matching the name of the definition and the DCB metadata linked to the node. Note that if one node is aligned with a DCB, it must have one unique mirror node with the other DCB in the same DCB pair. If the node has a matched node, the matched node must be the mirror node and the definition name is consistent with the current node. The matched node results contribute to the violated DCB detection via dependency missing determination. Besides, the ODG’s size can also be shrunk if there are nodes not attached to any DCBs, which means they are not changed during merging. After the node deletion, the newly generated graph is called Shrunk Dependency Graph (SDG).

3.3.2. Violated DCB Detection

Violated DCBs are the underlying cause of seemingly successful but erroneous merging. To offer developers a comprehensive understanding of the merging process, WizardMerge detects violated DCBs based on an edge-sensitive algorithm and deems them as conflicts requiring resolution suggestions. Given the SDGs and node matching relationship, WizardMerge traverses each edge in the two versions of the SDG separately. Each edge, starting from $v$ and ending at $u$, signifies that $v$ relies on $u$. WizardMerge determines which version of the DCB associated with $u$ and $v$ is ultimately applied in the merge results (i.e., from VA, VB, or conflict). WizardMerge then ascertains whether these nodes represent violated DCBs by the applied versions and matching nodes of $u$ and $v$. We introduce all the safe (i.e. not violated DCBs detected) and violated scenarios as follows.

Symbols Definition

Let the SDGs from VA and VB be represented as $G_{A}=\ <V(G_{A}),E(G_{A})>$ and $G_{B}=\ <V(G_{B}),E(G_{B})>$, where $V$ indicates the vertices set and $E$ indicates the edges set. For each vertex $v\in V$, we represent its mirror node as $Mi(v)$ and use $match(Mi(v))$ to indicate whether the mirror node of $v$ is a matching node ($True$ or $False$). $v$ belongs to only one of the $V_{N}$, $V_{A}$, and $V_{C}$ vertex sets, representing not applied, applied, and conflict node sets respectively. For each edge $e(v,u)\in E$, it represents an edge from $v$ to $u$, indicating $v$’s dependency on $u$. According to the construction principles of SDG, there are two basic facts:

• If $v\in V_{A}$, then $Mi(v)\in V_{N}$, and vice versa.

• If $v\in V_{C}$, then $Mi(v)\in V_{C}$.

As each $v\in V_{A}$ must indicate another vertex (i.e., $Mi(v)$) belongs to $V_{N}$, WizardMerge only analyzes the cases where $v\in V_{A}$ or $v\in V_{C}$ to avoid duplicate traversal.

Safe Scenarios

For each $v$ and an edge $e=(v,u)$, we define the scenarios satisfying any of the following four formulas as safe:

(1) $$v\in V_{A},u\in V_{A}$$

(2) $$v\in V_{A},u\notin V_{A},match(Mi(u))=True$$

(3) $$v\in V_{C},u\in V_{A}$$

(4) $$v\in V_{C},u\notin V_{A},match(Mi(u))=True$$

In SDGs, the above formulas can be regarded as an edge-sensitive detection algorithm, which is visiualized as depicted in  Figure 6. For Equation 1, if both $u$ and $v$ are applied, it means the dependency relation between nodes within the same SDG (as shown in Scenario 1 of  Figure 6). By the same token, Scenario 3 also illustrates such a direct dependency represented by  Equation 3. For Equation 2 (Scenario 2 in  Figure 6), $v$ is applied but $u$ is either not applied ($u\in V_{N}$) or in conflict status ($u\in V_{C}$). Nevertheless, if the mirror of $u$ matches $u$ ($match(Mi(u))=True$), it means that at least in the other SDG, $v$ can find its corresponding dependency applied (i.e., $Mi(u)$) although $u$ is not applied, or both versions of conflicted $u$ hold the same dependency for $v$. To this end, WizardMerge uses a virtual dependency edge from $v$ to $Mi(u)$ to indicate a cross dependency between nodes from different SDGs. Similarly,  Equation 4 (Scenario 4) is also regarded as safe with the same reason.

Figure 6. Edge traversal scenarios visualization

Violated Scenarios

For each $v$ and an edge $e=(v,u)$, all the scenarios not detected as safe are regarded as violated scenarios. These scenarios are:

(5) $$v\in V_{A},u\notin V_{A},match(Mi(u))=False$$

(6) $$v\in V_{C},u\notin V_{A},match(Mi(u))=False$$

The Scenario 5 and Scenario 6 in  Figure 6 visualize  Equation 5 and  Equation 6 respectively. Once $u$ is not applied or in conflict, and the mirror node of $u$ does not match it ($match(Mi(u))=False$), it means that $v$ misses dependency from $u$ in both SDGs (when $u\in V_{N}$), or $Mi(u)$ holds a different dependency from $u$, which does not match $v$’s requirement (when $u\in V_{C}$).

WizardMerge identifies these cases are incorrectly handled by Git merge and marks the corresponding $v$, $u$, $Mi(v)$ and $Mi(u)$ as violated. Note that vertices with conflicts are always treated as violated, regardless of whether they are encountered in safe or violated scenarios. Finally, the DCBs attached to these vertices are also marked as violated.

Figure 7. MDG example. Each node in MDG contains exactly a pair of mirror nodes in SDG. Each edge is built if there is at least one SDG edge from one SDG node to another.

3.3.3. Priority-Oriented Classification

WizardMerge further minimizes the number of nodes that require processing and constructs a Minimum Dependency Graph (MDG) to emulate the dependencies of the merged version of code. In the MDG, each node will consist of either an applied node or a conflict node and its matching node, and the edges between nodes will be created based on various SDGs according to the applying status. Specifically, while establishing the MDG, WizardMerge will traverse each conflict node or node associated with violated DCBs, and based on the applying status of the node, it will switch to the corresponding version of SDG and continue traversing the nodes in that particular SDG. Particularly, if the node is in conflict status, then the outcoming edges of both the mirror of the node and itself would be iterated. Concurrently, WizardMerge sets up a directed edge between corresponding nodes for the MDG, relying on the encountered edges during traversal. Ultimately, the MDG encapsulates the essential dependencies of the two versions of code to be merged.

Figure 7 shows an instance illustrating how MDG is built from SDG. Each MDG node is created from a pair of nodes related to conflict or violated DCBs. SDG node A-E are from VA and all Mirror nodes are from VB. Starting from A and its mirror, WizardMerge iterates the outcoming edges and finds B is linked to a violated DCB. Then, WizardMerge creates a new node MDG_Node_B containing B and its mirror. As B is not applied while its mirror node is applied, WizardMerge iterates the outcoming edges of the mirror of B and finds a pair of conflict nodes (i.e., E and Mirror), which forms MDG_Node_E. WizardMerge then iterates the outcoming edges of both B and Mirror because of the conflict. By the same token, MDG_Node_D and MDG_Node_C are created.

WizardMerge then employs the Tarjan algorithm (Tarjan, 1972) to condense the MDG nodes and eliminate cycles. During this process, nodes in the same strongly connected component are regarded as having identical priority, as these nodes may reference each other within the code. In the case of the directed acyclic MDG, WizardMerge divides the MDG into multiple subgraphs based on connectivity. All nodes within each subgraph are grouped, and each node is assigned a priority through the topological sorting of the subgraph. Nodes that appear later in the topological order signify that other nodes have greater dependencies on them, while the nodes themselves have fewer dependencies. Consequently, these nodes are assigned higher priority, enabling developers to address them earlier. In  Figure 7, MDG_Node_C, MDG_Node_D and MDG_Node_E are in the same cyclic of MDG and are thus assigned the same resolution priority as they depend on each other. After calculating the topological order, WizardMerge suggests that the DCB resolution priority should be {MDG_Node_C, MDG_Node_D, MDG_Node_E}, {MDG_Node_B} and {MDG_Node_A}.

4. Evaluation

In this section, we evaluate the effectiveness of WizardMerge, aiming to answer the following research questions:

• RQ1: Can WizardMerge help reduce the time consumption of merging conflicts?

• RQ2: Can WizardMerge detect violated DCBs related to conflicts applied by Git?

• RQ3: Can WizardMerge detect violated DCBs unrelated to conflicts applied by Git?

Dataset Collection. We choose Firefox (Mozilla, 2023), Linux Kernel (Torvalds, 2023), MySQL (MySQL, 2024), PHP (MySQL, 2024), and LLVM (LLVM, 2024) as the target projects because of their widespread usage as open-source software. Additionally, they boast extensive code bases and are maintained by multiple developers, resulting in repositories that feature intricate commits and merging scenarios. We collect 22 conflict pairs from Firefox, 43 from Linux Kernel, 17 from LLVM, 46 from PHP, and 99 from MySQL with a committing timeframe from 2021 to 2024. For each pair of conflicts, we only focus on the files in C/C++ format and guarantee they either have at least five conflict regions or violated DCBs detected. On average, a conflict contains 824.33 lines of codes and is related to 6.8 files.

Evaluate with State-of-the-art (SOTA) Systems. We initially intended to assess WizardMerge alongside other cutting-edge systems. However, JDIME (Apel et al., 2012), Mastery (Zhu et al., 2022), Spork (Larsén et al., 2022), SafeMerge (Sousa et al., 2018), AutoMerge (Zhu and He, 2018), IntelliMerge (Shen et al., 2019) and SoManyConflicts (Shen et al., 2021) encountered language incompatibility issues within our datasets. Besides, migrating WizardMerge to the languages these systems support is impractical because as an LLVM-based project, WizardMerge requires the full support from the LLVM framework, while the compiler front ends of Java (Stepanov, 2020), Typescript (ApsarasX, 2021), and Javascript (ApsarasX, 2021) are still under development. Furthermore, FSTMerge(Apel et al., 2011) purports scalability contingent upon users implementing the merging engine for specific languages. Unfortunately, its C/C++ parsers are either underdeveloped (i.e., accommodating only basic syntax) or unimplemented, rendering it unsuitable for real-world projects. In addition, as mentioned in § 2.2, the machine learning approaches (Zhang et al., 2022; Svyatkovskiy et al., 2022; Elias et al., 2023; Dong et al., [n. d.]; Aldndni et al., 2023; Dinella et al., 2022; Dong et al., 2023) meet the sequence length limitation challenge when facing the large-scale targets we chose.

Evaluation Environment. We evaluated WizardMerge on an AMD EPYC 7713P server with 64/128 cores/threads, NVIDIA GeForce RTX 4090 (24GB GPU memory), and 256GB memory, running Ubuntu 20.04 with kernel 5.4.0.

4.1. Effectiveness on Conflict Resolution

To address RQ1, we conducted a comparative analysis of the time consumption associated with two distinct approaches (Git merge w/ and w/o WizardMerge) for merging conflict pairs. As WizardMerge only provides suggestions instead of resolutions of conflicts, We have to assign two types of technical staff to the manual merging phase: skilled staffs, researchers with deep understanding of the project, and ordinary staffs, researchers having general understanding of the project. Initially, the ordinary staff employed WizardMerge to analyze the two versions and performed the merge utilizing the suggestions provided by WizardMerge. Subsequently, the skilled staff manually merged the two candidate versions using Git merge without any additional assistance. We meticulously recorded the number of conflicts that can be analyzed by WizardMerge and the time taken (with precision to the minute) from the commencement of conflict analysis to their complete resolution.

Table 1. Conflict coverage of WizardMerge. Total Num indicates the total number of conflicts in each dataset. Analyzed Num indicates the number of conflicts successfully analyzed by WizardMerge. Cover Rate indicates the ratio of the above two columns.

width = colspec = Q[223]Q[277]Q[202]Q[210], hline1,7 = -0.08em, hline2 = -0.05em, Dataset & Analyzed Num Total Num Cover Rate
Firefox 159 160 99.38%
Linux Kernel 75 88 85.23%
LLVM 71 72 96.61%
PHP 236 255 92.55%
MySQL 797 964 82.68%

Before comparing the effectiveness of merging w/ and w/o WizardMerge, we first evaluate its ability to assess conflicts. As shown in Table 1, we calculated the total number of conflicts for each dataset and recorded how many conflicts can be successfully analyzed by WizardMerge. WizardMerge can give suggestions of more than 80% conflicts from the five targets. Notice that some conflicts cannot be handled by WizardMerge, we manually dig the reasons behind the failure. In the design section, we mentioned that WizardMerge’s analysis is based on LLVM IR. However, in textual merging results, some conflicts are caused by the content of comments or preprocessing instructions (e.g., #include and macro definition). Since comments do not belong to the code scope, and the preprocessing instructions will be expanded in the Clang front end, LLVM IR will lose the text information of these conflicts, and finally WizardMerge will not give suggestions related to them.

Figure 8. Manual merging time w/ and w/o WizardMerge.

The effectiveness of merging w/ and w/o WizardMerge is quantified by time consumption and is shown in Figure 8. When the time consumption of merging a pair of commits exceeds 70 minutes, we will mark it as ”$>70$” and stop resolving it. In 135 out of 277 conflict scenarios, WizardMerge contributes to reducing version conflict resolution time, and as the time consumption w/o WizardMerge increases, the assistance ability of WizardMerge also becomes more obvious. Remarkably, for the 205th conflict pair, manual merging w/o WizardMerge costs more than 70 minutes, while with the help of WizardMerge, the merging process can be finished in 35 minutes. This exceptional performance is attributed to the Priority-Oriented Classification module in WizardMerge, which provides categorization and fixes priority recommendations for manually resolved code blocks. Simultaneously, the Violated DCB Detection module in WizardMerge automatically identifies code blocks related to conflicts. This feature simplifies developers’ efforts in analyzing dependencies and avoids the substantial time spent on the manual in-depth exploration of extensive code space required by Git merge. However, WizardMerge may not optimize the time consumption for all data points. In 18 out of 277 conflict cases, using WizardMerge could even increase the burden of conflict resolution. This occurs when only a small number of conflicts are present and few code blocks are affected, rendering WizardMerge’s assistance not substantial. Additionally, as mentioned above, WizardMerge fails to generate suggestions on comments or preprocessing instructions.

Listing 1: Case study for conflict & violated DCB classification and WizardMerge-produced resolving order assignment.

⬇

1diff --git a/gfx/layers/ScrollbarData.h b/gfx/layers/ScrollbarData.h

2--- b/gfx/layers/ScrollbarData.h

3+++ a/gfx/layers/ScrollbarData.h

4@@ +38,10 -38,9 @@ struct ScrollbarData

5 * This constructor is for Thumb layer type.

6 */

7 ScrollbarData(ScrollDirection aDirection, float aThumbRatio,

8<<<<<<< HEAD

9+ OuterCSSCoord aThumbStart, OuterCSSCoord aThumbLength,

10+ OuterCSSCoord aThumbMinLength, bool aThumbIsAsyncDraggable,

11+ OuterCSSCoord aScrollTrackStart,

12+ OuterCSSCoord aScrollTrackLength, uint64_t aTargetViewId)

13=======

14- CSSCoord aThumbStart, CSSCoord aThumbLength,

15- bool aThumbIsAsyncDraggable, CSSCoord aScrollTrackStart,

16- CSSCoord aScrollTrackLength, uint64_t aTargetViewId)

17>>>>>>> 281943a7a7564da09bd6076cac0c47a7a62144dc

18 : mDirection(Some(aDirection)),

19 mScrollbarLayerType(ScrollbarLayerType::Thumb),

20 mThumbRatio(aThumbRatio),

21@@ +65,16 -63,16 @@

22 public:

23 ScrollbarData() = default;

24

25<<<<<<< HEAD

26+ static ScrollbarData CreateForThumb(

27+ ScrollDirection aDirection, float aThumbRatio,

28+ OuterCSSCoord aThumbStart,

29+ OuterCSSCoord aThumbLength, OuterCSSCoord aThumbMinLength,

30+ bool aThumbIsAsyncDraggable,

31+ OuterCSSCoord aScrollTrackStart,

32+ OuterCSSCoord aScrollTrackLength, uint64_t aTargetViewId) {

33=======

34- static ScrollbarData CreateForThumb(ScrollDirection aDirection,

35- float aThumbRatio, CSSCoord aThumbStart,

36- CSSCoord aThumbLength,

37- bool aThumbIsAsyncDraggable,

38- CSSCoord aScrollTrackStart,

39- CSSCoord aScrollTrackLength,

40- uint64_t aTargetViewId) {

41>>>>>>> 281943a7a7564da09bd6076cac0c47a7a62144dc

42 return ScrollbarData(aDirection, aThumbRatio, aThumbStart, aThumbLength,

43+ aThumbMinLength, aThumbIsAsyncDraggable,

44+ aScrollTrackStart, aScrollTrackLength, aTargetViewId);

45- aThumbIsAsyncDraggable, aScrollTrackStart,

46- aScrollTrackLength, aTargetViewId);

47 }

48

49@@ MergeGuardian Result

50@@ Group 0:

51@@ |

52@@ C-- ScrollbarData xxx/ScrollbarData.h 41-44, 41-43

53@@ |

54@@ C-- CreateForThumb xxx/ScrollbarData.h 68-74, 66-72

55@@ |

56@@ A-- CreateForThumb xxx/ScrollbarData.h 76-77

57@@ |

58@@ B-- (applied) CreateForThumb xxx/ScrollbarData.h 74-75

1 presents a case study illustrating how WizardMerge classifies the conflicts and violated DCBs and assigns resolving privileges between VA 145d3f6 and VB 281943a. Initially, both versions introduce distinct modifications to the ScrollbarData constructor, resulting in a merge conflict (lines 8-17). Subsequently, both versions make different alterations to the parameter types of the CreateForThumb method in the ScrollbarData class, leading to another merge conflict (lines 25-41). However, Git’s strategy reports these conflicts directly to the developer without providing additional clues. In contrast, WizardMerge utilizes dependency analysis between definitions to discern that the constructor of ScrollbarData will be called by CreateForThumb (line 42). Consequently, WizardMerge classifies the two conflicts into one group, assigning higher fix priority to lines 8-17 than to lines 25-41.

Additionally, VA and VB present diverse implementations of the function body of the CreateForThumb method. According to the three-way merging algorithm, Git applied the code snippets from VB (lines 45-46) after detecting these two conflicts. Moreover, within the pair of DCBs represented by lines 43-46, although lines 45-46 are applied without conflicts, it cannot ensure the constructor of ScrollbarData receives the correct parameter types when both conflicts are present. This is because, if the developer chooses to apply all VA modifications when resolving these conflicts, the applied lines 45-46 from VB will lack essential parameters, aThumbMinLength and aThumbIsAsyncDraggabl, used by ScrollbarData constructor and the types of aThumbStart, aThumbLength, aScrollTrackStart, and aScrollTrackLength will not match the ScrollbarData constructor prototype. Nevertheless, WizardMerge detects lines 45-46 and its mirror DCB (i.e., lines 43-44) through its innovative dependency analysis approach, treating them as violated DCBs. It reports them to developers along with other conflicts. Since lines 43-46 depend not only on lines 8-17 (function call) but also on lines 25-41 (definition of prototype), these two violated DCBs are grouped with the previous two conflicts, with fixed priority coming after the two conflicts. The resolution suggestions provided by WizardMerge are shown in lines 49-58 of 1, where items prefixed with C indicate pairs of DCBs with conflicts, and items prefixed with A or B indicate DCBs from VA or VB considered as violated DCBs.

[style=ccl] Conclusion: Our evaluation confirms WizardMerge can give suggestions for 72.45% of the conflicts. We analyze the time expenditures associated with conflict resolution and their corresponding DCBs w/ and w/o the utilization of WizardMerge to answering RQ1. On average, WizardMerge demonstrates a 23.85% reduction in resolution time. This underscores the efficiency and practicality of WizardMerge in facilitating conflict resolution, even in the context of large-scale real-world software.

Table 2. Violated DCB detection records. CR VA represents the LoC of CR violated DCB in VA, and CR VB represents the LoC of CR violated DCB in VB. The format $n/m$ indicates that there are $m$ LoCs in total, of which WizardMerge detects $n$. Similarly, CU VA represents the LoC of CU violated DCB in VA, and CU VB represents the LoC of CU violated DCB in VB. The format $n/m$ indicates that WizardMerge detect $m$ LoCs as CU violated DCB, of which $n$ are confirmed. Recall and Precision with $\dagger$ and $\ddagger$ stand for VA and VB respectively.

width = colspec = Q[119]Q[96]Q[85]Q[88]Q[88]Q[104]Q[104]Q[121]Q[121], hline1,7 = -0.08em, hline2 = -0.05em, Dataset & CR-VA CR-VB CU-VA CU-VB Recall$\dagger$ Recall$\ddagger$ Precision$\dagger$ Precision$\ddagger$
Firefox 151/174 112/123 75/652 98/717 88.30% 91.06% 11.50% 13.67%
Linux Kernel 107/131 156/192 171/1245 105/905 81.68% 81.25% 13.73% 11.60%
LLVM 212/316 16/23 N/A N/A 67.09% 69.57% N/A N/A
PHP 92/132 49/139 226/324 213/358 69.70% 35.25% 69.75% 59.50%
MySQL 12274/13100 3171/3469 1750/4597 1307/2427 93.69% 91.41% 38.07% 53.85%

4.2. Violated DCB Detection

To address both RQ2 and RQ3, our initial step involves establishing the ground truth regarding the number of violated DCBs by manually merging two code versions using Git merge. Subsequently, we employ WizardMerge to conduct an analysis and document the identified violated DCBs. As not all code segments within a DCB pertain to violated DCBs, we utilize Line of Code (LoC) for careful quantification of the violated DCBs. These violated DCBs are further categorized into Conflict-Related (CR) and Conflict-Unrelated (CU) violated DCBs.

4.2.1. Conflict-Related Violated DCBs

In addition to addressing conflict DCBs, developers should reassess the DCBs automatically applied by Git merge. Resolving one conflict might potentially impact other sets of DCBs. Throughout our evaluation, we recorded the LoC for DCBs linked to conflicts in both versions. This data reflects WizardMerge’s capability in elucidating the correlation between conflicts and violated DCBs.

Table 2 illustrates the CR-violated DCB detection results of WizardMerge. As VA and VB’s codes are different, the LoC of CR-violated DCBs in the same diff pair may vary as well. Thus, we documented the LoC from both VA and VB. According to the evaluation, 167 out of 227 conflict scenarios are confirmed to contain CR-violated DCBs. For most of the targets, WizardMerge successfully detected more than 60% CR-violated DCBs, providing a promising assistive cue for developers in executing manual fixes and facilitating them in exploring the CR-violated DCBs. Noticeably, although MySQL datasets have the most LoC of CR-violated DCBs, WizardMerge’s detection recall even reaches 93.69%. For LLVM and PHP, WizardMerge showed moderate recalls.

We also delved into the reasons behind WizardMerge’s inability to detect CR-violated DCBs in certain datasets. Firstly, the Linux Kernel encountered compilation failure with the ”O0” option, a crucial setting for preserving debug information and preventing code optimization. Although ”Og” can be used for better debug ability, it is akin to ”O1,” resulting in the elimination of significant debug information (Du, 2018). For instance, inlined functions are inserted at the invocation location and subsequently removed from the original code. As WizardMerge depends on the collaboration of debug information and LLVM IR, the absence of debug information leads to the failure of node generation and DCB matching. Secondly, some datasets include violated dependencies among local variables within a specific function or macro definition, which WizardMerge’s analysis currently does not support.

Listing 2: Case study for conflict-related violated DCBs

⬇

1diff --git a/drivers/net/virtio_net.c b/drivers/net/virtio_net.c

2--- b/drivers/net/virtio_net.c

3+++ a/drivers/net/virtio_net.c

4@@ -126,12 +127,9 @@ struct virtnet_stat_desc virtnet_rq_stats_desc[] = {

5 #define VIRTNET_SQ_STATS_LEN ARRAY_SIZE(virtnet_sq_stats_desc)

6 #define VIRTNET_RQ_STATS_LEN ARRAY_SIZE(virtnet_rq_stats_desc)

7

8<<<<<<< 5c5e0e81202667f9c052edb99699818363b19129

9- struct virtnet_rq_dma {

10- dma_addr_t addr;

11- u32 ref;

12- u16 len;

13- u16 need_sync;

14=======

15+ struct virtnet_interrupt_coalesce {

16+ u32 max_packets;

17+ u32 max_usecs;

18>>>>>>> 1acfe2c1225899eab5ab724c91b7e1eb2881b9ab

19 };

20@@ -147,6 +145,8 @@ struct send_queue {

21

22 struct virtnet_sq_stats stats;

23

24+ struct virtnet_interrupt_coalesce intr_coal;

25

26 struct napi_struct napi;

27@@ -164,6 +164,8 @@ struct receive_queue {

28

29 struct virtnet_rq_stats stats;

30

31+ struct virtnet_interrupt_coalesce intr_coal;

32

33 /* Chain pages by the private ptr. */

34@@ -185,12 +187,6 @@ struct receive_queue {

35 struct xdp_rxq_info xdp_rxq;

36

37- /* Record the last dma info to free ... */

38- struct virtnet_rq_dma *last_dma;

39- /* Do dma by self */

40- bool do_dma;

41 };

42@@ -295,10 +292,8 @@ struct virtnet_info {

43 u32 speed;

44

45 /* Interrupt coalescing settings */

46- u32 tx_usecs;

47- u32 rx_usecs;

48- u32 tx_max_packets;

49- u32 rx_max_packets;

50+ struct virtnet_interrupt_coalesce intr_coal_tx;

51+ struct virtnet_interrupt_coalesce intr_coal_rx;

2 presents an intriguing case study revealing conflict-related violated DCBs detected by WizardMerge between VA 5c5e0e8 and VB 1acfe2c. In VA, the definition for virtnet_rq_dma is present, whereas at the same position in VB, virtnet_interrupt_coalesce is defined. Git identifies these versions’ different modifications as a conflict and prompts manual resolution for developers. Subsequently, Git designates other DCBs as not in conflict and applies them based on their consistency with the base version’s DCBs. Eventually, the code snippets from lines 24, 31, and 50-51 (from VA) along with 37-40 (from VB) are applied. Despite the differences between VA and VB in lines 46-51, lines 46-49 from VB are consistent with the base version’s snippets. According to the three-way merging strategy, Git prefers to apply lines 50-51 from VA. In contrast, WizardMerge analyzes all modified code and discovers that even though the conflict is highlighted, some related DCBs have been applied without alerting the developers. For instance, applying lines 37-40 from VB assumes the presence of struct virtnet_rq_dma. Yet, if the developer opts for lines 15-17 as the conflict resolution, the structure becomes undefined within that context. Similarly, applying lines 24, 31, and 50-51 from VA assumes the definition of struct virtnet_interrupt_coalesce, while they will cause compilation errors if the developer chooses lines 9-13 as the conflict resolution. Consequently, WizardMerge identifies these code snippets as violated DCBs in conjunction with the conflict. Furthermore, WizardMerge assigns higher priority to the conflict, signifying the dependency of other DCBs on the conflict and suggesting developers resolve the conflict before reconsidering these violated DCBs.

4.2.2. Conflict-Unrelated Violated DCBs

Throughout this evaluation, we document the LoC for DCBs unrelated to conflicts in both variant versions reported by WizardMerge. Following this, we manually inspected the identified DCBs and calculated the number of LoC genuinely violated among them.

The results of WizardMerge’s detection of CU-violated DCBs are also presented in Table 2. As CU-violated DCBs are isolated from conflicts, WizardMerge demonstrates the capability to detect them, even in scenarios where it fails to handle any conflicts. In total, WizardMerge detected CU-violated DCBs in 137 out of 227 conflict scenarios, while no CU-violated DCBs were found in LLVM. These DCBs, lacking necessary dependent definitions and automatically applied by Git merge without developer notification, do not lead to conflicts but can result in compile errors or even latent bugs affecting users at runtime. While WizardMerge showcases its potential in uncovering violated dependency issues, the evaluation also highlights instances of false positive CU-violated DCBs. This arises from the lack of function body analysis in WizardMerge. According to WizardMerge’s DCB detection algorithm §3.3.2, the relationship between two DCBs from the same function relies on line numbers, with the latter one forcibly dependent on the former one. If the two DCBs are applied from different versions, WizardMerge marks them as CU-violated DCBs, even if they are unrelated. This conservative algorithm may result in more false positives, but WizardMerge prioritizes its application to prevent overlooking the detection of CU-violated DCBs.

Listing 3: The definitions of function EnsureNSSInitializedChromeOrContent are the same in both versions

⬇

1// security/manager/ssl/nsNSSComponent.cpp

2bool EnsureNSSInitializedChromeOrContent() {

3 ...

4 if (XRE_IsParentProcess()) {

5 // Create nsISupports * via template class nsCOMPtr.

6 nsCOMPtr<nsISupports> nss =

7 do_GetService(PSM_COMPONENT_CONTRACTID);

8 if (!nss) {

9 return false;

10 }

11 initialized = true;

12 return true;

13 }

14 ...

15}

Listing 4: Difference between commits d2956560d539 and a20620423a53 in file xpcom/base/nsCOMPtr.h

⬇

1diff --git a/xpcom/base/nsCOMPtr.h b/xpcom/base/nsCOMPtr.h

2--- a/xpcom/base/nsCOMPtr.h

3+++ b/xpcom/base/nsCOMPtr.h

4template <class T>

5class MOZ_IS_REFPTR nsCOMPtr final {

6 ...

7};

8

9...

10

11+ template <>

12+ class MOZ_IS_REFPTR nsCOMPtr<nsISupports>

13+ : private nsCOMPtr_base {

14+ ...

15+ }

3 and 4 present another case study where WizardMerge explores conflict-unrelated violated DCBs within Firefox (between versions VA d295656 and VB a206204), which were overlooked by Git merge. Specifically, in the file nsNSSComponent.cpp, both versions define the function EnsureNSSInitializedChromeOrContent with the same contents. In 3 lines 6-7, a pointer to nsISupports is created via the template class nsCOMPtr. The definition of nsCOMPtr is found in nsCOMPtr.h. However, in addition to the generic template, a template specialization (Vandevoorde and Josuttis, 2002) is also defined for nsISupports in VB, as shown in lines 11-15 in 4. This specialization of nsCOMPtr for nsISupports allows users to employ nsCOMPtr¡nsISupports¿ similarly to how they use nsISupports* and void*, essentially as a ’catch-all’ pointer pointing to any valid [XP]COM interface (Mozilla, 2024). When attempting to merge nsCOMPtr.h from the two versions, Git applies the file from VA because the file from VB is identical to the file from the base version. Consequently, in the function EnsureNSSInitializedChromeOrContent, the usage of nsCOMPtr¡nsISupports¿ will follow lines 4-7 in 4, causing nss to only be able to point to the single [XP]COM-correct nsISupports instance within an object. This inconsistency can lead to a potential type confusion bug (Haller et al., 2016; Jeon et al., 2017). Since no compilation error occurs after successfully being applied by Git merge, it would be extremely challenging for developers to notice such a bug, not to mention identify the root cause. With the assistance of WizardMerge, the loss of template specialization can be detected in the merged version, thereby notifying developers to address it manually.

[style=ccl] Conclusion: We assess the efficacy of WizardMerge in identifying CR-violated and CU-violated DCBs by quantifying these DCBs in terms of Lines of Code (LoC), addressing both RQ2 and RQ3. The results reveal that WizardMerge achieves a detection recall of 80.09% and 73.71% for CR-violated DCBs from both merging candidates in the five target projects on average. Furthermore, despite attaining precision rates of 33.26% and 34.66% for CU-violated DCBs in the four target projects on average, WizardMerge effectively reveals deeply concealed CU-violated DCBs that are overlooked by developers. To underscore the impacts of CR-violated and CU-violated DCBs, we present case studies that further elucidate the rationale behind WizardMerge’s noteworthy findings.

5. Discussion

In this section, we discuss the present limitations in WizardMerge’s design and explore potential avenues for enhancing WizardMerge.

Improve Graph Generation. As discussed in §3.3, WizardMerge incorporates three node types and five edge types to construct the ODG. While it adeptly manages numerous merging scenarios, the evaluation outcomes highlighted in §4 suggest that this incompleteness could result in an inability to address certain conflicts or violated DCB instances. For example, WizardMerge cannot infer the dependency from a global variable to a function if the global variable is initialized by the function. This is because, during the compilation process, the initial values of global variables are established before the execution. In contrast, a function’s return value is accessible only after being executed. When initializing global variables with a function’s return value, the compiler transforms the function invocation into initialization code. To ensure the execution of this initialization code before the main program commences, the compiler positions this code within a specific section of the executable file, commonly denoted as the ”.init” segment. This separation facilitates the execution of these initialization routines prior to the initiation of the main program logic. We leave updating the features as our future work to adapt to such scenarios.

Assess Code Optimization. WizardMerge conducts dependency analysis based on the compilation metadata. Nevertheless, it overlooks a substantial amount of code information due to compilation optimizations like unused function elimination and vectorization (LLVM, 2023). As an interim measure, WizardMerge presently enforces the ”O0” option. However, some projects require compilation optimization for successful building. For instance, the Linux kernel relies on optimization to eliminate redundant code segments and disallows the ”O0” option. In the future, we aim to explore how to adapt our approach to arbitrary optimization options.

6. Related Work

6.1. Merging Strategies

Structured Merging

Mastery (Zhu et al., 2022) introduces an innovative structured merging algorithm that employs a dual approach: top-down and bottom-up traversal. It can minimize redundant computations and enable the elegant and efficient handling of the code that has been relocated from its original position to another location. Spork (Larsén et al., 2022) extends the merging algorithm from the 3DM  (Lindholm, 2004) to maintain the well-structured code format and language-specific constructs. To fully retain the original functionality of the merged code, SafeMerge (Sousa et al., 2018) leverages a verification algorithm for analyzing distinct edits independently and combining them to achieve a comprehensive demonstration of conflict freedom.

Semi-structured Merging

JDime (Apel et al., 2012) introduces a structured merge approach with auto-tuning that dynamically adjusts the merge process by switching between unstructured and structured merging based on the presence of conflicts. FSTMerge (Apel et al., 2011) stands as an early example of semi-structured merging, offering a framework for the development of semi-structured merging. Intellimerge (Shen et al., 2019) transforms source code into a program element graph via semantic analysis, matches vertices with similar semantics, merges matched vertices’ textual content, and ultimately translates the resulting graph back into source code files.

The above works, however, cannot help the developers with resolving conflicts. On the contrary, WizardMerge is constructed atop Git merge, furnishing developers with clues to aid manual resolution instead of dictating final merging decisions.

6.2. Conflict Resolution

Conflict Resolution Assistance

TIPMerge (Costa et al., 2016) evaluates the developers’ experience with the key files based on the project and branch history (Costa et al., 2016) to determine the most suitable developers for merging tasks. Automerge (Zhu and He, 2018) relies on version space algebra (Lau et al., 2003) to represent the program space and implement a ranking mechanism to identify a resolution within the program space that is highly likely to align with the developer’s expectations. SoManyConflicts (Shen et al., 2021) is implemented by modeling conflicts and their interrelations as a graph and employing classical graph algorithms to offer recommendations for resolving multiple conflicts more efficiently.

Machine Learning Approaches

MergeBERT (Svyatkovskiy et al., 2022) reframes conflict resolution as a classification problem and leverages token-level three-way differencing and a transformer encoder model to build a neural program merge framework. Gmerge (Zhang et al., 2022) investigates the viability of automated merge conflict resolution through k-shot learning utilizing pre-trained large language models (LLMs), such as GPT-3 (Floridi and Chiriatti, 2020). MergeGen (Dong et al., 2023) treats conflict resolution as a generation task, which can produce new codes that do not exist in input, and produce more flexible combinations.

The essential difference compared with existing assistance systems and machine learning approaches is that WizardMerge considers all modified code snippets, which further helps developers resolve the violated DCBs in merging scenarios.

7. Conclusion

We introduce WizardMerge, a novel code-merging assistance system leveraging the merging results of Git and dependency analysis based on LLVM IR, named definition range, and debug information. Via the dependency analysis, WizardMerge is able to detect the loss of dependency of the named definitions, therefore providing more accurate merging order suggestions including conflicts and applied code blocks for the developers. Our evaluation demonstrates that WizardMerge significantly diminishes conflict merging time costs. Beyond addressing conflicts, WizardMerge provides merging suggestions for most of the code blocks potentially affected by the conflicts. Moreover, WizardMerge exhibits the capability to identify conflict-unrelated code blocks which should require manual intervention yet automatically applied by Git.