// 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 System.Collections.Generic;
using System.Diagnostics;
using Roslyn.Utilities;

namespace Microsoft.CodeAnalysis;

public partial class ProjectDependencyGraph
{
    internal ProjectDependencyGraph WithProjectReferenceRemoved(ProjectId projectId, ProjectId referencedProjectId)
    {
        Contract.ThrowIfFalse(ProjectIds.Contains(projectId));
        Contract.ThrowIfFalse(_referencesMap[projectId].Contains(referencedProjectId));

        // Removing a project reference doesn't change the set of projects
        var projectIds = ProjectIds;

        // Incrementally update the graph
        var referencesMap = ComputeNewReferencesMapForRemovedProjectReference(_referencesMap, projectId, referencedProjectId);
        var reverseReferencesMap = ComputeNewReverseReferencesMapForRemovedProjectReference(_lazyReverseReferencesMap, projectId, referencedProjectId);
        var transitiveReferencesMap = ComputeNewTransitiveReferencesMapForRemovedProjectReference(_transitiveReferencesMap, projectId, referencedProjectId);
        var reverseTransitiveReferencesMap = ComputeNewReverseTransitiveReferencesMapForRemovedProjectReference(_reverseTransitiveReferencesMap, projectId, referencedProjectId);

        return new ProjectDependencyGraph(
            projectIds,
            referencesMap,
            reverseReferencesMap,
            transitiveReferencesMap,
            reverseTransitiveReferencesMap,
            topologicallySortedProjects: default,
            dependencySets: default);
    }

    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewReferencesMapForRemovedProjectReference(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingForwardReferencesMap,
        ProjectId projectId,
        ProjectId referencedProjectId)
    {
        return existingForwardReferencesMap.MultiRemove(projectId, referencedProjectId);
    }

    /// <summary>
    /// Computes a new <see cref="_lazyReverseReferencesMap"/> for the removal of a project reference.
    /// </summary>
    /// <param name="existingReverseReferencesMap">The <see cref="_lazyReverseReferencesMap"/> prior to the removal,
    /// or <see langword="null"/> if the reverse references map was not computed for the prior graph.</param>
    /// <param name="projectId">The project ID from which a project reference is being removed.</param>
    /// <param name="referencedProjectId">The target of the project reference which is being removed.</param>
    /// <returns>The updated (complete) reverse references map, or <see langword="null"/> if the reverse references
    /// map could not be incrementally updated.</returns>
    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? ComputeNewReverseReferencesMapForRemovedProjectReference(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? existingReverseReferencesMap,
        ProjectId projectId,
        ProjectId referencedProjectId)
    {
        if (existingReverseReferencesMap is null)
        {
            return null;
        }

        return existingReverseReferencesMap.MultiRemove(referencedProjectId, projectId);
    }

    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewTransitiveReferencesMapForRemovedProjectReference(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingTransitiveReferencesMap,
        ProjectId projectId,
        ProjectId referencedProjectId)
    {
        var builder = existingTransitiveReferencesMap.ToBuilder();

        // Invalidate the transitive references from every project referencing the changed project (transitively)
        foreach (var (project, references) in existingTransitiveReferencesMap)
        {
            if (!references.Contains(projectId))
            {
                // This is the forward-references-equivalent of the optimization in the update of reverse transitive
                // references.
                continue;
            }

            Debug.Assert(references.Contains(referencedProjectId));
            builder.Remove(project);
        }

        // Invalidate the transitive references from the changed project
        builder.Remove(projectId);

        return builder.ToImmutable();
    }

    private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeNewReverseTransitiveReferencesMapForRemovedProjectReference(
        ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> existingReverseTransitiveReferencesMap,
        ProjectId projectId,
        ProjectId referencedProjectId)
    {
        var builder = existingReverseTransitiveReferencesMap.ToBuilder();

        // Invalidate the transitive reverse references from every project previously referenced by the original
        // project (transitively), except for cases where the removed project reference could not impact the result.
        foreach (var (project, references) in existingReverseTransitiveReferencesMap)
        {
            if (!references.Contains(referencedProjectId))
            {
                // If projectId references project, it isn't through referencedProjectId so the change doesn't
                // impact the dependency graph.
                //
                // Suppose we start with the following graph, and are removing the project reference A->B:
                //
                //   A -> B -> C
                //     \
                //      > D
                //
                // This case is not hit for project C. The reverse transitive references for C contains B, which is
                // the target project of the removed reference. We can see that project C is impacted by this
                // removal, and after the removal, project A will no longer be in the reverse transitive references
                // of C.
                //
                // This case is hit for project D. The reverse transitive references for D does not contain B, which
                // means project D cannot be "downstream" of the impact of removing the reference A->B. We can see
                // that project A will still be in the reverse transitive references of D.
                //
                // This optimization does not catch all cases. For example, consider the following graph where we
                // are removing the project reference A->B:
                //
                //   A -> B -> D
                //     \_______^
                //
                // For this example, we do not hit this optimization because D contains project B in the set of
                // reverse transitive references. Without more complicated checks, we cannot rule out the
                // possibility that A may have been removed from the reverse transitive references of D by the
                // removal of the A->B reference.
                continue;
            }

            Debug.Assert(references.Contains(projectId));
            builder.Remove(project);
        }

        // Invalidate the transitive references from the previously-referenced project
        builder.Remove(referencedProjectId);

        return builder.ToImmutable();
    }
}