idl_parser.cpp

/*
 * Copyright 2014 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.
 */

#include <algorithm>
#include <list>

#ifdef _WIN32
#if !defined(_USE_MATH_DEFINES)
#define _USE_MATH_DEFINES  // For M_PI.
#endif                     // !defined(_USE_MATH_DEFINES)
#endif                     // _WIN32

#include <math.h>

#include "flatbuffers/idl.h"
#include "flatbuffers/util.h"

namespace flatbuffers {

const char *const kTypeNames[] = {
  #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, PTYPE) \
    IDLTYPE,
    FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
  #undef FLATBUFFERS_TD
  nullptr
};

const char kTypeSizes[] = {
  #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, PTYPE) \
      sizeof(CTYPE),
    FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
  #undef FLATBUFFERS_TD
};

// The enums in the reflection schema should match the ones we use internally.
// Compare the last element to check if these go out of sync.
static_assert(BASE_TYPE_UNION ==
              static_cast<BaseType>(reflection::Union),
              "enums don't match");

// Any parsing calls have to be wrapped in this macro, which automates
// handling of recursive error checking a bit. It will check the received
// CheckedError object, and return straight away on error.
#define ECHECK(call) { auto ce = (call); if (ce.Check()) return ce; }

// These two functions are called hundreds of times below, so define a short
// form:
#define NEXT() ECHECK(Next())
#define EXPECT(tok) ECHECK(Expect(tok))

static bool ValidateUTF8(const std::string &str) {
  const char *s = &str[0];
  const char * const sEnd = s + str.length();
  while (s < sEnd) {
    if (FromUTF8(&s) < 0) {
      return false;
    }
  }
  return true;
}

CheckedError Parser::Error(const std::string &msg) {
  error_ = file_being_parsed_.length() ? AbsolutePath(file_being_parsed_) : "";
  #ifdef _WIN32
    error_ += "(" + NumToString(line_) + ")";  // MSVC alike
  #else
    if (file_being_parsed_.length()) error_ += ":";
    error_ += NumToString(line_) + ":0";  // gcc alike
  #endif
  error_ += ": error: " + msg;
  return CheckedError(true);
}

inline CheckedError NoError() { return CheckedError(false); }

// Ensure that integer values we parse fit inside the declared integer type.
CheckedError Parser::CheckBitsFit(int64_t val, size_t bits) {
  // Left-shifting a 64-bit value by 64 bits or more is undefined
  // behavior (C99 6.5.7), so check *before* we shift.
  if (bits < 64) {
    // Bits we allow to be used.
    auto mask = static_cast<int64_t>((1ull << bits) - 1);
    if ((val & ~mask) != 0 &&  // Positive or unsigned.
        (val |  mask) != -1)   // Negative.
      return Error("constant does not fit in a " + NumToString(bits) +
                   "-bit field");
  }
  return NoError();
}

// atot: templated version of atoi/atof: convert a string to an instance of T.
template<typename T> inline CheckedError atot(const char *s, Parser &parser,
                                              T *val) {
  int64_t i = StringToInt(s);
  ECHECK(parser.CheckBitsFit(i, sizeof(T) * 8));
  *val = (T)i;
  return NoError();
}
template<> inline CheckedError atot<bool>(const char *s, Parser &parser,
                                          bool *val) {
  (void)parser;
  *val = 0 != atoi(s);
  return NoError();
}
template<> inline CheckedError atot<float>(const char *s, Parser &parser,
                                           float *val) {
  (void)parser;
  *val = static_cast<float>(strtod(s, nullptr));
  return NoError();
}
template<> inline CheckedError atot<double>(const char *s, Parser &parser,
                                            double *val) {
  (void)parser;
  *val = strtod(s, nullptr);
  return NoError();
}

template<> inline CheckedError atot<Offset<void>>(const char *s, Parser &parser,
                                                  Offset<void> *val) {
  (void)parser;
  *val = Offset<void>(atoi(s));
  return NoError();
}

std::string Namespace::GetFullyQualifiedName(const std::string &name,
                                             size_t max_components) const {
  // Early exit if we don't have a defined namespace.
  if (components.size() == 0 || !max_components) {
    return name;
  }
  std::stringstream stream;
  for (size_t i = 0; i < std::min(components.size(), max_components);
       i++) {
    if (i) {
      stream << ".";
    }
    stream << components[i];
  }

  stream << "." << name;
  return stream.str();
}



// Declare tokens we'll use. Single character tokens are represented by their
// ascii character code (e.g. '{'), others above 256.
#define FLATBUFFERS_GEN_TOKENS(TD) \
  TD(Eof, 256, "end of file") \
  TD(StringConstant, 257, "string constant") \
  TD(IntegerConstant, 258, "integer constant") \
  TD(FloatConstant, 259, "float constant") \
  TD(Identifier, 260, "identifier") \
  TD(Table, 261, "table") \
  TD(Struct, 262, "struct") \
  TD(Enum, 263, "enum") \
  TD(Union, 264, "union") \
  TD(NameSpace, 265, "namespace") \
  TD(RootType, 266, "root_type") \
  TD(FileIdentifier, 267, "file_identifier") \
  TD(FileExtension, 268, "file_extension") \
  TD(Include, 269, "include") \
  TD(Attribute, 270, "attribute") \
  TD(Null, 271, "null") \
  TD(Service, 272, "rpc_service")
#ifdef __GNUC__
__extension__  // Stop GCC complaining about trailing comma with -Wpendantic.
#endif
enum {
  #define FLATBUFFERS_TOKEN(NAME, VALUE, STRING) kToken ## NAME = VALUE,
    FLATBUFFERS_GEN_TOKENS(FLATBUFFERS_TOKEN)
  #undef FLATBUFFERS_TOKEN
  #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, PTYPE) \
      kToken ## ENUM,
    FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
  #undef FLATBUFFERS_TD
};

static std::string TokenToString(int t) {
  static const char *tokens[] = {
    #define FLATBUFFERS_TOKEN(NAME, VALUE, STRING) STRING,
      FLATBUFFERS_GEN_TOKENS(FLATBUFFERS_TOKEN)
    #undef FLATBUFFERS_TOKEN
    #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, PTYPE) \
      IDLTYPE,
      FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
    #undef FLATBUFFERS_TD
  };
  if (t < 256) {  // A single ascii char token.
    std::string s;
    s.append(1, static_cast<char>(t));
    return s;
  } else {       // Other tokens.
    return tokens[t - 256];
  }
}

std::string Parser::TokenToStringId(int t) {
  return TokenToString(t) + (t == kTokenIdentifier ? ": " + attribute_ : "");
}

// Parses exactly nibbles worth of hex digits into a number, or error.
CheckedError Parser::ParseHexNum(int nibbles, int64_t *val) {
  for (int i = 0; i < nibbles; i++)
    if (!isxdigit(static_cast<const unsigned char>(cursor_[i])))
      return Error("escape code must be followed by " + NumToString(nibbles) +
                   " hex digits");
  std::string target(cursor_, cursor_ + nibbles);
  *val = StringToUInt(target.c_str(), nullptr, 16);
  cursor_ += nibbles;
  return NoError();
}

CheckedError Parser::SkipByteOrderMark() {
  if (static_cast<unsigned char>(*cursor_) != 0xef) return NoError();
  cursor_++;
  if (static_cast<unsigned char>(*cursor_) != 0xbb) return Error("invalid utf-8 byte order mark");
  cursor_++;
  if (static_cast<unsigned char>(*cursor_) != 0xbf) return Error("invalid utf-8 byte order mark");
  cursor_++;
  return NoError();
}

bool IsIdentifierStart(char c) {
  return isalpha(static_cast<unsigned char>(c)) || c == '_';
}

CheckedError Parser::Next() {
  doc_comment_.clear();
  bool seen_newline = false;
  attribute_.clear();
  for (;;) {
    char c = *cursor_++;
    token_ = c;
    switch (c) {
      case '\0': cursor_--; token_ = kTokenEof; return NoError();
      case ' ': case '\r': case '\t': break;
      case '\n': line_++; seen_newline = true; break;
      case '{': case '}': case '(': case ')': case '[': case ']':
      case ',': case ':': case ';': case '=': return NoError();
      case '.':
        if(!isdigit(static_cast<const unsigned char>(*cursor_))) return NoError();
        return Error("floating point constant can\'t start with \".\"");
      case '\"':
      case '\'': {
        int unicode_high_surrogate = -1;

        while (*cursor_ != c) {
          if (*cursor_ < ' ' && *cursor_ >= 0)
            return Error("illegal character in string constant");
          if (*cursor_ == '\\') {
            cursor_++;
            if (unicode_high_surrogate != -1 &&
                *cursor_ != 'u') {
              return Error(
                "illegal Unicode sequence (unpaired high surrogate)");
            }
            switch (*cursor_) {
              case 'n':  attribute_ += '\n'; cursor_++; break;
              case 't':  attribute_ += '\t'; cursor_++; break;
              case 'r':  attribute_ += '\r'; cursor_++; break;
              case 'b':  attribute_ += '\b'; cursor_++; break;
              case 'f':  attribute_ += '\f'; cursor_++; break;
              case '\"': attribute_ += '\"'; cursor_++; break;
              case '\'': attribute_ += '\''; cursor_++; break;
              case '\\': attribute_ += '\\'; cursor_++; break;
              case '/':  attribute_ += '/';  cursor_++; break;
              case 'x': {  // Not in the JSON standard
                cursor_++;
                int64_t val;
                ECHECK(ParseHexNum(2, &val));
                attribute_ += static_cast<char>(val);
                break;
              }
              case 'u': {
                cursor_++;
                int64_t val;
                ECHECK(ParseHexNum(4, &val));
                if (val >= 0xD800 && val <= 0xDBFF) {
                  if (unicode_high_surrogate != -1) {
                    return Error(
                      "illegal Unicode sequence (multiple high surrogates)");
                  } else {
                    unicode_high_surrogate = static_cast<int>(val);
                  }
                } else if (val >= 0xDC00 && val <= 0xDFFF) {
                  if (unicode_high_surrogate == -1) {
                    return Error(
                      "illegal Unicode sequence (unpaired low surrogate)");
                  } else {
                    int code_point = 0x10000 +
                      ((unicode_high_surrogate & 0x03FF) << 10) +
                      (val & 0x03FF);
                    ToUTF8(code_point, &attribute_);
                    unicode_high_surrogate = -1;
                  }
                } else {
                  if (unicode_high_surrogate != -1) {
                    return Error(
                      "illegal Unicode sequence (unpaired high surrogate)");
                  }
                  ToUTF8(static_cast<int>(val), &attribute_);
                }
                break;
              }
              default: return Error("unknown escape code in string constant");
            }
          } else { // printable chars + UTF-8 bytes
            if (unicode_high_surrogate != -1) {
              return Error(
                "illegal Unicode sequence (unpaired high surrogate)");
            }
            attribute_ += *cursor_++;
          }
        }
        if (unicode_high_surrogate != -1) {
          return Error(
            "illegal Unicode sequence (unpaired high surrogate)");
        }
        cursor_++;
        if (!opts.allow_non_utf8 && !ValidateUTF8(attribute_)) {
          return Error("illegal UTF-8 sequence");
        }
        token_ = kTokenStringConstant;
        return NoError();
      }
      case '/':
        if (*cursor_ == '/') {
          const char *start = ++cursor_;
          while (*cursor_ && *cursor_ != '\n' && *cursor_ != '\r') cursor_++;
          if (*start == '/') {  // documentation comment
            if (cursor_ != source_ && !seen_newline)
              return Error(
                    "a documentation comment should be on a line on its own");
            doc_comment_.push_back(std::string(start + 1, cursor_));
          }
          break;
        } else if (*cursor_ == '*') {
          cursor_++;
          // TODO: make nested.
          while (*cursor_ != '*' || cursor_[1] != '/') {
            if (*cursor_ == '\n') line_++;
            if (!*cursor_) return Error("end of file in comment");
            cursor_++;
          }
          cursor_ += 2;
          break;
        }
        // fall thru
      default:
        if (IsIdentifierStart(c)) {
          // Collect all chars of an identifier:
          const char *start = cursor_ - 1;
          while (isalnum(static_cast<unsigned char>(*cursor_)) ||
                 *cursor_ == '_')
            cursor_++;
          attribute_.append(start, cursor_);
          // First, see if it is a type keyword from the table of types:
          #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, \
            PTYPE) \
            if (attribute_ == IDLTYPE) { \
              token_ = kToken ## ENUM; \
              return NoError(); \
            }
            FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
          #undef FLATBUFFERS_TD
          // If it's a boolean constant keyword, turn those into integers,
          // which simplifies our logic downstream.
          if (attribute_ == "true" || attribute_ == "false") {
            attribute_ = NumToString(attribute_ == "true");
            token_ = kTokenIntegerConstant;
            return NoError();
          }
          // Check for declaration keywords:
          if (attribute_ == "table") {
            token_ = kTokenTable;
            return NoError();
          }
          if (attribute_ == "struct") {
            token_ = kTokenStruct;
            return NoError();
          }
          if (attribute_ == "enum") {
            token_ = kTokenEnum;
            return NoError();
          }
          if (attribute_ == "union") {
            token_ = kTokenUnion;
            return NoError();
          }
          if (attribute_ == "namespace") {
            token_ = kTokenNameSpace;
            return NoError();
          }
          if (attribute_ == "root_type") {
            token_ = kTokenRootType;
            return NoError();
          }
          if (attribute_ == "include") {
            token_ = kTokenInclude;
            return NoError();
          }
          if (attribute_ == "attribute") {
            token_ = kTokenAttribute;
            return NoError();
          }
          if (attribute_ == "file_identifier") {
            token_ = kTokenFileIdentifier;
            return NoError();
          }
          if (attribute_ == "file_extension") {
            token_ = kTokenFileExtension;
            return NoError();
          }
          if (attribute_ == "null") {
            token_ = kTokenNull;
            return NoError();
          }
          if (attribute_ == "rpc_service") {
            token_ = kTokenService;
            return NoError();
          }
          // If not, it is a user-defined identifier:
          token_ = kTokenIdentifier;
          return NoError();
        } else if (isdigit(static_cast<unsigned char>(c)) || c == '-') {
          const char *start = cursor_ - 1;
          if (c == '-' && *cursor_ == '0' && (cursor_[1] == 'x' || cursor_[1] == 'X')) {
            ++start;
            ++cursor_;
            attribute_.append(&c, &c + 1);
            c = '0';
          }
          if (c == '0' && (*cursor_ == 'x' || *cursor_ == 'X')) {
              cursor_++;
              while (isxdigit(static_cast<unsigned char>(*cursor_))) cursor_++;
              attribute_.append(start + 2, cursor_);
              attribute_ = NumToString(StringToUInt(attribute_.c_str(), nullptr, 16));
              token_ = kTokenIntegerConstant;
              return NoError();
          }
          while (isdigit(static_cast<unsigned char>(*cursor_))) cursor_++;
          if (*cursor_ == '.' || *cursor_ == 'e' || *cursor_ == 'E') {
            if (*cursor_ == '.') {
              cursor_++;
              while (isdigit(static_cast<unsigned char>(*cursor_))) cursor_++;
            }
            // See if this float has a scientific notation suffix. Both JSON
            // and C++ (through strtod() we use) have the same format:
            if (*cursor_ == 'e' || *cursor_ == 'E') {
              cursor_++;
              if (*cursor_ == '+' || *cursor_ == '-') cursor_++;
              while (isdigit(static_cast<unsigned char>(*cursor_))) cursor_++;
            }
            token_ = kTokenFloatConstant;
          } else {
            token_ = kTokenIntegerConstant;
          }
          attribute_.append(start, cursor_);
          return NoError();
        }
        std::string ch;
        ch = c;
        if (c < ' ' || c > '~') ch = "code: " + NumToString(c);
        return Error("illegal character: " + ch);
    }
  }
}

