dom/base/nsTextFragment.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * A class which represents a fragment of text (eg inside a text
   9  * node); if only codepoints below 256 are used, the text is stored as
  10  * a char*; otherwise the text is stored as a char16_t*
  11  */
  12
  13 #include "nsTextFragment.h"
  14 #include "nsCRT.h"
  15 #include "nsReadableUtils.h"
  16 #include "nsMemory.h"
  17 #include "nsBidiUtils.h"
  18 #include "nsUnicharUtils.h"
  19 #include "mozilla/CheckedInt.h"
  20 #include "mozilla/MemoryReporting.h"
  21 #include "mozilla/SSE.h"
  22 #include "nsTextFragmentImpl.h"
  23 #include <algorithm>
  24
  25 #define TEXTFRAG_WHITE_AFTER_NEWLINE 50
  26 #define TEXTFRAG_MAX_NEWLINES 7
  27
  28 // Static buffer used for common fragments
  29 static char* sSpaceSharedString[TEXTFRAG_MAX_NEWLINES + 1];
  30 static char* sTabSharedString[TEXTFRAG_MAX_NEWLINES + 1];
  31 static char sSingleCharSharedString[256];
  32
  33 using namespace mozilla;
  34
  35 // static
  36 nsresult nsTextFragment::Init() {
  37   // Create whitespace strings
  38   uint32_t i;
  39   for (i = 0; i <= TEXTFRAG_MAX_NEWLINES; ++i) {
  40     sSpaceSharedString[i] = new char[1 + i + TEXTFRAG_WHITE_AFTER_NEWLINE];
  41     sTabSharedString[i] = new char[1 + i + TEXTFRAG_WHITE_AFTER_NEWLINE];
  42     sSpaceSharedString[i][0] = ' ';
  43     sTabSharedString[i][0] = ' ';
  44     uint32_t j;
  45     for (j = 1; j < 1 + i; ++j) {
  46       sSpaceSharedString[i][j] = '\n';
  47       sTabSharedString[i][j] = '\n';
  48     }
  49     for (; j < (1 + i + TEXTFRAG_WHITE_AFTER_NEWLINE); ++j) {
  50       sSpaceSharedString[i][j] = ' ';
  51       sTabSharedString[i][j] = '\t';
  52     }
  53   }
  54
  55   // Create single-char strings
  56   for (i = 0; i < 256; ++i) {
  57     sSingleCharSharedString[i] = i;
  58   }
  59
  60   return NS_OK;
  61 }
  62
  63 // static
  64 void nsTextFragment::Shutdown() {
  65   uint32_t i;
  66   for (i = 0; i <= TEXTFRAG_MAX_NEWLINES; ++i) {
  67     delete[] sSpaceSharedString[i];
  68     delete[] sTabSharedString[i];
  69     sSpaceSharedString[i] = nullptr;
  70     sTabSharedString[i] = nullptr;
  71   }
  72 }
  73
  74 nsTextFragment::~nsTextFragment() {
  75   ReleaseText();
  76   MOZ_COUNT_DTOR(nsTextFragment);
  77 }
  78
  79 void nsTextFragment::ReleaseText() {
  80   if (mState.mIs2b) {
  81     NS_RELEASE(m2b);
  82   } else if (mState.mLength && m1b && mState.mInHeap) {
  83     free(const_cast<char*>(m1b));
  84   }
  85
  86   m1b = nullptr;
  87   mState.mIsBidi = false;
  88
  89   // Set mState.mIs2b, mState.mInHeap, and mState.mLength = 0 with mAllBits;
  90   mAllBits = 0;
  91 }
  92
  93 nsTextFragment& nsTextFragment::operator=(const nsTextFragment& aOther) {
  94   ReleaseText();
  95
  96   if (aOther.mState.mLength) {
  97     if (!aOther.mState.mInHeap) {
  98       MOZ_ASSERT(!aOther.mState.mIs2b);
  99       m1b = aOther.m1b;
 100     } else if (aOther.mState.mIs2b) {
 101       m2b = aOther.m2b;
 102       NS_ADDREF(m2b);
 103     } else {
 104       m1b = static_cast<char*>(malloc(aOther.mState.mLength));
 105       if (m1b) {
 106         memcpy(const_cast<char*>(m1b), aOther.m1b, aOther.mState.mLength);
 107       } else {
 108         // allocate a buffer for a single REPLACEMENT CHARACTER
 109         m2b = nsStringBuffer::Alloc(sizeof(char16_t) * 2).take();
 110         if (!m2b) {
 111           MOZ_CRASH("OOM!");
 112         }
 113         char16_t* data = static_cast<char16_t*>(m2b->Data());
 114         data[0] = 0xFFFD;  // REPLACEMENT CHARACTER
 115         data[1] = char16_t(0);
 116         mState.mIs2b = true;
 117         mState.mInHeap = true;
 118         mState.mLength = 1;
 119         return *this;
 120       }
 121     }
 122
 123     mAllBits = aOther.mAllBits;
 124   }
 125
 126   return *this;
 127 }
 128
 129 static inline int32_t FirstNon8BitUnvectorized(const char16_t* str,
 130                                                const char16_t* end) {
 131   typedef Non8BitParameters<sizeof(size_t)> p;
 132   const size_t mask = p::mask();
 133   const uint32_t alignMask = p::alignMask();
 134   const uint32_t numUnicharsPerWord = p::numUnicharsPerWord();
 135   const int32_t len = end - str;
 136   int32_t i = 0;
 137
 138   // Align ourselves to a word boundary.
 139   int32_t alignLen = std::min(
 140       len, int32_t(((-NS_PTR_TO_INT32(str)) & alignMask) / sizeof(char16_t)));
 141   for (; i < alignLen; i++) {
 142     if (str[i] > 255) return i;
 143   }
 144
 145   // Check one word at a time.
 146   const int32_t wordWalkEnd =
 147       ((len - i) / numUnicharsPerWord) * numUnicharsPerWord;
 148   for (; i < wordWalkEnd; i += numUnicharsPerWord) {
 149     const size_t word = *reinterpret_cast<const size_t*>(str + i);
 150     if (word & mask) return i;
 151   }
 152
 153   // Take care of the remainder one character at a time.
 154   for (; i < len; i++) {
 155     if (str[i] > 255) return i;
 156   }
 157
 158   return -1;
 159 }
 160
 161 #ifdef MOZILLA_MAY_SUPPORT_SSE2
 162 namespace mozilla {
 163 namespace SSE2 {
 164 int32_t FirstNon8Bit(const char16_t* str, const char16_t* end);
 165 }  // namespace SSE2
 166 }  // namespace mozilla
 167 #endif
 168
 169 /*
 170  * This function returns -1 if all characters in str are 8 bit characters.
 171  * Otherwise, it returns a value less than or equal to the index of the first
 172  * non-8bit character in str. For example, if first non-8bit character is at
 173  * position 25, it may return 25, or for example 24, or 16. But it guarantees
 174  * there is no non-8bit character before returned value.
 175  */
 176 static inline int32_t FirstNon8Bit(const char16_t* str, const char16_t* end) {
 177 #ifdef MOZILLA_MAY_SUPPORT_SSE2
 178   if (mozilla::supports_sse2()) {
 179     return mozilla::SSE2::FirstNon8Bit(str, end);
 180   }
 181 #endif
 182
 183   return FirstNon8BitUnvectorized(str, end);
 184 }
 185
 186 bool nsTextFragment::SetTo(const char16_t* aBuffer, int32_t aLength,
 187                            bool aUpdateBidi, bool aForce2b) {
 188   if (aForce2b && mState.mIs2b && !m2b->IsReadonly()) {
 189     uint32_t storageSize = m2b->StorageSize();
 190     uint32_t neededSize = aLength * sizeof(char16_t);
 191     if (!neededSize) {
 192       if (storageSize < AutoStringDefaultStorageSize) {
 193         // If we're storing small enough nsStringBuffer, let's preserve it.
 194
 195         static_cast<char16_t*>(m2b->Data())[0] = char16_t(0);
 196         mState.mLength = 0;
 197         mState.mIsBidi = false;
 198         return true;
 199       }
 200     } else if ((neededSize < storageSize) &&
 201                ((storageSize / 2) <
 202                 (neededSize + AutoStringDefaultStorageSize))) {
 203       // Don't try to reuse the existing nsStringBuffer, if it would have
 204       // lots of unused space.
 205
 206       memcpy(m2b->Data(), aBuffer, neededSize);
 207       static_cast<char16_t*>(m2b->Data())[aLength] = char16_t(0);
 208       mState.mLength = aLength;
 209       mState.mIsBidi = false;
 210       if (aUpdateBidi) {
 211         UpdateBidiFlag(aBuffer, aLength);
 212       }
 213       return true;
 214     }
 215   }
 216
 217   ReleaseText();
 218
 219   if (aLength == 0) {
 220     return true;
 221   }
 222
 223   char16_t firstChar = *aBuffer;
 224   if (!aForce2b && aLength == 1 && firstChar < 256) {
 225     m1b = sSingleCharSharedString + firstChar;
 226     mState.mInHeap = false;
 227     mState.mIs2b = false;
 228     mState.mLength = 1;
 229
 230     return true;
 231   }
 232
 233   const char16_t* ucp = aBuffer;
 234   const char16_t* uend = aBuffer + aLength;
 235
 236   // Check if we can use a shared string
 237   if (!aForce2b &&
 238       aLength <= 1 + TEXTFRAG_WHITE_AFTER_NEWLINE + TEXTFRAG_MAX_NEWLINES &&
 239       (firstChar == ' ' || firstChar == '\n' || firstChar == '\t')) {
 240     if (firstChar == ' ') {
 241       ++ucp;
 242     }
 243
 244     const char16_t* start = ucp;
 245     while (ucp < uend && *ucp == '\n') {
 246       ++ucp;
 247     }
 248     const char16_t* endNewLine = ucp;
 249
 250     char16_t space = ucp < uend && *ucp == '\t' ? '\t' : ' ';
 251     while (ucp < uend && *ucp == space) {
 252       ++ucp;
 253     }
 254
 255     if (ucp == uend && endNewLine - start <= TEXTFRAG_MAX_NEWLINES &&
 256         ucp - endNewLine <= TEXTFRAG_WHITE_AFTER_NEWLINE) {
 257       char** strings = space == ' ' ? sSpaceSharedString : sTabSharedString;
 258       m1b = strings[endNewLine - start];
 259
 260       // If we didn't find a space in the beginning, skip it now.
 261       if (firstChar != ' ') {
 262         ++m1b;
 263       }
 264
 265       mState.mInHeap = false;
 266       mState.mIs2b = false;
 267       mState.mLength = aLength;
 268
 269       return true;
 270     }
 271   }
 272
 273   // See if we need to store the data in ucs2 or not
 274   int32_t first16bit = aForce2b ? 0 : FirstNon8Bit(ucp, uend);
 275
 276   if (first16bit != -1) {  // aBuffer contains no non-8bit character
 277     // Use ucs2 storage because we have to
 278     CheckedUint32 m2bSize = aLength + 1;
 279     m2bSize *= sizeof(char16_t);
 280     if (!m2bSize.isValid()) {
 281       return false;
 282     }
 283
 284     m2b = nsStringBuffer::Alloc(m2bSize.value()).take();
 285     if (!m2b) {
 286       return false;
 287     }
 288     memcpy(m2b->Data(), aBuffer, aLength * sizeof(char16_t));
 289     static_cast<char16_t*>(m2b->Data())[aLength] = char16_t(0);
 290
 291     mState.mIs2b = true;
 292     if (aUpdateBidi) {
 293       UpdateBidiFlag(aBuffer + first16bit, aLength - first16bit);
 294     }
 295
 296   } else {
 297     // Use 1 byte storage because we can
 298     char* buff = static_cast<char*>(malloc(aLength));
 299     if (!buff) {
 300       return false;
 301     }
 302
 303     // Copy data
 304     LossyConvertUTF16toLatin1(MakeSpan(aBuffer, aLength),
 305                               MakeSpan(buff, aLength));
 306     m1b = buff;
 307     mState.mIs2b = false;
 308   }
 309
 310   // Setup our fields
 311   mState.mInHeap = true;
 312   mState.mLength = aLength;
 313
 314   return true;
 315 }
 316
 317 void nsTextFragment::CopyTo(char16_t* aDest, int32_t aOffset, int32_t aCount) {
 318   NS_ASSERTION(aOffset >= 0, "Bad offset passed to nsTextFragment::CopyTo()!");
 319   NS_ASSERTION(aCount >= 0, "Bad count passed to nsTextFragment::CopyTo()!");
 320
 321   if (aOffset < 0) {
 322     aOffset = 0;
 323   }
 324
 325   if (uint32_t(aOffset + aCount) > GetLength()) {
 326     aCount = mState.mLength - aOffset;
 327   }
 328
 329   if (aCount != 0) {
 330     if (mState.mIs2b) {
 331       memcpy(aDest, Get2b() + aOffset, sizeof(char16_t) * aCount);
 332     } else {
 333       const char* cp = m1b + aOffset;
 334       ConvertLatin1toUTF16(MakeSpan(cp, aCount), MakeSpan(aDest, aCount));
 335     }
 336   }
 337 }
 338
 339 bool nsTextFragment::Append(const char16_t* aBuffer, uint32_t aLength,
 340                             bool aUpdateBidi, bool aForce2b) {
 341   if (!aLength) {
 342     return true;
 343   }
 344
 345   // This is a common case because some callsites create a textnode
 346   // with a value by creating the node and then calling AppendData.
 347   if (mState.mLength == 0) {
 348     return SetTo(aBuffer, aLength, aUpdateBidi, aForce2b);
 349   }
 350
 351   // Should we optimize for aData.Length() == 0?
 352
 353   // FYI: Don't use CheckedInt in this method since here is very hot path
 354   //      in some performance tests.
 355   if (NS_MAX_TEXT_FRAGMENT_LENGTH - mState.mLength < aLength) {
 356     return false;  // Would be overflown if we'd keep handling.
 357   }
 358
 359   if (mState.mIs2b) {
 360     size_t size = mState.mLength + aLength + 1;
 361     if (SIZE_MAX / sizeof(char16_t) < size) {
 362       return false;  // Would be overflown if we'd keep handling.
 363     }
 364     size *= sizeof(char16_t);
 365
 366     // Already a 2-byte string so the result will be too
 367     nsStringBuffer* buff = nullptr;
 368     nsStringBuffer* bufferToRelease = nullptr;
 369     if (m2b->IsReadonly()) {
 370       buff = nsStringBuffer::Alloc(size).take();
 371       if (!buff) {
 372         return false;
 373       }
 374       bufferToRelease = m2b;
 375       memcpy(static_cast<char16_t*>(buff->Data()), m2b->Data(),
 376              mState.mLength * sizeof(char16_t));
 377     } else {
 378       buff = nsStringBuffer::Realloc(m2b, size);
 379       if (!buff) {
 380         return false;
 381       }
 382     }
 383
 384     char16_t* data = static_cast<char16_t*>(buff->Data());
 385     memcpy(data + mState.mLength, aBuffer, aLength * sizeof(char16_t));
 386     mState.mLength += aLength;
 387     m2b = buff;
 388     data[mState.mLength] = char16_t(0);
 389
 390     NS_IF_RELEASE(bufferToRelease);
 391
 392     if (aUpdateBidi) {
 393       UpdateBidiFlag(aBuffer, aLength);
 394     }
 395
 396     return true;
 397   }
 398
 399   // Current string is a 1-byte string, check if the new data fits in one byte
 400   // too.
 401   int32_t first16bit = aForce2b ? 0 : FirstNon8Bit(aBuffer, aBuffer + aLength);
 402
 403   if (first16bit != -1) {  // aBuffer contains no non-8bit character
 404     size_t size = mState.mLength + aLength + 1;
 405     if (SIZE_MAX / sizeof(char16_t) < size) {
 406       return false;  // Would be overflown if we'd keep handling.
 407     }
 408     size *= sizeof(char16_t);
 409
 410     // The old data was 1-byte, but the new is not so we have to expand it
 411     // all to 2-byte
 412     nsStringBuffer* buff = nsStringBuffer::Alloc(size).take();
 413     if (!buff) {
 414       return false;
 415     }
 416
 417     // Copy data into buff
 418     char16_t* data = static_cast<char16_t*>(buff->Data());
 419     ConvertLatin1toUTF16(MakeSpan(m1b, mState.mLength),
 420                          MakeSpan(data, mState.mLength));
 421
 422     memcpy(data + mState.mLength, aBuffer, aLength * sizeof(char16_t));
 423     mState.mLength += aLength;
 424     mState.mIs2b = true;
 425
 426     if (mState.mInHeap) {
 427       free(const_cast<char*>(m1b));
 428     }
 429     data[mState.mLength] = char16_t(0);
 430     m2b = buff;
 431
 432     mState.mInHeap = true;
 433
 434     if (aUpdateBidi) {
 435       UpdateBidiFlag(aBuffer + first16bit, aLength - first16bit);
 436     }
 437
 438     return true;
 439   }
 440
 441   // The new and the old data is all 1-byte
 442   size_t size = mState.mLength + aLength;
 443   MOZ_ASSERT(sizeof(char) == 1);
 444   char* buff;
 445   if (mState.mInHeap) {
 446     buff = static_cast<char*>(realloc(const_cast<char*>(m1b), size));
 447     if (!buff) {
 448       return false;
 449     }
 450   } else {
 451     buff = static_cast<char*>(malloc(size));
 452     if (!buff) {
 453       return false;
 454     }
 455
 456     memcpy(buff, m1b, mState.mLength);
 457     mState.mInHeap = true;
 458   }
 459
 460   // Copy aBuffer into buff.
 461   LossyConvertUTF16toLatin1(MakeSpan(aBuffer, aLength),
 462                             MakeSpan(buff + mState.mLength, aLength));
 463
 464   m1b = buff;
 465   mState.mLength += aLength;
 466
 467   return true;
 468 }
 469
 470 /* virtual */
 471 size_t nsTextFragment::SizeOfExcludingThis(
 472     mozilla::MallocSizeOf aMallocSizeOf) const {
 473   if (Is2b()) {
 474     return m2b->SizeOfIncludingThisIfUnshared(aMallocSizeOf);
 475   }
 476
 477   if (mState.mInHeap) {
 478     return aMallocSizeOf(m1b);
 479   }
 480
 481   return 0;
 482 }
 483
 484 // To save time we only do this when we really want to know, not during
 485 // every allocation
 486 void nsTextFragment::UpdateBidiFlag(const char16_t* aBuffer, uint32_t aLength) {
 487   if (mState.mIs2b && !mState.mIsBidi) {
 488     if (HasRTLChars(MakeSpan(aBuffer, aLength))) {
 489       mState.mIsBidi = true;
 490     }
 491   }
 492 }
 493
 494 bool nsTextFragment::TextEquals(const nsTextFragment& aOther) const {
 495   if (!Is2b()) {
 496     // We're 1-byte.
 497     if (!aOther.Is2b()) {
 498       nsDependentCSubstring ourStr(Get1b(), GetLength());
 499       return ourStr.Equals(
 500           nsDependentCSubstring(aOther.Get1b(), aOther.GetLength()));
 501     }
 502
 503     // We're 1-byte, the other thing is 2-byte.  Instead of implementing a
 504     // separate codepath for this, just use our code below.
 505     return aOther.TextEquals(*this);
 506   }
 507
 508   nsDependentSubstring ourStr(Get2b(), GetLength());
 509   if (aOther.Is2b()) {
 510     return ourStr.Equals(
 511         nsDependentSubstring(aOther.Get2b(), aOther.GetLength()));
 512   }
 513
 514   // We can't use EqualsASCII here, because the other string might not
 515   // actually be ASCII.  Just roll our own compare; do it in the simple way.
 516   // Bug 1532356 tracks not having to roll our own.
 517   if (GetLength() != aOther.GetLength()) {
 518     return false;
 519   }
 520
 521   const char16_t* ourChars = Get2b();
 522   const char* otherChars = aOther.Get1b();
 523   for (uint32_t i = 0; i < GetLength(); ++i) {
 524     if (ourChars[i] != static_cast<char16_t>(otherChars[i])) {
 525       return false;
 526     }
 527   }
 528
 529   return true;
 530 }