src/google/protobuf/repeated_field.h

// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd

// Author: kenton@google.com (Kenton Varda)
//  Based on original Protocol Buffers design by
//  Sanjay Ghemawat, Jeff Dean, and others.
//
// RepeatedField and RepeatedPtrField are used by generated protocol message
// classes to manipulate repeated fields.  These classes are very similar to
// STL's vector, but include a number of optimizations found to be useful
// specifically in the case of Protocol Buffers.  RepeatedPtrField is
// particularly different from STL vector as it manages ownership of the
// pointers that it contains.
//
// This header covers RepeatedField.

#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/dynamic_annotations.h"
#include "absl/base/optimization.h"
#include "absl/log/absl_check.h"
#include "absl/meta/type_traits.h"
#include "absl/strings/cord.h"
#include "google/protobuf/arena.h"
#include "google/protobuf/generated_enum_util.h"
#include "google/protobuf/internal_visibility.h"
#include "google/protobuf/message_lite.h"
#include "google/protobuf/port.h"
#include "google/protobuf/repeated_ptr_field.h"

// Must be included last.
#include "google/protobuf/port_def.inc"

#ifdef SWIG
#error "You cannot SWIG proto headers"
#endif

namespace google {
namespace protobuf {

class Message;
class UnknownField;  // For the allowlist

namespace internal {

template <typename T, int kHeapRepHeaderSize>
constexpr int RepeatedFieldLowerClampLimit() {
  // The header is padded to be at least `sizeof(T)` when it would be smaller
  // otherwise.
  static_assert(sizeof(T) <= kHeapRepHeaderSize, "");
  // We want to pad the minimum size to be a power of two bytes, including the
  // header.
  // The first allocation is kHeapRepHeaderSize bytes worth of elements for a
  // total of 2*kHeapRepHeaderSize bytes. For an 8-byte header, we allocate 8
  // bool, 2 ints, or 1 int64.
  return kHeapRepHeaderSize / sizeof(T);
}

// kRepeatedFieldUpperClampLimit is the lowest signed integer value that
// overflows when multiplied by 2 (which is undefined behavior). Sizes above
// this will clamp to the maximum int value instead of following exponential
// growth when growing a repeated field.
#if defined(__cpp_inline_variables)
inline constexpr int kRepeatedFieldUpperClampLimit =
#else
constexpr int kRepeatedFieldUpperClampLimit =
#endif
    (std::numeric_limits<int>::max() / 2) + 1;

template <typename Element>
class RepeatedIterator;

// Sentinel base class.
struct RepeatedFieldBase {};

// We can't skip the destructor for, e.g., arena allocated RepeatedField<Cord>.
template <typename Element,
          bool Trivial = Arena::is_destructor_skippable<Element>::value>
struct RepeatedFieldDestructorSkippableBase : RepeatedFieldBase {};

template <typename Element>
struct RepeatedFieldDestructorSkippableBase<Element, true> : RepeatedFieldBase {
  using DestructorSkippable_ = void;
};

template <size_t kMinSize>
struct HeapRep {
  // Avoid 'implicitly deleted dtor' warnings on certain compilers.
  ~HeapRep() = delete;

  void* elements() { return this + 1; }

  // Align to 8 as sanitizers are picky on the alignment of containers to start
  // at 8 byte offsets even when compiling for 32 bit platforms.
  union {
    alignas(8) Arena* arena;
    // We pad the header to be at least `sizeof(Element)` so that we have
    // power-of-two sized allocations, which enables Arena optimizations.
    char padding[kMinSize];
  };
};

// We use small object optimization (SOO) to store elements inline when possible
// for small repeated fields. We do so in order to avoid memory indirections.
// Note that SOO is disabled on 32-bit platforms due to alignment limitations.

// SOO data is stored in the same space as the size/capacity ints.
enum { kSooCapacityBytes = 2 * sizeof(int) };

// Arena/elements pointers are aligned to at least kSooPtrAlignment bytes so we
// can use the lower bits to encode whether we're in SOO mode and if so, the
// SOO size. NOTE: we also tried using all kSooPtrMask bits to encode SOO size
// and use all ones as a sentinel value for non-SOO mode, but that was slower in
// benchmarks/loadtests.
enum { kSooPtrAlignment = 8 };
// The mask for the size bits in SOO mode, and also a sentinel value indicating
// that the field is not in SOO mode.
enum { kSooPtrMask = ~(kSooPtrAlignment - 1) };
// This bit is 0 when in SOO mode and 1 when in non-SOO mode.
enum { kNotSooBit = kSooPtrAlignment >> 1 };
// These bits are used to encode the size when in SOO mode (sizes are 0-3).
enum { kSooSizeMask = kNotSooBit - 1 };

// The number of elements that can be stored in the SOO rep. On 64-bit
// platforms, this is 1 for int64_t, 2 for int32_t, 3 for bool, and 0 for
// absl::Cord. We return 0 to disable SOO on 32-bit platforms.
constexpr int SooCapacityElements(size_t element_size) {
  if (sizeof(void*) < 8) return 0;
  return std::min<int>(kSooCapacityBytes / element_size, kSooSizeMask);
}

struct LongSooRep {
  // Returns char* rather than void* so callers can do pointer arithmetic.
  char* elements() const {
    auto ret = reinterpret_cast<char*>(elements_int & kSooPtrMask);
    ABSL_DCHECK_NE(ret, nullptr);
    return ret;
  }

  uintptr_t elements_int;
  int size;
  int capacity;
};
struct ShortSooRep {
  constexpr ShortSooRep() = default;
  explicit ShortSooRep(Arena* arena)
      : arena_and_size(reinterpret_cast<uintptr_t>(arena)) {
    ABSL_DCHECK_EQ(size(), 0);
  }

  int size() const { return arena_and_size & kSooSizeMask; }
  bool is_soo() const { return (arena_and_size & kNotSooBit) == 0; }

  uintptr_t arena_and_size = 0;
  union {
    char data[kSooCapacityBytes];
    // NOTE: in some language versions, we can't have a constexpr constructor
    // if we don't initialize all fields, but `data` doesn't need to be
    // initialized so initialize an empty dummy variable instead.
    std::true_type dummy = {};
  };
};
struct SooRep {
  constexpr SooRep() : short_rep() {}
  explicit SooRep(Arena* arena) : short_rep(arena) {}