// Check if a given token is next.
bool Parser::Is(int t) {
  return t == token_;
}

// Expect a given token to be next, consume it, or error if not present.
CheckedError Parser::Expect(int t) {
  if (t != token_) {
    return Error("expecting: " + TokenToString(t) + " instead got: " +
                 TokenToStringId(token_));
  }
  NEXT();
  return NoError();
}

CheckedError Parser::ParseNamespacing(std::string *id, std::string *last) {
  while (Is('.')) {
    NEXT();
    *id += ".";
    *id += attribute_;
    if (last) *last = attribute_;
    EXPECT(kTokenIdentifier);
  }
  return NoError();
}

EnumDef *Parser::LookupEnum(const std::string &id) {
  // Search thru parent namespaces.
  for (int components = static_cast<int>(namespaces_.back()->components.size());
       components >= 0; components--) {
    auto ed = enums_.Lookup(
                namespaces_.back()->GetFullyQualifiedName(id, components));
    if (ed) return ed;
  }
  return nullptr;
}

CheckedError Parser::ParseTypeIdent(Type &type) {
  std::string id = attribute_;
  EXPECT(kTokenIdentifier);
  ECHECK(ParseNamespacing(&id, nullptr));
  auto enum_def = LookupEnum(id);
  if (enum_def) {
    type = enum_def->underlying_type;
    if (enum_def->is_union) type.base_type = BASE_TYPE_UNION;
  } else {
    type.base_type = BASE_TYPE_STRUCT;
    type.struct_def = LookupCreateStruct(id);
  }
  return NoError();
}

