Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: 2ef08388946ff079e418c761c041fae161f6df8a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
/*******************************************************************************
 * Copyright (c) 2000, 2008 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.jface.text;

import org.eclipse.core.runtime.Assert;


/**
 * Implements a gap managing text store. The gap text store relies on the assumption that
 * consecutive changes to a document are co-located. The start of the gap is always moved to the
 * location of the last change.
 * <p>
 * <strong>Performance:</strong> Typing-style changes perform in constant time unless re-allocation
 * becomes necessary. Generally, a change that does not cause re-allocation will cause at most one
 * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} operation of a length of
 * about <var>d</var>, where <var>d</var> is the distance from the previous change. Let <var>a(x)</var>
 * be the algorithmic performance of an <code>arraycopy</code> operation of the length <var>x</var>,
 * then such a change then performs in <i>O(a(x))</i>,
 * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in <i>O(a(length))</i>,
 * {@link #get(int)} in <i>O(1)</i>.
 * <p>
 * How frequently the array needs re-allocation is controlled by the constructor parameters.
 * </p>
 * <p>
 * This class is not intended to be subclassed.
 * </p>
 *
 * @see CopyOnWriteTextStore for a copy-on-write text store wrapper
 * @noextend This class is not intended to be subclassed by clients.
 */
public class GapTextStore implements ITextStore {
	/**
	 * The minimum gap size allocated when re-allocation occurs.
	 * @since 3.3
	 */
	private final int fMinGapSize;
	/**
	 * The maximum gap size allocated when re-allocation occurs.
	 * @since 3.3
	 */
	private final int fMaxGapSize;
	/**
	 * The multiplier to compute the array size from the content length
	 * (1&nbsp;&lt;=&nbsp;fSizeMultiplier&nbsp;&lt;=&nbsp;2).
	 *
	 * @since 3.3
	 */
	private final float fSizeMultiplier;

	/** The store's content */
	private char[] fContent= new char[0];
	/** Starting index of the gap */
	private int fGapStart= 0;
	/** End index of the gap */
	private int fGapEnd= 0;
	/**
	 * The current high water mark. If a change would cause the gap to grow larger than this, the
	 * array is re-allocated.
	 * @since 3.3
	 */
	private int fThreshold= 0;

	/**
	 * Creates a new empty text store using the specified low and high watermarks.
	 *
	 * @param lowWatermark unused - at the lower bound, the array is only resized when the content
	 *        does not fit
	 * @param highWatermark if the gap is ever larger than this, it will automatically be shrunken
	 *        (&gt;=&nbsp;0)
	 * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} instead
	 */
	@Deprecated
	public GapTextStore(int lowWatermark, int highWatermark) {
		/*
		 * Legacy constructor. The API contract states that highWatermark is the upper bound for the
		 * gap size. Albeit this contract was not previously adhered to, it is now: The allocated
		 * gap size is fixed at half the highWatermark. Since the threshold is always twice the
		 * allocated gap size, the gap will never grow larger than highWatermark. Previously, the
		 * gap size was initialized to highWatermark, causing re-allocation if the content length
		 * shrunk right after allocation. The fixed gap size is now only half of the previous value,
		 * circumventing that problem (there was no API contract specifying the initial gap size).
		 *
		 * The previous implementation did not allow the gap size to become smaller than
		 * lowWatermark, which doesn't make any sense: that area of the gap was simply never ever
		 * used.
		 */
		this(highWatermark / 2, highWatermark / 2, 0f);
	}

	/**
	 * Equivalent to
	 * {@linkplain GapTextStore#GapTextStore(int, int, float) new GapTextStore(256, 4096, 0.1f)}.
	 *
	 * @since 3.3
	 */
	public GapTextStore() {
		this(256, 4096, 0.1f);
	}

