// 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.Linq;
 
namespace Microsoft.CodeAnalysis.Shared.Utilities
{
    internal static partial class ExtensionOrderer
    {
        internal static IList<Lazy<TExtension, TMetadata>> Order<TExtension, TMetadata>(
            IEnumerable<Lazy<TExtension, TMetadata>> extensions)
            where TMetadata : OrderableMetadata
        {
            var graph = GetGraph(extensions);
            return graph.TopologicalSort();
        }
 
        private static Graph<TExtension, TMetadata> GetGraph<TExtension, TMetadata>(
            IEnumerable<Lazy<TExtension, TMetadata>> extensions)
            where TMetadata : OrderableMetadata
        {
            var list = extensions.ToList();
            var graph = new Graph<TExtension, TMetadata>();
 
            foreach (var extension in list)
            {
                graph.Nodes.Add(extension, new Node<TExtension, TMetadata>(extension));
            }
 
            foreach (var extension in list)
            {
                var extensionNode = graph.Nodes[extension];
                foreach (var before in extension.Metadata.BeforeTyped)
                {
                    foreach (var beforeExtension in graph.FindExtensions(before))
                    {
                        var otherExtensionNode = graph.Nodes[beforeExtension];
                        otherExtensionNode.ExtensionsBeforeMeSet.Add(extensionNode);
                    }
                }
 
                foreach (var after in extension.Metadata.AfterTyped)
                {
                    foreach (var afterExtension in graph.FindExtensions(after))
                    {
                        var otherExtensionNode = graph.Nodes[afterExtension];
                        extensionNode.ExtensionsBeforeMeSet.Add(otherExtensionNode);
                    }
                }
            }
 
            return graph;
        }
 
        internal static class TestAccessor
        {
            /// <summary>
            /// Helper for checking whether cycles exist in the extension ordering.
            /// Throws <see cref="ArgumentException"/> if a cycle is detected.
            /// </summary>
            /// <exception cref="ArgumentException">A cycle was detected in the extension ordering.</exception>
            internal static void CheckForCycles<TExtension, TMetadata>(
                IEnumerable<Lazy<TExtension, TMetadata>> extensions)
                where TMetadata : OrderableMetadata
            {
                var graph = GetGraph(extensions);
                graph.CheckForCycles();
            }
        }
    }
}