/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2013 Apple Inc. All rights
 * reserved.
 * Copyright (C) 2009 Google Inc. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 */

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_IMPL_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_IMPL_H_

#include <hwy/highway.h>
#include <limits.h>
#include <string.h>

#include <array>
#include <atomic>
#include <functional>
#include <new>

#include "base/check_op.h"
#include "base/compiler_specific.h"
#include "base/containers/span.h"
#include "base/dcheck_is_on.h"
#include "base/functional/callback_forward.h"
#include "base/memory/ref_counted.h"
#include "base/numerics/checked_math.h"
#include "base/numerics/safe_conversions.h"
#include "build/build_config.h"
#include "partition_alloc/partition_alloc_constants.h"
#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
#include "third_party/blink/renderer/platform/wtf/forward.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"
#include "third_party/blink/renderer/platform/wtf/text/ascii_ctype.h"
#include "third_party/blink/renderer/platform/wtf/text/ascii_fast_path.h"
#include "third_party/blink/renderer/platform/wtf/text/number_parsing_options.h"
#include "third_party/blink/renderer/platform/wtf/text/string_hasher.h"
#include "third_party/blink/renderer/platform/wtf/text/wtf_uchar.h"
#include "third_party/blink/renderer/platform/wtf/vector.h"
#include "third_party/blink/renderer/platform/wtf/wtf_export.h"

#if BUILDFLAG(IS_APPLE)
#include "base/apple/scoped_cftyperef.h"

typedef const struct __CFString* CFStringRef;
#endif

#ifdef __OBJC__
@class NSString;
#endif

namespace blink {

class AtomicStringTable;

enum TextCaseSensitivity {
  kTextCaseSensitive,
  kTextCaseAsciiInsensitive,
};

// Computes a standard StringHasher string for the given buffer,
// with the caveat that the buffer may contain 8-bit data only.
// In that case, it is converted from UChar to LChar on the fly,
// so that we return the same hash as if we hashed the string as
// LChar to begin with. This ensures that the same code points
// are hashed to the same value, even if someone called e.g.
// Ensure16Bit() on the string at some point.
WTF_EXPORT unsigned ComputeHashForWideString(base::span<const UChar> str);

enum StripBehavior { kStripExtraWhiteSpace, kDoNotStripWhiteSpace };

typedef bool (*CharacterMatchFunctionPtr)(UChar);
typedef bool (*IsWhiteSpaceFunctionPtr)(UChar);
typedef HashMap<wtf_size_t, StringImpl*, AlreadyHashedTraits>
    StaticStringsTable;

// You can find documentation about this class in this doc:
// https://chromium.googlesource.com/chromium/src/+/HEAD/third_party/blink/renderer/platform/wtf/text/README.md
class WTF_EXPORT StringImpl {
 public:
  using size_type = wtf_size_t;
  static constexpr size_type npos = kNotFound;

 private:
  // StringImpls are allocated out of the WTF buffer partition.
  void* operator new(size_t);
  void* operator new(size_t, void* ptr) { return ptr; }
  void operator delete(StringImpl* impl, std::destroying_delete_t);

  // Used to construct static strings, which have a special ref_count_ that can
  // never hit zero. This means that the static string will never be destroyed.
  enum ConstructEmptyStringTag { kConstructEmptyString };
  explicit StringImpl(ConstructEmptyStringTag)
      : length_(0),
        hash_and_flags_(kAsciiPropertyCheckDone | kContainsOnlyAscii |
                        kIsLowerAscii | kIs8Bit | kIsStatic) {
    // Ensure that the hash is computed so that AtomicStringHash can call
    // existingHash() with impunity. The empty string is special because it
    // is never entered into AtomicString's HashKey, but still needs to
    // compare correctly.
    GetHash();
  }

  enum ConstructEmptyString16BitTag { kConstructEmptyString16Bit };
  explicit StringImpl(ConstructEmptyString16BitTag)
      : length_(0),
        hash_and_flags_(kAsciiPropertyCheckDone | kContainsOnlyAscii |
                        kIsLowerAscii | kIsStatic) {
    GetHash();
  }

  // FIXME: there has to be a less hacky way to do this.
  enum Force8Bit { kForce8BitConstructor };
  StringImpl(size_type length, Force8Bit)
      : length_(length), hash_and_flags_(LengthToAsciiFlags(length) | kIs8Bit) {
    DCHECK(length_);
  }

  StringImpl(size_type length)
      : length_(length), hash_and_flags_(LengthToAsciiFlags(length)) {
    DCHECK(length_);
  }

  enum StaticStringTag { kStaticString };
  StringImpl(size_type length, wtf_size_t hash, StaticStringTag)
      : length_(length),
        hash_and_flags_(hash << kHashShift | LengthToAsciiFlags(length) |
                        kIs8Bit | kIsStatic) {}

 public:
  REQUIRE_ADOPTION_FOR_REFCOUNTED_TYPE();
  static StringImpl* empty_;
  static StringImpl* empty16_bit_;

  StringImpl(const StringImpl&) = delete;
  StringImpl& operator=(const StringImpl&) = delete;
  ~StringImpl();

  static void InitStatics();

  static StringImpl* CreateStatic(base::span<const char> string);
  static void ReserveStaticStringsCapacityForSize(wtf_size_t size);
  static void FreezeStaticStrings();
  static const StaticStringsTable& AllStaticStrings();
  static size_type HighestStaticStringLength() {
    return highest_static_string_length_;
  }

