flexbuffers.h

Go to the documentation of this file.

/*
 * Copyright (c) 2023 Samsung Electronics Co., Ltd. All Rights Reserved
 * Copyright 2017 Google Inc. All rights reserved.
 *
 * 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
 *
 *     http://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.
 */
 
#ifndef FLATBUFFERS_FLEXBUFFERS_H_
#define FLATBUFFERS_FLEXBUFFERS_H_
 
#include <map>
// Used to select STL variant.
#include "flatbuffers/base.h"
// We use the basic binary writing functions from the regular FlatBuffers.
#include "flatbuffers/util.h"
 
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4127) // C4127: conditional expression is constant
#endif
 
namespace flexbuffers
{
 
class Reference;
class Map;
 
// These are used in the lower 2 bits of a type field to determine the size of
// the elements (and or size field) of the item pointed to (e.g. vector).
enum BitWidth
{
  BIT_WIDTH_8 = 0,
  BIT_WIDTH_16 = 1,
  BIT_WIDTH_32 = 2,
  BIT_WIDTH_64 = 3,
};
 
// These are used as the upper 6 bits of a type field to indicate the actual
// type.
enum Type
{
  FBT_NULL = 0,
  FBT_INT = 1,
  FBT_UINT = 2,
  FBT_FLOAT = 3,
  // Types above stored inline, types below store an offset.
  FBT_KEY = 4,
  FBT_STRING = 5,
  FBT_INDIRECT_INT = 6,
  FBT_INDIRECT_UINT = 7,
  FBT_INDIRECT_FLOAT = 8,
  FBT_MAP = 9,
  FBT_VECTOR = 10,     // Untyped.
  FBT_VECTOR_INT = 11, // Typed any size (stores no type table).
  FBT_VECTOR_UINT = 12,
  FBT_VECTOR_FLOAT = 13,
  FBT_VECTOR_KEY = 14,
  // DEPRECATED, use FBT_VECTOR or FBT_VECTOR_KEY instead.
  // Read test.cpp/FlexBuffersDeprecatedTest() for details on why.
  FBT_VECTOR_STRING_DEPRECATED = 15,
  FBT_VECTOR_INT2 = 16, // Typed tuple (no type table, no size field).
  FBT_VECTOR_UINT2 = 17,
  FBT_VECTOR_FLOAT2 = 18,
  FBT_VECTOR_INT3 = 19, // Typed triple (no type table, no size field).
  FBT_VECTOR_UINT3 = 20,
  FBT_VECTOR_FLOAT3 = 21,
  FBT_VECTOR_INT4 = 22, // Typed quad (no type table, no size field).
  FBT_VECTOR_UINT4 = 23,
  FBT_VECTOR_FLOAT4 = 24,
  FBT_BLOB = 25,
  FBT_BOOL = 26,
  FBT_VECTOR_BOOL = 36, // To Allow the same type of conversion of type to vector type
};
 
inline bool IsInline(Type t) { return t <= FBT_FLOAT || t == FBT_BOOL; }
 
inline bool IsTypedVectorElementType(Type t)
{
  return (t >= FBT_INT && t <= FBT_STRING) || t == FBT_BOOL;
}
 
inline bool IsTypedVector(Type t)
{
  return (t >= FBT_VECTOR_INT && t <= FBT_VECTOR_STRING_DEPRECATED) || t == FBT_VECTOR_BOOL;
}
 
inline bool IsFixedTypedVector(Type t) { return t >= FBT_VECTOR_INT2 && t <= FBT_VECTOR_FLOAT4; }
 
inline Type ToTypedVector(Type t, size_t fixed_len = 0)
{
  FLATBUFFERS_ASSERT(IsTypedVectorElementType(t));
  switch (fixed_len)
  {
    case 0:
      return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT);
    case 2:
      return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT2);
    case 3:
      return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT3);
    case 4:
      return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT4);
    default:
      FLATBUFFERS_ASSERT(0);
      return FBT_NULL;
  }
}
 
inline Type ToTypedVectorElementType(Type t)
{
  FLATBUFFERS_ASSERT(IsTypedVector(t));
  return static_cast<Type>(t - FBT_VECTOR_INT + FBT_INT);
}
 
inline Type ToFixedTypedVectorElementType(Type t, uint8_t *len)
{
  FLATBUFFERS_ASSERT(IsFixedTypedVector(t));
  auto fixed_type = t - FBT_VECTOR_INT2;
  *len = static_cast<uint8_t>(fixed_type / 3 + 2); // 3 types each, starting from length 2.
  return static_cast<Type>(fixed_type % 3 + FBT_INT);
}
 
// TODO: implement proper support for 8/16bit floats, or decide not to
// support them.
typedef int16_t half;
typedef int8_t quarter;
 
// TODO: can we do this without conditionals using intrinsics or inline asm
// on some platforms? Given branch prediction the method below should be
// decently quick, but it is the most frequently executed function.
// We could do an (unaligned) 64-bit read if we ifdef out the platforms for
// which that doesn't work (or where we'd read into un-owned memory).
template <typename R, typename T1, typename T2, typename T4, typename T8>
R ReadSizedScalar(const uint8_t *data, uint8_t byte_width)
{
  return byte_width < 4 ? (byte_width < 2 ? static_cast<R>(flatbuffers::ReadScalar<T1>(data))
                                          : static_cast<R>(flatbuffers::ReadScalar<T2>(data)))
                        : (byte_width < 8 ? static_cast<R>(flatbuffers::ReadScalar<T4>(data))
                                          : static_cast<R>(flatbuffers::ReadScalar<T8>(data)));
}
 
inline int64_t ReadInt64(const uint8_t *data, uint8_t byte_width)
{
  return ReadSizedScalar<int64_t, int8_t, int16_t, int32_t, int64_t>(data, byte_width);
}
 
inline uint64_t ReadUInt64(const uint8_t *data, uint8_t byte_width)
{
#if defined(_MSC_VER) && ((defined(_M_X64) && !defined(_M_ARM64EC)) || defined _M_IX86)
  uint64_t u = 0;
  __movsb(reinterpret_cast<uint8_t *>(&u), reinterpret_cast<const uint8_t *>(data), byte_width);
  return flatbuffers::EndianScalar(u);
#else
  return ReadSizedScalar<uint64_t, uint8_t, uint16_t, uint32_t, uint64_t>(data, byte_width);
#endif
  // clang-format on
}
 
inline double ReadDouble(const uint8_t *data, uint8_t byte_width)
{
  return ReadSizedScalar<double, quarter, half, float, double>(data, byte_width);
}
 
inline const uint8_t *Indirect(const uint8_t *offset, uint8_t byte_width)
{
  return offset - ReadUInt64(offset, byte_width);
}
 
template <typename T> const uint8_t *Indirect(const uint8_t *offset)
{
  return offset - flatbuffers::ReadScalar<T>(offset);
}
 
inline BitWidth WidthU(uint64_t u)
{
#define FLATBUFFERS_GET_FIELD_BIT_WIDTH(value, width) \
  {                                                   \
    if (!((u) & ~((1ULL << (width)) - 1ULL)))         \
      return BIT_WIDTH_##width;                       \
  }
  FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 8);
  FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 16);
  FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 32);
#undef FLATBUFFERS_GET_FIELD_BIT_WIDTH
  return BIT_WIDTH_64;
}
 
inline BitWidth WidthI(int64_t i)
{
  auto u = static_cast<uint64_t>(i) << 1;
  return WidthU(i >= 0 ? u : ~u);
}
 
inline BitWidth WidthF(double f)
{
  return static_cast<double>(static_cast<float>(f)) == f ? BIT_WIDTH_32 : BIT_WIDTH_64;
}
 
