include/flatbuffers/flexbuffers.h

   1 /*
   2  * Copyright 2017 Google Inc. All rights reserved.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FLATBUFFERS_FLEXBUFFERS_H_
  18 #define FLATBUFFERS_FLEXBUFFERS_H_
  19
  20 #include <map>
  21 // Used to select STL variant.
  22 #include "flatbuffers/base.h"
  23 // We use the basic binary writing functions from the regular FlatBuffers.
  24 #include "flatbuffers/util.h"
  25
  26 #ifdef _MSC_VER
  27 #  include <intrin.h>
  28 #endif
  29
  30 #if defined(_MSC_VER)
  31 #  pragma warning(push)
  32 #  pragma warning(disable : 4127)  // C4127: conditional expression is constant
  33 #endif
  34
  35 namespace flexbuffers {
  36
  37 class Reference;
  38 class Map;
  39
  40 // These are used in the lower 2 bits of a type field to determine the size of
  41 // the elements (and or size field) of the item pointed to (e.g. vector).
  42 enum BitWidth {
  43   BIT_WIDTH_8 = 0,
  44   BIT_WIDTH_16 = 1,
  45   BIT_WIDTH_32 = 2,
  46   BIT_WIDTH_64 = 3,
  47 };
  48
  49 // These are used as the upper 6 bits of a type field to indicate the actual
  50 // type.
  51 enum Type {
  52   FBT_NULL = 0,
  53   FBT_INT = 1,
  54   FBT_UINT = 2,
  55   FBT_FLOAT = 3,
  56   // Types above stored inline, types below store an offset.
  57   FBT_KEY = 4,
  58   FBT_STRING = 5,
  59   FBT_INDIRECT_INT = 6,
  60   FBT_INDIRECT_UINT = 7,
  61   FBT_INDIRECT_FLOAT = 8,
  62   FBT_MAP = 9,
  63   FBT_VECTOR = 10,      // Untyped.
  64   FBT_VECTOR_INT = 11,  // Typed any size (stores no type table).
  65   FBT_VECTOR_UINT = 12,
  66   FBT_VECTOR_FLOAT = 13,
  67   FBT_VECTOR_KEY = 14,
  68   FBT_VECTOR_STRING = 15,
  69   FBT_VECTOR_INT2 = 16,  // Typed tuple (no type table, no size field).
  70   FBT_VECTOR_UINT2 = 17,
  71   FBT_VECTOR_FLOAT2 = 18,
  72   FBT_VECTOR_INT3 = 19,  // Typed triple (no type table, no size field).
  73   FBT_VECTOR_UINT3 = 20,
  74   FBT_VECTOR_FLOAT3 = 21,
  75   FBT_VECTOR_INT4 = 22,  // Typed quad (no type table, no size field).
  76   FBT_VECTOR_UINT4 = 23,
  77   FBT_VECTOR_FLOAT4 = 24,
  78   FBT_BLOB = 25,
  79   FBT_BOOL = 26,
  80   FBT_VECTOR_BOOL =
  81       36,  // To Allow the same type of conversion of type to vector type
  82 };
  83
  84 inline bool IsInline(Type t) { return t <= FBT_FLOAT || t == FBT_BOOL; }
  85
  86 inline bool IsTypedVectorElementType(Type t) {
  87   return (t >= FBT_INT && t <= FBT_STRING) || t == FBT_BOOL;
  88 }
  89
  90 inline bool IsTypedVector(Type t) {
  91   return (t >= FBT_VECTOR_INT && t <= FBT_VECTOR_STRING) ||
  92          t == FBT_VECTOR_BOOL;
  93 }
  94
  95 inline bool IsFixedTypedVector(Type t) {
  96   return t >= FBT_VECTOR_INT2 && t <= FBT_VECTOR_FLOAT4;
  97 }
  98
  99 inline Type ToTypedVector(Type t, size_t fixed_len = 0) {
 100   FLATBUFFERS_ASSERT(IsTypedVectorElementType(t));
 101   switch (fixed_len) {
 102     case 0: return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT);
 103     case 2: return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT2);
 104     case 3: return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT3);
 105     case 4: return static_cast<Type>(t - FBT_INT + FBT_VECTOR_INT4);
 106     default: FLATBUFFERS_ASSERT(0); return FBT_NULL;
 107   }
 108 }
 109
 110 inline Type ToTypedVectorElementType(Type t) {
 111   FLATBUFFERS_ASSERT(IsTypedVector(t));
 112   return static_cast<Type>(t - FBT_VECTOR_INT + FBT_INT);
 113 }
 114
 115 inline Type ToFixedTypedVectorElementType(Type t, uint8_t *len) {
 116   FLATBUFFERS_ASSERT(IsFixedTypedVector(t));
 117   auto fixed_type = t - FBT_VECTOR_INT2;
 118   *len = static_cast<uint8_t>(fixed_type / 3 +
 119                               2);  // 3 types each, starting from length 2.
 120   return static_cast<Type>(fixed_type % 3 + FBT_INT);
 121 }
 122
 123 // TODO: implement proper support for 8/16bit floats, or decide not to
 124 // support them.
 125 typedef int16_t half;
 126 typedef int8_t quarter;
 127
 128 // TODO: can we do this without conditionals using intrinsics or inline asm
 129 // on some platforms? Given branch prediction the method below should be
 130 // decently quick, but it is the most frequently executed function.
 131 // We could do an (unaligned) 64-bit read if we ifdef out the platforms for
 132 // which that doesn't work (or where we'd read into un-owned memory).
 133 template<typename R, typename T1, typename T2, typename T4, typename T8>
 134 R ReadSizedScalar(const uint8_t *data, uint8_t byte_width) {
 135   return byte_width < 4
 136              ? (byte_width < 2
 137                     ? static_cast<R>(flatbuffers::ReadScalar<T1>(data))
 138                     : static_cast<R>(flatbuffers::ReadScalar<T2>(data)))
 139              : (byte_width < 8
 140                     ? static_cast<R>(flatbuffers::ReadScalar<T4>(data))
 141                     : static_cast<R>(flatbuffers::ReadScalar<T8>(data)));
 142 }
 143
 144 inline int64_t ReadInt64(const uint8_t *data, uint8_t byte_width) {
 145   return ReadSizedScalar<int64_t, int8_t, int16_t, int32_t, int64_t>(
 146       data, byte_width);
 147 }
 148
 149 inline uint64_t ReadUInt64(const uint8_t *data, uint8_t byte_width) {
 150   // This is the "hottest" function (all offset lookups use this), so worth
 151   // optimizing if possible.
 152   // TODO: GCC apparently replaces memcpy by a rep movsb, but only if count is a
 153   // constant, which here it isn't. Test if memcpy is still faster than
 154   // the conditionals in ReadSizedScalar. Can also use inline asm.
 155   // clang-format off
 156   #if defined(_MSC_VER) && (defined(_M_X64) || defined _M_IX86)
 157     uint64_t u = 0;
 158     __movsb(reinterpret_cast<uint8_t *>(&u),
 159             reinterpret_cast<const uint8_t *>(data), byte_width);
 160     return flatbuffers::EndianScalar(u);
 161   #else
 162     return ReadSizedScalar<uint64_t, uint8_t, uint16_t, uint32_t, uint64_t>(
 163              data, byte_width);
 164   #endif
 165   // clang-format on
 166 }
 167
 168 inline double ReadDouble(const uint8_t *data, uint8_t byte_width) {
 169   return ReadSizedScalar<double, quarter, half, float, double>(data,
 170                                                                byte_width);
 171 }
 172
 173 inline const uint8_t *Indirect(const uint8_t *offset, uint8_t byte_width) {
 174   return offset - ReadUInt64(offset, byte_width);
 175 }
 176
 177 template<typename T> const uint8_t *Indirect(const uint8_t *offset) {
 178   return offset - flatbuffers::ReadScalar<T>(offset);
 179 }
 180
 181 inline BitWidth WidthU(uint64_t u) {
 182 #define FLATBUFFERS_GET_FIELD_BIT_WIDTH(value, width)                   \
 183   {                                                                     \
 184     if (!((u) & ~((1ULL << (width)) - 1ULL))) return BIT_WIDTH_##width; \
 185   }
 186   FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 8);
 187   FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 16);
 188   FLATBUFFERS_GET_FIELD_BIT_WIDTH(u, 32);
 189 #undef FLATBUFFERS_GET_FIELD_BIT_WIDTH
 190   return BIT_WIDTH_64;
 191 }
 192
 193 inline BitWidth WidthI(int64_t i) {
 194   auto u = static_cast<uint64_t>(i) << 1;
 195   return WidthU(i >= 0 ? u : ~u);
 196 }
 197
 198 inline BitWidth WidthF(double f) {
 199   return static_cast<double>(static_cast<float>(f)) == f ? BIT_WIDTH_32
 200                                                          : BIT_WIDTH_64;
 201 }
 202
 203 // Base class of all types below.
 204 // Points into the data buffer and allows access to one type.
 205 class Object {
 206  public:
 207   Object(const uint8_t *data, uint8_t byte_width)
 208       : data_(data), byte_width_(byte_width) {}
 209
 210  protected:
 211   const uint8_t *data_;
 212   uint8_t byte_width_;
 213 };
 214
 215 // Stores size in `byte_width_` bytes before data_ pointer.
 216 class Sized : public Object {
 217  public:
 218   Sized(const uint8_t *data, uint8_t byte_width) : Object(data, byte_width) {}
 219   size_t size() const {
 220     return static_cast<size_t>(ReadUInt64(data_ - byte_width_, byte_width_));
 221   }
 222 };
 223
 224 class String : public Sized {
 225  public:
 226   String(const uint8_t *data, uint8_t byte_width) : Sized(data, byte_width) {}
 227
 228   size_t length() const { return size(); }
 229   const char *c_str() const { return reinterpret_cast<const char *>(data_); }
 230   std::string str() const { return std::string(c_str(), length()); }
 231
 232   static String EmptyString() {
 233     static const uint8_t empty_string[] = { 0 /*len*/, 0 /*terminator*/ };
 234     return String(empty_string + 1, 1);
 235   }
 236   bool IsTheEmptyString() const { return data_ == EmptyString().data_; }
 237 };
 238
 239 class Blob : public Sized {
 240  public:
 241   Blob(const uint8_t *data_buf, uint8_t byte_width)
 242       : Sized(data_buf, byte_width) {}
 243
 244   static Blob EmptyBlob() {
 245     static const uint8_t empty_blob[] = { 0 /*len*/ };
 246     return Blob(empty_blob + 1, 1);
 247   }
 248   bool IsTheEmptyBlob() const { return data_ == EmptyBlob().data_; }
 249   const uint8_t *data() const { return data_; }
 250 };
 251
 252 class Vector : public Sized {
 253  public:
 254   Vector(const uint8_t *data, uint8_t byte_width) : Sized(data, byte_width) {}
 255
 256   Reference operator[](size_t i) const;
 257
 258   static Vector EmptyVector() {
 259     static const uint8_t empty_vector[] = { 0 /*len*/ };
 260     return Vector(empty_vector + 1, 1);
 261   }
 262   bool IsTheEmptyVector() const { return data_ == EmptyVector().data_; }
 263 };
 264
 265 class TypedVector : public Sized {
 266  public:
 267   TypedVector(const uint8_t *data, uint8_t byte_width, Type element_type)
 268       : Sized(data, byte_width), type_(element_type) {}
 269
 270   Reference operator[](size_t i) const;
 271
 272   static TypedVector EmptyTypedVector() {
 273     static const uint8_t empty_typed_vector[] = { 0 /*len*/ };
 274     return TypedVector(empty_typed_vector + 1, 1, FBT_INT);
 275   }
 276   bool IsTheEmptyVector() const {
 277     return data_ == TypedVector::EmptyTypedVector().data_;
 278   }
 279
 280   Type ElementType() { return type_; }
 281
 282  private:
 283   Type type_;
 284
 285   friend Map;
 286 };
 287
 288 class FixedTypedVector : public Object {
 289  public:
 290   FixedTypedVector(const uint8_t *data, uint8_t byte_width, Type element_type,
 291                    uint8_t len)
 292       : Object(data, byte_width), type_(element_type), len_(len) {}
 293
 294   Reference operator[](size_t i) const;
 295
 296   static FixedTypedVector EmptyFixedTypedVector() {
 297     static const uint8_t fixed_empty_vector[] = { 0 /* unused */ };
 298     return FixedTypedVector(fixed_empty_vector, 1, FBT_INT, 0);
 299   }
 300   bool IsTheEmptyFixedTypedVector() const {
 301     return data_ == FixedTypedVector::EmptyFixedTypedVector().data_;
 302   }
 303
 304   Type ElementType() { return type_; }
 305   uint8_t size() { return len_; }
 306
 307  private:
 308   Type type_;
 309   uint8_t len_;
 310 };
 311
 312 class Map : public Vector {
 313  public:
 314   Map(const uint8_t *data, uint8_t byte_width) : Vector(data, byte_width) {}
 315
 316   Reference operator[](const char *key) const;
 317   Reference operator[](const std::string &key) const;
 318
 319   Vector Values() const { return Vector(data_, byte_width_); }
 320
 321   TypedVector Keys() const {
 322     const size_t num_prefixed_fields = 3;
 323     auto keys_offset = data_ - byte_width_ * num_prefixed_fields;
 324     return TypedVector(Indirect(keys_offset, byte_width_),
 325                        static_cast<uint8_t>(
 326                            ReadUInt64(keys_offset + byte_width_, byte_width_)),
 327                        FBT_KEY);
 328   }
 329
 330   static Map EmptyMap() {
 331     static const uint8_t empty_map[] = {
 332       0 /*keys_len*/, 0 /*keys_offset*/, 1 /*keys_width*/, 0 /*len*/
 333     };
 334     return Map(empty_map + 4, 1);
 335   }
 336
 337   bool IsTheEmptyMap() const { return data_ == EmptyMap().data_; }
 338 };
 339
 340 template<typename T>
 341 void AppendToString(std::string &s, T &&v, bool keys_quoted) {
 342   s += "[ ";
 343   for (size_t i = 0; i < v.size(); i++) {
 344     if (i) s += ", ";
 345     v[i].ToString(true, keys_quoted, s);
 346   }
 347   s += " ]";
 348 }
 349
 350 class Reference {
 351  public:
 352   Reference()
 353       : data_(nullptr),
 354         parent_width_(0),
 355         byte_width_(BIT_WIDTH_8),
 356         type_(FBT_NULL) {}
 357
 358   Reference(const uint8_t *data, uint8_t parent_width, uint8_t byte_width,
 359             Type type)
 360       : data_(data),
 361         parent_width_(parent_width),
 362         byte_width_(byte_width),
 363         type_(type) {}
 364
 365   Reference(const uint8_t *data, uint8_t parent_width, uint8_t packed_type)
 366       : data_(data), parent_width_(parent_width) {
 367     byte_width_ = 1U << static_cast<BitWidth>(packed_type & 3);
 368     type_ = static_cast<Type>(packed_type >> 2);
 369   }
 370
 371   Type GetType() const { return type_; }
 372
 373   bool IsNull() const { return type_ == FBT_NULL; }
 374   bool IsBool() const { return type_ == FBT_BOOL; }
 375   bool IsInt() const { return type_ == FBT_INT || type_ == FBT_INDIRECT_INT; }
 376   bool IsUInt() const {
 377     return type_ == FBT_UINT || type_ == FBT_INDIRECT_UINT;
 378   }
 379   bool IsIntOrUint() const { return IsInt() || IsUInt(); }
 380   bool IsFloat() const {
 381     return type_ == FBT_FLOAT || type_ == FBT_INDIRECT_FLOAT;
 382   }
 383   bool IsNumeric() const { return IsIntOrUint() || IsFloat(); }
 384   bool IsString() const { return type_ == FBT_STRING; }
 385   bool IsKey() const { return type_ == FBT_KEY; }
 386   bool IsVector() const { return type_ == FBT_VECTOR || type_ == FBT_MAP; }
 387   bool IsUntypedVector() const { return type_ == FBT_VECTOR; }
 388   bool IsTypedVector() const { return flexbuffers::IsTypedVector(type_); }
 389   bool IsFixedTypedVector() const {
 390     return flexbuffers::IsFixedTypedVector(type_);
 391   }
 392   bool IsAnyVector() const {
 393     return (IsTypedVector() || IsFixedTypedVector() || IsVector());
 394   }
 395   bool IsMap() const { return type_ == FBT_MAP; }
 396   bool IsBlob() const { return type_ == FBT_BLOB; }
 397   bool AsBool() const {
 398     return (type_ == FBT_BOOL ? ReadUInt64(data_, parent_width_)
 399                               : AsUInt64()) != 0;
 400   }
 401
 402   // Reads any type as a int64_t. Never fails, does most sensible conversion.
 403   // Truncates floats, strings are attempted to be parsed for a number,
 404   // vectors/maps return their size. Returns 0 if all else fails.
 405   int64_t AsInt64() const {
 406     if (type_ == FBT_INT) {
 407       // A fast path for the common case.
 408       return ReadInt64(data_, parent_width_);
 409     } else
 410       switch (type_) {
 411         case FBT_INDIRECT_INT: return ReadInt64(Indirect(), byte_width_);
 412         case FBT_UINT: return ReadUInt64(data_, parent_width_);
 413         case FBT_INDIRECT_UINT: return ReadUInt64(Indirect(), byte_width_);
 414         case FBT_FLOAT:
 415           return static_cast<int64_t>(ReadDouble(data_, parent_width_));
 416         case FBT_INDIRECT_FLOAT:
 417           return static_cast<int64_t>(ReadDouble(Indirect(), byte_width_));
 418         case FBT_NULL: return 0;
 419         case FBT_STRING: return flatbuffers::StringToInt(AsString().c_str());
 420         case FBT_VECTOR: return static_cast<int64_t>(AsVector().size());
 421         case FBT_BOOL: return ReadInt64(data_, parent_width_);
 422         default:
 423           // Convert other things to int.
 424           return 0;
 425       }
 426   }
 427
 428   // TODO: could specialize these to not use AsInt64() if that saves
 429   // extension ops in generated code, and use a faster op than ReadInt64.
 430   int32_t AsInt32() const { return static_cast<int32_t>(AsInt64()); }
 431   int16_t AsInt16() const { return static_cast<int16_t>(AsInt64()); }
 432   int8_t AsInt8() const { return static_cast<int8_t>(AsInt64()); }
 433
 434   uint64_t AsUInt64() const {
 435     if (type_ == FBT_UINT) {
 436       // A fast path for the common case.
 437       return ReadUInt64(data_, parent_width_);
 438     } else
 439       switch (type_) {
 440         case FBT_INDIRECT_UINT: return ReadUInt64(Indirect(), byte_width_);
 441         case FBT_INT: return ReadInt64(data_, parent_width_);
 442         case FBT_INDIRECT_INT: return ReadInt64(Indirect(), byte_width_);
 443         case FBT_FLOAT:
 444           return static_cast<uint64_t>(ReadDouble(data_, parent_width_));
 445         case FBT_INDIRECT_FLOAT:
 446           return static_cast<uint64_t>(ReadDouble(Indirect(), byte_width_));
 447         case FBT_NULL: return 0;
 448         case FBT_STRING: return flatbuffers::StringToUInt(AsString().c_str());
 449         case FBT_VECTOR: return static_cast<uint64_t>(AsVector().size());
 450         case FBT_BOOL: return ReadUInt64(data_, parent_width_);
 451         default:
 452           // Convert other things to uint.
 453           return 0;
 454       }
 455   }
 456
 457   uint32_t AsUInt32() const { return static_cast<uint32_t>(AsUInt64()); }
 458   uint16_t AsUInt16() const { return static_cast<uint16_t>(AsUInt64()); }
 459   uint8_t AsUInt8() const { return static_cast<uint8_t>(AsUInt64()); }
 460
 461   double AsDouble() const {
 462     if (type_ == FBT_FLOAT) {
 463       // A fast path for the common case.
 464       return ReadDouble(data_, parent_width_);
 465     } else
 466       switch (type_) {
 467         case FBT_INDIRECT_FLOAT: return ReadDouble(Indirect(), byte_width_);
 468         case FBT_INT:
 469           return static_cast<double>(ReadInt64(data_, parent_width_));
 470         case FBT_UINT:
 471           return static_cast<double>(ReadUInt64(data_, parent_width_));
 472         case FBT_INDIRECT_INT:
 473           return static_cast<double>(ReadInt64(Indirect(), byte_width_));
 474         case FBT_INDIRECT_UINT:
 475           return static_cast<double>(ReadUInt64(Indirect(), byte_width_));
 476         case FBT_NULL: return 0.0;
 477         case FBT_STRING: return strtod(AsString().c_str(), nullptr);
 478         case FBT_VECTOR: return static_cast<double>(AsVector().size());
 479         case FBT_BOOL:
 480           return static_cast<double>(ReadUInt64(data_, parent_width_));
 481         default:
 482           // Convert strings and other things to float.
 483           return 0;
 484       }
 485   }
 486
 487   float AsFloat() const { return static_cast<float>(AsDouble()); }
 488
 489   const char *AsKey() const {
 490     if (type_ == FBT_KEY) {
 491       return reinterpret_cast<const char *>(Indirect());
 492     } else {
 493       return "";
 494     }
 495   }
 496
 497   // This function returns the empty string if you try to read a not-string.
 498   String AsString() const {
 499     if (type_ == FBT_STRING) {
 500       return String(Indirect(), byte_width_);
 501     } else {
 502       return String::EmptyString();
 503     }
 504   }
 505
 506   // Unlike AsString(), this will convert any type to a std::string.
 507   std::string ToString() const {
 508     std::string s;
 509     ToString(false, false, s);
 510     return s;
 511   }
 512
 513   // Convert any type to a JSON-like string. strings_quoted determines if
 514   // string values at the top level receive "" quotes (inside other values
 515   // they always do). keys_quoted determines if keys are quoted, at any level.
 516   // TODO(wvo): add further options to have indentation/newlines.
 517   void ToString(bool strings_quoted, bool keys_quoted, std::string &s) const {
 518     if (type_ == FBT_STRING) {
 519       String str(Indirect(), byte_width_);
 520       if (strings_quoted) {
 521         flatbuffers::EscapeString(str.c_str(), str.length(), &s, true, false);
 522       } else {
 523         s.append(str.c_str(), str.length());
 524       }
 525     } else if (IsKey()) {
 526       auto str = AsKey();
 527       if (keys_quoted) {
 528         flatbuffers::EscapeString(str, strlen(str), &s, true, false);
 529       } else {
 530         s += str;
 531       }
 532     } else if (IsInt()) {
 533       s += flatbuffers::NumToString(AsInt64());
 534     } else if (IsUInt()) {
 535       s += flatbuffers::NumToString(AsUInt64());
 536     } else if (IsFloat()) {
 537       s += flatbuffers::NumToString(AsDouble());
 538     } else if (IsNull()) {
 539       s += "null";
 540     } else if (IsBool()) {
 541       s += AsBool() ? "true" : "false";
 542     } else if (IsMap()) {
 543       s += "{ ";
 544       auto m = AsMap();
 545       auto keys = m.Keys();
 546       auto vals = m.Values();
 547       for (size_t i = 0; i < keys.size(); i++) {
 548         keys[i].ToString(true, keys_quoted, s);
 549         s += ": ";
 550         vals[i].ToString(true, keys_quoted, s);
 551         if (i < keys.size() - 1) s += ", ";
 552       }
 553       s += " }";
 554     } else if (IsVector()) {
 555       AppendToString<Vector>(s, AsVector(), keys_quoted);
 556     } else if (IsTypedVector()) {
 557       AppendToString<TypedVector>(s, AsTypedVector(), keys_quoted);
 558     } else if (IsFixedTypedVector()) {
 559       AppendToString<FixedTypedVector>(s, AsFixedTypedVector(), keys_quoted);
 560     } else if (IsBlob()) {
 561       auto blob = AsBlob();
 562       flatbuffers::EscapeString(reinterpret_cast<const char *>(blob.data()),
 563                                 blob.size(), &s, true, false);
 564     } else {
 565       s += "(?)";
 566     }
 567   }
 568
 569   // This function returns the empty blob if you try to read a not-blob.
 570   // Strings can be viewed as blobs too.
 571   Blob AsBlob() const {
 572     if (type_ == FBT_BLOB || type_ == FBT_STRING) {
 573       return Blob(Indirect(), byte_width_);
 574     } else {
 575       return Blob::EmptyBlob();
 576     }
 577   }
 578
 579   // This function returns the empty vector if you try to read a not-vector.
 580   // Maps can be viewed as vectors too.
 581   Vector AsVector() const {
 582     if (type_ == FBT_VECTOR || type_ == FBT_MAP) {
 583       return Vector(Indirect(), byte_width_);
 584     } else {
 585       return Vector::EmptyVector();
 586     }
 587   }
 588
 589   TypedVector AsTypedVector() const {
 590     if (IsTypedVector()) {
 591       return TypedVector(Indirect(), byte_width_,
 592                          ToTypedVectorElementType(type_));
 593     } else {
 594       return TypedVector::EmptyTypedVector();
 595     }
 596   }
 597
 598   FixedTypedVector AsFixedTypedVector() const {
 599     if (IsFixedTypedVector()) {
 600       uint8_t len = 0;
 601       auto vtype = ToFixedTypedVectorElementType(type_, &len);
 602       return FixedTypedVector(Indirect(), byte_width_, vtype, len);
 603     } else {
 604       return FixedTypedVector::EmptyFixedTypedVector();
 605     }
 606   }
 607
 608   Map AsMap() const {
 609     if (type_ == FBT_MAP) {
 610       return Map(Indirect(), byte_width_);
 611     } else {
 612       return Map::EmptyMap();
 613     }
 614   }
 615
 616   template<typename T> T As() const;
 617
 618   // Experimental: Mutation functions.
 619   // These allow scalars in an already created buffer to be updated in-place.
 620   // Since by default scalars are stored in the smallest possible space,
 621   // the new value may not fit, in which case these functions return false.
 622   // To avoid this, you can construct the values you intend to mutate using
 623   // Builder::ForceMinimumBitWidth.
 624   bool MutateInt(int64_t i) {
 625     if (type_ == FBT_INT) {
 626       return Mutate(data_, i, parent_width_, WidthI(i));
 627     } else if (type_ == FBT_INDIRECT_INT) {
 628       return Mutate(Indirect(), i, byte_width_, WidthI(i));
 629     } else if (type_ == FBT_UINT) {
 630       auto u = static_cast<uint64_t>(i);
 631       return Mutate(data_, u, parent_width_, WidthU(u));
 632     } else if (type_ == FBT_INDIRECT_UINT) {
 633       auto u = static_cast<uint64_t>(i);
 634       return Mutate(Indirect(), u, byte_width_, WidthU(u));
 635     } else {
 636       return false;
 637     }
 638   }
 639
 640   bool MutateBool(bool b) {
 641     return type_ == FBT_BOOL && Mutate(data_, b, parent_width_, BIT_WIDTH_8);
 642   }
 643
 644   bool MutateUInt(uint64_t u) {
 645     if (type_ == FBT_UINT) {
 646       return Mutate(data_, u, parent_width_, WidthU(u));
 647     } else if (type_ == FBT_INDIRECT_UINT) {
 648       return Mutate(Indirect(), u, byte_width_, WidthU(u));
 649     } else if (type_ == FBT_INT) {
 650       auto i = static_cast<int64_t>(u);
 651       return Mutate(data_, i, parent_width_, WidthI(i));
 652     } else if (type_ == FBT_INDIRECT_INT) {
 653       auto i = static_cast<int64_t>(u);
 654       return Mutate(Indirect(), i, byte_width_, WidthI(i));
 655     } else {
 656       return false;
 657     }
 658   }
 659
 660   bool MutateFloat(float f) {
 661     if (type_ == FBT_FLOAT) {
 662       return MutateF(data_, f, parent_width_, BIT_WIDTH_32);
 663     } else if (type_ == FBT_INDIRECT_FLOAT) {
 664       return MutateF(Indirect(), f, byte_width_, BIT_WIDTH_32);
 665     } else {
 666       return false;
 667     }
 668   }
 669
 670   bool MutateFloat(double d) {
 671     if (type_ == FBT_FLOAT) {
 672       return MutateF(data_, d, parent_width_, WidthF(d));
 673     } else if (type_ == FBT_INDIRECT_FLOAT) {
 674       return MutateF(Indirect(), d, byte_width_, WidthF(d));
 675     } else {
 676       return false;
 677     }
 678   }
 679
 680   bool MutateString(const char *str, size_t len) {
 681     auto s = AsString();
 682     if (s.IsTheEmptyString()) return false;
 683     // This is very strict, could allow shorter strings, but that creates
 684     // garbage.
 685     if (s.length() != len) return false;
 686     memcpy(const_cast<char *>(s.c_str()), str, len);
 687     return true;
 688   }
 689   bool MutateString(const char *str) { return MutateString(str, strlen(str)); }
 690   bool MutateString(const std::string &str) {
 691     return MutateString(str.data(), str.length());
 692   }
 693
 694  private:
 695   const uint8_t *Indirect() const {
 696     return flexbuffers::Indirect(data_, parent_width_);
 697   }
 698
 699   template<typename T>
 700   bool Mutate(const uint8_t *dest, T t, size_t byte_width,
 701               BitWidth value_width) {
 702     auto fits = static_cast<size_t>(static_cast<size_t>(1U) << value_width) <=
 703                 byte_width;
 704     if (fits) {
 705       t = flatbuffers::EndianScalar(t);
 706       memcpy(const_cast<uint8_t *>(dest), &t, byte_width);
 707     }
 708     return fits;
 709   }
 710
 711   template<typename T>
 712   bool MutateF(const uint8_t *dest, T t, size_t byte_width,
 713                BitWidth value_width) {
 714     if (byte_width == sizeof(double))
 715       return Mutate(dest, static_cast<double>(t), byte_width, value_width);
 716     if (byte_width == sizeof(float))
 717       return Mutate(dest, static_cast<float>(t), byte_width, value_width);
 718     FLATBUFFERS_ASSERT(false);
 719     return false;
 720   }
 721
 722   const uint8_t *data_;
 723   uint8_t parent_width_;
 724   uint8_t byte_width_;
 725   Type type_;
 726 };
 727
 728 // Template specialization for As().
 729 template<> inline bool Reference::As<bool>() const { return AsBool(); }
 730
 731 template<> inline int8_t Reference::As<int8_t>() const { return AsInt8(); }
 732 template<> inline int16_t Reference::As<int16_t>() const { return AsInt16(); }
 733 template<> inline int32_t Reference::As<int32_t>() const { return AsInt32(); }
 734 template<> inline int64_t Reference::As<int64_t>() const { return AsInt64(); }
 735
 736 template<> inline uint8_t Reference::As<uint8_t>() const { return AsUInt8(); }
 737 template<> inline uint16_t Reference::As<uint16_t>() const {
 738   return AsUInt16();
 739 }
 740 template<> inline uint32_t Reference::As<uint32_t>() const {
 741   return AsUInt32();
 742 }
 743 template<> inline uint64_t Reference::As<uint64_t>() const {
 744   return AsUInt64();
 745 }
 746
 747 template<> inline double Reference::As<double>() const { return AsDouble(); }
 748 template<> inline float Reference::As<float>() const { return AsFloat(); }
 749
 750 template<> inline String Reference::As<String>() const { return AsString(); }
 751 template<> inline std::string Reference::As<std::string>() const {
 752   return AsString().str();
 753 }
 754
 755 template<> inline Blob Reference::As<Blob>() const { return AsBlob(); }
 756 template<> inline Vector Reference::As<Vector>() const { return AsVector(); }
 757 template<> inline TypedVector Reference::As<TypedVector>() const {
 758   return AsTypedVector();
 759 }
 760 template<> inline FixedTypedVector Reference::As<FixedTypedVector>() const {
 761   return AsFixedTypedVector();
 762 }
 763 template<> inline Map Reference::As<Map>() const { return AsMap(); }
 764
 765 inline uint8_t PackedType(BitWidth bit_width, Type type) {
 766   return static_cast<uint8_t>(bit_width | (type << 2));
 767 }
 768
 769 inline uint8_t NullPackedType() { return PackedType(BIT_WIDTH_8, FBT_NULL); }
 770
 771 // Vector accessors.
 772 // Note: if you try to access outside of bounds, you get a Null value back
 773 // instead. Normally this would be an assert, but since this is "dynamically
 774 // typed" data, you may not want that (someone sends you a 2d vector and you
 775 // wanted 3d).
 776 // The Null converts seamlessly into a default value for any other type.
 777 // TODO(wvo): Could introduce an #ifdef that makes this into an assert?
 778 inline Reference Vector::operator[](size_t i) const {
 779   auto len = size();
 780   if (i >= len) return Reference(nullptr, 1, NullPackedType());
 781   auto packed_type = (data_ + len * byte_width_)[i];
 782   auto elem = data_ + i * byte_width_;
 783   return Reference(elem, byte_width_, packed_type);
 784 }
 785
 786 inline Reference TypedVector::operator[](size_t i) const {
 787   auto len = size();
 788   if (i >= len) return Reference(nullptr, 1, NullPackedType());
 789   auto elem = data_ + i * byte_width_;
 790   return Reference(elem, byte_width_, 1, type_);
 791 }
 792
 793 inline Reference FixedTypedVector::operator[](size_t i) const {
 794   if (i >= len_) return Reference(nullptr, 1, NullPackedType());
 795   auto elem = data_ + i * byte_width_;
 796   return Reference(elem, byte_width_, 1, type_);
 797 }
 798
 799 template<typename T> int KeyCompare(const void *key, const void *elem) {
 800   auto str_elem = reinterpret_cast<const char *>(
 801       Indirect<T>(reinterpret_cast<const uint8_t *>(elem)));
 802   auto skey = reinterpret_cast<const char *>(key);
 803   return strcmp(skey, str_elem);
 804 }
 805
 806 inline Reference Map::operator[](const char *key) const {
 807   auto keys = Keys();
 808   // We can't pass keys.byte_width_ to the comparison function, so we have
 809   // to pick the right one ahead of time.
 810   int (*comp)(const void *, const void *) = nullptr;
 811   switch (keys.byte_width_) {
 812     case 1: comp = KeyCompare<uint8_t>; break;
 813     case 2: comp = KeyCompare<uint16_t>; break;
 814     case 4: comp = KeyCompare<uint32_t>; break;
 815     case 8: comp = KeyCompare<uint64_t>; break;
 816   }
 817   auto res = std::bsearch(key, keys.data_, keys.size(), keys.byte_width_, comp);
 818   if (!res) return Reference(nullptr, 1, NullPackedType());
 819   auto i = (reinterpret_cast<uint8_t *>(res) - keys.data_) / keys.byte_width_;
 820   return (*static_cast<const Vector *>(this))[i];
 821 }
 822
 823 inline Reference Map::operator[](const std::string &key) const {
 824   return (*this)[key.c_str()];
 825 }
 826
 827 inline Reference GetRoot(const uint8_t *buffer, size_t size) {
 828   // See Finish() below for the serialization counterpart of this.
 829   // The root starts at the end of the buffer, so we parse backwards from there.
 830   auto end = buffer + size;
 831   auto byte_width = *--end;
 832   auto packed_type = *--end;
 833   end -= byte_width;  // The root data item.
 834   return Reference(end, byte_width, packed_type);
 835 }
 836
 837 inline Reference GetRoot(const std::vector<uint8_t> &buffer) {
 838   return GetRoot(flatbuffers::vector_data(buffer), buffer.size());
 839 }
 840
 841 // Flags that configure how the Builder behaves.
 842 // The "Share" flags determine if the Builder automatically tries to pool
 843 // this type. Pooling can reduce the size of serialized data if there are
 844 // multiple maps of the same kind, at the expense of slightly slower
 845 // serialization (the cost of lookups) and more memory use (std::set).
 846 // By default this is on for keys, but off for strings.
 847 // Turn keys off if you have e.g. only one map.
 848 // Turn strings on if you expect many non-unique string values.
 849 // Additionally, sharing key vectors can save space if you have maps with
 850 // identical field populations.
 851 enum BuilderFlag {
 852   BUILDER_FLAG_NONE = 0,
 853   BUILDER_FLAG_SHARE_KEYS = 1,
 854   BUILDER_FLAG_SHARE_STRINGS = 2,
 855   BUILDER_FLAG_SHARE_KEYS_AND_STRINGS = 3,
 856   BUILDER_FLAG_SHARE_KEY_VECTORS = 4,
 857   BUILDER_FLAG_SHARE_ALL = 7,
 858 };
 859
 860 class Builder FLATBUFFERS_FINAL_CLASS {
 861  public:
 862   Builder(size_t initial_size = 256,
 863           BuilderFlag flags = BUILDER_FLAG_SHARE_KEYS)
 864       : buf_(initial_size),
 865         finished_(false),
 866         flags_(flags),
 867         force_min_bit_width_(BIT_WIDTH_8),
 868         key_pool(KeyOffsetCompare(buf_)),
 869         string_pool(StringOffsetCompare(buf_)) {
 870     buf_.clear();
 871   }
 872
 873   /// @brief Get the serialized buffer (after you call `Finish()`).
 874   /// @return Returns a vector owned by this class.
 875   const std::vector<uint8_t> &GetBuffer() const {
 876     Finished();
 877     return buf_;
 878   }
 879
 880   // Size of the buffer. Does not include unfinished values.
 881   size_t GetSize() const { return buf_.size(); }
 882
 883   // Reset all state so we can re-use the buffer.
 884   void Clear() {
 885     buf_.clear();
 886     stack_.clear();
 887     finished_ = false;
 888     // flags_ remains as-is;
 889     force_min_bit_width_ = BIT_WIDTH_8;
 890     key_pool.clear();
 891     string_pool.clear();
 892   }
 893
 894   // All value constructing functions below have two versions: one that
 895   // takes a key (for placement inside a map) and one that doesn't (for inside
 896   // vectors and elsewhere).
 897
 898   void Null() { stack_.push_back(Value()); }
 899   void Null(const char *key) {
 900     Key(key);
 901     Null();
 902   }
 903
 904   void Int(int64_t i) { stack_.push_back(Value(i, FBT_INT, WidthI(i))); }
 905   void Int(const char *key, int64_t i) {
 906     Key(key);
 907     Int(i);
 908   }
 909
 910   void UInt(uint64_t u) { stack_.push_back(Value(u, FBT_UINT, WidthU(u))); }
 911   void UInt(const char *key, uint64_t u) {
 912     Key(key);
 913     UInt(u);
 914   }
 915
 916   void Float(float f) { stack_.push_back(Value(f)); }
 917   void Float(const char *key, float f) {
 918     Key(key);
 919     Float(f);
 920   }
 921
 922   void Double(double f) { stack_.push_back(Value(f)); }
 923   void Double(const char *key, double d) {
 924     Key(key);
 925     Double(d);
 926   }
 927
 928   void Bool(bool b) { stack_.push_back(Value(b)); }
 929   void Bool(const char *key, bool b) {
 930     Key(key);
 931     Bool(b);
 932   }
 933
 934   void IndirectInt(int64_t i) { PushIndirect(i, FBT_INDIRECT_INT, WidthI(i)); }
 935   void IndirectInt(const char *key, int64_t i) {
 936     Key(key);
 937     IndirectInt(i);
 938   }
 939
 940   void IndirectUInt(uint64_t u) {
 941     PushIndirect(u, FBT_INDIRECT_UINT, WidthU(u));
 942   }
 943   void IndirectUInt(const char *key, uint64_t u) {
 944     Key(key);
 945     IndirectUInt(u);
 946   }
 947
 948   void IndirectFloat(float f) {
 949     PushIndirect(f, FBT_INDIRECT_FLOAT, BIT_WIDTH_32);
 950   }
 951   void IndirectFloat(const char *key, float f) {
 952     Key(key);
 953     IndirectFloat(f);
 954   }
 955
 956   void IndirectDouble(double f) {
 957     PushIndirect(f, FBT_INDIRECT_FLOAT, WidthF(f));
 958   }
 959   void IndirectDouble(const char *key, double d) {
 960     Key(key);
 961     IndirectDouble(d);
 962   }
 963
 964   size_t Key(const char *str, size_t len) {
 965     auto sloc = buf_.size();
 966     WriteBytes(str, len + 1);
 967     if (flags_ & BUILDER_FLAG_SHARE_KEYS) {
 968       auto it = key_pool.find(sloc);
 969       if (it != key_pool.end()) {
 970         // Already in the buffer. Remove key we just serialized, and use
 971         // existing offset instead.
 972         buf_.resize(sloc);
 973         sloc = *it;
 974       } else {
 975         key_pool.insert(sloc);
 976       }
 977     }
 978     stack_.push_back(Value(static_cast<uint64_t>(sloc), FBT_KEY, BIT_WIDTH_8));
 979     return sloc;
 980   }
 981
 982   size_t Key(const char *str) { return Key(str, strlen(str)); }
 983   size_t Key(const std::string &str) { return Key(str.c_str(), str.size()); }
 984
 985   size_t String(const char *str, size_t len) {
 986     auto reset_to = buf_.size();
 987     auto sloc = CreateBlob(str, len, 1, FBT_STRING);
 988     if (flags_ & BUILDER_FLAG_SHARE_STRINGS) {
 989       StringOffset so(sloc, len);
 990       auto it = string_pool.find(so);
 991       if (it != string_pool.end()) {
 992         // Already in the buffer. Remove string we just serialized, and use
 993         // existing offset instead.
 994         buf_.resize(reset_to);
 995         sloc = it->first;
 996         stack_.back().u_ = sloc;
 997       } else {
 998         string_pool.insert(so);
 999       }
1000     }
1001     return sloc;
1002   }
1003   size_t String(const char *str) { return String(str, strlen(str)); }
1004   size_t String(const std::string &str) {
1005     return String(str.c_str(), str.size());
1006   }
1007   void String(const flexbuffers::String &str) {
1008     String(str.c_str(), str.length());
1009   }
1010
1011   void String(const char *key, const char *str) {
1012     Key(key);
1013     String(str);
1014   }
1015   void String(const char *key, const std::string &str) {
1016     Key(key);
1017     String(str);
1018   }
1019   void String(const char *key, const flexbuffers::String &str) {
1020     Key(key);
1021     String(str);
1022   }
1023
1024   size_t Blob(const void *data, size_t len) {
1025     return CreateBlob(data, len, 0, FBT_BLOB);
1026   }
1027   size_t Blob(const std::vector<uint8_t> &v) {
1028     return CreateBlob(flatbuffers::vector_data(v), v.size(), 0, FBT_BLOB);
1029   }
1030
1031   // TODO(wvo): support all the FlexBuffer types (like flexbuffers::String),
1032   // e.g. Vector etc. Also in overloaded versions.
1033   // Also some FlatBuffers types?
1034
1035   size_t StartVector() { return stack_.size(); }
1036   size_t StartVector(const char *key) {
1037     Key(key);
1038     return stack_.size();
1039   }
1040   size_t StartMap() { return stack_.size(); }
1041   size_t StartMap(const char *key) {
1042     Key(key);
1043     return stack_.size();
1044   }
1045
1046   // TODO(wvo): allow this to specify an aligment greater than the natural
1047   // alignment.
1048   size_t EndVector(size_t start, bool typed, bool fixed) {
1049     auto vec = CreateVector(start, stack_.size() - start, 1, typed, fixed);
1050     // Remove temp elements and return vector.
1051     stack_.resize(start);
1052     stack_.push_back(vec);
1053     return static_cast<size_t>(vec.u_);
1054   }
1055
1056   size_t EndMap(size_t start) {
1057     // We should have interleaved keys and values on the stack.
1058     // Make sure it is an even number:
1059     auto len = stack_.size() - start;
1060     FLATBUFFERS_ASSERT(!(len & 1));
1061     len /= 2;
1062     // Make sure keys are all strings:
1063     for (auto key = start; key < stack_.size(); key += 2) {
1064       FLATBUFFERS_ASSERT(stack_[key].type_ == FBT_KEY);
1065     }
1066     // Now sort values, so later we can do a binary search lookup.
1067     // We want to sort 2 array elements at a time.
1068     struct TwoValue {
1069       Value key;
1070       Value val;
1071     };
1072     // TODO(wvo): strict aliasing?
1073     // TODO(wvo): allow the caller to indicate the data is already sorted
1074     // for maximum efficiency? With an assert to check sortedness to make sure
1075     // we're not breaking binary search.
1076     // Or, we can track if the map is sorted as keys are added which would be
1077     // be quite cheap (cheaper than checking it here), so we can skip this
1078     // step automatically when appliccable, and encourage people to write in
1079     // sorted fashion.
1080     // std::sort is typically already a lot faster on sorted data though.
1081     auto dict =
1082         reinterpret_cast<TwoValue *>(flatbuffers::vector_data(stack_) + start);
1083     std::sort(dict, dict + len,
1084               [&](const TwoValue &a, const TwoValue &b) -> bool {
1085                 auto as = reinterpret_cast<const char *>(
1086                     flatbuffers::vector_data(buf_) + a.key.u_);
1087                 auto bs = reinterpret_cast<const char *>(
1088                     flatbuffers::vector_data(buf_) + b.key.u_);
1089                 auto comp = strcmp(as, bs);
1090                 // If this assertion hits, you've added two keys with the same
1091                 // value to this map.
1092                 // TODO: Have to check for pointer equality, as some sort
1093                 // implementation apparently call this function with the same
1094                 // element?? Why?
1095                 FLATBUFFERS_ASSERT(comp || &a == &b);
1096                 return comp < 0;
1097               });
1098     // First create a vector out of all keys.
1099     // TODO(wvo): if kBuilderFlagShareKeyVectors is true, see if we can share
1100     // the first vector.
1101     auto keys = CreateVector(start, len, 2, true, false);
1102     auto vec = CreateVector(start + 1, len, 2, false, false, &keys);
1103     // Remove temp elements and return map.
1104     stack_.resize(start);
1105     stack_.push_back(vec);
1106     return static_cast<size_t>(vec.u_);
1107   }
1108
1109   template<typename F> size_t Vector(F f) {
1110     auto start = StartVector();
1111     f();
1112     return EndVector(start, false, false);
1113   }
1114   template<typename F, typename T> size_t Vector(F f, T &state) {
1115     auto start = StartVector();
1116     f(state);
1117     return EndVector(start, false, false);
1118   }
1119   template<typename F> size_t Vector(const char *key, F f) {
1120     auto start = StartVector(key);
1121     f();
1122     return EndVector(start, false, false);
1123   }
1124   template<typename F, typename T>
1125   size_t Vector(const char *key, F f, T &state) {
1126     auto start = StartVector(key);
1127     f(state);
1128     return EndVector(start, false, false);
1129   }
1130
1131   template<typename T> void Vector(const T *elems, size_t len) {
1132     if (flatbuffers::is_scalar<T>::value) {
1133       // This path should be a lot quicker and use less space.
1134       ScalarVector(elems, len, false);
1135     } else {
1136       auto start = StartVector();
1137       for (size_t i = 0; i < len; i++) Add(elems[i]);
1138       EndVector(start, false, false);
1139     }
1140   }
1141   template<typename T>
1142   void Vector(const char *key, const T *elems, size_t len) {
1143     Key(key);
1144     Vector(elems, len);
1145   }
1146   template<typename T> void Vector(const std::vector<T> &vec) {
1147     Vector(flatbuffers::vector_data(vec), vec.size());
1148   }
1149
1150   template<typename F> size_t TypedVector(F f) {
1151     auto start = StartVector();
1152     f();
1153     return EndVector(start, true, false);
1154   }
1155   template<typename F, typename T> size_t TypedVector(F f, T &state) {
1156     auto start = StartVector();
1157     f(state);
1158     return EndVector(start, true, false);
1159   }
1160   template<typename F> size_t TypedVector(const char *key, F f) {
1161     auto start = StartVector(key);
1162     f();
1163     return EndVector(start, true, false);
1164   }
1165   template<typename F, typename T>
1166   size_t TypedVector(const char *key, F f, T &state) {
1167     auto start = StartVector(key);
1168     f(state);
1169     return EndVector(start, true, false);
1170   }
1171
1172   template<typename T> size_t FixedTypedVector(const T *elems, size_t len) {
1173     // We only support a few fixed vector lengths. Anything bigger use a
1174     // regular typed vector.
1175     FLATBUFFERS_ASSERT(len >= 2 && len <= 4);
1176     // And only scalar values.
1177     static_assert(flatbuffers::is_scalar<T>::value, "Unrelated types");
1178     return ScalarVector(elems, len, true);
1179   }
1180
1181   template<typename T>
1182   size_t FixedTypedVector(const char *key, const T *elems, size_t len) {
1183     Key(key);
1184     return FixedTypedVector(elems, len);
1185   }
1186
1187   template<typename F> size_t Map(F f) {
1188     auto start = StartMap();
1189     f();
1190     return EndMap(start);
1191   }
1192   template<typename F, typename T> size_t Map(F f, T &state) {
1193     auto start = StartMap();
1194     f(state);
1195     return EndMap(start);
1196   }
1197   template<typename F> size_t Map(const char *key, F f) {
1198     auto start = StartMap(key);
1199     f();
1200     return EndMap(start);
1201   }
1202   template<typename F, typename T> size_t Map(const char *key, F f, T &state) {
1203     auto start = StartMap(key);
1204     f(state);
1205     return EndMap(start);
1206   }
1207   template<typename T> void Map(const std::map<std::string, T> &map) {
1208     auto start = StartMap();
1209     for (auto it = map.begin(); it != map.end(); ++it)
1210       Add(it->first.c_str(), it->second);
1211     EndMap(start);
1212   }
1213
1214   // If you wish to share a value explicitly (a value not shared automatically
1215   // through one of the BUILDER_FLAG_SHARE_* flags) you can do so with these
1216   // functions. Or if you wish to turn those flags off for performance reasons
1217   // and still do some explicit sharing. For example:
1218   // builder.IndirectDouble(M_PI);
1219   // auto id = builder.LastValue();  // Remember where we stored it.
1220   // .. more code goes here ..
1221   // builder.ReuseValue(id);  // Refers to same double by offset.
1222   // LastValue works regardless of wether the value has a key or not.
1223   // Works on any data type.
1224   struct Value;
1225   Value LastValue() { return stack_.back(); }
1226   void ReuseValue(Value v) { stack_.push_back(v); }
1227   void ReuseValue(const char *key, Value v) {
1228     Key(key);
1229     ReuseValue(v);
1230   }
1231
1232   // Overloaded Add that tries to call the correct function above.
1233   void Add(int8_t i) { Int(i); }
1234   void Add(int16_t i) { Int(i); }
1235   void Add(int32_t i) { Int(i); }
1236   void Add(int64_t i) { Int(i); }
1237   void Add(uint8_t u) { UInt(u); }
1238   void Add(uint16_t u) { UInt(u); }
1239   void Add(uint32_t u) { UInt(u); }
1240   void Add(uint64_t u) { UInt(u); }
1241   void Add(float f) { Float(f); }
1242   void Add(double d) { Double(d); }
1243   void Add(bool b) { Bool(b); }
1244   void Add(const char *str) { String(str); }
1245   void Add(const std::string &str) { String(str); }
1246   void Add(const flexbuffers::String &str) { String(str); }
1247
1248   template<typename T> void Add(const std::vector<T> &vec) { Vector(vec); }
1249
1250   template<typename T> void Add(const char *key, const T &t) {
1251     Key(key);
1252     Add(t);
1253   }
1254
1255   template<typename T> void Add(const std::map<std::string, T> &map) {
1256     Map(map);
1257   }
1258
1259   template<typename T> void operator+=(const T &t) { Add(t); }
1260
1261   // This function is useful in combination with the Mutate* functions above.
1262   // It forces elements of vectors and maps to have a minimum size, such that
1263   // they can later be updated without failing.
1264   // Call with no arguments to reset.
1265   void ForceMinimumBitWidth(BitWidth bw = BIT_WIDTH_8) {
1266     force_min_bit_width_ = bw;
1267   }
1268
1269   void Finish() {
1270     // If you hit this assert, you likely have objects that were never included
1271     // in a parent. You need to have exactly one root to finish a buffer.
1272     // Check your Start/End calls are matched, and all objects are inside
1273     // some other object.
1274     FLATBUFFERS_ASSERT(stack_.size() == 1);
1275
1276     // Write root value.
1277     auto byte_width = Align(stack_[0].ElemWidth(buf_.size(), 0));
1278     WriteAny(stack_[0], byte_width);
1279     // Write root type.
1280     Write(stack_[0].StoredPackedType(), 1);
1281     // Write root size. Normally determined by parent, but root has no parent :)
1282     Write(byte_width, 1);
1283
1284     finished_ = true;
1285   }
1286
1287  private:
1288   void Finished() const {
1289     // If you get this assert, you're attempting to get access a buffer
1290     // which hasn't been finished yet. Be sure to call
1291     // Builder::Finish with your root object.
1292     FLATBUFFERS_ASSERT(finished_);
1293   }
1294
1295   // Align to prepare for writing a scalar with a certain size.
1296   uint8_t Align(BitWidth alignment) {
1297     auto byte_width = 1U << alignment;
1298     buf_.insert(buf_.end(), flatbuffers::PaddingBytes(buf_.size(), byte_width),
1299                 0);
1300     return static_cast<uint8_t>(byte_width);
1301   }
1302
1303   void WriteBytes(const void *val, size_t size) {
1304     buf_.insert(buf_.end(), reinterpret_cast<const uint8_t *>(val),
1305                 reinterpret_cast<const uint8_t *>(val) + size);
1306   }
1307
1308   template<typename T> void Write(T val, size_t byte_width) {
1309     FLATBUFFERS_ASSERT(sizeof(T) >= byte_width);
1310     val = flatbuffers::EndianScalar(val);
1311     WriteBytes(&val, byte_width);
1312   }
1313
1314   void WriteDouble(double f, uint8_t byte_width) {
1315     switch (byte_width) {
1316       case 8: Write(f, byte_width); break;
1317       case 4: Write(static_cast<float>(f), byte_width); break;
1318       // case 2: Write(static_cast<half>(f), byte_width); break;
1319       // case 1: Write(static_cast<quarter>(f), byte_width); break;
1320       default: FLATBUFFERS_ASSERT(0);
1321     }
1322   }
1323
1324   void WriteOffset(uint64_t o, uint8_t byte_width) {
1325     auto reloff = buf_.size() - o;
1326     FLATBUFFERS_ASSERT(byte_width == 8 || reloff < 1ULL << (byte_width * 8));
1327     Write(reloff, byte_width);
1328   }
1329
1330   template<typename T> void PushIndirect(T val, Type type, BitWidth bit_width) {
1331     auto byte_width = Align(bit_width);
1332     auto iloc = buf_.size();
1333     Write(val, byte_width);
1334     stack_.push_back(Value(static_cast<uint64_t>(iloc), type, bit_width));
1335   }
1336
1337   static BitWidth WidthB(size_t byte_width) {
1338     switch (byte_width) {
1339       case 1: return BIT_WIDTH_8;
1340       case 2: return BIT_WIDTH_16;
1341       case 4: return BIT_WIDTH_32;
1342       case 8: return BIT_WIDTH_64;
1343       default: FLATBUFFERS_ASSERT(false); return BIT_WIDTH_64;
1344     }
1345   }
1346
1347   template<typename T> static Type GetScalarType() {
1348     static_assert(flatbuffers::is_scalar<T>::value, "Unrelated types");
1349     return flatbuffers::is_floating_point<T>::value
1350                ? FBT_FLOAT
1351                : flatbuffers::is_same<T, bool>::value
1352                      ? FBT_BOOL
1353                      : (flatbuffers::is_unsigned<T>::value ? FBT_UINT
1354                                                            : FBT_INT);
1355   }
1356
1357  public:
1358   // This was really intended to be private, except for LastValue/ReuseValue.
1359   struct Value {
1360     union {
1361       int64_t i_;
1362       uint64_t u_;
1363       double f_;
1364     };
1365
1366     Type type_;
1367
1368     // For scalars: of itself, for vector: of its elements, for string: length.
1369     BitWidth min_bit_width_;
1370
1371     Value() : i_(0), type_(FBT_NULL), min_bit_width_(BIT_WIDTH_8) {}
1372
1373     Value(bool b)
1374         : u_(static_cast<uint64_t>(b)),
1375           type_(FBT_BOOL),
1376           min_bit_width_(BIT_WIDTH_8) {}
1377
1378     Value(int64_t i, Type t, BitWidth bw)
1379         : i_(i), type_(t), min_bit_width_(bw) {}
1380     Value(uint64_t u, Type t, BitWidth bw)
1381         : u_(u), type_(t), min_bit_width_(bw) {}
1382
1383     Value(float f) : f_(f), type_(FBT_FLOAT), min_bit_width_(BIT_WIDTH_32) {}
1384     Value(double f) : f_(f), type_(FBT_FLOAT), min_bit_width_(WidthF(f)) {}
1385
1386     uint8_t StoredPackedType(BitWidth parent_bit_width_ = BIT_WIDTH_8) const {
1387       return PackedType(StoredWidth(parent_bit_width_), type_);
1388     }
1389
1390     BitWidth ElemWidth(size_t buf_size, size_t elem_index) const {
1391       if (IsInline(type_)) {
1392         return min_bit_width_;
1393       } else {
1394         // We have an absolute offset, but want to store a relative offset
1395         // elem_index elements beyond the current buffer end. Since whether
1396         // the relative offset fits in a certain byte_width depends on
1397         // the size of the elements before it (and their alignment), we have
1398         // to test for each size in turn.
1399         for (size_t byte_width = 1;
1400              byte_width <= sizeof(flatbuffers::largest_scalar_t);
1401              byte_width *= 2) {
1402           // Where are we going to write this offset?
1403           auto offset_loc = buf_size +
1404                             flatbuffers::PaddingBytes(buf_size, byte_width) +
1405                             elem_index * byte_width;
1406           // Compute relative offset.
1407           auto offset = offset_loc - u_;
1408           // Does it fit?
1409           auto bit_width = WidthU(offset);
1410           if (static_cast<size_t>(static_cast<size_t>(1U) << bit_width) ==
1411               byte_width)
1412             return bit_width;
1413         }
1414         FLATBUFFERS_ASSERT(false);  // Must match one of the sizes above.
1415         return BIT_WIDTH_64;
1416       }
1417     }
1418
1419     BitWidth StoredWidth(BitWidth parent_bit_width_ = BIT_WIDTH_8) const {
1420       if (IsInline(type_)) {
1421         return (std::max)(min_bit_width_, parent_bit_width_);
1422       } else {
1423         return min_bit_width_;
1424       }
1425     }
1426   };
1427
1428  private:
1429   void WriteAny(const Value &val, uint8_t byte_width) {
1430     switch (val.type_) {
1431       case FBT_NULL:
1432       case FBT_INT: Write(val.i_, byte_width); break;
1433       case FBT_BOOL:
1434       case FBT_UINT: Write(val.u_, byte_width); break;
1435       case FBT_FLOAT: WriteDouble(val.f_, byte_width); break;
1436       default: WriteOffset(val.u_, byte_width); break;
1437     }
1438   }
1439
1440   size_t CreateBlob(const void *data, size_t len, size_t trailing, Type type) {
1441     auto bit_width = WidthU(len);
1442     auto byte_width = Align(bit_width);
1443     Write<uint64_t>(len, byte_width);
1444     auto sloc = buf_.size();
1445     WriteBytes(data, len + trailing);
1446     stack_.push_back(Value(static_cast<uint64_t>(sloc), type, bit_width));
1447     return sloc;
1448   }
1449
1450   template<typename T>
1451   size_t ScalarVector(const T *elems, size_t len, bool fixed) {
1452     auto vector_type = GetScalarType<T>();
1453     auto byte_width = sizeof(T);
1454     auto bit_width = WidthB(byte_width);
1455     // If you get this assert, you're trying to write a vector with a size
1456     // field that is bigger than the scalars you're trying to write (e.g. a
1457     // byte vector > 255 elements). For such types, write a "blob" instead.
1458     // TODO: instead of asserting, could write vector with larger elements
1459     // instead, though that would be wasteful.
1460     FLATBUFFERS_ASSERT(WidthU(len) <= bit_width);
1461     if (!fixed) Write<uint64_t>(len, byte_width);
1462     auto vloc = buf_.size();
1463     for (size_t i = 0; i < len; i++) Write(elems[i], byte_width);
1464     stack_.push_back(Value(static_cast<uint64_t>(vloc),
1465                            ToTypedVector(vector_type, fixed ? len : 0),
1466                            bit_width));
1467     return vloc;
1468   }
1469
1470   Value CreateVector(size_t start, size_t vec_len, size_t step, bool typed,
1471                      bool fixed, const Value *keys = nullptr) {
1472     FLATBUFFERS_ASSERT(
1473         !fixed ||
1474         typed);  // typed=false, fixed=true combination is not supported.
1475     // Figure out smallest bit width we can store this vector with.
1476     auto bit_width = (std::max)(force_min_bit_width_, WidthU(vec_len));
1477     auto prefix_elems = 1;
1478     if (keys) {
1479       // If this vector is part of a map, we will pre-fix an offset to the keys
1480       // to this vector.
1481       bit_width = (std::max)(bit_width, keys->ElemWidth(buf_.size(), 0));
1482       prefix_elems += 2;
1483     }
1484     Type vector_type = FBT_KEY;
1485     // Check bit widths and types for all elements.
1486     for (size_t i = start; i < stack_.size(); i += step) {
1487       auto elem_width = stack_[i].ElemWidth(buf_.size(), i + prefix_elems);
1488       bit_width = (std::max)(bit_width, elem_width);
1489       if (typed) {
1490         if (i == start) {
1491           vector_type = stack_[i].type_;
1492         } else {
1493           // If you get this assert, you are writing a typed vector with
1494           // elements that are not all the same type.
1495           FLATBUFFERS_ASSERT(vector_type == stack_[i].type_);
1496         }
1497       }
1498     }
1499     // If you get this assert, your fixed types are not one of:
1500     // Int / UInt / Float / Key.
1501     FLATBUFFERS_ASSERT(!fixed || IsTypedVectorElementType(vector_type));
1502     auto byte_width = Align(bit_width);
1503     // Write vector. First the keys width/offset if available, and size.
1504     if (keys) {
1505       WriteOffset(keys->u_, byte_width);
1506       Write<uint64_t>(1ULL << keys->min_bit_width_, byte_width);
1507     }
1508     if (!fixed) Write<uint64_t>(vec_len, byte_width);
1509     // Then the actual data.
1510     auto vloc = buf_.size();
1511     for (size_t i = start; i < stack_.size(); i += step) {
1512       WriteAny(stack_[i], byte_width);
1513     }
1514     // Then the types.
1515     if (!typed) {
1516       for (size_t i = start; i < stack_.size(); i += step) {
1517         buf_.push_back(stack_[i].StoredPackedType(bit_width));
1518       }
1519     }
1520     return Value(static_cast<uint64_t>(vloc),
1521                  keys ? FBT_MAP
1522                       : (typed ? ToTypedVector(vector_type, fixed ? vec_len : 0)
1523                                : FBT_VECTOR),
1524                  bit_width);
1525   }
1526
1527   // You shouldn't really be copying instances of this class.
1528   Builder(const Builder &);
1529   Builder &operator=(const Builder &);
1530
1531   std::vector<uint8_t> buf_;
1532   std::vector<Value> stack_;
1533
1534   bool finished_;
1535
1536   BuilderFlag flags_;
1537
1538   BitWidth force_min_bit_width_;
1539
1540   struct KeyOffsetCompare {
1541     explicit KeyOffsetCompare(const std::vector<uint8_t> &buf) : buf_(&buf) {}
1542     bool operator()(size_t a, size_t b) const {
1543       auto stra =
1544           reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + a);
1545       auto strb =
1546           reinterpret_cast<const char *>(flatbuffers::vector_data(*buf_) + b);
1547       return strcmp(stra, strb) < 0;
1548     }
1549     const std::vector<uint8_t> *buf_;
1550   };
1551
1552   typedef std::pair<size_t, size_t> StringOffset;
1553   struct StringOffsetCompare {
1554     explicit StringOffsetCompare(const std::vector<uint8_t> &buf)
1555         : buf_(&buf) {}
1556     bool operator()(const StringOffset &a, const StringOffset &b) const {
1557       auto stra = reinterpret_cast<const char *>(
1558           flatbuffers::vector_data(*buf_) + a.first);
1559       auto strb = reinterpret_cast<const char *>(
1560           flatbuffers::vector_data(*buf_) + b.first);
1561       return strncmp(stra, strb, (std::min)(a.second, b.second) + 1) < 0;
1562     }
1563     const std::vector<uint8_t> *buf_;
1564   };
1565
1566   typedef std::set<size_t, KeyOffsetCompare> KeyOffsetMap;
1567   typedef std::set<StringOffset, StringOffsetCompare> StringOffsetMap;
1568
1569   KeyOffsetMap key_pool;
1570   StringOffsetMap string_pool;
1571 };
1572
1573 }  // namespace flexbuffers
1574
1575 #if defined(_MSC_VER)
1576 #  pragma warning(pop)
1577 #endif
1578
1579 #endif  // FLATBUFFERS_FLEXBUFFERS_H_