1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // https://developers.google.com/protocol-buffers/ 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@google.com (Kenton Varda) 32 // Based on original Protocol Buffers design by 33 // Sanjay Ghemawat, Jeff Dean, and others. 34 // 35 // Interface for manipulating databases of descriptors. 36 37 #ifndef GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 38 #define GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 39 40 #include <map> 41 #include <string> 42 #include <utility> 43 #include <vector> 44 #include <google/protobuf/stubs/common.h> 45 #include <google/protobuf/descriptor.h> 46 47 namespace google { 48 namespace protobuf { 49 50 // Defined in this file. 51 class DescriptorDatabase; 52 class SimpleDescriptorDatabase; 53 class EncodedDescriptorDatabase; 54 class DescriptorPoolDatabase; 55 class MergedDescriptorDatabase; 56 57 // Abstract interface for a database of descriptors. 58 // 59 // This is useful if you want to create a DescriptorPool which loads 60 // descriptors on-demand from some sort of large database. If the database 61 // is large, it may be inefficient to enumerate every .proto file inside it 62 // calling DescriptorPool::BuildFile() for each one. Instead, a DescriptorPool 63 // can be created which wraps a DescriptorDatabase and only builds particular 64 // descriptors when they are needed. 65 class LIBPROTOBUF_EXPORT DescriptorDatabase { 66 public: DescriptorDatabase()67 inline DescriptorDatabase() {} 68 virtual ~DescriptorDatabase(); 69 70 // Find a file by file name. Fills in in *output and returns true if found. 71 // Otherwise, returns false, leaving the contents of *output undefined. 72 virtual bool FindFileByName(const string& filename, 73 FileDescriptorProto* output) = 0; 74 75 // Find the file that declares the given fully-qualified symbol name. 76 // If found, fills in *output and returns true, otherwise returns false 77 // and leaves *output undefined. 78 virtual bool FindFileContainingSymbol(const string& symbol_name, 79 FileDescriptorProto* output) = 0; 80 81 // Find the file which defines an extension extending the given message type 82 // with the given field number. If found, fills in *output and returns true, 83 // otherwise returns false and leaves *output undefined. containing_type 84 // must be a fully-qualified type name. 85 virtual bool FindFileContainingExtension(const string& containing_type, 86 int field_number, 87 FileDescriptorProto* output) = 0; 88 89 // Finds the tag numbers used by all known extensions of 90 // extendee_type, and appends them to output in an undefined 91 // order. This method is best-effort: it's not guaranteed that the 92 // database will find all extensions, and it's not guaranteed that 93 // FindFileContainingExtension will return true on all of the found 94 // numbers. Returns true if the search was successful, otherwise 95 // returns false and leaves output unchanged. 96 // 97 // This method has a default implementation that always returns 98 // false. FindAllExtensionNumbers(const string &,std::vector<int> *)99 virtual bool FindAllExtensionNumbers(const string& /* extendee_type */, 100 std::vector<int>* /* output */) { 101 return false; 102 } 103 104 105 // Finds the file names and appends them to the output in an 106 // undefined order. This method is best-effort: it's not guaranteed that the 107 // database will find all files. Returns true if the database supports 108 // searching all file names, otherwise returns false and leaves output 109 // unchanged. 110 // 111 // This method has a default implementation that always returns 112 // false. FindAllFileNames(std::vector<string> * output)113 virtual bool FindAllFileNames(std::vector<string>* output) { 114 return false; 115 } 116 117 private: 118 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(DescriptorDatabase); 119 }; 120 121 // A DescriptorDatabase into which you can insert files manually. 122 // 123 // FindFileContainingSymbol() is fully-implemented. When you add a file, its 124 // symbols will be indexed for this purpose. Note that the implementation 125 // may return false positives, but only if it isn't possible for the symbol 126 // to be defined in any other file. In particular, if a file defines a symbol 127 // "Foo", then searching for "Foo.[anything]" will match that file. This way, 128 // the database does not need to aggressively index all children of a symbol. 129 // 130 // FindFileContainingExtension() is mostly-implemented. It works if and only 131 // if the original FieldDescriptorProto defining the extension has a 132 // fully-qualified type name in its "extendee" field (i.e. starts with a '.'). 133 // If the extendee is a relative name, SimpleDescriptorDatabase will not 134 // attempt to resolve the type, so it will not know what type the extension is 135 // extending. Therefore, calling FindFileContainingExtension() with the 136 // extension's containing type will never actually find that extension. Note 137 // that this is an unlikely problem, as all FileDescriptorProtos created by the 138 // protocol compiler (as well as ones created by calling 139 // FileDescriptor::CopyTo()) will always use fully-qualified names for all 140 // types. You only need to worry if you are constructing FileDescriptorProtos 141 // yourself, or are calling compiler::Parser directly. 142 class LIBPROTOBUF_EXPORT SimpleDescriptorDatabase : public DescriptorDatabase { 143 public: 144 SimpleDescriptorDatabase(); 145 ~SimpleDescriptorDatabase(); 146 147 // Adds the FileDescriptorProto to the database, making a copy. The object 148 // can be deleted after Add() returns. Returns false if the file conflicted 149 // with a file already in the database, in which case an error will have 150 // been written to GOOGLE_LOG(ERROR). 151 bool Add(const FileDescriptorProto& file); 152 153 // Adds the FileDescriptorProto to the database and takes ownership of it. 154 bool AddAndOwn(const FileDescriptorProto* file); 155 156 // implements DescriptorDatabase ----------------------------------- 157 bool FindFileByName(const string& filename, 158 FileDescriptorProto* output); 159 bool FindFileContainingSymbol(const string& symbol_name, 160 FileDescriptorProto* output); 161 bool FindFileContainingExtension(const string& containing_type, 162 int field_number, 163 FileDescriptorProto* output); 164 bool FindAllExtensionNumbers(const string& extendee_type, 165 std::vector<int>* output); 166 167 private: 168 // So that it can use DescriptorIndex. 169 friend class EncodedDescriptorDatabase; 170 171 // An index mapping file names, symbol names, and extension numbers to 172 // some sort of values. 173 template <typename Value> 174 class DescriptorIndex { 175 public: 176 // Helpers to recursively add particular descriptors and all their contents 177 // to the index. 178 bool AddFile(const FileDescriptorProto& file, 179 Value value); 180 bool AddSymbol(const string& name, Value value); 181 bool AddNestedExtensions(const DescriptorProto& message_type, 182 Value value); 183 bool AddExtension(const FieldDescriptorProto& field, 184 Value value); 185 186 Value FindFile(const string& filename); 187 Value FindSymbol(const string& name); 188 Value FindExtension(const string& containing_type, int field_number); 189 bool FindAllExtensionNumbers(const string& containing_type, 190 std::vector<int>* output); 191 192 private: 193 std::map<string, Value> by_name_; 194 std::map<string, Value> by_symbol_; 195 std::map<std::pair<string, int>, Value> by_extension_; 196 197 // Invariant: The by_symbol_ map does not contain any symbols which are 198 // prefixes of other symbols in the map. For example, "foo.bar" is a 199 // prefix of "foo.bar.baz" (but is not a prefix of "foo.barbaz"). 200 // 201 // This invariant is important because it means that given a symbol name, 202 // we can find a key in the map which is a prefix of the symbol in O(lg n) 203 // time, and we know that there is at most one such key. 204 // 205 // The prefix lookup algorithm works like so: 206 // 1) Find the last key in the map which is less than or equal to the 207 // search key. 208 // 2) If the found key is a prefix of the search key, then return it. 209 // Otherwise, there is no match. 210 // 211 // I am sure this algorithm has been described elsewhere, but since I 212 // wasn't able to find it quickly I will instead prove that it works 213 // myself. The key to the algorithm is that if a match exists, step (1) 214 // will find it. Proof: 215 // 1) Define the "search key" to be the key we are looking for, the "found 216 // key" to be the key found in step (1), and the "match key" to be the 217 // key which actually matches the serach key (i.e. the key we're trying 218 // to find). 219 // 2) The found key must be less than or equal to the search key by 220 // definition. 221 // 3) The match key must also be less than or equal to the search key 222 // (because it is a prefix). 223 // 4) The match key cannot be greater than the found key, because if it 224 // were, then step (1) of the algorithm would have returned the match 225 // key instead (since it finds the *greatest* key which is less than or 226 // equal to the search key). 227 // 5) Therefore, the found key must be between the match key and the search 228 // key, inclusive. 229 // 6) Since the search key must be a sub-symbol of the match key, if it is 230 // not equal to the match key, then search_key[match_key.size()] must 231 // be '.'. 232 // 7) Since '.' sorts before any other character that is valid in a symbol 233 // name, then if the found key is not equal to the match key, then 234 // found_key[match_key.size()] must also be '.', because any other value 235 // would make it sort after the search key. 236 // 8) Therefore, if the found key is not equal to the match key, then the 237 // found key must be a sub-symbol of the match key. However, this would 238 // contradict our map invariant which says that no symbol in the map is 239 // a sub-symbol of any other. 240 // 9) Therefore, the found key must match the match key. 241 // 242 // The above proof assumes the match key exists. In the case that the 243 // match key does not exist, then step (1) will return some other symbol. 244 // That symbol cannot be a super-symbol of the search key since if it were, 245 // then it would be a match, and we're assuming the match key doesn't exist. 246 // Therefore, step 2 will correctly return no match. 247 248 // Find the last entry in the by_symbol_ map whose key is less than or 249 // equal to the given name. 250 typename std::map<string, Value>::iterator FindLastLessOrEqual( 251 const string& name); 252 253 // True if either the arguments are equal or super_symbol identifies a 254 // parent symbol of sub_symbol (e.g. "foo.bar" is a parent of 255 // "foo.bar.baz", but not a parent of "foo.barbaz"). 256 bool IsSubSymbol(const string& sub_symbol, const string& super_symbol); 257 258 // Returns true if and only if all characters in the name are alphanumerics, 259 // underscores, or periods. 260 bool ValidateSymbolName(const string& name); 261 }; 262 263 264 DescriptorIndex<const FileDescriptorProto*> index_; 265 std::vector<const FileDescriptorProto*> files_to_delete_; 266 267 // If file is non-NULL, copy it into *output and return true, otherwise 268 // return false. 269 bool MaybeCopy(const FileDescriptorProto* file, 270 FileDescriptorProto* output); 271 272 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(SimpleDescriptorDatabase); 273 }; 274 275 // Very similar to SimpleDescriptorDatabase, but stores all the descriptors 276 // as raw bytes and generally tries to use as little memory as possible. 277 // 278 // The same caveats regarding FindFileContainingExtension() apply as with 279 // SimpleDescriptorDatabase. 280 class LIBPROTOBUF_EXPORT EncodedDescriptorDatabase : public DescriptorDatabase { 281 public: 282 EncodedDescriptorDatabase(); 283 ~EncodedDescriptorDatabase(); 284 285 // Adds the FileDescriptorProto to the database. The descriptor is provided 286 // in encoded form. The database does not make a copy of the bytes, nor 287 // does it take ownership; it's up to the caller to make sure the bytes 288 // remain valid for the life of the database. Returns false and logs an error 289 // if the bytes are not a valid FileDescriptorProto or if the file conflicted 290 // with a file already in the database. 291 bool Add(const void* encoded_file_descriptor, int size); 292 293 // Like Add(), but makes a copy of the data, so that the caller does not 294 // need to keep it around. 295 bool AddCopy(const void* encoded_file_descriptor, int size); 296 297 // Like FindFileContainingSymbol but returns only the name of the file. 298 bool FindNameOfFileContainingSymbol(const string& symbol_name, 299 string* output); 300 301 // implements DescriptorDatabase ----------------------------------- 302 bool FindFileByName(const string& filename, 303 FileDescriptorProto* output); 304 bool FindFileContainingSymbol(const string& symbol_name, 305 FileDescriptorProto* output); 306 bool FindFileContainingExtension(const string& containing_type, 307 int field_number, 308 FileDescriptorProto* output); 309 bool FindAllExtensionNumbers(const string& extendee_type, 310 std::vector<int>* output); 311 312 private: 313 SimpleDescriptorDatabase::DescriptorIndex<std::pair<const void*, int> > 314 index_; 315 std::vector<void*> files_to_delete_; 316 317 // If encoded_file.first is non-NULL, parse the data into *output and return 318 // true, otherwise return false. 319 bool MaybeParse(std::pair<const void*, int> encoded_file, 320 FileDescriptorProto* output); 321 322 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(EncodedDescriptorDatabase); 323 }; 324 325 // A DescriptorDatabase that fetches files from a given pool. 326 class LIBPROTOBUF_EXPORT DescriptorPoolDatabase : public DescriptorDatabase { 327 public: 328 explicit DescriptorPoolDatabase(const DescriptorPool& pool); 329 ~DescriptorPoolDatabase(); 330 331 // implements DescriptorDatabase ----------------------------------- 332 bool FindFileByName(const string& filename, 333 FileDescriptorProto* output); 334 bool FindFileContainingSymbol(const string& symbol_name, 335 FileDescriptorProto* output); 336 bool FindFileContainingExtension(const string& containing_type, 337 int field_number, 338 FileDescriptorProto* output); 339 bool FindAllExtensionNumbers(const string& extendee_type, 340 std::vector<int>* output); 341 342 private: 343 const DescriptorPool& pool_; 344 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(DescriptorPoolDatabase); 345 }; 346 347 // A DescriptorDatabase that wraps two or more others. It first searches the 348 // first database and, if that fails, tries the second, and so on. 349 class LIBPROTOBUF_EXPORT MergedDescriptorDatabase : public DescriptorDatabase { 350 public: 351 // Merge just two databases. The sources remain property of the caller. 352 MergedDescriptorDatabase(DescriptorDatabase* source1, 353 DescriptorDatabase* source2); 354 // Merge more than two databases. The sources remain property of the caller. 355 // The vector may be deleted after the constructor returns but the 356 // DescriptorDatabases need to stick around. 357 explicit MergedDescriptorDatabase( 358 const std::vector<DescriptorDatabase*>& sources); 359 ~MergedDescriptorDatabase(); 360 361 // implements DescriptorDatabase ----------------------------------- 362 bool FindFileByName(const string& filename, 363 FileDescriptorProto* output); 364 bool FindFileContainingSymbol(const string& symbol_name, 365 FileDescriptorProto* output); 366 bool FindFileContainingExtension(const string& containing_type, 367 int field_number, 368 FileDescriptorProto* output); 369 // Merges the results of calling all databases. Returns true iff any 370 // of the databases returned true. 371 bool FindAllExtensionNumbers(const string& extendee_type, 372 std::vector<int>* output); 373 374 375 private: 376 std::vector<DescriptorDatabase*> sources_; 377 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MergedDescriptorDatabase); 378 }; 379 380 } // namespace protobuf 381 382 } // namespace google 383 #endif // GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 384