// Base class of all types below.
// Points into the data buffer and allows access to one type.
class Object
{
public:
  Object(const uint8_t *data, uint8_t byte_width) : data_(data), byte_width_(byte_width) {}
 
protected:
  const uint8_t *data_;
  uint8_t byte_width_;
};
 
// Object that has a size, obtained either from size prefix, or elsewhere.
class Sized : public Object
{
public:
  // Size prefix.
  Sized(const uint8_t *data, uint8_t byte_width) : Object(data, byte_width), size_(read_size()) {}
  // Manual size.
  Sized(const uint8_t *data, uint8_t byte_width, size_t sz) : Object(data, byte_width), size_(sz) {}
  size_t size() const { return size_; }
  // Access size stored in `byte_width_` bytes before data_ pointer.
  size_t read_size() const
  {
    return static_cast<size_t>(ReadUInt64(data_ - byte_width_, byte_width_));
  }
 
protected:
  size_t size_;
};
 
class String : public Sized
{
public:
  // Size prefix.
  String(const uint8_t *data, uint8_t byte_width) : Sized(data, byte_width) {}
  // Manual size.
  String(const uint8_t *data, uint8_t byte_width, size_t sz) : Sized(data, byte_width, sz) {}
 
  size_t length() const { return size(); }
  const char *c_str() const { return reinterpret_cast<const char *>(data_); }
  std::string str() const { return std::string(c_str(), size()); }
 
  static String EmptyString()
  {
    static const char *empty_string = "";
    return String(reinterpret_cast<const uint8_t *>(empty_string), 1, 0);
  }
  bool IsTheEmptyString() const { return data_ == EmptyString().data_; }
};
 
class Blob : public Sized
{
public:
  Blob(const uint8_t *data_buf, uint8_t byte_width) : Sized(data_buf, byte_width) {}
 
  static Blob EmptyBlob()
  {
    static const uint8_t empty_blob[] = {0 /*len*/};
    return Blob(empty_blob + 1, 1);
  }
  bool IsTheEmptyBlob() const { return data_ == EmptyBlob().data_; }
  const uint8_t *data() const { return data_; }
};
 
class Vector : public Sized
{
public:
  Vector(const uint8_t *data, uint8_t byte_width) : Sized(data, byte_width) {}
 
  Reference operator[](size_t i) const;
 
  static Vector EmptyVector()
  {
    static const uint8_t empty_vector[] = {0 /*len*/};
    return Vector(empty_vector + 1, 1);
  }
  bool IsTheEmptyVector() const { return data_ == EmptyVector().data_; }
};
 
class TypedVector : public Sized
{
public:
  TypedVector(const uint8_t *data, uint8_t byte_width, Type element_type)
    : Sized(data, byte_width), type_(element_type)
  {
  }
 
  Reference operator[](size_t i) const;
 
  static TypedVector EmptyTypedVector()
  {
    static const uint8_t empty_typed_vector[] = {0 /*len*/};
    return TypedVector(empty_typed_vector + 1, 1, FBT_INT);
  }
  bool IsTheEmptyVector() const { return data_ == TypedVector::EmptyTypedVector().data_; }
 
  Type ElementType() { return type_; }
 
  friend Reference;
 
private:
  Type type_;
 
  friend Map;
};
 
class FixedTypedVector : public Object
{
public:
  FixedTypedVector(const uint8_t *data, uint8_t byte_width, Type element_type, uint8_t len)
    : Object(data, byte_width), type_(element_type), len_(len)
  {
  }
 
  Reference operator[](size_t i) const;
 
  static FixedTypedVector EmptyFixedTypedVector()
  {
    static const uint8_t fixed_empty_vector[] = {0 /* unused */};
    return FixedTypedVector(fixed_empty_vector, 1, FBT_INT, 0);
  }
  bool IsTheEmptyFixedTypedVector() const
  {
    return data_ == FixedTypedVector::EmptyFixedTypedVector().data_;
  }
 
  Type ElementType() { return type_; }
  uint8_t size() { return len_; }
 
private:
  Type type_;
  uint8_t len_;
};
 
class Map : public Vector
{
public:
  Map(const uint8_t *data, uint8_t byte_width) : Vector(data, byte_width) {}
 
  Reference operator[](const char *key) const;
  Reference operator[](const std::string &key) const;
 
  Vector Values() const { return Vector(data_, byte_width_); }
 
  TypedVector Keys() const
  {
    const size_t num_prefixed_fields = 3;
    auto keys_offset = data_ - byte_width_ * num_prefixed_fields;
    return TypedVector(Indirect(keys_offset, byte_width_),
                       static_cast<uint8_t>(ReadUInt64(keys_offset + byte_width_, byte_width_)),
                       FBT_KEY);
  }
 
  static Map EmptyMap()
  {
    static const uint8_t empty_map[] = {
      0 /*keys_len*/, 0 /*keys_offset*/, 1 /*keys_width*/, 0 /*len*/
    };
    return Map(empty_map + 4, 1);
  }
 
  bool IsTheEmptyMap() const { return data_ == EmptyMap().data_; }
};
 
template <typename T> void AppendToString(std::string &s, T &&v, bool keys_quoted)
{
  s += "[ ";
  for (size_t i = 0; i < v.size(); i++)
  {
    if (i)
      s += ", ";
    v[i].ToString(true, keys_quoted, s);
  }
  s += " ]";
}
 
class Reference
{
public:
  Reference() : data_(nullptr), parent_width_(0), byte_width_(BIT_WIDTH_8), type_(FBT_NULL) {}
 
  Reference(const uint8_t *data, uint8_t parent_width, uint8_t byte_width, Type type)
    : data_(data), parent_width_(parent_width), byte_width_(byte_width), type_(type)
  {
  }
 
  Reference(const uint8_t *data, uint8_t parent_width, uint8_t packed_type)
    : data_(data), parent_width_(parent_width)
  {
    byte_width_ = 1U << static_cast<BitWidth>(packed_type & 3);
    type_ = static_cast<Type>(packed_type >> 2);
  }
 
  Type GetType() const { return type_; }
 
  bool IsNull() const { return type_ == FBT_NULL; }
  bool IsBool() const { return type_ == FBT_BOOL; }
  bool IsInt() const { return type_ == FBT_INT || type_ == FBT_INDIRECT_INT; }
  bool IsUInt() const { return type_ == FBT_UINT || type_ == FBT_INDIRECT_UINT; }
  bool IsIntOrUint() const { return IsInt() || IsUInt(); }
  bool IsFloat() const { return type_ == FBT_FLOAT || type_ == FBT_INDIRECT_FLOAT; }
  bool IsNumeric() const { return IsIntOrUint() || IsFloat(); }
  bool IsString() const { return type_ == FBT_STRING; }
  bool IsKey() const { return type_ == FBT_KEY; }
  bool IsVector() const { return type_ == FBT_VECTOR || type_ == FBT_MAP; }
  bool IsUntypedVector() const { return type_ == FBT_VECTOR; }
  bool IsTypedVector() const { return flexbuffers::IsTypedVector(type_); }
  bool IsFixedTypedVector() const { return flexbuffers::IsFixedTypedVector(type_); }
  bool IsAnyVector() const { return (IsTypedVector() || IsFixedTypedVector() || IsVector()); }
  bool IsMap() const { return type_ == FBT_MAP; }
  bool IsBlob() const { return type_ == FBT_BLOB; }
  bool AsBool() const
  {
    return (type_ == FBT_BOOL ? ReadUInt64(data_, parent_width_) : AsUInt64()) != 0;
  }
 
