chromium/third_party/blink/renderer/platform/wtf/vector.h

/*
 *  Copyright (C) 2005, 2006, 2007, 2008 Apple 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.
 *
 */

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_H_

#include <string.h>

#include <algorithm>
#include <concepts>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <ranges>
#include <type_traits>
#include <utility>

#include "base/check_op.h"
#include "base/compiler_specific.h"
#include "base/containers/checked_iterators.h"
#include "base/containers/span.h"
#include "base/dcheck_is_on.h"
#include "base/numerics/safe_conversions.h"
#include "base/ranges/algorithm.h"
#include "build/build_config.h"
#include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h"
#include "third_party/blink/renderer/platform/wtf/assertions.h"
#include "third_party/blink/renderer/platform/wtf/atomic_operations.h"
#include "third_party/blink/renderer/platform/wtf/construct_traits.h"
#include "third_party/blink/renderer/platform/wtf/container_annotations.h"
#include "third_party/blink/renderer/platform/wtf/forward.h"  // For default Vector template parameters.
#include "third_party/blink/renderer/platform/wtf/hash_table_deleted_value_type.h"
#include "third_party/blink/renderer/platform/wtf/std_lib_extras.h"
#include "third_party/blink/renderer/platform/wtf/type_traits.h"
#include "third_party/blink/renderer/platform/wtf/vector_traits.h"
#include "third_party/blink/renderer/platform/wtf/wtf_size_t.h"

// For ASAN builds, disable inline buffers completely as they cause various
// issues.
#ifdef ANNOTATE_CONTIGUOUS_CONTAINER
#define INLINE_CAPACITY …
#else
#define INLINE_CAPACITY …
#endif

namespace WTF {

#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
// The allocation pool for nodes is one big chunk that ASAN has no insight
// into, so it can cloak errors. Make it as small as possible to force nodes
// to be allocated individually where ASAN can see them.
static const wtf_size_t kInitialVectorSize = 1;
#else
static const wtf_size_t kInitialVectorSize = …;
#endif

template <typename T, wtf_size_t inlineBuffer, typename Allocator>
class Deque;

//
// Vector Traits
//

// Bunch of traits for Vector are defined here, with which you can customize
// Vector's behavior. In most cases the default traits are appropriate, so you
// usually don't have to specialize those traits by yourself.
//
// The behavior of the implementation below can be controlled by VectorTraits.
// If you want to change the behavior of your type, take a look at VectorTraits
// (defined in VectorTraits.h), too.

// Tracing assumes the entire backing store is safe to access. To guarantee
// that, tracing a backing store starts by marking the whole backing store
// capacity as accessible. With concurrent marking enabled, annotating size
// changes could conflict with marking the whole store as accessible, causing
// a race.
#if defined(ADDRESS_SANITIZER)
#define MARKING_AWARE_ANNOTATE_CHANGE_SIZE …
#define MARKING_AWARE_ANNOTATE_NEW_BUFFER …
#else
#define MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, buffer, capacity, \
                                           old_size, new_size) …
#define MARKING_AWARE_ANNOTATE_NEW_BUFFER(Allocator, buffer, capacity, size) …
#endif  // defined(ADDRESS_SANITIZER)

template <typename T>
struct VectorElementComparer { … };

VectorElementComparer<std::unique_ptr<T>>;

// `VectorOperationOrigin` tracks the origin of a vector operation. This is
// needed for the Vector specialization of `HeapAllocator` which is used for
// garbage-collected objects.
//
// The general idea is that during construction of a Vector write barriers can
// be omitted as objects are allocated unmarked and the GC would thus still
// process such objects. Conservative GC is unaffected and would find the
// objects through the stack scan.
//
// This usually applies to storage in the object itself, i.e., inline capacity.
// For Vector it even applies to out-of-line backings as long as those also omit
// the write barrier as they only are referred to from the Vector itself.
enum class VectorOperationOrigin { … };

