/src/libprotobuf-mutator/build/external.protobuf/src/external.protobuf/src/google/protobuf/descriptor.cc

Source (jump to first uncovered line)
// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// Author: kenton@google.com (Kenton Varda)
//  Based on original Protocol Buffers design by
//  Sanjay Ghemawat, Jeff Dean, and others.

#include "google/protobuf/descriptor.h"

#include <algorithm>
#include <array>
#include <cstdlib>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>

#include "google/protobuf/stubs/common.h"
#include "absl/base/call_once.h"
#include "absl/base/casts.h"
#include "absl/base/dynamic_annotations.h"
#include "absl/container/btree_map.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/hash/hash.h"
#include "absl/log/absl_check.h"
#include "absl/log/absl_log.h"
#include "absl/strings/ascii.h"
#include "absl/strings/escaping.h"
#include "absl/strings/match.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/str_join.h"
#include "absl/strings/str_split.h"
#include "absl/strings/string_view.h"
#include "absl/strings/strip.h"
#include "absl/strings/substitute.h"
#include "absl/synchronization/mutex.h"
#include "absl/types/optional.h"
#include "google/protobuf/any.h"
#include "google/protobuf/descriptor.pb.h"
#include "google/protobuf/descriptor_database.h"
#include "google/protobuf/dynamic_message.h"
#include "google/protobuf/generated_message_util.h"
#include "google/protobuf/io/strtod.h"
#include "google/protobuf/io/tokenizer.h"
#include "google/protobuf/port.h"
#include "google/protobuf/text_format.h"
#include "google/protobuf/unknown_field_set.h"


// Must be included last.
#include "google/protobuf/port_def.inc"

namespace google {
namespace protobuf {
namespace {
using ::google::protobuf::internal::DownCast;

const int kPackageLimit = 100;


std::string ToCamelCase(const std::string& input, bool lower_first) {
  bool capitalize_next = !lower_first;
  std::string result;
  result.reserve(input.size());

  for (char character : input) {
    if (character == '_') {
      capitalize_next = true;
    } else if (capitalize_next) {
      result.push_back(absl::ascii_toupper(character));
      capitalize_next = false;
    } else {
      result.push_back(character);
    }
  }

  // Lower-case the first letter.
  if (lower_first && !result.empty()) {
    result[0] = absl::ascii_tolower(result[0]);
  }

  return result;
}

std::string ToJsonName(const std::string& input) {
  bool capitalize_next = false;
  std::string result;
  result.reserve(input.size());

  for (char character : input) {
    if (character == '_') {
      capitalize_next = true;
    } else if (capitalize_next) {
      result.push_back(absl::ascii_toupper(character));
      capitalize_next = false;
    } else {
      result.push_back(character);
    }
  }

  return result;
}

template <typename OptionsT>
bool IsLegacyJsonFieldConflictEnabled(const OptionsT& options) {
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
#endif
  return options.deprecated_legacy_json_field_conflicts();
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
}

// Backport of fold expressions for the comma operator to C++11.
// Usage:  Fold({expr...});
// Guaranteed to evaluate left-to-right
struct ExpressionEater {
  template <typename T>
  ExpressionEater(T&&) {}  // NOLINT
};
void Fold(std::initializer_list<ExpressionEater>) {}

template <int R>
constexpr size_t RoundUpTo(size_t n) {
  static_assert((R & (R - 1)) == 0, "Must be power of two");
  return (n + (R - 1)) & ~(R - 1);
}

constexpr size_t Max(size_t a, size_t b) { return a > b ? a : b; }
template <typename T, typename... Ts>
constexpr size_t Max(T a, Ts... b) {
  return Max(a, Max(b...));
}

template <typename T>
constexpr size_t EffectiveAlignof() {
  // `char` is special in that it gets aligned to 8. It is where we drop the
  // trivial structs.
  return std::is_same<T, char>::value ? 8 : alignof(T);
}

template <int align, typename U, typename... T>
using AppendIfAlign =
    typename std::conditional<EffectiveAlignof<U>() == align, void (*)(T..., U),
                              void (*)(T...)>::type;

// Metafunction to sort types in descending order of alignment.
// Useful for the flat allocator to ensure proper alignment of all elements
// without having to add padding.
// Instead of implementing a proper sort metafunction we just do a
// filter+merge, which is much simpler to write as a metafunction.
// We have a fixed set of alignments we can filter on.
// For simplicity we use a function pointer as a type list.
template <typename In, typename T16, typename T8, typename T4, typename T2,
          typename T1>
struct TypeListSortImpl;

template <typename... T16, typename... T8, typename... T4, typename... T2,
          typename... T1>
struct TypeListSortImpl<void (*)(), void (*)(T16...), void (*)(T8...),
                        void (*)(T4...), void (*)(T2...), void (*)(T1...)> {
  using type = void (*)(T16..., T8..., T4..., T2..., T1...);
};

template <typename First, typename... Rest, typename... T16, typename... T8,
          typename... T4, typename... T2, typename... T1>
struct TypeListSortImpl<void (*)(First, Rest...), void (*)(T16...),
                        void (*)(T8...), void (*)(T4...), void (*)(T2...),
                        void (*)(T1...)> {
  using type = typename TypeListSortImpl<
      void (*)(Rest...), AppendIfAlign<16, First, T16...>,
      AppendIfAlign<8, First, T8...>, AppendIfAlign<4, First, T4...>,
      AppendIfAlign<2, First, T2...>, AppendIfAlign<1, First, T1...>>::type;
};

template <typename... T>
using SortByAlignment =
    typename TypeListSortImpl<void (*)(T...), void (*)(), void (*)(),
                              void (*)(), void (*)(), void (*)()>::type;

template <template <typename...> class C, typename... T>
auto ApplyTypeList(void (*)(T...)) -> C<T...>;

template <typename T>
constexpr int FindTypeIndex() {
  return -1;
}

template <typename T, typename T1, typename... Ts>
constexpr int FindTypeIndex() {
  return std::is_same<T, T1>::value ? 0 : FindTypeIndex<T, Ts...>() + 1;
}

// A type to value map, where the possible keys as specified in `Keys...`.
// The values for key `K` is `ValueT<K>`
template <template <typename> class ValueT, typename... Keys>
class TypeMap {
 public:
  template <typename K>
  ValueT<K>& Get() {
    return static_cast<Base<K>&>(payload_).value;
  }

  template <typename K>
  const ValueT<K>& Get() const {
    return static_cast<const Base<K>&>(payload_).value;
  }

 private:
  template <typename K>
  struct Base {
    ValueT<K> value{};
  };
  struct Payload : Base<Keys>... {};
  Payload payload_;
};

template <typename T>
using IntT = int;
template <typename T>
using PointerT = T*;

// Manages an allocation of sequential arrays of type `T...`.
// It is more space efficient than storing N (ptr, size) pairs, by storing only
// the pointer to the head and the boundaries between the arrays.
template <typename... T>
class FlatAllocation {
 public:
  static constexpr size_t kMaxAlign = Max(alignof(T)...);

  FlatAllocation(const TypeMap<IntT, T...>& ends) : ends_(ends) {
    // The arrays start just after FlatAllocation, so adjust the ends.
    Fold({(ends_.template Get<T>() +=
           RoundUpTo<kMaxAlign>(sizeof(FlatAllocation)))...});
    Fold({Init<T>()...});
  }

  void Destroy() {
    Fold({Destroy<T>()...});
    internal::SizedDelete(this, total_bytes());
  }

  template <int I>
  using type = typename std::tuple_element<I, std::tuple<T...>>::type;

  // Gets a tuple of the head pointers for the arrays
  TypeMap<PointerT, T...> Pointers() const {
    TypeMap<PointerT, T...> out;
    Fold({(out.template Get<T>() = Begin<T>())...});
    return out;
  }


 private:
  // Total number of bytes used by all arrays.
  int total_bytes() const {
    // Get the last end.
    return ends_.template Get<typename std::tuple_element<
        sizeof...(T) - 1, std::tuple<T...>>::type>();
  }


  template <typename U>
  int BeginOffset() const {
    constexpr int type_index = FindTypeIndex<U, T...>();
    // Avoid a negative value here to keep it compiling when type_index == 0
    constexpr int prev_type_index = type_index == 0 ? 0 : type_index - 1;
    using PrevType =
        typename std::tuple_element<prev_type_index, std::tuple<T...>>::type;
    // Ensure the types are properly aligned.
    static_assert(EffectiveAlignof<PrevType>() >= EffectiveAlignof<U>(), "");
    return type_index == 0 ? RoundUpTo<kMaxAlign>(sizeof(FlatAllocation))
                           : ends_.template Get<PrevType>();
  }

  template <typename U>
  int EndOffset() const {
    return ends_.template Get<U>();
  }

  // Avoid the reinterpret_cast if the array is empty.
  // Clang's Control Flow Integrity does not like the cast pointing to memory
  // that is not yet initialized to be of that type.
  // (from -fsanitize=cfi-unrelated-cast)
  template <typename U>
  U* Begin() const {
    int begin = BeginOffset<U>(), end = EndOffset<U>();
    if (begin == end) return nullptr;
    return reinterpret_cast<U*>(data() + begin);
  }

  template <typename U>
  U* End() const {
    int begin = BeginOffset<U>(), end = EndOffset<U>();
    if (begin == end) return nullptr;
    return reinterpret_cast<U*>(data() + end);
  }

  template <typename U>
  bool Init() {
    // Skip for the `char` block. No need to zero initialize it.
    if (std::is_same<U, char>::value) return true;
    for (char *p = data() + BeginOffset<U>(), *end = data() + EndOffset<U>();
         p != end; p += sizeof(U)) {
      ::new (p) U{};
    }
    return true;
  }

  template <typename U>
  bool Destroy() {
    if (std::is_trivially_destructible<U>::value) return true;
    for (U* it = Begin<U>(), *end = End<U>(); it != end; ++it) {
      it->~U();
    }
    return true;
  }

  char* data() const {
    return const_cast<char*>(reinterpret_cast<const char*>(this));
  }

  TypeMap<IntT, T...> ends_;
};

template <typename... T>
TypeMap<IntT, T...> CalculateEnds(const TypeMap<IntT, T...>& sizes) {
  int total = 0;
  TypeMap<IntT, T...> out;
  Fold({(out.template Get<T>() = total +=
         sizeof(T) * sizes.template Get<T>())...});
  return out;
}

// The implementation for FlatAllocator below.
// This separate class template makes it easier to have methods that fold on
// `T...`.
template <typename... T>
class FlatAllocatorImpl {
 public:
  using Allocation = FlatAllocation<T...>;

  template <typename U>
  void PlanArray(int array_size) {
    // We can't call PlanArray after FinalizePlanning has been called.
    ABSL_CHECK(!has_allocated());
    if (std::is_trivially_destructible<U>::value) {
      // Trivial types are aligned to 8 bytes.
      static_assert(alignof(U) <= 8, "");
      total_.template Get<char>() += RoundUpTo<8>(array_size * sizeof(U));
    } else {
      // Since we can't use `if constexpr`, just make the expression compile
      // when this path is not taken.
      using TypeToUse =
          typename std::conditional<std::is_trivially_destructible<U>::value,
                                    char, U>::type;
      total_.template Get<TypeToUse>() += array_size;
    }
  }

