1 /*

     2  * This file compiles an abstract syntax tree (AST) into Python bytecode.

     3  *

     4  * The primary entry point is PyAST_Compile(), which returns a

     5  * PyCodeObject.  The compiler makes several passes to build the code

     6  * object:

     7  *   1. Checks for future statements.  See future.c

     8  *   2. Builds a symbol table.	See symtable.c.

     9  *   3. Generate code for basic blocks.  See compiler_mod() in this file.

    10  *   4. Assemble the basic blocks into final code.  See assemble() in

    11  *	this file.	 

    12  *   5. Optimize the byte code (peephole optimizations).  See peephole.c

    13  *

    14  * Note that compiler_mod() suggests module, but the module ast type

    15  * (mod_ty) has cases for expressions and interactive statements.

    16  *

    17  * CAUTION: The VISIT_* macros abort the current function when they

    18  * encounter a problem. So don't invoke them when there is memory

    19  * which needs to be released. Code blocks are OK, as the compiler

    20  * structure takes care of releasing those.  Use the arena to manage

    21  * objects.

    22  */

    23 

    24 #include "Python.h"

    25 

    26 #include "Python-ast.h"

    27 #include "node.h"

    28 #include "pyarena.h"

    29 #include "ast.h"

    30 #include "code.h"

    31 #include "compile.h"

    32 #include "symtable.h"

    33 #include "opcode.h"

    34 

    35 int Py_OptimizeFlag = 0;

    36 

    37 #define DEFAULT_BLOCK_SIZE 16

    38 #define DEFAULT_BLOCKS 8

    39 #define DEFAULT_CODE_SIZE 128

    40 #define DEFAULT_LNOTAB_SIZE 16

    41 

    42 struct instr {

    43 	unsigned i_jabs : 1;

    44 	unsigned i_jrel : 1;

    45 	unsigned i_hasarg : 1;

    46 	unsigned char i_opcode;

    47 	int i_oparg;

    48 	struct basicblock_ *i_target; /* target block (if jump instruction) */

    49 	int i_lineno;

    50 };

    51 

    52 typedef struct basicblock_ {

    53     /* Each basicblock in a compilation unit is linked via b_list in the

    54        reverse order that the block are allocated.  b_list points to the next

    55        block, not to be confused with b_next, which is next by control flow. */

    56 	struct basicblock_ *b_list;

    57 	/* number of instructions used */

    58 	int b_iused;

    59 	/* length of instruction array (b_instr) */

    60 	int b_ialloc;

    61 	/* pointer to an array of instructions, initially NULL */

    62 	struct instr *b_instr;

    63 	/* If b_next is non-NULL, it is a pointer to the next

    64 	   block reached by normal control flow. */

    65 	struct basicblock_ *b_next;

    66 	/* b_seen is used to perform a DFS of basicblocks. */

    67 	unsigned b_seen : 1;

    68 	/* b_return is true if a RETURN_VALUE opcode is inserted. */

    69 	unsigned b_return : 1;

    70 	/* depth of stack upon entry of block, computed by stackdepth() */

    71 	int b_startdepth;

    72 	/* instruction offset for block, computed by assemble_jump_offsets() */

    73 	int b_offset;

    74 } basicblock;

    75 

    76 /* fblockinfo tracks the current frame block.

    77 

    78 A frame block is used to handle loops, try/except, and try/finally.

    79 It's called a frame block to distinguish it from a basic block in the

    80 compiler IR.

    81 */

    82 

    83 enum fblocktype { LOOP, EXCEPT, FINALLY_TRY, FINALLY_END };

    84 

    85 struct fblockinfo {

    86 	enum fblocktype fb_type;

    87 	basicblock *fb_block;

    88 };

    89 

    90 /* The following items change on entry and exit of code blocks.

    91    They must be saved and restored when returning to a block.

    92 */

    93 struct compiler_unit {

    94 	PySTEntryObject *u_ste;

    95 

    96 	PyObject *u_name;

    97 	/* The following fields are dicts that map objects to

    98 	   the index of them in co_XXX.	 The index is used as

    99 	   the argument for opcodes that refer to those collections.

   100 	*/

   101 	PyObject *u_consts;    /* all constants */

   102 	PyObject *u_names;     /* all names */

   103 	PyObject *u_varnames;  /* local variables */

   104 	PyObject *u_cellvars;  /* cell variables */

   105 	PyObject *u_freevars;  /* free variables */

   106 

   107 	PyObject *u_private;	/* for private name mangling */

   108 

   109 	int u_argcount;	   /* number of arguments for block */ 

   110 	/* Pointer to the most recently allocated block.  By following b_list

   111 	   members, you can reach all early allocated blocks. */

   112 	basicblock *u_blocks;

   113 	basicblock *u_curblock; /* pointer to current block */

   114 	int u_tmpname;		/* temporary variables for list comps */

   115 

   116 	int u_nfblocks;

   117 	struct fblockinfo u_fblock[CO_MAXBLOCKS];

   118 

   119 	int u_firstlineno; /* the first lineno of the block */

   120 	int u_lineno;	   /* the lineno for the current stmt */

   121 	bool u_lineno_set; /* boolean to indicate whether instr

   122 			      has been generated with current lineno */

   123 };

   124 

   125 /* This struct captures the global state of a compilation.  

   126 

   127 The u pointer points to the current compilation unit, while units

   128 for enclosing blocks are stored in c_stack.	The u and c_stack are

   129 managed by compiler_enter_scope() and compiler_exit_scope().

   130 */

   131 

   132 struct compiler {

   133 	const char *c_filename;

   134 	struct symtable *c_st;

   135 	PyFutureFeatures *c_future; /* pointer to module's __future__ */

   136 	PyCompilerFlags *c_flags;

   137 

   138 	int c_interactive;	 /* true if in interactive mode */

   139 	int c_nestlevel;

   140 

   141 	struct compiler_unit *u; /* compiler state for current block */

   142 	PyObject *c_stack;	 /* Python list holding compiler_unit ptrs */

   143 	char *c_encoding;	 /* source encoding (a borrowed reference) */

   144 	PyArena *c_arena;	 /* pointer to memory allocation arena */

   145 };

   146 

   147 static int compiler_enter_scope(struct compiler *, identifier, void *, int);

   148 static void compiler_free(struct compiler *);

   149 static basicblock *compiler_new_block(struct compiler *);

   150 static int compiler_next_instr(struct compiler *, basicblock *);

   151 static int compiler_addop(struct compiler *, int);

   152 static int compiler_addop_o(struct compiler *, int, PyObject *, PyObject *);

   153 static int compiler_addop_i(struct compiler *, int, int);

   154 static int compiler_addop_j(struct compiler *, int, basicblock *, int);

   155 static basicblock *compiler_use_new_block(struct compiler *);

   156 static int compiler_error(struct compiler *, const char *);

   157 static int compiler_nameop(struct compiler *, identifier, expr_context_ty);

   158 

   159 static PyCodeObject *compiler_mod(struct compiler *, mod_ty);

   160 static int compiler_visit_stmt(struct compiler *, stmt_ty);

   161 static int compiler_visit_keyword(struct compiler *, keyword_ty);

   162 static int compiler_visit_expr(struct compiler *, expr_ty);

   163 static int compiler_augassign(struct compiler *, stmt_ty);

   164 static int compiler_visit_slice(struct compiler *, slice_ty,

   165 				expr_context_ty);

   166 

   167 static int compiler_push_fblock(struct compiler *, enum fblocktype,

   168 				basicblock *);

   169 static void compiler_pop_fblock(struct compiler *, enum fblocktype,

   170 				basicblock *);

   171 /* Returns true if there is a loop on the fblock stack. */

   172 static int compiler_in_loop(struct compiler *);

   173 

   174 static int inplace_binop(struct compiler *, operator_ty);

   175 static int expr_constant(expr_ty e);

   176 

   177 static int compiler_with(struct compiler *, stmt_ty);

   178 

   179 static PyCodeObject *assemble(struct compiler *, int addNone);

   180 static PyObject *__doc__;

   181 

   182 PyObject *

   183 _Py_Mangle(PyObject *privateobj, PyObject *ident)

   184 {

   185 	/* Name mangling: __private becomes _classname__private.

   186 	   This is independent from how the name is used. */

   187 	const char *p, *name = PyString_AsString(ident);

   188 	char *buffer;

   189 	size_t nlen, plen;

   190 	if (privateobj == NULL || !PyString_Check(privateobj) ||

   191 	    name == NULL || name[0] != '_' || name[1] != '_') {

   192 		Py_INCREF(ident);

   193 		return ident;

   194 	}

   195 	p = PyString_AsString(privateobj);

   196 	nlen = strlen(name);

   197 	/* Don't mangle __id__ or names with dots.

   198 

   199 	   The only time a name with a dot can occur is when

   200 	   we are compiling an import statement that has a 

   201 	   package name.

   202 

   203 	   TODO(jhylton): Decide whether we want to support

   204 	   mangling of the module name, e.g. __M.X.

   205 	*/

   206 	if ((name[nlen-1] == '_' && name[nlen-2] == '_') 

   207 	    || strchr(name, '.')) {

   208 		Py_INCREF(ident);

   209 		return ident; /* Don't mangle __whatever__ */

   210 	}

   211 	/* Strip leading underscores from class name */

   212 	while (*p == '_')

   213 		p++;

   214 	if (*p == '\0') {

   215 		Py_INCREF(ident);

   216 		return ident; /* Don't mangle if class is just underscores */

   217 	}

   218 	plen = strlen(p);

   219 

   220 	assert(1 <= PY_SSIZE_T_MAX - nlen);

   221 	assert(1 + nlen <= PY_SSIZE_T_MAX - plen);

   222 

   223 	ident = PyString_FromStringAndSize(NULL, 1 + nlen + plen);

   224 	if (!ident)

   225 		return 0;

   226 	/* ident = "_" + p[:plen] + name # i.e. 1+plen+nlen bytes */

   227 	buffer = PyString_AS_STRING(ident);

   228 	buffer[0] = '_';

   229 	strncpy(buffer+1, p, plen);

   230 	strcpy(buffer+1+plen, name);

   231 	return ident;

   232 }

   233 

   234 static int

   235 compiler_init(struct compiler *c)

   236 {

   237 	memset(c, 0, sizeof(struct compiler));

   238 

   239 	c->c_stack = PyList_New(0);

   240 	if (!c->c_stack)

   241 		return 0;

   242 

   243 	return 1;

   244 }

   245 

   246 PyCodeObject *

   247 PyAST_Compile(mod_ty mod, const char *filename, PyCompilerFlags *flags,

   248 	      PyArena *arena)

   249 {

   250 	struct compiler c;

   251 	PyCodeObject *co = NULL;

   252 	PyCompilerFlags local_flags;

   253 	int merged;

   254 

   255 	if (!__doc__) {

   256 		__doc__ = PyString_InternFromString("__doc__");

   257 		if (!__doc__)

   258 			return NULL;

   259 	}

   260 

   261 	if (!compiler_init(&c))

   262 		return NULL;

   263 	c.c_filename = filename;

   264 	c.c_arena = arena;

   265 	c.c_future = PyFuture_FromAST(mod, filename);

   266 	if (c.c_future == NULL)

   267 		goto finally;

   268 	if (!flags) {

   269 		local_flags.cf_flags = 0;

   270 		flags = &local_flags;

   271 	}

   272 	merged = c.c_future->ff_features | flags->cf_flags;

   273 	c.c_future->ff_features = merged;

   274 	flags->cf_flags = merged;

   275 	c.c_flags = flags;

   276 	c.c_nestlevel = 0;

   277 

   278 	c.c_st = PySymtable_Build(mod, filename, c.c_future);

   279 	if (c.c_st == NULL) {

   280 		if (!PyErr_Occurred())

   281 			PyErr_SetString(PyExc_SystemError, "no symtable");

   282 		goto finally;

   283 	}

   284 

   285 	/* XXX initialize to NULL for now, need to handle */

   286 	c.c_encoding = NULL;

   287 

   288 	co = compiler_mod(&c, mod);

   289 

   290  finally:

   291 	compiler_free(&c);

   292 	assert(co || PyErr_Occurred());

   293 	return co;

   294 }

   295 

   296 PyCodeObject *

   297 PyNode_Compile(struct _node *n, const char *filename)

   298 {

   299 	PyCodeObject *co = NULL;

   300 	mod_ty mod;

   301 	PyArena *arena = PyArena_New();

   302 	if (!arena)

   303 		return NULL;

   304 	mod = PyAST_FromNode(n, NULL, filename, arena);

   305 	if (mod)

   306 		co = PyAST_Compile(mod, filename, NULL, arena);

   307 	PyArena_Free(arena);

   308 	return co;

   309 }

   310 

   311 static void

   312 compiler_free(struct compiler *c)

   313 {

   314 	if (c->c_st)

   315 		PySymtable_Free(c->c_st);

   316 	if (c->c_future)

   317 		PyObject_Free(c->c_future);

   318 	Py_DECREF(c->c_stack);

   319 }

   320 

   321 static PyObject *

   322 list2dict(PyObject *list)

   323 {

   324 	Py_ssize_t i, n;

   325 	PyObject *v, *k;

   326 	PyObject *dict = PyDict_New();

   327 	if (!dict) return NULL;

   328 

   329 	n = PyList_Size(list);

   330 	for (i = 0; i < n; i++) {

   331 		v = PyInt_FromLong(i);

   332 		if (!v) {

   333 			Py_DECREF(dict);

   334 			return NULL;

   335 		}

   336 		k = PyList_GET_ITEM(list, i);

   337 		k = PyTuple_Pack(2, k, k->ob_type);

   338 		if (k == NULL || PyDict_SetItem(dict, k, v) < 0) {

   339 			Py_XDECREF(k);

   340 			Py_DECREF(v);

   341 			Py_DECREF(dict);

   342 			return NULL;

   343 		}

   344 		Py_DECREF(k);

   345 		Py_DECREF(v);

   346 	}

   347 	return dict;

   348 }

   349 

   350 /* Return new dict containing names from src that match scope(s).

   351 

   352 src is a symbol table dictionary.  If the scope of a name matches

   353 either scope_type or flag is set, insert it into the new dict.	The

   354 values are integers, starting at offset and increasing by one for

   355 each key.

   356 */

   357 

   358 static PyObject *

   359 dictbytype(PyObject *src, int scope_type, int flag, int offset)

   360 {

   361 	Py_ssize_t pos = 0, i = offset, scope;

   362 	PyObject *k, *v, *dest = PyDict_New();

   363 

   364 	assert(offset >= 0);

   365 	if (dest == NULL)

   366 		return NULL;

   367 

   368 	while (PyDict_Next(src, &pos, &k, &v)) {

   369 		/* XXX this should probably be a macro in symtable.h */

   370 		assert(PyInt_Check(v));

   371 		scope = (PyInt_AS_LONG(v) >> SCOPE_OFF) & SCOPE_MASK;

   372 

   373 		if (scope == scope_type || PyInt_AS_LONG(v) & flag) {

   374 			PyObject *tuple, *item = PyInt_FromLong(i);

   375 			if (item == NULL) {

   376 				Py_DECREF(dest);

   377 				return NULL;

   378 			}

   379 			i++;

   380 			tuple = PyTuple_Pack(2, k, k->ob_type);

   381 			if (!tuple || PyDict_SetItem(dest, tuple, item) < 0) {

   382 				Py_DECREF(item);

   383 				Py_DECREF(dest);

   384 				Py_XDECREF(tuple);

   385 				return NULL;

   386 			}

   387 			Py_DECREF(item);

   388 			Py_DECREF(tuple);

   389 		}

   390 	}

   391 	return dest;

   392 }

   393 

   394 static void

   395 compiler_unit_check(struct compiler_unit *u)

   396 {

   397 	basicblock *block;

   398 	for (block = u->u_blocks; block != NULL; block = block->b_list) {

   399 		assert((void *)block != (void *)0xcbcbcbcb);

   400 		assert((void *)block != (void *)0xfbfbfbfb);

   401 		assert((void *)block != (void *)0xdbdbdbdb);

   402 		if (block->b_instr != NULL) {

   403 			assert(block->b_ialloc > 0);

   404 			assert(block->b_iused > 0);

   405 			assert(block->b_ialloc >= block->b_iused);

   406 		}

   407 		else {

   408 			assert (block->b_iused == 0);

   409 			assert (block->b_ialloc == 0);

   410 		}

   411 	}

   412 }

   413 

   414 static void

   415 compiler_unit_free(struct compiler_unit *u)

   416 {

   417 	basicblock *b, *next;

   418 

   419 	compiler_unit_check(u);

   420 	b = u->u_blocks;

   421 	while (b != NULL) {

   422 		if (b->b_instr)

   423 			PyObject_Free((void *)b->b_instr);

   424 		next = b->b_list;

   425 		PyObject_Free((void *)b);

   426 		b = next;

   427 	}

   428 	Py_CLEAR(u->u_ste);

   429 	Py_CLEAR(u->u_name);

   430 	Py_CLEAR(u->u_consts);

   431 	Py_CLEAR(u->u_names);

   432 	Py_CLEAR(u->u_varnames);

   433 	Py_CLEAR(u->u_freevars);

   434 	Py_CLEAR(u->u_cellvars);

   435 	Py_CLEAR(u->u_private);

   436 	PyObject_Free(u);

   437 }

   438 

   439 static int

   440 compiler_enter_scope(struct compiler *c, identifier name, void *key,

   441 		     int lineno)

   442 {

   443 	struct compiler_unit *u;

   444 

   445 	u = (struct compiler_unit *)PyObject_Malloc(sizeof(

   446 						struct compiler_unit));

   447 	if (!u) {

   448 		PyErr_NoMemory();

   449 		return 0;

   450 	}

   451 	memset(u, 0, sizeof(struct compiler_unit));

   452 	u->u_argcount = 0;

   453 	u->u_ste = PySymtable_Lookup(c->c_st, key);

   454 	if (!u->u_ste) {

   455 		compiler_unit_free(u);

   456 		return 0;

   457 	}

   458 	Py_INCREF(name);

   459 	u->u_name = name;

   460 	u->u_varnames = list2dict(u->u_ste->ste_varnames);

   461 	u->u_cellvars = dictbytype(u->u_ste->ste_symbols, CELL, 0, 0);

   462 	if (!u->u_varnames || !u->u_cellvars) {

   463 		compiler_unit_free(u);

   464 		return 0;

   465 	}

   466 

   467 	u->u_freevars = dictbytype(u->u_ste->ste_symbols, FREE, DEF_FREE_CLASS,

   468 				   PyDict_Size(u->u_cellvars));

   469 	if (!u->u_freevars) {

   470 		compiler_unit_free(u);

   471 		return 0;

   472 	}

   473 

   474 	u->u_blocks = NULL;

   475 	u->u_tmpname = 0;

   476 	u->u_nfblocks = 0;

   477 	u->u_firstlineno = lineno;

   478 	u->u_lineno = 0;

   479 	u->u_lineno_set = false;

   480 	u->u_consts = PyDict_New();

   481 	if (!u->u_consts) {

   482 		compiler_unit_free(u);

   483 		return 0;

   484 	}

   485 	u->u_names = PyDict_New();

   486 	if (!u->u_names) {

   487 		compiler_unit_free(u);

   488 		return 0;

   489 	}

   490 

   491 	u->u_private = NULL;

   492 

   493 	/* Push the old compiler_unit on the stack. */

   494 	if (c->u) {

   495 		PyObject *wrapper = PyCObject_FromVoidPtr(c->u, NULL);

   496 		if (!wrapper || PyList_Append(c->c_stack, wrapper) < 0) {

   497 			Py_XDECREF(wrapper);

   498 			compiler_unit_free(u);

   499 			return 0;

   500 		}

   501 		Py_DECREF(wrapper);

   502 		u->u_private = c->u->u_private;

   503 		Py_XINCREF(u->u_private);

   504 	}

   505 	c->u = u;

   506 

   507 	c->c_nestlevel++;

   508 	if (compiler_use_new_block(c) == NULL)

   509 		return 0;

   510 

   511 	return 1;

   512 }

   513 

   514 static void

   515 compiler_exit_scope(struct compiler *c)

   516 {

   517 	int n;

   518 	PyObject *wrapper;

   519 

   520 	c->c_nestlevel--;

   521 	compiler_unit_free(c->u);

   522 	/* Restore c->u to the parent unit. */

   523 	n = PyList_GET_SIZE(c->c_stack) - 1;

   524 	if (n >= 0) {

   525 		wrapper = PyList_GET_ITEM(c->c_stack, n);

   526 		c->u = (struct compiler_unit *)PyCObject_AsVoidPtr(wrapper);

   527 		assert(c->u);

   528 		/* we are deleting from a list so this really shouldn't fail */

   529 		if (PySequence_DelItem(c->c_stack, n) < 0)

   530 			Py_FatalError("compiler_exit_scope()");

   531 		compiler_unit_check(c->u);

   532 	}

   533 	else

   534 		c->u = NULL;

   535 

   536 }

   537 

   538 /* Allocate a new "anonymous" local variable.

   539    Used by list comprehensions and with statements.

   540 */

   541 

   542 static PyObject *

   543 compiler_new_tmpname(struct compiler *c)

   544 {

   545 	char tmpname[256];

   546 	PyOS_snprintf(tmpname, sizeof(tmpname), "_[%d]", ++c->u->u_tmpname);

   547 	return PyString_FromString(tmpname);

   548 }

   549 

   550 /* Allocate a new block and return a pointer to it.

   551    Returns NULL on error.

   552 */

   553 

   554 static basicblock *

   555 compiler_new_block(struct compiler *c)

   556 {

   557 	basicblock *b;

   558 	struct compiler_unit *u;

   559 

   560 	u = c->u;

   561 	b = (basicblock *)PyObject_Malloc(sizeof(basicblock));

   562 	if (b == NULL) {

   563 		PyErr_NoMemory();

   564 		return NULL;

   565 	}

   566 	memset((void *)b, 0, sizeof(basicblock));

   567 	/* Extend the singly linked list of blocks with new block. */

   568 	b->b_list = u->u_blocks;

   569 	u->u_blocks = b;

   570 	return b;

   571 }

   572 

   573 static basicblock *

   574 compiler_use_new_block(struct compiler *c)

   575 {

   576 	basicblock *block = compiler_new_block(c);

   577 	if (block == NULL)

   578 		return NULL;

   579 	c->u->u_curblock = block;

   580 	return block;

   581 }

   582 

   583 static basicblock *

   584 compiler_next_block(struct compiler *c)

   585 {

   586 	basicblock *block = compiler_new_block(c);

   587 	if (block == NULL)

   588 		return NULL;

   589 	c->u->u_curblock->b_next = block;

   590 	c->u->u_curblock = block;

   591 	return block;

   592 }

   593 

   594 static basicblock *

   595 compiler_use_next_block(struct compiler *c, basicblock *block)

   596 {

   597 	assert(block != NULL);

   598 	c->u->u_curblock->b_next = block;

   599 	c->u->u_curblock = block;

   600 	return block;

   601 }

   602 

   603 /* Returns the offset of the next instruction in the current block's

   604    b_instr array.  Resizes the b_instr as necessary.

   605    Returns -1 on failure.

   606 */

   607 

   608 static int

   609 compiler_next_instr(struct compiler *c, basicblock *b)

   610 {

   611 	assert(b != NULL);

   612 	if (b->b_instr == NULL) {

   613 		b->b_instr = (struct instr *)PyObject_Malloc(

   614 				 sizeof(struct instr) * DEFAULT_BLOCK_SIZE);

   615 		if (b->b_instr == NULL) {

   616 			PyErr_NoMemory();

   617 			return -1;

   618 		}

   619 		b->b_ialloc = DEFAULT_BLOCK_SIZE;

   620 		memset((char *)b->b_instr, 0,

   621 		       sizeof(struct instr) * DEFAULT_BLOCK_SIZE);

   622 	}

   623 	else if (b->b_iused == b->b_ialloc) {

   624 		struct instr *tmp;

   625 		size_t oldsize, newsize;

   626 		oldsize = b->b_ialloc * sizeof(struct instr);

   627 		newsize = oldsize << 1;

   628 

   629 		if (oldsize > (PY_SIZE_MAX >> 1)) {

   630 			PyErr_NoMemory();

   631 			return -1;

   632 		}

   633 

   634 		if (newsize == 0) {

   635 			PyErr_NoMemory();

   636 			return -1;

   637 		}

   638 		b->b_ialloc <<= 1;

   639 		tmp = (struct instr *)PyObject_Realloc(

   640 						(void *)b->b_instr, newsize);

   641 		if (tmp == NULL) {

   642 			PyErr_NoMemory();

   643 			return -1;

   644 		}

   645 		b->b_instr = tmp;

   646 		memset((char *)b->b_instr + oldsize, 0, newsize - oldsize);

   647 	}

   648 	return b->b_iused++;

   649 }

   650 

   651 /* Set the i_lineno member of the instruction at offset off if the

   652    line number for the current expression/statement has not

   653    already been set.  If it has been set, the call has no effect.

   654 

   655    The line number is reset in the following cases:

   656    - when entering a new scope

   657    - on each statement

   658    - on each expression that start a new line

   659    - before the "except" clause

   660    - before the "for" and "while" expressions

   661 */

   662 

   663 static void

   664 compiler_set_lineno(struct compiler *c, int off)

   665 {

   666 	basicblock *b;

   667 	if (c->u->u_lineno_set)

   668 		return;

   669 	c->u->u_lineno_set = true;

   670 	b = c->u->u_curblock;

   671 	b->b_instr[off].i_lineno = c->u->u_lineno;

   672 }

   673 

   674 static int

   675 opcode_stack_effect(int opcode, int oparg)

   676 {

   677 	switch (opcode) {

   678 		case POP_TOP:

   679 			return -1;

   680 		case ROT_TWO:

   681 		case ROT_THREE:

   682 			return 0;

   683 		case DUP_TOP:

   684 			return 1;

   685 		case ROT_FOUR:

   686 			return 0;

   687 

   688 		case UNARY_POSITIVE:

   689 		case UNARY_NEGATIVE:

   690 		case UNARY_NOT:

   691 		case UNARY_CONVERT:

   692 		case UNARY_INVERT:

   693 			return 0;

   694 

   695 		case LIST_APPEND:

   696 			return -2;

   697 

   698 		case BINARY_POWER:

   699 		case BINARY_MULTIPLY:

   700 		case BINARY_DIVIDE:

   701 		case BINARY_MODULO:

   702 		case BINARY_ADD:

   703 		case BINARY_SUBTRACT:

   704 		case BINARY_SUBSCR:

   705 		case BINARY_FLOOR_DIVIDE:

   706 		case BINARY_TRUE_DIVIDE:

   707 			return -1;

   708 		case INPLACE_FLOOR_DIVIDE:

   709 		case INPLACE_TRUE_DIVIDE:

   710 			return -1;

   711 

   712 		case SLICE+0:

   713 			return 1;

   714 		case SLICE+1:

   715 			return 0;

   716 		case SLICE+2:

   717 			return 0;

   718 		case SLICE+3:

   719 			return -1;

   720 

   721 		case STORE_SLICE+0:

   722 			return -2;

   723 		case STORE_SLICE+1:

   724 			return -3;

   725 		case STORE_SLICE+2:

   726 			return -3;

   727 		case STORE_SLICE+3:

   728 			return -4;

   729 

   730 		case DELETE_SLICE+0:

   731 			return -1;

   732 		case DELETE_SLICE+1:

   733 			return -2;

   734 		case DELETE_SLICE+2:

   735 			return -2;

   736 		case DELETE_SLICE+3:

   737 			return -3;

   738 

   739 		case INPLACE_ADD:

   740 		case INPLACE_SUBTRACT:

   741 		case INPLACE_MULTIPLY:

   742 		case INPLACE_DIVIDE:

   743 		case INPLACE_MODULO:

   744 			return -1;

   745 		case STORE_SUBSCR:

   746 			return -3;

   747 		case STORE_MAP:

   748 			return -2;

   749 		case DELETE_SUBSCR:

   750 			return -2;

   751 

   752 		case BINARY_LSHIFT:

   753 		case BINARY_RSHIFT:

   754 		case BINARY_AND:

   755 		case BINARY_XOR:

   756 		case BINARY_OR:

   757 			return -1;

   758 		case INPLACE_POWER:

   759 			return -1;

   760 		case GET_ITER:

   761 			return 0;

   762 

   763 		case PRINT_EXPR:

   764 			return -1;

   765 		case PRINT_ITEM:

   766 			return -1;

   767 		case PRINT_NEWLINE:

   768 			return 0;

   769 		case PRINT_ITEM_TO:

   770 			return -2;

   771 		case PRINT_NEWLINE_TO:

   772 			return -1;

   773 		case INPLACE_LSHIFT:

   774 		case INPLACE_RSHIFT:

   775 		case INPLACE_AND:

   776 		case INPLACE_XOR:

   777 		case INPLACE_OR:

   778 			return -1;

   779 		case BREAK_LOOP:

   780 			return 0;

   781 		case WITH_CLEANUP:

   782 			return -1; /* XXX Sometimes more */

   783 		case LOAD_LOCALS:

   784 			return 1;

   785 		case RETURN_VALUE:

   786 			return -1;

   787 		case IMPORT_STAR:

   788 			return -1;

   789 		case EXEC_STMT:

   790 			return -3;

   791 		case YIELD_VALUE:

   792 			return 0;

   793 

   794 		case POP_BLOCK:

   795 			return 0;

   796 		case END_FINALLY:

   797 			return -1; /* or -2 or -3 if exception occurred */

   798 		case BUILD_CLASS:

   799 			return -2;

   800 

   801 		case STORE_NAME:

   802 			return -1;

   803 		case DELETE_NAME:

   804 			return 0;

   805 		case UNPACK_SEQUENCE:

   806 			return oparg-1;

   807 		case FOR_ITER:

   808 			return 1;

   809 

   810 		case STORE_ATTR:

   811 			return -2;

   812 		case DELETE_ATTR:

   813 			return -1;

   814 		case STORE_GLOBAL:

   815 			return -1;

   816 		case DELETE_GLOBAL:

   817 			return 0;

   818 		case DUP_TOPX:

   819 			return oparg;

   820 		case LOAD_CONST:

   821 			return 1;

   822 		case LOAD_NAME:

   823 			return 1;

   824 		case BUILD_TUPLE:

   825 		case BUILD_LIST:

   826 			return 1-oparg;

   827 		case BUILD_MAP:

   828 			return 1;

   829 		case LOAD_ATTR:

   830 			return 0;

   831 		case COMPARE_OP:

   832 			return -1;

   833 		case IMPORT_NAME:

   834 			return 0;

   835 		case IMPORT_FROM:

   836 			return 1;

   837 

   838 		case JUMP_FORWARD:

   839 		case JUMP_IF_FALSE:

   840 		case JUMP_IF_TRUE:

   841 		case JUMP_ABSOLUTE:

   842 			return 0;

   843 

   844 		case LOAD_GLOBAL:

   845 			return 1;

   846 

   847 		case CONTINUE_LOOP:

   848 			return 0;

   849 		case SETUP_LOOP:

   850 			return 0;

   851 		case SETUP_EXCEPT:

   852 		case SETUP_FINALLY:

   853 			return 3; /* actually pushed by an exception */

   854 

   855 		case LOAD_FAST:

   856 			return 1;

   857 		case STORE_FAST:

   858 			return -1;

   859 		case DELETE_FAST:

   860 			return 0;

   861 

   862 		case RAISE_VARARGS:

   863 			return -oparg;

   864 #define NARGS(o) (((o) % 256) + 2*((o) / 256))

   865 		case CALL_FUNCTION:

   866 			return -NARGS(oparg);

   867 		case CALL_FUNCTION_VAR:

   868 		case CALL_FUNCTION_KW:

   869 			return -NARGS(oparg)-1;

   870 		case CALL_FUNCTION_VAR_KW:

   871 			return -NARGS(oparg)-2;

   872 #undef NARGS

   873 		case MAKE_FUNCTION:

   874 			return -oparg;

   875 		case BUILD_SLICE:

   876 			if (oparg == 3)

   877 				return -2;

   878 			else

   879 				return -1;

   880 

   881 		case MAKE_CLOSURE:

   882 			return -oparg;

   883 		case LOAD_CLOSURE:

   884 			return 1;

   885 		case LOAD_DEREF:

   886 			return 1;

   887 		case STORE_DEREF:

   888 			return -1;

   889 		default:

   890 			fprintf(stderr, "opcode = %d\n", opcode);

   891 			Py_FatalError("opcode_stack_effect()");

   892 

   893 	}

   894 	return 0; /* not reachable */

   895 }

   896 

   897 /* Add an opcode with no argument.

   898    Returns 0 on failure, 1 on success.

   899 */

   900 

   901 static int

   902 compiler_addop(struct compiler *c, int opcode)

   903 {

   904 	basicblock *b;

   905 	struct instr *i;

   906 	int off;

   907 	off = compiler_next_instr(c, c->u->u_curblock);

   908 	if (off < 0)

   909 		return 0;

   910 	b = c->u->u_curblock;

   911 	i = &b->b_instr[off];

   912 	i->i_opcode = opcode;

   913 	i->i_hasarg = 0;

   914 	if (opcode == RETURN_VALUE)

   915 		b->b_return = 1;

   916 	compiler_set_lineno(c, off);

   917 	return 1;

   918 }

   919 

   920 static int

   921 compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)

   922 {

   923 	PyObject *t, *v;

   924 	Py_ssize_t arg;

   925 	unsigned char *p, *q;

   926 	Py_complex z;

   927 	double d;

   928 	int real_part_zero, imag_part_zero;

   929 

   930 	/* necessary to make sure types aren't coerced (e.g., int and long) */

   931         /* _and_ to distinguish 0.0 from -0.0 e.g. on IEEE platforms */

   932         if (PyFloat_Check(o)) {

   933 		d = PyFloat_AS_DOUBLE(o);

   934 		p = (unsigned char*) &d;

   935 		/* all we need is to make the tuple different in either the 0.0

   936 		 * or -0.0 case from all others, just to avoid the "coercion".

   937 		 */

   938 		if (*p==0 && p[sizeof(double)-1]==0)

   939 			t = PyTuple_Pack(3, o, o->ob_type, Py_None);

   940 		else

   941 			t = PyTuple_Pack(2, o, o->ob_type);

   942 	}

   943 	else if (PyComplex_Check(o)) {

   944 		/* complex case is even messier: we need to make complex(x,

   945 		   0.) different from complex(x, -0.) and complex(0., y)

   946 		   different from complex(-0., y), for any x and y.  In

   947 		   particular, all four complex zeros should be

   948 		   distinguished.*/

   949 		z = PyComplex_AsCComplex(o);

   950 		p = (unsigned char*) &(z.real);

   951 		q = (unsigned char*) &(z.imag);

   952 		/* all that matters here is that on IEEE platforms

   953 		   real_part_zero will be true if z.real == 0., and false if

   954 		   z.real == -0.  In fact, real_part_zero will also be true

   955 		   for some other rarely occurring nonzero floats, but this

   956 		   doesn't matter. Similar comments apply to

   957 		   imag_part_zero. */

   958 		real_part_zero = *p==0 && p[sizeof(double)-1]==0;

   959 		imag_part_zero = *q==0 && q[sizeof(double)-1]==0;

   960 		if (real_part_zero && imag_part_zero) {

   961 			t = PyTuple_Pack(4, o, o->ob_type, Py_True, Py_True);

   962 		}

   963 		else if (real_part_zero && !imag_part_zero) {

   964 			t = PyTuple_Pack(4, o, o->ob_type, Py_True, Py_False);

   965 		}

   966 		else if (!real_part_zero && imag_part_zero) {

   967 			t = PyTuple_Pack(4, o, o->ob_type, Py_False, Py_True);

   968 		}

   969 		else {

   970 			t = PyTuple_Pack(2, o, o->ob_type);

   971 		}

   972         }

   973 	else {

   974 		t = PyTuple_Pack(2, o, o->ob_type);

   975         }

   976 	if (t == NULL)

   977 		return -1;

   978 

   979 	v = PyDict_GetItem(dict, t);

   980 	if (!v) {

   981 		arg = PyDict_Size(dict);

   982 		v = PyInt_FromLong(arg);

   983 		if (!v) {

   984 			Py_DECREF(t);

   985 			return -1;

   986 		}

   987 		if (PyDict_SetItem(dict, t, v) < 0) {

   988 			Py_DECREF(t);

   989 			Py_DECREF(v);

   990 			return -1;

   991 		}

   992 		Py_DECREF(v);

   993 	}

   994 	else

   995 		arg = PyInt_AsLong(v);

   996 	Py_DECREF(t);

   997 	return arg;

   998 }

   999 

  1000 static int

  1001 compiler_addop_o(struct compiler *c, int opcode, PyObject *dict,

  1002 		     PyObject *o)

  1003 {

  1004     int arg = compiler_add_o(c, dict, o);

  1005     if (arg < 0)

  1006 	return 0;

  1007     return compiler_addop_i(c, opcode, arg);

  1008 }

  1009 

  1010 static int

  1011 compiler_addop_name(struct compiler *c, int opcode, PyObject *dict,

  1012 		    PyObject *o)

  1013 {

  1014     int arg;

  1015     PyObject *mangled = _Py_Mangle(c->u->u_private, o);

  1016     if (!mangled)

  1017 	return 0;

  1018     arg = compiler_add_o(c, dict, mangled);

  1019     Py_DECREF(mangled);

  1020     if (arg < 0)

  1021 	return 0;

  1022     return compiler_addop_i(c, opcode, arg);

  1023 }

  1024 

  1025 /* Add an opcode with an integer argument.

  1026    Returns 0 on failure, 1 on success.

  1027 */

  1028 

  1029 static int

  1030 compiler_addop_i(struct compiler *c, int opcode, int oparg)

  1031 {

  1032 	struct instr *i;

  1033 	int off;

  1034 	off = compiler_next_instr(c, c->u->u_curblock);

  1035 	if (off < 0)

  1036 		return 0;

  1037 	i = &c->u->u_curblock->b_instr[off];

  1038 	i->i_opcode = opcode;

  1039 	i->i_oparg = oparg;

  1040 	i->i_hasarg = 1;

  1041 	compiler_set_lineno(c, off);

  1042 	return 1;

  1043 }

  1044 

  1045 static int

  1046 compiler_addop_j(struct compiler *c, int opcode, basicblock *b, int absolute)

  1047 {

  1048 	struct instr *i;

  1049 	int off;

  1050 

  1051 	assert(b != NULL);

  1052 	off = compiler_next_instr(c, c->u->u_curblock);

  1053 	if (off < 0)

  1054 		return 0;

  1055 	i = &c->u->u_curblock->b_instr[off];

  1056 	i->i_opcode = opcode;

  1057 	i->i_target = b;

  1058 	i->i_hasarg = 1;

  1059 	if (absolute)

  1060 		i->i_jabs = 1;

  1061 	else

  1062 		i->i_jrel = 1;

  1063 	compiler_set_lineno(c, off);

  1064 	return 1;

  1065 }

  1066 

  1067 /* The distinction between NEW_BLOCK and NEXT_BLOCK is subtle.	(I'd

  1068    like to find better names.)	NEW_BLOCK() creates a new block and sets

  1069    it as the current block.  NEXT_BLOCK() also creates an implicit jump

  1070    from the current block to the new block.

  1071 */

  1072 

  1073 /* The returns inside these macros make it impossible to decref objects

  1074    created in the local function.  Local objects should use the arena.

  1075 */

  1076 

  1077 

  1078 #define NEW_BLOCK(C) { \

  1079 	if (compiler_use_new_block((C)) == NULL) \

  1080 		return 0; \

  1081 }

  1082 

  1083 #define NEXT_BLOCK(C) { \

  1084 	if (compiler_next_block((C)) == NULL) \

  1085 		return 0; \

  1086 }

  1087 

  1088 #define ADDOP(C, OP) { \

  1089 	if (!compiler_addop((C), (OP))) \

  1090 		return 0; \

  1091 }

  1092 

  1093 #define ADDOP_IN_SCOPE(C, OP) { \

  1094 	if (!compiler_addop((C), (OP))) { \

  1095 		compiler_exit_scope(c); \

  1096 		return 0; \

  1097 	} \

  1098 }

  1099 

  1100 #define ADDOP_O(C, OP, O, TYPE) { \

  1101 	if (!compiler_addop_o((C), (OP), (C)->u->u_ ## TYPE, (O))) \

  1102 		return 0; \

  1103 }

  1104 

  1105 #define ADDOP_NAME(C, OP, O, TYPE) { \

  1106 	if (!compiler_addop_name((C), (OP), (C)->u->u_ ## TYPE, (O))) \

  1107 		return 0; \

  1108 }

  1109 

  1110 #define ADDOP_I(C, OP, O) { \

  1111 	if (!compiler_addop_i((C), (OP), (O))) \

  1112 		return 0; \

  1113 }

  1114 

  1115 #define ADDOP_JABS(C, OP, O) { \

  1116 	if (!compiler_addop_j((C), (OP), (O), 1)) \

  1117 		return 0; \

  1118 }

  1119 

  1120 #define ADDOP_JREL(C, OP, O) { \

  1121 	if (!compiler_addop_j((C), (OP), (O), 0)) \

  1122 		return 0; \

  1123 }

  1124 

  1125 /* VISIT and VISIT_SEQ takes an ASDL type as their second argument.  They use

  1126    the ASDL name to synthesize the name of the C type and the visit function.

  1127 */

  1128 

  1129 #define VISIT(C, TYPE, V) {\

  1130 	if (!compiler_visit_ ## TYPE((C), (V))) \

  1131 		return 0; \

  1132 }

  1133 

  1134 #define VISIT_IN_SCOPE(C, TYPE, V) {\

  1135 	if (!compiler_visit_ ## TYPE((C), (V))) { \