File: src\Compilers\Core\Portable\Collections\ImmutableArrayExtensions.cs
Web Access
Project: src\src\CodeStyle\Core\Analyzers\Microsoft.CodeAnalysis.CodeStyle.csproj (Microsoft.CodeAnalysis.CodeStyle)
// 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;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
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 Microsoft.CodeAnalysis.Shared.Collections;
using Roslyn.Utilities;
 
#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="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 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 copy.AsImmutable();
            }
#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, 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;
        }
    }
}