A Universal Textual Merge Strategy Based on Tokens for Version Control Systems Qiqi Jason Gu
Mikoláš Janota
[email protected] CIIRC, Czech Technical University in Prague Prague, Czech Republic
[email protected] CIIRC, Czech Technical University in Prague Prague, Czech Republic
arXiv:2604.13813v1 [cs.SE] 15 Apr 2026
Abstract Merging is a core operation in version control systems such as Git, but traditional line-based algorithms often yield spurious conflicts, particularly in the presence of refactorings or parallel edits. While syntax- and semantics-aware merging approaches can reduce conflicts, they introduce drawbacks such as loss of formatting, dependence on language-specific parsers, and limited flexibility across heterogeneous artifacts. To address this gap, we present Summer, a novel textual token-based merge algorithm independent of document formats. Dividing text into tokens, our approach formulates token-level changes in one branch into string-rewriting rules and move rules, and applies these rules to the text of the other branch to construct a merge. Despite being independent on programming languages, our move rules model extracting and inlining functions. We evaluated Summer on ConflictBench, a large benchmark of realworld merge scenarios, comparing it with five pioneering merge tools across Java and non-Java files. Experimental results show that Summer achieved the highest 36% accuracy in reproducing merges verbatim identical to developers’, and ranked second in semantic accuracy.
CCS Concepts • Software and its engineering → Software configuration management and version control systems.
Keywords software merging, textual merging, Git, differencing algorithms, string rewriting systems ACM Reference Format: Qiqi Jason Gu and Mikoláš Janota. 2026. A Universal Textual Merge Strategy Based on Tokens for Version Control Systems. In Proceedings of The 30th International Conference on Evaluation and Assessment in Software Engineering (EASE 2026). ACM, New York, NY, USA, 11 pages. https://doi.org/10.1145/ nnnnnnn.nnnnnnn
1
Introduction
Version control systems, such as Git and Perforce, are commonplace in modern software development [27], video game development, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. EASE 2026, Glasgow, Scotland, United Kingdom © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn
and book writing [25]. They allow practitioners to work in parallel on separate branches and later integrate their work by performing a merge. A successful merge is saved by a merge commit with two parent revisions. Merging is a critical yet nontrivial operation in version control systems. Apart from custom merge drivers, Git provides six builtin merge strategies, which all operate purely at the textual level. Because changes are compared line by line, if two parallel modifications are made in the same line, this line fails to merge and a conflict is reported [19]. Beyond line-level edits, common programming practices such as code refactorings or method reordering further impede git diff’s ability in aligning lines, and then given a misaligned diff, git merge produces conflicts when the intended changes are logically compatible [27]. In spite of great advances in deep learning, neural networks or large language models are not a panacea in merging revisions of repositories. On the one hand, running neural networks locally requires high-end GPUs, which not every developer has. On the other hand, sending data over to the cloud raises security and privacy concerns. Partly due to these reasons, current research mainly applies neural networks on small, local conflict zones [8, 30, 32] rather than merging two whole branches where hundreds of files can be changed, along with file renaming and copying and modification to metadata. While there is abundant literature on parsing and merging Java source code [1, 10, 12], support for non-Java languages remains limited due to inherent parsing difficulties. For example, TEX is context-sensitive, and determining its parse tree requires executing the code. C++ is also context-sensitive. For instance, if int f(M); is preceded by #define M int, then f is a function that takes an int and returns an int. If it is preceded by #define M 0, then f is an int variable initialized with 0. Parsing dynamic languages, such as JavaScript, is also a challenge [8]. Next, even if a parse tree can be determined, it is common for a tool not to see the trees for the forest. A smart, semantics-aware diff tool in C++ is sensitive to semantic differences but disregards syntactical disparities. Given value\t= 5[myArray] and value\t= *(myArray + 5) which are functionally equivalent because both express array indexing, the tool reports no difference since syntactical information is discarded. Similarly, a syntax-aware diff tool may ignore lexical disparities in comments, white spaces, parentheses for grouping, and other so-called “trivia”. However, trivia is important for professional software engineers who want to review formatting changes and rewording in comments [21]. Finally, an AST-based merge result hardly fully reflects the original manner of coding. Because of the lost details during comparison, it cannot respect the original style when writing back a merged
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Qiqi Jason Gu and Mikoláš Janota
Start merge
syntax tree. For the previous example, the semantic tree may be written out as value = myArray[5], which matches neither of the two versions and misses the tab character (\t) on the left of the equal sign. At the same time, an AST tool still resorts to a textual merge tool for low-level data, including the content of string literal nodes, and files that the tool does not understand, including README files, configuration scripts, and various auxiliary artifacts, which are present in nearly all repositories [24]. Hence, we propose a universal textual merge algorithm, which can be used directly as a standalone merge driver by software engineers, but also as a component called by an AST-based tool. We name the algorithm and the implemented tool as Summer, short for Substitution Manager and Merge Error Resolver. Summer offers three user-level actions, decompose, rebase, and merge. It can be installed as a plugin of Git, so that git rebase calls summer rebase and git merge calls summer merge. decompose It is the most fundamental action, which summarizes modification steps conducted in one or more commits. For example, if a class Foo is renamed to Bar, this change may affect many files. Nevertheless, a single step, Foo → Bar, is sufficient to reproduce the entire modification. rebase This action invokes the action decompose to get modification steps and then applies these steps onto another branch. merge Given two branches, the action merge first determines a merge direction (Section 3.2), whether from left to right, or from right to left, then invokes the action rebase. Figure 1 illustrates the workflow of merging the left branch onto the right branch. Suppose a file in a base revision has content i++ and Foo. The left branch modifies i++ to i--, denoted by ⇒. The right branch makes two changes, modifying i++ to i+=1 and Foo to Bar. The process Determine merge direction determines that the left branch contains only one change, making it simpler to decompose and apply. Thus we decompose the changes in the left branch into steps. The change i++ ⇒ i-- boils down to editing a single symbol, so the rule, denoted by →, is + → -. Finally, the rule applies to the right branch and we get i-=1 and Bar as the merge result. Each step Summer produces is either a mathematical stringrewriting rule (Section 3.4), which rewrites the current revision towards the target revision, or a move rule (Section 3.5), which says “if a string-rewriting rule matches, then execute another stringrewriting rule.” In Section 4, we employ a notable benchmark ConflictBench created by Shen et al. [28] for evaluating merge tools. Summer and 5 widely-used merge tools are compared on this benchmark. The results show that our algorithm achieved the highest overall accuracy (36%) in Java and non-Java files when we evaluated character-to-character matching against developers’ merge results. If we compared Summer’s literal match accuracy with languagedependent tools’ semantic match accuracy, the 36% merge accuracy of Summer is the second highest, with AutoMerge leading at 46.2%. Although individual developers emphasize semantic accuracy, our tool’s literal matching capability makes it ideal in an industrial setting. We conclude that Summer outperforms the majority of widelyused merge tools in terms of merge accuracy. Section 5 discusses
Left branch
Right branch
i++ ⇒ i--
i++ ⇒ i+=1 Foo ⇒ Bar
Determine merge direction Left branch is simpler
Get left steps Step 1: + → -
Apply left steps onto right Merge result i++ ⇒ i-=1 Foo ⇒ Bar
Figure 1: The flowchart of the merge action in Summer
threats to the validity of our findings. The last section concludes our paper.
2
Related Work
Merging utilizes a common ancestor as the base and applies changes from one branch onto another. In this section we study 4 aspects of a merge tool: its mathematical theories, scopes of merging, how to use text, and alignments of substrings or tree nodes. We briefly discuss merge conflict resolutions, which are to try another merge strategy in a smaller scope. The effectiveness of resolving a conflict locally may be limited due to an error in a broader scope, such as a wrong pair of file names being aligned.
2.1
Theories of Merging
Darcs [26] is a version control system which stores patches (functions that transform text). Darcs is built on top of patch theory. Patch theory argues that the merge operation is commutative, i.e., merges from A to B and from B to A should yield the same result, either a conflict or the same textual state [16]. The merge operation in Darcs has exponential running time [11] because Darcs allows interactions among patches. Mimram and Cinzia [20] modeled merges as pushouts in category theory. If the partial order of two added lines from two branches cannot be established, the two branches are in conflict. Git is built on top of directed acyclic graphs, and stores static text for each revision. The 3-way merge strategy in Git is commutative, but rebasing is not. Summer is designed for traditional version control systems such as Git and Subversion, but Summer presents Darcs’s patches as string-rewriting rules, so that it can merge text in a powerful way.
2.2
Scopes of Merging
Although most merging tasks ultimately boil down to operations on plain text, the scope of merging can vary considerably. It ranges from a short fragment of text, a file identified by its path, an entire
A Universal Textual Merge Strategy Based on Tokens
directory containing many files, to a full revision with metadata in a version control repository. As a wrapper around GNU diff, wdiff highlights differences word by word by splitting each word in an input file into its own line, then runs GNU diff. wiggle [6] is the word-wise version of GNU patch, capable of incorporating two pieces of text with regard to a base. These two tools work on the text level and do not compare or merge file names. Folder-level tools include AutoMerge [36], IntelliMerge [29], FSTMerge [4], and KDiff3. These tools compare two folders or merge three folders, treating one as the base. However, none of them performs file renaming detection. Stock merge tools in version control systems merge everything in a revision, including file renaming detection or tracking. Git additionally has a “rerere” functionality that reuses historical merge resolutions. Vale et al. advised merge tools to analyze an entire merge request rather than only the conflict parts in order to get more context [34, p4979-4980]. Inspired by Programming by Example, the algorithm by Pan et al. [24] learns merge patterns from the whole history of a repository and applies those patterns to a particular merge scenario. Resembling the stock merge tool in Git, Summer receives revision identifiers and merges everything in a revision. It treats all data, whether file content or file names, as strings by a mapping (Section 3.1).
2.3
Preprocessing of Text
When a merging task boils down to plain text, the way to preprocess the text is another problem. A piece of text can be broken into words, lines, or blocks. With domain knowledge, it can also be parsed into a tree. The most well-known GIT/GNU diff compares textual input line by line. This approach has an obvious disadvantage in that it cannot handle parallel modifications to the same line [19]. There is an early algorithm [33] that detects moved strings between the old and new text, but it does not permit minor modifications within a moved string, such as renaming a variable. wdiff and wiggle [6] compare and merge words. Parsing a piece of program code into a tree is extensively scoped. Seibt et al. [27] showed that compared to git merge, a syntactic merge strategy decreased the number of conflicts from 6.69% to 5.32%. CLDiff [15] parses Java code and builds an abstract syntax tree (AST). Nodes at or higher than the statement level are merged with a tree algorithm; other elements are passed to git diff and git merge. Comments are ignored. Employing a different cut-off, JDime [3] incorporates method bodies in a textual way and incorporates high-level nodes syntactically, but it has difficulty handling identifier renaming. Furthermore, sometimes JDime performed a clean merge but the artifact turned out not compilable [27]. Leßenich et al. [17] enhanced JDime’s handling of renaming and shifted code. FSTMerge was initially proposed in [4], then improved in [7]. It can merge Java, C#, and Python code and fall back to git merge for the remaining content. From a semantic viewpoint, code refactoring leads to 22% of merge conflicts [18]. RefMerge [10] and IntelliMerge [29] are
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
the state of the art for resolving conflicts of this particular kind. They detect refactorings in two branches, undo them, then call git merge to merge the two branches, and finally replay the refactorings on the merged codebase. Although AST-based tools are blind to trivia such as comments and parentheses, it is rare for merge tools to use concrete syntax trees (CST). We only found one preprint [9], which is not yet peer-reviewed, that uses a CST for merging. When designing a differencing algorithm for a language for cyber-physical systems, Sjölund [31] weighed up a CST but gave it up due to the increased complexity. Bates [5] built a text editor that parses the content into a CST and only sends the modified part of the CST for updating the user interface. Nevertheless, Bates’ algorithm is not for a version control system. Summer fills the gap by dividing text into tokens of letters, digits, white spaces, and symbols before merging.
2.4
Aligning Similarities
To find differences, one must match unchanged or similar parts so that other parts are labeled as added or deleted. For instance, git diff has options --find-renames, --find-copies, and --find-copiesharder to perform alignments on the file level. Myers’ differencing algorithm [22] aims for the shortest edit script. Much as the number of additions or deletions is minimized, the content of each addition or deletion can be long. Git implements multiple variations of Myers algorithm, and one of them is the histogram diff algorithm, which according to Nugroho et al. [23], provides fast speed and good code alignment. Summer first utilizes the histogram algorithm to obtain a line-wise diff, then tokenizes changed lines, and calls the Levenshtein distance to get a token-wise diff (Section 3.3). The problem of edit distance for unordered trees is NP-hard [35]. Consequently, researchers who study syntax tree-based merging have to make trade-offs or heuristics to achieve accuracy and runtime speed. If the bi-gram similarity [2] of two nodes is greater than 0.8, CLDiff [15] aligns the two subtrees. IntelliMerge [29] only aligns nodes of the same syntactic type. IntelliMerge calculates the string cosine similarity for identifier nodes and the Jaccard similarity for other nodes, with the matching threshold 0.618. Zhu et al. [36] built AutoMerge on top of JDime, and matched nodes based on an adjustable quality function. Dinella et al. invented DeepMerge [8] which uses a neural network to align JavaScript lines in order to resolve a conflict in a local scope. DeepMerge achieved 61% accuracy if a conflict zone had fewer than 7 lines, and otherwise its overall accuracy was 36.5%. Nevertheless, their neural network only repositions existing lines rather than generating new code.
3
The Workflow of Merge
The merge action of Summer executes in 6 stages, corresponding to 6 subsections here. An overview is available in Figure 1 in Introduction. Section 3.1 covers preparation. Section 3.2 is to determine a merge direction. The Get step process in Figure 1 maps to Section 3.3 to 3.5. Finally we talk about applying steps in Section 3.6. Summer accepts 3 revision identifiers (the SHA of a commit in Git) for the left branch, the right branch, and the base of the two
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Table 1: A dictionary presenting a Git commit, where a submodule path is changed, a file is renamed, and its content is changed
Qiqi Jason Gu and Mikoláš Janota
Table 2: Breaking up coarse-grained string edits from Table 1 into substitution edits, identity edits, and one insertion edit Buckets of string edits
Label
Bucket
github ⇒ gitlab
Submodule path
github.com/txaty/bigcomplex ⇒ gitlab.com/txaty/bigcomplex
.com/txaty/bigcomplex ⇒ .com/txaty/bigcomplex
File name
bc.go ⇒ Program.go
.go ⇒ .go
Content of bc.go
import bc "github.com/txaty/bigcomplex"
bc ⇒ Program import bc " ⇒ import bc "
github ⇒ gitlab
func main() { g1 := bc.NewGaussianInt(5, 6) // 5 + 6i g2 := bc.NewGaussianInt(1, 2) // 1 + 2i div := new(bc.GaussianInt).Div(g2, g1) fmt.Println(div) }
.com/txaty/bigcomplex"\n ⇒ .com/txaty/bigcomplex"\n
𝜀 ⇒ import "fmt"\n func main()// 1 + 2i\n\t ⇒ func main()// 1 + 2i\n\t
div ⇒ res := new...\n\tfmt.Println( ⇒ := new...\n\tfmt.Println(
⇒
div ⇒ res
import bc "gitlab . com/txaty /bigcomplex" import "fmt" func main() { g1 := bc.NewGaussianInt(5, 6) // 5 + 6i g2 := bc.NewGaussianInt(1, 2) // 1 + 2i res := new(bc.GaussianInt).Div(g2, g1) fmt.Println(res) }
branches. Since it is always possible to squash multiple commits into one, in this section we describe our algorithm in terms of 3 commits, abandoning the term “branch”. We use the term “commit” to emphasize the modification, and the term “revision” to emphasize the state after the modification. Our implementation supports unsquashed commits.
3.1
Mapping a Commit to String Edits
When asked to decompose one commit, Summer internally invokes its decomposition library. Although Summer handles file contents, file names, and metadata of a version control system, the decomposition library works purely on strings. Therefore, a mapping from a commit to strings is required. Suppose in a Git commit, a submodule path is changed from github.com/txaty/bigcomplex to gitlab.com/txaty/bigcomplex, a file is renamed from bc.go to Program.go, and the file content is modified from import bc "github.com...Println(div)\n} to import bc "gitlab.com...Println(res)\n}. Summer reads the commit and formulates a dictionary as Table 1 shows. The column Bucket contains the set of modifications in the string format; the column Label records the meaning of each bucket. Only the Bucket part is sent to the decomposition library to get fine-grained steps, and the library thus processes strings in an agnostic way, whether they are file names or file contents.
3.2
Determining Merge Direction
Given a base commit, a left commit, and a right commit, Summer has to determine whether to merge the left commit onto the right, or merge the right commit onto the left. For example, if one commit deletes a file, and another commit modifies the same file, Summer has to merge the former on top of the latter as a modification cannot be applied to a non-existent file. Similarly, if one commit deletes
)\n} ⇒ )\n}
file A and modifies file B, and another commit modifies file A and deletes file B, then neither direction will work and thus a conflict is raised. If there is no file deletion in both commits, Summer calculates the Levenshtein Distance from the left to the base, and from the right to the base. Afterward, Summer chooses to decompose the simple commit, and applies the steps onto a complicated commit.
3.3
Dissecting String Edits
The decomposition library receives a set of buckets and each bucket currently contains one single string edit. Although each string edit can be directly returned as a step for merging, it is too coarsegrained. For instance, import bc "github.com...Println(div)\n} ⇒ import bc "gitlab.com...Println(res)\n} captures the context of a whole file, which is even worse than a traditional line-wise diff. Therefore, we have to dissect the string edit in each bucket. For each string edit, we call Git’s histogram algorithm to get a diff. According to Nugroho et al. [23], the histogram algorithm is fast and provides good code alignment. Next, for each block of consecutive deleted lines followed by consecutive added lines, we tokenize the deleted and added lines. We define four categories of characters: digit, letter, white space, and symbol. Continuous characters of the same category form a token, except that each symbol forms its own token. For example, n=0xFF_0f is tokenized to {n, =, 0, xFF, _, 0, f}. Finally, the two sequences of tokens from a modified block are sent to the Levenshtein distance algorithm for alignment, so that we get a list of string edits about inserted, modified, deleted, and unchanged tokens for each bucket. Displaying the three buckets of string edits, Table 2 is the result of dissecting the column Bucket of Table 1. We retain identity string edits, i.e., the lhs and the rhs are identical, but we visually write them in a smaller font size. 𝜀 ⇒ import "fmt"\n is an insertion edit that changes the empty string to an import statement. Others are substitution edits.
A Universal Textual Merge Strategy Based on Tokens
Algorithm 1 find a list of precise rewriting rules from buckets of rewriting instances function getPreciseRewriting(buckets) 𝑃 ←∅ for all 𝑏 ∈ buckets do for 𝑖 = 0, . . . , |𝑏 | do expandEdit(𝑖, 𝑏, buckets, 𝑃) end for end for return SortAndFilter(𝑃) end function function expandEdit(i, b, buckets, P_ref) for 𝑗 = 0, . . . , w do for 𝑘 = 0, . . . , w do 𝑟 ← join𝑙 (b[i-j:i+k]) → join𝑟 (b[i-j:i+k]) tp, fp ← getClassificationMetrics(r, buckets) P_ref[r]=(tp, fp) end for end for end function
3.4
From String-Rewriting Instances to String-Rewriting Rules
The string edits that we have shown, such as bc.go ⇒ Program.go and )\n} ⇒ )\n}, are mathematically called string-rewriting instances. They describe what changed but not a general pattern that can be applied elsewhere. To merge branches, we need to transform these specific edits into reusable transformation rules, which we call string-rewriting rules. We use ⇒ to denote a string-rewriting instance and → to denote a string-rewriting rule. We call them rewriting instances and rewriting rules for short. The previous section has dissected and aligned string-rewriting instances, which creates a solid foundation to execute Algorithm 1, reversing each rewriting instance back to a sequence of rewriting rules. The function getPreciseRewriting in Algorithm 1 returns a set of rewriting rules from a set of bucketed string edits. For each edit in each bucket, we call the function expandEdit to reverse it to zero or more string-rewriting rules, and check true positives (tp) and false positives (fp) of these rules. In the function expandEdit, w is short for context window. The function join() takes each nonidentity rewriting instance as a whole or takes individual tokens from identity rewriting instances. join𝑙 () joins the left-hand sides of rewriting instances in the specified range to a single string, and join𝑟 () joins right-hand sides. Then, the → connective makes the two strings into one string-rewriting rule which is assigned to 𝑟 . Following Table 2, github ⇒ gitlab is passed into expandEdit(). When 𝑗 = 0 and 𝑘 = 0, a rewriting rule github → gitlab is formed with tp = 2 and fp = 0. bc ⇒ Program is also passed into expandEdit(). When 𝑗 = 0 and 𝑘 = 0, a rewriting rule bc → Program is formed. Unfortunately, this rule incorrectly rewrites import bc "github.com/txaty/bigcomplex" to import Program "github.com/txaty/bigcomplex", which boosts false positives. When 𝑘 = 1, join𝑙 () and join𝑟 () add additional context from what comes after. After bc ⇒ Program is .go ⇒ .go ,
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Listing 1: Left commit: two lines are extracted into a new function ... public void addListener(O obj) { notNull(obj); validate(obj); + runCheck(obj); Listeners.add(obj.getListener()); } + + public void runCheck(O obj) { + notNull(obj); + validate(obj); + } }
which is an identity rewriting instance. Therefore, join() takes one token at a time, which is the dot (.), and a new rewriting rule bc. → Program. is formed. This rule has tp = 1, fp = 0. Classification metrics cannot be computed for an insertion rule 𝜀 → import "fmt"\n. When 𝑗 = 1, 𝑘 = 0, the created substitution rule is \n → \nimport "fmt"\n with tp = 1, fp = 6. When 𝑗 = 0, 𝑘 = 1, the created substitution rule is func → import "fmt"\nfunc with tp = 1, fp = 0. The function SortAndFilter calculates the precision of each rule, namely tp/(tp + fp). Rules with precision no more than 0.5 are filtered out. The remaining non-overlapping rewriting rules are the ones that best reproduce the target modifications that Summer passed to the decomposition library. If getPreciseRewriting() returns rules with precision less than 1, these rules make mistakes amid rewriting. getPreciseRewriting() has to be called one more time to generate another set of rules to fix these mistakes. In the end, if we still cannot fully reproduce the target modifications, we increase the context window w. All in all, it is always possible to rewrite a string (or a set of strings) to a target string (or a target set) by a sequence of string-rewriting rules. In terms of the time complexity, let 𝑀 be the total number of string edits in buckets and 𝑁 be the total number of tokens in the 𝑁 lhs of buckets. The average length of an edit is 𝑀 . getClassificationMetrics() invokes a string-searching algorithm, resulting in 𝑁 𝑁 . We loop w 2 times in expandEdit() and the time complexity 𝑀 𝑀 times in getPreciseRewriting. Therefore, the time complexity of the function getPreciseRewriting in Algorithm 1 is 𝑂 (w 2 𝑁 2 ), irrelevant to the number of edits1 .
3.5
The Move Rules
Although it is guaranteed to find a list of substitution rewriting rules to completely represent a set of string edits, these rules do not capture the nuance of moving text. In contrast, moving text is quite common in software development, in the form of extracting a method and inlining a method. Consider an example presented in the RefMerge paper [10]: the left commit extracts two lines into a new function runCheck as Listing 1; the right commit changes the calling style notNull(obj) 1We assume comparing two tokens is an elementary operation, but in reality the
average number of characters in a token matters. Copying characters in join𝑙 () and join𝑟 () are ignored too.
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Step 1: add a new definition: runCheck(O obj){ notNull(obj); validate(obj); }
Step 2: validate(obj); \n\t\tListeners → runCheck(obj);\n\t\tListeners
Step 3: \t\t notNull(obj); \n\t\trunCheck → \t\trunCheck Figure 2: Decomposed steps without the move semantics from the left commit (Listing 1). Boxed parts do not apply on the right revision. Step 1′ : move whatever before Listeners 𝑎 = {\n\t\t
\n\t\tListeners →
{\n\t\trunCheck(obj);\n\t\tListeners
𝑐 = \n} → \n\n
\n}
′
Step 2 : add the function header \t}\n → \t}\n\n\tpublic void runCheck(O obj) {\n\t\t
Step 3′ : add the function footer \n} → \n\t}\n}
Figure 3: Decomposed steps with the move semantics from the left commit (Listing 1). They can apply on the right revision.
⇒ obj.notNull() and validate(obj) ⇒ obj.validate(). The algorithm presented in Section 3.4 finds three fine-grained steps from Listing 1, shown in Figure 2. None of the 3 steps in Figure 2 are correct with respect to the right revision. Step 1 can match in the right revision, but it writes out the old calling style. Step 2 and Step 3 do not even match because the calling style has been changed from validate(obj) to obj.validate() and notNull(obj) to obj.notNull(). One way to solve this problem is a string-rewriting algebra in Darcs Patch Theory which allows a string-rewriting rule to be rewritten by another rule. However, we take another approach in this paper. In this section, we present move rules, which also solve the problem of moving text. A move rule is in the form 𝑎 ⊢ 𝑐, read as “if 𝑎 matches, then execute 𝑐”. Both 𝑎 and 𝑐 are string-rewriting rules. Unlike rewriting rules discussed in the previous section, the lhs of 𝑎 includes a capture group that can capture text amid matching, and the rhs of 𝑐 has a backreference to this captured text. With the new move semantics, Summer finds one move step and two string-rewriting steps, shown in Figure 3. Step 1′ is a move rule. The execution result of Step 1′ is Listing 2. The lhs of 𝑎 in the left revision captures the function body notNull(obj);\n\t\t validate(obj); and its rhs is similar to the rhs of the original Step 2. The rhs of 𝑐 moves the captured function body to Line 6 and 7. When the move step executes in the left revision, it captures and moves notNull(obj);\n\t\tvalidate(obj);. When it executes
Qiqi Jason Gu and Mikoláš Janota
Listing 2: The content after the move rule Step 1′ in the right revision 1 2 3 4 5 6 7 8
public void addListener(O obj) { runCheck(obj); Listeners.add(obj.getListener()); } obj.notNull(); obj.validate(); }
Algorithm 2 Generate move rules from string edits organized in buckets function getPreciseMove(buckets) 𝑃 ←∅ for all 𝑏 ∈ buckets do for 𝑖 = 0, . . . , |𝑏 | do if b[i] is insertion then findExtract(𝑖, 𝑏, buckets, 𝑃) else if b[i] is deletion then findInline(𝑖, 𝑏, buckets, 𝑃) end if end for end for return SortAndFilter(𝑃) end function
in the right revision, it captures and moves obj.notNull();\n\t\t obj.validate();. In this way, move rules adapt the local style in the current revision. Accordingly, move rules should be created and executed before string-rewriting rules. So far, the call site (Line 2 in Listing 2) has been perfectly reconstructed, but the function body at Line 6 and 7 is bare. Step 2′ adds the function header public void runCheck(O obj), and Step 3′ adds the footer of a single indented curly bracket. Overall, these rules generated from the left commit correctly apply to the right revision. Despite being similar to an operation of one cut and one paste, a move operation can handle one-to-many and many-to-one edits. One-to-many means that one piece of text is deleted and its substring is added to many places. In other words, 𝑎 is matched once, and 𝑐 is matched and executed one or more times. One-tomany models inlining operations. On the other hand, many-to-one models extraction operations. Algorithm 2 illustrates the idea. getPreciseMove is akin to getPreciseRewriting. In the loop body, findExtract and findInline are terminology borrowed from code refactoring, although Summer itself has no concept of refactoring. Algorithm 3 outlines the findExtract function. To begin with, findLS() finds the longest common substring 𝑠 shared by b[i], which is an insertion edit, and the entire buckets. The subscription 𝑟 requests to match the rhs of insertion b[i] to the lhs of deletion or substitution edits in buckets. In this way, we find which sites the “function body”–a metaphor for the extracted text–is moved from. Then from Line 3 to 4, findExtract makes use of expandEdit defined in Algorithm 1 to find a substitution rule as the consequent for inserting the new “function definition”–the “function body” plus an optional prefix and postfix. From Line 7 to 10, we loop the sites
A Universal Textual Merge Strategy Based on Tokens
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Algorithm 3 Build a move rule for many-to-one extractions
Table 3: The types of 73 non-java files in the dataset
1: function findExtract(i, b, buckets, P_ref)
s, sites ← findLS𝑟 (b[i], buckets) 3: 𝑃𝑐 ← ∅ 4: expandEdit(i, b, buckets, 𝑃𝑐 ) 5: 𝑐, 𝑚𝑐 ← SortAndFilter(𝑃𝑐 )[0] 6: c.rhs ← c.rhs ◦(𝑠 → ) 7: 𝑃𝑎 ← ∅ 8: for all j ∈ sites do 9: expandEdit(j, b, buckets, 𝑃𝑎 ) 10: end for 11: 𝑎, 𝑚𝑎 ←SortAndFilter(𝑃𝑎 )[0] 12: a.lhs ← a.lhs ◦(𝑠 → ) 13: P_ref[𝑎 ⊢ 𝑐] ← 𝑚𝑎 + 𝑚𝑐 14: end function 2:
where the longest substring is found and create an antecedent rule for deleting the sites. Furthermore, in Line 6 and 12 the rewriting rule s → is applied onto the rhs of 𝑐 and the lhs of 𝑎 respectively, to install a capturing device and a backreference device. Finally, a move rule is created and its classification metrics (tp and fp) is the sum of its components (see Line 5, 11, and 13). Apparently, if 𝑠 is too trivial, 𝑃𝑐 or 𝑃𝑎 is empty, then findExtract terminates early. The function findInline is quite the opposite, which involves calling findLS𝑙 . 𝑁 In terms of complexity, findLS finishes in 𝑂 ( 𝑀 𝑀) = 𝑂 (𝑁 ). ex𝑤2 𝑁 2 pandEdit finishes in 𝑂 ( 𝑀 ) which we have shown in the previous subsection. Then, let 𝑑 be the number of insertion or deletion edits (𝑁 ≥ 𝑀 ≥ 𝑑 ≥ 0). The time complexity of findExtract 2
becomes 𝑂 𝑁 + (𝑀 − 𝑑) 𝑤 𝑀𝑁
2
. getPreciseMove loops findEx-
tract 𝑑 times. Therefore, the overall running time is 𝑂 (𝑑𝑤 2 𝑁 2 ).
3.6
Applying Rules
When string-rewriting rules and move rules are obtained, applying them to strings is a straightforward search-and-replace operation. Nevertheless, our rules were created from tokenized strings, and thus each match must start and end at token boundaries. Otherwise, for instance, the string-rewriting rule public → private that changes the visibility of a method will replace the class name Republican with Reprivatean. Summer does not expect a rule to be applied certain number of times because the situation of the left commit and the right commit can differ. For example, the left commit changes the indentation style from 4 spaces to 1 tab \s\s\s\s → \t, and the rule applies at 100 places in the left commit. When the rule is used in the right revision, as this revision has already been formatted to tabs, this rule applies few times. The disparity between application counts is not a red flag. Given a set of bucketed string edits, Summer first tries Section 3.1, 3.2, 3.3, 3.5, 3.6 for non-overlapping move rules. When the algorithm in Section 3.5 finds no move rule, Summer executes Section 3.1, 3.2, 3.3, 3.4, 3.6 for non-overlapping string-rewriting rules. Accordingly, Summer may run twice for a complicated commit.
4
File Type
Count
pom.xml txt, markdown, or adoc build.gradle properties files groovy or scala others
23 16 9 7 5 13
Evaluation by a Modified ConflictBench
A number of benchmark suites have been proposed for testing merge tools; however, many are no longer available, such as Seibt et al.’s dataset [27] and IntelliMerge’s dataset [29]. The data used to train DeepMerge [8] is limited, including only resolutions achieved by rearranging lines. Similarly, datasets that were published with refactoring-aware merge tools include only conflicts induced by code refactorings. In contrast, Ghiotto et al. [12] provided a general dataset of 25,328 merge failures. Shen et al. composed ConflictBench, which has 180 merge failures [28]. We eventually chose ConflictBench because it was new and easy to set up. The merge driver in Shen’s ConflictBench aims to create merge results by giving merely 3 files and their paths to a merge tool, corresponding to the base, the left, and the right branch. The merge driver does not evaluate merge results, which is done manually by checking semantic equivalence. The 3 files by design were not mergeable by git merge. This benchmark comes with the binaries of 4 merge tools, namely AutoMerge, FSTMerge, IntelliMerge, and JDime; and it installs KDiff3 during setup. We did not seek latest versions of these tools in order to produce fair and comparable results. KDiff3 is a GUI tool and all others are command line. We introduce a fully automatic method for assessing the literal similarity of merge results. Although solo developers focus more on semantic equivalence, IT companies have strict requirements on code styles and readability and they may favor literal equivalence. Moreover verbatim comparison is purely objective and automatic. Therefore, we modified ConflictBench to call git diff --ignore-blank-lines --ignore-all-space to automatically compare the file synthesized by a merge tool and the one by the developer. For Java files, we make a minimal normalization by sorting the import statements. Put simply, our modified ConflictBench automatically computes merge results’ literal similarity by giving merely 3 files to a merge tool. As of the dataset in ConflictBench, the repo mybatis-plus contains a strange folder named d:\codeGen which is not accepted by Windows. This folder is outside of the tree structure of the conflicting file, so we mirrored this repo and removed this folder without affecting the merge process. The repo FEBS-Shiro was no longer available and we could not find any forks. Hence, the total number of repos was reduced to 179. Although the main language of these repos is Java, 73 merge scenarios are about non-Java files, a breakdown of which is displayed in Table 3. Given that four merge tools rely on abstract syntax trees, we added another baseline tool wiggle 1.3, as a representative of purely
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
textual merge approaches. Since KDiff is a GUI tool, we coded an AutoHotKey script to click the merge button and close dialogs which interrupt the automatic process. AutoMerge extended JDime, so we skipped the latter in our experiments. Besides, we made additional improvements to Shen’s merge driver while preserving its behavior. The original merge driver prepares the testing input by copying a repo folder and deleting everything but the single conflicting file, which easily leads to file locking issues and breaks the integrity of a test run. Our new version utilizes the sparse checkout feature of Git so that only the required file is materialized, greatly boosting the robustness of our evaluation. The evaluation results are in Table 4. The first 3 tools, namely Summer, KDiff, and wiggle, are universal merge tools. FSTMerge is not universal, but it can merge Java, XML files, and a number of other formats. IntelliMerge and AutoMerge were designed to merge Java files, so we left their values empty in the non-Java cases. The literal matches were automatically reported by git diff. The values in the row semantic matches were copied from Shen’s report. We define merge accuracy as literal match accuracy for a textual merge tool, and as semantic match accuracy for an AST tool. To summarize, in the Java category, the 34 matches made by Summer are the highest in the literal matching track. If we compare merge accuracy, Summer ranks second losing to AutoMerge. In the non-Java category, Summer achieved the highest accuracy across all metrics. For corporations that have strict rules regarding code styles and readability, we recommend Summer because it observes the original, local styling and syntax, it does not delete comments and copyright headers, and its merge output is ready to commit. In the subsequent subsections, we first analyze a few most difficult cases for all merge tools. Then we use Table 5 to guide our analysis. This table is venn diagrams showing intersections of Summer’s solutions and each other tool’s solutions, and solutions unique to Summer and to the other. When the size of a set is less than 3, we show the repo names instead of a number. As a result, we analyze the repos server, thumbnailator, and jmonkeyengin, which have stars in Table 5. Finally, we discuss the disparity between AutoMerge’s literal matches and semantic matches by checking additional repos.
4.1
Java Scenarios
The repo junit4 is one of the 59 most difficult cases, which no tool can merge correctly. In junit4, the left branch increased a version number; the right branch removed the snapshot tag from the version number; and the merge commit added back the snapshot tag. This case is particularly challenging in that the correct resolution requires a solid understanding of the meaning of the snapshot tag. Another most difficult case is halo, where the left branch added a comment warning about a null pointer exception, and the right branch fixed the null pointer exception. The developer only adopted the right branch. A large language model should be able to merge the local region correctly. The repo thumbnailator is one of the two cases that IntelliMerge could handle but Summer could not, as shown in Table 5. In thumbnailator, its left branch adds a @since tag followed by a space, and its right branch adds a @since tag followed by a tab. As
Qiqi Jason Gu and Mikoláš Janota
Listing 3: For thumbnailator, Summer (on the left) added an extra since tag comparing to developer. FSTMerge and AutoMerge (on the right) wrote in a style differing to developer * * @author coobird * @since 0.3.4 - * @since 0.3.4 * */ public interface Size
* @since 0.3.4 * */ -public interface Size { +public interface Size +{ /** * Calculates the size
Listing 4: IntelliMerge produced duplicated throws expressions for server boolean received; Server server; +
+
protected void startServer() throws IOException throws IOException { protected void startServer() throws IOException { server = new Server(); server.startServer(); } @Before public void setUp() throws IOException throws IOException { public void setUp() throws IOException { startServer(); }
Listing 5: AutoMerge failed to rename a variable in the merge result for SimianArmy + +
@Override public void doMonkeyBusiness() { /** {@inheritDoc} */ @Override public void doMonkeyBusiness() { allChaosTypes = Lists.newArrayList(); allChaosTypes.add(new ShutdownInstanceChaosType(cfg)); enabledChaosTypes.add(new DetachVolumesChaosType(cfg)); + allChaosTypes.add(new DetachVolumesChaosType(cfg)); }
Summer does not know semantics of the space and the tab character, it adds both to the merge result, shown in Listing 3. On the contrary, the developer picked merely the tab version. FSTMerge and AutoMerge resolved the conflicts logically correctly, but did not respect the original coding style, shown in the same listing. IntelliMerge successfully merged this case. KDiff and wiggle both gave up. Although IntelliMerge claims to be an AST tool, it does not always produce syntactically correct output. A case in point is the repo server. Listing 4 shows the merge result by IntelliMerge for this repo, where the duplicated throws expressions are not legal. Only Summer and FSTMerge passed this case. The repo SimianArmy is one of the 11 cases in Table 5 which Summer can literally match and AutoMerge cannot semantically match. In SimianArmy, the left branch adds a new line enabledChaosTypes.add(new DetachVolumesChaosType(cfg)); and the right branch renames all enabledChaosTypes to allChaosTypes. Listing 5 shows that in addition to formatting and comment issues, AutoMerge added the new line to the merge result, but failed to
A Universal Textual Merge Strategy Based on Tokens
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Table 4: Evaluation results divided by the Java category and the non-Java category. Each category shows the number of solutions literally (lit.) and semantically (sem.) matching developers’, and their accuracy. Summer
KDiff3
wiggle
FSTMerge
IntelliMerge
AutoMerge
5 29 4.7% 27% 27%
0 49 0 46% 46%
106 Java cases
Lit. matches Sem. matches Lit. Accuracy Sem. Accuracy Merge Accuracy
34 32% 32%
12 15 11% 14% 11%
4 3.8% 3.8%
5 24 4.7% 23% 23%
73 non-Java cases
Lit. matches Sem. matches Lit. Accuracy Sem. Accuracy Merge Accuracy
30 41% 41%
11 14 15% 19% 15%
1 1.4% 1.4%
4 9 5.5% 12% 12%
Total
Merge Accuracy
36%
13%
2.8%
18%
Table 5: Summer’s unique solutions to each other tool, and other tools’ unique solutions to Summer. We analyze the repos of which names have stars. (a) the Java category
Summer-only 25 34 33
Both 9 0 server*
31
3
11
23
Other-only 3 4 4 thumbnailator* JCTools
KDiff3 Wiggle FSTMerge IntelliMerge AutoMerge’s semantic matches
26
Listing 6: AutoMerge printed a full syntax tree without omitting optional elements for RxJava +/** + * Copyright 2014 Netflix, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in + ... + */ package rx; ... - @SuppressWarnings(value = { "unchecked" }) public final static <T extends java.lang.Object> Observable<T> concat(...) { + @SuppressWarnings("unchecked") + public final static <T> Observable<T> concat(...) { return create(OperationConcat.concat(t1, t2, t3)); } ...
(b) the non-Java category
Summer-only 23 29 27
Both 7 aeron 3
Other-only 4 0 jmonkeyengin*
KDiff3 Wiggle FSTMerge
rename it to allChaosTypes. Summer passed this case. All other tools failed. AutoMerge’s solutions deviate from developers’ not only in comments and line breaks, but also in optional elements in the Java language. Shen classified AutoMerge’s solution in Listing 6 as semantically equivalent, but the difference is huge in a literal sense. For starters, AutoMerge did not preserve the copyright header and javadoc because they are comments. In an enterprise context, this merge result may violate licensing requirements. Secondly, AutoMerge printed optional nodes in the syntax tree, such as value = { "unchecked" } versus simply "unchecked", and T extends java.lang.Object versus simply T. Only KDiff and Summer passed this test.
- private static class ThrowObservable<T extends java.lang.Object> extends Observable<T> { + /** + * An Observable that invokes {@link Observer#onError onError} ... + * @param <T> the type of item ... + */ + private static class ThrowObservable<T> extends Observable<T> { public ThrowObservable(final Throwable exception) {
4.2
Non-Java Scenarios
There are 38 most difficult cases in the non-Java scenarios where no tool can merge correctly. One of them is repo redisson. The correct value in an XML node is 3.4.2-SNAPSHOT. The value Summer gave is 3.4.3-SNAPSHOT, while wiggle gave 2.9.3-SNAPSHOT. FSTMerge formatted the XML file in its own way, but the value of the version tag was correct. KDiff refused to merge. Another case is reactive-streams-jvm. The file in conflict is CopyrightWaivers.txt, which hosts a tabular structure. Shown in Listing 7, the output of FSTMerge did not have the rows ouertani, 2m, and ldaley. Summer, on the other hand, added all necessary rows but did not order them to the developer’s liking. KDiff and wiggle refused to merge.
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
Listing 7: FSTMerge failed to add certain rows in reactivestreams-jvm savulchik ktoso +ouertani +2m +ldaley colinrgodsey
| Stanislav Savulchik, [email protected] | Konrad Malawski, [email protected], Typesafe | Slim Ouertani, [email protected] | Martynas Mickevicius, [email protected], Typesafe | Luke Daley, [email protected], Gradleware | Colin Godsey, [email protected], MediaMath Inc.
Listing 8: Summer added a row to a wrong place in reactivestreams-jvm savulchik | Stanislav Savulchik, [email protected] ktoso | Konrad Malawski, [email protected], Typesafe -colinrgodsey | Colin Godsey, [email protected], MediaMath Inc. ouertani | Slim Ouertani, [email protected] 2m | Martynas Mickevicius, [email protected], Typesafe ldaley | Luke Daley, [email protected], Gradleware +colinrgodsey | Colin Godsey, [email protected], MediaMath Inc.
The left and right branches of the repo jmonkeyengine made similar changes, both having -J-XX:PermSize=128m ⇒ -J-XX\:PermSize\= 128m. The merge result of Summer is -J-XX\\:PermSize\\=128m because Summer incorrectly applied the rule : → \: twice and = → \= twice. This case reveals that our algorithm can make mistakes with rules that insert characters.
5
Threats to Validity
Based on the evaluation of 179 Java and non-Java cases, we conclude that Summer outperforms other universal tools, though specialized AST tools achieve higher semantic accuracy. However, there are threats to the validity in our study.
5.1
Construct Validity
Our evaluation measures “merge accuracy”, i.e., literal match accuracy for a textual merge tool and semantic match accuracy for an AST tool. The literal match accuracy is purely objective and the semantic match accuracy is subjective. For example, it is subjective whether files with and without a copyright header are semantically equivalent. We relaxed the literal matching criteria by ignoring blank lines and spaces, and sorting Java’s import statements.
5.2
Internal Validity
Bugs in the implementation of the described algorithm threaten the internal validity of our claim, but we added 40+ automated tests and numerous assertions to ensure the correctness of Summer. The validity of Shen’s original ConflictBench has been established in [28]. To avoid introducing new threats, we preserved the original behavior of the benchmark driver and kept our improvements minimal, while enhancing error detection and reducing crashes due to file locking. Removing the repo FEBS-Shiro may slightly affect the dataset balance. However, we did not add a new repo because it would introduce a new bias. We fixed a directory in mybatis-plus that was invisible to a merge tool, so it had no impact on validity. Overall, our changes were necessary for a consistent and fair platform to establish experimental reliability.
Qiqi Jason Gu and Mikoláš Janota
5.3
External Validity
The evaluation was mainly done on the Java programming language with a variety of other data formats. Consequently, the accuracy numbers may not generalize well to documents in other languages or formats. Summer currently ignores changes in file encoding and line endings. These kinds of changes exist in the real world, but they are considered infrequent. Also, ConflictBench does not test multiple conflicting files. If one branch deletes file A and modifies file B, and the other branch modifies file A and deletes file B, as discussed in Section 3.2, a suitable merge direction cannot be determined and this reduces Summer’s merge accuracy. Finally, ConflictBench only provides the conflicting file to each merge tool, but Summer actually can read all changed files in the left and right branches to determine the best merge. Receiving limited information, Summer’s accuracy is a conservative estimate. The same applies to other tools. ConflictBench does not send styling guides to AST tools and thus they made formatting mistakes seen in Listings 3, 6, and 7. To mitigate this threat, the merge accuracy is defined as semantic match accuracy for an AST tool relying on Shen’s manually evaluated accuracy numbers.
6
Conclusions
A universal merge tool offers two key advantages in software engineering. Firstly, a single universal merge tool has low maintenance burdens on both developers and users. Its developers do not have to update the tool when a specific programming language introduces new syntax. Users avoid installing multiple language-specific tools, each requiring security vetting in enterprise environments. Additionally, multiple tools create compatibility challenges, as their dependencies may conflict. Secondly, advances in universal merge algorithms boost performance of high-level syntactic or semantic merge tools because high-level tools rely on string merge algorithms for the content of terminal nodes in a syntax tree, for instance the literal value of a string node. Our proposal Summer, as a universal textual merge algorithm and tool, observes original coding styles and deliberate syntax choices, preserves comments and copyright headers, and its merge output is ready to commit. For Java files, without relying on the knowledge about syntax or code refactoring, Summer matched 32% of developers’ merge resolutions character-to-character. The accuracy for XML, ReadMe, and other files is 41%, and overall 36%. The percentages are higher than other well-developed merge tools, demonstrating the effectiveness of the proposed algorithm. In the future, we plan to integrate our algorithm with the Darcs version control system. Next, we need to test Summer on a larger dataset, for example Ghiotto’s [12]. Data Availability. The source code of Summer is available at [14]. The source code of the improved ConflictBench is at [13]. Acknowledgements. The research was supported by the European Union under the project ROBOPROX (reg. no. CZ.02.01.01/00/22_008/ 0004590). This article is part of the RICAIP project that has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 857306.
A Universal Textual Merge Strategy Based on Tokens
References [1] Paola Accioly, Paulo Borba, and Guilherme Cavalcanti. 2018. Understanding semistructured merge conflict characteristics in open-source java projects. Empirical Software Engineering 23, 4 (2018), 2051–2085. [2] George W Adamson and Jillian Boreham. 1974. The use of an association measure based on character structure to identify semantically related pairs of words and document titles. Information storage and retrieval 10, 7-8 (1974), 253–260. [3] Sven Apel, Olaf Leßenich, and Christian Lengauer. 2012. Structured merge with auto-tuning: balancing precision and performance. In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering. Association for Computing Machinery, New York, NY, USA, 120–129. [4] Sven Apel, Jörg Liebig, Benjamin Brandl, Christian Lengauer, and Christian Kästner. 2011. Semistructured merge: rethinking merge in revision control systems. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering. Association for Computing Machinery, New York, NY, USA, 190–200. [5] R Bates. 2002. Text editor interfaces for semantic editors. SBLP2002, VI Simpósio Brasileiro do Linguagens de Programmaçao (2002). [6] Neil Brown. 2025. wiggle - apply rejected patches and perform word-wise diffs. https://github.com/neilbrown/wiggle [7] Guilherme Cavalcanti, Paulo Borba, and Paola Accioly. 2017. Evaluating and improving semistructured merge. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 1–27. [8] Elizabeth Dinella, Todd Mytkowicz, Alexey Svyatkovskiy, Christian Bird, Mayur Naik, and Shuvendu Lahiri. 2022. Deepmerge: learning to merge programs. IEEE Transactions on Software Engineering 49, 4 (2022), 1599–1614. [9] Joao Pedro Duarte, Paulo Borba, and Guilherme Cavalcanti. 2025. LastMerge: A language-agnostic structured tool for code integration. arXiv:2507.19687 [cs.SE] https://arxiv.org/abs/2507.19687 [10] Max Ellis, Sarah Nadi, and Danny Dig. 2022. Operation-based refactoring-aware merging: an empirical evaluation. IEEE Transactions on Software Engineering 49, 4 (2022), 2698–2721. [11] Joseph Gentle and Martin Kleppmann. 2025. Collaborative Text Editing with Egwalker: Better, Faster, Smaller. In Proceedings of the Twentieth European Conference on Computer Systems. Association for Computing Machinery, New York, NY, USA, 311–328. [12] Gleiph Ghiotto, Leonardo Murta, Márcio Barros, and Andre Van Der Hoek. 2018. On the nature of merge conflicts: a study of 2,731 open source Java projects hosted by GitHub. IEEE Transactions on Software Engineering 46, 8 (2018), 892–915. [13] Qiqi Gu and Mikoláš Janota. 2026. Source code of Improved ConflictBench. https://gitlab.com/token-based-merging/conflictbench [14] Qiqi Gu and Mikoláš Janota. 2026. Source code of Summer. https://gitlab.com/ token-based-merging/summer [15] Kaifeng Huang, Bihuan Chen, Xin Peng, Daihong Zhou, Ying Wang, Yang Liu, and Wenyun Zhao. 2018. Cldiff: generating concise linked code differences. In Proceedings of the 33rd ACM/IEEE international conference on automated software engineering. Association for Computing Machinery, New York, NY, USA, 679–690. [16] Judah Jacobson. 2009. A formalization of darcs patch theory using inverse semigroups. [17] Olaf Leßenich, Sven Apel, Christian Kästner, Georg Seibt, and Janet Siegmund. 2017. Renaming and shifted code in structured merging: looking ahead for precision and performance. In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, IEEE, Urbana, IL, USA, 543–553. [18] Mehran Mahmoudi, Sarah Nadi, and Nikolaos Tsantalis. 2019. Are refactorings to blame? an empirical study of refactorings in merge conflicts. In 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, IEEE, Hangzhou, China, 151–162. [19] Tom Mens. 2002. A state-of-the-art survey on software merging. IEEE transactions on software engineering 28, 5 (2002), 449–462. [20] Samuel Mimram and Cinzia Di Giusto. 2013. A categorical theory of patches. Electronic notes in theoretical computer science 298 (2013), 283–307. [21] Victor Cacciari Miraldo and Wouter Swierstra. 2019. An efficient algorithm for type-safe structural diffing. Proceedings of the ACM on Programming Languages 3, ICFP (2019), 1–29. [22] Eugene W Myers. 1986. An O(ND) difference algorithm and its variations. Algorithmica 1, 1 (1986), 251–266. [23] Yusuf Sulistyo Nugroho, Hideaki Hata, and Kenichi Matsumoto. 2020. How different are different diff algorithms in Git? Empirical Software Engineering 25 (2020), 790–823. [24] Rangeet Pan, Vu Le, Nachiappan Nagappan, Sumit Gulwani, Shuvendu Lahiri, and Mike Kaufman. 2021. Can program synthesis be used to learn merge conflict resolutions? an empirical analysis. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). IEEE, Madrid, Spain, 785–796. [25] Ei Pa Pa Pe-Than, Laura Dabbish, and James D Herbsleb. 2018. Collaborative writing on GitHub: a case study of a book project. In Companion of the 2018 ACM Conference on Computer Supported Cooperative Work and Social Computing. Association for Computing Machinery, New York, NY, USA, 305–308.
EASE 2026, 9–12 June, 2026, Glasgow, Scotland, United Kingdom
[26] David Roundy. 2005. Darcs: distributed version management in haskell. In Proceedings of the 2005 ACM SIGPLAN workshop on Haskell. Association for Computing Machinery, New York, NY, USA, 1–4. [27] Georg Seibt, Florian Heck, Guilherme Cavalcanti, Paulo Borba, and Sven Apel. 2021. Leveraging structure in software merge: an empirical study. IEEE Transactions on Software Engineering 48, 11 (2021), 4590–4610. [28] Bowen Shen and Na Meng. 2024. ConflictBench: a benchmark to evaluate software merge tools. Journal of Systems and Software 214 (2024), 112084. [29] Bo Shen, Wei Zhang, Haiyan Zhao, Guangtai Liang, Zhi Jin, and Qianxiang Wang. 2019. IntelliMerge: a refactoring-aware software merging technique. Proceedings of the ACM on Programming Languages 3, OOPSLA (2019), 1–28. [30] Chaochao Shen, Wenhua Yang, Minxue Pan, and Yu Zhou. 2023. Git merge conflict resolution leveraging strategy classification and LLM. In 2023 IEEE 23rd International Conference on Software Quality, Reliability, and Security (QRS). IEEE, Chiang Mai, Thailand, 228–239. [31] Martin Sjölund. 2021. Evaluating a tree diff algorithm for use in modelica tools. In Modelica Conferences. Linköping University Electronic Press, Linköping, Sweden, 529–537. [32] Alexey Svyatkovskiy, Sarah Fakhoury, Negar Ghorbani, Todd Mytkowicz, Elizabeth Dinella, Christian Bird, Jinu Jang, Neel Sundaresan, and Shuvendu K Lahiri. 2022. Program merge conflict resolution via neural transformers. In Proceedings of the 30th ACM joint European software engineering conference and symposium on the foundations of software engineering. Association for Computing Machinery, New York, NY, USA, 822–833. [33] Walter F Tichy. 1984. The string-to-string correction problem with block moves. ACM Transactions on Computer Systems (TOCS) 2, 4 (1984), 309–321. [34] Gustavo Vale, Claus Hunsen, Eduardo Figueiredo, and Sven Apel. 2021. Challenges of resolving merge conflicts: a mining and survey study. IEEE Transactions on Software Engineering 48, 12 (2021), 4964–4985. [35] Kaizhong Zhang and Tao Jiang. 1994. Some MAX SNP-hard results concerning unordered labeled trees. Inform. Process. Lett. 49, 5 (1994), 249–254. [36] Fengmin Zhu, Fei He, and Qianshan Yu. 2019. Enhancing precision of structured merge by proper tree matching. In 2019 IEEE/ACM 41st International Conference on Software Engineering: Companion Proceedings (ICSE-Companion). IEEE, Montreal, QC, Canada, 286–287.