File: CodeRefactorings\SyncNamespace\AbstractChangeNamespaceService.cs
Web Access
Project: ..\..\..\src\Features\Core\Portable\Microsoft.CodeAnalysis.Features.csproj (Microsoft.CodeAnalysis.Features)
// 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.Linq;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.AddImport;
using Microsoft.CodeAnalysis.CodeCleanup;
using Microsoft.CodeAnalysis.CodeGeneration;
using Microsoft.CodeAnalysis.Editing;
using Microsoft.CodeAnalysis.FindSymbols;
using Microsoft.CodeAnalysis.Formatting;
using Microsoft.CodeAnalysis.Host;
using Microsoft.CodeAnalysis.LanguageService;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.RemoveUnnecessaryImports;
using Microsoft.CodeAnalysis.Shared.Extensions;
using Microsoft.CodeAnalysis.Simplification;
using Microsoft.CodeAnalysis.Text;
using Roslyn.Utilities;
 
namespace Microsoft.CodeAnalysis.ChangeNamespace
{
    /// <summary>
    /// This intermediate class is used to hide method `TryGetReplacementReferenceSyntax` from <see cref="IChangeNamespaceService" />.
    /// </summary>
    internal abstract class AbstractChangeNamespaceService : IChangeNamespaceService
    {
        public abstract Task<bool> CanChangeNamespaceAsync(Document document, SyntaxNode container, CancellationToken cancellationToken);
 
        public abstract Task<Solution> ChangeNamespaceAsync(Document document, SyntaxNode container, string targetNamespace, CodeCleanupOptionsProvider fallbackOptions, CancellationToken cancellationToken);
 
        public abstract Task<Solution?> TryChangeTopLevelNamespacesAsync(Document document, string targetNamespace, CodeCleanupOptionsProvider fallbackOptions, CancellationToken cancellationToken);
 
        /// <summary>
        /// Try to get a new node to replace given node, which is a reference to a top-level type declared inside the 
        /// namespace to be changed. If this reference is the right side of a qualified name, the new node returned would
        /// be the entire qualified name. Depends on whether <paramref name="newNamespaceParts"/> is provided, the name 
        /// in the new node might be qualified with this new namespace instead.
        /// </summary>
        /// <param name="reference">A reference to a type declared inside the namespace to be changed, which is calculated 
        /// based on results from `SymbolFinder.FindReferencesAsync`.</param>
        /// <param name="newNamespaceParts">If specified, the namespace of original reference will be replaced with given 
        /// namespace in the replacement node.</param>
        /// <param name="old">The node to be replaced. This might be an ancestor of original </param>
        /// <param name="new">The replacement node.</param>
        public abstract bool TryGetReplacementReferenceSyntax(SyntaxNode reference, ImmutableArray<string> newNamespaceParts, ISyntaxFactsService syntaxFacts, [NotNullWhen(returnValue: true)] out SyntaxNode? old, [NotNullWhen(returnValue: true)] out SyntaxNode? @new);
    }
 
