gfx/thebes/gfxSkipChars.h

   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 "nsAutoPtr.h"
  10 #include "nsTArray.h"
  11 #include "gfxTypes.h"
  12
  13 /*
  14  * gfxSkipChars is a data structure representing a list of characters that
  15  * have been skipped. The initial string is called the "original string"
  16  * and after skipping some characters, the result is called the "skipped string".
  17  * gfxSkipChars provides efficient ways to translate between offsets in the
  18  * original string and the skipped string. It is used by textrun code to keep
  19  * track of offsets before and after text transformations such as whitespace
  20  * compression and control code deletion.
  21  */
  22
  23 /**
  24  * gfxSkipCharsBuilder is a helper class that accumulates a list of (skip, keep)
  25  * commands and can eventually be used to construct a real gfxSkipChars.
  26  * gfxSkipCharsBuilder objects are quite large so don't keep these around.
  27  * On the positive side, the Skip/KeepChar(s) methods are very efficient,
  28  * especially when you have runs of all-kept or all-skipped characters.
  29  *
  30  * mBuffer is an array of bytes; even numbered bytes represent characters kept,
  31  * odd numbered bytes represent characters skipped. After those characters
  32  * are accounted for, we have mRunCharCount characters which are kept or
  33  * skipped depending on the value of mRunSkipped.
  34  *
  35  * mCharCount is the sum of counts of all skipped and kept characters, i.e.,
  36  * the length of the original string.
  37  */
  38 class THEBES_API gfxSkipCharsBuilder {
  39 public:
  40     gfxSkipCharsBuilder() :
  41         mCharCount(0), mRunCharCount(0), mRunSkipped(false), mInErrorState(false)
  42     {}
  43
  44     void SkipChars(uint32_t aChars) {
  45         DoChars(aChars, true);
  46     }
  47     void KeepChars(uint32_t aChars) {
  48         DoChars(aChars, false);
  49     }
  50     void SkipChar() {
  51         SkipChars(1);
  52     }
  53     void KeepChar() {
  54         KeepChars(1);
  55     }
  56     void DoChars(uint32_t aChars, bool aSkipped) {
  57         if (aSkipped != mRunSkipped && aChars > 0) {
  58             FlushRun();
  59         }
  60         NS_ASSERTION(mRunCharCount + aChars > mRunCharCount,
  61                      "Character count overflow");
  62         mRunCharCount += aChars;
  63     }
  64
  65     bool IsOK() { return !mInErrorState; }
  66
  67     uint32_t GetCharCount() { return mCharCount + mRunCharCount; }
  68     bool GetAllCharsKept() { return mBuffer.Length() == 0; }
  69
  70     friend class gfxSkipChars;
  71
  72 private:
  73     typedef AutoFallibleTArray<uint8_t,256> Buffer;
  74
  75     /**
  76      * Moves mRunCharCount/mRunSkipped to the buffer (updating mCharCount),
  77      * sets mRunCharCount to zero and toggles mRunSkipped.
  78      */
  79     void FlushRun();
  80
  81     Buffer       mBuffer;
  82     uint32_t     mCharCount;
  83     uint32_t     mRunCharCount;
  84     bool mRunSkipped; // == mBuffer.Length()&1
  85     bool mInErrorState;
  86 };
  87
  88 /**
  89  * The gfxSkipChars list is represented as a list of bytes of the form
  90  * [chars to keep, chars to skip, chars to keep, chars to skip, ...]
  91  * In the special case where all chars are to be kept, the list is length
  92  * zero.
  93  *
  94  * A freshly-created gfxSkipChars means "all chars kept".
  95  */
  96 class THEBES_API gfxSkipChars {
  97 public:
  98     gfxSkipChars() : mListLength(0), mCharCount(0) {}
  99
 100     void TakeFrom(gfxSkipChars* aSkipChars) {
 101         mList = aSkipChars->mList.forget();
 102         mListLength = aSkipChars->mListLength;
 103         mCharCount = aSkipChars->mCharCount;
 104         aSkipChars->mCharCount = 0;
 105         aSkipChars->mListLength = 0;
 106         BuildShortcuts();
 107     }
 108
 109     void TakeFrom(gfxSkipCharsBuilder* aSkipCharsBuilder) {
 110         if (!aSkipCharsBuilder->mBuffer.Length()) {
 111             NS_ASSERTION(!aSkipCharsBuilder->mRunSkipped, "out of sync");
 112             // all characters kept
 113             mCharCount = aSkipCharsBuilder->mRunCharCount;
 114             mList = nullptr;
 115             mListLength = 0;
 116         } else {
 117             aSkipCharsBuilder->FlushRun();
 118             mCharCount = aSkipCharsBuilder->mCharCount;
 119             mList = new uint8_t[aSkipCharsBuilder->mBuffer.Length()];
 120             if (!mList) {
 121                 mListLength = 0;
 122             } else {
 123                 mListLength = aSkipCharsBuilder->mBuffer.Length();
 124                 memcpy(mList, aSkipCharsBuilder->mBuffer.Elements(), mListLength);
 125             }
 126         }
 127         aSkipCharsBuilder->mBuffer.Clear();
 128         aSkipCharsBuilder->mCharCount = 0;
 129         aSkipCharsBuilder->mRunCharCount = 0;
 130         aSkipCharsBuilder->mRunSkipped = false;
 131         BuildShortcuts();
 132     }
 133
 134     void SetAllKeep(uint32_t aLength) {
 135         mCharCount = aLength;
 136         mList = nullptr;
 137         mListLength = 0;
 138     }
 139
 140     int32_t GetOriginalCharCount() const { return mCharCount; }
 141
 142     friend class gfxSkipCharsIterator;
 143
 144 private:
 145     struct Shortcut {
 146         uint32_t mListPrefixLength;
 147         uint32_t mListPrefixCharCount;
 148         uint32_t mListPrefixKeepCharCount;
 149
 150         Shortcut() {}
 151         Shortcut(uint32_t aListPrefixLength, uint32_t aListPrefixCharCount,
 152                  uint32_t aListPrefixKeepCharCount) :
 153             mListPrefixLength(aListPrefixLength),
 154             mListPrefixCharCount(aListPrefixCharCount),
 155             mListPrefixKeepCharCount(aListPrefixKeepCharCount) {}
 156     };
 157
 158     void BuildShortcuts();
 159
 160     nsAutoArrayPtr<uint8_t>  mList;
 161     nsAutoArrayPtr<Shortcut> mShortcuts;
 162     uint32_t                 mListLength;
 163     uint32_t                 mCharCount;
 164 };
 165
 166 /**
 167  * A gfxSkipCharsIterator represents a position in the original string. It lets you
 168  * map efficiently to and from positions in the string after skipped characters
 169  * have been removed. You can also specify an offset that is added to all
 170  * incoming original string offsets and subtracted from all outgoing original
 171  * string offsets --- useful when the gfxSkipChars corresponds to something
 172  * offset from the original DOM coordinates, which it often does for gfxTextRuns.
 173  *
 174  * The current positions (in both the original and skipped strings) are
 175  * always constrained to be >= 0 and <= the string length. When the position
 176  * is equal to the string length, it is at the end of the string. The current
 177  * positions do not include any aOriginalStringToSkipCharsOffset.
 178  *
 179  * When the position in the original string corresponds to a skipped character,
 180  * the skipped-characters offset is the offset of the next unskipped character,
 181  * or the skipped-characters string length if there is no next unskipped character.
 182  */
 183 class THEBES_API gfxSkipCharsIterator {
 184 public:
 185     /**
 186      * @param aOriginalStringToSkipCharsOffset add this to all incoming and
 187      * outgoing original string offsets
 188      */
 189     gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
 190                          int32_t aOriginalStringToSkipCharsOffset,
 191                          int32_t aOriginalStringOffset)
 192         : mSkipChars(&aSkipChars),
 193           mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset),
 194           mListPrefixLength(0), mListPrefixCharCount(0), mListPrefixKeepCharCount(0) {
 195           SetOriginalOffset(aOriginalStringOffset);
 196     }
 197
 198     gfxSkipCharsIterator(const gfxSkipChars& aSkipChars,
 199                          int32_t aOriginalStringToSkipCharsOffset = 0)
 200         : mSkipChars(&aSkipChars),
 201           mOriginalStringOffset(0), mSkippedStringOffset(0),
 202           mOriginalStringToSkipCharsOffset(aOriginalStringToSkipCharsOffset),
 203           mListPrefixLength(0), mListPrefixCharCount(0), mListPrefixKeepCharCount(0) {
 204     }
 205
 206     gfxSkipCharsIterator(const gfxSkipCharsIterator& aIterator)
 207         : mSkipChars(aIterator.mSkipChars),
 208           mOriginalStringOffset(aIterator.mOriginalStringOffset),
 209           mSkippedStringOffset(aIterator.mSkippedStringOffset),
 210           mOriginalStringToSkipCharsOffset(aIterator.mOriginalStringToSkipCharsOffset),
 211           mListPrefixLength(aIterator.mListPrefixLength),
 212           mListPrefixCharCount(aIterator.mListPrefixCharCount),
 213           mListPrefixKeepCharCount(aIterator.mListPrefixKeepCharCount)
 214     {}
 215
 216     /**
 217      * The empty constructor creates an object that is useless until it is assigned.
 218      */
 219     gfxSkipCharsIterator() : mSkipChars(nullptr) {}
 220
 221     /**
 222      * Return true if this iterator is properly initialized and usable.
 223      */
 224     bool IsInitialized() { return mSkipChars != nullptr; }
 225
 226     /**
 227      * Set the iterator to aOriginalStringOffset in the original string.
 228      * This can efficiently move forward or backward from the current position.
 229      * aOriginalStringOffset is clamped to [0,originalStringLength].
 230      */
 231     void SetOriginalOffset(int32_t aOriginalStringOffset) {
 232         SetOffsets(aOriginalStringOffset + mOriginalStringToSkipCharsOffset, true);
 233     }
 234
 235     /**
 236      * Set the iterator to aSkippedStringOffset in the skipped string.
 237      * This can efficiently move forward or backward from the current position.
 238      * aSkippedStringOffset is clamped to [0,skippedStringLength].
 239      */
 240     void SetSkippedOffset(uint32_t aSkippedStringOffset) {
 241         SetOffsets(aSkippedStringOffset, false);
 242     }
 243
 244     uint32_t ConvertOriginalToSkipped(int32_t aOriginalStringOffset) {
 245         SetOriginalOffset(aOriginalStringOffset);
 246         return GetSkippedOffset();
 247     }
 248     uint32_t ConvertSkippedToOriginal(int32_t aSkippedStringOffset) {
 249         SetSkippedOffset(aSkippedStringOffset);
 250         return GetOriginalOffset();
 251     }
 252
 253     /**
 254      * Test if the character at the current position in the original string
 255      * is skipped or not. If aRunLength is non-null, then *aRunLength is set
 256      * to a number of characters all of which are either skipped or not, starting
 257      * at this character. When the current position is at the end of the original
 258      * string, we return true and *aRunLength is set to zero.
 259      */
 260     bool IsOriginalCharSkipped(int32_t* aRunLength = nullptr) const;
 261
 262     void AdvanceOriginal(int32_t aDelta) {
 263         SetOffsets(mOriginalStringOffset + aDelta, true);
 264     }
 265     void AdvanceSkipped(int32_t aDelta) {
 266         SetOffsets(mSkippedStringOffset + aDelta, false);
 267     }
 268
 269     /**
 270      * @return the offset within the original string
 271      */
 272     int32_t GetOriginalOffset() const {
 273         return mOriginalStringOffset - mOriginalStringToSkipCharsOffset;
 274     }
 275     /**
 276      * @return the offset within the skipped string corresponding to the
 277      * current position in the original string. If the current position
 278      * in the original string is a character that is skipped, then we return
 279      * the position corresponding to the first non-skipped character in the
 280      * original string after the current position, or the length of the skipped
 281      * string if there is no such character.
 282      */
 283     uint32_t GetSkippedOffset() const { return mSkippedStringOffset; }
 284
 285     int32_t GetOriginalEnd() const {
 286         return mSkipChars->GetOriginalCharCount() -
 287             mOriginalStringToSkipCharsOffset;
 288     }
 289
 290 private:
 291     void SetOffsets(uint32_t aOffset, bool aInOriginalString);
 292
 293     const gfxSkipChars* mSkipChars;
 294     int32_t mOriginalStringOffset;
 295     uint32_t mSkippedStringOffset;
 296
 297     // This offset is added to map from "skipped+unskipped characters in
 298     // the original DOM string" character space to "skipped+unskipped
 299     // characters in the textrun's gfxSkipChars" character space
 300     int32_t mOriginalStringToSkipCharsOffset;
 301
 302     /*
 303      * This is used to speed up cursor-style traversal. The invariant is that
 304      * the first mListPrefixLength bytes of mSkipChars.mList sum to
 305      * mListPrefixCharCount, and the even-indexed bytes in that prefix sum to
 306      * mListPrefixKeepCharCount.
 307      * Also, 0 <= mListPrefixLength < mSkipChars.mListLength, or else
 308      * mSkipChars.mListLength is zero.
 309      * Also, mListPrefixCharCount <= mOriginalStringOffset (and therefore
 310      * mListPrefixKeepCharCount < mSkippedStringOffset).
 311      */
 312     uint32_t mListPrefixLength;
 313     uint32_t mListPrefixCharCount;
 314     uint32_t mListPrefixKeepCharCount;
 315 };
 316
 317 #endif /*GFX_SKIP_CHARS_H*/