Merge branch 'db/javac-ast'
[idea/community.git] / platform / diff-impl / src / com / intellij / diff / comparison / MergeResolveUtil.kt
1 /*
2  * Copyright 2000-2016 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.diff.comparison
17
18 import com.intellij.diff.fragments.DiffFragment
19 import com.intellij.diff.util.Side
20 import com.intellij.diff.util.Side.LEFT
21 import com.intellij.diff.util.Side.RIGHT
22 import com.intellij.openapi.progress.DumbProgressIndicator
23 import com.intellij.util.text.MergingCharSequence
24
25 object MergeResolveUtil {
26   /*
27    * Here we assume, that resolve results are explicitly verified by user and can be safely undone.
28    * Thus we trade higher chances of incorrect resolve for higher chances of correct resolve.
29    *
30    * We're making an assertion, that "A-X-B" and "B-X-A" conflicts should produce equal results.
31    * This leads us to conclusion, that insertion-insertion conflicts can't be possibly resolved (if inserted fragments are different),
32    * because we don't know the right order of inserted chunks (and sorting them alphabetically or by length makes no sense).
33    *
34    * deleted-inserted conflicts can be resolved by applying both of them.
35    * deleted-deleted conflicts can be resolved by merging deleted intervals.
36    * modifications can be considered as "insertion + deletion" and resolved accordingly.
37    */
38   @JvmStatic
39   fun tryResolveConflict(leftText: CharSequence, baseText: CharSequence, rightText: CharSequence): CharSequence? {
40     try {
41       val resolved = Helper(leftText, baseText, rightText).execute(ComparisonPolicy.DEFAULT)
42       if (resolved != null) return resolved
43
44       return Helper(leftText, baseText, rightText).execute(ComparisonPolicy.IGNORE_WHITESPACES)
45     }
46     catch (e: DiffTooBigException) {
47       return null
48     }
49   }
50 }
51
52 private class Helper(val leftText: CharSequence, val baseText: CharSequence, val rightText: CharSequence) {
53   val newContent = StringBuilder()
54
55   var lastBaseOffset = 0
56   var index1 = 0
57   var index2 = 0
58
59   fun execute(policy: ComparisonPolicy): CharSequence? {
60     val fragments1 = ByWord.compare(baseText, leftText, policy, DumbProgressIndicator.INSTANCE)
61     val fragments2 = ByWord.compare(baseText, rightText, policy, DumbProgressIndicator.INSTANCE)
62
63     while (true) {
64       val changeStart1 = fragments1.getOrNull(index1)?.startOffset1 ?: -1
65       val changeStart2 = fragments2.getOrNull(index2)?.startOffset1 ?: -1
66
67       if (changeStart1 == -1 && changeStart2 == -1) {
68         // no more changes left
69         appendBase(baseText.length)
70         break
71       }
72
73       // skip till the next block of changes
74       if (changeStart1 != -1 && changeStart2 != -1) {
75         appendBase(Math.min(changeStart1, changeStart2))
76       }
77       else if (changeStart1 != -1) {
78         appendBase(changeStart1)
79       }
80       else {
81         appendBase(changeStart2)
82       }
83
84
85       // collect next block of changes, that intersect one another.
86       var baseOffsetEnd = lastBaseOffset
87       var end1 = index1
88       var end2 = index2
89
90       while (true) {
91         val next1 = fragments1.getOrNull(end1)
92         val next2 = fragments2.getOrNull(end2)
93
94         if (next1 != null && next1.startOffset1 <= baseOffsetEnd) {
95           baseOffsetEnd = Math.max(baseOffsetEnd, next1.endOffset1)
96           end1++
97           continue
98         }
99         if (next2 != null && next2.startOffset1 <= baseOffsetEnd) {
100           baseOffsetEnd = Math.max(baseOffsetEnd, next2.endOffset1)
101           end2++
102           continue
103         }
104
105         break
106       }
107       assert(index1 != end1 || index2 != end2)
108
109       val inserted1 = getInsertedContent(fragments1, index1, end1, LEFT)
110       val inserted2 = getInsertedContent(fragments2, index2, end2, RIGHT)
111       index1 = end1
112       index2 = end2
113
114
115       // merge and apply deletions
116       lastBaseOffset = baseOffsetEnd
117
118
119       // merge and apply non-conflicted insertions
120       if (inserted1.isEmpty() && inserted2.isEmpty()) continue
121       if (inserted2.isEmpty()) {
122         newContent.append(inserted1)
123         continue
124       }
125       if (inserted1.isEmpty()) {
126         newContent.append(inserted2)
127         continue
128       }
129
130       if (ComparisonUtil.isEquals(inserted1, inserted2, policy)) {
131         val inserted = if (inserted1.length <= inserted2.length) inserted1 else inserted2
132         newContent.append(inserted)
133         continue
134       }
135
136       // we faced conflicting insertions - resolve failed
137       return null;
138     }
139
140     return newContent
141   }
142
143   private fun appendBase(endOffset: Int) {
144     if (lastBaseOffset == endOffset) return
145     newContent.append(baseText.subSequence(lastBaseOffset, endOffset))
146     lastBaseOffset = endOffset
147   }
148
149   private fun getInsertedContent(fragments: List<DiffFragment>, start: Int, end: Int, side: Side): CharSequence {
150     val text = side.select(leftText, rightText)!!
151
152     val empty: CharSequence = ""
153     return fragments.subList(start, end).fold(empty, { prefix, fragment ->
154       MergingCharSequence(prefix, text.subSequence(fragment.startOffset2, fragment.endOffset2))
155     })
156   }
157 }