using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Microsoft.CodeAnalysis;

namespace Vellum.Generator
{
    /// <summary>
    /// Describes a type something saves and the types it's built from, as plain data, and decides whether all of it can
    /// be saved. A symbol can't be compared between runs of an incremental generator, since each edit makes new ones.
    /// </summary>
    public sealed class TypeShape : IEquatable<TypeShape>
    {
        /// <summary>
        /// Holds how deeply a type's parts may nest, which is how deeply the runtime checks a type for being saveable.
        /// </summary>
        public const int MaxDepth = SaveNode.MaxDepth;

        /// <summary>
        /// Holds how many parts a shape may have before a generic [Saveable] type stops being looked into.
        /// </summary>
        public const int MaxParts = 1024;

        /// <summary>
        /// Holds how C# spells the whole type, as the code that saves it wrote it.
        /// </summary>
        public readonly string Display;

        /// <summary>
        /// Holds the type first, then its parts. Each part's own parts sit together after the parts before it.
        /// </summary>
        public readonly EquatableArray<TypePart> Parts;

        public TypeShape(string display, EquatableArray<TypePart> parts)
        {
            Display = display;
            Parts = parts;
        }

        private static PartKind KindOf(ITypeSymbol type)
        {
            if (type.TypeKind == TypeKind.TypeParameter || type.TypeKind == TypeKind.Error)
            {
                return PartKind.Ignored;
            }

            var named = type as INamedTypeSymbol;
            if (named != null && named.IsGenericType && SaveableClass.IsMarked(named))
            {
                return PartKind.SavedMembers;
            }

            if (SaveableTypes.IsBuiltIn(type) || (named != null && SaveableClass.IsMarked(named)))
            {
                return PartKind.Whole;
            }

            if (type is IArrayTypeSymbol)
            {
                return PartKind.Collection;
            }

            if (named == null || !named.IsGenericType)
            {
                return PartKind.Plain;
            }

            if (SaveableTypes.IsBuiltInCollection(named))
            {
                return PartKind.Collection;
            }

            return PartKind.Generic;
        }

        // The types a collection or generic type is built from, or the types of a generic [Saveable] type's members.
        private static List<ITypeSymbol> PartsOf(ITypeSymbol type, PartKind kind)
        {
            var array = type as IArrayTypeSymbol;
            if (array != null)
            {
                return new List<ITypeSymbol> { array.ElementType };
            }

            var named = (INamedTypeSymbol)type;
            if (kind == PartKind.SavedMembers)
            {
                return SaveableClass.SavedMembersWithBasesOf(named).Select(member => member.Type).ToList();
            }

            return SaveableTypes.ArgumentsOf(named);
        }

        // Queues the type arguments of each generic class a family could match.  They are looked at only when a family
        // marks a type parameter [Saveable].  The type's own arguments are already queued as its parts.
        private static EquatableArray<BaseArguments> AddBaseArguments(ITypeSymbol type, bool ownArgumentsQueued,
            int firstChild, int childCount, List<ITypeSymbol> symbols, int depth, List<int> depths)
        {
            ImmutableArray<BaseArguments>.Builder returnMe = ImmutableArray.CreateBuilder<BaseArguments>();
            if (type.TypeKind != TypeKind.Class
                && type.TypeKind != TypeKind.Struct
                && type.TypeKind != TypeKind.Interface)
            {
                return default;
            }

            var linked = new List<INamedTypeSymbol>();
            for (ITypeSymbol link = type; link != null && link.SpecialType != SpecialType.System_Object;
                link = link.BaseType)
            {
                var named = link as INamedTypeSymbol;
                if (named != null && named.IsGenericType)
                {
                    linked.Add(named);
                }
            }

            linked.AddRange(type.AllInterfaces.Where(implemented => implemented.IsGenericType));
            foreach (INamedTypeSymbol named in linked)
            {
                string name = SaveableTypes.NameOf(named.OriginalDefinition);
                if (ReferenceEquals(named, type) && ownArgumentsQueued)
                {
                    returnMe.Add(new BaseArguments(name, firstChild, childCount));
                    continue;
                }

                List<ITypeSymbol> arguments = SaveableTypes.ArgumentsOf(named);
                returnMe.Add(new BaseArguments(name, symbols.Count, arguments.Count));
                foreach (ITypeSymbol argument in arguments)
                {
                    symbols.Add(argument);
                    depths.Add(depth);
                }
            }

            return new EquatableArray<BaseArguments>(returnMe.ToImmutable());
        }

