Update protobuf to r428, part 1.

third_party/protobuf/src/google/protobuf/descriptor.cc

Index: third_party/protobuf/src/google/protobuf/descriptor.cc
===================================================================
--- third_party/protobuf/src/google/protobuf/descriptor.cc	(revision 216642)
+++ third_party/protobuf/src/google/protobuf/descriptor.cc	(working copy)
@@ -54,7 +54,7 @@
 #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-inl.h>
+#include <google/protobuf/stubs/stl_util.h>
 
 #undef PACKAGE  // autoheader #defines this.  :(
 
@@ -108,6 +108,21 @@
   "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
 
@@ -221,7 +236,8 @@
 
 struct Symbol {
   enum Type {
-    NULL_SYMBOL, MESSAGE, FIELD, ENUM, ENUM_VALUE, SERVICE, METHOD, PACKAGE
+    NULL_SYMBOL, MESSAGE, FIELD, ENUM, ENUM_VALUE, SERVICE, METHOD,
+    PACKAGE
   };
   Type type;
   union {
@@ -311,18 +327,43 @@
   Tables();
   ~Tables();
 
-  // Checkpoint the state of the tables.  Future calls to Rollback() will
-  // return the Tables to this state.  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.  BuildFile() calls
-  // Checkpoint() before it starts building and Rollback() if it encounters
-  // an error.
-  void Checkpoint();
+  // 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();
 
-  // Roll back the Tables to the state of the last Checkpoint(), removing
-  // everything that was added after that point.
-  void Rollback();
+  // 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.
@@ -405,10 +446,28 @@
   FilesByNameMap        files_by_name_;
   ExtensionsGroupedByDescriptorMap extensions_;
 
-  int strings_before_checkpoint_;
-  int messages_before_checkpoint_;
-  int file_tables_before_checkpoint_;
-  int allocations_before_checkpoint_;
+  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_;
@@ -481,11 +540,15 @@
 };
 
 DescriptorPool::Tables::Tables()
-  : strings_before_checkpoint_(0),
-    messages_before_checkpoint_(0),
-    allocations_before_checkpoint_(0) {}
+    // Start some hash_map and hash_set objects with a small # of buckets
+    : known_bad_files_(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_);
@@ -496,51 +559,80 @@
   STLDeleteElements(&file_tables_);
 }
 
-FileDescriptorTables::FileDescriptorTables() {}
+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) {
+}
+
 FileDescriptorTables::~FileDescriptorTables() {}
 
 const FileDescriptorTables FileDescriptorTables::kEmpty;
 
-void DescriptorPool::Tables::Checkpoint() {
-  strings_before_checkpoint_ = strings_.size();
-  messages_before_checkpoint_ = messages_.size();
-  file_tables_before_checkpoint_ = file_tables_.size();
-  allocations_before_checkpoint_ = allocations_.size();
+void DescriptorPool::Tables::AddCheckpoint() {
+  checkpoints_.push_back(CheckPoint(this));
+}
 
-  symbols_after_checkpoint_.clear();
-  files_after_checkpoint_.clear();
-  extensions_after_checkpoint_.clear();
+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::Rollback() {
-  for (int i = 0; i < symbols_after_checkpoint_.size(); i++) {
+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 = 0; i < files_after_checkpoint_.size(); 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 = 0; i < extensions_after_checkpoint_.size(); i++) {
+  for (int i = checkpoint.pending_extensions_before_checkpoint;
+       i < extensions_after_checkpoint_.size();
+       i++) {
     extensions_.erase(extensions_after_checkpoint_[i]);
   }
 
-  symbols_after_checkpoint_.clear();
-  files_after_checkpoint_.clear();
-  extensions_after_checkpoint_.clear();
+  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() + strings_before_checkpoint_, strings_.end());
+      strings_.begin() + checkpoint.strings_before_checkpoint, strings_.end());
   STLDeleteContainerPointers(
-    messages_.begin() + messages_before_checkpoint_, messages_.end());
+      messages_.begin() + checkpoint.messages_before_checkpoint,
+      messages_.end());
   STLDeleteContainerPointers(
-    file_tables_.begin() + file_tables_before_checkpoint_, file_tables_.end());
-  for (int i = allocations_before_checkpoint_; i < allocations_.size(); i++) {
+      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(strings_before_checkpoint_);
-  messages_.resize(messages_before_checkpoint_);
-  file_tables_.resize(file_tables_before_checkpoint_);
-  allocations_.resize(allocations_before_checkpoint_);
+  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();
 }
 
 // -------------------------------------------------------------------
