#include "Python.h"

#include "pycore_ast.h"           // stmt_ty

#include "pycore_parser.h"        // _PyParser_ASTFromString()

#include "pycore_pystate.h"       // _PyThreadState_GET()

#include "pycore_runtime.h"       // _Py_ID()

#include "pycore_symtable.h"      // PySTEntryObject

#include "pycore_unicodeobject.h" // _PyUnicode_EqualToASCIIString

#include "setobject.h"

#include <stddef.h>               // offsetof()

#include <stdint.h>

// Set this to 1 to dump all symtables to stdout for debugging

#define _PY_DUMP_SYMTABLE 0

/* error strings used for warnings */

#define GLOBAL_PARAM \

"name '%U' is parameter and global"

#define NONLOCAL_PARAM \

"name '%U' is parameter and nonlocal"

#define GLOBAL_AFTER_ASSIGN \

"name '%U' is assigned to before global declaration"

#define NONLOCAL_AFTER_ASSIGN \

"name '%U' is assigned to before nonlocal declaration"

#define GLOBAL_AFTER_USE \

"name '%U' is used prior to global declaration"

#define NONLOCAL_AFTER_USE \

"name '%U' is used prior to nonlocal declaration"

#define GLOBAL_ANNOT \

"annotated name '%U' can't be global"

#define NONLOCAL_ANNOT \

"annotated name '%U' can't be nonlocal"

#define IMPORT_STAR_WARNING "import * only allowed at module level"

#define NAMED_EXPR_COMP_IN_CLASS \

"assignment expression within a comprehension cannot be used in a class body"

#define NAMED_EXPR_COMP_IN_TYPEVAR_BOUND \

"assignment expression within a comprehension cannot be used in a TypeVar bound"

#define NAMED_EXPR_COMP_IN_TYPEALIAS \

"assignment expression within a comprehension cannot be used in a type alias"

#define NAMED_EXPR_COMP_IN_TYPEPARAM \

"assignment expression within a comprehension cannot be used within the definition of a generic"

#define NAMED_EXPR_COMP_CONFLICT \

"assignment expression cannot rebind comprehension iteration variable '%U'"

#define NAMED_EXPR_COMP_INNER_LOOP_CONFLICT \

"comprehension inner loop cannot rebind assignment expression target '%U'"

#define NAMED_EXPR_COMP_ITER_EXPR \

"assignment expression cannot be used in a comprehension iterable expression"

#define ANNOTATION_NOT_ALLOWED \

"%s cannot be used within an annotation"

#define EXPR_NOT_ALLOWED_IN_TYPE_VARIABLE \

"%s cannot be used within %s"

#define EXPR_NOT_ALLOWED_IN_TYPE_ALIAS \

"%s cannot be used within a type alias"

#define EXPR_NOT_ALLOWED_IN_TYPE_PARAMETERS \

"%s cannot be used within the definition of a generic"

#define DUPLICATE_TYPE_PARAM \

"duplicate type parameter '%U'"

#define ASYNC_WITH_OUTSIDE_ASYNC_FUNC \

"'async with' outside async function"

#define ASYNC_FOR_OUTSIDE_ASYNC_FUNC \

"'async for' outside async function"

#define LOCATION(x) SRC_LOCATION_FROM_AST(x)

#define SET_ERROR_LOCATION(FNAME, L) \

    PyErr_RangedSyntaxLocationObject((FNAME), \

        (L).lineno, (L).col_offset + 1, (L).end_lineno, (L).end_col_offset + 1)

#define IS_ASYNC_DEF(st) ((st)->st_cur->ste_type == FunctionBlock && (st)->st_cur->ste_coroutine)

static int

ste_uses_fast_locals(PySTEntryObject *ste)

{

    return _PyST_IsFunctionLike(ste) || ste->ste_type == InlinedComprehensionBlock;

}

static PySTEntryObject *

ste_new(struct symtable *st, identifier name, _Py_block_ty block,

        void *key, _Py_SourceLocation loc)

