// Copyright 2016 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_VIEW_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_VIEW_H_

#include <cstring>
#include <type_traits>

#include "base/check.h"
#include "base/compiler_specific.h"
#include "base/containers/span.h"
#include "base/dcheck_is_on.h"
#include "base/numerics/safe_conversions.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/get_ptr.h"
#include "third_party/blink/renderer/platform/wtf/text/string_impl.h"

#if DCHECK_IS_ON()
#include "base/memory/scoped_refptr.h"
#endif

namespace blink {

class CodePointIterator;

enum class Utf8ConversionMode : uint8_t {
  // Unpaired surrogates are encoded using the standard UTF-8 encoding scheme,
  // even though surrogate characters should not be present in a valid UTF-8
  // string.
  kLenient,
  // Conversion terminates at the first unpaired surrogate, if any.
  kStrict,
  // Unpaired surrogates are replaced with U+FFFD (REPLACEMENT CHARACTER).
  kStrictReplacingErrors
};

// A string like object that wraps either an 8bit or 16bit byte sequence
// and keeps track of the length and the type, it does NOT own the bytes.
// This class is like std::string_view for blink::String.
//
// Since StringView does not own the bytes creating a StringView from a String,
// then replacing a StringImpl object in the String will result in a
// use-after-free. Asserts in ~StringView attempt to enforce this for most
// common cases.
//
// See https://abseil.io/tips/1 for more details.
//
// Unlike `std::string_view`, pass-by-value is not recommended because a
// `blink::StringView` instance consists of three words.
//
// When a method of this class is compatible with an equivalent method in
// `std::string_view`, we use the same method name as `std::string_view` (i.e.,
// `snake_case()`) rather than following the Google/Blink C++ style guide's
// naming rules. This improves consistency in string manipulation.
class WTF_EXPORT StringView {
  DISALLOW_NEW();

 public:
  using size_type = wtf_size_t;
  static constexpr size_type npos = kNotFound;

  // A buffer that allows for short strings to be held on the stack during a
  // transform. This is a performance optimization for very hot paths and
  // should rarely need to be used.
  class StackBackingStore {
   public:
    // Returns a span of size |length| that is valid for as long the
    // StackBackingStore object is alive and Realloc() has not been called
    // again.
    template <typename CharT>
    base::span<CharT> Realloc(wtf_size_t length) {
      size_t size = length * sizeof(CharT);
      if (size > sizeof(stackbuf16_)) [[unlikely]] {
        heapbuf_.reset(reinterpret_cast<char*>(
            Partitions::BufferMalloc(size, "StackBackingStore")));
        // SAFETY: `heapbuf_` is the result of BufferMalloc() for `length`.
        return UNSAFE_BUFFERS(base::span(
            base::unchecked, reinterpret_cast<CharT*>(heapbuf_.get()), length));
      }

      // If the Realloc() shrinks the buffer size, |heapbuf_| will keep a copy
      // of the old string. A reset can be added here, but given this is a
      // transient usage, deferring to the destructor is just as good and avoids
      // another branch.
      static_assert(alignof(decltype(stackbuf16_)) % alignof(CharT) == 0,
                    "stack buffer must be sufficiently aligned");
      // SAFETY: `length` is smaller than the size of `stackbuf16_`.
      return UNSAFE_BUFFERS(base::span(
          base::unchecked, reinterpret_cast<CharT*>(&stackbuf16_[0]), length));
    }

   public:
    struct BufferDeleter {
      void operator()(void* buffer) { Partitions::BufferFree(buffer); }
    };

    static_assert(sizeof(UChar) != sizeof(char),
                  "A char array will trigger -fstack-protect an produce "
                  "overkill stack canaries all over v8 bindings");

    // The size 64 is just a guess on a good size. No data was used in its
    // selection.
    UChar stackbuf16_[64];
    std::unique_ptr<char[], BufferDeleter> heapbuf_;
  };

