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>
    /// Finds which of a passage's locals and parameters are kept in fields, and which of those are saved because
    /// they're still needed after one of its pauses.
    /// </summary>
    public class PassageLocals
    {
        public const string FieldSeparator = "__";

        public readonly IMethodSymbol Passage;

        public readonly PassagePlan Plan;

        /// <summary>
        /// Holds every saved local and parameter, in the order the passage declares them.
        /// </summary>
        public readonly List<ISymbol> Saved = new List<ISymbol>();

        /// <summary>
        /// Holds every local and parameter kept in a field: the saved ones, plus locals used in more than one
        /// braced segment, which couldn't see each other otherwise.
        /// </summary>
        public readonly List<ISymbol> Hoisted = new List<ISymbol>();

        /// <summary>
        /// Holds what each pause needs saved.
        /// </summary>
        public readonly Dictionary<Pause, List<ISymbol>> NeededAt = new Dictionary<Pause, List<ISymbol>>();

        // Each local is checked once, so a local needed at several pauses is reported only once.
        private readonly Dictionary<ISymbol, bool> movable =
            new Dictionary<ISymbol, bool>(SymbolEqualityComparer.Default);

        // Two hoisted locals can share a name when they sit in sibling scopes, so the later ones are numbered.
        private readonly Dictionary<ISymbol, int> ordinals =
            new Dictionary<ISymbol, int>(SymbolEqualityComparer.Default);

        // The variables that patterns and out arguments declare, which the writer can turn into hoisted locals.
        private readonly HashSet<ISymbol> expressionVariables =
            new HashSet<ISymbol>(SymbolEqualityComparer.Default);

        private readonly List<ISymbol> topAliases = new List<ISymbol>();

        private readonly Dictionary<int, List<ISymbol>> segmentAliases = new Dictionary<int, List<ISymbol>>();

        /// <summary>
        /// Holds whether the passage keeps its locals in a frame class of its own.
        /// </summary>
        public readonly bool OwnsFrame;

        // What every saved key of the passage starts with.  An override's include its class, since a local it shares a
        // name with in the passage it overrides may be of another type, and would be read as the wrong one.
        private readonly string keyStem;

        private PassageLocals(IMethodSymbol passage, PassagePlan plan, bool ownsFrame, bool overridesPassage)
        {
            Passage = passage;
            Plan = plan;
            OwnsFrame = ownsFrame;
            keyStem = overridesPassage ? passage.ContainingType.Name + "." + passage.Name : passage.Name;
        }

        public static ITypeSymbol TypeOf(ISymbol symbol)
        {
            var local = symbol as ILocalSymbol;
            if (local != null)
            {
                return local.Type;
            }

            return ((IParameterSymbol)symbol).Type;
        }

        public bool IsSaved(ISymbol symbol)
        {
            return Saved.Contains(symbol, SymbolEqualityComparer.Default);
        }

        public bool IsHoisted(ISymbol symbol)
        {
            return Hoisted.Contains(symbol, SymbolEqualityComparer.Default);
        }

        /// <summary>
        /// Gets the hoisted symbols whose ref aliases go at the top of the passage: parameters, and locals declared
        /// directly in its body.
        /// </summary>
        public IReadOnlyList<ISymbol> TopAliases
        {
            get
            {
                return topAliases;
            }
        }

        /// <summary>
        /// Returns the hoisted locals a braced segment uses, whose ref aliases go at the top of that segment.
        /// </summary>
        public IReadOnlyList<ISymbol> AliasesIn(int segment)
        {
            List<ISymbol> returnMe;
            if (segmentAliases.TryGetValue(segment, out returnMe))
            {
                return returnMe;
            }

            return new ISymbol[0];
        }

        private int OrdinalOf(ISymbol symbol)
        {
            int returnMe;
            ordinals.TryGetValue(symbol, out returnMe);
            return returnMe;
        }

        public string FieldName(ISymbol symbol)
        {
            string returnMe = Passage.Name + FieldSeparator + symbol.Name;
            int ordinal = OrdinalOf(symbol);
            if (ordinal > 0)
            {
                returnMe += FieldSeparator + ordinal;
            }

            return returnMe;
        }

        public string FieldName(SpillTemp temp)
        {
            return Passage.Name + FieldSeparator + temp.Name;
        }

        /// <summary>
        /// Returns the expression a passage copy reads and writes <paramref name="symbol"/>'s field through.
        /// </summary>
        public string Access(ISymbol symbol)
        {
            return PassageWriter.FrameName + "." + FieldName(symbol);
        }

        public string Access(SpillTemp temp)
        {
            return PassageWriter.FrameName + "." + FieldName(temp);
        }

        public string Key(SpillTemp temp)
        {
            return keyStem + "." + temp.Name;
        }

        /// <summary>
        /// Gets whether any value held in a spill temp has to be saved.
        /// </summary>
        public bool HasSavedTemps
        {
            get
            {
                return Plan.Temps.Any(temp => temp.Saved);
            }
        }

        public string Key(ISymbol symbol)
        {
            string returnMe = keyStem + "." + symbol.Name;
            int ordinal = OrdinalOf(symbol);
            if (ordinal > 0)
            {
                returnMe += "#" + ordinal;
            }

            return returnMe;
        }

        // Hoisting rewrites a declaration into an assignment, which only works for one written as a statement of its
        // own in a block.
        private static bool IsPlainDeclaration(ISymbol symbol)
        {
            var parameter = symbol as IParameterSymbol;
            if (parameter != null)
            {
                return parameter.RefKind != RefKind.Ref && parameter.RefKind != RefKind.RefReadOnlyParameter;
            }

            var local = (ILocalSymbol)symbol;
            var declarator = local.DeclaringSyntaxReferences.FirstOrDefault()?.GetSyntax() as VariableDeclaratorSyntax;
            if (declarator?.Parent?.Parent is ForStatementSyntax)
            {
                return !local.IsRef && !local.IsConst;
            }

            var statement = declarator?.Parent?.Parent as LocalDeclarationStatementSyntax;
            SyntaxNode container = statement?.Parent;
            while (container is LabeledStatementSyntax)
            {
                container = container.Parent;
            }

            return statement != null
                && (container is BlockSyntax || container is SwitchSectionSyntax)
                && !local.IsRef
                && !local.IsConst
                && statement.UsingKeyword.IsKind(SyntaxKind.None);
        }

        // Returns why a field can't have this type, or null if it can.  Walks the type arguments and array elements
        // without recursing, since the type may be arbitrarily nested.
        private static string WhyNotAFieldType(ITypeSymbol type)
        {
            var pending = new Stack<ITypeSymbol>();
            pending.Push(type);
            while (pending.Count > 0)
            {
                ITypeSymbol next = pending.Pop();
                if (next.IsAnonymousType)
                {
                    return "an anonymous type has no name to declare the field with.  Write a class or struct for " +
                        "it, or use a tuple.";
                }

                if (next.IsRefLikeType)
                {
                    return "a ref struct can't be the type of a field in a class.";
                }

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

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

            return null;
        }

        private bool CanMove(ISymbol symbol, List<Diagnostic> diagnostics)
        {
            bool returnMe;
            if (movable.TryGetValue(symbol, out returnMe))
            {
                return returnMe;
            }

            returnMe = IsPlainDeclaration(symbol) || expressionVariables.Contains(symbol);
            if (!returnMe)
            {
                diagnostics.Add(Diagnostic.Create(ScriptDiagnostics.UnsupportedLocal, symbol.Locations.FirstOrDefault(),
                    symbol.Name));
            }
            else
            {
                string whyNot = WhyNotAFieldType(TypeOf(symbol));
                if (whyNot != null)
                {
                    diagnostics.Add(Diagnostic.Create(ScriptDiagnostics.UnsavableLocalType,
                        symbol.Locations.FirstOrDefault(), symbol.Name, whyNot));
                    returnMe = false;
                }
            }

            movable.Add(symbol, returnMe);
            return returnMe;
        }

        // Each tick hands the script its context afresh, so a parameter carrying it is passed, never saved.  A ref
        // or ref readonly parameter is passed afresh too, and the variable it refers to is the caller's to save.
        private static bool IsCandidate(ISymbol symbol, ScriptClass script)
        {
            var parameter = symbol as IParameterSymbol;
            if (parameter != null)
            {
                return !parameter.IsThis
                    && parameter.RefKind != RefKind.Ref
                    && parameter.RefKind != RefKind.RefReadOnlyParameter
                    && !SymbolEqualityComparer.Default.Equals(parameter.Type, script.ContextType);
            }

            var local = symbol as ILocalSymbol;
            return local != null && !local.IsConst;
        }

        private static int DeclarationOrder(ISymbol symbol)
        {
            return symbol.Locations.First().SourceSpan.Start;
        }

        /// <summary>
        /// Holds one piece of code a resumed pause goes on to run: a run of statements, or an expression.
        /// </summary>
        private class Region
        {
            public readonly StatementSyntax First;
            public readonly StatementSyntax Last;
            public readonly ExpressionSyntax Expression;

            public Region(StatementSyntax first, StatementSyntax last)
            {
                First = first;
                Last = last;
            }

            public Region(ExpressionSyntax expression)
            {
                Expression = expression;
            }

            public DataFlowAnalysis Analyze(SemanticModel model)
            {
                if (Expression != null)
                {
                    return model.AnalyzeDataFlow(Expression);
                }

                if (First == Last)
                {
                    return model.AnalyzeDataFlow(First);
                }

                return model.AnalyzeDataFlow(First, Last);
            }
        }

        // The next trip around a loop runs its condition, body and step, but not its initializer, which would hide a
        // variable that a resume in the middle of the loop still needs.
        private static List<Region> NextTripOf(StatementSyntax loop)
        {
            var returnMe = new List<Region>();
            var whileLoop = loop as WhileStatementSyntax;
            if (whileLoop != null)
            {
                returnMe.Add(new Region(whileLoop.Condition));
                returnMe.Add(new Region(whileLoop.Statement, whileLoop.Statement));
                return returnMe;
            }

            var doLoop = loop as DoStatementSyntax;
            if (doLoop != null)
            {
                returnMe.Add(new Region(doLoop.Statement, doLoop.Statement));
                returnMe.Add(new Region(doLoop.Condition));
                return returnMe;
            }

            var forLoop = (ForStatementSyntax)loop;
            if (forLoop.Condition != null)
            {
                returnMe.Add(new Region(forLoop.Condition));
            }

            returnMe.Add(new Region(forLoop.Statement, forLoop.Statement));
            foreach (ExpressionSyntax incrementor in forLoop.Incrementors)
            {
                returnMe.Add(new Region(incrementor));
            }

            return returnMe;
        }

        private static List<Region> Run(StatementSyntax first, StatementSyntax last)
        {
            return new List<Region> { new Region(first, last) };
        }

        // What a resumed pause goes on to run, in order: the rest of the block holding it, then the rest of each block
        // holding that, up to the body.  An if's other branch never runs after the branch resumed in.  Leaving a loop's
        // body goes round the loop again, which is one piece of its own.
        private static List<List<Region>> ContinuationOf(StatementSyntax pause, BlockSyntax body, bool includePause)
        {
            var returnMe = new List<List<Region>>();
            StatementSyntax current = pause;
            bool includeCurrent = includePause;
            while (true)
            {
                SyntaxNode parent = current.Parent;
                var block = parent as BlockSyntax;
                if (block != null)
                {
                    int index = block.Statements.IndexOf(current);
                    int first = includeCurrent ? index : index + 1;
                    if (first < block.Statements.Count)
                    {
                        returnMe.Add(Run(block.Statements[first], block.Statements.Last()));
                    }

                    if (block == body)
                    {
                        return returnMe;
                    }

                    current = block;
                    includeCurrent = false;
                }
                else if (parent is LabeledStatementSyntax)
                {
                    current = (StatementSyntax)parent;
                }
                else if (parent is SwitchSectionSyntax)
                {
                    // A section runs on to the code after its switch.
                    var section = (SwitchSectionSyntax)parent;
                    int index = section.Statements.IndexOf(current);
                    int first = includeCurrent ? index : index + 1;
                    if (first < section.Statements.Count)
                    {
                        returnMe.Add(Run(section.Statements[first], section.Statements.Last()));
                    }

                    current = (StatementSyntax)section.Parent;
                    includeCurrent = false;
                }
                else if (parent is WhileStatementSyntax
                    || parent is DoStatementSyntax
                    || parent is ForStatementSyntax)
                {
                    // The body of a loop, which is a lone statement when it has no braces.
                    if (includeCurrent)
                    {
                        returnMe.Add(Run(current, current));
                    }

                    returnMe.Add(NextTripOf((StatementSyntax)parent));
                    current = (StatementSyntax)parent;
                    includeCurrent = false;
                }
                else
                {
                    // An embedded statement, as in "if (x) Yield();".
                    if (includeCurrent)
                    {
                        returnMe.Add(Run(current, current));
                    }

                    current = parent as IfStatementSyntax ?? (StatementSyntax)parent.Parent;
                    includeCurrent = false;
                }
            }
        }

        // The variable a statement sets once its pause is over, which nothing from before the pause can be needed for.
        private static ISymbol AssignedByStatement(StatementSyntax statement, SemanticModel model)
        {
            var declaration = statement as LocalDeclarationStatementSyntax;
            if (declaration != null)
            {
                return model.GetDeclaredSymbol(declaration.Declaration.Variables[0]);
            }

            var assignment = (statement as ExpressionStatementSyntax)?.Expression as AssignmentExpressionSyntax;
            if (assignment != null
                && !assignment.IsKind(SyntaxKind.CoalesceAssignmentExpression)
                && ScriptClass.IsPlainTarget(assignment.Left))
            {
                return model.GetSymbolInfo(assignment.Left).Symbol;
            }

            return null;
        }

        // A pause inside a statement resumes partway through it, so only the code still to run in the statement
        // counts.  The locals it declares itself aren't needed from before, and operands already stored are not read
        // again.
        private static IEnumerable<ISymbol> LocalsReadAfter(Pause pause, SemanticModel model)
        {
            foreach (SyntaxNode node in pause.Reads)
            {
                foreach (IdentifierNameSyntax name in node.DescendantNodesAndSelf().OfType<IdentifierNameSyntax>())
                {
                    ISymbol symbol = model.GetSymbolInfo(name).Symbol;
                    if ((symbol is ILocalSymbol || symbol is IParameterSymbol)
                        && !IsReplaced(name, node, pause.Replacements)
                        && !symbol.Locations.Any(location => pause.Outer.Span.Contains(location.SourceSpan)))
                    {
                        yield return symbol;
                    }
                }
            }
        }

        // What an if, loop or switch runs after its header: its branches, or its body and the next trip around.
        private static List<Region> OwnerRegions(StatementSyntax owner)
        {
            var ifStatement = owner as IfStatementSyntax;
            if (ifStatement != null)
            {
                var branches = new List<Region> { new Region(ifStatement.Statement, ifStatement.Statement) };
                if (ifStatement.Else != null)
                {
                    branches.Add(new Region(ifStatement.Else.Statement, ifStatement.Else.Statement));
                }

                return branches;
            }

            var switchStatement = owner as SwitchStatementSyntax;
            if (switchStatement != null)
            {
                var sections = new List<Region>();
                foreach (SwitchSectionSyntax section in switchStatement.Sections)
                {
                    foreach (SwitchLabelSyntax label in section.Labels)
                    {
                        var pattern = label as CasePatternSwitchLabelSyntax;
                        if (pattern?.WhenClause != null)
                        {
                            sections.Add(new Region(pattern.WhenClause.Condition));
                        }
                    }

                    sections.Add(new Region(section.Statements[0], section.Statements.Last()));
                }

                return sections;
            }

            return NextTripOf(owner);
        }

        // Throws if the compiler can't analyze the code after the pause.  No input is known to do that.  Skipping the
        // pause would leave its locals unsaved and fail much later, so this is a tripwire.
        private List<ISymbol> NeededAfter(Pause pause, BlockSyntax body, SemanticModel model, ScriptClass script,
            List<Diagnostic> diagnostics)
        {
            var needed = new HashSet<ISymbol>(SymbolEqualityComparer.Default);
            var assigned = new HashSet<ISymbol>(SymbolEqualityComparer.Default);
            var pieces = new List<List<Region>>();
            if (pause.Owner != null)
            {
                // The header goes on to its body, which a loop then goes round again.
                needed.UnionWith(LocalsReadAfter(pause, model));
                pieces.Add(OwnerRegions(pause.Owner));
                pieces.AddRange(ContinuationOf(pause.Owner, body, includePause: false));
            }
            else
            {
                if (pause.Call != null)
                {
                    needed.UnionWith(LocalsReadAfter(pause, model));
                    ISymbol assignedLater = AssignedByStatement(pause.Statement, model);
                    if (assignedLater != null)
                    {
                        needed.Remove(assignedLater);
                        assigned.Add(assignedLater);
                    }
                }
                else if (pause.Kind == PauseKind.Trigger)
                {
                    // The arguments were read before the pause, and the result is set once it is over.
                    ISymbol assignedLater = AssignedByStatement(pause.Statement, model);
                    if (assignedLater != null)
                    {
                        assigned.Add(assignedLater);
                    }
                }

                pieces.AddRange(ContinuationOf(pause.Outer, body,
                    includePause: pause.Call == null
                        && pause.Kind != PauseKind.Wait
                        && pause.Kind != PauseKind.Trigger));
            }

            foreach (List<Region> piece in pieces)
            {
                foreach (Region region in piece)
                {
                    DataFlowAnalysis flow = region.Analyze(model);
                    if (!flow.Succeeded)
                    {
                        throw new InvalidOperationException("Data flow analysis failed for the code after the pause '" +
                            pause.Key + "' at " + pause.Statement.GetLocation().GetLineSpan() + ".");
                    }

                    // A later piece reads what an earlier one always writes, so that value is never from the save.
                    foreach (ISymbol symbol in flow.DataFlowsIn)
                    {
                        if (!assigned.Contains(symbol))
                        {
                            needed.Add(symbol);
                        }
                    }

                    // A loop might not run, so only a lone run of statements is sure to assign.
                    if (piece.Count == 1)
                    {
                        assigned.UnionWith(flow.AlwaysAssigned);
                    }
                }
            }

            return needed.Where(symbol => IsCandidate(symbol, script) && CanMove(symbol, diagnostics))
                .OrderBy(DeclarationOrder).ToList();
        }

        private static IEnumerable<SyntaxNode> UsesIn(PlanPart part)
        {
            if (part.Kind == PartKind.Branch)
            {
                yield return part.Condition;
            }
            else if (part.Kind == PartKind.Store || part.Kind == PartKind.Evaluate)
            {
                yield return part.Value;
            }
            else if (part.Kind == PartKind.Deadline || part.Kind == PartKind.TriggerBegin)
            {
                yield return part.Condition;
            }
            else if (part.Kind == PartKind.ArmTest)
            {
                yield return part.Condition;
                yield return part.Arm.Pattern;
                if (part.Arm.WhenClause != null)
                {
                    yield return part.Arm.WhenClause.Condition;
                }
            }
            else if (part.Kind == PartKind.Pause && part.Pause.Call != null)
            {
                yield return part.Pause.Call;
            }
            else if (part.Kind == PartKind.Copy || part.Kind == PartKind.Pause)
            {
                yield return part.Statement;
            }
            else if (part.Kind == PartKind.ForInit)
            {
                var forLoop = (ForStatementSyntax)part.Statement;
                if (forLoop.Declaration != null)
                {
                    yield return forLoop.Declaration;
                }

                foreach (ExpressionSyntax initializer in forLoop.Initializers)
                {
                    yield return initializer;
                }
            }
            else if (part.Kind == PartKind.Dispatch)
            {
                var dispatching = (SwitchStatementSyntax)part.Statement;
                yield return dispatching.Expression;
                foreach (SwitchSectionSyntax section in dispatching.Sections)
                {
                    foreach (SwitchLabelSyntax label in section.Labels)
                    {
                        yield return label;
                    }
                }
            }
            else if (part.Kind == PartKind.ForStep)
            {
                foreach (ExpressionSyntax incrementor in ((ForStatementSyntax)part.Statement).Incrementors)
                {
                    yield return incrementor;
                }
            }
        }

        private static VariableDeclarationSyntax DeclarationOf(PlanPart part)
        {
            if (part.Kind == PartKind.Copy || part.Kind == PartKind.Pause)
            {
                return (part.Statement as LocalDeclarationStatementSyntax)?.Declaration;
            }

            if (part.Kind == PartKind.ForInit)
            {
                return ((ForStatementSyntax)part.Statement).Declaration;
            }

            return null;
        }

        /// <summary>
        /// Holds where each local appears among the braced segments and the parts, for the locals declared in a segment.
        /// </summary>
        private class LocalUses
        {
            public readonly Dictionary<ISymbol, HashSet<int>> Segments =
                new Dictionary<ISymbol, HashSet<int>>(SymbolEqualityComparer.Default);

            public readonly Dictionary<ISymbol, HashSet<PlanPart>> Parts =
                new Dictionary<ISymbol, HashSet<PlanPart>>(SymbolEqualityComparer.Default);

            public readonly List<ISymbol> DeclaredInSegments = new List<ISymbol>();

            /// <summary>
            /// Holds the variables declared in a condition that became a jump, which C# scopes to the statement.
            /// </summary>
            public readonly HashSet<ISymbol> ConditionOwned = new HashSet<ISymbol>(SymbolEqualityComparer.Default);

            /// <summary>
            /// Holds the variables a switch expression arm's test or a passage call's out argument declares.  The
            /// statement that holds them may sit outside any segment, which couldn't see a variable declared in a
            /// segment of its own.
            /// </summary>
            public readonly HashSet<ISymbol> ArmDeclared = new HashSet<ISymbol>(SymbolEqualityComparer.Default);

            public void Note(ISymbol symbol, PlanPart part)
            {
                HashSet<int> segments;
                if (!Segments.TryGetValue(symbol, out segments))
                {
                    segments = new HashSet<int>();
                    Segments.Add(symbol, segments);
                }

                segments.Add(part.Segment);

                HashSet<PlanPart> parts;
                if (!Parts.TryGetValue(symbol, out parts))
                {
                    parts = new HashSet<PlanPart>();
                    Parts.Add(symbol, parts);
                }

                parts.Add(part);
            }
        }

        // A designation that the part itself scopes: C# lets one in a statement's header reach the rest of its block,
        // but not one inside a nested statement.
        private static IEnumerable<SingleVariableDesignationSyntax> DesignationsOf(PlanPart part)
        {
            foreach (SyntaxNode use in UsesIn(part))
            {
                foreach (SingleVariableDesignationSyntax designation in
                    use.DescendantNodesAndSelf().OfType<SingleVariableDesignationSyntax>())
                {
                    if (part.Kind != PartKind.Copy
                        || designation.FirstAncestorOrSelf<StatementSyntax>() == part.Statement)
                    {
                        yield return designation;
                    }
                }
            }
        }

        // An operand that is read from a temp isn't a use of the locals inside it.
        private static bool IsReplaced(SyntaxNode name, SyntaxNode use,
            IReadOnlyDictionary<SyntaxNode, SpillTemp> replacements)
        {
            if (replacements == null)
            {
                return false;
            }

            for (SyntaxNode ancestor = name; ancestor != null && ancestor != use; ancestor = ancestor.Parent)
            {
                if (replacements.ContainsKey(ancestor) && !ExpressionSpiller.IsCompoundTarget(ancestor))
                {
                    return true;
                }
            }

            return false;
        }

        private LocalUses UsesOfScopedLocals(ScriptClass script)
        {
            var returnMe = new LocalUses();
            foreach (Pause pause in Plan.Pauses)
            {
                InvocationExpressionSyntax call = pause.Call ?? script.AsPassageCall(pause.Statement)?.Invocation;
                if (call == null)
                {
                    continue;
                }

                SemanticModel callModel = script.ModelFor(call);
                foreach (SingleVariableDesignationSyntax designation in
                    call.ArgumentList.DescendantNodes().OfType<SingleVariableDesignationSyntax>())
                {
                    ISymbol declared = callModel.GetDeclaredSymbol(designation);
                    if (declared != null && expressionVariables.Contains(declared))
                    {
                        returnMe.ArmDeclared.Add(declared);
                    }
                }
            }

            foreach (PlanPart part in Plan.Parts)
            {
                if (part.Segment < 0)
                {
                    continue;
                }

                SemanticModel model = script.ModelFor(part.Anchor.SourceTree.GetRoot());
                foreach (SyntaxNode use in UsesIn(part))
                {
                    // A test of an operand that was stored whole reads its temp, not the locals inside it.
                    if (part.Kind == PartKind.Branch
                        && part.Replacements != null
                        && part.Replacements.ContainsKey(use))
                    {
                        continue;
                    }

                    foreach (IdentifierNameSyntax name in use.DescendantNodesAndSelf().OfType<IdentifierNameSyntax>())
                    {
                        var local = model.GetSymbolInfo(name).Symbol as ILocalSymbol;
                        if (local != null && !IsReplaced(name, use, part.Replacements))
                        {
                            returnMe.Note(local, part);
                        }
                    }
                }

                VariableDeclarationSyntax declaration = DeclarationOf(part);
                if (declaration != null)
                {
                    foreach (VariableDeclaratorSyntax declarator in declaration.Variables)
                    {
                        ISymbol declared = model.GetDeclaredSymbol(declarator);
                        returnMe.Note(declared, part);
                        returnMe.DeclaredInSegments.Add(declared);
                    }
                }

                if (part.Kind != PartKind.Copy
                    && part.Kind != PartKind.Branch
                    && part.Kind != PartKind.Dispatch
                    && part.Kind != PartKind.ArmTest)
                {
                    continue;
                }

                foreach (SingleVariableDesignationSyntax designation in DesignationsOf(part))
                {
                    ISymbol declared = model.GetDeclaredSymbol(designation);
                    if (declared == null || !expressionVariables.Contains(declared))
                    {
                        continue;
                    }

                    if (part.Kind == PartKind.ArmTest)
                    {
                        returnMe.ArmDeclared.Add(declared);
                    }

                    if (returnMe.ArmDeclared.Contains(declared))
                    {
                        continue;
                    }

                    returnMe.Note(declared, part);
                    returnMe.DeclaredInSegments.Add(declared);
                    if (part.Kind != PartKind.Copy)
                    {
                        returnMe.ConditionOwned.Add(declared);
                    }
                }
            }

            return returnMe;
        }

        // A lambda, local function or query scopes its own variables, and a pause loop's condition has no
        // segment of its own to give an alias to.
        private void FindExpressionVariables(ScriptClass script, BlockSyntax body)
        {
            SemanticModel model = script.ModelFor(body);
            var pauseLoops = new HashSet<SyntaxNode>(
                Plan.Pauses.Where(pause => pause.Kind == PauseKind.YieldLoop).Select(pause => pause.Statement));
            foreach (SingleVariableDesignationSyntax designation in
                body.DescendantNodes().OfType<SingleVariableDesignationSyntax>())
            {
                bool rewritable = !pauseLoops.Contains(designation.FirstAncestorOrSelf<StatementSyntax>());
                for (SyntaxNode ancestor = designation.Parent; ancestor != body && rewritable;
                    ancestor = ancestor.Parent)
                {
                    rewritable = !(ancestor is AnonymousFunctionExpressionSyntax)
                        && !(ancestor is LocalFunctionStatementSyntax)
                        && !(ancestor is QueryExpressionSyntax);
                }

                var local = model.GetDeclaredSymbol(designation) as ILocalSymbol;
                if (rewritable && local != null)
                {
                    expressionVariables.Add(local);
                }
            }
        }

        private void Hoist(HashSet<ISymbol> saved, LocalUses uses, List<Diagnostic> diagnostics)
        {
            var hoisted = new HashSet<ISymbol>(saved, SymbolEqualityComparer.Default);
            foreach (ISymbol local in uses.DeclaredInSegments)
            {
                // A condition that became a jump no longer scopes its variables over the code it guards, so any use
                // outside the condition needs the hoisted copy, even in the same segment.
                bool crosses = uses.Segments[local].Count > 1
                    || (uses.ConditionOwned.Contains(local) && uses.Parts[local].Count > 1);
                if (crosses && !saved.Contains(local) && CanMove(local, diagnostics))
                {
                    hoisted.Add(local);
                }
            }

            foreach (ISymbol local in uses.ArmDeclared)
            {
                if (CanMove(local, diagnostics))
                {
                    hoisted.Add(local);
                }
            }

            // An out parameter is the passage's own variable until the passage ends, so it lives in a field.
            foreach (IParameterSymbol parameter in Passage.Parameters.Where(each => each.RefKind == RefKind.Out))
            {
                hoisted.Add(parameter);
            }

            Saved.AddRange(saved.OrderBy(DeclarationOrder));
            Hoisted.AddRange(hoisted.OrderBy(DeclarationOrder));
            foreach (IGrouping<string, ISymbol> sameName in Hoisted.GroupBy(symbol => symbol.Name))
            {
                int ordinal = 0;
                foreach (ISymbol symbol in sameName)
                {
                    ordinals[symbol] = ordinal++;
                }
            }

            var inSegments = new HashSet<ISymbol>(uses.DeclaredInSegments, SymbolEqualityComparer.Default);
            foreach (ISymbol symbol in Hoisted)
            {
                if (!inSegments.Contains(symbol))
                {
                    topAliases.Add(symbol);
                    continue;
                }

                foreach (int segment in uses.Segments[symbol].OrderBy(segment => segment))
                {
                    List<ISymbol> aliases;
                    if (!segmentAliases.TryGetValue(segment, out aliases))
                    {
                        aliases = new List<ISymbol>();
                        segmentAliases.Add(segment, aliases);
                    }

                    aliases.Add(symbol);
                }
            }
        }

        public static PassageLocals Find(ScriptClass script, IMethodSymbol passage, List<Diagnostic> diagnostics)
        {
            var returnMe = new PassageLocals(passage, PassagePlan.Build(script, passage, diagnostics),
                script.OwnsFrame(passage), overridesPassage: script.IsVirtualPassage(passage) && passage.IsOverride);
            BlockSyntax body = script.Methods[passage].Body;
            if (body == null)
            {
                return returnMe;
            }

            SemanticModel model = script.ModelFor(body);
            returnMe.FindExpressionVariables(script, body);
            var saved = new HashSet<ISymbol>(SymbolEqualityComparer.Default);
            foreach (Pause pause in returnMe.Plan.Pauses)
            {
                List<ISymbol> needed = returnMe.NeededAfter(pause, body, model, script, diagnostics);
                returnMe.NeededAt[pause] = needed;
                saved.UnionWith(needed);
            }

            returnMe.Hoist(saved, returnMe.UsesOfScopedLocals(script), diagnostics);
            return returnMe;
        }
    }
}