  template <typename U>
  U* AllocateArray(int array_size) {
    constexpr bool trivial = std::is_trivially_destructible<U>::value;
    using TypeToUse = typename std::conditional<trivial, char, U>::type;

    // We can only allocate after FinalizePlanning has been called.
    ABSL_CHECK(has_allocated());

    TypeToUse*& data = pointers_.template Get<TypeToUse>();
    int& used = used_.template Get<TypeToUse>();
    U* res = reinterpret_cast<U*>(data + used);
    used += trivial ? RoundUpTo<8>(array_size * sizeof(U)) : array_size;
    ABSL_CHECK_LE(used, total_.template Get<TypeToUse>());
    return res;
  }

  template <typename... In>
  const std::string* AllocateStrings(In&&... in) {
    std::string* strings = AllocateArray<std::string>(sizeof...(in));
    std::string* res = strings;
    Fold({(*strings++ = std::string(std::forward<In>(in)))...});
    return res;
  }

  // Allocate all 5 names of the field:
  // name, full name, lowercase, camelcase and json.
  // It will dedup the strings when possible.
  // The resulting array contains `name` at index 0, `full_name` at index 1
  // and the other 3 indices are specified in the result.
  void PlanFieldNames(const std::string& name,
                      const std::string* opt_json_name) {
    ABSL_CHECK(!has_allocated());

    // Fast path for snake_case names, which follow the style guide.
    if (opt_json_name == nullptr) {
      switch (GetFieldNameCase(name)) {
        case FieldNameCase::kAllLower:
          // Case 1: they are all the same.
          return PlanArray<std::string>(2);
        case FieldNameCase::kSnakeCase:
          // Case 2: name==lower, camel==json
          return PlanArray<std::string>(3);
        default:
          break;
      }
    }

    std::string lowercase_name = name;
    absl::AsciiStrToLower(&lowercase_name);

    std::string camelcase_name = ToCamelCase(name, /* lower_first = */ true);
    std::string json_name =
        opt_json_name != nullptr ? *opt_json_name : ToJsonName(name);

    absl::string_view all_names[] = {name, lowercase_name, camelcase_name,
                                     json_name};
    std::sort(all_names, all_names + 4);
    int unique =
        static_cast<int>(std::unique(all_names, all_names + 4) - all_names);

    PlanArray<std::string>(unique + 1);
  }

  struct FieldNamesResult {
    const std::string* array;
    int lowercase_index;
    int camelcase_index;
    int json_index;
  };
  FieldNamesResult AllocateFieldNames(const std::string& name,
                                      const std::string& scope,
                                      const std::string* opt_json_name) {
    ABSL_CHECK(has_allocated());

    std::string full_name =
        scope.empty() ? name : absl::StrCat(scope, ".", name);

    // Fast path for snake_case names, which follow the style guide.
    if (opt_json_name == nullptr) {
      switch (GetFieldNameCase(name)) {
        case FieldNameCase::kAllLower:
          // Case 1: they are all the same.
          return {AllocateStrings(name, std::move(full_name)), 0, 0, 0};
        case FieldNameCase::kSnakeCase:
          // Case 2: name==lower, camel==json
          return {AllocateStrings(name, std::move(full_name),
                                  ToCamelCase(name, /* lower_first = */ true)),
                  0, 2, 2};
        default:
          break;
      }
    }

    std::vector<std::string> names;
    names.push_back(name);
    names.push_back(std::move(full_name));

    const auto push_name = [&](std::string new_name) {
      for (size_t i = 0; i < names.size(); ++i) {
        // Do not compare the full_name. It is unlikely to match, except in
        // custom json_name. We are not taking this into account in
        // PlanFieldNames so better to not try it.
        if (i == 1) continue;
        if (names[i] == new_name) return i;
      }
      names.push_back(std::move(new_name));
      return names.size() - 1;
    };

    FieldNamesResult result{nullptr, 0, 0, 0};

    std::string lowercase_name = name;
    absl::AsciiStrToLower(&lowercase_name);
    result.lowercase_index = push_name(std::move(lowercase_name));
    result.camelcase_index =
        push_name(ToCamelCase(name, /* lower_first = */ true));
    result.json_index =
        push_name(opt_json_name != nullptr ? *opt_json_name : ToJsonName(name));

    std::string* all_names = AllocateArray<std::string>(names.size());
    result.array = all_names;
    std::move(names.begin(), names.end(), all_names);

    return result;
  }

  template <typename Alloc>
  void FinalizePlanning(Alloc& alloc) {
    ABSL_CHECK(!has_allocated());

    pointers_ = alloc->CreateFlatAlloc(total_)->Pointers();

    ABSL_CHECK(has_allocated());
  }

  void ExpectConsumed() const {
    // We verify that we consumed all the memory requested if there was no
    // error in processing.
    Fold({ExpectConsumed<T>()...});
  }

 private:
  bool has_allocated() const {
    return pointers_.template Get<char>() != nullptr;
  }

  static bool IsLower(char c) { return 'a' <= c && c <= 'z'; }
  static bool IsDigit(char c) { return '0' <= c && c <= '9'; }
  static bool IsLowerOrDigit(char c) { return IsLower(c) || IsDigit(c); }

  enum class FieldNameCase { kAllLower, kSnakeCase, kOther };
  FieldNameCase GetFieldNameCase(const std::string& name) {
    if (!IsLower(name[0])) return FieldNameCase::kOther;
    FieldNameCase best = FieldNameCase::kAllLower;
    for (char c : name) {
      if (IsLowerOrDigit(c)) {
        // nothing to do
      } else if (c == '_') {
        best = FieldNameCase::kSnakeCase;
      } else {
        return FieldNameCase::kOther;
      }
    }
    return best;
  }

  template <typename U>
  bool ExpectConsumed() const {
    ABSL_CHECK_EQ(total_.template Get<U>(), used_.template Get<U>());
    return true;
  }

  TypeMap<PointerT, T...> pointers_;
  TypeMap<IntT, T...> total_;
  TypeMap<IntT, T...> used_;
};

}  // namespace

class Symbol {
 public:
  enum Type {
    NULL_SYMBOL,
    MESSAGE,
    FIELD,
    ONEOF,
    ENUM,
    ENUM_VALUE,
    ENUM_VALUE_OTHER_PARENT,
    SERVICE,
    METHOD,
    FULL_PACKAGE,
    SUB_PACKAGE,
  };

  Symbol() {
    static constexpr internal::SymbolBase null_symbol{};
    static_assert(null_symbol.symbol_type_ == NULL_SYMBOL, "");
    // Initialize with a sentinel to make sure `ptr_` is never null.
    ptr_ = &null_symbol;
  }

  // Every object we store derives from internal::SymbolBase, where we store the
  // symbol type enum.
  // Storing in the object can be done without using more space in most cases,
  // while storing it in the Symbol type would require 8 bytes.
#define DEFINE_MEMBERS(TYPE, TYPE_CONSTANT, FIELD)                             \
  explicit Symbol(TYPE* value) : ptr_(value) {                                 \
    value->symbol_type_ = TYPE_CONSTANT;                                       \
  }                                                                            \
  const TYPE* FIELD() const {                                                  \
    return type() == TYPE_CONSTANT ? static_cast<const TYPE*>(ptr_) : nullptr; \
  }

  DEFINE_MEMBERS(Descriptor, MESSAGE, descriptor)
  DEFINE_MEMBERS(FieldDescriptor, FIELD, field_descriptor)
  DEFINE_MEMBERS(OneofDescriptor, ONEOF, oneof_descriptor)
  DEFINE_MEMBERS(EnumDescriptor, ENUM, enum_descriptor)
  DEFINE_MEMBERS(ServiceDescriptor, SERVICE, service_descriptor)
  DEFINE_MEMBERS(MethodDescriptor, METHOD, method_descriptor)
  DEFINE_MEMBERS(FileDescriptor, FULL_PACKAGE, file_descriptor)

  // We use a special node for subpackage FileDescriptor.
  // It is potentially added to the table with multiple different names, so we
  // need a separate place to put the name.
  struct Subpackage : internal::SymbolBase {
    int name_size;
    const FileDescriptor* file;
  };
  DEFINE_MEMBERS(Subpackage, SUB_PACKAGE, sub_package_file_descriptor)

  // Enum values have two different parents.
  // We use two different identitied for the same object to determine the two
  // different insertions in the map.
  static Symbol EnumValue(EnumValueDescriptor* value, int n) {
    Symbol s;
    internal::SymbolBase* ptr;
    if (n == 0) {
      ptr = static_cast<internal::SymbolBaseN<0>*>(value);
      ptr->symbol_type_ = ENUM_VALUE;
    } else {
      ptr = static_cast<internal::SymbolBaseN<1>*>(value);
      ptr->symbol_type_ = ENUM_VALUE_OTHER_PARENT;
    }
    s.ptr_ = ptr;
    return s;
  }

  const EnumValueDescriptor* enum_value_descriptor() const {
    return type() == ENUM_VALUE
               ? static_cast<const EnumValueDescriptor*>(
                     static_cast<const internal::SymbolBaseN<0>*>(ptr_))
           : type() == ENUM_VALUE_OTHER_PARENT
               ? static_cast<const EnumValueDescriptor*>(
                     static_cast<const internal::SymbolBaseN<1>*>(ptr_))
               : nullptr;
  }

#undef DEFINE_MEMBERS

  Type type() const { return static_cast<Type>(ptr_->symbol_type_); }
  bool IsNull() const { return type() == NULL_SYMBOL; }
  bool IsType() const { return type() == MESSAGE || type() == ENUM; }
  bool IsAggregate() const {
    return IsType() || IsPackage() || type() == SERVICE;
  }
  bool IsPackage() const {
    return type() == FULL_PACKAGE || type() == SUB_PACKAGE;
  }

  const FileDescriptor* GetFile() const {
    switch (type()) {
      case MESSAGE:
        return descriptor()->file();
      case FIELD:
        return field_descriptor()->file();
      case ONEOF:
        return oneof_descriptor()->containing_type()->file();
      case ENUM:
        return enum_descriptor()->file();
      case ENUM_VALUE:
        return enum_value_descriptor()->type()->file();
      case SERVICE:
        return service_descriptor()->file();
      case METHOD:
        return method_descriptor()->service()->file();
      case FULL_PACKAGE:
        return file_descriptor();
      case SUB_PACKAGE:
        return sub_package_file_descriptor()->file;
      default:
        return nullptr;
    }
  }

  absl::string_view full_name() const {
    switch (type()) {
      case MESSAGE:
        return descriptor()->full_name();
      case FIELD:
        return field_descriptor()->full_name();
      case ONEOF:
        return oneof_descriptor()->full_name();
      case ENUM:
        return enum_descriptor()->full_name();
      case ENUM_VALUE:
        return enum_value_descriptor()->full_name();
      case SERVICE:
        return service_descriptor()->full_name();
      case METHOD:
        return method_descriptor()->full_name();
      case FULL_PACKAGE:
        return file_descriptor()->package();
      case SUB_PACKAGE:
        return absl::string_view(sub_package_file_descriptor()->file->package())
            .substr(0, sub_package_file_descriptor()->name_size);
      default:
        ABSL_CHECK(false);
    }
    return "";
  }

