FunctionCode.cs

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the Apache 2.0 License.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq.Expressions;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Threading;

using IronPython.Compiler;
using IronPython.Runtime.Operations;
using IronPython.Runtime.Types;

using Microsoft.Scripting;
using Microsoft.Scripting.Ast;
using Microsoft.Scripting.Debugging.CompilerServices;
using Microsoft.Scripting.Generation;
using Microsoft.Scripting.Interpreter;
using Microsoft.Scripting.Runtime;
using Microsoft.Scripting.Utils;

namespace IronPython.Runtime {
    /// <summary>
    /// Represents a piece of code.  This can reference either a CompiledCode
    /// object or a Function.   The user can explicitly call FunctionCode by
    /// passing it into exec or eval.
    /// </summary>
    [PythonType("code")]
    [DebuggerDisplay("{co_name}, FileName = {co_filename}")]
    public class FunctionCode : IExpressionSerializable, ICodeFormattable {
        internal Delegate _normalDelegate;                          // the normal delegate - this can be a compiled or interpreted delegate.
        private readonly Compiler.Ast.ScopeStatement _lambda;       // the original DLR lambda that contains the code
        internal readonly string _initialDoc;                       // the initial doc string
        private readonly int _localCount;                           // the number of local variables in the code
        private bool _compilingLight;                               // true if we're compiling for light exceptions
        private int _exceptionCount;

        // debugging/tracing support
        private LambdaExpression _tracingLambda;                    // the transformed lambda used for tracing/debugging
        internal Delegate _tracingDelegate;                         // the delegate used for tracing/debugging, if one has been created.  This can be interpreted or compiled.

        /// <summary>
        /// This is both the lock that is held while enumerating the threads or updating the thread accounting
        /// information.  It's also a marker CodeList which is put in place when we are enumerating the thread
        /// list and all additions need to block.
        /// 
        /// This lock is also acquired whenever we need to calculate how a function's delegate should be created 
        /// so that we don't race against sys.settrace/sys.setprofile.
        /// </summary>
        private static readonly CodeList _CodeCreateAndUpdateDelegateLock = new CodeList();

        /// <summary>
        /// Constructor used to create a FunctionCode for code that's been serialized to disk.  
        /// 
        /// Code constructed this way cannot be interpreted or debugged using sys.settrace/sys.setprofile.
        /// 
        /// Function codes created this way do support recursion enforcement and are therefore registered in the global function code registry.
        /// </summary>
        internal FunctionCode(PythonContext context, Delegate code, Compiler.Ast.ScopeStatement scope, string documentation, int localCount) {
            _normalDelegate = code;
            _lambda = scope;
            co_argcount = scope.ArgCount;
            co_kwonlyargcount = scope.KwOnlyArgCount;
            _initialDoc = documentation;

            // need to take this lock to ensure sys.settrace/sys.setprofile is not actively changing
            lock (_CodeCreateAndUpdateDelegateLock) {
                SetTarget(AddRecursionCheck(context, code));
            }

            RegisterFunctionCode(context);
        }

        /// <summary>
        /// Constructor to create a FunctionCode at runtime.
        /// 
        /// Code constructed this way supports both being interpreted and debugged.  When necessary the code will
        /// be re-compiled or re-interpreted for that specific purpose.
        /// 
        /// Function codes created this way do support recursion enforcement and are therefore registered in the global function code registry.
        /// 
        /// the initial delegate provided here should NOT be the actual code.  It should always be a delegate which updates our Target lazily.
        /// </summary>
        internal FunctionCode(PythonContext context, Delegate initialDelegate, Compiler.Ast.ScopeStatement scope, string documentation, bool? tracing, bool register) {
            _lambda = scope;
            SetTarget(initialDelegate);
            _initialDoc = documentation;
            _localCount = scope.Variables == null ? 0 : scope.Variables.Count;
            co_argcount = scope.ArgCount;
            co_kwonlyargcount = scope.KwOnlyArgCount;

            if (tracing.HasValue) {
                if (tracing.Value) {
                    _tracingDelegate = initialDelegate;
                } else {
                    _normalDelegate = initialDelegate;
                }
            }

            if (register) {
                RegisterFunctionCode(context);
            }
        }

        private static PythonTuple SymbolListToTuple(IList<string> vars) {
            if (vars != null && vars.Count != 0) {
                object[] tupleData = new object[vars.Count];
                for (int i = 0; i < vars.Count; i++) {
                    tupleData[i] = vars[i];
                }
                return PythonTuple.MakeTuple(tupleData);
            } else {
                return PythonTuple.EMPTY;
            }
        }

        private static PythonTuple StringArrayToTuple(string[] closureVars) {
            if (closureVars != null && closureVars.Length != 0) {
                return PythonTuple.MakeTuple((object[])closureVars);
            } else {
                return PythonTuple.EMPTY;
            }
        }

