some more assertions
[idea/community.git] / platform / core-impl / src / com / intellij / openapi / editor / impl / LineSet.java
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.openapi.editor.impl;
17
18 import com.intellij.openapi.editor.ex.LineIterator;
19 import com.intellij.openapi.util.text.LineTokenizer;
20 import com.intellij.util.BitUtil;
21 import com.intellij.util.text.CharArrayUtil;
22 import com.intellij.util.text.MergingCharSequence;
23 import gnu.trove.TByteArrayList;
24 import gnu.trove.TIntArrayList;
25 import org.jetbrains.annotations.NotNull;
26 import org.jetbrains.annotations.TestOnly;
27
28 import java.util.Arrays;
29
30 /**
31  * Data structure specialized for working with document text lines, i.e. stores information about line mapping to document
32  * offsets and provides convenient ways to work with that information like retrieving target line by document offset etc.
33  * <p/>
34  * Immutable.
35  */
36 public class LineSet{
37   private static final int MODIFIED_MASK = 0x4;
38   private static final int SEPARATOR_MASK = 0x3;
39
40   private final int[] myStarts;
41   private final byte[] myFlags;
42   private final int myLength;
43
44   private LineSet(int[] starts, byte[] flags, int length) {
45     myStarts = starts;
46     myFlags = flags;
47     myLength = length;
48   }
49
50   public static LineSet createLineSet(CharSequence text) {
51     return createLineSet(text, false);
52   }
53
54   @NotNull
55   private static LineSet createLineSet(@NotNull CharSequence text, boolean markModified) {
56     TIntArrayList starts = new TIntArrayList();
57     TByteArrayList flags = new TByteArrayList();
58
59     LineTokenizer lineTokenizer = new LineTokenizer(text);
60     while (!lineTokenizer.atEnd()) {
61       starts.add(lineTokenizer.getOffset());
62       flags.add((byte) (lineTokenizer.getLineSeparatorLength() | (markModified ? MODIFIED_MASK : 0)));
63       lineTokenizer.advance();
64     }
65     return new LineSet(starts.toNativeArray(), flags.toNativeArray(), text.length());
66   }
67
68   @NotNull
69   LineSet update(@NotNull CharSequence prevText, int start, int end, @NotNull CharSequence replacement, boolean wholeTextReplaced) {
70     if (myLength == 0) {
71       return createLineSet(replacement, !wholeTextReplaced);
72     }
73
74     LineSet result = isSingleLineChange(start, end, replacement)
75                      ? updateInsideOneLine(findLineIndex(start), replacement.length() - (end - start))
76                      : genericUpdate(prevText, start, end, replacement);
77
78     if (doTest) {
79       MergingCharSequence newText = new MergingCharSequence(
80         new MergingCharSequence(prevText.subSequence(0, start), replacement),
81         prevText.subSequence(end, prevText.length()));
82       result.checkEquals(createLineSet(newText));
83     }
84     return wholeTextReplaced ? result.clearModificationFlags() : result;
85   }
86
87   private boolean isSingleLineChange(int start, int end, @NotNull CharSequence replacement) {
88     if (start == 0 && end == myLength && replacement.length() == 0) return false;
89
90     int startLine = findLineIndex(start);
91     return startLine == findLineIndex(end) && !CharArrayUtil.containLineBreaks(replacement) && !isLastEmptyLine(startLine);
92   }
93
94   @NotNull
95   private LineSet updateInsideOneLine(int line, int lengthDelta) {
96     int[] starts = myStarts.clone();
97     for (int i = line + 1; i < starts.length; i++) {
98       starts[i] += lengthDelta;
99     }
100
101     byte[] flags = myFlags.clone();
102     flags[line] |= MODIFIED_MASK;
103     return new LineSet(starts, flags, myLength + lengthDelta);
104   }
105
106   private LineSet genericUpdate(CharSequence prevText, int _start, int _end, CharSequence replacement) {
107     int startOffset = _start;
108     if (replacement.length() > 0 && replacement.charAt(0) == '\n' && startOffset > 0 && prevText.charAt(startOffset - 1) == '\r') {
109       startOffset--;
110     }
111     int startLine = findLineIndex(startOffset);
112     startOffset = getLineStart(startLine);
113
114     int endOffset = _end;
115     if (replacement.length() > 0 && replacement.charAt(replacement.length() - 1) == '\r' && endOffset < prevText.length() && prevText.charAt(endOffset) == '\n') {
116       endOffset++;
117     }
118     int endLine = findLineIndex(endOffset);
119     endOffset = getLineEnd(endLine);
120     if (!isLastEmptyLine(endLine)) endLine++;
121
122     replacement = new MergingCharSequence(
123       new MergingCharSequence(prevText.subSequence(startOffset, _start), replacement),
124       prevText.subSequence(_end, endOffset));
125
126     LineSet patch = createLineSet(replacement, true);
127     return applyPatch(startOffset, endOffset, startLine, endLine, patch);
128   }
129
130   private void checkEquals(@NotNull LineSet fresh) {
131     if (getLineCount() != fresh.getLineCount()) {
132       throw new AssertionError();
133     }
134     for (int i = 0; i < getLineCount(); i++) {
135       boolean start = getLineStart(i) != fresh.getLineStart(i);
136       boolean end = getLineEnd(i) != fresh.getLineEnd(i);
137       boolean sep = getSeparatorLength(i) != fresh.getSeparatorLength(i);
138       if (start || end || sep) {
139         throw new AssertionError();
140       }
141     }
142   }
143
144   @NotNull
145   private LineSet applyPatch(int startOffset, int endOffset, int startLine, int endLine, @NotNull LineSet patch) {
146     int lineShift = patch.myStarts.length - (endLine - startLine);
147     int lengthShift = patch.myLength - (endOffset - startOffset);
148
149     int newLineCount = myStarts.length + lineShift;
150     int[] starts = new int[newLineCount];
151     byte[] flags = new byte[newLineCount];
152
153     for (int i = 0; i < startLine; i++) {
154       starts[i] = myStarts[i];
155       flags[i] = myFlags[i];
156     }
157     for (int i = 0; i < patch.myStarts.length; i++) {
158       starts[startLine + i] = patch.myStarts[i] + startOffset;
159       flags[startLine + i] = patch.myFlags[i];
160     }
161     for (int i = endLine; i < myStarts.length; i++) {
162       starts[lineShift + i] = myStarts[i] + lengthShift;
163       flags[lineShift + i] = myFlags[i];
164     }
165     return new LineSet(starts, flags, myLength + lengthShift);
166   }
167
168   public int findLineIndex(int offset) {
169     if (offset < 0 || offset > myLength) {
170       throw new IndexOutOfBoundsException("Wrong offset: " + offset + ". Should be in range: [0, " + myLength + "]");
171     }
172     if (myLength == 0) return 0;
173     if (offset == myLength) return getLineCount() - 1;
174
175     int bsResult = Arrays.binarySearch(myStarts, offset);
176     return bsResult >= 0 ? bsResult : -bsResult - 2;
177   }
178
179   @NotNull
180   public LineIterator createIterator() {
181     return new LineIteratorImpl(this);
182   }
183
184   public final int getLineStart(int index) {
185     checkLineIndex(index);
186     return isLastEmptyLine(index) ? myLength : myStarts[index];
187   }
188
189   private boolean isLastEmptyLine(int index) {
190     return index == myFlags.length && index > 0 && (myFlags[index - 1] & SEPARATOR_MASK) > 0;
191   }
192
193   public final int getLineEnd(int index) {
194     checkLineIndex(index);
195     return index >= myStarts.length - 1 ? myLength : myStarts[index + 1];
196   }
197
198   private void checkLineIndex(int index) {
199     if (index < 0 || index >= getLineCount()) {
200       throw new IndexOutOfBoundsException("Wrong line: " + index + ". Available lines count: " + getLineCount());
201     }
202   }
203
204   final boolean isModified(int index) {
205     checkLineIndex(index);
206     return !isLastEmptyLine(index) && BitUtil.isSet(myFlags[index], MODIFIED_MASK);
207   }
208
209   @NotNull
210   final LineSet setModified(int index) {
211     if (isLastEmptyLine(index) || isModified(index)) return this;
212
213     byte[] flags = myFlags.clone();
214     flags[index] |= MODIFIED_MASK;
215     return new LineSet(myStarts, flags, myLength);
216   }
217
218   @NotNull
219   LineSet clearModificationFlags(int startLine, int endLine) {
220     if (startLine > endLine) {
221       throw new IllegalArgumentException("endLine < startLine: " + endLine + " < " + startLine + "; lineCount: " + getLineCount());
222     }
223     checkLineIndex(startLine);
224     checkLineIndex(endLine - 1);
225
226     if (isLastEmptyLine(endLine - 1)) endLine--;
227     if (startLine >= endLine) return this;
228
229     byte[] flags = myFlags.clone();
230     for (int i = startLine; i < endLine; i++) {
231       flags[i] &= ~MODIFIED_MASK;
232     }
233     return new LineSet(myStarts, flags, myLength);
234   }
235
236   @NotNull
237   LineSet clearModificationFlags() {
238     byte[] flags = myFlags.clone();
239     for (int i = 0; i < flags.length; i++) {
240       flags[i] &= ~MODIFIED_MASK;
241     }
242     return new LineSet(myStarts, flags, myLength);
243   }
244
245   final int getSeparatorLength(int index) {
246     checkLineIndex(index);
247     return index < myFlags.length ? myFlags[index] & SEPARATOR_MASK : 0;
248   }
249
250   final int getLineCount() {
251     return myStarts.length + (isLastEmptyLine(myStarts.length) ? 1 : 0);
252   }
253
254   @TestOnly
255   public static void setTestingMode(boolean testMode) {
256     doTest = testMode;
257   }
258
259   private static boolean doTest;
260
261   int getLength() {
262     return myLength;
263   }
264 }