  // [string.view.cons] ---------------------------------------------

  // Null string.
  StringView() { Clear(); }

  // From a StringView:
  StringView(const StringView&) = default;
  StringView(const StringView& view, size_type offset);
  StringView(const StringView&, size_type offset, size_type length);

  // From a StringImpl:
  StringView(const StringImpl*);
  StringView(const StringImpl*, size_type offset);
  StringView(const StringImpl*, size_type offset, size_type length);

  // From a non-null StringImpl.
  StringView(const StringImpl& impl)
      : impl_(const_cast<StringImpl*>(&impl)),
        bytes_(impl.RawByteSpan().data()),
        length_(impl.length()) {}

  // From a non-null StringImpl, avoids the null check.
  StringView(StringImpl& impl)
      : impl_(&impl),
        bytes_(impl.RawByteSpan().data()),
        length_(impl.length()) {}
  StringView(StringImpl&, size_type offset);
  StringView(StringImpl&, size_type offset, size_type length);

  // From a String, implemented in wtf_string.h
  inline StringView(const String& string LIFETIME_BOUND,
                    size_type offset,
                    size_type length);
  inline StringView(const String& string LIFETIME_BOUND, size_type offset);
  // NOLINTNEXTLINE(google-explicit-constructor)
  inline StringView(const String& string LIFETIME_BOUND);

  // From an AtomicString, implemented in atomic_string.h
  inline StringView(const AtomicString& string LIFETIME_BOUND,
                    size_type offset,
                    size_type length);
  inline StringView(const AtomicString& string LIFETIME_BOUND,
                    size_type offset);
  // NOLINTNEXTLINE(google-explicit-constructor)
  inline StringView(const AtomicString& string LIFETIME_BOUND);

  // From a literal string or LChar buffer:
  explicit StringView(base::span<const LChar> chars)
      : impl_(StringImpl::empty_),
        bytes_(chars.data()),
        length_(base::checked_cast<size_type>(chars.size())) {}
  // NOLINTNEXTLINE(google-explicit-constructor)
  StringView(const char* chars)
      : impl_(StringImpl::empty_),
        bytes_(chars),
        length_(chars ? base::checked_cast<size_type>(strlen(chars)) : 0) {}

  // From a wide literal string or UChar buffer.
  explicit StringView(base::span<const UChar> chars)
      : impl_(StringImpl::empty16_bit_),
        bytes_(chars.data()),
        length_(base::checked_cast<size_type>(chars.size())) {}
  // NOLINTNEXTLINE(google-explicit-constructor)
  StringView(const UChar* chars);

  // StringView(const T*, size_type) are deleted explicitly because `const T*`
  // is converted to a StringView implicitly and StringView(const StringView&,
  // size_type offset) would be used unexpectedly.
  StringView(const LChar*, size_type) = delete;
  StringView(const char*, size_type) = delete;
  StringView(const UChar*, size_type) = delete;

  StringView& operator=(const StringView&) = default;

#if DCHECK_IS_ON()
  ~StringView();
#endif

  // [string.view.iterators] ----------------------------------------

  // Iterator support
  //
  // begin() and end() return iterators for UChar32, neither UChar nor LChar.
  // If you'd like to iterate code units, just use [] and length().
  //
  // * Iterate code units
  //    for (wtf_size_t i = 0; i < view.length(); ++i) {
  //      UChar code_unit = view[i];
  //      ...
  // * Iterate code points
  //    for (UChar32 code_point : view) {
  //      ...
  CodePointIterator begin() const;
  CodePointIterator end() const;

  // [string.view.capacity] -----------------------------------------

  size_type length() const { return length_; }
  bool empty() const { return !length_; }

  bool IsNull() const { return !bytes_; }

  void Clear();

  // [string.view.access] -------------------------------------------

