layout.h

// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

// This file is NOT intended for use by clients, except in generated code.
//
// This file defines low-level, non-type-safe classes for traversing the Cap'n Proto memory layout
// (which is also its wire format).  Code generated by the Cap'n Proto compiler uses these classes,
// as does other parts of the Cap'n proto library which provide a higher-level interface for
// dynamic introspection.

#ifndef CAPNP_LAYOUT_H_
#define CAPNP_LAYOUT_H_

#include <kj/common.h>
#include <kj/memory.h>
#include "common.h"
#include "blob.h"
#include "endian.h"

#if __mips__ && !defined(CAPNP_CANONICALIZE_NAN)
#define CAPNP_CANONICALIZE_NAN 1
// Explicitly detect NaNs and canonicalize them to the quiet NaN value as would be returned by
// __builtin_nan("") on systems implementing the IEEE-754 recommended (but not required) NaN
// signalling/quiet differentiation (such as x86).  Unfortunately, some architectures -- in
// particular, MIPS -- represent quiet vs. signalling nans differently than the rest of the world.
// Canonicalizing them makes output consistent (which is important!), but hurts performance
// slightly.
//
// Note that trying to convert MIPS NaNs to standard NaNs without losing data doesn't work.
// Signaling vs. quiet is indicated by a bit, with the meaning being the opposite on MIPS vs.
// everyone else.  It would be great if we could just flip that bit, but we can't, because if the
// significand is all-zero, then the value is infinity rather than NaN.  This means that on most
// machines, where the bit indicates quietness, there is one more quiet NaN value than signalling
// NaN value, whereas on MIPS there is one more sNaN than qNaN, and thus there is no isomorphic
// mapping that properly preserves quietness.  Instead of doing something hacky, we just give up
// and blow away NaN payloads, because no one uses them anyway.
#endif

namespace capnp {

class ClientHook;

namespace _ {  // private

class PointerBuilder;
class PointerReader;
class StructBuilder;
class StructReader;
class ListBuilder;
class ListReader;
class OrphanBuilder;
struct WirePointer;
struct WireHelpers;
class SegmentReader;
class SegmentBuilder;
class Arena;
class BuilderArena;

// =============================================================================

enum class FieldSize: uint8_t {
  // TODO(cleanup):  Rename to FieldLayout or maybe ValueLayout.

  // Notice that each member of this enum, when representing a list element size, represents a
  // size that is greater than or equal to the previous members, since INLINE_COMPOSITE is used
  // only for multi-word structs.  This is important because it allows us to compare FieldSize
  // values for the purpose of deciding when we need to upgrade a list.

  VOID = 0,
  BIT = 1,
  BYTE = 2,
  TWO_BYTES = 3,
  FOUR_BYTES = 4,
  EIGHT_BYTES = 5,

  POINTER = 6,  // Indicates that the field lives in the pointer section, not the data section.

  INLINE_COMPOSITE = 7
  // A composite type of fixed width.  This serves two purposes:
  // 1) For lists of composite types where all the elements would have the exact same width,
  //    allocating a list of pointers which in turn point at the elements would waste space.  We
  //    can avoid a layer of indirection by placing all the elements in a flat sequence, and only
  //    indicating the element properties (e.g. field count for structs) once.
  //
  //    Specifically, a list pointer indicating INLINE_COMPOSITE element size actually points to
  //    a "tag" describing one element.  This tag is formatted like a wire pointer, but the
  //    "offset" instead stores the element count of the list.  The flat list of elements appears
  //    immediately after the tag.  In the list pointer itself, the element count is replaced with
  //    a word count for the whole list (excluding tag).  This allows the tag and elements to be
  //    precached in a single step rather than two sequential steps.
  //
  //    It is NOT intended to be possible to substitute an INLINE_COMPOSITE list for a POINTER
  //    list or vice-versa without breaking recipients.  Recipients expect one or the other
  //    depending on the message definition.
  //
  //    However, it IS allowed to substitute an INLINE_COMPOSITE list -- specifically, of structs --
  //    when a list was expected, or vice versa, with the assumption that the first field of the
  //    struct (field number zero) correspond to the element type.  This allows a list of
  //    primitives to be upgraded to a list of structs, avoiding the need to use parallel arrays
  //    when you realize that you need to attach some extra information to each element of some
  //    primitive list.
  //
  // 2) At one point there was a notion of "inline" struct fields, but it was deemed too much of
  //    an implementation burden for too little gain, and so was deleted.
};

typedef decltype(BITS / ELEMENTS) BitsPerElement;
typedef decltype(POINTERS / ELEMENTS) PointersPerElement;

static constexpr BitsPerElement BITS_PER_ELEMENT_TABLE[8] = {
    0 * BITS / ELEMENTS,
    1 * BITS / ELEMENTS,
    8 * BITS / ELEMENTS,
    16 * BITS / ELEMENTS,
    32 * BITS / ELEMENTS,
    64 * BITS / ELEMENTS,
    0 * BITS / ELEMENTS,
    0 * BITS / ELEMENTS
};

inline constexpr BitsPerElement dataBitsPerElement(FieldSize size) {
  return _::BITS_PER_ELEMENT_TABLE[static_cast<int>(size)];
}

inline constexpr PointersPerElement pointersPerElement(FieldSize size) {
  return size == FieldSize::POINTER ? 1 * POINTERS / ELEMENTS : 0 * POINTERS / ELEMENTS;
}

template <size_t size> struct ElementSizeForByteSize;
template <> struct ElementSizeForByteSize<1> { static constexpr FieldSize value = FieldSize::BYTE; };
template <> struct ElementSizeForByteSize<2> { static constexpr FieldSize value = FieldSize::TWO_BYTES; };
template <> struct ElementSizeForByteSize<4> { static constexpr FieldSize value = FieldSize::FOUR_BYTES; };
template <> struct ElementSizeForByteSize<8> { static constexpr FieldSize value = FieldSize::EIGHT_BYTES; };

template <typename T> struct ElementSizeForType {
  static constexpr FieldSize value =
      // Primitive types that aren't special-cased below can be determined from sizeof().
      kind<T>() == Kind::PRIMITIVE ? ElementSizeForByteSize<sizeof(T)>::value :
      kind<T>() == Kind::ENUM ? FieldSize::TWO_BYTES :
      kind<T>() == Kind::STRUCT ? FieldSize::INLINE_COMPOSITE :

      // Everything else is a pointer.
      FieldSize::POINTER;
};

// Void and bool are special.
template <> struct ElementSizeForType<Void> { static constexpr FieldSize value = FieldSize::VOID; };
template <> struct ElementSizeForType<bool> { static constexpr FieldSize value = FieldSize::BIT; };

// Lists and blobs are pointers, not structs.
template <typename T, bool b> struct ElementSizeForType<List<T, b>> {
  static constexpr FieldSize value = FieldSize::POINTER;
};
template <> struct ElementSizeForType<Text> {
  static constexpr FieldSize value = FieldSize::POINTER;
};
template <> struct ElementSizeForType<Data> {
  static constexpr FieldSize value = FieldSize::POINTER;
};

template <typename T>
inline constexpr FieldSize elementSizeForType() {
  return ElementSizeForType<T>::value;
}

struct MessageSizeCounts {
  WordCount64 wordCount;
  uint capCount;