    internal abstract class AbstractChangeNamespaceService<TNamespaceDeclarationSyntax, TCompilationUnitSyntax, TMemberDeclarationSyntax>
        : AbstractChangeNamespaceService
        where TNamespaceDeclarationSyntax : SyntaxNode
        where TCompilationUnitSyntax : SyntaxNode
        where TMemberDeclarationSyntax : SyntaxNode
    {
        private static readonly char[] s_dotSeparator = new[] { '.' };
 
        /// <summary>
        /// The annotation used to track applicable container in each document to be fixed.
        /// </summary>
        protected static SyntaxAnnotation ContainerAnnotation { get; } = new SyntaxAnnotation();
 
        protected static SyntaxAnnotation WarningAnnotation { get; }
            = CodeActions.WarningAnnotation.Create(
                FeaturesResources.Warning_colon_changing_namespace_may_produce_invalid_code_and_change_code_meaning);
 
        protected abstract TCompilationUnitSyntax ChangeNamespaceDeclaration(
            TCompilationUnitSyntax root, ImmutableArray<string> declaredNamespaceParts, ImmutableArray<string> targetNamespaceParts);
 
        protected abstract SyntaxList<TMemberDeclarationSyntax> GetMemberDeclarationsInContainer(SyntaxNode compilationUnitOrNamespaceDecl);
 
        protected abstract Task<SyntaxNode?> TryGetApplicableContainerFromSpanAsync(Document document, TextSpan span, CancellationToken cancellationToken);
 
        protected abstract string GetDeclaredNamespace(SyntaxNode container);
 
        /// <summary>
        /// Decide if we can change the namespace for provided <paramref name="container"/> based on the criteria listed for 
        /// <see cref="IChangeNamespaceService.CanChangeNamespaceAsync(Document, SyntaxNode, CancellationToken)"/>
        /// </summary>
        /// <returns>
        /// If namespace can be changed, returns a list of documents that linked to the provided document (including itself)
        /// and the corresponding container nodes in each document, which will later be used for annotation. Otherwise, a 
        /// default ImmutableArray is returned. Currently we only support linked document in multi-targeting project scenario.
        /// </returns>
        protected abstract Task<ImmutableArray<(DocumentId id, SyntaxNode container)>> GetValidContainersFromAllLinkedDocumentsAsync(Document document, SyntaxNode container, CancellationToken cancellationToken);
 
        private static bool IsValidContainer(SyntaxNode container)
            => container is TCompilationUnitSyntax or TNamespaceDeclarationSyntax;
 
        protected static bool IsGlobalNamespace(ImmutableArray<string> parts)
            => parts is [""];
 
        public override async Task<bool> CanChangeNamespaceAsync(Document document, SyntaxNode container, CancellationToken cancellationToken)
        {
            if (!IsValidContainer(container))
            {
                throw new ArgumentException(nameof(container));
            }
 
            var applicableContainers = await GetValidContainersFromAllLinkedDocumentsAsync(document, container, cancellationToken).ConfigureAwait(false);
            return !applicableContainers.IsDefault;
        }
 
        public override async Task<Solution?> TryChangeTopLevelNamespacesAsync(
            Document document,
            string targetNamespace,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            var syntaxFacts = document.GetRequiredLanguageService<ISyntaxFactsService>();
            var syntaxRoot = await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
 
            // Don't descend into anything other than top level declarations from the root.
            // ChangeNamespaceService only controls top level declarations right now.
            // Don't use namespaces that already match the target namespace
            var originalNamespaceDeclarations = await GetTopLevelNamespacesAsync(document, cancellationToken).ConfigureAwait(false);
 
            if (originalNamespaceDeclarations.Length == 0)
            {
                return null;
            }
 
            var semanticModel = await document.GetRequiredSemanticModelAsync(cancellationToken).ConfigureAwait(false);
            var originalNamespaceName = semanticModel.GetRequiredDeclaredSymbol(originalNamespaceDeclarations.First(), cancellationToken).ToDisplayString();
            var solution = document.Project.Solution;
 
            // Only loop as many top level namespace declarations as we originally had. 
            // Change namespace doesn't change this number, so this helps limit us and
            // rule out namespaces that didn't need to be changed
            for (var i = 0; i < originalNamespaceDeclarations.Length; i++)
            {
                var namespaceName = semanticModel.GetRequiredDeclaredSymbol(originalNamespaceDeclarations[i], cancellationToken).ToDisplayString();
                if (namespaceName != originalNamespaceName)
                {
                    // Skip all namespaces that didn't match the original namespace name that 
                    // we were syncing. 
                    continue;
                }
 
                syntaxRoot = await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
 
                // Since the original namespaces were retrieved before the document was modified
                // get the current top level namespaces. Since we're only renaming namespaces, the 
                // number and index of each is the same.
                var namespaces = await GetTopLevelNamespacesAsync(document, cancellationToken).ConfigureAwait(false);
                Debug.Assert(namespaces.Length == originalNamespaceDeclarations.Length);
 
                var namespaceToRename = namespaces[i];
                solution = await ChangeNamespaceAsync(document, namespaceToRename, targetNamespace, fallbackOptions, cancellationToken).ConfigureAwait(false);
                document = solution.GetRequiredDocument(document.Id);
            }
 
            return solution;
            static async Task<ImmutableArray<SyntaxNode>> GetTopLevelNamespacesAsync(Document document, CancellationToken cancellationToken)
            {
                var syntaxRoot = await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
                var syntaxFacts = document.GetRequiredLanguageService<ISyntaxFactsService>();
 
                return syntaxRoot
                    .DescendantNodes(n => !syntaxFacts.IsDeclaration(n))
                    .Where(syntaxFacts.IsBaseNamespaceDeclaration)
                    .ToImmutableArray();
            }
        }
 
        public override async Task<Solution> ChangeNamespaceAsync(
            Document document,
            SyntaxNode container,
            string targetNamespace,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            // Make sure given namespace name is valid, "" means global namespace.
            var syntaxFacts = document.GetRequiredLanguageService<ISyntaxFactsService>();
            if (targetNamespace == null
                || (targetNamespace.Length > 0 && !targetNamespace.Split(s_dotSeparator).All(syntaxFacts.IsValidIdentifier)))
            {
                throw new ArgumentException(nameof(targetNamespace));
            }
 
            if (!IsValidContainer(container))
            {
                throw new ArgumentException(nameof(container));
            }
 
            var solution = document.Project.Solution;
 
            var containersFromAllDocuments = await GetValidContainersFromAllLinkedDocumentsAsync(document, container, cancellationToken).ConfigureAwait(false);
            if (containersFromAllDocuments.IsDefault)
            {
                return solution;
            }
 
            // No action required if declared namespace already matches target.
            var declaredNamespace = GetDeclaredNamespace(container);
            if (syntaxFacts.StringComparer.Equals(targetNamespace, declaredNamespace))
            {
                return solution;
            }
 
            // Annotate the container nodes so we can still find and modify them after syntax tree has changed.
            var annotatedSolution = await AnnotateContainersAsync(solution, containersFromAllDocuments, cancellationToken).ConfigureAwait(false);
 
            // Here's the entire process for changing namespace:
            // 1. Change the namespace declaration, fix references and add imports that might be necessary.
            // 2. Explicitly merge the diff to get a new solution.
            // 3. Remove added imports that are unnecessary.
            // 4. Do another explicit diff merge based on last merged solution.
            //
            // The reason for doing explicit diff merge twice is so merging after remove unnecessary imports can be correctly handled.
 
            var documentIds = containersFromAllDocuments.SelectAsArray(pair => pair.id);
            var solutionAfterNamespaceChange = annotatedSolution;
            using var _ = PooledHashSet<DocumentId>.GetInstance(out var referenceDocuments);
 
            foreach (var documentId in documentIds)
            {
                var (newSolution, refDocumentIds) =
                    await ChangeNamespaceInSingleDocumentAsync(solutionAfterNamespaceChange, documentId, declaredNamespace, targetNamespace, fallbackOptions, cancellationToken)
                        .ConfigureAwait(false);
                solutionAfterNamespaceChange = newSolution;
                referenceDocuments.AddRange(refDocumentIds);
            }
 
            var solutionAfterFirstMerge = await MergeDiffAsync(solution, solutionAfterNamespaceChange, cancellationToken).ConfigureAwait(false);
 
            // After changing documents, we still need to remove unnecessary imports related to our change.
            // We don't try to remove all imports that might become unnecessary/invalid after the namespace change, 
            // just ones that fully match the old/new namespace. Because it's hard to get it right and will almost 
            // certainly cause perf issue.
            // For example, if we are changing namespace `Foo.Bar` (which is the only namespace declaration with such name)
            // to `A.B`, the using of name `Bar` in a different file below would remain untouched, even it's no longer valid:
            //
            //      namespace Foo
            //      {
            //          using Bar;
            //          ~~~~~~~~~
            //      }
            //
            // Also, because we may have added different imports to document that triggered the refactoring
            // and the documents that reference affected types declared in changed namespace, we try to remove
            // unnecessary imports separately.
 
            var solutionAfterImportsRemoved = await RemoveUnnecessaryImportsAsync(
                solutionAfterFirstMerge,
                documentIds,
                GetAllNamespaceImportsForDeclaringDocument(declaredNamespace, targetNamespace),
                fallbackOptions,
                cancellationToken).ConfigureAwait(false);
 
            solutionAfterImportsRemoved = await RemoveUnnecessaryImportsAsync(
                solutionAfterImportsRemoved,
                referenceDocuments.ToImmutableArray(),
                ImmutableArray.Create(declaredNamespace, targetNamespace),
                fallbackOptions,
                cancellationToken).ConfigureAwait(false);
 
            return await MergeDiffAsync(solutionAfterFirstMerge, solutionAfterImportsRemoved, cancellationToken).ConfigureAwait(false);
        }
 
        protected async Task<ImmutableArray<(DocumentId, SyntaxNode)>> TryGetApplicableContainersFromAllDocumentsAsync(
            Solution solution,
            ImmutableArray<DocumentId> ids,
            TextSpan span,
            CancellationToken cancellationToken)
        {
            // If the node specified by span doesn't meet the requirement to be an applicable container in any of the documents 
            // (See `TryGetApplicableContainerFromSpanAsync`), or we are getting different namespace declarations among 
            // those documents, then we know we can't make a proper code change. We will return null and the check 
            // will return false. We use span of namespace declaration found in each document to decide if they are identical.            
 
            var documents = ids.SelectAsArray(solution.GetRequiredDocument);
            using var _1 = ArrayBuilder<(DocumentId, SyntaxNode)>.GetInstance(ids.Length, out var containers);
            using var _2 = PooledHashSet<TextSpan>.GetInstance(out var spanForContainers);
 
            foreach (var document in documents)
            {
                var container = await TryGetApplicableContainerFromSpanAsync(document, span, cancellationToken).ConfigureAwait(false);
 
                if (container is TNamespaceDeclarationSyntax)
                {
                    spanForContainers.Add(container.Span);
                }
                else if (container is TCompilationUnitSyntax)
                {
                    // In case there's no namespace declaration in the document, we used an empty span as key, 
                    // since a valid namespace declaration node can't have zero length.
                    spanForContainers.Add(default);
                }
                else
                {
                    return default;
                }
 
                containers.Add((document.Id, container));
            }
 
            return spanForContainers.Count == 1 ? containers.ToImmutable() : default;
        }
 
        /// <summary>
        /// Mark container nodes with our annotation so we can keep track of them across syntax modifications.
        /// </summary>
        protected static async Task<Solution> AnnotateContainersAsync(Solution solution, ImmutableArray<(DocumentId, SyntaxNode)> containers, CancellationToken cancellationToken)
        {
            var solutionEditor = new SolutionEditor(solution);
            foreach (var (id, container) in containers)
            {
                var documentEditor = await solutionEditor.GetDocumentEditorAsync(id, cancellationToken).ConfigureAwait(false);
                documentEditor.ReplaceNode(container, container.WithAdditionalAnnotations(ContainerAnnotation));
            }
 
            return solutionEditor.GetChangedSolution();
        }
 
        protected async Task<bool> ContainsPartialTypeWithMultipleDeclarationsAsync(
            Document document, SyntaxNode container, CancellationToken cancellationToken)
        {
            var memberDecls = GetMemberDeclarationsInContainer(container);
            var semanticModel = await document.GetRequiredSemanticModelAsync(cancellationToken).ConfigureAwait(false);
            var semanticFacts = document.GetRequiredLanguageService<ISemanticFactsService>();
 
            foreach (var memberDecl in memberDecls)
            {
                var memberSymbol = semanticModel.GetDeclaredSymbol(memberDecl, cancellationToken);
 
                // Simplify the check by assuming no multiple partial declarations in one document
                if (memberSymbol is ITypeSymbol typeSymbol
                    && typeSymbol.DeclaringSyntaxReferences.Length > 1
                    && semanticFacts.IsPartial(typeSymbol, cancellationToken))
                {
                    return true;
                }
            }
 
            return false;
        }
 
        protected static bool IsSupportedLinkedDocument(Document document, out ImmutableArray<DocumentId> allDocumentIds)
        {
            var solution = document.Project.Solution;
            var linkedDocumentIds = document.GetLinkedDocumentIds();
 
            // TODO: figure out how to properly determine if and how a document is linked using project system.
 
            // If we found a linked document which is part of a project with different project file,
            // then it's an actual linked file (i.e. not a multi-targeting project). We don't support that for now.
            if (linkedDocumentIds.Any(static (id, arg) =>
                    !PathUtilities.PathsEqual(arg.solution.GetRequiredDocument(id).Project.FilePath!, arg.document.Project.FilePath!), (solution, document)))
            {
                allDocumentIds = default;
                return false;
            }
 
            allDocumentIds = linkedDocumentIds.Add(document.Id);
            return true;
        }
 
        private async Task<ImmutableArray<ISymbol>> GetDeclaredSymbolsInContainerAsync(
            Document document,
            SyntaxNode container,
            CancellationToken cancellationToken)
        {
            var semanticModel = await document.GetRequiredSemanticModelAsync(cancellationToken).ConfigureAwait(false);
            var declarations = GetMemberDeclarationsInContainer(container);
            var builder = ArrayBuilder<ISymbol>.GetInstance();
 
            foreach (var declaration in declarations)
            {
                var symbol = semanticModel.GetDeclaredSymbol(declaration, cancellationToken);
                builder.AddIfNotNull(symbol);
            }
 
            return builder.ToImmutableAndFree();
        }
 
        private static ImmutableArray<string> GetNamespaceParts(string @namespace)
            => @namespace?.Split(s_dotSeparator).ToImmutableArray() ?? default;
 
        private static ImmutableArray<string> GetAllNamespaceImportsForDeclaringDocument(string oldNamespace, string newNamespace)
        {
            var parts = GetNamespaceParts(oldNamespace);
            var builder = ArrayBuilder<string>.GetInstance();
            for (var i = 1; i <= parts.Length; ++i)
            {
                builder.Add(string.Join(".", parts.Take(i)));
            }
 
            builder.Add(newNamespace);
 
            return builder.ToImmutableAndFree();
        }
 
        private static ImmutableArray<SyntaxNode> CreateImports(Document document, ImmutableArray<string> names, bool withFormatterAnnotation)
        {
            var generator = SyntaxGenerator.GetGenerator(document);
            using var _ = ArrayBuilder<SyntaxNode>.GetInstance(names.Length, out var builder);
            for (var i = 0; i < names.Length; ++i)
                builder.Add(CreateImport(generator, names[i], withFormatterAnnotation));
 
            return builder.ToImmutableAndClear();
        }
 
        private static SyntaxNode CreateImport(SyntaxGenerator syntaxGenerator, string name, bool withFormatterAnnotation)
        {
            var import = syntaxGenerator.NamespaceImportDeclaration(name);
            if (withFormatterAnnotation)
            {
                import = import.WithAdditionalAnnotations(Formatter.Annotation);
            }
 
            return import;
        }
 
        /// <summary>
        /// Try to change the namespace declaration in the document (specified by <paramref name="id"/> in <paramref name="solution"/>).
        /// Returns a new solution after changing namespace, and a list of IDs for documents that also changed because they reference
        /// the types declared in the changed namespace (not include the document contains the declaration itself).
        /// </summary>
        private async Task<(Solution, ImmutableArray<DocumentId>)> ChangeNamespaceInSingleDocumentAsync(
            Solution solution,
            DocumentId id,
            string oldNamespace,
            string newNamespace,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            var document = solution.GetRequiredDocument(id);
            var root = await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
            var container = root.GetAnnotatedNodes(ContainerAnnotation).Single();
 
            // Get types declared in the changing namespace, because we need to fix all references to them, 
            // e.g. change the namespace for qualified name, add imports to proper containers, etc.
            var declaredSymbols = await GetDeclaredSymbolsInContainerAsync(document, container, cancellationToken).ConfigureAwait(false);
 
            var editor = await DocumentEditor.CreateAsync(document, cancellationToken).ConfigureAwait(false);
 
            // Separating references to declaredSymbols into two groups based on whether it's located in the same 
            // document as the namespace declaration. This is because code change required for them are different.
            var refLocationsInCurrentDocument = new List<LocationForAffectedSymbol>();
            var refLocationsInOtherDocuments = new List<LocationForAffectedSymbol>();
 
            var refLocations = await Task.WhenAll(
                declaredSymbols.Select(declaredSymbol
                    => FindReferenceLocationsForSymbolAsync(document, declaredSymbol, cancellationToken))).ConfigureAwait(false);
 
            foreach (var refLocation in refLocations.SelectMany(locs => locs))
            {
                if (refLocation.Document.Id == document.Id)
                {
                    refLocationsInCurrentDocument.Add(refLocation);
                }
                else
                {
                    RoslynDebug.AssertNotNull(refLocation.Document.FilePath);
                    RoslynDebug.AssertNotNull(document.FilePath);
                    Debug.Assert(!PathUtilities.PathsEqual(refLocation.Document.FilePath, document.FilePath));
                    refLocationsInOtherDocuments.Add(refLocation);
                }
            }
 
            var documentWithNewNamespace = await FixDeclarationDocumentAsync(document, refLocationsInCurrentDocument, oldNamespace, newNamespace, fallbackOptions, cancellationToken)
                .ConfigureAwait(false);
            var solutionWithChangedNamespace = documentWithNewNamespace.Project.Solution;
 
            var refLocationGroups = refLocationsInOtherDocuments.GroupBy(loc => loc.Document.Id);
 
            var fixedDocuments = await Task.WhenAll(
                refLocationGroups.Select(refInOneDocument =>
                    FixReferencingDocumentAsync(
                        solutionWithChangedNamespace.GetRequiredDocument(refInOneDocument.Key),
                        refInOneDocument,
                        newNamespace,
                        fallbackOptions,
                        cancellationToken))).ConfigureAwait(false);
 
            var solutionWithFixedReferences = await MergeDocumentChangesAsync(solutionWithChangedNamespace, fixedDocuments, cancellationToken).ConfigureAwait(false);
 
            return (solutionWithFixedReferences, refLocationGroups.SelectAsArray(g => g.Key));
        }
 
        private static async Task<Solution> MergeDocumentChangesAsync(Solution originalSolution, Document[] changedDocuments, CancellationToken cancellationToken)
        {
            foreach (var document in changedDocuments)
            {
                originalSolution = originalSolution.WithDocumentSyntaxRoot(
                    document.Id,
                    await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false));
            }
 
            return originalSolution;
        }
 
