ProjectDependencyGraph.cs

// 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 Roslyn.Utilities;

namespace Microsoft.CodeAnalysis
{
    /// <summary>
    /// A <see cref="ProjectDependencyGraph"/> models the dependencies between projects in a solution.
    /// </summary>
    public partial class ProjectDependencyGraph
    {
        private readonly ImmutableHashSet<ProjectId> _projectIds;

        /// <summary>
        /// The map of projects to dependencies. This field is always fully initialized. Projects which do not reference
        /// any other projects do not have a key in this map (i.e. they are omitted, as opposed to including them with
        /// an empty value).
        ///
        /// <list type="bullet">
        /// <item><description>This field is always fully initialized</description></item>
        /// <item><description>Projects which do not reference any other projects do not have a key in this map (i.e.
        /// they are omitted, as opposed to including them with an empty value)</description></item>
        /// <item><description>The keys and values in this map are always contained in
        /// <see cref="_projectIds"/></description></item>
        /// </list>
        /// </summary>
        private readonly ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> _referencesMap;

        // guards lazy computed data
        private readonly NonReentrantLock _dataLock = new();

        /// <summary>
        /// The lazily-initialized map of projects to projects which reference them. This field is either null, or
        /// fully-computed. Projects which are not referenced by any other project do not have a key in this map (i.e.
        /// they are omitted, as opposed to including them with an empty value).
        /// </summary>
        private ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? _lazyReverseReferencesMap;

        // These are computed fully on demand. ImmutableArray.IsDefault indicates the item needs to be realized
        private ImmutableArray<ProjectId> _lazyTopologicallySortedProjects;

        // This is not typed ImmutableArray<ImmutableArray<...>> because GetDependencySets() wants to return
        // an IEnumerable<IEnumerable<...>>, and ImmutableArray<ImmutableArray<...>> can't be converted
        // to an IEnumerable<IEnumerable<...>> without a bunch of boxing.
        private ImmutableArray<IEnumerable<ProjectId>> _lazyDependencySets;

        // These accumulate results on demand. They are never null, but a missing key/value pair indicates it needs to be computed.
        private ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> _transitiveReferencesMap;
        private ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> _reverseTransitiveReferencesMap;

        internal static readonly ProjectDependencyGraph Empty = new(
            ImmutableHashSet<ProjectId>.Empty,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
            ImmutableArray<ProjectId>.Empty,
            ImmutableArray<IEnumerable<ProjectId>>.Empty);

        internal ProjectDependencyGraph(
            ImmutableHashSet<ProjectId> projectIds,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> referencesMap)
            : this(
                  projectIds,
                  RemoveItemsWithEmptyValues(referencesMap),
                  reverseReferencesMap: null,
                  transitiveReferencesMap: ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
                  reverseTransitiveReferencesMap: ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Empty,
                  default,
                  default)
        {
        }

        // This constructor is private to prevent other Roslyn code from producing this type with inconsistent inputs.
        private ProjectDependencyGraph(
            ImmutableHashSet<ProjectId> projectIds,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> referencesMap,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? reverseReferencesMap,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> transitiveReferencesMap,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> reverseTransitiveReferencesMap,
            ImmutableArray<ProjectId> topologicallySortedProjects,
            ImmutableArray<IEnumerable<ProjectId>> dependencySets)
        {
            Contract.ThrowIfNull(transitiveReferencesMap);
            Contract.ThrowIfNull(reverseTransitiveReferencesMap);

            _projectIds = projectIds;
            _referencesMap = referencesMap;
            _lazyReverseReferencesMap = reverseReferencesMap;
            _transitiveReferencesMap = transitiveReferencesMap;
            _reverseTransitiveReferencesMap = reverseTransitiveReferencesMap;
            _lazyTopologicallySortedProjects = topologicallySortedProjects;
            _lazyDependencySets = dependencySets;

            ValidateForwardReferences(_projectIds, _referencesMap);
            ValidateReverseReferences(_projectIds, _referencesMap, _lazyReverseReferencesMap);
        }

        internal ImmutableHashSet<ProjectId> ProjectIds => _projectIds;

        private static ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> RemoveItemsWithEmptyValues(
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> map)
        {
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>.Builder? builder = null;
            foreach (var (key, value) in map)
            {
                if (!value.IsEmpty)
                {
                    continue;
                }

                builder ??= map.ToBuilder();
                builder.Remove(key);
            }

            return builder?.ToImmutable() ?? map;
        }

