MergeBERT: Program Merge Conflict Resolution via Neural Transformers
Authors: Alexey Svyatkovskiy
Todd Mytkowicz
Negar Ghorbani
Sarah Fakhoury
Elizabeth A Dinella
Christian Bird
Neel Sundaresan
Shuvendu Lahiri
Venue: ICLR 2022 Submitted (2022)
Keywords: Software evolution
program merge
ml4code

Abstract: Collaborative software development is an integral part of the modern software development life cycle, essential to the success of large-scale software projects. When multiple developers make concurrent changes around the same lines of code, a merge conflict may occur. 
Such conflicts stall pull requests and continuous integration pipelines for hours to several days, seriously hurting developer productivity.

In this paper, we introduce MergeBERT, a novel neural program merge framework based on the token-level three-way differencing and a transformer encoder model. Exploiting restricted nature of merge conflict resolutions, we reformulate the task of generating the resolution sequence as a classification task over a set of primitive merge patterns extracted from real-world merge commit data.

Our model achieves 63--68\% accuracy of merge resolution synthesis, yielding nearly a 3$\times$ performance improvement over existing structured, and 2$\times$ improvement over neural program merge tools. Finally, we demonstrate that MergeBERT is sufficiently flexible to work with source code files in Java, JavaScript, TypeScript, and C\# programming languages, and can generalize zero-shot to unseen languages.

Under review conference paper ICLR 2022
MERGEBERT: PROGRAM MERGE CONFLICT RESOLU- TION VIA NEURAL TRANSFORMERS
Anonymous authors Paper under double-blind review
ABSTRACT
Collaborative software development is an integral part of the modern software development life cycle, essential to the success of large-scale software projects. When multiple developers make concurrent changes around the same lines of code, a merge conflict may occur. Such conflicts stall pull requests and contin- uous integration pipelines for hours to several days, seriously hurting developer productivity.
this paper. we introduce MergeBERT, a novel neural program merge framework based on the token-level three-way differencing and transformer encoder model. Exploiting restricted nature of merge conflict resolutions, we reformulate the task of generating the resolution sequence as classification task over of primitive merge patterns extracted from real-world merge commit data.
Our model achieves 63-68% accuracy of merge resolution synthesis, yielding nearly 3 performance improvement over existing structured, and 2 improve- ment over neural program merge tools. Finally, we demonstrate that MergeBERT is sufficiently flexible to work with source code files in Java, JavaScript, TypeScript, and C# programming languages, and can generalize zero-shot to unseen languages.
INTRODUCTION
Collaborative software development relies on version control systems such as git to track changes across files. In most projects, developers work primarily in branch of software repository. periodically synchronizing their code changes with ma branch via pull requests (Gousios et al.)
2016). When multiple developers make concurrent changes to the same line of code, merge conflict may occur. According up to 46% of all merge commits result in conflicts. Resolving merge conflicts is a time-consuming, complicated, and error-prone activity that requires understanding both the syntax and program semantics, often taking more time than developing code feature itself (Bird & Zimmermann 2012
empirical study of four large software projects by Zimmermann (2007)
Modern version control systems such as git utilize the di ff3 algorithm for performing unstructured line- based thyee-way merge of input files (Smith) 1998). This algorithm aligns the two-way diffs of two versions of the code A and 13 over the common base O into sequence of diff "slots". At each slot, a change from either or B is selected. If both program versions introduce a change the same slot, a merge conflict is produced, and manual resolution of the conflicting modifications is required.
versatile, production-level merge conflict resolution system should be aware of programming language syntax and semanties yet be sufficienlly flexible to work with any source code files, irrespective of the programming language. It should generalize a wide variety of real-world merge conflicts beyond a specific merge type or domain of software artifacts.
Inspired by the exceptional performance of transformer models and self-supervised pretraining in natural language understanding and generation tasks (Devlin al. 2019; Radford et al. 2019)
Liu et al. [219 Lewis et al., [219 Raffel et al.) 2020) as well as in the programming language domain (Feng et al. 2020) Svyatkovskiy et al. 2020 Clement et al. 2020 Tuffano al. 2020 Ahmad
al. 2021), we introduce MergeBERT: neural program merge framework based token-level three-way differencing and transfer learning. We select a bidirectional transformer encoder (BERT) as our encoder implementation. As a bidirectional encoder. BERT allows to attend to code context surrounding the conflicting chunks, which is key advantage over Tefi-to-right language models. To

---