  MessageSizeCounts& operator+=(const MessageSizeCounts& other) {
    wordCount += other.wordCount;
    capCount += other.capCount;
    return *this;
  }

  MessageSize asPublic() {
    return MessageSize { wordCount / WORDS, capCount };
  }
};

// =============================================================================

template <int wordCount>
union AlignedData {
  // Useful for declaring static constant data blobs as an array of bytes, but forcing those
  // bytes to be word-aligned.

  uint8_t bytes[wordCount * sizeof(word)];
  word words[wordCount];
};

struct StructSize {
  WordCount16 data;
  WirePointerCount16 pointers;

  FieldSize preferredListEncoding;
  // Preferred size to use when encoding a list of this struct.  This is INLINE_COMPOSITE if and
  // only if the struct is larger than one word; otherwise the struct list can be encoded more
  // efficiently by encoding it as if it were some primitive type.

  inline constexpr WordCount total() const { return data + pointers * WORDS_PER_POINTER; }

  StructSize() = default;
  inline constexpr StructSize(WordCount data, WirePointerCount pointers,
                              FieldSize preferredListEncoding)
      : data(data), pointers(pointers), preferredListEncoding(preferredListEncoding) {}
};

template <typename T> struct StructSize_;
// Specialized for every struct type with member:  static constexpr StructSize value"

template <typename T, typename = typename StructSize_<T>::Exists>
inline constexpr StructSize structSize() {
  return StructSize_<T>::value;
}
template <typename T, typename CapnpPrivate = typename T::_capnpPrivate, bool = false>
inline constexpr StructSize structSize() {
  return CapnpPrivate::structSize;
}

// -------------------------------------------------------------------
// Masking of default values

template <typename T, Kind kind = kind<T>()> struct Mask_;
template <typename T> struct Mask_<T, Kind::PRIMITIVE> { typedef T Type; };
template <typename T> struct Mask_<T, Kind::ENUM> { typedef uint16_t Type; };
template <> struct Mask_<float, Kind::PRIMITIVE> { typedef uint32_t Type; };
template <> struct Mask_<double, Kind::PRIMITIVE> { typedef uint64_t Type; };

template <typename T> struct Mask_<T, Kind::OTHER> {
  // Union discriminants end up here.
  static_assert(sizeof(T) == 2, "Don't know how to mask this type.");
  typedef uint16_t Type;
};

template <typename T>
using Mask = typename Mask_<T>::Type;

template <typename T>
KJ_ALWAYS_INLINE(Mask<T> mask(T value, Mask<T> mask));
template <typename T>
KJ_ALWAYS_INLINE(T unmask(Mask<T> value, Mask<T> mask));

template <typename T>
inline Mask<T> mask(T value, Mask<T> mask) {
  return static_cast<Mask<T> >(value) ^ mask;
}

template <>
inline uint32_t mask<float>(float value, uint32_t mask) {
#if CAPNP_CANONICALIZE_NAN
  if (value != value) {
    return 0x7fc00000u ^ mask;
  }
#endif

  uint32_t i;
  static_assert(sizeof(i) == sizeof(value), "float is not 32 bits?");
  memcpy(&i, &value, sizeof(value));
  return i ^ mask;
}

template <>
inline uint64_t mask<double>(double value, uint64_t mask) {
#if CAPNP_CANONICALIZE_NAN
  if (value != value) {
    return 0x7ff8000000000000ull ^ mask;
  }
#endif

  uint64_t i;
  static_assert(sizeof(i) == sizeof(value), "double is not 64 bits?");
  memcpy(&i, &value, sizeof(value));
  return i ^ mask;
}

template <typename T>
inline T unmask(Mask<T> value, Mask<T> mask) {
  return static_cast<T>(value ^ mask);
}

template <>
inline float unmask<float>(uint32_t value, uint32_t mask) {
  value ^= mask;
  float result;
  static_assert(sizeof(result) == sizeof(value), "float is not 32 bits?");
  memcpy(&result, &value, sizeof(value));
  return result;
}

template <>
inline double unmask<double>(uint64_t value, uint64_t mask) {
  value ^= mask;
  double result;
  static_assert(sizeof(result) == sizeof(value), "double is not 64 bits?");
  memcpy(&result, &value, sizeof(value));
  return result;
}

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

class PointerBuilder: public kj::DisallowConstCopy {
  // Represents a single pointer, usually embedded in a struct or a list.

public:
  inline PointerBuilder(): segment(nullptr), pointer(nullptr) {}