  // Reads any type as a int64_t. Never fails, does most sensible conversion.
  // Truncates floats, strings are attempted to be parsed for a number,
  // vectors/maps return their size. Returns 0 if all else fails.
  int64_t AsInt64() const
  {
    if (type_ == FBT_INT)
    {
      // A fast path for the common case.
      return ReadInt64(data_, parent_width_);
    }
    else
      switch (type_)
      {
        case FBT_INDIRECT_INT:
          return ReadInt64(Indirect(), byte_width_);
        case FBT_UINT:
          return ReadUInt64(data_, parent_width_);
        case FBT_INDIRECT_UINT:
          return ReadUInt64(Indirect(), byte_width_);
        case FBT_FLOAT:
          return static_cast<int64_t>(ReadDouble(data_, parent_width_));
        case FBT_INDIRECT_FLOAT:
          return static_cast<int64_t>(ReadDouble(Indirect(), byte_width_));
        case FBT_NULL:
          return 0;
        case FBT_STRING:
          return flatbuffers::StringToInt(AsString().c_str());
        case FBT_VECTOR:
          return static_cast<int64_t>(AsVector().size());
        case FBT_BOOL:
          return ReadInt64(data_, parent_width_);
        default:
          // Convert other things to int.
          return 0;
      }
  }
 
  // TODO: could specialize these to not use AsInt64() if that saves
  // extension ops in generated code, and use a faster op than ReadInt64.
  int32_t AsInt32() const { return static_cast<int32_t>(AsInt64()); }
  int16_t AsInt16() const { return static_cast<int16_t>(AsInt64()); }
  int8_t AsInt8() const { return static_cast<int8_t>(AsInt64()); }
 
  uint64_t AsUInt64() const
  {
    if (type_ == FBT_UINT)
    {
      // A fast path for the common case.
      return ReadUInt64(data_, parent_width_);
    }
    else
      switch (type_)
      {
        case FBT_INDIRECT_UINT:
          return ReadUInt64(Indirect(), byte_width_);
        case FBT_INT:
          return ReadInt64(data_, parent_width_);
        case FBT_INDIRECT_INT:
          return ReadInt64(Indirect(), byte_width_);
        case FBT_FLOAT:
          return static_cast<uint64_t>(ReadDouble(data_, parent_width_));
        case FBT_INDIRECT_FLOAT:
          return static_cast<uint64_t>(ReadDouble(Indirect(), byte_width_));
        case FBT_NULL:
          return 0;
        case FBT_STRING:
          return flatbuffers::StringToUInt(AsString().c_str());
        case FBT_VECTOR:
          return static_cast<uint64_t>(AsVector().size());
        case FBT_BOOL:
          return ReadUInt64(data_, parent_width_);
        default:
          // Convert other things to uint.
          return 0;
      }
  }
 
  uint32_t AsUInt32() const { return static_cast<uint32_t>(AsUInt64()); }
  uint16_t AsUInt16() const { return static_cast<uint16_t>(AsUInt64()); }
  uint8_t AsUInt8() const { return static_cast<uint8_t>(AsUInt64()); }
 
  double AsDouble() const
  {
    if (type_ == FBT_FLOAT)
    {
      // A fast path for the common case.
      return ReadDouble(data_, parent_width_);
    }
    else
      switch (type_)
      {
        case FBT_INDIRECT_FLOAT:
          return ReadDouble(Indirect(), byte_width_);
        case FBT_INT:
          return static_cast<double>(ReadInt64(data_, parent_width_));
        case FBT_UINT:
          return static_cast<double>(ReadUInt64(data_, parent_width_));
        case FBT_INDIRECT_INT:
          return static_cast<double>(ReadInt64(Indirect(), byte_width_));
        case FBT_INDIRECT_UINT:
          return static_cast<double>(ReadUInt64(Indirect(), byte_width_));
        case FBT_NULL:
          return 0.0;
        case FBT_STRING:
        {
          double d;
          flatbuffers::StringToNumber(AsString().c_str(), &d);
          return d;
        }
        case FBT_VECTOR:
          return static_cast<double>(AsVector().size());
        case FBT_BOOL:
          return static_cast<double>(ReadUInt64(data_, parent_width_));
        default:
          // Convert strings and other things to float.
          return 0;
      }
  }
 
  float AsFloat() const { return static_cast<float>(AsDouble()); }
 
  const char *AsKey() const
  {
    if (type_ == FBT_KEY || type_ == FBT_STRING)
    {
      return reinterpret_cast<const char *>(Indirect());
    }
    else
    {
      return "";
    }
  }
 
  // This function returns the empty string if you try to read something that
  // is not a string or key.
  String AsString() const
  {
    if (type_ == FBT_STRING)
    {
      return String(Indirect(), byte_width_);
    }
    else if (type_ == FBT_KEY)
    {
      auto key = Indirect();
      return String(key, byte_width_, strlen(reinterpret_cast<const char *>(key)));
    }
    else
    {
      return String::EmptyString();
    }
  }
 
  // Unlike AsString(), this will convert any type to a std::string.
  std::string ToString() const
  {
    std::string s;
    ToString(false, false, s);
    return s;
  }
 
  // Convert any type to a JSON-like string. strings_quoted determines if
  // string values at the top level receive "" quotes (inside other values
  // they always do). keys_quoted determines if keys are quoted, at any level.
  // TODO(wvo): add further options to have indentation/newlines.
  void ToString(bool strings_quoted, bool keys_quoted, std::string &s) const
  {
    if (type_ == FBT_STRING)
    {
      String str(Indirect(), byte_width_);
      if (strings_quoted)
      {
        flatbuffers::EscapeString(str.c_str(), str.length(), &s, true, false);
      }
      else
      {
        s.append(str.c_str(), str.length());
      }
    }
    else if (IsKey())
    {
      auto str = AsKey();
      if (keys_quoted)
      {
        flatbuffers::EscapeString(str, strlen(str), &s, true, false);
      }
      else
      {
        s += str;
      }
    }
    else if (IsInt())
    {
      s += flatbuffers::NumToString(AsInt64());
    }
    else if (IsUInt())
    {
      s += flatbuffers::NumToString(AsUInt64());
    }
    else if (IsFloat())
    {
      s += flatbuffers::NumToString(AsDouble());
    }
    else if (IsNull())
    {
      s += "null";
    }
    else if (IsBool())
    {
      s += AsBool() ? "true" : "false";
    }
    else if (IsMap())
    {
      s += "{ ";
      auto m = AsMap();
      auto keys = m.Keys();
      auto vals = m.Values();
      for (size_t i = 0; i < keys.size(); i++)
      {
        keys[i].ToString(true, keys_quoted, s);
        s += ": ";
        vals[i].ToString(true, keys_quoted, s);
        if (i < keys.size() - 1)
          s += ", ";
      }
      s += " }";
    }
    else if (IsVector())
    {
      AppendToString<Vector>(s, AsVector(), keys_quoted);
    }
    else if (IsTypedVector())
    {
      AppendToString<TypedVector>(s, AsTypedVector(), keys_quoted);
    }
    else if (IsFixedTypedVector())
    {
      AppendToString<FixedTypedVector>(s, AsFixedTypedVector(), keys_quoted);
    }
    else if (IsBlob())
    {
      auto blob = AsBlob();
      flatbuffers::EscapeString(reinterpret_cast<const char *>(blob.data()), blob.size(), &s, true,
                                false);
    }
    else
    {
      s += "(?)";
    }
  }
 
  // This function returns the empty blob if you try to read a not-blob.
  // Strings can be viewed as blobs too.
  Blob AsBlob() const
  {
    if (type_ == FBT_BLOB || type_ == FBT_STRING)
    {
      return Blob(Indirect(), byte_width_);
    }
    else
    {
      return Blob::EmptyBlob();
    }
  }
 
