MegaBites-AI/Windows-powershell
0308
1// Copyright (c) Microsoft Corporation.2// Licensed under the MIT License.3 4using System.Collections;5using System.Collections.Concurrent;6using System.Collections.Generic;7using System.Collections.ObjectModel;8using System.Linq;9 10namespace System.Management.Automation.Language11{12 internal static class VariablePathExtensions13 {14 internal static bool IsAnyLocal(this VariablePath variablePath)15 {16 return variablePath.IsUnscopedVariable || variablePath.IsLocal || variablePath.IsPrivate;17 }18 }19 20 internal class VariableAnalysisDetails21 {22 internal VariableAnalysisDetails()23 {24 this.AssociatedAsts = new List<Ast>();25 }26 27 public int BitIndex { get; set; }28 29 public int LocalTupleIndex { get; set; }30 31 public Type Type { get; set; }32 33 public string Name { get; set; }34 35 public bool Automatic { get; set; }36 37 public bool PreferenceVariable { get; set; }38 39 public bool Assigned { get; set; }40 41 public List<Ast> AssociatedAsts { get; }42 }43 44 internal sealed class FindAllVariablesVisitor : AstVisitor45 {46 private static readonly HashSet<string> s_hashOfPessimizingCmdlets = new HashSet<string>(StringComparer.OrdinalIgnoreCase);47 48 private static readonly string[] s_pessimizingCmdlets = new string[]49 {50 "New-Variable",51 "Remove-Variable",52 "Set-Variable",53 "Set-PSBreakpoint",54 "Microsoft.PowerShell.Utility\\New-Variable",55 "Microsoft.PowerShell.Utility\\Remove-Variable",56 "Microsoft.PowerShell.Utility\\Set-Variable",57 "Microsoft.PowerShell.Utility\\Set-PSBreakpoint",58 "nv",59 "rv",60 "sbp",61 "sv",62 "set",63 };64 65 static FindAllVariablesVisitor()66 {67 foreach (var cmdlet in s_pessimizingCmdlets)68 {69 s_hashOfPessimizingCmdlets.Add(cmdlet);70 }71 }72 73 internal static Dictionary<string, VariableAnalysisDetails> Visit(TrapStatementAst trap)74 {75 // We disable optimizations for trap because it simplifies what we need to do when invoking76 // the trap, and it's assumed that the code inside a trap rarely, if ever, actually creates77 // any local variables.78 var visitor = new FindAllVariablesVisitor(disableOptimizations: true, scriptCmdlet: false);79 trap.Body.InternalVisit(visitor);80 return visitor._variables;81 }82 83 // Used to analyze an expression that is invoked separately, i.e. a default argument.84 internal static Dictionary<string, VariableAnalysisDetails> Visit(ExpressionAst exprAst)85 {86 // We disable optimizations for default expressions because it simplifies what we need to do when87 // invoking the default expression, and it's assumed that the code inside a trap rarely, if ever,88 // actually creates any local variables.89 var visitor = new FindAllVariablesVisitor(disableOptimizations: true, scriptCmdlet: false);90 exprAst.InternalVisit(visitor);91 return visitor._variables;92 }93 94 internal static Dictionary<string, VariableAnalysisDetails> Visit(IParameterMetadataProvider ast,95 bool disableOptimizations,96 bool scriptCmdlet,97 out int localsAllocated,98 out bool forceNoOptimizing)99 {100 var visitor = new FindAllVariablesVisitor(disableOptimizations, scriptCmdlet);101 102 // Visit the body before the parameters so we don't allocate any tuple slots for parameters103 // if we won't be optimizing because of a call to new-variable/remove-variable, etc.104 105 ast.Body.InternalVisit(visitor);106 forceNoOptimizing = visitor._disableOptimizations;107 108 if (ast.Parameters != null)109 {110 visitor.VisitParameters(ast.Parameters);111 }112 113 localsAllocated = visitor._variables.Count(static details => details.Value.LocalTupleIndex != VariableAnalysis.Unanalyzed);114 return visitor._variables;115 }116 117 private bool _disableOptimizations;118 119 private readonly Dictionary<string, VariableAnalysisDetails> _variables120 = new Dictionary<string, VariableAnalysisDetails>(StringComparer.OrdinalIgnoreCase);121 122 private FindAllVariablesVisitor(bool disableOptimizations, bool scriptCmdlet)123 {124 _disableOptimizations = disableOptimizations;125 126 var automaticVariables = SpecialVariables.AutomaticVariables;127 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.Underbar) == (int)AutomaticVariable.Underbar,128 "automaticVariables order is incorrect (0)");129 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.Args) == (int)AutomaticVariable.Args,130 "automaticVariables order is incorrect (1)");131 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.This) == (int)AutomaticVariable.This,132 "automaticVariables order is incorrect (2)");133 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.Input) == (int)AutomaticVariable.Input,134 "automaticVariables order is incorrect (3)");135 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.PSCmdlet) == (int)AutomaticVariable.PSCmdlet,136 "automaticVariables order is incorrect (4)");137 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.PSBoundParameters) == (int)AutomaticVariable.PSBoundParameters,138 "automaticVariables order is incorrect (5)");139 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.MyInvocation) == (int)AutomaticVariable.MyInvocation,140 "automaticVariables order is incorrect (6)");141 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.PSScriptRoot) == (int)AutomaticVariable.PSScriptRoot,142 "automaticVariables order is incorrect (7)");143 Diagnostics.Assert(Array.IndexOf(automaticVariables, SpecialVariables.PSCommandPath) == (int)AutomaticVariable.PSCommandPath,144 "automaticVariables order is incorrect (8)");145 146 int i;147 for (i = 0; i < automaticVariables.Length; ++i)148 {149 NoteVariable(automaticVariables[i], i, SpecialVariables.AutomaticVariableTypes[i], automatic: true);150 }151 152 if (scriptCmdlet)153 {154 var preferenceVariables = SpecialVariables.PreferenceVariables;155 for (i = 0; i < preferenceVariables.Length; ++i)156 {157 NoteVariable(preferenceVariables[i], i + (int)AutomaticVariable.NumberOfAutomaticVariables,158 SpecialVariables.PreferenceVariableTypes[i], preferenceVariable: true);159 }160 }161 162 NoteVariable(SpecialVariables.Question, VariableAnalysis.Unanalyzed, typeof(bool), automatic: true);163 }164 165 private void VisitParameters(ReadOnlyCollection<ParameterAst> parameters)166 {167 foreach (ParameterAst t in parameters)168 {169 var variableExpressionAst = t.Name;170 var varPath = variableExpressionAst.VariablePath;171 172 if (varPath.IsAnyLocal())173 {174 var variableName = VariableAnalysis.GetUnaliasedVariableName(varPath);175 VariableAnalysisDetails analysisDetails;176 if (_variables.TryGetValue(variableName, out analysisDetails))177 {178 // Forget whatever type we deduced in the body, we'll revisit that type after walking179 // the flow graph. We should see the parameter type for the variable first.180 analysisDetails.Type = t.StaticType;181 182 // If the parameter has no default value, we can't allocate a strongly typed183 // slot in the tuple. This only matters for value types where we allow184 // comparisons with $null and don't try to convert the $null value to the185 // valuetype because the parameter has no value yet. For example:186 // & { param([System.Reflection.MemberTypes]$m) ($null -eq $m) }187 188 if (!Compiler.TryGetDefaultParameterValue(analysisDetails.Type, out _))189 {190 analysisDetails.LocalTupleIndex = VariableAnalysis.ForceDynamic;191 }192 }193 else194 {195 NoteVariable(variableName, VariableAnalysis.Unanalyzed, t.StaticType);196 }197 }198 }199 }200 201 // Add a variable to the variable dictionary202 private void NoteVariable(string variableName, int index, Type type, bool automatic = false, bool preferenceVariable = false)203 {204 if (!_variables.ContainsKey(variableName))205 {206 var details = new VariableAnalysisDetails207 {208 BitIndex = _variables.Count,209 LocalTupleIndex = index,210 Name = variableName,211 Type = type,212 Automatic = automatic,213 PreferenceVariable = preferenceVariable,214 Assigned = false,215 };216 _variables.Add(variableName, details);217 }218 }219 220 public override AstVisitAction VisitDataStatement(DataStatementAst dataStatementAst)221 {222 if (dataStatementAst.Variable != null)223 {224 NoteVariable(dataStatementAst.Variable, VariableAnalysis.Unanalyzed, null);225 }226 227 return AstVisitAction.Continue;228 }229 230 public override AstVisitAction VisitSwitchStatement(SwitchStatementAst switchStatementAst)231 {232 NoteVariable(SpecialVariables.@switch, VariableAnalysis.Unanalyzed, typeof(IEnumerator));233 234 return AstVisitAction.Continue;235 }236 237 public override AstVisitAction VisitForEachStatement(ForEachStatementAst forEachStatementAst)238 {239 NoteVariable(SpecialVariables.@foreach, VariableAnalysis.Unanalyzed, typeof(IEnumerator));240 241 return AstVisitAction.Continue;242 }243 244 public override AstVisitAction VisitVariableExpression(VariableExpressionAst variableExpressionAst)245 {246 var varPath = variableExpressionAst.VariablePath;247 if (varPath.IsAnyLocal())248 {249 if (varPath.IsPrivate)250 {251 // TODO: force just this variable to be dynamic, not all variables.252 _disableOptimizations = true;253 }254 255 NoteVariable(VariableAnalysis.GetUnaliasedVariableName(varPath), VariableAnalysis.Unanalyzed, null);256 }257 258 return AstVisitAction.Continue;259 }260 261 private int _runtimeUsingIndex;262 263 public override AstVisitAction VisitUsingExpression(UsingExpressionAst usingExpressionAst)264 {265 // On the local machine, we may have set the index because of a call to ScriptBlockToPowerShell or Invoke-Command.266 // On the remote machine, the index probably isn't set yet, so we set it here, mostly to avoid another pass267 // over the ast. We assert below to ensure we're setting to the same value in both the local and remote cases.268 if (usingExpressionAst.RuntimeUsingIndex == -1)269 {270 usingExpressionAst.RuntimeUsingIndex = _runtimeUsingIndex;271 }272 273 Diagnostics.Assert(usingExpressionAst.RuntimeUsingIndex == _runtimeUsingIndex, "Logic error in visiting using expressions.");274 _runtimeUsingIndex += 1;275 276 return AstVisitAction.Continue;277 }278 279 public override AstVisitAction VisitCommand(CommandAst commandAst)280 {281 var commandName = commandAst.CommandElements[0] as StringConstantExpressionAst;282 if (commandName != null && s_hashOfPessimizingCmdlets.Contains(commandName.Value))283 {284 // TODO: psuedo-bind the command invocation to figure out the variable and only force that variable to be unoptimized285 _disableOptimizations = true;286 }287 288 if (commandAst.InvocationOperator == TokenKind.Dot)289 {290 // For code like:291 // & { . { [string]$x = "abc" }; $x = 42; $x.GetType() }292 // We expect $x to be of type string, not int.293 // If we optimize, we'll end up throwing an error because the variable created in dotting is not consistent with the first294 // assignment to $x in the outer scope. To support this scenario, we'll disable optimizing when dotting.295 //296 // This is not a complete fix - some cmdlets (like foreach-object) dot scripts. We don't want to disable optimizations297 // unnecessarily (foreach-object is used heavily). This issue rarely comes up in foreach-object, so we'll live with the298 // errors. (See VariableNotWritableRare for the errors that happen when this issue arises.)299 300 _disableOptimizations = true;301 }302 303 return AstVisitAction.Continue;304 }305 306 public override AstVisitAction VisitFunctionDefinition(FunctionDefinitionAst functionDefinitionAst)307 {308 // We don't want to discover any variables in nested functions - they get their own scope.309 return AstVisitAction.SkipChildren;310 }311 312 public override AstVisitAction VisitScriptBlockExpression(ScriptBlockExpressionAst scriptBlockExpressionAst)313 {314 // We don't want to discover any variables in script block expressions - they get their own scope.315 return AstVisitAction.SkipChildren;316 }317 318 public override AstVisitAction VisitTrap(TrapStatementAst trapStatementAst)319 {320 // We don't want to discover any variables in traps - they get their own scope.321 return AstVisitAction.SkipChildren;322 }323 }324 325 internal class VariableAnalysis : ICustomAstVisitor2326 {327 // Tuple slots start at index 0. >= 0 means a variable is allocated in the tuple. -1 means we haven't328 // analyzed a specific use of a variable and don't know what slot it might be assigned to yet.329 internal const int Unanalyzed = -1;330 331 // In some cases, we want to force a variable to not be allocated in the tuple, but instead use the variable332 // table along with a PSVariable instance. For example,333 // 1. if a variable's type might change in the same scope;334 // 2. if there might be any validation attributes or more than one argument conversion335 // 3. if there is one argument conversion but the conversion type cannot be resolved at compile time (it's336 // possible that the assembly containing the type would be loaded during runtime)337 // in these cases, we rely on the setter PSVariable.Value to handle those attributes.338 internal const int ForceDynamic = -2;339 340 private sealed class LoopGotoTargets341 {342 internal LoopGotoTargets(string label, Block breakTarget, Block continueTarget)343 {344 this.Label = label;345 this.BreakTarget = breakTarget;346 this.ContinueTarget = continueTarget;347 }348 349 internal string Label { get; }350 351 internal Block BreakTarget { get; }352 353 internal Block ContinueTarget { get; }354 }355 356 private sealed class Block357 {358 internal readonly List<Ast> _asts = new List<Ast>();359 private readonly List<Block> _successors = new List<Block>();360 internal readonly List<Block> _predecessors = new List<Block>();361 362 internal object _visitData;363 internal bool _throws;364 internal bool _returns;365 366 internal bool _unreachable { get; private set; }367 368 // Only Entry block, that can be constructed via NewEntryBlock() is reachable initially.369 // all other blocks are unreachable.370 // reachability of block should be proved with FlowsTo() calls.371 public Block()372 {373 this._unreachable = true;374 }375 376 public static Block NewEntryBlock()377 {378 return new Block(unreachable: false);379 }380 381 private Block(bool unreachable)382 {383 this._unreachable = unreachable;384 }385 386 /// <summary>387 /// Tell flow analysis that this block can flow to next block.388 /// </summary>389 /// <param name="next"></param>390 internal void FlowsTo(Block next)391 {392 if (_successors.IndexOf(next) < 0)393 {394 if (!_unreachable)395 {396 next._unreachable = false;397 }398 399 _successors.Add(next);400 next._predecessors.Add(this);401 }402 }403 404 internal void AddAst(Ast ast)405 {406 Diagnostics.Assert(ast is VariableExpressionAst || ast is AssignmentTarget || ast is DataStatementAst,407 "Only add variables and assignments");408 _asts.Add(ast);409 }410 411 internal static List<Block> GenerateReverseDepthFirstOrder(Block block)412 {413 List<Block> result = new List<Block>();414 415 VisitDepthFirstOrder(block, result);416 result.Reverse();417 for (int i = 0; i < result.Count; i++)418 {419 result[i]._visitData = null;420 }421 422 return result;423 }424 425 private static void VisitDepthFirstOrder(Block block, List<Block> visitData)426 {427 if (ReferenceEquals(block._visitData, visitData))428 return;429 430 block._visitData = visitData;431 432 foreach (Block succ in block._successors)433 {434 VisitDepthFirstOrder(succ, visitData);435 }436 437 visitData.Add(block);438 }439 }440 441 private sealed class AssignmentTarget : Ast442 {443 internal readonly ExpressionAst _targetAst;444 internal readonly string _variableName;445 internal readonly Type _type;446 447 public AssignmentTarget(ExpressionAst targetExpressionAst)448 : base(PositionUtilities.EmptyExtent)449 {450 this._targetAst = targetExpressionAst;451 }452 453 public AssignmentTarget(string variableName, Type type)454 : base(PositionUtilities.EmptyExtent)455 {456 this._variableName = variableName;457 this._type = type;458 }459 460 public override Ast Copy()461 {462 Diagnostics.Assert(false, "This code is unreachable.");463 return null;464 }465 466 internal override object Accept(ICustomAstVisitor visitor)467 {468 Diagnostics.Assert(false, "This code is unreachable.");469 return null;470 }471 472 internal override AstVisitAction InternalVisit(AstVisitor visitor)473 {474 Diagnostics.Assert(false, "This code is unreachable.");475 return AstVisitAction.Continue;476 }477 }478 479 internal static string GetUnaliasedVariableName(string varName)480 {481 return varName.Equals(SpecialVariables.PSItem, StringComparison.OrdinalIgnoreCase)482 ? SpecialVariables.Underbar483 : varName;484 }485 486 internal static string GetUnaliasedVariableName(VariablePath varPath)487 {488 return GetUnaliasedVariableName(varPath.UnqualifiedPath);489 }490 491 // At compile time, we know specific variables are allscope and we can't optimize assignments. This hashset must remain492 // constant though - it only contains variable names known to _always_ be allscope. For other names, we need a special493 // check before choosing to run the optimized code or unoptimized (dotted) version which will correctly handle allscope494 // assignments.495 private static readonly ConcurrentDictionary<string, bool> s_allScopeVariables = new ConcurrentDictionary<string, bool>(1, 16, StringComparer.OrdinalIgnoreCase);496 497 internal static void NoteAllScopeVariable(string variableName)498 {499 s_allScopeVariables.GetOrAdd(variableName, true);500 }501 502 internal static bool AnyVariablesCouldBeAllScope(Dictionary<string, int> variableNames)503 {504 return variableNames.Any(static keyValuePair => s_allScopeVariables.ContainsKey(keyValuePair.Key));505 }506 507 private Dictionary<string, VariableAnalysisDetails> _variables;508 private Block _entryBlock;509 private Block _exitBlock;510 private Block _currentBlock;511 private bool _disableOptimizations;512 private readonly List<LoopGotoTargets> _loopTargets = new List<LoopGotoTargets>();513 private int _localsAllocated;514 515 // Used to analyze an expression that is invoked separately, i.e. a default argument.516 internal static Tuple<Type, Dictionary<string, int>> AnalyzeExpression(ExpressionAst exprAst)517 {518 return (new VariableAnalysis()).AnalyzeImpl(exprAst);519 }520 521 private Tuple<Type, Dictionary<string, int>> AnalyzeImpl(ExpressionAst exprAst)522 {523 _variables = FindAllVariablesVisitor.Visit(exprAst);524 525 // We disable optimizations for expression because it simplifies what we need to do when invoking526 // the default argument, and it's assumed that the code inside a default argument rarely, if ever, actually creates527 // any local variables.528 _disableOptimizations = true;529 Init();530 531 _localsAllocated = SpecialVariables.AutomaticVariables.Length;532 _currentBlock = _entryBlock;533 exprAst.Accept(this);534 _currentBlock.FlowsTo(_exitBlock);535 536 return FinishAnalysis();537 }538 539 internal static Tuple<Type, Dictionary<string, int>> AnalyzeTrap(TrapStatementAst trap)540 {541 return (new VariableAnalysis()).AnalyzeImpl(trap);542 }543 544 private Tuple<Type, Dictionary<string, int>> AnalyzeImpl(TrapStatementAst trap)545 {546 _variables = FindAllVariablesVisitor.Visit(trap);547 548 // We disable optimizations for trap because it simplifies what we need to do when invoking549 // the trap, and it's assumed that the code inside a trap rarely, if ever, actually creates550 // any local variables.551 _disableOptimizations = true;552 Init();553 554 _localsAllocated = SpecialVariables.AutomaticVariables.Length;555 _currentBlock = _entryBlock;556 trap.Body.Accept(this);557 _currentBlock.FlowsTo(_exitBlock);558 559 return FinishAnalysis();560 }561 562 private void Init()563 {564 _entryBlock = Block.NewEntryBlock();565 _exitBlock = new Block();566 }567 568 internal static Tuple<Type, Dictionary<string, int>> Analyze(IParameterMetadataProvider ast, bool disableOptimizations, bool scriptCmdlet)569 {570 return (new VariableAnalysis()).AnalyzeImpl(ast, disableOptimizations, scriptCmdlet);571 }572 573 /// <summary>574 /// Analyze a member function, marking variable references as "dynamic" (so they can be reported as errors)575 /// and also analyze the control flow to make sure every block returns (or throws)576 /// </summary>577 /// <param name="ast"></param>578 /// <returns></returns>579 internal static bool AnalyzeMemberFunction(FunctionMemberAst ast)580 {581 VariableAnalysis va = (new VariableAnalysis());582 va.AnalyzeImpl(ast, false, false);583 return va._exitBlock._predecessors.All(static b => b._returns || b._throws || b._unreachable);584 }585 586 private Tuple<Type, Dictionary<string, int>> AnalyzeImpl(IParameterMetadataProvider ast, bool disableOptimizations, bool scriptCmdlet)587 {588 _variables = FindAllVariablesVisitor.Visit(ast, disableOptimizations, scriptCmdlet, out _localsAllocated, out _disableOptimizations);589 Init();590 591 if (ast.Parameters != null)592 {593 foreach (var parameter in ast.Parameters)594 {595 var variablePath = parameter.Name.VariablePath;596 if (variablePath.IsAnyLocal())597 {598 bool anyAttributes = false;599 int countConverts = -1; // First convert is really the parameter type, so it doesn't count600 Type type = null;601 bool anyUnresolvedTypes = false;602 foreach (var paramAst in parameter.Attributes)603 {604 if (paramAst is TypeConstraintAst)605 {606 countConverts += 1;607 if (type == null)608 {609 type = paramAst.TypeName.GetReflectionType();610 if (type == null)611 {612 anyUnresolvedTypes = true;613 }614 }615 }616 else617 {618 var attrType = paramAst.TypeName.GetReflectionAttributeType();619 if (attrType == null)620 {621 anyUnresolvedTypes = true;622 }623 else if (typeof(ValidateArgumentsAttribute).IsAssignableFrom(attrType)624 || typeof(ArgumentTransformationAttribute).IsAssignableFrom(attrType))625 {626 // If there are any attributes that have semantic meaning, we need to use a PSVariable.627 anyAttributes = true;628 }629 }630 }631 632 var varName = GetUnaliasedVariableName(variablePath);633 var details = _variables[varName];634 details.Assigned = true;635 type ??= details.Type ?? typeof(object);636 637 // automatic and preference variables are pre-allocated, so they can't be unallocated638 // and forced to be dynamic.639 // unresolved types can happen at parse time640 // [ref] parameters are forced to dynamic so that we can assign $null in the parameter641 // binder w/o conversions kicking in (the setter in MutableTuple will convert $null to PSReference<Null>642 // but that won't happen if we create a PSVariable (this is an ugly hack, but it works.)643 if ((anyAttributes || anyUnresolvedTypes || countConverts > 0 || typeof(PSReference).IsAssignableFrom(type) || MustBeBoxed(type)) &&644 !details.Automatic && !details.PreferenceVariable)645 {646 details.LocalTupleIndex = ForceDynamic;647 }648 649 _entryBlock.AddAst(new AssignmentTarget(varName, type));650 }651 }652 }653 654 ast.Body.Accept(this);655 656 return FinishAnalysis(scriptCmdlet);657 }658 659 private Tuple<Type, Dictionary<string, int>> FinishAnalysis(bool scriptCmdlet = false)660 {661 var blocks = Block.GenerateReverseDepthFirstOrder(_entryBlock);662 663 // The first block has no predecessors, so analyze outside the loop to "prime" the bitarray.664 var bitArray = new BitArray(_variables.Count);665 blocks[0]._visitData = bitArray;666 AnalyzeBlock(bitArray, blocks[0]);667 668 for (int index = 1; index < blocks.Count; index++)669 {670 var block = blocks[index];671 672 bitArray = new BitArray(_variables.Count);673 bitArray.SetAll(true);674 block._visitData = bitArray;675 676 int predCount = 0;677 foreach (var pred in block._predecessors)678 {679 // VisitData can be null when the pred occurs because of a continue statement.680 if (pred._visitData != null)681 {682 predCount += 1;683 bitArray.And((BitArray)pred._visitData);684 }685 }686 687 Diagnostics.Assert(predCount != 0, "If we didn't and anything, there is a flaw in the logic and incorrect code may be generated.");688 689 AnalyzeBlock(bitArray, block);690 }691 692 Diagnostics.Assert(_exitBlock._predecessors.All(p => p._unreachable || p._visitData is BitArray), "VisitData wasn't set on a reachable block");693 694 foreach (var details in _variables.Values)695 {696 if (details.LocalTupleIndex == ForceDynamic)697 {698 foreach (var ast in details.AssociatedAsts)699 {700 FixTupleIndex(ast, ForceDynamic);701 FixAssigned(ast, details);702 }703 }704 }705 706 // Automatic variables from 'SpecialVariables.AutomaticVariables' usually are pre-allocated,707 // but there could be situations where some of them are forced to be dynamic. We need to count708 // them in when creating tuple slots in such cases to make sure we create enough slots.709 // However, $? is not a real automatic variable from 'SpecialVariables.AutomaticVariables'710 // even though it's marked as so, and thus we need to exclude it.711 var orderedLocals = (from details in _variables.Values712 where (details.LocalTupleIndex >= 0 || (details.LocalTupleIndex == ForceDynamic &&713 details.Automatic &&714 details.Name != SpecialVariables.Question))715 orderby details.LocalTupleIndex716 select details).ToArray();717 718 Diagnostics.Assert(!_disableOptimizations719 || orderedLocals.Length == (int)AutomaticVariable.NumberOfAutomaticVariables +720 (scriptCmdlet ? SpecialVariables.PreferenceVariables.Length : 0),721 "analysis is incorrectly allocating number of locals when optimizations are disabled.");722 723 var nameToIndexMap = new Dictionary<string, int>(0, StringComparer.OrdinalIgnoreCase);724 for (int i = 0; i < orderedLocals.Length; ++i)725 {726 var details = orderedLocals[i];727 var name = details.Name;728 nameToIndexMap.Add(name, i);729 730 if (details.LocalTupleIndex != i)731 {732 foreach (var ast in details.AssociatedAsts)733 {734 FixTupleIndex(ast, i);735 }736 }737 // Automatic variables assign the type directly, not relying on any analysis. For738 // all other variables, we don't determine the type of the local until we're done739 // with the analysis.740 Diagnostics.Assert(details.Type != null, "Type should be resolved already");741 }742 743 var tupleType = MutableTuple.MakeTupleType((from l in orderedLocals select l.Type).ToArray());744 return Tuple.Create(tupleType, nameToIndexMap);745 }746 747 private static bool MustBeBoxed(Type type)748 {749 // We need to box mutable value types so that member operations like750 // $value.Property = 42751 // We make sure we never allocate an instance of such mutable types in the MutableType.752 753 return (type.IsValueType && PSVariableAssignmentBinder.IsValueTypeMutable(type)) && typeof(SwitchParameter) != type;754 }755 756 private static void FixTupleIndex(Ast ast, int newIndex)757 {758 var variableAst = ast as VariableExpressionAst;759 if (variableAst != null)760 {761 if (variableAst.TupleIndex != ForceDynamic)762 {763 variableAst.TupleIndex = newIndex;764 }765 }766 else767 {768 var dataStatementAst = ast as DataStatementAst;769 if (dataStatementAst != null)770 {771 if (dataStatementAst.TupleIndex != ForceDynamic)772 {773 dataStatementAst.TupleIndex = newIndex;774 }775 }776 }777 }778 779 private static void FixAssigned(Ast ast, VariableAnalysisDetails details)780 {781 var variableAst = ast as VariableExpressionAst;782 if (variableAst != null && details.Assigned)783 {784 variableAst.Assigned = true;785 }786 }787 788 private void AnalyzeBlock(BitArray assignedBitArray, Block block)789 {790 foreach (var ast in block._asts)791 {792 var variableExpressionAst = ast as VariableExpressionAst;793 if (variableExpressionAst != null)794 {795 var varPath = variableExpressionAst.VariablePath;796 if (varPath.IsAnyLocal())797 {798 var varName = GetUnaliasedVariableName(varPath);799 var details = _variables[varName];800 if (details.Automatic)801 {802 variableExpressionAst.TupleIndex = details.LocalTupleIndex;803 variableExpressionAst.Automatic = true;804 }805 else806 {807 variableExpressionAst.TupleIndex = assignedBitArray[details.BitIndex] && !details.PreferenceVariable808 ? details.LocalTupleIndex809 : VariableAnalysis.ForceDynamic;810 }811 }812 813 continue;814 }815 816 var assignmentTarget = ast as AssignmentTarget;817 if (assignmentTarget != null)818 {819 if (assignmentTarget._targetAst != null)820 {821 CheckLHSAssign(assignmentTarget._targetAst, assignedBitArray);822 }823 else824 {825 CheckLHSAssignVar(assignmentTarget._variableName, assignedBitArray, assignmentTarget._type);826 }827 828 continue;829 }830 831 var dataStatementAst = ast as DataStatementAst;832 if (dataStatementAst != null)833 {834 var details = CheckLHSAssignVar(dataStatementAst.Variable, assignedBitArray, typeof(object));835 dataStatementAst.TupleIndex = details.LocalTupleIndex;836 details.AssociatedAsts.Add(dataStatementAst);837 continue;838 }839 840 Diagnostics.Assert(false, "Unexpected type in list of ASTs");841 }842 }843 844 private void CheckLHSAssign(ExpressionAst lhs, BitArray assignedBitArray)845 {846 var convertExpr = lhs as ConvertExpressionAst;847 Type convertType = null;848 if (convertExpr != null)849 {850 lhs = convertExpr.Child;851 convertType = convertExpr.StaticType;852 }853 854 var varExpr = lhs as VariableExpressionAst;855 Diagnostics.Assert(varExpr != null, "unexpected ast type on lhs");856 857 var varPath = varExpr.VariablePath;858 if (varPath.IsAnyLocal())859 {860 var varName = GetUnaliasedVariableName(varPath);861 if (convertType == null &&862 (varName.Equals(SpecialVariables.@foreach, StringComparison.OrdinalIgnoreCase) ||863 varName.Equals(SpecialVariables.@switch, StringComparison.OrdinalIgnoreCase)))864 {865 // $switch/$foreach are normally typed as IEnumerator, but if the values are directly866 // assigned (as opposed to implicitly assigned which goes directly to CheckLHSAssignVar),867 // then force the type to object.868 convertType = typeof(object);869 }870 871 VariableAnalysisDetails analysisDetails = CheckLHSAssignVar(varName, assignedBitArray, convertType);872 873 analysisDetails.AssociatedAsts.Add(varExpr);874 analysisDetails.Assigned = true;875 varExpr.TupleIndex = analysisDetails.LocalTupleIndex;876 varExpr.Automatic = analysisDetails.Automatic;877 }878 else879 {880 varExpr.TupleIndex = VariableAnalysis.ForceDynamic;881 }882 }883 884 private VariableAnalysisDetails CheckLHSAssignVar(string variableName, BitArray assignedBitArray, Type convertType)885 {886 var analysisDetails = _variables[variableName];887 if (analysisDetails.LocalTupleIndex == VariableAnalysis.Unanalyzed)888 {889 analysisDetails.LocalTupleIndex = _disableOptimizations || s_allScopeVariables.ContainsKey(variableName)890 ? VariableAnalysis.ForceDynamic891 : _localsAllocated++;892 }893 894 if (convertType != null && MustBeBoxed(convertType))895 {896 analysisDetails.LocalTupleIndex = VariableAnalysis.ForceDynamic;897 }898 899 var type = analysisDetails.Type;900 if (type == null)901 {902 analysisDetails.Type = convertType ?? typeof(object);903 }904 else905 {906 if (!assignedBitArray[analysisDetails.BitIndex] && convertType == null)907 {908 // The variable has not been assigned in the current flow control path, but has been on some other909 // path (because the type was already assigned.) Make sure they are compatible by forcing a type comparison.910 convertType = typeof(object);911 }912 913 if (convertType != null && !convertType.Equals(type))914 {915 if (analysisDetails.Automatic || analysisDetails.PreferenceVariable)916 {917 // Can't be dynamic, but we were optimistic that we could strongly type the automatic918 // and it turns out we can't.919 analysisDetails.Type = typeof(object);920 }921 else922 {923 analysisDetails.LocalTupleIndex = ForceDynamic;924 }925 }926 }927 928 assignedBitArray.Set(analysisDetails.BitIndex, true);929 930 return analysisDetails;931 }932 933 public object VisitErrorStatement(ErrorStatementAst errorStatementAst)934 {935 return null;936 }937 938 public object VisitErrorExpression(ErrorExpressionAst errorExpressionAst)939 {940 return null;941 }942 943 public object VisitScriptBlock(ScriptBlockAst scriptBlockAst)944 {945 _currentBlock = _entryBlock;946 947 scriptBlockAst.DynamicParamBlock?.Accept(this);948 scriptBlockAst.BeginBlock?.Accept(this);949 scriptBlockAst.ProcessBlock?.Accept(this);950 scriptBlockAst.EndBlock?.Accept(this);951 scriptBlockAst.CleanBlock?.Accept(this);952 953 _currentBlock.FlowsTo(_exitBlock);954 955 return null;956 }957 958 public object VisitParamBlock(ParamBlockAst paramBlockAst)959 {960 return null;961 }962 963 public object VisitNamedBlock(NamedBlockAst namedBlockAst)964 {965 // Don't visit traps - they get their own scope966 return VisitStatementBlock(namedBlockAst.Statements);967 }968 969 public object VisitTypeConstraint(TypeConstraintAst typeConstraintAst)970 {971 Diagnostics.Assert(false, "Code is unreachable");972 return null;973 }974 975 public object VisitAttribute(AttributeAst attributeAst)976 {977 Diagnostics.Assert(false, "Code is unreachable");978 return null;979 }980 981 public object VisitNamedAttributeArgument(NamedAttributeArgumentAst namedAttributeArgumentAst)982 {983 Diagnostics.Assert(false, "Code is unreachable");984 return null;985 }986 987 public object VisitParameter(ParameterAst parameterAst)988 {989 // Nothing to do now, we've already allocated parameters in the first pass looking for all variable naems.990 Diagnostics.Assert(false, "Code is unreachable");991 return null;992 }993 994 public object VisitFunctionDefinition(FunctionDefinitionAst functionDefinitionAst)995 {996 // Don't recurse into the function definition, it's variables are distinct from the script block997 // we're currently analyzing.998 999 return null;1000 }1001 1002 public object VisitStatementBlock(StatementBlockAst statementBlockAst)1003 {1004 // Don't visit traps - they get their own scope1005 return VisitStatementBlock(statementBlockAst.Statements);1006 }1007 1008 private object VisitStatementBlock(ReadOnlyCollection<StatementAst> statements)1009 {1010 foreach (var stmt in statements)1011 {1012 stmt.Accept(this);1013 }1014 1015 return null;1016 }1017 1018 public object VisitIfStatement(IfStatementAst ifStmtAst)1019 {1020 Block afterStmt = new Block();1021 1022 if (ifStmtAst.ElseClause == null)1023 {1024 // There is no else, flow can go straight to afterStmt.1025 _currentBlock.FlowsTo(afterStmt);1026 }1027 1028 int clauseCount = ifStmtAst.Clauses.Count;1029 for (int i = 0; i < clauseCount; i++)1030 {1031 var clause = ifStmtAst.Clauses[i];1032 bool isLastClause = (i == (clauseCount - 1) && ifStmtAst.ElseClause == null);1033 Block clauseBlock = new Block();1034 Block nextBlock = isLastClause ? afterStmt : new Block();1035 1036 clause.Item1.Accept(this);1037 1038 _currentBlock.FlowsTo(clauseBlock);1039 _currentBlock.FlowsTo(nextBlock);1040 _currentBlock = clauseBlock;1041 1042 clause.Item2.Accept(this);1043 1044 _currentBlock.FlowsTo(afterStmt);1045 _currentBlock = nextBlock;1046 }1047 1048 if (ifStmtAst.ElseClause != null)1049 {1050 ifStmtAst.ElseClause.Accept(this);1051 _currentBlock.FlowsTo(afterStmt);1052 }1053 1054 _currentBlock = afterStmt;1055 return null;1056 }1057 1058 public object VisitTernaryExpression(TernaryExpressionAst ternaryExpressionAst)1059 {1060 var ifTrue = new Block();1061 var ifFalse = new Block();1062 var after = new Block();1063 1064 ternaryExpressionAst.Condition.Accept(this);1065 _currentBlock.FlowsTo(ifTrue);1066 _currentBlock.FlowsTo(ifFalse);1067 _currentBlock = ifTrue;1068 1069 ternaryExpressionAst.IfTrue.Accept(this);1070 _currentBlock.FlowsTo(after);1071 _currentBlock = ifFalse;1072 1073 ternaryExpressionAst.IfFalse.Accept(this);1074 _currentBlock.FlowsTo(after);1075 _currentBlock = after;1076 1077 return null;1078 }1079 1080 public object VisitTrap(TrapStatementAst trapStatementAst)1081 {1082 trapStatementAst.Body.Accept(this);1083 return null;1084 }1085 1086 public object VisitSwitchStatement(SwitchStatementAst switchStatementAst)1087 {1088 var details = _variables[SpecialVariables.@switch];1089 if (details.LocalTupleIndex == VariableAnalysis.Unanalyzed && !_disableOptimizations)1090 {1091 details.LocalTupleIndex = _localsAllocated++;1092 }1093 1094 Action generateCondition = () =>1095 {1096 switchStatementAst.Condition.Accept(this);1097 1098 // $switch is set after evaluating the condition.1099 _currentBlock.AddAst(new AssignmentTarget(SpecialVariables.@switch, typeof(IEnumerator)));1100 };1101 1102 Action switchBodyGenerator = () =>1103 {1104 bool hasDefault = (switchStatementAst.Default != null);1105 Block afterStmt = new Block();1106 1107 int clauseCount = switchStatementAst.Clauses.Count;1108 for (int i = 0; i < clauseCount; i++)1109 {1110 var clause = switchStatementAst.Clauses[i];1111 Block clauseBlock = new Block();1112 bool isLastClause = (i == (clauseCount - 1) && !hasDefault);1113 Block nextBlock = isLastClause ? afterStmt : new Block();1114 1115 clause.Item1.Accept(this);1116 1117 _currentBlock.FlowsTo(nextBlock);1118 _currentBlock.FlowsTo(clauseBlock);1119 _currentBlock = clauseBlock;1120 1121 clause.Item2.Accept(this);1122 1123 if (!isLastClause)1124 {1125 _currentBlock.FlowsTo(nextBlock);1126 _currentBlock = nextBlock;1127 }1128 }1129 1130 if (hasDefault)1131 {1132 // If any clause was executed, we skip the default, so there is always a branch over the default.1133 _currentBlock.FlowsTo(afterStmt);1134 switchStatementAst.Default.Accept(this);1135 }1136 1137 _currentBlock.FlowsTo(afterStmt);1138 _currentBlock = afterStmt;1139 };1140 1141 GenerateWhileLoop(switchStatementAst.Label, generateCondition, switchBodyGenerator);1142 1143 return null;1144 }1145 1146 public object VisitDataStatement(DataStatementAst dataStatementAst)1147 {1148 dataStatementAst.Body.Accept(this);1149 if (dataStatementAst.Variable != null)1150 {1151 _currentBlock.AddAst(dataStatementAst);1152 }1153 1154 return null;1155 }1156 1157 private void GenerateWhileLoop(string loopLabel,1158 Action generateCondition,1159 Action generateLoopBody,1160 Ast continueAction = null)1161 {1162 // We model the flow graph like this (if continueAction is null, the first part is slightly different):1163 // goto L1164 // :ContinueTarget1165 // continueAction1166 // :L1167 // if (condition)1168 // {1169 // loop body1170 // // break -> goto BreakTarget1171 // // continue -> goto ContinueTarget1172 // goto ContinueTarget1173 // }1174 // :BreakTarget1175 1176 var continueBlock = new Block();1177 1178 if (continueAction != null)1179 {1180 var blockAfterContinue = new Block();1181 1182 // Represent the goto over the condition before the first iteration.1183 _currentBlock.FlowsTo(blockAfterContinue);1184 1185 _currentBlock = continueBlock;1186 continueAction.Accept(this);1187 1188 _currentBlock.FlowsTo(blockAfterContinue);1189 _currentBlock = blockAfterContinue;1190 }1191 else1192 {1193 _currentBlock.FlowsTo(continueBlock);1194 _currentBlock = continueBlock;1195 }1196 1197 var bodyBlock = new Block();1198 var breakBlock = new Block();1199 1200 // Condition can be null from an uncommon for loop: for() {}