  bool is_soo() const {
    static_assert(sizeof(LongSooRep) == sizeof(ShortSooRep), "");
    static_assert(offsetof(SooRep, long_rep) == offsetof(SooRep, short_rep),
                  "");
    static_assert(offsetof(LongSooRep, elements_int) ==
                      offsetof(ShortSooRep, arena_and_size),
                  "");
    return short_rep.is_soo();
  }
  Arena* soo_arena() const {
    ABSL_DCHECK(is_soo());
    return reinterpret_cast<Arena*>(short_rep.arena_and_size & kSooPtrMask);
  }
  int size(bool is_soo) const {
    ABSL_DCHECK_EQ(is_soo, this->is_soo());
#if !defined(__clang__) && defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
    return is_soo ? short_rep.size() : long_rep.size;
#if !defined(__clang__) && defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
  }
  void set_size(bool is_soo, int size) {
    ABSL_DCHECK_EQ(is_soo, this->is_soo());
    if (is_soo) {
      ABSL_DCHECK_LE(size, kSooSizeMask);
      short_rep.arena_and_size &= kSooPtrMask;
      short_rep.arena_and_size |= size;
    } else {
      long_rep.size = size;
    }
  }
  // Initializes the SooRep in non-SOO mode with the given capacity and heap
  // allocation.
  void set_non_soo(bool was_soo, int capacity, void* elements) {
    ABSL_DCHECK_EQ(was_soo, is_soo());
    ABSL_DCHECK_NE(elements, nullptr);
    ABSL_DCHECK_EQ(reinterpret_cast<uintptr_t>(elements) % kSooPtrAlignment,
                   uintptr_t{0});
    if (was_soo) long_rep.size = short_rep.size();
    long_rep.capacity = capacity;
    long_rep.elements_int = reinterpret_cast<uintptr_t>(elements) | kNotSooBit;
  }

  union {
    LongSooRep long_rep;
    ShortSooRep short_rep;
  };
};

}  // namespace internal

// RepeatedField is used to represent repeated fields of a primitive type (in
// other words, everything except strings and nested Messages).  Most users will
// not ever use a RepeatedField directly; they will use the get-by-index,
// set-by-index, and add accessors that are generated for all repeated fields.
// Actually, in addition to primitive types, we use RepeatedField for repeated
// Cords, because the Cord class is in fact just a reference-counted pointer.
// We have to specialize several methods in the Cord case to get the memory
// management right; e.g. swapping when appropriate, etc.
template <typename Element>
class RepeatedField final
    : private internal::RepeatedFieldDestructorSkippableBase<Element> {
  static_assert(
      alignof(Arena) >= alignof(Element),
      "We only support types that have an alignment smaller than Arena");
  static_assert(!std::is_const<Element>::value,
                "We do not support const value types.");
  static_assert(!std::is_volatile<Element>::value,
                "We do not support volatile value types.");
  static_assert(!std::is_pointer<Element>::value,
                "We do not support pointer value types.");
  static_assert(!std::is_reference<Element>::value,
                "We do not support reference value types.");
  static constexpr PROTOBUF_ALWAYS_INLINE void StaticValidityCheck() {
    static_assert(
        absl::disjunction<internal::is_supported_integral_type<Element>,
                          internal::is_supported_floating_point_type<Element>,
                          std::is_same<absl::Cord, Element>,
                          std::is_same<UnknownField, Element>,
                          is_proto_enum<Element>>::value,
        "We only support non-string scalars in RepeatedField.");
  }

 public:
  using value_type = Element;
  using size_type = int;
  using difference_type = ptrdiff_t;
  using reference = Element&;
  using const_reference = const Element&;
  using pointer = Element*;
  using const_pointer = const Element*;
  using iterator = internal::RepeatedIterator<Element>;
  using const_iterator = internal::RepeatedIterator<const Element>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  constexpr RepeatedField();
  RepeatedField(const RepeatedField& rhs) : RepeatedField(nullptr, rhs) {}

  // TODO: make this constructor private
  explicit RepeatedField(Arena* arena);

  template <typename Iter,
            typename = typename std::enable_if<std::is_constructible<
                Element, decltype(*std::declval<Iter>())>::value>::type>
  RepeatedField(Iter begin, Iter end);

  // Arena enabled constructors: for internal use only.
  RepeatedField(internal::InternalVisibility, Arena* arena)
      : RepeatedField(arena) {}
  RepeatedField(internal::InternalVisibility, Arena* arena,
                const RepeatedField& rhs)
      : RepeatedField(arena, rhs) {}

  RepeatedField& operator=(const RepeatedField& other)
      ABSL_ATTRIBUTE_LIFETIME_BOUND;

  RepeatedField(RepeatedField&& rhs) noexcept
      : RepeatedField(nullptr, std::move(rhs)) {}
  RepeatedField& operator=(RepeatedField&& other) noexcept
      ABSL_ATTRIBUTE_LIFETIME_BOUND;

  ~RepeatedField();

  bool empty() const;
  int size() const;

  const_reference Get(int index) const ABSL_ATTRIBUTE_LIFETIME_BOUND;
  pointer Mutable(int index) ABSL_ATTRIBUTE_LIFETIME_BOUND;

  const_reference operator[](int index) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return Get(index);
  }
  reference operator[](int index) ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return *Mutable(index);
  }

  const_reference at(int index) const ABSL_ATTRIBUTE_LIFETIME_BOUND;
  reference at(int index) ABSL_ATTRIBUTE_LIFETIME_BOUND;

  void Set(int index, const Element& value);
  void Add(Element value);

  // Appends a new element and returns a pointer to it.
  // The new element is uninitialized if |Element| is a POD type.
  pointer Add() ABSL_ATTRIBUTE_LIFETIME_BOUND;
  // Appends elements in the range [begin, end) after reserving
  // the appropriate number of elements.
  template <typename Iter>
  void Add(Iter begin, Iter end);

  // Removes the last element in the array.
  void RemoveLast();

  // Extracts elements with indices in "[start .. start+num-1]".
  // Copies them into "elements[0 .. num-1]" if "elements" is not nullptr.
  // Caution: also moves elements with indices [start+num ..].
  // Calling this routine inside a loop can cause quadratic behavior.
  void ExtractSubrange(int start, int num, Element* elements);

  ABSL_ATTRIBUTE_REINITIALIZES void Clear();

  // Appends the elements from `other` after this instance.
  // The end result length will be `other.size() + this->size()`.
  void MergeFrom(const RepeatedField& other);

  // Replaces the contents with a copy of the elements from `other`.
  ABSL_ATTRIBUTE_REINITIALIZES void CopyFrom(const RepeatedField& other);

  // Replaces the contents with RepeatedField(begin, end).
  template <typename Iter>
  ABSL_ATTRIBUTE_REINITIALIZES void Assign(Iter begin, Iter end);

