multibuf_v2.h

// Copyright 2025 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
 
// NOTE: MultiBuf version 2 is in a nearly stable state, but may still change.
// The Pigweed team will announce breaking changes in the API. It is strongly
// recommended to coordinate with the Pigweed team if you want to start using
// this code.
 
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <type_traits>
 
#include "pw_allocator/allocator.h"
#include "pw_allocator/null_allocator.h"
#include "pw_bytes/span.h"
#include "pw_containers/dynamic_deque.h"
#include "pw_multibuf/chunks.h"
#include "pw_multibuf/internal/byte_iterator.h"
#include "pw_multibuf/internal/entry.h"
#include "pw_multibuf/observer.h"
#include "pw_multibuf/properties.h"
 
namespace pw {
 
// Forward declarations.
template <multibuf::Property...>
class BasicMultiBuf;
 
 
// Type aliases of the BasicMultiBuf interface types for each different
// combination of propeties, listed here for easier discoverability.
 
using FlatMultiBuf = BasicMultiBuf<>;
 
using FlatConstMultiBuf = BasicMultiBuf<multibuf::Property::kConst>;
 
using MultiBuf = BasicMultiBuf<multibuf::Property::kLayerable>;
 
using ConstMultiBuf =
    BasicMultiBuf<multibuf::Property::kConst, multibuf::Property::kLayerable>;
 
using TrackedFlatMultiBuf = BasicMultiBuf<multibuf::Property::kObservable>;
 
using TrackedFlatConstMultiBuf =
    BasicMultiBuf<multibuf::Property::kConst, multibuf::Property::kObservable>;
 
using TrackedMultiBuf = BasicMultiBuf<multibuf::Property::kLayerable,
                                      multibuf::Property::kObservable>;
 
using TrackedConstMultiBuf = BasicMultiBuf<multibuf::Property::kConst,
                                           multibuf::Property::kLayerable,
                                           multibuf::Property::kObservable>;
 
namespace multibuf::internal {
 
class GenericMultiBuf;
 
template <typename>
class Instance;
 
}  // namespace multibuf::internal
 
template <multibuf::Property... kProperties>
class BasicMultiBuf {
 protected:
  using Deque = DynamicDeque<multibuf::internal::Entry>;
  using GenericMultiBuf = multibuf::internal::GenericMultiBuf;
 
 public:
  [[nodiscard]] static constexpr bool is_const() {
    return ((kProperties == multibuf::Property::kConst) || ...);
  }
 
  [[nodiscard]] static constexpr bool is_layerable() {
    return ((kProperties == multibuf::Property::kLayerable) || ...);
  }
 
  [[nodiscard]] static constexpr bool is_observable() {
    return ((kProperties == multibuf::Property::kObservable) || ...);
  }
 
  using size_type = typename Deque::size_type;
  using difference_type = typename Deque::difference_type;
  using iterator = multibuf::internal::
      ByteIterator<size_type, multibuf::internal::ChunkMutability::kMutable>;
  using const_iterator = multibuf::internal::
      ByteIterator<size_type, multibuf::internal::ChunkMutability::kConst>;
  using pointer = iterator::pointer;
  using const_pointer = const_iterator::pointer;
  using reference = iterator::reference;
  using const_reference = const_iterator::reference;
  using value_type = std::conditional_t<is_const(),
                                        const_iterator::value_type,
                                        iterator::value_type>;
 
  using ChunksType = multibuf::internal::Chunks<Deque>;
  using ConstChunksType = multibuf::internal::ConstChunks<Deque>;
 
  using Instance = multibuf::internal::Instance<BasicMultiBuf>;
 
  // Interfaces are not copyable or movable; copy and move `Instance`s instead.
 
  BasicMultiBuf(const BasicMultiBuf&) { InvalidCopyOrMove<>(); }
 
  template <multibuf::Property... kOtherProperties>
  BasicMultiBuf(const BasicMultiBuf<kOtherProperties...>&) {
    InvalidCopyOrMove<>();
  }
 
  BasicMultiBuf& operator=(const BasicMultiBuf&) { InvalidCopyOrMove<>(); }
 
  template <multibuf::Property... kOtherProperties>
  BasicMultiBuf& operator=(const BasicMultiBuf<kOtherProperties...>&) {
    InvalidCopyOrMove<>();
  }
 