{

    PySTEntryObject *ste = NULL;

    PyObject *k = NULL;

    k = PyLong_FromVoidPtr(key);

    if (k == NULL)

        goto fail;

    ste = PyObject_New(PySTEntryObject, &PySTEntry_Type);

    if (ste == NULL) {

        Py_DECREF(k);

        goto fail;

    }

    ste->ste_table = st;

    ste->ste_id = k; /* ste owns reference to k */

    ste->ste_name = Py_NewRef(name);

    ste->ste_function_name = NULL;

    ste->ste_symbols = NULL;

    ste->ste_varnames = NULL;

    ste->ste_children = NULL;

    ste->ste_directives = NULL;

    ste->ste_mangled_names = NULL;

    ste->ste_type = block;

    ste->ste_scope_info = NULL;

    ste->ste_nested = 0;

    ste->ste_varargs = 0;

    ste->ste_varkeywords = 0;

    ste->ste_annotations_used = 0;

    ste->ste_loc = loc;

    if (st->st_cur != NULL &&

        (st->st_cur->ste_nested ||

         ste_uses_fast_locals(st->st_cur)))

        ste->ste_nested = 1;

    ste->ste_generator = 0;

    ste->ste_coroutine = 0;

    ste->ste_comprehension = NoComprehension;

    ste->ste_returns_value = 0;

    ste->ste_needs_class_closure = 0;

    ste->ste_parent = (block == InlinedComprehensionBlock) ? st->st_cur : NULL;

    ste->ste_comp_iter_target = 0;

    ste->ste_can_see_class_scope = 0;

    ste->ste_comp_iter_expr = 0;

    ste->ste_needs_classdict = 0;

    ste->ste_has_conditional_annotations = 0;

    ste->ste_in_conditional_block = 0;

    ste->ste_in_try_block = 0;

    ste->ste_in_unevaluated_annotation = 0;

    ste->ste_annotation_block = NULL;

    ste->ste_has_docstring = 0;

    ste->ste_method = 0;

    if (st->st_cur != NULL &&

        st->st_cur->ste_type == ClassBlock &&

        block == FunctionBlock) {

        ste->ste_method = 1;

    }

    ste->ste_symbols = PyDict_New();

    ste->ste_varnames = PyList_New(0);

    ste->ste_children = PyList_New(0);

    if (ste->ste_symbols == NULL

        || ste->ste_varnames == NULL

        || ste->ste_children == NULL)

        goto fail;

    if (PyDict_SetItem(st->st_blocks, ste->ste_id, (PyObject *)ste) < 0)

        goto fail;

    return ste;

 fail:

    Py_XDECREF(ste);

    return NULL;

}

static PyObject *

ste_repr(PyObject *op)

{

    PySTEntryObject *ste = (PySTEntryObject *)op;

    return PyUnicode_FromFormat("<symtable entry %U(%R), line %d>",

                                ste->ste_name, ste->ste_id, ste->ste_loc.lineno);

}

static void

ste_dealloc(PyObject *op)

{

    PySTEntryObject *ste = (PySTEntryObject *)op;

    ste->ste_table = NULL;

    Py_XDECREF(ste->ste_id);

    Py_XDECREF(ste->ste_name);

    Py_XDECREF(ste->ste_function_name);

    Py_XDECREF(ste->ste_symbols);

    Py_XDECREF(ste->ste_varnames);

    Py_XDECREF(ste->ste_children);

    Py_XDECREF(ste->ste_directives);

    Py_XDECREF(ste->ste_annotation_block);

    Py_XDECREF(ste->ste_mangled_names);

    PyObject_Free(ste);

}

#define OFF(x) offsetof(PySTEntryObject, x)

static PyMemberDef ste_memberlist[] = {

    {"id",       _Py_T_OBJECT, OFF(ste_id), Py_READONLY},

    {"name",     _Py_T_OBJECT, OFF(ste_name), Py_READONLY},

    {"symbols",  _Py_T_OBJECT, OFF(ste_symbols), Py_READONLY},

    {"varnames", _Py_T_OBJECT, OFF(ste_varnames), Py_READONLY},

    {"children", _Py_T_OBJECT, OFF(ste_children), Py_READONLY},

    {"nested",   Py_T_INT,    OFF(ste_nested), Py_READONLY},

    {"type",     Py_T_INT,    OFF(ste_type), Py_READONLY},

    {"lineno",   Py_T_INT,    OFF(ste_loc.lineno), Py_READONLY},

    {NULL}

};

