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