        /// <summary>
        /// Registers the current function code in our global weak list of all function codes.
        /// 
        /// The weak list can be enumerated with GetAllCode().
        /// 
        /// Ultimately there are 3 types of threads we care about races with:
        ///     1. Other threads which are registering function codes
        ///     2. Threads calling sys.settrace which require the world to stop and get updated
        ///     3. Threads running cleanup (thread pool thread, or call to gc.collect).
        ///     
        /// The 1st two must have perfect synchronization.  We cannot have a thread registering
        /// a new function which another thread is trying to update all of the functions in the world.  Doing
        /// so would mean we could miss adding tracing to a thread.   
        /// 
        /// But the cleanup thread can run in parallel to either registrying or sys.settrace.  The only
        /// thing it needs to take a lock for is updating our accounting information about the
        /// number of code objects are alive.
        /// </summary>
        private void RegisterFunctionCode(PythonContext context) {
            if (_lambda == null) {
                return;
            }

            WeakReference codeRef = new WeakReference(this);
            CodeList prevCode;
            lock (_CodeCreateAndUpdateDelegateLock) {
                Debug.Assert(context._allCodes != _CodeCreateAndUpdateDelegateLock);
                // we do an interlocked operation here because this can run in parallel w/ the CodeCleanup thread.  The
                // lock only prevents us from running in parallel w/ an update to all of the functions in the world which
                // needs to be synchronized.
                do {
                    prevCode = context._allCodes;
                } while (Interlocked.CompareExchange(ref context._allCodes, new CodeList(codeRef, prevCode), prevCode) != prevCode);

                if (context._codeCount++ == context._nextCodeCleanup) {
                    // run cleanup of codes on another thread
                    CleanFunctionCodes(context, false);
                }
            }
        }

        internal static void CleanFunctionCodes(PythonContext context, bool synchronous) {
            if (synchronous) {
                CodeCleanup(context);
            } else {
                ThreadPool.QueueUserWorkItem(CodeCleanup, context);
            }
        }

        internal void SetTarget(Delegate target) {
            Target = LightThrowTarget = target;
        }

        internal void LightThrowCompile(CodeContext/*!*/ context) {
            if (++_exceptionCount > 20) {
                if (!_compilingLight && (object)Target == (object)LightThrowTarget) {
                    _compilingLight = true;
                    if (!IsOnDiskCode) {
                        ThreadPool.QueueUserWorkItem(x => {
                            // on mono if the runtime is shutting down, this can throw an InvalidOperationException
                            try {
                                var pyCtx = context.LanguageContext;

                                bool enableTracing;
                                lock (pyCtx._codeUpdateLock) {
                                    enableTracing = context.LanguageContext.EnableTracing;
                                }

                                Delegate target = enableTracing
                                    ? ((LambdaExpression)LightExceptions.Rewrite(
                                        GetGeneratorOrNormalLambdaTracing(pyCtx).Reduce())).Compile()
                                    : ((LambdaExpression)LightExceptions.Rewrite(GetGeneratorOrNormalLambda().Reduce()))
                                    .Compile();

                                lock (pyCtx._codeUpdateLock) {
                                    if (context.LanguageContext.EnableTracing == enableTracing) {
                                        LightThrowTarget = target;
                                    }
                                }
                            } catch (InvalidOperationException ex) {
                                // The InvalidOperationException is thrown with an empty message
                                if (!string.IsNullOrEmpty(ex.Message)) {
                                    throw;
                                }
                            }
                        });
                    }
                }
            }
        }

        private bool IsOnDiskCode {
            get {
                if (_lambda is Compiler.Ast.SerializedScopeStatement) {
                    return true;
                }

                if (_lambda is Compiler.Ast.PythonAst) {
                    return ((Compiler.Ast.PythonAst)_lambda).OnDiskProxy;
                }
                return false;
            }
        }

        /// <summary>
        /// Enumerates all function codes for updating the current type of targets we generate.
        /// 
        /// While enumerating we hold a lock so that users cannot change sys.settrace/sys.setprofile
        /// until the lock is released.
        /// </summary>
        private static IEnumerable<FunctionCode> GetAllCode(PythonContext context) {
            // only a single thread can enumerate the current FunctionCodes at a time.
            lock (_CodeCreateAndUpdateDelegateLock) {
                CodeList curCodeList = Interlocked.Exchange(ref context._allCodes, _CodeCreateAndUpdateDelegateLock);
                Debug.Assert(curCodeList != _CodeCreateAndUpdateDelegateLock);

                CodeList initialCode = curCodeList;

                try {
                    while (curCodeList != null) {
                        WeakReference codeRef = curCodeList.Code;
                        FunctionCode target = (FunctionCode)codeRef.Target;

                        if (target != null) {
                            yield return target;
                        }

                        curCodeList = curCodeList.Next;
                    }
                } finally {
                    Interlocked.Exchange(ref context._allCodes, initialCode);
                }
            }
        }

        internal static void UpdateAllCode(PythonContext context) {
            foreach (FunctionCode fc in GetAllCode(context)) {
                fc.UpdateDelegate(context, false);
            }
        }