  // Reserves space to expand the field to at least the given size.  If the
  // array is grown, it will always be at least doubled in size.
  void Reserve(int new_size);

  // Resizes the RepeatedField to a new, smaller size.  This is O(1).
  // Except for RepeatedField<Cord>, for which it is O(size-new_size).
  void Truncate(int new_size);

  void AddAlreadyReserved(Element value);
  int Capacity() const;

  // Adds `n` elements to this instance asserting there is enough capacity.
  // The added elements are uninitialized if `Element` is trivial.
  pointer AddAlreadyReserved() ABSL_ATTRIBUTE_LIFETIME_BOUND;
  pointer AddNAlreadyReserved(int n) ABSL_ATTRIBUTE_LIFETIME_BOUND;

  // Like STL resize.  Uses value to fill appended elements.
  // Like Truncate() if new_size <= size(), otherwise this is
  // O(new_size - size()).
  void Resize(size_type new_size, const Element& value);

  // Gets the underlying array.  This pointer is possibly invalidated by
  // any add or remove operation.
  pointer mutable_data() ABSL_ATTRIBUTE_LIFETIME_BOUND;
  const_pointer data() const ABSL_ATTRIBUTE_LIFETIME_BOUND;

  // Swaps entire contents with "other". If they are separate arenas, then
  // copies data between each other.
  void Swap(RepeatedField* other);

  // Swaps two elements.
  void SwapElements(int index1, int index2);

  iterator begin() ABSL_ATTRIBUTE_LIFETIME_BOUND;
  const_iterator begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND;
  const_iterator cbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND;
  iterator end() ABSL_ATTRIBUTE_LIFETIME_BOUND;
  const_iterator end() const ABSL_ATTRIBUTE_LIFETIME_BOUND;
  const_iterator cend() const ABSL_ATTRIBUTE_LIFETIME_BOUND;