  static inline PointerBuilder getRoot(SegmentBuilder* segment, word* location);
  // Get a PointerBuilder representing a message root located in the given segment at the given
  // location.

  bool isNull();

  StructBuilder getStruct(StructSize size, const word* defaultValue);
  ListBuilder getList(FieldSize elementSize, const word* defaultValue);
  ListBuilder getStructList(StructSize elementSize, const word* defaultValue);
  template <typename T> typename T::Builder getBlob(const void* defaultValue,ByteCount defaultSize);
  kj::Own<ClientHook> getCapability();
  // Get methods:  Get the value.  If it is null, initialize it to a copy of the default value.
  // The default value is encoded as an "unchecked message" for structs, lists, and objects, or a
  // simple byte array for blobs.

  StructBuilder initStruct(StructSize size);
  ListBuilder initList(FieldSize elementSize, ElementCount elementCount);
  ListBuilder initStructList(ElementCount elementCount, StructSize size);
  template <typename T> typename T::Builder initBlob(ByteCount size);
  // Init methods:  Initialize the pointer to a newly-allocated object, discarding the existing
  // object.

  void setStruct(const StructReader& value);
  void setList(const ListReader& value);
  template <typename T> void setBlob(typename T::Reader value);
  void setCapability(kj::Own<ClientHook>&& cap);
  // Set methods:  Initialize the pointer to a newly-allocated copy of the given value, discarding
  // the existing object.

  void adopt(OrphanBuilder&& orphan);
  // Set the pointer to point at the given orphaned value.

  OrphanBuilder disown();
  // Set the pointer to null and return its previous value as an orphan.

  void clear();
  // Clear the pointer to null, discarding its previous value.

  void transferFrom(PointerBuilder other);
  // Equivalent to `adopt(other.disown())`.

  void copyFrom(PointerReader other);
  // Equivalent to `set(other.get())`.

  PointerReader asReader() const;

  BuilderArena* getArena() const;
  // Get the arena containing this pointer.

private:
  SegmentBuilder* segment;     // Memory segment in which the pointer resides.
  WirePointer* pointer;        // Pointer to the pointer.

  inline PointerBuilder(SegmentBuilder* segment, WirePointer* pointer)
      : segment(segment), pointer(pointer) {}

  friend class StructBuilder;
  friend class ListBuilder;
};

class PointerReader {
public:
  inline PointerReader(): segment(nullptr), pointer(nullptr), nestingLimit(0x7fffffff) {}

  static PointerReader getRoot(SegmentReader* segment, const word* location, int nestingLimit);
  // Get a PointerReader representing a message root located in the given segment at the given
  // location.

  static inline PointerReader getRootUnchecked(const word* location);
  // Get a PointerReader for an unchecked message.

  MessageSizeCounts targetSize() const;
  // Return the total size of the target object and everything to which it points.  Does not count
  // far pointer overhead.  This is useful for deciding how much space is needed to copy the object
  // into a flat array.  However, the caller is advised NOT to treat this value as secure.  Instead,
  // use the result as a hint for allocating the first segment, do the copy, and then throw an
  // exception if it overruns.

  bool isNull() const;

  StructReader getStruct(const word* defaultValue) const;
  ListReader getList(FieldSize expectedElementSize, const word* defaultValue) const;
  template <typename T>
  typename T::Reader getBlob(const void* defaultValue, ByteCount defaultSize) const;
  kj::Own<ClientHook> getCapability() const;
  // Get methods:  Get the value.  If it is null, return the default value instead.
  // The default value is encoded as an "unchecked message" for structs, lists, and objects, or a
  // simple byte array for blobs.

  const word* getUnchecked() const;
  // If this is an unchecked message, get a word* pointing at the location of the pointer.  This
  // word* can actually be passed to readUnchecked() to read the designated sub-object later.  If
  // this isn't an unchecked message, throws an exception.

  kj::Maybe<Arena&> getArena() const;
  // Get the arena containing this pointer.

private:
  SegmentReader* segment;      // Memory segment in which the pointer resides.
  const WirePointer* pointer;  // Pointer to the pointer.  null = treat as null pointer.

  int nestingLimit;
  // Limits the depth of message structures to guard against stack-overflow-based DoS attacks.
  // Once this reaches zero, further pointers will be pruned.

  inline PointerReader(SegmentReader* segment, const WirePointer* pointer, int nestingLimit)
      : segment(segment), pointer(pointer), nestingLimit(nestingLimit) {}

  friend class StructReader;
  friend class ListReader;
  friend class PointerBuilder;
  friend class OrphanBuilder;
};

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

class StructBuilder: public kj::DisallowConstCopy {
public:
  inline StructBuilder(): segment(nullptr), data(nullptr), pointers(nullptr), bit0Offset(0) {}