        /// <summary>
        /// Returns the shape of <paramref name="type"/>.
        /// </summary>
        public static TypeShape Of(ITypeSymbol type)
        {
            // Parts go in a queue's order, so the parts of one type end up together without any recursion.
            var symbols = new List<ITypeSymbol> { type };
            var depths = new List<int> { 1 };
            ImmutableArray<TypePart>.Builder parts = ImmutableArray.CreateBuilder<TypePart>();
            var expanded = new HashSet<string>();
            var queuedBases = new Dictionary<string, EquatableArray<BaseArguments>>();
            for (int i = 0; i < symbols.Count; ++i)
            {
                ITypeSymbol current = SaveableTypes.WithoutNullable(symbols[i]);
                PartKind kind = KindOf(current);

                // A type that holds itself is checked at its first appearance, which is what keeps it from looping.
                // One that keeps growing as it nests is cut off by the part limit, and counts as unsaveable.
                if (kind == PartKind.SavedMembers && !expanded.Add(SaveableTypes.NameOf(current)))
                {
                    kind = PartKind.Whole;
                }
                else if (kind == PartKind.SavedMembers && symbols.Count > MaxParts)
                {
                    kind = PartKind.Plain;
                }

                string openName = null;
                var named = current as INamedTypeSymbol;
                if (named != null && named.IsGenericType)
                {
                    openName = SaveableTypes.NameOf(named.OriginalDefinition);
                }

                // Nothing past the depth limit is looked at, which also keeps a deeply nested type from being walked.
                int firstChild = symbols.Count;
                int childCount = 0;
                bool hasParts = kind == PartKind.Generic || kind == PartKind.Collection
                    || kind == PartKind.SavedMembers;
                if (hasParts && depths[i] <= MaxDepth)
                {
                    List<ITypeSymbol> children = PartsOf(current, kind);
                    childCount = children.Count;
                    foreach (ITypeSymbol child in children)
                    {
                        symbols.Add(child);
                        depths.Add(depths[i] + 1);
                    }
                }

                EquatableArray<string> familyNames = default;
                EquatableArray<BaseArguments> baseArguments = default;
                if (kind == PartKind.Plain || kind == PartKind.Generic)
                {
                    familyNames = SaveableTypes.FamilyNamesOf(current);

                    // A type met again shares the arguments queued the first time, so a type that implements an
                    // interface made from itself doesn't keep queueing.
                    string typeName = SaveableTypes.NameOf(current);
                    if (!queuedBases.TryGetValue(typeName, out baseArguments)
                        && depths[i] <= MaxDepth
                        && symbols.Count <= MaxParts)
                    {
                        baseArguments = AddBaseArguments(current, kind == PartKind.Generic, firstChild, childCount,
                            symbols, depths[i] + 1, depths);
                        queuedBases.Add(typeName, baseArguments);
                    }
                }

                parts.Add(new TypePart(SaveableTypes.NameOf(current), openName, kind, firstChild, childCount,
                    familyNames, baseArguments));
            }

            return new TypeShape(type.ToDisplayString(), new EquatableArray<TypePart>(parts.ToImmutable()));
        }

        // Queues the arguments of the base class a family saves that the family requires to be saveable. A type met
        // again shares the arguments of its first appearance, so each is queued once or a type made from itself would
        // loop.
        private void PushFamilyArguments(TypePart part, ImmutableArray<int> positions, string familyBase, int depth,
            Stack<KeyValuePair<int, int>> pending, HashSet<int> queued)
        {
            if (positions.Length == 0)
            {
                return;
            }

            BaseArguments arguments = part.BaseArguments.Items.FirstOrDefault(
                candidate => candidate.Name == familyBase);
            if (arguments == null)
            {
                return;
            }

            for (int i = positions.Length - 1; i >= 0; --i)
            {
                if (positions[i] < arguments.ChildCount && queued.Add(arguments.FirstChild + positions[i]))
                {
                    pending.Push(new KeyValuePair<int, int>(arguments.FirstChild + positions[i], depth + 1));
                }
            }
        }

