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
33using System;
34using System.Collections.Generic;
35using System.Text;
36using System.Text.RegularExpressions;
37
38namespace 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<ObjectIntPair<IDescriptor>, FieldDescriptor> fieldsByNumber =
49            new Dictionary<ObjectIntPair<IDescriptor>, FieldDescriptor>();
50
51        private readonly IDictionary<ObjectIntPair<IDescriptor>, EnumValueDescriptor> enumValuesByNumber =
52            new Dictionary<ObjectIntPair<IDescriptor>, EnumValueDescriptor>();
53
54        private readonly HashSet<FileDescriptor> dependencies;
55
56        internal DescriptorPool(IEnumerable<FileDescriptor> dependencyFiles)
57        {
58            dependencies = new HashSet<FileDescriptor>();
59            foreach (var dependencyFile in dependencyFiles)
60            {
61                dependencies.Add(dependencyFile);
62                ImportPublicDependencies(dependencyFile);
63            }
64
65            foreach (FileDescriptor dependency in dependencyFiles)
66            {
67                AddPackage(dependency.Package, dependency);
68            }
69        }
70
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;
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>
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>
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>
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>
209        internal FieldDescriptor FindFieldByNumber(MessageDescriptor messageDescriptor, int number)
210        {
211            FieldDescriptor ret;
212            fieldsByNumber.TryGetValue(new ObjectIntPair<IDescriptor>(messageDescriptor, number), out ret);
213            return ret;
214        }
215
216        internal EnumValueDescriptor FindEnumValueByNumber(EnumDescriptor enumDescriptor, int number)
217        {
218            EnumValueDescriptor ret;
219            enumValuesByNumber.TryGetValue(new ObjectIntPair<IDescriptor>(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>
228        internal void AddFieldByNumber(FieldDescriptor field)
229        {
230            // for extensions, we use the extended type, otherwise we use the containing type
231            ObjectIntPair<IDescriptor> key = new ObjectIntPair<IDescriptor>(field.Proto.HasExtendee ? field.ExtendeeType : field.ContainingType, field.FieldNumber);
232            FieldDescriptor old;
233            if (fieldsByNumber.TryGetValue(key, out old))
234            {
235                throw new DescriptorValidationException(field, "Field number " + field.FieldNumber +
236                                                               "has already been used in \"" +
237                                                               field.ContainingType.FullName +
238                                                               "\" by field \"" + old.Name + "\".");
239            }
240            fieldsByNumber[key] = field;
241        }
242
243        /// <summary>
244        /// Adds an enum value to the enumValuesByNumber table. If an enum value
245        /// with the same type and number already exists, this method does nothing.
246        /// (This is allowed; the first value defined with the number takes precedence.)
247        /// </summary>
248        internal void AddEnumValueByNumber(EnumValueDescriptor enumValue)
249        {
250            ObjectIntPair<IDescriptor> key = new ObjectIntPair<IDescriptor>(enumValue.EnumDescriptor, enumValue.Number);
251            if (!enumValuesByNumber.ContainsKey(key))
252            {
253                enumValuesByNumber[key] = enumValue;
254            }
255        }
256
257        /// <summary>
258        /// Looks up a descriptor by name, relative to some other descriptor.
259        /// The name may be fully-qualified (with a leading '.'), partially-qualified,
260        /// or unqualified. C++-like name lookup semantics are used to search for the
261        /// matching descriptor.
262        /// </summary>
263        /// <remarks>
264        /// This isn't heavily optimized, but it's only used during cross linking anyway.
265        /// If it starts being used more widely, we should look at performance more carefully.
266        /// </remarks>
267        internal IDescriptor LookupSymbol(string name, IDescriptor relativeTo)
268        {
269            IDescriptor result;
270            if (name.StartsWith("."))
271            {
272                // Fully-qualified name.
273                result = FindSymbol<IDescriptor>(name.Substring(1));
274            }
275            else
276            {
277                // If "name" is a compound identifier, we want to search for the
278                // first component of it, then search within it for the rest.
279                int firstPartLength = name.IndexOf('.');
280                string firstPart = firstPartLength == -1 ? name : name.Substring(0, firstPartLength);
281
282                // We will search each parent scope of "relativeTo" looking for the
283                // symbol.
284                StringBuilder scopeToTry = new StringBuilder(relativeTo.FullName);
285
286                while (true)
287                {
288                    // Chop off the last component of the scope.
289
290                    int dotpos = scopeToTry.ToString().LastIndexOf(".");
291                    if (dotpos == -1)
292                    {
293                        result = FindSymbol<IDescriptor>(name);
294                        break;
295                    }
296                    else
297                    {
298                        scopeToTry.Length = dotpos + 1;
299
300                        // Append firstPart and try to find.
301                        scopeToTry.Append(firstPart);
302                        result = FindSymbol<IDescriptor>(scopeToTry.ToString());
303
304                        if (result != null)
305                        {
306                            if (firstPartLength != -1)
307                            {
308                                // We only found the first part of the symbol.  Now look for
309                                // the whole thing.  If this fails, we *don't* want to keep
310                                // searching parent scopes.
311                                scopeToTry.Length = dotpos + 1;
312                                scopeToTry.Append(name);
313                                result = FindSymbol<IDescriptor>(scopeToTry.ToString());
314                            }
315                            break;
316                        }
317
318                        // Not found.  Remove the name so we can try again.
319                        scopeToTry.Length = dotpos;
320                    }
321                }
322            }
323
324            if (result == null)
325            {
326                throw new DescriptorValidationException(relativeTo, "\"" + name + "\" is not defined.");
327            }
328            else
329            {
330                return result;
331            }
332        }
333    }
334}