  BasicMultiBuf(BasicMultiBuf&&) { InvalidCopyOrMove<>(); }
 
  BasicMultiBuf& operator=(BasicMultiBuf&&) { InvalidCopyOrMove<>(); }
 
  // Conversions
 
  template <typename OtherMultiBuf>
  constexpr OtherMultiBuf& as() & {
    multibuf::internal::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return generic().template as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf>
  constexpr const OtherMultiBuf& as() const& {
    multibuf::internal::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return generic().template as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf>
  constexpr OtherMultiBuf&& as() && {
    multibuf::internal::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return std::move(generic().template as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf>
  constexpr const OtherMultiBuf&& as() const&& {
    multibuf::internal::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return std::move(generic().template as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf::internal::EnableIfConvertible<BasicMultiBuf,
                                                               OtherMultiBuf>>
  constexpr operator OtherMultiBuf&() & {
    return as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf::internal::EnableIfConvertible<BasicMultiBuf,
                                                               OtherMultiBuf>>
  constexpr operator const OtherMultiBuf&() const& {
    return as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf::internal::EnableIfConvertible<BasicMultiBuf,
                                                               OtherMultiBuf>>
  constexpr operator OtherMultiBuf&&() && {
    return std::move(as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf::internal::EnableIfConvertible<BasicMultiBuf,
                                                               OtherMultiBuf>>
  constexpr operator const OtherMultiBuf&&() const&& {
    return std::move(as<OtherMultiBuf>());
  }
 
  // Accessors
 
  constexpr bool empty() const { return generic().empty(); }
 
  constexpr bool at_capacity() const { return generic().at_capacity(); }
 
  constexpr size_t size() const { return generic().size(); }
 
  template <bool kMutable = !is_const()>
  std::enable_if_t<kMutable, reference> at(size_t index) {
    return *(begin() + static_cast<int>(index));
  }
  const_reference at(size_t index) const {
    return *(begin() + static_cast<int>(index));
  }
 
  template <bool kMutable = !is_const()>
  std::enable_if_t<kMutable, reference> operator[](size_t index) {
    return at(index);
  }
  const_reference operator[](size_t index) const { return at(index); }
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, ChunksType> Chunks() {
    return generic().Chunks();
  }
  constexpr ConstChunksType Chunks() const { return generic().ConstChunks(); }
  constexpr ConstChunksType ConstChunks() const {
    return generic().ConstChunks();
  }
 
  // Iterators.
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, iterator> begin() {
    return generic().begin();
  }
  constexpr const_iterator begin() const { return cbegin(); }
  constexpr const_iterator cbegin() const { return generic().cbegin(); }
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, iterator> end() {
    return generic().end();
  }
  constexpr const_iterator end() const { return cend(); }
  constexpr const_iterator cend() const { return generic().cend(); }
 
  // Other methods
 
  [[nodiscard]] bool TryReserveChunks(size_t num_chunks) {
    return generic().TryReserveChunks(num_chunks);
  }
 
  // Mutators
 
  template <multibuf::Property... kOtherProperties>
  [[nodiscard]] bool TryReserveForInsert(
      const_iterator pos, const BasicMultiBuf<kOtherProperties...>& mb);
 
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos);
 
  template <multibuf::Property... kOtherProperties>
  void Insert(const_iterator pos, BasicMultiBuf<kOtherProperties...>&& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  void Insert(const_iterator pos, const T& bytes);
 
  void Insert(const_iterator pos, UniquePtr<std::byte[]>&& bytes) {
    Insert(pos, std::move(bytes), 0);
  }
  void Insert(const_iterator pos, UniquePtr<const std::byte[]>&& bytes) {
    Insert(pos, std::move(bytes), 0);
  }
 
  void Insert(const_iterator pos,
              UniquePtr<std::byte[]>&& bytes,
              size_t offset,
              size_t length = dynamic_extent);
  void Insert(const_iterator pos,
              UniquePtr<const std::byte[]>&& bytes,
              size_t offset,
              size_t length = dynamic_extent);
 
  void Insert(const_iterator pos, const SharedPtr<std::byte[]>& bytes) {
    Insert(pos, bytes, 0);
  }
  void Insert(const_iterator pos, const SharedPtr<const std::byte[]>& bytes) {
    Insert(pos, bytes, 0);
  }
 
  void Insert(const_iterator pos,
              const SharedPtr<std::byte[]>& bytes,
              size_t offset,
              size_t length = dynamic_extent);
  void Insert(const_iterator pos,
              const SharedPtr<const std::byte[]>& bytes,
              size_t offset,
              size_t length = dynamic_extent);
 
  template <multibuf::Property... kOtherProperties>
  [[nodiscard]] bool TryReserveForPushBack(
      const BasicMultiBuf<kOtherProperties...>& mb);
 
  [[nodiscard]] bool TryReserveForPushBack();
 
  template <multibuf::Property... kOtherProperties>
  void PushBack(BasicMultiBuf<kOtherProperties...>&& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  void PushBack(const T& bytes);
 
  void PushBack(UniquePtr<std::byte[]>&& bytes) {
    PushBack(std::move(bytes), 0);
  }
  void PushBack(UniquePtr<const std::byte[]>&& bytes) {
    PushBack(std::move(bytes), 0);
  }
 
  void PushBack(UniquePtr<std::byte[]>&& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  void PushBack(UniquePtr<const std::byte[]>&& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  void PushBack(const SharedPtr<std::byte[]>& bytes) { PushBack(bytes, 0); }
  void PushBack(const SharedPtr<const std::byte[]>& bytes) {
    PushBack(bytes, 0);
  }
 
  void PushBack(const SharedPtr<std::byte[]>& bytes,
                size_t offset,
                size_t length = dynamic_extent);
  void PushBack(const SharedPtr<const std::byte[]>& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  [[nodiscard]] bool IsRemovable(const_iterator pos, size_t size) const {
    return generic().IsRemovable(pos, size);
  }
 
  Result<Instance> Remove(const_iterator pos, size_t size);
 
  Result<Instance> PopFrontFragment();
 
  // clang-format off
  // clang-format on
  Result<const_iterator> Discard(const_iterator pos, size_t size) {
    return generic().Discard(pos, size);
  }
 
  [[nodiscard]] bool IsReleasable(const_iterator pos) const {
    return generic().IsReleasable(pos);
  }
 
  UniquePtr<value_type[]> Release(const_iterator pos);
 
  [[nodiscard]] bool IsShareable(const_iterator pos) const {
    return generic().IsShareable(pos);
  }
 
  SharedPtr<value_type[]> Share(const_iterator pos);
 
  size_t CopyTo(ByteSpan dst, size_t offset = 0) const {
    return generic().CopyTo(dst, offset);
  }
 
  size_t CopyFrom(ConstByteSpan src, size_t offset = 0) {
    static_assert(!is_const(),
                  "`CopyFrom` may only be called on mutable MultiBufs");
    return generic().CopyFrom(src, offset);
  }
 
  ConstByteSpan Get(ByteSpan copy, size_t offset = 0) const {
    return generic().Get(copy, offset);
  }
 
  template <int&... kExplicitGuard, typename Visitor>
  auto Visit(Visitor visitor, ByteSpan copy, size_t offset) {
    return visitor(Get(copy, offset));
  }
 
  void Clear() { generic().Clear(); }
 
  void ShrinkToFit() { generic().ShrinkToFit(); }
 
  // Observable methods.
 
  constexpr multibuf::Observer* observer() const {
    static_assert(is_observable(),
                  "`observer` may only be called on observable MultiBufs");
    return generic().observer_;
  }
 
  void set_observer(multibuf::Observer* observer) {
    static_assert(is_observable(),
                  "`set_observer` may only be called on observable MultiBufs");
    generic().observer_ = observer;
  }
 
  // Layerable methods.
 
  size_type NumFragments() const {
    static_assert(is_layerable(),
                  "`NumFragments` may only be called on layerable MultiBufs");
    return generic().NumFragments();
  }
 
  constexpr size_type NumLayers() const {
    static_assert(is_layerable(),
                  "`NumLayers` may only be called on layerable MultiBufs");
    return generic().NumLayers();
  }
 
  [[nodiscard]] bool TryReserveLayers(size_t num_layers,
                                      size_t num_chunks = 1) {
    return generic().TryReserveLayers(num_layers, num_chunks);
  }
 
  [[nodiscard]] bool AddLayer(size_t offset, size_t length = dynamic_extent) {
    static_assert(is_layerable(),
                  "`AddLayer` may only be called on layerable MultiBufs");
    return generic().AddLayer(offset, length);
  }
 
  void SealTopLayer() {
    static_assert(is_layerable(),
                  "`SealTopLayer` may only be called on layerable MultiBufs");
    return generic().SealTopLayer();
  }
 
  void UnsealTopLayer() {
    static_assert(is_layerable(),
                  "`UnsealTopLayer` may only be called on layerable MultiBufs");
    return generic().UnsealTopLayer();
  }
 
  [[nodiscard]] bool IsTopLayerSealed() {
    static_assert(
        is_layerable(),
        "`IsTopLayerSealed` may only be called on layerable MultiBufs");
    return generic().IsTopLayerSealed();
  }
 
  void TruncateTopLayer(size_t length) {
    static_assert(
        is_layerable(),
        "`TruncateTopLayer` may only be called on layerable MultiBufs");
    generic().TruncateTopLayer(length);
  }
 
  void SetTopLayer(ConstByteSpan src) {
    static_assert(!is_const() && is_layerable(),
                  "`SetTopLayer` may only be called on mutable, layerable "
                  "MultiBufs");
    PW_ASSERT(src.size() <= size());
    CopyFrom(src);
    TruncateTopLayer(src.size());
  }
 
  void PopLayer() {
    static_assert(is_layerable(),
                  "`PopLayer` may only be called on layerable MultiBufs");
    generic().PopLayer();
  }
 
 protected:
  constexpr BasicMultiBuf() { multibuf::internal::PropertiesAreValid(); }
 
 private:
  template <bool kValidCopyOrMove = false>
  static constexpr void InvalidCopyOrMove() {
    static_assert(kValidCopyOrMove,
                  "Only copies and moves from `BasicMultiBuf<...>::Instance`"
                  "to `BasicMultiBuf<...>&` or another "
                  "`BasicMultiBuf<...>::Instance` are valid.");
  }
 
  template <multibuf::Property...>
  friend class BasicMultiBuf;
 
  constexpr GenericMultiBuf& generic() {
    return static_cast<GenericMultiBuf&>(*this);
  }
  constexpr const GenericMultiBuf& generic() const {
    return static_cast<const GenericMultiBuf&>(*this);
  }
};
 
 
 
namespace multibuf::internal {
 
// A generic MultiBuf implementation that provides the functionality of any
// `BasicMultiBuf<kProperties>` type.
//
// This class should not be instantiated directly. Instead, use `Instance` as
// described below. This is the base class for all `Instance` types, and derives
// from every supported `BasicMultiBuf` type. It implements the MultiBuf
// behavior in one type, and allows for performing conversions from `Instance`s
// and `BasicMultiBuf`s to `BasicMultiBuf`s with different yet compatible
// propreties.
class GenericMultiBuf final
    : private BasicMultiBuf<>,
      private BasicMultiBuf<Property::kObservable>,
      private BasicMultiBuf<Property::kLayerable>,
      private BasicMultiBuf<Property::kConst>,
      private BasicMultiBuf<Property::kConst, Property::kObservable>,
      private BasicMultiBuf<Property::kConst, Property::kLayerable>,
      private BasicMultiBuf<Property::kLayerable, Property::kObservable>,
      private BasicMultiBuf<Property::kConst,
                            Property::kLayerable,
                            Property::kObservable> {
 private:
  using ControlBlock = allocator::internal::ControlBlock;
  using typename BasicMultiBuf<>::ChunksType;
  using typename BasicMultiBuf<>::ConstChunksType;
  using typename BasicMultiBuf<>::Deque;
 
 public:
  using typename BasicMultiBuf<>::const_iterator;
  using typename BasicMultiBuf<>::const_pointer;
  using typename BasicMultiBuf<>::const_reference;
  using typename BasicMultiBuf<>::difference_type;
  using typename BasicMultiBuf<>::iterator;
  using typename BasicMultiBuf<>::pointer;
  using typename BasicMultiBuf<>::reference;
  using typename BasicMultiBuf<>::size_type;
 
  ~GenericMultiBuf() { Clear(); }
 
  // Not copyable.
  GenericMultiBuf(const GenericMultiBuf&) = delete;
  GenericMultiBuf& operator=(const GenericMultiBuf&) = delete;
 
  // Movable.
  GenericMultiBuf(GenericMultiBuf&& other)
      : GenericMultiBuf(other.deque_.get_allocator()) {
    *this = std::move(other);
  }
  GenericMultiBuf& operator=(GenericMultiBuf&& other);
 
 private:
  template <::pw::multibuf::Property...>
  friend class ::pw::BasicMultiBuf;
 
  template <typename>
  friend class Instance;
 
  constexpr explicit GenericMultiBuf(Allocator& allocator)
      : deque_(allocator) {}
 
  template <typename MultiBufType>
  constexpr MultiBufType& as() {
    return *this;
  }
 
  template <typename MultiBufType>
  constexpr const MultiBufType& as() const {
    return *this;
  }
 
  // Accessors.
 
  constexpr bool empty() const { return deque_.empty(); }
 
  constexpr bool at_capacity() const {
    return deque_.size() == deque_.capacity();
  }
 
  constexpr size_t size() const {
    return static_cast<size_t>(cend() - cbegin());
  }
 
  // Iterators.
 
  constexpr ChunksType Chunks() {
    return ChunksType(deque_, entries_per_chunk_);
  }
  constexpr ConstChunksType ConstChunks() const {
    return ConstChunksType(deque_, entries_per_chunk_);
  }
 
  constexpr iterator begin() { return iterator(Chunks().begin(), 0); }
  constexpr const_iterator cbegin() const {
    return const_iterator(ConstChunks().cbegin(), 0);
  }
 
  constexpr iterator end() { return iterator(Chunks().end(), 0); }
  constexpr const_iterator cend() const {
    return const_iterator(ConstChunks().cend(), 0);
  }
 
  // Mutators.
 
  [[nodiscard]] bool TryReserveChunks(size_t num_chunks) {
    return TryReserveLayers(NumLayers(), num_chunks);
  }
 
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         const GenericMultiBuf& mb);
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos);
 
  void Insert(const_iterator pos, GenericMultiBuf&& mb);
  void Insert(const_iterator pos, ConstByteSpan bytes);
  void Insert(const_iterator pos,
              ConstByteSpan bytes,
              size_t offset,
              size_t length,
              Deallocator* deallocator);
  void Insert(const_iterator pos,
              ConstByteSpan bytes,
              size_t offset,
              size_t length,
              ControlBlock* control_block);
 
  [[nodiscard]] constexpr bool IsRemovable(const_iterator pos,
                                           size_t size) const {
    return pos != cend() && size != 0 &&
           size <= static_cast<size_t>(cend() - pos);
  }
 
  Result<GenericMultiBuf> Remove(const_iterator pos, size_t size);
 
  Result<GenericMultiBuf> PopFrontFragment();
 
  Result<const_iterator> Discard(const_iterator pos, size_t size);
 
  [[nodiscard]] bool IsReleasable(const_iterator pos) const;
 
  UniquePtr<std::byte[]> Release(const_iterator pos);
 
  [[nodiscard]] bool IsShareable(const_iterator pos) const;
 
  SharedPtr<std::byte[]> Share(const_iterator pos);
 
  size_t CopyTo(ByteSpan dst, size_t offset) const {
    return CopyToImpl(dst, offset, 0);
  }
 
  size_t CopyFrom(ConstByteSpan src, size_t offset);
 
  ConstByteSpan Get(ByteSpan copy, size_t offset) const;
 
  void Clear();
 
  void ShrinkToFit();
 
  // Layerable methods.
 
  size_type NumFragments() const;
 
  constexpr size_type NumLayers() const {
    return entries_per_chunk_ - Entry::kMinEntriesPerChunk + 1;
  }
 
  [[nodiscard]] bool TryReserveLayers(size_t num_layers, size_t num_chunks = 1);
 
  [[nodiscard]] bool AddLayer(size_t offset, size_t length = dynamic_extent);
 
  void SealTopLayer();
 
  void UnsealTopLayer();
 
  void TruncateTopLayer(size_t length);
 
  void PopLayer();
 
  // Implementation methods.
  //
  // These methods are used to implement the methods above, and should not be
  // called directly by BasicMultiBuf<>.
 
  static size_t CheckRange(size_t offset, size_t length, size_t size);
 
  constexpr size_type num_chunks() const {
    return deque_.size() / entries_per_chunk_;
  }
 
  constexpr size_type memory_context_index(size_type chunk) const {
    return Entry::memory_context_index(chunk, entries_per_chunk_);
  }
 
  constexpr size_type data_index(size_type chunk) const {
    return Entry::data_index(chunk, entries_per_chunk_);
  }
 
  constexpr size_type base_view_index(size_type chunk) const {
    return Entry::base_view_index(chunk, entries_per_chunk_);
  }
 
  constexpr size_type view_index(size_type chunk, size_type layer) const {
    return Entry::view_index(chunk, entries_per_chunk_, layer);
  }
 
  constexpr size_type top_view_index(size_type chunk) const {
    return Entry::top_view_index(chunk, entries_per_chunk_);
  }
 
  constexpr std::byte* GetData(size_type chunk) const {
    return deque_[data_index(chunk)].data;
  }
 
  constexpr bool IsOwned(size_type chunk) const {
    return deque_[base_view_index(chunk)].base_view.owned;
  }
 
  constexpr bool IsShared(size_type chunk) const {
    return deque_[base_view_index(chunk)].base_view.shared;
  }
 
  constexpr bool IsSealed(size_type chunk) const {
    return entries_per_chunk_ == Entry::kMinEntriesPerChunk
               ? false
               : deque_[top_view_index(chunk)].view.sealed;
  }
 
  constexpr bool IsBoundary(size_type chunk) const {
    return entries_per_chunk_ == Entry::kMinEntriesPerChunk
               ? true
               : deque_[top_view_index(chunk)].view.boundary;
  }
 
  constexpr size_type GetOffset(size_type chunk, uint16_t layer) const {
    return layer == 1 ? deque_[base_view_index(chunk)].base_view.offset
                      : deque_[view_index(chunk, layer)].view.offset;
  }
 
  constexpr size_type GetOffset(size_type chunk) const {
    return GetOffset(chunk, NumLayers());
  }
 
  constexpr size_type GetRelativeOffset(size_type chunk) const {
    uint16_t layer = NumLayers();
    if (layer == 1) {
      return GetOffset(chunk, layer);
    }
    return GetOffset(chunk, layer) - GetOffset(chunk, layer - 1);
  }
 
  constexpr size_type GetLength(size_type chunk) const {
    return entries_per_chunk_ == Entry::kMinEntriesPerChunk
               ? deque_[base_view_index(chunk)].base_view.length
               : deque_[top_view_index(chunk)].view.length;
  }
 
  constexpr ByteSpan GetView(size_type chunk) const {
    return ByteSpan(GetData(chunk) + GetOffset(chunk), GetLength(chunk));
  }
 
  std::pair<size_type, size_type> GetChunkAndOffset(const_iterator pos) const;
 
  [[nodiscard]] bool TryConvertToShared(size_type chunk);
 
  [[nodiscard]] bool TryReserveEntries(size_type num_entries,
                                       bool split = false);
 
  size_type InsertChunks(const_iterator pos, size_type num_chunks);
 
  size_type Insert(const_iterator pos,
                   ConstByteSpan bytes,
                   size_t offset,
                   size_t length);
 
  void SplitBase(size_type chunk, Deque& out_deque, size_type out_chunk);
 
  void SplitBefore(size_type chunk,
                   size_type split,
                   Deque& out_deque,
                   size_type out_chunk);
 
  void SplitBefore(size_type chunk, size_type split);
 
  void SplitAfter(size_type chunk,
                  size_type split,
                  Deque& out_deque,
                  size_type out_chunk);
 
  void SplitAfter(size_type chunk, size_type split);
 
  [[nodiscard]] bool TryReserveForRemove(const_iterator pos,
                                         size_t size,
                                         GenericMultiBuf* out);
 
  void MoveRange(const_iterator pos, size_t size, GenericMultiBuf& out);
 
  void ClearRange(const_iterator pos, size_t size);
 
  void EraseRange(const_iterator pos, size_t size);
 
  size_t CopyToImpl(ByteSpan dst, size_t offset, size_type start) const;
 
  [[nodiscard]] bool IsTopLayerSealed() const;
 
  void SetLayer(size_t offset, size_t length);
 
  // Describes the memory and views to that in a one-dimensional sequence.
  // Every `entries_per_chunk_`-th entry holds a pointer to memory, each entry
  // for a given offset less than `entries_per_chunk_` after that entry is a
  // view that is part of the same "layer" in the MultiBuf.
  //
  // This base type will always have 0 or 2 layers, but derived classes may add
  // more.
  //
  // For example, a MultiBuf that has had 3 `Chunk`s and two additional layers
  // added would have a `deque_` resembling the following:
  //
  //          buffer 0:         buffer 1:         buffer 2:
  // layer 3: deque_[0x3].view  deque_[0x7].view  deque_[0xB].view
  // layer 2: deque_[0x2].view  deque_[0x6].view  deque_[0xA].view
  // layer 1: deque_[0x1].view  deque_[0x5].view  deque_[0x9].view
  // layer 0: deque_[0x0].data  deque_[0x4].data  deque_[0x8].data
  Deque deque_;
 
  // Number of entries per chunk in this MultiBuf.
  size_type entries_per_chunk_ = Entry::kMinEntriesPerChunk;
 
  Observer* observer_ = nullptr;
};
 
template <typename MultiBufType>
class Instance {
 public:
  constexpr explicit Instance(Allocator& allocator) : base_(allocator) {}
 
  constexpr Instance(Instance&&) = default;
  constexpr Instance& operator=(Instance&&) = default;
 
  // Provide a more helpful compile-time error when a user tries to
  // copy-construct an interface type.
  template <Property... kProperties>
  constexpr Instance(const BasicMultiBuf<kProperties...>&)
      : base_(allocator::GetNullAllocator()) {
    MoveOnly<>();
  }
 
  // Provide a more helpful compile-time error when a user tries to copy-assign
  // an interface type.
  template <Property... kProperties>
  constexpr Instance& operator=(const BasicMultiBuf<kProperties...>&) {
    MoveOnly<>();
  }
 
  constexpr Instance(MultiBufType&& mb)
      : base_(std::move(static_cast<GenericMultiBuf&>(mb))) {}
 
  constexpr Instance& operator=(MultiBufType&& mb) {
    base_ = std::move(static_cast<GenericMultiBuf&>(mb));
    return *this;
  }
 
  template <Property... kProperties>
  constexpr Instance(BasicMultiBuf<kProperties...>&& mb)
      : base_(std::move(static_cast<internal::GenericMultiBuf&>(mb))) {
    internal::AssertIsConvertible<BasicMultiBuf<kProperties...>,
                                  MultiBufType>();
  }
 
  template <Property... kProperties>
  constexpr Instance& operator=(BasicMultiBuf<kProperties...>&& mb) {
    internal::AssertIsConvertible<BasicMultiBuf<kProperties...>,
                                  MultiBufType>();
    base_ = std::move(static_cast<internal::GenericMultiBuf&>(mb));
    return *this;
  }
 
  constexpr MultiBufType* operator->() { return &base_.as<MultiBufType>(); }
  constexpr const MultiBufType* operator->() const {
    return &base_.as<MultiBufType>();
  }
 
  constexpr MultiBufType& operator*() & { return base_.as<MultiBufType>(); }
  constexpr const MultiBufType& operator*() const& {
    return base_.as<MultiBufType>();
  }
 
  constexpr MultiBufType&& operator*() && {
    return std::move(base_.as<MultiBufType>());
  }
  constexpr const MultiBufType&& operator*() const&& {
    return std::move(base_.as<MultiBufType>());
  }
 
  constexpr operator MultiBufType&() & { return base_.as<MultiBufType>(); }
  constexpr operator const MultiBufType&() const& {
    return base_.as<MultiBufType>();
  }
 
  constexpr operator MultiBufType&&() && {
    return std::move(base_.as<MultiBufType>());
  }
  constexpr operator const MultiBufType&&() const&& {
    return std::move(base_.as<MultiBufType>());
  }
 
 private:
  // Helper functions to provide a more helpful compile-time error when a this
  // type is used incorrectly.
  template <bool kMoveOnly = false>
  static constexpr void MoveOnly() {
    static_assert(kMoveOnly,
                  "Instances can only be created from existing MultiBufs using "
                  "move-construction or move-assignment.");
  }
 
  GenericMultiBuf base_;
};
 
}  // namespace multibuf::internal
 
// Template method implementations.
 
template <multibuf::Property... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(const_iterator pos) {
  return generic().TryReserveForInsert(pos);
}
 
template <multibuf::Property... kProperties>
template <multibuf::Property... kOtherProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const BasicMultiBuf<kOtherProperties...>& mb) {
  multibuf::internal::AssertIsConvertible<BasicMultiBuf<kOtherProperties...>,
                                          BasicMultiBuf>();
  return generic().TryReserveForInsert(pos,
                                       static_cast<const GenericMultiBuf&>(mb));
}
 
template <multibuf::Property... kProperties>
template <multibuf::Property... kOtherProperties>
void BasicMultiBuf<kProperties...>::Insert(
    const_iterator pos, BasicMultiBuf<kOtherProperties...>&& mb) {
  multibuf::internal::AssertIsConvertible<BasicMultiBuf<kOtherProperties...>,
                                          BasicMultiBuf>();
  generic().Insert(pos, std::move(mb.generic()));
}
 
template <multibuf::Property... kProperties>
template <int&... kExplicitGuard, typename T, typename>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos, const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  generic().Insert(pos, bytes);
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           UniquePtr<std::byte[]>&& bytes,
                                           size_t offset,
                                           size_t length) {
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.deallocator());
  bytes.Release();
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           UniquePtr<const std::byte[]>&& bytes,
                                           size_t offset,
                                           size_t length) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.deallocator());
  bytes.Release();
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           const SharedPtr<std::byte[]>& bytes,
                                           size_t offset,
                                           size_t length) {
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.control_block());
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::Insert(
    const_iterator pos,
    const SharedPtr<const std::byte[]>& bytes,
    size_t offset,
    size_t length) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.control_block());
}
 
template <multibuf::Property... kProperties>
template <multibuf::Property... kOtherProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const BasicMultiBuf<kOtherProperties...>& mb) {
  return generic().TryReserveForInsert(end(),
                                       static_cast<const GenericMultiBuf&>(mb));
}
 
template <multibuf::Property... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack() {
  return generic().TryReserveForInsert(end());
}
 
template <multibuf::Property... kProperties>
template <multibuf::Property... kOtherProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    BasicMultiBuf<kOtherProperties...>&& mb) {
  Insert(end(), std::move(mb));
}
 
template <multibuf::Property... kProperties>
template <int&... kExplicitGuard, typename T, typename>
void BasicMultiBuf<kProperties...>::PushBack(const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), bytes);
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(UniquePtr<std::byte[]>&& bytes,
                                             size_t offset,
                                             size_t length) {
  Insert(end(), std::move(bytes), offset, length);
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    UniquePtr<const std::byte[]>&& bytes, size_t offset, size_t length) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), std::move(bytes), offset, length);
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    const SharedPtr<std::byte[]>& bytes, size_t offset, size_t length) {
  Insert(end(), bytes, offset, length);
}
 
