1 #region Copyright notice and license
2 // Protocol Buffers - Google's data interchange format
3 // Copyright 2008 Google Inc.  All rights reserved.
4 // https://developers.google.com/protocol-buffers/
5 //
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are
8 // met:
9 //
10 //     * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 //     * Redistributions in binary form must reproduce the above
13 // copyright notice, this list of conditions and the following disclaimer
14 // in the documentation and/or other materials provided with the
15 // distribution.
16 //     * Neither the name of Google Inc. nor the names of its
17 // contributors may be used to endorse or promote products derived from
18 // this software without specific prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #endregion
32 
33 using System;
34 using System.Collections.Generic;
35 using System.Text;
36 using System.Text.RegularExpressions;
37 
38 namespace Google.Protobuf.Reflection
39 {
40     /// <summary>
41     /// Contains lookup tables containing all the descriptors defined in a particular file.
42     /// </summary>
43     internal sealed class DescriptorPool
44     {
45         private readonly IDictionary<string, IDescriptor> descriptorsByName =
46             new Dictionary<string, IDescriptor>();
47 
48         private readonly IDictionary<DescriptorIntPair, FieldDescriptor> fieldsByNumber =
49             new Dictionary<DescriptorIntPair, FieldDescriptor>();
50 
51         private readonly IDictionary<DescriptorIntPair, EnumValueDescriptor> enumValuesByNumber =
52             new Dictionary<DescriptorIntPair, EnumValueDescriptor>();
53 
54         private readonly HashSet<FileDescriptor> dependencies;
55 
DescriptorPool(FileDescriptor[] dependencyFiles)56         internal DescriptorPool(FileDescriptor[] dependencyFiles)
57         {
58             dependencies = new HashSet<FileDescriptor>();
59             for (int i = 0; i < dependencyFiles.Length; i++)
60             {
61                 dependencies.Add(dependencyFiles[i]);
62                 ImportPublicDependencies(dependencyFiles[i]);
63             }
64 
65             foreach (FileDescriptor dependency in dependencyFiles)
66             {
67                 AddPackage(dependency.Package, dependency);
68             }
69         }
70 
ImportPublicDependencies(FileDescriptor file)71         private void ImportPublicDependencies(FileDescriptor file)
72         {
73             foreach (FileDescriptor dependency in file.PublicDependencies)
74             {
75                 if (dependencies.Add(dependency))
76                 {
77                     ImportPublicDependencies(dependency);
78                 }
79             }
80         }
81 
82         /// <summary>
83         /// Finds a symbol of the given name within the pool.
84         /// </summary>
85         /// <typeparam name="T">The type of symbol to look for</typeparam>
86         /// <param name="fullName">Fully-qualified name to look up</param>
87         /// <returns>The symbol with the given name and type,
88         /// or null if the symbol doesn't exist or has the wrong type</returns>
89         internal T FindSymbol<T>(string fullName) where T : class
90         {
91             IDescriptor result;
descriptorsByName.TryGetValue(fullName, out result)92             descriptorsByName.TryGetValue(fullName, out result);
93             T descriptor = result as T;
94             if (descriptor != null)
95             {
96                 return descriptor;
97             }
98 
99             // dependencies contains direct dependencies and any *public* dependencies
100             // of those dependencies (transitively)... so we don't need to recurse here.
101             foreach (FileDescriptor dependency in dependencies)
102             {
103                 dependency.DescriptorPool.descriptorsByName.TryGetValue(fullName, out result);
104                 descriptor = result as T;
105                 if (descriptor != null)
106                 {
107                     return descriptor;
108                 }
109             }
110 
111             return null;
112         }
113 
114         /// <summary>
115         /// Adds a package to the symbol tables. If a package by the same name
116         /// already exists, that is fine, but if some other kind of symbol
117         /// exists under the same name, an exception is thrown. If the package
118         /// has multiple components, this also adds the parent package(s).
119         /// </summary>
AddPackage(string fullName, FileDescriptor file)120         internal void AddPackage(string fullName, FileDescriptor file)
121         {
122             int dotpos = fullName.LastIndexOf('.');
123             String name;
124             if (dotpos != -1)
125             {
126                 AddPackage(fullName.Substring(0, dotpos), file);
127                 name = fullName.Substring(dotpos + 1);
128             }
129             else
130             {
131                 name = fullName;
132             }
133 
134             IDescriptor old;
135             if (descriptorsByName.TryGetValue(fullName, out old))
136             {
137                 if (!(old is PackageDescriptor))
138                 {
139                     throw new DescriptorValidationException(file,
140                                                             "\"" + name +
141                                                             "\" is already defined (as something other than a " +
142                                                             "package) in file \"" + old.File.Name + "\".");
143                 }
144             }
145             descriptorsByName[fullName] = new PackageDescriptor(name, fullName, file);
146         }
147 
148         /// <summary>
149         /// Adds a symbol to the symbol table.
150         /// </summary>
151         /// <exception cref="DescriptorValidationException">The symbol already existed
152         /// in the symbol table.</exception>
AddSymbol(IDescriptor descriptor)153         internal void AddSymbol(IDescriptor descriptor)
154         {
155             ValidateSymbolName(descriptor);
156             String fullName = descriptor.FullName;
157 
158             IDescriptor old;
159             if (descriptorsByName.TryGetValue(fullName, out old))
160             {
161                 int dotPos = fullName.LastIndexOf('.');
162                 string message;
163                 if (descriptor.File == old.File)
164                 {
165                     if (dotPos == -1)
166                     {
167                         message = "\"" + fullName + "\" is already defined.";
168                     }
169                     else
170                     {
171                         message = "\"" + fullName.Substring(dotPos + 1) + "\" is already defined in \"" +
172                                   fullName.Substring(0, dotPos) + "\".";
173                     }
174                 }
175                 else
176                 {
177                     message = "\"" + fullName + "\" is already defined in file \"" + old.File.Name + "\".";
178                 }
179                 throw new DescriptorValidationException(descriptor, message);
180             }
181             descriptorsByName[fullName] = descriptor;
182         }
183 
184         private static readonly Regex ValidationRegex = new Regex("^[_A-Za-z][_A-Za-z0-9]*$",
185                                                                   FrameworkPortability.CompiledRegexWhereAvailable);
186 
187         /// <summary>
188         /// Verifies that the descriptor's name is valid (i.e. it contains
189         /// only letters, digits and underscores, and does not start with a digit).
190         /// </summary>
191         /// <param name="descriptor"></param>
ValidateSymbolName(IDescriptor descriptor)192         private static void ValidateSymbolName(IDescriptor descriptor)
193         {
194             if (descriptor.Name == "")
195             {
196                 throw new DescriptorValidationException(descriptor, "Missing name.");
197             }
198             if (!ValidationRegex.IsMatch(descriptor.Name))
199             {
200                 throw new DescriptorValidationException(descriptor,
201                                                         "\"" + descriptor.Name + "\" is not a valid identifier.");
202             }
203         }
204 
205         /// <summary>
206         /// Returns the field with the given number in the given descriptor,
207         /// or null if it can't be found.
208         /// </summary>
FindFieldByNumber(MessageDescriptor messageDescriptor, int number)209         internal FieldDescriptor FindFieldByNumber(MessageDescriptor messageDescriptor, int number)
210         {
211             FieldDescriptor ret;
212             fieldsByNumber.TryGetValue(new DescriptorIntPair(messageDescriptor, number), out ret);
213             return ret;
214         }
215 
FindEnumValueByNumber(EnumDescriptor enumDescriptor, int number)216         internal EnumValueDescriptor FindEnumValueByNumber(EnumDescriptor enumDescriptor, int number)
217         {
218             EnumValueDescriptor ret;
219             enumValuesByNumber.TryGetValue(new DescriptorIntPair(enumDescriptor, number), out ret);
220             return ret;
221         }
222 
223         /// <summary>
224         /// Adds a field to the fieldsByNumber table.
225         /// </summary>
226         /// <exception cref="DescriptorValidationException">A field with the same
227         /// containing type and number already exists.</exception>
AddFieldByNumber(FieldDescriptor field)228         internal void AddFieldByNumber(FieldDescriptor field)
229         {
230             DescriptorIntPair key = new DescriptorIntPair(field.ContainingType, field.FieldNumber);
231             FieldDescriptor old;
232             if (fieldsByNumber.TryGetValue(key, out old))
233             {
234                 throw new DescriptorValidationException(field, "Field number " + field.FieldNumber +
235                                                                "has already been used in \"" +
236                                                                field.ContainingType.FullName +
237                                                                "\" by field \"" + old.Name + "\".");
238             }
239             fieldsByNumber[key] = field;
240         }
241 
242         /// <summary>
243         /// Adds an enum value to the enumValuesByNumber table. If an enum value
244         /// with the same type and number already exists, this method does nothing.
245         /// (This is allowed; the first value defined with the number takes precedence.)
246         /// </summary>
AddEnumValueByNumber(EnumValueDescriptor enumValue)247         internal void AddEnumValueByNumber(EnumValueDescriptor enumValue)
248         {
249             DescriptorIntPair key = new DescriptorIntPair(enumValue.EnumDescriptor, enumValue.Number);
250             if (!enumValuesByNumber.ContainsKey(key))
251             {
252                 enumValuesByNumber[key] = enumValue;
253             }
254         }
255 
256         /// <summary>
257         /// Looks up a descriptor by name, relative to some other descriptor.
258         /// The name may be fully-qualified (with a leading '.'), partially-qualified,
259         /// or unqualified. C++-like name lookup semantics are used to search for the
260         /// matching descriptor.
261         /// </summary>
262         /// <remarks>
263         /// This isn't heavily optimized, but it's only used during cross linking anyway.
264         /// If it starts being used more widely, we should look at performance more carefully.
265         /// </remarks>
LookupSymbol(string name, IDescriptor relativeTo)266         internal IDescriptor LookupSymbol(string name, IDescriptor relativeTo)
267         {
268             IDescriptor result;
269             if (name.StartsWith("."))
270             {
271                 // Fully-qualified name.
272                 result = FindSymbol<IDescriptor>(name.Substring(1));
273             }
274             else
275             {
276                 // If "name" is a compound identifier, we want to search for the
277                 // first component of it, then search within it for the rest.
278                 int firstPartLength = name.IndexOf('.');
279                 string firstPart = firstPartLength == -1 ? name : name.Substring(0, firstPartLength);
280 
281                 // We will search each parent scope of "relativeTo" looking for the
282                 // symbol.
283                 StringBuilder scopeToTry = new StringBuilder(relativeTo.FullName);
284 
285                 while (true)
286                 {
287                     // Chop off the last component of the scope.
288 
289                     int dotpos = scopeToTry.ToString().LastIndexOf(".");
290                     if (dotpos == -1)
291                     {
292                         result = FindSymbol<IDescriptor>(name);
293                         break;
294                     }
295                     else
296                     {
297                         scopeToTry.Length = dotpos + 1;
298 
299                         // Append firstPart and try to find.
300                         scopeToTry.Append(firstPart);
301                         result = FindSymbol<IDescriptor>(scopeToTry.ToString());
302 
303                         if (result != null)
304                         {
305                             if (firstPartLength != -1)
306                             {
307                                 // We only found the first part of the symbol.  Now look for
308                                 // the whole thing.  If this fails, we *don't* want to keep
309                                 // searching parent scopes.
310                                 scopeToTry.Length = dotpos + 1;
311                                 scopeToTry.Append(name);
312                                 result = FindSymbol<IDescriptor>(scopeToTry.ToString());
313                             }
314                             break;
315                         }
316 
317                         // Not found.  Remove the name so we can try again.
318                         scopeToTry.Length = dotpos;
319                     }
320                 }
321             }
322 
323             if (result == null)
324             {
325                 throw new DescriptorValidationException(relativeTo, "\"" + name + "\" is not defined.");
326             }
327             else
328             {
329                 return result;
330             }
331         }
332 
333         /// <summary>
334         /// Struct used to hold the keys for the fieldByNumber table.
335         /// </summary>
336         private struct DescriptorIntPair : IEquatable<DescriptorIntPair>
337         {
338             private readonly int number;
339             private readonly IDescriptor descriptor;
340 
DescriptorIntPairGoogle.Protobuf.Reflection.DescriptorPool.DescriptorIntPair341             internal DescriptorIntPair(IDescriptor descriptor, int number)
342             {
343                 this.number = number;
344                 this.descriptor = descriptor;
345             }
346 
EqualsGoogle.Protobuf.Reflection.DescriptorPool.DescriptorIntPair347             public bool Equals(DescriptorIntPair other)
348             {
349                 return descriptor == other.descriptor
350                        && number == other.number;
351             }
352 
EqualsGoogle.Protobuf.Reflection.DescriptorPool.DescriptorIntPair353             public override bool Equals(object obj)
354             {
355                 if (obj is DescriptorIntPair)
356                 {
357                     return Equals((DescriptorIntPair) obj);
358                 }
359                 return false;
360             }
361 
GetHashCodeGoogle.Protobuf.Reflection.DescriptorPool.DescriptorIntPair362             public override int GetHashCode()
363             {
364                 return descriptor.GetHashCode()*((1 << 16) - 1) + number;
365             }
366         }
367     }
368 }