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 <iostream>
#include <list>

#include <math.h>

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

namespace flatbuffers {

const double kPi = 3.14159265358979323846;

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

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

// 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;
}

void Parser::Message(const std::string &msg) {
  error_ = file_being_parsed_.length() ? AbsolutePath(file_being_parsed_) : "";
  // clang-format off
  #ifdef _WIN32
    error_ += "(" + NumToString(line_) + ")";  // MSVC alike
  #else
    if (file_being_parsed_.length()) error_ += ":";
    error_ += NumToString(line_) + ":0";  // gcc alike
  #endif
  // clang-format on
  error_ += ": " + msg;
}

void Parser::Warning(const std::string &msg) { Message("warning: " + msg); }

CheckedError Parser::Error(const std::string &msg) {
  Message("error: " + msg);
  return CheckedError(true);
}

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

inline std::string OutOfRangeErrorMsg(int64_t val, const std::string &op,
                                      int64_t limit) {
  const std::string cause = NumToString(val) + op + NumToString(limit);
  return "constant does not fit (" + cause + ")";
}

// Ensure that integer values we parse fit inside the declared integer type.
CheckedError Parser::CheckInRange(int64_t val, int64_t min, int64_t max) {
  if (val < min)
    return Error(OutOfRangeErrorMsg(val, " < ", min));
  else if (val > max)
    return Error(OutOfRangeErrorMsg(val, " > ", max));
  else
    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);
  const int64_t min = flatbuffers::numeric_limits<T>::min();
  const int64_t max = flatbuffers::numeric_limits<T>::max();
  ECHECK(parser.CheckInRange(i, min, max));
  *val = (T)i;
  return NoError();
}
template<>
inline CheckedError atot<uint64_t>(const char *s, Parser &parser,
                                   uint64_t *val) {
  (void)parser;
  *val = StringToUInt(s);
  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];
  }
  if (name.length()) 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.
// clang-format off
#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")
#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
};

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];
  }
}
// clang-format on

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

// Parses exactly nibbles worth of hex digits into a number, or error.
CheckedError Parser::ParseHexNum(int nibbles, uint64_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_ < ' ' && static_cast<signed char>(*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_++;
                uint64_t val;
                ECHECK(ParseHexNum(2, &val));
                attribute_ += static_cast<char>(val);
                break;
              }
              case 'u': {
                cursor_++;
                uint64_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_);
          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(static_cast<int64_t>(
                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_; }

bool Parser::IsIdent(const char *id) {
  return token_ == kTokenIdentifier && attribute_ == id;
}

// 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>(current_namespace_->components.size());
       components >= 0; components--) {
    auto ed = enums_.Lookup(
        current_namespace_->GetFullyQualifiedName(id, components));
    if (ed) return ed;
  }
  return nullptr;
}

