// 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. #nullable enable using System; using System.Collections.Generic; using System.Collections.Immutable; using System.Diagnostics; using System.IO; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Threading; using System.Threading.Tasks; using Microsoft.CodeAnalysis.PooledObjects; using Microsoft.CodeAnalysis.Collections; using Roslyn.Utilities; using Microsoft.CodeAnalysis.Shared.Collections; #if DEBUG using System.Linq; #endif namespace Microsoft.CodeAnalysis { /// <summary> /// The collection of extension methods for the <see cref="ImmutableArray{T}"/> type /// </summary> internal static class ImmutableArrayExtensions { /// <summary> /// Converts a sequence to an immutable array. /// </summary> /// <typeparam name="T">Elemental type of the sequence.</typeparam> /// <param name="items">The sequence to convert.</param> /// <returns>An immutable copy of the contents of the sequence.</returns> /// <exception cref="ArgumentNullException">If items is null (default)</exception> /// <remarks>If the sequence is null, this will throw <see cref="ArgumentNullException"/></remarks> public static ImmutableArray<T> AsImmutable<T>(this IEnumerable<T> items) { return ImmutableArray.CreateRange<T>(items); } /// <summary> /// Converts a sequence to an immutable array. /// </summary> /// <typeparam name="T">Elemental type of the sequence.</typeparam> /// <param name="items">The sequence to convert.</param> /// <returns>An immutable copy of the contents of the sequence.</returns> /// <remarks>If the sequence is null, this will return an empty array.</remarks> public static ImmutableArray<T> AsImmutableOrEmpty<T>(this IEnumerable<T>? items) { if (items == null) { return ImmutableArray<T>.Empty; } return ImmutableArray.CreateRange<T>(items); } /// <summary> /// Converts a sequence to an immutable array. /// </summary> /// <typeparam name="T">Elemental type of the sequence.</typeparam> /// <param name="items">The sequence to convert.</param> /// <returns>An immutable copy of the contents of the sequence.</returns> /// <remarks>If the sequence is null, this will return the default (null) array.</remarks> public static ImmutableArray<T> AsImmutableOrNull<T>(this IEnumerable<T>? items) { if (items == null) { return default; } return ImmutableArray.CreateRange<T>(items); } /// <summary> /// Converts an array to an immutable array. The array must not be null. /// </summary> /// <typeparam name="T"></typeparam> /// <param name="items">The sequence to convert</param> /// <returns></returns> public static ImmutableArray<T> AsImmutable<T>(this T[] items) { Debug.Assert(items != null); return ImmutableArray.Create<T>(items); } /// <summary> /// Converts a array to an immutable array. /// </summary> /// <typeparam name="T"></typeparam> /// <param name="items">The sequence to convert</param> /// <returns></returns> /// <remarks>If the sequence is null, this will return the default (null) array.</remarks> public static ImmutableArray<T> AsImmutableOrNull<T>(this T[]? items) { if (items == null) { return default; } return ImmutableArray.Create<T>(items); } /// <summary> /// Converts an array to an immutable array. /// </summary> /// <typeparam name="T"></typeparam> /// <param name="items">The sequence to convert</param> /// <returns>If the array is null, this will return an empty immutable array.</returns> public static ImmutableArray<T> AsImmutableOrEmpty<T>(this T[]? items) { if (items == null) { return ImmutableArray<T>.Empty; } return ImmutableArray.Create<T>(items); } /// <summary> /// Reads bytes from specified <see cref="MemoryStream"/>. /// </summary> /// <param name="stream">The stream.</param> /// <returns>Read-only content of the stream.</returns> public static ImmutableArray<byte> ToImmutable(this MemoryStream stream) { return ImmutableArray.Create<byte>(stream.ToArray()); } /// <summary> /// Maps an immutable array to another immutable array. /// </summary> /// <typeparam name="TItem"></typeparam> /// <typeparam name="TResult"></typeparam> /// <param name="items">The array to map</param> /// <param name="map">The mapping delegate</param> /// <returns>If the items's length is 0, this will return an empty immutable array</returns> public static ImmutableArray<TResult> SelectAsArray<TItem, TResult>(this ImmutableArray<TItem> items, Func<TItem, TResult> map) { return ImmutableArray.CreateRange(items, map); } /// <summary> /// Maps an immutable array to another immutable array. /// </summary> /// <typeparam name="TItem"></typeparam> /// <typeparam name="TArg"></typeparam> /// <typeparam name="TResult"></typeparam> /// <param name="items">The sequence to map</param> /// <param name="map">The mapping delegate</param> /// <param name="arg">The extra input used by mapping delegate</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectAsArray<TItem, TArg, TResult>(this ImmutableArray<TItem> items, Func<TItem, TArg, TResult> map, TArg arg) { return ImmutableArray.CreateRange(items, map, arg); } /// <summary> /// Maps an immutable array to another immutable array. /// </summary> /// <typeparam name="TItem"></typeparam> /// <typeparam name="TArg"></typeparam> /// <typeparam name="TResult"></typeparam> /// <param name="items">The sequence to map</param> /// <param name="map">The mapping delegate</param> /// <param name="arg">The extra input used by mapping delegate</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectAsArray<TItem, TArg, TResult>(this ImmutableArray<TItem> items, Func<TItem, int, TArg, TResult> map, TArg arg) { switch (items.Length) { case 0: return ImmutableArray<TResult>.Empty; case 1: return ImmutableArray.Create(map(items[0], 0, arg)); case 2: return ImmutableArray.Create(map(items[0], 0, arg), map(items[1], 1, arg)); case 3: return ImmutableArray.Create(map(items[0], 0, arg), map(items[1], 1, arg), map(items[2], 2, arg)); case 4: return ImmutableArray.Create(map(items[0], 0, arg), map(items[1], 1, arg), map(items[2], 2, arg), map(items[3], 3, arg)); default: var builder = ArrayBuilder<TResult>.GetInstance(items.Length); for (int i = 0; i < items.Length; i++) { builder.Add(map(items[i], i, arg)); } return builder.ToImmutableAndFree(); } } /// <summary> /// Maps a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, bool> predicate, Func<TItem, TResult> selector) { if (array.Length == 0) { return ImmutableArray<TResult>.Empty; } var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item)) { builder.Add(selector(item)); } } return builder.ToImmutableAndFree(); } /// <summary> /// Maps a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <typeparam name="TArg">Type of the extra argument</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <param name="arg">The extra input used by <paramref name="predicate"/> and <paramref name="selector"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectAsArray<TItem, TArg, TResult>(this ImmutableArray<TItem> array, Func<TItem, TArg, bool> predicate, Func<TItem, TArg, TResult> selector, TArg arg) { if (array.Length == 0) { return ImmutableArray<TResult>.Empty; } var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item, arg)) { builder.Add(selector(item, arg)); } } return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="selector">A transform function to apply to each element.</param> /// <returns>If the array's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, IEnumerable<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) builder.AddRange(selector(item)); return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="selector">A transform function to apply to each element.</param> /// <returns>If the array's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, ImmutableArray<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) builder.AddRange(selector(item)); return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="selector">A transform function to apply to each element.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, OneOrMany<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { selector(item).AddRangeTo(builder); } return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, bool> predicate, Func<TItem, IEnumerable<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item)) builder.AddRange(selector(item)); } return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, bool> predicate, Func<TItem, ImmutableArray<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item)) builder.AddRange(selector(item)); } return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, bool> predicate, Func<TItem, OneOrMany<TResult>> selector) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item)) selector(item).AddRangeTo(builder); } return builder.ToImmutableAndFree(); } /// <summary> /// Maps and flattens a subset of immutable array to another immutable array. /// </summary> /// <typeparam name="TItem">Type of the source array items</typeparam> /// <typeparam name="TArg">Type of the argument to pass to the predicate and selector</typeparam> /// <typeparam name="TResult">Type of the transformed array items</typeparam> /// <param name="array">The array to transform</param> /// <param name="predicate">The condition to use for filtering the array content.</param> /// <param name="selector">A transform function to apply to each element that is not filtered out by <paramref name="predicate"/>.</param> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> SelectManyAsArray<TItem, TArg, TResult>(this ImmutableArray<TItem> array, Func<TItem, TArg, bool> predicate, Func<TItem, TArg, OneOrMany<TResult>> selector, TArg arg) { if (array.Length == 0) return ImmutableArray<TResult>.Empty; var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in array) { if (predicate(item, arg)) selector(item, arg).AddRangeTo(builder); } return builder.ToImmutableAndFree(); } /// <summary> /// Maps an immutable array through a function that returns ValueTasks, returning the new ImmutableArray. /// </summary> public static async ValueTask<ImmutableArray<TResult>> SelectAsArrayAsync<TItem, TResult>(this ImmutableArray<TItem> array, Func<TItem, CancellationToken, ValueTask<TResult>> selector, CancellationToken cancellationToken) { if (array.IsEmpty) return ImmutableArray<TResult>.Empty; var builder = new TResult[array.Length]; for (var i = 0; i < array.Length; i++) { builder[i] = await selector(array[i], cancellationToken).ConfigureAwait(false); } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } /// <summary> /// Maps an immutable array through a function that returns ValueTasks, returning the new ImmutableArray. /// </summary> public static async ValueTask<ImmutableArray<TResult>> SelectAsArrayAsync<TItem, TArg, TResult>(this ImmutableArray<TItem> array, Func<TItem, TArg, CancellationToken, ValueTask<TResult>> selector, TArg arg, CancellationToken cancellationToken) { if (array.IsEmpty) return ImmutableArray<TResult>.Empty; var builder = new TResult[array.Length]; for (var i = 0; i < array.Length; i++) { builder[i] = await selector(array[i], arg, cancellationToken).ConfigureAwait(false); } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } public static ValueTask<ImmutableArray<TResult>> SelectManyAsArrayAsync<TItem, TArg, TResult>(this ImmutableArray<TItem> source, Func<TItem, TArg, CancellationToken, ValueTask<ImmutableArray<TResult>>> selector, TArg arg, CancellationToken cancellationToken) { if (source.Length == 0) { return new ValueTask<ImmutableArray<TResult>>(ImmutableArray<TResult>.Empty); } if (source.Length == 1) { return selector(source[0], arg, cancellationToken); } return CreateTaskAsync(); async ValueTask<ImmutableArray<TResult>> CreateTaskAsync() { var builder = ArrayBuilder<TResult>.GetInstance(); foreach (var item in source) { builder.AddRange(await selector(item, arg, cancellationToken).ConfigureAwait(false)); } return builder.ToImmutableAndFree(); } } /// <summary> /// Zips two immutable arrays together through a mapping function, producing another immutable array. /// </summary> /// <returns>If the items's length is 0, this will return an empty immutable array.</returns> public static ImmutableArray<TResult> ZipAsArray<T1, T2, TResult>(this ImmutableArray<T1> self, ImmutableArray<T2> other, Func<T1, T2, TResult> map) { Debug.Assert(self.Length == other.Length); switch (self.Length) { case 0: return ImmutableArray<TResult>.Empty; case 1: return ImmutableArray.Create(map(self[0], other[0])); case 2: return ImmutableArray.Create(map(self[0], other[0]), map(self[1], other[1])); case 3: return ImmutableArray.Create(map(self[0], other[0]), map(self[1], other[1]), map(self[2], other[2])); case 4: return ImmutableArray.Create(map(self[0], other[0]), map(self[1], other[1]), map(self[2], other[2]), map(self[3], other[3])); default: var builder = new TResult[self.Length]; for (int i = 0; i < self.Length; i++) { builder[i] = map(self[i], other[i]); } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } } public static ImmutableArray<TResult> ZipAsArray<T1, T2, TArg, TResult>(this ImmutableArray<T1> self, ImmutableArray<T2> other, TArg arg, Func<T1, T2, int, TArg, TResult> map) { Debug.Assert(self.Length == other.Length); if (self.IsEmpty) { return ImmutableArray<TResult>.Empty; } var builder = ArrayBuilder<TResult>.GetInstance(self.Length); for (int i = 0; i < self.Length; i++) { builder.Add(map(self[i], other[i], i, arg)); } return builder.ToImmutableAndFree(); } /// <summary> /// Creates a new immutable array based on filtered elements by the predicate. The array must not be null. /// </summary> /// <param name="array">The array to process</param> /// <param name="predicate">The delegate that defines the conditions of the element to search for.</param> public static ImmutableArray<T> WhereAsArray<T>(this ImmutableArray<T> array, Func<T, bool> predicate) => WhereAsArrayImpl<T, object?>(array, predicate, predicateWithArg: null, arg: null); /// <summary> /// Creates a new immutable array based on filtered elements by the predicate. The array must not be null. /// </summary> /// <param name="array">The array to process</param> /// <param name="predicate">The delegate that defines the conditions of the element to search for.</param> public static ImmutableArray<T> WhereAsArray<T, TArg>(this ImmutableArray<T> array, Func<T, TArg, bool> predicate, TArg arg) => WhereAsArrayImpl(array, predicateWithoutArg: null, predicate, arg); private static ImmutableArray<T> WhereAsArrayImpl<T, TArg>(ImmutableArray<T> array, Func<T, bool>? predicateWithoutArg, Func<T, TArg, bool>? predicateWithArg, TArg arg) { Debug.Assert(!array.IsDefault); Debug.Assert(predicateWithArg != null ^ predicateWithoutArg != null); ArrayBuilder<T>? builder = null; bool none = true; bool all = true; int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if ((predicateWithoutArg != null) ? predicateWithoutArg(a) : predicateWithArg!(a, arg)) { none = false; if (all) { continue; } Debug.Assert(i > 0); if (builder == null) { builder = ArrayBuilder<T>.GetInstance(); } builder.Add(a); } else { if (none) { all = false; continue; } Debug.Assert(i > 0); if (all) { Debug.Assert(builder == null); all = false; builder = ArrayBuilder<T>.GetInstance(); for (int j = 0; j < i; j++) { builder.Add(array[j]); } } } } if (builder != null) { Debug.Assert(!all); Debug.Assert(!none); return builder.ToImmutableAndFree(); } else if (all) { return array; } else { Debug.Assert(none); return ImmutableArray<T>.Empty; } } public static bool Any<T, TArg>(this ImmutableArray<T> array, Func<T, TArg, bool> predicate, TArg arg) { int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if (predicate(a, arg)) { return true; } } return false; } public static bool All<T, TArg>(this ImmutableArray<T> array, Func<T, TArg, bool> predicate, TArg arg) { int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if (!predicate(a, arg)) { return false; } } return true; } public static async Task<bool> AnyAsync<T>(this ImmutableArray<T> array, Func<T, Task<bool>> predicateAsync) { int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if (await predicateAsync(a).ConfigureAwait(false)) { return true; } } return false; } public static async Task<bool> AnyAsync<T, TArg>(this ImmutableArray<T> array, Func<T, TArg, Task<bool>> predicateAsync, TArg arg) { int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if (await predicateAsync(a, arg).ConfigureAwait(false)) { return true; } } return false; } public static async ValueTask<T?> FirstOrDefaultAsync<T>(this ImmutableArray<T> array, Func<T, Task<bool>> predicateAsync) { int n = array.Length; for (int i = 0; i < n; i++) { var a = array[i]; if (await predicateAsync(a).ConfigureAwait(false)) { return a; } } return default; } public static TValue? FirstOrDefault<TValue, TArg>(this ImmutableArray<TValue> array, Func<TValue, TArg, bool> predicate, TArg arg) { foreach (var val in array) { if (predicate(val, arg)) { return val; } } return default; } public static TValue Single<TValue, TArg>(this ImmutableArray<TValue> array, Func<TValue, TArg, bool> predicate, TArg arg) { var hasValue = false; TValue? value = default; foreach (var item in array) { if (predicate(item, arg)) { if (hasValue) { throw ExceptionUtilities.Unreachable(); } value = item; hasValue = true; } } if (!hasValue) { throw ExceptionUtilities.Unreachable(); } return value!; } /// <summary> /// Casts the immutable array of a Type to an immutable array of its base type. /// </summary> [MethodImpl(MethodImplOptions.AggressiveInlining)] public static ImmutableArray<TBase> Cast<TDerived, TBase>(this ImmutableArray<TDerived> items) where TDerived : class, TBase { return ImmutableArray<TBase>.CastUp(items); } /// <summary> /// Determines whether this instance and another immutable array are equal. /// </summary> /// <typeparam name="T"></typeparam> /// <param name="array1"></param> /// <param name="array2"></param> /// <param name="comparer">The comparer to determine if the two arrays are equal.</param> /// <returns>True if the two arrays are equal</returns> public static bool SetEquals<T>(this ImmutableArray<T> array1, ImmutableArray<T> array2, IEqualityComparer<T> comparer) { if (array1.IsDefault) { return array2.IsDefault; } else if (array2.IsDefault) { return false; } var count1 = array1.Length; var count2 = array2.Length; // avoid constructing HashSets in these common cases if (count1 == 0) { return count2 == 0; } else if (count2 == 0) { return false; } else if (count1 == 1 && count2 == 1) { var item1 = array1[0]; var item2 = array2[0]; return comparer.Equals(item1, item2); } var set1 = new HashSet<T>(array1, comparer); var set2 = new HashSet<T>(array2, comparer); // internally recognizes that set2 is a HashSet with the same comparer (http://msdn.microsoft.com/en-us/library/bb346516.aspx) return set1.SetEquals(set2); } /// <summary> /// Returns an empty array if the input array is null (default) /// </summary> public static ImmutableArray<T> NullToEmpty<T>(this ImmutableArray<T> array) { return array.IsDefault ? ImmutableArray<T>.Empty : array; } /// <summary> /// Returns an empty array if the input nullable value type is null or the underlying array is null (default) /// </summary> public static ImmutableArray<T> NullToEmpty<T>(this ImmutableArray<T>? array) => array switch { null or { IsDefault: true } => ImmutableArray<T>.Empty, { } underlying => underlying }; /// <summary> /// Returns an array of distinct elements, preserving the order in the original array. /// If the array has no duplicates, the original array is returned. The original array must not be null. /// </summary> public static ImmutableArray<T> Distinct<T>(this ImmutableArray<T> array, IEqualityComparer<T>? comparer = null) { Debug.Assert(!array.IsDefault); if (array.Length < 2) { return array; } var set = new HashSet<T>(comparer); var builder = ArrayBuilder<T>.GetInstance(); foreach (var a in array) { if (set.Add(a)) { builder.Add(a); } } var result = (builder.Count == array.Length) ? array : builder.ToImmutable(); builder.Free(); return result; } // In DEBUG, swap the first and last elements of a read-only array, yielding a new read only array. // This helps to avoid depending on accidentally sorted arrays. internal static ImmutableArray<T> ConditionallyDeOrder<T>(this ImmutableArray<T> array) { #if DEBUG if (!array.IsDefault && array.Length >= 2) { T[] copy = array.ToArray(); int last = copy.Length - 1; var temp = copy[0]; copy[0] = copy[last]; copy[last] = temp; return ImmutableCollectionsMarshal.AsImmutableArray(copy); } #endif return array; } internal static ImmutableArray<TValue> Flatten<TKey, TValue>( this Dictionary<TKey, ImmutableArray<TValue>> dictionary, IComparer<TValue>? comparer = null) where TKey : notnull { if (dictionary.Count == 0) { return ImmutableArray<TValue>.Empty; } var builder = ArrayBuilder<TValue>.GetInstance(); foreach (var kvp in dictionary) { builder.AddRange(kvp.Value); } if (comparer != null && builder.Count > 1) { // PERF: Beware ImmutableArray<T>.Builder.Sort allocates a Comparer wrapper object builder.Sort(comparer); } return builder.ToImmutableAndFree(); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, ImmutableArray<T> second) { return first.AddRange(second); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, ImmutableArray<T> second, ImmutableArray<T> third) { var builder = new T[first.Length + second.Length + third.Length]; var index = 0; foreach (var item in first) { builder[index++] = item; } foreach (var item in second) { builder[index++] = item; } foreach (var item in third) { builder[index++] = item; } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, ImmutableArray<T> second, ImmutableArray<T> third, ImmutableArray<T> fourth) { var builder = new T[first.Length + second.Length + third.Length + fourth.Length]; var index = 0; foreach (var item in first) { builder[index++] = item; } foreach (var item in second) { builder[index++] = item; } foreach (var item in third) { builder[index++] = item; } foreach (var item in fourth) { builder[index++] = item; } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, ImmutableArray<T> second, ImmutableArray<T> third, ImmutableArray<T> fourth, ImmutableArray<T> fifth) { var builder = new T[first.Length + second.Length + third.Length + fourth.Length + fifth.Length]; var index = 0; foreach (var item in first) { builder[index++] = item; } foreach (var item in second) { builder[index++] = item; } foreach (var item in third) { builder[index++] = item; } foreach (var item in fourth) { builder[index++] = item; } foreach (var item in fifth) { builder[index++] = item; } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, ImmutableArray<T> second, ImmutableArray<T> third, ImmutableArray<T> fourth, ImmutableArray<T> fifth, ImmutableArray<T> sixth) { var builder = new T[first.Length + second.Length + third.Length + fourth.Length + fifth.Length + sixth.Length]; var index = 0; foreach (var item in first) { builder[index++] = item; } foreach (var item in second) { builder[index++] = item; } foreach (var item in third) { builder[index++] = item; } foreach (var item in fourth) { builder[index++] = item; } foreach (var item in fifth) { builder[index++] = item; } foreach (var item in sixth) { builder[index++] = item; } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } internal static ImmutableArray<T> Concat<T>(this ImmutableArray<T> first, T second) { return first.Add(second); } internal static ImmutableArray<T> AddRange<T>(this ImmutableArray<T> self, in TemporaryArray<T> items) { if (items.Count == 0) { return self; } if (items.Count == 1) { return self.Add(items[0]); } var builder = new T[self.Length + items.Count]; var index = 0; foreach (var item in self) { builder[index++] = item; } foreach (var item in items) { builder[index++] = item; } return ImmutableCollectionsMarshal.AsImmutableArray(builder); } /// <summary> /// Determines whether duplicates exist using default equality comparer. /// </summary> /// <param name="array">Array to search for duplicates</param> /// <returns>Whether duplicates were found</returns> internal static bool HasDuplicates<T>(this ImmutableArray<T> array) { switch (array.Length) { case 0: case 1: return false; case 2: return EqualityComparer<T>.Default.Equals(array[0], array[1]); default: var set = PooledHashSet<T>.GetInstance(); var foundDuplicate = false; foreach (var element in array) { if (!set.Add(element)) { foundDuplicate = true; break; } } set.Free(); return foundDuplicate; } } /// <summary> /// Determines whether duplicates exist using <paramref name="comparer"/>. Use other override /// if you don't need a custom comparer. /// </summary> /// <param name="array">Array to search for duplicates</param> /// <param name="comparer">Comparer to use in search</param> /// <returns>Whether duplicates were found</returns> internal static bool HasDuplicates<T>(this ImmutableArray<T> array, IEqualityComparer<T> comparer) { switch (array.Length) { case 0: case 1: return false; case 2: comparer ??= EqualityComparer<T>.Default; return comparer.Equals(array[0], array[1]); default: var set = new HashSet<T>(comparer); foreach (var element in array) { if (!set.Add(element)) { return true; } } return false; } } public static int Count<T>(this ImmutableArray<T> items, Func<T, bool> predicate) { if (items.IsEmpty) { return 0; } int count = 0; for (int i = 0; i < items.Length; ++i) { if (predicate(items[i])) { ++count; } } return count; } public static int Sum<T>(this ImmutableArray<T> items, Func<T, int> selector) { var sum = 0; foreach (var item in items) sum += selector(item); return sum; } public static int Sum<T>(this ImmutableArray<T> items, Func<T, int, int> selector) { var sum = 0; for (var i = 0; i < items.Length; i++) sum += selector(items[i], i); return sum; } internal static void AddToMultiValueDictionaryBuilder<K, T>(Dictionary<K, object> accumulator, K key, T item) where K : notnull where T : notnull { if (accumulator.TryGetValue(key, out var existingValueOrArray)) { if (existingValueOrArray is ArrayBuilder<T> arrayBuilder) { // Already a builder in the accumulator, just add to that. } else { // Just a single value in the accumulator so far. Convert to using a builder. arrayBuilder = ArrayBuilder<T>.GetInstance(capacity: 2); arrayBuilder.Add((T)existingValueOrArray); accumulator[key] = arrayBuilder; } arrayBuilder.Add(item); } else { // Nothing in the dictionary so far. Add the item directly. accumulator.Add(key, item); } } internal static void CreateNameToMembersMap<TKey, TNamespaceOrTypeSymbol, TNamedTypeSymbol, TNamespaceSymbol> (Dictionary<TKey, object> dictionary, Dictionary<TKey, ImmutableArray<TNamespaceOrTypeSymbol>> result) where TKey : notnull where TNamespaceOrTypeSymbol : class where TNamedTypeSymbol : class, TNamespaceOrTypeSymbol where TNamespaceSymbol : class, TNamespaceOrTypeSymbol { foreach (var entry in dictionary) result.Add(entry.Key, createMembers(entry.Value)); return; static ImmutableArray<TNamespaceOrTypeSymbol> createMembers(object value) { if (value is ArrayBuilder<TNamespaceOrTypeSymbol> builder) { Debug.Assert(builder.Count > 1); foreach (var item in builder) { if (item is TNamespaceSymbol) return builder.ToImmutableAndFree(); } return ImmutableArray<TNamespaceOrTypeSymbol>.CastUp(builder.ToDowncastedImmutableAndFree<TNamedTypeSymbol>()); } else { TNamespaceOrTypeSymbol symbol = (TNamespaceOrTypeSymbol)value; return symbol is TNamespaceSymbol ? ImmutableArray.Create(symbol) : ImmutableArray<TNamespaceOrTypeSymbol>.CastUp(ImmutableArray.Create((TNamedTypeSymbol)symbol)); } } } internal static Dictionary<TKey, ImmutableArray<TNamedTypeSymbol>> GetTypesFromMemberMap<TKey, TNamespaceOrTypeSymbol, TNamedTypeSymbol> (Dictionary<TKey, ImmutableArray<TNamespaceOrTypeSymbol>> map, IEqualityComparer<TKey> comparer) where TKey : notnull where TNamespaceOrTypeSymbol : class where TNamedTypeSymbol : class, TNamespaceOrTypeSymbol { // Initialize dictionary capacity to avoid resize allocations during Add calls. // Most iterations through the loop add an entry. If map is smaller than the // smallest capacity dictionary will use, we'll let it grow organically as // it's possible we might not add anything to the dictionary. var capacity = map.Count > 3 ? map.Count : 0; var dictionary = new Dictionary<TKey, ImmutableArray<TNamedTypeSymbol>>(capacity, comparer); foreach (var entry in map) { var namedTypes = getOrCreateNamedTypes(entry.Value); if (namedTypes.Length > 0) dictionary.Add(entry.Key, namedTypes); } return dictionary; static ImmutableArray<TNamedTypeSymbol> getOrCreateNamedTypes(ImmutableArray<TNamespaceOrTypeSymbol> members) { Debug.Assert(members.Length > 0); // See if creator 'map' put a downcasted ImmutableArray<TNamedTypeSymbol> in it. If so, we can just directly // downcast to that and trivially reuse it. If not, that means the array must have contained at least one // TNamespaceSymbol and we'll need to filter that out. var membersAsNamedTypes = members.As<TNamedTypeSymbol>(); if (!membersAsNamedTypes.IsDefault) return membersAsNamedTypes; // Preallocate the right amount so we can avoid garbage reallocs. var count = members.Count(static s => s is TNamedTypeSymbol); // Must have less items than in the original array. Otherwise, the .As<TNamedTypeSymbol>() cast would // have succeeded. Debug.Assert(count < members.Length); if (count == 0) return ImmutableArray<TNamedTypeSymbol>.Empty; var builder = ArrayBuilder<TNamedTypeSymbol>.GetInstance(count); foreach (var member in members) { if (member is TNamedTypeSymbol namedType) builder.Add(namedType); } Debug.Assert(builder.Count == count); return builder.ToImmutableAndFree(); } } internal static bool SequenceEqual<TElement, TArg>(this ImmutableArray<TElement> array1, ImmutableArray<TElement> array2, TArg arg, Func<TElement, TElement, TArg, bool> predicate) { // The framework implementation of SequenceEqual forces a NullRef for default array1 and 2, so we // maintain the same behavior in this extension if (array1.IsDefault) { throw new NullReferenceException(); } if (array2.IsDefault) { throw new NullReferenceException(); } if (array1.Length != array2.Length) { return false; } for (int i = 0; i < array1.Length; i++) { if (!predicate(array1[i], array2[i], arg)) { return false; } } return true; } internal static int IndexOf<T>(this ImmutableArray<T> array, T item, IEqualityComparer<T> comparer) => array.IndexOf(item, startIndex: 0, comparer); internal static bool IsSorted<T>(this ImmutableArray<T> array, Comparison<T> comparison) => IsSorted(array, Comparer<T>.Create(comparison)); internal static bool IsSorted<T>(this ImmutableArray<T> array, IComparer<T>? comparer = null) { comparer ??= Comparer<T>.Default; for (var i = 1; i < array.Length; i++) { if (comparer.Compare(array[i - 1], array[i]) > 0) { return false; } } return true; } // same as Array.BinarySearch but the ability to pass arbitrary value to the comparer without allocation internal static int BinarySearch<TElement, TValue>(this ImmutableArray<TElement> array, TValue value, Func<TElement, TValue, int> comparer) => BinarySearch(array.AsSpan(), value, comparer); internal static int BinarySearch<TElement, TValue>(this ReadOnlySpan<TElement> array, TValue value, Func<TElement, TValue, int> comparer) { int low = 0; int high = array.Length - 1; while (low <= high) { int middle = low + ((high - low) >> 1); int comparison = comparer(array[middle], value); if (comparison == 0) { return middle; } if (comparison > 0) { high = middle - 1; } else { low = middle + 1; } } return ~low; } internal static int BinarySearch<TElement, TValue>(this ImmutableSegmentedList<TElement> array, TValue value, Func<TElement, TValue, int> comparer) { int low = 0; int high = array.Count - 1; while (low <= high) { int middle = low + ((high - low) >> 1); int comparison = comparer(array[middle], value); if (comparison == 0) { return middle; } if (comparison > 0) { high = middle - 1; } else { low = middle + 1; } } return ~low; } public static bool IsSubsetOf<TElement>(this ImmutableArray<TElement> array, ImmutableArray<TElement> other) { if (other.Length == 0) { return array.Length == 0; } switch (array.Length) { case 0: return true; case 1: return other.Contains(array[0]); case 2: return other.Contains(array[0]) && other.Contains(array[1]); case 3: return other.Contains(array[0]) && other.Contains(array[1]) && other.Contains(array[2]); } var set = PooledHashSet<TElement>.GetInstance(); foreach (var item in other) { set.Add(item); } foreach (var item in array) { if (!set.Contains(item)) { set.Free(); return false; } } set.Free(); return true; } } } |