        internal ProjectDependencyGraph WithProjectReferences(ProjectId projectId, IReadOnlyList<ProjectReference> projectReferences)
        {
            Contract.ThrowIfFalse(_projectIds.Contains(projectId));

            // This method we can't optimize very well: changing project references arbitrarily could invalidate pretty much anything.
            // The only thing we can reuse is our actual map of project references for all the other projects, so we'll do that.

            // only include projects contained in the solution:
            var referencedProjectIds = projectReferences.IsEmpty() ? ImmutableHashSet<ProjectId>.Empty :
                projectReferences
                    .Where(r => _projectIds.Contains(r.ProjectId))
                    .Select(r => r.ProjectId)
                    .ToImmutableHashSet();

            var referencesMap = referencedProjectIds.IsEmpty ?
                _referencesMap.Remove(projectId) : _referencesMap.SetItem(projectId, referencedProjectIds);

            return new ProjectDependencyGraph(_projectIds, referencesMap);
        }

        /// <summary>
        /// Gets the list of projects that this project directly depends on.
        /// </summary>
        public IImmutableSet<ProjectId> GetProjectsThatThisProjectDirectlyDependsOn(ProjectId projectId)
        {
            if (projectId == null)
            {
                throw new ArgumentNullException(nameof(projectId));
            }

            return _referencesMap.GetValueOrDefault(projectId, ImmutableHashSet<ProjectId>.Empty);
        }

        /// <summary>
        /// Gets the list of projects that directly depend on this project.
        /// </summary> 
        public IImmutableSet<ProjectId> GetProjectsThatDirectlyDependOnThisProject(ProjectId projectId)
        {
            if (projectId == null)
            {
                throw new ArgumentNullException(nameof(projectId));
            }

            if (_lazyReverseReferencesMap == null)
            {
                using (_dataLock.DisposableWait())
                {
                    return this.GetProjectsThatDirectlyDependOnThisProject_NoLock(projectId);
                }
            }
            else
            {
                // okay, because its only ever going to be computed and assigned once
                return this.GetProjectsThatDirectlyDependOnThisProject_NoLock(projectId);
            }
        }

        private ImmutableHashSet<ProjectId> GetProjectsThatDirectlyDependOnThisProject_NoLock(ProjectId projectId)
        {
            if (_lazyReverseReferencesMap == null)
            {
                _lazyReverseReferencesMap = this.ComputeReverseReferencesMap();
                ValidateReverseReferences(_projectIds, _referencesMap, _lazyReverseReferencesMap);
            }

            return _lazyReverseReferencesMap.GetValueOrDefault(projectId, ImmutableHashSet<ProjectId>.Empty);
        }

        private ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> ComputeReverseReferencesMap()
        {
            var reverseReferencesMap = new Dictionary<ProjectId, HashSet<ProjectId>>();

            foreach (var (projectId, references) in _referencesMap)
            {
                foreach (var referencedId in references)
                    reverseReferencesMap.MultiAdd(referencedId, projectId);
            }

            return reverseReferencesMap
                .Select(kvp => new KeyValuePair<ProjectId, ImmutableHashSet<ProjectId>>(kvp.Key, kvp.Value.ToImmutableHashSet()))
                .ToImmutableDictionary();
        }

        /// <summary>
        /// Gets the list of projects that directly or transitively this project depends on, if it has already been
        /// cached.
        /// </summary>
        internal ImmutableHashSet<ProjectId>? TryGetProjectsThatThisProjectTransitivelyDependsOn(ProjectId projectId)
        {
            if (projectId is null)
            {
                throw new ArgumentNullException(nameof(projectId));
            }

            _transitiveReferencesMap.TryGetValue(projectId, out var projects);
            return projects;
        }

        /// <summary>
        /// Gets the list of projects that directly or transitively this project depends on
        /// </summary>
        public IImmutableSet<ProjectId> GetProjectsThatThisProjectTransitivelyDependsOn(ProjectId projectId)
        {
            if (projectId == null)
            {
                throw new ArgumentNullException(nameof(projectId));
            }

            // first try without lock for speed
            var currentMap = _transitiveReferencesMap;
            if (currentMap.TryGetValue(projectId, out var transitiveReferences))
            {
                return transitiveReferences;
            }
            else
            {
                using (_dataLock.DisposableWait())
                {
                    return GetProjectsThatThisProjectTransitivelyDependsOn_NoLock(projectId);
                }
            }
        }

        private ImmutableHashSet<ProjectId> GetProjectsThatThisProjectTransitivelyDependsOn_NoLock(ProjectId projectId)
        {
            if (!_transitiveReferencesMap.TryGetValue(projectId, out var transitiveReferences))
            {
                using var pooledObject = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                var results = pooledObject.Object;
                this.ComputeTransitiveReferences(projectId, results);
                transitiveReferences = results.ToImmutableHashSet();
                _transitiveReferencesMap = _transitiveReferencesMap.Add(projectId, transitiveReferences);
            }

            return transitiveReferences;
        }

