1 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*- 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 = std::move(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 153 gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator) = default; 154 155 /** 156 * The empty constructor creates an object that is useless until it is 157 * assigned. 158 */ gfxSkipCharsIterator()159 gfxSkipCharsIterator() 160 : mSkipChars(nullptr), 161 mOriginalStringOffset(0), 162 mSkippedStringOffset(0), 163 mCurrentRangeIndex(0), 164 mOriginalStringToSkipCharsOffset(0) {} 165 166 /** 167 * Return true if this iterator is properly initialized and usable. 168 */ IsInitialized()169 bool IsInitialized() const { return mSkipChars != nullptr; } 170 171 /** 172 * Set the iterator to aOriginalStringOffset in the original string. 173 * This can efficiently move forward or backward from the current position. 174 * aOriginalStringOffset is clamped to [0,originalStringLength]. 175 */ 176 void SetOriginalOffset(int32_t aOriginalStringOffset); 177 178 /** 179 * Set the iterator to aSkippedStringOffset in the skipped string. 180 * This can efficiently move forward or backward from the current position. 181 * aSkippedStringOffset is clamped to [0,skippedStringLength]. 182 */ 183 void SetSkippedOffset(uint32_t aSkippedStringOffset); 184 ConvertOriginalToSkipped(int32_t aOriginalStringOffset)185 uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset) { 186 SetOriginalOffset(aOriginalStringOffset); 187 return GetSkippedOffset(); 188 } 189 ConvertSkippedToOriginal(uint32_t aSkippedStringOffset)190 int32_t ConvertSkippedToOriginal(uint32_t aSkippedStringOffset) { 191 SetSkippedOffset(aSkippedStringOffset); 192 return GetOriginalOffset(); 193 } 194 195 /** 196 * Test if the character at the current position in the original string 197 * is skipped or not. If aRunLength is non-null, then *aRunLength is set 198 * to a number of characters all of which are either skipped or not, starting 199 * at this character. When the current position is at the end of the original 200 * string, we return true and *aRunLength is set to zero. 201 */ 202 bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const; 203 AdvanceOriginal(int32_t aDelta)204 void AdvanceOriginal(int32_t aDelta) { 205 SetOriginalOffset(GetOriginalOffset() + aDelta); 206 } 207 AdvanceSkipped(int32_t aDelta)208 void AdvanceSkipped(int32_t aDelta) { 209 SetSkippedOffset(GetSkippedOffset() + aDelta); 210 } 211 212 /** 213 * @return the offset within the original string 214 */ GetOriginalOffset()215 int32_t GetOriginalOffset() const { 216 return mOriginalStringOffset - mOriginalStringToSkipCharsOffset; 217 } 218 219 /** 220 * @return the offset within the skipped string corresponding to the 221 * current position in the original string. If the current position 222 * in the original string is a character that is skipped, then we return 223 * the position corresponding to the first non-skipped character in the 224 * original string after the current position, or the length of the skipped 225 * string if there is no such character. 226 */ GetSkippedOffset()227 uint32_t GetSkippedOffset() const { return mSkippedStringOffset; } 228 GetOriginalEnd()229 int32_t GetOriginalEnd() const { 230 return mSkipChars->GetOriginalCharCount() - 231 mOriginalStringToSkipCharsOffset; 232 } 233 234 private: 235 const gfxSkipChars* mSkipChars; 236 237 // Current position 238 int32_t mOriginalStringOffset; 239 uint32_t mSkippedStringOffset; 240 241 // Index of the last skippedRange that precedes or contains the current 242 // position in the original string. 243 // If index == -1 then we are before the first skipped char. 244 int32_t mCurrentRangeIndex; 245 246 // This offset is added to map from "skipped+unskipped characters in 247 // the original DOM string" character space to "skipped+unskipped 248 // characters in the textrun's gfxSkipChars" character space 249 int32_t mOriginalStringToSkipCharsOffset; 250 }; 251 252 #endif /*GFX_SKIP_CHARS_H*/ 253