  inline word* getLocation() { return reinterpret_cast<word*>(data); }
  // Get the object's location.  Only valid for independently-allocated objects (i.e. not list
  // elements).

  inline BitCount getDataSectionSize() const { return dataSize; }
  inline WirePointerCount getPointerSectionSize() const { return pointerCount; }
  inline Data::Builder getDataSectionAsBlob();

  template <typename T>
  KJ_ALWAYS_INLINE(bool hasDataField(ElementCount offset));
  // Return true if the field is set to something other than its default value.

  template <typename T>
  KJ_ALWAYS_INLINE(T getDataField(ElementCount offset));
  // Gets the data field value of the given type at the given offset.  The offset is measured in
  // multiples of the field size, determined by the type.

  template <typename T>
  KJ_ALWAYS_INLINE(T getDataField(ElementCount offset, Mask<T> mask));
  // Like getDataField() but applies the given XOR mask to the data on load.  Used for reading
  // fields with non-zero default values.

  template <typename T>
  KJ_ALWAYS_INLINE(void setDataField(
      ElementCount offset, kj::NoInfer<T> value));
  // Sets the data field value at the given offset.

  template <typename T>
  KJ_ALWAYS_INLINE(void setDataField(
      ElementCount offset, kj::NoInfer<T> value, Mask<T> mask));
  // Like setDataField() but applies the given XOR mask before storing.  Used for writing fields
  // with non-zero default values.

  KJ_ALWAYS_INLINE(PointerBuilder getPointerField(WirePointerCount ptrIndex));
  // Get a builder for a pointer field given the index within the pointer section.

  void clearAll();
  // Clear all pointers and data.

  void transferContentFrom(StructBuilder other);
  // Adopt all pointers from `other`, and also copy all data.  If `other`'s sections are larger
  // than this, the extra data is not transferred, meaning there is a risk of data loss when
  // transferring from messages built with future versions of the protocol.

  void copyContentFrom(StructReader other);
  // Copy content from `other`.  If `other`'s sections are larger than this, the extra data is not
  // copied, meaning there is a risk of data loss when copying from messages built with future
  // versions of the protocol.

  StructReader asReader() const;
  // Gets a StructReader pointing at the same memory.

  BuilderArena* getArena();
  // Gets the arena in which this object is allocated.

private:
  SegmentBuilder* segment;     // Memory segment in which the struct resides.
  void* data;                  // Pointer to the encoded data.
  WirePointer* pointers;   // Pointer to the encoded pointers.

  BitCount32 dataSize;
  // Size of data section.  We use a bit count rather than a word count to more easily handle the
  // case of struct lists encoded with less than a word per element.

  WirePointerCount16 pointerCount;  // Size of the pointer section.

  BitCount8 bit0Offset;
  // A special hack:  If dataSize == 1 bit, then bit0Offset is the offset of that bit within the
  // byte pointed to by `data`.  In all other cases, this is zero.  This is needed to implement
  // struct lists where each struct is one bit.

  inline StructBuilder(SegmentBuilder* segment, void* data, WirePointer* pointers,
                       BitCount dataSize, WirePointerCount pointerCount, BitCount8 bit0Offset)
      : segment(segment), data(data), pointers(pointers),
        dataSize(dataSize), pointerCount(pointerCount), bit0Offset(bit0Offset) {}

  friend class ListBuilder;
  friend struct WireHelpers;
  friend class OrphanBuilder;
};

class StructReader {
public:
  inline StructReader()
      : segment(nullptr), data(nullptr), pointers(nullptr), dataSize(0),
        pointerCount(0), bit0Offset(0), nestingLimit(0x7fffffff) {}

  const void* getLocation() const { return data; }

  inline BitCount getDataSectionSize() const { return dataSize; }
  inline WirePointerCount getPointerSectionSize() const { return pointerCount; }
  inline Data::Reader getDataSectionAsBlob();

  template <typename T>
  KJ_ALWAYS_INLINE(bool hasDataField(ElementCount offset) const);
  // Return true if the field is set to something other than its default value.

  template <typename T>
  KJ_ALWAYS_INLINE(T getDataField(ElementCount offset) const);
  // Get the data field value of the given type at the given offset.  The offset is measured in
  // multiples of the field size, determined by the type.  Returns zero if the offset is past the
  // end of the struct's data section.

  template <typename T>
  KJ_ALWAYS_INLINE(
      T getDataField(ElementCount offset, Mask<T> mask) const);
  // Like getDataField(offset), but applies the given XOR mask to the result.  Used for reading
  // fields with non-zero default values.

  KJ_ALWAYS_INLINE(PointerReader getPointerField(WirePointerCount ptrIndex) const);
  // Get a reader for a pointer field given the index within the pointer section.  If the index
  // is out-of-bounds, returns a null pointer.

  MessageSizeCounts totalSize() const;
  // Return the total size of the struct and everything to which it points.  Does not count far
  // pointer overhead.  This is useful for deciding how much space is needed to copy the struct
  // into a flat array.  However, the caller is advised NOT to treat this value as secure.  Instead,
  // use the result as a hint for allocating the first segment, do the copy, and then throw an
  // exception if it overruns.

private:
  SegmentReader* segment;  // Memory segment in which the struct resides.

  const void* data;
  const WirePointer* pointers;

  BitCount32 dataSize;
  // Size of data section.  We use a bit count rather than a word count to more easily handle the
  // case of struct lists encoded with less than a word per element.