        /// <summary>
        /// Returns the index of the innermost part that can't be saved, which is 0, the type itself, if nothing
        /// smaller is to blame, or -1 if all of it can be saved. <paramref name="converted"/> holds the name of each
        /// type something has a converter for, and of each generic type something has a generic converter for.
        /// <paramref name="families"/> holds, for each base class or interface something has a family converter for,
        /// which of its type arguments the converter marks [Saveable].  A type derived from one is saved whole, except
        /// that those arguments must be saveable too.  <paramref name="saveableArguments"/> holds, for each generic
        /// type with a generic converter, which of its type arguments must be saveable. The others can be anything,
        /// and a generic type missing from it needs every argument saveable.
        /// </summary>
        public int FindUnsaveable(HashSet<string> converted, Dictionary<string, EquatableArray<int>> families,
            Dictionary<string, EquatableArray<int>> saveableArguments)
        {
            var pending = new Stack<KeyValuePair<int, int>>();
            var familyQueued = new HashSet<int>();
            pending.Push(new KeyValuePair<int, int>(0, 1));
            while (pending.Count > 0)
            {
                KeyValuePair<int, int> entry = pending.Pop();
                TypePart part = Parts.Items[entry.Key];
                if (part.Kind == PartKind.Ignored || part.Kind == PartKind.Whole || converted.Contains(part.Name))
                {
                    continue;
                }

                string familyBase = part.FamilyNames.Items.FirstOrDefault(families.ContainsKey);
                if (familyBase != null)
                {
                    PushFamilyArguments(part, families[familyBase].Items, familyBase, entry.Value, pending,
                        familyQueued);
                    continue;
                }

                bool savedFromParts = part.Kind == PartKind.Collection
                    || part.Kind == PartKind.SavedMembers
                    || (part.Kind == PartKind.Generic && converted.Contains(part.OpenName));
                if (!savedFromParts || entry.Value > MaxDepth)
                {
                    return entry.Key;
                }

                EquatableArray<int> required;
                if (part.Kind == PartKind.Generic && saveableArguments.TryGetValue(part.OpenName, out required))
                {
                    ImmutableArray<int> positions = required.Items;
                    for (int i = positions.Length - 1; i >= 0; --i)
                    {
                        if (positions[i] < part.ChildCount)
                        {
                            pending.Push(new KeyValuePair<int, int>(part.FirstChild + positions[i], entry.Value + 1));
                        }
                    }

                    continue;
                }

                for (int i = part.ChildCount - 1; i >= 0; --i)
                {
                    pending.Push(new KeyValuePair<int, int>(part.FirstChild + i, entry.Value + 1));
                }
            }

            return -1;
        }

        /// <summary>
        /// Returns the report that something saved as <paramref name="savedName"/> can't be saved because of the part
        /// at <paramref name="unsaveable"/>, the index <see cref="FindUnsaveable"/> found.
        /// </summary>
        public Diagnostic UnsaveableDiagnostic(Location location, string savedName, int unsaveable)
        {
            string context = "";
            if (unsaveable != 0)
            {
                context = " (inside " + Display + ")";
            }

            return Diagnostic.Create(VellumDiagnostics.UnsaveableType, location, savedName,
                Parts.Items[unsaveable].Name, context);
        }

        public bool Equals(TypeShape other)
        {
            return other != null && Display == other.Display && Parts.Equals(other.Parts);
        }

        public override bool Equals(object obj)
        {
            return Equals(obj as TypeShape);
        }

        public override int GetHashCode()
        {
            return Display.GetHashCode() * 31 + Parts.GetHashCode();
        }
    }
}