Python/ast.c

   1 /*
   2  * This file includes functions to transform a concrete syntax tree (CST) to
   3  * an abstract syntax tree (AST).  The main function is PyAST_FromNode().
   4  *
   5  */
   6 #include "Python.h"
   7 #include "Python-ast.h"
   8 #include "grammar.h"
   9 #include "node.h"
  10 #include "pyarena.h"
  11 #include "ast.h"
  12 #include "token.h"
  13 #include "parsetok.h"
  14 #include "graminit.h"
  15
  16 #include <assert.h>
  17
  18 /* Data structure used internally */
  19 struct compiling {
  20     char *c_encoding; /* source encoding */
  21     PyArena *c_arena; /* arena for allocating memeory */
  22     const char *c_filename; /* filename */
  23 };
  24
  25 static asdl_seq *seq_for_testlist(struct compiling *, const node *);
  26 static expr_ty ast_for_expr(struct compiling *, const node *);
  27 static stmt_ty ast_for_stmt(struct compiling *, const node *);
  28 static asdl_seq *ast_for_suite(struct compiling *, const node *);
  29 static asdl_seq *ast_for_exprlist(struct compiling *, const node *,
  30                                   expr_context_ty);
  31 static expr_ty ast_for_testlist(struct compiling *, const node *);
  32 static expr_ty ast_for_testlist_gexp(struct compiling *, const node *);
  33
  34 /* Note different signature for ast_for_call */
  35 static expr_ty ast_for_call(struct compiling *, const node *, expr_ty);
  36
  37 static PyObject *parsenumber(const char *);
  38 static PyObject *parsestr(const char *s, const char *encoding);
  39 static PyObject *parsestrplus(struct compiling *, const node *n);
  40
  41 #ifndef LINENO
  42 #define LINENO(n)       ((n)->n_lineno)
  43 #endif
  44
  45 static identifier
  46 new_identifier(const char* n, PyArena *arena) {
  47     PyObject* id = PyString_InternFromString(n);
  48     PyArena_AddPyObject(arena, id);
  49     return id;
  50 }
  51
  52 #define NEW_IDENTIFIER(n) new_identifier(STR(n), c->c_arena)
  53
  54 /* This routine provides an invalid object for the syntax error.
  55    The outermost routine must unpack this error and create the
  56    proper object.  We do this so that we don't have to pass
  57    the filename to everything function.
  58
  59    XXX Maybe we should just pass the filename...
  60 */
  61
  62 static int
  63 ast_error(const node *n, const char *errstr)
  64 {
  65     PyObject *u = Py_BuildValue("zi", errstr, LINENO(n));
  66     if (!u)
  67         return 0;
  68     PyErr_SetObject(PyExc_SyntaxError, u);
  69     Py_DECREF(u);
  70     return 0;
  71 }
  72
  73 static void
  74 ast_error_finish(const char *filename)
  75 {
  76     PyObject *type, *value, *tback, *errstr, *loc, *tmp;
  77     long lineno;
  78
  79     assert(PyErr_Occurred());
  80     if (!PyErr_ExceptionMatches(PyExc_SyntaxError))
  81         return;
  82
  83     PyErr_Fetch(&type, &value, &tback);
  84     errstr = PyTuple_GetItem(value, 0);
  85     if (!errstr)
  86         return;
  87     Py_INCREF(errstr);
  88     lineno = PyInt_AsLong(PyTuple_GetItem(value, 1));
  89     if (lineno == -1) {
  90         Py_DECREF(errstr);
  91         return;
  92     }
  93     Py_DECREF(value);
  94
  95     loc = PyErr_ProgramText(filename, lineno);
  96     if (!loc) {
  97         Py_INCREF(Py_None);
  98         loc = Py_None;
  99     }
 100     tmp = Py_BuildValue("(zlOO)", filename, lineno, Py_None, loc);
 101     Py_DECREF(loc);
 102     if (!tmp) {
 103         Py_DECREF(errstr);
 104         return;
 105     }
 106     value = PyTuple_Pack(2, errstr, tmp);
 107     Py_DECREF(errstr);
 108     Py_DECREF(tmp);
 109     if (!value)
 110         return;
 111     PyErr_Restore(type, value, tback);
 112 }
 113
 114 /* num_stmts() returns number of contained statements.
 115
 116    Use this routine to determine how big a sequence is needed for
 117    the statements in a parse tree.  Its raison d'etre is this bit of
 118    grammar:
 119
 120    stmt: simple_stmt | compound_stmt
 121    simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
 122
 123    A simple_stmt can contain multiple small_stmt elements joined
 124    by semicolons.  If the arg is a simple_stmt, the number of
 125    small_stmt elements is returned.
 126 */
 127
 128 static int
 129 num_stmts(const node *n)
 130 {
 131     int i, l;
 132     node *ch;
 133
 134     switch (TYPE(n)) {
 135         case single_input:
 136             if (TYPE(CHILD(n, 0)) == NEWLINE)
 137                 return 0;
 138             else
 139                 return num_stmts(CHILD(n, 0));
 140         case file_input:
 141             l = 0;
 142             for (i = 0; i < NCH(n); i++) {
 143                 ch = CHILD(n, i);
 144                 if (TYPE(ch) == stmt)
 145                     l += num_stmts(ch);
 146             }
 147             return l;
 148         case stmt:
 149             return num_stmts(CHILD(n, 0));
 150         case compound_stmt:
 151             return 1;
 152         case simple_stmt:
 153             return NCH(n) / 2; /* Divide by 2 to remove count of semi-colons */
 154         case suite:
 155             if (NCH(n) == 1)
 156                 return num_stmts(CHILD(n, 0));
 157             else {
 158                 l = 0;
 159                 for (i = 2; i < (NCH(n) - 1); i++)
 160                     l += num_stmts(CHILD(n, i));
 161                 return l;
 162             }
 163         default: {
 164             char buf[128];
 165
 166             sprintf(buf, "Non-statement found: %d %d\n",
 167                     TYPE(n), NCH(n));
 168             Py_FatalError(buf);
 169         }
 170     }
 171     assert(0);
 172     return 0;
 173 }
 174
 175 /* Transform the CST rooted at node * to the appropriate AST
 176 */
 177
 178 mod_ty
 179 PyAST_FromNode(const node *n, PyCompilerFlags *flags, const char *filename,
 180                PyArena *arena)
 181 {
 182     int i, j, k, num;
 183     asdl_seq *stmts = NULL;
 184     stmt_ty s;
 185     node *ch;
 186     struct compiling c;
 187
 188     if (flags && flags->cf_flags & PyCF_SOURCE_IS_UTF8) {
 189         c.c_encoding = "utf-8";
 190         if (TYPE(n) == encoding_decl) {
 191             ast_error(n, "encoding declaration in Unicode string");
 192             goto error;
 193         }
 194     } else if (TYPE(n) == encoding_decl) {
 195         c.c_encoding = STR(n);
 196         n = CHILD(n, 0);
 197     } else {
 198         c.c_encoding = NULL;
 199     }
 200     c.c_arena = arena;
 201     c.c_filename = filename;
 202
 203     k = 0;
 204     switch (TYPE(n)) {
 205         case file_input:
 206             stmts = asdl_seq_new(num_stmts(n), arena);
 207             if (!stmts)
 208                 return NULL;
 209             for (i = 0; i < NCH(n) - 1; i++) {
 210                 ch = CHILD(n, i);
 211                 if (TYPE(ch) == NEWLINE)
 212                     continue;
 213                 REQ(ch, stmt);
 214                 num = num_stmts(ch);
 215                 if (num == 1) {
 216                     s = ast_for_stmt(&c, ch);
 217                     if (!s)
 218                         goto error;
 219                     asdl_seq_SET(stmts, k++, s);
 220                 }
 221                 else {
 222                     ch = CHILD(ch, 0);
 223                     REQ(ch, simple_stmt);
 224                     for (j = 0; j < num; j++) {
 225                         s = ast_for_stmt(&c, CHILD(ch, j * 2));
 226                         if (!s)
 227                             goto error;
 228                         asdl_seq_SET(stmts, k++, s);
 229                     }
 230                 }
 231             }
 232             return Module(stmts, arena);
 233         case eval_input: {
 234             expr_ty testlist_ast;
 235
 236             /* XXX Why not gen_for here? */
 237             testlist_ast = ast_for_testlist(&c, CHILD(n, 0));
 238             if (!testlist_ast)
 239                 goto error;
 240             return Expression(testlist_ast, arena);
 241         }
 242         case single_input:
 243             if (TYPE(CHILD(n, 0)) == NEWLINE) {
 244                 stmts = asdl_seq_new(1, arena);
 245                 if (!stmts)
 246                     goto error;
 247                 asdl_seq_SET(stmts, 0, Pass(n->n_lineno, n->n_col_offset,
 248                                             arena));
 249                 if (!asdl_seq_GET(stmts, 0))
 250                     goto error;
 251                 return Interactive(stmts, arena);
 252             }
 253             else {
 254                 n = CHILD(n, 0);
 255                 num = num_stmts(n);
 256                 stmts = asdl_seq_new(num, arena);
 257                 if (!stmts)
 258                     goto error;
 259                 if (num == 1) {
 260                     s = ast_for_stmt(&c, n);
 261                     if (!s)
 262                         goto error;
 263                     asdl_seq_SET(stmts, 0, s);
 264                 }
 265                 else {
 266                     /* Only a simple_stmt can contain multiple statements. */
 267                     REQ(n, simple_stmt);
 268                     for (i = 0; i < NCH(n); i += 2) {
 269                         if (TYPE(CHILD(n, i)) == NEWLINE)
 270                             break;
 271                         s = ast_for_stmt(&c, CHILD(n, i));
 272                         if (!s)
 273                             goto error;
 274                         asdl_seq_SET(stmts, i / 2, s);
 275                     }
 276                 }
 277
 278                 return Interactive(stmts, arena);
 279             }
 280         default:
 281             PyErr_Format(PyExc_SystemError,
 282                          "invalid node %d for PyAST_FromNode", TYPE(n));
 283             goto error;
 284     }
 285  error:
 286     ast_error_finish(filename);
 287     return NULL;
 288 }
 289
 290 /* Return the AST repr. of the operator represented as syntax (|, ^, etc.)
 291 */
 292
 293 static operator_ty
 294 get_operator(const node *n)
 295 {
 296     switch (TYPE(n)) {
 297         case VBAR:
 298             return BitOr;
 299         case CIRCUMFLEX:
 300             return BitXor;
 301         case AMPER:
 302             return BitAnd;
 303         case LEFTSHIFT:
 304             return LShift;
 305         case RIGHTSHIFT:
 306             return RShift;
 307         case PLUS:
 308             return Add;
 309         case MINUS:
 310             return Sub;
 311         case STAR:
 312             return Mult;
 313         case SLASH:
 314             return Div;
 315         case DOUBLESLASH:
 316             return FloorDiv;
 317         case PERCENT:
 318             return Mod;
 319         default:
 320             return (operator_ty)0;
 321     }
 322 }
 323
 324 /* Set the context ctx for expr_ty e, recursively traversing e.
 325
 326    Only sets context for expr kinds that "can appear in assignment context"
 327    (according to ../Parser/Python.asdl).  For other expr kinds, it sets
 328    an appropriate syntax error and returns false.
 329 */
 330
 331 static int
 332 set_context(expr_ty e, expr_context_ty ctx, const node *n)
 333 {
 334     asdl_seq *s = NULL;
 335     /* If a particular expression type can't be used for assign / delete,
 336        set expr_name to its name and an error message will be generated.
 337     */
 338     const char* expr_name = NULL;
 339
 340     /* The ast defines augmented store and load contexts, but the
 341        implementation here doesn't actually use them.  The code may be
 342        a little more complex than necessary as a result.  It also means
 343        that expressions in an augmented assignment have a Store context.
 344        Consider restructuring so that augmented assignment uses
 345        set_context(), too.
 346     */
 347     assert(ctx != AugStore && ctx != AugLoad);
 348
 349     switch (e->kind) {
 350         case Attribute_kind:
 351             if (ctx == Store &&
 352                 !strcmp(PyString_AS_STRING(e->v.Attribute.attr), "None")) {
 353                 return ast_error(n, "assignment to None");
 354             }
 355             e->v.Attribute.ctx = ctx;
 356             break;
 357         case Subscript_kind:
 358             e->v.Subscript.ctx = ctx;
 359             break;
 360         case Name_kind:
 361             if (ctx == Store &&
 362                 !strcmp(PyString_AS_STRING(e->v.Name.id), "None")) {
 363                     return ast_error(n, "assignment to None");
 364             }
 365             e->v.Name.ctx = ctx;
 366             break;
 367         case List_kind:
 368             e->v.List.ctx = ctx;
 369             s = e->v.List.elts;
 370             break;
 371         case Tuple_kind:
 372             if (asdl_seq_LEN(e->v.Tuple.elts) == 0)
 373                 return ast_error(n, "can't assign to ()");
 374             e->v.Tuple.ctx = ctx;
 375             s = e->v.Tuple.elts;
 376             break;
 377         case Lambda_kind:
 378             expr_name = "lambda";
 379             break;
 380         case Call_kind:
 381             expr_name = "function call";
 382             break;
 383         case BoolOp_kind:
 384         case BinOp_kind:
 385         case UnaryOp_kind:
 386             expr_name = "operator";
 387             break;
 388         case GeneratorExp_kind:
 389             expr_name = "generator expression";
 390             break;
 391         case Yield_kind:
 392             expr_name = "yield expression";
 393             break;
 394         case ListComp_kind:
 395             expr_name = "list comprehension";
 396             break;
 397         case Dict_kind:
 398         case Num_kind:
 399         case Str_kind:
 400             expr_name = "literal";
 401             break;
 402         case Compare_kind:
 403             expr_name = "comparison";
 404             break;
 405         case Repr_kind:
 406             expr_name = "repr";
 407             break;
 408         case IfExp_kind:
 409             expr_name = "conditional expression";
 410             break;
 411         default:
 412             PyErr_Format(PyExc_SystemError,
 413                          "unexpected expression in assignment %d (line %d)",
 414                          e->kind, e->lineno);
 415             return 0;
 416     }
 417     /* Check for error string set by switch */
 418     if (expr_name) {
 419         char buf[300];
 420         PyOS_snprintf(buf, sizeof(buf),
 421                       "can't %s %s",
 422                       ctx == Store ? "assign to" : "delete",
 423                       expr_name);
 424         return ast_error(n, buf);
 425     }
 426
 427     /* If the LHS is a list or tuple, we need to set the assignment
 428        context for all the contained elements.
 429     */
 430     if (s) {
 431         int i;
 432
 433         for (i = 0; i < asdl_seq_LEN(s); i++) {
 434             if (!set_context((expr_ty)asdl_seq_GET(s, i), ctx, n))
 435                 return 0;
 436         }
 437     }
 438     return 1;
 439 }
 440
 441 static operator_ty
 442 ast_for_augassign(const node *n)
 443 {
 444     REQ(n, augassign);
 445     n = CHILD(n, 0);
 446     switch (STR(n)[0]) {
 447         case '+':
 448             return Add;
 449         case '-':
 450             return Sub;
 451         case '/':
 452             if (STR(n)[1] == '/')
 453                 return FloorDiv;
 454             else
 455                 return Div;
 456         case '%':
 457             return Mod;
 458         case '<':
 459             return LShift;
 460         case '>':
 461             return RShift;
 462         case '&':
 463             return BitAnd;
 464         case '^':
 465             return BitXor;
 466         case '|':
 467             return BitOr;
 468         case '*':
 469             if (STR(n)[1] == '*')
 470                 return Pow;
 471             else
 472                 return Mult;
 473         default:
 474             PyErr_Format(PyExc_SystemError, "invalid augassign: %s", STR(n));
 475             return (operator_ty)0;
 476     }
 477 }
 478
 479 static cmpop_ty
 480 ast_for_comp_op(const node *n)
 481 {
 482     /* comp_op: '<'|'>'|'=='|'>='|'<='|'<>'|'!='|'in'|'not' 'in'|'is'
 483                |'is' 'not'
 484     */
 485     REQ(n, comp_op);
 486     if (NCH(n) == 1) {
 487         n = CHILD(n, 0);
 488         switch (TYPE(n)) {
 489             case LESS:
 490                 return Lt;
 491             case GREATER:
 492                 return Gt;
 493             case EQEQUAL:                       /* == */
 494                 return Eq;
 495             case LESSEQUAL:
 496                 return LtE;
 497             case GREATEREQUAL:
 498                 return GtE;
 499             case NOTEQUAL:
 500                 return NotEq;
 501             case NAME:
 502                 if (strcmp(STR(n), "in") == 0)
 503                     return In;
 504                 if (strcmp(STR(n), "is") == 0)
 505                     return Is;
 506             default:
 507                 PyErr_Format(PyExc_SystemError, "invalid comp_op: %s",
 508                              STR(n));
 509                 return (cmpop_ty)0;
 510         }
 511     }
 512     else if (NCH(n) == 2) {
 513         /* handle "not in" and "is not" */
 514         switch (TYPE(CHILD(n, 0))) {
 515             case NAME:
 516                 if (strcmp(STR(CHILD(n, 1)), "in") == 0)
 517                     return NotIn;
 518                 if (strcmp(STR(CHILD(n, 0)), "is") == 0)
 519                     return IsNot;
 520             default:
 521                 PyErr_Format(PyExc_SystemError, "invalid comp_op: %s %s",
 522                              STR(CHILD(n, 0)), STR(CHILD(n, 1)));
 523                 return (cmpop_ty)0;
 524         }
 525     }
 526     PyErr_Format(PyExc_SystemError, "invalid comp_op: has %d children",
 527                  NCH(n));
 528     return (cmpop_ty)0;
 529 }
 530
 531 static asdl_seq *
 532 seq_for_testlist(struct compiling *c, const node *n)
 533 {
 534     /* testlist: test (',' test)* [','] */
 535     asdl_seq *seq;
 536     expr_ty expression;
 537     int i;
 538     assert(TYPE(n) == testlist ||
 539            TYPE(n) == listmaker ||
 540            TYPE(n) == testlist_gexp ||
 541            TYPE(n) == testlist_safe ||
 542            TYPE(n) == testlist1);
 543
 544     seq = asdl_seq_new((NCH(n) + 1) / 2, c->c_arena);
 545     if (!seq)
 546         return NULL;
 547
 548     for (i = 0; i < NCH(n); i += 2) {
 549         assert(TYPE(CHILD(n, i)) == test || TYPE(CHILD(n, i)) == old_test);
 550
 551         expression = ast_for_expr(c, CHILD(n, i));
 552         if (!expression)
 553             return NULL;
 554
 555         assert(i / 2 < seq->size);
 556         asdl_seq_SET(seq, i / 2, expression);
 557     }
 558     return seq;
 559 }
 560
 561 static expr_ty
 562 compiler_complex_args(struct compiling *c, const node *n)
 563 {
 564     int i, len = (NCH(n) + 1) / 2;
 565     expr_ty result;
 566     asdl_seq *args = asdl_seq_new(len, c->c_arena);
 567     if (!args)
 568         return NULL;
 569
 570     /* fpdef: NAME | '(' fplist ')'
 571        fplist: fpdef (',' fpdef)* [',']
 572     */
 573     REQ(n, fplist);
 574     for (i = 0; i < len; i++) {
 575         const node *fpdef_node = CHILD(n, 2*i);
 576         const node *child;
 577         expr_ty arg;
 578 set_name:
 579         /* fpdef_node is either a NAME or an fplist */
 580         child = CHILD(fpdef_node, 0);
 581         if (TYPE(child) == NAME) {
 582             if (!strcmp(STR(child), "None")) {
 583                 ast_error(child, "assignment to None");
 584                 return NULL;
 585             }
 586             arg = Name(NEW_IDENTIFIER(child), Store, LINENO(child),
 587                        child->n_col_offset, c->c_arena);
 588         }
 589         else {
 590             assert(TYPE(fpdef_node) == fpdef);
 591             /* fpdef_node[0] is not a name, so it must be '(', get CHILD[1] */
 592             child = CHILD(fpdef_node, 1);
 593             assert(TYPE(child) == fplist);
 594             /* NCH == 1 means we have (x), we need to elide the extra parens */
 595             if (NCH(child) == 1) {
 596                 fpdef_node = CHILD(child, 0);
 597                 assert(TYPE(fpdef_node) == fpdef);
 598                 goto set_name;
 599             }
 600             arg = compiler_complex_args(c, child);
 601         }
 602         asdl_seq_SET(args, i, arg);
 603     }
 604
 605     result = Tuple(args, Store, LINENO(n), n->n_col_offset, c->c_arena);
 606     if (!set_context(result, Store, n))
 607         return NULL;
 608     return result;
 609 }
 610
 611
 612 /* Create AST for argument list. */
 613
 614 static arguments_ty
 615 ast_for_arguments(struct compiling *c, const node *n)
 616 {
 617     /* parameters: '(' [varargslist] ')'
 618        varargslist: (fpdef ['=' test] ',')* ('*' NAME [',' '**' NAME]
 619             | '**' NAME) | fpdef ['=' test] (',' fpdef ['=' test])* [',']
 620     */
 621     int i, j, k, n_args = 0, n_defaults = 0, found_default = 0;
 622     asdl_seq *args, *defaults;
 623     identifier vararg = NULL, kwarg = NULL;
 624     node *ch;
 625
 626     if (TYPE(n) == parameters) {
 627         if (NCH(n) == 2) /* () as argument list */
 628             return arguments(NULL, NULL, NULL, NULL, c->c_arena);
 629         n = CHILD(n, 1);
 630     }
 631     REQ(n, varargslist);
 632
 633     /* first count the number of normal args & defaults */
 634     for (i = 0; i < NCH(n); i++) {
 635         ch = CHILD(n, i);
 636         if (TYPE(ch) == fpdef)
 637             n_args++;
 638         if (TYPE(ch) == EQUAL)
 639             n_defaults++;
 640     }
 641     args = (n_args ? asdl_seq_new(n_args, c->c_arena) : NULL);
 642     if (!args && n_args)
 643         return NULL; /* Don't need to goto error; no objects allocated */
 644     defaults = (n_defaults ? asdl_seq_new(n_defaults, c->c_arena) : NULL);
 645     if (!defaults && n_defaults)
 646         return NULL; /* Don't need to goto error; no objects allocated */
 647
 648     /* fpdef: NAME | '(' fplist ')'
 649        fplist: fpdef (',' fpdef)* [',']
 650     */
 651     i = 0;
 652     j = 0;  /* index for defaults */
 653     k = 0;  /* index for args */
 654     while (i < NCH(n)) {
 655         ch = CHILD(n, i);
 656         switch (TYPE(ch)) {
 657             case fpdef:
 658             handle_fpdef:
 659                 /* XXX Need to worry about checking if TYPE(CHILD(n, i+1)) is
 660                    anything other than EQUAL or a comma? */
 661                 /* XXX Should NCH(n) check be made a separate check? */
 662                 if (i + 1 < NCH(n) && TYPE(CHILD(n, i + 1)) == EQUAL) {
 663                     expr_ty expression = ast_for_expr(c, CHILD(n, i + 2));
 664                     if (!expression)
 665                         goto error;
 666                     assert(defaults != NULL);
 667                     asdl_seq_SET(defaults, j++, expression);
 668                     i += 2;
 669                     found_default = 1;
 670                 }
 671                 else if (found_default) {
 672                     ast_error(n,
 673                              "non-default argument follows default argument");
 674                     goto error;
 675                 }
 676                 if (NCH(ch) == 3) {
 677                     ch = CHILD(ch, 1);
 678                     /* def foo((x)): is not complex, special case. */
 679                     if (NCH(ch) != 1) {
 680                         /* We have complex arguments, setup for unpacking. */
 681                         asdl_seq_SET(args, k++, compiler_complex_args(c, ch));
 682                         if (!asdl_seq_GET(args, k-1))
 683                                 goto error;
 684                     } else {
 685                         /* def foo((x)): setup for checking NAME below. */
 686                         /* Loop because there can be many parens and tuple
 687                            unpacking mixed in. */
 688                         ch = CHILD(ch, 0);
 689                         assert(TYPE(ch) == fpdef);
 690                         goto handle_fpdef;
 691                     }
 692                 }
 693                 if (TYPE(CHILD(ch, 0)) == NAME) {
 694                     expr_ty name;
 695                     if (!strcmp(STR(CHILD(ch, 0)), "None")) {
 696                         ast_error(CHILD(ch, 0), "assignment to None");
 697                         goto error;
 698                     }
 699                     name = Name(NEW_IDENTIFIER(CHILD(ch, 0)),
 700                                 Param, LINENO(ch), ch->n_col_offset,
 701                                 c->c_arena);
 702                     if (!name)
 703                         goto error;
 704                     asdl_seq_SET(args, k++, name);
 705
 706                 }
 707                 i += 2; /* the name and the comma */
 708                 break;
 709             case STAR:
 710                 if (!strcmp(STR(CHILD(n, i+1)), "None")) {
 711                     ast_error(CHILD(n, i+1), "assignment to None");
 712                     goto error;
 713                 }
 714                 vararg = NEW_IDENTIFIER(CHILD(n, i+1));
 715                 i += 3;
 716                 break;
 717             case DOUBLESTAR:
 718                 if (!strcmp(STR(CHILD(n, i+1)), "None")) {
 719                     ast_error(CHILD(n, i+1), "assignment to None");
 720                     goto error;
 721                 }
 722                 kwarg = NEW_IDENTIFIER(CHILD(n, i+1));
 723                 i += 3;
 724                 break;
 725             default:
 726                 PyErr_Format(PyExc_SystemError,
 727                              "unexpected node in varargslist: %d @ %d",
 728                              TYPE(ch), i);
 729                 goto error;
 730         }
 731     }
 732
 733     return arguments(args, vararg, kwarg, defaults, c->c_arena);
 734
 735  error:
 736     Py_XDECREF(vararg);
 737     Py_XDECREF(kwarg);
 738     return NULL;
 739 }
 740
 741 static expr_ty
 742 ast_for_dotted_name(struct compiling *c, const node *n)
 743 {
 744     expr_ty e;
 745     identifier id;
 746     int lineno, col_offset;
 747     int i;
 748
 749     REQ(n, dotted_name);
 750
 751     lineno = LINENO(n);
 752     col_offset = n->n_col_offset;
 753
 754     id = NEW_IDENTIFIER(CHILD(n, 0));
 755     if (!id)
 756         return NULL;
 757     e = Name(id, Load, lineno, col_offset, c->c_arena);
 758     if (!e)
 759         return NULL;
 760
 761     for (i = 2; i < NCH(n); i+=2) {
 762         id = NEW_IDENTIFIER(CHILD(n, i));
 763         if (!id)
 764             return NULL;
 765         e = Attribute(e, id, Load, lineno, col_offset, c->c_arena);
 766         if (!e)
 767             return NULL;
 768     }
 769
 770     return e;
 771 }
 772
 773 static expr_ty
 774 ast_for_decorator(struct compiling *c, const node *n)
 775 {
 776     /* decorator: '@' dotted_name [ '(' [arglist] ')' ] NEWLINE */
 777     expr_ty d = NULL;
 778     expr_ty name_expr;
 779
 780     REQ(n, decorator);
 781     REQ(CHILD(n, 0), AT);
 782     REQ(RCHILD(n, -1), NEWLINE);
 783
 784     name_expr = ast_for_dotted_name(c, CHILD(n, 1));
 785     if (!name_expr)
 786         return NULL;
 787
 788     if (NCH(n) == 3) { /* No arguments */
 789         d = name_expr;
 790         name_expr = NULL;
 791     }
 792     else if (NCH(n) == 5) { /* Call with no arguments */
 793         d = Call(name_expr, NULL, NULL, NULL, NULL, LINENO(n),
 794                  n->n_col_offset, c->c_arena);
 795         if (!d)
 796             return NULL;
 797         name_expr = NULL;
 798     }
 799     else {
 800         d = ast_for_call(c, CHILD(n, 3), name_expr);
 801         if (!d)
 802             return NULL;
 803         name_expr = NULL;
 804     }
 805
 806     return d;
 807 }
 808
 809 static asdl_seq*
 810 ast_for_decorators(struct compiling *c, const node *n)
 811 {
 812     asdl_seq* decorator_seq;
 813     expr_ty d;
 814     int i;
 815
 816     REQ(n, decorators);
 817     decorator_seq = asdl_seq_new(NCH(n), c->c_arena);
 818     if (!decorator_seq)
 819         return NULL;
 820
 821     for (i = 0; i < NCH(n); i++) {
 822         d = ast_for_decorator(c, CHILD(n, i));
 823             if (!d)
 824                 return NULL;
 825             asdl_seq_SET(decorator_seq, i, d);
 826     }
 827     return decorator_seq;
 828 }
 829
 830 static stmt_ty
 831 ast_for_funcdef(struct compiling *c, const node *n)
 832 {
 833     /* funcdef: 'def' [decorators] NAME parameters ':' suite */
 834     identifier name;
 835     arguments_ty args;
 836     asdl_seq *body;
 837     asdl_seq *decorator_seq = NULL;
 838     int name_i;
 839
 840     REQ(n, funcdef);
 841
 842     if (NCH(n) == 6) { /* decorators are present */
 843         decorator_seq = ast_for_decorators(c, CHILD(n, 0));
 844         if (!decorator_seq)
 845             return NULL;
 846         name_i = 2;
 847     }
 848     else {
 849         name_i = 1;
 850     }
 851
 852     name = NEW_IDENTIFIER(CHILD(n, name_i));
 853     if (!name)
 854         return NULL;
 855     else if (!strcmp(STR(CHILD(n, name_i)), "None")) {
 856         ast_error(CHILD(n, name_i), "assignment to None");
 857         return NULL;
 858     }
 859     args = ast_for_arguments(c, CHILD(n, name_i + 1));
 860     if (!args)
 861         return NULL;
 862     body = ast_for_suite(c, CHILD(n, name_i + 3));
 863     if (!body)
 864         return NULL;
 865
 866     return FunctionDef(name, args, body, decorator_seq, LINENO(n),
 867                        n->n_col_offset, c->c_arena);
 868 }
 869
 870 static expr_ty
 871 ast_for_lambdef(struct compiling *c, const node *n)
 872 {
 873     /* lambdef: 'lambda' [varargslist] ':' test */
 874     arguments_ty args;
 875     expr_ty expression;
 876
 877     if (NCH(n) == 3) {
 878         args = arguments(NULL, NULL, NULL, NULL, c->c_arena);
 879         if (!args)
 880             return NULL;
 881         expression = ast_for_expr(c, CHILD(n, 2));
 882         if (!expression)
 883             return NULL;
 884     }
 885     else {
 886         args = ast_for_arguments(c, CHILD(n, 1));
 887         if (!args)
 888             return NULL;
 889         expression = ast_for_expr(c, CHILD(n, 3));
 890         if (!expression)
 891             return NULL;
 892     }
 893
 894     return Lambda(args, expression, LINENO(n), n->n_col_offset, c->c_arena);
 895 }
 896
 897 static expr_ty
 898 ast_for_ifexpr(struct compiling *c, const node *n)
 899 {
 900     /* test: or_test 'if' or_test 'else' test */
 901     expr_ty expression, body, orelse;
 902
 903     assert(NCH(n) == 5);
 904     body = ast_for_expr(c, CHILD(n, 0));
 905     if (!body)
 906         return NULL;
 907     expression = ast_for_expr(c, CHILD(n, 2));
 908     if (!expression)
 909         return NULL;
 910     orelse = ast_for_expr(c, CHILD(n, 4));
 911     if (!orelse)
 912         return NULL;
 913     return IfExp(expression, body, orelse, LINENO(n), n->n_col_offset,
 914                  c->c_arena);
 915 }
 916
 917 /* XXX(nnorwitz): the listcomp and genexpr code should be refactored
 918    so there is only a single version.  Possibly for loops can also re-use
 919    the code.
 920 */
 921
 922 /* Count the number of 'for' loop in a list comprehension.
 923
 924    Helper for ast_for_listcomp().
 925 */
 926
 927 static int
 928 count_list_fors(const node *n)
 929 {
 930     int n_fors = 0;
 931     node *ch = CHILD(n, 1);
 932
 933  count_list_for:
 934     n_fors++;
 935     REQ(ch, list_for);
 936     if (NCH(ch) == 5)
 937         ch = CHILD(ch, 4);
 938     else
 939         return n_fors;
 940  count_list_iter:
 941     REQ(ch, list_iter);
 942     ch = CHILD(ch, 0);
 943     if (TYPE(ch) == list_for)
 944         goto count_list_for;
 945     else if (TYPE(ch) == list_if) {
 946         if (NCH(ch) == 3) {
 947             ch = CHILD(ch, 2);
 948             goto count_list_iter;
 949         }
 950         else
 951             return n_fors;
 952     }
 953
 954     /* Should never be reached */
 955     PyErr_SetString(PyExc_SystemError, "logic error in count_list_fors");
 956     return -1;
 957 }
 958
 959 /* Count the number of 'if' statements in a list comprehension.
 960
 961    Helper for ast_for_listcomp().
 962 */
 963
 964 static int
 965 count_list_ifs(const node *n)
 966 {
 967     int n_ifs = 0;
 968
 969  count_list_iter:
 970     REQ(n, list_iter);
 971     if (TYPE(CHILD(n, 0)) == list_for)
 972         return n_ifs;
 973     n = CHILD(n, 0);
 974     REQ(n, list_if);
 975     n_ifs++;
 976     if (NCH(n) == 2)
 977         return n_ifs;
 978     n = CHILD(n, 2);
 979     goto count_list_iter;
 980 }
 981
 982 static expr_ty
 983 ast_for_listcomp(struct compiling *c, const node *n)
 984 {
 985     /* listmaker: test ( list_for | (',' test)* [','] )
 986        list_for: 'for' exprlist 'in' testlist_safe [list_iter]
 987        list_iter: list_for | list_if
 988        list_if: 'if' test [list_iter]
 989        testlist_safe: test [(',' test)+ [',']]
 990     */
 991     expr_ty elt;
 992     asdl_seq *listcomps;
 993     int i, n_fors;
 994     node *ch;
 995
 996     REQ(n, listmaker);
 997     assert(NCH(n) > 1);
 998
 999     elt = ast_for_expr(c, CHILD(n, 0));
1000     if (!elt)
1001         return NULL;
1002
1003     n_fors = count_list_fors(n);
1004     if (n_fors == -1)
1005         return NULL;
1006
1007     listcomps = asdl_seq_new(n_fors, c->c_arena);
1008     if (!listcomps)
1009         return NULL;
1010
1011     ch = CHILD(n, 1);
1012     for (i = 0; i < n_fors; i++) {
1013         comprehension_ty lc;
1014         asdl_seq *t;
1015         expr_ty expression;
1016         node *for_ch;
1017
1018         REQ(ch, list_for);
1019
1020         for_ch = CHILD(ch, 1);
1021         t = ast_for_exprlist(c, for_ch, Store);
1022         if (!t)
1023             return NULL;
1024         expression = ast_for_testlist(c, CHILD(ch, 3));
1025         if (!expression)
1026             return NULL;
1027
1028         /* Check the # of children rather than the length of t, since
1029            [x for x, in ... ] has 1 element in t, but still requires a Tuple.
1030         */
1031         if (NCH(for_ch) == 1)
1032             lc = comprehension((expr_ty)asdl_seq_GET(t, 0), expression, NULL,
1033                                c->c_arena);
1034         else
1035             lc = comprehension(Tuple(t, Store, LINENO(ch), ch->n_col_offset,
1036                                      c->c_arena),
1037                                expression, NULL, c->c_arena);
1038         if (!lc)
1039             return NULL;
1040
1041         if (NCH(ch) == 5) {
1042             int j, n_ifs;
1043             asdl_seq *ifs;
1044             expr_ty list_for_expr;
1045
1046             ch = CHILD(ch, 4);
1047             n_ifs = count_list_ifs(ch);
1048             if (n_ifs == -1)
1049                 return NULL;
1050
1051             ifs = asdl_seq_new(n_ifs, c->c_arena);
1052             if (!ifs)
1053                 return NULL;
1054
1055             for (j = 0; j < n_ifs; j++) {
1056                 REQ(ch, list_iter);
1057                 ch = CHILD(ch, 0);
1058                 REQ(ch, list_if);
1059
1060                 list_for_expr = ast_for_expr(c, CHILD(ch, 1));
1061                 if (!list_for_expr)
1062                     return NULL;
1063
1064                 asdl_seq_SET(ifs, j, list_for_expr);
1065                 if (NCH(ch) == 3)
1066                     ch = CHILD(ch, 2);
1067             }
1068             /* on exit, must guarantee that ch is a list_for */
1069             if (TYPE(ch) == list_iter)
1070                 ch = CHILD(ch, 0);
1071             lc->ifs = ifs;
1072         }
1073         asdl_seq_SET(listcomps, i, lc);
1074     }
1075
1076     return ListComp(elt, listcomps, LINENO(n), n->n_col_offset, c->c_arena);
1077 }
1078
1079 /* Count the number of 'for' loops in a generator expression.
1080
1081    Helper for ast_for_genexp().
1082 */
1083
1084 static int
1085 count_gen_fors(const node *n)
1086 {
1087     int n_fors = 0;
1088     node *ch = CHILD(n, 1);
1089
1090  count_gen_for:
1091     n_fors++;
1092     REQ(ch, gen_for);
1093     if (NCH(ch) == 5)
1094         ch = CHILD(ch, 4);
1095     else
1096         return n_fors;
1097  count_gen_iter:
1098     REQ(ch, gen_iter);
1099     ch = CHILD(ch, 0);
1100     if (TYPE(ch) == gen_for)
1101         goto count_gen_for;
1102     else if (TYPE(ch) == gen_if) {
1103         if (NCH(ch) == 3) {
1104             ch = CHILD(ch, 2);
1105             goto count_gen_iter;
1106         }
1107         else
1108             return n_fors;
1109     }
1110
1111     /* Should never be reached */
1112     PyErr_SetString(PyExc_SystemError,
1113                     "logic error in count_gen_fors");
1114     return -1;
1115 }
1116
1117 /* Count the number of 'if' statements in a generator expression.
1118
1119    Helper for ast_for_genexp().
1120 */
1121
1122 static int
1123 count_gen_ifs(const node *n)
1124 {
1125     int n_ifs = 0;
1126
1127     while (1) {
1128         REQ(n, gen_iter);
1129         if (TYPE(CHILD(n, 0)) == gen_for)
1130             return n_ifs;
1131         n = CHILD(n, 0);
1132         REQ(n, gen_if);
1133         n_ifs++;
1134         if (NCH(n) == 2)
1135             return n_ifs;
1136         n = CHILD(n, 2);
1137     }
1138 }
1139
1140 /* TODO(jhylton): Combine with list comprehension code? */
1141 static expr_ty
1142 ast_for_genexp(struct compiling *c, const node *n)
1143 {
1144     /* testlist_gexp: test ( gen_for | (',' test)* [','] )
1145        argument: [test '='] test [gen_for]       # Really [keyword '='] test */
1146     expr_ty elt;
1147     asdl_seq *genexps;
1148     int i, n_fors;
1149     node *ch;
1150
1151     assert(TYPE(n) == (testlist_gexp) || TYPE(n) == (argument));
1152     assert(NCH(n) > 1);
1153
1154     elt = ast_for_expr(c, CHILD(n, 0));
1155     if (!elt)
1156         return NULL;
1157
1158     n_fors = count_gen_fors(n);
1159     if (n_fors == -1)
1160         return NULL;
1161
1162     genexps = asdl_seq_new(n_fors, c->c_arena);
1163     if (!genexps)
1164         return NULL;
1165
1166     ch = CHILD(n, 1);
1167     for (i = 0; i < n_fors; i++) {
1168         comprehension_ty ge;
1169         asdl_seq *t;
1170         expr_ty expression;
1171         node *for_ch;
1172
1173         REQ(ch, gen_for);
1174
1175         for_ch = CHILD(ch, 1);
1176         t = ast_for_exprlist(c, for_ch, Store);
1177         if (!t)
1178             return NULL;
1179         expression = ast_for_expr(c, CHILD(ch, 3));
1180         if (!expression)
1181             return NULL;
1182
1183         /* Check the # of children rather than the length of t, since
1184            (x for x, in ...) has 1 element in t, but still requires a Tuple. */
1185         if (NCH(for_ch) == 1)
1186             ge = comprehension((expr_ty)asdl_seq_GET(t, 0), expression,
1187                                NULL, c->c_arena);
1188         else
1189             ge = comprehension(Tuple(t, Store, LINENO(ch), ch->n_col_offset,
1190                                      c->c_arena),
1191                                expression, NULL, c->c_arena);
1192
1193         if (!ge)
1194             return NULL;
1195
1196         if (NCH(ch) == 5) {
1197             int j, n_ifs;
1198             asdl_seq *ifs;
1199
1200             ch = CHILD(ch, 4);
1201             n_ifs = count_gen_ifs(ch);
1202             if (n_ifs == -1)
1203                 return NULL;
1204
1205             ifs = asdl_seq_new(n_ifs, c->c_arena);
1206             if (!ifs)
1207                 return NULL;
1208
1209             for (j = 0; j < n_ifs; j++) {
1210                 REQ(ch, gen_iter);
1211                 ch = CHILD(ch, 0);
1212                 REQ(ch, gen_if);
1213
1214                 expression = ast_for_expr(c, CHILD(ch, 1));
1215                 if (!expression)
1216                     return NULL;
1217                 asdl_seq_SET(ifs, j, expression);
1218                 if (NCH(ch) == 3)
1219                     ch = CHILD(ch, 2);
1220             }
1221             /* on exit, must guarantee that ch is a gen_for */
1222             if (TYPE(ch) == gen_iter)
1223                 ch = CHILD(ch, 0);
1224             ge->ifs = ifs;
1225         }
1226         asdl_seq_SET(genexps, i, ge);
1227     }
1228
1229     return GeneratorExp(elt, genexps, LINENO(n), n->n_col_offset, c->c_arena);
1230 }
1231
1232 static expr_ty
1233 ast_for_atom(struct compiling *c, const node *n)
1234 {
1235     /* atom: '(' [yield_expr|testlist_gexp] ')' | '[' [listmaker] ']'
1236        | '{' [dictmaker] '}' | '`' testlist '`' | NAME | NUMBER | STRING+
1237     */
1238     node *ch = CHILD(n, 0);
1239
1240     switch (TYPE(ch)) {
1241     case NAME:
1242         /* All names start in Load context, but may later be
1243            changed. */
1244         return Name(NEW_IDENTIFIER(ch), Load, LINENO(n), n->n_col_offset,
1245                     c->c_arena);
1246     case STRING: {
1247         PyObject *str = parsestrplus(c, n);
1248         if (!str) {
1249 #ifdef Py_USING_UNICODE
1250             if (PyErr_ExceptionMatches(PyExc_UnicodeError)){
1251                 PyObject *type, *value, *tback, *errstr;
1252                 PyErr_Fetch(&type, &value, &tback);
1253                 errstr = ((PyUnicodeErrorObject *)value)->reason;
1254                 if (errstr) {
1255                     char *s = "";
1256                     char buf[128];
1257                     s = PyString_AsString(errstr);
1258                     PyOS_snprintf(buf, sizeof(buf), "(unicode error) %s", s);
1259                     ast_error(n, buf);
1260                 } else {
1261                     ast_error(n, "(unicode error) unknown error");
1262                 }
1263                 Py_DECREF(type);
1264                 Py_DECREF(value);
1265                 Py_XDECREF(tback);
1266             }
1267 #endif
1268             return NULL;
1269         }
1270         PyArena_AddPyObject(c->c_arena, str);
1271         return Str(str, LINENO(n), n->n_col_offset, c->c_arena);
1272     }
1273     case NUMBER: {
1274         PyObject *pynum = parsenumber(STR(ch));
1275         if (!pynum)
1276             return NULL;
1277
1278         PyArena_AddPyObject(c->c_arena, pynum);
1279         return Num(pynum, LINENO(n), n->n_col_offset, c->c_arena);
1280     }
1281     case LPAR: /* some parenthesized expressions */
1282         ch = CHILD(n, 1);
1283
1284         if (TYPE(ch) == RPAR)
1285             return Tuple(NULL, Load, LINENO(n), n->n_col_offset, c->c_arena);
1286
1287         if (TYPE(ch) == yield_expr)
1288             return ast_for_expr(c, ch);
1289
1290         if ((NCH(ch) > 1) && (TYPE(CHILD(ch, 1)) == gen_for))
1291             return ast_for_genexp(c, ch);
1292
1293         return ast_for_testlist_gexp(c, ch);
1294     case LSQB: /* list (or list comprehension) */
1295         ch = CHILD(n, 1);
1296
1297         if (TYPE(ch) == RSQB)
1298             return List(NULL, Load, LINENO(n), n->n_col_offset, c->c_arena);
1299
1300         REQ(ch, listmaker);
1301         if (NCH(ch) == 1 || TYPE(CHILD(ch, 1)) == COMMA) {
1302             asdl_seq *elts = seq_for_testlist(c, ch);
1303             if (!elts)
1304                 return NULL;
1305
1306             return List(elts, Load, LINENO(n), n->n_col_offset, c->c_arena);
1307         }
1308         else
1309             return ast_for_listcomp(c, ch);
1310     case LBRACE: {
1311         /* dictmaker: test ':' test (',' test ':' test)* [','] */
1312         int i, size;
1313         asdl_seq *keys, *values;
1314
1315         ch = CHILD(n, 1);
1316         size = (NCH(ch) + 1) / 4; /* +1 in case no trailing comma */
1317         keys = asdl_seq_new(size, c->c_arena);
1318         if (!keys)
1319             return NULL;
1320
1321         values = asdl_seq_new(size, c->c_arena);
1322         if (!values)
1323             return NULL;
1324
1325         for (i = 0; i < NCH(ch); i += 4) {
1326             expr_ty expression;
1327
1328             expression = ast_for_expr(c, CHILD(ch, i));
1329             if (!expression)
1330                 return NULL;
1331
1332             asdl_seq_SET(keys, i / 4, expression);
1333
1334             expression = ast_for_expr(c, CHILD(ch, i + 2));
1335             if (!expression)
1336                 return NULL;
1337
1338             asdl_seq_SET(values, i / 4, expression);
1339         }
1340         return Dict(keys, values, LINENO(n), n->n_col_offset, c->c_arena);
1341     }
1342     case BACKQUOTE: { /* repr */
1343         expr_ty expression;
1344         if (Py_Py3kWarningFlag) {
1345             if (PyErr_WarnExplicit(PyExc_DeprecationWarning,
1346                                    "backquote not supported in 3.x",
1347                                    c->c_filename, LINENO(n),
1348                                    NULL, NULL)) {
1349             return NULL;
1350             }
1351         }
1352         expression = ast_for_testlist(c, CHILD(n, 1));
1353         if (!expression)
1354             return NULL;
1355
1356         return Repr(expression, LINENO(n), n->n_col_offset, c->c_arena);
1357     }
1358     default:
1359         PyErr_Format(PyExc_SystemError, "unhandled atom %d", TYPE(ch));
1360         return NULL;
1361     }
1362 }
1363
1364 static slice_ty
1365 ast_for_slice(struct compiling *c, const node *n)
1366 {
1367     node *ch;
1368     expr_ty lower = NULL, upper = NULL, step = NULL;
1369
1370     REQ(n, subscript);
1371
1372     /*
1373        subscript: '.' '.' '.' | test | [test] ':' [test] [sliceop]
1374        sliceop: ':' [test]
1375     */
1376     ch = CHILD(n, 0);
1377     if (TYPE(ch) == DOT)
1378         return Ellipsis(c->c_arena);
1379
1380     if (NCH(n) == 1 && TYPE(ch) == test) {
1381         /* 'step' variable hold no significance in terms of being used over
1382            other vars */
1383         step = ast_for_expr(c, ch);
1384         if (!step)
1385             return NULL;
1386
1387         return Index(step, c->c_arena);
1388     }
1389
1390     if (TYPE(ch) == test) {
1391         lower = ast_for_expr(c, ch);
1392         if (!lower)
1393             return NULL;
1394     }
1395
1396     /* If there's an upper bound it's in the second or third position. */
1397     if (TYPE(ch) == COLON) {
1398         if (NCH(n) > 1) {
1399             node *n2 = CHILD(n, 1);
1400
1401             if (TYPE(n2) == test) {
1402                 upper = ast_for_expr(c, n2);
1403                 if (!upper)
1404                     return NULL;
1405             }
1406         }
1407     } else if (NCH(n) > 2) {
1408         node *n2 = CHILD(n, 2);
1409
1410         if (TYPE(n2) == test) {
1411             upper = ast_for_expr(c, n2);
1412             if (!upper)
1413                 return NULL;
1414         }
1415     }
1416
1417     ch = CHILD(n, NCH(n) - 1);
1418     if (TYPE(ch) == sliceop) {
1419         if (NCH(ch) == 1) {
1420             /* No expression, so step is None */
1421             ch = CHILD(ch, 0);
1422             step = Name(new_identifier("None", c->c_arena), Load,
1423                         LINENO(ch), ch->n_col_offset, c->c_arena);
1424             if (!step)
1425                 return NULL;
1426         } else {
1427             ch = CHILD(ch, 1);
1428             if (TYPE(ch) == test) {
1429                 step = ast_for_expr(c, ch);
1430                 if (!step)
1431                     return NULL;
1432             }
1433         }
1434     }
1435
1436     return Slice(lower, upper, step, c->c_arena);
1437 }
1438
1439 static expr_ty
1440 ast_for_binop(struct compiling *c, const node *n)
1441 {
1442         /* Must account for a sequence of expressions.
1443            How should A op B op C by represented?
1444            BinOp(BinOp(A, op, B), op, C).
1445         */
1446
1447         int i, nops;
1448         expr_ty expr1, expr2, result;
1449         operator_ty newoperator;
1450
1451         expr1 = ast_for_expr(c, CHILD(n, 0));
1452         if (!expr1)
1453             return NULL;
1454
1455         expr2 = ast_for_expr(c, CHILD(n, 2));
1456         if (!expr2)
1457             return NULL;
1458
1459         newoperator = get_operator(CHILD(n, 1));
1460         if (!newoperator)
1461             return NULL;
1462
1463         result = BinOp(expr1, newoperator, expr2, LINENO(n), n->n_col_offset,
1464                        c->c_arena);
1465         if (!result)
1466             return NULL;
1467
1468         nops = (NCH(n) - 1) / 2;
1469         for (i = 1; i < nops; i++) {
1470                 expr_ty tmp_result, tmp;
1471                 const node* next_oper = CHILD(n, i * 2 + 1);
1472
1473                 newoperator = get_operator(next_oper);
1474                 if (!newoperator)
1475                     return NULL;
1476
1477                 tmp = ast_for_expr(c, CHILD(n, i * 2 + 2));
1478                 if (!tmp)
1479                     return NULL;
1480
1481                 tmp_result = BinOp(result, newoperator, tmp,
1482                                    LINENO(next_oper), next_oper->n_col_offset,
1483                                    c->c_arena);
1484                 if (!tmp_result)
1485                         return NULL;
1486                 result = tmp_result;
1487         }
1488         return result;
1489 }
1490
1491 static expr_ty
1492 ast_for_trailer(struct compiling *c, const node *n, expr_ty left_expr)
1493 {
1494     /* trailer: '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME
1495        subscriptlist: subscript (',' subscript)* [',']
1496        subscript: '.' '.' '.' | test | [test] ':' [test] [sliceop]
1497      */
1498     REQ(n, trailer);
1499     if (TYPE(CHILD(n, 0)) == LPAR) {
1500         if (NCH(n) == 2)
1501             return Call(left_expr, NULL, NULL, NULL, NULL, LINENO(n),
1502                         n->n_col_offset, c->c_arena);
1503         else
1504             return ast_for_call(c, CHILD(n, 1), left_expr);
1505     }
1506     else if (TYPE(CHILD(n, 0)) == DOT ) {
1507         return Attribute(left_expr, NEW_IDENTIFIER(CHILD(n, 1)), Load,
1508                          LINENO(n), n->n_col_offset, c->c_arena);
1509     }
1510     else {
1511         REQ(CHILD(n, 0), LSQB);
1512         REQ(CHILD(n, 2), RSQB);
1513         n = CHILD(n, 1);
1514         if (NCH(n) == 1) {
1515             slice_ty slc = ast_for_slice(c, CHILD(n, 0));
1516             if (!slc)
1517                 return NULL;
1518             return Subscript(left_expr, slc, Load, LINENO(n), n->n_col_offset,
1519                              c->c_arena);
1520         }
1521         else {
1522             /* The grammar is ambiguous here. The ambiguity is resolved
1523                by treating the sequence as a tuple literal if there are
1524                no slice features.
1525             */
1526             int j;
1527             slice_ty slc;
1528             expr_ty e;
1529             bool simple = true;
1530             asdl_seq *slices, *elts;
1531             slices = asdl_seq_new((NCH(n) + 1) / 2, c->c_arena);
1532             if (!slices)
1533                 return NULL;
1534             for (j = 0; j < NCH(n); j += 2) {
1535                 slc = ast_for_slice(c, CHILD(n, j));
1536                 if (!slc)
1537                     return NULL;
1538                 if (slc->kind != Index_kind)
1539                     simple = false;
1540                 asdl_seq_SET(slices, j / 2, slc);
1541             }
1542             if (!simple) {
1543                 return Subscript(left_expr, ExtSlice(slices, c->c_arena),
1544                                  Load, LINENO(n), n->n_col_offset, c->c_arena);
1545             }
1546             /* extract Index values and put them in a Tuple */
1547             elts = asdl_seq_new(asdl_seq_LEN(slices), c->c_arena);
1548             if (!elts)
1549                 return NULL;
1550             for (j = 0; j < asdl_seq_LEN(slices); ++j) {
1551                 slc = (slice_ty)asdl_seq_GET(slices, j);
1552                 assert(slc->kind == Index_kind  && slc->v.Index.value);
1553                 asdl_seq_SET(elts, j, slc->v.Index.value);
1554             }
1555             e = Tuple(elts, Load, LINENO(n), n->n_col_offset, c->c_arena);
1556             if (!e)
1557                 return NULL;
1558             return Subscript(left_expr, Index(e, c->c_arena),
1559                              Load, LINENO(n), n->n_col_offset, c->c_arena);
1560         }
1561     }
1562 }
1563
1564 static expr_ty
1565 ast_for_factor(struct compiling *c, const node *n)
1566 {
1567     node *pfactor, *ppower, *patom, *pnum;
1568     expr_ty expression;
1569
1570     /* If the unary - operator is applied to a constant, don't generate
1571        a UNARY_NEGATIVE opcode.  Just store the approriate value as a
1572        constant.  The peephole optimizer already does something like
1573        this but it doesn't handle the case where the constant is
1574        (sys.maxint - 1).  In that case, we want a PyIntObject, not a
1575        PyLongObject.
1576     */
1577     if (TYPE(CHILD(n, 0)) == MINUS &&
1578         NCH(n) == 2 &&
1579         TYPE((pfactor = CHILD(n, 1))) == factor &&
1580         NCH(pfactor) == 1 &&
1581         TYPE((ppower = CHILD(pfactor, 0))) == power &&
1582         NCH(ppower) == 1 &&
1583         TYPE((patom = CHILD(ppower, 0))) == atom &&
1584         TYPE((pnum = CHILD(patom, 0))) == NUMBER) {
1585         char *s = PyObject_MALLOC(strlen(STR(pnum)) + 2);
1586         if (s == NULL)
1587             return NULL;
1588         s[0] = '-';
1589         strcpy(s + 1, STR(pnum));
1590         PyObject_FREE(STR(pnum));
1591         STR(pnum) = s;
1592         return ast_for_atom(c, patom);
1593     }
1594
1595     expression = ast_for_expr(c, CHILD(n, 1));
1596     if (!expression)
1597         return NULL;
1598
1599     switch (TYPE(CHILD(n, 0))) {
1600         case PLUS:
1601             return UnaryOp(UAdd, expression, LINENO(n), n->n_col_offset,
1602                            c->c_arena);
1603         case MINUS:
1604             return UnaryOp(USub, expression, LINENO(n), n->n_col_offset,
1605                            c->c_arena);
1606         case TILDE:
1607             return UnaryOp(Invert, expression, LINENO(n),
1608                            n->n_col_offset, c->c_arena);
1609     }
1610     PyErr_Format(PyExc_SystemError, "unhandled factor: %d",
1611                  TYPE(CHILD(n, 0)));
1612     return NULL;
1613 }
1614
1615 static expr_ty
1616 ast_for_power(struct compiling *c, const node *n)
1617 {
1618     /* power: atom trailer* ('**' factor)*
1619      */
1620     int i;
1621     expr_ty e, tmp;
1622     REQ(n, power);
1623     e = ast_for_atom(c, CHILD(n, 0));
1624     if (!e)
1625         return NULL;
1626     if (NCH(n) == 1)
1627         return e;
1628     for (i = 1; i < NCH(n); i++) {
1629         node *ch = CHILD(n, i);
1630         if (TYPE(ch) != trailer)
1631             break;
1632         tmp = ast_for_trailer(c, ch, e);
1633         if (!tmp)
1634             return NULL;
1635         tmp->lineno = e->lineno;
1636         tmp->col_offset = e->col_offset;
1637         e = tmp;
1638     }
1639     if (TYPE(CHILD(n, NCH(n) - 1)) == factor) {
1640         expr_ty f = ast_for_expr(c, CHILD(n, NCH(n) - 1));
1641         if (!f)
1642             return NULL;
1643         tmp = BinOp(e, Pow, f, LINENO(n), n->n_col_offset, c->c_arena);
1644         if (!tmp)
1645             return NULL;
1646         e = tmp;
1647     }
1648     return e;
1649 }
1650
1651 /* Do not name a variable 'expr'!  Will cause a compile error.
1652 */
1653
1654 static expr_ty
1655 ast_for_expr(struct compiling *c, const node *n)
1656 {
1657     /* handle the full range of simple expressions
1658        test: or_test ['if' or_test 'else' test] | lambdef
1659        or_test: and_test ('or' and_test)*
1660        and_test: not_test ('and' not_test)*
1661        not_test: 'not' not_test | comparison
1662        comparison: expr (comp_op expr)*
1663        expr: xor_expr ('|' xor_expr)*
1664        xor_expr: and_expr ('^' and_expr)*
1665        and_expr: shift_expr ('&' shift_expr)*
1666        shift_expr: arith_expr (('<<'|'>>') arith_expr)*
1667        arith_expr: term (('+'|'-') term)*
1668        term: factor (('*'|'/'|'%'|'//') factor)*
1669        factor: ('+'|'-'|'~') factor | power
1670        power: atom trailer* ('**' factor)*
1671
1672        As well as modified versions that exist for backward compatibility,
1673        to explicitly allow:
1674        [ x for x in lambda: 0, lambda: 1 ]
1675        (which would be ambiguous without these extra rules)
1676
1677        old_test: or_test | old_lambdef
1678        old_lambdef: 'lambda' [vararglist] ':' old_test
1679
1680     */
1681
1682     asdl_seq *seq;
1683     int i;
1684
1685  loop:
1686     switch (TYPE(n)) {
1687         case test:
1688         case old_test:
1689             if (TYPE(CHILD(n, 0)) == lambdef ||
1690                 TYPE(CHILD(n, 0)) == old_lambdef)
1691                 return ast_for_lambdef(c, CHILD(n, 0));
1692             else if (NCH(n) > 1)
1693                 return ast_for_ifexpr(c, n);
1694             /* Fallthrough */
1695         case or_test:
1696         case and_test:
1697             if (NCH(n) == 1) {
1698                 n = CHILD(n, 0);
1699                 goto loop;
1700             }
1701             seq = asdl_seq_new((NCH(n) + 1) / 2, c->c_arena);
1702             if (!seq)
1703                 return NULL;
1704             for (i = 0; i < NCH(n); i += 2) {
1705                 expr_ty e = ast_for_expr(c, CHILD(n, i));
1706                 if (!e)
1707                     return NULL;
1708                 asdl_seq_SET(seq, i / 2, e);
1709             }
1710             if (!strcmp(STR(CHILD(n, 1)), "and"))
1711                 return BoolOp(And, seq, LINENO(n), n->n_col_offset,
1712                               c->c_arena);
1713             assert(!strcmp(STR(CHILD(n, 1)), "or"));
1714             return BoolOp(Or, seq, LINENO(n), n->n_col_offset, c->c_arena);
1715         case not_test:
1716             if (NCH(n) == 1) {
1717                 n = CHILD(n, 0);
1718                 goto loop;
1719             }
1720             else {
1721                 expr_ty expression = ast_for_expr(c, CHILD(n, 1));
1722                 if (!expression)
1723                     return NULL;
1724
1725                 return UnaryOp(Not, expression, LINENO(n), n->n_col_offset,
1726                                c->c_arena);
1727             }
1728         case comparison:
1729             if (NCH(n) == 1) {
1730                 n = CHILD(n, 0);
1731                 goto loop;
1732             }
1733             else {
1734                 expr_ty expression;
1735                 asdl_int_seq *ops;
1736                 asdl_seq *cmps;
1737                 ops = asdl_int_seq_new(NCH(n) / 2, c->c_arena);
1738                 if (!ops)
1739                     return NULL;
1740                 cmps = asdl_seq_new(NCH(n) / 2, c->c_arena);
1741                 if (!cmps) {
1742                     return NULL;
1743                 }
1744                 for (i = 1; i < NCH(n); i += 2) {
1745                     cmpop_ty newoperator;
1746
1747                     newoperator = ast_for_comp_op(CHILD(n, i));
1748                     if (!newoperator) {
1749                         return NULL;
1750                     }
1751
1752                     expression = ast_for_expr(c, CHILD(n, i + 1));
1753                     if (!expression) {
1754                         return NULL;
1755                     }
1756
1757                     asdl_seq_SET(ops, i / 2, newoperator);
1758                     asdl_seq_SET(cmps, i / 2, expression);
1759                 }
1760                 expression = ast_for_expr(c, CHILD(n, 0));
1761                 if (!expression) {
1762                     return NULL;
1763                 }
1764
1765                 return Compare(expression, ops, cmps, LINENO(n),
1766                                n->n_col_offset, c->c_arena);
1767             }
1768             break;
1769
1770         /* The next five cases all handle BinOps.  The main body of code
1771            is the same in each case, but the switch turned inside out to
1772            reuse the code for each type of operator.
1773          */
1774         case expr:
1775         case xor_expr:
1776         case and_expr:
1777         case shift_expr:
1778         case arith_expr:
1779         case term:
1780             if (NCH(n) == 1) {
1781                 n = CHILD(n, 0);
1782                 goto loop;
1783             }
1784             return ast_for_binop(c, n);
1785         case yield_expr: {
1786             expr_ty exp = NULL;
1787             if (NCH(n) == 2) {
1788                 exp = ast_for_testlist(c, CHILD(n, 1));
1789                 if (!exp)
1790                     return NULL;
1791             }
1792             return Yield(exp, LINENO(n), n->n_col_offset, c->c_arena);
1793         }
1794         case factor:
1795             if (NCH(n) == 1) {
1796                 n = CHILD(n, 0);
1797                 goto loop;
1798             }
1799             return ast_for_factor(c, n);
1800         case power:
1801             return ast_for_power(c, n);
1802         default:
1803             PyErr_Format(PyExc_SystemError, "unhandled expr: %d", TYPE(n));
1804             return NULL;
1805     }
1806     /* should never get here unless if error is set */
1807     return NULL;
1808 }
1809
1810 static expr_ty
1811 ast_for_call(struct compiling *c, const node *n, expr_ty func)
1812 {
1813     /*
1814       arglist: (argument ',')* (argument [',']| '*' test [',' '**' test]
1815                | '**' test)
1816       argument: [test '='] test [gen_for]        # Really [keyword '='] test
1817     */
1818
1819     int i, nargs, nkeywords, ngens;
1820     asdl_seq *args;
1821     asdl_seq *keywords;
1822     expr_ty vararg = NULL, kwarg = NULL;
1823
1824     REQ(n, arglist);
1825
1826     nargs = 0;
1827     nkeywords = 0;
1828     ngens = 0;
1829     for (i = 0; i < NCH(n); i++) {
1830         node *ch = CHILD(n, i);
1831         if (TYPE(ch) == argument) {
1832             if (NCH(ch) == 1)
1833                 nargs++;
1834             else if (TYPE(CHILD(ch, 1)) == gen_for)
1835                 ngens++;
1836             else
1837                 nkeywords++;
1838         }
1839     }
1840     if (ngens > 1 || (ngens && (nargs || nkeywords))) {
1841         ast_error(n, "Generator expression must be parenthesized "
1842                   "if not sole argument");
1843         return NULL;
1844     }
1845
1846     if (nargs + nkeywords + ngens > 255) {
1847       ast_error(n, "more than 255 arguments");
1848       return NULL;
1849     }
1850
1851     args = asdl_seq_new(nargs + ngens, c->c_arena);
1852     if (!args)
1853         return NULL;
1854     keywords = asdl_seq_new(nkeywords, c->c_arena);
1855     if (!keywords)
1856         return NULL;
1857     nargs = 0;
1858     nkeywords = 0;
1859     for (i = 0; i < NCH(n); i++) {
1860         node *ch = CHILD(n, i);
1861         if (TYPE(ch) == argument) {
1862             expr_ty e;
1863             if (NCH(ch) == 1) {
1864                 if (nkeywords) {
1865                     ast_error(CHILD(ch, 0),
1866                               "non-keyword arg after keyword arg");
1867                     return NULL;
1868                 }
1869                 e = ast_for_expr(c, CHILD(ch, 0));
1870                 if (!e)
1871                     return NULL;
1872                 asdl_seq_SET(args, nargs++, e);
1873             }
1874             else if (TYPE(CHILD(ch, 1)) == gen_for) {
1875                 e = ast_for_genexp(c, ch);
1876                 if (!e)
1877                     return NULL;
1878                 asdl_seq_SET(args, nargs++, e);
1879             }
1880             else {
1881                 keyword_ty kw;
1882                 identifier key;
1883
1884                 /* CHILD(ch, 0) is test, but must be an identifier? */
1885                 e = ast_for_expr(c, CHILD(ch, 0));
1886                 if (!e)
1887                     return NULL;
1888                 /* f(lambda x: x[0] = 3) ends up getting parsed with
1889                  * LHS test = lambda x: x[0], and RHS test = 3.
1890                  * SF bug 132313 points out that complaining about a keyword
1891                  * then is very confusing.
1892                  */
1893                 if (e->kind == Lambda_kind) {
1894                     ast_error(CHILD(ch, 0),
1895                               "lambda cannot contain assignment");
1896                     return NULL;
1897                 } else if (e->kind != Name_kind) {
1898                     ast_error(CHILD(ch, 0), "keyword can't be an expression");
1899                     return NULL;
1900                 }
1901                 key = e->v.Name.id;
1902                 if (!strcmp(PyString_AS_STRING(key), "None")) {
1903                     ast_error(CHILD(ch, 0), "assignment to None");
1904                     return NULL;
1905                 }
1906                 e = ast_for_expr(c, CHILD(ch, 2));
1907                 if (!e)
1908                     return NULL;
1909                 kw = keyword(key, e, c->c_arena);
1910                 if (!kw)
1911                     return NULL;
1912                 asdl_seq_SET(keywords, nkeywords++, kw);
1913             }
1914         }
1915         else if (TYPE(ch) == STAR) {
1916             vararg = ast_for_expr(c, CHILD(n, i+1));
1917             i++;
1918         }
1919         else if (TYPE(ch) == DOUBLESTAR) {
1920             kwarg = ast_for_expr(c, CHILD(n, i+1));
1921             i++;
1922         }
1923     }
1924
1925     return Call(func, args, keywords, vararg, kwarg, func->lineno,
1926                 func->col_offset, c->c_arena);
1927 }
1928
1929 static expr_ty
1930 ast_for_testlist(struct compiling *c, const node* n)
1931 {
1932     /* testlist_gexp: test (',' test)* [','] */
1933     /* testlist: test (',' test)* [','] */
1934     /* testlist_safe: test (',' test)+ [','] */
1935     /* testlist1: test (',' test)* */
1936     assert(NCH(n) > 0);
1937     if (TYPE(n) == testlist_gexp) {
1938         if (NCH(n) > 1)
1939             assert(TYPE(CHILD(n, 1)) != gen_for);
1940     }
1941     else {
1942         assert(TYPE(n) == testlist ||
1943                TYPE(n) == testlist_safe ||
1944                TYPE(n) == testlist1);
1945     }
1946     if (NCH(n) == 1)
1947         return ast_for_expr(c, CHILD(n, 0));
1948     else {
1949         asdl_seq *tmp = seq_for_testlist(c, n);
1950         if (!tmp)
1951             return NULL;
1952         return Tuple(tmp, Load, LINENO(n), n->n_col_offset, c->c_arena);
1953     }
1954 }
1955
1956 static expr_ty
1957 ast_for_testlist_gexp(struct compiling *c, const node* n)
1958 {
1959     /* testlist_gexp: test ( gen_for | (',' test)* [','] ) */
1960     /* argument: test [ gen_for ] */
1961     assert(TYPE(n) == testlist_gexp || TYPE(n) == argument);
1962     if (NCH(n) > 1 && TYPE(CHILD(n, 1)) == gen_for)
1963         return ast_for_genexp(c, n);
1964     return ast_for_testlist(c, n);
1965 }
1966
1967 /* like ast_for_testlist() but returns a sequence */
1968 static asdl_seq*
1969 ast_for_class_bases(struct compiling *c, const node* n)
1970 {
1971     /* testlist: test (',' test)* [','] */
1972     assert(NCH(n) > 0);
1973     REQ(n, testlist);
1974     if (NCH(n) == 1) {
1975         expr_ty base;
1976         asdl_seq *bases = asdl_seq_new(1, c->c_arena);
1977         if (!bases)
1978             return NULL;
1979         base = ast_for_expr(c, CHILD(n, 0));
1980         if (!base)
1981             return NULL;
1982         asdl_seq_SET(bases, 0, base);
1983         return bases;
1984     }
1985
1986     return seq_for_testlist(c, n);
1987 }
1988
1989 static stmt_ty
1990 ast_for_expr_stmt(struct compiling *c, const node *n)
1991 {
1992     REQ(n, expr_stmt);
1993     /* expr_stmt: testlist (augassign (yield_expr|testlist)
1994                 | ('=' (yield_expr|testlist))*)
1995        testlist: test (',' test)* [',']
1996        augassign: '+=' | '-=' | '*=' | '/=' | '%=' | '&=' | '|=' | '^='
1997                 | '<<=' | '>>=' | '**=' | '//='
1998        test: ... here starts the operator precendence dance
1999      */
2000
2001     if (NCH(n) == 1) {
2002         expr_ty e = ast_for_testlist(c, CHILD(n, 0));
2003         if (!e)
2004             return NULL;
2005
2006         return Expr(e, LINENO(n), n->n_col_offset, c->c_arena);
2007     }
2008     else if (TYPE(CHILD(n, 1)) == augassign) {
2009         expr_ty expr1, expr2;
2010         operator_ty newoperator;
2011         node *ch = CHILD(n, 0);
2012
2013         expr1 = ast_for_testlist(c, ch);
2014         if (!expr1)
2015             return NULL;
2016         /* TODO(nas): Remove duplicated error checks (set_context does it) */
2017         switch (expr1->kind) {
2018             case GeneratorExp_kind:
2019                 ast_error(ch, "augmented assignment to generator "
2020                           "expression not possible");
2021                 return NULL;
2022             case Yield_kind:
2023                 ast_error(ch, "augmented assignment to yield "
2024                           "expression not possible");
2025                 return NULL;
2026             case Name_kind: {
2027                 const char *var_name = PyString_AS_STRING(expr1->v.Name.id);
2028                 if (var_name[0] == 'N' && !strcmp(var_name, "None")) {
2029                     ast_error(ch, "assignment to None");
2030                     return NULL;
2031                 }
2032                 break;
2033             }
2034             case Attribute_kind:
2035             case Subscript_kind:
2036                 break;
2037             default:
2038                 ast_error(ch, "illegal expression for augmented "
2039                           "assignment");
2040                 return NULL;
2041         }
2042         if(!set_context(expr1, Store, ch))
2043             return NULL;
2044
2045         ch = CHILD(n, 2);
2046         if (TYPE(ch) == testlist)
2047             expr2 = ast_for_testlist(c, ch);
2048         else
2049             expr2 = ast_for_expr(c, ch);
2050         if (!expr2)
2051             return NULL;
2052
2053         newoperator = ast_for_augassign(CHILD(n, 1));
2054         if (!newoperator)
2055             return NULL;
2056
2057         return AugAssign(expr1, newoperator, expr2, LINENO(n), n->n_col_offset,
2058                          c->c_arena);
2059     }
2060     else {
2061         int i;
2062         asdl_seq *targets;
2063         node *value;
2064         expr_ty expression;
2065
2066         /* a normal assignment */
2067         REQ(CHILD(n, 1), EQUAL);
2068         targets = asdl_seq_new(NCH(n) / 2, c->c_arena);
2069         if (!targets)
2070             return NULL;
2071         for (i = 0; i < NCH(n) - 2; i += 2) {
2072             expr_ty e;
2073             node *ch = CHILD(n, i);
2074             if (TYPE(ch) == yield_expr) {
2075                 ast_error(ch, "assignment to yield expression not possible");
2076                 return NULL;
2077             }
2078             e = ast_for_testlist(c, ch);
2079
2080             /* set context to assign */
2081             if (!e)
2082                 return NULL;
2083
2084             if (!set_context(e, Store, CHILD(n, i)))
2085                 return NULL;
2086
2087             asdl_seq_SET(targets, i / 2, e);
2088         }
2089         value = CHILD(n, NCH(n) - 1);
2090         if (TYPE(value) == testlist)
2091             expression = ast_for_testlist(c, value);
2092         else
2093             expression = ast_for_expr(c, value);
2094         if (!expression)
2095             return NULL;
2096         return Assign(targets, expression, LINENO(n), n->n_col_offset,
2097                       c->c_arena);
2098     }
2099 }
2100
2101 static stmt_ty
2102 ast_for_print_stmt(struct compiling *c, const node *n)
2103 {
2104     /* print_stmt: 'print' ( [ test (',' test)* [','] ]
2105                              | '>>' test [ (',' test)+ [','] ] )
2106      */
2107     expr_ty dest = NULL, expression;
2108     asdl_seq *seq;
2109     bool nl;
2110     int i, j, start = 1;
2111
2112     REQ(n, print_stmt);
2113     if (NCH(n) >= 2 && TYPE(CHILD(n, 1)) == RIGHTSHIFT) {
2114         dest = ast_for_expr(c, CHILD(n, 2));
2115         if (!dest)
2116             return NULL;
2117             start = 4;
2118     }
2119     seq = asdl_seq_new((NCH(n) + 1 - start) / 2, c->c_arena);
2120     if (!seq)
2121         return NULL;
2122     for (i = start, j = 0; i < NCH(n); i += 2, ++j) {
2123         expression = ast_for_expr(c, CHILD(n, i));
2124         if (!expression)
2125             return NULL;
2126         asdl_seq_SET(seq, j, expression);
2127     }
2128     nl = (TYPE(CHILD(n, NCH(n) - 1)) == COMMA) ? false : true;
2129     return Print(dest, seq, nl, LINENO(n), n->n_col_offset, c->c_arena);
2130 }
2131
2132 static asdl_seq *
2133 ast_for_exprlist(struct compiling *c, const node *n, expr_context_ty context)
2134 {
2135     asdl_seq *seq;
2136     int i;
2137     expr_ty e;
2138
2139     REQ(n, exprlist);
2140
2141     seq = asdl_seq_new((NCH(n) + 1) / 2, c->c_arena);
2142     if (!seq)
2143         return NULL;
2144     for (i = 0; i < NCH(n); i += 2) {
2145         e = ast_for_expr(c, CHILD(n, i));
2146         if (!e)
2147             return NULL;
2148         asdl_seq_SET(seq, i / 2, e);
2149         if (context && !set_context(e, context, CHILD(n, i)))
2150             return NULL;
2151     }
2152     return seq;
2153 }
2154
2155 static stmt_ty
2156 ast_for_del_stmt(struct compiling *c, const node *n)
2157 {
2158     asdl_seq *expr_list;
2159
2160     /* del_stmt: 'del' exprlist */
2161     REQ(n, del_stmt);
2162
2163     expr_list = ast_for_exprlist(c, CHILD(n, 1), Del);
2164     if (!expr_list)
2165         return NULL;
2166     return Delete(expr_list, LINENO(n), n->n_col_offset, c->c_arena);
2167 }
2168
2169 static stmt_ty
2170 ast_for_flow_stmt(struct compiling *c, const node *n)
2171 {
2172     /*
2173       flow_stmt: break_stmt | continue_stmt | return_stmt | raise_stmt
2174                  | yield_stmt
2175       break_stmt: 'break'
2176       continue_stmt: 'continue'
2177       return_stmt: 'return' [testlist]
2178       yield_stmt: yield_expr
2179       yield_expr: 'yield' testlist
2180       raise_stmt: 'raise' [test [',' test [',' test]]]
2181     */
2182     node *ch;
2183
2184     REQ(n, flow_stmt);
2185     ch = CHILD(n, 0);
2186     switch (TYPE(ch)) {
2187         case break_stmt:
2188             return Break(LINENO(n), n->n_col_offset, c->c_arena);
2189         case continue_stmt:
2190             return Continue(LINENO(n), n->n_col_offset, c->c_arena);
2191         case yield_stmt: { /* will reduce to yield_expr */
2192             expr_ty exp = ast_for_expr(c, CHILD(ch, 0));
2193             if (!exp)
2194                 return NULL;
2195             return Expr(exp, LINENO(n), n->n_col_offset, c->c_arena);
2196         }
2197         case return_stmt:
2198             if (NCH(ch) == 1)
2199                 return Return(NULL, LINENO(n), n->n_col_offset, c->c_arena);
2200             else {
2201                 expr_ty expression = ast_for_testlist(c, CHILD(ch, 1));
2202                 if (!expression)
2203                     return NULL;
2204                 return Return(expression, LINENO(n), n->n_col_offset,
2205                               c->c_arena);
2206             }
2207         case raise_stmt:
2208             if (NCH(ch) == 1)
2209                 return Raise(NULL, NULL, NULL, LINENO(n), n->n_col_offset,
2210                              c->c_arena);
2211             else if (NCH(ch) == 2) {
2212                 expr_ty expression = ast_for_expr(c, CHILD(ch, 1));
2213                 if (!expression)
2214                     return NULL;
2215                 return Raise(expression, NULL, NULL, LINENO(n),
2216                              n->n_col_offset, c->c_arena);
2217             }
2218             else if (NCH(ch) == 4) {
2219                 expr_ty expr1, expr2;
2220
2221                 expr1 = ast_for_expr(c, CHILD(ch, 1));
2222                 if (!expr1)
2223                     return NULL;
2224                 expr2 = ast_for_expr(c, CHILD(ch, 3));
2225                 if (!expr2)
2226                     return NULL;
2227
2228                 return Raise(expr1, expr2, NULL, LINENO(n), n->n_col_offset,
2229                              c->c_arena);
2230             }
2231             else if (NCH(ch) == 6) {
2232                 expr_ty expr1, expr2, expr3;
2233
2234                 expr1 = ast_for_expr(c, CHILD(ch, 1));
2235                 if (!expr1)
2236                     return NULL;
2237                 expr2 = ast_for_expr(c, CHILD(ch, 3));
2238                 if (!expr2)
2239                     return NULL;
2240                 expr3 = ast_for_expr(c, CHILD(ch, 5));
2241                 if (!expr3)
2242                     return NULL;
2243
2244                 return Raise(expr1, expr2, expr3, LINENO(n), n->n_col_offset,
2245                              c->c_arena);
2246             }
2247         default:
2248             PyErr_Format(PyExc_SystemError,
2249                          "unexpected flow_stmt: %d", TYPE(ch));
2250             return NULL;
2251     }
2252
2253     PyErr_SetString(PyExc_SystemError, "unhandled flow statement");
2254     return NULL;
2255 }
2256
2257 static alias_ty
2258 alias_for_import_name(struct compiling *c, const node *n)
2259 {
2260     /*
2261       import_as_name: NAME ['as' NAME]
2262       dotted_as_name: dotted_name ['as' NAME]
2263       dotted_name: NAME ('.' NAME)*
2264     */
2265     PyObject *str;
2266
2267  loop:
2268     switch (TYPE(n)) {
2269         case import_as_name:
2270             str = NULL;
2271             if (NCH(n) == 3) {
2272                 str = NEW_IDENTIFIER(CHILD(n, 2));
2273             }
2274             return alias(NEW_IDENTIFIER(CHILD(n, 0)), str, c->c_arena);
2275         case dotted_as_name:
2276             if (NCH(n) == 1) {
2277                 n = CHILD(n, 0);
2278                 goto loop;
2279             }
2280             else {
2281                 alias_ty a = alias_for_import_name(c, CHILD(n, 0));
2282                 if (!a)
2283                     return NULL;
2284                 assert(!a->asname);
2285                 a->asname = NEW_IDENTIFIER(CHILD(n, 2));
2286                 return a;
2287             }
2288             break;
2289         case dotted_name:
2290             if (NCH(n) == 1)
2291                 return alias(NEW_IDENTIFIER(CHILD(n, 0)), NULL, c->c_arena);
2292             else {
2293                 /* Create a string of the form "a.b.c" */
2294                 int i;
2295                 size_t len;
2296                 char *s;
2297
2298                 len = 0;
2299                 for (i = 0; i < NCH(n); i += 2)
2300                     /* length of string plus one for the dot */
2301                     len += strlen(STR(CHILD(n, i))) + 1;
2302                 len--; /* the last name doesn't have a dot */
2303                 str = PyString_FromStringAndSize(NULL, len);
2304                 if (!str)
2305                     return NULL;
2306                 s = PyString_AS_STRING(str);
2307                 if (!s)
2308                     return NULL;
2309                 for (i = 0; i < NCH(n); i += 2) {
2310                     char *sch = STR(CHILD(n, i));
2311                     strcpy(s, STR(CHILD(n, i)));
2312                     s += strlen(sch);
2313                     *s++ = '.';
2314                 }
2315                 --s;
2316                 *s = '\0';
2317                 PyString_InternInPlace(&str);
2318                 PyArena_AddPyObject(c->c_arena, str);
2319                 return alias(str, NULL, c->c_arena);
2320             }
2321             break;
2322         case STAR:
2323             str = PyString_InternFromString("*");
2324             PyArena_AddPyObject(c->c_arena, str);
2325             return alias(str, NULL, c->c_arena);
2326         default:
2327             PyErr_Format(PyExc_SystemError,
2328                          "unexpected import name: %d", TYPE(n));
2329             return NULL;
2330     }
2331
2332     PyErr_SetString(PyExc_SystemError, "unhandled import name condition");
2333     return NULL;
2334 }
2335
2336 static stmt_ty
2337 ast_for_import_stmt(struct compiling *c, const node *n)
2338 {
2339     /*
2340       import_stmt: import_name | import_from
2341       import_name: 'import' dotted_as_names
2342       import_from: 'from' ('.'* dotted_name | '.') 'import'
2343                           ('*' | '(' import_as_names ')' | import_as_names)
2344     */
2345     int lineno;
2346     int col_offset;
2347     int i;
2348     asdl_seq *aliases;
2349
2350     REQ(n, import_stmt);
2351     lineno = LINENO(n);
2352     col_offset = n->n_col_offset;
2353     n = CHILD(n, 0);
2354     if (TYPE(n) == import_name) {
2355         n = CHILD(n, 1);
2356         REQ(n, dotted_as_names);
2357         aliases = asdl_seq_new((NCH(n) + 1) / 2, c->c_arena);
2358         if (!aliases)
2359             return NULL;
2360         for (i = 0; i < NCH(n); i += 2) {
2361             alias_ty import_alias = alias_for_import_name(c, CHILD(n, i));
2362             if (!import_alias)
2363                 return NULL;
2364             asdl_seq_SET(aliases, i / 2, import_alias);
2365         }
2366         return Import(aliases, lineno, col_offset, c->c_arena);
2367     }
2368     else if (TYPE(n) == import_from) {
2369         int n_children;
2370         int idx, ndots = 0;
2371         alias_ty mod = NULL;
2372         identifier modname;
2373
2374        /* Count the number of dots (for relative imports) and check for the
2375           optional module name */
2376         for (idx = 1; idx < NCH(n); idx++) {
2377             if (TYPE(CHILD(n, idx)) == dotted_name) {
2378                 mod = alias_for_import_name(c, CHILD(n, idx));
2379                 idx++;
2380                 break;
2381             } else if (TYPE(CHILD(n, idx)) != DOT) {
2382                 break;
2383             }
2384             ndots++;
2385         }
2386         idx++; /* skip over the 'import' keyword */
2387         switch (TYPE(CHILD(n, idx))) {
2388         case STAR:
2389             /* from ... import * */
2390             n = CHILD(n, idx);
2391             n_children = 1;
2392             if (ndots) {
2393                 ast_error(n, "'import *' not allowed with 'from .'");
2394                 return NULL;
2395             }
2396             break;
2397         case LPAR:
2398             /* from ... import (x, y, z) */
2399             n = CHILD(n, idx + 1);
2400             n_children = NCH(n);
2401             break;
2402         case import_as_names:
2403             /* from ... import x, y, z */
2404             n = CHILD(n, idx);
2405             n_children = NCH(n);
2406             if (n_children % 2 == 0) {
2407                 ast_error(n, "trailing comma not allowed without"
2408                              " surrounding parentheses");
2409                 return NULL;
2410             }
2411             break;
2412         default:
2413             ast_error(n, "Unexpected node-type in from-import");
2414             return NULL;
2415         }
2416
2417         aliases = asdl_seq_new((n_children + 1) / 2, c->c_arena);
2418         if (!aliases)
2419             return NULL;
2420
2421         /* handle "from ... import *" special b/c there's no children */
2422         if (TYPE(n) == STAR) {
2423             alias_ty import_alias = alias_for_import_name(c, n);
2424             if (!import_alias)
2425                 return NULL;
2426                 asdl_seq_SET(aliases, 0, import_alias);
2427         }
2428         else {
2429             for (i = 0; i < NCH(n); i += 2) {
2430                 alias_ty import_alias = alias_for_import_name(c, CHILD(n, i));
2431                 if (!import_alias)
2432                     return NULL;
2433                     asdl_seq_SET(aliases, i / 2, import_alias);
2434             }
2435         }
2436         if (mod != NULL)
2437             modname = mod->name;
2438         else
2439             modname = new_identifier("", c->c_arena);
2440         return ImportFrom(modname, aliases, ndots, lineno, col_offset,
2441                           c->c_arena);
2442     }
2443     PyErr_Format(PyExc_SystemError,
2444                  "unknown import statement: starts with command '%s'",
2445                  STR(CHILD(n, 0)));
2446     return NULL;
2447 }
2448
2449 static stmt_ty
2450 ast_for_global_stmt(struct compiling *c, const node *n)
2451 {
2452     /* global_stmt: 'global' NAME (',' NAME)* */
2453     identifier name;
2454     asdl_seq *s;
2455     int i;
2456
2457     REQ(n, global_stmt);
2458     s = asdl_seq_new(NCH(n) / 2, c->c_arena);
2459     if (!s)
2460         return NULL;
2461     for (i = 1; i < NCH(n); i += 2) {
2462         name = NEW_IDENTIFIER(CHILD(n, i));
2463         if (!name)
2464             return NULL;
2465         asdl_seq_SET(s, i / 2, name);
2466     }
2467     return Global(s, LINENO(n), n->n_col_offset, c->c_arena);
2468 }
2469
2470 static stmt_ty
2471 ast_for_exec_stmt(struct compiling *c, const node *n)
2472 {
2473     expr_ty expr1, globals = NULL, locals = NULL;
2474     int n_children = NCH(n);
2475     if (n_children != 2 && n_children != 4 && n_children != 6) {
2476         PyErr_Format(PyExc_SystemError,
2477                      "poorly formed 'exec' statement: %d parts to statement",
2478                      n_children);
2479         return NULL;
2480     }
2481
2482     /* exec_stmt: 'exec' expr ['in' test [',' test]] */
2483     REQ(n, exec_stmt);
2484     expr1 = ast_for_expr(c, CHILD(n, 1));
2485     if (!expr1)
2486         return NULL;
2487     if (n_children >= 4) {
2488         globals = ast_for_expr(c, CHILD(n, 3));
2489         if (!globals)
2490             return NULL;
2491     }
2492     if (n_children == 6) {
2493         locals = ast_for_expr(c, CHILD(n, 5));
2494         if (!locals)
2495             return NULL;
2496     }
2497
2498     return Exec(expr1, globals, locals, LINENO(n), n->n_col_offset,
2499                 c->c_arena);
2500 }
2501
2502 static stmt_ty
2503 ast_for_assert_stmt(struct compiling *c, const node *n)
2504 {
2505     /* assert_stmt: 'assert' test [',' test] */
2506     REQ(n, assert_stmt);
2507     if (NCH(n) == 2) {
2508         expr_ty expression = ast_for_expr(c, CHILD(n, 1));
2509         if (!expression)
2510             return NULL;
2511         return Assert(expression, NULL, LINENO(n), n->n_col_offset,
2512                       c->c_arena);
2513     }
2514     else if (NCH(n) == 4) {
2515         expr_ty expr1, expr2;
2516
2517         expr1 = ast_for_expr(c, CHILD(n, 1));
2518         if (!expr1)
2519             return NULL;
2520         expr2 = ast_for_expr(c, CHILD(n, 3));
2521         if (!expr2)
2522             return NULL;
2523
2524         return Assert(expr1, expr2, LINENO(n), n->n_col_offset, c->c_arena);
2525     }
2526     PyErr_Format(PyExc_SystemError,
2527                  "improper number of parts to 'assert' statement: %d",
2528                  NCH(n));
2529     return NULL;
2530 }
2531
2532 static asdl_seq *
2533 ast_for_suite(struct compiling *c, const node *n)
2534 {
2535     /* suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT */
2536     asdl_seq *seq;
2537     stmt_ty s;
2538     int i, total, num, end, pos = 0;
2539     node *ch;
2540
2541     REQ(n, suite);
2542
2543     total = num_stmts(n);
2544     seq = asdl_seq_new(total, c->c_arena);
2545     if (!seq)
2546         return NULL;
2547     if (TYPE(CHILD(n, 0)) == simple_stmt) {
2548         n = CHILD(n, 0);
2549         /* simple_stmt always ends with a NEWLINE,
2550            and may have a trailing SEMI
2551         */
2552         end = NCH(n) - 1;
2553         if (TYPE(CHILD(n, end - 1)) == SEMI)
2554             end--;
2555         /* loop by 2 to skip semi-colons */
2556         for (i = 0; i < end; i += 2) {
2557             ch = CHILD(n, i);
2558             s = ast_for_stmt(c, ch);
2559             if (!s)
2560                 return NULL;
2561             asdl_seq_SET(seq, pos++, s);
2562         }
2563     }
2564     else {
2565         for (i = 2; i < (NCH(n) - 1); i++) {
2566             ch = CHILD(n, i);
2567             REQ(ch, stmt);
2568             num = num_stmts(ch);
2569             if (num == 1) {
2570                 /* small_stmt or compound_stmt with only one child */
2571                 s = ast_for_stmt(c, ch);
2572                 if (!s)
2573                     return NULL;
2574                 asdl_seq_SET(seq, pos++, s);
2575             }
2576             else {
2577                 int j;
2578                 ch = CHILD(ch, 0);
2579                 REQ(ch, simple_stmt);
2580                 for (j = 0; j < NCH(ch); j += 2) {
2581                     /* statement terminates with a semi-colon ';' */
2582                     if (NCH(CHILD(ch, j)) == 0) {
2583                         assert((j + 1) == NCH(ch));
2584                         break;
2585                     }
2586                     s = ast_for_stmt(c, CHILD(ch, j));
2587                     if (!s)
2588                         return NULL;
2589                     asdl_seq_SET(seq, pos++, s);
2590                 }
2591             }
2592         }
2593     }
2594     assert(pos == seq->size);
2595     return seq;
2596 }
2597
2598 static stmt_ty
2599 ast_for_if_stmt(struct compiling *c, const node *n)
2600 {
2601     /* if_stmt: 'if' test ':' suite ('elif' test ':' suite)*
2602        ['else' ':' suite]
2603     */
2604     char *s;
2605
2606     REQ(n, if_stmt);
2607
2608     if (NCH(n) == 4) {
2609         expr_ty expression;
2610         asdl_seq *suite_seq;
2611
2612         expression = ast_for_expr(c, CHILD(n, 1));
2613         if (!expression)
2614             return NULL;
2615         suite_seq = ast_for_suite(c, CHILD(n, 3));
2616         if (!suite_seq)
2617             return NULL;
2618
2619         return If(expression, suite_seq, NULL, LINENO(n), n->n_col_offset,
2620                   c->c_arena);
2621     }
2622
2623     s = STR(CHILD(n, 4));
2624     /* s[2], the third character in the string, will be
2625        's' for el_s_e, or
2626        'i' for el_i_f
2627     */
2628     if (s[2] == 's') {
2629         expr_ty expression;
2630         asdl_seq *seq1, *seq2;
2631
2632         expression = ast_for_expr(c, CHILD(n, 1));
2633         if (!expression)
2634             return NULL;
2635         seq1 = ast_for_suite(c, CHILD(n, 3));
2636         if (!seq1)
2637             return NULL;
2638         seq2 = ast_for_suite(c, CHILD(n, 6));
2639         if (!seq2)
2640             return NULL;
2641
2642         return If(expression, seq1, seq2, LINENO(n), n->n_col_offset,
2643                   c->c_arena);
2644     }
2645     else if (s[2] == 'i') {
2646         int i, n_elif, has_else = 0;
2647         expr_ty expression;
2648         asdl_seq *suite_seq;
2649         asdl_seq *orelse = NULL;
2650         n_elif = NCH(n) - 4;
2651         /* must reference the child n_elif+1 since 'else' token is third,
2652            not fourth, child from the end. */
2653         if (TYPE(CHILD(n, (n_elif + 1))) == NAME
2654             && STR(CHILD(n, (n_elif + 1)))[2] == 's') {
2655             has_else = 1;
2656             n_elif -= 3;
2657         }
2658         n_elif /= 4;
2659
2660         if (has_else) {
2661             asdl_seq *suite_seq2;
2662
2663             orelse = asdl_seq_new(1, c->c_arena);
2664             if (!orelse)
2665                 return NULL;
2666             expression = ast_for_expr(c, CHILD(n, NCH(n) - 6));
2667             if (!expression)
2668                 return NULL;
2669             suite_seq = ast_for_suite(c, CHILD(n, NCH(n) - 4));
2670             if (!suite_seq)
2671                 return NULL;
2672             suite_seq2 = ast_for_suite(c, CHILD(n, NCH(n) - 1));
2673             if (!suite_seq2)
2674                 return NULL;
2675
2676             asdl_seq_SET(orelse, 0,
2677                          If(expression, suite_seq, suite_seq2,
2678                             LINENO(CHILD(n, NCH(n) - 6)),
2679                             CHILD(n, NCH(n) - 6)->n_col_offset,
2680                             c->c_arena));
2681             /* the just-created orelse handled the last elif */
2682             n_elif--;
2683         }
2684
2685         for (i = 0; i < n_elif; i++) {
2686             int off = 5 + (n_elif - i - 1) * 4;
2687             asdl_seq *newobj = asdl_seq_new(1, c->c_arena);
2688             if (!newobj)
2689                 return NULL;
2690             expression = ast_for_expr(c, CHILD(n, off));
2691             if (!expression)
2692                 return NULL;
2693             suite_seq = ast_for_suite(c, CHILD(n, off + 2));
2694             if (!suite_seq)
2695                 return NULL;
2696
2697             asdl_seq_SET(newobj, 0,
2698                          If(expression, suite_seq, orelse,
2699                             LINENO(CHILD(n, off)),
2700                             CHILD(n, off)->n_col_offset, c->c_arena));
2701             orelse = newobj;
2702         }
2703         expression = ast_for_expr(c, CHILD(n, 1));
2704         if (!expression)
2705             return NULL;
2706         suite_seq = ast_for_suite(c, CHILD(n, 3));
2707         if (!suite_seq)
2708             return NULL;
2709         return If(expression, suite_seq, orelse,
2710                   LINENO(n), n->n_col_offset, c->c_arena);
2711     }
2712
2713     PyErr_Format(PyExc_SystemError,
2714                  "unexpected token in 'if' statement: %s", s);
2715     return NULL;
2716 }
2717
2718 static stmt_ty
2719 ast_for_while_stmt(struct compiling *c, const node *n)
2720 {
2721     /* while_stmt: 'while' test ':' suite ['else' ':' suite] */
2722     REQ(n, while_stmt);
2723
2724     if (NCH(n) == 4) {
2725         expr_ty expression;
2726         asdl_seq *suite_seq;
2727
2728         expression = ast_for_expr(c, CHILD(n, 1));
2729         if (!expression)
2730             return NULL;
2731         suite_seq = ast_for_suite(c, CHILD(n, 3));
2732         if (!suite_seq)
2733             return NULL;
2734         return While(expression, suite_seq, NULL, LINENO(n), n->n_col_offset,
2735                      c->c_arena);
2736     }
2737     else if (NCH(n) == 7) {
2738         expr_ty expression;
2739         asdl_seq *seq1, *seq2;
2740
2741         expression = ast_for_expr(c, CHILD(n, 1));
2742         if (!expression)
2743             return NULL;
2744         seq1 = ast_for_suite(c, CHILD(n, 3));
2745         if (!seq1)
2746             return NULL;
2747         seq2 = ast_for_suite(c, CHILD(n, 6));
2748         if (!seq2)
2749             return NULL;
2750
2751         return While(expression, seq1, seq2, LINENO(n), n->n_col_offset,
2752                      c->c_arena);
2753     }
2754
2755     PyErr_Format(PyExc_SystemError,
2756                  "wrong number of tokens for 'while' statement: %d",
2757                  NCH(n));
2758     return NULL;
2759 }
2760
2761 static stmt_ty
2762 ast_for_for_stmt(struct compiling *c, const node *n)
2763 {
2764     asdl_seq *_target, *seq = NULL, *suite_seq;
2765     expr_ty expression;
2766     expr_ty target;
2767     const node *node_target;
2768     /* for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite] */
2769     REQ(n, for_stmt);
2770
2771     if (NCH(n) == 9) {
2772         seq = ast_for_suite(c, CHILD(n, 8));
2773         if (!seq)
2774             return NULL;
2775     }
2776
2777     node_target = CHILD(n, 1);
2778     _target = ast_for_exprlist(c, node_target, Store);
2779     if (!_target)
2780         return NULL;
2781     /* Check the # of children rather than the length of _target, since
2782        for x, in ... has 1 element in _target, but still requires a Tuple. */
2783     if (NCH(node_target) == 1)
2784         target = (expr_ty)asdl_seq_GET(_target, 0);
2785     else
2786         target = Tuple(_target, Store, LINENO(n), n->n_col_offset, c->c_arena);
2787
2788     expression = ast_for_testlist(c, CHILD(n, 3));
2789     if (!expression)
2790         return NULL;
2791     suite_seq = ast_for_suite(c, CHILD(n, 5));
2792     if (!suite_seq)
2793         return NULL;
2794
2795     return For(target, expression, suite_seq, seq, LINENO(n), n->n_col_offset,
2796                c->c_arena);
2797 }
2798
2799 static excepthandler_ty
2800 ast_for_except_clause(struct compiling *c, const node *exc, node *body)
2801 {
2802     /* except_clause: 'except' [test [(',' | 'as') test]] */
2803     REQ(exc, except_clause);
2804     REQ(body, suite);
2805
2806     if (NCH(exc) == 1) {
2807         asdl_seq *suite_seq = ast_for_suite(c, body);
2808         if (!suite_seq)
2809             return NULL;
2810
2811         return excepthandler(NULL, NULL, suite_seq, LINENO(exc),
2812                              exc->n_col_offset, c->c_arena);
2813     }
2814     else if (NCH(exc) == 2) {
2815         expr_ty expression;
2816         asdl_seq *suite_seq;
2817
2818         expression = ast_for_expr(c, CHILD(exc, 1));
2819         if (!expression)
2820             return NULL;
2821         suite_seq = ast_for_suite(c, body);
2822         if (!suite_seq)
2823             return NULL;
2824
2825         return excepthandler(expression, NULL, suite_seq, LINENO(exc),
2826                              exc->n_col_offset, c->c_arena);
2827     }
2828     else if (NCH(exc) == 4) {
2829         asdl_seq *suite_seq;
2830         expr_ty expression;
2831         expr_ty e = ast_for_expr(c, CHILD(exc, 3));
2832         if (!e)
2833             return NULL;
2834         if (!set_context(e, Store, CHILD(exc, 3)))
2835             return NULL;
2836         expression = ast_for_expr(c, CHILD(exc, 1));
2837         if (!expression)
2838             return NULL;
2839         suite_seq = ast_for_suite(c, body);
2840         if (!suite_seq)
2841             return NULL;
2842
2843         return excepthandler(expression, e, suite_seq, LINENO(exc),
2844                              exc->n_col_offset, c->c_arena);
2845     }
2846
2847     PyErr_Format(PyExc_SystemError,
2848                  "wrong number of children for 'except' clause: %d",
2849                  NCH(exc));
2850     return NULL;
2851 }
2852
2853 static stmt_ty
2854 ast_for_try_stmt(struct compiling *c, const node *n)
2855 {
2856     const int nch = NCH(n);
2857     int n_except = (nch - 3)/3;
2858     asdl_seq *body, *orelse = NULL, *finally = NULL;
2859
2860     REQ(n, try_stmt);
2861
2862     body = ast_for_suite(c, CHILD(n, 2));
2863     if (body == NULL)
2864         return NULL;
2865
2866     if (TYPE(CHILD(n, nch - 3)) == NAME) {
2867         if (strcmp(STR(CHILD(n, nch - 3)), "finally") == 0) {
2868             if (nch >= 9 && TYPE(CHILD(n, nch - 6)) == NAME) {
2869                 /* we can assume it's an "else",
2870                    because nch >= 9 for try-else-finally and
2871                    it would otherwise have a type of except_clause */
2872                 orelse = ast_for_suite(c, CHILD(n, nch - 4));
2873                 if (orelse == NULL)
2874                     return NULL;
2875                 n_except--;
2876             }
2877
2878             finally = ast_for_suite(c, CHILD(n, nch - 1));
2879             if (finally == NULL)
2880                 return NULL;
2881             n_except--;
2882         }
2883         else {
2884             /* we can assume it's an "else",
2885                otherwise it would have a type of except_clause */
2886             orelse = ast_for_suite(c, CHILD(n, nch - 1));
2887             if (orelse == NULL)
2888                 return NULL;
2889             n_except--;
2890         }
2891     }
2892     else if (TYPE(CHILD(n, nch - 3)) != except_clause) {
2893         ast_error(n, "malformed 'try' statement");
2894         return NULL;
2895     }
2896
2897     if (n_except > 0) {
2898         int i;
2899         stmt_ty except_st;
2900         /* process except statements to create a try ... except */
2901         asdl_seq *handlers = asdl_seq_new(n_except, c->c_arena);
2902         if (handlers == NULL)
2903             return NULL;
2904
2905         for (i = 0; i < n_except; i++) {
2906             excepthandler_ty e = ast_for_except_clause(c, CHILD(n, 3 + i * 3),
2907                                                        CHILD(n, 5 + i * 3));
2908             if (!e)
2909                 return NULL;
2910             asdl_seq_SET(handlers, i, e);
2911         }
2912
2913         except_st = TryExcept(body, handlers, orelse, LINENO(n),
2914                               n->n_col_offset, c->c_arena);
2915         if (!finally)
2916             return except_st;
2917
2918         /* if a 'finally' is present too, we nest the TryExcept within a
2919            TryFinally to emulate try ... except ... finally */
2920         body = asdl_seq_new(1, c->c_arena);
2921         if (body == NULL)
2922             return NULL;
2923         asdl_seq_SET(body, 0, except_st);
2924     }
2925
2926     /* must be a try ... finally (except clauses are in body, if any exist) */
2927     assert(finally != NULL);
2928     return TryFinally(body, finally, LINENO(n), n->n_col_offset, c->c_arena);
2929 }
2930
2931 static expr_ty
2932 ast_for_with_var(struct compiling *c, const node *n)
2933 {
2934     REQ(n, with_var);
2935     return ast_for_expr(c, CHILD(n, 1));
2936 }
2937
2938 /* with_stmt: 'with' test [ with_var ] ':' suite */
2939 static stmt_ty
2940 ast_for_with_stmt(struct compiling *c, const node *n)
2941 {
2942     expr_ty context_expr, optional_vars = NULL;
2943     int suite_index = 3;    /* skip 'with', test, and ':' */
2944     asdl_seq *suite_seq;
2945
2946     assert(TYPE(n) == with_stmt);
2947     context_expr = ast_for_expr(c, CHILD(n, 1));
2948     if (!context_expr)
2949         return NULL;
2950     if (TYPE(CHILD(n, 2)) == with_var) {
2951         optional_vars = ast_for_with_var(c, CHILD(n, 2));
2952
2953         if (!optional_vars) {
2954             return NULL;
2955         }
2956         if (!set_context(optional_vars, Store, n)) {
2957             return NULL;
2958         }
2959         suite_index = 4;
2960     }
2961
2962     suite_seq = ast_for_suite(c, CHILD(n, suite_index));
2963     if (!suite_seq) {
2964         return NULL;
2965     }
2966     return With(context_expr, optional_vars, suite_seq, LINENO(n),
2967                 n->n_col_offset, c->c_arena);
2968 }
2969
2970 static stmt_ty
2971 ast_for_classdef(struct compiling *c, const node *n)
2972 {
2973     /* classdef: 'class' NAME ['(' testlist ')'] ':' suite */
2974     asdl_seq *bases, *s;
2975
2976     REQ(n, classdef);
2977
2978     if (!strcmp(STR(CHILD(n, 1)), "None")) {
2979             ast_error(n, "assignment to None");
2980             return NULL;
2981     }
2982
2983     if (NCH(n) == 4) {
2984         s = ast_for_suite(c, CHILD(n, 3));
2985         if (!s)
2986             return NULL;
2987         return ClassDef(NEW_IDENTIFIER(CHILD(n, 1)), NULL, s, LINENO(n),
2988                         n->n_col_offset, c->c_arena);
2989     }
2990     /* check for empty base list */
2991     if (TYPE(CHILD(n,3)) == RPAR) {
2992         s = ast_for_suite(c, CHILD(n,5));
2993         if (!s)
2994                 return NULL;
2995         return ClassDef(NEW_IDENTIFIER(CHILD(n, 1)), NULL, s, LINENO(n),
2996                         n->n_col_offset, c->c_arena);
2997     }
2998
2999     /* else handle the base class list */
3000     bases = ast_for_class_bases(c, CHILD(n, 3));
3001     if (!bases)
3002         return NULL;
3003
3004     s = ast_for_suite(c, CHILD(n, 6));
3005     if (!s)
3006         return NULL;
3007     return ClassDef(NEW_IDENTIFIER(CHILD(n, 1)), bases, s, LINENO(n),
3008                     n->n_col_offset, c->c_arena);
3009 }
3010
3011 static stmt_ty
3012 ast_for_stmt(struct compiling *c, const node *n)
3013 {
3014     if (TYPE(n) == stmt) {
3015         assert(NCH(n) == 1);
3016         n = CHILD(n, 0);
3017     }
3018     if (TYPE(n) == simple_stmt) {
3019         assert(num_stmts(n) == 1);
3020         n = CHILD(n, 0);
3021     }
3022     if (TYPE(n) == small_stmt) {
3023         REQ(n, small_stmt);
3024         n = CHILD(n, 0);
3025         /* small_stmt: expr_stmt | print_stmt  | del_stmt | pass_stmt
3026                      | flow_stmt | import_stmt | global_stmt | exec_stmt
3027                      | assert_stmt
3028         */
3029         switch (TYPE(n)) {
3030             case expr_stmt:
3031                 return ast_for_expr_stmt(c, n);
3032             case print_stmt:
3033                 return ast_for_print_stmt(c, n);
3034             case del_stmt:
3035                 return ast_for_del_stmt(c, n);
3036             case pass_stmt:
3037                 return Pass(LINENO(n), n->n_col_offset, c->c_arena);
3038             case flow_stmt:
3039                 return ast_for_flow_stmt(c, n);
3040             case import_stmt:
3041                 return ast_for_import_stmt(c, n);
3042             case global_stmt:
3043                 return ast_for_global_stmt(c, n);
3044             case exec_stmt:
3045                 return ast_for_exec_stmt(c, n);
3046             case assert_stmt:
3047                 return ast_for_assert_stmt(c, n);
3048             default:
3049                 PyErr_Format(PyExc_SystemError,
3050                              "unhandled small_stmt: TYPE=%d NCH=%d\n",
3051                              TYPE(n), NCH(n));
3052                 return NULL;
3053         }
3054     }
3055     else {
3056         /* compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt
3057                         | funcdef | classdef
3058         */
3059         node *ch = CHILD(n, 0);
3060         REQ(n, compound_stmt);
3061         switch (TYPE(ch)) {
3062             case if_stmt:
3063                 return ast_for_if_stmt(c, ch);
3064             case while_stmt:
3065                 return ast_for_while_stmt(c, ch);
3066             case for_stmt:
3067                 return ast_for_for_stmt(c, ch);
3068             case try_stmt:
3069                 return ast_for_try_stmt(c, ch);
3070             case with_stmt:
3071                 return ast_for_with_stmt(c, ch);
3072             case funcdef:
3073                 return ast_for_funcdef(c, ch);
3074             case classdef:
3075                 return ast_for_classdef(c, ch);
3076             default:
3077                 PyErr_Format(PyExc_SystemError,
3078                              "unhandled small_stmt: TYPE=%d NCH=%d\n",
3079                              TYPE(n), NCH(n));
3080                 return NULL;
3081         }
3082     }
3083 }
3084
3085 static PyObject *
3086 parsenumber(const char *s)
3087 {
3088         const char *end;
3089         long x;
3090         double dx;
3091 #ifndef WITHOUT_COMPLEX
3092         Py_complex c;
3093         int imflag;
3094 #endif
3095
3096         errno = 0;
3097         end = s + strlen(s) - 1;
3098 #ifndef WITHOUT_COMPLEX
3099         imflag = *end == 'j' || *end == 'J';
3100 #endif
3101         if (*end == 'l' || *end == 'L')
3102                 return PyLong_FromString((char *)s, (char **)0, 0);
3103         if (s[0] == '0') {
3104                 x = (long) PyOS_strtoul((char *)s, (char **)&end, 0);
3105                 if (x < 0 && errno == 0) {
3106                                 return PyLong_FromString((char *)s,
3107                                                          (char **)0,
3108                                                          0);
3109                 }
3110         }
3111         else
3112                 x = PyOS_strtol((char *)s, (char **)&end, 0);
3113         if (*end == '\0') {
3114                 if (errno != 0)
3115                         return PyLong_FromString((char *)s, (char **)0, 0);
3116                 return PyInt_FromLong(x);
3117         }
3118         /* XXX Huge floats may silently fail */
3119 #ifndef WITHOUT_COMPLEX
3120         if (imflag) {
3121                 c.real = 0.;
3122                 PyFPE_START_PROTECT("atof", return 0)
3123                 c.imag = PyOS_ascii_atof(s);
3124                 PyFPE_END_PROTECT(c)
3125                 return PyComplex_FromCComplex(c);
3126         }
3127         else
3128 #endif
3129         {
3130                 PyFPE_START_PROTECT("atof", return 0)
3131                 dx = PyOS_ascii_atof(s);
3132                 PyFPE_END_PROTECT(dx)
3133                 return PyFloat_FromDouble(dx);
3134         }
3135 }
3136
3137 static PyObject *
3138 decode_utf8(const char **sPtr, const char *end, char* encoding)
3139 {
3140 #ifndef Py_USING_UNICODE
3141         Py_FatalError("decode_utf8 should not be called in this build.");
3142         return NULL;
3143 #else
3144         PyObject *u, *v;
3145         char *s, *t;
3146         t = s = (char *)*sPtr;
3147         /* while (s < end && *s != '\\') s++; */ /* inefficient for u".." */
3148         while (s < end && (*s & 0x80)) s++;
3149         *sPtr = s;
3150         u = PyUnicode_DecodeUTF8(t, s - t, NULL);
3151         if (u == NULL)
3152                 return NULL;
3153         v = PyUnicode_AsEncodedString(u, encoding, NULL);
3154         Py_DECREF(u);
3155         return v;
3156 #endif
3157 }
3158
3159 #ifdef Py_USING_UNICODE
3160 static PyObject *
3161 decode_unicode(const char *s, size_t len, int rawmode, const char *encoding)
3162 {
3163         PyObject *v, *u;
3164         char *buf;
3165         char *p;
3166         const char *end;
3167         if (encoding == NULL) {
3168                 buf = (char *)s;
3169                 u = NULL;
3170         } else if (strcmp(encoding, "iso-8859-1") == 0) {
3171                 buf = (char *)s;
3172                 u = NULL;
3173         } else {
3174                 /* "\XX" may become "\u005c\uHHLL" (12 bytes) */
3175                 u = PyString_FromStringAndSize((char *)NULL, len * 4);
3176                 if (u == NULL)
3177                         return NULL;
3178                 p = buf = PyString_AsString(u);
3179                 end = s + len;
3180                 while (s < end) {
3181                         if (*s == '\\') {
3182                                 *p++ = *s++;
3183                                 if (*s & 0x80) {
3184                                         strcpy(p, "u005c");
3185                                         p += 5;
3186                                 }
3187                         }
3188                         if (*s & 0x80) { /* XXX inefficient */
3189                                 PyObject *w;
3190                                 char *r;
3191                                 Py_ssize_t rn, i;
3192                                 w = decode_utf8(&s, end, "utf-16-be");
3193                                 if (w == NULL) {
3194                                         Py_DECREF(u);
3195                                         return NULL;
3196                                 }
3197                                 r = PyString_AsString(w);
3198                                 rn = PyString_Size(w);
3199                                 assert(rn % 2 == 0);
3200                                 for (i = 0; i < rn; i += 2) {
3201                                         sprintf(p, "\\u%02x%02x",
3202                                                 r[i + 0] & 0xFF,
3203                                                 r[i + 1] & 0xFF);
3204                                         p += 6;
3205                                 }
3206                                 Py_DECREF(w);
3207                         } else {
3208                                 *p++ = *s++;
3209                         }
3210                 }
3211                 len = p - buf;
3212                 s = buf;
3213         }
3214         if (rawmode)
3215                 v = PyUnicode_DecodeRawUnicodeEscape(s, len, NULL);
3216         else
3217                 v = PyUnicode_DecodeUnicodeEscape(s, len, NULL);
3218         Py_XDECREF(u);
3219         return v;
3220 }
3221 #endif
3222
3223 /* s is a Python string literal, including the bracketing quote characters,
3224  * and r &/or u prefixes (if any), and embedded escape sequences (if any).
3225  * parsestr parses it, and returns the decoded Python string object.
3226  */
3227 static PyObject *
3228 parsestr(const char *s, const char *encoding)
3229 {
3230         size_t len;
3231         int quote = Py_CHARMASK(*s);
3232         int rawmode = 0;
3233         int need_encoding;
3234         int unicode = 0;
3235
3236         if (isalpha(quote) || quote == '_') {
3237                 if (quote == 'u' || quote == 'U') {
3238                         quote = *++s;
3239                         unicode = 1;
3240                 }
3241                 if (quote == 'r' || quote == 'R') {
3242                         quote = *++s;
3243                         rawmode = 1;
3244                 }
3245         }
3246         if (quote != '\'' && quote != '\"') {
3247                 PyErr_BadInternalCall();
3248                 return NULL;
3249         }
3250         s++;
3251         len = strlen(s);
3252         if (len > INT_MAX) {
3253                 PyErr_SetString(PyExc_OverflowError,
3254                                 "string to parse is too long");
3255                 return NULL;
3256         }
3257         if (s[--len] != quote) {
3258                 PyErr_BadInternalCall();
3259                 return NULL;
3260         }
3261         if (len >= 4 && s[0] == quote && s[1] == quote) {
3262                 s += 2;
3263                 len -= 2;
3264                 if (s[--len] != quote || s[--len] != quote) {
3265                         PyErr_BadInternalCall();
3266                         return NULL;
3267                 }
3268         }
3269 #ifdef Py_USING_UNICODE
3270         if (unicode || Py_UnicodeFlag) {
3271                 return decode_unicode(s, len, rawmode, encoding);
3272         }
3273 #endif
3274         need_encoding = (encoding != NULL &&
3275                          strcmp(encoding, "utf-8") != 0 &&
3276                          strcmp(encoding, "iso-8859-1") != 0);
3277         if (rawmode || strchr(s, '\\') == NULL) {
3278                 if (need_encoding) {
3279 #ifndef Py_USING_UNICODE
3280                         /* This should not happen - we never see any other
3281                            encoding. */
3282                         Py_FatalError(
3283                             "cannot deal with encodings in this build.");
3284 #else
3285                         PyObject *v, *u = PyUnicode_DecodeUTF8(s, len, NULL);
3286                         if (u == NULL)
3287                                 return NULL;
3288                         v = PyUnicode_AsEncodedString(u, encoding, NULL);
3289                         Py_DECREF(u);
3290                         return v;
3291 #endif
3292                 } else {
3293                         return PyString_FromStringAndSize(s, len);
3294                 }
3295         }
3296
3297         return PyString_DecodeEscape(s, len, NULL, unicode,
3298                                      need_encoding ? encoding : NULL);
3299 }
3300
3301 /* Build a Python string object out of a STRING atom.  This takes care of
3302  * compile-time literal catenation, calling parsestr() on each piece, and
3303  * pasting the intermediate results together.
3304  */
3305 static PyObject *
3306 parsestrplus(struct compiling *c, const node *n)
3307 {
3308         PyObject *v;
3309         int i;
3310         REQ(CHILD(n, 0), STRING);
3311         if ((v = parsestr(STR(CHILD(n, 0)), c->c_encoding)) != NULL) {
3312                 /* String literal concatenation */
3313                 for (i = 1; i < NCH(n); i++) {
3314                         PyObject *s;
3315                         s = parsestr(STR(CHILD(n, i)), c->c_encoding);
3316                         if (s == NULL)
3317                                 goto onError;
3318                         if (PyString_Check(v) && PyString_Check(s)) {
3319                                 PyString_ConcatAndDel(&v, s);
3320                                 if (v == NULL)
3321                                     goto onError;
3322                         }
3323 #ifdef Py_USING_UNICODE
3324                         else {
3325                                 PyObject *temp = PyUnicode_Concat(v, s);
3326                                 Py_DECREF(s);
3327                                 Py_DECREF(v);
3328                                 v = temp;
3329                                 if (v == NULL)
3330                                     goto onError;
3331                         }
3332 #endif
3333                 }
3334         }
3335         return v;
3336
3337  onError:
3338         Py_XDECREF(v);
3339         return NULL;
3340 }