using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.CSharp;
using Microsoft.CodeAnalysis.CSharp.Syntax;

namespace Ariadne.Generator
{
    /// <summary>
    /// A value held in a field while a passage is paused, because an expression needs it after the pause.
    /// </summary>
    public class SpillTemp
    {
        public readonly string Name;

        public readonly ITypeSymbol Type;

        /// <summary>
        /// Holds the code the temp's value comes from, which a save library's analyzer reports a problem type on.
        /// </summary>
        public readonly Location Where;

        /// <summary>
        /// Holds whether some pause falls between the temp being set and last read, so its value is saved.
        /// </summary>
        public bool Saved;

        /// <summary>
        /// The code that builds the temp's value when the frame is made, or null to leave it unset.
        /// </summary>
        public string Initializer;

        public SpillTemp(string name, ITypeSymbol type, Location where)
        {
            Name = name;
            Type = type;
            Where = where;
        }
    }

    public enum SpillStepKind
    {
        Pause,
        Store,
        Branch,
        Jump,
        Label,
        ArmTest,
    }

    /// <summary>
    /// Says what a branch tests its operand for, besides truth.
    /// </summary>
    public enum NullCheck
    {
        None,
        IsNull,
        IsNotNull,
    }

    /// <summary>
    /// One thing to do ahead of the statement itself: pause in a passage call, store an operand, or steer around the
    /// steps of an operand that only runs sometimes.
    /// </summary>
    public class SpillStep
    {
        public readonly SpillStepKind Kind;

        /// <summary>
        /// Holds the passage call to pause in, or null for any other step.
        /// </summary>
        public readonly InvocationExpressionSyntax Call;

        /// <summary>
        /// Holds the operand a store keeps or a branch tests, or null for any other step.
        /// </summary>
        public readonly ExpressionSyntax Value;

        /// <summary>
        /// Holds the temp that receives the value, or null for a call that returns nothing and for any step that
        /// keeps no value.
        /// </summary>
        public readonly SpillTemp Temp;

        /// <summary>
        /// Holds the label a branch or jump goes to, or the label a label step defines.
        /// </summary>
        public readonly string Name;

        /// <summary>
        /// Holds whether a branch goes when its test fails.
        /// </summary>
        public readonly bool Negate;

        public readonly NullCheck NullCheck;

        /// <summary>
        /// Holds the switch expression arm an ArmTest checks the value against, or null for any other step.
        /// </summary>
        public readonly SwitchExpressionArmSyntax Arm;

        /// <summary>
        /// Holds the temps that must survive a pause in this step, which is empty for any other step.
        /// </summary>
        public readonly List<SpillTemp> LiveTemps = new List<SpillTemp>();

        private SpillStep(SpillStepKind kind, InvocationExpressionSyntax call, ExpressionSyntax value, SpillTemp temp,
            string name, bool negate, NullCheck nullCheck, SwitchExpressionArmSyntax arm = null)
        {
            Arm = arm;
            Kind = kind;
            Call = call;
            Value = value;
            Temp = temp;
            Name = name;
            Negate = negate;
            NullCheck = nullCheck;
        }

        public static SpillStep Pause(InvocationExpressionSyntax call, SpillTemp temp)
        {
            return new SpillStep(SpillStepKind.Pause, call, null, temp, null, false, NullCheck.None);
        }

        public static SpillStep Store(ExpressionSyntax value, SpillTemp temp)
        {
            return new SpillStep(SpillStepKind.Store, null, value, temp, null, false, NullCheck.None);
        }

        public static SpillStep Branch(ExpressionSyntax value, bool negate, NullCheck nullCheck, string target)
        {
            return new SpillStep(SpillStepKind.Branch, null, value, null, target, negate, nullCheck);
        }

        /// <summary>
        /// Makes a step that goes to <paramref name="target"/> unless the value matches the arm.
        /// </summary>
        public static SpillStep ArmTest(ExpressionSyntax value, SwitchExpressionArmSyntax arm, string target)
        {
            return new SpillStep(SpillStepKind.ArmTest, null, value, null, target, true, NullCheck.None, arm);
        }

        public static SpillStep Jump(string target)
        {
            return new SpillStep(SpillStepKind.Jump, null, null, null, target, false, NullCheck.None);
        }

        public static SpillStep Label(string name)
        {
            return new SpillStep(SpillStepKind.Label, null, null, null, name, false, NullCheck.None);
        }
    }

