MegaBites-AI/Windows-powershell

1/* ****************************************************************************2 *3 * Copyright (c) Microsoft Corporation.4 *5 * This source code is subject to terms and conditions of the Apache License, Version 2.0. A6 * copy of the license can be found in the License.html file at the root of this distribution. If7 * you cannot locate the Apache License, Version 2.0, please send an email to8 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound9 * by the terms of the Apache License, Version 2.0.10 *11 * You must not remove this notice, or any other, from this software.12 *13 *14 * ***************************************************************************/15 16#if !CLR217using System.Linq.Expressions;18#endif19using System.Collections.Generic;20using System.Diagnostics;21using System.Management.Automation.Language;22using System.Runtime.CompilerServices;23 24namespace System.Management.Automation.Interpreter25{26    using AstUtils = System.Management.Automation.Interpreter.Utils;27    using LoopFunc = Func<object[], StrongBox<object>[], InterpretedFrame, int>;28 29    internal sealed class LoopCompiler : ExpressionVisitor30    {31        private struct LoopVariable32        {33            public ExpressionAccess Access;34 35            // a variable that holds on the strong box for closure variables:36            public ParameterExpression BoxStorage;37 38            public LoopVariable(ExpressionAccess access, ParameterExpression box)39            {40                Access = access;41                BoxStorage = box;42            }43 44            public override string ToString()45            {46                return Access.ToString() + " " + BoxStorage;47            }48        }49 50        private readonly ParameterExpression _frameDataVar;51        private readonly ParameterExpression _frameClosureVar;52        private readonly ParameterExpression _frameVar;53        private readonly LabelTarget _returnLabel;54        // locals and closure variables defined outside the loop55        private readonly Dictionary<ParameterExpression, LocalVariable> _outerVariables, _closureVariables;56        private readonly PowerShellLoopExpression _loop;57        private List<ParameterExpression> _temps;58        // tracks variables that flow in and flow out for initialization and59        private readonly Dictionary<ParameterExpression, LoopVariable> _loopVariables;60        // variables which are defined and used within the loop61        private HashSet<ParameterExpression> _loopLocals;62 63        private readonly HybridReferenceDictionary<LabelTarget, BranchLabel> _labelMapping;64        private readonly int _loopStartInstructionIndex;65        private readonly int _loopEndInstructionIndex;66 67        internal LoopCompiler(PowerShellLoopExpression loop,68                              HybridReferenceDictionary<LabelTarget, BranchLabel> labelMapping,69                              Dictionary<ParameterExpression, LocalVariable> locals,70                              Dictionary<ParameterExpression, LocalVariable> closureVariables,71                              int loopStartInstructionIndex,72                              int loopEndInstructionIndex)73        {74            _loop = loop;75            _outerVariables = locals;76            _closureVariables = closureVariables;77            _frameDataVar = Expression.Parameter(typeof(object[]));78            _frameClosureVar = Expression.Parameter(typeof(StrongBox<object>[]));79            _frameVar = Expression.Parameter(typeof(InterpretedFrame));80            _loopVariables = new Dictionary<ParameterExpression, LoopVariable>();81            _returnLabel = Expression.Label(typeof(int));82            _labelMapping = labelMapping;83            _loopStartInstructionIndex = loopStartInstructionIndex;84            _loopEndInstructionIndex = loopEndInstructionIndex;85        }86 87        internal LoopFunc CreateDelegate()88        {89            var loop = Visit(_loop);90            var body = new List<Expression>();91            var finallyClause = new List<Expression>();92 93            foreach (var variable in _loopVariables)94            {95                LocalVariable local;96                if (!_outerVariables.TryGetValue(variable.Key, out local))97                {98                    local = _closureVariables[variable.Key];99                }100 101                Expression elemRef = local.LoadFromArray(_frameDataVar, _frameClosureVar);102 103                if (local.InClosureOrBoxed)104                {105                    var box = variable.Value.BoxStorage;106                    Debug.Assert(box != null);107                    body.Add(Expression.Assign(box, elemRef));108                    AddTemp(box);109                }110                else111                {112                    // Always initialize the variable even if it is only written to.113                    // If a write-only variable is actually not assigned during execution of the loop we will still write some value back.114                    // This value must be the original value, which we assign at entry.115                    body.Add(Expression.Assign(variable.Key, AstUtils.Convert(elemRef, variable.Key.Type)));116 117                    if ((variable.Value.Access & ExpressionAccess.Write) != 0)118                    {119                        finallyClause.Add(Expression.Assign(elemRef, AstUtils.Box(variable.Key)));120                    }121 122                    AddTemp(variable.Key);123                }124            }125 126            if (finallyClause.Count > 0)127            {128                body.Add(Expression.TryFinally(loop, Expression.Block(finallyClause)));129            }130            else131            {132                body.Add(loop);133            }134 135            body.Add(Expression.Label(_returnLabel, Expression.Constant(_loopEndInstructionIndex - _loopStartInstructionIndex)));136 137            var lambda = Expression.Lambda<LoopFunc>(138                _temps != null ? Expression.Block(_temps, body) : Expression.Block(body),139                new[] { _frameDataVar, _frameClosureVar, _frameVar }140            );141            return lambda.Compile();142        }143 144        protected override Expression VisitExtension(Expression node)145        {146            // Reduce extensions before we visit them so that we operate on a plain DLR tree,147            // where we know relationships among the nodes (which nodes represent write context etc.).148            if (node.CanReduce)149            {150                return Visit(node.Reduce());151            }152 153            return base.VisitExtension(node);154        }155 156        #region Gotos157 158        protected override Expression VisitGoto(GotoExpression node)159        {160            BranchLabel label;161 162            var target = node.Target;163            var value = Visit(node.Value);164 165            // TODO: Is it possible for an inner reducible node of the loop to rely on nodes produced by reducing outer reducible nodes?166 167            // Unknown label => must be within the loop:168            if (!_labelMapping.TryGetValue(target, out label))169            {170                return node.Update(target, value);171            }172 173            // Known label within the loop:174            if (label.TargetIndex >= _loopStartInstructionIndex && label.TargetIndex < _loopEndInstructionIndex)175            {176                return node.Update(target, value);177            }178 179            return Expression.Return(_returnLabel,180                (value != null && value.Type != typeof(void)) ?181                    Expression.Call(_frameVar, InterpretedFrame.GotoMethod, Expression.Constant(label.LabelIndex), AstUtils.Box(value)) :182                    Expression.Call(_frameVar, InterpretedFrame.VoidGotoMethod, Expression.Constant(label.LabelIndex)),183                node.Type184           );185        }186 187        #endregion188 189        #region Local Variables190 191        // Gather all outer variables accessed in the loop.192        // Determines which ones are read from and written to.193        // We will consider a variable as "read" if it is read anywhere in the loop even though194        // the first operation might actually always be "write". We could do better if we had CFG.195 196        protected override Expression VisitBlock(BlockExpression node)197        {198            var variables = ((BlockExpression)node).Variables;199            var prevLocals = EnterVariableScope(variables);200 201            var res = base.VisitBlock(node);202 203            ExitVariableScope(prevLocals);204            return res;205        }206 207        private HashSet<ParameterExpression> EnterVariableScope(ICollection<ParameterExpression> variables)208        {209            if (_loopLocals == null)210            {211                _loopLocals = new HashSet<ParameterExpression>(variables);212                return null;213            }214 215            var prevLocals = new HashSet<ParameterExpression>(_loopLocals);216            _loopLocals.UnionWith(variables);217            return prevLocals;218        }219 220        protected override CatchBlock VisitCatchBlock(CatchBlock node)221        {222            if (node.Variable != null)223            {224                var prevLocals = EnterVariableScope(new[] { node.Variable });225                var res = base.VisitCatchBlock(node);226                ExitVariableScope(prevLocals);227                return res;228            }229            else230            {231                return base.VisitCatchBlock(node);232            }233        }234 235        protected override Expression VisitLambda<T>(Expression<T> node)236        {237            var prevLocals = EnterVariableScope(node.Parameters);238            try239            {240                return base.VisitLambda<T>(node);241            }242            finally243            {244                ExitVariableScope(prevLocals);245            }246        }247 248        private void ExitVariableScope(HashSet<ParameterExpression> prevLocals)249        {250            _loopLocals = prevLocals;251        }252 253        protected override Expression VisitBinary(BinaryExpression node)254        {255            // reduce compound assignments:256            if (node.CanReduce)257            {258                return Visit(node.Reduce());259            }260 261            Debug.Assert(!node.NodeType.IsReadWriteAssignment());262 263            var param = node.Left as ParameterExpression;264            if (param != null && node.NodeType == ExpressionType.Assign)265            {266                var left = VisitVariable(param, ExpressionAccess.Write);267                var right = Visit(node.Right);268 269                // left parameter is a boxed variable:270                if (left.Type != param.Type)271                {272                    Debug.Assert(left.Type == typeof(object));273 274                    Expression rightVar;275                    if (right.NodeType != ExpressionType.Parameter)276                    {277                        // { left.Value = (object)(rightVar = right), rightVar }278 279                        rightVar = AddTemp(Expression.Parameter(right.Type));280                        right = Expression.Assign(rightVar, right);281                    }282                    else283                    {284                        // { left.Value = (object)right, right }285 286                        rightVar = right;287                    }288 289                    return Expression.Block(290                        node.Update(left, null, Expression.Convert(right, left.Type)),291                        rightVar292                    );293                }294                else295                {296                    return node.Update(left, null, right);297                }298            }299            else300            {301                return base.VisitBinary(node);302            }303        }304 305        protected override Expression VisitUnary(UnaryExpression node)306        {307            // reduce inplace increment/decrement:308            if (node.CanReduce)309            {310                return Visit(node.Reduce());311            }312 313            Debug.Assert(!node.NodeType.IsReadWriteAssignment());314            return base.VisitUnary(node);315        }316 317        // TODO: if we supported ref/out parameter we would need to override318        // MethodCallExpression, VisitDynamic and VisitNew319 320        protected override Expression VisitParameter(ParameterExpression node)321        {322            return VisitVariable(node, ExpressionAccess.Read);323        }324 325        private Expression VisitVariable(ParameterExpression node, ExpressionAccess access)326        {327            ParameterExpression box;328            LoopVariable existing;329            LocalVariable loc;330 331            if (_loopLocals.Contains(node))332            {333                // local to the loop - not propagated in or out334                return node;335            }336            else if (_loopVariables.TryGetValue(node, out existing))337            {338                // existing outer variable that we are already tracking339                box = existing.BoxStorage;340                _loopVariables[node] = new LoopVariable(existing.Access | access, box);341            }342            else if (_outerVariables.TryGetValue(node, out loc) ||343              (_closureVariables != null && _closureVariables.TryGetValue(node, out loc)))344            {345                // not tracking this variable yet, but defined in outer scope and seen for the 1st time346                box = loc.InClosureOrBoxed ? Expression.Parameter(typeof(StrongBox<object>), node.Name) : null;347                _loopVariables[node] = new LoopVariable(access, box);348            }349            else350            {351                // node is a variable defined in a nested lambda -> skip352                return node;353            }354 355            if (box != null)356            {357                if ((access & ExpressionAccess.Write) != 0)358                {359                    // compound assignments were reduced:360                    Debug.Assert((access & ExpressionAccess.Read) == 0);361 362                    // box.Value = (object)rhs363                    return LightCompiler.Unbox(box);364                }365                else366                {367                    // (T)box.Value368                    return Expression.Convert(LightCompiler.Unbox(box), node.Type);369                }370            }371 372            return node;373        }374 375        private ParameterExpression AddTemp(ParameterExpression variable)376        {377            _temps ??= new List<ParameterExpression>();378 379            _temps.Add(variable);380            return variable;381        }382 383        #endregion384    }385}386