  // Reverse iterator support
  reverse_iterator rbegin() ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return reverse_iterator(end());
  }
  const_reverse_iterator rbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return const_reverse_iterator(end());
  }
  reverse_iterator rend() ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return reverse_iterator(begin());
  }
  const_reverse_iterator rend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
    return const_reverse_iterator(begin());
  }

  // Returns the number of bytes used by the repeated field, excluding
  // sizeof(*this)
  size_t SpaceUsedExcludingSelfLong() const;

  int SpaceUsedExcludingSelf() const {
    return internal::ToIntSize(SpaceUsedExcludingSelfLong());
  }

  // Removes the element referenced by position.
  //
  // Returns an iterator to the element immediately following the removed
  // element.
  //
  // Invalidates all iterators at or after the removed element, including end().
  iterator erase(const_iterator position) ABSL_ATTRIBUTE_LIFETIME_BOUND;

  // Removes the elements in the range [first, last).
  //
  // Returns an iterator to the element immediately following the removed range.
  //
  // Invalidates all iterators at or after the removed range, including end().
  iterator erase(const_iterator first,
                 const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND;

  // Gets the Arena on which this RepeatedField stores its elements.
  // Note: this can be inaccurate for split default fields so we make this
  // function non-const.
  inline Arena* GetArena() { return GetArena(is_soo()); }

  // For internal use only.
  //
  // This is public due to it being called by generated code.
  inline void InternalSwap(RepeatedField* other);

  static constexpr size_t InternalGetArenaOffset(internal::InternalVisibility) {
    return PROTOBUF_FIELD_OFFSET(RepeatedField, soo_rep_) +
           PROTOBUF_FIELD_OFFSET(internal::ShortSooRep, arena_and_size);
  }

 private:
  using InternalArenaConstructable_ = void;
  // We use std::max in order to share template instantiations between
  // different element types.
  using HeapRep = internal::HeapRep<std::max<size_t>(sizeof(Element), 8)>;

  template <typename T>
  friend class Arena::InternalHelper;

  friend class Arena;

  static constexpr int kSooCapacityElements =
      internal::SooCapacityElements(sizeof(Element));

  static constexpr int kInitialSize = 0;
  static PROTOBUF_CONSTEXPR const size_t kHeapRepHeaderSize = sizeof(HeapRep);

  RepeatedField(Arena* arena, const RepeatedField& rhs);
  RepeatedField(Arena* arena, RepeatedField&& rhs);

  inline Arena* GetArena(bool is_soo) const {
    return is_soo ? soo_rep_.soo_arena() : heap_rep()->arena;
  }

  bool is_soo() const { return soo_rep_.is_soo(); }
  int size(bool is_soo) const { return soo_rep_.size(is_soo); }
  int Capacity(bool is_soo) const {
#if !defined(__clang__) && defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
    return is_soo ? kSooCapacityElements : soo_rep_.long_rep.capacity;
#if !defined(__clang__) && defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
  }
  void set_size(bool is_soo, int size) {
    ABSL_DCHECK_LE(size, Capacity(is_soo));
    soo_rep_.set_size(is_soo, size);
  }

  // Swaps entire contents with "other". Should be called only if the caller can
  // guarantee that both repeated fields are on the same arena or are on the
  // heap. Swapping between different arenas is disallowed and caught by a
  // ABSL_DCHECK (see API docs for details).
  void UnsafeArenaSwap(RepeatedField* other);

  // Copy constructs `n` instances in place into the array `dst`.
  // This function is identical to `std::uninitialized_copy_n(src, n, dst)`
  // except that we explicit declare the memory to not be aliased, which will
  // result in `memcpy` code generation instead of `memmove` for trivial types.
  static inline void UninitializedCopyN(const Element* PROTOBUF_RESTRICT src,
                                        int n, Element* PROTOBUF_RESTRICT dst) {
    std::uninitialized_copy_n(src, n, dst);
  }

  // Copy constructs `[begin, end)` instances in place into the array `dst`.
  // See above `UninitializedCopyN()` function comments for more information.
  template <typename Iter>
  static inline void UninitializedCopy(Iter begin, Iter end,
                                       Element* PROTOBUF_RESTRICT dst) {
    std::uninitialized_copy(begin, end, dst);
  }

  // Destroys all elements in [begin, end).
  // This function does nothing if `Element` is trivial.
  static void Destroy(const Element* begin, const Element* end) {
    if (!std::is_trivial<Element>::value) {
      std::for_each(begin, end, [&](const Element& e) { e.~Element(); });
    }
  }

  template <typename Iter>
  void AddForwardIterator(Iter begin, Iter end);

  template <typename Iter>
  void AddInputIterator(Iter begin, Iter end);

  // Reserves space to expand the field to at least the given size.
  // If the array is grown, it will always be at least doubled in size.
  // If `annotate_size` is true (the default), then this function will annotate
  // the old container from `old_size` to `Capacity()` (unpoison memory)
  // directly before it is being released, and annotate the new container from
  // `Capacity()` to `old_size` (poison unused memory).
  void Grow(bool was_soo, int old_size, int new_size);
  void GrowNoAnnotate(bool was_soo, int old_size, int new_size);

  // Annotates a change in size of this instance. This function should be called
  // with (capacity, old_size) after new memory has been allocated and filled
  // from previous memory, and UnpoisonBuffer() should be called right before
  // (previously annotated) memory is released.
  void AnnotateSize(int old_size, int new_size) const {
    if (old_size != new_size) {
      ABSL_ATTRIBUTE_UNUSED const bool is_soo = this->is_soo();
      ABSL_ATTRIBUTE_UNUSED const Element* elem = unsafe_elements(is_soo);
      ABSL_ANNOTATE_CONTIGUOUS_CONTAINER(elem, elem + Capacity(is_soo),
                                         elem + old_size, elem + new_size);
      if (new_size < old_size) {
        ABSL_ANNOTATE_MEMORY_IS_UNINITIALIZED(
            elem + new_size, (old_size - new_size) * sizeof(Element));
      }
    }
  }

  // Unpoisons the memory buffer.
  void UnpoisonBuffer() const {
    AnnotateSize(size(), Capacity());
    if (is_soo()) {
      // We need to manually unpoison the SOO buffer because in reflection for
      // split repeated fields, we poison the whole SOO buffer even when we
      // don't actually use the whole SOO buffer (e.g. for RepeatedField<bool>).
      internal::UnpoisonMemoryRegion(soo_rep_.short_rep.data,
                                     sizeof(soo_rep_.short_rep.data));
    }
  }

  // Replaces size with new_size and returns the previous value of
  // size. This function is intended to be the only place where
  // size is modified, with the exception of `AddInputIterator()`
  // where the size of added items is not known in advance.
  inline int ExchangeCurrentSize(bool is_soo, int new_size) {
    const int prev_size = size(is_soo);
    AnnotateSize(prev_size, new_size);
    set_size(is_soo, new_size);
    return prev_size;
  }

  // Returns a pointer to elements array.
  // pre-condition: Capacity() > 0.
  Element* elements(bool is_soo) {
    ABSL_DCHECK_GT(Capacity(is_soo), 0);
    return unsafe_elements(is_soo);
  }
  const Element* elements(bool is_soo) const {
    return const_cast<RepeatedField*>(this)->elements(is_soo);
  }

  // Returns a pointer to elements array if it exists; otherwise an invalid
  // pointer is returned. This only happens for empty repeated fields, where you
  // can't dereference this pointer anyway (it's empty).
  Element* unsafe_elements(bool is_soo) {
    return is_soo ? reinterpret_cast<Element*>(soo_rep_.short_rep.data)
                  : reinterpret_cast<Element*>(soo_rep_.long_rep.elements());
  }
  const Element* unsafe_elements(bool is_soo) const {
    return const_cast<RepeatedField*>(this)->unsafe_elements(is_soo);
  }

  // Returns a pointer to the HeapRep struct.
  // pre-condition: the HeapRep must have been allocated, ie !is_soo().
  HeapRep* heap_rep() const {
    ABSL_DCHECK(!is_soo());
    return reinterpret_cast<HeapRep*>(soo_rep_.long_rep.elements() -
                                      kHeapRepHeaderSize);
  }

  // Internal helper to delete all elements and deallocate the storage.
  template <bool in_destructor = false>
  void InternalDeallocate() {
    ABSL_DCHECK(!is_soo());
    const size_t bytes = Capacity(false) * sizeof(Element) + kHeapRepHeaderSize;
    if (heap_rep()->arena == nullptr) {
      internal::SizedDelete(heap_rep(), bytes);
    } else if (!in_destructor) {
      // If we are in the destructor, we might be being destroyed as part of
      // the arena teardown. We can't try and return blocks to the arena then.
      heap_rep()->arena->ReturnArrayMemory(heap_rep(), bytes);
    }
  }

  // A note on the representation here (see also comment below for
  // RepeatedPtrFieldBase's struct HeapRep):
  //
  // We maintain the same sizeof(RepeatedField) as before we added arena support
  // so that we do not degrade performance by bloating memory usage. Directly
  // adding an arena_ element to RepeatedField is quite costly. By using
  // indirection in this way, we keep the same size when the RepeatedField is
  // empty (common case), and add only an 8-byte header to the elements array
  // when non-empty. We make sure to place the size fields directly in the
  // RepeatedField class to avoid costly cache misses due to the indirection.
  internal::SooRep soo_rep_{};
};

// implementation ====================================================

template <typename Element>
constexpr RepeatedField<Element>::RepeatedField() {
  StaticValidityCheck();
#ifdef __cpp_lib_is_constant_evaluated
  if (!std::is_constant_evaluated()) {
    AnnotateSize(kSooCapacityElements, 0);
  }
#endif  // __cpp_lib_is_constant_evaluated
}

template <typename Element>
inline RepeatedField<Element>::RepeatedField(Arena* arena) : soo_rep_(arena) {
  StaticValidityCheck();
  AnnotateSize(kSooCapacityElements, 0);
}

template <typename Element>
inline RepeatedField<Element>::RepeatedField(Arena* arena,
                                             const RepeatedField& rhs)
    : soo_rep_(arena) {
  StaticValidityCheck();
  AnnotateSize(kSooCapacityElements, 0);
  const bool rhs_is_soo = rhs.is_soo();
  if (auto size = rhs.size(rhs_is_soo)) {
    bool is_soo = true;
    if (size > kSooCapacityElements) {
      Grow(is_soo, 0, size);
      is_soo = false;
    }
    ExchangeCurrentSize(is_soo, size);
    UninitializedCopyN(rhs.elements(rhs_is_soo), size, unsafe_elements(is_soo));
  }
}

template <typename Element>
template <typename Iter, typename>
RepeatedField<Element>::RepeatedField(Iter begin, Iter end) {
  StaticValidityCheck();
  AnnotateSize(kSooCapacityElements, 0);
  Add(begin, end);
}

