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