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