    /// <summary>
    /// What an expression with a pause inside it becomes: steps to run in order, then the expression with each
    /// replaced operand read from its temp.
    /// </summary>
    public class SpillSequence
    {
        public readonly List<SpillStep> Steps = new List<SpillStep>();

        public readonly Dictionary<SyntaxNode, SpillTemp> Replacements = new Dictionary<SyntaxNode, SpillTemp>();

        public readonly List<SpillTemp> Temps = new List<SpillTemp>();

        /// <summary>
        /// Holds how many operators were turned into jumps, which the labels they use are numbered by.
        /// </summary>
        public int Conditionals;
    }

    /// <summary>
    /// Lifts the passage calls out of an expression without changing the order C# evaluates it in: every operand that
    /// comes before a call, and might not hold the same value after the pause, is stored first.
    /// </summary>
    public class ExpressionSpiller
    {
        private class Frame
        {
            public ExpressionSyntax Node;

            /// <summary>
            /// Holds the operands in the order C# evaluates them.
            /// </summary>
            public readonly List<ExpressionSyntax> Operands = new List<ExpressionSyntax>();

            /// <summary>
            /// Holds how many of the leading operands are the object a call or index is made on.
            /// </summary>
            public int Receivers;

            public int Next;

            /// <summary>
            /// Holds the operands already evaluated.
            /// </summary>
            public readonly List<ExpressionSyntax> Done = new List<ExpressionSyntax>();

            /// <summary>
            /// Holds whether the first operand decides if the others run, and the others have a pause in them.
            /// </summary>
            public bool Conditional;

            /// <summary>
            /// Holds the arms of a switch expression whose arms are conditional, or null for any other frame.
            /// </summary>
            public IReadOnlyList<SwitchExpressionArmSyntax> Arms;

            /// <summary>
            /// Holds whether the first operand is a variable the node writes, which the node's own code goes on to
            /// read in place.
            /// </summary>
            public bool Assigns;

            /// <summary>
            /// Holds how many operands have been completed.
            /// </summary>
            public int Finished;

            public int Number;
        }

        private readonly ScriptClass script;
        private readonly SemanticModel model;
        private readonly HashSet<SyntaxNode> spine = new HashSet<SyntaxNode>();
        private readonly HashSet<ISymbol> assigned = new HashSet<ISymbol>(SymbolEqualityComparer.Default);
        private readonly SpillSequence returnMe = new SpillSequence();
        private readonly int firstNumber;
        private readonly int firstConditional;

        private ExpressionSpiller(ScriptClass script, SemanticModel model, int firstNumber, int firstConditional)
        {
            this.script = script;
            this.model = model;
            this.firstNumber = firstNumber;
            this.firstConditional = firstConditional;
        }

        private static bool InFunction(SyntaxNode node, SyntaxNode root)
        {
            for (SyntaxNode current = node.Parent; current != null; current = current.Parent)
            {
                if (current is AnonymousFunctionExpressionSyntax || current is LocalFunctionStatementSyntax)
                {
                    return true;
                }

                if (current == root)
                {
                    return false;
                }
            }

            return false;
        }

        // A local or parameter can't change while the callee runs, unless this statement itself assigns it.
        private void FindAssigned(SyntaxNode statement)
        {
            foreach (SyntaxNode node in statement.DescendantNodesAndSelf())
            {
                ExpressionSyntax target = null;
                var assignment = node as AssignmentExpressionSyntax;
                if (assignment != null)
                {
                    target = assignment.Left;
                }

                var prefix = node as PrefixUnaryExpressionSyntax;
                if (prefix != null && (prefix.IsKind(SyntaxKind.PreIncrementExpression)
                    || prefix.IsKind(SyntaxKind.PreDecrementExpression)))
                {
                    target = prefix.Operand;
                }

                var postfix = node as PostfixUnaryExpressionSyntax;
                if (postfix != null)
                {
                    target = postfix.Operand;
                }

                var argument = node as ArgumentSyntax;
                if (argument != null && !argument.RefKindKeyword.IsKind(SyntaxKind.None)
                    && !argument.RefKindKeyword.IsKind(SyntaxKind.InKeyword))
                {
                    target = argument.Expression;
                }

                if (target != null)
                {
                    ISymbol symbol = model.GetSymbolInfo(target).Symbol;
                    if (symbol != null)
                    {
                        assigned.Add(symbol);
                    }
                }
            }
        }