PyTypeObject PySTEntry_Type = {

    PyVarObject_HEAD_INIT(&PyType_Type, 0)

    "symtable entry",

    sizeof(PySTEntryObject),

    0,

    ste_dealloc,                                /* tp_dealloc */

    0,                                          /* tp_vectorcall_offset */

    0,                                          /* tp_getattr */

    0,                                          /* tp_setattr */

    0,                                          /* tp_as_async */

    ste_repr,                                   /* tp_repr */

    0,                                          /* tp_as_number */

    0,                                          /* tp_as_sequence */

    0,                                          /* tp_as_mapping */

    0,                                          /* tp_hash */

    0,                                          /* tp_call */

    0,                                          /* tp_str */

    PyObject_GenericGetAttr,                    /* tp_getattro */

    0,                                          /* tp_setattro */

    0,                                          /* tp_as_buffer */

    Py_TPFLAGS_DEFAULT,                         /* tp_flags */

    0,                                          /* tp_doc */

    0,                                          /* tp_traverse */

    0,                                          /* tp_clear */

    0,                                          /* tp_richcompare */

    0,                                          /* tp_weaklistoffset */

    0,                                          /* tp_iter */

    0,                                          /* tp_iternext */

    0,                                          /* tp_methods */

    ste_memberlist,                             /* tp_members */

    0,                                          /* tp_getset */

    0,                                          /* tp_base */

    0,                                          /* tp_dict */

    0,                                          /* tp_descr_get */

    0,                                          /* tp_descr_set */

    0,                                          /* tp_dictoffset */

    0,                                          /* tp_init */

    0,                                          /* tp_alloc */

    0,                                          /* tp_new */

};

static int symtable_analyze(struct symtable *st);

static int symtable_enter_block(struct symtable *st, identifier name,

                                _Py_block_ty block, void *ast, _Py_SourceLocation loc);

static int symtable_exit_block(struct symtable *st);

static int symtable_visit_stmt(struct symtable *st, stmt_ty s);

static int symtable_visit_expr(struct symtable *st, expr_ty s);

static int symtable_visit_type_param(struct symtable *st, type_param_ty s);

static int symtable_visit_genexp(struct symtable *st, expr_ty s);

static int symtable_visit_listcomp(struct symtable *st, expr_ty s);

static int symtable_visit_setcomp(struct symtable *st, expr_ty s);

static int symtable_visit_dictcomp(struct symtable *st, expr_ty s);

static int symtable_visit_arguments(struct symtable *st, arguments_ty);

static int symtable_visit_excepthandler(struct symtable *st, excepthandler_ty);

static int symtable_visit_alias(struct symtable *st, alias_ty);

static int symtable_visit_comprehension(struct symtable *st, comprehension_ty);

static int symtable_visit_keyword(struct symtable *st, keyword_ty);

static int symtable_visit_params(struct symtable *st, asdl_arg_seq *args);

static int symtable_visit_annotation(struct symtable *st, expr_ty annotation, void *key);

static int symtable_visit_argannotations(struct symtable *st, asdl_arg_seq *args);

static int symtable_implicit_arg(struct symtable *st, int pos);

static int symtable_visit_annotations(struct symtable *st, stmt_ty, arguments_ty, expr_ty,

                                      struct _symtable_entry *parent_ste);

static int symtable_visit_withitem(struct symtable *st, withitem_ty item);

static int symtable_visit_match_case(struct symtable *st, match_case_ty m);

static int symtable_visit_pattern(struct symtable *st, pattern_ty s);

static int symtable_raise_if_annotation_block(struct symtable *st, const char *, expr_ty);

static int symtable_raise_if_not_coroutine(struct symtable *st, const char *msg, _Py_SourceLocation loc);

static int symtable_raise_if_comprehension_block(struct symtable *st, expr_ty);

static int symtable_add_def(struct symtable *st, PyObject *name, int flag, _Py_SourceLocation loc);

/* For debugging purposes only */

#if _PY_DUMP_SYMTABLE

static void _dump_symtable(PySTEntryObject* ste, PyObject* prefix)

