﻿// 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 disable

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.Text;
using Roslyn.Test.Utilities;
using Xunit;

namespace Microsoft.CodeAnalysis.UnitTests
{
    /// <summary>
    /// Tests for CachingLookup.
    /// </summary>
    public class CachingLookupTests
    {
        private readonly Random _randomCaseGenerator = new Random(17);

        private int[] RandomNumbers(int length, int seed)
        {
            Random rand = new Random(seed);

            int[] result = new int[length];
            for (int i = 0; i < length; ++i)
            {
                result[i] = rand.Next(100, ((length / 10) + 4) * 100);
            }

            return result;
        }

        private SegmentedHashSet<string> Keys(int[] numbers, bool randomCase, IEqualityComparer<string> comparer)
        {
            var keys = new SegmentedHashSet<string>(comparer);
            foreach (var n in numbers)
            {
                keys.Add(GetKey(n, randomCase));
            }

            return keys;
        }

        private string GetKey(int number, bool randomCase)
        {
            if (randomCase)
            {
                bool upper = _randomCaseGenerator.Next(2) == 0;
                return (upper ? "AA" : "aa") + Right2Chars(number.ToString());
            }
            else
            {
                return "AA" + Right2Chars(number.ToString());
            }
        }

        private ImmutableArray<int> Values(string key, int[] numbers, bool ignoreCase)
        {
            return (from n in numbers
                    where string.Equals(GetKey(n, ignoreCase), key, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)
                    select n).ToArray().AsImmutableOrNull();
        }

        private ILookup<string, int> CreateLookup(int[] numbers, bool randomCase)
        {
            if (randomCase)
            {
                return numbers.ToLookup(n => GetKey(n, randomCase), StringComparer.OrdinalIgnoreCase);
            }
            else
            {
                return numbers.ToLookup(n => GetKey(n, randomCase), StringComparer.Ordinal);
            }
        }

        private string Right2Chars(string s)
        {
            return s.Substring(s.Length - 2);
        }

        private void CheckEqualEnumerable<T>(IEnumerable<T> e1, IEnumerable<T> e2)
        {
            List<T> l1 = e1.ToList();
            List<T> l2 = e2.ToList();

            Assert.Equal(l1.Count, l2.Count);

            foreach (T item in l1)
            {
                Assert.Contains(item, l2);
            }

            foreach (T item in l2)
            {
                Assert.Contains(item, l1);
            }
        }

        private void CompareLookups1(ILookup<string, int> look1, CachingDictionary<string, int> look2, SegmentedHashSet<string> keys)
        {
            foreach (string k in keys)
            {
                Assert.Equal(look1.Contains(k), look2.Contains(k));
                CheckEqualEnumerable(look1[k], look2[k]);
            }

            foreach (string k in new string[] { "goo", "bar", "banana", "flibber" })
            {
                Assert.False(look1.Contains(k));
                Assert.False(look2.Contains(k));
                Assert.Empty(look1[k]);
                Assert.Empty(look2[k]);
            }
        }

        private void CompareLookups2(ILookup<string, int> look1, CachingDictionary<string, int> look2, SegmentedHashSet<string> keys)
        {
            foreach (string k in look1.Select(g => g.Key))
            {
                CheckEqualEnumerable(look1[k], look2[k]);
            }

            foreach (string k in look2.Keys)
            {
                CheckEqualEnumerable(look1[k], look2[k]);
            }

            Assert.Equal(look1.Count, look2.Count);
        }

        private void CompareLookups2(CachingDictionary<string, int> look1, ILookup<string, int> look2, SegmentedHashSet<string> keys)
        {
            foreach (string k in look1.Keys)
            {
                CheckEqualEnumerable(look1[k], look2[k]);
            }

            foreach (string k in look2.Select(g => g.Key))
            {
                CheckEqualEnumerable(look1[k], look2[k]);
            }

            Assert.Equal(look1.Count, look2.Count);
        }

        [Fact]
        public void CachingLookupCorrectResults()
        {
            StringComparer comparer = StringComparer.Ordinal;
            int[] numbers = RandomNumbers(200, 11234);
            var dict = new Dictionary<string, ImmutableArray<int>>(comparer);
            foreach (string k in Keys(numbers, false, comparer))
            {
                dict.Add(k, Values(k, numbers, false));
            }

            var look1 = CreateLookup(numbers, false);
            var look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, false, comparer: c), comparer);
            CompareLookups1(look1, look2, Keys(numbers, false, comparer));