        private void ComputeTransitiveReferences(ProjectId project, HashSet<ProjectId> result)
        {
            var otherProjects = this.GetProjectsThatThisProjectDirectlyDependsOn(project);

            foreach (var other in otherProjects)
            {
                if (result.Add(other))
                {
                    ComputeTransitiveReferences(other, result);
                }
            }
        }

        /// <summary>
        /// Gets the list of projects that directly or transitively depend on this project.
        /// </summary>
        public IEnumerable<ProjectId> GetProjectsThatTransitivelyDependOnThisProject(ProjectId projectId)
        {
            if (projectId == null)
            {
                throw new ArgumentNullException(nameof(projectId));
            }

            // first try without lock for speed
            var currentMap = _reverseTransitiveReferencesMap;
            if (currentMap.TryGetValue(projectId, out var reverseTransitiveReferences))
            {
                return reverseTransitiveReferences;
            }
            else
            {
                using (_dataLock.DisposableWait())
                {
                    return this.GetProjectsThatTransitivelyDependOnThisProject_NoLock(projectId);
                }
            }
        }

        private ImmutableHashSet<ProjectId> GetProjectsThatTransitivelyDependOnThisProject_NoLock(ProjectId projectId)
        {
            if (!_reverseTransitiveReferencesMap.TryGetValue(projectId, out var reverseTransitiveReferences))
            {
                using var pooledObject = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                var results = pooledObject.Object;

                ComputeReverseTransitiveReferences(projectId, results);
                reverseTransitiveReferences = results.ToImmutableHashSet();
                _reverseTransitiveReferencesMap = _reverseTransitiveReferencesMap.Add(projectId, reverseTransitiveReferences);
            }

            return reverseTransitiveReferences;
        }

        private void ComputeReverseTransitiveReferences(ProjectId project, HashSet<ProjectId> results)
        {
            var otherProjects = this.GetProjectsThatDirectlyDependOnThisProject_NoLock(project);
            foreach (var other in otherProjects)
            {
                if (results.Add(other))
                {
                    ComputeReverseTransitiveReferences(other, results);
                }
            }
        }

        /// <summary>
        /// Returns all the projects for the solution in a topologically sorted order with respect
        /// to their dependencies. Projects that depend on other projects will always show up later in this sequence
        /// than the projects they depend on.
        /// </summary>
        public IEnumerable<ProjectId> GetTopologicallySortedProjects(CancellationToken cancellationToken = default)
        {
            if (_lazyTopologicallySortedProjects.IsDefault)
            {
                using (_dataLock.DisposableWait(cancellationToken))
                {
                    this.GetTopologicallySortedProjects_NoLock(cancellationToken);
                }
            }

            return _lazyTopologicallySortedProjects;
        }

        private void GetTopologicallySortedProjects_NoLock(CancellationToken cancellationToken)
        {
            if (_lazyTopologicallySortedProjects.IsDefault)
            {
                using var seenProjects = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                using var resultList = SharedPools.Default<List<ProjectId>>().GetPooledObject();
                this.TopologicalSort(_projectIds, seenProjects.Object, resultList.Object, cancellationToken);
                _lazyTopologicallySortedProjects = resultList.Object.ToImmutableArray();
            }
        }

        private void TopologicalSort(
            IEnumerable<ProjectId> projectIds,
            HashSet<ProjectId> seenProjects,
            List<ProjectId> resultList,
            CancellationToken cancellationToken)
        {
            foreach (var projectId in projectIds)
            {
                cancellationToken.ThrowIfCancellationRequested();

                // Make sure we only ever process a project once.
                if (seenProjects.Add(projectId))
                {
                    // Recurse and add anything this project depends on before adding the project itself.
                    if (_referencesMap.TryGetValue(projectId, out var projectReferenceIds))
                    {
                        TopologicalSort(projectReferenceIds, seenProjects, resultList, cancellationToken);
                    }

                    resultList.Add(projectId);
                }
            }
        }

        /// <summary>
        /// Returns a sequence of sets, where each set contains items with shared interdependency,
        /// and there is no dependency between sets.  Each set returned will sorted in topological order.
        /// </summary>
        public IEnumerable<IEnumerable<ProjectId>> GetDependencySets(CancellationToken cancellationToken = default)
        {
            if (_lazyDependencySets == null)
            {
                using (_dataLock.DisposableWait(cancellationToken))
                {
                    this.GetDependencySets_NoLock(cancellationToken);
                }
            }

            return _lazyDependencySets;
        }