        private static void CodeCleanup(object state) {
            PythonContext context = (PythonContext)state;

            // only allow 1 thread at a time to do cleanup (other threads can continue adding)
            lock (context._codeCleanupLock) {
                // the bulk of the work is in scanning the list, this proceeeds lock free
                int removed = 0, kept = 0;
                CodeList prev = null;
                CodeList cur = GetRootCodeNoUpdating(context);

                while (cur != null) {
                    if (!cur.Code.IsAlive) {
                        if (prev == null) {
                            if (Interlocked.CompareExchange(ref context._allCodes, cur.Next, cur) != cur) {
                                // someone else snuck in and added a new code entry, spin and try again.
                                cur = GetRootCodeNoUpdating(context);
                                continue;
                            }
                            cur = cur.Next;
                            removed++;
                            continue;
                        } else {
                            // remove from the linked list, we're the only one who can change this.
                            Debug.Assert(prev.Next == cur);
                            removed++;
                            cur = prev.Next = cur.Next;
                            continue;
                        }
                    } else {
                        kept++;
                    }
                    prev = cur;
                    cur = cur.Next;
                }

                // finally update our bookkeeping statistics which requires locking but is fast.
                lock (_CodeCreateAndUpdateDelegateLock) {
                    // calculate the next cleanup, we want each pass to remove ~50% of all entries
                    const double removalGoal = .50;

                    if (context._codeCount == 0) {
                        // somehow we would have had to queue a bunch of function codes, have 1 thread
                        // clean them up all up, and a 2nd queued thread waiting to clean them up as well.
                        // At the same time there would have to be no live functions defined which means
                        // we're executing top-level code which is causing this to happen.
                        context._nextCodeCleanup = 200;
                        return;
                    }
                    //Console.WriteLine("Removed {0} entries, {1} remain", removed, context._codeCount);

                    Debug.Assert(removed <= context._codeCount);
                    double pctRemoved = (double)removed / (double)context._codeCount; // % of code removed
                    double targetRatio = pctRemoved / removalGoal;                    // how we need to adjust our last goal

                    // update the total and next node cleanup
                    int newCount = Interlocked.Add(ref context._codeCount, -removed);
                    Debug.Assert(newCount >= 0);

                    // set the new target for cleanup
                    int nextCleanup = targetRatio != 0 ? newCount + (int)(context._nextCodeCleanup / targetRatio) : -1;
                    if (nextCleanup > 0) {
                        // we're making good progress, use the newly calculated next cleanup point
                        context._nextCodeCleanup = nextCleanup;
                    } else {
                        // none or very small amount cleaned up, just schedule a cleanup for sometime in the future.
                        context._nextCodeCleanup += 500;
                    }

                    Debug.Assert(context._nextCodeCleanup >= context._codeCount, String.Format("{0} vs {1} ({2})", context._nextCodeCleanup, context._codeCount, targetRatio));
                }
            }
        }

        private static CodeList GetRootCodeNoUpdating(PythonContext context) {
            CodeList cur = context._allCodes;
            if (cur == _CodeCreateAndUpdateDelegateLock) {
                lock (_CodeCreateAndUpdateDelegateLock) {
                    // wait until enumerating thread is done, but it's alright
                    // if we got cur and then an enumeration started (because we'll
                    // just clear entries out)
                    cur = context._allCodes;
                    Debug.Assert(cur != _CodeCreateAndUpdateDelegateLock);
                }
            }
            return cur;
        }

        public SourceSpan Span {
            [PythonHidden]
            get {
                return _lambda.Span;
            }
        }

        internal string[] ArgNames {
            get {
                return _lambda.ParameterNames;
            }
        }

        internal FunctionAttributes Flags {
            get {
                return _lambda.Flags;
            }
        }

        internal bool IsModule {
            get {
                return _lambda is Compiler.Ast.PythonAst;
            }
        }

        #region Public constructors

        /*
        /// <summary>
        /// Standard python siganture
        /// </summary>
        /// <param name="argcount"></param>
        /// <param name="nlocals"></param>
        /// <param name="stacksize"></param>
        /// <param name="flags"></param>
        /// <param name="codestring"></param>
        /// <param name="constants"></param>
        /// <param name="names"></param>
        /// <param name="varnames"></param>
        /// <param name="filename"></param>
        /// <param name="name"></param>
        /// <param name="firstlineno"></param>
        /// <param name="nlotab"></param>
        /// <param name="freevars"></param>
        /// <param name="callvars"></param>
        public FunctionCode(int argcount, int nlocals, int stacksize, int flags, string codestring, object constants, Tuple names, Tuple varnames, string filename, string name, int firstlineno, object nlotab, object freevars=null, object callvars=null) {
        }*/

        #endregion

        #region Public Python API Surface

        public PythonTuple co_varnames {
            get {
                return SymbolListToTuple(_lambda.GetVarNames());
            }
        }

        public int co_argcount { get; }

        public int co_kwonlyargcount { get; }

        /// <summary>
        /// Returns a list of variable names which are accessed from nested functions.
        /// </summary>
        public PythonTuple co_cellvars {
            get {
                return SymbolListToTuple(_lambda.CellVariables != null ? ArrayUtils.ToArray(_lambda.CellVariables) : null);
            }
        }

        /// <summary>
        /// Returns the byte code.  IronPython does not implement this and always
        /// returns an empty string for byte code.
        /// </summary>
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
        public object co_code {
            get {
                return String.Empty;
            }
        }

        /// <summary>
        /// Returns a list of constants used by the function.
        /// 
        /// The first constant is the doc string, or None if no doc string is provided.
        /// 
        /// IronPython currently does not include any other constants than the doc string.
        /// </summary>
        public PythonTuple co_consts {
            get {
                if (_initialDoc != null) {
                    return PythonTuple.MakeTuple(_initialDoc, null);
                }

                return PythonTuple.MakeTuple((object)null);
            }
        }

        /// <summary>
        /// Returns the filename that the code object was defined in.
        /// </summary>
        public string co_filename {
            get {
                return _lambda.Filename;
            }
        }

        /// <summary>
        /// Returns the 1st line number of the code object.
        /// </summary>
        public int co_firstlineno {
            get {
                return Span.Start.Line;
            }
        }