  // Returns a code unit at the specified index.
  // This operator performs an out-of-bounds access if the specified
  // index is out of range.
  UNSAFE_BUFFER_USAGE UChar operator[](size_type i) const {
    SECURITY_DCHECK(i < length());
    // SAFETY: Performance-sensitive, enforced by UNSAFE_BUFFER_USAGE.
    UNSAFE_BUFFERS({
      if (Is8Bit()) {
        return static_cast<const LChar*>(bytes_)[i];
      }
      return static_cast<const UChar*>(bytes_)[i];
    })
  }

  // Returns the Unicode code point starting at the specified offset of this
  // string. If the offset points an unpaired surrogate, this function returns
  // the surrogate code unit as is. If you'd like to check such surroagtes,
  // use U_IS_SURROGATE() defined in unicode/utf.h.
  // PRECONDITIONS: `i` must be less than `length()`.
  UNSAFE_BUFFER_USAGE UChar32 CodePointAt(size_type i) const;

  // Returns i+2 if a pair of [i] and [i+1] is a valid surrogate pair.
  // Returns i+1 otherwise.
  size_type NextCodePointOffset(size_type i) const;

  // Does `CodePointAt()`, and the specified `i` is updated by
  // `NextCodePointOffset()`.
  // PRECONDITIONS: `i` must be less than `length()`.
  UNSAFE_BUFFER_USAGE UChar32 CodePointAtAndNext(size_type& i) const;

  // [string.view.modifiers] ----------------------------------------

  // Removes the first `len` characters from this view by advancing the start
  // address and reducing the `length()`.
  // If `len` is greater than `length()`, this function crashes.
  void remove_prefix(size_type len);

  // Removes the last `len` characters from this view by reducing the
  // `length()`.
  // If `len` is greater than `length()`, this function crashes.
  void remove_suffix(size_type len);

  // [string.view.ops] ----------------------------------------------

  bool Is8Bit() const { return impl_->Is8Bit(); }

  String ToString() const;
  AtomicString ToAtomicString() const;
  bool IsAtomic() const { return SharedImpl() && SharedImpl()->IsAtomic(); }

  [[nodiscard]] std::string Utf8(
      Utf8ConversionMode mode = Utf8ConversionMode::kLenient) const;

  base::span<const LChar> Span8() const {
    DCHECK(Is8Bit());
    // SAFETY: bytes_ have length_ elements.
    return UNSAFE_BUFFERS(base::span(
        base::unchecked, static_cast<const LChar*>(bytes_), length_));
  }

  base::span<const UChar> Span16() const {
    DCHECK(!Is8Bit());
    // SAFETY: bytes_ have length_ elements.
    return UNSAFE_BUFFERS(base::span(
        base::unchecked, static_cast<const UChar*>(bytes_), length_));
  }

  base::span<const uint16_t> SpanUint16() const {
    DCHECK(!Is8Bit());
    // SAFETY: bytes_ have length_ elements.
    return UNSAFE_BUFFERS(base::span(
        base::unchecked, static_cast<const uint16_t*>(bytes_), length_));
  }

  const void* Bytes() const { return bytes_; }

  base::span<const uint8_t> RawByteSpan() const {
    if (Is8Bit()) {
      return Span8();
    }
    return base::as_byte_span(Span16());
  }

  // This is not named impl() like String because it has different semantics.
  // String::impl() is never null if String::isNull() is false. For StringView
  // sharedImpl() can be null if the StringView was created with a non-zero
  // offset, or a length that made it shorter than the underlying impl.
  StringImpl* SharedImpl() const {
    // If this StringView is backed by a StringImpl, and was constructed
    // with a zero offset and the same length we can just access the impl
    // directly since this == StringView(m_impl).
    if (impl_->RawByteSpan().data() == Bytes() && length_ == impl_->length()) {
      return GetPtr(impl_);
    }
    return nullptr;
  }

