#include "Python.h"

#include "Python-ast.h"

#include "code.h"

#include "symtable.h"

#include "structmember.h"

/* error strings used for warnings */

#define GLOBAL_AFTER_ASSIGN \

"name '%.400s' is assigned to before global declaration"

#define GLOBAL_AFTER_USE \

"name '%.400s' is used prior to global declaration"

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

#define RETURN_VAL_IN_GENERATOR \

    "'return' with argument inside generator"

static PySTEntryObject *

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

	      void *key, int lineno)

{

	PySTEntryObject *ste = NULL;

	PyObject *k;

	k = PyLong_FromVoidPtr(key);

	if (k == NULL)

		goto fail;

	ste = PyObject_New(PySTEntryObject, &PySTEntry_Type);

	if (ste == NULL)

		goto fail;

	ste->ste_table = st;

	ste->ste_id = k;

	ste->ste_tmpname = 0;

	ste->ste_name = name;

	Py_INCREF(name);

	ste->ste_symbols = NULL;

	ste->ste_varnames = NULL;

	ste->ste_children = NULL;

	ste->ste_symbols = PyDict_New();

	if (ste->ste_symbols == NULL)

	    goto fail;

	ste->ste_varnames = PyList_New(0);

	if (ste->ste_varnames == NULL)

	    goto fail;

	ste->ste_children = PyList_New(0);

	if (ste->ste_children == NULL)

	    goto fail;

	ste->ste_type = block;

	ste->ste_unoptimized = 0;

	ste->ste_nested = 0;

	ste->ste_free = 0;

	ste->ste_varargs = 0;

	ste->ste_varkeywords = 0;

	ste->ste_opt_lineno = 0;

	ste->ste_tmpname = 0;

	ste->ste_lineno = lineno;

	if (st->st_cur != NULL &&

	    (st->st_cur->ste_nested ||

	     st->st_cur->ste_type == FunctionBlock))

		ste->ste_nested = 1;

	ste->ste_child_free = 0;

	ste->ste_generator = 0;

	ste->ste_returns_value = 0;

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

	    goto fail;

	return ste;

 fail:

	Py_XDECREF(ste);

	return NULL;

}

static PyObject *

ste_repr(PySTEntryObject *ste)

{

	char buf[256];

	PyOS_snprintf(buf, sizeof(buf),

		      "<symtable entry %.100s(%ld), line %d>",

		      PyString_AS_STRING(ste->ste_name),

		      PyInt_AS_LONG(ste->ste_id), ste->ste_lineno);

	return PyString_FromString(buf);

}

static void

ste_dealloc(PySTEntryObject *ste)

{

	ste->ste_table = NULL;

	Py_XDECREF(ste->ste_id);

	Py_XDECREF(ste->ste_name);

	Py_XDECREF(ste->ste_symbols);

	Py_XDECREF(ste->ste_varnames);

	Py_XDECREF(ste->ste_children);

	PyObject_Del(ste);

}

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

static PyMemberDef ste_memberlist[] = {

	{"id",       T_OBJECT, OFF(ste_id), READONLY},

	{"name",     T_OBJECT, OFF(ste_name), READONLY},

	{"symbols",  T_OBJECT, OFF(ste_symbols), READONLY},

	{"varnames", T_OBJECT, OFF(ste_varnames), READONLY},

	{"children", T_OBJECT, OFF(ste_children), READONLY},

        {"optimized",T_INT,    OFF(ste_unoptimized), READONLY},

	{"nested",   T_INT,    OFF(ste_nested), READONLY},

	{"type",     T_INT,    OFF(ste_type), READONLY},

	{"lineno",   T_INT,    OFF(ste_lineno), READONLY},

	{NULL}

};

PyTypeObject PySTEntry_Type = {

	PyVarObject_HEAD_INIT(&PyType_Type, 0)

	"symtable entry",

	sizeof(PySTEntryObject),

	0,

	(destructor)ste_dealloc,                /* tp_dealloc */

	0,                                      /* tp_print */

	0,			               /* tp_getattr */

	0,					/* tp_setattr */

	0,			                /* tp_compare */

	(reprfunc)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_warn(struct symtable *st, char *msg, int lineno);

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

				_Py_block_ty block, void *ast, int lineno);