StructDef *Parser::LookupStruct(const std::string &id) const {
  auto sd = structs_.Lookup(id);
  if (sd) sd->refcount++;
  return sd;
}

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_ == kTokenIdentifier) {
    if (IsIdent("bool")) {
      type.base_type = BASE_TYPE_BOOL;
      NEXT();
    } else if (IsIdent("byte") || IsIdent("int8")) {
      type.base_type = BASE_TYPE_CHAR;
      NEXT();
    } else if (IsIdent("ubyte") || IsIdent("uint8")) {
      type.base_type = BASE_TYPE_UCHAR;
      NEXT();
    } else if (IsIdent("short") || IsIdent("int16")) {
      type.base_type = BASE_TYPE_SHORT;
      NEXT();
    } else if (IsIdent("ushort") || IsIdent("uint16")) {
      type.base_type = BASE_TYPE_USHORT;
      NEXT();
    } else if (IsIdent("int") || IsIdent("int32")) {
      type.base_type = BASE_TYPE_INT;
      NEXT();
    } else if (IsIdent("uint") || IsIdent("uint32")) {
      type.base_type = BASE_TYPE_UINT;
      NEXT();
    } else if (IsIdent("long") || IsIdent("int64")) {
      type.base_type = BASE_TYPE_LONG;
      NEXT();
    } else if (IsIdent("ulong") || IsIdent("uint64")) {
      type.base_type = BASE_TYPE_ULONG;
      NEXT();
    } else if (IsIdent("float") || IsIdent("float32")) {
      type.base_type = BASE_TYPE_FLOAT;
      NEXT();
    } else if (IsIdent("double") || IsIdent("float64")) {
      type.base_type = BASE_TYPE_DOUBLE;
      NEXT();
    } else if (IsIdent("string")) {
      type.base_type = BASE_TYPE_STRING;
      NEXT();
    } else {
      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).");
    }
    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_;

  if (LookupStruct(name))
    return Error("field name can not be the same as table/struct name");

  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));
  } else if (type.base_type == BASE_TYPE_VECTOR &&
             type.element == BASE_TYPE_UNION) {
    // Only cpp, js and ts supports the union vector feature so far.
    if (!SupportsVectorOfUnions()) {
      return Error(
          "Vectors of unions are not yet supported in all "
          "the specified programming languages.");
    }
    // For vector of union fields, add a second auto-generated vector field to
    // hold the types, with a special suffix.
    Type union_vector(BASE_TYPE_VECTOR, nullptr, type.enum_def);
    union_vector.element = BASE_TYPE_UTYPE;
    ECHECK(AddField(struct_def, name + UnionTypeFieldSuffix(), union_vector,
                    &typefield));
  }

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

  if (token_ == '=') {
    NEXT();
    if (!IsScalar(type.base_type) || struct_def.fixed)
      return Error(
            "default values currently only supported for scalars in tables");
    ECHECK(ParseSingleValue(field->value));
  }
  if (type.enum_def &&
      !type.enum_def->is_union &&
      !type.enum_def->attributes.Lookup("bit_flags") &&
      !type.enum_def->ReverseLookup(static_cast<int>(
                                 StringToInt(field->value.constant.c_str())))) {
    return Error("default value of " + field->value.constant + " for field " +
                 name + " is not part of enum " + type.enum_def->name);
  }
  if (IsFloat(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()))))
    Warning("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(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(type.base_type)) {
      field->required = true;
      if (type.base_type != BASE_TYPE_STRING)
        return Error("'key' field must be string or scalar type");
    }
  }

  auto field_native_custom_alloc =
      field->attributes.Lookup("native_custom_alloc");
  if (field_native_custom_alloc)
    return Error(
        "native_custom_alloc can only be used with a table or struct "
        "definition");

  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 (type.base_type != BASE_TYPE_VECTOR || 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);

    // Keep a pointer to StructDef in FieldDef to simplify re-use later
    auto nested_qualified_name =
        current_namespace_->GetFullyQualifiedName(nested->constant);
    field->nested_flatbuffer = LookupStruct(nested_qualified_name);
  }

  if (field->attributes.Lookup("flexbuffer")) {
    field->flexbuffer = true;
    uses_flexbuffers_ = true;
    if (type.base_type != BASE_TYPE_VECTOR ||
        type.element != BASE_TYPE_UCHAR)
      return Error("flexbuffer attribute may only apply to a vector of ubyte");
  }

  if (typefield) {
    if (!IsScalar(typefield->value.type.base_type)) {
      // this is a union vector field
      typefield->required = field->required;
    }
    // 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::ParseString(Value &val) {
  auto s = attribute_;
  EXPECT(kTokenStringConstant);
  val.constant = NumToString(builder_.CreateString(s).o);
  return NoError();
}