// Parse any IDL type.
CheckedError Parser::ParseType(Type &type) {
  if (token_ >= kTokenBOOL && token_ <= kTokenSTRING) {
    type.base_type = static_cast<BaseType>(token_ - kTokenNONE);
    NEXT();
  } else {
    if (token_ == kTokenIdentifier) {
      ECHECK(ParseTypeIdent(type));
    } else if (token_ == '[') {
      NEXT();
      Type subtype;
      ECHECK(ParseType(subtype));
      if (subtype.base_type == BASE_TYPE_VECTOR) {
        // We could support this, but it will complicate things, and it's
        // easier to work around with a struct around the inner vector.
        return Error(
              "nested vector types not supported (wrap in table first).");
      }
      if (subtype.base_type == BASE_TYPE_UNION) {
        // We could support this if we stored a struct of 2 elements per
        // union element.
        return Error(
              "vector of union types not supported (wrap in table first).");
      }
      type = Type(BASE_TYPE_VECTOR, subtype.struct_def, subtype.enum_def);
      type.element = subtype.base_type;
      EXPECT(']');
    } else {
      return Error("illegal type syntax");
    }
  }
  return NoError();
}

CheckedError Parser::AddField(StructDef &struct_def, const std::string &name,
                              const Type &type, FieldDef **dest) {
  auto &field = *new FieldDef();
  field.value.offset =
    FieldIndexToOffset(static_cast<voffset_t>(struct_def.fields.vec.size()));
  field.name = name;
  field.file = struct_def.file;
  field.value.type = type;
  if (struct_def.fixed) {  // statically compute the field offset
    auto size = InlineSize(type);
    auto alignment = InlineAlignment(type);
    // structs_ need to have a predictable format, so we need to align to
    // the largest scalar
    struct_def.minalign = std::max(struct_def.minalign, alignment);
    struct_def.PadLastField(alignment);
    field.value.offset = static_cast<voffset_t>(struct_def.bytesize);
    struct_def.bytesize += size;
  }
  if (struct_def.fields.Add(name, &field))
    return Error("field already exists: " + name);
  *dest = &field;
  return NoError();
}