  WirePointerCount16 pointerCount;  // Size of the pointer section.

  BitCount8 bit0Offset;
  // A special hack:  If dataSize == 1 bit, then bit0Offset is the offset of that bit within the
  // byte pointed to by `data`.  In all other cases, this is zero.  This is needed to implement
  // struct lists where each struct is one bit.
  //
  // TODO(someday):  Consider packing this together with dataSize, since we have 10 extra bits
  //   there doing nothing -- or arguably 12 bits, if you consider that 2-bit and 4-bit sizes
  //   aren't allowed.  Consider that we could have a method like getDataSizeIn<T>() which is
  //   specialized to perform the correct shifts for each size.

  int nestingLimit;
  // Limits the depth of message structures to guard against stack-overflow-based DoS attacks.
  // Once this reaches zero, further pointers will be pruned.
  // TODO(perf):  Limit to 8 bits for better alignment?

  inline StructReader(SegmentReader* segment, const void* data, const WirePointer* pointers,
                      BitCount dataSize, WirePointerCount pointerCount, BitCount8 bit0Offset,
                      int nestingLimit)
      : segment(segment), data(data), pointers(pointers),
        dataSize(dataSize), pointerCount(pointerCount), bit0Offset(bit0Offset),
        nestingLimit(nestingLimit) {}

  friend class ListReader;
  friend class StructBuilder;
  friend struct WireHelpers;
};

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

class ListBuilder: public kj::DisallowConstCopy {
public:
  inline ListBuilder()
      : segment(nullptr), ptr(nullptr), elementCount(0 * ELEMENTS),
        step(0 * BITS / ELEMENTS) {}

  inline word* getLocation() {
    // Get the object's location.  Only valid for independently-allocated objects (i.e. not list
    // elements).

    if (step * ELEMENTS <= BITS_PER_WORD * WORDS) {
      return reinterpret_cast<word*>(ptr);
    } else {
      return reinterpret_cast<word*>(ptr) - POINTER_SIZE_IN_WORDS;
    }
  }

  inline ElementCount size() const;
  // The number of elements in the list.

  Text::Builder asText();
  Data::Builder asData();
  // Reinterpret the list as a blob.  Throws an exception if the elements are not byte-sized.

  template <typename T>
  KJ_ALWAYS_INLINE(T getDataElement(ElementCount index));
  // Get the element of the given type at the given index.

  template <typename T>
  KJ_ALWAYS_INLINE(void setDataElement(
      ElementCount index, kj::NoInfer<T> value));
  // Set the element at the given index.

  KJ_ALWAYS_INLINE(PointerBuilder getPointerElement(ElementCount index));

  StructBuilder getStructElement(ElementCount index);

  ListReader asReader() const;
  // Get a ListReader pointing at the same memory.

  BuilderArena* getArena();
  // Gets the arena in which this object is allocated.

private:
  SegmentBuilder* segment;  // Memory segment in which the list resides.

  byte* ptr;  // Pointer to list content.

  ElementCount elementCount;  // Number of elements in the list.

  decltype(BITS / ELEMENTS) step;
  // The distance between elements.

  BitCount32 structDataSize;
  WirePointerCount16 structPointerCount;
  // The struct properties to use when interpreting the elements as structs.  All lists can be
  // interpreted as struct lists, so these are always filled in.

  inline ListBuilder(SegmentBuilder* segment, void* ptr,
                     decltype(BITS / ELEMENTS) step, ElementCount size,
                     BitCount structDataSize, WirePointerCount structPointerCount)
      : segment(segment), ptr(reinterpret_cast<byte*>(ptr)),
        elementCount(size), step(step), structDataSize(structDataSize),
        structPointerCount(structPointerCount) {}

  friend class StructBuilder;
  friend struct WireHelpers;
  friend class OrphanBuilder;
};

class ListReader {
public:
  inline ListReader()
      : segment(nullptr), ptr(nullptr), elementCount(0), step(0 * BITS / ELEMENTS),
        structDataSize(0), structPointerCount(0), nestingLimit(0x7fffffff) {}

  inline ElementCount size() const;
  // The number of elements in the list.

  Text::Reader asText();
  Data::Reader asData();
  // Reinterpret the list as a blob.  Throws an exception if the elements are not byte-sized.

  template <typename T>
  KJ_ALWAYS_INLINE(T getDataElement(ElementCount index) const);
  // Get the element of the given type at the given index.

  KJ_ALWAYS_INLINE(PointerReader getPointerElement(ElementCount index) const);

  StructReader getStructElement(ElementCount index) const;

private:
  SegmentReader* segment;  // Memory segment in which the list resides.

  const byte* ptr;  // Pointer to list content.

  ElementCount elementCount;  // Number of elements in the list.

  decltype(BITS / ELEMENTS) step;
  // The distance between elements.

  BitCount32 structDataSize;
  WirePointerCount16 structPointerCount;
  // The struct properties to use when interpreting the elements as structs.  All lists can be
  // interpreted as struct lists, so these are always filled in.

  int nestingLimit;
  // Limits the depth of message structures to guard against stack-overflow-based DoS attacks.
  // Once this reaches zero, further pointers will be pruned.

  inline ListReader(SegmentReader* segment, const void* ptr,
                    ElementCount elementCount, decltype(BITS / ELEMENTS) step,
                    BitCount structDataSize, WirePointerCount structPointerCount,
                    int nestingLimit)
      : segment(segment), ptr(reinterpret_cast<const byte*>(ptr)), elementCount(elementCount),
        step(step), structDataSize(structDataSize),
        structPointerCount(structPointerCount), nestingLimit(nestingLimit) {}

