using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using System.Threading;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.CSharp;
using Microsoft.CodeAnalysis.CSharp.Syntax;
using Microsoft.CodeAnalysis.Operations;

namespace Vellum.Generator
{
    /// <summary>
    /// Finds each generic method, and each member of a generic type, that saves a type built from its own type
    /// parameters, by following the uses that hand them on to a registered member, and writes the
    /// [RegisterSaveMethod] attributes that let uses of it be checked.
    /// </summary>
    public static class SaveMethods
    {
        public const string FileName = "Vellum.RegisterSaveMethod.g.cs";

        public const string ParameterName = "SaveMethodParameter";

        public const string ClassParameterName = "SaveClassParameter";

        public const string InheritedReason =
            "uses a type parameter that the interface it implements, or the base class it overrides a member of, " +
            "doesn't take as a type argument of its own";

        public const string UnspellableReason =
            "uses a type that can't be spelled in an attribute, such as a private type or a pointer";

        // An assembly attribute can only name a type every part of the assembly can see.
        private static bool CanName(INamedTypeSymbol type)
        {
            for (INamedTypeSymbol current = type; current != null; current = current.ContainingType)
            {
                switch (current.DeclaredAccessibility)
                {
                    case Accessibility.Private:
                    case Accessibility.Protected:
                    case Accessibility.ProtectedAndInternal:
                        return false;
                }
            }

            return true;
        }

        // An explicit interface implementation has no ID of its own, only its interface's.  An accessor of one still
        // has the kind of an accessor.
        private static bool HasOwnId(IMethodSymbol method)
        {
            if (method.ExplicitInterfaceImplementations.Length > 0)
            {
                return false;
            }

            switch (method.MethodKind)
            {
                case MethodKind.Ordinary:
                case MethodKind.Constructor:
                case MethodKind.UserDefinedOperator:
                case MethodKind.Conversion:
                case MethodKind.PropertyGet:
                case MethodKind.PropertySet:
                case MethodKind.EventAdd:
                case MethodKind.EventRemove:
                    return true;
                default:
                    return false;
            }
        }

        private static bool AddId(List<string> ids, IMethodSymbol method)
        {
            string id = method.OriginalDefinition.GetDocumentationCommentId();
            if (id != null && !ids.Contains(id))
            {
                ids.Add(id);
                return true;
            }

            return false;
        }

        // Says which number each type parameter of the type has among the interface's type arguments.  A type parameter
        // that the interface doesn't take as an argument by itself, such as one inside a List, has none.
        private static EquatableArray<int> ClassMapOf(INamedTypeSymbol type, INamedTypeSymbol implemented)
        {
            var map = new int[SavedTypeAnalyzer.ClassArgumentsOf(type).Length];
            for (int i = 0; i < map.Length; ++i)
            {
                map[i] = -1;
            }

            ImmutableArray<ITypeSymbol> interfaceArguments = SavedTypeAnalyzer.ClassArgumentsOf(implemented);
            for (int number = 0; number < interfaceArguments.Length; ++number)
            {
                var parameter = interfaceArguments[number] as ITypeParameterSymbol;
                if (parameter != null && parameter.TypeParameterKind == TypeParameterKind.Type)
                {
                    int ordinal = SaveTemplate.ClassOrdinalOf(parameter);
                    if (ordinal < map.Length && map[ordinal] < 0)
                    {
                        map[ordinal] = number;
                    }
                }
            }

            return new EquatableArray<int>(map.ToImmutableArray());
        }

        // A converter is only called through ToNode(object) and FromNode(object), so what it overrides has no call to
        // check.  Its base class's parameter is also often a type built from its own, which can't be numbered.
        private static bool IsConverter(INamedTypeSymbol type)
        {
            for (INamedTypeSymbol baseType = type.BaseType; baseType != null; baseType = baseType.BaseType)
            {
                if (baseType.MetadataName == "SaveConverter`1"
                    && baseType.ContainingNamespace.ToDisplayString() == "Vellum")
                {
                    return true;
                }
            }

            return false;
        }