        /// <summary>
        /// Returns a set of flags for the function.
        /// 
        ///     0x04 is set if the function used *args
        ///     0x08 is set if the function used **args
        ///     0x20 is set if the function is a generator
        /// </summary>
        public int co_flags {
            get {
                return (int)Flags;
            }
        }

        /// <summary>
        /// Returns a list of free variables (variables accessed
        /// from an outer scope).  This does not include variables
        /// accessed in the global scope.
        /// </summary>
        public PythonTuple co_freevars {
            get {
                return SymbolListToTuple(_lambda.FreeVariables != null ? CollectionUtils.ConvertAll(_lambda.FreeVariables, x => x.Name) : null);
            }
        }

        /// <summary>
        /// Returns a mapping between byte code and line numbers.  IronPython does
        /// not implement this because byte code is not available.
        /// </summary>
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
        public object co_lnotab {
            get {
                throw PythonOps.NotImplementedError("");
            }
        }

        /// <summary>
        /// Returns the name of the code (function name, class name, or &lt;module&gt;).
        /// </summary>
        public string co_name {
            get {
                return _lambda.Name;
            }
        }

        /// <summary>
        /// Returns a list of global variable names accessed by the code.
        /// </summary>
        public PythonTuple co_names {
            get {
                return SymbolListToTuple(_lambda.GlobalVariables);
            }
        }

        /// <summary>
        /// Returns the number of local varaibles defined in the function.
        /// </summary>
        public object co_nlocals {
            get {
                return _localCount;
            }
        }

        /// <summary>
        /// Returns the stack size.  IronPython does not implement this
        /// because byte code is not supported.
        /// </summary>
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
        public object co_stacksize {
            get {
                throw PythonOps.NotImplementedError("");
            }
        }

        #endregion

        #region ICodeFormattable Members

        public string/*!*/ __repr__(CodeContext/*!*/ context) {
            return string.Format(
                "<code object {0} at {1}, file {2}, line {3}>",
                co_name,
                PythonOps.HexId(this),
                !string.IsNullOrEmpty(co_filename) ? string.Format("\"{0}\"", co_filename) : "???",
                co_firstlineno != 0 ? co_firstlineno : -1);
        }

        #endregion

        #region Internal API Surface

        internal LightLambdaExpression Code {
            get {
                return _lambda.GetLambda();
            }
        }

        internal Compiler.Ast.ScopeStatement PythonCode {
            get {
                return (Compiler.Ast.ScopeStatement)_lambda;
            }
        }

        /// <summary>
        /// The current target for the function.  This can change based upon adaptive compilation, recursion enforcement, and tracing.
        /// </summary>
        internal Delegate Target { get; private set; }

        internal Delegate LightThrowTarget { get; private set; }

        internal object Call(CodeContext/*!*/ context) {
            if (co_freevars != PythonTuple.EMPTY) {
                throw PythonOps.TypeError("cannot exec code object that contains free variables: {0}", co_freevars.__repr__(context));
            }

            // Target is read only once, since switching tracing on or off on another thread may change it at any time.
            Delegate target = Target;
            if (target == null || (target.GetMethodInfo()?.DeclaringType == typeof(PythonCallTargets))) {
                target = UpdateDelegate(context.LanguageContext, true);
            }

            if (target is Func<CodeContext, CodeContext> classTarget) {
                return classTarget(context);
            }

            if (target is LookupCompilationDelegate moduleCode) {
                return moduleCode(context, this);
            }

            if (target is Func<FunctionCode, object> optimizedModuleCode) {
                return optimizedModuleCode(this);
            }

            var func = new PythonFunction(context, this, null, [], null, null, new MutableTuple<object>());
            CallSite<Func<CallSite, CodeContext, PythonFunction, object>> site = context.LanguageContext.FunctionCallSite;
            return site.Target(site, context, func);
        }

        /// <summary>
        /// Creates a FunctionCode object for exec/eval/execfile'd/compile'd code.
        /// 
        /// The code is then executed in a specific CodeContext by calling the .Call method.
        /// 
        /// If the code is being used for compile (vs. exec/eval/execfile) then it needs to be
        /// registered in case our tracing mode changes.
        /// </summary>
        internal static FunctionCode FromSourceUnit(SourceUnit sourceUnit, PythonCompilerOptions options, bool register) {
            var code = PythonContext.CompilePythonCode(sourceUnit, options, ThrowingErrorSink.Default);
            if (sourceUnit.CodeProperties == ScriptCodeParseResult.Empty) {
                // source span is made up
                throw new SyntaxErrorException("unexpected EOF while parsing",
                    sourceUnit, new SourceSpan(new SourceLocation(0, 1, 1), new SourceLocation(0, 1, 1)), 0, Severity.Error);
            }
            return ((RunnableScriptCode)code).GetFunctionCode(register);
        }

        #endregion

        #region Private helper functions

        private void ExpandArgsTuple(List<string> names, PythonTuple toExpand) {
            for (int i = 0; i < toExpand.__len__(); i++) {
                if (toExpand[i] is PythonTuple) {
                    ExpandArgsTuple(names, toExpand[i] as PythonTuple);
                } else {
                    names.Add(toExpand[i] as string);
                }
            }
        }

        #endregion

        public override bool Equals(object obj) {
            // overridden because CPython defines this on code objects
            return base.Equals(obj);
        }

        public override int GetHashCode() {
            // overridden because CPython defines this on code objects
            return base.GetHashCode();
        }

