﻿// 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.Linq;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.Internal.Log;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Shared.Collections;
using Microsoft.CodeAnalysis.Shared.Extensions;
using Microsoft.CodeAnalysis.Shared.TestHooks;
using Microsoft.CodeAnalysis.Shared.Utilities;
using Roslyn.Utilities;

namespace Microsoft.CodeAnalysis.NavigateTo
{
    [Flags]
    internal enum NavigateToSearchScope
    {
        RegularDocuments = 0b01,
        GeneratedDocuments = 0b10,
        AllDocuments = RegularDocuments | GeneratedDocuments
    }

    internal class NavigateToSearcher
    {
        private readonly INavigateToSearcherHost _host;
        private readonly Solution _solution;
        private readonly INavigateToSearchCallback _callback;
        private readonly string _searchPattern;
        private readonly IImmutableSet<string> _kinds;
        private readonly IStreamingProgressTracker _progress_doNotAccessDirectly;

        private readonly Document? _activeDocument;
        private readonly ImmutableArray<Document> _visibleDocuments;

        private int _remainingProgressItems;

        private NavigateToSearcher(
            INavigateToSearcherHost host,
            Solution solution,
            INavigateToSearchCallback callback,
            string searchPattern,
            IImmutableSet<string> kinds)
        {
            _host = host;
            _solution = solution;
            _callback = callback;
            _searchPattern = searchPattern;
            _kinds = kinds;
            _progress_doNotAccessDirectly = new StreamingProgressTracker((current, maximum, ct) =>
            {
                callback.ReportProgress(current, maximum);
                return new ValueTask();
            });

            var docTrackingService = _solution.Services.GetRequiredService<IDocumentTrackingService>();

            // If the workspace is tracking documents, use that to prioritize our search
            // order.  That way we provide results for the documents the user is working
            // on faster than the rest of the solution.
            _activeDocument = docTrackingService.GetActiveDocument(_solution);
            _visibleDocuments = docTrackingService.GetVisibleDocuments(_solution)
                                                  .WhereAsArray(d => d != _activeDocument);
        }

        public static NavigateToSearcher Create(
            Solution solution,
            IAsynchronousOperationListener asyncListener,
            INavigateToSearchCallback callback,
            string searchPattern,
            IImmutableSet<string> kinds,
            CancellationToken disposalToken,
            INavigateToSearcherHost? host = null)
        {
            host ??= new DefaultNavigateToSearchHost(solution, asyncListener, disposalToken);
            return new NavigateToSearcher(host, solution, callback, searchPattern, kinds);
        }

        private async Task AddProgressItemsAsync(int count, CancellationToken cancellationToken)
        {
            Debug.Assert(count >= 0);
            Debug.Assert(_remainingProgressItems >= 0);
            Interlocked.Add(ref _remainingProgressItems, count);
            await _progress_doNotAccessDirectly.AddItemsAsync(count, cancellationToken).ConfigureAwait(false);
        }

        private async Task ProgressItemsCompletedAsync(int count, CancellationToken cancellationToken)
        {
            var newValue = Interlocked.Add(ref _remainingProgressItems, -count);
            Debug.Assert(newValue >= 0);
            await _progress_doNotAccessDirectly.ItemsCompletedAsync(count, cancellationToken).ConfigureAwait(false);
        }

        public Task SearchAsync(bool searchCurrentDocument, CancellationToken cancellationToken)
            => SearchAsync(searchCurrentDocument, NavigateToSearchScope.AllDocuments, cancellationToken);