  static scoped_refptr<StringImpl> Create(base::span<const UChar>);
  static scoped_refptr<StringImpl> Create(base::span<const LChar>);
  static scoped_refptr<StringImpl> Create(
      base::span<const LChar>,
      AsciiStringAttributes ascii_attributes);
  static scoped_refptr<StringImpl> Create8BitIfPossible(
      base::span<const UChar>);

  ALWAYS_INLINE static scoped_refptr<StringImpl> Create(
      base::span<const char> s) {
    return Create(base::as_bytes(s));
  }

  // Create a StringImpl with space for `length` LChar characters. `data` will
  // be the character data allocated, and _must_be_completely_filled_in_ by the
  // caller.
  static scoped_refptr<StringImpl> CreateUninitialized(size_t length,
                                                       base::span<LChar>& data);
  // Create a StringImpl with space for `length` UChar characters. `data` will
  // be the character data allocated, and _must_be_completely_filled_in_ by the
  // caller.
  static scoped_refptr<StringImpl> CreateUninitialized(size_t length,
                                                       base::span<UChar>& data);

  size_type length() const { return length_; }
  bool Is8Bit() const {
    return hash_and_flags_.load(std::memory_order_relaxed) & kIs8Bit;
  }

  ALWAYS_INLINE base::span<const LChar> Span8() const {
    DCHECK(Is8Bit());
    return CharacterBuffer<LChar>();
  }
  ALWAYS_INLINE base::span<const UChar> Span16() const {
    DCHECK(!Is8Bit());
    return CharacterBuffer<UChar>();
  }
  ALWAYS_INLINE base::span<const uint16_t> SpanUint16() const {
    DCHECK(!Is8Bit());
    return CharacterBuffer<uint16_t>();
  }
  ALWAYS_INLINE base::span<const uint8_t> RawByteSpan() const {
    // SAFETY: The AllocationSize<CharType>() helper function computes a size
    // that includes `length_` UChar/LChar characters in addition to the size
    // required for the StringImpl.
    return UNSAFE_BUFFERS(base::span(base::unchecked,
                                     reinterpret_cast<const uint8_t*>(this + 1),
                                     CharactersSizeInBytes()));
  }
  // Create a new std::u16string based on this.
  // The character content is always copied.
  std::u16string ToU16String() const;

  template <typename CharType>
  ALWAYS_INLINE base::span<CharType> Span() const;

  size_t CharactersSizeInBytes() const {
    return length() * (Is8Bit() ? sizeof(LChar) : sizeof(UChar));
  }

  ALWAYS_INLINE size_t GetAllocatedSize() const;

  bool IsAtomic() const {
    return hash_and_flags_.load(std::memory_order_acquire) & kIsAtomic;
  }

  void SetIsAtomic() {
    hash_and_flags_.fetch_or(kIsAtomic, std::memory_order_release);
  }

  void UnsetIsAtomic() {
    hash_and_flags_.fetch_and(~kIsAtomic, std::memory_order_release);
  }

  bool IsStatic() const {
    return hash_and_flags_.load(std::memory_order_relaxed) & kIsStatic;
  }

  bool ContainsOnlyAsciiOrEmpty() const;
  bool ContainsNoAsciiUpper() const;

  // The high bits of 'hash' are always empty, but we prefer to store our
  // flags in the low bits because it makes them slightly more efficient to
  // access.  So, we shift left and right when setting and getting our hash
  // code.
  void SetHash(wtf_size_t hash) const {
    // Multiple clients assume that StringHasher is the canonical string
    // hash function.
    DCHECK_EQ(
        hash,
        (Is8Bit() ? StringHasher::ComputeHashAndMaskTop8Bits(
                        reinterpret_cast<const char*>(Span8().data()), length_)
                  : ComputeHashForWideString(Span16())));
    DCHECK(hash);  // Verify that 0 is a valid sentinel hash value.
    SetHashRaw(hash);
  }

  bool HasHash() const { return GetHashRaw() != 0; }

  wtf_size_t ExistingHash() const {
    DCHECK(HasHash());
    return GetHashRaw();
  }

  wtf_size_t GetHash() const {
    if (wtf_size_t hash = GetHashRaw())
      return hash;
    return HashSlowCase();
  }

  ALWAYS_INLINE bool HasOneRef() const {
    return ref_count_.load(std::memory_order_acquire) == 1;
  }

  ALWAYS_INLINE void AddRef() const {
    if (!IsStatic()) {
      uint32_t previous_ref_count =
          ref_count_.fetch_add(1, std::memory_order_relaxed);
      CHECK_NE(previous_ref_count, std::numeric_limits<uint32_t>::max());
#if DCHECK_IS_ON()
      ref_count_change_count_++;
#endif
    }
  }

  // We explicitly remove the AddRef and Release operations from the tsan
  // bots because even though all data races in the C++ memory model sense
  // are undefined behavior, the use of atomics prevents a data race on
  // ref_count_ itself.

  // Sharing the AtomicStringTable causes other races outside of ref_count_
  // that could lead to an early deletion of the StringImpl while other
  // threads are still holding references to it.
  // Possible races:
  // 1. Races where ref_count_ doesn't reach zero are not harmful.
  // 2. Races involving only release calls are not harmful. The
  //    atomicity of the operations guarantee that only the last subtraction to
  //    be executed will trigger the deletion of the StringImpl.
  // 3. A fetch_add on thread A is ordered after a fetch_sub on thread B that
  //    reaches 0. This can only happen on an AddRef() reached through the
  //    AtomicStringTable::Add* methods, otherwise there should be another
  //    reference on thread A, and the Release() on thread B could not have
  //    reached 0. This race is mitigated by the fact that the Atomic String
  //    Table Add and Removal operations (including the fetch_sub to 0) are
  //    done under a lock.