  std::pair<const void*, absl::string_view> parent_name_key() const {
    const auto or_file = [&](const void* p) { return p ? p : GetFile(); };
    switch (type()) {
      case MESSAGE:
        return {or_file(descriptor()->containing_type()), descriptor()->name()};
      case FIELD: {
        auto* field = field_descriptor();
        return {or_file(field->is_extension() ? field->extension_scope()
                                              : field->containing_type()),
                field->name()};
      }
      case ONEOF:
        return {oneof_descriptor()->containing_type(),
                oneof_descriptor()->name()};
      case ENUM:
        return {or_file(enum_descriptor()->containing_type()),
                enum_descriptor()->name()};
      case ENUM_VALUE:
        return {or_file(enum_value_descriptor()->type()->containing_type()),
                enum_value_descriptor()->name()};
      case ENUM_VALUE_OTHER_PARENT:
        return {enum_value_descriptor()->type(),
                enum_value_descriptor()->name()};
      case SERVICE:
        return {GetFile(), service_descriptor()->name()};
      case METHOD:
        return {method_descriptor()->service(), method_descriptor()->name()};
      default:
        ABSL_CHECK(false);
    }
    return {};
  }

 private:
  const internal::SymbolBase* ptr_;
};

const FieldDescriptor::CppType
    FieldDescriptor::kTypeToCppTypeMap[MAX_TYPE + 1] = {
        static_cast<CppType>(0),  // 0 is reserved for errors

        CPPTYPE_DOUBLE,   // TYPE_DOUBLE
        CPPTYPE_FLOAT,    // TYPE_FLOAT
        CPPTYPE_INT64,    // TYPE_INT64
        CPPTYPE_UINT64,   // TYPE_UINT64
        CPPTYPE_INT32,    // TYPE_INT32
        CPPTYPE_UINT64,   // TYPE_FIXED64
        CPPTYPE_UINT32,   // TYPE_FIXED32
        CPPTYPE_BOOL,     // TYPE_BOOL
        CPPTYPE_STRING,   // TYPE_STRING
        CPPTYPE_MESSAGE,  // TYPE_GROUP
        CPPTYPE_MESSAGE,  // TYPE_MESSAGE
        CPPTYPE_STRING,   // TYPE_BYTES
        CPPTYPE_UINT32,   // TYPE_UINT32
        CPPTYPE_ENUM,     // TYPE_ENUM
        CPPTYPE_INT32,    // TYPE_SFIXED32
        CPPTYPE_INT64,    // TYPE_SFIXED64
        CPPTYPE_INT32,    // TYPE_SINT32
        CPPTYPE_INT64,    // TYPE_SINT64
};

const char* const FieldDescriptor::kTypeToName[MAX_TYPE + 1] = {
    "ERROR",  // 0 is reserved for errors

    "double",    // TYPE_DOUBLE
    "float",     // TYPE_FLOAT
    "int64",     // TYPE_INT64
    "uint64",    // TYPE_UINT64
    "int32",     // TYPE_INT32
    "fixed64",   // TYPE_FIXED64
    "fixed32",   // TYPE_FIXED32
    "bool",      // TYPE_BOOL
    "string",    // TYPE_STRING
    "group",     // TYPE_GROUP
    "message",   // TYPE_MESSAGE
    "bytes",     // TYPE_BYTES
    "uint32",    // TYPE_UINT32
    "enum",      // TYPE_ENUM
    "sfixed32",  // TYPE_SFIXED32
    "sfixed64",  // TYPE_SFIXED64
    "sint32",    // TYPE_SINT32
    "sint64",    // TYPE_SINT64
};

const char* const FieldDescriptor::kCppTypeToName[MAX_CPPTYPE + 1] = {
    "ERROR",  // 0 is reserved for errors

    "int32",    // CPPTYPE_INT32
    "int64",    // CPPTYPE_INT64
    "uint32",   // CPPTYPE_UINT32
    "uint64",   // CPPTYPE_UINT64
    "double",   // CPPTYPE_DOUBLE
    "float",    // CPPTYPE_FLOAT
    "bool",     // CPPTYPE_BOOL
    "enum",     // CPPTYPE_ENUM
    "string",   // CPPTYPE_STRING
    "message",  // CPPTYPE_MESSAGE
};

const char* const FieldDescriptor::kLabelToName[MAX_LABEL + 1] = {
    "ERROR",  // 0 is reserved for errors

    "optional",  // LABEL_OPTIONAL
    "required",  // LABEL_REQUIRED
    "repeated",  // LABEL_REPEATED
};

const char* FileDescriptor::SyntaxName(FileDescriptor::Syntax syntax) {
  switch (syntax) {
    case SYNTAX_PROTO2:
      return "proto2";
    case SYNTAX_PROTO3:
      return "proto3";
    case SYNTAX_UNKNOWN:
      return "unknown";
  }
  ABSL_LOG(FATAL) << "can't reach here.";
  return nullptr;
}

static const char* const kNonLinkedWeakMessageReplacementName = "google.protobuf.Empty";

#if !defined(_MSC_VER) || (_MSC_VER >= 1900 && _MSC_VER < 1912)
const int FieldDescriptor::kMaxNumber;
const int FieldDescriptor::kFirstReservedNumber;
const int FieldDescriptor::kLastReservedNumber;
#endif

namespace {

std::string EnumValueToPascalCase(const std::string& input) {
  bool next_upper = true;
  std::string result;
  result.reserve(input.size());

  for (char character : input) {
    if (character == '_') {
      next_upper = true;
    } else {
      if (next_upper) {
        result.push_back(absl::ascii_toupper(character));
      } else {
        result.push_back(absl::ascii_tolower(character));
      }
      next_upper = false;
    }
  }

  return result;
}

// Class to remove an enum prefix from enum values.
class PrefixRemover {
 public:
  PrefixRemover(absl::string_view prefix) {
    // Strip underscores and lower-case the prefix.
    for (char character : prefix) {
      if (character != '_') {
        prefix_ += absl::ascii_tolower(character);
      }
    }
  }

  // Tries to remove the enum prefix from this enum value.
  // If this is not possible, returns the input verbatim.
  std::string MaybeRemove(absl::string_view str) {
    // We can't just lowercase and strip str and look for a prefix.
    // We need to properly recognize the difference between:
    //
    //   enum Foo {
    //     FOO_BAR_BAZ = 0;
    //     FOO_BARBAZ = 1;
    //   }
    //
    // This is acceptable (though perhaps not advisable) because even when
    // we PascalCase, these two will still be distinct (BarBaz vs. Barbaz).
    size_t i, j;

    // Skip past prefix_ in str if we can.
    for (i = 0, j = 0; i < str.size() && j < prefix_.size(); i++) {
      if (str[i] == '_') {
        continue;
      }

      if (absl::ascii_tolower(str[i]) != prefix_[j++]) {
        return std::string(str);
      }
    }

    // If we didn't make it through the prefix, we've failed to strip the
    // prefix.
    if (j < prefix_.size()) {
      return std::string(str);
    }

    // Skip underscores between prefix and further characters.
    while (i < str.size() && str[i] == '_') {
      i++;
    }

    // Enum label can't be the empty string.
    if (i == str.size()) {
      return std::string(str);
    }

    // We successfully stripped the prefix.
    str.remove_prefix(i);
    return std::string(str);
  }

 private:
  std::string prefix_;
};

// A DescriptorPool contains a bunch of hash-maps to implement the
// various Find*By*() methods.  Since hashtable lookups are O(1), it's
// most efficient to construct a fixed set of large hash-maps used by
// all objects in the pool rather than construct one or more small
// hash-maps for each object.
//
// The keys to these hash-maps are (parent, name) or (parent, number) pairs.
struct FullNameQuery {
  absl::string_view query;
  absl::string_view full_name() const { return query; }
};
struct SymbolByFullNameHash {
  using is_transparent = void;

  template <typename T>
  size_t operator()(const T& s) const {
    return absl::HashOf(s.full_name());
  }
};
struct SymbolByFullNameEq {
  using is_transparent = void;

  template <typename T, typename U>
  bool operator()(const T& a, const U& b) const {
    return a.full_name() == b.full_name();
  }
};
using SymbolsByNameSet =
    absl::flat_hash_set<Symbol, SymbolByFullNameHash, SymbolByFullNameEq>;

struct ParentNameQuery {
  std::pair<const void*, absl::string_view> query;
  std::pair<const void*, absl::string_view> parent_name_key() const {
    return query;
  }
};
struct SymbolByParentHash {
  using is_transparent = void;

  template <typename T>
  size_t operator()(const T& s) const {
    return absl::HashOf(s.parent_name_key());
  }
};
struct SymbolByParentEq {
  using is_transparent = void;

  template <typename T, typename U>
  bool operator()(const T& a, const U& b) const {
    return a.parent_name_key() == b.parent_name_key();
  }
};
using SymbolsByParentSet =
    absl::flat_hash_set<Symbol, SymbolByParentHash, SymbolByParentEq>;

struct FilesByNameHash {
  using is_transparent = void;

  size_t operator()(absl::string_view name) const { return absl::HashOf(name); }

  size_t operator()(const FileDescriptor* file) const {
    return absl::HashOf(file->name());
  }
};

struct FilesByNameEq {
  using is_transparent = void;

  bool operator()(absl::string_view lhs, absl::string_view rhs) const {
    return lhs == rhs;
  }
  bool operator()(absl::string_view lhs, const FileDescriptor* rhs) const {
    return lhs == rhs->name();
  }
  bool operator()(const FileDescriptor* lhs, absl::string_view rhs) const {
    return lhs->name() == rhs;
  }
  bool operator()(const FileDescriptor* lhs, const FileDescriptor* rhs) const {
    return lhs == rhs || lhs->name() == rhs->name();
  }
};
using FilesByNameSet =
    absl::flat_hash_set<const FileDescriptor*, FilesByNameHash, FilesByNameEq>;

using FieldsByNameMap =
    absl::flat_hash_map<std::pair<const void*, absl::string_view>,
                        const FieldDescriptor*>;

struct ParentNumberQuery {
  std::pair<const void*, int> query;
};
std::pair<const void*, int> ObjectToParentNumber(const FieldDescriptor* field) {
  return {field->containing_type(), field->number()};
}
std::pair<const void*, int> ObjectToParentNumber(
    const EnumValueDescriptor* enum_value) {
  return {enum_value->type(), enum_value->number()};
}
std::pair<const void*, int> ObjectToParentNumber(ParentNumberQuery query) {
  return query.query;
}
struct ParentNumberHash {
  using is_transparent = void;

  template <typename T>
  size_t operator()(const T& t) const {
    return absl::HashOf(ObjectToParentNumber(t));
  }
};
struct ParentNumberEq {
  using is_transparent = void;