CheckedError Parser::ParseComma() {
  if (!opts.protobuf_ascii_alike) 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;
      // Find corresponding type field we may have already parsed.
      for (auto elem = field_stack_.rbegin();
           elem != field_stack_.rbegin() + parent_fieldn; ++elem) {
        auto &type = elem->second->value.type;
        if (type.base_type == BASE_TYPE_UTYPE &&
            type.enum_def == val.type.enum_def) {
          constant = elem->first.constant;
          break;
        }
      }
      if (constant.empty()) {
        // 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.
        ECHECK(ParseComma());
        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;
      }
      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);
      if (enum_val->union_type.base_type == BASE_TYPE_STRUCT) {
        ECHECK(ParseTable(*enum_val->union_type.struct_def, &val.constant,
                          nullptr));
        if (enum_val->union_type.struct_def->fixed) {
          // All BASE_TYPE_UNION values are offsets, so turn this into one.
          SerializeStruct(*enum_val->union_type.struct_def, val);
          builder_.ClearOffsets();
          val.constant = NumToString(builder_.GetSize());
        }
      } else if (enum_val->union_type.base_type == BASE_TYPE_STRING) {
        ECHECK(ParseString(val));
      } else {
        assert(false);
      }
      break;
    }
    case BASE_TYPE_STRUCT:
      ECHECK(ParseTable(*val.type.struct_def, &val.constant, nullptr));
      break;
    case BASE_TYPE_STRING: {
      ECHECK(ParseString(val));
      break;
    }
    case BASE_TYPE_VECTOR: {
      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::ParseTableDelimiters(size_t &fieldn,
                                          const StructDef *struct_def,
                                          ParseTableDelimitersBody body,
                                          void *state) {
  // We allow tables both as JSON object{ .. } with field names
  // or vector[..] with all fields in order
  char terminator = '}';
  bool is_nested_vector = struct_def && Is('[');
  if (is_nested_vector) {
    NEXT();
    terminator = ']';
  } else {
    EXPECT('{');
  }
  for (;;) {
    if ((!opts.strict_json || !fieldn) && Is(terminator)) break;
    std::string name;
    if (is_nested_vector) {
      if (fieldn > struct_def->fields.vec.size()) {
        return Error("too many unnamed fields in nested array");
      }
      name = struct_def->fields.vec[fieldn]->name;
    } else {
      name = attribute_;
      if (Is(kTokenStringConstant)) {
        NEXT();
      } else {
        EXPECT(opts.strict_json ? kTokenStringConstant : kTokenIdentifier);
      }
      if (!opts.protobuf_ascii_alike || !(Is('{') || Is('['))) EXPECT(':');
    }
    ECHECK(body(name, fieldn, struct_def, state));
    if (Is(terminator)) break;
    ECHECK(ParseComma());
  }
  NEXT();
  if (is_nested_vector && fieldn != struct_def->fields.vec.size()) {
    return Error("wrong number of unnamed fields in table vector");
  }
  return NoError();
}

CheckedError Parser::ParseTable(const StructDef &struct_def, std::string *value,
                                uoffset_t *ovalue) {
  size_t fieldn_outer = 0;
  auto err = ParseTableDelimiters(
      fieldn_outer, &struct_def,
      [](const std::string &name, size_t &fieldn,
         const StructDef *struct_def_inner, void *state) -> CheckedError {
        Parser *parser = static_cast<Parser *>(state);
        if (name == "$schema") {
          ECHECK(parser->Expect(kTokenStringConstant));
          return NoError();
        }
        auto field = struct_def_inner->fields.Lookup(name);
        if (!field) {
          if (!parser->opts.skip_unexpected_fields_in_json) {
            return parser->Error("unknown field: " + name);
          } else {
            ECHECK(parser->SkipAnyJsonValue());
          }
        } else {
          if (parser->IsIdent("null")) {
            ECHECK(parser->Next());  // Ignore this field.
          } else {
            Value val = field->value;
            if (field->flexbuffer) {
              flexbuffers::Builder builder(1024,
                                           flexbuffers::BUILDER_FLAG_SHARE_ALL);
              ECHECK(parser->ParseFlexBufferValue(&builder));
              builder.Finish();
              auto off = parser->builder_.CreateVector(builder.GetBuffer());
              val.constant = NumToString(off.o);
            } else if (field->nested_flatbuffer) {
              ECHECK(parser->ParseNestedFlatbuffer(val, field, fieldn,
                                                   struct_def_inner));
            } else {
              ECHECK(
                  parser->ParseAnyValue(val, field, fieldn, struct_def_inner));
            }
            // Hardcoded insertion-sort with error-check.
            // If fields are specified in order, then this loop exits
            // immediately.
            auto elem = parser->field_stack_.rbegin();
            for (; elem != parser->field_stack_.rbegin() + fieldn; ++elem) {
              auto existing_field = elem->second;
              if (existing_field == field)
                return parser->Error("field set more than once: " +
                                     field->name);
              if (existing_field->value.offset < field->value.offset) break;
            }
            // Note: elem points to before the insertion point, thus .base()
            // points to the correct spot.
            parser->field_stack_.insert(elem.base(),
                                        std::make_pair(val, field));
            fieldn++;
          }
        }
        return NoError();
      },
      this);
  ECHECK(err);

  // Check if all required fields are parsed.