        /// <summary>
        /// Returns the IDs <paramref name="method"/> is registered under: its own, one for each interface method it
        /// implements, and one for each method it overrides.
        /// </summary>
        /// <param name="ownCount">Gets how many of the leading IDs are the method's own, which is zero or one.</param>
        /// <param name="classMaps">
        /// Gets, for each ID, how the type parameters of the method's type are numbered by the interface or base class
        /// that ID is from.  The method's own has none.
        /// </param>
        public static List<string> RegistrationIds(IMethodSymbol method, out int ownCount,
            out List<EquatableArray<int>> classMaps)
        {
            var returnMe = new List<string>();
            classMaps = new List<EquatableArray<int>>();
            INamedTypeSymbol type = method.ContainingType;
            if (HasOwnId(method) && CanName(type) && AddId(returnMe, method))
            {
                classMaps.Add(default);
            }

            ownCount = returnMe.Count;

            // Saving code usually calls through an interface, eg: generated code that only knows Ariadne's IArcWriter.
            foreach (INamedTypeSymbol implemented in type.AllInterfaces)
            {
                foreach (IMethodSymbol member in implemented.GetMembers().OfType<IMethodSymbol>())
                {
                    if (SymbolEqualityComparer.Default.Equals(
                            type.FindImplementationForInterfaceMember(member), method)
                        && CanName(implemented)
                        && AddId(returnMe, member))
                    {
                        classMaps.Add(ClassMapOf(type, implemented));
                    }
                }
            }

            // A call through the base class runs the override, so what the override saves is saved by that call too.
            for (IMethodSymbol overridden = IsConverter(type) ? null : method.OverriddenMethod; overridden != null;
                overridden = overridden.OverriddenMethod)
            {
                if (CanName(overridden.ContainingType) && AddId(returnMe, overridden))
                {
                    classMaps.Add(ClassMapOf(type, overridden.ContainingType));
                }
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the IDs <paramref name="method"/> is registered under: its own, one for each interface method it
        /// implements, and one for each method it overrides.
        /// </summary>
        public static List<string> RegistrationIds(IMethodSymbol method)
        {
            int ownCount;
            List<EquatableArray<int>> classMaps;
            return RegistrationIds(method, out ownCount, out classMaps);
        }

        /// <summary>
        /// Returns the methods a call to <paramref name="method"/> can be registered under: the method, the methods it
        /// overrides, and the interface methods <paramref name="receiver"/> implements with it.
        /// </summary>
        /// <remarks>
        /// A call through a class reaches a registration made on its interface, or on a base class's method.  The
        /// receiver is the type the call was made on, which can implement an interface that the class declaring the
        /// method doesn't.  Each result is made from the type arguments it is seen with, so its containing type says
        /// what the type parameters of that type stand for here.
        /// </remarks>
        public static List<IMethodSymbol> Candidates(IMethodSymbol method, ITypeSymbol receiver)
        {
            var returnMe = new List<IMethodSymbol>();
            var chain = new List<IMethodSymbol>();
            // A method constructed from type arguments has no overridden method of its own.  Its definition over the
            // same containing type does.
            for (IMethodSymbol current = method; current != null; current = current.ConstructedFrom.OverriddenMethod)
            {
                returnMe.Add(current);
                chain.Add(current.OriginalDefinition);
            }

            ITypeSymbol type = receiver ?? method.ContainingType;
            if (type == null || type.TypeKind == TypeKind.Interface)
            {
                return returnMe;
            }

            foreach (INamedTypeSymbol implemented in type.AllInterfaces)
            {
                foreach (ISymbol member in implemented.GetMembers(method.Name))
                {
                    var interfaceMethod = member as IMethodSymbol;
                    if (interfaceMethod == null)
                    {
                        continue;
                    }

                    var implementation = type.FindImplementationForInterfaceMember(interfaceMethod) as IMethodSymbol;
                    if (implementation != null
                        && chain.Contains(implementation.OriginalDefinition, SymbolEqualityComparer.Default))
                    {
                        returnMe.Add(interfaceMethod);
                    }
                }
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the IDs a call to <paramref name="method"/> can be registered under, which are those of its
        /// <see cref="Candidates"/>.
        /// </summary>
        public static List<string> CandidateIds(IMethodSymbol method, ITypeSymbol receiver)
        {
            var returnMe = new List<string>();
            foreach (IMethodSymbol candidate in Candidates(method, receiver))
            {
                AddId(returnMe, candidate);
            }

            return returnMe;
        }

        // The stand-in types are what an attribute can spell where a method's own type parameters would go.
        private static string Attribute(string id, SaveTemplate template)
        {
            return "[assembly: global::Vellum.RegisterSaveMethod(\"" + id + "\", typeof(" + template.ToSource() + "))]";
        }

        /// <summary>
        /// Returns a registration for each template that an assembly's [RegisterSaveMethod] attributes, or the
        /// assemblies it references, name.
        /// </summary>
        public static EquatableArray<SaveRegistration> SeedsOf(Compilation compilation)
        {
            var returnMe = new List<SaveRegistration>();
            foreach (KeyValuePair<string, List<ITypeSymbol>> registered in SavedTypeAnalyzer.Registered(compilation))
            {
                foreach (ITypeSymbol saved in registered.Value)
                {
                    IMethodSymbol owner = null;
                    SaveTemplate template = SaveTemplate.Of(saved, ref owner);
                    if (template != null)
                    {
                        returnMe.Add(new SaveRegistration(registered.Key, template));
                    }
                }
            }

            // A dictionary's order isn't promised, and an equal result has to look equal to the pipeline.
            returnMe.Sort((left, right) =>
            {
                int byId = string.CompareOrdinal(left.Id, right.Id);
                return byId != 0 ? byId : string.CompareOrdinal(left.Template.ToSource(), right.Template.ToSource());
            });
            return new EquatableArray<SaveRegistration>(returnMe.ToImmutableArray());
        }

        private static bool Add(Dictionary<string, List<SaveTemplate>> known, string id, SaveTemplate template)
        {
            List<SaveTemplate> templates;
            if (!known.TryGetValue(id, out templates))
            {
                templates = new List<SaveTemplate>();
                known.Add(id, templates);
            }

            if (templates.Contains(template))
            {
                return false;
            }

            templates.Add(template);
            return true;
        }

        /// <summary>
        /// Returns the registrations the calls in <paramref name="edges"/> add to <paramref name="seeds"/>, by
        /// handing registered methods' type parameters on.
        /// </summary>
        /// <param name="dropped">
        /// Gets each method that couldn't be registered, and why, since what it saves can't be spelled in an attribute.
        /// </param>
        public static List<SaveRegistration> Solve(IEnumerable<SaveRegistration> seeds, IEnumerable<SaveEdge> edges,
            List<KeyValuePair<string, string>> dropped)
        {
            var known = new Dictionary<string, List<SaveTemplate>>();
            foreach (SaveRegistration seed in seeds)
            {
                Add(known, seed.Id, seed.Template);
            }

            var returnMe = new List<SaveRegistration>();
            List<SaveEdge> edgeList = edges.ToList();

            // A registration can make a caller registered, and so make its own callers registered.  This runs until
            // a pass adds nothing.  A template that nests too deep is dropped, which is what ends a method that keeps
            // passing a bigger type to itself.
            bool changed = true;
            while (changed)
            {
                changed = false;
                foreach (SaveEdge edge in edgeList)
                {
                    for (int callee = 0; callee < edge.CalleeIds.Items.Length; ++callee)
                    {
                        List<SaveTemplate> saved;
                        if (!known.TryGetValue(edge.CalleeIds.Items[callee], out saved))
                        {
                            continue;
                        }

                        ImmutableArray<SaveTemplate> classArguments = callee < edge.CalleeClassArguments.Items.Length
                            ? edge.CalleeClassArguments.Items[callee].Items
                            : ImmutableArray<SaveTemplate>.Empty;

                        // The list grows when a method hands its own parameters to itself.
                        for (int i = 0; i < saved.Count; ++i)
                        {
                            SaveTemplate composed = saved[i].Fill(edge.Arguments.Items, classArguments);
                            if (composed == null || !(composed.HasParameter || composed.HasUnspellable))
                            {
                                continue;
                            }

                            string reason = null;
                            if (composed.HasUnspellable)
                            {
                                reason = UnspellableReason;
                            }
                            else if (composed.Depth > SaveTemplate.MaxDepth)
                            {
                                reason = "nests more than " + SaveTemplate.MaxDepth + " types deep";
                            }

                            for (int caller = 0; caller < edge.CallerIds.Items.Length; ++caller)
                            {
                                string callerId = edge.CallerIds.Items[caller];
                                SaveTemplate registered = composed;

                                // An interface or base class numbers its own type parameters, so a template that uses
                                // the holding type's parameters is renumbered to be registered under one.
                                if (reason == null && composed.HasClassParameter && caller >= edge.OwnCallerCount)
                                {
                                    ImmutableArray<int> map = caller < edge.CallerClassMaps.Items.Length
                                        ? edge.CallerClassMaps.Items[caller].Items
                                        : ImmutableArray<int>.Empty;
                                    registered = composed.RemapClassParameters(map);
                                    if (registered == null)
                                    {
                                        reason = InheritedReason;
                                    }
                                }

                                if (reason != null)
                                {
                                    var problem = new KeyValuePair<string, string>(callerId, reason);
                                    if (!dropped.Contains(problem))
                                    {
                                        dropped.Add(problem);
                                    }

                                    // The reason belongs to this caller ID alone when it's the interface's or base's.
                                    if (reason == InheritedReason)
                                    {
                                        reason = null;
                                    }
                                }
                                else if (Add(known, callerId, registered))
                                {
                                    returnMe.Add(new SaveRegistration(callerId, registered));
                                    changed = true;
                                }
                            }
                        }
                    }
                }
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the attribute for each of <paramref name="registrations"/>.
        /// </summary>
        public static List<string> Attributes(IEnumerable<SaveRegistration> registrations)
        {
            return registrations.Select(registration => Attribute(registration.Id, registration.Template)).ToList();
        }

        // A callee with no type parameters is handed the types its Type arguments name.  Only a use of one method can
        // hand on its type arguments, since a use of several has no one list to number them by.
        private static List<ITypeSymbol> HandedTypes(IOperation use, IReadOnlyList<IMethodSymbol> targets)
        {
            var returnMe = new List<ITypeSymbol>();
            var invocation = use as IInvocationOperation;
            if (targets.Count == 1 && targets[0].IsGenericMethod)
            {
                returnMe.AddRange(targets[0].TypeArguments);
                return returnMe;
            }

            if (invocation == null)
            {
                return returnMe;
            }

            foreach (IArgumentOperation argument in invocation.Arguments)
            {
                if (argument.Parameter?.Type.ToDisplayString() == "System.Type")
                {
                    returnMe.Add((argument.Value as ITypeOfOperation)?.TypeOperand);
                }
            }

            return returnMe;
        }

        // Returns whether the type uses a type parameter of the member, or of the type around it.  A type nests as deep
        // as the source does, so this keeps its own stack and gives up at a size no real type reaches.
        private static bool UsesParameterOf(ITypeSymbol type, IMethodSymbol member)
        {
            var pending = new Stack<ITypeSymbol>();
            pending.Push(type);
            for (int visited = 0; pending.Count > 0 && visited < 4096; ++visited)
            {
                ITypeSymbol current = pending.Pop();
                var parameter = current as ITypeParameterSymbol;
                if (parameter != null)
                {
                    if (parameter.TypeParameterKind == TypeParameterKind.Type
                        || SymbolEqualityComparer.Default.Equals(parameter.DeclaringMethod, member))
                    {
                        return true;
                    }

                    continue;
                }

                var array = current as IArrayTypeSymbol;
                if (array != null)
                {
                    pending.Push(array.ElementType);
                    continue;
                }

                for (var named = current as INamedTypeSymbol; named != null; named = named.ContainingType)
                {
                    foreach (ITypeSymbol argument in named.TypeArguments)
                    {
                        pending.Push(argument);
                    }
                }
            }

            return false;
        }

        private static bool NamesIn(SyntaxNode code)
        {
            if (code == null)
            {
                return false;
            }

            foreach (SyntaxNode node in code.DescendantNodesAndSelf())
            {
                if (node is IdentifierNameSyntax
                    || node is InvocationExpressionSyntax
                    || node is ElementAccessExpressionSyntax
                    || node is ElementBindingExpressionSyntax)
                {
                    return true;
                }
            }

            return false;
        }

        // Binding is what costs, and any name in a body could be a property.  The signature is skipped, since its
        // types are names too.  A primary constructor's code is the arguments it hands its base class.
        private static bool NamesAnything(SyntaxNode member)
        {
            var method = member as BaseMethodDeclarationSyntax;
            var constructor = member as ConstructorDeclarationSyntax;
            var accessor = member as AccessorDeclarationSyntax;
            var type = member as TypeDeclarationSyntax;
            if (method != null)
            {
                return NamesIn(method.Body)
                    || NamesIn(method.ExpressionBody)
                    || (constructor != null && NamesIn(constructor.Initializer));
            }

            if (accessor != null)
            {
                return NamesIn(accessor.Body) || NamesIn(accessor.ExpressionBody);
            }

            if (type != null)
            {
                return type.BaseList != null && type.BaseList.Types.OfType<PrimaryConstructorBaseTypeSyntax>()
                    .Any(baseType => NamesIn(baseType.ArgumentList));
            }

            return NamesIn(member);
        }

        // Static members and constants have no instance to be called on, so nothing hands them anything.
        private static bool IsInstance(SyntaxTokenList modifiers)
        {
            return !modifiers.Any(SyntaxKind.StaticKeyword) && !modifiers.Any(SyntaxKind.ConstKeyword);
        }

        // An initializer of an instance field or property, which every instance constructor runs.
        private static bool IsInstanceInitializer(EqualsValueClauseSyntax clause)
        {
            var property = clause.Parent as PropertyDeclarationSyntax;
            if (property != null)
            {
                return IsInstance(property.Modifiers);
            }

            var field = clause.Parent?.Parent?.Parent as FieldDeclarationSyntax;
            return field != null && IsInstance(field.Modifiers);
        }

        // The code that runs when a member is used: a method, operator, constructor, accessor, expression-bodied
        // property, or initializer of an instance field or property.  A type with a primary constructor is its
        // constructor.
        private static bool IsMemberBody(SyntaxNode node)
        {
            if (node is MethodDeclarationSyntax
                || node is AccessorDeclarationSyntax
                || node is OperatorDeclarationSyntax
                || node is ConversionOperatorDeclarationSyntax)
            {
                return true;
            }

            var constructor = node as ConstructorDeclarationSyntax;
            var clause = node as EqualsValueClauseSyntax;
            var type = node as TypeDeclarationSyntax;
            if (constructor != null)
            {
                return IsInstance(constructor.Modifiers);
            }

            if (clause != null)
            {
                return IsInstanceInitializer(clause);
            }

            if (type != null)
            {
                return type.ParameterList != null;
            }

            return node is ArrowExpressionClauseSyntax
                && (node.Parent is PropertyDeclarationSyntax || node.Parent is IndexerDeclarationSyntax);
        }

        /// <summary>
        /// Returns whether <paramref name="node"/> is a method, constructor, accessor, initializer or property body
        /// that names something, and has type parameters of its own or sits inside a type that has them, so what it
        /// saves could be one of them.
        /// </summary>
        public static bool MightHoldEdges(SyntaxNode node, CancellationToken cancellation)
        {
            if (!IsMemberBody(node))
            {
                return false;
            }

            var method = node as MethodDeclarationSyntax;
            bool hasTypeParameters = method != null && method.TypeParameterList != null;
            for (SyntaxNode ancestor = node; !hasTypeParameters && ancestor != null;
                ancestor = ancestor.Parent)
            {
                var type = ancestor as TypeDeclarationSyntax;
                hasTypeParameters = type != null && type.TypeParameterList != null;
            }

            return hasTypeParameters && NamesAnything(node);
        }

        // What a type the member hands on is in terms of the member's own type parameters.  A closed type that can't be
        // spelled hands nothing on, which is null.  One that uses a parameter is the callee's to warn about, if it
        // saves that argument.
        private static SaveTemplate HandedTemplate(ITypeSymbol handed, IMethodSymbol member, ref IMethodSymbol owner)
        {
            if (handed == null)
            {
                return null;
            }

            SaveTemplate template = SaveTemplate.Of(handed, ref owner);
            if (template == null && UsesParameterOf(handed, member))
            {
                template = SaveTemplate.Unspellable;
            }

            return template;
        }

        private static bool HandsOn(SaveTemplate template)
        {
            return template != null && (template.HasParameter || template.HasUnspellable);
        }

        /// <summary>
        /// Holds the kinds of operation that run a method, so a use of any of them can be a call to a registered one.
        /// </summary>
        public static readonly ImmutableArray<OperationKind> UseKinds = ImmutableArray.Create(
            OperationKind.Invocation, OperationKind.ObjectCreation, OperationKind.PropertyReference,
            OperationKind.EventAssignment, OperationKind.MethodReference, OperationKind.Binary, OperationKind.Unary,
            OperationKind.Conversion, OperationKind.CompoundAssignment, OperationKind.Increment,
            OperationKind.Decrement, OperationKind.Loop, OperationKind.DeconstructionAssignment);

        // A property that returns by reference is assigned through its getter.  Which accessors run otherwise depends
        // on whether the reference is read, written, or both.
        private static List<IMethodSymbol> AccessorsUsed(IPropertyReferenceOperation reference)
        {
            IPropertySymbol property = reference.Property;
            // A tuple on the left of a deconstruction assigns each of its elements.
            IOperation target = reference;
            while (target.Parent is ITupleOperation)
            {
                target = target.Parent;
            }

            bool reads = true;
            bool writes = false;
            var assignment = target.Parent as IAssignmentOperation;
            if (assignment != null && assignment.Target == target)
            {
                writes = true;
                reads = !(assignment is ISimpleAssignmentOperation || assignment is IDeconstructionAssignmentOperation);
            }
            else if (reference.Parent is IIncrementOrDecrementOperation)
            {
                writes = true;
            }

            if (property.ReturnsByRef || property.ReturnsByRefReadonly)
            {
                reads = true;
                writes = false;
            }

            var returnMe = new List<IMethodSymbol>();
            if (reads && property.GetMethod != null)
            {
                returnMe.Add(property.GetMethod);
            }

            if (writes && property.SetMethod != null)
            {
                returnMe.Add(property.SetMethod);
            }

            return returnMe;
        }

        private static readonly IMethodSymbol[] NoMethods = new IMethodSymbol[0];

        private static IReadOnlyList<IMethodSymbol> Only(IMethodSymbol method)
        {
            return method == null ? NoMethods : new[] { method };
        }

        // The methods a foreach calls, which the compiler finds by pattern.
        private static IReadOnlyList<IMethodSymbol> IteratorMethods(IForEachLoopOperation loop)
        {
            SemanticModel model = loop.SemanticModel;
            var syntax = loop.Syntax as ForEachStatementSyntax;
            var variableSyntax = loop.Syntax as ForEachVariableStatementSyntax;
            if (model == null || (syntax == null && variableSyntax == null))
            {
                return NoMethods;
            }

            // An array is walked by index, though the model still names the IEnumerable methods for it.
            ExpressionSyntax collection = syntax != null ? syntax.Expression : variableSyntax.Expression;
            if (model.GetTypeInfo(collection).Type is IArrayTypeSymbol)
            {
                return NoMethods;
            }

            ForEachStatementInfo info = syntax != null
                ? model.GetForEachStatementInfo(syntax)
                : model.GetForEachStatementInfo(variableSyntax);
            var returnMe = new List<IMethodSymbol>();
            foreach (IMethodSymbol method in new[]
                { info.GetEnumeratorMethod, info.MoveNextMethod, info.CurrentProperty?.GetMethod, info.DisposeMethod })
            {
                if (method != null)
                {
                    returnMe.Add(method);
                }
            }

            return returnMe;
        }

        // The Deconstruct methods a deconstruction calls, one for each level of nesting that has one.
        private static IReadOnlyList<IMethodSymbol> DeconstructMethods(IDeconstructionAssignmentOperation assignment)
        {
            SemanticModel model = assignment.SemanticModel;
            var syntax = assignment.Syntax as AssignmentExpressionSyntax;
            if (model == null || syntax == null)
            {
                return NoMethods;
            }

            var returnMe = new List<IMethodSymbol>();
            var pending = new Stack<DeconstructionInfo>();
            pending.Push(model.GetDeconstructionInfo(syntax));
            while (pending.Count > 0)
            {
                DeconstructionInfo info = pending.Pop();
                if (info.Method != null)
                {
                    returnMe.Add(info.Method);
                }

                if (!info.Nested.IsDefaultOrEmpty)
                {
                    foreach (DeconstructionInfo nested in info.Nested)
                    {
                        pending.Push(nested);
                    }
                }
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the methods running <paramref name="use"/> calls.  That is the method of a call, a method group or a
        /// user-defined operator, the constructor of an object creation, the accessors of a property reference or an
        /// event subscription, and the methods of a foreach or a deconstruction.  Anything else calls none.
        /// </summary>
        public static IReadOnlyList<IMethodSymbol> Called(IOperation use)
        {
            switch (use.Kind)
            {
                case OperationKind.Invocation:
                    return Only(((IInvocationOperation)use).TargetMethod);
                case OperationKind.ObjectCreation:
                    // A creation of an anonymous type or a struct's default value runs no constructor.
                    return Only(((IObjectCreationOperation)use).Constructor);
                case OperationKind.PropertyReference:
                    return AccessorsUsed((IPropertyReferenceOperation)use);
                case OperationKind.EventAssignment:
                    var subscription = (IEventAssignmentOperation)use;
                    IEventSymbol subscribed = (subscription.EventReference as IEventReferenceOperation)?.Event;
                    return Only(subscribed == null ? null
                        : subscription.Adds ? subscribed.AddMethod : subscribed.RemoveMethod);
                case OperationKind.MethodReference:
                    return Only(((IMethodReferenceOperation)use).Method);
                case OperationKind.Binary:
                    return Only(((IBinaryOperation)use).OperatorMethod);
                case OperationKind.Unary:
                    return Only(((IUnaryOperation)use).OperatorMethod);
                case OperationKind.Conversion:
                    return Only(((IConversionOperation)use).OperatorMethod);
                case OperationKind.CompoundAssignment:
                    return Only(((ICompoundAssignmentOperation)use).OperatorMethod);
                case OperationKind.Increment:
                case OperationKind.Decrement:
                    return Only(((IIncrementOrDecrementOperation)use).OperatorMethod);
                case OperationKind.Loop:
                    var loop = use as IForEachLoopOperation;
                    return loop == null ? NoMethods : IteratorMethods(loop);
                case OperationKind.DeconstructionAssignment:
                    return DeconstructMethods((IDeconstructionAssignmentOperation)use);
                default:
                    return NoMethods;
            }
        }

        /// <summary>
        /// Returns the type <paramref name="use"/> reaches its member through, or null if it has no instance.
        /// </summary>
        public static ITypeSymbol ReceiverOf(IOperation use)
        {
            var invocation = use as IInvocationOperation;
            var property = use as IPropertyReferenceOperation;
            var subscription = use as IEventAssignmentOperation;
            var reference = use as IMethodReferenceOperation;
            if (invocation != null)
            {
                return invocation.Instance?.Type;
            }

            if (property != null)
            {
                return property.Instance?.Type;
            }

            if (reference != null)
            {
                return reference.Instance?.Type;
            }

            return (subscription?.EventReference as IEventReferenceOperation)?.Instance?.Type;
        }

        // The edge for a use inside the member, if it hands one of the member's type parameters, or one of the type
        // around it, on to a callee.
        private static SaveEdge EdgeOf(IOperation use, IMethodSymbol member)
        {
            // Most operations in a body call nothing.
            if (!UseKinds.Contains(use.Kind))
            {
                return null;
            }

            IReadOnlyList<IMethodSymbol> targets = Called(use);
            if (targets.Count == 0)
            {
                return null;
            }

            // A local function or lambda inside the member has type parameters of its own, which the member's callers
            // can't be asked to supply.
            IMethodSymbol owner = member;
            bool handsOnAParameter = false;
            var arguments = ImmutableArray.CreateBuilder<SaveTemplate>();
            foreach (ITypeSymbol handed in HandedTypes(use, targets))
            {
                SaveTemplate template = HandedTemplate(handed, member, ref owner);
                handsOnAParameter |= HandsOn(template);
                arguments.Add(template);
            }

            var calleeIds = new List<string>();
            var calleeClassArguments = new List<EquatableArray<SaveTemplate>>();
            ITypeSymbol receiver = ReceiverOf(use);
            foreach (IMethodSymbol target in targets)
            {
                foreach (IMethodSymbol candidate in Candidates(target, receiver))
                {
                    string id = candidate.OriginalDefinition.GetDocumentationCommentId();
                    if (id == null || calleeIds.Contains(id))
                    {
                        continue;
                    }

                    var classArguments = ImmutableArray.CreateBuilder<SaveTemplate>();
                    foreach (ITypeSymbol argument in SavedTypeAnalyzer.ClassArgumentsOf(candidate.ContainingType))
                    {
                        SaveTemplate template = HandedTemplate(argument, member, ref owner);
                        handsOnAParameter |= HandsOn(template);
                        classArguments.Add(template);
                    }

                    calleeIds.Add(id);
                    calleeClassArguments.Add(new EquatableArray<SaveTemplate>(classArguments.ToImmutable()));
                }
            }

            if (!handsOnAParameter)
            {
                return null;
            }

            int ownCount;
            List<EquatableArray<int>> classMaps;
            List<string> callerIds = RegistrationIds(member, out ownCount, out classMaps);
            if (callerIds.Count == 0)
            {
                return null;
            }

            return new SaveEdge(new EquatableArray<string>(callerIds.ToImmutableArray()), ownCount,
                new EquatableArray<EquatableArray<int>>(classMaps.ToImmutableArray()),
                new EquatableArray<string>(calleeIds.ToImmutableArray()),
                new EquatableArray<EquatableArray<SaveTemplate>>(calleeClassArguments.ToImmutableArray()),
                new EquatableArray<SaveTemplate>(arguments.ToImmutable()));
        }

        // Every instance constructor runs the initializers, except a record's copy constructor.  A type that declares
        // none has an implicit one that does.
        private static List<IMethodSymbol> InitializedBy(INamedTypeSymbol type)
        {
            var returnMe = new List<IMethodSymbol>();
            foreach (IMethodSymbol constructor in type.InstanceConstructors)
            {
                bool copies = type.IsRecord && constructor.Parameters.Length == 1
                    && SymbolEqualityComparer.Default.Equals(constructor.Parameters[0].Type, type);
                if (!copies)
                {
                    returnMe.Add(constructor);
                }
            }

            return returnMe;
        }

        // The methods a body belongs to.  An expression-bodied property is its getter, and the type of a primary
        // constructor is that constructor.  An initializer belongs to each constructor that runs it.
        private static List<IMethodSymbol> MembersOf(SemanticModel model, SyntaxNode node,
            CancellationToken cancellation)
        {
            var returnMe = new List<IMethodSymbol>();
            var type = node as TypeDeclarationSyntax;
            IMethodSymbol member = null;
            if (node is ArrowExpressionClauseSyntax)
            {
                member = (model.GetDeclaredSymbol(node.Parent, cancellation) as IPropertySymbol)?.GetMethod;
            }
            else if (node is EqualsValueClauseSyntax)
            {
                var container = node.Ancestors().OfType<TypeDeclarationSyntax>().FirstOrDefault();
                var containerType = container == null ? null : model.GetDeclaredSymbol(container, cancellation);
                if (containerType != null && IsInstanceInitializer((EqualsValueClauseSyntax)node))
                {
                    returnMe.AddRange(InitializedBy(containerType));
                }
            }
            else if (type != null)
            {
                INamedTypeSymbol declared = model.GetDeclaredSymbol(type, cancellation);
                member = declared?.InstanceConstructors.FirstOrDefault(
                    constructor => constructor.DeclaringSyntaxReferences
                        .Any(reference => reference.GetSyntax(cancellation) == type));
            }
            else
            {
                member = model.GetDeclaredSymbol(node, cancellation) as IMethodSymbol;
            }

            if (member != null)
            {
                returnMe.Add(member);
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the edges for the calls and property uses in the body of the member declared at
        /// <paramref name="node"/>, each once.
        /// </summary>
        public static ImmutableArray<SaveEdge> EdgesOfMember(SemanticModel model, SyntaxNode node,
            CancellationToken cancellation)
        {
            List<IMethodSymbol> members = MembersOf(model, node, cancellation);
            IOperation body = members.Count == 0 ? null : model.GetOperation(node, cancellation);
            if (body == null)
            {
                return ImmutableArray<SaveEdge>.Empty;
            }

            ImmutableArray<SaveEdge>.Builder returnMe = ImmutableArray.CreateBuilder<SaveEdge>();
            foreach (IOperation operation in body.DescendantsAndSelf())
            {
                foreach (IMethodSymbol member in members)
                {
                    SaveEdge edge = EdgeOf(operation, member);
                    if (edge != null && !returnMe.Contains(edge))
                    {
                        returnMe.Add(edge);
                    }
                }
            }

            return returnMe.ToImmutable();
        }

        /// <summary>
        /// Returns the edges for the method declared around <paramref name="context"/>.
        /// </summary>
        public static ImmutableArray<SaveEdge> FindMemberEdges(GeneratorSyntaxContext context,
            CancellationToken cancellation)
        {
            return EdgesOfMember(context.SemanticModel, context.Node, cancellation);
        }

        // A call inside a lambda or local function belongs to the method around it.
        private static IMethodSymbol EnclosingMember(SemanticModel model, SyntaxNode node,
            CancellationToken cancellation)
        {
            ISymbol symbol = model.GetEnclosingSymbol(node.SpanStart, cancellation);
            var method = symbol as IMethodSymbol;
            while (method != null
                && (method.MethodKind == MethodKind.LocalFunction || method.MethodKind == MethodKind.AnonymousFunction))
            {
                symbol = method.ContainingSymbol;
                method = symbol as IMethodSymbol;
            }

            return method;
        }

        /// <summary>
        /// Returns the edge for the call or property use at <paramref name="node"/>, if it hands one of its member's
        /// type parameters on.
        /// </summary>
        public static ImmutableArray<SaveEdge> EdgesOf(SemanticModel model, SyntaxNode node,
            CancellationToken cancellation)
        {
            IOperation use = model.GetOperation(node, cancellation);
            IMethodSymbol member = use == null ? null : EnclosingMember(model, node, cancellation);
            SaveEdge edge = member == null ? null : EdgeOf(use, member);
            return edge == null ? ImmutableArray<SaveEdge>.Empty : ImmutableArray.Create(edge);
        }

        /// <summary>
        /// Returns a file of <paramref name="attributes"/>, or null if there are none.
        /// </summary>
        public static string File(IEnumerable<string> attributes)
        {
            List<string> sorted = attributes.Distinct().OrderBy(line => line, System.StringComparer.Ordinal).ToList();
            if (sorted.Count == 0)
            {
                return null;
            }

            var code = new CodeWriter();
            code.AddLine("// <auto-generated/>");
            code.AddLine("// The generic methods Vellum.Generator found saving their type parameters, so their " +
                "callers are checked.");
            foreach (string line in sorted)
            {
                code.AddLine(line);
            }

            return code.ToString();
        }
    }
}