  template <typename T, typename U>
  bool operator()(const T& a, const U& b) const {
    return ObjectToParentNumber(a) == ObjectToParentNumber(b);
  }
};
using FieldsByNumberSet = absl::flat_hash_set<const FieldDescriptor*,
                                              ParentNumberHash, ParentNumberEq>;
using EnumValuesByNumberSet =
    absl::flat_hash_set<const EnumValueDescriptor*, ParentNumberHash,
                        ParentNumberEq>;

// This is a map rather than a hash-map, since we use it to iterate
// through all the extensions that extend a given Descriptor, and an
// ordered data structure that implements lower_bound is convenient
// for that.
using ExtensionsGroupedByDescriptorMap =
    absl::btree_map<std::pair<const Descriptor*, int>, const FieldDescriptor*>;
using LocationsByPathMap =
    absl::flat_hash_map<std::string, const SourceCodeInfo_Location*>;

absl::flat_hash_set<std::string>* NewAllowedProto3Extendee() {
  const char* kOptionNames[] = {
      "FileOptions",   "MessageOptions",   "FieldOptions",
      "EnumOptions",   "EnumValueOptions", "ServiceOptions",
      "MethodOptions", "OneofOptions",     "ExtensionRangeOptions"};
  auto allowed_proto3_extendees = new absl::flat_hash_set<std::string>();
  allowed_proto3_extendees->reserve(sizeof(kOptionNames) /
                                    sizeof(kOptionNames[0]));

  for (const char* option_name : kOptionNames) {
    // descriptor.proto has a different package name in opensource. We allow
    // both so the opensource protocol compiler can also compile internal
    // proto3 files with custom options. See: b/27567912
    allowed_proto3_extendees->insert(std::string("google.protobuf.") +
                                     option_name);
    // Split the word to trick the opensource processing scripts so they
    // will keep the original package name.
    allowed_proto3_extendees->insert(std::string("proto2.") + option_name);
  }
  return allowed_proto3_extendees;
}

// Checks whether the extendee type is allowed in proto3.
// Only extensions to descriptor options are allowed. We use name comparison
// instead of comparing the descriptor directly because the extensions may be
// defined in a different pool.
bool AllowedExtendeeInProto3(const std::string& name) {
  static auto allowed_proto3_extendees =
      internal::OnShutdownDelete(NewAllowedProto3Extendee());
  return allowed_proto3_extendees->find(name) !=
         allowed_proto3_extendees->end();
}
}  // anonymous namespace

// Contains tables specific to a particular file.  These tables are not
// modified once the file has been constructed, so they need not be
// protected by a mutex.  This makes operations that depend only on the
// contents of a single file -- e.g. Descriptor::FindFieldByName() --
// lock-free.
//
// For historical reasons, the definitions of the methods of
// FileDescriptorTables and DescriptorPool::Tables are interleaved below.
// These used to be a single class.
class FileDescriptorTables {
 public:
  FileDescriptorTables();
  ~FileDescriptorTables();

  // Empty table, used with placeholder files.
  inline static const FileDescriptorTables& GetEmptyInstance();

  // -----------------------------------------------------------------
  // Finding items.

  // Returns a null Symbol (symbol.IsNull() is true) if not found.
  // TODO(sbenza): All callers to this function know the type they are looking
  // for. If we propagate that information statically we can make the query
  // faster.
  inline Symbol FindNestedSymbol(const void* parent,
                                 absl::string_view name) const;

  // These return nullptr if not found.
  inline const FieldDescriptor* FindFieldByNumber(const Descriptor* parent,
                                                  int number) const;
  inline const FieldDescriptor* FindFieldByLowercaseName(
      const void* parent, absl::string_view lowercase_name) const;
  inline const FieldDescriptor* FindFieldByCamelcaseName(
      const void* parent, absl::string_view camelcase_name) const;
  inline const EnumValueDescriptor* FindEnumValueByNumber(
      const EnumDescriptor* parent, int number) const;
  // This creates a new EnumValueDescriptor if not found, in a thread-safe way.
  inline const EnumValueDescriptor* FindEnumValueByNumberCreatingIfUnknown(
      const EnumDescriptor* parent, int number) const;

  // -----------------------------------------------------------------
  // Adding items.

  // These add items to the corresponding tables.  They return false if
  // the key already exists in the table.
  bool AddAliasUnderParent(const void* parent, absl::string_view name,
                           Symbol symbol);
  bool AddFieldByNumber(FieldDescriptor* field);
  bool AddEnumValueByNumber(EnumValueDescriptor* value);

  // Populates p->first->locations_by_path_ from p->second.
  // Unusual signature dictated by absl::call_once.
  static void BuildLocationsByPath(
      std::pair<const FileDescriptorTables*, const SourceCodeInfo*>* p);

  // Returns the location denoted by the specified path through info,
  // or nullptr if not found.
  // The value of info must be that of the corresponding FileDescriptor.
  // (Conceptually a pure function, but stateful as an optimisation.)
  const SourceCodeInfo_Location* GetSourceLocation(
      const std::vector<int>& path, const SourceCodeInfo* info) const;

  // Must be called after BuildFileImpl(), even if the build failed and
  // we are going to roll back to the last checkpoint.
  void FinalizeTables();

 private:
  const void* FindParentForFieldsByMap(const FieldDescriptor* field) const;
  static void FieldsByLowercaseNamesLazyInitStatic(
      const FileDescriptorTables* tables);
  void FieldsByLowercaseNamesLazyInitInternal() const;
  static void FieldsByCamelcaseNamesLazyInitStatic(
      const FileDescriptorTables* tables);
  void FieldsByCamelcaseNamesLazyInitInternal() const;

  SymbolsByParentSet symbols_by_parent_;
  mutable absl::once_flag fields_by_lowercase_name_once_;
  mutable absl::once_flag fields_by_camelcase_name_once_;
  // Make these fields atomic to avoid race conditions with
  // GetEstimatedOwnedMemoryBytesSize. Once the pointer is set the map won't
  // change anymore.
  mutable std::atomic<const FieldsByNameMap*> fields_by_lowercase_name_{};
  mutable std::atomic<const FieldsByNameMap*> fields_by_camelcase_name_{};
  FieldsByNumberSet fields_by_number_;  // Not including extensions.
  EnumValuesByNumberSet enum_values_by_number_;
  mutable EnumValuesByNumberSet unknown_enum_values_by_number_
      PROTOBUF_GUARDED_BY(unknown_enum_values_mu_);

  // Populated on first request to save space, hence constness games.
  mutable absl::once_flag locations_by_path_once_;
  mutable LocationsByPathMap locations_by_path_;

  // Mutex to protect the unknown-enum-value map due to dynamic
  // EnumValueDescriptor creation on unknown values.
  mutable absl::Mutex unknown_enum_values_mu_;
};

namespace internal {

// Small sequential allocator to be used within a single file.
// Most of the memory for a single FileDescriptor and everything under it is
// allocated in a single block of memory, with the FlatAllocator giving it out
// in parts later.
// The code first plans the total number of bytes needed by calling PlanArray
// with all the allocations that will happen afterwards, then calls
// FinalizePlanning passing the underlying allocator (the DescriptorPool::Tables
// instance), and then proceeds to get the memory via
// `AllocateArray`/`AllocateString` calls. The calls to PlanArray and
// The calls have to match between planning and allocating, though not
// necessarily in the same order.
class FlatAllocator
    : public decltype(ApplyTypeList<FlatAllocatorImpl>(
          SortByAlignment<char, std::string, SourceCodeInfo,
                          FileDescriptorTables,
                          // Option types
                          MessageOptions, FieldOptions, EnumOptions,
                          EnumValueOptions, ExtensionRangeOptions, OneofOptions,
                          ServiceOptions, MethodOptions, FileOptions>())) {};

}  // namespace internal

// ===================================================================
// DescriptorPool::Tables

class DescriptorPool::Tables {
 public:
  Tables();
  ~Tables();

  // Record the current state of the tables to the stack of checkpoints.
  // Each call to AddCheckpoint() must be paired with exactly one call to either
  // ClearLastCheckpoint() or RollbackToLastCheckpoint().
  //
  // This is used when building files, since some kinds of validation errors
  // cannot be detected until the file's descriptors have already been added to
  // the tables.
  //
  // This supports recursive checkpoints, since building a file may trigger
  // recursive building of other files. Note that recursive checkpoints are not
  // normally necessary; explicit dependencies are built prior to checkpointing.
  // So although we recursively build transitive imports, there is at most one
  // checkpoint in the stack during dependency building.
  //
  // Recursive checkpoints only arise during cross-linking of the descriptors.
  // Symbol references must be resolved, via DescriptorBuilder::FindSymbol and
  // friends. If the pending file references an unknown symbol
  // (e.g., it is not defined in the pending file's explicit dependencies), and
  // the pool is using a fallback database, and that database contains a file
  // defining that symbol, and that file has not yet been built by the pool,
  // the pool builds the file during cross-linking, leading to another
  // checkpoint.
  void AddCheckpoint();

  // Mark the last checkpoint as having cleared successfully, removing it from
  // the stack. If the stack is empty, all pending symbols will be committed.
  //
  // Note that this does not guarantee that the symbols added since the last
  // checkpoint won't be rolled back: if a checkpoint gets rolled back,
  // everything past that point gets rolled back, including symbols added after
  // checkpoints that were pushed onto the stack after it and marked as cleared.
  void ClearLastCheckpoint();

  // Roll back the Tables to the state of the checkpoint at the top of the
  // stack, removing everything that was added after that point.
  void RollbackToLastCheckpoint();

  // The stack of files which are currently being built.  Used to detect
  // cyclic dependencies when loading files from a DescriptorDatabase.  Not
  // used when fallback_database_ == nullptr.
  std::vector<std::string> pending_files_;

  // A set of files which we have tried to load from the fallback database
  // and encountered errors.  We will not attempt to load them again during
  // execution of the current public API call, but for compatibility with
  // legacy clients, this is cleared at the beginning of each public API call.
  // Not used when fallback_database_ == nullptr.
  absl::flat_hash_set<std::string> known_bad_files_;

  // A set of symbols which we have tried to load from the fallback database
  // and encountered errors. We will not attempt to load them again during
  // execution of the current public API call, but for compatibility with
  // legacy clients, this is cleared at the beginning of each public API call.
  absl::flat_hash_set<std::string> known_bad_symbols_;

  // The set of descriptors for which we've already loaded the full
  // set of extensions numbers from fallback_database_.
  absl::flat_hash_set<const Descriptor*> extensions_loaded_from_db_;

  // Maps type name to Descriptor::WellKnownType.  This is logically global
  // and const, but we make it a member here to simplify its construction and
  // destruction.  This only has 20-ish entries and is one per DescriptorPool,
  // so the overhead is small.
  absl::flat_hash_map<std::string, Descriptor::WellKnownType> well_known_types_;

  // -----------------------------------------------------------------
  // Finding items.

  // Find symbols.  This returns a null Symbol (symbol.IsNull() is true)
  // if not found.
  inline Symbol FindSymbol(absl::string_view key) const;