static int symtable_exit_block(struct symtable *st, void *ast);

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_genexp(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_slice(struct symtable *st, slice_ty);

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

static int symtable_visit_params_nested(struct symtable *st, asdl_seq *args);

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

static identifier top = NULL, lambda = NULL, genexpr = NULL;

#define GET_IDENTIFIER(VAR) \

	((VAR) ? (VAR) : ((VAR) = PyString_InternFromString(# VAR)))

#define DUPLICATE_ARGUMENT \

"duplicate argument '%s' in function definition"

static struct symtable *

symtable_new(void)

{

	struct symtable *st;

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

	if (st == NULL)

		return NULL;

	st->st_filename = NULL;

	st->st_symbols = NULL;

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

		goto fail;

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

		goto fail; 

	st->st_cur = NULL;

	st->st_tmpname = 0;

	st->st_private = NULL;

	return st;

 fail:

	PySymtable_Free(st);

	return NULL;

}

struct symtable *

PySymtable_Build(mod_ty mod, const char *filename, PyFutureFeatures *future)

{

	struct symtable *st = symtable_new();

	asdl_seq *seq;

	int i;

	if (st == NULL)

		return st;

	st->st_filename = filename;

	st->st_future = future;

	if (!GET_IDENTIFIER(top) ||

	    !symtable_enter_block(st, top, ModuleBlock, (void *)mod, 0)) {

		PySymtable_Free(st);

		return NULL;

	}

	st->st_top = st->st_cur;

	st->st_cur->ste_unoptimized = OPT_TOPLEVEL;

	/* Any other top-level initialization? */

	switch (mod->kind) {

	case Module_kind:

		seq = mod->v.Module.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 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 Suite_kind:

		PyErr_SetString(PyExc_RuntimeError,

				"this compiler does not handle Suites");

		goto error;

	}

	if (!symtable_exit_block(st, (void *)mod)) {

		PySymtable_Free(st);

		return NULL;

	}

	if (symtable_analyze(st))

		return st;

	PySymtable_Free(st);

	return NULL;

 error:

	(void) symtable_exit_block(st, (void *)mod);

	PySymtable_Free(st);

	return NULL;

}

void

PySymtable_Free(struct symtable *st)

{

	Py_XDECREF(st->st_symbols);

	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;

	v = PyDict_GetItem(st->st_symbols, k);

	if (v) {

		assert(PySTEntry_Check(v));

		Py_INCREF(v);

	}

	else {

		PyErr_SetString(PyExc_KeyError,

				"unknown symbol table entry");

	}

	Py_DECREF(k);

	return (PySTEntryObject *)v;

}

int 

PyST_GetScope(PySTEntryObject *ste, PyObject *name)

{

	PyObject *v = PyDict_GetItem(ste->ste_symbols, name);

	if (!v)

		return 0;

	assert(PyInt_Check(v));

	return (PyInt_AS_LONG(v) >> SCOPE_OFF) & SCOPE_MASK;

}

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

   The next several functions are helpers for PySymtable_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 free 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: the name is a parameter 

   here, the name is used by 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 the variable is free or an implicit global.

   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 free 

   in a child, the variable is marked as a cell.  The current function 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.

   The sets of bound and free variables are implemented as dictionaries

   mapping strings to None.

*/

#define SET_SCOPE(DICT, NAME, I) { \

	PyObject *o = PyInt_FromLong(I); \

	if (!o) \

		return 0; \

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

		Py_DECREF(o); \

		return 0; \

	} \

	Py_DECREF(o); \

}

/* Decide on scope of name, given flags.

   The dicts passed in as arguments are modified as necessary.

   ste is passed so that flags can be updated.

*/

static int 

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

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

	     PyObject *global)

{

	if (flags & DEF_GLOBAL) {

		if (flags & DEF_PARAM) {

			PyErr_Format(PyExc_SyntaxError,

				     "name '%s' is local and global",

				     PyString_AS_STRING(name));

			PyErr_SyntaxLocation(ste->ste_table->st_filename,

					     ste->ste_lineno);

			return 0;

		}

		SET_SCOPE(dict, name, GLOBAL_EXPLICIT);

		if (PyDict_SetItem(global, name, Py_None) < 0)

			return 0;

		if (bound && PyDict_GetItem(bound, name)) {

			if (PyDict_DelItem(bound, name) < 0)

				return 0;

		}

		return 1;

	}

	if (flags & DEF_BOUND) {

		SET_SCOPE(dict, name, LOCAL);

		if (PyDict_SetItem(local, name, Py_None) < 0)

			return 0;

		if (PyDict_GetItem(global, name)) {

			if (PyDict_DelItem(global, name) < 0)

				return 0;

		}

		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 && PyDict_GetItem(bound, name)) {

		SET_SCOPE(dict, name, FREE);

		ste->ste_free = 1;

		if (PyDict_SetItem(free, name, Py_None) < 0)

			return 0;

		return 1;

	}

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

	   explicit?  It could also be global implicit.

	 */

	else if (global && PyDict_GetItem(global, name)) {

		SET_SCOPE(dict, name, GLOBAL_EXPLICIT);

		return 1;

	}

	else {

		if (ste->ste_nested)

			ste->ste_free = 1;

		SET_SCOPE(dict, name, GLOBAL_IMPLICIT);

		return 1;

	}

	return 0; /* Can't get here */

}

#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 *scope, PyObject *free)

{

        PyObject *name, *v, *w;

	int success = 0;

	Py_ssize_t pos = 0;

	w = PyInt_FromLong(CELL);

	if (!w)

		return 0;

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

		long flags;

		assert(PyInt_Check(v));

		flags = PyInt_AS_LONG(v);

		if (flags != LOCAL)

			continue;

		if (!PyDict_GetItem(free, name))

			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(scope, name, w) < 0)

			goto error;

		if (!PyDict_DelItem(free, name) < 0)

			goto error;

	}

	success = 1;

 error:

	Py_DECREF(w);

	return success;

}

