diff options
Diffstat (limited to 'src/google/protobuf/descriptor_database.h')
| -rw-r--r-- | src/google/protobuf/descriptor_database.h | 207 |
1 files changed, 186 insertions, 21 deletions
diff --git a/src/google/protobuf/descriptor_database.h b/src/google/protobuf/descriptor_database.h index 1230d09b..c23ab75f 100644 --- a/src/google/protobuf/descriptor_database.h +++ b/src/google/protobuf/descriptor_database.h @@ -46,6 +46,13 @@ namespace google { namespace protobuf { +// Defined in this file. +class DescriptorDatabase; +class SimpleDescriptorDatabase; +class EncodedDescriptorDatabase; +class DescriptorPoolDatabase; +class MergedDescriptorDatabase; + // Abstract interface for a database of descriptors. // // This is useful if you want to create a DescriptorPool which loads @@ -78,6 +85,21 @@ class LIBPROTOBUF_EXPORT DescriptorDatabase { int field_number, FileDescriptorProto* output) = 0; + // Finds the tag numbers used by all known extensions of + // extendee_type, and appends them to output in an undefined + // order. This method is best-effort: it's not guaranteed that the + // database will find all extensions, and it's not guaranteed that + // FindFileContainingExtension will return true on all of the found + // numbers. Returns true if the search was successful, otherwise + // returns false and leaves output unchanged. + // + // This method has a default implementation that always returns + // false. + virtual bool FindAllExtensionNumbers(const string& extendee_type, + vector<int>* output) { + return false; + } + private: GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(DescriptorDatabase); }; @@ -85,7 +107,11 @@ class LIBPROTOBUF_EXPORT DescriptorDatabase { // A DescriptorDatabase into which you can insert files manually. // // FindFileContainingSymbol() is fully-implemented. When you add a file, its -// symbols will be indexed for this purpose. +// symbols will be indexed for this purpose. Note that the implementation +// may return false positives, but only if it isn't possible for the symbol +// to be defined in any other file. In particular, if a file defines a symbol +// "Foo", then searching for "Foo.[anything]" will match that file. This way, +// the database does not need to aggressively index all children of a symbol. // // FindFileContainingExtension() is mostly-implemented. It works if and only // if the original FieldDescriptorProto defining the extension has a @@ -105,11 +131,13 @@ class LIBPROTOBUF_EXPORT SimpleDescriptorDatabase : public DescriptorDatabase { ~SimpleDescriptorDatabase(); // Adds the FileDescriptorProto to the database, making a copy. The object - // can be deleted after Add() returns. - void Add(const FileDescriptorProto& file); + // can be deleted after Add() returns. Returns false if the file conflicted + // with a file already in the database, in which case an error will have + // been written to GOOGLE_LOG(ERROR). + bool Add(const FileDescriptorProto& file); // Adds the FileDescriptorProto to the database and takes ownership of it. - void AddAndOwn(const FileDescriptorProto* file); + bool AddAndOwn(const FileDescriptorProto* file); // implements DescriptorDatabase ----------------------------------- bool FindFileByName(const string& filename, @@ -119,31 +147,162 @@ class LIBPROTOBUF_EXPORT SimpleDescriptorDatabase : public DescriptorDatabase { bool FindFileContainingExtension(const string& containing_type, int field_number, FileDescriptorProto* output); + bool FindAllExtensionNumbers(const string& extendee_type, + vector<int>* output); private: - // Helpers to recursively add particular descriptors and all their contents - // to the by-symbol and by-extension tables. - void AddMessage(const string& path, - const DescriptorProto& message_type, - const FileDescriptorProto* file); - void AddField(const string& path, - const FieldDescriptorProto& field, - const FileDescriptorProto* file); - void AddEnum(const string& path, - const EnumDescriptorProto& enum_type, - const FileDescriptorProto* file); - void AddService(const string& path, - const ServiceDescriptorProto& service, - const FileDescriptorProto* file); + // So that it can use DescriptorIndex. + friend class EncodedDescriptorDatabase; + + // An index mapping file names, symbol names, and extension numbers to + // some sort of values. + template <typename Value> + class DescriptorIndex { + public: + // Helpers to recursively add particular descriptors and all their contents + // to the index. + bool AddFile(const FileDescriptorProto& file, + Value value); + bool AddSymbol(const string& name, Value value); + bool AddNestedExtensions(const DescriptorProto& message_type, + Value value); + bool AddExtension(const FieldDescriptorProto& field, + Value value); + + Value FindFile(const string& filename); + Value FindSymbol(const string& name); + Value FindExtension(const string& containing_type, int field_number); + bool FindAllExtensionNumbers(const string& containing_type, + vector<int>* output); + + private: + map<string, Value> by_name_; + map<string, Value> by_symbol_; + map<pair<string, int>, Value> by_extension_; + + // Invariant: The by_symbol_ map does not contain any symbols which are + // prefixes of other symbols in the map. For example, "foo.bar" is a + // prefix of "foo.bar.baz" (but is not a prefix of "foo.barbaz"). + // + // This invariant is important because it means that given a symbol name, + // we can find a key in the map which is a prefix of the symbol in O(lg n) + // time, and we know that there is at most one such key. + // + // The prefix lookup algorithm works like so: + // 1) Find the last key in the map which is less than or equal to the + // search key. + // 2) If the found key is a prefix of the search key, then return it. + // Otherwise, there is no match. + // + // I am sure this algorithm has been described elsewhere, but since I + // wasn't able to find it quickly I will instead prove that it works + // myself. The key to the algorithm is that if a match exists, step (1) + // will find it. Proof: + // 1) Define the "search key" to be the key we are looking for, the "found + // key" to be the key found in step (1), and the "match key" to be the + // key which actually matches the serach key (i.e. the key we're trying + // to find). + // 2) The found key must be less than or equal to the search key by + // definition. + // 3) The match key must also be less than or equal to the search key + // (because it is a prefix). + // 4) The match key cannot be greater than the found key, because if it + // were, then step (1) of the algorithm would have returned the match + // key instead (since it finds the *greatest* key which is less than or + // equal to the search key). + // 5) Therefore, the found key must be between the match key and the search + // key, inclusive. + // 6) Since the search key must be a sub-symbol of the match key, if it is + // not equal to the match key, then search_key[match_key.size()] must + // be '.'. + // 7) Since '.' sorts before any other character that is valid in a symbol + // name, then if the found key is not equal to the match key, then + // found_key[match_key.size()] must also be '.', because any other value + // would make it sort after the search key. + // 8) Therefore, if the found key is not equal to the match key, then the + // found key must be a sub-symbol of the match key. However, this would + // contradict our map invariant which says that no symbol in the map is + // a sub-symbol of any other. + // 9) Therefore, the found key must match the match key. + // + // The above proof assumes the match key exists. In the case that the + // match key does not exist, then step (1) will return some other symbol. + // That symbol cannot be a super-symbol of the search key since if it were, + // then it would be a match, and we're assuming the match key doesn't exist. + // Therefore, step 2 will correctly return no match. + + // Find the last entry in the by_symbol_ map whose key is less than or + // equal to the given name. + typename map<string, Value>::iterator FindLastLessOrEqual( + const string& name); + + // True if either the arguments are equal or super_symbol identifies a + // parent symbol of sub_symbol (e.g. "foo.bar" is a parent of + // "foo.bar.baz", but not a parent of "foo.barbaz"). + bool IsSubSymbol(const string& sub_symbol, const string& super_symbol); + // Returns true if and only if all characters in the name are alphanumerics, + // underscores, or periods. + bool ValidateSymbolName(const string& name); + }; + + + DescriptorIndex<const FileDescriptorProto*> index_; vector<const FileDescriptorProto*> files_to_delete_; - map<string, const FileDescriptorProto*> files_by_name_; - map<string, const FileDescriptorProto*> files_by_symbol_; - map<pair<string, int>, const FileDescriptorProto*> files_by_extension_; + + // If file is non-NULL, copy it into *output and return true, otherwise + // return false. + bool MaybeCopy(const FileDescriptorProto* file, + FileDescriptorProto* output); GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(SimpleDescriptorDatabase); }; +// Very similar to SimpleDescriptorDatabase, but stores all the descriptors +// as raw bytes and generally tries to use as little memory as possible. +// +// The same caveats regarding FindFileContainingExtension() apply as with +// SimpleDescriptorDatabase. +class LIBPROTOBUF_EXPORT EncodedDescriptorDatabase : public DescriptorDatabase { + public: + EncodedDescriptorDatabase(); + ~EncodedDescriptorDatabase(); + + // Adds the FileDescriptorProto to the database. The descriptor is provided + // in encoded form. The database does not make a copy of the bytes, nor + // does it take ownership; it's up to the caller to make sure the bytes + // remain valid for the life of the database. Returns false and logs an error + // if the bytes are not a valid FileDescriptorProto or if the file conflicted + // with a file already in the database. + bool Add(const void* encoded_file_descriptor, int size); + + // Like Add(), but makes a copy of the data, so that the caller does not + // need to keep it around. + bool AddCopy(const void* encoded_file_descriptor, int size); + + // implements DescriptorDatabase ----------------------------------- + bool FindFileByName(const string& filename, + FileDescriptorProto* output); + bool FindFileContainingSymbol(const string& symbol_name, + FileDescriptorProto* output); + bool FindFileContainingExtension(const string& containing_type, + int field_number, + FileDescriptorProto* output); + bool FindAllExtensionNumbers(const string& extendee_type, + vector<int>* output); + + private: + SimpleDescriptorDatabase::DescriptorIndex<pair<const void*, int> > index_; + vector<void*> files_to_delete_; + + // If encoded_file.first is non-NULL, parse the data into *output and return + // true, otherwise return false. + bool MaybeParse(pair<const void*, int> encoded_file, + FileDescriptorProto* output); + + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(EncodedDescriptorDatabase); +}; + // A DescriptorDatabase that fetches files from a given pool. class LIBPROTOBUF_EXPORT DescriptorPoolDatabase : public DescriptorDatabase { public: @@ -158,6 +317,8 @@ class LIBPROTOBUF_EXPORT DescriptorPoolDatabase : public DescriptorDatabase { bool FindFileContainingExtension(const string& containing_type, int field_number, FileDescriptorProto* output); + bool FindAllExtensionNumbers(const string& extendee_type, + vector<int>* output); private: const DescriptorPool& pool_; @@ -185,6 +346,10 @@ class LIBPROTOBUF_EXPORT MergedDescriptorDatabase : public DescriptorDatabase { bool FindFileContainingExtension(const string& containing_type, int field_number, FileDescriptorProto* output); + // Merges the results of calling all databases. Returns true iff any + // of the databases returned true. + bool FindAllExtensionNumbers(const string& extendee_type, + vector<int>* output); private: vector<DescriptorDatabase*> sources_; |