        [return: MaybeNotImplemented]
        public NotImplementedType __gt__(CodeContext context, object other) => NotImplementedType.Value;

        [return: MaybeNotImplemented]
        public NotImplementedType __lt__(CodeContext context, object other) => NotImplementedType.Value;

        [return: MaybeNotImplemented]
        public NotImplementedType __ge__(CodeContext context, object other) => NotImplementedType.Value;

        [return: MaybeNotImplemented]
        public NotImplementedType __le__(CodeContext context, object other) => NotImplementedType.Value;

        /// <summary>
        /// Called the 1st time a function is invoked by our OriginalCallTarget* methods
        /// over in PythonCallTargets.  This computes the real delegate which needs to be
        /// created for the function.  Usually this means starting off interpretering.  It 
        /// also involves adding the wrapper function for recursion enforcement.
        /// 
        /// Because this can race against sys.settrace/setprofile we need to take our 
        /// _ThreadIsEnumeratingAndAccountingLock to ensure no one is actively changing all
        /// of the live functions.
        /// </summary>
        internal void LazyCompileFirstTarget(PythonFunction function) {
            lock (_CodeCreateAndUpdateDelegateLock) {
                UpdateDelegate(function.Context.LanguageContext, true);
            }
        }

        /// <summary>
        ///   Updates the delegate based upon current Python context settings for recursion enforcement and for tracing.
        /// </summary>
        /// <remarks>
        ///   With <paramref name="forceCreation"/> false, this is the update done by switching tracing on or off (<see cref="UpdateAllCode"/>)
        ///   and it always sets the target. With <paramref name="forceCreation"/> true, the update is not synchronized with such a switch,
        ///   so the delegate is set as the target only if the tracing mode it was built for is still current (see <see cref="PublishTarget"/>).
        /// </remarks>
        /// <returns>
        ///   The delegate for the tracing mode that was current when the update started, or null if only a lazy target was set (only when
        ///   <paramref name="forceCreation"/> is false). A caller that needs the delegate should use this result rather than read
        ///   <see cref="Target"/> again: another thread may change it at any time, e.g. by switching tracing on or off.
        /// </returns>
        internal Delegate UpdateDelegate(PythonContext context, bool forceCreation) {
            // Read only once: the delegate is built for this mode, even if another thread switches tracing on or off meanwhile.
            bool tracing = context.EnableTracing;
            Delegate finalTarget;

            if (tracing && _lambda != null) {
                if (_tracingLambda == null) {
                    if (!forceCreation) {
                        // the user just called sys.settrace(), don't force re-compilation of every method in the system.  Instead
                        // we'll just re-compile them as they're invoked.
                        SetLazyTarget();
                        return null;
                    }
                    _tracingLambda = GetGeneratorOrNormalLambdaTracing(context);
                }

                if (_tracingDelegate == null) {
                    _tracingDelegate = CompileLambda(_tracingLambda, new TargetUpdaterForCompilation(context, this).SetCompiledTargetTracing);
                }

                finalTarget = _tracingDelegate;
            } else {
                if (_normalDelegate == null) {
                    if (!forceCreation) {
                        // we cannot create the delegate when forceCreation is false because we hold the
                        // _CodeCreateAndUpdateDelegateLock and compiling the delegate may create a FunctionCode
                        // object which requires the lock.
                        SetLazyTarget();
                        return null;
                    }
                    _normalDelegate = CompileLambda(GetGeneratorOrNormalLambda(), new TargetUpdaterForCompilation(context, this).SetCompiledTarget);
                }

                finalTarget = _normalDelegate;
            }

            finalTarget = AddRecursionCheck(context, finalTarget);

            if (forceCreation) {
                PublishTarget(context, tracing, finalTarget);
            } else {
                SetTarget(finalTarget);
            }
            return finalTarget;
        }


        /// <summary>
        ///   Sets the target to a delegate built for the given tracing mode, unless that mode is no longer current.
        /// </summary>
        /// <remarks>
        ///   Used for updates that are not synchronized with switching tracing on or off (<see cref="UpdateAllCode"/>), so that a delegate
        ///   built for the previous mode cannot replace the target set for the new one. Such a delegate stays in its cache
        ///   (<see cref="_normalDelegate"/> or <see cref="_tracingDelegate"/>) and is used when the mode switches back.
        /// </remarks>
        /// <param name="tracing">
        ///   The tracing mode that <paramref name="target"/> was built for: true for the tracing delegate, false for the normal one.
        /// </param>
        /// <param name="target">
        ///   The delegate for the target, with the recursion check already added (see <see cref="AddRecursionCheck"/>).
        /// </param>
        internal void PublishTarget(PythonContext context, bool tracing, Delegate target) {
            if (context.EnableTracing != tracing) {
                return;
            }

            SetTarget(target);
            Thread.MemoryBarrier();
            while (context.EnableTracing != tracing) {
                tracing = context.EnableTracing;
                UpdateDelegate(context, forceCreation: false);
                Thread.MemoryBarrier();
            }
        }


        /// <summary>
        ///   Sets a target that creates the delegate for the current mode (tracing or not) when it is first needed.
        /// </summary>
        /// <remarks>
        ///   A function gets a call target that compiles its delegate on the first call. A class body cannot get one, since its
        ///   delegate has a different signature (<c>Func&lt;CodeContext, CodeContext&gt;</c>); it gets a null target instead, as when it
        ///   has not been compiled yet, which makes <see cref="PythonOps.MakeClass"/> compile it the next time the class is created.
        /// </remarks>
        private void SetLazyTarget() {
            if (_lambda is Compiler.Ast.ClassDefinition) {
                SetTarget(null);
            } else {
                PythonCallTargets.GetPythonTargetType(_lambda.ParameterNames.Length > PythonCallTargets.MaxArgs, _lambda.ParameterNames.Length, out Delegate target);
                SetTarget(target);
            }
        }

