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.Globalization;18using System.Linq;19using System.Linq.Expressions;20#else21using Microsoft.Scripting.Ast;22#endif23using System.Collections.Generic;24using System.Diagnostics;25 26namespace System.Management.Automation.Interpreter27{28    /// <summary>29    /// Contains compiler state corresponding to a LabelTarget30    /// See also LabelScopeInfo.31    /// </summary>32    internal sealed class LabelInfo33    {34        // The tree node representing this label35        private readonly LabelTarget _node;36 37        // The BranchLabel label, will be mutated if Node is redefined38        private BranchLabel _label;39 40        // The blocks where this label is defined. If it has more than one item,41        // the blocks can't be jumped to except from a child block42        // If there's only 1 block (the common case) it's stored here, if there's multiple blocks it's stored43        // as a HashSet<LabelScopeInfo>44        private object _definitions;45 46        // Blocks that jump to this block47        private readonly List<LabelScopeInfo> _references = new List<LabelScopeInfo>();48 49        // True if at least one jump is across blocks50        // If we have any jump across blocks to this label, then the51        // LabelTarget can only be defined in one place52        private bool _acrossBlockJump;53 54        internal LabelInfo(LabelTarget node)55        {56            _node = node;57        }58 59        internal BranchLabel GetLabel(LightCompiler compiler)60        {61            EnsureLabel(compiler);62            return _label;63        }64 65        internal void Reference(LabelScopeInfo block)66        {67            _references.Add(block);68            if (HasDefinitions)69            {70                ValidateJump(block);71            }72        }73 74        internal void Define(LabelScopeInfo block)75        {76            // Prevent the label from being shadowed, which enforces cleaner77            // trees. Also we depend on this for simplicity (keeping only one78            // active IL Label per LabelInfo)79            for (LabelScopeInfo j = block; j != null; j = j.Parent)80            {81                if (j.ContainsTarget(_node))82                {83                    throw new InvalidOperationException(string.Create(CultureInfo.InvariantCulture, $"Label target already defined: {_node.Name}"));84                }85            }86 87            AddDefinition(block);88            block.AddLabelInfo(_node, this);89 90            // Once defined, validate all jumps91            if (HasDefinitions && !HasMultipleDefinitions)92            {93                foreach (var r in _references)94                {95                    ValidateJump(r);96                }97            }98            else99            {100                // Was just redefined, if we had any across block jumps, they're101                // now invalid102                if (_acrossBlockJump)103                {104                    throw new InvalidOperationException("Ambiguous jump");105                }106                // For local jumps, we need a new IL label107                // This is okay because:108                //   1. no across block jumps have been made or will be made109                //   2. we don't allow the label to be shadowed110                _label = null;111            }112        }113 114        private void ValidateJump(LabelScopeInfo reference)115        {116            // look for a simple jump out117            for (LabelScopeInfo j = reference; j != null; j = j.Parent)118            {119                if (DefinedIn(j))120                {121                    // found it, jump is valid!122                    return;123                }124 125                if (j.Kind == LabelScopeKind.Filter)126                {127                    break;128                }129            }130 131            _acrossBlockJump = true;132 133            if (HasMultipleDefinitions)134            {135                throw new InvalidOperationException(string.Create(CultureInfo.InvariantCulture, $"Ambiguous jump {_node.Name}"));136            }137 138            // We didn't find an outward jump. Look for a jump across blocks139            LabelScopeInfo def = FirstDefinition();140            LabelScopeInfo common = CommonNode(def, reference, static b => b.Parent);141 142            // Validate that we aren't jumping across a finally143            for (LabelScopeInfo j = reference; j != common; j = j.Parent)144            {145                if (j.Kind == LabelScopeKind.Filter)146                {147                    throw new InvalidOperationException("Control cannot leave filter test");148                }149            }150 151            // Validate that we aren't jumping into a catch or an expression152            for (LabelScopeInfo j = def; j != common; j = j.Parent)153            {154                if (!j.CanJumpInto)155                {156                    if (j.Kind == LabelScopeKind.Expression)157                    {158                        throw new InvalidOperationException("Control cannot enter an expression");159                    }160                    else161                    {162                        throw new InvalidOperationException("Control cannot enter try");163                    }164                }165            }166        }167 168        internal void ValidateFinish()169        {170            // Make sure that if this label was jumped to, it is also defined171            if (_references.Count > 0 && !HasDefinitions)172            {173                throw new InvalidOperationException("label target undefined");174            }175        }176 177        private void EnsureLabel(LightCompiler compiler)178        {179            _label ??= compiler.Instructions.MakeLabel();180        }181 182        private bool DefinedIn(LabelScopeInfo scope)183        {184            if (_definitions == scope)185            {186                return true;187            }188 189            HashSet<LabelScopeInfo> definitions = _definitions as HashSet<LabelScopeInfo>;190            if (definitions != null)191            {192                return definitions.Contains(scope);193            }194 195            return false;196        }197 198        private bool HasDefinitions199        {200            get201            {202                return _definitions != null;203            }204        }205 206        private LabelScopeInfo FirstDefinition()207        {208            LabelScopeInfo scope = _definitions as LabelScopeInfo;209            if (scope != null)210            {211                return scope;212            }213 214            return ((HashSet<LabelScopeInfo>)_definitions).First();215        }216 217        private void AddDefinition(LabelScopeInfo scope)218        {219            if (_definitions == null)220            {221                _definitions = scope;222            }223            else224            {225                HashSet<LabelScopeInfo> set = _definitions as HashSet<LabelScopeInfo>;226                if (set == null)227                {228                    _definitions = set = new HashSet<LabelScopeInfo>() { (LabelScopeInfo)_definitions };229                }230 231                set.Add(scope);232            }233        }234 235        private bool HasMultipleDefinitions236        {237            get238            {239                return _definitions is HashSet<LabelScopeInfo>;240            }241        }242 243        internal static T CommonNode<T>(T first, T second, Func<T, T> parent) where T : class244        {245            var cmp = EqualityComparer<T>.Default;246            if (cmp.Equals(first, second))247            {248                return first;249            }250 251            var set = new HashSet<T>(cmp);252            for (T t = first; t != null; t = parent(t))253            {254                set.Add(t);255            }256 257            for (T t = second; t != null; t = parent(t))258            {259                if (set.Contains(t))260                {261                    return t;262                }263            }264 265            return null;266        }267    }268 269    internal enum LabelScopeKind270    {271        // any "statement like" node that can be jumped into272        Statement,273 274        // these correspond to the node of the same name275        Block,276        Switch,277        Lambda,278        Try,279 280        // these correspond to the part of the try block we're in281        Catch,282        Finally,283        Filter,284 285        // the catch-all value for any other expression type286        // (means we can't jump into it)287        Expression,288    }289 290    //291    // Tracks scoping information for LabelTargets. Logically corresponds to a292    // "label scope". Even though we have arbitrary goto support, we still need293    // to track what kinds of nodes that gotos are jumping through, both to294    // emit property IL ("leave" out of a try block), and for validation, and295    // to allow labels to be duplicated in the tree, as long as the jumps are296    // considered "up only" jumps.297    //298    // We create one of these for every Expression that can be jumped into, as299    // well as creating them for the first expression we can't jump into. The300    // "Kind" property indicates what kind of scope this is.301    //302    internal sealed class LabelScopeInfo303    {304        private HybridReferenceDictionary<LabelTarget, LabelInfo> _labels; // lazily allocated, we typically use this only once every 6th-7th block305        internal readonly LabelScopeKind Kind;306        internal readonly LabelScopeInfo Parent;307 308        internal LabelScopeInfo(LabelScopeInfo parent, LabelScopeKind kind)309        {310            Parent = parent;311            Kind = kind;312        }313 314        /// <summary>315        /// Returns true if we can jump into this node.316        /// </summary>317        internal bool CanJumpInto318        {319            get320            {321                switch (Kind)322                {323                    case LabelScopeKind.Block:324                    case LabelScopeKind.Statement:325                    case LabelScopeKind.Switch:326                    case LabelScopeKind.Lambda:327                        return true;328                }329 330                return false;331            }332        }333 334        internal bool ContainsTarget(LabelTarget target)335        {336            if (_labels == null)337            {338                return false;339            }340 341            return _labels.ContainsKey(target);342        }343 344        internal bool TryGetLabelInfo(LabelTarget target, out LabelInfo info)345        {346            if (_labels == null)347            {348                info = null;349                return false;350            }351 352            return _labels.TryGetValue(target, out info);353        }354 355        internal void AddLabelInfo(LabelTarget target, LabelInfo info)356        {357            Debug.Assert(CanJumpInto);358 359            _labels ??= new HybridReferenceDictionary<LabelTarget, LabelInfo>();360 361            _labels[target] = info;362        }363    }364}365