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 #define COMP_GENEXP 0
43 #define COMP_SETCOMP 1
44 #define COMP_DICTCOMP 2
45
46 struct instr {
47 unsigned i_jabs : 1;
48 unsigned i_jrel : 1;
49 unsigned i_hasarg : 1;
50 unsigned char i_opcode;
51 int i_oparg;
52 struct basicblock_ *i_target; /* target block (if jump instruction) */
53 int i_lineno;
54 };
55
56 typedef struct basicblock_ {
57 /* Each basicblock in a compilation unit is linked via b_list in the
58 reverse order that the block are allocated. b_list points to the next
59 block, not to be confused with b_next, which is next by control flow. */
60 struct basicblock_ *b_list;
61 /* number of instructions used */
62 int b_iused;
63 /* length of instruction array (b_instr) */
64 int b_ialloc;
65 /* pointer to an array of instructions, initially NULL */
66 struct instr *b_instr;
67 /* If b_next is non-NULL, it is a pointer to the next
68 block reached by normal control flow. */
69 struct basicblock_ *b_next;
70 /* b_seen is used to perform a DFS of basicblocks. */
71 unsigned b_seen : 1;
72 /* b_return is true if a RETURN_VALUE opcode is inserted. */
73 unsigned b_return : 1;
74 /* depth of stack upon entry of block, computed by stackdepth() */
75 int b_startdepth;
76 /* instruction offset for block, computed by assemble_jump_offsets() */
77 int b_offset;
78 } basicblock;
79
80 /* fblockinfo tracks the current frame block.
81
82 A frame block is used to handle loops, try/except, and try/finally.
83 It's called a frame block to distinguish it from a basic block in the
84 compiler IR.
85 */
86
87 enum fblocktype { LOOP, EXCEPT, FINALLY_TRY, FINALLY_END };
88
89 struct fblockinfo {
90 enum fblocktype fb_type;
91 basicblock *fb_block;
92 };
93
94 /* The following items change on entry and exit of code blocks.
95 They must be saved and restored when returning to a block.
96 */
97 struct compiler_unit {
98 PySTEntryObject *u_ste;
99
100 PyObject *u_name;
101 /* The following fields are dicts that map objects to
102 the index of them in co_XXX. The index is used as
103 the argument for opcodes that refer to those collections.
104 */
105 PyObject *u_consts; /* all constants */
106 PyObject *u_names; /* all names */
107 PyObject *u_varnames; /* local variables */
108 PyObject *u_cellvars; /* cell variables */
109 PyObject *u_freevars; /* free variables */
110
111 PyObject *u_private; /* for private name mangling */
112
113 int u_argcount; /* number of arguments for block */
114 /* Pointer to the most recently allocated block. By following b_list
115 members, you can reach all early allocated blocks. */
116 basicblock *u_blocks;
117 basicblock *u_curblock; /* pointer to current block */
118
119 int u_nfblocks;
120 struct fblockinfo u_fblock[CO_MAXBLOCKS];
121
122 int u_firstlineno; /* the first lineno of the block */
123 int u_lineno; /* the lineno for the current stmt */
124 bool u_lineno_set; /* boolean to indicate whether instr
125 has been generated with current lineno */
126 };
127
128 /* This struct captures the global state of a compilation.
129
130 The u pointer points to the current compilation unit, while units
131 for enclosing blocks are stored in c_stack. The u and c_stack are
132 managed by compiler_enter_scope() and compiler_exit_scope().
133 */
134
135 struct compiler {
136 const char *c_filename;
137 struct symtable *c_st;
138 PyFutureFeatures *c_future; /* pointer to module's __future__ */
139 PyCompilerFlags *c_flags;
140
141 int c_interactive; /* true if in interactive mode */
142 int c_nestlevel;
143
144 struct compiler_unit *u; /* compiler state for current block */
145 PyObject *c_stack; /* Python list holding compiler_unit ptrs */
146 PyArena *c_arena; /* pointer to memory allocation arena */
147 };
148
149 static int compiler_enter_scope(struct compiler *, identifier, void *, int);
150 static void compiler_free(struct compiler *);
151 static basicblock *compiler_new_block(struct compiler *);
152 static int compiler_next_instr(struct compiler *, basicblock *);
153 static int compiler_addop(struct compiler *, int);
154 static int compiler_addop_o(struct compiler *, int, PyObject *, PyObject *);
155 static int compiler_addop_i(struct compiler *, int, int);
156 static int compiler_addop_j(struct compiler *, int, basicblock *, int);
157 static basicblock *compiler_use_new_block(struct compiler *);
158 static int compiler_error(struct compiler *, const char *);
159 static int compiler_nameop(struct compiler *, identifier, expr_context_ty);
160
161 static PyCodeObject *compiler_mod(struct compiler *, mod_ty);
162 static int compiler_visit_stmt(struct compiler *, stmt_ty);
163 static int compiler_visit_keyword(struct compiler *, keyword_ty);
164 static int compiler_visit_expr(struct compiler *, expr_ty);
165 static int compiler_augassign(struct compiler *, stmt_ty);
166 static int compiler_visit_slice(struct compiler *, slice_ty,
167 expr_context_ty);
168
169 static int compiler_push_fblock(struct compiler *, enum fblocktype,
170 basicblock *);
171 static void compiler_pop_fblock(struct compiler *, enum fblocktype,
172 basicblock *);
173 /* Returns true if there is a loop on the fblock stack. */
174 static int compiler_in_loop(struct compiler *);
175
176 static int inplace_binop(struct compiler *, operator_ty);
177 static int expr_constant(expr_ty e);
178
179 static int compiler_with(struct compiler *, stmt_ty);
180
181 static PyCodeObject *assemble(struct compiler *, int addNone);
182 static PyObject *__doc__;
183
184 #define COMPILER_CAPSULE_NAME_COMPILER_UNIT "compile.c compiler unit"
185
186 PyObject *
_Py_Mangle(PyObject * privateobj,PyObject * ident)187 _Py_Mangle(PyObject *privateobj, PyObject *ident)
188 {
189 /* Name mangling: __private becomes _classname__private.
190 This is independent from how the name is used. */
191 const char *p, *name = PyString_AsString(ident);
192 char *buffer;
193 size_t nlen, plen;
194 if (privateobj == NULL || !PyString_Check(privateobj) ||
195 name == NULL || name[0] != '_' || name[1] != '_') {
196 Py_INCREF(ident);
197 return ident;
198 }
199 p = PyString_AsString(privateobj);
200 nlen = strlen(name);
201 /* Don't mangle __id__ or names with dots.
202
203 The only time a name with a dot can occur is when
204 we are compiling an import statement that has a
205 package name.
206
207 TODO(jhylton): Decide whether we want to support
208 mangling of the module name, e.g. __M.X.
209 */
210 if ((name[nlen-1] == '_' && name[nlen-2] == '_')
211 || strchr(name, '.')) {
212 Py_INCREF(ident);
213 return ident; /* Don't mangle __whatever__ */
214 }
215 /* Strip leading underscores from class name */
216 while (*p == '_')
217 p++;
218 if (*p == '\0') {
219 Py_INCREF(ident);
220 return ident; /* Don't mangle if class is just underscores */
221 }
222 plen = strlen(p);
223
224 if (plen + nlen >= PY_SSIZE_T_MAX - 1) {
225 PyErr_SetString(PyExc_OverflowError,
226 "private identifier too large to be mangled");
227 return NULL;
228 }
229
230 ident = PyString_FromStringAndSize(NULL, 1 + nlen + plen);
231 if (!ident)
232 return 0;
233 /* ident = "_" + p[:plen] + name # i.e. 1+plen+nlen bytes */
234 buffer = PyString_AS_STRING(ident);
235 buffer[0] = '_';
236 strncpy(buffer+1, p, plen);
237 strcpy(buffer+1+plen, name);
238 return ident;
239 }
240
241 static int
compiler_init(struct compiler * c)242 compiler_init(struct compiler *c)
243 {
244 memset(c, 0, sizeof(struct compiler));
245
246 c->c_stack = PyList_New(0);
247 if (!c->c_stack)
248 return 0;
249
250 return 1;
251 }
252
253 PyCodeObject *
PyAST_Compile(mod_ty mod,const char * filename,PyCompilerFlags * flags,PyArena * arena)254 PyAST_Compile(mod_ty mod, const char *filename, PyCompilerFlags *flags,
255 PyArena *arena)
256 {
257 struct compiler c;
258 PyCodeObject *co = NULL;
259 PyCompilerFlags local_flags;
260 int merged;
261
262 if (!__doc__) {
263 __doc__ = PyString_InternFromString("__doc__");
264 if (!__doc__)
265 return NULL;
266 }
267
268 if (!compiler_init(&c))
269 return NULL;
270 c.c_filename = filename;
271 c.c_arena = arena;
272 c.c_future = PyFuture_FromAST(mod, filename);
273 if (c.c_future == NULL)
274 goto finally;
275 if (!flags) {
276 local_flags.cf_flags = 0;
277 flags = &local_flags;
278 }
279 merged = c.c_future->ff_features | flags->cf_flags;
280 c.c_future->ff_features = merged;
281 flags->cf_flags = merged;
282 c.c_flags = flags;
283 c.c_nestlevel = 0;
284
285 c.c_st = PySymtable_Build(mod, filename, c.c_future);
286 if (c.c_st == NULL) {
287 if (!PyErr_Occurred())
288 PyErr_SetString(PyExc_SystemError, "no symtable");
289 goto finally;
290 }
291
292 co = compiler_mod(&c, mod);
293
294 finally:
295 compiler_free(&c);
296 assert(co || PyErr_Occurred());
297 return co;
298 }
299
300 PyCodeObject *
PyNode_Compile(struct _node * n,const char * filename)301 PyNode_Compile(struct _node *n, const char *filename)
302 {
303 PyCodeObject *co = NULL;
304 mod_ty mod;
305 PyArena *arena = PyArena_New();
306 if (!arena)
307 return NULL;
308 mod = PyAST_FromNode(n, NULL, filename, arena);
309 if (mod)
310 co = PyAST_Compile(mod, filename, NULL, arena);
311 PyArena_Free(arena);
312 return co;
313 }
314
315 static void
compiler_free(struct compiler * c)316 compiler_free(struct compiler *c)
317 {
318 if (c->c_st)
319 PySymtable_Free(c->c_st);
320 if (c->c_future)
321 PyObject_Free(c->c_future);
322 Py_DECREF(c->c_stack);
323 }
324
325 static PyObject *
list2dict(PyObject * list)326 list2dict(PyObject *list)
327 {
328 Py_ssize_t i, n;
329 PyObject *v, *k;
330 PyObject *dict = PyDict_New();
331 if (!dict) return NULL;
332
333 n = PyList_Size(list);
334 for (i = 0; i < n; i++) {
335 v = PyInt_FromLong(i);
336 if (!v) {
337 Py_DECREF(dict);
338 return NULL;
339 }
340 k = PyList_GET_ITEM(list, i);
341 k = _PyCode_ConstantKey(k);
342 if (k == NULL || PyDict_SetItem(dict, k, v) < 0) {
343 Py_XDECREF(k);
344 Py_DECREF(v);
345 Py_DECREF(dict);
346 return NULL;
347 }
348 Py_DECREF(k);
349 Py_DECREF(v);
350 }
351 return dict;
352 }
353
354 /* Return new dict containing names from src that match scope(s).
355
356 src is a symbol table dictionary. If the scope of a name matches
357 either scope_type or flag is set, insert it into the new dict. The
358 values are integers, starting at offset and increasing by one for
359 each key.
360 */
361
362 static PyObject *
dictbytype(PyObject * src,int scope_type,int flag,int offset)363 dictbytype(PyObject *src, int scope_type, int flag, int offset)
364 {
365 Py_ssize_t i = offset, scope, num_keys, key_i;
366 PyObject *k, *v, *dest = PyDict_New();
367 PyObject *sorted_keys;
368
369 assert(offset >= 0);
370 if (dest == NULL)
371 return NULL;
372
373 /* Sort the keys so that we have a deterministic order on the indexes
374 saved in the returned dictionary. These indexes are used as indexes
375 into the free and cell var storage. Therefore if they aren't
376 deterministic, then the generated bytecode is not deterministic.
377 */
378 sorted_keys = PyDict_Keys(src);
379 if (sorted_keys == NULL)
380 return NULL;
381 if (PyList_Sort(sorted_keys) != 0) {
382 Py_DECREF(sorted_keys);
383 return NULL;
384 }
385 num_keys = PyList_GET_SIZE(sorted_keys);
386
387 for (key_i = 0; key_i < num_keys; key_i++) {
388 k = PyList_GET_ITEM(sorted_keys, key_i);
389 v = PyDict_GetItem(src, k);
390 /* XXX this should probably be a macro in symtable.h */
391 assert(PyInt_Check(v));
392 scope = (PyInt_AS_LONG(v) >> SCOPE_OFF) & SCOPE_MASK;
393
394 if (scope == scope_type || PyInt_AS_LONG(v) & flag) {
395 PyObject *tuple, *item = PyInt_FromLong(i);
396 if (item == NULL) {
397 Py_DECREF(sorted_keys);
398 Py_DECREF(dest);
399 return NULL;
400 }
401 i++;
402 tuple = _PyCode_ConstantKey(k);
403 if (!tuple || PyDict_SetItem(dest, tuple, item) < 0) {
404 Py_DECREF(sorted_keys);
405 Py_DECREF(item);
406 Py_DECREF(dest);
407 Py_XDECREF(tuple);
408 return NULL;
409 }
410 Py_DECREF(item);
411 Py_DECREF(tuple);
412 }
413 }
414 Py_DECREF(sorted_keys);
415 return dest;
416 }
417
418 static void
compiler_unit_check(struct compiler_unit * u)419 compiler_unit_check(struct compiler_unit *u)
420 {
421 basicblock *block;
422 for (block = u->u_blocks; block != NULL; block = block->b_list) {
423 assert((void *)block != (void *)0xcbcbcbcb);
424 assert((void *)block != (void *)0xfbfbfbfb);
425 assert((void *)block != (void *)0xdbdbdbdb);
426 if (block->b_instr != NULL) {
427 assert(block->b_ialloc > 0);
428 assert(block->b_iused > 0);
429 assert(block->b_ialloc >= block->b_iused);
430 }
431 else {
432 assert (block->b_iused == 0);
433 assert (block->b_ialloc == 0);
434 }
435 }
436 }
437
438 static void
compiler_unit_free(struct compiler_unit * u)439 compiler_unit_free(struct compiler_unit *u)
440 {
441 basicblock *b, *next;
442
443 compiler_unit_check(u);
444 b = u->u_blocks;
445 while (b != NULL) {
446 if (b->b_instr)
447 PyObject_Free((void *)b->b_instr);
448 next = b->b_list;
449 PyObject_Free((void *)b);
450 b = next;
451 }
452 Py_CLEAR(u->u_ste);
453 Py_CLEAR(u->u_name);
454 Py_CLEAR(u->u_consts);
455 Py_CLEAR(u->u_names);
456 Py_CLEAR(u->u_varnames);
457 Py_CLEAR(u->u_freevars);
458 Py_CLEAR(u->u_cellvars);
459 Py_CLEAR(u->u_private);
460 PyObject_Free(u);
461 }
462
463 static int
compiler_enter_scope(struct compiler * c,identifier name,void * key,int lineno)464 compiler_enter_scope(struct compiler *c, identifier name, void *key,
465 int lineno)
466 {
467 struct compiler_unit *u;
468
469 u = (struct compiler_unit *)PyObject_Malloc(sizeof(
470 struct compiler_unit));
471 if (!u) {
472 PyErr_NoMemory();
473 return 0;
474 }
475 memset(u, 0, sizeof(struct compiler_unit));
476 u->u_argcount = 0;
477 u->u_ste = PySymtable_Lookup(c->c_st, key);
478 if (!u->u_ste) {
479 compiler_unit_free(u);
480 return 0;
481 }
482 Py_INCREF(name);
483 u->u_name = name;
484 u->u_varnames = list2dict(u->u_ste->ste_varnames);
485 u->u_cellvars = dictbytype(u->u_ste->ste_symbols, CELL, 0, 0);
486 if (!u->u_varnames || !u->u_cellvars) {
487 compiler_unit_free(u);
488 return 0;
489 }
490
491 u->u_freevars = dictbytype(u->u_ste->ste_symbols, FREE, DEF_FREE_CLASS,
492 PyDict_Size(u->u_cellvars));
493 if (!u->u_freevars) {
494 compiler_unit_free(u);
495 return 0;
496 }
497
498 u->u_blocks = NULL;
499 u->u_nfblocks = 0;
500 u->u_firstlineno = lineno;
501 u->u_lineno = 0;
502 u->u_lineno_set = false;
503 u->u_consts = PyDict_New();
504 if (!u->u_consts) {
505 compiler_unit_free(u);
506 return 0;
507 }
508 u->u_names = PyDict_New();
509 if (!u->u_names) {
510 compiler_unit_free(u);
511 return 0;
512 }
513
514 u->u_private = NULL;
515
516 /* Push the old compiler_unit on the stack. */
517 if (c->u) {
518 PyObject *capsule = PyCapsule_New(c->u, COMPILER_CAPSULE_NAME_COMPILER_UNIT, NULL);
519 if (!capsule || PyList_Append(c->c_stack, capsule) < 0) {
520 Py_XDECREF(capsule);
521 compiler_unit_free(u);
522 return 0;
523 }
524 Py_DECREF(capsule);
525 u->u_private = c->u->u_private;
526 Py_XINCREF(u->u_private);
527 }
528 c->u = u;
529
530 c->c_nestlevel++;
531 if (compiler_use_new_block(c) == NULL)
532 return 0;
533
534 return 1;
535 }
536
537 static void
compiler_exit_scope(struct compiler * c)538 compiler_exit_scope(struct compiler *c)
539 {
540 int n;
541 PyObject *capsule;
542
543 c->c_nestlevel--;
544 compiler_unit_free(c->u);
545 /* Restore c->u to the parent unit. */
546 n = PyList_GET_SIZE(c->c_stack) - 1;
547 if (n >= 0) {
548 capsule = PyList_GET_ITEM(c->c_stack, n);
549 c->u = (struct compiler_unit *)PyCapsule_GetPointer(capsule, COMPILER_CAPSULE_NAME_COMPILER_UNIT);
550 assert(c->u);
551 /* we are deleting from a list so this really shouldn't fail */
552 if (PySequence_DelItem(c->c_stack, n) < 0)
553 Py_FatalError("compiler_exit_scope()");
554 compiler_unit_check(c->u);
555 }
556 else
557 c->u = NULL;
558
559 }
560
561 /* Allocate a new block and return a pointer to it.
562 Returns NULL on error.
563 */
564
565 static basicblock *
compiler_new_block(struct compiler * c)566 compiler_new_block(struct compiler *c)
567 {
568 basicblock *b;
569 struct compiler_unit *u;
570
571 u = c->u;
572 b = (basicblock *)PyObject_Malloc(sizeof(basicblock));
573 if (b == NULL) {
574 PyErr_NoMemory();
575 return NULL;
576 }
577 memset((void *)b, 0, sizeof(basicblock));
578 /* Extend the singly linked list of blocks with new block. */
579 b->b_list = u->u_blocks;
580 u->u_blocks = b;
581 return b;
582 }
583
584 static basicblock *
compiler_use_new_block(struct compiler * c)585 compiler_use_new_block(struct compiler *c)
586 {
587 basicblock *block = compiler_new_block(c);
588 if (block == NULL)
589 return NULL;
590 c->u->u_curblock = block;
591 return block;
592 }
593
594 static basicblock *
compiler_next_block(struct compiler * c)595 compiler_next_block(struct compiler *c)
596 {
597 basicblock *block = compiler_new_block(c);
598 if (block == NULL)
599 return NULL;
600 c->u->u_curblock->b_next = block;
601 c->u->u_curblock = block;
602 return block;
603 }
604
605 static basicblock *
compiler_use_next_block(struct compiler * c,basicblock * block)606 compiler_use_next_block(struct compiler *c, basicblock *block)
607 {
608 assert(block != NULL);
609 c->u->u_curblock->b_next = block;
610 c->u->u_curblock = block;
611 return block;
612 }
613
614 /* Returns the offset of the next instruction in the current block's
615 b_instr array. Resizes the b_instr as necessary.
616 Returns -1 on failure.
617 */
618
619 static int
compiler_next_instr(struct compiler * c,basicblock * b)620 compiler_next_instr(struct compiler *c, basicblock *b)
621 {
622 assert(b != NULL);
623 if (b->b_instr == NULL) {
624 b->b_instr = (struct instr *)PyObject_Malloc(
625 sizeof(struct instr) * DEFAULT_BLOCK_SIZE);
626 if (b->b_instr == NULL) {
627 PyErr_NoMemory();
628 return -1;
629 }
630 b->b_ialloc = DEFAULT_BLOCK_SIZE;
631 memset((char *)b->b_instr, 0,
632 sizeof(struct instr) * DEFAULT_BLOCK_SIZE);
633 }
634 else if (b->b_iused == b->b_ialloc) {
635 struct instr *tmp;
636 size_t oldsize, newsize;
637 oldsize = b->b_ialloc * sizeof(struct instr);
638 newsize = oldsize << 1;
639
640 if (oldsize > (PY_SIZE_MAX >> 1)) {
641 PyErr_NoMemory();
642 return -1;
643 }
644
645 if (newsize == 0) {
646 PyErr_NoMemory();
647 return -1;
648 }
649 b->b_ialloc <<= 1;
650 tmp = (struct instr *)PyObject_Realloc(
651 (void *)b->b_instr, newsize);
652 if (tmp == NULL) {
653 PyErr_NoMemory();
654 return -1;
655 }
656 b->b_instr = tmp;
657 memset((char *)b->b_instr + oldsize, 0, newsize - oldsize);
658 }
659 return b->b_iused++;
660 }
661
662 /* Set the i_lineno member of the instruction at offset off if the
663 line number for the current expression/statement has not
664 already been set. If it has been set, the call has no effect.
665
666 The line number is reset in the following cases:
667 - when entering a new scope
668 - on each statement
669 - on each expression that start a new line
670 - before the "except" clause
671 - before the "for" and "while" expressions
672 */
673
674 static void
compiler_set_lineno(struct compiler * c,int off)675 compiler_set_lineno(struct compiler *c, int off)
676 {
677 basicblock *b;
678 if (c->u->u_lineno_set)
679 return;
680 c->u->u_lineno_set = true;
681 b = c->u->u_curblock;
682 b->b_instr[off].i_lineno = c->u->u_lineno;
683 }
684
685 static int
opcode_stack_effect(int opcode,int oparg)686 opcode_stack_effect(int opcode, int oparg)
687 {
688 switch (opcode) {
689 case POP_TOP:
690 return -1;
691 case ROT_TWO:
692 case ROT_THREE:
693 return 0;
694 case DUP_TOP:
695 return 1;
696 case ROT_FOUR:
697 return 0;
698
699 case UNARY_POSITIVE:
700 case UNARY_NEGATIVE:
701 case UNARY_NOT:
702 case UNARY_CONVERT:
703 case UNARY_INVERT:
704 return 0;
705
706 case SET_ADD:
707 case LIST_APPEND:
708 return -1;
709
710 case MAP_ADD:
711 return -2;
712
713 case BINARY_POWER:
714 case BINARY_MULTIPLY:
715 case BINARY_DIVIDE:
716 case BINARY_MODULO:
717 case BINARY_ADD:
718 case BINARY_SUBTRACT:
719 case BINARY_SUBSCR:
720 case BINARY_FLOOR_DIVIDE:
721 case BINARY_TRUE_DIVIDE:
722 return -1;
723 case INPLACE_FLOOR_DIVIDE:
724 case INPLACE_TRUE_DIVIDE:
725 return -1;
726
727 case SLICE+0:
728 return 0;
729 case SLICE+1:
730 return -1;
731 case SLICE+2:
732 return -1;
733 case SLICE+3:
734 return -2;
735
736 case STORE_SLICE+0:
737 return -2;
738 case STORE_SLICE+1:
739 return -3;
740 case STORE_SLICE+2:
741 return -3;
742 case STORE_SLICE+3:
743 return -4;
744
745 case DELETE_SLICE+0:
746 return -1;
747 case DELETE_SLICE+1:
748 return -2;
749 case DELETE_SLICE+2:
750 return -2;
751 case DELETE_SLICE+3:
752 return -3;
753
754 case INPLACE_ADD:
755 case INPLACE_SUBTRACT:
756 case INPLACE_MULTIPLY:
757 case INPLACE_DIVIDE:
758 case INPLACE_MODULO:
759 return -1;
760 case STORE_SUBSCR:
761 return -3;
762 case STORE_MAP:
763 return -2;
764 case DELETE_SUBSCR:
765 return -2;
766
767 case BINARY_LSHIFT:
768 case BINARY_RSHIFT:
769 case BINARY_AND:
770 case BINARY_XOR:
771 case BINARY_OR:
772 return -1;
773 case INPLACE_POWER:
774 return -1;
775 case GET_ITER:
776 return 0;
777
778 case PRINT_EXPR:
779 return -1;
780 case PRINT_ITEM:
781 return -1;
782 case PRINT_NEWLINE:
783 return 0;
784 case PRINT_ITEM_TO:
785 return -2;
786 case PRINT_NEWLINE_TO:
787 return -1;
788 case INPLACE_LSHIFT:
789 case INPLACE_RSHIFT:
790 case INPLACE_AND:
791 case INPLACE_XOR:
792 case INPLACE_OR:
793 return -1;
794 case BREAK_LOOP:
795 return 0;
796 case SETUP_WITH:
797 return 4;
798 case WITH_CLEANUP:
799 return -1; /* XXX Sometimes more */
800 case LOAD_LOCALS:
801 return 1;
802 case RETURN_VALUE:
803 return -1;
804 case IMPORT_STAR:
805 return -1;
806 case EXEC_STMT:
807 return -3;
808 case YIELD_VALUE:
809 return 0;
810
811 case POP_BLOCK:
812 return 0;
813 case END_FINALLY:
814 return -3; /* or -1 or -2 if no exception occurred or
815 return/break/continue */
816 case BUILD_CLASS:
817 return -2;
818
819 case STORE_NAME:
820 return -1;
821 case DELETE_NAME:
822 return 0;
823 case UNPACK_SEQUENCE:
824 return oparg-1;
825 case FOR_ITER:
826 return 1; /* or -1, at end of iterator */
827
828 case STORE_ATTR:
829 return -2;
830 case DELETE_ATTR:
831 return -1;
832 case STORE_GLOBAL:
833 return -1;
834 case DELETE_GLOBAL:
835 return 0;
836 case DUP_TOPX:
837 return oparg;
838 case LOAD_CONST:
839 return 1;
840 case LOAD_NAME:
841 return 1;
842 case BUILD_TUPLE:
843 case BUILD_LIST:
844 case BUILD_SET:
845 return 1-oparg;
846 case BUILD_MAP:
847 return 1;
848 case LOAD_ATTR:
849 return 0;
850 case COMPARE_OP:
851 return -1;
852 case IMPORT_NAME:
853 return -1;
854 case IMPORT_FROM:
855 return 1;
856
857 case JUMP_FORWARD:
858 case JUMP_IF_TRUE_OR_POP: /* -1 if jump not taken */
859 case JUMP_IF_FALSE_OR_POP: /* "" */
860 case JUMP_ABSOLUTE:
861 return 0;
862
863 case POP_JUMP_IF_FALSE:
864 case POP_JUMP_IF_TRUE:
865 return -1;
866
867 case LOAD_GLOBAL:
868 return 1;
869
870 case CONTINUE_LOOP:
871 return 0;
872 case SETUP_LOOP:
873 case SETUP_EXCEPT:
874 case SETUP_FINALLY:
875 return 0;
876
877 case LOAD_FAST:
878 return 1;
879 case STORE_FAST:
880 return -1;
881 case DELETE_FAST:
882 return 0;
883
884 case RAISE_VARARGS:
885 return -oparg;
886 #define NARGS(o) (((o) % 256) + 2*((o) / 256))
887 case CALL_FUNCTION:
888 return -NARGS(oparg);
889 case CALL_FUNCTION_VAR:
890 case CALL_FUNCTION_KW:
891 return -NARGS(oparg)-1;
892 case CALL_FUNCTION_VAR_KW:
893 return -NARGS(oparg)-2;
894 #undef NARGS
895 case MAKE_FUNCTION:
896 return -oparg;
897 case BUILD_SLICE:
898 if (oparg == 3)
899 return -2;
900 else
901 return -1;
902
903 case MAKE_CLOSURE:
904 return -oparg-1;
905 case LOAD_CLOSURE:
906 return 1;
907 case LOAD_DEREF:
908 return 1;
909 case STORE_DEREF:
910 return -1;
911 default:
912 fprintf(stderr, "opcode = %d\n", opcode);
913 Py_FatalError("opcode_stack_effect()");
914
915 }
916 return 0; /* not reachable */
917 }
918
919 /* Add an opcode with no argument.
920 Returns 0 on failure, 1 on success.
921 */
922
923 static int
compiler_addop(struct compiler * c,int opcode)924 compiler_addop(struct compiler *c, int opcode)
925 {
926 basicblock *b;
927 struct instr *i;
928 int off;
929 off = compiler_next_instr(c, c->u->u_curblock);
930 if (off < 0)
931 return 0;
932 b = c->u->u_curblock;
933 i = &b->b_instr[off];
934 i->i_opcode = opcode;
935 i->i_hasarg = 0;
936 if (opcode == RETURN_VALUE)
937 b->b_return = 1;
938 compiler_set_lineno(c, off);
939 return 1;
940 }
941
942 static int
compiler_add_o(struct compiler * c,PyObject * dict,PyObject * o)943 compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o)
944 {
945 PyObject *t, *v;
946 Py_ssize_t arg;
947
948 t = _PyCode_ConstantKey(o);
949 if (t == NULL)
950 return -1;
951
952 v = PyDict_GetItem(dict, t);
953 if (!v) {
954 arg = PyDict_Size(dict);
955 v = PyInt_FromLong(arg);
956 if (!v) {
957 Py_DECREF(t);
958 return -1;
959 }
960 if (PyDict_SetItem(dict, t, v) < 0) {
961 Py_DECREF(t);
962 Py_DECREF(v);
963 return -1;
964 }
965 Py_DECREF(v);
966 }
967 else
968 arg = PyInt_AsLong(v);
969 Py_DECREF(t);
970 return arg;
971 }
972
973 static int
compiler_addop_o(struct compiler * c,int opcode,PyObject * dict,PyObject * o)974 compiler_addop_o(struct compiler *c, int opcode, PyObject *dict,
975 PyObject *o)
976 {
977 int arg = compiler_add_o(c, dict, o);
978 if (arg < 0)
979 return 0;
980 return compiler_addop_i(c, opcode, arg);
981 }
982
983 static int
compiler_addop_name(struct compiler * c,int opcode,PyObject * dict,PyObject * o)984 compiler_addop_name(struct compiler *c, int opcode, PyObject *dict,
985 PyObject *o)
986 {
987 int arg;
988 PyObject *mangled = _Py_Mangle(c->u->u_private, o);
989 if (!mangled)
990 return 0;
991 arg = compiler_add_o(c, dict, mangled);
992 Py_DECREF(mangled);
993 if (arg < 0)
994 return 0;
995 return compiler_addop_i(c, opcode, arg);
996 }
997
998 /* Add an opcode with an integer argument.
999 Returns 0 on failure, 1 on success.
1000 */
1001
1002 static int
compiler_addop_i(struct compiler * c,int opcode,int oparg)1003 compiler_addop_i(struct compiler *c, int opcode, int oparg)
1004 {
1005 struct instr *i;
1006 int off;
1007 off = compiler_next_instr(c, c->u->u_curblock);
1008 if (off < 0)
1009 return 0;
1010 i = &c->u->u_curblock->b_instr[off];
1011 i->i_opcode = opcode;
1012 i->i_oparg = oparg;
1013 i->i_hasarg = 1;
1014 compiler_set_lineno(c, off);
1015 return 1;
1016 }
1017
1018 static int
compiler_addop_j(struct compiler * c,int opcode,basicblock * b,int absolute)1019 compiler_addop_j(struct compiler *c, int opcode, basicblock *b, int absolute)
1020 {
1021 struct instr *i;
1022 int off;
1023
1024 assert(b != NULL);
1025 off = compiler_next_instr(c, c->u->u_curblock);
1026 if (off < 0)
1027 return 0;
1028 i = &c->u->u_curblock->b_instr[off];
1029 i->i_opcode = opcode;
1030 i->i_target = b;
1031 i->i_hasarg = 1;
1032 if (absolute)
1033 i->i_jabs = 1;
1034 else
1035 i->i_jrel = 1;
1036 compiler_set_lineno(c, off);
1037 return 1;
1038 }
1039
1040 /* The distinction between NEW_BLOCK and NEXT_BLOCK is subtle. (I'd
1041 like to find better names.) NEW_BLOCK() creates a new block and sets
1042 it as the current block. NEXT_BLOCK() also creates an implicit jump
1043 from the current block to the new block.
1044 */
1045
1046 /* The returns inside these macros make it impossible to decref objects
1047 created in the local function. Local objects should use the arena.
1048 */
1049
1050
1051 #define NEW_BLOCK(C) { \
1052 if (compiler_use_new_block((C)) == NULL) \
1053 return 0; \
1054 }
1055
1056 #define NEXT_BLOCK(C) { \
1057 if (compiler_next_block((C)) == NULL) \
1058 return 0; \
1059 }
1060
1061 #define ADDOP(C, OP) { \
1062 if (!compiler_addop((C), (OP))) \
1063 return 0; \
1064 }
1065
1066 #define ADDOP_IN_SCOPE(C, OP) { \
1067 if (!compiler_addop((C), (OP))) { \
1068 compiler_exit_scope(c); \
1069 return 0; \
1070 } \
1071 }
1072
1073 #define ADDOP_O(C, OP, O, TYPE) { \
1074 if (!compiler_addop_o((C), (OP), (C)->u->u_ ## TYPE, (O))) \
1075 return 0; \
1076 }
1077
1078 #define ADDOP_NAME(C, OP, O, TYPE) { \
1079 if (!compiler_addop_name((C), (OP), (C)->u->u_ ## TYPE, (O))) \
1080 return 0; \
1081 }
1082
1083 #define ADDOP_I(C, OP, O) { \
1084 if (!compiler_addop_i((C), (OP), (O))) \
1085 return 0; \
1086 }
1087
1088 #define ADDOP_JABS(C, OP, O) { \
1089 if (!compiler_addop_j((C), (OP), (O), 1)) \
1090 return 0; \
1091 }
1092
1093 #define ADDOP_JREL(C, OP, O) { \
1094 if (!compiler_addop_j((C), (OP), (O), 0)) \
1095 return 0; \
1096 }
1097
1098 /* VISIT and VISIT_SEQ takes an ASDL type as their second argument. They use
1099 the ASDL name to synthesize the name of the C type and the visit function.
1100 */
1101
1102 #define VISIT(C, TYPE, V) {\
1103 if (!compiler_visit_ ## TYPE((C), (V))) \
1104 return 0; \
1105 }
1106
1107 #define VISIT_IN_SCOPE(C, TYPE, V) {\
1108 if (!compiler_visit_ ## TYPE((C), (V))) { \
1109 compiler_exit_scope(c); \
1110 return 0; \
1111 } \
1112 }
1113
1114 #define VISIT_SLICE(C, V, CTX) {\
1115 if (!compiler_visit_slice((C), (V), (CTX))) \
1116 return 0; \
1117 }
1118
1119 #define VISIT_SEQ(C, TYPE, SEQ) { \
1120 int _i; \
1121 asdl_seq *seq = (SEQ); /* avoid variable capture */ \
1122 for (_i = 0; _i < asdl_seq_LEN(seq); _i++) { \
1123 TYPE ## _ty elt = (TYPE ## _ty)asdl_seq_GET(seq, _i); \
1124 if (!compiler_visit_ ## TYPE((C), elt)) \
1125 return 0; \
1126 } \
1127 }
1128
1129 #define VISIT_SEQ_IN_SCOPE(C, TYPE, SEQ) { \
1130 int _i; \
1131 asdl_seq *seq = (SEQ); /* avoid variable capture */ \
1132 for (_i = 0; _i < asdl_seq_LEN(seq); _i++) { \
1133 TYPE ## _ty elt = (TYPE ## _ty)asdl_seq_GET(seq, _i); \
1134 if (!compiler_visit_ ## TYPE((C), elt)) { \
1135 compiler_exit_scope(c); \
1136 return 0; \
1137 } \
1138 } \
1139 }
1140
1141 static int
compiler_isdocstring(stmt_ty s)1142 compiler_isdocstring(stmt_ty s)
1143 {
1144 if (s->kind != Expr_kind)
1145 return 0;
1146 return s->v.Expr.value->kind == Str_kind;
1147 }
1148
1149 /* Compile a sequence of statements, checking for a docstring. */
1150
1151 static int
compiler_body(struct compiler * c,asdl_seq * stmts)1152 compiler_body(struct compiler *c, asdl_seq *stmts)
1153 {
1154 int i = 0;
1155 stmt_ty st;
1156
1157 if (!asdl_seq_LEN(stmts))
1158 return 1;
1159 st = (stmt_ty)asdl_seq_GET(stmts, 0);
1160 if (compiler_isdocstring(st) && Py_OptimizeFlag < 2) {
1161 /* don't generate docstrings if -OO */
1162 i = 1;
1163 VISIT(c, expr, st->v.Expr.value);
1164 if (!compiler_nameop(c, __doc__, Store))
1165 return 0;
1166 }
1167 for (; i < asdl_seq_LEN(stmts); i++)
1168 VISIT(c, stmt, (stmt_ty)asdl_seq_GET(stmts, i));
1169 return 1;
1170 }
1171
1172 static PyCodeObject *
compiler_mod(struct compiler * c,mod_ty mod)1173 compiler_mod(struct compiler *c, mod_ty mod)
1174 {
1175 PyCodeObject *co;
1176 int addNone = 1;
1177 static PyObject *module;
1178 if (!module) {
1179 module = PyString_InternFromString("<module>");
1180 if (!module)
1181 return NULL;
1182 }
1183 /* Use 0 for firstlineno initially, will fixup in assemble(). */
1184 if (!compiler_enter_scope(c, module, mod, 0))
1185 return NULL;
1186 switch (mod->kind) {
1187 case Module_kind:
1188 if (!compiler_body(c, mod->v.Module.body)) {
1189 compiler_exit_scope(c);
1190 return 0;
1191 }
1192 break;
1193 case Interactive_kind:
1194 c->c_interactive = 1;
1195 VISIT_SEQ_IN_SCOPE(c, stmt,
1196 mod->v.Interactive.body);
1197 break;
1198 case Expression_kind:
1199 VISIT_IN_SCOPE(c, expr, mod->v.Expression.body);
1200 addNone = 0;
1201 break;
1202 case Suite_kind:
1203 PyErr_SetString(PyExc_SystemError,
1204 "suite should not be possible");
1205 return 0;
1206 default:
1207 PyErr_Format(PyExc_SystemError,
1208 "module kind %d should not be possible",
1209 mod->kind);
1210 return 0;
1211 }
1212 co = assemble(c, addNone);
1213 compiler_exit_scope(c);
1214 return co;
1215 }
1216
1217 /* The test for LOCAL must come before the test for FREE in order to
1218 handle classes where name is both local and free. The local var is
1219 a method and the free var is a free var referenced within a method.
1220 */
1221
1222 static int
get_ref_type(struct compiler * c,PyObject * name)1223 get_ref_type(struct compiler *c, PyObject *name)
1224 {
1225 int scope = PyST_GetScope(c->u->u_ste, name);
1226 if (scope == 0) {
1227 char buf[350];
1228 PyOS_snprintf(buf, sizeof(buf),
1229 "unknown scope for %.100s in %.100s(%s) in %s\n"
1230 "symbols: %s\nlocals: %s\nglobals: %s",
1231 PyString_AS_STRING(name),
1232 PyString_AS_STRING(c->u->u_name),
1233 PyString_AS_STRING(PyObject_Repr(c->u->u_ste->ste_id)),
1234 c->c_filename,
1235 PyString_AS_STRING(PyObject_Repr(c->u->u_ste->ste_symbols)),
1236 PyString_AS_STRING(PyObject_Repr(c->u->u_varnames)),
1237 PyString_AS_STRING(PyObject_Repr(c->u->u_names))
1238 );
1239 Py_FatalError(buf);
1240 }
1241
1242 return scope;
1243 }
1244
1245 static int
compiler_lookup_arg(PyObject * dict,PyObject * name)1246 compiler_lookup_arg(PyObject *dict, PyObject *name)
1247 {
1248 PyObject *k, *v;
1249 k = _PyCode_ConstantKey(name);
1250 if (k == NULL)
1251 return -1;
1252 v = PyDict_GetItem(dict, k);
1253 Py_DECREF(k);
1254 if (v == NULL)
1255 return -1;
1256 return PyInt_AS_LONG(v);
1257 }
1258
1259 static int
compiler_make_closure(struct compiler * c,PyCodeObject * co,int args)1260 compiler_make_closure(struct compiler *c, PyCodeObject *co, int args)
1261 {
1262 int i, free = PyCode_GetNumFree(co);
1263 if (free == 0) {
1264 ADDOP_O(c, LOAD_CONST, (PyObject*)co, consts);
1265 ADDOP_I(c, MAKE_FUNCTION, args);
1266 return 1;
1267 }
1268 for (i = 0; i < free; ++i) {
1269 /* Bypass com_addop_varname because it will generate
1270 LOAD_DEREF but LOAD_CLOSURE is needed.
1271 */
1272 PyObject *name = PyTuple_GET_ITEM(co->co_freevars, i);
1273 int arg, reftype;
1274
1275 /* Special case: If a class contains a method with a
1276 free variable that has the same name as a method,
1277 the name will be considered free *and* local in the
1278 class. It should be handled by the closure, as
1279 well as by the normal name loookup logic.
1280 */
1281 reftype = get_ref_type(c, name);
1282 if (reftype == CELL)
1283 arg = compiler_lookup_arg(c->u->u_cellvars, name);
1284 else /* (reftype == FREE) */
1285 arg = compiler_lookup_arg(c->u->u_freevars, name);
1286 if (arg == -1) {
1287 printf("lookup %s in %s %d %d\n"
1288 "freevars of %s: %s\n",
1289 PyString_AS_STRING(PyObject_Repr(name)),
1290 PyString_AS_STRING(c->u->u_name),
1291 reftype, arg,
1292 PyString_AS_STRING(co->co_name),
1293 PyString_AS_STRING(PyObject_Repr(co->co_freevars)));
1294 Py_FatalError("compiler_make_closure()");
1295 }
1296 ADDOP_I(c, LOAD_CLOSURE, arg);
1297 }
1298 ADDOP_I(c, BUILD_TUPLE, free);
1299 ADDOP_O(c, LOAD_CONST, (PyObject*)co, consts);
1300 ADDOP_I(c, MAKE_CLOSURE, args);
1301 return 1;
1302 }
1303
1304 static int
compiler_decorators(struct compiler * c,asdl_seq * decos)1305 compiler_decorators(struct compiler *c, asdl_seq* decos)
1306 {
1307 int i;
1308
1309 if (!decos)
1310 return 1;
1311
1312 for (i = 0; i < asdl_seq_LEN(decos); i++) {
1313 VISIT(c, expr, (expr_ty)asdl_seq_GET(decos, i));
1314 }
1315 return 1;
1316 }
1317
1318 static int
compiler_arguments(struct compiler * c,arguments_ty args)1319 compiler_arguments(struct compiler *c, arguments_ty args)
1320 {
1321 int i;
1322 int n = asdl_seq_LEN(args->args);
1323 /* Correctly handle nested argument lists */
1324 for (i = 0; i < n; i++) {
1325 expr_ty arg = (expr_ty)asdl_seq_GET(args->args, i);
1326 if (arg->kind == Tuple_kind) {
1327 PyObject *id = PyString_FromFormat(".%d", i);
1328 if (id == NULL) {
1329 return 0;
1330 }
1331 if (!compiler_nameop(c, id, Load)) {
1332 Py_DECREF(id);
1333 return 0;
1334 }
1335 Py_DECREF(id);
1336 VISIT(c, expr, arg);
1337 }
1338 }
1339 return 1;
1340 }
1341
1342 static int
compiler_function(struct compiler * c,stmt_ty s)1343 compiler_function(struct compiler *c, stmt_ty s)
1344 {
1345 PyCodeObject *co;
1346 PyObject *first_const = Py_None;
1347 arguments_ty args = s->v.FunctionDef.args;
1348 asdl_seq* decos = s->v.FunctionDef.decorator_list;
1349 stmt_ty st;
1350 int i, n, docstring;
1351
1352 assert(s->kind == FunctionDef_kind);
1353
1354 if (!compiler_decorators(c, decos))
1355 return 0;
1356 if (args->defaults)
1357 VISIT_SEQ(c, expr, args->defaults);
1358 if (!compiler_enter_scope(c, s->v.FunctionDef.name, (void *)s,
1359 s->lineno))
1360 return 0;
1361
1362 st = (stmt_ty)asdl_seq_GET(s->v.FunctionDef.body, 0);
1363 docstring = compiler_isdocstring(st);
1364 if (docstring && Py_OptimizeFlag < 2)
1365 first_const = st->v.Expr.value->v.Str.s;
1366 if (compiler_add_o(c, c->u->u_consts, first_const) < 0) {
1367 compiler_exit_scope(c);
1368 return 0;
1369 }
1370
1371 /* unpack nested arguments */
1372 compiler_arguments(c, args);
1373
1374 c->u->u_argcount = asdl_seq_LEN(args->args);
1375 n = asdl_seq_LEN(s->v.FunctionDef.body);
1376 /* if there was a docstring, we need to skip the first statement */
1377 for (i = docstring; i < n; i++) {
1378 st = (stmt_ty)asdl_seq_GET(s->v.FunctionDef.body, i);
1379 VISIT_IN_SCOPE(c, stmt, st);
1380 }
1381 co = assemble(c, 1);
1382 compiler_exit_scope(c);
1383 if (co == NULL)
1384 return 0;
1385
1386 compiler_make_closure(c, co, asdl_seq_LEN(args->defaults));
1387 Py_DECREF(co);
1388
1389 for (i = 0; i < asdl_seq_LEN(decos); i++) {
1390 ADDOP_I(c, CALL_FUNCTION, 1);
1391 }
1392
1393 return compiler_nameop(c, s->v.FunctionDef.name, Store);
1394 }
1395
1396 static int
compiler_class(struct compiler * c,stmt_ty s)1397 compiler_class(struct compiler *c, stmt_ty s)
1398 {
1399 int n, i;
1400 PyCodeObject *co;
1401 PyObject *str;
1402 asdl_seq* decos = s->v.ClassDef.decorator_list;
1403
1404 if (!compiler_decorators(c, decos))
1405 return 0;
1406
1407 /* push class name on stack, needed by BUILD_CLASS */
1408 ADDOP_O(c, LOAD_CONST, s->v.ClassDef.name, consts);
1409 /* push the tuple of base classes on the stack */
1410 n = asdl_seq_LEN(s->v.ClassDef.bases);
1411 if (n > 0)
1412 VISIT_SEQ(c, expr, s->v.ClassDef.bases);
1413 ADDOP_I(c, BUILD_TUPLE, n);
1414 if (!compiler_enter_scope(c, s->v.ClassDef.name, (void *)s,
1415 s->lineno))
1416 return 0;
1417 Py_INCREF(s->v.ClassDef.name);
1418 Py_XSETREF(c->u->u_private, s->v.ClassDef.name);
1419 str = PyString_InternFromString("__name__");
1420 if (!str || !compiler_nameop(c, str, Load)) {
1421 Py_XDECREF(str);
1422 compiler_exit_scope(c);
1423 return 0;
1424 }
1425
1426 Py_DECREF(str);
1427 str = PyString_InternFromString("__module__");
1428 if (!str || !compiler_nameop(c, str, Store)) {
1429 Py_XDECREF(str);
1430 compiler_exit_scope(c);
1431 return 0;
1432 }
1433 Py_DECREF(str);
1434
1435 if (!compiler_body(c, s->v.ClassDef.body)) {
1436 compiler_exit_scope(c);
1437 return 0;
1438 }
1439
1440 ADDOP_IN_SCOPE(c, LOAD_LOCALS);
1441 ADDOP_IN_SCOPE(c, RETURN_VALUE);
1442 co = assemble(c, 1);
1443 compiler_exit_scope(c);
1444 if (co == NULL)
1445 return 0;
1446
1447 compiler_make_closure(c, co, 0);
1448 Py_DECREF(co);
1449
1450 ADDOP_I(c, CALL_FUNCTION, 0);
1451 ADDOP(c, BUILD_CLASS);
1452 /* apply decorators */
1453 for (i = 0; i < asdl_seq_LEN(decos); i++) {
1454 ADDOP_I(c, CALL_FUNCTION, 1);
1455 }
1456 if (!compiler_nameop(c, s->v.ClassDef.name, Store))
1457 return 0;
1458 return 1;
1459 }
1460
1461 static int
compiler_ifexp(struct compiler * c,expr_ty e)1462 compiler_ifexp(struct compiler *c, expr_ty e)
1463 {
1464 basicblock *end, *next;
1465
1466 assert(e->kind == IfExp_kind);
1467 end = compiler_new_block(c);
1468 if (end == NULL)
1469 return 0;
1470 next = compiler_new_block(c);
1471 if (next == NULL)
1472 return 0;
1473 VISIT(c, expr, e->v.IfExp.test);
1474 ADDOP_JABS(c, POP_JUMP_IF_FALSE, next);
1475 VISIT(c, expr, e->v.IfExp.body);
1476 ADDOP_JREL(c, JUMP_FORWARD, end);
1477 compiler_use_next_block(c, next);
1478 VISIT(c, expr, e->v.IfExp.orelse);
1479 compiler_use_next_block(c, end);
1480 return 1;
1481 }
1482
1483 static int
compiler_lambda(struct compiler * c,expr_ty e)1484 compiler_lambda(struct compiler *c, expr_ty e)
1485 {
1486 PyCodeObject *co;
1487 static identifier name;
1488 arguments_ty args = e->v.Lambda.args;
1489 assert(e->kind == Lambda_kind);
1490
1491 if (!name) {
1492 name = PyString_InternFromString("<lambda>");
1493 if (!name)
1494 return 0;
1495 }
1496
1497 if (args->defaults)
1498 VISIT_SEQ(c, expr, args->defaults);
1499 if (!compiler_enter_scope(c, name, (void *)e, e->lineno))
1500 return 0;
1501
1502 /* unpack nested arguments */
1503 compiler_arguments(c, args);
1504
1505 /* Make None the first constant, so the lambda can't have a
1506 docstring. */
1507 if (compiler_add_o(c, c->u->u_consts, Py_None) < 0)
1508 return 0;
1509
1510 c->u->u_argcount = asdl_seq_LEN(args->args);
1511 VISIT_IN_SCOPE(c, expr, e->v.Lambda.body);
1512 if (c->u->u_ste->ste_generator) {
1513 ADDOP_IN_SCOPE(c, POP_TOP);
1514 }
1515 else {
1516 ADDOP_IN_SCOPE(c, RETURN_VALUE);
1517 }
1518 co = assemble(c, 1);
1519 compiler_exit_scope(c);
1520 if (co == NULL)
1521 return 0;
1522
1523 compiler_make_closure(c, co, asdl_seq_LEN(args->defaults));
1524 Py_DECREF(co);
1525
1526 return 1;
1527 }
1528
1529 static int
compiler_print(struct compiler * c,stmt_ty s)1530 compiler_print(struct compiler *c, stmt_ty s)
1531 {
1532 int i, n;
1533 bool dest;
1534
1535 assert(s->kind == Print_kind);
1536 n = asdl_seq_LEN(s->v.Print.values);
1537 dest = false;
1538 if (s->v.Print.dest) {
1539 VISIT(c, expr, s->v.Print.dest);
1540 dest = true;
1541 }
1542 for (i = 0; i < n; i++) {
1543 expr_ty e = (expr_ty)asdl_seq_GET(s->v.Print.values, i);
1544 if (dest) {
1545 ADDOP(c, DUP_TOP);
1546 VISIT(c, expr, e);
1547 ADDOP(c, ROT_TWO);
1548 ADDOP(c, PRINT_ITEM_TO);
1549 }
1550 else {
1551 VISIT(c, expr, e);
1552 ADDOP(c, PRINT_ITEM);
1553 }
1554 }
1555 if (s->v.Print.nl) {
1556 if (dest)
1557 ADDOP(c, PRINT_NEWLINE_TO)
1558 else
1559 ADDOP(c, PRINT_NEWLINE)
1560 }
1561 else if (dest)
1562 ADDOP(c, POP_TOP);
1563 return 1;
1564 }
1565
1566 static int
compiler_if(struct compiler * c,stmt_ty s)1567 compiler_if(struct compiler *c, stmt_ty s)
1568 {
1569 basicblock *end, *next;
1570 int constant;
1571 assert(s->kind == If_kind);
1572 end = compiler_new_block(c);
1573 if (end == NULL)
1574 return 0;
1575
1576 constant = expr_constant(s->v.If.test);
1577 /* constant = 0: "if 0"
1578 * constant = 1: "if 1", "if 2", ...
1579 * constant = -1: rest */
1580 if (constant == 0) {
1581 if (s->v.If.orelse)
1582 VISIT_SEQ(c, stmt, s->v.If.orelse);
1583 } else if (constant == 1) {
1584 VISIT_SEQ(c, stmt, s->v.If.body);
1585 } else {
1586 if (s->v.If.orelse) {
1587 next = compiler_new_block(c);
1588 if (next == NULL)
1589 return 0;
1590 }
1591 else
1592 next = end;
1593 VISIT(c, expr, s->v.If.test);
1594 ADDOP_JABS(c, POP_JUMP_IF_FALSE, next);
1595 VISIT_SEQ(c, stmt, s->v.If.body);
1596 ADDOP_JREL(c, JUMP_FORWARD, end);
1597 if (s->v.If.orelse) {
1598 compiler_use_next_block(c, next);
1599 VISIT_SEQ(c, stmt, s->v.If.orelse);
1600 }
1601 }
1602 compiler_use_next_block(c, end);
1603 return 1;
1604 }
1605
1606 static int
compiler_for(struct compiler * c,stmt_ty s)1607 compiler_for(struct compiler *c, stmt_ty s)
1608 {
1609 basicblock *start, *cleanup, *end;
1610
1611 start = compiler_new_block(c);
1612 cleanup = compiler_new_block(c);
1613 end = compiler_new_block(c);
1614 if (start == NULL || end == NULL || cleanup == NULL)
1615 return 0;
1616 ADDOP_JREL(c, SETUP_LOOP, end);
1617 if (!compiler_push_fblock(c, LOOP, start))
1618 return 0;
1619 VISIT(c, expr, s->v.For.iter);
1620 ADDOP(c, GET_ITER);
1621 compiler_use_next_block(c, start);
1622 ADDOP_JREL(c, FOR_ITER, cleanup);
1623 VISIT(c, expr, s->v.For.target);
1624 VISIT_SEQ(c, stmt, s->v.For.body);
1625 ADDOP_JABS(c, JUMP_ABSOLUTE, start);
1626 compiler_use_next_block(c, cleanup);
1627 ADDOP(c, POP_BLOCK);
1628 compiler_pop_fblock(c, LOOP, start);
1629 VISIT_SEQ(c, stmt, s->v.For.orelse);
1630 compiler_use_next_block(c, end);
1631 return 1;
1632 }
1633
1634 static int
compiler_while(struct compiler * c,stmt_ty s)1635 compiler_while(struct compiler *c, stmt_ty s)
1636 {
1637 basicblock *loop, *orelse, *end, *anchor = NULL;
1638 int constant = expr_constant(s->v.While.test);
1639
1640 if (constant == 0) {
1641 if (s->v.While.orelse)
1642 VISIT_SEQ(c, stmt, s->v.While.orelse);
1643 return 1;
1644 }
1645 loop = compiler_new_block(c);
1646 end = compiler_new_block(c);
1647 if (constant == -1) {
1648 anchor = compiler_new_block(c);
1649 if (anchor == NULL)
1650 return 0;
1651 }
1652 if (loop == NULL || end == NULL)
1653 return 0;
1654 if (s->v.While.orelse) {
1655 orelse = compiler_new_block(c);
1656 if (orelse == NULL)
1657 return 0;
1658 }
1659 else
1660 orelse = NULL;
1661
1662 ADDOP_JREL(c, SETUP_LOOP, end);
1663 compiler_use_next_block(c, loop);
1664 if (!compiler_push_fblock(c, LOOP, loop))
1665 return 0;
1666 if (constant == -1) {
1667 VISIT(c, expr, s->v.While.test);
1668 ADDOP_JABS(c, POP_JUMP_IF_FALSE, anchor);
1669 }
1670 VISIT_SEQ(c, stmt, s->v.While.body);
1671 ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
1672
1673 /* XXX should the two POP instructions be in a separate block
1674 if there is no else clause ?
1675 */
1676
1677 if (constant == -1)
1678 compiler_use_next_block(c, anchor);
1679 ADDOP(c, POP_BLOCK);
1680 compiler_pop_fblock(c, LOOP, loop);
1681 if (orelse != NULL) /* what if orelse is just pass? */
1682 VISIT_SEQ(c, stmt, s->v.While.orelse);
1683 compiler_use_next_block(c, end);
1684
1685 return 1;
1686 }
1687
1688 static int
compiler_continue(struct compiler * c)1689 compiler_continue(struct compiler *c)
1690 {
1691 static const char LOOP_ERROR_MSG[] = "'continue' not properly in loop";
1692 static const char IN_FINALLY_ERROR_MSG[] =
1693 "'continue' not supported inside 'finally' clause";
1694 int i;
1695
1696 if (!c->u->u_nfblocks)
1697 return compiler_error(c, LOOP_ERROR_MSG);
1698 i = c->u->u_nfblocks - 1;
1699 switch (c->u->u_fblock[i].fb_type) {
1700 case LOOP:
1701 ADDOP_JABS(c, JUMP_ABSOLUTE, c->u->u_fblock[i].fb_block);
1702 break;
1703 case EXCEPT:
1704 case FINALLY_TRY:
1705 while (--i >= 0 && c->u->u_fblock[i].fb_type != LOOP) {
1706 /* Prevent continue anywhere under a finally
1707 even if hidden in a sub-try or except. */
1708 if (c->u->u_fblock[i].fb_type == FINALLY_END)
1709 return compiler_error(c, IN_FINALLY_ERROR_MSG);
1710 }
1711 if (i == -1)
1712 return compiler_error(c, LOOP_ERROR_MSG);
1713 ADDOP_JABS(c, CONTINUE_LOOP, c->u->u_fblock[i].fb_block);
1714 break;
1715 case FINALLY_END:
1716 return compiler_error(c, IN_FINALLY_ERROR_MSG);
1717 }
1718
1719 return 1;
1720 }
1721
1722 /* Code generated for "try: <body> finally: <finalbody>" is as follows:
1723
1724 SETUP_FINALLY L
1725 <code for body>
1726 POP_BLOCK
1727 LOAD_CONST <None>
1728 L: <code for finalbody>
1729 END_FINALLY
1730
1731 The special instructions use the block stack. Each block
1732 stack entry contains the instruction that created it (here
1733 SETUP_FINALLY), the level of the value stack at the time the
1734 block stack entry was created, and a label (here L).
1735
1736 SETUP_FINALLY:
1737 Pushes the current value stack level and the label
1738 onto the block stack.
1739 POP_BLOCK:
1740 Pops en entry from the block stack, and pops the value
1741 stack until its level is the same as indicated on the
1742 block stack. (The label is ignored.)
1743 END_FINALLY:
1744 Pops a variable number of entries from the *value* stack
1745 and re-raises the exception they specify. The number of
1746 entries popped depends on the (pseudo) exception type.
1747
1748 The block stack is unwound when an exception is raised:
1749 when a SETUP_FINALLY entry is found, the exception is pushed
1750 onto the value stack (and the exception condition is cleared),
1751 and the interpreter jumps to the label gotten from the block
1752 stack.
1753 */
1754
1755 static int
compiler_try_finally(struct compiler * c,stmt_ty s)1756 compiler_try_finally(struct compiler *c, stmt_ty s)
1757 {
1758 basicblock *body, *end;
1759 body = compiler_new_block(c);
1760 end = compiler_new_block(c);
1761 if (body == NULL || end == NULL)
1762 return 0;
1763
1764 ADDOP_JREL(c, SETUP_FINALLY, end);
1765 compiler_use_next_block(c, body);
1766 if (!compiler_push_fblock(c, FINALLY_TRY, body))
1767 return 0;
1768 VISIT_SEQ(c, stmt, s->v.TryFinally.body);
1769 ADDOP(c, POP_BLOCK);
1770 compiler_pop_fblock(c, FINALLY_TRY, body);
1771
1772 ADDOP_O(c, LOAD_CONST, Py_None, consts);
1773 compiler_use_next_block(c, end);
1774 if (!compiler_push_fblock(c, FINALLY_END, end))
1775 return 0;
1776 VISIT_SEQ(c, stmt, s->v.TryFinally.finalbody);
1777 ADDOP(c, END_FINALLY);
1778 compiler_pop_fblock(c, FINALLY_END, end);
1779
1780 return 1;
1781 }
1782
1783 /*
1784 Code generated for "try: S except E1, V1: S1 except E2, V2: S2 ...":
1785 (The contents of the value stack is shown in [], with the top
1786 at the right; 'tb' is trace-back info, 'val' the exception's
1787 associated value, and 'exc' the exception.)
1788
1789 Value stack Label Instruction Argument
1790 [] SETUP_EXCEPT L1
1791 [] <code for S>
1792 [] POP_BLOCK
1793 [] JUMP_FORWARD L0
1794
1795 [tb, val, exc] L1: DUP )
1796 [tb, val, exc, exc] <evaluate E1> )
1797 [tb, val, exc, exc, E1] COMPARE_OP EXC_MATCH ) only if E1
1798 [tb, val, exc, 1-or-0] POP_JUMP_IF_FALSE L2 )
1799 [tb, val, exc] POP
1800 [tb, val] <assign to V1> (or POP if no V1)
1801 [tb] POP
1802 [] <code for S1>
1803 JUMP_FORWARD L0
1804
1805 [tb, val, exc] L2: DUP
1806 .............................etc.......................
1807
1808 [tb, val, exc] Ln+1: END_FINALLY # re-raise exception
1809
1810 [] L0: <next statement>
1811
1812 Of course, parts are not generated if Vi or Ei is not present.
1813 */
1814 static int
compiler_try_except(struct compiler * c,stmt_ty s)1815 compiler_try_except(struct compiler *c, stmt_ty s)
1816 {
1817 basicblock *body, *orelse, *except, *end;
1818 int i, n;
1819
1820 body = compiler_new_block(c);
1821 except = compiler_new_block(c);
1822 orelse = compiler_new_block(c);
1823 end = compiler_new_block(c);
1824 if (body == NULL || except == NULL || orelse == NULL || end == NULL)
1825 return 0;
1826 ADDOP_JREL(c, SETUP_EXCEPT, except);
1827 compiler_use_next_block(c, body);
1828 if (!compiler_push_fblock(c, EXCEPT, body))
1829 return 0;
1830 VISIT_SEQ(c, stmt, s->v.TryExcept.body);
1831 ADDOP(c, POP_BLOCK);
1832 compiler_pop_fblock(c, EXCEPT, body);
1833 ADDOP_JREL(c, JUMP_FORWARD, orelse);
1834 n = asdl_seq_LEN(s->v.TryExcept.handlers);
1835 compiler_use_next_block(c, except);
1836 for (i = 0; i < n; i++) {
1837 excepthandler_ty handler = (excepthandler_ty)asdl_seq_GET(
1838 s->v.TryExcept.handlers, i);
1839 if (!handler->v.ExceptHandler.type && i < n-1)
1840 return compiler_error(c, "default 'except:' must be last");
1841 c->u->u_lineno_set = false;
1842 c->u->u_lineno = handler->lineno;
1843 except = compiler_new_block(c);
1844 if (except == NULL)
1845 return 0;
1846 if (handler->v.ExceptHandler.type) {
1847 ADDOP(c, DUP_TOP);
1848 VISIT(c, expr, handler->v.ExceptHandler.type);
1849 ADDOP_I(c, COMPARE_OP, PyCmp_EXC_MATCH);
1850 ADDOP_JABS(c, POP_JUMP_IF_FALSE, except);
1851 }
1852 ADDOP(c, POP_TOP);
1853 if (handler->v.ExceptHandler.name) {
1854 VISIT(c, expr, handler->v.ExceptHandler.name);
1855 }
1856 else {
1857 ADDOP(c, POP_TOP);
1858 }
1859 ADDOP(c, POP_TOP);
1860 VISIT_SEQ(c, stmt, handler->v.ExceptHandler.body);
1861 ADDOP_JREL(c, JUMP_FORWARD, end);
1862 compiler_use_next_block(c, except);
1863 }
1864 ADDOP(c, END_FINALLY);
1865 compiler_use_next_block(c, orelse);
1866 VISIT_SEQ(c, stmt, s->v.TryExcept.orelse);
1867 compiler_use_next_block(c, end);
1868 return 1;
1869 }
1870
1871 static int
compiler_import_as(struct compiler * c,identifier name,identifier asname)1872 compiler_import_as(struct compiler *c, identifier name, identifier asname)
1873 {
1874 /* The IMPORT_NAME opcode was already generated. This function
1875 merely needs to bind the result to a name.
1876
1877 If there is a dot in name, we need to split it and emit a
1878 LOAD_ATTR for each name.
1879 */
1880 const char *src = PyString_AS_STRING(name);
1881 const char *dot = strchr(src, '.');
1882 if (dot) {
1883 /* Consume the base module name to get the first attribute */
1884 src = dot + 1;
1885 while (dot) {
1886 /* NB src is only defined when dot != NULL */
1887 PyObject *attr;
1888 dot = strchr(src, '.');
1889 attr = PyString_FromStringAndSize(src,
1890 dot ? dot - src : strlen(src));
1891 if (!attr)
1892 return 0;
1893 ADDOP_O(c, LOAD_ATTR, attr, names);
1894 Py_DECREF(attr);
1895 src = dot + 1;
1896 }
1897 }
1898 return compiler_nameop(c, asname, Store);
1899 }
1900
1901 static int
compiler_import(struct compiler * c,stmt_ty s)1902 compiler_import(struct compiler *c, stmt_ty s)
1903 {
1904 /* The Import node stores a module name like a.b.c as a single
1905 string. This is convenient for all cases except
1906 import a.b.c as d
1907 where we need to parse that string to extract the individual
1908 module names.
1909 XXX Perhaps change the representation to make this case simpler?
1910 */
1911 int i, n = asdl_seq_LEN(s->v.Import.names);
1912
1913 for (i = 0; i < n; i++) {
1914 alias_ty alias = (alias_ty)asdl_seq_GET(s->v.Import.names, i);
1915 int r;
1916 PyObject *level;
1917
1918 if (c->c_flags && (c->c_flags->cf_flags & CO_FUTURE_ABSOLUTE_IMPORT))
1919 level = PyInt_FromLong(0);
1920 else
1921 level = PyInt_FromLong(-1);
1922
1923 if (level == NULL)
1924 return 0;
1925
1926 ADDOP_O(c, LOAD_CONST, level, consts);
1927 Py_DECREF(level);
1928 ADDOP_O(c, LOAD_CONST, Py_None, consts);
1929 ADDOP_NAME(c, IMPORT_NAME, alias->name, names);
1930
1931 if (alias->asname) {
1932 r = compiler_import_as(c, alias->name, alias->asname);
1933 if (!r)
1934 return r;
1935 }
1936 else {
1937 identifier tmp = alias->name;
1938 const char *base = PyString_AS_STRING(alias->name);
1939 char *dot = strchr(base, '.');
1940 if (dot) {
1941 tmp = PyString_FromStringAndSize(base,
1942 dot - base);
1943 if (tmp == NULL)
1944 return 0;
1945 }
1946 r = compiler_nameop(c, tmp, Store);
1947 if (dot) {
1948 Py_DECREF(tmp);
1949 }
1950 if (!r)
1951 return r;
1952 }
1953 }
1954 return 1;
1955 }
1956
1957 static int
compiler_from_import(struct compiler * c,stmt_ty s)1958 compiler_from_import(struct compiler *c, stmt_ty s)
1959 {
1960 int i, n = asdl_seq_LEN(s->v.ImportFrom.names);
1961
1962 PyObject *names = PyTuple_New(n);
1963 PyObject *level;
1964 static PyObject *empty_string;
1965
1966 if (!empty_string) {
1967 empty_string = PyString_FromString("");
1968 if (!empty_string)
1969 return 0;
1970 }
1971
1972 if (!names)
1973 return 0;
1974
1975 if (s->v.ImportFrom.level == 0 && c->c_flags &&
1976 !(c->c_flags->cf_flags & CO_FUTURE_ABSOLUTE_IMPORT))
1977 level = PyInt_FromLong(-1);
1978 else
1979 level = PyInt_FromLong(s->v.ImportFrom.level);
1980
1981 if (!level) {
1982 Py_DECREF(names);
1983 return 0;
1984 }
1985
1986 /* build up the names */
1987 for (i = 0; i < n; i++) {
1988 alias_ty alias = (alias_ty)asdl_seq_GET(s->v.ImportFrom.names, i);
1989 Py_INCREF(alias->name);
1990 PyTuple_SET_ITEM(names, i, alias->name);
1991 }
1992
1993 if (s->lineno > c->c_future->ff_lineno && s->v.ImportFrom.module &&
1994 !strcmp(PyString_AS_STRING(s->v.ImportFrom.module), "__future__")) {
1995 Py_DECREF(level);
1996 Py_DECREF(names);
1997 return compiler_error(c, "from __future__ imports must occur "
1998 "at the beginning of the file");
1999 }
2000
2001 ADDOP_O(c, LOAD_CONST, level, consts);
2002 Py_DECREF(level);
2003 ADDOP_O(c, LOAD_CONST, names, consts);
2004 Py_DECREF(names);
2005 if (s->v.ImportFrom.module) {
2006 ADDOP_NAME(c, IMPORT_NAME, s->v.ImportFrom.module, names);
2007 }
2008 else {
2009 ADDOP_NAME(c, IMPORT_NAME, empty_string, names);
2010 }
2011 for (i = 0; i < n; i++) {
2012 alias_ty alias = (alias_ty)asdl_seq_GET(s->v.ImportFrom.names, i);
2013 identifier store_name;
2014
2015 if (i == 0 && *PyString_AS_STRING(alias->name) == '*') {
2016 assert(n == 1);
2017 ADDOP(c, IMPORT_STAR);
2018 return 1;
2019 }
2020
2021 ADDOP_NAME(c, IMPORT_FROM, alias->name, names);
2022 store_name = alias->name;
2023 if (alias->asname)
2024 store_name = alias->asname;
2025
2026 if (!compiler_nameop(c, store_name, Store)) {
2027 Py_DECREF(names);
2028 return 0;
2029 }
2030 }
2031 /* remove imported module */
2032 ADDOP(c, POP_TOP);
2033 return 1;
2034 }
2035
2036 static int
compiler_assert(struct compiler * c,stmt_ty s)2037 compiler_assert(struct compiler *c, stmt_ty s)
2038 {
2039 static PyObject *assertion_error = NULL;
2040 basicblock *end;
2041
2042 if (Py_OptimizeFlag)
2043 return 1;
2044 if (assertion_error == NULL) {
2045 assertion_error = PyString_InternFromString("AssertionError");
2046 if (assertion_error == NULL)
2047 return 0;
2048 }
2049 if (s->v.Assert.test->kind == Tuple_kind &&
2050 asdl_seq_LEN(s->v.Assert.test->v.Tuple.elts) > 0) {
2051 const char* msg =
2052 "assertion is always true, perhaps remove parentheses?";
2053 if (PyErr_WarnExplicit(PyExc_SyntaxWarning, msg, c->c_filename,
2054 c->u->u_lineno, NULL, NULL) == -1)
2055 return 0;
2056 }
2057 VISIT(c, expr, s->v.Assert.test);
2058 end = compiler_new_block(c);
2059 if (end == NULL)
2060 return 0;
2061 ADDOP_JABS(c, POP_JUMP_IF_TRUE, end);
2062 ADDOP_O(c, LOAD_GLOBAL, assertion_error, names);
2063 if (s->v.Assert.msg) {
2064 VISIT(c, expr, s->v.Assert.msg);
2065 ADDOP_I(c, CALL_FUNCTION, 1);
2066 }
2067 ADDOP_I(c, RAISE_VARARGS, 1);
2068 compiler_use_next_block(c, end);
2069 return 1;
2070 }
2071
2072 static int
compiler_visit_stmt(struct compiler * c,stmt_ty s)2073 compiler_visit_stmt(struct compiler *c, stmt_ty s)
2074 {
2075 int i, n;
2076
2077 /* Always assign a lineno to the next instruction for a stmt. */
2078 c->u->u_lineno = s->lineno;
2079 c->u->u_lineno_set = false;
2080
2081 switch (s->kind) {
2082 case FunctionDef_kind:
2083 return compiler_function(c, s);
2084 case ClassDef_kind:
2085 return compiler_class(c, s);
2086 case Return_kind:
2087 if (c->u->u_ste->ste_type != FunctionBlock)
2088 return compiler_error(c, "'return' outside function");
2089 if (s->v.Return.value) {
2090 VISIT(c, expr, s->v.Return.value);
2091 }
2092 else
2093 ADDOP_O(c, LOAD_CONST, Py_None, consts);
2094 ADDOP(c, RETURN_VALUE);
2095 break;
2096 case Delete_kind:
2097 VISIT_SEQ(c, expr, s->v.Delete.targets)
2098 break;
2099 case Assign_kind:
2100 n = asdl_seq_LEN(s->v.Assign.targets);
2101 VISIT(c, expr, s->v.Assign.value);
2102 for (i = 0; i < n; i++) {
2103 if (i < n - 1)
2104 ADDOP(c, DUP_TOP);
2105 VISIT(c, expr,
2106 (expr_ty)asdl_seq_GET(s->v.Assign.targets, i));
2107 }
2108 break;
2109 case AugAssign_kind:
2110 return compiler_augassign(c, s);
2111 case Print_kind:
2112 return compiler_print(c, s);
2113 case For_kind:
2114 return compiler_for(c, s);
2115 case While_kind:
2116 return compiler_while(c, s);
2117 case If_kind:
2118 return compiler_if(c, s);
2119 case Raise_kind:
2120 n = 0;
2121 if (s->v.Raise.type) {
2122 VISIT(c, expr, s->v.Raise.type);
2123 n++;
2124 if (s->v.Raise.inst) {
2125 VISIT(c, expr, s->v.Raise.inst);
2126 n++;
2127 if (s->v.Raise.tback) {
2128 VISIT(c, expr, s->v.Raise.tback);
2129 n++;
2130 }
2131 }
2132 }
2133 ADDOP_I(c, RAISE_VARARGS, n);
2134 break;
2135 case TryExcept_kind:
2136 return compiler_try_except(c, s);
2137 case TryFinally_kind:
2138 return compiler_try_finally(c, s);
2139 case Assert_kind:
2140 return compiler_assert(c, s);
2141 case Import_kind:
2142 return compiler_import(c, s);
2143 case ImportFrom_kind:
2144 return compiler_from_import(c, s);
2145 case Exec_kind:
2146 VISIT(c, expr, s->v.Exec.body);
2147 if (s->v.Exec.globals) {
2148 VISIT(c, expr, s->v.Exec.globals);
2149 if (s->v.Exec.locals) {
2150 VISIT(c, expr, s->v.Exec.locals);
2151 } else {
2152 ADDOP(c, DUP_TOP);
2153 }
2154 } else {
2155 ADDOP_O(c, LOAD_CONST, Py_None, consts);
2156 ADDOP(c, DUP_TOP);
2157 }
2158 ADDOP(c, EXEC_STMT);
2159 break;
2160 case Global_kind:
2161 break;
2162 case Expr_kind:
2163 if (c->c_interactive && c->c_nestlevel <= 1) {
2164 VISIT(c, expr, s->v.Expr.value);
2165 ADDOP(c, PRINT_EXPR);
2166 }
2167 else if (s->v.Expr.value->kind != Str_kind &&
2168 s->v.Expr.value->kind != Num_kind) {
2169 VISIT(c, expr, s->v.Expr.value);
2170 ADDOP(c, POP_TOP);
2171 }
2172 break;
2173 case Pass_kind:
2174 break;
2175 case Break_kind:
2176 if (!compiler_in_loop(c))
2177 return compiler_error(c, "'break' outside loop");
2178 ADDOP(c, BREAK_LOOP);
2179 break;
2180 case Continue_kind:
2181 return compiler_continue(c);
2182 case With_kind:
2183 return compiler_with(c, s);
2184 }
2185 return 1;
2186 }
2187
2188 static int
unaryop(unaryop_ty op)2189 unaryop(unaryop_ty op)
2190 {
2191 switch (op) {
2192 case Invert:
2193 return UNARY_INVERT;
2194 case Not:
2195 return UNARY_NOT;
2196 case UAdd:
2197 return UNARY_POSITIVE;
2198 case USub:
2199 return UNARY_NEGATIVE;
2200 default:
2201 PyErr_Format(PyExc_SystemError,
2202 "unary op %d should not be possible", op);
2203 return 0;
2204 }
2205 }
2206
2207 static int
binop(struct compiler * c,operator_ty op)2208 binop(struct compiler *c, operator_ty op)
2209 {
2210 switch (op) {
2211 case Add:
2212 return BINARY_ADD;
2213 case Sub:
2214 return BINARY_SUBTRACT;
2215 case Mult:
2216 return BINARY_MULTIPLY;
2217 case Div:
2218 if (c->c_flags && c->c_flags->cf_flags & CO_FUTURE_DIVISION)
2219 return BINARY_TRUE_DIVIDE;
2220 else
2221 return BINARY_DIVIDE;
2222 case Mod:
2223 return BINARY_MODULO;
2224 case Pow:
2225 return BINARY_POWER;
2226 case LShift:
2227 return BINARY_LSHIFT;
2228 case RShift:
2229 return BINARY_RSHIFT;
2230 case BitOr:
2231 return BINARY_OR;
2232 case BitXor:
2233 return BINARY_XOR;
2234 case BitAnd:
2235 return BINARY_AND;
2236 case FloorDiv:
2237 return BINARY_FLOOR_DIVIDE;
2238 default:
2239 PyErr_Format(PyExc_SystemError,
2240 "binary op %d should not be possible", op);
2241 return 0;
2242 }
2243 }
2244
2245 static int
cmpop(cmpop_ty op)2246 cmpop(cmpop_ty op)
2247 {
2248 switch (op) {
2249 case Eq:
2250 return PyCmp_EQ;
2251 case NotEq:
2252 return PyCmp_NE;
2253 case Lt:
2254 return PyCmp_LT;
2255 case LtE:
2256 return PyCmp_LE;
2257 case Gt:
2258 return PyCmp_GT;
2259 case GtE:
2260 return PyCmp_GE;
2261 case Is:
2262 return PyCmp_IS;
2263 case IsNot:
2264 return PyCmp_IS_NOT;
2265 case In:
2266 return PyCmp_IN;
2267 case NotIn:
2268 return PyCmp_NOT_IN;
2269 default:
2270 return PyCmp_BAD;
2271 }
2272 }
2273
2274 static int
inplace_binop(struct compiler * c,operator_ty op)2275 inplace_binop(struct compiler *c, operator_ty op)
2276 {
2277 switch (op) {
2278 case Add:
2279 return INPLACE_ADD;
2280 case Sub:
2281 return INPLACE_SUBTRACT;
2282 case Mult:
2283 return INPLACE_MULTIPLY;
2284 case Div:
2285 if (c->c_flags && c->c_flags->cf_flags & CO_FUTURE_DIVISION)
2286 return INPLACE_TRUE_DIVIDE;
2287 else
2288 return INPLACE_DIVIDE;
2289 case Mod:
2290 return INPLACE_MODULO;
2291 case Pow:
2292 return INPLACE_POWER;
2293 case LShift:
2294 return INPLACE_LSHIFT;
2295 case RShift:
2296 return INPLACE_RSHIFT;
2297 case BitOr:
2298 return INPLACE_OR;
2299 case BitXor:
2300 return INPLACE_XOR;
2301 case BitAnd:
2302 return INPLACE_AND;
2303 case FloorDiv:
2304 return INPLACE_FLOOR_DIVIDE;
2305 default:
2306 PyErr_Format(PyExc_SystemError,
2307 "inplace binary op %d should not be possible", op);
2308 return 0;
2309 }
2310 }
2311
2312 static int
compiler_nameop(struct compiler * c,identifier name,expr_context_ty ctx)2313 compiler_nameop(struct compiler *c, identifier name, expr_context_ty ctx)
2314 {
2315 int op, scope, arg;
2316 enum { OP_FAST, OP_GLOBAL, OP_DEREF, OP_NAME } optype;
2317
2318 PyObject *dict = c->u->u_names;
2319 PyObject *mangled;
2320 /* XXX AugStore isn't used anywhere! */
2321
2322 mangled = _Py_Mangle(c->u->u_private, name);
2323 if (!mangled)
2324 return 0;
2325
2326 op = 0;
2327 optype = OP_NAME;
2328 scope = PyST_GetScope(c->u->u_ste, mangled);
2329 switch (scope) {
2330 case FREE:
2331 dict = c->u->u_freevars;
2332 optype = OP_DEREF;
2333 break;
2334 case CELL:
2335 dict = c->u->u_cellvars;
2336 optype = OP_DEREF;
2337 break;
2338 case LOCAL:
2339 if (c->u->u_ste->ste_type == FunctionBlock)
2340 optype = OP_FAST;
2341 break;
2342 case GLOBAL_IMPLICIT:
2343 if (c->u->u_ste->ste_type == FunctionBlock &&
2344 !c->u->u_ste->ste_unoptimized)
2345 optype = OP_GLOBAL;
2346 break;
2347 case GLOBAL_EXPLICIT:
2348 optype = OP_GLOBAL;
2349 break;
2350 default:
2351 /* scope can be 0 */
2352 break;
2353 }
2354
2355 /* XXX Leave assert here, but handle __doc__ and the like better */
2356 assert(scope || PyString_AS_STRING(name)[0] == '_');
2357
2358 switch (optype) {
2359 case OP_DEREF:
2360 switch (ctx) {
2361 case Load: op = LOAD_DEREF; break;
2362 case Store: op = STORE_DEREF; break;
2363 case AugLoad:
2364 case AugStore:
2365 break;
2366 case Del:
2367 PyErr_Format(PyExc_SyntaxError,
2368 "can not delete variable '%s' referenced "
2369 "in nested scope",
2370 PyString_AS_STRING(name));
2371 Py_DECREF(mangled);
2372 return 0;
2373 case Param:
2374 default:
2375 PyErr_SetString(PyExc_SystemError,
2376 "param invalid for deref variable");
2377 return 0;
2378 }
2379 break;
2380 case OP_FAST:
2381 switch (ctx) {
2382 case Load: op = LOAD_FAST; break;
2383 case Store: op = STORE_FAST; break;
2384 case Del: op = DELETE_FAST; break;
2385 case AugLoad:
2386 case AugStore:
2387 break;
2388 case Param:
2389 default:
2390 PyErr_SetString(PyExc_SystemError,
2391 "param invalid for local variable");
2392 return 0;
2393 }
2394 ADDOP_O(c, op, mangled, varnames);
2395 Py_DECREF(mangled);
2396 return 1;
2397 case OP_GLOBAL:
2398 switch (ctx) {
2399 case Load: op = LOAD_GLOBAL; break;
2400 case Store: op = STORE_GLOBAL; break;
2401 case Del: op = DELETE_GLOBAL; break;
2402 case AugLoad:
2403 case AugStore:
2404 break;
2405 case Param:
2406 default:
2407 PyErr_SetString(PyExc_SystemError,
2408 "param invalid for global variable");
2409 return 0;
2410 }
2411 break;
2412 case OP_NAME:
2413 switch (ctx) {
2414 case Load: op = LOAD_NAME; break;
2415 case Store: op = STORE_NAME; break;
2416 case Del: op = DELETE_NAME; break;
2417 case AugLoad:
2418 case AugStore:
2419 break;
2420 case Param:
2421 default:
2422 PyErr_SetString(PyExc_SystemError,
2423 "param invalid for name variable");
2424 return 0;
2425 }
2426 break;
2427 }
2428
2429 assert(op);
2430 arg = compiler_add_o(c, dict, mangled);
2431 Py_DECREF(mangled);
2432 if (arg < 0)
2433 return 0;
2434 return compiler_addop_i(c, op, arg);
2435 }
2436
2437 static int
compiler_boolop(struct compiler * c,expr_ty e)2438 compiler_boolop(struct compiler *c, expr_ty e)
2439 {
2440 basicblock *end;
2441 int jumpi, i, n;
2442 asdl_seq *s;
2443
2444 assert(e->kind == BoolOp_kind);
2445 if (e->v.BoolOp.op == And)
2446 jumpi = JUMP_IF_FALSE_OR_POP;
2447 else
2448 jumpi = JUMP_IF_TRUE_OR_POP;
2449 end = compiler_new_block(c);
2450 if (end == NULL)
2451 return 0;
2452 s = e->v.BoolOp.values;
2453 n = asdl_seq_LEN(s) - 1;
2454 assert(n >= 0);
2455 for (i = 0; i < n; ++i) {
2456 VISIT(c, expr, (expr_ty)asdl_seq_GET(s, i));
2457 ADDOP_JABS(c, jumpi, end);
2458 }
2459 VISIT(c, expr, (expr_ty)asdl_seq_GET(s, n));
2460 compiler_use_next_block(c, end);
2461 return 1;
2462 }
2463
2464 static int
compiler_list(struct compiler * c,expr_ty e)2465 compiler_list(struct compiler *c, expr_ty e)
2466 {
2467 int n = asdl_seq_LEN(e->v.List.elts);
2468 if (e->v.List.ctx == Store) {
2469 ADDOP_I(c, UNPACK_SEQUENCE, n);
2470 }
2471 VISIT_SEQ(c, expr, e->v.List.elts);
2472 if (e->v.List.ctx == Load) {
2473 ADDOP_I(c, BUILD_LIST, n);
2474 }
2475 return 1;
2476 }
2477
2478 static int
compiler_tuple(struct compiler * c,expr_ty e)2479 compiler_tuple(struct compiler *c, expr_ty e)
2480 {
2481 int n = asdl_seq_LEN(e->v.Tuple.elts);
2482 if (e->v.Tuple.ctx == Store) {
2483 ADDOP_I(c, UNPACK_SEQUENCE, n);
2484 }
2485 VISIT_SEQ(c, expr, e->v.Tuple.elts);
2486 if (e->v.Tuple.ctx == Load) {
2487 ADDOP_I(c, BUILD_TUPLE, n);
2488 }
2489 return 1;
2490 }
2491
2492 static int
compiler_compare(struct compiler * c,expr_ty e)2493 compiler_compare(struct compiler *c, expr_ty e)
2494 {
2495 int i, n;
2496 basicblock *cleanup = NULL;
2497
2498 /* XXX the logic can be cleaned up for 1 or multiple comparisons */
2499 VISIT(c, expr, e->v.Compare.left);
2500 n = asdl_seq_LEN(e->v.Compare.ops);
2501 assert(n > 0);
2502 if (n > 1) {
2503 cleanup = compiler_new_block(c);
2504 if (cleanup == NULL)
2505 return 0;
2506 VISIT(c, expr,
2507 (expr_ty)asdl_seq_GET(e->v.Compare.comparators, 0));
2508 }
2509 for (i = 1; i < n; i++) {
2510 ADDOP(c, DUP_TOP);
2511 ADDOP(c, ROT_THREE);
2512 ADDOP_I(c, COMPARE_OP,
2513 cmpop((cmpop_ty)(asdl_seq_GET(
2514 e->v.Compare.ops, i - 1))));
2515 ADDOP_JABS(c, JUMP_IF_FALSE_OR_POP, cleanup);
2516 NEXT_BLOCK(c);
2517 if (i < (n - 1))
2518 VISIT(c, expr,
2519 (expr_ty)asdl_seq_GET(e->v.Compare.comparators, i));
2520 }
2521 VISIT(c, expr, (expr_ty)asdl_seq_GET(e->v.Compare.comparators, n - 1));
2522 ADDOP_I(c, COMPARE_OP,
2523 cmpop((cmpop_ty)(asdl_seq_GET(e->v.Compare.ops, n - 1))));
2524 if (n > 1) {
2525 basicblock *end = compiler_new_block(c);
2526 if (end == NULL)
2527 return 0;
2528 ADDOP_JREL(c, JUMP_FORWARD, end);
2529 compiler_use_next_block(c, cleanup);
2530 ADDOP(c, ROT_TWO);
2531 ADDOP(c, POP_TOP);
2532 compiler_use_next_block(c, end);
2533 }
2534 return 1;
2535 }
2536
2537 static int
compiler_call(struct compiler * c,expr_ty e)2538 compiler_call(struct compiler *c, expr_ty e)
2539 {
2540 int n, code = 0;
2541
2542 VISIT(c, expr, e->v.Call.func);
2543 n = asdl_seq_LEN(e->v.Call.args);
2544 VISIT_SEQ(c, expr, e->v.Call.args);
2545 if (e->v.Call.keywords) {
2546 VISIT_SEQ(c, keyword, e->v.Call.keywords);
2547 n |= asdl_seq_LEN(e->v.Call.keywords) << 8;
2548 }
2549 if (e->v.Call.starargs) {
2550 VISIT(c, expr, e->v.Call.starargs);
2551 code |= 1;
2552 }
2553 if (e->v.Call.kwargs) {
2554 VISIT(c, expr, e->v.Call.kwargs);
2555 code |= 2;
2556 }
2557 switch (code) {
2558 case 0:
2559 ADDOP_I(c, CALL_FUNCTION, n);
2560 break;
2561 case 1:
2562 ADDOP_I(c, CALL_FUNCTION_VAR, n);
2563 break;
2564 case 2:
2565 ADDOP_I(c, CALL_FUNCTION_KW, n);
2566 break;
2567 case 3:
2568 ADDOP_I(c, CALL_FUNCTION_VAR_KW, n);
2569 break;
2570 }
2571 return 1;
2572 }
2573
2574 static int
compiler_listcomp_generator(struct compiler * c,asdl_seq * generators,int gen_index,expr_ty elt)2575 compiler_listcomp_generator(struct compiler *c, asdl_seq *generators,
2576 int gen_index, expr_ty elt)
2577 {
2578 /* generate code for the iterator, then each of the ifs,
2579 and then write to the element */
2580
2581 comprehension_ty l;
2582 basicblock *start, *anchor, *skip, *if_cleanup;
2583 int i, n;
2584
2585 start = compiler_new_block(c);
2586 skip = compiler_new_block(c);
2587 if_cleanup = compiler_new_block(c);
2588 anchor = compiler_new_block(c);
2589
2590 if (start == NULL || skip == NULL || if_cleanup == NULL ||
2591 anchor == NULL)
2592 return 0;
2593
2594 l = (comprehension_ty)asdl_seq_GET(generators, gen_index);
2595 VISIT(c, expr, l->iter);
2596 ADDOP(c, GET_ITER);
2597 compiler_use_next_block(c, start);
2598 ADDOP_JREL(c, FOR_ITER, anchor);
2599 NEXT_BLOCK(c);
2600 VISIT(c, expr, l->target);
2601
2602 /* XXX this needs to be cleaned up...a lot! */
2603 n = asdl_seq_LEN(l->ifs);
2604 for (i = 0; i < n; i++) {
2605 expr_ty e = (expr_ty)asdl_seq_GET(l->ifs, i);
2606 VISIT(c, expr, e);
2607 ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup);
2608 NEXT_BLOCK(c);
2609 }
2610
2611 if (++gen_index < asdl_seq_LEN(generators))
2612 if (!compiler_listcomp_generator(c, generators, gen_index, elt))
2613 return 0;
2614
2615 /* only append after the last for generator */
2616 if (gen_index >= asdl_seq_LEN(generators)) {
2617 VISIT(c, expr, elt);
2618 ADDOP_I(c, LIST_APPEND, gen_index+1);
2619
2620 compiler_use_next_block(c, skip);
2621 }
2622 compiler_use_next_block(c, if_cleanup);
2623 ADDOP_JABS(c, JUMP_ABSOLUTE, start);
2624 compiler_use_next_block(c, anchor);
2625
2626 return 1;
2627 }
2628
2629 static int
compiler_listcomp(struct compiler * c,expr_ty e)2630 compiler_listcomp(struct compiler *c, expr_ty e)
2631 {
2632 assert(e->kind == ListComp_kind);
2633 ADDOP_I(c, BUILD_LIST, 0);
2634 return compiler_listcomp_generator(c, e->v.ListComp.generators, 0,
2635 e->v.ListComp.elt);
2636 }
2637
2638 /* Dict and set comprehensions and generator expressions work by creating a
2639 nested function to perform the actual iteration. This means that the
2640 iteration variables don't leak into the current scope.
2641 The defined function is called immediately following its definition, with the
2642 result of that call being the result of the expression.
2643 The LC/SC version returns the populated container, while the GE version is
2644 flagged in symtable.c as a generator, so it returns the generator object
2645 when the function is called.
2646 This code *knows* that the loop cannot contain break, continue, or return,
2647 so it cheats and skips the SETUP_LOOP/POP_BLOCK steps used in normal loops.
2648
2649 Possible cleanups:
2650 - iterate over the generator sequence instead of using recursion
2651 */
2652
2653 static int
compiler_comprehension_generator(struct compiler * c,asdl_seq * generators,int gen_index,expr_ty elt,expr_ty val,int type)2654 compiler_comprehension_generator(struct compiler *c,
2655 asdl_seq *generators, int gen_index,
2656 expr_ty elt, expr_ty val, int type)
2657 {
2658 /* generate code for the iterator, then each of the ifs,
2659 and then write to the element */
2660
2661 comprehension_ty gen;
2662 basicblock *start, *anchor, *skip, *if_cleanup;
2663 int i, n;
2664
2665 start = compiler_new_block(c);
2666 skip = compiler_new_block(c);
2667 if_cleanup = compiler_new_block(c);
2668 anchor = compiler_new_block(c);
2669
2670 if (start == NULL || skip == NULL || if_cleanup == NULL ||
2671 anchor == NULL)
2672 return 0;
2673
2674 gen = (comprehension_ty)asdl_seq_GET(generators, gen_index);
2675
2676 if (gen_index == 0) {
2677 /* Receive outermost iter as an implicit argument */
2678 c->u->u_argcount = 1;
2679 ADDOP_I(c, LOAD_FAST, 0);
2680 }
2681 else {
2682 /* Sub-iter - calculate on the fly */
2683 VISIT(c, expr, gen->iter);
2684 ADDOP(c, GET_ITER);
2685 }
2686 compiler_use_next_block(c, start);
2687 ADDOP_JREL(c, FOR_ITER, anchor);
2688 NEXT_BLOCK(c);
2689 VISIT(c, expr, gen->target);
2690
2691 /* XXX this needs to be cleaned up...a lot! */
2692 n = asdl_seq_LEN(gen->ifs);
2693 for (i = 0; i < n; i++) {
2694 expr_ty e = (expr_ty)asdl_seq_GET(gen->ifs, i);
2695 VISIT(c, expr, e);
2696 ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup);
2697 NEXT_BLOCK(c);
2698 }
2699
2700 if (++gen_index < asdl_seq_LEN(generators))
2701 if (!compiler_comprehension_generator(c,
2702 generators, gen_index,
2703 elt, val, type))
2704 return 0;
2705
2706 /* only append after the last for generator */
2707 if (gen_index >= asdl_seq_LEN(generators)) {
2708 /* comprehension specific code */
2709 switch (type) {
2710 case COMP_GENEXP:
2711 VISIT(c, expr, elt);
2712 ADDOP(c, YIELD_VALUE);
2713 ADDOP(c, POP_TOP);
2714 break;
2715 case COMP_SETCOMP:
2716 VISIT(c, expr, elt);
2717 ADDOP_I(c, SET_ADD, gen_index + 1);
2718 break;
2719 case COMP_DICTCOMP:
2720 /* With 'd[k] = v', v is evaluated before k, so we do
2721 the same. */
2722 VISIT(c, expr, val);
2723 VISIT(c, expr, elt);
2724 ADDOP_I(c, MAP_ADD, gen_index + 1);
2725 break;
2726 default:
2727 return 0;
2728 }
2729
2730 compiler_use_next_block(c, skip);
2731 }
2732 compiler_use_next_block(c, if_cleanup);
2733 ADDOP_JABS(c, JUMP_ABSOLUTE, start);
2734 compiler_use_next_block(c, anchor);
2735
2736 return 1;
2737 }
2738
2739 static int
compiler_comprehension(struct compiler * c,expr_ty e,int type,identifier name,asdl_seq * generators,expr_ty elt,expr_ty val)2740 compiler_comprehension(struct compiler *c, expr_ty e, int type, identifier name,
2741 asdl_seq *generators, expr_ty elt, expr_ty val)
2742 {
2743 PyCodeObject *co = NULL;
2744 expr_ty outermost_iter;
2745
2746 outermost_iter = ((comprehension_ty)
2747 asdl_seq_GET(generators, 0))->iter;
2748
2749 if (!compiler_enter_scope(c, name, (void *)e, e->lineno))
2750 goto error;
2751
2752 if (type != COMP_GENEXP) {
2753 int op;
2754 switch (type) {
2755 case COMP_SETCOMP:
2756 op = BUILD_SET;
2757 break;
2758 case COMP_DICTCOMP:
2759 op = BUILD_MAP;
2760 break;
2761 default:
2762 PyErr_Format(PyExc_SystemError,
2763 "unknown comprehension type %d", type);
2764 goto error_in_scope;
2765 }
2766
2767 ADDOP_I(c, op, 0);
2768 }
2769
2770 if (!compiler_comprehension_generator(c, generators, 0, elt,
2771 val, type))
2772 goto error_in_scope;
2773
2774 if (type != COMP_GENEXP) {
2775 ADDOP(c, RETURN_VALUE);
2776 }
2777
2778 co = assemble(c, 1);
2779 compiler_exit_scope(c);
2780 if (co == NULL)
2781 goto error;
2782
2783 if (!compiler_make_closure(c, co, 0))
2784 goto error;
2785 Py_DECREF(co);
2786
2787 VISIT(c, expr, outermost_iter);
2788 ADDOP(c, GET_ITER);
2789 ADDOP_I(c, CALL_FUNCTION, 1);
2790 return 1;
2791 error_in_scope:
2792 compiler_exit_scope(c);
2793 error:
2794 Py_XDECREF(co);
2795 return 0;
2796 }
2797
2798 static int
compiler_genexp(struct compiler * c,expr_ty e)2799 compiler_genexp(struct compiler *c, expr_ty e)
2800 {
2801 static identifier name;
2802 if (!name) {
2803 name = PyString_FromString("<genexpr>");
2804 if (!name)
2805 return 0;
2806 }
2807 assert(e->kind == GeneratorExp_kind);
2808 return compiler_comprehension(c, e, COMP_GENEXP, name,
2809 e->v.GeneratorExp.generators,
2810 e->v.GeneratorExp.elt, NULL);
2811 }
2812
2813 static int
compiler_setcomp(struct compiler * c,expr_ty e)2814 compiler_setcomp(struct compiler *c, expr_ty e)
2815 {
2816 static identifier name;
2817 if (!name) {
2818 name = PyString_FromString("<setcomp>");
2819 if (!name)
2820 return 0;
2821 }
2822 assert(e->kind == SetComp_kind);
2823 return compiler_comprehension(c, e, COMP_SETCOMP, name,
2824 e->v.SetComp.generators,
2825 e->v.SetComp.elt, NULL);
2826 }
2827
2828 static int
compiler_dictcomp(struct compiler * c,expr_ty e)2829 compiler_dictcomp(struct compiler *c, expr_ty e)
2830 {
2831 static identifier name;
2832 if (!name) {
2833 name = PyString_FromString("<dictcomp>");
2834 if (!name)
2835 return 0;
2836 }
2837 assert(e->kind == DictComp_kind);
2838 return compiler_comprehension(c, e, COMP_DICTCOMP, name,
2839 e->v.DictComp.generators,
2840 e->v.DictComp.key, e->v.DictComp.value);
2841 }
2842
2843 static int
compiler_visit_keyword(struct compiler * c,keyword_ty k)2844 compiler_visit_keyword(struct compiler *c, keyword_ty k)
2845 {
2846 ADDOP_O(c, LOAD_CONST, k->arg, consts);
2847 VISIT(c, expr, k->value);
2848 return 1;
2849 }
2850
2851 /* Test whether expression is constant. For constants, report
2852 whether they are true or false.
2853
2854 Return values: 1 for true, 0 for false, -1 for non-constant.
2855 */
2856
2857 static int
expr_constant(expr_ty e)2858 expr_constant(expr_ty e)
2859 {
2860 switch (e->kind) {
2861 case Num_kind:
2862 return PyObject_IsTrue(e->v.Num.n);
2863 case Str_kind:
2864 return PyObject_IsTrue(e->v.Str.s);
2865 case Name_kind:
2866 /* __debug__ is not assignable, so we can optimize
2867 * it away in if and while statements */
2868 if (strcmp(PyString_AS_STRING(e->v.Name.id),
2869 "__debug__") == 0)
2870 return ! Py_OptimizeFlag;
2871 /* fall through */
2872 default:
2873 return -1;
2874 }
2875 }
2876
2877 /*
2878 Implements the with statement from PEP 343.
2879
2880 The semantics outlined in that PEP are as follows:
2881
2882 with EXPR as VAR:
2883 BLOCK
2884
2885 It is implemented roughly as:
2886
2887 context = EXPR
2888 exit = context.__exit__ # not calling it
2889 value = context.__enter__()
2890 try:
2891 VAR = value # if VAR present in the syntax
2892 BLOCK
2893 finally:
2894 if an exception was raised:
2895 exc = copy of (exception, instance, traceback)
2896 else:
2897 exc = (None, None, None)
2898 exit(*exc)
2899 */
2900 static int
compiler_with(struct compiler * c,stmt_ty s)2901 compiler_with(struct compiler *c, stmt_ty s)
2902 {
2903 basicblock *block, *finally;
2904
2905 assert(s->kind == With_kind);
2906
2907 block = compiler_new_block(c);
2908 finally = compiler_new_block(c);
2909 if (!block || !finally)
2910 return 0;
2911
2912 /* Evaluate EXPR */
2913 VISIT(c, expr, s->v.With.context_expr);
2914 ADDOP_JREL(c, SETUP_WITH, finally);
2915
2916 /* SETUP_WITH pushes a finally block. */
2917 compiler_use_next_block(c, block);
2918 /* Note that the block is actually called SETUP_WITH in ceval.c, but
2919 functions the same as SETUP_FINALLY except that exceptions are
2920 normalized. */
2921 if (!compiler_push_fblock(c, FINALLY_TRY, block)) {
2922 return 0;
2923 }
2924
2925 if (s->v.With.optional_vars) {
2926 VISIT(c, expr, s->v.With.optional_vars);
2927 }
2928 else {
2929 /* Discard result from context.__enter__() */
2930 ADDOP(c, POP_TOP);
2931 }
2932
2933 /* BLOCK code */
2934 VISIT_SEQ(c, stmt, s->v.With.body);
2935
2936 /* End of try block; start the finally block */
2937 ADDOP(c, POP_BLOCK);
2938 compiler_pop_fblock(c, FINALLY_TRY, block);
2939
2940 ADDOP_O(c, LOAD_CONST, Py_None, consts);
2941 compiler_use_next_block(c, finally);
2942 if (!compiler_push_fblock(c, FINALLY_END, finally))
2943 return 0;
2944
2945 /* Finally block starts; context.__exit__ is on the stack under
2946 the exception or return information. Just issue our magic
2947 opcode. */
2948 ADDOP(c, WITH_CLEANUP);
2949
2950 /* Finally block ends. */
2951 ADDOP(c, END_FINALLY);
2952 compiler_pop_fblock(c, FINALLY_END, finally);
2953 return 1;
2954 }
2955
2956 static int
compiler_visit_expr(struct compiler * c,expr_ty e)2957 compiler_visit_expr(struct compiler *c, expr_ty e)
2958 {
2959 int i, n;
2960
2961 /* If expr e has a different line number than the last expr/stmt,
2962 set a new line number for the next instruction.
2963 */
2964 if (e->lineno > c->u->u_lineno) {
2965 c->u->u_lineno = e->lineno;
2966 c->u->u_lineno_set = false;
2967 }
2968 switch (e->kind) {
2969 case BoolOp_kind:
2970 return compiler_boolop(c, e);
2971 case BinOp_kind:
2972 VISIT(c, expr, e->v.BinOp.left);
2973 VISIT(c, expr, e->v.BinOp.right);
2974 ADDOP(c, binop(c, e->v.BinOp.op));
2975 break;
2976 case UnaryOp_kind:
2977 VISIT(c, expr, e->v.UnaryOp.operand);
2978 ADDOP(c, unaryop(e->v.UnaryOp.op));
2979 break;
2980 case Lambda_kind:
2981 return compiler_lambda(c, e);
2982 case IfExp_kind:
2983 return compiler_ifexp(c, e);
2984 case Dict_kind:
2985 n = asdl_seq_LEN(e->v.Dict.values);
2986 ADDOP_I(c, BUILD_MAP, (n>0xFFFF ? 0xFFFF : n));
2987 for (i = 0; i < n; i++) {
2988 VISIT(c, expr,
2989 (expr_ty)asdl_seq_GET(e->v.Dict.values, i));
2990 VISIT(c, expr,
2991 (expr_ty)asdl_seq_GET(e->v.Dict.keys, i));
2992 ADDOP(c, STORE_MAP);
2993 }
2994 break;
2995 case Set_kind:
2996 n = asdl_seq_LEN(e->v.Set.elts);
2997 VISIT_SEQ(c, expr, e->v.Set.elts);
2998 ADDOP_I(c, BUILD_SET, n);
2999 break;
3000 case ListComp_kind:
3001 return compiler_listcomp(c, e);
3002 case SetComp_kind:
3003 return compiler_setcomp(c, e);
3004 case DictComp_kind:
3005 return compiler_dictcomp(c, e);
3006 case GeneratorExp_kind:
3007 return compiler_genexp(c, e);
3008 case Yield_kind:
3009 if (c->u->u_ste->ste_type != FunctionBlock)
3010 return compiler_error(c, "'yield' outside function");
3011 if (e->v.Yield.value) {
3012 VISIT(c, expr, e->v.Yield.value);
3013 }
3014 else {
3015 ADDOP_O(c, LOAD_CONST, Py_None, consts);
3016 }
3017 ADDOP(c, YIELD_VALUE);
3018 break;
3019 case Compare_kind:
3020 return compiler_compare(c, e);
3021 case Call_kind:
3022 return compiler_call(c, e);
3023 case Repr_kind:
3024 VISIT(c, expr, e->v.Repr.value);
3025 ADDOP(c, UNARY_CONVERT);
3026 break;
3027 case Num_kind:
3028 ADDOP_O(c, LOAD_CONST, e->v.Num.n, consts);
3029 break;
3030 case Str_kind:
3031 ADDOP_O(c, LOAD_CONST, e->v.Str.s, consts);
3032 break;
3033 /* The following exprs can be assignment targets. */
3034 case Attribute_kind:
3035 if (e->v.Attribute.ctx != AugStore)
3036 VISIT(c, expr, e->v.Attribute.value);
3037 switch (e->v.Attribute.ctx) {
3038 case AugLoad:
3039 ADDOP(c, DUP_TOP);
3040 /* Fall through to load */
3041 case Load:
3042 ADDOP_NAME(c, LOAD_ATTR, e->v.Attribute.attr, names);
3043 break;
3044 case AugStore:
3045 ADDOP(c, ROT_TWO);
3046 /* Fall through to save */
3047 case Store:
3048 ADDOP_NAME(c, STORE_ATTR, e->v.Attribute.attr, names);
3049 break;
3050 case Del:
3051 ADDOP_NAME(c, DELETE_ATTR, e->v.Attribute.attr, names);
3052 break;
3053 case Param:
3054 default:
3055 PyErr_SetString(PyExc_SystemError,
3056 "param invalid in attribute expression");
3057 return 0;
3058 }
3059 break;
3060 case Subscript_kind:
3061 switch (e->v.Subscript.ctx) {
3062 case AugLoad:
3063 VISIT(c, expr, e->v.Subscript.value);
3064 VISIT_SLICE(c, e->v.Subscript.slice, AugLoad);
3065 break;
3066 case Load:
3067 VISIT(c, expr, e->v.Subscript.value);
3068 VISIT_SLICE(c, e->v.Subscript.slice, Load);
3069 break;
3070 case AugStore:
3071 VISIT_SLICE(c, e->v.Subscript.slice, AugStore);
3072 break;
3073 case Store:
3074 VISIT(c, expr, e->v.Subscript.value);
3075 VISIT_SLICE(c, e->v.Subscript.slice, Store);
3076 break;
3077 case Del:
3078 VISIT(c, expr, e->v.Subscript.value);
3079 VISIT_SLICE(c, e->v.Subscript.slice, Del);
3080 break;
3081 case Param:
3082 default:
3083 PyErr_SetString(PyExc_SystemError,
3084 "param invalid in subscript expression");
3085 return 0;
3086 }
3087 break;
3088 case Name_kind:
3089 return compiler_nameop(c, e->v.Name.id, e->v.Name.ctx);
3090 /* child nodes of List and Tuple will have expr_context set */
3091 case List_kind:
3092 return compiler_list(c, e);
3093 case Tuple_kind:
3094 return compiler_tuple(c, e);
3095 }
3096 return 1;
3097 }
3098
3099 static int
compiler_augassign(struct compiler * c,stmt_ty s)3100 compiler_augassign(struct compiler *c, stmt_ty s)
3101 {
3102 expr_ty e = s->v.AugAssign.target;
3103 expr_ty auge;
3104
3105 assert(s->kind == AugAssign_kind);
3106
3107 switch (e->kind) {
3108 case Attribute_kind:
3109 auge = Attribute(e->v.Attribute.value, e->v.Attribute.attr,
3110 AugLoad, e->lineno, e->col_offset, c->c_arena);
3111 if (auge == NULL)
3112 return 0;
3113 VISIT(c, expr, auge);
3114 VISIT(c, expr, s->v.AugAssign.value);
3115 ADDOP(c, inplace_binop(c, s->v.AugAssign.op));
3116 auge->v.Attribute.ctx = AugStore;
3117 VISIT(c, expr, auge);
3118 break;
3119 case Subscript_kind:
3120 auge = Subscript(e->v.Subscript.value, e->v.Subscript.slice,
3121 AugLoad, e->lineno, e->col_offset, c->c_arena);
3122 if (auge == NULL)
3123 return 0;
3124 VISIT(c, expr, auge);
3125 VISIT(c, expr, s->v.AugAssign.value);
3126 ADDOP(c, inplace_binop(c, s->v.AugAssign.op));
3127 auge->v.Subscript.ctx = AugStore;
3128 VISIT(c, expr, auge);
3129 break;
3130 case Name_kind:
3131 if (!compiler_nameop(c, e->v.Name.id, Load))
3132 return 0;
3133 VISIT(c, expr, s->v.AugAssign.value);
3134 ADDOP(c, inplace_binop(c, s->v.AugAssign.op));
3135 return compiler_nameop(c, e->v.Name.id, Store);
3136 default:
3137 PyErr_Format(PyExc_SystemError,
3138 "invalid node type (%d) for augmented assignment",
3139 e->kind);
3140 return 0;
3141 }
3142 return 1;
3143 }
3144
3145 static int
compiler_push_fblock(struct compiler * c,enum fblocktype t,basicblock * b)3146 compiler_push_fblock(struct compiler *c, enum fblocktype t, basicblock *b)
3147 {
3148 struct fblockinfo *f;
3149 if (c->u->u_nfblocks >= CO_MAXBLOCKS) {
3150 PyErr_SetString(PyExc_SyntaxError,
3151 "too many statically nested blocks");
3152 return 0;
3153 }
3154 f = &c->u->u_fblock[c->u->u_nfblocks++];
3155 f->fb_type = t;
3156 f->fb_block = b;
3157 return 1;
3158 }
3159
3160 static void
compiler_pop_fblock(struct compiler * c,enum fblocktype t,basicblock * b)3161 compiler_pop_fblock(struct compiler *c, enum fblocktype t, basicblock *b)
3162 {
3163 struct compiler_unit *u = c->u;
3164 assert(u->u_nfblocks > 0);
3165 u->u_nfblocks--;
3166 assert(u->u_fblock[u->u_nfblocks].fb_type == t);
3167 assert(u->u_fblock[u->u_nfblocks].fb_block == b);
3168 }
3169
3170 static int
compiler_in_loop(struct compiler * c)3171 compiler_in_loop(struct compiler *c) {
3172 int i;
3173 struct compiler_unit *u = c->u;
3174 for (i = 0; i < u->u_nfblocks; ++i) {
3175 if (u->u_fblock[i].fb_type == LOOP)
3176 return 1;
3177 }
3178 return 0;
3179 }
3180 /* Raises a SyntaxError and returns 0.
3181 If something goes wrong, a different exception may be raised.
3182 */
3183
3184 static int
compiler_error(struct compiler * c,const char * errstr)3185 compiler_error(struct compiler *c, const char *errstr)
3186 {
3187 PyObject *loc;
3188 PyObject *u = NULL, *v = NULL;
3189
3190 loc = PyErr_ProgramText(c->c_filename, c->u->u_lineno);
3191 if (!loc) {
3192 Py_INCREF(Py_None);
3193 loc = Py_None;
3194 }
3195 u = Py_BuildValue("(ziOO)", c->c_filename, c->u->u_lineno,
3196 Py_None, loc);
3197 if (!u)
3198 goto exit;
3199 v = Py_BuildValue("(zO)", errstr, u);
3200 if (!v)
3201 goto exit;
3202 PyErr_SetObject(PyExc_SyntaxError, v);
3203 exit:
3204 Py_DECREF(loc);
3205 Py_XDECREF(u);
3206 Py_XDECREF(v);
3207 return 0;
3208 }
3209
3210 static int
compiler_handle_subscr(struct compiler * c,const char * kind,expr_context_ty ctx)3211 compiler_handle_subscr(struct compiler *c, const char *kind,
3212 expr_context_ty ctx)
3213 {
3214 int op = 0;
3215
3216 /* XXX this code is duplicated */
3217 switch (ctx) {
3218 case AugLoad: /* fall through to Load */
3219 case Load: op = BINARY_SUBSCR; break;
3220 case AugStore:/* fall through to Store */
3221 case Store: op = STORE_SUBSCR; break;
3222 case Del: op = DELETE_SUBSCR; break;
3223 case Param:
3224 PyErr_Format(PyExc_SystemError,
3225 "invalid %s kind %d in subscript\n",
3226 kind, ctx);
3227 return 0;
3228 }
3229 if (ctx == AugLoad) {
3230 ADDOP_I(c, DUP_TOPX, 2);
3231 }
3232 else if (ctx == AugStore) {
3233 ADDOP(c, ROT_THREE);
3234 }
3235 ADDOP(c, op);
3236 return 1;
3237 }
3238
3239 static int
compiler_slice(struct compiler * c,slice_ty s,expr_context_ty ctx)3240 compiler_slice(struct compiler *c, slice_ty s, expr_context_ty ctx)
3241 {
3242 int n = 2;
3243 assert(s->kind == Slice_kind);
3244
3245 /* only handles the cases where BUILD_SLICE is emitted */
3246 if (s->v.Slice.lower) {
3247 VISIT(c, expr, s->v.Slice.lower);
3248 }
3249 else {
3250 ADDOP_O(c, LOAD_CONST, Py_None, consts);
3251 }
3252
3253 if (s->v.Slice.upper) {
3254 VISIT(c, expr, s->v.Slice.upper);
3255 }
3256 else {
3257 ADDOP_O(c, LOAD_CONST, Py_None, consts);
3258 }
3259
3260 if (s->v.Slice.step) {
3261 n++;
3262 VISIT(c, expr, s->v.Slice.step);
3263 }
3264 ADDOP_I(c, BUILD_SLICE, n);
3265 return 1;
3266 }
3267
3268 static int
compiler_simple_slice(struct compiler * c,slice_ty s,expr_context_ty ctx)3269 compiler_simple_slice(struct compiler *c, slice_ty s, expr_context_ty ctx)
3270 {
3271 int op = 0, slice_offset = 0, stack_count = 0;
3272
3273 assert(s->v.Slice.step == NULL);
3274 if (s->v.Slice.lower) {
3275 slice_offset++;
3276 stack_count++;
3277 if (ctx != AugStore)
3278 VISIT(c, expr, s->v.Slice.lower);
3279 }
3280 if (s->v.Slice.upper) {
3281 slice_offset += 2;
3282 stack_count++;
3283 if (ctx != AugStore)
3284 VISIT(c, expr, s->v.Slice.upper);
3285 }
3286
3287 if (ctx == AugLoad) {
3288 switch (stack_count) {
3289 case 0: ADDOP(c, DUP_TOP); break;
3290 case 1: ADDOP_I(c, DUP_TOPX, 2); break;
3291 case 2: ADDOP_I(c, DUP_TOPX, 3); break;
3292 }
3293 }
3294 else if (ctx == AugStore) {
3295 switch (stack_count) {
3296 case 0: ADDOP(c, ROT_TWO); break;
3297 case 1: ADDOP(c, ROT_THREE); break;
3298 case 2: ADDOP(c, ROT_FOUR); break;
3299 }
3300 }
3301
3302 switch (ctx) {
3303 case AugLoad: /* fall through to Load */
3304 case Load: op = SLICE; break;
3305 case AugStore:/* fall through to Store */
3306 case Store: op = STORE_SLICE; break;
3307 case Del: op = DELETE_SLICE; break;
3308 case Param:
3309 default:
3310 PyErr_SetString(PyExc_SystemError,
3311 "param invalid in simple slice");
3312 return 0;
3313 }
3314
3315 ADDOP(c, op + slice_offset);
3316 return 1;
3317 }
3318
3319 static int
compiler_visit_nested_slice(struct compiler * c,slice_ty s,expr_context_ty ctx)3320 compiler_visit_nested_slice(struct compiler *c, slice_ty s,
3321 expr_context_ty ctx)
3322 {
3323 switch (s->kind) {
3324 case Ellipsis_kind:
3325 ADDOP_O(c, LOAD_CONST, Py_Ellipsis, consts);
3326 break;
3327 case Slice_kind:
3328 return compiler_slice(c, s, ctx);
3329 case Index_kind:
3330 VISIT(c, expr, s->v.Index.value);
3331 break;
3332 case ExtSlice_kind:
3333 default:
3334 PyErr_SetString(PyExc_SystemError,
3335 "extended slice invalid in nested slice");
3336 return 0;
3337 }
3338 return 1;
3339 }
3340
3341 static int
compiler_visit_slice(struct compiler * c,slice_ty s,expr_context_ty ctx)3342 compiler_visit_slice(struct compiler *c, slice_ty s, expr_context_ty ctx)
3343 {
3344 char * kindname = NULL;
3345 switch (s->kind) {
3346 case Index_kind:
3347 kindname = "index";
3348 if (ctx != AugStore) {
3349 VISIT(c, expr, s->v.Index.value);
3350 }
3351 break;
3352 case Ellipsis_kind:
3353 kindname = "ellipsis";
3354 if (ctx != AugStore) {
3355 ADDOP_O(c, LOAD_CONST, Py_Ellipsis, consts);
3356 }
3357 break;
3358 case Slice_kind:
3359 kindname = "slice";
3360 if (!s->v.Slice.step)
3361 return compiler_simple_slice(c, s, ctx);
3362 if (ctx != AugStore) {
3363 if (!compiler_slice(c, s, ctx))
3364 return 0;
3365 }
3366 break;
3367 case ExtSlice_kind:
3368 kindname = "extended slice";
3369 if (ctx != AugStore) {
3370 int i, n = asdl_seq_LEN(s->v.ExtSlice.dims);
3371 for (i = 0; i < n; i++) {
3372 slice_ty sub = (slice_ty)asdl_seq_GET(
3373 s->v.ExtSlice.dims, i);
3374 if (!compiler_visit_nested_slice(c, sub, ctx))
3375 return 0;
3376 }
3377 ADDOP_I(c, BUILD_TUPLE, n);
3378 }
3379 break;
3380 default:
3381 PyErr_Format(PyExc_SystemError,
3382 "invalid subscript kind %d", s->kind);
3383 return 0;
3384 }
3385 return compiler_handle_subscr(c, kindname, ctx);
3386 }
3387
3388
3389 /* End of the compiler section, beginning of the assembler section */
3390
3391 /* do depth-first search of basic block graph, starting with block.
3392 post records the block indices in post-order.
3393
3394 XXX must handle implicit jumps from one block to next
3395 */
3396
3397 struct assembler {
3398 PyObject *a_bytecode; /* string containing bytecode */
3399 int a_offset; /* offset into bytecode */
3400 int a_nblocks; /* number of reachable blocks */
3401 basicblock **a_postorder; /* list of blocks in dfs postorder */
3402 PyObject *a_lnotab; /* string containing lnotab */
3403 int a_lnotab_off; /* offset into lnotab */
3404 int a_lineno; /* last lineno of emitted instruction */
3405 int a_lineno_off; /* bytecode offset of last lineno */
3406 };
3407
3408 static void
dfs(struct compiler * c,basicblock * b,struct assembler * a)3409 dfs(struct compiler *c, basicblock *b, struct assembler *a)
3410 {
3411 int i;
3412 struct instr *instr = NULL;
3413
3414 if (b->b_seen)
3415 return;
3416 b->b_seen = 1;
3417 if (b->b_next != NULL)
3418 dfs(c, b->b_next, a);
3419 for (i = 0; i < b->b_iused; i++) {
3420 instr = &b->b_instr[i];
3421 if (instr->i_jrel || instr->i_jabs)
3422 dfs(c, instr->i_target, a);
3423 }
3424 a->a_postorder[a->a_nblocks++] = b;
3425 }
3426
3427 static int
stackdepth_walk(struct compiler * c,basicblock * b,int depth,int maxdepth)3428 stackdepth_walk(struct compiler *c, basicblock *b, int depth, int maxdepth)
3429 {
3430 int i, target_depth;
3431 struct instr *instr;
3432 if (b->b_seen || b->b_startdepth >= depth)
3433 return maxdepth;
3434 b->b_seen = 1;
3435 b->b_startdepth = depth;
3436 for (i = 0; i < b->b_iused; i++) {
3437 instr = &b->b_instr[i];
3438 depth += opcode_stack_effect(instr->i_opcode, instr->i_oparg);
3439 if (depth > maxdepth)
3440 maxdepth = depth;
3441 assert(depth >= 0); /* invalid code or bug in stackdepth() */
3442 if (instr->i_jrel || instr->i_jabs) {
3443 target_depth = depth;
3444 if (instr->i_opcode == FOR_ITER) {
3445 target_depth = depth-2;
3446 }
3447 else if (instr->i_opcode == SETUP_FINALLY ||
3448 instr->i_opcode == SETUP_EXCEPT) {
3449 target_depth = depth+3;
3450 if (target_depth > maxdepth)
3451 maxdepth = target_depth;
3452 }
3453 else if (instr->i_opcode == JUMP_IF_TRUE_OR_POP ||
3454 instr->i_opcode == JUMP_IF_FALSE_OR_POP)
3455 depth = depth - 1;
3456 maxdepth = stackdepth_walk(c, instr->i_target,
3457 target_depth, maxdepth);
3458 if (instr->i_opcode == JUMP_ABSOLUTE ||
3459 instr->i_opcode == JUMP_FORWARD) {
3460 goto out; /* remaining code is dead */
3461 }
3462 }
3463 }
3464 if (b->b_next)
3465 maxdepth = stackdepth_walk(c, b->b_next, depth, maxdepth);
3466 out:
3467 b->b_seen = 0;
3468 return maxdepth;
3469 }
3470
3471 /* Find the flow path that needs the largest stack. We assume that
3472 * cycles in the flow graph have no net effect on the stack depth.
3473 */
3474 static int
stackdepth(struct compiler * c)3475 stackdepth(struct compiler *c)
3476 {
3477 basicblock *b, *entryblock;
3478 entryblock = NULL;
3479 for (b = c->u->u_blocks; b != NULL; b = b->b_list) {
3480 b->b_seen = 0;
3481 b->b_startdepth = INT_MIN;
3482 entryblock = b;
3483 }
3484 if (!entryblock)
3485 return 0;
3486 return stackdepth_walk(c, entryblock, 0, 0);
3487 }
3488
3489 static int
assemble_init(struct assembler * a,int nblocks,int firstlineno)3490 assemble_init(struct assembler *a, int nblocks, int firstlineno)
3491 {
3492 memset(a, 0, sizeof(struct assembler));
3493 a->a_lineno = firstlineno;
3494 a->a_bytecode = PyString_FromStringAndSize(NULL, DEFAULT_CODE_SIZE);
3495 if (!a->a_bytecode)
3496 return 0;
3497 a->a_lnotab = PyString_FromStringAndSize(NULL, DEFAULT_LNOTAB_SIZE);
3498 if (!a->a_lnotab)
3499 return 0;
3500 if (nblocks > PY_SIZE_MAX / sizeof(basicblock *)) {
3501 PyErr_NoMemory();
3502 return 0;
3503 }
3504 a->a_postorder = (basicblock **)PyObject_Malloc(
3505 sizeof(basicblock *) * nblocks);
3506 if (!a->a_postorder) {
3507 PyErr_NoMemory();
3508 return 0;
3509 }
3510 return 1;
3511 }
3512
3513 static void
assemble_free(struct assembler * a)3514 assemble_free(struct assembler *a)
3515 {
3516 Py_XDECREF(a->a_bytecode);
3517 Py_XDECREF(a->a_lnotab);
3518 if (a->a_postorder)
3519 PyObject_Free(a->a_postorder);
3520 }
3521
3522 /* Return the size of a basic block in bytes. */
3523
3524 static int
instrsize(struct instr * instr)3525 instrsize(struct instr *instr)
3526 {
3527 if (!instr->i_hasarg)
3528 return 1; /* 1 byte for the opcode*/
3529 if (instr->i_oparg > 0xffff)
3530 return 6; /* 1 (opcode) + 1 (EXTENDED_ARG opcode) + 2 (oparg) + 2(oparg extended) */
3531 return 3; /* 1 (opcode) + 2 (oparg) */
3532 }
3533
3534 static int
blocksize(basicblock * b)3535 blocksize(basicblock *b)
3536 {
3537 int i;
3538 int size = 0;
3539
3540 for (i = 0; i < b->b_iused; i++)
3541 size += instrsize(&b->b_instr[i]);
3542 return size;
3543 }
3544
3545 /* Appends a pair to the end of the line number table, a_lnotab, representing
3546 the instruction's bytecode offset and line number. See
3547 Objects/lnotab_notes.txt for the description of the line number table. */
3548
3549 static int
assemble_lnotab(struct assembler * a,struct instr * i)3550 assemble_lnotab(struct assembler *a, struct instr *i)
3551 {
3552 int d_bytecode, d_lineno;
3553 int len;
3554 unsigned char *lnotab;
3555
3556 d_bytecode = a->a_offset - a->a_lineno_off;
3557 d_lineno = i->i_lineno - a->a_lineno;
3558
3559 assert(d_bytecode >= 0);
3560 assert(d_lineno >= 0);
3561
3562 if(d_bytecode == 0 && d_lineno == 0)
3563 return 1;
3564
3565 if (d_bytecode > 255) {
3566 int j, nbytes, ncodes = d_bytecode / 255;
3567 nbytes = a->a_lnotab_off + 2 * ncodes;
3568 len = PyString_GET_SIZE(a->a_lnotab);
3569 if (nbytes >= len) {
3570 if ((len <= INT_MAX / 2) && (len * 2 < nbytes))
3571 len = nbytes;
3572 else if (len <= INT_MAX / 2)
3573 len *= 2;
3574 else {
3575 PyErr_NoMemory();
3576 return 0;
3577 }
3578 if (_PyString_Resize(&a->a_lnotab, len) < 0)
3579 return 0;
3580 }
3581 lnotab = (unsigned char *)
3582 PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
3583 for (j = 0; j < ncodes; j++) {
3584 *lnotab++ = 255;
3585 *lnotab++ = 0;
3586 }
3587 d_bytecode -= ncodes * 255;
3588 a->a_lnotab_off += ncodes * 2;
3589 }
3590 assert(d_bytecode <= 255);
3591 if (d_lineno > 255) {
3592 int j, nbytes, ncodes = d_lineno / 255;
3593 nbytes = a->a_lnotab_off + 2 * ncodes;
3594 len = PyString_GET_SIZE(a->a_lnotab);
3595 if (nbytes >= len) {
3596 if ((len <= INT_MAX / 2) && len * 2 < nbytes)
3597 len = nbytes;
3598 else if (len <= INT_MAX / 2)
3599 len *= 2;
3600 else {
3601 PyErr_NoMemory();
3602 return 0;
3603 }
3604 if (_PyString_Resize(&a->a_lnotab, len) < 0)
3605 return 0;
3606 }
3607 lnotab = (unsigned char *)
3608 PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
3609 *lnotab++ = d_bytecode;
3610 *lnotab++ = 255;
3611 d_bytecode = 0;
3612 for (j = 1; j < ncodes; j++) {
3613 *lnotab++ = 0;
3614 *lnotab++ = 255;
3615 }
3616 d_lineno -= ncodes * 255;
3617 a->a_lnotab_off += ncodes * 2;
3618 }
3619
3620 len = PyString_GET_SIZE(a->a_lnotab);
3621 if (a->a_lnotab_off + 2 >= len) {
3622 if (_PyString_Resize(&a->a_lnotab, len * 2) < 0)
3623 return 0;
3624 }
3625 lnotab = (unsigned char *)
3626 PyString_AS_STRING(a->a_lnotab) + a->a_lnotab_off;
3627
3628 a->a_lnotab_off += 2;
3629 if (d_bytecode) {
3630 *lnotab++ = d_bytecode;
3631 *lnotab++ = d_lineno;
3632 }
3633 else { /* First line of a block; def stmt, etc. */
3634 *lnotab++ = 0;
3635 *lnotab++ = d_lineno;
3636 }
3637 a->a_lineno = i->i_lineno;
3638 a->a_lineno_off = a->a_offset;
3639 return 1;
3640 }
3641
3642 /* assemble_emit()
3643 Extend the bytecode with a new instruction.
3644 Update lnotab if necessary.
3645 */
3646
3647 static int
assemble_emit(struct assembler * a,struct instr * i)3648 assemble_emit(struct assembler *a, struct instr *i)
3649 {
3650 int size, arg = 0, ext = 0;
3651 Py_ssize_t len = PyString_GET_SIZE(a->a_bytecode);
3652 char *code;
3653
3654 size = instrsize(i);
3655 if (i->i_hasarg) {
3656 arg = i->i_oparg;
3657 ext = arg >> 16;
3658 }
3659 if (i->i_lineno && !assemble_lnotab(a, i))
3660 return 0;
3661 if (a->a_offset + size >= len) {
3662 if (len > PY_SSIZE_T_MAX / 2)
3663 return 0;
3664 if (_PyString_Resize(&a->a_bytecode, len * 2) < 0)
3665 return 0;
3666 }
3667 code = PyString_AS_STRING(a->a_bytecode) + a->a_offset;
3668 a->a_offset += size;
3669 if (size == 6) {
3670 assert(i->i_hasarg);
3671 *code++ = (char)EXTENDED_ARG;
3672 *code++ = ext & 0xff;
3673 *code++ = ext >> 8;
3674 arg &= 0xffff;
3675 }
3676 *code++ = i->i_opcode;
3677 if (i->i_hasarg) {
3678 assert(size == 3 || size == 6);
3679 *code++ = arg & 0xff;
3680 *code++ = arg >> 8;
3681 }
3682 return 1;
3683 }
3684
3685 static void
assemble_jump_offsets(struct assembler * a,struct compiler * c)3686 assemble_jump_offsets(struct assembler *a, struct compiler *c)
3687 {
3688 basicblock *b;
3689 int bsize, totsize, extended_arg_count = 0, last_extended_arg_count;
3690 int i;
3691
3692 /* Compute the size of each block and fixup jump args.
3693 Replace block pointer with position in bytecode. */
3694 do {
3695 totsize = 0;
3696 for (i = a->a_nblocks - 1; i >= 0; i--) {
3697 b = a->a_postorder[i];
3698 bsize = blocksize(b);
3699 b->b_offset = totsize;
3700 totsize += bsize;
3701 }
3702 last_extended_arg_count = extended_arg_count;
3703 extended_arg_count = 0;
3704 for (b = c->u->u_blocks; b != NULL; b = b->b_list) {
3705 bsize = b->b_offset;
3706 for (i = 0; i < b->b_iused; i++) {
3707 struct instr *instr = &b->b_instr[i];
3708 /* Relative jumps are computed relative to
3709 the instruction pointer after fetching
3710 the jump instruction.
3711 */
3712 bsize += instrsize(instr);
3713 if (instr->i_jabs)
3714 instr->i_oparg = instr->i_target->b_offset;
3715 else if (instr->i_jrel) {
3716 int delta = instr->i_target->b_offset - bsize;
3717 instr->i_oparg = delta;
3718 }
3719 else
3720 continue;
3721 if (instr->i_oparg > 0xffff)
3722 extended_arg_count++;
3723 }
3724 }
3725
3726 /* XXX: This is an awful hack that could hurt performance, but
3727 on the bright side it should work until we come up
3728 with a better solution.
3729
3730 The issue is that in the first loop blocksize() is called
3731 which calls instrsize() which requires i_oparg be set
3732 appropriately. There is a bootstrap problem because
3733 i_oparg is calculated in the second loop above.
3734
3735 So we loop until we stop seeing new EXTENDED_ARGs.
3736 The only EXTENDED_ARGs that could be popping up are
3737 ones in jump instructions. So this should converge
3738 fairly quickly.
3739 */
3740 } while (last_extended_arg_count != extended_arg_count);
3741 }
3742
3743 static PyObject *
dict_keys_inorder(PyObject * dict,int offset)3744 dict_keys_inorder(PyObject *dict, int offset)
3745 {
3746 PyObject *tuple, *k, *v;
3747 Py_ssize_t i, pos = 0, size = PyDict_Size(dict);
3748
3749 tuple = PyTuple_New(size);
3750 if (tuple == NULL)
3751 return NULL;
3752 while (PyDict_Next(dict, &pos, &k, &v)) {
3753 i = PyInt_AS_LONG(v);
3754 /* The keys of the dictionary are tuples. (see compiler_add_o)
3755 The object we want is always first, though. */
3756 k = PyTuple_GET_ITEM(k, 1);
3757 Py_INCREF(k);
3758 assert((i - offset) < size);
3759 assert((i - offset) >= 0);
3760 PyTuple_SET_ITEM(tuple, i - offset, k);
3761 }
3762 return tuple;
3763 }
3764
3765 static int
compute_code_flags(struct compiler * c)3766 compute_code_flags(struct compiler *c)
3767 {
3768 PySTEntryObject *ste = c->u->u_ste;
3769 int flags = 0, n;
3770 if (ste->ste_type != ModuleBlock)
3771 flags |= CO_NEWLOCALS;
3772 if (ste->ste_type == FunctionBlock) {
3773 if (!ste->ste_unoptimized)
3774 flags |= CO_OPTIMIZED;
3775 if (ste->ste_nested)
3776 flags |= CO_NESTED;
3777 if (ste->ste_generator)
3778 flags |= CO_GENERATOR;
3779 if (ste->ste_varargs)
3780 flags |= CO_VARARGS;
3781 if (ste->ste_varkeywords)
3782 flags |= CO_VARKEYWORDS;
3783 }
3784
3785 /* (Only) inherit compilerflags in PyCF_MASK */
3786 flags |= (c->c_flags->cf_flags & PyCF_MASK);
3787
3788 n = PyDict_Size(c->u->u_freevars);
3789 if (n < 0)
3790 return -1;
3791 if (n == 0) {
3792 n = PyDict_Size(c->u->u_cellvars);
3793 if (n < 0)
3794 return -1;
3795 if (n == 0) {
3796 flags |= CO_NOFREE;
3797 }
3798 }
3799
3800 return flags;
3801 }
3802
3803 static PyCodeObject *
makecode(struct compiler * c,struct assembler * a)3804 makecode(struct compiler *c, struct assembler *a)
3805 {
3806 PyObject *tmp;
3807 PyCodeObject *co = NULL;
3808 PyObject *consts = NULL;
3809 PyObject *names = NULL;
3810 PyObject *varnames = NULL;
3811 PyObject *filename = NULL;
3812 PyObject *name = NULL;
3813 PyObject *freevars = NULL;
3814 PyObject *cellvars = NULL;
3815 PyObject *bytecode = NULL;
3816 int nlocals, flags;
3817
3818 tmp = dict_keys_inorder(c->u->u_consts, 0);
3819 if (!tmp)
3820 goto error;
3821 consts = PySequence_List(tmp); /* optimize_code requires a list */
3822 Py_DECREF(tmp);
3823
3824 names = dict_keys_inorder(c->u->u_names, 0);
3825 varnames = dict_keys_inorder(c->u->u_varnames, 0);
3826 if (!consts || !names || !varnames)
3827 goto error;
3828
3829 cellvars = dict_keys_inorder(c->u->u_cellvars, 0);
3830 if (!cellvars)
3831 goto error;
3832 freevars = dict_keys_inorder(c->u->u_freevars, PyTuple_Size(cellvars));
3833 if (!freevars)
3834 goto error;
3835 filename = PyString_FromString(c->c_filename);
3836 if (!filename)
3837 goto error;
3838
3839 nlocals = PyDict_Size(c->u->u_varnames);
3840 flags = compute_code_flags(c);
3841 if (flags < 0)
3842 goto error;
3843
3844 bytecode = PyCode_Optimize(a->a_bytecode, consts, names, a->a_lnotab);
3845 if (!bytecode)
3846 goto error;
3847
3848 tmp = PyList_AsTuple(consts); /* PyCode_New requires a tuple */
3849 if (!tmp)
3850 goto error;
3851 Py_DECREF(consts);
3852 consts = tmp;
3853
3854 co = PyCode_New(c->u->u_argcount, nlocals, stackdepth(c), flags,
3855 bytecode, consts, names, varnames,
3856 freevars, cellvars,
3857 filename, c->u->u_name,
3858 c->u->u_firstlineno,
3859 a->a_lnotab);
3860 error:
3861 Py_XDECREF(consts);
3862 Py_XDECREF(names);
3863 Py_XDECREF(varnames);
3864 Py_XDECREF(filename);
3865 Py_XDECREF(name);
3866 Py_XDECREF(freevars);
3867 Py_XDECREF(cellvars);
3868 Py_XDECREF(bytecode);
3869 return co;
3870 }
3871
3872
3873 /* For debugging purposes only */
3874 #if 0
3875 static void
3876 dump_instr(const struct instr *i)
3877 {
3878 const char *jrel = i->i_jrel ? "jrel " : "";
3879 const char *jabs = i->i_jabs ? "jabs " : "";
3880 char arg[128];
3881
3882 *arg = '\0';
3883 if (i->i_hasarg)
3884 sprintf(arg, "arg: %d ", i->i_oparg);
3885
3886 fprintf(stderr, "line: %d, opcode: %d %s%s%s\n",
3887 i->i_lineno, i->i_opcode, arg, jabs, jrel);
3888 }
3889
3890 static void
3891 dump_basicblock(const basicblock *b)
3892 {
3893 const char *seen = b->b_seen ? "seen " : "";
3894 const char *b_return = b->b_return ? "return " : "";
3895 fprintf(stderr, "used: %d, depth: %d, offset: %d %s%s\n",
3896 b->b_iused, b->b_startdepth, b->b_offset, seen, b_return);
3897 if (b->b_instr) {
3898 int i;
3899 for (i = 0; i < b->b_iused; i++) {
3900 fprintf(stderr, " [%02d] ", i);
3901 dump_instr(b->b_instr + i);
3902 }
3903 }
3904 }
3905 #endif
3906
3907 static PyCodeObject *
assemble(struct compiler * c,int addNone)3908 assemble(struct compiler *c, int addNone)
3909 {
3910 basicblock *b, *entryblock;
3911 struct assembler a;
3912 int i, j, nblocks;
3913 PyCodeObject *co = NULL;
3914
3915 /* Make sure every block that falls off the end returns None.
3916 XXX NEXT_BLOCK() isn't quite right, because if the last
3917 block ends with a jump or return b_next shouldn't set.
3918 */
3919 if (!c->u->u_curblock->b_return) {
3920 NEXT_BLOCK(c);
3921 if (addNone)
3922 ADDOP_O(c, LOAD_CONST, Py_None, consts);
3923 ADDOP(c, RETURN_VALUE);
3924 }
3925
3926 nblocks = 0;
3927 entryblock = NULL;
3928 for (b = c->u->u_blocks; b != NULL; b = b->b_list) {
3929 nblocks++;
3930 entryblock = b;
3931 }
3932
3933 /* Set firstlineno if it wasn't explicitly set. */
3934 if (!c->u->u_firstlineno) {
3935 if (entryblock && entryblock->b_instr)
3936 c->u->u_firstlineno = entryblock->b_instr->i_lineno;
3937 else
3938 c->u->u_firstlineno = 1;
3939 }
3940 if (!assemble_init(&a, nblocks, c->u->u_firstlineno))
3941 goto error;
3942 dfs(c, entryblock, &a);
3943
3944 /* Can't modify the bytecode after computing jump offsets. */
3945 assemble_jump_offsets(&a, c);
3946
3947 /* Emit code in reverse postorder from dfs. */
3948 for (i = a.a_nblocks - 1; i >= 0; i--) {
3949 b = a.a_postorder[i];
3950 for (j = 0; j < b->b_iused; j++)
3951 if (!assemble_emit(&a, &b->b_instr[j]))
3952 goto error;
3953 }
3954
3955 if (_PyString_Resize(&a.a_lnotab, a.a_lnotab_off) < 0)
3956 goto error;
3957 if (_PyString_Resize(&a.a_bytecode, a.a_offset) < 0)
3958 goto error;
3959
3960 co = makecode(c, &a);
3961 error:
3962 assemble_free(&a);
3963 return co;
3964 }
3965