        /// <summary>
        /// Called to set the initial target delegate when the user has passed -X:Debug to enable
        /// .NET style debugging.
        /// </summary>
        internal void SetDebugTarget(PythonContext context, Delegate target) {
            _normalDelegate = target;

            PublishTarget(context, tracing: false, AddRecursionCheck(context, target));
        }

        /// <summary>
        /// Gets the LambdaExpression for tracing.  
        /// 
        /// If this is a generator function code then the lambda gets tranformed into the correct generator code.
        /// </summary>
        private LambdaExpression GetGeneratorOrNormalLambdaTracing(PythonContext context) {
            var debugProperties = new PythonDebuggingPayload(this);

            var debugInfo = new DebugLambdaInfo(
                null,           // IDebugCompilerSupport
                null,           // lambda alias
                false,          // optimize for leaf frames
                null,           // hidden variables
                null,           // variable aliases
                debugProperties // custom payload
            );

#if FEATURE_NET_ASYNC
            // Under .NET-async, async bodies are lowered before they reach here and must NOT go through the generator rewriter:
            //  * plain async (Coroutine, no Generator) via AsyncExpression,
            //  * async generators (Generator+Coroutine) via AsyncEnumerableExpression.
            // As in CPython, calling an async function only creates the coroutine (or async generator) object, so the outer factory lambda
            // is not traced at all. The async body is traced instead.
            if ((Flags & FunctionAttributes.Coroutine) != 0) {
                var lambda = (LambdaExpression)Compiler.Ast.Node.RemoveFrame(_lambda.GetLambda());
                return (LambdaExpression)new AsyncDebugHookInjector(context.DebugContext, debugInfo).Visit(lambda);
            }
#endif
            if ((Flags & (FunctionAttributes.Generator | FunctionAttributes.Coroutine)) == 0) {
                return context.DebugContext.TransformLambda((LambdaExpression)Compiler.Ast.Node.RemoveFrame(_lambda.GetLambda()), debugInfo);
            }

            bool isCoroutine = (Flags & FunctionAttributes.Coroutine) != 0;
            return Expression.Lambda(
                Code.Type,
                new GeneratorRewriter(
                    _lambda.Name,
                    Compiler.Ast.Node.RemoveFrame(Code.Body),
                    isCoroutine
                ).Reduce(
                    _lambda.ShouldInterpret,
                    _lambda.EmitDebugSymbols,
                    context.Options.CompilationThreshold,
                    Code.Parameters,
                    x => (Expression<Func<MutableTuple, object>>)context.DebugContext.TransformLambda(x, debugInfo)
                ),
                Code.Name,
                Code.Parameters
            );
        }