        public async Task SearchAsync(
            bool searchCurrentDocument,
            NavigateToSearchScope scope,
            CancellationToken cancellationToken)
        {
            var isFullyLoaded = true;

            try
            {
                using var navigateToSearch = Logger.LogBlock(FunctionId.NavigateTo_Search, KeyValueLogMessage.Create(LogType.UserAction), cancellationToken);

                if (searchCurrentDocument)
                {
                    await SearchCurrentDocumentAsync(cancellationToken).ConfigureAwait(false);
                }
                else
                {
                    // We consider ourselves fully loaded when both the project system has completed loaded us, and we've
                    // totally hydrated the oop side.  Until that happens, we'll attempt to return cached data from languages
                    // that support that.
                    isFullyLoaded = await _host.IsFullyLoadedAsync(cancellationToken).ConfigureAwait(false);

                    // Let the UI know if we're not fully loaded (and then might be reporting cached results).
                    if (!isFullyLoaded)
                        _callback.ReportIncomplete();

                    await SearchAllProjectsAsync(isFullyLoaded, scope, cancellationToken).ConfigureAwait(false);
                }
            }
            finally
            {
                // Ensure that we actually complete all our remaining progress items so that the progress bar completes.
                await ProgressItemsCompletedAsync(_remainingProgressItems, cancellationToken).ConfigureAwait(false);
                Debug.Assert(_remainingProgressItems == 0);

                // Pass along isFullyLoaded so that the UI can show indication to users that results may be incomplete.
                _callback.Done(isFullyLoaded);
            }
        }

        private async Task SearchCurrentDocumentAsync(CancellationToken cancellationToken)
        {
            if (_activeDocument == null)
                return;

            var project = _activeDocument.Project;
            var service = _host.GetNavigateToSearchService(project);
            if (service == null)
                return;

            await AddProgressItemsAsync(1, cancellationToken).ConfigureAwait(false);
            await service.SearchDocumentAsync(
                _activeDocument, _searchPattern, _kinds, _activeDocument,
                r => _callback.AddItemAsync(project, r, cancellationToken),
                cancellationToken).ConfigureAwait(false);
        }

        private async Task SearchAllProjectsAsync(
            bool isFullyLoaded,
            NavigateToSearchScope scope,
            CancellationToken cancellationToken)
        {
            var seenItems = new HashSet<INavigateToSearchResult>(NavigateToSearchResultComparer.Instance);
            var orderedProjects = GetOrderedProjectsToProcess();

            var searchRegularDocuments = scope.HasFlag(NavigateToSearchScope.RegularDocuments);
            var searchGeneratedDocuments = scope.HasFlag(NavigateToSearchScope.GeneratedDocuments);
            Debug.Assert(searchRegularDocuments || searchGeneratedDocuments);

            var projectCount = orderedProjects.Sum(g => g.Length);

            if (isFullyLoaded)
            {
                // We may do up to two passes.  One for loaded docs.  One for source generated docs.
                await AddProgressItemsAsync(
                    projectCount * ((searchRegularDocuments ? 1 : 0) + (searchGeneratedDocuments ? 1 : 0)),
                    cancellationToken).ConfigureAwait(false);

                if (searchRegularDocuments)
                    await SearchFullyLoadedProjectsAsync(orderedProjects, seenItems, cancellationToken).ConfigureAwait(false);

                if (searchGeneratedDocuments)
                    await SearchGeneratedDocumentsAsync(seenItems, cancellationToken).ConfigureAwait(false);
            }
            else
            {
                // If we're not fully loaded, we only search regular documents.  Generated documents must wait until
                // we're fully loaded (and thus have all the information necessary to properly run generators).
                if (searchRegularDocuments)
                {
                    // We do at least two passes.  One for cached docs.  One for normal docs.
                    await AddProgressItemsAsync(
                        projectCount * 2,
                        cancellationToken).ConfigureAwait(false);

                    await SearchCachedDocumentsAsync(orderedProjects, seenItems, cancellationToken).ConfigureAwait(false);

                    // If searching cached data returned any results, then we're done.  We've at least shown some results
                    // to the user.  That will hopefully serve them well enough until the solution fully loads.
                    if (seenItems.Count > 0)
                        return;

                    await SearchFullyLoadedProjectsAsync(orderedProjects, seenItems, cancellationToken).ConfigureAwait(false);

                    // Report a telemetry event to track if we found uncached items after failing to find cached items.
                    // In practice if we see that we are always finding uncached items, then it's likely something
                    // has broken in the caching system since we would expect to normally find values there.  Specifically
                    // we expect: foundFullItems <<< not foundFullItems.
                    Logger.Log(FunctionId.NavigateTo_CacheItemsMiss, KeyValueLogMessage.Create(m => m["FoundFullItems"] = seenItems.Count > 0));
                }
            }
        }