        private ITypeSymbol TypeOf(ExpressionSyntax node)
        {
            TypeInfo info = model.GetTypeInfo(node);
            ITypeSymbol type = info.Type ?? info.ConvertedType;
            if (type == null
                || type.TypeKind == TypeKind.Error
                || type.SpecialType == SpecialType.System_Void
                || type.IsAnonymousType
                || type.IsRefLikeType)
            {
                return null;
            }

            return type;
        }

        private bool IsStable(ExpressionSyntax node)
        {
            while (node is ParenthesizedExpressionSyntax)
            {
                node = ((ParenthesizedExpressionSyntax)node).Expression;
            }

            if (model.GetConstantValue(node).HasValue)
            {
                return true;
            }

            if (node is LiteralExpressionSyntax
                || node is ThisExpressionSyntax
                || node is BaseExpressionSyntax
                || node is TypeOfExpressionSyntax
                || node is DefaultExpressionSyntax)
            {
                return true;
            }

            if (node is IdentifierNameSyntax
                || node is MemberAccessExpressionSyntax
                || node is PredefinedTypeSyntax)
            {
                ISymbol symbol = model.GetSymbolInfo(node).Symbol;
                if ((symbol is ILocalSymbol || symbol is IParameterSymbol) && !assigned.Contains(symbol))
                {
                    return true;
                }
            }

            return IsObjectRead(node);
        }

        // A name, or a chain of fields and properties, that holds an object.  The object is the world's own, so a
        // copy kept across the pause (and saved) would be a different one.  Reading it again afterward is what the
        // script means.
        private bool IsObjectRead(ExpressionSyntax node)
        {
            ITypeSymbol type = TypeOf(node);
            if (type == null || type.IsValueType || type.SpecialType == SpecialType.System_String)
            {
                return false;
            }

            while (true)
            {
                if (node is ThisExpressionSyntax)
                {
                    return true;
                }

                ISymbol symbol = model.GetSymbolInfo(node).Symbol;
                if (symbol is INamespaceOrTypeSymbol)
                {
                    return true;
                }

                if (assigned.Contains(symbol)
                    || !(symbol is ILocalSymbol || symbol is IParameterSymbol || symbol is IFieldSymbol
                        || symbol is IPropertySymbol))
                {
                    return false;
                }

                var member = node as MemberAccessExpressionSyntax;
                if (member == null)
                {
                    return node is IdentifierNameSyntax;
                }

                node = member.Expression;
            }
        }

        // Passing a variable by reference reads nothing, so it can be passed after the pause.
        private static bool IsPlainLocation(ExpressionSyntax expression)
        {
            return ScriptClass.IsPlainTarget(expression);
        }

        // An out argument that declares a variable is made by the call itself, so only a passage call can take one.
        private bool AddArguments(Frame frame, IEnumerable<ArgumentSyntax> arguments, bool declares = false)
        {
            foreach (ArgumentSyntax argument in arguments)
            {
                if (argument.RefKindKeyword.IsKind(SyntaxKind.None)
                    || argument.RefKindKeyword.IsKind(SyntaxKind.InKeyword))
                {
                    frame.Operands.Add(argument.Expression);
                }
                else if (!IsPlainLocation(argument.Expression)
                    && !(declares && argument.Expression is DeclarationExpressionSyntax))
                {
                    return false;
                }
            }

            return true;
        }

        private bool AddInvocationOperands(Frame frame, InvocationExpressionSyntax invocation)
        {
            ExpressionSyntax target = invocation.Expression;
            var member = target as MemberAccessExpressionSyntax;
            if (member != null && member.IsKind(SyntaxKind.SimpleMemberAccessExpression))
            {
                // A binding is only half of an expression, so it can't be set aside on its own.
                if (member.Expression is MemberBindingExpressionSyntax
                    || member.Expression is ElementBindingExpressionSyntax)
                {
                    return false;
                }

                if (!(model.GetSymbolInfo(member.Expression).Symbol is INamespaceOrTypeSymbol))
                {
                    frame.Operands.Add(member.Expression);
                    frame.Receivers = 1;
                }
            }
            else if (target is MemberBindingExpressionSyntax)
            {
                // The object is the one before the ?. that this call hangs from.
            }
            else if (target is IdentifierNameSyntax || target is GenericNameSyntax)
            {
                if (!(model.GetSymbolInfo(target).Symbol is IMethodSymbol))
                {
                    frame.Operands.Add(target);
                    frame.Receivers = 1;
                }
            }
            else
            {
                return false;
            }

            return AddArguments(frame, invocation.ArgumentList.Arguments,
                declares: script.AnyPassageCalled(invocation) != null);
        }