  friend class StructReader;
  friend class ListBuilder;
  friend struct WireHelpers;
  friend class OrphanBuilder;
};

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

class OrphanBuilder {
public:
  inline OrphanBuilder(): segment(nullptr), location(nullptr) { memset(&tag, 0, sizeof(tag)); }
  OrphanBuilder(const OrphanBuilder& other) = delete;
  inline OrphanBuilder(OrphanBuilder&& other) noexcept;
  inline ~OrphanBuilder() noexcept(false);

  static OrphanBuilder initStruct(BuilderArena* arena, StructSize size);
  static OrphanBuilder initList(BuilderArena* arena, ElementCount elementCount,
                                FieldSize elementSize);
  static OrphanBuilder initStructList(BuilderArena* arena, ElementCount elementCount,
                                      StructSize elementSize);
  static OrphanBuilder initText(BuilderArena* arena, ByteCount size);
  static OrphanBuilder initData(BuilderArena* arena, ByteCount size);

  static OrphanBuilder copy(BuilderArena* arena, StructReader copyFrom);
  static OrphanBuilder copy(BuilderArena* arena, ListReader copyFrom);
  static OrphanBuilder copy(BuilderArena* arena, PointerReader copyFrom);
  static OrphanBuilder copy(BuilderArena* arena, Text::Reader copyFrom);
  static OrphanBuilder copy(BuilderArena* arena, Data::Reader copyFrom);
  static OrphanBuilder copy(BuilderArena* arena, kj::Own<ClientHook> copyFrom);

  static OrphanBuilder referenceExternalData(BuilderArena* arena, Data::Reader data);

  OrphanBuilder& operator=(const OrphanBuilder& other) = delete;
  inline OrphanBuilder& operator=(OrphanBuilder&& other);

  inline bool operator==(decltype(nullptr)) const { return location == nullptr; }
  inline bool operator!=(decltype(nullptr)) const { return location != nullptr; }

  StructBuilder asStruct(StructSize size);
  // Interpret as a struct, or throw an exception if not a struct.

  ListBuilder asList(FieldSize elementSize);
  // Interpret as a list, or throw an exception if not a list.  elementSize cannot be
  // INLINE_COMPOSITE -- use asStructList() instead.

  ListBuilder asStructList(StructSize elementSize);
  // Interpret as a struct list, or throw an exception if not a list.

  Text::Builder asText();
  Data::Builder asData();
  // Interpret as a blob, or throw an exception if not a blob.

  StructReader asStructReader(StructSize size) const;
  ListReader asListReader(FieldSize elementSize) const;
  kj::Own<ClientHook> asCapability() const;
  Text::Reader asTextReader() const;
  Data::Reader asDataReader() const;

  void truncate(ElementCount size, bool isText);

private:
  static_assert(1 * POINTERS * WORDS_PER_POINTER == 1 * WORDS,
                "This struct assumes a pointer is one word.");
  word tag;
  // Contains an encoded WirePointer representing this object.  WirePointer is defined in
  // layout.c++, but fits in a word.
  //
  // This may be a FAR pointer.  Even in that case, `location` points to the eventual destination
  // of that far pointer.  The reason we keep the far pointer around rather than just making `tag`
  // represent the final destination is because if the eventual adopter of the pointer is not in
  // the target's segment then it may be useful to reuse the far pointer landing pad.
  //
  // If `tag` is not a far pointer, its offset is garbage; only `location` points to the actual
  // target.

  SegmentBuilder* segment;
  // Segment in which the object resides.

  word* location;
  // Pointer to the object, or nullptr if the pointer is null.  For capabilities, we make this
  // point at `tag` just so that it is non-null for operator==, but it is never used.

  inline OrphanBuilder(const void* tagPtr, SegmentBuilder* segment, word* location)
      : segment(segment), location(location) {
    memcpy(&tag, tagPtr, sizeof(tag));
  }

  inline WirePointer* tagAsPtr() { return reinterpret_cast<WirePointer*>(&tag); }
  inline const WirePointer* tagAsPtr() const { return reinterpret_cast<const WirePointer*>(&tag); }

  void euthanize();
  // Erase the target object, zeroing it out and possibly reclaiming the memory.  Called when
  // the OrphanBuilder is being destroyed or overwritten and it is non-null.