template <typename Element>
RepeatedField<Element>::~RepeatedField() {
  StaticValidityCheck();
  const bool is_soo = this->is_soo();
#ifndef NDEBUG
  // Try to trigger segfault / asan failure in non-opt builds if arena_
  // lifetime has ended before the destructor.
  auto arena = GetArena(is_soo);
  if (arena) (void)arena->SpaceAllocated();
#endif
  const int size = this->size(is_soo);
  if (size > 0) {
    Element* elem = unsafe_elements(is_soo);
    Destroy(elem, elem + size);
  }
  UnpoisonBuffer();
  if (!is_soo) InternalDeallocate<true>();
}

template <typename Element>
inline RepeatedField<Element>& RepeatedField<Element>::operator=(
    const RepeatedField& other) ABSL_ATTRIBUTE_LIFETIME_BOUND {
  if (this != &other) CopyFrom(other);
  return *this;
}

template <typename Element>
inline RepeatedField<Element>::RepeatedField(Arena* arena, RepeatedField&& rhs)
    : RepeatedField(arena) {
  if (internal::CanMoveWithInternalSwap(arena, rhs.GetArena())) {
    InternalSwap(&rhs);
  } else {
    // We don't just call Swap(&rhs) here because it would perform 3 copies if
    // rhs is on a different arena.
    CopyFrom(rhs);
  }
}

template <typename Element>
inline RepeatedField<Element>& RepeatedField<Element>::operator=(
    RepeatedField&& other) noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
  // We don't just call Swap(&other) here because it would perform 3 copies if
  // the two fields are on different arenas.
  if (this != &other) {
    if (internal::CanMoveWithInternalSwap(GetArena(), other.GetArena())) {
      InternalSwap(&other);
    } else {
      CopyFrom(other);
    }
  }
  return *this;
}

template <typename Element>
inline bool RepeatedField<Element>::empty() const {
  return size() == 0;
}

template <typename Element>
inline int RepeatedField<Element>::size() const {
  return size(is_soo());
}

template <typename Element>
inline int RepeatedField<Element>::Capacity() const {
  return Capacity(is_soo());
}

template <typename Element>
inline void RepeatedField<Element>::AddAlreadyReserved(Element value) {
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_DCHECK_LT(old_size, Capacity(is_soo));
  void* p = elements(is_soo) + ExchangeCurrentSize(is_soo, old_size + 1);
  ::new (p) Element(std::move(value));
}

template <typename Element>
inline Element* RepeatedField<Element>::AddAlreadyReserved()
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_DCHECK_LT(old_size, Capacity(is_soo));
  // new (p) <TrivialType> compiles into nothing: this is intentional as this
  // function is documented to return uninitialized data for trivial types.
  void* p = elements(is_soo) + ExchangeCurrentSize(is_soo, old_size + 1);
  return ::new (p) Element;
}

template <typename Element>
inline Element* RepeatedField<Element>::AddNAlreadyReserved(int n)
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_ATTRIBUTE_UNUSED const int capacity = Capacity(is_soo);
  ABSL_DCHECK_GE(capacity - old_size, n) << capacity << ", " << old_size;
  Element* p =
      unsafe_elements(is_soo) + ExchangeCurrentSize(is_soo, old_size + n);
  for (Element *begin = p, *end = p + n; begin != end; ++begin) {
    new (static_cast<void*>(begin)) Element;
  }
  return p;
}

template <typename Element>
inline void RepeatedField<Element>::Resize(int new_size, const Element& value) {
  ABSL_DCHECK_GE(new_size, 0);
  bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  if (new_size > old_size) {
    if (new_size > Capacity(is_soo)) {
      Grow(is_soo, old_size, new_size);
      is_soo = false;
    }
    Element* elem = elements(is_soo);
    Element* first = elem + ExchangeCurrentSize(is_soo, new_size);
    std::uninitialized_fill(first, elem + new_size, value);
  } else if (new_size < old_size) {
    Element* elem = unsafe_elements(is_soo);
    Destroy(elem + new_size, elem + old_size);
    ExchangeCurrentSize(is_soo, new_size);
  }
}

template <typename Element>
inline const Element& RepeatedField<Element>::Get(int index) const
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  ABSL_DCHECK_GE(index, 0);
  ABSL_DCHECK_LT(index, size());
  return elements(is_soo())[index];
}

template <typename Element>
inline const Element& RepeatedField<Element>::at(int index) const
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  ABSL_CHECK_GE(index, 0);
  ABSL_CHECK_LT(index, size());
  return elements(is_soo())[index];
}

template <typename Element>
inline Element& RepeatedField<Element>::at(int index)
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  ABSL_CHECK_GE(index, 0);
  ABSL_CHECK_LT(index, size());
  return elements(is_soo())[index];
}

template <typename Element>
inline Element* RepeatedField<Element>::Mutable(int index)
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  ABSL_DCHECK_GE(index, 0);
  ABSL_DCHECK_LT(index, size());
  return &elements(is_soo())[index];
}

template <typename Element>
inline void RepeatedField<Element>::Set(int index, const Element& value) {
  *Mutable(index) = value;
}

template <typename Element>
inline void RepeatedField<Element>::Add(Element value) {
  bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  int capacity = Capacity(is_soo);
  Element* elem = unsafe_elements(is_soo);
  if (ABSL_PREDICT_FALSE(old_size == capacity)) {
    Grow(is_soo, old_size, old_size + 1);
    is_soo = false;
    capacity = Capacity(is_soo);
    elem = unsafe_elements(is_soo);
  }
  int new_size = old_size + 1;
  void* p = elem + ExchangeCurrentSize(is_soo, new_size);
  ::new (p) Element(std::move(value));

  // The below helps the compiler optimize dense loops.
  // Note: we can't call functions in PROTOBUF_ASSUME so use local variables.
  ABSL_ATTRIBUTE_UNUSED const bool final_is_soo = this->is_soo();
  PROTOBUF_ASSUME(is_soo == final_is_soo);
  ABSL_ATTRIBUTE_UNUSED const int final_size = size(is_soo);
  PROTOBUF_ASSUME(new_size == final_size);
  ABSL_ATTRIBUTE_UNUSED Element* const final_elements = unsafe_elements(is_soo);
  PROTOBUF_ASSUME(elem == final_elements);
  ABSL_ATTRIBUTE_UNUSED const int final_capacity = Capacity(is_soo);
  PROTOBUF_ASSUME(capacity == final_capacity);
}

template <typename Element>
inline Element* RepeatedField<Element>::Add() ABSL_ATTRIBUTE_LIFETIME_BOUND {
  bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  if (ABSL_PREDICT_FALSE(old_size == Capacity())) {
    Grow(is_soo, old_size, old_size + 1);
    is_soo = false;
  }
  void* p = unsafe_elements(is_soo) + ExchangeCurrentSize(is_soo, old_size + 1);
  return ::new (p) Element;
}