        /// <summary>
        /// Returns whether <paramref name="node"/> is the variable that a compound assignment reads, applies an
        /// operator to and writes back.
        /// </summary>
        public static bool IsCompoundTarget(SyntaxNode node)
        {
            var assignment = node.Parent as AssignmentExpressionSyntax;

            return assignment != null
                && assignment.Left == node
                && !assignment.IsKind(SyntaxKind.SimpleAssignmentExpression);
        }

        // A declaration, or a tuple of names, declarations and discards.  Assigning to one works nothing out first.
        private static bool IsDeconstructionTarget(ExpressionSyntax target)
        {
            if (target is DeclarationExpressionSyntax)
            {
                return true;
            }

            var tuple = target as TupleExpressionSyntax;
            if (tuple == null)
            {
                return false;
            }

            return tuple.Arguments.All(argument => ScriptClass.IsPlainTarget(argument.Expression)
                || IsDeconstructionTarget(argument.Expression));
        }

        // C# works out the object and index a target is reached through first, then (for a compound assignment) reads
        // the old value, then the right side.  A plain name has nothing to work out.
        private bool DescribeAssignment(Frame frame, AssignmentExpressionSyntax assignment)
        {
            ExpressionSyntax left = assignment.Left;
            bool simple = assignment.IsKind(SyntaxKind.SimpleAssignmentExpression);
            bool coalesce = assignment.IsKind(SyntaxKind.CoalesceAssignmentExpression);
            bool plain = ScriptClass.IsPlainTarget(left);
            if (model.GetSymbolInfo(left).Symbol is IEventSymbol || (coalesce && !plain))
            {
                return false;
            }

            var element = left as ElementAccessExpressionSyntax;
            var member = left as MemberAccessExpressionSyntax;
            bool reachable = true;
            if (!plain && element != null)
            {
                frame.Operands.Add(element.Expression);
                frame.Receivers = 1;
                reachable = AddArguments(frame, element.ArgumentList.Arguments);
            }
            else if (!plain && member != null && member.IsKind(SyntaxKind.SimpleMemberAccessExpression))
            {
                frame.Operands.Add(member.Expression);
                frame.Receivers = 1;
            }
            else if (!plain && !(simple && IsDeconstructionTarget(left)))
            {
                return false;
            }

            if (!simple)
            {
                frame.Operands.Add(left);
            }

            frame.Operands.Add(assignment.Right);
            if (coalesce)
            {
                frame.Assigns = true;
                frame.Conditional = spine.Contains(assignment.Right);
            }

            return reachable;
        }