  ALWAYS_INLINE void Release() {
    if (!IsStatic()) {
      // This can be relaxed: if it observes the last reference,
      // DestroyIfNeeded() performs the acquire load before checking flags.
      // Successful non-final decrements only need release ordering to publish
      // prior writes through the ref_count_ release sequence.
      uint32_t current_ref = ref_count_.load(std::memory_order_relaxed);
#if DCHECK_IS_ON()
      // In non-DCHECK builds, we can save a bit of time in micro-benchmarks by
      // not checking the arithmetic. We hope that checking in DCHECK builds is
      // enough to catch implementation bugs, and that implementation bugs are
      // the only way we'd experience underflow.
      DCHECK_NE(current_ref, 0u);
      ref_count_change_count_++;
#endif
      // This is a fancy fetch_sub() that allows the actual decrement to 0 to
      // be delegated to the DestroyIfNeeded() function. The result of this
      // compare_exchange_weak() will never be 0. Without this, there would be
      // a potential race by reaching 0 and calling AddRef and Release on
      // another thread before the deletion of the string in this thread,
      // triggering the removal and destruction of the string twice.
      do {
        if (current_ref == 1) {
          DestroyIfNeeded();
          return;
        }
      } while (!ref_count_.compare_exchange_weak(current_ref, current_ref - 1,
                                                 std::memory_order_release,
                                                 std::memory_order_relaxed));
    }
  }

#if DCHECK_IS_ON()
  unsigned int RefCountChangeCountForTesting() const {
    return ref_count_change_count_;
  }
  void ResetRefCountChangeCountForTesting() { ref_count_change_count_ = 0; }
#endif

  ALWAYS_INLINE void Adopted() const {}

  // FIXME: Does this really belong in StringImpl?
  template <typename T>
  static void CopyChars(base::span<T> destination, base::span<const T> source) {
    destination.copy_from(source);
  }

#if HWY_TARGET != HWY_SCALAR
  ALWAYS_INLINE static void SimdCopyChars(base::span<UChar> destination,
                                          base::span<const LChar> source) {
    namespace hw = hwy::HWY_NAMESPACE;

    constexpr hw::FixedTag<uint16_t, 8> d16;
    constexpr hw::FixedTag<uint8_t, 16> d8;
    HWY_LANES_CONSTEXPR size_t kLanes = hw::Lanes(d8);

    const size_t length = source.size();
    const LChar* src = source.data();
    UChar* dst = destination.data();

    // SAFETY: The SIMD code requires raw buffer access.
    UNSAFE_BUFFERS({
      size_t i = 0;
      if (length >= kLanes) {
        for (; i + kLanes <= length; i += kLanes) {
          const auto v8 = hw::LoadU(d8, src + i);
          const auto v16_low = hw::PromoteLowerTo(d16, v8);
          const auto v16_high = hw::PromoteUpperTo(d16, v8);
          hw::StoreU(v16_low, d16, reinterpret_cast<uint16_t*>(dst + i));
          hw::StoreU(v16_high, d16,
                     reinterpret_cast<uint16_t*>(dst + i + hw::Lanes(d16)));
        }
      }

      for (; i < length; ++i) {
        dst[i] = src[i];
      }
    });
  }
#endif  // HWY_TARGET != HWY_SCALAR

  ALWAYS_INLINE static void CopyChars(base::span<UChar> destination,
                                      base::span<const LChar> source) {
    CHECK_EQ(destination.size(), source.size());

#if HWY_TARGET != HWY_SCALAR
    return SimdCopyChars(destination, source);
#else
    for (size_t i = 0; i < source.size(); ++i) {
      destination[i] = source[i];
    }
#endif  // HWY_TARGET != HWY_SCALAR
  }

  // It is no longer required to create isolated copies for thread-safety
  // purposes.
  scoped_refptr<StringImpl> IsolatedCopy() const;

  scoped_refptr<StringImpl> Substring(size_type pos,
                                      size_type len = npos) const;

  // PRECONDITIONS: `i` must be less than `length`.
  UNSAFE_BUFFER_USAGE UChar operator[](size_type i) const {
    SECURITY_DCHECK(i < length_);
    // SAFETY: Performance sensitive. Safety required from caller, enforced
    // by UNSAFE_BUFFER_USAGE.
    UNSAFE_BUFFERS({
      if (Is8Bit()) {
        return reinterpret_cast<const LChar*>(this + 1)[i];
      }
      return reinterpret_cast<const UChar*>(this + 1)[i];
    });
  }
  UChar32 CodePointAtOrZero(size_type);

  bool ContainsOnlyWhitespaceOrEmpty();

  scoped_refptr<StringImpl> ToAsciiLower();
  scoped_refptr<StringImpl> ToAsciiUpper();

  scoped_refptr<StringImpl> Fill(UChar);
  // FIXME: Do we need fill(char) or can we just do the right thing if UChar is
  // ASCII?
  scoped_refptr<StringImpl> FoldCase();

  size_type LengthWithStrippedWhiteSpace() const;

  scoped_refptr<StringImpl> StripWhiteSpace();
  scoped_refptr<StringImpl> StripWhiteSpace(IsWhiteSpaceFunctionPtr);
  scoped_refptr<StringImpl> SimplifyWhiteSpace(
      StripBehavior = kStripExtraWhiteSpace);
  scoped_refptr<StringImpl> SimplifyWhiteSpace(
      IsWhiteSpaceFunctionPtr,
      StripBehavior = kStripExtraWhiteSpace);