            look1 = CreateLookup(numbers, false);
            look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, false, comparer: c), comparer);
            CompareLookups2(look1, look2, Keys(numbers, false, comparer));
            CompareLookups1(look1, look2, Keys(numbers, false, comparer));

            look1 = CreateLookup(numbers, false);
            look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, false, comparer: c), comparer);
            CompareLookups2(look2, look1, Keys(numbers, false, comparer));
            CompareLookups1(look1, look2, Keys(numbers, false, comparer));
        }

        [Fact]
        public void CachingLookupCaseInsensitive()
        {
            StringComparer comparer = StringComparer.OrdinalIgnoreCase;
            int[] numbers = RandomNumbers(300, 719);
            var dict = new Dictionary<string, ImmutableArray<int>>(comparer);
            foreach (string k in Keys(numbers, false, comparer))
            {
                dict.Add(k, Values(k, numbers, false));
            }

            var look1 = CreateLookup(numbers, true);
            var look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));

            look1 = CreateLookup(numbers, true);
            look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups2(look1, look2, Keys(numbers, true, comparer));
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));

            look1 = CreateLookup(numbers, true);
            look2 = new CachingDictionary<string, int>(
                s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups2(look2, look1, Keys(numbers, true, comparer));
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));
        }

        [Fact]
        public void CachingLookupCaseInsensitiveNoCacheMissingKeys()
        {
            StringComparer comparer = StringComparer.OrdinalIgnoreCase;
            int[] numbers = RandomNumbers(435, 19874);
            var dict = new Dictionary<string, ImmutableArray<int>>(comparer);
            foreach (string k in Keys(numbers, false, comparer))
            {
                dict.Add(k, Values(k, numbers, false));
            }

            var look1 = CreateLookup(numbers, true);
            var look2 = new CachingDictionary<string, int>(s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                                                                        (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));

            look1 = CreateLookup(numbers, true);
            look2 = new CachingDictionary<string, int>(s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                                                   (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups2(look1, look2, Keys(numbers, true, comparer));
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));

            look1 = CreateLookup(numbers, true);
            look2 = new CachingDictionary<string, int>(s => dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>(),
                                                   (c) => Keys(numbers, true, comparer: c), comparer);
            CompareLookups2(look2, look1, Keys(numbers, true, comparer));
            CompareLookups1(look1, look2, Keys(numbers, true, comparer));
        }

        // Ensure that we are called back exactly once per key.
        [Fact]
        public void CallExactlyOncePerKey()
        {
            StringComparer comparer = StringComparer.OrdinalIgnoreCase;
            int[] numbers = RandomNumbers(435, 19874);
            var dict = new Dictionary<string, ImmutableArray<int>>(comparer);
            foreach (string k in Keys(numbers, false, comparer))
            {
                dict.Add(k, Values(k, numbers, false));
            }

            HashSet<string> lookedUp = new HashSet<string>(comparer);
            bool askedForKeys = false;

            var look1 = new CachingDictionary<string, int>(s =>
            {
                Assert.False(lookedUp.Contains(s));
                lookedUp.Add(s);
                return dict.TryGetValue(s, out var value) ? value : ImmutableArray.Create<int>();
            },
                 (c) =>
            {
                Assert.False(askedForKeys);
                askedForKeys = true;
                return Keys(numbers, true, comparer: c);
            }, comparer);

            string key1 = GetKey(numbers[0], false);
            string key2 = GetKey(numbers[1], false);
            string key3 = GetKey(numbers[2], false);

            ImmutableArray<int> retval;
            retval = look1[key1];
            retval = look1[key2];
            retval = look1[key3];
            retval = look1[key1];
            retval = look1[key2];
            retval = look1[key3];

            retval = look1[key1];
            retval = look1[key2];
            retval = look1[key3];
            retval = look1[key1];
            retval = look1[key2];
            retval = look1[key3];
        }

        [Fact]
        [WorkItem(60259, "https://github.com/dotnet/roslyn/issues/60259")]
        public void FullyPopulateRace_01()
        {
            CachingDictionary<int, FullyPopulateRaceHelper> lookup = null;
            FullyPopulateRaceHelper item = null;
            int itemAccessCount = 0;
            lookup = new CachingDictionary<int, FullyPopulateRaceHelper>(getElementsOfKey, getKeys, EqualityComparer<int>.Default);

            _ = lookup.Count;
            Assert.NotNull(item);
            Assert.Same(item, getItem());

            ImmutableArray<FullyPopulateRaceHelper> getElementsOfKey(int id)
            {
                itemAccessCount++;
                if (item is null && itemAccessCount == 1)
                {
                    item = getItem();
                }

                return ImmutableArray.Create<FullyPopulateRaceHelper>(new FullyPopulateRaceHelper());
            }

            SegmentedHashSet<int> getKeys(IEqualityComparer<int> comparer)
            {
                return new SegmentedHashSet<int>(new[] { 1 }, comparer);
            }

            FullyPopulateRaceHelper getItem()
            {
                return lookup[1][0];
            }
        }

        private class FullyPopulateRaceHelper { }

        [Fact]
        [WorkItem(60259, "https://github.com/dotnet/roslyn/issues/60259")]
        public void FullyPopulateRace_02()
        {
            CachingDictionary<int, FullyPopulateRaceHelper> lookup = null;
            FullyPopulateRaceHelper item = null;
            int itemAccessCount = 0;
            lookup = new CachingDictionary<int, FullyPopulateRaceHelper>(getElementsOfKey, getKeys, EqualityComparer<int>.Default);

            Assert.Empty(lookup[2]);
            _ = lookup.Count;
            Assert.NotNull(item);
            Assert.Same(item, getItem());

            ImmutableArray<FullyPopulateRaceHelper> getElementsOfKey(int id)
            {
                if (id != 1)
                {
                    return ImmutableArray<FullyPopulateRaceHelper>.Empty;
                }

                itemAccessCount++;
                if (item is null && itemAccessCount == 1)
                {
                    item = getItem();
                }

                return ImmutableArray.Create<FullyPopulateRaceHelper>(new FullyPopulateRaceHelper());
            }

            SegmentedHashSet<int> getKeys(IEqualityComparer<int> comparer)
            {
                return new SegmentedHashSet<int>(new[] { 1 }, comparer);
            }

            FullyPopulateRaceHelper getItem()
            {
                return lookup[1][0];
            }
        }
    }
}