        // Fills in the operands of an expression with a passage call inside it, in evaluation order.  Returns false for
        // an expression this doesn't know how to take apart yet.
        private bool Describe(Frame frame)
        {
            ExpressionSyntax node = frame.Node;
            switch (node.Kind())
            {
                case SyntaxKind.ParenthesizedExpression:
                    frame.Operands.Add(((ParenthesizedExpressionSyntax)node).Expression);
                    return true;
                case SyntaxKind.CastExpression:
                    frame.Operands.Add(((CastExpressionSyntax)node).Expression);
                    return true;
                case SyntaxKind.UnaryPlusExpression:
                case SyntaxKind.UnaryMinusExpression:
                case SyntaxKind.BitwiseNotExpression:
                case SyntaxKind.LogicalNotExpression:
                    frame.Operands.Add(((PrefixUnaryExpressionSyntax)node).Operand);
                    return true;
                case SyntaxKind.AddExpression:
                case SyntaxKind.SubtractExpression:
                case SyntaxKind.MultiplyExpression:
                case SyntaxKind.DivideExpression:
                case SyntaxKind.ModuloExpression:
                case SyntaxKind.LeftShiftExpression:
                case SyntaxKind.RightShiftExpression:
                case SyntaxKind.BitwiseOrExpression:
                case SyntaxKind.BitwiseAndExpression:
                case SyntaxKind.ExclusiveOrExpression:
                case SyntaxKind.EqualsExpression:
                case SyntaxKind.NotEqualsExpression:
                case SyntaxKind.LessThanExpression:
                case SyntaxKind.LessThanOrEqualExpression:
                case SyntaxKind.GreaterThanExpression:
                case SyntaxKind.GreaterThanOrEqualExpression:
                    frame.Operands.Add(((BinaryExpressionSyntax)node).Left);
                    frame.Operands.Add(((BinaryExpressionSyntax)node).Right);
                    return true;
                case SyntaxKind.SimpleAssignmentExpression:
                case SyntaxKind.AddAssignmentExpression:
                case SyntaxKind.SubtractAssignmentExpression:
                case SyntaxKind.MultiplyAssignmentExpression:
                case SyntaxKind.DivideAssignmentExpression:
                case SyntaxKind.ModuloAssignmentExpression:
                case SyntaxKind.AndAssignmentExpression:
                case SyntaxKind.ExclusiveOrAssignmentExpression:
                case SyntaxKind.OrAssignmentExpression:
                case SyntaxKind.LeftShiftAssignmentExpression:
                case SyntaxKind.RightShiftAssignmentExpression:
                case SyntaxKind.CoalesceAssignmentExpression:
                    return DescribeAssignment(frame, (AssignmentExpressionSyntax)node);
                case SyntaxKind.IsExpression:
                case SyntaxKind.AsExpression:
                    frame.Operands.Add(((BinaryExpressionSyntax)node).Left);
                    return true;
                case SyntaxKind.IsPatternExpression:
                    frame.Operands.Add(((IsPatternExpressionSyntax)node).Expression);
                    return true;
                case SyntaxKind.SwitchExpression:
                    var switchExpression = (SwitchExpressionSyntax)node;
                    frame.Operands.Add(switchExpression.GoverningExpression);

                    // A guard is checked ahead of every arm, so it can't hold a pause that only one arm would run.
                    if (switchExpression.Arms.Any(arm => arm.WhenClause != null && spine.Contains(arm.WhenClause)))
                    {
                        return false;
                    }

                    if (switchExpression.Arms.Any(arm => spine.Contains(arm)))
                    {
                        frame.Arms = switchExpression.Arms.ToList();
                        frame.Conditional = true;
                        frame.Operands.AddRange(switchExpression.Arms.Select(arm => arm.Expression));
                    }

                    return true;
                case SyntaxKind.SimpleMemberAccessExpression:
                    frame.Operands.Add(((MemberAccessExpressionSyntax)node).Expression);
                    return true;
                case SyntaxKind.ElementAccessExpression:
                    var element = (ElementAccessExpressionSyntax)node;
                    frame.Operands.Add(element.Expression);
                    frame.Receivers = 1;
                    return AddArguments(frame, element.ArgumentList.Arguments);
                case SyntaxKind.InvocationExpression:
                    return AddInvocationOperands(frame, (InvocationExpressionSyntax)node);
                case SyntaxKind.ObjectCreationExpression:
                    var creation = (ObjectCreationExpressionSyntax)node;
                    return creation.Initializer == null && creation.ArgumentList != null
                        && AddArguments(frame, creation.ArgumentList.Arguments);
                case SyntaxKind.InterpolatedStringExpression:
                    foreach (InterpolatedStringContentSyntax content in
                        ((InterpolatedStringExpressionSyntax)node).Contents)
                    {
                        var interpolation = content as InterpolationSyntax;
                        if (interpolation != null)
                        {
                            frame.Operands.Add(interpolation.Expression);
                        }
                    }

                    return true;
                case SyntaxKind.TupleExpression:
                    return AddArguments(frame, ((TupleExpressionSyntax)node).Arguments);
                case SyntaxKind.LogicalAndExpression:
                case SyntaxKind.LogicalOrExpression:
                case SyntaxKind.CoalesceExpression:
                    var shortCircuit = (BinaryExpressionSyntax)node;
                    frame.Operands.Add(shortCircuit.Left);
                    frame.Operands.Add(shortCircuit.Right);
                    frame.Conditional = spine.Contains(shortCircuit.Right);
                    return true;
                case SyntaxKind.ConditionalExpression:
                    var conditional = (ConditionalExpressionSyntax)node;
                    frame.Operands.Add(conditional.Condition);
                    frame.Operands.Add(conditional.WhenTrue);
                    frame.Operands.Add(conditional.WhenFalse);
                    frame.Conditional = spine.Contains(conditional.WhenTrue) || spine.Contains(conditional.WhenFalse);
                    return true;
                case SyntaxKind.ConditionalAccessExpression:
                    var access = (ConditionalAccessExpressionSyntax)node;
                    if (access.Expression is MemberBindingExpressionSyntax
                        || access.Expression is ElementBindingExpressionSyntax
                        || access.Expression is ConditionalAccessExpressionSyntax)
                    {
                        return false;
                    }

                    frame.Operands.Add(access.Expression);
                    if (spine.Contains(access.WhenNotNull))
                    {
                        frame.Operands.Add(access.WhenNotNull);
                        frame.Conditional = true;
                    }

                    return true;
                case SyntaxKind.ElementBindingExpression:
                    return AddArguments(frame, ((ElementBindingExpressionSyntax)node).ArgumentList.Arguments);
                default:
                    return false;
            }
        }