  // This implements the body of DescriptorPool::Find*ByName().  It should
  // really be a private method of DescriptorPool, but that would require
  // declaring Symbol in descriptor.h, which would drag all kinds of other
  // stuff into the header.  Yay C++.
  Symbol FindByNameHelper(const DescriptorPool* pool, absl::string_view name);

  // These return nullptr if not found.
  inline const FileDescriptor* FindFile(absl::string_view key) const;
  inline const FieldDescriptor* FindExtension(const Descriptor* extendee,
                                              int number) const;
  inline void FindAllExtensions(const Descriptor* extendee,
                                std::vector<const FieldDescriptor*>* out) const;

  // -----------------------------------------------------------------
  // Adding items.

  // These add items to the corresponding tables.  They return false if
  // the key already exists in the table.  For AddSymbol(), the string passed
  // in must be one that was constructed using AllocateString(), as it will
  // be used as a key in the symbols_by_name_ map without copying.
  bool AddSymbol(absl::string_view full_name, Symbol symbol);
  bool AddFile(const FileDescriptor* file);
  bool AddExtension(const FieldDescriptor* field);

  // -----------------------------------------------------------------
  // Allocating memory.

  // Allocate an object which will be reclaimed when the pool is
  // destroyed.  Note that the object's destructor will never be called,
  // so its fields must be plain old data (primitive data types and
  // pointers).  All of the descriptor types are such objects.
  template <typename Type>
  Type* Allocate();

  // Allocate some bytes which will be reclaimed when the pool is
  // destroyed. Memory is aligned to 8 bytes.
  void* AllocateBytes(int size);

  // Create a FlatAllocation for the corresponding sizes.
  // All objects within it will be default constructed.
  // The whole allocation, including the non-trivial objects within, will be
  // destroyed with the pool.
  template <typename... T>
  internal::FlatAllocator::Allocation* CreateFlatAlloc(
      const TypeMap<IntT, T...>& sizes);


 private:
  // All memory allocated in the pool.  Must be first as other objects can
  // point into these.
  struct MiscDeleter {
    void operator()(int* p) const { internal::SizedDelete(p, *p + 8); }
  };
  // Miscellaneous allocations are length prefixed. The paylaod is 8 bytes after
  // the `int` that contains the size. This keeps the payload aligned.
  std::vector<std::unique_ptr<int, MiscDeleter>> misc_allocs_;
  struct FlatAllocDeleter {
    void operator()(internal::FlatAllocator::Allocation* p) const {
      p->Destroy();
    }
  };
  std::vector<
      std::unique_ptr<internal::FlatAllocator::Allocation, FlatAllocDeleter>>
      flat_allocs_;

  SymbolsByNameSet symbols_by_name_;
  FilesByNameSet files_by_name_;
  ExtensionsGroupedByDescriptorMap extensions_;