        /// <summary>
        /// Gets the correct final LambdaExpression for this piece of code.
        /// 
        /// This is either just _lambda or _lambda re-written to be a generator expression.
        /// </summary>
        private LightLambdaExpression GetGeneratorOrNormalLambda() {
            LightLambdaExpression finalCode;
#if FEATURE_NET_ASYNC
            // See the sibling GetGeneratorOrNormalLambdaTracing: only a plain generator
            // (Generator without Coroutine) is rewritten; plain async and async generators are lowered earlier.
            if ((Flags & FunctionAttributes.Generator) == 0 || (Flags & FunctionAttributes.Coroutine) != 0) {
#else
            if ((Flags & (FunctionAttributes.Generator | FunctionAttributes.Coroutine)) == 0) {
#endif
                finalCode = Code;
            } else {
                bool isCoroutine = (Flags & FunctionAttributes.Coroutine) != 0;
                finalCode = Code.ToGenerator(
                    _lambda.ShouldInterpret,
                    _lambda.EmitDebugSymbols,
                    _lambda.GlobalParent.PyContext.Options.CompilationThreshold,
                    isCoroutine
                );
            }
            return finalCode;
        }

        private Delegate CompileLambda(LightLambdaExpression code, EventHandler<LightLambdaCompileEventArgs> handler) {
#if EMIT_PDB
            if (_lambda.EmitDebugSymbols) {
                return CompilerHelpers.CompileToMethod((LambdaExpression)code.Reduce(), DebugInfoGenerator.CreatePdbGenerator(), true);
            }
#endif    
            if (_lambda.ShouldInterpret) {
                Delegate result = code.Compile(_lambda.GlobalParent.PyContext.Options.CompilationThreshold);

                // If the adaptive compiler decides to compile this function, we
                // want to store the new compiled target. This saves us from going
                // through the interpreter stub every call.
                if (result.Target is LightLambda lightLambda) {
                    lightLambda.Compile += handler;
                }

                return result;
            }

            return code.Compile();
        }

        private Delegate CompileLambda(LambdaExpression code, EventHandler<LightLambdaCompileEventArgs> handler) {
#if EMIT_PDB
            if (_lambda.EmitDebugSymbols) {
                return CompilerHelpers.CompileToMethod(code, DebugInfoGenerator.CreatePdbGenerator(), true);
            } 
#endif
            if (_lambda.ShouldInterpret) {
                Delegate result = CompilerHelpers.LightCompile(code, _lambda.GlobalParent.PyContext.Options.CompilationThreshold);

                // If the adaptive compiler decides to compile this function, we
                // want to store the new compiled target. This saves us from going
                // through the interpreter stub every call.
                if (result.Target is LightLambda lightLambda) {
                    lightLambda.Compile += handler;
                }

                return result;
            }

            return code.Compile();
        }

        internal Delegate AddRecursionCheck(PythonContext context, Delegate finalTarget) {
            if (context.RecursionLimit != Int32.MaxValue) {
                if (finalTarget is Func<CodeContext, CodeContext> ||
                    finalTarget is Func<FunctionCode, object> ||
                    finalTarget is LookupCompilationDelegate) {
                    // no recursion enforcement on classes or modules
                    return finalTarget;
                }

                switch (_lambda.ParameterNames.Length) {
                    #region Generated Python Recursion Delegate Switch

                    // *** BEGIN GENERATED CODE ***
                    // generated by function: gen_recursion_delegate_switch from: generate_calls.py

                    case 0:
                        finalTarget = new Func<PythonFunction, object>(new PythonFunctionRecursionCheck0((Func<PythonFunction, object>)finalTarget).CallTarget);
                        break;
                    case 1:
                        finalTarget = new Func<PythonFunction, object, object>(new PythonFunctionRecursionCheck1((Func<PythonFunction, object, object>)finalTarget).CallTarget);
                        break;
                    case 2:
                        finalTarget = new Func<PythonFunction, object, object, object>(new PythonFunctionRecursionCheck2((Func<PythonFunction, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 3:
                        finalTarget = new Func<PythonFunction, object, object, object, object>(new PythonFunctionRecursionCheck3((Func<PythonFunction, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 4:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object>(new PythonFunctionRecursionCheck4((Func<PythonFunction, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 5:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object>(new PythonFunctionRecursionCheck5((Func<PythonFunction, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 6:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck6((Func<PythonFunction, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 7:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck7((Func<PythonFunction, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 8:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck8((Func<PythonFunction, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 9:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck9((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 10:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck10((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 11:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck11((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 12:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck12((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 13:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck13((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 14:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck14((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;
                    case 15:
                        finalTarget = new Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object>(new PythonFunctionRecursionCheck15((Func<PythonFunction, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object, object>)finalTarget).CallTarget);
                        break;

                    // *** END GENERATED CODE ***

                    #endregion
                    default:
                        finalTarget = new Func<PythonFunction, object[], object>(new PythonFunctionRecursionCheckN((Func<PythonFunction, object[], object>)finalTarget).CallTarget);
                        break;

                }
            }
            return finalTarget;
        }

        private class TargetUpdaterForCompilation {
            private readonly PythonContext _context;
            private readonly FunctionCode _code;

            public TargetUpdaterForCompilation(PythonContext context, FunctionCode code) {
                _code = code;
                _context = context;
            }

            public void SetCompiledTarget(object sender, LightLambdaCompileEventArgs e) {
                _code.PublishTarget(_context, tracing: false, _code.AddRecursionCheck(_context, _code._normalDelegate = e.Compiled));
            }

            public void SetCompiledTargetTracing(object sender, LightLambdaCompileEventArgs e) {
                _code.PublishTarget(_context, tracing: true, _code.AddRecursionCheck(_context, _code._tracingDelegate = e.Compiled));
            }
        }

        #region IExpressionSerializable Members

        Expression IExpressionSerializable.CreateExpression() {
            return Expression.Call(
                typeof(PythonOps).GetMethod(nameof(PythonOps.MakeFunctionCode)),
                Compiler.Ast.PythonAst._globalContext,
                Expression.Constant(_lambda.Name),
                Expression.Constant(_initialDoc, typeof(string)),
                Expression.NewArrayInit(
                    typeof(string),
                    ArrayUtils.ConvertAll(_lambda.ParameterNames, (x) => Expression.Constant(x))
                ),
                Expression.Constant(_lambda.ArgCount),
                Expression.Constant(Flags),
                Expression.Constant(_lambda.IndexSpan.Start),
                Expression.Constant(_lambda.IndexSpan.End),
                Expression.Constant(_lambda.Filename),
                GetGeneratorOrNormalLambda(),
                TupleToStringArray(co_freevars),
                TupleToStringArray(co_names),
                TupleToStringArray(co_cellvars),
                TupleToStringArray(co_varnames),
                Expression.Constant(_localCount)
            );
        }

        private static Expression TupleToStringArray(PythonTuple tuple) {
            return tuple.Count > 0 ?
                (Expression)Expression.NewArrayInit(
                    typeof(string),
                    ArrayUtils.ConvertAll(tuple._data, (x) => Expression.Constant(x))
                ) :
                (Expression)Expression.Constant(null, typeof(string[]));
        }

        #endregion

        /// <summary>
        /// Extremely light weight linked list of weak references used for tracking
        /// all of the FunctionCode objects which get created and need to be updated
        /// for purposes of recursion enforcement or tracing.
        /// </summary>
        internal class CodeList {
            public readonly WeakReference Code;
            public CodeList Next;

            public CodeList() { }

            public CodeList(WeakReference code, CodeList next) {
                Code = code;
                Next = next;
            }
        }
    }

    internal class PythonDebuggingPayload {
        public FunctionCode Code;
        private Dictionary<int, bool> _handlerLocations;
        private Dictionary<int, Dictionary<int, bool>> _loopAndFinallyLocations;

        public PythonDebuggingPayload(FunctionCode code) {
            Code = code;
        }

        public Dictionary<int, bool> HandlerLocations {
            get {
                if (_handlerLocations == null) {
                    GatherLocations();
                }

                return _handlerLocations;
            }
        }

        public Dictionary<int, Dictionary<int, bool>> LoopAndFinallyLocations {
            get {
                if (_loopAndFinallyLocations == null) {
                    GatherLocations();
                }

                return _loopAndFinallyLocations;
            }
        }

        private void GatherLocations() {
            var walker = new TracingWalker();

            Code.PythonCode.Walk(walker);

            _loopAndFinallyLocations = walker.LoopAndFinallyLocations;
            _handlerLocations = walker.HandlerLocations;
        }

        private class TracingWalker : Compiler.Ast.PythonWalker {
            private bool _inLoop, _inFinally;
            private int _loopId;
            public Dictionary<int, bool> HandlerLocations = new Dictionary<int, bool>();
            public Dictionary<int, Dictionary<int, bool>> LoopAndFinallyLocations = new Dictionary<int, Dictionary<int, bool>>();
            private Dictionary<int, bool> _loopIds = new Dictionary<int, bool>();

            public override bool Walk(Compiler.Ast.ForStatement node) {
                UpdateLoops(node);
                WalkLoopBody(node.Body, false);

                if (node.Else != null) {
                    node.Else.Walk(this);
                }

                return false;
            }

            private void WalkLoopBody(IronPython.Compiler.Ast.Statement body, bool isFinally) {

                bool inLoop = _inLoop;
                bool inFinally = _inFinally;

                int loopId = ++_loopId;
                _inFinally = false;
                _inLoop = true;
                _loopIds.Add(loopId, isFinally);

                body.Walk(this);

                _inLoop = inLoop;
                _inFinally = inFinally;
                LoopOrFinallyIds.Remove(loopId);
            }

            public override bool Walk(Compiler.Ast.WhileStatement node) {
                UpdateLoops(node);

                WalkLoopBody(node.Body, false);

                node.ElseStatement?.Walk(this);

                return false;
            }

            public override bool Walk(Compiler.Ast.TryStatement node) {
                UpdateLoops(node);

                node.Body.Walk(this);

                foreach (var handler in node.Handlers) {
                    HandlerLocations[handler.Span.Start.Line] = false;
                    handler.Body.Walk(this);
                }

                if (node.Finally != null) {
                    WalkLoopBody(node.Finally, true);
                }
                return false;
            }

            public override bool Walk(Compiler.Ast.AssertStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.AssignmentStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.AugmentedAssignStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.BreakStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.ClassDefinition node) {
                UpdateLoops(node);
                return false;
            }

            public override bool Walk(Compiler.Ast.ContinueStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override void PostWalk(Compiler.Ast.EmptyStatement node) {
                UpdateLoops(node);
                base.PostWalk(node);
            }

            public override bool Walk(Compiler.Ast.DelStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.EmptyStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.GlobalStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.FromImportStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.ExpressionStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.FunctionDefinition node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.IfStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.ImportStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.RaiseStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            public override bool Walk(Compiler.Ast.WithStatement node) {
                UpdateLoops(node);
                return base.Walk(node);
            }

            private void UpdateLoops(Compiler.Ast.Statement stmt) {
                if (_inFinally || _inLoop) {
                    if (!LoopAndFinallyLocations.ContainsKey(stmt.Span.Start.Line)) {
                        LoopAndFinallyLocations.Add(stmt.Span.Start.Line, new Dictionary<int, bool>(LoopOrFinallyIds));
                    }
                }
            }

            public Dictionary<int, bool> LoopOrFinallyIds {
                get {
                    if (_loopIds == null) {
                        _loopIds = new Dictionary<int, bool>();
                    }
                    return _loopIds;
                }
            }
        }
    }

#if FEATURE_NET_ASYNC
    /// <summary>
    ///   Swaps a lowered <see cref="AsyncExpression"/> / <see cref="AsyncEnumerableExpression"/> for a debug-enabled copy.
    /// </summary>
    /// <remarks>
    ///   Used to build the tracing variant of an async function: the debug-enabled node instruments its own body when reduced, so the
    ///   async body becomes traceable while the outer factory stays untraced. A function's own async node is the only one in its lambda
    ///   — nested defs compile to their own lambdas/codes — so a single replacement is made, and the node is not descended into.
    /// </remarks>
    internal sealed class AsyncDebugHookInjector : ExpressionVisitor {
        private readonly DebugContext _debugContext;
        private readonly DebugLambdaInfo _debugLambdaInfo;

        internal AsyncDebugHookInjector(DebugContext debugContext, DebugLambdaInfo debugLambdaInfo) {
            _debugContext = debugContext;
            _debugLambdaInfo = debugLambdaInfo;
        }

        protected override Expression VisitExtension(Expression node) {
            switch (node) {
                case AsyncExpression ae:
                    return ae.WithDebugInfo(_debugContext, _debugLambdaInfo);
                case AsyncEnumerableExpression aee:
                    return aee.WithDebugInfo(_debugContext, _debugLambdaInfo);
                default:
                    return base.VisitExtension(node);
            }
        }
    }
#endif
}