@@ -811,7 +903,7 @@
   generated_pool_ = NULL;
 }
 
-void InitGeneratedPool() {
+static void InitGeneratedPool() {
   generated_database_ = new EncodedDescriptorDatabase;
   generated_pool_ = new DescriptorPool(generated_database_);
 
@@ -874,11 +966,11 @@
   const FileDescriptor* result = tables_->FindFile(name);
   if (result != NULL) return result;
   if (underlay_ != NULL) {
-    const FileDescriptor* result = underlay_->FindFileByName(name);
+    result = underlay_->FindFileByName(name);
     if (result != NULL) return result;
   }
   if (TryFindFileInFallbackDatabase(name)) {
-    const FileDescriptor* result = tables_->FindFile(name);
+    result = tables_->FindFile(name);
     if (result != NULL) return result;
   }
   return NULL;
@@ -890,12 +982,12 @@
   Symbol result = tables_->FindSymbol(symbol_name);
   if (!result.IsNull()) return result.GetFile();
   if (underlay_ != NULL) {
-    const FileDescriptor* result =
+    const FileDescriptor* file_result =
       underlay_->FindFileContainingSymbol(symbol_name);
-    if (result != NULL) return result;
+    if (file_result != NULL) return file_result;
   }
   if (TryFindSymbolInFallbackDatabase(symbol_name)) {
-    Symbol result = tables_->FindSymbol(symbol_name);
+    result = tables_->FindSymbol(symbol_name);
     if (!result.IsNull()) return result.GetFile();
   }
   return NULL;
@@ -962,12 +1054,11 @@
     return result;
   }
   if (underlay_ != NULL) {
-    const FieldDescriptor* result =
-      underlay_->FindExtensionByNumber(extendee, number);
+    result = underlay_->FindExtensionByNumber(extendee, number);
     if (result != NULL) return result;
   }
   if (TryFindExtensionInFallbackDatabase(extendee, number)) {
-    const FieldDescriptor* result = tables_->FindExtension(extendee, number);
+    result = tables_->FindExtension(extendee, number);
     if (result != NULL) {
       return result;
     }
@@ -1241,9 +1332,48 @@
   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;
 
+  // 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.
+  if (IsSubSymbolOfBuiltType(name)) return false;
+
   FileDescriptorProto file_proto;
   if (!fallback_database_->FindFileContainingSymbol(name, &file_proto)) {
     return false;
@@ -1345,6 +1475,14 @@
     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());
   }
@@ -1363,6 +1501,12 @@
   }
 }
 