template <multibuf::Property... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    const SharedPtr<const std::byte[]>& bytes, size_t offset, size_t length) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), bytes, offset, length);
}
 
template <multibuf::Property... kProperties>
Result<multibuf::internal::Instance<BasicMultiBuf<kProperties...>>>
BasicMultiBuf<kProperties...>::Remove(const_iterator pos, size_t size) {
  auto result = generic().Remove(pos, size);
  if (!result.ok()) {
    return result.status();
  }
  return Instance(std::move(*result));
}
 
template <multibuf::Property... kProperties>
Result<multibuf::internal::Instance<BasicMultiBuf<kProperties...>>>
BasicMultiBuf<kProperties...>::PopFrontFragment() {
  auto result = generic().PopFrontFragment();
  if (!result.ok()) {
    return result.status();
  }
  return Instance(std::move(*result));
}
 
template <multibuf::Property... kProperties>
UniquePtr<typename BasicMultiBuf<kProperties...>::value_type[]>
BasicMultiBuf<kProperties...>::Release(const_iterator pos) {
  UniquePtr<std::byte[]> bytes = generic().Release(pos);
  if constexpr (is_const()) {
    UniquePtr<const std::byte[]> const_bytes(
        bytes.get(), bytes.size(), *(bytes.deallocator()));
    bytes.Release();
    return const_bytes;
  } else {
    return bytes;
  }
}
 
template <multibuf::Property... kProperties>
SharedPtr<typename BasicMultiBuf<kProperties...>::value_type[]>
BasicMultiBuf<kProperties...>::Share(const_iterator pos) {
  return SharedPtr<value_type[]>(generic().Share(pos));
}
 
}  // namespace pw