// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. using System.Collections.Generic; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.Linq; using System.Runtime.CompilerServices; using System.Runtime.Versioning; namespace System.Collections.Immutable { /// /// A readonly array with O(1) indexable lookup time. /// /// The type of element stored by the array. /// /// This type has a documented contract of being exactly one reference-type field in size. /// Our own class depends on it, as well as others externally. /// IMPORTANT NOTICE FOR MAINTAINERS AND REVIEWERS: /// This type should be thread-safe. As a struct, it cannot protect its own fields /// from being changed from one thread while its members are executing on other threads /// because structs can change *in place* simply by reassigning the field containing /// this struct. Therefore it is extremely important that /// ** Every member should only dereference this ONCE. ** /// If a member needs to reference the array field, that counts as a dereference of this. /// Calling other instance members (properties or methods) also counts as dereferencing this. /// Any member that needs to use this more than once must instead /// assign this to a local variable and use that for the rest of the code instead. /// This effectively copies the one field in the struct to a local variable so that /// it is insulated from other threads. /// [DebuggerDisplay("{DebuggerDisplay,nq}")] [NonVersionable] // Applies to field layout public partial struct ImmutableArray : IEnumerable, IEquatable>, IImmutableArray { /// /// An empty (initialized) instance of . /// #pragma warning disable CA1825 // Array.Empty() doesn't exist in all configurations // Switching to Array.Empty also has a non-negligible impact on the working set memory public static readonly ImmutableArray Empty = new ImmutableArray(new T[0]); #pragma warning restore CA1825 /// /// The backing field for this instance. References to this value should never be shared with outside code. /// /// /// This would be private, but we make it internal so that our own extension methods can access it. /// [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] internal readonly T[]? array; /// /// Initializes a new instance of the struct /// *without making a defensive copy*. /// /// The array to use. May be null for "default" arrays. internal ImmutableArray(T[]? items) { this.array = items; } #region Operators /// /// Checks equality between two instances. /// /// The instance to the left of the operator. /// The instance to the right of the operator. /// true if the values' underlying arrays are reference equal; false otherwise. [NonVersionable] public static bool operator ==(ImmutableArray left, ImmutableArray right) { return left.Equals(right); } /// /// Checks inequality between two instances. /// /// The instance to the left of the operator. /// The instance to the right of the operator. /// true if the values' underlying arrays are reference not equal; false otherwise. [NonVersionable] public static bool operator !=(ImmutableArray left, ImmutableArray right) { return !left.Equals(right); } /// /// Checks equality between two instances. /// /// The instance to the left of the operator. /// The instance to the right of the operator. /// true if the values' underlying arrays are reference equal; false otherwise. public static bool operator ==(ImmutableArray? left, ImmutableArray? right) { return left.GetValueOrDefault().Equals(right.GetValueOrDefault()); } /// /// Checks inequality between two instances. /// /// The instance to the left of the operator. /// The instance to the right of the operator. /// true if the values' underlying arrays are reference not equal; false otherwise. public static bool operator !=(ImmutableArray? left, ImmutableArray? right) { return !left.GetValueOrDefault().Equals(right.GetValueOrDefault()); } #endregion /// /// Gets the element at the specified index in the read-only list. /// /// The zero-based index of the element to get. /// The element at the specified index in the read-only list. public T this[int index] { [NonVersionable] get { // We intentionally do not check this.array != null, and throw NullReferenceException // if this is called while uninitialized. // The reason for this is perf. // Length and the indexer must be absolutely trivially implemented for the JIT optimization // of removing array bounds checking to work. return this.array![index]; } } /// /// Gets a read-only reference to the element at the specified index in the read-only list. /// /// The zero-based index of the element to get a reference to. /// A read-only reference to the element at the specified index in the read-only list. public ref readonly T ItemRef(int index) { // We intentionally do not check this.array != null, and throw NullReferenceException // if this is called while uninitialized. // The reason for this is perf. // Length and the indexer must be absolutely trivially implemented for the JIT optimization // of removing array bounds checking to work. return ref this.array![index]; } /// /// Gets a value indicating whether this collection is empty. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] public bool IsEmpty { [NonVersionable] get { return this.array!.Length == 0; } } /// /// Gets the number of elements in the array. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] public int Length { [NonVersionable] get { // We intentionally do not check this.array != null, and throw NullReferenceException // if this is called while uninitialized. // The reason for this is perf. // Length and the indexer must be absolutely trivially implemented for the JIT optimization // of removing array bounds checking to work. return this.array!.Length; } } /// /// Gets a value indicating whether this struct was initialized without an actual array instance. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] public bool IsDefault { get { return this.array == null; } } /// /// Gets a value indicating whether this struct is empty or uninitialized. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] public bool IsDefaultOrEmpty { get { ImmutableArray self = this; return self.array == null || self.array.Length == 0; } } /// /// Gets an untyped reference to the array. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] Array? IImmutableArray.Array { get { return this.array; } } /// /// Gets the string to display in the debugger watches window for this instance. /// [DebuggerBrowsable(DebuggerBrowsableState.Never)] private string DebuggerDisplay { get { ImmutableArray self = this; return self.IsDefault ? "Uninitialized" : $"Length = {self.Length}"; } } /// /// Copies the contents of this array to the specified array. /// /// The array to copy to. public void CopyTo(T[] destination) { ImmutableArray self = this; self.ThrowNullRefIfNotInitialized(); Array.Copy(self.array!, destination, self.Length); } /// /// Copies the contents of this array to the specified array. /// /// The array to copy to. /// The index into the destination array to which the first copied element is written. public void CopyTo(T[] destination, int destinationIndex) { ImmutableArray self = this; self.ThrowNullRefIfNotInitialized(); Array.Copy(self.array!, 0, destination, destinationIndex, self.Length); } /// /// Copies the contents of this array to the specified array. /// /// The index into this collection of the first element to copy. /// The array to copy to. /// The index into the destination array to which the first copied element is written. /// The number of elements to copy. public void CopyTo(int sourceIndex, T[] destination, int destinationIndex, int length) { ImmutableArray self = this; self.ThrowNullRefIfNotInitialized(); Array.Copy(self.array!, sourceIndex, destination, destinationIndex, length); } /// /// Returns a builder that is populated with the same contents as this array. /// /// The new builder. public ImmutableArray.Builder ToBuilder() { ImmutableArray self = this; if (self.Length == 0) { return new Builder(); // allow the builder to create itself with a reasonable default capacity } var builder = new Builder(self.Length); builder.AddRange(self); return builder; } /// /// Returns an enumerator for the contents of the array. /// /// An enumerator. [MethodImpl(MethodImplOptions.AggressiveInlining)] public Enumerator GetEnumerator() { ImmutableArray self = this; self.ThrowNullRefIfNotInitialized(); return new Enumerator(self.array!); } /// /// Returns a hash code for this instance. /// /// /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table. /// public override int GetHashCode() { ImmutableArray self = this; return self.array == null ? 0 : self.array.GetHashCode(); } /// /// Determines whether the specified is equal to this instance. /// /// The to compare with this instance. /// /// true if the specified is equal to this instance; otherwise, false. /// public override bool Equals([NotNullWhen(true)] object? obj) { return obj is IImmutableArray other && this.array == other.Array; } /// /// Indicates whether the current object is equal to another object of the same type. /// /// An object to compare with this object. /// /// true if the current object is equal to the parameter; otherwise, false. /// [NonVersionable] public bool Equals(ImmutableArray other) { return this.array == other.array; } /// /// Initializes a new instance of the struct based on the contents /// of an existing instance, allowing a covariant static cast to efficiently reuse the existing array. /// /// The array to initialize the array with. No copy is made. /// /// Covariant upcasts from this method may be reversed by calling the /// or method. /// public static ImmutableArray< #nullable disable T #nullable restore > CastUp(ImmutableArray items) where TDerived : class?, T { return new ImmutableArray(items.array); } /// /// Initializes a new instance of the struct by casting the underlying /// array to an array of type . /// /// Thrown if the cast is illegal. public ImmutableArray< #nullable disable TOther #nullable restore > CastArray() where TOther : class? { return new ImmutableArray((TOther[])(object)array!); } /// /// Creates an immutable array for this array, cast to a different element type. /// /// The type of array element to return. /// /// A struct typed for the base element type. If the cast fails, an instance /// is returned whose property returns true. /// /// /// Arrays of derived elements types can be cast to arrays of base element types /// without reallocating the array. /// These upcasts can be reversed via this same method, casting an array of base /// element types to their derived types. However, downcasting is only successful /// when it reverses a prior upcasting operation. /// public ImmutableArray< #nullable disable TOther #nullable restore > As() where TOther : class? { return new ImmutableArray((this.array as TOther[])); } /// /// Returns an enumerator for the contents of the array. /// /// An enumerator. /// Thrown if the property returns true. IEnumerator IEnumerable.GetEnumerator() { ImmutableArray self = this; self.ThrowInvalidOperationIfNotInitialized(); return EnumeratorObject.Create(self.array!); } /// /// Returns an enumerator for the contents of the array. /// /// An enumerator. /// Thrown if the property returns true. IEnumerator IEnumerable.GetEnumerator() { ImmutableArray self = this; self.ThrowInvalidOperationIfNotInitialized(); return EnumeratorObject.Create(self.array!); } /// /// Throws a null reference exception if the array field is null. /// internal void ThrowNullRefIfNotInitialized() { // Force NullReferenceException if array is null by touching its Length. // This way of checking has a nice property of requiring very little code // and not having any conditions/branches. // In a faulting scenario we are relying on hardware to generate the fault. // And in the non-faulting scenario (most common) the check is virtually free since // if we are going to do anything with the array, we will need Length anyways // so touching it, and potentially causing a cache miss, is not going to be an // extra expense. _ = this.array!.Length; } /// /// Throws an if the field is null, i.e. the /// property returns true. The /// message specifies that the operation cannot be performed /// on a default instance of . /// /// This is intended for explicitly implemented interface method and property implementations. /// private void ThrowInvalidOperationIfNotInitialized() { if (this.IsDefault) { throw new InvalidOperationException(SR.InvalidOperationOnDefaultArray); } } } }