CheckedError Parser::ParseField(StructDef &struct_def) {
  std::string name = attribute_;
  std::vector<std::string> dc = doc_comment_;
  EXPECT(kTokenIdentifier);
  EXPECT(':');
  Type type;
  ECHECK(ParseType(type));

  if (struct_def.fixed && !IsScalar(type.base_type) && !IsStruct(type))
    return Error("structs_ may contain only scalar or struct fields");

  FieldDef *typefield = nullptr;
  if (type.base_type == BASE_TYPE_UNION) {
    // For union fields, add a second auto-generated field to hold the type,
    // with a special suffix.
    ECHECK(AddField(struct_def, name + UnionTypeFieldSuffix(),
                    type.enum_def->underlying_type, &typefield));
  }

  FieldDef *field;
  ECHECK(AddField(struct_def, name, type, &field));

  if (token_ == '=') {
    NEXT();
    if (!IsScalar(type.base_type))
      return Error("default values currently only supported for scalars");
    ECHECK(ParseSingleValue(field->value));
  }
  if (IsFloat(field->value.type.base_type)) {
    if (!strpbrk(field->value.constant.c_str(), ".eE"))
      field->value.constant += ".0";
  }

  if (type.enum_def &&
      IsScalar(type.base_type) &&
      !struct_def.fixed &&
      !type.enum_def->attributes.Lookup("bit_flags") &&
      !type.enum_def->ReverseLookup(static_cast<int>(
                         StringToInt(field->value.constant.c_str()))))
    return Error("enum " + type.enum_def->name +
          " does not have a declaration for this field\'s default of " +
          field->value.constant);

  field->doc_comment = dc;
  ECHECK(ParseMetaData(&field->attributes));
  field->deprecated = field->attributes.Lookup("deprecated") != nullptr;
  auto hash_name = field->attributes.Lookup("hash");
  if (hash_name) {
    switch (type.base_type) {
      case BASE_TYPE_INT:
      case BASE_TYPE_UINT: {
        if (FindHashFunction32(hash_name->constant.c_str()) == nullptr)
          return Error("Unknown hashing algorithm for 32 bit types: " +
                hash_name->constant);
        break;
      }
      case BASE_TYPE_LONG:
      case BASE_TYPE_ULONG: {
        if (FindHashFunction64(hash_name->constant.c_str()) == nullptr)
          return Error("Unknown hashing algorithm for 64 bit types: " +
                hash_name->constant);
        break;
      }
      default:
        return Error(
              "only int, uint, long and ulong data types support hashing.");
    }
  }
  auto cpp_type = field->attributes.Lookup("cpp_type");
  if (cpp_type) {
    if (!hash_name)
      return Error("cpp_type can only be used with a hashed field");
  }
  if (field->deprecated && struct_def.fixed)
    return Error("can't deprecate fields in a struct");
  field->required = field->attributes.Lookup("required") != nullptr;
  if (field->required && (struct_def.fixed ||
                         IsScalar(field->value.type.base_type)))
    return Error("only non-scalar fields in tables may be 'required'");
  field->key = field->attributes.Lookup("key") != nullptr;
  if (field->key) {
    if (struct_def.has_key)
      return Error("only one field may be set as 'key'");
    struct_def.has_key = true;
    if (!IsScalar(field->value.type.base_type)) {
      field->required = true;
      if (field->value.type.base_type != BASE_TYPE_STRING)
        return Error("'key' field must be string or scalar type");
    }
  }

  field->native_inline = field->attributes.Lookup("native_inline") != nullptr;
  if (field->native_inline && !IsStruct(field->value.type))
    return Error("native_inline can only be defined on structs'");

  auto nested = field->attributes.Lookup("nested_flatbuffer");
  if (nested) {
    if (nested->type.base_type != BASE_TYPE_STRING)
      return Error(
            "nested_flatbuffer attribute must be a string (the root type)");
    if (field->value.type.base_type != BASE_TYPE_VECTOR ||
        field->value.type.element != BASE_TYPE_UCHAR)
      return Error(
            "nested_flatbuffer attribute may only apply to a vector of ubyte");
    // This will cause an error if the root type of the nested flatbuffer
    // wasn't defined elsewhere.
    LookupCreateStruct(nested->constant);
  }

  if (typefield) {
    // If this field is a union, and it has a manually assigned id,
    // the automatically added type field should have an id as well (of N - 1).
    auto attr = field->attributes.Lookup("id");
    if (attr) {
      auto id = atoi(attr->constant.c_str());
      auto val = new Value();
      val->type = attr->type;
      val->constant = NumToString(id - 1);
      typefield->attributes.Add("id", val);
    }
  }

  EXPECT(';');
  return NoError();
}

