// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Analyzer.Utilities;
using Analyzer.Utilities.Extensions;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.Diagnostics;

namespace Microsoft.NetCore.Analyzers.Security
{
    using static MicrosoftNetCoreAnalyzersResources;

    /// <summary>
    /// CA5362: <inheritdoc cref="PotentialReferenceCycleInDeserializedObjectGraphTitle"/>
    /// </summary>
    [DiagnosticAnalyzer(LanguageNames.CSharp, LanguageNames.VisualBasic)]
    public sealed class PotentialReferenceCycleInDeserializedObjectGraph : DiagnosticAnalyzer
    {
        internal const string DiagnosticId = "CA5362";

        internal static readonly DiagnosticDescriptor Rule = DiagnosticDescriptorHelper.Create(
            DiagnosticId,
            CreateLocalizableResourceString(nameof(PotentialReferenceCycleInDeserializedObjectGraphTitle)),
            CreateLocalizableResourceString(nameof(PotentialReferenceCycleInDeserializedObjectGraphMessage)),
            DiagnosticCategory.Security,
            RuleLevel.Disabled,
            description: CreateLocalizableResourceString(nameof(PotentialReferenceCycleInDeserializedObjectGraphDescription)),
            isPortedFxCopRule: false,
            isDataflowRule: false,
            isReportedAtCompilationEnd: true);

        public override ImmutableArray<DiagnosticDescriptor> SupportedDiagnostics { get; } = ImmutableArray.Create(Rule);