  struct CheckPoint {
    explicit CheckPoint(const Tables* tables)
        : flat_allocations_before_checkpoint(
              static_cast<int>(tables->flat_allocs_.size())),
          misc_allocations_before_checkpoint(
              static_cast<int>(tables->misc_allocs_.size())),
          pending_symbols_before_checkpoint(
              tables->symbols_after_checkpoint_.size()),
          pending_files_before_checkpoint(
              tables->files_after_checkpoint_.size()),
          pending_extensions_before_checkpoint(
              tables->extensions_after_checkpoint_.size()) {}
    int flat_allocations_before_checkpoint;
    int misc_allocations_before_checkpoint;
    int pending_symbols_before_checkpoint;
    int pending_files_before_checkpoint;
    int pending_extensions_before_checkpoint;
  };
  std::vector<CheckPoint> checkpoints_;
  std::vector<Symbol> symbols_after_checkpoint_;
  std::vector<const FileDescriptor*> files_after_checkpoint_;
  std::vector<std::pair<const Descriptor*, int>> extensions_after_checkpoint_;
};

DescriptorPool::Tables::Tables() {
  well_known_types_.insert({
      {"google.protobuf.DoubleValue", Descriptor::WELLKNOWNTYPE_DOUBLEVALUE},
      {"google.protobuf.FloatValue", Descriptor::WELLKNOWNTYPE_FLOATVALUE},
      {"google.protobuf.Int64Value", Descriptor::WELLKNOWNTYPE_INT64VALUE},
      {"google.protobuf.UInt64Value", Descriptor::WELLKNOWNTYPE_UINT64VALUE},
      {"google.protobuf.Int32Value", Descriptor::WELLKNOWNTYPE_INT32VALUE},
      {"google.protobuf.UInt32Value", Descriptor::WELLKNOWNTYPE_UINT32VALUE},
      {"google.protobuf.StringValue", Descriptor::WELLKNOWNTYPE_STRINGVALUE},
      {"google.protobuf.BytesValue", Descriptor::WELLKNOWNTYPE_BYTESVALUE},
      {"google.protobuf.BoolValue", Descriptor::WELLKNOWNTYPE_BOOLVALUE},
      {"google.protobuf.Any", Descriptor::WELLKNOWNTYPE_ANY},
      {"google.protobuf.FieldMask", Descriptor::WELLKNOWNTYPE_FIELDMASK},
      {"google.protobuf.Duration", Descriptor::WELLKNOWNTYPE_DURATION},
      {"google.protobuf.Timestamp", Descriptor::WELLKNOWNTYPE_TIMESTAMP},
      {"google.protobuf.Value", Descriptor::WELLKNOWNTYPE_VALUE},
      {"google.protobuf.ListValue", Descriptor::WELLKNOWNTYPE_LISTVALUE},
      {"google.protobuf.Struct", Descriptor::WELLKNOWNTYPE_STRUCT},
  });
}

DescriptorPool::Tables::~Tables() { ABSL_DCHECK(checkpoints_.empty()); }

FileDescriptorTables::FileDescriptorTables() {}

FileDescriptorTables::~FileDescriptorTables() {
  delete fields_by_lowercase_name_.load(std::memory_order_acquire);
  delete fields_by_camelcase_name_.load(std::memory_order_acquire);
}

inline const FileDescriptorTables& FileDescriptorTables::GetEmptyInstance() {
  static auto file_descriptor_tables =
      internal::OnShutdownDelete(new FileDescriptorTables());
  return *file_descriptor_tables;
}

void DescriptorPool::Tables::AddCheckpoint() {
  checkpoints_.emplace_back(this);
}

void DescriptorPool::Tables::ClearLastCheckpoint() {
  ABSL_DCHECK(!checkpoints_.empty());
  checkpoints_.pop_back();
  if (checkpoints_.empty()) {
    // All checkpoints have been cleared: we can now commit all of the pending
    // data.
    symbols_after_checkpoint_.clear();
    files_after_checkpoint_.clear();
    extensions_after_checkpoint_.clear();
  }
}

void DescriptorPool::Tables::RollbackToLastCheckpoint() {
  ABSL_DCHECK(!checkpoints_.empty());
  const CheckPoint& checkpoint = checkpoints_.back();

  for (size_t i = checkpoint.pending_symbols_before_checkpoint;
       i < symbols_after_checkpoint_.size(); i++) {
    symbols_by_name_.erase(symbols_after_checkpoint_[i]);
  }
  for (size_t i = checkpoint.pending_files_before_checkpoint;
       i < files_after_checkpoint_.size(); i++) {
    files_by_name_.erase(files_after_checkpoint_[i]);
  }
  for (size_t i = checkpoint.pending_extensions_before_checkpoint;
       i < extensions_after_checkpoint_.size(); i++) {
    extensions_.erase(extensions_after_checkpoint_[i]);
  }

  symbols_after_checkpoint_.resize(
      checkpoint.pending_symbols_before_checkpoint);
  files_after_checkpoint_.resize(checkpoint.pending_files_before_checkpoint);
  extensions_after_checkpoint_.resize(
      checkpoint.pending_extensions_before_checkpoint);

  flat_allocs_.resize(checkpoint.flat_allocations_before_checkpoint);
  misc_allocs_.resize(checkpoint.misc_allocations_before_checkpoint);
  checkpoints_.pop_back();
}

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

inline Symbol DescriptorPool::Tables::FindSymbol(absl::string_view key) const {
  auto it = symbols_by_name_.find(FullNameQuery{key});
  return it == symbols_by_name_.end() ? Symbol() : *it;
}

inline Symbol FileDescriptorTables::FindNestedSymbol(
    const void* parent, absl::string_view name) const {
  auto it = symbols_by_parent_.find(ParentNameQuery{{parent, name}});
  return it == symbols_by_parent_.end() ? Symbol() : *it;
}

Symbol DescriptorPool::Tables::FindByNameHelper(const DescriptorPool* pool,
                                                absl::string_view name) {
  if (pool->mutex_ != nullptr) {
    // Fast path: the Symbol is already cached.  This is just a hash lookup.
    absl::ReaderMutexLock lock(pool->mutex_);
    if (known_bad_symbols_.empty() && known_bad_files_.empty()) {
      Symbol result = FindSymbol(name);
      if (!result.IsNull()) return result;
    }
  }
  absl::MutexLockMaybe lock(pool->mutex_);
  if (pool->fallback_database_ != nullptr) {
    known_bad_symbols_.clear();
    known_bad_files_.clear();
  }
  Symbol result = FindSymbol(name);

  if (result.IsNull() && pool->underlay_ != nullptr) {
    // Symbol not found; check the underlay.
    result = pool->underlay_->tables_->FindByNameHelper(pool->underlay_, name);
  }

  if (result.IsNull()) {
    // Symbol still not found, so check fallback database.
    if (pool->TryFindSymbolInFallbackDatabase(name)) {
      result = FindSymbol(name);
    }
  }

  return result;
}

inline const FileDescriptor* DescriptorPool::Tables::FindFile(
    absl::string_view key) const {
  auto it = files_by_name_.find(key);
  if (it == files_by_name_.end()) return nullptr;
  return *it;
}

inline const FieldDescriptor* FileDescriptorTables::FindFieldByNumber(
    const Descriptor* parent, int number) const {
  // If `number` is within the sequential range, just index into the parent
  // without doing a table lookup.
  if (parent != nullptr &&  //
      1 <= number && number <= parent->sequential_field_limit_) {
    return parent->field(number - 1);
  }

  auto it = fields_by_number_.find(ParentNumberQuery{{parent, number}});
  return it == fields_by_number_.end() ? nullptr : *it;
}

const void* FileDescriptorTables::FindParentForFieldsByMap(
    const FieldDescriptor* field) const {
  if (field->is_extension()) {
    if (field->extension_scope() == nullptr) {
      return field->file();
    } else {
      return field->extension_scope();
    }
  } else {
    return field->containing_type();
  }
}

void FileDescriptorTables::FieldsByLowercaseNamesLazyInitStatic(
    const FileDescriptorTables* tables) {
  tables->FieldsByLowercaseNamesLazyInitInternal();
}

void FileDescriptorTables::FieldsByLowercaseNamesLazyInitInternal() const {
  auto* map = new FieldsByNameMap;
  for (Symbol symbol : symbols_by_parent_) {
    const FieldDescriptor* field = symbol.field_descriptor();
    if (!field) continue;
    (*map)[{FindParentForFieldsByMap(field), field->lowercase_name().c_str()}] =
        field;
  }
  fields_by_lowercase_name_.store(map, std::memory_order_release);
}

inline const FieldDescriptor* FileDescriptorTables::FindFieldByLowercaseName(
    const void* parent, absl::string_view lowercase_name) const {
  absl::call_once(fields_by_lowercase_name_once_,
                  &FileDescriptorTables::FieldsByLowercaseNamesLazyInitStatic,
                  this);
  const auto* fields =
      fields_by_lowercase_name_.load(std::memory_order_acquire);
  auto it = fields->find({parent, lowercase_name});
  if (it == fields->end()) return nullptr;
  return it->second;
}

void FileDescriptorTables::FieldsByCamelcaseNamesLazyInitStatic(
    const FileDescriptorTables* tables) {
  tables->FieldsByCamelcaseNamesLazyInitInternal();
}

void FileDescriptorTables::FieldsByCamelcaseNamesLazyInitInternal() const {
  auto* map = new FieldsByNameMap;
  for (Symbol symbol : symbols_by_parent_) {
    const FieldDescriptor* field = symbol.field_descriptor();
    if (!field) continue;
    (*map)[{FindParentForFieldsByMap(field), field->camelcase_name().c_str()}] =
        field;
  }
  fields_by_camelcase_name_.store(map, std::memory_order_release);
}

inline const FieldDescriptor* FileDescriptorTables::FindFieldByCamelcaseName(
    const void* parent, absl::string_view camelcase_name) const {
  absl::call_once(fields_by_camelcase_name_once_,
                  FileDescriptorTables::FieldsByCamelcaseNamesLazyInitStatic,
                  this);
  auto* fields = fields_by_camelcase_name_.load(std::memory_order_acquire);
  auto it = fields->find({parent, camelcase_name});
  if (it == fields->end()) return nullptr;
  return it->second;
}

inline const EnumValueDescriptor* FileDescriptorTables::FindEnumValueByNumber(
    const EnumDescriptor* parent, int number) const {
  // If `number` is within the sequential range, just index into the parent
  // without doing a table lookup.
  const int base = parent->value(0)->number();
  if (base <= number &&
      number <= static_cast<int64_t>(base) + parent->sequential_value_limit_) {
    return parent->value(number - base);
  }

  auto it = enum_values_by_number_.find(ParentNumberQuery{{parent, number}});
  return it == enum_values_by_number_.end() ? nullptr : *it;
}

inline const EnumValueDescriptor*
FileDescriptorTables::FindEnumValueByNumberCreatingIfUnknown(
    const EnumDescriptor* parent, int number) const {
  // First try, with map of compiled-in values.
  {
    const auto* value = FindEnumValueByNumber(parent, number);
    if (value != nullptr) {
      return value;
    }
  }

  const ParentNumberQuery query{{parent, number}};

  // Second try, with reader lock held on unknown enum values: common case.
  {
    absl::ReaderMutexLock l(&unknown_enum_values_mu_);
    auto it = unknown_enum_values_by_number_.find(query);
    if (it != unknown_enum_values_by_number_.end()) {
      return *it;
    }
  }
  // If not found, try again with writer lock held, and create new descriptor if
  // necessary.
  {
    absl::WriterMutexLock l(&unknown_enum_values_mu_);
    auto it = unknown_enum_values_by_number_.find(query);
    if (it != unknown_enum_values_by_number_.end()) {
      return *it;
    }

    // Create an EnumValueDescriptor dynamically. We don't insert it into the
    // EnumDescriptor (it's not a part of the enum as originally defined), but
    // we do insert it into the table so that we can return the same pointer
    // later.
    std::string enum_value_name = absl::StrFormat(
        "UNKNOWN_ENUM_VALUE_%s_%d", parent->name().c_str(), number);
    auto* pool = DescriptorPool::generated_pool();
    auto* tables = const_cast<DescriptorPool::Tables*>(pool->tables_.get());
    internal::FlatAllocator alloc;
    alloc.PlanArray<EnumValueDescriptor>(1);
    alloc.PlanArray<std::string>(2);

    {
      // Must lock the pool because we will do allocations in the shared arena.
      absl::MutexLockMaybe l2(pool->mutex_);
      alloc.FinalizePlanning(tables);
    }
    EnumValueDescriptor* result = alloc.AllocateArray<EnumValueDescriptor>(1);
    result->all_names_ = alloc.AllocateStrings(
        enum_value_name,
        absl::StrCat(parent->full_name(), ".", enum_value_name));
    result->number_ = number;
    result->type_ = parent;
    result->options_ = &EnumValueOptions::default_instance();
    unknown_enum_values_by_number_.insert(result);
    return result;
  }
}

inline const FieldDescriptor* DescriptorPool::Tables::FindExtension(
    const Descriptor* extendee, int number) const {
  auto it = extensions_.find({extendee, number});
  if (it == extensions_.end()) return nullptr;
  return it->second;
}

inline void DescriptorPool::Tables::FindAllExtensions(
    const Descriptor* extendee,
    std::vector<const FieldDescriptor*>* out) const {
  ExtensionsGroupedByDescriptorMap::const_iterator it =
      extensions_.lower_bound(std::make_pair(extendee, 0));
  for (; it != extensions_.end() && it->first.first == extendee; ++it) {
    out->push_back(it->second);
  }
}

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

bool DescriptorPool::Tables::AddSymbol(absl::string_view full_name,
                                       Symbol symbol) {
  ABSL_DCHECK_EQ(full_name, symbol.full_name());
  if (symbols_by_name_.insert(symbol).second) {
    symbols_after_checkpoint_.push_back(symbol);
    return true;
  } else {
    return false;
  }
}

bool FileDescriptorTables::AddAliasUnderParent(const void* parent,
                                               absl::string_view name,
                                               Symbol symbol) {
  ABSL_DCHECK_EQ(name, symbol.parent_name_key().second);
  ABSL_DCHECK_EQ(parent, symbol.parent_name_key().first);
  return symbols_by_parent_.insert(symbol).second;
}

bool DescriptorPool::Tables::AddFile(const FileDescriptor* file) {
  if (files_by_name_.insert(file).second) {
    files_after_checkpoint_.push_back(file);
    return true;
  } else {
    return false;
  }
}

void FileDescriptorTables::FinalizeTables() {}

bool FileDescriptorTables::AddFieldByNumber(FieldDescriptor* field) {
  // Skip fields that are at the start of the sequence.
  if (field->containing_type() != nullptr && field->number() >= 1 &&
      field->number() <= field->containing_type()->sequential_field_limit_) {
    if (field->is_extension()) {
      // Conflicts with the field that already exists in the sequential range.
      return false;
    }
    // Only return true if the field at that index matches. Otherwise it
    // conflicts with the existing field in the sequential range.
    return field->containing_type()->field(field->number() - 1) == field;
  }

  return fields_by_number_.insert(field).second;
}

bool FileDescriptorTables::AddEnumValueByNumber(EnumValueDescriptor* value) {
  // Skip values that are at the start of the sequence.
  const int base = value->type()->value(0)->number();
  if (base <= value->number() &&
      value->number() <=
          static_cast<int64_t>(base) + value->type()->sequential_value_limit_)
    return true;
  return enum_values_by_number_.insert(value).second;
}

bool DescriptorPool::Tables::AddExtension(const FieldDescriptor* field) {
  auto it_inserted =
      extensions_.insert({{field->containing_type(), field->number()}, field});
  if (it_inserted.second) {
    extensions_after_checkpoint_.push_back(it_inserted.first->first);
    return true;
  } else {
    return false;
  }
}

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

template <typename Type>
Type* DescriptorPool::Tables::Allocate() {
  static_assert(std::is_trivially_destructible<Type>::value, "");
  static_assert(alignof(Type) <= 8, "");
  return ::new (AllocateBytes(sizeof(Type))) Type{};
}

void* DescriptorPool::Tables::AllocateBytes(int size) {
  if (size == 0) return nullptr;
  void* p = ::operator new(size + RoundUpTo<8>(sizeof(int)));
  int* sizep = static_cast<int*>(p);
  misc_allocs_.emplace_back(sizep);
  *sizep = size;
  return static_cast<char*>(p) + RoundUpTo<8>(sizeof(int));
}

template <typename... T>
internal::FlatAllocator::Allocation* DescriptorPool::Tables::CreateFlatAlloc(
    const TypeMap<IntT, T...>& sizes) {
  auto ends = CalculateEnds(sizes);
  using FlatAlloc = internal::FlatAllocator::Allocation;

  int last_end = ends.template Get<
      typename std::tuple_element<sizeof...(T) - 1, std::tuple<T...>>::type>();
  size_t total_size =
      last_end + RoundUpTo<FlatAlloc::kMaxAlign>(sizeof(FlatAlloc));
  char* data = static_cast<char*>(::operator new(total_size));
  auto* res = ::new (data) FlatAlloc(ends);
  flat_allocs_.emplace_back(res);

  return res;
}

void FileDescriptorTables::BuildLocationsByPath(
    std::pair<const FileDescriptorTables*, const SourceCodeInfo*>* p) {
  for (int i = 0, len = p->second->location_size(); i < len; ++i) {
    const SourceCodeInfo_Location* loc = &p->second->location().Get(i);
    p->first->locations_by_path_[absl::StrJoin(loc->path(), ",")] = loc;
  }
}

const SourceCodeInfo_Location* FileDescriptorTables::GetSourceLocation(
    const std::vector<int>& path, const SourceCodeInfo* info) const {
  std::pair<const FileDescriptorTables*, const SourceCodeInfo*> p(
      std::make_pair(this, info));
  absl::call_once(locations_by_path_once_,
                  FileDescriptorTables::BuildLocationsByPath, &p);
  auto it = locations_by_path_.find(absl::StrJoin(path, ","));
  if (it == locations_by_path_.end()) return nullptr;
  return it->second;
}

// ===================================================================
// DescriptorPool

DescriptorPool::ErrorCollector::~ErrorCollector() {}

DescriptorPool::DescriptorPool()
    : mutex_(nullptr),
      fallback_database_(nullptr),
      default_error_collector_(nullptr),
      underlay_(nullptr),
      tables_(new Tables),
      enforce_dependencies_(true),
      lazily_build_dependencies_(false),
      allow_unknown_(false),
      enforce_weak_(false),
      disallow_enforce_utf8_(false),
      deprecated_legacy_json_field_conflicts_(false) {}

DescriptorPool::DescriptorPool(DescriptorDatabase* fallback_database,
                               ErrorCollector* error_collector)
    : mutex_(new absl::Mutex),
      fallback_database_(fallback_database),
      default_error_collector_(error_collector),
      underlay_(nullptr),
      tables_(new Tables),
      enforce_dependencies_(true),
      lazily_build_dependencies_(false),
      allow_unknown_(false),
      enforce_weak_(false),
      disallow_enforce_utf8_(false),
      deprecated_legacy_json_field_conflicts_(false) {}

DescriptorPool::DescriptorPool(const DescriptorPool* underlay)
    : mutex_(nullptr),
      fallback_database_(nullptr),
      default_error_collector_(nullptr),
      underlay_(underlay),
      tables_(new Tables),
      enforce_dependencies_(true),
      lazily_build_dependencies_(false),
      allow_unknown_(false),
      enforce_weak_(false),
      disallow_enforce_utf8_(false),
      deprecated_legacy_json_field_conflicts_(false) {}

DescriptorPool::~DescriptorPool() {
  if (mutex_ != nullptr) delete mutex_;
}

// DescriptorPool::BuildFile() defined later.
// DescriptorPool::BuildFileCollectingErrors() defined later.

void DescriptorPool::InternalDontEnforceDependencies() {
  enforce_dependencies_ = false;
}

void DescriptorPool::AddUnusedImportTrackFile(absl::string_view file_name,
                                              bool is_error) {
  unused_import_track_files_[file_name] = is_error;
}


void DescriptorPool::ClearUnusedImportTrackFiles() {
  unused_import_track_files_.clear();
}

bool DescriptorPool::InternalIsFileLoaded(absl::string_view filename) const {
  absl::MutexLockMaybe lock(mutex_);
  return tables_->FindFile(filename) != nullptr;
}

// generated_pool ====================================================

namespace {


EncodedDescriptorDatabase* GeneratedDatabase() {
  static auto generated_database =
      internal::OnShutdownDelete(new EncodedDescriptorDatabase());
  return generated_database;
}

DescriptorPool* NewGeneratedPool() {
  auto generated_pool = new DescriptorPool(GeneratedDatabase());
  generated_pool->InternalSetLazilyBuildDependencies();
  return generated_pool;
}

}  // anonymous namespace

DescriptorDatabase* DescriptorPool::internal_generated_database() {
  return GeneratedDatabase();
}

DescriptorPool* DescriptorPool::internal_generated_pool() {
  static DescriptorPool* generated_pool =
      internal::OnShutdownDelete(NewGeneratedPool());
  return generated_pool;
}

const DescriptorPool* DescriptorPool::generated_pool() {
  const DescriptorPool* pool = internal_generated_pool();
  // Ensure that descriptor.proto gets registered in the generated pool. It is a
  // special case because it is included in the full runtime. We have to avoid
  // registering it pre-main, because we need to ensure that the linker
  // --gc-sections step can strip out the full runtime if it is unused.
  DescriptorProto::descriptor();
  return pool;
}


void DescriptorPool::InternalAddGeneratedFile(
    const void* encoded_file_descriptor, int size) {
  // So, this function is called in the process of initializing the
  // descriptors for generated proto classes.  Each generated .pb.cc file
  // has an internal procedure called AddDescriptors() which is called at
  // process startup, and that function calls this one in order to register
  // the raw bytes of the FileDescriptorProto representing the file.
  //
  // We do not actually construct the descriptor objects right away.  We just
  // hang on to the bytes until they are actually needed.  We actually construct
  // the descriptor the first time one of the following things happens:
  // * Someone calls a method like descriptor(), GetDescriptor(), or
  //   GetReflection() on the generated types, which requires returning the
  //   descriptor or an object based on it.
  // * Someone looks up the descriptor in DescriptorPool::generated_pool().
  //
  // Once one of these happens, the DescriptorPool actually parses the
  // FileDescriptorProto and generates a FileDescriptor (and all its children)
  // based on it.
  //
  // Note that FileDescriptorProto is itself a generated protocol message.
  // Therefore, when we parse one, we have to be very careful to avoid using
  // any descriptor-based operations, since this might cause infinite recursion
  // or deadlock.
  ABSL_CHECK(GeneratedDatabase()->Add(encoded_file_descriptor, size));
}


// Find*By* methods ==================================================

// TODO(kenton):  There's a lot of repeated code here, but I'm not sure if
//   there's any good way to factor it out.  Think about this some time when
//   there's nothing more important to do (read: never).

const FileDescriptor* DescriptorPool::FindFileByName(
    absl::string_view name) const {
  absl::MutexLockMaybe lock(mutex_);
  if (fallback_database_ != nullptr) {
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
  }
  const FileDescriptor* result = tables_->FindFile(name);
  if (result != nullptr) return result;
  if (underlay_ != nullptr) {
    result = underlay_->FindFileByName(name);
    if (result != nullptr) return result;
  }
  if (TryFindFileInFallbackDatabase(name)) {
    result = tables_->FindFile(name);
    if (result != nullptr) return result;
  }
  return nullptr;
}

const FileDescriptor* DescriptorPool::FindFileContainingSymbol(
    absl::string_view symbol_name) const {
  absl::MutexLockMaybe lock(mutex_);
  if (fallback_database_ != nullptr) {
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
  }
  Symbol result = tables_->FindSymbol(symbol_name);
  if (!result.IsNull()) return result.GetFile();
  if (underlay_ != nullptr) {
    const FileDescriptor* file_result =
        underlay_->FindFileContainingSymbol(symbol_name);
    if (file_result != nullptr) return file_result;
  }
  if (TryFindSymbolInFallbackDatabase(symbol_name)) {
    result = tables_->FindSymbol(symbol_name);
    if (!result.IsNull()) return result.GetFile();
  }
  return nullptr;
}

const Descriptor* DescriptorPool::FindMessageTypeByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).descriptor();
}