{

    const char *blocktype = "";

    switch (ste->ste_type) {

        case FunctionBlock: blocktype = "FunctionBlock"; break;

        case ClassBlock: blocktype = "ClassBlock"; break;

        case ModuleBlock: blocktype = "ModuleBlock"; break;

        case AnnotationBlock: blocktype = "AnnotationBlock"; break;

        case TypeVariableBlock: blocktype = "TypeVariableBlock"; break;

        case TypeAliasBlock: blocktype = "TypeAliasBlock"; break;

        case TypeParametersBlock: blocktype = "TypeParametersBlock"; break;

        case InlinedComprehensionBlock: blocktype = "InlinedComprehensionBlock"; break;

    }

    const char *comptype = "";

    switch (ste->ste_comprehension) {

        case ListComprehension: comptype = " ListComprehension"; break;

        case DictComprehension: comptype = " DictComprehension"; break;

        case SetComprehension: comptype = " SetComprehension"; break;

        case GeneratorExpression: comptype = " GeneratorExpression"; break;

        case NoComprehension: break;

    }

    PyObject* msg = PyUnicode_FromFormat(

        (

            "%U=== Symtable for %U ===\n"

            "%U%s%s\n"

            "%U%s%s%s%s%s%s%s%s%s%s\n"

            "%Ulineno: %d col_offset: %d\n"

            "%U--- Symbols ---\n"

        ),

        prefix,

        ste->ste_name,

        prefix,

        blocktype,

        comptype,

        prefix,

        ste->ste_nested ? " nested" : "",

        ste->ste_generator ? " generator" : "",

        ste->ste_coroutine ? " coroutine" : "",

        ste->ste_varargs ? " varargs" : "",

        ste->ste_varkeywords ? " varkeywords" : "",

        ste->ste_returns_value ? " returns_value" : "",

        ste->ste_needs_class_closure ? " needs_class_closure" : "",

        ste->ste_needs_classdict ? " needs_classdict" : "",

        ste->ste_comp_iter_target ? " comp_iter_target" : "",

        ste->ste_can_see_class_scope ? " can_see_class_scope" : "",

        prefix,

        ste->ste_loc.lineno,

        ste->ste_loc.col_offset,

        prefix

    );

    assert(msg != NULL);

    printf("%s", PyUnicode_AsUTF8(msg));

    Py_DECREF(msg);

    PyObject *name, *value;

    Py_ssize_t pos = 0;

    while (PyDict_Next(ste->ste_symbols, &pos, &name, &value)) {

        int scope = _PyST_GetScope(ste, name);

        long flags = _PyST_GetSymbol(ste, name);

        printf("%s  %s: ", PyUnicode_AsUTF8(prefix), PyUnicode_AsUTF8(name));

        if (flags & DEF_GLOBAL) printf(" DEF_GLOBAL");

        if (flags & DEF_LOCAL) printf(" DEF_LOCAL");

        if (flags & DEF_PARAM) printf(" DEF_PARAM");

        if (flags & DEF_NONLOCAL) printf(" DEF_NONLOCAL");

        if (flags & USE) printf(" USE");

        if (flags & DEF_FREE_CLASS) printf(" DEF_FREE_CLASS");

        if (flags & DEF_IMPORT) printf(" DEF_IMPORT");

        if (flags & DEF_ANNOT) printf(" DEF_ANNOT");

        if (flags & DEF_COMP_ITER) printf(" DEF_COMP_ITER");

        if (flags & DEF_TYPE_PARAM) printf(" DEF_TYPE_PARAM");

        switch (scope) {

            case LOCAL: printf(" LOCAL"); break;

            case GLOBAL_EXPLICIT: printf(" GLOBAL_EXPLICIT"); break;

            case GLOBAL_IMPLICIT: printf(" GLOBAL_IMPLICIT"); break;

            case FREE: printf(" FREE"); break;

            case CELL: printf(" CELL"); break;

        }

        printf("\n");

    }

    printf("%s--- Children ---\n", PyUnicode_AsUTF8(prefix));

    PyObject *new_prefix = PyUnicode_FromFormat("  %U", prefix);

    assert(new_prefix != NULL);

    for (Py_ssize_t i = 0; i < PyList_GET_SIZE(ste->ste_children); i++) {

        PyObject *child = PyList_GetItem(ste->ste_children, i);

        assert(child != NULL && PySTEntry_Check(child));

        _dump_symtable((PySTEntryObject *)child, new_prefix);

    }

    Py_DECREF(new_prefix);

}

static void dump_symtable(PySTEntryObject* ste)

{

    PyObject *empty = Py_GetConstant(Py_CONSTANT_EMPTY_STR);

    assert(empty != NULL);

    _dump_symtable(ste, empty);

    Py_DECREF(empty);

}

#endif

#define DUPLICATE_PARAMETER \

"duplicate parameter '%U' in function definition"

static struct symtable *

symtable_new(void)

{

    struct symtable *st;

    st = (struct symtable *)PyMem_Malloc(sizeof(struct symtable));

    if (st == NULL) {

        PyErr_NoMemory();

        return NULL;

    }

    st->st_filename = NULL;

    st->st_blocks = NULL;

    if ((st->st_stack = PyList_New(0)) == NULL)

        goto fail;

    if ((st->st_blocks = PyDict_New()) == NULL)

        goto fail;

    st->st_cur = NULL;

    st->st_private = NULL;

    return st;

 fail:

    _PySymtable_Free(st);

    return NULL;

}

struct symtable *

_PySymtable_Build(mod_ty mod, PyObject *filename, _PyFutureFeatures *future)