        private SpillTemp NewTemp(ITypeSymbol type, Location where)
        {
            var temp = new SpillTemp("__spill" + (firstNumber + returnMe.Temps.Count), type, where);
            returnMe.Temps.Add(temp);
            return temp;
        }

        // Stores each operand that has already been evaluated and might change meanwhile, outermost first, since
        // that's the order they were evaluated in.  Returns false if one can't be stored without changing what the
        // expression means.
        private bool SpillPending(List<Frame> frames)
        {
            foreach (Frame frame in frames)
            {
                for (int i = 0; i < frame.Done.Count; ++i)
                {
                    ExpressionSyntax operand = frame.Done[i];
                    if (returnMe.Replacements.ContainsKey(operand) || IsStable(operand))
                    {
                        continue;
                    }

                    ITypeSymbol type = TypeOf(operand);

                    // A copy of a struct would take the changes meant for the original.
                    if (type == null || (i < frame.Receivers && type.IsValueType))
                    {
                        return false;
                    }

                    SpillTemp temp = NewTemp(type, operand.GetLocation());
                    returnMe.Steps.Add(SpillStep.Store(operand, temp));
                    returnMe.Replacements[operand] = temp;
                }
            }

            return true;
        }

        // Whatever came before an operator that only sometimes runs its later operands has to be settled first, since
        // the branch will skip any steps that were left to the later operands.
        private bool Begin(List<Frame> ancestors, Frame frame)
        {
            if (!frame.Conditional)
            {
                return true;
            }

            frame.Number = firstConditional + returnMe.Conditionals++;
            return SpillPending(ancestors);
        }

        private static string EndLabel(Frame frame)
        {
            return "__cond" + frame.Number + "End";
        }

        private static string ElseLabel(Frame frame)
        {
            return "__cond" + frame.Number + "Else";
        }

        // Keeps the operand that decides which others run, if it might not read the same after a pause.
        private bool StoreDecider(ExpressionSyntax decider)
        {
            if (!returnMe.Replacements.ContainsKey(decider) && !IsStable(decider))
            {
                ITypeSymbol type = TypeOf(decider);
                if (type == null)
                {
                    return false;
                }

                SpillTemp temp = NewTemp(type, decider.GetLocation());
                returnMe.Steps.Add(SpillStep.Store(decider, temp));
                returnMe.Replacements[decider] = temp;
            }

            return true;
        }

        private static string ArmLabel(Frame frame, int arm)
        {
            return "__cond" + frame.Number + "Arm" + arm;
        }

        // Lays out the arms of a switch expression one after another: each is tested, run if it matches, and left
        // by a jump to the end.
        private bool CompletedArm(Frame parent, int index)
        {
            ExpressionSyntax governing = parent.Done[0];
            if (index == 0)
            {
                if (!StoreDecider(governing))
                {
                    return false;
                }

                returnMe.Steps.Add(SpillStep.ArmTest(governing, parent.Arms[0], ArmLabel(parent, 0)));
                return true;
            }

            int arm = index - 1;
            if (arm < parent.Arms.Count - 1)
            {
                returnMe.Steps.Add(SpillStep.Jump(EndLabel(parent)));
                returnMe.Steps.Add(SpillStep.Label(ArmLabel(parent, arm)));
                returnMe.Steps.Add(SpillStep.ArmTest(governing, parent.Arms[arm + 1], ArmLabel(parent, arm + 1)));
            }
            else
            {
                returnMe.Steps.Add(SpillStep.Label(ArmLabel(parent, arm)));
                returnMe.Steps.Add(SpillStep.Label(EndLabel(parent)));
            }

            return true;
        }

