parsermodule.c revision b28f6e7c7bbad58e23304e00c5c730bd44b50ba0
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 28#include "Python.h" /* general Python API */ 29#include "graminit.h" /* symbols defined in the grammar */ 30#include "node.h" /* internal parser structure */ 31#include "token.h" /* token definitions */ 32 /* ISTERMINAL() / ISNONTERMINAL() */ 33#include "compile.h" /* PyNode_Compile() */ 34 35#ifdef lint 36#include <note.h> 37#else 38#define NOTE(x) 39#endif 40 41#ifdef macintosh 42char *strdup(char *); 43#endif 44 45/* String constants used to initialize module attributes. 46 * 47 */ 48static char* 49parser_copyright_string 50= "Copyright 1995-1996 by Virginia Polytechnic Institute & State\n\ 51University, Blacksburg, Virginia, USA, and Fred L. Drake, Jr., Reston,\n\ 52Virginia, USA. Portions copyright 1991-1995 by Stichting Mathematisch\n\ 53Centrum, Amsterdam, The Netherlands."; 54 55 56static char* 57parser_doc_string 58= "This is an interface to Python's internal parser."; 59 60static char* 61parser_version_string = "0.5"; 62 63 64typedef PyObject* (*SeqMaker) (int length); 65typedef int (*SeqInserter) (PyObject* sequence, 66 int index, 67 PyObject* element); 68 69/* The function below is copyrighted by Stichting Mathematisch Centrum. The 70 * original copyright statement is included below, and continues to apply 71 * in full to the function immediately following. All other material is 72 * original, copyrighted by Fred L. Drake, Jr. and Virginia Polytechnic 73 * Institute and State University. Changes were made to comply with the 74 * new naming conventions. Added arguments to provide support for creating 75 * lists as well as tuples, and optionally including the line numbers. 76 */ 77 78 79static PyObject* 80node2tuple(node *n, /* node to convert */ 81 SeqMaker mkseq, /* create sequence */ 82 SeqInserter addelem, /* func. to add elem. in seq. */ 83 int lineno) /* include line numbers? */ 84{ 85 if (n == NULL) { 86 Py_INCREF(Py_None); 87 return (Py_None); 88 } 89 if (ISNONTERMINAL(TYPE(n))) { 90 int i; 91 PyObject *v; 92 PyObject *w; 93 94 v = mkseq(1 + NCH(n)); 95 if (v == NULL) 96 return (v); 97 w = PyInt_FromLong(TYPE(n)); 98 if (w == NULL) { 99 Py_DECREF(v); 100 return ((PyObject*) NULL); 101 } 102 (void) addelem(v, 0, w); 103 for (i = 0; i < NCH(n); i++) { 104 w = node2tuple(CHILD(n, i), mkseq, addelem, lineno); 105 if (w == NULL) { 106 Py_DECREF(v); 107 return ((PyObject*) NULL); 108 } 109 (void) addelem(v, i+1, w); 110 } 111 return (v); 112 } 113 else if (ISTERMINAL(TYPE(n))) { 114 PyObject *result = mkseq(2 + lineno); 115 if (result != NULL) { 116 (void) addelem(result, 0, PyInt_FromLong(TYPE(n))); 117 (void) addelem(result, 1, PyString_FromString(STR(n))); 118 if (lineno == 1) 119 (void) addelem(result, 2, PyInt_FromLong(n->n_lineno)); 120 } 121 return (result); 122 } 123 else { 124 PyErr_SetString(PyExc_SystemError, 125 "unrecognized parse tree node type"); 126 return ((PyObject*) NULL); 127 } 128} 129/* 130 * End of material copyrighted by Stichting Mathematisch Centrum. 131 */ 132 133 134 135/* There are two types of intermediate objects we're interested in: 136 * 'eval' and 'exec' types. These constants can be used in the ast_type 137 * field of the object type to identify which any given object represents. 138 * These should probably go in an external header to allow other extensions 139 * to use them, but then, we really should be using C++ too. ;-) 140 * 141 * The PyAST_FRAGMENT type is not currently supported. Maybe not useful? 142 * Haven't decided yet. 143 */ 144 145#define PyAST_EXPR 1 146#define PyAST_SUITE 2 147#define PyAST_FRAGMENT 3 148 149 150/* These are the internal objects and definitions required to implement the 151 * AST type. Most of the internal names are more reminiscent of the 'old' 152 * naming style, but the code uses the new naming convention. 153 */ 154 155static PyObject* 156parser_error = 0; 157 158 159typedef struct _PyAST_Object { 160 PyObject_HEAD /* standard object header */ 161 node* ast_node; /* the node* returned by the parser */ 162 int ast_type; /* EXPR or SUITE ? */ 163} PyAST_Object; 164 165 166staticforward void 167parser_free(PyAST_Object *ast); 168 169staticforward int 170parser_compare(PyAST_Object *left, PyAST_Object *right); 171 172staticforward PyObject * 173parser_getattr(PyObject *self, char *name); 174 175 176static 177PyTypeObject PyAST_Type = { 178 PyObject_HEAD_INIT(NULL) 179 0, 180 "ast", /* tp_name */ 181 (int) sizeof(PyAST_Object), /* tp_basicsize */ 182 0, /* tp_itemsize */ 183 (destructor)parser_free, /* tp_dealloc */ 184 0, /* tp_print */ 185 parser_getattr, /* tp_getattr */ 186 0, /* tp_setattr */ 187 (cmpfunc)parser_compare, /* tp_compare */ 188 0, /* tp_repr */ 189 0, /* tp_as_number */ 190 0, /* tp_as_sequence */ 191 0, /* tp_as_mapping */ 192 0, /* tp_hash */ 193 0, /* tp_call */ 194 0, /* tp_str */ 195 0, /* tp_getattro */ 196 0, /* tp_setattro */ 197 198 /* Functions to access object as input/output buffer */ 199 0, /* tp_as_buffer */ 200 201 Py_TPFLAGS_DEFAULT, /* tp_flags */ 202 203 /* __doc__ */ 204 "Intermediate representation of a Python parse tree." 205}; /* PyAST_Type */ 206 207 208static int 209parser_compare_nodes(node *left, node *right) 210{ 211 int j; 212 213 if (TYPE(left) < TYPE(right)) 214 return (-1); 215 216 if (TYPE(right) < TYPE(left)) 217 return (1); 218 219 if (ISTERMINAL(TYPE(left))) 220 return (strcmp(STR(left), STR(right))); 221 222 if (NCH(left) < NCH(right)) 223 return (-1); 224 225 if (NCH(right) < NCH(left)) 226 return (1); 227 228 for (j = 0; j < NCH(left); ++j) { 229 int v = parser_compare_nodes(CHILD(left, j), CHILD(right, j)); 230 231 if (v != 0) 232 return (v); 233 } 234 return (0); 235} 236 237 238/* int parser_compare(PyAST_Object* left, PyAST_Object* right) 239 * 240 * Comparison function used by the Python operators ==, !=, <, >, <=, >= 241 * This really just wraps a call to parser_compare_nodes() with some easy 242 * checks and protection code. 243 * 244 */ 245static int 246parser_compare(PyAST_Object *left, PyAST_Object *right) 247{ 248 if (left == right) 249 return (0); 250 251 if ((left == 0) || (right == 0)) 252 return (-1); 253 254 return (parser_compare_nodes(left->ast_node, right->ast_node)); 255} 256 257 258/* parser_newastobject(node* ast) 259 * 260 * Allocates a new Python object representing an AST. This is simply the 261 * 'wrapper' object that holds a node* and allows it to be passed around in 262 * Python code. 263 * 264 */ 265static PyObject* 266parser_newastobject(node *ast, int type) 267{ 268 PyAST_Object* o = PyObject_New(PyAST_Object, &PyAST_Type); 269 270 if (o != 0) { 271 o->ast_node = ast; 272 o->ast_type = type; 273 } 274 else { 275 PyNode_Free(ast); 276 } 277 return ((PyObject*)o); 278} 279 280 281/* void parser_free(PyAST_Object* ast) 282 * 283 * This is called by a del statement that reduces the reference count to 0. 284 * 285 */ 286static void 287parser_free(PyAST_Object *ast) 288{ 289 PyNode_Free(ast->ast_node); 290 PyObject_Del(ast); 291} 292 293 294/* parser_ast2tuple(PyObject* self, PyObject* args, PyObject* kw) 295 * 296 * This provides conversion from a node* to a tuple object that can be 297 * returned to the Python-level caller. The AST object is not modified. 298 * 299 */ 300static PyObject* 301parser_ast2tuple(PyAST_Object *self, PyObject *args, PyObject *kw) 302{ 303 PyObject *line_option = 0; 304 PyObject *res = 0; 305 int ok; 306 307 static char *keywords[] = {"ast", "line_info", NULL}; 308 309 if (self == NULL) { 310 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|O:ast2tuple", keywords, 311 &PyAST_Type, &self, &line_option); 312 } 313 else 314 ok = PyArg_ParseTupleAndKeywords(args, kw, "|O:totuple", &keywords[1], 315 &line_option); 316 if (ok != 0) { 317 int lineno = 0; 318 if (line_option != NULL) { 319 lineno = (PyObject_IsTrue(line_option) != 0) ? 1 : 0; 320 } 321 /* 322 * Convert AST into a tuple representation. Use Guido's function, 323 * since it's known to work already. 324 */ 325 res = node2tuple(((PyAST_Object*)self)->ast_node, 326 PyTuple_New, PyTuple_SetItem, lineno); 327 } 328 return (res); 329} 330 331 332/* parser_ast2list(PyObject* self, PyObject* args, PyObject* kw) 333 * 334 * This provides conversion from a node* to a list object that can be 335 * returned to the Python-level caller. The AST object is not modified. 336 * 337 */ 338static PyObject* 339parser_ast2list(PyAST_Object *self, PyObject *args, PyObject *kw) 340{ 341 PyObject *line_option = 0; 342 PyObject *res = 0; 343 int ok; 344 345 static char *keywords[] = {"ast", "line_info", NULL}; 346 347 if (self == NULL) 348 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|O:ast2list", keywords, 349 &PyAST_Type, &self, &line_option); 350 else 351 ok = PyArg_ParseTupleAndKeywords(args, kw, "|O:tolist", &keywords[1], 352 &line_option); 353 if (ok) { 354 int lineno = 0; 355 if (line_option != 0) { 356 lineno = PyObject_IsTrue(line_option) ? 1 : 0; 357 } 358 /* 359 * Convert AST into a tuple representation. Use Guido's function, 360 * since it's known to work already. 361 */ 362 res = node2tuple(self->ast_node, 363 PyList_New, PyList_SetItem, lineno); 364 } 365 return (res); 366} 367 368 369/* parser_compileast(PyObject* self, PyObject* args) 370 * 371 * This function creates code objects from the parse tree represented by 372 * the passed-in data object. An optional file name is passed in as well. 373 * 374 */ 375static PyObject* 376parser_compileast(PyAST_Object *self, PyObject *args, PyObject *kw) 377{ 378 PyObject* res = 0; 379 char* str = "<ast>"; 380 int ok; 381 382 static char *keywords[] = {"ast", "filename", NULL}; 383 384 if (self == NULL) 385 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!|s:compileast", keywords, 386 &PyAST_Type, &self, &str); 387 else 388 ok = PyArg_ParseTupleAndKeywords(args, kw, "|s:compile", &keywords[1], 389 &str); 390 391 if (ok) 392 res = (PyObject *)PyNode_Compile(self->ast_node, str); 393 394 return (res); 395} 396 397 398/* PyObject* parser_isexpr(PyObject* self, PyObject* args) 399 * PyObject* parser_issuite(PyObject* self, PyObject* args) 400 * 401 * Checks the passed-in AST object to determine if it is an expression or 402 * a statement suite, respectively. The return is a Python truth value. 403 * 404 */ 405static PyObject* 406parser_isexpr(PyAST_Object *self, PyObject *args, PyObject *kw) 407{ 408 PyObject* res = 0; 409 int ok; 410 411 static char *keywords[] = {"ast", NULL}; 412 413 if (self == NULL) 414 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:isexpr", keywords, 415 &PyAST_Type, &self); 416 else 417 ok = PyArg_ParseTupleAndKeywords(args, kw, ":isexpr", &keywords[1]); 418 419 if (ok) { 420 /* Check to see if the AST represents an expression or not. */ 421 res = (self->ast_type == PyAST_EXPR) ? Py_True : Py_False; 422 Py_INCREF(res); 423 } 424 return (res); 425} 426 427 428static PyObject* 429parser_issuite(PyAST_Object *self, PyObject *args, PyObject *kw) 430{ 431 PyObject* res = 0; 432 int ok; 433 434 static char *keywords[] = {"ast", NULL}; 435 436 if (self == NULL) 437 ok = PyArg_ParseTupleAndKeywords(args, kw, "O!:issuite", keywords, 438 &PyAST_Type, &self); 439 else 440 ok = PyArg_ParseTupleAndKeywords(args, kw, ":issuite", &keywords[1]); 441 442 if (ok) { 443 /* Check to see if the AST represents an expression or not. */ 444 res = (self->ast_type == PyAST_EXPR) ? Py_False : Py_True; 445 Py_INCREF(res); 446 } 447 return (res); 448} 449 450 451#define PUBLIC_METHOD_TYPE (METH_VARARGS|METH_KEYWORDS) 452 453static PyMethodDef 454parser_methods[] = { 455 {"compile", (PyCFunction)parser_compileast, PUBLIC_METHOD_TYPE, 456 "Compile this AST object into a code object."}, 457 {"isexpr", (PyCFunction)parser_isexpr, PUBLIC_METHOD_TYPE, 458 "Determines if this AST object was created from an expression."}, 459 {"issuite", (PyCFunction)parser_issuite, PUBLIC_METHOD_TYPE, 460 "Determines if this AST object was created from a suite."}, 461 {"tolist", (PyCFunction)parser_ast2list, PUBLIC_METHOD_TYPE, 462 "Creates a list-tree representation of this AST."}, 463 {"totuple", (PyCFunction)parser_ast2tuple, PUBLIC_METHOD_TYPE, 464 "Creates a tuple-tree representation of this AST."}, 465 466 {NULL, NULL, 0, NULL} 467}; 468 469 470static PyObject* 471parser_getattr(PyObject *self, char *name) 472{ 473 return (Py_FindMethod(parser_methods, self, name)); 474} 475 476 477/* err_string(char* message) 478 * 479 * Sets the error string for an exception of type ParserError. 480 * 481 */ 482static void 483err_string(char *message) 484{ 485 PyErr_SetString(parser_error, message); 486} 487 488 489/* PyObject* parser_do_parse(PyObject* args, int type) 490 * 491 * Internal function to actually execute the parse and return the result if 492 * successful, or set an exception if not. 493 * 494 */ 495static PyObject* 496parser_do_parse(PyObject *args, PyObject *kw, char *argspec, int type) 497{ 498 char* string = 0; 499 PyObject* res = 0; 500 501 static char *keywords[] = {"source", NULL}; 502 503 if (PyArg_ParseTupleAndKeywords(args, kw, argspec, keywords, &string)) { 504 node* n = PyParser_SimpleParseString(string, 505 (type == PyAST_EXPR) 506 ? eval_input : file_input); 507 508 if (n != 0) 509 res = parser_newastobject(n, type); 510 else 511 err_string("could not parse string"); 512 } 513 return (res); 514} 515 516 517/* PyObject* parser_expr(PyObject* self, PyObject* args) 518 * PyObject* parser_suite(PyObject* self, PyObject* args) 519 * 520 * External interfaces to the parser itself. Which is called determines if 521 * the parser attempts to recognize an expression ('eval' form) or statement 522 * suite ('exec' form). The real work is done by parser_do_parse() above. 523 * 524 */ 525static PyObject* 526parser_expr(PyAST_Object *self, PyObject *args, PyObject *kw) 527{ 528 NOTE(ARGUNUSED(self)) 529 return (parser_do_parse(args, kw, "s:expr", PyAST_EXPR)); 530} 531 532 533static PyObject* 534parser_suite(PyAST_Object *self, PyObject *args, PyObject *kw) 535{ 536 NOTE(ARGUNUSED(self)) 537 return (parser_do_parse(args, kw, "s:suite", PyAST_SUITE)); 538} 539 540 541 542/* This is the messy part of the code. Conversion from a tuple to an AST 543 * object requires that the input tuple be valid without having to rely on 544 * catching an exception from the compiler. This is done to allow the 545 * compiler itself to remain fast, since most of its input will come from 546 * the parser directly, and therefore be known to be syntactically correct. 547 * This validation is done to ensure that we don't core dump the compile 548 * phase, returning an exception instead. 549 * 550 * Two aspects can be broken out in this code: creating a node tree from 551 * the tuple passed in, and verifying that it is indeed valid. It may be 552 * advantageous to expand the number of AST types to include funcdefs and 553 * lambdadefs to take advantage of the optimizer, recognizing those ASTs 554 * here. They are not necessary, and not quite as useful in a raw form. 555 * For now, let's get expressions and suites working reliably. 556 */ 557 558 559staticforward node* build_node_tree(PyObject *tuple); 560staticforward int validate_expr_tree(node *tree); 561staticforward int validate_file_input(node *tree); 562 563 564/* PyObject* parser_tuple2ast(PyObject* self, PyObject* args) 565 * 566 * This is the public function, called from the Python code. It receives a 567 * single tuple object from the caller, and creates an AST object if the 568 * tuple can be validated. It does this by checking the first code of the 569 * tuple, and, if acceptable, builds the internal representation. If this 570 * step succeeds, the internal representation is validated as fully as 571 * possible with the various validate_*() routines defined below. 572 * 573 * This function must be changed if support is to be added for PyAST_FRAGMENT 574 * AST objects. 575 * 576 */ 577static PyObject* 578parser_tuple2ast(PyAST_Object *self, PyObject *args, PyObject *kw) 579{ 580 NOTE(ARGUNUSED(self)) 581 PyObject *ast = 0; 582 PyObject *tuple; 583 node *tree; 584 585 static char *keywords[] = {"sequence", NULL}; 586 587 if (!PyArg_ParseTupleAndKeywords(args, kw, "O:sequence2ast", keywords, 588 &tuple)) 589 return (0); 590 if (!PySequence_Check(tuple)) { 591 PyErr_SetString(PyExc_ValueError, 592 "sequence2ast() requires a single sequence argument"); 593 return (0); 594 } 595 /* 596 * Convert the tree to the internal form before checking it. 597 */ 598 tree = build_node_tree(tuple); 599 if (tree != 0) { 600 int start_sym = TYPE(tree); 601 if (start_sym == eval_input) { 602 /* Might be an eval form. */ 603 if (validate_expr_tree(tree)) 604 ast = parser_newastobject(tree, PyAST_EXPR); 605 } 606 else if (start_sym == file_input) { 607 /* This looks like an exec form so far. */ 608 if (validate_file_input(tree)) 609 ast = parser_newastobject(tree, PyAST_SUITE); 610 } 611 else { 612 /* This is a fragment, at best. */ 613 PyNode_Free(tree); 614 err_string("parse tree does not use a valid start symbol"); 615 } 616 } 617 /* Make sure we throw an exception on all errors. We should never 618 * get this, but we'd do well to be sure something is done. 619 */ 620 if ((ast == 0) && !PyErr_Occurred()) 621 err_string("unspecified AST error occurred"); 622 623 return (ast); 624} 625 626 627/* node* build_node_children() 628 * 629 * Iterate across the children of the current non-terminal node and build 630 * their structures. If successful, return the root of this portion of 631 * the tree, otherwise, 0. Any required exception will be specified already, 632 * and no memory will have been deallocated. 633 * 634 */ 635static node* 636build_node_children(PyObject *tuple, node *root, int *line_num) 637{ 638 int len = PyObject_Size(tuple); 639 int i; 640 641 for (i = 1; i < len; ++i) { 642 /* elem must always be a sequence, however simple */ 643 PyObject* elem = PySequence_GetItem(tuple, i); 644 int ok = elem != NULL; 645 long type = 0; 646 char *strn = 0; 647 648 if (ok) 649 ok = PySequence_Check(elem); 650 if (ok) { 651 PyObject *temp = PySequence_GetItem(elem, 0); 652 if (temp == NULL) 653 ok = 0; 654 else { 655 ok = PyInt_Check(temp); 656 if (ok) 657 type = PyInt_AS_LONG(temp); 658 Py_DECREF(temp); 659 } 660 } 661 if (!ok) { 662 PyErr_SetObject(parser_error, 663 Py_BuildValue("os", elem, 664 "Illegal node construct.")); 665 Py_XDECREF(elem); 666 return (0); 667 } 668 if (ISTERMINAL(type)) { 669 int len = PyObject_Size(elem); 670 PyObject *temp; 671 672 if ((len != 2) && (len != 3)) { 673 err_string("terminal nodes must have 2 or 3 entries"); 674 return 0; 675 } 676 temp = PySequence_GetItem(elem, 1); 677 if (temp == NULL) 678 return 0; 679 if (!PyString_Check(temp)) { 680 PyErr_Format(parser_error, 681 "second item in terminal node must be a string," 682 " found %s", 683 ((PyTypeObject*)PyObject_Type(temp))->tp_name); 684 Py_DECREF(temp); 685 return 0; 686 } 687 if (len == 3) { 688 PyObject *o = PySequence_GetItem(elem, 2); 689 if (o != NULL) { 690 if (PyInt_Check(o)) 691 *line_num = PyInt_AS_LONG(o); 692 else { 693 PyErr_Format(parser_error, 694 "third item in terminal node must be an" 695 " integer, found %s", 696 ((PyTypeObject*)PyObject_Type(temp))->tp_name); 697 Py_DECREF(o); 698 Py_DECREF(temp); 699 return 0; 700 } 701 Py_DECREF(o); 702 } 703 } 704 len = PyString_GET_SIZE(temp) + 1; 705 strn = (char *)PyMem_MALLOC(len); 706 if (strn != NULL) 707 (void) memcpy(strn, PyString_AS_STRING(temp), len); 708 Py_DECREF(temp); 709 } 710 else if (!ISNONTERMINAL(type)) { 711 /* 712 * It has to be one or the other; this is an error. 713 * Throw an exception. 714 */ 715 PyErr_SetObject(parser_error, 716 Py_BuildValue("os", elem, "unknown node type.")); 717 Py_XDECREF(elem); 718 return (0); 719 } 720 PyNode_AddChild(root, type, strn, *line_num); 721 722 if (ISNONTERMINAL(type)) { 723 node* new_child = CHILD(root, i - 1); 724 725 if (new_child != build_node_children(elem, new_child, line_num)) { 726 Py_XDECREF(elem); 727 return (0); 728 } 729 } 730 else if (type == NEWLINE) { /* It's true: we increment the */ 731 ++(*line_num); /* line number *after* the newline! */ 732 } 733 Py_XDECREF(elem); 734 } 735 return (root); 736} 737 738 739static node* 740build_node_tree(PyObject *tuple) 741{ 742 node* res = 0; 743 PyObject *temp = PySequence_GetItem(tuple, 0); 744 long num = -1; 745 746 if (temp != NULL) 747 num = PyInt_AsLong(temp); 748 Py_XDECREF(temp); 749 if (ISTERMINAL(num)) { 750 /* 751 * The tuple is simple, but it doesn't start with a start symbol. 752 * Throw an exception now and be done with it. 753 */ 754 tuple = Py_BuildValue("os", tuple, 755 "Illegal ast tuple; cannot start with terminal symbol."); 756 PyErr_SetObject(parser_error, tuple); 757 } 758 else if (ISNONTERMINAL(num)) { 759 /* 760 * Not efficient, but that can be handled later. 761 */ 762 int line_num = 0; 763 764 res = PyNode_New(num); 765 if (res != build_node_children(tuple, res, &line_num)) { 766 PyNode_Free(res); 767 res = 0; 768 } 769 } 770 else 771 /* The tuple is illegal -- if the number is neither TERMINAL nor 772 * NONTERMINAL, we can't use it. Not sure the implementation 773 * allows this condition, but the API doesn't preclude it. 774 */ 775 PyErr_SetObject(parser_error, 776 Py_BuildValue("os", tuple, 777 "Illegal component tuple.")); 778 779 return (res); 780} 781 782 783/* 784 * Validation routines used within the validation section: 785 */ 786staticforward int validate_terminal(node *terminal, int type, char *string); 787 788#define validate_ampersand(ch) validate_terminal(ch, AMPER, "&") 789#define validate_circumflex(ch) validate_terminal(ch, CIRCUMFLEX, "^") 790#define validate_colon(ch) validate_terminal(ch, COLON, ":") 791#define validate_comma(ch) validate_terminal(ch, COMMA, ",") 792#define validate_dedent(ch) validate_terminal(ch, DEDENT, "") 793#define validate_equal(ch) validate_terminal(ch, EQUAL, "=") 794#define validate_indent(ch) validate_terminal(ch, INDENT, (char*)NULL) 795#define validate_lparen(ch) validate_terminal(ch, LPAR, "(") 796#define validate_newline(ch) validate_terminal(ch, NEWLINE, (char*)NULL) 797#define validate_rparen(ch) validate_terminal(ch, RPAR, ")") 798#define validate_semi(ch) validate_terminal(ch, SEMI, ";") 799#define validate_star(ch) validate_terminal(ch, STAR, "*") 800#define validate_vbar(ch) validate_terminal(ch, VBAR, "|") 801#define validate_doublestar(ch) validate_terminal(ch, DOUBLESTAR, "**") 802#define validate_dot(ch) validate_terminal(ch, DOT, ".") 803#define validate_name(ch, str) validate_terminal(ch, NAME, str) 804 805#define VALIDATER(n) static int validate_##n(node *tree) 806 807VALIDATER(node); VALIDATER(small_stmt); 808VALIDATER(class); VALIDATER(node); 809VALIDATER(parameters); VALIDATER(suite); 810VALIDATER(testlist); VALIDATER(varargslist); 811VALIDATER(fpdef); VALIDATER(fplist); 812VALIDATER(stmt); VALIDATER(simple_stmt); 813VALIDATER(expr_stmt); VALIDATER(power); 814VALIDATER(print_stmt); VALIDATER(del_stmt); 815VALIDATER(return_stmt); VALIDATER(list_iter); 816VALIDATER(raise_stmt); VALIDATER(import_stmt); 817VALIDATER(global_stmt); VALIDATER(list_if); 818VALIDATER(assert_stmt); VALIDATER(list_for); 819VALIDATER(exec_stmt); VALIDATER(compound_stmt); 820VALIDATER(while); VALIDATER(for); 821VALIDATER(try); VALIDATER(except_clause); 822VALIDATER(test); VALIDATER(and_test); 823VALIDATER(not_test); VALIDATER(comparison); 824VALIDATER(comp_op); VALIDATER(expr); 825VALIDATER(xor_expr); VALIDATER(and_expr); 826VALIDATER(shift_expr); VALIDATER(arith_expr); 827VALIDATER(term); VALIDATER(factor); 828VALIDATER(atom); VALIDATER(lambdef); 829VALIDATER(trailer); VALIDATER(subscript); 830VALIDATER(subscriptlist); VALIDATER(sliceop); 831VALIDATER(exprlist); VALIDATER(dictmaker); 832VALIDATER(arglist); VALIDATER(argument); 833VALIDATER(listmaker); 834 835#undef VALIDATER 836 837#define is_even(n) (((n) & 1) == 0) 838#define is_odd(n) (((n) & 1) == 1) 839 840 841static int 842validate_ntype(node *n, int t) 843{ 844 if (TYPE(n) != t) { 845 PyErr_Format(parser_error, "Expected node type %d, got %d.", 846 t, TYPE(n)); 847 return 0; 848 } 849 return 1; 850} 851 852 853/* Verifies that the number of child nodes is exactly 'num', raising 854 * an exception if it isn't. The exception message does not indicate 855 * the exact number of nodes, allowing this to be used to raise the 856 * "right" exception when the wrong number of nodes is present in a 857 * specific variant of a statement's syntax. This is commonly used 858 * in that fashion. 859 */ 860static int 861validate_numnodes(node *n, int num, const char *const name) 862{ 863 if (NCH(n) != num) { 864 PyErr_Format(parser_error, 865 "Illegal number of children for %s node.", name); 866 return 0; 867 } 868 return 1; 869} 870 871 872static int 873validate_terminal(node *terminal, int type, char *string) 874{ 875 int res = (validate_ntype(terminal, type) 876 && ((string == 0) || (strcmp(string, STR(terminal)) == 0))); 877 878 if (!res && !PyErr_Occurred()) { 879 PyErr_Format(parser_error, 880 "Illegal terminal: expected \"%s\"", string); 881 } 882 return (res); 883} 884 885 886/* X (',' X) [','] 887 */ 888static int 889validate_repeating_list(node *tree, int ntype, int (*vfunc)(node *), 890 const char *const name) 891{ 892 int nch = NCH(tree); 893 int res = (nch && validate_ntype(tree, ntype) 894 && vfunc(CHILD(tree, 0))); 895 896 if (!res && !PyErr_Occurred()) 897 (void) validate_numnodes(tree, 1, name); 898 else { 899 if (is_even(nch)) 900 res = validate_comma(CHILD(tree, --nch)); 901 if (res && nch > 1) { 902 int pos = 1; 903 for ( ; res && pos < nch; pos += 2) 904 res = (validate_comma(CHILD(tree, pos)) 905 && vfunc(CHILD(tree, pos + 1))); 906 } 907 } 908 return (res); 909} 910 911 912/* validate_class() 913 * 914 * classdef: 915 * 'class' NAME ['(' testlist ')'] ':' suite 916 */ 917static int 918validate_class(node *tree) 919{ 920 int nch = NCH(tree); 921 int res = validate_ntype(tree, classdef) && ((nch == 4) || (nch == 7)); 922 923 if (res) { 924 res = (validate_name(CHILD(tree, 0), "class") 925 && validate_ntype(CHILD(tree, 1), NAME) 926 && validate_colon(CHILD(tree, nch - 2)) 927 && validate_suite(CHILD(tree, nch - 1))); 928 } 929 else 930 (void) validate_numnodes(tree, 4, "class"); 931 if (res && (nch == 7)) { 932 res = (validate_lparen(CHILD(tree, 2)) 933 && validate_testlist(CHILD(tree, 3)) 934 && validate_rparen(CHILD(tree, 4))); 935 } 936 return (res); 937} 938 939 940/* if_stmt: 941 * 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite] 942 */ 943static int 944validate_if(node *tree) 945{ 946 int nch = NCH(tree); 947 int res = (validate_ntype(tree, if_stmt) 948 && (nch >= 4) 949 && validate_name(CHILD(tree, 0), "if") 950 && validate_test(CHILD(tree, 1)) 951 && validate_colon(CHILD(tree, 2)) 952 && validate_suite(CHILD(tree, 3))); 953 954 if (res && ((nch % 4) == 3)) { 955 /* ... 'else' ':' suite */ 956 res = (validate_name(CHILD(tree, nch - 3), "else") 957 && validate_colon(CHILD(tree, nch - 2)) 958 && validate_suite(CHILD(tree, nch - 1))); 959 nch -= 3; 960 } 961 else if (!res && !PyErr_Occurred()) 962 (void) validate_numnodes(tree, 4, "if"); 963 if ((nch % 4) != 0) 964 /* Will catch the case for nch < 4 */ 965 res = validate_numnodes(tree, 0, "if"); 966 else if (res && (nch > 4)) { 967 /* ... ('elif' test ':' suite)+ ... */ 968 int j = 4; 969 while ((j < nch) && res) { 970 res = (validate_name(CHILD(tree, j), "elif") 971 && validate_colon(CHILD(tree, j + 2)) 972 && validate_test(CHILD(tree, j + 1)) 973 && validate_suite(CHILD(tree, j + 3))); 974 j += 4; 975 } 976 } 977 return (res); 978} 979 980 981/* parameters: 982 * '(' [varargslist] ')' 983 * 984 */ 985static int 986validate_parameters(node *tree) 987{ 988 int nch = NCH(tree); 989 int res = validate_ntype(tree, parameters) && ((nch == 2) || (nch == 3)); 990 991 if (res) { 992 res = (validate_lparen(CHILD(tree, 0)) 993 && validate_rparen(CHILD(tree, nch - 1))); 994 if (res && (nch == 3)) 995 res = validate_varargslist(CHILD(tree, 1)); 996 } 997 else { 998 (void) validate_numnodes(tree, 2, "parameters"); 999 } 1000 return (res); 1001} 1002 1003 1004/* validate_suite() 1005 * 1006 * suite: 1007 * simple_stmt 1008 * | NEWLINE INDENT stmt+ DEDENT 1009 */ 1010static int 1011validate_suite(node *tree) 1012{ 1013 int nch = NCH(tree); 1014 int res = (validate_ntype(tree, suite) && ((nch == 1) || (nch >= 4))); 1015 1016 if (res && (nch == 1)) 1017 res = validate_simple_stmt(CHILD(tree, 0)); 1018 else if (res) { 1019 /* NEWLINE INDENT stmt+ DEDENT */ 1020 res = (validate_newline(CHILD(tree, 0)) 1021 && validate_indent(CHILD(tree, 1)) 1022 && validate_stmt(CHILD(tree, 2)) 1023 && validate_dedent(CHILD(tree, nch - 1))); 1024 1025 if (res && (nch > 4)) { 1026 int i = 3; 1027 --nch; /* forget the DEDENT */ 1028 for ( ; res && (i < nch); ++i) 1029 res = validate_stmt(CHILD(tree, i)); 1030 } 1031 else if (nch < 4) 1032 res = validate_numnodes(tree, 4, "suite"); 1033 } 1034 return (res); 1035} 1036 1037 1038static int 1039validate_testlist(node *tree) 1040{ 1041 return (validate_repeating_list(tree, testlist, 1042 validate_test, "testlist")); 1043} 1044 1045 1046/* '*' NAME [',' '**' NAME] | '**' NAME 1047 */ 1048static int 1049validate_varargslist_trailer(node *tree, int start) 1050{ 1051 int nch = NCH(tree); 1052 int res = 0; 1053 int sym; 1054 1055 if (nch <= start) { 1056 err_string("expected variable argument trailer for varargslist"); 1057 return 0; 1058 } 1059 sym = TYPE(CHILD(tree, start)); 1060 if (sym == STAR) { 1061 /* 1062 * ('*' NAME [',' '**' NAME] 1063 */ 1064 if (nch-start == 2) 1065 res = validate_name(CHILD(tree, start+1), NULL); 1066 else if (nch-start == 5) 1067 res = (validate_name(CHILD(tree, start+1), NULL) 1068 && validate_comma(CHILD(tree, start+2)) 1069 && validate_doublestar(CHILD(tree, start+3)) 1070 && validate_name(CHILD(tree, start+4), NULL)); 1071 } 1072 else if (sym == DOUBLESTAR) { 1073 /* 1074 * '**' NAME 1075 */ 1076 if (nch-start == 2) 1077 res = validate_name(CHILD(tree, start+1), NULL); 1078 } 1079 if (!res) 1080 err_string("illegal variable argument trailer for varargslist"); 1081 return res; 1082} 1083 1084 1085/* validate_varargslist() 1086 * 1087 * varargslist: 1088 * (fpdef ['=' test] ',')* 1089 * ('*' NAME [',' '**' NAME] 1090 * | '**' NAME) 1091 * | fpdef ['=' test] (',' fpdef ['=' test])* [','] 1092 * 1093 */ 1094static int 1095validate_varargslist(node *tree) 1096{ 1097 int nch = NCH(tree); 1098 int res = validate_ntype(tree, varargslist) && (nch != 0); 1099 int sym; 1100 1101 if (!res) 1102 return 0; 1103 if (nch < 1) { 1104 err_string("varargslist missing child nodes"); 1105 return 0; 1106 } 1107 sym = TYPE(CHILD(tree, 0)); 1108 if (sym == STAR || sym == DOUBLESTAR) 1109 /* whole thing matches: 1110 * '*' NAME [',' '**' NAME] | '**' NAME 1111 */ 1112 res = validate_varargslist_trailer(tree, 0); 1113 else if (sym == fpdef) { 1114 int i = 0; 1115 1116 sym = TYPE(CHILD(tree, nch-1)); 1117 if (sym == NAME) { 1118 /* 1119 * (fpdef ['=' test] ',')+ 1120 * ('*' NAME [',' '**' NAME] 1121 * | '**' NAME) 1122 */ 1123 /* skip over (fpdef ['=' test] ',')+ */ 1124 while (res && (i+2 <= nch)) { 1125 res = validate_fpdef(CHILD(tree, i)); 1126 ++i; 1127 if (res && TYPE(CHILD(tree, i)) == EQUAL && (i+2 <= nch)) { 1128 res = (validate_equal(CHILD(tree, i)) 1129 && validate_test(CHILD(tree, i+1))); 1130 if (res) 1131 i += 2; 1132 } 1133 if (res && i < nch) { 1134 res = validate_comma(CHILD(tree, i)); 1135 ++i; 1136 if (res && i < nch 1137 && (TYPE(CHILD(tree, i)) == DOUBLESTAR 1138 || TYPE(CHILD(tree, i)) == STAR)) 1139 break; 1140 } 1141 } 1142 /* ... '*' NAME [',' '**' NAME] | '**' NAME 1143 * i --^^^ 1144 */ 1145 if (res) 1146 res = validate_varargslist_trailer(tree, i); 1147 } 1148 else { 1149 /* 1150 * fpdef ['=' test] (',' fpdef ['=' test])* [','] 1151 */ 1152 /* strip trailing comma node */ 1153 if (sym == COMMA) { 1154 res = validate_comma(CHILD(tree, nch-1)); 1155 if (!res) 1156 return 0; 1157 --nch; 1158 } 1159 /* 1160 * fpdef ['=' test] (',' fpdef ['=' test])* 1161 */ 1162 res = validate_fpdef(CHILD(tree, 0)); 1163 ++i; 1164 if (res && (i+2 <= nch) && TYPE(CHILD(tree, i)) == EQUAL) { 1165 res = (validate_equal(CHILD(tree, i)) 1166 && validate_test(CHILD(tree, i+1))); 1167 i += 2; 1168 } 1169 /* 1170 * ... (',' fpdef ['=' test])* 1171 * i ---^^^ 1172 */ 1173 while (res && (nch - i) >= 2) { 1174 res = (validate_comma(CHILD(tree, i)) 1175 && validate_fpdef(CHILD(tree, i+1))); 1176 i += 2; 1177 if (res && (nch - i) >= 2 && TYPE(CHILD(tree, i)) == EQUAL) { 1178 res = (validate_equal(CHILD(tree, i)) 1179 && validate_test(CHILD(tree, i+1))); 1180 i += 2; 1181 } 1182 } 1183 if (res && nch - i != 0) { 1184 res = 0; 1185 err_string("illegal formation for varargslist"); 1186 } 1187 } 1188 } 1189 return res; 1190} 1191 1192 1193/* list_iter: list_for | list_if 1194 */ 1195static int 1196validate_list_iter(node *tree) 1197{ 1198 int res = (validate_ntype(tree, list_iter) 1199 && validate_numnodes(tree, 1, "list_iter")); 1200 if (res && TYPE(CHILD(tree, 0)) == list_for) 1201 res = validate_list_for(CHILD(tree, 0)); 1202 else 1203 res = validate_list_if(CHILD(tree, 0)); 1204 1205 return res; 1206} 1207 1208/* list_for: 'for' exprlist 'in' testlist [list_iter] 1209 */ 1210static int 1211validate_list_for(node *tree) 1212{ 1213 int nch = NCH(tree); 1214 int res; 1215 1216 if (nch == 5) 1217 res = validate_list_iter(CHILD(tree, 4)); 1218 else 1219 res = validate_numnodes(tree, 4, "list_for"); 1220 1221 if (res) 1222 res = (validate_name(CHILD(tree, 0), "for") 1223 && validate_exprlist(CHILD(tree, 1)) 1224 && validate_name(CHILD(tree, 2), "in") 1225 && validate_testlist(CHILD(tree, 3))); 1226 1227 return res; 1228} 1229 1230/* list_if: 'if' test [list_iter] 1231 */ 1232static int 1233validate_list_if(node *tree) 1234{ 1235 int nch = NCH(tree); 1236 int res; 1237 1238 if (nch == 3) 1239 res = validate_list_iter(CHILD(tree, 2)); 1240 else 1241 res = validate_numnodes(tree, 2, "list_if"); 1242 1243 if (res) 1244 res = (validate_name(CHILD(tree, 0), "if") 1245 && validate_test(CHILD(tree, 1))); 1246 1247 return res; 1248} 1249 1250 1251/* validate_fpdef() 1252 * 1253 * fpdef: 1254 * NAME 1255 * | '(' fplist ')' 1256 */ 1257static int 1258validate_fpdef(node *tree) 1259{ 1260 int nch = NCH(tree); 1261 int res = validate_ntype(tree, fpdef); 1262 1263 if (res) { 1264 if (nch == 1) 1265 res = validate_ntype(CHILD(tree, 0), NAME); 1266 else if (nch == 3) 1267 res = (validate_lparen(CHILD(tree, 0)) 1268 && validate_fplist(CHILD(tree, 1)) 1269 && validate_rparen(CHILD(tree, 2))); 1270 else 1271 res = validate_numnodes(tree, 1, "fpdef"); 1272 } 1273 return (res); 1274} 1275 1276 1277static int 1278validate_fplist(node *tree) 1279{ 1280 return (validate_repeating_list(tree, fplist, 1281 validate_fpdef, "fplist")); 1282} 1283 1284 1285/* simple_stmt | compound_stmt 1286 * 1287 */ 1288static int 1289validate_stmt(node *tree) 1290{ 1291 int res = (validate_ntype(tree, stmt) 1292 && validate_numnodes(tree, 1, "stmt")); 1293 1294 if (res) { 1295 tree = CHILD(tree, 0); 1296 1297 if (TYPE(tree) == simple_stmt) 1298 res = validate_simple_stmt(tree); 1299 else 1300 res = validate_compound_stmt(tree); 1301 } 1302 return (res); 1303} 1304 1305 1306/* small_stmt (';' small_stmt)* [';'] NEWLINE 1307 * 1308 */ 1309static int 1310validate_simple_stmt(node *tree) 1311{ 1312 int nch = NCH(tree); 1313 int res = (validate_ntype(tree, simple_stmt) 1314 && (nch >= 2) 1315 && validate_small_stmt(CHILD(tree, 0)) 1316 && validate_newline(CHILD(tree, nch - 1))); 1317 1318 if (nch < 2) 1319 res = validate_numnodes(tree, 2, "simple_stmt"); 1320 --nch; /* forget the NEWLINE */ 1321 if (res && is_even(nch)) 1322 res = validate_semi(CHILD(tree, --nch)); 1323 if (res && (nch > 2)) { 1324 int i; 1325 1326 for (i = 1; res && (i < nch); i += 2) 1327 res = (validate_semi(CHILD(tree, i)) 1328 && validate_small_stmt(CHILD(tree, i + 1))); 1329 } 1330 return (res); 1331} 1332 1333 1334static int 1335validate_small_stmt(node *tree) 1336{ 1337 int nch = NCH(tree); 1338 int res = validate_numnodes(tree, 1, "small_stmt"); 1339 1340 if (res) { 1341 int ntype = TYPE(CHILD(tree, 0)); 1342 1343 if ( (ntype == expr_stmt) 1344 || (ntype == print_stmt) 1345 || (ntype == del_stmt) 1346 || (ntype == pass_stmt) 1347 || (ntype == flow_stmt) 1348 || (ntype == import_stmt) 1349 || (ntype == global_stmt) 1350 || (ntype == assert_stmt) 1351 || (ntype == exec_stmt)) 1352 res = validate_node(CHILD(tree, 0)); 1353 else { 1354 res = 0; 1355 err_string("illegal small_stmt child type"); 1356 } 1357 } 1358 else if (nch == 1) { 1359 res = 0; 1360 PyErr_Format(parser_error, 1361 "Unrecognized child node of small_stmt: %d.", 1362 TYPE(CHILD(tree, 0))); 1363 } 1364 return (res); 1365} 1366 1367 1368/* compound_stmt: 1369 * if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef 1370 */ 1371static int 1372validate_compound_stmt(node *tree) 1373{ 1374 int res = (validate_ntype(tree, compound_stmt) 1375 && validate_numnodes(tree, 1, "compound_stmt")); 1376 int ntype; 1377 1378 if (!res) 1379 return (0); 1380 1381 tree = CHILD(tree, 0); 1382 ntype = TYPE(tree); 1383 if ( (ntype == if_stmt) 1384 || (ntype == while_stmt) 1385 || (ntype == for_stmt) 1386 || (ntype == try_stmt) 1387 || (ntype == funcdef) 1388 || (ntype == classdef)) 1389 res = validate_node(tree); 1390 else { 1391 res = 0; 1392 PyErr_Format(parser_error, 1393 "Illegal compound statement type: %d.", TYPE(tree)); 1394 } 1395 return (res); 1396} 1397 1398 1399static int 1400validate_expr_stmt(node *tree) 1401{ 1402 int j; 1403 int nch = NCH(tree); 1404 int res = (validate_ntype(tree, expr_stmt) 1405 && is_odd(nch) 1406 && validate_testlist(CHILD(tree, 0))); 1407 1408 if (res && nch == 3 1409 && TYPE(CHILD(tree, 1)) == augassign) { 1410 res = (validate_numnodes(CHILD(tree, 1), 1, "augassign") 1411 && validate_testlist(CHILD(tree, 2))); 1412 1413 if (res) { 1414 char *s = STR(CHILD(CHILD(tree, 1), 0)); 1415 1416 res = (strcmp(s, "+=") == 0 1417 || strcmp(s, "-=") == 0 1418 || strcmp(s, "*=") == 0 1419 || strcmp(s, "/=") == 0 1420 || strcmp(s, "%=") == 0 1421 || strcmp(s, "&=") == 0 1422 || strcmp(s, "|=") == 0 1423 || strcmp(s, "^=") == 0 1424 || strcmp(s, "<<=") == 0 1425 || strcmp(s, ">>=") == 0 1426 || strcmp(s, "**=") == 0); 1427 if (!res) 1428 err_string("illegal augmmented assignment operator"); 1429 } 1430 } 1431 else { 1432 for (j = 1; res && (j < nch); j += 2) 1433 res = (validate_equal(CHILD(tree, j)) 1434 && validate_testlist(CHILD(tree, j + 1))); 1435 } 1436 return (res); 1437} 1438 1439 1440/* print_stmt: 1441 * 1442 * 'print' ( [ test (',' test)* [','] ] 1443 * | '>>' test [ (',' test)+ [','] ] ) 1444 */ 1445static int 1446validate_print_stmt(node *tree) 1447{ 1448 int nch = NCH(tree); 1449 int res = (validate_ntype(tree, print_stmt) 1450 && (nch > 0) 1451 && validate_name(CHILD(tree, 0), "print")); 1452 1453 if (res && nch > 1) { 1454 int sym = TYPE(CHILD(tree, 1)); 1455 int i = 1; 1456 int allow_trailing_comma = 1; 1457 1458 if (sym == test) 1459 res = validate_test(CHILD(tree, i++)); 1460 else { 1461 if (nch < 3) 1462 res = validate_numnodes(tree, 3, "print_stmt"); 1463 else { 1464 res = (validate_ntype(CHILD(tree, i), RIGHTSHIFT) 1465 && validate_test(CHILD(tree, i+1))); 1466 i += 2; 1467 allow_trailing_comma = 0; 1468 } 1469 } 1470 if (res) { 1471 /* ... (',' test)* [','] */ 1472 while (res && i+2 <= nch) { 1473 res = (validate_comma(CHILD(tree, i)) 1474 && validate_test(CHILD(tree, i+1))); 1475 allow_trailing_comma = 1; 1476 i += 2; 1477 } 1478 if (res && !allow_trailing_comma) 1479 res = validate_numnodes(tree, i, "print_stmt"); 1480 else if (res && i < nch) 1481 res = validate_comma(CHILD(tree, i)); 1482 } 1483 } 1484 return (res); 1485} 1486 1487 1488static int 1489validate_del_stmt(node *tree) 1490{ 1491 return (validate_numnodes(tree, 2, "del_stmt") 1492 && validate_name(CHILD(tree, 0), "del") 1493 && validate_exprlist(CHILD(tree, 1))); 1494} 1495 1496 1497static int 1498validate_return_stmt(node *tree) 1499{ 1500 int nch = NCH(tree); 1501 int res = (validate_ntype(tree, return_stmt) 1502 && ((nch == 1) || (nch == 2)) 1503 && validate_name(CHILD(tree, 0), "return")); 1504 1505 if (res && (nch == 2)) 1506 res = validate_testlist(CHILD(tree, 1)); 1507 1508 return (res); 1509} 1510 1511 1512static int 1513validate_raise_stmt(node *tree) 1514{ 1515 int nch = NCH(tree); 1516 int res = (validate_ntype(tree, raise_stmt) 1517 && ((nch == 1) || (nch == 2) || (nch == 4) || (nch == 6))); 1518 1519 if (res) { 1520 res = validate_name(CHILD(tree, 0), "raise"); 1521 if (res && (nch >= 2)) 1522 res = validate_test(CHILD(tree, 1)); 1523 if (res && nch > 2) { 1524 res = (validate_comma(CHILD(tree, 2)) 1525 && validate_test(CHILD(tree, 3))); 1526 if (res && (nch > 4)) 1527 res = (validate_comma(CHILD(tree, 4)) 1528 && validate_test(CHILD(tree, 5))); 1529 } 1530 } 1531 else 1532 (void) validate_numnodes(tree, 2, "raise"); 1533 if (res && (nch == 4)) 1534 res = (validate_comma(CHILD(tree, 2)) 1535 && validate_test(CHILD(tree, 3))); 1536 1537 return (res); 1538} 1539 1540 1541static int 1542validate_import_as_name(node *tree) 1543{ 1544 int nch = NCH(tree); 1545 int ok = validate_ntype(tree, import_as_name); 1546 1547 if (ok) { 1548 if (nch == 1) 1549 ok = validate_name(CHILD(tree, 0), NULL); 1550 else if (nch == 3) 1551 ok = (validate_name(CHILD(tree, 0), NULL) 1552 && validate_name(CHILD(tree, 1), "as") 1553 && validate_name(CHILD(tree, 2), NULL)); 1554 else 1555 ok = validate_numnodes(tree, 3, "import_as_name"); 1556 } 1557 return ok; 1558} 1559 1560 1561/* dotted_name: NAME ("." NAME)* 1562 */ 1563static int 1564validate_dotted_name(node *tree) 1565{ 1566 int nch = NCH(tree); 1567 int res = (validate_ntype(tree, dotted_name) 1568 && is_odd(nch) 1569 && validate_name(CHILD(tree, 0), NULL)); 1570 int i; 1571 1572 for (i = 1; res && (i < nch); i += 2) { 1573 res = (validate_dot(CHILD(tree, i)) 1574 && validate_name(CHILD(tree, i+1), NULL)); 1575 } 1576 return res; 1577} 1578 1579 1580/* dotted_as_name: dotted_name [NAME NAME] 1581 */ 1582static int 1583validate_dotted_as_name(node *tree) 1584{ 1585 int nch = NCH(tree); 1586 int res = validate_ntype(tree, dotted_as_name); 1587 1588 if (res) { 1589 if (nch == 1) 1590 res = validate_dotted_name(CHILD(tree, 0)); 1591 else if (nch == 3) 1592 res = (validate_dotted_name(CHILD(tree, 0)) 1593 && validate_name(CHILD(tree, 1), "as") 1594 && validate_name(CHILD(tree, 2), NULL)); 1595 else { 1596 res = 0; 1597 err_string("illegal number of children for dotted_as_name"); 1598 } 1599 } 1600 return res; 1601} 1602 1603 1604/* import_stmt: 1605 * 1606 * 'import' dotted_as_name (',' dotted_as_name)* 1607 * | 'from' dotted_name 'import' ('*' | import_as_name (',' import_as_name)*) 1608 */ 1609static int 1610validate_import_stmt(node *tree) 1611{ 1612 int nch = NCH(tree); 1613 int res = (validate_ntype(tree, import_stmt) 1614 && (nch >= 2) && is_even(nch) 1615 && validate_ntype(CHILD(tree, 0), NAME)); 1616 1617 if (res && (strcmp(STR(CHILD(tree, 0)), "import") == 0)) { 1618 int j; 1619 1620 res = validate_dotted_as_name(CHILD(tree, 1)); 1621 for (j = 2; res && (j < nch); j += 2) 1622 res = (validate_comma(CHILD(tree, j)) 1623 && validate_dotted_as_name(CHILD(tree, j + 1))); 1624 } 1625 else if (res && (res = validate_name(CHILD(tree, 0), "from"))) { 1626 res = ((nch >= 4) && is_even(nch) 1627 && validate_dotted_name(CHILD(tree, 1)) 1628 && validate_name(CHILD(tree, 2), "import")); 1629 if (nch == 4) { 1630 if (TYPE(CHILD(tree, 3)) == import_as_name) 1631 res = validate_import_as_name(CHILD(tree, 3)); 1632 else 1633 res = validate_star(CHILD(tree, 3)); 1634 } 1635 else { 1636 /* 'from' dotted_name 'import' import_as_name 1637 * (',' import_as_name)+ 1638 */ 1639 int j; 1640 res = validate_import_as_name(CHILD(tree, 3)); 1641 for (j = 4; res && (j < nch); j += 2) 1642 res = (validate_comma(CHILD(tree, j)) 1643 && validate_import_as_name(CHILD(tree, j + 1))); 1644 } 1645 } 1646 else 1647 res = 0; 1648 1649 return (res); 1650} 1651 1652 1653static int 1654validate_global_stmt(node *tree) 1655{ 1656 int j; 1657 int nch = NCH(tree); 1658 int res = (validate_ntype(tree, global_stmt) 1659 && is_even(nch) && (nch >= 2)); 1660 1661 if (res) 1662 res = (validate_name(CHILD(tree, 0), "global") 1663 && validate_ntype(CHILD(tree, 1), NAME)); 1664 for (j = 2; res && (j < nch); j += 2) 1665 res = (validate_comma(CHILD(tree, j)) 1666 && validate_ntype(CHILD(tree, j + 1), NAME)); 1667 1668 return (res); 1669} 1670 1671 1672/* exec_stmt: 1673 * 1674 * 'exec' expr ['in' test [',' test]] 1675 */ 1676static int 1677validate_exec_stmt(node *tree) 1678{ 1679 int nch = NCH(tree); 1680 int res = (validate_ntype(tree, exec_stmt) 1681 && ((nch == 2) || (nch == 4) || (nch == 6)) 1682 && validate_name(CHILD(tree, 0), "exec") 1683 && validate_expr(CHILD(tree, 1))); 1684 1685 if (!res && !PyErr_Occurred()) 1686 err_string("illegal exec statement"); 1687 if (res && (nch > 2)) 1688 res = (validate_name(CHILD(tree, 2), "in") 1689 && validate_test(CHILD(tree, 3))); 1690 if (res && (nch == 6)) 1691 res = (validate_comma(CHILD(tree, 4)) 1692 && validate_test(CHILD(tree, 5))); 1693 1694 return (res); 1695} 1696 1697 1698/* assert_stmt: 1699 * 1700 * 'assert' test [',' test] 1701 */ 1702static int 1703validate_assert_stmt(node *tree) 1704{ 1705 int nch = NCH(tree); 1706 int res = (validate_ntype(tree, assert_stmt) 1707 && ((nch == 2) || (nch == 4)) 1708 && (validate_name(CHILD(tree, 0), "__assert__") || 1709 validate_name(CHILD(tree, 0), "assert")) 1710 && validate_test(CHILD(tree, 1))); 1711 1712 if (!res && !PyErr_Occurred()) 1713 err_string("illegal assert statement"); 1714 if (res && (nch > 2)) 1715 res = (validate_comma(CHILD(tree, 2)) 1716 && validate_test(CHILD(tree, 3))); 1717 1718 return (res); 1719} 1720 1721 1722static int 1723validate_while(node *tree) 1724{ 1725 int nch = NCH(tree); 1726 int res = (validate_ntype(tree, while_stmt) 1727 && ((nch == 4) || (nch == 7)) 1728 && validate_name(CHILD(tree, 0), "while") 1729 && validate_test(CHILD(tree, 1)) 1730 && validate_colon(CHILD(tree, 2)) 1731 && validate_suite(CHILD(tree, 3))); 1732 1733 if (res && (nch == 7)) 1734 res = (validate_name(CHILD(tree, 4), "else") 1735 && validate_colon(CHILD(tree, 5)) 1736 && validate_suite(CHILD(tree, 6))); 1737 1738 return (res); 1739} 1740 1741 1742static int 1743validate_for(node *tree) 1744{ 1745 int nch = NCH(tree); 1746 int res = (validate_ntype(tree, for_stmt) 1747 && ((nch == 6) || (nch == 9)) 1748 && validate_name(CHILD(tree, 0), "for") 1749 && validate_exprlist(CHILD(tree, 1)) 1750 && validate_name(CHILD(tree, 2), "in") 1751 && validate_testlist(CHILD(tree, 3)) 1752 && validate_colon(CHILD(tree, 4)) 1753 && validate_suite(CHILD(tree, 5))); 1754 1755 if (res && (nch == 9)) 1756 res = (validate_name(CHILD(tree, 6), "else") 1757 && validate_colon(CHILD(tree, 7)) 1758 && validate_suite(CHILD(tree, 8))); 1759 1760 return (res); 1761} 1762 1763 1764/* try_stmt: 1765 * 'try' ':' suite (except_clause ':' suite)+ ['else' ':' suite] 1766 * | 'try' ':' suite 'finally' ':' suite 1767 * 1768 */ 1769static int 1770validate_try(node *tree) 1771{ 1772 int nch = NCH(tree); 1773 int pos = 3; 1774 int res = (validate_ntype(tree, try_stmt) 1775 && (nch >= 6) && ((nch % 3) == 0)); 1776 1777 if (res) 1778 res = (validate_name(CHILD(tree, 0), "try") 1779 && validate_colon(CHILD(tree, 1)) 1780 && validate_suite(CHILD(tree, 2)) 1781 && validate_colon(CHILD(tree, nch - 2)) 1782 && validate_suite(CHILD(tree, nch - 1))); 1783 else if (!PyErr_Occurred()) { 1784 const char* name = "except"; 1785 if (TYPE(CHILD(tree, nch - 3)) != except_clause) 1786 name = STR(CHILD(tree, nch - 3)); 1787 1788 PyErr_Format(parser_error, 1789 "Illegal number of children for try/%s node.", name); 1790 } 1791 /* Skip past except_clause sections: */ 1792 while (res && (TYPE(CHILD(tree, pos)) == except_clause)) { 1793 res = (validate_except_clause(CHILD(tree, pos)) 1794 && validate_colon(CHILD(tree, pos + 1)) 1795 && validate_suite(CHILD(tree, pos + 2))); 1796 pos += 3; 1797 } 1798 if (res && (pos < nch)) { 1799 res = validate_ntype(CHILD(tree, pos), NAME); 1800 if (res && (strcmp(STR(CHILD(tree, pos)), "finally") == 0)) 1801 res = (validate_numnodes(tree, 6, "try/finally") 1802 && validate_colon(CHILD(tree, 4)) 1803 && validate_suite(CHILD(tree, 5))); 1804 else if (res) { 1805 if (nch == (pos + 3)) { 1806 res = ((strcmp(STR(CHILD(tree, pos)), "except") == 0) 1807 || (strcmp(STR(CHILD(tree, pos)), "else") == 0)); 1808 if (!res) 1809 err_string("illegal trailing triple in try statement"); 1810 } 1811 else if (nch == (pos + 6)) { 1812 res = (validate_name(CHILD(tree, pos), "except") 1813 && validate_colon(CHILD(tree, pos + 1)) 1814 && validate_suite(CHILD(tree, pos + 2)) 1815 && validate_name(CHILD(tree, pos + 3), "else")); 1816 } 1817 else 1818 res = validate_numnodes(tree, pos + 3, "try/except"); 1819 } 1820 } 1821 return (res); 1822} 1823 1824 1825static int 1826validate_except_clause(node *tree) 1827{ 1828 int nch = NCH(tree); 1829 int res = (validate_ntype(tree, except_clause) 1830 && ((nch == 1) || (nch == 2) || (nch == 4)) 1831 && validate_name(CHILD(tree, 0), "except")); 1832 1833 if (res && (nch > 1)) 1834 res = validate_test(CHILD(tree, 1)); 1835 if (res && (nch == 4)) 1836 res = (validate_comma(CHILD(tree, 2)) 1837 && validate_test(CHILD(tree, 3))); 1838 1839 return (res); 1840} 1841 1842 1843static int 1844validate_test(node *tree) 1845{ 1846 int nch = NCH(tree); 1847 int res = validate_ntype(tree, test) && is_odd(nch); 1848 1849 if (res && (TYPE(CHILD(tree, 0)) == lambdef)) 1850 res = ((nch == 1) 1851 && validate_lambdef(CHILD(tree, 0))); 1852 else if (res) { 1853 int pos; 1854 res = validate_and_test(CHILD(tree, 0)); 1855 for (pos = 1; res && (pos < nch); pos += 2) 1856 res = (validate_name(CHILD(tree, pos), "or") 1857 && validate_and_test(CHILD(tree, pos + 1))); 1858 } 1859 return (res); 1860} 1861 1862 1863static int 1864validate_and_test(node *tree) 1865{ 1866 int pos; 1867 int nch = NCH(tree); 1868 int res = (validate_ntype(tree, and_test) 1869 && is_odd(nch) 1870 && validate_not_test(CHILD(tree, 0))); 1871 1872 for (pos = 1; res && (pos < nch); pos += 2) 1873 res = (validate_name(CHILD(tree, pos), "and") 1874 && validate_not_test(CHILD(tree, 0))); 1875 1876 return (res); 1877} 1878 1879 1880static int 1881validate_not_test(node *tree) 1882{ 1883 int nch = NCH(tree); 1884 int res = validate_ntype(tree, not_test) && ((nch == 1) || (nch == 2)); 1885 1886 if (res) { 1887 if (nch == 2) 1888 res = (validate_name(CHILD(tree, 0), "not") 1889 && validate_not_test(CHILD(tree, 1))); 1890 else if (nch == 1) 1891 res = validate_comparison(CHILD(tree, 0)); 1892 } 1893 return (res); 1894} 1895 1896 1897static int 1898validate_comparison(node *tree) 1899{ 1900 int pos; 1901 int nch = NCH(tree); 1902 int res = (validate_ntype(tree, comparison) 1903 && is_odd(nch) 1904 && validate_expr(CHILD(tree, 0))); 1905 1906 for (pos = 1; res && (pos < nch); pos += 2) 1907 res = (validate_comp_op(CHILD(tree, pos)) 1908 && validate_expr(CHILD(tree, pos + 1))); 1909 1910 return (res); 1911} 1912 1913 1914static int 1915validate_comp_op(node *tree) 1916{ 1917 int res = 0; 1918 int nch = NCH(tree); 1919 1920 if (!validate_ntype(tree, comp_op)) 1921 return (0); 1922 if (nch == 1) { 1923 /* 1924 * Only child will be a terminal with a well-defined symbolic name 1925 * or a NAME with a string of either 'is' or 'in' 1926 */ 1927 tree = CHILD(tree, 0); 1928 switch (TYPE(tree)) { 1929 case LESS: 1930 case GREATER: 1931 case EQEQUAL: 1932 case EQUAL: 1933 case LESSEQUAL: 1934 case GREATEREQUAL: 1935 case NOTEQUAL: 1936 res = 1; 1937 break; 1938 case NAME: 1939 res = ((strcmp(STR(tree), "in") == 0) 1940 || (strcmp(STR(tree), "is") == 0)); 1941 if (!res) { 1942 PyErr_Format(parser_error, 1943 "illegal operator '%s'", STR(tree)); 1944 } 1945 break; 1946 default: 1947 err_string("illegal comparison operator type"); 1948 break; 1949 } 1950 } 1951 else if ((res = validate_numnodes(tree, 2, "comp_op")) != 0) { 1952 res = (validate_ntype(CHILD(tree, 0), NAME) 1953 && validate_ntype(CHILD(tree, 1), NAME) 1954 && (((strcmp(STR(CHILD(tree, 0)), "is") == 0) 1955 && (strcmp(STR(CHILD(tree, 1)), "not") == 0)) 1956 || ((strcmp(STR(CHILD(tree, 0)), "not") == 0) 1957 && (strcmp(STR(CHILD(tree, 1)), "in") == 0)))); 1958 if (!res && !PyErr_Occurred()) 1959 err_string("unknown comparison operator"); 1960 } 1961 return (res); 1962} 1963 1964 1965static int 1966validate_expr(node *tree) 1967{ 1968 int j; 1969 int nch = NCH(tree); 1970 int res = (validate_ntype(tree, expr) 1971 && is_odd(nch) 1972 && validate_xor_expr(CHILD(tree, 0))); 1973 1974 for (j = 2; res && (j < nch); j += 2) 1975 res = (validate_xor_expr(CHILD(tree, j)) 1976 && validate_vbar(CHILD(tree, j - 1))); 1977 1978 return (res); 1979} 1980 1981 1982static int 1983validate_xor_expr(node *tree) 1984{ 1985 int j; 1986 int nch = NCH(tree); 1987 int res = (validate_ntype(tree, xor_expr) 1988 && is_odd(nch) 1989 && validate_and_expr(CHILD(tree, 0))); 1990 1991 for (j = 2; res && (j < nch); j += 2) 1992 res = (validate_circumflex(CHILD(tree, j - 1)) 1993 && validate_and_expr(CHILD(tree, j))); 1994 1995 return (res); 1996} 1997 1998 1999static int 2000validate_and_expr(node *tree) 2001{ 2002 int pos; 2003 int nch = NCH(tree); 2004 int res = (validate_ntype(tree, and_expr) 2005 && is_odd(nch) 2006 && validate_shift_expr(CHILD(tree, 0))); 2007 2008 for (pos = 1; res && (pos < nch); pos += 2) 2009 res = (validate_ampersand(CHILD(tree, pos)) 2010 && validate_shift_expr(CHILD(tree, pos + 1))); 2011 2012 return (res); 2013} 2014 2015 2016static int 2017validate_chain_two_ops(node *tree, int (*termvalid)(node *), int op1, int op2) 2018 { 2019 int pos = 1; 2020 int nch = NCH(tree); 2021 int res = (is_odd(nch) 2022 && (*termvalid)(CHILD(tree, 0))); 2023 2024 for ( ; res && (pos < nch); pos += 2) { 2025 if (TYPE(CHILD(tree, pos)) != op1) 2026 res = validate_ntype(CHILD(tree, pos), op2); 2027 if (res) 2028 res = (*termvalid)(CHILD(tree, pos + 1)); 2029 } 2030 return (res); 2031} 2032 2033 2034static int 2035validate_shift_expr(node *tree) 2036{ 2037 return (validate_ntype(tree, shift_expr) 2038 && validate_chain_two_ops(tree, validate_arith_expr, 2039 LEFTSHIFT, RIGHTSHIFT)); 2040} 2041 2042 2043static int 2044validate_arith_expr(node *tree) 2045{ 2046 return (validate_ntype(tree, arith_expr) 2047 && validate_chain_two_ops(tree, validate_term, PLUS, MINUS)); 2048} 2049 2050 2051static int 2052validate_term(node *tree) 2053{ 2054 int pos = 1; 2055 int nch = NCH(tree); 2056 int res = (validate_ntype(tree, term) 2057 && is_odd(nch) 2058 && validate_factor(CHILD(tree, 0))); 2059 2060 for ( ; res && (pos < nch); pos += 2) 2061 res = (((TYPE(CHILD(tree, pos)) == STAR) 2062 || (TYPE(CHILD(tree, pos)) == SLASH) 2063 || (TYPE(CHILD(tree, pos)) == PERCENT)) 2064 && validate_factor(CHILD(tree, pos + 1))); 2065 2066 return (res); 2067} 2068 2069 2070/* factor: 2071 * 2072 * factor: ('+'|'-'|'~') factor | power 2073 */ 2074static int 2075validate_factor(node *tree) 2076{ 2077 int nch = NCH(tree); 2078 int res = (validate_ntype(tree, factor) 2079 && (((nch == 2) 2080 && ((TYPE(CHILD(tree, 0)) == PLUS) 2081 || (TYPE(CHILD(tree, 0)) == MINUS) 2082 || (TYPE(CHILD(tree, 0)) == TILDE)) 2083 && validate_factor(CHILD(tree, 1))) 2084 || ((nch == 1) 2085 && validate_power(CHILD(tree, 0))))); 2086 return (res); 2087} 2088 2089 2090/* power: 2091 * 2092 * power: atom trailer* ('**' factor)* 2093 */ 2094static int 2095validate_power(node *tree) 2096{ 2097 int pos = 1; 2098 int nch = NCH(tree); 2099 int res = (validate_ntype(tree, power) && (nch >= 1) 2100 && validate_atom(CHILD(tree, 0))); 2101 2102 while (res && (pos < nch) && (TYPE(CHILD(tree, pos)) == trailer)) 2103 res = validate_trailer(CHILD(tree, pos++)); 2104 if (res && (pos < nch)) { 2105 if (!is_even(nch - pos)) { 2106 err_string("illegal number of nodes for 'power'"); 2107 return (0); 2108 } 2109 for ( ; res && (pos < (nch - 1)); pos += 2) 2110 res = (validate_doublestar(CHILD(tree, pos)) 2111 && validate_factor(CHILD(tree, pos + 1))); 2112 } 2113 return (res); 2114} 2115 2116 2117static int 2118validate_atom(node *tree) 2119{ 2120 int pos; 2121 int nch = NCH(tree); 2122 int res = validate_ntype(tree, atom); 2123 2124 if (res && nch < 1) 2125 res = validate_numnodes(tree, nch+1, "atom"); 2126 if (res) { 2127 switch (TYPE(CHILD(tree, 0))) { 2128 case LPAR: 2129 res = ((nch <= 3) 2130 && (validate_rparen(CHILD(tree, nch - 1)))); 2131 2132 if (res && (nch == 3)) 2133 res = validate_testlist(CHILD(tree, 1)); 2134 break; 2135 case LSQB: 2136 if (nch == 2) 2137 res = validate_ntype(CHILD(tree, 1), RSQB); 2138 else if (nch == 3) 2139 res = (validate_listmaker(CHILD(tree, 1)) 2140 && validate_ntype(CHILD(tree, 2), RSQB)); 2141 else { 2142 res = 0; 2143 err_string("illegal list display atom"); 2144 } 2145 break; 2146 case LBRACE: 2147 res = ((nch <= 3) 2148 && validate_ntype(CHILD(tree, nch - 1), RBRACE)); 2149 2150 if (res && (nch == 3)) 2151 res = validate_dictmaker(CHILD(tree, 1)); 2152 break; 2153 case BACKQUOTE: 2154 res = ((nch == 3) 2155 && validate_testlist(CHILD(tree, 1)) 2156 && validate_ntype(CHILD(tree, 2), BACKQUOTE)); 2157 break; 2158 case NAME: 2159 case NUMBER: 2160 res = (nch == 1); 2161 break; 2162 case STRING: 2163 for (pos = 1; res && (pos < nch); ++pos) 2164 res = validate_ntype(CHILD(tree, pos), STRING); 2165 break; 2166 default: 2167 res = 0; 2168 break; 2169 } 2170 } 2171 return (res); 2172} 2173 2174 2175/* listmaker: 2176 * test ( list_for | (',' test)* [','] ) 2177 */ 2178static int 2179validate_listmaker(node *tree) 2180{ 2181 int nch = NCH(tree); 2182 int ok = nch; 2183 2184 if (nch == 0) 2185 err_string("missing child nodes of listmaker"); 2186 else 2187 ok = validate_test(CHILD(tree, 0)); 2188 2189 /* 2190 * list_iter | (',' test)* [','] 2191 */ 2192 if (nch == 2 && TYPE(CHILD(tree, 1)) == list_for) 2193 ok = validate_list_for(CHILD(tree, 1)); 2194 else { 2195 /* (',' test)* [','] */ 2196 int i = 1; 2197 while (ok && nch - i >= 2) { 2198 ok = (validate_comma(CHILD(tree, i)) 2199 && validate_test(CHILD(tree, i+1))); 2200 i += 2; 2201 } 2202 if (ok && i == nch-1) 2203 ok = validate_comma(CHILD(tree, i)); 2204 else if (i != nch) { 2205 ok = 0; 2206 err_string("illegal trailing nodes for listmaker"); 2207 } 2208 } 2209 return ok; 2210} 2211 2212 2213/* funcdef: 2214 * 'def' NAME parameters ':' suite 2215 * 2216 */ 2217static int 2218validate_funcdef(node *tree) 2219{ 2220 return (validate_ntype(tree, funcdef) 2221 && validate_numnodes(tree, 5, "funcdef") 2222 && validate_name(CHILD(tree, 0), "def") 2223 && validate_ntype(CHILD(tree, 1), NAME) 2224 && validate_colon(CHILD(tree, 3)) 2225 && validate_parameters(CHILD(tree, 2)) 2226 && validate_suite(CHILD(tree, 4))); 2227} 2228 2229 2230static int 2231validate_lambdef(node *tree) 2232{ 2233 int nch = NCH(tree); 2234 int res = (validate_ntype(tree, lambdef) 2235 && ((nch == 3) || (nch == 4)) 2236 && validate_name(CHILD(tree, 0), "lambda") 2237 && validate_colon(CHILD(tree, nch - 2)) 2238 && validate_test(CHILD(tree, nch - 1))); 2239 2240 if (res && (nch == 4)) 2241 res = validate_varargslist(CHILD(tree, 1)); 2242 else if (!res && !PyErr_Occurred()) 2243 (void) validate_numnodes(tree, 3, "lambdef"); 2244 2245 return (res); 2246} 2247 2248 2249/* arglist: 2250 * 2251 * (argument ',')* (argument [','] | '*' test [',' '**' test] | '**' test) 2252 */ 2253static int 2254validate_arglist(node *tree) 2255{ 2256 int nch = NCH(tree); 2257 int i = 0; 2258 int ok = 1; 2259 2260 if (nch <= 0) 2261 /* raise the right error from having an invalid number of children */ 2262 return validate_numnodes(tree, nch + 1, "arglist"); 2263 2264 while (ok && nch-i >= 2) { 2265 /* skip leading (argument ',') */ 2266 ok = (validate_argument(CHILD(tree, i)) 2267 && validate_comma(CHILD(tree, i+1))); 2268 if (ok) 2269 i += 2; 2270 else 2271 PyErr_Clear(); 2272 } 2273 ok = 1; 2274 if (nch-i > 0) { 2275 /* 2276 * argument | '*' test [',' '**' test] | '**' test 2277 */ 2278 int sym = TYPE(CHILD(tree, i)); 2279 2280 if (sym == argument) { 2281 ok = validate_argument(CHILD(tree, i)); 2282 if (ok && i+1 != nch) { 2283 err_string("illegal arglist specification" 2284 " (extra stuff on end)"); 2285 ok = 0; 2286 } 2287 } 2288 else if (sym == STAR) { 2289 ok = validate_star(CHILD(tree, i)); 2290 if (ok && (nch-i == 2)) 2291 ok = validate_test(CHILD(tree, i+1)); 2292 else if (ok && (nch-i == 5)) 2293 ok = (validate_test(CHILD(tree, i+1)) 2294 && validate_comma(CHILD(tree, i+2)) 2295 && validate_doublestar(CHILD(tree, i+3)) 2296 && validate_test(CHILD(tree, i+4))); 2297 else { 2298 err_string("illegal use of '*' in arglist"); 2299 ok = 0; 2300 } 2301 } 2302 else if (sym == DOUBLESTAR) { 2303 if (nch-i == 2) 2304 ok = (validate_doublestar(CHILD(tree, i)) 2305 && validate_test(CHILD(tree, i+1))); 2306 else { 2307 err_string("illegal use of '**' in arglist"); 2308 ok = 0; 2309 } 2310 } 2311 else { 2312 err_string("illegal arglist specification"); 2313 ok = 0; 2314 } 2315 } 2316 return (ok); 2317} 2318 2319 2320 2321/* argument: 2322 * 2323 * [test '='] test 2324 */ 2325static int 2326validate_argument(node *tree) 2327{ 2328 int nch = NCH(tree); 2329 int res = (validate_ntype(tree, argument) 2330 && ((nch == 1) || (nch == 3)) 2331 && validate_test(CHILD(tree, 0))); 2332 2333 if (res && (nch == 3)) 2334 res = (validate_equal(CHILD(tree, 1)) 2335 && validate_test(CHILD(tree, 2))); 2336 2337 return (res); 2338} 2339 2340 2341 2342/* trailer: 2343 * 2344 * '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME 2345 */ 2346static int 2347validate_trailer(node *tree) 2348{ 2349 int nch = NCH(tree); 2350 int res = validate_ntype(tree, trailer) && ((nch == 2) || (nch == 3)); 2351 2352 if (res) { 2353 switch (TYPE(CHILD(tree, 0))) { 2354 case LPAR: 2355 res = validate_rparen(CHILD(tree, nch - 1)); 2356 if (res && (nch == 3)) 2357 res = validate_arglist(CHILD(tree, 1)); 2358 break; 2359 case LSQB: 2360 res = (validate_numnodes(tree, 3, "trailer") 2361 && validate_subscriptlist(CHILD(tree, 1)) 2362 && validate_ntype(CHILD(tree, 2), RSQB)); 2363 break; 2364 case DOT: 2365 res = (validate_numnodes(tree, 2, "trailer") 2366 && validate_ntype(CHILD(tree, 1), NAME)); 2367 break; 2368 default: 2369 res = 0; 2370 break; 2371 } 2372 } 2373 else { 2374 (void) validate_numnodes(tree, 2, "trailer"); 2375 } 2376 return (res); 2377} 2378 2379 2380/* subscriptlist: 2381 * 2382 * subscript (',' subscript)* [','] 2383 */ 2384static int 2385validate_subscriptlist(node *tree) 2386{ 2387 return (validate_repeating_list(tree, subscriptlist, 2388 validate_subscript, "subscriptlist")); 2389} 2390 2391 2392/* subscript: 2393 * 2394 * '.' '.' '.' | test | [test] ':' [test] [sliceop] 2395 */ 2396static int 2397validate_subscript(node *tree) 2398{ 2399 int offset = 0; 2400 int nch = NCH(tree); 2401 int res = validate_ntype(tree, subscript) && (nch >= 1) && (nch <= 4); 2402 2403 if (!res) { 2404 if (!PyErr_Occurred()) 2405 err_string("invalid number of arguments for subscript node"); 2406 return (0); 2407 } 2408 if (TYPE(CHILD(tree, 0)) == DOT) 2409 /* take care of ('.' '.' '.') possibility */ 2410 return (validate_numnodes(tree, 3, "subscript") 2411 && validate_dot(CHILD(tree, 0)) 2412 && validate_dot(CHILD(tree, 1)) 2413 && validate_dot(CHILD(tree, 2))); 2414 if (nch == 1) { 2415 if (TYPE(CHILD(tree, 0)) == test) 2416 res = validate_test(CHILD(tree, 0)); 2417 else 2418 res = validate_colon(CHILD(tree, 0)); 2419 return (res); 2420 } 2421 /* Must be [test] ':' [test] [sliceop], 2422 * but at least one of the optional components will 2423 * be present, but we don't know which yet. 2424 */ 2425 if ((TYPE(CHILD(tree, 0)) != COLON) || (nch == 4)) { 2426 res = validate_test(CHILD(tree, 0)); 2427 offset = 1; 2428 } 2429 if (res) 2430 res = validate_colon(CHILD(tree, offset)); 2431 if (res) { 2432 int rem = nch - ++offset; 2433 if (rem) { 2434 if (TYPE(CHILD(tree, offset)) == test) { 2435 res = validate_test(CHILD(tree, offset)); 2436 ++offset; 2437 --rem; 2438 } 2439 if (res && rem) 2440 res = validate_sliceop(CHILD(tree, offset)); 2441 } 2442 } 2443 return (res); 2444} 2445 2446 2447static int 2448validate_sliceop(node *tree) 2449{ 2450 int nch = NCH(tree); 2451 int res = ((nch == 1) || validate_numnodes(tree, 2, "sliceop")) 2452 && validate_ntype(tree, sliceop); 2453 if (!res && !PyErr_Occurred()) { 2454 res = validate_numnodes(tree, 1, "sliceop"); 2455 } 2456 if (res) 2457 res = validate_colon(CHILD(tree, 0)); 2458 if (res && (nch == 2)) 2459 res = validate_test(CHILD(tree, 1)); 2460 2461 return (res); 2462} 2463 2464 2465static int 2466validate_exprlist(node *tree) 2467{ 2468 return (validate_repeating_list(tree, exprlist, 2469 validate_expr, "exprlist")); 2470} 2471 2472 2473static int 2474validate_dictmaker(node *tree) 2475{ 2476 int nch = NCH(tree); 2477 int res = (validate_ntype(tree, dictmaker) 2478 && (nch >= 3) 2479 && validate_test(CHILD(tree, 0)) 2480 && validate_colon(CHILD(tree, 1)) 2481 && validate_test(CHILD(tree, 2))); 2482 2483 if (res && ((nch % 4) == 0)) 2484 res = validate_comma(CHILD(tree, --nch)); 2485 else if (res) 2486 res = ((nch % 4) == 3); 2487 2488 if (res && (nch > 3)) { 2489 int pos = 3; 2490 /* ( ',' test ':' test )* */ 2491 while (res && (pos < nch)) { 2492 res = (validate_comma(CHILD(tree, pos)) 2493 && validate_test(CHILD(tree, pos + 1)) 2494 && validate_colon(CHILD(tree, pos + 2)) 2495 && validate_test(CHILD(tree, pos + 3))); 2496 pos += 4; 2497 } 2498 } 2499 return (res); 2500} 2501 2502 2503static int 2504validate_eval_input(node *tree) 2505{ 2506 int pos; 2507 int nch = NCH(tree); 2508 int res = (validate_ntype(tree, eval_input) 2509 && (nch >= 2) 2510 && validate_testlist(CHILD(tree, 0)) 2511 && validate_ntype(CHILD(tree, nch - 1), ENDMARKER)); 2512 2513 for (pos = 1; res && (pos < (nch - 1)); ++pos) 2514 res = validate_ntype(CHILD(tree, pos), NEWLINE); 2515 2516 return (res); 2517} 2518 2519 2520static int 2521validate_node(node *tree) 2522{ 2523 int nch = 0; /* num. children on current node */ 2524 int res = 1; /* result value */ 2525 node* next = 0; /* node to process after this one */ 2526 2527 while (res && (tree != 0)) { 2528 nch = NCH(tree); 2529 next = 0; 2530 switch (TYPE(tree)) { 2531 /* 2532 * Definition nodes. 2533 */ 2534 case funcdef: 2535 res = validate_funcdef(tree); 2536 break; 2537 case classdef: 2538 res = validate_class(tree); 2539 break; 2540 /* 2541 * "Trivial" parse tree nodes. 2542 * (Why did I call these trivial?) 2543 */ 2544 case stmt: 2545 res = validate_stmt(tree); 2546 break; 2547 case small_stmt: 2548 /* 2549 * expr_stmt | print_stmt | del_stmt | pass_stmt | flow_stmt 2550 * | import_stmt | global_stmt | exec_stmt | assert_stmt 2551 */ 2552 res = validate_small_stmt(tree); 2553 break; 2554 case flow_stmt: 2555 res = (validate_numnodes(tree, 1, "flow_stmt") 2556 && ((TYPE(CHILD(tree, 0)) == break_stmt) 2557 || (TYPE(CHILD(tree, 0)) == continue_stmt) 2558 || (TYPE(CHILD(tree, 0)) == return_stmt) 2559 || (TYPE(CHILD(tree, 0)) == raise_stmt))); 2560 if (res) 2561 next = CHILD(tree, 0); 2562 else if (nch == 1) 2563 err_string("illegal flow_stmt type"); 2564 break; 2565 /* 2566 * Compound statements. 2567 */ 2568 case simple_stmt: 2569 res = validate_simple_stmt(tree); 2570 break; 2571 case compound_stmt: 2572 res = validate_compound_stmt(tree); 2573 break; 2574 /* 2575 * Fundamental statements. 2576 */ 2577 case expr_stmt: 2578 res = validate_expr_stmt(tree); 2579 break; 2580 case print_stmt: 2581 res = validate_print_stmt(tree); 2582 break; 2583 case del_stmt: 2584 res = validate_del_stmt(tree); 2585 break; 2586 case pass_stmt: 2587 res = (validate_numnodes(tree, 1, "pass") 2588 && validate_name(CHILD(tree, 0), "pass")); 2589 break; 2590 case break_stmt: 2591 res = (validate_numnodes(tree, 1, "break") 2592 && validate_name(CHILD(tree, 0), "break")); 2593 break; 2594 case continue_stmt: 2595 res = (validate_numnodes(tree, 1, "continue") 2596 && validate_name(CHILD(tree, 0), "continue")); 2597 break; 2598 case return_stmt: 2599 res = validate_return_stmt(tree); 2600 break; 2601 case raise_stmt: 2602 res = validate_raise_stmt(tree); 2603 break; 2604 case import_stmt: 2605 res = validate_import_stmt(tree); 2606 break; 2607 case global_stmt: 2608 res = validate_global_stmt(tree); 2609 break; 2610 case exec_stmt: 2611 res = validate_exec_stmt(tree); 2612 break; 2613 case assert_stmt: 2614 res = validate_assert_stmt(tree); 2615 break; 2616 case if_stmt: 2617 res = validate_if(tree); 2618 break; 2619 case while_stmt: 2620 res = validate_while(tree); 2621 break; 2622 case for_stmt: 2623 res = validate_for(tree); 2624 break; 2625 case try_stmt: 2626 res = validate_try(tree); 2627 break; 2628 case suite: 2629 res = validate_suite(tree); 2630 break; 2631 /* 2632 * Expression nodes. 2633 */ 2634 case testlist: 2635 res = validate_testlist(tree); 2636 break; 2637 case test: 2638 res = validate_test(tree); 2639 break; 2640 case and_test: 2641 res = validate_and_test(tree); 2642 break; 2643 case not_test: 2644 res = validate_not_test(tree); 2645 break; 2646 case comparison: 2647 res = validate_comparison(tree); 2648 break; 2649 case exprlist: 2650 res = validate_exprlist(tree); 2651 break; 2652 case comp_op: 2653 res = validate_comp_op(tree); 2654 break; 2655 case expr: 2656 res = validate_expr(tree); 2657 break; 2658 case xor_expr: 2659 res = validate_xor_expr(tree); 2660 break; 2661 case and_expr: 2662 res = validate_and_expr(tree); 2663 break; 2664 case shift_expr: 2665 res = validate_shift_expr(tree); 2666 break; 2667 case arith_expr: 2668 res = validate_arith_expr(tree); 2669 break; 2670 case term: 2671 res = validate_term(tree); 2672 break; 2673 case factor: 2674 res = validate_factor(tree); 2675 break; 2676 case power: 2677 res = validate_power(tree); 2678 break; 2679 case atom: 2680 res = validate_atom(tree); 2681 break; 2682 2683 default: 2684 /* Hopefully never reached! */ 2685 err_string("unrecognized node type"); 2686 res = 0; 2687 break; 2688 } 2689 tree = next; 2690 } 2691 return (res); 2692} 2693 2694 2695static int 2696validate_expr_tree(node *tree) 2697{ 2698 int res = validate_eval_input(tree); 2699 2700 if (!res && !PyErr_Occurred()) 2701 err_string("could not validate expression tuple"); 2702 2703 return (res); 2704} 2705 2706 2707/* file_input: 2708 * (NEWLINE | stmt)* ENDMARKER 2709 */ 2710static int 2711validate_file_input(node *tree) 2712{ 2713 int j = 0; 2714 int nch = NCH(tree) - 1; 2715 int res = ((nch >= 0) 2716 && validate_ntype(CHILD(tree, nch), ENDMARKER)); 2717 2718 for ( ; res && (j < nch); ++j) { 2719 if (TYPE(CHILD(tree, j)) == stmt) 2720 res = validate_stmt(CHILD(tree, j)); 2721 else 2722 res = validate_newline(CHILD(tree, j)); 2723 } 2724 /* This stays in to prevent any internal failures from getting to the 2725 * user. Hopefully, this won't be needed. If a user reports getting 2726 * this, we have some debugging to do. 2727 */ 2728 if (!res && !PyErr_Occurred()) 2729 err_string("VALIDATION FAILURE: report this to the maintainer!"); 2730 2731 return (res); 2732} 2733 2734 2735static PyObject* 2736pickle_constructor = NULL; 2737 2738 2739static PyObject* 2740parser__pickler(PyObject *self, PyObject *args) 2741{ 2742 NOTE(ARGUNUSED(self)) 2743 PyObject *result = NULL; 2744 PyObject *ast = NULL; 2745 PyObject *empty_dict = NULL; 2746 2747 if (PyArg_ParseTuple(args, "O!:_pickler", &PyAST_Type, &ast)) { 2748 PyObject *newargs; 2749 PyObject *tuple; 2750 2751 if ((empty_dict = PyDict_New()) == NULL) 2752 goto finally; 2753 if ((newargs = Py_BuildValue("Oi", ast, 1)) == NULL) 2754 goto finally; 2755 tuple = parser_ast2tuple((PyAST_Object*)NULL, newargs, empty_dict); 2756 if (tuple != NULL) { 2757 result = Py_BuildValue("O(O)", pickle_constructor, tuple); 2758 Py_DECREF(tuple); 2759 } 2760 Py_DECREF(empty_dict); 2761 Py_DECREF(newargs); 2762 } 2763 finally: 2764 Py_XDECREF(empty_dict); 2765 2766 return (result); 2767} 2768 2769 2770/* Functions exported by this module. Most of this should probably 2771 * be converted into an AST object with methods, but that is better 2772 * done directly in Python, allowing subclasses to be created directly. 2773 * We'd really have to write a wrapper around it all anyway to allow 2774 * inheritance. 2775 */ 2776static PyMethodDef parser_functions[] = { 2777 {"ast2tuple", (PyCFunction)parser_ast2tuple, PUBLIC_METHOD_TYPE, 2778 "Creates a tuple-tree representation of an AST."}, 2779 {"ast2list", (PyCFunction)parser_ast2list, PUBLIC_METHOD_TYPE, 2780 "Creates a list-tree representation of an AST."}, 2781 {"compileast", (PyCFunction)parser_compileast, PUBLIC_METHOD_TYPE, 2782 "Compiles an AST object into a code object."}, 2783 {"expr", (PyCFunction)parser_expr, PUBLIC_METHOD_TYPE, 2784 "Creates an AST object from an expression."}, 2785 {"isexpr", (PyCFunction)parser_isexpr, PUBLIC_METHOD_TYPE, 2786 "Determines if an AST object was created from an expression."}, 2787 {"issuite", (PyCFunction)parser_issuite, PUBLIC_METHOD_TYPE, 2788 "Determines if an AST object was created from a suite."}, 2789 {"suite", (PyCFunction)parser_suite, PUBLIC_METHOD_TYPE, 2790 "Creates an AST object from a suite."}, 2791 {"sequence2ast", (PyCFunction)parser_tuple2ast, PUBLIC_METHOD_TYPE, 2792 "Creates an AST object from a tree representation."}, 2793 {"tuple2ast", (PyCFunction)parser_tuple2ast, PUBLIC_METHOD_TYPE, 2794 "Creates an AST object from a tree representation."}, 2795 2796 /* private stuff: support pickle module */ 2797 {"_pickler", (PyCFunction)parser__pickler, METH_VARARGS, 2798 "Returns the pickle magic to allow ast objects to be pickled."}, 2799 2800 {NULL, NULL, 0, NULL} 2801 }; 2802 2803 2804DL_EXPORT(void) initparser(void); /* supply a prototype */ 2805 2806DL_EXPORT(void) 2807initparser(void) 2808{ 2809 PyObject* module; 2810 PyObject* dict; 2811 2812 PyAST_Type.ob_type = &PyType_Type; 2813 module = Py_InitModule("parser", parser_functions); 2814 dict = PyModule_GetDict(module); 2815 2816 if (parser_error == 0) 2817 parser_error = PyErr_NewException("parser.ParserError", NULL, NULL); 2818 2819 if ((parser_error == 0) 2820 || (PyDict_SetItemString(dict, "ParserError", parser_error) != 0)) 2821 { 2822 /* caller will check PyErr_Occurred() */ 2823 return; 2824 } 2825 /* 2826 * Nice to have, but don't cry if we fail. 2827 */ 2828 Py_INCREF(&PyAST_Type); 2829 PyDict_SetItemString(dict, "ASTType", (PyObject*)&PyAST_Type); 2830 2831 PyDict_SetItemString(dict, "__copyright__", 2832 PyString_FromString(parser_copyright_string)); 2833 PyDict_SetItemString(dict, "__doc__", 2834 PyString_FromString(parser_doc_string)); 2835 PyDict_SetItemString(dict, "__version__", 2836 PyString_FromString(parser_version_string)); 2837 2838 /* register to support pickling */ 2839 module = PyImport_ImportModule("copy_reg"); 2840 if (module != NULL) { 2841 PyObject *func, *pickler; 2842 2843 func = PyObject_GetAttrString(module, "pickle"); 2844 pickle_constructor = PyDict_GetItemString(dict, "sequence2ast"); 2845 pickler = PyDict_GetItemString(dict, "_pickler"); 2846 Py_XINCREF(pickle_constructor); 2847 if ((func != NULL) && (pickle_constructor != NULL) 2848 && (pickler != NULL)) { 2849 PyObject *res; 2850 2851 res = PyObject_CallFunction( 2852 func, "OOO", &PyAST_Type, pickler, pickle_constructor); 2853 Py_XDECREF(res); 2854 } 2855 Py_XDECREF(func); 2856 Py_DECREF(module); 2857 } 2858} 2859