src/Compilers/Core/CodeAnalysisTest/Collections/ImmutableSetTest.cs - main - githubmirror/roslyn

src/Compilers/Core/CodeAnalysisTest/Collections/ImmutableSetTest.cs
526 строк21 KB
Sam Harwell
Fix CA1825 (Avoid zero-length array allocations)
09 июл 2021, 23:38
09 июл 2021, 23:380ca55e6
// 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.

// NOTE: This code is derived from an implementation originally in dotnet/runtime:
// https://github.com/dotnet/runtime/blob/v5.0.8/src/libraries/System.Collections.Immutable/tests/ImmutableSetTest.cs
//
// See the commentary in https://github.com/dotnet/roslyn/pull/50156 for notes on incorporating changes made to the
// reference implementation.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Xunit;
using SetTriad = System.Tuple<System.Collections.Generic.IEnumerable<int>, System.Collections.Generic.IEnumerable<int>, bool>;

#pragma warning disable CA1829 // Use Length/Count property instead of Count() when available
#pragma warning disable RS0002 // Use 'SpecializedCollections.SingletonEnumerable()'

namespace Microsoft.CodeAnalysis.UnitTests.Collections
{
    public abstract partial class ImmutableSetTest : ImmutablesTestBase
    {
        [Fact]
        public void AddTest()
        {
            AddTestHelper(this.Empty<int>(), 3, 5, 4, 3);
        }

        [Fact]
        public void AddDuplicatesTest()
        {
            var arrayWithDuplicates = Enumerable.Range(1, 100).Concat(Enumerable.Range(1, 100)).ToArray();
            AddTestHelper(this.Empty<int>(), arrayWithDuplicates);
        }

        [Fact]
        public void RemoveTest()
        {
            RemoveTestHelper(this.Empty<int>().Add(3).Add(5), 5, 3);
        }

        [Fact]
        public void AddRemoveLoadTest()
        {
            var data = GenerateDummyFillData();
            AddRemoveLoadTestHelper(Empty<double>(), data);
        }

        [Fact]
        public void RemoveNonExistingTest()
        {
            System.Collections.Immutable.IImmutableSet<int> emptySet = this.Empty<int>();
            Assert.True(IsSame(emptySet, emptySet.Remove(5)));

            // Also fill up a set with many elements to build up the tree, then remove from various places in the tree.
            const int Size = 200;
            var set = emptySet;
            for (int i = 0; i < Size; i += 2)
            { // only even numbers!
                set = set.Add(i);
            }

            // Verify that removing odd numbers doesn't change anything.
            for (int i = 1; i < Size; i += 2)
            {
                var setAfterRemoval = set.Remove(i);
                Assert.True(IsSame(set, setAfterRemoval));
            }
        }

        [Fact]
        public void AddBulkFromImmutableToEmpty()
        {
            var set = this.Empty<int>().Add(5);
            var empty2 = this.Empty<int>();
            Assert.True(IsSame(set, empty2.Union(set))); // "Filling an empty immutable set with the contents of another immutable set with the exact same comparer should return the other set."
        }

        /// <summary>
        /// Verifies that Except *does* enumerate its argument if the collection is empty.
        /// </summary>
        /// <remarks>
        /// While this would seem an implementation detail and simply lack of an optimization,
        /// it turns out that changing this behavior now *could* represent a breaking change
        /// because if the enumerable were to throw an exception, that exception would be
        /// observed previously, but would no longer be thrown if this behavior changed.
        /// So this is a test to lock the behavior in place or be thoughtful if adding the optimization.
        /// </remarks>
        /// <!--<seealso cref="ImmutableListTest.RemoveRangeDoesNotEnumerateSequenceIfThisIsEmpty"/>-->
        [Fact]
        public void ExceptDoesEnumerateSequenceIfThisIsEmpty()
        {
            bool enumerated = false;
            Empty<int>().Except(Enumerable.Range(1, 1).Select(n => { enumerated = true; return n; }));
            Assert.True(enumerated);
        }