        private readonly struct LocationForAffectedSymbol
        {
            public LocationForAffectedSymbol(ReferenceLocation location, bool isReferenceToExtensionMethod)
            {
                ReferenceLocation = location;
                IsReferenceToExtensionMethod = isReferenceToExtensionMethod;
            }
 
            public ReferenceLocation ReferenceLocation { get; }
 
            public bool IsReferenceToExtensionMethod { get; }
 
            public Document Document => ReferenceLocation.Document;
        }
 
        private static async Task<ImmutableArray<LocationForAffectedSymbol>> FindReferenceLocationsForSymbolAsync(
            Document document, ISymbol symbol, CancellationToken cancellationToken)
        {
            using var _ = ArrayBuilder<LocationForAffectedSymbol>.GetInstance(out var builder);
 
            var referencedSymbols = await FindReferencesAsync(symbol, document, cancellationToken).ConfigureAwait(false);
            builder.AddRange(referencedSymbols
                .Where(refSymbol => refSymbol.Definition.Equals(symbol))
                .SelectMany(refSymbol => refSymbol.Locations)
                .Select(location => new LocationForAffectedSymbol(location, isReferenceToExtensionMethod: false)));
 
            // So far we only have references to types declared in affected namespace. We also need to 
            // handle invocation of extension methods (in reduced form) that are declared in those types. 
            // Therefore additional calls to find references are needed for those extension methods.
            // This will returns all the references, not just in the reduced form. But we will
            // not further distinguish the usage. In the worst case, those references are redundant because
            // they are already covered by the type references found above.
            if (symbol is INamedTypeSymbol typeSymbol && typeSymbol.MightContainExtensionMethods)
            {
                foreach (var methodSymbol in typeSymbol.GetMembers().OfType<IMethodSymbol>())
                {
                    if (methodSymbol.IsExtensionMethod)
                    {
                        var referencedMethodSymbols = await FindReferencesAsync(methodSymbol, document, cancellationToken).ConfigureAwait(false);
                        builder.AddRange(referencedMethodSymbols
                            .SelectMany(refSymbol => refSymbol.Locations)
                            .Select(location => new LocationForAffectedSymbol(location, isReferenceToExtensionMethod: true)));
                    }
                }
            }
 
            return builder.ToImmutable();
        }
 