const FieldDescriptor* DescriptorPool::FindFieldByName(
    absl::string_view name) const {
  if (const FieldDescriptor* field =
          tables_->FindByNameHelper(this, name).field_descriptor()) {
    if (!field->is_extension()) {
      return field;
    }
  }
  return nullptr;
}

const FieldDescriptor* DescriptorPool::FindExtensionByName(
    absl::string_view name) const {
  if (const FieldDescriptor* field =
          tables_->FindByNameHelper(this, name).field_descriptor()) {
    if (field->is_extension()) {
      return field;
    }
  }
  return nullptr;
}

const OneofDescriptor* DescriptorPool::FindOneofByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).oneof_descriptor();
}

const EnumDescriptor* DescriptorPool::FindEnumTypeByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).enum_descriptor();
}

const EnumValueDescriptor* DescriptorPool::FindEnumValueByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).enum_value_descriptor();
}

const ServiceDescriptor* DescriptorPool::FindServiceByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).service_descriptor();
}

const MethodDescriptor* DescriptorPool::FindMethodByName(
    absl::string_view name) const {
  return tables_->FindByNameHelper(this, name).method_descriptor();
}

const FieldDescriptor* DescriptorPool::FindExtensionByNumber(
    const Descriptor* extendee, int number) const {
  if (extendee->extension_range_count() == 0) return nullptr;
  // A faster path to reduce lock contention in finding extensions, assuming
  // most extensions will be cache hit.
  if (mutex_ != nullptr) {
    absl::ReaderMutexLock lock(mutex_);
    const FieldDescriptor* result = tables_->FindExtension(extendee, number);
    if (result != nullptr) {
      return result;
    }
  }
  absl::MutexLockMaybe lock(mutex_);
  if (fallback_database_ != nullptr) {
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
  }
  const FieldDescriptor* result = tables_->FindExtension(extendee, number);
  if (result != nullptr) {
    return result;
  }
  if (underlay_ != nullptr) {
    result = underlay_->FindExtensionByNumber(extendee, number);
    if (result != nullptr) return result;
  }
  if (TryFindExtensionInFallbackDatabase(extendee, number)) {
    result = tables_->FindExtension(extendee, number);
    if (result != nullptr) {
      return result;
    }
  }
  return nullptr;
}

const FieldDescriptor* DescriptorPool::InternalFindExtensionByNumberNoLock(
    const Descriptor* extendee, int number) const {
  if (extendee->extension_range_count() == 0) return nullptr;

  const FieldDescriptor* result = tables_->FindExtension(extendee, number);
  if (result != nullptr) {
    return result;
  }

  if (underlay_ != nullptr) {
    result = underlay_->InternalFindExtensionByNumberNoLock(extendee, number);
    if (result != nullptr) return result;
  }

  return nullptr;
}

const FieldDescriptor* DescriptorPool::FindExtensionByPrintableName(
    const Descriptor* extendee, absl::string_view printable_name) const {
  if (extendee->extension_range_count() == 0) return nullptr;
  const FieldDescriptor* result = FindExtensionByName(printable_name);
  if (result != nullptr && result->containing_type() == extendee) {
    return result;
  }
  if (extendee->options().message_set_wire_format()) {
    // MessageSet extensions may be identified by type name.
    const Descriptor* type = FindMessageTypeByName(printable_name);
    if (type != nullptr) {
      // Look for a matching extension in the foreign type's scope.
      const int type_extension_count = type->extension_count();
      for (int i = 0; i < type_extension_count; i++) {
        const FieldDescriptor* extension = type->extension(i);
        if (extension->containing_type() == extendee &&
            extension->type() == FieldDescriptor::TYPE_MESSAGE &&
            extension->is_optional() && extension->message_type() == type) {
          // Found it.
          return extension;
        }
      }
    }
  }
  return nullptr;
}

void DescriptorPool::FindAllExtensions(
    const Descriptor* extendee,
    std::vector<const FieldDescriptor*>* out) const {
  absl::MutexLockMaybe lock(mutex_);
  if (fallback_database_ != nullptr) {
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
  }

  // Initialize tables_->extensions_ from the fallback database first
  // (but do this only once per descriptor).
  if (fallback_database_ != nullptr &&
      tables_->extensions_loaded_from_db_.count(extendee) == 0) {
    std::vector<int> numbers;
    if (fallback_database_->FindAllExtensionNumbers(extendee->full_name(),
                                                    &numbers)) {
      for (int number : numbers) {
        if (tables_->FindExtension(extendee, number) == nullptr) {
          TryFindExtensionInFallbackDatabase(extendee, number);
        }
      }
      tables_->extensions_loaded_from_db_.insert(extendee);
    }
  }

  tables_->FindAllExtensions(extendee, out);
  if (underlay_ != nullptr) {
    underlay_->FindAllExtensions(extendee, out);
  }
}


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