  friend struct WireHelpers;
};

// =======================================================================================
// Internal implementation details...

// These are defined in the source file.
template <> typename Text::Builder PointerBuilder::initBlob<Text>(ByteCount size);
template <> void PointerBuilder::setBlob<Text>(typename Text::Reader value);
template <> typename Text::Builder PointerBuilder::getBlob<Text>(const void* defaultValue, ByteCount defaultSize);
template <> typename Text::Reader PointerReader::getBlob<Text>(const void* defaultValue, ByteCount defaultSize) const;

template <> typename Data::Builder PointerBuilder::initBlob<Data>(ByteCount size);
template <> void PointerBuilder::setBlob<Data>(typename Data::Reader value);
template <> typename Data::Builder PointerBuilder::getBlob<Data>(const void* defaultValue, ByteCount defaultSize);
template <> typename Data::Reader PointerReader::getBlob<Data>(const void* defaultValue, ByteCount defaultSize) const;

inline PointerBuilder PointerBuilder::getRoot(SegmentBuilder* segment, word* location) {
  return PointerBuilder(segment, reinterpret_cast<WirePointer*>(location));
}

inline PointerReader PointerReader::getRootUnchecked(const word* location) {
  return PointerReader(nullptr, reinterpret_cast<const WirePointer*>(location), 0x7fffffff);
}

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

inline Data::Builder StructBuilder::getDataSectionAsBlob() {
  return Data::Builder(reinterpret_cast<byte*>(data), dataSize / BITS_PER_BYTE / BYTES);
}

template <typename T>
inline bool StructBuilder::hasDataField(ElementCount offset) {
  return getDataField<Mask<T>>(offset) != 0;
}

template <>
inline bool StructBuilder::hasDataField<Void>(ElementCount offset) {
  return false;
}

template <typename T>
inline T StructBuilder::getDataField(ElementCount offset) {
  return reinterpret_cast<WireValue<T>*>(data)[offset / ELEMENTS].get();
}

template <>
inline bool StructBuilder::getDataField<bool>(ElementCount offset) {
  // This branch should be compiled out whenever this is inlined with a constant offset.
  BitCount boffset = (offset == 0 * ELEMENTS) ?
      BitCount(bit0Offset) : offset * (1 * BITS / ELEMENTS);
  byte* b = reinterpret_cast<byte*>(data) + boffset / BITS_PER_BYTE;
  return (*reinterpret_cast<uint8_t*>(b) & (1 << (boffset % BITS_PER_BYTE / BITS))) != 0;
}

template <>
inline Void StructBuilder::getDataField<Void>(ElementCount offset) {
  return VOID;
}

template <typename T>
inline T StructBuilder::getDataField(ElementCount offset, Mask<T> mask) {
  return unmask<T>(getDataField<Mask<T> >(offset), mask);
}

template <typename T>
inline void StructBuilder::setDataField(ElementCount offset, kj::NoInfer<T> value) {
  reinterpret_cast<WireValue<T>*>(data)[offset / ELEMENTS].set(value);
}

#if CAPNP_CANONICALIZE_NAN
// Use mask() on floats and doubles to make sure we canonicalize NaNs.
template <>
inline void StructBuilder::setDataField<float>(ElementCount offset, float value) {
  setDataField<uint32_t>(offset, mask<float>(value, 0));
}
template <>
inline void StructBuilder::setDataField<double>(ElementCount offset, double value) {
  setDataField<uint64_t>(offset, mask<double>(value, 0));
}
#endif

template <>
inline void StructBuilder::setDataField<bool>(ElementCount offset, bool value) {
  // This branch should be compiled out whenever this is inlined with a constant offset.
  BitCount boffset = (offset == 0 * ELEMENTS) ?
      BitCount(bit0Offset) : offset * (1 * BITS / ELEMENTS);
  byte* b = reinterpret_cast<byte*>(data) + boffset / BITS_PER_BYTE;
  uint bitnum = boffset % BITS_PER_BYTE / BITS;
  *reinterpret_cast<uint8_t*>(b) = (*reinterpret_cast<uint8_t*>(b) & ~(1 << bitnum))
                                 | (static_cast<uint8_t>(value) << bitnum);
}

template <>
inline void StructBuilder::setDataField<Void>(ElementCount offset, Void value) {}

template <typename T>
inline void StructBuilder::setDataField(ElementCount offset, kj::NoInfer<T> value, Mask<T> m) {
  setDataField<Mask<T> >(offset, mask<T>(value, m));
}

inline PointerBuilder StructBuilder::getPointerField(WirePointerCount ptrIndex) {
  // Hacky because WirePointer is defined in the .c++ file (so is incomplete here).
  return PointerBuilder(segment, reinterpret_cast<WirePointer*>(
      reinterpret_cast<word*>(pointers) + ptrIndex * WORDS_PER_POINTER));
}

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

inline Data::Reader StructReader::getDataSectionAsBlob() {
  return Data::Reader(reinterpret_cast<const byte*>(data), dataSize / BITS_PER_BYTE / BYTES);
}

template <typename T>
inline bool StructReader::hasDataField(ElementCount offset) const {
  return getDataField<Mask<T>>(offset) != 0;
}

template <>
inline bool StructReader::hasDataField<Void>(ElementCount offset) const {
  return false;
}

template <typename T>
inline T StructReader::getDataField(ElementCount offset) const {
  if ((offset + 1 * ELEMENTS) * capnp::bitsPerElement<T>() <= dataSize) {
    return reinterpret_cast<const WireValue<T>*>(data)[offset / ELEMENTS].get();
  } else {
    return static_cast<T>(0);
  }
}

template <>
inline bool StructReader::getDataField<bool>(ElementCount offset) const {
  BitCount boffset = offset * (1 * BITS / ELEMENTS);
  if (boffset < dataSize) {
    // This branch should be compiled out whenever this is inlined with a constant offset.
    if (offset == 0 * ELEMENTS) {
      boffset = bit0Offset;
    }
    const byte* b = reinterpret_cast<const byte*>(data) + boffset / BITS_PER_BYTE;
    return (*reinterpret_cast<const uint8_t*>(b) & (1 << (boffset % BITS_PER_BYTE / BITS))) != 0;
  } else {
    return false;
  }
}

template <>
inline Void StructReader::getDataField<Void>(ElementCount offset) const {
  return VOID;
}

template <typename T>
T StructReader::getDataField(ElementCount offset, Mask<T> mask) const {
  return unmask<T>(getDataField<Mask<T> >(offset), mask);
}

inline PointerReader StructReader::getPointerField(WirePointerCount ptrIndex) const {
  if (ptrIndex < pointerCount) {
    // Hacky because WirePointer is defined in the .c++ file (so is incomplete here).
    return PointerReader(segment, reinterpret_cast<const WirePointer*>(
        reinterpret_cast<const word*>(pointers) + ptrIndex * WORDS_PER_POINTER), nestingLimit);
  } else{
    return PointerReader();
  }
}

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

inline ElementCount ListBuilder::size() const { return elementCount; }

template <typename T>
inline T ListBuilder::getDataElement(ElementCount index) {
  return reinterpret_cast<WireValue<T>*>(ptr + index * step / BITS_PER_BYTE)->get();

  // TODO(perf):  Benchmark this alternate implementation, which I suspect may make better use of
  //   the x86 SIB byte.  Also use it for all the other getData/setData implementations below, and
  //   the various non-inline methods that look up pointers.
  //   Also if using this, consider changing ptr back to void* instead of byte*.
//  return reinterpret_cast<WireValue<T>*>(ptr)[
//      index / ELEMENTS * (step / capnp::bitsPerElement<T>())].get();
}

template <>
inline bool ListBuilder::getDataElement<bool>(ElementCount index) {
  // Ignore stepBytes for bit lists because bit lists cannot be upgraded to struct lists.
  BitCount bindex = index * step;
  byte* b = ptr + bindex / BITS_PER_BYTE;
  return (*reinterpret_cast<uint8_t*>(b) & (1 << (bindex % BITS_PER_BYTE / BITS))) != 0;
}

template <>
inline Void ListBuilder::getDataElement<Void>(ElementCount index) {
  return VOID;
}

template <typename T>
inline void ListBuilder::setDataElement(ElementCount index, kj::NoInfer<T> value) {
  reinterpret_cast<WireValue<T>*>(ptr + index * step / BITS_PER_BYTE)->set(value);
}

#if CAPNP_CANONICALIZE_NAN
// Use mask() on floats and doubles to make sure we canonicalize NaNs.
template <>
inline void ListBuilder::setDataElement<float>(ElementCount index, float value) {
  setDataElement<uint32_t>(index, mask<float>(value, 0));
}
template <>
inline void ListBuilder::setDataElement<double>(ElementCount index, double value) {
  setDataElement<uint64_t>(index, mask<double>(value, 0));
}
#endif

template <>
inline void ListBuilder::setDataElement<bool>(ElementCount index, bool value) {
  // Ignore stepBytes for bit lists because bit lists cannot be upgraded to struct lists.
  BitCount bindex = index * (1 * BITS / ELEMENTS);
  byte* b = ptr + bindex / BITS_PER_BYTE;
  uint bitnum = bindex % BITS_PER_BYTE / BITS;
  *reinterpret_cast<uint8_t*>(b) = (*reinterpret_cast<uint8_t*>(b) & ~(1 << bitnum))
                                 | (static_cast<uint8_t>(value) << bitnum);
}

template <>
inline void ListBuilder::setDataElement<Void>(ElementCount index, Void value) {}

inline PointerBuilder ListBuilder::getPointerElement(ElementCount index) {
  return PointerBuilder(segment,
      reinterpret_cast<WirePointer*>(ptr + index * step / BITS_PER_BYTE));
}

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

inline ElementCount ListReader::size() const { return elementCount; }

template <typename T>
inline T ListReader::getDataElement(ElementCount index) const {
  return reinterpret_cast<const WireValue<T>*>(ptr + index * step / BITS_PER_BYTE)->get();
}

template <>
inline bool ListReader::getDataElement<bool>(ElementCount index) const {
  // Ignore stepBytes for bit lists because bit lists cannot be upgraded to struct lists.
  BitCount bindex = index * step;
  const byte* b = ptr + bindex / BITS_PER_BYTE;
  return (*reinterpret_cast<const uint8_t*>(b) & (1 << (bindex % BITS_PER_BYTE / BITS))) != 0;
}

template <>
inline Void ListReader::getDataElement<Void>(ElementCount index) const {
  return VOID;
}

inline PointerReader ListReader::getPointerElement(ElementCount index) const {
  return PointerReader(segment,
      reinterpret_cast<const WirePointer*>(ptr + index * step / BITS_PER_BYTE), nestingLimit);
}

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

inline OrphanBuilder::OrphanBuilder(OrphanBuilder&& other) noexcept
    : segment(other.segment), location(other.location) {
  memcpy(&tag, &other.tag, sizeof(tag));  // Needs memcpy to comply with aliasing rules.
  other.segment = nullptr;
  other.location = nullptr;
}

inline OrphanBuilder::~OrphanBuilder() noexcept(false) {
  if (segment != nullptr) euthanize();
}

inline OrphanBuilder& OrphanBuilder::operator=(OrphanBuilder&& other) {
  // With normal smart pointers, it's important to handle the case where the incoming pointer
  // is actually transitively owned by this one.  In this case, euthanize() would destroy `other`
  // before we copied it.  This isn't possible in the case of `OrphanBuilder` because it only
  // owns message objects, and `other` is not itself a message object, therefore cannot possibly
  // be transitively owned by `this`.

  if (segment != nullptr) euthanize();
  segment = other.segment;
  location = other.location;
  memcpy(&tag, &other.tag, sizeof(tag));  // Needs memcpy to comply with aliasing rules.
  other.segment = nullptr;
  other.location = nullptr;
  return *this;
}

}  // namespace _ (private)
}  // namespace capnp

#endif  // CAPNP_LAYOUT_H_