  // This function returns the empty vector if you try to read a not-vector.
  // Maps can be viewed as vectors too.
  Vector AsVector() const
  {
    if (type_ == FBT_VECTOR || type_ == FBT_MAP)
    {
      return Vector(Indirect(), byte_width_);
    }
    else
    {
      return Vector::EmptyVector();
    }
  }
 
  TypedVector AsTypedVector() const
  {
    if (IsTypedVector())
    {
      auto tv = TypedVector(Indirect(), byte_width_, ToTypedVectorElementType(type_));
      if (tv.type_ == FBT_STRING)
      {
        // These can't be accessed as strings, since we don't know the bit-width
        // of the size field, see the declaration of
        // FBT_VECTOR_STRING_DEPRECATED above for details.
        // We change the type here to be keys, which are a subtype of strings,
        // and will ignore the size field. This will truncate strings with
        // embedded nulls.
        tv.type_ = FBT_KEY;
      }
      return tv;
    }
    else
    {
      return TypedVector::EmptyTypedVector();
    }
  }
 
  FixedTypedVector AsFixedTypedVector() const
  {
    if (IsFixedTypedVector())
    {
      uint8_t len = 0;
      auto vtype = ToFixedTypedVectorElementType(type_, &len);
      return FixedTypedVector(Indirect(), byte_width_, vtype, len);
    }
    else
    {
      return FixedTypedVector::EmptyFixedTypedVector();
    }
  }
 
  Map AsMap() const
  {
    if (type_ == FBT_MAP)
    {
      return Map(Indirect(), byte_width_);
    }
    else
    {
      return Map::EmptyMap();
    }
  }
 
  template <typename T> T As() const;
 
  // Experimental: Mutation functions.
  // These allow scalars in an already created buffer to be updated in-place.
  // Since by default scalars are stored in the smallest possible space,
  // the new value may not fit, in which case these functions return false.
  // To avoid this, you can construct the values you intend to mutate using
  // Builder::ForceMinimumBitWidth.
  bool MutateInt(int64_t i)
  {
    if (type_ == FBT_INT)
    {
      return Mutate(data_, i, parent_width_, WidthI(i));
    }
    else if (type_ == FBT_INDIRECT_INT)
    {
      return Mutate(Indirect(), i, byte_width_, WidthI(i));
    }
    else if (type_ == FBT_UINT)
    {
      auto u = static_cast<uint64_t>(i);
      return Mutate(data_, u, parent_width_, WidthU(u));
    }
    else if (type_ == FBT_INDIRECT_UINT)
    {
      auto u = static_cast<uint64_t>(i);
      return Mutate(Indirect(), u, byte_width_, WidthU(u));
    }
    else
    {
      return false;
    }
  }
 
  bool MutateBool(bool b)
  {
    return type_ == FBT_BOOL && Mutate(data_, b, parent_width_, BIT_WIDTH_8);
  }
 
  bool MutateUInt(uint64_t u)
  {
    if (type_ == FBT_UINT)
    {
      return Mutate(data_, u, parent_width_, WidthU(u));
    }
    else if (type_ == FBT_INDIRECT_UINT)
    {
      return Mutate(Indirect(), u, byte_width_, WidthU(u));
    }
    else if (type_ == FBT_INT)
    {
      auto i = static_cast<int64_t>(u);
      return Mutate(data_, i, parent_width_, WidthI(i));
    }
    else if (type_ == FBT_INDIRECT_INT)
    {
      auto i = static_cast<int64_t>(u);
      return Mutate(Indirect(), i, byte_width_, WidthI(i));
    }
    else
    {
      return false;
    }
  }
 
  bool MutateFloat(float f)
  {
    if (type_ == FBT_FLOAT)
    {
      return MutateF(data_, f, parent_width_, BIT_WIDTH_32);
    }
    else if (type_ == FBT_INDIRECT_FLOAT)
    {
      return MutateF(Indirect(), f, byte_width_, BIT_WIDTH_32);
    }
    else
    {
      return false;
    }
  }
 
  bool MutateFloat(double d)
  {
    if (type_ == FBT_FLOAT)
    {
      return MutateF(data_, d, parent_width_, WidthF(d));
    }
    else if (type_ == FBT_INDIRECT_FLOAT)
    {
      return MutateF(Indirect(), d, byte_width_, WidthF(d));
    }
    else
    {
      return false;
    }
  }
 
  bool MutateString(const char *str, size_t len)
  {
    auto s = AsString();
    if (s.IsTheEmptyString())
      return false;
    // This is very strict, could allow shorter strings, but that creates
    // garbage.
    if (s.length() != len)
      return false;
    memcpy(const_cast<char *>(s.c_str()), str, len);
    return true;
  }
  bool MutateString(const char *str) { return MutateString(str, strlen(str)); }
  bool MutateString(const std::string &str) { return MutateString(str.data(), str.length()); }
 
private:
  const uint8_t *Indirect() const { return flexbuffers::Indirect(data_, parent_width_); }
 
  template <typename T>
  bool Mutate(const uint8_t *dest, T t, size_t byte_width, BitWidth value_width)
  {
    auto fits = static_cast<size_t>(static_cast<size_t>(1U) << value_width) <= byte_width;
    if (fits)
    {
      t = flatbuffers::EndianScalar(t);
      memcpy(const_cast<uint8_t *>(dest), &t, byte_width);
    }
    return fits;
  }
 
  template <typename T>
  bool MutateF(const uint8_t *dest, T t, size_t byte_width, BitWidth value_width)
  {
    if (byte_width == sizeof(double))
      return Mutate(dest, static_cast<double>(t), byte_width, value_width);
    if (byte_width == sizeof(float))
      return Mutate(dest, static_cast<float>(t), byte_width, value_width);
    FLATBUFFERS_ASSERT(false);
    return false;
  }
 
  const uint8_t *data_;
  uint8_t parent_width_;
  uint8_t byte_width_;
  Type type_;
};
 
// Template specialization for As().
template <> inline bool Reference::As<bool>() const { return AsBool(); }
 
template <> inline int8_t Reference::As<int8_t>() const { return AsInt8(); }
template <> inline int16_t Reference::As<int16_t>() const { return AsInt16(); }
template <> inline int32_t Reference::As<int32_t>() const { return AsInt32(); }
template <> inline int64_t Reference::As<int64_t>() const { return AsInt64(); }
 
template <> inline uint8_t Reference::As<uint8_t>() const { return AsUInt8(); }
template <> inline uint16_t Reference::As<uint16_t>() const { return AsUInt16(); }
template <> inline uint32_t Reference::As<uint32_t>() const { return AsUInt32(); }
template <> inline uint64_t Reference::As<uint64_t>() const { return AsUInt64(); }
 
template <> inline double Reference::As<double>() const { return AsDouble(); }
template <> inline float Reference::As<float>() const { return AsFloat(); }
 
template <> inline String Reference::As<String>() const { return AsString(); }
template <> inline std::string Reference::As<std::string>() const { return AsString().str(); }
 
template <> inline Blob Reference::As<Blob>() const { return AsBlob(); }
template <> inline Vector Reference::As<Vector>() const { return AsVector(); }
template <> inline TypedVector Reference::As<TypedVector>() const { return AsTypedVector(); }
template <> inline FixedTypedVector Reference::As<FixedTypedVector>() const
{
  return AsFixedTypedVector();
}
template <> inline Map Reference::As<Map>() const { return AsMap(); }
 
inline uint8_t PackedType(BitWidth bit_width, Type type)
{
  return static_cast<uint8_t>(bit_width | (type << 2));
}
 
inline uint8_t NullPackedType() { return PackedType(BIT_WIDTH_8, FBT_NULL); }
 
