/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*- * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #ifndef GFX_SKIP_CHARS_H #define GFX_SKIP_CHARS_H #include "nsTArray.h" /* * gfxSkipChars is a data structure representing a list of characters that * have been skipped. The initial string is called the "original string" * and after skipping some characters, the result is called the "skipped string". * gfxSkipChars provides efficient ways to translate between offsets in the * original string and the skipped string. It is used by textrun code to keep * track of offsets before and after text transformations such as whitespace * compression and control code deletion. */ /** * The gfxSkipChars is represented as a sorted array of skipped ranges. * * A freshly-created gfxSkipChars means "all chars kept". */ class gfxSkipChars { friend struct SkippedRangeStartComparator; friend struct SkippedRangeOffsetComparator; private: class SkippedRange { public: SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta) : mOffset(aOffset), mLength(aLength), mDelta(aDelta) { } uint32_t Start() const { return mOffset; } uint32_t End() const { return mOffset + mLength; } uint32_t Length() const { return mLength; } uint32_t SkippedOffset() const { return mOffset - mDelta; } uint32_t Delta() const { return mDelta; } uint32_t NextDelta() const { return mDelta + mLength; } void Extend(uint32_t aChars) { mLength += aChars; } private: uint32_t mOffset; // original-string offset at which we want to skip uint32_t mLength; // number of skipped chars at this offset uint32_t mDelta; // sum of lengths of preceding skipped-ranges }; public: gfxSkipChars() : mCharCount(0) { } void SkipChars(uint32_t aChars) { NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow"); uint32_t rangeCount = mRanges.Length(); uint32_t delta = 0; if (rangeCount > 0) { SkippedRange& lastRange = mRanges[rangeCount - 1]; if (lastRange.End() == mCharCount) { lastRange.Extend(aChars); mCharCount += aChars; return; } delta = lastRange.NextDelta(); } mRanges.AppendElement(SkippedRange(mCharCount, aChars, delta)); mCharCount += aChars; } void KeepChars(uint32_t aChars) { NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow"); mCharCount += aChars; } void SkipChar() { SkipChars(1); } void KeepChar() { KeepChars(1); } void TakeFrom(gfxSkipChars* aSkipChars) { mRanges.SwapElements(aSkipChars->mRanges); mCharCount = aSkipChars->mCharCount; aSkipChars->mCharCount = 0; } int32_t GetOriginalCharCount() const { return mCharCount; } const SkippedRange& LastRange() const { // this is only valid if mRanges is non-empty; no assertion here // because nsTArray will already assert if we abuse it return mRanges[mRanges.Length() - 1]; } friend class gfxSkipCharsIterator; private: nsTArray<SkippedRange> mRanges; uint32_t mCharCount; }; /** * A gfxSkipCharsIterator represents a position in the original string. It lets you * map efficiently to and from positions in the string after skipped characters * have been removed. You can also specify an offset that is added to all * incoming original string offsets and subtracted from all outgoing original * string offsets --- useful when the gfxSkipChars corresponds to something * offset from the original DOM coordinates, which it often does for gfxTextRuns. * * The current positions (in both the original and skipped strings) are * always constrained to be >= 0 and <= the string length. When the position * is equal to the string length, it is at the end of the string. The current * positions do not include any aOriginalStringToSkipCharsOffset. * * When the position in the original string corresponds to a skipped character, * the skipped-characters offset is the offset of the next unskipped character, * or the skipped-characters string length if there is no next unskipped character. */ class gfxSkipCharsIterator { public: /** * @param aOriginalStringToSkipCharsOffset add this to all incoming and * outgoing original string offsets */ gfxSkipCharsIterator(const gfxSkipChars& aSkipChars, int32_t aOriginalStringToSkipCharsOffset, int32_t aOriginalStringOffset) : mSkipChars(&aSkipChars), mOriginalStringOffset(0), mSkippedStringOffset(0), mCurrentRangeIndex(-1), mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) { SetOriginalOffset(aOriginalStringOffset); } explicit gfxSkipCharsIterator(const gfxSkipChars& aSkipChars, int32_t aOriginalStringToSkipCharsOffset = 0) : mSkipChars(&aSkipChars), mOriginalStringOffset(0), mSkippedStringOffset(0), mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) { mCurrentRangeIndex = mSkipChars->mRanges.IsEmpty() || mSkipChars->mRanges[0].Start() > 0 ? -1 : 0; } gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator) : mSkipChars(aIterator.mSkipChars), mOriginalStringOffset(aIterator.mOriginalStringOffset), mSkippedStringOffset(aIterator.mSkippedStringOffset), mCurrentRangeIndex(aIterator.mCurrentRangeIndex), mOriginalStringToSkipCharsOffset(aIterator.mOriginalStringToSkipCharsOffset) { } /** * The empty constructor creates an object that is useless until it is assigned. */ gfxSkipCharsIterator() : mSkipChars(nullptr) { } /** * Return true if this iterator is properly initialized and usable. */ bool IsInitialized() { return mSkipChars != nullptr; } /** * Set the iterator to aOriginalStringOffset in the original string. * This can efficiently move forward or backward from the current position. * aOriginalStringOffset is clamped to [0,originalStringLength]. */ void SetOriginalOffset(int32_t aOriginalStringOffset); /** * Set the iterator to aSkippedStringOffset in the skipped string. * This can efficiently move forward or backward from the current position. * aSkippedStringOffset is clamped to [0,skippedStringLength]. */ void SetSkippedOffset(uint32_t aSkippedStringOffset); uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset) { SetOriginalOffset(aOriginalStringOffset); return GetSkippedOffset(); } int32_t ConvertSkippedToOriginal(uint32_t aSkippedStringOffset) { SetSkippedOffset(aSkippedStringOffset); return GetOriginalOffset(); } /** * Test if the character at the current position in the original string * is skipped or not. If aRunLength is non-null, then *aRunLength is set * to a number of characters all of which are either skipped or not, starting * at this character. When the current position is at the end of the original * string, we return true and *aRunLength is set to zero. */ bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const; void AdvanceOriginal(int32_t aDelta) { SetOriginalOffset(GetOriginalOffset() + aDelta); } void AdvanceSkipped(int32_t aDelta) { SetSkippedOffset(GetSkippedOffset() + aDelta); } /** * @return the offset within the original string */ int32_t GetOriginalOffset() const { return mOriginalStringOffset - mOriginalStringToSkipCharsOffset; } /** * @return the offset within the skipped string corresponding to the * current position in the original string. If the current position * in the original string is a character that is skipped, then we return * the position corresponding to the first non-skipped character in the * original string after the current position, or the length of the skipped * string if there is no such character. */ uint32_t GetSkippedOffset() const { return mSkippedStringOffset; } int32_t GetOriginalEnd() const { return mSkipChars->GetOriginalCharCount() - mOriginalStringToSkipCharsOffset; } private: const gfxSkipChars* mSkipChars; // Current position int32_t mOriginalStringOffset; uint32_t mSkippedStringOffset; // Index of the last skippedRange that precedes or contains the current // position in the original string. // If index == -1 then we are before the first skipped char. int32_t mCurrentRangeIndex; // This offset is added to map from "skipped+unskipped characters in // the original DOM string" character space to "skipped+unskipped // characters in the textrun's gfxSkipChars" character space int32_t mOriginalStringToSkipCharsOffset; }; #endif /*GFX_SKIP_CHARS_H*/