Under review as conference paper ICLR 2022
endow our model with a basic knowledge of programmiing language syntax and semanties, we adopt a two-step training procedure: (1) unsupervised masked language model pretraining on a massively multilingual source code corpus, (2) supervised finetuning for the sequence classification task. We transfer weights of the pretrained encoder into multi-input model architecture that encodes all imputs that a standard di 1f algorithm takes (two two-way diff's of input programs) as well as the edit sequence information, then aggregate them for learning. While MergeBERT utilizes BERT, other encoder architectures such as LSTM (Hochreiter & Schmidhuber [997). or efficient transformer variants like Poolingformer (Zhang et al. (021) could also be utilized for this task.
The paper contributions are as follows: (1) we introduce MergeBERT a novel transformer-bast program merge framework that leverages token-level three-way way differencing and formulates the task of generating the resolution sequence as a classification task over a set of primitive merge patterns extracted from real-world merge commit data, (2) we effectively transfer knowledge about program syntax and types of source code identifiers from millions of software programs to downstream sequence classification task merge conflict resolution by using self-supervised pretraining (see section 5 which also makes this approach computationally more feasible, (3) we overcome several limitations of the existing neural program merge models Dinella al. (2021) and semi-structured program merge tools like jsre and JDime to improve upon the state-of-the-ard by 2-3x (see sections 7 and 8). and finally, (4) we demonstrate that multilingual MergeBERT is sufficiently versatile to work with programs in Java, JavaScript, TypeSeript, and C#,, and can generalize unseen languages without retraining.
1.1 RELATED WORK
There have been multiple attempts to improve merge algorithms by restricting the them a particular programming language or a specific type of applications (Mens) 2002). Typically, such attempts result in algorithms that do not scale well have low coverage.
Syntactic merge algorithms improve upon diff3 by verifying the syntactie correctness of the merged programs. Several syntactic program merge techniques have been proposed (Westfechtel. 1991. Asklund 1999) which are based on parse trees or abstract syntax trees and graphs.
Apel et al. noted that structured and unstructured merge each has strengths and weaknesses. They developed a struttrructured merge tool. FSTMERGE, which switches between approaches (Apel al. 2010). They later introduced JDIME, an approach that automatically tunes a mixture of structured and unstructured merge based conffict locations (Apel et al. 2012). AUTOMERGE tool (Zhu & He 2018) improves upon the JDIME by adding a built-in matcher to check output resolutions for the merges performed by JDIME. AUTOMERGE synthesizes resolutions only when the structured merge algorithm fails to complete merge. (Trindade Tavares et al. (2019) later implemented jsFgeMerge by adapting an off-the-shelf grammar for JavaScript and modifying the FSTMerge algorithm itself address JavaScript specific issues.
In addition, Pan et al. (2021) explore using program synthesis to learn repeated merge resolutions within a project. However, the approach is limited to single C++ project, and only deals with restricted cases of import statements. Sousa et al. (2018) explore the use of program verification to certify that a merge obeys a semantic correctness criteria, but does not help resolve merge conflicts.
MOTIVATING EXAMPLE
In this section, we formulate the traditional line- merge conflict resolution problem as classifi- cation task and show how token-level formulation of d ff3 helps localize the merge conflicts. Fig. [ provides an example merge conffict in JavaScript. Fig. I[a) on the left shows the standard diff3 markers "<<<<<<< A.js", "IIIII O.js", "_-====" and ">>>>>>> B.js", which denote the confficting regions introduced by programs A, base O, and B respectively. Here, O represents the most common ancestor of programs A and B in the version control history. We denote the program text of di diff3 conflicting regions as Ay. B,. O,, where j is a conflict index. The conflict index may be omitted when referring to programs consisting of single conflict only. We refer to the program text outside the conflicting chunks, common to all merged programs versions, as a prefix and suffix, and denote it respectively as Pref and Suff throughout the paper. First, MergeBERT represents each line-level merge conflict instance at token level (Fig. [b)) which localizes conflicting regions,

---

Under review conference paper ICLR 2022
yielding a A, C O, and then invokes the neural model to predict a resolution via classification (Fig. (F).. Here, and throughout the paper we will use lower case notations to refer attributes of token-level differencing (e.g. b, and o are conflict regions produced by di FF3 of token granularity). Intuitively, token diff3 first turns the line- ane-structured text into list of tokens (including space and line delimiters), applies standard di ff3 algorithm to the resulting documents, and reconstructs the merged document at line level. As result of token-level merge, the whole "let max (y, string cleanly merged, becoming part of the program prefix, and prepended to the program suffix.
Token-level di diff3k is syntactic merge algorithm. As such, it does not guarantee semantic cor- rectness of the merged program. In most cases (82%) however, token merge matches the user resolution.
Observe, that the resolution does not consist of any single line from either or since both edits mod- ify a common line present in the base. Hence, earlier neural approaches such as DeepMerge (Dinella ct al. 202I) would not be able synthesize the resolution. On the other hand, structured merge techniques (such as Mergeeygyy [Trindade Tavares et al. (2019)) cannot resolve the conflict as the conflict appears on program statement, which leads to side effects (e.g. syntactically incorrect code).
token-level merge can interleave edits within lines (i.e., tokens which one edit does not conflict with another are trivially merged). Consider A's edit of the var to let keyword. Such non- conflicting edits suffice demonstrate the above. Likewise, consider the token-level conflict for the arguments to the max function: an appropriate model trained on JavaScript should be able easily deduce that taking the edit from B (i.c., 11 zz) captures the behavior of A's edit as well. The suggested resolution gives intuitive demonstration for how MergeBERT turns complex line-level resolution into simpler token-level classification problem.
MergeBERT can deal with non-trivial real-world merges composed of multiple conflicting chunks. We include complete example of such merge conflict in the Appendix.
y
Y= <CCEREE A.js
Prefix
let (y,
<<<C<<< a.1=
II|IIII o.
(y,
11
y (y,
0.js
var x max (y, 10)
10
console. log (x)
11,
B.
>>>>>>> B. console. Log (x)
Suffix
console.. log (x)
(a) Line-level conflict
(b) Token-level conflict
(c) Resolved merge
Figure 1:
Example merge conflict represented through standard di EE3 (left) and token-level diff3 (center), and the user resolution (right). The merge conflict resolution takes the token-level edit b.
3 BACKGROUND: DATA-DRIVEN MERGE
Dinella al. (2021 introduced the data-driven program merge problem as a supervised machine
learning problem. A program merge consists of 4-tuple programs (A, (A,,,O, B,,, where
1. The base program O is the most common ancestor in the version history for programs A and B3,
2. di fE3 produces an unstructured live-level conflict when applied to (A,, B, O), and
M the program with the developer resolution, having no conflicts.
Given a set of such programs and merges (A, B, O M.,). the goal of data-driven merge is to leam function, merge, that maximizes the of examples where merge(A, 18, O) M. Moreover,

---

Under review conference paper ICLR 2022
since a program may have multiple unstructured conflicts (A,, B,, J,,))., the data-driven merge considers the different merge tuples corresponding to the conflicting regions independently, and poses the learning problem over all the merge tuples present in (A, B, O.M). Dinella et al. (202T) also provide an algorithu for extracting the exact resolution regions for each merge tuple and define a dataset that corresponds to non- non-trivial resolutions where the developer does not drop one of the changes in the resolution. Further, they provide a eequence-t-ssqquee architecture, where bi-directional gated recurrent unit (GRU) is used for encoding the merge inputs comprising of (A, B3, Q) segments of a merge tuple, and a pointer mechanism is used to restrict the output to only choose from line segments present in the input. Given the restriction on copying only lines from inputs, the dataset defined in the paper did not consider merges where the resolution required leken-level interleaving, such as the conflict in Figure [ of merge conflicts in single language, JavaScript. In contrast, our paper addresses both of these limitations.
encoder-decoder based
And, lastly, the dataset consists
MERGE CONFLICT RESOLUTION AS A CLASSIFICATION TASK
In this work, demonstrate how exploit the restricted nature of merge conflict resolutions (compared to an arbitrary program repair) to leverage discriminative models to perform the task of generating the resolution sequence. We have empirically observed that a diff3 of token granularity enjoys two useful properties over its live-level counterpart: (i) it helps localize the merge conflicts small program segments, effectively reducing the size of conflicting regions, and (ii) most resolutions of merge conflicts produced by token di fi3 consist entirely of changes from or b or o or a sequential composition of a followed by b vice versa. On the flip side, token-level merge has the potential to introduce many small conflicts. To balance the trade-off, we start with the line-level conflicts as produced by the standard diff3 and perform a token-level merge of only the segments present in the line-level conflict. There are several potential outcomes for such two-level merge the line-level:
A conflict-free token-level merge: For example, the edit from A about 1et is merged since B does not edit that slot as shown in Fig. (bb).
A single localized token-level merge conflict: For example, the edit from both A and B for the arguments of max yields a single conflict as shown in Fig. Fig.
Multiple token-level conflicts: Such a case (not illustrated above) can result in several token-level conflicts.
Token-level diff3 applied to a merge tuple (A,B,O, would generally result in a set of localized confticting regions and resolutions (a,, oy: We empirically observe that majority of such r are comprised entirely (i) aj. (ti) by. (111 oj. concatenating (fu) aj. by or (v) by. aj. and variants of (iu-e) having the lines present in the base excluded, comprising a total of nine primitive merge resolution patterns (see section 10.1 in Appendix for more details about the primitive merge patterns).
We. therefore, can treat the problem of constructing ry as a classification task to predict between these possibilities. It is important note that although we are predicting simple resolution strategies at token-level, they translate to complex interleavings line-level. Of course, not all line-level conflicts are resolved by breaking that conflict to tokens-sone some resolutions which are complex line-based interleavings are not expressible as a choice at the token-level.
The key practical advantage of formulating merge conflict resolution classification task is a significant reduction in total FLOPS required decode a resolution region, as compared to generative models, making this approach an appealing candidate for deployment in IDEs (see section I1.I)
5 MERGEBERT: NEURAL PROGRAM MERGE FRAMEWORK
MergeBERT is textual program merge model based on the bidirectional transformer encoder (BERT) model. It approaches merge conflict resolution as sequence classification task given conflicting regions extracted with token-level differencing and surrounding code context. The key technical

---

steps each Under review conference paper ICLR 2022
Let eax 11, 4)
PEP 01C C
Becooiing
MJl Type
Classsfication
2et
coceece beanch
Enserdee
23,
Lobeoding
Towe Esbaodin5
Scoodee
An overview of the MergeBERT architecture. From left to right: given conflicting programs A. B and O token-level differencing is performed first, next, programs tokenized and the corresponding sequences are aligned (a and a b/o, and o|6). We extract pair of token sequences (Amo and Abo). Four aligned token sequences are fed to the multi-input encoder neural network, while edit sequences
Figure 2:
consumed as type embeddings. Finally, encoded token sequences are summarized into hidden state which serves as input to classification layer. See Algorithm| forr details about merge resolution decoding. Parts of the neural networks colored in blue finetuned, the rest are transferred from pretrained encoder and frozen.
innovation to MergeBERT lies how it breaks program text into an input representation amenable to training with transformer encoder and how it aggregates various input encodings for classification.
MergeBERT exploits the traditional two-step pretraining and finetuning training procedure. We use self-supervised masked language modeling (MLM) pretraining on massively multilingual source code corpus followed by supervised finetuning for a classification task (section 11.4 provides details about the implementation). For finetuning, construct multi-ine input model architecture that encodes pair-wir wise aligned token sequences conflicting programs A and B with respect original program O, as well as corresponding edit sequence steps, then aggregate them for learning. An overview MergeBERT model architecture is shown in Fig. 2
Given merge tuple (A, B, (.M) with leven-level conflicting chunks uy. 0j. MergeBERT models the following conditional probability distribution:
p(ry az by
(1)
and consequently, for entire programs:
p P
II b(ryla,,
(2)
where N is number token-level conflicts in the merge tuple (,,
Treating teken-level conflicts independently simplifying assumption. However, data shows that only 5% of merge conflicts result in more than I token-level conflict per line-level conflict.
5.1 REPRESENTING MERGE CONFLICTS
As shown by Dinella et al. 2021 l an effective merge representation needs to be "edit aware" to provide an indication that A and B are edits of the original program O. Prior work distributed representations edits (Yin al. 2019) descríbes how compute a two-way diff using a standard deterministic diffing algorithm and represent the resulting pair-wise alignment as a vector consumable by machine learning models.
Given merge tuple (A, B, M), MergeBERT first calculates two two-way alignments between the sequence tokens conflicting regions a (respectively b) with respect to that the original program o. For each pair of aligned token sequence we extract an "edit sequence" that represents how turn the second sequence into the first. These edit sequences A and Ab. are comprised of

---

Under review conference paper ICLR 2022
the following editing actions (kinds of edits): represents equivalent tokens, + represents insertions, represents deletions, < represents a replacement, and 0 is used as a padding token. Overall, this produces four token sequences and two edit sequences: (#lo: ola> and A...) and (6)... o/s, and A.o). Each token sequence covers the corresponding conflicting region and, potentially, surrounding code tokens. Fig. 2 shows an example of edit sequence.
5.2 CONTEXT ENCODING
We pretrain a BERT model & following the masked language modeling objective multilingual dataset of source code files. In each source code file, of tokens is sampled random uniform and replaced with [MASK] symbols, and the model aims to reconstruct the original sequence. We make use of a Byte-Pair Encoding (BPE) unsupervised tokenization procedure to avoid a blowup the vocabulary size given the sparse nature of code identifiers Karampatsis et al. (2020). Besides code tokens, the vocabulary includes the special symbols representing editing steps and the [MASK] symbol.
During finetuning, introduce edit type embedding combining it with token and position embeddings via addition: S ST + Sp Sg. Edit type embedding helps the model recognize the edit steps, which are not supplied during pretraining. See Fig. in the Appendix for details.
As shown in Fig. 2 we utilize pretrained encoder model to independently encode each of the four token sequences o. ola. blo. and 0|&) of merged programs, passing edit sequences (Aao and Abo) as type embedding indices.
MERGE TUPLE SUMMARIZATION
In standard sequence learning tasks there is one input and one output sequence. In merge conflict resolution setting, there multiple input programs and resolution. To facilitate learning this setting, we construct MergeBERT as multi-input encoder neural network, which first encodes token sequences a/o. o/a- bla. and and then aggregates them into a single hidden summarization state:
hm
Σ
0: E(x,, A)
V.E(alo.ol..Mol Mo..ol)))
where is the context encoder and Ex,,, A) are the embedding tensors for each of the sequences 3; & (alo, ola; blo, ola). After encoding and aggregation linear classification layer with softmax is applied:
Mrrs by. oÿ) = softmax(W hm + b)
(4)
The resulting line-level resolution region is obtained by concatenating the prefix pref, predicted token-level resolution rj. and the suffix suff. f. Finally, in the case of one-to-many correspondence between the original line-level and the token-level conflicts (see [1.5 in the Appendix for example [ pseudocode), MergeBERT uses a standard beam-search to decode the most promising predictions.
6 DATASET
To create dataset for pretraining, we clone all non-fork repositories with more than 20 stars GitHub that have C, C++ C#, Python, Java, JavaScript, TypeScript, PHP, Go, and Ruby as their top language. The resulting dataset comprises over 64 million source code files.
The finetuning dataset is mined from 100 thousand open source software repositories in multiple programming languages with merge conflicts. It contains commits from git histories with exactly two parents, which resulted in a merge conflict. We replay git merge on the two parents to see if it generates any conflicts. Otherwise, we ignore the merge from our dataset. We follow Dinella ct al. (2021) to extract resolution regions-however however, we do not restrict ourselves to conflicts with less than 30 lines only, Lastly, we extract token-level conflicts and labels from line-level conflicts and resolutions. Tab. provides summary of the finetuning dataset.

---

Under review conference paper ICLR 2022
7 BASELINE MODELS
7.1 LANGUAGE MODEL BASELINE
Neural language models (LMs)) have shown great performance in natural language generation (Rad) ford al., 2019; Sellam et al. 2020), and have been successfully applied to domain source code (Hindle et al. 2012: SSyatkovskiy et al.) 2020) Feng et al.) 2020). We consider the gener- ative pretrained transformer language model for code (GPT-C) and appeal to the naturalness of software (Allamanis et al. 2018) to construct our baseline approach the merge resolution synthesis task. We establish the following baseline: given an unstructured line-level conflict produced by diff3, take the common source code prefix Pref acting as intent for program merge. We attempt to generate an entire resolution region ooken-by-token using beam search. an ablation experiment, we repeat this for the conflicts produced with the token-level differencing algorithm (Fig. shows details about prefix and conflicting regions).
7.2 DEEPMERGE: NEURAL. MODEL FOR INTERLEAVINGS
Next, we consider DeepMerge (Dinella ct al. 2021) :: sequence-to-sequeeee model based on the bidirectional GRU summarized in section It learns generate resolution region by choosing from line segments present the input (line interleavings) with a pointer mechanism. We retrain the DeepMerge model on our TypeScript dataset.
7.3 JDIME
Looking stronger baseline, we consider JDIME, a Java-specific merge tool that automatically tunes the merging process by switching between structured and unstructured merge algorithms (Apel al. 2012). Structured merge is abstract syntax tree (AST) aware and leverages syntactic information to improve matching precision of conflicting nodes. To compare accuracy of JDIME to that MergeBERT, we use the Java test and complete the following evaluation steps: first, we identify the set of merge conflict scenarios where JDME did report merge conflict, and the standard dif ff3 algorithm did. Second, we compare the JDIME output to the version of the code where merge conflict is resolved. Third, we calculate. DIME accuracy by identifying the number of merges where JDIME output file correctly matches the resolved conflict file.
As a result of its AST matching approach, code generated by JDime is reformatted, and the original order of statements is not always preserved. In addition, source code comments that are part of conflicting code chunks are not merged.
A simple syntactic comparison is too restrictive, and JDime merge output can still be semantically correct. To accurately identify semantically equivalent merges, we use GumTree Falleri et al. (2014). an AST differencing tool, to compute fine grained edit scripts between the two merge files. By ignoring semantically equivalent differences computed by GumTTre (such as moved method declarations) we have a more accurate baseline comparison between the number of semantically equivalent merges generated by JDime and MergeBERT.
7.4 JSFSTMERGE
Apel et al. (001 introduced FSTMerge, semi-structured merge engine using an approach similar to JDIME, but that that allows a user to provide an annotated language grammar specification for any language. [Trindade Tavares al. (2019) implemented MergeMerge by adapting off-the-shelf grammar for JavaScript to address shortcomings of FSTMerge and also modifying the FSTMerge algorithm itself. For example, statements can be intermingled with function declarations at the same syntactic level, and statement order must be preserved while function order does not. jsFSeMerge allows for certain types of nodes to maintain their relative order (e.g.. statements) while others may be order independent (e.g., function declarations) even if they share the same parent node.
For cases where Merge produces a resolution that does not match the user resolution, we manually inspect the output for semantic equivalence (e.g., reordered import statements).

---

Under review conference paper ICLR 2022
EVALUATION
We evaluate MergeBERTTs accuracy of resolution synthesis. Our evaluation metries are precision recall of verbatim string match (modulo whitespaces or indentation) of the decoded predictions to the user resolution extracted from real-world merge resolutions. This definition is rather restrictive as a predicted resolution might differ from the true user resolution by, for instance, only the order of statements, being semantically equivalent otherwise. As such, this evaluation approach gives a lower bound of the MergeBERT model performance.
In addition the precision and recall, estimate the fraction of syntactically correct (or parseable) source code suggestions to filter out merge resolutions with syntax errors.
8.1 BASELINE MODEL EVALUATIONS
Table I:
Evaluation results for MergeBERT and various neural baselines calculated for merge conflicts in TypeScript programming language test set. The table shows top-1 precision, recall, and F-score metries.
Approach
Granularity
Precision
Recall
F-score
LM
Line
3.6
3.1
3.3
DeepMerge
Line
55.0
35.1
45.3
diff3
Token
82.4
36.1
50.2
LM
Token
49.7
48.1
48,9
DeepMerge
Token
64.5
42.7
MergeBERT
Token
69.1
68.2
68.7
As seen Tab. D performance of language model baselines on the task of merge resolution synthesis is relatively low, suggesting that the naturalness hypothesis is insufficient to capture the developer intent when merging programs. This is perhaps not surprising given the notion of precision that does not tolerate even a single token mismatch.
MergeBERR tool is based on two core components: token-level di FF3 and a multi-input neural transfommer model. The token-level differencing algorithm alone gives high top-1 precision of 82.4%, with relatively low recall of only 36.1% 1.. Combined with the neural transformer model, the recall is increased to a total of 68.2%. Note, as a deterministic algorithm token-level di ff3 can only provide single suggestion.
DeepMerge precision of merge resolution synthesis quite admirable, showing 55.0% top-I precision. However, it was only able to produce accurate predictions for 63.8% generate predictions for merge conflicts which are not representable as a line interleaving. This type of merge conflicts comprises almost third of the test resulting in recall of 35.1% which significantly lower than MergeBERT, and 50% lower F-score.
test conflicts, failing
Ablation Study
We conduct two ablation experiments to carry out a more precise comparison against the DeepMerge baseline.
First, we evaluate DeepMerge model in combination with the token-level di ff3. As seen in Tab. T overall performance improves, resulting in a 13% higher F-score, but still falling short of MergeBERT by 34% F-score (7% lower precision and 60% lower recall). Second, since DeepMerge is not able to produce accurate predictions for merge conflicts which are not representable restrict our test set to this type of merge conflicts only. Overall, MergeBERT yields 70.6% (78.6% 6%) top-1 1 (top-3) precision compared to 55.0% (59.1%) for DeepMerge. showing that MergeBERT performance on this merge type comparable that on the entire test set.
line interleaving, we
Semi-structured Program Merge Baselines
As can be seen from Tab. 2 jsFSTMerge only able to produce a resolution for 22.8% of conflicts. and the produced resolution is correct only 15.8% of the time. This is in line with the conclusions of the creators of Merge that semi-structured merge approaches may be advantageous

---

Under review conference paper ICLR 2022
Table 2: Comparison of MergeBERT to JDime and jsFee semi-structurre merge tools. The table shows top-1 precision, recall, F-score of merge resolution synthesis, fraction of merge conflicts an approach generated resolutions for, and percentage of syntactically correct predictions. JDime evaluation is on a Java data set and jsFSTMerge is on a JavaScript data set.
Approach
Language
Precision
Recall
F-score
Syntax (%)
JDime
Java
26.3
21.6
23.7
90.9
MergeBERT
Java
63.9
63.2
63.5
98.3
jsFgeMerge
JavaScript
15.8
3.6
5.9
94.4
MergeBERT
JavaScript
66.9
65.6
66.2
97.4
Table 3: Detailed evaluation results for monolingual and multilingual MergeBERT models, well zero-shot performance on an unseen language. The table shows precision, recall, F-score of merge resolution synthesis, and percentage of syntactically correct predictions. Top: monolingual models, bottom: multilingual.
Test (Train) Languages
Precision
Recall
F-score
Syntax (%)
Top-1
Top-3
Top-1
Top-3
Top-1
Top-3
JavaScript (IS)
66.9
75.4
65.6
73.9
66.2
74.6
97.4
TypeScript (TS)
69.1
76.6
68.2
75.6
68.7
76.1
97.0
Java (Java)
63.9
76.1
63.2
75.2
63.5
75.6
98.3
C# (C#)
68.7
76.4
67.3
74.8
68.0
75.6
98.3
JavaScript (JS. TS, C#. Java)
66.6
75.2
65.3
73.8
65.9
74.5
97.4
TypeScript (JS, TS, C#, Java)
68.5
76.8
67.6
75.8
68.0
76.3
96.9
Java (JS. TS, C#, Java)
63.6
76.0
62.9
75.1
63.2
75.6
98.2
C# (JS, TS, C#, Java)
66.3
76.2
65.1
74.8
65.7
75.5
98.3
Scala (JS, TS, CH,, Java)
57.8
64.8
56.5
63.3
57.1
64.1
97.9
for dynamic scripting languages (Trindade Tavares et al. 2019). Because jsFST may produce reformatted code, manually examined cases where resolution produced but did match the user resolution (our oracle). If the produced resolution was semantically equivalent to the user resolution, we classified it as correct.
Tab. 3 shows the detailed evaluation results of the MergeBERT. As seen, multilingual variant of MergeBERRT yields 63.6 68.5% top-1 and 75.2 76.8% top-3 precision of verbatim match and relatively high recall values. Overall, the multilingual variant the model generates results comparable to the monolingual versions on the languages present in the training set and shows the potential for zero-shot generalization to unseen languages. We test the zero-shot generalization property on merge conflicts in Scald" programming language and obtain an encouraging 64.8% top-3 precision of merge resolution synthesis.
9 CONCLUSION
This paper introduces MergeBERT, transformer-based program merge framework that leverages token-level differencing and reformulates the task of generating the resolution sequence as a clas- sification task over a set of primitive merge patterns extracted from real-world merge commit data. MergeBERT exploits pretraining over massive amounts of code and then finetuning on specific pro- gramming languages, achieving 64-69% precision and 63 68% recall merge resolution synthesis. Lastly, Mer is flexible and effective, capable of resolving more conflicts than the existing tools in multiple programming languages.
Our work focuses on helping software developers resolve merge conflicts and improve their produc- tivity. The lightweight finetuning approach that lies at the core of this tool promotes the re-usability of pretrained transformer models for software engineering tasks.
http://wwww.sell--lag..or

---

Under review conference paper ICLR 2022
REFERENCES
Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai- Wei Chang. Unified pre- pre-training for program understanding and generation. CoRR, abs/2103.06333, 2021. URL https://axxxx
Atg/abs/2100 .163333333333333 06333
Miltiadis Allamanis, Earl T. Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Comput. Sure, 51)4), July 2018. ISSN 0360-0300.
doi: 10. 145/3212695, URL https://dcciiic http://ddoooo///o/oo//o 1t/gg/11.00 100.111115/222250
Sven Apel, Jörg Liebig. Christian Lengauer, Christian Kästner, and William R Cook. Semistructured merge in revision control systems. In VaMoS. pp. 13-19, 2010.
Sven Apel, Jörg Licbig, Benjamin Brandl, Christian Lengauer, and Christian Kästner. Semistructured merge: Rethinking merge in revision control systems. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE '11, pp. 190-200, New York, NY, USA, 201 Association for Computing Machinery. ISBN 9781450304436. doi: 10. 14.114//222113322022 20251:
Sven Apel, Olaf Leßenich, and Christian Lengauer. Structured merge with auto-tuning: balancing precision and performance. In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, pp. 120-129, 2012.
Ulf Asklund. Identifying conflicts during structural merge. 1999.
Christian Bird and Thomas Zimmermann. Assessing the value of branches with what-if analysis. Proceedings of the 20th International Symposium on Foundations of Software Engineering. ACM, 2012.
Colin Clement, Dawn Drain, Jonathan Timcheck. Alexey Svyatkovskiy, and Neel Sundaresan. Pymt5: Multi-mode translation of natural language and python code with transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9052-9065, 2020.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Compulational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4171-4188 Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19- 1423. U
7/www. a web.. www.oorg////totooo ogy/N19 9-443
Elizabeth Dinella, Todd Mytkowicz, Alexey Svyatkovskiy, Christian Bird, Mayur Naik, and Shu- vendu K. Lahiri. Deepmerge: Learning to merge programs, 2021.
Jean-Rémy Falleri, Floréal Morandat, Xavier Blane, Matias Martinez, and Martin Monperrus. Fine- grained and accurate source code differencing. In ACM/IEEE International Conference on Au- tomated Software Engineering, ASE '4, Vasterus, Sweden September 15 19, 2014, pp. 313- 324, 2014. doi: 011144/2662237.26-2222 URL httptt acm. org wttp://.g......... 2ttp//....45/2222999 2642982]
Zhangyin Feng. Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng. Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, and Ming Zhou. CodeBERT: A pre-trained model for programming and natural languages. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 1547, Online, November 2020. Association for Computational Linguistics. doi: 10. 1t..1166/112220.fff 10.11665//1/2220..mmdg----- eet.sseemmll111999 URL http::::///www.w.w.bbbbb org/ httpr////ttlclll//2.ooo Findings-
Georgios Gousios, Margaret-Ame Anne Storey, and Alberto Bacchelli. Work practices and challenges in pull-based development: the contributor's perspective. In 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE), pp. 285-296. IEEE, 2016.
10

---

Under review conference paper ICLR 2022
Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, Michele Tufano, Shao Kun Deng, Colin B. Clement, Dawn Drain, Neel Sundaresan, Jian Yin, Daxin Jiang, and Ming Zhou. Graphcodebert: Pre-training code representations with data flow. 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https:// @penrevics not www.mrorrmmoooooo 1TC44024322
Abram Hindle, Earl T. Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. On the naturalness of software. In Proceedings of the 34th International Conference on Software Engineering, ICSE '12 pp. 837-847. IEEE Press, 2012. ISBN 9781467310673.
Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Computation, 9 doi: 10.1162/neco. 1997.9.8.1735 URL https
18):173 11 1997. ISSN 0899-7667.
//dci.org/10..
1997. 9.8.979....777..
Rafacl-Michael Karampatsis, Hlib Babii, Romain Robbes, Charles Sutton, and Andrea Janes. Big code & big vocabulary: -ocablooybbllry models for source code. In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering. ICSE '20, pp. 1073-1085, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 08884455712100 doi: 10. 145/ $377811.3380342
Mike Lewis. Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlmoyer. Bart: Denoising sqquence-to-sqqeee pre-training for natural language generation, translation, and comprehension, 2019.
Y. Liu, Myle Oit, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, M. Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1 1692, 2019.
Tom Mens. A state-of-the-an survey software merging. IEEE transactions software engineering, 28(5):449 462, 2002.
Rangeet Pan, Vu Le, Nachiappan Nagappan, Sumit Gulwani, Shuvendu K. Lahiri, and Mike Kaufman. Can program synthesis be used to learn merge conflict resolutions? an empirical analysis. CoRR, abs/2103.02004, 2021. URL | dattps://arxian
2200//1003000000 02004.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and lly Sutskever. Language models are unsupervised multitask leameers 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer, 2020.
Baptiste Rozière, Marie-Anne Lachaux, Mare Szafraniec, and Guillaume Lample. DOBF: A deob- fuscation pre-training objective for programming languages. CoRR, abs/2102.07492, 2021. URL
https://azxiv. www.:/i.worrr.aao.. wttp://gp..p////......... /ttpo////222.e. 07492
Thibault Sellam, Dipanjan Das. and Ankur Parikh. BLEURT: Learning robust metrics for text genera- tion. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pp. 7881-7892, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/v1/ 2020 main.704, 704. URL /ttps::/ hwwp::///wwww... wwwweb.wwbbb...... wwwpww.wwgwccc.o...tw.oo...ooo.t http///ooooo//o.oooeoe/oo/
704
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. 1865386 1/P16 1162. UtL/https:/// http://wwww/ccccoocoo orgg
mathelogy/PIse 1162
R. Smith. Gnu dift3, distributed with GNU diffutils package, April 1998.
M. Sousa, I. Dillig, and S. K. Lahiri. Verified three-way program merge. Proc. ACM Program. Lang.. 2: 1-:::2,,, 2018.

---

Under review conference paper ICLR 2022
Alexey Svyatkovskiy, Shao Kun Deng. Shengyu Fu, and Neel Sundaresan. Intellicode compose: Code generation using transformer. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, ESSE//FSE 2020, pp. 1433-1es 1143,14,,,aa New York. NY. USA. 2020, Association for Computing Machinery. ISBN 9781450370431. doi: 011144/3368899344100009
341 7058
Alberto Trindade Tavares, Paulo Borba, Guilherme Cavalcanti, and Sérgio Soares. Semistructured merge in javascript systems. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 1014-1025, 2019. doi: 10.1 10.1009//TE 20..00098....
Michele Tufano, Dawn Drain, Alexey Svyatkovskiy, Shao Kun Deng, and Neel Sundaresan, Unit test case generation with transfommers. CoRR, (bss22009.056177 2020. URL w bttts::/aaxxi:s orgg/ abs/2009.
Bemhard Westfechtel. Structure-oriented merging revisions of software documents. In Proceedings of the 3rd international workshop on Software configuration management, pp. 68-79, 1991.
Pengcheng Yin, Graham Neubig. Miltiadis Allamanis, Marc Brockschmidt, and Alexander L. Gaunt. Learning represent edits, 2019.
Hang Zhang, Yeyun Gong, Yelong Shen, Weisheng Li, Jiancheng Lv, Nan Duan, and Weizhu Chen. Poolingformer: Long document modeling with pooling attention. CoRR, abs/2105.04371, 2021. URL http::ttt::///tt //ax::://///xvv// org/
Fengmin Zhu and Fei He. Conflict resolution for structured merge via version space algebra. Proc. ACM Program. Lang. 2(00PSLA), October 2018. doi: 10.1145/3276536. URL https 7
10. 44/ 7 66366
Thomas Zimmermann. Mining workspace updates in cvs. In Proceedings of the Fourth International Workshop on Mining Software Repositories, MSR '07, pp. 11, USA, 2007. IEER Computer Society. ISBN 076952950X. doi: 2..100//SR.2007. URL httts:/::://// htt.:::::///oi.og//.......
MSR.2007 2007.22
10
APPENDIX
10.1
PRIMITIVE MERGE RESOLUTION TYPES
Given a merge tuple (A, ...M) with line-level conflicting regions A,, B,, O., i=O..,, and token- level confficting regions a), of corresponding line-level conflict we define following nine basic merge resolution types which serve as labels for supervised classification task:
1. Take changes a) proposed in program A (developer branch A) as resolution,
Take changes bj proposed in program B as resolution.
3. Take changes of in the base reference program O as resolution,
4. Take string concatenation of changes in at and by, resolution,
Take string concatenation of changes in bf and az as resolution (reverse order as compared to the previous),
Take changes as proposed in program A, excluding the lines also present in the base reference program O, as resolution,
Take changes bj proposed program B, excluding the lines present the base, as resolution,
8. Take string concatenation of changes in af and bj. excluding the lines present in the base, resolution,
9. Take string concatenation of changes in bf and af. excluding the lines present in the base. resolution (reverse order as compared to the previous).

---

Under review conference paper ICLR 2022
A-25.78 %
%
Label 21.64
Other 16.16
Remove base 6.39
1.08% %
Base 0.31 %
Figure 3: Summary merge conflict resolution labels in our dataset for TypeScript: label distribution for merge conflicts extracted with the standard (line-level) dift' algorithm, right.
While the above primitive merge patterns are defined for token-level confticting chunks, same definition could be applied line-level, substituting aj, bj. of chunks with A,, B., O,,
We use data-driven approach to identify these 9 primitive merge resolution patterns based on the analysis of the real-world merge conflict resolutions from GitHuh. Our analysis shows that over 99% of all the merge conflicts be represented using these labels. While the above nine resolution types are primitive, they form basis sufficient to cover large class of real-world merge resolutions modern version control systems, including arbitrary combinations or interleavings of lines.
Fig. 1ig.3sshom shows the label distribution obtained for the standard (line-level) diff3 conflicting regions in dataset for TypeScript programming language. As seen, nearly 50% of all cases are trivial take changes from branch A or Arguably, these cases can he resolved without machine learning and are easily addressed by take ours or take theirs merge resolution strategies. The "Remove base" category combines the four primitive merge patterns that remove the lines present in the base branch from the resolution (e.g. take changes proposed in one program and exclude the lines present base). The "Other" category consists of arbitrary line- tne-interleavings.
Fig. 1 shows the label distribution obtained for token-level differencing algorithm. It excludes trivial (take A or take B) merge resolutions line-level. Note, that "take merge resolution token-leve does not correspond to "take ours" or "take theirs" merge resolution strategy, and can map to any label at line-level, thus representing non-trivial merge scenario stimulating for machine learning studies.
is important stress, these primitive merge resolution types token-level are not strictly defined templates dictating which syntactic structures should be selected from input programs. For instance, a label "take changes proposed in program A correspond single code token well entire method signature or body. such, the merge types are restrictive their representation power of merge conflicts.
10.2 SUMMARY OF THE FINETUNING DATASET
Tab. 4 shows the summary of the finetuning merge conflict resolution dataset. The finctuning dataset is split into development and test set in the proportion 80/20 at random at file-level. The development set further split into train and validation in 80/20 proportion the merge conflict level.

---

Under review conference paper ICLR 2022
A R-399.23 %
AB-19.90
3.96 %
bese-1.78
0.38 %
Falled to Label- 0.06 %
Figure 4: Summary of merge conffict resolution labels in our dataset for TypeScript: label distribution for merge conflicts extracted with token-level differencing algorithm.
Table 4: Number of merge conflicts in the dataset.
Programming language
Development set
Test set
C#
27874
6969
JavaSeript TypeScript
66573
16644
22422 103065
5606
Java
25767
Scala
389
11 MERGE RESOLUTION DECODING
Each model prediction yields probability distribution p(r, laj, by, 0;) over primitive merge patterns given token-level conflict. In case one-to-many correspondence between original line-level and the token-level confficts (see, for instance, Fig. 8 to approximate the original p( p( A, B, O) we decode the most promising combination from the predicted solution space. This can be conceptualized maximum cost path search on matrix, which we approach beam search algorithm.
Algorithm 1 Merge conflict resolution decoding algorithm (beam search) with MergeBERT
b (ro: 0}
Initialize beam state, logprob] Perform token-level differencing
{az, by. 0z, ry 1r 1 + (ccken_
for 0 to N do
a, Ab = 0Ao = 0 then return pref, rj suff,
b case token-level merge results in clean merge
else
for (r), TopK[mergebert((jllg, by, 0;)) bu prefj : r5 suff,. //}
Update beam each token-level
conflict j
end for
b - TopM(b)
Prune candidates to keep top-M
end end for
+ b(0)
Get resolution region string
return R

---

Under review conference paper ICLR 2022
As a result, the model prediction for each line-level conflict consists of either label for a token-level conflict or a combination of labels for multiple token-level conflicts representing the best prediction for each token-level conflict within the line-level conflict. Given these labels for each line-level conflict and the contents of the merged file, MergeBERT generates the code corresponding to the resolution region. The contents of the merged file includes the conflict in question and its surrounding regions. Therefore, for each confficting line, MergeBERT chooses between the versions of code based on the labels the model produced and generates the resolution code by concatenating them. Afterwards, MergeBERT checks the syntax of the generated resolved code, and in case of correctness, outputs it as the candidate merge conflict resolution.
In of multiple line-level conflicts in the merged file, MergeBERT refines the contents of the merged file that serves as the surrounding region of the conflict. More specifically, for each line-level conflict, MergeBERT replaces the other conflicts in the the merged file contents with the code it previously generated as their predicted resolutions. For this purpose, MergeBERT updates the contents of the merged file after resolving each line-level conflict with code generates as the conffict resolution based on the model prediction.
11.1 INFERENCE COST
Computational efficiency is important constraint influencing machine learning design decisions production environments (e.g. deployment IDE, GitHub action). the following, we discuss inference costs and floating point operations per second (FIOPs)) of MergeBERT as compared to the language model baseline.
In this paper, reformulate the task of merge conflict region classification problem. This provides a major speedup during inference, due to a smaller number of inference calls necessary to decode resolution. Indeed, in most cases MergeBERT requires only 1 inference call to resolve merge conflict, with up to 3 calls in the worst case, based our dataset. The cost of single inference call on a 16GB Tesla V100 GPU is ms. The end-to-end time to resolve a merge conflict (including tokenization, alignment, and edit sequence extraction) is 105 ms on average, and up to 500 ms in the worst case.
With GPT-C language model, the resolution region is decoded token-by-token via the beam search algorithm. The average time to decode a single token (in our experiments we use beam width of 5, 16GB
and 1024 tokens context length, with past hidden state caching optimization enabled) Tesla V100 GPU is about 15 ms. With token-level differencing, the resolution size is 70 tokens on average (up to 1584 tokens maximum, in our dataset), which yields 1.1 seconds on average and up to 23.8 seconds in the worst case (the largest conflict) to generate resolution token sequence. Overall, end-to-end inference time required to resolve a merge conflict (including parsing and tokenization) is 2.3 seconds on average and up to 48.5 seconds for the largest conflict. From the user experience prospective in IDE, inference times of over 10 seconds are prohibitively slow.
11.111 FLOATING POINT OPERATIONS PER SECOND
following, we identify main operations in the transformer encoder, for the multi-input Merge- BERT architecture (see Fig. 2 for reference):
Self-attention: 600 MFLOPs 4 inputs (encoder weights are shared for all inputs),
Feed-forward layer: 1200 MFLOPs x inputs.
Contribution of the lightweight pooling (aggregation) and classification layers are negligibly small. With total of 6 transformer encoder layers this yields: 43200 MFLOPs per forward pass.
For the GPT-C transformer decoder-only model get:
Self-attention: 600 MFLOPs
feewaf layer: 1200 MFLOPs
with a total of 12 encoder layers this yields: 21600 MFLOPs per inference call, and for 6 encoder layers: 10800 MFLOPs.

---

Under review conference paper ICLR 2022
With larger FLOPs per a single forward pass as compared to generative approach, with MergeBERT we gain significant reduction in total FLOPS required to decode resolution region as a result needing to performing orders of magnitude less calls (I-3 calls with MergeBIRT as compared to 10-1584 with language model), making this approach an appealing candidate for deployment IDE.
11.2 IMPACT OF PRETRAINING DETAILS
The effect of sule-vupe pretraining is two-fold: (1) it speeds up the time to solution as result of faster model convergence we observe 20% higher F-score after 5 training epochs and 32 times larger finetuning training throughput, and (2) yields 14% overall higher F-score as compared a model trained from scratch.
While experiments with various pretraining objectives (Guo al. 2021 Roztère et al. 2021) is outside of the scope of this work, as baseline, we utilized the CodeBERI public checkpoint for a downstream task of merge conflict resolution which utilizes a similar pretraining objective as ours. The resulting model showed comparable F-score, and likely explanation for the difference is that the CodeBERT is pretrained the NerehearchNet dataset, which does not include C# and TypeScript programming languages used in this study.
70.0
67.5
65.0
62.5
57.5
Train (randorn init.)
55.0
Finetune (CodeBERT ckpt.)
Finetune (DeeaDev ckot)
52.5
0
50
100
150
200
250
300
Figure 5: MergeBERT model trained from scratch as compared to finetuning training for sequence classification downstream task with the encoder weights transferred and frozen during finetuning. The F-scores of merge resolution synthesis are quoted for TypeScript test set as function of epoch. bubbiccl available checkpoint is quoted for reference. Finetuning performance with CodeBERT-base bublicly
11.3 CONTEXT ENCODING DETAILS
Fig. 6 Fillustrate how input representations are extracted.
We conduct ablation study the edit type embedding to understand the impact of edit-awareness of encoding on the model performance. As shown in Tab. 5 edit type embedding information could improve MergeBERT F-score by 7%.
Table 5: Evaluation results MergeBERT and the model variant without edit-type embedding for merge conflicts in TypeScript programming language test set. The table shows top-1 precision, recall, and F-score metrics.
Approach
Precision
Recall
F-score
w/o type embedding
65.2
63.1
64.1
BET
69.1
68.2
68.7

---

Under review conference paper ICLR 2022
20
Toarr
S.m.
Token
5,
%
Sce
Se
4
ton
%
%
Fostion
%
%
5
Figure 6: MergeBERT imput representation. The input embeddings sum of the token embeddings, the type embeddings and the position embeddings. Type embeddings are extracted from the edit sequence step that represent how to turn the alo sequence into the 0/a
11.4 IMPLEMENTATION DETAILS
We pretrain BERT model with 6 encoder layers, 12 attention heads, and a hidden state size of 768. The vocabulary is constructed using byte-pair encoding method (Sennrich al. 2016) and the vocabulary size is 50000. We set the maximum sequence length to 512. Input sequences cover conflicting regions and surrounding code (i.c., fragments of Pref and Suf f) up to maximum length of 512 BPE tokens. The backbone of our implementation HuggingFace's Robert aModel and Roberta FotttForrSee SeSpeeence i ficatic on classes in Py PyTorch, which are modified to turn the model into multi-input architecture shown in Fig. 2
We train the model with Adam stochastic optimizer with weight decay fix using learning rate of 5e-5, 512 batch size and 8 backward passes per a allreduce on 64M files in C, C++, C#, Python, Java, JavaScript. TypeScript, PHP, Go and Ruby programming languages. The training was performed on 64 NVIDIA Tesla V100 with 32GB memory for 21 days; we utilized mixed precision. Finetuning was performed 4 NVIDIA Tesla V100 GPUs with 16GB memory for 6 hours.
the inference phase, the model prediction for each line-level conflict consists of one or more token- level predictions. Given the token-level predictions and the contents of the merged file, MergeBERT generates the code corresponding to the resolution region. The contents of the merged file include the conflict question and surrounding regions. Afterward, MergeBERT checks the syntax of the generated code with tree-sitte parser and outputs it as the candidate merge conflict resolution only case of correctness.
The model prediction for each line-level conflict consists of either label for token-level conflict a combination of labels for multiple token-level conflicts representing the best prediction for each token-level conflict within the line-level conflict. Given these labels for each line-level conflict and the contents of the merged file, MergeBERT generates the code corresponding region. The contents the merged file includes the conflict question and its surrounding regions. Therefore, MergeBERT. for each conflicting line, chooses between the versions of code based on the labels the model produced and generates the resolution code concatenating them. Afterwards, MergeBERT checks the syntax of the generated resolved code, and in case of correctness, outputs it as the candidate merge conflict resolution.
the resolution
In case of multiple line-level conflicts in the merged file, MergeBERT refines the contents of the merged file that serves as the surrounding region of the conflict. More specifically, MergeBERT replaces the other conflicts in the the merged file contents with the code it previously generated as their predicted resolutions. For this purpose, as shown in Fig. 7 MergeBERT updates the contents of the merged file after resolving each line-level conflict with the code it generates as the conflict resolution based on the model prediction.
11.5 MULTIPLE CONFLICTING REGIONS
MergeBERT can deal with non-trivial real-world merges, composed of multiple conflicting chunks. To provide an example of such merge conflict, we include Fig. 8 MergeBERT correctly predicts
hhups://rcc-sitter wtw.origghhuuuihieeeiiiiiii

---

Under review conference paper ICLR 2022
Prefix for conffict
some
1/ (CONZLICT 1] start sccese< Curzent Change (A)
conflict version
code
Base
version
Inconing Change (B)
// [CONELICT 1]
some
code:
[CONTLICT Change
code of conflict version 1111|1 Base
code conflict version
code of confiiet version >クンラ>>> Inconing Change (B) // [COMFLICE 2] and
(a) Resolving conflict
Prefix for canffict2
code of predi cted resclution
code:
// [CONFLICI 2]
<cce<<< Curzent Change (A) code for conflict version
11111
conflict version
code for conflict version 3000000 Incoming Change // [CONFLICE
(b) Resolving conffict
Figure 7: An example of a file with multiple conflicting regions.
a concatenation of changes proposed by developers A and B for the first token-level chunk and a concatenation of changes proposed by developers B and (in the reverse order) for the second chunk.

---

Under review conference paper ICLR 2022
VaE dorn $ (thie);
(setiingg funation()
var data fozm, (or
<<<<<<< (E(etttings.
9-param([ :sattings.
|||III Base.ja parans... fields settings.
paparan (ffields settinga.......... fielda))
3303530 B.ja
settings submitilandler)
ratuen settings rubmitittadllen aeply
Re beturn
(a) Line-level conflict
forn (this);
settings (ww.biiidaeettiigg..eeooo evant. function
var status = false:
serialize
(oettings. (iella)
data +
<<<<<<<
data
Base. parans
data +
B.ja
<<<ее<< A.ja
paran fields';
Base Fields
Param(
3033333 B. rields));
iE (atatus 46 settings aubni tBandeer)) [
settings. submi titandler. apply (thim)
return atatus;
(b) Token-level conflicts
(this))
settings.con bon. event, function() vaz status false:
iE(smttinga data *- 5.paran 'fielde' wettinge.tieedde
settings.
return settinge. subni tiannder.. (thi))
Re tutu
(c) Resolved merge
Figure 8: Example real-world merge conflict resolved by MergeBERT. (Top) merge conflict repre- sented through the standard é f3,, (middle) corresponding token-level conflicts, and (bottom) the user resolution.


Reviews:
[{"review_id": "x9pVWP9QzdH", "reviewer": "Reviewer_k5J6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n+ Hierarchical two-level differencing appears to be an intuitive and good idea.\n+ Casting the problem as classification over a set of merge patterns appears advantageous in both learning and computation, since most of the time the resolution comes from either of the two change versions.\n+ Pre-training can be applied directly.\n\nCons:\n\n- This idea is somewhat incremental, largely based on the work of Dinella et al., 2020.\n- MergeBERT is not as good as *diff3* in terms of precision, which is to me a more important measure. \n- Some parts of the techniques and experiments are not clear, for example the class label and data split. I have more detailed questions below.\n\n\nQuestions:\n\n1. It is somewhat unintuitive that `let` is not part of the token-level conflict. I understand that `var` is not changed in the version B, but it is important from both A and B perspectives that there is a change that needs an agreement in resolution. In that case, I don’t think merging `let` right away is an indisputable decision.\n\n2. For this change from `--num_cores=2` to `--max_length=256 --num_cores=2`, what is the result of the two-level diff?\n\n3. Is treating conflicting regions independently in Eq. (2) is oversimplified?\n\n4. How do you split the train and test dataset (Table 4)? Is there a validation dataset?\n\n5. How do you deal with conflicts from more than 2 versions?\n\n", "summary_of_the_paper": "This paper presents MergeBERT, a deep model for resolving program merge conflicts in software development. The authors introduce a new, hierarchical differencing and cast the problem as classifying over a fixed set of merge patterns, instead of generating . The model is pre-trained on a large corpus of GitHub code.", "summary_of_the_review": "Overall, the paper presents several new technical contributions and insights, but some parts are not entirely convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HAKP6cbvvk", "reviewer": "Reviewer_vcTN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an important problem, and I'm excited to see more work in finding a neural solution to it.\n\nHowever, this submission seems more like a refinement of DeepMerge than a novel contribution on its own. The data representation for conflicts is a generalization from DeepMerge, and the model architecture is a straighforward form of a Transformer-based classifier. However, the limited novelty might be offset by the positive progress on this important problem, modulo a number of questions below.\n\nI wonder if there's room to incorporate the strategies of syntactic or lexical merging employed by FSTMerge and its variants and other non-neural baselines into the actions predicted by something like MergeBERT. It seems excessive to throw out the engineering that went into such non-neural tools, if they can be used for something more sophisticated than o, a, b, oa, ob, etc. Q1: I'd be curious if you think the strategies in those earlier tools are incompatible with an encoder like your Transformer-based encoder, too coarse grained, or perhaps just too complicated.\n\nThat said, I like the data-driven design of the task (e.g., the merge resolution \"recipes\" described in section 4). I would have liked to see where the 9 edit patterns came from though (presumably some analysis of real conflict resolutions?), since otherwise they appear arbitrary. Q2: are your classification labels arbitrary? Did you choose them by analyzing actual merge-conflict resolutions?\n\n## Non-conflicting token edits\n\nMy biggest concern with your work is that you seem to treat token conflicts as independent of each other, but of course they are most certainly not, in general. For example, on page 3, with respect to Figure 1, I'd be careful about calling a token with no direct conflict a \"non-conflicting edit\" (e.g., the statement on `var` versus `let`). Consider the following diff:\n```\n<<<<<<<< A\na = func2(y, 10)\n|||||||| O\na = func2(y, 9)\n========\na = func3(y, 10, 12)\n>>>>>>>> B\n```\nwhere `func2` is a function with arity 2, and `func3` is a function with arity 3. Here, although the `func2` to `func3` change on `B` is \"non-conflicting\", it is not independent of the change from `9)` to `10)` or `10, 12)`, since one keeps the arity at 2 and the other changes it to 3. Perhaps a model can learn these interdependencies but your model does not. I'd caution you against calling independent token changes \"non-conflicting\". Maybe there's a better motivating example than this one, or again, perhaps there's some analysis of real conflict resolutions showing that real conflicts are indeed token-independent.\n\n## Evaluation\n\nI don't quite understand your definition of precision and recall. Is precision perfect accuracy modulo whitespace per conflict region? What's recall? Why is it not 100%? Do you have a threshold on classification probability you're using that's causing you to lose some examples? It seems you have one interpretation of recall for diff3 (it cannot resolve the conflict) and possibly another for MergeBERT? Q3: Please explain your metrics with specificity.\n\nIt's not obvious how BLEU-4 is a relevant metric. In cases where token-level conflict resolution kicks in, A or B or even O probably share many n-grams with the resolution. What kind of solution does BLEU-4 allow you to score positively that would be genuinely acceptable for this task? An example would be helpful here. Q4: Please explain why BLEU-4 is a good metric for this task, perhaps with an example.\n\nThe zero-shot generalization to Scala is puzzling. Presumably the value proposition here is to argue that you don't have to pre-train for every language, and a single strong (potentially multilingual) model can do the job. But then I would want to see the comparison of pre-training/fine-tuning on Scala versus the zero-shot version with neither pre-training nor fine-tuning. In the absence of that, it's not clear what the headroom is for this language. Is the result good? Is it bad? Maybe pre-training and fine-tuning on Scala gives super high F1. Q5: How does MergeBERT do if you pre-train on Scala and fine-tune on Scala, and how does that compare to your zero-shot results?\n\nI don't understand the point of Section 8.2. You already do MLM pre-training on your unilingual and multilingual pre-training datasets. What does this section add to what you already do? Q6: Please explain what research question Section 8.2 is answering, and what the answer is.\n\n", "summary_of_the_paper": "This paper addresses merge-conflict resolution in source code repositories. Whereas prior neural work (DeepMerge) can only do line-level resolutions (i.e., predict a resolution that chooses some sequence of entire lines from the original file version or the two divergent branches), this work refines the task further towards token level resolutions, thereby covering more interesting cases. Whereas DeepMerge cast the task as a pointer-sequence prediction (predicted a sequence of lines from the input), MergeBERT casts the task as a classification problem: for each conflict instance (some token-sequence conflict), one of 9 recipes are chosen to merge (e.g., just the original tokens, just one of the branches, some concatenation of the three, and some substitution of tokens in the original by concatenations). Similarly to DeepMerge, the input is encoded as a combination of aligned token sequences of the original snapshots and the divergent branches, as well as an encoding of the token-wise edit \"script\" for the pairwise diffs (same, inserted, deleted, replaced). But instead of encoding this edit sequence explicitly, MergeBERT uses it as a token type embedding in a Transformer encoder, along with a positional embedding and the token embedding itself.\n\nThe Transformer encoder is pre-trained with the masked language model objective, before fine-tuning on merge-conflict resolutions. The resulting tool is shown to resolve more merge conflicts than prior work, and also to generalize to a language unseen during pre-training or fine-tuning.", "summary_of_the_review": "Important problem, but there are many unanswered questions making the submission feel incomplete.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BP_cbM4Fzt6", "reviewer": "Reviewer_TUUK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n+ This is a compelling task, merge conflicts are an important problem\n+ Reducing the problem to using a classifier is valuable practically \n+ The nine primitive merge resolution patterns covering 99% of merge cases is an interesting observation\n\nCons:\n+ The encoding is token-based and rather standard\n+ Missing ablation study\n+ Experimental evaluation partial with respect to most important baseline \n\n* Tackling the merge conflicts problem is interesting. Using a learned model to decide how to resolve it is interesting as well (but not novel), since, it’s not always clear what is the best resolution (which is consistent with the context).\n\n* It’s not clear how the model looks like, Do you train BERT only for word vectors? If so, what about exploiting the context? Is the encoder of the aligned sequences the pre-trained BERT? It looks like you are not finetuning it (based on the blue squares of Figure 2, showing that only the Edit Type Embeddings are finetuned), so how should it handle the new kind of inputs? (token embedding + type embedding + position embeddings)\n\n* How important is the edit type embedding used in finetuning? The paper refers to Figure 5 in the appendix that shows how these are used, but not how important are they for the final result. In general, the paper would benefit from a more extensive ablation study. \n\n* The comparison with DeepMerge includes cases where DeepMerge cannot produce a prediction, as these cases are not line-level merges. This is not an apples-to-apples comparison. What would happen if we compare DeepMerge/MergeBert considering only line-level merges?\n\n* Comparisons to JDime and jsFSTMerge are useful for showing the superiority of your neural approach, but I am more interested in understanding what makes your approach work well.\n\n* Table 3 is pretty much due to properties of BERT and not of MergeBERT, right? Similar experience reported in CodeBERT?\n\n* Primitive Merge Resolution Types: Appendix 10.1 seems to emphasize this, but I do have some comments:\n\"Our analysis shows that over 99% of all the merge conflicts can be represented using these labels\"\nBut FIgure 3 (left) says that you failed to label 21.64% of the TypeScript examples. Can you please elaborate on this point?\nIt’s not clear how the colors in Figure 3 are related to your 9 classes. Does “Remove base” correspond to classes 6-9?, is so, what does pink (“Other”) refer to?\nPlease align the legends on both sides of Figure 3.\nI would emphasize that there are almost 21.64% non-trivial examples (in TypeScript), which the token-level diff method can solve by using a classification approach.\n\n* It would be helpful to add an encoder-decoder baseline - given (A, B, O), generate the resolution.\n\n* Table 1- what is the meaning of the diff3 row? I guess it’s for the examples where the token granularity diff managed to solve conflicts the line-diff couldn’t. Please clarify that. \n\n* Table 1 - what about using BERTMerge with line diff and DeepMerge with token diff? It’s essential for a fair comparison.\n\n* Section 8.2: The impact of pretraining is not disputed, but again it is not a contribution of the technique presented here. \n\nMinor: \n\n* Figure 2: should all edit operations in the blue squares be <->? \n\n* Figure 7(b) needs to be corrected: `data +=` is also a conflict, and there is a piece of code after the last conflict - ``});`.\n", "summary_of_the_paper": "This paper is about using BERT for the automatic resolution of merge conflicts. The main idea is to cast the problem of automatic merge resolution as a classification problem with 9 classes (token-level merge patterns). The technique use token-level differencing to represent the input to the merge problem as four aligned token sequences, together with two edit-type embeddings. The input sequences are fed to BERT and the results are aggregated and used for classification. \nThe technique is compared to state-of-the-art automatic-merge tools and is shown to outperform them in all benchmarks. \n", "summary_of_the_review": "The problem of automatic merge resolution is compelling. The authors present a solution that is based on token-level diff (no ML contribution), identify 9 merge patterns (no ML contribution), and finally use BERT with minor adaptations to classify which merge pattern should be used. For this model, some details of what exactly is being fine-tuned are not clear. \n\nThe suggested approach shows improvement compared to existing baselines. \n\nThe experimental evaluation is hard to follow because neither of the existing baselines addresses the exact same kind of merges. The closest baseline in terms of technique is DeepMerge, and the comparison to that baseline is quite partial. \n\nOverall, this may be a great software-engineering contribution, but I'm afraid that there's not a lot here for ICLR.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a fair effort, making some headway on a problem of practical importance. 
There was some discussion of scoping and whether the contribution was Machine-Learning-y enough. 
I'm kind of ambivalent on that particular question: I think the general rule is that the further out-of-scope the paper seems, the better the results need to be for people to overlook it. 
I think in this case, unfortunately, even the two most positive reviewers did not evince enough excitement about this paper for it to get accepted in light of the scoping concerns. 
Given the various constraints involved, I don't think I can recommend acceptance.

In order to get it accepted into a future conference I would recommend either:
a) Submit to a more Software-Engineering focused venue
b) Really shore up the evaluation such that the reviewers sympathetic to this kind of paper will find it unimpeachable and score it more generously.
Decision: Reject