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