        [Fact]
        public void SetEqualsTest()
        {
            Assert.True(this.Empty<int>().SetEquals(this.Empty<int>()));
            var nonEmptySet = this.Empty<int>().Add(5);
            Assert.True(nonEmptySet.SetEquals(nonEmptySet));

            this.SetCompareTestHelper(s => s.SetEquals, s => s.SetEquals, this.GetSetEqualsScenarios());
        }

        [Fact]
        public void IsProperSubsetOfTest()
        {
            this.SetCompareTestHelper(s => s.IsProperSubsetOf, s => s.IsProperSubsetOf, GetIsProperSubsetOfScenarios());
        }

        [Fact]
        public void IsProperSupersetOfTest()
        {
            this.SetCompareTestHelper(s => s.IsProperSupersetOf, s => s.IsProperSupersetOf, GetIsProperSubsetOfScenarios().Select(Flip));
        }

        [Fact]
        public void IsSubsetOfTest()
        {
            this.SetCompareTestHelper(s => s.IsSubsetOf, s => s.IsSubsetOf, GetIsSubsetOfScenarios());
        }

        [Fact]
        public void IsSupersetOfTest()
        {
            this.SetCompareTestHelper(s => s.IsSupersetOf, s => s.IsSupersetOf, GetIsSubsetOfScenarios().Select(Flip));
        }

        [Fact]
        public void OverlapsTest()
        {
            this.SetCompareTestHelper(s => s.Overlaps, s => s.Overlaps, GetOverlapsScenarios());
        }

        [Fact]
        public void EqualsTest()
        {
            Assert.False(Empty<int>().Equals(null));
            Assert.False(Empty<int>().Equals("hi"));
            Assert.True(Empty<int>().Equals(Empty<int>()));
            Assert.False(Empty<int>().Add(3).Equals(Empty<int>().Add(3)));
            Assert.False(Empty<int>().Add(5).Equals(Empty<int>().Add(3)));
            Assert.False(Empty<int>().Add(3).Add(5).Equals(Empty<int>().Add(3)));
            Assert.False(Empty<int>().Add(3).Equals(Empty<int>().Add(3).Add(5)));
        }

        [Fact]
        public void GetHashCodeTest()
        {
            // verify that get hash code is the default address based one.
            Assert.Equal(EqualityComparer<object>.Default.GetHashCode(Empty<int>()), Empty<int>().GetHashCode());
        }

        [Fact]
        public void ClearTest()
        {
            var originalSet = this.Empty<int>();
            var nonEmptySet = originalSet.Add(5);
            var clearedSet = nonEmptySet.Clear();
            Assert.True(IsSame(originalSet, clearedSet));
        }

        [Fact]
        public void ISetMutationMethods()
        {
            var set = (ISet<int>)this.Empty<int>();
            Assert.Throws<NotSupportedException>(() => set.Add(0));
            Assert.Throws<NotSupportedException>(() => set.ExceptWith(null!));
            Assert.Throws<NotSupportedException>(() => set.UnionWith(null!));
            Assert.Throws<NotSupportedException>(() => set.IntersectWith(null!));
            Assert.Throws<NotSupportedException>(() => set.SymmetricExceptWith(null!));
        }

        [Fact]
        public void ICollectionOfTMembers()
        {
            var set = (ICollection<int>)this.Empty<int>();
            Assert.Throws<NotSupportedException>(() => set.Add(1));
            Assert.Throws<NotSupportedException>(() => set.Clear());
            Assert.Throws<NotSupportedException>(() => set.Remove(1));
            Assert.True(set.IsReadOnly);
        }

        [Fact]
        public void ICollectionMethods()
        {
            ICollection builder = (ICollection)this.Empty<string>();
            string[] array = Array.Empty<string>();
            builder.CopyTo(array, 0);

            builder = (ICollection)this.Empty<string>().Add("a");
            array = new string[builder.Count + 1];

            builder.CopyTo(array, 1);
            Assert.Equal(new[] { null, "a" }, array);

            Assert.True(builder.IsSynchronized);
            Assert.NotNull(builder.SyncRoot);
            Assert.Same(builder.SyncRoot, builder.SyncRoot);
        }

