terminal: support custom keyboard shortcuts for Split Right/Split Down (IDEA-237048)
[idea/community.git] / platform / diff-impl / src / com / intellij / diff / tools / fragmented / LineNumberConvertor.java
1 // Copyright 2000-2020 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.intellij.diff.tools.fragmented;
3
4 import com.intellij.util.SmartList;
5 import org.jetbrains.annotations.NotNull;
6
7 import java.util.List;
8 import java.util.Map;
9 import java.util.TreeMap;
10 import java.util.function.IntUnaryOperator;
11
12 public final class LineNumberConvertor {
13   // Master -> Slave
14   @NotNull private final TreeMap<Integer, Data> myFragments;
15
16   // Slave -> Master
17   @NotNull private final TreeMap<Integer, Data> myInvertedFragments;
18
19   @NotNull private final Corrector myCorrector = new Corrector();
20
21   private LineNumberConvertor(@NotNull TreeMap<Integer, Data> fragments,
22                               @NotNull TreeMap<Integer, Data> invertedFragments) {
23     myFragments = fragments;
24     myInvertedFragments = invertedFragments;
25   }
26
27   public int convert(int value) {
28     return convert(value, true, false);
29   }
30
31   public int convertInv(int value) {
32     return convert(value, false, false);
33   }
34
35   public int convertApproximate(int value) {
36     return convert(value, true, true);
37   }
38
39   public int convertApproximateInv(int value) {
40     return convert(value, false, true);
41   }
42
43   //
44   // Impl
45   //
46
47   @NotNull
48   public IntUnaryOperator createConvertor() {
49     return this::convert;
50   }
51
52   public int convert(int value, boolean fromMaster, boolean approximate) {
53     return myCorrector.convertCorrected(value, fromMaster, approximate);
54   }
55
56   /**
57    * Master was changed. We should update converters, because of changed shift.
58    *
59    * @param synchronous true - corresponding range in slave was changed in the same way.
60    *                           NB: [startLine, endLine) range MUST be strictly mapped to the slave.
61    *                    false - slave was not changed.
62    *                            Modified range can no longer be strictly converted.
63    */
64   public void handleMasterChange(int startLine, int endLine, int shift, boolean synchronous) {
65     myCorrector.handleMasterChange(startLine, endLine, shift, synchronous);
66   }
67
68
69   /**
70    * @param approximate false: return exact matching between lines, and -1 if it's impossible
71    *        (strict)    true: return 'good enough' position, even if exact matching is impossible
72    */
73   private int convertRaw(boolean fromMaster, int value, boolean approximate) {
74     TreeMap<Integer, Data> fragments = fromMaster ? myFragments : myInvertedFragments;
75
76     if (approximate) {
77       Map.Entry<Integer, Data> prevEntry = fragments.floorEntry(value);
78       if (prevEntry == null) return 0;
79       int start = prevEntry.getKey();
80       Data data = prevEntry.getValue();
81
82       return Math.min(data.otherStart - start + value, data.otherStart + data.otherLength);
83     }
84     else {
85       Map.Entry<Integer, Data> prevEntry = fragments.floorEntry(value);
86       if (prevEntry == null) return -1;
87       int start = prevEntry.getKey();
88       Data data = prevEntry.getValue();
89
90       if (value >= start + data.length) return -1;
91       if (data.length != data.otherLength) return -1;
92
93       return data.otherStart - start + value;
94     }
95   }
96
97   public static class Builder {
98     @NotNull private final TreeMap<Integer, Data> myFragments = new TreeMap<>();
99     @NotNull private final TreeMap<Integer, Data> myInvertedFragments = new TreeMap<>();
100
101     public void put(int masterStart, int slaveStart, int length) {
102       put(masterStart, slaveStart, length, length);
103     }
104
105     public void put(int masterStart, int slaveStart, int masterLength, int slaveLength) {
106       myFragments.put(masterStart, new Data(masterLength, slaveStart, slaveLength));
107       myInvertedFragments.put(slaveStart, new Data(slaveLength, masterStart, masterLength));
108     }
109
110     @NotNull
111     public LineNumberConvertor build() {
112       return new LineNumberConvertor(myFragments, myInvertedFragments);
113     }
114   }
115
116   private static class Data {
117     public final int length;
118     public final int otherStart;
119     public final int otherLength;
120
121     Data(int length, int otherStart, int otherLength) {
122       this.length = length;
123       this.otherStart = otherStart;
124       this.otherLength = otherLength;
125     }
126   }
127
128   /*
129    * myFragments allow to convert between Sm-So-Su, Mm-Mo-Mu, Em-Eo-Eu.
130    *
131    * Corrector processes information about master side modifications B -> B'
132    * and allows to convert between Sm'-So'-Su', Mm'-Mo'-Mu', Em'-Eo'-Eu'.
133    *
134    * sync - when master and slave are modified in the same way
135    * async - when only master is modified
136    *
137    *
138    *         Before                            After
139    *
140    *  sync            async
141    *         master
142    *
143    * Sm +       + So    + Su         Sm' +       + So'   + Su'
144    *    |       |       |                |       |       |
145    *    |       |       |                |       |       |
146    *    |       |       |                |       |       |
147    * Am +-------+ Ao    + Au         Am' +-------+ Ao'   + Au'
148    *    |       |       |                |       |       |
149    * Mm +   B   + Mo    + Mu         Mm' +       + Mo'   + Mu'
150    *    |       |       |                |   B'  |       |
151    * Bm +-------+ Bo    |                |       |       |
152    *    |       |       |                |       |       |
153    *    |       |       |            Bm' +-------+ Bo'   |
154    *    |       |       |                |       |       |
155    * Em +       + Eo    + Eu             |       |       + Eu'
156    *                                     |       |
157    *                                 Em' +       + Eo'
158    *
159    * Su == Su'; Mu == Mu'; Eu == Eu'; Au == Au'
160    * Sm == Sm'; So == So'; Am == Am'; Ao == Ao'
161    * Bo - Ao == Bm - Am; Bo' - Ao' == Bm' - Am'
162    *
163    * change.startMaster == Ao == Ao'
164    * change.startSlave == Am == Am'
165    *
166    * change.oldLength == Bo - Ao
167    * change.newLength == Bo' - Ao'
168    *
169    * In case of multiple changes - we process them in reverse order (from new to old).
170    *
171    */
172   private class Corrector {
173     private final List<CorrectedChange> myChanges = new SmartList<>();
174
175     public void handleMasterChange(int startLine, int endLine, int shift, boolean synchronous) {
176       int oldLength = endLine - startLine;
177       int newLength = oldLength + shift;
178
179       if (synchronous) {
180         int oldSlaveStart = convert(startLine, true, false);
181         assert oldSlaveStart != -1;
182
183         myChanges.add(new CorrectedChange(startLine, oldSlaveStart, oldLength, newLength));
184       }
185       else {
186         myChanges.add(new CorrectedChange(startLine, oldLength, newLength));
187       }
188     }
189
190     public int convertCorrected(int value, boolean fromMaster, boolean approximate) {
191       if (fromMaster) {
192         return convertFromMaster(value, approximate, myChanges.size() - 1);
193       }
194       else {
195         return convertFromSlave(value, approximate, myChanges.size() - 1);
196       }
197     }
198
199     private int convertFromSlave(int value, boolean approximate, int index) {
200       if (index < 0) {
201         return convertRaw(false, value, approximate);
202       }
203
204       CorrectedChange change = myChanges.get(index);
205       int shift = change.newLength - change.oldLength;
206
207       if (!change.synchronous) { // ?u' -> ?o'
208         int converted = convertFromSlave(value, approximate, index - 1);
209         if (converted < change.startMaster) { // Su' -> So'
210           // Su' == Su; So' == So
211           // value == Su'; converted == So
212           return converted;
213         }
214         if (converted >= change.startMaster + change.oldLength) { // Eu' -> Eo'
215           // Eo' == Eo + shift; Eu' == Eu
216           // value == Eu'; converted == Eo
217           return converted + shift;
218         }
219
220         // Mu' -> Mo'
221         if (!approximate) return -1;
222         // We can't convert Mo into Mo'
223         // converted == Mo
224         return append(converted, Math.min(change.newLength, converted - change.startMaster));
225       }
226       else { // ?m '-> ?o'
227         if (value < change.startSlave) { // Sm' -> So'
228           return convertFromSlave(value, approximate, index - 1);
229         }
230         if (value >= change.startSlave + change.newLength) { // Em' -> Eo'
231           // Em' == Em + shift; Eo' == Eo + shift
232           // value == Em'; converted == Eo
233           int converted = convertFromSlave(value - shift, approximate, index - 1);
234           return append(converted, shift);
235         }
236
237         // Mm' -> Mo'
238         // Ao == Ao'; Am == Am'; Mo' - Ao' == Mm' - Am'
239         // convertedStart == Ao; value - change.startMaster == Mm' - Am'
240         int convertedStart = convertFromSlave(change.startSlave, approximate, index - 1);
241         return append(convertedStart, value - change.startSlave);
242       }
243     }
244
245     private int convertFromMaster(int value, boolean approximate, int index) {
246       if (index < 0) {
247         return convertRaw(true, value, approximate);
248       }
249
250       CorrectedChange change = myChanges.get(index);
251       int shift = change.newLength - change.oldLength;
252
253       if (value < change.startMaster) { // So' -> Sm', So' -> Su'
254         // So' == So; Sm' == Sm; Su' == Su
255         // value = So'
256         return convertFromMaster(value, approximate, index - 1);
257       }
258       if (value >= change.startMaster + change.newLength) { // Eo' -> Em', Eo' -> Eu'
259         // Eo' == Eo + shift; Em' == Em + shift; Eu' == Eu
260         // value = Eo'
261         int converted = convertFromMaster(value - shift, approximate, index - 1);
262         return append(converted, change.synchronous ? shift : 0);
263       }
264
265       if (!change.synchronous) { // Mo' -> Mu'
266         if (!approximate) return -1;
267         // we can't convert Mo' into Mo. And thus get valid Mu/Mu'.
268         // return: Au'
269         return convertFromMaster(change.startMaster, approximate, index - 1);
270       }
271       else { // Mo' -> Mm'
272         // Ao == Ao'; Am == Am'; Mo' - Ao' == Mm' - Am'
273         // value = Mo'
274         int convertedStart = convertFromMaster(change.startMaster, approximate, index - 1);
275         return append(convertedStart, value - change.startMaster);
276       }
277     }
278
279     private int append(int value, int shift) {
280       return value == -1 ? -1 : value + shift;
281     }
282   }
283
284   private static class CorrectedChange {
285     public final boolean synchronous;
286
287     public final int startMaster;
288     public final int startSlave;
289     public final int oldLength;
290     public final int newLength;
291
292     CorrectedChange(int startMaster, int oldLength, int newLength) {
293       this.synchronous = false;
294       this.startSlave = -1;
295
296       this.startMaster = startMaster;
297       this.oldLength = oldLength;
298       this.newLength = newLength;
299     }
300
301     CorrectedChange(int startMaster, int startSlave, int oldLength, int newLength) {
302       this.synchronous = true;
303
304       this.startMaster = startMaster;
305       this.startSlave = startSlave;
306       this.oldLength = oldLength;
307       this.newLength = newLength;
308     }
309   }
310 }