text: // 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/stubs/hash.h>
  #include <map>
  #include <memory>
  #ifndef _SHARED_PTR_H
  #include <google/protobuf/stubs/shared_ptr.h>
  #endif
  #include <set>
  #include <string>
  #include <vector>
  #include <algorithm>
  #include <limits>
  
  #include <google/protobuf/descriptor.h>
  #include <google/protobuf/descriptor_database.h>
  #include <google/protobuf/descriptor.pb.h>
  #include <google/protobuf/dynamic_message.h>
  #include <google/protobuf/generated_message_util.h>
  #include <google/protobuf/text_format.h>
  #include <google/protobuf/unknown_field_set.h>
  #include <google/protobuf/wire_format.h>
  #include <google/protobuf/io/strtod.h>
  #include <google/protobuf/io/coded_stream.h>
  #include <google/protobuf/io/tokenizer.h>
  #include <google/protobuf/io/zero_copy_stream_impl.h>
  #include <google/protobuf/stubs/common.h>
  #include <google/protobuf/stubs/logging.h>
  #include <google/protobuf/stubs/mutex.h>
  #include <google/protobuf/stubs/once.h>
  #include <google/protobuf/stubs/stringprintf.h>
  #include <google/protobuf/stubs/strutil.h>
  #include <google/protobuf/stubs/substitute.h>
  #include <google/protobuf/stubs/map_util.h>
  #include <google/protobuf/stubs/stl_util.h>
  
  #undef PACKAGE  // autoheader #defines this.  :(
  
  namespace google {
  
  namespace protobuf {
  
  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";
    }
    GOOGLE_LOG(FATAL) << "can't reach here.";
    return NULL;
  }
  
  static const char * const kNonLinkedWeakMessageReplacementName = "google.protobuf.Empty";
  
  #if !defined(_MSC_VER) || _MSC_VER >= 1900
  const int FieldDescriptor::kMaxNumber;
  const int FieldDescriptor::kFirstReservedNumber;
  const int FieldDescriptor::kLastReservedNumber;
  #endif
  
  namespace {
  
  // Note:  I distrust ctype.h due to locales.
  char ToUpper(char ch) {
    return (ch >= 'a' && ch <= 'z') ? (ch - 'a' + 'A') : ch;
  }
  
  char ToLower(char ch) {
    return (ch >= 'A' && ch <= 'Z') ? (ch - 'A' + 'a') : ch;
  }
  
  string ToCamelCase(const string& input, bool lower_first) {
    bool capitalize_next = !lower_first;
    string result;
    result.reserve(input.size());
  
    for (int i = 0; i < input.size(); i++) {
      if (input[i] == '_') {
        capitalize_next = true;
      } else if (capitalize_next) {
        result.push_back(ToUpper(input[i]));
        capitalize_next = false;
      } else {
        result.push_back(input[i]);
      }
    }
  
    // Lower-case the first letter.
    if (lower_first && !result.empty()) {
      result[0] = ToLower(result[0]);
    }
  
    return result;
  }
  
  string ToJsonName(const string& input) {
    bool capitalize_next = false;
    string result;
    result.reserve(input.size());
  
    for (int i = 0; i < input.size(); i++) {
      if (input[i] == '_') {
        capitalize_next = true;
      } else if (capitalize_next) {
        result.push_back(ToUpper(input[i]));
        capitalize_next = false;
      } else {
        result.push_back(input[i]);
      }
    }
  
    return result;
  }
  
  string EnumValueToPascalCase(const string& input) {
    bool next_upper = true;
    string result;
    result.reserve(input.size());
  
    for (int i = 0; i < input.size(); i++) {
      if (input[i] == '_') {
        next_upper = true;
      } else {
        if (next_upper) {
          result.push_back(ToUpper(input[i]));
        } else {
          result.push_back(ToLower(input[i]));
        }
        next_upper = false;
      }
    }
  
    return result;
  }
  
  // Class to remove an enum prefix from enum values.
  class PrefixRemover {
   public:
    PrefixRemover(StringPiece prefix) {
      // Strip underscores and lower-case the prefix.
      for (int i = 0; i < prefix.size(); i++) {
        if (prefix[i] != '_') {
          prefix_ += ascii_tolower(prefix[i]);
        }
      }
    }
  
    // Tries to remove the enum prefix from this enum value.
    // If this is not possible, returns the input verbatim.
    string MaybeRemove(StringPiece 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 (ascii_tolower(str[i]) != prefix_[j++]) {
          return str.as_string();
        }
      }
  
      // If we didn't make it through the prefix, we've failed to strip the
      // prefix.
      if (j < prefix_.size()) {
        return str.as_string();
      }
  
      // 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 str.as_string();
      }
  
      // We successfully stripped the prefix.
      str.remove_prefix(i);
      return str.as_string();
    }
  
   private:
    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.  Unfortunately STL doesn't provide hash functions for pair<>,
  // so we must invent our own.
  //
  // TODO(kenton):  Use StringPiece rather than const char* in keys?  It would
  //   be a lot cleaner but we'd just have to convert it back to const char*
  //   for the open source release.
  
  typedef pair<const void*, const char*> PointerStringPair;
  
  struct PointerStringPairEqual {
    inline bool operator()(const PointerStringPair& a,
                           const PointerStringPair& b) const {
      return a.first == b.first && strcmp(a.second, b.second) == 0;
    }
  };
  
  template<typename PairType>
  struct PointerIntegerPairHash {
    size_t operator()(const PairType& p) const {
      // FIXME(kenton):  What is the best way to compute this hash?  I have
      // no idea!  This seems a bit better than an XOR.
      return reinterpret_cast<intptr_t>(p.first) * ((1 << 16) - 1) + p.second;
    }
  
  #ifdef _MSC_VER
    // Used only by MSVC and platforms where hash_map is not available.
    static const size_t bucket_size = 4;
    static const size_t min_buckets = 8;
  #endif
    inline bool operator()(const PairType& a, const PairType& b) const {
      return a.first < b.first ||
            (a.first == b.first && a.second < b.second);
    }
  };
  
  typedef pair<const Descriptor*, int> DescriptorIntPair;
  typedef pair<const EnumDescriptor*, int> EnumIntPair;
  
  struct PointerStringPairHash {
    size_t operator()(const PointerStringPair& p) const {
      // FIXME(kenton):  What is the best way to compute this hash?  I have
      // no idea!  This seems a bit better than an XOR.
      hash<const char*> cstring_hash;
      return reinterpret_cast<intptr_t>(p.first) * ((1 << 16) - 1) +
             cstring_hash(p.second);
    }
  
  #ifdef _MSC_VER
    // Used only by MSVC and platforms where hash_map is not available.
    static const size_t bucket_size = 4;
    static const size_t min_buckets = 8;
  #endif
    inline bool operator()(const PointerStringPair& a,
                           const PointerStringPair& b) const {
      if (a.first < b.first) return true;
      if (a.first > b.first) return false;
      return strcmp(a.second, b.second) < 0;
    }
  };
  
  
  struct Symbol {
    enum Type {
      NULL_SYMBOL, MESSAGE, FIELD, ONEOF, ENUM, ENUM_VALUE, SERVICE, METHOD,
      PACKAGE
    };
    Type type;
    union {
      const Descriptor* descriptor;
      const FieldDescriptor* field_descriptor;
      const OneofDescriptor* oneof_descriptor;
      const EnumDescriptor* enum_descriptor;
      const EnumValueDescriptor* enum_value_descriptor;
      const ServiceDescriptor* service_descriptor;
      const MethodDescriptor* method_descriptor;
      const FileDescriptor* package_file_descriptor;
    };
  
    inline Symbol() : type(NULL_SYMBOL) { descriptor = NULL; }
    inline bool IsNull() const { return type == NULL_SYMBOL; }
    inline bool IsType() const {
      return type == MESSAGE || type == ENUM;
    }
    inline bool IsAggregate() const {
      return type == MESSAGE || type == PACKAGE
          || type == ENUM || type == SERVICE;
    }
  
  #define CONSTRUCTOR(TYPE, TYPE_CONSTANT, FIELD)  \
    inline explicit Symbol(const TYPE* value) {    \
      type = TYPE_CONSTANT;                        \
      this->FIELD = value;                         \
    }
  
    CONSTRUCTOR(Descriptor         , MESSAGE   , descriptor             )
    CONSTRUCTOR(FieldDescriptor    , FIELD     , field_descriptor       )
    CONSTRUCTOR(OneofDescriptor    , ONEOF     , oneof_descriptor       )
    CONSTRUCTOR(EnumDescriptor     , ENUM      , enum_descriptor        )
    CONSTRUCTOR(EnumValueDescriptor, ENUM_VALUE, enum_value_descriptor  )
    CONSTRUCTOR(ServiceDescriptor  , SERVICE   , service_descriptor     )
    CONSTRUCTOR(MethodDescriptor   , METHOD    , method_descriptor      )
    CONSTRUCTOR(FileDescriptor     , PACKAGE   , package_file_descriptor)
  #undef CONSTRUCTOR
  
    const FileDescriptor* GetFile() const {
      switch (type) {
        case NULL_SYMBOL: return NULL;
        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 PACKAGE    : return package_file_descriptor;
      }
      return NULL;
    }
  };
  
  const Symbol kNullSymbol;
  
  typedef hash_map<const char*, Symbol,
                   hash<const char*>, streq>
    SymbolsByNameMap;
  typedef hash_map<PointerStringPair, Symbol,
                   PointerStringPairHash, PointerStringPairEqual>
    SymbolsByParentMap;
  typedef hash_map<const char*, const FileDescriptor*,
                   hash<const char*>, streq>
    FilesByNameMap;
  typedef hash_map<PointerStringPair, const FieldDescriptor*,
                   PointerStringPairHash, PointerStringPairEqual>
    FieldsByNameMap;
  typedef hash_map<DescriptorIntPair, const FieldDescriptor*,
                   PointerIntegerPairHash<DescriptorIntPair> >
    FieldsByNumberMap;
  typedef hash_map<EnumIntPair, const EnumValueDescriptor*,
                   PointerIntegerPairHash<EnumIntPair> >
    EnumValuesByNumberMap;
  // 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.
  typedef map<DescriptorIntPair, const FieldDescriptor*>
    ExtensionsGroupedByDescriptorMap;
  typedef hash_map<string, const SourceCodeInfo_Location*> LocationsByPathMap;
  
  set<string>* allowed_proto3_extendees_ = NULL;
  GOOGLE_PROTOBUF_DECLARE_ONCE(allowed_proto3_extendees_init_);
  
  void DeleteAllowedProto3Extendee() {
    delete allowed_proto3_extendees_;
  }
  
  void InitAllowedProto3Extendee() {
    allowed_proto3_extendees_ = new set<string>;
    const char* kOptionNames[] = {
        "FileOptions",      "MessageOptions", "FieldOptions", "EnumOptions",
        "EnumValueOptions", "ServiceOptions", "MethodOptions"};
    for (int i = 0; i < GOOGLE_ARRAYSIZE(kOptionNames); ++i) {
      // 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(string("google.protobuf.") +
                                        kOptionNames[i]);
      // Split the word to trick the opensource processing scripts so they
      // will keep the origial package name.
      allowed_proto3_extendees_->insert(string("proto") + "2." + kOptionNames[i]);
    }
  
    google::protobuf::internal::OnShutdown(&DeleteAllowedProto3Extendee);
  }
  
  // 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 string& name) {
    ::google::protobuf::GoogleOnceInit(&allowed_proto3_extendees_init_, &InitAllowedProto3Extendee);
    return allowed_proto3_extendees_->find(name) !=
           allowed_proto3_extendees_->end();
  }
  
  }  // anonymous namespace
  
  // ===================================================================
  // 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_ == NULL.
    vector<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_ == NULL.
    hash_set<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.
    hash_set<string> known_bad_symbols_;
  
    // The set of descriptors for which we've already loaded the full
    // set of extensions numbers from fallback_database_.
    hash_set<const Descriptor*> extensions_loaded_from_db_;
  
    // -----------------------------------------------------------------
    // Finding items.
  
    // Find symbols.  This returns a null Symbol (symbol.IsNull() is true)
    // if not found.
    inline Symbol FindSymbol(const string& 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, const string& name);
  
    // These return NULL if not found.
    inline const FileDescriptor* FindFile(const string& key) const;
    inline const FieldDescriptor* FindExtension(const Descriptor* extendee,
                                                int number);
    inline void FindAllExtensions(const Descriptor* extendee,
                                  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(const string& 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 an array of objects which will be reclaimed when the
    // pool in destroyed.  Again, destructors are never called.
    template<typename Type> Type* AllocateArray(int count);
  
    // Allocate a string which will be destroyed when the pool is destroyed.
    // The string is initialized to the given value for convenience.
    string* AllocateString(const string& value);
  
    // Allocate a protocol message object.  Some older versions of GCC have
    // trouble understanding explicit template instantiations in some cases, so
    // in those cases we have to pass a dummy pointer of the right type as the
    // parameter instead of specifying the type explicitly.
    template<typename Type> Type* AllocateMessage(Type* dummy = NULL);
  
    // Allocate a FileDescriptorTables object.
    FileDescriptorTables* AllocateFileTables();
  
   private:
    vector<string*> strings_;    // All strings in the pool.
    vector<Message*> messages_;  // All messages in the pool.
    vector<FileDescriptorTables*> file_tables_;  // All file tables in the pool.
    vector<void*> allocations_;  // All other memory allocated in the pool.
  
    SymbolsByNameMap      symbols_by_name_;
    FilesByNameMap        files_by_name_;
    ExtensionsGroupedByDescriptorMap extensions_;
  
    struct CheckPoint {
      explicit CheckPoint(const Tables* tables)
        : strings_before_checkpoint(tables->strings_.size()),
          messages_before_checkpoint(tables->messages_.size()),
          file_tables_before_checkpoint(tables->file_tables_.size()),
          allocations_before_checkpoint(tables->allocations_.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 strings_before_checkpoint;
      int messages_before_checkpoint;
      int file_tables_before_checkpoint;
      int allocations_before_checkpoint;
      int pending_symbols_before_checkpoint;
      int pending_files_before_checkpoint;
      int pending_extensions_before_checkpoint;
    };
    vector<CheckPoint> checkpoints_;
    vector<const char*      > symbols_after_checkpoint_;
    vector<const char*      > files_after_checkpoint_;
    vector<DescriptorIntPair> extensions_after_checkpoint_;
  
    // Allocate some bytes which will be reclaimed when the pool is
    // destroyed.
    void* AllocateBytes(int size);
  };
  
  // 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.
  
    // Find symbols.  These return a null Symbol (symbol.IsNull() is true)
    // if not found.
    inline Symbol FindNestedSymbol(const void* parent,
                                   const string& name) const;
    inline Symbol FindNestedSymbolOfType(const void* parent,
                                         const string& name,
                                         const Symbol::Type type) const;
  
    // These return NULL if not found.
    inline const FieldDescriptor* FindFieldByNumber(
      const Descriptor* parent, int number) const;
    inline const FieldDescriptor* FindFieldByLowercaseName(
      const void* parent, const string& lowercase_name) const;
    inline const FieldDescriptor* FindFieldByCamelcaseName(
      const void* parent, const string& 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.  For AddAliasUnderParent(), the
    // string passed in must be one that was constructed using AllocateString(),
    // as it will be used as a key in the symbols_by_parent_ map without copying.
    bool AddAliasUnderParent(const void* parent, const string& name,
                             Symbol symbol);
    bool AddFieldByNumber(const FieldDescriptor* field);
    bool AddEnumValueByNumber(const EnumValueDescriptor* value);
  
    // Adds the field to the lowercase_name and camelcase_name maps.  Never
    // fails because we allow duplicates; the first field by the name wins.
    void AddFieldByStylizedNames(const FieldDescriptor* field);
  
    // Populates p->first->locations_by_path_ from p->second.
    // Unusual signature dictated by GoogleOnceDynamic.
    static void BuildLocationsByPath(
        pair<const FileDescriptorTables*, const SourceCodeInfo*>* p);
  
    // Returns the location denoted by the specified path through info,
    // or NULL 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 vector<int>& path, const SourceCodeInfo* info) const;
  
   private:
    SymbolsByParentMap    symbols_by_parent_;
    FieldsByNameMap       fields_by_lowercase_name_;
    FieldsByNameMap       fields_by_camelcase_name_;
    FieldsByNumberMap     fields_by_number_;       // Not including extensions.
    EnumValuesByNumberMap enum_values_by_number_;
    mutable EnumValuesByNumberMap unknown_enum_values_by_number_
        GOOGLE_GUARDED_BY(unknown_enum_values_mu_);
  
    // Populated on first request to save space, hence constness games.
    mutable GoogleOnceDynamic 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 Mutex unknown_enum_values_mu_;
  };
  
  DescriptorPool::Tables::Tables()
      // Start some hash_map and hash_set objects with a small # of buckets
      : known_bad_files_(3),
        known_bad_symbols_(3),
        extensions_loaded_from_db_(3),
        symbols_by_name_(3),
        files_by_name_(3) {}
  
  
  DescriptorPool::Tables::~Tables() {
    GOOGLE_DCHECK(checkpoints_.empty());
    // Note that the deletion order is important, since the destructors of some
    // messages may refer to objects in allocations_.
    STLDeleteElements(&messages_);
    for (int i = 0; i < allocations_.size(); i++) {
      operator delete(allocations_[i]);
    }
    STLDeleteElements(&strings_);
    STLDeleteElements(&file_tables_);
  }
  
  FileDescriptorTables::FileDescriptorTables()
      // Initialize all the hash tables to start out with a small # of buckets
      : symbols_by_parent_(3),
        fields_by_lowercase_name_(3),
        fields_by_camelcase_name_(3),
        fields_by_number_(3),
        enum_values_by_number_(3),
        unknown_enum_values_by_number_(3) {
  }
  
  FileDescriptorTables::~FileDescriptorTables() {}
  
  namespace {
  
  FileDescriptorTables* file_descriptor_tables_ = NULL;
  GOOGLE_PROTOBUF_DECLARE_ONCE(file_descriptor_tables_once_init_);
  
  void DeleteFileDescriptorTables() {
    delete file_descriptor_tables_;
    file_descriptor_tables_ = NULL;
  }
  
  void InitFileDescriptorTables() {
    file_descriptor_tables_ = new FileDescriptorTables();
    internal::OnShutdown(&DeleteFileDescriptorTables);
  }
  
  inline void InitFileDescriptorTablesOnce() {
    ::google::protobuf::GoogleOnceInit(
        &file_descriptor_tables_once_init_, &InitFileDescriptorTables);
  }
  
  }  // anonymous namespace
  
  inline const FileDescriptorTables& FileDescriptorTables::GetEmptyInstance() {
    InitFileDescriptorTablesOnce();
    return *file_descriptor_tables_;
  }
  
  void DescriptorPool::Tables::AddCheckpoint() {
    checkpoints_.push_back(CheckPoint(this));
  }
  
  void DescriptorPool::Tables::ClearLastCheckpoint() {
    GOOGLE_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() {
    GOOGLE_DCHECK(!checkpoints_.empty());
    const CheckPoint& checkpoint = checkpoints_.back();
  
    for (int i = checkpoint.pending_symbols_before_checkpoint;
         i < symbols_after_checkpoint_.size();
         i++) {
      symbols_by_name_.erase(symbols_after_checkpoint_[i]);
    }
    for (int i = checkpoint.pending_files_before_checkpoint;
         i < files_after_checkpoint_.size();
         i++) {
      files_by_name_.erase(files_after_checkpoint_[i]);
    }
    for (int 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);
  
    STLDeleteContainerPointers(
        strings_.begin() + checkpoint.strings_before_checkpoint, strings_.end());
    STLDeleteContainerPointers(
        messages_.begin() + checkpoint.messages_before_checkpoint,
        messages_.end());
    STLDeleteContainerPointers(
        file_tables_.begin() + checkpoint.file_tables_before_checkpoint,
        file_tables_.end());
    for (int i = checkpoint.allocations_before_checkpoint;
         i < allocations_.size();
         i++) {
      operator delete(allocations_[i]);
    }
  
    strings_.resize(checkpoint.strings_before_checkpoint);
    messages_.resize(checkpoint.messages_before_checkpoint);
    file_tables_.resize(checkpoint.file_tables_before_checkpoint);
    allocations_.resize(checkpoint.allocations_before_checkpoint);
    checkpoints_.pop_back();
  }
  
  // -------------------------------------------------------------------
  
  inline Symbol DescriptorPool::Tables::FindSymbol(const string& key) const {
    const Symbol* result = FindOrNull(symbols_by_name_, key.c_str());
    if (result == NULL) {
      return kNullSymbol;
    } else {
      return *result;
    }
  }
  
  inline Symbol FileDescriptorTables::FindNestedSymbol(
      const void* parent, const string& name) const {
    const Symbol* result =
      FindOrNull(symbols_by_parent_, PointerStringPair(parent, name.c_str()));
    if (result == NULL) {
      return kNullSymbol;
    } else {
      return *result;
    }
  }
  
  inline Symbol FileDescriptorTables::FindNestedSymbolOfType(
      const void* parent, const string& name, const Symbol::Type type) const {
    Symbol result = FindNestedSymbol(parent, name);
    if (result.type != type) return kNullSymbol;
    return result;
  }
  
  Symbol DescriptorPool::Tables::FindByNameHelper(
      const DescriptorPool* pool, const string& name) {
    MutexLockMaybe lock(pool->mutex_);
    known_bad_symbols_.clear();
    known_bad_files_.clear();
    Symbol result = FindSymbol(name);
  
    if (result.IsNull() && pool->underlay_ != NULL) {
      // 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(
      const string& key) const {
    return FindPtrOrNull(files_by_name_, key.c_str());
  }
  
  inline const FieldDescriptor* FileDescriptorTables::FindFieldByNumber(
      const Descriptor* parent, int number) const {
    return FindPtrOrNull(fields_by_number_, std::make_pair(parent, number));
  }
  
  inline const FieldDescriptor* FileDescriptorTables::FindFieldByLowercaseName(
      const void* parent, const string& lowercase_name) const {
    return FindPtrOrNull(fields_by_lowercase_name_,
                         PointerStringPair(parent, lowercase_name.c_str()));
  }
  
  inline const FieldDescriptor* FileDescriptorTables::FindFieldByCamelcaseName(
      const void* parent, const string& camelcase_name) const {
    return FindPtrOrNull(fields_by_camelcase_name_,
                         PointerStringPair(parent, camelcase_name.c_str()));
  }
  
  inline const EnumValueDescriptor* FileDescriptorTables::FindEnumValueByNumber(
      const EnumDescriptor* parent, int number) const {
    return FindPtrOrNull(enum_values_by_number_, std::make_pair(parent, number));
  }
  
  inline const EnumValueDescriptor*
  FileDescriptorTables::FindEnumValueByNumberCreatingIfUnknown(
      const EnumDescriptor* parent, int number) const {
    // First try, with map of compiled-in values.
    {
      const EnumValueDescriptor* desc =
          FindPtrOrNull(enum_values_by_number_, std::make_pair(parent, number));
      if (desc != NULL) {
        return desc;
      }
    }
    // Second try, with reader lock held on unknown enum values: common case.
    {
      ReaderMutexLock l(&unknown_enum_values_mu_);
      const EnumValueDescriptor* desc = FindPtrOrNull(
          unknown_enum_values_by_number_, std::make_pair(parent, number));
      if (desc != NULL) {
        return desc;
      }
    }
    // If not found, try again with writer lock held, and create new descriptor if
    // necessary.
    {
      WriterMutexLock l(&unknown_enum_values_mu_);
      const EnumValueDescriptor* desc = FindPtrOrNull(
          unknown_enum_values_by_number_, std::make_pair(parent, number));
      if (desc != NULL) {
        return desc;
      }
  
      // 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.
      string enum_value_name = StringPrintf(
          "UNKNOWN_ENUM_VALUE_%s_%d", parent->name().c_str(), number);
      DescriptorPool::Tables* tables =
          const_cast<DescriptorPool::Tables*>(DescriptorPool::generated_pool()->
                                              tables_.get());
      EnumValueDescriptor* result = tables->Allocate<EnumValueDescriptor>();
      result->name_ = tables->AllocateString(enum_value_name);
      result->full_name_ = tables->AllocateString(parent->full_name() +
                                                  "." + enum_value_name);
      result->number_ = number;
      result->type_ = parent;
      result->options_ = &EnumValueOptions::default_instance();
      InsertIfNotPresent(&unknown_enum_values_by_number_,
                         std::make_pair(parent, number), result);
      return result;
    }
  }
  
  
  inline const FieldDescriptor* DescriptorPool::Tables::FindExtension(
      const Descriptor* extendee, int number) {
    return FindPtrOrNull(extensions_, std::make_pair(extendee, number));
  }
  
  inline void DescriptorPool::Tables::FindAllExtensions(
      const Descriptor* extendee, 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(
      const string& full_name, Symbol symbol) {
    if (InsertIfNotPresent(&symbols_by_name_, full_name.c_str(), symbol)) {
      symbols_after_checkpoint_.push_back(full_name.c_str());
      return true;
    } else {
      return false;
    }
  }
  
  bool FileDescriptorTables::AddAliasUnderParent(
      const void* parent, const string& name, Symbol symbol) {
    PointerStringPair by_parent_key(parent, name.c_str());
    return InsertIfNotPresent(&symbols_by_parent_, by_parent_key, symbol);
  }
  
  bool DescriptorPool::Tables::AddFile(const FileDescriptor* file) {
    if (InsertIfNotPresent(&files_by_name_, file->name().c_str(), file)) {
      files_after_checkpoint_.push_back(file->name().c_str());
      return true;
    } else {
      return false;
    }
  }
  
  void FileDescriptorTables::AddFieldByStylizedNames(
      const FieldDescriptor* field) {
    const void* parent;
    if (field->is_extension()) {
      if (field->extension_scope() == NULL) {
        parent = field->file();
      } else {
        parent = field->extension_scope();
      }
    } else {
      parent = field->containing_type();
    }
  
    PointerStringPair lowercase_key(parent, field->lowercase_name().c_str());
    InsertIfNotPresent(&fields_by_lowercase_name_, lowercase_key, field);
  
    PointerStringPair camelcase_key(parent, field->camelcase_name().c_str());
    InsertIfNotPresent(&fields_by_camelcase_name_, camelcase_key, field);
  }
  
  bool FileDescriptorTables::AddFieldByNumber(const FieldDescriptor* field) {
    DescriptorIntPair key(field->containing_type(), field->number());
    return InsertIfNotPresent(&fields_by_number_, key, field);
  }
  
  bool FileDescriptorTables::AddEnumValueByNumber(
      const EnumValueDescriptor* value) {
    EnumIntPair key(value->type(), value->number());
    return InsertIfNotPresent(&enum_values_by_number_, key, value);
  }
  
  bool DescriptorPool::Tables::AddExtension(const FieldDescriptor* field) {
    DescriptorIntPair key(field->containing_type(), field->number());
    if (InsertIfNotPresent(&extensions_, key, field)) {
      extensions_after_checkpoint_.push_back(key);
      return true;
    } else {
      return false;
    }
  }
  
  // -------------------------------------------------------------------
  
  template<typename Type>
  Type* DescriptorPool::Tables::Allocate() {
    return reinterpret_cast<Type*>(AllocateBytes(sizeof(Type)));
  }
  
  template<typename Type>
  Type* DescriptorPool::Tables::AllocateArray(int count) {
    return reinterpret_cast<Type*>(AllocateBytes(sizeof(Type) * count));
  }
  
  string* DescriptorPool::Tables::AllocateString(const string& value) {
    string* result = new string(value);
    strings_.push_back(result);
    return result;
  }
  
  template<typename Type>
  Type* DescriptorPool::Tables::AllocateMessage(Type* /* dummy */) {
    Type* result = new Type;
    messages_.push_back(result);
    return result;
  }
  
  FileDescriptorTables* DescriptorPool::Tables::AllocateFileTables() {
    FileDescriptorTables* result = new FileDescriptorTables;
    file_tables_.push_back(result);
    return result;
  }
  
  void* DescriptorPool::Tables::AllocateBytes(int size) {
    // TODO(kenton):  Would it be worthwhile to implement this in some more
    // sophisticated way?  Probably not for the open source release, but for
    // internal use we could easily plug in one of our existing memory pool
    // allocators...
    if (size == 0) return NULL;
  
    void* result = operator new(size);
    allocations_.push_back(result);
    return result;
  }
  
  void FileDescriptorTables::BuildLocationsByPath(
      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_[Join(loc->path(), ",")] = loc;
    }
  }
  
  const SourceCodeInfo_Location* FileDescriptorTables::GetSourceLocation(
      const vector<int>& path, const SourceCodeInfo* info) const {
    pair<const FileDescriptorTables*, const SourceCodeInfo*> p(
        std::make_pair(this, info));
    locations_by_path_once_.Init(&FileDescriptorTables::BuildLocationsByPath, &p);
    return FindPtrOrNull(locations_by_path_, Join(path, ","));
  }
  
  // ===================================================================
  // DescriptorPool
  
  DescriptorPool::ErrorCollector::~ErrorCollector() {}
  
  DescriptorPool::DescriptorPool()
    : mutex_(NULL),
      fallback_database_(NULL),
      default_error_collector_(NULL),
      underlay_(NULL),
      tables_(new Tables),
      enforce_dependencies_(true),
      allow_unknown_(false),
      enforce_weak_(false) {}
  
  DescriptorPool::DescriptorPool(DescriptorDatabase* fallback_database,
                                 ErrorCollector* error_collector)
    : mutex_(new Mutex),
      fallback_database_(fallback_database),
      default_error_collector_(error_collector),
      underlay_(NULL),
      tables_(new Tables),
      enforce_dependencies_(true),
      allow_unknown_(false),
      enforce_weak_(false) {
  }
  
  DescriptorPool::DescriptorPool(const DescriptorPool* underlay)
    : mutex_(NULL),
      fallback_database_(NULL),
      default_error_collector_(NULL),
      underlay_(underlay),
      tables_(new Tables),
      enforce_dependencies_(true),
      allow_unknown_(false),
      enforce_weak_(false) {}
  
  DescriptorPool::~DescriptorPool() {
    if (mutex_ != NULL) delete mutex_;
  }
  
  // DescriptorPool::BuildFile() defined later.
  // DescriptorPool::BuildFileCollectingErrors() defined later.
  
  void DescriptorPool::InternalDontEnforceDependencies() {
    enforce_dependencies_ = false;
  }
  
  void DescriptorPool::AddUnusedImportTrackFile(const string& file_name) {
    unused_import_track_files_.insert(file_name);
  }
  
  void DescriptorPool::ClearUnusedImportTrackFiles() {
    unused_import_track_files_.clear();
  }
  
  bool DescriptorPool::InternalIsFileLoaded(const string& filename) const {
    MutexLockMaybe lock(mutex_);
    return tables_->FindFile(filename) != NULL;
  }
  
  // generated_pool ====================================================
  
  namespace {
  
  
  EncodedDescriptorDatabase* generated_database_ = NULL;
  DescriptorPool* generated_pool_ = NULL;
  GOOGLE_PROTOBUF_DECLARE_ONCE(generated_pool_init_);
  
  void DeleteGeneratedPool() {
    delete generated_database_;
    generated_database_ = NULL;
    delete generated_pool_;
    generated_pool_ = NULL;
  }
  
  static void InitGeneratedPool() {
    generated_database_ = new EncodedDescriptorDatabase;
    generated_pool_ = new DescriptorPool(generated_database_);
  
    internal::OnShutdown(&DeleteGeneratedPool);
  }
  
  inline void InitGeneratedPoolOnce() {
    ::google::protobuf::GoogleOnceInit(&generated_pool_init_, &InitGeneratedPool);
  }
  
  }  // anonymous namespace
  
  const DescriptorPool* DescriptorPool::generated_pool() {
    InitGeneratedPoolOnce();
    return generated_pool_;
  }
  
  
  DescriptorPool* DescriptorPool::internal_generated_pool() {
    InitGeneratedPoolOnce();
    return generated_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.
    InitGeneratedPoolOnce();
    GOOGLE_CHECK(generated_database_->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(const string& name) const {
    MutexLockMaybe lock(mutex_);
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
    const FileDescriptor* result = tables_->FindFile(name);
    if (result != NULL) return result;
    if (underlay_ != NULL) {
      result = underlay_->FindFileByName(name);
      if (result != NULL) return result;
    }
    if (TryFindFileInFallbackDatabase(name)) {
      result = tables_->FindFile(name);
      if (result != NULL) return result;
    }
    return NULL;
  }
  
  const FileDescriptor* DescriptorPool::FindFileContainingSymbol(
      const string& symbol_name) const {
    MutexLockMaybe lock(mutex_);
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
    Symbol result = tables_->FindSymbol(symbol_name);
    if (!result.IsNull()) return result.GetFile();
    if (underlay_ != NULL) {
      const FileDescriptor* file_result =
        underlay_->FindFileContainingSymbol(symbol_name);
      if (file_result != NULL) return file_result;
    }
    if (TryFindSymbolInFallbackDatabase(symbol_name)) {
      result = tables_->FindSymbol(symbol_name);
      if (!result.IsNull()) return result.GetFile();
    }
    return NULL;
  }
  
  const Descriptor* DescriptorPool::FindMessageTypeByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::MESSAGE) ? result.descriptor : NULL;
  }
  
  const FieldDescriptor* DescriptorPool::FindFieldByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    if (result.type == Symbol::FIELD &&
        !result.field_descriptor->is_extension()) {
      return result.field_descriptor;
    } else {
      return NULL;
    }
  }
  
  const FieldDescriptor* DescriptorPool::FindExtensionByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    if (result.type == Symbol::FIELD &&
        result.field_descriptor->is_extension()) {
      return result.field_descriptor;
    } else {
      return NULL;
    }
  }
  
  const OneofDescriptor* DescriptorPool::FindOneofByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::ONEOF) ? result.oneof_descriptor : NULL;
  }
  
  const EnumDescriptor* DescriptorPool::FindEnumTypeByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::ENUM) ? result.enum_descriptor : NULL;
  }
  
  const EnumValueDescriptor* DescriptorPool::FindEnumValueByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::ENUM_VALUE) ?
      result.enum_value_descriptor : NULL;
  }
  
  const ServiceDescriptor* DescriptorPool::FindServiceByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::SERVICE) ? result.service_descriptor : NULL;
  }
  
  const MethodDescriptor* DescriptorPool::FindMethodByName(
      const string& name) const {
    Symbol result = tables_->FindByNameHelper(this, name);
    return (result.type == Symbol::METHOD) ? result.method_descriptor : NULL;
  }
  
  const FieldDescriptor* DescriptorPool::FindExtensionByNumber(
      const Descriptor* extendee, int number) const {
    MutexLockMaybe lock(mutex_);
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
    const FieldDescriptor* result = tables_->FindExtension(extendee, number);
    if (result != NULL) {
      return result;
    }
    if (underlay_ != NULL) {
      result = underlay_->FindExtensionByNumber(extendee, number);
      if (result != NULL) return result;
    }
    if (TryFindExtensionInFallbackDatabase(extendee, number)) {
      result = tables_->FindExtension(extendee, number);
      if (result != NULL) {
        return result;
      }
    }
    return NULL;
  }
  
  void DescriptorPool::FindAllExtensions(
      const Descriptor* extendee, vector<const FieldDescriptor*>* out) const {
    MutexLockMaybe lock(mutex_);
    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_ != NULL &&
        tables_->extensions_loaded_from_db_.count(extendee) == 0) {
      vector<int> numbers;
      if (fallback_database_->FindAllExtensionNumbers(extendee->full_name(),
                                                      &numbers)) {
        for (int i = 0; i < numbers.size(); ++i) {
          int number = numbers[i];
          if (tables_->FindExtension(extendee, number) == NULL) {
            TryFindExtensionInFallbackDatabase(extendee, number);
          }
        }
        tables_->extensions_loaded_from_db_.insert(extendee);
      }
    }
  
    tables_->FindAllExtensions(extendee, out);
    if (underlay_ != NULL) {
      underlay_->FindAllExtensions(extendee, out);
    }
  }
  
  
  // -------------------------------------------------------------------
  
  const FieldDescriptor*
  Descriptor::FindFieldByNumber(int key) const {
    const FieldDescriptor* result =
      file()->tables_->FindFieldByNumber(this, key);
    if (result == NULL || result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindFieldByLowercaseName(const string& key) const {
    const FieldDescriptor* result =
      file()->tables_->FindFieldByLowercaseName(this, key);
    if (result == NULL || result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindFieldByCamelcaseName(const string& key) const {
    const FieldDescriptor* result =
      file()->tables_->FindFieldByCamelcaseName(this, key);
    if (result == NULL || result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindFieldByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::FIELD);
    if (!result.IsNull() && !result.field_descriptor->is_extension()) {
      return result.field_descriptor;
    } else {
      return NULL;
    }
  }
  
  const OneofDescriptor*
  Descriptor::FindOneofByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::ONEOF);
    if (!result.IsNull()) {
      return result.oneof_descriptor;
    } else {
      return NULL;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindExtensionByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::FIELD);
    if (!result.IsNull() && result.field_descriptor->is_extension()) {
      return result.field_descriptor;
    } else {
      return NULL;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindExtensionByLowercaseName(const string& key) const {
    const FieldDescriptor* result =
      file()->tables_->FindFieldByLowercaseName(this, key);
    if (result == NULL || !result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const FieldDescriptor*
  Descriptor::FindExtensionByCamelcaseName(const string& key) const {
    const FieldDescriptor* result =
      file()->tables_->FindFieldByCamelcaseName(this, key);
    if (result == NULL || !result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const Descriptor*
  Descriptor::FindNestedTypeByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::MESSAGE);
    if (!result.IsNull()) {
      return result.descriptor;
    } else {
      return NULL;
    }
  }
  
  const EnumDescriptor*
  Descriptor::FindEnumTypeByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::ENUM);
    if (!result.IsNull()) {
      return result.enum_descriptor;
    } else {
      return NULL;
    }
  }
  
  const EnumValueDescriptor*
  Descriptor::FindEnumValueByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::ENUM_VALUE);
    if (!result.IsNull()) {
      return result.enum_value_descriptor;
    } else {
      return NULL;
    }
  }
  
  const EnumValueDescriptor*
  EnumDescriptor::FindValueByName(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::ENUM_VALUE);
    if (!result.IsNull()) {
      return result.enum_value_descriptor;
    } else {
      return NULL;
    }
  }
  
  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(const string& key) const {
    Symbol result =
      file()->tables_->FindNestedSymbolOfType(this, key, Symbol::METHOD);
    if (!result.IsNull()) {
      return result.method_descriptor;
    } else {
      return NULL;
    }
  }
  
  const Descriptor*
  FileDescriptor::FindMessageTypeByName(const string& key) const {
    Symbol result = tables_->FindNestedSymbolOfType(this, key, Symbol::MESSAGE);
    if (!result.IsNull()) {
      return result.descriptor;
    } else {
      return NULL;
    }
  }
  
  const EnumDescriptor*
  FileDescriptor::FindEnumTypeByName(const string& key) const {
    Symbol result = tables_->FindNestedSymbolOfType(this, key, Symbol::ENUM);
    if (!result.IsNull()) {
      return result.enum_descriptor;
    } else {
      return NULL;
    }
  }
  
  const EnumValueDescriptor*
  FileDescriptor::FindEnumValueByName(const string& key) const {
    Symbol result =
      tables_->FindNestedSymbolOfType(this, key, Symbol::ENUM_VALUE);
    if (!result.IsNull()) {
      return result.enum_value_descriptor;
    } else {
      return NULL;
    }
  }
  
  const ServiceDescriptor*
  FileDescriptor::FindServiceByName(const string& key) const {
    Symbol result = tables_->FindNestedSymbolOfType(this, key, Symbol::SERVICE);
    if (!result.IsNull()) {
      return result.service_descriptor;
    } else {
      return NULL;
    }
  }
  
  const FieldDescriptor*
  FileDescriptor::FindExtensionByName(const string& key) const {
    Symbol result = tables_->FindNestedSymbolOfType(this, key, Symbol::FIELD);
    if (!result.IsNull() && result.field_descriptor->is_extension()) {
      return result.field_descriptor;
    } else {
      return NULL;
    }
  }
  
  const FieldDescriptor*
  FileDescriptor::FindExtensionByLowercaseName(const string& key) const {
    const FieldDescriptor* result = tables_->FindFieldByLowercaseName(this, key);
    if (result == NULL || !result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  const FieldDescriptor*
  FileDescriptor::FindExtensionByCamelcaseName(const string& key) const {
    const FieldDescriptor* result = tables_->FindFieldByCamelcaseName(this, key);
    if (result == NULL || !result->is_extension()) {
      return NULL;
    } else {
      return result;
    }
  }
  
  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 NULL;
  }
  
  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 NULL;
  }
  
  // -------------------------------------------------------------------
  
  bool DescriptorPool::TryFindFileInFallbackDatabase(const string& name) const {
    if (fallback_database_ == NULL) return false;
  
    if (tables_->known_bad_files_.count(name) > 0) return false;
  
    FileDescriptorProto file_proto;
    if (!fallback_database_->FindFileByName(name, &file_proto) ||
        BuildFileFromDatabase(file_proto) == NULL) {
      tables_->known_bad_files_.insert(name);
      return false;
    }
    return true;
  }
  
  bool DescriptorPool::IsSubSymbolOfBuiltType(const string& name) const {
    string prefix = name;
    for (;;) {
      string::size_type dot_pos = prefix.find_last_of('.');
      if (dot_pos == 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.type != Symbol::PACKAGE) {
        return true;
      }
    }
    if (underlay_ != NULL) {
      // Check to see if any prefix of this symbol exists in the underlay.
      return underlay_->IsSubSymbolOfBuiltType(name);
    }
    return false;
  }
  
  bool DescriptorPool::TryFindSymbolInFallbackDatabase(const string& name) const {
    if (fallback_database_ == NULL) return false;
  
    if (tables_->known_bad_symbols_.count(name) > 0) return false;
  
    FileDescriptorProto file_proto;
    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, &file_proto)
  
        // 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()) != NULL
  
        // Build the file.
        || BuildFileFromDatabase(file_proto) == NULL) {
      tables_->known_bad_symbols_.insert(name);
      return false;
    }
  
    return true;
  }
  
  bool DescriptorPool::TryFindExtensionInFallbackDatabase(
      const Descriptor* containing_type, int field_number) const {
    if (fallback_database_ == NULL) return false;
  
    FileDescriptorProto file_proto;
    if (!fallback_database_->FindFileContainingExtension(
          containing_type->full_name(), field_number, &file_proto)) {
      return false;
    }
  
    if (tables_->FindFile(file_proto.name()) != NULL) {
      // 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) == NULL) {
      return false;
    }
  
    return true;
  }
  
  // ===================================================================
  
  bool FieldDescriptor::is_map() const {
    return type() == TYPE_MESSAGE && message_type()->options().map_entry();
  }
  
  string FieldDescriptor::DefaultValueAsString(bool quote_string_type) const {
    GOOGLE_CHECK(has_default_value()) << "No default value";
    switch (cpp_type()) {
      case CPPTYPE_INT32:
        return SimpleItoa(default_value_int32());
        break;
      case CPPTYPE_INT64:
        return SimpleItoa(default_value_int64());
        break;
      case CPPTYPE_UINT32:
        return SimpleItoa(default_value_uint32());
        break;
      case CPPTYPE_UINT64:
        return SimpleItoa(default_value_uint64());
        break;
      case CPPTYPE_FLOAT:
        return SimpleFtoa(default_value_float());
        break;
      case CPPTYPE_DOUBLE:
        return SimpleDtoa(default_value_double());
        break;
      case CPPTYPE_BOOL:
        return default_value_bool() ? "true" : "false";
        break;
      case CPPTYPE_STRING:
        if (quote_string_type) {
          return "\"" + CEscape(default_value_string()) + "\"";
        } else {
          if (type() == TYPE_BYTES) {
            return CEscape(default_value_string());
          } else {
            return default_value_string();
          }
        }
        break;
      case CPPTYPE_ENUM:
        return default_value_enum()->name();
        break;
      case CPPTYPE_MESSAGE:
        GOOGLE_LOG(DFATAL) << "Messages can't have default values!";
        break;
    }
    GOOGLE_LOG(FATAL) << "Can't get here: failed to get default value as string";
    return "";
  }
  
  // CopyTo methods ====================================================
  
  void FileDescriptor::CopyTo(FileDescriptorProto* proto) const {
    proto->set_name(name());
    if (!package().empty()) proto->set_package(package());
    // TODO(liujisi): Also populate when syntax="proto2".
    if (syntax() == SYNTAX_PROTO3) proto->set_syntax(SyntaxName(syntax()));
  
    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(); i++) {
      message_type(i)->CopyTo(proto->add_message_type());
    }
    for (int i = 0; i < enum_type_count(); i++) {
      enum_type(i)->CopyTo(proto->add_enum_type());
    }
    for (int i = 0; i < service_count(); i++) {
      service(i)->CopyTo(proto->add_service());
    }
    for (int i = 0; i < extension_count(); i++) {
      extension(i)->CopyTo(proto->add_extension());
    }
  
    if (&options() != &FileOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void FileDescriptor::CopyJsonNameTo(FileDescriptorProto* proto) const {
    if (message_type_count() != proto->message_type_size() ||
        extension_count() != proto->extension_size()) {
      GOOGLE_LOG(ERROR) << "Cannot copy json_name to a proto of a different size.";
      return;
    }
    for (int i = 0; i < message_type_count(); i++) {
      message_type(i)->CopyJsonNameTo(proto->mutable_message_type(i));
    }
    for (int i = 0; i < extension_count(); i++) {
      extension(i)->CopyJsonNameTo(proto->mutable_extension(i));
    }
  }
  
  void FileDescriptor::CopySourceCodeInfoTo(FileDescriptorProto* proto) const {
    if (source_code_info_ &&
        source_code_info_ != &SourceCodeInfo::default_instance()) {
      proto->mutable_source_code_info()->CopyFrom(*source_code_info_);
    }
  }
  
  void Descriptor::CopyTo(DescriptorProto* proto) const {
    proto->set_name(name());
  
    for (int i = 0; i < field_count(); i++) {
      field(i)->CopyTo(proto->add_field());
    }
    for (int i = 0; i < oneof_decl_count(); i++) {
      oneof_decl(i)->CopyTo(proto->add_oneof_decl());
    }
    for (int i = 0; i < nested_type_count(); i++) {
      nested_type(i)->CopyTo(proto->add_nested_type());
    }
    for (int i = 0; i < enum_type_count(); i++) {
      enum_type(i)->CopyTo(proto->add_enum_type());
    }
    for (int i = 0; i < extension_range_count(); i++) {
      DescriptorProto::ExtensionRange* range = proto->add_extension_range();
      range->set_start(extension_range(i)->start);
      range->set_end(extension_range(i)->end);
    }
    for (int i = 0; i < extension_count(); i++) {
      extension(i)->CopyTo(proto->add_extension());
    }
    for (int i = 0; i < reserved_range_count(); i++) {
      DescriptorProto::ReservedRange* range = proto->add_reserved_range();
      range->set_start(reserved_range(i)->start);
      range->set_end(reserved_range(i)->end);
    }
    for (int i = 0; i < reserved_name_count(); i++) {
      proto->add_reserved_name(reserved_name(i));
    }
  
    if (&options() != &MessageOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void Descriptor::CopyJsonNameTo(DescriptorProto* proto) const {
    if (field_count() != proto->field_size() ||
        nested_type_count() != proto->nested_type_size() ||
        extension_count() != proto->extension_size()) {
      GOOGLE_LOG(ERROR) << "Cannot copy json_name to a proto of a different size.";
      return;
    }
    for (int i = 0; i < field_count(); i++) {
      field(i)->CopyJsonNameTo(proto->mutable_field(i));
    }
    for (int i = 0; i < nested_type_count(); i++) {
      nested_type(i)->CopyJsonNameTo(proto->mutable_nested_type(i));
    }
    for (int i = 0; i < extension_count(); i++) {
      extension(i)->CopyJsonNameTo(proto->mutable_extension(i));
    }
  }
  
  void FieldDescriptor::CopyTo(FieldDescriptorProto* proto) const {
    proto->set_name(name());
    proto->set_number(number());
    if (has_json_name_) {
      proto->set_json_name(json_name());
    }
  
    // Some compilers do not allow static_cast directly between two enum types,
    // so we must cast to int first.
    proto->set_label(static_cast<FieldDescriptorProto::Label>(
                       implicit_cast<int>(label())));
    proto->set_type(static_cast<FieldDescriptorProto::Type>(
                      implicit_cast<int>(type())));
  
    if (is_extension()) {
      if (!containing_type()->is_unqualified_placeholder_) {
        proto->set_extendee(".");
      }
      proto->mutable_extendee()->append(containing_type()->full_name());
    }
  
    if (cpp_type() == CPPTYPE_MESSAGE) {
      if (message_type()->is_placeholder_) {
        // We don't actually know if the type is a message type.  It could be
        // an enum.
        proto->clear_type();
      }
  
      if (!message_type()->is_unqualified_placeholder_) {
        proto->set_type_name(".");
      }
      proto->mutable_type_name()->append(message_type()->full_name());
    } else if (cpp_type() == CPPTYPE_ENUM) {
      if (!enum_type()->is_unqualified_placeholder_) {
        proto->set_type_name(".");
      }
      proto->mutable_type_name()->append(enum_type()->full_name());
    }
  
    if (has_default_value()) {
      proto->set_default_value(DefaultValueAsString(false));
    }
  
    if (containing_oneof() != NULL && !is_extension()) {
      proto->set_oneof_index(containing_oneof()->index());
    }
  
    if (&options() != &FieldOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void FieldDescriptor::CopyJsonNameTo(FieldDescriptorProto* proto) const {
    proto->set_json_name(json_name());
  }
  
  void OneofDescriptor::CopyTo(OneofDescriptorProto* proto) const {
    proto->set_name(name());
    if (&options() != &OneofOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void EnumDescriptor::CopyTo(EnumDescriptorProto* proto) const {
    proto->set_name(name());
  
    for (int i = 0; i < value_count(); i++) {
      value(i)->CopyTo(proto->add_value());
    }
  
    if (&options() != &EnumOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void EnumValueDescriptor::CopyTo(EnumValueDescriptorProto* proto) const {
    proto->set_name(name());
    proto->set_number(number());
  
    if (&options() != &EnumValueOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void ServiceDescriptor::CopyTo(ServiceDescriptorProto* proto) const {
    proto->set_name(name());
  
    for (int i = 0; i < method_count(); i++) {
      method(i)->CopyTo(proto->add_method());
    }
  
    if (&options() != &ServiceOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  }
  
  void MethodDescriptor::CopyTo(MethodDescriptorProto* proto) const {
    proto->set_name(name());
  
    if (!input_type()->is_unqualified_placeholder_) {
      proto->set_input_type(".");
    }
    proto->mutable_input_type()->append(input_type()->full_name());
  
    if (!output_type()->is_unqualified_placeholder_) {
      proto->set_output_type(".");
    }
    proto->mutable_output_type()->append(output_type()->full_name());
  
    if (&options() != &MethodOptions::default_instance()) {
      proto->mutable_options()->CopyFrom(options());
    }
  
    if (client_streaming_) {
      proto->set_client_streaming(true);
    }
    if (server_streaming_) {
      proto->set_server_streaming(true);
    }
  }
  
  // DebugString methods ===============================================
  
  namespace {
  
  // Used by each of the option formatters.
  bool RetrieveOptions(int depth,
                       const Message &options,
                       vector<string> *option_entries) {
    option_entries->clear();
    const Reflection* reflection = options.GetReflection();
    vector<const FieldDescriptor*> fields;
    reflection->ListFields(options, &fields);
    for (int i = 0; i < fields.size(); i++) {
      int count = 1;
      bool repeated = false;
      if (fields[i]->is_repeated()) {
        count = reflection->FieldSize(options, fields[i]);
        repeated = true;
      }
      for (int j = 0; j < count; j++) {
        string fieldval;
        if (fields[i]->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
          string tmp;
          TextFormat::Printer printer;
          printer.SetInitialIndentLevel(depth + 1);
          printer.PrintFieldValueToString(options, fields[i],
                                          repeated ? j : -1, &tmp);
          fieldval.append("{\n");
          fieldval.append(tmp);
          fieldval.append(depth * 2, ' ');
          fieldval.append("}");
        } else {
          TextFormat::PrintFieldValueToString(options, fields[i],
                                              repeated ? j : -1, &fieldval);
        }
        string name;
        if (fields[i]->is_extension()) {
          name = "(." + fields[i]->full_name() + ")";
        } else {
          name = fields[i]->name();
        }
        option_entries->push_back(name + " = " + fieldval);
      }
    }
    return !option_entries->empty();
  }
  
  // Formats options that all appear together in brackets. Does not include
  // brackets.
  bool FormatBracketedOptions(int depth, const Message &options, string *output) {
    vector<string> all_options;
    if (RetrieveOptions(depth, options, &all_options)) {
      output->append(Join(all_options, ", "));
    }
    return !all_options.empty();
  }
  
  // Formats options one per line
  bool FormatLineOptions(int depth, const Message &options, string *output) {
    string prefix(depth * 2, ' ');
    vector<string> all_options;
    if (RetrieveOptions(depth, options, &all_options)) {
      for (int i = 0; i < all_options.size(); i++) {
        strings::SubstituteAndAppend(output, "$0option $1;\n",
                                     prefix, all_options[i]);
      }
    }
    return !all_options.empty();
  }
  
  class SourceLocationCommentPrinter {
   public:
    template<typename DescType>
    SourceLocationCommentPrinter(const DescType* desc,
                                 const string& prefix,
                                 const DebugStringOptions& options)
        : options_(options), prefix_(prefix) {
      // Perform the SourceLocation lookup only if we're including user comments,
      // because the lookup is fairly expensive.
      have_source_loc_ = options.include_comments &&
          desc->GetSourceLocation(&source_loc_);
    }
    SourceLocationCommentPrinter(const FileDescriptor* file,
                                 const vector<int>& path,
                                 const string& prefix,
                                 const DebugStringOptions& options)
        : options_(options), prefix_(prefix) {
      // Perform the SourceLocation lookup only if we're including user comments,
      // because the lookup is fairly expensive.
      have_source_loc_ = options.include_comments &&
          file->GetSourceLocation(path, &source_loc_);
    }
    void AddPreComment(string* output) {
      if (have_source_loc_) {
        // Detached leading comments.
        for (int i = 0 ; i < source_loc_.leading_detached_comments.size(); ++i) {
          *output += FormatComment(source_loc_.leading_detached_comments[i]);
          *output += "\n";
        }
        // Attached leading comments.
        if (!source_loc_.leading_comments.empty()) {
          *output += FormatComment(source_loc_.leading_comments);
        }
      }
    }
    void AddPostComment(string* output) {
      if (have_source_loc_ && source_loc_.trailing_comments.size() > 0) {
        *output += FormatComment(source_loc_.trailing_comments);
      }
    }
  
    // Format comment such that each line becomes a full-line C++-style comment in
    // the DebugString() output.
    string FormatComment(const string& comment_text) {
      string stripped_comment = comment_text;
      StripWhitespace(&stripped_comment);
      vector<string> lines = Split(stripped_comment, "\n");
      string output;
      for (int i = 0; i < lines.size(); ++i) {
        const string& line = lines[i];
        strings::SubstituteAndAppend(&output, "$0// $1\n", prefix_, line);
      }
      return output;
    }
  
   private:
  
    bool have_source_loc_;
    SourceLocation source_loc_;
    DebugStringOptions options_;
    string prefix_;
  };
  
  }  // anonymous namespace
  
  string FileDescriptor::DebugString() const {
    DebugStringOptions options;  // default options
    return DebugStringWithOptions(options);
  }
  
  string FileDescriptor::DebugStringWithOptions(
      const DebugStringOptions& debug_string_options) const {
    string contents;
    {
      vector<int> path;
      path.push_back(FileDescriptorProto::kSyntaxFieldNumber);
      SourceLocationCommentPrinter syntax_comment(
          this, path, "", debug_string_options);
      syntax_comment.AddPreComment(&contents);
      strings::SubstituteAndAppend(&contents, "syntax = \"$0\";\n\n",
                                   SyntaxName(syntax()));
      syntax_comment.AddPostComment(&contents);
    }
  
    SourceLocationCommentPrinter
        comment_printer(this, "", debug_string_options);
    comment_printer.AddPreComment(&contents);
  
    set<int> public_dependencies;
    set<int> weak_dependencies;
    public_dependencies.insert(public_dependencies_,
                               public_dependencies_ + public_dependency_count_);
    weak_dependencies.insert(weak_dependencies_,
                             weak_dependencies_ + weak_dependency_count_);
  
    for (int i = 0; i < dependency_count(); i++) {
      if (public_dependencies.count(i) > 0) {
        strings::SubstituteAndAppend(&contents, "import public \"$0\";\n",
                                     dependency(i)->name());
      } else if (weak_dependencies.count(i) > 0) {
        strings::SubstituteAndAppend(&contents, "import weak \"$0\";\n",
                                     dependency(i)->name());
      } else {
        strings::SubstituteAndAppend(&contents, "import \"$0\";\n",
                                     dependency(i)->name());
      }
    }
  
    if (!package().empty()) {
      vector<int> path;
      path.push_back(FileDescriptorProto::kPackageFieldNumber);
      SourceLocationCommentPrinter package_comment(
          this, path, "", debug_string_options);
      package_comment.AddPreComment(&contents);
      strings::SubstituteAndAppend(&contents, "package $0;\n\n", package());
      package_comment.AddPostComment(&contents);
    }
  
    if (FormatLineOptions(0, options(), &contents)) {
      contents.append("\n");  // add some space if we had options
    }
  
    for (int i = 0; i < enum_type_count(); i++) {
      enum_type(i)->DebugString(0, &contents, debug_string_options);
      contents.append("\n");
    }
  
    // Find all the 'group' type extensions; we will not output their nested
    // definitions (those will be done with their group field descriptor).
    set<const Descriptor*> groups;
    for (int i = 0; i < extension_count(); i++) {
      if (extension(i)->type() == FieldDescriptor::TYPE_GROUP) {
        groups.insert(extension(i)->message_type());
      }
    }
  
    for (int i = 0; i < message_type_count(); i++) {
      if (groups.count(message_type(i)) == 0) {
        message_type(i)->DebugString(0, &contents, debug_string_options,
                                     /* include_opening_clause */ true);
        contents.append("\n");
      }
    }
  
    for (int i = 0; i < service_count(); i++) {
      service(i)->DebugString(&contents, debug_string_options);
      contents.append("\n");
    }
  
    const Descriptor* containing_type = NULL;
    for (int i = 0; i < extension_count(); i++) {
      if (extension(i)->containing_type() != containing_type) {
        if (i > 0) contents.append("}\n\n");
        containing_type = extension(i)->containing_type();
        strings::SubstituteAndAppend(&contents, "extend .$0 {\n",
                                     containing_type->full_name());
      }
      extension(i)->DebugString(1, FieldDescriptor::PRINT_LABEL, &contents,
                                debug_string_options);
    }
    if (extension_count() > 0) contents.append("}\n\n");
  
    comment_printer.AddPostComment(&contents);
  
    return contents;
  }
  
  string Descriptor::DebugString() const {
    DebugStringOptions options;  // default options
    return DebugStringWithOptions(options);
  }
  
  string Descriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(0, &contents, options, /* include_opening_clause */ true);
    return contents;
  }
  
  void Descriptor::DebugString(int depth, string *contents,
                               const DebugStringOptions&
                               debug_string_options,
                               bool include_opening_clause) const {
    if (options().map_entry()) {
      // Do not generate debug string for auto-generated map-entry type.
      return;
    }
    string prefix(depth * 2, ' ');
    ++depth;
  
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
  
    if (include_opening_clause) {
      strings::SubstituteAndAppend(contents, "$0message $1", prefix, name());
    }
    contents->append(" {\n");
  
    FormatLineOptions(depth, options(), contents);
  
    // Find all the 'group' types for fields and extensions; we will not output
    // their nested definitions (those will be done with their group field
    // descriptor).
    set<const Descriptor*> groups;
    for (int i = 0; i < field_count(); i++) {
      if (field(i)->type() == FieldDescriptor::TYPE_GROUP) {
        groups.insert(field(i)->message_type());
      }
    }
    for (int i = 0; i < extension_count(); i++) {
      if (extension(i)->type() == FieldDescriptor::TYPE_GROUP) {
        groups.insert(extension(i)->message_type());
      }
    }
  
    for (int i = 0; i < nested_type_count(); i++) {
      if (groups.count(nested_type(i)) == 0) {
        nested_type(i)->DebugString(depth, contents, debug_string_options,
                                    /* include_opening_clause */ true);
      }
    }
    for (int i = 0; i < enum_type_count(); i++) {
      enum_type(i)->DebugString(depth, contents, debug_string_options);
    }
    for (int i = 0; i < field_count(); i++) {
      if (field(i)->containing_oneof() == NULL) {
        field(i)->DebugString(depth, FieldDescriptor::PRINT_LABEL, contents,
                              debug_string_options);
      } else if (field(i)->containing_oneof()->field(0) == field(i)) {
        // This is the first field in this oneof, so print the whole oneof.
        field(i)->containing_oneof()->DebugString(depth, contents,
                                                  debug_string_options);
      }
    }
  
    for (int i = 0; i < extension_range_count(); i++) {
      strings::SubstituteAndAppend(contents, "$0  extensions $1 to $2;\n",
                                   prefix,
                                   extension_range(i)->start,
                                   extension_range(i)->end - 1);
    }
  
    // Group extensions by what they extend, so they can be printed out together.
    const Descriptor* containing_type = NULL;
    for (int i = 0; i < extension_count(); i++) {
      if (extension(i)->containing_type() != containing_type) {
        if (i > 0) strings::SubstituteAndAppend(contents, "$0  }\n", prefix);
        containing_type = extension(i)->containing_type();
        strings::SubstituteAndAppend(contents, "$0  extend .$1 {\n",
                                     prefix, containing_type->full_name());
      }
      extension(i)->DebugString(
          depth + 1, FieldDescriptor::PRINT_LABEL, contents,
          debug_string_options);
    }
    if (extension_count() > 0)
      strings::SubstituteAndAppend(contents, "$0  }\n", prefix);
  
    if (reserved_range_count() > 0) {
      strings::SubstituteAndAppend(contents, "$0  reserved ", prefix);
      for (int i = 0; i < reserved_range_count(); i++) {
        const Descriptor::ReservedRange* range = reserved_range(i);
        if (range->end == range->start + 1) {
          strings::SubstituteAndAppend(contents, "$0, ", range->start);
        } else {
          strings::SubstituteAndAppend(contents, "$0 to $1, ",
                                       range->start, range->end - 1);
        }
      }
      contents->replace(contents->size() - 2, 2, ";\n");
    }
  
    if (reserved_name_count() > 0) {
      strings::SubstituteAndAppend(contents, "$0  reserved ", prefix);
      for (int i = 0; i < reserved_name_count(); i++) {
        strings::SubstituteAndAppend(contents, "\"$0\", ",
                                     CEscape(reserved_name(i)));
      }
      contents->replace(contents->size() - 2, 2, ";\n");
    }
  
    strings::SubstituteAndAppend(contents, "$0}\n", prefix);
    comment_printer.AddPostComment(contents);
  }
  
  string FieldDescriptor::DebugString() const {
    DebugStringOptions options;  // default options
    return DebugStringWithOptions(options);
  }
  
  string FieldDescriptor::DebugStringWithOptions(
      const DebugStringOptions& debug_string_options) const {
    string contents;
    int depth = 0;
    if (is_extension()) {
      strings::SubstituteAndAppend(&contents, "extend .$0 {\n",
                                   containing_type()->full_name());
      depth = 1;
    }
    DebugString(depth, PRINT_LABEL, &contents, debug_string_options);
    if (is_extension()) {
      contents.append("}\n");
    }
    return contents;
  }
  
  // The field type string used in FieldDescriptor::DebugString()
  string FieldDescriptor::FieldTypeNameDebugString() const {
    switch(type()) {
      case TYPE_MESSAGE:
        return "." + message_type()->full_name();
      case TYPE_ENUM:
        return "." + enum_type()->full_name();
      default:
        return kTypeToName[type()];
    }
  }
  
  void FieldDescriptor::DebugString(int depth,
                                    PrintLabelFlag print_label_flag,
                                    string *contents,
                                    const DebugStringOptions&
                                    debug_string_options) const {
    string prefix(depth * 2, ' ');
    string field_type;
  
    // Special case map fields.
    if (is_map()) {
      strings::SubstituteAndAppend(
          &field_type, "map<$0, $1>",
          message_type()->field(0)->FieldTypeNameDebugString(),
          message_type()->field(1)->FieldTypeNameDebugString());
    } else {
      field_type = FieldTypeNameDebugString();
    }
  
    string label;
    if (print_label_flag == PRINT_LABEL && !is_map()) {
      label = kLabelToName[this->label()];
      label.push_back(' ');
    }
  
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
  
    strings::SubstituteAndAppend(contents, "$0$1$2 $3 = $4",
                                 prefix,
                                 label,
                                 field_type,
                                 type() == TYPE_GROUP ? message_type()->name() :
                                                        name(),
                                 number());
  
    bool bracketed = false;
    if (has_default_value()) {
      bracketed = true;
      strings::SubstituteAndAppend(contents, " [default = $0",
                                   DefaultValueAsString(true));
    }
    if (has_json_name_) {
      if (!bracketed) {
        bracketed = true;
        contents->append("[");
      } else {
        contents->append(", ");
      }
      contents->append("json_name = \"");
      contents->append(CEscape(json_name()));
      contents->append("\"");
    }
  
    string formatted_options;
    if (FormatBracketedOptions(depth, options(), &formatted_options)) {
      contents->append(bracketed ? ", " : " [");
      bracketed = true;
      contents->append(formatted_options);
    }
  
    if (bracketed) {
      contents->append("]");
    }
  
    if (type() == TYPE_GROUP) {
      if (debug_string_options.elide_group_body) {
        contents->append(" { ... };\n");
      } else {
        message_type()->DebugString(depth, contents, debug_string_options,
                                    /* include_opening_clause */ false);
      }
    } else {
      contents->append(";\n");
    }
  
    comment_printer.AddPostComment(contents);
  }
  
  string OneofDescriptor::DebugString() const {
    DebugStringOptions options;  // default values
    return DebugStringWithOptions(options);
  }
  
  string OneofDescriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(0, &contents, options);
    return contents;
  }
  
  void OneofDescriptor::DebugString(int depth, string* contents,
                                    const DebugStringOptions&
                                    debug_string_options) const {
    string prefix(depth * 2, ' ');
    ++depth;
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
    strings::SubstituteAndAppend(
        contents, "$0 oneof $1 {", prefix, name());
  
    FormatLineOptions(depth, options(), contents);
  
    if (debug_string_options.elide_oneof_body) {
      contents->append(" ... }\n");
    } else {
      for (int i = 0; i < field_count(); i++) {
        field(i)->DebugString(depth, FieldDescriptor::OMIT_LABEL, contents,
                              debug_string_options);
      }
      strings::SubstituteAndAppend(contents, "$0}\n", prefix);
    }
    comment_printer.AddPostComment(contents);
  }
  
  string EnumDescriptor::DebugString() const {
    DebugStringOptions options;  // default values
    return DebugStringWithOptions(options);
  }
  
  string EnumDescriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(0, &contents, options);
    return contents;
  }
  
  void EnumDescriptor::DebugString(int depth, string *contents,
                                   const DebugStringOptions&
                                   debug_string_options) const {
    string prefix(depth * 2, ' ');
    ++depth;
  
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
  
    strings::SubstituteAndAppend(contents, "$0enum $1 {\n",
                                 prefix, name());
  
    FormatLineOptions(depth, options(), contents);
  
    for (int i = 0; i < value_count(); i++) {
      value(i)->DebugString(depth, contents, debug_string_options);
    }
    strings::SubstituteAndAppend(contents, "$0}\n", prefix);
  
    comment_printer.AddPostComment(contents);
  }
  
  string EnumValueDescriptor::DebugString() const {
    DebugStringOptions options;  // default values
    return DebugStringWithOptions(options);
  }
  
  string EnumValueDescriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(0, &contents, options);
    return contents;
  }
  
  void EnumValueDescriptor::DebugString(int depth, string *contents,
                                        const DebugStringOptions&
                                        debug_string_options) const {
    string prefix(depth * 2, ' ');
  
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
  
    strings::SubstituteAndAppend(contents, "$0$1 = $2",
                                 prefix, name(), number());
  
    string formatted_options;
    if (FormatBracketedOptions(depth, options(), &formatted_options)) {
      strings::SubstituteAndAppend(contents, " [$0]", formatted_options);
    }
    contents->append(";\n");
  
    comment_printer.AddPostComment(contents);
  }
  
  string ServiceDescriptor::DebugString() const {
    DebugStringOptions options;  // default values
    return DebugStringWithOptions(options);
  }
  
  string ServiceDescriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(&contents, options);
    return contents;
  }
  
  void ServiceDescriptor::DebugString(string *contents,
                                      const DebugStringOptions&
                                      debug_string_options) const {
    SourceLocationCommentPrinter
        comment_printer(this, /* prefix */ "", debug_string_options);
    comment_printer.AddPreComment(contents);
  
    strings::SubstituteAndAppend(contents, "service $0 {\n", name());
  
    FormatLineOptions(1, options(), contents);
  
    for (int i = 0; i < method_count(); i++) {
      method(i)->DebugString(1, contents, debug_string_options);
    }
  
    contents->append("}\n");
  
    comment_printer.AddPostComment(contents);
  }
  
  string MethodDescriptor::DebugString() const {
    DebugStringOptions options;  // default values
    return DebugStringWithOptions(options);
  }
  
  string MethodDescriptor::DebugStringWithOptions(
      const DebugStringOptions& options) const {
    string contents;
    DebugString(0, &contents, options);
    return contents;
  }
  
  void MethodDescriptor::DebugString(int depth, string *contents,
                                     const DebugStringOptions&
                                     debug_string_options) const {
    string prefix(depth * 2, ' ');
    ++depth;
  
    SourceLocationCommentPrinter
        comment_printer(this, prefix, debug_string_options);
    comment_printer.AddPreComment(contents);
  
    strings::SubstituteAndAppend(contents, "$0rpc $1($4.$2) returns ($5.$3)",
                                 prefix, name(),
                                 input_type()->full_name(),
                                 output_type()->full_name(),
                                 client_streaming() ? "stream " : "",
                                 server_streaming() ? "stream " : "");
  
    string formatted_options;
    if (FormatLineOptions(depth, options(), &formatted_options)) {
      strings::SubstituteAndAppend(contents, " {\n$0$1}\n",
                                   formatted_options, prefix);
    } else {
      contents->append(";\n");
    }
  
    comment_printer.AddPostComment(contents);
  }
  
  
  // Location methods ===============================================
  
  bool FileDescriptor::GetSourceLocation(const vector<int>& path,
                                         SourceLocation* out_location) const {
    GOOGLE_CHECK_NOTNULL(out_location);
    if (source_code_info_) {
      if (const SourceCodeInfo_Location* loc =
          tables_->GetSourceLocation(path, source_code_info_)) {
        const RepeatedField<int32>& span = loc->span();
        if (span.size() == 3 || span.size() == 4) {
          out_location->start_line   = span.Get(0);
          out_location->start_column = span.Get(1);
          out_location->end_line     = span.Get(span.size() == 3 ? 0 : 2);
          out_location->end_column   = span.Get(span.size() - 1);
  
          out_location->leading_comments = loc->leading_comments();
          out_location->trailing_comments = loc->trailing_comments();
          out_location->leading_detached_comments.assign(
              loc->leading_detached_comments().begin(),
              loc->leading_detached_comments().end());
          return true;
        }
      }
    }
    return false;
  }
  
  bool FileDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;  // empty path for root FileDescriptor
    return GetSourceLocation(path, out_location);
  }
  
  bool FieldDescriptor::is_packed() const {
    if (!is_packable()) return false;
    if (file_->syntax() == FileDescriptor::SYNTAX_PROTO2) {
      return (options_ != NULL) && options_->packed();
    } else {
      return options_ == NULL || !options_->has_packed() || options_->packed();
    }
  }
  
  bool Descriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return file()->GetSourceLocation(path, out_location);
  }
  
  bool FieldDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return file()->GetSourceLocation(path, out_location);
  }
  
  bool OneofDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return containing_type()->file()->GetSourceLocation(path, out_location);
  }
  
  bool EnumDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return file()->GetSourceLocation(path, out_location);
  }
  
  bool MethodDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return service()->file()->GetSourceLocation(path, out_location);
  }
  
  bool ServiceDescriptor::GetSourceLocation(SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return file()->GetSourceLocation(path, out_location);
  }
  
  bool EnumValueDescriptor::GetSourceLocation(
      SourceLocation* out_location) const {
    vector<int> path;
    GetLocationPath(&path);
    return type()->file()->GetSourceLocation(path, out_location);
  }
  
  void Descriptor::GetLocationPath(vector<int>* output) const {
    if (containing_type()) {
      containing_type()->GetLocationPath(output);
      output->push_back(DescriptorProto::kNestedTypeFieldNumber);
      output->push_back(index());
    } else {
      output->push_back(FileDescriptorProto::kMessageTypeFieldNumber);
      output->push_back(index());
    }
  }
  
  void FieldDescriptor::GetLocationPath(vector<int>* output) const {
    if (is_extension()) {
      if (extension_scope() == NULL) {
        output->push_back(FileDescriptorProto::kExtensionFieldNumber);
        output->push_back(index());
      } else {
        extension_scope()->GetLocationPath(output);
        output->push_back(DescriptorProto::kExtensionFieldNumber);
        output->push_back(index());
      }
    } else {
      containing_type()->GetLocationPath(output);
      output->push_back(DescriptorProto::kFieldFieldNumber);
      output->push_back(index());
    }
  }
  
  void OneofDescriptor::GetLocationPath(vector<int>* output) const {
    containing_type()->GetLocationPath(output);
    output->push_back(DescriptorProto::kOneofDeclFieldNumber);
    output->push_back(index());
  }
  
  void EnumDescriptor::GetLocationPath(vector<int>* output) const {
    if (containing_type()) {
      containing_type()->GetLocationPath(output);
      output->push_back(DescriptorProto::kEnumTypeFieldNumber);
      output->push_back(index());
    } else {
      output->push_back(FileDescriptorProto::kEnumTypeFieldNumber);
      output->push_back(index());
    }
  }
  
  void EnumValueDescriptor::GetLocationPath(vector<int>* output) const {
    type()->GetLocationPath(output);
    output->push_back(EnumDescriptorProto::kValueFieldNumber);
    output->push_back(index());
  }
  
  void ServiceDescriptor::GetLocationPath(vector<int>* output) const {
    output->push_back(FileDescriptorProto::kServiceFieldNumber);
    output->push_back(index());
  }
  
  void MethodDescriptor::GetLocationPath(vector<int>* output) const {
    service()->GetLocationPath(output);
    output->push_back(ServiceDescriptorProto::kMethodFieldNumber);
    output->push_back(index());
  }
  
  // ===================================================================
  
  namespace {
  
  // Represents an options message to interpret. Extension names in the option
  // name are resolved relative to name_scope. element_name and orig_opt are
  // used only for error reporting (since the parser records locations against
  // pointers in the original options, not the mutable copy). The Message must be
  // one of the Options messages in descriptor.proto.
  struct OptionsToInterpret {
    OptionsToInterpret(const string& ns,
                       const string& el,
                       const Message* orig_opt,
                       Message* opt)
        : name_scope(ns),
          element_name(el),
          original_options(orig_opt),
          options(opt) {
    }
    string name_scope;
    string element_name;
    const Message* original_options;
    Message* options;
  };
  
  }  // namespace
  
  class DescriptorBuilder {
   public:
    DescriptorBuilder(const DescriptorPool* pool,
                      DescriptorPool::Tables* tables,
                      DescriptorPool::ErrorCollector* error_collector);
    ~DescriptorBuilder();
  
    const FileDescriptor* BuildFile(const FileDescriptorProto& proto);
  
   private:
    friend class OptionInterpreter;
  
    // Non-recursive part of BuildFile functionality.
    const FileDescriptor* BuildFileImpl(const FileDescriptorProto& proto);
  
    const DescriptorPool* pool_;
    DescriptorPool::Tables* tables_;  // for convenience
    DescriptorPool::ErrorCollector* error_collector_;
  
    // As we build descriptors we store copies of the options messages in
    // them. We put pointers to those copies in this vector, as we build, so we
    // can later (after cross-linking) interpret those options.
    vector<OptionsToInterpret> options_to_interpret_;
  
    bool had_errors_;
    string filename_;
    FileDescriptor* file_;
    FileDescriptorTables* file_tables_;
    set<const FileDescriptor*> dependencies_;
  
    // unused_dependency_ is used to record the unused imported files.
    // Note: public import is not considered.
    set<const FileDescriptor*> unused_dependency_;
  
    // If LookupSymbol() finds a symbol that is in a file which is not a declared
    // dependency of this file, it will fail, but will set
    // possible_undeclared_dependency_ to point at that file.  This is only used
    // by AddNotDefinedError() to report a more useful error message.
    // possible_undeclared_dependency_name_ is the name of the symbol that was
    // actually found in possible_undeclared_dependency_, which may be a parent
    // of the symbol actually looked for.
    const FileDescriptor* possible_undeclared_dependency_;
    string possible_undeclared_dependency_name_;
  
    // If LookupSymbol() could resolve a symbol which is not defined,
    // record the resolved name.  This is only used by AddNotDefinedError()
    // to report a more useful error message.
    string undefine_resolved_name_;
  
    void AddError(const string& element_name,
                  const Message& descriptor,
                  DescriptorPool::ErrorCollector::ErrorLocation location,
                  const string& error);
    void AddError(const string& element_name,
                  const Message& descriptor,
                  DescriptorPool::ErrorCollector::ErrorLocation location,
                  const char* error);
    void AddRecursiveImportError(const FileDescriptorProto& proto, int from_here);
    void AddTwiceListedError(const FileDescriptorProto& proto, int index);
    void AddImportError(const FileDescriptorProto& proto, int index);
  
    // Adds an error indicating that undefined_symbol was not defined.  Must
    // only be called after LookupSymbol() fails.
    void AddNotDefinedError(
      const string& element_name,
      const Message& descriptor,
      DescriptorPool::ErrorCollector::ErrorLocation location,
      const string& undefined_symbol);
  
    void AddWarning(const string& element_name, const Message& descriptor,
                    DescriptorPool::ErrorCollector::ErrorLocation location,
                    const string& error);
  
    // Silly helper which determines if the given file is in the given package.
    // I.e., either file->package() == package_name or file->package() is a
    // nested package within package_name.
    bool IsInPackage(const FileDescriptor* file, const string& package_name);
  
    // Helper function which finds all public dependencies of the given file, and
    // stores the them in the dependencies_ set in the builder.
    void RecordPublicDependencies(const FileDescriptor* file);
  
    // Like tables_->FindSymbol(), but additionally:
    // - Search the pool's underlay if not found in tables_.
    // - Insure that the resulting Symbol is from one of the file's declared
    //   dependencies.
    Symbol FindSymbol(const string& name);
  
    // Like FindSymbol() but does not require that the symbol is in one of the
    // file's declared dependencies.
    Symbol FindSymbolNotEnforcingDeps(const string& name);
  
    // This implements the body of FindSymbolNotEnforcingDeps().
    Symbol FindSymbolNotEnforcingDepsHelper(const DescriptorPool* pool,
                                            const string& name);
  
    // Like FindSymbol(), but looks up the name relative to some other symbol
    // name.  This first searches siblings of relative_to, then siblings of its
    // parents, etc.  For example, LookupSymbol("foo.bar", "baz.qux.corge") makes
    // the following calls, returning the first non-null result:
    // FindSymbol("baz.qux.foo.bar"), FindSymbol("baz.foo.bar"),
    // FindSymbol("foo.bar").  If AllowUnknownDependencies() has been called
    // on the DescriptorPool, this will generate a placeholder type if
    // the name is not found (unless the name itself is malformed).  The
    // placeholder_type parameter indicates what kind of placeholder should be
    // constructed in this case.  The resolve_mode parameter determines whether
    // any symbol is returned, or only symbols that are types.  Note, however,
    // that LookupSymbol may still return a non-type symbol in LOOKUP_TYPES mode,
    // if it believes that's all it could refer to.  The caller should always
    // check that it receives the type of symbol it was expecting.
    enum PlaceholderType {
      PLACEHOLDER_MESSAGE,
      PLACEHOLDER_ENUM,
      PLACEHOLDER_EXTENDABLE_MESSAGE
    };
    enum ResolveMode {
      LOOKUP_ALL, LOOKUP_TYPES
    };
    Symbol LookupSymbol(const string& name, const string& relative_to,
                        PlaceholderType placeholder_type = PLACEHOLDER_MESSAGE,
                        ResolveMode resolve_mode = LOOKUP_ALL);
  
    // Like LookupSymbol() but will not return a placeholder even if
    // AllowUnknownDependencies() has been used.
    Symbol LookupSymbolNoPlaceholder(const string& name,
                                     const string& relative_to,
                                     ResolveMode resolve_mode = LOOKUP_ALL);
  
    // Creates a placeholder type suitable for return from LookupSymbol().  May
    // return kNullSymbol if the name is not a valid type name.
    Symbol NewPlaceholder(const string& name, PlaceholderType placeholder_type);
  
    // Creates a placeholder file.  Never returns NULL.  This is used when an
    // import is not found and AllowUnknownDependencies() is enabled.
    FileDescriptor* NewPlaceholderFile(const string& name);
  
    // Calls tables_->AddSymbol() and records an error if it fails.  Returns
    // true if successful or false if failed, though most callers can ignore
    // the return value since an error has already been recorded.
    bool AddSymbol(const string& full_name,
                   const void* parent, const string& name,
                   const Message& proto, Symbol symbol);
  
    // Like AddSymbol(), but succeeds if the symbol is already defined as long
    // as the existing definition is also a package (because it's OK to define
    // the same package in two different files).  Also adds all parents of the
    // packgae to the symbol table (e.g. AddPackage("foo.bar", ...) will add
    // "foo.bar" and "foo" to the table).
    void AddPackage(const string& name, const Message& proto,
                    const FileDescriptor* file);
  
    // Checks that the symbol name contains only alphanumeric characters and
    // underscores.  Records an error otherwise.
    void ValidateSymbolName(const string& name, const string& full_name,
                            const Message& proto);
  
    // Like ValidateSymbolName(), but the name is allowed to contain periods and
    // an error is indicated by returning false (not recording the error).
    bool ValidateQualifiedName(const string& name);
  
    // Used by BUILD_ARRAY macro (below) to avoid having to have the type
    // specified as a macro parameter.
    template <typename Type>
    inline void AllocateArray(int size, Type** output) {
      *output = tables_->AllocateArray<Type>(size);
    }
  
    // Allocates a copy of orig_options in tables_ and stores it in the
    // descriptor. Remembers its uninterpreted options, to be interpreted
    // later. DescriptorT must be one of the Descriptor messages from
    // descriptor.proto.
    template<class DescriptorT> void AllocateOptions(
        const typename DescriptorT::OptionsType& orig_options,
        DescriptorT* descriptor);
    // Specialization for FileOptions.
    void AllocateOptions(const FileOptions& orig_options,
                         FileDescriptor* descriptor);
  
    // Implementation for AllocateOptions(). Don't call this directly.
    template<class DescriptorT> void AllocateOptionsImpl(
        const string& name_scope,
        const string& element_name,
        const typename DescriptorT::OptionsType& orig_options,
        DescriptorT* descriptor);
  
    // These methods all have the same signature for the sake of the BUILD_ARRAY
    // macro, below.
    void BuildMessage(const DescriptorProto& proto,
                      const Descriptor* parent,
                      Descriptor* result);
    void BuildFieldOrExtension(const FieldDescriptorProto& proto,
                               const Descriptor* parent,
                               FieldDescriptor* result,
                               bool is_extension);
    void BuildField(const FieldDescriptorProto& proto,
                    const Descriptor* parent,
                    FieldDescriptor* result) {
      BuildFieldOrExtension(proto, parent, result, false);
    }
    void BuildExtension(const FieldDescriptorProto& proto,
                        const Descriptor* parent,
                        FieldDescriptor* result) {
      BuildFieldOrExtension(proto, parent, result, true);
    }
    void BuildExtensionRange(const DescriptorProto::ExtensionRange& proto,
                             const Descriptor* parent,
                             Descriptor::ExtensionRange* result);
    void BuildReservedRange(const DescriptorProto::ReservedRange& proto,
                             const Descriptor* parent,
                             Descriptor::ReservedRange* result);
    void BuildOneof(const OneofDescriptorProto& proto,
                    Descriptor* parent,
                    OneofDescriptor* result);
    void CheckEnumValueUniqueness(const EnumDescriptorProto& proto,
                                  const EnumDescriptor* result);
    void BuildEnum(const EnumDescriptorProto& proto,
                   const Descriptor* parent,
                   EnumDescriptor* result);
    void BuildEnumValue(const EnumValueDescriptorProto& proto,
                        const EnumDescriptor* parent,
                        EnumValueDescriptor* result);
    void BuildService(const ServiceDescriptorProto& proto,
                      const void* dummy,
                      ServiceDescriptor* result);
    void BuildMethod(const MethodDescriptorProto& proto,
                     const ServiceDescriptor* parent,
                     MethodDescriptor* result);
  
    void LogUnusedDependency(const FileDescriptorProto& proto,
                             const FileDescriptor* result);
  
    // Must be run only after building.
    //
    // NOTE: Options will not be available during cross-linking, as they
    // have not yet been interpreted. Defer any handling of options to the
    // Validate*Options methods.
    void CrossLinkFile(FileDescriptor* file, const FileDescriptorProto& proto);
    void CrossLinkMessage(Descriptor* message, const DescriptorProto& proto);
    void CrossLinkField(FieldDescriptor* field,
                        const FieldDescriptorProto& proto);
    void CrossLinkEnum(EnumDescriptor* enum_type,
                       const EnumDescriptorProto& proto);
    void CrossLinkEnumValue(EnumValueDescriptor* enum_value,
                            const EnumValueDescriptorProto& proto);
    void CrossLinkService(ServiceDescriptor* service,
                          const ServiceDescriptorProto& proto);
    void CrossLinkMethod(MethodDescriptor* method,
                         const MethodDescriptorProto& proto);
  
    // Must be run only after cross-linking.
    void InterpretOptions();
  
    // A helper class for interpreting options.
    class OptionInterpreter {
     public:
      // Creates an interpreter that operates in the context of the pool of the
      // specified builder, which must not be NULL. We don't take ownership of the
      // builder.
      explicit OptionInterpreter(DescriptorBuilder* builder);
  
      ~OptionInterpreter();
  
      // Interprets the uninterpreted options in the specified Options message.
      // On error, calls AddError() on the underlying builder and returns false.
      // Otherwise returns true.
      bool InterpretOptions(OptionsToInterpret* options_to_interpret);
  
      class AggregateOptionFinder;
  
     private:
      // Interprets uninterpreted_option_ on the specified message, which
      // must be the mutable copy of the original options message to which
      // uninterpreted_option_ belongs.
      bool InterpretSingleOption(Message* options);
  
      // Adds the uninterpreted_option to the given options message verbatim.
      // Used when AllowUnknownDependencies() is in effect and we can't find
      // the option's definition.
      void AddWithoutInterpreting(const UninterpretedOption& uninterpreted_option,
                                  Message* options);
  
      // A recursive helper function that drills into the intermediate fields
      // in unknown_fields to check if field innermost_field is set on the
      // innermost message. Returns false and sets an error if so.
      bool ExamineIfOptionIsSet(
          vector<const FieldDescriptor*>::const_iterator intermediate_fields_iter,
          vector<const FieldDescriptor*>::const_iterator intermediate_fields_end,
          const FieldDescriptor* innermost_field, const string& debug_msg_name,
          const UnknownFieldSet& unknown_fields);
  
      // Validates the value for the option field of the currently interpreted
      // option and then sets it on the unknown_field.
      bool SetOptionValue(const FieldDescriptor* option_field,
                          UnknownFieldSet* unknown_fields);
  
      // Parses an aggregate value for a CPPTYPE_MESSAGE option and
      // saves it into *unknown_fields.
      bool SetAggregateOption(const FieldDescriptor* option_field,
                              UnknownFieldSet* unknown_fields);
  
      // Convenience functions to set an int field the right way, depending on
      // its wire type (a single int CppType can represent multiple wire types).
      void SetInt32(int number, int32 value, FieldDescriptor::Type type,
                    UnknownFieldSet* unknown_fields);
      void SetInt64(int number, int64 value, FieldDescriptor::Type type,
                    UnknownFieldSet* unknown_fields);
      void SetUInt32(int number, uint32 value, FieldDescriptor::Type type,
                     UnknownFieldSet* unknown_fields);
      void SetUInt64(int number, uint64 value, FieldDescriptor::Type type,
                     UnknownFieldSet* unknown_fields);
  
      // A helper function that adds an error at the specified location of the
      // option we're currently interpreting, and returns false.
      bool AddOptionError(DescriptorPool::ErrorCollector::ErrorLocation location,
                          const string& msg) {
        builder_->AddError(options_to_interpret_->element_name,
                           *uninterpreted_option_, location, msg);
        return false;
      }
  
      // A helper function that adds an error at the location of the option name
      // and returns false.
      bool AddNameError(const string& msg) {
        return AddOptionError(DescriptorPool::ErrorCollector::OPTION_NAME, msg);
      }
  
      // A helper function that adds an error at the location of the option name
      // and returns false.
      bool AddValueError(const string& msg) {
        return AddOptionError(DescriptorPool::ErrorCollector::OPTION_VALUE, msg);
      }
  
      // We interpret against this builder's pool. Is never NULL. We don't own
      // this pointer.
      DescriptorBuilder* builder_;
  
      // The options we're currently interpreting, or NULL if we're not in a call
      // to InterpretOptions.
      const OptionsToInterpret* options_to_interpret_;
  
      // The option we're currently interpreting within options_to_interpret_, or
      // NULL if we're not in a call to InterpretOptions(). This points to a
      // submessage of the original option, not the mutable copy. Therefore we
      // can use it to find locations recorded by the parser.
      const UninterpretedOption* uninterpreted_option_;
  
      // Factory used to create the dynamic messages we need to parse
      // any aggregate option values we encounter.
      DynamicMessageFactory dynamic_factory_;
  
      GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(OptionInterpreter);
    };
  
    // Work-around for broken compilers:  According to the C++ standard,
    // OptionInterpreter should have access to the private members of any class
    // which has declared DescriptorBuilder as a friend.  Unfortunately some old
    // versions of GCC and other compilers do not implement this correctly.  So,
    // we have to have these intermediate methods to provide access.  We also
    // redundantly declare OptionInterpreter a friend just to make things extra
    // clear for these bad compilers.
    friend class OptionInterpreter;
    friend class OptionInterpreter::AggregateOptionFinder;
  
    static inline bool get_allow_unknown(const DescriptorPool* pool) {
      return pool->allow_unknown_;
    }
    static inline bool get_enforce_weak(const DescriptorPool* pool) {
      return pool->enforce_weak_;
    }
    static inline bool get_is_placeholder(const Descriptor* descriptor) {
      return descriptor->is_placeholder_;
    }
    static inline void assert_mutex_held(const DescriptorPool* pool) {
      if (pool->mutex_ != NULL) {
        pool->mutex_->AssertHeld();
      }
    }
  
    // Must be run only after options have been interpreted.
    //
    // NOTE: Validation code must only reference the options in the mutable
    // descriptors, which are the ones that have been interpreted. The const
    // proto references are passed in only so they can be provided to calls to
    // AddError(). Do not look at their options, which have not been interpreted.
    void ValidateFileOptions(FileDescriptor* file,
                             const FileDescriptorProto& proto);
    void ValidateMessageOptions(Descriptor* message,
                                const DescriptorProto& proto);
    void ValidateFieldOptions(FieldDescriptor* field,
                              const FieldDescriptorProto& proto);
    void ValidateEnumOptions(EnumDescriptor* enm,
                             const EnumDescriptorProto& proto);
    void ValidateEnumValueOptions(EnumValueDescriptor* enum_value,
                                  const EnumValueDescriptorProto& proto);
    void ValidateServiceOptions(ServiceDescriptor* service,
                                const ServiceDescriptorProto& proto);
    void ValidateMethodOptions(MethodDescriptor* method,
                               const MethodDescriptorProto& proto);
    void ValidateProto3(FileDescriptor* file,
                        const FileDescriptorProto& proto);
    void ValidateProto3Message(Descriptor* message,
                               const DescriptorProto& proto);
    void ValidateProto3Field(FieldDescriptor* field,
                             const FieldDescriptorProto& proto);
    void ValidateProto3Enum(EnumDescriptor* enm,
                            const EnumDescriptorProto& proto);
  
    // Returns true if the map entry message is compatible with the
    // auto-generated entry message from map fields syntax.
    bool ValidateMapEntry(FieldDescriptor* field,
                          const FieldDescriptorProto& proto);
  
    // Recursively detects naming conflicts with map entry types for a
    // better error message.
    void DetectMapConflicts(const Descriptor* message,
                            const DescriptorProto& proto);
  
  };
  
  const FileDescriptor* DescriptorPool::BuildFile(
      const FileDescriptorProto& proto) {
    GOOGLE_CHECK(fallback_database_ == NULL)
      << "Cannot call BuildFile on a DescriptorPool that uses a "
         "DescriptorDatabase.  You must instead find a way to get your file "
         "into the underlying database.";
    GOOGLE_CHECK(mutex_ == NULL);   // Implied by the above GOOGLE_CHECK.
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
    return DescriptorBuilder(this, tables_.get(), NULL).BuildFile(proto);
  }
  
  const FileDescriptor* DescriptorPool::BuildFileCollectingErrors(
      const FileDescriptorProto& proto,
      ErrorCollector* error_collector) {
    GOOGLE_CHECK(fallback_database_ == NULL)
      << "Cannot call BuildFile on a DescriptorPool that uses a "
         "DescriptorDatabase.  You must instead find a way to get your file "
         "into the underlying database.";
    GOOGLE_CHECK(mutex_ == NULL);   // Implied by the above GOOGLE_CHECK.
    tables_->known_bad_symbols_.clear();
    tables_->known_bad_files_.clear();
    return DescriptorBuilder(this, tables_.get(),
                             error_collector).BuildFile(proto);
  }
  
  const FileDescriptor* DescriptorPool::BuildFileFromDatabase(
      const FileDescriptorProto& proto) const {
    mutex_->AssertHeld();
    if (tables_->known_bad_files_.count(proto.name()) > 0) {
      return NULL;
    }
    const FileDescriptor* result =
        DescriptorBuilder(this, tables_.get(),
                          default_error_collector_).BuildFile(proto);
    if (result == NULL) {
      tables_->known_bad_files_.insert(proto.name());
    }
    return result;
  }
  
  DescriptorBuilder::DescriptorBuilder(
      const DescriptorPool* pool,
      DescriptorPool::Tables* tables,
      DescriptorPool::ErrorCollector* error_collector)
    : pool_(pool),
      tables_(tables),
      error_collector_(error_collector),
      had_errors_(false),
      possible_undeclared_dependency_(NULL),
      undefine_resolved_name_("") {}
  
  DescriptorBuilder::~DescriptorBuilder() {}
  
  void DescriptorBuilder::AddError(
      const string& element_name,
      const Message& descriptor,
      DescriptorPool::ErrorCollector::ErrorLocation location,
      const string& error) {
    if (error_collector_ == NULL) {
      if (!had_errors_) {
        GOOGLE_LOG(ERROR) << "Invalid proto descriptor for file \"" << filename_
                   << "\":";
      }
      GOOGLE_LOG(ERROR) << "  " << element_name << ": " << error;
    } else {
      error_collector_->AddError(filename_, element_name,
                                 &descriptor, location, error);
    }
    had_errors_ = true;
  }
  
  void DescriptorBuilder::AddError(
      const string& element_name,
      const Message& descriptor,
      DescriptorPool::ErrorCollector::ErrorLocation location,
      const char* error) {
    AddError(element_name, descriptor, location, string(error));
  }
  
  void DescriptorBuilder::AddNotDefinedError(
      const string& element_name,
      const Message& descriptor,
      DescriptorPool::ErrorCollector::ErrorLocation location,
      const string& undefined_symbol) {
    if (possible_undeclared_dependency_ == NULL &&
        undefine_resolved_name_.empty()) {
      AddError(element_name, descriptor, location,
               "\"" + undefined_symbol + "\" is not defined.");
    } else {
      if (possible_undeclared_dependency_ != NULL) {
        AddError(element_name, descriptor, location,
                 "\"" + possible_undeclared_dependency_name_ +
                 "\" seems to be defined in \"" +
                 possible_undeclared_dependency_->name() + "\", which is not "
                 "imported by \"" + filename_ + "\".  To use it here, please "
                 "add the necessary import.");
      }
      if (!undefine_resolved_name_.empty()) {
        AddError(element_name, descriptor, location,
                 "\"" + undefined_symbol + "\" is resolved to \"" +
                 undefine_resolved_name_ + "\", which is not defined. "
                 "The innermost scope is searched first in name resolution. "
                 "Consider using a leading '.'(i.e., \"."
                 + undefined_symbol +
                 "\") to start from the outermost scope.");
      }
    }
  }
  
  void DescriptorBuilder::AddWarning(
      const string& element_name, const Message& descriptor,
      DescriptorPool::ErrorCollector::ErrorLocation location,
      const string& error) {
    if (error_collector_ == NULL) {
      GOOGLE_LOG(WARNING) << filename_ << " " << element_name << ": " << error;
    } else {
      error_collector_->AddWarning(filename_, element_name, &descriptor, location,
                                   error);
    }
  }
  
  bool DescriptorBuilder::IsInPackage(const FileDescriptor* file,
                                      const string& package_name) {
    return HasPrefixString(file->package(), package_name) &&
             (file->package().size() == package_name.size() ||
              file->package()[package_name.size()] == '.');
  }
  
  void DescriptorBuilder::RecordPublicDependencies(const FileDescriptor* file) {
    if (file == NULL || !dependencies_.insert(file).second) return;
    for (int i = 0; file != NULL && i < file->public_dependency_count(); i++) {
      RecordPublicDependencies(file->public_dependency(i));
    }
  }
  
  Symbol DescriptorBuilder::FindSymbolNotEnforcingDepsHelper(
      const DescriptorPool* pool, const string& name) {
    // If we are looking at an underlay, we must lock its mutex_, since we are
    // accessing the underlay's tables_ directly.
    MutexLockMaybe lock((pool == pool_) ? NULL : pool->mutex_);
  
    Symbol result = pool->tables_->FindSymbol(name);
    if (result.IsNull() && pool->underlay_ != NULL) {
      // Symbol not found; check the underlay.
      result = FindSymbolNotEnforcingDepsHelper(pool->underlay_, name);
    }
  
    if (result.IsNull()) {
      // In theory, we shouldn't need to check fallback_database_ because the
      // symbol should be in one of its file's direct dependencies, and we have
      // already loaded those by the time we get here.  But we check anyway so
      // that we can generate better error message when dependencies are missing
      // (i.e., "missing dependency" rather than "type is not defined").
      if (pool->TryFindSymbolInFallbackDatabase(name)) {
        result = pool->tables_->FindSymbol(name);
      }
    }
  
    return result;
  }
  
  Symbol DescriptorBuilder::FindSymbolNotEnforcingDeps(const string& name) {
    return FindSymbolNotEnforcingDepsHelper(pool_, name);
  }
  
  Symbol DescriptorBuilder::FindSymbol(const string& name) {
    Symbol result = FindSymbolNotEnforcingDeps(name);
  
    if (result.IsNull()) return result;
  
    if (!pool_->enforce_dependencies_) {
      // Hack for CompilerUpgrader.
      return result;
    }
  
    // Only find symbols which were defined in this file or one of its
    // dependencies.
    const FileDescriptor* file = result.GetFile();
    if (file == file_ || dependencies_.count(file) > 0) {
      unused_dependency_.erase(file);
      return result;
    }
  
    if (result.type == Symbol::PACKAGE) {
      // Arg, this is overcomplicated.  The symbol is a package name.  It could
      // be that the package was defined in multiple files.  result.GetFile()
      // returns the first file we saw that used this package.  We've determined
      // that that file is not a direct dependency of the file we are currently
      // building, but it could be that some other file which *is* a direct
      // dependency also defines the same package.  We can't really rule out this
      // symbol unless none of the dependencies define it.
      if (IsInPackage(file_, name)) return result;
      for (set<const FileDescriptor*>::const_iterator it = dependencies_.begin();
           it != dependencies_.end(); ++it) {
        // Note:  A dependency may be NULL if it was not found or had errors.
        if (*it != NULL && IsInPackage(*it, name)) return result;
      }
    }
  
    possible_undeclared_dependency_ = file;
    possible_undeclared_dependency_name_ = name;
    return kNullSymbol;
  }
  
  Symbol DescriptorBuilder::LookupSymbolNoPlaceholder(
      const string& name, const string& relative_to, ResolveMode resolve_mode) {
    possible_undeclared_dependency_ = NULL;
    undefine_resolved_name_.clear();
  
    if (name.size() > 0 && name[0] == '.') {
      // Fully-qualified name.
      return FindSymbol(name.substr(1));
    }
  
    // If name is something like "Foo.Bar.baz", and symbols named "Foo" are
    // defined in multiple parent scopes, we only want to find "Bar.baz" in the
    // innermost one.  E.g., the following should produce an error:
    //   message Bar { message Baz {} }
    //   message Foo {
    //     message Bar {
    //     }
    //     optional Bar.Baz baz = 1;
    //   }
    // So, we look for just "Foo" first, then look for "Bar.baz" within it if
    // found.
    string::size_type name_dot_pos = name.find_first_of('.');
    string first_part_of_name;
    if (name_dot_pos == string::npos) {
      first_part_of_name = name;
    } else {
      first_part_of_name = name.substr(0, name_dot_pos);
    }
  
    string scope_to_try(relative_to);
  
    while (true) {
      // Chop off the last component of the scope.
      string::size_type dot_pos = scope_to_try.find_last_of('.');
      if (dot_pos == string::npos) {
        return FindSymbol(name);
      } else {
        scope_to_try.erase(dot_pos);
      }
  
      // Append ".first_part_of_name" and try to find.
      string::size_type old_size = scope_to_try.size();
      scope_to_try.append(1, '.');
      scope_to_try.append(first_part_of_name);
      Symbol result = FindSymbol(scope_to_try);
      if (!result.IsNull()) {
        if (first_part_of_name.size() < name.size()) {
          // name is a compound symbol, of which we only found the first part.
          // Now try to look up the rest of it.
          if (result.IsAggregate()) {
            scope_to_try.append(name, first_part_of_name.size(),
                                name.size() - first_part_of_name.size());
            result = FindSymbol(scope_to_try);
            if (result.IsNull()) {
              undefine_resolved_name_ = scope_to_try;
            }
            return result;
          } else {
            // We found a symbol but it's not an aggregate.  Continue the loop.
          }
        } else {
          if (resolve_mode == LOOKUP_TYPES && !result.IsType()) {
            // We found a symbol but it's not a type.  Continue the loop.
          } else {
            return result;
          }
        }
      }
  
      // Not found.  Remove the name so we can try again.
      scope_to_try.erase(old_size);
    }
  }
  
  Symbol DescriptorBuilder::LookupSymbol(
      const string& name, const string& relative_to,
      PlaceholderType placeholder_type, ResolveMode resolve_mode) {
    Symbol result = LookupSymbolNoPlaceholder(
        name, relative_to, resolve_mode);
    if (result.IsNull() && pool_->allow_unknown_) {
      // Not found, but AllowUnknownDependencies() is enabled.  Return a
      // placeholder instead.
      result = NewPlaceholder(name, placeholder_type);
    }
    return result;
  }
  
  Symbol DescriptorBuilder::NewPlaceholder(const string& name,
                                           PlaceholderType placeholder_type) {
    // Compute names.
    const string* placeholder_full_name;
    const string* placeholder_name;
    const string* placeholder_package;
  
    if (!ValidateQualifiedName(name)) return kNullSymbol;
    if (name[0] == '.') {
      // Fully-qualified.
      placeholder_full_name = tables_->AllocateString(name.substr(1));
    } else {
      placeholder_full_name = tables_->AllocateString(name);
    }
  
    string::size_type dotpos = placeholder_full_name->find_last_of('.');
    if (dotpos != string::npos) {
      placeholder_package = tables_->AllocateString(
        placeholder_full_name->substr(0, dotpos));
      placeholder_name = tables_->AllocateString(
        placeholder_full_name->substr(dotpos + 1));
    } else {
      placeholder_package = &internal::GetEmptyString();
      placeholder_name = placeholder_full_name;
    }
  
    // Create the placeholders.
    FileDescriptor* placeholder_file = NewPlaceholderFile(
        *placeholder_full_name + ".placeholder.proto");
    placeholder_file->package_ = placeholder_package;
  
    if (placeholder_type == PLACEHOLDER_ENUM) {
      placeholder_file->enum_type_count_ = 1;
      placeholder_file->enum_types_ =
        tables_->AllocateArray<EnumDescriptor>(1);
  
      EnumDescriptor* placeholder_enum = &placeholder_file->enum_types_[0];
      memset(placeholder_enum, 0, sizeof(*placeholder_enum));
  
      placeholder_enum->full_name_ = placeholder_full_name;
      placeholder_enum->name_ = placeholder_name;
      placeholder_enum->file_ = placeholder_file;
      placeholder_enum->options_ = &EnumOptions::default_instance();
      placeholder_enum->is_placeholder_ = true;
      placeholder_enum->is_unqualified_placeholder_ = (name[0] != '.');
  
      // Enums must have at least one value.
      placeholder_enum->value_count_ = 1;
      placeholder_enum->values_ = tables_->AllocateArray<EnumValueDescriptor>(1);
  
      EnumValueDescriptor* placeholder_value = &placeholder_enum->values_[0];
      memset(placeholder_value, 0, sizeof(*placeholder_value));
  
      placeholder_value->name_ = tables_->AllocateString("PLACEHOLDER_VALUE");
      // Note that enum value names are siblings of their type, not children.
      placeholder_value->full_name_ =
        placeholder_package->empty() ? placeholder_value->name_ :
          tables_->AllocateString(*placeholder_package + ".PLACEHOLDER_VALUE");
  
      placeholder_value->number_ = 0;
      placeholder_value->type_ = placeholder_enum;
      placeholder_value->options_ = &EnumValueOptions::default_instance();
  
      return Symbol(placeholder_enum);
    } else {
      placeholder_file->message_type_count_ = 1;
      placeholder_file->message_types_ =
        tables_->AllocateArray<Descriptor>(1);
  
      Descriptor* placeholder_message = &placeholder_file->message_types_[0];
      memset(placeholder_message, 0, sizeof(*placeholder_message));
  
      placeholder_message->full_name_ = placeholder_full_name;
      placeholder_message->name_ = placeholder_name;
      placeholder_message->file_ = placeholder_file;
      placeholder_message->options_ = &MessageOptions::default_instance();
      placeholder_message->is_placeholder_ = true;
      placeholder_message->is_unqualified_placeholder_ = (name[0] != '.');
  
      if (placeholder_type == PLACEHOLDER_EXTENDABLE_MESSAGE) {
        placeholder_message->extension_range_count_ = 1;
        placeholder_message->extension_ranges_ =
          tables_->AllocateArray<Descriptor::ExtensionRange>(1);
        placeholder_message->extension_ranges_->start = 1;
        // kMaxNumber + 1 because ExtensionRange::end is exclusive.
        placeholder_message->extension_ranges_->end =
          FieldDescriptor::kMaxNumber + 1;
      }
  
      return Symbol(placeholder_message);
    }
  }
  
  FileDescriptor* DescriptorBuilder::NewPlaceholderFile(
      const string& name) {
    FileDescriptor* placeholder = tables_->Allocate<FileDescriptor>();
    memset(placeholder, 0, sizeof(*placeholder));
  
    placeholder->name_ = tables_->AllocateString(name);
    placeholder->package_ = &internal::GetEmptyString();
    placeholder->pool_ = pool_;
    placeholder->options_ = &FileOptions::default_instance();
    placeholder->tables_ = &FileDescriptorTables::GetEmptyInstance();
    placeholder->source_code_info_ = &SourceCodeInfo::default_instance();
    placeholder->is_placeholder_ = true;
    placeholder->syntax_ = FileDescriptor::SYNTAX_PROTO2;
    // All other fields are zero or NULL.
  
    return placeholder;
  }
  
  bool DescriptorBuilder::AddSymbol(
      const string& full_name, const void* parent, const string& name,
      const Message& proto, Symbol symbol) {
    // If the caller passed NULL for the parent, the symbol is at file scope.
    // Use its file as the parent instead.
    if (parent == NULL) parent = file_;
  
    if (tables_->AddSymbol(full_name, symbol)) {
      if (!file_tables_->AddAliasUnderParent(parent, name, symbol)) {
        GOOGLE_LOG(DFATAL) << "\"" << full_name << "\" not previously defined in "
                       "symbols_by_name_, but was defined in symbols_by_parent_; "
                       "this shouldn't be possible.";
        return false;
      }
      return true;
    } else {
      const FileDescriptor* other_file = tables_->FindSymbol(full_name).GetFile();
      if (other_file == file_) {
        string::size_type dot_pos = full_name.find_last_of('.');
        if (dot_pos == string::npos) {
          AddError(full_name, proto, DescriptorPool::ErrorCollector::NAME,
                   "\"" + full_name + "\" is already defined.");
        } else {
          AddError(full_name, proto, DescriptorPool::ErrorCollector::NAME,
                   "\"" + full_name.substr(dot_pos + 1) +
                   "\" is already defined in \"" +
                   full_name.substr(0, dot_pos) + "\".");
        }
      } else {
        // Symbol seems to have been defined in a different file.
        AddError(full_name, proto, DescriptorPool::ErrorCollector::NAME,
                 "\"" + full_name + "\" is already defined in file \"" +
                 other_file->name() + "\".");
      }
      return false;
    }
  }
  
  void DescriptorBuilder::AddPackage(
      const string& name, const Message& proto, const FileDescriptor* file) {
    if (tables_->AddSymbol(name, Symbol(file))) {
      // Success.  Also add parent package, if any.
      string::size_type dot_pos = name.find_last_of('.');
      if (dot_pos == string::npos) {
        // No parents.
        ValidateSymbolName(name, name, proto);
      } else {
        // Has parent.
        string* parent_name = tables_->AllocateString(name.substr(0, dot_pos));
        AddPackage(*parent_name, proto, file);
        ValidateSymbolName(name.substr(dot_pos + 1), name, proto);
      }
    } else {
      Symbol existing_symbol = tables_->FindSymbol(name);
      // It's OK to redefine a package.
      if (existing_symbol.type != Symbol::PACKAGE) {
        // Symbol seems to have been defined in a different file.
        AddError(name, proto, DescriptorPool::ErrorCollector::NAME,
                 "\"" + name + "\" is already defined (as something other than "
                 "a package) in file \"" + existing_symbol.GetFile()->name() +
                 "\".");
      }
    }
  }
  
  void DescriptorBuilder::ValidateSymbolName(
      const string& name, const string& full_name, const Message& proto) {
    if (name.empty()) {
      AddError(full_name, proto, DescriptorPool::ErrorCollector::NAME,
               "Missing name.");
    } else {
      for (int i = 0; i < name.size(); i++) {
        // I don't trust isalnum() due to locales.  :(
        if ((name[i] < 'a' || 'z' < name[i]) &&
            (name[i] < 'A' || 'Z' < name[i]) &&
            (name[i] < '0' || '9' < name[i]) &&
            (name[i] != '_')) {
          AddError(full_name, proto, DescriptorPool::ErrorCollector::NAME,
                   "\"" + name + "\" is not a valid identifier.");
        }
      }
    }
  }
  
  bool DescriptorBuilder::ValidateQualifiedName(const string& name) {
    bool last_was_period = false;
  
    for (int i = 0; i < name.size(); i++) {
      // I don't trust isalnum() due to locales.  :(
      if (('a' <= name[i] && name[i] <= 'z') ||
          ('A' <= name[i] && name[i] <= 'Z') ||
          ('0' <= name[i] && name[i] <= '9') ||
          (name[i] == '_')) {
        last_was_period = false;
      } else if (name[i] == '.') {
        if (last_was_period) return false;
        last_was_period = true;
      } else {
        return false;
      }
    }
  
    return !name.empty() && !last_was_period;
  }
  
  // -------------------------------------------------------------------
  
  // This generic implementation is good for all descriptors except
  // FileDescriptor.
  template<class DescriptorT> void DescriptorBuilder::AllocateOptions(
      const typename DescriptorT::OptionsType& orig_options,
      DescriptorT* descriptor) {
    AllocateOptionsImpl(descriptor->full_name(), descriptor->full_name(),
                        orig_options, descriptor);
  }
  
  // We specialize for FileDescriptor.
  void DescriptorBuilder::AllocateOptions(const FileOptions& orig_options,
                                          FileDescriptor* descriptor) {
    // We add the dummy token so that LookupSymbol does the right thing.
    AllocateOptionsImpl(descriptor->package() + ".dummy", descriptor->name(),
                        orig_options, descriptor);
  }
  
  template<class DescriptorT> void DescriptorBuilder::AllocateOptionsImpl(
      const string& name_scope,
      const string& element_name,
      const typename DescriptorT::OptionsType& orig_options,
      DescriptorT* descriptor) {
    // We need to use a dummy pointer to work around a bug in older versions of
    // GCC.  Otherwise, the following two lines could be replaced with:
    //   typename DescriptorT::OptionsType* options =
    //       tables_->AllocateMessage<typename DescriptorT::OptionsType>();
    typename DescriptorT::OptionsType* const dummy = NULL;
    typename DescriptorT::OptionsType* options = tables_->AllocateMessage(dummy);
    // Avoid using MergeFrom()/CopyFrom() in this class to make it -fno-rtti
    // friendly. Without RTTI, MergeFrom() and CopyFrom() will fallback to the
    // reflection based method, which requires the Descriptor. However, we are in
    // the middle of building the descriptors, thus the deadlock.
    options->ParseFromString(orig_options.SerializeAsString());
    descriptor->options_ = options;
  
    // Don't add to options_to_interpret_ unless there were uninterpreted
    // options.  This not only avoids unnecessary work, but prevents a
    // bootstrapping problem when building descriptors for descriptor.proto.
    // descriptor.proto does not contain any uninterpreted options, but
    // attempting to interpret options anyway will cause
    // OptionsType::GetDescriptor() to be called which may then deadlock since
    // we're still trying to build it.
    if (options->uninterpreted_option_size() > 0) {
      options_to_interpret_.push_back(
          OptionsToInterpret(name_scope, element_name, &orig_options, options));
    }
  }
  
  
  // A common pattern:  We want to convert a repeated field in the descriptor
  // to an array of values, calling some method to build each value.
  #define BUILD_ARRAY(INPUT, OUTPUT, NAME, METHOD, PARENT)             \
    OUTPUT->NAME##_count_ = INPUT.NAME##_size();                       \
    AllocateArray(INPUT.NAME##_size(), &OUTPUT->NAME##s_);             \
    for (int i = 0; i < INPUT.NAME##_size(); i++) {                    \
      METHOD(INPUT.NAME(i), PARENT, OUTPUT->NAME##s_ + i);             \
    }
  
  void DescriptorBuilder::AddRecursiveImportError(
      const FileDescriptorProto& proto, int from_here) {
    string error_message("File recursively imports itself: ");
    for (int i = from_here; i < tables_->pending_files_.size(); i++) {
      error_message.append(tables_->pending_files_[i]);
      error_message.append(" -> ");
    }
    error_message.append(proto.name());
  
    AddError(proto.name(), proto, DescriptorPool::ErrorCollector::OTHER,
             error_message);
  }
  
  void DescriptorBuilder::AddTwiceListedError(const FileDescriptorProto& proto,
                                              int index) {
    AddError(proto.name(), proto, DescriptorPool::ErrorCollector::OTHER,
             "Import \"" + proto.dependency(index) + "\" was listed twice.");
  }
  
  void DescriptorBuilder::AddImportError(const FileDescriptorProto& proto,
                                         int index) {
    string message;
    if (pool_->fallback_database_ == NULL) {
      message = "Import \"" + proto.dependency(index) +
                "\" has not been loaded.";
    } else {
      message = "Import \"" + proto.dependency(index) +
                "\" was not found or had errors.";
    }
    AddError(proto.name(), proto, DescriptorPool::ErrorCollector::OTHER, message);
  }
  
  static bool ExistingFileMatchesProto(const FileDescriptor* existing_file,
                                       const FileDescriptorProto& proto) {
    FileDescriptorProto existing_proto;
    existing_file->CopyTo(&existing_proto);
    // TODO(liujisi): Remove it when CopyTo supports copying syntax params when
    // syntax="proto2".
    if (existing_file->syntax() == FileDescriptor::SYNTAX_PROTO2 &&
        proto.has_syntax()) {
      existing_proto.set_syntax(
          existing_file->SyntaxName(existing_file->syntax()));
    }
  
    return existing_proto.SerializeAsString() == proto.SerializeAsString();
  }
  
  const FileDescriptor* DescriptorBuilder::BuildFile(
      const FileDescriptorProto& proto) {
    filename_ = proto.name();
  
    // Check if the file already exists and is identical to the one being built.
    // Note:  This only works if the input is canonical -- that is, it
    //   fully-qualifies all type names, has no UninterpretedOptions, etc.
    //   This is fine, because this idempotency "feature" really only exists to
    //   accommodate one hack in the proto1->proto2 migration layer.
    const FileDescriptor* existing_file = tables_->FindFile(filename_);
    if (existing_file != NULL) {
      // File already in pool.  Compare the existing one to the input.
      if (ExistingFileMatchesProto(existing_file, proto)) {
        // They're identical.  Return the existing descriptor.
        return existing_file;
      }
  
      // Not a match.  The error will be detected and handled later.
    }
  
    // Check to see if this file is already on the pending files list.
    // TODO(kenton):  Allow recursive imports?  It may not work with some
    //   (most?) programming languages.  E.g., in C++, a forward declaration
    //   of a type is not sufficient to allow it to be used even in a
    //   generated header file due to inlining.  This could perhaps be
    //   worked around using tricks involving inserting #include statements
    //   mid-file, but that's pretty ugly, and I'm pretty sure there are
    //   some languages out there that do not allow recursive dependencies
    //   at all.
    for (int i = 0; i < tables_->pending_files_.size(); i++) {
      if (tables_->pending_files_[i] == proto.name()) {
        AddRecursiveImportError(proto, i);
        return NULL;
      }
    }
  
    // If we have a fallback_database_, attempt to load all dependencies now,
    // before checkpointing tables_.  This avoids confusion with recursive
    // checkpoints.
    if (pool_->fallback_database_ != NULL) {
      tables_->pending_files_.push_back(proto.name());
      for (int i = 0; i < proto.dependency_size(); i++) {
        if (tables_->FindFile(proto.dependency(i)) == NULL &&
            (pool_->underlay_ == NULL ||
             pool_->underlay_->FindFileByName(proto.dependency(i)) == NULL)) {
          // We don't care what this returns since we'll find out below anyway.
          pool_->TryFindFileInFallbackDatabase(proto.dependency(i));
        }
      }
      tables_->pending_files_.pop_back();
    }
    return BuildFileImpl(proto);
  }
  
  const FileDescriptor* DescriptorBuilder::BuildFileImpl(
      const FileDescriptorProto& proto) {
    // Checkpoint the tables so that we can roll back if something goes wrong.
    tables_->AddCheckpoint();
  
    FileDescriptor* result = tables_->Allocate<FileDescriptor>();
    file_ = result;
  
    result->is_placeholder_ = false;
    if (proto.has_source_code_info()) {
      SourceCodeInfo *info = tables_->AllocateMessage<SourceCodeInfo>();
      info->CopyFrom(proto.source_code_info());
      result->source_code_info_ = info;
    } else {
      result->source_code_info_ = &SourceCodeInfo::default_instance();
    }
  
    file_tables_ = tables_->AllocateFileTables();
    file_->tables_ = file_tables_;
  
    if (!proto.has_name()) {
      AddError("", proto, DescriptorPool::ErrorCollector::OTHER,
               "Missing field: FileDescriptorProto.name.");
    }
  
    // TODO(liujisi): Report error when the syntax is empty after all the protos
    // have added the syntax statement.
    if (proto.syntax().empty() || proto.syntax() == "proto2") {
      file_->syntax_ = FileDescriptor::SYNTAX_PROTO2;
    } else if (proto.syntax() == "proto3") {
      file_->syntax_ = FileDescriptor::SYNTAX_PROTO3;
    } else {
      file_->syntax_ = FileDescriptor::SYNTAX_UNKNOWN;
      AddError(proto.name(), proto, DescriptorPool::ErrorCollector::OTHER,
               "Unrecognized syntax: " + proto.syntax());
    }
  
    result->name_ = tables_->AllocateString(proto.name());
    if (proto.has_package()) {
      result->package_ = tables_->AllocateString(proto.package());
    } else {
      // We cannot rely on proto.package() returning a valid string if
      // proto.has_package() is false, because we might be running at static
      // initialization time, in which case default values have not yet been
      // initialized.
      result->package_ = tables_->AllocateString("");
    }
    result->pool_ = pool_;
  
    // Add to tables.
    if (!tables_->AddFile(result)) {
      AddError(proto.name(), proto, DescriptorPool::ErrorCollector::OTHER,
               "A file with this name is already in the pool.");
      // Bail out early so that if this is actually the exact same file, we
      // don't end up reporting that every single symbol is already defined.
      tables_->RollbackToLastCheckpoint();
      return NULL;
    }
    if (!result->package().empty()) {
      AddPackage(result->package(), proto, result);
    }
  
    // Make sure all dependencies are loaded.
    set<string> seen_dependencies;
    result->dependency_count_ = proto.dependency_size();
    result->dependencies_ =
      tables_->AllocateArray<const FileDescriptor*>(proto.dependency_size());
    unused_dependency_.clear();
    set<int> weak_deps;
    for (int i = 0; i < proto.weak_dependency_size(); ++i) {
      weak_deps.insert(proto.weak_dependency(i));
    }
    for (int i = 0; i < proto.dependency_size(); i++) {
      if (!seen_dependencies.insert(proto.dependency(i)).second) {
        AddTwiceListedError(proto, i);
      }
  
      const FileDescriptor* dependency = tables_->FindFile(proto.dependency(i));
      if (dependency == NULL && pool_->underlay_ != NULL) {
        dependency = pool_->underlay_->FindFileByName(proto.dependency(i));
      }
  
      if (dependency == NULL) {
        if (pool_->allow_unknown_ ||
            (!pool_->enforce_weak_ && weak_deps.find(i) != weak_deps.end())) {
          dependency = NewPlaceholderFile(proto.dependency(i));
        } else {
          AddImportError(proto, i);
        }
      } else {
        // Add to unused_dependency_ to track unused imported files.
        // Note: do not track unused imported files for public import.
        if (pool_->enforce_dependencies_ &&
            (pool_->unused_import_track_files_.find(proto.name()) !=
             pool_->unused_import_track_files_.end()) &&
            (dependency->public_dependency_count() == 0)) {
          unused_dependency_.insert(dependency);
        }
      }
  
      result->dependencies_[i] = dependency;
    }
  
    // Check public dependencies.
    int public_dependency_count = 0;
    result->public_dependencies_ = tables_->AllocateArray<int>(
        proto.public_dependency_size());
    for (int i = 0; i < proto.public_dependency_size(); i++) {
      // Only put valid public dependency indexes.
      int index = proto.public_dependency(i);
      if (index >= 0 && index < proto.dependency_size()) {
        result->public_dependencies_[public_dependency_count++] = index;
        // Do not track unused imported files for public import.
        unused_dependency_.erase(result->dependency(index));
      } else {
        AddError(proto.name(), proto,
                 DescriptorPool::ErrorCollector::OTHER,
                 "Invalid public dependency index.");
      }
    }
    result->public_dependency_count_ = public_dependency_count;
  
    // Build dependency set
    dependencies_.clear();
    for (int i = 0; i < result->dependency_count(); i++) {
      RecordPublicDependencies(result->dependency(i));
    }
  
    // Check weak dependencies.
    int weak_dependency_count = 0;
    result->weak_dependencies_ = tables_->AllocateArray<int>(
        proto.weak_dependency_size());
    for (int i = 0; i < proto.weak_dependency_size(); i++) {
      int index = proto.weak_dependency(i);
      if (index >= 0 && index < proto.dependency_size()) {
        result->weak_dependencies_[weak_dependency_count++] = index;
      } else {
        AddError(proto.name(), proto,
                 DescriptorPool::ErrorCollector::OTHER,
                 "Invalid weak dependency index.");
      }
    }
    result->weak_dependency_count_ = weak_dependency_count;
  
    // Convert children.
    BUILD_ARRAY(proto, result, message_type, BuildMessage  , NULL);
    BUILD_ARRAY(proto, result, enum_type   , BuildEnum     , NULL);
    BUILD_ARRAY(proto, result, service     , BuildService  , NULL);
    BUILD_ARRAY(proto, result, extension   , BuildExtension, NULL);
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    // Note that the following steps must occur in exactly the specified order.
  
    // Cross-link.
    CrossLinkFile(result, proto);
  
    // Interpret any remaining uninterpreted options gathered into
    // options_to_interpret_ during descriptor building.  Cross-linking has made
    // extension options known, so all interpretations should now succeed.
    if (!had_errors_) {
      OptionInterpreter option_interpreter(this);
      for (vector<OptionsToInterpret>::iterator iter =
               options_to_interpret_.begin();
           iter != options_to_interpret_.end(); ++iter) {
        option_interpreter.InterpretOptions(&(*iter));
      }
      options_to_interpret_.clear();
    }
  
    // Validate options.
    if (!had_errors_) {
      ValidateFileOptions(result, proto);
    }
  
    // Additional naming conflict check for map entry types. Only need to check
    // this if there are already errors.
    if (had_errors_) {
      for (int i = 0; i < proto.message_type_size(); ++i) {
        DetectMapConflicts(result->message_type(i), proto.message_type(i));
      }
    }
  
  
    if (!unused_dependency_.empty()) {
      LogUnusedDependency(proto, result);
    }
  
    if (had_errors_) {
      tables_->RollbackToLastCheckpoint();
      return NULL;
    } else {
      tables_->ClearLastCheckpoint();
      return result;
    }
  }
  
  void DescriptorBuilder::BuildMessage(const DescriptorProto& proto,
                                       const Descriptor* parent,
                                       Descriptor* result) {
    const string& scope = (parent == NULL) ?
      file_->package() : parent->full_name();
    string* full_name = tables_->AllocateString(scope);
    if (!full_name->empty()) full_name->append(1, '.');
    full_name->append(proto.name());
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    result->name_            = tables_->AllocateString(proto.name());
    result->full_name_       = full_name;
    result->file_            = file_;
    result->containing_type_ = parent;
    result->is_placeholder_  = false;
    result->is_unqualified_placeholder_ = false;
  
    // Build oneofs first so that fields and extension ranges can refer to them.
    BUILD_ARRAY(proto, result, oneof_decl     , BuildOneof         , result);
    BUILD_ARRAY(proto, result, field          , BuildField         , result);
    BUILD_ARRAY(proto, result, nested_type    , BuildMessage       , result);
    BUILD_ARRAY(proto, result, enum_type      , BuildEnum          , result);
    BUILD_ARRAY(proto, result, extension_range, BuildExtensionRange, result);
    BUILD_ARRAY(proto, result, extension      , BuildExtension     , result);
    BUILD_ARRAY(proto, result, reserved_range , BuildReservedRange , result);
  
    // Copy reserved names.
    int reserved_name_count = proto.reserved_name_size();
    result->reserved_name_count_ = reserved_name_count;
    result->reserved_names_ =
        tables_->AllocateArray<const string*>(reserved_name_count);
    for (int i = 0; i < reserved_name_count; ++i) {
      result->reserved_names_[i] =
          tables_->AllocateString(proto.reserved_name(i));
    }
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    AddSymbol(result->full_name(), parent, result->name(),
              proto, Symbol(result));
  
    for (int i = 0; i < proto.reserved_range_size(); i++) {
      const DescriptorProto_ReservedRange& range1 = proto.reserved_range(i);
      for (int j = i + 1; j < proto.reserved_range_size(); j++) {
        const DescriptorProto_ReservedRange& range2 = proto.reserved_range(j);
        if (range1.end() > range2.start() && range2.end() > range1.start()) {
          AddError(result->full_name(), proto.reserved_range(i),
                   DescriptorPool::ErrorCollector::NUMBER,
                   strings::Substitute("Reserved range $0 to $1 overlaps with "
                                       "already-defined range $2 to $3.",
                                       range2.start(), range2.end() - 1,
                                       range1.start(), range1.end() - 1));
        }
      }
    }
  
    hash_set<string> reserved_name_set;
    for (int i = 0; i < proto.reserved_name_size(); i++) {
      const string& name = proto.reserved_name(i);
      if (reserved_name_set.find(name) == reserved_name_set.end()) {
        reserved_name_set.insert(name);
      } else {
        AddError(name, proto, DescriptorPool::ErrorCollector::NAME,
                 strings::Substitute(
                   "Field name \"$0\" is reserved multiple times.",
                   name));
      }
    }
  
    for (int i = 0; i < result->field_count(); i++) {
      const FieldDescriptor* field = result->field(i);
      for (int j = 0; j < result->extension_range_count(); j++) {
        const Descriptor::ExtensionRange* range = result->extension_range(j);
        if (range->start <= field->number() && field->number() < range->end) {
          AddError(field->full_name(), proto.extension_range(j),
                   DescriptorPool::ErrorCollector::NUMBER,
                   strings::Substitute(
                     "Extension range $0 to $1 includes field \"$2\" ($3).",
                     range->start, range->end - 1,
                     field->name(), field->number()));
        }
      }
      for (int j = 0; j < result->reserved_range_count(); j++) {
        const Descriptor::ReservedRange* range = result->reserved_range(j);
        if (range->start <= field->number() && field->number() < range->end) {
          AddError(field->full_name(), proto.reserved_range(j),
                   DescriptorPool::ErrorCollector::NUMBER,
                   strings::Substitute(
                     "Field \"$0\" uses reserved number $1.",
                     field->name(), field->number()));
        }
      }
      if (reserved_name_set.find(field->name()) != reserved_name_set.end()) {
        AddError(field->full_name(), proto.field(i),
                 DescriptorPool::ErrorCollector::NAME,
                 strings::Substitute(
                   "Field name \"$0\" is reserved.", field->name()));
      }
    }
  
    // Check that extension ranges don't overlap and don't include
    // reserved field numbers.
    for (int i = 0; i < result->extension_range_count(); i++) {
      const Descriptor::ExtensionRange* range1 = result->extension_range(i);
      for (int j = 0; j < result->reserved_range_count(); j++) {
        const Descriptor::ReservedRange* range2 = result->reserved_range(j);
        if (range1->end > range2->start && range2->end > range1->start) {
          AddError(result->full_name(), proto.extension_range(j),
                   DescriptorPool::ErrorCollector::NUMBER,
                   strings::Substitute("Extension range $0 to $1 overlaps with "
                                       "reserved range $2 to $3.",
                                       range1->start, range1->end - 1,
                                       range2->start, range2->end - 1));
        }
      }
      for (int j = i + 1; j < result->extension_range_count(); j++) {
        const Descriptor::ExtensionRange* range2 = result->extension_range(j);
        if (range1->end > range2->start && range2->end > range1->start) {
          AddError(result->full_name(), proto.extension_range(j),
                   DescriptorPool::ErrorCollector::NUMBER,
                   strings::Substitute("Extension range $0 to $1 overlaps with "
                                       "already-defined range $2 to $3.",
                                       range2->start, range2->end - 1,
                                       range1->start, range1->end - 1));
        }
      }
    }
  }
  
  
  void DescriptorBuilder::BuildFieldOrExtension(const FieldDescriptorProto& proto,
                                                const Descriptor* parent,
                                                FieldDescriptor* result,
                                                bool is_extension) {
    const string& scope = (parent == NULL) ?
      file_->package() : parent->full_name();
    string* full_name = tables_->AllocateString(scope);
    if (!full_name->empty()) full_name->append(1, '.');
    full_name->append(proto.name());
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    result->name_         = tables_->AllocateString(proto.name());
    result->full_name_    = full_name;
    result->file_         = file_;
    result->number_       = proto.number();
    result->is_extension_ = is_extension;
  
    // If .proto files follow the style guide then the name should already be
    // lower-cased.  If that's the case we can just reuse the string we already
    // allocated rather than allocate a new one.
    string lowercase_name(proto.name());
    LowerString(&lowercase_name);
    if (lowercase_name == proto.name()) {
      result->lowercase_name_ = result->name_;
    } else {
      result->lowercase_name_ = tables_->AllocateString(lowercase_name);
    }
  
    // Don't bother with the above optimization for camel-case names since
    // .proto files that follow the guide shouldn't be using names in this
    // format, so the optimization wouldn't help much.
    result->camelcase_name_ =
        tables_->AllocateString(ToCamelCase(proto.name(),
                                            /* lower_first = */ true));
  
    if (proto.has_json_name()) {
      result->has_json_name_ = true;
      result->json_name_ = tables_->AllocateString(proto.json_name());
    } else {
      result->has_json_name_ = false;
      result->json_name_ = tables_->AllocateString(ToJsonName(proto.name()));
    }
  
    // Some compilers do not allow static_cast directly between two enum types,
    // so we must cast to int first.
    result->type_  = static_cast<FieldDescriptor::Type>(
                       implicit_cast<int>(proto.type()));
    result->label_ = static_cast<FieldDescriptor::Label>(
                       implicit_cast<int>(proto.label()));
  
    // An extension cannot have a required field (b/13365836).
    if (result->is_extension_ &&
        result->label_ == FieldDescriptor::LABEL_REQUIRED) {
      AddError(result->full_name(), proto,
               // Error location `TYPE`: we would really like to indicate
               // `LABEL`, but the `ErrorLocation` enum has no entry for this, and
               // we don't necessarily know about all implementations of the
               // `ErrorCollector` interface to extend them to handle the new
               // error location type properly.
               DescriptorPool::ErrorCollector::TYPE,
               "Message extensions cannot have required fields.");
    }
  
    // Some of these may be filled in when cross-linking.
    result->containing_type_ = NULL;
    result->extension_scope_ = NULL;
    result->message_type_ = NULL;
    result->enum_type_ = NULL;
  
    result->has_default_value_ = proto.has_default_value();
    if (proto.has_default_value() && result->is_repeated()) {
      AddError(result->full_name(), proto,
               DescriptorPool::ErrorCollector::DEFAULT_VALUE,
               "Repeated fields can't have default values.");
    }
  
    if (proto.has_type()) {
      if (proto.has_default_value()) {
        char* end_pos = NULL;
        switch (result->cpp_type()) {
          case FieldDescriptor::CPPTYPE_INT32:
            result->default_value_int32_ =
              strtol(proto.default_value().c_str(), &end_pos, 0);
            break;
          case FieldDescriptor::CPPTYPE_INT64:
            result->default_value_int64_ =
              strto64(proto.default_value().c_str(), &end_pos, 0);
            break;
          case FieldDescriptor::CPPTYPE_UINT32:
            result->default_value_uint32_ =
              strtoul(proto.default_value().c_str(), &end_pos, 0);
            break;
          case FieldDescriptor::CPPTYPE_UINT64:
            result->default_value_uint64_ =
              strtou64(proto.default_value().c_str(), &end_pos, 0);
            break;
          case FieldDescriptor::CPPTYPE_FLOAT:
            if (proto.default_value() == "inf") {
              result->default_value_float_ = numeric_limits<float>::infinity();
            } else if (proto.default_value() == "-inf") {
              result->default_value_float_ = -numeric_limits<float>::infinity();
            } else if (proto.default_value() == "nan") {
              result->default_value_float_ = numeric_limits<float>::quiet_NaN();
            } else  {
              result->default_value_float_ = io::SafeDoubleToFloat(
                  io::NoLocaleStrtod(proto.default_value().c_str(), &end_pos));
            }
            break;
          case FieldDescriptor::CPPTYPE_DOUBLE:
            if (proto.default_value() == "inf") {
              result->default_value_double_ = numeric_limits<double>::infinity();
            } else if (proto.default_value() == "-inf") {
              result->default_value_double_ = -numeric_limits<double>::infinity();
            } else if (proto.default_value() == "nan") {
              result->default_value_double_ = numeric_limits<double>::quiet_NaN();
            } else  {
              result->default_value_double_ =
                  io::NoLocaleStrtod(proto.default_value().c_str(), &end_pos);
            }
            break;
          case FieldDescriptor::CPPTYPE_BOOL:
            if (proto.default_value() == "true") {
              result->default_value_bool_ = true;
            } else if (proto.default_value() == "false") {
              result->default_value_bool_ = false;
            } else {
              AddError(result->full_name(), proto,
                       DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                       "Boolean default must be true or false.");
            }
            break;
          case FieldDescriptor::CPPTYPE_ENUM:
            // This will be filled in when cross-linking.
            result->default_value_enum_ = NULL;
            break;
          case FieldDescriptor::CPPTYPE_STRING:
            if (result->type() == FieldDescriptor::TYPE_BYTES) {
              result->default_value_string_ = tables_->AllocateString(
                UnescapeCEscapeString(proto.default_value()));
            } else {
              result->default_value_string_ =
                  tables_->AllocateString(proto.default_value());
            }
            break;
          case FieldDescriptor::CPPTYPE_MESSAGE:
            AddError(result->full_name(), proto,
                     DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                     "Messages can't have default values.");
            result->has_default_value_ = false;
            break;
        }
  
        if (end_pos != NULL) {
          // end_pos is only set non-NULL by the parsers for numeric types, above.
          // This checks that the default was non-empty and had no extra junk
          // after the end of the number.
          if (proto.default_value().empty() || *end_pos != '\0') {
            AddError(result->full_name(), proto,
                     DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                     "Couldn't parse default value \"" + proto.default_value() +
                     "\".");
          }
        }
      } else {
        // No explicit default value
        switch (result->cpp_type()) {
          case FieldDescriptor::CPPTYPE_INT32:
            result->default_value_int32_ = 0;
            break;
          case FieldDescriptor::CPPTYPE_INT64:
            result->default_value_int64_ = 0;
            break;
          case FieldDescriptor::CPPTYPE_UINT32:
            result->default_value_uint32_ = 0;
            break;
          case FieldDescriptor::CPPTYPE_UINT64:
            result->default_value_uint64_ = 0;
            break;
          case FieldDescriptor::CPPTYPE_FLOAT:
            result->default_value_float_ = 0.0f;
            break;
          case FieldDescriptor::CPPTYPE_DOUBLE:
            result->default_value_double_ = 0.0;
            break;
          case FieldDescriptor::CPPTYPE_BOOL:
            result->default_value_bool_ = false;
            break;
          case FieldDescriptor::CPPTYPE_ENUM:
            // This will be filled in when cross-linking.
            result->default_value_enum_ = NULL;
            break;
          case FieldDescriptor::CPPTYPE_STRING:
            result->default_value_string_ = &internal::GetEmptyString();
            break;
          case FieldDescriptor::CPPTYPE_MESSAGE:
            break;
        }
      }
    }
  
    if (result->number() <= 0) {
      AddError(result->full_name(), proto, DescriptorPool::ErrorCollector::NUMBER,
               "Field numbers must be positive integers.");
    } else if (!is_extension && result->number() > FieldDescriptor::kMaxNumber) {
      // Only validate that the number is within the valid field range if it is
      // not an extension. Since extension numbers are validated with the
      // extendee's valid set of extension numbers, and those are in turn
      // validated against the max allowed number, the check is unnecessary for
      // extension fields.
      // This avoids cross-linking issues that arise when attempting to check if
      // the extendee is a message_set_wire_format message, which has a higher max
      // on extension numbers.
      AddError(result->full_name(), proto, DescriptorPool::ErrorCollector::NUMBER,
               strings::Substitute("Field numbers cannot be greater than $0.",
                                   FieldDescriptor::kMaxNumber));
    } else if (result->number() >= FieldDescriptor::kFirstReservedNumber &&
               result->number() <= FieldDescriptor::kLastReservedNumber) {
      AddError(result->full_name(), proto, DescriptorPool::ErrorCollector::NUMBER,
               strings::Substitute(
                 "Field numbers $0 through $1 are reserved for the protocol "
                 "buffer library implementation.",
                 FieldDescriptor::kFirstReservedNumber,
                 FieldDescriptor::kLastReservedNumber));
    }
  
    if (is_extension) {
      if (!proto.has_extendee()) {
        AddError(result->full_name(), proto,
                 DescriptorPool::ErrorCollector::EXTENDEE,
                 "FieldDescriptorProto.extendee not set for extension field.");
      }
  
      result->extension_scope_ = parent;
  
      if (proto.has_oneof_index()) {
        AddError(result->full_name(), proto,
                 DescriptorPool::ErrorCollector::OTHER,
                 "FieldDescriptorProto.oneof_index should not be set for "
                 "extensions.");
      }
  
      // Fill in later (maybe).
      result->containing_oneof_ = NULL;
    } else {
      if (proto.has_extendee()) {
        AddError(result->full_name(), proto,
                 DescriptorPool::ErrorCollector::EXTENDEE,
                 "FieldDescriptorProto.extendee set for non-extension field.");
      }
  
      result->containing_type_ = parent;
  
      if (proto.has_oneof_index()) {
        if (proto.oneof_index() < 0 ||
            proto.oneof_index() >= parent->oneof_decl_count()) {
          AddError(result->full_name(), proto,
                   DescriptorPool::ErrorCollector::OTHER,
                   strings::Substitute("FieldDescriptorProto.oneof_index $0 is "
                                       "out of range for type \"$1\".",
                                       proto.oneof_index(),
                                       parent->name()));
          result->containing_oneof_ = NULL;
        } else {
          result->containing_oneof_ = parent->oneof_decl(proto.oneof_index());
        }
      } else {
        result->containing_oneof_ = NULL;
      }
    }
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
  
    AddSymbol(result->full_name(), parent, result->name(),
              proto, Symbol(result));
  }
  
  void DescriptorBuilder::BuildExtensionRange(
      const DescriptorProto::ExtensionRange& proto,
      const Descriptor* parent,
      Descriptor::ExtensionRange* result) {
    result->start = proto.start();
    result->end = proto.end();
    if (result->start <= 0) {
      AddError(parent->full_name(), proto,
               DescriptorPool::ErrorCollector::NUMBER,
               "Extension numbers must be positive integers.");
    }
  
    // Checking of the upper bound of the extension range is deferred until after
    // options interpreting. This allows messages with message_set_wire_format to
    // have extensions beyond FieldDescriptor::kMaxNumber, since the extension
    // numbers are actually used as int32s in the message_set_wire_format.
  
    if (result->start >= result->end) {
      AddError(parent->full_name(), proto,
               DescriptorPool::ErrorCollector::NUMBER,
               "Extension range end number must be greater than start number.");
    }
  }
  
  void DescriptorBuilder::BuildReservedRange(
      const DescriptorProto::ReservedRange& proto,
      const Descriptor* parent,
      Descriptor::ReservedRange* result) {
    result->start = proto.start();
    result->end = proto.end();
    if (result->start <= 0) {
      AddError(parent->full_name(), proto,
               DescriptorPool::ErrorCollector::NUMBER,
               "Reserved numbers must be positive integers.");
    }
  }
  
  void DescriptorBuilder::BuildOneof(const OneofDescriptorProto& proto,
                                     Descriptor* parent,
                                     OneofDescriptor* result) {
    string* full_name = tables_->AllocateString(parent->full_name());
    full_name->append(1, '.');
    full_name->append(proto.name());
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    result->name_ = tables_->AllocateString(proto.name());
    result->full_name_ = full_name;
  
    result->containing_type_ = parent;
  
    // We need to fill these in later.
    result->field_count_ = 0;
    result->fields_ = NULL;
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    AddSymbol(result->full_name(), parent, result->name(),
              proto, Symbol(result));
  }
  
  void DescriptorBuilder::CheckEnumValueUniqueness(
      const EnumDescriptorProto& proto, const EnumDescriptor* result) {
  
    // Check that enum labels are still unique when we remove the enum prefix from
    // values that have it.
    //
    // This will fail for something like:
    //
    //   enum MyEnum {
    //     MY_ENUM_FOO = 0;
    //     FOO = 1;
    //   }
    //
    // By enforcing this reasonable constraint, we allow code generators to strip
    // the prefix and/or PascalCase it without creating conflicts.  This can lead
    // to much nicer language-specific enums like:
    //
    //   enum NameType {
    //     FirstName = 1,
    //     LastName = 2,
    //   }
    //
    // Instead of:
    //
    //   enum NameType {
    //     NAME_TYPE_FIRST_NAME = 1,
    //     NAME_TYPE_LAST_NAME = 2,
    //   }
    PrefixRemover remover(result->name());
    map<string, const google::protobuf::EnumValueDescriptor*> values;
    for (int i = 0; i < result->value_count(); i++) {
      const google::protobuf::EnumValueDescriptor* value = result->value(i);
      string stripped =
          EnumValueToPascalCase(remover.MaybeRemove(value->name()));
      std::pair<map<string, const google::protobuf::EnumValueDescriptor*>::iterator, bool>
          insert_result = values.insert(std::make_pair(stripped, value));
      bool inserted = insert_result.second;
  
      // We don't throw the error if the two conflicting symbols are identical, or
      // if they map to the same number.  In the former case, the normal symbol
      // duplication error will fire so we don't need to (and its error message
      // will make more sense). We allow the latter case so users can create
      // aliases which add or remove the prefix (code generators that do prefix
      // stripping should de-dup the labels in this case).
      if (!inserted && insert_result.first->second->name() != value->name() &&
          insert_result.first->second->number() != value->number()) {
        string error_message =
            "When enum name is stripped and label is PascalCased (" + stripped +
            "), this value label conflicts with " + values[stripped]->name() +
            ". This will make the proto fail to compile for some languages, such "
            "as C#.";
        // There are proto2 enums out there with conflicting names, so to preserve
        // compatibility we issue only a warning for proto2.
        if (result->file()->syntax() == FileDescriptor::SYNTAX_PROTO2) {
          AddWarning(value->full_name(), proto.value(i),
                     DescriptorPool::ErrorCollector::NAME, error_message);
        } else {
          AddError(value->full_name(), proto.value(i),
                   DescriptorPool::ErrorCollector::NAME, error_message);
        }
      }
    }
  }
  
  void DescriptorBuilder::BuildEnum(const EnumDescriptorProto& proto,
                                    const Descriptor* parent,
                                    EnumDescriptor* result) {
    const string& scope = (parent == NULL) ?
      file_->package() : parent->full_name();
    string* full_name = tables_->AllocateString(scope);
    if (!full_name->empty()) full_name->append(1, '.');
    full_name->append(proto.name());
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    result->name_            = tables_->AllocateString(proto.name());
    result->full_name_       = full_name;
    result->file_            = file_;
    result->containing_type_ = parent;
    result->is_placeholder_  = false;
    result->is_unqualified_placeholder_ = false;
  
    if (proto.value_size() == 0) {
      // We cannot allow enums with no values because this would mean there
      // would be no valid default value for fields of this type.
      AddError(result->full_name(), proto,
               DescriptorPool::ErrorCollector::NAME,
               "Enums must contain at least one value.");
    }
  
    BUILD_ARRAY(proto, result, value, BuildEnumValue, result);
  
    CheckEnumValueUniqueness(proto, result);
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    AddSymbol(result->full_name(), parent, result->name(),
              proto, Symbol(result));
  }
  
  void DescriptorBuilder::BuildEnumValue(const EnumValueDescriptorProto& proto,
                                         const EnumDescriptor* parent,
                                         EnumValueDescriptor* result) {
    result->name_   = tables_->AllocateString(proto.name());
    result->number_ = proto.number();
    result->type_   = parent;
  
    // Note:  full_name for enum values is a sibling to the parent's name, not a
    //   child of it.
    string* full_name = tables_->AllocateString(*parent->full_name_);
    full_name->resize(full_name->size() - parent->name_->size());
    full_name->append(*result->name_);
    result->full_name_ = full_name;
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    // Again, enum values are weird because we makes them appear as siblings
    // of the enum type instead of children of it.  So, we use
    // parent->containing_type() as the value's parent.
    bool added_to_outer_scope =
      AddSymbol(result->full_name(), parent->containing_type(), result->name(),
                proto, Symbol(result));
  
    // However, we also want to be able to search for values within a single
    // enum type, so we add it as a child of the enum type itself, too.
    // Note:  This could fail, but if it does, the error has already been
    //   reported by the above AddSymbol() call, so we ignore the return code.
    bool added_to_inner_scope =
      file_tables_->AddAliasUnderParent(parent, result->name(), Symbol(result));
  
    if (added_to_inner_scope && !added_to_outer_scope) {
      // This value did not conflict with any values defined in the same enum,
      // but it did conflict with some other symbol defined in the enum type's
      // scope.  Let's print an additional error to explain this.
      string outer_scope;
      if (parent->containing_type() == NULL) {
        outer_scope = file_->package();
      } else {
        outer_scope = parent->containing_type()->full_name();
      }
  
      if (outer_scope.empty()) {
        outer_scope = "the global scope";
      } else {
        outer_scope = "\"" + outer_scope + "\"";
      }
  
      AddError(result->full_name(), proto,
               DescriptorPool::ErrorCollector::NAME,
               "Note that enum values use C++ scoping rules, meaning that "
               "enum values are siblings of their type, not children of it.  "
               "Therefore, \"" + result->name() + "\" must be unique within "
               + outer_scope + ", not just within \"" + parent->name() + "\".");
    }
  
    // An enum is allowed to define two numbers that refer to the same value.
    // FindValueByNumber() should return the first such value, so we simply
    // ignore AddEnumValueByNumber()'s return code.
    file_tables_->AddEnumValueByNumber(result);
  }
  
  void DescriptorBuilder::BuildService(const ServiceDescriptorProto& proto,
                                       const void* /* dummy */,
                                       ServiceDescriptor* result) {
    string* full_name = tables_->AllocateString(file_->package());
    if (!full_name->empty()) full_name->append(1, '.');
    full_name->append(proto.name());
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    result->name_      = tables_->AllocateString(proto.name());
    result->full_name_ = full_name;
    result->file_      = file_;
  
    BUILD_ARRAY(proto, result, method, BuildMethod, result);
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    AddSymbol(result->full_name(), NULL, result->name(),
              proto, Symbol(result));
  }
  
  void DescriptorBuilder::BuildMethod(const MethodDescriptorProto& proto,
                                      const ServiceDescriptor* parent,
                                      MethodDescriptor* result) {
    result->name_    = tables_->AllocateString(proto.name());
    result->service_ = parent;
  
    string* full_name = tables_->AllocateString(parent->full_name());
    full_name->append(1, '.');
    full_name->append(*result->name_);
    result->full_name_ = full_name;
  
    ValidateSymbolName(proto.name(), *full_name, proto);
  
    // These will be filled in when cross-linking.
    result->input_type_ = NULL;
    result->output_type_ = NULL;
  
    // Copy options.
    if (!proto.has_options()) {
      result->options_ = NULL;  // Will set to default_instance later.
    } else {
      AllocateOptions(proto.options(), result);
    }
  
    result->client_streaming_ = proto.client_streaming();
    result->server_streaming_ = proto.server_streaming();
  
    AddSymbol(result->full_name(), parent, result->name(),
              proto, Symbol(result));
  }
  
  #undef BUILD_ARRAY
  
  // -------------------------------------------------------------------
  
  void DescriptorBuilder::CrossLinkFile(
      FileDescriptor* file, const FileDescriptorProto& proto) {
    if (file->options_ == NULL) {
      file->options_ = &FileOptions::default_instance();
    }
  
    for (int i = 0; i < file->message_type_count(); i++) {
      CrossLinkMessage(&file->message_types_[i], proto.message_type(i));
    }
  
    for (int i = 0; i < file->extension_count(); i++) {
      CrossLinkField(&file->extensions_[i], proto.extension(i));
    }
  
    for (int i = 0; i < file->enum_type_count(); i++) {
      CrossLinkEnum(&file->enum_types_[i], proto.enum_type(i));
    }
  
    for (int i = 0; i < file->service_count(); i++) {
      CrossLinkService(&file->services_[i], proto.service(i));
    }
  }
  
  void DescriptorBuilder::CrossLinkMessage(
      Descriptor* message, const DescriptorProto& proto) {
    if (message->options_ == NULL) {
      message->options_ = &MessageOptions::default_instance();
    }
  
    for (int i = 0; i < message->nested_type_count(); i++) {
      CrossLinkMessage(&message->nested_types_[i], proto.nested_type(i));
    }
  
    for (int i = 0; i < message->enum_type_count(); i++) {
      CrossLinkEnum(&message->enum_types_[i], proto.enum_type(i));
    }
  
    for (int i = 0; i < message->field_count(); i++) {
      CrossLinkField(&message->fields_[i], proto.field(i));
    }
  
    for (int i = 0; i < message->extension_count(); i++) {
      CrossLinkField(&message->extensions_[i], proto.extension(i));
    }
  
    // Set up field array for each oneof.
  
    // First count the number of fields per oneof.
    for (int i = 0; i < message->field_count(); i++) {
      const OneofDescriptor* oneof_decl = message->field(i)->containing_oneof();
      if (oneof_decl != NULL) {
        // Make sure fields belonging to the same oneof are defined consecutively.
        // This enables optimizations in codegens and reflection libraries to
        // skip fields in the oneof group, as only one of the field can be set.
        // Note that field_count() returns how many fields in this oneof we have
        // seen so far. field_count() > 0 guarantees that i > 0, so field(i-1) is
        // safe.
        if (oneof_decl->field_count() > 0 &&
            message->field(i - 1)->containing_oneof() != oneof_decl) {
          AddError(
              message->full_name() + "." + message->field(i - 1)->name(),
              proto.field(i - 1), DescriptorPool::ErrorCollector::OTHER,
              strings::Substitute(
                  "Fields in the same oneof must be defined consecutively. "
                  "\"$0\" cannot be defined before the completion of the "
                  "\"$1\" oneof definition.",
                  message->field(i - 1)->name(), oneof_decl->name()));
        }
        // Must go through oneof_decls_ array to get a non-const version of the
        // OneofDescriptor.
        ++message->oneof_decls_[oneof_decl->index()].field_count_;
      }
    }
  
    // Then allocate the arrays.
    for (int i = 0; i < message->oneof_decl_count(); i++) {
      OneofDescriptor* oneof_decl = &message->oneof_decls_[i];
  
      if (oneof_decl->field_count() == 0) {
        AddError(message->full_name() + "." + oneof_decl->name(),
                 proto.oneof_decl(i),
                 DescriptorPool::ErrorCollector::NAME,
                 "Oneof must have at least one field.");
      }
  
      oneof_decl->fields_ =
        tables_->AllocateArray<const FieldDescriptor*>(oneof_decl->field_count_);
      oneof_decl->field_count_ = 0;
  
      if (oneof_decl->options_ == NULL) {
        oneof_decl->options_ = &OneofOptions::default_instance();
      }
    }
  
    // Then fill them in.
    for (int i = 0; i < message->field_count(); i++) {
      const OneofDescriptor* oneof_decl = message->field(i)->containing_oneof();
      if (oneof_decl != NULL) {
        OneofDescriptor* mutable_oneof_decl =
            &message->oneof_decls_[oneof_decl->index()];
        message->fields_[i].index_in_oneof_ = mutable_oneof_decl->field_count_;
        mutable_oneof_decl->fields_[mutable_oneof_decl->field_count_++] =
            message->field(i);
      }
    }
  }
  
  void DescriptorBuilder::CrossLinkField(
      FieldDescriptor* field, const FieldDescriptorProto& proto) {
    if (field->options_ == NULL) {
      field->options_ = &FieldOptions::default_instance();
    }
  
    if (proto.has_extendee()) {
      Symbol extendee = LookupSymbol(proto.extendee(), field->full_name(),
                                     PLACEHOLDER_EXTENDABLE_MESSAGE);
      if (extendee.IsNull()) {
        AddNotDefinedError(field->full_name(), proto,
                           DescriptorPool::ErrorCollector::EXTENDEE,
                           proto.extendee());
        return;
      } else if (extendee.type != Symbol::MESSAGE) {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::EXTENDEE,
                 "\"" + proto.extendee() + "\" is not a message type.");
        return;
      }
      field->containing_type_ = extendee.descriptor;
  
      const Descriptor::ExtensionRange* extension_range = field->containing_type()
          ->FindExtensionRangeContainingNumber(field->number());
  
      if (extension_range == NULL) {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::NUMBER,
                 strings::Substitute("\"$0\" does not declare $1 as an "
                                     "extension number.",
                                     field->containing_type()->full_name(),
                                     field->number()));
      }
    }
  
    if (field->containing_oneof() != NULL) {
      if (field->label() != FieldDescriptor::LABEL_OPTIONAL) {
        // Note that this error will never happen when parsing .proto files.
        // It can only happen if you manually construct a FileDescriptorProto
        // that is incorrect.
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::NAME,
                 "Fields of oneofs must themselves have label LABEL_OPTIONAL.");
      }
    }
  
    if (proto.has_type_name()) {
      // Assume we are expecting a message type unless the proto contains some
      // evidence that it expects an enum type.  This only makes a difference if
      // we end up creating a placeholder.
      bool expecting_enum = (proto.type() == FieldDescriptorProto::TYPE_ENUM) ||
                            proto.has_default_value();
  
      Symbol type =
        LookupSymbol(proto.type_name(), field->full_name(),
                     expecting_enum ? PLACEHOLDER_ENUM : PLACEHOLDER_MESSAGE,
                     LOOKUP_TYPES);
  
      // If the type is a weak type, we change the type to a google.protobuf.Empty field.
      if (type.IsNull() && !pool_->enforce_weak_ && proto.options().weak()) {
        type = FindSymbol(kNonLinkedWeakMessageReplacementName);
      }
  
      if (type.IsNull()) {
        AddNotDefinedError(field->full_name(), proto,
                           DescriptorPool::ErrorCollector::TYPE,
                           proto.type_name());
        return;
      }
  
      if (!proto.has_type()) {
        // Choose field type based on symbol.
        if (type.type == Symbol::MESSAGE) {
          field->type_ = FieldDescriptor::TYPE_MESSAGE;
        } else if (type.type == Symbol::ENUM) {
          field->type_ = FieldDescriptor::TYPE_ENUM;
        } else {
          AddError(field->full_name(), proto,
                   DescriptorPool::ErrorCollector::TYPE,
                   "\"" + proto.type_name() + "\" is not a type.");
          return;
        }
      }
  
      if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
        if (type.type != Symbol::MESSAGE) {
          AddError(field->full_name(), proto,
                   DescriptorPool::ErrorCollector::TYPE,
                   "\"" + proto.type_name() + "\" is not a message type.");
          return;
        }
        field->message_type_ = type.descriptor;
  
        if (field->has_default_value()) {
          AddError(field->full_name(), proto,
                   DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                   "Messages can't have default values.");
        }
      } else if (field->cpp_type() == FieldDescriptor::CPPTYPE_ENUM) {
        if (type.type != Symbol::ENUM) {
          AddError(field->full_name(), proto,
                   DescriptorPool::ErrorCollector::TYPE,
                   "\"" + proto.type_name() + "\" is not an enum type.");
          return;
        }
        field->enum_type_ = type.enum_descriptor;
  
        if (field->enum_type()->is_placeholder_) {
          // We can't look up default values for placeholder types.  We'll have
          // to just drop them.
          field->has_default_value_ = false;
        }
  
        if (field->has_default_value()) {
          // Ensure that the default value is an identifier. Parser cannot always
          // verify this because it does not have complete type information.
          // N.B. that this check yields better error messages but is not
          // necessary for correctness (an enum symbol must be a valid identifier
          // anyway), only for better errors.
          if (!io::Tokenizer::IsIdentifier(proto.default_value())) {
            AddError(field->full_name(), proto,
                     DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                     "Default value for an enum field must be an identifier.");
          } else {
            // We can't just use field->enum_type()->FindValueByName() here
            // because that locks the pool's mutex, which we have already locked
            // at this point.
            Symbol default_value =
              LookupSymbolNoPlaceholder(proto.default_value(),
                                        field->enum_type()->full_name());
  
            if (default_value.type == Symbol::ENUM_VALUE &&
                default_value.enum_value_descriptor->type() ==
                field->enum_type()) {
              field->default_value_enum_ = default_value.enum_value_descriptor;
            } else {
              AddError(field->full_name(), proto,
                       DescriptorPool::ErrorCollector::DEFAULT_VALUE,
                       "Enum type \"" + field->enum_type()->full_name() +
                       "\" has no value named \"" + proto.default_value() +
                       "\".");
            }
          }
        } else if (field->enum_type()->value_count() > 0) {
          // All enums must have at least one value, or we would have reported
          // an error elsewhere.  We use the first defined value as the default
          // if a default is not explicitly defined.
          field->default_value_enum_ = field->enum_type()->value(0);
        }
      } else {
        AddError(field->full_name(), proto, DescriptorPool::ErrorCollector::TYPE,
                 "Field with primitive type has type_name.");
      }
    } else {
      if (field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE ||
          field->cpp_type() == FieldDescriptor::CPPTYPE_ENUM) {
        AddError(field->full_name(), proto, DescriptorPool::ErrorCollector::TYPE,
                 "Field with message or enum type missing type_name.");
      }
    }
  
    // Add the field to the fields-by-number table.
    // Note:  We have to do this *after* cross-linking because extensions do not
    //   know their containing type until now.
    if (!file_tables_->AddFieldByNumber(field)) {
      const FieldDescriptor* conflicting_field =
        file_tables_->FindFieldByNumber(field->containing_type(),
                                        field->number());
      if (field->is_extension()) {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::NUMBER,
                 strings::Substitute("Extension number $0 has already been used "
                                     "in \"$1\" by extension \"$2\".",
                                     field->number(),
                                     field->containing_type()->full_name(),
                                     conflicting_field->full_name()));
      } else {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::NUMBER,
                 strings::Substitute("Field number $0 has already been used in "
                                     "\"$1\" by field \"$2\".",
                                     field->number(),
                                     field->containing_type()->full_name(),
                                     conflicting_field->name()));
      }
    } else {
      if (field->is_extension()) {
        if (!tables_->AddExtension(field)) {
          const FieldDescriptor* conflicting_field =
              tables_->FindExtension(field->containing_type(), field->number());
          string error_msg = strings::Substitute(
              "Extension number $0 has already been used in \"$1\" by extension "
              "\"$2\" defined in $3.",
              field->number(),
              field->containing_type()->full_name(),
              conflicting_field->full_name(),
              conflicting_field->file()->name());
          // Conflicting extension numbers should be an error. However, before
          // turning this into an error we need to fix all existing broken
          // protos first.
          // TODO(xiaofeng): Change this to an error.
          AddWarning(field->full_name(), proto,
                     DescriptorPool::ErrorCollector::NUMBER, error_msg);
        }
      }
    }
  
    // Add the field to the lowercase-name and camelcase-name tables.
    file_tables_->AddFieldByStylizedNames(field);
  }
  
  void DescriptorBuilder::CrossLinkEnum(
      EnumDescriptor* enum_type, const EnumDescriptorProto& proto) {
    if (enum_type->options_ == NULL) {
      enum_type->options_ = &EnumOptions::default_instance();
    }
  
    for (int i = 0; i < enum_type->value_count(); i++) {
      CrossLinkEnumValue(&enum_type->values_[i], proto.value(i));
    }
  }
  
  void DescriptorBuilder::CrossLinkEnumValue(
      EnumValueDescriptor* enum_value,
      const EnumValueDescriptorProto& /* proto */) {
    if (enum_value->options_ == NULL) {
      enum_value->options_ = &EnumValueOptions::default_instance();
    }
  }
  
  void DescriptorBuilder::CrossLinkService(
      ServiceDescriptor* service, const ServiceDescriptorProto& proto) {
    if (service->options_ == NULL) {
      service->options_ = &ServiceOptions::default_instance();
    }
  
    for (int i = 0; i < service->method_count(); i++) {
      CrossLinkMethod(&service->methods_[i], proto.method(i));
    }
  }
  
  void DescriptorBuilder::CrossLinkMethod(
      MethodDescriptor* method, const MethodDescriptorProto& proto) {
    if (method->options_ == NULL) {
      method->options_ = &MethodOptions::default_instance();
    }
  
    Symbol input_type = LookupSymbol(proto.input_type(), method->full_name());
    if (input_type.IsNull()) {
      AddNotDefinedError(method->full_name(), proto,
                         DescriptorPool::ErrorCollector::INPUT_TYPE,
                         proto.input_type());
    } else if (input_type.type != Symbol::MESSAGE) {
      AddError(method->full_name(), proto,
               DescriptorPool::ErrorCollector::INPUT_TYPE,
               "\"" + proto.input_type() + "\" is not a message type.");
    } else {
      method->input_type_ = input_type.descriptor;
    }
  
    Symbol output_type = LookupSymbol(proto.output_type(), method->full_name());
    if (output_type.IsNull()) {
      AddNotDefinedError(method->full_name(), proto,
                         DescriptorPool::ErrorCollector::OUTPUT_TYPE,
                         proto.output_type());
    } else if (output_type.type != Symbol::MESSAGE) {
      AddError(method->full_name(), proto,
               DescriptorPool::ErrorCollector::OUTPUT_TYPE,
               "\"" + proto.output_type() + "\" is not a message type.");
    } else {
      method->output_type_ = output_type.descriptor;
    }
  }
  
  // -------------------------------------------------------------------
  
  #define VALIDATE_OPTIONS_FROM_ARRAY(descriptor, array_name, type)  \
    for (int i = 0; i < descriptor->array_name##_count(); ++i) {     \
      Validate##type##Options(descriptor->array_name##s_ + i,        \
                              proto.array_name(i));                  \
    }
  
  // Determine if the file uses optimize_for = LITE_RUNTIME, being careful to
  // avoid problems that exist at init time.
  static bool IsLite(const FileDescriptor* file) {
    // TODO(kenton):  I don't even remember how many of these conditions are
    //   actually possible.  I'm just being super-safe.
    return file != NULL &&
           &file->options() != &FileOptions::default_instance() &&
           file->options().optimize_for() == FileOptions::LITE_RUNTIME;
  }
  
  void DescriptorBuilder::ValidateFileOptions(FileDescriptor* file,
                                              const FileDescriptorProto& proto) {
    VALIDATE_OPTIONS_FROM_ARRAY(file, message_type, Message);
    VALIDATE_OPTIONS_FROM_ARRAY(file, enum_type, Enum);
    VALIDATE_OPTIONS_FROM_ARRAY(file, service, Service);
    VALIDATE_OPTIONS_FROM_ARRAY(file, extension, Field);
  
    // Lite files can only be imported by other Lite files.
    if (!IsLite(file)) {
      for (int i = 0; i < file->dependency_count(); i++) {
        if (IsLite(file->dependency(i))) {
          AddError(
            file->name(), proto,
            DescriptorPool::ErrorCollector::OTHER,
            "Files that do not use optimize_for = LITE_RUNTIME cannot import "
            "files which do use this option.  This file is not lite, but it "
            "imports \"" + file->dependency(i)->name() + "\" which is.");
          break;
        }
      }
    }
    if (file->syntax() == FileDescriptor::SYNTAX_PROTO3) {
      ValidateProto3(file, proto);
    }
  }
  
  void DescriptorBuilder::ValidateProto3(
      FileDescriptor* file, const FileDescriptorProto& proto) {
    for (int i = 0; i < file->extension_count(); ++i) {
      ValidateProto3Field(file->extensions_ + i, proto.extension(i));
    }
    for (int i = 0; i < file->message_type_count(); ++i) {
      ValidateProto3Message(file->message_types_ + i, proto.message_type(i));
    }
    for (int i = 0; i < file->enum_type_count(); ++i) {
      ValidateProto3Enum(file->enum_types_ + i, proto.enum_type(i));
    }
  }
  
  static string ToLowercaseWithoutUnderscores(const string& name) {
    string result;
    for (int i = 0; i < name.size(); ++i) {
      if (name[i] != '_') {
        if (name[i] >= 'A' && name[i] <= 'Z') {
          result.push_back(name[i] - 'A' + 'a');
        } else {
          result.push_back(name[i]);
        }
      }
    }
    return result;
  }
  
  void DescriptorBuilder::ValidateProto3Message(
      Descriptor* message, const DescriptorProto& proto) {
    for (int i = 0; i < message->nested_type_count(); ++i) {
      ValidateProto3Message(message->nested_types_ + i,
                                   proto.nested_type(i));
    }
    for (int i = 0; i < message->enum_type_count(); ++i) {
      ValidateProto3Enum(message->enum_types_ + i,
                                proto.enum_type(i));
    }
    for (int i = 0; i < message->field_count(); ++i) {
      ValidateProto3Field(message->fields_ + i, proto.field(i));
    }
    for (int i = 0; i < message->extension_count(); ++i) {
      ValidateProto3Field(message->extensions_ +i, proto.extension(i));
    }
    if (message->extension_range_count() > 0) {
      AddError(message->full_name(), proto,
               DescriptorPool::ErrorCollector::OTHER,
               "Extension ranges are not allowed in proto3.");
    }
    if (message->options().message_set_wire_format()) {
      // Using MessageSet doesn't make sense since we disallow extensions.
      AddError(message->full_name(), proto,
               DescriptorPool::ErrorCollector::OTHER,
               "MessageSet is not supported in proto3.");
    }
  
    // In proto3, we reject field names if they conflict in camelCase.
    // Note that we currently enforce a stricter rule: Field names must be
    // unique after being converted to lowercase with underscores removed.
    map<string, const FieldDescriptor*> name_to_field;
    for (int i = 0; i < message->field_count(); ++i) {
      string lowercase_name = ToLowercaseWithoutUnderscores(
          message->field(i)->name());
      if (name_to_field.find(lowercase_name) != name_to_field.end()) {
        AddError(message->full_name(), proto,
                 DescriptorPool::ErrorCollector::OTHER,
                 "The JSON camel-case name of field \"" +
                 message->field(i)->name() + "\" conflicts with field \"" +
                 name_to_field[lowercase_name]->name() + "\". This is not " +
                 "allowed in proto3.");
      } else {
        name_to_field[lowercase_name] = message->field(i);
      }
    }
  }
  
  void DescriptorBuilder::ValidateProto3Field(
      FieldDescriptor* field, const FieldDescriptorProto& proto) {
    if (field->is_extension() &&
        !AllowedExtendeeInProto3(field->containing_type()->full_name())) {
      AddError(field->full_name(), proto,
               DescriptorPool::ErrorCollector::OTHER,
               "Extensions in proto3 are only allowed for defining options.");
    }
    if (field->is_required()) {
      AddError(field->full_name(), proto,
               DescriptorPool::ErrorCollector::OTHER,
               "Required fields are not allowed in proto3.");
    }
    if (field->has_default_value()) {
      AddError(
          field->full_name(), proto, DescriptorPool::ErrorCollector::OTHER,
          "Explicit default values are not allowed in proto3.");
    }
    if (field->cpp_type() == FieldDescriptor::CPPTYPE_ENUM &&
        field->enum_type() &&
        field->enum_type()->file()->syntax() != FileDescriptor::SYNTAX_PROTO3) {
      // Proto3 messages can only use Proto3 enum types; otherwise we can't
      // guarantee that the default value is zero.
      AddError(field->full_name(), proto,
               DescriptorPool::ErrorCollector::TYPE,
               "Enum type \"" + field->enum_type()->full_name() +
               "\" is not a proto3 enum, but is used in \"" +
               field->containing_type()->full_name() +
               "\" which is a proto3 message type.");
    }
    if (field->type() == FieldDescriptor::TYPE_GROUP) {
      AddError(field->full_name(), proto,
               DescriptorPool::ErrorCollector::TYPE,
               "Groups are not supported in proto3 syntax.");
    }
  }
  
  void DescriptorBuilder::ValidateProto3Enum(
      EnumDescriptor* enm, const EnumDescriptorProto& proto) {
    if (enm->value_count() > 0 && enm->value(0)->number() != 0) {
      AddError(
          enm->full_name(), proto, DescriptorPool::ErrorCollector::OTHER,
          "The first enum value must be zero in proto3.");
    }
  }
  
  void DescriptorBuilder::ValidateMessageOptions(Descriptor* message,
                                                 const DescriptorProto& proto) {
    VALIDATE_OPTIONS_FROM_ARRAY(message, field, Field);
    VALIDATE_OPTIONS_FROM_ARRAY(message, nested_type, Message);
    VALIDATE_OPTIONS_FROM_ARRAY(message, enum_type, Enum);
    VALIDATE_OPTIONS_FROM_ARRAY(message, extension, Field);
  
    const int64 max_extension_range =
        static_cast<int64>(message->options().message_set_wire_format() ?
                           kint32max :
                           FieldDescriptor::kMaxNumber);
    for (int i = 0; i < message->extension_range_count(); ++i) {
      if (message->extension_range(i)->end > max_extension_range + 1) {
        AddError(
            message->full_name(), proto.extension_range(i),
            DescriptorPool::ErrorCollector::NUMBER,
            strings::Substitute("Extension numbers cannot be greater than $0.",
                                max_extension_range));
      }
    }
  }
  
  void DescriptorBuilder::ValidateFieldOptions(FieldDescriptor* field,
      const FieldDescriptorProto& proto) {
    // Only message type fields may be lazy.
    if (field->options().lazy()) {
      if (field->type() != FieldDescriptor::TYPE_MESSAGE) {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::TYPE,
                 "[lazy = true] can only be specified for submessage fields.");
      }
    }
  
    // Only repeated primitive fields may be packed.
    if (field->options().packed() && !field->is_packable()) {
      AddError(
        field->full_name(), proto,
        DescriptorPool::ErrorCollector::TYPE,
        "[packed = true] can only be specified for repeated primitive fields.");
    }
  
    // Note:  Default instance may not yet be initialized here, so we have to
    //   avoid reading from it.
    if (field->containing_type_ != NULL &&
        &field->containing_type()->options() !=
        &MessageOptions::default_instance() &&
        field->containing_type()->options().message_set_wire_format()) {
      if (field->is_extension()) {
        if (!field->is_optional() ||
            field->type() != FieldDescriptor::TYPE_MESSAGE) {
          AddError(field->full_name(), proto,
                   DescriptorPool::ErrorCollector::TYPE,
                   "Extensions of MessageSets must be optional messages.");
        }
      } else {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::NAME,
                 "MessageSets cannot have fields, only extensions.");
      }
    }
  
    // Lite extensions can only be of Lite types.
    if (IsLite(field->file()) &&
        field->containing_type_ != NULL &&
        !IsLite(field->containing_type()->file())) {
      AddError(field->full_name(), proto,
               DescriptorPool::ErrorCollector::EXTENDEE,
               "Extensions to non-lite types can only be declared in non-lite "
               "files.  Note that you cannot extend a non-lite type to contain "
               "a lite type, but the reverse is allowed.");
    }
  
    // Validate map types.
    if (field->is_map()) {
      if (!ValidateMapEntry(field, proto)) {
        AddError(field->full_name(), proto,
                 DescriptorPool::ErrorCollector::OTHER,
                 "map_entry should not be set explicitly. Use map<KeyType, "
                 "ValueType> instead.");
      }
    }
  
  }
  
  void DescriptorBuilder::ValidateEnumOptions(EnumDescriptor* enm,
                                              const EnumDescriptorProto& proto) {
    VALIDATE_OPTIONS_FROM_ARRAY(enm, value, EnumValue);
    if (!enm->options().has_allow_alias() || !enm->options().allow_alias()) {
      map<int, string> used_values;
      for (int i = 0; i < enm->value_count(); ++i) {
        const EnumValueDescriptor* enum_value = enm->value(i);
        if (used_values.find(enum_value->number()) != used_values.end()) {
          string error =
              "\"" + enum_value->full_name() +
              "\" uses the same enum value as \"" +
              used_values[enum_value->number()] + "\". If this is intended, set "
              "'option allow_alias = true;' to the enum definition.";
          if (!enm->options().allow_alias()) {
            // Generate error if duplicated enum values are explicitly disallowed.
            AddError(enm->full_name(), proto,
                     DescriptorPool::ErrorCollector::NUMBER,
                     error);
          } else {
            // Generate warning if duplicated values are found but the option
            // isn't set.
            GOOGLE_LOG(ERROR) << error;
          }
        } else {
          used_values[enum_value->number()] = enum_value->full_name();
        }
      }
    }
  }
  
  void DescriptorBuilder::ValidateEnumValueOptions(
      EnumValueDescriptor* /* enum_value */,
      const EnumValueDescriptorProto& /* proto */) {
    // Nothing to do so far.
  }
  void DescriptorBuilder::ValidateServiceOptions(ServiceDescriptor* service,
      const ServiceDescriptorProto& proto) {
    if (IsLite(service->file()) &&
        (service->file()->options().cc_generic_services() ||
         service->file()->options().java_generic_services())) {
      AddError(service->full_name(), proto,
               DescriptorPool::ErrorCollector::NAME,
               "Files with optimize_for = LITE_RUNTIME cannot define services "
               "unless you set both options cc_generic_services and "
               "java_generic_sevices to false.");
    }
  
    VALIDATE_OPTIONS_FROM_ARRAY(service, method, Method);
  }
  
  void DescriptorBuilder::ValidateMethodOptions(MethodDescriptor* /* method */,
      const MethodDescriptorProto& /* proto */) {
    // Nothing to do so far.
  }
  
  bool DescriptorBuilder::ValidateMapEntry(FieldDescriptor* field,
                                           const FieldDescriptorProto& proto) {
    const Descriptor* message = field->message_type();
    if (// Must not contain extensions, extension range or nested message or
        // enums
        message->extension_count() != 0 ||
        field->label() != FieldDescriptor::LABEL_REPEATED ||
        message->extension_range_count() != 0 ||
        message->nested_type_count() != 0 || message->enum_type_count() != 0 ||
        // Must contain exactly two fields
        message->field_count() != 2 ||
        // Field name and message name must match
        message->name() != ToCamelCase(field->name(), false) + "Entry" ||
        // Entry message must be in the same containing type of the field.
        field->containing_type() != message->containing_type()) {
      return false;
    }
  
    const FieldDescriptor* key = message->field(0);
    const FieldDescriptor* value = message->field(1);
    if (key->label() != FieldDescriptor::LABEL_OPTIONAL || key->number() != 1 ||
        key->name() != "key") {
      return false;
    }
    if (value->label() != FieldDescriptor::LABEL_OPTIONAL ||
        value->number() != 2 || value->name() != "value") {
      return false;
    }
  
    // Check key types are legal.
    switch (key->type()) {
      case FieldDescriptor::TYPE_ENUM:
        AddError(
            field->full_name(), proto, DescriptorPool::ErrorCollector::TYPE,
            "Key in map fields cannot be enum types.");
        break;
      case FieldDescriptor::TYPE_FLOAT:
      case FieldDescriptor::TYPE_DOUBLE:
      case FieldDescriptor::TYPE_MESSAGE:
      case FieldDescriptor::TYPE_GROUP:
      case FieldDescriptor::TYPE_BYTES:
        AddError(
            field->full_name(), proto, DescriptorPool::ErrorCollector::TYPE,
            "Key in map fields cannot be float/double, bytes or message types.");
        break;
      case FieldDescriptor::TYPE_BOOL:
      case FieldDescriptor::TYPE_INT32:
      case FieldDescriptor::TYPE_INT64:
      case FieldDescriptor::TYPE_SINT32:
      case FieldDescriptor::TYPE_SINT64:
      case FieldDescriptor::TYPE_STRING:
      case FieldDescriptor::TYPE_UINT32:
      case FieldDescriptor::TYPE_UINT64:
      case FieldDescriptor::TYPE_FIXED32:
      case FieldDescriptor::TYPE_FIXED64:
      case FieldDescriptor::TYPE_SFIXED32:
      case FieldDescriptor::TYPE_SFIXED64:
        // Legal cases
        break;
      // Do not add a default, so that the compiler will complain when new types
      // are added.
    }
  
    if (value->type() == FieldDescriptor::TYPE_ENUM) {
      if (value->enum_type()->value(0)->number() != 0) {
        AddError(
            field->full_name(), proto, DescriptorPool::ErrorCollector::TYPE,
            "Enum value in map must define 0 as the first value.");
      }
    }
  
    return true;
  }
  
  void DescriptorBuilder::DetectMapConflicts(const Descriptor* message,
                                             const DescriptorProto& proto) {
    map<string, const Descriptor*> seen_types;
    for (int i = 0; i < message->nested_type_count(); ++i) {
      const Descriptor* nested = message->nested_type(i);
      pair<map<string, const Descriptor*>::iterator, bool> result =
          seen_types.insert(std::make_pair(nested->name(), nested));
      if (!result.second) {
        if (result.first->second->options().map_entry() ||
            nested->options().map_entry()) {
          AddError(message->full_name(), proto,
                   DescriptorPool::ErrorCollector::NAME,
                   "Expanded map entry type " + nested->name() +
                   " conflicts with an existing nested message type.");
        }
      }
      // Recursively test on the nested types.
      DetectMapConflicts(message->nested_type(i), proto.nested_type(i));
    }
    // Check for conflicted field names.
    for (int i = 0; i < message->field_count(); ++i) {
      const FieldDescriptor* field = message->field(i);
      map<string, const Descriptor*>::iterator iter =
          seen_types.find(field->name());
      if (iter != seen_types.end() && iter->second->options().map_entry()) {
        AddError(message->full_name(), proto,
                 DescriptorPool::ErrorCollector::NAME,
                 "Expanded map entry type " + iter->second->name() +
                 " conflicts with an existing field.");
      }
    }
    // Check for conflicted enum names.
    for (int i = 0; i < message->enum_type_count(); ++i) {
      const EnumDescriptor* enum_desc = message->enum_type(i);
      map<string, const Descriptor*>::iterator iter =
          seen_types.find(enum_desc->name());
      if (iter != seen_types.end() && iter->second->options().map_entry()) {
        AddError(message->full_name(), proto,
                 DescriptorPool::ErrorCollector::NAME,
                 "Expanded map entry type " + iter->second->name() +
                 " conflicts with an existing enum type.");
      }
    }
    // Check for conflicted oneof names.
    for (int i = 0; i < message->oneof_decl_count(); ++i) {
      const OneofDescriptor* oneof_desc = message->oneof_decl(i);
      map<string, const Descriptor*>::iterator iter =
          seen_types.find(oneof_desc->name());
      if (iter != seen_types.end() && iter->second->options().map_entry()) {
        AddError(message->full_name(), proto,
                 DescriptorPool::ErrorCollector::NAME,
                 "Expanded map entry type " + iter->second->name() +
                 " conflicts with an existing oneof type.");
      }
    }
  }
  
  
  #undef VALIDATE_OPTIONS_FROM_ARRAY
  
  // -------------------------------------------------------------------
  
  DescriptorBuilder::OptionInterpreter::OptionInterpreter(
      DescriptorBuilder* builder) : builder_(builder) {
    GOOGLE_CHECK(builder_);
  }
  
  DescriptorBuilder::OptionInterpreter::~OptionInterpreter() {
  }
  
  bool DescriptorBuilder::OptionInterpreter::InterpretOptions(
      OptionsToInterpret* options_to_interpret) {
    // Note that these may be in different pools, so we can't use the same
    // descriptor and reflection objects on both.
    Message* options = options_to_interpret->options;
    const Message* original_options = options_to_interpret->original_options;
  
    bool failed = false;
    options_to_interpret_ = options_to_interpret;
  
    // Find the uninterpreted_option field in the mutable copy of the options
    // and clear them, since we're about to interpret them.
    const FieldDescriptor* uninterpreted_options_field =
        options->GetDescriptor()->FindFieldByName("uninterpreted_option");
    GOOGLE_CHECK(uninterpreted_options_field != NULL)
        << "No field named \"uninterpreted_option\" in the Options proto.";
    options->GetReflection()->ClearField(options, uninterpreted_options_field);
  
    // Find the uninterpreted_option field in the original options.
    const FieldDescriptor* original_uninterpreted_options_field =
        original_options->GetDescriptor()->
            FindFieldByName("uninterpreted_option");
    GOOGLE_CHECK(original_uninterpreted_options_field != NULL)
        << "No field named \"uninterpreted_option\" in the Options proto.";
  
    const int num_uninterpreted_options = original_options->GetReflection()->
        FieldSize(*original_options, original_uninterpreted_options_field);
    for (int i = 0; i < num_uninterpreted_options; ++i) {
      uninterpreted_option_ = down_cast<const UninterpretedOption*>(
          &original_options->GetReflection()->GetRepeatedMessage(
              *original_options, original_uninterpreted_options_field, i));
      if (!InterpretSingleOption(options)) {
        // Error already added by InterpretSingleOption().
        failed = true;
        break;
      }
    }
    // Reset these, so we don't have any dangling pointers.
    uninterpreted_option_ = NULL;
    options_to_interpret_ = NULL;
  
    if (!failed) {
      // InterpretSingleOption() added the interpreted options in the
      // UnknownFieldSet, in case the option isn't yet known to us.  Now we
      // serialize the options message and deserialize it back.  That way, any
      // option fields that we do happen to know about will get moved from the
      // UnknownFieldSet into the real fields, and thus be available right away.
      // If they are not known, that's OK too. They will get reparsed into the
      // UnknownFieldSet and wait there until the message is parsed by something
      // that does know about the options.
      string buf;
      GOOGLE_CHECK(options->AppendPartialToString(&buf))
          << "Protocol message could not be serialized.";
      GOOGLE_CHECK(options->ParsePartialFromString(buf))
          << "Protocol message serialized itself in invalid fashion.";
      if (!options->IsInitialized()) {
        builder_->AddWarning(
            options_to_interpret->element_name, *original_options,
            DescriptorPool::ErrorCollector::OTHER,
            "Options could not be fully parsed using the proto descriptors "
            "compiled into this binary. Missing required fields: " +
            options->InitializationErrorString());
      }
    }
    return !failed;
  }
  
  bool DescriptorBuilder::OptionInterpreter::InterpretSingleOption(
      Message* options) {
    // First do some basic validation.
    if (uninterpreted_option_->name_size() == 0) {
      // This should never happen unless the parser has gone seriously awry or
      // someone has manually created the uninterpreted option badly.
      return AddNameError("Option must have a name.");
    }
    if (uninterpreted_option_->name(0).name_part() == "uninterpreted_option") {
      return AddNameError("Option must not use reserved name "
                          "\"uninterpreted_option\".");
    }
  
    const Descriptor* options_descriptor = NULL;
    // Get the options message's descriptor from the builder's pool, so that we
    // get the version that knows about any extension options declared in the
    // file we're currently building. The descriptor should be there as long as
    // the file we're building imported "google/protobuf/descriptors.proto".
  
    // Note that we use DescriptorBuilder::FindSymbolNotEnforcingDeps(), not
    // DescriptorPool::FindMessageTypeByName() because we're already holding the
    // pool's mutex, and the latter method locks it again.  We don't use
    // FindSymbol() because files that use custom options only need to depend on
    // the file that defines the option, not descriptor.proto itself.
    Symbol symbol = builder_->FindSymbolNotEnforcingDeps(
      options->GetDescriptor()->full_name());
    if (!symbol.IsNull() && symbol.type == Symbol::MESSAGE) {
      options_descriptor = symbol.descriptor;
    } else {
      // The options message's descriptor was not in the builder's pool, so use
      // the standard version from the generated pool. We're not holding the
      // generated pool's mutex, so we can search it the straightforward way.
      options_descriptor = options->GetDescriptor();
    }
    GOOGLE_CHECK(options_descriptor);
  
    // We iterate over the name parts to drill into the submessages until we find
    // the leaf field for the option. As we drill down we remember the current
    // submessage's descriptor in |descriptor| and the next field in that
    // submessage in |field|. We also track the fields we're drilling down
    // through in |intermediate_fields|. As we go, we reconstruct the full option
    // name in |debug_msg_name|, for use in error messages.
    const Descriptor* descriptor = options_descriptor;
    const FieldDescriptor* field = NULL;
    vector<const FieldDescriptor*> intermediate_fields;
    string debug_msg_name = "";
  
    for (int i = 0; i < uninterpreted_option_->name_size(); ++i) {
      const string& name_part = uninterpreted_option_->name(i).name_part();
      if (debug_msg_name.size() > 0) {
        debug_msg_name += ".";
      }
      if (uninterpreted_option_->name(i).is_extension()) {
        debug_msg_name += "(" + name_part + ")";
        // Search for the extension's descriptor as an extension in the builder's
        // pool. Note that we use DescriptorBuilder::LookupSymbol(), not
        // DescriptorPool::FindExtensionByName(), for two reasons: 1) It allows
        // relative lookups, and 2) because we're already holding the pool's
        // mutex, and the latter method locks it again.
        symbol = builder_->LookupSymbol(name_part,
                                        options_to_interpret_->name_scope);
        if (!symbol.IsNull() && symbol.type == Symbol::FIELD) {
          field = symbol.field_descriptor;
        }
        // If we don't find the field then the field's descriptor was not in the
        // builder's pool, but there's no point in looking in the generated
        // pool. We require that you import the file that defines any extensions
        // you use, so they must be present in the builder's pool.
      } else {
        debug_msg_name += name_part;
        // Search for the field's descriptor as a regular field.
        field = descriptor->FindFieldByName(name_part);
      }
  
      if (field == NULL) {
        if (get_allow_unknown(builder_->pool_)) {
          // We can't find the option, but AllowUnknownDependencies() is enabled,
          // so we will just leave it as uninterpreted.
          AddWithoutInterpreting(*uninterpreted_option_, options);
          return true;
        } else if (!(builder_->undefine_resolved_name_).empty()) {
          // Option is resolved to a name which is not defined.
          return AddNameError(
              "Option \"" + debug_msg_name + "\" is resolved to \"(" +
              builder_->undefine_resolved_name_ +
              ")\", which is not defined. The innermost scope is searched first "
              "in name resolution. Consider using a leading '.'(i.e., \"(." +
              debug_msg_name.substr(1) +
              "\") to start from the outermost scope.");
        } else {
          return AddNameError("Option \"" + debug_msg_name + "\" unknown.");
        }
      } else if (field->containing_type() != descriptor) {
        if (get_is_placeholder(field->containing_type())) {
          // The field is an extension of a placeholder type, so we can't
          // reliably verify whether it is a valid extension to use here (e.g.
          // we don't know if it is an extension of the correct *Options message,
          // or if it has a valid field number, etc.).  Just leave it as
          // uninterpreted instead.
          AddWithoutInterpreting(*uninterpreted_option_, options);
          return true;
        } else {
          // This can only happen if, due to some insane misconfiguration of the
          // pools, we find the options message in one pool but the field in
          // another. This would probably imply a hefty bug somewhere.
          return AddNameError("Option field \"" + debug_msg_name +
                              "\" is not a field or extension of message \"" +
                              descriptor->name() + "\".");
        }
      } else if (i < uninterpreted_option_->name_size() - 1) {
        if (field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) {
          return AddNameError("Option \"" +  debug_msg_name +
                              "\" is an atomic type, not a message.");
        } else if (field->is_repeated()) {
          return AddNameError("Option field \"" + debug_msg_name +
                              "\" is a repeated message. Repeated message "
                              "options must be initialized using an "
                              "aggregate value.");
        } else {
          // Drill down into the submessage.
          intermediate_fields.push_back(field);
          descriptor = field->message_type();
        }
      }
    }
  
    // We've found the leaf field. Now we use UnknownFieldSets to set its value
    // on the options message. We do so because the message may not yet know
    // about its extension fields, so we may not be able to set the fields
    // directly. But the UnknownFieldSets will serialize to the same wire-format
    // message, so reading that message back in once the extension fields are
    // known will populate them correctly.
  
    // First see if the option is already set.
    if (!field->is_repeated() && !ExamineIfOptionIsSet(
            intermediate_fields.begin(),
            intermediate_fields.end(),
            field, debug_msg_name,
            options->GetReflection()->GetUnknownFields(*options))) {
      return false;  // ExamineIfOptionIsSet() already added the error.
    }
  
  
    // First set the value on the UnknownFieldSet corresponding to the
    // innermost message.
    google::protobuf::scoped_ptr<UnknownFieldSet> unknown_fields(new UnknownFieldSet());
    if (!SetOptionValue(field, unknown_fields.get())) {
      return false;  // SetOptionValue() already added the error.
    }
  
    // Now wrap the UnknownFieldSet with UnknownFieldSets corresponding to all
    // the intermediate messages.
    for (vector<const FieldDescriptor*>::reverse_iterator iter =
             intermediate_fields.rbegin();
         iter != intermediate_fields.rend(); ++iter) {
      google::protobuf::scoped_ptr<UnknownFieldSet> parent_unknown_fields(
          new UnknownFieldSet());
      switch ((*iter)->type()) {
        case FieldDescriptor::TYPE_MESSAGE: {
          io::StringOutputStream outstr(
              parent_unknown_fields->AddLengthDelimited((*iter)->number()));
          io::CodedOutputStream out(&outstr);
          internal::WireFormat::SerializeUnknownFields(*unknown_fields, &out);
          GOOGLE_CHECK(!out.HadError())
              << "Unexpected failure while serializing option submessage "
              << debug_msg_name << "\".";
          break;
        }
  
        case FieldDescriptor::TYPE_GROUP: {
           parent_unknown_fields->AddGroup((*iter)->number())
                                ->MergeFrom(*unknown_fields);
          break;
        }
  
        default:
          GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_MESSAGE: "
                     << (*iter)->type();
          return false;
      }
      unknown_fields.reset(parent_unknown_fields.release());
    }
  
    // Now merge the UnknownFieldSet corresponding to the top-level message into
    // the options message.
    options->GetReflection()->MutableUnknownFields(options)->MergeFrom(
        *unknown_fields);
  
    return true;
  }
  
  void DescriptorBuilder::OptionInterpreter::AddWithoutInterpreting(
      const UninterpretedOption& uninterpreted_option, Message* options) {
    const FieldDescriptor* field =
      options->GetDescriptor()->FindFieldByName("uninterpreted_option");
    GOOGLE_CHECK(field != NULL);
  
    options->GetReflection()->AddMessage(options, field)
      ->CopyFrom(uninterpreted_option);
  }
  
  bool DescriptorBuilder::OptionInterpreter::ExamineIfOptionIsSet(
      vector<const FieldDescriptor*>::const_iterator intermediate_fields_iter,
      vector<const FieldDescriptor*>::const_iterator intermediate_fields_end,
      const FieldDescriptor* innermost_field, const string& debug_msg_name,
      const UnknownFieldSet& unknown_fields) {
    // We do linear searches of the UnknownFieldSet and its sub-groups.  This
    // should be fine since it's unlikely that any one options structure will
    // contain more than a handful of options.
  
    if (intermediate_fields_iter == intermediate_fields_end) {
      // We're at the innermost submessage.
      for (int i = 0; i < unknown_fields.field_count(); i++) {
        if (unknown_fields.field(i).number() == innermost_field->number()) {
          return AddNameError("Option \"" + debug_msg_name +
                              "\" was already set.");
        }
      }
      return true;
    }
  
    for (int i = 0; i < unknown_fields.field_count(); i++) {
      if (unknown_fields.field(i).number() ==
          (*intermediate_fields_iter)->number()) {
        const UnknownField* unknown_field = &unknown_fields.field(i);
        FieldDescriptor::Type type = (*intermediate_fields_iter)->type();
        // Recurse into the next submessage.
        switch (type) {
          case FieldDescriptor::TYPE_MESSAGE:
            if (unknown_field->type() == UnknownField::TYPE_LENGTH_DELIMITED) {
              UnknownFieldSet intermediate_unknown_fields;
              if (intermediate_unknown_fields.ParseFromString(
                      unknown_field->length_delimited()) &&
                  !ExamineIfOptionIsSet(intermediate_fields_iter + 1,
                                        intermediate_fields_end,
                                        innermost_field, debug_msg_name,
                                        intermediate_unknown_fields)) {
                return false;  // Error already added.
              }
            }
            break;
  
          case FieldDescriptor::TYPE_GROUP:
            if (unknown_field->type() == UnknownField::TYPE_GROUP) {
              if (!ExamineIfOptionIsSet(intermediate_fields_iter + 1,
                                        intermediate_fields_end,
                                        innermost_field, debug_msg_name,
                                        unknown_field->group())) {
                return false;  // Error already added.
              }
            }
            break;
  
          default:
            GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_MESSAGE: " << type;
            return false;
        }
      }
    }
    return true;
  }
  
  bool DescriptorBuilder::OptionInterpreter::SetOptionValue(
      const FieldDescriptor* option_field,
      UnknownFieldSet* unknown_fields) {
    // We switch on the CppType to validate.
    switch (option_field->cpp_type()) {
  
      case FieldDescriptor::CPPTYPE_INT32:
        if (uninterpreted_option_->has_positive_int_value()) {
          if (uninterpreted_option_->positive_int_value() >
              static_cast<uint64>(kint32max)) {
            return AddValueError("Value out of range for int32 option \"" +
                                 option_field->full_name() + "\".");
          } else {
            SetInt32(option_field->number(),
                     uninterpreted_option_->positive_int_value(),
                     option_field->type(), unknown_fields);
          }
        } else if (uninterpreted_option_->has_negative_int_value()) {
          if (uninterpreted_option_->negative_int_value() <
              static_cast<int64>(kint32min)) {
            return AddValueError("Value out of range for int32 option \"" +
                                 option_field->full_name() + "\".");
          } else {
            SetInt32(option_field->number(),
                     uninterpreted_option_->negative_int_value(),
                     option_field->type(), unknown_fields);
          }
        } else {
          return AddValueError("Value must be integer for int32 option \"" +
                               option_field->full_name() + "\".");
        }
        break;
  
      case FieldDescriptor::CPPTYPE_INT64:
        if (uninterpreted_option_->has_positive_int_value()) {
          if (uninterpreted_option_->positive_int_value() >
              static_cast<uint64>(kint64max)) {
            return AddValueError("Value out of range for int64 option \"" +
                                 option_field->full_name() + "\".");
          } else {
            SetInt64(option_field->number(),
                     uninterpreted_option_->positive_int_value(),
                     option_field->type(), unknown_fields);
          }
        } else if (uninterpreted_option_->has_negative_int_value()) {
          SetInt64(option_field->number(),
                   uninterpreted_option_->negative_int_value(),
                   option_field->type(), unknown_fields);
        } else {
          return AddValueError("Value must be integer for int64 option \"" +
                               option_field->full_name() + "\".");
        }
        break;
  
      case FieldDescriptor::CPPTYPE_UINT32:
        if (uninterpreted_option_->has_positive_int_value()) {
          if (uninterpreted_option_->positive_int_value() > kuint32max) {
            return AddValueError("Value out of range for uint32 option \"" +
                                 option_field->name() + "\".");
          } else {
            SetUInt32(option_field->number(),
                      uninterpreted_option_->positive_int_value(),
                      option_field->type(), unknown_fields);
          }
        } else {
          return AddValueError("Value must be non-negative integer for uint32 "
                               "option \"" + option_field->full_name() + "\".");
        }
        break;
  
      case FieldDescriptor::CPPTYPE_UINT64:
        if (uninterpreted_option_->has_positive_int_value()) {
          SetUInt64(option_field->number(),
                    uninterpreted_option_->positive_int_value(),
                    option_field->type(), unknown_fields);
        } else {
          return AddValueError("Value must be non-negative integer for uint64 "
                               "option \"" + option_field->full_name() + "\".");
        }
        break;
  
      case FieldDescriptor::CPPTYPE_FLOAT: {
        float value;
        if (uninterpreted_option_->has_double_value()) {
          value = uninterpreted_option_->double_value();
        } else if (uninterpreted_option_->has_positive_int_value()) {
          value = uninterpreted_option_->positive_int_value();
        } else if (uninterpreted_option_->has_negative_int_value()) {
          value = uninterpreted_option_->negative_int_value();
        } else {
          return AddValueError("Value must be number for float option \"" +
                               option_field->full_name() + "\".");
        }
        unknown_fields->AddFixed32(option_field->number(),
            google::protobuf::internal::WireFormatLite::EncodeFloat(value));
        break;
      }
  
      case FieldDescriptor::CPPTYPE_DOUBLE: {
        double value;
        if (uninterpreted_option_->has_double_value()) {
          value = uninterpreted_option_->double_value();
        } else if (uninterpreted_option_->has_positive_int_value()) {
          value = uninterpreted_option_->positive_int_value();
        } else if (uninterpreted_option_->has_negative_int_value()) {
          value = uninterpreted_option_->negative_int_value();
        } else {
          return AddValueError("Value must be number for double option \"" +
                               option_field->full_name() + "\".");
        }
        unknown_fields->AddFixed64(option_field->number(),
            google::protobuf::internal::WireFormatLite::EncodeDouble(value));
        break;
      }
  
      case FieldDescriptor::CPPTYPE_BOOL:
        uint64 value;
        if (!uninterpreted_option_->has_identifier_value()) {
          return AddValueError("Value must be identifier for boolean option "
                               "\"" + option_field->full_name() + "\".");
        }
        if (uninterpreted_option_->identifier_value() == "true") {
          value = 1;
        } else if (uninterpreted_option_->identifier_value() == "false") {
          value = 0;
        } else {
          return AddValueError("Value must be \"true\" or \"false\" for boolean "
                               "option \"" + option_field->full_name() + "\".");
        }
        unknown_fields->AddVarint(option_field->number(), value);
        break;
  
      case FieldDescriptor::CPPTYPE_ENUM: {
        if (!uninterpreted_option_->has_identifier_value()) {
          return AddValueError("Value must be identifier for enum-valued option "
                               "\"" + option_field->full_name() + "\".");
        }
        const EnumDescriptor* enum_type = option_field->enum_type();
        const string& value_name = uninterpreted_option_->identifier_value();
        const EnumValueDescriptor* enum_value = NULL;
  
        if (enum_type->file()->pool() != DescriptorPool::generated_pool()) {
          // Note that the enum value's fully-qualified name is a sibling of the
          // enum's name, not a child of it.
          string fully_qualified_name = enum_type->full_name();
          fully_qualified_name.resize(fully_qualified_name.size() -
                                      enum_type->name().size());
          fully_qualified_name += value_name;
  
          // Search for the enum value's descriptor in the builder's pool. Note
          // that we use DescriptorBuilder::FindSymbolNotEnforcingDeps(), not
          // DescriptorPool::FindEnumValueByName() because we're already holding
          // the pool's mutex, and the latter method locks it again.
          Symbol symbol =
            builder_->FindSymbolNotEnforcingDeps(fully_qualified_name);
          if (!symbol.IsNull() && symbol.type == Symbol::ENUM_VALUE) {
            if (symbol.enum_value_descriptor->type() != enum_type) {
              return AddValueError("Enum type \"" + enum_type->full_name() +
                  "\" has no value named \"" + value_name + "\" for option \"" +
                  option_field->full_name() +
                  "\". This appears to be a value from a sibling type.");
            } else {
              enum_value = symbol.enum_value_descriptor;
            }
          }
        } else {
          // The enum type is in the generated pool, so we can search for the
          // value there.
          enum_value = enum_type->FindValueByName(value_name);
        }
  
        if (enum_value == NULL) {
          return AddValueError("Enum type \"" +
                               option_field->enum_type()->full_name() +
                               "\" has no value named \"" + value_name + "\" for "
                               "option \"" + option_field->full_name() + "\".");
        } else {
          // Sign-extension is not a problem, since we cast directly from int32 to
          // uint64, without first going through uint32.
          unknown_fields->AddVarint(option_field->number(),
            static_cast<uint64>(static_cast<int64>(enum_value->number())));
        }
        break;
      }
  
      case FieldDescriptor::CPPTYPE_STRING:
        if (!uninterpreted_option_->has_string_value()) {
          return AddValueError("Value must be quoted string for string option "
                               "\"" + option_field->full_name() + "\".");
        }
        // The string has already been unquoted and unescaped by the parser.
        unknown_fields->AddLengthDelimited(option_field->number(),
            uninterpreted_option_->string_value());
        break;
  
      case FieldDescriptor::CPPTYPE_MESSAGE:
        if (!SetAggregateOption(option_field, unknown_fields)) {
          return false;
        }
        break;
    }
  
    return true;
  }
  
  class DescriptorBuilder::OptionInterpreter::AggregateOptionFinder
      : public TextFormat::Finder {
   public:
    DescriptorBuilder* builder_;
  
    virtual const FieldDescriptor* FindExtension(
        Message* message, const string& name) const {
      assert_mutex_held(builder_->pool_);
      const Descriptor* descriptor = message->GetDescriptor();
      Symbol result = builder_->LookupSymbolNoPlaceholder(
          name, descriptor->full_name());
      if (result.type == Symbol::FIELD &&
          result.field_descriptor->is_extension()) {
        return result.field_descriptor;
      } else if (result.type == Symbol::MESSAGE &&
                 descriptor->options().message_set_wire_format()) {
        const Descriptor* foreign_type = result.descriptor;
        // The text format allows MessageSet items to be specified using
        // the type name, rather than the extension identifier. If the symbol
        // lookup returned a Message, and the enclosing Message has
        // message_set_wire_format = true, then return the message set
        // extension, if one exists.
        for (int i = 0; i < foreign_type->extension_count(); i++) {
          const FieldDescriptor* extension = foreign_type->extension(i);
          if (extension->containing_type() == descriptor &&
              extension->type() == FieldDescriptor::TYPE_MESSAGE &&
              extension->is_optional() &&
              extension->message_type() == foreign_type) {
            // Found it.
            return extension;
          }
        }
      }
      return NULL;
    }
  };
  
  // A custom error collector to record any text-format parsing errors
  namespace {
  class AggregateErrorCollector : public io::ErrorCollector {
   public:
    string error_;
  
    virtual void AddError(int /* line */, int /* column */,
                          const string& message) {
      if (!error_.empty()) {
        error_ += "; ";
      }
      error_ += message;
    }
  
    virtual void AddWarning(int /* line */, int /* column */,
                            const string& /* message */) {
      // Ignore warnings
    }
  };
  }
  
  // We construct a dynamic message of the type corresponding to
  // option_field, parse the supplied text-format string into this
  // message, and serialize the resulting message to produce the value.
  bool DescriptorBuilder::OptionInterpreter::SetAggregateOption(
      const FieldDescriptor* option_field,
      UnknownFieldSet* unknown_fields) {
    if (!uninterpreted_option_->has_aggregate_value()) {
      return AddValueError("Option \"" + option_field->full_name() +
                           "\" is a message. To set the entire message, use "
                           "syntax like \"" + option_field->name() +
                           " = { <proto text format> }\". "
                           "To set fields within it, use "
                           "syntax like \"" + option_field->name() +
                           ".foo = value\".");
    }
  
    const Descriptor* type = option_field->message_type();
    google::protobuf::scoped_ptr<Message> dynamic(dynamic_factory_.GetPrototype(type)->New());
    GOOGLE_CHECK(dynamic.get() != NULL)
        << "Could not create an instance of " << option_field->DebugString();
  
    AggregateErrorCollector collector;
    AggregateOptionFinder finder;
    finder.builder_ = builder_;
    TextFormat::Parser parser;
    parser.RecordErrorsTo(&collector);
    parser.SetFinder(&finder);
    if (!parser.ParseFromString(uninterpreted_option_->aggregate_value(),
                                dynamic.get())) {
      AddValueError("Error while parsing option value for \"" +
                    option_field->name() + "\": " + collector.error_);
      return false;
    } else {
      string serial;
      dynamic->SerializeToString(&serial);  // Never fails
      if (option_field->type() == FieldDescriptor::TYPE_MESSAGE) {
        unknown_fields->AddLengthDelimited(option_field->number(), serial);
      } else {
        GOOGLE_CHECK_EQ(option_field->type(),  FieldDescriptor::TYPE_GROUP);
        UnknownFieldSet* group = unknown_fields->AddGroup(option_field->number());
        group->ParseFromString(serial);
      }
      return true;
    }
  }
  
  void DescriptorBuilder::OptionInterpreter::SetInt32(int number, int32 value,
      FieldDescriptor::Type type, UnknownFieldSet* unknown_fields) {
    switch (type) {
      case FieldDescriptor::TYPE_INT32:
        unknown_fields->AddVarint(number,
          static_cast<uint64>(static_cast<int64>(value)));
        break;
  
      case FieldDescriptor::TYPE_SFIXED32:
        unknown_fields->AddFixed32(number, static_cast<uint32>(value));
        break;
  
      case FieldDescriptor::TYPE_SINT32:
        unknown_fields->AddVarint(number,
            google::protobuf::internal::WireFormatLite::ZigZagEncode32(value));
        break;
  
      default:
        GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_INT32: " << type;
        break;
    }
  }
  
  void DescriptorBuilder::OptionInterpreter::SetInt64(int number, int64 value,
      FieldDescriptor::Type type, UnknownFieldSet* unknown_fields) {
    switch (type) {
      case FieldDescriptor::TYPE_INT64:
        unknown_fields->AddVarint(number, static_cast<uint64>(value));
        break;
  
      case FieldDescriptor::TYPE_SFIXED64:
        unknown_fields->AddFixed64(number, static_cast<uint64>(value));
        break;
  
      case FieldDescriptor::TYPE_SINT64:
        unknown_fields->AddVarint(number,
            google::protobuf::internal::WireFormatLite::ZigZagEncode64(value));
        break;
  
      default:
        GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_INT64: " << type;
        break;
    }
  }
  
  void DescriptorBuilder::OptionInterpreter::SetUInt32(int number, uint32 value,
      FieldDescriptor::Type type, UnknownFieldSet* unknown_fields) {
    switch (type) {
      case FieldDescriptor::TYPE_UINT32:
        unknown_fields->AddVarint(number, static_cast<uint64>(value));
        break;
  
      case FieldDescriptor::TYPE_FIXED32:
        unknown_fields->AddFixed32(number, static_cast<uint32>(value));
        break;
  
      default:
        GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_UINT32: " << type;
        break;
    }
  }
  
  void DescriptorBuilder::OptionInterpreter::SetUInt64(int number, uint64 value,
      FieldDescriptor::Type type, UnknownFieldSet* unknown_fields) {
    switch (type) {
      case FieldDescriptor::TYPE_UINT64:
        unknown_fields->AddVarint(number, value);
        break;
  
      case FieldDescriptor::TYPE_FIXED64:
        unknown_fields->AddFixed64(number, value);
        break;
  
      default:
        GOOGLE_LOG(FATAL) << "Invalid wire type for CPPTYPE_UINT64: " << type;
        break;
    }
  }
  
  void DescriptorBuilder::LogUnusedDependency(const FileDescriptorProto& proto,
                                              const FileDescriptor* result) {
  
    if (!unused_dependency_.empty()) {
      std::set<string> annotation_extensions;
      annotation_extensions.insert("google.protobuf.MessageOptions");
      annotation_extensions.insert("google.protobuf.FileOptions");
      annotation_extensions.insert("google.protobuf.FieldOptions");
      annotation_extensions.insert("google.protobuf.EnumOptions");
      annotation_extensions.insert("google.protobuf.EnumValueOptions");
      annotation_extensions.insert("google.protobuf.ServiceOptions");
      annotation_extensions.insert("google.protobuf.MethodOptions");
      annotation_extensions.insert("google.protobuf.StreamOptions");
      for (set<const FileDescriptor*>::const_iterator
               it = unused_dependency_.begin();
           it != unused_dependency_.end(); ++it) {
        // Do not log warnings for proto files which extend annotations.
        int i;
        for (i = 0 ; i < (*it)->extension_count(); ++i) {
          if (annotation_extensions.find(
                  (*it)->extension(i)->containing_type()->full_name())
              != annotation_extensions.end()) {
            break;
          }
        }
        // Log warnings for unused imported files.
        if (i == (*it)->extension_count()) {
          string error_message = "Import " + (*it)->name() + " but not used.";
          AddWarning((*it)->name(), proto, DescriptorPool::ErrorCollector::OTHER,
                     error_message);
        }
      }
    }
  }
  
  }  // namespace protobuf
  }  // namespace google
  