CheckedError Parser::ParseAnyValue(Value &val, FieldDef *field,
                                   size_t parent_fieldn,
                                   const StructDef *parent_struct_def) {
  switch (val.type.base_type) {
    case BASE_TYPE_UNION: {
      assert(field);
      std::string constant;
      if (!parent_fieldn ||
          field_stack_.back().second->value.type.base_type != BASE_TYPE_UTYPE) {
        // We haven't seen the type field yet. Sadly a lot of JSON writers
        // output these in alphabetical order, meaning it comes after this
        // value. So we scan past the value to find it, then come back here.
        auto type_name = field->name + UnionTypeFieldSuffix();
        assert(parent_struct_def);
        auto type_field = parent_struct_def->fields.Lookup(type_name);
        assert(type_field);  // Guaranteed by ParseField().
        // Remember where we are in the source file, so we can come back here.
        auto backup = *static_cast<ParserState *>(this);
        ECHECK(SkipAnyJsonValue());  // The table.
        EXPECT(',');
        auto next_name = attribute_;
        if (Is(kTokenStringConstant)) {
          NEXT();
        } else {
          EXPECT(kTokenIdentifier);
        }
        if (next_name != type_name)
          return Error("missing type field after this union value: " +
                       type_name);
        EXPECT(':');
        Value type_val = type_field->value;
        ECHECK(ParseAnyValue(type_val, type_field, 0, nullptr));
        constant = type_val.constant;
        // Got the information we needed, now rewind:
        *static_cast<ParserState *>(this) = backup;
      } else {
        constant = field_stack_.back().first.constant;
      }
      uint8_t enum_idx;
      ECHECK(atot(constant.c_str(), *this, &enum_idx));
      auto enum_val = val.type.enum_def->ReverseLookup(enum_idx);
      if (!enum_val) return Error("illegal type id for: " + field->name);
      ECHECK(ParseTable(*enum_val->struct_def, &val.constant, nullptr));
      break;
    }
    case BASE_TYPE_STRUCT:
      ECHECK(ParseTable(*val.type.struct_def, &val.constant, nullptr));
      break;
    case BASE_TYPE_STRING: {
      auto s = attribute_;
      EXPECT(kTokenStringConstant);
      val.constant = NumToString(builder_.CreateString(s).o);
      break;
    }
    case BASE_TYPE_VECTOR: {
      EXPECT('[');
      uoffset_t off;
      ECHECK(ParseVector(val.type.VectorType(), &off));
      val.constant = NumToString(off);
      break;
    }
    case BASE_TYPE_INT:
    case BASE_TYPE_UINT:
    case BASE_TYPE_LONG:
    case BASE_TYPE_ULONG: {
      if (field && field->attributes.Lookup("hash") &&
          (token_ == kTokenIdentifier || token_ == kTokenStringConstant)) {
        ECHECK(ParseHash(val, field));
      } else {
        ECHECK(ParseSingleValue(val));
      }
      break;
    }
    default:
      ECHECK(ParseSingleValue(val));
      break;
  }
  return NoError();
}