        [Fact]
        public void NullHandling()
        {
            var empty = this.Empty<string?>();
            var set = empty.Add(null);
            Assert.True(set.Contains(null));
            Assert.True(set.TryGetValue(null, out var @null));
            Assert.Null(@null);
            Assert.Equal(empty, set.Remove(null));

            set = empty.Union(new[] { null, "a" });
            Assert.True(set.IsSupersetOf(new[] { null, "a" }));
            Assert.True(set.IsSubsetOf(new[] { null, "a" }));
            Assert.True(set.IsProperSupersetOf(new[] { (string?)null }));
            Assert.True(set.IsProperSubsetOf(new[] { null, "a", "b" }));
            Assert.True(set.Overlaps(new[] { null, "b" }));
            Assert.True(set.SetEquals(new[] { null, null, "a", "a" }));

            set = set.Intersect(new[] { (string?)null });
            Assert.Equal(1, set.Count);

            set = set.Except(new[] { (string?)null });
            Assert.False(set.Contains(null));
        }

        protected abstract bool IncludesGetHashCodeDerivative { get; }

        internal static List<T> ToListNonGeneric<T>(System.Collections.IEnumerable sequence)
        {
            Assert.NotNull(sequence);

            var list = new List<T>();
            var enumerator = sequence.GetEnumerator();
            while (enumerator.MoveNext())
            {
                list.Add((T)enumerator.Current);
            }

            return list;
        }

        protected abstract System.Collections.Immutable.IImmutableSet<T> Empty<T>();

        protected abstract ISet<T> EmptyMutable<T>();

        protected System.Collections.Immutable.IImmutableSet<T> SetWith<T>(params T[] items)
        {
            return this.Empty<T>().Union(items);
        }

        protected static void CustomSortTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> emptySet, bool matchOrder, T[] injectedValues, T[] expectedValues)
        {
            Assert.NotNull(emptySet);
            Assert.NotNull(injectedValues);
            Assert.NotNull(expectedValues);

            var set = emptySet;
            foreach (T value in injectedValues)
            {
                set = set.Add(value);
            }

            Assert.Equal(expectedValues.Length, set.Count);
            if (matchOrder)
            {
                Assert.Equal<T>(expectedValues, set.ToList());
            }
            else
            {
                CollectionAssertAreEquivalent(expectedValues, set.ToList());
            }
        }

