1 // Copyright (c) Microsoft. All rights reserved. 2 // Licensed under the MIT license. See LICENSE file in the project root for full license information. 3 //----------------------------------------------------------------------- 4 // </copyright> 5 // <summary>Collection of instance or definition items</summary> 6 //----------------------------------------------------------------------- 7 8 using System; 9 using System.Collections; 10 using System.Collections.Generic; 11 using System.Diagnostics; 12 using ObjectModel = System.Collections.ObjectModel; 13 using Microsoft.Build.Evaluation; 14 using Microsoft.Build.Shared; 15 using Microsoft.Build.Internal; 16 17 namespace Microsoft.Build.Collections 18 { 19 /// <summary> 20 /// Collection of items that allows a list of all items of a specified type to be 21 /// retrieved in O(1), and specific items to be added, removed, or checked for in O(1). 22 /// All items of a particular type can also be removed in O(1). 23 /// Items are ordered with respect to all other items of their type. 24 /// </summary> 25 /// <remarks> 26 /// Really a Dictionary<string, ICollection<T>> where the key (the item type) is obtained from IKeyed.Key 27 /// Is not observable, so if clients wish to observe modifications they must mediate them themselves and 28 /// either not expose this collection or expose it through a readonly wrapper. 29 /// At various places in this class locks are taken on the backing collection. The reason for this is to allow 30 /// this class to be asynchronously enumerated. This is accomplished by the CopyOnReadEnumerable which will 31 /// lock the backing collection when it does its deep cloning. This prevents asynchronous access from corrupting 32 /// the state of the enumeration until the collection has been fully copied. 33 /// </remarks> 34 /// <typeparam name="T">Item class type to store</typeparam> 35 [DebuggerDisplay("#Item types={ItemTypes.Count} #Items={Count}")] 36 internal sealed class ItemDictionary<T> : IEnumerable<T>, IItemProvider<T> 37 where T : class, IKeyed, IItem 38 { 39 /// <summary> 40 /// Dictionary of item lists used as a backing store. 41 /// An empty list should never be stored in here unless it is an empty marker. 42 /// See <see cref="AddEmptyMarker">AddEmptyMarker</see>. 43 /// This collection provides quick access to the ordered set of items of a particular type. 44 /// </summary> 45 private readonly Dictionary<string, LinkedList<T>> _itemLists; 46 47 /// <summary> 48 /// Dictionary of items in the collection, to speed up Contains, 49 /// Remove, and Replace. For those operations, we look up here, 50 /// then modify the other dictionary to match. 51 /// </summary> 52 private readonly Dictionary<T, LinkedListNode<T>> _nodes; 53 54 /// <summary> 55 /// Constructor for an empty collection. 56 /// </summary> ItemDictionary()57 internal ItemDictionary() 58 { 59 // Tracing.Record("new item dictionary"); 60 _itemLists = new Dictionary<string, LinkedList<T>>(MSBuildNameIgnoreCaseComparer.Default); 61 _nodes = new Dictionary<T, LinkedListNode<T>>(); 62 } 63 64 /// <summary> 65 /// Constructor for an empty collection taking an initial capacity 66 /// for the number of distinct item types 67 /// </summary> ItemDictionary(int initialItemTypesCapacity, int initialItemsCapacity = 0)68 internal ItemDictionary(int initialItemTypesCapacity, int initialItemsCapacity = 0) 69 { 70 // Tracing.Record("new item dictionary"); 71 _itemLists = new Dictionary<string, LinkedList<T>>(initialItemTypesCapacity, MSBuildNameIgnoreCaseComparer.Default); 72 _nodes = new Dictionary<T, LinkedListNode<T>>(initialItemsCapacity); 73 } 74 75 /// <summary> 76 /// Constructor for an collection holding items from a specified enumerable. 77 /// </summary> ItemDictionary(IEnumerable<T> items)78 internal ItemDictionary(IEnumerable<T> items) 79 { 80 // Tracing.Record("new item dictionary"); 81 _itemLists = new Dictionary<string, LinkedList<T>>(MSBuildNameIgnoreCaseComparer.Default); 82 _nodes = new Dictionary<T, LinkedListNode<T>>(); 83 ImportItems(items); 84 } 85 86 /// <summary> 87 /// Number of items in total, for debugging purposes. 88 /// </summary> 89 internal int Count 90 { 91 get { return _nodes.Count; } 92 } 93 94 /// <summary> 95 /// Get the item types that have at least one item in this collection 96 /// </summary> 97 /// <remarks> 98 /// KeyCollection<K> is already a read only collection, so no protection 99 /// is necessary. 100 /// </remarks> 101 internal ICollection<string> ItemTypes 102 { 103 get 104 { 105 lock (_itemLists) 106 { 107 return _itemLists.Keys; 108 } 109 } 110 } 111 112 /// <summary> 113 /// Returns the item list for a particular item type, 114 /// creating and adding a new item list if necessary. 115 /// Does not throw if there are no items of this type. 116 /// This is a read-only list. 117 /// If the result is not empty it is a live list. 118 /// Use AddItem or RemoveItem to modify items in this project. 119 /// Using the return value from this in a multithreaded situation is unsafe. 120 /// </summary> 121 internal ICollection<T> this[string itemtype] 122 { 123 get 124 { 125 LinkedList<T> list; 126 lock (_itemLists) 127 { 128 if (!_itemLists.TryGetValue(itemtype, out list)) 129 { 130 return Array.Empty<T>(); 131 } 132 } 133 134 return new ReadOnlyCollection<T>(list); 135 } 136 } 137 138 /// <summary> 139 /// Empty the collection 140 /// </summary> Clear()141 public void Clear() 142 { 143 lock (_itemLists) 144 { 145 foreach (ICollection<T> list in _itemLists.Values) 146 { 147 list.Clear(); 148 } 149 150 _itemLists.Clear(); 151 _nodes.Clear(); 152 } 153 } 154 155 /// <summary> 156 /// Returns an enumerable which copies the underlying data on read. 157 /// </summary> GetCopyOnReadEnumerable()158 public IEnumerable<T> GetCopyOnReadEnumerable() 159 { 160 return new CopyOnReadEnumerable<T>(this, _itemLists); 161 } 162 163 /// <summary> 164 /// Gets an enumerator over the items in the collection 165 /// </summary> GetEnumerator()166 public IEnumerator<T> GetEnumerator() 167 { 168 return new ItemDictionary<T>.Enumerator(_itemLists.Values); 169 } 170 171 /// <summary> 172 /// Get an enumerator over entries 173 /// </summary> IEnumerable.GetEnumerator()174 IEnumerator IEnumerable.GetEnumerator() 175 { 176 return _itemLists.GetEnumerator(); 177 } 178 179 #region ItemDictionary<T> Members 180 181 /// <summary> 182 /// Returns all of the items for the specified type. 183 /// If there are no items of this type, returns an empty list. 184 /// Using the return from this method in a multithreaded scenario is unsafe. 185 /// </summary> 186 /// <param name="itemType">The item type to return</param> 187 /// <returns>The list of matching items.</returns> GetItems(string itemType)188 public ICollection<T> GetItems(string itemType) 189 { 190 ICollection<T> result = this[itemType]; 191 192 return result ?? Array.Empty<T>(); 193 } 194 195 #endregion 196 197 /// <summary> 198 /// Whether the provided item is in this table or not. 199 /// </summary> Contains(T projectItem)200 internal bool Contains(T projectItem) 201 { 202 lock (_itemLists) 203 { 204 return _nodes.ContainsKey(projectItem); 205 } 206 } 207 208 /// <summary> 209 /// Add a new item to the collection, at the 210 /// end of the list of other items with its key. 211 /// </summary> Add(T projectItem)212 internal void Add(T projectItem) 213 { 214 lock (_itemLists) 215 { 216 LinkedList<T> list; 217 if (!_itemLists.TryGetValue(projectItem.Key, out list)) 218 { 219 list = new LinkedList<T>(); 220 _itemLists[projectItem.Key] = list; 221 } 222 223 LinkedListNode<T> node = list.AddLast(projectItem); 224 _nodes.Add(projectItem, node); 225 } 226 } 227 228 /// <summary> 229 /// Removes an item, if it is in the collection. 230 /// Returns true if it was found, otherwise false. 231 /// </summary> 232 /// <remarks> 233 /// If a list is emptied, removes the list from the enclosing collection 234 /// so it can be garbage collected. 235 /// </remarks> Remove(T projectItem)236 internal bool Remove(T projectItem) 237 { 238 lock (_itemLists) 239 { 240 LinkedListNode<T> node; 241 if (!_nodes.TryGetValue(projectItem, out node)) 242 { 243 return false; 244 } 245 246 LinkedList<T> list = node.List; 247 list.Remove(node); 248 _nodes.Remove(projectItem); 249 250 // Save memory 251 if (list.Count == 0) 252 { 253 _itemLists.Remove(projectItem.Key); 254 } 255 256 return true; 257 } 258 } 259 260 /// <summary> 261 /// Replaces an exsting item with a new item. This is necessary to preserve the original ordering semantics of Lookup.GetItems 262 /// when items with metadata modifications are being returned. See Dev10 bug 480737. 263 /// If the item is not found, does nothing. 264 /// </summary> 265 /// <param name="existingItem">The item to be replaced.</param> 266 /// <param name="newItem">The replacement item.</param> Replace(T existingItem, T newItem)267 internal void Replace(T existingItem, T newItem) 268 { 269 ErrorUtilities.VerifyThrow(existingItem.Key == newItem.Key, "Cannot replace an item {0} with an item {1} with a different name.", existingItem.Key, newItem.Key); 270 lock (_itemLists) 271 { 272 LinkedListNode<T> node; 273 if (_nodes.TryGetValue(existingItem, out node)) 274 { 275 node.Value = newItem; 276 _nodes.Remove(existingItem); 277 _nodes.Add(newItem, node); 278 } 279 } 280 } 281 282 /// <summary> 283 /// Add the set of items specified to this dictionary 284 /// </summary> 285 /// <param name="other">An enumerator over the items to remove.</param> ImportItems(IEnumerable<T> other)286 internal void ImportItems(IEnumerable<T> other) 287 { 288 foreach (T item in other) 289 { 290 Add(item); 291 } 292 } 293 294 /// <summary> 295 /// Add the set of items specified, all sharing an item type, to this dictionary. 296 /// </summary> 297 /// <comment> 298 /// This is a little faster than ImportItems where all the items have the same item type. 299 /// </comment> ImportItemsOfType(string itemType, IEnumerable<T> items)300 internal void ImportItemsOfType(string itemType, IEnumerable<T> items) 301 { 302 lock (_itemLists) 303 { 304 LinkedList<T> list; 305 if (!_itemLists.TryGetValue(itemType, out list)) 306 { 307 list = new LinkedList<T>(); 308 _itemLists[itemType] = list; 309 } 310 311 foreach (T item in items) 312 { 313 #if DEBUG 314 // Debug only: hot code path 315 ErrorUtilities.VerifyThrow(String.Equals(itemType, item.Key, StringComparison.OrdinalIgnoreCase), "Item type mismatch"); 316 #endif 317 LinkedListNode<T> node = list.AddLast(item); 318 _nodes.Add(item, node); 319 } 320 } 321 } 322 323 /// <summary> 324 /// Remove the set of items specified from this dictionary 325 /// </summary> 326 /// <param name="other">An enumerator over the items to remove.</param> RemoveItems(IEnumerable<T> other)327 internal void RemoveItems(IEnumerable<T> other) 328 { 329 foreach (T item in other) 330 { 331 Remove(item); 332 } 333 } 334 335 /// <summary> 336 /// Special method used for batching buckets. 337 /// Adds an explicit marker indicating there are no items for the specified item type. 338 /// In the general case, this is redundant, but batching buckets use this to indicate that they are 339 /// batching over the item type, but their bucket does not contain items of that type. 340 /// See <see cref="HasEmptyMarker">HasEmptyMarker</see>. 341 /// </summary> AddEmptyMarker(string itemType)342 internal void AddEmptyMarker(string itemType) 343 { 344 lock (_itemLists) 345 { 346 ErrorUtilities.VerifyThrow(!_itemLists.ContainsKey(itemType), "Should be none"); 347 _itemLists.Add(itemType, new LinkedList<T>()); 348 } 349 } 350 351 /// <summary> 352 /// Special method used for batching buckets. 353 /// Lookup can call this to see whether there was an explicit marker placed indicating that 354 /// there are no items of this type. See comment on <see cref="AddEmptyMarker">AddEmptyMarker</see>. 355 /// </summary> HasEmptyMarker(string itemType)356 internal bool HasEmptyMarker(string itemType) 357 { 358 lock (_itemLists) 359 { 360 LinkedList<T> list; 361 362 if (_itemLists.TryGetValue(itemType, out list) && list.Count == 0) 363 { 364 return true; 365 } 366 367 return false; 368 } 369 } 370 371 /// <summary> 372 /// Custom enumerator that allows enumeration over all the items in the collection 373 /// as though they were in a single list. 374 /// All items of a type are returned consecutively in their correct order. 375 /// However the order in which item types are returned is not defined. 376 /// </summary> 377 private class Enumerator : IEnumerator<T>, IDisposable 378 { 379 /// <summary> 380 /// Enumerator over lists 381 /// </summary> 382 private IEnumerator<ICollection<T>> _listEnumerator; 383 384 /// <summary> 385 /// Enumerator over items in the current list 386 /// </summary> 387 private IEnumerator<T> _itemEnumerator; 388 389 /// <summary> 390 /// Constructs an item enumerator over a list enumerator 391 /// </summary> Enumerator(IEnumerable<ICollection<T>> listEnumerable)392 internal Enumerator(IEnumerable<ICollection<T>> listEnumerable) 393 { 394 _listEnumerator = listEnumerable.GetEnumerator(); // Now get the enumerator, since we now have the lock. 395 _itemEnumerator = null; // Must assign all struct fields first 396 _itemEnumerator = GetNextItemEnumerator(); 397 } 398 399 /// <summary> 400 /// Finalizer 401 /// </summary> ~Enumerator()402 ~Enumerator() 403 { 404 Dispose(false); 405 } 406 407 /// <summary> 408 /// Get the current item 409 /// </summary> 410 public T Current 411 { 412 get 413 { 414 // Undefined if enumerator is before or after collection: we return null 415 return _itemEnumerator != null ? _itemEnumerator.Current : null; 416 } 417 } 418 419 /// <summary> 420 /// Implementation of IEnumerator.Current, which unlike IEnumerator>T<.Current throws 421 /// if there is no current object 422 /// </summary> 423 object IEnumerator.Current 424 { 425 get 426 { 427 if (_itemEnumerator != null) 428 { 429 return _itemEnumerator.Current; 430 } 431 432 // will throw InvalidOperationException, per IEnumerator contract 433 return ((IEnumerator)_listEnumerator).Current; 434 } 435 } 436 437 /// <summary> 438 /// Move to the next object if any, 439 /// otherwise returns false 440 /// </summary> MoveNext()441 public bool MoveNext() 442 { 443 if (_itemEnumerator == null) 444 { 445 return false; 446 } 447 448 while (!_itemEnumerator.MoveNext()) 449 { 450 _itemEnumerator = GetNextItemEnumerator(); 451 452 if (_itemEnumerator == null) 453 { 454 return false; 455 } 456 } 457 458 return true; 459 } 460 461 /// <summary> 462 /// Reset the enumerator 463 /// </summary> Reset()464 public void Reset() 465 { 466 if (_itemEnumerator != null) 467 { 468 _itemEnumerator.Reset(); 469 } 470 471 _listEnumerator.Reset(); 472 } 473 474 /// <summary> 475 /// IDisposable implementation. 476 /// </summary> Dispose()477 public void Dispose() 478 { 479 Dispose(true); 480 GC.SuppressFinalize(this); 481 } 482 483 /// <summary> 484 /// The real disposer. 485 /// </summary> Dispose(bool disposing)486 protected virtual void Dispose(bool disposing) 487 { 488 if (disposing) 489 { 490 if (_listEnumerator != null) 491 { 492 if (_itemEnumerator != null) 493 { 494 _itemEnumerator.Dispose(); 495 _itemEnumerator = null; 496 } 497 498 _listEnumerator.Dispose(); 499 _listEnumerator = null; 500 } 501 } 502 } 503 504 /// <summary> 505 /// Get an item enumerator over the next list with items in it 506 /// </summary> GetNextItemEnumerator()507 private IEnumerator<T> GetNextItemEnumerator() 508 { 509 do 510 { 511 if (!_listEnumerator.MoveNext()) 512 { 513 return null; 514 } 515 } 516 while (_listEnumerator.Current == null || _listEnumerator.Current.Count == 0); 517 518 return _listEnumerator.Current.GetEnumerator(); 519 } 520 } 521 } 522 } 523