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