Line data Source code
1 : /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #ifndef GFX_SKIP_CHARS_H
7 : #define GFX_SKIP_CHARS_H
8 :
9 : #include "nsTArray.h"
10 :
11 : /*
12 : * gfxSkipChars is a data structure representing a list of characters that
13 : * have been skipped. The initial string is called the "original string"
14 : * and after skipping some characters, the result is called the "skipped string".
15 : * gfxSkipChars provides efficient ways to translate between offsets in the
16 : * original string and the skipped string. It is used by textrun code to keep
17 : * track of offsets before and after text transformations such as whitespace
18 : * compression and control code deletion.
19 : */
20 :
21 : /**
22 : * The gfxSkipChars is represented as a sorted array of skipped ranges.
23 : *
24 : * A freshly-created gfxSkipChars means "all chars kept".
25 : */
26 92 : class gfxSkipChars
27 : {
28 : friend struct SkippedRangeStartComparator;
29 : friend struct SkippedRangeOffsetComparator;
30 :
31 : private:
32 : class SkippedRange
33 : {
34 : public:
35 0 : SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta)
36 0 : : mOffset(aOffset), mLength(aLength), mDelta(aDelta)
37 0 : { }
38 :
39 0 : uint32_t Start() const
40 : {
41 0 : return mOffset;
42 : }
43 :
44 0 : uint32_t End() const
45 : {
46 0 : return mOffset + mLength;
47 : }
48 :
49 : uint32_t Length() const
50 : {
51 : return mLength;
52 : }
53 :
54 0 : uint32_t SkippedOffset() const
55 : {
56 0 : return mOffset - mDelta;
57 : }
58 :
59 : uint32_t Delta() const
60 : {
61 : return mDelta;
62 : }
63 :
64 0 : uint32_t NextDelta() const
65 : {
66 0 : return mDelta + mLength;
67 : }
68 :
69 0 : void Extend(uint32_t aChars)
70 : {
71 0 : mLength += aChars;
72 0 : }
73 :
74 : private:
75 : uint32_t mOffset; // original-string offset at which we want to skip
76 : uint32_t mLength; // number of skipped chars at this offset
77 : uint32_t mDelta; // sum of lengths of preceding skipped-ranges
78 : };
79 :
80 : public:
81 107 : gfxSkipChars()
82 107 : : mCharCount(0)
83 107 : { }
84 :
85 0 : void SkipChars(uint32_t aChars)
86 : {
87 0 : NS_ASSERTION(mCharCount + aChars > mCharCount,
88 : "Character count overflow");
89 0 : uint32_t rangeCount = mRanges.Length();
90 0 : uint32_t delta = 0;
91 0 : if (rangeCount > 0) {
92 0 : SkippedRange& lastRange = mRanges[rangeCount - 1];
93 0 : if (lastRange.End() == mCharCount) {
94 0 : lastRange.Extend(aChars);
95 0 : mCharCount += aChars;
96 0 : return;
97 : }
98 0 : delta = lastRange.NextDelta();
99 : }
100 0 : mRanges.AppendElement(SkippedRange(mCharCount, aChars, delta));
101 0 : mCharCount += aChars;
102 : }
103 :
104 202 : void KeepChars(uint32_t aChars)
105 : {
106 202 : NS_ASSERTION(mCharCount + aChars > mCharCount,
107 : "Character count overflow");
108 202 : mCharCount += aChars;
109 202 : }
110 :
111 0 : void SkipChar()
112 : {
113 0 : SkipChars(1);
114 0 : }
115 :
116 202 : void KeepChar()
117 : {
118 202 : KeepChars(1);
119 202 : }
120 :
121 21 : void TakeFrom(gfxSkipChars* aSkipChars)
122 : {
123 21 : mRanges.SwapElements(aSkipChars->mRanges);
124 21 : mCharCount = aSkipChars->mCharCount;
125 21 : aSkipChars->mCharCount = 0;
126 21 : }
127 :
128 289 : int32_t GetOriginalCharCount() const
129 : {
130 289 : return mCharCount;
131 : }
132 :
133 0 : const SkippedRange& LastRange() const
134 : {
135 : // this is only valid if mRanges is non-empty; no assertion here
136 : // because nsTArray will already assert if we abuse it
137 0 : return mRanges[mRanges.Length() - 1];
138 : }
139 :
140 : friend class gfxSkipCharsIterator;
141 :
142 : private:
143 : nsTArray<SkippedRange> mRanges;
144 : uint32_t mCharCount;
145 : };
146 :
147 : /**
148 : * A gfxSkipCharsIterator represents a position in the original string. It lets you
149 : * map efficiently to and from positions in the string after skipped characters
150 : * have been removed. You can also specify an offset that is added to all
151 : * incoming original string offsets and subtracted from all outgoing original
152 : * string offsets --- useful when the gfxSkipChars corresponds to something
153 : * offset from the original DOM coordinates, which it often does for gfxTextRuns.
154 : *
155 : * The current positions (in both the original and skipped strings) are
156 : * always constrained to be >= 0 and <= the string length. When the position
157 : * is equal to the string length, it is at the end of the string. The current
158 : * positions do not include any aOriginalStringToSkipCharsOffset.
159 : *
160 : * When the position in the original string corresponds to a skipped character,
161 : * the skipped-characters offset is the offset of the next unskipped character,
162 : * or the skipped-characters string length if there is no next unskipped character.
163 : */
164 : class gfxSkipCharsIterator
165 : {
166 : public:
167 : /**
168 : * @param aOriginalStringToSkipCharsOffset add this to all incoming and
169 : * outgoing original string offsets
170 : */
171 104 : gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
172 : int32_t aOriginalStringToSkipCharsOffset,
173 : int32_t aOriginalStringOffset)
174 104 : : mSkipChars(&aSkipChars),
175 : mOriginalStringOffset(0),
176 : mSkippedStringOffset(0),
177 : mCurrentRangeIndex(-1),
178 104 : mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset)
179 : {
180 104 : SetOriginalOffset(aOriginalStringOffset);
181 104 : }
182 :
183 63 : explicit gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
184 : int32_t aOriginalStringToSkipCharsOffset = 0)
185 63 : : mSkipChars(&aSkipChars),
186 : mOriginalStringOffset(0),
187 : mSkippedStringOffset(0),
188 63 : mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset)
189 : {
190 63 : mCurrentRangeIndex =
191 63 : mSkipChars->mRanges.IsEmpty() ||
192 126 : mSkipChars->mRanges[0].Start() > 0 ? -1 : 0;
193 63 : }
194 :
195 284 : gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator)
196 284 : : mSkipChars(aIterator.mSkipChars),
197 284 : mOriginalStringOffset(aIterator.mOriginalStringOffset),
198 284 : mSkippedStringOffset(aIterator.mSkippedStringOffset),
199 284 : mCurrentRangeIndex(aIterator.mCurrentRangeIndex),
200 1136 : mOriginalStringToSkipCharsOffset(aIterator.mOriginalStringToSkipCharsOffset)
201 284 : { }
202 :
203 : /**
204 : * The empty constructor creates an object that is useless until it is assigned.
205 : */
206 0 : gfxSkipCharsIterator()
207 0 : : mSkipChars(nullptr)
208 0 : { }
209 :
210 : /**
211 : * Return true if this iterator is properly initialized and usable.
212 : */
213 62 : bool IsInitialized()
214 : {
215 62 : return mSkipChars != nullptr;
216 : }
217 :
218 : /**
219 : * Set the iterator to aOriginalStringOffset in the original string.
220 : * This can efficiently move forward or backward from the current position.
221 : * aOriginalStringOffset is clamped to [0,originalStringLength].
222 : */
223 : void SetOriginalOffset(int32_t aOriginalStringOffset);
224 :
225 : /**
226 : * Set the iterator to aSkippedStringOffset in the skipped string.
227 : * This can efficiently move forward or backward from the current position.
228 : * aSkippedStringOffset is clamped to [0,skippedStringLength].
229 : */
230 : void SetSkippedOffset(uint32_t aSkippedStringOffset);
231 :
232 69 : uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset)
233 : {
234 69 : SetOriginalOffset(aOriginalStringOffset);
235 69 : return GetSkippedOffset();
236 : }
237 :
238 17 : int32_t ConvertSkippedToOriginal(uint32_t aSkippedStringOffset)
239 : {
240 17 : SetSkippedOffset(aSkippedStringOffset);
241 17 : return GetOriginalOffset();
242 : }
243 :
244 : /**
245 : * Test if the character at the current position in the original string
246 : * is skipped or not. If aRunLength is non-null, then *aRunLength is set
247 : * to a number of characters all of which are either skipped or not, starting
248 : * at this character. When the current position is at the end of the original
249 : * string, we return true and *aRunLength is set to zero.
250 : */
251 : bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const;
252 :
253 261 : void AdvanceOriginal(int32_t aDelta)
254 : {
255 261 : SetOriginalOffset(GetOriginalOffset() + aDelta);
256 261 : }
257 :
258 4 : void AdvanceSkipped(int32_t aDelta)
259 : {
260 4 : SetSkippedOffset(GetSkippedOffset() + aDelta);
261 4 : }
262 :
263 : /**
264 : * @return the offset within the original string
265 : */
266 755 : int32_t GetOriginalOffset() const
267 : {
268 755 : return mOriginalStringOffset - mOriginalStringToSkipCharsOffset;
269 : }
270 :
271 : /**
272 : * @return the offset within the skipped string corresponding to the
273 : * current position in the original string. If the current position
274 : * in the original string is a character that is skipped, then we return
275 : * the position corresponding to the first non-skipped character in the
276 : * original string after the current position, or the length of the skipped
277 : * string if there is no such character.
278 : */
279 313 : uint32_t GetSkippedOffset() const
280 : {
281 313 : return mSkippedStringOffset;
282 : }
283 :
284 247 : int32_t GetOriginalEnd() const
285 : {
286 247 : return mSkipChars->GetOriginalCharCount() -
287 247 : mOriginalStringToSkipCharsOffset;
288 : }
289 :
290 : private:
291 : const gfxSkipChars* mSkipChars;
292 :
293 : // Current position
294 : int32_t mOriginalStringOffset;
295 : uint32_t mSkippedStringOffset;
296 :
297 : // Index of the last skippedRange that precedes or contains the current
298 : // position in the original string.
299 : // If index == -1 then we are before the first skipped char.
300 : int32_t mCurrentRangeIndex;
301 :
302 : // This offset is added to map from "skipped+unskipped characters in
303 : // the original DOM string" character space to "skipped+unskipped
304 : // characters in the textrun's gfxSkipChars" character space
305 : int32_t mOriginalStringToSkipCharsOffset;
306 : };
307 :
308 : #endif /*GFX_SKIP_CHARS_H*/
|