/* Check for illegal statements in unoptimized namespaces */

static int

check_unoptimized(const PySTEntryObject* ste) {

	char buf[300];

	const char* trailer;

	if (ste->ste_type != FunctionBlock || !ste->ste_unoptimized

	    || !(ste->ste_free || ste->ste_child_free))

		return 1;

	trailer = (ste->ste_child_free ? 

		       "contains a nested function with free variables" :

			       "is a nested function");

	switch (ste->ste_unoptimized) {

	case OPT_TOPLEVEL: /* exec / import * at top-level is fine */

	case OPT_EXEC: /* qualified exec is fine */

		return 1;

	case OPT_IMPORT_STAR:

		PyOS_snprintf(buf, sizeof(buf), 

			      "import * is not allowed in function '%.100s' "

			      "because it is %s",

			      PyString_AS_STRING(ste->ste_name), trailer);

		break;

	case OPT_BARE_EXEC:

		PyOS_snprintf(buf, sizeof(buf),

			      "unqualified exec is not allowed in function "

			      "'%.100s' it %s",

			      PyString_AS_STRING(ste->ste_name), trailer);

		break;

	default:

		PyOS_snprintf(buf, sizeof(buf), 

			      "function '%.100s' uses import * and bare exec, "

			      "which are illegal because it %s",

			      PyString_AS_STRING(ste->ste_name), trailer);

		break;

	}

	PyErr_SetString(PyExc_SyntaxError, buf);

	PyErr_SyntaxLocation(ste->ste_table->st_filename, 

			     ste->ste_opt_lineno);

	return 0;

}

/* Enter the final scope information into the st_symbols dict. 

 * 

 * All arguments are dicts.  Modifies symbols, others are read-only.

*/

static int

update_symbols(PyObject *symbols, PyObject *scope, 

               PyObject *bound, PyObject *free, int classflag)

{

	PyObject *name, *v, *u, *w, *free_value = NULL;

	Py_ssize_t pos = 0;

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

		long i, flags;