// A collection of all the traits used by Vector. This is basically an
// implementation detail of Vector, and you probably don't want to change this.
// If you want to customize Vector's behavior, you should specialize
// VectorTraits instead (defined in VectorTraits.h).
template <typename T, typename Allocator>
struct VectorTypeOperations { … };

//
// VectorBuffer
//

// VectorBuffer is an implementation detail of Vector and Deque. It manages
// Vector's underlying buffer, and does operations like allocation or
// expansion.
//
// Not meant for general consumption.

template <typename T, typename Allocator>
class VectorBufferBase { … };

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator = PartitionAllocator>
class VectorBuffer;

VectorBuffer<T, 0, Allocator>;

template <typename T, wtf_size_t InlineCapacity, typename Allocator>
class VectorBuffer : protected VectorBufferBase<T, Allocator> { … };

// UncheckedIteraotr<T> is just a wrapper of a T pointer with no bounds
// checking, and the default iterator implementation of WTF::Vector.
template <typename T>
class UncheckedIterator { … };

template <typename T, bool checked_iter>
struct IteratorSelector;

IteratorSelector<T, true>;

IteratorSelector<T, false>;

//
// Vector
//

// Vector is a container that works just like std::vector. WTF's Vector has
// several extra functionalities: inline buffer, behavior customization via
// traits, and Oilpan support. Those are explained in the sections below.
//
// Vector is the most basic container, which stores its element in a contiguous
// buffer. The buffer is expanded automatically when necessary. The elements
// are automatically moved to the new buffer. This event is called a
// reallocation. A reallocation takes O(N)-time (N = number of elements), but
// its occurrences are rare, so its time cost should not be significant,
// compared to the time cost of other operations to the vector.
//
// Time complexity of key operations is as follows:
//
//     * Indexed access -- O(1)
//     * Insertion or removal of an element at the end -- amortized O(1)
//     * Other insertion or removal -- O(N)
//     * Swapping with another vector -- O(1)
//
// 1. Iterator invalidation semantics
//
// Vector provides STL-compatible iterators and reverse iterators. Iterators
// are _invalidated_ on certain occasions. Reading an invalidated iterator
// causes undefined behavior.
//
// Iterators are invalidated on the following situations:
//
//     * When a reallocation happens on a vector, all the iterators for that
//       vector will be invalidated.
//     * Some member functions invalidate part of the existing iterators for
//       the vector; see comments on the individual functions.
//     * [Oilpan only] Heap compaction invalidates all the iterators for any
//       HeapVectors. This means you can only store an iterator on stack, as
//       a local variable.
//
// In this context, pointers or references to an element of a Vector are
// essentially equivalent to iterators, in that they also become invalid
// whenever corresponding iterators are invalidated.
//
// 2. Inline buffer
//
// Vectors may have an _inline buffer_. An inline buffer is a storage area
// that is contained in the vector itself, along with other metadata like
// size_. It is used as a storage space when the vector's elements fit in
// that space. If the inline buffer becomes full and further space is
// necessary, an out-of-line buffer is allocated in the heap, and it will
// take over the role of the inline buffer.
//
// The existence of an inline buffer is indicated by non-zero |InlineCapacity|
// template argument. The value represents the number of elements that can be
// stored in the inline buffer. Zero |InlineCapacity| means the vector has no
// inline buffer.
//
// An inline buffer increases the size of the Vector instances, and, in trade
// for that, it gives you several performance benefits, as long as the number
// of elements do not exceed |InlineCapacity|:
//
//     * No heap allocation will be made.
//     * Memory locality will improve.
//
// Generally, having an inline buffer is useful for vectors that (1) are
// frequently accessed or modified, and (2) contain only a few elements at
// most.
//
// 3. Behavior customization
//
// You usually do not need to customize Vector's behavior, since the default
// behavior is appropriate for normal usage. The behavior is controlled by
// VectorTypeOperations traits template above. Read VectorTypeOperations
// and VectorTraits if you want to change the behavior for your types (i.e.
// if you really want faster vector operations).
//
// The default traits basically do the following:
//
//     * Skip constructor call and fill zeros with memset for simple types;
//     * Skip destructor call for simple types;
//     * Copy or move by memcpy for simple types; and
//     * Customize the comparisons for smart pointer types, so you can look
//       up a std::unique_ptr<T> element with a raw pointer, for instance.
//
// 4. Oilpan
//
// If you want to store garbage collected objects in Vector, (1) use HeapVector
// (defined in HeapAllocator.h) instead of Vector, and (2) make sure your
// garbage-collected type is wrapped with Member, like:
//
//     HeapVector<Member<Node>> nodes;
//
// Unlike normal garbage-collected objects, a HeapVector object itself is
// NOT a garbage-collected object, but its backing buffer is allocated in
// Oilpan heap, and it may still carry garbage-collected objects.
//
// Even though a HeapVector object is not garbage-collected, you still need
// to trace it, if you stored it in your class. Also, you can allocate it
// as a local variable. This is useful when you want to build a vector locally
// and put it in an on-heap vector with swap().
//
// Also, heap compaction, which may happen at any time when Blink code is not
// running (i.e. Blink code does not appear in the call stack), may invalidate
// existing iterators for any HeapVectors. So, essentially, you should always
// allocate an iterator on stack (as a local variable), and you should not
// store iterators in another heap object.

