File: Workspace\Solution\ProjectDependencyGraph_RemoveProject.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.Immutable;
using Microsoft.CodeAnalysis.PooledObjects;
using Roslyn.Utilities;
 
namespace Microsoft.CodeAnalysis;
 
public partial class ProjectDependencyGraph
{
    internal ProjectDependencyGraph WithProjectsRemoved(ArrayBuilder<ProjectId> removedProjectIds)
    {
        // Project ID set and direct forward references are trivially updated by removing the key corresponding to
        // the project getting removed.
        var projectIdsBuilder = ProjectIds.ToBuilder();
        foreach (var projectId in removedProjectIds)
            Contract.ThrowIfFalse(projectIdsBuilder.Remove(projectId));
        var projectIds = projectIdsBuilder.ToImmutable();
 
        var referencesMap = ComputeNewReferencesMapForRemovedProject(
            existingForwardReferencesMap: _referencesMap,
            existingReverseReferencesMap: _lazyReverseReferencesMap,
            removedProjectIds);
 
        // The direct reverse references map is updated by removing the key for the project getting removed, and
        // also updating any direct references to the removed project.
        var reverseReferencesMap = ComputeNewReverseReferencesMapForRemovedProject(
            existingForwardReferencesMap: _referencesMap,
            existingReverseReferencesMap: _lazyReverseReferencesMap,
            removedProjectIds);
        var transitiveReferencesMap = ComputeNewTransitiveReferencesMapForRemovedProject(_transitiveReferencesMap, removedProjectIds);
        var reverseTransitiveReferencesMap = ComputeNewReverseTransitiveReferencesMapForRemovedProject(_reverseTransitiveReferencesMap, removedProjectIds);
        return new ProjectDependencyGraph(
            projectIds,
            referencesMap,
            reverseReferencesMap,
            transitiveReferencesMap,
            reverseTransitiveReferencesMap,
            topologicallySortedProjects: default,
            dependencySets: default);
    }
 
    /// <summary>
    /// Computes a new <see cref="_referencesMap"/> for the removal of a project.
    /// </summary>
    /// <param name="existingForwardReferencesMap">The <see cref="_referencesMap"/> prior to the removal.</param>
    /// <param name="existingReverseReferencesMap">The <see cref="_lazyReverseReferencesMap"/> prior to the removal.
    /// This map serves as a hint to the removal process; i.e. it is assumed correct if it contains data, but may be
    /// omitted without impacting correctness.</param>
    /// <param name="removedProjectIds">IDs of projects which are being removed.</param>
    /// <returns>The <see cref="_referencesMap"/> for the project dependency graph once the project is removed.</returns>
    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewReferencesMapForRemovedProject(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingForwardReferencesMap,
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? existingReverseReferencesMap,
        ArrayBuilder<ProjectId> removedProjectIds)
    {
        var builder = existingForwardReferencesMap.ToBuilder();
 
        // TODO: Consider optimizing when a large number of projects are being removed simultaneously
        if (existingReverseReferencesMap is not null)
        {
            foreach (var removedProjectId in removedProjectIds)
            {
                // We know all the projects directly referencing 'projectId', so remove 'projectId' from the set of
                // references in each of those cases directly.
                if (existingReverseReferencesMap.TryGetValue(removedProjectId, out var referencingProjects))
                {
                    foreach (var id in referencingProjects)
                        builder.MultiRemove(id, removedProjectId);
                }
            }
        }
        else
        {
            // We don't know which projects reference 'projectId', so iterate over all known projects and remove
            // 'projectId' from the set of references if it exists.
            foreach (var (id, _) in existingForwardReferencesMap)
            {
                foreach (var removedProjectId in removedProjectIds)
                    builder.MultiRemove(id, removedProjectId);
            }
        }
 
        // Finally, remove each item in removedProjectIds
        foreach (var removedProjectId in removedProjectIds)
            builder.Remove(removedProjectId);
 
        return builder.ToImmutable();
    }
 