  // Like SharedImpl(), but also succeeds when this view is a *prefix* of its
  // backing StringImpl (starts at the beginning of the impl's buffer but may be
  // shorter than the whole impl). Returns that StringImpl on success.
  StringImpl* SharedSubImpl() const {
    if (impl_->RawByteSpan().data() == Bytes()) {
      return GetPtr(impl_);
    }
    return nullptr;
  }

  // Returns the substring of `this` string, starting at `offset` and consisting
  // of at most `len` characters.
  //
  // If `offset` > `length()`, this function crashes. It's similar to
  // std::string_view::substr(), but not compatible with
  // blink::String::Substring().
  //
  // If `offset + len` >= `length()`,  the resultant string is truncated at
  // `length()`. It's compatible with both std::string_view::substr() and
  // blink::String::Substring(). This behavior does not match to
  // `StringView(*this, offset, len)`.
  StringView substr(size_type offset) const;
  StringView substr(size_type offset, size_type length) const;

  // This is an alias for `substr()`.
  StringView subview(size_type offset) const { return substr(offset); }
  StringView subview(size_type offset, size_type length) const {
    return substr(offset, length);
  }

  // Returns `true` if `this` string starts with `other`.
  bool starts_with(const StringView& other) const;
  // Returns `true` if `this` string starts with `c`.
  bool starts_with(UChar c) const {
    // SAFETY: non-empty implies first element is accessible.
    return !empty() && UNSAFE_BUFFERS((*this)[0]) == c;
  }

  // Returns `true` if `this` string ends with `other`.
  bool ends_with(const StringView& other) const;
  // Returns `true` if `this` string ends with `c`.
  bool ends_with(UChar c) const {
    // SAFETY: non-empty implies last element is accessible.
    return !empty() && UNSAFE_BUFFERS((*this)[length() - 1]) == c;
  }

  // Returns `true` if this StringView contains the specified string.
  bool contains(const StringView& other) const;
  // Returns `true` if this StringView contains the specified character.
  bool contains(UChar ch) const;

  // [string.view.find] ---------------------------------------------

  // Find a substring. Returns the index of the match, or `kNotFound`.
  size_type find(const StringView& value, size_type start = 0) const;
  // Find a character. Returns the index of the match, or `kNotFound`.
  size_type find(UChar ch, size_type start = 0) const;
  // Find characters. Returns the index of the match, or `kNotFound`.
  size_type Find(CharacterMatchFunctionPtr match_function,
                 size_type start = 0) const;

  // Searches for the last occurrence of a substring within this string.
  //
  // This method performs a backward search starting from the 'start' index.
  // If 'start' is npos, the search begins from the end of the string.
  //
  // Returns the index of the start of the found substring, or npos if
  // no match is found.
  //
  // Special Cases:
  // - If 'value' is empty, the search always succeeds and returns
  //   the minimum of 'start' and length().
  // - Null strings and zero-length strings are treated as equivalent
  //   for both `this` string and the 'value' parameter.
  size_type rfind(const StringView& value, size_type start = npos) const;
  // Find the last occurrence of a character. Returns the index of the match, or
  // `kNotFound`.
  size_type rfind(UChar ch, size_type start = npos) const;
  // Find the last character matching `match_function`. Returns the index of
  // the match, or `kNotFound`.
  size_type ReverseFind(CharacterMatchFunctionPtr match_function,
                        size_type start = npos) const;

  // We have no find_first_of(), find_last_of(), find_first_not_of(), and
  // find_last_not_of().  Feel free to add them if necessary.

  // Functions to analyze the content -------------------------------

  bool ContainsNoAsciiUpper() const;
  bool ContainsOnlyAsciiOrEmpty() const;
  // Returns true if the string is empty or contains only Latin-1 characters.
  bool ContainsOnlyLatin1OrEmpty() const;

  bool SubstringContainsOnlyWhitespaceOrEmpty(size_type from,
                                              size_type to) const;