+void FileDescriptor::CopySourceCodeInfoTo(FileDescriptorProto* proto) const {
+  if (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());
 
@@ -1490,16 +1634,14 @@
 namespace {
 
 // Used by each of the option formatters.
-bool RetrieveOptions(const Message &options, vector<string> *option_entries) {
+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++) {
-    // Doesn't make sense to have message type fields here
-    if (fields[i]->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
-      continue;
-    }
     int count = 1;
     bool repeated = false;
     if (fields[i]->is_repeated()) {
@@ -1508,9 +1650,27 @@
     }
     for (int j = 0; j < count; j++) {
       string fieldval;
-      TextFormat::PrintFieldValueToString(options, fields[i],
-                                          repeated ? count : -1, &fieldval);
-      option_entries->push_back(fields[i]->name() + " = " + 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();
@@ -1518,9 +1678,9 @@
 
 // Formats options that all appear together in brackets. Does not include
 // brackets.
-bool FormatBracketedOptions(const Message &options, string *output) {
+bool FormatBracketedOptions(int depth, const Message &options, string *output) {
   vector<string> all_options;
-  if (RetrieveOptions(options, &all_options)) {
+  if (RetrieveOptions(depth, options, &all_options)) {
     output->append(JoinStrings(all_options, ", "));
   }
   return !all_options.empty();
@@ -1530,7 +1690,7 @@
 bool FormatLineOptions(int depth, const Message &options, string *output) {
   string prefix(depth * 2, ' ');
   vector<string> all_options;
-  if (RetrieveOptions(options, &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]);
@@ -1544,9 +1704,24 @@
 string FileDescriptor::DebugString() const {
   string contents = "syntax = \"proto2\";\n\n";
 
+  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++) {
-    strings::SubstituteAndAppend(&contents, "import \"$0\";\n",
-                                 dependency(i)->name());
+    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()) {
@@ -1712,7 +1887,7 @@
   }
 
   string formatted_options;
-  if (FormatBracketedOptions(options(), &formatted_options)) {
+  if (FormatBracketedOptions(depth, options(), &formatted_options)) {
     contents->append(bracketed ? ", " : " [");
     bracketed = true;
     contents->append(formatted_options);
@@ -1761,7 +1936,7 @@
                                prefix, name(), number());
 
   string formatted_options;
-  if (FormatBracketedOptions(options(), &formatted_options)) {
+  if (FormatBracketedOptions(depth, options(), &formatted_options)) {
     strings::SubstituteAndAppend(contents, " [$0]", formatted_options);
   }
   contents->append(";\n");
@@ -1807,6 +1982,126 @@
     contents->append(";\n");
   }
 }
+
+
+// Location methods ===============================================
+
+static bool PathsEqual(const vector<int>& x, const RepeatedField<int32>& y) {
+  if (x.size() != y.size()) return false;
+  for (int i = 0; i < x.size(); ++i) {
+    if (x[i] != y.Get(i)) return false;
+  }
+  return true;
+}
+
+bool FileDescriptor::GetSourceLocation(const vector<int>& path,
+                                       SourceLocation* out_location) const {
+  GOOGLE_CHECK_NOTNULL(out_location);
+  const SourceCodeInfo* info = source_code_info_;
+  for (int i = 0; info && i < info->location_size(); ++i) {
+    if (PathsEqual(path, info->location(i).path())) {
+      const RepeatedField<int32>& span = info->location(i).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 = info->location(i).leading_comments();
+        out_location->trailing_comments = info->location(i).trailing_comments();
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+bool FieldDescriptor::is_packed() const {
+  return is_packable() && (options_ != NULL) && 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 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 {
+  containing_type()->GetLocationPath(output);
+  output->push_back(DescriptorProto::kFieldFieldNumber);
+  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 {
@@ -1859,6 +2154,7 @@
   string filename_;
   FileDescriptor* file_;
   FileDescriptorTables* file_tables_;
+  set<const FileDescriptor*> dependencies_;
 
   // 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
@@ -1888,6 +2184,10 @@
   // 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
@@ -1898,6 +2198,10 @@
   // 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
@@ -2189,6 +2493,7 @@
 
   void ValidateMapKey(FieldDescriptor* field,
                       const FieldDescriptorProto& proto);
+
 };
 
 const FileDescriptor* DescriptorPool::BuildFile(
@@ -2275,31 +2580,48 @@
             file->package()[package_name.size()] == '.');
 }
 
-Symbol DescriptorBuilder::FindSymbolNotEnforcingDeps(const string& name) {
-  Symbol result;
+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));
+  }
+}
 
-  // We need to search our pool and all its underlays.
-  const DescriptorPool* pool = pool_;
-  while (true) {
-    // If we are looking at an underlay, we must lock its mutex_, since we are
-    // accessing the underlay's tables_ dircetly.
-    MutexLockMaybe lock((pool == pool_) ? NULL : pool->mutex_);
+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_);
 
-    // Note that we don't have to check fallback_database_ here because the
-    // symbol has to be in one of its file's direct dependencies, and we have
-    // already loaded those by the time we get here.
-    result = pool->tables_->FindSymbol(name);
-    if (!result.IsNull()) break;
-    if (pool->underlay_ == NULL) return kNullSymbol;
-    pool = pool->underlay_;
+  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;
@@ -2308,10 +2630,7 @@
   // Only find symbols which were defined in this file or one of its
   // dependencies.
   const FileDescriptor* file = result.GetFile();
-  if (file == file_) return result;
-  for (int i = 0; i < file_->dependency_count(); i++) {
-    if (file == file_->dependency(i)) return result;
-  }
+  if (file == file_ || dependencies_.count(file) > 0) return result;
 
   if (result.type == Symbol::PACKAGE) {
     // Arg, this is overcomplicated.  The symbol is a package name.  It could
@@ -2322,12 +2641,10 @@
     // 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 (int i = 0; i < file_->dependency_count(); i++) {
+    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 (file_->dependency(i) != NULL &&
-          IsInPackage(file_->dependency(i), name)) {
-        return result;
-      }
+      if (*it != NULL && IsInPackage(*it, name)) return result;
     }
   }
 
@@ -2448,6 +2765,8 @@
   FileDescriptor* placeholder_file = tables_->Allocate<FileDescriptor>();
   memset(placeholder_file, 0, sizeof(*placeholder_file));
 
+  placeholder_file->source_code_info_ = &SourceCodeInfo::default_instance();
+
   placeholder_file->name_ =
     tables_->AllocateString(*placeholder_full_name + ".placeholder.proto");
   placeholder_file->package_ = placeholder_package;
@@ -2757,11 +3076,19 @@
   }
 
   // Checkpoint the tables so that we can roll back if something goes wrong.
-  tables_->Checkpoint();
+  tables_->AddCheckpoint();
 
   FileDescriptor* result = tables_->Allocate<FileDescriptor>();
   file_ = result;
 
+  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_;
 
@@ -2788,7 +3115,7 @@
              "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_->Rollback();
+    tables_->RollbackToLastCheckpoint();
     return NULL;
   }
   if (!result->package().empty()) {
@@ -2833,6 +3160,45 @@
     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;
+    } 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);
@@ -2870,10 +3236,10 @@
   }
 
   if (had_errors_) {
-    tables_->Rollback();
+    tables_->RollbackToLastCheckpoint();
     return NULL;
   } else {
-    tables_->Checkpoint();
+    tables_->ClearLastCheckpoint();
     return result;
   }
 }
@@ -3065,7 +3431,7 @@
               UnescapeCEscapeString(proto.default_value()));
           } else {
             result->default_value_string_ =
-              tables_->AllocateString(proto.default_value());
+                tables_->AllocateString(proto.default_value());
           }
           break;
         case FieldDescriptor::CPPTYPE_MESSAGE:
@@ -3126,7 +3492,15 @@
   if (result->number() <= 0) {
     AddError(result->full_name(), proto, DescriptorPool::ErrorCollector::NUMBER,
              "Field numbers must be positive integers.");
-  } else if (result->number() > FieldDescriptor::kMaxNumber) {
+  } 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));
@@ -3181,12 +3555,10 @@
              "Extension numbers must be positive integers.");
   }
 
