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