//            Copyright Keysight Technologies 2012-2019
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, you can obtain one at http://mozilla.org/MPL/2.0/.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace OpenTap
{
    /// <summary>
    /// This class represents a resource in a dependency tree, and contains lists of the resources it depends on.
    /// </summary>
    [DebuggerDisplay("{Depender} : {Resource}")]
    internal class ResourceNode : IResourceReferences
    {
        /// <summary>
        /// The resource this node represents.
        /// </summary>
        public IResource Resource { get; set; }

        /// <summary> The property that references this resource. </summary>
        public IMemberData Depender { get; }

        /// <summary>
        /// The resources that this node depends on. These are marked with <see cref="ResourceOpenAttribute"/>.
        /// </summary>
        internal readonly List<IResource> WeakDependencies;
        /// <summary>
        /// The resources that this node depends on. These will be opened before this nodes resource.
        /// </summary>
        internal readonly List<IResource> StrongDependencies;

        /// <summary>
        /// TestSteps (or other IResources) that uses this resource. These are the reason this resources needs to be opened when running a TestPlan.
        /// </summary>
        public List<ResourceReference> References { get; } = new List<ResourceReference>();

        internal ResourceNode(IResource resource)
        {
            this.Resource = resource;
            this.WeakDependencies = new List<IResource>();
            this.StrongDependencies = new List<IResource>();
        }

        internal ResourceNode(IResource resource, IMemberData prop, IEnumerable<IResource> weakDeps, IEnumerable<IResource> strongDeps)
        {
            this.Resource = resource;
            this.Depender = prop;
            this.WeakDependencies = weakDeps.ToList();
            this.StrongDependencies = strongDeps.ToList();
        }
    }


    internal class ResourceDependencyAnalyzer
    {
        private static TraceSource Log = OpenTap.Log.CreateSource("Dependency Analyzer");

        private struct ResourceDep
        {
            public override bool Equals(object obj)
            {
                if (obj is ResourceDep other)
                    return other.Behavior == Behavior && other.Resource == Resource &&
                           other.Depender == Depender;
                return false;
            }

            public override int GetHashCode() => Behavior.GetHashCode() * 3120732 + 
                                                 (Resource?.GetHashCode() ?? 73289132) * 134017414 +
                                                 (Depender?.GetHashCode() ?? 321312) * 730921632;

            public readonly ResourceOpenBehavior Behavior;
            public readonly IResource Resource;
            public readonly IMemberData Depender; // this is important in case the resource is null

            public ResourceDep(ResourceOpenBehavior behavior, IResource resource, IMemberData dep)
            {
                this.Behavior = behavior;
                this.Resource = resource;
                this.Depender = dep;
            }

            public ResourceDep(IResource resource)
            {
                Depender = null;
                this.Resource = resource;
                Behavior = ResourceOpenBehavior.Before;
            }
        }

        private ResourceDep FilterProps(IResource o, IMemberData pi)
        {
            var behavior = ResourceOpenBehavior.Before;
            var attr = pi.GetAttribute<ResourceOpenAttribute>();
            if (attr != null) behavior = attr.Behavior;

            return new ResourceDep(behavior, o, pi);
        }

        ResourceDep[] getManyResources<T>(T[] steps)
        {
            if (steps.Length == 0)
                return Array.Empty<ResourceDep>();

            var result = new HashSet<ResourceDep>();
            TestStepExtensions.GetObjectSettings<IResource, T, ResourceDep>(steps, true, FilterProps, result);
            result.RemoveWhere(dep => dep.Behavior == ResourceOpenBehavior.Ignore);
            return result.ToArray();
            
        }

        private IEnumerable<ResourceDep> GetResources<T>(T Step)
        {
            if (Step == null)
                return Array.Empty<ResourceDep>();
            return getManyResources(new[] { Step });
        }

        private ResourceNode Analyze(ResourceDep resource)
        {
            var resources = GetResources(resource.Resource);
            return new ResourceNode(resource.Resource,resource.Depender, 
                weakDeps: resources.Where(x => x.Behavior == ResourceOpenBehavior.InParallel).Select(x => x.Resource), 
                strongDeps: resources.Where(x => x.Behavior == ResourceOpenBehavior.Before).Select(x => x.Resource)
                );
        }

        private List<ResourceNode> GetResourceTree(ICollection<ResourceDep> resources)
        {
            Queue<ResourceDep> allResources = new Queue<ResourceDep>(resources);
            HashSet<ResourceDep> knownNodes = new HashSet<ResourceDep>();
            List<ResourceNode> allNodes = new List<ResourceNode>();

            ResourceDep x;
            while (allResources.Count > 0)
            {
                x = allResources.Dequeue();

                if (x.Resource == null)
                {
                    if (knownNodes.Any(k => k.Resource == x.Resource && k.Depender == x.Depender))
                        continue;
                }
                else
                {
                    if (knownNodes.Any(k => k.Resource == x.Resource))
                        continue;
                }
                knownNodes.Add(x);

                var newNode = Analyze(x);
                allNodes.Add(newNode);

                if (x.Resource != null)
                {
                    List<IResource> newNodes = newNode.WeakDependencies.Concat(newNode.StrongDependencies).ToList();
                    foreach (IResource node in newNodes.Except(knownNodes.Select(k => k.Resource)))
                        allResources.Enqueue(new ResourceDep(node));
                }
            }

            return allNodes;
        }

        private void ExpandTree(List<ResourceNode> nodes)
        {
            var lut = nodes.Where(x => x.Resource != null).ToDictionary(x => x.Resource, x => x);

            bool changed;
            do
            {
                changed = false;

                foreach (var n in nodes)
                {
                    if (n == null) continue;
                    var newDeps = n.StrongDependencies.Where(x => x != null)
                        .SelectMany(x => lut[x].StrongDependencies.Concat(lut[x].WeakDependencies))
                        .Except(n.StrongDependencies)
                        .ToArray();
                    if (newDeps.Length > 0)
                    {
                        changed = true;
                        n.StrongDependencies.AddRange(newDeps);
                    }
                }
            }
            while (changed);
        }

        #region Strongly connected component algorithm
        // Can be used to find all strongly connected components(circular references) in the graph made up of the resources and the dependencies between them.
        // Implemented based on pseudo code from here: https://en.wikipedia.org/w/index.php?title=Tarjan%27s_strongly_connected_components_algorithm&oldid=774903237
        private class Vertex
        {
            internal int index, lowlink;
            internal bool onStack;
            internal ResourceNode node;
        }

        private void StrongConnect(Vertex v, Dictionary<IResource, Vertex> V, Stack<Vertex> S, List<List<IResource>> sccs, ref int index)
        {
            v.index = index;
            v.lowlink = index;
            index++;
            S.Push(v);
            v.onStack = true;

            // For all edges (v->w)
            foreach (var w in v.node.StrongDependencies.Select(n => V[n]))
            {
                if (w.index == -1)
                {
                    StrongConnect(w, V, S, sccs, ref index);
                    v.lowlink = Math.Min(v.lowlink, w.lowlink);
                }
                else if (w.onStack)
                {
                    v.lowlink = Math.Min(v.lowlink, w.index);
                }
            }

            if (v.lowlink == v.index)
            {
                List<IResource> scc = new List<IResource>();
                Vertex w;
                do
                {
                    w = S.Pop();
                    w.onStack = false;
                    scc.Add(w.node.Resource);
                }
                while (v != w);

                if (scc.Count > 1)
                    sccs.Add(scc);
            }
        }

        private List<List<IResource>> FindStronglyConnectedComponents(List<ResourceNode> tree)
        {
            List<List<IResource>> sccs = new List<List<IResource>>();

            var V = tree.Where(n => n.Resource != null).ToDictionary(n => n.Resource, n => new Vertex { index = -1, lowlink = -1, node = n });
            var S = new Stack<Vertex>();

            int index = 0;

            foreach (var v in V.Values)
                if (v.index == -1)
                    StrongConnect(v, V, S, sccs, ref index);

            return sccs;
        }
        #endregion

        /// <summary>
        /// Finds all IResource properties on a list of references. The references can be any class derived from ITapPlugin, such as ITestStep or IResource.
        /// If a reference supplied in the <paramref name="references"/> list is a IResource itself it will be added to the resulting list.
        /// </summary>
        internal List<ResourceNode> GetAllResources(object[] references, out bool errorDetected)
        {
            errorDetected = false;

            ResourceDep[] stepResources = getManyResources(references);
            var resourceDeps = new List<ResourceDep>(stepResources);
            foreach (var reference in references)
            {
                if(reference is IResource res)
                    resourceDeps.Add(new ResourceDep(res));
            }
            List<ResourceNode> tree = GetResourceTree(resourceDeps);

            ExpandTree(tree);

            // Check that no resources have direct references to itself.
            foreach (var scc in tree.Where(x => x.StrongDependencies.Any(dep => dep == x.Resource)))
            {
                foreach (var dep in scc.StrongDependencies)
                {
                    if (dep == scc.Resource)
                    {
                        errorDetected = true;
                        Log.Error("Resource is referencing itself: {0}", scc.Resource);
                        break;
                    }
                }
                
            }

            // Figure out if all resources has their resource properties set
            foreach(var leaf in tree)
            {
                if(leaf.StrongDependencies.Any(s => s is null))
                {
                    errorDetected = true;
                    Log.Error($"Resource setting not set on resource {leaf.Resource}. Please configure or disable the resource.");
                }
            }

            if (errorDetected) // If any resources has resource properties which is not set, let's return early, because FindStronglyConntectedComponents method below will throw a confusing error in this case.
                return tree;

            // Figure out if there are circular references, and list the circular references in an exception each.
            var sccs = FindStronglyConnectedComponents(tree);
            if (sccs.Count > 0)
            {
                errorDetected = true;

                foreach (var scc in sccs)
                    Log.Error(string.Format("Circular references between resources: {0}", string.Join(",", scc.Select(res => res.Name))));
            }

            //Add users of resources
            foreach (var r in references)
            {
                TestStepExtensions.GetObjectSettings<IResource, object, ResourceNode>(r, true, (res, prop) =>
                {
                    var nodes = tree.Where(n => n.Resource == res);
                    if (nodes.Count() > 1)
                    {
                        // Normally we would expect that the tree only contains one node representing each resource. 
                        // In case of null resources however, we want one node per property, such that ILockManager.BeforeOpen()
                        // has a chance to set each property to a different resource instance.
                        if (res != null)
                            throw new Exception($"Duplicate entry for Resource '{res.Name}' in tree.");
                        nodes = nodes.Where(n => n.Depender == prop);
                    }

                    var nodeRepresentingResource = nodes.FirstOrDefault();
                    if (nodeRepresentingResource != null)
                        nodeRepresentingResource.References.Add(new ResourceReference(r, prop));
                    return nodeRepresentingResource;
                }, new HashSet<ResourceNode>());
            }

            return tree;
        }
    }
}