        private ImmutableArray<IEnumerable<ProjectId>> GetDependencySets_NoLock(CancellationToken cancellationToken)
        {
            if (_lazyDependencySets == null)
            {
                using var seenProjects = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                using var results = SharedPools.Default<List<IEnumerable<ProjectId>>>().GetPooledObject();
                this.ComputeDependencySets(seenProjects.Object, results.Object, cancellationToken);
                _lazyDependencySets = results.Object.ToImmutableArray();
            }

            return _lazyDependencySets;
        }

        private void ComputeDependencySets(HashSet<ProjectId> seenProjects, List<IEnumerable<ProjectId>> results, CancellationToken cancellationToken)
        {
            foreach (var project in _projectIds)
            {
                if (seenProjects.Add(project))
                {
                    // We've never seen this project before, so we have not yet dealt with any projects
                    // in its dependency set.
                    using var dependencySet = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                    ComputedDependencySet(project, dependencySet.Object);

                    // add all items in the dependency set to seen projects so we don't revisit any of them
                    seenProjects.UnionWith(dependencySet.Object);

                    // now make sure the items within the sets are topologically sorted.
                    using var topologicallySeenProjects = SharedPools.Default<HashSet<ProjectId>>().GetPooledObject();
                    using var sortedProjects = SharedPools.Default<List<ProjectId>>().GetPooledObject();
                    this.TopologicalSort(dependencySet.Object, topologicallySeenProjects.Object, sortedProjects.Object, cancellationToken);
                    results.Add(sortedProjects.Object.ToImmutableArrayOrEmpty());
                }
            }
        }

        private void ComputedDependencySet(ProjectId project, HashSet<ProjectId> result)
        {
            if (result.Add(project))
            {
                var otherProjects = this.GetProjectsThatDirectlyDependOnThisProject_NoLock(project).Concat(
                                    this.GetProjectsThatThisProjectDirectlyDependsOn(project));

                foreach (var other in otherProjects)
                {
                    ComputedDependencySet(other, result);
                }
            }
        }

        [Conditional("DEBUG")]
        private static void ValidateForwardReferences(
            ImmutableHashSet<ProjectId> projectIds,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> referencesMap)
        {
            RoslynDebug.Assert(referencesMap is object);

            Debug.Assert(projectIds.Count >= referencesMap.Count);
            Debug.Assert(referencesMap.Keys.All(projectIds.Contains));

            foreach (var (_, referencedProjects) in referencesMap)
            {
                Debug.Assert(!referencedProjects.IsEmpty, "Unexpected empty value in the forward references map.");
                foreach (var referencedProject in referencedProjects)
                {
                    Debug.Assert(projectIds.Contains(referencedProject), "Unexpected reference to unknown project.");
                }
            }
        }

        [Conditional("DEBUG")]
        private static void ValidateReverseReferences(
            ImmutableHashSet<ProjectId> projectIds,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>> forwardReferencesMap,
            ImmutableDictionary<ProjectId, ImmutableHashSet<ProjectId>>? reverseReferencesMap)
        {
            if (reverseReferencesMap is null)
                return;

            Debug.Assert(projectIds.Count >= reverseReferencesMap.Count);
            Debug.Assert(reverseReferencesMap.Keys.All(projectIds.Contains));

            foreach (var (project, referencedProjects) in forwardReferencesMap)
            {
                foreach (var referencedProject in referencedProjects)
                {
                    Debug.Assert(reverseReferencesMap.ContainsKey(referencedProject));
                    Debug.Assert(reverseReferencesMap[referencedProject].Contains(project));
                }
            }

            foreach (var (project, referencingProjects) in reverseReferencesMap)
            {
                Debug.Assert(!referencingProjects.IsEmpty, "Unexpected empty value in the reverse references map.");
                foreach (var referencingProject in referencingProjects)
                {
                    Debug.Assert(forwardReferencesMap.ContainsKey(referencingProject));
                    Debug.Assert(forwardReferencesMap[referencingProject].Contains(project));
                }
            }
        }

        internal TestAccessor GetTestAccessor()
            => new(this);

        internal readonly struct TestAccessor
        {
            private readonly ProjectDependencyGraph _instance;

            public TestAccessor(ProjectDependencyGraph instance)
                => _instance = instance;

            /// <summary>
            /// Gets the list of projects that directly or transitively depend on this project, if it has already been
            /// cached.
            /// </summary>
            public ImmutableHashSet<ProjectId>? TryGetProjectsThatTransitivelyDependOnThisProject(ProjectId projectId)
            {
                if (projectId is null)
                {
                    throw new ArgumentNullException(nameof(projectId));
                }

                _instance._reverseTransitiveReferencesMap.TryGetValue(projectId, out var projects);
                return projects;
            }
        }
    }
}