        /// <summary>
        /// Returns a sequence of groups of projects to process.  The sequence is in priority order, and all projects in
        /// a particular group should be processed before the next group.  This allows us to associate CPU resources in
        /// likely areas the user wants, while also still allowing for good parallelization.  Specifically, we consider
        /// the active-document the most important to get results for, as some users use navigate-to to navigate within
        /// the doc they are editing.  So we want those results to appear as quick as possible, without the search for
        /// them contending with the searches for other projects for CPU time.
        /// </summary>
        private ImmutableArray<ImmutableArray<Project>> GetOrderedProjectsToProcess()
        {
            using var result = TemporaryArray<ImmutableArray<Project>>.Empty;

            using var _ = PooledHashSet<Project>.GetInstance(out var processedProjects);

            // First, if there's an active document, search that project first, prioritizing that active document and
            // all visible documents from it.
            if (_activeDocument != null)
            {
                processedProjects.Add(_activeDocument.Project);
                result.Add(ImmutableArray.Create(_activeDocument.Project));
            }

            // Next process all visible docs that were not from the active project.
            using var buffer = TemporaryArray<Project>.Empty;
            foreach (var doc in _visibleDocuments)
            {
                if (processedProjects.Add(doc.Project))
                    buffer.Add(doc.Project);
            }

            if (buffer.Count > 0)
                result.Add(buffer.ToImmutableAndClear());

            // Finally, process the remainder of projects
            foreach (var project in _solution.Projects)
            {
                if (processedProjects.Add(project))
                    buffer.Add(project);
            }

            if (buffer.Count > 0)
                result.Add(buffer.ToImmutableAndClear());

            return result.ToImmutableAndClear();
        }

        /// <summary>
        /// Given a search within a particular project, this returns any documents within that project that should take
        /// precedence when searching.  This allows results to get to the user more quickly for common cases (like using
        /// nav-to to find results in the file you currently have open
        /// </summary>
        private ImmutableArray<Document> GetPriorityDocuments(Project project)
        {
            using var _ = ArrayBuilder<Document>.GetInstance(out var result);
            if (_activeDocument?.Project == project)
                result.Add(_activeDocument);

            foreach (var doc in _visibleDocuments)
            {
                if (doc.Project == project)
                    result.Add(doc);
            }

            result.RemoveDuplicates();
            return result.ToImmutable();
        }

        private async Task ProcessOrderedProjectsAsync(
            bool parallel,
            ImmutableArray<ImmutableArray<Project>> orderedProjects,
            HashSet<INavigateToSearchResult> seenItems,
            Func<INavigateToSearchService, Project, Func<INavigateToSearchResult, Task>, Task> processProjectAsync,
            CancellationToken cancellationToken)
        {
            // Process each group one at a time.  However, in each group process all projects in parallel to get results
            // as quickly as possible.  The net effect of this is that we will search the active doc immediately, then
            // the open docs in parallel, then the rest of the projects after that.  Because the active/open docs should
            // be a far smaller set, those results should come in almost immediately in a prioritized fashion, with the
            // rest of the results following soon after as best as we can find them.
            foreach (var projectGroup in orderedProjects)
            {
                if (!parallel)
                {
                    foreach (var project in projectGroup)
                        await SearchCoreAsync(project).ConfigureAwait(false);
                }
                else
                {
                    var allTasks = projectGroup.Select(p => Task.Run(() => SearchCoreAsync(p), cancellationToken));
                    await Task.WhenAll(allTasks).ConfigureAwait(false);
                }
            }

            return;

            async Task SearchCoreAsync(Project project)
            {
                try
                {
                    // If they don't even support the service, then always show them as having done the
                    // complete search.  That way we don't call back into this project ever.
                    var service = _host.GetNavigateToSearchService(project);
                    if (service == null)
                        return;

                    await processProjectAsync(service, project, result =>
                    {
                        // If we're seeing a dupe in another project, then filter it out here.  The results from
                        // the individual projects will already contain the information about all the projects
                        // leading to a better condensed view that doesn't look like it contains duplicate info.
                        lock (seenItems)
                        {
                            if (!seenItems.Add(result))
                                return Task.CompletedTask;
                        }

                        return _callback.AddItemAsync(project, result, cancellationToken);
                    }).ConfigureAwait(false);
                }
                finally
                {
                    // after each project is searched, increment our progress.
                    await ProgressItemsCompletedAsync(count: 1, cancellationToken).ConfigureAwait(false);
                }
            }
        }