  template <bool isSpecialCharacter(UChar)>
  bool IsAllSpecialCharacters() const;

  // Functions creating new string(s) from `this` string ------------

  // This will return a StringView with a version of |this| that has all ASCII
  // characters lowercased. The returned StringView is guarantee to be valid for
  // as long as |backing_store| is valid.
  //
  // The odd lifetime of the returned object occurs because lowercasing may
  // require allocation. When that happens, |backing_store| is used as the
  // backing store and the returned StringView has the same lifetime.
  StringView LowerAsciiMaybeUsingBuffer(StackBackingStore& backing_store) const;

  // Returns a substring removing leading and trailing white spaces.
  // This function removes spaces, \n, \t, \r, \f, \v, and unicode spaces such
  // as U+2000 and U+3000.
  [[nodiscard]] StringView StripWhiteSpace() const;
  // Returns a substring removing leading and trailing matched characters.
  [[nodiscard]] StringView StripWhiteSpace(
      IsWhiteSpaceFunctionPtr predicate) const;

  // Returns a list of substrings of `this`, separated by `separator`.
  //
  // `StringView("a,,b").Split(',')` produces ["a", "", "b"], and
  // `StringView("").Split(',')` produces [""].
  Vector<StringView> Split(UChar separator) const;

  // Returns a list of substrings of `this`, separated by `separator`.
  // This doesn't produce empty substrings.
  //
  // `StringView(" a  b").SplitSkippingEmpty(' ')` produces ["a", "b"], and
  // `StringView("").SplitSkippingEmpty(',')` produces an empty list.
  Vector<StringView> SplitSkippingEmpty(UChar separator) const;

  // Returns a version suitable for gtest and base/logging.*.  It prepends and
  // appends double-quotes, and escapes characters other than ASCII printables.
  [[nodiscard]] String EncodeForDebugging() const;

 private:
  void Set(const StringImpl&, size_type offset);
  void Set(const StringImpl&, size_type offset, size_type length);

// We use the StringImpl to mark for 8bit or 16bit, even for strings where
// we were constructed from a char pointer. So m_impl->bytes() might have
// nothing to do with this view's bytes().
#if DCHECK_IS_ON()
  scoped_refptr<StringImpl> impl_;
#else
  StringImpl* impl_;
#endif
  const void* bytes_;
  size_type length_;
};

inline StringView::StringView(const StringView& view, size_type offset)
    : impl_(view.impl_), length_(view.length() - offset) {
  CHECK(offset <= view.length());
  // SAFETY: Hard CHECK() in previous line.
  UNSAFE_BUFFERS({
    if (Is8Bit()) {
      bytes_ = static_cast<const LChar*>(view.bytes_) + offset;
    } else {
      bytes_ = static_cast<const UChar*>(view.bytes_) + offset;
    }
  });
}

inline StringView::StringView(const StringView& view,
                              size_type offset,
                              size_type length)
    : impl_(view.impl_), length_(length) {
  // Deliberately combine tests to minimize code size.
  CHECK(offset <= view.length() && length <= view.length() - offset);
  // SAFETY: Hard CHECK()s in previous two lines.
  UNSAFE_BUFFERS({
    if (Is8Bit()) {
      bytes_ = static_cast<const LChar*>(view.bytes_) + offset;
    } else {
      bytes_ = static_cast<const UChar*>(view.bytes_) + offset;
    }
  });
}

inline StringView::StringView(const StringImpl* impl) {
  if (!impl) {
    Clear();
    return;
  }
  impl_ = const_cast<StringImpl*>(impl);
  length_ = impl->length();
  bytes_ = impl->RawByteSpan().data();
}

inline StringView::StringView(const StringImpl* impl, size_type offset) {
  impl ? Set(*impl, offset) : Clear();
}

inline StringView::StringView(const StringImpl* impl,
                              size_type offset,
                              size_type length) {
  impl ? Set(*impl, offset, length) : Clear();
}

inline StringView::StringView(StringImpl& impl, size_type offset) {
  Set(impl, offset);
}

inline StringView::StringView(StringImpl& impl,
                              size_type offset,
                              size_type length) {
  Set(impl, offset, length);
}

inline void StringView::Clear() {
  length_ = 0;
  bytes_ = nullptr;
  impl_ = StringImpl::empty_;  // mark as 8 bit.
}

inline void StringView::Set(const StringImpl& impl, size_type offset) {
  impl_ = const_cast<StringImpl*>(&impl);
  length_ = impl.length() - offset;
  CHECK(offset <= impl.length());
  // SAFETY: Hard CHECK() in previous line.
  UNSAFE_BUFFERS({
    if (impl.Is8Bit()) {
      bytes_ = impl.Span8().data() + offset;
    } else {
      bytes_ = impl.Span16().data() + offset;
    }
  });
}

inline void StringView::Set(const StringImpl& impl,
                            size_type offset,
                            size_type length) {
  impl_ = const_cast<StringImpl*>(&impl);
  length_ = length;
  // Deliberately combine tests to minimize code size.
  CHECK(offset <= impl.length() && length <= impl.length() - offset);
  // SAFETY: Hard CHECK()s in previous line.
  UNSAFE_BUFFERS({
    if (impl.Is8Bit()) {
      bytes_ = impl.Span8().data() + offset;
    } else {
      bytes_ = impl.Span16().data() + offset;
    }
  });
}

// 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(const StringView&,
                                            const StringView&);