void Parser::SerializeStruct(const StructDef &struct_def, const Value &val) {
  assert(val.constant.length() == struct_def.bytesize);
  builder_.Align(struct_def.minalign);
  builder_.PushBytes(reinterpret_cast<const uint8_t *>(val.constant.c_str()),
                     struct_def.bytesize);
  builder_.AddStructOffset(val.offset, builder_.GetSize());
}

CheckedError Parser::ParseTable(const StructDef &struct_def, std::string *value,
                                uoffset_t *ovalue) {
  EXPECT('{');
  size_t fieldn = 0;
  for (;;) {
    if ((!opts.strict_json || !fieldn) && Is('}')) { NEXT(); break; }
    std::string name = attribute_;
    if (Is(kTokenStringConstant)) {
      NEXT();
    } else {
      EXPECT(opts.strict_json ? kTokenStringConstant : kTokenIdentifier);
    }
    auto field = struct_def.fields.Lookup(name);
    if (!field) {
      if (!opts.skip_unexpected_fields_in_json) {
        return Error("unknown field: " + name);
      } else {
        EXPECT(':');
        ECHECK(SkipAnyJsonValue());
      }
    } else {
      EXPECT(':');
      if (Is(kTokenNull)) {
        NEXT(); // Ignore this field.
      } else {
        Value val = field->value;
        ECHECK(ParseAnyValue(val, field, fieldn, &struct_def));
        size_t i = field_stack_.size();
        // Hardcoded insertion-sort with error-check.
        // If fields are specified in order, then this loop exits immediately.
        for (; i > field_stack_.size() - fieldn; i--) {
          auto existing_field = field_stack_[i - 1].second;
          if (existing_field == field)
            return Error("field set more than once: " + field->name);
          if (existing_field->value.offset < field->value.offset) break;
        }
        field_stack_.insert(field_stack_.begin() + i, std::make_pair(val, field));
        fieldn++;
      }
    }
    if (Is('}')) { NEXT(); break; }
    EXPECT(',');
  }

  if (struct_def.fixed && fieldn != struct_def.fields.vec.size())
    return Error("struct: wrong number of initializers: " + struct_def.name);

  auto start = struct_def.fixed
                 ? builder_.StartStruct(struct_def.minalign)
                 : builder_.StartTable();

  for (size_t size = struct_def.sortbysize ? sizeof(largest_scalar_t) : 1;
       size;
       size /= 2) {
    // Go through elements in reverse, since we're building the data backwards.
    for (auto it = field_stack_.rbegin();
             it != field_stack_.rbegin() + fieldn; ++it) {
      auto &field_value = it->first;
      auto field = it->second;
      if (!struct_def.sortbysize ||
          size == SizeOf(field_value.type.base_type)) {
        switch (field_value.type.base_type) {
          #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, \
            PTYPE) \
            case BASE_TYPE_ ## ENUM: \
              builder_.Pad(field->padding); \
              if (struct_def.fixed) { \
                CTYPE val; \
                ECHECK(atot(field_value.constant.c_str(), *this, &val)); \
                builder_.PushElement(val); \
              } else { \
                CTYPE val, valdef; \
                ECHECK(atot(field_value.constant.c_str(), *this, &val)); \
                ECHECK(atot(field->value.constant.c_str(), *this, &valdef)); \
                builder_.AddElement(field_value.offset, val, valdef); \
              } \
              break;
            FLATBUFFERS_GEN_TYPES_SCALAR(FLATBUFFERS_TD);
          #undef FLATBUFFERS_TD
          #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, \
            PTYPE) \
            case BASE_TYPE_ ## ENUM: \
              builder_.Pad(field->padding); \
              if (IsStruct(field->value.type)) { \
                SerializeStruct(*field->value.type.struct_def, field_value); \
              } else { \
                CTYPE val; \
                ECHECK(atot(field_value.constant.c_str(), *this, &val)); \
                builder_.AddOffset(field_value.offset, val); \
              } \
              break;
            FLATBUFFERS_GEN_TYPES_POINTER(FLATBUFFERS_TD);
          #undef FLATBUFFERS_TD
        }
      }
    }
  }
  for (size_t i = 0; i < fieldn; i++) field_stack_.pop_back();

  if (struct_def.fixed) {
    builder_.ClearOffsets();
    builder_.EndStruct();
    assert(value);
    // Temporarily store this struct in the value string, since it is to
    // be serialized in-place elsewhere.
    value->assign(
          reinterpret_cast<const char *>(builder_.GetCurrentBufferPointer()),
          struct_def.bytesize);
    builder_.PopBytes(struct_def.bytesize);
    assert(!ovalue);
  } else {
    auto val = builder_.EndTable(start,
                          static_cast<voffset_t>(struct_def.fields.vec.size()));
    if (ovalue) *ovalue = val;
    if (value) *value = NumToString(val);
  }
  return NoError();
}