        // Adds the branch that decides, after its first operand, whether an operator's other operands run.
        private bool BranchAfterFirstOperand(Frame frame, ExpressionSyntax decider)
        {
            // The statement tests and writes the variable in place, so it is read here and not kept.
            if (!frame.Assigns && !StoreDecider(decider))
            {
                return false;
            }

            switch (frame.Node.Kind())
            {
                case SyntaxKind.LogicalAndExpression:
                    returnMe.Steps.Add(SpillStep.Branch(decider, true, NullCheck.None, EndLabel(frame)));
                    break;
                case SyntaxKind.LogicalOrExpression:
                    returnMe.Steps.Add(SpillStep.Branch(decider, false, NullCheck.None, EndLabel(frame)));
                    break;
                case SyntaxKind.CoalesceExpression:
                case SyntaxKind.CoalesceAssignmentExpression:
                    returnMe.Steps.Add(SpillStep.Branch(decider, false, NullCheck.IsNotNull, EndLabel(frame)));
                    break;
                case SyntaxKind.ConditionalExpression:
                    returnMe.Steps.Add(SpillStep.Branch(decider, true, NullCheck.None, ElseLabel(frame)));
                    break;
                default:
                    returnMe.Steps.Add(SpillStep.Branch(decider, false, NullCheck.IsNull, EndLabel(frame)));
                    break;
            }

            return true;
        }

        // Records that an operand has been evaluated, and for an operator that only sometimes runs its later operands,
        // lays out the jumps around them.
        private bool Completed(Frame parent, ExpressionSyntax operand)
        {
            parent.Done.Add(operand);
            if (!parent.Conditional)
            {
                return true;
            }

            int index = parent.Finished++;
            if (index > 0 || parent.Assigns)
            {
                // The statement runs these itself, and only on the paths that reach them.
                parent.Done.RemoveAt(parent.Done.Count - 1);
            }

            if (parent.Arms != null)
            {
                return CompletedArm(parent, index);
            }

            bool isConditionalExpression = parent.Node.IsKind(SyntaxKind.ConditionalExpression);
            if (index == 0)
            {
                return BranchAfterFirstOperand(parent, operand);
            }

            if (isConditionalExpression && index == 1)
            {
                returnMe.Steps.Add(SpillStep.Jump(EndLabel(parent)));
                returnMe.Steps.Add(SpillStep.Label(ElseLabel(parent)));
            }
            else
            {
                returnMe.Steps.Add(SpillStep.Label(EndLabel(parent)));
            }

            return true;
        }

        private bool Walk(IReadOnlyList<ExpressionSyntax> roots)
        {
            var frames = new List<Frame>();
            var start = new Frame();
            if (roots.Count == 1)
            {
                start.Node = roots[0];
                if (!Describe(start))
                {
                    return false;
                }
            }
            else
            {
                // Several expressions that one statement runs in order, such as a declaration's initializers.
                start.Operands.AddRange(roots);
            }

            if (!Begin(frames, start))
            {
                return false;
            }

            frames.Add(start);
            while (frames.Count > 0)
            {
                Frame top = frames[frames.Count - 1];
                if (top.Next < top.Operands.Count)
                {
                    ExpressionSyntax operand = top.Operands[top.Next++];
                    if (!spine.Contains(operand))
                    {
                        if (!Completed(top, operand))
                        {
                            return false;
                        }

                        continue;
                    }

                    var inner = new Frame { Node = operand };
                    if (!Describe(inner) || !Begin(frames, inner))
                    {
                        return false;
                    }

                    frames.Add(inner);
                    continue;
                }

                frames.RemoveAt(frames.Count - 1);
                var call = top.Node as InvocationExpressionSyntax;
                if (call != null && script.AnyPassageCalled(call) != null)
                {
                    if (!SpillPending(frames))
                    {
                        return false;
                    }

                    IMethodSymbol passage = script.AnyPassageCalled(call);
                    SpillTemp temp = null;
                    if (!passage.ReturnsVoid)
                    {
                        // The type as constructed at the call, since the passage's own may be a type parameter's.
                        var target = (IMethodSymbol)script.ModelFor(call).GetSymbolInfo(call).Symbol;
                        temp = NewTemp(target.ReturnType, call.GetLocation());
                        returnMe.Replacements[call] = temp;
                    }

                    returnMe.Steps.Add(SpillStep.Pause(call, temp));
                }

                if (frames.Count > 0 && !Completed(frames[frames.Count - 1], top.Node))
                {
                    return false;
                }
            }

            return true;
        }

        private static bool IsInside(SyntaxNode node, SyntaxNode ancestor)
        {
            for (SyntaxNode current = node.Parent; current != null; current = current.Parent)
            {
                if (current == ancestor)
                {
                    return true;
                }
            }

            return false;
        }

        // The operand a step evaluates, which reads each temp that stands in for something inside it.
        private static SyntaxNode RootOf(SpillStep step)
        {
            return step.Call ?? (SyntaxNode)step.Value;
        }

