parsermodule.c revision 7544508f0245173bff5866aa1598c8f6cce1fc5f
1/* parsermodule.c 2 * 3 * Copyright 1995-1996 by Fred L. Drake, Jr. and Virginia Polytechnic 4 * Institute and State University, Blacksburg, Virginia, USA. 5 * Portions copyright 1991-1995 by Stichting Mathematisch Centrum, 6 * Amsterdam, The Netherlands. Copying is permitted under the terms 7 * associated with the main Python distribution, with the additional 8 * restriction that this additional notice be included and maintained 9 * on all distributed copies. 10 * 11 * This module serves to replace the original parser module written 12 * by Guido. The functionality is not matched precisely, but the 13 * original may be implemented on top of this. This is desirable 14 * since the source of the text to be parsed is now divorced from 15 * this interface. 16 * 17 * Unlike the prior interface, the ability to give a parse tree 18 * produced by Python code as a tuple to the compiler is enabled by 19 * this module. See the documentation for more details. 20 * 21 * I've added some annotations that help with the lint code-checking 22 * program, but they're not complete by a long shot. The real errors 23 * that lint detects are gone, but there are still warnings with 24 * Py_[X]DECREF() and Py_[X]INCREF() macros. The lint annotations 25 * look like "NOTE(...)". 26 * 27 * To debug parser errors like 28 * "parser.ParserError: Expected node type 12, got 333." 29 * decode symbol numbers using the automatically-generated files 30 * Lib/symbol.h and Include/token.h. 31 */ 32 33#include "Python.h" /* general Python API */ 34#include "Python-ast.h" /* mod_ty */ 35#include "graminit.h" /* symbols defined in the grammar */ 36#include "node.h" /* internal parser structure */ 37#include "errcode.h" /* error codes for PyNode_*() */ 38#include "token.h" /* token definitions */ 39#include "grammar.h" 40#include "parsetok.h" 41 /* ISTERMINAL() / ISNONTERMINAL() */ 42#undef Yield 43#include "ast.h" 44 45extern grammar _PyParser_Grammar; /* From graminit.c */ 46 47#ifdef lint 48#include <note.h> 49#else 50#define NOTE(x) 51#endif 52 53/* String constants used to initialize module attributes. 54 * 55 */ 56static char parser_copyright_string[] = 57"Copyright 1995-1996 by Virginia Polytechnic Institute & State\n\ 58University, Blacksburg, Virginia, USA, and Fred L. Drake, Jr., Reston,\n\ 59Virginia, USA. Portions copyright 1991-1995 by Stichting Mathematisch\n\ 60Centrum, Amsterdam, The Netherlands."; 61 62 63PyDoc_STRVAR(parser_doc_string, 64"This is an interface to Python's internal parser."); 65 66static char parser_version_string[] = "0.5"; 67 68 69typedef PyObject* (*SeqMaker) (Py_ssize_t length); 70typedef int (*SeqInserter) (PyObject* sequence, 71 Py_ssize_t index, 72 PyObject* element); 73 74/* The function below is copyrighted by Stichting Mathematisch Centrum. The 75 * original copyright statement is included below, and continues to apply 76 * in full to the function immediately following. All other material is 77 * original, copyrighted by Fred L. Drake, Jr. and Virginia Polytechnic 78 * Institute and State University. Changes were made to comply with the 79 * new naming conventions. Added arguments to provide support for creating 80 * lists as well as tuples, and optionally including the line numbers. 81 */ 82 83 84static PyObject* 85node2tuple(node *n, /* node to convert */ 86 SeqMaker mkseq, /* create sequence */ 87 SeqInserter addelem, /* func. to add elem. in seq. */ 88 int lineno, /* include line numbers? */ 89 int col_offset) /* include column offsets? */ 90{ 91 PyObject *result = NULL, *w; 92 93 if (n == NULL) { 94 Py_INCREF(Py_None); 95 return Py_None; 96 } 97 98 if (ISNONTERMINAL(TYPE(n))) { 99 int i; 100 101 result = mkseq(1 + NCH(n) + (TYPE(n) == encoding_decl)); 102 if (result == NULL) 103 goto error; 104 105 w = PyLong_FromLong(TYPE(n)); 106 if (w == NULL) 107 goto error; 108 (void) addelem(result, 0, w); 109 110 for (i = 0; i < NCH(n); i++) { 111 w = node2tuple(CHILD(n, i), mkseq, addelem, lineno, col_offset); 112 if (w == NULL) 113 goto error; 114 (void) addelem(result, i+1, w); 115 } 116 117 if (TYPE(n) == encoding_decl) { 118 w = PyUnicode_FromString(STR(n)); 119 if (w == NULL) 120 goto error; 121 (void) addelem(result, i+1, w); 122 } 123 } 124 else if (ISTERMINAL(TYPE(n))) { 125 result = mkseq(2 + lineno + col_offset); 126 if (result == NULL) 127 goto error; 128 129 w = PyLong_FromLong(TYPE(n)); 130 if (w == NULL) 131 goto error; 132 (void) addelem(result, 0, w); 133 134 w = PyUnicode_FromString(STR(n)); 135 if (w == NULL) 136 goto error; 137 (void) addelem(result, 1, w); 138 139 if (lineno == 1) { 140 w = PyLong_FromLong(n->n_lineno); 141 if (w == NULL) 142 goto error; 143 (void) addelem(result, 2, w); 144 } 145 146 if (col_offset == 1) { 147 w = PyLong_FromLong(n->n_col_offset); 148 if (w == NULL) 149 goto error; 150 (void) addelem(result, 3, w); 151 } 152 } 153 else { 154 PyErr_SetString(PyExc_SystemError, 155 "unrecognized parse tree node type"); 156 return ((PyObject*) NULL); 157 } 158 return result; 159 160error: 161 Py_XDECREF(result); 162 return NULL; 163} 164/* 165 * End of material copyrighted by Stichting Mathematisch Centrum. 166 */ 167 168 169 170/* There are two types of intermediate objects we're interested in: 171 * 'eval' and 'exec' types. These constants can be used in the st_type 172 * field of the object type to identify which any given object represents. 173 * These should probably go in an external header to allow other extensions 174 * to use them, but then, we really should be using C++ too. ;-) 175 */ 176 177#define PyST_EXPR 1 178#define PyST_SUITE 2 179 180 181/* These are the internal objects and definitions required to implement the 182 * ST type. Most of the internal names are more reminiscent of the 'old' 183 * naming style, but the code uses the new naming convention. 184 */ 185 186static PyObject* 187parser_error = 0; 188 189 190typedef struct { 191 PyObject_HEAD /* standard object header */ 192 node* st_node; /* the node* returned by the parser */ 193 int st_type; /* EXPR or SUITE ? */ 194 PyCompilerFlags st_flags; /* Parser and compiler flags */ 195} PyST_Object; 196 197 198static void parser_free(PyST_Object *st); 199static PyObject* parser_sizeof(PyST_Object *, void *); 200static PyObject* parser_richcompare(PyObject *left, PyObject *right, int op); 201static PyObject* parser_compilest(PyST_Object *, PyObject *, PyObject *); 202static PyObject* parser_isexpr(PyST_Object *, PyObject *, PyObject *); 203static PyObject* parser_issuite(PyST_Object *, PyObject *, PyObject *); 204static PyObject* parser_st2list(PyST_Object *, PyObject *, PyObject *); 205static PyObject* parser_st2tuple(PyST_Object *, PyObject *, PyObject *); 206 207#define PUBLIC_METHOD_TYPE (METH_VARARGS|METH_KEYWORDS) 208 209static PyMethodDef parser_methods[] = { 210 {"compile", (PyCFunction)parser_compilest, PUBLIC_METHOD_TYPE, 211 PyDoc_STR("Compile this ST object into a code object.")}, 212 {"isexpr", (PyCFunction)parser_isexpr, PUBLIC_METHOD_TYPE, 213 PyDoc_STR("Determines if this ST object was created from an expression.")}, 214 {"issuite", (PyCFunction)parser_issuite, PUBLIC_METHOD_TYPE, 215 PyDoc_STR("Determines if this ST object was created from a suite.")}, 216 {"tolist", (PyCFunction)parser_st2list, PUBLIC_METHOD_TYPE, 217 PyDoc_STR("Creates a list-tree representation of this ST.")}, 218 {"totuple", (PyCFunction)parser_st2tuple, PUBLIC_METHOD_TYPE, 219 PyDoc_STR("Creates a tuple-tree representation of this ST.")}, 220 {"__sizeof__", (PyCFunction)parser_sizeof, METH_NOARGS, 221 PyDoc_STR("Returns size in memory, in bytes.")}, 222 {NULL, NULL, 0, NULL} 223}; 224 225static 226PyTypeObject PyST_Type = { 227 PyVarObject_HEAD_INIT(NULL, 0) 228 "parser.st", /* tp_name */ 229 (int) sizeof(PyST_Object), /* tp_basicsize */ 230 0, /* tp_itemsize */ 231 (destructor)parser_free, /* tp_dealloc */ 232 0, /* tp_print */ 233 0, /* tp_getattr */ 234 0, /* tp_setattr */ 235 0, /* tp_reserved */ 236 0, /* tp_repr */ 237 0, /* tp_as_number */ 238 0, /* tp_as_sequence */ 239 0, /* tp_as_mapping */ 240 0, /* tp_hash */ 241 0, /* tp_call */ 242 0, /* tp_str */ 243 0, /* tp_getattro */ 244 0, /* tp_setattro */ 245 246 /* Functions to access object as input/output buffer */ 247 0, /* tp_as_buffer */ 248 249 Py_TPFLAGS_DEFAULT, /* tp_flags */ 250 251 /* __doc__ */ 252 "Intermediate representation of a Python parse tree.", 253 0, /* tp_traverse */ 254 0, /* tp_clear */ 255 parser_richcompare, /* tp_richcompare */ 256 0, /* tp_weaklistoffset */ 257 0, /* tp_iter */ 258 0, /* tp_iternext */ 259 parser_methods, /* tp_methods */ 260}; /* PyST_Type */ 261 262 263/* PyST_Type isn't subclassable, so just check ob_type */ 264#define PyST_Object_Check(v) ((v)->ob_type == &PyST_Type) 265 266static int 267parser_compare_nodes(node *left, node *right) 268{ 269 int j; 270 271 if (TYPE(left) < TYPE(right)) 272 return (-1); 273 274 if (TYPE(right) < TYPE(left)) 275 return (1); 276 277 if (ISTERMINAL(TYPE(left))) 278 return (strcmp(STR(left), STR(right))); 279 280 if (NCH(left) < NCH(right)) 281 return (-1); 282 283 if (NCH(right) < NCH(left)) 284 return (1); 285 286 for (j = 0; j < NCH(left); ++j) { 287 int v = parser_compare_nodes(CHILD(left, j), CHILD(right, j)); 288 289 if (v != 0) 290 return (v); 291 } 292 return (0); 293} 294 295/* parser_richcompare(PyObject* left, PyObject* right, int op) 296 * 297 * Comparison function used by the Python operators ==, !=, <, >, <=, >= 298 * This really just wraps a call to parser_compare_nodes() with some easy 299 * checks and protection code. 300 * 301 */ 302 303#define TEST_COND(cond) ((cond) ? Py_True : Py_False) 304 305static PyObject * 306parser_richcompare(PyObject *left, PyObject *right, int op) 307{ 308 int result; 309 PyObject *v; 310 311 /* neither argument should be NULL, unless something's gone wrong */ 312 if (left == NULL || right == NULL) { 313 PyErr_BadInternalCall(); 314 return NULL; 315 } 316 317 /* both arguments should be instances of PyST_Object */ 318 if (!PyST_Object_Check(left) || !PyST_Object_Check(right)) { 319 v = Py_NotImplemented; 320 goto finished; 321 } 322 323 if (left == right) 324 /* if arguments are identical, they're equal */ 325 result = 0; 326 else 327 result = parser_compare_nodes(((PyST_Object *)left)->st_node, 328 ((PyST_Object *)right)->st_node); 329 330 /* Convert return value to a Boolean */ 331 switch (op) { 332 case Py_EQ: 333 v = TEST_COND(result == 0); 334 break; 335 case Py_NE: 336 v = TEST_COND(result != 0); 337 break; 338 case Py_LE: 339 v = TEST_COND(result <= 0); 340 break; 341 case Py_GE: 342 v = TEST_COND(result >= 0); 343 break; 344 case Py_LT: 345 v = TEST_COND(result < 0); 346 break; 347 case Py_GT: 348 v = TEST_COND(result > 0); 349 break; 350 default: 351 PyErr_BadArgument(); 352 return NULL; 353 } 354 finished: 355 Py_INCREF(v); 356 return v; 357} 358 359/* parser_newstobject(node* st) 360 * 361 * Allocates a new Python object representing an ST. This is simply the 362 * 'wrapper' object that holds a node* and allows it to be passed around in 363 * Python code. 364 * 365 */ 366static PyObject* 367parser_newstobject(node *st, int type) 368{ 369 PyST_Object* o = PyObject_New(PyST_Object, &PyST_Type); 370 371 if (o != 0) { 372 o->st_node = st; 373 o->st_type = type; 374 o->st_flags.cf_flags = 0; 375 } 376 else { 377 PyNode_Free(st); 378 } 379 return ((PyObject*)o); 380} 381 382 383/* void parser_free(PyST_Object* st) 384 * 385 * This is called by a del statement that reduces the reference count to 0. 386 * 387 */ 388static void 389parser_free(PyST_Object *st) 390{ 391 PyNode_Free(st->st_node); 392 PyObject_Del(st); 393} 394 395static PyObject * 396parser_sizeof(PyST_Object *st, void *unused) 397{ 398 Py_ssize_t res; 399 400 res = sizeof(PyST_Object) + _PyNode_SizeOf(st->st_node); 401 return PyLong_FromSsize_t(res); 402} 403 404 405/* parser_st2tuple(PyObject* self, PyObject* args, PyObject* kw) 406 * 407 * This provides conversion from a node* to a tuple object that can be 408 * returned to the Python-level caller. The ST object is not modified. 409 * 410 */ 411static PyObject* 412parser_st2tuple(PyST_Object *self, PyObject *args, PyObject *kw) 413{ 414 int line_info = 0; 415 int col_info = 0; 416 PyObject *res = 0; 417 int ok; 418 419 static char *keywords[] = {"st", "line_info", "col_info", NULL}; 420 421 if (self == NULL || PyModule_Check(self)) { 422 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|pp:st2tuple", keywords, 423 &PyST_Type, &self, &line_info, 424 &col_info); 425 } 426 else 427 ok = PyArg_ParseTupleAndKeywords(args, kw, "|pp:totuple", &keywords[1], 428 &line_info, &col_info); 429 if (ok != 0) { 430 /* 431 * Convert ST into a tuple representation. Use Guido's function, 432 * since it's known to work already. 433 */ 434 res = node2tuple(((PyST_Object*)self)->st_node, 435 PyTuple_New, PyTuple_SetItem, line_info, col_info); 436 } 437 return (res); 438} 439 440 441/* parser_st2list(PyObject* self, PyObject* args, PyObject* kw) 442 * 443 * This provides conversion from a node* to a list object that can be 444 * returned to the Python-level caller. The ST object is not modified. 445 * 446 */ 447static PyObject* 448parser_st2list(PyST_Object *self, PyObject *args, PyObject *kw) 449{ 450 int line_info = 0; 451 int col_info = 0; 452 PyObject *res = 0; 453 int ok; 454 455 static char *keywords[] = {"st", "line_info", "col_info", NULL}; 456 457 if (self == NULL || PyModule_Check(self)) 458 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|pp:st2list", keywords, 459 &PyST_Type, &self, &line_info, 460 &col_info); 461 else 462 ok = PyArg_ParseTupleAndKeywords(args, kw, "|pp:tolist", &keywords[1], 463 &line_info, &col_info); 464 if (ok) { 465 /* 466 * Convert ST into a tuple representation. Use Guido's function, 467 * since it's known to work already. 468 */ 469 res = node2tuple(self->st_node, 470 PyList_New, PyList_SetItem, line_info, col_info); 471 } 472 return (res); 473} 474 475 476/* parser_compilest(PyObject* self, PyObject* args) 477 * 478 * This function creates code objects from the parse tree represented by 479 * the passed-in data object. An optional file name is passed in as well. 480 * 481 */ 482static PyObject* 483parser_compilest(PyST_Object *self, PyObject *args, PyObject *kw) 484{ 485 PyObject* res = NULL; 486 PyArena* arena = NULL; 487 mod_ty mod; 488 PyObject* filename = NULL; 489 int ok; 490 491 static char *keywords[] = {"st", "filename", NULL}; 492 493 if (self == NULL || PyModule_Check(self)) 494 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|O&:compilest", keywords, 495 &PyST_Type, &self, 496 PyUnicode_FSDecoder, &filename); 497 else 498 ok = PyArg_ParseTupleAndKeywords(args, kw, "|O&:compile", &keywords[1], 499 PyUnicode_FSDecoder, &filename); 500 if (!ok) 501 goto error; 502 503 if (filename == NULL) { 504 filename = PyUnicode_FromString("<syntax-tree>"); 505 if (filename == NULL) 506 goto error; 507 } 508 509 arena = PyArena_New(); 510 if (!arena) 511 goto error; 512 513 mod = PyAST_FromNodeObject(self->st_node, &self->st_flags, 514 filename, arena); 515 if (!mod) 516 goto error; 517 518 res = (PyObject *)PyAST_CompileObject(mod, filename, 519 &self->st_flags, -1, arena); 520error: 521 Py_XDECREF(filename); 522 if (arena != NULL) 523 PyArena_Free(arena); 524 return res; 525} 526 527 528/* PyObject* parser_isexpr(PyObject* self, PyObject* args) 529 * PyObject* parser_issuite(PyObject* self, PyObject* args) 530 * 531 * Checks the passed-in ST object to determine if it is an expression or 532 * a statement suite, respectively. The return is a Python truth value. 533 * 534 */ 535static PyObject* 536parser_isexpr(PyST_Object *self, PyObject *args, PyObject *kw) 537{ 538 PyObject* res = 0; 539 int ok; 540 541 static char *keywords[] = {"st", NULL}; 542 543 if (self == NULL || PyModule_Check(self)) 544 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:isexpr", keywords, 545 &PyST_Type, &self); 546 else 547 ok = PyArg_ParseTupleAndKeywords(args, kw, ":isexpr", &keywords[1]); 548 549 if (ok) { 550 /* Check to see if the ST represents an expression or not. */ 551 res = (self->st_type == PyST_EXPR) ? Py_True : Py_False; 552 Py_INCREF(res); 553 } 554 return (res); 555} 556 557 558static PyObject* 559parser_issuite(PyST_Object *self, PyObject *args, PyObject *kw) 560{ 561 PyObject* res = 0; 562 int ok; 563 564 static char *keywords[] = {"st", NULL}; 565 566 if (self == NULL || PyModule_Check(self)) 567 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:issuite", keywords, 568 &PyST_Type, &self); 569 else 570 ok = PyArg_ParseTupleAndKeywords(args, kw, ":issuite", &keywords[1]); 571 572 if (ok) { 573 /* Check to see if the ST represents an expression or not. */ 574 res = (self->st_type == PyST_EXPR) ? Py_False : Py_True; 575 Py_INCREF(res); 576 } 577 return (res); 578} 579 580 581/* err_string(char* message) 582 * 583 * Sets the error string for an exception of type ParserError. 584 * 585 */ 586static void 587err_string(char *message) 588{ 589 PyErr_SetString(parser_error, message); 590} 591 592 593/* PyObject* parser_do_parse(PyObject* args, int type) 594 * 595 * Internal function to actually execute the parse and return the result if 596 * successful or set an exception if not. 597 * 598 */ 599static PyObject* 600parser_do_parse(PyObject *args, PyObject *kw, char *argspec, int type) 601{ 602 char* string = 0; 603 PyObject* res = 0; 604 int flags = 0; 605 perrdetail err; 606 607 static char *keywords[] = {"source", NULL}; 608 609 if (PyArg_ParseTupleAndKeywords(args, kw, argspec, keywords, &string)) { 610 node* n = PyParser_ParseStringFlagsFilenameEx(string, NULL, 611 &_PyParser_Grammar, 612 (type == PyST_EXPR) 613 ? eval_input : file_input, 614 &err, &flags); 615 616 if (n) { 617 res = parser_newstobject(n, type); 618 if (res) 619 ((PyST_Object *)res)->st_flags.cf_flags = flags & PyCF_MASK; 620 } 621 else { 622 PyParser_SetError(&err); 623 } 624 PyParser_ClearError(&err); 625 } 626 return (res); 627} 628 629 630/* PyObject* parser_expr(PyObject* self, PyObject* args) 631 * PyObject* parser_suite(PyObject* self, PyObject* args) 632 * 633 * External interfaces to the parser itself. Which is called determines if 634 * the parser attempts to recognize an expression ('eval' form) or statement 635 * suite ('exec' form). The real work is done by parser_do_parse() above. 636 * 637 */ 638static PyObject* 639parser_expr(PyST_Object *self, PyObject *args, PyObject *kw) 640{ 641 NOTE(ARGUNUSED(self)) 642 return (parser_do_parse(args, kw, "s:expr", PyST_EXPR)); 643} 644 645 646static PyObject* 647parser_suite(PyST_Object *self, PyObject *args, PyObject *kw) 648{ 649 NOTE(ARGUNUSED(self)) 650 return (parser_do_parse(args, kw, "s:suite", PyST_SUITE)); 651} 652 653 654 655/* This is the messy part of the code. Conversion from a tuple to an ST 656 * object requires that the input tuple be valid without having to rely on 657 * catching an exception from the compiler. This is done to allow the 658 * compiler itself to remain fast, since most of its input will come from 659 * the parser directly, and therefore be known to be syntactically correct. 660 * This validation is done to ensure that we don't core dump the compile 661 * phase, returning an exception instead. 662 * 663 * Two aspects can be broken out in this code: creating a node tree from 664 * the tuple passed in, and verifying that it is indeed valid. It may be 665 * advantageous to expand the number of ST types to include funcdefs and 666 * lambdadefs to take advantage of the optimizer, recognizing those STs 667 * here. They are not necessary, and not quite as useful in a raw form. 668 * For now, let's get expressions and suites working reliably. 669 */ 670 671 672static node* build_node_tree(PyObject *tuple); 673static int validate_expr_tree(node *tree); 674static int validate_file_input(node *tree); 675static int validate_encoding_decl(node *tree); 676 677/* PyObject* parser_tuple2st(PyObject* self, PyObject* args) 678 * 679 * This is the public function, called from the Python code. It receives a 680 * single tuple object from the caller, and creates an ST object if the 681 * tuple can be validated. It does this by checking the first code of the 682 * tuple, and, if acceptable, builds the internal representation. If this 683 * step succeeds, the internal representation is validated as fully as 684 * possible with the various validate_*() routines defined below. 685 * 686 * This function must be changed if support is to be added for PyST_FRAGMENT 687 * ST objects. 688 * 689 */ 690static PyObject* 691parser_tuple2st(PyST_Object *self, PyObject *args, PyObject *kw) 692{ 693 NOTE(ARGUNUSED(self)) 694 PyObject *st = 0; 695 PyObject *tuple; 696 node *tree; 697 698 static char *keywords[] = {"sequence", NULL}; 699 700 if (!PyArg_ParseTupleAndKeywords(args, kw, "O:sequence2st", keywords, 701 &tuple)) 702 return (0); 703 if (!PySequence_Check(tuple)) { 704 PyErr_SetString(PyExc_ValueError, 705 "sequence2st() requires a single sequence argument"); 706 return (0); 707 } 708 /* 709 * Convert the tree to the internal form before checking it. 710 */ 711 tree = build_node_tree(tuple); 712 if (tree != 0) { 713 int start_sym = TYPE(tree); 714 if (start_sym == eval_input) { 715 /* Might be an eval form. */ 716 if (validate_expr_tree(tree)) 717 st = parser_newstobject(tree, PyST_EXPR); 718 else 719 PyNode_Free(tree); 720 } 721 else if (start_sym == file_input) { 722 /* This looks like an exec form so far. */ 723 if (validate_file_input(tree)) 724 st = parser_newstobject(tree, PyST_SUITE); 725 else 726 PyNode_Free(tree); 727 } 728 else if (start_sym == encoding_decl) { 729 /* This looks like an encoding_decl so far. */ 730 if (validate_encoding_decl(tree)) 731 st = parser_newstobject(tree, PyST_SUITE); 732 else 733 PyNode_Free(tree); 734 } 735 else { 736 /* This is a fragment, at best. */ 737 PyNode_Free(tree); 738 err_string("parse tree does not use a valid start symbol"); 739 } 740 } 741 /* Make sure we raise an exception on all errors. We should never 742 * get this, but we'd do well to be sure something is done. 743 */ 744 if (st == NULL && !PyErr_Occurred()) 745 err_string("unspecified ST error occurred"); 746 747 return st; 748} 749 750 751/* node* build_node_children() 752 * 753 * Iterate across the children of the current non-terminal node and build 754 * their structures. If successful, return the root of this portion of 755 * the tree, otherwise, 0. Any required exception will be specified already, 756 * and no memory will have been deallocated. 757 * 758 */ 759static node* 760build_node_children(PyObject *tuple, node *root, int *line_num) 761{ 762 Py_ssize_t len = PyObject_Size(tuple); 763 Py_ssize_t i; 764 int err; 765 766 for (i = 1; i < len; ++i) { 767 /* elem must always be a sequence, however simple */ 768 PyObject* elem = PySequence_GetItem(tuple, i); 769 int ok = elem != NULL; 770 int type = 0; 771 char *strn = 0; 772 773 if (ok) 774 ok = PySequence_Check(elem); 775 if (ok) { 776 PyObject *temp = PySequence_GetItem(elem, 0); 777 if (temp == NULL) 778 ok = 0; 779 else { 780 ok = PyLong_Check(temp); 781 if (ok) { 782 type = _PyLong_AsInt(temp); 783 if (type == -1 && PyErr_Occurred()) { 784 Py_DECREF(temp); 785 Py_DECREF(elem); 786 return 0; 787 } 788 } 789 Py_DECREF(temp); 790 } 791 } 792 if (!ok) { 793 PyObject *err = Py_BuildValue("Os", elem, 794 "Illegal node construct."); 795 PyErr_SetObject(parser_error, err); 796 Py_XDECREF(err); 797 Py_XDECREF(elem); 798 return (0); 799 } 800 if (ISTERMINAL(type)) { 801 Py_ssize_t len = PyObject_Size(elem); 802 PyObject *temp; 803 const char *temp_str; 804 805 if ((len != 2) && (len != 3)) { 806 err_string("terminal nodes must have 2 or 3 entries"); 807 return 0; 808 } 809 temp = PySequence_GetItem(elem, 1); 810 if (temp == NULL) 811 return 0; 812 if (!PyUnicode_Check(temp)) { 813 PyErr_Format(parser_error, 814 "second item in terminal node must be a string," 815 " found %s", 816 Py_TYPE(temp)->tp_name); 817 Py_DECREF(temp); 818 Py_DECREF(elem); 819 return 0; 820 } 821 if (len == 3) { 822 PyObject *o = PySequence_GetItem(elem, 2); 823 if (o != NULL) { 824 if (PyLong_Check(o)) { 825 int num = _PyLong_AsInt(o); 826 if (num == -1 && PyErr_Occurred()) { 827 Py_DECREF(o); 828 Py_DECREF(temp); 829 Py_DECREF(elem); 830 return 0; 831 } 832 *line_num = num; 833 } 834 else { 835 PyErr_Format(parser_error, 836 "third item in terminal node must be an" 837 " integer, found %s", 838 Py_TYPE(temp)->tp_name); 839 Py_DECREF(o); 840 Py_DECREF(temp); 841 Py_DECREF(elem); 842 return 0; 843 } 844 Py_DECREF(o); 845 } 846 } 847 temp_str = _PyUnicode_AsStringAndSize(temp, &len); 848 if (temp_str == NULL) { 849 Py_DECREF(temp); 850 Py_XDECREF(elem); 851 return 0; 852 } 853 strn = (char *)PyObject_MALLOC(len + 1); 854 if (strn == NULL) { 855 Py_DECREF(temp); 856 Py_XDECREF(elem); 857 PyErr_NoMemory(); 858 return 0; 859 } 860 (void) memcpy(strn, temp_str, len + 1); 861 Py_DECREF(temp); 862 } 863 else if (!ISNONTERMINAL(type)) { 864 /* 865 * It has to be one or the other; this is an error. 866 * Raise an exception. 867 */ 868 PyObject *err = Py_BuildValue("os", elem, "unknown node type."); 869 PyErr_SetObject(parser_error, err); 870 Py_XDECREF(err); 871 Py_XDECREF(elem); 872 return (0); 873 } 874 err = PyNode_AddChild(root, type, strn, *line_num, 0); 875 if (err == E_NOMEM) { 876 Py_XDECREF(elem); 877 PyObject_FREE(strn); 878 return (node *) PyErr_NoMemory(); 879 } 880 if (err == E_OVERFLOW) { 881 Py_XDECREF(elem); 882 PyObject_FREE(strn); 883 PyErr_SetString(PyExc_ValueError, 884 "unsupported number of child nodes"); 885 return NULL; 886 } 887 888 if (ISNONTERMINAL(type)) { 889 node* new_child = CHILD(root, i - 1); 890 891 if (new_child != build_node_children(elem, new_child, line_num)) { 892 Py_XDECREF(elem); 893 return (0); 894 } 895 } 896 else if (type == NEWLINE) { /* It's true: we increment the */ 897 ++(*line_num); /* line number *after* the newline! */ 898 } 899 Py_XDECREF(elem); 900 } 901 return root; 902} 903 904 905static node* 906build_node_tree(PyObject *tuple) 907{ 908 node* res = 0; 909 PyObject *temp = PySequence_GetItem(tuple, 0); 910 long num = -1; 911 912 if (temp != NULL) 913 num = PyLong_AsLong(temp); 914 Py_XDECREF(temp); 915 if (ISTERMINAL(num)) { 916 /* 917 * The tuple is simple, but it doesn't start with a start symbol. 918 * Raise an exception now and be done with it. 919 */ 920 tuple = Py_BuildValue("Os", tuple, 921 "Illegal syntax-tree; cannot start with terminal symbol."); 922 PyErr_SetObject(parser_error, tuple); 923 Py_XDECREF(tuple); 924 } 925 else if (ISNONTERMINAL(num)) { 926 /* 927 * Not efficient, but that can be handled later. 928 */ 929 int line_num = 0; 930 PyObject *encoding = NULL; 931 932 if (num == encoding_decl) { 933 encoding = PySequence_GetItem(tuple, 2); 934 /* tuple isn't borrowed anymore here, need to DECREF */ 935 tuple = PySequence_GetSlice(tuple, 0, 2); 936 if (tuple == NULL) 937 return NULL; 938 } 939 res = PyNode_New(num); 940 if (res != NULL) { 941 if (res != build_node_children(tuple, res, &line_num)) { 942 PyNode_Free(res); 943 res = NULL; 944 } 945 if (res && encoding) { 946 Py_ssize_t len; 947 const char *temp; 948 temp = _PyUnicode_AsStringAndSize(encoding, &len); 949 if (temp == NULL) { 950 Py_DECREF(res); 951 Py_DECREF(encoding); 952 Py_DECREF(tuple); 953 return NULL; 954 } 955 res->n_str = (char *)PyObject_MALLOC(len + 1); 956 if (res->n_str == NULL) { 957 Py_DECREF(res); 958 Py_DECREF(encoding); 959 Py_DECREF(tuple); 960 PyErr_NoMemory(); 961 return NULL; 962 } 963 (void) memcpy(res->n_str, temp, len + 1); 964 Py_DECREF(encoding); 965 Py_DECREF(tuple); 966 } 967 } 968 } 969 else { 970 /* The tuple is illegal -- if the number is neither TERMINAL nor 971 * NONTERMINAL, we can't use it. Not sure the implementation 972 * allows this condition, but the API doesn't preclude it. 973 */ 974 PyObject *err = Py_BuildValue("os", tuple, 975 "Illegal component tuple."); 976 PyErr_SetObject(parser_error, err); 977 Py_XDECREF(err); 978 } 979 980 return (res); 981} 982 983 984/* 985 * Validation routines used within the validation section: 986 */ 987static int validate_terminal(node *terminal, int type, char *string); 988 989#define validate_ampersand(ch) validate_terminal(ch, AMPER, "&") 990#define validate_circumflex(ch) validate_terminal(ch, CIRCUMFLEX, "^") 991#define validate_colon(ch) validate_terminal(ch, COLON, ":") 992#define validate_comma(ch) validate_terminal(ch, COMMA, ",") 993#define validate_dedent(ch) validate_terminal(ch, DEDENT, "") 994#define validate_equal(ch) validate_terminal(ch, EQUAL, "=") 995#define validate_indent(ch) validate_terminal(ch, INDENT, (char*)NULL) 996#define validate_lparen(ch) validate_terminal(ch, LPAR, "(") 997#define validate_newline(ch) validate_terminal(ch, NEWLINE, (char*)NULL) 998#define validate_rparen(ch) validate_terminal(ch, RPAR, ")") 999#define validate_semi(ch) validate_terminal(ch, SEMI, ";") 1000#define validate_star(ch) validate_terminal(ch, STAR, "*") 1001#define validate_vbar(ch) validate_terminal(ch, VBAR, "|") 1002#define validate_doublestar(ch) validate_terminal(ch, DOUBLESTAR, "**") 1003#define validate_dot(ch) validate_terminal(ch, DOT, ".") 1004#define validate_at(ch) validate_terminal(ch, AT, "@") 1005#define validate_rarrow(ch) validate_terminal(ch, RARROW, "->") 1006#define validate_name(ch, str) validate_terminal(ch, NAME, str) 1007 1008#define VALIDATER(n) static int validate_##n(node *tree) 1009 1010VALIDATER(node); VALIDATER(small_stmt); 1011VALIDATER(class); VALIDATER(node); 1012VALIDATER(parameters); VALIDATER(suite); 1013VALIDATER(testlist); VALIDATER(varargslist); 1014VALIDATER(vfpdef); 1015VALIDATER(stmt); VALIDATER(simple_stmt); 1016VALIDATER(expr_stmt); VALIDATER(power); 1017VALIDATER(del_stmt); 1018VALIDATER(return_stmt); VALIDATER(raise_stmt); 1019VALIDATER(import_stmt); VALIDATER(import_stmt); 1020VALIDATER(import_name); VALIDATER(yield_stmt); 1021VALIDATER(global_stmt); VALIDATER(nonlocal_stmt); 1022VALIDATER(assert_stmt); 1023VALIDATER(compound_stmt); VALIDATER(test_or_star_expr); 1024VALIDATER(while); VALIDATER(for); 1025VALIDATER(try); VALIDATER(except_clause); 1026VALIDATER(test); VALIDATER(and_test); 1027VALIDATER(not_test); VALIDATER(comparison); 1028VALIDATER(comp_op); 1029VALIDATER(star_expr); VALIDATER(expr); 1030VALIDATER(xor_expr); VALIDATER(and_expr); 1031VALIDATER(shift_expr); VALIDATER(arith_expr); 1032VALIDATER(term); VALIDATER(factor); 1033VALIDATER(atom); VALIDATER(lambdef); 1034VALIDATER(trailer); VALIDATER(subscript); 1035VALIDATER(subscriptlist); VALIDATER(sliceop); 1036VALIDATER(exprlist); VALIDATER(dictorsetmaker); 1037VALIDATER(arglist); VALIDATER(argument); 1038VALIDATER(comp_for); 1039VALIDATER(comp_iter); VALIDATER(comp_if); 1040VALIDATER(testlist_comp); VALIDATER(yield_expr); 1041VALIDATER(or_test); 1042VALIDATER(test_nocond); VALIDATER(lambdef_nocond); 1043VALIDATER(yield_arg); 1044VALIDATER(async_funcdef); VALIDATER(async_stmt); 1045VALIDATER(atom_expr); 1046 1047#undef VALIDATER 1048 1049#define is_even(n) (((n) & 1) == 0) 1050#define is_odd(n) (((n) & 1) == 1) 1051 1052 1053static int 1054validate_ntype(node *n, int t) 1055{ 1056 if (TYPE(n) != t) { 1057 PyErr_Format(parser_error, "Expected node type %d, got %d.", 1058 t, TYPE(n)); 1059 return 0; 1060 } 1061 return 1; 1062} 1063 1064 1065/* Verifies that the number of child nodes is exactly 'num', raising 1066 * an exception if it isn't. The exception message does not indicate 1067 * the exact number of nodes, allowing this to be used to raise the 1068 * "right" exception when the wrong number of nodes is present in a 1069 * specific variant of a statement's syntax. This is commonly used 1070 * in that fashion. 1071 */ 1072static int 1073validate_numnodes(node *n, int num, const char *const name) 1074{ 1075 if (NCH(n) != num) { 1076 PyErr_Format(parser_error, 1077 "Illegal number of children for %s node.", name); 1078 return 0; 1079 } 1080 return 1; 1081} 1082 1083 1084static int 1085validate_terminal(node *terminal, int type, char *string) 1086{ 1087 int res = (validate_ntype(terminal, type) 1088 && ((string == 0) || (strcmp(string, STR(terminal)) == 0))); 1089 1090 if (!res && !PyErr_Occurred()) { 1091 PyErr_Format(parser_error, 1092 "Illegal terminal: expected \"%s\"", string); 1093 } 1094 return (res); 1095} 1096 1097/* X (',' X) [','] */ 1098static int 1099validate_repeating_list_variable(node *tree, 1100 int list_node_type, 1101 int (*validate_child_func_inc)(node *, int *), 1102 int *pos, 1103 const char *const list_node_type_name) 1104{ 1105 int nch = NCH(tree); 1106 int res = (nch && validate_ntype(tree, list_node_type)); 1107 1108 if (!res && !PyErr_Occurred()) { 1109 /* Unconditionally raise. */ 1110 (void) validate_numnodes(tree, 1, list_node_type_name); 1111 } 1112 else { 1113 for ( ; res && *pos < nch; ) { 1114 res = validate_child_func_inc(tree, pos); 1115 if (!res || *pos >= nch) 1116 break; 1117 res = validate_comma(CHILD(tree, (*pos)++)); 1118 } 1119 } 1120 return res; 1121} 1122 1123/* X (',' X) [','] */ 1124static int 1125validate_repeating_list(node *tree, 1126 int list_node_type, 1127 int (*validate_child_func)(node *), 1128 const char *const list_node_type_name) 1129{ 1130 int nch = NCH(tree); 1131 int res = (nch && validate_ntype(tree, list_node_type)); 1132 int pos = 0; 1133 1134 if (!res && !PyErr_Occurred()) { 1135 /* Unconditionally raise. */ 1136 (void) validate_numnodes(tree, 1, list_node_type_name); 1137 } 1138 else { 1139 for ( ; res && pos < nch; ) { 1140 res = validate_child_func(CHILD(tree, pos++)); 1141 if (!res || pos >= nch) 1142 break; 1143 res = validate_comma(CHILD(tree, pos++)); 1144 } 1145 } 1146 return res; 1147} 1148 1149 1150/* validate_class() 1151 * 1152 * classdef: 1153 * 'class' NAME ['(' testlist ')'] ':' suite 1154 */ 1155static int 1156validate_class(node *tree) 1157{ 1158 int nch = NCH(tree); 1159 int res = (validate_ntype(tree, classdef) && 1160 ((nch == 4) || (nch == 6) || (nch == 7))); 1161 1162 if (res) { 1163 res = (validate_name(CHILD(tree, 0), "class") 1164 && validate_ntype(CHILD(tree, 1), NAME) 1165 && validate_colon(CHILD(tree, nch - 2)) 1166 && validate_suite(CHILD(tree, nch - 1))); 1167 } 1168 else { 1169 (void) validate_numnodes(tree, 4, "class"); 1170 } 1171 1172 if (res) { 1173 if (nch == 7) { 1174 res = ((validate_lparen(CHILD(tree, 2)) && 1175 validate_arglist(CHILD(tree, 3)) && 1176 validate_rparen(CHILD(tree, 4)))); 1177 } 1178 else if (nch == 6) { 1179 res = (validate_lparen(CHILD(tree,2)) && 1180 validate_rparen(CHILD(tree,3))); 1181 } 1182 } 1183 return (res); 1184} 1185 1186 1187/* if_stmt: 1188 * 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite] 1189 */ 1190static int 1191validate_if(node *tree) 1192{ 1193 int nch = NCH(tree); 1194 int res = (validate_ntype(tree, if_stmt) 1195 && (nch >= 4) 1196 && validate_name(CHILD(tree, 0), "if") 1197 && validate_test(CHILD(tree, 1)) 1198 && validate_colon(CHILD(tree, 2)) 1199 && validate_suite(CHILD(tree, 3))); 1200 1201 if (res && ((nch % 4) == 3)) { 1202 /* ... 'else' ':' suite */ 1203 res = (validate_name(CHILD(tree, nch - 3), "else") 1204 && validate_colon(CHILD(tree, nch - 2)) 1205 && validate_suite(CHILD(tree, nch - 1))); 1206 nch -= 3; 1207 } 1208 else if (!res && !PyErr_Occurred()) 1209 (void) validate_numnodes(tree, 4, "if"); 1210 if ((nch % 4) != 0) 1211 /* Will catch the case for nch < 4 */ 1212 res = validate_numnodes(tree, 0, "if"); 1213 else if (res && (nch > 4)) { 1214 /* ... ('elif' test ':' suite)+ ... */ 1215 int j = 4; 1216 while ((j < nch) && res) { 1217 res = (validate_name(CHILD(tree, j), "elif") 1218 && validate_colon(CHILD(tree, j + 2)) 1219 && validate_test(CHILD(tree, j + 1)) 1220 && validate_suite(CHILD(tree, j + 3))); 1221 j += 4; 1222 } 1223 } 1224 return (res); 1225} 1226 1227 1228/* parameters: 1229 * '(' [varargslist] ')' 1230 * 1231 */ 1232static int 1233validate_parameters(node *tree) 1234{ 1235 int nch = NCH(tree); 1236 int res = validate_ntype(tree, parameters) && ((nch == 2) || (nch == 3)); 1237 1238 if (res) { 1239 res = (validate_lparen(CHILD(tree, 0)) 1240 && validate_rparen(CHILD(tree, nch - 1))); 1241 if (res && (nch == 3)) 1242 res = validate_varargslist(CHILD(tree, 1)); 1243 } 1244 else { 1245 (void) validate_numnodes(tree, 2, "parameters"); 1246 } 1247 return (res); 1248} 1249 1250 1251/* validate_suite() 1252 * 1253 * suite: 1254 * simple_stmt 1255 * | NEWLINE INDENT stmt+ DEDENT 1256 */ 1257static int 1258validate_suite(node *tree) 1259{ 1260 int nch = NCH(tree); 1261 int res = (validate_ntype(tree, suite) && ((nch == 1) || (nch >= 4))); 1262 1263 if (res && (nch == 1)) 1264 res = validate_simple_stmt(CHILD(tree, 0)); 1265 else if (res) { 1266 /* NEWLINE INDENT stmt+ DEDENT */ 1267 res = (validate_newline(CHILD(tree, 0)) 1268 && validate_indent(CHILD(tree, 1)) 1269 && validate_stmt(CHILD(tree, 2)) 1270 && validate_dedent(CHILD(tree, nch - 1))); 1271 1272 if (res && (nch > 4)) { 1273 int i = 3; 1274 --nch; /* forget the DEDENT */ 1275 for ( ; res && (i < nch); ++i) 1276 res = validate_stmt(CHILD(tree, i)); 1277 } 1278 else if (nch < 4) 1279 res = validate_numnodes(tree, 4, "suite"); 1280 } 1281 return (res); 1282} 1283 1284 1285static int 1286validate_testlist(node *tree) 1287{ 1288 return (validate_repeating_list(tree, testlist, 1289 validate_test, "testlist")); 1290} 1291 1292static int 1293validate_testlist_star_expr(node *tl) 1294{ 1295 return (validate_repeating_list(tl, testlist_star_expr, validate_test_or_star_expr, 1296 "testlist")); 1297} 1298 1299 1300/* validate either vfpdef or tfpdef. 1301 * vfpdef: NAME 1302 * tfpdef: NAME [':' test] 1303 */ 1304static int 1305validate_vfpdef(node *tree) 1306{ 1307 int nch = NCH(tree); 1308 if (TYPE(tree) == vfpdef) { 1309 return nch == 1 && validate_name(CHILD(tree, 0), NULL); 1310 } 1311 else if (TYPE(tree) == tfpdef) { 1312 if (nch == 1) { 1313 return validate_name(CHILD(tree, 0), NULL); 1314 } 1315 else if (nch == 3) { 1316 return validate_name(CHILD(tree, 0), NULL) && 1317 validate_colon(CHILD(tree, 1)) && 1318 validate_test(CHILD(tree, 2)); 1319 } 1320 } 1321 return 0; 1322} 1323 1324/* '*' [vfpdef] (',' vfpdef ['=' test])* [',' '**' vfpdef] | '**' vfpdef 1325 * ..or tfpdef in place of vfpdef. vfpdef: NAME; tfpdef: NAME [':' test] 1326 */ 1327static int 1328validate_varargslist_trailer(node *tree, int start) 1329{ 1330 int nch = NCH(tree); 1331 int res = 0; 1332 1333 if (nch <= start) { 1334 err_string("expected variable argument trailer for varargslist"); 1335 return 0; 1336 } 1337 if (TYPE(CHILD(tree, start)) == STAR) { 1338 /* 1339 * '*' [vfpdef] 1340 */ 1341 res = validate_star(CHILD(tree, start++)); 1342 if (res && start < nch && (TYPE(CHILD(tree, start)) == vfpdef || 1343 TYPE(CHILD(tree, start)) == tfpdef)) 1344 res = validate_vfpdef(CHILD(tree, start++)); 1345 /* 1346 * (',' vfpdef ['=' test])* 1347 */ 1348 while (res && start + 1 < nch && ( 1349 TYPE(CHILD(tree, start + 1)) == vfpdef || 1350 TYPE(CHILD(tree, start + 1)) == tfpdef)) { 1351 res = (validate_comma(CHILD(tree, start++)) 1352 && validate_vfpdef(CHILD(tree, start++))); 1353 if (res && start + 1 < nch && TYPE(CHILD(tree, start)) == EQUAL) 1354 res = (validate_equal(CHILD(tree, start++)) 1355 && validate_test(CHILD(tree, start++))); 1356 } 1357 /* 1358 * [',' '**' vfpdef] 1359 */ 1360 if (res && start + 2 < nch && TYPE(CHILD(tree, start+1)) == DOUBLESTAR) 1361 res = (validate_comma(CHILD(tree, start++)) 1362 && validate_doublestar(CHILD(tree, start++)) 1363 && validate_vfpdef(CHILD(tree, start++))); 1364 } 1365 else if (TYPE(CHILD(tree, start)) == DOUBLESTAR) { 1366 /* 1367 * '**' vfpdef 1368 */ 1369 if (start + 1 < nch) 1370 res = (validate_doublestar(CHILD(tree, start++)) 1371 && validate_vfpdef(CHILD(tree, start++))); 1372 else { 1373 res = 0; 1374 err_string("expected vfpdef after ** in varargslist trailer"); 1375 } 1376 } 1377 else { 1378 res = 0; 1379 err_string("expected * or ** in varargslist trailer"); 1380 } 1381 1382 if (res && start != nch) { 1383 res = 0; 1384 err_string("unexpected extra children in varargslist trailer"); 1385 } 1386 return res; 1387} 1388 1389 1390/* validate_varargslist() 1391 * 1392 * Validate typedargslist or varargslist. 1393 * 1394 * typedargslist: ((tfpdef ['=' test] ',')* 1395 * ('*' [tfpdef] (',' tfpdef ['=' test])* [',' '**' tfpdef] | 1396 * '**' tfpdef) 1397 * | tfpdef ['=' test] (',' tfpdef ['=' test])* [',']) 1398 * tfpdef: NAME [':' test] 1399 * varargslist: ((vfpdef ['=' test] ',')* 1400 * ('*' [vfpdef] (',' vfpdef ['=' test])* [',' '**' vfpdef] | 1401 * '**' vfpdef) 1402 * | vfpdef ['=' test] (',' vfpdef ['=' test])* [',']) 1403 * vfpdef: NAME 1404 * 1405 */ 1406static int 1407validate_varargslist(node *tree) 1408{ 1409 int nch = NCH(tree); 1410 int res = (TYPE(tree) == varargslist || 1411 TYPE(tree) == typedargslist) && 1412 (nch != 0); 1413 int sym; 1414 node *ch; 1415 int i = 0; 1416 1417 if (!res) 1418 return 0; 1419 if (nch < 1) { 1420 err_string("varargslist missing child nodes"); 1421 return 0; 1422 } 1423 while (i < nch) { 1424 ch = CHILD(tree, i); 1425 sym = TYPE(ch); 1426 if (sym == vfpdef || sym == tfpdef) { 1427 /* validate (vfpdef ['=' test] ',')+ */ 1428 res = validate_vfpdef(ch); 1429 ++i; 1430 if (res && (i+2 <= nch) && TYPE(CHILD(tree, i)) == EQUAL) { 1431 res = (validate_equal(CHILD(tree, i)) 1432 && validate_test(CHILD(tree, i+1))); 1433 if (res) 1434 i += 2; 1435 } 1436 if (res && i < nch) { 1437 res = validate_comma(CHILD(tree, i)); 1438 ++i; 1439 } 1440 } else if (sym == DOUBLESTAR || sym == STAR) { 1441 res = validate_varargslist_trailer(tree, i); 1442 break; 1443 } else { 1444 res = 0; 1445 err_string("illegal formation for varargslist"); 1446 } 1447 } 1448 return res; 1449} 1450 1451 1452/* comp_iter: comp_for | comp_if 1453 */ 1454static int 1455validate_comp_iter(node *tree) 1456{ 1457 int res = (validate_ntype(tree, comp_iter) 1458 && validate_numnodes(tree, 1, "comp_iter")); 1459 if (res && TYPE(CHILD(tree, 0)) == comp_for) 1460 res = validate_comp_for(CHILD(tree, 0)); 1461 else 1462 res = validate_comp_if(CHILD(tree, 0)); 1463 1464 return res; 1465} 1466 1467/* comp_for: 'for' exprlist 'in' test [comp_iter] 1468 */ 1469static int 1470validate_comp_for(node *tree) 1471{ 1472 int nch = NCH(tree); 1473 int res; 1474 1475 if (nch == 5) 1476 res = validate_comp_iter(CHILD(tree, 4)); 1477 else 1478 res = validate_numnodes(tree, 4, "comp_for"); 1479 1480 if (res) 1481 res = (validate_name(CHILD(tree, 0), "for") 1482 && validate_exprlist(CHILD(tree, 1)) 1483 && validate_name(CHILD(tree, 2), "in") 1484 && validate_or_test(CHILD(tree, 3))); 1485 1486 return res; 1487} 1488 1489/* comp_if: 'if' test_nocond [comp_iter] 1490 */ 1491static int 1492validate_comp_if(node *tree) 1493{ 1494 int nch = NCH(tree); 1495 int res; 1496 1497 if (nch == 3) 1498 res = validate_comp_iter(CHILD(tree, 2)); 1499 else 1500 res = validate_numnodes(tree, 2, "comp_if"); 1501 1502 if (res) 1503 res = (validate_name(CHILD(tree, 0), "if") 1504 && validate_test_nocond(CHILD(tree, 1))); 1505 1506 return res; 1507} 1508 1509 1510/* simple_stmt | compound_stmt 1511 * 1512 */ 1513static int 1514validate_stmt(node *tree) 1515{ 1516 int res = (validate_ntype(tree, stmt) 1517 && validate_numnodes(tree, 1, "stmt")); 1518 1519 if (res) { 1520 tree = CHILD(tree, 0); 1521 1522 if (TYPE(tree) == simple_stmt) 1523 res = validate_simple_stmt(tree); 1524 else 1525 res = validate_compound_stmt(tree); 1526 } 1527 return (res); 1528} 1529 1530 1531/* small_stmt (';' small_stmt)* [';'] NEWLINE 1532 * 1533 */ 1534static int 1535validate_simple_stmt(node *tree) 1536{ 1537 int nch = NCH(tree); 1538 int res = (validate_ntype(tree, simple_stmt) 1539 && (nch >= 2) 1540 && validate_small_stmt(CHILD(tree, 0)) 1541 && validate_newline(CHILD(tree, nch - 1))); 1542 1543 if (nch < 2) 1544 res = validate_numnodes(tree, 2, "simple_stmt"); 1545 --nch; /* forget the NEWLINE */ 1546 if (res && is_even(nch)) 1547 res = validate_semi(CHILD(tree, --nch)); 1548 if (res && (nch > 2)) { 1549 int i; 1550 1551 for (i = 1; res && (i < nch); i += 2) 1552 res = (validate_semi(CHILD(tree, i)) 1553 && validate_small_stmt(CHILD(tree, i + 1))); 1554 } 1555 return (res); 1556} 1557 1558 1559static int 1560validate_small_stmt(node *tree) 1561{ 1562 int nch = NCH(tree); 1563 int res = validate_numnodes(tree, 1, "small_stmt"); 1564 1565 if (res) { 1566 int ntype = TYPE(CHILD(tree, 0)); 1567 1568 if ( (ntype == expr_stmt) 1569 || (ntype == del_stmt) 1570 || (ntype == pass_stmt) 1571 || (ntype == flow_stmt) 1572 || (ntype == import_stmt) 1573 || (ntype == global_stmt) 1574 || (ntype == nonlocal_stmt) 1575 || (ntype == assert_stmt)) 1576 res = validate_node(CHILD(tree, 0)); 1577 else { 1578 res = 0; 1579 err_string("illegal small_stmt child type"); 1580 } 1581 } 1582 else if (nch == 1) { 1583 res = 0; 1584 PyErr_Format(parser_error, 1585 "Unrecognized child node of small_stmt: %d.", 1586 TYPE(CHILD(tree, 0))); 1587 } 1588 return (res); 1589} 1590 1591 1592/* compound_stmt: 1593 * if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated 1594 */ 1595static int 1596validate_compound_stmt(node *tree) 1597{ 1598 int res = (validate_ntype(tree, compound_stmt) 1599 && validate_numnodes(tree, 1, "compound_stmt")); 1600 int ntype; 1601 1602 if (!res) 1603 return (0); 1604 1605 tree = CHILD(tree, 0); 1606 ntype = TYPE(tree); 1607 if ( (ntype == if_stmt) 1608 || (ntype == while_stmt) 1609 || (ntype == for_stmt) 1610 || (ntype == try_stmt) 1611 || (ntype == with_stmt) 1612 || (ntype == funcdef) 1613 || (ntype == async_stmt) 1614 || (ntype == classdef) 1615 || (ntype == decorated)) 1616 res = validate_node(tree); 1617 else { 1618 res = 0; 1619 PyErr_Format(parser_error, 1620 "Illegal compound statement type: %d.", TYPE(tree)); 1621 } 1622 return (res); 1623} 1624 1625static int 1626validate_yield_or_testlist(node *tree, int tse) 1627{ 1628 if (TYPE(tree) == yield_expr) { 1629 return validate_yield_expr(tree); 1630 } 1631 else { 1632 if (tse) 1633 return validate_testlist_star_expr(tree); 1634 else 1635 return validate_testlist(tree); 1636 } 1637} 1638 1639static int 1640validate_expr_stmt(node *tree) 1641{ 1642 int j; 1643 int nch = NCH(tree); 1644 int res = (validate_ntype(tree, expr_stmt) 1645 && is_odd(nch) 1646 && validate_testlist_star_expr(CHILD(tree, 0))); 1647 1648 if (res && nch == 3 1649 && TYPE(CHILD(tree, 1)) == augassign) { 1650 res = validate_numnodes(CHILD(tree, 1), 1, "augassign") 1651 && validate_yield_or_testlist(CHILD(tree, 2), 0); 1652 1653 if (res) { 1654 char *s = STR(CHILD(CHILD(tree, 1), 0)); 1655 1656 res = (strcmp(s, "+=") == 0 1657 || strcmp(s, "-=") == 0 1658 || strcmp(s, "*=") == 0 1659 || strcmp(s, "/=") == 0 1660 || strcmp(s, "//=") == 0 1661 || strcmp(s, "%=") == 0 1662 || strcmp(s, "&=") == 0 1663 || strcmp(s, "|=") == 0 1664 || strcmp(s, "^=") == 0 1665 || strcmp(s, "<<=") == 0 1666 || strcmp(s, ">>=") == 0 1667 || strcmp(s, "**=") == 0); 1668 if (!res) 1669 err_string("illegal augmented assignment operator"); 1670 } 1671 } 1672 else { 1673 for (j = 1; res && (j < nch); j += 2) 1674 res = validate_equal(CHILD(tree, j)) 1675 && validate_yield_or_testlist(CHILD(tree, j + 1), 1); 1676 } 1677 return (res); 1678} 1679 1680 1681static int 1682validate_del_stmt(node *tree) 1683{ 1684 return (validate_numnodes(tree, 2, "del_stmt") 1685 && validate_name(CHILD(tree, 0), "del") 1686 && validate_exprlist(CHILD(tree, 1))); 1687} 1688 1689 1690static int 1691validate_return_stmt(node *tree) 1692{ 1693 int nch = NCH(tree); 1694 int res = (validate_ntype(tree, return_stmt) 1695 && ((nch == 1) || (nch == 2)) 1696 && validate_name(CHILD(tree, 0), "return")); 1697 1698 if (res && (nch == 2)) 1699 res = validate_testlist(CHILD(tree, 1)); 1700 1701 return (res); 1702} 1703 1704 1705/* 1706 * raise_stmt: 1707 * 1708 * 'raise' [test ['from' test]] 1709 */ 1710static int 1711validate_raise_stmt(node *tree) 1712{ 1713 int nch = NCH(tree); 1714 int res = (validate_ntype(tree, raise_stmt) 1715 && ((nch == 1) || (nch == 2) || (nch == 4))); 1716 1717 if (!res && !PyErr_Occurred()) 1718 (void) validate_numnodes(tree, 2, "raise"); 1719 1720 if (res) { 1721 res = validate_name(CHILD(tree, 0), "raise"); 1722 if (res && (nch >= 2)) 1723 res = validate_test(CHILD(tree, 1)); 1724 if (res && (nch == 4)) { 1725 res = (validate_name(CHILD(tree, 2), "from") 1726 && validate_test(CHILD(tree, 3))); 1727 } 1728 } 1729 return (res); 1730} 1731 1732 1733/* yield_expr: 'yield' [yield_arg] 1734 */ 1735static int 1736validate_yield_expr(node *tree) 1737{ 1738 int nch = NCH(tree); 1739 if (nch < 1 || nch > 2) 1740 return 0; 1741 if (!validate_ntype(tree, yield_expr)) 1742 return 0; 1743 if (!validate_name(CHILD(tree, 0), "yield")) 1744 return 0; 1745 if (nch == 2) { 1746 if (!validate_yield_arg(CHILD(tree, 1))) 1747 return 0; 1748 } 1749 return 1; 1750} 1751 1752/* yield_arg: 'from' test | testlist 1753 */ 1754static int 1755validate_yield_arg(node *tree) 1756{ 1757 int nch = NCH(tree); 1758 if (!validate_ntype(tree, yield_arg)) 1759 return 0; 1760 switch (nch) { 1761 case 1: 1762 if (!validate_testlist(CHILD(tree, nch - 1))) 1763 return 0; 1764 break; 1765 case 2: 1766 if (!validate_name(CHILD(tree, 0), "from")) 1767 return 0; 1768 if (!validate_test(CHILD(tree, 1))) 1769 return 0; 1770 break; 1771 default: 1772 return 0; 1773 } 1774 return 1; 1775} 1776 1777/* yield_stmt: yield_expr 1778 */ 1779static int 1780validate_yield_stmt(node *tree) 1781{ 1782 return (validate_ntype(tree, yield_stmt) 1783 && validate_numnodes(tree, 1, "yield_stmt") 1784 && validate_yield_expr(CHILD(tree, 0))); 1785} 1786 1787 1788static int 1789validate_import_as_name(node *tree) 1790{ 1791 int nch = NCH(tree); 1792 int ok = validate_ntype(tree, import_as_name); 1793 1794 if (ok) { 1795 if (nch == 1) 1796 ok = validate_name(CHILD(tree, 0), NULL); 1797 else if (nch == 3) 1798 ok = (validate_name(CHILD(tree, 0), NULL) 1799 && validate_name(CHILD(tree, 1), "as") 1800 && validate_name(CHILD(tree, 2), NULL)); 1801 else 1802 ok = validate_numnodes(tree, 3, "import_as_name"); 1803 } 1804 return ok; 1805} 1806 1807 1808/* dotted_name: NAME ("." NAME)* 1809 */ 1810static int 1811validate_dotted_name(node *tree) 1812{ 1813 int nch = NCH(tree); 1814 int res = (validate_ntype(tree, dotted_name) 1815 && is_odd(nch) 1816 && validate_name(CHILD(tree, 0), NULL)); 1817 int i; 1818 1819 for (i = 1; res && (i < nch); i += 2) { 1820 res = (validate_dot(CHILD(tree, i)) 1821 && validate_name(CHILD(tree, i+1), NULL)); 1822 } 1823 return res; 1824} 1825 1826 1827/* dotted_as_name: dotted_name [NAME NAME] 1828 */ 1829static int 1830validate_dotted_as_name(node *tree) 1831{ 1832 int nch = NCH(tree); 1833 int res = validate_ntype(tree, dotted_as_name); 1834 1835 if (res) { 1836 if (nch == 1) 1837 res = validate_dotted_name(CHILD(tree, 0)); 1838 else if (nch == 3) 1839 res = (validate_dotted_name(CHILD(tree, 0)) 1840 && validate_name(CHILD(tree, 1), "as") 1841 && validate_name(CHILD(tree, 2), NULL)); 1842 else { 1843 res = 0; 1844 err_string("illegal number of children for dotted_as_name"); 1845 } 1846 } 1847 return res; 1848} 1849 1850 1851/* dotted_as_name (',' dotted_as_name)* */ 1852static int 1853validate_dotted_as_names(node *tree) 1854{ 1855 int nch = NCH(tree); 1856 int res = is_odd(nch) && validate_dotted_as_name(CHILD(tree, 0)); 1857 int i; 1858 1859 for (i = 1; res && (i < nch); i += 2) 1860 res = (validate_comma(CHILD(tree, i)) 1861 && validate_dotted_as_name(CHILD(tree, i + 1))); 1862 return (res); 1863} 1864 1865 1866/* import_as_name (',' import_as_name)* [','] */ 1867static int 1868validate_import_as_names(node *tree) 1869{ 1870 int nch = NCH(tree); 1871 int res = validate_import_as_name(CHILD(tree, 0)); 1872 int i; 1873 1874 for (i = 1; res && (i + 1 < nch); i += 2) 1875 res = (validate_comma(CHILD(tree, i)) 1876 && validate_import_as_name(CHILD(tree, i + 1))); 1877 return (res); 1878} 1879 1880 1881/* 'import' dotted_as_names */ 1882static int 1883validate_import_name(node *tree) 1884{ 1885 return (validate_ntype(tree, import_name) 1886 && validate_numnodes(tree, 2, "import_name") 1887 && validate_name(CHILD(tree, 0), "import") 1888 && validate_dotted_as_names(CHILD(tree, 1))); 1889} 1890 1891/* Helper function to count the number of leading dots (or ellipsis tokens) in 1892 * 'from ...module import name' 1893 */ 1894static int 1895count_from_dots(node *tree) 1896{ 1897 int i; 1898 for (i = 1; i < NCH(tree); i++) 1899 if (TYPE(CHILD(tree, i)) != DOT && TYPE(CHILD(tree, i)) != ELLIPSIS) 1900 break; 1901 return i - 1; 1902} 1903 1904/* import_from: ('from' ('.'* dotted_name | '.'+) 1905 * 'import' ('*' | '(' import_as_names ')' | import_as_names)) 1906 */ 1907static int 1908validate_import_from(node *tree) 1909{ 1910 int nch = NCH(tree); 1911 int ndots = count_from_dots(tree); 1912 int havename = (TYPE(CHILD(tree, ndots + 1)) == dotted_name); 1913 int offset = ndots + havename; 1914 int res = validate_ntype(tree, import_from) 1915 && (offset >= 1) 1916 && (nch >= 3 + offset) 1917 && validate_name(CHILD(tree, 0), "from") 1918 && (!havename || validate_dotted_name(CHILD(tree, ndots + 1))) 1919 && validate_name(CHILD(tree, offset + 1), "import"); 1920 1921 if (res && TYPE(CHILD(tree, offset + 2)) == LPAR) 1922 res = ((nch == offset + 5) 1923 && validate_lparen(CHILD(tree, offset + 2)) 1924 && validate_import_as_names(CHILD(tree, offset + 3)) 1925 && validate_rparen(CHILD(tree, offset + 4))); 1926 else if (res && TYPE(CHILD(tree, offset + 2)) != STAR) 1927 res = validate_import_as_names(CHILD(tree, offset + 2)); 1928 return (res); 1929} 1930 1931 1932/* import_stmt: import_name | import_from */ 1933static int 1934validate_import_stmt(node *tree) 1935{ 1936 int nch = NCH(tree); 1937 int res = validate_numnodes(tree, 1, "import_stmt"); 1938 1939 if (res) { 1940 int ntype = TYPE(CHILD(tree, 0)); 1941 1942 if (ntype == import_name || ntype == import_from) 1943 res = validate_node(CHILD(tree, 0)); 1944 else { 1945 res = 0; 1946 err_string("illegal import_stmt child type"); 1947 } 1948 } 1949 else if (nch == 1) { 1950 res = 0; 1951 PyErr_Format(parser_error, 1952 "Unrecognized child node of import_stmt: %d.", 1953 TYPE(CHILD(tree, 0))); 1954 } 1955 return (res); 1956} 1957 1958 1959/* global_stmt: 1960 * 1961 * 'global' NAME (',' NAME)* 1962 */ 1963static int 1964validate_global_stmt(node *tree) 1965{ 1966 int j; 1967 int nch = NCH(tree); 1968 int res = (validate_ntype(tree, global_stmt) 1969 && is_even(nch) && (nch >= 2)); 1970 1971 if (!res && !PyErr_Occurred()) 1972 err_string("illegal global statement"); 1973 1974 if (res) 1975 res = (validate_name(CHILD(tree, 0), "global") 1976 && validate_ntype(CHILD(tree, 1), NAME)); 1977 for (j = 2; res && (j < nch); j += 2) 1978 res = (validate_comma(CHILD(tree, j)) 1979 && validate_ntype(CHILD(tree, j + 1), NAME)); 1980 1981 return (res); 1982} 1983 1984/* nonlocal_stmt: 1985 * 1986 * 'nonlocal' NAME (',' NAME)* 1987 */ 1988static int 1989validate_nonlocal_stmt(node *tree) 1990{ 1991 int j; 1992 int nch = NCH(tree); 1993 int res = (validate_ntype(tree, nonlocal_stmt) 1994 && is_even(nch) && (nch >= 2)); 1995 1996 if (!res && !PyErr_Occurred()) 1997 err_string("illegal nonlocal statement"); 1998 1999 if (res) 2000 res = (validate_name(CHILD(tree, 0), "nonlocal") 2001 && validate_ntype(CHILD(tree, 1), NAME)); 2002 for (j = 2; res && (j < nch); j += 2) 2003 res = (validate_comma(CHILD(tree, j)) 2004 && validate_ntype(CHILD(tree, j + 1), NAME)); 2005 2006 return res; 2007} 2008 2009/* assert_stmt: 2010 * 2011 * 'assert' test [',' test] 2012 */ 2013static int 2014validate_assert_stmt(node *tree) 2015{ 2016 int nch = NCH(tree); 2017 int res = (validate_ntype(tree, assert_stmt) 2018 && ((nch == 2) || (nch == 4)) 2019 && (validate_name(CHILD(tree, 0), "assert")) 2020 && validate_test(CHILD(tree, 1))); 2021 2022 if (!res && !PyErr_Occurred()) 2023 err_string("illegal assert statement"); 2024 if (res && (nch > 2)) 2025 res = (validate_comma(CHILD(tree, 2)) 2026 && validate_test(CHILD(tree, 3))); 2027 2028 return (res); 2029} 2030 2031 2032static int 2033validate_while(node *tree) 2034{ 2035 int nch = NCH(tree); 2036 int res = (validate_ntype(tree, while_stmt) 2037 && ((nch == 4) || (nch == 7)) 2038 && validate_name(CHILD(tree, 0), "while") 2039 && validate_test(CHILD(tree, 1)) 2040 && validate_colon(CHILD(tree, 2)) 2041 && validate_suite(CHILD(tree, 3))); 2042 2043 if (res && (nch == 7)) 2044 res = (validate_name(CHILD(tree, 4), "else") 2045 && validate_colon(CHILD(tree, 5)) 2046 && validate_suite(CHILD(tree, 6))); 2047 2048 return (res); 2049} 2050 2051 2052static int 2053validate_for(node *tree) 2054{ 2055 int nch = NCH(tree); 2056 int res = (validate_ntype(tree, for_stmt) 2057 && ((nch == 6) || (nch == 9)) 2058 && validate_name(CHILD(tree, 0), "for") 2059 && validate_exprlist(CHILD(tree, 1)) 2060 && validate_name(CHILD(tree, 2), "in") 2061 && validate_testlist(CHILD(tree, 3)) 2062 && validate_colon(CHILD(tree, 4)) 2063 && validate_suite(CHILD(tree, 5))); 2064 2065 if (res && (nch == 9)) 2066 res = (validate_name(CHILD(tree, 6), "else") 2067 && validate_colon(CHILD(tree, 7)) 2068 && validate_suite(CHILD(tree, 8))); 2069 2070 return (res); 2071} 2072 2073 2074/* try_stmt: 2075 * 'try' ':' suite (except_clause ':' suite)+ ['else' ':' suite] 2076 ['finally' ':' suite] 2077 * | 'try' ':' suite 'finally' ':' suite 2078 * 2079 */ 2080static int 2081validate_try(node *tree) 2082{ 2083 int nch = NCH(tree); 2084 int pos = 3; 2085 int res = (validate_ntype(tree, try_stmt) 2086 && (nch >= 6) && ((nch % 3) == 0)); 2087 2088 if (res) 2089 res = (validate_name(CHILD(tree, 0), "try") 2090 && validate_colon(CHILD(tree, 1)) 2091 && validate_suite(CHILD(tree, 2)) 2092 && validate_colon(CHILD(tree, nch - 2)) 2093 && validate_suite(CHILD(tree, nch - 1))); 2094 else if (!PyErr_Occurred()) { 2095 const char* name = "except"; 2096 if (TYPE(CHILD(tree, nch - 3)) != except_clause) 2097 name = STR(CHILD(tree, nch - 3)); 2098 2099 PyErr_Format(parser_error, 2100 "Illegal number of children for try/%s node.", name); 2101 } 2102 /* Handle try/finally statement */ 2103 if (res && (TYPE(CHILD(tree, pos)) == NAME) && 2104 (strcmp(STR(CHILD(tree, pos)), "finally") == 0)) { 2105 res = (validate_numnodes(tree, 6, "try/finally") 2106 && validate_colon(CHILD(tree, 4)) 2107 && validate_suite(CHILD(tree, 5))); 2108 return (res); 2109 } 2110 /* try/except statement: skip past except_clause sections */ 2111 while (res && pos < nch && (TYPE(CHILD(tree, pos)) == except_clause)) { 2112 res = (validate_except_clause(CHILD(tree, pos)) 2113 && validate_colon(CHILD(tree, pos + 1)) 2114 && validate_suite(CHILD(tree, pos + 2))); 2115 pos += 3; 2116 } 2117 /* skip else clause */ 2118 if (res && pos < nch && (TYPE(CHILD(tree, pos)) == NAME) && 2119 (strcmp(STR(CHILD(tree, pos)), "else") == 0)) { 2120 res = (validate_colon(CHILD(tree, pos + 1)) 2121 && validate_suite(CHILD(tree, pos + 2))); 2122 pos += 3; 2123 } 2124 if (res && pos < nch) { 2125 /* last clause must be a finally */ 2126 res = (validate_name(CHILD(tree, pos), "finally") 2127 && validate_numnodes(tree, pos + 3, "try/except/finally") 2128 && validate_colon(CHILD(tree, pos + 1)) 2129 && validate_suite(CHILD(tree, pos + 2))); 2130 } 2131 return (res); 2132} 2133 2134 2135static int 2136validate_except_clause(node *tree) 2137{ 2138 int nch = NCH(tree); 2139 int res = (validate_ntype(tree, except_clause) 2140 && ((nch == 1) || (nch == 2) || (nch == 4)) 2141 && validate_name(CHILD(tree, 0), "except")); 2142 2143 if (res && (nch > 1)) 2144 res = validate_test(CHILD(tree, 1)); 2145 if (res && (nch == 4)) 2146 res = (validate_name(CHILD(tree, 2), "as") 2147 && validate_ntype(CHILD(tree, 3), NAME)); 2148 2149 return (res); 2150} 2151 2152 2153static int 2154validate_test(node *tree) 2155{ 2156 int nch = NCH(tree); 2157 int res = validate_ntype(tree, test) && is_odd(nch); 2158 2159 if (res && (TYPE(CHILD(tree, 0)) == lambdef)) 2160 res = ((nch == 1) 2161 && validate_lambdef(CHILD(tree, 0))); 2162 else if (res) { 2163 res = validate_or_test(CHILD(tree, 0)); 2164 res = (res && (nch == 1 || (nch == 5 && 2165 validate_name(CHILD(tree, 1), "if") && 2166 validate_or_test(CHILD(tree, 2)) && 2167 validate_name(CHILD(tree, 3), "else") && 2168 validate_test(CHILD(tree, 4))))); 2169 } 2170 return (res); 2171} 2172 2173static int 2174validate_test_nocond(node *tree) 2175{ 2176 int nch = NCH(tree); 2177 int res = validate_ntype(tree, test_nocond) && (nch == 1); 2178 2179 if (res && (TYPE(CHILD(tree, 0)) == lambdef_nocond)) 2180 res = (validate_lambdef_nocond(CHILD(tree, 0))); 2181 else if (res) { 2182 res = (validate_or_test(CHILD(tree, 0))); 2183 } 2184 return (res); 2185} 2186 2187static int 2188validate_or_test(node *tree) 2189{ 2190 int nch = NCH(tree); 2191 int res = validate_ntype(tree, or_test) && is_odd(nch); 2192 2193 if (res) { 2194 int pos; 2195 res = validate_and_test(CHILD(tree, 0)); 2196 for (pos = 1; res && (pos < nch); pos += 2) 2197 res = (validate_name(CHILD(tree, pos), "or") 2198 && validate_and_test(CHILD(tree, pos + 1))); 2199 } 2200 return (res); 2201} 2202 2203 2204static int 2205validate_and_test(node *tree) 2206{ 2207 int pos; 2208 int nch = NCH(tree); 2209 int res = (validate_ntype(tree, and_test) 2210 && is_odd(nch) 2211 && validate_not_test(CHILD(tree, 0))); 2212 2213 for (pos = 1; res && (pos < nch); pos += 2) 2214 res = (validate_name(CHILD(tree, pos), "and") 2215 && validate_not_test(CHILD(tree, 0))); 2216 2217 return (res); 2218} 2219 2220 2221static int 2222validate_not_test(node *tree) 2223{ 2224 int nch = NCH(tree); 2225 int res = validate_ntype(tree, not_test) && ((nch == 1) || (nch == 2)); 2226 2227 if (res) { 2228 if (nch == 2) 2229 res = (validate_name(CHILD(tree, 0), "not") 2230 && validate_not_test(CHILD(tree, 1))); 2231 else if (nch == 1) 2232 res = validate_comparison(CHILD(tree, 0)); 2233 } 2234 return (res); 2235} 2236 2237 2238static int 2239validate_comparison(node *tree) 2240{ 2241 int pos; 2242 int nch = NCH(tree); 2243 int res = (validate_ntype(tree, comparison) 2244 && is_odd(nch) 2245 && validate_expr(CHILD(tree, 0))); 2246 2247 for (pos = 1; res && (pos < nch); pos += 2) 2248 res = (validate_comp_op(CHILD(tree, pos)) 2249 && validate_expr(CHILD(tree, pos + 1))); 2250 2251 return (res); 2252} 2253 2254 2255static int 2256validate_comp_op(node *tree) 2257{ 2258 int res = 0; 2259 int nch = NCH(tree); 2260 2261 if (!validate_ntype(tree, comp_op)) 2262 return (0); 2263 if (nch == 1) { 2264 /* 2265 * Only child will be a terminal with a well-defined symbolic name 2266 * or a NAME with a string of either 'is' or 'in' 2267 */ 2268 tree = CHILD(tree, 0); 2269 switch (TYPE(tree)) { 2270 case LESS: 2271 case GREATER: 2272 case EQEQUAL: 2273 case EQUAL: 2274 case LESSEQUAL: 2275 case GREATEREQUAL: 2276 case NOTEQUAL: 2277 res = 1; 2278 break; 2279 case NAME: 2280 res = ((strcmp(STR(tree), "in") == 0) 2281 || (strcmp(STR(tree), "is") == 0)); 2282 if (!res) { 2283 PyErr_Format(parser_error, 2284 "illegal operator '%s'", STR(tree)); 2285 } 2286 break; 2287 default: 2288 err_string("illegal comparison operator type"); 2289 break; 2290 } 2291 } 2292 else if ((res = validate_numnodes(tree, 2, "comp_op")) != 0) { 2293 res = (validate_ntype(CHILD(tree, 0), NAME) 2294 && validate_ntype(CHILD(tree, 1), NAME) 2295 && (((strcmp(STR(CHILD(tree, 0)), "is") == 0) 2296 && (strcmp(STR(CHILD(tree, 1)), "not") == 0)) 2297 || ((strcmp(STR(CHILD(tree, 0)), "not") == 0) 2298 && (strcmp(STR(CHILD(tree, 1)), "in") == 0)))); 2299 if (!res && !PyErr_Occurred()) 2300 err_string("unknown comparison operator"); 2301 } 2302 return (res); 2303} 2304 2305 2306static int 2307validate_star_expr(node *tree) 2308{ 2309 int res = validate_ntype(tree, star_expr); 2310 if (!res) return res; 2311 if (!validate_numnodes(tree, 2, "star_expr")) 2312 return 0; 2313 return validate_ntype(CHILD(tree, 0), STAR) && \ 2314 validate_expr(CHILD(tree, 1)); 2315} 2316 2317 2318static int 2319validate_expr(node *tree) 2320{ 2321 int j; 2322 int nch = NCH(tree); 2323 int res = (validate_ntype(tree, expr) 2324 && is_odd(nch) 2325 && validate_xor_expr(CHILD(tree, 0))); 2326 2327 for (j = 2; res && (j < nch); j += 2) 2328 res = (validate_xor_expr(CHILD(tree, j)) 2329 && validate_vbar(CHILD(tree, j - 1))); 2330 2331 return (res); 2332} 2333 2334 2335static int 2336validate_xor_expr(node *tree) 2337{ 2338 int j; 2339 int nch = NCH(tree); 2340 int res = (validate_ntype(tree, xor_expr) 2341 && is_odd(nch) 2342 && validate_and_expr(CHILD(tree, 0))); 2343 2344 for (j = 2; res && (j < nch); j += 2) 2345 res = (validate_circumflex(CHILD(tree, j - 1)) 2346 && validate_and_expr(CHILD(tree, j))); 2347 2348 return (res); 2349} 2350 2351 2352static int 2353validate_and_expr(node *tree) 2354{ 2355 int pos; 2356 int nch = NCH(tree); 2357 int res = (validate_ntype(tree, and_expr) 2358 && is_odd(nch) 2359 && validate_shift_expr(CHILD(tree, 0))); 2360 2361 for (pos = 1; res && (pos < nch); pos += 2) 2362 res = (validate_ampersand(CHILD(tree, pos)) 2363 && validate_shift_expr(CHILD(tree, pos + 1))); 2364 2365 return (res); 2366} 2367 2368 2369static int 2370validate_chain_two_ops(node *tree, int (*termvalid)(node *), int op1, int op2) 2371 { 2372 int pos = 1; 2373 int nch = NCH(tree); 2374 int res = (is_odd(nch) 2375 && (*termvalid)(CHILD(tree, 0))); 2376 2377 for ( ; res && (pos < nch); pos += 2) { 2378 if (TYPE(CHILD(tree, pos)) != op1) 2379 res = validate_ntype(CHILD(tree, pos), op2); 2380 if (res) 2381 res = (*termvalid)(CHILD(tree, pos + 1)); 2382 } 2383 return (res); 2384} 2385 2386 2387static int 2388validate_shift_expr(node *tree) 2389{ 2390 return (validate_ntype(tree, shift_expr) 2391 && validate_chain_two_ops(tree, validate_arith_expr, 2392 LEFTSHIFT, RIGHTSHIFT)); 2393} 2394 2395 2396static int 2397validate_arith_expr(node *tree) 2398{ 2399 return (validate_ntype(tree, arith_expr) 2400 && validate_chain_two_ops(tree, validate_term, PLUS, MINUS)); 2401} 2402 2403 2404static int 2405validate_term(node *tree) 2406{ 2407 int pos = 1; 2408 int nch = NCH(tree); 2409 int res = (validate_ntype(tree, term) 2410 && is_odd(nch) 2411 && validate_factor(CHILD(tree, 0))); 2412 2413 for ( ; res && (pos < nch); pos += 2) 2414 res = (((TYPE(CHILD(tree, pos)) == STAR) 2415 || (TYPE(CHILD(tree, pos)) == SLASH) 2416 || (TYPE(CHILD(tree, pos)) == DOUBLESLASH) 2417 || (TYPE(CHILD(tree, pos)) == PERCENT)) 2418 && validate_factor(CHILD(tree, pos + 1))); 2419 2420 return (res); 2421} 2422 2423 2424/* factor: 2425 * 2426 * factor: ('+'|'-'|'~') factor | power 2427 */ 2428static int 2429validate_factor(node *tree) 2430{ 2431 int nch = NCH(tree); 2432 int res = (validate_ntype(tree, factor) 2433 && (((nch == 2) 2434 && ((TYPE(CHILD(tree, 0)) == PLUS) 2435 || (TYPE(CHILD(tree, 0)) == MINUS) 2436 || (TYPE(CHILD(tree, 0)) == TILDE)) 2437 && validate_factor(CHILD(tree, 1))) 2438 || ((nch == 1) 2439 && validate_power(CHILD(tree, 0))))); 2440 return (res); 2441} 2442 2443 2444/* power: 2445 * 2446 * power: atom_expr trailer* ['**' factor] 2447 */ 2448static int 2449validate_power(node *tree) 2450{ 2451 int nch = NCH(tree); 2452 int res = (validate_ntype(tree, power) && (nch >= 1) 2453 && validate_atom_expr(CHILD(tree, 0))); 2454 2455 if (nch > 1) { 2456 if (nch != 3) { 2457 err_string("illegal number of nodes for 'power'"); 2458 return (0); 2459 } 2460 res = (validate_doublestar(CHILD(tree, 1)) 2461 && validate_factor(CHILD(tree, 2))); 2462 } 2463 2464 return (res); 2465} 2466 2467 2468/* atom_expr: 2469 * 2470 * atom_expr: [AWAIT] atom trailer* 2471 */ 2472static int 2473validate_atom_expr(node *tree) 2474{ 2475 int start = 0; 2476 int nch = NCH(tree); 2477 int res; 2478 int pos; 2479 2480 res = validate_ntype(tree, atom_expr) && (nch >= 1); 2481 if (!res) { 2482 return (res); 2483 } 2484 2485 if (TYPE(CHILD(tree, 0)) == AWAIT) { 2486 start = 1; 2487 if (nch < 2) { 2488 err_string("illegal number of nodes for 'atom_expr'"); 2489 return (0); 2490 } 2491 } 2492 2493 res = validate_atom(CHILD(tree, start)); 2494 if (res) { 2495 pos = start + 1; 2496 while (res && (pos < nch) && (TYPE(CHILD(tree, pos)) == trailer)) 2497 res = validate_trailer(CHILD(tree, pos++)); 2498 } 2499 2500 return (res); 2501} 2502 2503 2504static int 2505validate_atom(node *tree) 2506{ 2507 int pos; 2508 int nch = NCH(tree); 2509 int res = validate_ntype(tree, atom); 2510 2511 if (res && nch < 1) 2512 res = validate_numnodes(tree, nch+1, "atom"); 2513 if (res) { 2514 switch (TYPE(CHILD(tree, 0))) { 2515 case LPAR: 2516 res = ((nch <= 3) 2517 && (validate_rparen(CHILD(tree, nch - 1)))); 2518 2519 if (res && (nch == 3)) { 2520 if (TYPE(CHILD(tree, 1))==yield_expr) 2521 res = validate_yield_expr(CHILD(tree, 1)); 2522 else 2523 res = validate_testlist_comp(CHILD(tree, 1)); 2524 } 2525 break; 2526 case LSQB: 2527 if (nch == 2) 2528 res = validate_ntype(CHILD(tree, 1), RSQB); 2529 else if (nch == 3) 2530 res = (validate_testlist_comp(CHILD(tree, 1)) 2531 && validate_ntype(CHILD(tree, 2), RSQB)); 2532 else { 2533 res = 0; 2534 err_string("illegal list display atom"); 2535 } 2536 break; 2537 case LBRACE: 2538 res = ((nch <= 3) 2539 && validate_ntype(CHILD(tree, nch - 1), RBRACE)); 2540 2541 if (res && (nch == 3)) 2542 res = validate_dictorsetmaker(CHILD(tree, 1)); 2543 break; 2544 case NAME: 2545 case NUMBER: 2546 case ELLIPSIS: 2547 res = (nch == 1); 2548 break; 2549 case STRING: 2550 for (pos = 1; res && (pos < nch); ++pos) 2551 res = validate_ntype(CHILD(tree, pos), STRING); 2552 break; 2553 default: 2554 res = 0; 2555 break; 2556 } 2557 } 2558 return (res); 2559} 2560 2561 2562/* testlist_comp: 2563 * (test|star_expr) ( comp_for | (',' (test|star_expr))* [','] ) 2564 */ 2565static int 2566validate_testlist_comp(node *tree) 2567{ 2568 int nch = NCH(tree); 2569 int ok; 2570 2571 if (nch == 0) { 2572 err_string("missing child nodes of testlist_comp"); 2573 return 0; 2574 } 2575 2576 if (nch == 2 && TYPE(CHILD(tree, 1)) == comp_for) { 2577 ok = (validate_test(CHILD(tree, 0)) 2578 && validate_comp_for(CHILD(tree, 1))); 2579 } 2580 else { 2581 ok = validate_repeating_list(tree, 2582 testlist_comp, 2583 validate_test_or_star_expr, 2584 "testlist_comp"); 2585 } 2586 return ok; 2587} 2588 2589/* decorator: 2590 * '@' dotted_name [ '(' [arglist] ')' ] NEWLINE 2591 */ 2592static int 2593validate_decorator(node *tree) 2594{ 2595 int ok; 2596 int nch = NCH(tree); 2597 ok = (validate_ntype(tree, decorator) && 2598 (nch == 3 || nch == 5 || nch == 6) && 2599 validate_at(CHILD(tree, 0)) && 2600 validate_dotted_name(CHILD(tree, 1)) && 2601 validate_newline(RCHILD(tree, -1))); 2602 2603 if (ok && nch != 3) { 2604 ok = (validate_lparen(CHILD(tree, 2)) && 2605 validate_rparen(RCHILD(tree, -2))); 2606 2607 if (ok && nch == 6) 2608 ok = validate_arglist(CHILD(tree, 3)); 2609 } 2610 2611 return ok; 2612} 2613 2614/* decorators: 2615 * decorator+ 2616 */ 2617static int 2618validate_decorators(node *tree) 2619{ 2620 int i, nch, ok; 2621 nch = NCH(tree); 2622 ok = validate_ntype(tree, decorators) && nch >= 1; 2623 2624 for (i = 0; ok && i < nch; ++i) 2625 ok = validate_decorator(CHILD(tree, i)); 2626 2627 return ok; 2628} 2629 2630/* with_item: 2631 * test ['as' expr] 2632 */ 2633static int 2634validate_with_item(node *tree) 2635{ 2636 int nch = NCH(tree); 2637 int ok = (validate_ntype(tree, with_item) 2638 && (nch == 1 || nch == 3) 2639 && validate_test(CHILD(tree, 0))); 2640 if (ok && nch == 3) 2641 ok = (validate_name(CHILD(tree, 1), "as") 2642 && validate_expr(CHILD(tree, 2))); 2643 return ok; 2644} 2645 2646/* with_stmt: 2647 * 0 1 ... -2 -1 2648 * 'with' with_item (',' with_item)* ':' suite 2649 */ 2650static int 2651validate_with_stmt(node *tree) 2652{ 2653 int i; 2654 int nch = NCH(tree); 2655 int ok = (validate_ntype(tree, with_stmt) 2656 && (nch % 2 == 0) 2657 && validate_name(CHILD(tree, 0), "with") 2658 && validate_colon(RCHILD(tree, -2)) 2659 && validate_suite(RCHILD(tree, -1))); 2660 for (i = 1; ok && i < nch - 2; i += 2) 2661 ok = validate_with_item(CHILD(tree, i)); 2662 return ok; 2663} 2664 2665/* funcdef: 'def' NAME parameters ['->' test] ':' suite */ 2666 2667static int 2668validate_funcdef(node *tree) 2669{ 2670 int nch = NCH(tree); 2671 int res = validate_ntype(tree, funcdef); 2672 if (res) { 2673 if (nch == 5) { 2674 res = (validate_name(CHILD(tree, 0), "def") 2675 && validate_ntype(CHILD(tree, 1), NAME) 2676 && validate_parameters(CHILD(tree, 2)) 2677 && validate_colon(CHILD(tree, 3)) 2678 && validate_suite(CHILD(tree, 4))); 2679 } 2680 else if (nch == 7) { 2681 res = (validate_name(CHILD(tree, 0), "def") 2682 && validate_ntype(CHILD(tree, 1), NAME) 2683 && validate_parameters(CHILD(tree, 2)) 2684 && validate_rarrow(CHILD(tree, 3)) 2685 && validate_test(CHILD(tree, 4)) 2686 && validate_colon(CHILD(tree, 5)) 2687 && validate_suite(CHILD(tree, 6))); 2688 } 2689 else { 2690 res = 0; 2691 err_string("illegal number of children for funcdef"); 2692 } 2693 } 2694 return res; 2695} 2696 2697/* async_funcdef: ASYNC funcdef */ 2698 2699static int 2700validate_async_funcdef(node *tree) 2701{ 2702 int nch = NCH(tree); 2703 int res = validate_ntype(tree, async_funcdef); 2704 if (res) { 2705 if (nch == 2) { 2706 res = (validate_ntype(CHILD(tree, 0), ASYNC) 2707 && validate_funcdef(CHILD(tree, 1))); 2708 } 2709 else { 2710 res = 0; 2711 err_string("illegal number of children for async_funcdef"); 2712 } 2713 } 2714 return res; 2715} 2716 2717 2718/* async_stmt: ASYNC (funcdef | with_stmt | for_stmt) */ 2719 2720static int 2721validate_async_stmt(node *tree) 2722{ 2723 int nch = NCH(tree); 2724 int res = (validate_ntype(tree, async_stmt) 2725 && validate_ntype(CHILD(tree, 0), ASYNC)); 2726 2727 if (nch != 2) { 2728 res = 0; 2729 err_string("illegal number of children for async_stmt"); 2730 } else { 2731 if (TYPE(CHILD(tree, 1)) == funcdef) { 2732 res = validate_funcdef(CHILD(tree, 1)); 2733 } 2734 else if (TYPE(CHILD(tree, 1)) == with_stmt) { 2735 res = validate_with_stmt(CHILD(tree, 1)); 2736 } 2737 else if (TYPE(CHILD(tree, 1)) == for_stmt) { 2738 res = validate_for(CHILD(tree, 1)); 2739 } 2740 } 2741 2742 return res; 2743} 2744 2745 2746 2747/* decorated 2748 * decorators (classdef | funcdef) 2749 */ 2750static int 2751validate_decorated(node *tree) 2752{ 2753 int nch = NCH(tree); 2754 int ok = (validate_ntype(tree, decorated) 2755 && (nch == 2) 2756 && validate_decorators(RCHILD(tree, -2))); 2757 if (TYPE(RCHILD(tree, -1)) == funcdef) 2758 ok = ok && validate_funcdef(RCHILD(tree, -1)); 2759 else 2760 ok = ok && validate_class(RCHILD(tree, -1)); 2761 return ok; 2762} 2763 2764static int 2765validate_lambdef(node *tree) 2766{ 2767 int nch = NCH(tree); 2768 int res = (validate_ntype(tree, lambdef) 2769 && ((nch == 3) || (nch == 4)) 2770 && validate_name(CHILD(tree, 0), "lambda") 2771 && validate_colon(CHILD(tree, nch - 2)) 2772 && validate_test(CHILD(tree, nch - 1))); 2773 2774 if (res && (nch == 4)) 2775 res = validate_varargslist(CHILD(tree, 1)); 2776 else if (!res && !PyErr_Occurred()) 2777 (void) validate_numnodes(tree, 3, "lambdef"); 2778 2779 return (res); 2780} 2781 2782 2783static int 2784validate_lambdef_nocond(node *tree) 2785{ 2786 int nch = NCH(tree); 2787 int res = (validate_ntype(tree, lambdef_nocond) 2788 && ((nch == 3) || (nch == 4)) 2789 && validate_name(CHILD(tree, 0), "lambda") 2790 && validate_colon(CHILD(tree, nch - 2)) 2791 && validate_test(CHILD(tree, nch - 1))); 2792 2793 if (res && (nch == 4)) 2794 res = validate_varargslist(CHILD(tree, 1)); 2795 else if (!res && !PyErr_Occurred()) 2796 (void) validate_numnodes(tree, 3, "lambdef_nocond"); 2797 2798 return (res); 2799} 2800 2801 2802/* arglist: 2803 * 2804 * (argument ',')* (argument [','] | '*' test [',' '**' test] | '**' test) 2805 */ 2806static int 2807validate_arglist(node *tree) 2808{ 2809 int nch = NCH(tree); 2810 int i = 0; 2811 int ok = 1; 2812 2813 if (nch <= 0) 2814 /* raise the right error from having an invalid number of children */ 2815 return validate_numnodes(tree, nch + 1, "arglist"); 2816 2817 if (nch > 1) { 2818 for (i=0; i<nch; i++) { 2819 if (TYPE(CHILD(tree, i)) == argument) { 2820 node *ch = CHILD(tree, i); 2821 if (NCH(ch) == 2 && TYPE(CHILD(ch, 1)) == comp_for) { 2822 err_string("need '(', ')' for generator expression"); 2823 return 0; 2824 } 2825 } 2826 } 2827 } 2828 2829 while (ok && nch-i >= 2) { 2830 /* skip leading (argument ',') */ 2831 ok = (validate_argument(CHILD(tree, i)) 2832 && validate_comma(CHILD(tree, i+1))); 2833 if (ok) 2834 i += 2; 2835 else 2836 PyErr_Clear(); 2837 } 2838 ok = 1; 2839 if (nch-i > 0) { 2840 int sym = TYPE(CHILD(tree, i)); 2841 2842 if (sym == argument) { 2843 ok = validate_argument(CHILD(tree, i)); 2844 if (ok && i+1 != nch) { 2845 err_string("illegal arglist specification" 2846 " (extra stuff on end)"); 2847 ok = 0; 2848 } 2849 } 2850 else { 2851 err_string("illegal arglist specification"); 2852 ok = 0; 2853 } 2854 } 2855 return (ok); 2856} 2857 2858 2859 2860/* argument: ( test [comp_for] | 2861 * test '=' test | 2862 * '**' expr | 2863 * star_expr ) 2864 */ 2865static int 2866validate_argument(node *tree) 2867{ 2868 int nch = NCH(tree); 2869 int res = (validate_ntype(tree, argument) 2870 && ((nch == 1) || (nch == 2) || (nch == 3))); 2871 2872 if (res) { 2873 if (TYPE(CHILD(tree, 0)) == DOUBLESTAR) { 2874 res = validate_expr(CHILD(tree, 1)); 2875 } 2876 else if (nch == 1) { 2877 res = validate_test_or_star_expr(CHILD(tree, 0)); 2878 } 2879 else if (nch == 2) { 2880 res = (validate_test(CHILD(tree, 0)) 2881 && validate_comp_for(CHILD(tree, 1))); 2882 } 2883 else if (res && (nch == 3)) { 2884 res = (validate_test(CHILD(tree, 0)) 2885 && validate_equal(CHILD(tree, 1)) 2886 && validate_test(CHILD(tree, 2))); 2887 } 2888 } 2889 return (res); 2890} 2891 2892 2893 2894/* trailer: 2895 * 2896 * '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME 2897 */ 2898static int 2899validate_trailer(node *tree) 2900{ 2901 int nch = NCH(tree); 2902 int res = validate_ntype(tree, trailer) && ((nch == 2) || (nch == 3)); 2903 2904 if (res) { 2905 switch (TYPE(CHILD(tree, 0))) { 2906 case LPAR: 2907 res = validate_rparen(CHILD(tree, nch - 1)); 2908 if (res && (nch == 3)) 2909 res = validate_arglist(CHILD(tree, 1)); 2910 break; 2911 case LSQB: 2912 res = (validate_numnodes(tree, 3, "trailer") 2913 && validate_subscriptlist(CHILD(tree, 1)) 2914 && validate_ntype(CHILD(tree, 2), RSQB)); 2915 break; 2916 case DOT: 2917 res = (validate_numnodes(tree, 2, "trailer") 2918 && validate_ntype(CHILD(tree, 1), NAME)); 2919 break; 2920 default: 2921 res = 0; 2922 break; 2923 } 2924 } 2925 else { 2926 (void) validate_numnodes(tree, 2, "trailer"); 2927 } 2928 return (res); 2929} 2930 2931 2932/* subscriptlist: 2933 * 2934 * subscript (',' subscript)* [','] 2935 */ 2936static int 2937validate_subscriptlist(node *tree) 2938{ 2939 return (validate_repeating_list(tree, subscriptlist, 2940 validate_subscript, "subscriptlist")); 2941} 2942 2943 2944/* subscript: 2945 * 2946 * '.' '.' '.' | test | [test] ':' [test] [sliceop] 2947 */ 2948static int 2949validate_subscript(node *tree) 2950{ 2951 int offset = 0; 2952 int nch = NCH(tree); 2953 int res = validate_ntype(tree, subscript) && (nch >= 1) && (nch <= 4); 2954 2955 if (!res) { 2956 if (!PyErr_Occurred()) 2957 err_string("invalid number of arguments for subscript node"); 2958 return (0); 2959 } 2960 if (TYPE(CHILD(tree, 0)) == DOT) 2961 /* take care of ('.' '.' '.') possibility */ 2962 return (validate_numnodes(tree, 3, "subscript") 2963 && validate_dot(CHILD(tree, 0)) 2964 && validate_dot(CHILD(tree, 1)) 2965 && validate_dot(CHILD(tree, 2))); 2966 if (nch == 1) { 2967 if (TYPE(CHILD(tree, 0)) == test) 2968 res = validate_test(CHILD(tree, 0)); 2969 else 2970 res = validate_colon(CHILD(tree, 0)); 2971 return (res); 2972 } 2973 /* Must be [test] ':' [test] [sliceop], 2974 * but at least one of the optional components will 2975 * be present, but we don't know which yet. 2976 */ 2977 if ((TYPE(CHILD(tree, 0)) != COLON) || (nch == 4)) { 2978 res = validate_test(CHILD(tree, 0)); 2979 offset = 1; 2980 } 2981 if (res) 2982 res = validate_colon(CHILD(tree, offset)); 2983 if (res) { 2984 int rem = nch - ++offset; 2985 if (rem) { 2986 if (TYPE(CHILD(tree, offset)) == test) { 2987 res = validate_test(CHILD(tree, offset)); 2988 ++offset; 2989 --rem; 2990 } 2991 if (res && rem) 2992 res = validate_sliceop(CHILD(tree, offset)); 2993 } 2994 } 2995 return (res); 2996} 2997 2998 2999static int 3000validate_sliceop(node *tree) 3001{ 3002 int nch = NCH(tree); 3003 int res = ((nch == 1) || validate_numnodes(tree, 2, "sliceop")) 3004 && validate_ntype(tree, sliceop); 3005 if (!res && !PyErr_Occurred()) { 3006 res = validate_numnodes(tree, 1, "sliceop"); 3007 } 3008 if (res) 3009 res = validate_colon(CHILD(tree, 0)); 3010 if (res && (nch == 2)) 3011 res = validate_test(CHILD(tree, 1)); 3012 3013 return (res); 3014} 3015 3016 3017static int 3018validate_test_or_star_expr(node *n) 3019{ 3020 if (TYPE(n) == test) 3021 return validate_test(n); 3022 return validate_star_expr(n); 3023} 3024 3025static int 3026validate_expr_or_star_expr(node *n) 3027{ 3028 if (TYPE(n) == expr) 3029 return validate_expr(n); 3030 return validate_star_expr(n); 3031} 3032 3033 3034static int 3035validate_exprlist(node *tree) 3036{ 3037 return (validate_repeating_list(tree, exprlist, 3038 validate_expr_or_star_expr, "exprlist")); 3039} 3040 3041/* Incrementing validate functions returns nonzero iff success (like other 3042 * validate functions, and advance *i by the length of the matched pattern. */ 3043 3044/* test ':' test */ 3045static int 3046validate_test_colon_test_inc(node *tree, int *i) 3047{ 3048 return (validate_test(CHILD(tree, (*i)++)) 3049 && validate_colon(CHILD(tree, (*i)++)) 3050 && validate_test(CHILD(tree, (*i)++))); 3051} 3052 3053/* test ':' test | '**' expr */ 3054static int 3055validate_dict_element_inc(node *tree, int *i) 3056{ 3057 int nch = NCH(tree); 3058 int res = 0; 3059 if (nch - *i >= 2) { 3060 if (TYPE(CHILD(tree, *i+1)) == COLON) { 3061 /* test ':' test */ 3062 res = validate_test_colon_test_inc(tree, i); 3063 } else { 3064 /* '**' expr */ 3065 res = (validate_doublestar(CHILD(tree, (*i)++)) 3066 && validate_expr(CHILD(tree, (*i)++))); 3067 } 3068 } 3069 return res; 3070} 3071 3072/* 3073 * dictorsetmaker: 3074 * 3075 * ( ((test ':' test | '**' expr) 3076 * (comp_for | (',' (test ':' test | '**' expr))* [','])) | 3077 * ((test | '*' test) 3078 * (comp_for | (',' (test | '*' test))* [','])) ) 3079 */ 3080static int 3081validate_dictorsetmaker(node *tree) 3082{ 3083 int nch = NCH(tree); 3084 int res; 3085 int i = 0; 3086 3087 res = validate_ntype(tree, dictorsetmaker); 3088 if (!res) 3089 return 0; 3090 3091 if (nch - i < 1) { 3092 /* Unconditionally raise. */ 3093 (void) validate_numnodes(tree, 1, "dictorsetmaker"); 3094 return 0; 3095 } 3096 3097 if (nch - i >= 2 3098 && ((TYPE(CHILD(tree, i+1)) == COLON) || 3099 (TYPE(CHILD(tree, i)) == DOUBLESTAR))) { 3100 /* Dictionary display or dictionary comprehension. */ 3101 if (nch - i >= 4 && TYPE(CHILD(tree, i+3)) == comp_for) { 3102 /* Dictionary comprehension. */ 3103 res = (validate_test_colon_test_inc(tree, &i) 3104 && validate_comp_for(CHILD(tree, i++))); 3105 if (!res) 3106 return 0; 3107 } else { 3108 /* Dictionary display. */ 3109 return validate_repeating_list_variable( 3110 tree, 3111 dictorsetmaker, 3112 validate_dict_element_inc, 3113 &i, 3114 "dictorsetmaker"); 3115 } 3116 } else { 3117 /* Set display or set comprehension. */ 3118 if (nch - i >= 2 && TYPE(CHILD(tree, i + 1)) == comp_for) { 3119 /* Set comprehension. */ 3120 res = (validate_test(CHILD(tree, i++)) 3121 && validate_comp_for(CHILD(tree, i++))); 3122 if (!res) 3123 return 0; 3124 } else { 3125 /* Set display. */ 3126 return validate_repeating_list(tree, 3127 dictorsetmaker, 3128 validate_test_or_star_expr, 3129 "dictorsetmaker"); 3130 } 3131 } 3132 3133 if (nch - i > 0) { 3134 err_string("Illegal trailing nodes for dictorsetmaker."); 3135 return 0; 3136 } 3137 3138 return 1; 3139} 3140 3141 3142static int 3143validate_eval_input(node *tree) 3144{ 3145 int pos; 3146 int nch = NCH(tree); 3147 int res = (validate_ntype(tree, eval_input) 3148 && (nch >= 2) 3149 && validate_testlist(CHILD(tree, 0)) 3150 && validate_ntype(CHILD(tree, nch - 1), ENDMARKER)); 3151 3152 for (pos = 1; res && (pos < (nch - 1)); ++pos) 3153 res = validate_ntype(CHILD(tree, pos), NEWLINE); 3154 3155 return (res); 3156} 3157 3158 3159static int 3160validate_node(node *tree) 3161{ 3162 int nch = 0; /* num. children on current node */ 3163 int res = 1; /* result value */ 3164 node* next = 0; /* node to process after this one */ 3165 3166 while (res && (tree != 0)) { 3167 nch = NCH(tree); 3168 next = 0; 3169 switch (TYPE(tree)) { 3170 /* 3171 * Definition nodes. 3172 */ 3173 case async_funcdef: 3174 res = validate_async_funcdef(tree); 3175 break; 3176 case async_stmt: 3177 res = validate_async_stmt(tree); 3178 break; 3179 case funcdef: 3180 res = validate_funcdef(tree); 3181 break; 3182 case with_stmt: 3183 res = validate_with_stmt(tree); 3184 break; 3185 case classdef: 3186 res = validate_class(tree); 3187 break; 3188 case decorated: 3189 res = validate_decorated(tree); 3190 break; 3191 /* 3192 * "Trivial" parse tree nodes. 3193 * (Why did I call these trivial?) 3194 */ 3195 case stmt: 3196 res = validate_stmt(tree); 3197 break; 3198 case small_stmt: 3199 /* 3200 * expr_stmt | del_stmt | pass_stmt | flow_stmt | 3201 * import_stmt | global_stmt | nonlocal_stmt | assert_stmt 3202 */ 3203 res = validate_small_stmt(tree); 3204 break; 3205 case flow_stmt: 3206 res = (validate_numnodes(tree, 1, "flow_stmt") 3207 && ((TYPE(CHILD(tree, 0)) == break_stmt) 3208 || (TYPE(CHILD(tree, 0)) == continue_stmt) 3209 || (TYPE(CHILD(tree, 0)) == yield_stmt) 3210 || (TYPE(CHILD(tree, 0)) == return_stmt) 3211 || (TYPE(CHILD(tree, 0)) == raise_stmt))); 3212 if (res) 3213 next = CHILD(tree, 0); 3214 else if (nch == 1) 3215 err_string("illegal flow_stmt type"); 3216 break; 3217 case yield_stmt: 3218 res = validate_yield_stmt(tree); 3219 break; 3220 /* 3221 * Compound statements. 3222 */ 3223 case simple_stmt: 3224 res = validate_simple_stmt(tree); 3225 break; 3226 case compound_stmt: 3227 res = validate_compound_stmt(tree); 3228 break; 3229 /* 3230 * Fundamental statements. 3231 */ 3232 case expr_stmt: 3233 res = validate_expr_stmt(tree); 3234 break; 3235 case del_stmt: 3236 res = validate_del_stmt(tree); 3237 break; 3238 case pass_stmt: 3239 res = (validate_numnodes(tree, 1, "pass") 3240 && validate_name(CHILD(tree, 0), "pass")); 3241 break; 3242 case break_stmt: 3243 res = (validate_numnodes(tree, 1, "break") 3244 && validate_name(CHILD(tree, 0), "break")); 3245 break; 3246 case continue_stmt: 3247 res = (validate_numnodes(tree, 1, "continue") 3248 && validate_name(CHILD(tree, 0), "continue")); 3249 break; 3250 case return_stmt: 3251 res = validate_return_stmt(tree); 3252 break; 3253 case raise_stmt: 3254 res = validate_raise_stmt(tree); 3255 break; 3256 case import_stmt: 3257 res = validate_import_stmt(tree); 3258 break; 3259 case import_name: 3260 res = validate_import_name(tree); 3261 break; 3262 case import_from: 3263 res = validate_import_from(tree); 3264 break; 3265 case global_stmt: 3266 res = validate_global_stmt(tree); 3267 break; 3268 case nonlocal_stmt: 3269 res = validate_nonlocal_stmt(tree); 3270 break; 3271 case assert_stmt: 3272 res = validate_assert_stmt(tree); 3273 break; 3274 case if_stmt: 3275 res = validate_if(tree); 3276 break; 3277 case while_stmt: 3278 res = validate_while(tree); 3279 break; 3280 case for_stmt: 3281 res = validate_for(tree); 3282 break; 3283 case try_stmt: 3284 res = validate_try(tree); 3285 break; 3286 case suite: 3287 res = validate_suite(tree); 3288 break; 3289 /* 3290 * Expression nodes. 3291 */ 3292 case testlist: 3293 res = validate_testlist(tree); 3294 break; 3295 case yield_expr: 3296 res = validate_yield_expr(tree); 3297 break; 3298 case test: 3299 res = validate_test(tree); 3300 break; 3301 case and_test: 3302 res = validate_and_test(tree); 3303 break; 3304 case not_test: 3305 res = validate_not_test(tree); 3306 break; 3307 case comparison: 3308 res = validate_comparison(tree); 3309 break; 3310 case exprlist: 3311 res = validate_exprlist(tree); 3312 break; 3313 case comp_op: 3314 res = validate_comp_op(tree); 3315 break; 3316 case expr: 3317 res = validate_expr(tree); 3318 break; 3319 case xor_expr: 3320 res = validate_xor_expr(tree); 3321 break; 3322 case and_expr: 3323 res = validate_and_expr(tree); 3324 break; 3325 case shift_expr: 3326 res = validate_shift_expr(tree); 3327 break; 3328 case arith_expr: 3329 res = validate_arith_expr(tree); 3330 break; 3331 case term: 3332 res = validate_term(tree); 3333 break; 3334 case factor: 3335 res = validate_factor(tree); 3336 break; 3337 case power: 3338 res = validate_power(tree); 3339 break; 3340 case atom: 3341 res = validate_atom(tree); 3342 break; 3343 3344 default: 3345 /* Hopefully never reached! */ 3346 err_string("unrecognized node type"); 3347 res = 0; 3348 break; 3349 } 3350 tree = next; 3351 } 3352 return (res); 3353} 3354 3355 3356static int 3357validate_expr_tree(node *tree) 3358{ 3359 int res = validate_eval_input(tree); 3360 3361 if (!res && !PyErr_Occurred()) 3362 err_string("could not validate expression tuple"); 3363 3364 return (res); 3365} 3366 3367 3368/* file_input: 3369 * (NEWLINE | stmt)* ENDMARKER 3370 */ 3371static int 3372validate_file_input(node *tree) 3373{ 3374 int j; 3375 int nch = NCH(tree) - 1; 3376 int res = ((nch >= 0) 3377 && validate_ntype(CHILD(tree, nch), ENDMARKER)); 3378 3379 for (j = 0; res && (j < nch); ++j) { 3380 if (TYPE(CHILD(tree, j)) == stmt) 3381 res = validate_stmt(CHILD(tree, j)); 3382 else 3383 res = validate_newline(CHILD(tree, j)); 3384 } 3385 /* This stays in to prevent any internal failures from getting to the 3386 * user. Hopefully, this won't be needed. If a user reports getting 3387 * this, we have some debugging to do. 3388 */ 3389 if (!res && !PyErr_Occurred()) 3390 err_string("VALIDATION FAILURE: report this to the maintainer!"); 3391 3392 return (res); 3393} 3394 3395static int 3396validate_encoding_decl(node *tree) 3397{ 3398 int nch = NCH(tree); 3399 int res = ((nch == 1) 3400 && validate_file_input(CHILD(tree, 0))); 3401 3402 if (!res && !PyErr_Occurred()) 3403 err_string("Error Parsing encoding_decl"); 3404 3405 return res; 3406} 3407 3408static PyObject* 3409pickle_constructor = NULL; 3410 3411 3412static PyObject* 3413parser__pickler(PyObject *self, PyObject *args) 3414{ 3415 NOTE(ARGUNUSED(self)) 3416 PyObject *result = NULL; 3417 PyObject *st = NULL; 3418 PyObject *empty_dict = NULL; 3419 3420 if (PyArg_ParseTuple(args, "O!:_pickler", &PyST_Type, &st)) { 3421 PyObject *newargs; 3422 PyObject *tuple; 3423 3424 if ((empty_dict = PyDict_New()) == NULL) 3425 goto finally; 3426 if ((newargs = Py_BuildValue("Oi", st, 1)) == NULL) 3427 goto finally; 3428 tuple = parser_st2tuple((PyST_Object*)NULL, newargs, empty_dict); 3429 if (tuple != NULL) { 3430 result = Py_BuildValue("O(O)", pickle_constructor, tuple); 3431 Py_DECREF(tuple); 3432 } 3433 Py_DECREF(empty_dict); 3434 Py_DECREF(newargs); 3435 } 3436 finally: 3437 Py_XDECREF(empty_dict); 3438 3439 return (result); 3440} 3441 3442 3443/* Functions exported by this module. Most of this should probably 3444 * be converted into an ST object with methods, but that is better 3445 * done directly in Python, allowing subclasses to be created directly. 3446 * We'd really have to write a wrapper around it all anyway to allow 3447 * inheritance. 3448 */ 3449static PyMethodDef parser_functions[] = { 3450 {"compilest", (PyCFunction)parser_compilest, PUBLIC_METHOD_TYPE, 3451 PyDoc_STR("Compiles an ST object into a code object.")}, 3452 {"expr", (PyCFunction)parser_expr, PUBLIC_METHOD_TYPE, 3453 PyDoc_STR("Creates an ST object from an expression.")}, 3454 {"isexpr", (PyCFunction)parser_isexpr, PUBLIC_METHOD_TYPE, 3455 PyDoc_STR("Determines if an ST object was created from an expression.")}, 3456 {"issuite", (PyCFunction)parser_issuite, PUBLIC_METHOD_TYPE, 3457 PyDoc_STR("Determines if an ST object was created from a suite.")}, 3458 {"suite", (PyCFunction)parser_suite, PUBLIC_METHOD_TYPE, 3459 PyDoc_STR("Creates an ST object from a suite.")}, 3460 {"sequence2st", (PyCFunction)parser_tuple2st, PUBLIC_METHOD_TYPE, 3461 PyDoc_STR("Creates an ST object from a tree representation.")}, 3462 {"st2tuple", (PyCFunction)parser_st2tuple, PUBLIC_METHOD_TYPE, 3463 PyDoc_STR("Creates a tuple-tree representation of an ST.")}, 3464 {"st2list", (PyCFunction)parser_st2list, PUBLIC_METHOD_TYPE, 3465 PyDoc_STR("Creates a list-tree representation of an ST.")}, 3466 {"tuple2st", (PyCFunction)parser_tuple2st, PUBLIC_METHOD_TYPE, 3467 PyDoc_STR("Creates an ST object from a tree representation.")}, 3468 3469 /* private stuff: support pickle module */ 3470 {"_pickler", (PyCFunction)parser__pickler, METH_VARARGS, 3471 PyDoc_STR("Returns the pickle magic to allow ST objects to be pickled.")}, 3472 3473 {NULL, NULL, 0, NULL} 3474 }; 3475 3476 3477 3478static struct PyModuleDef parsermodule = { 3479 PyModuleDef_HEAD_INIT, 3480 "parser", 3481 NULL, 3482 -1, 3483 parser_functions, 3484 NULL, 3485 NULL, 3486 NULL, 3487 NULL 3488}; 3489 3490PyMODINIT_FUNC PyInit_parser(void); /* supply a prototype */ 3491 3492PyMODINIT_FUNC 3493PyInit_parser(void) 3494{ 3495 PyObject *module, *copyreg; 3496 3497 if (PyType_Ready(&PyST_Type) < 0) 3498 return NULL; 3499 module = PyModule_Create(&parsermodule); 3500 if (module == NULL) 3501 return NULL; 3502 3503 if (parser_error == 0) 3504 parser_error = PyErr_NewException("parser.ParserError", NULL, NULL); 3505 3506 if (parser_error == 0) 3507 return NULL; 3508 /* CAUTION: The code next used to skip bumping the refcount on 3509 * parser_error. That's a disaster if PyInit_parser() gets called more 3510 * than once. By incref'ing, we ensure that each module dict that 3511 * gets created owns its reference to the shared parser_error object, 3512 * and the file static parser_error vrbl owns a reference too. 3513 */ 3514 Py_INCREF(parser_error); 3515 if (PyModule_AddObject(module, "ParserError", parser_error) != 0) 3516 return NULL; 3517 3518 Py_INCREF(&PyST_Type); 3519 PyModule_AddObject(module, "STType", (PyObject*)&PyST_Type); 3520 3521 PyModule_AddStringConstant(module, "__copyright__", 3522 parser_copyright_string); 3523 PyModule_AddStringConstant(module, "__doc__", 3524 parser_doc_string); 3525 PyModule_AddStringConstant(module, "__version__", 3526 parser_version_string); 3527 3528 /* Register to support pickling. 3529 * If this fails, the import of this module will fail because an 3530 * exception will be raised here; should we clear the exception? 3531 */ 3532 copyreg = PyImport_ImportModuleNoBlock("copyreg"); 3533 if (copyreg != NULL) { 3534 PyObject *func, *pickler; 3535 _Py_IDENTIFIER(pickle); 3536 _Py_IDENTIFIER(sequence2st); 3537 _Py_IDENTIFIER(_pickler); 3538 3539 func = _PyObject_GetAttrId(copyreg, &PyId_pickle); 3540 pickle_constructor = _PyObject_GetAttrId(module, &PyId_sequence2st); 3541 pickler = _PyObject_GetAttrId(module, &PyId__pickler); 3542 Py_XINCREF(pickle_constructor); 3543 if ((func != NULL) && (pickle_constructor != NULL) 3544 && (pickler != NULL)) { 3545 PyObject *res; 3546 3547 res = PyObject_CallFunctionObjArgs(func, &PyST_Type, pickler, 3548 pickle_constructor, NULL); 3549 Py_XDECREF(res); 3550 } 3551 Py_XDECREF(func); 3552 Py_XDECREF(pickle_constructor); 3553 Py_XDECREF(pickler); 3554 Py_DECREF(copyreg); 3555 } 3556 return module; 3557} 3558