gfx/thebes/gfxSkipChars.h

   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 "mozilla/Attributes.h"
  10 #include "nsTArray.h"
  11
  12 /*
  13  * gfxSkipChars is a data structure representing a list of characters that
  14  * have been skipped. The initial string is called the "original string"
  15  * and after skipping some characters, the result is called the "skipped
  16  * string". gfxSkipChars provides efficient ways to translate between offsets in
  17  * the original string and the skipped string. It is used by textrun code to
  18  * keep track of offsets before and after text transformations such as
  19  * whitespace compression and control code deletion.
  20  */
  21
  22 /**
  23  * The gfxSkipChars is represented as a sorted array of skipped ranges.
  24  *
  25  * A freshly-created gfxSkipChars means "all chars kept".
  26  */
  27 class gfxSkipChars {
  28   friend struct SkippedRangeStartComparator;
  29   friend struct SkippedRangeOffsetComparator;
  30
  31  private:
  32   class SkippedRange {
  33    public:
  34     SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta)
  35         : mOffset(aOffset), mLength(aLength), mDelta(aDelta) {}
  36
  37     uint32_t Start() const { return mOffset; }
  38
  39     uint32_t End() const { return mOffset + mLength; }
  40
  41     uint32_t Length() const { return mLength; }
  42
  43     uint32_t SkippedOffset() const { return mOffset - mDelta; }
  44
  45     uint32_t Delta() const { return mDelta; }
  46
  47     uint32_t NextDelta() const { return mDelta + mLength; }
  48
  49     void Extend(uint32_t aChars) { mLength += aChars; }
  50
  51    private:
  52     uint32_t mOffset;  // original-string offset at which we want to skip
  53     uint32_t mLength;  // number of skipped chars at this offset
  54     uint32_t mDelta;   // sum of lengths of preceding skipped-ranges
  55   };
  56
  57  public:
  58   gfxSkipChars() : mCharCount(0) {}
  59
  60   void SkipChars(uint32_t aChars) {
  61     NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow");
  62     uint32_t rangeCount = mRanges.Length();
  63     uint32_t delta = 0;
  64     if (rangeCount > 0) {
  65       SkippedRange& lastRange = mRanges[rangeCount - 1];
  66       if (lastRange.End() == mCharCount) {
  67         lastRange.Extend(aChars);
  68         mCharCount += aChars;
  69         return;
  70       }
  71       delta = lastRange.NextDelta();
  72     }
  73     mRanges.AppendElement(SkippedRange(mCharCount, aChars, delta));
  74     mCharCount += aChars;
  75   }
  76
  77   void KeepChars(uint32_t aChars) {
  78     NS_ASSERTION(mCharCount + aChars > mCharCount, "Character count overflow");
  79     mCharCount += aChars;
  80   }
  81
  82   void SkipChar() { SkipChars(1); }
  83
  84   void KeepChar() { KeepChars(1); }
  85
  86   void TakeFrom(gfxSkipChars* aSkipChars) {
  87     mRanges = std::move(aSkipChars->mRanges);
  88     mCharCount = aSkipChars->mCharCount;
  89     aSkipChars->mCharCount = 0;
  90   }
  91
  92   int32_t GetOriginalCharCount() const { return mCharCount; }
  93
  94   const SkippedRange& LastRange() const {
  95     // this is only valid if mRanges is non-empty; no assertion here
  96     // because nsTArray will already assert if we abuse it
  97     return mRanges[mRanges.Length() - 1];
  98   }
  99
 100   friend class gfxSkipCharsIterator;
 101
 102  private:
 103   nsTArray<SkippedRange> mRanges;
 104   uint32_t mCharCount;
 105 };
 106
 107 /**
 108  * A gfxSkipCharsIterator represents a position in the original string. It lets
 109  * you map efficiently to and from positions in the string after skipped
 110  * characters have been removed. You can also specify an offset that is added to
 111  * all incoming original string offsets and subtracted from all outgoing
 112  * original string offsets --- useful when the gfxSkipChars corresponds to
 113  * something offset from the original DOM coordinates, which it often does for
 114  * gfxTextRuns.
 115  *
 116  * The current positions (in both the original and skipped strings) are
 117  * always constrained to be >= 0 and <= the string length. When the position
 118  * is equal to the string length, it is at the end of the string. The current
 119  * positions do not include any aOriginalStringToSkipCharsOffset.
 120  *
 121  * When the position in the original string corresponds to a skipped character,
 122  * the skipped-characters offset is the offset of the next unskipped character,
 123  * or the skipped-characters string length if there is no next unskipped
 124  * character.
 125  */
 126 class MOZ_STACK_CLASS gfxSkipCharsIterator {
 127  public:
 128   /**
 129    * @param aOriginalStringToSkipCharsOffset add this to all incoming and
 130    * outgoing original string offsets
 131    */
 132   gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
 133                        int32_t aOriginalStringToSkipCharsOffset,
 134                        int32_t aOriginalStringOffset)
 135       : mSkipChars(&aSkipChars),
 136         mOriginalStringOffset(0),
 137         mSkippedStringOffset(0),
 138         mCurrentRangeIndex(-1),
 139         mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) {
 140     SetOriginalOffset(aOriginalStringOffset);
 141   }
 142
 143   explicit gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
 144                                 int32_t aOriginalStringToSkipCharsOffset = 0)
 145       : mSkipChars(&aSkipChars),
 146         mOriginalStringOffset(0),
 147         mSkippedStringOffset(0),
 148         mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset) {
 149     mCurrentRangeIndex =
 150         mSkipChars->mRanges.IsEmpty() || mSkipChars->mRanges[0].Start() > 0 ? -1
 151                                                                             : 0;
 152   }
 153
 154   gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator) = default;
 155
 156   /**
 157    * The empty constructor creates an object that is useless until it is
 158    * assigned.
 159    */
 160   gfxSkipCharsIterator()
 161       : mSkipChars(nullptr),
 162         mOriginalStringOffset(0),
 163         mSkippedStringOffset(0),
 164         mCurrentRangeIndex(0),
 165         mOriginalStringToSkipCharsOffset(0) {}
 166
 167   /**
 168    * Return true if this iterator is properly initialized and usable.
 169    */
 170   bool IsInitialized() const { 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
 186   uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset) {
 187     SetOriginalOffset(aOriginalStringOffset);
 188     return GetSkippedOffset();
 189   }
 190
 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
 205   void AdvanceOriginal(int32_t aDelta) {
 206     SetOriginalOffset(GetOriginalOffset() + aDelta);
 207   }
 208
 209   void AdvanceSkipped(int32_t aDelta) {
 210     SetSkippedOffset(GetSkippedOffset() + aDelta);
 211   }
 212
 213   /**
 214    * @return the offset within the original string
 215    */
 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    */
 228   uint32_t GetSkippedOffset() const { return mSkippedStringOffset; }
 229
 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*/