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;23using System.Threading;24 25namespace System.Management.Automation.Interpreter26{27    using LoopFunc = Func<object[], StrongBox<object>[], InterpretedFrame, int>;28 29    internal abstract class OffsetInstruction : Instruction30    {31        internal const int Unknown = Int32.MinValue;32        internal const int CacheSize = 32;33 34        // the offset to jump to (relative to this instruction):35        protected int _offset = Unknown;36 37        public int Offset { get { return _offset; } }38 39        public abstract Instruction[] Cache { get; }40 41        public Instruction Fixup(int offset)42        {43            Debug.Assert(_offset == Unknown && offset != Unknown);44            _offset = offset;45 46            var cache = Cache;47            if (cache != null && offset >= 0 && offset < cache.Length)48            {49                return cache[offset] ?? (cache[offset] = this);50            }51 52            return this;53        }54 55        public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects)56        {57            return ToString() + (_offset != Unknown ? " -> " + (instructionIndex + _offset) : string.Empty);58        }59 60        public override string ToString()61        {62            return InstructionName + (_offset == Unknown ? "(?)" : "(" + _offset + ")");63        }64    }65 66    internal sealed class BranchFalseInstruction : OffsetInstruction67    {68        private static Instruction[] s_cache;69 70        public override Instruction[] Cache71        {72            get { return s_cache ??= new Instruction[CacheSize]; }73        }74 75        internal BranchFalseInstruction()76        {77        }78 79        public override int ConsumedStack { get { return 1; } }80 81        public override int Run(InterpretedFrame frame)82        {83            Debug.Assert(_offset != Unknown);84 85            if (!(bool)frame.Pop())86            {87                return _offset;88            }89 90            return +1;91        }92    }93 94    internal sealed class BranchTrueInstruction : OffsetInstruction95    {96        private static Instruction[] s_cache;97 98        public override Instruction[] Cache99        {100            get { return s_cache ??= new Instruction[CacheSize]; }101        }102 103        internal BranchTrueInstruction()104        {105        }106 107        public override int ConsumedStack { get { return 1; } }108 109        public override int Run(InterpretedFrame frame)110        {111            Debug.Assert(_offset != Unknown);112 113            if ((bool)frame.Pop())114            {115                return _offset;116            }117 118            return +1;119        }120    }121 122    internal sealed class CoalescingBranchInstruction : OffsetInstruction123    {124        private static Instruction[] s_cache;125 126        public override Instruction[] Cache127        {128            get { return s_cache ??= new Instruction[CacheSize]; }129        }130 131        internal CoalescingBranchInstruction()132        {133        }134 135        public override int ConsumedStack { get { return 1; } }136 137        public override int ProducedStack { get { return 1; } }138 139        public override int Run(InterpretedFrame frame)140        {141            Debug.Assert(_offset != Unknown);142 143            if (frame.Peek() != null)144            {145                return _offset;146            }147 148            return +1;149        }150    }151 152    internal class BranchInstruction : OffsetInstruction153    {154        private static Instruction[][][] s_caches;155 156        public override Instruction[] Cache157        {158            get159            {160                s_caches ??= new Instruction[2][][] { new Instruction[2][], new Instruction[2][] };161 162                return s_caches[ConsumedStack][ProducedStack] ?? (s_caches[ConsumedStack][ProducedStack] = new Instruction[CacheSize]);163            }164        }165 166        internal readonly bool _hasResult;167        internal readonly bool _hasValue;168 169        internal BranchInstruction()170            : this(false, false)171        {172        }173 174        public BranchInstruction(bool hasResult, bool hasValue)175        {176            _hasResult = hasResult;177            _hasValue = hasValue;178        }179 180        public override int ConsumedStack181        {182            get { return _hasValue ? 1 : 0; }183        }184 185        public override int ProducedStack186        {187            get { return _hasResult ? 1 : 0; }188        }189 190        public override int Run(InterpretedFrame frame)191        {192            Debug.Assert(_offset != Unknown);193 194            return _offset;195        }196    }197 198    internal abstract class IndexedBranchInstruction : Instruction199    {200        protected const int CacheSize = 32;201 202        internal readonly int _labelIndex;203 204        protected IndexedBranchInstruction(int labelIndex)205        {206            _labelIndex = labelIndex;207        }208 209        public RuntimeLabel GetLabel(InterpretedFrame frame)210        {211            Debug.Assert(_labelIndex != UnknownInstrIndex);212            return frame.Interpreter._labels[_labelIndex];213        }214 215        public override string ToDebugString(int instructionIndex, object cookie, Func<int, int> labelIndexer, IList<object> objects)216        {217            Debug.Assert(_labelIndex != UnknownInstrIndex);218            int targetIndex = labelIndexer(_labelIndex);219            return ToString() + (targetIndex != BranchLabel.UnknownIndex ? " -> " + targetIndex : string.Empty);220        }221 222        public override string ToString()223        {224            Debug.Assert(_labelIndex != UnknownInstrIndex);225            return InstructionName + "[" + _labelIndex + "]";226        }227    }228 229    /// <summary>230    /// This instruction implements a goto expression that can jump out of any expression.231    /// It pops values (arguments) from the evaluation stack that the expression tree nodes in between232    /// the goto expression and the target label node pushed and not consumed yet.233    /// A goto expression can jump into a node that evaluates arguments only if it carries234    /// a value and jumps right after the first argument (the carried value will be used as the first argument).235    /// Goto can jump into an arbitrary child of a BlockExpression since the block doesn't accumulate values236    /// on evaluation stack as its child expressions are being evaluated.237    ///238    /// Goto needs to execute any finally blocks on the way to the target label.239    /// <example>240    /// {241    ///     f(1, 2, try { g(3, 4, try { goto L } finally { ... }, 6) } finally { ... }, 7, 8)242    ///     L: ...243    /// }244    /// </example>245    /// The goto expression here jumps to label L while having 4 items on evaluation stack (1, 2, 3 and 4).246    /// The jump needs to execute both finally blocks, the first one on stack level 4 the247    /// second one on stack level 2. So, it needs to jump the first finally block, pop 2 items from the stack,248    /// run second finally block and pop another 2 items from the stack and set instruction pointer to label L.249    /// </summary>250    internal sealed class GotoInstruction : IndexedBranchInstruction251    {252        private const int Variants = 4;253 254        private static readonly GotoInstruction[] s_cache = new GotoInstruction[Variants * CacheSize];255 256        private readonly bool _hasResult;257 258        // TODO: We can remember hasValue in label and look it up when calculating stack balance. That would save some cache.259        private readonly bool _hasValue;260 261        // The values should technically be Consumed = 1, Produced = 1 for gotos that target a label whose continuation depth262        // is different from the current continuation depth. This is because we will consume one continuation from the _continuations263        // and at meantime produce a new _pendingContinuation. However, in case of forward gotos, we don't not know that is the264        // case until the label is emitted. By then the consumed and produced stack information is useless.265        // The important thing here is that the stack balance is 0.266        public override int ConsumedContinuations { get { return 0; } }267 268        public override int ProducedContinuations { get { return 0; } }269 270        public override int ConsumedStack271        {272            get { return _hasValue ? 1 : 0; }273        }274 275        public override int ProducedStack276        {277            get { return _hasResult ? 1 : 0; }278        }279 280        private GotoInstruction(int targetIndex, bool hasResult, bool hasValue)281            : base(targetIndex)282        {283            _hasResult = hasResult;284            _hasValue = hasValue;285        }286 287        internal static GotoInstruction Create(int labelIndex, bool hasResult, bool hasValue)288        {289            if (labelIndex < CacheSize)290            {291                var index = Variants * labelIndex | (hasResult ? 2 : 0) | (hasValue ? 1 : 0);292                return s_cache[index] ?? (s_cache[index] = new GotoInstruction(labelIndex, hasResult, hasValue));293            }294 295            return new GotoInstruction(labelIndex, hasResult, hasValue);296        }297 298        public override int Run(InterpretedFrame frame)299        {300            // goto the target label or the current finally continuation:301            return frame.Goto(_labelIndex, _hasValue ? frame.Pop() : Interpreter.NoValue, gotoExceptionHandler: false);302        }303    }304 305    internal sealed class EnterTryCatchFinallyInstruction : IndexedBranchInstruction306    {307        private readonly bool _hasFinally = false;308        private TryCatchFinallyHandler _tryHandler;309 310        internal void SetTryHandler(TryCatchFinallyHandler tryHandler)311        {312            Debug.Assert(_tryHandler == null && tryHandler != null, "the tryHandler can be set only once");313            _tryHandler = tryHandler;314        }315 316        public override int ProducedContinuations { get { return _hasFinally ? 1 : 0; } }317 318        private EnterTryCatchFinallyInstruction(int targetIndex, bool hasFinally)319            : base(targetIndex)320        {321            _hasFinally = hasFinally;322        }323 324        internal static EnterTryCatchFinallyInstruction CreateTryFinally(int labelIndex)325        {326            return new EnterTryCatchFinallyInstruction(labelIndex, true);327        }328 329        internal static EnterTryCatchFinallyInstruction CreateTryCatch()330        {331            return new EnterTryCatchFinallyInstruction(UnknownInstrIndex, false);332        }333 334        public override int Run(InterpretedFrame frame)335        {336            Debug.Assert(_tryHandler != null, "the tryHandler must be set already");337 338            if (_hasFinally)339            {340                // Push finally.341                frame.PushContinuation(_labelIndex);342            }343 344            int prevInstrIndex = frame.InstructionIndex;345            frame.InstructionIndex++;346 347            // Start to run the try/catch/finally blocks348            var instructions = frame.Interpreter.Instructions.Instructions;349            try350            {351                // run the try block352                int index = frame.InstructionIndex;353                while (index >= _tryHandler.TryStartIndex && index < _tryHandler.TryEndIndex)354                {355                    index += instructions[index].Run(frame);356                    frame.InstructionIndex = index;357                }358 359                // we finish the try block and is about to jump out of the try/catch blocks360                if (index == _tryHandler.GotoEndTargetIndex)361                {362                    // run the 'Goto' that jumps out of the try/catch/finally blocks363                    Debug.Assert(instructions[index] is GotoInstruction, "should be the 'Goto' instruction that jumps out the try/catch/finally");364                    frame.InstructionIndex += instructions[index].Run(frame);365                }366            }367            catch (RethrowException)368            {369                // a rethrow instruction in the try handler gets to run370                throw;371            }372            catch (Exception exception)373            {374                frame.SaveTraceToException(exception);375                // rethrow if there is no catch blocks defined for this try block376                if (!_tryHandler.IsCatchBlockExist) { throw; }377 378                // Search for the best handler in the TryCatchFinally block. If no suitable handler is found, rethrow379                ExceptionHandler exHandler;380                frame.InstructionIndex += _tryHandler.GotoHandler(frame, exception, out exHandler);381                if (exHandler == null) { throw; }382                bool rethrow = false;383                try384                {385                    // run the catch block386                    int index = frame.InstructionIndex;387                    while (index >= exHandler.HandlerStartIndex && index < exHandler.HandlerEndIndex)388                    {389                        index += instructions[index].Run(frame);390                        frame.InstructionIndex = index;391                    }392 393                    // we finish the catch block and is about to jump out of the try/catch blocks394                    if (index == _tryHandler.GotoEndTargetIndex)395                    {396                        // run the 'Goto' that jumps out of the try/catch/finally blocks397                        Debug.Assert(instructions[index] is GotoInstruction, "should be the 'Goto' instruction that jumps out the try/catch/finally");398                        frame.InstructionIndex += instructions[index].Run(frame);399                    }400                }401                catch (RethrowException)402                {403                    // a rethrow instruction in a catch block gets to run404                    rethrow = true;405                }406 407                if (rethrow) { throw; }408            }409            finally410            {411                if (_tryHandler.IsFinallyBlockExist)412                {413                    // We get to the finally block in two paths:414                    //  1. Jump from the try/catch blocks. This includes two sub-routes:415                    //        a. 'Goto' instruction in the middle of try/catch block416                    //        b. try/catch block runs to its end. Then the 'Goto(end)' will be trigger to jump out of the try/catch block417                    //  2. Exception thrown from the try/catch blocks418                    // In the first path, the continuation mechanism works and frame.InstructionIndex will be updated to point to the first instruction of the finally block419                    // In the second path, the continuation mechanism is not involved and frame.InstructionIndex is not updated420#if DEBUG421                    bool isFromJump = frame.IsJumpHappened();422                    Debug.Assert(!isFromJump || _tryHandler.FinallyStartIndex == frame.InstructionIndex, "we should already jump to the first instruction of the finally");423#endif424                    // run the finally block425                    // we cannot jump out of the finally block, and we cannot have an immediate rethrow in it426                    int index = frame.InstructionIndex = _tryHandler.FinallyStartIndex;427                    while (index >= _tryHandler.FinallyStartIndex && index < _tryHandler.FinallyEndIndex)428                    {429                        index += instructions[index].Run(frame);430                        frame.InstructionIndex = index;431                    }432                }433            }434 435            return frame.InstructionIndex - prevInstrIndex;436        }437 438        public override string InstructionName439        {440            get { return _hasFinally ? "EnterTryFinally" : "EnterTryCatch"; }441        }442 443        public override string ToString()444        {445            return _hasFinally ? "EnterTryFinally[" + _labelIndex + "]" : "EnterTryCatch";446        }447    }448 449    /// <summary>450    /// The first instruction of finally block.451    /// </summary>452    internal sealed class EnterFinallyInstruction : IndexedBranchInstruction453    {454        private static readonly EnterFinallyInstruction[] s_cache = new EnterFinallyInstruction[CacheSize];455 456        public override int ProducedStack { get { return 2; } }457 458        public override int ConsumedContinuations { get { return 1; } }459 460        private EnterFinallyInstruction(int labelIndex)461            : base(labelIndex)462        {463        }464 465        internal static EnterFinallyInstruction Create(int labelIndex)466        {467            if (labelIndex < CacheSize)468            {469                return s_cache[labelIndex] ?? (s_cache[labelIndex] = new EnterFinallyInstruction(labelIndex));470            }471 472            return new EnterFinallyInstruction(labelIndex);473        }474 475        public override int Run(InterpretedFrame frame)476        {477            // If _pendingContinuation == -1 then we were getting into the finally block because an exception was thrown478            //      in this case we need to set the stack depth479            // Else we were getting into this finally block from a 'Goto' jump, and the stack depth is already set properly480            if (!frame.IsJumpHappened())481            {482                frame.SetStackDepth(GetLabel(frame).StackDepth);483            }484 485            frame.PushPendingContinuation();486            frame.RemoveContinuation();487            return 1;488        }489    }490 491    /// <summary>492    /// The last instruction of finally block.493    /// </summary>494    internal sealed class LeaveFinallyInstruction : Instruction495    {496        internal static readonly Instruction Instance = new LeaveFinallyInstruction();497 498        public override int ConsumedStack { get { return 2; } }499 500        private LeaveFinallyInstruction()501        {502        }503 504        public override int Run(InterpretedFrame frame)505        {506            frame.PopPendingContinuation();507 508            // If _pendingContinuation == -1 then we were getting into the finally block because an exception was thrown509            // In this case we just return 1, and the real instruction index will be calculated by GotoHandler later510            if (!frame.IsJumpHappened()) { return 1; }511            // jump to goto target or to the next finally:512            return frame.YieldToPendingContinuation();513        }514    }515 516    // no-op: we need this just to balance the stack depth.517    internal sealed class EnterExceptionHandlerInstruction : Instruction518    {519        internal static readonly EnterExceptionHandlerInstruction Void = new EnterExceptionHandlerInstruction(false);520        internal static readonly EnterExceptionHandlerInstruction NonVoid = new EnterExceptionHandlerInstruction(true);521 522        // True if try-expression is non-void.523        private readonly bool _hasValue;524 525        private EnterExceptionHandlerInstruction(bool hasValue)526        {527            _hasValue = hasValue;528        }529 530        // If an exception is throws in try-body the expression result of try-body is not evaluated and loaded to the stack.531        // So the stack doesn't contain the try-body's value when we start executing the handler.532        // However, while emitting instructions try block falls thru the catch block with a value on stack.533        // We need to declare it consumed so that the stack state upon entry to the handler corresponds to the real534        // stack depth after throw jumped to this catch block.535        public override int ConsumedStack { get { return _hasValue ? 1 : 0; } }536 537        // A variable storing the current exception is pushed to the stack by exception handling.538        // Catch handlers: The value is immediately popped and stored into a local.539        // Fault handlers: The value is kept on stack during fault handler evaluation.540        public override int ProducedStack { get { return 1; } }541 542        public override int Run(InterpretedFrame frame)543        {544            // nop (the exception value is pushed by the interpreter in HandleCatch)545            return 1;546        }547    }548 549    /// <summary>550    /// The last instruction of a catch exception handler.551    /// </summary>552    internal sealed class LeaveExceptionHandlerInstruction : IndexedBranchInstruction553    {554        private static readonly LeaveExceptionHandlerInstruction[] s_cache = new LeaveExceptionHandlerInstruction[2 * CacheSize];555 556        private readonly bool _hasValue;557 558        // The catch block yields a value if the body is non-void. This value is left on the stack.559        public override int ConsumedStack560        {561            get { return _hasValue ? 1 : 0; }562        }563 564        public override int ProducedStack565        {566            get { return _hasValue ? 1 : 0; }567        }568 569        private LeaveExceptionHandlerInstruction(int labelIndex, bool hasValue)570            : base(labelIndex)571        {572            _hasValue = hasValue;573        }574 575        internal static LeaveExceptionHandlerInstruction Create(int labelIndex, bool hasValue)576        {577            if (labelIndex < CacheSize)578            {579                int index = (2 * labelIndex) | (hasValue ? 1 : 0);580                return s_cache[index] ?? (s_cache[index] = new LeaveExceptionHandlerInstruction(labelIndex, hasValue));581            }582 583            return new LeaveExceptionHandlerInstruction(labelIndex, hasValue);584        }585 586        public override int Run(InterpretedFrame frame)587        {588            return GetLabel(frame).Index - frame.InstructionIndex;589        }590    }591 592    /// <summary>593    /// The last instruction of a fault exception handler.594    /// </summary>595    internal sealed class LeaveFaultInstruction : Instruction596    {597        internal static readonly Instruction NonVoid = new LeaveFaultInstruction(true);598        internal static readonly Instruction Void = new LeaveFaultInstruction(false);599 600        private readonly bool _hasValue;601 602        // The fault block has a value if the body is non-void, but the value is never used.603        // We compile the body of a fault block as void.604        // However, we keep the exception object that was pushed upon entering the fault block on the stack during execution of the block605        // and pop it at the end.606        public override int ConsumedStack607        {608            get { return 1; }609        }610 611        // While emitting instructions a non-void try-fault expression is expected to produce a value.612        public override int ProducedStack613        {614            get { return _hasValue ? 1 : 0; }615        }616 617        private LeaveFaultInstruction(bool hasValue)618        {619            _hasValue = hasValue;620        }621 622        public override int Run(InterpretedFrame frame)623        {624            object exception = frame.Pop();625            throw new RethrowException();626        }627    }628 629    internal sealed class ThrowInstruction : Instruction630    {631        internal static readonly ThrowInstruction Throw = new ThrowInstruction(true, false);632        internal static readonly ThrowInstruction VoidThrow = new ThrowInstruction(false, false);633        internal static readonly ThrowInstruction Rethrow = new ThrowInstruction(true, true);634        internal static readonly ThrowInstruction VoidRethrow = new ThrowInstruction(false, true);635 636        private readonly bool _hasResult, _rethrow;637 638        private ThrowInstruction(bool hasResult, bool isRethrow)639        {640            _hasResult = hasResult;641            _rethrow = isRethrow;642        }643 644        public override int ProducedStack645        {646            get { return _hasResult ? 1 : 0; }647        }648 649        public override int ConsumedStack650        {651            get652            {653                return 1;654            }655        }656 657        public override int Run(InterpretedFrame frame)658        {659            var ex = (Exception)frame.Pop();660            if (_rethrow)661            {662                // ExceptionHandler handler;663                // return frame.Interpreter.GotoHandler(frame, ex, out handler);664                throw new RethrowException();665            }666 667            throw ex;668        }669    }670 671    internal sealed class SwitchInstruction : Instruction672    {673        private readonly Dictionary<int, int> _cases;674 675        internal SwitchInstruction(Dictionary<int, int> cases)676        {677            Assert.NotNull(cases);678            _cases = cases;679        }680 681        public override int ConsumedStack { get { return 1; } }682 683        public override int ProducedStack { get { return 0; } }684 685        public override int Run(InterpretedFrame frame)686        {687            int target;688            return _cases.TryGetValue((int)frame.Pop(), out target) ? target : 1;689        }690    }691 692    internal sealed class EnterLoopInstruction : Instruction693    {694        private readonly int _instructionIndex;695        private Dictionary<ParameterExpression, LocalVariable> _variables;696        private Dictionary<ParameterExpression, LocalVariable> _closureVariables;697        private PowerShellLoopExpression _loop;698        private int _loopEnd;699        private int _compilationThreshold;700 701        internal EnterLoopInstruction(PowerShellLoopExpression loop, LocalVariables locals, int compilationThreshold, int instructionIndex)702        {703            _loop = loop;704            _variables = locals.CopyLocals();705            _closureVariables = locals.ClosureVariables;706            _compilationThreshold = compilationThreshold;707            _instructionIndex = instructionIndex;708        }709 710        internal void FinishLoop(int loopEnd)711        {712            _loopEnd = loopEnd;713        }714 715        public override int Run(InterpretedFrame frame)716        {717            // Don't lock here, it's a frequently hit path.718            //719            // There could be multiple threads racing, but that is okay.720            // Two bad things can happen:721            //   * We miss decrements (some thread sets the counter forward)722            //   * We might enter the "if" branch more than once.723            //724            // The first is okay, it just means we take longer to compile.725            // The second we explicitly guard against inside of Compile().726            //727            // We can't miss 0. The first thread that writes -1 must have read 0 and hence start compilation.728            if (unchecked(_compilationThreshold--) == 0)729            {730                if (frame.Interpreter.CompileSynchronously)731                {732                    Compile(frame);733                }734                else735                {736                    // Kick off the compile on another thread so this one can keep going737                    ThreadPool.QueueUserWorkItem(Compile, frame);738                }739            }740 741            return 1;742        }743 744        private bool Compiled745        {746            get { return _loop == null; }747        }748 749        private void Compile(object frameObj)750        {751            if (Compiled)752            {753                return;754            }755 756            lock (this)757            {758                if (Compiled)759                {760                    return;761                }762 763                // PerfTrack.NoteEvent(PerfTrack.Categories.Compiler, "Interpreted loop compiled");764 765                InterpretedFrame frame = (InterpretedFrame)frameObj;766                var compiler = new LoopCompiler(_loop, frame.Interpreter.LabelMapping, _variables, _closureVariables, _instructionIndex, _loopEnd);767                var instructions = frame.Interpreter.Instructions.Instructions;768 769                // replace this instruction with an optimized one:770                instructions[_instructionIndex] = new CompiledLoopInstruction(compiler.CreateDelegate());771 772                // invalidate this instruction, some threads may still hold on it:773                _loop = null;774                _variables = null;775                _closureVariables = null;776            }777        }778    }779 780    internal sealed class CompiledLoopInstruction : Instruction781    {782        private readonly LoopFunc _compiledLoop;783 784        public CompiledLoopInstruction(LoopFunc compiledLoop)785        {786            Assert.NotNull(compiledLoop);787            _compiledLoop = compiledLoop;788        }789 790        public override int Run(InterpretedFrame frame)791        {792            return _compiledLoop(frame.Data, frame.Closure, frame);793        }794    }795}796