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<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
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
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 DescriptorIntPair(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 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>
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>
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>
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
341            internal DescriptorIntPair(IDescriptor descriptor, int number)
342            {
343                this.number = number;
344                this.descriptor = descriptor;
345            }
346
347            public bool Equals(DescriptorIntPair other)
348            {
349                return descriptor == other.descriptor
350                       && number == other.number;
351            }
352
353            public override bool Equals(object obj)
354            {
355                if (obj is DescriptorIntPair)
356                {
357                    return Equals((DescriptorIntPair) obj);
358                }
359                return false;
360            }
361
362            public override int GetHashCode()
363            {
364                return descriptor.GetHashCode()*((1 << 16) - 1) + number;
365            }
366        }
367    }
368}