  scoped_refptr<StringImpl> RemoveCharacters(CharacterMatchFunctionPtr);
  template <typename CharType>
  ALWAYS_INLINE scoped_refptr<StringImpl> RemoveCharacters(
      base::span<const CharType> characters,
      CharacterMatchFunctionPtr);

  // Remove characters between [start, start+lengthToRemove). The range is
  // clamped to the size of the string. Does nothing if start >= length().
  scoped_refptr<StringImpl> Remove(size_type start,
                                   size_type length_to_remove = 1);

  // Find characters.
  size_type Find(LChar character, size_type start = 0) const;
  size_type Find(char character, size_type start = 0) const;
  size_type Find(UChar character, size_type start = 0) const;
  size_type Find(CharacterMatchFunctionPtr, size_type index = 0) const;
  size_type Find(base::RepeatingCallback<bool(UChar)> match_callback,
                 size_type index = 0) const;

  // Find substrings.
  size_type Find(const StringView&, size_type index = 0) const;
  // Unicode aware case insensitive string matching. Non-ASCII characters might
  // match to ASCII characters. This function is rarely used to implement web
  // platform features.  See crbug.com/40476285.
  size_type DeprecatedFindIgnoringCase(const StringView&,
                                       size_type index = 0) const;
  size_type FindIgnoringAsciiCase(const StringView&, size_type index = 0) const;

  size_type ReverseFind(UChar, size_type index = npos) const;
  size_type ReverseFind(const StringView&, size_type index = npos) const;

  bool StartsWith(UChar) const;
  bool StartsWith(const StringView&) const;
  // Unicode aware case insensitive string matching. Non-ASCII characters might
  // match to ASCII characters. This function is rarely used to implement web
  // platform features.  See crbug.com/40476285.
  bool DeprecatedStartsWithIgnoringCase(const StringView&) const;
  bool StartsWithIgnoringCaseAndAccents(const StringView&) const;
  bool StartsWithIgnoringAsciiCase(const StringView&) const;

  bool EndsWith(UChar) const;
  bool EndsWith(const StringView&) const;
  // Unicode aware case insensitive string matching. Non-ASCII characters might
  // match to ASCII characters. This function is rarely used to implement web
  // platform features.  See crbug.com/40476285.
  bool DeprecatedEndsWithIgnoringCase(const StringView&) const;
  bool EndsWithIgnoringAsciiCase(const StringView&) const;

  // Replace parts of the string.
  scoped_refptr<StringImpl> Replace(UChar pattern, UChar replacement);
  scoped_refptr<StringImpl> Replace(UChar pattern,
                                    const StringView& replacement);
  scoped_refptr<StringImpl> Replace(const StringView& pattern,
                                    const StringView& replacement);
  scoped_refptr<StringImpl> Replace(size_type index,
                                    size_type length_to_replace,
                                    const StringView& replacement);

  scoped_refptr<StringImpl> UpconvertedString();

  // Copy characters from string starting at `start` up until the size of
  // `buffer` or the end of the string is reached. Returns the actual number of
  // characters copied.
  size_t CopyTo(base::span<UChar> buffer, size_type start) const;

  // Append characters from this string into a buffer. Expects the buffer to
  // have the methods:
  //    append(const UChar*, wtf_size_t length);
  //    append(const LChar*, wtf_size_t length);
  // StringBuilder and Vector conform to this protocol.
  template <typename BufferType>
  void AppendTo(BufferType&,
                size_type start = 0,
                size_type length = npos) const;

#if BUILDFLAG(IS_APPLE)
  base::apple::ScopedCFTypeRef<CFStringRef> CreateCFString();
#endif
#ifdef __OBJC__
  operator NSString*();
#endif

  static const std::array<UChar, 256> kLatin1CaseFoldTable;

 private:
  friend class AtomicStringTable;
  enum Flags {
    // These two fields are never modified for the lifetime of the StringImpl.
    // It is therefore safe to read them with a relaxed operation.
    kIs8Bit = 1 << 0,
    kIsStatic = 1 << 1,

    // This is the only flag that can be both set and unset. It is safe to do
    // so because all accesses are mediated by the same atomic string table and
    // so protected by a mutex. Thus these accesses can also be relaxed.
    kIsAtomic = 1 << 2,

    // These bits are set atomically together. They are initially all
    // zero, and like the hash computation below, become non-zero only as part
    // of a single atomic bitwise or. Thus concurrent loads will always observe
    // either a state where the ASCII property check has not been completed and
    // all bits are zero, or a state where the state is fully populated.
    //
    // The reason kIsLowerAscii is cached but upper ascii is not is that
    // DOM attributes APIs require a lowercasing check making it fairly hot.
    kAsciiPropertyCheckDone = 1 << 3,
    kContainsOnlyAscii = 1 << 4,
    kIsLowerAscii = 1 << 5,

    // The last 24 bits (past kHashShift) are reserved for the hash.
    // These bits are all zero if the hash is uncomputed, and the hash is
    // atomically stored with bitwise or.
    //
    // Therefore a relaxed read can be used, and will either observe an
    // uncomputed hash (if the fetch_or is not yet visible on this thread)
    // or the correct hash (if it is). It is possible for a thread to compute
    // the hash for a second time if there is a race. This is safe, since
    // storing the same bits again with a bitwise or is idempotent.
  };

  // Hash value is 24 bits.
  constexpr static int kHashShift = (sizeof(unsigned) * 8) - 24;

  static inline constexpr uint32_t LengthToAsciiFlags(int length) {
    return length
               ? 0
               : kAsciiPropertyCheckDone | kContainsOnlyAscii | kIsLowerAscii;
  }

