15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Protocol Buffers - Google's data interchange format 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2008 Google Inc. All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://code.google.com/p/protobuf/ 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: kenton@google.com (Kenton Varda) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Based on original Protocol Buffers design by 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sanjay Ghemawat, Jeff Dean, and others. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Interface for manipulating databases of descriptors. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <utility> 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 44ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch#include <google/protobuf/stubs/common.h> 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <google/protobuf/descriptor.h> 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace google { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace protobuf { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Defined in this file. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class DescriptorDatabase; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SimpleDescriptorDatabase; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class EncodedDescriptorDatabase; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class DescriptorPoolDatabase; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MergedDescriptorDatabase; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Abstract interface for a database of descriptors. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is useful if you want to create a DescriptorPool which loads 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// descriptors on-demand from some sort of large database. If the database 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is large, it may be inefficient to enumerate every .proto file inside it 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// calling DescriptorPool::BuildFile() for each one. Instead, a DescriptorPool 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// can be created which wraps a DescriptorDatabase and only builds particular 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// descriptors when they are needed. 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT DescriptorDatabase { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline DescriptorDatabase() {} 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~DescriptorDatabase(); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find a file by file name. Fills in in *output and returns true if found. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, returns false, leaving the contents of *output undefined. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool FindFileByName(const string& filename, 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output) = 0; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find the file that declares the given fully-qualified symbol name. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If found, fills in *output and returns true, otherwise returns false 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and leaves *output undefined. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool FindFileContainingSymbol(const string& symbol_name, 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output) = 0; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find the file which defines an extension extending the given message type 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with the given field number. If found, fills in *output and returns true, 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // otherwise returns false and leaves *output undefined. containing_type 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // must be a fully-qualified type name. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool FindFileContainingExtension(const string& containing_type, 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_number, 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output) = 0; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Finds the tag numbers used by all known extensions of 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // extendee_type, and appends them to output in an undefined 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // order. This method is best-effort: it's not guaranteed that the 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // database will find all extensions, and it's not guaranteed that 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FindFileContainingExtension will return true on all of the found 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // numbers. Returns true if the search was successful, otherwise 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // returns false and leaves output unchanged. 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This method has a default implementation that always returns 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // false. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool FindAllExtensionNumbers(const string& extendee_type, 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output) { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(DescriptorDatabase); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A DescriptorDatabase into which you can insert files manually. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FindFileContainingSymbol() is fully-implemented. When you add a file, its 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// symbols will be indexed for this purpose. Note that the implementation 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// may return false positives, but only if it isn't possible for the symbol 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to be defined in any other file. In particular, if a file defines a symbol 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "Foo", then searching for "Foo.[anything]" will match that file. This way, 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the database does not need to aggressively index all children of a symbol. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FindFileContainingExtension() is mostly-implemented. It works if and only 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// if the original FieldDescriptorProto defining the extension has a 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// fully-qualified type name in its "extendee" field (i.e. starts with a '.'). 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the extendee is a relative name, SimpleDescriptorDatabase will not 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// attempt to resolve the type, so it will not know what type the extension is 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// extending. Therefore, calling FindFileContainingExtension() with the 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// extension's containing type will never actually find that extension. Note 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that this is an unlikely problem, as all FileDescriptorProtos created by the 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// protocol compiler (as well as ones created by calling 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FileDescriptor::CopyTo()) will always use fully-qualified names for all 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// types. You only need to worry if you are constructing FileDescriptorProtos 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// yourself, or are calling compiler::Parser directly. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT SimpleDescriptorDatabase : public DescriptorDatabase { 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SimpleDescriptorDatabase(); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SimpleDescriptorDatabase(); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds the FileDescriptorProto to the database, making a copy. The object 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can be deleted after Add() returns. Returns false if the file conflicted 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with a file already in the database, in which case an error will have 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // been written to GOOGLE_LOG(ERROR). 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Add(const FileDescriptorProto& file); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds the FileDescriptorProto to the database and takes ownership of it. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddAndOwn(const FileDescriptorProto* file); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // implements DescriptorDatabase ----------------------------------- 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileByName(const string& filename, 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingSymbol(const string& symbol_name, 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingExtension(const string& containing_type, 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_number, 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAllExtensionNumbers(const string& extendee_type, 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // So that it can use DescriptorIndex. 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class EncodedDescriptorDatabase; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // An index mapping file names, symbol names, and extension numbers to 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // some sort of values. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template <typename Value> 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class DescriptorIndex { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Helpers to recursively add particular descriptors and all their contents 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the index. 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddFile(const FileDescriptorProto& file, 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value value); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddSymbol(const string& name, Value value); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddNestedExtensions(const DescriptorProto& message_type, 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value value); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddExtension(const FieldDescriptorProto& field, 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value value); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value FindFile(const string& filename); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value FindSymbol(const string& name); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value FindExtension(const string& containing_type, int field_number); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAllExtensionNumbers(const string& containing_type, 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map<string, Value> by_name_; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map<string, Value> by_symbol_; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map<pair<string, int>, Value> by_extension_; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Invariant: The by_symbol_ map does not contain any symbols which are 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // prefixes of other symbols in the map. For example, "foo.bar" is a 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // prefix of "foo.bar.baz" (but is not a prefix of "foo.barbaz"). 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This invariant is important because it means that given a symbol name, 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we can find a key in the map which is a prefix of the symbol in O(lg n) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // time, and we know that there is at most one such key. 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The prefix lookup algorithm works like so: 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1) Find the last key in the map which is less than or equal to the 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // search key. 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2) If the found key is a prefix of the search key, then return it. 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, there is no match. 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // I am sure this algorithm has been described elsewhere, but since I 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // wasn't able to find it quickly I will instead prove that it works 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // myself. The key to the algorithm is that if a match exists, step (1) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will find it. Proof: 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1) Define the "search key" to be the key we are looking for, the "found 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // key" to be the key found in step (1), and the "match key" to be the 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // key which actually matches the serach key (i.e. the key we're trying 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to find). 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2) The found key must be less than or equal to the search key by 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // definition. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 3) The match key must also be less than or equal to the search key 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (because it is a prefix). 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 4) The match key cannot be greater than the found key, because if it 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // were, then step (1) of the algorithm would have returned the match 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // key instead (since it finds the *greatest* key which is less than or 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // equal to the search key). 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 5) Therefore, the found key must be between the match key and the search 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // key, inclusive. 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 6) Since the search key must be a sub-symbol of the match key, if it is 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not equal to the match key, then search_key[match_key.size()] must 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // be '.'. 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 7) Since '.' sorts before any other character that is valid in a symbol 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // name, then if the found key is not equal to the match key, then 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // found_key[match_key.size()] must also be '.', because any other value 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // would make it sort after the search key. 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 8) Therefore, if the found key is not equal to the match key, then the 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // found key must be a sub-symbol of the match key. However, this would 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // contradict our map invariant which says that no symbol in the map is 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a sub-symbol of any other. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 9) Therefore, the found key must match the match key. 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The above proof assumes the match key exists. In the case that the 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // match key does not exist, then step (1) will return some other symbol. 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // That symbol cannot be a super-symbol of the search key since if it were, 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // then it would be a match, and we're assuming the match key doesn't exist. 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Therefore, step 2 will correctly return no match. 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find the last entry in the by_symbol_ map whose key is less than or 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // equal to the given name. 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename map<string, Value>::iterator FindLastLessOrEqual( 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const string& name); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // True if either the arguments are equal or super_symbol identifies a 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // parent symbol of sub_symbol (e.g. "foo.bar" is a parent of 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // "foo.bar.baz", but not a parent of "foo.barbaz"). 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsSubSymbol(const string& sub_symbol, const string& super_symbol); 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true if and only if all characters in the name are alphanumerics, 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // underscores, or periods. 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ValidateSymbolName(const string& name); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DescriptorIndex<const FileDescriptorProto*> index_; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<const FileDescriptorProto*> files_to_delete_; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If file is non-NULL, copy it into *output and return true, otherwise 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // return false. 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MaybeCopy(const FileDescriptorProto* file, 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(SimpleDescriptorDatabase); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Very similar to SimpleDescriptorDatabase, but stores all the descriptors 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as raw bytes and generally tries to use as little memory as possible. 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The same caveats regarding FindFileContainingExtension() apply as with 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SimpleDescriptorDatabase. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT EncodedDescriptorDatabase : public DescriptorDatabase { 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EncodedDescriptorDatabase(); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~EncodedDescriptorDatabase(); 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds the FileDescriptorProto to the database. The descriptor is provided 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // in encoded form. The database does not make a copy of the bytes, nor 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // does it take ownership; it's up to the caller to make sure the bytes 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // remain valid for the life of the database. Returns false and logs an error 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if the bytes are not a valid FileDescriptorProto or if the file conflicted 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with a file already in the database. 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Add(const void* encoded_file_descriptor, int size); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Like Add(), but makes a copy of the data, so that the caller does not 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // need to keep it around. 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool AddCopy(const void* encoded_file_descriptor, int size); 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Like FindFileContainingSymbol but returns only the name of the file. 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindNameOfFileContainingSymbol(const string& symbol_name, 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) string* output); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // implements DescriptorDatabase ----------------------------------- 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileByName(const string& filename, 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingSymbol(const string& symbol_name, 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingExtension(const string& containing_type, 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_number, 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAllExtensionNumbers(const string& extendee_type, 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SimpleDescriptorDatabase::DescriptorIndex<pair<const void*, int> > index_; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<void*> files_to_delete_; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If encoded_file.first is non-NULL, parse the data into *output and return 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // true, otherwise return false. 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MaybeParse(pair<const void*, int> encoded_file, 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(EncodedDescriptorDatabase); 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A DescriptorDatabase that fetches files from a given pool. 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT DescriptorPoolDatabase : public DescriptorDatabase { 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DescriptorPoolDatabase(const DescriptorPool& pool); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~DescriptorPoolDatabase(); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // implements DescriptorDatabase ----------------------------------- 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileByName(const string& filename, 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingSymbol(const string& symbol_name, 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingExtension(const string& containing_type, 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_number, 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAllExtensionNumbers(const string& extendee_type, 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const DescriptorPool& pool_; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(DescriptorPoolDatabase); 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A DescriptorDatabase that wraps two or more others. It first searches the 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// first database and, if that fails, tries the second, and so on. 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT MergedDescriptorDatabase : public DescriptorDatabase { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge just two databases. The sources remain property of the caller. 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergedDescriptorDatabase(DescriptorDatabase* source1, 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DescriptorDatabase* source2); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge more than two databases. The sources remain property of the caller. 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The vector may be deleted after the constructor returns but the 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // DescriptorDatabases need to stick around. 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergedDescriptorDatabase(const vector<DescriptorDatabase*>& sources); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~MergedDescriptorDatabase(); 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // implements DescriptorDatabase ----------------------------------- 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileByName(const string& filename, 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingSymbol(const string& symbol_name, 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindFileContainingExtension(const string& containing_type, 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_number, 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FileDescriptorProto* output); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merges the results of calling all databases. Returns true iff any 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of the databases returned true. 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAllExtensionNumbers(const string& extendee_type, 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<int>* output); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<DescriptorDatabase*> sources_; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(MergedDescriptorDatabase); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace protobuf 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace google 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // GOOGLE_PROTOBUF_DESCRIPTOR_DATABASE_H__ 368