xpcom/string/nsTSubstring.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 #include "double-conversion/double-conversion.h"
   8 #include "mozilla/CheckedInt.h"
   9 #include "mozilla/MathAlgorithms.h"
  10 #include "mozilla/MemoryReporting.h"
  11 #include "mozilla/Printf.h"
  12 #include "mozilla/ResultExtensions.h"
  13
  14 #include "nsASCIIMask.h"
  15 #include "nsCharTraits.h"
  16 #include "nsISupports.h"
  17 #include "nsString.h"
  18 #include "nsTArray.h"
  19
  20 // It's not worthwhile to reallocate the buffer and memcpy the
  21 // contents over when the size difference isn't large. With
  22 // power-of-two allocation buckets and 64 as the typical inline
  23 // capacity, considering that above 1000 there performance aspects
  24 // of realloc and memcpy seem to be absorbed, relative to the old
  25 // code, by the performance benefits of the new code being exact,
  26 // we need to choose which transitions of 256 to 128, 512 to 256
  27 // and 1024 to 512 to allow. As a guess, let's pick the middle
  28 // one as the the largest potential transition that we forgo. So
  29 // we'll shrink from 1024 bucket to 512 bucket but not from 512
  30 // bucket to 256 bucket. We'll decide by comparing the difference
  31 // of capacities. As bucket differences, the differences are 256
  32 // and 512. Since the capacities have various overheads, we
  33 // can't compare with 256 or 512 exactly but it's easier to
  34 // compare to some number that's between the two, so it's
  35 // far away from either to ignore the overheads.
  36 const uint32_t kNsStringBufferShrinkingThreshold = 384;
  37
  38 using double_conversion::DoubleToStringConverter;
  39
  40 // ---------------------------------------------------------------------------
  41
  42 static const char16_t gNullChar = 0;
  43
  44 char* const nsCharTraits<char>::sEmptyBuffer =
  45     (char*)const_cast<char16_t*>(&gNullChar);
  46 char16_t* const nsCharTraits<char16_t>::sEmptyBuffer =
  47     const_cast<char16_t*>(&gNullChar);
  48
  49 // ---------------------------------------------------------------------------
  50
  51 static void ReleaseData(void* aData, nsAString::DataFlags aFlags) {
  52   if (aFlags & nsAString::DataFlags::REFCOUNTED) {
  53     mozilla::StringBuffer::FromData(aData)->Release();
  54   } else if (aFlags & nsAString::DataFlags::OWNED) {
  55     // Treat this as destruction of a "StringAdopt" object for leak
  56     // tracking purposes.
  57     MOZ_LOG_DTOR(aData, "StringAdopt", 1);
  58
  59     free(aData);
  60   }
  61   // otherwise, nothing to do.
  62 }
  63
  64 // ---------------------------------------------------------------------------
  65
  66 #ifdef XPCOM_STRING_CONSTRUCTOR_OUT_OF_LINE
  67 template <typename T>
  68 nsTSubstring<T>::nsTSubstring(char_type* aData, size_type aLength,
  69                               DataFlags aDataFlags, ClassFlags aClassFlags)
  70     : ::mozilla::detail::nsTStringRepr<T>(aData, aLength, aDataFlags,
  71                                           aClassFlags) {
  72   AssertValid();
  73
  74   if (aDataFlags & DataFlags::OWNED) {
  75     MOZ_LOG_CTOR(this->mData, "StringAdopt", 1);
  76   }
  77 }
  78 #endif /* XPCOM_STRING_CONSTRUCTOR_OUT_OF_LINE */
  79
  80 /**
  81  * helper function for down-casting a nsTSubstring to an nsTAutoString.
  82  */
  83 template <typename T>
  84 inline const nsTAutoString<T>* AsAutoString(const nsTSubstring<T>* aStr) {
  85   return static_cast<const nsTAutoString<T>*>(aStr);
  86 }
  87
  88 template <typename T>
  89 mozilla::Result<mozilla::BulkWriteHandle<T>, nsresult>
  90 nsTSubstring<T>::BulkWrite(size_type aCapacity, size_type aPrefixToPreserve,
  91                            bool aAllowShrinking) {
  92   auto r = StartBulkWriteImpl(aCapacity, aPrefixToPreserve, aAllowShrinking);
  93   if (MOZ_UNLIKELY(r.isErr())) {
  94     return r.propagateErr();
  95   }
  96   return mozilla::BulkWriteHandle<T>(this, r.unwrap());
  97 }
  98
  99 template <typename T>
 100 auto nsTSubstring<T>::StartBulkWriteImpl(
 101     size_type aCapacity, size_type aPrefixToPreserve, bool aAllowShrinking,
 102     size_type aSuffixLength, size_type aOldSuffixStart,
 103     size_type aNewSuffixStart) -> mozilla::Result<size_type, nsresult> {
 104   // Note! Capacity does not include room for the terminating null char.
 105
 106   MOZ_ASSERT(aPrefixToPreserve <= aCapacity,
 107              "Requested preservation of an overlong prefix.");
 108   MOZ_ASSERT(aNewSuffixStart + aSuffixLength <= aCapacity,
 109              "Requesed move of suffix to out-of-bounds location.");
 110   // Can't assert aOldSuffixStart, because mLength may not be valid anymore,
 111   // since this method allows itself to be called more than once.
 112
 113   // If zero capacity is requested, set the string to the special empty
 114   // string.
 115   if (MOZ_UNLIKELY(!aCapacity)) {
 116     ReleaseData(this->mData, this->mDataFlags);
 117     SetToEmptyBuffer();
 118     return 0;
 119   }
 120
 121   // Note! Capacity() returns 0 when the string is immutable.
 122   const size_type curCapacity = Capacity();
 123
 124   bool shrinking = false;
 125
 126   // We've established that aCapacity > 0.
 127   // |curCapacity == 0| means that the buffer is immutable or 0-sized, so we
 128   // need to allocate a new buffer. We cannot use the existing buffer even
 129   // though it might be large enough.
 130
 131   if (aCapacity <= curCapacity) {
 132     if (aAllowShrinking) {
 133       shrinking = true;
 134     } else {
 135       char_traits::move(this->mData + aNewSuffixStart,
 136                         this->mData + aOldSuffixStart, aSuffixLength);
 137       if (aSuffixLength) {
 138         char_traits::uninitialize(this->mData + aPrefixToPreserve,
 139                                   XPCOM_MIN(aNewSuffixStart - aPrefixToPreserve,
 140                                             kNsStringBufferMaxPoison));
 141         char_traits::uninitialize(
 142             this->mData + aNewSuffixStart + aSuffixLength,
 143             XPCOM_MIN(curCapacity + 1 - aNewSuffixStart - aSuffixLength,
 144                       kNsStringBufferMaxPoison));
 145       } else {
 146         char_traits::uninitialize(this->mData + aPrefixToPreserve,
 147                                   XPCOM_MIN(curCapacity + 1 - aPrefixToPreserve,
 148                                             kNsStringBufferMaxPoison));
 149       }
 150       return curCapacity;
 151     }
 152   }
 153
 154   char_type* oldData = this->mData;
 155   DataFlags oldFlags = this->mDataFlags;
 156
 157   char_type* newData;
 158   DataFlags newDataFlags;
 159   size_type newCapacity;
 160
 161   // If this is an nsTAutoStringN, it's possible that we can use the inline
 162   // buffer.
 163   if ((this->mClassFlags & ClassFlags::INLINE) &&
 164       (aCapacity <= AsAutoString(this)->mInlineCapacity)) {
 165     newCapacity = AsAutoString(this)->mInlineCapacity;
 166     newData = (char_type*)AsAutoString(this)->mStorage;
 167     newDataFlags = DataFlags::TERMINATED | DataFlags::INLINE;
 168   } else {
 169     // If |aCapacity > kMaxCapacity|, then our doubling algorithm may not be
 170     // able to allocate it.  Just bail out in cases like that.  We don't want
 171     // to be allocating 2GB+ strings anyway.
 172     static_assert((sizeof(mozilla::StringBuffer) & 0x1) == 0,
 173                   "bad size for mozilla::StringBuffer");
 174     if (MOZ_UNLIKELY(!this->CheckCapacity(aCapacity))) {
 175       return mozilla::Err(NS_ERROR_OUT_OF_MEMORY);
 176     }
 177
 178     // We increase our capacity so that the allocated buffer grows
 179     // exponentially, which gives us amortized O(1) appending. Below the
 180     // threshold, we use powers-of-two. Above the threshold, we grow by at
 181     // least 1.125, rounding up to the nearest MiB.
 182     const size_type slowGrowthThreshold = 8 * 1024 * 1024;
 183
 184     // mozilla::StringBuffer allocates sizeof(mozilla::StringBuffer) + passed
 185     // size, and storageSize below wants extra 1 * sizeof(char_type).
 186     const size_type neededExtraSpace =
 187         sizeof(mozilla::StringBuffer) / sizeof(char_type) + 1;
 188
 189     size_type temp;
 190     if (aCapacity >= slowGrowthThreshold) {
 191       size_type minNewCapacity =
 192           curCapacity + (curCapacity >> 3);  // multiply by 1.125
 193       temp = XPCOM_MAX(aCapacity, minNewCapacity) + neededExtraSpace;
 194
 195       // Round up to the next multiple of MiB, but ensure the expected
 196       // capacity doesn't include the extra space required by
 197       // mozilla::StringBuffer and null-termination.
 198       const size_t MiB = 1 << 20;
 199       temp = (MiB * ((temp + MiB - 1) / MiB)) - neededExtraSpace;
 200     } else {
 201       // Round up to the next power of two.
 202       temp =
 203           mozilla::RoundUpPow2(aCapacity + neededExtraSpace) - neededExtraSpace;
 204     }
 205
 206     newCapacity = XPCOM_MIN(temp, base_string_type::kMaxCapacity);
 207     MOZ_ASSERT(newCapacity >= aCapacity,
 208                "should have hit the early return at the top");
 209     // Avoid shrinking if the new buffer size is close to the old. Note that
 210     // unsigned underflow is defined behavior.
 211     if ((curCapacity - newCapacity) <= kNsStringBufferShrinkingThreshold &&
 212         (this->mDataFlags & DataFlags::REFCOUNTED)) {
 213       MOZ_ASSERT(aAllowShrinking, "How come we didn't return earlier?");
 214       // We're already close enough to the right size.
 215       newData = oldData;
 216       newCapacity = curCapacity;
 217     } else {
 218       size_type storageSize = (newCapacity + 1) * sizeof(char_type);
 219       // Since we allocate only by powers of 2 we always fit into a full
 220       // mozjemalloc bucket, it's not useful to use realloc, which may spend
 221       // time uselessly copying too much.
 222       mozilla::StringBuffer* newHdr =
 223           mozilla::StringBuffer::Alloc(storageSize).take();
 224       if (newHdr) {
 225         newData = (char_type*)newHdr->Data();
 226       } else if (shrinking) {
 227         // We're still in a consistent state.
 228         //
 229         // Since shrinking is just a memory footprint optimization, we
 230         // don't propagate OOM if we tried to shrink in order to avoid
 231         // OOM crashes from infallible callers. If we're lucky, soon enough
 232         // a fallible caller reaches OOM and is able to deal or we end up
 233         // disposing of this string before reaching OOM again.
 234         newData = oldData;
 235         newCapacity = curCapacity;
 236       } else {
 237         return mozilla::Err(NS_ERROR_OUT_OF_MEMORY);
 238       }
 239     }
 240     newDataFlags = DataFlags::TERMINATED | DataFlags::REFCOUNTED;
 241   }
 242
 243   this->mData = newData;
 244   this->mDataFlags = newDataFlags;
 245
 246   if (oldData == newData) {
 247     char_traits::move(newData + aNewSuffixStart, oldData + aOldSuffixStart,
 248                       aSuffixLength);
 249     if (aSuffixLength) {
 250       char_traits::uninitialize(this->mData + aPrefixToPreserve,
 251                                 XPCOM_MIN(aNewSuffixStart - aPrefixToPreserve,
 252                                           kNsStringBufferMaxPoison));
 253       char_traits::uninitialize(
 254           this->mData + aNewSuffixStart + aSuffixLength,
 255           XPCOM_MIN(newCapacity + 1 - aNewSuffixStart - aSuffixLength,
 256                     kNsStringBufferMaxPoison));
 257     } else {
 258       char_traits::uninitialize(this->mData + aPrefixToPreserve,
 259                                 XPCOM_MIN(newCapacity + 1 - aPrefixToPreserve,
 260                                           kNsStringBufferMaxPoison));
 261     }
 262   } else {
 263     char_traits::copy(newData, oldData, aPrefixToPreserve);
 264     char_traits::copy(newData + aNewSuffixStart, oldData + aOldSuffixStart,
 265                       aSuffixLength);
 266     ReleaseData(oldData, oldFlags);
 267   }
 268
 269   return newCapacity;
 270 }
 271
 272 template <typename T>
 273 void nsTSubstring<T>::FinishBulkWriteImpl(size_type aLength) {
 274   if (aLength) {
 275     FinishBulkWriteImplImpl(aLength);
 276   } else {
 277     ReleaseData(this->mData, this->mDataFlags);
 278     SetToEmptyBuffer();
 279   }
 280   AssertValid();
 281 }
 282
 283 template <typename T>
 284 void nsTSubstring<T>::Finalize() {
 285   ReleaseData(this->mData, this->mDataFlags);
 286   // this->mData, this->mLength, and this->mDataFlags are purposefully left
 287   // dangling
 288 }
 289
 290 template <typename T>
 291 bool nsTSubstring<T>::ReplacePrep(index_type aCutStart, size_type aCutLength,
 292                                   size_type aNewLength) {
 293   aCutLength = XPCOM_MIN(aCutLength, this->mLength - aCutStart);
 294
 295   mozilla::CheckedInt<size_type> newTotalLen = this->Length();
 296   newTotalLen += aNewLength;
 297   newTotalLen -= aCutLength;
 298   if (!newTotalLen.isValid()) {
 299     return false;
 300   }
 301
 302   if (aCutStart == this->mLength && Capacity() > newTotalLen.value()) {
 303     this->mDataFlags &= ~DataFlags::VOIDED;
 304     this->mData[newTotalLen.value()] = char_type(0);
 305     this->mLength = newTotalLen.value();
 306     return true;
 307   }
 308
 309   return ReplacePrepInternal(aCutStart, aCutLength, aNewLength,
 310                              newTotalLen.value());
 311 }
 312
 313 template <typename T>
 314 bool nsTSubstring<T>::ReplacePrepInternal(index_type aCutStart,
 315                                           size_type aCutLen, size_type aFragLen,
 316                                           size_type aNewLen) {
 317   size_type newSuffixStart = aCutStart + aFragLen;
 318   size_type oldSuffixStart = aCutStart + aCutLen;
 319   size_type suffixLength = this->mLength - oldSuffixStart;
 320
 321   mozilla::Result<size_type, nsresult> r = StartBulkWriteImpl(
 322       aNewLen, aCutStart, false, suffixLength, oldSuffixStart, newSuffixStart);
 323   if (r.isErr()) {
 324     return false;
 325   }
 326   FinishBulkWriteImpl(aNewLen);
 327   return true;
 328 }
 329
 330 template <typename T>
 331 typename nsTSubstring<T>::size_type nsTSubstring<T>::Capacity() const {
 332   // return 0 to indicate an immutable or 0-sized buffer
 333
 334   size_type capacity;
 335   if (this->mDataFlags & DataFlags::REFCOUNTED) {
 336     // if the string is readonly, then we pretend that it has no capacity.
 337     mozilla::StringBuffer* hdr = mozilla::StringBuffer::FromData(this->mData);
 338     if (hdr->IsReadonly()) {
 339       capacity = 0;
 340     } else {
 341       capacity = (size_t(hdr->StorageSize()) / sizeof(char_type)) - 1;
 342     }
 343   } else if (this->mDataFlags & DataFlags::INLINE) {
 344     MOZ_ASSERT(this->mClassFlags & ClassFlags::INLINE);
 345     capacity = AsAutoString(this)->mInlineCapacity;
 346   } else if (this->mDataFlags & DataFlags::OWNED) {
 347     // we don't store the capacity of an adopted buffer because that would
 348     // require an additional member field.  the best we can do is base the
 349     // capacity on our length.  remains to be seen if this is the right
 350     // trade-off.
 351     capacity = this->mLength;
 352   } else {
 353     capacity = 0;
 354   }
 355
 356   return capacity;
 357 }
 358
 359 template <typename T>
 360 bool nsTSubstring<T>::EnsureMutable(size_type aNewLen) {
 361   if (aNewLen == size_type(-1) || aNewLen == this->mLength) {
 362     if (this->mDataFlags & (DataFlags::INLINE | DataFlags::OWNED)) {
 363       return true;
 364     }
 365     if ((this->mDataFlags & DataFlags::REFCOUNTED) &&
 366         !mozilla::StringBuffer::FromData(this->mData)->IsReadonly()) {
 367       return true;
 368     }
 369
 370     aNewLen = this->mLength;
 371   }
 372   return SetLength(aNewLen, mozilla::fallible);
 373 }
 374
 375 // ---------------------------------------------------------------------------
 376
 377 // This version of Assign is optimized for single-character assignment.
 378 template <typename T>
 379 void nsTSubstring<T>::Assign(char_type aChar) {
 380   if (MOZ_UNLIKELY(!Assign(aChar, mozilla::fallible))) {
 381     AllocFailed(1);
 382   }
 383 }
 384
 385 template <typename T>
 386 bool nsTSubstring<T>::Assign(char_type aChar, const fallible_t&) {
 387   auto r = StartBulkWriteImpl(1, 0, true);
 388   if (MOZ_UNLIKELY(r.isErr())) {
 389     return false;
 390   }
 391   *this->mData = aChar;
 392   FinishBulkWriteImpl(1);
 393   return true;
 394 }
 395
 396 template <typename T>
 397 void nsTSubstring<T>::Assign(const char_type* aData, size_type aLength) {
 398   if (MOZ_UNLIKELY(!Assign(aData, aLength, mozilla::fallible))) {
 399     AllocFailed(aLength == size_type(-1) ? char_traits::length(aData)
 400                                          : aLength);
 401   }
 402 }
 403
 404 template <typename T>
 405 bool nsTSubstring<T>::Assign(const char_type* aData,
 406                              const fallible_t& aFallible) {
 407   return Assign(aData, size_type(-1), aFallible);
 408 }
 409
 410 template <typename T>
 411 bool nsTSubstring<T>::Assign(const char_type* aData, size_type aLength,
 412                              const fallible_t& aFallible) {
 413   if (!aData || aLength == 0) {
 414     Truncate();
 415     return true;
 416   }
 417
 418   if (MOZ_UNLIKELY(aLength == size_type(-1))) {
 419     aLength = char_traits::length(aData);
 420   }
 421
 422   if (MOZ_UNLIKELY(this->IsDependentOn(aData, aData + aLength))) {
 423     return Assign(string_type(aData, aLength), aFallible);
 424   }
 425
 426   auto r = StartBulkWriteImpl(aLength, 0, true);
 427   if (MOZ_UNLIKELY(r.isErr())) {
 428     return false;
 429   }
 430   char_traits::copy(this->mData, aData, aLength);
 431   FinishBulkWriteImpl(aLength);
 432   return true;
 433 }
 434
 435 template <typename T>
 436 void nsTSubstring<T>::AssignASCII(const char* aData, size_type aLength) {
 437   if (MOZ_UNLIKELY(!AssignASCII(aData, aLength, mozilla::fallible))) {
 438     AllocFailed(aLength);
 439   }
 440 }
 441
 442 template <typename T>
 443 bool nsTSubstring<T>::AssignASCII(const char* aData, size_type aLength,
 444                                   const fallible_t& aFallible) {
 445   MOZ_ASSERT(aLength != size_type(-1));
 446
 447   // A Unicode string can't depend on an ASCII string buffer,
 448   // so this dependence check only applies to CStrings.
 449   if constexpr (std::is_same_v<T, char>) {
 450     if (this->IsDependentOn(aData, aData + aLength)) {
 451       return Assign(string_type(aData, aLength), aFallible);
 452     }
 453   }
 454
 455   auto r = StartBulkWriteImpl(aLength, 0, true);
 456   if (MOZ_UNLIKELY(r.isErr())) {
 457     return false;
 458   }
 459   char_traits::copyASCII(this->mData, aData, aLength);
 460   FinishBulkWriteImpl(aLength);
 461   return true;
 462 }
 463
 464 template <typename T>
 465 void nsTSubstring<T>::AssignLiteral(const char_type* aData, size_type aLength) {
 466   ReleaseData(this->mData, this->mDataFlags);
 467   SetData(const_cast<char_type*>(aData), aLength,
 468           DataFlags::TERMINATED | DataFlags::LITERAL);
 469 }
 470
 471 template <typename T>
 472 void nsTSubstring<T>::Assign(const self_type& aStr) {
 473   if (!Assign(aStr, mozilla::fallible)) {
 474     AllocFailed(aStr.Length());
 475   }
 476 }
 477
 478 template <typename T>
 479 bool nsTSubstring<T>::Assign(const self_type& aStr,
 480                              const fallible_t& aFallible) {
 481   // |aStr| could be sharable. We need to check its flags to know how to
 482   // deal with it.
 483
 484   if (&aStr == this) {
 485     return true;
 486   }
 487
 488   if (!aStr.mLength) {
 489     Truncate();
 490     this->mDataFlags |= aStr.mDataFlags & DataFlags::VOIDED;
 491     return true;
 492   }
 493
 494   if (aStr.mDataFlags & DataFlags::REFCOUNTED) {
 495     // nice! we can avoid a string copy :-)
 496
 497     // |aStr| should be null-terminated
 498     NS_ASSERTION(aStr.mDataFlags & DataFlags::TERMINATED,
 499                  "shared, but not terminated");
 500
 501     ReleaseData(this->mData, this->mDataFlags);
 502
 503     SetData(aStr.mData, aStr.mLength,
 504             DataFlags::TERMINATED | DataFlags::REFCOUNTED);
 505
 506     // get an owning reference to the this->mData
 507     mozilla::StringBuffer::FromData(this->mData)->AddRef();
 508     return true;
 509   }
 510   if (aStr.mDataFlags & DataFlags::LITERAL) {
 511     MOZ_ASSERT(aStr.mDataFlags & DataFlags::TERMINATED, "Unterminated literal");
 512
 513     AssignLiteral(aStr.mData, aStr.mLength);
 514     return true;
 515   }
 516
 517   // else, treat this like an ordinary assignment.
 518   return Assign(aStr.Data(), aStr.Length(), aFallible);
 519 }
 520
 521 template <typename T>
 522 void nsTSubstring<T>::Assign(self_type&& aStr) {
 523   if (!Assign(std::move(aStr), mozilla::fallible)) {
 524     AllocFailed(aStr.Length());
 525   }
 526 }
 527
 528 template <typename T>
 529 void nsTSubstring<T>::AssignOwned(self_type&& aStr) {
 530   MOZ_ASSERT(aStr.mDataFlags & (DataFlags::REFCOUNTED | DataFlags::OWNED),
 531              "neither shared nor owned");
 532
 533   // If they have a REFCOUNTED or OWNED buffer, we can avoid a copy - so steal
 534   // their buffer and reset them to the empty string.
 535
 536   // |aStr| should be null-terminated
 537   MOZ_ASSERT(aStr.mDataFlags & DataFlags::TERMINATED,
 538              "shared or owned, but not terminated");
 539
 540   ReleaseData(this->mData, this->mDataFlags);
 541
 542   SetData(aStr.mData, aStr.mLength, aStr.mDataFlags);
 543   aStr.SetToEmptyBuffer();
 544 }
 545
 546 template <typename T>
 547 bool nsTSubstring<T>::Assign(self_type&& aStr, const fallible_t& aFallible) {
 548   // We're moving |aStr| in this method, so we need to try to steal the data,
 549   // and in the fallback perform a copy-assignment followed by a truncation of
 550   // the original string.
 551
 552   if (&aStr == this) {
 553     NS_WARNING("Move assigning a string to itself?");
 554     return true;
 555   }
 556
 557   if (aStr.mDataFlags & (DataFlags::REFCOUNTED | DataFlags::OWNED)) {
 558     AssignOwned(std::move(aStr));
 559     return true;
 560   }
 561
 562   // Otherwise treat this as a normal assignment, and truncate the moved string.
 563   // We don't truncate the source string if the allocation failed.
 564   if (!Assign(aStr, aFallible)) {
 565     return false;
 566   }
 567   aStr.Truncate();
 568   return true;
 569 }
 570
 571 template <typename T>
 572 void nsTSubstring<T>::Assign(const substring_tuple_type& aTuple) {
 573   if (!Assign(aTuple, mozilla::fallible)) {
 574     AllocFailed(aTuple.Length());
 575   }
 576 }
 577
 578 template <typename T>
 579 bool nsTSubstring<T>::AssignNonDependent(const substring_tuple_type& aTuple,
 580                                          size_type aTupleLength,
 581                                          const mozilla::fallible_t& aFallible) {
 582   NS_ASSERTION(aTuple.Length() == aTupleLength, "wrong length passed");
 583
 584   auto r = StartBulkWriteImpl(aTupleLength);
 585   if (r.isErr()) {
 586     return false;
 587   }
 588
 589   aTuple.WriteTo(this->mData, aTupleLength);
 590
 591   FinishBulkWriteImpl(aTupleLength);
 592   return true;
 593 }
 594
 595 template <typename T>
 596 bool nsTSubstring<T>::Assign(const substring_tuple_type& aTuple,
 597                              const fallible_t& aFallible) {
 598   const auto [isDependentOnThis, tupleLength] =
 599       aTuple.IsDependentOnWithLength(this->mData, this->mData + this->mLength);
 600   if (isDependentOnThis) {
 601     string_type temp;
 602     self_type& tempSubstring = temp;
 603     if (!tempSubstring.AssignNonDependent(aTuple, tupleLength, aFallible)) {
 604       return false;
 605     }
 606     AssignOwned(std::move(temp));
 607     return true;
 608   }
 609
 610   return AssignNonDependent(aTuple, tupleLength, aFallible);
 611 }
 612
 613 template <typename T>
 614 void nsTSubstring<T>::Adopt(char_type* aData, size_type aLength) {
 615   if (aData) {
 616     ReleaseData(this->mData, this->mDataFlags);
 617
 618     if (aLength == size_type(-1)) {
 619       aLength = char_traits::length(aData);
 620     }
 621
 622     SetData(aData, aLength, DataFlags::TERMINATED | DataFlags::OWNED);
 623
 624     // Treat this as construction of a "StringAdopt" object for leak
 625     // tracking purposes.
 626     MOZ_LOG_CTOR(this->mData, "StringAdopt", 1);
 627   } else {
 628     SetIsVoid(true);
 629   }
 630 }
 631
 632 // This version of Replace is optimized for single-character replacement.
 633 template <typename T>
 634 void nsTSubstring<T>::Replace(index_type aCutStart, size_type aCutLength,
 635                               char_type aChar) {
 636   aCutStart = XPCOM_MIN(aCutStart, this->Length());
 637
 638   if (ReplacePrep(aCutStart, aCutLength, 1)) {
 639     this->mData[aCutStart] = aChar;
 640   }
 641 }
 642
 643 template <typename T>
 644 bool nsTSubstring<T>::Replace(index_type aCutStart, size_type aCutLength,
 645                               char_type aChar, const fallible_t&) {
 646   aCutStart = XPCOM_MIN(aCutStart, this->Length());
 647
 648   if (!ReplacePrep(aCutStart, aCutLength, 1)) {
 649     return false;
 650   }
 651
 652   this->mData[aCutStart] = aChar;
 653
 654   return true;
 655 }
 656
 657 template <typename T>
 658 void nsTSubstring<T>::Replace(index_type aCutStart, size_type aCutLength,
 659                               const char_type* aData, size_type aLength) {
 660   if (!Replace(aCutStart, aCutLength, aData, aLength, mozilla::fallible)) {
 661     AllocFailed(this->Length() - aCutLength + 1);
 662   }
 663 }
 664
 665 template <typename T>
 666 bool nsTSubstring<T>::Replace(index_type aCutStart, size_type aCutLength,
 667                               const char_type* aData, size_type aLength,
 668                               const fallible_t& aFallible) {
 669   // unfortunately, some callers pass null :-(
 670   if (!aData) {
 671     aLength = 0;
 672   } else {
 673     if (aLength == size_type(-1)) {
 674       aLength = char_traits::length(aData);
 675     }
 676
 677     if (this->IsDependentOn(aData, aData + aLength)) {
 678       nsTAutoString<T> temp(aData, aLength);
 679       return Replace(aCutStart, aCutLength, temp, aFallible);
 680     }
 681   }
 682
 683   aCutStart = XPCOM_MIN(aCutStart, this->Length());
 684
 685   bool ok = ReplacePrep(aCutStart, aCutLength, aLength);
 686   if (!ok) {
 687     return false;
 688   }
 689
 690   if (aLength > 0) {
 691     char_traits::copy(this->mData + aCutStart, aData, aLength);
 692   }
 693
 694   return true;
 695 }
 696
 697 template <typename T>
 698 void nsTSubstring<T>::Replace(index_type aCutStart, size_type aCutLength,
 699                               const substring_tuple_type& aTuple) {
 700   const auto [isDependentOnThis, tupleLength] =
 701       aTuple.IsDependentOnWithLength(this->mData, this->mData + this->mLength);
 702
 703   if (isDependentOnThis) {
 704     nsTAutoString<T> temp;
 705     if (!temp.AssignNonDependent(aTuple, tupleLength, mozilla::fallible)) {
 706       AllocFailed(tupleLength);
 707     }
 708     Replace(aCutStart, aCutLength, temp);
 709     return;
 710   }
 711
 712   aCutStart = XPCOM_MIN(aCutStart, this->Length());
 713
 714   if (ReplacePrep(aCutStart, aCutLength, tupleLength) && tupleLength > 0) {
 715     aTuple.WriteTo(this->mData + aCutStart, tupleLength);
 716   }
 717 }
 718
 719 template <typename T>
 720 void nsTSubstring<T>::ReplaceLiteral(index_type aCutStart, size_type aCutLength,
 721                                      const char_type* aData,
 722                                      size_type aLength) {
 723   aCutStart = XPCOM_MIN(aCutStart, this->Length());
 724
 725   if (!aCutStart && aCutLength == this->Length() &&
 726       !(this->mDataFlags & DataFlags::REFCOUNTED)) {
 727     // Check for REFCOUNTED above to avoid undoing the effect of
 728     // SetCapacity().
 729     AssignLiteral(aData, aLength);
 730   } else if (ReplacePrep(aCutStart, aCutLength, aLength) && aLength > 0) {
 731     char_traits::copy(this->mData + aCutStart, aData, aLength);
 732   }
 733 }
 734
 735 template <typename T>
 736 void nsTSubstring<T>::Append(char_type aChar) {
 737   if (MOZ_UNLIKELY(!Append(aChar, mozilla::fallible))) {
 738     AllocFailed(this->mLength + 1);
 739   }
 740 }
 741
 742 template <typename T>
 743 bool nsTSubstring<T>::Append(char_type aChar, const fallible_t& aFallible) {
 744   size_type oldLen = this->mLength;
 745   size_type newLen = oldLen + 1;  // Can't overflow
 746   auto r = StartBulkWriteImpl(newLen, oldLen, false);
 747   if (MOZ_UNLIKELY(r.isErr())) {
 748     return false;
 749   }
 750   this->mData[oldLen] = aChar;
 751   FinishBulkWriteImpl(newLen);
 752   return true;
 753 }
 754
 755 template <typename T>
 756 void nsTSubstring<T>::Append(const char_type* aData, size_type aLength) {
 757   if (MOZ_UNLIKELY(!Append(aData, aLength, mozilla::fallible))) {
 758     AllocFailed(this->mLength + (aLength == size_type(-1)
 759                                      ? char_traits::length(aData)
 760                                      : aLength));
 761   }
 762 }
 763
 764 template <typename T>
 765 bool nsTSubstring<T>::Append(const char_type* aData, size_type aLength,
 766                              const fallible_t& aFallible) {
 767   if (MOZ_UNLIKELY(aLength == size_type(-1))) {
 768     aLength = char_traits::length(aData);
 769   }
 770
 771   if (MOZ_UNLIKELY(!aLength)) {
 772     // Avoid undoing the effect of SetCapacity() if both
 773     // mLength and aLength are zero.
 774     return true;
 775   }
 776
 777   if (MOZ_UNLIKELY(this->IsDependentOn(aData, aData + aLength))) {
 778     return Append(string_type(aData, aLength), mozilla::fallible);
 779   }
 780   size_type oldLen = this->mLength;
 781   mozilla::CheckedInt<size_type> newLen(oldLen);
 782   newLen += aLength;
 783   if (MOZ_UNLIKELY(!newLen.isValid())) {
 784     return false;
 785   }
 786   auto r = StartBulkWriteImpl(newLen.value(), oldLen, false);
 787   if (MOZ_UNLIKELY(r.isErr())) {
 788     return false;
 789   }
 790   char_traits::copy(this->mData + oldLen, aData, aLength);
 791   FinishBulkWriteImpl(newLen.value());
 792   return true;
 793 }
 794
 795 template <typename T>
 796 void nsTSubstring<T>::AppendASCII(const char* aData, size_type aLength) {
 797   if (MOZ_UNLIKELY(!AppendASCII(aData, aLength, mozilla::fallible))) {
 798     AllocFailed(this->mLength +
 799                 (aLength == size_type(-1) ? strlen(aData) : aLength));
 800   }
 801 }
 802
 803 template <typename T>
 804 bool nsTSubstring<T>::AppendASCII(const char* aData,
 805                                   const fallible_t& aFallible) {
 806   return AppendASCII(aData, size_type(-1), aFallible);
 807 }
 808
 809 template <typename T>
 810 bool nsTSubstring<T>::AppendASCII(const char* aData, size_type aLength,
 811                                   const fallible_t& aFallible) {
 812   if (MOZ_UNLIKELY(aLength == size_type(-1))) {
 813     aLength = strlen(aData);
 814   }
 815
 816   if (MOZ_UNLIKELY(!aLength)) {
 817     // Avoid undoing the effect of SetCapacity() if both
 818     // mLength and aLength are zero.
 819     return true;
 820   }
 821
 822   if constexpr (std::is_same_v<T, char>) {
 823     // 16-bit string can't depend on an 8-bit buffer
 824     if (MOZ_UNLIKELY(this->IsDependentOn(aData, aData + aLength))) {
 825       return Append(string_type(aData, aLength), mozilla::fallible);
 826     }
 827   }
 828
 829   size_type oldLen = this->mLength;
 830   mozilla::CheckedInt<size_type> newLen(oldLen);
 831   newLen += aLength;
 832   if (MOZ_UNLIKELY(!newLen.isValid())) {
 833     return false;
 834   }
 835   auto r = StartBulkWriteImpl(newLen.value(), oldLen, false);
 836   if (MOZ_UNLIKELY(r.isErr())) {
 837     return false;
 838   }
 839   char_traits::copyASCII(this->mData + oldLen, aData, aLength);
 840   FinishBulkWriteImpl(newLen.value());
 841   return true;
 842 }
 843
 844 template <typename T>
 845 void nsTSubstring<T>::Append(const self_type& aStr) {
 846   if (MOZ_UNLIKELY(!Append(aStr, mozilla::fallible))) {
 847     AllocFailed(this->mLength + aStr.Length());
 848   }
 849 }
 850
 851 template <typename T>
 852 bool nsTSubstring<T>::Append(const self_type& aStr,
 853                              const fallible_t& aFallible) {
 854   // Check refcounted to avoid undoing the effects of SetCapacity().
 855   if (MOZ_UNLIKELY(!this->mLength &&
 856                    !(this->mDataFlags & DataFlags::REFCOUNTED))) {
 857     return Assign(aStr, mozilla::fallible);
 858   }
 859   return Append(aStr.BeginReading(), aStr.Length(), mozilla::fallible);
 860 }
 861
 862 template <typename T>
 863 void nsTSubstring<T>::Append(const substring_tuple_type& aTuple) {
 864   if (MOZ_UNLIKELY(!Append(aTuple, mozilla::fallible))) {
 865     AllocFailed(this->mLength + aTuple.Length());
 866   }
 867 }
 868
 869 template <typename T>
 870 bool nsTSubstring<T>::Append(const substring_tuple_type& aTuple,
 871                              const fallible_t& aFallible) {
 872   const auto [isDependentOnThis, tupleLength] =
 873       aTuple.IsDependentOnWithLength(this->mData, this->mData + this->mLength);
 874
 875   if (MOZ_UNLIKELY(!tupleLength)) {
 876     // Avoid undoing the effect of SetCapacity() if both
 877     // mLength and tupleLength are zero.
 878     return true;
 879   }
 880
 881   if (MOZ_UNLIKELY(isDependentOnThis)) {
 882     return Append(string_type(aTuple), aFallible);
 883   }
 884
 885   size_type oldLen = this->mLength;
 886   mozilla::CheckedInt<size_type> newLen(oldLen);
 887   newLen += tupleLength;
 888   if (MOZ_UNLIKELY(!newLen.isValid())) {
 889     return false;
 890   }
 891   auto r = StartBulkWriteImpl(newLen.value(), oldLen, false);
 892   if (MOZ_UNLIKELY(r.isErr())) {
 893     return false;
 894   }
 895   aTuple.WriteTo(this->mData + oldLen, tupleLength);
 896   FinishBulkWriteImpl(newLen.value());
 897   return true;
 898 }
 899
 900 template <typename T>
 901 void nsTSubstring<T>::SetCapacity(size_type aCapacity) {
 902   if (!SetCapacity(aCapacity, mozilla::fallible)) {
 903     AllocFailed(aCapacity);
 904   }
 905 }
 906
 907 template <typename T>
 908 bool nsTSubstring<T>::SetCapacity(size_type aCapacity, const fallible_t&) {
 909   size_type length = this->mLength;
 910   // This method can no longer be used to shorten the
 911   // logical length.
 912   size_type capacity = XPCOM_MAX(aCapacity, length);
 913
 914   auto r = StartBulkWriteImpl(capacity, length, true);
 915   if (r.isErr()) {
 916     return false;
 917   }
 918
 919   if (MOZ_UNLIKELY(!capacity)) {
 920     // Zero capacity was requested on a zero-length
 921     // string. In this special case, we are pointing
 922     // to the special empty buffer, which is already
 923     // zero-terminated and not writable, so we must
 924     // not attempt to zero-terminate it.
 925     AssertValid();
 926     return true;
 927   }
 928
 929   // FinishBulkWriteImpl with argument zero releases
 930   // the heap-allocated buffer. However, SetCapacity()
 931   // is a special case that allows mLength to be zero
 932   // while a heap-allocated buffer exists.
 933   // By calling FinishBulkWriteImplImpl, we skip the
 934   // zero case handling that's inappropriate in the
 935   // SetCapacity() case.
 936   FinishBulkWriteImplImpl(length);
 937   return true;
 938 }
 939
 940 template <typename T>
 941 void nsTSubstring<T>::SetLength(size_type aLength) {
 942   if (!SetLength(aLength, mozilla::fallible)) {
 943     AllocFailed(aLength);
 944   }
 945 }
 946
 947 template <typename T>
 948 bool nsTSubstring<T>::SetLength(size_type aLength,
 949                                 const fallible_t& aFallible) {
 950   size_type preserve = XPCOM_MIN(aLength, this->Length());
 951   auto r = StartBulkWriteImpl(aLength, preserve, true);
 952   if (r.isErr()) {
 953     return false;
 954   }
 955
 956   FinishBulkWriteImpl(aLength);
 957
 958   return true;
 959 }
 960
 961 template <typename T>
 962 void nsTSubstring<T>::Truncate() {
 963   ReleaseData(this->mData, this->mDataFlags);
 964   SetToEmptyBuffer();
 965   AssertValid();
 966 }
 967
 968 template <typename T>
 969 void nsTSubstring<T>::SetIsVoid(bool aVal) {
 970   if (aVal) {
 971     Truncate();
 972     this->mDataFlags |= DataFlags::VOIDED;
 973   } else {
 974     this->mDataFlags &= ~DataFlags::VOIDED;
 975   }
 976 }
 977
 978 template <typename T>
 979 void nsTSubstring<T>::StripChar(char_type aChar) {
 980   if (this->mLength == 0) {
 981     return;
 982   }
 983
 984   if (!EnsureMutable()) {  // XXX do this lazily?
 985     AllocFailed(this->mLength);
 986   }
 987
 988   // XXX(darin): this code should defer writing until necessary.
 989
 990   char_type* to = this->mData;
 991   char_type* from = this->mData;
 992   char_type* end = this->mData + this->mLength;
 993
 994   while (from < end) {
 995     char_type theChar = *from++;
 996     if (aChar != theChar) {
 997       *to++ = theChar;
 998     }
 999   }
1000   *to = char_type(0);  // add the null
1001   this->mLength = to - this->mData;
1002 }
1003
1004 template <typename T>
1005 void nsTSubstring<T>::StripChars(const char_type* aChars) {
1006   if (this->mLength == 0) {
1007     return;
1008   }
1009
1010   if (!EnsureMutable()) {  // XXX do this lazily?
1011     AllocFailed(this->mLength);
1012   }
1013
1014   // XXX(darin): this code should defer writing until necessary.
1015
1016   char_type* to = this->mData;
1017   char_type* from = this->mData;
1018   char_type* end = this->mData + this->mLength;
1019
1020   while (from < end) {
1021     char_type theChar = *from++;
1022     const char_type* test = aChars;
1023
1024     for (; *test && *test != theChar; ++test);
1025
1026     if (!*test) {
1027       // Not stripped, copy this char.
1028       *to++ = theChar;
1029     }
1030   }
1031   *to = char_type(0);  // add the null
1032   this->mLength = to - this->mData;
1033 }
1034
1035 template <typename T>
1036 void nsTSubstring<T>::StripTaggedASCII(const ASCIIMaskArray& aToStrip) {
1037   if (this->mLength == 0) {
1038     return;
1039   }
1040
1041   size_t untaggedPrefixLength = 0;
1042   for (; untaggedPrefixLength < this->mLength; ++untaggedPrefixLength) {
1043     uint32_t theChar = (uint32_t)this->mData[untaggedPrefixLength];
1044     if (mozilla::ASCIIMask::IsMasked(aToStrip, theChar)) {
1045       break;
1046     }
1047   }
1048
1049   if (untaggedPrefixLength == this->mLength) {
1050     return;
1051   }
1052
1053   if (!EnsureMutable()) {
1054     AllocFailed(this->mLength);
1055   }
1056
1057   char_type* to = this->mData + untaggedPrefixLength;
1058   char_type* from = to;
1059   char_type* end = this->mData + this->mLength;
1060
1061   while (from < end) {
1062     uint32_t theChar = (uint32_t)*from++;
1063     // Replacing this with a call to ASCIIMask::IsMasked
1064     // regresses performance somewhat, so leaving it inlined.
1065     if (!mozilla::ASCIIMask::IsMasked(aToStrip, theChar)) {
1066       // Not stripped, copy this char.
1067       *to++ = (char_type)theChar;
1068     }
1069   }
1070   *to = char_type(0);  // add the null
1071   this->mLength = to - this->mData;
1072 }
1073
1074 template <typename T>
1075 void nsTSubstring<T>::StripCRLF() {
1076   // Expanding this call to copy the code from StripTaggedASCII
1077   // instead of just calling it does somewhat help with performance
1078   // but it is not worth it given the duplicated code.
1079   StripTaggedASCII(mozilla::ASCIIMask::MaskCRLF());
1080 }
1081
1082 template <typename T>
1083 struct MOZ_STACK_CLASS PrintfAppend : public mozilla::PrintfTarget {
1084   explicit PrintfAppend(nsTSubstring<T>* aString) : mString(aString) {}
1085
1086   bool append(const char* aStr, size_t aLen) override {
1087     if (aLen == 0) {
1088       return true;
1089     }
1090
1091     mString->AppendASCII(aStr, aLen);
1092     return true;
1093   }
1094
1095  private:
1096   nsTSubstring<T>* mString;
1097 };
1098
1099 template <typename T>
1100 void nsTSubstring<T>::AppendPrintf(const char* aFormat, ...) {
1101   PrintfAppend<T> appender(this);
1102   va_list ap;
1103   va_start(ap, aFormat);
1104   bool r = appender.vprint(aFormat, ap);
1105   if (!r) {
1106     MOZ_CRASH("Allocation or other failure in PrintfTarget::print");
1107   }
1108   va_end(ap);
1109 }
1110
1111 template <typename T>
1112 void nsTSubstring<T>::AppendVprintf(const char* aFormat, va_list aAp) {
1113   PrintfAppend<T> appender(this);
1114   bool r = appender.vprint(aFormat, aAp);
1115   if (!r) {
1116     MOZ_CRASH("Allocation or other failure in PrintfTarget::print");
1117   }
1118 }
1119
1120 template <typename T>
1121 void nsTSubstring<T>::AppendIntDec(int32_t aInteger) {
1122   PrintfAppend<T> appender(this);
1123   bool r = appender.appendIntDec(aInteger);
1124   if (MOZ_UNLIKELY(!r)) {
1125     MOZ_CRASH("Allocation or other failure while appending integers");
1126   }
1127 }
1128
1129 template <typename T>
1130 void nsTSubstring<T>::AppendIntDec(uint32_t aInteger) {
1131   PrintfAppend<T> appender(this);
1132   bool r = appender.appendIntDec(aInteger);
1133   if (MOZ_UNLIKELY(!r)) {
1134     MOZ_CRASH("Allocation or other failure while appending integers");
1135   }
1136 }
1137
1138 template <typename T>
1139 void nsTSubstring<T>::AppendIntOct(uint32_t aInteger) {
1140   PrintfAppend<T> appender(this);
1141   bool r = appender.appendIntOct(aInteger);
1142   if (MOZ_UNLIKELY(!r)) {
1143     MOZ_CRASH("Allocation or other failure while appending integers");
1144   }
1145 }
1146
1147 template <typename T>
1148 void nsTSubstring<T>::AppendIntHex(uint32_t aInteger) {
1149   PrintfAppend<T> appender(this);
1150   bool r = appender.appendIntHex(aInteger);
1151   if (MOZ_UNLIKELY(!r)) {
1152     MOZ_CRASH("Allocation or other failure while appending integers");
1153   }
1154 }
1155
1156 template <typename T>
1157 void nsTSubstring<T>::AppendIntDec(int64_t aInteger) {
1158   PrintfAppend<T> appender(this);
1159   bool r = appender.appendIntDec(aInteger);
1160   if (MOZ_UNLIKELY(!r)) {
1161     MOZ_CRASH("Allocation or other failure while appending integers");
1162   }
1163 }
1164
1165 template <typename T>
1166 void nsTSubstring<T>::AppendIntDec(uint64_t aInteger) {
1167   PrintfAppend<T> appender(this);
1168   bool r = appender.appendIntDec(aInteger);
1169   if (MOZ_UNLIKELY(!r)) {
1170     MOZ_CRASH("Allocation or other failure while appending integers");
1171   }
1172 }
1173
1174 template <typename T>
1175 void nsTSubstring<T>::AppendIntOct(uint64_t aInteger) {
1176   PrintfAppend<T> appender(this);
1177   bool r = appender.appendIntOct(aInteger);
1178   if (MOZ_UNLIKELY(!r)) {
1179     MOZ_CRASH("Allocation or other failure while appending integers");
1180   }
1181 }
1182
1183 template <typename T>
1184 void nsTSubstring<T>::AppendIntHex(uint64_t aInteger) {
1185   PrintfAppend<T> appender(this);
1186   bool r = appender.appendIntHex(aInteger);
1187   if (MOZ_UNLIKELY(!r)) {
1188     MOZ_CRASH("Allocation or other failure while appending integers");
1189   }
1190 }
1191
1192 // Returns the length of the formatted aDouble in aBuf.
1193 static int FormatWithoutTrailingZeros(char (&aBuf)[40], double aDouble,
1194                                       int aPrecision) {
1195   static const DoubleToStringConverter converter(
1196       DoubleToStringConverter::UNIQUE_ZERO |
1197           DoubleToStringConverter::NO_TRAILING_ZERO |
1198           DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN,
1199       "Infinity", "NaN", 'e', -6, 21, 6, 1);
1200   double_conversion::StringBuilder builder(aBuf, sizeof(aBuf));
1201   converter.ToPrecision(aDouble, aPrecision, &builder);
1202   int length = builder.position();
1203   builder.Finalize();
1204   return length;
1205 }
1206
1207 template <typename T>
1208 void nsTSubstring<T>::AppendFloat(float aFloat) {
1209   char buf[40];
1210   int length = FormatWithoutTrailingZeros(buf, aFloat, 6);
1211   AppendASCII(buf, length);
1212 }
1213
1214 template <typename T>
1215 void nsTSubstring<T>::AppendFloat(double aFloat) {
1216   char buf[40];
1217   int length = FormatWithoutTrailingZeros(buf, aFloat, 15);
1218   AppendASCII(buf, length);
1219 }
1220
1221 template <typename T>
1222 size_t nsTSubstring<T>::SizeOfExcludingThisIfUnshared(
1223     mozilla::MallocSizeOf aMallocSizeOf) const {
1224   if (this->mDataFlags & DataFlags::REFCOUNTED) {
1225     return mozilla::StringBuffer::FromData(this->mData)
1226         ->SizeOfIncludingThisIfUnshared(aMallocSizeOf);
1227   }
1228   if (this->mDataFlags & DataFlags::OWNED) {
1229     return aMallocSizeOf(this->mData);
1230   }
1231
1232   // If we reach here, exactly one of the following must be true:
1233   // - DataFlags::VOIDED is set, and this->mData points to sEmptyBuffer;
1234   // - DataFlags::INLINE is set, and this->mData points to a buffer within a
1235   //   string object (e.g. nsAutoString);
1236   // - None of DataFlags::REFCOUNTED, DataFlags::OWNED, DataFlags::INLINE is
1237   //   set, and this->mData points to a buffer owned by something else.
1238   //
1239   // In all three cases, we don't measure it.
1240   return 0;
1241 }
1242
1243 template <typename T>
1244 size_t nsTSubstring<T>::SizeOfExcludingThisEvenIfShared(
1245     mozilla::MallocSizeOf aMallocSizeOf) const {
1246   // This is identical to SizeOfExcludingThisIfUnshared except for the
1247   // DataFlags::REFCOUNTED case.
1248   if (this->mDataFlags & DataFlags::REFCOUNTED) {
1249     return mozilla::StringBuffer::FromData(this->mData)
1250         ->SizeOfIncludingThisEvenIfShared(aMallocSizeOf);
1251   }
1252   if (this->mDataFlags & DataFlags::OWNED) {
1253     return aMallocSizeOf(this->mData);
1254   }
1255   return 0;
1256 }
1257
1258 template <typename T>
1259 size_t nsTSubstring<T>::SizeOfIncludingThisIfUnshared(
1260     mozilla::MallocSizeOf aMallocSizeOf) const {
1261   return aMallocSizeOf(this) + SizeOfExcludingThisIfUnshared(aMallocSizeOf);
1262 }
1263
1264 template <typename T>
1265 size_t nsTSubstring<T>::SizeOfIncludingThisEvenIfShared(
1266     mozilla::MallocSizeOf aMallocSizeOf) const {
1267   return aMallocSizeOf(this) + SizeOfExcludingThisEvenIfShared(aMallocSizeOf);
1268 }
1269
1270 template <typename T>
1271 nsTSubstringSplitter<T> nsTSubstring<T>::Split(const char_type aChar) const {
1272   return nsTSubstringSplitter<T>(
1273       nsTCharSeparatedTokenizerTemplate<
1274           NS_TokenizerIgnoreNothing, T,
1275           nsTokenizerFlags::IncludeEmptyTokenAtEnd>(*this, aChar));
1276 }
1277
1278 // Common logic for nsTSubstring<T>::ToInteger and nsTSubstring<T>::ToInteger64.
1279 template <typename T, typename int_type>
1280 int_type ToIntegerCommon(const nsTSubstring<T>& aSrc, nsresult* aErrorCode,
1281                          uint32_t aRadix) {
1282   MOZ_ASSERT(aRadix == 10 || aRadix == 16);
1283
1284   // Initial value, override if we find an integer.
1285   *aErrorCode = NS_ERROR_ILLEGAL_VALUE;
1286
1287   // Begin by skipping over leading chars that shouldn't be part of the number.
1288   auto cp = aSrc.BeginReading();
1289   auto endcp = aSrc.EndReading();
1290   bool negate = false;
1291   bool done = false;
1292
1293   // NB: For backwards compatibility I'm not going to change this logic but
1294   //     it seems really odd. Previously there was logic to auto-detect the
1295   //     radix if kAutoDetect was passed in. In practice this value was never
1296   //     used, so it pretended to auto detect and skipped some preceding
1297   //     letters (excluding valid hex digits) but never used the result.
1298   //
1299   //     For example if you pass in "Get the number: 10", aRadix = 10 we'd
1300   //     skip the 'G', and then fail to parse "et the number: 10". If aRadix =
1301   //     16 we'd skip the 'G', and parse just 'e' returning 14.
1302   while ((cp < endcp) && (!done)) {
1303     switch (*cp++) {
1304         // clang-format off
1305       case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
1306       case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
1307       case '0': case '1': case '2': case '3': case '4':
1308       case '5': case '6': case '7': case '8': case '9':
1309         done = true;
1310         break;
1311       // clang-format on
1312       case '-':
1313         if constexpr (!std::is_signed_v<int_type>) {
1314           return 0;
1315         }
1316         negate = true;
1317         break;
1318       default:
1319         break;
1320     }
1321   }
1322
1323   if (!done) {
1324     // No base 16 or base 10 digits were found.
1325     return 0;
1326   }
1327
1328   // Step back.
1329   cp--;
1330
1331   mozilla::CheckedInt<int_type> result;
1332
1333   // Now iterate the numeric chars and build our result.
1334   while (cp < endcp) {
1335     auto theChar = *cp++;
1336     if (('0' <= theChar) && (theChar <= '9')) {
1337       result = (aRadix * result) + (theChar - '0');
1338     } else if ((theChar >= 'A') && (theChar <= 'F')) {
1339       if (10 == aRadix) {
1340         // Invalid base 10 digit, error out.
1341         return 0;
1342       }
1343       result = (aRadix * result) + ((theChar - 'A') + 10);
1344     } else if ((theChar >= 'a') && (theChar <= 'f')) {
1345       if (10 == aRadix) {
1346         // Invalid base 10 digit, error out.
1347         return 0;
1348       }
1349       result = (aRadix * result) + ((theChar - 'a') + 10);
1350     } else if ((('X' == theChar) || ('x' == theChar)) && result == 0) {
1351       // For some reason we support a leading 'x' regardless of radix. For
1352       // example: "000000x500", aRadix = 10 would be parsed as 500 rather
1353       // than 0.
1354       continue;
1355     } else {
1356       // We've encountered a char that's not a legal number or sign and we can
1357       // terminate processing.
1358       break;
1359     }
1360
1361     if (!result.isValid()) {
1362       // Overflow!
1363       return 0;
1364     }
1365   }
1366
1367   // Integer found.
1368   *aErrorCode = NS_OK;
1369
1370   if (negate) {
1371     result = -result;
1372   }
1373
1374   return result.value();
1375 }
1376
1377 template <typename T>
1378 int32_t nsTSubstring<T>::ToInteger(nsresult* aErrorCode,
1379                                    uint32_t aRadix) const {
1380   return ToIntegerCommon<T, int32_t>(*this, aErrorCode, aRadix);
1381 }
1382
1383 template <typename T>
1384 uint32_t nsTSubstring<T>::ToUnsignedInteger(nsresult* aErrorCode,
1385                                             uint32_t aRadix) const {
1386   return ToIntegerCommon<T, uint32_t>(*this, aErrorCode, aRadix);
1387 }
1388
1389 /**
1390  * nsTSubstring::ToInteger64
1391  */
1392 template <typename T>
1393 int64_t nsTSubstring<T>::ToInteger64(nsresult* aErrorCode,
1394                                      uint32_t aRadix) const {
1395   return ToIntegerCommon<T, int64_t>(*this, aErrorCode, aRadix);
1396 }
1397
1398 /**
1399  * nsTSubstring::Mid
1400  */
1401 template <typename T>
1402 typename nsTSubstring<T>::size_type nsTSubstring<T>::Mid(
1403     self_type& aResult, index_type aStartPos, size_type aLengthToCopy) const {
1404   if (aStartPos == 0 && aLengthToCopy >= this->mLength) {
1405     aResult = *this;
1406   } else {
1407     aResult = Substring(*this, aStartPos, aLengthToCopy);
1408   }
1409
1410   return aResult.mLength;
1411 }
1412
1413 /**
1414  * nsTSubstring::StripWhitespace
1415  */
1416
1417 template <typename T>
1418 void nsTSubstring<T>::StripWhitespace() {
1419   if (!StripWhitespace(mozilla::fallible)) {
1420     this->AllocFailed(this->mLength);
1421   }
1422 }
1423
1424 template <typename T>
1425 bool nsTSubstring<T>::StripWhitespace(const fallible_t&) {
1426   if (!this->EnsureMutable()) {
1427     return false;
1428   }
1429
1430   this->StripTaggedASCII(mozilla::ASCIIMask::MaskWhitespace());
1431   return true;
1432 }
1433
1434 /**
1435  * nsTSubstring::ReplaceChar,ReplaceSubstring
1436  */
1437
1438 template <typename T>
1439 void nsTSubstring<T>::ReplaceChar(char_type aOldChar, char_type aNewChar) {
1440   int32_t i = this->FindChar(aOldChar);
1441   if (i == kNotFound) {
1442     return;
1443   }
1444
1445   if (!this->EnsureMutable()) {
1446     this->AllocFailed(this->mLength);
1447   }
1448   for (; i != kNotFound; i = this->FindChar(aOldChar, i + 1)) {
1449     this->mData[i] = aNewChar;
1450   }
1451 }
1452
1453 template <typename T>
1454 void nsTSubstring<T>::ReplaceChar(const string_view& aSet, char_type aNewChar) {
1455   int32_t i = this->FindCharInSet(aSet);
1456   if (i == kNotFound) {
1457     return;
1458   }
1459
1460   if (!this->EnsureMutable()) {
1461     this->AllocFailed(this->mLength);
1462   }
1463   for (; i != kNotFound; i = this->FindCharInSet(aSet, i + 1)) {
1464     this->mData[i] = aNewChar;
1465   }
1466 }
1467
1468 template <typename T>
1469 void nsTSubstring<T>::ReplaceSubstring(const char_type* aTarget,
1470                                        const char_type* aNewValue) {
1471   ReplaceSubstring(nsTDependentString<T>(aTarget),
1472                    nsTDependentString<T>(aNewValue));
1473 }
1474
1475 template <typename T>
1476 bool nsTSubstring<T>::ReplaceSubstring(const char_type* aTarget,
1477                                        const char_type* aNewValue,
1478                                        const fallible_t& aFallible) {
1479   return ReplaceSubstring(nsTDependentString<T>(aTarget),
1480                           nsTDependentString<T>(aNewValue), aFallible);
1481 }
1482
1483 template <typename T>
1484 void nsTSubstring<T>::ReplaceSubstring(const self_type& aTarget,
1485                                        const self_type& aNewValue) {
1486   if (!ReplaceSubstring(aTarget, aNewValue, mozilla::fallible)) {
1487     // Note that this may wildly underestimate the allocation that failed, as
1488     // we could have been replacing multiple copies of aTarget.
1489     this->AllocFailed(this->mLength + (aNewValue.Length() - aTarget.Length()));
1490   }
1491 }
1492
1493 template <typename T>
1494 bool nsTSubstring<T>::ReplaceSubstring(const self_type& aTarget,
1495                                        const self_type& aNewValue,
1496                                        const fallible_t&) {
1497   struct Segment {
1498     uint32_t mBegin, mLength;
1499     Segment(uint32_t aBegin, uint32_t aLength)
1500         : mBegin(aBegin), mLength(aLength) {}
1501   };
1502
1503   if (aTarget.Length() == 0) {
1504     return true;
1505   }
1506
1507   // Remember all of the non-matching parts.
1508   AutoTArray<Segment, 16> nonMatching;
1509   uint32_t i = 0;
1510   mozilla::CheckedUint32 newLength;
1511   while (true) {
1512     int32_t r = this->Find(aTarget, i);
1513     int32_t until = (r == kNotFound) ? this->Length() - i : r - i;
1514     nonMatching.AppendElement(Segment(i, until));
1515     newLength += until;
1516     if (r == kNotFound) {
1517       break;
1518     }
1519
1520     newLength += aNewValue.Length();
1521     i = r + aTarget.Length();
1522     if (i >= this->Length()) {
1523       // Add an auxiliary entry at the end of the list to help as an edge case
1524       // for the algorithms below.
1525       nonMatching.AppendElement(Segment(this->Length(), 0));
1526       break;
1527     }
1528   }
1529
1530   if (!newLength.isValid()) {
1531     return false;
1532   }
1533
1534   // If there's only one non-matching segment, then the target string was not
1535   // found, and there's nothing to do.
1536   if (nonMatching.Length() == 1) {
1537     MOZ_ASSERT(
1538         nonMatching[0].mBegin == 0 && nonMatching[0].mLength == this->Length(),
1539         "We should have the correct non-matching segment.");
1540     return true;
1541   }
1542
1543   // Make sure that we can mutate our buffer.
1544   // Note that we always allocate at least an this->mLength sized buffer,
1545   // because the rest of the algorithm relies on having access to all of the
1546   // original string.  In other words, we over-allocate in the shrinking case.
1547   uint32_t oldLen = this->Length();
1548   auto r =
1549       this->StartBulkWriteImpl(XPCOM_MAX(oldLen, newLength.value()), oldLen);
1550   if (r.isErr()) {
1551     return false;
1552   }
1553
1554   if (aTarget.Length() >= aNewValue.Length()) {
1555     // In the shrinking case, start filling the buffer from the beginning.
1556     const uint32_t delta = (aTarget.Length() - aNewValue.Length());
1557     for (i = 1; i < nonMatching.Length(); ++i) {
1558       // When we move the i'th non-matching segment into position, we need to
1559       // account for the characters deleted by the previous |i| replacements by
1560       // subtracting |i * delta|.
1561       const char_type* sourceSegmentPtr = this->mData + nonMatching[i].mBegin;
1562       char_type* destinationSegmentPtr =
1563           this->mData + nonMatching[i].mBegin - i * delta;
1564       // Write the i'th replacement immediately before the new i'th non-matching
1565       // segment.
1566       char_traits::copy(destinationSegmentPtr - aNewValue.Length(),
1567                         aNewValue.Data(), aNewValue.Length());
1568       char_traits::move(destinationSegmentPtr, sourceSegmentPtr,
1569                         nonMatching[i].mLength);
1570     }
1571   } else {
1572     // In the growing case, start filling the buffer from the end.
1573     const uint32_t delta = (aNewValue.Length() - aTarget.Length());
1574     for (i = nonMatching.Length() - 1; i > 0; --i) {
1575       // When we move the i'th non-matching segment into position, we need to
1576       // account for the characters added by the previous |i| replacements by
1577       // adding |i * delta|.
1578       const char_type* sourceSegmentPtr = this->mData + nonMatching[i].mBegin;
1579       char_type* destinationSegmentPtr =
1580           this->mData + nonMatching[i].mBegin + i * delta;
1581       char_traits::move(destinationSegmentPtr, sourceSegmentPtr,
1582                         nonMatching[i].mLength);
1583       // Write the i'th replacement immediately before the new i'th non-matching
1584       // segment.
1585       char_traits::copy(destinationSegmentPtr - aNewValue.Length(),
1586                         aNewValue.Data(), aNewValue.Length());
1587     }
1588   }
1589
1590   // Adjust the length and make sure the string is null terminated.
1591   this->FinishBulkWriteImpl(newLength.value());
1592
1593   return true;
1594 }
1595
1596 /**
1597  * nsTSubstring::Trim
1598  */
1599
1600 template <typename T>
1601 void nsTSubstring<T>::Trim(const std::string_view& aSet, bool aTrimLeading,
1602                            bool aTrimTrailing, bool aIgnoreQuotes) {
1603   char_type* start = this->mData;
1604   char_type* end = this->mData + this->mLength;
1605
1606   // skip over quotes if requested
1607   if (aIgnoreQuotes && this->mLength > 2 &&
1608       this->mData[0] == this->mData[this->mLength - 1] &&
1609       (this->mData[0] == '\'' || this->mData[0] == '"')) {
1610     ++start;
1611     --end;
1612   }
1613
1614   if (aTrimLeading) {
1615     uint32_t cutStart = start - this->mData;
1616     uint32_t cutLength = 0;
1617
1618     // walk forward from start to end
1619     for (; start != end; ++start, ++cutLength) {
1620       if ((*start & ~0x7F) ||  // non-ascii
1621           aSet.find(char(*start)) == std::string_view::npos) {
1622         break;
1623       }
1624     }
1625
1626     if (cutLength) {
1627       this->Cut(cutStart, cutLength);
1628
1629       // reset iterators
1630       start = this->mData + cutStart;
1631       end = this->mData + this->mLength - cutStart;
1632     }
1633   }
1634
1635   if (aTrimTrailing) {
1636     uint32_t cutEnd = end - this->mData;
1637     uint32_t cutLength = 0;
1638
1639     // walk backward from end to start
1640     --end;
1641     for (; end >= start; --end, ++cutLength) {
1642       if ((*end & ~0x7F) ||  // non-ascii
1643           aSet.find(char(*end)) == std::string_view::npos) {
1644         break;
1645       }
1646     }
1647
1648     if (cutLength) {
1649       this->Cut(cutEnd - cutLength, cutLength);
1650     }
1651   }
1652 }
1653
1654 /**
1655  * nsTSubstring::CompressWhitespace.
1656  */
1657
1658 template <typename T>
1659 void nsTSubstring<T>::CompressWhitespace(bool aTrimLeading,
1660                                          bool aTrimTrailing) {
1661   // Quick exit
1662   if (this->mLength == 0) {
1663     return;
1664   }
1665
1666   if (!this->EnsureMutable()) {
1667     this->AllocFailed(this->mLength);
1668   }
1669
1670   const ASCIIMaskArray& mask = mozilla::ASCIIMask::MaskWhitespace();
1671
1672   char_type* to = this->mData;
1673   char_type* from = this->mData;
1674   char_type* end = this->mData + this->mLength;
1675
1676   // Compresses runs of whitespace down to a normal space ' ' and convert
1677   // any whitespace to a normal space.  This assumes that whitespace is
1678   // all standard 7-bit ASCII.
1679   bool skipWS = aTrimLeading;
1680   while (from < end) {
1681     uint32_t theChar = *from++;
1682     if (mozilla::ASCIIMask::IsMasked(mask, theChar)) {
1683       if (!skipWS) {
1684         *to++ = ' ';
1685         skipWS = true;
1686       }
1687     } else {
1688       *to++ = theChar;
1689       skipWS = false;
1690     }
1691   }
1692
1693   // If we need to trim the trailing whitespace, back up one character.
1694   if (aTrimTrailing && skipWS && to > this->mData) {
1695     to--;
1696   }
1697
1698   *to = char_type(0);  // add the null
1699   this->mLength = to - this->mData;
1700 }
1701
1702 template class nsTSubstring<char>;
1703 template class nsTSubstring<char16_t>;