        private static async Task<ImmutableArray<ReferencedSymbol>> FindReferencesAsync(ISymbol symbol, Document document, CancellationToken cancellationToken)
        {
            cancellationToken.ThrowIfCancellationRequested();
            var progress = new StreamingProgressCollector();
            await SymbolFinder.FindReferencesAsync(
                symbol, document.Project.Solution, progress, documents: null,
                FindReferencesSearchOptions.Default, cancellationToken).ConfigureAwait(false);
 
            return progress.GetReferencedSymbols();
        }
 
        private async Task<Document> FixDeclarationDocumentAsync(
            Document document,
            IReadOnlyList<LocationForAffectedSymbol> refLocations,
            string oldNamespace,
            string newNamespace,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            Debug.Assert(newNamespace != null);
 
            // 1. Fix references to the affected types in this document if necessary.
            // 2. Add usings for containing namespaces, in case we have references 
            //    relying on old namespace declaration for resolution. 
            //
            //      For example, in the code below, after we change namespace to 
            //      "A.B.C", we will need to add "using Foo.Bar;".     
            //
            //      namespace Foo.Bar.Baz
            //      {
            //          class C1
            //          {
            //               C2 _c2;    // C2 is define in namespace "Foo.Bar" in another document.
            //          }
            //      }
            //
            // 3. Change namespace declaration to target namespace.
            // 4. Simplify away unnecessary qualifications.
 
            var addImportService = document.GetRequiredLanguageService<IAddImportsService>();
            ImmutableArray<SyntaxNode> containersToAddImports;
 
            var oldNamespaceParts = GetNamespaceParts(oldNamespace);
            var newNamespaceParts = GetNamespaceParts(newNamespace);
 
            if (refLocations.Count > 0)
            {
                (document, containersToAddImports) = await FixReferencesAsync(document, this, addImportService, refLocations, newNamespaceParts, fallbackOptions, cancellationToken)
                    .ConfigureAwait(false);
            }
            else
            {
                // If there's no reference to types declared in this document,
                // we will use root node as import container.
                containersToAddImports = ImmutableArray.Create(await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false));
            }
 