	/**
	 * Creates an empty text store that uses re-allocation thresholds relative to the content
	 * length. Re-allocation is controlled by the <em>gap factor</em>, which is the quotient of
	 * the gap size and the array size. Re-allocation occurs if a change causes the gap factor to go
	 * outside <code>[0,&nbsp;maxGapFactor]</code>. When re-allocation occurs, the array is sized
	 * such that the gap factor is <code>0.5 * maxGapFactor</code>. The gap size computed in this
	 * manner is bounded by the <code>minSize</code> and <code>maxSize</code> parameters.
	 * <p>
	 * A <code>maxGapFactor</code> of <code>0</code> creates a text store that never has a gap
	 * at all (if <code>minSize</code> is 0); a <code>maxGapFactor</code> of <code>1</code>
	 * creates a text store that doubles its size with every re-allocation and that never shrinks.
	 * </p>
	 * <p>
	 * The <code>minSize</code> and <code>maxSize</code> parameters are absolute bounds to the
	 * allocated gap size. Use <code>minSize</code> to avoid frequent re-allocation for small
	 * documents. Use <code>maxSize</code> to avoid a huge gap being allocated for large
	 * documents.
	 * </p>
	 *
	 * @param minSize the minimum gap size to allocate (&gt;=&nbsp;0; use 0 for no minimum)
	 * @param maxSize the maximum gap size to allocate (&gt;=&nbsp;minSize; use
	 *        {@link Integer#MAX_VALUE} for no maximum)
	 * @param maxGapFactor is the maximum fraction of the array that is occupied by the gap (<code>0&nbsp;&lt;=&nbsp;maxGapFactor&nbsp;&lt;=&nbsp;1</code>)
	 * @since 3.3
	 */
	public GapTextStore(int minSize, int maxSize, float maxGapFactor) {
		Assert.isLegal(0f <= maxGapFactor && maxGapFactor <= 1f);
		Assert.isLegal(0 <= minSize && minSize <= maxSize);
		fMinGapSize= minSize;
		fMaxGapSize= maxSize;
		fSizeMultiplier= 1 / (1 - maxGapFactor / 2);
	}

	@Override
	public final char get(int offset) {
		if (offset < fGapStart)
			return fContent[offset];

		return fContent[offset + gapSize()];
	}

	@Override
	public final String get(int offset, int length) {
		if (fGapStart <= offset)
			return new String(fContent, offset + gapSize() , length);

		final int end= offset + length;

		if (end <= fGapStart)
			return new String(fContent, offset, length);

		StringBuilder buf= new StringBuilder(length); // see Bug 113871
		buf.append(fContent, offset, fGapStart - offset);
		buf.append(fContent, fGapEnd, end - fGapStart);
		return buf.toString();
	}

	@Override
	public final int getLength() {
		return fContent.length - gapSize();
	}

	@Override
	public final void set(String text) {
		/*
		 * Moves the gap to the end of the content. There is no sensible prediction of where the
		 * next change will occur, but at least the next change will not trigger re-allocation. This
		 * is especially important when using the GapTextStore within a CopyOnWriteTextStore, where
		 * the GTS is only initialized right before a modification.
		 */
		replace(0, getLength(), text);
	}

	@Override
	public final void replace(int offset, int length, String text) {
		if (text == null) {
			adjustGap(offset, length, 0);
		} else {
			int textLength= text.length();
			adjustGap(offset, length, textLength);
			if (textLength != 0)
				text.getChars(0, textLength, fContent, offset);
		}
	}

	/**
	 * Moves the gap to <code>offset + add</code>, moving any content after
	 * <code>offset + remove</code> behind the gap. The gap size is kept between 0 and
	 * {@link #fThreshold}, leading to re-allocation if needed. The content between
	 * <code>offset</code> and <code>offset + add</code> is undefined after this operation.
	 *
	 * @param offset the offset at which a change happens
	 * @param remove the number of character which are removed or overwritten at <code>offset</code>
	 * @param add the number of character which are inserted or overwriting at <code>offset</code>
	 */
	private void adjustGap(int offset, int remove, int add) {
		final int oldGapSize= gapSize();
		final int newGapSize= oldGapSize - add + remove;
		final boolean reuseArray= 0 <= newGapSize && newGapSize <= fThreshold;

		final int newGapStart= offset + add;
		final int newGapEnd;

		if (reuseArray)
			newGapEnd= moveGap(offset, remove, oldGapSize, newGapSize, newGapStart);
		else
			newGapEnd= reallocate(offset, remove, oldGapSize, newGapSize, newGapStart);

		fGapStart= newGapStart;
		fGapEnd= newGapEnd;
	}