// Vector accessors.
// Note: if you try to access outside of bounds, you get a Null value back
// instead. Normally this would be an assert, but since this is "dynamically
// typed" data, you may not want that (someone sends you a 2d vector and you
// wanted 3d).
// The Null converts seamlessly into a default value for any other type.
// TODO(wvo): Could introduce an #ifdef that makes this into an assert?
inline Reference Vector::operator[](size_t i) const
{
  auto len = size();
  if (i >= len)
    return Reference(nullptr, 1, NullPackedType());
  auto packed_type = (data_ + len * byte_width_)[i];
  auto elem = data_ + i * byte_width_;
  return Reference(elem, byte_width_, packed_type);
}
 
inline Reference TypedVector::operator[](size_t i) const
{
  auto len = size();
  if (i >= len)
    return Reference(nullptr, 1, NullPackedType());
  auto elem = data_ + i * byte_width_;
  return Reference(elem, byte_width_, 1, type_);
}
 
inline Reference FixedTypedVector::operator[](size_t i) const
{
  if (i >= len_)
    return Reference(nullptr, 1, NullPackedType());
  auto elem = data_ + i * byte_width_;
  return Reference(elem, byte_width_, 1, type_);
}
 
template <typename T> int KeyCompare(const void *key, const void *elem)
{
  auto str_elem =
    reinterpret_cast<const char *>(Indirect<T>(reinterpret_cast<const uint8_t *>(elem)));
  auto skey = reinterpret_cast<const char *>(key);
  return strcmp(skey, str_elem);
}
 
inline Reference Map::operator[](const char *key) const
{
  auto keys = Keys();
  // We can't pass keys.byte_width_ to the comparison function, so we have
  // to pick the right one ahead of time.
  int (*comp)(const void *, const void *) = nullptr;
  switch (keys.byte_width_)
  {
    case 1:
      comp = KeyCompare<uint8_t>;
      break;
    case 2:
      comp = KeyCompare<uint16_t>;
      break;
    case 4:
      comp = KeyCompare<uint32_t>;
      break;
    case 8:
      comp = KeyCompare<uint64_t>;
      break;
  }
  auto res = std::bsearch(key, keys.data_, keys.size(), keys.byte_width_, comp);
  if (!res)
    return Reference(nullptr, 1, NullPackedType());
  auto i = (reinterpret_cast<uint8_t *>(res) - keys.data_) / keys.byte_width_;
  return (*static_cast<const Vector *>(this))[i];
}
 
inline Reference Map::operator[](const std::string &key) const { return (*this)[key.c_str()]; }
 
inline Reference GetRoot(const uint8_t *buffer, size_t size)
{
  // See Finish() below for the serialization counterpart of this.
  // The root starts at the end of the buffer, so we parse backwards from there.
  auto end = buffer + size;
  auto byte_width = *--end;
  auto packed_type = *--end;
  end -= byte_width; // The root data item.
  return Reference(end, byte_width, packed_type);
}
 
inline Reference GetRoot(const std::vector<uint8_t> &buffer)
{
  return GetRoot(flatbuffers::vector_data(buffer), buffer.size());
}
 
// Flags that configure how the Builder behaves.
// The "Share" flags determine if the Builder automatically tries to pool
// this type. Pooling can reduce the size of serialized data if there are
// multiple maps of the same kind, at the expense of slightly slower
// serialization (the cost of lookups) and more memory use (std::set).
// By default this is on for keys, but off for strings.
// Turn keys off if you have e.g. only one map.
// Turn strings on if you expect many non-unique string values.
// Additionally, sharing key vectors can save space if you have maps with
// identical field populations.
enum BuilderFlag
{
  BUILDER_FLAG_NONE = 0,
  BUILDER_FLAG_SHARE_KEYS = 1,
  BUILDER_FLAG_SHARE_STRINGS = 2,
  BUILDER_FLAG_SHARE_KEYS_AND_STRINGS = 3,
  BUILDER_FLAG_SHARE_KEY_VECTORS = 4,
  BUILDER_FLAG_SHARE_ALL = 7,
};
 
class Builder FLATBUFFERS_FINAL_CLASS
{
public:
  Builder(size_t initial_size = 256, BuilderFlag flags = BUILDER_FLAG_SHARE_KEYS)
    : buf_(initial_size), finished_(false), has_duplicate_keys_(false), flags_(flags),
      force_min_bit_width_(BIT_WIDTH_8), key_pool(KeyOffsetCompare(buf_)),
      string_pool(StringOffsetCompare(buf_))
  {
    buf_.clear();
  }
 
#ifdef FLATBUFFERS_DEFAULT_DECLARATION
  Builder(Builder &&) = default;
  Builder &operator=(Builder &&) = default;
#endif
 
  const std::vector<uint8_t> &GetBuffer() const
  {
    Finished();
    return buf_;
  }
 
  // Size of the buffer. Does not include unfinished values.
  size_t GetSize() const { return buf_.size(); }
 
  // Reset all state so we can re-use the buffer.
  void Clear()
  {
    buf_.clear();
    stack_.clear();
    finished_ = false;
    // flags_ remains as-is;
    force_min_bit_width_ = BIT_WIDTH_8;
    key_pool.clear();
    string_pool.clear();
  }
 
  // All value constructing functions below have two versions: one that
  // takes a key (for placement inside a map) and one that doesn't (for inside
  // vectors and elsewhere).
 
  void Null() { stack_.push_back(Value()); }
  void Null(const char *key)
  {
    Key(key);
    Null();
  }
 
  void Int(int64_t i) { stack_.push_back(Value(i, FBT_INT, WidthI(i))); }
  void Int(const char *key, int64_t i)
  {
    Key(key);
    Int(i);
  }
 
  void UInt(uint64_t u) { stack_.push_back(Value(u, FBT_UINT, WidthU(u))); }
  void UInt(const char *key, uint64_t u)
  {
    Key(key);
    UInt(u);
  }
 
  void Float(float f) { stack_.push_back(Value(f)); }
  void Float(const char *key, float f)
  {
    Key(key);
    Float(f);
  }
 
  void Double(double f) { stack_.push_back(Value(f)); }
  void Double(const char *key, double d)
  {
    Key(key);
    Double(d);
  }
 
  void Bool(bool b) { stack_.push_back(Value(b)); }
  void Bool(const char *key, bool b)
  {
    Key(key);
    Bool(b);
  }
 
  void IndirectInt(int64_t i) { PushIndirect(i, FBT_INDIRECT_INT, WidthI(i)); }
  void IndirectInt(const char *key, int64_t i)
  {
    Key(key);
    IndirectInt(i);
  }
 
  void IndirectUInt(uint64_t u) { PushIndirect(u, FBT_INDIRECT_UINT, WidthU(u)); }
  void IndirectUInt(const char *key, uint64_t u)
  {
    Key(key);
    IndirectUInt(u);
  }
 
  void IndirectFloat(float f) { PushIndirect(f, FBT_INDIRECT_FLOAT, BIT_WIDTH_32); }
  void IndirectFloat(const char *key, float f)
  {
    Key(key);
    IndirectFloat(f);
  }
 
  void IndirectDouble(double f) { PushIndirect(f, FBT_INDIRECT_FLOAT, WidthF(f)); }
  void IndirectDouble(const char *key, double d)
  {
    Key(key);
    IndirectDouble(d);
  }
 
  size_t Key(const char *str, size_t len)
  {
    auto sloc = buf_.size();
    WriteBytes(str, len + 1);
    if (flags_ & BUILDER_FLAG_SHARE_KEYS)
    {
      auto it = key_pool.find(sloc);
      if (it != key_pool.end())
      {
        // Already in the buffer. Remove key we just serialized, and use
        // existing offset instead.
        buf_.resize(sloc);
        sloc = *it;
      }
      else
      {
        key_pool.insert(sloc);
      }
    }
    stack_.push_back(Value(static_cast<uint64_t>(sloc), FBT_KEY, BIT_WIDTH_8));
    return sloc;
  }
 