WTF_EXPORT bool DeprecatedEqualIgnoringCaseAndNullity(const StringView&,
                                                      const StringView&);

WTF_EXPORT bool EqualIgnoringAsciiCase(const StringView&, const StringView&);

template <size_t N>
inline bool EqualIgnoringAsciiCase(const StringView& a,
                                   const char (&literal)[N]) {
  if (a.length() != N - 1 || (N == 1 && a.IsNull()))
    return false;
  base::span<const char> span = base::span(literal).template first<N - 1>();
  return a.Is8Bit() ? EqualIgnoringAsciiCase(a.Span8(), span)
                    : EqualIgnoringAsciiCase(a.Span16(), span);
}

WTF_EXPORT int CodeUnitCompareIgnoringAsciiCase(const StringView& a,
                                                const StringView& b);
inline bool CodeUnitCompareIgnoringAsciiCaseLessThan(const StringView& a,
                                                     const StringView& b) {
  return CodeUnitCompareIgnoringAsciiCase(a, b) < 0;
}

// TODO(esprehn): Can't make this an overload of blink::Equal since that makes
// calls to Equal() that pass literal strings ambiguous. Figure out if we can
// replace all the callers with EqualStringView and then rename it to Equal().
WTF_EXPORT bool EqualStringView(const StringView&, const StringView&);

inline bool operator==(const StringView& a, const StringView& b) {
  return EqualStringView(a, b);
}

inline StringView::size_type StringView::Find(
    CharacterMatchFunctionPtr match_function,
    size_type start) const {
  return Is8Bit() ? blink::Find(Span8(), match_function, start)
                  : blink::Find(Span16(), match_function, start);
}

inline StringView::size_type StringView::ReverseFind(
    CharacterMatchFunctionPtr match_function,
    size_type start) const {
  return Is8Bit() ? blink::ReverseFind(Span8(), match_function, start)
                  : blink::ReverseFind(Span16(), match_function, start);
}

template <bool isSpecialCharacter(UChar)>
inline bool StringView::IsAllSpecialCharacters() const {
  if (empty()) {
    return true;
  }
  return Is8Bit() ? std::ranges::all_of(Span8(), isSpecialCharacter)
                  : std::ranges::all_of(Span16(), isSpecialCharacter);
}

WTF_EXPORT std::ostream& operator<<(std::ostream&, const StringView&);

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_VIEW_H_