{

    struct symtable *st = symtable_new();

    asdl_stmt_seq *seq;

    Py_ssize_t i;

    PyThreadState *tstate;

    if (st == NULL)

        return NULL;

    if (filename == NULL) {

        _PySymtable_Free(st);

        return NULL;

    }

    st->st_filename = Py_NewRef(filename);

    st->st_future = future;

    /* Setup recursion depth check counters */

    tstate = _PyThreadState_GET();

    if (!tstate) {

        _PySymtable_Free(st);

        return NULL;

    }

    /* Make the initial symbol information gathering pass */

    _Py_SourceLocation loc0 = {0, 0, 0, 0};

    if (!symtable_enter_block(st, &_Py_ID(top), ModuleBlock, (void *)mod, loc0)) {

        _PySymtable_Free(st);

        return NULL;

    }

    st->st_top = st->st_cur;

    switch (mod->kind) {

    case Module_kind:

        seq = mod->v.Module.body;

        if (_PyAST_GetDocString(seq)) {

            st->st_cur->ste_has_docstring = 1;

        }

        for (i = 0; i < asdl_seq_LEN(seq); i++)

            if (!symtable_visit_stmt(st,

                        (stmt_ty)asdl_seq_GET(seq, i)))

                goto error;

        break;

    case Expression_kind:

        if (!symtable_visit_expr(st, mod->v.Expression.body))

            goto error;

        break;

    case Interactive_kind:

        seq = mod->v.Interactive.body;

        for (i = 0; i < asdl_seq_LEN(seq); i++)

            if (!symtable_visit_stmt(st,

                        (stmt_ty)asdl_seq_GET(seq, i)))

                goto error;

        break;

    case FunctionType_kind:

        PyErr_SetString(PyExc_RuntimeError,

                        "this compiler does not handle FunctionTypes");

        goto error;

    }

    if (!symtable_exit_block(st)) {

        _PySymtable_Free(st);

        return NULL;

    }

    /* Make the second symbol analysis pass */

    if (symtable_analyze(st)) {

#if _PY_DUMP_SYMTABLE

        dump_symtable(st->st_top);

#endif

        return st;

    }

    _PySymtable_Free(st);

    return NULL;

 error:

    (void) symtable_exit_block(st);

    _PySymtable_Free(st);

    return NULL;

}

void

_PySymtable_Free(struct symtable *st)

{

    Py_XDECREF(st->st_filename);

    Py_XDECREF(st->st_blocks);

    Py_XDECREF(st->st_stack);

    PyMem_Free((void *)st);

}

PySTEntryObject *

_PySymtable_Lookup(struct symtable *st, void *key)

{

    PyObject *k, *v;

    k = PyLong_FromVoidPtr(key);

    if (k == NULL)

        return NULL;

    if (PyDict_GetItemRef(st->st_blocks, k, &v) == 0) {

        PyErr_SetString(PyExc_KeyError,

                        "unknown symbol table entry");

    }

    Py_DECREF(k);

    assert(v == NULL || PySTEntry_Check(v));

    return (PySTEntryObject *)v;

}

int

_PySymtable_LookupOptional(struct symtable *st, void *key,

                           PySTEntryObject **out)

{

    PyObject *k = PyLong_FromVoidPtr(key);

    if (k == NULL) {

        *out = NULL;

        return -1;

    }

    int result = PyDict_GetItemRef(st->st_blocks, k, (PyObject **)out);

    Py_DECREF(k);

    assert(*out == NULL || PySTEntry_Check(*out));

    return result;

}

long

_PyST_GetSymbol(PySTEntryObject *ste, PyObject *name)

{

    PyObject *v;

    if (PyDict_GetItemRef(ste->ste_symbols, name, &v) < 0) {

        return -1;

    }

    if (v == NULL) {

        return 0;

    }

    long symbol = PyLong_AsLong(v);

    Py_DECREF(v);

    if (symbol < 0) {

        if (!PyErr_Occurred()) {

            PyErr_SetString(PyExc_SystemError, "invalid symbol");

        }

        return -1;

    }

    return symbol;

}

int

_PyST_GetScope(PySTEntryObject *ste, PyObject *name)

{

    long symbol = _PyST_GetSymbol(ste, name);

    if (symbol < 0) {

        return -1;

    }

    return SYMBOL_TO_SCOPE(symbol);

}

int

_PyST_IsFunctionLike(PySTEntryObject *ste)

{

    return ste->ste_type == FunctionBlock

        || ste->ste_type == AnnotationBlock

        || ste->ste_type == TypeVariableBlock

        || ste->ste_type == TypeAliasBlock

        || ste->ste_type == TypeParametersBlock;

}

int

_PyST_IsClassClosureName(PyObject *name)