        private Task SearchFullyLoadedProjectsAsync(
            ImmutableArray<ImmutableArray<Project>> orderedProjects,
            HashSet<INavigateToSearchResult> seenItems,
            CancellationToken cancellationToken)
        {
            // Search the fully loaded project in parallel.  We know this will be called after we've already hydrated the 
            // oop side.  So all calls will immediately see the solution as ready on the other end, and can start checking
            // all the docs it has.  Most docs will then find a hit in the index and can return results immediately.  Docs
            // that are not in the cache can be rescanned and have their new index contents checked.
            return ProcessOrderedProjectsAsync(
                parallel: true,
                orderedProjects,
                seenItems,
                (s, p, cb) => s.SearchProjectAsync(p, GetPriorityDocuments(p), _searchPattern, _kinds, _activeDocument, cb, cancellationToken),
                cancellationToken);
        }

        private Task SearchCachedDocumentsAsync(
            ImmutableArray<ImmutableArray<Project>> orderedProjects,
            HashSet<INavigateToSearchResult> seenItems,
            CancellationToken cancellationToken)
        {
            // We search cached information in parallel.  This is because there's no syncing step when searching cached
            // docs.  As such, we can just send a request for all projects in parallel to our OOP host and have it read
            // and search the local DB easily.  The DB can easily scale to feed all the threads trying to read from it
            // and we can get high throughput just processing everything in parallel.
            return ProcessOrderedProjectsAsync(
                parallel: true,
                orderedProjects,
                seenItems,
                (s, p, cb) => s.SearchCachedDocumentsAsync(p, GetPriorityDocuments(p), _searchPattern, _kinds, _activeDocument, cb, cancellationToken),
                cancellationToken);
        }

        private Task SearchGeneratedDocumentsAsync(
            HashSet<INavigateToSearchResult> seenItems,
            CancellationToken cancellationToken)
        {
            // Process all projects, serially, in topological order.  Generating source can be expensive.  It requires
            // creating and processing the entire compilation for a project, which itself may require dependent compilations
            // as references.  These dependents might also be skeleton references in the case of cross language projects.
            //
            // As such, we always want to compute the information for one project before moving onto a project that depends on
            // it.  That way information is available as soon as possible, and then computation for it immediately benefits 
            // what comes next.  Importantly, this avoids the problem of picking a project deep in the dependency tree, which
            // then pulls on N other projects, forcing results for this single project to pay that full price (that would 
            // be paid when we hit these through a normal topological walk).
            //
            // Note the projects in each 'dependency set' are already sorted in topological order.  So they will process in
            // the desired order if we process serially.
            var allProjects = _solution.GetProjectDependencyGraph()
                                       .GetDependencySets(cancellationToken)
                                       .SelectAsArray(s => s.SelectAsArray(_solution.GetRequiredProject));

            return ProcessOrderedProjectsAsync(
                parallel: false,
                allProjects,
                seenItems,
                (s, p, cb) => s.SearchGeneratedDocumentsAsync(p, _searchPattern, _kinds, _activeDocument, cb, cancellationToken),
                cancellationToken);
        }
    }
}