template <typename Element>
template <typename Iter>
inline void RepeatedField<Element>::AddForwardIterator(Iter begin, Iter end) {
  bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  int capacity = Capacity(is_soo);
  Element* elem = unsafe_elements(is_soo);
  int new_size = old_size + static_cast<int>(std::distance(begin, end));
  if (ABSL_PREDICT_FALSE(new_size > capacity)) {
    Grow(is_soo, old_size, new_size);
    is_soo = false;
    elem = unsafe_elements(is_soo);
    capacity = Capacity(is_soo);
  }
  UninitializedCopy(begin, end, elem + ExchangeCurrentSize(is_soo, new_size));

  // The below helps the compiler optimize dense loops.
  // Note: we can't call functions in PROTOBUF_ASSUME so use local variables.
  ABSL_ATTRIBUTE_UNUSED const bool final_is_soo = this->is_soo();
  PROTOBUF_ASSUME(is_soo == final_is_soo);
  ABSL_ATTRIBUTE_UNUSED const int final_size = size(is_soo);
  PROTOBUF_ASSUME(new_size == final_size);
  ABSL_ATTRIBUTE_UNUSED Element* const final_elements = unsafe_elements(is_soo);
  PROTOBUF_ASSUME(elem == final_elements);
  ABSL_ATTRIBUTE_UNUSED const int final_capacity = Capacity(is_soo);
  PROTOBUF_ASSUME(capacity == final_capacity);
}

template <typename Element>
template <typename Iter>
inline void RepeatedField<Element>::AddInputIterator(Iter begin, Iter end) {
  bool is_soo = this->is_soo();
  int size = this->size(is_soo);
  int capacity = Capacity(is_soo);
  Element* elem = unsafe_elements(is_soo);
  Element* first = elem + size;
  Element* last = elem + capacity;
  UnpoisonBuffer();

  while (begin != end) {
    if (ABSL_PREDICT_FALSE(first == last)) {
      size = first - elem;
      GrowNoAnnotate(is_soo, size, size + 1);
      is_soo = false;
      elem = unsafe_elements(is_soo);
      capacity = Capacity(is_soo);
      first = elem + size;
      last = elem + capacity;
    }
    ::new (static_cast<void*>(first)) Element(*begin);
    ++begin;
    ++first;
  }

  const int new_size = first - elem;
  set_size(is_soo, new_size);
  AnnotateSize(capacity, new_size);
}

template <typename Element>
template <typename Iter>
inline void RepeatedField<Element>::Add(Iter begin, Iter end) {
  if (std::is_base_of<
          std::forward_iterator_tag,
          typename std::iterator_traits<Iter>::iterator_category>::value) {
    AddForwardIterator(begin, end);
  } else {
    AddInputIterator(begin, end);
  }
}

template <typename Element>
inline void RepeatedField<Element>::RemoveLast() {
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_DCHECK_GT(old_size, 0);
  elements(is_soo)[old_size - 1].~Element();
  ExchangeCurrentSize(is_soo, old_size - 1);
}

template <typename Element>
void RepeatedField<Element>::ExtractSubrange(int start, int num,
                                             Element* elements) {
  ABSL_DCHECK_GE(start, 0);
  ABSL_DCHECK_GE(num, 0);
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_DCHECK_LE(start + num, old_size);
  Element* elem = unsafe_elements(is_soo);

  // Save the values of the removed elements if requested.
  if (elements != nullptr) {
    for (int i = 0; i < num; ++i) elements[i] = std::move(elem[i + start]);
  }

  // Slide remaining elements down to fill the gap.
  if (num > 0) {
    for (int i = start + num; i < old_size; ++i)
      elem[i - num] = std::move(elem[i]);
    Truncate(old_size - num);
  }
}

template <typename Element>
inline void RepeatedField<Element>::Clear() {
  const bool is_soo = this->is_soo();
  Element* elem = unsafe_elements(is_soo);
  Destroy(elem, elem + size(is_soo));
  ExchangeCurrentSize(is_soo, 0);
}

template <typename Element>
inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
  ABSL_DCHECK_NE(&other, this);
  const bool other_is_soo = other.is_soo();
  if (auto other_size = other.size(other_is_soo)) {
    const int old_size = size();
    Reserve(old_size + other_size);
    const bool is_soo = this->is_soo();
    Element* dst =
        elements(is_soo) + ExchangeCurrentSize(is_soo, old_size + other_size);
    UninitializedCopyN(other.elements(other_is_soo), other_size, dst);
  }
}

template <typename Element>
inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
  if (&other == this) return;
  Clear();
  MergeFrom(other);
}

template <typename Element>
template <typename Iter>
inline void RepeatedField<Element>::Assign(Iter begin, Iter end) {
  Clear();
  Add(begin, end);
}

template <typename Element>
inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase(
    const_iterator position) ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return erase(position, position + 1);
}

template <typename Element>
inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase(
    const_iterator first, const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND {
  size_type first_offset = first - cbegin();
  if (first != last) {
    Truncate(std::copy(last, cend(), begin() + first_offset) - cbegin());
  }
  return begin() + first_offset;
}

template <typename Element>
inline Element* RepeatedField<Element>::mutable_data()
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return unsafe_elements(is_soo());
}

template <typename Element>
inline const Element* RepeatedField<Element>::data() const
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return unsafe_elements(is_soo());
}

template <typename Element>
inline void RepeatedField<Element>::InternalSwap(
    RepeatedField* PROTOBUF_RESTRICT other) {
  ABSL_DCHECK(this != other);

  // We need to unpoison during the swap in case we're in SOO mode.
  UnpoisonBuffer();
  other->UnpoisonBuffer();

  internal::memswap<sizeof(internal::SooRep)>(
      reinterpret_cast<char*>(&this->soo_rep_),
      reinterpret_cast<char*>(&other->soo_rep_));

  AnnotateSize(Capacity(), size());
  other->AnnotateSize(other->Capacity(), other->size());
}

template <typename Element>
void RepeatedField<Element>::Swap(RepeatedField* other) {
  if (this == other) return;
  Arena* arena = GetArena();
  Arena* other_arena = other->GetArena();
  if (internal::CanUseInternalSwap(arena, other_arena)) {
    InternalSwap(other);
  } else {
    RepeatedField<Element> temp(other_arena);
    temp.MergeFrom(*this);
    CopyFrom(*other);
    other->UnsafeArenaSwap(&temp);
  }
}

