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 15 * string". gfxSkipChars provides efficient ways to translate between offsets in 16 * the original string and the skipped string. It is used by textrun code to 17 * keep track of offsets before and after text transformations such as 18 * whitespace 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 class gfxSkipChars { 27 friend struct SkippedRangeStartComparator; 28 friend struct SkippedRangeOffsetComparator; 29 30 private: 31 class SkippedRange { 32 public: SkippedRange(uint32_t aOffset,uint32_t aLength,uint32_t aDelta)33 SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta) 34 : mOffset(aOffset), mLength(aLength), mDelta(aDelta) {} 35 Start()36 uint32_t Start() const { return mOffset; } 37 End()38 uint32_t End() const { return mOffset + mLength; } 39 Length()40 uint32_t Length() const { return mLength; } 41 SkippedOffset()42 uint32_t SkippedOffset() const { return mOffset - mDelta; } 43 Delta()44 uint32_t Delta() const { return mDelta; } 45 NextDelta()46 uint32_t NextDelta() const { return mDelta + mLength; } 47 Extend(uint32_t aChars)48 void Extend(uint32_t aChars) { mLength += aChars; } 49 50 private: 51 uint32_t mOffset; // original-string offset at which we want to skip 52 uint32_t mLength; // number of skipped chars at this offset 53 uint32_t mDelta; // sum of lengths of preceding skipped-ranges 54 }; 55 56 public: gfxSkipChars()57 gfxSkipChars() : mCharCount(0) {} 58 SkipChars(uint32_t aChars)59 void SkipChars(uint32_t aChars) { 60 NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow"); 61 uint32_t rangeCount = mRanges.Length(); 62 uint32_t delta = 0; 63 if (rangeCount > 0) { 64 SkippedRange& lastRange = mRanges[rangeCount - 1]; 65 if (lastRange.End() == mCharCount) { 66 lastRange.Extend(aChars); 67 mCharCount += aChars; 68 return; 69 } 70 delta = lastRange.NextDelta(); 71 } 72 mRanges.AppendElement(SkippedRange(mCharCount, aChars, delta)); 73 mCharCount += aChars; 74 } 75 KeepChars(uint32_t aChars)76 void KeepChars(uint32_t aChars) { 77 NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow"); 78 mCharCount += aChars; 79 } 80 SkipChar()81 void SkipChar() { SkipChars(1); } 82 KeepChar()83 void KeepChar() { KeepChars(1); } 84 TakeFrom(gfxSkipChars * aSkipChars)85 void TakeFrom(gfxSkipChars* aSkipChars) { 86 mRanges.SwapElements(aSkipChars->mRanges); 87 mCharCount = aSkipChars->mCharCount; 88 aSkipChars->mCharCount = 0; 89 } 90 GetOriginalCharCount()91 int32_t GetOriginalCharCount() const { return mCharCount; } 92 LastRange()93 const SkippedRange& LastRange() const { 94 // this is only valid if mRanges is non-empty; no assertion here 95 // because nsTArray will already assert if we abuse it 96 return mRanges[mRanges.Length() - 1]; 97 } 98 99 friend class gfxSkipCharsIterator; 100 101 private: 102 nsTArray<SkippedRange> mRanges; 103 uint32_t mCharCount; 104 }; 105 106 /** 107 * A gfxSkipCharsIterator represents a position in the original string. It lets 108 * you map efficiently to and from positions in the string after skipped 109 * characters have been removed. You can also specify an offset that is added to 110 * all incoming original string offsets and subtracted from all outgoing 111 * original string offsets --- useful when the gfxSkipChars corresponds to 112 * something offset from the original DOM coordinates, which it often does for 113 * gfxTextRuns. 114 * 115 * The current positions (in both the original and skipped strings) are 116 * always constrained to be >= 0 and <= the string length. When the position 117 * is equal to the string length, it is at the end of the string. The current 118 * positions do not include any aOriginalStringToSkipCharsOffset. 119 * 120 * When the position in the original string corresponds to a skipped character, 121 * the skipped-characters offset is the offset of the next unskipped character, 122 * or the skipped-characters string length if there is no next unskipped 123 * character. 124 */ 125 class gfxSkipCharsIterator { 126 public: 127 /** 128 * @param aOriginalStringToSkipCharsOffset add this to all incoming and 129 * outgoing original string offsets 130 */ gfxSkipCharsIterator(const gfxSkipChars & aSkipChars,int32_t aOriginalStringToSkipCharsOffset,int32_t aOriginalStringOffset)131 gfxSkipCharsIterator(const gfxSkipChars& aSkipChars, 132 int32_t aOriginalStringToSkipCharsOffset, 133 int32_t aOriginalStringOffset) 134 : mSkipChars(&aSkipChars), 135 mOriginalStringOffset(0), 136 mSkippedStringOffset(0), 137 mCurrentRangeIndex(-1), 138 mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) { 139 SetOriginalOffset(aOriginalStringOffset); 140 } 141 142 explicit gfxSkipCharsIterator(const gfxSkipChars& aSkipChars, 143 int32_t aOriginalStringToSkipCharsOffset = 0) 144 : mSkipChars(&aSkipChars), 145 mOriginalStringOffset(0), 146 mSkippedStringOffset(0), 147 mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) { 148 mCurrentRangeIndex = 149 mSkipChars->mRanges.IsEmpty() || mSkipChars->mRanges[0].Start() > 0 ? -1 150 : 0; 151 } 152 gfxSkipCharsIterator(const gfxSkipCharsIterator & aIterator)153 gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator) 154 : mSkipChars(aIterator.mSkipChars), 155 mOriginalStringOffset(aIterator.mOriginalStringOffset), 156 mSkippedStringOffset(aIterator.mSkippedStringOffset), 157 mCurrentRangeIndex(aIterator.mCurrentRangeIndex), 158 mOriginalStringToSkipCharsOffset( 159 aIterator.mOriginalStringToSkipCharsOffset) {} 160 161 /** 162 * The empty constructor creates an object that is useless until it is 163 * assigned. 164 */ gfxSkipCharsIterator()165 gfxSkipCharsIterator() : mSkipChars(nullptr) {} 166 167 /** 168 * Return true if this iterator is properly initialized and usable. 169 */ IsInitialized()170 bool IsInitialized() { return mSkipChars != nullptr; } 171 172 /** 173 * Set the iterator to aOriginalStringOffset in the original string. 174 * This can efficiently move forward or backward from the current position. 175 * aOriginalStringOffset is clamped to [0,originalStringLength]. 176 */ 177 void SetOriginalOffset(int32_t aOriginalStringOffset); 178 179 /** 180 * Set the iterator to aSkippedStringOffset in the skipped string. 181 * This can efficiently move forward or backward from the current position. 182 * aSkippedStringOffset is clamped to [0,skippedStringLength]. 183 */ 184 void SetSkippedOffset(uint32_t aSkippedStringOffset); 185 ConvertOriginalToSkipped(int32_t aOriginalStringOffset)186 uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset) { 187 SetOriginalOffset(aOriginalStringOffset); 188 return GetSkippedOffset(); 189 } 190 ConvertSkippedToOriginal(uint32_t aSkippedStringOffset)191 int32_t ConvertSkippedToOriginal(uint32_t aSkippedStringOffset) { 192 SetSkippedOffset(aSkippedStringOffset); 193 return GetOriginalOffset(); 194 } 195 196 /** 197 * Test if the character at the current position in the original string 198 * is skipped or not. If aRunLength is non-null, then *aRunLength is set 199 * to a number of characters all of which are either skipped or not, starting 200 * at this character. When the current position is at the end of the original 201 * string, we return true and *aRunLength is set to zero. 202 */ 203 bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const; 204 AdvanceOriginal(int32_t aDelta)205 void AdvanceOriginal(int32_t aDelta) { 206 SetOriginalOffset(GetOriginalOffset() + aDelta); 207 } 208 AdvanceSkipped(int32_t aDelta)209 void AdvanceSkipped(int32_t aDelta) { 210 SetSkippedOffset(GetSkippedOffset() + aDelta); 211 } 212 213 /** 214 * @return the offset within the original string 215 */ GetOriginalOffset()216 int32_t GetOriginalOffset() const { 217 return mOriginalStringOffset - mOriginalStringToSkipCharsOffset; 218 } 219 220 /** 221 * @return the offset within the skipped string corresponding to the 222 * current position in the original string. If the current position 223 * in the original string is a character that is skipped, then we return 224 * the position corresponding to the first non-skipped character in the 225 * original string after the current position, or the length of the skipped 226 * string if there is no such character. 227 */ GetSkippedOffset()228 uint32_t GetSkippedOffset() const { return mSkippedStringOffset; } 229 GetOriginalEnd()230 int32_t GetOriginalEnd() const { 231 return mSkipChars->GetOriginalCharCount() - 232 mOriginalStringToSkipCharsOffset; 233 } 234 235 private: 236 const gfxSkipChars* mSkipChars; 237 238 // Current position 239 int32_t mOriginalStringOffset; 240 uint32_t mSkippedStringOffset; 241 242 // Index of the last skippedRange that precedes or contains the current 243 // position in the original string. 244 // If index == -1 then we are before the first skipped char. 245 int32_t mCurrentRangeIndex; 246 247 // This offset is added to map from "skipped+unskipped characters in 248 // the original DOM string" character space to "skipped+unskipped 249 // characters in the textrun's gfxSkipChars" character space 250 int32_t mOriginalStringToSkipCharsOffset; 251 }; 252 253 #endif /*GFX_SKIP_CHARS_H*/ 254