{

    return _PyUnicode_EqualToASCIIString(name, "__class__")

        || _PyUnicode_EqualToASCIIString(name, "__classdict__")

        || _PyUnicode_EqualToASCIIString(name, "__conditional_annotations__");

}

static int

error_at_directive(PySTEntryObject *ste, PyObject *name)

{

    Py_ssize_t i;

    PyObject *data;

    assert(ste->ste_directives);

    for (i = 0; i < PyList_GET_SIZE(ste->ste_directives); i++) {

        data = PyList_GET_ITEM(ste->ste_directives, i);

        assert(PyTuple_CheckExact(data));

        assert(PyUnicode_CheckExact(PyTuple_GET_ITEM(data, 0)));

        if (PyUnicode_Compare(PyTuple_GET_ITEM(data, 0), name) == 0) {

            PyErr_RangedSyntaxLocationObject(ste->ste_table->st_filename,

                                             PyLong_AsLong(PyTuple_GET_ITEM(data, 1)),

                                             PyLong_AsLong(PyTuple_GET_ITEM(data, 2)) + 1,

                                             PyLong_AsLong(PyTuple_GET_ITEM(data, 3)),

                                             PyLong_AsLong(PyTuple_GET_ITEM(data, 4)) + 1);

            return 0;

        }

    }

    PyErr_SetString(PyExc_RuntimeError,

                    "BUG: internal directive bookkeeping broken");

    return 0;

}

/* Analyze raw symbol information to determine scope of each name.

   The next several functions are helpers for symtable_analyze(),

   which determines whether a name is local, global, or free.  In addition,

   it determines which local variables are cell variables; they provide

   bindings that are used for free variables in enclosed blocks.

   There are also two kinds of global variables, implicit and explicit.  An

   explicit global is declared with the global statement.  An implicit

   global is a free variable for which the compiler has found no binding

   in an enclosing function scope.  The implicit global is either a global

   or a builtin.  Python's module and class blocks use the xxx_NAME opcodes

   to handle these names to implement slightly odd semantics.  In such a

   block, the name is treated as global until it is assigned to; then it

   is treated as a local.

   The symbol table requires two passes to determine the scope of each name.

   The first pass collects raw facts from the AST via the symtable_visit_*

   functions: the name is a parameter here, the name is used but not defined

   here, etc.  The second pass analyzes these facts during a pass over the

   PySTEntryObjects created during pass 1.

   When a function is entered during the second pass, the parent passes

   the set of all name bindings visible to its children.  These bindings

   are used to determine if non-local variables are free or implicit globals.

   Names which are explicitly declared nonlocal must exist in this set of

   visible names - if they do not, a syntax error is raised. After doing

   the local analysis, it analyzes each of its child blocks using an

   updated set of name bindings.

   The children update the free variable set.  If a local variable is added to

   the free variable set by the child, the variable is marked as a cell.  The

   function object being defined must provide runtime storage for the variable

   that may outlive the function's frame.  Cell variables are removed from the

   free set before the analyze function returns to its parent.

   During analysis, the names are:

      symbols: dict mapping from symbol names to flag values (including offset scope values)

      scopes: dict mapping from symbol names to scope values (no offset)

      local: set of all symbol names local to the current scope

      bound: set of all symbol names local to a containing function scope

      free: set of all symbol names referenced but not bound in child scopes

      global: set of all symbol names explicitly declared as global

*/

#define SET_SCOPE(DICT, NAME, I) \

    do { \

        PyObject *o = PyLong_FromLong(I); \

        if (!o) \

            return 0; \

        if (PyDict_SetItem((DICT), (NAME), o) < 0) { \

            Py_DECREF(o); \

            return 0; \

        } \

        Py_DECREF(o); \

    } while(0)

/* Decide on scope of name, given flags.

   The namespace dictionaries may be modified to record information

   about the new name.  For example, a new global will add an entry to

   global.  A name that was global can be changed to local.

*/

static int

analyze_name(PySTEntryObject *ste, PyObject *scopes, PyObject *name, long flags,

             PyObject *bound, PyObject *local, PyObject *free,

             PyObject *global, PyObject *type_params, PySTEntryObject *class_entry)

