1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Collections.Generic;
6 
7 namespace System.Dynamic
8 {
9     /// <summary>
10     /// Represents a dynamically assigned class.  Expando objects which share the same
11     /// members will share the same class.  Classes are dynamically assigned as the
12     /// expando object gains members.
13     /// </summary>
14     internal class ExpandoClass
15     {
16         private readonly string[] _keys;                            // list of names associated with each element in the data array, sorted
17         private readonly int _hashCode;                             // pre-calculated hash code of all the keys the class contains
18         private Dictionary<int, List<WeakReference>> _transitions;  // cached transitions
19 
20         private const int EmptyHashCode = 6551;                     // hash code of the empty ExpandoClass.
21 
22         internal static readonly ExpandoClass Empty = new ExpandoClass();    // The empty Expando class - all Expando objects start off w/ this class.
23 
24         /// <summary>
25         /// Constructs the empty ExpandoClass.  This is the class used when an
26         /// empty Expando object is initially constructed.
27         /// </summary>
ExpandoClass()28         internal ExpandoClass()
29         {
30             _hashCode = EmptyHashCode;
31             _keys = Array.Empty<string>();
32         }
33 
34         /// <summary>
35         /// Constructs a new ExpandoClass that can hold onto the specified keys.  The
36         /// keys must be sorted ordinally.  The hash code must be precalculated for
37         /// the keys.
38         /// </summary>
ExpandoClass(string[] keys, int hashCode)39         internal ExpandoClass(string[] keys, int hashCode)
40         {
41             _hashCode = hashCode;
42             _keys = keys;
43         }
44 
45         /// <summary>
46         /// Finds or creates a new ExpandoClass given the existing set of keys
47         /// in this ExpandoClass plus the new key to be added. Members in an
48         /// ExpandoClass are always stored case sensitively.
49         /// </summary>
FindNewClass(string newKey)50         internal ExpandoClass FindNewClass(string newKey)
51         {
52             // just XOR the newKey hash code
53             int hashCode = _hashCode ^ newKey.GetHashCode();
54 
55             lock (this)
56             {
57                 List<WeakReference> infos = GetTransitionList(hashCode);
58 
59                 for (int i = 0; i < infos.Count; i++)
60                 {
61                     ExpandoClass klass = infos[i].Target as ExpandoClass;
62                     if (klass == null)
63                     {
64                         infos.RemoveAt(i);
65                         i--;
66                         continue;
67                     }
68 
69                     if (string.Equals(klass._keys[klass._keys.Length - 1], newKey, StringComparison.Ordinal))
70                     {
71                         // the new key is the key we added in this transition
72                         return klass;
73                     }
74                 }
75 
76                 // no applicable transition, create a new one
77                 string[] keys = new string[_keys.Length + 1];
78                 Array.Copy(_keys, 0, keys, 0, _keys.Length);
79                 keys[_keys.Length] = newKey;
80                 ExpandoClass ec = new ExpandoClass(keys, hashCode);
81 
82                 infos.Add(new WeakReference(ec));
83                 return ec;
84             }
85         }
86 
87         /// <summary>
88         /// Gets the lists of transitions that are valid from this ExpandoClass
89         /// to an ExpandoClass whose keys hash to the appropriate hash code.
90         /// </summary>
GetTransitionList(int hashCode)91         private List<WeakReference> GetTransitionList(int hashCode)
92         {
93             if (_transitions == null)
94             {
95                 _transitions = new Dictionary<int, List<WeakReference>>();
96             }
97 
98             List<WeakReference> infos;
99             if (!_transitions.TryGetValue(hashCode, out infos))
100             {
101                 _transitions[hashCode] = infos = new List<WeakReference>();
102             }
103 
104             return infos;
105         }
106 
107         /// <summary>
108         /// Gets the index at which the value should be stored for the specified name.
109         /// </summary>
GetValueIndex(string name, bool caseInsensitive, ExpandoObject obj)110         internal int GetValueIndex(string name, bool caseInsensitive, ExpandoObject obj)
111         {
112             if (caseInsensitive)
113             {
114                 return GetValueIndexCaseInsensitive(name, obj);
115             }
116             else
117             {
118                 return GetValueIndexCaseSensitive(name);
119             }
120         }
121 
122         /// <summary>
123         /// Gets the index at which the value should be stored for the specified name
124         /// case sensitively. Returns the index even if the member is marked as deleted.
125         /// </summary>
GetValueIndexCaseSensitive(string name)126         internal int GetValueIndexCaseSensitive(string name)
127         {
128             for (int i = 0; i < _keys.Length; i++)
129             {
130                 if (string.Equals(
131                     _keys[i],
132                     name,
133                     StringComparison.Ordinal))
134                 {
135                     return i;
136                 }
137             }
138             return ExpandoObject.NoMatch;
139         }
140 
141         /// <summary>
142         /// Gets the index at which the value should be stored for the specified name,
143         /// the method is only used in the case-insensitive case.
144         /// </summary>
145         /// <param name="name">the name of the member</param>
146         /// <param name="obj">The ExpandoObject associated with the class
147         /// that is used to check if a member has been deleted.</param>
148         /// <returns>
149         /// the exact match if there is one
150         /// if there is exactly one member with case insensitive match, return it
151         /// otherwise we throw AmbiguousMatchException.
152         /// </returns>
GetValueIndexCaseInsensitive(string name, ExpandoObject obj)153         private int GetValueIndexCaseInsensitive(string name, ExpandoObject obj)
154         {
155             int caseInsensitiveMatch = ExpandoObject.NoMatch; //the location of the case-insensitive matching member
156             lock (obj.LockObject)
157             {
158                 for (int i = _keys.Length - 1; i >= 0; i--)
159                 {
160                     if (string.Equals(
161                         _keys[i],
162                         name,
163                         StringComparison.OrdinalIgnoreCase))
164                     {
165                         //if the matching member is deleted, continue searching
166                         if (!obj.IsDeletedMember(i))
167                         {
168                             if (caseInsensitiveMatch == ExpandoObject.NoMatch)
169                             {
170                                 caseInsensitiveMatch = i;
171                             }
172                             else
173                             {
174                                 //Ambiguous match, stop searching
175                                 return ExpandoObject.AmbiguousMatchFound;
176                             }
177                         }
178                     }
179                 }
180             }
181             //There is exactly one member with case insensitive match.
182             return caseInsensitiveMatch;
183         }
184 
185         /// <summary>
186         /// Gets the names of the keys that can be stored in the Expando class.  The
187         /// list is sorted ordinally.
188         /// </summary>
189         internal string[] Keys => _keys;
190     }
191 }
192