  size_t Key(const char *str) { return Key(str, strlen(str)); }
  size_t Key(const std::string &str) { return Key(str.c_str(), str.size()); }
 
  size_t String(const char *str, size_t len)
  {
    auto reset_to = buf_.size();
    auto sloc = CreateBlob(str, len, 1, FBT_STRING);
    if (flags_ & BUILDER_FLAG_SHARE_STRINGS)
    {
      StringOffset so(sloc, len);
      auto it = string_pool.find(so);
      if (it != string_pool.end())
      {
        // Already in the buffer. Remove string we just serialized, and use
        // existing offset instead.
        buf_.resize(reset_to);
        sloc = it->first;
        stack_.back().u_ = sloc;
      }
      else
      {
        string_pool.insert(so);
      }
    }
    return sloc;
  }
  size_t String(const char *str) { return String(str, strlen(str)); }
  size_t String(const std::string &str) { return String(str.c_str(), str.size()); }
  void String(const flexbuffers::String &str) { String(str.c_str(), str.length()); }
 
  void String(const char *key, const char *str)
  {
    Key(key);
    String(str);
  }
  void String(const char *key, const std::string &str)
  {
    Key(key);
    String(str);
  }
  void String(const char *key, const flexbuffers::String &str)
  {
    Key(key);
    String(str);
  }
 
  size_t Blob(const void *data, size_t len) { return CreateBlob(data, len, 0, FBT_BLOB); }
  size_t Blob(const std::vector<uint8_t> &v)
  {
    return CreateBlob(flatbuffers::vector_data(v), v.size(), 0, FBT_BLOB);
  }
 
  // TODO(wvo): support all the FlexBuffer types (like flexbuffers::String),
  // e.g. Vector etc. Also in overloaded versions.
  // Also some FlatBuffers types?
 
  size_t StartVector() { return stack_.size(); }
  size_t StartVector(const char *key)
  {
    Key(key);
    return stack_.size();
  }
  size_t StartMap() { return stack_.size(); }
  size_t StartMap(const char *key)
  {
    Key(key);
    return stack_.size();
  }
 
  // TODO(wvo): allow this to specify an aligment greater than the natural
  // alignment.
  size_t EndVector(size_t start, bool typed, bool fixed)
  {
    auto vec = CreateVector(start, stack_.size() - start, 1, typed, fixed);
    // Remove temp elements and return vector.
    stack_.resize(start);
    stack_.push_back(vec);
    return static_cast<size_t>(vec.u_);
  }
 
  size_t EndMap(size_t start)
  {
    // We should have interleaved keys and values on the stack.
    // Make sure it is an even number:
    auto len = stack_.size() - start;
    FLATBUFFERS_ASSERT(!(len & 1));
    len /= 2;
    // Make sure keys are all strings:
    for (auto key = start; key < stack_.size(); key += 2)
    {
      FLATBUFFERS_ASSERT(stack_[key].type_ == FBT_KEY);
    }
    // Now sort values, so later we can do a binary search lookup.
    // We want to sort 2 array elements at a time.
    struct TwoValue
    {
      Value key;
      Value val;
    };
    // TODO(wvo): strict aliasing?
    // TODO(wvo): allow the caller to indicate the data is already sorted
    // for maximum efficiency? With an assert to check sortedness to make sure
    // we're not breaking binary search.
    // Or, we can track if the map is sorted as keys are added which would be
    // be quite cheap (cheaper than checking it here), so we can skip this
    // step automatically when appliccable, and encourage people to write in
    // sorted fashion.
    // std::sort is typically already a lot faster on sorted data though.
    auto dict = reinterpret_cast<TwoValue *>(flatbuffers::vector_data(stack_) + start);
    std::sort(dict, dict + len, [&](const TwoValue &a, const TwoValue &b) -> bool {
      auto as = reinterpret_cast<const char *>(flatbuffers::vector_data(buf_) + a.key.u_);
      auto bs = reinterpret_cast<const char *>(flatbuffers::vector_data(buf_) + b.key.u_);
      auto comp = strcmp(as, bs);
      // We want to disallow duplicate keys, since this results in a
      // map where values cannot be found.
      // But we can't assert here (since we don't want to fail on
      // random JSON input) or have an error mechanism.
      // Instead, we set has_duplicate_keys_ in the builder to
      // signal this.
      // TODO: Have to check for pointer equality, as some sort
      // implementation apparently call this function with the same
      // element?? Why?
      if (!comp && &a != &b)
        has_duplicate_keys_ = true;
      return comp < 0;
    });
    // First create a vector out of all keys.
    // TODO(wvo): if kBuilderFlagShareKeyVectors is true, see if we can share
    // the first vector.
    auto keys = CreateVector(start, len, 2, true, false);
    auto vec = CreateVector(start + 1, len, 2, false, false, &keys);
    // Remove temp elements and return map.
    stack_.resize(start);
    stack_.push_back(vec);
    return static_cast<size_t>(vec.u_);
  }
 
  // Call this after EndMap to see if the map had any duplicate keys.
  // Any map with such keys won't be able to retrieve all values.
  bool HasDuplicateKeys() const { return has_duplicate_keys_; }
 
  template <typename F> size_t Vector(F f)
  {
    auto start = StartVector();
    f();
    return EndVector(start, false, false);
  }
  template <typename F, typename T> size_t Vector(F f, T &state)
  {
    auto start = StartVector();
    f(state);
    return EndVector(start, false, false);
  }
  template <typename F> size_t Vector(const char *key, F f)
  {
    auto start = StartVector(key);
    f();
    return EndVector(start, false, false);
  }
  template <typename F, typename T> size_t Vector(const char *key, F f, T &state)
  {
    auto start = StartVector(key);
    f(state);
    return EndVector(start, false, false);
  }
 
  template <typename T> void Vector(const T *elems, size_t len)
  {
    if (flatbuffers::is_scalar<T>::value)
    {
      // This path should be a lot quicker and use less space.
      ScalarVector(elems, len, false);
    }
    else
    {
      auto start = StartVector();
      for (size_t i = 0; i < len; i++)
        Add(elems[i]);
      EndVector(start, false, false);
    }
  }
  template <typename T> void Vector(const char *key, const T *elems, size_t len)
  {
    Key(key);
    Vector(elems, len);
  }
  template <typename T> void Vector(const std::vector<T> &vec)
  {
    Vector(flatbuffers::vector_data(vec), vec.size());
  }
 
  template <typename F> size_t TypedVector(F f)
  {
    auto start = StartVector();
    f();
    return EndVector(start, true, false);
  }
  template <typename F, typename T> size_t TypedVector(F f, T &state)
  {
    auto start = StartVector();
    f(state);
    return EndVector(start, true, false);
  }
  template <typename F> size_t TypedVector(const char *key, F f)
  {
    auto start = StartVector(key);
    f();
    return EndVector(start, true, false);
  }
  template <typename F, typename T> size_t TypedVector(const char *key, F f, T &state)
  {
    auto start = StartVector(key);
    f(state);
    return EndVector(start, true, false);
  }
 
  template <typename T> size_t FixedTypedVector(const T *elems, size_t len)
  {
    // We only support a few fixed vector lengths. Anything bigger use a
    // regular typed vector.
    FLATBUFFERS_ASSERT(len >= 2 && len <= 4);
    // And only scalar values.
    static_assert(flatbuffers::is_scalar<T>::value, "Unrelated types");
    return ScalarVector(elems, len, true);
  }
 