  static inline uint32_t AsciiStringAttributesToFlags(
      AsciiStringAttributes ascii_attributes) {
    uint32_t flags = kAsciiPropertyCheckDone;
    if (ascii_attributes.contains_only_ascii)
      flags |= kContainsOnlyAscii;
    if (ascii_attributes.is_lower_ascii)
      flags |= kIsLowerAscii;
    return flags;
  }

  void SetHashRaw(unsigned hash_val) const {
    // Setting the hash is idempotent so fetch_or() is sufficient. DCHECK()
    // as a sanity check.
    unsigned previous_value = hash_and_flags_.fetch_or(
        hash_val << kHashShift, std::memory_order_relaxed);
    DCHECK(((previous_value >> kHashShift) == 0) ||
           ((previous_value >> kHashShift) == hash_val));
  }

  unsigned GetHashRaw() const {
    return hash_and_flags_.load(std::memory_order_relaxed) >> kHashShift;
  }

  template <typename CharType>
  static size_t AllocationSize(size_type length) {
    static_assert(
        sizeof(CharType) > 1,
        "Don't use this template with 1-byte chars; use a template "
        "specialization to save time and code-size by avoiding a CheckMul.");
    return base::CheckAdd(sizeof(StringImpl),
                          base::CheckMul(length, sizeof(CharType)))
        .ValueOrDie();
  }

  template <typename CharType>
  ALWAYS_INLINE base::span<CharType> CharacterBuffer() {
    // SAFETY: The AllocationSize<CharType>() helper function computes a size
    // that includes `length_` UChar/LChar characters in addition to the size
    // required for the StringImpl.
    return UNSAFE_BUFFERS(base::span(
        base::unchecked, reinterpret_cast<CharType*>(this + 1), length_));
  }
  template <typename CharType>
  ALWAYS_INLINE base::span<const CharType> CharacterBuffer() const {
    return const_cast<StringImpl*>(this)->CharacterBuffer<CharType>();
  }

  template <typename DestCharType,
            typename SrcCharType,
            typename ReplacementCharType>
  void DoReplace(base::span<const SrcCharType> source,
                 UChar pattern,
                 base::span<const ReplacementCharType> replacement,
                 base::span<DestCharType> dest) const;
  template <typename DestCharType>
  void DoReplace(const StringView& pattern,
                 const StringView& replacement,
                 base::span<DestCharType> dest) const;

  template <class UCharPredicate>
  scoped_refptr<StringImpl> StripMatchedCharacters(UCharPredicate);
  template <typename CharType, class UCharPredicate>
  scoped_refptr<StringImpl> SimplifyMatchedCharactersToSpace(
      base::span<const CharType>,
      UCharPredicate,
      StripBehavior);
  NOINLINE wtf_size_t HashSlowCase() const;

  void DestroyIfNeeded();

  // Calculates the kContainsOnlyAscii and kIsLowerAscii flags. Returns
  // a bitfield with those 2 values.
  unsigned ComputeAsciiFlags() const;

#if DCHECK_IS_ON()
  std::string AsciiForDebugging() const;
#endif