        /// <summary>
        /// Tests various aspects of a set.  This should be called only from the unordered or sorted overloads of this method.
        /// </summary>
        /// <typeparam name="T">The type of element stored in the set.</typeparam>
        /// <param name="emptySet">The empty set.</param>
        protected static void EmptyTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> emptySet)
        {
            Assert.NotNull(emptySet);

            Assert.Equal(0, emptySet.Count); //, "Empty set should have a Count of 0");
            Assert.Equal(0, emptySet.Count()); //, "Enumeration of an empty set yielded elements.");
            Assert.True(IsSame(emptySet, emptySet.Clear()));
        }

        private IEnumerable<SetTriad> GetSetEqualsScenarios()
        {
            return new List<SetTriad>
            {
                new SetTriad(SetWith<int>(), Array.Empty<int>(), true),
                new SetTriad(SetWith<int>(5), new int[] { 5 }, true),
                new SetTriad(SetWith<int>(5), new int[] { 5, 5 }, true),
                new SetTriad(SetWith<int>(5, 8), new int[] { 5, 5 }, false),
                new SetTriad(SetWith<int>(5, 8), new int[] { 5, 7 }, false),
                new SetTriad(SetWith<int>(5, 8), new int[] { 5, 8 }, true),
                new SetTriad(SetWith<int>(5), Array.Empty<int>(), false),
                new SetTriad(SetWith<int>(), new int[] { 5 }, false),
                new SetTriad(SetWith<int>(5, 8), new int[] { 5 }, false),
                new SetTriad(SetWith<int>(5), new int[] { 5, 8 }, false),
                new SetTriad(SetWith<int>(5, 8), SetWith<int>(5, 8), true),
            };
        }

        private static IEnumerable<SetTriad> GetIsProperSubsetOfScenarios()
        {
            return new List<SetTriad>
            {
                new SetTriad(Array.Empty<int>(), Array.Empty<int>(), false),
                new SetTriad(new int[] { 1 }, Array.Empty<int>(), false),
                new SetTriad(new int[] { 1 }, new int[] { 2 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 2, 3 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 1, 2 }, true),
                new SetTriad(Array.Empty<int>(), new int[] { 1 }, true),
            };
        }

        private static IEnumerable<SetTriad> GetIsSubsetOfScenarios()
        {
            var results = new List<SetTriad>
            {
                new SetTriad(Array.Empty<int>(), Array.Empty<int>(), true),
                new SetTriad(new int[] { 1 }, new int[] { 1 }, true),
                new SetTriad(new int[] { 1, 2 }, new int[] { 1, 2 }, true),
                new SetTriad(new int[] { 1 }, Array.Empty<int>(), false),
                new SetTriad(new int[] { 1 }, new int[] { 2 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 2, 3 }, false),
            };

            // By definition, any proper subset is also a subset.
            // But because a subset may not be a proper subset, we filter the proper- scenarios.
            results.AddRange(GetIsProperSubsetOfScenarios().Where(s => s.Item3));
            return results;
        }

        private static IEnumerable<SetTriad> GetOverlapsScenarios()
        {
            return new List<SetTriad>
            {
                new SetTriad(Array.Empty<int>(), Array.Empty<int>(), false),
                new SetTriad(Array.Empty<int>(), new int[] { 1 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 2 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 2, 3 }, false),
                new SetTriad(new int[] { 1, 2 }, new int[] { 3 }, false),
                new SetTriad(new int[] { 1 }, new int[] { 1, 2 }, true),
                new SetTriad(new int[] { 1, 2 }, new int[] { 1 }, true),
                new SetTriad(new int[] { 1 }, new int[] { 1 }, true),
                new SetTriad(new int[] { 1, 2 }, new int[] { 2, 3, 4 }, true),
            };
        }

        private void SetCompareTestHelper<T>(Func<System.Collections.Immutable.IImmutableSet<T>, Func<IEnumerable<T>, bool>> operation, Func<ISet<T>, Func<IEnumerable<T>, bool>> baselineOperation, IEnumerable<Tuple<IEnumerable<T>, IEnumerable<T>, bool>> scenarios)
        {
            //const string message = "Scenario #{0}: Set 1: {1}, Set 2: {2}";

            int iteration = 0;
            foreach (var scenario in scenarios)
            {
                iteration++;

                // Figure out the response expected based on the BCL mutable collections.
                var baselineSet = this.EmptyMutable<T>();
                baselineSet.UnionWith(scenario.Item1);
                var expectedFunc = baselineOperation(baselineSet);
                bool expected = expectedFunc(scenario.Item2);
                Assert.Equal(expected, scenario.Item3); //, "Test scenario has an expected result that is inconsistent with BCL mutable collection behavior.");

                var actualFunc = operation(this.SetWith(scenario.Item1.ToArray()));
                var args = new object[] { iteration, ToStringDeferred(scenario.Item1), ToStringDeferred(scenario.Item2) };
                Assert.Equal(scenario.Item3, actualFunc(this.SetWith(scenario.Item2.ToArray()))); //, message, args);
                Assert.Equal(scenario.Item3, actualFunc(scenario.Item2)); //, message, args);
            }
        }

        private static Tuple<IEnumerable<T>, IEnumerable<T>, bool> Flip<T>(Tuple<IEnumerable<T>, IEnumerable<T>, bool> scenario)
        {
            return new Tuple<IEnumerable<T>, IEnumerable<T>, bool>(scenario.Item2, scenario.Item1, scenario.Item3);
        }

        private static void RemoveTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> set, params T[] values)
        {
            Assert.NotNull(set);
            Assert.NotNull(values);

            Assert.True(IsSame(set, set.Except(Enumerable.Empty<T>())));

            int initialCount = set.Count;
            int removedCount = 0;
            foreach (T value in values)
            {
                var nextSet = set.Remove(value);
                Assert.NotSame(set, nextSet);
                Assert.Equal(initialCount - removedCount, set.Count);
                Assert.Equal(initialCount - removedCount - 1, nextSet.Count);

                Assert.True(IsSame(nextSet, nextSet.Remove(value))); //, "Removing a non-existing element should not change the set reference.");
                removedCount++;
                set = nextSet;
            }

            Assert.Equal(initialCount - removedCount, set.Count);
        }

        private static void AddRemoveLoadTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> set, T[] data)
        {
            Assert.NotNull(set);
            Assert.NotNull(data);

            foreach (T value in data)
            {
                var newSet = set.Add(value);
                Assert.NotSame(set, newSet);
                set = newSet;
            }

            foreach (T value in data)
            {
                Assert.True(set.Contains(value));
            }

            foreach (T value in data)
            {
                var newSet = set.Remove(value);
                Assert.NotSame(set, newSet);
                set = newSet;
            }
        }

        protected static void EnumeratorTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> emptySet, IComparer<T>? comparer, params T[] values)
        {
            var set = emptySet;
            foreach (T value in values)
            {
                set = set.Add(value);
            }

            var nonGenericEnumerableList = ToListNonGeneric<T>(set);
            CollectionAssertAreEquivalent(nonGenericEnumerableList, values);

            var list = set.ToList();
            CollectionAssertAreEquivalent(list, values);

            if (comparer != null)
            {
                Array.Sort(values, comparer);
                Assert.Equal<T>(values, list);
            }

            // Apply some less common uses to the enumerator to test its metal.
            IEnumerator<T> enumerator;
            using (enumerator = set.GetEnumerator())
            {
                Assert.Equal(default, enumerator.Current);
                enumerator.Reset(); // reset isn't usually called before MoveNext
                Assert.Equal(default, enumerator.Current);
                ManuallyEnumerateTest(list, enumerator);
                Assert.False(enumerator.MoveNext()); // call it again to make sure it still returns false

                enumerator.Reset();
                Assert.Equal(default, enumerator.Current);
                ManuallyEnumerateTest(list, enumerator);
                Assert.Equal(default, enumerator.Current);

                // this time only partially enumerate
                enumerator.Reset();
                enumerator.MoveNext();
                enumerator.Reset();
                ManuallyEnumerateTest(list, enumerator);
            }

            enumerator.Reset();
            Assert.True(enumerator.MoveNext());
            Assert.Equal(set.First(), enumerator.Current);
        }

        private static void AddTestHelper<T>(System.Collections.Immutable.IImmutableSet<T> set, params T[] values)
        {
            Assert.NotNull(set);
            Assert.NotNull(values);

            Assert.True(IsSame(set, set.Union(Enumerable.Empty<T>())));

            int initialCount = set.Count;

            var uniqueValues = new HashSet<T>(values);
            var enumerateAddSet = set.Union(values);
            Assert.Equal(initialCount + uniqueValues.Count, enumerateAddSet.Count);
            foreach (T value in values)
            {
                Assert.True(enumerateAddSet.Contains(value));
            }

            int addedCount = 0;
            foreach (T value in values)
            {
                bool duplicate = set.Contains(value);
                var nextSet = set.Add(value);
                Assert.True(nextSet.Count > 0);
                Assert.Equal(initialCount + addedCount, set.Count);
                int expectedCount = initialCount + addedCount;
                if (!duplicate)
                {
                    expectedCount++;
                }
                Assert.Equal(expectedCount, nextSet.Count);
                Assert.Equal(duplicate, set.Contains(value));
                Assert.True(nextSet.Contains(value));
                if (!duplicate)
                {
                    addedCount++;
                }

                // Next assert temporarily disabled because Roslyn's set doesn't follow this rule.
                Assert.True(IsSame(nextSet, nextSet.Add(value))); //, "Adding duplicate value {0} should keep the original reference.", value);
                set = nextSet;
            }
        }
    }
}