            Debug.Assert(containersToAddImports.Length > 0);
 
            // Need to import all containing namespaces of old namespace and add them to the document (if it's not global namespace)
            // Include the new namespace in case there are multiple namespace declarations in
            // the declaring document. They may need a using statement added to correctly keep
            // references to the type inside it's new namespace
            var namesToImport = GetAllNamespaceImportsForDeclaringDocument(oldNamespace, newNamespace);
 
            var documentOptions = await document.GetCodeCleanupOptionsAsync(fallbackOptions, cancellationToken).ConfigureAwait(false);
 
            var documentWithAddedImports = await AddImportsInContainersAsync(
                document,
                addImportService,
                containersToAddImports,
                namesToImport,
                documentOptions.AddImportOptions,
                cancellationToken).ConfigureAwait(false);
 
            var root = await documentWithAddedImports.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
 
            root = ChangeNamespaceDeclaration((TCompilationUnitSyntax)root, oldNamespaceParts, newNamespaceParts)
                .WithAdditionalAnnotations(Formatter.Annotation);
 
            // Need to invoke formatter explicitly since we are doing the diff merge ourselves.
            var services = documentWithAddedImports.Project.Solution.Services;
            root = Formatter.Format(root, Formatter.Annotation, services, documentOptions.FormattingOptions, cancellationToken);
 