// In general, Vector requires destruction.
kVectorNeedsDestructor;

// For garbage collection, Vector does not require destruction when there's no
// inline capacity.
kVectorNeedsDestructor;

// For garbage collection, a Vector with inline capacity conditionally requires
// destruction based on whether the element type itself requires destruction.
//
// However, for now, always return true, as there are many uses of on-stack
// HeapVector with inline capacity that require eager clearing for performance.
//
// Ideally, there should be a different representation for on-stack usages
// which would allow eager clearing for all uses of Vector from stack and avoid
// destructors on heap.
kVectorNeedsDestructor;

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
class Vector : private VectorBuffer<T, INLINE_CAPACITY, Allocator> { … };

//
// Vector out-of-line implementation
//

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline Vector<T, InlineCapacity, Allocator, checked_iter>::Vector() { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(
    wtf_size_t size)
    : … { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(
    wtf_size_t size,
    const T& val)
    : … { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(const Vector& other)
    : … { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename Proj, typename>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(const Vector& other,
                                                           Proj proj)
    : Base(other.capacity()) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <wtf_size_t otherCapacity>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(
    const Vector<T, otherCapacity, Allocator, checked_iter>& other)
    : Base(other.capacity()) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U, wtf_size_t otherCapacity, typename Proj, typename>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(
    const Vector<U, otherCapacity, Allocator>& other,
    Proj proj)
    : Base(other.capacity()) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>&
Vector<T, InlineCapacity, Allocator, checked_iter>::operator=(
    const Vector& other) { … }

inline bool TypelessPointersAreEqual(const void* a, const void* b) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <wtf_size_t otherCapacity>
Vector<T, InlineCapacity, Allocator, checked_iter>&
Vector<T, InlineCapacity, Allocator, checked_iter>::operator=(
    const Vector<T, otherCapacity, Allocator, checked_iter>& other) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename Range>
  requires std::ranges::input_range<Range> && std::ranges::sized_range<Range>
void Vector<T, InlineCapacity, Allocator, checked_iter>::assign(
    const Range& range) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(Vector&& other) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>&
Vector<T, InlineCapacity, Allocator, checked_iter>::operator=(Vector&& other) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>::Vector(
    std::initializer_list<T> elements)
    : … { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
Vector<T, InlineCapacity, Allocator, checked_iter>&
Vector<T, InlineCapacity, Allocator, checked_iter>::operator=(
    std::initializer_list<T> elements) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
bool Vector<T, InlineCapacity, Allocator, checked_iter>::Contains(
    const U& value) const { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
wtf_size_t Vector<T, InlineCapacity, Allocator, checked_iter>::Find(
    const U& value) const { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
wtf_size_t Vector<T, InlineCapacity, Allocator, checked_iter>::ReverseFind(
    const U& value) const { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::Fill(
    const T& val,
    wtf_size_t new_size)
  requires(!Allocator::kIsGarbageCollected)
{ … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::ExpandCapacity(
    wtf_size_t new_min_capacity) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
T* Vector<T, InlineCapacity, Allocator, checked_iter>::ExpandCapacity(
    wtf_size_t new_min_capacity,
    T* ptr) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
inline U* Vector<T, InlineCapacity, Allocator, checked_iter>::ExpandCapacity(
    wtf_size_t new_min_capacity,
    U* ptr) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::resize(
    wtf_size_t size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::Shrink(
    wtf_size_t size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::Grow(wtf_size_t size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::reserve(
    wtf_size_t new_capacity) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void
Vector<T, InlineCapacity, Allocator, checked_iter>::ReserveInitialCapacity(
    wtf_size_t initial_capacity) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::ShrinkCapacity(
    wtf_size_t new_capacity) { … }

// Templatizing these is better than just letting the conversion happen
// implicitly.
template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
ALWAYS_INLINE void
Vector<T, InlineCapacity, Allocator, checked_iter>::push_back(U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename... Args>
ALWAYS_INLINE T&
Vector<T, InlineCapacity, Allocator, checked_iter>::emplace_back(
    Args&&... args) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
void Vector<T, InlineCapacity, Allocator, checked_iter>::Append(
    const U* data,
    wtf_size_t data_size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
NOINLINE PRESERVE_MOST void
Vector<T, InlineCapacity, Allocator, checked_iter>::AppendSlowCase(U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U, wtf_size_t otherCapacity, typename OtherAllocator, bool f>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::AppendVector(
    const Vector<U, otherCapacity, OtherAllocator, f>& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename Iterator>
void Vector<T, InlineCapacity, Allocator, checked_iter>::AppendRange(
    Iterator begin,
    Iterator end) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U, size_t N>
void Vector<T, InlineCapacity, Allocator, checked_iter>::AppendSpan(
    base::span<U, N> data) { … }

// This version of append saves a branch in the case where you know that the
// vector's capacity is large enough for the append to succeed.
template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
ALWAYS_INLINE void
Vector<T, InlineCapacity, Allocator, checked_iter>::UncheckedAppend(U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::insert(
    wtf_size_t position,
    U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
void Vector<T, InlineCapacity, Allocator, checked_iter>::insert(
    wtf_size_t position,
    const U* data,
    wtf_size_t data_size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
void Vector<T, InlineCapacity, Allocator, checked_iter>::InsertAt(
    Vector::iterator position,
    U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
void Vector<T, InlineCapacity, Allocator, checked_iter>::InsertAt(
    Vector::iterator position,
    const U* data,
    wtf_size_t data_size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U, wtf_size_t otherCapacity, typename OtherAllocator, bool f>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::InsertVector(
    wtf_size_t position,
    const Vector<U, otherCapacity, OtherAllocator, f>& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::push_front(
    U&& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U>
void Vector<T, InlineCapacity, Allocator, checked_iter>::push_front(
    const U* data,
    wtf_size_t data_size) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
template <typename U, wtf_size_t otherCapacity, typename OtherAllocator, bool f>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::PrependVector(
    const Vector<U, otherCapacity, OtherAllocator, f>& val) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::EraseAt(
    wtf_size_t position) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline auto Vector<T, InlineCapacity, Allocator, checked_iter>::erase(
    iterator position) -> iterator { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline auto Vector<T, InlineCapacity, Allocator, checked_iter>::erase(
    iterator first,
    iterator last) -> iterator { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::EraseAt(
    wtf_size_t position,
    wtf_size_t length) { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void Vector<T, InlineCapacity, Allocator, checked_iter>::Reverse() { … }

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
inline void swap(Vector<T, InlineCapacity, Allocator, checked_iter>& a,
                 Vector<T, InlineCapacity, Allocator, checked_iter>& b) { … }

template <typename T,
          wtf_size_t InlineCapacityA,
          wtf_size_t InlineCapacityB,
          typename Allocator,
          bool checked_iter>
bool operator==(const Vector<T, InlineCapacityA, Allocator, checked_iter>& a,
                const Vector<T, InlineCapacityB, Allocator, checked_iter>& b) { … }

template <typename T,
          wtf_size_t InlineCapacityA,
          wtf_size_t InlineCapacityB,
          typename Allocator,
          bool checked_iter>
inline bool operator!=(
    const Vector<T, InlineCapacityA, Allocator, checked_iter>& a,
    const Vector<T, InlineCapacityB, Allocator, checked_iter>& b) { … }

namespace internal {
template <typename Allocator, typename VisitorDispatcher, typename T>
void TraceInlinedBuffer(VisitorDispatcher visitor,
                        const T* buffer_begin,
                        size_t capacity) { … }

template <typename Allocator,
          typename VisitorDispatcher,
          typename T,
          wtf_size_t InlineCapacity>
void DeferredTraceImpl(VisitorDispatcher visitor, const void* object) { … }

}  // namespace internal

// Only defined for HeapAllocator. Used when visiting vector object.
template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::Trace(
    auto visitor) const
  requires Allocator::kIsGarbageCollected
{
  static_assert(Allocator::kIsGarbageCollected,
                "Garbage collector must be enabled.");

  const T* buffer = BufferSafe();

  if (!buffer) {
    // Register the slot for heap compaction.
    Allocator::TraceVectorBacking(visitor, static_cast<T*>(nullptr),
                                  Base::BufferSlot());
    return;
  }

  if (Base::IsOutOfLineBuffer(buffer)) {
    Allocator::TraceVectorBacking(visitor, buffer, Base::BufferSlot());
  } else {
    // We should not visit inline buffers, but we still need to register the
    // slot for heap compaction. So, we pass nullptr to this method.
    Allocator::TraceVectorBacking(visitor, static_cast<T*>(nullptr),
                                  Base::BufferSlot());

    // Bail out for concurrent marking.
    if (!VectorTraits<T>::kCanTraceConcurrently) {
      if (Allocator::DeferTraceToMutatorThreadIfConcurrent(
              visitor, buffer,
              internal::DeferredTraceImpl<Allocator, decltype(visitor), T,
                                          InlineCapacity>,
              InlineCapacity * sizeof(T))) {
        return;
      }
    }

    // Inline buffer requires tracing immediately.
    internal::TraceInlinedBuffer<Allocator>(visitor, buffer, InlineCapacity);
  }
}

template <typename T,
          wtf_size_t InlineCapacity,
          typename Allocator,
          bool checked_iter>
void Vector<T, InlineCapacity, Allocator, checked_iter>::ReallocateBuffer(
    wtf_size_t new_capacity) { … }

// Erase/EraseIf are based on C++20's uniform container erasure API:
// - https://eel.is/c++draft/libraryindex#:erase
// - https://eel.is/c++draft/libraryindex#:erase_if
template <typename T,
          wtf_size_t inline_capacity,
          typename Allocator,
          bool checked_iter,
          typename U>
wtf_size_t Erase(Vector<T, inline_capacity, Allocator, checked_iter>& v,
                 const U& value) { … }

template <typename T,
          wtf_size_t inline_capacity,
          typename Allocator,
          bool checked_iter,
          typename Pred>
wtf_size_t EraseIf(Vector<T, inline_capacity, Allocator, checked_iter>& v,
                   Pred pred) { … }

}  // namespace WTF

Vector;

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_VECTOR_H_