-  if (result->end > FieldDescriptor::kMaxNumber + 1) {
-    AddError(parent->full_name(), proto,
-             DescriptorPool::ErrorCollector::NUMBER,
-             strings::Substitute("Extension numbers cannot be greater than $0.",
-                                 FieldDescriptor::kMaxNumber));
-  }
+  // 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,
@@ -3681,6 +4053,20 @@
   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,
@@ -3689,6 +4075,15 @@
     ValidateMapKey(field, 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(
@@ -3727,11 +4122,27 @@
              "files.  Note that you cannot extend a non-lite type to contain "
              "a lite type, but the reverse is allowed.");
   }
+
 }
 
 void DescriptorBuilder::ValidateEnumOptions(EnumDescriptor* enm,
                                             const EnumDescriptorProto& proto) {
   VALIDATE_OPTIONS_FROM_ARRAY(enm, value, EnumValue);
+  if (!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()) {
+        AddError(enm->full_name(), proto,
+                 DescriptorPool::ErrorCollector::NUMBER,
+                 "\"" + enum_value->full_name() +
+                 "\" uses the same enum value as \"" +
+                 used_values[enum_value->number()] + "\"");
+      } else {
+        used_values[enum_value->number()] = enum_value->full_name();
+      }
+    }
+  }
 }
 
 void DescriptorBuilder::ValidateEnumValueOptions(
@@ -3811,6 +4222,7 @@
   field->experimental_map_key_ = key_field;
 }
 
+
 #undef VALIDATE_OPTIONS_FROM_ARRAY
 
 // -------------------------------------------------------------------
@@ -3901,9 +4313,11 @@
   // 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::FindSymbol(), not
+  // 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.
+  // 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) {
@@ -3939,8 +4353,8 @@
       // 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 symbol = builder_->LookupSymbol(name_part,
-                                             options_to_interpret_->name_scope);
+      symbol = builder_->LookupSymbol(name_part,
+                                      options_to_interpret_->name_scope);
       if (!symbol.IsNull() && symbol.type == Symbol::FIELD) {
         field = symbol.field_descriptor;
       }
@@ -4344,14 +4758,32 @@
   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, message->GetDescriptor()->full_name());
+        name, descriptor->full_name());
     if (result.type == Symbol::FIELD &&
         result.field_descriptor->is_extension()) {
       return result.field_descriptor;
-    } else {
-      return NULL;
+    } 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;
   }
 };
 
@@ -4409,7 +4841,13 @@
   } else {
     string serial;
     dynamic->SerializeToString(&serial);  // Never fails
-    unknown_fields->AddLengthDelimited(option_field->number(), serial);
+    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;
   }
 }