{

    int contains;

    if (flags & DEF_GLOBAL) {

        if (flags & DEF_NONLOCAL) {

            PyErr_Format(PyExc_SyntaxError,

                         "name '%U' is nonlocal and global",

                         name);

            return error_at_directive(ste, name);

        }

        SET_SCOPE(scopes, name, GLOBAL_EXPLICIT);

        if (PySet_Add(global, name) < 0)

            return 0;

        if (bound && (PySet_Discard(bound, name) < 0))

            return 0;

        return 1;

    }

    if (flags & DEF_NONLOCAL) {

        if (!bound) {

            PyErr_Format(PyExc_SyntaxError,

                         "nonlocal declaration not allowed at module level");

            return error_at_directive(ste, name);

        }

        contains = PySet_Contains(bound, name);

        if (contains < 0) {

            return 0;

        }

        if (!contains) {

            PyErr_Format(PyExc_SyntaxError,

                         "no binding for nonlocal '%U' found",

                         name);

            return error_at_directive(ste, name);

        }

        contains = PySet_Contains(type_params, name);

        if (contains < 0) {

            return 0;

        }

        if (contains) {

            PyErr_Format(PyExc_SyntaxError,

                         "nonlocal binding not allowed for type parameter '%U'",

                         name);

            return error_at_directive(ste, name);

        }

        SET_SCOPE(scopes, name, FREE);

        return PySet_Add(free, name) >= 0;

    }

    if (flags & DEF_BOUND) {

        SET_SCOPE(scopes, name, LOCAL);

        if (PySet_Add(local, name) < 0)

            return 0;

        if (PySet_Discard(global, name) < 0)

            return 0;

        if (flags & DEF_TYPE_PARAM) {

            if (PySet_Add(type_params, name) < 0)

                return 0;

        }

        else {

            if (PySet_Discard(type_params, name) < 0)

                return 0;

        }

        return 1;

    }

    // If we were passed class_entry (i.e., we're in an ste_can_see_class_scope scope)

    // and the bound name is in that set, then the name is potentially bound both by

    // the immediately enclosing class namespace, and also by an outer function namespace.

    // In that case, we want the runtime name resolution to look at only the class

    // namespace and the globals (not the namespace providing the bound).

    // Similarly, if the name is explicitly global in the class namespace (through the

    // global statement), we want to also treat it as a global in this scope.

    if (class_entry != NULL) {

        long class_flags = _PyST_GetSymbol(class_entry, name);

        if (class_flags < 0) {

            return 0;

        }

        if (class_flags & DEF_GLOBAL) {

            SET_SCOPE(scopes, name, GLOBAL_EXPLICIT);

            return 1;

        }

        else if ((class_flags & DEF_BOUND) && !(class_flags & DEF_NONLOCAL)) {

            SET_SCOPE(scopes, name, GLOBAL_IMPLICIT);

            return 1;

        }

    }

    /* If an enclosing block has a binding for this name, it

       is a free variable rather than a global variable.

       Note that having a non-NULL bound implies that the block

       is nested.

    */

    if (bound) {

        contains = PySet_Contains(bound, name);

        if (contains < 0) {

            return 0;

        }

        if (contains) {

            SET_SCOPE(scopes, name, FREE);

            return PySet_Add(free, name) >= 0;

        }

    }

    /* If a parent has a global statement, then call it global

       explicit?  It could also be global implicit.

     */

    if (global) {

        contains = PySet_Contains(global, name);

        if (contains < 0) {

            return 0;

        }

        if (contains) {

            SET_SCOPE(scopes, name, GLOBAL_IMPLICIT);

            return 1;

        }

    }

    SET_SCOPE(scopes, name, GLOBAL_IMPLICIT);

    return 1;

}

/* See InternalDocs/inlined_comprehensions.md. */

static int

is_free_in_any_child(PySTEntryObject *entry, PyObject *key)

{

    for (Py_ssize_t i = 0; i < PyList_GET_SIZE(entry->ste_children); i++) {

        PySTEntryObject *child_ste = (PySTEntryObject *)PyList_GET_ITEM(

            entry->ste_children, i);

        if (child_ste->ste_type == InlinedComprehensionBlock) {

            /* this is the same scope, so we check its children */

            int nested = is_free_in_any_child(child_ste, key);

            if (nested != 0) {

                return nested;

            }

            continue;

        }

        long scope = _PyST_GetScope(child_ste, key);

        if (scope < 0) {

            return -1;

        }

        if (scope == FREE) {

            return 1;

        }

    }

    return 0;

}

static int

symtable_add_flag(PyObject *dict, PyObject *name, int flag)

{

    PyObject *o = PyDict_GetItemWithError(dict, name);

    long val;

    if (o != NULL) {

        val = PyLong_AsLong(o);

        if (val == -1 && PyErr_Occurred()) {

            return 0;

        }

        val |= flag;

    }

    else if (PyErr_Occurred()) {

        return 0;

    }

    else {

        val = flag;

    }

    o = PyLong_FromLong(val);

    if (o == NULL) {

        return 0;

    }

    int rc = PyDict_SetItem(dict, name, o);

    Py_DECREF(o);

    return rc >= 0;

}

