1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // http://code.google.com/p/protobuf/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 // Author: kenton (at) google.com (Kenton Varda) 32 // Based on original Protocol Buffers design by 33 // Sanjay Ghemawat, Jeff Dean, and others. 34 35 #include <google/protobuf/descriptor_database.h> 36 37 #include <set> 38 39 #include <google/protobuf/descriptor.pb.h> 40 #include <google/protobuf/wire_format_lite_inl.h> 41 #include <google/protobuf/stubs/strutil.h> 42 #include <google/protobuf/stubs/stl_util.h> 43 #include <google/protobuf/stubs/map-util.h> 44 45 namespace google { 46 namespace protobuf { 47 48 DescriptorDatabase::~DescriptorDatabase() {} 49 50 // =================================================================== 51 52 template <typename Value> 53 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::AddFile( 54 const FileDescriptorProto& file, 55 Value value) { 56 if (!InsertIfNotPresent(&by_name_, file.name(), value)) { 57 GOOGLE_LOG(ERROR) << "File already exists in database: " << file.name(); 58 return false; 59 } 60 61 // We must be careful here -- calling file.package() if file.has_package() is 62 // false could access an uninitialized static-storage variable if we are being 63 // run at startup time. 64 string path = file.has_package() ? file.package() : string(); 65 if (!path.empty()) path += '.'; 66 67 for (int i = 0; i < file.message_type_size(); i++) { 68 if (!AddSymbol(path + file.message_type(i).name(), value)) return false; 69 if (!AddNestedExtensions(file.message_type(i), value)) return false; 70 } 71 for (int i = 0; i < file.enum_type_size(); i++) { 72 if (!AddSymbol(path + file.enum_type(i).name(), value)) return false; 73 } 74 for (int i = 0; i < file.extension_size(); i++) { 75 if (!AddSymbol(path + file.extension(i).name(), value)) return false; 76 if (!AddExtension(file.extension(i), value)) return false; 77 } 78 for (int i = 0; i < file.service_size(); i++) { 79 if (!AddSymbol(path + file.service(i).name(), value)) return false; 80 } 81 82 return true; 83 } 84 85 template <typename Value> 86 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::AddSymbol( 87 const string& name, Value value) { 88 // We need to make sure not to violate our map invariant. 89 90 // If the symbol name is invalid it could break our lookup algorithm (which 91 // relies on the fact that '.' sorts before all other characters that are 92 // valid in symbol names). 93 if (!ValidateSymbolName(name)) { 94 GOOGLE_LOG(ERROR) << "Invalid symbol name: " << name; 95 return false; 96 } 97 98 // Try to look up the symbol to make sure a super-symbol doesn't already 99 // exist. 100 typename map<string, Value>::iterator iter = FindLastLessOrEqual(name); 101 102 if (iter == by_symbol_.end()) { 103 // Apparently the map is currently empty. Just insert and be done with it. 104 by_symbol_.insert(typename map<string, Value>::value_type(name, value)); 105 return true; 106 } 107 108 if (IsSubSymbol(iter->first, name)) { 109 GOOGLE_LOG(ERROR) << "Symbol name \"" << name << "\" conflicts with the existing " 110 "symbol \"" << iter->first << "\"."; 111 return false; 112 } 113 114 // OK, that worked. Now we have to make sure that no symbol in the map is 115 // a sub-symbol of the one we are inserting. The only symbol which could 116 // be so is the first symbol that is greater than the new symbol. Since 117 // |iter| points at the last symbol that is less than or equal, we just have 118 // to increment it. 119 ++iter; 120 121 if (iter != by_symbol_.end() && IsSubSymbol(name, iter->first)) { 122 GOOGLE_LOG(ERROR) << "Symbol name \"" << name << "\" conflicts with the existing " 123 "symbol \"" << iter->first << "\"."; 124 return false; 125 } 126 127 // OK, no conflicts. 128 129 // Insert the new symbol using the iterator as a hint, the new entry will 130 // appear immediately before the one the iterator is pointing at. 131 by_symbol_.insert(iter, typename map<string, Value>::value_type(name, value)); 132 133 return true; 134 } 135 136 template <typename Value> 137 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::AddNestedExtensions( 138 const DescriptorProto& message_type, 139 Value value) { 140 for (int i = 0; i < message_type.nested_type_size(); i++) { 141 if (!AddNestedExtensions(message_type.nested_type(i), value)) return false; 142 } 143 for (int i = 0; i < message_type.extension_size(); i++) { 144 if (!AddExtension(message_type.extension(i), value)) return false; 145 } 146 return true; 147 } 148 149 template <typename Value> 150 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::AddExtension( 151 const FieldDescriptorProto& field, 152 Value value) { 153 if (!field.extendee().empty() && field.extendee()[0] == '.') { 154 // The extension is fully-qualified. We can use it as a lookup key in 155 // the by_symbol_ table. 156 if (!InsertIfNotPresent(&by_extension_, 157 make_pair(field.extendee().substr(1), 158 field.number()), 159 value)) { 160 GOOGLE_LOG(ERROR) << "Extension conflicts with extension already in database: " 161 "extend " << field.extendee() << " { " 162 << field.name() << " = " << field.number() << " }"; 163 return false; 164 } 165 } else { 166 // Not fully-qualified. We can't really do anything here, unfortunately. 167 // We don't consider this an error, though, because the descriptor is 168 // valid. 169 } 170 return true; 171 } 172 173 template <typename Value> 174 Value SimpleDescriptorDatabase::DescriptorIndex<Value>::FindFile( 175 const string& filename) { 176 return FindWithDefault(by_name_, filename, Value()); 177 } 178 179 template <typename Value> 180 Value SimpleDescriptorDatabase::DescriptorIndex<Value>::FindSymbol( 181 const string& name) { 182 typename map<string, Value>::iterator iter = FindLastLessOrEqual(name); 183 184 return (iter != by_symbol_.end() && IsSubSymbol(iter->first, name)) ? 185 iter->second : Value(); 186 } 187 188 template <typename Value> 189 Value SimpleDescriptorDatabase::DescriptorIndex<Value>::FindExtension( 190 const string& containing_type, 191 int field_number) { 192 return FindWithDefault(by_extension_, 193 make_pair(containing_type, field_number), 194 Value()); 195 } 196 197 template <typename Value> 198 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::FindAllExtensionNumbers( 199 const string& containing_type, 200 vector<int>* output) { 201 typename map<pair<string, int>, Value >::const_iterator it = 202 by_extension_.lower_bound(make_pair(containing_type, 0)); 203 bool success = false; 204 205 for (; it != by_extension_.end() && it->first.first == containing_type; 206 ++it) { 207 output->push_back(it->first.second); 208 success = true; 209 } 210 211 return success; 212 } 213 214 template <typename Value> 215 typename map<string, Value>::iterator 216 SimpleDescriptorDatabase::DescriptorIndex<Value>::FindLastLessOrEqual( 217 const string& name) { 218 // Find the last key in the map which sorts less than or equal to the 219 // symbol name. Since upper_bound() returns the *first* key that sorts 220 // *greater* than the input, we want the element immediately before that. 221 typename map<string, Value>::iterator iter = by_symbol_.upper_bound(name); 222 if (iter != by_symbol_.begin()) --iter; 223 return iter; 224 } 225 226 template <typename Value> 227 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::IsSubSymbol( 228 const string& sub_symbol, const string& super_symbol) { 229 return sub_symbol == super_symbol || 230 (HasPrefixString(super_symbol, sub_symbol) && 231 super_symbol[sub_symbol.size()] == '.'); 232 } 233 234 template <typename Value> 235 bool SimpleDescriptorDatabase::DescriptorIndex<Value>::ValidateSymbolName( 236 const string& name) { 237 for (int i = 0; i < name.size(); i++) { 238 // I don't trust ctype.h due to locales. :( 239 if (name[i] != '.' && name[i] != '_' && 240 (name[i] < '0' || name[i] > '9') && 241 (name[i] < 'A' || name[i] > 'Z') && 242 (name[i] < 'a' || name[i] > 'z')) { 243 return false; 244 } 245 } 246 return true; 247 } 248 249 // ------------------------------------------------------------------- 250 251 SimpleDescriptorDatabase::SimpleDescriptorDatabase() {} 252 SimpleDescriptorDatabase::~SimpleDescriptorDatabase() { 253 STLDeleteElements(&files_to_delete_); 254 } 255 256 bool SimpleDescriptorDatabase::Add(const FileDescriptorProto& file) { 257 FileDescriptorProto* new_file = new FileDescriptorProto; 258 new_file->CopyFrom(file); 259 return AddAndOwn(new_file); 260 } 261 262 bool SimpleDescriptorDatabase::AddAndOwn(const FileDescriptorProto* file) { 263 files_to_delete_.push_back(file); 264 return index_.AddFile(*file, file); 265 } 266 267 bool SimpleDescriptorDatabase::FindFileByName( 268 const string& filename, 269 FileDescriptorProto* output) { 270 return MaybeCopy(index_.FindFile(filename), output); 271 } 272 273 bool SimpleDescriptorDatabase::FindFileContainingSymbol( 274 const string& symbol_name, 275 FileDescriptorProto* output) { 276 return MaybeCopy(index_.FindSymbol(symbol_name), output); 277 } 278 279 bool SimpleDescriptorDatabase::FindFileContainingExtension( 280 const string& containing_type, 281 int field_number, 282 FileDescriptorProto* output) { 283 return MaybeCopy(index_.FindExtension(containing_type, field_number), output); 284 } 285 286 bool SimpleDescriptorDatabase::FindAllExtensionNumbers( 287 const string& extendee_type, 288 vector<int>* output) { 289 return index_.FindAllExtensionNumbers(extendee_type, output); 290 } 291 292 bool SimpleDescriptorDatabase::MaybeCopy(const FileDescriptorProto* file, 293 FileDescriptorProto* output) { 294 if (file == NULL) return false; 295 output->CopyFrom(*file); 296 return true; 297 } 298 299 // ------------------------------------------------------------------- 300 301 EncodedDescriptorDatabase::EncodedDescriptorDatabase() {} 302 EncodedDescriptorDatabase::~EncodedDescriptorDatabase() { 303 for (int i = 0; i < files_to_delete_.size(); i++) { 304 operator delete(files_to_delete_[i]); 305 } 306 } 307 308 bool EncodedDescriptorDatabase::Add( 309 const void* encoded_file_descriptor, int size) { 310 FileDescriptorProto file; 311 if (file.ParseFromArray(encoded_file_descriptor, size)) { 312 return index_.AddFile(file, make_pair(encoded_file_descriptor, size)); 313 } else { 314 GOOGLE_LOG(ERROR) << "Invalid file descriptor data passed to " 315 "EncodedDescriptorDatabase::Add()."; 316 return false; 317 } 318 } 319 320 bool EncodedDescriptorDatabase::AddCopy( 321 const void* encoded_file_descriptor, int size) { 322 void* copy = operator new(size); 323 memcpy(copy, encoded_file_descriptor, size); 324 files_to_delete_.push_back(copy); 325 return Add(copy, size); 326 } 327 328 bool EncodedDescriptorDatabase::FindFileByName( 329 const string& filename, 330 FileDescriptorProto* output) { 331 return MaybeParse(index_.FindFile(filename), output); 332 } 333 334 bool EncodedDescriptorDatabase::FindFileContainingSymbol( 335 const string& symbol_name, 336 FileDescriptorProto* output) { 337 return MaybeParse(index_.FindSymbol(symbol_name), output); 338 } 339 340 bool EncodedDescriptorDatabase::FindNameOfFileContainingSymbol( 341 const string& symbol_name, 342 string* output) { 343 pair<const void*, int> encoded_file = index_.FindSymbol(symbol_name); 344 if (encoded_file.first == NULL) return false; 345 346 // Optimization: The name should be the first field in the encoded message. 347 // Try to just read it directly. 348 io::CodedInputStream input(reinterpret_cast<const uint8*>(encoded_file.first), 349 encoded_file.second); 350 351 const uint32 kNameTag = internal::WireFormatLite::MakeTag( 352 FileDescriptorProto::kNameFieldNumber, 353 internal::WireFormatLite::WIRETYPE_LENGTH_DELIMITED); 354 355 if (input.ReadTag() == kNameTag) { 356 // Success! 357 return internal::WireFormatLite::ReadString(&input, output); 358 } else { 359 // Slow path. Parse whole message. 360 FileDescriptorProto file_proto; 361 if (!file_proto.ParseFromArray(encoded_file.first, encoded_file.second)) { 362 return false; 363 } 364 *output = file_proto.name(); 365 return true; 366 } 367 } 368 369 bool EncodedDescriptorDatabase::FindFileContainingExtension( 370 const string& containing_type, 371 int field_number, 372 FileDescriptorProto* output) { 373 return MaybeParse(index_.FindExtension(containing_type, field_number), 374 output); 375 } 376 377 bool EncodedDescriptorDatabase::FindAllExtensionNumbers( 378 const string& extendee_type, 379 vector<int>* output) { 380 return index_.FindAllExtensionNumbers(extendee_type, output); 381 } 382 383 bool EncodedDescriptorDatabase::MaybeParse( 384 pair<const void*, int> encoded_file, 385 FileDescriptorProto* output) { 386 if (encoded_file.first == NULL) return false; 387 return output->ParseFromArray(encoded_file.first, encoded_file.second); 388 } 389 390 // =================================================================== 391 392 DescriptorPoolDatabase::DescriptorPoolDatabase(const DescriptorPool& pool) 393 : pool_(pool) {} 394 DescriptorPoolDatabase::~DescriptorPoolDatabase() {} 395 396 bool DescriptorPoolDatabase::FindFileByName( 397 const string& filename, 398 FileDescriptorProto* output) { 399 const FileDescriptor* file = pool_.FindFileByName(filename); 400 if (file == NULL) return false; 401 output->Clear(); 402 file->CopyTo(output); 403 return true; 404 } 405 406 bool DescriptorPoolDatabase::FindFileContainingSymbol( 407 const string& symbol_name, 408 FileDescriptorProto* output) { 409 const FileDescriptor* file = pool_.FindFileContainingSymbol(symbol_name); 410 if (file == NULL) return false; 411 output->Clear(); 412 file->CopyTo(output); 413 return true; 414 } 415 416 bool DescriptorPoolDatabase::FindFileContainingExtension( 417 const string& containing_type, 418 int field_number, 419 FileDescriptorProto* output) { 420 const Descriptor* extendee = pool_.FindMessageTypeByName(containing_type); 421 if (extendee == NULL) return false; 422 423 const FieldDescriptor* extension = 424 pool_.FindExtensionByNumber(extendee, field_number); 425 if (extension == NULL) return false; 426 427 output->Clear(); 428 extension->file()->CopyTo(output); 429 return true; 430 } 431 432 bool DescriptorPoolDatabase::FindAllExtensionNumbers( 433 const string& extendee_type, 434 vector<int>* output) { 435 const Descriptor* extendee = pool_.FindMessageTypeByName(extendee_type); 436 if (extendee == NULL) return false; 437 438 vector<const FieldDescriptor*> extensions; 439 pool_.FindAllExtensions(extendee, &extensions); 440 441 for (int i = 0; i < extensions.size(); ++i) { 442 output->push_back(extensions[i]->number()); 443 } 444 445 return true; 446 } 447 448 // =================================================================== 449 450 MergedDescriptorDatabase::MergedDescriptorDatabase( 451 DescriptorDatabase* source1, 452 DescriptorDatabase* source2) { 453 sources_.push_back(source1); 454 sources_.push_back(source2); 455 } 456 MergedDescriptorDatabase::MergedDescriptorDatabase( 457 const vector<DescriptorDatabase*>& sources) 458 : sources_(sources) {} 459 MergedDescriptorDatabase::~MergedDescriptorDatabase() {} 460 461 bool MergedDescriptorDatabase::FindFileByName( 462 const string& filename, 463 FileDescriptorProto* output) { 464 for (int i = 0; i < sources_.size(); i++) { 465 if (sources_[i]->FindFileByName(filename, output)) { 466 return true; 467 } 468 } 469 return false; 470 } 471 472 bool MergedDescriptorDatabase::FindFileContainingSymbol( 473 const string& symbol_name, 474 FileDescriptorProto* output) { 475 for (int i = 0; i < sources_.size(); i++) { 476 if (sources_[i]->FindFileContainingSymbol(symbol_name, output)) { 477 // The symbol was found in source i. However, if one of the previous 478 // sources defines a file with the same name (which presumably doesn't 479 // contain the symbol, since it wasn't found in that source), then we 480 // must hide it from the caller. 481 FileDescriptorProto temp; 482 for (int j = 0; j < i; j++) { 483 if (sources_[j]->FindFileByName(output->name(), &temp)) { 484 // Found conflicting file in a previous source. 485 return false; 486 } 487 } 488 return true; 489 } 490 } 491 return false; 492 } 493 494 bool MergedDescriptorDatabase::FindFileContainingExtension( 495 const string& containing_type, 496 int field_number, 497 FileDescriptorProto* output) { 498 for (int i = 0; i < sources_.size(); i++) { 499 if (sources_[i]->FindFileContainingExtension( 500 containing_type, field_number, output)) { 501 // The symbol was found in source i. However, if one of the previous 502 // sources defines a file with the same name (which presumably doesn't 503 // contain the symbol, since it wasn't found in that source), then we 504 // must hide it from the caller. 505 FileDescriptorProto temp; 506 for (int j = 0; j < i; j++) { 507 if (sources_[j]->FindFileByName(output->name(), &temp)) { 508 // Found conflicting file in a previous source. 509 return false; 510 } 511 } 512 return true; 513 } 514 } 515 return false; 516 } 517 518 bool MergedDescriptorDatabase::FindAllExtensionNumbers( 519 const string& extendee_type, 520 vector<int>* output) { 521 set<int> merged_results; 522 vector<int> results; 523 bool success = false; 524 525 for (int i = 0; i < sources_.size(); i++) { 526 if (sources_[i]->FindAllExtensionNumbers(extendee_type, &results)) { 527 copy(results.begin(), results.end(), 528 insert_iterator<set<int> >(merged_results, merged_results.begin())); 529 success = true; 530 } 531 results.clear(); 532 } 533 534 copy(merged_results.begin(), merged_results.end(), 535 insert_iterator<vector<int> >(*output, output->end())); 536 537 return success; 538 } 539 540 } // namespace protobuf 541 } // namespace google 542