File: FindSymbols\FindReferences\FindReferencesSearchEngine_FindReferencesInDocuments.cs
Web Access
Project: src\src\Workspaces\Core\Portable\Microsoft.CodeAnalysis.Workspaces.csproj (Microsoft.CodeAnalysis.Workspaces)
// 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.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.CodeAnalysis.FindSymbols.Finders;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Shared.Extensions;
using Microsoft.CodeAnalysis.Shared.Utilities;
 
namespace Microsoft.CodeAnalysis.FindSymbols;
 
internal sealed partial class FindReferencesSearchEngine
{
    public async Task FindReferencesInDocumentsAsync(
        ISymbol originalSymbol, IImmutableSet<Document> documents, CancellationToken cancellationToken)
    {
        // Caller needs to pass unidirectional cascading to make this search efficient.  If we only have
        // unidirectional cascading, then we only need to check the potential matches we find in the file against
        // the starting symbol.
        Debug.Assert(_options.UnidirectionalHierarchyCascade);
 
        // Mapping from symbols (unified across metadata/retargeting) and the set of symbols that was produced for 
        // them in the case of linked files across projects.  This allows references to be found to any of the unified
        // symbols, while the user only gets a single reported group back that corresponds to that entire set.
        //
        // This is a normal dictionary that is not locked.  It is only ever read and written to serially from within the
        // high level project-walking code in this method.
        using var _ = s_symbolToGroupPool.GetPooledObject(out var symbolToGroup);
 
        var unifiedSymbols = new MetadataUnifyingSymbolHashSet
        {
            originalSymbol
        };
 
        // As we hit symbols, we may have to compute if they have an inheritance relationship to the symbols we're
        // searching for.  Cache those results so we don't have to continually perform them.
        //
        // Note: this is a dictionary as we do all our work serially (though asynchronously).  If we ever change to
        // doing things concurrently, this will need to be changed.
        var hasInheritanceRelationshipCache = new Dictionary<(ISymbol searchSymbol, ISymbol candidateSymbol), bool>();
 
        // Create and report the initial set of symbols to search for.  This includes linked and cascaded symbols. It does
        // not walk up/down the inheritance hierarchy.
        var symbolSet = await SymbolSet.DetermineInitialSearchSymbolsAsync(this, unifiedSymbols, cancellationToken).ConfigureAwait(false);
 
        // Safe to call as we're in the entry-point method, and nothing is running concurrently with this call.
        var allSymbolsAndGroups = await ReportGroupsSeriallyAsync(
            [.. symbolSet], symbolToGroup, cancellationToken).ConfigureAwait(false);
 
        // Process projects in dependency graph order so that any compilations built by one are available for later
        // projects. We only have to examine the projects containing the documents requested though.
        var dependencyGraph = _solution.GetProjectDependencyGraph();
        var projectsToSearch = documents.Select(d => d.Project).Where(p => p.SupportsCompilation).ToImmutableHashSet();
 
        foreach (var projectId in dependencyGraph.GetTopologicallySortedProjects(cancellationToken))
        {
            var currentProject = _solution.GetRequiredProject(projectId);
            if (!projectsToSearch.Contains(currentProject))
                continue;
 
            // Safe to call as we're in the entry-point method, and it's only serially looping over the projects when
            // calling into this.
            await PerformSearchInProjectSeriallyAsync(allSymbolsAndGroups, currentProject).ConfigureAwait(false);
        }
 
        return;
 
        async ValueTask PerformSearchInProjectSeriallyAsync(ImmutableArray<(ISymbol symbol, SymbolGroup group)> symbols, Project project)
        {
            using var _ = PooledDictionary<ISymbol, PooledHashSet<string>>.GetInstance(out var symbolToGlobalAliases);
            try
            {
                // Compute global aliases up front for the project so it can be used below for all the symbols we're
                // searching for.
                await AddGlobalAliasesAsync(project, symbols, symbolToGlobalAliases, cancellationToken).ConfigureAwait(false);
 
                foreach (var document in documents)
                {
                    if (document.Project != project)
                        continue;
 
                    // Safe to call as we're only in a serial context ourselves.
                    await PerformSearchInDocumentSeriallyAsync(symbols, document, symbolToGlobalAliases).ConfigureAwait(false);
                }
            }
            finally
            {
                FreeGlobalAliases(symbolToGlobalAliases);
            }
        }
 
        async ValueTask PerformSearchInDocumentSeriallyAsync(
            ImmutableArray<(ISymbol symbol, SymbolGroup group)> symbols,
            Document document,
            PooledDictionary<ISymbol, PooledHashSet<string>> symbolToGlobalAliases)
        {
            // We're doing to do all of our processing of this document at once.  This will necessitate all the
            // appropriate finders checking this document for hits.  We're likely going to need to perform syntax
            // and semantics checks in this file.  So just grab those once here and hold onto them for the lifetime
            // of this call.
            var cache = await FindReferenceCache.GetCacheAsync(document, cancellationToken).ConfigureAwait(false);
 
            foreach (var (symbol, group) in symbols)
            {
                var state = new FindReferencesDocumentState(
                    cache, TryGet(symbolToGlobalAliases, symbol));
 
                // Safe to call as we're only in a serial context ourselves.
                await PerformSearchInDocumentSeriallyWorkerAsync(symbol, group, state).ConfigureAwait(false);
            }
        }
 
        async ValueTask PerformSearchInDocumentSeriallyWorkerAsync(
            ISymbol symbol, SymbolGroup group, FindReferencesDocumentState state)
        {
            // Always perform a normal search, looking for direct references to exactly that symbol.
            await DirectSymbolSearchAsync(symbol, group, state).ConfigureAwait(false);
 
            // Now, for symbols that could involve inheritance, look for references to the same named entity, and
            // see if it's a reference to a symbol that shares an inheritance relationship with that symbol.
            //
            // Safe to call as we're only in a serial context ourselves.
            await InheritanceSymbolSearchSeriallyAsync(symbol, state).ConfigureAwait(false);
        }
 
        async ValueTask DirectSymbolSearchAsync(ISymbol symbol, SymbolGroup group, FindReferencesDocumentState state)
        {
            await ProducerConsumer<FinderLocation>.RunAsync(
                ProducerConsumerOptions.SingleReaderWriterOptions,
                static (callback, args, cancellationToken) =>
                {
                    var (@this, symbol, group, state) = args;
 
                    // We don't bother calling into the finders in parallel as there's only ever one that applies for a
                    // particular symbol kind.  All the rest bail out immediately after a quick type-check.  So there's
                    // no benefit in forking out to have only one of them end up actually doing work.
                    foreach (var finder in @this._finders)
                    {
                        finder.FindReferencesInDocument(
                            symbol, state,
                            static (finderLocation, callback) => callback(finderLocation),
                            callback, @this._options, cancellationToken);
                    }
 
                    return Task.CompletedTask;
                },
                consumeItems: static async (values, args, cancellationToken) =>
                {
                    var (@this, symbol, group, state) = args;
                    var converted = await ConvertLocationsAsync(@this, values, symbol, group, cancellationToken).ConfigureAwait(false);
                    await @this._progress.OnReferencesFoundAsync(converted, cancellationToken).ConfigureAwait(false);
                },
                args: (@this: this, symbol, group, state),
                cancellationToken).ConfigureAwait(false);
        }
 
        static async Task<ImmutableArray<(SymbolGroup group, ISymbol symbol, ReferenceLocation location)>> ConvertLocationsAsync(
            FindReferencesSearchEngine @this, IAsyncEnumerable<FinderLocation> locations, ISymbol symbol, SymbolGroup group, CancellationToken cancellationToken)
        {
            using var _ = ArrayBuilder<(SymbolGroup group, ISymbol symbol, ReferenceLocation location)>.GetInstance(out var result);
 
            // Transform the individual finder-location objects to "group/symbol/location" tuples.
            await foreach (var location in locations)
                result.Add((group, symbol, location.Location));
 
            return result.ToImmutableAndClear();
        }
 
        async ValueTask InheritanceSymbolSearchSeriallyAsync(ISymbol symbol, FindReferencesDocumentState state)
        {
            if (InvolvesInheritance(symbol))
            {
                var tokens = AbstractReferenceFinder.FindMatchingIdentifierTokens(state, symbol.Name, cancellationToken);
 
                foreach (var token in tokens)
                {
                    var parent = state.SyntaxFacts.TryGetBindableParent(token) ?? token.GetRequiredParent();
                    var symbolInfo = state.Cache.GetSymbolInfo(parent, cancellationToken);
 
                    var (matched, candidate, candidateReason) = await HasInheritanceRelationshipAsync(symbol, symbolInfo).ConfigureAwait(false);
                    if (matched)
                    {
                        // Ensure we report this new symbol/group in case it's the first time we're seeing it.
                        // Safe to call this as we're only being called from within a serial context ourselves.
                        var candidateGroup = await ReportGroupSeriallyAsync(
                            candidate, symbolToGroup, cancellationToken).ConfigureAwait(false);
 
                        var location = AbstractReferenceFinder.CreateReferenceLocation(state, token, candidateReason, cancellationToken);
                        await _progress.OnReferencesFoundAsync([(candidateGroup, candidate, location)], cancellationToken).ConfigureAwait(false);
                    }
                }
            }
        }
 
        async ValueTask<(bool matched, ISymbol candidate, CandidateReason candidateReason)> HasInheritanceRelationshipAsync(
            ISymbol symbol, SymbolInfo symbolInfo)
        {
            if (await HasInheritanceRelationshipSingleAsync(symbol, symbolInfo.Symbol).ConfigureAwait(false))
                return (matched: true, symbolInfo.Symbol!, CandidateReason.None);
 
            foreach (var candidate in symbolInfo.CandidateSymbols)
            {
                if (await HasInheritanceRelationshipSingleAsync(symbol, candidate).ConfigureAwait(false))
                    return (matched: true, candidate, symbolInfo.CandidateReason);
            }
 
            return default;
        }
 
        async ValueTask<bool> HasInheritanceRelationshipSingleAsync(ISymbol searchSymbol, [NotNullWhen(true)] ISymbol? candidate)
        {
            if (candidate is null)
                return false;
 
            var key = (searchSymbol: searchSymbol.GetOriginalUnreducedDefinition(), candidate: candidate.GetOriginalUnreducedDefinition());
            if (!hasInheritanceRelationshipCache.TryGetValue(key, out var relationship))
            {
                relationship = await ComputeInheritanceRelationshipAsync(key.searchSymbol, key.candidate).ConfigureAwait(false);
                hasInheritanceRelationshipCache[key] = relationship;
            }
 
            return relationship;
        }
 
        async Task<bool> ComputeInheritanceRelationshipAsync(
            ISymbol searchSymbol, ISymbol candidate)
        {
            // Counter-intuitive, but if these are matching symbols, they do *not* have an inheritance relationship.
            // We do *not* want to report these as they would have been found in the original call to the finders in
            // PerformSearchInTextSpanAsync.
            if (SymbolFinder.OriginalSymbolsMatch(_solution, searchSymbol, candidate))
                return false;
 
            // walk up the original symbol's inheritance hierarchy to see if we hit the candidate. Don't walk down
            // derived types here.  The point of this algorithm is to only walk upwards looking for matches.
            var searchSymbolUpSet = await SymbolSet.CreateAsync(
                this, [searchSymbol], includeImplementationsThroughDerivedTypes: false, cancellationToken).ConfigureAwait(false);
            foreach (var symbolUp in searchSymbolUpSet.GetAllSymbols())
            {
                if (SymbolFinder.OriginalSymbolsMatch(_solution, symbolUp, candidate))
                    return true;
            }
 
            // walk up the candidate's inheritance hierarchy to see if we hit the original symbol. Don't walk down
            // derived types here.  The point of this algorithm is to only walk upwards looking for matches.
            var candidateSymbolUpSet = await SymbolSet.CreateAsync(
                this, [candidate], includeImplementationsThroughDerivedTypes: false, cancellationToken).ConfigureAwait(false);
            foreach (var candidateUp in candidateSymbolUpSet.GetAllSymbols())
            {
                if (SymbolFinder.OriginalSymbolsMatch(_solution, searchSymbol, candidateUp))
                    return true;
            }
 
            return false;
        }
    }
}