const FieldDescriptor* Descriptor::FindFieldByNumber(int key) const {
  const FieldDescriptor* result = file()->tables_->FindFieldByNumber(this, key);
  if (result == nullptr || result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const FieldDescriptor* Descriptor::FindFieldByLowercaseName(
    absl::string_view key) const {
  const FieldDescriptor* result =
      file()->tables_->FindFieldByLowercaseName(this, key);
  if (result == nullptr || result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const FieldDescriptor* Descriptor::FindFieldByCamelcaseName(
    absl::string_view key) const {
  const FieldDescriptor* result =
      file()->tables_->FindFieldByCamelcaseName(this, key);
  if (result == nullptr || result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const FieldDescriptor* Descriptor::FindFieldByName(
    absl::string_view key) const {
  const FieldDescriptor* field =
      file()->tables_->FindNestedSymbol(this, key).field_descriptor();
  return field != nullptr && !field->is_extension() ? field : nullptr;
}

const OneofDescriptor* Descriptor::FindOneofByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).oneof_descriptor();
}

const FieldDescriptor* Descriptor::FindExtensionByName(
    absl::string_view key) const {
  const FieldDescriptor* field =
      file()->tables_->FindNestedSymbol(this, key).field_descriptor();
  return field != nullptr && field->is_extension() ? field : nullptr;
}

const FieldDescriptor* Descriptor::FindExtensionByLowercaseName(
    absl::string_view key) const {
  const FieldDescriptor* result =
      file()->tables_->FindFieldByLowercaseName(this, key);
  if (result == nullptr || !result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const FieldDescriptor* Descriptor::FindExtensionByCamelcaseName(
    absl::string_view key) const {
  const FieldDescriptor* result =
      file()->tables_->FindFieldByCamelcaseName(this, key);
  if (result == nullptr || !result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const Descriptor* Descriptor::FindNestedTypeByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).descriptor();
}

const EnumDescriptor* Descriptor::FindEnumTypeByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).enum_descriptor();
}

const EnumValueDescriptor* Descriptor::FindEnumValueByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).enum_value_descriptor();
}

const FieldDescriptor* Descriptor::map_key() const {
  if (!options().map_entry()) return nullptr;
  ABSL_DCHECK_EQ(field_count(), 2);
  return field(0);
}

const FieldDescriptor* Descriptor::map_value() const {
  if (!options().map_entry()) return nullptr;
  ABSL_DCHECK_EQ(field_count(), 2);
  return field(1);
}

const EnumValueDescriptor* EnumDescriptor::FindValueByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).enum_value_descriptor();
}

const EnumValueDescriptor* EnumDescriptor::FindValueByNumber(int key) const {
  return file()->tables_->FindEnumValueByNumber(this, key);
}

const EnumValueDescriptor* EnumDescriptor::FindValueByNumberCreatingIfUnknown(
    int key) const {
  return file()->tables_->FindEnumValueByNumberCreatingIfUnknown(this, key);
}

const MethodDescriptor* ServiceDescriptor::FindMethodByName(
    absl::string_view key) const {
  return file()->tables_->FindNestedSymbol(this, key).method_descriptor();
}

const Descriptor* FileDescriptor::FindMessageTypeByName(
    absl::string_view key) const {
  return tables_->FindNestedSymbol(this, key).descriptor();
}

const EnumDescriptor* FileDescriptor::FindEnumTypeByName(
    absl::string_view key) const {
  return tables_->FindNestedSymbol(this, key).enum_descriptor();
}

const EnumValueDescriptor* FileDescriptor::FindEnumValueByName(
    absl::string_view key) const {
  return tables_->FindNestedSymbol(this, key).enum_value_descriptor();
}

const ServiceDescriptor* FileDescriptor::FindServiceByName(
    absl::string_view key) const {
  return tables_->FindNestedSymbol(this, key).service_descriptor();
}

const FieldDescriptor* FileDescriptor::FindExtensionByName(
    absl::string_view key) const {
  const FieldDescriptor* field =
      tables_->FindNestedSymbol(this, key).field_descriptor();
  return field != nullptr && field->is_extension() ? field : nullptr;
}

const FieldDescriptor* FileDescriptor::FindExtensionByLowercaseName(
    absl::string_view key) const {
  const FieldDescriptor* result = tables_->FindFieldByLowercaseName(this, key);
  if (result == nullptr || !result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

const FieldDescriptor* FileDescriptor::FindExtensionByCamelcaseName(
    absl::string_view key) const {
  const FieldDescriptor* result = tables_->FindFieldByCamelcaseName(this, key);
  if (result == nullptr || !result->is_extension()) {
    return nullptr;
  } else {
    return result;
  }
}

void Descriptor::ExtensionRange::CopyTo(
    DescriptorProto_ExtensionRange* proto) const {
  proto->set_start(this->start);
  proto->set_end(this->end);
  if (options_ != &ExtensionRangeOptions::default_instance()) {
    *proto->mutable_options() = *options_;
  }
}

const Descriptor::ExtensionRange*
Descriptor::FindExtensionRangeContainingNumber(int number) const {
  // Linear search should be fine because we don't expect a message to have
  // more than a couple extension ranges.
  for (int i = 0; i < extension_range_count(); i++) {
    if (number >= extension_range(i)->start &&
        number < extension_range(i)->end) {
      return extension_range(i);
    }
  }
  return nullptr;
}

const Descriptor::ReservedRange* Descriptor::FindReservedRangeContainingNumber(
    int number) const {
  // TODO(chrisn): Consider a non-linear search.
  for (int i = 0; i < reserved_range_count(); i++) {
    if (number >= reserved_range(i)->start && number < reserved_range(i)->end) {
      return reserved_range(i);
    }
  }
  return nullptr;
}

const EnumDescriptor::ReservedRange*
EnumDescriptor::FindReservedRangeContainingNumber(int number) const {
  // TODO(chrisn): Consider a non-linear search.
  for (int i = 0; i < reserved_range_count(); i++) {
    if (number >= reserved_range(i)->start &&
        number <= reserved_range(i)->end) {
      return reserved_range(i);
    }
  }
  return nullptr;
}

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

bool DescriptorPool::TryFindFileInFallbackDatabase(
    absl::string_view name) const {
  if (fallback_database_ == nullptr) return false;

  if (tables_->known_bad_files_.contains(name)) return false;

  // NOINLINE to reduce the stack cost of the operation in the caller.
  const auto find_file = [](DescriptorDatabase& database,
                            absl::string_view filename,
                            FileDescriptorProto& output) PROTOBUF_NOINLINE {
    return database.FindFileByName(std::string(filename), &output);
  };

  auto file_proto = absl::make_unique<FileDescriptorProto>();
  if (!find_file(*fallback_database_, name, *file_proto) ||
      BuildFileFromDatabase(*file_proto) == nullptr) {
    tables_->known_bad_files_.emplace(name);
    return false;
  }
  return true;
}

bool DescriptorPool::IsSubSymbolOfBuiltType(absl::string_view name) const {
  auto prefix = std::string(name);
  for (;;) {
    std::string::size_type dot_pos = prefix.find_last_of('.');
    if (dot_pos == std::string::npos) {
      break;
    }
    prefix = prefix.substr(0, dot_pos);
    Symbol symbol = tables_->FindSymbol(prefix);
    // If the symbol type is anything other than PACKAGE, then its complete
    // definition is already known.
    if (!symbol.IsNull() && !symbol.IsPackage()) {
      return true;
    }
  }
  if (underlay_ != nullptr) {
    // Check to see if any prefix of this symbol exists in the underlay.
    return underlay_->IsSubSymbolOfBuiltType(name);
  }
  return false;
}

bool DescriptorPool::TryFindSymbolInFallbackDatabase(
    absl::string_view name) const {
  if (fallback_database_ == nullptr) return false;

  if (tables_->known_bad_symbols_.contains(name)) return false;

  std::string name_string(name);
  auto file_proto = absl::make_unique<FileDescriptorProto>();
  if (  // We skip looking in the fallback database if the name is a sub-symbol
        // of any descriptor that already exists in the descriptor pool (except
        // for package descriptors).  This is valid because all symbols except
        // for packages are defined in a single file, so if the symbol exists
        // then we should already have its definition.
        //
        // The other reason to do this is to support "overriding" type
        // definitions by merging two databases that define the same type. (Yes,
        // people do this.)  The main difficulty with making this work is that
        // FindFileContainingSymbol() is allowed to return both false positives
        // (e.g., SimpleDescriptorDatabase, UpgradedDescriptorDatabase) and
        // false negatives (e.g. ProtoFileParser, SourceTreeDescriptorDatabase).
        // When two such databases are merged, looking up a non-existent
        // sub-symbol of a type that already exists in the descriptor pool can
        // result in an attempt to load multiple definitions of the same type.
        // The check below avoids this.
      IsSubSymbolOfBuiltType(name)

      // Look up file containing this symbol in fallback database.
      || !fallback_database_->FindFileContainingSymbol(name_string,
                                                       file_proto.get())

      // Check if we've already built this file. If so, it apparently doesn't
      // contain the symbol we're looking for.  Some DescriptorDatabases
      // return false positives.
      || tables_->FindFile(file_proto->name()) != nullptr

      // Build the file.
      || BuildFileFromDatabase(*file_proto) == nullptr) {
    tables_->known_bad_symbols_.insert(std::move(name_string));
    return false;
  }

  return true;
}

bool DescriptorPool::TryFindExtensionInFallbackDatabase(
    const Descriptor* containing_type, int field_number) const {
  if (fallback_database_ == nullptr) return false;

  auto file_proto = absl::make_unique<FileDescriptorProto>();
  if (!fallback_database_->FindFileContainingExtension(
          containing_type->full_name(), field_number, file_proto.get())) {
    return false;
  }

  if (tables_->FindFile(file_proto->name()) != nullptr) {
    // We've already loaded this file, and it apparently doesn't contain the
    // extension we're looking for.  Some DescriptorDatabases return false
    // positives.
    return false;
  }

  if (BuildFileFromDatabase(*file_proto) == nullptr) {
    return false;
  }

  return true;
}

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

bool FieldDescriptor::is_map_message_type() const {
  return type_descriptor_.message_type->options().map_entry();
}

std::string FieldDescriptor::DefaultValueAsString(
    bool quote_string_type) const {
  ABSL_CHECK(has_default_value()) << "No default value";
  switch (cpp_type()) {
    case CPPTYPE_INT32:
      return absl::StrCat(default_value_int32_t());
    case CPPTYPE_INT64:
      return absl::StrCat(default_value_int64_t());
    case CPPTYPE_UINT32:
      return absl::StrCat(default_value_uint32_t());
    case CPPTYPE_UINT64:
      return absl::StrCat(default_value_uint64_t());
    case CPPTYPE_FLOAT:
      return io::SimpleFtoa(default_value_float());
    case CPPTYPE_DOUBLE:
      return io::SimpleDtoa(default_value_double());
    case CPPTYPE_BOOL:
      return default_value_bool() ? "true" : "false";
    case CPPTYPE_STRING:
      if (quote_string_type) {
        return absl::StrCat("\"", absl::CEscape(default_value_string()), "\"");
      } else {
        if (type() == TYPE_BYTES) {
          return absl::CEscape(default_value_string());
        } else {
          return default_value_string();
        }
      }
    case CPPTYPE_ENUM:
      return default_value_enum()->name();
    case CPPTYPE_MESSAGE:
      ABSL_DLOG(FATAL) << "Messages can't have default values!";
      break;
  }
  ABSL_LOG(FATAL) << "Can't get here: failed to get default value as string";
  return "";
}

// CopyTo methods ====================================================

void FileDescriptor::CopyTo(FileDescriptorProto* proto) const {
  CopyHeadingTo(proto);

  for (int i = 0; i < dependency_count(); i++) {
    proto->add_dependency(dependency(i)->name());
  }

  for (int i = 0; i < public_dependency_count(); i++) {
    proto->add_public_dependency(public_dependencies_[i]);
  }

  for (int i = 0; i < weak_dependency_count(); i++) {
    proto->add_weak_dependency(weak_dependencies_[i]);
  }

  for (int i = 0; i < message_type_count()

Coverage Report

Created: 2023-11-19 07:09