    /// <summary>
    /// Computes a new <see cref="_lazyReverseReferencesMap"/> for the removal of a project.
    /// </summary>
    /// <param name="existingReverseReferencesMap">The <see cref="_lazyReverseReferencesMap"/> prior to the removal,
    /// or <see langword="null"/> if the value prior to removal was not computed for the graph.</param>
    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? ComputeNewReverseReferencesMapForRemovedProject(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingForwardReferencesMap,
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? existingReverseReferencesMap,
        ArrayBuilder<ProjectId> removedProjectIds)
    {
        // If the map was never calculated for the previous graph, so there is nothing to update.
        if (existingReverseReferencesMap is null)
            return null;
 
        // TODO: Consider optimizing when a large number of projects are being removed simultaneously
        var builder = existingReverseReferencesMap.ToBuilder();
        foreach (var removedProjectId in removedProjectIds)
        {
            // If the removed project did not reference any other projects, nothing to do for this project.
            if (!existingForwardReferencesMap.TryGetValue(removedProjectId, out var forwardReferences))
                continue;
 
            // Iterate over each project referenced by 'removedProjectId', which is now being removed. Update the
            // reverse references map for the project to no longer include 'removedProjectId' in the list.
            foreach (var referencedProjectId in forwardReferences)
                builder.MultiRemove(referencedProjectId, removedProjectId);
        }
 
        // Finally, remove each item in removedProjectIds
        foreach (var removedProjectId in removedProjectIds)
            builder.Remove(removedProjectId);
 
        return builder.ToImmutable();
    }
 
    /// <summary>
    /// Computes a new <see cref="_transitiveReferencesMap"/> for the removal of a project.
    /// </summary>
    /// <seealso cref="ComputeNewReverseTransitiveReferencesMapForRemovedProject"/>
    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewTransitiveReferencesMapForRemovedProject(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingTransitiveReferencesMap,
        ArrayBuilder<ProjectId> removedProjectIds)
    {
        var builder = existingTransitiveReferencesMap.ToBuilder();
 
        // Iterate over each project and invalidate the transitive references for the project if the project has an
        // existing transitive reference to 'removedProjectId'.
        foreach (var (project, references) in existingTransitiveReferencesMap)
        {
            foreach (var removedProjectId in removedProjectIds)
            {
                if (references.Contains(removedProjectId))
                {
                    // The project transitively referenced 'removedProjectId', so any transitive references brought in
                    // exclusively through this reference are no longer valid. Remove the project from the map and the
                    // new transitive references will be recomputed the first time they are needed.
                    builder.Remove(project);
                    break;
                }
            }
        }
 
        // Finally, remove each item in removedProjectIds
        foreach (var removedProjectId in removedProjectIds)
            builder.Remove(removedProjectId);
 
        return builder.ToImmutable();
    }
 
    /// <summary>
    /// Computes a new <see cref="_reverseTransitiveReferencesMap"/> for the removal of a project.
    /// </summary>
    /// <seealso cref="ComputeNewTransitiveReferencesMapForRemovedProject"/>
    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewReverseTransitiveReferencesMapForRemovedProject(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingReverseTransitiveReferencesMap,
        ArrayBuilder<ProjectId> removedProjectIds)
    {
        var builder = existingReverseTransitiveReferencesMap.ToBuilder();
 
        // Iterate over each project and invalidate the transitive reverse references for the project if the project
        // has an existing transitive reverse reference to 'removedProjectId'.
        foreach (var (project, references) in existingReverseTransitiveReferencesMap)
        {
            foreach (var removedProjectId in removedProjectIds)
            {
                if (references.Contains(removedProjectId))
                {
                    // 'removedProjectId' transitively referenced the project, so any transitive reverse references
                    // brought in exclusively through this reverse reference are no longer valid. Remove the project
                    // from the map and the new transitive reverse references will be recomputed the first time they are
                    // needed.
                    builder.Remove(project);
                    break;
                }
            }
        }
 
        foreach (var removedProjectId in removedProjectIds)
            builder.Remove(removedProjectId);
 
        return builder.ToImmutable();
    }
}