  template <typename T> size_t FixedTypedVector(const char *key, const T *elems, size_t len)
  {
    Key(key);
    return FixedTypedVector(elems, len);
  }
 
  template <typename F> size_t Map(F f)
  {
    auto start = StartMap();
    f();
    return EndMap(start);
  }
  template <typename F, typename T> size_t Map(F f, T &state)
  {
    auto start = StartMap();
    f(state);
    return EndMap(start);
  }
  template <typename F> size_t Map(const char *key, F f)
  {
    auto start = StartMap(key);
    f();
    return EndMap(start);
  }
  template <typename F, typename T> size_t Map(const char *key, F f, T &state)
  {
    auto start = StartMap(key);
    f(state);
    return EndMap(start);
  }
  template <typename T> void Map(const std::map<std::string, T> &map)
  {
    auto start = StartMap();
    for (auto it = map.begin(); it != map.end(); ++it)
      Add(it->first.c_str(), it->second);
    EndMap(start);
  }
 
  // If you wish to share a value explicitly (a value not shared automatically
  // through one of the BUILDER_FLAG_SHARE_* flags) you can do so with these
  // functions. Or if you wish to turn those flags off for performance reasons
  // and still do some explicit sharing. For example:
  // builder.IndirectDouble(M_PI);
  // auto id = builder.LastValue();  // Remember where we stored it.
  // .. more code goes here ..
  // builder.ReuseValue(id);  // Refers to same double by offset.
  // LastValue works regardless of whether the value has a key or not.
  // Works on any data type.
  struct Value;
  Value LastValue() { return stack_.back(); }
  void ReuseValue(Value v) { stack_.push_back(v); }
  void ReuseValue(const char *key, Value v)
  {
    Key(key);
    ReuseValue(v);
  }
 
  // Overloaded Add that tries to call the correct function above.
  void Add(int8_t i) { Int(i); }
  void Add(int16_t i) { Int(i); }
  void Add(int32_t i) { Int(i); }
  void Add(int64_t i) { Int(i); }
  void Add(uint8_t u) { UInt(u); }
  void Add(uint16_t u) { UInt(u); }
  void Add(uint32_t u) { UInt(u); }
  void Add(uint64_t u) { UInt(u); }
  void Add(float f) { Float(f); }
  void Add(double d) { Double(d); }
  void Add(bool b) { Bool(b); }
  void Add(const char *str) { String(str); }
  void Add(const std::string &str) { String(str); }
  void Add(const flexbuffers::String &str) { String(str); }
 
  template <typename T> void Add(const std::vector<T> &vec) { Vector(vec); }
 
  template <typename T> void Add(const char *key, const T &t)
  {
    Key(key);
    Add(t);
  }
 
  template <typename T> void Add(const std::map<std::string, T> &map) { Map(map); }
 
  template <typename T> void operator+=(const T &t) { Add(t); }
 
  // This function is useful in combination with the Mutate* functions above.
  // It forces elements of vectors and maps to have a minimum size, such that
  // they can later be updated without failing.
  // Call with no arguments to reset.
  void ForceMinimumBitWidth(BitWidth bw = BIT_WIDTH_8) { force_min_bit_width_ = bw; }
 
  void Finish()
  {
    // If you hit this assert, you likely have objects that were never included
    // in a parent. You need to have exactly one root to finish a buffer.
    // Check your Start/End calls are matched, and all objects are inside
    // some other object.
    FLATBUFFERS_ASSERT(stack_.size() == 1);
 
    // Write root value.
    auto byte_width = Align(stack_[0].ElemWidth(buf_.size(), 0));
    WriteAny(stack_[0], byte_width);
    // Write root type.
    Write(stack_[0].StoredPackedType(), 1);
    // Write root size. Normally determined by parent, but root has no parent :)
    Write(byte_width, 1);
 
    finished_ = true;
  }
 
private:
  void Finished() const
  {
    // If you get this assert, you're attempting to get access a buffer
    // which hasn't been finished yet. Be sure to call
    // Builder::Finish with your root object.
    FLATBUFFERS_ASSERT(finished_);
  }
 
  // Align to prepare for writing a scalar with a certain size.
  uint8_t Align(BitWidth alignment)
  {
    auto byte_width = 1U << alignment;
    buf_.insert(buf_.end(), flatbuffers::PaddingBytes(buf_.size(), byte_width), 0);
    return static_cast<uint8_t>(byte_width);
  }
 
  void WriteBytes(const void *val, size_t size)
  {
    buf_.insert(buf_.end(), reinterpret_cast<const uint8_t *>(val),
                reinterpret_cast<const uint8_t *>(val) + size);
  }
 
  template <typename T> void Write(T val, size_t byte_width)
  {
    FLATBUFFERS_ASSERT(sizeof(T) >= byte_width);
    val = flatbuffers::EndianScalar(val);
    WriteBytes(&val, byte_width);
  }
 
  void WriteDouble(double f, uint8_t byte_width)
  {
    switch (byte_width)
    {
      case 8:
        Write(f, byte_width);
        break;
      case 4:
        Write(static_cast<float>(f), byte_width);
        break;
      // case 2: Write(static_cast<half>(f), byte_width); break;
      // case 1: Write(static_cast<quarter>(f), byte_width); break;
      default:
        FLATBUFFERS_ASSERT(0);
    }
  }
 
  void WriteOffset(uint64_t o, uint8_t byte_width)
  {
    auto reloff = buf_.size() - o;
    FLATBUFFERS_ASSERT(byte_width == 8 || reloff < 1ULL << (byte_width * 8));
    Write(reloff, byte_width);
  }
 
  template <typename T> void PushIndirect(T val, Type type, BitWidth bit_width)
  {
    auto byte_width = Align(bit_width);
    auto iloc = buf_.size();
    Write(val, byte_width);
    stack_.push_back(Value(static_cast<uint64_t>(iloc), type, bit_width));
  }
 
  static BitWidth WidthB(size_t byte_width)
  {
    switch (byte_width)
    {
      case 1:
        return BIT_WIDTH_8;
      case 2:
        return BIT_WIDTH_16;
      case 4:
        return BIT_WIDTH_32;
      case 8:
        return BIT_WIDTH_64;
      default:
        FLATBUFFERS_ASSERT(false);
        return BIT_WIDTH_64;
    }
  }
 
  template <typename T> static Type GetScalarType()
  {
    static_assert(flatbuffers::is_scalar<T>::value, "Unrelated types");
    return flatbuffers::is_floating_point<T>::value
             ? FBT_FLOAT
             : flatbuffers::is_same<T, bool>::value
                 ? FBT_BOOL
                 : (flatbuffers::is_unsigned<T>::value ? FBT_UINT : FBT_INT);
  }
 
public:
  // This was really intended to be private, except for LastValue/ReuseValue.
  struct Value
  {
    union {
      int64_t i_;
      uint64_t u_;
      double f_;
    };
 
    Type type_;
 
    // For scalars: of itself, for vector: of its elements, for string: length.
    BitWidth min_bit_width_;
 
    Value() : i_(0), type_(FBT_NULL), min_bit_width_(BIT_WIDTH_8) {}
 
    Value(bool b) : u_(static_cast<uint64_t>(b)), type_(FBT_BOOL), min_bit_width_(BIT_WIDTH_8) {}
 
    Value(int64_t i, Type t, BitWidth bw) : i_(i), type_(t), min_bit_width_(bw) {}
    Value(uint64_t u, Type t, BitWidth bw) : u_(u), type_(t), min_bit_width_(bw) {}
 
