From 29d7b6dee194e71bc5c98eec962bcac39bee8bb7 Mon Sep 17 00:00:00 2001 From: David Wrighton Date: Tue, 7 Feb 2017 09:23:15 -0800 Subject: Factor ImmutableArray into many files (#15526) * Factor ImmutableArray into many files - Break immutable array (an enumerable, immutable, array) into a core component - And a bunch of algorithm components which represents algorithms on the array - And a bunch of components which represent creation of new related immutable arrays - The purpose of this work is to make it possible to source include the core of immutable array into a component which cannot depend on high level apis such as LINQ, SortedDictionary, etc. (All api use must be satisfied by System.Private.CoreLib). The work to add this other component (System.Private.Reflection.Metadata.Ecma335 will be delivered via a separate PR) * Finish merge with ImmutableArray changes * Reduce number of partial files to two --- .../src/System.Collections.Immutable.csproj | 2 + .../Immutable/ImmutableArray_1.Minimal.cs | 426 +++++++++++++++++++++ .../Collections/Immutable/ImmutableArray_1.cs | 411 +------------------- .../Immutable/ImmutableExtensions.Minimal.cs | 181 +++++++++ .../Collections/Immutable/ImmutableExtensions.cs | 166 +------- 5 files changed, 611 insertions(+), 575 deletions(-) create mode 100644 src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Minimal.cs create mode 100644 src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs diff --git a/src/System.Collections.Immutable/src/System.Collections.Immutable.csproj b/src/System.Collections.Immutable/src/System.Collections.Immutable.csproj index 553fef628d..f13f641d9d 100644 --- a/src/System.Collections.Immutable/src/System.Collections.Immutable.csproj +++ b/src/System.Collections.Immutable/src/System.Collections.Immutable.csproj @@ -45,6 +45,7 @@ + @@ -55,6 +56,7 @@ + diff --git a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Minimal.cs b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Minimal.cs new file mode 100644 index 0000000000..b5a30ae825 --- /dev/null +++ b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.Minimal.cs @@ -0,0 +1,426 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; +using System.Diagnostics; +using System.Diagnostics.CodeAnalysis; +using System.Diagnostics.Contracts; +using System.Globalization; +using System.Linq; +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 . + /// + public static readonly ImmutableArray Empty = new ImmutableArray(new T[0]); + + /// + /// 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 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 value indicating whether this collection is empty. + /// + [DebuggerBrowsable(DebuggerBrowsableState.Never)] + public bool IsEmpty + { + [NonVersionable] + get { return this.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 + { + var 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 + { + var self = this; + return self.IsDefault ? "Uninitialized" : String.Format(CultureInfo.CurrentCulture, "Length = {0}", self.Length); + } + } + + /// + /// Copies the contents of this array to the specified array. + /// + /// The array to copy to. + [Pure] + public void CopyTo(T[] destination) + { + var self = this; + self.ThrowNullRefIfNotInitialized(); + Array.Copy(self.array, 0, destination, 0, 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. + [Pure] + public void CopyTo(T[] destination, int destinationIndex) + { + var 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. + [Pure] + public void CopyTo(int sourceIndex, T[] destination, int destinationIndex, int length) + { + var 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. + [Pure] + public ImmutableArray.Builder ToBuilder() + { + var 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. + [Pure] + public Enumerator GetEnumerator() + { + var 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. + /// + [Pure] + public override int GetHashCode() + { + var 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. + /// + [Pure] + public override bool Equals(object obj) + { + IImmutableArray other = obj as IImmutableArray; + if (other != null) + { + return this.array == other.Array; + } + + return false; + } + + /// + /// 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. + /// + [Pure] + [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. + /// + [Pure] + public static ImmutableArray 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. + [Pure] + public ImmutableArray 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. + /// + [Pure] + public ImmutableArray 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. + [Pure] + IEnumerator IEnumerable.GetEnumerator() + { + var 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. + [Pure] + IEnumerator IEnumerable.GetEnumerator() + { + var 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. + var unused = 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); + } + } + } +} diff --git a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.cs b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.cs index c6585b17da..48981cfc7f 100644 --- a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.cs +++ b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray_1.cs @@ -12,123 +12,8 @@ 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 : IReadOnlyList, IList, IEquatable>, IImmutableList, IList, IImmutableArray, IStructuralComparable, IStructuralEquatable + public partial struct ImmutableArray : IReadOnlyList, IList, IEquatable>, IList, IImmutableArray, IStructuralComparable, IStructuralEquatable, IImmutableList { - /// - /// An empty (initialized) instance of . - /// - public static readonly ImmutableArray Empty = new ImmutableArray(new T[0]); - - /// - /// 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 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 or sets the element at the specified index in the read-only list. /// @@ -159,34 +44,6 @@ namespace System.Collections.Immutable get { return true; } } - /// - /// Gets a value indicating whether this collection is empty. - /// - [DebuggerBrowsable(DebuggerBrowsableState.Never)] - public bool IsEmpty - { - [NonVersionable] - get { return this.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 the number of array in the collection. /// @@ -235,50 +92,6 @@ namespace System.Collections.Immutable } } - /// - /// 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 - { - var 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 - { - var self = this; - return self.IsDefault ? "Uninitialized" : String.Format(CultureInfo.CurrentCulture, "Length = {0}", self.Length); - } - } - /// /// Searches the array for the specified item. /// @@ -475,46 +288,6 @@ namespace System.Collections.Immutable return this.IndexOf(item) >= 0; } - /// - /// Copies the contents of this array to the specified array. - /// - /// The array to copy to. - [Pure] - public void CopyTo(T[] destination) - { - var self = this; - self.ThrowNullRefIfNotInitialized(); - Array.Copy(self.array, 0, destination, 0, 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. - [Pure] - public void CopyTo(T[] destination, int destinationIndex) - { - var 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. - [Pure] - public void CopyTo(int sourceIndex, T[] destination, int destinationIndex, int length) - { - var self = this; - self.ThrowNullRefIfNotInitialized(); - Array.Copy(self.array, sourceIndex, destination, destinationIndex, length); - } - /// /// Returns a new array with the specified value inserted at the specified position. /// @@ -1030,131 +803,6 @@ namespace System.Collections.Immutable return self; } - - /// - /// Returns a builder that is populated with the same contents as this array. - /// - /// The new builder. - [Pure] - public ImmutableArray.Builder ToBuilder() - { - var 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. - [Pure] - public Enumerator GetEnumerator() - { - var 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. - /// - [Pure] - public override int GetHashCode() - { - var 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. - /// - [Pure] - public override bool Equals(object obj) - { - IImmutableArray other = obj as IImmutableArray; - if (other != null) - { - return this.array == other.Array; - } - - return false; - } - - /// - /// 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. - /// - [Pure] - [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. - /// - [Pure] - public static ImmutableArray 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. - [Pure] - public ImmutableArray 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. - /// - [Pure] - public ImmutableArray As() where TOther : class - { - return new ImmutableArray(this.array as TOther[]); - } - /// /// Filters the elements of this array to those assignable to the specified type. /// @@ -1207,32 +855,6 @@ namespace System.Collections.Immutable throw new NotSupportedException(); } - /// - /// Returns an enumerator for the contents of the array. - /// - /// An enumerator. - /// Thrown if the property returns true. - [Pure] - IEnumerator IEnumerable.GetEnumerator() - { - var 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. - [Pure] - IEnumerator IEnumerable.GetEnumerator() - { - var self = this; - self.ThrowInvalidOperationIfNotInitialized(); - return EnumeratorObject.Create(self.array); - } - /// /// See /// @@ -1643,37 +1265,6 @@ namespace System.Collections.Immutable #endregion - /// - /// 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. - var unused = 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); - } - } /// /// Returns an array with items at the specified indices removed. diff --git a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs new file mode 100644 index 0000000000..2887d99fd3 --- /dev/null +++ b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.Minimal.cs @@ -0,0 +1,181 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +using System.Collections.Generic; +using System.Diagnostics; +using System.Diagnostics.CodeAnalysis; +using System.Diagnostics.Contracts; +using System.Linq; +using System.Reflection; + +namespace System.Collections.Immutable +{ + internal static partial class ImmutableExtensions + { + /// + /// Tries to divine the number of elements in a sequence without actually enumerating each element. + /// + /// The type of elements in the sequence. + /// The enumerable source. + /// Receives the number of elements in the enumeration, if it could be determined. + /// true if the count could be determined; false otherwise. + internal static bool TryGetCount(this IEnumerable sequence, out int count) + { + return TryGetCount((IEnumerable)sequence, out count); + } + + /// + /// Tries to divine the number of elements in a sequence without actually enumerating each element. + /// + /// The type of elements in the sequence. + /// The enumerable source. + /// Receives the number of elements in the enumeration, if it could be determined. + /// true if the count could be determined; false otherwise. + internal static bool TryGetCount(this IEnumerable sequence, out int count) + { + var collection = sequence as ICollection; + if (collection != null) + { + count = collection.Count; + return true; + } + + var collectionOfT = sequence as ICollection; + if (collectionOfT != null) + { + count = collectionOfT.Count; + return true; + } + + var readOnlyCollection = sequence as IReadOnlyCollection; + if (readOnlyCollection != null) + { + count = readOnlyCollection.Count; + return true; + } + + count = 0; + return false; + } + + /// + /// Gets the number of elements in the specified sequence, + /// while guaranteeing that the sequence is only enumerated once + /// in total by this method and the caller. + /// + /// The type of element in the collection. + /// The sequence. + /// The number of elements in the sequence. + internal static int GetCount(ref IEnumerable sequence) + { + int count; + if (!sequence.TryGetCount(out count)) + { + // We cannot predict the length of the sequence. We must walk the entire sequence + // to find the count. But avoid our caller also having to enumerate by capturing + // the enumeration in a snapshot and passing that back to the caller. + var list = sequence.ToList(); + count = list.Count; + sequence = list; + } + + return count; + } + + /// + /// Tries to copy the elements in the sequence to the specified array, + /// if the sequence is a well-known collection type. Otherwise, does + /// nothing and returns false. + /// + /// The type of element in the sequence. + /// The sequence to copy. + /// The array to copy the elements to. + /// The index in the array to start copying. + /// true if the elements were successfully copied; false otherwise. + /// + /// + /// The reason we don't copy anything other than for well-known types is that a malicious interface + /// implementation of could hold on to the array when its + /// method is called. If the array it holds onto underlies an , it could violate + /// immutability by modifying the array. + /// + /// + internal static bool TryCopyTo(this IEnumerable sequence, T[] array, int arrayIndex) + { + Debug.Assert(sequence != null); + Debug.Assert(array != null); + Debug.Assert(arrayIndex >= 0 && arrayIndex <= array.Length); + + // IList is the GCD of what the following types implement. + var listInterface = sequence as IList; + if (listInterface != null) + { + var list = sequence as List; + if (list != null) + { + list.CopyTo(array, arrayIndex); + return true; + } + + // Array.Copy can throw an ArrayTypeMismatchException if the underlying type of + // the destination array is not typeof(T[]), but is assignment-compatible with T[]. + // See https://github.com/dotnet/corefx/issues/2241 for more info. + if (sequence.GetType() == typeof(T[])) + { + var sourceArray = (T[])sequence; + Array.Copy(sourceArray, 0, array, arrayIndex, sourceArray.Length); + return true; + } + + if (sequence is ImmutableArray) + { + var immutable = (ImmutableArray)sequence; + Array.Copy(immutable.array, 0, array, arrayIndex, immutable.Length); + return true; + } + } + + return false; + } + + /// + /// Gets a copy of a sequence as an array. + /// + /// The type of element. + /// The sequence to be copied. + /// The number of elements in the sequence. + /// The array. + /// + /// This is more efficient than the extension method + /// because that only tries to cast the sequence to to determine + /// the count before it falls back to reallocating arrays as it enumerates. + /// + internal static T[] ToArray(this IEnumerable sequence, int count) + { + Requires.NotNull(sequence, nameof(sequence)); + Requires.Range(count >= 0, nameof(count)); + + if (count == 0) + { + return ImmutableArray.Empty.array; + } + + T[] array = new T[count]; + + if (!sequence.TryCopyTo(array, 0)) + { + int i = 0; + foreach (var item in sequence) + { + Requires.Argument(i < count); + array[i++] = item; + } + + Requires.Argument(i == count); + } + + return array; + } + } +} diff --git a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.cs b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.cs index 783192bbd5..4f0a711ca7 100644 --- a/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.cs +++ b/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableExtensions.cs @@ -14,172 +14,8 @@ namespace System.Collections.Immutable /// /// Extension methods for immutable types. /// - internal static class ImmutableExtensions + internal static partial class ImmutableExtensions { - /// - /// Tries to divine the number of elements in a sequence without actually enumerating each element. - /// - /// The type of elements in the sequence. - /// The enumerable source. - /// Receives the number of elements in the enumeration, if it could be determined. - /// true if the count could be determined; false otherwise. - internal static bool TryGetCount(this IEnumerable sequence, out int count) - { - return TryGetCount((IEnumerable)sequence, out count); - } - - /// - /// Tries to divine the number of elements in a sequence without actually enumerating each element. - /// - /// The type of elements in the sequence. - /// The enumerable source. - /// Receives the number of elements in the enumeration, if it could be determined. - /// true if the count could be determined; false otherwise. - internal static bool TryGetCount(this IEnumerable sequence, out int count) - { - var collection = sequence as ICollection; - if (collection != null) - { - count = collection.Count; - return true; - } - - var collectionOfT = sequence as ICollection; - if (collectionOfT != null) - { - count = collectionOfT.Count; - return true; - } - - var readOnlyCollection = sequence as IReadOnlyCollection; - if (readOnlyCollection != null) - { - count = readOnlyCollection.Count; - return true; - } - - count = 0; - return false; - } - - /// - /// Gets the number of elements in the specified sequence, - /// while guaranteeing that the sequence is only enumerated once - /// in total by this method and the caller. - /// - /// The type of element in the collection. - /// The sequence. - /// The number of elements in the sequence. - internal static int GetCount(ref IEnumerable sequence) - { - int count; - if (!sequence.TryGetCount(out count)) - { - // We cannot predict the length of the sequence. We must walk the entire sequence - // to find the count. But avoid our caller also having to enumerate by capturing - // the enumeration in a snapshot and passing that back to the caller. - var list = sequence.ToList(); - count = list.Count; - sequence = list; - } - - return count; - } - - /// - /// Tries to copy the elements in the sequence to the specified array, - /// if the sequence is a well-known collection type. Otherwise, does - /// nothing and returns false. - /// - /// The type of element in the sequence. - /// The sequence to copy. - /// The array to copy the elements to. - /// The index in the array to start copying. - /// true if the elements were successfully copied; false otherwise. - /// - /// - /// The reason we don't copy anything other than for well-known types is that a malicious interface - /// implementation of could hold on to the array when its - /// method is called. If the array it holds onto underlies an , it could violate - /// immutability by modifying the array. - /// - /// - internal static bool TryCopyTo(this IEnumerable sequence, T[] array, int arrayIndex) - { - Debug.Assert(sequence != null); - Debug.Assert(array != null); - Debug.Assert(arrayIndex >= 0 && arrayIndex <= array.Length); - - // IList is the GCD of what the following types implement. - var listInterface = sequence as IList; - if (listInterface != null) - { - var list = sequence as List; - if (list != null) - { - list.CopyTo(array, arrayIndex); - return true; - } - - // Array.Copy can throw an ArrayTypeMismatchException if the underlying type of - // the destination array is not typeof(T[]), but is assignment-compatible with T[]. - // See https://github.com/dotnet/corefx/issues/2241 for more info. - if (sequence.GetType() == typeof(T[])) - { - var sourceArray = (T[])sequence; - Array.Copy(sourceArray, 0, array, arrayIndex, sourceArray.Length); - return true; - } - - if (sequence is ImmutableArray) - { - var immutable = (ImmutableArray)sequence; - Array.Copy(immutable.array, 0, array, arrayIndex, immutable.Length); - return true; - } - } - - return false; - } - - /// - /// Gets a copy of a sequence as an array. - /// - /// The type of element. - /// The sequence to be copied. - /// The number of elements in the sequence. - /// The array. - /// - /// This is more efficient than the extension method - /// because that only tries to cast the sequence to to determine - /// the count before it falls back to reallocating arrays as it enumerates. - /// - internal static T[] ToArray(this IEnumerable sequence, int count) - { - Requires.NotNull(sequence, nameof(sequence)); - Requires.Range(count >= 0, nameof(count)); - - if (count == 0) - { - return ImmutableArray.Empty.array; - } - - T[] array = new T[count]; - - if (!sequence.TryCopyTo(array, 0)) - { - int i = 0; - foreach (var item in sequence) - { - Requires.Argument(i < count); - array[i++] = item; - } - - Requires.Argument(i == count); - } - - return array; - } #if EqualsStructurally -- cgit v1.2.3