        public sealed override void Initialize(AnalysisContext context)
        {
            context.EnableConcurrentExecution();

            // Security analyzer - analyze and report diagnostics on generated code.
            context.ConfigureGeneratedCodeAnalysis(GeneratedCodeAnalysisFlags.Analyze | GeneratedCodeAnalysisFlags.ReportDiagnostics);

            context.RegisterCompilationStartAction(
                (CompilationStartAnalysisContext compilationStartAnalysisContext) =>
                {
                    var compilation = compilationStartAnalysisContext.Compilation;
                    var serializableAttributeTypeSymbol = compilation.GetOrCreateTypeByMetadataName(WellKnownTypeNames.SystemSerializableAttribute);

                    if (serializableAttributeTypeSymbol == null)
                    {
                        return;
                    }

                    var nonSerializedAttribute = compilation.GetOrCreateTypeByMetadataName(WellKnownTypeNames.SystemNonSerializedAttribute);

                    if (nonSerializedAttribute == null)
                    {
                        return;
                    }

                    ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>> forwardGraph = new ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>>();
                    ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>> invertedGraph = new ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>>();

                    // It keeps the out Degree of every vertex in the invertedGraph, which is corresponding to the in Degree of the vertex in forwardGraph.
                    ConcurrentDictionary<ISymbol, int> inDegree = new ConcurrentDictionary<ISymbol, int>();

                    // It Keeps the out degree of every vertex in the forwardGraph, which is corresponding to the in Degree of the vertex in invertedGraph.
                    ConcurrentDictionary<ISymbol, int> outDegree = new ConcurrentDictionary<ISymbol, int>();

                    compilationStartAnalysisContext.RegisterSymbolAction(
                        (SymbolAnalysisContext symbolAnalysisContext) =>
                        {
                            DrawGraph((INamedTypeSymbol)symbolAnalysisContext.Symbol);
                        }, SymbolKind.NamedType);

                    compilationStartAnalysisContext.RegisterCompilationEndAction(
                        (CompilationAnalysisContext compilationAnalysisContext) =>
                        {
                            ModifyDegree(inDegree, forwardGraph);
                            ModifyDegree(outDegree, invertedGraph);

                            // If the degree of a vertex is greater than 0 both in the forward graph and inverted graph after topological sorting,
                            // the vertex must belong to a loop.
                            var leftVertices = inDegree.Where(s => s.Value > 0).Select(s => s.Key).ToImmutableHashSet();
                            var invertedLeftVertices = outDegree.Where(s => s.Value > 0).Select(s => s.Key).ToImmutableHashSet();
                            var verticesInLoop = leftVertices.Intersect(invertedLeftVertices);

                            foreach (var vertex in verticesInLoop)
                            {
                                if (vertex is IFieldSymbol fieldInLoop)
                                {
                                    var associatedSymbol = fieldInLoop.AssociatedSymbol;
                                    compilationAnalysisContext.ReportDiagnostic(
                                        fieldInLoop.CreateDiagnostic(
                                            Rule,
                                            associatedSymbol == null ? vertex.Name : associatedSymbol.Name));
                                }
                            }
                        });

                    // Traverse from point to its descendants, save the information into a directed graph.
                    //
                    // point: The initial point
                    void DrawGraph(ITypeSymbol point)
                    {
                        // If the point has been visited, return;
                        // otherwise, add it to the graph and mark it as visited.
                        if (!AddPointToBothGraphs(point))
                        {
                            return;
                        }

                        foreach (var associatedTypePoint in GetAssociatedTypes(point))
                        {
                            if (associatedTypePoint == null ||
                                associatedTypePoint.Equals(point))
                            {
                                continue;
                            }

                            AddLineToBothGraphs(point, associatedTypePoint);
                            DrawGraph(associatedTypePoint);
                        }

                        if (point.IsInSource() &&
                            point.HasAnyAttribute(serializableAttributeTypeSymbol))
                        {
                            var fieldPoints = point.GetMembers().OfType<IFieldSymbol>().Where(s => !s.HasAnyAttribute(nonSerializedAttribute) &&
                                                                                                        !s.IsStatic);

                            foreach (var fieldPoint in fieldPoints)
                            {
                                var fieldTypePoint = fieldPoint.Type;
                                AddLineToBothGraphs(point, fieldPoint);
                                AddLineToBothGraphs(fieldPoint, fieldTypePoint);
                                DrawGraph(fieldTypePoint);
                            }
                        }
                    }

                    static HashSet<ITypeSymbol> GetAssociatedTypes(ITypeSymbol type)
                    {
                        var result = new HashSet<ITypeSymbol>();

                        if (type is INamedTypeSymbol namedTypeSymbol)
                        {
                            // 1. Type arguments of generic type.
                            if (namedTypeSymbol.IsGenericType)
                            {
                                foreach (var arg in namedTypeSymbol.TypeArguments)
                                {
                                    result.Add(arg);
                                }
                            }

                            // 2. The type it constructed from.
                            var constructedFrom = namedTypeSymbol.ConstructedFrom;
                            result.Add(constructedFrom);
                        }
                        else if (type is IArrayTypeSymbol arrayTypeSymbol)
                        {
                            // 3. Element type of the array.
                            result.Add(arrayTypeSymbol.ElementType);
                        }

                        // 4. Base type.
                        if (type.BaseType != null)
                        {
                            result.Add(type.BaseType);
                        }

                        return result;
                    }

                    // Add a line to the graph.
                    //
                    // from: The start point of the line
                    // to: The end point of the line
                    // degree: The out degree of all vertices in the graph
                    // graph: The graph
                    void AddLine(ISymbol from, ISymbol to, ConcurrentDictionary<ISymbol, int> degree, ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>> graph)
                    {
                        graph.AddOrUpdate(from, new ConcurrentDictionary<ISymbol, bool> { [to] = true }, (k, v) =>
                        {
                            v[to] = true;
                            return v;
                        });
                        degree.AddOrUpdate(from, 1, (k, v) => v + 1);
                    }

                    // Add a point to the graph.
                    //
                    // point: The point to be added
                    // degree: The out degree of all vertices in the graph
                    // graph: The graph
                    static bool AddPoint(ISymbol point, ConcurrentDictionary<ISymbol, int> degree, ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>> graph)
                    {
                        degree.TryAdd(point, 0);
                        return graph.TryAdd(point, new ConcurrentDictionary<ISymbol, bool>());
                    }

                    // Add a line to the forward graph and inverted graph unconditionally.
                    //
                    // from: The start point of the line
                    // to: The end point of the line
                    void AddLineToBothGraphs(ISymbol from, ISymbol to)
                    {
                        AddLine(from, to, outDegree, forwardGraph);
                        AddLine(to, from, inDegree, invertedGraph);
                    }

                    // Add a point to the forward graph and inverted graph unconditionally.
                    //
                    // point: The point to be added
                    // return: `true` if `point` is added to the forward graph successfully; otherwise `false`.
                    bool AddPointToBothGraphs(ISymbol point)
                    {
                        AddPoint(point, inDegree, invertedGraph);
                        return AddPoint(point, outDegree, forwardGraph);
                    }

                    // According to topological sorting, modify the degree of every vertex in the graph.
                    //
                    // degree: The in degree of all vertices in the graph
                    // graph: The graph
                    static void ModifyDegree(ConcurrentDictionary<ISymbol, int> degree, ConcurrentDictionary<ISymbol, ConcurrentDictionary<ISymbol, bool>> graph)
                    {
                        var stack = new Stack<ISymbol>(degree.Where(s => s.Value == 0).Select(s => s.Key));

                        while (stack.Count != 0)
                        {
                            var start = stack.Pop();
                            degree.AddOrUpdate(start, -1, (k, v) => v - 1);

                            foreach (var vertex in graph[start].Keys)
                            {
                                degree.AddOrUpdate(vertex, -1, (k, v) => v - 1);

                                if (degree[vertex] == 0)
                                {
                                    stack.Push(vertex);
                                }
                            }
                        }
                    }
                });
        }
    }
}