static int

finalize_inlined_comprehension(PySTEntryObject *ste, PySTEntryObject *comp,

                                PyObject *comp_free, PyObject *outer_newfree,

                                PyObject *inlined_cells)

{

    PyObject *k, *v;

    Py_ssize_t pos = 0;

    assert(comp->ste_type == InlinedComprehensionBlock);

    assert(comp->ste_parent != NULL);

    while (PyDict_Next(comp->ste_symbols, &pos, &k, &v)) {

        long comp_flags = PyLong_AsLong(v);

        if (comp_flags == -1 && PyErr_Occurred()) {

            goto error;

        }

        int scope = SYMBOL_TO_SCOPE(comp_flags);

        if (scope == CELL) {

            if (PySet_Add(inlined_cells, k) < 0) {

                goto error;

            }

        }

        PyObject *existing = PyDict_GetItemWithError(ste->ste_symbols, k);

        if (existing == NULL && PyErr_Occurred()) {

            goto error;

        }

        // These names are not allowed to be free through a class (see

        // drop_class_free) unless a nested child needs them. Keep FREE

        // on this table; compile treats the load as a global.

        if (scope == FREE && ste->ste_type == ClassBlock &&

                _PyST_IsClassClosureName(k)) {

            int child_needs_free = is_free_in_any_child(comp, k);

            if (child_needs_free < 0) {

                goto error;

            }

            if (!child_needs_free) {

                if (PySet_Discard(comp_free, k) < 0) {

                    goto error;

                }

            }

            continue;

        }

        int is_def_bound = 0;

        if (existing) {

            long flags = PyLong_AsLong(existing);

            if (flags == -1 && PyErr_Occurred()) {

                goto error;

            }

            is_def_bound = flags & DEF_BOUND;

        }

        // Loads here are in the enclosing compilation unit.

        if (scope == FREE && (comp_flags & USE) &&

                !symtable_add_flag(ste->ste_symbols, k, USE)) {

            goto error;

        }

        if (is_def_bound && ste->ste_type != ClassBlock) {

            // free vars in comprehension that are locals in outer scope can

            // now simply be locals, unless they are free in comp children,

            // needed as cells by sibling nested scopes, or if the outer

            // scope is a class block

            int ok = is_free_in_any_child(comp, k);

            if (ok < 0) {

                goto error;

            }

            if (!ok) {

                int in_newfree = PySet_Contains(outer_newfree, k);

                if (in_newfree < 0) {

                    goto error;

                }

                if (!in_newfree) {

                    if (PySet_Discard(comp_free, k) < 0) {

                        goto error;

                    }

                }

            }

        }

        else if (!existing) {

            assert(scope != FREE || PySet_Contains(comp_free, k) == 1);

        }

    }

    return 1;

error:

    return 0;

}

#undef SET_SCOPE

/* If a name is defined in free and also in locals, then this block

   provides the binding for the free variable.  The name should be

   marked CELL in this block and removed from the free list.

   Note that the current block's free variables are included in free.

   That's safe because no name can be free and local in the same scope.

*/

static int

analyze_cells(PyObject *scopes, PyObject *free, PyObject *inlined_cells)

{

    PyObject *name, *v, *v_cell;

    int success = 0;

    Py_ssize_t pos = 0;

    v_cell = PyLong_FromLong(CELL);

    if (!v_cell)

        return 0;

    while (PyDict_Next(scopes, &pos, &name, &v)) {

        long scope = PyLong_AsLong(v);

        if (scope == -1 && PyErr_Occurred()) {

            goto error;

        }

        if (scope != LOCAL)

            continue;

        int contains = PySet_Contains(free, name);

        if (contains < 0) {

            goto error;

        }

        if (!contains) {

            contains = PySet_Contains(inlined_cells, name);

            if (contains < 0) {

                goto error;

            }

            if (!contains) {

                continue;

            }

        }

        /* Replace LOCAL with CELL for this name, and remove

           from free. It is safe to replace the value of name

           in the dict, because it will not cause a resize.

         */

        if (PyDict_SetItem(scopes, name, v_cell) < 0)

            goto error;

        if (PySet_Discard(free, name) < 0)

            goto error;

    }

    success = 1;

 error:

    Py_DECREF(v_cell);

    return success;

}

static int

drop_class_free(PySTEntryObject *ste, PyObject *free)

{

    int res;