	/**
	 * Moves the gap to <code>newGapStart</code>.
	 *
	 * @param offset the change offset
	 * @param remove the number of removed / overwritten characters
	 * @param oldGapSize the old gap size
	 * @param newGapSize the gap size after the change
	 * @param newGapStart the offset in the array to move the gap to
	 * @return the new gap end
	 * @since 3.3
	 */
	private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) {
		/*
		 * No re-allocation necessary. The area between the change offset and gap can be copied
		 * in at most one operation. Don't copy parts that will be overwritten anyway.
		 */
		final int newGapEnd= newGapStart + newGapSize;
		if (offset < fGapStart) {
			int afterRemove= offset + remove;
			if (afterRemove < fGapStart) {
				final int betweenSize= fGapStart - afterRemove;
				arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
			}
			// otherwise, only the gap gets enlarged
		} else {
			final int offsetShifted= offset + oldGapSize;
			final int betweenSize= offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
			arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
		}
		return newGapEnd;
	}

	/**
	 * Reallocates a new array and copies the data from the previous one.
	 *
	 * @param offset the change offset
	 * @param remove the number of removed / overwritten characters
	 * @param oldGapSize the old gap size
	 * @param newGapSize the gap size after the change if no re-allocation would occur (can be negative)
	 * @param newGapStart the offset in the array to move the gap to
	 * @return the new gap end
	 * @since 3.3
	 */
	private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) {
		// the new content length (without any gap)
		final int newLength= fContent.length - newGapSize;
		// the new array size based on the gap factor
		int newArraySize= (int) (newLength * fSizeMultiplier);
		newGapSize= newArraySize - newLength;

		// bound the gap size within min/max
		if (newGapSize < fMinGapSize) {
			newGapSize= fMinGapSize;
			newArraySize= newLength + newGapSize;
		} else if (newGapSize > fMaxGapSize) {
			newGapSize= fMaxGapSize;
			newArraySize= newLength + newGapSize;
		}

		// the upper threshold is always twice the gapsize
		fThreshold= newGapSize * 2;
		final char[] newContent= allocate(newArraySize);
		final int newGapEnd= newGapStart + newGapSize;

		/*
		 * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
		 * array. Either one of change offset and the gap may come first.
		 * - unchanged area before the change offset / gap
		 * - area between the change offset and the gap (either one may be first)
		 * - rest area after the change offset / after the gap
		 */
		if (offset < fGapStart) {
			// change comes before gap
			arrayCopy(0, newContent, 0, offset);
			int afterRemove= offset + remove;
			if (afterRemove < fGapStart) {
				// removal is completely before the gap
				final int betweenSize= fGapStart - afterRemove;
				arrayCopy(afterRemove, newContent, newGapEnd, betweenSize);
				final int restSize= fContent.length - fGapEnd;
				arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize);
			} else {
				// removal encompasses the gap
				afterRemove += oldGapSize;
				final int restSize= fContent.length - afterRemove;
				arrayCopy(afterRemove, newContent, newGapEnd, restSize);
			}
		} else {
			// gap comes before change
			arrayCopy(0, newContent, 0, fGapStart);
			final int offsetShifted= offset + oldGapSize;
			final int betweenSize= offsetShifted - fGapEnd;
			arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
			final int afterRemove= offsetShifted + remove;
			final int restSize= fContent.length - afterRemove;
			arrayCopy(afterRemove, newContent, newGapEnd, restSize);
		}

		fContent= newContent;
		return newGapEnd;
	}

	/**
	 * Allocates a new <code>char[size]</code>.
	 *
	 * @param size the length of the new array.
	 * @return a newly allocated char array
	 * @since 3.3
	 */
	private char[] allocate(int size) {
		return new char[size];
	}

	/*
	 * Executes System.arraycopy if length != 0. A length < 0 cannot happen -> don't hide coding
	 * errors by checking for negative lengths.
	 * @since 3.3
	 */
	private void arrayCopy(int srcPos, char[] dest, int destPos, int length) {
		if (length != 0)
			System.arraycopy(fContent, srcPos, dest, destPos, length);
	}

	/**
	 * Returns the gap size.
	 *
	 * @return the gap size
	 * @since 3.3
	 */
	private int gapSize() {
		return fGapEnd - fGapStart;
	}

	/**
	 * Returns a copy of the content of this text store.
	 * For internal use only.
	 *
	 * @return a copy of the content of this text store
	 */
	protected String getContentAsString() {
		return new String(fContent);
	}

	/**
	 * Returns the start index of the gap managed by this text store.
	 * For internal use only.
	 *
	 * @return the start index of the gap managed by this text store
	 */
	protected int getGapStartIndex() {
		return fGapStart;
	}

	/**
	 * Returns the end index of the gap managed by this text store.
	 * For internal use only.
	 *
	 * @return the end index of the gap managed by this text store
	 */
	protected int getGapEndIndex() {
		return fGapEnd;
	}
}

Back to the top