  static size_type highest_static_string_length_;

#if DCHECK_IS_ON()
  void AssertHashIsCorrect() {
    DCHECK(HasHash());
    DCHECK_EQ(ExistingHash(),
              StringHasher::ComputeHashAndMaskTop8Bits(
                  reinterpret_cast<const char*>(Span8().data()), length()));
  }
#endif

#if DCHECK_IS_ON()
  mutable std::atomic<unsigned> ref_count_change_count_{0};
#endif
  // TODO (crbug.com/1083392): Use base::AtomicRefCount.
  mutable std::atomic_uint32_t ref_count_{1};
  const size_type length_;
  mutable std::atomic<uint32_t> hash_and_flags_;
};

// The maximum length of a 16-bit string such that its StringImpl allocation
// (header plus character data) fits within
// partition_alloc::MaxAllocationSize().
inline constexpr wtf_size_t kStringMaxUCharLength = static_cast<wtf_size_t>(
    (partition_alloc::MaxAllocationSize() - sizeof(StringImpl)) /
    sizeof(UChar));

template <>
ALWAYS_INLINE base::span<LChar> StringImpl::Span<LChar>() const {
  return const_cast<StringImpl*>(this)->CharacterBuffer<LChar>();
}

template <>
ALWAYS_INLINE base::span<UChar> StringImpl::Span<UChar>() const {
  return const_cast<StringImpl*>(this)->CharacterBuffer<UChar>();
}

// The following template specialization can be moved to the class declaration
// once we officially switch to C++17 (we need C++ DR727 to be implemented).
template <>
ALWAYS_INLINE size_t StringImpl::AllocationSize<LChar>(size_type length) {
  static_assert(sizeof(LChar) == 1, "sizeof(LChar) should be 1.");
  return base::CheckAdd(sizeof(StringImpl), length).ValueOrDie();
}

// EqualToCString() can be faster than operator== because operator== creates
// a StringView, and it requires strlen(latin1).
//
// `latin1` must not be nullptr, and should point Latin-1 characters.
WTF_EXPORT bool EqualToCString(const StringView& a, const char* latin1);
WTF_EXPORT bool EqualToCString(const StringImpl* a, const char* latin1);

WTF_EXPORT bool Equal(const StringImpl*, const StringImpl*);
WTF_EXPORT bool Equal(const StringImpl*, base::span<const LChar>);
WTF_EXPORT bool Equal(const StringImpl*, base::span<const UChar>);
inline bool Equal(const StringImpl* a, base::span<const char> b) {
  return Equal(a, base::as_bytes(b));
}
WTF_EXPORT bool EqualNonNull(const StringImpl* a, const StringImpl* b);

ALWAYS_INLINE bool StringImpl::ContainsOnlyAsciiOrEmpty() const {
  uint32_t flags = hash_and_flags_.load(std::memory_order_relaxed);
  if (flags & kAsciiPropertyCheckDone)
    return flags & kContainsOnlyAscii;
  return ComputeAsciiFlags() & kContainsOnlyAscii;
}

ALWAYS_INLINE size_t StringImpl::GetAllocatedSize() const {
  const size_t size = CharactersSizeInBytes() + sizeof(StringImpl);
  DCHECK(Is8Bit() ? size == AllocationSize<LChar>(length())
                  : size == AllocationSize<UChar>(length()));
  return size;
}

ALWAYS_INLINE bool StringImpl::ContainsNoAsciiUpper() const {
  uint32_t flags = hash_and_flags_.load(std::memory_order_relaxed);
  if (flags & kAsciiPropertyCheckDone)
    return flags & kIsLowerAscii;
  return ComputeAsciiFlags() & kIsLowerAscii;
}

// Unicode aware case insensitive string matching. Non-ASCII characters might
// match to ASCII characters. These functions are rarely used to implement web
// platform features.
// These functions are deprecated. Use EqualIgnoringAsciiCase(), or introduce
// EqualIgnoringUnicodeCase(). See crbug.com/627682
WTF_EXPORT bool DeprecatedEqualIgnoringCase(base::span<const LChar>,
                                            base::span<const LChar>);
WTF_EXPORT bool DeprecatedEqualIgnoringCase(base::span<const UChar>,
                                            base::span<const LChar>);
inline bool DeprecatedEqualIgnoringCase(base::span<const LChar> a,
                                        base::span<const UChar> b) {
  return DeprecatedEqualIgnoringCase(b, a);
}
WTF_EXPORT bool DeprecatedEqualIgnoringCase(base::span<const UChar>,
                                            base::span<const UChar>);

WTF_EXPORT bool EqualIgnoringNullity(StringImpl*, StringImpl*);

template <typename CharacterTypeA, typename CharacterTypeB>
inline bool EqualIgnoringAsciiCase(base::span<const CharacterTypeA> a,
                                   base::span<const CharacterTypeB> b) {
  CHECK_EQ(a.size(), b.size());
  size_t length = a.size();
  const CharacterTypeA* a_data = a.data();
  const CharacterTypeB* b_data = b.data();
  while (length--) {
    // Avoid base::span::operator[] for better performance.
    // SAFETY: This function ensures a_data and b_data move inside their spans,
    // since CHECK() above ensures a and b have same size.
    if (UNSAFE_BUFFERS(ToAsciiLower(*a_data++) != ToAsciiLower(*b_data++))) {
      return false;
    }
  }
  return true;
}

#if HWY_TARGET != HWY_SCALAR
ALWAYS_INLINE bool SimdEqualIgnoringAsciiCase(base::span<const LChar> a,
                                              base::span<const LChar> b) {
  namespace hw = hwy::HWY_NAMESPACE;
  constexpr hw::FixedTag<uint8_t, 16> d;
  HWY_LANES_CONSTEXPR size_t kLanes = hw::Lanes(d);

  // SAFETY: The SIMD code requires raw buffer access.
  UNSAFE_BUFFERS({
    size_t i = 0;
    if (a.size() >= kLanes) {
      const auto upper_A = hw::Set(d, 'A');
      const auto upper_Z = hw::Set(d, 'Z');
      const auto case_bit = hw::Set(d, 0x20);
      for (; i + kLanes <= a.size(); i += kLanes) {
        auto va = hw::LoadU(d, reinterpret_cast<const uint8_t*>(a.data() + i));
        auto vb = hw::LoadU(d, reinterpret_cast<const uint8_t*>(b.data() + i));
        auto is_upper_a = hw::And(hw::Ge(va, upper_A), hw::Le(va, upper_Z));
        va = hw::IfThenElse(is_upper_a, hw::Or(va, case_bit), va);
        auto is_upper_b = hw::And(hw::Ge(vb, upper_A), hw::Le(vb, upper_Z));
        vb = hw::IfThenElse(is_upper_b, hw::Or(vb, case_bit), vb);
        if (!hw::AllTrue(d, hw::Eq(va, vb))) {
          return false;
        }
      }
    }
    for (; i < a.size(); ++i) {
      if (ToAsciiLower(a.data()[i]) != ToAsciiLower(b.data()[i])) {
        return false;
      }
    }
  });
  return true;
}

ALWAYS_INLINE bool SimdEqualIgnoringAsciiCase(base::span<const UChar> a,
                                              base::span<const LChar> b) {
  namespace hw = hwy::HWY_NAMESPACE;
  constexpr hw::FixedTag<uint16_t, 8> d16;
  constexpr hw::FixedTag<uint8_t, 8> d8;
  HWY_LANES_CONSTEXPR size_t kLanes = hw::Lanes(d16);

  // SAFETY: The SIMD code requires raw buffer access.
  UNSAFE_BUFFERS({
    size_t i = 0;
    if (a.size() >= kLanes) {
      const auto upper_A = hw::Set(d16, 'A');
      const auto upper_Z = hw::Set(d16, 'Z');
      const auto case_bit = hw::Set(d16, 0x20);
      for (; i + kLanes <= a.size(); i += kLanes) {
        auto va =
            hw::LoadU(d16, reinterpret_cast<const uint16_t*>(a.data() + i));
        auto vb_8 =
            hw::LoadU(d8, reinterpret_cast<const uint8_t*>(b.data() + i));
        auto vb = hw::PromoteTo(d16, vb_8);
        auto is_upper_a = hw::And(hw::Ge(va, upper_A), hw::Le(va, upper_Z));
        va = hw::IfThenElse(is_upper_a, hw::Or(va, case_bit), va);
        auto is_upper_b = hw::And(hw::Ge(vb, upper_A), hw::Le(vb, upper_Z));
        vb = hw::IfThenElse(is_upper_b, hw::Or(vb, case_bit), vb);
        if (!hw::AllTrue(d16, hw::Eq(va, vb))) {
          return false;
        }
      }
    }
    for (; i < a.size(); ++i) {
      if (ToAsciiLower(a.data()[i]) != ToAsciiLower(b.data()[i])) {
        return false;
      }
    }
  });
  return true;
}

ALWAYS_INLINE bool SimdEqualIgnoringAsciiCase(base::span<const UChar> a,
                                              base::span<const UChar> b) {
  namespace hw = hwy::HWY_NAMESPACE;
  constexpr hw::FixedTag<uint16_t, 8> d;
  HWY_LANES_CONSTEXPR size_t kLanes = hw::Lanes(d);

  // SAFETY: The SIMD code requires raw buffer access.
  UNSAFE_BUFFERS({
    size_t i = 0;
    if (a.size() >= kLanes) {
      const auto upper_A = hw::Set(d, 'A');
      const auto upper_Z = hw::Set(d, 'Z');
      const auto case_bit = hw::Set(d, 0x20);
      for (; i + kLanes <= a.size(); i += kLanes) {
        auto va = hw::LoadU(d, reinterpret_cast<const uint16_t*>(a.data() + i));
        auto vb = hw::LoadU(d, reinterpret_cast<const uint16_t*>(b.data() + i));
        auto is_upper_a = hw::And(hw::Ge(va, upper_A), hw::Le(va, upper_Z));
        va = hw::IfThenElse(is_upper_a, hw::Or(va, case_bit), va);
        auto is_upper_b = hw::And(hw::Ge(vb, upper_A), hw::Le(vb, upper_Z));
        vb = hw::IfThenElse(is_upper_b, hw::Or(vb, case_bit), vb);
        if (!hw::AllTrue(d, hw::Eq(va, vb))) {
          return false;
        }
      }
    }
    for (; i < a.size(); ++i) {
      if (ToAsciiLower(a.data()[i]) != ToAsciiLower(b.data()[i])) {
        return false;
      }
    }
  });
  return true;
}
#endif  // HWY_TARGET != HWY_SCALAR

ALWAYS_INLINE bool EqualIgnoringAsciiCase(base::span<const LChar> a,
                                          base::span<const LChar> b) {
  CHECK_EQ(a.size(), b.size());
#if HWY_TARGET != HWY_SCALAR
  return SimdEqualIgnoringAsciiCase(a, b);
#else
  return EqualIgnoringAsciiCase<LChar, LChar>(a, b);
#endif  // HWY_TARGET != HWY_SCALAR
}

ALWAYS_INLINE bool EqualIgnoringAsciiCase(base::span<const UChar> a,
                                          base::span<const LChar> b) {
  CHECK_EQ(a.size(), b.size());
#if HWY_TARGET != HWY_SCALAR
  return SimdEqualIgnoringAsciiCase(a, b);
#else
  return EqualIgnoringAsciiCase<UChar, LChar>(a, b);
#endif  // HWY_TARGET != HWY_SCALAR
}

ALWAYS_INLINE bool EqualIgnoringAsciiCase(base::span<const LChar> a,
                                          base::span<const UChar> b) {
  return EqualIgnoringAsciiCase(b, a);
}

ALWAYS_INLINE bool EqualIgnoringAsciiCase(base::span<const UChar> a,
                                          base::span<const UChar> b) {
  CHECK_EQ(a.size(), b.size());
#if HWY_TARGET != HWY_SCALAR
  return SimdEqualIgnoringAsciiCase(a, b);
#else
  return EqualIgnoringAsciiCase<UChar, UChar>(a, b);
#endif  // HWY_TARGET != HWY_SCALAR
}

template <typename CharType>
inline wtf_size_t Find(base::span<const CharType> characters,
                       CharType match_character,
                       wtf_size_t index = 0) {
  if (index >= characters.size()) {
    return kNotFound;
  }
  // Pass raw pointers to std::find for better performance.
  const CharType* begin = base::to_address(characters.begin());
  const CharType* end = base::to_address(characters.end());
  const CharType* it = std::find(base::to_address(characters.begin() + index),
                                 end, match_character);
  return it == end ? kNotFound : CheckedDistance(begin, it);
}

ALWAYS_INLINE wtf_size_t Find(base::span<const UChar> characters,
                              LChar match_character,
                              wtf_size_t index = 0) {
  return Find(characters, static_cast<UChar>(match_character), index);
}

inline wtf_size_t Find(base::span<const LChar> characters,
                       UChar match_character,
                       wtf_size_t index = 0) {
  if (match_character & ~0xFF)
    return kNotFound;
  return Find(characters, static_cast<LChar>(match_character), index);
}

template <typename CharacterType>
inline wtf_size_t Find(base::span<const CharacterType> characters,
                       char match_character,
                       wtf_size_t index = 0) {
  return Find(characters, static_cast<LChar>(match_character), index);
}

template <typename CharType>
inline wtf_size_t Find(base::span<const CharType> characters,
                       CharacterMatchFunctionPtr match_function,
                       wtf_size_t index = 0) {
  if (index >= characters.size()) {
    return kNotFound;
  }
  // Pass raw pointers to std::find_if for better performance.
  const CharType* begin = base::to_address(characters.begin());
  const CharType* end = base::to_address(characters.end());
  const CharType* it = std::find_if(
      base::to_address(characters.begin() + index), end, match_function);
  return it == end ? kNotFound : CheckedDistance(begin, it);
}

template <typename CharType>
inline wtf_size_t ReverseFind(base::span<const CharType> characters,
                              CharacterMatchFunctionPtr match_function,
                              wtf_size_t index) {
  const wtf_size_t length = base::checked_cast<wtf_size_t>(characters.size());
  if (!length) {
    return kNotFound;
  }
  if (index >= length) {
    index = length - 1;
  }
  while (!match_function(characters[index])) {
    if (!index--) {
      return kNotFound;
    }
  }
  return index;
}

inline StringImpl::size_type StringImpl::Find(LChar character,
                                              size_type start) const {
  if (Is8Bit())
    return blink::Find(Span8(), character, start);
  return blink::Find(Span16(), character, start);
}

ALWAYS_INLINE StringImpl::size_type StringImpl::Find(char character,
                                                     size_type start) const {
  return Find(static_cast<LChar>(character), start);
}

inline StringImpl::size_type StringImpl::Find(UChar character,
                                              size_type start) const {
  if (Is8Bit())
    return blink::Find(Span8(), character, start);
  return blink::Find(Span16(), character, start);
}

// Null-terminated strings is generally discouraged as it has high chance to
// cause Buffer overflow.
UNSAFE_BUFFER_USAGE inline wtf_size_t LengthOfNullTerminatedString(
    const UChar* string) {
  size_t length = 0;
  while (string[length] != 0) {
    ++length;
  }
  return base::checked_cast<wtf_size_t>(length);
}

template <typename CharacterType1,
          typename CharacterType2,
          typename Projection = std::identity>
static inline int CodeUnitCompare(base::span<const CharacterType1> c1,
                                  base::span<const CharacterType2> c2,
                                  Projection proj = {}) {
  const size_t lmin = std::min(c1.size(), c2.size());
  size_t pos = 0;
  while (pos < lmin && proj(c1[pos]) == proj(c2[pos])) {
    ++pos;
  }
  if (pos < lmin) {
    return proj(c1[pos]) > proj(c2[pos]) ? 1 : -1;
  }
  if (c1.size() == c2.size()) {
    return 0;
  }
  return c1.size() > c2.size() ? 1 : -1;
}

static inline int CodeUnitCompare(const StringImpl* string1,
                                  const StringImpl* string2) {
  if (!string1)
    return (string2 && string2->length()) ? -1 : 0;

  if (!string2)
    return string1->length() ? 1 : 0;

  bool string1_is_8bit = string1->Is8Bit();
  bool string2_is_8bit = string2->Is8Bit();
  if (string1_is_8bit) {
    if (string2_is_8bit) {
      return CodeUnitCompare(string1->Span8(), string2->Span8());
    }
    return CodeUnitCompare(string1->Span8(), string2->Span16());
  }
  if (string2_is_8bit) {
    return -CodeUnitCompare(string2->Span8(), string1->Span16());
  }
  return CodeUnitCompare(string1->Span16(), string2->Span16());
}

inline scoped_refptr<StringImpl> StringImpl::IsolatedCopy() const {
  if (Is8Bit())
    return Create(Span8());
  return Create(Span16());
}

template <typename BufferType>
inline void StringImpl::AppendTo(BufferType& result,
                                 size_type start,
                                 size_type length) const {
  size_type number_of_characters_to_copy = std::min(length, length_ - start);
  if (!number_of_characters_to_copy)
    return;
  if (Is8Bit())
    result.append_range(Span8().subspan(start, number_of_characters_to_copy));
  else
    result.append_range(Span16().subspan(start, number_of_characters_to_copy));
}

template <typename T>
struct HashTraits;
// Defined in string_hash.h.
template <>
struct HashTraits<StringImpl*>;
template <>
struct HashTraits<scoped_refptr<StringImpl>>;

namespace internal {

// This is not in string_internal.h because this should be visible from
// wtf_string.h and we don't want to include string_internal.h from
// wtf_string.h.
template <typename StringType, typename FinderType, bool allow_empty_entries>
Vector<StringType> SplitByFinder(const StringType& input, FinderType finder) {
  Vector<StringType> result;
  if (input.empty()) {
    if (allow_empty_entries) {
      result.push_back(input);
    }
    return result;
  }

  auto input_view = input.subview(0);
  using size_type = typename StringType::size_type;
  size_type start_pos = 0;
  size_type current_pos = 0;

  while (current_pos < input.length()) {
    auto separator_length = finder(input_view, current_pos);
    if (separator_length) {
      auto sub = input.substr(start_pos, current_pos - start_pos);
      if (allow_empty_entries || !sub.empty()) {
        result.push_back(sub);
      }
      if (*separator_length == 0) {
        start_pos = current_pos;
        current_pos++;
      } else {
        current_pos += *separator_length;
        start_pos = current_pos;
      }
    } else {
      current_pos++;
    }
  }

  auto sub = input.substr(start_pos);
  if (allow_empty_entries || !sub.empty()) {
    result.push_back(sub);
  }

  return result;
}

}  // namespace internal

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_IMPL_H_