CheckedError Parser::ParseVector(const Type &type, uoffset_t *ovalue) {
  int count = 0;
  for (;;) {
    if ((!opts.strict_json || !count) && Is(']')) { NEXT(); break; }
    Value val;
    val.type = type;
    ECHECK(ParseAnyValue(val, nullptr, 0, nullptr));
    field_stack_.push_back(std::make_pair(val, nullptr));
    count++;
    if (Is(']')) { NEXT(); break; }
    EXPECT(',');
  }

  builder_.StartVector(count * InlineSize(type) / InlineAlignment(type),
                       InlineAlignment(type));
  for (int i = 0; i < count; i++) {
    // start at the back, since we're building the data backwards.
    auto &val = field_stack_.back().first;
    switch (val.type.base_type) {
      #define FLATBUFFERS_TD(ENUM, IDLTYPE, CTYPE, JTYPE, GTYPE, NTYPE, PTYPE) \
        case BASE_TYPE_ ## ENUM: \
          if (IsStruct(val.type)) SerializeStruct(*val.type.struct_def, val); \
          else { \
             CTYPE elem; \
             ECHECK(atot(val.constant.c_str(), *this, &elem)); \
             builder_.PushElement(elem); \
          } \
          break;
        FLATBUFFERS_GEN_TYPES(FLATBUFFERS_TD)
      #undef FLATBUFFERS_TD
    }
    field_stack_.pop_back();
  }

  builder_.ClearOffsets();
  *ovalue = builder_.EndVector(count);
  return NoError();
}

CheckedError Parser::ParseMetaData(SymbolTable<Value> *attributes) {
  if (Is('(')) {
    NEXT();
    for (;;) {
      auto name = attribute_;
      EXPECT(kTokenIdentifier);
      if (known_attributes_.find(name) == known_attributes_.end())
        return Error("user define attributes must be declared before use: " +
                     name);
      auto e = new Value();
      attributes->Add(name, e);
      if (Is(':')) {
        NEXT();
        ECHECK(ParseSingleValue(*e));
      }
      if (Is(')')) { NEXT(); break; }
      EXPECT(',');
    }
  }
  return NoError();
}

CheckedError Parser::TryTypedValue(int dtoken, bool check, Value &e,
                                   BaseType req, bool *destmatch) {
  bool match = dtoken == token_;
  if (match) {
    *destmatch = true;
    e.constant = attribute_;
    if (!check) {
      if (e.type.base_type == BASE_TYPE_NONE) {
        e.type.base_type = req;
      } else {
        return Error(std::string("type mismatch: expecting: ") +
                     kTypeNames[e.type.base_type] +
                     ", found: " +
                     kTypeNames[req]);