template <typename Element>
void RepeatedField<Element>::UnsafeArenaSwap(RepeatedField* other) {
  if (this == other) return;
  ABSL_DCHECK_EQ(GetArena(), other->GetArena());
  InternalSwap(other);
}

template <typename Element>
void RepeatedField<Element>::SwapElements(int index1, int index2) {
  Element* elem = elements(is_soo());
  using std::swap;  // enable ADL with fallback
  swap(elem[index1], elem[index2]);
}

template <typename Element>
inline typename RepeatedField<Element>::iterator RepeatedField<Element>::begin()
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return iterator(unsafe_elements(is_soo()));
}
template <typename Element>
inline typename RepeatedField<Element>::const_iterator
RepeatedField<Element>::begin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return const_iterator(unsafe_elements(is_soo()));
}
template <typename Element>
inline typename RepeatedField<Element>::const_iterator
RepeatedField<Element>::cbegin() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
  return const_iterator(unsafe_elements(is_soo()));
}
template <typename Element>
inline typename RepeatedField<Element>::iterator RepeatedField<Element>::end()
    ABSL_ATTRIBUTE_LIFETIME_BOUND {
  const bool is_soo = this->is_soo();
  return iterator(unsafe_elements(is_soo) + size(is_soo));
}
template <typename Element>
inline typename RepeatedField<Element>::const_iterator
RepeatedField<Element>::end() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
  const bool is_soo = this->is_soo();
  return const_iterator(unsafe_elements(is_soo) + size(is_soo));
}
template <typename Element>
inline typename RepeatedField<Element>::const_iterator
RepeatedField<Element>::cend() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
  const bool is_soo = this->is_soo();
  return const_iterator(unsafe_elements(is_soo) + size(is_soo));
}

template <typename Element>
inline size_t RepeatedField<Element>::SpaceUsedExcludingSelfLong() const {
  const int capacity = Capacity();
  return capacity > kSooCapacityElements
             ? capacity * sizeof(Element) + kHeapRepHeaderSize
             : 0;
}

namespace internal {
// Returns the new size for a reserved field based on its 'capacity' and the
// requested 'new_size'. The result is clamped to the closed interval:
//   [internal::kMinRepeatedFieldAllocationSize,
//    std::numeric_limits<int>::max()]
// Requires: new_size > capacity
template <typename T, int kHeapRepHeaderSize>
inline int CalculateReserveSize(int capacity, int new_size) {
  constexpr int lower_limit =
      RepeatedFieldLowerClampLimit<T, kHeapRepHeaderSize>();
  if (new_size < lower_limit) {
    // Clamp to smallest allowed size.
    return lower_limit;
  }
  constexpr int kMaxSizeBeforeClamp =
      (std::numeric_limits<int>::max() - kHeapRepHeaderSize) / 2;
  if (ABSL_PREDICT_FALSE(capacity > kMaxSizeBeforeClamp)) {
    return std::numeric_limits<int>::max();
  }
  constexpr int kSooCapacityElements = SooCapacityElements(sizeof(T));
  if (kSooCapacityElements > 0 && kSooCapacityElements < lower_limit) {
    // In this case, we need to set capacity to 0 here to ensure power-of-two
    // sized allocations.
    if (capacity < lower_limit) capacity = 0;
  } else {
    ABSL_DCHECK(capacity == 0 || capacity >= lower_limit)
        << capacity << " " << lower_limit;
  }
  // We want to double the number of bytes, not the number of elements, to try
  // to stay within power-of-two allocations.
  // The allocation has kHeapRepHeaderSize + sizeof(T) * capacity.
  int doubled_size = 2 * capacity + kHeapRepHeaderSize / sizeof(T);
  return std::max(doubled_size, new_size);
}
}  // namespace internal

template <typename Element>
void RepeatedField<Element>::Reserve(int new_size) {
  const bool was_soo = is_soo();
  if (ABSL_PREDICT_FALSE(new_size > Capacity(was_soo))) {
    Grow(was_soo, size(was_soo), new_size);
  }
}

// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
// amount of code bloat.
template <typename Element>
PROTOBUF_NOINLINE void RepeatedField<Element>::GrowNoAnnotate(bool was_soo,
                                                              int old_size,
                                                              int new_size) {
  const int old_capacity = Capacity(was_soo);
  ABSL_DCHECK_GT(new_size, old_capacity);
  HeapRep* new_rep;
  Arena* arena = GetArena();

  new_size = internal::CalculateReserveSize<Element, kHeapRepHeaderSize>(
      old_capacity, new_size);

  ABSL_DCHECK_LE(static_cast<size_t>(new_size),
                 (std::numeric_limits<size_t>::max() - kHeapRepHeaderSize) /
                     sizeof(Element))
      << "Requested size is too large to fit into size_t.";
  size_t bytes =
      kHeapRepHeaderSize + sizeof(Element) * static_cast<size_t>(new_size);
  if (arena == nullptr) {
    ABSL_DCHECK_LE((bytes - kHeapRepHeaderSize) / sizeof(Element),
                   static_cast<size_t>(std::numeric_limits<int>::max()))
        << "Requested size is too large to fit element count into int.";
    internal::SizedPtr res = internal::AllocateAtLeast(bytes);
    size_t num_available =
        std::min((res.n - kHeapRepHeaderSize) / sizeof(Element),
                 static_cast<size_t>(std::numeric_limits<int>::max()));
    new_size = static_cast<int>(num_available);
    new_rep = static_cast<HeapRep*>(res.p);
  } else {
    new_rep =
        reinterpret_cast<HeapRep*>(Arena::CreateArray<char>(arena, bytes));
  }
  new_rep->arena = arena;

  if (old_size > 0) {
    Element* pnew = static_cast<Element*>(new_rep->elements());
    Element* pold = elements(was_soo);
    // TODO: add absl::is_trivially_relocatable<Element>
    if (std::is_trivial<Element>::value) {
      memcpy(static_cast<void*>(pnew), pold, old_size * sizeof(Element));
    } else {
      for (Element* end = pnew + old_size; pnew != end; ++pnew, ++pold) {
        ::new (static_cast<void*>(pnew)) Element(std::move(*pold));
        pold->~Element();
      }
    }
  }
  if (!was_soo) InternalDeallocate();

  soo_rep_.set_non_soo(was_soo, new_size, new_rep->elements());
}