        // A temp needs saving at each pause that falls after the step that sets it and no later than the last step
        // that reads it.  Steps are counted in the order they run on any path, so a pause on a path the temp is never
        // set on is counted too, which only saves a value that wasn't used.  The pause's own arguments count as reads,
        // since they're worked out again each time the callee is entered.
        private void FindLiveTemps()
        {
            var lastRead = new Dictionary<SpillTemp, int>();
            foreach (KeyValuePair<SyntaxNode, SpillTemp> replacement in returnMe.Replacements)
            {
                // The statement itself reads whatever isn't hidden inside an operand that was stored whole.
                SyntaxNode nearest = null;
                for (SyntaxNode current = replacement.Key.Parent; current != null && nearest == null;
                    current = current.Parent)
                {
                    // A compound assignment's target is still reached through its parts, after the old value is kept.
                    if (returnMe.Replacements.ContainsKey(current) && !IsCompoundTarget(current))
                    {
                        nearest = current;
                    }
                }

                int last = nearest == null ? returnMe.Steps.Count : -1;
                for (int i = 0; i < returnMe.Steps.Count; ++i)
                {
                    SyntaxNode root = RootOf(returnMe.Steps[i]);
                    if (root == null)
                    {
                        continue;
                    }

                    bool reads = IsInside(replacement.Key, root)
                        && (nearest == null || nearest == root || !IsInside(nearest, root));
                    if (root == replacement.Key && (returnMe.Steps[i].Kind == SpillStepKind.Branch
                        || returnMe.Steps[i].Kind == SpillStepKind.ArmTest))
                    {
                        reads = true;
                    }

                    if (reads)
                    {
                        last = Math.Max(last, i);
                    }
                }

                lastRead[replacement.Value] = last;
            }

            for (int i = 0; i < returnMe.Steps.Count; ++i)
            {
                SpillStep step = returnMe.Steps[i];
                if (step.Kind != SpillStepKind.Pause)
                {
                    continue;
                }

                for (int earlier = 0; earlier < i; ++earlier)
                {
                    SpillTemp temp = returnMe.Steps[earlier].Temp;
                    if (temp != null && lastRead[temp] >= i)
                    {
                        step.LiveTemps.Add(temp);
                        temp.Saved = true;
                    }
                }
            }
        }

        /// <summary>
        /// Returns the steps that take the passage calls out of <paramref name="root"/>, or null if it has none or has
        /// something that can't be taken apart yet.  <paramref name="statement"/> is whatever contains the expression.
        /// </summary>
        /// <param name="firstNumber">Where the temps' numbering starts, so a passage's temps differ in name.</param>
        /// <param name="firstConditional">Where the numbering of the jump labels starts.</param>
        public static SpillSequence Spill(ScriptClass script, SemanticModel model, SyntaxNode statement,
            ExpressionSyntax root, int firstNumber, int firstConditional)
        {
            return Spill(script, model, statement, new[] { root }, firstNumber, firstConditional);
        }

        /// <summary>
        /// Returns the steps for several expressions that run one after another, in the order given.
        /// </summary>
        public static SpillSequence Spill(ScriptClass script, SemanticModel model, SyntaxNode statement,
            IReadOnlyList<ExpressionSyntax> roots, int firstNumber, int firstConditional)
        {
            var spiller = new ExpressionSpiller(script, model, firstNumber, firstConditional);
            var calls = new List<InvocationExpressionSyntax>();
            foreach (ExpressionSyntax root in roots)
            {
                calls.AddRange(root.DescendantNodesAndSelf().OfType<InvocationExpressionSyntax>()
                    .Where(invocation => script.AnyPassageCalled(invocation) != null));
            }

            if (calls.Count == 0)
            {
                return null;
            }

            foreach (InvocationExpressionSyntax call in calls)
            {
                ExpressionSyntax root = null;
                for (SyntaxNode node = call; root == null; node = node.Parent)
                {
                    root = roots.FirstOrDefault(candidate => candidate == node);
                }

                if (InFunction(call, root) || (script.AnyPassageCalled(call).ReturnsVoid && call != root))
                {
                    return null;
                }

                for (SyntaxNode node = call; ; node = node.Parent)
                {
                    spiller.spine.Add(node);
                    if (node == root)
                    {
                        break;
                    }
                }
            }

            spiller.FindAssigned(statement);
            if (!spiller.Walk(roots))
            {
                return null;
            }

            spiller.FindLiveTemps();
            return spiller.returnMe;
        }
    }
}