    Value(float f) : f_(static_cast<double>(f)), type_(FBT_FLOAT), min_bit_width_(BIT_WIDTH_32) {}
    Value(double f) : f_(f), type_(FBT_FLOAT), min_bit_width_(WidthF(f)) {}
 
    uint8_t StoredPackedType(BitWidth parent_bit_width_ = BIT_WIDTH_8) const
    {
      return PackedType(StoredWidth(parent_bit_width_), type_);
    }
 
    BitWidth ElemWidth(size_t buf_size, size_t elem_index) const
    {
      if (IsInline(type_))
      {
        return min_bit_width_;
      }
      else
      {
        // We have an absolute offset, but want to store a relative offset
        // elem_index elements beyond the current buffer end. Since whether
        // the relative offset fits in a certain byte_width depends on
        // the size of the elements before it (and their alignment), we have
        // to test for each size in turn.
        for (size_t byte_width = 1; byte_width <= sizeof(flatbuffers::largest_scalar_t);
             byte_width *= 2)
        {
          // Where are we going to write this offset?
          auto offset_loc =
            buf_size + flatbuffers::PaddingBytes(buf_size, byte_width) + elem_index * byte_width;
          // Compute relative offset.
          auto offset = offset_loc - u_;
          // Does it fit?
          auto bit_width = WidthU(offset);
          if (static_cast<size_t>(static_cast<size_t>(1U) << bit_width) == byte_width)
            return bit_width;
        }
        FLATBUFFERS_ASSERT(false); // Must match one of the sizes above.
        return BIT_WIDTH_64;
      }
    }
 
    BitWidth StoredWidth(BitWidth parent_bit_width_ = BIT_WIDTH_8) const
    {
      if (IsInline(type_))
      {
        return (std::max)(min_bit_width_, parent_bit_width_);
      }
      else
      {
        return min_bit_width_;
      }
    }
  };
 
private:
  void WriteAny(const Value &val, uint8_t byte_width)
  {
    switch (val.type_)
    {
      case FBT_NULL:
      case FBT_INT:
        Write(val.i_, byte_width);
        break;
      case FBT_BOOL:
      case FBT_UINT:
        Write(val.u_, byte_width);
        break;
      case FBT_FLOAT:
        WriteDouble(val.f_, byte_width);
        break;
      default:
        WriteOffset(val.u_, byte_width);
        break;
    }
  }
 
  size_t CreateBlob(const void *data, size_t len, size_t trailing, Type type)
  {
    auto bit_width = WidthU(len);
    auto byte_width = Align(bit_width);
    Write<uint64_t>(len, byte_width);
    auto sloc = buf_.size();
    WriteBytes(data, len + trailing);
    stack_.push_back(Value(static_cast<uint64_t>(sloc), type, bit_width));
    return sloc;
  }
 
  template <typename T> size_t ScalarVector(const T *elems, size_t len, bool fixed)
  {
    auto vector_type = GetScalarType<T>();
    auto byte_width = sizeof(T);
    auto bit_width = WidthB(byte_width);
    // If you get this assert, you're trying to write a vector with a size
    // field that is bigger than the scalars you're trying to write (e.g. a
    // byte vector > 255 elements). For such types, write a "blob" instead.
    // TODO: instead of asserting, could write vector with larger elements
    // instead, though that would be wasteful.
    FLATBUFFERS_ASSERT(WidthU(len) <= bit_width);
    Align(bit_width);
    if (!fixed)
      Write<uint64_t>(len, byte_width);
    auto vloc = buf_.size();
    for (size_t i = 0; i < len; i++)
      Write(elems[i], byte_width);
    stack_.push_back(
      Value(static_cast<uint64_t>(vloc), ToTypedVector(vector_type, fixed ? len : 0), bit_width));
    return vloc;
  }
 
  Value CreateVector(size_t start, size_t vec_len, size_t step, bool typed, bool fixed,
                     const Value *keys = nullptr)
  {
    FLATBUFFERS_ASSERT(!fixed || typed); // typed=false, fixed=true combination is not supported.
    // Figure out smallest bit width we can store this vector with.
    auto bit_width = (std::max)(force_min_bit_width_, WidthU(vec_len));
    auto prefix_elems = 1;
    if (keys)
    {
      // If this vector is part of a map, we will pre-fix an offset to the keys
      // to this vector.
      bit_width = (std::max)(bit_width, keys->ElemWidth(buf_.size(), 0));
      prefix_elems += 2;
    }
    Type vector_type = FBT_KEY;
    // Check bit widths and types for all elements.
    for (size_t i = start; i < stack_.size(); i += step)
    {
      auto elem_width = stack_[i].ElemWidth(buf_.size(), i - start + prefix_elems);
      bit_width = (std::max)(bit_width, elem_width);
      if (typed)
      {
        if (i == start)
        {
          vector_type = stack_[i].type_;
        }
        else
        {
          // If you get this assert, you are writing a typed vector with
          // elements that are not all the same type.
          FLATBUFFERS_ASSERT(vector_type == stack_[i].type_);
        }
      }
    }
    // If you get this assert, your fixed types are not one of:
    // Int / UInt / Float / Key.
    FLATBUFFERS_ASSERT(!fixed || IsTypedVectorElementType(vector_type));
    auto byte_width = Align(bit_width);
    // Write vector. First the keys width/offset if available, and size.
    if (keys)
    {
      WriteOffset(keys->u_, byte_width);
      Write<uint64_t>(1ULL << keys->min_bit_width_, byte_width);
    }
    if (!fixed)
      Write<uint64_t>(vec_len, byte_width);
    // Then the actual data.
    auto vloc = buf_.size();
    for (size_t i = start; i < stack_.size(); i += step)
    {
      WriteAny(stack_[i], byte_width);
    }
    // Then the types.
    if (!typed)
    {
      for (size_t i = start; i < stack_.size(); i += step)
      {
        buf_.push_back(stack_[i].StoredPackedType(bit_width));
      }
    }
    return Value(static_cast<uint64_t>(vloc),
                 keys ? FBT_MAP
                      : (typed ? ToTypedVector(vector_type, fixed ? vec_len : 0) : FBT_VECTOR),
                 bit_width);
  }
 
  // You shouldn't really be copying instances of this class.
  Builder(const Builder &);
  Builder &operator=(const Builder &);
 
  std::vector<uint8_t> buf_;
  std::vector<Value> stack_;
 
  bool finished_;
  bool has_duplicate_keys_;
 
  BuilderFlag flags_;
 
  BitWidth force_min_bit_width_;
 
  struct KeyOffsetCompare
  {
    explicit KeyOffsetCompare(const std::vector<uint8_t> &buf) : buf_(&buf) {}
    bool operator()(size_t a, size_t b) const
    {
      auto stra = reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + a);
      auto strb = reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + b);
      return strcmp(stra, strb) < 0;
    }
    const std::vector<uint8_t> *buf_;
  };
 
  typedef std::pair<size_t, size_t> StringOffset;
  struct StringOffsetCompare
  {
    explicit StringOffsetCompare(const std::vector<uint8_t> &buf) : buf_(&buf) {}
    bool operator()(const StringOffset &a, const StringOffset &b) const
    {
      auto stra = reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + a.first);
      auto strb = reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + b.first);
      return strncmp(stra, strb, (std::min)(a.second, b.second) + 1) < 0;
    }
    const std::vector<uint8_t> *buf_;
  };
 
  typedef std::set<size_t, KeyOffsetCompare> KeyOffsetMap;
  typedef std::set<StringOffset, StringOffsetCompare> StringOffsetMap;
 
  KeyOffsetMap key_pool;
  StringOffsetMap string_pool;
};
 
} // namespace flexbuffers
 
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
 
#endif // FLATBUFFERS_FLEXBUFFERS_H_