// Ideally we would be able to use:
//   template <bool annotate_size = true>
//   void Grow();
// However, as explained in b/266411038#comment9, this causes issues
// in shared libraries for Youtube (and possibly elsewhere).
template <typename Element>
PROTOBUF_NOINLINE void RepeatedField<Element>::Grow(bool was_soo, int old_size,
                                                    int new_size) {
  UnpoisonBuffer();
  GrowNoAnnotate(was_soo, old_size, new_size);
  AnnotateSize(Capacity(), old_size);
}

template <typename Element>
inline void RepeatedField<Element>::Truncate(int new_size) {
  const bool is_soo = this->is_soo();
  const int old_size = size(is_soo);
  ABSL_DCHECK_LE(new_size, old_size);
  if (new_size < old_size) {
    Element* elem = unsafe_elements(is_soo);
    Destroy(elem + new_size, elem + old_size);
    ExchangeCurrentSize(is_soo, new_size);
  }
}

template <>
PROTOBUF_EXPORT size_t
RepeatedField<absl::Cord>::SpaceUsedExcludingSelfLong() const;


// -------------------------------------------------------------------

// Iterators and helper functions that follow the spirit of the STL
// std::back_insert_iterator and std::back_inserter but are tailor-made
// for RepeatedField and RepeatedPtrField. Typical usage would be:
//
//   std::copy(some_sequence.begin(), some_sequence.end(),
//             RepeatedFieldBackInserter(proto.mutable_sequence()));
//
// Ported by johannes from util/gtl/proto-array-iterators.h

namespace internal {

// STL-like iterator implementation for RepeatedField.  You should not
// refer to this class directly; use RepeatedField<T>::iterator instead.
//
// Note: All of the iterator operators *must* be inlined to avoid performance
// regressions.  This is caused by the extern template declarations below (which
// are required because of the RepeatedField extern template declarations).  If
// any of these functions aren't explicitly inlined (e.g. defined in the class),
// the compiler isn't allowed to inline them.
template <typename Element>
class RepeatedIterator {
 private:
  using traits =
      std::iterator_traits<typename std::remove_const<Element>::type*>;

 public:
  // Note: value_type is never cv-qualified.
  using value_type = typename traits::value_type;
  using difference_type = typename traits::difference_type;
  using pointer = Element*;
  using reference = Element&;
  using iterator_category = typename traits::iterator_category;
  using iterator_concept = typename IteratorConceptSupport<traits>::tag;

  constexpr RepeatedIterator() noexcept : it_(nullptr) {}

  // Allows "upcasting" from RepeatedIterator<T**> to
  // RepeatedIterator<const T*const*>.
  template <typename OtherElement,
            typename std::enable_if<std::is_convertible<
                OtherElement*, pointer>::value>::type* = nullptr>
  constexpr RepeatedIterator(
      const RepeatedIterator<OtherElement>& other) noexcept
      : it_(other.it_) {}

  // dereferenceable
  constexpr reference operator*() const noexcept { return *it_; }
  constexpr pointer operator->() const noexcept { return it_; }

 private:
  // Helper alias to hide the internal type.
  using iterator = RepeatedIterator<Element>;

 public:
  // {inc,dec}rementable
  iterator& operator++() noexcept {
    ++it_;
    return *this;
  }
  iterator operator++(int) noexcept { return iterator(it_++); }
  iterator& operator--() noexcept {
    --it_;
    return *this;
  }
  iterator operator--(int) noexcept { return iterator(it_--); }

  // equality_comparable
  friend constexpr bool operator==(const iterator& x,
                                   const iterator& y) noexcept {
    return x.it_ == y.it_;
  }
  friend constexpr bool operator!=(const iterator& x,
                                   const iterator& y) noexcept {
    return x.it_ != y.it_;
  }

  // less_than_comparable
  friend constexpr bool operator<(const iterator& x,
                                  const iterator& y) noexcept {
    return x.it_ < y.it_;
  }
  friend constexpr bool operator<=(const iterator& x,
                                   const iterator& y) noexcept {
    return x.it_ <= y.it_;
  }
  friend constexpr bool operator>(const iterator& x,
                                  const iterator& y) noexcept {
    return x.it_ > y.it_;
  }
  friend constexpr bool operator>=(const iterator& x,
                                   const iterator& y) noexcept {
    return x.it_ >= y.it_;
  }

  // addable, subtractable
  iterator& operator+=(difference_type d) noexcept {
    it_ += d;
    return *this;
  }
  constexpr iterator operator+(difference_type d) const noexcept {
    return iterator(it_ + d);
  }
  friend constexpr iterator operator+(const difference_type d,
                                      iterator it) noexcept {
    return it + d;
  }

  iterator& operator-=(difference_type d) noexcept {
    it_ -= d;
    return *this;
  }
  iterator constexpr operator-(difference_type d) const noexcept {
    return iterator(it_ - d);
  }

  // indexable
  constexpr reference operator[](difference_type d) const noexcept {
    return it_[d];
  }

  // random access iterator
  friend constexpr difference_type operator-(iterator it1,
                                             iterator it2) noexcept {
    return it1.it_ - it2.it_;
  }

 private:
  template <typename OtherElement>
  friend class RepeatedIterator;

  // Allow construction from RepeatedField.
  friend class RepeatedField<value_type>;
  explicit RepeatedIterator(pointer it) noexcept : it_(it) {}

  // The internal iterator.
  pointer it_;
};

// A back inserter for RepeatedField objects.
template <typename T>
class RepeatedFieldBackInsertIterator {
 public:
  using iterator_category = std::output_iterator_tag;
  using value_type = T;
  using pointer = void;
  using reference = void;
  using difference_type = std::ptrdiff_t;

  explicit RepeatedFieldBackInsertIterator(
      RepeatedField<T>* const mutable_field)
      : field_(mutable_field) {}
  RepeatedFieldBackInsertIterator<T>& operator=(const T& value) {
    field_->Add(value);
    return *this;
  }
  RepeatedFieldBackInsertIterator<T>& operator*() { return *this; }
  RepeatedFieldBackInsertIterator<T>& operator++() { return *this; }
  RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) {
    return *this;
  }

 private:
  RepeatedField<T>* field_;
};

}  // namespace internal

// Provides a back insert iterator for RepeatedField instances,
// similar to std::back_inserter().
template <typename T>
internal::RepeatedFieldBackInsertIterator<T> RepeatedFieldBackInserter(
    RepeatedField<T>* const mutable_field) {
  return internal::RepeatedFieldBackInsertIterator<T>(mutable_field);
}


}  // namespace protobuf
}  // namespace google

#include "google/protobuf/port_undef.inc"

#endif  // GOOGLE_PROTOBUF_REPEATED_FIELD_H__