            root = root.WithAdditionalAnnotations(Simplifier.Annotation);
            var formattedDocument = documentWithAddedImports.WithSyntaxRoot(root);
            return await Simplifier.ReduceAsync(formattedDocument, documentOptions.SimplifierOptions, cancellationToken).ConfigureAwait(false);
        }
 
        private static async Task<Document> FixReferencingDocumentAsync(
            Document document,
            IEnumerable<LocationForAffectedSymbol> refLocations,
            string newNamespace,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            // 1. Fully qualify all simple references (i.e. not via an alias) with new namespace.
            // 2. Add using of new namespace (for each reference's container).
            // 3. Try to simplify qualified names introduced from step(1).
 
            var addImportService = document.GetRequiredLanguageService<IAddImportsService>();
            var changeNamespaceService = document.GetRequiredLanguageService<IChangeNamespaceService>();
 
            var newNamespaceParts = GetNamespaceParts(newNamespace);
 
            var (documentWithRefFixed, containers) =
                await FixReferencesAsync(document, changeNamespaceService, addImportService, refLocations, newNamespaceParts, fallbackOptions, cancellationToken)
                    .ConfigureAwait(false);
 
            var documentOptions = await document.GetCodeCleanupOptionsAsync(fallbackOptions, cancellationToken).ConfigureAwait(false);
 
            var documentWithAdditionalImports = await AddImportsInContainersAsync(
                documentWithRefFixed,
                addImportService,
                containers,
                ImmutableArray.Create(newNamespace),
                documentOptions.AddImportOptions,
                cancellationToken).ConfigureAwait(false);
 
            // Need to invoke formatter explicitly since we are doing the diff merge ourselves.
            var formattedDocument = await Formatter.FormatAsync(documentWithAdditionalImports, Formatter.Annotation, documentOptions.FormattingOptions, cancellationToken)
                .ConfigureAwait(false);
 
            return await Simplifier.ReduceAsync(formattedDocument, documentOptions.SimplifierOptions, cancellationToken).ConfigureAwait(false);
        }
 
        /// <summary>
        /// Fix each reference and return a collection of proper containers (innermost container
        /// with imports) that new import should be added to based on reference locations.
        /// If <paramref name="newNamespaceParts"/> is specified (not default), the fix would be:
        ///     1. qualify the reference with new namespace and mark it for simplification, or
        ///     2. find and mark the qualified reference for simplification.
        /// Otherwise, there would be no namespace replacement.
        /// </summary>
        private static async Task<(Document, ImmutableArray<SyntaxNode>)> FixReferencesAsync(
            Document document,
            IChangeNamespaceService changeNamespaceService,
            IAddImportsService addImportService,
            IEnumerable<LocationForAffectedSymbol> refLocations,
            ImmutableArray<string> newNamespaceParts,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            var editor = await DocumentEditor.CreateAsync(document, cancellationToken).ConfigureAwait(false);
            var root = editor.OriginalRoot;
            using var _ = PooledHashSet<SyntaxNode>.GetInstance(out var containers);
 
            var generator = SyntaxGenerator.GetGenerator(document);
            var syntaxFacts = document.GetRequiredLanguageService<ISyntaxFactsService>();
            var codeGenerator = document.GetRequiredLanguageService<ICodeGenerationService>();
 
            // We need a dummy import to figure out the container for given reference.
            var dummyImport = CreateImport(generator, "Dummy", withFormatterAnnotation: false);
            var abstractChangeNamespaceService = (AbstractChangeNamespaceService)changeNamespaceService;
 
            foreach (var refLoc in refLocations)
            {
                Debug.Assert(document.Id == refLoc.Document.Id);
 
                // Ignore references via alias. For simple cases where the alias is defined as the type we are interested,
                // it will be handled properly because it is one of the reference to the type symbol. Otherwise, we don't
                // attempt to make a potential fix, and user might end up with errors as a result.                    
                if (refLoc.ReferenceLocation.Alias != null)
                {
                    continue;
                }
 
                // Other documents in the solution might have changed after we calculated those ReferenceLocation, 
                // so we can't trust anything to be still up-to-date except their spans.
 
                // Get inner most node in case of type used as a base type. e.g.
                //
                //      public class Foo {}
                //      public class Bar : Foo {}
                //
                // For the reference to Foo where it is used as a base class, the BaseTypeSyntax and the TypeSyntax
                // have exact same span.
 
                var refNode = root.FindNode(refLoc.ReferenceLocation.Location.SourceSpan, findInsideTrivia: true, getInnermostNodeForTie: true);
 
                // For invocation of extension method, we only need to add missing import.
                if (!refLoc.IsReferenceToExtensionMethod)
                {
                    if (abstractChangeNamespaceService.TryGetReplacementReferenceSyntax(
                            refNode, newNamespaceParts, syntaxFacts, out var oldNode, out var newNode))
                    {
                        editor.ReplaceNode(oldNode, newNode.WithAdditionalAnnotations(Simplifier.Annotation));
                    }
                }
 
                var addImportsOptions = await document.GetAddImportPlacementOptionsAsync(fallbackOptions, cancellationToken).ConfigureAwait(false);
 
                // Use a dummy import node to figure out which container the new import will be added to.
                var container = addImportService.GetImportContainer(root, refNode, dummyImport, addImportsOptions);
                containers.Add(container);
            }
 
            foreach (var container in containers)
            {
                editor.TrackNode(container);
            }
 
            var fixedDocument = editor.GetChangedDocument();
            root = await fixedDocument.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
            var result = (fixedDocument, containers.SelectAsArray(c => root.GetCurrentNode(c)
                ?? throw new InvalidOperationException("Can't get SyntaxNode from GetCurrentNode.")));
 
            return result;
        }
 
        private static async Task<Solution> RemoveUnnecessaryImportsAsync(
            Solution solution,
            ImmutableArray<DocumentId> ids,
            ImmutableArray<string> names,
            CodeCleanupOptionsProvider fallbackOptions,
            CancellationToken cancellationToken)
        {
            using var _ = PooledHashSet<DocumentId>.GetInstance(out var linkedDocumentsToSkip);
            var documentsToProcessBuilder = ArrayBuilder<Document>.GetInstance();
 
            foreach (var id in ids)
            {
                if (linkedDocumentsToSkip.Contains(id))
                {
                    continue;
                }
 
                var document = solution.GetRequiredDocument(id);
                linkedDocumentsToSkip.AddRange(document.GetLinkedDocumentIds());
                documentsToProcessBuilder.Add(document);
 
                document = await RemoveUnnecessaryImportsWorker(
                    document,
                    CreateImports(document, names, withFormatterAnnotation: false),
                    cancellationToken).ConfigureAwait(false);
                solution = document.Project.Solution;
            }
 
            var documentsToProcess = documentsToProcessBuilder.ToImmutableAndFree();
 
            var changeDocuments = await Task.WhenAll(documentsToProcess.Select(
                    doc => RemoveUnnecessaryImportsWorker(
                        doc,
                        CreateImports(doc, names, withFormatterAnnotation: false),
                        cancellationToken))).ConfigureAwait(false);
 
            return await MergeDocumentChangesAsync(solution, changeDocuments, cancellationToken).ConfigureAwait(false);
 
            async Task<Document> RemoveUnnecessaryImportsWorker(
                Document doc,
                IEnumerable<SyntaxNode> importsToRemove,
                CancellationToken token)
            {
                var removeImportService = doc.GetRequiredLanguageService<IRemoveUnnecessaryImportsService>();
                var syntaxFacts = doc.GetRequiredLanguageService<ISyntaxFactsService>();
                var formattingOptions = await doc.GetSyntaxFormattingOptionsAsync(fallbackOptions, token).ConfigureAwait(false);
 
                return await removeImportService.RemoveUnnecessaryImportsAsync(
                    doc,
                    import => importsToRemove.Any(importToRemove => syntaxFacts.AreEquivalent(importToRemove, import)),
                    formattingOptions,
                    token).ConfigureAwait(false);
            }
        }
 
        /// <summary>
        /// Add imports for the namespace specified by <paramref name="names"/>
        /// to the provided <paramref name="containers"/>
        /// </summary>
        private static async Task<Document> AddImportsInContainersAsync(
            Document document,
            IAddImportsService addImportService,
            ImmutableArray<SyntaxNode> containers,
            ImmutableArray<string> names,
            AddImportPlacementOptions options,
            CancellationToken cancellationToken)
        {
            // Sort containers based on their span start, to make the result of 
            // adding imports deterministic. 
            if (containers.Length > 1)
            {
                containers = containers.Sort(SyntaxNodeSpanStartComparer.Instance);
            }
 
            var generator = document.GetRequiredLanguageService<SyntaxGenerator>();
 
            var imports = CreateImports(document, names, withFormatterAnnotation: true);
            foreach (var container in containers)
            {
                // If the container is a namespace declaration, the context we pass to 
                // AddImportService must be a child of the declaration, otherwise the 
                // import will be added to root node instead.
                var contextLocation = container is TNamespaceDeclarationSyntax
                    ? container.DescendantNodes().First()
                    : container;
 
                var compilation = await document.Project.GetRequiredCompilationAsync(cancellationToken).ConfigureAwait(false);
                var root = await document.GetRequiredSyntaxRootAsync(cancellationToken).ConfigureAwait(false);
                root = addImportService.AddImports(compilation, root, contextLocation, imports, generator, options, cancellationToken);
                document = document.WithSyntaxRoot(root);
            }
 
            return document;
        }
 
        private static async Task<Solution> MergeDiffAsync(Solution oldSolution, Solution newSolution, CancellationToken cancellationToken)
        {
            var diffMergingSession = new LinkedFileDiffMergingSession(oldSolution, newSolution, newSolution.GetChanges(oldSolution));
            var mergeResult = await diffMergingSession.MergeDiffsAsync(mergeConflictHandler: null, cancellationToken: cancellationToken).ConfigureAwait(false);
            return mergeResult.MergedSolution;
        }
 
        private class SyntaxNodeSpanStartComparer : IComparer<SyntaxNode>
        {
            private SyntaxNodeSpanStartComparer()
            {
            }
 
            public static SyntaxNodeSpanStartComparer Instance { get; } = new SyntaxNodeSpanStartComparer();
 
            public int Compare(SyntaxNode? x, SyntaxNode? y)
            {
                Contract.ThrowIfNull(x);
                Contract.ThrowIfNull(y);
 
                return x.Span.Start - y.Span.Start;
            }
        }
    }
}